Stabilize SSAReverser.

8 files changed, 55 insertions, 11 deletions

diff --git a/libyul/optimiser/Metrics.cpp b/libyul/optimiser/Metrics.cpp
index df919682..e13940aa 100644
--- a/libyul/optimiser/Metrics.cpp
+++ b/libyul/optimiser/Metrics.cpp
@@ -134,3 +134,15 @@ void CodeCost::visit(Expression const& _expression)
 	++m_cost;
 	ASTWalker::visit(_expression);
 }
+
+void AssignmentCounter::operator()(Assignment const& _assignment)
+{
+	for (auto const& variable: _assignment.variableNames)
+		++m_assignmentCounters[variable.name];
+}
+
+size_t AssignmentCounter::assignmentCount(YulString _name) const
+{
+	auto it = m_assignmentCounters.find(_name);
+	return (it == m_assignmentCounters.end()) ? 0 : it->second;
+}
diff --git a/libyul/optimiser/Metrics.h b/libyul/optimiser/Metrics.h
index 03e1b62a..5364646e 100644
--- a/libyul/optimiser/Metrics.h
+++ b/libyul/optimiser/Metrics.h
@@ -77,4 +77,18 @@ private:
 	size_t m_cost = 0;
 };
 
+/**
+ * Counts the number of assignments to every variable.
+ * Only works after running the Disambiguator.
+ */
+class AssignmentCounter: public ASTWalker
+{
+public:
+	using ASTWalker::operator();
+	void operator()(Assignment const& _assignment) override;
+	std::size_t assignmentCount(YulString _name) const;
+private:
+	std::map<YulString, size_t> m_assignmentCounters;
+};
+
 }
diff --git a/libyul/optimiser/SSAReverser.cpp b/libyul/optimiser/SSAReverser.cpp
index 2cfa3d58..6548ebb5 100644
--- a/libyul/optimiser/SSAReverser.cpp
+++ b/libyul/optimiser/SSAReverser.cpp
@@ -15,6 +15,7 @@
 	along with solidity.  If not, see <http://www.gnu.org/licenses/>.
 */
 #include <libyul/optimiser/SSAReverser.h>
+#include <libyul/optimiser/Metrics.h>
 #include <libyul/AsmData.h>
 #include <libdevcore/CommonData.h>
 
@@ -22,6 +23,13 @@ using namespace std;
 using namespace dev;
 using namespace yul;
 
+void SSAReverser::run(Block& _block)
+{
+	AssignmentCounter assignmentCounter;
+	assignmentCounter(_block);
+	SSAReverser{assignmentCounter}(_block);
+}
+
 void SSAReverser::operator()(Block& _block)
 {
 	walkVector(_block.statements);
@@ -47,7 +55,7 @@ void SSAReverser::operator()(Block& _block)
 					assignment->variableNames.size() == 1 &&
 					identifier &&
 					identifier->name == varDecl->variables.front().name
-					)
+				)
 				{
 					vector<Statement> result;
 					result.emplace_back(Assignment{
@@ -75,7 +83,10 @@ void SSAReverser::operator()(Block& _block)
 				if (
 					varDecl2->variables.size() == 1 &&
 					identifier &&
-					identifier->name == varDecl->variables.front().name
+					identifier->name == varDecl->variables.front().name && (
+						m_assignmentCounter.assignmentCount(varDecl2->variables.front().name) >
+						m_assignmentCounter.assignmentCount(varDecl->variables.front().name)
+				   )
 				)
 				{
 					vector<Statement> result;
diff --git a/libyul/optimiser/SSAReverser.h b/libyul/optimiser/SSAReverser.h
index 34b61647..67abeb56 100644
--- a/libyul/optimiser/SSAReverser.h
+++ b/libyul/optimiser/SSAReverser.h
@@ -21,6 +21,8 @@
 namespace yul
 {
 
+class AssignmentCounter;
+
 /**
  * Reverses the SSA transformation.
  *
@@ -54,7 +56,7 @@ namespace yul
  * 	After that the CSE can replace references of a_1 by references to a,
  * 	after which the unused pruner can remove the declaration of a_1.
  *
- * 	Prerequisites: None
+ * 	Prerequisites: Disambiguator
  *
  */
 class SSAReverser: public ASTModifier
@@ -62,6 +64,11 @@ class SSAReverser: public ASTModifier
 public:
 	using ASTModifier::operator();
 	void operator()(Block& _block) override;
+
+	static void run(Block& _block);
+private:
+	SSAReverser(AssignmentCounter const& _assignmentCounter): m_assignmentCounter(_assignmentCounter) {}
+	AssignmentCounter const& m_assignmentCounter;
 };
 
 }
diff --git a/libyul/optimiser/Suite.cpp b/libyul/optimiser/Suite.cpp
index 63931554..8cf6e104 100644
--- a/libyul/optimiser/Suite.cpp
+++ b/libyul/optimiser/Suite.cpp
@@ -90,7 +90,7 @@ void OptimiserSuite::run(
 		CommonSubexpressionEliminator{_dialect}(ast);
 		UnusedPruner::runUntilStabilised(_dialect, ast, reservedIdentifiers);
 
-		SSAReverser{}(ast);
+		SSAReverser::run(ast);
 		CommonSubexpressionEliminator{_dialect}(ast);
 		UnusedPruner::runUntilStabilised(_dialect, ast, reservedIdentifiers);
 
@@ -130,7 +130,7 @@ void OptimiserSuite::run(
 	ExpressionJoiner::run(ast);
 	UnusedPruner::runUntilStabilised(_dialect, ast);
 
-	SSAReverser{}(ast);
+	SSAReverser::run(ast);
 	CommonSubexpressionEliminator{_dialect}(ast);
 	UnusedPruner::runUntilStabilised(_dialect, ast, reservedIdentifiers);
 
diff --git a/test/libyul/YulOptimizerTest.cpp b/test/libyul/YulOptimizerTest.cpp
index 914e0d6a..306721a0 100644
--- a/test/libyul/YulOptimizerTest.cpp
+++ b/test/libyul/YulOptimizerTest.cpp
@@ -227,7 +227,7 @@ bool YulOptimizerTest::run(ostream& _stream, string const& _linePrefix, bool con
 	else if (m_optimizerStep == "ssaReverser")
 	{
 		disambiguate();
-		SSAReverser{}(*m_ast);
+		SSAReverser::run(*m_ast);
 	}
 	else if (m_optimizerStep == "ssaAndBack")
 	{
@@ -237,7 +237,7 @@ bool YulOptimizerTest::run(ostream& _stream, string const& _linePrefix, bool con
 		SSATransform::run(*m_ast, nameDispenser);
 		RedundantAssignEliminator::run(*m_dialect, *m_ast);
 		// reverse SSA
-		SSAReverser{}(*m_ast);
+		SSAReverser::run(*m_ast);
 		CommonSubexpressionEliminator{*m_dialect}(*m_ast);
 		UnusedPruner::runUntilStabilised(*m_dialect, *m_ast);
 	}
diff --git a/test/libyul/yulOptimizerTests/ssaAndBack/two_vars.yul b/test/libyul/yulOptimizerTests/ssaAndBack/two_vars.yul
index 85325fb9..9f2a046e 100644
--- a/test/libyul/yulOptimizerTests/ssaAndBack/two_vars.yul
+++ b/test/libyul/yulOptimizerTests/ssaAndBack/two_vars.yul
@@ -10,9 +10,9 @@
 // ----
 // ssaAndBack
 // {
-//     let a := mload(0)
-//     let b := mload(a)
-//     let a_3 := mload(b)
+//     let a_1 := mload(0)
+//     let b_2 := mload(a_1)
+//     let a_3 := mload(b_2)
 //     let b_4 := mload(a_3)
 //     let a_5 := mload(b_4)
 //     let b_6 := mload(a_5)
diff --git a/test/tools/yulopti.cpp b/test/tools/yulopti.cpp
index 07ebfc7d..7203ef54 100644
--- a/test/tools/yulopti.cpp
+++ b/test/tools/yulopti.cpp
@@ -190,7 +190,7 @@ public:
 				EquivalentFunctionCombiner::run(*m_ast);
 				break;
 			case 'V':
-				SSAReverser{}(*m_ast);
+				SSAReverser::run(*m_ast);
 				break;
 			default:
 				cout << "Unknown option." << endl;