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 * Stack layout generator for Yul to EVM code generation. 20 */ 21 22 #pragma once 23 24 #include <libyul/backends/evm/ControlFlowGraph.h> 25 26 #include <map> 27 28 namespace solidity::yul 29 { 30 31 struct StackLayout 32 { 33 struct BlockInfo 34 { 35 /// Complete stack layout that is required for entering a block. 36 Stack entryLayout; 37 /// The resulting stack layout after executing the block. 38 Stack exitLayout; 39 }; 40 std::map<CFG::BasicBlock const*, BlockInfo> blockInfos; 41 /// For each operation the complete stack layout that: 42 /// - has the slots required for the operation at the stack top. 43 /// - will have the operation result in a layout that makes it easy to achieve the next desired layout. 44 std::map<CFG::Operation const*, Stack> operationEntryLayout; 45 }; 46 47 class StackLayoutGenerator 48 { 49 public: 50 struct StackTooDeep 51 { 52 /// Number of slots that need to be saved. 53 size_t deficit = 0; 54 /// Set of variables, eliminating which would decrease the stack deficit. 55 std::vector<YulString> variableChoices; 56 }; 57 58 static StackLayout run(CFG const& _cfg); 59 /// @returns a map from function names to the stack too deep errors occurring in that function. 60 /// Requires @a _cfg to be a control flow graph generated from disambiguated Yul. 61 /// The empty string is mapped to the stack too deep errors of the main entry point. 62 static std::map<YulString, std::vector<StackTooDeep>> reportStackTooDeep(CFG const& _cfg); 63 /// @returns all stack too deep errors in the function named @a _functionName. 64 /// Requires @a _cfg to be a control flow graph generated from disambiguated Yul. 65 /// If @a _functionName is empty, the stack too deep errors of the main entry point are reported instead. 66 static std::vector<StackTooDeep> reportStackTooDeep(CFG const& _cfg, YulString _functionName); 67 68 private: 69 StackLayoutGenerator(StackLayout& _context); 70 71 /// @returns the optimal entry stack layout, s.t. @a _operation can be applied to it and 72 /// the result can be transformed to @a _exitStack with minimal stack shuffling. 73 /// Simultaneously stores the entry layout required for executing the operation in m_layout. 74 Stack propagateStackThroughOperation(Stack _exitStack, CFG::Operation const& _operation, bool _aggressiveStackCompression = false); 75 76 /// @returns the desired stack layout at the entry of @a _block, assuming the layout after 77 /// executing the block should be @a _exitStack. 78 Stack propagateStackThroughBlock(Stack _exitStack, CFG::BasicBlock const& _block, bool _aggressiveStackCompression = false); 79 80 /// Main algorithm walking the graph from entry to exit and propagating back the stack layouts to the entries. 81 /// Iteratively reruns itself along backwards jumps until the layout is stabilized. 82 void processEntryPoint(CFG::BasicBlock const& _entry); 83 84 /// @returns the best known exit layout of @a _block, if all dependencies are already @a _visited. 85 /// If not, adds the dependencies to @a _dependencyList and @returns std::nullopt. 86 std::optional<Stack> getExitLayoutOrStageDependencies( 87 CFG::BasicBlock const& _block, 88 std::set<CFG::BasicBlock const*> const& _visited, 89 std::list<CFG::BasicBlock const*>& _dependencyList 90 ) const; 91 92 /// @returns a pair of ``{jumpingBlock, targetBlock}`` for each backwards jump in the graph starting at @a _entry. 93 std::list<std::pair<CFG::BasicBlock const*, CFG::BasicBlock const*>> collectBackwardsJumps(CFG::BasicBlock const& _entry) const; 94 95 /// After the main algorithms, layouts at conditional jumps are merely compatible, i.e. the exit layout of the 96 /// jumping block is a superset of the entry layout of the target block. This function modifies the entry layouts 97 /// of conditional jump targets, s.t. the entry layout of target blocks match the exit layout of the jumping block 98 /// exactly, except that slots not required after the jump are marked as `JunkSlot`s. 99 void stitchConditionalJumps(CFG::BasicBlock const& _block); 100 101 /// Calculates the ideal stack layout, s.t. both @a _stack1 and @a _stack2 can be achieved with minimal 102 /// stack shuffling when starting from the returned layout. 103 static Stack combineStack(Stack const& _stack1, Stack const& _stack2); 104 105 /// Walks through the CFG and reports any stack too deep errors that would occur when generating code for it 106 /// without countermeasures. 107 std::vector<StackTooDeep> reportStackTooDeep(CFG::BasicBlock const& _entry) const; 108 109 /// @returns a copy of @a _stack stripped of all duplicates and slots that can be freely generated. 110 /// Attempts to create a layout that requires a minimal amount of operations to reconstruct the original 111 /// stack @a _stack. 112 static Stack compressStack(Stack _stack); 113 114 StackLayout& m_layout; 115 }; 116 117 } 118