Value Numbering: How TurboFan Merges Two Identical Expressions

TL;DR: src/compiler/value-numbering-reducer.cc keeps a hand-rolled, open-addressed hash table of the idempotent nodes it has seen, keyed by NodeProperties::HashCode - the operator’s hash, the input count, and the ids of the inputs. When a new node hashes to an entry that NodeProperties::Equals says is identical, the new node is replaced by the old one. Only operators with Operator::kIdempotent are eligible, which in practice means the pure ones: no effect input, no control input, no deopt. Everything with a side effect - a load, a call, a store - is invisible to this pass, and the Turboshaft successor to it, src/compiler/turboshaft/value-numbering-reducer.h, has to invent an “epoch” mechanism to merge loads safely.

A TurboFan graph is a DAG, and DAGs are full of repeated subexpressions. a + b computed twice, Math.max(x, 0) inlined twice, the same constant used in four places. Every one of those duplicates is a node that has to be scheduled, a value that has to be assigned a register, and a live range that has to be tracked.

Value numbering is the pass that collapses them. The name comes from classic compiler literature - “global value numbering” - and V8’s implementation is small, sharp and slightly unusual.

Hash-consing: the node cache

Before value numbering there is a much simpler form of the same idea. V8 does not create a new node every time you ask for a constant. It hash-conses them: the NodeCache in src/compiler/node-cache.h maps a value to the node that represents it, and the node is created only the first time.

// src/compiler/node-cache.h:28
// A cache for nodes based on a key. Useful for implementing canonicalization of
// nodes such as constants, parameters, etc.
template <typename Key, typename Hash = base::hash<Key>,
          typename Pred = std::equal_to<Key> >
class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) NodeCache final {
 public:
  explicit NodeCache(Zone* zone) : map_(zone) {}
  ~NodeCache() = default;
  NodeCache(const NodeCache&) = delete;
  NodeCache& operator=(const NodeCache&) = delete;

  // Search for node associated with {key} and return a pointer to a memory
  // location in this cache that stores an entry for the key. If the location
  // returned by this method contains a non-nullptr node, the caller can use
  // that node. Otherwise it is the responsibility of the caller to fill the
  // entry with a new node.
  Node** Find(Key key) { return &(map_[key]); }

The Node** return is the interesting design. Find does not create anything; it hands back a slot in the map, and the caller fills it in if it is empty:

// src/compiler/js-graph.cc:149
Node* JSGraph::NumberConstant(double value) {
  Node** loc = cache_.FindNumberConstant(value);
  if (*loc == nullptr) {
    *loc = graph()->NewNode(common()->NumberConstant(value));
  }
  return *loc;
}

CommonNodeCache (src/compiler/common-node-cache.h) is the bundle of all of these - one per kind of constant: int32, int64, tagged index, float32, float64, external, pointer, number, heap, and the two relocatable variants. The float and double caches hash the bit pattern, not the value, so that -0.0 and +0.0 and the various NaNs each get their own node:

// src/compiler/common-node-cache.h:47
  Node** FindFloat32Constant(float value) {
    // We canonicalize float constants at the bit representation level.
    return float32_constants_.Find(base::bit_cast<int32_t>(value));
  }

  Node** FindFloat64Constant(Float64 value) {
    // We canonicalize double constants at the bit representation level.
    return float64_constants_.Find(value.get_bits());
  }

There is also a set of global cached nodes - undefined, true, false, null, 0, -0, 1, -1, NaN, the empty fixed array, a dozen map constants, and the various holes (TheHole, TdzHole, Uninitialized, OptimizedOut, StaleRegister), listed in the CACHED_GLOBAL_LIST macro in src/compiler/js-graph.h:115. They exist as single, shared nodes for the whole compilation, and JSGraph::GetCachedNodes hands them all to the reducer as roots so that they can be used as replacements.

This is the one place where two identical nodes really do become the same node. Value numbering, by contrast, replaces one with the other.

The value numbering reducer

src/compiler/value-numbering-reducer.cc is a Reducer - not an AdvancedReducer - and it maintains a single open-addressed hash table in a zone-allocated array. The first thing it does is check the operator’s properties:

// src/compiler/value-numbering-reducer.cc:26
Reduction ValueNumberingReducer::Reduce(Node* node) {
  if (!node->op()->HasProperty(Operator::kIdempotent)) return NoChange();

  const size_t hash = NodeProperties::HashCode(node);
  if (!entries_) {
    DCHECK_EQ(0, size_);
    DCHECK_EQ(0, capacity_);
    // Allocate the initial entries and insert the first entry.
    capacity_ = kInitialCapacity;
    entries_ = temp_zone()->AllocateArray<Node*>(kInitialCapacity);
    memset(entries_, 0, sizeof(*entries_) * kInitialCapacity);
    entries_[hash & (kInitialCapacity - 1)] = node;
    size_ = 1;
    return NoChange();
  }

kInitialCapacity is 256, and the table is a power of two, so the bucket index is hash & (capacity_ - 1). The probe sequence is linear probing:

// src/compiler/value-numbering-reducer.cc:45
  const size_t mask = capacity_ - 1;
  size_t dead = capacity_;

  for (size_t i = hash & mask;; i = (i + 1) & mask) {
    Node* entry = entries_[i];
    if (!entry) {
      if (dead != capacity_) {
        // Reuse dead entry that we discovered on the way.
        entries_[dead] = node;
      } else {
        // Have to insert a new entry.
        entries_[i] = node;
        size_++;

        // Resize to keep load factor below 80%
        if (size_ + size_ / 4 >= capacity_) Grow();
      }
      DCHECK(size_ + size_ / 4 < capacity_);
      return NoChange();
    }

Two details worth stopping on. The load factor is kept below 80 % (size_ + size_ / 4 >= capacity_ triggers a grow), and a dead entry

• a node killed since it was inserted - is remembered during the probe and reused rather than leaving a hole in the table:

// src/compiler/value-numbering-reducer.cc:115
    // Skip dead entries, but remember their indices so we can reuse them.
    if (entry->IsDead()) {
      dead = i;
      continue;
    }
    if (NodeProperties::Equals(entry, node)) {
      return ReplaceIfTypesMatch(node, entry);
    }

What counts as “the same expression”

Two functions in src/compiler/node-properties.cc define equality. The hash combines the operator’s hash, the input count, and the ids of the inputs:

// src/compiler/node-properties.cc:700
size_t NodeProperties::HashCode(Node* node) {
  size_t h = base::hash_combine(node->op()->HashCode(), node->InputCount());
  for (Node* input : node->inputs()) {
    h = base::hash_combine(h, input->id());
  }
  return h;
}

and the equality check compares the operators and then the inputs, one by one (src/compiler/node-properties.cc:708):

bool NodeProperties::Equals(Node* a, Node* b) {
  if (!a->op()->Equals(b->op())) return false;
  if (a->InputCount() != b->InputCount()) return false;
  Node::Inputs aInputs = a->inputs();
  Node::Inputs bInputs = b->inputs();

  auto aIt = aInputs.begin();
  auto bIt = bInputs.begin();
  auto aEnd = aInputs.end();

  for (; aIt != aEnd; ++aIt, ++bIt) {
    if ((*aIt)->id() != (*bIt)->id()) return false;
  }
  return true;
}

node->inputs() is all the inputs - value, effect and control. So two nodes are equal only if they have the same operator, the same number of inputs, and the same inputs in the same positions.

The operator comparison is not just an opcode comparison. Operator has a virtual Equals, and the templated Operator1<T> override compares the static parameter too (src/compiler/operator.h:202), so LoadField at offset 8 and LoadField at offset 16 are different operators even though they have the same opcode.

Idempotence: the gate

The kIdempotent property is the whole safety argument, and it is defined in src/compiler/operator.h:

// src/compiler/operator.h:40
  enum Property {
    kNoProperties = 0,
    kCommutative = 1 << 0,  // OP(a, b) == OP(b, a) for all inputs.
    kAssociative = 1 << 1,  // OP(a, OP(b,c)) == OP(OP(a,b), c) for all inputs.
    kIdempotent = 1 << 2,   // OP(a); OP(a) == OP(a).
    kNoRead = 1 << 3,       // Has no scheduling dependency on Effects
    kNoWrite = 1 << 4,      // Does not modify any Effects and thereby
                            // create new scheduling dependencies.
    kNoThrow = 1 << 5,      // Can never generate an exception.
    kNoDeopt = 1 << 6,      // Can never generate an eager deoptimization exit.
    kFoldable = kNoRead | kNoWrite,
    kEliminatable = kNoDeopt | kNoWrite | kNoThrow,
    kKontrol = kNoDeopt | kFoldable | kNoThrow,
    kPure = kKontrol | kIdempotent
  };

OP(a); OP(a) == OP(a) - running it twice is the same as running it once. A kPure operator has no effect input, no control input, cannot throw, cannot deoptimize, does not read or write memory, and is idempotent. That is the class of node this pass can safely merge.

Everything else is invisible to it. A LoadField is V(LoadField, FieldAccess, Operator::kNoWrite, 1, 1, 1) (src/compiler/simplified-operator.cc:2609) - it has an effect input and a control input, and it is not idempotent, so the reducer returns NoChange before even hashing it. Same for calls, stores and deoptimization points.

This is where the “effects and deopt points prevent merging” rule comes from, and it is worth being precise about the two independent reasons:

1. The operator property. A node that reads memory, writes memory, throws, or deoptimizes is not idempotent, so it is never considered.
2. The input comparison. NodeProperties::Equals compares effect and control inputs as well as value inputs, so even for a node that somehow had the kIdempotent property, two instances with different effect chains would not be equal.

The type check on replacement

When the reducer finds a match, it does not replace unconditionally. The replacement’s type has to be at least as good as the original’s:

// src/compiler/value-numbering-reducer.cc:126
Reduction ValueNumberingReducer::ReplaceIfTypesMatch(Node* node,
                                                     Node* replacement) {
  // Make sure the replacement has at least as good type as the original node.
  if (NodeProperties::IsTyped(replacement) && NodeProperties::IsTyped(node)) {
    Type replacement_type = NodeProperties::GetType(replacement);
    Type node_type = NodeProperties::GetType(node);
    if (!replacement_type.Is(node_type)) {
      // Ideally, we would set an intersection of {replacement_type} and
      // {node_type} here. However, typing of NumberConstants assigns different
      // types to constants with the same value (it creates a fresh heap
      // number), which would make the intersection empty. To be safe, we use
      // the smaller type if the types are comparable.
      if (node_type.Is(replacement_type)) {
        NodeProperties::SetType(replacement, node_type);
      } else {
        // Types are not comparable => do not replace.
        return NoChange();
      }
    }
  }
  return Replace(replacement);
}

The comment is a nice piece of compiler archaeology. Two NumberConstant nodes with the same value can have different types, because the typer gives each one its own fresh heap number. Intersecting those types would produce the empty type, so the reducer falls back to “use the smaller type if the types are comparable, otherwise do not replace at all”.

The collision problem

The reducer has to cope with the fact that other reducers change nodes underneath it. The comment describes the scenario exactly:

// src/compiler/value-numbering-reducer.cc:66
    if (entry == node) {
      // We need to check for a certain class of collisions here. Imagine the
      // following scenario:
      //
      //  1. We insert node1 with op1 and certain inputs at index i.
      //  2. We insert node2 with op2 and certain inputs at index i+1.
      //  3. Some other reducer changes node1 to op2 and the inputs from node2.
      //
      // Now we are called again to reduce node1, and we would return NoChange
      // in this case because we find node1 first, but what we should actually
      // do is return Replace(node2) instead.
      for (size_t j = (i + 1) & mask;; j = (j + 1) & mask) {

The reducer is asked to reduce node1 again, finds itself in the bucket, and has to keep probing to find the other node that is now equal to it:

// src/compiler/value-numbering-reducer.cc:98
        if (NodeProperties::Equals(other_entry, node)) {
          Reduction reduction = ReplaceIfTypesMatch(node, other_entry);
          if (reduction.Changed()) {
            // Overwrite the colliding entry with the actual entry.
            entries_[i] = other_entry;
          }
          return reduction;
        }

This is a real subtlety: the value numbering table is a cache of a mutable graph, and the reducer has to be defensive about its own stale entries.

How the graph reducer drives it

Value numbering is not a phase on its own; it is one reducer among several, all run by the GraphReducer to a fixed point. The reducer loop explains why the value numbering reducer can see the same node twice:

// src/compiler/graph-reducer.cc:100
Reduction GraphReducer::Reduce(Node* const node) {
  auto skip = reducers_.end();
  for (auto i = reducers_.begin(); i != reducers_.end();) {
    if (i != skip) {
      tick_counter_->TickAndMaybeEnterSafepoint();
      Reduction reduction = (*i)->Reduce(node, observe_node_manager_);
      if (!reduction.Changed()) {
        // No change from this reducer.
      } else if (reduction.replacement() == node) {
        // {replacement} == {node} represents an in-place reduction. Rerun
        // all the other reducers for this node, as now there may be more
        // opportunities for reduction.
        ...
        skip = i;
        i = reducers_.begin();
        continue;
      } else {
        // {node} was replaced by another node.
        ...
        return reduction;
      }
    }
    ++i;
  }

An in-place reduction restarts the whole reducer list for that node - exactly the situation the collision comment describes: node1 was reduced in place by another reducer, and now value numbering gets to look at it again.

ValueNumberingReducer is added to four phases in src/compiler/pipeline.cc - the EarlyOptimizationPhase (line 1259), the LoadEliminationPhase (line 1292), and the two Wasm phases (lines 1380 and 1404).

Value numbering in Turboshaft: the epoch trick

The modern backend replaces all of this with a much more ambitious version, in src/compiler/turboshaft/value-numbering-reducer.h. It does merge loads, which the old one could not, and to do that safely it invents an “epoch” mechanism.

The epoch counter is bumped whenever an operation can write memory (src/compiler/turboshaft/value-numbering-reducer.h:190), and the epoch is part of the hash, so that a load recorded before a write is not found after it:

// src/compiler/turboshaft/value-numbering-reducer.h:464
  template <bool same_block_only, class Op>
  size_t ComputeHash(const Op& op, bool needs_epoch_check) {
    size_t hash = op.hash_value();
    if (same_block_only) {
      hash = fast_hash_combine(Asm().current_block()->index(), hash);
    }
    if (needs_epoch_check) {
      hash = fast_hash_combine(current_epoch_, hash);
    }
    if (V8_UNLIKELY(hash == 0)) return 1;
    return hash;
  }

The subtlety is that the epoch is per block, not global, and it is recomputed at each block boundary from the predecessors’ end epochs:

// src/compiler/turboshaft/value-numbering-reducer.h:241
    if (block->IsLoop()) {
      // We assume that the backedge might invalidate everything that requires
      // an epoch check. So, we increment the current_epoch, thus guaranteeing
      // that we won't replace any CanRead operation in the loop by an operation
      // from before the loop.
      current_epoch_++;
    }

The epoch is recomputed at each block boundary from the maximum of the predecessors’ end epochs, so it is a per-block version number rather than a global one. The loop case is the good bit: a backedge might write anything, so entering a loop bumps the epoch and invalidates every load recorded before the loop.

Not everything can be merged, though. The reducer has a whitelist of effects that permit it (src/compiler/turboshaft/value-numbering-reducer.h:291): CanDependOnChecks, CanChangeControlFlow, CanAllocateWithoutIdentity and CanReadMemory. And two special cases are carved out. DeoptimizeIf is merged, even though it can leave the function:

// src/compiler/turboshaft/value-numbering-reducer.h:299
  template <class Op>
  bool EffectsAllowGVN(const Op& op) {
    if constexpr (std::is_same_v<Op, DeoptimizeIfOp>) {
      // GVNing DeoptimizeIf even though its effect would otherwise prevent it.
      return true;
    }
    if constexpr (std::is_same_v<Op, LoadOp>) {
      if (!op.index().valid() && op.offset == offsetof(HeapObject, map_)) {
        // We don't GVN loads at offset kMapOffset, because they could be string
        // maps loads, which can get invalidated on GCs and we don't increment
        // {current_epoch_} on operations that can_allocate but only on those
        // that can_write.
        return false;
      }
    }
    return EffectsAllowGVN(op.Effects());
  }

The map load exclusion is a nice detail: a load of the map field of a string can be invalidated by a garbage collection, and the epoch counter is not bumped by operations that only allocate.

The Turboshaft reducer also has an explicit “do not merge” scope (src/compiler/turboshaft/value-numbering-reducer.h:100), for the rare cases where the compiler deliberately wants duplication.

The scheduler and register allocation

Value numbering is a graph optimisation, and its payoff lands in the backend. The instruction selector turns each surviving graph node into one or more machine instructions:

// src/compiler/backend/instruction-selector.cc:303
Instruction* InstructionSelector::Emit(Instruction* instr) {
  instructions_.push_back(instr);
  return instr;
}

Fewer nodes means fewer instructions, fewer virtual registers, shorter live ranges, and less register pressure. The register allocator then builds one live range per virtual register:

// src/compiler/backend/register-allocator.cc:1173
      live_ranges_(code->VirtualRegisterCount(), nullptr, allocation_zone()),

and the number of registers it needs is a function of how many values are live at the same time. Two identical a + b computations that share one node are one live range instead of two.

The scheduler is affected too. TurboFan’s scheduler can split a basic block at a pure node if that node’s uses are spread across successors (src/compiler/scheduler.cc:1615). A node that has been merged away is not a candidate for splitting at all.

Related

• How V8 optimizes JavaScript with TurboFan
• How V8 deoptimizes hot JavaScript

Trade-offs

What it buys. Fewer nodes, fewer instructions, less register pressure, smaller code, and a graph that is easier for later analyses to reason about.

What it costs.

• A hash table per compilation. Zone-allocated, grown by doubling, rehashing every entry on the way.
• The idempotence restriction. The pass is blind to loads, stores and calls, which is where most of the redundancy in a real program lives. The Turboshaft successor exists precisely to fix that, and it pays for it with the epoch machinery.
• Type friction. Two structurally identical nodes can have incomparable types - the NumberConstant case - and then they cannot be merged at all.
• Stale entries. The table caches a mutable graph, so a node that changes under it can invalidate its own entry.

The bottom line

TurboFan’s value numbering is a hash table with a very specific idea of what it may merge: nodes whose operator says “running me twice is the same as running me once”, and whose inputs are literally the same nodes. Everything else is left alone.

That restriction is not timidity, it is the definition of the problem. A load is not idempotent - the world might change between the two loads - and a deoptimization point is not idempotent - the second one might not be reached at all. The Turboshaft rewrite, with its epoch counter, shows how far you can push this by replacing “nothing happened in between” with a version number that bumps whenever something might have written.

The thing people get wrong

People assume value numbering is “common subexpression elimination” - the compiler notices that you wrote a + b twice and does it once. In TurboFan’s classic implementation, that is exactly not what happens. The reducer only ever sees operators with Operator::kIdempotent, which means pure, effect-free, control-free, non-throwing, non-deopting nodes. Two a + b computations are merged if the + is a pure add; two o.x loads are not merged at all, because a load has an effect input and is not idempotent.

The other misconception is that value numbering is about the source code. It is about the graph. Two expressions that look different can be the same node after inlining, constant folding and type narrowing; two that look identical can be different nodes because their effect chains differ. Which is why the Turboshaft version needs a dominator-tree traversal with per-depth bookkeeping to know when a previous definition is still in scope.