Subroutines and Static Jumps for the EVM

[gcolvin]

eip: 2315
title: Simple Subroutines for the EVM
status: Draft
type: Standards Track
category: Core
author: Greg Colvin
discussions-to: https://github.com/ethereum/EIPs/issues/2315
created: 2019-10-17

Simple Summary

Subroutines.

Abstract

This proposal introduces two opcodes to support subroutines: JUMPSUB and RETSUB.

Motivation

The EVM does not provide subroutines as a primitive. Instead, calls must be synthesized by fetching, adjusting and pushing the current program counter and jumping to the subroutine address; returns must be synthesized by getting the return address to the top of stack and jumping back to it.

Specification

Proposal

JUMPSUB

Jumps to the address on top of the stack. This must be a JUMPDEST.

RETSUB

Returns to the most recently executed JUMPSUB instruction.

Backwards Compatibility

These changes do not affect existing VM code..

Rationale

This is the smallest possible change that provides native subroutines without breaking backwards compatibility. It does not enforce validity like #615, but code that
_ pushes constants argument before every JUMP and JUMPI and
_ ensures that the data stack is the same size at the end of every basic block
is valid and will meet all of the #615 safety conditions. In particular, the Yellow paper defines five exceptional halting states. Valid code cannot violate states 3, 4, or 5.

1 Insufficient gas

2 More than 1024 stack items

3 Insufficient stack items

4 Invalid jump destination

5 Invalid instruction

Implementation

Jumps to and returns from subroutines are described here in terms of

• The EVM data stack, (as defined in the Yellow Paper).
• A return stack of program counters.
• The program counter PC which is the byte offset of the currently executing instruction.

Execution of EVM bytecode begins with one value on the return stack—code_size. Executing the virtual byte of 0 at this offset causes an EVM to stop. Thus executing a RETSUB with no prior JUMPSUB executes a STOP. A STOP or RETURN ends the execution of a subroutine.

Semantics are defined by the following pseudo-C code.

   uint256 data_stack[1024];
   uint16 return_stack[1024] = {code_size};
   byte code[code_size];

   while (PC < code_size) {
      switch opcode = code[PC];
      case jumpsub:
         push(return_stack,PC);
         PC = pop(data_stack);
         break;
      cast retsub:
         PC = pop(return_stack);
         break;
      ...
      case 0:
         stop();
      default:
         invalid_instruction();
      }
      ++PC;
   }

Costs & Codes

We suggest the cost of JUMPSUB should be low, and RETSUB should be verylow.
Measurement will tell.

We suggest the following opcodes:

0xbe JUMPSUB
0xbf RETSUB

Copyright and related rights waived via CC0.

[gcolvin]

Discussion of concepts here. Edits of live Google Doc here:
https://docs.google.com/a/ethereum.org/document/d/1y6qKjnlQ3zlxWs3s16I_LcSfJVGDE0lQp3I7UZPAxWc/edit?usp=sharing

[chfast]

Subroutine Max Frame Size Extension

In the current version of the draft we have check for stack overflow in runtime for every executing instruction (in practice it means at every jump). To lower the overhead, we can keep information how much stack is a subrountine using at most and do not allow to call it if the call could cause the stack overflow. That will limit runtime checks only to JUMPSUB/JUMPSUBV instructions.

Specification

1. Extend BEGINSUB specification with third parameter max_frame_size
   -- the maximum size of the stack frame the subroutine is allowed to use.

2. In the Validity section, after condition 6 add new conditions:

   6a. For JUMPSUB and JUMPSUBV the frame size + the max_frame_size of the BEGINSUB(s) to jump to is not greater than 1024.

   6b. The frame size is not greater than the max_frame_size of the enclosing subroutine.

3. In the Validating subroutines section, after

   // check for stack overflow
   if SP > 1024
       return false
   

   add

   // check for exiding the max_frame_size
   if SP > max_frame_size(return_pc)
       return false
   

[gcolvin]

I'm torn between increasing efficiency and not complicating the interface. Especially don't want to make programmers keep track of the stack use of every routine, even when they are not otherwise tight on stack. One thing to consider is that validation guarantees that determining max frame sizes can be done in one linear-time traversal of the code, just before execution. One such pass is likely anyway for a high-performance EVM.

[VoR0220]

I need to digest this some more, but initial reading, I think that while it definitely makes the EVM more complex, it also has the potential to make it both more performant and potentially more safe since formal verification will likely benefit from this.

[gcolvin]

Moved to PR in EIP repository: #187
Discussion here: #615