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.
• Replacement of any jump to a dead code line by a jump to whatever follow this line.

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