SUBJECT CODE

TYPE THE SUBJECT NAME HERE

UNIT NO 5
CODE OPTIMIZATION

5.1 Principle sources of optimization

III VI

20CSPC602
COMPILER DESIGN
 20CSPC602
COMPILER DESIGN
Principle sources of optimization
Code Optimization: Intro

Intermediate Code undergoes various transformations—called

Optimizations—to make the resulting code running faster and taking less
space.

Optimization never guarantees that the resulting code is the best possible.
We will consider only Machine-Independent Optimizations—i.e., they don’t take
into consideration any properties of the target machine.

The techniques used are a combination of Control-Flow and Data-Flow

analysis.
– Control-Flow Analysis. Identifies loops in the flow graph of a program since
such loops are usually good candidates for improvement.
– Data-Flow Analysis. Collects information about the way variables are used
in a program.
 20CSPC602
COMPILER DESIGN
Principle sources of optimization
Criteria for Code-Improving Transformations

The best transformations are those that yield the most benefit for the least
effort.
1. A transformation must preserve the meaning of a program. It’s better to
miss an opportunity to apply a transformation rather than risk changing
what the program does.
2. A transformation must, on the average, speed up a program by a
measurable amount.
3. Avoid code-optimization for programs that run occasionally or during
debugging.
4. Remember! Dramatic improvements are usually obtained by improving
the source code: The programmer is always responsible in finding the best
possible data structures and algorithms for solving a problem.
 20CSPC602
COMPILER DESIGN
Principle sources of optimization
Quicksort: An Example Program
We will use the sorting program Quicksort to illustrate the effects of the
various optimization techniques.
void quicksort(m,n)
int m,n;
int i,j,v,x;
if (n <= m) return;
i = m-1; j = n; v = a[n];
while (1)
do i = i+1; while (a[i]<v);
do j = j-1; while (a[j]>v);
if (i>=j) break;
x = a[i]; a[i] = a[j]; a[j] =x;

x = a[i]; a[i] = a[n]; a[n] =x /* fragment ends here */ quicksort(m,j);

quicksort(i+1,n);
 20CSPC602
COMPILER DESIGN
Principle sources of optimization
The following is the three-address code for a fragment of Quicksort.
 20CSPC602
COMPILER DESIGN
Principle sources of optimization

Basic Blocks and Flow Graphs

The Machine-Independent Code-Optimization phase consists of control-flow

and data-flow analysis followed by the application of transformations.

During Control-Flow analysis, a program is represented as a Flow Graph

where:

– Nodes represent Basic Blocks: Sequence of consecutive statements in

which flow-of-control enters at the beginning and leaves at the end
without halt or branches;

– Edges represent the flow of control.

 20CSPC602
COMPILER DESIGN
Principle sources of optimization
Flow graph for the three-address code fragment for quicksort. Each Bi is a
basic block.
 20CSPC602
COMPILER DESIGN
Principle sources of optimization

Sources of Optimization
1. Common Subexpression Elimination
2. Copy Propagation
3. Dead-Code Elimination
4. Constant Folding
5. Loop Optimization
 20CSPC602
COMPILER DESIGN
Principle sources of optimization

We distinguish local transformations—involving only statements in a single

basic block—from global transformations.

A basic block computes a set of expressions: A number of transformations can

be applied to a basic block without changing the expressions computed by the
block.

1. Common Subexpressions elimination;

2. Copy Propagation;

3. Dead-Code elimination;

4. Constant Folding.
 20CSPC602
COMPILER DESIGN
Principle sources of optimization

1. Common Subexpressions Elimination

Frequently a program will include calculations of the same value.

An occurrence of an expression E is called a common subexpression if E was

previously computed, and the values of variables in E have no changed since
the previous computation.
 20CSPC602
COMPILER DESIGN
Principle sources of optimization

Example. Consider the basic block B5. The assignments to both t7 and t10
have common subexpressions and can be eliminated.

After local common subexpression elimination, B5 is transformed as:

 20CSPC602
COMPILER DESIGN
Principle sources of optimization
 20CSPC602
COMPILER DESIGN
Principle sources of optimization

Example. The following flow graph shows the result of eliminating both
local and global common subexpressions from basic blocks B5 and B6
 20CSPC602
COMPILER DESIGN
Principle sources of optimization

Copy Propagation

Copy Propagation Rule: Given the copy statement x := y use y for x

whenever possible after the copy statement.

Copy Propagation applied to Block B5 yields:

This transformation together with Dead-Code Elimination (see next slide)

will give us the opportunity to eliminate the assignment altogether.
 20CSPC602
COMPILER DESIGN
Principle sources of optimization

Dead-Code Elimination

A variable is live at a point in a program if its value can be used subsequently,

otherwise it is dead.

A piece of code is dead if data computed is never used elsewhere.

Dead-Code may appear as the result of previous transformation.

Dead-Code works well together with Copy Propagation.

Example. Considering the Block B5 after Copy Propagation we can see that x
is never reused all over the code. Thus, x is a dead variable and we can
eliminate the assignment x := t3 from B5.
 20CSPC602
COMPILER DESIGN
Principle sources of optimization
Constant Folding

Based on deducing at compile-time that the value of an expression (and in

particular of a variable) is a constant.

Constant Folding is the transformation that substitutes an expression with a

constant.

Constant Folding is useful to discover Dead-Code.

Example. Consider the conditional statement: if (x) goto L

If, by Constant Folding, we discover that x is always false we can eliminate
both the if-test and the jump to L.
 20CSPC602
COMPILER DESIGN
Principle sources of optimization

Loop Optimization

The running time of a program can be improved if we decrease the amount of

instructions in an inner loop.

Three techniques are useful:

1. Code Motion

2. Reduction in Strength

3. Induction-Variable elimination
 20CSPC602
COMPILER DESIGN
Principle sources of optimization

Code Motion

If the computation of an expression is loop-invariant this transformation places

such computation before the loop.

Example. Consider the following while statement:

while (i <= limit - 2) do

The expression limit - 2 is loop invariant. Code motion transformation will result
in:
t := limit -2;
while (i <= t) do
 20CSPC602
COMPILER DESIGN
Principle sources of optimization

Reduction in Strength

It is based on the replacement of a computation with a less expensive one.

Result. The substitution of a multiplication by a subtraction will speed up the

resulting code.
 20CSPC602
COMPILER DESIGN
Principle sources of optimization

Induction Variables

A variable x is an Induction Variable of a loop if every time the variable x

changes values, it is incremented or decremented by some constant.

A common situation is one in which an induction variable, say i, indexes an

array, and some other induction variable, say t, is the actual offset to access the
array:

Often we can get rid of i.

In general, when there are two or more Induction Variables it is possible to get
rid of all but one.
 20CSPC602
COMPILER DESIGN
Principle sources of optimization

Induction Variables Elimination: An Example

Example. Consider the loop of Bock B3 . The variables j and t4 are Induction
Variables. The same applies for variables i and t2 in Block B2.

After Reduction in Strength is applied to both t2 and t4 , the only use of i and

j is to determine the test in B4.

Since t2 := 4 * i and t4 := 4 * j the test t2 > t4 is equivalent to i > j.

After this replacement in the test, both i (in Block B2) and j (in Block B3)
become dead-variables and can be eliminated.
 20CSPC602
COMPILER DESIGN
Principle sources of optimization
Flow Graph after Reduction in Strength and Induction-Variables elimination.