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
the SSA transformation would be
a1 = 1
a2 = a1 + 1
b1 = a2
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
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.
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
a2 are actually the same variable: my last line could then be rendered as
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
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.