Optimization — Constant Folding & Dead Code

A compiler that only translates source to bytecode leaves obvious wins on the table. Optimization passes are transformations over the IR (intermediate representation) that produce semantically-equivalent but cheaper code. They typically run after parsing/type-checking and before final code generation, and can be composed as a pipeline: each pass takes a tree, rewrites it, and hands it to the next pass.

Constant folding

If both operands of an arithmetic expression are known at compile time, there's no reason to compute the result at runtime:

1 + 2        →  3
(2 * 3) + 4  →  10

Implement this as a bottom-up tree rewrite: recursively fold the children first, then check if the current node is a binary op whose both children are now literal numbers. If so, replace the whole node with the computed literal. Because folding is bottom-up, (1 + 2) * (3 + 4) folds inside-out: (1+2) becomes 3, (3+4) becomes 7, and finally 3 * 7 folds to 21 — a single pass handles arbitrarily nested constant subexpressions as long as the recursion visits children before parents.

Watch the edge cases:

• Division/modulo by a folded zero — x / (2 - 2) must not fold to a divide-by-zero at compile time; leave it unfolded (or emit a compile error) rather than crashing the compiler.
• Type-sensitive folding — folding 1 + 2 to 3 is only valid if + means numeric addition for those operand types; don't fold across types you haven't modeled (e.g., string concatenation vs. numeric add) unless the fold logic accounts for it.
• Overflow — some languages require folded results to respect the same integer width/overflow rules as runtime arithmetic, so the optimized and unoptimized programs behave identically.

Dead code elimination

Any statement that appears after an unconditional return in the same block can never execute — it's dead:

fun f() {
  return 42;
  print("never runs");   // dead
}

The transformation is straightforward: walk a block's statement list, and once you hit a return, drop every statement that follows it in that block. This has to be scoped correctly — a return inside one branch of an if doesn't make code after the whole if dead, only code after the return within that same branch's block.

Strength reduction

Replace an expensive operation with a cheaper, equivalent one. A classic example: multiplying by a small constant can be replaced by repeated addition, e.g. x * 2 → x + x. On many architectures addition is cheaper than multiplication, so this trades instruction type for the same instruction count (or fewer, once combined with further folding). Note the guard: only rewrite when the other operand is a runtime value — if both operands are already constants, constant folding should handle it directly instead (2 * 3 should fold to 6, not become 3 + 3).

Measuring the win

A good way to see optimizations "work" is to compare the instruction count of the naive compiled output against the optimized output for the same source — folding and dead-code elimination should strictly shrink (or hold steady) the emitted instruction count, never grow it. Your exercise wires these three passes together over a small expression-tree IR and reports the before/after instruction counts so you can verify the optimizer is actually doing something.