Global optimization techniques in Compiler Design - Mini Project: Build & Apply

Understanding Global Optimization Techniques in Compiler Design

📖 Scenario: You are learning about how compilers improve program performance by applying global optimization techniques. These techniques analyze the entire program or large parts of it to make the code run faster or use less memory.

🎯 Goal: Build a simple conceptual map of global optimization techniques used in compiler design. You will create a data structure listing common techniques, add a configuration for their purpose, apply a filter to select techniques based on that purpose, and finally complete the map with a summary description.

📋 What You'll Learn

Create a dictionary named optimizations with exact keys and descriptions of global optimization techniques.

Add a variable named target_purpose to specify the optimization goal.

Use a dictionary comprehension named selected_optimizations to filter techniques matching the target_purpose.

Add a final string variable summary describing the selected techniques.

💡 Why This Matters

🌍 Real World

Compiler developers use global optimization techniques to improve the speed and efficiency of programs by analyzing the entire code.

💼 Career

Understanding these techniques is important for compiler engineers, software developers working on performance-critical applications, and computer science students.

1

Create the dictionary of global optimization techniques

Create a dictionary called optimizations with these exact entries: 'Constant Propagation': 'Replace variables with known constant values', 'Dead Code Elimination': 'Remove code that does not affect the program', 'Loop Invariant Code Motion': 'Move calculations out of loops when possible', 'Common Subexpression Elimination': 'Reuse results of repeated expressions'.

Compiler Design

# Create the dictionary named optimizations with the given techniques and descriptions
# Your code here

Hint

Use a dictionary with the exact keys and values as listed.

2

Add the target purpose variable

Add a variable called target_purpose and set it to the string 'performance' to specify the optimization goal.

Compiler Design

optimizations = {
    'Constant Propagation': 'Replace variables with known constant values',
    'Dead Code Elimination': 'Remove code that does not affect the program',
    'Loop Invariant Code Motion': 'Move calculations out of loops when possible',
    'Common Subexpression Elimination': 'Reuse results of repeated expressions'
}
# Add the target_purpose variable set to 'performance'
# Your code here

Hint

Set target_purpose exactly to the string 'performance'.

3

Filter optimizations by purpose

Create a dictionary comprehension named selected_optimizations that includes only those entries from optimizations where the description contains the word 'code' (case-sensitive).

Compiler Design

optimizations = {
    'Constant Propagation': 'Replace variables with known constant values',
    'Dead Code Elimination': 'Remove code that does not affect the program',
    'Loop Invariant Code Motion': 'Move calculations out of loops when possible',
    'Common Subexpression Elimination': 'Reuse results of repeated expressions'
}
target_purpose = 'performance'
# Create selected_optimizations dictionary with items where 'code' is in the description
# Your code here

Hint

Use a dictionary comprehension filtering descriptions containing 'code'.

4

Add a summary description

Add a string variable called summary that describes the selected optimizations as 'These optimizations focus on removing or reducing unnecessary code to improve performance.'

Compiler Design

optimizations = {
    'Constant Propagation': 'Replace variables with known constant values',
    'Dead Code Elimination': 'Remove code that does not affect the program',
    'Loop Invariant Code Motion': 'Move calculations out of loops when possible',
    'Common Subexpression Elimination': 'Reuse results of repeated expressions'
}
target_purpose = 'performance'
selected_optimizations = {name: desc for name, desc in optimizations.items() if 'code' in desc}
# Add the summary string describing the selected optimizations
# Your code here

Hint

Assign the exact summary string to the variable summary.

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