Merge pull request #3798 from ethereum/commutative-swap

Remove useless SWAP1 in front of commutative operations

3 files changed, 97 insertions, 1 deletions

diff --git a/Changelog.md b/Changelog.md
index b9619c27..9618dfa7 100644
--- a/Changelog.md
+++ b/Changelog.md
@@ -5,6 +5,7 @@ Features:
  * Commandline interface: Error when missing or inaccessible file detected. Suppress it with the ``--ignore-missing`` flag.
  * General: Support accessing dynamic return data in post-byzantium EVMs.
  * Interfaces: Allow overriding external functions in interfaces with public in an implementing contract.
+ * Optimizer: Remove useless ``SWAP1`` instruction preceding a commutative instruction (such as ``ADD``, ``MUL``, etc).
  * Optimizer: Optimize across ``mload`` if ``msize()`` is not used.
  * Syntax Checker: Issue warning for empty structs (or error as experimental 0.5.0 feature).
  * General: Introduce new constructor syntax using the ``constructor`` keyword as experimental 0.5.0 feature.
diff --git a/libevmasm/PeepholeOptimiser.cpp b/libevmasm/PeepholeOptimiser.cpp
index 168d1109..30646545 100644
--- a/libevmasm/PeepholeOptimiser.cpp
+++ b/libevmasm/PeepholeOptimiser.cpp
@@ -154,6 +154,25 @@ struct DoublePush: SimplePeepholeOptimizerMethod<DoublePush, 2>
 	}
 };
 
+struct CommutativeSwap: SimplePeepholeOptimizerMethod<CommutativeSwap, 2>
+{
+	static bool applySimple(AssemblyItem const& _swap, AssemblyItem const& _op, std::back_insert_iterator<AssemblyItems> _out)
+	{
+		// Remove SWAP1 if following instruction is commutative
+		if (
+			_swap.type() == Operation &&
+			_swap.instruction() == Instruction::SWAP1 &&
+			SemanticInformation::isCommutativeOperation(_op)
+		)
+		{
+			*_out = _op;
+			return true;
+		}
+		else
+			return false;
+	}
+};
+
 struct JumpToNext: SimplePeepholeOptimizerMethod<JumpToNext, 3>
 {
 	static size_t applySimple(
@@ -260,7 +279,7 @@ bool PeepholeOptimiser::optimise()
 {
 	OptimiserState state {m_items, 0, std::back_inserter(m_optimisedItems)};
 	while (state.i < m_items.size())
-		applyMethods(state, PushPop(), OpPop(), DoublePush(), DoubleSwap(), JumpToNext(), UnreachableCode(), TagConjunctions(), Identity());
+		applyMethods(state, PushPop(), OpPop(), DoublePush(), DoubleSwap(), CommutativeSwap(), JumpToNext(), UnreachableCode(), TagConjunctions(), Identity());
 	if (m_optimisedItems.size() < m_items.size() || (
 		m_optimisedItems.size() == m_items.size() && (
 			eth::bytesRequired(m_optimisedItems, 3) < eth::bytesRequired(m_items, 3) ||
diff --git a/test/libevmasm/Optimiser.cpp b/test/libevmasm/Optimiser.cpp
index 28f6b8c0..b622b4fb 100644
--- a/test/libevmasm/Optimiser.cpp
+++ b/test/libevmasm/Optimiser.cpp
@@ -858,6 +858,82 @@ BOOST_AUTO_TEST_CASE(peephole_pop_calldatasize)
 	BOOST_CHECK(items.empty());
 }
 
+BOOST_AUTO_TEST_CASE(peephole_commutative_swap1)
+{
+	vector<Instruction> ops{
+		Instruction::ADD,
+		Instruction::MUL,
+		Instruction::EQ,
+		Instruction::AND,
+		Instruction::OR,
+		Instruction::XOR
+	};
+	for (Instruction const op: ops)
+	{
+		AssemblyItems items{
+			u256(1),
+			u256(2),
+			Instruction::SWAP1,
+			op,
+			u256(4),
+			u256(5)
+		};
+		AssemblyItems expectation{
+			u256(1),
+			u256(2),
+			op,
+			u256(4),
+			u256(5)
+		};
+		PeepholeOptimiser peepOpt(items);
+		BOOST_REQUIRE(peepOpt.optimise());
+		BOOST_CHECK_EQUAL_COLLECTIONS(
+		items.begin(), items.end(),
+			expectation.begin(), expectation.end()
+		);
+	}
+}
+
+BOOST_AUTO_TEST_CASE(peephole_noncommutative_swap1)
+{
+	// NOTE: not comprehensive
+	vector<Instruction> ops{
+		Instruction::SUB,
+		Instruction::DIV,
+		Instruction::SDIV,
+		Instruction::MOD,
+		Instruction::SMOD,
+		Instruction::EXP,
+		Instruction::LT,
+		Instruction::GT
+	};
+	for (Instruction const op: ops)
+	{
+		AssemblyItems items{
+			u256(1),
+			u256(2),
+			Instruction::SWAP1,
+			op,
+			u256(4),
+			u256(5)
+		};
+		AssemblyItems expectation{
+			u256(1),
+			u256(2),
+			Instruction::SWAP1,
+			op,
+			u256(4),
+			u256(5)
+		};
+		PeepholeOptimiser peepOpt(items);
+		BOOST_REQUIRE(!peepOpt.optimise());
+		BOOST_CHECK_EQUAL_COLLECTIONS(
+		items.begin(), items.end(),
+			expectation.begin(), expectation.end()
+		);
+	}
+}
+
 BOOST_AUTO_TEST_CASE(jumpdest_removal)
 {
 	AssemblyItems items{