diff options
21 files changed, 195 insertions, 68 deletions
diff --git a/libsolidity/inlineasm/AsmScope.cpp b/libsolidity/inlineasm/AsmScope.cpp index 858bd4de..10893b96 100644 --- a/libsolidity/inlineasm/AsmScope.cpp +++ b/libsolidity/inlineasm/AsmScope.cpp @@ -24,7 +24,6 @@ using namespace std; using namespace dev; using namespace dev::solidity::assembly; - bool Scope::registerLabel(yul::YulString _name) { if (exists(_name)) diff --git a/libyul/optimiser/DataFlowAnalyzer.cpp b/libyul/optimiser/DataFlowAnalyzer.cpp index 1ff1d2f0..134777d0 100644 --- a/libyul/optimiser/DataFlowAnalyzer.cpp +++ b/libyul/optimiser/DataFlowAnalyzer.cpp @@ -84,13 +84,26 @@ void DataFlowAnalyzer::operator()(Switch& _switch) void DataFlowAnalyzer::operator()(FunctionDefinition& _fun) { + // Save all information. We might rather reinstantiate this class, + // but this could be difficult if it is subclassed. + map<YulString, Expression const*> value; + map<YulString, set<YulString>> references; + map<YulString, set<YulString>> referencedBy; + m_value.swap(value); + m_references.swap(references); + m_referencedBy.swap(referencedBy); pushScope(true); + for (auto const& parameter: _fun.parameters) m_variableScopes.back().variables.emplace(parameter.name); for (auto const& var: _fun.returnVariables) m_variableScopes.back().variables.emplace(var.name); ASTModifier::operator()(_fun); + popScope(); + m_value.swap(value); + m_references.swap(references); + m_referencedBy.swap(referencedBy); } void DataFlowAnalyzer::operator()(ForLoop& _for) diff --git a/libyul/optimiser/NameDispenser.cpp b/libyul/optimiser/NameDispenser.cpp index 492c863d..3c870fa5 100644 --- a/libyul/optimiser/NameDispenser.cpp +++ b/libyul/optimiser/NameDispenser.cpp @@ -52,11 +52,10 @@ YulString NameDispenser::newName(YulString _nameHint, YulString _context) YulString NameDispenser::newNameInternal(YulString _nameHint) { YulString name = _nameHint; - size_t suffix = 0; while (name.empty() || m_usedNames.count(name)) { - suffix++; - name = YulString(_nameHint.str() + "_" + to_string(suffix)); + m_counter++; + name = YulString(_nameHint.str() + "_" + to_string(m_counter)); } m_usedNames.emplace(name); return name; diff --git a/libyul/optimiser/NameDispenser.h b/libyul/optimiser/NameDispenser.h index 57adbcad..7311440b 100644 --- a/libyul/optimiser/NameDispenser.h +++ b/libyul/optimiser/NameDispenser.h @@ -54,6 +54,7 @@ private: YulString newNameInternal(YulString _nameHint); std::set<YulString> m_usedNames; + size_t m_counter = 0; }; } diff --git a/libyul/optimiser/Suite.cpp b/libyul/optimiser/Suite.cpp index c7339d2e..7d52a5a8 100644 --- a/libyul/optimiser/Suite.cpp +++ b/libyul/optimiser/Suite.cpp @@ -33,6 +33,7 @@ #include <libyul/optimiser/CommonSubexpressionEliminator.h> #include <libyul/optimiser/SSATransform.h> #include <libyul/optimiser/RedundantAssignEliminator.h> +#include <libyul/optimiser/VarDeclPropagator.h> #include <libsolidity/inlineasm/AsmAnalysisInfo.h> #include <libsolidity/inlineasm/AsmData.h> @@ -65,6 +66,7 @@ void OptimiserSuite::run( ExpressionSplitter{dispenser}(ast); SSATransform::run(ast, dispenser); RedundantAssignEliminator::run(ast); + VarDeclPropagator{}(ast); RedundantAssignEliminator::run(ast); CommonSubexpressionEliminator{}(ast); @@ -90,21 +92,26 @@ void OptimiserSuite::run( RedundantAssignEliminator::run(ast); CommonSubexpressionEliminator{}(ast); FullInliner{ast, dispenser}.run(); + VarDeclPropagator{}(ast); SSATransform::run(ast, dispenser); RedundantAssignEliminator::run(ast); + VarDeclPropagator{}(ast); RedundantAssignEliminator::run(ast); ExpressionSimplifier::run(ast); CommonSubexpressionEliminator{}(ast); SSATransform::run(ast, dispenser); RedundantAssignEliminator::run(ast); + VarDeclPropagator{}(ast); RedundantAssignEliminator::run(ast); UnusedPruner::runUntilStabilised(ast, reservedIdentifiers); } ExpressionJoiner::run(ast); + VarDeclPropagator{}(ast); UnusedPruner::runUntilStabilised(ast); ExpressionJoiner::run(ast); UnusedPruner::runUntilStabilised(ast); ExpressionJoiner::run(ast); + VarDeclPropagator{}(ast); UnusedPruner::runUntilStabilised(ast); ExpressionJoiner::run(ast); UnusedPruner::runUntilStabilised(ast); diff --git a/test/libyul/yulOptimizerTests/commonSubexpressionEliminator/case2.yul b/test/libyul/yulOptimizerTests/commonSubexpressionEliminator/case2.yul new file mode 100644 index 00000000..fd8b4bc8 --- /dev/null +++ b/test/libyul/yulOptimizerTests/commonSubexpressionEliminator/case2.yul @@ -0,0 +1,52 @@ +{ + let _13 := 0x20 + let _14 := allocate(_13) + pop(_14) + let _15 := 2 + let _16 := 3 + let _17 := 0x40 + let _18 := allocate(_17) + let _19 := array_index_access(_18, _16) + mstore(_19, _15) + function allocate(size) -> p + { + let _1 := 0x40 + let p_2 := mload(_1) + p := p_2 + let _20 := add(p_2, size) + mstore(_1, _20) + } + function array_index_access(array, index) -> p_1 + { + let _21 := 0x20 + let _22 := mul(index, _21) + p_1 := add(array, _22) + } +} +// ---- +// commonSubexpressionEliminator +// { +// let _13 := 0x20 +// let _14 := allocate(_13) +// pop(_14) +// let _15 := 2 +// let _16 := 3 +// let _17 := 0x40 +// let _18 := allocate(_17) +// let _19 := array_index_access(_18, _16) +// mstore(_19, _15) +// function allocate(size) -> p +// { +// let _1 := 0x40 +// let p_2 := mload(_1) +// p := p_2 +// let _20 := add(p_2, size) +// mstore(_1, _20) +// } +// function array_index_access(array, index) -> p_1 +// { +// let _21 := 0x20 +// let _22 := mul(index, _21) +// p_1 := add(array, _22) +// } +// } diff --git a/test/libyul/yulOptimizerTests/commonSubexpressionEliminator/function_scopes.yul b/test/libyul/yulOptimizerTests/commonSubexpressionEliminator/function_scopes.yul new file mode 100644 index 00000000..28e840cf --- /dev/null +++ b/test/libyul/yulOptimizerTests/commonSubexpressionEliminator/function_scopes.yul @@ -0,0 +1,52 @@ +{ + function allocate(size) -> p + { + let _1 := 0x40 + p := mload(_1) + let _2 := add(p, size) + let _3 := 0x40 + mstore(_3, _2) + } + function array_index_access(array, index) -> p_1 + { + let _4 := 0x20 + let _5 := mul(index, _4) + p_1 := add(array, _5) + } + let _6 := 0x20 + let _7 := allocate(_6) + pop(_7) + let _8 := 0x40 + let x := allocate(_8) + let _9 := 2 + let _10 := 3 + let _11 := array_index_access(x, _10) + mstore(_11, _9) +} +// ---- +// commonSubexpressionEliminator +// { +// function allocate(size) -> p +// { +// let _1 := 0x40 +// p := mload(_1) +// let _2 := add(p, size) +// let _3 := _1 +// mstore(_1, _2) +// } +// function array_index_access(array, index) -> p_1 +// { +// let _4 := 0x20 +// let _5 := mul(index, _4) +// p_1 := add(array, _5) +// } +// let _6 := 0x20 +// let _7 := allocate(_6) +// pop(_7) +// let _8 := 0x40 +// let x := allocate(_8) +// let _9 := 2 +// let _10 := 3 +// let _11 := array_index_access(x, _10) +// mstore(_11, _9) +// } diff --git a/test/libyul/yulOptimizerTests/disambiguator/for_statement.yul b/test/libyul/yulOptimizerTests/disambiguator/for_statement.yul index 0d2a38c5..6875abec 100644 --- a/test/libyul/yulOptimizerTests/disambiguator/for_statement.yul +++ b/test/libyul/yulOptimizerTests/disambiguator/for_statement.yul @@ -22,7 +22,7 @@ // a_1 := a_1 // } // { -// let b_1:u256 := a_1 +// let b_2:u256 := a_1 // } // } // } diff --git a/test/libyul/yulOptimizerTests/disambiguator/funtion_call.yul b/test/libyul/yulOptimizerTests/disambiguator/funtion_call.yul index f917bb68..df49b92a 100644 --- a/test/libyul/yulOptimizerTests/disambiguator/funtion_call.yul +++ b/test/libyul/yulOptimizerTests/disambiguator/funtion_call.yul @@ -14,9 +14,9 @@ // let a:u256, b:u256, c:u256, d:u256, f:u256 // } // { -// function f_1(a_1:u256) -> c_1:u256, d_1:u256 +// function f_1(a_2:u256) -> c_3:u256, d_4:u256 // { -// let b_1:u256, c_1_1:u256 := f_1(a_1) +// let b_5:u256, c_1:u256 := f_1(a_2) // } // } // } diff --git a/test/libyul/yulOptimizerTests/disambiguator/if_statement.yul b/test/libyul/yulOptimizerTests/disambiguator/if_statement.yul index 14f53757..bc3aa30f 100644 --- a/test/libyul/yulOptimizerTests/disambiguator/if_statement.yul +++ b/test/libyul/yulOptimizerTests/disambiguator/if_statement.yul @@ -16,7 +16,7 @@ // let a_1:bool // if a_1 // { -// let b_1:bool := a_1 +// let b_2:bool := a_1 // } // } // } diff --git a/test/libyul/yulOptimizerTests/disambiguator/switch_statement.yul b/test/libyul/yulOptimizerTests/disambiguator/switch_statement.yul index 340ecccf..e62e957f 100644 --- a/test/libyul/yulOptimizerTests/disambiguator/switch_statement.yul +++ b/test/libyul/yulOptimizerTests/disambiguator/switch_statement.yul @@ -18,10 +18,10 @@ // let a_1:u256 // switch a_1 // case 0:u256 { -// let b_1:u256 := a_1 +// let b_2:u256 := a_1 // } // default { -// let c_1:u256 := a_1 +// let c_3:u256 := a_1 // } // } // } diff --git a/test/libyul/yulOptimizerTests/disambiguator/variables_inside_functions.yul b/test/libyul/yulOptimizerTests/disambiguator/variables_inside_functions.yul index e80959f6..839692bc 100644 --- a/test/libyul/yulOptimizerTests/disambiguator/variables_inside_functions.yul +++ b/test/libyul/yulOptimizerTests/disambiguator/variables_inside_functions.yul @@ -13,12 +13,12 @@ // let c:u256 // let b:u256 // } -// function f(a:u256, c_1:u256) -> b_1:u256 +// function f(a:u256, c_1:u256) -> b_2:u256 // { // let x:u256 // } // { -// let a_1:u256 -// let x_1:u256 +// let a_3:u256 +// let x_4:u256 // } // } diff --git a/test/libyul/yulOptimizerTests/fullInliner/double_inline.yul b/test/libyul/yulOptimizerTests/fullInliner/double_inline.yul index dd1c1f8a..ee7f5bf5 100644 --- a/test/libyul/yulOptimizerTests/fullInliner/double_inline.yul +++ b/test/libyul/yulOptimizerTests/fullInliner/double_inline.yul @@ -14,13 +14,13 @@ // f_b := sload(mload(f_a)) // f_c := 3 // let b3 := f_b -// let f_a_1 := f_c -// let f_b_1 -// let f_c_1 -// f_b_1 := sload(mload(f_a_1)) -// f_c_1 := 3 -// let b4 := f_b_1 -// let c4 := f_c_1 +// let f_a_2 := f_c +// let f_b_3 +// let f_c_4 +// f_b_3 := sload(mload(f_a_2)) +// f_c_4 := 3 +// let b4 := f_b_3 +// let c4 := f_c_4 // } // function f(a) -> b, c // { diff --git a/test/libyul/yulOptimizerTests/fullInliner/multi_fun.yul b/test/libyul/yulOptimizerTests/fullInliner/multi_fun.yul index c704944d..8bc6ec58 100644 --- a/test/libyul/yulOptimizerTests/fullInliner/multi_fun.yul +++ b/test/libyul/yulOptimizerTests/fullInliner/multi_fun.yul @@ -23,9 +23,9 @@ // } // function g(b, c) -> y // { -// let f_a_1 := b -// let f_x_1 -// f_x_1 := add(f_a_1, f_a_1) -// y := mul(mload(c), f_x_1) +// let f_a_6 := b +// let f_x_7 +// f_x_7 := add(f_a_6, f_a_6) +// y := mul(mload(c), f_x_7) // } // } diff --git a/test/libyul/yulOptimizerTests/fullInliner/multi_fun_callback.yul b/test/libyul/yulOptimizerTests/fullInliner/multi_fun_callback.yul index bcdba8e0..d09877de 100644 --- a/test/libyul/yulOptimizerTests/fullInliner/multi_fun_callback.yul +++ b/test/libyul/yulOptimizerTests/fullInliner/multi_fun_callback.yul @@ -46,14 +46,14 @@ // } // function g(x_1) // { -// let f_x_1 := 1 -// mstore(0, f_x_1) +// let f_x_8 := 1 +// mstore(0, f_x_8) // let f_h_t // f_h_t := 2 // mstore(7, f_h_t) // let f_g_x_1 := 10 // f(1) -// mstore(1, f_x_1) +// mstore(1, f_x_8) // } // function h() -> t // { diff --git a/test/libyul/yulOptimizerTests/fullInliner/not_inside_for.yul b/test/libyul/yulOptimizerTests/fullInliner/not_inside_for.yul index 44fc7b21..9644e6c1 100644 --- a/test/libyul/yulOptimizerTests/fullInliner/not_inside_for.yul +++ b/test/libyul/yulOptimizerTests/fullInliner/not_inside_for.yul @@ -21,18 +21,18 @@ // } // f(x) // { -// let f_a_1 := x -// let f_r_1 -// sstore(f_a_1, 0) -// f_r_1 := f_a_1 -// x := f_r_1 +// let f_a_3 := x +// let f_r_4 +// sstore(f_a_3, 0) +// f_r_4 := f_a_3 +// x := f_r_4 // } // { -// let f_a_2 := x -// let f_r_2 -// sstore(f_a_2, 0) -// f_r_2 := f_a_2 -// let t := f_r_2 +// let f_a_6 := x +// let f_r_7 +// sstore(f_a_6, 0) +// f_r_7 := f_a_6 +// let t := f_r_7 // } // } // function f(a) -> r diff --git a/test/libyul/yulOptimizerTests/fullSuite/medium.yul b/test/libyul/yulOptimizerTests/fullSuite/medium.yul index 45cc555d..47812fa8 100644 --- a/test/libyul/yulOptimizerTests/fullSuite/medium.yul +++ b/test/libyul/yulOptimizerTests/fullSuite/medium.yul @@ -14,13 +14,13 @@ // fullSuite // { // { -// let _12 := 0x20 +// let _18 := 0x20 // let allocate__7 := 0x40 -// let allocate_p_2 := mload(allocate__7) -// mstore(allocate__7, add(allocate_p_2, _12)) -// pop(allocate_p_2) -// let allocate_p_2_1 := mload(allocate__7) -// mstore(allocate__7, add(allocate_p_2_1, allocate__7)) -// mstore(add(allocate_p_2_1, 96), 2) +// let allocate_p_12 := mload(allocate__7) +// mstore(allocate__7, add(allocate_p_12, _18)) +// pop(allocate_p_12) +// let allocate_p_12_31 := mload(allocate__7) +// mstore(allocate__7, add(allocate_p_12_31, allocate__7)) +// mstore(add(allocate_p_12_31, 96), 2) // } // } diff --git a/test/libyul/yulOptimizerTests/ssaPlusCleanup/control_structures.yul b/test/libyul/yulOptimizerTests/ssaPlusCleanup/control_structures.yul index 51d1627f..d2408343 100644 --- a/test/libyul/yulOptimizerTests/ssaPlusCleanup/control_structures.yul +++ b/test/libyul/yulOptimizerTests/ssaPlusCleanup/control_structures.yul @@ -17,19 +17,19 @@ // let length_1 := mload(from) // length := length_1 // mstore(to, length_1) -// let from_1 := add(from, 0x20) -// let to_1 := add(to, 0x20) +// let from_2 := add(from, 0x20) +// let to_3 := add(to, 0x20) // for { -// let x_1 := 1 -// let x := x_1 +// let x_4 := 1 +// let x := x_4 // } // lt(x, length_1) // { -// let x_2 := add(x, 0x20) -// x := x_2 +// let x_5 := add(x, 0x20) +// x := x_5 // } // { -// mstore(add(to_1, x), mload(add(from_1, x))) +// mstore(add(to_3, x), mload(add(from_2, x))) // } // } // } diff --git a/test/libyul/yulOptimizerTests/ssaTransform/function.yul b/test/libyul/yulOptimizerTests/ssaTransform/function.yul index b319d12e..995d16cc 100644 --- a/test/libyul/yulOptimizerTests/ssaTransform/function.yul +++ b/test/libyul/yulOptimizerTests/ssaTransform/function.yul @@ -13,11 +13,11 @@ // { // let b_1 := add(b, a) // b := b_1 -// let c_1 := add(c, b_1) -// c := c_1 -// let d_1 := add(d, c_1) -// d := d_1 -// let a_1 := add(a, d_1) -// a := a_1 +// let c_2 := add(c, b_1) +// c := c_2 +// let d_3 := add(d, c_2) +// d := d_3 +// let a_4 := add(a, d_3) +// a := a_4 // } // } diff --git a/test/libyul/yulOptimizerTests/ssaTransform/nested.yul b/test/libyul/yulOptimizerTests/ssaTransform/nested.yul index 55adfc37..49a76953 100644 --- a/test/libyul/yulOptimizerTests/ssaTransform/nested.yul +++ b/test/libyul/yulOptimizerTests/ssaTransform/nested.yul @@ -17,16 +17,16 @@ // let a := a_1 // let a_2 := 2 // a := a_2 -// let b_1 := 3 -// let b := b_1 -// let b_2 := 4 -// b := b_2 +// let b_3 := 3 +// let b := b_3 +// let b_4 := 4 +// b := b_4 // { -// let a_3 := 3 -// a := a_3 -// let a_4 := 4 -// a := a_4 +// let a_5 := 3 +// a := a_5 +// let a_6 := 4 +// a := a_6 // } -// let a_5 := add(b_2, a) -// a := a_5 +// let a_7 := add(b_4, a) +// a := a_7 // } diff --git a/test/tools/yulopti.cpp b/test/tools/yulopti.cpp index 68fc9f4f..348c5f4a 100644 --- a/test/tools/yulopti.cpp +++ b/test/tools/yulopti.cpp @@ -45,6 +45,7 @@ #include <libyul/optimiser/ExpressionJoiner.h> #include <libyul/optimiser/RedundantAssignEliminator.h> #include <libyul/optimiser/SSATransform.h> +#include <libyul/optimiser/VarDeclPropagator.h> #include <libdevcore/JSON.h> @@ -120,7 +121,7 @@ public: m_nameDispenser = make_shared<NameDispenser>(*m_ast); disambiguated = true; } - cout << "(q)quit/(f)flatten/(c)se/(x)plit/(j)oin/(g)rouper/(h)oister/" << endl; + cout << "(q)quit/(f)flatten/(c)se/propagate var(d)ecls/(x)plit/(j)oin/(g)rouper/(h)oister/" << endl; cout << " (e)xpr inline/(i)nline/(s)implify/(u)nusedprune/ss(a) transform/" << endl; cout << " (r)edundant assign elim./re(m)aterializer? "; cout.flush(); @@ -136,6 +137,9 @@ public: case 'c': (CommonSubexpressionEliminator{})(*m_ast); break; + case 'd': + (VarDeclPropagator{})(*m_ast); + break; case 'x': ExpressionSplitter{*m_nameDispenser}(*m_ast); break; |