Advanced: Improve basic block matadata placement

[chfast]

Introduction to basic block metadata

The evmone/Advanced split instructions into basic blocks and pre-computes matadata of these basic blocks (base gas cost, stack usage). The metadata is then attach to the first instruction in the basic block.

The basic block creation is done by inspecting instruction kind:

1. JUMPDEST always starts new block.
2. Jumps (JUMP, JUMPI) and terminating instructions (STOP, RETURN, etc) end current block.

Because the JUMPDEST is often the first instruction in the basic block the metadata is attached to this instruction. However, if this is not the case additional "internal" instruction BEGINBLOCK is inserted (with metadata attached) to the program internal representation. This is problematic because the internal representation may be longer by unbound number of instructions than the original bytecode.

Improvement proposal

We should inspect individual block splitting instruction kinds.

1. JUMPDEST must continue to have metadata attached because any jump can target it. No change here.
2. The terminating instructions end execution and instructions after them are in "dead block" which are unreachable up to the next JUMPDEST. The instruction in "dead block" may be ignored, omitted or replaced with "unreachable" internal instruction.
3. JUMP always targets a JUMPDEST (with metadata) and there is a "dead block" after JUMP.
4. JUMPI may target a JUMPDEST. Otherwise the execution may continue to the next instruction after JUMPI. We should attach the metadata of the fall-though block to the JUMPI instruction.

Therefore: basic block metadata should be attached to JUMPDEST and JUMPI instructions without the need to insert additional internal instructions. Some instructions may be recognized as unreachable and end up in a "dead block".

Bonus: The metadata of the program entry block must be attached somewhere.

[gumb0]

Because the JUMPDEST is often the first instruction in the basic block the metadata is attached to this instruction. However, if this is not the case additional "internal" instruction BEGINBLOCK is inserted (with metadata attached) to the program internal representation.

Actually currently JUMPDEST is never inserted and BEGINBLOCK is always inserted and metadata is attached to it.

JUMPI may target a JUMPDEST. Otherwise the execution may continue to the next instruction after JUMPI. We should attach the metadata of the fall-though block to the JUMPI instruction.

But also JUMPI itself is the final instruction of the previous block, right? So this means in case of JUMPI, metadata is at the last instruction of previous block.

[chfast]

Actually currently JUMPDEST is never inserted and BEGINBLOCK is always inserted and metadata is attached to it.

Yes. During execution we can consider JUMPDEST and BEGINBLOCK as the same instruction. The distinction only matters during analysis.

But also JUMPI itself is the final instruction of the previous block, right? So this means in case of JUMPI, metadata is at the last instruction of previous block.

This is correct. But note that the block after a JUMPI is only reachable directly from the JUMPI block.