1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
/*
This file is part of cpp-ethereum.
cpp-ethereum is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
cpp-ethereum is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with cpp-ethereum. If not, see <http://www.gnu.org/licenses/>.
*/
/**
* @file ControlFlowGraph.h
* @author Christian <c@ethdev.com>
* @date 2015
* Control flow analysis for the optimizer.
*/
#pragma once
#include <vector>
#include <memory>
#include <libdevcore/Common.h>
#include <libdevcore/Assertions.h>
#include <libevmasm/ExpressionClasses.h>
namespace dev
{
namespace eth
{
class KnownState;
/**
* Identifier for a block, coincides with the tag number of an AssemblyItem but adds a special
* ID for the inital block.
*/
class BlockId
{
public:
BlockId() { *this = invalid(); }
explicit BlockId(unsigned _id): m_id(_id) {}
explicit BlockId(u256 const& _id);
static BlockId initial() { return BlockId(-2); }
static BlockId invalid() { return BlockId(-1); }
bool operator==(BlockId const& _other) const { return m_id == _other.m_id; }
bool operator!=(BlockId const& _other) const { return m_id != _other.m_id; }
bool operator<(BlockId const& _other) const { return m_id < _other.m_id; }
explicit operator bool() const { return *this != invalid(); }
private:
unsigned m_id;
};
/**
* Control flow block inside which instruction counter is always incremented by one
* (except for possibly the last instruction).
*/
struct BasicBlock
{
/// Start index into assembly item list.
unsigned begin = 0;
/// End index (excluded) inte assembly item list.
unsigned end = 0;
/// Tags pushed inside this block, with multiplicity.
std::vector<BlockId> pushedTags;
/// ID of the block that always follows this one (either non-branching part of JUMPI or flow
/// into new block), or BlockId::invalid() otherwise
BlockId next = BlockId::invalid();
/// ID of the block that has to precede this one (because control flows into it).
BlockId prev = BlockId::invalid();
enum class EndType { JUMP, JUMPI, STOP, HANDOVER };
EndType endType = EndType::HANDOVER;
/// Knowledge about the state when this block is entered. Intersection of all possible ways
/// to enter this block.
std::shared_ptr<KnownState> startState;
/// Knowledge about the state at the end of this block.
std::shared_ptr<KnownState> endState;
};
class ControlFlowGraph
{
public:
/// Initializes the control flow graph.
/// @a _items has to persist across the usage of this class.
ControlFlowGraph(AssemblyItems const& _items): m_items(_items) {}
/// @returns the collection of optimised items, should be called only once.
AssemblyItems optimisedItems();
private:
void findLargestTag();
void splitBlocks();
void resolveNextLinks();
void removeUnusedBlocks();
void gatherKnowledge();
void setPrevLinks();
AssemblyItems rebuildCode();
/// @returns the corresponding BlockId if _id is a pushed jump tag,
/// and an invalid BlockId otherwise.
BlockId expressionClassToBlockId(ExpressionClasses::Id _id, ExpressionClasses& _exprClasses);
BlockId generateNewId();
unsigned m_lastUsedId = 0;
AssemblyItems const& m_items;
std::map<BlockId, BasicBlock> m_blocks;
};
}
}
|
