From 295f8c07ad63cd1b0c5176bd39e9c13f64968c7e Mon Sep 17 00:00:00 2001 From: chriseth Date: Thu, 18 Jan 2018 13:56:42 +0100 Subject: Explicitly add reversed operands for commutative operations. --- libevmasm/RuleList.h | 90 ++++++++++++++++++++++++++++++++-------------------- 1 file 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 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, 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, 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, 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::EQ, Instruction::LT, @@ -174,28 +191,33 @@ std::vector, 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, 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{X, A}, std::vector{A, X}}) + { + rules += std::vector, 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 -- cgit