Compiler Design

Department of Computer Science

Mekelle University
Fkrezgy Yohannes (Ing.)

Compiler Design-Fkrezgy Y. 1
Code Optimization

Compiler Design-Fkrezgy Y. 2
 Code Optimization
• Why
– Reduce programmers’ burden
• Allow programmers to concentrate on high level concept
• Without worrying about performance issues
• Target
– Reduce execution time
– Reduce space
– Sometimes, these are tradeoffs
• Types
– Intermediate code level
• We are looking at this part now
– Assembly level
• Instruction selection, register allocation, etc.
Compiler Design-Fkrezgy Y. 3
 Code Optimization
• Code optimization is aimed at obtaining a more efficient code.
• Two constraints on the techniques used to perform
optimizations:
• They must ensure that the transformed program is semantically
equivalent to the original program.
• The improvement of the program efficiency must be achieved without
changing the algorithms which are used in the program.
• Optimization may be classified as machine dependent and
machine independent.
• Machine dependent optimizations exploit characteristics of the target
machine.
• Machine independent optimizations are based on the mathematical
properties of a sequence of source statements.
Compiler Design-Fkrezgy Y. 4
 When and Where To Optimize (1)
• Some techniques of optimization are applied to the
intermediate code, to streamline, rearrange, compress, etc. in
an effort to reduce the size of the abstract syntax tree or shrink
the number of TAC instructions.
• Others are applied as part of final code generation – choosing
which instructions to omit, how to allocate registers and
when/what to spill, and the like.
• An still other optimizations may occur after final code
generation, attempting to re-work the assembly code itself
into something more efficient.

Compiler Design-Fkrezgy Y. 5
 When and Where To Optimize (2)
• Generally, optimization can be very complex and time-
consuming; it often involves multiple sub-phases, some of
which are applied more than once..
• Most compilers allows optimization to be turned off to speed
up compilation.
• A Code optimizer sits between the front end and the code
generator.
– Works with intermediate code.
– Can do control-flow analysis.
– Can do data-flow analysis.
– Does transformations to improve the intermediate code.
Compiler Design-Fkrezgy Y. 6
 Factors Influencing Optimization
• The target machine: machine dependent factors can be
parameterized to compiler for fine tuning
• Architecture of Target CPU:
– Number of CPU registers
– RISC vs CISC
– Pipeline Architecture
– Number of functional units
• Machine Architecture
– Cache Size and type
– Cache/Memory transfer rate

Compiler Design-Fkrezgy Y. 7
 Themes behind Optimization Techniques
• Avoid redundancy: something already computed need not be
computed again.
• Smaller code: less work for CPU, cache, and memory!
• Less jumps: jumps interfere with code pre-fetch
• Code locality: codes executed close together in time is
generated close together in memory – increase locality of
reference
• Extract more information about code: More info – better
code generation

Compiler Design-Fkrezgy Y. 8
 Data-Flow Analysis
• It is the process of collecting information about the way the
variables are used , defined in the program.
• Analysis is done at basic block granularity.
• Collected information is represented as a set of data flow
equations
• Useful for performing several optimizations such as constant
propagation and copy propagation.
• Different Data flow problems:
 Reaching Definition Analysis
 Live Variable Analysis
 Use-Definition chains(UD chains)
 Definition-use chains(DU chains)
Compiler Design-Fkrezgy Y. 9
 Classes of Optimization
• Optimization techniques can be separated into two general
classes:
– Local Optimization: concerned with transformations on
small sections of code (involving only few instructions)
and generally operate on the machine language instructions
which are produced by the code generator.
– Global Optimization: concerned with large blocks of
code, or even multiple blocks or modules, and will be
applied to the intermediate form, atom strings, or syntax
trees put out by the parser.
• Both local and global optimization phases are optional, but
may be included in the compiler.
Compiler Design-Fkrezgy Y. 10
 Optimization Transformations/
Techniques (1)
• Global Optimization:
– Optimizations provided by a compiler includes:
A.Eliminating common sub-expressions
• An expression need not be evaluated if it was
previously computed and values of variables in this
expression have not changed since the earlier
computation. T1 = b * c;
a = b * c;
a = T1;
.
.
.
.
.
.
d = b * c + x – y;
d = T1 + x – y;
Compiler Design-Fkrezgy Y. 11
 Optimization Transformations (2)
B. Variable propagation:
• If a variable is assigned to another variable, we use one in
place of another.
• This will be useful to carry out other optimization that
were otherwise not possible.
c = a * b;
x = a;
.
.
d = x * b;
• Here, if we replace x by a then a*b and x*b will be
identified as common sub-expression.
Compiler Design-Fkrezgy Y. 12
 Optimization Transformations (3)
C. Dead Code Elimination:
• If the value contained in a variable at that point is not used
anywhere in the program subsequently, the variable is said
to be dead at that place.
• If an assignment is made to a dead variable, then that
assignment is a dead assignment and it can be safely
removed from the program.
• A piece of code is said to be dead if it computes values that
are never used any where in the program.
• Dead code can be eliminated safely.
• Variable propagation often leads to making assignment
statements into dead code.
Compiler Design-Fkrezgy Y. 13
 Optimization Transformations (4)

c = a * b; c = a * b;
x = a; x = a;
. .
. .
. .
d = x * b + 4; d = a * b + 4;

• This assignment x = a is now useless and can be removed.

Compiler Design-Fkrezgy Y. 14
 Optimization Transformations (5)
D. Compile Time Evaluation:
• Expressions whose values can be pre-computed at the
compilation time.
• We can improve the execution efficiency of a program by
shifting execution time actions to compile time.
• We can evaluate an expression by a single value (known as
Constant folding).
• Example: A = 2 * (22.0/7.0) * r
• Here we can perform the computation 2 * (22.0/7.0) at
compile time itself.

Compiler Design-Fkrezgy Y. 15
 Optimization Transformations (6)
– If a variable is assigned a constant value and is used in an
expression without being assigned other value to it, we can
evaluate some portion of the expression using constant
value (known as constant propagation)

– Example: x = 12.4;
.
.
.
y = x /2.3;

– Here we evaluate x/2.3 as 12.4/2.3 at compile time.

Compiler Design-Fkrezgy Y. 16
 Optimization Transformations (7)
E. Loop optimizations: (Code motion, Induction variable
elimination, and Strength Reduction.)
• Code motion:
• Moving code from one part of the program to other without
modifying the algorithm:
• Reduce size of the program
• Reduce execution frequency of the code subjected to
movement
• Loops are usually executed several times.
• We can bring the loop-invariant statements out of the
loop.
Compiler Design-Fkrezgy Y. 17
 Optimization Transformations (8)
i. Execution frequency reduction: Move expression out of
a loop if the evaluation does not change inside the loop.

• The statement b= x+y is executed every time with the

loop. But because it is loop-invariant, we can bring it
outside the loop. It will then be executed only once.
Compiler Design-Fkrezgy Y. 18
 Optimization Transformations (9)
ii. Code Space reduction: Similar to common sub-
expression elimination but with the objective to reduce
code size.

Example: Code hoisting

temp : = x * 2
if (a< b) then if (a< b) then
z := x * 2 z := temp
else else
y := x * 2 + 10 y := temp + 10

• “x * 2“ is computed once in both cases, but the code size in

the second case reduces.
Compiler Design-Fkrezgy Y. 19
 Optimization Transformations (10)
• Strength Reduction:
– Replacement of an operator with a less costly one.
Example:

X2 = X * X
2.0 * X = X + X
X / 2 = X * 0.5

• Typical cases of strength reduction occurs in address

calculation of array references.
• Applies to integer expressions involving induction variables
(loop optimization)
Compiler Design-Fkrezgy Y. 20
 Optimization Transformations (11)
F. Use of Algebraic Identities:
– Certain computations that look different to the compiler
and not identified as common sub-expressions are actually
same.
– An expression B op C will usually be treated as being
different to C op B.
– However, for certain operations (like addition and
multiplication), they will produce the same result.
– We can achieve further optimization by treating them as
common sub-expressions for such operations.

Compiler Design-Fkrezgy Y. 21
Optimization Transformations (12)

X+0≡0+X≡X
X–0≡X
X*1≡1*X≡X
X/1≡X

Compiler Design-Fkrezgy Y. 22
 Optimization Transformations (13)
Local Optimization:
• Target code generated statement by statement generally contains
redundant instructions.
• We can improve the quality of such code by applying optimizing
transformations locally by examining a short sequence of code
instructions and replacing them by faster or shorter sequence, if
possible.
• This technique is known as Peephole Optimization where the
peephole is a small moving window on the program.
• Many of the code optimization techniques can be carried out by a
single portion of a program known as Basic Block.

Compiler Design-Fkrezgy Y. 23
 Conti…

Compiler Design-Fkrezgy Y. 24