llvm / llvm/llvm-project

[LoopVectorize] Per-loop DominatorTree verification causes quadratic compile time in assertion builds

Open
#218,487 1 comment 0 reactions 1 assignee Claimed by @loveysuby View on GitHub
slow-compile vectorizers
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

## Summary

In an optimized LLVM build with assertions enabled and
`LLVM_ENABLE_EXPENSIVE_CHECKS=OFF`, `LoopVectorizePass::processLoop()` verifies
the function's whole dominator tree after every loop that is actually
vectorized/interleaved:

```cpp
assert(DT->verify(DominatorTree::VerificationLevel::Fast) &&
"DT not preserved correctly");
```

At llvm-project main commit
[`399a8ce19e2c`](https://github.com/llvm/llvm-project/commit/399a8ce19e2c8b6c5b5916204ab46eab7158cc04),
this is at
[`LoopVectorize.cpp:8302-8303`](https://github.com/llvm/llvm-project/blob/399a8ce19e2c8b6c5b5916204ab46eab7158cc04/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp#L8302-L8303).
For a generated function with many loops, the check is therefore repeated
thousands of times over the same function-scale data structure.

This is separate from the DT verification in
[`LoopVectorizationPlanner::executePlan()`](https://github.com/llvm/llvm-project/blob/399a8ce19e2c8b6c5b5916204ab46eab7158cc04/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp#L5962-L5964),
which is guarded by `#ifdef EXPENSIVE_CHECKS` and is not compiled in the build
measured here.

Moving only the `processLoop()` check to the end of `runImpl()` and executing
it once when `Changed` reduced the end-to-end `default` time of a real
generated workload by 41%, with byte-identical output bitcode, optimization
remarks, and pass statistics.

## Real-workload trigger

The real input is an LLVM bitcode snapshot taken immediately before the first
LoopVectorize invocation while compiling MODNet. Lowering produced one large
generated function, `main_graph_modnet`, with:

- 12,814 basic blocks
- 99,706 LLVM instructions
- 4,861 loops in the LoopInfo forest
- 3,092 loops analyzed by LoopVectorize
- 2,304 loops vectorized

`LoopsVectorized` corresponds to successful `processLoop()` calls reaching the
common exit, so the unconditional `processLoop()` DT check runs 2,304 times in
the standalone pass. The once-per-function candidate runs it once.

For `default`, the counters are 3,114 loops analyzed and 2,327 vectorized,
so the baseline performs 2,327 of these checks.

## Measurements

Configuration:

- LLVM 24.0.0git at `399a8ce19e2c`
- `CMAKE_BUILD_TYPE=Release`
- `LLVM_ENABLE_ASSERTIONS=ON`
- `LLVM_ENABLE_EXPENSIVE_CHECKS=OFF`
- X86 target only
- AMD Ryzen 9 3900X; both variants pinned to CPU 3
- one warm-up per variant/scenario, then three alternating baseline/candidate pairs
- measurements started only after load1 remained below 6

Median values are shown below. Percentage changes are the median of paired
changes.

| Scenario | Wall time | Paired wall change | User CPU | Paired user change | Max RSS |
|---|---:|---:|---:|---:|---:|
| MODNet `loop-vectorize` | 17.74 -> 3.23 s | **-81.8%** | 17.63 -> 3.13 s | **-82.2%** | 147,608 -> 148,004 KiB |
| MODNet `default` | 38.61 -> 22.45 s | **-41.2%** | 38.41 -> 22.24 s | **-41.4%** | 303,852 -> 303,236 KiB |
| Synthetic 800-loop `loop-vectorize` | 0.93 -> 0.50 s | **-47.3%** | 0.83 -> 0.48 s | **-43.4%** | 52,400 -> 53,480 KiB |

The RSS differences are small and inconsistent in direction, so I consider
memory impact neutral.

An independent three-pair measurement at the immediately preceding main pin
`902c28258ab6` reproduced the result: -82.3% standalone, -42.7% `default`,
and -48.0% synthetic wall time. A separate seven-pair run that overlapped a
high-load build was retained but excluded from the conclusion.

## Candidate change

The candidate does not remove DT validation. It changes its granularity from
once per successfully transformed loop to once per changed function, next to
the existing once-per-function `verifyFunction` check:

```diff
@@ -8299,9 +8299,6 @@ bool LoopVectorizePass::processLoop(Loop *L) {
++LoopsVectorized;
}

- assert(DT->verify(DominatorTree::VerificationLevel::Fast) &&
- "DT not preserved correctly");
-
return true;
}

@@ -8369,6 +8366,8 @@ LoopVectorizeResult LoopVectorizePass::runImpl(Function &F) {
// Verify once per function rather than once per processed loop, which would
// make the pass quadratic in the number of loops.
+ assert((!Changed || DT->verify(DominatorTree::VerificationLevel::Fast)) &&
+ "DT not preserved correctly");
assert((!Changed || !verifyFunction(F, &dbgs())) &&
"Invalid IR produced by LoopVectorize");
```

The `executePlan()` check under `EXPENSIVE_CHECKS` is left unchanged.

## Output and test checks

For both baseline and candidate, on the real standalone pass, real
`default`, and synthetic input:

- output bitcode was byte-identical;
- LoopVectorize optimization-remark YAML was byte-identical;
- pass-statistics JSON was byte-identical;
- `-verify-each` passed on the real and synthetic inputs.

On a tests-enabled build at `902c28258ab6`, the candidate also passed the full
`check-llvm-transforms-loopvectorize` target: 878 passed, 501 unsupported in the
X86-only configuration, 0 failed (1,379 discovered). I have not run the full
`check-llvm` suite or CTMark.

## Relevant history

- [PR #114292](https://github.com/llvm/llvm-project/pull/114292) moved the DT
check from an epilogue-specific path to the common end of `processLoop()`, so
it now runs after every successful loop transformation.
- [PR #216448](https://github.com/llvm/llvm-project/pull/216448) moved the
neighboring per-loop `verifyFunction` to the end of `runImpl()` because its
function-wide verification caused quadratic compile time. The DT check was
left in `processLoop()`.
- [Issue #48033](https://github.com/llvm/llvm-project/issues/48033) is a similar
precedent for repeated whole-function verification in SLPVectorizer.

Would moving the DT check once per changed function be the preferred policy,
or should it instead be placed under `EXPENSIVE_CHECKS`? The once-per-function
form preserves an assertion-build invariant check while losing only the exact
per-loop failure locality.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.