next up previous
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  

\fbox{
\begin{minipage}{10 cm}
\begin{description}
\item[{\bf Input:}] A basic b...
...t z} $\}$\ \\
\> {\bf return} $D \setminus L$\ \\
\end{tabbing}\end{minipage}}


DEAD CODE ELIMINATION consists of the following transformations

Dead code arises for a number of reasons.


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.

Example 1   On most machines 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 up previous
Next: Data-flow Analysis and Global Optimization Up: Introduction to three-address code optimization Previous: Code analysis.
Marc Moreno Maza
2004-12-02