russell@unturf.com
bb1a6f002f
swift-0001: QualifiedLookupRequest::evaluate (NameLookup.cpp:2860) pushes protocol superclassDecl onto BFS stack unconditionally — visited.insert() return not checked. Nearby ClassDecl arm (line 2833) is correctly guarded. Diamond protocol hierarchies sharing a class superclass trigger O(2^D) re-traversal on every qualified member lookup. Fix: check .second. llvm, gcc, webkit: CLEAN in available sparse-clone code.
23 lines
1 KiB
Markdown
23 lines
1 KiB
Markdown
# CLEAN — LLVM (llvm/llvm)
|
|
Scanned 2026-03-30 for CWE-407 diamond recursion (O(2^D)).
|
|
|
|
## Scope
|
|
|
|
Sparse clone: `llvm/llvm/lib/` — Analysis/ (390 files), Support/, Transforms/.
|
|
No IR/ or CodeGen/ in this clone (Type.cpp, StructType, PointerType not present).
|
|
|
|
## Findings
|
|
|
|
- `Analysis/ScalarEvolution.cpp` — `Visited.insert(I)` at line 8747 is a BFS
|
|
seed (worklist-based, not recursive); `PushDefUseChildren` checks `.second`
|
|
correctly (line 4947). CLEAN.
|
|
- `Analysis/MemorySSAUpdater.cpp` — line 66 checks `.second`; line 50 is a
|
|
seed. CLEAN.
|
|
- All `Transforms/Utils/` recursive worklist traversals (`LoopPeel`,
|
|
`InlineFunction`, `MoveAutoInit`, `PredicateInfo`, `BypassSlowDivision`)
|
|
check `!Visited.insert(...).second` before adding to worklist. CLEAN.
|
|
- `Analysis/TypeMetadataUtils.cpp` — no visited patterns at all. CLEAN.
|
|
- No `getSubtypes()`, `getBases()`, `bases()`, `superclasses()` type hierarchy
|
|
iteration found in the available subset (IR/ not in clone).
|
|
|
|
**Result: No actionable O(2^D) diamond defects in available code.**
|