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

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 |
|---|---|
| Predecessor and successor blocks |
| Facts generated and invalidated by |
| Reads before definition, and assignments in |
| Facts before and after |
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.

3. Local rewrite table: pattern, condition and result
Pass | Before -> after | When to use | Safety check |
|---|---|---|---|
Constant folding |
| Operands are constants | Preserve arithmetic, overflow and traps |
Constant propagation |
| A reaching value is known | No relevant path redefines |
Algebraic simplification |
| An identity applies | Removed evaluation has no call, trap or volatile access |
Copy propagation |
| A copy adds nothing | Values are not redefined before use |
Common subexpression elimination |
| It was computed earlier | Operands are unchanged and evaluation is pure |
Dead assignment elimination |
| Its result is not live | No side effect |
Strength reduction |
|
| Correct initialisation and numeric semantics |
Jump threading |
| 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. | Which definitions may reach here? Include all feasible predecessors. |
Available expressions | Forward, intersection. | Reuse only if every incoming path supplies it. Set |
Live variables | Backward, union. | 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.
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 t4t0=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:
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 sOutputs 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.

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 | Its value changed |
Delete a call whose return is dead | It may have a side effect |
Hoist | A path skipping |
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.
Keep learning
Intermediate Code Generation Formula Sheet: TAC, Quadruples and Backpatching Revision Notes
Revise intermediate code generation through compact formulas, representation tables and verified traces. Follow one expression from TAC to DAG reuse, then patch a Boolean branch exactly.
Intermediate Code Generation in Compiler Design: TAC, Backpatching and DAGs
Connect expressions, short-circuit control flow and local optimisation through a single worked translation, from source code to resolved TAC and a reusable DAG.
Code Optimization Mistakes in Compiler Design: How to Avoid Losing GATE Marks
A rewrite that looks familiar is not necessarily safe. Trace six common optimization errors, learn why each one changes program meaning, and use a five-step check before accepting an answer.
Code Optimization in Compiler Design: Basic Blocks, Data Flow and Worked Examples
Learn how compiler optimizers use basic blocks, control-flow graphs and data-flow facts. Two checked traces cover loop strength reduction, liveness and safe dead-code removal.





