Q5Compiler Design

Code Optimization is a highly aggressive, mathematically intensive phase of the compiler. Its absolute singular objective is to ruthlessly transform the Intermediate Representation (IR) of the program to drastically reduce execution time (CPU cycles) and minimize physical memory footprint (RAM), all without altering the mathematical logic or output of the original source code. Optimization algorithms are architecturally split into two massive categories: Machine-Independent Optimization (which operates on the abstract intermediate code) and Machine-Dependent Optimization (which utilizes specific CPU hardware features like registers and cache).

To execute Machine-Independent optimizations, the compiler violently shatters the continuous intermediate code into isolated atomic sequences called Basic Blocks, and mathematically maps their execution paths using a Control Flow Graph (CFG). Optimizations are then applied either "Locally" (inside a single Basic Block) or "Globally" (across the entire CFG).

1. Local Optimization Techniques

These algorithms aggressively target the code within the strict confines of a single Basic Block.

• A. Constant Folding: The compiler mathematically evaluates constant expressions at compile-time instead of runtime. If the code contains x = 22 * 7 / 2;, the compiler calculates this value during compilation and violently replaces the entire expression with the physical result x = 77;. This saves the CPU from executing useless math operations during runtime.
• B. Constant Propagation: If a variable is aggressively assigned a constant value (e.g., pi = 3.14), and then used in a subsequent expression (area = pi * r * r), the compiler will mathematically substitute the constant directly into the expression (area = 3.14 * r * r), freeing up a memory lookup.
• C. Common Subexpression Elimination: If the compiler detects that the exact same mathematical operation is executed multiple times within a block without the variables changing (e.g., a = b * c followed by d = b * c + 5), it will calculate b * c exactly once, store it in a temporary register, and reuse the result, slashing CPU cycle waste.
• D. Dead-Code Elimination: The compiler utilizes data-flow analysis to mathematically prove that a specific variable or block of code can absolutely never be reached or used (e.g., code following a return statement, or a variable that is assigned but never read). The compiler ruthlessly deletes this code from the binary.

2. Loop Optimization Techniques (Global)

Because loops (like for and while) are executed continuously, they consume the massive majority of a program's CPU time. Loop optimization yields the highest performance gains in compiler architecture.

• A. Code Motion (Loop Invariant Computation): If a mathematical expression inside a loop produces the exact same result during every single iteration (e.g., while (i < n) { x = y + z; i++; } where y and z do not change), the compiler forcefully rips the expression x = y + z; out of the loop and places it physically before the loop begins. This prevents the CPU from re-calculating the identical equation thousands of times.
• B. Induction Variable Elimination: In a for(i=0; i<10; i++) loop, the variable i is an induction variable. If the loop contains j = 4 * i, j is a derived induction variable. The compiler can mathematically replace the expensive multiplication operation (4 * i) with a highly efficient addition operation (j = j + 4), drastically increasing execution speed on primitive CPUs.
• C. Loop Unrolling: To eliminate the continuous overhead of evaluating the loop condition (e.g., i < n) and jumping back to the top of the loop, the compiler will physically duplicate the inner code of the loop multiple times. For a loop running 4 times, it will just write the code out 4 times in a row, completely destroying the loop structure but resulting in blisteringly fast straight-line execution.