From b1454433b27124badece507b3f3aae822de8d83d Mon Sep 17 00:00:00 2001 From: chriseth Date: Sat, 3 Nov 2018 16:04:42 +0100 Subject: Remove variables that go out of scope from data structure. --- libyul/optimiser/RedundantAssignEliminator.cpp | 32 ++- libyul/optimiser/RedundantAssignEliminator.h | 7 + .../yulOptimizerTests/fullSuite/abi_example1.yul | 309 ++++++++++++--------- 3 files changed, 199 insertions(+), 149 deletions(-) diff --git a/libyul/optimiser/RedundantAssignEliminator.cpp b/libyul/optimiser/RedundantAssignEliminator.cpp index df6c4e4e..b7217074 100644 --- a/libyul/optimiser/RedundantAssignEliminator.cpp +++ b/libyul/optimiser/RedundantAssignEliminator.cpp @@ -96,9 +96,15 @@ void RedundantAssignEliminator::operator()(FunctionDefinition const& _functionDe (*this)(_functionDefinition.body); for (auto const& param: _functionDefinition.parameters) + { changeUndecidedTo(param.name, State::Unused); + finalize(param.name); + } for (auto const& retParam: _functionDefinition.returnVariables) + { changeUndecidedTo(retParam.name, State::Used); + finalize(retParam.name); + } } void RedundantAssignEliminator::operator()(ForLoop const& _forLoop) @@ -150,16 +156,7 @@ void RedundantAssignEliminator::run(Block& _ast) RedundantAssignEliminator rae; rae(_ast); - std::set assignmentsToRemove; - for (auto const& variables: rae.m_assignments) - for (auto const& assignment: variables.second) - { - assertThrow(assignment.second != State::Undecided, OptimizerException, ""); - if (assignment.second == State::Unused && MovableChecker{*assignment.first->value}.movable()) - assignmentsToRemove.emplace(assignment.first); - } - - AssignmentRemover remover{assignmentsToRemove}; + AssignmentRemover remover{rae.m_assignmentsToRemove}; remover(_ast); } @@ -192,6 +189,8 @@ void joinMap(std::map& _a, std::map&& _b, F _conflictSolver) void RedundantAssignEliminator::join(RedundantAssignEliminator& _other) { + m_assignmentsToRemove.insert(begin(_other.m_assignmentsToRemove), end(_other.m_assignmentsToRemove)); + joinMap(m_assignments, std::move(_other.m_assignments), []( map& _assignmentHere, map&& _assignmentThere @@ -208,6 +207,19 @@ void RedundantAssignEliminator::changeUndecidedTo(YulString _variable, Redundant assignment.second = _newState; } +void RedundantAssignEliminator::finalize(YulString _variable) +{ + for (auto& assignment: m_assignments[_variable]) + { + assertThrow(assignment.second != State::Undecided, OptimizerException, ""); + if (assignment.second == State{State::Unused} && MovableChecker{*assignment.first->value}.movable()) + // TODO the only point where we actually need this + // to be a set is for the for loop + m_assignmentsToRemove.insert(assignment.first); + } + m_assignments.erase(_variable); +} + void AssignmentRemover::operator()(Block& _block) { boost::range::remove_erase_if(_block.statements, [=](Statement const& _statement) -> bool { diff --git a/libyul/optimiser/RedundantAssignEliminator.h b/libyul/optimiser/RedundantAssignEliminator.h index a9c6a8f7..76106aae 100644 --- a/libyul/optimiser/RedundantAssignEliminator.h +++ b/libyul/optimiser/RedundantAssignEliminator.h @@ -149,8 +149,12 @@ private: } ~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); } @@ -164,10 +168,13 @@ private: /// Will destroy @a _other. void join(RedundantAssignEliminator& _other); void changeUndecidedTo(YulString _variable, State _newState); + void finalize(YulString _variable); std::set m_declaredVariables; // TODO check that this does not cause nondeterminism! + // This could also be a pseudo-map from state to assignment. std::map> m_assignments; + std::set m_assignmentsToRemove; }; class AssignmentRemover: public ASTModifier diff --git a/test/libyul/yulOptimizerTests/fullSuite/abi_example1.yul b/test/libyul/yulOptimizerTests/fullSuite/abi_example1.yul index c2fb3274..cc6044d3 100644 --- a/test/libyul/yulOptimizerTests/fullSuite/abi_example1.yul +++ b/test/libyul/yulOptimizerTests/fullSuite/abi_example1.yul @@ -458,166 +458,197 @@ // ---- // fullSuite // { -// let _246 := mload(0) -// let abi_encode_pos := 0x20 -// let abi_encode_length_5 := mload(_246) -// mstore(0x20, abi_encode_length_5) -// abi_encode_pos := 64 -// let abi_encode_srcPtr := add(_246, 0x20) -// for { -// let abi_encode_i_5 := 0 -// } -// lt(abi_encode_i_5, abi_encode_length_5) -// { -// abi_encode_i_5 := add(abi_encode_i_5, 1) -// } // { -// let _456 := mload(abi_encode_srcPtr) -// let abi_encode_pos_1_6 := abi_encode_pos -// let abi_encode_srcPtr_1_5 := _456 +// let _1 := 0x20 +// let _2 := 0 +// let _485 := mload(_2) +// let abi_encode_pos := _1 +// let abi_encode_length_68 := mload(_485) +// mstore(_1, abi_encode_length_68) +// let abi_encode_pos_590 := 64 +// abi_encode_pos := abi_encode_pos_590 +// let abi_encode_srcPtr := add(_485, _1) // for { -// let abi_encode_i_6_5 := 0 +// let abi_encode_i_69 := _2 // } -// lt(abi_encode_i_6_5, 0x3) +// lt(abi_encode_i_69, abi_encode_length_68) // { -// abi_encode_i_6_5 := add(abi_encode_i_6_5, 1) +// abi_encode_i_69 := add(abi_encode_i_69, 1) // } // { -// mstore(abi_encode_pos_1_6, and(mload(abi_encode_srcPtr_1_5), 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF)) -// abi_encode_srcPtr_1_5 := add(abi_encode_srcPtr_1_5, 0x20) -// abi_encode_pos_1_6 := add(abi_encode_pos_1_6, 0x20) +// let _922 := mload(abi_encode_srcPtr) +// let abi_encode_pos_71_1029 := abi_encode_pos +// let abi_encode_length_72_1030 := 0x3 +// let abi_encode_srcPtr_73_1031 := _922 +// for { +// let abi_encode_i_74_1032 := _2 +// } +// lt(abi_encode_i_74_1032, abi_encode_length_72_1030) +// { +// abi_encode_i_74_1032 := add(abi_encode_i_74_1032, 1) +// } +// { +// mstore(abi_encode_pos_71_1029, and(mload(abi_encode_srcPtr_73_1031), 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF)) +// abi_encode_srcPtr_73_1031 := add(abi_encode_srcPtr_73_1031, _1) +// abi_encode_pos_71_1029 := add(abi_encode_pos_71_1029, _1) +// } +// abi_encode_srcPtr := add(abi_encode_srcPtr, _1) +// abi_encode_pos := add(abi_encode_pos, 0x60) // } -// abi_encode_srcPtr := add(abi_encode_srcPtr, 0x20) -// abi_encode_pos := add(abi_encode_pos, 0x60) -// } -// let _248 := mload(0x40) -// let _250 := mload(0x20) -// if slt(sub(_248, _250), 128) -// { -// revert(0, 0) -// } -// let abi_decode_value0_2_4 := calldataload(_250) -// let abi_decode_value1_2_4 := calldataload(add(_250, 32)) -// let abi_decode_offset_18 := calldataload(add(_250, 64)) -// if gt(abi_decode_offset_18, 0xffffffffffffffff) -// { -// revert(0, 0) -// } -// let _474 := add(_250, abi_decode_offset_18) -// if iszero(slt(add(_474, 0x1f), _248)) -// { -// revert(0, 0) -// } -// let abi_decode_length_4_1 := calldataload(_474) -// if gt(abi_decode_length_4_1, 0xffffffffffffffff) -// { -// revert(0, 0) -// } -// let abi_decode_array_allo__371_1 := mul(abi_decode_length_4_1, 0x20) -// let abi_decode_array_4_1_1 := allocateMemory(add(abi_decode_array_allo__371_1, 0x20)) -// let abi_decode_dst_4_7 := abi_decode_array_4_1_1 -// mstore(abi_decode_array_4_1_1, abi_decode_length_4_1) -// let abi_decode_offset_5_1_1 := add(_474, 0x20) -// abi_decode_dst_4_7 := add(abi_decode_array_4_1_1, 0x20) -// let abi_decode_src_4_5 := abi_decode_offset_5_1_1 -// if gt(add(add(_474, abi_decode_array_allo__371_1), 0x20), _248) -// { -// revert(0, 0) -// } -// for { -// let abi_decode_i_4_5 := 0 -// } -// lt(abi_decode_i_4_5, abi_decode_length_4_1) -// { -// abi_decode_i_4_5 := add(abi_decode_i_4_5, 1) -// } -// { -// mstore(abi_decode_dst_4_7, calldataload(abi_decode_src_4_5)) -// abi_decode_dst_4_7 := add(abi_decode_dst_4_7, 0x20) -// abi_decode_src_4_5 := add(abi_decode_src_4_5, 0x20) -// } -// let abi_decode_offset_19 := calldataload(add(_250, 96)) -// if gt(abi_decode_offset_19, 0xffffffffffffffff) -// { -// revert(0, 0) -// } -// let _481 := add(_250, abi_decode_offset_19) -// if iszero(slt(add(_481, 0x1f), _248)) -// { -// revert(0, 0) -// } -// let abi_decode_length_1_1 := calldataload(_481) -// if gt(abi_decode_length_1_1, 0xffffffffffffffff) -// { -// revert(0, 0) -// } -// let abi_decode_array_1_1_1 := allocateMemory(add(mul(abi_decode_length_1_1, 0x20), 0x20)) -// let abi_decode_dst_1_7 := abi_decode_array_1_1_1 -// mstore(abi_decode_array_1_1_1, abi_decode_length_1_1) -// let abi_decode_offset_2_1_1 := add(_481, 0x20) -// abi_decode_dst_1_7 := add(abi_decode_array_1_1_1, 0x20) -// let abi_decode_src_1_5 := abi_decode_offset_2_1_1 -// if gt(add(add(_481, mul(abi_decode_length_1_1, 0x40)), 0x20), _248) -// { -// revert(0, 0) -// } -// for { -// let abi_decode_i_1_5 := 0 -// } -// lt(abi_decode_i_1_5, abi_decode_length_1_1) -// { -// abi_decode_i_1_5 := add(abi_decode_i_1_5, 1) -// } -// { -// if iszero(slt(add(abi_decode_src_1_5, 0x1f), _248)) +// let _924 := 0x40 +// let _487 := mload(_924) +// let _488 := mload(_1) +// let abi_decode_value0_60_618 +// let abi_decode_value0_60 := abi_decode_value0_60_618 +// let abi_decode_value1_61_619 +// let abi_decode_value1_61 := abi_decode_value1_61_619 +// let abi_decode_value2_620 +// let abi_decode_value2 := abi_decode_value2_620 +// let abi_decode_value3_621 +// let abi_decode_value3 := abi_decode_value3_621 +// if slt(sub(_487, _488), 128) // { -// revert(0, 0) +// revert(_2, _2) // } -// if 0 // { -// revert(0, 0) +// abi_decode_value0_60 := calldataload(_488) // } -// let allocateMe_memPtr_5 := mload(64) -// let allocateMe_newFreePtr := add(allocateMe_memPtr_5, 64) -// if or(gt(allocateMe_newFreePtr, 0xffffffffffffffff), lt(allocateMe_newFreePtr, allocateMe_memPtr_5)) // { -// revert(0, 0) -// } -// mstore(64, allocateMe_newFreePtr) -// let abi_decode_abi_decode_dst_2_5 := allocateMe_memPtr_5 -// let abi_decode_abi_decode_src_2_5 := abi_decode_src_1_5 -// if gt(add(abi_decode_src_1_5, 64), _248) -// { -// revert(0, 0) -// } -// for { -// let abi_decode_abi_decode_i_2_5 := 0 +// abi_decode_value1_61 := calldataload(add(_488, 32)) // } -// lt(abi_decode_abi_decode_i_2_5, 0x2) // { -// abi_decode_abi_decode_i_2_5 := add(abi_decode_abi_decode_i_2_5, 1) +// let abi_decode_offset_64 := calldataload(add(_488, abi_encode_pos_590)) +// let _931 := 0xffffffffffffffff +// if gt(abi_decode_offset_64, _931) +// { +// revert(_2, _2) +// } +// let _933 := add(_488, abi_decode_offset_64) +// if iszero(slt(add(_933, 0x1f), _487)) +// { +// revert(_2, _2) +// } +// let abi_decode_length_30_1038 := calldataload(_933) +// if gt(abi_decode_length_30_1038, _931) +// { +// revert(_2, _2) +// } +// let abi_decode_array_allo__561 := mul(abi_decode_length_30_1038, _1) +// let abi_decode_array_29_279_1039 := allocateMemory(add(abi_decode_array_allo__561, _1)) +// let abi_decode_dst_31_1040 := abi_decode_array_29_279_1039 +// mstore(abi_decode_array_29_279_1039, abi_decode_length_30_1038) +// let abi_decode_offset_27_281_1041 := add(_933, _1) +// abi_decode_dst_31_1040 := add(abi_decode_array_29_279_1039, _1) +// let abi_decode_src_32_1042 := abi_decode_offset_27_281_1041 +// if gt(add(add(_933, abi_decode_array_allo__561), _1), _487) +// { +// revert(_2, _2) +// } +// for { +// let abi_decode_i_33_1044 := _2 +// } +// lt(abi_decode_i_33_1044, abi_decode_length_30_1038) +// { +// abi_decode_i_33_1044 := add(abi_decode_i_33_1044, 1) +// } +// { +// mstore(abi_decode_dst_31_1040, calldataload(abi_decode_src_32_1042)) +// abi_decode_dst_31_1040 := add(abi_decode_dst_31_1040, _1) +// abi_decode_src_32_1042 := add(abi_decode_src_32_1042, _1) +// } +// abi_decode_value2 := abi_decode_array_29_279_1039 // } // { -// mstore(abi_decode_abi_decode_dst_2_5, calldataload(abi_decode_abi_decode_src_2_5)) -// abi_decode_abi_decode_dst_2_5 := add(abi_decode_abi_decode_dst_2_5, 0x20) -// abi_decode_abi_decode_src_2_5 := add(abi_decode_abi_decode_src_2_5, 0x20) +// let abi_decode_offset_65 := calldataload(add(_488, 96)) +// let _936 := 0xffffffffffffffff +// if gt(abi_decode_offset_65, _936) +// { +// revert(_2, _2) +// } +// let _938 := add(_488, abi_decode_offset_65) +// let abi_decode__489_1048 := 0x1f +// if iszero(slt(add(_938, abi_decode__489_1048), _487)) +// { +// revert(_2, _2) +// } +// let abi_decode_length_6_1050 := calldataload(_938) +// if gt(abi_decode_length_6_1050, _936) +// { +// revert(_2, _2) +// } +// let abi_decode_array_5_254_1051 := allocateMemory(add(mul(abi_decode_length_6_1050, _1), _1)) +// let abi_decode_dst_7_1052 := abi_decode_array_5_254_1051 +// mstore(abi_decode_array_5_254_1051, abi_decode_length_6_1050) +// let abi_decode_offset_3_256_1053 := add(_938, _1) +// abi_decode_dst_7_1052 := add(abi_decode_array_5_254_1051, _1) +// let abi_decode_src_8_1054 := abi_decode_offset_3_256_1053 +// if gt(add(add(_938, mul(abi_decode_length_6_1050, _924)), _1), _487) +// { +// revert(_2, _2) +// } +// for { +// let abi_decode_i_9_1058 := _2 +// } +// lt(abi_decode_i_9_1058, abi_decode_length_6_1050) +// { +// abi_decode_i_9_1058 := add(abi_decode_i_9_1058, 1) +// } +// { +// if iszero(slt(add(abi_decode_src_8_1054, abi_decode__489_1048), _487)) +// { +// revert(_2, _2) +// } +// let abi_decode_abi_decode_length_14 := 0x2 +// if _2 +// { +// revert(_2, _2) +// } +// let allocateMe_memPtr_315 := mload(abi_encode_pos_590) +// let allocateMe_newFreePtr := add(allocateMe_memPtr_315, abi_encode_pos_590) +// if or(gt(allocateMe_newFreePtr, _936), lt(allocateMe_newFreePtr, allocateMe_memPtr_315)) +// { +// revert(_2, _2) +// } +// mstore(abi_encode_pos_590, allocateMe_newFreePtr) +// let abi_decode_abi_decode_dst_15 := allocateMe_memPtr_315 +// let abi_decode_abi_decode_src_16 := abi_decode_src_8_1054 +// if gt(add(abi_decode_src_8_1054, abi_encode_pos_590), _487) +// { +// revert(_2, _2) +// } +// for { +// let abi_decode_abi_decode_i_17 := _2 +// } +// lt(abi_decode_abi_decode_i_17, abi_decode_abi_decode_length_14) +// { +// abi_decode_abi_decode_i_17 := add(abi_decode_abi_decode_i_17, 1) +// } +// { +// mstore(abi_decode_abi_decode_dst_15, calldataload(abi_decode_abi_decode_src_16)) +// abi_decode_abi_decode_dst_15 := add(abi_decode_abi_decode_dst_15, _1) +// abi_decode_abi_decode_src_16 := add(abi_decode_abi_decode_src_16, _1) +// } +// mstore(abi_decode_dst_7_1052, allocateMe_memPtr_315) +// abi_decode_dst_7_1052 := add(abi_decode_dst_7_1052, _1) +// abi_decode_src_8_1054 := add(abi_decode_src_8_1054, _924) +// } +// abi_decode_value3 := abi_decode_array_5_254_1051 // } -// mstore(abi_decode_dst_1_7, allocateMe_memPtr_5) -// abi_decode_dst_1_7 := add(abi_decode_dst_1_7, 0x20) -// abi_decode_src_1_5 := add(abi_decode_src_1_5, 0x40) +// sstore(abi_decode_value0_60, abi_decode_value1_61) +// sstore(abi_decode_value2, abi_decode_value3) +// sstore(_2, abi_encode_pos) // } -// sstore(abi_decode_value0_2_4, abi_decode_value1_2_4) -// sstore(abi_decode_array_4_1_1, abi_decode_array_1_1_1) -// sstore(0, abi_encode_pos) // function allocateMemory(size) -> memPtr // { -// let memPtr_5 := mload(64) -// memPtr := memPtr_5 -// let newFreePtr := add(memPtr_5, size) -// if or(gt(newFreePtr, 0xffffffffffffffff), lt(newFreePtr, memPtr_5)) +// let _199 := 64 +// let memPtr_315 := mload(_199) +// memPtr := memPtr_315 +// let newFreePtr := add(memPtr_315, size) +// if or(gt(newFreePtr, 0xffffffffffffffff), lt(newFreePtr, memPtr_315)) // { -// revert(0, 0) +// let _204 := 0 +// revert(_204, _204) // } -// mstore(64, newFreePtr) +// mstore(_199, newFreePtr) // } // } -- cgit v1.2.3