# UNDF: UNDF-2026-000000434
# JSC-0002: DFGGraph::handleSuccessor() O(E×P) predecessor deduplication via Vector::contains

**File:** `Source/JavaScriptCore/dfg/DFGGraph.cpp`
**Lines:** 738–747 (`handleSuccessor`), 749–761 (`determineReachability`)
**Severity:** MEDIUM
**CWE:** CWE-407 (Inefficient Algorithmic Complexity)

## Description

`Graph::handleSuccessor()` builds the `predecessors` list for each basic
block as part of reachability analysis.  It deduplicates predecessors
with a linear membership test:

```cpp
// DFGGraph.cpp line 744-746
if (!successor->predecessors.contains(block))
    successor->predecessors.append(block);
```

`PredecessorList` is `typedef Vector<BasicBlock*, 2>` (DFGBasicBlock.h
line 46).  `Vector::contains` is a linear scan — O(P) where P is the
current predecessor count.

`handleSuccessor` is called from `determineReachability()`:

```cpp
while (!worklist.isEmpty()) {
    BasicBlock* block = worklist.takeLast();
    for (unsigned i = block->numSuccessors(); i--;)     // O(S)
        handleSuccessor(worklist, block, block->successor(i));  // O(P) each
}
```

Total cost over the entire CFG: O(E × P_avg) where E = number of CFG
edges and P_avg = average predecessor count.

For pathological CFGs (e.g., a function with a large switch that merges
into a single join block with P predecessors):
- E = number of edges = P (each arm is one edge to the join)
- Cost = O(P²)

With a 500-case switch, P=500, cost = 250 000 comparisons per
`resetReachability()` call.  `resetReachability()` is called at the
start of every DFG optimization pass.

## Fix

Replace `PredecessorList` (`Vector<BasicBlock*, 2>`) dedup check with a
separate `HashSet<BasicBlock*>` in `handleSuccessor`, or change
`BasicBlock::predecessors` to a type with O(1) membership.

Minimal fix at the call site:

```cpp
void Graph::handleSuccessor(Vector<BasicBlock*, 16>& worklist,
    BasicBlock* block, BasicBlock* successor)
{
    if (!successor->isReachable) {
        successor->isReachable = true;
        worklist.append(successor);
    }
    // Use a HashSet for O(1) dedup instead of Vector::contains O(P)
    if (m_predecessorSeen.add(successor, block))  // HashSet<pair>
        successor->predecessors.append(block);
}
```

Alternatively, make `PredecessorList` a `HashSet<BasicBlock*>` since
iteration order is not required for DFG analysis (the passes iterate
block indices, not predecessor list order).

## Complexity

| Scenario | Before | After |
|----------|--------|-------|
| `handleSuccessor` per call | O(P) | O(1) |
| `determineReachability` | O(E × P) | O(E) |
| 500-case switch (P=500) | 250 000 ops | 500 ops |

**Speedup:** ~500× for large switch convergence blocks

## Affected Callers

- `Graph::determineReachability()` — called from `Graph::resetReachability()`
- `resetReachability()` is called at the start of multiple DFG phases:
  ByteCodeParser, SSA conversion, CFG simplification, etc.

## References

- `Source/JavaScriptCore/dfg/DFGBasicBlock.h` line 46 — `PredecessorList` typedef
- `Source/JavaScriptCore/dfg/DFGGraph.cpp` lines 738–777
