EIP-2315 Simple Subroutines for the EVM

Specification

  • JUMPSUB – Jumps to the address on top of the stack. This must be a JUMPDEST .
  • RETSUB – Returns to the most recently executed JUMPSUB instruction.

Rationale
This is the smallest possible change that provides native subroutines without breaking backwards compatibility…


Note: current draft includes a BEGINSUB opcode to use rather than JUMPDEST.

3 Likes

I’m probably just being slow but I don’t understand why this should be adopted, and the provided rationale doesn’t clear anything up for me. If it’s already possible to implement subroutines then as inelegant as the current situation might be why introduce a native subroutine mechanism? It can be implemented more efficiently, letting contracts have a lower gas cost? It makes static analysis on the resulting contracts easier? It unlocks other future changes with cool benefits?

Yes, lower gas costs. And yes, easier static analysis - you can know that the code is a subroutine call or return, rather than try to work it out by pattern matching Solidity or other conventions.

3 Likes

Pulling over from AllCoreDevs.

Tomasz Kajetan Stańczak @tkstanczak 06:22
@gcolvin would be good to have a test for nested JUMPSUB and a JUMPSUB nested in a CALL invoked from inside the subtoutine

@tkstanczak @holiman Here are a couple more test cases, probably wrong as I hurry to get out in the sun.

offset step op        stack
0      0    PUSH1 3   []
1      1    JUMPSUB   [3]
2      8    STOP      []
3      2    JUMPDEST  []
4      3    PUSH1 7   []
5      4    JUMPSUB   [7]
6      7    RETURNSUB []
7      5    JUMPDEST  []
8      6    RETURNSUB []

Program should STOP with an empty stack after 8 steps.

offset step op        stack
0      0    PUSH1 3   []
1      1    JUMPSUB   [3]
2      2    JUMPDEST  []
3      3    RETURNSUB []
1      4    JUMPSUB   []

Program should STOP with an empty stack after 4 steps, due to virtual zero at end of code.

I think the second one will cause InvalidJumpDestination exception (which is a good test case too).

offset step op        stack
0      0    PUSH1 3   []
1      1    JUMPSUB   [2]
2      2    JUMPDEST  []
3      3    RETURNSUB []
4      4    STOP   []

The idea here is to demand nothing, but simply provide a mechanism. For this EIP such demands will need to be made by other tools.

PUSH1 2 I assume. The second time this hits RETURNSUB it will pop the codesize left on the call stack and jump to the implicit 0 past the end of the code (at offset 5) and stop. It will never get to the STOP at offset 4.

contract fun {
    function multiply(uint x, uint y) returns (uint) {
        return x * y;
    }
    function test() returns (uint) {
        return multiply(2,3);
    }
}

Solidity:
   MULTIPLY:
      0x0
      dup2
      dup4
      mul
      swap1
      pop
      swap3
      swap2
      pop
      pop
      jump
   TEST:
      0x0
      RTN
      0x2
      0x3
      MULTIPLY
      jump
   RTN:
      swap1
      pop
      swap1
      jump

Comparable EIP-2315 or EIP-615:
   MULTIPLY:
       mul
       returnsub   
   TEST:
       0x2
       0x3
       MULTIPLY
       jumpsub
       returnsub
1 Like

Pros:

  • Less gas consumption
  • much easier for static analysis
  • better readability: concise and clear syntax
  • easier to maintain
  • less error prone
  • no hard fork needed

Cons:

  • nothing.This is how a machine should work.
1 Like

Optimized code from the latest solc does a better job with the multiply() function, which is a leaf. Non-leaf functions remain costly to get out of, as shown by adding a layer to the test.

contract fun {
    function multiply(uint x, uint y) public returns (uint) {
        return x * y;
    }
    function test_mul(uint x, uint y) public returns (uint) {
        return multiply(x,y);
    }
    function test(uint x, uint y) public returns (uint) {
        return test_mul(2,3);
    }
}

Here is what solc can do now with just jump:

1  MULTIPLY:   
5     mul
3     swap1
8     jump
=
17 gas

1  TEST_MUL:
5     0x00
5     RTN
5     dup4
5     dup4
5     MULTIPLY
8     jump
=
34 gas

1  RTN:
3     swap4
3     swap3
2     pop
2     pop
2     pop
8     jump
=
21 gas (twice)

   TEST:
5     0x00
5     RTN
5     0x02
5     0x03
5     TEST_MUL
5     jump
=
30 gas

123 gas TOTAL

But with jumpsub and returnsub only a third as much gas is needed.

1  MULTIPLY:
5     mul
3     returnsub
=
9 gas

1  TEST_MUL:
3     MULTIPLY
5     jumpsub
3     returnsub
=
12 gas

1  TEST:
3     0x02
3     0x03
3     TEST_MUL
5     jumpsub
3     returnsub
=
18 gas

39 gas TOTAL
1 Like

Surprised to see the optimizer doing such a bad job. But yeah this test case shows exactly how the subroutine features would benefit sophisticated situations like this.

I haven’t tried to hand-optimize the Solidity output, but I don’t think that it could do much better. It’s intrinsically difficult to handle subroutines without instructions for the purpose, as the history of CPU development pretty clearly shows.

I’m not sure what’s sophisticated here – just two function calls and one multiplication.

Some diggings: On Remix it is using Solidity compiler’s legacy optimizer, which cannot handle functions with calls to other functions, hence the non-optimized TEST_MUL function.

Hi @lialan The output above is from the latest solc.

Is static analysis that much easier if all the subroutine offsets are still dynamic (e.g. not an immediate on JUMPSUB)?

Better to say, some kinds of static analysis, @axic, as I’ve heard complaints about the problem of deciphering subroutines in EVM code, and the EIP gives a good example. Other kinds analysis don’t care.

The reason none of this optimised is that all functions are marked public. That means all of them need to made available externally. In a more realistic example, most of those would not be marked public and then they become inlined or better optimised.

@axic Thanks, I’ll try that. The public case is still relevant, but I also want to see what the limits are.