Global optimization techniques in Compiler Design - Step-by-Step Execution

Concept Flow - Global optimization techniques

Start: Program Code

↓

Analyze Whole Program

↓

Identify Optimization Opportunities

↓

Apply Transformations Globally

↓

Check for Improved Performance

↓

Repeat or Finish

Global optimization looks at the entire program to find and apply improvements that make the program run faster or use less memory.

Execution Sample

Compiler Design

1. Analyze all functions
2. Detect common subexpressions
3. Move invariant code out of loops
4. Inline small functions
5. Remove unused variables

This sequence shows steps a global optimizer might take to improve a program's performance.

Analysis Table

Step	Action	Code Area	Effect	Result
1	Analyze all functions	Whole program	Find repeated calculations	List of common subexpressions
2	Detect common subexpressions	Multiple functions	Avoid repeated work	Subexpressions identified
3	Move invariant code out of loops	Loops	Reduce repeated execution	Loop body smaller
4	Inline small functions	Function calls	Remove call overhead	Faster execution
5	Remove unused variables	Whole program	Reduce memory use	Cleaner code
6	Check performance	Whole program	Measure improvements	Optimization success
7	Repeat if needed	Whole program	Further optimize	Final optimized code
8	Finish	Whole program	No more improvements	Optimized program ready

💡 No more optimization opportunities found, process ends.

State Tracker

Variable	Start	After Step 2	After Step 3	After Step 5	Final
Common Subexpressions	None	Identified	Identified	Identified	Used for optimization
Loop Code Size	Original	Original	Reduced	Reduced	Reduced
Function Calls	Original	Original	Original	Reduced	Reduced
Unused Variables	Present	Present	Present	Removed	Removed

Key Insights - 3 Insights

Why does the optimizer move code out of loops?

Because code that does not change inside a loop wastes time if run repeatedly. Moving it out reduces repeated work, as shown in step 3 of the execution table.

How does inlining small functions improve performance?

Inlining replaces a function call with the function's code, removing the overhead of calling. This is shown in step 4 where function calls are reduced.

Why remove unused variables during global optimization?

Unused variables take memory and clutter code. Removing them cleans the program and can improve memory use, as seen in step 5.

Visual Quiz - 3 Questions

Look at the execution table, at which step are common subexpressions identified?

A Step 2

B Step 1

C Step 3

D Step 4

💡 Hint

Check the 'Action' column for 'Detect common subexpressions' in the execution table.

According to the variable tracker, what happens to loop code size after step 3?

A It increases

B It stays the same

C It reduces

D It is removed

💡 Hint

Look at the 'Loop Code Size' row in the variable tracker after step 3.

If unused variables were not removed, which step's result would change in the execution table?

A Step 3

B Step 5

C Step 6

D Step 7

💡 Hint

Refer to the 'Remove unused variables' action in step 5 of the execution table.

Concept Snapshot

Global optimization techniques analyze the entire program to improve performance.
They detect repeated calculations, move code out of loops, inline functions, and remove unused variables.
These steps reduce execution time and memory use.
Optimization repeats until no more improvements are found.
Global optimization is more powerful but costlier than local optimization.

Full Transcript

Global optimization techniques look at the whole program to find ways to make it run better. The process starts by analyzing all functions to find repeated calculations called common subexpressions. Then, it moves code that does not change out of loops to avoid doing the same work many times. Small functions are inlined to remove the overhead of calling them. Unused variables are removed to save memory and clean the code. After these steps, the optimizer checks if the program runs better. If yes, it may repeat the process to find more improvements. This continues until no more improvements are possible, resulting in an optimized program.

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