1. Criteria must follow for optimization
1.1. The meaning of the source program must preserved
1.2. The algorithm should not be modified
1.3. Must Improve Time, Space Consumption
2. Optimization Technique
2.1. Compile Time Evaluation
2.1.1. Constant Folding
2.1.1.1. Small Computation must done at compile time
2.1.1.2. Evaluation of an expression whose operands are known to be constant
2.1.1.2.1. EX: a = 5+2*3 the above expression must compute at compile time
2.1.2. Constant Propagation
2.1.2.1. if a variable is assigned a constant value, then Replace all the constant expressions with their constant literals
2.1.2.1.1. Ex: Before optimization: temp = 5; prop = temp; After optimization prop = 5;
2.2. Operator Strength Reduction
2.2.1. Replacing the high strength operator by the low strength.
2.2.2. Ex: A^2 can be replace by A*A
2.3. Copy Propagation
2.3.1. Similar to constant propagation, but generalized to non-constant values.
2.3.1.1. Before Optimization t2 = t1; t3 = t2*t1; t4 = t3; t5 = t3*t2; c = t5+t4; After optimization t3 = t1*t1; t5 = t3*1; c = t5+t3;
2.3.2. Helps in register allocation
2.3.3. Can be done both localy (basic block level) or globaly (whole procedure).
2.4. Dead Code Elimination
2.4.1. If an instruction's result is never used, the instruction is considered "dead" and can be removed
2.4.1.1. Ex: Consider t1=t2+t3; and if t1 is never used again then we can eliminate
2.5. Algebraic Smiplification and re-association
2.6. Common Sub-expression Elimination
2.6.1. Identify common sub-expression present in different expression, compute once, and use the result in all the places.
2.6.1.1. Example: Before a := b * c … … x := b * c + 5 After temp := b * c ... x := temp + 5
2.7. Loop Optimization
2.7.1. Loop Transformation
2.7.1.1. Loop Interchange/Permutation
2.7.1.1.1. Exchange inner loops with outer loops
2.7.1.1.2. Before for (k = 0; k < 100; k = k+1) for (j = 0; j < 100; j = j+1) for (i = 0; i < 5000; i = i+1) x[i][j] = 2 * x[i][j]; After for (k = 0; k < 100; k = k+1) for (i = 0; i < 5000; i = i+1) for (j = 0; j < 100; j = j+1) x[i][j] = 2 * x[i][j];
2.7.1.2. Loop splitting
2.7.1.2.1. Attempts to simplify a loop or eliminate dependencies by breaking it into multiple loops which have the same bodies but iterate over different contiguous portions of the index range.
2.7.1.3. Loop fusion/Combining
2.7.1.3.1. Two adjacent loops would iterate the same number of times, their bodies can be combined as long as they make no reference to each other's data
2.7.1.3.2. Example Before int i, a[100], b[100]; for (i = 0; i < 100; i++) { a[i] = 1; } for (i = 0; i < 100; i++) { b[i] = 2; } After int i, a[100], b[100]; for (i = 0; i < 100; i++) { a[i] = 1; b[i] = 2; }
2.7.1.4. Loop fission/Distribution
2.7.1.4.1. Example : Before int i, a[100], b[100]; for (i = 0; i < 100; i++) { a[i] = 1; b[i] = 2; } After int i, a[100], b[100]; for (i = 0; i < 100; i++) { a[i] = 1; } for (i = 0; i < 100; i++) { b[i] = 2; }
2.7.1.4.2. Break down a large loop body into smaller ones to achieve better utilization of locality of reference.
2.7.1.5. Loop unrolling
2.7.1.5.1. Duplicates the body of the loop multiple times
2.7.1.5.2. Example int main(void) { printf("Hello\n"); printf("Hello\n"); printf("Hello\n"); printf("Hello\n"); printf("Hello\n"); return 0; }
2.7.2. Loop Invariant Code Removal
2.7.2.1. Example Before for(i=1;i<=10;i++){ a = b*5; x = a+b+i;} After a = b*5; for(i=1;i<=10;i++){ x = a+b+i;}
2.7.2.2. One that computes the same value every time a loop is executed
2.7.3. Induction Variable Removal
2.7.3.1. Example: Before int a[SIZE]; int b[SIZE]; void f (void) { int i1, i2, i3; for (i1 = 0, i2 = 0, i3 = 0; i1 < SIZE; i1++) a[i2++] = b[i3++]; return; } After int a[SIZE]; int b[SIZE]; void f (void) { int i1; for (i1 = 0; i1 < SIZE; i1++) a[i1] = b[i1]; return; }
2.7.3.2. Some loops contain two or more induction variables that can be combined into one induction variable.
2.7.3.3. Induction variables are variables such that every time they change value, they are incremented or decremented.
2.7.4. Strength Reduction
3. Classification
3.1. Local Optimization
3.1.1. Performed within basic block
3.1.2. The simplest form of Optimization
3.1.3. No need to analyze the whole procedure body
3.2. Global Optimization
3.2.1. Optimization across the basic block
3.2.2. Data-flow analysis is done to perform optimization across basic block
3.2.3. Each basic block is a node in the flow graph of the program
3.2.4. These optimization can be extended to an entire control-flow graph
3.3. Peephole Optimization
3.3.1. A local optimization technique.
3.3.2. Simplistic in nature, but effective in practise.
3.3.3. Do mahine dependent improvement
3.3.4. Characteristics
3.3.4.1. Redundant-Instruction elimination
3.3.4.2. Flow-of-control Optimization
3.3.4.3. Use of machine idioms
3.3.5. Can be applied directly on Assembly Language
4. Types of Optimization
4.1. Machine Depenedent
4.1.1. Requires knowledge of the target machine
4.1.2. Take maximum advantage of memory hierarchy.
4.1.3. Replace sequence of instructions with more powerful one
4.2. Machine Independent
4.2.1. performed indepedently of the target machine
4.2.1.1. Improve the intermediate code to get a better target code as the output.
4.2.2. Remove redundant (unreachable, useless) code
5. Factors Influencing Optimization
5.1. The Target Machine
5.1.1. Machine dependent factors can be parameterized to compiler for fine tuning
5.2. Architecture of Target CPU
5.2.1. Number of CPU registers
5.2.2. RISC vs CISC
5.2.3. Pipeline Architecture
5.2.4. Number of functional units
5.3. Machine Architecture
5.3.1. Cache Size and type
5.3.2. Cache/Memory transfer rate