Repository navigation
perf(codegen): #8167 leaves 22% on fib40 — the range test is provably unnecessary on a branch that already narrows the parameter #8171
Description
Summary
#8167 recovers 45.3x on fib40 but lands 22% short of the pre-#8033 build. The gap is the range test #8167 must emit, and for this shape the test is provably unnecessary.
Measured locally, same source, same perry-dev archives, /usr/bin/time -l, instructions retired (load-independent):
| build | instructions |
|---|---|
| carrying the #8033 regression | 211.54 G |
| #8167 | 4.67 G |
pre-#8033 (9c1a672ce line) |
3.83 G |
4.67 / 3.83 = 1.22.
Why the test is there, and why it is not needed here
#8167's spec_i32_derived_window is right to be careful. For a raw-i32 parameter n, the window of n - 1 is [-2^31-1, 2^31-2] — one value wider than the slot — so the derived argument is not provably containable and the overlapping case correctly emits a range check with the boxed entry as the cold arm.
But fib's recursive calls sit in the else arm of n < 2. On that edge n >= 2, so n - 1 >= 1 and n - 2 >= 0: both are strictly inside the slot and the test can only ever succeed. The window analysis is currently flow-insensitive — it reads the parameter's declared range and nothing about the branch it is standing in — so it cannot see that.
Two recursive calls per invocation, ~331 M invocations, one range test each: that is the 22%.
What would close it
Narrow the parameter window along a branch condition before computing the derived window. The minimal version is what fib needs: when the call site is dominated by a comparison of the specialized parameter against an integer constant, intersect the parameter's window with the implied half-line for that edge. n < 2 false-edge gives n ∈ [2, 2^31-1], and the existing interval arithmetic then proves containment with no further change.
This composes with #8167 rather than replacing it — the disjoint and overlapping cases still need their current handling for everything the narrowing cannot prove.
Worth checking at the same time
Whether the residual is uniform. fib40 is the extreme case (its entire hot body is the specialized entry), so a shape that only takes the range-checked path occasionally may show far less than 22%. That should be measured on the corpus rather than assumed, and the corpus rows to watch are the ones #8033 hit: tree, interp, shapes, churn, cycles.
Not a blocker for anything
#8167 is merged and is overwhelmingly the right change — 45.3x, byte-exact output, clone self-recursing with zero dynamic helpers in it. This is the last 22%, filed so it does not get lost now that the headline number looks good.
Activity
proggeramlug commentedon Aug 16, 2026
Closing: the number in this issue is right, the attribution is wrong. The range test costs zero instructions.
Method — the emitted module IR from
--trace llvm, with the wholespec_i32_call.{fast,fallback,merge}diamond replaced by a directsub i32+ call, both variants pushed through perry's exact pipeline (Homebrew LLVM 22.1.4, the version perry links:function(mem2reg,sccp),rewrite-statepoints-for-gcthendefault<O3>,llc -O3 -mcpu=apple-m1).The two instruction streams are byte-identical.
default<O3>already folds thefcmp oge/fcmp olepair, thefptosi/sitofpround trip, and the entire boxed fallback arm. The shipped hot loop contains no range test at all:16 instructions internal / 12 leaf x 165.58 M invocations each = 4.636 G, against a measured 4.66 G. The budget is fully accounted for with the guard contributing 0.000 G.
So do not build the
dominating_boundthreading or theFnCtxbranch-condition stack. That is M-sized work against a provably zero-cost target, and it carries the #7846/#8033 trap (the narrowing must key off the branch condition's own SSA operand, never a declared type) for no return.The 22% is real and is a different defect. It is the same defect as #8175's 93%, and neither issue names it: the i32 parameter representation defeats LLVM's shrink-wrapping, so the ~165 M leaf invocations each execute a 48-byte frame save/restore they never use.
subs w0,w0,#1fuses then<2test withn-1and clobbersw0in the entry block, so the leaf must readnback fromx19— a callee-saved def in the entry block, which pins the save point and blocks shrink-wrapping.Measured on the quiet M1 mini, best-of-5, all producing 102334155: the f64-parameter shape (i.e. pre-#8033, which does shrink-wrap) gives 3.818 G / 0.39 s against main's 4.660 G / 0.75 s. 4.646/3.818 = 1.217 — this issue's 22%, reproduced exactly and independently. The same row gives 0.75/0.39 = 1.92, which is #8175's "+93.2%".
Re-scoped in #8175, which now carries the mechanism and the prize. Closing this one.