Explicitly add reversed operands for commutative operations.

1 files changed, 56 insertions, 34 deletions

diff --git a/libevmasm/RuleList.h b/libevmasm/RuleList.h
index 3e7be720..f8a6ce73 100644
--- a/libevmasm/RuleList.h
+++ b/libevmasm/RuleList.h
@@ -43,11 +43,6 @@ template <class S> S modWorkaround(S const& _a, S const& _b)
 	return (S)(bigint(_a) % bigint(_b));
 }
 
-// TODO: Add a parameter that will cause rules with swapped arguments
-// to be added explicitly. This is needed by the new optimizer, but not
-// by the old. The new optimizer requires that the order of arbitrary
-// expressions is not altered.
-
 /// @returns a list of simplification rules given certain match placeholders.
 /// A, B and C should represent constants, X and Y arbitrary expressions.
 /// The third element in the tuple is a boolean flag that indicates whether
@@ -96,11 +91,16 @@ std::vector<std::tuple<Pattern, std::function<Pattern()>, bool>> simplificationR
 			return u256(boost::multiprecision::bit_test(B.d(), testBit) ? B.d() | ~mask : B.d() & mask);
 		}, false},
 
-		// invariants involving known constants (commutative instructions will be checked with swapped operants too)
+		// invariants involving known constants
 		{{Instruction::ADD, {X, 0}}, [=]{ return X; }, false},
+		{{Instruction::ADD, {0, X}}, [=]{ return X; }, false},
 		{{Instruction::SUB, {X, 0}}, [=]{ return X; }, false},
 		{{Instruction::MUL, {X, 0}}, [=]{ return u256(0); }, true},
+		{{Instruction::MUL, {0, X}}, [=]{ return u256(0); }, true},
 		{{Instruction::MUL, {X, 1}}, [=]{ return X; }, false},
+		{{Instruction::MUL, {1, X}}, [=]{ return X; }, false},
+		{{Instruction::MUL, {X, u256(-1)}}, [=]() -> Pattern { return {Instruction::SUB, {0, X}}; }, false},
+		{{Instruction::MUL, {u256(-1), X}}, [=]() -> Pattern { return {Instruction::SUB, {0, X}}; }, false},
 		{{Instruction::DIV, {X, 0}}, [=]{ return u256(0); }, true},
 		{{Instruction::DIV, {0, X}}, [=]{ return u256(0); }, true},
 		{{Instruction::DIV, {X, 1}}, [=]{ return X; }, false},
@@ -108,13 +108,19 @@ std::vector<std::tuple<Pattern, std::function<Pattern()>, bool>> simplificationR
 		{{Instruction::SDIV, {0, X}}, [=]{ return u256(0); }, true},
 		{{Instruction::SDIV, {X, 1}}, [=]{ return X; }, false},
 		{{Instruction::AND, {X, ~u256(0)}}, [=]{ return X; }, false},
+		{{Instruction::AND, {~u256(0), X}}, [=]{ return X; }, false},
 		{{Instruction::AND, {X, 0}}, [=]{ return u256(0); }, true},
+		{{Instruction::AND, {0, X}}, [=]{ return u256(0); }, true},
 		{{Instruction::OR, {X, 0}}, [=]{ return X; }, false},
+		{{Instruction::OR, {0, X}}, [=]{ return X; }, false},
 		{{Instruction::OR, {X, ~u256(0)}}, [=]{ return ~u256(0); }, true},
+		{{Instruction::OR, {~u256(0), X}}, [=]{ return ~u256(0); }, true},
 		{{Instruction::XOR, {X, 0}}, [=]{ return X; }, false},
+		{{Instruction::XOR, {0, X}}, [=]{ return X; }, false},
 		{{Instruction::MOD, {X, 0}}, [=]{ return u256(0); }, true},
 		{{Instruction::MOD, {0, X}}, [=]{ return u256(0); }, true},
 		{{Instruction::EQ, {X, 0}}, [=]() -> Pattern { return {Instruction::ISZERO, {X}}; }, false },
+		{{Instruction::EQ, {0, X}}, [=]() -> Pattern { return {Instruction::ISZERO, {X}}; }, false },
 
 		// operations involving an expression and itself
 		{{Instruction::AND, {X, X}}, [=]{ return X; }, true},
@@ -130,14 +136,25 @@ std::vector<std::tuple<Pattern, std::function<Pattern()>, bool>> simplificationR
 
 		// logical instruction combinations
 		{{Instruction::NOT, {{Instruction::NOT, {X}}}}, [=]{ return X; }, false},
-		{{Instruction::XOR, {{{X}, {Instruction::XOR, {X, Y}}}}}, [=]{ return Y; }, true},
-		{{Instruction::OR, {{{X}, {Instruction::AND, {X, Y}}}}}, [=]{ return X; }, true},
-		{{Instruction::AND, {{{X}, {Instruction::OR, {X, Y}}}}}, [=]{ return X; }, true},
-		{{Instruction::AND, {{{X}, {Instruction::NOT, {X}}}}}, [=]{ return u256(0); }, true},
-		{{Instruction::OR, {{{X}, {Instruction::NOT, {X}}}}}, [=]{ return ~u256(0); }, true},
+		{{Instruction::XOR, {X, {Instruction::XOR, {X, Y}}}}, [=]{ return Y; }, true},
+		{{Instruction::XOR, {X, {Instruction::XOR, {Y, X}}}}, [=]{ return Y; }, true},
+		{{Instruction::XOR, {{Instruction::XOR, {X, Y}}, X}}, [=]{ return Y; }, true},
+		{{Instruction::XOR, {{Instruction::XOR, {Y, X}}, X}}, [=]{ return Y; }, true},
+		{{Instruction::OR, {X, {Instruction::AND, {X, Y}}}}, [=]{ return X; }, true},
+		{{Instruction::OR, {X, {Instruction::AND, {Y, X}}}}, [=]{ return X; }, true},
+		{{Instruction::OR, {{Instruction::AND, {X, Y}}, X}}, [=]{ return X; }, true},
+		{{Instruction::OR, {{Instruction::AND, {Y, X}}, X}}, [=]{ return X; }, true},
+		{{Instruction::AND, {X, {Instruction::OR, {X, Y}}}}, [=]{ return X; }, true},
+		{{Instruction::AND, {X, {Instruction::OR, {Y, X}}}}, [=]{ return X; }, true},
+		{{Instruction::AND, {{Instruction::OR, {X, Y}}, X}}, [=]{ return X; }, true},
+		{{Instruction::AND, {{Instruction::OR, {Y, X}}, X}}, [=]{ return X; }, true},
+		{{Instruction::AND, {X, {Instruction::NOT, {X}}}}, [=]{ return u256(0); }, true},
+		{{Instruction::AND, {{Instruction::NOT, {X}}, X}}, [=]{ return u256(0); }, true},
+		{{Instruction::OR, {X, {Instruction::NOT, {X}}}}, [=]{ return ~u256(0); }, true},
+		{{Instruction::OR, {{Instruction::NOT, {X}}, X}}, [=]{ return ~u256(0); }, true},
 	};
 
-	// Double negation of opcodes with binary result
+	// Double negation of opcodes with boolean result
 	for (auto const& op: std::vector<Instruction>{
 		Instruction::EQ,
 		Instruction::LT,
@@ -174,28 +191,33 @@ std::vector<std::tuple<Pattern, std::function<Pattern()>, bool>> simplificationR
 	{
 		auto op = opFun.first;
 		auto fun = opFun.second;
-		// Moving constants to the outside, order matters here!
-		// we need actions that return expressions (or patterns?) here, and we need also reversed rules
-		// (X+A)+B -> X+(A+B)
-		rules += std::vector<std::tuple<Pattern, std::function<Pattern()>, bool>>{{
-			{op, {{op, {X, A}}, B}},
-			[=]() -> Pattern { return {op, {X, fun(A.d(), B.d())}}; },
-			false
-		}, {
-		// X+(Y+A) -> (X+Y)+A
-			{op, {{op, {X, A}}, Y}},
-			[=]() -> Pattern { return {op, {{op, {X, Y}}, A}}; },
-			false
-		}, {
-		// For now, we still need explicit commutativity for the inner pattern
-			{op, {{op, {A, X}}, B}},
-			[=]() -> Pattern { return {op, {X, fun(A.d(), B.d())}}; },
-			false
-		}, {
-			{op, {{op, {A, X}}, Y}},
-			[=]() -> Pattern { return {op, {{op, {X, Y}}, A}}; },
-			false
-		}};
+		// Moving constants to the outside, order matters here - we first add rules
+		// for constants and then for non-constants.
+		// xa can be (X, A) or (A, X)
+		for (auto xa: {std::vector<Pattern>{X, A}, std::vector<Pattern>{A, X}})
+		{
+			rules += std::vector<std::tuple<Pattern, std::function<Pattern()>, bool>>{{
+				// (X+A)+B -> X+(A+B)
+				{op, {{op, xa}, B}},
+				[=]() -> Pattern { return {op, {X, fun(A.d(), B.d())}}; },
+				false
+			}, {
+				// (X+A)+Y -> (X+Y)+A
+				{op, {{op, xa}, Y}},
+				[=]() -> Pattern { return {op, {{op, {X, Y}}, A}}; },
+				false
+			}, {
+				// B+(X+A) -> X+(A+B)
+				{op, {B, {op, xa}}},
+				[=]() -> Pattern { return {op, {X, fun(A.d(), B.d())}}; },
+				false
+			}, {
+				// Y+(X+A) -> (Y+X)+A
+				{op, {Y, {op, xa}}},
+				[=]() -> Pattern { return {op, {{op, {Y, X}}, A}}; },
+				false
+			}};
+		}
 	}
 
 	// move constants across subtractions