Understanding Value Numbering and Global Value Numbering in JVM C1 Compiler Optimization

To eliminate redundant calculations, compilers merge identical operations during compilation. The C1 compiler builds a High‑level Intermediate Representation (HIR) composed of basic blocks (BB) forming a control‑flow graph, where each block contains SSA‑form instructions.

2. Value Numbering

Value numbering assigns a hash to each SSA instruction, then scans for identical instructions to merge them. Global Value Numbering extends this across multiple BBs, using the same algorithmic principles.

2.1 SSA Instruction

An example BB and its SSA instructions illustrate the concept:

B0 (SV) [0, 14] -> B1 sux: B1 pred: B5
empty stack
inlining depth 0
__bci__use__tid____instr____________________________________
. 1    0    i8     a5._12 (I) t
  4    0    i9     8
  6    0    i10    i8 + i9
  9    0    i11    18
  11   0    i12    i6 + i11
. 14   0     13    goto B1

For the statement int adder = c.t+8; three three‑address instructions are generated:

__bci__use__tid____instr____________________________________
. 1    0    i8     a5._12 (I) t
  4    0    i9     8
  6    0    i10    i8 + i9

2.2 Computing the Hash

The hash for an ArithmeticOp (e.g., i10) is derived from the substituted values of its operands (i8 and i9). The hashing macros are:

#define HASH1(x1            )                    ((intx)(x1))
#define HASH2(x1, x2        )                    ((HASH1(x1        ) << 7) ^ HASH1(x2))
#define HASH3(x1, x2, x3    )                    ((HASH2(x1, x2    ) << 7) ^ HASH1(x3))
#define HASH4(x1, x2, x3, x4)                    ((HASH3(x1, x2, x3) << 7) ^ HASH1(x4))

2.3 ValueMapArray

Because hash collisions are possible, the JVM stores each instruction’s hash and value in a ValueMapEntry linked list within a ValueMapArray. The array index is computed as hash % size, and entries with the same hash are traversed to verify true equality.

virtual bool is_equal(Value v) const {
    if (!(enabled) ) return false;
    class_name* _v = v->as_##class_name();
    if (_v == NULL ) return false;
    if (f1 != _v->f1) return false;
    if (f2 != _v->f2) return false;
    if (f3 != _v->f3) return false;
    return true;
}

If an instruction’s hash is zero (e.g., if, goto, return), it is not stored in the array.

2.4 CFG Control‑Flow Analysis

Global Value Numbering performs a function‑wide analysis, requiring data‑flow information across BBs. Consider the following code:

int adder = c.t+8;
while (num<100){
    num = c.t+8;
    if(num>10)
    c.t=10;
}
return num+c.t+8;

The corresponding CFG shows that the first and third occurrences of c.t+8 cannot be merged because c.t is reassigned inside the loop.

2.5.1 Kill Scenarios

A "kill" occurs when a variable’s value changes, preventing further merging of expressions that depend on it. For example, after c.t = 10, any previous value numbers involving c.t must be invalidated.

The kill process marks the field as killed and removes related ValueMapEntry objects, often using a bitmap where each bit represents a variable.

2.5.2 Flow Analysis

The C1 HIR is a doubly‑linked list of BBs. Forward analysis may incorrectly include non‑loop nodes, so backward analysis is employed to isolate true loop‑contained nodes and limit analysis to a configurable maximum loop size (default 8).

2.5.3 Replacing Identical Expressions

When an identical expression is found in a later BB, the compiler substitutes the earlier computed value. Example transformation:

. 27   0    i18    a4._12 (I) t
  30   0    i19    i11 + i18
  31   0    i20    8
  33   0    i21    i19 + i20
. 34   0    i22    ireturn i21

becomes

30   1    i19    i11 + i7
  33   1    i21    i19 + i8
. 34   0    i22    ireturn i21

Here i7 replaces i18 and i8 replaces i20, demonstrating successful value‑numbering optimization.