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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
|
/*
This file is part of solidity.
solidity 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.
solidity 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 solidity. If not, see <http://www.gnu.org/licenses/>.
*/
/**
* Optimiser component that removes assignments to variables that are not used
* until they go out of scope or are re-assigned.
*/
#pragma once
#include <libyul/AsmDataForward.h>
#include <libyul/optimiser/ASTWalker.h>
#include <map>
namespace yul
{
/**
* Optimiser component that removes assignments to variables that are not used
* until they go out of scope or are re-assigned. This component
* respects the control-flow and takes it into account for removal.
*
* Example:
*
* {
* let a
* a := 1
* a := 2
* b := 2
* if calldataload(0)
* {
* b := mload(a)
* }
* a := b
* }
*
* In the example, "a := 1" can be removed because the value from this assignment
* is not used in any control-flow branch (it is replaced right away).
* The assignment "a := 2" is also overwritten by "a := b" at the end,
* but there is a control-flow path (through the condition body) which uses
* the value from "a := 2" and thus, this assignment cannot be removed.
*
* Detailed rules:
*
* The AST is traversed twice: in an information gathering step and in the
* actual removal step. During information gathering, we maintain a
* mapping from assignment statements to the three states
* "unused", "undecided" and "used".
* When an assignment is visited, it is added to the mapping in the "undecided" state
* (see remark about for loops below) and every other assignment to the same variable
* that is still in the "undecided" state is changed to "unused".
* When a variable is referenced, the state of any assignment to that variable still
* in the "undecided" state is changed to "used".
* At points where control flow splits, a copy
* of the mapping is handed over to each branch. At points where control flow
* joins, the two mappings coming from the two branches are combined in the following way:
* Statements that are only in one mapping or have the same state are used unchanged.
* Conflicting values are resolved in the following way:
* "unused", "undecided" -> "undecided"
* "unused", "used" -> "used"
* "undecided, "used" -> "used".
*
* For for-loops, the condition, body and post-part are visited twice, taking
* the joining control-flow at the condition into account.
* In other words, we create three control flow paths: Zero runs of the loop,
* one run and two runs and then combine them at the end.
* Running at most twice is enough because there are only three different states.
*
* For switch statements that have a "default"-case, there is no control-flow
* part that skips the switch.
*
* When a variable goes out of scope, all statements still in the "undecided"
* state are changed to "unused", unless the variable is the return
* parameter of a function - there, the state changes to "used".
*
* In the second traversal, all assignments that are in the "unused" state are removed.
*
*
* This step is usually run right after the SSA transform to complete
* the generation of the pseudo-SSA.
*
* Prerequisite: Disambiguator.
*/
class RedundantAssignEliminator: public ASTWalker
{
public:
RedundantAssignEliminator(RedundantAssignEliminator const&) = default;
RedundantAssignEliminator& operator=(RedundantAssignEliminator const&) = default;
RedundantAssignEliminator(RedundantAssignEliminator&&) = default;
RedundantAssignEliminator& operator=(RedundantAssignEliminator&&) = default;
void operator()(Identifier const& _identifier) override;
void operator()(VariableDeclaration const& _variableDeclaration) override;
void operator()(Assignment const& _assignment) override;
void operator()(If const& _if) override;
void operator()(Switch const& _switch) override;
void operator()(FunctionDefinition const&) override;
void operator()(ForLoop const&) override;
void operator()(Block const& _block) override;
static void run(Block& _ast);
private:
RedundantAssignEliminator() = default;
class State
{
public:
enum Value { Unused, Undecided, Used };
State(Value _value = Undecided): m_value(_value) {}
inline bool operator==(State _other) const { return m_value == _other.m_value; }
inline bool operator!=(State _other) const { return !operator==(_other); }
static inline void join(State& _a, State const& _b)
{
// Using "max" works here because of the order of the values in the enum.
_a.m_value = Value(std::max(int(_a.m_value), int(_b.m_value)));
}
private:
Value m_value = Undecided;
};
/**
* Takes care about storing the list of declared variables and
* sets them to "unused" when it is destroyed.
*/
class BlockScope
{
public:
explicit BlockScope(RedundantAssignEliminator& _rae): m_rae(_rae)
{
swap(m_rae.m_declaredVariables, m_outerDeclaredVariables);
}
~BlockScope()
{
// This should actually store all declared variables
// into a different mapping
for (auto const& var: m_rae.m_declaredVariables)
m_rae.changeUndecidedTo(var, State::Unused);
for (auto const& var: m_rae.m_declaredVariables)
m_rae.finalize(var);
swap(m_rae.m_declaredVariables, m_outerDeclaredVariables);
}
private:
RedundantAssignEliminator& m_rae;
std::set<YulString> m_outerDeclaredVariables;
};
/// Joins the assignment mapping with @a _other according to the rules laid out
/// above.
/// Will destroy @a _other.
void join(RedundantAssignEliminator& _other);
void changeUndecidedTo(YulString _variable, State _newState);
void finalize(YulString _variable);
std::set<YulString> m_declaredVariables;
// TODO check that this does not cause nondeterminism!
// This could also be a pseudo-map from state to assignment.
std::map<YulString, std::map<Assignment const*, State>> m_assignments;
std::set<Assignment const*> m_assignmentsToRemove;
};
class AssignmentRemover: public ASTModifier
{
public:
explicit AssignmentRemover(std::set<Assignment const*> const& _toRemove):
m_toRemove(_toRemove)
{}
void operator()(Block& _block) override;
private:
std::set<Assignment const*> const& m_toRemove;
};
}
|
