Code optimisation and code generation notes — Unit 5

The optimization phase attempts to improve the Intermediate Code so that the final machine code executes faster and/or consumes less memory.

⇒1.1 The Golden Rule

Optimization MUST NOT change the meaning or output of the program under any circumstances.

⇒1.2 Types of Optimization

• Machine-Independent: Performed on the TAC/IR (e.g., removing unused variables).
• Machine-Dependent: Performed on the final target code, utilizing specific hardware features (e.g., specific CPU registers or specific assembly instructions).

Before optimizing, the compiler divides the TAC into structural units.

⇒2.1 Basic Blocks

A Basic Block is a sequence of consecutive instructions with exactly one entry point (at the top) and one exit point (at the bottom). There are no jump instructions inside a basic block, only at the very end.

⇒2.2 Flow Graphs

A directed graph where the nodes are Basic Blocks, and the edges represent jumps (control flow) between them. This graph is the foundation for analyzing loops and reachability.

These optimizations are performed inside a single Basic Block.

• Constant Folding: Evaluating expressions at compile time. Translating `x = 2 * 3` directly into `x = 6`.
• Constant Propagation: If `x = 5`, substituting `5` for `x` in subsequent instructions.
• Algebraic Simplification: Removing useless math. Translating `x = y * 1` into `x = y`, or `x = y + 0` into `x = y`.
• Strength Reduction: Replacing expensive operations with cheaper ones. Replacing `x = y * 2` with `x = y + y` or `x = y << 1` (bit shift).

These optimizations cross Basic Block boundaries and are heavily focused on loops, since programs spend 90% of their execution time inside loops.

• Code Motion (Loop Invariant Computation): If a calculation inside a loop yields the same result every iteration, move the calculation outside and above the loop so it only executes once.
• Dead Code Elimination: Removing code that can never be reached (e.g., code after a `return` statement), or removing variables that are calculated but never used.
• Common Subexpression Elimination: If `a = b + c` is computed, and later `d = b + c` is computed (and b/c haven't changed), just reuse the first result.

The final phase of the compiler. It maps the optimized Intermediate Code into the target machine language (Assembly or Machine Code).

⇒5.1 Key Challenges

• Instruction Selection: Choosing the appropriate assembly instructions. (e.g., Should we use an `ADD` instruction, or a specialized `INC` instruction?)
• Register Allocation: Memory access is slow; CPU registers are fast. The compiler must decide which variables get to live in the limited number of CPU registers.
• Instruction Scheduling: Reordering instructions to keep the CPU pipeline full and avoid stalling while waiting for memory fetches.

A CPU might only have 8 general-purpose registers, but a program might have 50 active variables.

⇒6.1 The Graph Coloring Algorithm

A famous solution to register allocation.

• Nodes = Variables.
• Edges = If two variables are 'live' (in use) at the exact same time, draw an edge between them.
• Colors = CPU Registers.
• Goal: Color every node using the minimum number of colors, such that no two connected nodes share the same color. If a graph requires 10 colors but the CPU only has 8 registers, the remaining 2 variables must be 'spilled' into slower RAM.

A final, machine-dependent optimization pass over the generated target code.

⇒7.1 How it works

A small, sliding window (the 'peephole') moves over the assembly instructions. It looks for specific, clumsy patterns generated by the code generator and replaces them with tighter assembly sequences.

• Redundant Loads/Stores: If the code stores Register A to Memory X, and the very next line loads Memory X back into Register A, delete the second line.
• Unreachable Code: Removing jumps to jumps (Jump chaining).

This represents the final polish before the object code is handed off to the Linker.