2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

This sounds similar to register allocation. Normally, register allocation is done at the scope of a single function, but it can also be done globally (interprocedurally). If you ignore all recursive and mutually recursive calls, you might be able to apply standard algorithms for register allocation to your situation.

$\endgroup$
  • $\begingroup$ Don't at least some register allocation algorithms (like graph coloring) work only if you know the number of registers? $\endgroup$ – svick Jun 1 '17 at 20:10
  • $\begingroup$ @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. $\endgroup$ – D.W. Jun 1 '17 at 21:29
  • $\begingroup$ Register allocation is NP-complete, this algorithm is definitely not; I believe it's O(n), where n is the number of call-sites. I have an example implementation in scheme at github.com/dustmop/co2/blob/master/casla.scm. The code isn't that complicated, I assume I'm not the first person to come up with this, but I can't find any info about the algorithm. $\endgroup$ – dustmop Jul 20 '17 at 20:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.