Chapter-Eight
Code Optimization
Basic Topics to be covered
What is code optimization?
Why optimization is needed ???
When to Optimize?
Code Optimization rule
The principal Sources of Optimization
What is Code Optimization ?
Code 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.
Code Optimization is used to improve the intermediate code by making it consume fewer
resources (i.e. CPU, Memory) so that faster-running machine code will result.
In optimization, high-level general programming constructs are replaced by very efficient
low-level programming codes.
The code optimization in the synthesis phase is a program transformation technique
It aids in reducing the storage space and increases compilation speed.
Why Code Optimization ?
Because of the Problem with Intermediate Code
ICG process introduces many inefficiencies
Extra copies of variable
Using variable instead of constants
Repeated evaluation of expression
Code optimization removes such inefficiencies
Why optimization is needed ?
Since our code optimization reduces code readability, it is often
conducted at the end of development.
Optimization can help:
To improve intermediate code
Better target code, Executes Faster, Shorter code, Less power
Efficient memory usage,
Better performance.
Complexity : Time, Space & Cost
Increase complilation speed and Reduce space consumed
Promote re-usability
When to Optimize?
Optimization of the code is often performed at the end of the development stage
since it reduces readability and adds code that is used to increase the performance.
Efforts for an optimized code 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.
Code Optimization rule
Compiler optimizing process should meet the following rules given below:
– The optimization must be correct, it must not, in any way, change the meaning of
the program.
– (i.e. It is expected that the un-optimized and optimized variants give the same
output for all inputs.)
– Optimization should increase the speed and performance of the program.
– The compilation time must be kept reasonable.
– The optimization process should not delay the overall compiling process.
Code Optimization: Example
Types of Code Optimization:
• The optimization process can be broadly classified into two types :
i. Machine Independent Optimization:
– This code optimization phase attempts to improve the intermediate code to get a better target
code as the output.
– The part of the intermediate code which is transformed here does not involve any CPU
registers or absolute memory locations.
ii. Machine Dependent Optimization:
– Machine-dependent optimization is done after the target code has been generated and when
the code is transformed according to the target machine architecture.
– It involves CPU registers and may have absolute memory references rather than relative
references.
– Machine-dependent optimizers put efforts to take maximum advantage of the memory
hierarchy.
Peephole Optimization
• One way we can begin to optimize our code is by using peephole technique.
• This is the idea of performing optimizations on small parts of the code, replacing sections
with shorter and faster code whilst still keeping the inputs consistent.
• This is a machine dependant optimization.
• Implement of peephole optimization, they are as follows:
– Redundant load/store elimination
– Common Sub-expression Elimination
– Constant folding
– Constant Propagation
– Strength reduction
– Null sequences
– Combining operators
Redundant load /store elimination
• Eliminating redundancy in code
– Input code:
x = y+5
i=x
k=i
j = k*3
– Optimized code:
x = y+5
i=x
j = x*3
Copy Propagation
Common Sub-expression Elimination
Constant Folding
Simplification of constants
Input code:
Evaluate constant expressions at compile time.
x = 3*3
Only possible when side-effect freeness guaranteed.
Optimized code:
x=9
Constant Propagation
Variables that have constant value, e.g. c := 3
• Later uses of c can be replaced by the constant
• If no change of c between!
Null sequences
• Unnecessary operators are removed
• Input code:
i = 13+2
k = i+10
– Optimized code:
k = 25
Combining operators
Multiple operations can be combined to a shorter equivilant expression
Input code:
i = j*(10+3)
Optimized code:
i = j*13
