# UNDF: UNDF-2026-000000599
# UNDF: (pending)
# graal-0001: RegisterVerifier.addToWorkList — ArrayList.contains() O(B²) in LSRA verification worklist

## CWE-407 — Algorithmic Complexity: O(N) ArrayList.contains() per block in register verifier worklist BFS

| Field        | Value |
|--------------|-------|
| ID           | graal-0001 |
| Severity     | MEDIUM |
| Ecosystem    | graal |
| Package      | jdk.graal.compiler |
| File         | `compiler/src/jdk.graal.compiler/src/jdk/graal/compiler/lir/alloc/lsra/RegisterVerifier.java` |
| Lines        | 50, 72–76, 80 |
| Complexity   | O(B) per block; O(B²) to process B-block CFG |
| Hot path     | Called during LSRA (Linear Scan Register Allocation) verification phase of JIT compilation |

## Defect

`RegisterVerifier.addToWorkList` uses `ArrayList<BasicBlock<?>>` as the worklist and checks for
duplicates with `workList.contains(block)` — an O(N) linear scan:

```java
// RegisterVerifier.java:50
ArrayList<BasicBlock<?>> workList;  // ArrayList → contains() is O(N)

// RegisterVerifier.java:72-76 (DEFECT)
void addToWorkList(BasicBlock<?> block) {
    if (!workList.contains(block)) {   // O(N) linear scan of workList
        workList.add(block);
    }
}

// RegisterVerifier.java:78-83
RegisterVerifier(LinearScan allocator) {
    // ...
    workList = new ArrayList<>(16);   // ArrayList
}
```

The `verify()` method (lines 86-102) drives a BFS: `processBlock()` calls `addToWorkList` for each
successor block. For B basic blocks in the CFG with branching factor F:
- `addToWorkList` is called ~B×F times
- Each call does O(worklist_size) scan ≤ O(B)
- Total: O(B² × F) comparisons

GraalVM's own codebase uses `EconomicSet` (a memory-efficient HashSet implementation) throughout
the compiler for exactly this use case. `ArrayList.contains` is out of place here.

## Fix

Replace `ArrayList` with a `java.util.HashSet<BasicBlock<?>>` or `EconomicSet<BasicBlock<?>>`,
or add a parallel membership set alongside the list (to preserve FIFO ordering):

```java
// AFTER — O(B) total for B-block CFG
ArrayList<BasicBlock<?>> workList;
EconomicSet<BasicBlock<?>> workListSet;   // ADD: O(1) membership guard

RegisterVerifier(LinearScan allocator) {
    this.allocator = allocator;
    workList = new ArrayList<>(16);
    workListSet = EconomicSet.create(16); // ADD
    // ...
}

void addToWorkList(BasicBlock<?> block) {
    if (workListSet.add(block)) {    // O(1): add returns false if already present
        workList.add(block);
    }
}

// In verify(), after remove(0), also remove from workListSet:
BasicBlock<?> block = workList.remove(0);
workListSet.remove(block);           // ADD: keep mirror in sync
processBlock(block);
```

## Speedup

| Blocks (B) | Before (comparisons) | After (comparisons) | Speedup |
|------------|----------------------|---------------------|---------|
| 50         | ~625                 | 50                  | 12.5×   |
| 100        | ~2,500               | 100                 | 25×     |
| 500        | ~62,500              | 500                 | 125×    |

Growth before: O(B²). Growth after: O(B).
