I'm creating a compiler static analysis module following the instructions of the classic book Compilers. Principles, Techniques and Tools by Ullman et alii.
I convert the AST representation into an three address code representation do the optimizations (basically dead code elimination and copy propagation for now) and then I convert into a similar three address code representation (more suitable to convert to bytecode).
For that, I have to create temporal variables so that my code representation looks like this:
t = IntLit(0)
t1 = left < right
t2 = !t1
cjump if t2 to L0:
t3 = number[right]
v = t3
t4 = left - IntLit(1)
i = t4
j = right
cont01 = True()
L2:
t5 = !cont01
cjump if t5 to L3:
cont02 = True()
L4:
t6 = !cont02
cjump if t6 to L5:
t7 = i + IntLit(1)
i = t7
t8 = number[t7]
Removed dead code: aux03 = t8
t10 = t8 < v
t9 = !t10
t11 = !t9
cjump if t11 to L6:
cont02 = False()
jump L7:
L6:
cont02 = True()
L7:
jump L4:
L5:
cont02 = True()
L8:
t12 = !cont02
cjump if t12 to L9:
t13 = j - IntLit(1)
j = t13
t14 = number[t13]
Removed dead code: aux03 = t14
t16 = v < t14
t15 = !t16
t17 = !t15
cjump if t17 to L10:
cont02 = False()
jump L11:
L10:
cont02 = True()
L11:
jump L8:
L9:
t18 = number[i]
t = t18
t19 = number[j]
number[i] = t19
number[j] = t18
t21 = i + IntLit(1)
t20 = j < t21
t22 = !t20
cjump if t22 to L12:
cont01 = False()
jump L13:
L12:
cont01 = True()
L13:
jump L2:
L3:
t23 = number[i]
number[j] = t23
t24 = number[right]
number[i] = t24
number[right] = t
t25 = i - IntLit(1)
t26 = This().Sort(left,t25)
Removed dead code: nt = t26
t27 = i + IntLit(1)
t28 = This().Sort(t27,right)
Removed dead code: nt = t28
jump L1:
L0:
Removed dead code: nt = IntLit(0)
L1:
return IntLit(0)
I wanted to get rid of temporal variables for code generation but I looks like I can't. Consider the following method:
def printing() : Int = {
var i : Int;
var j : Int;
var z : Int;
i = this.printing1();
z = i;
println(z);
return i;
}
I get the following code:
t1 = This().printing1()
Removed dead code: i = t1
Removed dead code: z = t1
println(t1)
return t1
What I'm doing to remove temporal variables is to propagate their value ahead. In normal situations I would just need one copy ahead. However, with copy propagation I may need to do it several times.
This should be no problem but combined with code elimination I cannot guarantee that method calls get assigned to non-temporal variables (look at the code above).
Therefore, when there is only one ahead occurrence of temporal variable storing method call result I can obviously copy the method call to it and end. When there isn't I can eliminate the result from the stack with a POP instruction. But when there are more than one occurrences I cannot copy the the instruction because I would get several calls.
My conclusion is that I need to keep temporal variables.
Is there another strategy which could help me to get reed of temporal variables?
I don't know if it is possible to get rid of all temporary variables using your current internal representation (i.e. the AST) but you may be able to reduce their amount using a register allocation algorithm.
It looks by your code that you generate a new temporal variable each time. This is similar to the problem when a compiler assumes (for simplicity) that the CPU has infinite registers. Then it has to generate code that actually uses the finite amount of registers the architecture has. To reduce from infinite registers/variables to a smaller, finite set, register allocation algorithms are used.
You may find a whole chapter (13) on the theme in the Engineering a Compiler by Keith Cooper book.
There is also lot of information on how this is done in real compilers like GCC.
What came to my mind is to think of variables as registers and then use a register allocation algorithm to reduce their number to a bare minimum.
This idea is obviously only my ten cents. Engineering a compiler is indeed a very complicated problem that would require in depth collaboration to solve your actual problem.