Frame slot coloring at -O0: from cubic to near‑linear
At -O0, FilPizlonator spent 48 seconds on one 160-block function. This change brings that down to 0.66 seconds, and the stack frames it produces are exactly the same.
-O0 (replayed at 10× speed)The problem
A JIT that prints its traces as C produces long, branchy functions: check a type, check another, add with an overflow check, call a helper, repeat. We hit this compiling PHP's opcache JIT output with Fil-C, much as Emacs' native compiler works on Fil-C. At -O1 such a function compiles in well under a second. At -O0, doubling its size made the compile roughly ten times slower: 0.8 s at 40 blocks, 4.7 s at 80, 48 s at 160, and 597 s and 2.8 GB at 300.
The profile was lopsided. At 80 blocks, 99.6% of the compile was in FilPizlonator, and most of that was in one function, computeFrameIndexMap.
What that function does
Every Fil-C function has a frame with an array of slots (lowers[]). The function keeps the capability of each pointer it holds in a slot, so the garbage collector can find it. Two pointers can share a slot if they are never live at the same time. computeFrameIndexMap picks a slot for each pointer in three steps:
- Walk the function backward to find where each pointer is live.
- Record a conflict between every two pointers that are live at the same time.
- Go through the pointers in program order. Place each one in the lowest slot that none of its already-placed conflicts holds.
This is greedy graph coloring, with slots as the colors. The rest of the page uses these words:
- local
- A small stack variable (
alloca) that doesn't escape. It keeps its pointer in a slot too. - always-live local
- A local with no lifetime markers, which the pass treats as live throughout the function. In the code:
AlwaysLive. - conflict
- Two pointers live at once, which therefore need different slots. In the code: an interference edge.
- place
- Choose the slot for one pointer. In the code: color.
Why -O0 makes it cubic
Lifetime markers (llvm.lifetime.start and .end) tell the pass where a local is in use. Clang emits none at -O0, so every local is always-live. The old code handled always-live locals in the simplest correct way: it added each one to the live set of every block. As a result, each always-live local conflicts with every other local and with every pointer in the function.
Say there are L always-live locals and P pointer values:
- Recording takes about L·(L/2 + P) conflicts, each stored twice in a hash set.
- Placing a pointer tries slot 0, then 1, then 2, and so on, and the locals hold the first L slots. For each slot it tries, the old code scanned the pointer's whole conflict list, which has at least L entries. That comes to about P·L²/2 checks.
The 160-block function has L = 803 and P = 4,647. That is about 4 million conflicts and 1.5 billion checks.
The idea: these conflicts follow a pattern, so don't record them
All locals are declared at the top of the function, in its entry block. An always-live local is live everywhere below its own declaration. So at any point in the function, the live always-live locals are simply the first k of them in declaration order, where k is how many were declared above that point. Past the entry block, that means all of them.
Placement visits the entry block first, in the same order. When it reaches a pointer, the always-live locals it has already placed are exactly the ones that were live where that pointer was defined. So every pointer just has to avoid the slots of all always-live locals placed so far. Those slots form one shared, growing taken set, which replaces millions of recorded conflicts.
Nothing ever leaves the taken set, so it can remember its first free slot. The search for a slot starts there.
Step through it
The widget below is a small program shaped like a JIT trace. It runs JavaScript models of the old and new code side by side. With -O0 and before, the locals (amber) gain conflicts with everything. Switch to after and the same placements come out with almost no conflicts recorded. With -O2, lifetime markers keep the conflicts few, and the two versions do similar work.
Placing faster
The new code also changes how one slot is chosen. The old code rescanned the conflict list for every slot it tried. The new code walks the list once and marks each conflict's slot. Then it takes the first slot, starting at the first free one, that is neither taken nor marked. A placement now costs the length of the list plus the distance to the answer, rather than their product.
- for (size_t FrameIndex = NumSpecialFrameObjects; ; FrameIndex++) { - bool Ok = true; - for (ValuePtr AIP : Adjacency) - if (FrameIndexMap.count(AIP) && FrameIndexMap[AIP].Index == FrameIndex) { Ok = false; break; } - if (Ok) { ... break; } - } + Pick++; + for (auto& Neighbor : Adjacency) // once per placement + if (placed) NeighborPick[its slot] = Pick; + for (size_t Index = std::max(Begin, Taken.FirstMissing); ; Index++) + if (!Taken.contains(Index) && NeighborPick[Index] != Pick) + return Index;
Two edge cases
A local that starts late
A local with lifetime markers isn't always-live. Suppose it is declared before an always-live local a, but its lifetime.start comes after a. Then the two conflict. The marked local is placed first, though, so when a is placed it can't know to avoid it. In this one case the new code records the conflicts explicitly. Choose late start above to see them in red. It happened in 1,430 functions of the test corpus.
Locals whose address is taken
These locals (LocalExplicit) get their slots in a separate area after the frame. An always-live one must not share a slot with any other, or the collector only sees whichever was written last. The old code recorded that as a conflict between every pair. The new code uses the same trick with two sets: the slots of all such locals placed so far, and the slots of the always-live ones among them. An always-live local avoids the first set. Any other local avoids the second set, plus its ordinary conflicts.
Why the frames are identical
The claim is this: before each placement, the old and new code rule out exactly the same slots. Both then take the lowest slot that remains, so by induction over the placement order, every pointer ends up in the same slot. The pattern above, plus the late-start case, is what makes the claim true. A debug assertion checks the pattern in every compile.
- Compared directly. A test compiler ran both versions on every function. It compared every slot, the frame size, the size of the separate area, and the setjmp and varargs slots. The inputs were
filc/testsat-O0, at-O2, and at-O1with optimization passes disabled, plus generated traces and handwritten edge cases. Result: 44,006 functions, 0 differences, frames up to 487 slots. - Reviewed. An independent review checked the argument and found no counterexample. It also caught two problems in a first draft, both since fixed:
BitVectorreturns anintindex, and copying a set for every pointer brought back quadratic work. - On upstream. The commit applies cleanly to
delugeat9d1ed206. With assertions on, 7,836 files fromfilc/testsbuilt at-O0and-O2without tripping the assertion. The only crashes were thebadasmtests, which are meant to fail.
Results
The JavaScript model from the widget, run on larger trace-shaped programs (5 locals and 29 pointers per block, as in the real -O0 code), shows the same shape. It counts the work each version does and checks that the placements match.
What's left
With the fix, -O0 is within about 2× of -O1 and grows only slightly faster than linearly. No single hot spot remains. The largest, at 600 blocks, is check scheduling (scheduleChecks, about 16%). It is left alone because changing it could move checks. The commit also makes one small unrelated change: it passes CanonicalPtrLiveAtTail by reference instead of copying it.