1 /*(
2 This file is part of solidity.
3
4 solidity is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation, either version 3 of the License, or
7 (at your option) any later version.
8
9 solidity is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with solidity. If not, see <http://www.gnu.org/licenses/>.
16 */
17 /**
18 * Base class to perform data flow analysis during AST walks.
19 * Tracks assignments and is used as base class for both Rematerialiser and
20 * Common Subexpression Eliminator.
21 */
22
23 #include <libyul/optimiser/DataFlowAnalyzer.h>
24
25 #include <libyul/optimiser/NameCollector.h>
26 #include <libyul/optimiser/Semantics.h>
27 #include <libyul/AST.h>
28 #include <libyul/Dialect.h>
29 #include <libyul/Exceptions.h>
30 #include <libyul/Utilities.h>
31
32 #include <libsolutil/CommonData.h>
33 #include <libsolutil/cxx20.h>
34
35 #include <variant>
36
37 #include <range/v3/view/reverse.hpp>
38
39 using namespace std;
40 using namespace solidity;
41 using namespace solidity::util;
42 using namespace solidity::yul;
43
DataFlowAnalyzer(Dialect const & _dialect,map<YulString,SideEffects> _functionSideEffects)44 DataFlowAnalyzer::DataFlowAnalyzer(
45 Dialect const& _dialect,
46 map<YulString, SideEffects> _functionSideEffects
47 ):
48 m_dialect(_dialect),
49 m_functionSideEffects(std::move(_functionSideEffects)),
50 m_knowledgeBase(_dialect, m_value)
51 {
52 if (auto const* builtin = _dialect.memoryStoreFunction(YulString{}))
53 m_storeFunctionName[static_cast<unsigned>(StoreLoadLocation::Memory)] = builtin->name;
54 if (auto const* builtin = _dialect.memoryLoadFunction(YulString{}))
55 m_loadFunctionName[static_cast<unsigned>(StoreLoadLocation::Memory)] = builtin->name;
56 if (auto const* builtin = _dialect.storageStoreFunction(YulString{}))
57 m_storeFunctionName[static_cast<unsigned>(StoreLoadLocation::Storage)] = builtin->name;
58 if (auto const* builtin = _dialect.storageLoadFunction(YulString{}))
59 m_loadFunctionName[static_cast<unsigned>(StoreLoadLocation::Storage)] = builtin->name;
60 }
61
operator ()(ExpressionStatement & _statement)62 void DataFlowAnalyzer::operator()(ExpressionStatement& _statement)
63 {
64 if (auto vars = isSimpleStore(StoreLoadLocation::Storage, _statement))
65 {
66 ASTModifier::operator()(_statement);
67 cxx20::erase_if(m_storage, mapTuple([&](auto&& key, auto&& value) {
68 return
69 !m_knowledgeBase.knownToBeDifferent(vars->first, key) &&
70 !m_knowledgeBase.knownToBeEqual(vars->second, value);
71 }));
72 m_storage[vars->first] = vars->second;
73 }
74 else if (auto vars = isSimpleStore(StoreLoadLocation::Memory, _statement))
75 {
76 ASTModifier::operator()(_statement);
77 cxx20::erase_if(m_memory, mapTuple([&](auto&& key, auto&& /* value */) {
78 return !m_knowledgeBase.knownToBeDifferentByAtLeast32(vars->first, key);
79 }));
80 m_memory[vars->first] = vars->second;
81 }
82 else
83 {
84 clearKnowledgeIfInvalidated(_statement.expression);
85 ASTModifier::operator()(_statement);
86 }
87 }
88
operator ()(Assignment & _assignment)89 void DataFlowAnalyzer::operator()(Assignment& _assignment)
90 {
91 set<YulString> names;
92 for (auto const& var: _assignment.variableNames)
93 names.emplace(var.name);
94 assertThrow(_assignment.value, OptimizerException, "");
95 clearKnowledgeIfInvalidated(*_assignment.value);
96 visit(*_assignment.value);
97 handleAssignment(names, _assignment.value.get(), false);
98 }
99
operator ()(VariableDeclaration & _varDecl)100 void DataFlowAnalyzer::operator()(VariableDeclaration& _varDecl)
101 {
102 set<YulString> names;
103 for (auto const& var: _varDecl.variables)
104 names.emplace(var.name);
105 m_variableScopes.back().variables += names;
106
107 if (_varDecl.value)
108 {
109 clearKnowledgeIfInvalidated(*_varDecl.value);
110 visit(*_varDecl.value);
111 }
112
113 handleAssignment(names, _varDecl.value.get(), true);
114 }
115
operator ()(If & _if)116 void DataFlowAnalyzer::operator()(If& _if)
117 {
118 clearKnowledgeIfInvalidated(*_if.condition);
119 unordered_map<YulString, YulString> storage = m_storage;
120 unordered_map<YulString, YulString> memory = m_memory;
121
122 ASTModifier::operator()(_if);
123
124 joinKnowledge(storage, memory);
125
126 clearValues(assignedVariableNames(_if.body));
127 }
128
operator ()(Switch & _switch)129 void DataFlowAnalyzer::operator()(Switch& _switch)
130 {
131 clearKnowledgeIfInvalidated(*_switch.expression);
132 visit(*_switch.expression);
133 set<YulString> assignedVariables;
134 for (auto& _case: _switch.cases)
135 {
136 unordered_map<YulString, YulString> storage = m_storage;
137 unordered_map<YulString, YulString> memory = m_memory;
138 (*this)(_case.body);
139 joinKnowledge(storage, memory);
140
141 set<YulString> variables = assignedVariableNames(_case.body);
142 assignedVariables += variables;
143 // This is a little too destructive, we could retain the old values.
144 clearValues(variables);
145 clearKnowledgeIfInvalidated(_case.body);
146 }
147 for (auto& _case: _switch.cases)
148 clearKnowledgeIfInvalidated(_case.body);
149 clearValues(assignedVariables);
150 }
151
operator ()(FunctionDefinition & _fun)152 void DataFlowAnalyzer::operator()(FunctionDefinition& _fun)
153 {
154 // Save all information. We might rather reinstantiate this class,
155 // but this could be difficult if it is subclassed.
156 ScopedSaveAndRestore valueResetter(m_value, {});
157 ScopedSaveAndRestore loopDepthResetter(m_loopDepth, 0u);
158 ScopedSaveAndRestore referencesResetter(m_references, {});
159 ScopedSaveAndRestore storageResetter(m_storage, {});
160 ScopedSaveAndRestore memoryResetter(m_memory, {});
161 pushScope(true);
162
163 for (auto const& parameter: _fun.parameters)
164 m_variableScopes.back().variables.emplace(parameter.name);
165 for (auto const& var: _fun.returnVariables)
166 {
167 m_variableScopes.back().variables.emplace(var.name);
168 handleAssignment({var.name}, nullptr, true);
169 }
170 ASTModifier::operator()(_fun);
171
172 // Note that the contents of return variables, storage and memory at this point
173 // might be incorrect due to the fact that the DataFlowAnalyzer ignores the ``leave``
174 // statement.
175
176 popScope();
177 }
178
operator ()(ForLoop & _for)179 void DataFlowAnalyzer::operator()(ForLoop& _for)
180 {
181 // If the pre block was not empty,
182 // we would have to deal with more complicated scoping rules.
183 assertThrow(_for.pre.statements.empty(), OptimizerException, "");
184
185 ++m_loopDepth;
186
187 AssignmentsSinceContinue assignmentsSinceCont;
188 assignmentsSinceCont(_for.body);
189
190 set<YulString> assignedVariables =
191 assignedVariableNames(_for.body) + assignedVariableNames(_for.post);
192 clearValues(assignedVariables);
193
194 // break/continue are tricky for storage and thus we almost always clear here.
195 clearKnowledgeIfInvalidated(*_for.condition);
196 clearKnowledgeIfInvalidated(_for.post);
197 clearKnowledgeIfInvalidated(_for.body);
198
199 visit(*_for.condition);
200 (*this)(_for.body);
201 clearValues(assignmentsSinceCont.names());
202 clearKnowledgeIfInvalidated(_for.body);
203 (*this)(_for.post);
204 clearValues(assignedVariables);
205 clearKnowledgeIfInvalidated(*_for.condition);
206 clearKnowledgeIfInvalidated(_for.post);
207 clearKnowledgeIfInvalidated(_for.body);
208
209 --m_loopDepth;
210 }
211
operator ()(Block & _block)212 void DataFlowAnalyzer::operator()(Block& _block)
213 {
214 size_t numScopes = m_variableScopes.size();
215 pushScope(false);
216 ASTModifier::operator()(_block);
217 popScope();
218 assertThrow(numScopes == m_variableScopes.size(), OptimizerException, "");
219 }
220
handleAssignment(set<YulString> const & _variables,Expression * _value,bool _isDeclaration)221 void DataFlowAnalyzer::handleAssignment(set<YulString> const& _variables, Expression* _value, bool _isDeclaration)
222 {
223 if (!_isDeclaration)
224 clearValues(_variables);
225
226 MovableChecker movableChecker{m_dialect, &m_functionSideEffects};
227 if (_value)
228 movableChecker.visit(*_value);
229 else
230 for (auto const& var: _variables)
231 assignValue(var, &m_zero);
232
233 if (_value && _variables.size() == 1)
234 {
235 YulString name = *_variables.begin();
236 // Expression has to be movable and cannot contain a reference
237 // to the variable that will be assigned to.
238 if (movableChecker.movable() && !movableChecker.referencedVariables().count(name))
239 assignValue(name, _value);
240 }
241
242 auto const& referencedVariables = movableChecker.referencedVariables();
243 for (auto const& name: _variables)
244 {
245 m_references[name] = referencedVariables;
246 if (!_isDeclaration)
247 {
248 // assignment to slot denoted by "name"
249 m_storage.erase(name);
250 // assignment to slot contents denoted by "name"
251 cxx20::erase_if(m_storage, mapTuple([&name](auto&& /* key */, auto&& value) { return value == name; }));
252 // assignment to slot denoted by "name"
253 m_memory.erase(name);
254 // assignment to slot contents denoted by "name"
255 cxx20::erase_if(m_memory, mapTuple([&name](auto&& /* key */, auto&& value) { return value == name; }));
256 }
257 }
258
259 if (_value && _variables.size() == 1)
260 {
261 YulString variable = *_variables.begin();
262 if (!movableChecker.referencedVariables().count(variable))
263 {
264 // This might erase additional knowledge about the slot.
265 // On the other hand, if we knew the value in the slot
266 // already, then the sload() / mload() would have been replaced by a variable anyway.
267 if (auto key = isSimpleLoad(StoreLoadLocation::Memory, *_value))
268 m_memory[*key] = variable;
269 else if (auto key = isSimpleLoad(StoreLoadLocation::Storage, *_value))
270 m_storage[*key] = variable;
271 }
272 }
273 }
274
pushScope(bool _functionScope)275 void DataFlowAnalyzer::pushScope(bool _functionScope)
276 {
277 m_variableScopes.emplace_back(_functionScope);
278 }
279
popScope()280 void DataFlowAnalyzer::popScope()
281 {
282 for (auto const& name: m_variableScopes.back().variables)
283 {
284 m_value.erase(name);
285 m_references.erase(name);
286 }
287 m_variableScopes.pop_back();
288 }
289
clearValues(set<YulString> _variables)290 void DataFlowAnalyzer::clearValues(set<YulString> _variables)
291 {
292 // All variables that reference variables to be cleared also have to be
293 // cleared, but not recursively, since only the value of the original
294 // variables changes. Example:
295 // let a := 1
296 // let b := a
297 // let c := b
298 // let a := 2
299 // add(b, c)
300 // In the last line, we can replace c by b, but not b by a.
301 //
302 // This cannot be easily tested since the substitutions will be done
303 // one by one on the fly, and the last line will just be add(1, 1)
304
305 // First clear storage knowledge, because we do not have to clear
306 // storage knowledge of variables whose expression has changed,
307 // since the value is still unchanged.
308 auto eraseCondition = mapTuple([&_variables](auto&& key, auto&& value) {
309 return _variables.count(key) || _variables.count(value);
310 });
311 cxx20::erase_if(m_storage, eraseCondition);
312 cxx20::erase_if(m_memory, eraseCondition);
313
314 // Also clear variables that reference variables to be cleared.
315 for (auto const& variableToClear: _variables)
316 for (auto const& [ref, names]: m_references)
317 if (names.count(variableToClear))
318 _variables.emplace(ref);
319
320 // Clear the value and update the reference relation.
321 for (auto const& name: _variables)
322 {
323 m_value.erase(name);
324 m_references.erase(name);
325 }
326 }
327
assignValue(YulString _variable,Expression const * _value)328 void DataFlowAnalyzer::assignValue(YulString _variable, Expression const* _value)
329 {
330 m_value[_variable] = {_value, m_loopDepth};
331 }
332
clearKnowledgeIfInvalidated(Block const & _block)333 void DataFlowAnalyzer::clearKnowledgeIfInvalidated(Block const& _block)
334 {
335 SideEffectsCollector sideEffects(m_dialect, _block, &m_functionSideEffects);
336 if (sideEffects.invalidatesStorage())
337 m_storage.clear();
338 if (sideEffects.invalidatesMemory())
339 m_memory.clear();
340 }
341
clearKnowledgeIfInvalidated(Expression const & _expr)342 void DataFlowAnalyzer::clearKnowledgeIfInvalidated(Expression const& _expr)
343 {
344 SideEffectsCollector sideEffects(m_dialect, _expr, &m_functionSideEffects);
345 if (sideEffects.invalidatesStorage())
346 m_storage.clear();
347 if (sideEffects.invalidatesMemory())
348 m_memory.clear();
349 }
350
joinKnowledge(unordered_map<YulString,YulString> const & _olderStorage,unordered_map<YulString,YulString> const & _olderMemory)351 void DataFlowAnalyzer::joinKnowledge(
352 unordered_map<YulString, YulString> const& _olderStorage,
353 unordered_map<YulString, YulString> const& _olderMemory
354 )
355 {
356 joinKnowledgeHelper(m_storage, _olderStorage);
357 joinKnowledgeHelper(m_memory, _olderMemory);
358 }
359
joinKnowledgeHelper(std::unordered_map<YulString,YulString> & _this,std::unordered_map<YulString,YulString> const & _older)360 void DataFlowAnalyzer::joinKnowledgeHelper(
361 std::unordered_map<YulString, YulString>& _this,
362 std::unordered_map<YulString, YulString> const& _older
363 )
364 {
365 // We clear if the key does not exist in the older map or if the value is different.
366 // This also works for memory because _older is an "older version"
367 // of m_memory and thus any overlapping write would have cleared the keys
368 // that are not known to be different inside m_memory already.
369 cxx20::erase_if(_this, mapTuple([&_older](auto&& key, auto&& currentValue){
370 YulString const* oldValue = valueOrNullptr(_older, key);
371 return !oldValue || *oldValue != currentValue;
372 }));
373 }
374
inScope(YulString _variableName) const375 bool DataFlowAnalyzer::inScope(YulString _variableName) const
376 {
377 for (auto const& scope: m_variableScopes | ranges::views::reverse)
378 {
379 if (scope.variables.count(_variableName))
380 return true;
381 if (scope.isFunction)
382 return false;
383 }
384 return false;
385 }
386
valueOfIdentifier(YulString const & _name)387 optional<u256> DataFlowAnalyzer::valueOfIdentifier(YulString const& _name)
388 {
389 if (m_value.count(_name))
390 if (Literal const* literal = get_if<Literal>(m_value.at(_name).value))
391 return valueOfLiteral(*literal);
392 return nullopt;
393 }
394
isSimpleStore(StoreLoadLocation _location,ExpressionStatement const & _statement) const395 std::optional<pair<YulString, YulString>> DataFlowAnalyzer::isSimpleStore(
396 StoreLoadLocation _location,
397 ExpressionStatement const& _statement
398 ) const
399 {
400 if (FunctionCall const* funCall = get_if<FunctionCall>(&_statement.expression))
401 if (funCall->functionName.name == m_storeFunctionName[static_cast<unsigned>(_location)])
402 if (Identifier const* key = std::get_if<Identifier>(&funCall->arguments.front()))
403 if (Identifier const* value = std::get_if<Identifier>(&funCall->arguments.back()))
404 return make_pair(key->name, value->name);
405 return {};
406 }
407
isSimpleLoad(StoreLoadLocation _location,Expression const & _expression) const408 std::optional<YulString> DataFlowAnalyzer::isSimpleLoad(
409 StoreLoadLocation _location,
410 Expression const& _expression
411 ) const
412 {
413 if (FunctionCall const* funCall = get_if<FunctionCall>(&_expression))
414 if (funCall->functionName.name == m_loadFunctionName[static_cast<unsigned>(_location)])
415 if (Identifier const* key = std::get_if<Identifier>(&funCall->arguments.front()))
416 return key->name;
417 return {};
418 }
419