Merge pull request #3822 from ethereum/swap-comparison

Replace comparison operators with opposites if preceded by SWAP1

4 files changed, 110 insertions, 6 deletions

diff --git a/Changelog.md b/Changelog.md
index 0db5df96..e208437e 100644
--- a/Changelog.md
+++ b/Changelog.md
@@ -7,6 +7,7 @@ Features:
  * 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: Replace comparison operators (``LT``, ``GT``, etc) with opposites if preceded by ``SWAP1``, e.g. ``SWAP1 LT`` is replaced with ``GT``.
  * 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 30646545..8a39de24 100644
--- a/libevmasm/PeepholeOptimiser.cpp
+++ b/libevmasm/PeepholeOptimiser.cpp
@@ -173,6 +173,32 @@ struct CommutativeSwap: SimplePeepholeOptimizerMethod<CommutativeSwap, 2>
 	}
 };
 
+struct SwapComparison: SimplePeepholeOptimizerMethod<SwapComparison, 2>
+{
+	static bool applySimple(AssemblyItem const& _swap, AssemblyItem const& _op, std::back_insert_iterator<AssemblyItems> _out)
+	{
+		map<Instruction, Instruction> swappableOps{
+			{ Instruction::LT, Instruction::GT },
+			{ Instruction::GT, Instruction::LT },
+			{ Instruction::SLT, Instruction::SGT },
+			{ Instruction::SGT, Instruction::SLT }
+		};
+
+		if (
+			_swap.type() == Operation &&
+			_swap.instruction() == Instruction::SWAP1 &&
+			_op.type() == Operation &&
+			swappableOps.count(_op.instruction())
+		)
+		{
+			*_out = swappableOps.at(_op.instruction());
+			return true;
+		}
+		else
+			return false;
+	}
+};
+
 struct JumpToNext: SimplePeepholeOptimizerMethod<JumpToNext, 3>
 {
 	static size_t applySimple(
@@ -279,7 +305,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(), CommutativeSwap(), JumpToNext(), UnreachableCode(), TagConjunctions(), Identity());
+		applyMethods(state, PushPop(), OpPop(), DoublePush(), DoubleSwap(), CommutativeSwap(), SwapComparison(), 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 b622b4fb..089be45d 100644
--- a/test/libevmasm/Optimiser.cpp
+++ b/test/libevmasm/Optimiser.cpp
@@ -888,7 +888,7 @@ BOOST_AUTO_TEST_CASE(peephole_commutative_swap1)
 		PeepholeOptimiser peepOpt(items);
 		BOOST_REQUIRE(peepOpt.optimise());
 		BOOST_CHECK_EQUAL_COLLECTIONS(
-		items.begin(), items.end(),
+			items.begin(), items.end(),
 			expectation.begin(), expectation.end()
 		);
 	}
@@ -903,9 +903,7 @@ BOOST_AUTO_TEST_CASE(peephole_noncommutative_swap1)
 		Instruction::SDIV,
 		Instruction::MOD,
 		Instruction::SMOD,
-		Instruction::EXP,
-		Instruction::LT,
-		Instruction::GT
+		Instruction::EXP
 	};
 	for (Instruction const op: ops)
 	{
@@ -928,7 +926,42 @@ BOOST_AUTO_TEST_CASE(peephole_noncommutative_swap1)
 		PeepholeOptimiser peepOpt(items);
 		BOOST_REQUIRE(!peepOpt.optimise());
 		BOOST_CHECK_EQUAL_COLLECTIONS(
-		items.begin(), items.end(),
+			items.begin(), items.end(),
+			expectation.begin(), expectation.end()
+		);
+	}
+}
+
+BOOST_AUTO_TEST_CASE(peephole_swap_comparison)
+{
+	map<Instruction, Instruction> swappableOps{
+		{ Instruction::LT, Instruction::GT },
+		{ Instruction::GT, Instruction::LT },
+		{ Instruction::SLT, Instruction::SGT },
+		{ Instruction::SGT, Instruction::SLT }
+	};
+
+	for (auto const& op: swappableOps)
+	{
+		AssemblyItems items{
+			u256(1),
+			u256(2),
+			Instruction::SWAP1,
+			op.first,
+			u256(4),
+			u256(5)
+		};
+		AssemblyItems expectation{
+			u256(1),
+			u256(2),
+			op.second,
+			u256(4),
+			u256(5)
+		};
+		PeepholeOptimiser peepOpt(items);
+		BOOST_REQUIRE(peepOpt.optimise());
+		BOOST_CHECK_EQUAL_COLLECTIONS(
+			items.begin(), items.end(),
 			expectation.begin(), expectation.end()
 		);
 	}
diff --git a/test/libsolidity/SolidityEndToEndTest.cpp b/test/libsolidity/SolidityEndToEndTest.cpp
index 07aa437e..beeae786 100644
--- a/test/libsolidity/SolidityEndToEndTest.cpp
+++ b/test/libsolidity/SolidityEndToEndTest.cpp
@@ -11097,6 +11097,50 @@ BOOST_AUTO_TEST_CASE(staticcall_for_view_and_pure)
 	}
 }
 
+BOOST_AUTO_TEST_CASE(swap_peephole_optimisation)
+{
+	char const* sourceCode = R"(
+		contract C {
+			function lt(uint a, uint b) returns (bool c) {
+				assembly {
+					a
+					b
+					swap1
+					lt
+					=: c
+				}
+			}
+			function add(uint a, uint b) returns (uint c) {
+				assembly {
+					a
+					b
+					swap1
+					add
+					=: c
+				}
+			}
+			function div(uint a, uint b) returns (uint c) {
+				assembly {
+					a
+					b
+					swap1
+					div
+					=: c
+				}
+			}
+		}
+	)";
+	compileAndRun(sourceCode);
+	BOOST_CHECK(callContractFunction("lt(uint256,uint256)", u256(1), u256(2)) == encodeArgs(u256(1)));
+	BOOST_CHECK(callContractFunction("lt(uint256,uint256)", u256(2), u256(1)) == encodeArgs(u256(0)));
+	BOOST_CHECK(callContractFunction("add(uint256,uint256)", u256(1), u256(2)) == encodeArgs(u256(3)));
+	BOOST_CHECK(callContractFunction("add(uint256,uint256)", u256(100), u256(200)) == encodeArgs(u256(300)));
+	BOOST_CHECK(callContractFunction("div(uint256,uint256)", u256(2), u256(1)) == encodeArgs(u256(2)));
+	BOOST_CHECK(callContractFunction("div(uint256,uint256)", u256(200), u256(10)) == encodeArgs(u256(20)));
+	BOOST_CHECK(callContractFunction("div(uint256,uint256)", u256(1), u256(0)) == encodeArgs(u256(0)));
+	BOOST_CHECK(callContractFunction("div(uint256,uint256)", u256(0), u256(1)) == encodeArgs(u256(0)));
+}
+
 BOOST_AUTO_TEST_SUITE_END()
 
 }