{"action":"created","issue":{"url":"https://api.github.com/repos/ethereum/solidity/issues/4959","repository_url":"https://api.github.com/repos/ethereum/solidity","labels_url":"https://api.github.com/repos/ethereum/solidity/issues/4959/labels{/name}","comments_url":"https://api.github.com/repos/ethereum/solidity/issues/4959/comments","events_url":"https://api.github.com/repos/ethereum/solidity/issues/4959/events","html_url":"https://github.com/ethereum/solidity/issues/4959","id":359767086,"node_id":"MDU6SXNzdWUzNTk3NjcwODY=","number":4959,"title":"implement more peephole optimization rule from the ICSE paper","user":{"login":"liangdzou","id":1409883,"node_id":"MDQ6VXNlcjE0MDk4ODM=","avatar_url":"https://avatars0.githubusercontent.com/u/1409883?v=4","gravatar_id":"","url":"https://api.github.com/users/liangdzou","html_url":"https://github.com/liangdzou","followers_url":"https://api.github.com/users/liangdzou/followers","following_url":"https://api.github.com/users/liangdzou/following{/other_user}","gists_url":"https://api.github.com/users/liangdzou/gists{/gist_id}","starred_url":"https://api.github.com/users/liangdzou/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/liangdzou/subscriptions","organizations_url":"https://api.github.com/users/liangdzou/orgs","repos_url":"https://api.github.com/users/liangdzou/repos","events_url":"https://api.github.com/users/liangdzou/events{/privacy}","received_events_url":"https://api.github.com/users/liangdzou/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":2,"created_at":"2018-09-13T07:00:45Z","updated_at":"2018-09-13T08:03:10Z","closed_at":null,"author_association":"CONTRIBUTOR","body":"## Abstract\r\n\r\nThere is an ICSE2018 paper introduced 24 rules for optimizing EVM gas. I think this should be implemented in Solidity.\r\n\r\n## Motivation\r\n\r\nOptimizing the gas spending for smart contracts.\r\n\r\n## Specification\r\n\r\nTo implement the 24 rules given by the ICSE2018 paper.\r\nThe operation sequence before → denotes an anti-pattern and the sequence after → is the code after optimization (delete indicates the anti-pattern can be removed).\r\n\r\nP1 — {swap(X), swap(X)} → delete, 1 ≤ X ≤ 16\r\n() indicates a number inside instead of a part of an operation. swap(X) exchanges the 1st and the (𝑋 + 1)th stack items. The two consecutive swap(X)s can be removed since the execution of them has no effect. The anti-pattern accounts for two bytes (e.g., the bytecode of swap1 is 0x90) and its deployment wastes 136 units of gas (every non-zero bytecode requires 68 units). The execution of this pattern wastes 6 units of gas because the execution of a swap(X) needs 3 units.\r\n\r\nP2 — {M consecutive jumpdests} → {jumpdest}, M ≥ 2\r\njumpdest marks a valid jump target (i.e., any valid jump operation must jump to a jumpdest). M consecutive jumpdests can be replaced with one because they point to the same operation (i.e., the operation after the final jumpdest). The deployment and invocation of this anti-pattern waste 68 × (𝑀 − 1) units and (𝑀 − 1) units of gas (the execution of a jumpdest needs 1 unit of gas), respectively.\r\n\r\nP3 — {OP, pop} → {pop}, OP ∈ {iszero, not, balance, calldataload, extcodesize, blockhash, mload, sload}\r\nOP consumes the top stack item, produces an outcome, and pushes the outcome on stack. pop removes the top stack item. This anti-pattern is semantically equivalent with one pop because the outcome of OP is immediately removed by pop. Due to page limit, we cannot explain the semantics of every EVM operation, and interested readers can refer to Ethereum’s yellow paper. The anti-pattern wastes 68 units of gas in deployment, and the amount of gas wasted by executing the anti-pattern instance depends on gas_cost of OP.\r\n\r\nP4 — {OP, pop} → {pop, pop}, OP ∈ {add, sub, mul, div, sdiv, mod, smod, exp, sigextnd, lt, gt, slt, sgt, eq, and, or, xor, byte, sha3}\r\nThis anti-pattern is similar with anti-pattern 3, but this OP consumes the top two stack items, produces an outcome, and pushes the outcome on stack. This anti-pattern is semantically equivalent with two consecutive pops because the the top 2 stack items are removed by two pops. The anti-pattern wastes 0 units of gas in deployment because both the anti-pattern and the efficient code consist of two non-zero bytes. The amount of gas wasted by executing the anti-pattern instance depends on gas_cost of OP.\r\n\r\nP5 — {OP, pop} → {pop, pop, pop}, OP ∈ {addmod, mulmod}\r\nThis anti-pattern is similar with anti-pattern 3, but this OP consumes the top three stack items, produces an outcome, and pushes the outcome on stack. This anti-pattern is semantically equivalent with three consecutive pops because the top 3 stack items are removed by pops. The anti-pattern is the only one which increases 68 units of gas in deployment after replacing with the efficient code. However, the three consecutive pops is more efficient than pop, pop is executing since a pop needs 2 units of gas and either addmod or mulmod needs 8 units of gas. Hence, the execution of this anti-pattern wastes 4 units of gas. Since a smart contract can be executed many times but can be deployed only once, OP, pop is considered to be less efficient than three pops.\r\n\r\nP6 — {OP, pop} → delete, OP ∈ {address, origin, caller, callvalue, calldatasize, codesize, gasprice, coinbase, timestamp, number, difficulty, gaslimit, pc, msize, gas}\r\nThis anti-pattern is similar with anti-pattern 3, but this OP doesn’t consume the stack item, but produces an outcome, and pushes the outcome on stack. Therefore, this anti-pattern can be deleted because the outcome of OP is immediately removed by pop. The anti-pattern wastes 136 units of gas in deployment, and the amount of gas wasted by executing the anti-pattern instance depends on gas_cost of OP.\r\n\r\nP7 — {swap1, swap(X), OP, dup(X), OP} → {dup2, swap(X+1), OP, OP}, 2 ≤ X ≤ 15, OP ∈ {add, mul, and, or, xor}\r\ndup(X) duplicates Xth stack item on stack top. Let the first three stack items be i0, i1 and i2, X be 2, and OP be add. After executing this anti-pattern, the number of stack items decreases by 1 and the top two items become i0 + i1 + i2, i1. Hence, one swap can be removed since OP (e.g. add) is commutative. The anti-pattern wastes 68 units and 3 units of gas for deployment and execution of a swap, respectively.\r\n\r\nP8 — {OP, stop} → {stop}, OP can be any operation except jumpdest, jump, jumpi and all operations that change storage.\r\nstop halts the execution of the smart contract and then stack and memory are cleared. For example, let OP be add, after the execution of stop, the outcome of add on stack will be discarded, and hence add can be removed. On the other hand, those operations involved in control flow transfer or changing the permanent storage space cannot be removed.\r\n\r\nP9 — {swap(X), dup(X+1), swap1} → {dup1, swap(X+1)}, 1 ≤ X ≤ 15\r\nLet the top two stack items be i0 and i1, X be 1, after the execution of this anti-pattern, the number of stack items increases by 1 and the top three stack items become i1, i0, and i0. Therefore, one swap operation can be removed. The deployment and invocation of this anti-pattern wastes 68 units and 3 units of gas, respectively.\r\n\r\nP10 — {push(X), swap(Y), Y consecutive pops} → {Y consecutive pops, push(X)}, 1 ≤ X ≤ 32, 1 ≤ Y ≤ 16\r\nAs an example, let the top stack item be i0 and the value pushed by the first operation, push1 is i1, and Y be 1, after the execution of this anti-pattern, the top stack item becomes i1. Hence, this anti-pattern can be replaced with pop, push1. Therefore, one swap operation can be removed. The deployment and invocation of this anti-pattern wastes 68 units and 3 units of gas, respectively.\r\n\r\nP11 — {swap(X), X+1 consecutive pops} → {X+1 consecutive pops}, 1 ≤ X ≤ 16\r\nLet X be 1, since two consecutive pops pop top two stack items, the swap1 has no effect. The deployment and invocation of this anti-pattern wastes 68 units and 3 units of gas, respectively.\r\n\r\nP12 — {swap(X), swap(Y), Y consecutive pops} → {X consecutive pops, swap(Y-X), (Y-X) consecutive pops}, 1 ≤ X ≤ 15, X < Y\r\nLet the top three stack items be i0, i1, and i2, X be 1 and Y be 2, after the execution of this anti-pattern, the number of stack items reduces by two and the top stack item becomes i1. One swap operation can be removed because the two consecutive pops cancel the effect of that swap. The deployment and invocation of this anti-pattern wastes 68 units and 3 units of gas, respectively.\r\n\r\nP13 — {X consecutive push(N)s, Y consecutive pops} → {(X-Y) consecutive push(N)s, if X > Y; (Y-X) consecutive pops, otherwise}, 1 ≤ N ≤ 32\r\nA pop immediately after a push can be removed because they have no effect. To investigate gas waste, we consider the following two situations. First, push(N) outnumbers pop. In this case, all Y pop operations and Y push(N) operations can be removed. Therefore, the deployment and invocation of the anti-pattern waste 136Y (68×2Y) units and 5Y (3Y+2Y) units of gas. Otherwise, all X push(N) operations and X pop operations can be removed. In this case, the deployment and invocation of the anti-pattern waste 136X (68×2X) units and 5X (3X+2X) units of gas.\r\n\r\nP14 — {X consecutive dup(N)s, Y consecutive pops} → {(X-Y) consecutive dup(N)s, if X > Y; (Y-X) consecutive pops, otherwise}, 1 ≤ N ≤ 16\r\nThis anti-pattern is similar with anti-pattern 13, because dup(N) duplicates the Nth stack item on stack, whose effect can be cancelled by pop. Similarly, the anti-pattern wastes 136Y units and 5Y units of gas in deployment and invocation, if X > Y; and 136X units and 5X units of gas, if X ≤ Y.\r\n\r\nP15 — {dup(X), swap(X)} → {dup(X)}, 1 ≤ X ≤ 16\r\nLet X be 1, dup1 duplicates the 1st stack item, so the following swap1 has no effect. The deployment and invocation of this anti-pattern wastes 68 units and 3 units of gas, respectively.\r\n\r\nP16 — {swap1, swap2, …, swap(X), swap(X-1), …, swap1, X-1 consecutive pops} → {X-1 consecutive pops, swap1}, 2 ≤ X ≤ 16\r\nLet the top three stack items be i0, i1 and i2, and X be 2, after the execution of this anti-pattern, the number of stack items reduces by one and the top two stack items become i2, i1. By executing pop before the sequence of swap operations, fewer swap operations are needed because swap(X) exchanges the top item with the (X+1)th stack item. In other words, EVM cannot adjust the order of non-top stack items directly; instead, it has to move one item on stack top and then exchange it with another stack item by executing several swaps. The optimized operation sequence removes 2X-2 redundant swap operations. Hence, the anti-pattern wastes 136(X-1) units and 6(X-1) units of gas in deployment and invocation, respectively.\r\n\r\nP17 — {swap1, OP} → {OP}, OP ∈ {add, mul, and, or, xor}\r\nSince OP is commutative, swap1 has no effect. Therefore, the deployment of the anti-pattern wastes 68 units and the amount of wasted gas in invocation is 3 units.\r\n\r\nP18 — {OP, iszero, iszero} → {OP}, OP ∈ {lt, gt, slt, sgt, eq}\r\nAs an example, the outcome of gt is either 1 or 0, depending on whether the 1st stack item is larger than the 2nd stack item. iszero sets the 1st stack item to 1 if it is 0, or 0 otherwise. Therefore, two consecutive iszeros do not change the outcome of OP. Therefore, the deployment and invocation of the anti-pattern wastes 136 units and 6 units of gas, respectively.\r\n\r\nP19 — {N consecutive push(X)，M consecutive swap(Y)} → {N consecutive push(X)}, Y < N, 1 ≤ X ≤ 32, 1 ≤ Y ≤ 16\r\npush(X) are the only operations that has operands, let N be 2 and Y be 1, so the operation sequence push(X), push(X), swap1 can be optimized as push(X), push(X). That is to say, by adjusting the order of the operands of push operations, the swap operation can be removed. Therefore, the anti-pattern wastes 68M units and 3M units of gas in deployment and invocation, respectively.\r\n\r\nP20 — {push(X), swap(Y), push(M), swap1} → {push(M), push(X), swap(Y+1)}, 1 ≤ X ≤ 32, 1 ≤ Y ≤ 15, 1 ≤ M ≤ 32\r\nFor the same reason with pattern 19, one swap operation of this anti-pattern can be removed, and hence it wastes 68 units and 3 units of gas in deployment and invocation, respectively.\r\n\r\nP21 — {consecutive X push(N), dup(Y), swap(Z)} → {combination of X push(N) and dup(M)}, Y<=X, Z<=X, M<=X, 1 ≤ N ≤ 32, 1 ≤ Y ≤ 16, 1 ≤ Z ≤ 16, 1 ≤ M ≤ 16\r\nFor the same reason with pattern 19, the swap operation of this anti-pattern can be removed, and hence the deployment and invocation of this anti-pattern wastes 68 units and 3 units of gas, respectively.\r\n\r\nP22 — {swap(N), M consecutive OPs，(N+M) consecutive and same OP'} → {M consecutive OPs，(N+M) consecutive and same OP'}, OP ∈ {push(X), dup(Y)}, OP' ∈ {add, mul, and, or, xor}, 1 ≤ X ≤ 32, 1 ≤ N ≤ 16, 1 ≤ Y ≤ 16\r\nSince OP' is commutative and both push(X) and dup(Y) increase the number of stack items by one, swap(N) in this anti-pattern can be removed. Therefore, the deployment and invocation of this anti-pattern wastes 68 units and 3 units of gas, respectively.\r\n\r\nP23 — {dup1, swap(X), dup2, swap1} → {dup1, dup2, swap(X+1)}, 1 ≤ X ≤ 15\r\nLet the first two stack items be i0, i1, and X be 2, after the execution of this anti-pattern, the number of stack items increases by two and the top four stack items become i1, i0, i0, i0. The optimized operation sequence has the same effect and has one fewer operations. Therefore, the deployment and invocation of this anti-pattern wastes 68 units and 3 units of gas, respectively.\r\n\r\nP24 — {dup(X), swap(X-1), swap1, dup(X), swap1} → {dup(X), dup1, swap(X), swap2}, 3 ≤ X ≤ 16\r\nLet the first three stack items be i0, i1, i2, and X be 3, after the execution of this anti-pattern, the number of stack items increases by two and the top five stack items become i0, i2, i1, i2, i2. One swap operation can be removed, and hence the deployment and invocation of this anti-pattern wastes 68 units and 3 units of gas, respectively.\r\n\r\n## Backwards Compatibility\r\n\r\nn/a"},"comment":{"url":"https://api.github.com/repos/ethereum/solidity/issues/comments/420919631","html_url":"https://github.com/ethereum/solidity/issues/4959#issuecomment-420919631","issue_url":"https://api.github.com/repos/ethereum/solidity/issues/4959","id":420919631,"node_id":"MDEyOklzc3VlQ29tbWVudDQyMDkxOTYzMQ==","user":{"login":"liangdzou","id":1409883,"node_id":"MDQ6VXNlcjE0MDk4ODM=","avatar_url":"https://avatars0.githubusercontent.com/u/1409883?v=4","gravatar_id":"","url":"https://api.github.com/users/liangdzou","html_url":"https://github.com/liangdzou","followers_url":"https://api.github.com/users/liangdzou/followers","following_url":"https://api.github.com/users/liangdzou/following{/other_user}","gists_url":"https://api.github.com/users/liangdzou/gists{/gist_id}","starred_url":"https://api.github.com/users/liangdzou/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/liangdzou/subscriptions","organizations_url":"https://api.github.com/users/liangdzou/orgs","repos_url":"https://api.github.com/users/liangdzou/repos","events_url":"https://api.github.com/users/liangdzou/events{/privacy}","received_events_url":"https://api.github.com/users/liangdzou/received_events","type":"User","site_admin":false},"created_at":"2018-09-13T08:03:10Z","updated_at":"2018-09-13T08:03:10Z","author_association":"CONTRIBUTOR","body":"I think the rules given are almost about one instruction or related instructions. The rules given here are more about many different instructions. I am not sure if the rule can be added in current infrastructure.\r\n\r\nFor example, the rule \"{M consecutive jumpdests} → {jumpdest}, M ≥ 2\", the pattern is not an instruction any more. It has serval jumpdest instructions, and they are not related as operator and operand. **I think current infrastructure requires the instructions are related as operator and operands, am I right?**\r\n\r\nCurrent rules are\r\n```\r\n 37 struct SimplificationRule                                                                                                                                                                                                                                                 \r\n 38 {                                                                               \r\n 39   Pattern pattern;                                                              \r\n 40   std::function<Pattern()> action;                                               \r\n 41   bool removesNonConstants;                                                      \r\n 42 };                                                                              \r\n```\r\nwhere pattern is basically a instruction.\r\n```\r\nPattern(Instruction _instruction, std::vector<Pattern> const& _arguments = {})\r\n```\r\n"}}
{"actor":{"display_login":"liangdzou"}}