# UNDF: UNDF-2026-000000565
# v8-0003 — compiler/revectorizer: SLPTree::TryReduceLoadChain loads O(L×N) → O(L)

## Metadata
- Project: V8
- Component: src/compiler/revectorizer.cc
- CWE: CWE-407
- Severity: MEDIUM
- Complexity: O(L×N) → O(L) per call, where L = effect-chain length, N = loads.size()
- Function: `SLPTree::TryReduceLoadChain`
- Line: 538 (chromium.googlesource.com/v8/v8, HEAD 2026-03)

## Problem

`TryReduceLoadChain` takes a `ZoneVector<Node*>& loads` and, for each entry in
that vector, walks the effect chain looking for sibling loads to reorder.
Inside the inner while-loop, membership in `loads` is tested with a linear
scan:

```cpp
// src/compiler/revectorizer.cc:537-548
while (SameBasicBlock(*it, load) && IsSupportedLoad(*it)) {
    if (std::find(loads.begin(), loads.end(), *it) != loads.end()) {
        // reorder *it into the chain
    }
    it.Advance();
}
```

Complexity: for each of the N loads, the effect chain is walked (L steps),
and at each step `std::find` does O(N) pointer comparisons → **O(N² × L)**
total.

The current callsite passes `node_group` (size = 2, asserted by `DCHECK_EQ`
at line 554). The defect is therefore latent at present but the function
signature accepts any vector and the quadratic pattern will materialise if
the callsite is extended to larger groups (e.g., 256-bit AVX-512 groups of 4
or 8 nodes, which is the stated direction of the SIMD vectoriser).

## Defective code

```cpp
// src/compiler/revectorizer.cc:529-549
void SLPTree::TryReduceLoadChain(const ZoneVector<Node*>& loads) {
  ZoneSet<Node*> visited(zone());
  for (Node* load : loads) {                    // outer: O(N)
    if (visited.find(load) != visited.end()) continue;
    visited.insert(load);
    EffectChainIterator dest(load);
    EffectChainIterator it(dest.Next());
    while (SameBasicBlock(*it, load) && IsSupportedLoad(*it)) {  // inner: O(L)
      if (std::find(loads.begin(), loads.end(), *it) != loads.end()) { // O(N) -- defect
        ...
      }
      it.Advance();
    }
  }
}
```

## Fix

Build a `ZoneUnorderedSet<Node*>` from `loads` before the loops and use O(1)
`count()` for membership testing:

```cpp
void SLPTree::TryReduceLoadChain(const ZoneVector<Node*>& loads) {
  // CWE-407 fix: O(1) membership for inner-loop test
  ZoneUnorderedSet<Node*> loads_set(loads.begin(), loads.end(), zone());
  ZoneSet<Node*> visited(zone());
  for (Node* load : loads) {
    if (visited.find(load) != visited.end()) continue;
    visited.insert(load);
    EffectChainIterator dest(load);
    EffectChainIterator it(dest.Next());
    while (SameBasicBlock(*it, load) && IsSupportedLoad(*it)) {
      if (loads_set.count(*it) != 0) {          // CWE-407 fix: O(1)
        ...
      }
      it.Advance();
    }
  }
}
```

`ZoneUnorderedSet` is already available via `src/zone/zone-containers.h`
which is included by `revectorizer.h`.

## Complexity analysis

| N (loads group size) | L (effect chain length) | Before (defect)  | After (fix)  |
|---|---|---|---|
| 2 (current)          | L                       | O(2L)            | O(2L)        |
| 4 (AVX-256 groups)   | L                       | O(16L)           | O(4L) — 4x  |
| 8 (AVX-512 groups)   | L                       | O(64L)           | O(8L) — 8x  |
| 16                   | L                       | O(256L)          | O(16L) — 16x|

At the current N=2 the overhead is a single extra pointer comparison per
chain step; the fix adds a one-time O(N) set construction that eliminates
the quadratic growth as N scales.
