Next: Data-flow Analysis and Global Optimization Up: Introduction to three-address code optimization Previous: Code analysis.

An overview of some basic optimization techniques

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.

Algorithm 1

DEAD CODE ELIMINATION consists of the following transformations

• Removal of any TAC statement x := y op z such that x is not referenced further in the program.
Dead code arises for a number of reasons.
• copy propagation is a common one.

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 * t1

can be replaced by
t6 := t4

Of 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.

• This is called Constant Folding.
• Constant folding can also be used to eliminate conditional branches.

Example 1   On most machines
• division is much more expensive than multiplication (8 times as slow is typical)
• and multiplication is typically 1-2 times as slow as addition.
For example the code

 t3:= t1 / y t4:= t2 / y

would be better executed as

 t5 := 1/y t3 := t1 * t5 t4 := t2 * t5

Example 2   Another common example is the fused multiply-add. On many architectures there is an instruction
fma R1,R2,R3,R4

which assigns
R1:=R2+R3*R4

and 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 ...

Next: Data-flow Analysis and Global Optimization Up: Introduction to three-address code optimization Previous: Code analysis.
Marc Moreno Maza
2004-12-02