EIP-2315 Simple Subroutines for the EVM

@axic, @lialan, @holiman. @karalabe. This program should be more optimizable. test() must be public or else the optimizer tries to eliminate everything.

pragma solidity >0.6.2;
contract fun {
    function test(uint x, uint y) pure public returns (uint) {
        return test_mul(x, y);
    }
    function test_mul(uint x, uint y) pure private returns (uint) {
        return multiply(x, y);
    }
    function multiply(uint x, uint y) pure private returns (uint) {
        return x * y;
    }
}

Compiling with solc --asm --optimize fun.sol gives this. I don’t fully understand what it is doing.

   TEST:
      0x00
      OUT
      dup4
      dup4
      MULTIPLY
      jump
   OUT:
      swap4
      swap3
      pop
      pop
      pop
      jump
   MULTIPLY:
      0x00
      dup2
      dup4
      mul
      OUT
      jump

Code generation with JUMPSUB should also optimize away test_mul.

  TEST:
     MULTIPLY
     jumpsub
     returnsub

  MULTIPLY:
     mul
     returnsub

I think in both cases the multiply() function could be inlined, but then there would be no test.

Arguing with example code is not too helpful, in my opinion. This proposals allows to eliminate moving up the return address in the stack prior to returning and that’s it. If we just want to optimize for fewer swap operations on return, we could also introduce a “rotate stack” opcode. If we also want to improve static analysis capabilities, then I would propose the EIP to be strengthened (or maybe just clarified) by the following rule:

If a BEGINSUB is reached in any way except a JUMPSUB, it causes an out-of-gas failure. This includes:

  • directly jumping to the beginsub using jump or jumpi
  • reaching the BEGINSUB by continuing execution from the one prior to it without jumping
  • BEGINSUB being the first opcode

An even bigger improvement would be to disallow regular jumps into and out of subroutines, but I’m not sure if that would be a too drastic change.

I cannot elaborate on whether this change is worth it, since Solidity neither benefits much from it nor is it a big cost to switch to using these opcodes in the code generator (as long as dynamic jumps are still allowed). People working on debuggers (remix, truffle, etc), static analysis tools and VM implementations should answer that question.

I don’t understand. Doesn’t this proposal allow for remove the return address from the stack entirely?

Of course if we keep making improvements we could end up back at EIP-615, so I want to keep this minimal. Last we talked @holiman wasn’t even sure BEGINSUB was worth it.

I think the pre-population of “code_len” on the return stack is a bit of a hack. Why not just check if the stack is empty, and fail if so?

That would be more in line with how the existing data-stack is handled – if we try to pop an empty stack it results in an error. Whereas with this EIP, we rely on a second-level check to ensure that we jump to an invalid location and thus never have to deal with empty return-stack. Feels like an unnecessary hacky workaround to some problem I don’t quite see… ?

Regarding the EIP, I pushed a commit on the geth - PR, to repro the last testcase that is in the EIP. The code is thus:

		byte(vm.PUSH1), 0x4,
		byte(vm.JUMPSUB),
		byte(vm.STOP),
		byte(vm.BEGINSUB),
		byte(vm.PUSH1), 0x9,
		byte(vm.JUMPSUB),
		byte(vm.RETURNSUB),
		byte(vm.BEGINSUB),
		byte(vm.RETURNSUB),

And the trace from running it is:

Pc Op Cost Stack RStack
0 PUSH1 3 [] [11]
2 JUMPSUB 8 [4] [11]
4 BEGINSUB 1 [] [11, 2]
5 PUSH1 3 [] [11, 2]
7 JUMPSUB 8 [9] [11, 2]
9 BEGINSUB 1 [] [11, 2, 7]
10 RETURNSUB 2 [] [11, 2, 7]
8 RETURNSUB 2 [] [11, 2]
3 STOP 0 [] [11]

Your example traces are not quite correct, some offsets are wrong, and you consistently forget about that hack which adds an out-of-bounds entry to the return stack.

1 Like

Thanks, Martin! As we discussed, the hack probably needs to be made invisible so far as the spec goes. Whether it’s worth it in an implementation is another story. And whether it should show up in this trace is still another story. The hack causes a STOP to be actually executed, without the hack the program just stops.

I think you should remove it from the EIP. Leave it up to client implementations how they want to implement it, I’d personally prefer to check emptyness of returnstack.

If it’s mandated by the EIP, it should be in the trace and count towards the 1024 limit. If not in the EIP, it obviously should not.

I don’t agree, and this is actually not just a details. So as currently specced, and implemented in geth, the hack causes an out-of-bounds “jump”, which causes an error. Thus, doing RETSUB without a prior JUMPSUB causes same type of error as invalid jump – an all-gas-consuming revert.

So there are two questions here, and my pref is within brackets:

  1. Should “unbalanced” RETSUB cause error? (my pref: YES)
  2. Should we pre-fill the stack with out-of-bounds? (my pref: NO)

On a more high-level, I’d be curious to hear from @axic or @chriseth what they think about this EIP.

Chris wrote above some suggestions which would prevent “walking” into a subroutine or jumping into one. IMO that would be a mistake, but I’m curious to hear why it would be beneficial. As it is now, consider the following code, in pseudo-code;

func formula(a, b int) int{
    return add(a * a, b*b)
}
func add(a, b, int) int{
    return a + b
}

When translated to the evm, this could be implemented a tail return,

LABEL_FORMULA:
   // code to put `a*a` and `b*b` on stack
   ...
   JUMP LABEL_ADD

LABEL_ADD:
  BEGINSUB
  add
  RETSUB

For a perhaps better example, see The Go low-level calling convention on x86-64 · dr knz @ work , where a c compiler generates similar code

Compare how DoCallAdd works in C or C++:


DoCallAdd:
     movl    $3, %edx
     movl    $2, %esi
     movl    $1, %edi
     jmp     FuncAdd

In short, allowing jumps into subroutines enables infinite (tail-) recursion.

As I explained above: We should be clear about the obective of this EIP. If it concerns static analysis, then it does not go far enough. If it concerns efficiency, then it is only marginally better than introducing stack-rotating opcodes and those would have more use-cases than merely returning from subroutines.

Concerning optimizing tail recursion: While I see that this saves a jumpsub, I do not think that tail recursion is something common on smart contracts on EVM especially due to the fact that recursion itself is not recommended due to the stack limit. Even if tail calls could be optimized so that they do not exhaust the stack, there is no guarantee to the developer that this actually happened.

I’m not an expert on static analysis, but I would assume that knowing that a ‘BEGINSUB’ can only be visited by a coming from a JUMPSUB and thus ensuring a proper balance on the return pc stack is nice to have. Furthermore, if there is a guarantee that there are no cross-subroutine jumps, then you can analyze a subroutine in isolation which should reduce the complexity of static program analysis. If there is a certain aspect of the program that cannot really be analyzed (for whatever reason), then this fact spreads to the whole program, while it could be limited to a specific subroutine if cross-subroutine jumps are disallowed.

But to sum up again: My personal take on this is that the Solidity compiler can benefit from it by reducing the bytecode size (eliminating the stack rotations on return and the explicit return PC push for calls), but the EIP also does not force the use of JUMPSUB, so it is a very light burden on us. The people we should ask for their opinion is those who are writing debuggers and bytecode analyzers.

Also @gcolvin - somehow my reply to your question above did not get saved here, sorry about that: You are right, the proposal eliminates pushing the return PC as well as rotating the stack upon return.

It would be pretty simple to implement the “no walking into a subroutine” (i.e: you need to JUMPSUB to a BEGINSUB, if you hit it while just incrementing the PC, it’s an error). So that’s definitely doable, if people think it’s a good thing.

However, implementing the “no jumping into a subroutine” (i.e: prevent JUMP to land on a JUMPDEST) would be extremely hairy. No can do, without a rigorous validation scheme.

Thanks for the explanation, Christian. This proposal only provides a little help to static analysis, but it’s intended to be, in combination with forbidding dynamic jumps, just enough. The consequences of RETURNSUB after walking into a BEGINSUB would be undefined, and it’s easy to check that they should go into the spec.

Forbidding dynamic jumps is easy enough, but they also have legitimate uses, and we don’t want to go the route of EIP-615 and provide safe alternative opcodes for those. But if they are allowed I’m not sure how to easily ensure that code doesn’t jump into a subroutine. So this proposal leaves it to compiler and tool writers to enforce appropriate rules.

I’m confused enough here that I need to study things and then we can talk, @holiman. I don’t think the geth code matches the proposal, but I’m not sure the proposal is coherent either. Since the code works the spec should probably be changed to match it.

I have proposed some changes to the spec: https://github.com/ethereum/EIPs/pull/2576

For reference to anyone new, the original PR contained a lot of discussions too: https://github.com/ethereum/EIPs/pull/2484

I have asked this on the gitter channel a while ago, but it seems it was never recorded anywhere.

EIP-615 had a static version of JUMPSUB, e.g. the destination is an immediate. This posed a problem, to which versioning was proposed, and ultimately led to the then-rejection of EIP-615.

EIP-2315 has a dynamic version of JUMPSUB, e.g. takes the destination from the stack.

I would like to see a static version of this in the future and hence asked to consider that here and design the proposal with that in mind (to be consistent), that is to have both the static and the dynamic version of JUMPSUB, but not implement the static version of the opcode now.

If subroutines are dynamic jump themselves how is disabling other kinds of dynamic jumps helping?

What are the proposed gas costs of the new opcodes? The current version doesn’t seem to contain them.

I wasn’t clear hear, @axic, sorry. It would be up to external tools to enforce stronger guarantees, such as only constants being pushed before all kinds of jumps.

This proposal is not directly compatible with EIP-615 because without a version change arguments have to go on the stack. But given that EIP-615 will require a version change that shouldn’t be difficult to deal with in a few different ways, including changing how arguments are passed to the JUMPSUB and BEGINSUB opcodes, or adding new opcodes, or having the validation phase enforce guarantees rather than restrict the opcodes themselves.

They are there, under the Implementations section.

We suggest that the cost of BEGINSUB be base , JUMPSUB be low , and RETURNSUB be verylow . Measurement will tell. …

I slightly disagree. Introducing a new multibyte opcode is IMO not a huge problem. However, EIP-615 included a lot of assumptions about code, such that a runtime jump analysis should not be needed (because of deploy time validation), or a double-pass of a much more complicated analysis would have to be made during runtime.

If we were to introduce e.g. JUMPSUB 0x00ff (defining it as in total three bytes), I don’t see any huge problems with that … ?