Lifetime tracking for temporary memory objects

[cameel]

Abstract

This issue proposes a mechanism for avoiding permanent memory allocation of memory objects that are immediately consumed and not used afterwards. The mechanism works at compilation time by generating code that writes to designated areas in unallocated memory space in a controlled manner, without the need to actually move the free memory pointer at runtime.

Motivation

There are many cases where the allocated memory is either never used (#12306) or could be freed immediately after use (#12335, #4182, #9046). Attempts to deal with them at Yul level (#5107) were unsuccessful so far because at that level we lose some semantic information about variables. Doing it in the code generator at the Solidity level is actually simpler.

This will make memory use less wasteful in many simple cases, e.g. the common keccak256(abi.encode(...)) pattern.

Specification

To be able to perform this optimization we need to classify certain elements of the AST:

• memory parameters of all callables (functions, modifiers, events, errors, constructors, etc.) and inputs of all types of expressions and statements are classified as either consuming or capturing. A memory object is captured if a reference to it remains stored a variable that survives the call. Otherwise we consider it consumed.
• memory return values in all expressions present in the source are classified as either temporary or permanent. The result is temporary if no other reference to the same memory object exists.

When a temporary object is passed into a consuming argument (which can be determined at compilation time), it is safe to destroy it immediately after the expression is evaluated.

If a permanent allocation of another memory object is necessary before the deallocation of a temporary, the optimization cannot be performed and the temporary is reclassified as permanent (forced permanent).

consuming and capturing arguments

• Parameters of user-defined functions and modifiers are always capturing.
  • We might be able to relax this rule later with extra analysis.
• Parameters of struct constructors and items in array literals are always capturing.
• Parameters of events and errors are always consuming.
• Parameters of builtins can be capturing or consuming - information about this must be hard-coded in the compiler.
• Parameters of built-in operators and statements can be capturing or consuming:
  • Right-hand-side of an assignment operator that assigns a reference is capturing.
  • Right-hand-side of an assignment operator that copies the whole object consuming.
  • delete operator is consuming.
  • Any operators and builtins that short-circuit their arguments (ternary operator, &&, ||, require()) are capturing.
    • This is a limitation that could be lifted at the cost of more complex code generation - see below.
  • Any arithmetic or comparison operator that takes or could potentially take memory objects as arguments is consuming. E.g. ==.
  • Parameters of all other built-in statements and operators are capturing.

temporary and permanent returns

• Return values of expressions that directly allocate memory are temporary. This includes operator new, struct constructors, array literals, ABI-encoding functions, etc.
• Any expression that consists only of a variable name is permanent.
• Return values of any other expressions are permanent. This includes user-defined functions, built-ins that do not directly allocate memory, any other operators that might be defined on memory objects, etc.

Implementation details

Analysis

At the analysis level we need some extra AST annotations:

1. lifespan: enum {Permanent, ForcedPermanent, Temporary, Unused} - on every memory return value of every expression.
   • To simplify the initial implementation, we treat all user-defined functions as doing permanent allocations and thus forcing temporaries to become permanent. We might be able to relax that rule later with extra analysis based on control flow graph.
2. temporaryHandling: enum {Consuming, Capturing} - on every memory argument of every expression.
   • Could also be calculated on the fly from semantic rules hard-coded in the codegen.
3. consumedTemporaries: list of AST node references - on every expression. Pointers to nodes representing any temporaries that can be deallocated after the expression is evaluated. Includes the result of the expression itself if it's unused.
   • In this initial version it could also be calculated on the fly in the codegen. This annotation plays a bigger role if we add pass-through arguments - see below.

Code generation

The optimization is performed for each statement in isolation. All allocations within the body are tracked using an internal stack (kept only at compilation time). The stack tracks sizes of temporary memory allocations in the order they are performed. The size can be in one of several variants:

• constant: for allocations of constant size known at compilation time. In this case we store the size directly.
• memory length prefix: for dynamic memory allocations where the the size is stored in the first slot of allocated memory (this is the case for dynamic arrays). In this case we store the address of the location of memory slot that stores the length and the type of the memory object (to be able to generate an expression that evaluates to size in bytes at runtime).
• unbounded: (optional) for temporary allocations performed by the code generator for its own purposes. These should be ephemeral and never happen outside of generated code but we could track them as a sanity check - such an allocation only ever makes sense on the top of the stack and anything else is a bug.

The optimization works as follows:

• We start with an empty stack, since temporaries cannot survive between statements.
• When an expression that returns a temporary is visited, a new item containing its size is pushed on the stack.
• The address returned by the allocating expression can be computred by summing up items on the stack. This produces an expression that evaluates to that value at runtime.
• When an expression with non-empty consumedTemporaries is visited, sizes of consumed temporaries are popped from the stack. As long as the analysis is performed correctly, it can be safely assumed that all of temporaries to be popped are at the top of the stack.

Limitations and possible extensions

Pass-through parameters

In the implementation described above only passing a temporary directly into a consuming argument lets us free it. A temporary will not be freed if it's parenthesized (e.g. (new uint[](5))), used in a tuple (e.g. (new uint[](1), new uint[](2), new uint[](3))), used in an array literal (e.g. [new uint[](1), new uint[](2), new uint[](3)]) or a struct constructor.

To deal with this case:

• Introduce a new type of parameter in addition to consuming and capturing: pass-through.
• Use pass-through for arguments of all the expressions mentioned above. I.e. expressions for which the temporary arguments can be safely deallocated at the point where all return values are deallocated.
• Consider the return values of the kinds of expressions mentioned above temporary in most cases:
  • An array literal or an invocation of a struct constructor returns a temporary (this is not transitive - the array/struct can store references to permanent objects and these won't be freed with it unless they are separately tracked as temporaries).
  • Parenthesized value is temporary IFF the value inside is temporary.
  • A tuple literal is considered temporary for the purposes of the analysis rule below (but obviously can't be freed since it's not a memory object itself). Just like arrays/structs the temporary designation is not transitive.
• In analysis:
  • When a temporary T is passed into a pass-through argument of expression X:
    • If any result of expression X is permanent or captured by some expression Y down the line, T becomes forced permanent.
    • If all results of expression X are temporary and consumed by expression Y, add T to consumedTemporaries annotation on the expression Y.
    • Both cases can propagate if all arguments of expression Y are also pass-through. The expression Z that eventually either captures T forcing it to become permanent or adds it to its consumedTemporaries can be several levels away.

Conditional allocation

The current syntax allows allocating memory in expressions that short-circuit, which results in conditional allocation. For example:

• condition ? new[](1) : new[](2)
• new uint[](2)[0] == new uint[](2)[0] && new uint[](2)[1] == new uint[](2)[1]
• require(condition, new uint[](2)[0] <= new uint[](2)[0] ? "a" : "b")

To be able to mark their arguments as pass-through or consuming, we need to replace the stack in the codegen with a binary tree where each node contains a stack. Then to calculate the address of a temporary we need to sum up not just a single stack but all stacks leading up to the tree root.

User-defined functions

The initial implementation forgoes many optimization opportunities when user-defined functions are involved:

1. Parameters of user-defined functions and modifiers are always capturing.
   • This could be improved with extra analysis to determine which parameters actually end up never assigned to variables (consumed) or returned directly or inside other temporaries (passed through).
2. Return values are permanent. It's not possible to return a temporary.
   • To handle this we would need to determine, the state of the stack of temporaries at every exit point from the function.
   • If there are multiple exits we would also need support for conditional allocation described above.
3. We treat all user-defined functions as doing permanent allocations, thus invalidating any temporaries created before calls to such functions.
   • We could use control flow graph to determine which functions are memory-neutral, i.e. do not actually move the free memory pointer.
   • Memory-neutral functions could still perform temporary allocations. To handle this the codegen, before a call to such a function, would push a new, virtual memory pointer to EVM stack (set to the current free memory pointer plus the size of all temporaries on its internal stack). The function would use it instead of the actual free memory pointer to avoid overwriting any temporaries still present outside of the call.

Backwards Compatibility

The change is transparent to the users and can only be observed through different gas usage or inline assembly. As such it's considered fully backwards-compatible.

[chriseth]

Another maybe simpler way is to do this at the level of functions: If all allocations inside a function turn out to be unused at the end of the function, we can store the free memory pointer on the stack at the beginning of the function and restore it at the end. This should also be stack-pressure-neutral.

[cameel]

I have updated the description. I thought I'd just update it for the case of allocation with length known only at runtime but then spent most of the day today trying to think my way out of various corner cases. For example turns out that consuming temporaries in anything that short-circuits (ternary op, bool ops, require()) is a real pain. I figured out ways around most of it but it complicates the mechanism and I suspect you won't like that so I have put it in a separate section about possible extensions instead. This way we have an option to ignore them and go for the basics. The basic version without any extensions is still enough to handle the most interesting cases like keccak256(abi.encode(...)), objects never assigned to a variable, assignments that copy memory to storage, etc. Has a ton of limitations regarding user-defined functions though.

The update to the base part mostly just removed the limitation for dynamic allocations and fleshed out the rules for marking stuff consuming/non-consuming/temporary/permanent. The rest are the optional extensions.

Another maybe simpler way is to do this at the level of functions: If all allocations inside a function turn out to be unused at the end of the function, we can store the free memory pointer on the stack at the beginning of the function and restore it at the end. This should also be stack-pressure-neutral.

The biggest problem with it is that a function may have conditions and multiple exits, and conditional allocation complicates the codegen part so I think just storing the free memory pointer won't be enough. I think we'd need a tree of stacks to handle it.

[github-actions]

This issue has been marked as stale due to inactivity for the last 90 days.
It will be automatically closed in 7 days.

[github-actions]

Hi everyone! This issue has been automatically closed due to inactivity.
If you think this issue is still relevant in the latest Solidity version and you have something to contribute, feel free to reopen.
However, unless the issue is a concrete proposal that can be implemented, we recommend starting a language discussion on the forum instead.