At this point in the compilation pipeline, the program has been reduced to intermediate code, a simplified, machine-independent sequence of instructions that faithfully captures everything the original source program was supposed to do. The trouble is that "faithfully captures what the program should do" and "does it as efficiently as possible" are two very different goals, and the straightforward translation process described in the previous tutorial rarely produces code that is anywhere close to optimal. Code optimization is the phase responsible for closing that gap, improving the intermediate representation so the final program runs faster, uses less memory, or consumes fewer resources, all without changing what the program actually computes.
It is worth pausing on that last phrase, since it is the single most important rule governing this entire phase. An optimization is only valid if it preserves the exact observable behavior of the original program for every possible input. A transformation that makes code faster but occasionally produces a different result is not an optimization at all; it is simply a bug. This constraint shapes everything about how optimization techniques are designed and applied throughout this tutorial.
In this tutorial, you will learn the difference between local and global optimization, several widely used optimization techniques including constant folding, dead code elimination, common subexpression elimination, and loop optimization, how a control flow graph helps organize code for optimization, and the fundamental principle that any valid optimization must never change what a program actually does.
Code optimization refers to the collection of techniques a compiler applies to intermediate code in order to improve its efficiency, typically measured in terms of execution speed, memory usage, or power consumption, while guaranteeing that the program's meaning and output remain completely unchanged. This phase operates on the intermediate representation produced by the previous phase, taking advantage of its simple, uniform structure to identify patterns of inefficiency that would be much harder to spot in the original, more complex source code.
It is important to set realistic expectations about what code optimization can achieve. No optimization technique can transform a fundamentally inefficient algorithm into an efficient one; that remains the responsibility of the programmer. What code optimization can do is remove unnecessary work, redundant computation, and wasted effort that naturally creeps in during the earlier phases of translation, particularly during the relatively mechanical, rule-based process of intermediate code generation described in the previous tutorial.
Optimization techniques are often categorized based on the scope of code they consider at once, distinguishing between optimizations applied within a small, straight-line sequence of instructions and optimizations that consider the flow of an entire function or program.
| Aspect | Local Optimization | Global Optimization |
|---|---|---|
| Scope | A single basic block, meaning a straight-line sequence of instructions with no jumps into or out of the middle of it. | An entire function or program, considering how control can flow between multiple basic blocks. |
| Complexity | Relatively simple to analyze, since there is only one possible path of execution through a basic block. | More complex, since it must account for multiple possible execution paths and how they interact. |
| Typical Techniques | Constant folding, common subexpression elimination within a block, and simple algebraic simplification. | Loop optimization, global common subexpression elimination, and dataflow analysis across multiple blocks. |
A basic block, referenced in the table above, is simply a maximal sequence of instructions that always executes together from beginning to end, with no branching into its middle and no branching out until its final instruction. Dividing intermediate code into basic blocks, and understanding how those blocks connect to one another through jumps and conditional branches, is the essential first step behind almost every optimization technique discussed in this tutorial.
Constant folding is one of the simplest and most intuitive optimization techniques. It involves evaluating expressions involving only constant values at compile time, rather than generating instructions that would recompute the same fixed result every single time the program actually runs.
Before Optimization: t1 = 4 * 5 total = t1 + price After Constant Folding: total = 20 + price
Since the values 4 and 5 are both known constants at compile time, there is no reason to generate an instruction that multiplies them together every time the program executes. The compiler can simply compute the result once, during compilation, and substitute the constant value directly into the generated code.
Dead code refers to any instruction whose result is never used anywhere in the rest of the program, meaning it can be safely removed without changing the program's observable behavior in any way. Dead code elimination is the process of identifying and removing exactly this kind of unnecessary instruction.
Before Optimization: t1 = a + b t2 = c * d total = t1 After Dead Code Elimination: t1 = a + b total = t1
In this example, the value computed and stored in t2 is never referenced anywhere afterward, which means the instruction that computes it can be removed entirely without affecting the final output of the program. Dead code often appears naturally as a side effect of other optimizations, such as constant folding or common subexpression elimination, which is why these techniques are frequently applied together, repeatedly, until no further improvements can be found.
A common subexpression is a computation that appears more than once in a piece of code, always producing the exact same result each time, because none of the values it depends on have changed between occurrences. Common subexpression elimination identifies these repeated computations and replaces every occurrence after the first with a reference to the already computed value, avoiding unnecessary repeated work.
Before Optimization: t1 = a + b t2 = a + b t3 = t1 * t2 After Common Subexpression Elimination: t1 = a + b t3 = t1 * t1
Here, the expression "a + b" is computed twice in the original code, but since neither a nor b changes between the two computations, the second computation is entirely redundant. By reusing the already computed value stored in t1, the optimized code avoids performing the same addition operation a second time, without altering the final result in any way.
Loops are often responsible for a disproportionate share of a program's total execution time, since the instructions inside a loop body may run many times over. Because of this, even small inefficiencies inside a loop can have an outsized impact on overall performance, which makes loop optimization one of the most valuable categories of optimization a compiler can perform.
Before Optimization:
for (i = 0; i < n; i = i + 1) {
t1 = x * y
array[i] = t1 + i
}
After Loop-Invariant Code Motion:
t1 = x * y
for (i = 0; i < n; i = i + 1) {
array[i] = t1 + i
}
In this example, the computation "x * y" does not depend on the loop variable i at all, meaning it produces exactly the same result on every single iteration of the loop. Since recomputing it inside the loop is pure wasted effort, loop-invariant code motion moves this computation outside the loop entirely, so it is calculated just once instead of n times, while still producing exactly the same overall behavior.
Before Optimization:
for (i = 0; i < n; i = i + 1) {
t1 = i * 4
array[t1] = 0
}
After Strength Reduction:
t1 = 0
for (i = 0; i < n; i = i + 1) {
array[t1] = 0
t1 = t1 + 4
}
Strength reduction replaces a relatively expensive operation, such as multiplication, with a cheaper equivalent, such as repeated addition, when the two produce identical results in a given context. In this example, rather than recomputing "i * 4" from scratch on every iteration, the optimized code simply adds 4 to a running total on each pass through the loop, achieving the exact same sequence of values through a less costly operation.
Many optimization techniques, particularly those operating at a global rather than local scope, rely on a structure called a control flow graph to organize and analyze the intermediate code. In a control flow graph, each node represents a basic block, and each directed edge represents a possible transfer of control from one block to another, whether through a simple fall-through to the next instruction, an unconditional jump, or one branch of a conditional jump.
Simplified Control Flow Graph Structure: Block1: (initial computation) | v Block2: (loop condition check) ----> Block4: (code after the loop) | v Block3: (loop body) | goes back up to Block2
By representing a program's structure this way, a compiler can systematically analyze how values flow between blocks, which is essential for correctly applying optimizations like loop-invariant code motion, since the compiler needs to reliably determine which computations remain constant across every iteration of a loop before it can safely move them outside that loop.
Every optimization technique discussed in this tutorial is governed by a single, non-negotiable requirement: the transformed code must produce exactly the same observable behavior as the original code, for every possible input the program might receive. This includes not just the final computed values, but also things like the exact sequence of any output the program produces and how it behaves in edge cases, such as division by zero or arithmetic overflow, depending on the guarantees a particular language makes about such situations.
This requirement is why certain tempting-looking transformations are not actually valid optimizations in every context. For instance, reordering two instructions that appear independent at first glance can sometimes change behavior if one of them has a side effect, such as writing to shared memory, that the other implicitly depends on. Compiler designers must analyze these dependencies carefully before applying any transformation, which is precisely why real optimizing compilers rely on carefully proven analysis techniques rather than simple pattern matching alone.
| Mistake | Correct Understanding |
|---|---|
| Assuming code optimization can improve a fundamentally inefficient algorithm's overall complexity. | Code optimization removes redundant or wasteful instructions within a given algorithm; it cannot transform a slow algorithm into a fundamentally faster one. |
| Believing local optimization and global optimization use the same techniques applied at different scales. | While some techniques overlap, global optimization often requires additional analysis, such as a control flow graph, to safely reason about multiple possible execution paths. |
| Applying common subexpression elimination without checking whether the shared values could have changed between occurrences. | Common subexpression elimination is only valid if none of the values involved in the repeated expression have changed between its occurrences. |
| Treating any transformation that produces faster code as automatically a valid optimization. | A transformation is only a valid optimization if it preserves the program's exact observable behavior for every possible input; otherwise, it is simply incorrect. |
Code optimization takes the intermediate representation produced during translation and improves it, removing redundant computation and unnecessary work while strictly preserving the program's original meaning. Techniques such as constant folding, dead code elimination, and common subexpression elimination operate primarily within local, straight-line blocks of code, while loop optimization and other global techniques rely on a control flow graph to safely reason about how values and control move across an entire function. Every one of these techniques is bound by the same fundamental requirement: the optimized code must behave exactly like the original for every possible input, a rule that separates genuine optimization from outright incorrect transformation.
In this tutorial, you learned what code optimization aims to achieve, the difference between local and global optimization, several widely used optimization techniques with worked examples, how a control flow graph supports global optimization, and the fundamental rule that governs whether any given transformation is actually a valid optimization. With this foundation in place, you are ready to explore code generation, the final phase where this optimized intermediate representation is translated into the actual target machine code.