Reduce number of temporary variables

Question

I'm writing something like a compiler. The problem is following: I have a code, consisting of a sequence of assignments:

    t1=a+b+c
    t2=t1*d
    t3=sqrt(t1+t2)
    t4=t2+5
    ...

most of "t"-variables are temporary. I want to reduce the number of temporary variables, re-using them as much, as possible. So, I need to rearrange the code, grouping expressions, having some variable as close to the variable assignment, so after computing those expressions the variable can be re-used. Of course, I want to preserve code logic during this procedure. Which is the best algorithm to do this?

The problem is one of 'register coalescing': http://en.wikipedia.org/wiki/Register_allocation — ArjunShankar, Oct 06 '12 at 11:31
One side note: While in the example you post, you already have true dependencies between the assignments, in many cases, 'reusing' variables is bad, and creates false dependencies that aren't really there. In fact, most optimizers start by rewriting code to a form where variables are *never* reused during assignment. It is called SSA: http://en.wikipedia.org/wiki/Static_single_assignment_form — ArjunShankar, Oct 06 '12 at 11:34

score 0 · Answer 1 · answered Oct 06 '12 at 11:33

You would look at the life span of the variables. When the variable is no longer used, you can discard it and reuse its memory space. For example:

t1=a+b+c
t2=t1*d
t3=sqrt(t1+t2)
// t1 is no longer used, free space to use for t4
t4=t2+5
// t2 is no longer used

...assuming only t3 and t4 is used later on

You could also look at variables with such a short lifespan that they don't even need to be allocated, for example:

t1 = a+b+c
t2 = t1 * 2

Here t1 is only used once, in the next statement, so you could just take the result of the previous calculation and use it:

t2 = (a+b+c) * 2

Yes, but it will be good to free variables as soon, as possible, so I want to rearrange initial code to make variables lifespans as short, as possible and looking for algorithm to do this. — Pavel, Oct 06 '12 at 11:41

Reduce number of temporary variables

1 Answers1