Global Value Numbering

In the world of computing, programs often perform the same calculation over and over. A smart compiler should recognize this redundancy and avoid redoing work. However, identifying when two seemingly different sequences of operations will produce the exact same result is a complex challenge that goes beyond simple text matching. This article delves into Global Value Numbering (GVN), a sophisticated compiler technique that formalizes this "art of seeing the same thing," not just in text, but in value. It addresses the knowledge gap between simple, localized optimizations and the need for a holistic, program-wide understanding of value equivalence across complex control flow like loops and conditional branches.

The following chapters will guide you through this powerful concept. First, in "Principles and Mechanisms," we will explore how GVN works, from its basic local form to its global power enabled by Static Single Assignment (SSA) and the $\Phi$-function, and how it uses algebraic reasoning to find hidden equivalences. Following that, "Applications and Interdisciplinary Connections" will reveal GVN's role as a foundational enabler for a host of other optimizations, demonstrating its profound impact on the performance of real-world software and its intricate interactions within the complex ecosystem of a modern compiler.

Imagine you are a master stonemason, tasked with building an arch. You have a pile of stones, and you need to cut them into precisely shaped blocks. If you need two identical blocks, would you measure and cut the first, then throw away your ruler and start from scratch for the second? Of course not! You’d use the first block as a template for the second, or at least use the same measurements. It’s faster, more efficient, and guarantees they are identical.

In the world of computing, a program often performs the same calculation over and over again. A smart compiler, like a master stonemason, should recognize this and avoid redoing work. The art of identifying when two seemingly different sequences of operations will produce the exact same result is the essence of ​​value numbering​​. It’s a journey into the heart of what it means for two things to be "the same," not just in text, but in value.

Let’s start with the simplest case. Imagine a detective who is brilliant but incredibly near-sighted. They can only see a short, straight path of instructions with no forks in the road. In compiler jargon, we call this a ​​basic block​​.

Within this tiny world, our detective is a genius. If they see the instruction u := a + b, they make a note: "The value of a + b is now stored in u." If, a moment later, they see v := a + b (and a and b haven't changed), they shout, "Aha! We've already done this!" They can simply advise the compiler to generate code for v := u instead, which is usually much faster than performing another addition. This simple trick is called ​​Local Value Numbering (LVN)​​. It operates within the confines of a single basic block, forgetting everything it knew the moment control flow branches or merges.

This is useful, but its near-sightedness is a profound limitation. What happens in a program with a simple if-else statement?

Real programs are full of choices, forks in the road represented by if-else statements, switch cases, and loops. A local detective who gets amnesia at every turn is of little help here. We need a master detective, one who has a map of the entire program—its ​​Control Flow Graph (CFG)​​—and can reason about all possible paths of execution. This is the domain of ​​Global Value Numbering (GVN)​​.

Consider this classic "diamond" pattern in a program's control flow:

A local analysis of block $B_3$ would see the computation u = a - b and, having no memory of what happened in $B_1$ or $B_2$, would dutifully perform the subtraction. But the global detective sees the whole picture! They reason that no matter which path was taken—the if branch or the else branch—the value of a - b was already computed. The computation in $B_3$ is therefore completely redundant. GVN is the technique that gives the compiler this powerful, cross-block vision. But how does it formalize this reasoning?

The secret weapon that enables GVN is a special program representation called ​​Static Single Assignment (SSA)​​ form. The idea is simple but revolutionary: every variable is assigned a value exactly once in the text of the program. If you need to "change" a variable, you create a new version of it instead. For instance, x = x + 1 becomes $x_2 := x_1 + 1$. This gives every value a unique name, making it vastly easier to track its journey through the program.

But this creates a new puzzle: what happens when paths merge? If $x_1$ was defined in the if branch and $x_2$ in the else branch, what is the value of x after the if-else statement concludes? SSA solves this with a wonderfully elegant concept: the ​​$\Phi$-function​​. At the join point, we write:

$x_3 \leftarrow \Phi(x_1, x_2)$

This is not a real instruction in the final machine code. It's a piece of notation for the compiler that means: "The value of $x_3$ is $x_1$ if we arrived from the if branch, and it is $x_2$ if we arrived from the else branch."

Now, watch the magic unfold. In our diamond example, the code in SSA form looks like this:

The GVN algorithm proceeds as follows:

1. In $B_1$, it sees t1 = a - b and gives this value a number, say Value #7.
2. In $B_2$, it sees t2 = a - b. It recognizes this is the same operation on the same inputs, so it also gets Value #7.
3. Now, in $B_3$, it analyzes t3 = Φ(t1, t2). It looks at the arguments to the $\Phi$-function and notices they both have the same value number: #7.
4. The conclusion is inescapable: no matter which path was taken, the result is Value #7. Therefore, t3 is also assigned Value #7!.
5. When it finally sees u = a - b, it computes its value number, which is of course #7, and realizes a variable (t3) holding this value is already available. The computation of u is redundant and can be replaced with t3.

The $\Phi$-function, which was invented to solve a bookkeeping problem, becomes the very tool that allows GVN to peer through the fog of control flow and unite equivalent values from different worlds.

The most beautiful aspect of GVN is that its concept of "sameness" can be much deeper than simple textual equality. A truly advanced GVN algorithm has the soul of a mathematician. It understands that the order and grouping of operations can change the text without changing the result.

Consider computing the sum of three numbers: x + y + z. You might write it as (x + y) + z. Your friend might write it as x + (y + z). A third person might write (z + x) + y. To a simple text-matching algorithm, these are all different. But a GVN armed with the laws of algebra—​​associativity​​ and ​​commutativity​​—knows they are all the same. It can ​​canonicalize​​ the expressions, perhaps by flattening the structure and sorting the operands alphabetically, to see that all three expressions boil down to the same canonical form: sum(x, y, z). This allows it to spot redundancies that are algebraically obvious but textually hidden.

This algebraic reasoning can be surprisingly powerful. The bitwise XOR operator, $\oplus$, forms a mathematical structure called a group. It has properties like associativity and, most interestingly, every element is its own inverse ($b \oplus b = 0$). A GVN that knows this can look at the expression (a ⊕ b) ⊕ b and, without even knowing the values of a and b, simplify it directly to a. It's performing abstract algebra right inside your compiler.

GVN's intelligence doesn't stop at finding redundancy. It can actively transform code into a more optimal form through pure logical deduction. Let's look at one of the most elegant transformations, which involves pushing an operation "through" a $\Phi$-function.

Imagine this scenario:

• Path 1: $x_1 \leftarrow a + b$
• Path 2: $x_2 \leftarrow a + c$
• Merge: $x \leftarrow \Phi(x_1, x_2)$
• After merge: $y \leftarrow x - a$

What is the value of y? A GVN can reason about this path by path:

• If we came down Path 1, x is $a + b$, so y is $(a + b) - a$, which simplifies to b.
• If we came down Path 2, x is $a + c$, so y is $(a + c) - a$, which simplifies to c.

So, the final value of y is b if we came from Path 1, and c if we came from Path 2. But wait! That is precisely the definition of $\Phi(b, c)$. The optimizer has deduced that the entire sequence $x \leftarrow \Phi(a+b, a+c); y \leftarrow x - a$ is semantically equivalent to the much simpler $y \leftarrow \Phi(b, c)$. This is not just removing a calculation; it's a profound restructuring of the program's logic into a cleaner, more direct form.

This journey into the pure, platonic realm of values is exhilarating, but a compiler must function in the messy real world. An optimization is only useful if it is ​​sound​​—it must not, under any circumstances, change the program's observable behavior. This means our idealistic GVN must contend with some harsh realities.

​​The Ghost of Memory:​​ What if our program uses pointers? Consider v1 := *p, followed by a store *q := 7, and then another load v2 := *p. Is v2 the same as v1? Maybe! But it depends entirely on whether the pointers p and q could possibly point to the same memory location (a problem known as ​​aliasing​​). If they might alias, a sound optimizer must be conservative. It must assume the store through q did change the value at *p, and therefore it cannot eliminate the second load. This conservatism is a necessary evil to ensure correctness. More advanced analyses, like ​​Memory SSA​​, try to give the optimizer better vision into the ghostly world of memory, but the fundamental challenge remains.

​​The Danger of Traps:​​ What about an operation like division, t := x / y? This isn't just a calculation; it's a potential landmine. If y is zero, the program will crash. Consider a program that cleverly guards the division: if (y != 0) t = x / y;. The original program will never crash. If a GVN optimizer, in its zeal to eliminate a redundant division, moves the computation to an earlier point where it's executed unconditionally, it might introduce a crash that wasn't there before. This is the cardinal sin of optimization. A sound GVN must prove that any code it moves will not introduce new exceptions or other observable side effects.

​​The Weirdness of Numbers:​​ Even our most basic assumptions about mathematics can be challenged. In the world of IEEE 754 floating-point arithmetic, there exists a strange value: ​​NaN (Not a Number)​​. In standard logic, it's a given that any value is equal to itself ($x == x$ is always true). But in IEEE 754, if x is NaN, the expression $x == x$ evaluates to false! A naive GVN that assumes reflexivity of equality might see if ($x == x$) and replace the entire conditional with true, breaking any code that correctly handles NaN. A sophisticated GVN must be aware of the specific rules of the domain it is working in. It can even use these strange rules to its advantage, deducing from if ($x != x$) that x must be NaN along that path, adding a valuable piece of information to its world model.

Global Value Numbering is far more than a simple pattern-matching tool. It is a beautiful synthesis of graph theory, algebra, and formal logic, all working in concert to reason about the very essence of a program's meaning. It's an unseen artist, quietly analyzing the flow of values, discovering hidden symmetries, and elegantly refactoring our code into something faster and more efficient. It performs these feats while bound by a strict Hippocratic Oath: "First, do no harm." The next time you compile a piece of software, take a moment to appreciate the silent, profound intelligence at work, an intelligence that finds unity and beauty in the complex tapestry of computation.

Having understood the principles of how Global Value Numbering (GVN) works, we might be tempted to see it as a neat but isolated trick—a clever bit of accounting inside a compiler. But that would be like looking at the discovery of the gear and seeing only a single toothed wheel. The true power of a fundamental idea lies not in its isolated existence, but in how it connects to everything else, how it enables new machinery, and how it changes our perspective on the entire system. GVN is precisely such an idea. It is not just one optimization among many; it is a foundational enabler, a catalyst that makes the entire optimization ecosystem more intelligent and effective.

Let's embark on a journey to see how this one idea—the "art of seeing the same thing"—radiates outward, creating synergies, solving practical problems, and revealing the beautifully complex dance of compiler optimization.

One of the most profound roles of GVN is to act as a "setup" pass. It tidies up the code, sharpens the compiler's understanding, and prepares the ground for other, more specialized optimizations to do their work. Without the "sight" provided by GVN, many of these other passes would be blind to opportunities right in front of them.

A simple, elegant example of this synergy is GVN's relationship with Copy Propagation (CP). Imagine a short sequence of code: first, we compute $x := a + b$, then we copy $y := x$, and finally, we recompute $z := a + b$. If we run Copy Propagation first, it sees no uses of $y$ to propagate, so it does nothing. A subsequent GVN pass would then spot that $z$'s computation is redundant with $x$'s and rewrite it to $z := x$`. This is an improvement, but we missed something.

Now, reverse the order. If GVN runs first, it immediately sees that $z := a + b$ is the same as the earlier computation for $x$. It transforms the code into $x := a + b; y := x; z := x$. Not only has it eliminated a redundant arithmetic operation, but it has created a new opportunity for Copy Propagation. The CP pass now has more information to work with, potentially simplifying the code even further down the line. This is a recurring theme: GVN doesn't just perform an optimization; it enriches the information available to the entire system.

This enabling power becomes truly spectacular when GVN starts to reason about program logic and algebraic identities. Consider a loop where, on different branches of an if statement, we compute $a \times b$ and $b \times a$. A mechanical optimization like Loop-Invariant Code Motion (LICM), which aims to hoist constant computations out of loops, would not see these as the same. It would leave both computations inside the loop. But a GVN pass that understands that multiplication is commutative will recognize that, no matter which path is taken, the value being computed is identical. It can unify these two computations into one, making it explicitly loop-invariant and allowing LICM to hoist it out, turning two expensive, repeated multiplications into a single one performed before the loop even starts.

This ability to simplify the program's logic has profound implications, especially in modern, object-oriented languages. A key optimization in these languages is ​​devirtualization​​, which aims to replace an indirect "virtual" function call with a faster, direct call. This is only possible if the compiler can prove the exact type of the object at the call site. Imagine code that checks an object's type ID and, if it matches type $D$, makes a virtual call. A GVN pass can analyze the flow of data and prove that the type ID is always that of type $D$, rendering the if check's condition true. This simplifies the control flow, making it obvious to the devirtualization pass that the object's type is known, thus enabling the optimization. Here, GVN acts as a detective, providing the crucial proof that unlocks a high-impact transformation.

GVN's role as an enabler extends to a whole class of powerful transformations. Partial Redundancy Elimination (PRE) is an optimization that finds computations that are redundant on some, but not all, paths leading to a point. By inserting the computation on the other paths, it can make the original computation fully redundant and eliminate it. However, a simple PRE pass often relies on pure syntactic equality. It wouldn't know that $(a + b) + c$ is the same as $a + c + b$. GVN, with its algebraic smarts, can canonicalize both expressions to the same form. After GVN runs, the "partial redundancy" becomes syntactically obvious to PRE, which can then spring into action. Similarly, Strength Reduction, which replaces expensive multiplications in loops with cheaper additions, relies on knowing which parts of the expression are loop-invariant. An early GVN and LICM pass are essential for identifying and hoisting these invariants, setting the stage for Strength Reduction to work its magic.

The true test of an optimization is its impact on real-world programs, which are dominated by loops and function calls. It is here, at a larger scale, that GVN's value truly shines.

Loops are the heart of computation. Any work a compiler can save inside a loop is magnified by the number of iterations. GVN is a cornerstone of loop optimization. By using a framework like Static Single Assignment (SSA), which gives every variable a unique definition, GVN can look at a computation inside a loop, like $u = a + b$, and see that its operands, $a$ and $b$, are actually defined outside the loop and never change within it. It can then prove that this computation is redundant with an identical one performed in the loop's preheader, effectively eliminating the work from the loop body entirely.

This isn't just an academic exercise. In a domain like image processing, a pipeline might involve applying several expensive filter kernels to millions of image tiles. Suppose two different conditional paths in the processing logic for a tile both happen to require the same expensive kernel $A(I)$. An SSA-based GVN can recognize this, ensuring that if that path is taken, the kernel is executed only once, and the result is reused. For a kernel costing 1200 cycles, on a task with 100,000 tiles where this condition is met 35% of the time, this single insight saves over 40 million machine cycles. This is a direct, measurable translation of an abstract algorithm into real-world performance.

The scope of GVN's vision can be expanded even further—across the boundaries of functions. On its own, GVN is typically an intraprocedural analysis, blind to what happens inside the functions it calls. One way to overcome this is through ​​procedure inlining​​, which replaces a function call with the body of the callee. This is like taking a sledgehammer to the walls between functions. Once the code is flattened into a single, large body, GVN can suddenly see a vast landscape of new optimization opportunities. A computation of $u \times v$ in a caller might be identical to several computations inside the now-inlined callee, allowing for massive elimination of redundancy that was previously invisible.

But there is a more subtle and often more powerful approach. Modern software engineering encourages defensive programming, such as checking if a pointer is NULL before using it. This leads to patterns where a caller validates its arguments, and then the callee validates its parameters all over again. These redundant checks can add up. An ​​interprocedural​​ GVN, combined with ​​function cloning​​, can solve this elegantly. It can see that a specific call site in function $f$ is guarded by a check a != NULL. It can then create a special, cloned version of the callee $g called $g*$ where the redundant internal NULL check is removed. It then rewrites the call in $f$ to use the optimized $g*$ while other callers, which provide no such guarantee, continue to call the original, safe $g$. This provides the best of both worlds: safety is preserved for unknown callers, while performance is gained for known, safe callers. This connects GVN directly to the creation of more robust and yet more efficient software.

Our journey might suggest that GVN is a universal good, an optimization that always improves things. The reality, as is so often the case in complex systems, is more nuanced and far more interesting. Optimization is a delicate dance of interacting forces, full of trade-offs and feedback loops.

One of the most classic trade-offs in a compiler is the tension between the number of instructions and the demand for machine registers. This is the stage for a fascinating interaction between GVN and Register Allocation (RA). By eliminating a redundant computation, GVN might also eliminate a temporary variable that held its result. This seems like a clear win. However, this act can extend the "live range" of the original variable, meaning it has to be kept in a register for longer. This longer life may cause it to interfere with more other variables, making the interference graph denser and the register allocator's job harder—potentially even forcing it to spill values to memory, which is very slow. In some cases, running GVN before register allocation can lead to a more constrained, harder-to-solve allocation problem. There is no free lunch; an improvement in one dimension can create a challenge in another.

This leads us to a final, deep truth about optimization: it is rarely a linear, one-shot process. It is an iterative search for a "fixed point." We've already seen hints of this. GVN enables devirtualization by simplifying control flow. But in other scenarios, devirtualization can enable GVN. A virtual call represents an unknown piece of code, forcing GVN to assume the worst—that the call might change any value in memory. This assumption acts as a barrier, preventing GVN from eliminating a load that appears redundant. But if a devirtualization pass can identify the specific function being called and prove it has no side effects on that memory, it removes the barrier. A second GVN pass can now see across the call and eliminate the redundant load.

This cyclic dependency—where GVN enables another pass, which in turn enables GVN again—is common. The solution is to run the optimization passes in a loop (GVN -> Devirtualization -> GVN -> ...) until no more changes occur. Even GVN itself must sometimes be run iteratively. Due to the way information propagates through a program's control-flow graph, a single pass might only uncover the first layer of equivalences. A second pass, armed with the knowledge from the first, can simplify a $\Phi$-function, which in turn allows a third pass to simplify another dependent $\Phi$-function, and so on, until the whole structure has settled into its simplest form.

This is the grand dance of a modern compiler. It is not a rigid assembly line but a dynamic, iterative process where different analyses and transformations communicate, enable, and constrain one another. Global Value Numbering is not just a single dancer in this performance; it is a choreographer, providing the vision and insight that allows the entire ensemble to achieve a state of profound and efficient simplicity.