Questions: Value Numbering and Redundancy Elimination

Question 1

A basic block contains: `t1 = a + b`, then `a = 5`, then `t2 = a + b`. Will local value numbering mark t2 as redundant and replace it with a copy of t1?

• A. Yes — t2 and t1 both compute a + b, so they receive the same value number and t2 is eliminated.
• B. No — the assignment `a = 5` gives `a` a new value number, so the (operator, VN(a), VN(b)) key for t2 differs from t1's key, and t2 is not redundant.
• C. Yes — but only after a dataflow analysis pass confirms that `a` holds the same value at both points.
• D. No — value numbering only works for multiplications and divisions, not additions.

Answer: (B)

This scenario is the canonical test of value numbering understanding. When `a = 5` is processed, `a` receives a new value number representing the constant 5 — different from the value number it held when t1 was computed. So when the algorithm reaches t2 = a + b, it forms the key (ADD, new-VN-of-a, VN-of-b), which is a different key from t1's (ADD, old-VN-of-a, VN-of-b). The table lookup fails to find a match, and t2 is correctly not eliminated. A common mistake is thinking value numbering tracks variable names syntactically; it actually tracks semantic values, and any reassignment creates a fresh value number.

Question 2

Which of the following optimizations is performed automatically by value numbering without requiring a separate analysis pass?

• A. Loop unrolling — value numbering detects loop bounds and duplicates loop bodies.
• B. Dead code elimination — value numbering marks unreachable instructions as unused.
• C. Constant folding — expressions like `3 + 4` receive the value number for the constant 7, and future uses are replaced by 7.
• D. Register allocation — value numbering assigns registers based on value lifetimes.

Answer: (C)

Constants receive value numbers just like computed expressions. When the algorithm encounters `3 + 4`, it looks up value numbers for the operands (constants 3 and 4), forms the key (ADD, VN(3), VN(4)), and evaluates the result: the value number is simply assigned to represent the constant 7. Any later expression that computes 3 + 4 gets the same value number and is replaced with 7. Constant folding thus falls out as a free byproduct of the value numbering machinery, with no additional analysis needed.

Question 3

Local value numbering can detect that `t3 = a + b` is redundant — even though it uses different variable names from an earlier `t1 = a + b` — as long as `a` and `b` have not been reassigned in between.

• T. True
• F. False

Answer: True

This is the fundamental advantage of value numbering over purely syntactic methods. Value numbering tracks the abstract value computed by each expression, not the textual identity of variable names. If `a` and `b` have not been reassigned between t1 and t3, they hold the same values (same value numbers), so the same key (ADD, VN(a), VN(b)) appears in the hash table twice, and the second computation is correctly identified as redundant. The algorithm replaces t3 with a copy of t1 without needing to know or care that both instructions 'look like' the same text.

Question 4

Value numbering identifies redundant computations by comparing the text of instructions — two computations with different variable names but equal results are seldom detected as equivalent.

• T. True
• F. False

Answer: False

Value numbering explicitly avoids textual comparison. It maps each variable to an abstract value number based on what computation produced it, not what the variable is named. Two variables with the same value number represent the same computed value, regardless of their names. This is what makes value numbering more powerful than naive syntactic redundancy elimination: it can detect that `t3 = x + y` is the same as `t1 = a + b` if x and a hold the same value number and y and b hold the same value number — which happens when they were both assigned the same prior computations.

Question 5

Explain how value numbering's hash table approach lets a compiler detect that an expression is redundant in a single forward pass, without re-examining prior instructions.

Model answer: The hash table maps (operator, value-number-of-left-operand, value-number-of-right-operand) to value numbers. As the algorithm processes each instruction, it looks up the operands' current value numbers, forms this triple as a key, and checks the table. If the key is present, the expression was computed before — it's redundant and can be replaced with a copy. If the key is absent, a fresh value number is assigned and stored. The table accumulates all previously seen value computations, so each new instruction only requires a single O(1) lookup to determine if it's redundant. No backward scanning is needed because the hash table is the accumulated memory of all prior computations.

The power of the hash table is that it provides constant-time lookup regardless of how many prior instructions exist. Instead of scanning backward through the instruction stream to find a matching computation, the algorithm simply hashes the current expression's semantics and checks if that hash key already exists. The key insight is that the value number of each operand already encodes everything relevant about what that variable holds — so looking up (operator, VN(op1), VN(op2)) is equivalent to asking 'has this exact computation been done before with these exact input values?' The answer is available in O(1) from the table.