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 // SPDX-License-Identifier: GPL-3.0
18 /**
19 * Code generator for translating Yul / inline assembly to EVM.
20 */
21
22 #include <libyul/backends/evm/EVMCodeTransform.h>
23
24 #include <libyul/optimiser/NameCollector.h>
25 #include <libyul/AsmAnalysisInfo.h>
26 #include <libyul/Utilities.h>
27
28 #include <libsolutil/Visitor.h>
29
30 #include <liblangutil/Exceptions.h>
31
32 #include <range/v3/view/reverse.hpp>
33
34 #include <range/v3/algorithm/max.hpp>
35 #include <range/v3/algorithm/none_of.hpp>
36 #include <range/v3/view/enumerate.hpp>
37 #include <range/v3/view/transform.hpp>
38
39 #include <utility>
40 #include <variant>
41
42 using namespace std;
43 using namespace solidity;
44 using namespace solidity::yul;
45 using namespace solidity::util;
46
CodeTransform(AbstractAssembly & _assembly,AsmAnalysisInfo & _analysisInfo,Block const & _block,bool _allowStackOpt,EVMDialect const & _dialect,BuiltinContext & _builtinContext,ExternalIdentifierAccess::CodeGenerator _identifierAccessCodeGen,UseNamedLabels _useNamedLabelsForFunctions,shared_ptr<Context> _context,vector<TypedName> _delayedReturnVariables,optional<AbstractAssembly::LabelID> _functionExitLabel)47 CodeTransform::CodeTransform(
48 AbstractAssembly& _assembly,
49 AsmAnalysisInfo& _analysisInfo,
50 Block const& _block,
51 bool _allowStackOpt,
52 EVMDialect const& _dialect,
53 BuiltinContext& _builtinContext,
54 ExternalIdentifierAccess::CodeGenerator _identifierAccessCodeGen,
55 UseNamedLabels _useNamedLabelsForFunctions,
56 shared_ptr<Context> _context,
57 vector<TypedName> _delayedReturnVariables,
58 optional<AbstractAssembly::LabelID> _functionExitLabel
59 ):
60 m_assembly(_assembly),
61 m_info(_analysisInfo),
62 m_dialect(_dialect),
63 m_builtinContext(_builtinContext),
64 m_allowStackOpt(_allowStackOpt),
65 m_useNamedLabelsForFunctions(_useNamedLabelsForFunctions),
66 m_identifierAccessCodeGen(move(_identifierAccessCodeGen)),
67 m_context(move(_context)),
68 m_delayedReturnVariables(move(_delayedReturnVariables)),
69 m_functionExitLabel(_functionExitLabel)
70 {
71 if (!m_context)
72 {
73 // initialize
74 m_context = make_shared<Context>();
75 if (m_allowStackOpt)
76 m_context->variableReferences = VariableReferenceCounter::run(m_info, _block);
77 }
78 }
79
decreaseReference(YulString,Scope::Variable const & _var)80 void CodeTransform::decreaseReference(YulString, Scope::Variable const& _var)
81 {
82 if (!m_allowStackOpt)
83 return;
84
85 unsigned& ref = m_context->variableReferences.at(&_var);
86 yulAssert(ref >= 1, "");
87 --ref;
88 if (ref == 0)
89 m_variablesScheduledForDeletion.insert(&_var);
90 }
91
unreferenced(Scope::Variable const & _var) const92 bool CodeTransform::unreferenced(Scope::Variable const& _var) const
93 {
94 return !m_context->variableReferences.count(&_var) || m_context->variableReferences[&_var] == 0;
95 }
96
freeUnusedVariables(bool _popUnusedSlotsAtStackTop)97 void CodeTransform::freeUnusedVariables(bool _popUnusedSlotsAtStackTop)
98 {
99 if (!m_allowStackOpt)
100 return;
101
102 for (auto const& identifier: m_scope->identifiers)
103 if (Scope::Variable const* var = get_if<Scope::Variable>(&identifier.second))
104 if (m_variablesScheduledForDeletion.count(var))
105 deleteVariable(*var);
106 // Directly in a function body block, we can also delete the function arguments,
107 // which live in the virtual function scope.
108 // However, doing so after the return variables are already allocated, seems to have an adverse
109 // effect, so we only do it before that.
110 if (!returnVariablesAndFunctionExitAreSetup() && !m_scope->functionScope && m_scope->superScope && m_scope->superScope->functionScope)
111 for (auto const& identifier: m_scope->superScope->identifiers)
112 if (Scope::Variable const* var = get_if<Scope::Variable>(&identifier.second))
113 if (m_variablesScheduledForDeletion.count(var))
114 deleteVariable(*var);
115
116 if (_popUnusedSlotsAtStackTop)
117 while (m_unusedStackSlots.count(m_assembly.stackHeight() - 1))
118 {
119 yulAssert(m_unusedStackSlots.erase(m_assembly.stackHeight() - 1), "");
120 m_assembly.appendInstruction(evmasm::Instruction::POP);
121 }
122 }
123
deleteVariable(Scope::Variable const & _var)124 void CodeTransform::deleteVariable(Scope::Variable const& _var)
125 {
126 yulAssert(m_allowStackOpt, "");
127 yulAssert(m_context->variableStackHeights.count(&_var) > 0, "");
128 m_unusedStackSlots.insert(static_cast<int>(m_context->variableStackHeights[&_var]));
129 m_context->variableStackHeights.erase(&_var);
130 m_context->variableReferences.erase(&_var);
131 m_variablesScheduledForDeletion.erase(&_var);
132 }
133
operator ()(VariableDeclaration const & _varDecl)134 void CodeTransform::operator()(VariableDeclaration const& _varDecl)
135 {
136 yulAssert(m_scope, "");
137
138 size_t const numVariables = _varDecl.variables.size();
139 auto heightAtStart = static_cast<size_t>(m_assembly.stackHeight());
140 if (_varDecl.value)
141 {
142 std::visit(*this, *_varDecl.value);
143 expectDeposit(static_cast<int>(numVariables), static_cast<int>(heightAtStart));
144 freeUnusedVariables(false);
145 }
146 else
147 {
148 m_assembly.setSourceLocation(originLocationOf(_varDecl));
149 size_t variablesLeft = numVariables;
150 while (variablesLeft--)
151 m_assembly.appendConstant(u256(0));
152 }
153
154 m_assembly.setSourceLocation(originLocationOf(_varDecl));
155 bool atTopOfStack = true;
156 for (size_t varIndex = 0; varIndex < numVariables; ++varIndex)
157 {
158 size_t varIndexReverse = numVariables - 1 - varIndex;
159 YulString varName = _varDecl.variables[varIndexReverse].name;
160 auto& var = std::get<Scope::Variable>(m_scope->identifiers.at(varName));
161 m_context->variableStackHeights[&var] = heightAtStart + varIndexReverse;
162 if (!m_allowStackOpt)
163 continue;
164
165 if (unreferenced(var))
166 {
167 if (atTopOfStack)
168 {
169 m_context->variableStackHeights.erase(&var);
170 m_assembly.appendInstruction(evmasm::Instruction::POP);
171 }
172 else
173 m_variablesScheduledForDeletion.insert(&var);
174 }
175 else
176 {
177 bool foundUnusedSlot = false;
178 for (auto it = m_unusedStackSlots.begin(); it != m_unusedStackSlots.end(); ++it)
179 {
180 if (m_assembly.stackHeight() - *it > 17)
181 continue;
182 foundUnusedSlot = true;
183 auto slot = static_cast<size_t>(*it);
184 m_unusedStackSlots.erase(it);
185 m_context->variableStackHeights[&var] = slot;
186 if (size_t heightDiff = variableHeightDiff(var, varName, true))
187 m_assembly.appendInstruction(evmasm::swapInstruction(static_cast<unsigned>(heightDiff - 1)));
188 m_assembly.appendInstruction(evmasm::Instruction::POP);
189 break;
190 }
191 if (!foundUnusedSlot)
192 atTopOfStack = false;
193 }
194 }
195 }
196
stackError(StackTooDeepError _error,int _targetStackHeight)197 void CodeTransform::stackError(StackTooDeepError _error, int _targetStackHeight)
198 {
199 m_assembly.appendInstruction(evmasm::Instruction::INVALID);
200 // Correct the stack.
201 while (m_assembly.stackHeight() > _targetStackHeight)
202 m_assembly.appendInstruction(evmasm::Instruction::POP);
203 while (m_assembly.stackHeight() < _targetStackHeight)
204 m_assembly.appendConstant(u256(0));
205 // Store error.
206 m_stackErrors.emplace_back(std::move(_error));
207 m_assembly.markAsInvalid();
208 }
209
operator ()(Assignment const & _assignment)210 void CodeTransform::operator()(Assignment const& _assignment)
211 {
212 int height = m_assembly.stackHeight();
213 std::visit(*this, *_assignment.value);
214 expectDeposit(static_cast<int>(_assignment.variableNames.size()), height);
215
216 m_assembly.setSourceLocation(originLocationOf(_assignment));
217 generateMultiAssignment(_assignment.variableNames);
218 }
219
operator ()(ExpressionStatement const & _statement)220 void CodeTransform::operator()(ExpressionStatement const& _statement)
221 {
222 m_assembly.setSourceLocation(originLocationOf(_statement));
223 std::visit(*this, _statement.expression);
224 }
225
operator ()(FunctionCall const & _call)226 void CodeTransform::operator()(FunctionCall const& _call)
227 {
228 yulAssert(m_scope, "");
229
230 m_assembly.setSourceLocation(originLocationOf(_call));
231 if (BuiltinFunctionForEVM const* builtin = m_dialect.builtin(_call.functionName.name))
232 {
233 for (auto&& [i, arg]: _call.arguments | ranges::views::enumerate | ranges::views::reverse)
234 if (!builtin->literalArgument(i))
235 visitExpression(arg);
236 m_assembly.setSourceLocation(originLocationOf(_call));
237 builtin->generateCode(_call, m_assembly, m_builtinContext);
238 }
239 else
240 {
241 AbstractAssembly::LabelID returnLabel = m_assembly.newLabelId();
242 m_assembly.appendLabelReference(returnLabel);
243
244 Scope::Function* function = nullptr;
245 yulAssert(m_scope->lookup(_call.functionName.name, GenericVisitor{
246 [](Scope::Variable&) { yulAssert(false, "Expected function name."); },
247 [&](Scope::Function& _function) { function = &_function; }
248 }), "Function name not found.");
249 yulAssert(function, "");
250 yulAssert(function->arguments.size() == _call.arguments.size(), "");
251 for (auto const& arg: _call.arguments | ranges::views::reverse)
252 visitExpression(arg);
253 m_assembly.setSourceLocation(originLocationOf(_call));
254 m_assembly.appendJumpTo(
255 functionEntryID(*function),
256 static_cast<int>(function->returns.size() - function->arguments.size()) - 1,
257 AbstractAssembly::JumpType::IntoFunction
258 );
259 m_assembly.appendLabel(returnLabel);
260 }
261 }
262
operator ()(Identifier const & _identifier)263 void CodeTransform::operator()(Identifier const& _identifier)
264 {
265 m_assembly.setSourceLocation(originLocationOf(_identifier));
266 // First search internals, then externals.
267 yulAssert(m_scope, "");
268 if (m_scope->lookup(_identifier.name, GenericVisitor{
269 [&](Scope::Variable& _var)
270 {
271 // TODO: opportunity for optimization: Do not DUP if this is the last reference
272 // to the top most element of the stack
273 if (size_t heightDiff = variableHeightDiff(_var, _identifier.name, false))
274 m_assembly.appendInstruction(evmasm::dupInstruction(static_cast<unsigned>(heightDiff)));
275 else
276 // Store something to balance the stack
277 m_assembly.appendConstant(u256(0));
278 decreaseReference(_identifier.name, _var);
279 },
280 [](Scope::Function&)
281 {
282 yulAssert(false, "Function not removed during desugaring.");
283 }
284 }))
285 {
286 return;
287 }
288 yulAssert(
289 m_identifierAccessCodeGen,
290 "Identifier not found and no external access available."
291 );
292 m_identifierAccessCodeGen(_identifier, IdentifierContext::RValue, m_assembly);
293 }
294
operator ()(Literal const & _literal)295 void CodeTransform::operator()(Literal const& _literal)
296 {
297 m_assembly.setSourceLocation(originLocationOf(_literal));
298 m_assembly.appendConstant(valueOfLiteral(_literal));
299 }
300
operator ()(If const & _if)301 void CodeTransform::operator()(If const& _if)
302 {
303 visitExpression(*_if.condition);
304 m_assembly.setSourceLocation(originLocationOf(_if));
305 m_assembly.appendInstruction(evmasm::Instruction::ISZERO);
306 AbstractAssembly::LabelID end = m_assembly.newLabelId();
307 m_assembly.appendJumpToIf(end);
308 (*this)(_if.body);
309 m_assembly.setSourceLocation(originLocationOf(_if));
310 m_assembly.appendLabel(end);
311 }
312
operator ()(Switch const & _switch)313 void CodeTransform::operator()(Switch const& _switch)
314 {
315 visitExpression(*_switch.expression);
316 int expressionHeight = m_assembly.stackHeight();
317 map<Case const*, AbstractAssembly::LabelID> caseBodies;
318 AbstractAssembly::LabelID end = m_assembly.newLabelId();
319 for (Case const& c: _switch.cases)
320 {
321 if (c.value)
322 {
323 (*this)(*c.value);
324 m_assembly.setSourceLocation(originLocationOf(c));
325 AbstractAssembly::LabelID bodyLabel = m_assembly.newLabelId();
326 caseBodies[&c] = bodyLabel;
327 yulAssert(m_assembly.stackHeight() == expressionHeight + 1, "");
328 m_assembly.appendInstruction(evmasm::dupInstruction(2));
329 m_assembly.appendInstruction(evmasm::Instruction::EQ);
330 m_assembly.appendJumpToIf(bodyLabel);
331 }
332 else
333 // default case
334 (*this)(c.body);
335 }
336 m_assembly.setSourceLocation(originLocationOf(_switch));
337 m_assembly.appendJumpTo(end);
338
339 size_t numCases = caseBodies.size();
340 for (auto const& c: caseBodies)
341 {
342 m_assembly.setSourceLocation(originLocationOf(*c.first));
343 m_assembly.appendLabel(c.second);
344 (*this)(c.first->body);
345 // Avoid useless "jump to next" for the last case.
346 if (--numCases > 0)
347 {
348 m_assembly.setSourceLocation(originLocationOf(*c.first));
349 m_assembly.appendJumpTo(end);
350 }
351 }
352
353 m_assembly.setSourceLocation(originLocationOf(_switch));
354 m_assembly.appendLabel(end);
355 m_assembly.appendInstruction(evmasm::Instruction::POP);
356 }
357
operator ()(FunctionDefinition const & _function)358 void CodeTransform::operator()(FunctionDefinition const& _function)
359 {
360 yulAssert(m_scope, "");
361 yulAssert(m_scope->identifiers.count(_function.name), "");
362 Scope::Function& function = std::get<Scope::Function>(m_scope->identifiers.at(_function.name));
363
364 size_t height = 1;
365 yulAssert(m_info.scopes.at(&_function.body), "");
366 Scope* virtualFunctionScope = m_info.scopes.at(m_info.virtualBlocks.at(&_function).get()).get();
367 yulAssert(virtualFunctionScope, "");
368 for (auto const& v: _function.parameters | ranges::views::reverse)
369 {
370 auto& var = std::get<Scope::Variable>(virtualFunctionScope->identifiers.at(v.name));
371 m_context->variableStackHeights[&var] = height++;
372 }
373
374 m_assembly.setSourceLocation(originLocationOf(_function));
375 int const stackHeightBefore = m_assembly.stackHeight();
376
377 m_assembly.appendLabel(functionEntryID(function));
378
379 m_assembly.setStackHeight(static_cast<int>(height));
380
381 CodeTransform subTransform(
382 m_assembly,
383 m_info,
384 _function.body,
385 m_allowStackOpt,
386 m_dialect,
387 m_builtinContext,
388 m_identifierAccessCodeGen,
389 m_useNamedLabelsForFunctions,
390 m_context,
391 _function.returnVariables,
392 m_assembly.newLabelId()
393 );
394 subTransform.m_scope = virtualFunctionScope;
395
396 if (m_allowStackOpt)
397 // Immediately delete entirely unused parameters.
398 for (auto const& v: _function.parameters | ranges::views::reverse)
399 {
400 auto& var = std::get<Scope::Variable>(virtualFunctionScope->identifiers.at(v.name));
401 if (util::valueOrDefault(m_context->variableReferences, &var, 0u) == 0)
402 subTransform.deleteVariable(var);
403 }
404
405 if (!m_allowStackOpt)
406 subTransform.setupReturnVariablesAndFunctionExit();
407
408 subTransform.m_assignedNamedLabels = move(m_assignedNamedLabels);
409
410 subTransform(_function.body);
411
412 m_assignedNamedLabels = move(subTransform.m_assignedNamedLabels);
413
414 m_assembly.setSourceLocation(originLocationOf(_function));
415 if (!subTransform.m_stackErrors.empty())
416 {
417 m_assembly.markAsInvalid();
418 for (StackTooDeepError& stackError: subTransform.m_stackErrors)
419 {
420 if (stackError.functionName.empty())
421 stackError.functionName = _function.name;
422 m_stackErrors.emplace_back(std::move(stackError));
423 }
424 }
425
426 if (!subTransform.returnVariablesAndFunctionExitAreSetup())
427 subTransform.setupReturnVariablesAndFunctionExit();
428 appendPopUntil(*subTransform.m_functionExitStackHeight);
429
430 yulAssert(
431 subTransform.m_functionExitStackHeight &&
432 *subTransform.m_functionExitStackHeight == m_assembly.stackHeight(),
433 ""
434 );
435
436 m_assembly.appendLabel(*subTransform.m_functionExitLabel);
437
438 {
439 // The stack layout here is:
440 // <return label>? <arguments...> <return values...>
441 // But we would like it to be:
442 // <return values...> <return label>?
443 // So we have to append some SWAP and POP instructions.
444
445 // This vector holds the desired target positions of all stack slots and is
446 // modified parallel to the actual stack.
447 vector<int> stackLayout(static_cast<size_t>(m_assembly.stackHeight()), -1);
448 stackLayout[0] = static_cast<int>(_function.returnVariables.size()); // Move return label to the top
449 for (auto&& [n, returnVariable]: ranges::views::enumerate(_function.returnVariables))
450 stackLayout.at(m_context->variableStackHeights.at(
451 &std::get<Scope::Variable>(virtualFunctionScope->identifiers.at(returnVariable.name))
452 )) = static_cast<int>(n);
453
454 if (stackLayout.size() > 17)
455 {
456 StackTooDeepError error(
457 _function.name,
458 YulString{},
459 static_cast<int>(stackLayout.size()) - 17,
460 "The function " +
461 _function.name.str() +
462 " has " +
463 to_string(stackLayout.size() - 17) +
464 " parameters or return variables too many to fit the stack size."
465 );
466 stackError(std::move(error), m_assembly.stackHeight() - static_cast<int>(_function.parameters.size()));
467 }
468 else
469 {
470 while (!stackLayout.empty() && stackLayout.back() != static_cast<int>(stackLayout.size() - 1))
471 if (stackLayout.back() < 0)
472 {
473 m_assembly.appendInstruction(evmasm::Instruction::POP);
474 stackLayout.pop_back();
475 }
476 else
477 {
478 m_assembly.appendInstruction(evmasm::swapInstruction(static_cast<unsigned>(stackLayout.size()) - static_cast<unsigned>(stackLayout.back()) - 1u));
479 swap(stackLayout[static_cast<size_t>(stackLayout.back())], stackLayout.back());
480 }
481 for (size_t i = 0; i < stackLayout.size(); ++i)
482 yulAssert(i == static_cast<size_t>(stackLayout[i]), "Error reshuffling stack.");
483 }
484 }
485 m_assembly.appendJump(
486 stackHeightBefore - static_cast<int>(_function.returnVariables.size()),
487 AbstractAssembly::JumpType::OutOfFunction
488 );
489 m_assembly.setStackHeight(stackHeightBefore);
490 }
491
operator ()(ForLoop const & _forLoop)492 void CodeTransform::operator()(ForLoop const& _forLoop)
493 {
494 Scope* originalScope = m_scope;
495 // We start with visiting the block, but not finalizing it.
496 m_scope = m_info.scopes.at(&_forLoop.pre).get();
497 int stackStartHeight = m_assembly.stackHeight();
498
499 visitStatements(_forLoop.pre.statements);
500
501 AbstractAssembly::LabelID loopStart = m_assembly.newLabelId();
502 AbstractAssembly::LabelID postPart = m_assembly.newLabelId();
503 AbstractAssembly::LabelID loopEnd = m_assembly.newLabelId();
504
505 m_assembly.setSourceLocation(originLocationOf(_forLoop));
506 m_assembly.appendLabel(loopStart);
507
508 visitExpression(*_forLoop.condition);
509 m_assembly.setSourceLocation(originLocationOf(_forLoop));
510 m_assembly.appendInstruction(evmasm::Instruction::ISZERO);
511 m_assembly.appendJumpToIf(loopEnd);
512
513 int const stackHeightBody = m_assembly.stackHeight();
514 m_context->forLoopStack.emplace(Context::ForLoopLabels{ {postPart, stackHeightBody}, {loopEnd, stackHeightBody} });
515 (*this)(_forLoop.body);
516
517 m_assembly.setSourceLocation(originLocationOf(_forLoop));
518 m_assembly.appendLabel(postPart);
519
520 (*this)(_forLoop.post);
521
522 m_assembly.setSourceLocation(originLocationOf(_forLoop));
523 m_assembly.appendJumpTo(loopStart);
524 m_assembly.appendLabel(loopEnd);
525
526 finalizeBlock(_forLoop.pre, stackStartHeight);
527 m_context->forLoopStack.pop();
528 m_scope = originalScope;
529 }
530
appendPopUntil(int _targetDepth)531 int CodeTransform::appendPopUntil(int _targetDepth)
532 {
533 int const stackDiffAfter = m_assembly.stackHeight() - _targetDepth;
534 for (int i = 0; i < stackDiffAfter; ++i)
535 m_assembly.appendInstruction(evmasm::Instruction::POP);
536 return stackDiffAfter;
537 }
538
operator ()(Break const & _break)539 void CodeTransform::operator()(Break const& _break)
540 {
541 yulAssert(!m_context->forLoopStack.empty(), "Invalid break-statement. Requires surrounding for-loop in code generation.");
542 m_assembly.setSourceLocation(originLocationOf(_break));
543
544 Context::JumpInfo const& jump = m_context->forLoopStack.top().done;
545 m_assembly.appendJumpTo(jump.label, appendPopUntil(jump.targetStackHeight));
546 }
547
operator ()(Continue const & _continue)548 void CodeTransform::operator()(Continue const& _continue)
549 {
550 yulAssert(!m_context->forLoopStack.empty(), "Invalid continue-statement. Requires surrounding for-loop in code generation.");
551 m_assembly.setSourceLocation(originLocationOf(_continue));
552
553 Context::JumpInfo const& jump = m_context->forLoopStack.top().post;
554 m_assembly.appendJumpTo(jump.label, appendPopUntil(jump.targetStackHeight));
555 }
556
operator ()(Leave const & _leaveStatement)557 void CodeTransform::operator()(Leave const& _leaveStatement)
558 {
559 yulAssert(m_functionExitLabel, "Invalid leave-statement. Requires surrounding function in code generation.");
560 yulAssert(m_functionExitStackHeight, "");
561 m_assembly.setSourceLocation(originLocationOf(_leaveStatement));
562 m_assembly.appendJumpTo(*m_functionExitLabel, appendPopUntil(*m_functionExitStackHeight));
563 }
564
operator ()(Block const & _block)565 void CodeTransform::operator()(Block const& _block)
566 {
567 Scope* originalScope = m_scope;
568 m_scope = m_info.scopes.at(&_block).get();
569
570 for (auto const& statement: _block.statements)
571 if (auto function = get_if<FunctionDefinition>(&statement))
572 createFunctionEntryID(*function);
573
574 int blockStartStackHeight = m_assembly.stackHeight();
575 visitStatements(_block.statements);
576
577 bool isOutermostFunctionBodyBlock = m_scope && m_scope->superScope && m_scope->superScope->functionScope;
578 bool performValidation = !m_allowStackOpt || !isOutermostFunctionBodyBlock;
579 finalizeBlock(_block, performValidation ? make_optional(blockStartStackHeight) : nullopt);
580 m_scope = originalScope;
581 }
582
createFunctionEntryID(FunctionDefinition const & _function)583 void CodeTransform::createFunctionEntryID(FunctionDefinition const& _function)
584 {
585 Scope::Function& scopeFunction = std::get<Scope::Function>(m_scope->identifiers.at(_function.name));
586 yulAssert(!m_context->functionEntryIDs.count(&scopeFunction), "");
587
588 optional<size_t> astID;
589 if (_function.debugData)
590 astID = _function.debugData->astID;
591
592 bool nameAlreadySeen = !m_assignedNamedLabels.insert(_function.name).second;
593
594 if (m_useNamedLabelsForFunctions == UseNamedLabels::YesAndForceUnique)
595 yulAssert(!nameAlreadySeen);
596
597 m_context->functionEntryIDs[&scopeFunction] =
598 (
599 m_useNamedLabelsForFunctions != UseNamedLabels::Never &&
600 !nameAlreadySeen
601 ) ?
602 m_assembly.namedLabel(
603 _function.name.str(),
604 _function.parameters.size(),
605 _function.returnVariables.size(),
606 astID
607 ) :
608 m_assembly.newLabelId();
609 }
610
functionEntryID(Scope::Function const & _scopeFunction) const611 AbstractAssembly::LabelID CodeTransform::functionEntryID(Scope::Function const& _scopeFunction) const
612 {
613 yulAssert(m_context->functionEntryIDs.count(&_scopeFunction), "");
614 return m_context->functionEntryIDs.at(&_scopeFunction);
615 }
616
visitExpression(Expression const & _expression)617 void CodeTransform::visitExpression(Expression const& _expression)
618 {
619 int height = m_assembly.stackHeight();
620 std::visit(*this, _expression);
621 expectDeposit(1, height);
622 }
623
setupReturnVariablesAndFunctionExit()624 void CodeTransform::setupReturnVariablesAndFunctionExit()
625 {
626 yulAssert(isInsideFunction(), "");
627 yulAssert(!returnVariablesAndFunctionExitAreSetup(), "");
628 yulAssert(m_scope, "");
629
630 ScopeGuard scopeGuard([oldScope = m_scope, this] { m_scope = oldScope; });
631 if (!m_scope->functionScope)
632 {
633 yulAssert(m_scope->superScope && m_scope->superScope->functionScope, "");
634 m_scope = m_scope->superScope;
635 }
636
637 // We could reuse unused slots for return variables, but it turns out this is detrimental in practice.
638 m_unusedStackSlots.clear();
639
640 if (m_delayedReturnVariables.empty())
641 {
642 m_functionExitStackHeight = 1;
643 return;
644 }
645
646 // Allocate slots for return variables as if they were declared as variables in the virtual function scope.
647 for (TypedName const& var: m_delayedReturnVariables)
648 (*this)(VariableDeclaration{var.debugData, {var}, {}});
649
650 m_functionExitStackHeight = ranges::max(m_delayedReturnVariables | ranges::views::transform([&](TypedName const& _name) {
651 return variableStackHeight(_name.name);
652 })) + 1;
653 m_delayedReturnVariables.clear();
654 }
655
656 namespace
657 {
658
statementNeedsReturnVariableSetup(Statement const & _statement,vector<TypedName> const & _returnVariables)659 bool statementNeedsReturnVariableSetup(Statement const& _statement, vector<TypedName> const& _returnVariables)
660 {
661 if (holds_alternative<FunctionDefinition>(_statement))
662 return true;
663 if (
664 holds_alternative<ExpressionStatement>(_statement) ||
665 holds_alternative<Assignment>(_statement)
666 )
667 {
668 ReferencesCounter referencesCounter{ReferencesCounter::CountWhat::OnlyVariables};
669 referencesCounter.visit(_statement);
670 auto isReferenced = [&referencesCounter](TypedName const& _returnVariable) {
671 return referencesCounter.references().count(_returnVariable.name);
672 };
673 if (ranges::none_of(_returnVariables, isReferenced))
674 return false;
675 }
676 return true;
677 }
678
679 }
680
visitStatements(vector<Statement> const & _statements)681 void CodeTransform::visitStatements(vector<Statement> const& _statements)
682 {
683 std::optional<AbstractAssembly::LabelID> jumpTarget = std::nullopt;
684
685 for (auto const& statement: _statements)
686 {
687 freeUnusedVariables();
688 if (
689 isInsideFunction() &&
690 !returnVariablesAndFunctionExitAreSetup() &&
691 statementNeedsReturnVariableSetup(statement, m_delayedReturnVariables)
692 )
693 setupReturnVariablesAndFunctionExit();
694
695 auto const* functionDefinition = std::get_if<FunctionDefinition>(&statement);
696 if (functionDefinition && !jumpTarget)
697 {
698 m_assembly.setSourceLocation(originLocationOf(*functionDefinition));
699 jumpTarget = m_assembly.newLabelId();
700 m_assembly.appendJumpTo(*jumpTarget, 0);
701 }
702 else if (!functionDefinition && jumpTarget)
703 {
704 m_assembly.appendLabel(*jumpTarget);
705 jumpTarget = std::nullopt;
706 }
707
708 std::visit(*this, statement);
709 }
710 // we may have a leftover jumpTarget
711 if (jumpTarget)
712 m_assembly.appendLabel(*jumpTarget);
713
714 freeUnusedVariables();
715 }
716
finalizeBlock(Block const & _block,optional<int> blockStartStackHeight)717 void CodeTransform::finalizeBlock(Block const& _block, optional<int> blockStartStackHeight)
718 {
719 m_assembly.setSourceLocation(originLocationOf(_block));
720
721 freeUnusedVariables();
722
723 // pop variables
724 yulAssert(m_info.scopes.at(&_block).get() == m_scope, "");
725 for (auto const& id: m_scope->identifiers)
726 if (holds_alternative<Scope::Variable>(id.second))
727 {
728 Scope::Variable const& var = std::get<Scope::Variable>(id.second);
729 if (m_allowStackOpt)
730 {
731 yulAssert(!m_context->variableStackHeights.count(&var), "");
732 yulAssert(!m_context->variableReferences.count(&var), "");
733 }
734 else
735 m_assembly.appendInstruction(evmasm::Instruction::POP);
736 }
737
738 if (blockStartStackHeight)
739 {
740 int deposit = m_assembly.stackHeight() - *blockStartStackHeight;
741 yulAssert(deposit == 0, "Invalid stack height at end of block: " + to_string(deposit));
742 }
743 }
744
generateMultiAssignment(vector<Identifier> const & _variableNames)745 void CodeTransform::generateMultiAssignment(vector<Identifier> const& _variableNames)
746 {
747 yulAssert(m_scope, "");
748 for (auto const& variableName: _variableNames | ranges::views::reverse)
749 generateAssignment(variableName);
750 }
751
generateAssignment(Identifier const & _variableName)752 void CodeTransform::generateAssignment(Identifier const& _variableName)
753 {
754 yulAssert(m_scope, "");
755 if (auto var = m_scope->lookup(_variableName.name))
756 {
757 Scope::Variable const& _var = std::get<Scope::Variable>(*var);
758 if (size_t heightDiff = variableHeightDiff(_var, _variableName.name, true))
759 m_assembly.appendInstruction(evmasm::swapInstruction(static_cast<unsigned>(heightDiff - 1)));
760 m_assembly.appendInstruction(evmasm::Instruction::POP);
761 decreaseReference(_variableName.name, _var);
762 }
763 else
764 {
765 yulAssert(
766 m_identifierAccessCodeGen,
767 "Identifier not found and no external access available."
768 );
769 m_identifierAccessCodeGen(_variableName, IdentifierContext::LValue, m_assembly);
770 }
771 }
772
variableHeightDiff(Scope::Variable const & _var,YulString _varName,bool _forSwap)773 size_t CodeTransform::variableHeightDiff(Scope::Variable const& _var, YulString _varName, bool _forSwap)
774 {
775 yulAssert(m_context->variableStackHeights.count(&_var), "");
776 size_t heightDiff = static_cast<size_t>(m_assembly.stackHeight()) - m_context->variableStackHeights[&_var];
777 yulAssert(heightDiff > (_forSwap ? 1 : 0), "Negative stack difference for variable.");
778 size_t limit = _forSwap ? 17 : 16;
779 if (heightDiff > limit)
780 {
781 m_stackErrors.emplace_back(
782 _varName,
783 heightDiff - limit,
784 "Variable " +
785 _varName.str() +
786 " is " +
787 to_string(heightDiff - limit) +
788 " slot(s) too deep inside the stack."
789 );
790 m_assembly.markAsInvalid();
791 return _forSwap ? 2 : 1;
792 }
793 return heightDiff;
794 }
795
variableStackHeight(YulString _name) const796 int CodeTransform::variableStackHeight(YulString _name) const
797 {
798 Scope::Variable const* var = get_if<Scope::Variable>(m_scope->lookup(_name));
799 yulAssert(var, "");
800 return static_cast<int>(m_context->variableStackHeights.at(var));
801 }
802
expectDeposit(int _deposit,int _oldHeight) const803 void CodeTransform::expectDeposit(int _deposit, int _oldHeight) const
804 {
805 yulAssert(m_assembly.stackHeight() == _oldHeight + _deposit, "Invalid stack deposit.");
806 }
807