65 lines
3.6 KiB
Markdown
65 lines
3.6 KiB
Markdown
# Single-pass graph building — design spec
|
|
|
|
> Status: accepted (README-documented; backlog #1)
|
|
> Owner: fold optimization loop (round 4+), operator-confirmed option 2.
|
|
> Guard rails: docs/research/optimization-loop-2026-07-30.md (measure-first, gates never weakened), the finding-fingerprint + gold gates, and the wall/RSS baselines.
|
|
|
|
## Goal
|
|
|
|
Eliminate the second full per-scan parse. Today a source scan parses every TU
|
|
twice — once to build the project call graph (`call_graph_ms` 18.8s on the fold
|
|
self-scan), once to run detectors — because the detector pass consumes the graph
|
|
(cross-TU candidate expansion + summary priming). The portability-safe fix is
|
|
one parse per TU; the graph comes from that same parse.
|
|
|
|
## Current sequence (scan_runner.cpp `runClangDetectorsOnShard`)
|
|
|
|
1. `primeCrossTUProperties` — third ClangTool parse, only when
|
|
div-by-zero/null-deref/int-overflow/oob are enabled (no-op on the fold
|
|
manifest).
|
|
2. `assembleProjectCallGraph` — full re-parse of all TUs → `call_graph`
|
|
(`graph_security_candidates` = cross-TU-expanded candidate set).
|
|
3. Detector pass — second full parse, runs every detector; the security
|
|
walk consults `graph_security_candidates`, and summary priming uses the
|
|
graph for SCC-ordered passes.
|
|
|
|
## Why it cannot be folded naively
|
|
|
|
The candidate-expansion closure needs the complete cross-TU graph, which exists
|
|
only after every TU is parsed. Running detectors in the very parse that builds
|
|
the graph therefore works only for graph-*independent* detectors. Graph-
|
|
*dependent* detectors (security candidate expansion; summary priming) demand,
|
|
in the deferred phase, either (A) kept ASTs (~210MB/AST — infeasible at 8 TUs),
|
|
or (B) re-materializing the walk input from persisted IR.
|
|
|
|
(B) is the chosen shape: encode functions to fold IR once, keep the lightweight
|
|
records, discard ASTs, run the closure, then walk candidates from the stored IR
|
|
without a re-parse.
|
|
|
|
## Seams
|
|
|
|
| Existing | Change |
|
|
|---|---|
|
|
| `collectCallGraphEdges(ctx, local_graph)` (source_call_graph.cpp) | already runs on a live `clang::ASTContext`; in-pass graph contribution is the same call + `graphToContribution` — no re-parse |
|
|
| `SecurityWalker` / detectors encode via `encodeExpr` + visitor hooks on the AST | the deferred walk must run on serialized `FunctionIR` (see `fold/ir`, `serialize.cpp`, `FunctionSummary`) instead of the live AST |
|
|
| `graph_security_candidates` + `securityCandidateFunctions` | unchanged consumer; its input (merged graph) is available only post-pass |
|
|
| `primeSymbolicSummaries` SCC order | unchanged consumer; needs the post-pass graph |
|
|
|
|
## Slice plan (each lands behind the gates; fingerprints exact)
|
|
|
|
- **S0 (measure, no behavior change)** — confirm the 18.8s is ClangTool parse
|
|
vs edge/merge, and measure the IR size for all fold-manifest functions
|
|
(bounds the memory for kept-IR). If per-function IR is ~KB-scale, (B) fits in
|
|
tens of MB.
|
|
- **S1 (neutral plumbing)** — a `--single-pass-graph` flag, default off; no
|
|
behavior change.
|
|
- **S2** — collect graph contributions in the detector pass (S1 gate on),
|
|
retire the `assembleProjectCallGraph` re-parse for the no-index path when
|
|
contributions cover the shard's files.
|
|
- **S3** — defer the graph-dependent security candidate expansion + summary
|
|
priming to the post-pass closure; walk from serialized IR.
|
|
- **S4** — fold `primeCrossTUProperties` into the same parse for the
|
|
div/null-deref/overflow/oob corpora.
|
|
|
|
Each slice: focused tests → full suite → fold + yams eval (fingerprints `0fec78e5…`
|
|
/ `247523c5…` EXACT, gold precision/recall 1.0, wall/RSS baselines) → checkpoint.
|