Principal Sources

of
OPTIMIZATION
Dr. ISLABUDEEN. M
Code Optimization

The code produced by the straight forward compiling algorithms can often be made to
run faster or take less space, or both. This improvement is achieved by program
transformations that are traditionally called optimizations.

Compilers that apply code-improving transformations are called optimizing compilers.

Code Optimization

The criteria for code improvement transformations

Simply stated, the best program transformations are those that yield the most benefit for
the least effort.

The transformations provided by an optimizing compiler should have several properties.

They are:

• The transformation must preserve the meaning of programs.

• A transformation must, on the average, speedup programs by a measurable amount.
• The transformation must be worth the effort.
Principal Sources of Optimization
• A transformation of a program is called local if it can be performed by looking
only at the statements in a basic block; otherwise, it is called global.

• Many transformations can be performed at both the local and global levels.

• Local transformations are usually performed first.

Function-Preserving Transformations
There are a number of ways in which a compiler can improve a program without
changing the function it computes.

Function preserving transformations examples:

• Common sub expression elimination
• Copy propagation
• Dead-code elimination
• Constant folding
Principal Sources of Optimization

Common Sub expressions elimination:

• An occurrence of an expression E is called a common sub-expression if E
was previously computed, and the values of variables in E have not changed
since the previous computation.
• We can avoid recomputing the expression if we can use the previously
computed value.
Principal Sources of Optimization

Examples for Common Sub expressions

Principal Sources of Optimization

Copy Propagation:
• Assignments of the form f : = g called copy statements, or copies for short.
The idea behind the copy-propagation transformation is to use g for f,
whenever possible after the copy statement f: = g.
• Copy propagation means use of one variable instead of another.
• This may not appear to be an improvement, but as we shall see it gives us
an opportunity to eliminate f.

Before Copy Propagation:

x = y;
z = x + 5;
Here, x is just a copy of y.
After Copy Propagation:
z = y + 5;
Now the redundant variable x is eliminated.

Presidency University, Bengaluru

Principal Sources of Optimization

Dead-Code Eliminations:
A variable is live at a point in a program if its value can be used subsequently;
otherwise, it is dead at that point. A related idea is dead or useless code, statements
that compute values that never get used.

Constant folding:
Deducing at compile time that the value of an expression is a constant and using
the constant instead is known as constant folding.
Principal Sources of Optimization

Examples for Dead-Code Eliminations:

x=0

if(x>0)
{
Dead Code
printfx(“X is greater than 0”);
}
else
{
printfx(“X = 0 or greater than 0”);
}

Then this can be replaced

x=0
printf (“X = 0 or greater than 0”);
Principal Sources of Optimization

Examples for Constant folding:

Area = 3.14*5*5;

This can be replaced by

Area = 78.5
Principal Sources of Optimization

Loop Optimizations:
In loops, especially in the inner loops, programs tend to spend the bulk of their
time. The running time of a program may be improved if the number of instructions
in an inner loop is decreased, even if we increase the amount of code outside that
loop.

Three techniques are important for loop optimization:

• Code motion, which moves code outside a loop.
• Induction-variable elimination, which we apply to replace variables from inner
loop.
• Reduction in strength, which replaces and expensive operation by a cheaper
one, such as a multiplication by an addition.
• Loop Unrolling, where the loop body is replicated multiple times to reduce loop
control overhead and increase instruction-level parallelism.
• Loop Jamming, where two or more adjacent loops with the same iteration space
are combined into a single loop.
Principal Sources of Optimization

Code Motion:
An important modification that decreases the amount of code in a loop is code
motion. This transformation takes an expression that yields the same result
independent of the number of times a loop is executed (a loop-invariant computation)
and places the expression before the loop.

while (i <= limit-2) /* statement does not change limit*/

Code motion will result in the equivalent of

t= limit-2;
while (i<=t)
Principal Sources of Optimization

Induction Variables :
An induction variable is a variable that gets increased or decreased by a fixed
amount on every iteration of a loop or is a linear function of another induction
variable.

A common compiler optimization is to recognize the existence of induction variables

and replace them with simpler computations

For example, in the following loop, i and j are induction variables.

Principal Sources of Optimization

Reduction In Strength:
Reduction in strength replaces expensive operations by equivalent cheaper ones on
the target machine.

Certain machine instructions are considerably cheaper than others and can often be
used as special cases of more expensive operators.

For example, x² is invariably cheaper to implement as x * x than as a call to an

exponentiation routine.

2 * X is replaced by X + X
Principal Sources of Optimization
Loop Unrolling
Loop unrolling is an optimization technique used in compiler design to improve the performance of
loops by reducing the overhead of loop control (like incrementing counters, checking conditions,
and branching).
Instead of executing the loop one iteration at a time, the compiler (or programmer) rewrites the loop
so that multiple iterations are performed within a single loop body.

Original Loop (before unrolling)

for (int i = 0; i < 8; i++) {
After Loop Unrolling (factor = 2)
A[i] = A[i] + 5;
for (int i = 0; i < 8; i += 2) { After Loop Unrolling (factor = 4)
}
A[i] = A[i] + 5; for (int i = 0; i < 8; i += 4) {
A[i+1] = A[i+1] + 5; A[i] = A[i] + 5;
} A[i+1] = A[i+1] + 5;
A[i+2] = A[i+2] + 5;
A[i+3] = A[i+3] + 5;
}
Principal Sources of Optimization
Loop Jamming (or) Loop Fusion
Loop jamming (or loop fusion) is a loop optimization technique where two or more adjacent loops
with the same iteration space are combined into a single loop.
The main purpose is to reduce loop overhead, improve data locality, and sometimes reduce cache
misses.

Before Loop Jamming:

for (int i = 0; i < n; i++) {
a[i] = b[i] + c[i];
} After Loop Jamming:
for (int i = 0; i < n; i++) {
for (int i = 0; i < n; i++) { a[i] = b[i] + c[i];
d[i] = a[i] * e[i]; d[i] = a[i] * e[i];
} }
Global Data Flow Analysis
• To do code optimization and code generation
• Compiler needs to collect information about the whole program
• Distribute it to each block in the whole program
• Data flow equations are the equations representing the expressions that
are appearing in the flow graph.
• Data flow information can be collected by setting up and solving systems
of equations that relate information at various points in a program.
• The data flow equation written in a form of equation such that,
out [S] = gen[S] U (in[S] − kill[S])
• Data flow equation can be read as “the information at the end of a statement is
either generated within a statement, or enters at the beginning and is not killed as
control flows through the statement”.
Path
• A path from p1 to pn is sequence of points p1, p2, …pn such
that for each i between 1 and n-1, either,
i. Pi – point immediately preceding the statement
Pi+1 – point immediately following that statement in the same
block

ii. Pi – End of some block

Pi+1 – beginning of a successor block
Reaching Definition
• A definition 𝐷 reaches at the point 𝑃 if there is a path from 𝐷 to 𝑃 along
which 𝐷 is not killed.
• A definition 𝐷 of variable 𝑥 is killed when there is a redefinition of 𝑥.
D1: y=2 B1

D2: y=y+2 B2

D3: x=y+2 B3

• The definition 𝐷1 is reaching definition for block 𝐵2, but the definition
𝐷1 is not reaching definition for block 𝐵3, because it is killed by
definition 𝐷2 in block 𝐵2.
Data Flow Properties
• A program point containing the definition is called Definition point.
• A program point at which a reference to a data item is made is called
Reference point.
• A program point at which some evaluating expression is given is called
Evaluation point.
W1:x=3 Definition point

W2: y=x Reference point

W3: z=a*b Evaluation point

Available Expression
• Determines the points in the program where a particular expression is “available”,
meaning that its value has already been computed and can be reused.
• An expression x + y is available at a point p, if every path from the entry node to p
evaluates x + y, and after the last such evaluation prior to reaching p, there are no
subsequent assignments to x or y.
B1: t1=4*i

B2: t2:c+d[t1] B3: t3=4*i

B4: t4=a[t3]

• Expression 4 ∗ 𝑖 is the available expression for 𝐵2, 𝐵3 and 𝐵4 because this expression
has not been changed by any of block appearing before 𝐵4.
Example - Computation of available
expressions
• After the first, b+c is available.
• After the second statement, a - d becomes available, but
b + c is no longer available, because b has been
redefined.
• The third statement does not make b + c available again,
because the value of c is immediately changed.
• After the last statement, a - d is no longer available,
because d has changed.
• Thus no expressions are generated, and all expressions
involving a, b, c, or d are killed
Live variable
• A variable 𝑥 is live at point 𝑝, if there is a path from 𝑝 to the exit, along
which the value of 𝑥 is used before it is redefined.
• Otherwise the variable is said to be dead at the point.
• Example:
b=3
c=5
a = f(b * c)
• The set of live variables are {b, c} because both are used in the
multiplication on line 3.
Busy Expression:
An expression 𝑒 is said to be busy expression along some path 𝑝𝑖. . 𝑝𝑗 if
and only if an evaluation of 𝑒 exists along some path 𝑝𝑖 … 𝑝𝑗 and no
definition of any operand exist before its evaluation along the path.
Dataflow analysis of structured programs
S → id:E | S; S | if E then S else S | do S while E
E → id+id | id
Example:
Data flow equations for reaching
definitions – [statement(s)]
Single Statement
Newly generated definition, d for a
All previous definition for a will be killed
except the newly generated definition, d

Sequence of Statements
Data flow equations for reaching
definitions – [if..else & loop]
Basic Block & Flow Graph
Basic Blocks
• A basic block is a sequence of consecutive statements in which flow of
control enters at the beginning and leaves at the end without halt or
possibility of branching except at the end.
• The following sequence of three-address statements forms a basic block:
t1 := a*a
t2 := a*b
t3 := 2*t2
t4 := t1+t3
t5 := b*b
t6 := t4+t5
Algorithm: Partition into basic blocks
Input: A sequence of three-address statements.
Output: A list of basic blocks with each three-address statement in exactly
one block.
Method:
1. We first determine the set of leaders, for that we use the following
rules:
a. The first statement is a leader.
b. Any statement that is the target of a conditional or unconditional goto is a leader.
c. Any statement that immediately follows a goto or conditional goto statement is a
leader.
2. For each leader, its basic block consists of the leader and all statements
up to but not including the next leader or the end of the program.
Example1: Partition into basic blocks
begin
prod := 0; Block B1 (1) prod := 0 Leader
i := 1; (2) i := 1
(3) t1 := 4*i Leader
do (4) t2 := a [t1]
prod := prod + a[t1] * b[t2]; (5) t3 := 4*i
(6) t4 :=b [t3]
i := i+1; (7) t5 := t2*t4
while i<= 20 (8) t6 := prod +t5
Block B2
(9) prod := t6
end (10) t7 := i+1
(11) i := t7
(12) if i<=20 goto (3)

Three Address
Code
Flow Graph
• We can add flow-of-control information to the set of basic blocks making up a program by
constructing a direct graph called a flow graph.
• Nodes in the flow graph represent computations, and the edges represent the flow of control.
• Example of flow graph for following three address code:

Construction of Flow Graph prod=0 Block B1

1. Draw directed edge from block1 to block2 if i=1
a. Conditional or unconditional jump from t1 := 4*i
block1 to block2 t2 := a [t1]
b. Block2 immediately follows block1 t3 := 4*i
Flow Graph t4 :=b [t3]
t5 := t2*t4 Block B2
t6 := prod +t5
prod := t6
t7 := i+1
i := t7
if i<=20 goto B2
Example2: Partition into basic blocks
Source code Intermediate code
Flow Graph
for i from 1 to 10 do
for j from 1 to 10 do
a[i, j] = 0.0;
for i from 1 to 10 do
a[i, i] = 1.0;
Basic Blocks
and
Flow Graphs
Dr. ISLABUDEEN. M
Basic Blocks and Flow Graphs

Basic Blocks
A basic block is a sequence of consecutive statements in which flow of control
enters at the beginning and leaves at the end without any halt or possibility
of branching except at the end.

The following sequence of three-address statements forms a basic block

t1 : = a * a
t2 : = a * b
t3 : = 2 * t2

Flow Graphs
Flow graph is a directed graph containing the flow-of-control information for the set
of basic blocks making up a program. The nodes of the flow graph are basic blocks.
Basic Blocks and Flow Graphs
Basic Block Construction:

Algorithm: Partition into basic blocks

Input: A sequence of three-address statements

Output: A list of basic blocks with each three-address statement in exactly one block

Method:

1. We first determine the set of leaders, the first statements of basic blocks. The rules we use are
of the following:
• The first statement is a leader.
• Any statement that is the target of a conditional or unconditional goto is a leader.
• Any statement that immediately follows a goto or conditional goto statement is a leader.

1. For each leader, its basic block consists of the leader and all statements up to but not
including the next leader or the end of the program.
Basic Blocks and Flow Graphs
Basic Blocks and Flow Graphs