Code Optimization

Compiler Design • Code optimization is a technique which tries to improve the code by eliminating
unnecessary code lines and arrange the statement such in a sequence speed up the
program execution without wasting the resources.

Chapter 6: Code Optimization and Code Generation

Advantage:
• faster execution speed
• utilizes the memory efficiently
• gives better performance
27-Jun-22 Fikru Tafesse(MSc. in Computer Science) 1 2

Cont'd ...
Code Optimization Techniques 1. Compile Time Evaluation
• Two techniques that falls under compile time evaluation are:
• Important code optimization techniques are:
i. Constant Folding
• it involves folding of the constants.
• The expressions that contain the operands having constant values at compile time are evaluated.
• Those expressions are then replaced with their respective results.
Example : Circumference of Circle = (22/7) x Diameter
• Here,

• This technique evaluates the expression 22/7 at compile time.

• The expression is then replaced with its result 3.14.
• This saves the time at run time.

3 4
 Cont'd ... Cont'd ...
2. Common Sub-Expression Elimination
ii. Constant Propagation
• The expression that has been already computed before and appears again in the code for computation is
• If some variable has been assigned some constant value, then it replaces that variable
called as Common Sub-Expression.
with its constant value in the further program during compilation. • In this technique,
• The condition is that the value of variable must not get alter in between. • As the name suggests, it involves eliminating the common sub expressions.

Example : pi = 3.14 • The redundant expressions are eliminated to avoid their re-computation.
• The already computed result is used in the further program when required.
radius = 10
Example : Code Before Optimization Code After Optimization
Area of circle = pi x radius x radius
S1 = 4*i S1 = 4*i
• Here, S2 = a[S1] S2 = a[S1]

• This technique substitutes the value of variables ‘pi’ and ‘radius’ at compile time. S3 = 4*j S3 = 4*j
S4 = 4*i // Redundant Expression S5 = n
• It then evaluates the expression 3.14 x 10 x 10.
S5 = n S6 = b[S44] + S5
• The expression is then replaced with its result 314. S6 = b[S44] + S5

• This saves the time at run time. 5 6

Cont'd ... Cont'd ...

3. Code Movement 4. Dead Code Elimination
• it involves movement of the code. • As the name suggests, it involves eliminating the dead code.
• The code present inside the loop is moved out if it does not matter whether it is present inside or outside. • The statements of the code which either never executes or are unreachable or their output is never used
• Such a code unnecessarily gets execute again and again with each iteration of the loop. are eliminated
• This leads to the wastage of time at run time.
Code Before Optimization Code After Optimization
Example : Code Before Optimization Code After Optimization Example :
i = 0;
for (int j=0; j<n; j++) { x = y + z;
if(i==1) {
x = y + z; for (int j=0; j<n; j++) {
a = x + 5; i = 0;
a[j] = 6*j; a[j] = 6*j;
}
} }

7 8
5. Strength Reduction
Cont'd ... Code Generation
• Strength reduction is used to replace the expensive operation by the cheaper once on the • Code generation can be considered as the final phase of compilation.
target machine. • The code generated by the compiler is an object code of some lower-level
• Addition of a constant is cheaper than a multiplication. programming language, for example, assembly language.
• So, we can replace multiplication with an addition within the loop. • We have seen that the source code written in a higher-level language is transformed
• Multiplication is cheaper than exponentiation. into a lower-level language that results in a lower-level object code, which should have
• So, we can replace exponentiation with multiplication within the loop. the following minimum properties:
Example :
Code Before Optimization Code After Optimization  It should carry the exact meaning of the source code.
 It should be efficient in terms of CPU usage and memory management.
B=A*2 B=A+A • Code generator is used to produce the target code for three-address statements.
i= j3 i = j *j * j
• It uses registers to store the operands of the three-address statement.

9 10

Cont'd ...
• Example: Consider the three-address statement x: = y + z. Issues in the design of a Code Generator
• It can have the following sequence of codes:
• The following issues arise during the code generation phase:
MOV z, R0
• Input to the code generator
ADD y, R0
• Target program
• Code generator converts the intermediate representation of source code into a form that
• Memory management
can be readily executed by the machine.
• Instruction selection
• A code generator is expected to generate the correct code.
• Register allocation
• Evaluation order

Fig. Position of Code Generator 11 12

 Cont'd ...
Basic Block and Flow Graphs Basic Block Construction Algorithm:
1. Basic block • Algorithm: Partition into basic blocks
• Basic block is a set of statements that always executes in a sequence one • Input: A sequence of three address code statements

after the other. • Output: List of basic blocks with each three-address statement in exactly one block
• Method: First identify the leader in the code.
• The characteristics of basic blocks are:
• Rule-01: Determining Leaders:
o They do not contain any kind of jump statements in them.
1. The first instruction in three address code statement is a leader.
o There is no possibility of branching or getting halt in the middle.
2. Any instructions that is the target of conditional or unconditional jump is
o All the statements execute in the same order they appear. a leader
o They do not lose the flow control of the program. 3. Any instruction that immediately follows a conditional or unconditional
jump is a leader.
13 14

Cont'd ... Cont'd ...

• Rule-02: Determining Basic Blocks: • Example: Flow graph for the vector dot product is given as follows:

1. All the statements that follow the leader (including the leader) till the next leader
appears form one basic block. • Block B1 is the initial node.
• Block B2 immediately follows B1, so from
2. The first statement of the code is called as the first leader.
B2 to B1 there is an edge.
3. The block containing the first leader is called as Initial block.
• The target of jump from last statement of
2. Flow Graphs: is a directed graph with flow control information added to the basic blocks. B1 is the first statement B2.
1. The nodes of the flow graph are basic blocks. • So, from B1 to B2 there is an edge.

• It has a distinguished initial node. • B2 is a successor of B1 and B1 is the

predecessor of B2.
2. The basic blocks serve as nodes of the flow graph.
3. There is a directed edge from block B1 to block B2 if B2 appears immediately after B1
in the code.

15 16
 Cont'd ... • Example 3: Consider the following source code: Cont'd ...
• Example 2: Consider the following source code

17 18 End