How to assign unique names to variables within a function?

Question

I want to promote all variables within the function to the top level of the function, make it more cache-friendly and reduce size bloat caused by alignment fill.

In other words, it will roughly allocate a structure like this

#align(4)
struct FunctionArea {
    // fields of return value
    return: T3
    // fields of input parameters
    in1: T1,
    in2: T2,
    // fields of local variables
    a1: A
}

But I'm having trouble figuring out which local variables are needed.

The difficulty is that I allow

1. shadow variable: the inner variable has the same name as the outer variable, but may occupy different spaces
2. move variable: variables have different names but occupy the same space

---

For example:

fn f(in1: T1, in2: T2) -> T3 {
    let a1: A = default;
    {
        let a1: A = default; // shadow 
        let a2: A = a1;      // move
        {
            let a2: A = default;    // shadow
            let a3: A = a1.clone(); // not move
        }
    }
}

This makes it impossible to use a simple counter to count which variables need to allocate memory space.

Question

How to accurately count which fields need to be created under move and shadow semantics?

There is no need to consider constants.

Answer 1

The conventional approach in compilers to this is a combination of conversion to static single assignment form and register allocation. Both the shadowing and the moving will be addressed automatically.

In SSA, the left-hand side of every assignment is a unique variable: given

a = 1
a = a + 1
b = a
print(b)

the SSA transformation would be

a1 = 1
a2 = a1 + 1
b1 = a2
print(b1)

In practice, it's common that the created variables are just numbered sequentially without names. For things like branches and loops, the formal definition uses "φ (phi) nodes" to define variables that draw from whichever predecessor is on the true execution path, but you can just treat that as multiple assignments to those specific variables at the end of the branch if you prefer.

The original names of the variables don't matter at this point and the new names are all unique, so your shadowing issue has already been dealt with. However, we now have more variables than we started with, and we'd like to get that back down to something reasonable. For that we'll use register allocation: while that's originally intended for hardware registers, it works just as well here, and we'll just assume we always have an additional register available when it's required.

There are several different register-allocation algorithms, and the problem is NP-hard, but for your purposes the simple linear Poletto algorithm is probably sufficient. In SSA form, we trivially know the lifetime of every variable (from first assignment to last read). The linear allocation algorithm proceeds from the top of the code downwards, allocating a new register (variable) for each overlapping lifetime it encounters, and returning one to the pool when its lifetime ends: for my example above, a1 lives for lines 1-2, and a2 for lines 2-3: a1 passes out of existence just before a2 needs to store something, so we can use the same storage location for both; we might just call this location a.

At the end of the process, we know the total number of storage slots required is the number of currently-allocated spaces plus the number of expired slots sitting in the pool. All of those can be preallocated at the top of the function.

---

For my b = a line we'll assume move semantics. a2 thus passes out of existence on the same line that b1 is assigned, so they'll also share the same storage — but in that case the assignment doesn't do anything, so we remove it entirely! Variables b1 and a2 are actually the same variable: my last line could then be rendered as print(a2) instead.

Whenever I'm "moving" a value, what I'm really doing is changing the name the source language uses to refer to it, while the value itself stays still; this is exactly the opposite of intuition here, but it falls out of the SSA/register allocation approach innately. You could do this during the SSA generation itself, so that a move of x into y just causes name y to translate to the same variable as x for the rest of its scope, or leave it for register allocation, depending on your implementation specifics, but either way the result is the same.

Your clones are simply ordinary operations on values, producing a new result, so they'll non-destructively use the old variable and produce a new one too.

This approach will use the minimum number of variables in total (approximately; the linear algorithm is not optimal), so your total stack size can be minimal; this will actually join unrelated non-overlapping variables into one, so it may be fewer than expected. If you have multiple incompatible storage classes (e.g. float/double), you can continue to segregate those, of course. If you need truly minimal space occupancy in all cases, the other graph-based register allocation algorithms will do a better job at the cost of more execution time and implementation complexity.