Classic Optimizations

Optimization involves two independent questions: whether a transformation is legal, and whether legal transformations are worthwhile. Fewer instructions, fewer calls, or less source code do not automatically answer these questions. Correctness depends on the semantics of the source language and IR, while benefits depend on the target and workload.

These optimizations are not limited to SSA form, nor do they all have uniform linear complexity. SSA provides conveniences such as explicit def-use chains, but practical algorithms also involve control flow, aliasing, cost models, and compilation time budgets.

Constant Folding and Propagation

Folding computes the value of known expressions at compile time, e.g., integer 2+3 yields 5; propagation carries known constants to their use sites, thereby triggering further folding. SCCP also tracks executable control-flow edges simultaneously, using constant conditions to exclude impossible branches.

x*0→0 is an algebraic simplification, not a fold where all operands are constants. Its legality depends on semantics: in IEEE floating-point, NaNs, infinities, and signed zeros can break certain real-number algebraic identities; if x comes from an expression with side effects, deleting its evaluation also requires proof. LLVM IR's poison, undef, and related flags have independent rules. LLVM UB Manual

A unique static definition in SSA does not guarantee the value is a constant; φ-nodes and loops still require analysis. Conditional propagation does not mean that eliminated branches never require syntax or type checking at the language frontend.

CSE and GVN: Finding Reusable Values

If two instances of b+c have consistent operation semantics, operands, and visible state, the second may reuse the result of the first. The existing value must be available on the path where it is needed; a value computed only in the left branch of an if cannot directly replace a computation in the right branch.

GVN uses value numbering to identify equivalences, which can be stronger than literal expression matching. When handling loads, one must also prove that no potentially aliasing stores or calls during the interval have modified memory. Two instructions with identical text are not replaceable values if they read different states.

Reuse may also extend the live range of certain results, increasing register pressure; therefore, legal CSE does not guarantee speedup in all cases.

Identical loads separated by a potentially aliasing store

The source code for both reads below is *p, but q may point to the same object. If p=q and the initial value is 3, the first read gets 3, and after writing 7, the second read gets 7, resulting in 10; directly reusing the first read would incorrectly calculate 6.

/* alias.c */
static int original(int *p, int *q) {
    int before = *p;
    *q = 7;
    return before + *p;
}
static int wrong_reuse(int *p, int *q) {
    int before = *p;
    *q = 7;
    return before + before;
}
int main(void) {
    int a = 3, b = 3;
    if (original(&a, &a) != 10) return 1;
    if (wrong_reuse(&b, &b) != 6) return 2;
    a = 3; b = 0;
    if (original(&a, &b) != 6 || b != 7) return 3;
    return 0;
}

This counterexample does not violate aliasing conventions; both pointer relationships are valid inputs for the function. If the interface additionally uses promises like restrict, the optimizer may leverage stronger facts, but callers must also satisfy the corresponding rules; one cannot arbitrarily add promises to a function and then continue treating previously allowed aliasing calls as equivalent.

Do identical loads observe the same memory state?

The transformation needs evidence that the store cannot affect the load, not accidental numeric agreement. With q=A and stored value3, both results are6, yet aliasing remains. Change it to7 and the counterexample appears. With q pointing to independent B, the store cannot change A in this model.

DCE and DSE: Unused Results Do Not Mean Behaviors Are Deletable

When pure computation results have no users, they can be recursively deleted; their operand definitions may also become dead code. Side effects, exceptions, synchronization, and control-flow semantics must be preserved or separately proven.

Stores cannot be deleted simply because they have no SSA users; however, if they are completely overwritten later with no observations in between, DSE can remove the dead store. Function calls are not always undeletable: if known effects, termination, and exception properties allow it, calls with unused results may be eliminated. Conversely, "looks like just a memory read" does not automatically imply deletability.

Inlining: Exposing Context, Not Just Removing Calls

Introducing the called function body at the call site allows constant parameters, aliasing relationships, and control-flow conditions to participate in subsequent optimizations. Costs include code bloat, compilation effort, instruction cache pressure, and register pressure.

Functions called only once may be good candidates for inlining, but whether the original definition can be deleted depends on exports, address escaping, etc. Recursion also requires limits on expansion. Practical decisions are made per call site combined with cost models, rather than "always inline all small functions."

LICM: Separating Proof of Invariance from Safe Early Execution

The operands of a loop invariant do not change across loop iterations, and the relevant memory cannot be modified by writes within the loop. However, moving it to the preheader also changes the execution condition: the loop might execute zero times, and the original instruction might be located within a conditional branch.

Legal hoisting requires proving that the instruction can be safely speculatively executed, or proving via necessary execution conditions and other constraints that early execution does not change behavior. Loads must consider address validity and aliasing, division must consider exception semantics, and calls must consider effects. "No side effects plus invariant operands" does not fully cover all constraints.

After hoisting, the values needed by the original users must still be preserved. Deleting the original assignment directly without connecting subsequent uses is an incorrect teaching transformation.

Verifying Zero-Trip Loops with Explicit Exception Semantics, Then Adding Execution Guards

To avoid relying on C's undefined behavior for division by zero, the following constructs a teaching model using Python's integer division and exception semantics. We only consider non-negative loop counts; the original and hoisted-with-guard versions should produce identical results and exceptions. The unguarded version raises an extra error when n=0 and d=0, constituting a counterexample.

def original(n, d):
    total = 0
    for _ in range(n):
        total += 10 // d
    return total


def hoisted(n, d):
    if n == 0:
        return 0
    value = 10 // d
    total = 0
    for _ in range(n):
        total += value
    return total


def wrong(n, d):
    value = 10 // d
    return sum(value for _ in range(n))


def outcome(fn, n, d):
    try:
        return ("value", fn(n, d))
    except ZeroDivisionError:
        return ("error", "division by zero")


for n in range(5):
    for d in (-2, 0, 2, 3):
        assert outcome(original, n, d) == outcome(hoisted, n, d)
assert outcome(original, 0, 0) == ("value", 0)
assert outcome(wrong, 0, 0) == ("error", "division by zero")

The guard's effectiveness also depends on the specific structure of this example: division is a pure computation that must occur every time the loop body is entered, d remains unchanged, and there are no prior effects that must happen first. If the division were hidden in another conditional branch inside the loop, proving only n>0 would still be insufficient for hoisting; if other operations might raise exceptions first, the language-required order of exceptions must still be preserved. This fix cannot be generalized into a universal template for arbitrary LICM.

Why are invariant operands not enough for hoisting?

Separate results, exceptions and division attempts to judge legality before savings. n=0,d=0 is the key counterexample: the original never divides, while unguarded hoisting throws early. The guarded form restores the condition in this restricted loop. Counts are division attempts, not total instructions or measured time.

Loop Unrolling: Trading Code Size for Control and Parallelism Opportunities

Partial unrolling copies several iteration bodies and handles the remaining iterations; complete unrolling requires determinable finite iterations or corresponding specialization conditions. Unknown iteration counts can also undergo partial unrolling with tail handling.

Unrolling may reduce back-edge overhead, expose instruction-level parallelism, or help vectorization, but it may also increase code volume and spills. There is no rule that all LLVM targets unroll by two to four times; consecutive scalar loads do not automatically become legal SIMD loads: bounds, alignment, dependencies, and target capabilities still need checking.

SROA and mem2reg: Making Local Memory States Easier to Analyze

If a local aggregate object does not escape in address and its accesses are understandable, it can be split according to usage intervals, reducing unnecessary aggregate memory operations. Suitable local slots can also be promoted to SSA values, with φ-nodes expressing merges at control-flow join points.

SROA does not mechanically have to be "one field corresponds to one variable"; some usages hinder splitting, while some implementations can perform promotion directly. mem2reg can also handle alloca that are already scalars, without requiring all scenarios to pass through SROA first. LLVM Pass Documentation

Pass Order: Opportunities and Invalidations Arise Together

Inlining exposes constants, constant propagation eliminates branches, and branch elimination renders more code useless; unrolling changes loop structure, and subsequent cleanup simplifies expressions. Repeating certain transformations can be valuable, but compilers do not infinitely pursue saturation; they must also control time, size, and analysis invalidation.

After modifying the CFG, the dominator tree, loop information, or memory analysis may no longer be valid. Transformations must correctly maintain or declare invalidation of related analyses; they cannot just make the output IR look superficially legal.

Verification and Quick Reference

You can combine IR verification, counterexample testing, diffs before and after transformation, and equivalence verification within specific ranges. Tests should include boundary paths, not just ensure identical output for one normal input. To measure performance, observe the target code after the complete optimization pipeline.

References

• LLVM Analysis and Transform Passes.
• LLVM IR Undefined Behavior.

Keywords: optimization, constant propagation, SCCP, CSE, GVN, DCE, DSE, inlining, LICM, unrolling, SROA, mem2reg