LateLowerGCFrame

Julia's LateLowerGCFrame pass makes the garbage collector's roots explicit. Julia's code generator keeps objects in tracked pointers (address space 10) and pointers derived from them (11 to 13), and leaves it to this pass to make sure that every object that is still needed at a safepoint (a call that may run the GC) is in a GC frame, an array of roots that the function pushes onto its task's GC stack. The pass

1. scans each function for the definitions and uses of tracked values and for the safepoints (calls that may allocate or otherwise reach the GC), numbering every tracked value, and lifting selects and phis of derived pointers to selects and phis of their base objects;
2. computes which values are live at each safepoint, and leaves out the ones kept alive by other live values (a value loaded from immutable memory of a live object, a constant, an argument);
3. colours the values that are live at the same safepoints with different frame slots;
4. creates the frame (julia.new_gc_frame, julia.push_gc_frame, julia.pop_gc_frame), stores the values to their slots before the safepoints they need to survive, and moves allocas of tracked pointers into the frame (julia.get_gc_frame_slot);
5. cleans up: lowers allocations (julia.gc_alloc_obj to julia.gc_alloc_bytes and a store of the type tag; julia.gc_alloc_memory to the same, or to a call of the runtime, followed by the initialization of the Memory's header), julia.typeof, write barriers, jlcalls (julia.call*), calls with a gc-transition bundle (switching the thread to the GC-safe state around them), julia.pointer_from_objref and julia.gc_loaded, and removes the metadata, intrinsics and operand bundles that only hold before this pass.

FinalLowerGC then lowers the frame intrinsics and julia.gc_alloc_bytes to Julia's runtime.

jl-late-lower-gc-frame (JuliaIR.LateLowerGCFramePass) ports the pass for the IR of every Julia version from 1.10 on, and jlopt runs it for Julia's name of the pass (LateLowerGCFrame). It is a required function pass. The code keeps the names and the structure of the C++ (local_scan for LocalScan, compute_liveness! for ComputeLiveness, color_roots for ColorRoots, place_roots_and_update_calls! for PlaceRootsAndUpdateCalls, cleanup_ir! for CleanupIR, ...), so that both can be read side by side.

jl-late-gc-cleanup (JuliaIR.LateGCCleanupPass) runs the same code on functions without a GC frame, as GPU back-ends emit them, after checking an input contract (see below).

What changes between Julia versions

The pass follows the C++ pass of the running Julia's version. The differences between versions are fields of JuliaIR.Dialect:

From Julia 1.14 on, the gc_barrier policy of the dialect selects the write-barrier build configuration: with :snapshot (or :snapshot_field_precise), barriers are never elided. Builds with MMTk are not supported.

Julia's runtime

Lowering allocations and GC state transitions needs the layout of Julia's runtime structures: where a task keeps its thread-local state (task_ptls, and task_gcstack for Julia 1.12's transitions), and where that state keeps the safepoint page (tls_safepoint) and the GC state (tls_gc_state). The pass takes them from the running Julia (see Runtime facts), only for functions that need them (the GPU cleanup never does), or from the pass options of the same names (task-ptls=168, ...), which override them. Like the C++ pass, which compiles them in, it uses them whatever the module's target is.

The GPU cleanup: jl-late-gc-cleanup

Code for GPUs and other targets without Julia's runtime has no GC stack, so only the cleanup applies to it. GPUCompiler runs LateLowerGCFrame for every target, after replacing allocations and removing write barriers itself, and some back-ends depend on the cleanup (see the Metal example below). jl-late-gc-cleanup checks that a function only contains what the cleanup handles without Julia's runtime and then runs the general pass on it; a function that breaks the contract makes it throw a JuliaIR.UnsupportedInputError, which lists every offending construct with its source location, before anything in the function is changed. Functions that the general pass skips (thunks) are checked too.

Input contract

The input is a function in the IR dialect of the running Julia, after the back-end's own GC lowering (GPUCompiler's GPULowerGCFrame and GPULowerPTLS). The function must not contain:

The function may contain the following, which the pass rewrites:

GPUCompiler's IR validator relies on the jlcall lowering: it reports dynamic calls by finding calls of jl_apply_generic and jl_invoke, which only exist after it.

Example: why Metal needs the cleanup

Julia passes immutable aggregates to functions by pointer and marks loads from such arguments as constant (!invariant.load and an immutable jtbaa_const tag). That is only true until the function is inlined into a caller that passes a stack slot: LLVM then believes the load cannot see the caller's store, and GVN folds it to undef (JuliaLang/julia#44285):

define internal i64 @getfield(ptr addrspace(11) %agg) {
  %v = load i64, ptr addrspace(11) %agg, !tbaa !const, !invariant.load !{}
  ret i64 %v
}

define i64 @kernel(i64 %x) {
  %slot = alloca i64
  store i64 %x, ptr %slot
  %p = addrspacecast ptr %slot to ptr addrspace(11)
  %r = call i64 @getfield(ptr addrspace(11) %p)   ; inline, then GVN: ret i64 undef
  ret i64 %r
}

GPUCompiler's Metal back-end inlines device code after optimization, so it relies on the cleanup having removed this metadata first. test/lit/late-gc-cleanup.ll checks both outcomes.

Differences with Julia's C++ pass

Deliberate differences, on the IR of every Julia version:

• Calls without Julia's operand bundles are kept in place. The C++ pass recreates them even when they need no changes.
• Operand bundles that are not Julia's are kept, also on the calls that replace jlcalls and allocations. The C++ pass removes every operand bundle from a call that has one, including, e.g., align assumptions and convergence control tokens.
• The GC state byte of a thread is accessed with an alignment that holds: the C++ pass claims pointer alignment, which the byte at offset 25 of Julia 1.12 and 1.13 doesn't have (it does at 1.14's offset 128).
• Allocas that are moved into the GC frame get their slots in the order of the function. The C++ pass iterates over a hash map keyed by the allocas' addresses, so its order changes from run to run (upstream's tests check these slots with CHECK-DAG).
• What the C++ pass takes from the host (sizeof(void*), for alignments, for the size of frame slots, and for the layout of a Memory's header and the size of the largest pooled object) comes from the module's data layout. This also supports targets with a different pointer size.
• The C++ pass declares ijl_gc_small_alloc in every module it runs on (Julia 1.12 and later); jl-late-gc-cleanup does not, since GPU modules don't link Julia's runtime.
• For calls marked julia.safepoint (Julia 1.14 and later), the memory effects of the function they call are dropped too, not only those of the call: LLVM combines both, so with the C++ pass a callee declared memory(none) still lets DSE delete the root stored for the call (a bug of the C++ pass, reproduced on Julia 1.14 with function(LateLowerGCFrame,FinalLowerGC,sroa,dse,instcombine)).
• Inputs on which the C++ pass crashes or asserts (an unexpected user of an alloca moved into the frame, a returned-roots argument that isn't an alloca, an insertelement of a tracked pointer at a dynamic index) make the port throw an error.
• The pass reports the control-flow graph as preserved unless it lowered a write barrier. The C++ pass of Julia 1.12 and older reports whether its cleanup changed something, and that of 1.12 and 1.13 reports the control-flow graph as changed whenever julia.gc_alloc_bytes is used (a hook for MMTk that does nothing in stock builds).

Fixes and features of later Julia versions that are applied to the IR of every version (none of them changes the output on IR that the older C++ pass handles):

• Julia 1.14: extractelements of tracked or derived pointers at a dynamic index are lifted (the C++ pass of 1.13 and older crashes).
• Julia 1.13: allocas that rooted pointers are stored to are found through selects and phis, as are the allocas of returned roots, and a trampoline that forwards its own sret argument is accepted (1.12 and older handle direct allocas only, and crash otherwise); calls that can return twice are always safepoints (1.12 and older skip the ones without memory effects, then fail when colouring); allocas with an alignment larger than 16 bytes are moved into the frame at an aligned slot, and the frame is aligned accordingly (1.12 and older assert).
• Julia 1.12: llvm.vector.extract and llvm.vector.insert of tracked pointers are handled (1.10 and 1.11 number them as new values).
• Julia 1.11: aggregates that contain pointers in address space 13 are recognized as loaded values, and selects and phis of aggregates of derived pointers are lifted (1.10 only handles vectors).

The pass also handles, on the IR of every version, constructs that only Julia 1.14 and later emit, so older versions' IR doesn't contain them: calls marked julia.safepoint are safepoints whatever their memory effects claim, and their memory effects are dropped (with LLVM 15, the attributes that LLVM 16 replaced by memory); julia.blackbox is lowered; thunks are skipped; julia.gc_alloc_obj calls with julia.gc_alloc_ptr_offsets or julia.gc_alloc_zeroinit bundles initialize the new object, and keep julia.reset_region metadata; julia.gc_alloc_zeroinit_indirect bundles are discharged.

What depends on the LLVM library rather than on the Julia version follows the library: the position of the pass-through operand of llvm.masked.load and llvm.masked.gather (LLVM 22 dropped their alignment operand), the alignment LLVM infers for a null type tag (LLVM 22 stopped inferring it), and the spelling of memory effects (attributes before LLVM 16).