Fil-C · FilPizlonator · alias analysis · commit 0a2f0f6 on mbrock/fil-c frame-alias-scope, based on pizlonator/fil-c deluge 9d1ed206

Fil-C frame accesses in their own alias scope

Every function's Fil-C frame is linked into the thread's frame list, so as far as LLVM knows it has escaped to the whole program. Each store that records a pointer's lower into the frame therefore may alias every other load and store — and since those stores precede almost every safepoint, object header loads can never be reused across them. One alias scope tells LLVM what Fil-C already knows: only calls can touch a frame. So calls are the one thing the scope leaves out.

Background: the frame, and why it escapes

frame: The per-function Fil-C record the pass allocates (Frame, from its alloca). It holds the lowers that root the function's live pointers for the GC, plus the current origin for diagnostics.
lower: The capability half of a pointer: it names the object (and its bounds and aux). Recording a pointer's lower in the frame is how the GC knows the object is still reachable.
safepoint: A place where the GC or runtime may take over — a call, a pollcheck, a syscall wrapped in exit/enter. Before each one, the pass stores the lowers of everything live into the frame.
header load: Loading an object's upper bound or aux pointer from its header, to check an access. These are the loads Fil-C emits constantly — and wants to CSE.
alias scope: LLVM metadata: !alias.scope on an access says “this access is in scope S”; !noalias listing S on another access says “this one never aliases anything in S”. Alias analysis may then move, merge and reuse accesses across each other.

On entry, each function links its frame into the thread's frame list, so that the GC, stack traces and unwinding can walk it. That is necessary — and it means the frame's address is handed to runtime code the optimizer cannot see into. In LLVM's terms the frame escapes. From then on, alias analysis must assume that any pointer it cannot fully account for might point into the frame, and vice versa: a store to the frame might be a store to anything. Conservative, sound — and, for a pass that stores to the frame before nearly every safepoint, devastating for the loads in between.

The symptom: the same upper bound, loaded 14 times

Consider one pointer checked several times in a row, with frame stores in between (this is the shape of PHP 8.5's ADD handler, thinned down). Each check wants the object's upper bound. Each frame store might, for all LLVM knows, be a store to that header. So no load can be reused across a frame store, and the upper bound is fetched again. In the real handler: 14 loads of one object's upper bound. With the frame stores known not to alias the header: 2.

Try it. A thinned-down stretch of one handler. Toggle the frame scope and watch which header loads the optimizer may reuse. Note what happens at the call either way.

Schematic, after the pass. The point is not the exact count — it is that only the call, never a frame store, forces a reload.

The change: one scope for the frame, none for calls

After lowering each function, a new tagFrameAccesses walks its loads and stores once. Those whose underlying object is the frame alloca get a single module-wide !alias.scope; every other load and store gets that scope appended to its !noalias list. That is the whole mechanism — fifty lines, metadata only, no IR reshaping:

// FilPizlonator.cpp, condensed from the commit
+  void tagFrameAccesses() {
+    if (!frameAliasScope)              // -filc-frame-alias-scope=0
+      return;
+    if (!FrameScopeList) {             // one scope, module-wide
+      MDBuilder MDB(C);
+      MDNode* Domain = MDB.createAnonymousAliasScopeDomain("filc_frame_domain");
+      MDNode* Scope  = MDB.createAnonymousAliasScope(Domain, "filc_frame");
+      FrameScopeList = MDNode::get(C, { Scope });
+    }
+    for (BasicBlock& BB : *NewF)
+      for (Instruction& I : BB) {
+        Value* Ptr;                   // loads and stores only —
+        if (LoadInst* LI = dyn_cast<LoadInst>(&I))        Ptr = LI->getPointerOperand();
+        else if (StoreInst* SI = dyn_cast<StoreInst>(&I)) Ptr = SI->getPointerOperand();
+        else continue;                // calls are never tagged
+        if (getUnderlyingObject(Ptr, 0) == Frame)
+          I.setMetadata(MD_alias_scope, FrameScopeList);
+        else
+          I.setMetadata(MD_noalias, concatenate(I.getMetadata(MD_noalias), FrameScopeList));
+      }
+  }
  // called once, right after the function is lowered:
+        tagFrameAccesses();

The one deliberate omission is the load-bearing part: calls get no metadata. A call still reads and clobbers every frame, exactly as before. Header loads are freed from frame stores, not from calls — a call can still collect, free the object, and change what the next header load must see.

Why this is sound

The claim the metadata makes is narrow: no load or store in user code ever accesses a frame, except the pass's own frame accesses. Three facts support it:

Who can touch a frame. The metadata only separates the top-left box from the bottom-right one; the top-right path goes through calls, which stay untagged barriers.

The runtime only looks at a frame from inside a call. GC handshakes, exit/enter around syscalls, stack traces, setjmp/longjmp and unwinding all happen while control is inside a runtime call. Since calls are untagged, they remain full barriers: no frame access is moved, merged or dropped across a call, and no other access is either. The second return of setjmp in particular relies on _setjmp staying an opaque call that may write the frame — it does.
User code can learn a frame's address but never gets a capability for it. __builtin_frame_address and friends hand out a bare address. Without a capability, any load or store through it traps rather than accessing the frame — so there is no user access for the metadata to be wrong about. The framealiasaddress test exercises exactly this, including laundering the address through a phi and an integer round trip.
The pass reaches a frame only through GEPs of its own alloca. That is what getUnderlyingObject(Ptr) == Frame checks, and it stays true after inlining, which is why one module-wide scope for all frames is sound rather than one scope per function.

Two constraints are worth stating plainly, because breaking either would break the argument:

Tagging runs once, on freshly lowered code — immediately after lowering, before any further optimization. Running it later, after native frame observers (runtime helpers that read top_frame) had been inlined into a function, would mark their frame-derived loads !noalias with the frame. It must not be re-run.
Calls must stay untagged. This is not decorative caution: tagging calls as well makes framealiasscope, framealiasnonlocal and the existing musttailroot crash at -O2, which is a useful check that the tests actually cover the distinction.

And it is all switchable: -filc-frame-alias-scope=0 restores today's behaviour exactly, since the change is metadata only.

Tests

framealiasscope: frame roots across opaque calls that collect — in a loop, after inlining, and with many adjacent slots.
framealiasthreads: roots held while another thread collects during a pollchecked loop, a blocking read, and signal handlers.
framealiasnonlocal (C++): setjmp loops that collect after every longjmp, kept and demoted musttails, and an unwinding destructor that collects while an exception crosses a frame holding the only reference.
framealiasaddress: a frame address laundered through a phi and an integer still traps on use.

As noted above, the tests catch the obvious wrong version: tagging calls too makes three of them crash at -O2.

Verification, with its limits stated

Verified on deluge 9d1ed206 with a dev compiler built from this branch. There is no deluge build of the runtime in that environment, so tests ran against filnix's staging runtime, which merges an earlier deluge. That runtime predates deluge's filc_jmp_buf_recreate, so tests that call setjmp compile but do not link — the same with the option on or off.

framealiasscope, framealiasthreads, framealiasaddress and musttailroot pass at -O0, -O2 and -O3. framealiasnonlocal compiles there; it uses setjmp, so it could not run there, but passed on the staging toolchain, where compiler and runtime match.
Every single-file test in filc/tests (6,616), compiled at its manifest level with -filc-frame-alias-scope=1 and =0, gives the same exit status and safety-error count both ways. Two tests segfaulted once in that run — one with the option on, one off — then passed 8 of 8 runs each way.
One wart in framealiasaddress: only the frame address goes through the integer round trip. At -O0 a round trip also drops a heap pointer's capability, so laundering both would make the test trap before it ever reached the frame.

Effect

On PHP 8.5's interpreter, the scope removes 0.2–7.5% of instructions in handler micro-benchmarks (the spread is per-handler: the more checks between safepoints, the more there was to save; the ADD handler's 14 upper-bound loads are the extreme). Filnix's staging toolchain has carried it since 22 October, building and testing the PHP 8.5 world: 1,222 PHP tests, 0 failures.

One commit for pizlonator/fil-c deluge: llvm/lib/Transforms/Instrumentation/FilPizlonator.cpp (+52) and four test directories, 0a2f0f6. Filnix's staging toolchain has carried the same change since 5dd226b. This page was written for review and is not part of the patch.