Tracking issue: solidity optimizer story

[moh-eulith]

I have a large contract that's compiled with --via-ir --optimize --optimize-runs 2
It's very close to going over the limit.

I looked at the generated opcodes and found several optimization opportunities.
I've implemented 1-5 in this repo and will do PR's against the main repo.
1 is implemented as a single change to the constant optimizer properly chooses between gas and size based
on command line parameters. This is single biggest size win (~945 bytes).

All five reduce the binary size of my large contract by 1149 bytes, which is significant.
ethereum/solidity@develop...moh-eulith:solidity:peep_combine

(6) is the only remaining large one, which I can't implement easily.

---

The following reduce both size and gas:

1. Mask generation
   ethereum/solidity@develop...moh-eulith:solidity:28_a_mask_generation
   a)
   15 instances of PUSH1 0x1 PUSH1 0x1 PUSH1 0x[0-9A-F]* SHL SUB NOT
   (sub case of the next one)
   -> PUSH0 NOT PUSH1 $bits SHL (saves 4 bytes)
   247 instances of PUSH1 0x1 PUSH1 0x1 PUSH1 0x[0-9A-F]* SHL SUB, saves 3*247 bytes
   PUSH1 0x1 PUSH1 0x1 PUSH1 0x40 SHL SUB : 8 bytes, 3 + 3 + 3 + 3 + 3 = 15 gas
   -> PUSH0 NOT PUSH1 0xC0 SHR: 5 bytes, 2 + 3 + 3 + 3 = 11 gas

b) Shifted mask generation
53 instances of PUSH1 0x1 PUSH1 0x[0-9A-F]* SHL PUSH1 0x1 PUSH1 0x[0-9A-F]* SHL SUB: saves 3*53
PUSH1 0x1 PUSH1 0x40 SHL PUSH1 0x1 PUSH1 0x80 SHL SUB: 11 opcodes
-> PUSH0 NOT PUSH1 0xC0 SHR PUSH1 0x40 SHL: 8 opcodes

The following reduce code size but increase gas cost:
This is implemented as part of the constant optimizer and properly chooses between gas and size based on command line params.
c)
42 instances of:
PUSH[56789] 0x[137F]F[F]*
(pushing with all 1's).
Length optimization (gas deopt): PUSH0 NOT PUSH1 (256 - $bits) SHR (save 1 or more bytes)

2. triple swap
   ethereum/solidity@develop...moh-eulith:solidity:28_b_triple_swap
   40 instances of:
   PUSH[1234] 0x[0-9ABCDEF]* SWAPN SWAP1 SWAPN
   -> SWAP[N-1] PUSH (save 2 bytes)
   no instances of dup swapN swap1 swapN

3. push dup swap
   ethereum/solidity@develop...moh-eulith:solidity:28_c_push_dup_swap
   58 instance of PUSH[123456789] 0x[0-9A-F]* DUP[2-9] SWAP1
PUSH DUP[2-9] SWAP1 -> DUP[x-1] PUSH (save 1 byte)

4. push x, swapZ, pushy, swap1
   ethereum/solidity@develop...moh-eulith:solidity:28_d_two_push_swap
   12 instances of PUSH[123456789] 0x[0-9A-F]* SWAP[1-9] PUSH[123456789] 0x[0-9A-F]* SWAP1
   push x, swapZ, pushy, swap1
   this the same as: push y, push x, swap[Z+1]
   1st push can also be dup:
   dupX swapZ pushY swap1 -> pushY dup(X+1) swap(Z+1)

5. push swap1 swap2 and (about 20 instances)
   -> swap1 push and (because and is commutative)
   ethereum/solidity@develop...moh-eulith:solidity:28_e_push_two_swap_comop
   generalizes to: push swap1 swapN ComOp -> swap[N-1] push ComOp
   no dup instances

6. Double jumps
   85 instances of JUMPDEST PUSH[12] 0x[0-9A-F]* JUMP
   this one is tricky (not peephole). it's typically preceded with JUMP or JUMPI
   All incoming jumps can be replaced with the push value (3 + 8 == 11 gas optimization) this is hard.
   it's not clear to me if there are any dynamic jumps in the code (jump address is computed, not a constant)
   The code seems to differentiate between push and push_tag, so maybe there are no dynamic jumps.
   This also can't be done externally because by the time we have just opcodes, there is no difference between PUSH and PUSH_TAG
   then if the preceding statement is JUMP or STOP or RETURN, the whole thing can be removed (82 instances)
   if the preceding statement is JUMPI, only JUMPDEST can be removed
   After a discussion with @cameel, it became clear this can be implemented.
   ethereum/solidity@develop...moh-eulith:solidity:trampoline

---

[cameel]

6. Double jumps

These are what you get when you have a call that accepts the result of another call as the last argument. The producer has to return to the place where it was called from and then we immediately call the consumer. Inlining the producer can eliminate this, but whether it can/should be done depends on other factors. If it does not happen, this pattern remains.

This case does involve dynamic jumps. I'm not sure the compiler will ever produce this with static ones, because that sounds like it would be much simpler to eliminate. If you're seeing this with static jumps, let me know.

In any case, I think that the reason you're seeing so much of it may be that it's a common pattern with public functions. These have an external part, which is called from the external dispatch, does ABI decoding and passes the result of that to the internal part. The internal part is what you really call when you invoke that function from another. As a result the internal part ends up being called from multiple places and is not inlined unless it's really trivial.

There is a way to optimize this: when calling the producer we could give it the address of the consumer as the return label. The problem is that this kind of optimization lives in this awkward space between the IR and the bytecode. You cannot do this at Yul level, because the result cannot be expressed using its high-level control flow - functions always return to the caller, not to some other place it tells them to. And it's quite hard to do in the opcode-based optimizer, because you need the high-level info about function calls to recognize this pattern. Looking at the example below, it could still be possible in some simpler cases, but it will be harder in full generality, because there can be a lot of stuff between placing the return label and the point of call when parameters are complex. I think that to do this reliably you may need the control flow graph.

The point where you have access to both the CFG and the bytecode structure is during the Yul->EVM transform, while we're walking the CFG and generating EVM opcodes from it. This would probably be in OptimizedEVMCodeTransform.h. Just be aware that part of the compiler is a bit in flux right now. We still use the older transform in some cases and we're also working on a new one that will help with stack issues, so we'd have to talk in the team about whether it's a good moment to jump at these kinds of tweaks.

Example

test.sol

contract C {
    event E(uint);

    function g(uint m) public {
        emit E(m);
    }

    function f() public {
        g(42);
    }
}

solc test.sol --optimize --asm --opcodes

The pattern you mention is present in the --opcodes output:

JUMP JUMPDEST PUSH1 0x55 JUMP

And here are the relevant bits of assembly, with some annotations and slightly altered syntax to make opcode arguments clearer:

    // external dispatch
      ...
      eq(dup1, 0x26121ff0) // -> external f()
      jumpi(tag_3)
      eq(dup1, 0xe420264a) // -> external g()
      jumpi(tag_4)
      ...

    // external f()
    tag_3:
      tag_5                // return address: end
      jump(tag_6)          // in -> internal f()

    // end
    tag_5:
      stop

    // external g()
    tag_4:
      tag_5             // return address: end
      tag_8             // return address: external g(), after ABI decoding
      calldatasize
      0x04     
      jump(tag_9)       // in -> ABI decoding helper

    // external g(), after ABI decoding
    tag_8:
      jump(tag_10)      // in -> internal g()

    // internal f()
    tag_6:
      tag_12            // return address: internal f(), after call to g()
      0x2a              // 42
      jump(tag_10)      // in -> internal g()

    // internal f(), after call to g()
    tag_12:
      jump              // out

    // internal g()
    tag_10:
    ...
    jump                // out

    // ABI decoding helper
    tag_9:
    ...

The seemingly redundant jump is in the external part of g() (tag_8) and it is there because it's the continuation of its body after invoking the ABI decoding helper. Normally the code that puts the arguments and the return address on the stack would go here, but in this case the uint argument will be placed on the stack by the helper and the return address (tag_5) is already there.

One way to eliminate the jump would be to inline the internal part of g() (tag_10) so that the jump back is not necessary. Here g() is also called from f() so the inliner decided not to do this.

The other way, that cannot be expressed in Yul would work by changing the return label so that the helper jumps to the internal part of g() directly instead of returning to external g() and having it jump there:

     // external g()
     tag_4:
       tag_5             // return address: end
-      tag_8             // return address: external g(), after ABI decoding
       calldatasize
       0x04     
       jump(tag_9)       // in -> ABI decoding helper
-
-    // external g(), after ABI decoding
-    tag_8:
-      jump(tag_10)      // in -> internal g()

[moh-eulith]

Thanks for the thorough explanation. I think in the last part, you meant replace all tag_8 with tag_10, like so, right?

     // external g()
     tag_4:
       tag_5             // return address: end
-      tag_8             // return address: external g(), after ABI decoding
+      tag_10             // return address inlined
       calldatasize
       0x04     
       jump(tag_9)       // in -> ABI decoding helper
-
-    // external g(), after ABI decoding
-    tag_8:
-      jump(tag_10)      // in -> internal g()

It seems to me recognizing the pattern in assembly (not yul... why is that so confusing?) is the easiest. The assembly output here is not something that the compiler actually goes through while compiling, correct? I guess adding such a step (yul -> real assembly -> opcodes) is not trivial/desirable?

[cameel]

Thanks for the thorough explanation. I think in the last part, you meant replace all tag_8 with tag_10, like so, right?

Yeah, this is a leftover from how I tried to modify it at first. I thought I reverted it to the original state, but I didn't. I noticed and fixed it after I posted.

not yul... why is that so confusing?

Haha, TBH I never liked this ambiguous terminology either. Yul is the inline assembly, but it's not EVM assembly :) I guess we have to live with that now though.

It seems to me recognizing the pattern in assembly (...) is the easiest.

In a trivial case like this where there's just one call with one argument it seems easy, but in general it seems to me that it could be harder. These patterns could be nested in each other. Maybe even overlap. There can be quite a lot of stuff in between the tag push and the jump when a function has lots of parameters and when their values are produced by calls, which can in turn take values from other calls. Intuitively, this just does not seem like the kind of problem well suited for pattern matching.

The assembly output here is nothing something that the compiler actually goes through while compiling, correct?

Not sure I fully understand the question. In the legacy pipeline this assembly actually comes directly from the codegen. In the IR pipeline, on the other hand, codegen produces Yul and then we build a CFG and convert it to opcodes. You could say that the transform directly produces that output.

Then in both cases the opcode-based optimizer runs a sequence of steps in multiple passes over the opcode stream. This is e.g. where the constant optimizer sits. You probably mean doing this as another opcode-based optimizer step (i.e. after we converted Yul to opcodes)?

I guess adding such a step (yul -> real assembly -> opcodes) is not trivial/desirable?

Whether it's desirable actually depends on how simple it would actually be. I suspect that a trivial one will only deal with the simple cases and I'm not sure how common those are in real contracts relatively to the more complex ones. It's mostly about the complexity of the implementation (and potential for bugs) compared to the benefit it provides.

Also, historically, we tended to see the opcode-based optimizer as legacy code that will eventually disappear, because Yul optimizer will already produce code that does not need it and is generally easier to work with and can have nice properties (like being able to prove correctness of transitions at Yul level). This turned out to not always be the case and some opcode-based optimizations will always be needed so extending them is still on the table.

Overall, hard to say without analyzing the problem a bit more. I suspect that a CFG solution would be both simpler and more comprehensive so I'd rather see it done there. But if you can come up with an opcode-based solution that's simple and general enough, we'd consider that too.

[moh-eulith]

The semantics are getting in the way, I think. What I'm calling "real assembly" has at least one salient difference with what I understand under the term "opcodes": there is no "tag" opcode (as in, not found in the yellow paper or in the output of --opcodes). And tag is a bit overloaded: it has 3 usages in assembly (push tag tag_8, place tag tag_8:, jump destination jump(tag8)) which translate to PUSH, JUMPDEST and nothing recognizable in opcodes (because the push happens potentially very far away). I've seen references to "PUSH_TAG" in the code, but not the other two.

So to put the question differently, since "tag" also doesn't appear in yul, is there a middle ground between yul and opcodes where tags exist? If so, can that be targeted for optimization by looking for "tag_a: jump(tag_b)" patterns?

[cameel]

Actually, I just realized a major downside of such an optimization is that it relies on dynamic jumps and those are something we have long been trying to eliminate from the EVM. It would not be possible on EOF for example.

Note how it would interfere with debuggers and static analysis tools. It is notoriously hard to distinguish calls from other jumps at the EVM bytecode level and this is why we provide the functionDebugData artifact. The optimization eliminates the entry point to the function (marked as // in here). I'm actually not sure what we'd report in functionDebugData in this case, because the entry point no longer exists. It would also break heuristics in tools that detect functions just looking at the patterns in the bytecode.

So at most this could be an optional, opt-in thing. But I'm a bit wary about whether making it easy to do this would be a good thing at all.

[moh-eulith]

fyi, I just did an --asm output of my real contract and it has this pattern:

    tag_415:
      tag_39
      jump      // in

repeated (different numbers) over and over.

I'm not sure I understand what you mean by dynamic jumps in this particular case. There is nothing dynamic about the pattern above, is there? (By dynamic, I mean something like computing a value to be pushed, then jumping there).

[cameel]

The semantics are getting in the way, I think.

Ah, now I see what you mean. Yes, I don't think we have good unambiguous terms for these. I usually call it assembly (the level where you have tags) vs bytecode (the actual byte representation with JUMPDESTs). Internally, in the compiler codebase the former is represented with AssemblyItems (there are explicit Tag and PushTag items, while JUMPDESTs can be represented by Operation, but are optional and implied by Tag), while bytecode is just a stream of bytes.

And tag is a bit overloaded: it has 3 usages in assembly (push tag tag_8, place tag tag_8:, jump destination jump(tag8)) which translate to PUSH, JUMPDEST and nothing recognizable in opcodes (because the push happens potentially very far away). I've seen references to "PUSH_TAG" in the code, but not the other two.

• push tag tag_8 -> AssemblyItem of type PushTag -> PUSH <jumpdest address> in bytecode
• place tag tag_8: -> AssemblyItem of type Tag -> JUMPDEST in bytecode
• jump destination jump(tag8) -> this is just a combination of two things: PushTag and JUMP

So to put the question differently, since "tag" also doesn't appear in yul, is there a middle ground between yul and opcodes where tags exist? If so, can that be targeted for optimization by looking for "tag_a: jump(tag_b)" patterns?

The opcode-based optimizer is actually that middle ground. It operates on AssemblyItems. Once bytecode has been generated from AssemblyItems, the compiler treats it mostly as a binary blob. It's a soup of opcodes and data, potentially with arbitrarily nested containers. Even library linking is just done by search and replace in it rather than analyzing it. The only exception is our rudimentary Disassembler, which produces the --opcodes output.

[moh-eulith]

I stared at the assembly some more. With one exception, all these occurrences are for the external function selector. It looks like this:

      0x11f3d2be
      eq
      tag_363
      jumpi
      dup1
      0x24313ed6
      eq
      tag_365
      jumpi
// same pattern repeated with other recognizably 4 byte function names

and the requisite:

    tag_365:
      tag_6
      jump      // in
    tag_363:
      tag_4
      jump      // in

This is the single use of tag_365, tag_363, etc. Am I missing something here, or is it perfectly safe to replace tag_365 with tag_6?

The one exception is not called from the function selector, but called many times, also always with a jumpi.

[cameel]

I'm not sure I understand what you mean by dynamic jumps in this particular case. There is nothing dynamic about the pattern above, is there? (By dynamic, I mean something like computing a value to be pushed, then jumping there).

Well, technically all EVM jumps are dynamic because they take the address from the stack. But by static I mean those where the address is a constant pushed immediately before JUMP and therefore the target can be uniquely determined by static analysis. By dynamic I mean ones where you cannot immediately tell where it could jump, even if the number of targets is limited.

[cameel]

Anyway, I have some things to deal with now so I'll return to this thread later. I wanted to just post a quick comment on point 6, because it intrigued me, but the comment was not-so-quick after all and it's turning into a longer discussion than I expected :)

[moh-eulith]

Thanks for you time. It gave me an idea I want to try 😄

[cameel]

Well, thank you too :) The opcode-based optimizer has been a bit neglected while we've been trying to deal with some more overarching design problems, so contributions like this do help us and surely will be appreciated by other users.

[moh-eulith]

Seems to work:
ethereum/solidity@develop...moh-eulith:solidity:trampoline
🌞