Lecture Notes: Code Optimization
1. Introduction to Code Optimization
Code optimization is the process of improving the intermediate or target code so that it runs faster,
takes less space, or both, without changing the program’s output.
It is one of the most important phases of compilation, aiming for efficient and high-performance
object code.
2. Principal Sources of Optimization
Optimization can come from different sources in a program. According to Ullman, the major sources
are:
1. **Common subexpressions** – Avoid recomputing expressions.
2. **Dead code** – Remove code that does not affect the program result.
3. **Loop optimizations** – Improve performance of loops which often dominate execution time.
4. **Copy propagation** – Replace variables that only copy other variables.
5. **Constant folding and propagation** – Evaluate constant expressions at compile time.
6. **Strength reduction** – Replace costly operations (e.g., multiplication) with cheaper ones (e.g.,
addition).
3. Loop Optimization
Loops are the most time-consuming parts of a program, so optimizing them gives significant
performance gains.
**Common loop optimizations include:**
• **Loop-Invariant Code Motion** – Move calculations that do not change within the loop to outside
the loop.
• **Strength Reduction** – Replace expensive operations inside loops with simpler ones.
• **Induction Variable Elimination** – Replace index variables with simpler arithmetic.
• **Loop Unrolling** – Execute multiple iterations in one loop pass to reduce overhead.
**Example:**
Before Optimization:
for (i = 0; i < n; i++)
x = a * b;
After Optimization:
t = a * b;
for (i = 0; i < n; i++)
x = t;
4. Copy Propagation
Copy propagation replaces uses of variables that are copies of others with the original variable.
**Example:**
a = b;
c = a + 1;
→ c = b + 1;
Benefits:
• Simplifies code.
• Exposes further optimization opportunities like dead code elimination.
5. Dead Code Elimination
Dead code is code that never affects the program’s observable output.
This can happen when:
• The computed value is never used.
• The code is unreachable.
**Example:**
x = 10;
x = 20; // The first assignment is dead
After elimination:
x = 20;
Benefits:
• Reduces code size.
• Improves execution speed.
6. Redundant Subexpression Elimination (CSE)
If an expression has already been computed and its operands have not changed, we can reuse the
previously computed value instead of recomputing it.
**Example:**
a = b + c;
d = b + c + e;
After optimization:
t = b + c;
a = t;
d = t + e;
Benefits:
• Avoids redundant computation.
• Reduces execution time.
7. Summary
• Code optimization improves performance and reduces program size.
• Main techniques: Loop optimization, copy propagation, dead code elimination, redundant
subexpression elimination.
• Loop optimization is the most impactful since loops run many times.
• Optimizations should maintain the semantics of the original program.
8. Conceptual Questions
1. What are the principal sources of optimization?
2. Explain different types of loop optimizations.
3. What is copy propagation? Give an example.
4. Define dead code elimination with an example.
5. Explain redundant subexpression elimination and its benefits.
