Add equivalent function combiner as Yul optimizer step.

10 files changed, 441 insertions, 48 deletions

diff --git a/libyul/CMakeLists.txt b/libyul/CMakeLists.txt
index ad9812bd..44af2fc3 100644
--- a/libyul/CMakeLists.txt
+++ b/libyul/CMakeLists.txt
@@ -44,6 +44,10 @@ add_library(yul
 	optimiser/DataFlowAnalyzer.h
 	optimiser/Disambiguator.cpp
 	optimiser/Disambiguator.h
+	optimiser/EquivalentFunctionDetector.cpp
+	optimiser/EquivalentFunctionDetector.h
+	optimiser/EquivalentFunctionCombiner.cpp
+	optimiser/EquivalentFunctionCombiner.h
 	optimiser/ExpressionInliner.cpp
 	optimiser/ExpressionInliner.h
 	optimiser/ExpressionJoiner.cpp
diff --git a/libyul/optimiser/CommonSubexpressionEliminator.cpp b/libyul/optimiser/CommonSubexpressionEliminator.cpp
index 8ce003e7..5f182eba 100644
--- a/libyul/optimiser/CommonSubexpressionEliminator.cpp
+++ b/libyul/optimiser/CommonSubexpressionEliminator.cpp
@@ -74,7 +74,7 @@ void CommonSubexpressionEliminator::visit(Expression& _e)
 		{
 			assertThrow(var.second, OptimizerException, "");
 			assertThrow(inScope(var.first), OptimizerException, "");
-			if (SyntacticalEqualityChecker::equal(_e, *var.second))
+			if (SyntacticallyEqual{}(_e, *var.second))
 			{
 				_e = Identifier{locationOf(_e), var.first};
 				break;
diff --git a/libyul/optimiser/EquivalentFunctionCombiner.cpp b/libyul/optimiser/EquivalentFunctionCombiner.cpp
new file mode 100644
index 00000000..939e63d2
--- /dev/null
+++ b/libyul/optimiser/EquivalentFunctionCombiner.cpp
@@ -0,0 +1,41 @@
+/*
+	This file is part of solidity.
+
+	solidity is free software: you can redistribute it and/or modify
+	it under the terms of the GNU General Public License as published by
+	the Free Software Foundation, either version 3 of the License, or
+	(at your option) any later version.
+
+	solidity is distributed in the hope that it will be useful,
+	but WITHOUT ANY WARRANTY; without even the implied warranty of
+	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+	GNU General Public License for more details.
+
+	You should have received a copy of the GNU General Public License
+	along with solidity.  If not, see <http://www.gnu.org/licenses/>.
+*/
+/**
+ * Optimiser component that combines syntactically equivalent functions.
+ */
+
+#include <libyul/optimiser/EquivalentFunctionCombiner.h>
+#include <libyul/AsmData.h>
+#include <libdevcore/CommonData.h>
+
+using namespace std;
+using namespace dev;
+using namespace yul;
+using namespace dev::solidity;
+
+void EquivalentFunctionCombiner::run(Block& _ast)
+{
+	EquivalentFunctionCombiner{EquivalentFunctionDetector::run(_ast)}(_ast);
+}
+
+void EquivalentFunctionCombiner::operator()(FunctionCall& _funCall)
+{
+	auto it = m_duplicates.find(_funCall.functionName.name);
+	if (it != m_duplicates.end())
+		_funCall.functionName.name = it->second->name;
+	ASTModifier::operator()(_funCall);
+}
diff --git a/libyul/optimiser/EquivalentFunctionCombiner.h b/libyul/optimiser/EquivalentFunctionCombiner.h
new file mode 100644
index 00000000..0c766ded
--- /dev/null
+++ b/libyul/optimiser/EquivalentFunctionCombiner.h
@@ -0,0 +1,49 @@
+/*
+	This file is part of solidity.
+
+	solidity is free software: you can redistribute it and/or modify
+	it under the terms of the GNU General Public License as published by
+	the Free Software Foundation, either version 3 of the License, or
+	(at your option) any later version.
+
+	solidity is distributed in the hope that it will be useful,
+	but WITHOUT ANY WARRANTY; without even the implied warranty of
+	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+	GNU General Public License for more details.
+
+	You should have received a copy of the GNU General Public License
+	along with solidity.  If not, see <http://www.gnu.org/licenses/>.
+*/
+/**
+ * Optimiser component that combines syntactically equivalent functions.
+ */
+#pragma once
+
+#include <libyul/optimiser/ASTWalker.h>
+#include <libyul/optimiser/EquivalentFunctionDetector.h>
+#include <libyul/AsmDataForward.h>
+
+namespace yul
+{
+
+/**
+ * Optimiser component that detects syntactically equivalent functions and replaces all calls to any of them by calls
+ * to one particular of them.
+ *
+ * Prerequisite: Disambiguator, Function Hoister
+ */
+class EquivalentFunctionCombiner: public ASTModifier
+{
+public:
+	static void run(Block& _ast);
+
+	using ASTModifier::operator();
+	void operator()(FunctionCall& _funCall) override;
+
+private:
+	EquivalentFunctionCombiner(std::map<YulString, FunctionDefinition const*> _duplicates): m_duplicates(std::move(_duplicates)) {}
+	std::map<YulString, FunctionDefinition const*> m_duplicates;
+};
+
+
+}
diff --git a/libyul/optimiser/EquivalentFunctionDetector.cpp b/libyul/optimiser/EquivalentFunctionDetector.cpp
new file mode 100644
index 00000000..d3a697bd
--- /dev/null
+++ b/libyul/optimiser/EquivalentFunctionDetector.cpp
@@ -0,0 +1,63 @@
+/*
+	This file is part of solidity.
+
+	solidity is free software: you can redistribute it and/or modify
+	it under the terms of the GNU General Public License as published by
+	the Free Software Foundation, either version 3 of the License, or
+	(at your option) any later version.
+
+	solidity is distributed in the hope that it will be useful,
+	but WITHOUT ANY WARRANTY; without even the implied warranty of
+	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+	GNU General Public License for more details.
+
+	You should have received a copy of the GNU General Public License
+	along with solidity.  If not, see <http://www.gnu.org/licenses/>.
+*/
+/**
+ * Optimiser component that combines syntactically equivalent functions.
+ */
+
+#include <libyul/optimiser/EquivalentFunctionDetector.h>
+#include <libyul/optimiser/SyntacticalEquality.h>
+
+#include <libyul/AsmData.h>
+#include <libyul/optimiser/Metrics.h>
+
+using namespace std;
+using namespace dev;
+using namespace yul;
+using namespace solidity;
+
+void EquivalentFunctionDetector::operator()(FunctionDefinition const& _fun)
+{
+	RoughHeuristic heuristic(_fun);
+	auto& candidates = m_candidates[heuristic];
+	for (auto const& candidate: candidates)
+		if (SyntacticallyEqual{}.statementEqual(_fun, *candidate))
+		{
+			m_duplicates[_fun.name] = candidate;
+			return;
+		}
+	candidates.push_back(&_fun);
+}
+
+bool EquivalentFunctionDetector::RoughHeuristic::operator<(EquivalentFunctionDetector::RoughHeuristic const& _rhs) const
+{
+	if (
+		std::make_tuple(m_fun.parameters.size(), m_fun.returnVariables.size()) ==
+		std::make_tuple(_rhs.m_fun.parameters.size(), _rhs.m_fun.returnVariables.size())
+	)
+		return codeSize() < _rhs.codeSize();
+	else
+		return
+			std::make_tuple(m_fun.parameters.size(), m_fun.returnVariables.size()) <
+			std::make_tuple(_rhs.m_fun.parameters.size(), _rhs.m_fun.returnVariables.size());
+}
+
+size_t EquivalentFunctionDetector::RoughHeuristic::codeSize() const
+{
+	if (!m_codeSize)
+		m_codeSize = CodeSize::codeSize(m_fun.body);
+	return *m_codeSize;
+}
diff --git a/libyul/optimiser/EquivalentFunctionDetector.h b/libyul/optimiser/EquivalentFunctionDetector.h
new file mode 100644
index 00000000..329fd385
--- /dev/null
+++ b/libyul/optimiser/EquivalentFunctionDetector.h
@@ -0,0 +1,71 @@
+/*
+	This file is part of solidity.
+
+	solidity is free software: you can redistribute it and/or modify
+	it under the terms of the GNU General Public License as published by
+	the Free Software Foundation, either version 3 of the License, or
+	(at your option) any later version.
+
+	solidity is distributed in the hope that it will be useful,
+	but WITHOUT ANY WARRANTY; without even the implied warranty of
+	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+	GNU General Public License for more details.
+
+	You should have received a copy of the GNU General Public License
+	along with solidity.  If not, see <http://www.gnu.org/licenses/>.
+*/
+/**
+ * Optimiser component that combines syntactically equivalent functions.
+ */
+#pragma once
+
+#include <libyul/optimiser/ASTWalker.h>
+#include <libyul/AsmDataForward.h>
+
+namespace yul
+{
+
+/**
+ * Optimiser component that detects syntactically equivalent functions.
+ *
+ * Prerequisite: Disambiguator
+ */
+class EquivalentFunctionDetector: public ASTWalker
+{
+public:
+	static std::map<YulString, FunctionDefinition const*> run(Block& _block)
+	{
+		EquivalentFunctionDetector detector{};
+		detector(_block);
+		return std::move(detector.m_duplicates);
+	}
+
+	using ASTWalker::operator();
+	void operator()(FunctionDefinition const& _fun) override;
+
+private:
+	EquivalentFunctionDetector() = default;
+	/**
+	 * Fast heuristic to detect distinct, resp. potentially equal functions.
+	 *
+	 * Defines a partial order on function definitions. If two functions
+	 * are comparable (one is "less" than the other), they are distinct.
+	 * If not (neither is "less" than the other), they are *potentially* equal.
+	 */
+	class RoughHeuristic
+	{
+	public:
+		RoughHeuristic(FunctionDefinition const& _fun): m_fun(_fun) {}
+		bool operator<(RoughHeuristic const& _rhs) const;
+	private:
+		std::size_t codeSize() const;
+		FunctionDefinition const& m_fun;
+		mutable boost::optional<std::size_t> m_codeSize;
+		// In case the heuristic doesn't turn out to be good enough, we might want to define a hash function for code blocks.
+	};
+	std::map<RoughHeuristic, std::vector<FunctionDefinition const*>> m_candidates;
+	std::map<YulString, FunctionDefinition const*> m_duplicates;
+};
+
+
+}
diff --git a/libyul/optimiser/SimplificationRules.cpp b/libyul/optimiser/SimplificationRules.cpp
index 037dad97..1b620b64 100644
--- a/libyul/optimiser/SimplificationRules.cpp
+++ b/libyul/optimiser/SimplificationRules.cpp
@@ -171,7 +171,7 @@ bool Pattern::matches(
 			Expression const* firstMatch = (*m_matchGroups)[m_matchGroup];
 			assertThrow(firstMatch, OptimizerException, "Match set but to null.");
 			return
-				SyntacticalEqualityChecker::equal(*firstMatch, _expr) &&
+				SyntacticallyEqual{}(*firstMatch, _expr) &&
 				MovableChecker(_dialect, _expr).movable();
 		}
 		else if (m_kind == PatternKind::Any)
diff --git a/libyul/optimiser/Suite.cpp b/libyul/optimiser/Suite.cpp
index 48914cf8..38c0bf49 100644
--- a/libyul/optimiser/Suite.cpp
+++ b/libyul/optimiser/Suite.cpp
@@ -25,6 +25,7 @@
 #include <libyul/optimiser/BlockFlattener.h>
 #include <libyul/optimiser/FunctionGrouper.h>
 #include <libyul/optimiser/FunctionHoister.h>
+#include <libyul/optimiser/EquivalentFunctionCombiner.h>
 #include <libyul/optimiser/ExpressionSplitter.h>
 #include <libyul/optimiser/ExpressionJoiner.h>
 #include <libyul/optimiser/ExpressionInliner.h>
@@ -62,6 +63,8 @@ void OptimiserSuite::run(
 	(FunctionHoister{})(ast);
 	(BlockFlattener{})(ast);
 	(FunctionGrouper{})(ast);
+	EquivalentFunctionCombiner::run(ast);
+	UnusedPruner::runUntilStabilised(_dialect, ast, reservedIdentifiers);
 	(ForLoopInitRewriter{})(ast);
 	(BlockFlattener{})(ast);
 	StructuralSimplifier{_dialect}(ast);
@@ -101,6 +104,7 @@ void OptimiserSuite::run(
 		CommonSubexpressionEliminator{_dialect}(ast);
 
 		(FunctionGrouper{})(ast);
+		EquivalentFunctionCombiner::run(ast);
 		FullInliner{ast, dispenser}.run();
 
 		SSATransform::run(ast, dispenser);
diff --git a/libyul/optimiser/SyntacticalEquality.cpp b/libyul/optimiser/SyntacticalEquality.cpp
index 99ce06e5..ba8cc793 100644
--- a/libyul/optimiser/SyntacticalEquality.cpp
+++ b/libyul/optimiser/SyntacticalEquality.cpp
@@ -22,6 +22,7 @@
 
 #include <libyul/Exceptions.h>
 #include <libyul/AsmData.h>
+#include <libyul/Utilities.h>
 
 #include <libdevcore/CommonData.h>
 
@@ -29,48 +30,166 @@ using namespace std;
 using namespace dev;
 using namespace yul;
 
-bool SyntacticalEqualityChecker::equal(Expression const& _e1, Expression const& _e2)
+bool SyntacticallyEqual::operator()(Expression const& _lhs, Expression const& _rhs)
 {
-	if (_e1.type() != _e2.type())
+	return boost::apply_visitor([this](auto&& _lhsExpr, auto&& _rhsExpr) -> bool {
+		// ``this->`` is redundant, but required to work around a bug present in gcc 6.x.
+		return this->expressionEqual(_lhsExpr, _rhsExpr);
+	}, _lhs, _rhs);
+}
+
+bool SyntacticallyEqual::operator()(Statement const& _lhs, Statement const& _rhs)
+{
+	return boost::apply_visitor([this](auto&& _lhsStmt, auto&& _rhsStmt) -> bool {
+		// ``this->`` is redundant, but required to work around a bug present in gcc 6.x.
+		return this->statementEqual(_lhsStmt, _rhsStmt);
+	}, _lhs, _rhs);
+}
+
+bool SyntacticallyEqual::expressionEqual(FunctionalInstruction const& _lhs, FunctionalInstruction const& _rhs)
+{
+	return
+		_lhs.instruction == _rhs.instruction &&
+		containerEqual(_lhs.arguments, _rhs.arguments, [this](Expression const& _lhsExpr, Expression const& _rhsExpr) -> bool {
+			return (*this)(_lhsExpr, _rhsExpr);
+		});
+}
+
+bool SyntacticallyEqual::expressionEqual(FunctionCall const& _lhs, FunctionCall const& _rhs)
+{
+	return
+		expressionEqual(_lhs.functionName, _rhs.functionName) &&
+		containerEqual(_lhs.arguments, _rhs.arguments, [this](Expression const& _lhsExpr, Expression const& _rhsExpr) -> bool {
+			return (*this)(_lhsExpr, _rhsExpr);
+		});
+}
+
+bool SyntacticallyEqual::expressionEqual(Identifier const& _lhs, Identifier const& _rhs)
+{
+	auto lhsIt = m_identifiersLHS.find(_lhs.name);
+	auto rhsIt = m_identifiersRHS.find(_rhs.name);
+	return
+		(lhsIt == m_identifiersLHS.end() && rhsIt == m_identifiersRHS.end() && _lhs.name == _rhs.name) ||
+		(lhsIt != m_identifiersLHS.end() && rhsIt != m_identifiersRHS.end() && lhsIt->second == rhsIt->second);
+}
+bool SyntacticallyEqual::expressionEqual(Literal const& _lhs, Literal const& _rhs)
+{
+	if (_lhs.kind != _rhs.kind || _lhs.type != _rhs.type)
 		return false;
-	// TODO This somehow calls strcmp - WHERE?
-
-	// TODO This should be replaced by some kind of AST walker as soon as it gets
-	// more complex.
-	if (_e1.type() == typeid(FunctionalInstruction))
-	{
-		auto const& e1 = boost::get<FunctionalInstruction>(_e1);
-		auto const& e2 = boost::get<FunctionalInstruction>(_e2);
-		return
-			e1.instruction == e2.instruction &&
-			equalVector(e1.arguments, e2.arguments);
-	}
-	else if (_e1.type() == typeid(FunctionCall))
-	{
-		auto const& e1 = boost::get<FunctionCall>(_e1);
-		auto const& e2 = boost::get<FunctionCall>(_e2);
-		return
-			equal(e1.functionName, e2.functionName) &&
-			equalVector(e1.arguments, e2.arguments);
-	}
-	else if (_e1.type() == typeid(Identifier))
-		return boost::get<Identifier>(_e1).name == boost::get<Identifier>(_e2).name;
-	else if (_e1.type() == typeid(Literal))
-	{
-		auto const& e1 = boost::get<Literal>(_e1);
-		auto const& e2 = boost::get<Literal>(_e2);
-		return e1.kind == e2.kind && e1.value == e2.value && e1.type == e2.type;
-	}
+	if (_lhs.kind == LiteralKind::Number)
+		return valueOfNumberLiteral(_lhs) == valueOfNumberLiteral(_rhs);
 	else
-	{
-		assertThrow(false, OptimizerException, "Invalid expression");
-	}
-	return false;
+		return _lhs.value == _rhs.value;
 }
 
-bool SyntacticalEqualityChecker::equalVector(vector<Expression> const& _e1, vector<Expression> const& _e2)
+bool SyntacticallyEqual::statementEqual(ExpressionStatement const& _lhs, ExpressionStatement const& _rhs)
 {
-	return _e1.size() == _e2.size() &&
-		std::equal(begin(_e1), end(_e1), begin(_e2), SyntacticalEqualityChecker::equal);
+	return (*this)(_lhs.expression, _rhs.expression);
+}
+bool SyntacticallyEqual::statementEqual(Assignment const& _lhs, Assignment const& _rhs)
+{
+	return containerEqual(
+		_lhs.variableNames,
+		_rhs.variableNames,
+		[this](Identifier const& _lhsVarName, Identifier const& _rhsVarName) -> bool {
+			return this->expressionEqual(_lhsVarName, _rhsVarName);
+		}
+	) && (*this)(*_lhs.value, *_rhs.value);
+}
+
+bool SyntacticallyEqual::statementEqual(VariableDeclaration const& _lhs, VariableDeclaration const& _rhs)
+{
+	// first visit expression, then variable declarations
+	if (!compareSharedPtr<Expression, &SyntacticallyEqual::operator()>(_lhs.value, _rhs.value))
+		return false;
+	return containerEqual(_lhs.variables, _rhs.variables, [this](TypedName const& _lhsVarName, TypedName const& _rhsVarName) -> bool {
+		return this->visitDeclaration(_lhsVarName, _rhsVarName);
+	});
+}
 
+bool SyntacticallyEqual::statementEqual(FunctionDefinition const& _lhs, FunctionDefinition const& _rhs)
+{
+	auto compare = [this](TypedName const& _lhsVarName, TypedName const& _rhsVarName) -> bool {
+		return this->visitDeclaration(_lhsVarName, _rhsVarName);
+	};
+	// first visit parameter declarations, then body
+	if (!containerEqual(_lhs.parameters, _rhs.parameters, compare))
+		return false;
+	if (!containerEqual(_lhs.returnVariables, _rhs.returnVariables, compare))
+		return false;
+	return statementEqual(_lhs.body, _rhs.body);
+}
+
+bool SyntacticallyEqual::statementEqual(If const& _lhs, If const& _rhs)
+{
+	return
+		compareSharedPtr<Expression, &SyntacticallyEqual::operator()>(_lhs.condition, _rhs.condition) &&
+		statementEqual(_lhs.body, _rhs.body);
+}
+
+bool SyntacticallyEqual::statementEqual(Switch const& _lhs, Switch const& _rhs)
+{
+	static auto const sortCasesByValue = [](Case const* _lhsCase, Case const* _rhsCase) -> bool {
+		return Less<Literal*>{}(_lhsCase->value.get(), _rhsCase->value.get());
+	};
+	std::set<Case const*, decltype(sortCasesByValue)> lhsCases(sortCasesByValue);
+	std::set<Case const*, decltype(sortCasesByValue)> rhsCases(sortCasesByValue);
+	for (auto const& lhsCase: _lhs.cases)
+		lhsCases.insert(&lhsCase);
+	for (auto const& rhsCase: _rhs.cases)
+		rhsCases.insert(&rhsCase);
+	return
+		compareSharedPtr<Expression, &SyntacticallyEqual::operator()>(_lhs.expression, _rhs.expression) &&
+		containerEqual(lhsCases, rhsCases, [this](Case const* _lhsCase, Case const* _rhsCase) -> bool {
+			return this->switchCaseEqual(*_lhsCase, *_rhsCase);
+		});
+}
+
+
+bool SyntacticallyEqual::switchCaseEqual(Case const& _lhs, Case const& _rhs)
+{
+	return
+		compareSharedPtr<Literal, &SyntacticallyEqual::expressionEqual>(_lhs.value, _rhs.value) &&
+		statementEqual(_lhs.body, _rhs.body);
+}
+
+bool SyntacticallyEqual::statementEqual(ForLoop const& _lhs, ForLoop const& _rhs)
+{
+	return
+		statementEqual(_lhs.pre, _rhs.pre) &&
+		compareSharedPtr<Expression, &SyntacticallyEqual::operator()>(_lhs.condition, _rhs.condition) &&
+		statementEqual(_lhs.body, _rhs.body) &&
+		statementEqual(_lhs.post, _rhs.post);
+}
+
+bool SyntacticallyEqual::statementEqual(Instruction const&, Instruction const&)
+{
+	assertThrow(false, OptimizerException, "");
+}
+
+bool SyntacticallyEqual::statementEqual(Label const&, Label const&)
+{
+	assertThrow(false, OptimizerException, "");
+}
+
+bool SyntacticallyEqual::statementEqual(StackAssignment const&, StackAssignment const&)
+{
+	assertThrow(false, OptimizerException, "");
+}
+
+bool SyntacticallyEqual::statementEqual(Block const& _lhs, Block const& _rhs)
+{
+	return containerEqual(_lhs.statements, _rhs.statements, [this](Statement const& _lhsStmt, Statement const& _rhsStmt) -> bool {
+		return (*this)(_lhsStmt, _rhsStmt);
+	});
+}
+
+bool SyntacticallyEqual::visitDeclaration(TypedName const& _lhs, TypedName const& _rhs)
+{
+	if (_lhs.type != _rhs.type)
+		return false;
+	std::size_t id = m_idsUsed++;
+	m_identifiersLHS[_lhs.name] = id;
+	m_identifiersRHS[_rhs.name] = id;
+	return true;
 }
diff --git a/libyul/optimiser/SyntacticalEquality.h b/libyul/optimiser/SyntacticalEquality.h
index 63c51b4f..d4630d95 100644
--- a/libyul/optimiser/SyntacticalEquality.h
+++ b/libyul/optimiser/SyntacticalEquality.h
@@ -21,27 +21,69 @@
 #pragma once
 
 #include <libyul/AsmDataForward.h>
+#include <libyul/YulString.h>
 
-#include <vector>
+#include <map>
+#include <type_traits>
 
 namespace yul
 {
 
+
 /**
  * Component that can compare ASTs for equality on a syntactic basis.
- * Ignores source locations but requires exact matches otherwise.
+ * Ignores source locations and allows for different variable names but requires exact matches otherwise.
  *
- * TODO: Only implemented for Expressions for now.
- * A future version might also recognize renamed variables and thus could be used to
- * remove duplicate functions.
+ * Prerequisite: Disambiguator (unless only expressions are compared)
  */
-class SyntacticalEqualityChecker
+class SyntacticallyEqual
 {
 public:
-	static bool equal(Expression const& _e1, Expression const& _e2);
+	bool operator()(Expression const& _lhs, Expression const& _rhs);
+	bool operator()(Statement const& _lhs, Statement const& _rhs);
+
+	bool expressionEqual(FunctionalInstruction const& _lhs, FunctionalInstruction const& _rhs);
+	bool expressionEqual(FunctionCall const& _lhs, FunctionCall const& _rhs);
+	bool expressionEqual(Identifier const& _lhs, Identifier const& _rhs);
+	bool expressionEqual(Literal const& _lhs, Literal const& _rhs);
+
+	bool statementEqual(ExpressionStatement const& _lhs, ExpressionStatement const& _rhs);
+	bool statementEqual(Assignment const& _lhs, Assignment const& _rhs);
+	bool statementEqual(VariableDeclaration const& _lhs, VariableDeclaration const& _rhs);
+	bool statementEqual(FunctionDefinition const& _lhs, FunctionDefinition const& _rhs);
+	bool statementEqual(If const& _lhs, If const& _rhs);
+	bool statementEqual(Switch const& _lhs, Switch const& _rhs);
+	bool switchCaseEqual(Case const& _lhs, Case const& _rhs);
+	bool statementEqual(ForLoop const& _lhs, ForLoop const& _rhs);
+	bool statementEqual(Block const& _lhs, Block const& _rhs);
+private:
+	bool statementEqual(Instruction const& _lhs, Instruction const& _rhs);
+	bool statementEqual(Label const& _lhs, Label const& _rhs);
+	bool statementEqual(StackAssignment const& _lhs, StackAssignment const& _rhs);
+
+	bool visitDeclaration(TypedName const& _lhs, TypedName const& _rhs);
+
+	template<typename U, typename V>
+	bool expressionEqual(U const&, V const&, std::enable_if_t<!std::is_same<U, V>::value>* = nullptr)
+	{
+		return false;
+	}
+
+	template<typename U, typename V>
+	bool statementEqual(U const&, V const&, std::enable_if_t<!std::is_same<U, V>::value>* = nullptr)
+	{
+		return false;
+	}
+
+	template<typename T, bool (SyntacticallyEqual::*CompareMember)(T const&, T const&)>
+	bool compareSharedPtr(std::shared_ptr<T> const& _lhs, std::shared_ptr<T> const& _rhs)
+	{
+		return (_lhs == _rhs) || (_lhs && _rhs && (this->*CompareMember)(*_lhs, *_rhs));
+	}
 
-protected:
-	static bool equalVector(std::vector<Expression> const& _e1, std::vector<Expression> const& _e2);
+	std::size_t m_idsUsed = 0;
+	std::map<YulString, std::size_t> m_identifiersLHS;
+	std::map<YulString, std::size_t> m_identifiersRHS;
 };
 
 }