Local optimization: constant folding, algebraic simplification, strength reduction, copy propagation, dead-code elimination, local CSE with the block DAG, peephole optimization

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

• Which feature of a language forces heap allocation? from Lesson 5.5
• Under static scoping, where does a procedure find a non-local name? from Lesson 5.3
• How many nodes does the DAG of the block a = b + c; b = a − d; c = b + c; d = a − d have? from Lesson 4.1

1 · The Story

📖

Tidying a chapter

Ishaan in the Optimization Room receives Dev’s draft chapter by chapter. Inside one chapter, read straight through, he applies small habits:

• “the price times 1” is just the price; “plus zero” disappears;
• “4 times 2” is written as 8 once, instead of being worked out every evening;
• “double the amount” becomes “add the amount to itself”, which the printers do faster;
• “let total be the sum; let answer be total”: he just uses the sum where answer was used;
• a phrase already worked out earlier in the chapter is reused, not recomputed;
• a sentence whose result nobody reads later is struck out.

Finally, he slides a small window over the printed lines and fixes silly pairs, like “store the figure, then immediately load the same figure”.

2 · Predict First

🤔

After x = 4; y = x * 2; z = y + 0; t = b * 1; u = t + z; w = u, if only u is needed after the block, how many instructions remain? Write your guess down. The answer is in the vault.

3 · Core Concept

Constant folding

Evaluate operations whose operands are all constants at compile time: y = 4 * 2 becomes y = 8. Combined with copies of constants (x = 4 followed by y = x * 2), folding spreads through a block.

Algebraic simplification

Use identities: x + 0 = x, x − 0 = x, x * 1 = x, x / 1 = x, x * 0 = 0. (Care with floating point, side effects and division by zero.)

Strength reduction

Replace an expensive operation by a cheaper equivalent: x * 2 → x + x or x << 1; x² → x * x; x / 4 → x >> 2 for unsigned x. In loops this becomes much more powerful (Lesson 6.6).

Copy propagation

After a copy x = y, replace later uses of x by y (as long as neither changes). The copy often becomes useless and can then be removed.

Dead-code elimination

An assignment whose target is not used later (in this block or after it) can be deleted, if it has no side effects. Deciding “used after the block” needs information about other blocks (Lesson 6.4); inside a block, the optimizer is told which variables are needed after it.

Local common subexpressions with the block DAG

Build the DAG of the block (Lesson 4.1): value numbering finds repeated computations with the same operands. Then generate code from the DAG: one instruction per operator node needed by a variable used after the block, plus copies where several needed variables label the same node. This removes local common subexpressions, folds constants, applies identities and drops dead code in one pass.

Peephole optimization (brief)

Slide a small window over the target code and replace patterns: redundant load/store pairs (ST a, R0 then LD R0, a), unreachable code after an unconditional jump, jumps to jumps (goto L1 … L1: goto L2 → goto L2), algebraic identities, and machine idioms (x = x + 1 → INC).

Story → compiler term

4 · Visual

Computed by building each block’s DAG with folding and identities, then emitting code only for values needed after the block (first two: only u, x needed; third: all four).

DAG of the second block: 4 * i is one node shared by t1 and t3.

5 · Worked Examples

Example 1 Easy

Optimize x = 4; y = x * 2; z = y + 0; t = b * 1; u = t + z; w = u; only u is needed after the block.

Solution

x = 4: copy, x now names the same value as 4; y = x * 2: constant folding gives 8; z = y + 0: constant folding gives 8; t = b * 1: algebraic identity, t = b; w = u: copy, w now names the same value as u. Result: u = b + 8. Ishaan works out 4 × 2 once, drops “times 1” and “plus 0”, and strikes everything nobody reads.

Example 2 Medium

Remove the local common subexpression: t1 = 4 * i; t2 = a + t1; t3 = 4 * i; t4 = b + t3; x = t2 + t4 (only x needed).

Solution

4 * i is computed twice with unchanged i; the DAG shares one node. Result (4 instructions instead of 5):

t1 = 4 * i
t2 = a + t1
t4 = b + t1
x = t2 + t4

Example 3 GATE

Optimize the block a = b + c; b = a − d; c = b + c; d = a − d, all four variables needed after it.

Solution

The DAG (Lesson 4.1) shows that d = a − d recomputes the value of b (same operator, same operands a and d₀). Output:

a = b + c
b = a - d
c = b + c
d = b

Note that c = b + c is not a common subexpression with a = b + c: b changed in between.

6 · Shortcuts

⚡

DAG method for a block: build the DAG with folding and identities; emit nodes only for variables needed after the block; count the emitted instructions. Valid when: questions asking for the optimized block or its instruction count.

⚡

Same text ≠ same value: an expression is a common subexpression only if none of its operands was reassigned in between. Valid when: spotting local common subexpressions.

7 · GATE Traps

⚠️

• b + c after b was reassigned is a different value.
• Dead-code elimination needs to know what is used after the block; an assignment to a variable used later is never dead.
• x * 0 = 0 is unsafe if x has side effects or may be NaN (floating point).
• Strength reduction must keep the meaning: x / 2 → x >> 1 is wrong for negative signed x.
• Peephole optimization works on target code in a small window, not on whole blocks.

8 · Memory Hook

🧠

Fold, simplify, reduce, propagate, share, delete; then peep.

9 · Connect the Dots

Everything here stayed inside one block. To reuse values across blocks or delete code that is dead globally, the optimizer needs facts that flow along the flow graph. The next lesson builds the general framework that computes such facts.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markTerms

Replacing x * 2 by x + x is:

• (A) constant folding
• (B) strength reduction
• (C) copy propagation
• (D) dead-code elimination

Q2NAT2 marksDAG optimization

Block: a = x * y; b = x * y; c = a + b; d = x * y; e = c + d; only e is needed after it. How many instructions remain after DAG-based optimization?

Numerical answer: ________

Q3MCQ2 marksOptimization

Block: p = 3; q = p * 4; r = q + s; u = s + q; v = r − u; only v is needed. The optimized code is:

• (A) v = 0
• (B) r = 12 + s; u = s + 12; v = r − u
• (C) q = 12; v = q
• (D) r = q + s; v = r − r

Q4MCQ1 markPeephole

Which is a typical peephole optimization?

• (A) choosing which variables share a register across the whole program
• (B) removing a load that immediately follows a store of the same value
• (C) building the flow graph
• (D) computing FIRST sets

Q5MSQ1 markLocal

Which can be done using only the DAG of one basic block (given which variables are needed after it)?

• (A) local common subexpression elimination
• (B) constant folding
• (C) removing assignments whose results are never used later
• (D) moving computations out of a loop

11 · Rule Card

• Constant folding: compute constant expressions at compile time.
• Algebraic simplification: x+0, x1, x0, x−0, x/1.
• Strength reduction: x2 → x+x or x1; x² → xx.
• Copy propagation: after x = y, use y.
• Dead code: assignments to variables not used later (no side effects).
• Local CSE: block DAG shares (op, operands) nodes; emit code only for needed values.
• Peephole: redundant load/store, unreachable code, jump-to-jump, idioms.

12 · Concept Ledger

local optimizationconstant foldingalgebraic simplificationstrength reductioncopy propagationdead-code eliminationcommon subexpression (local)peephole optimization

13 · Answer Vault