# UNDF: UNDF-2026-000000537
# SM-0003: SimpleSet::contains() O(N) linear scan in loop-unrolling phase

**File:** `js/src/jit/UnrollLoops.cpp`
**Lines:** 303–311 (`contains`), 313 (`add`); call sites at 1361, 1386, 1450
**Severity:** MEDIUM
**CWE:** CWE-407 (Inefficient Algorithmic Complexity)

## Description

`SimpleSet<T,N,AP>` is a pointer-set backed by `mozilla::Vector<T,N,AP>`.
Its `contains()` method performs a full linear scan:

```cpp
bool contains(T t) const {
  for (auto* existing : vec_) {
    if (existing == t) return true;
  }
  return false;
}
bool add(T t) {
  return contains(t) ? true : vec_.append(t);
}
```

Two instantiations are hot:

| Alias | Inline cap | Usage |
|-------|-----------|-------|
| `BlockSet` | 8  | `state.exitTargetBlocks` |
| `ValueSet` | 64 | `state.exitingValues`    |

`state.exitTargetBlocks.contains(succ)` and `state.exitingValues.contains(exitingValue)`
are called inside the unrolling triple-nested loop:

```
for cix in 0..unrollFactor:          // copies (up to ~4)
  for bix in 0..numBlocksInOriginal: // blocks
    for each successor of block's last instruction:
      exitTargetBlocks.contains(succ)          // O(B) scan, B up to 8
    for each phi/instruction in block:
      exitingValues.contains(exitingValue)     // O(V) scan, V up to 64
```

With `ValueSet` holding up to `MaxValuesForPeel = 64` entries and 4 unroll
copies, worst-case cost is `O(4 × blocks × V)` per loop unroll.  The
`MaxValuesForPeel` guard caps V at 64, so at V=64 this is 256 × blocks ×
64 = up to 16 384 pointer comparisons per loop body vs. O(256 × blocks) with
O(1) lookup.

## Fix

Replace `mozilla::Vector<T, N, AP>` backing with
`mozilla::HashSet<T, DefaultHasher<T>, AP>` (already available in SpiderMonkey
via `mozilla/HashTable.h`).  `contains()` becomes a single hash probe; `add()`
uses `putNew()`.  Iteration order is irrelevant for both `BlockSet` and
`ValueSet`.

```cpp
// Before
class SimpleSet {
  mozilla::Vector<T, N, AP> vec_;
 public:
  bool contains(T t) const {
    for (auto* existing : vec_) {     // O(N) scan — CWE-407
      if (existing == t) return true;
    }
    return false;
  }
  [[nodiscard]] bool add(T t) {
    return contains(t) ? true : vec_.append(t);
  }
};

// After
class SimpleSet {
  mozilla::HashSet<T, mozilla::DefaultHasher<T>, AP> set_;
 public:
  bool contains(T t) const {
    return set_.has(t);               // O(1) amortised
  }
  [[nodiscard]] bool add(T t) {
    return set_.putNew(t);            // O(1) amortised, ignores duplicates
  }
  bool empty() const { return set_.empty(); }
  size_t size() const { return set_.count(); }
  T get(size_t ix) const = delete;   // callers use contains/add only
};
```

Note: `get(ix)` is used at line 878 (`state.exitingValues.get(i)`) only in a
sequential loop that doesn't call `contains()`, so it can be preserved by
keeping a parallel `Vector` for indexed access or switching callers to iterate
over the set.

## Complexity

| Path | Before | After |
|------|--------|-------|
| `contains()` | O(N) | O(1) |
| `add()` | O(N) | O(1) |
| Unroll inner loop per copy (V=64) | O(64) per check | O(1) per check |
| Worst case (V=64, 4× copies, 50 blocks) | ~51 200 ops | ~800 ops |

**Speedup:** ~64× at V=64 (ValueSet inline cap)

## References

- SM-0002: MDefinitionRemapper::lookup() same file, same phase
- `MaxValuesForPeel` defined near line 200 in UnrollLoops.cpp
