Global optimization techniques in Compiler Design - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

What is the main goal of global optimization techniques in compilers?

Global optimization techniques aim to improve the performance of a program by analyzing and transforming code. What is their primary goal?

A To optimize code across multiple functions and blocks for better overall performance

B To reduce the size of the source code without changing performance

C To optimize code only within a single basic block

D To translate code into machine language without any changes

💡 Hint

Think about how global optimization differs from local optimization.

Global optimization techniques analyze the entire program or large parts of it, not just small sections, to improve overall performance by considering interactions between different parts of the code.

📋 Factual

intermediate

Which of the following is a common global optimization technique?

Identify a widely used global optimization technique in compilers.

A Constant folding within a single statement

B Register allocation for a single instruction

C Loop invariant code motion

D Syntax checking during parsing

💡 Hint

Consider optimizations that move code outside loops to avoid repeated execution.

Loop invariant code motion moves calculations that do not change inside a loop to outside the loop, reducing repeated work and improving performance globally.

🔍 Analysis

advanced

What is the effect of dead code elimination on program execution?

Consider a program with some code that never affects the output. What does dead code elimination do, and how does it affect execution?

A Changes the program logic to produce different results

B Removes unused code, reducing program size and potentially improving speed

C Adds extra checks to ensure all code runs at least once

D Duplicates code to improve parallel execution

💡 Hint

Think about code that does not change the program's output or state.

Dead code elimination removes code that does not affect the program's behavior, which reduces size and can improve execution speed by avoiding unnecessary instructions.

❓ Reasoning

advanced

Why is interprocedural analysis important for global optimization?

Interprocedural analysis looks at multiple functions together. Why is this important for global optimization?

A It allows optimizations that consider interactions between functions, improving overall program efficiency

B It limits optimization to one function at a time to avoid errors

C It only checks syntax errors across functions

D It duplicates functions to increase code size for better caching

💡 Hint

Think about how functions can affect each other’s behavior.

Interprocedural analysis enables the compiler to optimize across function boundaries by understanding how functions interact, leading to better global optimizations.

❓ Comparison

expert

Compare the impact of global common subexpression elimination (GCSE) versus local common subexpression elimination (LCSE). Which statement is true?

Consider two optimization techniques: GCSE and LCSE. Which of the following correctly compares their impact?

A GCSE duplicates expressions to improve readability, LCSE removes them

B LCSE eliminates more redundant calculations than GCSE because it works globally

C Both GCSE and LCSE only optimize within a single basic block

D GCSE can eliminate repeated calculations across multiple blocks, while LCSE only within a single block

💡 Hint

Think about the scope each technique covers.

GCSE looks for repeated expressions across multiple blocks or functions, removing more redundancy than LCSE, which only works inside one block.

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