# UNDF: UNDF-2026-000000536
# SM-0002: MDefinitionRemapper::lookup() O(N) linear scan in loop-unrolling phase

**File:** `js/src/jit/UnrollLoops.cpp`
**Lines:** 344–354 (`lookup`), 1132–1140 (call site in unrolling loop)
**Severity:** MEDIUM
**CWE:** CWE-407 (Inefficient Algorithmic Complexity)

## Description

`MDefinitionRemapper` stores `(original, replacement)` pairs in a
`mozilla::Vector<Pair, 32, SystemAllocPolicy>`.  Its `lookup()` method
iterates the entire vector linearly (O(V)) to find a key.

`lookup()` is called from `MakeReplacementInstruction()` and
`MakeReplacementPhi()` — once per operand of every instruction/phi being
cloned.  These helpers are called inside a doubly-nested loop:

```
for cix in 1..unrollFactor:          // copies
  for bix in 0..numBlocksInOriginal: // blocks
    for each phi in block:
      for each operand of phi:
        mapper.lookup(operand)        // O(V) scan
    for each insn in block:
      for each operand of insn:
        mapper.lookup(operand)        // O(V) scan
```

With V values in the mapper (bounded by `MaxValuesForPeel = 150`), each
lookup is O(V) and the total cloning cost per body copy is O(V²) = up to
22 500 pointer comparisons.  With `unrollFactor` up to ~4, worst case is
O(4 × V²) = 90 000 ops for a single loop unroll.

## Fix

Replace `mozilla::Vector<Pair, 32>` with
`mozilla::HashMap<MDefinition*, MDefinition*, DefaultHasher<MDefinition*>>`
(already available in `js/src/ds/PointerSet.h` or via `HashSet.h`).

`lookup()` becomes O(1) amortised.  `enregister()` uses `put()`,
`update()` uses `put()`.  No iteration order requirement exists for the
remapper — unlike `ValueSet` which has an inline size.

## Complexity

| Path | Before | After |
|------|--------|-------|
| `lookup()` | O(V) | O(1) |
| Total unroll of loop with V values | O(V²) | O(V) |
| Worst case (V=150, 4× unroll) | 90 000 ops | 600 ops |

**Speedup:** ~150× at V=150

## References

- `SimpleSet::add()` also calls `contains()` (O(N)) — see SM-0003
- Related fix: SM-0001 (LinearSum::add HashMap)
