DETERMINING USELESS NAMES OF A BASIC BLOCK. In the following algorithm, for a basic block B we assume that lives(B) is the set of the variables appearing in B that are referred in a basic block B' following B in the CFG.
DEAD CODE ELIMINATION consists of the following transformations
COMMON SUBEXPRESSION ELIMINATION Consider the following TAC.
t1 := 4 - 2 | |
t2 := t1 | |
t3 := a * t2 | |
t4 := t3 * t1 | |
t5 := t4 + b | |
t6 := t3 * t1 | |
t7 := t6 + b | |
c := t5 * t7 | |
Note that the values of t1 and t3 cannot change between the two computations of t4 and t6. Hence the line
t6 := t3 * t1can be replaced by
t6 := t4Of course this is a fairly trivial case. But a compiler could recognize much more complex common subexpressions.
COPY PROPAGATION.After a statement x := y we know that x and y have the same value, we can replace all occurrences of x with y between this assignment and the next definition of y.
Copy propagation makes further subexpressions elimination possible.
ARITHMETIC TRANSFORMATIONS. If possible, arithmetic expressions should be computed at compile time.
t3:= t1 / y | |
t4:= t2 / y | |
would be better executed as
t5 := 1/y | |
t3 := t1 * t5 | |
t4 := t2 * t5 | |
fma R1,R2,R3,R4which assigns
R1:=R2+R3*R4and runs in the time of a single multiply. If we can re-order code to recognize such opportunities we can significantly improve common loops.
PACKING TEMPORARIES. We can replace two distinct temporaries by a single one if they are not simultaneously live. For example the code
t4 := a + a | |
t5 := t4 + b | |
c := t5 * t5 | |
would be better executed as
t1 := a + a | |
t1 := t1 + b | |
c := t1 * t1 | |
One of the main difficulties is deciding in which order to apply these optimizations, and how many times to apply them ...