8.2 Principal Sources of Code Optimization: Local, Global & Loop Transformations

Back to DBMS Notes

📚Module 01Principal Sources of Code Optimization⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: The Formula 1 Pit Crew & Track Engineer

Writing high-level source code is like a racing driver navigating a Grand Prix course. The Code Optimizer is the telemetry engineering team and pit crew that tunes the vehicle before race day:

• Constant Folding: Instead of having the car's onboard computer compute $2 \times 3.1415$ every millisecond while hurtling down the straight, the engineer pre-computes $6.283$ in the garage before the race begins.
• Loop-Invariant Code Motion (Hoisting): If a mechanic needs to verify tire pressure, they do it once in the pit lane before the driver starts their stint, rather than jumping onto the chassis to check the tire on every lap around the circuit.
• Strength Reduction: Instead of driving a heavy hydraulic turbine (multiplication) on every revolution, they swap it for an incremental tooth gear (addition) that delivers the exact same mechanical output with 80% less engine friction.

💻 Bridging to Computer Science: Pruning Computational Waste Across Scope Boundaries

In compiler optimization:

• Optimization passes transform intermediate code into equivalent code that runs faster, uses less memory, and consumes less energy.
• Local Optimizations operate within a single basic block (e.g. local common subexpression elimination via DAGs).
• Loop Optimizations target the inner loops where programs spend 90% of their execution time (the 90/10 Rule), applying loop-invariant code motion, induction variable elimination, and strength reduction.

📑Table of Contents

• 🏗️ Architectural Foundations: Local vs Global vs Loop Optimizations
• 📐 Formal Foundations: The Three Cardinal Rules of Optimization
• 🛠️ Taxonomy of Machine-Independent Transformations
  • 1️⃣ Compile-Time Evaluation
  • 2️⃣ Common Subexpression Elimination (CSE)
  • 3️⃣ Copy Propagation
  • 4️⃣ Dead Code Elimination
• 🔄 Deep-Dive: Loop Optimizations
  • 1️⃣ Loop-Invariant Code Motion (LICM / Hoisting)
  • 2️⃣ Induction Variables & Strength Reduction
• 🏭 Real-World Production Context: How Industry Builds This
• 📐 Numerical Applications & Worked Examples
  • Example 1: Full Loop Optimization Pipeline
  • Example 2: Legality of Loop-Invariant Code Motion
• 🎯 Exam & Interview Pitfall Check

---

🏗️ Architectural Foundations: Local vs Global vs Loop Optimizations

Scope of Optimization: Local vs Global vs Loop

Classifying compiler optimizations by the scope of their analysis windows

Local

Local Optimization

🔍

Dominant Architecture / DomainSingle Basic Block (Straight-Line Code)

• •Analyzes straight-line code within one isolated basic block.
• •Uses DAG construction and local value numbering.
• •Fastest compile-time execution; zero inter-block dataflow tracking.
• •Eliminates local duplicate calculations and constant expressions.

"Micro-optimizations confined strictly within straight-line boundaries."

Loop

Loop Optimization

🔄

Dominant Architecture / DomainNatural Loops, Inner Hotspots (90/10 Rule)

• •Targets the 10% of code that consumes 90% of total CPU execution time.
• •Hoists invariant expressions to the loop preheader.
• •Replaces heavy multiplications with iterative additions (strength reduction).
• •Eliminates redundant induction variables to free up physical hardware registers.

"Maximizing ROI: speeding up hot inner loops transforms overall runtime."

---

📐 Formal Foundations: The Three Cardinal Rules of Optimization

Any automated code optimization pass in a production compiler must strictly adhere to three foundational axioms:

1. Semantic Preservation (The Golden Rule): The transformation must preserve the exact observable behavior of the program across all legal inputs. A transformation that speeds up code by $10\times$ but produces an incorrect answer on $0.01\%$ of inputs is not an optimization; it is a critical compiler bug.
2. Speed & Size Improvement: The transformation must measurably reduce execution time, CPU cycles, or binary code size on average target workloads.
3. Reasonable Compile-Time Overhead: The compiler must complete optimization passes in reasonable time. Spending 45 minutes of compile time to save 2 nanoseconds of runtime is mathematically impractical.

---

🛠️ Taxonomy of Machine-Independent Transformations

Architecture Flow

Core Machine-Independent Optimization Transformations

The progressive reduction of redundant operations across intermediate code

🧮Compile-Time

Constant Folding & Propagation

Evaluating static operations at compile time and forwarding constant values.

→

Enables

✂️Deduplication

Common Subexpression Elimination

Reusing previously computed values instead of recalculating identical expressions.

→

Exposes

🗑️Pruning

Dead Code Elimination

Deleting instructions whose results are never read by any live variable.

→

Refines

🚀Loop Hoisting

Loop-Invariant Code Motion

Lifting loop-independent computations out of the loop into a preheader.

1️⃣ Compile-Time Evaluation

• Constant Folding: The compiler computes the values of expressions whose operands are known compile-time constants:

  $$x = 24 \times 60 \times 60 \implies x = 86400$$

• Constant Propagation: If a variable $x$ is assigned a constant value $c$, the compiler replaces all subsequent uses of $x$ (up until any potential reassignment) with the constant $c$:

  $$\begin{aligned} r &= 10 \\ \text{area} &= 3.1415 \times r \times r \implies \text{area} = 3.1415 \times 10 \times 10 = 314.15 \end{aligned}$$

2️⃣ Common Subexpression Elimination (CSE)

An occurrence of an expression $E$ is a Common Subexpression if $E$ was previously computed, and the values of the operands of $E$ have not changed since the previous computation.

// Before CSE:
t1 = 4 * i;
v = a[t1];
t2 = 4 * i; // Redundant! Operands 4 and i are unchanged.
w = b[t2];

// After CSE:
t1 = 4 * i;
v = a[t1];
w = b[t1];  // Reuses t1 directly!

3️⃣ Copy Propagation

Given a copy assignment $x = y$, copy propagation replaces uses of $x$ with $y$, provided no assignment to $y$ occurs in between. While $x = y$ itself does not seem wasteful, copy propagation frequently turns variable $x$ into Dead Code, enabling the entire assignment to be erased!

4️⃣ Dead Code Elimination

A variable is live at point $p$ if its value could be read along some execution path starting at $p$; otherwise, it is dead. Any assignment $x = y + z$ where $x$ is dead and the expression produces no observable side effects (such as memory writes or exceptions) can be deleted outright.

---

🔄 Deep-Dive: Loop Optimizations

Since software spends the vast majority of execution time inside loops, loop transformations yield the highest performance returns:

1️⃣ Loop-Invariant Code Motion (LICM / Hoisting)

An expression is Loop-Invariant if its operands take on the exact same value across every iteration of the loop.

Preconditions for Hoisting Expressions Out of Loop L:

To safely hoist an assignment $x = y + z$ to a loop preheader block:

1. The definition of $x$ must dominate all exits of loop $L$ (or $x$ must be dead at all loop exits).
2. There must be no other assignment to variable $x$ within loop $L$.
3. The definition of $x$ must dominate all uses of $x$ inside loop $L$.

// Before Hoisting:
for (int i = 0; i < n; i++) {
    x = y + z;        // y and z do not change inside the loop!
    a[i] = 6 * i + x;
}

// After Hoisting:
x = y + z;            // Hoisted out to Loop Preheader!
for (int i = 0; i < n; i++) {
    a[i] = 6 * i + x;
}

2️⃣ Induction Variables & Strength Reduction

A variable $x$ is an Induction Variable of a loop if its value changes by a constant amount each time around the loop:

• Basic Induction Variable ($i$): Only updated via $i = i \pm c$.
• Derived Induction Variable ($j$): Defined as $j = c_1 \times i + c_2$, where $i$ is a basic induction variable.

Strength Reduction replaces expensive operations (e.g. integer multiplication $4 \times i$) with cheaper hardware operations (e.g. addition $t = t + 4$):

Strength Reduction & Induction Variable Elimination Trace

Lowering iterative multiplication into incremental addition

High-Level Loop

Loop Preheader

Loop Body

Loop Increment

1

High-Level Loop→Loop Preheader

Initialize Derived Temp

2

Loop Body→Loop Body

Replace Multiplication with Temp

3

Loop Increment→Loop Increment

Additive Step

4

Loop Increment→High-Level Loop

Eliminate Basic Variable

---

🏭 Real-World Production Context: How Industry Builds This

In industrial production compilers (such as GCC, Clang, and HotSpot JIT):

Modern compilers group optimization passes into standardized levels:

• -O0: Zero optimizations. Generates literal 1-to-1 machine instructions matching the source. Essential for interactive debugging.
• -O1: Basic optimizations: local DAG simplifications, dead code elimination, and constant propagation.
• -O2: Production default: global common subexpression elimination, loop-invariant code motion (LICM), strength reduction, and function inlining.
• -O3: Aggressive optimizations: automatic SIMD auto-vectorization (AVX-512), loop unrolling, and link-time whole-program optimization.
• -Os / -Oz: Size-focused optimizations: disables code-duplicating passes (like unrolling) to produce the smallest executable binary for embedded devices.

In LLVM's LoopVectorizePass, loops operating over independent array indices are transformed to execute multiple iterations simultaneously using CPU SIMD vector registers (e.g. processing 8 32-bit floats in a single AVX clock cycle).

---

📐 Numerical Applications & Worked Examples

Example 1: Full Loop Optimization Pipeline

Consider the following unoptimized Three-Address Code for clearing an array of 50 integers:

(1)  i = 1
(2)  t1 = 4 * i
(3)  a[t1] = 0
(4)  t2 = i + 1
(5)  i = t2
(6)  if i <= 50 goto (2)

Apply:

1. Strength Reduction on the derived induction variable $t_1$.
2. Induction Variable Elimination to completely remove the basic induction variable $i$. Show the final optimized instruction stream.

Step-by-Step Analytical Solution:

Step 1: Identify Induction Variables

• Basic induction variable: $i$ (starts at 1, incremented by 1 in lines 4–5).
• Derived induction variable: $t_1 = 4 \times i$.

Step 2: Apply Strength Reduction on Derived Variable $t_1$

• In the preheader (before loop entry):
  • At $i = 1$, $t_1 = 4 \times 1 = 4$.
  • Emit initialization: $t_1 = 4$.
• Inside the loop:
  • When $i$ increments by $1$, $t_1$ increases by $4 \times 1 = 4$.
  • Replace line (2) $t_1 = 4 \times i$ with an incremental addition at the bottom of the loop: $t_1 = t_1 + 4$.

Intermediate Code:
(1)  i = 1
(2)  t1 = 4
(3)  a[t1] = 0
(4)  t1 = t1 + 4
(5)  t2 = i + 1
(6)  i = t2
(7)  if i <= 50 goto (3)

Step 3: Eliminate Basic Induction Variable $i$ After strength reduction, variable $i$ is consumed only to evaluate the loop termination condition: if i <= 50 goto (3).

• At termination: $i \le 50 \iff 4 \times i \le 4 \times 50 \iff t_1 \le 200$.
• Because line (4) increments $t_1$ before the test, when $i = 50$, $t_1$ reaches $4 \times 50 + 4 = 204$.
• Therefore, the condition $i \le 50$ is mathematically equivalent to: $t_1 \le 200$ (testing against the updated bound).
• Variables $t_2$ and $i$ are now completely dead! We eliminate them entirely.

Final Optimized Three-Address Code:

(1) t1 = 4
(2) a[t1] = 0
(3) t1 = t1 + 4
(4) if t1 <= 200 goto (2)

Optimization Results:

• Loop body reduced from 5 instructions to 3 instructions.
• Costly hardware multiplication $4 \times i$ eradicated.
• Register pressure halved: variable $i$ is deleted from physical register allocation!

---

Example 2: Legality of Loop-Invariant Code Motion

Consider the loop:

while (p > 0) {
    if (flag == 1) {
        x = a + b;
    }
    p--;
}

Can the statement $x = a + b$ be hoisted out of the loop into a preheader if variables $a$ and $b$ are never modified inside the loop? Justify analytically.

Step-by-Step Analytical Trace:

1. Verify Precondition 1 (Dominance of Exits):
   • Does the statement $x = a + b$ dominate all exits of the loop?
   • No. If $\text{flag} \neq 1$, the statement $x = a + b$ is bypassed, yet the loop decrements $p$ and terminates when $p \le 0$.
2. Failure Counterexample:
   • Suppose before the loop: $x = 100$ and $\text{flag} = 0$.
   • During loop execution, because $\text{flag} == 0$, $x$ is never assigned, so after the loop exits, $x$ must remain $100$.
   • If the compiler unconditionally hoists $x = a + b$ to the preheader:
     • $x$ will be overwritten with $a + b$ even when $\text{flag} == 0$!
   • This alters the value of $x$ observable after the loop, directly violating the Semantic Preservation Axiom.
3. Verdict: The statement CANNOT be hoisted unless the compiler can prove that $\text{flag} == 1$ is invariant across all iterations, or $x$ is dead outside the loop.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: "What are the essential preconditions required before an expression can be safely hoisted out of a loop?"
Key Focus Points:

• The statement defining $x$ must dominate all loop exits (or $x$ must be dead at all loop exits).
• There must be no other assignments to $x$ in the loop.
• The definition of $x$ must dominate all uses of $x$ in the loop.

Question 2: "What is the difference between a basic induction variable and a derived induction variable?"
Key Focus Points:

• Basic Induction Variable: A variable $i$ whose only assignments in the loop have the form $i = i \pm c$ (where $c$ is a loop-invariant constant).
• Derived Induction Variable: A variable $j$ whose value is a linear function of a basic induction variable ($j = c_1 \times i + c_2$).

Common Interview Traps: Architectural Trade-Offs

Trap 1: Hoisting potentially trapping operations out of conditional loops.
Answer: Critical safety hazard. If an expression like $x = y / z$ sits inside a loop that may execute zero times, hoisting it to a preheader can trigger an unexpected floating-point exception (SIGFPE if $z == 0$) on inputs that would have run safely in the unoptimized program.

Trap 2: Assuming loop unrolling always improves performance.
Answer: Hardware cache penalty. Aggressive loop unrolling inflates machine code footprint. If the loop size exceeds the CPU's Level-1 Instruction Cache (L1 I-Cache), severe cache thrashing occurs, causing the program to run slower than the unrolled original.

---

🗺️View Complete Compiler Design Roadmap & Syllabus

← Previous Topic8.1 Basic Blocks, Flow Graphs & Control Flow AnalysisNext Topic →8.3 Runtime Environments, Activation Records & Storage Allocation