Module VI

Code Optimization

Prabhu Prasad Dev

Assistant Professor
School of Computer Engineering
KIIT Deemed to be University
Bhubaneswar, India
6.1 Code Optimization
• Code optimization in compiler design refers to the process of modifying a program to improve its
efficiency and performance without changing its output or behavior.
• The goal is to produce code that runs faster, consumes less memory, or meets specific criteria
important for the application or hardware it runs on.

 Goals of Code Optimization

• Reduce Execution Time: Making the program run faster by reducing the number of instructions
or optimizing the execution path.
• Minimize Memory Usage: Reducing the size of the code and the amount of runtime memory
required.
• Energy Efficiency: In battery-powered devices, optimizing for lower energy consumption can be
crucial.
• Improve Parallelism: Taking advantage of multi-core processors to execute code in parallel,
thereby reducing overall execution time.

Prabhu Prasad Dev CD / Module-VI 2

6.2 Machine Independent vs Dependent Optimization
Optimization Type Machine-Independent Machine-Dependent
Optimizations that are tailored to the
Optimizations that do not rely on the hardware
Definition specific features of the target machine's
characteristics of the target machine.
hardware.
To improve code efficiency and performance in a To leverage specific hardware features for
Goal
general manner. maximum performance and efficiency.
- Loop unrolling - Common subexpression
- Instruction scheduling - Register allocation
Examples elimination - Dead code elimination - Loop
- Pipeline optimization - Cache optimization
invariant code motion
Specific to a particular hardware
Can be applied across different hardware
Scope architecture; may need adjustments for
platforms without modification.
different platforms.
Extracts the maximum possible
Improves code portability and maintains
Benefits performance from the hardware, exploiting
performance improvements across platforms.
specific architectural advantages.
May not fully exploit hardware-specific Less portable; optimizations for one
Limitations optimizations leading to less than optimal architecture may not be relevant or could
performance on some architectures. even degrade performance on another.

Prabhu Prasad Dev CD / Module-VI 3

6.3 Peephole Optimization
 It is a simple and effective optimization technique for locally improving target code.
 This technique is applied to improve the performance of the target program by
examining the short sequence of target instructions and replacing these instructions
by shorter or faster sequence.
 A peephole is a small window which is moved over the target code and
transformations can be made and hence is the name.
 The peephole optimization can be applied on the target code using following
characteristic:
1. Redundant load and store instruction elimination
2. Eliminating Unreachable Code
3. Flow-of-control optimizations
4. Simplify Algebraic Expressions
5. Strength Reduction
6. Use of Machine Idioms

Prabhu Prasad Dev CD / Module-VI 4

6.3.1 Redundant load and store Elimination

Example:

If we see the instruction sequence

LD R0, a

ST a, R0

in a target program, we can delete the store instruction because whenever it is executed,

the first instruction will ensure that the value of a has already been loaded into register R0.

Note that if the store instruction had a label, we could not be sure that the first instruction is
always executed before the second, so we could not remove the store instruction

Prabhu Prasad Dev CD / Module-VI 5

6.3.2 Elimination of Unreachable Code

 We can eliminate unreachable instructions. In the following code the if statement will never get executed and
hence can be eliminated.

𝑠𝑢𝑚 = 0
𝑖𝑓 𝑠𝑢𝑚
𝑝𝑟𝑖𝑛𝑡𝑓 %d, 𝑠𝑢𝑚 ;

 In the following code, Line 5 is unreachable and hence can be eliminated.

1. 𝑖𝑛𝑡 𝑓𝑢𝑛 𝑖𝑛𝑡 𝑎, 𝑖𝑛𝑡 𝑏

2. {
3. 𝑐 = 𝑎 + 𝑏;
4. 𝑟𝑒𝑡𝑢𝑟𝑛 𝑐;
5. 𝑝𝑟𝑖𝑛𝑡𝑓 %d, 𝑐 ;
6. }

Prabhu Prasad Dev CD / Module-VI 6

6.3.3 Flow of Control Optimization

 Using peephole optimization unnecessary jumps on jumps can be eliminated.

Example 2
Example 1
Finally, suppose there is only one jump to L1 and L1 is
preceded by an unconditional goto. Then the sequence

If there are now no jumps to L1, then it may be While the number of instructions in the two sequences is
possible to eliminate the statement L1: goto L2 the same, we sometimes skip the unconditional jump in
provided it is preceded by an unconditional jump the second sequence, but never in the first. Thus, the
second sequence is superior to the first in execution time.

Prabhu Prasad Dev CD / Module-VI 7

 6.3.4 Simplify Algebraic Expressions
 Peephole optimization is an effective technique for algebraic simplification.
 The following statements can be eliminated by peephole optimizations.
𝑥 = 𝑥 + 0 or 𝑥 = 𝑥 ∗ 1
 We can eliminate them by using mathematical identities.
 Some of these identities are given below:
𝑥+0=0+𝑥 =𝑥
𝑥×1=1×𝑥 =𝑥
𝑥−0=𝑥
𝑥 Τ1 = 𝑥

Prabhu Prasad Dev CD / Module-VI 8

6.3.5 Strength Reduction
 Certain machine instructions are cheaper than the other.
 In order to improve the performance of the intermediate code we can replace
these instructions by equivalent cheaper instructions.

EXPENSIVE CHEAPER
𝑥2 = 𝑥×𝑥

2×𝑥 = 𝑥+𝑥
𝑥 Τ2 = 𝑥 × 0.5

Prabhu Prasad Dev CD / Module-VI 9

6.3.6 Use of Machine Idioms
 Use of Machine Idioms refers to the use of hardware instructions that are designed to carry out certain
operations more efficiently than their high-level language counterparts.
 Efficiency through Hardware Instructions: Machines often have hardware-level instructions to perform
common tasks more efficiently than could be done in software using general instructions.
 Optimization in Loops:
• In loop counters or iterating over data structures, these idioms can be used to write more optimized
loops. For example, for (x = 0; x < limit; x++) uses the auto-increment idiom to increase the loop counter.
 Improving Code Quality:
• Using these hardware features can make code more concise and readable, especially for operations like
pushing or popping elements from a stack, or for simple operations like incrementing a value.
• Example: Instead of writing x = x + 1, you could use x++, which utilizes the auto-increment feature of the
hardware if available.
 Auto-increment and Auto-decrement Addressing Modes:
• Some machines support addressing modes that automatically increase or decrease the value of a
register before or after it is used for an operation.
• Example: In assembly language, an instruction like LOAD (X)+ might load the value at address X into a
register and then increment the value of X. This is useful when working with arrays or stacks.
Prabhu Prasad Dev CD / Module-VI 10
6.4 Types of Machine-Independent Optimizations

 Local Optimization
 Global Optimization

Prabhu Prasad Dev CD / Module-VI 11

Local vs Global Optimization
Aspect Local Optimization Global Optimization
Limited to a basic block (a straight-line code
Across multiple basic blocks within a
Scope sequence with no branches in except to the
function or entire program.
entry and no branches out except at the exit).
Considers all variables across the function
Only optimizes considering the local
Variables or program, including interactions between
variables within the basic block.
them.
Does not consider control flow; assumes Analyzes and modifies control flow across
Control Flow
sequential execution. the program to improve efficiency.
Includes loop optimizations (like loop
Includes simplification of expressions,
unrolling, loop fusion), inlining
Functionality elimination of local common
functions, and interprocedural
subexpressions, and constant folding.
optimizations.
Global optimizations often depend on
Local optimizations are generally
Dependency information from multiple blocks and may
independent of other blocks.
require data flow analysis.
These optimizations are applied more Applied less frequently due to higher
Frequency of Use frequently since they are simpler and less complexity and cost in terms of compilation
costly to perform. time.
Prabhu Prasad Dev CD / Module-VI 12
Examples of Local Optimization

 Local Common sub-expression elimination

 Copy propagation
 Dead Code Elimination
 Constant propagation and constant folding

Prabhu Prasad Dev CD / Module-VI 13

Examples of Global Optimization

 Global Common sub-expression elimination

 Copy propagation
 Dead Code Elimination
 Constant propagation and constant folding
 Loop Optimization
• Loop invariant code motion
• Induction variable elimination and strength reduction
• Loop unrolling

Prabhu Prasad Dev CD / Module-VI 14

6.4.1 Common Subexpressions Elimination
 The common sub expression is an expression
appearing repeatedly in the program which is Example
computed previously.
 If the operands of a sub expression do not get changed
at all then result of such sub expression is used instead
of recomputing it each time.
 Types of Subexpressions Elimination:
• Local Common Sub-expression elimination
 It is used within a single basic block.
 A basic block is a simple code sequence that
has no branches.
• Global Common Sub-expression elimination (to be
Local Common Sub-expression elimination
discussed later)
 It is used for an entire procedure of common
sub-expression elimination.

Prabhu Prasad Dev CD / Module-VI 15

6.4.2 Copy Propagation / Variable Propagation
 Copy propagation means use of one variable instead of another
 Example:

𝑥 = 𝑝𝑖;
... 𝑎𝑟𝑒𝑎 = 𝑝𝑖 ∗ 𝑟 ∗ 𝑟;
𝑎𝑟𝑒𝑎 = 𝑥 ∗ 𝑟 ∗ 𝑟;
• Here the variable 𝑥 is eliminated.
• The necessary condition is that a
variable must be assigned to
another variable or some constant.

Prabhu Prasad Dev CD / Module-VI 16

6.4.3 Dead Code Elimination
 A variable is said to be live in a program if the value contained into it is used subsequently.
 A variable is said to be dead at a point in a program if the value contained into it is never been used. The
code containing such a variable is known as dead code.
 A programmer is unlikely to introduce any dead code intentionally, it may appear as the result of previous
transformations.
 Example:
Consider the following code:
𝑖𝑛𝑡 𝑎 = 10, 𝑏 = 20;
𝑖𝑓 𝑎%2 == 0
𝑝𝑟𝑖𝑛𝑡𝑓("Even");
𝑒𝑙𝑠𝑒
𝑝𝑟𝑖𝑛𝑡𝑓("Odd");
The code 𝑏 = 20; can be considered as dead code and can be eliminated from the program to optimize
the code.

Prabhu Prasad Dev CD / Module-VI 17

6.4.4 Strength Reduction
 The strength of certain operators is higher than others.
 For example strength of ∗ operator is higher than + operator.
 In strength reduction technique, the higher strength operators can be replace by lower strength
operators.
 Example:

 The induction variable is integer scalar identifier used in the form of 𝑣 = 𝑣 ± 𝑐𝑜𝑛𝑠𝑡𝑎𝑛𝑡 where 𝑣 is a
induction variable.
 In the modified code 𝑡𝑒𝑚𝑝 is the induction variable.

Prabhu Prasad Dev CD / Module-VI 18

6.4.5 Constant Folding
 It refers to the evaluation of expression at compilation time whose operands are known to be
constants.
 Example:
• If we have an expression say 10 ∗ 2 + 4 is expanded then the compiler can calculate the result
(24) in this case) during compilation time and modify the code as if it contains the resultant
(24) rather than the original expression 10 ∗ 2 + 4 − 𝑏.

𝐿1: 𝑇1 = 10 ∗ 2 𝐿1: 𝑇1 = 24
𝐿2: 𝑇2 = 𝑇1 + 4 𝐿2: 𝑇2 = 𝑇2 − 𝑏
𝐿3: 𝑇3 = 𝑇2 − 𝑏 𝐿4: 𝑎 = 𝑇2
𝐿4: 𝑎 = 𝑇3

3AC before Constant Folding 3AC after Constant Folding

Prabhu Prasad Dev CD / Module-VI 19

6.5 Prerequisites of Loop Optimization: Basic Blocks

 A basic block B is a sequence of consecutive instructions such that:

1. Flow of Control enters B only at its beginning
2. Flow of Control leaves B at its end (under normal execution)
3. Flow of Control cannot halt or branch out of B except at its end.

Prabhu Prasad Dev CD / Module-VI 20

6.5.1 Algorithm for Partitioning Code into Basic Blocks
1. Determine the set of leaders, i.e., the first instruction of each basic block:
a) The first statement is a leader.
b) Any instruction that is the target of a branch is a leader.
c) Any instruction following a (conditional or unconditional) branch is a leader.
2. For each leader, its basic block consists of:
a) The leader itself
b) All subsequent instructions up to, but not including, the next leader.

Prabhu Prasad Dev CD / Module-VI 21

6.5.2 Control Flow Graphs
 A flow graph is a directed graph in which the flow control information is added to
the basic blocks.
• The nodes to the flow graph are represented by basic blocks
• The block whose leader is the first statement is called initial block.
• There is a directed edge from block 𝐵1 to block 𝐵2 if 𝐵2 immediately follows 𝐵1
in the given sequence.

Prabhu Prasad Dev CD / Module-VI 22

6.5.3 Construction of Control Flow Graph
1. Identify the basic blocks.
2. There is an edge from block 𝑎 to block 𝑏 if:
a) There is a (conditional or unconditional) branch from the last instruction of block 𝑎
to the first instruction of block 𝑏 or
b) Block 𝑏 immediately follows block 𝑎 in the original order of three-address
instructions, and block 𝑎 does not end in an unconditional branch.

Often we add two nodes, called the ENTRY and EXIT, that do not correspond to
executable intermediate instructions.
• There is an edge from the ENTRY to the first executable node of the flow graph, that
is, to the basic block that comes from the first instruction of the intermediate code.
• There is an edge to the EXIT from any basic block that contains an instruction that
could be the last executed instruction of the program

Prabhu Prasad Dev CD / Module-VI 23

6.5.4 Loops
Many code transformations depend upon the “identification of loops" in a flow graph.
We say that a set of nodes L in a flow graph is a loop if L contains a node e called the loop entry,
such that:
1. e is not ENTRY, the entry of the entire flow graph.
2. No node in L besides e has a predecessor outside L. That is, every path from ENTRY to any
node in L goes through e.
3. Every node in L has a nonempty path, completely within L to e.

Prabhu Prasad Dev CD / Module-VI 24

6.5.4 Loops Example

This flow graph has three loops:

1. B3 by itself.
2. B6 by itself.
3. {B2, B3, B4}.

The first two are single nodes with an edge to the node itself.
For instance, B3 forms a loop with B3 as its entry. Note that the
last requirement for a loop is that there be a nonempty path
from B3 to itself. Thus, a single node like B2, which does not
have an edge B2 → B2, is not a loop, since there is no
nonempty path from B2 to itself within {B2}.

The third loop, L = {B2, B3, B4}, has B2 as its loop entry. Note
that among these three nodes, only B2 has a predecessor, B1,
that is not in L. Further, each of the three nodes has a
nonempty path to B2 staying within L. For instance, B2 has the
path B2 → B3 → B4 → B2.

Prabhu Prasad Dev CD / Module-VI 25

6.5.5 Construction of Basic Blocks: Example
Question: Consider the following code for computing dot product of two vectors 𝑎
and 𝑏 of length 10 and partition it into basic blocks. The machine uses 4 bytes per
word.
1. 𝒑𝒓𝒐𝒅 = 𝟎;
𝒑𝒓𝒐𝒅 = 𝟎
2. 𝒊 = 𝟏;
𝒊=𝟏 3. 𝒕𝟏 = 𝟒 ∗ 𝒊;
𝒅𝒐 4. 𝒕𝟐 = 𝒂𝒅𝒅𝒓(𝑨) − 𝟒;
{ 5. 𝒕𝟑 = 𝒕𝟐 𝒕𝟏 ;
𝒑𝒓𝒐𝒅 = 𝒑𝒓𝒐𝒅 + 𝒂 𝒊 ∗ 𝒃 𝒊 ; 6. 𝒕𝟒 = 𝟒 ∗ 𝒊;
𝒊 = 𝒊 + 𝟏; 7. 𝒕𝟓 = 𝒂𝒅𝒅𝒓(𝑩) − 𝟒;
}𝒘𝒉𝒊𝒍𝒆 𝒊 ≤ 𝟏𝟎 ; 8. 𝒕𝟔 = 𝒕𝟓 𝒕𝟒 ;
9. 𝒕𝟕 = 𝒕𝟑 ∗ 𝒕𝟔;
10. 𝒕𝟖 = 𝒑𝒓𝒐𝒅 + 𝒕𝟕;
11. 𝒑𝒓𝒐𝒅 = 𝒕𝟖
12. 𝒕𝟗 = 𝒊 + 𝟏
13. 𝒊 = 𝒕𝟗
14. 𝒊𝒇 𝒊 ≤ 𝟏𝟎 𝒈𝒐𝒕𝒐 (𝟑)
Source Code 3 Address Code
Prabhu Prasad Dev CD / Module-VI 26
Example Contd..
Applying some intra code optimization and peep hole optimization techniques we
get the following code:
1. 𝒑𝒓𝒐𝒅 = 𝟎; 1. 𝒑𝒓𝒐𝒅 = 𝟎;
2. 𝒊 = 𝟏; 2. 𝒊 = 𝟏;
3. 𝒕𝟏 = 𝟒 ∗ 𝒊; 3. 𝒕𝟏 = 𝟒 ∗ 𝒊;
4. 𝒕𝟐 = 𝒂𝒅𝒅𝒓(𝑨) − 𝟒; 4. 𝒕𝟐 = 𝒂𝒅𝒅𝒓(𝑨) − 𝟒;
5. 𝒕𝟑 = 𝒕𝟐 𝒕𝟏 ; 5. 𝒕𝟑 = 𝒕𝟐 𝒕𝟏 ;
6. 𝒕𝟒 = 𝟒 ∗ 𝒊; 6. 𝒕𝟒 = 𝒂𝒅𝒅𝒓(𝑩) − 𝟒;
7. 𝒕𝟓 = 𝒂𝒅𝒅𝒓(𝑩 ) − 𝟒; 7. 𝒕𝟓 = 𝒕𝟒 𝒕𝟏 ;
8. 𝒕𝟔 = 𝒕𝟓 𝒕𝟒 ; 8. 𝒕𝟔 = 𝒕𝟑 ∗ 𝒕𝟓;
9. 𝒕𝟕 = 𝒕𝟑 ∗ 𝒕𝟔; 9. 𝒑𝒓𝒐𝒅 = 𝒑𝒓𝒐𝒅 + 𝒕𝟔;
10. 𝒕𝟖 = 𝒑𝒓𝒐𝒅 + 𝒕𝟕; 10. 𝒊=𝒊+𝟏
11. 𝒑𝒓𝒐𝒅 = 𝒕𝟖 11. 𝒊𝒇 𝒊 ≤ 𝟏𝟎 𝒈𝒐𝒕𝒐 (𝟑)
12. 𝒕𝟗 = 𝒊 + 𝟏
13. 𝒊 = 𝒕𝟗
14. 𝒊𝒇 𝒊 ≤ 𝟏𝟎 𝒈𝒐𝒕𝒐 (𝟑)

3 Address Code Optimized 3 Address Code

Prabhu Prasad Dev CD / Module-VI 27
Example Contd..(Finding Leader)
Finding out leaders: According to the algorithm for construction of Flow graph:
Leader 1 Leader 2 • Statement 1 is a leader by rule 1(a)
• Statement 3 is also leader by rule 1(b)

1. 𝒑𝒓𝒐𝒅 = 𝟎; Algorithm:
2. 𝒊 = 𝟏; 1. Determine the set of leaders, i.e., the first instruction of
3. 𝒕𝟏 = 𝟒 ∗ 𝒊; each basic block:
4. 𝒕𝟐 = 𝒂𝒅𝒅𝒓𝑨 − 𝟒;
5. 𝒕𝟑 = 𝒕𝟐 𝒕𝟏 ; a) The first statement is a leader.
6. 𝒕𝟒 = 𝒂𝒅𝒅𝒓𝑩 − 𝟒; b) Any instruction that is the target of a branch is a leader.
7. 𝒕𝟓 = 𝒕𝟒 𝒕𝟏 ; c) Any instruction following a (conditional or unconditional)
8. 𝒕𝟔 = 𝒕𝟑 ∗ 𝒕𝟓; branch is a leader.
9. 𝒑𝒓𝒐𝒅 = 𝒑𝒓𝒐𝒅 + 𝒕𝟔;
10. 𝒊=𝒊+𝟏 2. For each leader, its basic block consists of:
11. 𝒊𝒇 𝒊 ≤ 𝟏𝟎 𝒈𝒐𝒕𝒐 (𝟑) a) The leader itself
b) All subsequent instructions up to, but not including, the
3 Address Code next leader.

Prabhu Prasad Dev CD / Module-VI 28

Example Contd…
Basic Blocks: According to the algorithm for construction of Flow graph:
1. 𝒑𝒓𝒐𝒅 = 𝟎; • Statement 1 is a leader by rule 1(a)
2. 𝒊 = 𝟏; B1 • Statement 3 is also leader by rule 1(b)
3. 𝒕𝟏 = 𝟒 ∗ 𝒊; • Hence, statement 1 and 2 form the basic block.
4. 𝒕𝟐 = 𝒂𝒅𝒅𝒓𝑨 − 𝟒; • Similarly, statement 3 to 11 form another basic block.
5. 𝒕𝟑 = 𝒕𝟐 𝒕𝟏 ;
6. 𝒕𝟒 = 𝒂𝒅𝒅𝒓𝑨 − 𝟒; Algorithm:
7. 𝒕𝟓 = 𝒕𝟒 𝒕𝟏 ; 1. Determine the set of leaders, i.e., the first instruction of each basic block:
8. 𝒕𝟔 = 𝒕𝟑 ∗ 𝒕𝟓;
B2
a) The first statement is a leader.
9. 𝒑𝒓𝒐𝒅 = 𝒑𝒓𝒐𝒅 + 𝒕𝟔;
b) Any instruction that is the target of a branch is a leader.
10. 𝒊=𝒊+𝟏
11. 𝒊𝒇 𝒊 ≤ 𝟏𝟎 𝒈𝒐𝒕𝒐 (𝟑) c) Any instruction following a (conditional or unconditional) branch is a
leader.
2. For each leader, its basic block consists of:
a) The leader itself
b) All subsequent instructions up to, but not including, the next leader.

Prabhu Prasad Dev CD / Module-VI 29

Example of Control Flow Graph – contd…

Basic Blocks Control Flow Graph

1. 𝒑𝒓𝒐𝒅 = 𝟎;
2. 𝒊 = 𝟏; B1
3. 𝒕𝟏 = 𝟒 ∗ 𝒊;
4. 𝒕𝟐 = 𝒂𝒅𝒅𝒓𝑨 − 𝟒;
5. 𝒕𝟑 = 𝒕𝟐 𝒕𝟏 ;
6. 𝒕𝟒 = 𝒂𝒅𝒅𝒓𝑨 − 𝟒;
7. 𝒕𝟓 = 𝒕𝟒 𝒕𝟏 ;
8. 𝒕𝟔 = 𝒕𝟑 ∗ 𝒕𝟓;
9. 𝒑𝒓𝒐𝒅 = 𝒑𝒓𝒐𝒅 + 𝒕𝟔;
10. 𝒊=𝒊+𝟏
11. 𝒊𝒇 𝒊 ≤ 𝟏𝟎 𝒈𝒐𝒕𝒐 (𝟑)
B2

Prabhu Prasad Dev CD / Module-VI 30

6.6 The Principal Sources of Optimization
 A compiler optimization must preserve the semantics of the original program.
 Except in very special circumstances, once a programmer chooses and
implements a particular algorithm, the compiler cannot understand enough about
the program to replace it with a substantially different and more efficient
algorithm.
 A compiler knows only how to apply relatively low-level semantic transformations,
using general facts such as algebraic identities like 𝑖 + 0 = 𝑖 or program
semantics such as the fact that performing the same operation on the same
values yields the same result.

Prabhu Prasad Dev CD / Module-VI 31

6.6.1 Causes of Redundancy
 There are many redundant operations in a program.
 More often, the redundancy is a side effect of having written the program in a
high-level language.
• Beside the languages like C or C++, where pointer arithmetic is allowed,
programmers have no choice but to refer to elements of an array or fields in a
structure through accesses like 𝐴[𝑖][𝑗] or 𝑋 → 𝑓.
 During compilation, the high-level data-structure accesses expands into a
number of low-level arithmetic operations.
• Computation of the location of the (i, j)th element of a matrix A.
 Accesses to the same data structure often share many common low-level
operations about which the programmers are not aware of and cannot eliminate
the redundancies themselves.

Prabhu Prasad Dev CD / Module-VI 32

6.6.2 A Running Example: Quicksort
 Consider the following fragment of a sorting program called quicksort for the illustration
of several important code-improving transformations.

Prabhu Prasad Dev CD / Module-VI 33

6.6.2 Intermediate code of Quicksort
Assumption: Integers occupy four bytes of memory space Loop 3

Loop 1
Loop 3
Loop 1
Loop 2 Loop 2

C code for quicksort Three-address Code

Prabhu Prasad Dev CD / Module-VI 34

Intermediate code of Quicksort
Assumption: Integers occupy four bytes of memory space Leader 1 Leader 6

Leader 2

Leader 3

Three-address Code Leader 4 Leader 5 Three-address Code

Prabhu Prasad Dev CD / Module-VI 35

Basic Blocks
Block B3
Leader 1 Leader 6
Block B1 Block B2

Leader 2

Leader 3

Leader 4 Leader 5 Block B4 Block B5 Block B6

Prabhu Prasad Dev CD / Module-VI 36

Flow Graph
Block B3

Block B1 Block B2

Block B4 Flow Graph

Block B5 Block B6

Prabhu Prasad Dev CD / Module-VI 37

6.6.3 Local common-subexpression elimination
 Frequently, a program includes
several calculations of the same
value, such as an offset in an array.
 Some of these duplicate calculations
cannot be avoided by the programmer
because they lie below the level of
detail accessible within the source
language.
 Example, block 𝐵5 shown in Fig. (a)
recalculates 4 ∗ 𝑖 and 4 ∗ 𝑗, although
none of these calculations were
requested explicitly by the
programmer.

Prabhu Prasad Dev CD / Module-VI 38

6.6.4 Global Common Subexpressions
 An occurrence of an expression 𝐸 is called a common subexpression if 𝐸 was
previously computed and the values of the variables in 𝐸 have not changed since
the previous computation.
 We avoid re-computing 𝐸 if we can use its previously computed value; that is, the
variable 𝑥 to which the previous computation of 𝐸 was assigned has not changed
in the interim.
• If 𝑥 has been changed, it may still be possible to reuse the computation of 𝐸 if
we assign its value to a new variable 𝑦, as well as to 𝑥, and use the value of 𝑦
in place of a re-computation of 𝐸.

Prabhu Prasad Dev CD / Module-VI 39

Global common-subexpression elimination: Example

𝑹𝒆𝒑𝒍𝒂𝒄𝒆𝒎𝒆𝒏𝒕
𝑡6 → 𝑡2
𝑡8 → 𝑡4
a[𝑡4]→ 𝑡5
a[𝑡2]→ 𝑡3
𝐱 = 𝐭𝟑 𝐱 = 𝐭𝟑 𝑡11 → 𝑡2
a[t2]= 𝐭𝟓 𝐭𝟏𝟒 = a[t1] 𝑡12 → 𝑡2
𝑡13 → 𝑡1
a[t2]= 𝐭𝟏𝟒 𝑡15 → 𝑡1
a[t4]= 𝐱
a[t1]= 𝐱

Prabhu Prasad Dev CD / Module-VI 40

6.6.5 Copy Propagation Example
 The idea behind
copy-propagation
transformation is to
use 𝒗 for 𝒖
wherever possible
after the copy
statement 𝒖 = 𝒗.

Prabhu Prasad Dev CD / Module-VI 41

Advantages of using Copy Propagation
 Copy propagation reduces the required computation time by eliminating the
redundant and unnecessary variable assignments in the expressions.
 Copy propagation ensures memory optimization.
 Only the required memory assignments and variables require memory, irrelevant
memory expressions are being eliminated.
 Copy propagation simplifies the available code by eliminating the expressions
that are not required making code easily understandable.

Prabhu Prasad Dev CD / Module-VI 42

6.6.6 Dead code elimination
 One advantage of copy propagation is that it often turns the copy statement into
dead code.
 For example, copy propagation followed by dead-code elimination removes the
assignment to x and transforms the code shown in Fig. (a) into Fig. (b)

(b)
(a)

(a) (b)

Prabhu Prasad Dev CD / Module-VI 43

6.6.7 Code Movement
 There are two basic goals of code movement:
1. To reduce the size of the code to obtain space complexity
2. To reduce the frequency of execution of code to obtain the time complexity.
 Example:

Prabhu Prasad Dev CD / Module-VI 44

6.7 Loop Optimization
 The code optimization can be significantly done in loops of the program.
 Loops are a very important place for optimizations, especially the inner loops where programs tend to spend
the bulk of their time.
 The running time of a program may be improved if we decrease the number of instructions in an inner loop,
even if we increase the amount of code outside that loop.
 Loop optimization is a technique in which code optimization is performed on inner loops.
 The loop optimization is carried out by the following methods:
1. Loop invariant Code Motion method
2. Induction Variable and strength reduction
3. Loop unrolling

Prabhu Prasad Dev CD / Module-VI 45

6.7.1 Loop invariant Code Motion
 Code motion is a technique which moves the code outside the loop. Hence is the name.
 If there lies some expression in the loop whose result remains unchanged even after
executing the loop for several times, then such an expression should be placed just
before the loop (i.e. outside the loop). Here before the loop means at the entry of the
loop.
 Example:

Prabhu Prasad Dev CD / Module-VI 46

6.7.2 Induction variables and strength reduction
 A variable 𝑥 is said to be an “induction variable” if there is a
positive or negative constant 𝑐 such that each time 𝑥 is
assigned, its value either increases or decreases by 𝑐.
 For instance, 𝑖 and 𝑡2 are induction variables in the loop
containing 𝐵2. Similarly, 𝑗 and 𝑡4 are induction variables in
the loop containing 𝐵3.
 Induction variables can be computed with a single
increment (addition or subtraction) per loop iteration. induction variables

 The transformation of replacing an expensive operation,

such as multiplication, by a cheaper one, such as addition,
is known as strength reduction.
 But induction variables not only allow us sometimes to
perform a strength reduction; often it is possible to eliminate
all but one of a group of induction variables whose values
remain in lock step as we go around the loop.

Prabhu Prasad Dev CD / Module-VI 47

How to process induction variables
 When processing loops, it is useful to work "inside-out";
that is, we should start with the inner loops and proceed
to progressively larger, surrounding loops.
 Here, we will see how this optimization applies to our
quicksort example by beginning with one of the innermost
loops: 𝐵3 by itself.
 Note that the values of 𝑗 and 𝑡4 remain in lock step i.e.
every time the value of 𝑗 decreases by 1, the value of t4
decreases by 4, because 4 * j is assigned to t4. These
variables, 𝑗 and 𝑡4 , are forming a pair of induction
variables.
 When there are two or more induction variables in a loop,
it may be possible to get rid of all but one.

Prabhu Prasad Dev CD / Module-VI 48

Contd…
 In the block 𝐵3 , the relationship 𝑡4 = 4 ∗ 𝑗 surely holds after
assignment to 𝑡4 and 𝑡4 is not changed elsewhere in the inner loop
(block 𝐵3).
 This follows that the value 𝑡4 is decremented by 4 in each execution
of the loop (block 𝐵3).
 We may therefore replace the assignment 𝑡4 = 4 ∗ 𝑗 by
𝒕𝟒 = 𝒕𝟒 − 𝟒.
 The only problem is that 𝑡4 does not have a value when we enter
block 𝐵3 for the first time.
 Since we must maintain the relationship 𝑡4 = 4 ∗ 𝑗 on entry to the
block B3, we place an initialization of 𝑡4 at the end of the block
where 𝑗 is initialized,
 Although we have added one more instruction, which is executed
once in block B1, the replacement of a multiplication by a subtraction
will speed up the object code if multiplication takes more time than
addition or subtraction, as is the case on many machines.

Prabhu Prasad Dev CD / Module-VI 49

Contd…

Prabhu Prasad Dev CD / Module-VI 50

Contd…

 After reduction in strength is applied to the inner loops

around 𝐵2 and 𝐵3, the only use of 𝑖 and 𝑗 is to determine the
outcome of the test in block 𝐵4.
 We know that the values of 𝑖 and 𝑡2 satisfy the relationship
𝑡2 = 4 ∗ 𝑖, while those of 𝑗 and 𝑡4 satisfy the relationship
𝑡4 = 4 ∗ 𝑗.
 Thus, the test 𝑡2 ≥ 𝑡4 can be substituted for i ≥ j.
 Once i ≥ j is replaced by 𝑡2 ≥ 𝑡4, 𝑖 in block 𝐵2 and 𝑗 in block
𝐵3 become dead variables, and the assignments to them in
these blocks become dead code that can be eliminated.
 The resulting flow graph is shown in the next slide.

Prabhu Prasad Dev CD / Module-VI 51

Contd…

Prabhu Prasad Dev CD / Module-VI 52

6.7.3 Loop Unrolling

 Loop Unrolling is a loop transformation

technique that helps to optimize the
execution time of a program.
 We basically remove or reduce iterations.
Loop unrolling increases the program’s
speed by eliminating loop control instruction
and loop test instructions.

Prabhu Prasad Dev CD / Module-VI 53

Practice Questions

 Aho Ullman Book:

• Exercises for Section 8.4
• Exercises for Section 8.5
• Exercises for Section 9.1

Prabhu Prasad Dev CD / Module-VI 54