Code Optimisation & Code Generation

What is Code Optimisation?

Analogy: Writing a first draft of an essay (intermediate code) and then editing it to be shorter and more impactful without changing the meaning (optimisation). The edited version says the same thing but better.

Key constraint: Optimisation must NEVER change the output of the program!

---

Optimisation Levels

Machine-independent (on Intermediate Representation):
  Applied before knowing the target CPU.
  Works on abstract TAC or similar IR.

  Examples: constant folding, CSE, dead code elimination, loop optimisations

Machine-dependent (after code selection):
  Applied to target-specific instructions.
  Knows register count, instruction latencies, etc.

  Examples: peephole, register allocation, instruction scheduling

---

Constant Folding — Compute at Compile Time

If an expression involves only constants, evaluate it now — no need to compute at runtime.

Before:            After:
  x = 3 * 4 + 1    →    x = 13
  y = 2 ** 10      →    y = 1024
  if (5 > 3) ...   →    always true → can eliminate the if

---

Constant Propagation — Substitute Known Values

If a variable always holds a known constant at some point, replace uses with the constant.

Before:
  x = 5          ← x is always 5 here
  y = x + 3      ← substitute: y = 5 + 3
  z = y * 2      ← after folding: y = 8, so z = 8 * 2

After constant folding too:
  x = 5
  y = 8
  z = 16

Now x and y may be dead code if not used elsewhere!

---

Dead Code Elimination

Remove code whose result is never used.

Before:
  x = 5 * 6    ← x never read again → DEAD
  y = 3 + 4    ← y never read again → DEAD
  z = a + b    ← z is used → KEEP
  return z

After:
  z = a + b
  return z

How to detect: LIVE VARIABLE ANALYSIS
  A variable is LIVE at a point if its current value may be READ later.
  A variable is DEAD if its value is NEVER read after its last write.

---

Common Subexpression Elimination (CSE)

If the same expression is computed multiple times with the same operands (not modified in between), compute it once.

Before:
  t1 = a + b
  t2 = a + b    ← same expression!
  x = t1 * t2

After CSE:
  t1 = a + b
  x = t1 * t1   ← reuse t1

But ONLY valid if a and b are NOT modified between the two computations!
CSE uses value numbering or DAG to detect same expressions.

---

Loop Optimisations — The Biggest Wins

Loops execute many times — even small improvements compound!

Loop-Invariant Code Motion (LICM)

Move code OUT of loop if it produces the same result every iteration.

Before:
  for i in range(1000):
      limit = n * n      ← n does not change in loop → INVARIANT
      if i < limit:
          A[i] = A[i] + 1

After LICM:
  limit = n * n          ← moved OUTSIDE the loop
  for i in range(1000):
      if i < limit:
          A[i] = A[i] + 1

Saves: 1000 multiplications → 1 multiplication

Strength Reduction — Replace Expensive with Cheap

Before:
  for i in range(n):
      j = i * 4    ← multiplication every iteration

After strength reduction:
  j = 0
  for i in range(n):
      // use j
      j = j + 4   ← addition (much cheaper than multiplication)

Multiplications → Additions: replace j = i*4 with j += 4

Loop Unrolling — Reduce Loop Overhead

Before (100 iterations, checking i<100 each time):
  for i in range(0, 100, 1):
      A[i] = B[i] + 1

After unrolling by 4 (25 iterations, check 25 times):
  for i in range(0, 100, 4):
      A[i]   = B[i]   + 1
      A[i+1] = B[i+1] + 1
      A[i+2] = B[i+2] + 1
      A[i+3] = B[i+3] + 1

Saves: 75 branch instructions and loop counter updates
Enables: more instruction-level parallelism

---

Peephole Optimisation — Local Cleanup

Slide a small window over the generated code and replace patterns with equivalents.

Pattern → Replacement:

ADD R1, #0        → (remove: adding 0 does nothing)
MUL R1, #1        → (remove: multiply by 1 does nothing)
MOV R1, R2        →
MOV R2, R1        → keep only first MOV (second is redundant copy-back)
JMP L             →
L:   ...          → (remove JMP: already at L!)
x = x + 1        →
y = x + 1        → x = x + 1; y = x  (avoid recomputing x+1)
SHL R1, 1         ← replace MUL R1, #2 (shift is faster than multiply)

---

Register Allocation — Graph Colouring

Problem: IR has unlimited temporaries; hardware has ~16-32 registers
         Variables that cannot fit in registers must be "spilled" to memory

Solution: Build INTERFERENCE GRAPH
  Nodes = variables (temporaries)
  Edge between X and Y if both are LIVE at the same time (cannot share register)

k-register allocation = k-colouring of this graph
  If graph is k-colourable: every variable gets a register
  If not: spill some variables (store/load from memory)

Graph k-colouring is NP-complete → practical heuristics used
  Chaitin's algorithm: iteratively remove nodes with degree < k

---

Quick Check

Q1. Apply constant folding and propagation to: x=2; y=x*3; z=y+1; print(z)

x = 2 (constant)
y = x*3 = 2*3 = 6 (propagate x, fold multiply)
z = y+1 = 6+1 = 7 (propagate y, fold add)
print(7) (propagate z)

After dead code elimination: x, y, z never read after last assignment
Optimised: print(7)

Q2. What is the condition for loop-invariant code motion to be safe? Answer: The computation must: (1) not depend on any variable that changes in the loop, (2) produce the same result every iteration, (3) be safe to execute (no exceptions) — or guaranteed to execute in the loop (to avoid changing program behaviour for loops that execute zero times).

Q3. How does peephole differ from other optimisations? Answer: Peephole is LOCAL (looks at a small window of 2-5 instructions) and MACHINE-DEPENDENT (knows target instructions). Other optimisations like CSE, LICM work on abstract IR and are machine-independent.