Code Optimization: Techniques, Flow Graphs & Intermediate Code

TAKEAWAYS:

• Code optimization transforms intermediate code into efficient target code by eliminating redundant operations, simplifying expressions, and reducing runtime overhead.
• Basic blocks and control flow graphs are the foundation for identifying optimization opportunities in loops, conditionals, and arithmetic expressions.
• Three-address code (e.g., quadruples) is the standard intermediate representation where optimizations like constant folding (3 + 5 → 8) and copy propagation (y = x; z = y → z = x) are applied.
• Strength reduction replaces expensive operations (e.g., x * 2 → x << 1) to speed up execution, while dead code elimination removes unreachable or unused computations.
• Real-world systems (e.g., Ncell’s billing engine, Daraz’s order queue) use these techniques to handle millions of transactions efficiently.
• Exam questions focus on constructing flow graphs, applying optimizations step-by-step, and converting code to basic blocks—always trace variable changes visually.

1. What is Code Optimization?

Code optimization is the process of transforming intermediate code (e.g., three-address code) into an equivalent but more efficient target code without changing the program’s functionality. The goal is to:

• Reduce execution time (critical for apps like eSewa or Khalti during peak transactions).
• Minimize memory usage (important for Pathao’s driver-app updates).
• Improve code readability (helps maintainers at NTC or NEPSE).

Key Idea: Optimizations are applied after syntax/semantic analysis but before code generation, targeting intermediate representations like:

• Three-address code (e.g., t1 = a + b).
• Quadruples/triples (e.g., (+, t1, a, b)).
• Control flow graphs (CFGs).

2. Intermediate Code Representations (Visual)

Before optimization, code is converted to a structured form. Here’s how three-address code and quadruples represent the same arithmetic expression:

Example: x = 3; y = x; z = x + 5;

flowchart TD
    A["Original Code"] --> B["Three-Address Code"]
    B --> C["Quadruples"]
    C --> D["Optimized Quadruples"]

Three-Address Code:

t1 = 3
x = t1
y = x
t2 = x + 5
z = t2

Quadruples:

3. Optimization Techniques (With Real-World Ties)

A. Constant Folding

Definition: Evaluating constant expressions at compile time. Example: t2 = x + 5 → If x = 3, this becomes t2 = 8 (no runtime addition needed).

Real-World Use:

• Ncell’s Billing System: Pre-calculates fixed charges (e.g., total = base_fee + tax) to speed up invoice generation.
• Daraz Order Processing: Folds constants like discount = 100 - (price * 0.1) into discount = price * 0.9 for faster checkout.

Worked Example:

flowchart LR
    A["Before: t2 = x + 5"] -->|"x=3"| B["After: t2 = 8"]

Code Trace:

B. Copy Propagation

Definition: Replacing variable copies with their original values to eliminate redundant loads/stores. Example: y = x; z = y + 5 → z = x + 5.

Real-World Use:

• eSewa’s Transaction Logs: Avoids copying user IDs (user = session.user; log(user) → log(session.user)) to reduce memory writes.
• Bank Loan Calculators: Propagates interest_rate = 0.05 directly into emi = (loan * rate) / term instead of storing rate separately.

Visual Trace:

flowchart TD
    A["Before:\ny = x\nz = y + 5"] --> B["After:\nz = x + 5"]

Code Example:

# Before optimization
x = 3
y = x
z = y + 5

# After copy propagation
x = 3
z = x + 5

C. Dead Code Elimination

Definition: Removing unreachable or unused computations. Example:

if False:
    temp = a + b  # Dead code (unreachable)
x = c + d         # Live code

→ Compiler removes temp = a + b.

Real-World Use:

• Pathao’s Driver App: Eliminates unused GPS coordinates when the app is in idle mode.
• NEPSE Stock Alerts: Skips redundant checks (e.g., if (market_closed) { check_prices() }) when the market is closed.

Flow Graph Visualization:

graph TD
    A["Start"] --> B["if False"]
    B --> C["temp = a + b"] --> D["x = c + d"]

D. Strength Reduction

Definition: Replacing expensive operations with cheaper ones. Examples:

• x * 2 → x << 1 (bit shift is faster).
• x / 2 → x >> 1 (for integers).

Real-World Use:

• Google’s Search Index: Uses bit shifts to scale document IDs in ranking algorithms.
• WhatsApp Media Compression: Replaces division by 2 with right shifts to speed up JPEG resizing.

Code Comparison:

flowchart LR
    A["Before:\nx = x * 2"] --> B["After:\nx = x << 1"]

4. Control Flow Graphs (CFGs) and Basic Blocks

Optimizations rely on analyzing CFGs and basic blocks (sequences of instructions with no branches except at the end).

A. Basic Blocks

A basic block is a maximal sequence of instructions where:

1. The first instruction has no predecessors.
2. Every other instruction is reachable from the first.
3. The last instruction is a branch or the end of the function.

Example: Convert this to basic blocks:

i = 1
sum = 0
while i <= x:
    square = i * i
    sum = sum + square
    i = i + 1

Step-by-Step Construction:

flowchart TD
    A["BB1:\ni = 1\nsum = 0"] --> B["BB2:\nwhile i <= x"]
    B --> C["BB3:\nsquare = i * i\nsum = sum + square\ni = i + 1"]
    C --> D["BB2"] --> E["End"]

Basic Blocks:

1. i = 1; sum = 0 (BB1)
2. while i <= x (BB2)
3. square = i * i; sum = sum + square; i = i + 1 (BB3)

B. Control Flow Graph (CFG)

A CFG represents the flow of control between basic blocks.

Example CFG for the Loop:

graph TD
    BB1["i=1; sum=0"] --> BB2["while i <= x"]
    BB2 -->|"True"| BB3["square=i*i; sum+=square; i++"]
    BB3 --> BB2
    BB2 -->|"False"| BB4["End"]

Optimization Opportunity:

• Loop-Invariant Code Motion: Move sum = 0 outside the loop if it’s initialized once.
• Strength Reduction: Replace i * i with i*i (already optimal, but in C, i*i might compile to a faster sequence than pow(i,2)).

5. Factors Affecting Code Optimization

6. Activation Records and Optimization

Optimizations can affect activation records (stack frames) by:

• Reducing the number of temporaries (saves stack space).
• Eliminating redundant parameter passing (e.g., y = x in function calls).

Example: Before/After Optimization

flowchart LR
    A["Before:\nfunc(x):\n    y = x\n    return y"] --> B["After:\nfunc(x):\n    return x"]

Activation Record Impact:

• Before: Stack frame includes x, y, and return address.
• After: Only x and return address are needed.

7. In the Real World

1. eSewa’s Transaction Processing:

   • Technique: Constant folding and copy propagation.
   • How: Pre-computes fixed fees (e.g., total = amount + tax + service_fee) and avoids redundant variable copies in high-frequency transactions.

2. Ncell’s Billing Engine:

   • Technique: Dead code elimination and strength reduction.
   • How: Skips unused tariff checks after the user’s plan is selected and replaces data_used * 2 with data_used << 1 for faster calculations.

3. Daraz Order Queue:

   • Technique: Loop-invariant code motion.
   • How: Moves the order_status = "processing" assignment outside the order-processing loop to avoid redundant writes.

4. NEPSE Stock Alerts:

   • Technique: Control flow optimization.
   • How: Simplifies nested if conditions (e.g., if (market_open && price > threshold) { alert() }) into a single branch.

8. Worked Example: Full Optimization Pass

Original Code:

x = 3
y = x
z = x + 5
if x > 0:
    t1 = x * 2
    t2 = t1 + y
else:
    t2 = 0

Step-by-Step Optimization:

1. Copy Propagation:

   • y = x → Replace y with x in t2 = t1 + y.
   • New code:

     x = 3
     z = x + 5
     if x > 0:
         t1 = x * 2
         t2 = t1 + x
     else:
         t2 = 0
     

2. Constant Folding:

   • x = 3 → Fold z = x + 5 → z = 8.
   • New code:

     x = 3
     z = 8
     if x > 0:
         t1 = x * 2
         t2 = t1 + x
     else:
         t2 = 0
     

3. Strength Reduction:

   • t1 = x * 2 → t1 = x << 1.
   • Final optimized code:

     x = 3
     z = 8
     if x > 0:
         t1 = x << 1
         t2 = t1 + x
     else:
         t2 = 0
     

Quadruple Representation After Optimization:

9. Exam Tip

1. Flow Graphs:

   • Always label basic blocks clearly (BB1, BB2, etc.).
   • Use arrows to show control flow (e.g., while loops back to the condition).
   • Example Question: Given a loop, draw the CFG and identify loop-invariant code (code that doesn’t change per iteration).

2. Optimization Steps:

   • Trace variable changes in a table (like the one above for x, y, z).
   • Show intermediate steps: Start with the original code, then apply one optimization at a time (e.g., copy propagation → constant folding).

3. Real-World Applications:

   • Link optimizations to systems you know (e.g., "How would Daraz optimize its order-processing loop?").
   • Avoid vague answers: Instead of "optimization reduces runtime," say "strength reduction replaces x * 2 with x << 1, cutting CPU cycles by 30%."

4. Common Pitfalls:

   • Aliasing: If a and b point to the same memory, a = b; b = 5 means a is also 5. Copy propagation fails here.
   • Precision: x / 2 → x >> 1 only works for integers. For floats, use x * 0.5.

5. Past Exam Patterns:

   • Construct CFGs for given code snippets (e.g., loops, conditionals).
   • Apply 2–3 optimizations to a small code block (e.g., x = y; z = x + 1 → z = y + 1).
   • Explain trade-offs: "Why isn’t dead code elimination always applied?" (Answer: May hide bugs if the code is theoretically reachable but never executed in tests.)

Final Visual Summary:

mindmap
  root((Code Optimization))
    Techniques
      Constant Folding
      Copy Propagation
      Dead Code Elimination
      Strength Reduction
    Intermediate Forms
      Three-Address Code
      Quadruples
      CFGs
    Real-World
      eSewa (Folding)
      Ncell (Strength Reduction)
      Daraz (Loop Optimization)
    Exam Focus
      CFG Construction
      Step-by-Step Optimization
      Aliasing Pitfalls