Code Optimization

1
Code Optimization
 Code optimization is a technique which tries to improve the code by
elimination unnecessary code lines and arranging the statements in such a
sequence that speed up the program execution without wasting resources.

 Code Optimization is an approach to enhance the performance of the code.

 It is a program transformation technique, which tries to improve the code by

making it consume less resources (i.e. CPU, Memory) and deliver high speed.

 In optimization, high-level general programming constructs are replaced by

very efficient low-level programming codes.

2
Code Optimization
 A code optimizing process must follow the three rules
 The output code must not, in any way, change the meaning
of the program.
 Optimization should increase the speed of the program and
the program should demand less number of resources.
 Optimization should itself be fast and should not delay the
overall compiling process.

3
Code Optimization
 Optimization can be made at various levels of compiling the
process.
 At the beginning, users can change/rearrange the code or use
better algorithms to write the code.
 After generating intermediate code, the compiler can
modify the intermediate code by address calculations and
improving loops.
 While producing the target machine code, the compiler
can make use of memory hierarchy and CPU registers.

4
Code Optimization

 The process of code optimization involves

 Eliminating the unwanted code lines
 Rearranging the statements of the code

 The optimized code advantages

 Optimized code has faster execution speed.
 Optimized code utilizes the memory efficiently.
 Optimized code gives better performance.
5
Types of Code Optimization
 Main Types of Code Optimization are -
 High-level optimizations
 Intermediate level optimizations
 Low-level optimizations .

 High-level optimization is a language dependent type of optimization

that operates at a level of the source code. include alignment of arrays,
padding, layout, and elimination of tail recursion.

 Most of the code optimizations performed fall under intermediate code

optimization which is language independent.
6
Common Sub-Expression Elimination

 The expression that has been already computed before

and appears again in the code for computation is
called as Common Sub-Expression.
 It involves eliminating the common sub expressions.
 The redundant expressions are eliminated to avoid their
re-computation.
 The already computed result is used in the further
program when required.
7
 Common Sub-Expression Elimination
Code Before Optimization Code After Optimization

S1 = 4 x i
S1 = 4 x i
S2 = a[S1]
S2 = a[S1]
S3 = 4 x j
S3 = 4 x j
S4 = 4 x i // Redundant Expression
S5 = n
S5 = n
S6 = b[S1] + S5
S6 = b[S4] + S5

8
 Constant Propagations
 If some variable has been assigned some constant value, then it replaces that
variable with its constant value in the further program during compilation.

 The condition is that the value of variable must not get alter in between.
pi = 3.14
radius = 10
Area of circle = pi x radius x radius

 Here,
 This technique substitutes the value of variables ‘pi’ and ‘radius’ at compile
time.
 It then evaluates the expression 3.14 x 10 x 10.
 The expression is then replaced with its result 3.14.
 This saves the time at run time.

9
Jump Threading
➢ Major goal is to reduce the number of dynamically
executed jumps on different paths.

if (a > 5) if (a > 5)
goto j; goto somewhere;
stuff (); stuff ();
stuff (); stuff ();
j: j:
goto somewhere; goto somewhere;

10
Dead Code Elimination
➢ It involves eliminating the dead code.

➢ The statements of the code which either never executes or

are unreachable or their output is never used are eliminated.

Code Before Optimization Code After Optimization

i=0;
if (i == 1)
{ i=0;
a=x+5;
}

11
Strength Reduction
➢ It involves reducing the strength of expressions.

➢ This technique replaces the expensive and costly operators

with the simple and cheaper ones.

Code Before Optimization Code After Optimization

B=Ax2 B=A+A
➢ This is because the cost of multiplication operator is higher
than that of addition operator.

12
Low-level Optimization
 It is highly specific to the type of architecture. This
includes the following:

 Register allocation: Here, a big number of target

program variables are assigned to a small number of
CPU registers. This can happen over a local register
allocation or a global register allocation or an inter-
procedural register allocation.

13
Low-level Optimization
 Instruction Scheduling – This is used to improve an instruction level
parallelism that in turn improves the performance of machines with
instruction pipelines. It will not change the meaning of the code but
rearranges the order of instructions to avoid pipeline stalls. Semantically
ambiguous operations are also avoided.

 Floating-point units utilization – Floating point units are designed

specifically to carry out operations of floating point numbers like addition,
subtraction, etc. The features of these units are utilized in low-level
optimizations which are highly specific to the type of architecture.

14
Low-level Optimization
 Branch prediction – Branch prediction techniques help to
guess in which way a branch functions even though it is
not known definitively which will be of great help for the
betterment of results.

 Peephole– Peephole optimization technique is carried out

over small code sections at a time to transform them by
replacing with shorter or faster sets of instructions. This set
is called as a peephole.
15
 Low-level Optimization
 Peephole– Redundant load elimination is a common
peephole optimization.
 Before: After
MOVQ R8, x MOVQ R8, x
MOVQ x, R8
Before: After:
MOVQ R8, x MOVQ R8, x
MOVQ x, R9 MOVQ R8, R9

16
Machine Independent and Machine
dependent
 Optimization can broadly be categorized into two- Machine
Independent and Machine dependent.

 Machine-independent optimization phase tries to improve the

intermediate code to obtain a better output. The optimized intermediate
code does not involve any absolute memory locations or CPU
registers.

 Machine-dependent optimization is done after generation of the

target code which is transformed according to target machine
architecture. This involves CPU registers and may have absolute
memory references.

17
Machine Independent Optimization
 The compiler takes in the intermediate code and
transforms a part of the code that does not involve any
CPU registers and/or absolute memory locations.

do Item = 10;
{ do
item = 10; {
value = value + item; value = value + item;
} }
while(value<100); while(value<100);

18
Machine Independent Optimization
 Machine independence includes two types
 Function Preserving
 Loop optimization

Function preserving
Common Sub Expression Elimination
BO AO
T1 = 4+i T1 = 4+i
T2 = T2 +T1 T2 = T2 +T1
T3 = 4 + i T4 = T2 + T1
T4 = T2 + T3

19
Machine Independent Optimization
 Constant folding:- just like constant propagation
 Constant folding is the technique of converting an expression
(or part of an expression) by combining multiple
constants into a single constant.
BO AO
T1 = 5/2 T1 = 2.5

 Copy Propagation
BO AO
T1 = X T2 = T3 + T2
T2 = T3 + T2 T3 = T1
20
Machine Independent Optimization
 Loop Optimization
 Code Motion

BO AO
While(i < = limit-2) t1 = limit – 2
{ While (i< =t1)
….. {
…… …..
… ……
} ...
}

21
Machine Independent Optimization

 Strength Reduction
 The multiplication operator can be easily replaced by left
shift operator a<<1 Division can be replaced by a a>>1
operator.

BO AO
T1 = a * 2 a<<1
T1 = a / 2 a >> 1

22
Machine Independent Optimization

 Frequency Reduction
 In this case if a expression inside a loop is not dynamically
affected by a loop we calculate it outside the loop and use
the value inside the loop.

23