# Local variables get assigned global addresses based upon call tree

When working with certain low-powered / embedded CPUs that are bad at using the stack, I need to avoid putting local variables there, instead opting to make them static variables. But this can waste a lot of address spaces since not every local in every function needs their own unique address. Rather, by looking at the call tree, functions that do call each other can share memory space.

For example, given code such as this:

void A() {
int x;
// ...
B();
C();
// ...
}

void B() {
int y;
// ...
}

void C() {
int z;
// ...
}


The variables y and z can be assigned the same address, while x should be unique so that calls to B() and C() don't clobber it.

Obviously this breaks recursion and multi-threading, but neither of those are a problem for the use cases I'm working in.

Is there a name for this algorithm? I'm assuming that it's well known, but it's very hard to search for information about this specific problem.

• @svick, some adaptation might be required. (For instance, one could do a search to find the smallest $n$ such that $n$ registers suffice. Smarter algorithms might be possible.) I don't know if you'll find a complete answer to this exact problem. – D.W. Jun 1 '17 at 21:29