Code Optimization and

Code Generation
Unit-5
 Contents
• Criteria for code improving transformations
• An Organization for an Optimizing Compiler
• Peephole optimization
 Code Optimization Introduction
Optimization is the process of transforming a piece of code to make more
efficient (either in terms of time or space) without changing its output or
side-effects. The only difference visible to the code’s user should be that it runs
faster and/or consumes less memory.
 Criteria for code improving transformations
The transformations provided by an optimizing compiler should have several properties.
[Link] transformation must preserve the meaning of programs. That is, the optimization must
not change the output produced by a program for a given input.
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.
[Link] programmer is always responsible in finding the best possible data structures and
algorithms for solving a problem.
 Conti...
Types of Code Optimization: The optimization process can be broadly
classified into two types :

Machine Independent • This code optimization phase attempts to improve

the intermediate code to get a better target code as the output.
Optimization The part of the intermediate code which is transformed here
does not involve any CPU registers or absolute memory locations.

• Machine-dependent optimization is done after the target

code has been generated and when the code is transformed
Machine Dependent according to the target machine architecture. It involves CPU
Optimization registers and may have absolute memory references rather than
relative references. Machine-dependent optimizers put efforts to
take maximum advantage of the memory hierarchy.
Hierarchy of Code Optimization Techniques

Code
Optimization

Machine Machine
Independent Dependent

Principle Sources Loop Peephole

of Optimization Optimization Optimization
Techniques Techniques Techniques
 Peephole Optimization
Peephole optimization is an local optimization technique works on a small window of
compiler-generated instructions; the small set is known as the peephole optimization in
compiler design or window.
In compiler design, local optimization means applying optimizations within a small region
of code, usually restricted to a basic block.
• A local optimization is an optimization technique that improves code inside a basic block
only.
• Basic block = a straight-line sequence of instructions with no jumps or branches (except
into the first and out of the last).
• Optimizations are applied only within that block, not across multiple blocks.
Conti....
Where It Appears?
After Code Generation, because it works directly on machine code or assembly code.
It is a machine-dependent optimization (since it deals with target instructions).
1. It is applied to the source code after it has been converted to the target code.
2. Peephole optimization comes under machine-dependent optimization. Machine-dependent
optimization occurs after the target code has been generated and transformed to fit the target
machine architecture. It makes use of CPU registers and may make use of absolute memory
references rather than relative memory references.
3. It is applied to a small piece of code, repeatedly.
Conti....
Benefits of Local Optimization

❖ Faster execution – Eliminates unnecessary instructions.

❖ Smaller code size – Redundant instructions removed.

❖ Foundation for global optimizations – Simplifies basic blocks, making further optimizations
easier.
•.
 Peephole Optimization Techniques
1) Redundant LOAD and STORE

2) Strength Reduction

3) Simple Algebraic Expressions

4) Replace Slower Instructions With Faster

5) Dead code Elimination

 Peephole Optimization Techniques

[Link] LOAD and STORE

LOAD: Transfers data from memory into a CPU register.
Example:
LOAD R1, 5000 → Take the contents of memory location 5000 and put it in register R1.
Use: Needed before doing operations (since the CPU works only with data in registers)
STORE:Transfers data from a CPU register into memory.
Example:
STORE R1, 6000 → Take the contents of register R1 and put it into memory location 6000.

Use: Needed to save results back to memory after computation.

Conti...
In this optimization, the redundant operations are removed. For
example, loading and storing values on registers can be optimized.
For example,
a= b+c
d= a+e
• It is implemented on the register(R0) as
 Conti...
It is implemented on the register(R0) as
MOV b, R0; instruction to copy b to the register
ADD c, R0; instruction to Add c to the register, the register is now b+c
MOV R0, a; instruction to Copy the register(b+c) to a
MOV a, R0; instruction to Copy a to the register
ADD e, R0 ;instruction to Add e to the register, the register is now a(b+c)+e
MOV R0, d; instruction to Copy the register to d

This can be optimized by removing load and store operation, like in third instruction value in register R0 is
copied to a, and it again loaded to R0 in the next step for further operation. The optimized implementation
will be:
Conti....
MOV b, R0; instruction to Copy b to the register
ADD c, R0; instruction to Add c to the register, which is now b+c (a)
MOV R0, a; instruction to Copy the register to a
ADD e, R0; instruction to Add e to the register, which is now b+c+e
[(a)+e]
MOV R0, d; instruction to Copy the register to d
Conti....
Benefit of eliminating redundant LOADs:

• Saves memory access time (memory operations are slower than

register operations).

• Reduces CPU cycles by avoiding unnecessary fetches.

• Lowers bus traffic (less interaction with memory hierarchy).

• Improves overall execution speed.

Conti....
[Link] Reduction
Strength reduction is a compiler optimization technique where an expensive
operation (like multiplication, division, or exponentiation) is replaced with a
computationally cheaper operation (like addition, subtraction, or bit-shifting),
without changing the program’s meaning.
Conti....
Multiplication → Exponentiation → Division → Multiplication by Power
Addition Multiplication Multiplication/Shift of 2 → Shift

for (i = 0; i < n; i++) { y = x^2; // expensive y = x / 2; // division is Multiplication by Power

a = 5 * i; // expensive expensive of 2 → Shift
(multiplication inside
loop)
}
Strength reduced to: Strength reduced to: Strength reduced to: Strength reduced to:

t = 0; y = x * x; // cheaper y = x >> 1; // bit-shift (if x y = x << 3; // faster

for (i = 0; i < n; i++) { is integer)
a = t;
t = t + 5; // cheaper
(addition instead of
multiplication)
}
Conti....
Benefits of Strength Reduction:
❖ Reduces execution time.

❖ Optimizes loops (especially useful in loop optimization).

❖ Saves CPU cycles, improving overall performance.

Conti....
[Link] Algebraic Expressions :-The compiler applies basic algebraic rules (like
removing unnecessary operations or replacing them with cheaper ones).
The algebraic expressions that are useless or written inefficiently are transformed.

Eliminating Neutral Operations

a=a+0
a=a*1
Benefit: Removes useless operations → fewer instructions, faster execution.
Removing Redundant Calculations
a=a/1
a=a-0
Benefit: Direct result without wasting CPU cycles.
Conti...
4. Replace Slower Instructions With Faster
Slower instructions can be replaced with faster ones, and registers play an
important role. For example, a register supporting unit increment operation will
perform better than adding one to the register. The same can be done with many
other operations, like multiplication.

Add #1
SUB #1
//The above instruction can be replaced with
// INC R
// DEC R
//If the register supports increment and decrement
b

Conti...
[Link] code Elimination
The dead code can be eliminated to improve the system's performance;
resources will be free and less memory will be needed.
int dead(void)
{
int a=1;
int b=5;
int c=a+b;
If(c<4)
{
int k=1;
k=k*2;
k=k+1;
}
 Basic Blocks And Flow Graphs

Basic Blocks:
A basic block is a sequence of consecutive instructions or statements in a program that has exactly
one entry point (the first instruction of the block) and one exit point (the last instruction of the
block), with no branches or jumps in between. Execution within a basic block always proceeds
sequentially from start to end without interruption.
Flow graphs, or control flow graphs (CFG):
These are directed graphs that represent the flow of control between basic blocks. Each node in
the graph corresponds to a basic block, and directed edges indicate possible control transfers
from one block to another. Flow graphs illustrate how the program execution moves between
basic blocks, capturing branching and looping structures.
Conti...
The characteristics of basic blocks are-

• They do not contain any kind of jump statements in them.

• There is no possibility of branching or getting halt in the middle.

• All the statements execute in the same order they appear.

• They do not lose the flow control of the program.

Main()
{
Int x=4,y=3,z;
Print(x);
Print(y);
Leader
Print(z);
If(z>5)
{
}
Else
{
}
Conti....
101: if (x>y) goto 103
If(x>y) 102: goto 107
A=a[10]+x;
103: t1=4*i
Else
104:t2=a[t1]
A=a[10]-x;
105:t3=a[t1]+x
106: goto 110
107:t4=4*i
108:t5=a[t4]
109: t6=t5-x;
110
Example
Three Address Code for
the expression a = b + c + d is-
Partitioning Intermediate Code Into Basic
Blocks-
Any given code can be partitioned into basic blocks using the following
rules-
Rule-01: Determining Leaders-
• Following statements of the code are called as Leaders–
• First statement of the code.
• Statement that is a target of the conditional or unconditional goto
statement.
• Statement that appears immediately after a goto statement.
Conti....
Rule-02: Determining Basic Blocks-
• All the statements that follow the leader (including the leader) till the
next leader appears form one basic block.
• The first statement of the code is called as the first leader.
• The block containing the first leader is called as Initial block.
Algorithm of Basic Block in Compiler
Design
1. First, find the set of leaders from intermediate code, the first
statements of basic blocks. The following are the steps for finding
leaders:
1. The first instruction of the three-address code is a leader.
2. Instructions that are the target of conditional/unconditional goto
are leaders.
3. Instructions that immediately follow any
conditional/unconditional goto/jump statements are leaders.
2. For each leader found, its basic block contains itself and all
instructions up to the next leader.
Conti....
1) prod := 0
(2) i := 1
(3) t1 := 4* i
(4) t2 := a[t1] /*compute a[i] */
(5) t3 := 4* i
(6) t4 := b[t3] /*compute b[i] */
(7) t5 := t2*t4
(8) t6 := prod+t5
(9) prod := t6
(10) t7 := i+1
(11) i := t7
(12) if i<=20 goto (3)
 )

Conti...
The three-address code for the above source program is given as :
1) prod := 0
(2) i := 1
(3) t1 := 4* i
(4) t2 := a[t1] /*compute a[i] */
(5) t3 := 4* i
(6) t4 := b[t3] /*compute b[i] */
(7) t5 := t2*t4
(8) t6 := prod+t5
(9) prod := t6
(10) t7 := i+1
(11) i := t7
(12) if i<=20 goto (3)
Basic block 1: Statement (1) to (2)
Basic block 2: Statement (3) to (12)
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. It has a distinguished initial node.

E.g.: Flow graph for the vector dot product is given as follows:
Conti...
▪ B1 is the initial node. B2 immediately
follows B1, so there is an edge from B1 to
B2. The target of jump from last statement of
B1 is the first statement B2, so there is an
edge from B1 (last statement) to B2 (first
statement).
▪ B1 is the predecessor of B2, and B2 is a
successor of B1.
 NEXT-USE INFORMATION

If the name in a register is no longer needed, then we remove the name

from the register and the register can be used to store some other names.
Input: Basic block B of three-address statements
Output: At each statement i: x= y op z, we attach to i the liveliness and
next-uses o
f x, y and z.
Method: We start at the last statement of B and scan backwards.
Conti...
1. Attach to statement i the information currently found in the symbol table
regarding the next-use and liveliness of x, y and z.
2. In the symbol table, set x to “not live” and “no next use”.
3. In th symbol table , set y and z to “live” and next uses of y and z to i.

Symbol Table
Name Liveliness Next-Use
x not live no next use
y live i
z live i
Conti...
If a statement or name in a
statement is used in another a=i+j
b=k+1
statement, then the statement
of that name is said to be next-used,
and in between, the statement or
name should redefined. This a1=a+2
b1=b+2
information can be called as

• next-use information. Here the names a, b in B1 are used in the

statements a1, b1 in B2. Now we will define the next use information.
Conti...
• If the name is used by another statement then the name is said to be live. If it is
not used by any other statement then the name is not live or dead.

• We can say I is live in B2 but not in B3.

The variables a, b in Be are live in B3,
because these are used in a1, b1.
 Principal sources of code 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.
Function-Preserving Transformations can be performed at both the local and
global levels. Local transformations are usually performed first.

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
Conti...

The other transformations come up primarily when global

optimizations are performed. Frequently, a program will include several
calculations of the offset in an array.
Some of the duplicate calculations cannot be avoided by the
programmer because they lie below the level of detail accessible within
the source language.
Conti...
[Link] Sub Expression 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.
Avoid recomputing the expression if we can use the previously computed value.
Example

Example Optimized Code

t1: = 4*i t1: = 4*i
t2: = a [t1] t2: = a [t1]
t3: = 4*j t3: = 4*j
t4: = 4*i t5: = n
t5: = n t6: = b [t1] +t5
t6: = b [t4] +t5

The common sub expression t4: =4*i is eliminated as its computation is already in t1 and the value of i is not
been changed from definition to use.
Contd....
[Link] 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 x.
Example:-
x=Pi;
A=x*r*r;
The optimization using copy propagation can be done as follows: A=Pi*r*r;
Here the variable x is eliminated
Conti..
3. 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. While the programmer is unlikely to introduce any dead code intentionally, it may appear as
the result of previous transformations.

Example:
i=0;
if(i= =1)
{
a=b+5;
}
Here, ‘if’ statement is dead code because this condition will never get satisfied.
Conti...
[Link] folding:
Deducing at compile time that the value of an expression is a constant and using the constant
instead is known as constant folding. One advantage of copy propagation is that it often turns the
copy statement into dead code.
For example,
a=3.14157/2 can be replaced by
a=1.570 there by eliminating a division operation.
An Organization for an Optimizing Compiler
Conti.....
Flow analysis is a fundamental prerequisite for many important types of
code improvement. Generally, control flow analysis precedes data flow
analysis. Control flow analysis (CFA) represents flow of control usually in
form of graphs, CFA constructs such as control flow graph, Call graph. Data
flow analysis (DFA) is the process of asserting and collecting information
prior to program execution about the possible modification, preservation,
and use of certain entities (such as values or attributes of variables) in a
computer program.
 Issues in the design of code generator

CODE GENERATION
The final phase in compiler model is the code generator. It takes as input an
intermediate representation of the source program and produces as output an
equivalent target program. The code generation techniques presented below can
be used whether or not an optimizing phase occurs before code generation.
Conti...
ISSUES IN THE DESIGN OF A CODE GENERATOR
The following issues arise during the code generation phase:
1. Input to code generator
2. Target program
3. Memory management
4. Instruction selection
5. Register allocation
6. Evaluation order
 Simple Code Generator
The simple code generator algorithm generates target code for a sequence of
three-address statements. The code generator algorithm works by considering individually
all the basic blocks. It uses the next-use information to decide on whether to keep the
computation in the register or move it to a variable so that the register could be reused.
It uses new function getreg() to assign registers to variables. The algorithm for code
generation initially checks if operands to three-address code are available in registers.
After computing the results of two operations, the results are kept in registers till the result
is required by another computation or register is kept up to a procedure call or end of block
to avoid errors.
Conti....
Register and Address Descriptors:

❖ A register descriptor is used to keep track of what is currently in each

registers. The register descriptors show that initially all the registers
are empty.

❖ An address descriptor stores the location where the current value of

the name can be found at run time.
Conti....
For example, consider the following instruction:
a := b+c
The following sequence would be followed by the code generator algorithm:
❖ The algorithm initially checks if ‘b’ and ‘c’ are in registers Ri, Rj. If available then the
instruction ADD Ri, Rj is generated and this costs 1 and the result is stored in Rj
❖ If ‘b’ alone is in register and ‘c’ is not in the register, then the instruction ADD c, Ri is
generated to a cost of 2
❖ MOV a, Rj is issued to move the computation to ‘a’.
Conti....
The issues that need to be resolved are how to get the registers. If the registers are
free then there is no issue. If the registers are all occupied, we must free an existing
register. Will the instruction generator go for memory-based instructions or will
necessarily have to go for a register-based instruction only is to be considered.

With these issues in consideration, the simple code generator algorithm uses two data
structures to resolve.
Conti.... The Code Generation Algorithm
Algorithm SimpleCodeGenerator( )
Input : Sequence of 3-address statements from a basic block.
Output: Assembly language code
Conti....
The issues that need to be resolved are how to get the registers. If the registers are free then
there is no issue. If the registers are all occupied, we must free an existing register. Will the
instruction generator go for memory-based instructions or will necessarily have to go for a
register-based instruction only is to be considered.
Conti....
For each statement x := y op z
[Link] location L = getreg(y, z) to store the result of y op z
[Link] y Ï L then generate
MOV y’,L
where y’ denotes one of the locations where the value of y is available choose register if
possible
3. Generate
OP z’,L
where z’ is one of the locations of z;
Update register/address descriptor of x to include L
4. If y and/or z has no next use and is stored in register, update register descriptors to
remove y and/or z
Conti....
❖ The first step in the algorithm is to invoke the getreg() function to get a register to store the result of the
computation.
❖ The second step is to find the location of the first operand on the LHS. If it is in a register which is found by querying
the address descriptor, then the same register is issued.
❖ The next step is issuing a MOV command to transfer the variable’s value into the register. If the variable is already in
a register, then this instruction could be eliminated.
❖ The third instruction is to operate on that register using the other operand and at this point the value of the LHS
variable of the input instruction is in the register. So, the address descriptor and register descriptors are updated
accordingly.
❖ The fourth step is to find out whether the current variable has a next-use immediately. Depending on the next-use
the register content is copied to the variable and the descriptors are updated so that the register could be used for
some other instructions.
Conti....
Algorithm for getreg ( )
Input: Request for a register
Output: A register or the memory location
1. If y is stored in a register R and R only holds the value y, and y has no next use, then
return R; Update address descriptor: value y no longer in R
2. Else, return a new empty register if available
3. Else, find an occupied register R; Store contents (register spill) by generating
MOV R,M for every M in address descriptor of y; Return register R
[Link] Return a memory location
Conti....
The getreg() function, returns a register if a free register is available. If the value of the
variable for which we are trying to issue a MOV instruction is already in a register then the
same register is used. If there are no free registers, then an occupied register is identified,
it is freed by moving its contents to variable and then is issued. If no such free register
could be identified, then the instruction operates on memory location.
References
• [Link]
• [Link]
• [Link]
• [Link]
• [Link]
• [Link]
• [Link]
• [Link]
• [Link]
egister-allocation/