Global optimization techniques in Compiler Design - Full Explanation

Introduction

When a program runs, it often repeats tasks or calculations that could be done once and reused. Global optimization techniques help the compiler find these opportunities across the entire program to make it run faster and use less memory.

Explanation

Constant Propagation

This technique finds values in the program that never change and replaces variables with those constant values everywhere. By doing this, the compiler can simplify expressions and sometimes remove code that no longer affects the program.

Replacing variables with constant values helps simplify and speed up the program.

Common Subexpression Elimination

The compiler looks for calculations that happen more than once with the same inputs. Instead of repeating the calculation, it computes the result once and reuses it. This reduces unnecessary repeated work.

Avoiding repeated calculations saves time and resources.

Dead Code Elimination

Some parts of the program never affect the final result or are never used. The compiler detects and removes this code, making the program smaller and faster.

Removing unused code cleans up the program and improves performance.

Loop Invariant Code Motion

Inside loops, some calculations do not change with each repetition. The compiler moves these calculations outside the loop so they are done only once, reducing the work done during each loop cycle.

Moving unchanging calculations out of loops reduces repeated work.

Inlining

Instead of calling a function repeatedly, the compiler replaces the call with the actual code of the function. This saves the overhead of jumping to the function and returning, speeding up execution.

Replacing function calls with code reduces call overhead and speeds up the program.

Real World Analogy

Imagine you are cooking a meal with many steps. If you chop all the vegetables once and use them in different dishes, you save time. Also, if you notice you keep peeling the same fruit multiple times, you can peel it once and store it ready to use. Similarly, if some ingredients are never used, you avoid buying them altogether.

Constant Propagation → Using pre-chopped vegetables instead of chopping each time

Common Subexpression Elimination → Peeling a fruit once and using it multiple times instead of peeling repeatedly

Dead Code Elimination → Not buying ingredients that are never used in any dish

Loop Invariant Code Motion → Preparing a sauce once outside the repeated cooking steps instead of making it every time

Inlining → Following a recipe step directly instead of calling someone else to do it and waiting

Diagram

Diagram

┌───────────────────────────────┐
│        Global Optimization     │
├───────────────┬───────────────┤
│ Constant      │ Common        │
│ Propagation   │ Subexpression │
│               │ Elimination   │
├───────────────┼───────────────┤
│ Dead Code     │ Loop Invariant│
│ Elimination   │ Code Motion   │
├───────────────┼───────────────┤
│               │ Inlining      │
└───────────────┴───────────────┘

This diagram shows the main global optimization techniques grouped under the global optimization process.

Key Facts

Global Optimization → Techniques that improve program performance by analyzing and transforming the entire program.

Constant Propagation → Replacing variables with known constant values throughout the program.

Common Subexpression Elimination → Reusing the result of repeated calculations to avoid recomputation.

Dead Code Elimination → Removing code that does not affect the program's output.

Loop Invariant Code Motion → Moving calculations that do not change out of loops to reduce repeated work.

Inlining → Replacing function calls with the actual function code to reduce call overhead.

Code Example

Compiler Design

def example(x):
    a = 5
    b = a + 3  # constant propagation can replace 'a' with 5
    c = x * 2
    d = c  # common subexpression elimination can reuse 'c'
    if False:
        print('This is dead code')  # dead code elimination removes this
    e = 10 + 20  # loop invariant code motion can move this out of the loop
    for i in range(10):
        print(c + d + e)
    return b

Common Confusions

Believing global optimization only looks at small parts of the program.

Believing global optimization only looks at small parts of the program. Global optimization analyzes the entire program to find improvements that local optimizations might miss.

Thinking inlining always makes the program faster.

Thinking inlining always makes the program faster. Inlining can increase code size and sometimes slow down the program if overused.

Assuming dead code elimination removes all unused variables automatically.

Assuming dead code elimination removes all unused variables automatically. Dead code elimination removes code that has no effect on output, but some unused variables may remain if they affect program state.

Summary

Global optimization techniques improve program speed and size by analyzing the whole program.

Key methods include constant propagation, common subexpression elimination, dead code elimination, loop invariant code motion, and inlining.

These techniques reduce repeated work, remove unnecessary code, and streamline function calls.

Practice

1. What is the main goal of global optimization techniques in compiler design?

easy

A. To fix syntax errors in the code

B. To translate code into machine language

C. To improve the performance of the entire program

D. To check for logical errors during runtime

Solution

1. Step 1: Understand the purpose of global optimization

   Global optimization aims to improve the whole program's efficiency, not just parts of it.

2. Step 2: Differentiate from other compiler tasks

   Fixing syntax or translating code are separate compiler phases, not optimization.

3. Final Answer:

   To improve the performance of the entire program -> Option C

4. Quick Check:

   Global optimization = whole program improvement [OK]

Hint: Global optimization means improving the entire program [OK]

Common Mistakes:

• Confusing optimization with syntax checking
• Thinking optimization only fixes errors
• Mixing code translation with optimization

2. Which of the following is a valid example of a global optimization technique?

easy

A. Register allocation

B. Loop-invariant code motion

C. Lexical analysis

D. Syntax parsing

Solution

1. Step 1: Identify global optimization techniques

   Loop-invariant code motion moves calculations out of loops to avoid repeated work.

2. Step 2: Exclude non-optimization tasks

   Syntax parsing and lexical analysis are earlier compiler phases; register allocation is a resource management step.

3. Final Answer:

   Loop-invariant code motion -> Option B

4. Quick Check:

   Moving code out of loops = loop-invariant code motion [OK]

Hint: Look for techniques that reduce repeated work in code [OK]

Common Mistakes:

• Confusing parsing with optimization
• Thinking register allocation is optimization
• Mixing compiler phases

3. Consider this code snippet before optimization:

for (int i = 0; i < n; i++) {
  int x = 5 * 10;
  sum += x;
}

Which global optimization technique can improve this code?

medium

A. Inline expansion

B. Dead code elimination

C. Constant folding

D. Loop-invariant code motion

Solution

1. Step 1: Identify repeated calculation inside the loop

   The expression 5 * 10 does not depend on i and is recalculated every iteration.

2. Step 2: Apply loop-invariant code motion

   Move int x = 5 * 10; outside the loop to avoid repeated calculation.

3. Final Answer:

   Loop-invariant code motion -> Option D

4. Quick Check:

   Move constant calculation out of loop = loop-invariant code motion [OK]

Hint: Move calculations that don't change out of loops [OK]

Common Mistakes:

• Choosing constant folding (done once, but not moving code)
• Confusing dead code elimination with removing unused code
• Thinking inline expansion applies here

4. Identify the error in this global optimization attempt:

int sum = 0;
for (int i = 0; i < n; i++) {
  int x = i * 2;
}
sum += x;

medium

A. Variable x is used outside its scope

B. Loop condition is incorrect

C. Sum variable is not initialized

D. No optimization applied

Solution

1. Step 1: Check variable scope of x

   The variable x is declared inside the loop and cannot be accessed outside it.

2. Step 2: Analyze usage of x after the loop

   Using x after the loop causes a scope error, preventing optimization.

3. Final Answer:

   Variable x is used outside its scope -> Option A

4. Quick Check:

   Variable scope error = using inside variable outside loop [OK]

Hint: Check if variables are used only where declared [OK]

Common Mistakes:

• Ignoring variable scope rules
• Assuming sum is uninitialized
• Thinking loop condition is wrong

5. Given a program with multiple repeated calculations and unused variables scattered across functions, which combination of global optimization techniques would best improve performance?

hard

A. Dead code elimination and loop-invariant code motion

B. Constant folding and syntax checking

C. Register allocation and lexical analysis

D. Inlining and parsing

Solution

1. Step 1: Identify techniques for removing unused code and repeated calculations

   Dead code elimination removes unused variables; loop-invariant code motion moves repeated calculations out of loops.

2. Step 2: Exclude unrelated compiler tasks

   Syntax checking, lexical analysis, parsing, and register allocation are not global optimizations for code improvement.

3. Final Answer:

   Dead code elimination and loop-invariant code motion -> Option A

4. Quick Check:

   Remove unused + move repeated = dead code elimination + loop-invariant motion [OK]

Hint: Combine removing unused code and moving repeated code out [OK]

Common Mistakes:

• Confusing compiler phases with optimization
• Choosing unrelated techniques like parsing
• Ignoring the need for multiple optimizations