EOF - JUMPF and non-returning functions

Abstract

This EIP allows for tail call optimizations in EOF functions (EIP-4750) by introducing a new instruction JUMPF, which jumps to a code section without adding a new return stack frame.

Additionally the format of the type sections is extended to allow declaring sections as non-returning, with simplified stack validation for JUMPF to such section.

Motivation

It is common for functions to make a call at the end of the routine only to then return. JUMPF optimizes this behavior by changing code sections without needing to update the return stack.

Knowing at validation time that a function will never return control allows for JUMPF to such function to be treated similar to terminating instructions, where extra items may be left on the operand stack at execution termination. This provides opportunities for compilers to generate more optimal code, both in code size and in spent gas. It is particularly beneficial for small error handling helpers, that end execution with REVERT: they are commonly reused in multiple branches and extracting them into a helper function is efficient, when there is no need to pop extra stack items before JUMPF to such helper.

Specification

Type section changes

We define a non-returning section as one that cannot return control to its caller section.

Type section outputs field contains a special value 0x80 when corresponding code section is non-returning. See Non-returning status validation below for validation details.

The first code section MUST have 0 inputs and be non-returning.

Execution Semantics

A new instruction, JUMPF (0xe5), is introduced.

1. JUMPF has one immediate argument, target_section_index, encoded as a 16-bit unsigned big-endian value.
2. If the operand stack size exceeds 1024 - type[target_section_index].max_stack_increase (i.e. if the called function may exceed the global stack height limit), execution results in an exceptional halt. This guarantees that the target function does not exceed global stack height limit.
3. JUMPF sets current_section_index to target_section_index and PC to 0, but does not change the return stack. Execution continues in the target section.
4. JUMPF costs 5 gas.
5. JUMPF neither pops nor pushes anything to the operand stack.

If the code is legacy bytecode, JUMPF instruction results in an exceptional halt. (Note: This means no change to behaviour.)

Code Validation

Let the definition of type[i] be inherited from EIP-4750 and define stack_height_min and stack_height_max to be the stack height bounds at a certain instruction during the instruction flow traversal.

• The immediate argument of JUMPF MUST be less than the total number of code sections.
• For each JUMPF instruction:
  • either type[current_section_index].outputs MUST be greater or equal type[target_section_index].outputs,
  • or type[target_section_index].outputs MUST be 0x80
• The stack height validation at JUMPF depends on whether the target section is non-returning:
  • JUMPF into returning section (type[target_section_index].outputs does not equal 0x80): stack_height_min and stack_height_max MUST be equal to type[current_section_index].outputs - type[target_section_index].outputs + type[target_section_index].inputs. This means that target section can output less stack elements than the original code section called by the top element on the return stack, if the current code section leaves the delta type[current_section_index].outputs - type[target_section_index].outputs element(s) on the stack.
  • JUMPF into non-returning section (type[target_section_index].outputs equals 0x80): stack_height_min MUST be greater than or equal to type[target_section_index].inputs.
• Stack overflow check at JUMPF: stack_height_max MUST be less than or equal to 1024 - types[target_section_index].max_stack_increase.
• JUMPF is considered terminating instruction, i.e. does not have successor instructions in code validation and MAY be final instruction in the section.
• The code validation defined in EIP-4200 also fails if any RJUMP* offset points to one of the two bytes directly following a JUMPF instruction.

CALLF instruction validation is extended to include the rule:

• Code section is invalid in case an immediate argument target_section_index of any CALLF targets a non-returning section, i.e. type[target_section_index].outputs equals 0x80.

Non-returning status validation

Section type MUST be non-returning if and only if the section contains no RETF instructions and no JUMPF instructions targeting returning sections (target section's status is checked via its output value in type section.) Note: This implies that section containing only JUMPFs into non-returning sections is non-returning itself.

Rationale

Allowing JUMPF to section with less outputs

An alternative rule for JUMPF stack validation could require the target section's outputs to be exactly equal to the current section's outputs. Under such rule, a particular target section (a shared "helper" piece of code) would only "match" sections (requiring some shared "helper" code to execute before returning) with the same number of outputs.

Instead, we allow a given JUMPF target section to be called from sections with more outputs, as long as these sections provide these extra stack elements (the "delta") themselves. This will reduce duplicated code as it will allow compilers more flexibility during code generation such that certain helpers can be used generically by functions, regardless of their output values.

Backwards Compatibility

This change is backward compatible as EOF does not allow undefined instructions to be used or deployed, meaning no contracts will be affected.

Security Considerations

This new instruction needs to be carefully considered during implementation of the EOF container validation algorithm.

Copyright

Copyright and related rights waived via CC0.