Code Optimization Formula Sheet for Compiler Design: Rules, Equations and Worked TAC

Revise code optimization as pattern, condition, rewrite and sanity check. Use compact equations, legality tests and one exact TAC transformation.

KnowledgeGate Team

Exam prep & CS education

Updated 7 Nov 20266 min read
Code Optimization Formula Sheet for Compiler Design: Rules, Equations and Worked TAC

Common subexpression elimination, liveness and loop-invariant code motion all turn on four checks: pattern -> condition -> rewrite -> sanity check. Apply those checks to blocks, data-flow equations, safe rewrites, loop arithmetic and a TAC trace. Assume ordinary exam-style three-address code unless machine behaviour, aliasing, overflow or floating-point semantics are specified. Pair with Compiler Design learning module.

1. The optimization contract and notation to write first

An optimization may change instructions, layout or names, but must preserve observable behaviour for every input. Local optimization stays within one block, global crosses a CFG, loop studies repeated paths, and peephole examines a short target-code window.

Notation

Meaning

pred(B), succ(B)

Predecessor and successor blocks

GEN[B], KILL[B]

Facts generated and invalidated by B

USE[B], DEF[B]

Reads before definition, and assignments in B

IN[B], OUT[B]

Facts before and after B

A fixed point means another pass changes no set. One TAC operator per statement exposes definitions, uses and repeated expressions. Full TAC, quadruple, triple and DAG representation is a separate study step; the worked loop below uses TAC to apply optimization rules.

2. Basic blocks, CFG, dominance and natural-loop rules

The first instruction is a leader. Every jump target is a leader. Every instruction immediately after a conditional or unconditional jump is also a leader when it exists. A block starts at a leader and ends before the next one. Add CFG edges for jumps and fall-through.

d dom n means every entry-to-n path passes through d. An edge n -> h is a back edge only when h dominates n. Its natural loop contains h, n, and nodes reaching n without passing through h. A preheader before the header supports safe hoisting.

For 1: i=0; 2: L1: if i>=4 goto L2; 3: x=x+i; 4: i=i+1; 5: goto L1; 6: L2: return x, leaders are 1, 2, 3 and 6. Blocks are B1={1}, B2={2}, B3={3,4,5}, B4={6}. Edges are B1->B2, B2->B3, B2->B4, B3->B2. The last is a back edge with natural loop {B2,B3}. For a fuller derivation of leaders, CFGs and natural loops, see Basic Block Optimization: Leaders, CFGs and Loop Methods; the pre-pass rules needed for optimization are leaders, CFG edges, dominance, and natural-loop membership.

Control-flow diagram of a natural loop: preheader B1 enters header B2, which branches to B3 or return B4; B3 loops back to B2, with states ending at return 16.

3. Local rewrite table: pattern, condition and result

Pass

Before -> after

When to use

Safety check

Constant folding

3*7 -> 21

Operands are constants

Preserve arithmetic, overflow and traps

Constant propagation

p=21; q=p+1 -> q=22

A reaching value is known

No relevant path redefines p

Algebraic simplification

x+0 -> x; x*1 -> x

An identity applies

Removed evaluation has no call, trap or volatile access

Copy propagation

u=v; w=u+2 -> w=v+2

A copy adds nothing

Values are not redefined before use

Common subexpression elimination

t1=a+b; t2=a+b -> t2=t1

It was computed earlier

Operands are unchanged and evaluation is pure

Dead assignment elimination

dead=21 -> remove

Its result is not live

No side effect

Strength reduction

offset=i*8 -> offset=0; offset=offset+8

i starts at 0 and rises by 1

Correct initialisation and numeric semantics

Jump threading

goto L1; L1: goto L2 -> goto L2

One jump leads to another

Preserve reachability

Cue: simplify and propagate, remove newly dead work, then rebuild analysis. It is not a rigid order. Continue until the required fixed point.

4. Data-flow equation sheet and meet operators

Analysis

Direction, meet and equations

Use cue and safety condition

Reaching definitions

Forward, union. IN[B] = union over P in pred(B) of OUT[P]; OUT[B] = GEN[B] union (IN[B] - KILL[B])

Which definitions may reach here? Include all feasible predecessors.

Available expressions

Forward, intersection. IN[B] = intersection over P in pred(B) of OUT[P]; OUT[B] = GEN[B] union (IN[B] - KILL[B])

Reuse only if every incoming path supplies it. Set IN[entry] to empty.

Live variables

Backward, union. OUT[B] = union over S in succ(B) of IN[S]; IN[B] = USE[B] union (OUT[B] - DEF[B])

Can a value be read later? Delete only side-effect-free stores.

USE[B] means reads before definition in B, not every mentioned variable. For 1: t=a+b, 2: u=t*2, 3: t=0, 4: return u, work backwards. Sets before lines 4, 3, 2 and 1 are {u}, {u}, {t} and {a,b}. Line 3 is dead. With a=3, b=5, both versions return u=(3+5)*2=16. For a fixed-point liveness walkthrough, use Liveness in Compiler Design: IN, OUT, USE and DEF; here liveness appears as the equation and a compact dead-assignment trace.

5. Loop optimization formulas and legality checks

Loop-invariant code motion: move t=f(a,b) to the preheader only if a and b are invariant, the definition reaches every intended use, and movement adds no side effect or exception to a skipped path. Use it for unchanged work.

Strength reduction: if basic induction variable i=i+c drives j=a*i+b, each step changes j by a*c. After correct initialisation, use j=j+a*c. For i starting at 0 and rising by 1, 8*i gives 0,8,16,24; use offset=0, then offset=offset+8. Preserve initial values and numeric semantics.

Loop unrolling: for trip count N and factor u, use q=floor(N/u) groups and r=N mod u cleanup iterations. With N=10, u=4, run 2 groups of 4 plus 2 cleanup iterations. Apply only when the supplied cost model supports it. Code growth, register pressure, branches and target instructions may cancel any benefit.

6. Fully worked TAC optimization with exact values

Assume a=10, b=5, bound 4, loop-invariant a and b, no aliasing through out, and ordinary integer TAC.

Code
t0=3*7
i=0
L1:
t1=a+b
t2=i*8
t3=t1+t2
out[i]=t3
i=i+1
if i<4 goto L1
t4=a+b
return t4

t0=21 is unused. For i=0,1,2,3, t1 stays 15, t2 is 0,8,16,24, and t3 is 15,23,31,39. Thus out=[15,23,31,39] and return is 15.

This IR performs 1 dead multiplication, 4 loop multiplications, 12 loop additions, and 1 post-loop addition: 5 multiplications and 13 additions.

Fold 3*7 and remove it, hoist a+b as s, replace i*8 with offset, and reuse s:

Code
s=a+b
i=0
offset=0
L1:
t=s+offset
out[i]=t
i=i+1
offset=offset+8
if i<4 goto L1
return s

Outputs remain 15,23,31,39, and return remains 15. This form has 0 multiplications and 13 additions. It removes five IR multiplications without claiming an exact wall-clock speedup.

Two-column TAC comparison shows constant folding, LICM, CSE and strength reduction; both versions output 15, 23, 31, 39 and return 15, with multiplications reduced from five to zero.

7. How exam-style questions test the sheet, plus safety traps

Typical tasks cover blocks, CFG edges, back edges, loops, IN and OUT, meet selection, dead work, availability, invariants and TAC outputs.

Tempting rewrite

Why unsafe

Reuse a+b after a changes

Its value changed

Delete a call whose return is dead

It may have a side effect

Hoist 10/x above a condition

A path skipping x=0 may now trap

Move a load across a possibly aliasing store

The store may change that location

Reassociate floating-point arithmetic

It is not exact algebra

Equate unreachable code with a dead assignment

Control flow differs from an unused value

Treat fewer IR operators as guaranteed faster

Target instructions and costs decide performance

For a complete CFG, liveness and legality treatment, use Code Optimization in Compiler Design: Complete Guide with Worked Examples; then use a compact formula card and one TAC optimization trace for rapid revision.

8. The 60-second revision order and next step

Form blocks and CFG; mark analysis direction; choose union for may facts or intersection for must facts; iterate to a fixed point; check legality before rewriting; apply fold -> propagate -> reuse -> eliminate; verify outputs and control flow; compare only the supplied cost measure.

Self-check: a=10, b=5, bound 4 must give out=[15,23,31,39] and return 15. Use the Compiler Design course for full teaching. When you can derive the equations and trace TAC unaided, move to timed practice.