Can any JUMP* go into any subroutine? Also can JUMP from within a subroutine go into another subroutine?
What happens in the case of:
JUMPSUB
JUMP (and jumping into another subroutine)
RETURNSUB
One would assume RETURNSUB picks up the last item from the return_stack. However from an analysis point of view in this case a RETURNSUB within a subroutine block may not only mean returning from that block, but returning from within some other block.
Yes, RETURNSUB must always return to the address last pushed on the stack and pop it @axic, regardless of the block it’s in. So in your example the RETURNSUB is unreachable, and the code will return to the JUMPSUB when and if it hits some other RETURNSUB. I think that will amount to a loop until the code jumped to stops somehow.
This proposal doesn’t constrain the structure of the code much at all, it just provides an efficient mechanism.
If subroutines are dynamic jump themselves how is disabling other kinds of dynamic jumps helping?
Other kinds of dynamic jumps aren’t disabled by this proposal. It only provides a more efficient alternative way to implement subroutines.
Sorry I had a typo in my example. I meant:
BEGINSUB
JUMP <next>
RETURNSUB (1)
next:
JUMPDEST
RETURNSUB (2)
And then (2) returns to where BEGINSUB was first invoked.
Yes. So in that way, it’s possible to implement the type of tail recursion I talked about here: EIP-2315 Simple Subroutines for the EVM
The analysis of the EIP with two proposed changes: EIP-2315 "Simple Subroutines for the EVM" analysis. By @chfast, @gumb0 and @axic.
We decided to publish in separately because of the length of it and wish to receive direct responses to the proposed changes.
Here is a preliminary implementation to use subroutines for yul functions:
It needs much more work to get it properly working, but maybe you can already use the generated bytecode for testing.
Here is the asm.js binary: https://313936-40892817-gh.circle-artifacts.com/0/soljson.js
Thanks, Christian.
(20must20)
If I see correctly this kind of relies/follows the recommendations from EIP-2315 "Simple Subroutines for the EVM" - Analysis, because it relies on not-flowing into beginsub (at least in one place in the assembler)
Currently the following opcodes are proposed:
0xb2 BEGINSUB
0xb3 JUMPSUB
0xb7 RETURNSUB
I propose to use these instead:
0x5c BEGINSUB
0x5d RETURNSUB
0x5e JUMPSUB
The reason: there are 4 opcodes free between 0x5b and 0x60, and in the same block we have JUMPDEST.
Placing it randomly after LOG would mean we have more holes in the opcode table.
Much better.
(…20)
Indeed! As the linked analysis article correctly states, flowing into a subroutine is not a feature a code generator would use. So I did not really follow the recommendations, I just did it in a clean way which is the same as what is recommended in the analysis 
Optimizing code generators can do some very strange things. Subroutines here need not be contiguous regions of code.
In openethereum, we implemented this EIP in https://github.com/openethereum/openethereum/pull/11629, also added a test for checking the recursion stack limit:
PUSH <recursion_limit>
s: BEGINSUB
DUP1
JUMPI :c
STOP
c: JUMPDEST
PUSH1 1
SWAP
SUB
JUMPSUB :s
with recursion_limit=1024 stops, with recursion_limit=1025 reverts
There is some inconsistency between the test case and the spec in EIP-2315.
The spec says that BEGINSUB is not supposed to be executed and its execution will cause error. JUMPSUB will land on the next instruction after BEGINSUB.
However, the test case (and the current open-ethereum implementation) assumes BEGINSUB can be executed as a noop. JUMPSUB will land on the BEGINSUB instead of the next.
Note that I believe the spec makes more sense from the security perspective. It prevents unintended control flow behavior in EVM crossing routine boundaries.
List of issues:
BEGINSUB should not be executed (or return OUT_OF_GAS). But the last test case in the EIP spec (Subroutine at end of code) counts it executed with gas 1.
The test case in openthereum also assumes BEGINSUB can be executed. If following the spec, it should be something like this:
// PUSH2 <recursion_limit>
// PUSH1
// JUMP :b
// :s BEGINSUB
// :b JUMPDEST
// DUP1
// JUMPI :c
// STOP
// :c JUMPDEST
// PUSH1 1
// SWAP
// SUB
// JUMPSUB :s
The gas cost of JUMPSUB sets to low, but in the test case table, it is 8 (mid).
A further comment on this: I think there is some logic behind putting Cost and Codes under Implementation in https://eips.ethereum.org/EIPS/eip-2315, but usually EIPs put these definitions into the Specification and that is where most people expect to find them.
(Cost and Codes currently contains the opcode numbers and the gas costs.)
I suggest to do the same here.
Furthermore there is a discussion about gas costs here: https://github.com/ethereum/EIPs/pull/2669#discussion_r430053819
To briefly summarise:
Current costs are defined as "BEGINSUB be base (2) , JUMPSUB be mid (8) , and RETURNSUB be verylow (3)"
@holiman suggests: "I don’t see why RETURNSUB should be so cheap. I’d actually prefer it to be same as JUMPSUB – or, more specifically, that cost of(JUMPSUB+RETURNSUB) == cost of (JUMP + JUMP) . Which currently would put it at mid == 8"
I suggest that since JUMPSUB and RETURNSUB both need to push to/pop from the return_stack, they should be more expensive than JUMP (mid). Maybe the difference is not measurable too much, but still they should not be the same. I suggest mid + 1 or mid + 2 as a hunch.
I would argue that a RETURNSUB is inherently cheaper, since it doesn’t have to validate the destination. It just needs to pop a stack and set PC. I mean POP is cheap (pops one). So my hunch is 10 for JUMPSUB and maybe 3 or 5 for RETURNSUB.
True, jumpdest analysis is not stipulated/charged for prior to execution – we should consider addressing that another time.
Do you think there would be a reasonable benchmark establishing the overhead of JUMPSUB vs. JUMP or should we stay with our hunches only?