---
# System prepended metadata

title: Untitled

---

memory escalation for acyclic call graphs
-----------------------------------------

The template for our runtime objects looks like this:
```
			object "<RuntimeObject>" {
				code {
					<memoryInit>
					<dispatch>
					<runtimeFunctions>
				}
				<runtimeSubObjects>
			}
```

So on external call entry points the first thing happening is writing to the free memory pointer, even before the dispatch.
- Without changing this, statically analyzed memory slots for escalating variables have to be shared between all functions.
- Furthermore static allocation for those slots is only possible if the subgraph of the call graph between the contract entry point and the function in question is acyclic (i.e. there are no recursive calls).
- The most primitive way to allocate such slots would be to make them globally unique for each local variable. But that's overhead for *every* call, so we should try to do better.

As a first step we mark all function arguments or local variables that are not reachable from the stack. Using that information we can mark functions as needing memory escalation.

If the call graph from the external entry point to a marked function contains a directed cycle we have to abort code generation.
Note: The call graph will likely contain undirected cycles as soon as any function is re-used from multiple call sites, but that's not a problem as long as there are no directed cycles, which happen for directly or mutually recursive calls.


So the basis now is the following **directed graph**:
- The root of the graph is the external contract entry point.
- The leaves are functions that need memory escalation.
- Paths from roots to leaves may contain more functions needing escalation.
- There are undirected cycles in the graph, but no directed cycles.


Simplest algorithm:
-------------------
Just sort the functions needing memory escalation by their name and assign globally unique slots to all variables that need memory escalation. Quite wasteful. Requires one reserved memory slot for each escalated variable for every call to the contract.

Prototypical case:
------------------
```
{
    <memoryInit>
    switch <signatureReadFromCalldata>
    case <sig1> {
        f()
    }
    case <sig2> {
        g()
    }
    case <sig3> {
        h()
    }
    function f() {
        fg()
    }
    function g(a1, ... a17) { // a1 needs escalation
        fg()
    }
    function fg() {
        let b1 := ... // needs escalation
        ...
        let b16 := ...
        ...
        
    }
    function h() {
        let freeMem := mload(0x40)
        ...
        switch ...
        case 0 { h1() }
        case 1 { h2() }
    }
    function h1() {
        let c1 := ... // needs escalation
        let c2 := ... // needs escalation
        ...
        let c17 := ...
        ...
        h3()
    }
    function h2() {
        let d1 := ... // needs escalation
        ...
        let d16 := ...
        ...
        h3()
    }
    function h3() {
        let e1 := ... // needs escalation
        ...
        let e16 := ...
    }
}
```

General idea for an algorithm
-----------------------------

- We want to initialize the free memory pointer as late as possible, so we move the initializing down the call graph up until before the first functions that read from memory (could exclude scratch space) or need escalation.
- We start at the leaves of the callgraph, moving backwards along paths.
- We can assign slots starting from zero at the leaves and move the call paths backwards as long as we don't hit a node with multiple out-edges - if we encounter such a node we store it in a list and stop with this path.
- Once all paths are processed we start again at the nodes stored in the list. We merge the maximum slot IDs assigned in their out-edges and continue assigning as before starting from that maximum plus one and start again.
- Whenever we hit a free memory pointer initialization we know the maximum memory slot needed and can therefore finalize the initialization and stop.


Formal algorithm for slot assignment
------------------------------------

TODO: change the traversal to be robust against cycles in parts that don't need escalation - or restrict the visit to paths that need escalation somewhere (i.e. look at the spanned acyclic subgraph)

We look at the directed call graph with edges starting from the transaction entry point. Vertices are yul functions.

Step 1 (optional):

- Optional: Traverse the call graph descending into functions. Once a function that does an ``mload`` or has variables requiring escalation is encountered, mark it as "needs memory init" and stop traversing this path.
- If not, then mark the entry node as "needs memory init"


Step 2:

- Let ``V`` be a set of vertices iniitalized with all nodes of the graph with no out-edges.
- Let ``next_available_slot :: V -> int`` be a map from vertices to integers initialized with zero for all veritces.
- for each ``v`` in ``V``:
  - let ``n`` be the maximum value of ``next_available_slot`` of the vertices along the outedges of ``v``.
  - assign slots to all variables that need memory escalation in the function corresponding to ``v`` in some deterministic order starting from ``n``. Store the maximum used slot  plus one in ``next_available_slot[v]``.
  - If ``v`` is not marked as ``needs memory init``, store all vertices along the inedges of ``v`` in ``V``.

Step 3:
- at every node marked "needs memory init" initialize memory while reserving ``next_available_slot[v]`` slots for memory variables.

***Need to verify***:
    - Doublecheck that this always works if escalated variables are accessed in a function *after* a call to another function escalating variables and with multiple calls in a function.

At the example above:
- Step 1: If we want late memory initialization we mark ``g``, ``fg`` and ``h`` as needs free memory init - otherwise the root node.
- Step 2: we start with ``V = {fg, h3}``.
  - ``fg``:
    - ``n`` is zero
    - assign slot 0 to ``b1``
    - store ``next_available_slot[fg] = 1``
    - Add ``f`` and ``g`` to ``V``.
  - ``h3``:
    - ``n`` is zero
    - assign slot 0 to ``e1``
    - store ``next_available_slot[h3] = 1``
    - Add ``h1`` and ``h2`` to ``V``.
  - ``f``:
    - ``n`` is one
    - we can add free memory init with one reserved slot here or traverse further without anything new happening to the root contributing 1 to the maximum there.
  - ``g``:
    - ``n`` is one
    - We assign slot 1 to ``a1``
    - store ``next_avaiable_slot[g] = 2``.
    - we add the root node to ``V``
  - ``h1``:
    - ``n`` is one
    - Assign 1 to c1 and 2 to c2
    - store ``next_avaiable_slot[h1] = 3``.
    - add ``h`` to ``V``
  - ``h2``:
    - ``n`` is one
    - Assign 1 to d1
    - store ``next_avaiable_slot[h1] = 2``.
    - add ``h`` to ``V`` (noop, already there)
  - ``h``:
    - ``n`` is max(3,2) = 3.
    - initialize free memory here or contribute 3 to the maximum at the root
  - ``root``:
    - only reached, if we don't opt for late memory initialization. Has a maximum of 3 for slot initialization

