VIP: venom dynamic memory semantics & built ins

[Philogy]

Simple Summary

Dynamic allocations and memory use are key for more complex contracts and patterns.

Motivation

With that comes the challenge of how frontends can give the compiler structured information about memory use to enable optimization passes without making the IR overly complex.

For dynamic allocations let's first define some core concepts:

• Static memory start offset: this is the memory offset the frontend as well as the IR should use to add/remove static memory allocations. Even with dynamic memory static allocations are still necessary to avoid stack-too-deep errors
• Scratch space: a static area of memory used to build small bytes sequences and hashing, this can either be implicitly defined (via various offset definitions that leave a gap) or just be part of the static area
• Free memory pointer (FMP): similar to Solidity the suggested memory allocation model is a simple bump allocator, where memory allocations are simple but deallocations become non-trivial without other analyses
• FMP start: While the FMP needs a fixed allocation the IR should have a way to initialize the free pointer in such a way

Specification

The changes are here are for the Venom IR

New Top Level Definitions

• free_memory_slot: uint: The memory offset for the word which will store the free memory pointer
• static_memory_start: uint: The memory offset at which the IR may place an arbitrary number of static variables into memory

New Builtin Instructions

• init_free_pointer() -> (): Initializes the free memory pointer, setting it to the end offset of the last static allocation. This builtin should effectively translate into mstore(fmp_slot, static_memory_start + max(static_allocation_ends)). Making this explicit and part of the control flow ensures that initializing memory for dynamic allocations is optional and can be left out for functions & code sections that do not need it.
• malloc(size: uint) -> (ptr: uint): Takes in a size in bytes and returns a the new memory offset at which the allocation lives. Should translate into ptr = mload(fmp_slot); mstore(fmp_slot, add(ptr, size));. The add should be unchecked, it should be delegated to the frontend to add checks ensuring that size is such that cumulative malloc invocations do not lead to the FMP wrapping around
• mhold() -> (ptr: uint): Retrieve the FMP without making an allocation. Used to signify that the value is a memory pointer but with a short lifetime. Should translate into ptr = mload(fmp_slot)

New IR Soundness Rules

• init_free_pointer must not be present more than once in any basic block
• init_free_pointer may not be placed such that any valid path through the CFG will encounter more than one init_free_pointer
• malloc and mhold must only be present in basic blocks that either:
  • contain an invocation to init_free_pointer before the dynamic memory instruction
  • are only reachable via paths that invoke init_free_pointer exactly once
• the offset parameter in palloca & alloca must be greater than or equal to static_memory_start
• static_memory_start must be greater than or equal to free_memory_slot + 0x20

Backwards Compatibility

Introduces new features but shouldn't create backwards incompatibilities.

Dependencies

N/A

References

N/A

Copyright

Copyright and related rights waived via CC0

[charles-cooper]

i don't think we really need a memory slot for the fmp, it's just a variable