Mumbai University > Computer Engineering > Sem6 > System Programming and Compiler Construction

Marks: 5M

Year: May 2015

Optimization

• Optimization 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.
• A code optimizing process must follow the three rules given below:

1. The output code must not, in any way, change the meaning of the program.
2. Optimization should increase the speed of the program and if possible, the program should demand less number of resources.
3. Optimization should itself be fast and should not delay the overall compiling process.

• Efforts for an optimized code can be made at various levels of compiling the process.

1. At the beginning, users can change/rearrange the code or use better algorithms to write the code.
2. After generating intermediate code, the compiler can modify the intermediate code by address calculations and improving loops.
3. While producing the target machine code, the compiler can make use of memory hierarchy and CPU registers.

• Optimization can be categorized broadly into two types:

  Machine Independent and Machine Dependent.

Function Preserving $\hspace{2.5 cm}$ Loop Optimization

• Common subexpression Elimination $\hspace{.5 cm}$ 1. Code motion

• Constant Folding $\hspace{3.5 cm}$ 2. Strength Reduction

• Copy Propagation $\hspace{3.5 cm}$ 3. Frequency Reduction

• Dead code Elimination $\hspace{2.5 cm}$ 4. Loop distribution

Loop Optimization

We are going to perform optimization on loops.

• Code Motion

  It specifies on a condition if we perform some operations to be carried out and then compare for a condition.

  Instead of that perform the calculation outside the loop and assign a value in the calculation.

• Code motion (also called code hoisting) unifies sequences of code common to one or more basic blocks to reduce code size and potentially avoid expensive re-evaluation.
• The most common form of code motion is loop-invariant code motion that moves statements that evaluate to the same value every iteration of the loop to somewhere outside the loop.

• What statements inside the following TAC code can be moved outside the loop body?

                      L0:
                      tmp1 = tmp2 + tmp3;
                      tmp4 = tmp4 + 1 ;
                      PushPram tmp4 ;
                      LCall _PrintInt ; 
                      PopParams 4;
                      tmp6 = 10 ; 
                      tmp5 = tmp4 == tmp6 ;
                      IfZ tmp5 Goto L0 ;
  

We have an intuition of what makes a loop in a flow graph, but here is a more formal definition. A loop is a set of basic blocks which satisfies two conditions:

1. All are strongly connected, i.e. there is a path between any two blocks.
2. The set has a unique entry point, i.e. every path from outside the loop that reaches any block inside the loop enters through a single node. A block n dominates m if all paths from the starting block to m must travel through n. Every block dominates itself.

For loop L, moving invariant statement s in block B which defines variable v outside the loop is a safe optimization if:

1. B dominates all exits from L
2. No other statement assigns a value to v
3. All uses of v inside L are from the definition in s.

Loop invariant code can be moved to just above the entry point to the loop.