Repository navigation
[vm/aot] IsSmallLeafOrReduction could be cached #64336
Description
Summary
I asked an llm to make dart build faster. It had an interesting finding:
When AOT-compiling dartdev, FlowGraphInliner spends 6.62s of gen_snapshot's 35.95s building and optimizing callee flow graphs that are then thrown away. A large part of that is one specific rejection path that, unlike the other rejection paths in the inliner, doesn't record the result — so the same callee is rebuilt from kernel at every one of its call sites.
Fixing just that one path removes -29.5% of the failed-inlining time (and makes the snapshot slightly smaller, but that seems accidental).
Background: how a callee gets rejected
CallSiteInliner::TryInliningImpl filters candidates in two stages.
Stage 1 (inliner.cc:1229-1249) runs before any graph exists. It reads the cached Function::optimized_instruction_count() / optimized_call_site_count() and calls ShouldWeInline. Cheap.
Stage 2 runs after BuildGraph (kernel → IL), ComputeSSA, and RunInliningPipeline (ConstantPropagation, ApplyClassIds, TypePropagation, ApplyICData, Canonicalize). Two rejections live here:
CollectGraphInfo+ShouldWeInline(inliner.cc:1457-1493). On failure, if the callee exceeded both thresholds, it callsfunction.set_is_inlinable(false)— it memoizes, so this path self-heals.- The
stricter_heuristicgate,IsSmallLeafOrReduction(inliner.cc:1501-1516). On failure it is not cached.
stricter_heuristic (inliner.cc:1751-1754) is on for AOT, -O2, non-always-inline, nesting_depth == 0 — i.e. most AOT static call sites.
So path 2 is the only rejection in the inliner that pays for a full callee graph and then discards the result.
Measurements
Compiling dartdev's kernel with gen_snapshot (ReleaseX64), via --print_precompiler_timings and --print-inlining-tree:
Late IsSmallLeafOrReduction bailouts |
56,215 |
| Distinct functions involved | 10,995 |
| Redundant callee graph builds | 45,220 |
| Time in failed inlining attempts | 6.62 s of 35.95 s gen_snapshot |
Time in Inlining overall |
17.60 s (47% of gen_snapshot) |
Worst repeat offenders:
| Callee | Rebuilt |
|---|---|
_GrowableList. |
2,639× |
StringBuffer.write |
2,118× |
_LinkedHashMapMixin.[]= |
706× |
For scale, Inlining is ~3.5× more expensive than top-level BuildGraph + ComputeSSA + AllocateRegisters + GenerateCode combined, and BuildGraph inside inlining (4.29s) dwarfs BuildGraph for all top-level functions (1.50s).
Why the IsSmallLeafOrReduction verdict can be generalized
IsSmallLeafOrReduction ends in:
if (call_count > 0) {
return instruction_count <= call_site_instructions;
}
return instruction_count <= FLAG_inlining_small_leaf_size_threshold;It is monotone increasing in call_site_instructions. At a call site the budget is static_call->ArgumentCount() + 1 + 1, and ArgumentCount() is bounded by arity, so
(IsGeneric() ? 1 : 0) + NumParameters() + 2
is an upper bound over all call sites of the function. A false there implies false everywhere. (Non-static call sites get call_site_instructions = 0, which is smaller still.)
Proposed fix
The LLM also produced a proposed fix: https://dart-review.googlesource.com/c/sdk/+/552660 (currently WIP). It may well not be the right shape — I'm filing this mostly because the underlying observation looks real, and someone who actually owns the inliner should decide what to do about it.
Record the generalized verdict in a spare bit of Function::state_bits_ (IsNotSmallLeafOrReduction) and bail out in stage 1, before BuildGraph.
With three guards:
- Not recorded, and not applied, when the call site specialized the callee — constant arguments, or omitted optional parameters whose defaults become
Constantstubs. Constant folding would make the graph smaller than the one measured. (Stage 1 already discards its cached counts for the same reason.) - Not recorded when the scan had to guess
kAvgListedMethodSize = 20for a recognized callee that has not been compiled yet, since that estimate can shrink later and would make inlining depend on compilation order. - Read and written only under
stricter_heuristic, which impliesis_aot().state_bits_is a plain non-atomicint8_t, so a JIT write would raceSetWasExecuted/SetProhibitsInstructionHoisting; AOT'sPrecompiler::Iterateis single-threaded.
This is a policy change, not a pure cache
CreateParameterStub (inliner.cc:1123-1144) refines the callee's parameter types with the caller's argument types before the inlining pipeline runs:
param->UpdateType(*CompileType::ComputeRefinedType(param->Type(), argument->Type()));So a callee can genuinely be a small leaf from caller X and not from caller Y, with no constants involved. The guards cover constant-driven specialization but not type-driven specialization. The patch therefore generalizes the first rejecting call site's verdict to the whole function, and inlines slightly less at the margin.
Empirically that is the good direction — the snapshot gets smaller — but it should be reviewed as a heuristic change.
Instrumented counters confirming the mechanism (dartdev.dill):
| Counter | baseline | patched |
|---|---|---|
set_is_inlinable(false) at the late heuristic |
5,393 | 5,393 |
Late IsSmallLeafOrReduction rejections |
57,636 | 30,923 |
| New early rejections from the cached bit | 0 | 26,936 |
The identical 5,393 shows the early bailout does not skip the set_is_inlinable(false) side effect of the late path.
Results
dartdev.dill, ReleaseX64 (gen_snapshot output verified byte-identical across runs):
| baseline | patched | Δ | |
|---|---|---|---|
| Failed-inlining time | 6.62 s | 4.67 s | -29.5% |
Inlining pass total |
17.60 s | 15.65 s | -11.1% |
gen_snapshot total |
35.95 s | 34.00 s | -5.4% |
End-to-end dart compile exe |
59.28 s | 57.33 s | -3.3% |
| Snapshot size | 32,881,440 B | 32,827,080 B | -0.165% |
Golem run over dart and dart-aot on linux-x64, linux-armv8, linux-armv8c, linux-armv7hf — patch 20662 against revision 124434 (Google-internal: https://golem.corp.goog/Revision?repository=dart&revision=124434&patch=20662):
dart-aotlinux-x64RunTimegeomean over 46 suites: -0.38%dart-aotlinux-armv8RunTimegeomean over 25 suites: +0.03%- Built SDK size: -99,776 B
- No significant change replicates across architectures.
Minor, same function
IsSmallLeafOrReduction's inlining_depth parameter is dead — declared, never
read. The CL passes /*inlining_depth=*/0 for documentation only.
Activity
biggs0125 commentedon Sep 23, 2026
@sigurdm Thanks for the proposed fix. Wondering what effect this would have on the golem benchmarks. Would you mind uploading a patch to golem and posting the results here?
@alexmarkov pointed out that every time we do these inline checks we have to do the full optimization pipeline to get the size heuristic for the inline target which is context sensitive. It's worth exploring whether we need that to be context sensitive and then if we don't we could get better caching.
sigurdm commentedon Sep 24, 2026
Thanks! The Golem numbers are in the issue body under "Results" — patch 20662 against revision 124434: https://golem.corp.goog/Revision?repository=dart&revision=124434&patch=20662
Short version:
dart-aotlinux-x64RunTimegeomean over 46 suites: -0.38%dart-aotlinux-armv8RunTimegeomean over 25 suites: +0.03%On context sensitivity: I measured it. On an instrumented
gen_snapshot(no caching change), every stage-2 inlining attempt (i.e. every time the callee graph is built and run through the inlining pipeline) logs the callee, whether the call site passed constants, whether any parameter type was narrowed by the caller's argument type, and the sizes/verdicts computed on that graph. Compilingdartdev:ShouldWeInlineat stage 2: for non-constant call sitesCollectGraphInfoalready reuses the counts cached from whichever graph was measured first. That's a different number from the graph in hand at 33.8% of those sites, but it changes the verdict at only 56 of 174,723 (0.03%). Per callee, the verdict on each site's own graph varies for 39 of 12,627 multi-site callees (30 because of constants, 9 because of types alone).IsSmallLeafOrReduction: 71,532 attempts get as far as this check; 82% fail it. The verdict varies across call sites for 113 of 5,237 multi-site callees: 84 because of constants, 29 because of argument types alone, 0 without any caller info. Compared to the same callee's no-caller-info verdict, 99.4% of sites agree. In the remaining 0.6% (270 sites) caller context makes it pass. It never makes it fail.So context sensitivity changes very few decisions, and constants account for about three quarters of those. Type-only specialization does matter for a handful of callees. The biggest is
_GrowableList.of: among its call sites without constants (all of which have narrowed parameter types), 64 pass the small-leaf check and 392 fail it, so the answer depends on what the caller knows about the argument. A size measured once without caller context, re-measured only when constants are passed, would probably lose those 64.That also showed that the first version of the CL wasn't quite right: it recorded the verdict from type-refined sites too, so it could lose some of those
_GrowableList.ofinlines depending on which caller is seen first. I've updated the CL (patch set 3) to only record it from sites where neither constants nor narrowed parameter types are involved.dartdev, median of 3 interleaved runs:So the stricter version keeps about two thirds of the compile-time win, and most of the size change goes away. That suggests most of the size change came from the type-refined sites. Whole-
gen_snapshotnumbers are too noisy on this machine to separate the two variants. The Golem numbers above are for the first version. I've started a Golem run for the current one against the same revision, and will post the results when it's done: https://golem.corp.goog/Revision?repository=dart&revision=124434&patch=20741Instrumentation diff, analysis script and steps to reproduce: https://gist.github.com/sigurdm/a16c768170e871552a4e604b43965f72
rakudrama commentedon Sep 24, 2026
I'm not so sure about the 'self-heals' comment.
Inlining decisions are compilation-order dependent (in my opinion a bug).
See: #48207
sigurdm commentedon Sep 28, 2026
@rakudrama Good point — by "self-heals" I only meant in terms of compile-time work (it stops rebuilding the callee graph over and over), not that the resulting decisions are order-independent.
Tracing the two examples in #48207, the second one is actually the exact same
CollectGraphInfoblind spot that showed up in thedartdevnumbers above:categorize(1)vscategorize(xx)): Whencategorize(xx)failsShouldWeInlineon both thresholds,set_is_inlinable(false)clearskIsInlinableBit, which is checked at the very top ofTryInliningImplbeforeCountConstants. So one unspecialized call permanently blocks later constant-argument calls (categorize(2)anddemo1'scategorize(1)). (IsNotSmallLeafOrReductionin the CL is only consulted whenconstant_arg_count == 0, so it avoids this.)categorize(g++)wheregisint): Hereconstants_count == 0, soCollectGraphInfotreats the call as unspecialized even thoughCreateParameterStubnarrowedofromObject?tointand folded the graph tosize = 1, call_sites = 0.CollectGraphInfocaches(1, 0)oncategorizeas itsoptimized_instruction_count/optimized_call_site_count.demo2,categorize(xx)(Object?, actual graph size 54, call sites 8) callsCollectGraphInfo(..., force=false), seesoptimized_instruction_count() != 0, and returns the cached(1, 0)instead of measuring the 54-instruction graph in hand (which is why it passesShouldWeInlineand only bails out atIsSmallLeafOrReduction).categorizeitself is compiled as a top-level function betweendemo2anddemo1, andFinalizeGraphcallsCollectGraphInfo(..., force=true)on the unspecialized graph, overwriting the cached counts with(54, 8). Whendemo1runs afterward,categorize(g++)(constant_arg_count == 0) reads(54, 8)at the Stage 1 early heuristic and bails out before building the graph.CollectGraphInfo's cached counts disagreed with the actual graph in hand at 33.8% of non-constant call sites in thedartdevtrace. Passingconstants_count > 0 || param_types_refined_intoCollectGraphInfo(so type-refined calls don't overwrite the unspecialized counts) would avoid poisoningoptimized_instruction_countoncategorize(g++).Note that while guarding
SetIsNotSmallLeafOrReduction(true)withconstants_count == 0 && !param_types_refined_avoids poisoning the cache from a specialized call, reading the bit at Stage 1 (constant_arg_count == 0) still leaves a compilation-order dependence for the 29 callees indartdev(andcategorizein #48207) where type refinement alone flips the verdict: if an unrefinedcategorize(xx)at depth >= 2 runs beforecategorize(g++), the latter will bail out at Stage 1 unless Stage 1 also checks whether any call-site argument has a narrower static type than the declared parameter type.Golem results for Patch Set 4 (patch 20741)
Guarding the cache write with
constants_count == 0 && !param_types_refined_eliminates almost all of the AOT snapshot size difference onSDKArtifactSizescompared to the unguarded version (patch 20662):SDKArtifactSizes)r124434)!param_types_refined_)analysis_serverdds_aotdartdevcdartdartaotruntimedart-aotRunTimegeomeans are within noise (+0.13%across 45 suites onlinux-x64,+0.53%across 18 suites onlinux-armv8).