Code Optimization

Part 1: Local Optimization

Introduction

In the architecture of a modern compiler, the code optimization phase stands as a critical bridge between intermediate code generation and target code generation. Its primary objective is to transform the intermediate representation of a program into a functionally equivalent version that executes more efficiently, either by running faster, consuming less memory, or reducing power consumption. We can broadly classify optimization techniques based on their scope of application.

Local optimization represents the most fundamental level of this process. It operates exclusively within the confines of a basic block, which is a straight-line sequence of code with no branches in or out, except at the beginning and end. Because the control flow within a basic block is linear and predictable, we can apply a variety of powerful transformations with a high degree of certainty and relatively low computational cost. These optimizations lay the groundwork for more complex, global optimizations that analyze the entire control-flow graph of a function. For the GATE examination, a firm grasp of identifying basic blocks and applying techniques like common sub-expression elimination is essential.

📖 Basic Block

A basic block is a maximal sequence of consecutive three-address code statements such that:

Control flow can only enter the block at the first statement, which is called the leader.

Control flow will leave the block after the last statement, without any possibility of halting or branching, except at the very end.

---

Key Concepts

#
## 1. Identifying Basic Blocks

Before any local optimization can be performed, we must first partition the intermediate code into its constituent basic blocks. This partitioning is accomplished by first identifying the "leaders" in the code.

The algorithm for identifying leaders is as follows:

The very first statement in the intermediate code is a leader.

Any statement that is the target of a conditional or unconditional jump is a leader.

Any statement that immediately follows a conditional or unconditional jump is a leader.

Once the leaders have been identified, a basic block is formed by taking a leader and all subsequent statements up to, but not including, the next leader.

Control Flow Graph Example

B1 (Leader: i=1)
j = 1

B2 (Leader: if i<10)
t1 = a[i]
t2 = b[j]

B3 (Leader: x=t1)
i = i + 1

B4 (Leader: y=t2)
j = j + 1

True

False

---

#
## 2. Common Sub-expression Elimination (CSE)

This is one of the most effective local optimizations. The core idea is to identify instances where the exact same expression is computed multiple times within a basic block. If we can verify that the values of the operands involved in the expression have not changed between computations, we can avoid re-computation.

The process involves:

Scanning the basic block for identical expressions.

For the first occurrence of an expression, say `y + z`, we compute it and store the result in a new temporary variable, say `t`.

For all subsequent occurrences of `y + z` within the same block, we replace the computation with a reference to `t`.

This is valid only as long as the values of `y` and `z` are not altered between the points of use.

Worked Example:

Problem: Consider the following code segment within a basic block. Count the number of additions and multiplications before and after applying Common Sub-expression Elimination.

```c
a = b + c;
d = x * y;
e = b + c;
f = x * y;
g = b + c;
```

Solution:

Before Optimization:

We can directly count the operations.

Additions: 3 (for `a`, `e`, `g`)

Multiplications: 2 (for `d`, `f`)

Total operations: 5

Applying CSE:

Step 1: Identify the common sub-expressions.
We observe two common sub-expressions: `b + c` and `x * y`.

Step 2: Introduce temporary variables for the first occurrences.
Let us introduce `t1` for `b + c` and `t2` for `x * y`.

t_1 = b + c

t_2 = x * y

Step 3: Rewrite the code using the temporary variables.
The first statements compute and store the results. Subsequent occurrences will reuse these results.

```c
// Optimized code
t1 = b + c; // 1st add
a = t1;
t2 = x * y; // 1st mul
d = t2;
e = t1; // Reuse t1
f = t2; // Reuse t2
g = t1; // Reuse t1
```

Step 4: Count the operations in the optimized code.

Additions: 1 (for `t1 = b + c`)

Multiplications: 1 (for `t2 = x * y`)

Total operations: 2

Result:

Before optimization: 3 additions, 2 multiplications.

After optimization: 1 addition, 1 multiplication.

Operations saved: 2 additions and 1 multiplication.

---

#
## 3. Constant Folding and Constant Propagation

These two optimizations are often used in tandem to simplify code at compile time.

📖 Constant Folding

The process of evaluating expressions at compile time whose operands are known to be constant. The constant result then replaces the expression in the intermediate code.

For instance, the statement `x = 2 3.14 10;` would be pre-calculated by the compiler and transformed into `x = 62.8;`.

📖 Constant Propagation

The process of replacing a variable with its known constant value in subsequent expressions. If we have a statement `x = 5;`, any following use of `x` can be replaced by `5`, provided `x` is not redefined in between.

Constant propagation often enables further constant folding.

Worked Example:

Problem: Optimize the following code using constant propagation and constant folding.

```c
const int a = 10;
int b = 20 - a;
int c = b * 4;
int d = 30;
```

Solution:

Step 1: Apply constant propagation for `a`.
The value of `a` is `10`. We substitute this into the expression for `b`.

```c
const int a = 10;
int b = 20 - 10; // Propagated 'a'
int c = b * 4;
int d = 30;
```

Step 2: Apply constant folding for `b`.
The expression `20 - 10` can be evaluated at compile time.

```c
const int a = 10;
int b = 10; // Folded '20 - 10'
int c = b * 4;
int d = 30;
```

Step 3: Apply constant propagation for `b`.
The new constant value of `b` (`10`) can be propagated to the expression for `c`.

```c
const int a = 10;
int b = 10;
int c = 10 * 4; // Propagated 'b'
int d = 30;
```

Step 4: Apply constant folding for `c`.
The expression `10 * 4` can be evaluated at compile time.

```c
const int a = 10;
int b = 10;
int c = 40; // Folded '10 * 4'
int d = 30;
```

Result: The optimized code has replaced computations with their final constant values, which are directly assigned.

---

#
## 4. Algebraic Simplification and Strength Reduction

These techniques leverage mathematical properties to transform code into a more efficient form.

Algebraic Simplification uses identities to simplify expressions.

Additive Identity: `x = y + 0;` becomes `x = y;`

Multiplicative Identity: `x = y * 1;` becomes `x = y;`

Multiplicative Zero: `x = y * 0;` becomes `x = 0;`

Strength Reduction involves replacing a computationally expensive (stronger) operation with an equivalent, but cheaper (weaker), one.

A common case is replacing multiplication with addition, especially inside loops. For example, `x * 2` can be replaced by `x + x` or a bitwise left shift `x << 1`.

In a loop, an expression like `i * 4` (where `i` is the loop index) can be replaced by a new variable that is initialized to `0` and incremented by `4` in each iteration.

📐
Strength Reduction in Loops

\begin{aligned} & \textbf{Original Code} \\ & \text{for (i=0; i<N; i++) \{ } \\ & \quad \text{...} = \text{base\_addr} + i \times C; \\ & \text{\}}\end{aligned}\quad \longrightarrow \quad\begin{aligned} & \textbf{Optimized Code} \\ & \text{temp = base\_addr;} \\ & \text{for (i=0; i<N; i++) \{ } \\ & \quad \text{...} = \text{temp;} \\ & \quad \text{temp = temp} + C; \\ & \text{\}}\end{aligned}

Variables:

$i$ : loop induction variable

$C$ : a constant stride

$\text{temp}$ : a new temporary variable

When to use: When a multiplication inside a loop depends linearly on the loop's induction variable. This is extremely common in array address calculations.

---

Problem-Solving Strategies

💡 GATE Strategy: Systematic Optimization Analysis

When presented with a code snippet and asked to count operations after optimization, follow a rigorous procedure:

Partition into Basic Blocks: First, identify all leaders and clearly delineate the basic blocks. This defines the scope of your local analysis.

Apply CSE within each Block: For each basic block, scan for common sub-expressions. Introduce temporary variables (e.g., `t1`, `t2`) to store the results of the first computation. Replace all subsequent identical computations in that block with the temporary variable.

Apply Constant Folding/Propagation: Evaluate all constant expressions and propagate constant values. This may simplify the code further.

Check for Strength Reduction: Pay special attention to loops. If you see multiplication involving the loop variable (`i * constant`), replace it with a new variable that is updated with addition in each iteration.

Rewrite the Final Code: Write down the fully optimized version of the code, incorporating all the changes. This is your reference for the final count.

Count Operations Carefully: Read the question to see exactly which operations to count (e.g., "additions", "dereferences", "multiplications"). Go through your rewritten code line-by-line and tally the counts. Do not forget to count the initial computations that are stored in your temporary variables.

---

Common Mistakes

⚠️ Avoid These Errors

❌ Ignoring Operand Re-definitions: Applying CSE for an expression `x + y` after `x` or `y` has been assigned a new value.

✅ Correct Approach: A sub-expression is only "common" if its constituent operands have not been modified since the last time it was computed. Always check for intermediate assignments to operands.

❌ Incorrect Basic Block Identification: Failing to identify a leader correctly, either by missing a jump target or the statement following a jump. This leads to an incorrect scope for local optimization.

✅ Correct Approach: Methodically apply the three rules for finding leaders before beginning any optimization analysis.

❌ Miscounting Operations Post-Optimization: Forgetting to count the single computation that is stored in the temporary variable during CSE. For `t1 = a + b; x = t1; y = t1;`, the addition count is 1, not 0.

✅ Correct Approach: The optimized code still performs the operation once. Count this initial computation and then note that subsequent uses add no further operational cost.

❌ Confusing Strength Reduction with CSE: Treating `i * 4` in a loop as a simple common sub-expression. While it might be, the more powerful optimization is strength reduction.

✅ Correct Approach: Recognize that expressions involving loop induction variables are primary candidates for strength reduction, which replaces multiplication with addition, a more significant saving.

---

Practice Questions

:::question type="MCQ" question="Consider the following code segment, which exists within a single basic block. Assume all variables are in registers.
```c
a = x + y;
b = a - z;
c = x + y;
d = c * 5;
e = a - z;
```
After applying local common sub-expression elimination, what is the minimum number of addition/subtraction operations required?" options=["2","3","4","5"] answer="2" hint="Identify the repeated expressions and introduce temporary variables. Count the operations in the transformed code." solution="
Step 1: Identify the common sub-expressions.
The expression `x + y` is computed twice.
The expression `a - z` is computed twice.

Step 2: Introduce temporary variables and rewrite the code.
Let `t1 = x + y` and `t2 = a - z`. However, we can be more efficient. The value of `x + y` is already stored in `a`. So we can reuse `a`. The value of `a - z` is stored in `b`. We can reuse `b`.

Let's use explicit temporaries for clarity.
`t1 = x + y;` (1st addition)
`a = t1;`
`t2 = a - z;` (1st subtraction)
`b = t2;`
`c = t1;` (Reuse `t1` instead of `x + y`)
`d = c * 5;`
`e = t2;` (Reuse `t2` instead of `a - z`)

Step 3: Count the addition/subtraction operations in the optimized code.
The first operation is `t1 = x + y` (1 addition).
The second operation is `t2 = a - z` (1 subtraction).
The subsequent assignments `c = t1` and `e = t2` do not involve any new additions or subtractions.

Result:
The total number of addition/subtraction operations is $1 + 1 = 2$ .
"
:::

:::question type="NAT" question="Given the following code fragment, what is the final value of the variable `z` after constant folding and constant propagation are applied by the compiler?
```c
int x = 5;
int y = 2 * x + 1;
int z = y - 3;
x = 10;
```" answer="8" hint="Propagate the initial value of `x` to the calculation of `y`, then fold the constants. The final assignment to `x` does not affect the value of `z`." solution="
Step 1: Initial values.
`x` is initialized to `5`.

Step 2: Propagate the constant value of `x` into the expression for `y`.
The statement `y = 2 x + 1;` becomes `y = 2 5 + 1;`.

Step 3: Apply constant folding to the expression for `y`.
`y = 10 + 1;`
`y = 11;`
The compiler now knows that `y` is `11`.

Step 4: Propagate the constant value of `y` into the expression for `z`.
The statement `z = y - 3;` becomes `z = 11 - 3;`.

Step 5: Apply constant folding to the expression for `z`.
`z = 8;`

Step 6: Analyze the final statement.
The statement `x = 10;` redefines `x`, but this happens after `z` has already been computed. Therefore, it has no effect on the final value of `z`.

Result:
The final value of `z` is 8.
"
:::

:::question type="MSQ" question="Which of the following local optimization techniques can be applied to the given basic block of code?
```c
a = 10 * 5;
b = x - 0;
c = y * 2;
d = x - 0;
```" options=["Constant Folding","Algebraic Simplification","Common Sub-expression Elimination","Strength Reduction"] answer="Constant Folding,Algebraic Simplification,Common Sub-expression Elimination,Strength Reduction" hint="Examine each line of code for opportunities to apply each of the listed optimizations." solution="

Constant Folding: The expression `10 * 5` in the first statement can be evaluated at compile time to `50`. So, Constant Folding is applicable.

Algebraic Simplification: The expressions `x - 0` use the additive identity rule (where subtraction is the inverse of addition). `x - 0` can be simplified to just `x`. So, Algebraic Simplification is applicable.

Common Sub-expression Elimination: The expression `x - 0` appears twice. After one is computed (or simplified), the result can be reused for the second. So, CSE is applicable.

Strength Reduction: The expression `y * 2` can be replaced by a cheaper operation, `y + y` or `y << 1`. So, Strength Reduction is applicable.

Therefore, all four optimizations can be applied to this code block.
"
:::

:::question type="MCQ" question="How many basic blocks are present in the following C code segment?
```c
1: i = 0;
2: if (i >= 10) goto L2;
3: L1:
4: a = a + 1;
5: i = i + 1;
6: if (i < 10) goto L1;
7: L2:
8: return a;
```" options=["2","3","4","5"] answer="3" hint="Identify the leaders first. The first statement is a leader. Any target of a goto is a leader. Any statement immediately after a goto is a leader." solution="
Step 1: Apply the rules for finding leaders.

Rule 1: Statement 1 (`i = 0;`) is the first statement, so it is a leader.

Rule 2: Statement 3 (label `L1`) is the target of `goto L1`. So, statement 3 is a leader.

Rule 2: Statement 7 (label `L2`) is the target of `goto L2`. So, statement 7 is a leader.

Rule 3: The statement after `goto L2` (statement 3) is already a leader. The statement after `goto L1` (statement 7) is also already a leader.

Step 2: Identify the leaders.
The leaders are statements 1, 3, and 7.

Step 3: Form the basic blocks.
A basic block starts with a leader and includes all statements up to the next leader.

Block 1: Starts at leader 1 and goes up to (but not including) leader 3. This block contains statements 1 and 2.

Block 2: Starts at leader 3 and goes up to (but not including) leader 7. This block contains statements 3, 4, 5, and 6.

Block 3: Starts at leader 7 and goes to the end. This block contains statements 7 and 8.

Result:
There are 3 basic blocks in the code.
"
:::

---

Summary

❗ Key Takeaways for GATE

Scope is Key: Local optimization is confined to basic blocks. The first step in any analysis must be the correct partitioning of code into these blocks by identifying leaders.

CSE is High-Yield: Common Sub-expression Elimination is a frequently tested and powerful technique. The core skill is to identify a repeated computation, store its result in a temporary variable, and reuse that result.

Check for Operand Validity: A sub-expression is only "common" if none of its operands have been redefined between computations. This is a critical detail that can change the outcome of an optimization problem.

Rewrite and Count: For numerical problems, always rewrite the optimized code segment. This provides a clear and unambiguous basis from which to count the required operations (additions, multiplications, dereferences, etc.), minimizing calculation errors.

---

What's Next?

💡 Continue Learning

This topic serves as a foundation for more advanced compiler optimizations.

Global Optimization: This is the next logical step. It extends the principles of local optimization to an entire function's control-flow graph. Techniques like global common sub-expression elimination and loop-invariant code motion operate across basic block boundaries.
Data Flow Analysis: To perform global optimizations safely and effectively, the compiler relies on a formal framework known as data flow analysis. Understanding concepts like Reaching Definitions and Live Variable Analysis is essential for comprehending how a compiler can reason about the flow of data across an entire program.

Code Optimization

Code Optimization

Part 1: Local Optimization

Introduction

Key Concepts

Problem-Solving Strategies

Common Mistakes

Practice Questions

Summary

What's Next?

🎯 Key Points to Remember

Related Topics in Compiler Design

Lexical Analysis

Syntax-Directed Translation

Intermediate Code Generation

Parsing (Syntax Analysis)

More Resources

Study Notes

Short Notes

Test Series

Mock Tests

Previous Year Papers

Chapter-wise PYQs

Chapter Practice

Why Choose MastersUp?

AI-Powered Plans

15,000+ Questions

Smart Analytics

Bookmark & Revise