java-topology/defects/spidermonkey/patch/sm-0003-simpleset-hashset.md

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:

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.

// 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