From faa7b61d763824f482b513b20bf6a2c38807480e Mon Sep 17 00:00:00 2001 From: chriseth Date: Mon, 29 Oct 2018 15:12:31 +0100 Subject: Use map join algorithm for performance. --- libyul/optimiser/RedundantAssignEliminator.cpp | 41 +++++++++++++++++++++----- libyul/optimiser/RedundantAssignEliminator.h | 4 +-- 2 files changed, 35 insertions(+), 10 deletions(-) (limited to 'libyul') diff --git a/libyul/optimiser/RedundantAssignEliminator.cpp b/libyul/optimiser/RedundantAssignEliminator.cpp index 775b7673..df6c4e4e 100644 --- a/libyul/optimiser/RedundantAssignEliminator.cpp +++ b/libyul/optimiser/RedundantAssignEliminator.cpp @@ -163,17 +163,42 @@ void RedundantAssignEliminator::run(Block& _ast) remover(_ast); } -void RedundantAssignEliminator::join(RedundantAssignEliminator& _other) +template +void joinMap(std::map& _a, std::map&& _b, F _conflictSolver) { - for (auto& var: _other.m_assignments) - if (m_assignments.count(var.first)) + // TODO Perhaps it is better to just create a sorted list + // and then use insert(begin, end) + + auto ita = _a.begin(); + auto aend = _a.end(); + auto itb = _b.begin(); + auto bend = _b.end(); + + for (; itb != bend; ++ita) + { + if (ita == aend) + ita = _a.insert(ita, std::move(*itb++)); + else if (ita->first < itb->first) + continue; + else if (itb->first < ita->first) + ita = _a.insert(ita, std::move(*itb++)); + else { - map& assignmentsHere = m_assignments[var.first]; - for (auto& assignment: var.second) - assignmentsHere[assignment.first].join(assignment.second); + _conflictSolver(ita->second, std::move(itb->second)); + ++itb; } - else - m_assignments[var.first] = std::move(var.second); + } +} + +void RedundantAssignEliminator::join(RedundantAssignEliminator& _other) +{ + joinMap(m_assignments, std::move(_other.m_assignments), []( + map& _assignmentHere, + map&& _assignmentThere + ) + { + return joinMap(_assignmentHere, std::move(_assignmentThere), State::join); + }); } void RedundantAssignEliminator::changeUndecidedTo(YulString _variable, RedundantAssignEliminator::State _newState) diff --git a/libyul/optimiser/RedundantAssignEliminator.h b/libyul/optimiser/RedundantAssignEliminator.h index 805a1f63..a9c6a8f7 100644 --- a/libyul/optimiser/RedundantAssignEliminator.h +++ b/libyul/optimiser/RedundantAssignEliminator.h @@ -127,10 +127,10 @@ private: State(Value _value = Undecided): m_value(_value) {} inline bool operator==(State _other) const { return m_value == _other.m_value; } inline bool operator!=(State _other) const { return !operator==(_other); } - inline void join(State const& _other) + static inline void join(State& _a, State const& _b) { // Using "max" works here because of the order of the values in the enum. - m_value = Value(std::max(int(_other.m_value), int(m_value))); + _a.m_value = Value(std::max(int(_a.m_value), int(_b.m_value))); } private: Value m_value = Undecided; -- cgit v1.2.3 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 ++++++ 2 files changed, 29 insertions(+), 10 deletions(-) (limited to 'libyul') 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 -- cgit v1.2.3