Garbage Collection Safepoints in LLVM

Status

This document describes a set of extensions to LLVM to support garbagecollection. By now, these mechanisms are well proven with commercial javaimplementation with a fully relocating collector having shipped using them.There are a couple places where bugs might still linger; these are called outbelow.

They are still listed as “experimental” to indicate that no forward or backwardcompatibility guarantees are offered across versions. If your use case is suchthat you need some form of forward compatibility guarantee, please raise theissue on the llvm-dev mailing list.

LLVM still supports an alternate mechanism for conservative garbage collectionsupport using the gcroot intrinsic. The gcroot mechanism is mostly ofhistorical interest at this point with one exception - its implementation ofshadow stacks has been used successfully by a number of language frontends andis still supported.

Overview & Core Concepts

To collect dead objects, garbage collectors must be able to identifyany references to objects contained within executing code, and,depending on the collector, potentially update them. The collectordoes not need this information at all points in code - that would makethe problem much harder - but only at well-defined points in theexecution known as ‘safepoints’ For most collectors, it is sufficientto track at least one copy of each unique pointer value. However, fora collector which wishes to relocate objects directly reachable fromrunning code, a higher standard is required.

One additional challenge is that the compiler may compute intermediateresults (“derived pointers”) which point outside of the allocation oreven into the middle of another allocation. The eventual use of thisintermediate value must yield an address within the bounds of theallocation, but such “exterior derived pointers” may be visible to thecollector. Given this, a garbage collector can not safely rely on theruntime value of an address to indicate the object it is associatedwith. If the garbage collector wishes to move any object, thecompiler must provide a mapping, for each pointer, to an indication ofits allocation.

To simplify the interaction between a collector and the compiled code,most garbage collectors are organized in terms of three abstractions:load barriers, store barriers, and safepoints.

  • A load barrier is a bit of code executed immediately after themachine load instruction, but before any use of the value loaded.Depending on the collector, such a barrier may be needed for allloads, merely loads of a particular type (in the original sourcelanguage), or none at all.
  • Analogously, a store barrier is a code fragment that runsimmediately before the machine store instruction, but after thecomputation of the value stored. The most common use of a storebarrier is to update a ‘card table’ in a generational garbagecollector.
  • A safepoint is a location at which pointers visible to the compiledcode (i.e. currently in registers or on the stack) are allowed tochange. After the safepoint completes, the actual pointer valuemay differ, but the ‘object’ (as seen by the source language)pointed to will not.
Note that the term ‘safepoint’ is somewhat overloaded. It refers toboth the location at which the machine state is parsable and thecoordination protocol involved in bring application threads to apoint at which the collector can safely use that information. Theterm “statepoint” as used in this document refers exclusively to theformer.

This document focuses on the last item - compiler support forsafepoints in generated code. We will assume that an outsidemechanism has decided where to place safepoints. From ourperspective, all safepoints will be function calls. To supportrelocation of objects directly reachable from values in compiled code,the collector must be able to:

  • identify every copy of a pointer (including copies introduced bythe compiler itself) at the safepoint,
  • identify which object each pointer relates to, and
  • potentially update each of those copies.This document describes the mechanism by which an LLVM based compilercan provide this information to a language runtime/collector, andensure that all pointers can be read and updated if desired.

Abstract Machine Model

At a high level, LLVM has been extended to support compiling to an abstractmachine which extends the actual target with a non-integral pointer typesuitable for representing a garbage collected reference to an object. Inparticular, such non-integral pointer type have no defined mapping to aninteger representation. This semantic quirk allows the runtime to pick ainteger mapping for each point in the program allowing relocations of objectswithout visible effects.

This high level abstract machine model is used for most of the optimizer. Asa result, transform passes do not need to be extended to look through explicitrelocation sequence. Before starting code generation, we switchrepresentations to an explicit form. The exact location chosen for loweringis an implementation detail.

Note that most of the value of the abstract machine model comes for collectorswhich need to model potentially relocatable objects. For a compiler whichsupports only a non-relocating collector, you may wish to consider startingwith the fully explicit form.

Warning: There is one currently known semantic hole in the definition ofnon-integral pointers which has not been addressed upstream. To work aroundthis, you need to disable speculation of loads unless the memory type(non-integral pointer vs anything else) is known to unchanged. That is, it isnot safe to speculate a load if doing causes a non-integral pointer value tobe loaded as any other type or vice versa. In practice, this restriction iswell isolated to isSafeToSpeculate in ValueTracking.cpp.

Explicit Representation

A frontend could directly generate this low level explicit form, butdoing so may inhibit optimization. Instead, it is recommended thatcompilers with relocating collectors target the abstract machine model justdescribed.

The heart of the explicit approach is to construct (or rewrite) the IR in amanner where the possible updates performed by the garbage collector areexplicitly visible in the IR. Doing so requires that we:

  • create a new SSA value for each potentially relocated pointer, andensure that no uses of the original (non relocated) value isreachable after the safepoint,
  • specify the relocation in a way which is opaque to the compiler toensure that the optimizer can not introduce new uses of anunrelocated value after a statepoint. This prevents the optimizerfrom performing unsound optimizations.
  • recording a mapping of live pointers (and the allocation they’reassociated with) for each statepoint.At the most abstract level, inserting a safepoint can be thought of asreplacing a call instruction with a call to a multiple return valuefunction which both calls the original target of the call, returnsits result, and returns updated values for any live pointers togarbage collected objects.
Note that the task of identifying all live pointers to garbagecollected values, transforming the IR to expose a pointer giving thebase object for every such live pointer, and inserting all theintrinsics correctly is explicitly out of scope for this document.The recommended approach is to use the utility passes described below.

This abstract function call is concretely represented by a sequence ofintrinsic calls known collectively as a “statepoint relocation sequence”.

Let’s consider a simple call in LLVM IR:

  1. define i8 addrspace(1)* @test1(i8 addrspace(1)* %obj)
  2.        gc "statepoint-example" {
  3.   call void ()* @foo()
  4.   ret i8 addrspace(1)* %obj
  5. }

Depending on our language we may need to allow a safepoint during the executionof foo. If so, we need to let the collector update local values in thecurrent frame. If we don’t, we’ll be accessing a potential invalid referenceonce we eventually return from the call.

In this example, we need to relocate the SSA value %obj. Since we can’tactually change the value in the SSA value %obj, we need to introduce a newSSA value %obj.relocated which represents the potentially changed value of%obj after the safepoint and update any following uses appropriately. Theresulting relocation sequence is:

  1. define i8 addrspace(1)* @test1(i8 addrspace(1)* %obj)
  2.        gc "statepoint-example" {
  3.   %0 = call token (i64, i32, void ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @foo, i32 0, i32 0, i32 0, i32 0, i8 addrspace(1)* %obj)
  4.   %obj.relocated = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %0, i32 7, i32 7)
  5.   ret i8 addrspace(1)* %obj.relocated
  6. }

Ideally, this sequence would have been represented as a M argument, Nreturn value function (where M is the number of values beingrelocated + the original call arguments and N is the original returnvalue + each relocated value), but LLVM does not easily support such arepresentation.

Instead, the statepoint intrinsic marks the actual site of thesafepoint or statepoint. The statepoint returns a token value (whichexists only at compile time). To get back the original return valueof the call, we use the gc.result intrinsic. To get the relocationof each pointer in turn, we use the gc.relocate intrinsic with theappropriate index. Note that both the gc.relocate and gc.result aretied to the statepoint. The combination forms a “statepoint relocationsequence” and represents the entirety of a parseable call or ‘statepoint’.

When lowered, this example would generate the following x86 assembly:

  1.         .globl        test1
  2.         .align        16, 0x90
  3.         pushq %rax
  4.         callq foo
  5. .Ltmp1:
  6.         movq  (%rsp), %rax  # This load is redundant (oops!)
  7.         popq  %rdx
  8.         retq

Each of the potentially relocated values has been spilled to thestack, and a record of that location has been recorded to theStack Map section. If the garbage collectorneeds to update any of these pointers during the call, it knowsexactly what to change.

The relevant parts of the StackMap section for our example are:

  1. # This describes the call site
  2. # Stack Maps: callsite 2882400000
  3.         .quad 2882400000
  4.         .long .Ltmp1-test1
  5.         .short        0
  6. # .. 8 entries skipped ..
  7. # This entry describes the spill slot which is directly addressable
  8. # off RSP with offset 0.  Given the value was spilled with a pushq,
  9. # that makes sense.
  10. # Stack Maps:   Loc 8: Direct RSP     [encoding: .byte 2, .byte 8, .short 7, .int 0]
  11.         .byte 2
  12.         .byte 8
  13.         .short        7
  14.         .long 0

This example was taken from the tests for the RewriteStatepointsForGCutility pass. As such, its full StackMap can be easily examined with thefollowing command.

  1. opt -rewrite-statepoints-for-gc test/Transforms/RewriteStatepointsForGC/basics.ll -S | llc -debug-only=stackmaps

Simplifications for Non-Relocating GCs

Some of the complexity in the previous example is unnecessary for anon-relocating collector. While a non-relocating collector still needs theinformation about which location contain live references, it doesn’t need torepresent explicit relocations. As such, the previously described explicitlowering can be simplified to remove all of the gc.relocate intrinsiccalls and leave uses in terms of the original reference value.

Here’s the explicit lowering for the previous example for a non-relocatingcollector:

  1. define i8 addrspace(1)* @test1(i8 addrspace(1)* %obj)
  2.        gc "statepoint-example" {
  3.   call token (i64, i32, void ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @foo, i32 0, i32 0, i32 0, i32 0, i8 addrspace(1)* %obj)
  4.   ret i8 addrspace(1)* %obj
  5. }

Recording On Stack Regions

In addition to the explicit relocation form previously described, thestatepoint infrastructure also allows the listing of allocas within the gcpointer list. Allocas can be listed with or without additional explicit gcpointer values and relocations.

An alloca in the gc region of the statepoint operand list will cause theaddress of the stack region to be listed in the stackmap for the statepoint.

This mechanism can be used to describe explicit spill slots if desired. Itthen becomes the generator’s responsibility to ensure that values arespill/filled to/from the alloca as needed on either side of the safepoint.Note that there is no way to indicate a corresponding base pointer for suchan explicitly specified spill slot, so usage is restricted to values forwhich the associated collector can derive the object base from the pointeritself.

This mechanism can be used to describe on stack objects containingreferences provided that the collector can map from the location on thestack to a heap map describing the internal layout of the references thecollector needs to process.

WARNING: At the moment, this alternate form is not well exercised. It isrecommended to use this with caution and expect to have to fix a few bugs.In particular, the RewriteStatepointsForGC utility pass does not doanything for allocas today.

Base & Derived Pointers

A “base pointer” is one which points to the starting address of an allocation(object). A “derived pointer” is one which is offset from a base pointer bysome amount. When relocating objects, a garbage collector needs to be ableto relocate each derived pointer associated with an allocation to the sameoffset from the new address.

“Interior derived pointers” remain within the bounds of the allocationthey’re associated with. As a result, the base object can be found atruntime provided the bounds of allocations are known to the runtime system.

“Exterior derived pointers” are outside the bounds of the associated object;they may even fall within another allocations address range. As a result,there is no way for a garbage collector to determine which allocation theyare associated with at runtime and compiler support is needed.

The gc.relocate intrinsic supports an explicit operand for describing theallocation associated with a derived pointer. This operand is frequentlyreferred to as the base operand, but does not strictly speaking have to bea base pointer, but it does need to lie within the bounds of the associatedallocation. Some collectors may require that the operand be an actual basepointer rather than merely an internal derived pointer. Note that duringlowering both the base and derived pointer operands are required to be liveover the associated call safepoint even if the base is otherwise unusedafterwards.

If we extend our previous example to include a pointless derived pointer,we get:

  1. define i8 addrspace(1)* @test1(i8 addrspace(1)* %obj)
  2.        gc "statepoint-example" {
  3.   %gep = getelementptr i8, i8 addrspace(1)* %obj, i64 20000
  4.   %token = call token (i64, i32, void ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @foo, i32 0, i32 0, i32 0, i32 0, i8 addrspace(1)* %obj, i8 addrspace(1)* %gep)
  5.   %obj.relocated = call i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %token, i32 7, i32 7)
  6.   %gep.relocated = call i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %token, i32 7, i32 8)
  7.   %p = getelementptr i8, i8 addrspace(1)* %gep, i64 -20000
  8.   ret i8 addrspace(1)* %p
  9. }

Note that in this example %p and %obj.relocate are the same address and wecould replace one with the other, potentially removing the derived pointerfrom the live set at the safepoint entirely.

GC Transitions

As a practical consideration, many garbage-collected systems allow code that iscollector-aware (“managed code”) to call code that is not collector-aware(“unmanaged code”). It is common that such calls must also be safepoints, sinceit is desirable to allow the collector to run during the execution ofunmanaged code. Furthermore, it is common that coordinating the transition frommanaged to unmanaged code requires extra code generation at the call site toinform the collector of the transition. In order to support these needs, astatepoint may be marked as a GC transition, and data that is necessary toperform the transition (if any) may be provided as additional arguments to thestatepoint.

Note that although in many cases statepoints may be inferred to be GCtransitions based on the function symbols involved (e.g. a call from afunction with GC strategy “foo” to a function with GC strategy “bar”),indirect calls that are also GC transitions must also be supported. Thisrequirement is the driving force behind the decision to require that GCtransitions are explicitly marked.

Let’s revisit the sample given above, this time treating the call to @fooas a GC transition. Depending on our target, the transition code may need toaccess some extra state in order to inform the collector of the transition.Let’s assume a hypothetical GC–somewhat unimaginatively named “hypothetical-gc”–that requires that a TLS variable must be written to before and after a callto unmanaged code. The resulting relocation sequence is:

  1. @flag = thread_local global i32 0, align 4
  2. define i8 addrspace(1) @test1(i8 addrspace(1) %obj)       gc "hypothetical-gc" {
  3.   %0 = call token (i64, i32, void (), i32, i32, …) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void () @foo, i32 0, i32 1, i32 @Flag, i32 0, i8 addrspace(1) %obj)  %obj.relocated = call coldcc i8 addrspace(1) @llvm.experimental.gc.relocate.p1i8(token %0, i32 7, i32 7)  ret i8 addrspace(1)* %obj.relocated}

During lowering, this will result in a instruction selection DAG that lookssomething like:

  1. CALLSEQ_START
  2. ...
  3. GC_TRANSITION_START (lowered i32 *@Flag), SRCVALUE i32* Flag
  4. STATEPOINT
  5. GC_TRANSITION_END (lowered i32 *@Flag), SRCVALUE i32 *Flag
  6. ...
  7. CALLSEQ_END

In order to generate the necessary transition code, the backend for each targetsupported by “hypothetical-gc” must be modified to lower GC_TRANSITION_STARTand GC_TRANSITION_END nodes appropriately when the “hypothetical-gc”strategy is in use for a particular function. Assuming that such lowering hasbeen added for X86, the generated assembly would be:

  1.         .globl        test1
  2.         .align        16, 0x90
  3.         pushq %rax
  4.         movl $1, %fs:Flag@TPOFF
  5.         callq foo
  6.         movl $0, %fs:Flag@TPOFF
  7. .Ltmp1:
  8.         movq  (%rsp), %rax  # This load is redundant (oops!)
  9.         popq  %rdx
  10.         retq

Note that the design as presented above is not fully implemented: in particular,strategy-specific lowering is not present, and all GC transitions are emitted asas single no-op before and after the call instruction. These no-ops are oftenremoved by the backend during dead machine instruction elimination.

Intrinsics

‘llvm.experimental.gc.statepoint’ Intrinsic

Syntax:

  1. declare token
  2.   @llvm.experimental.gc.statepoint(i64 <id>, i32 <num patch bytes>,
  3.                  func_type <target>,
  4.                  i64 <#call args>, i64 <flags>,
  5.                  ... (call parameters),
  6.                  i64 <# transition args>, ... (transition parameters),
  7.                  i64 <# deopt args>, ... (deopt parameters),
  8.                  ... (gc parameters))

Overview:

The statepoint intrinsic represents a call which is parse-able by theruntime.

Operands:

The ‘id’ operand is a constant integer that is reported as the IDfield in the generated stackmap. LLVM does not interpret thisparameter in any way and its meaning is up to the statepoint user todecide. Note that LLVM is free to duplicate code containingstatepoint calls, and this may transform IR that had a unique ‘id’ perlexical call to statepoint to IR that does not.

If ‘num patch bytes’ is non-zero then the call instructioncorresponding to the statepoint is not emitted and LLVM emits ‘numpatch bytes’ bytes of nops in its place. LLVM will emit code toprepare the function arguments and retrieve the function return valuein accordance to the calling convention; the former before the nopsequence and the latter after the nop sequence. It is expected thatthe user will patch over the ‘num patch bytes’ bytes of nops with acalling sequence specific to their runtime before executing thegenerated machine code. There are no guarantees with respect to thealignment of the nop sequence. Unlike Stack maps and patch points in LLVM statepoints donot have a concept of shadow bytes. Note that semantically thestatepoint still represents a call or invoke to ‘target’, and the nopsequence after patching is expected to represent an operationequivalent to a call or invoke to ‘target’.

The ‘target’ operand is the function actually being called. Thetarget can be specified as either a symbolic LLVM function, or as anarbitrary Value of appropriate function type. Note that the functiontype must match the signature of the callee and the types of the ‘callparameters’ arguments.

The ‘#call args’ operand is the number of arguments to the actualcall. It must exactly match the number of arguments passed in the‘call parameters’ variable length section.

The ‘flags’ operand is used to specify extra information about thestatepoint. This is currently only used to mark certain statepointsas GC transitions. This operand is a 64-bit integer with the followinglayout, where bit 0 is the least significant bit:

Bit #Usage
0Set if the statepoint is a GC transition, clearedotherwise.
1-63Reserved for future use; must be cleared.

The ‘call parameters’ arguments are simply the arguments which need tobe passed to the call target. They will be lowered according to thespecified calling convention and otherwise handled like a normal callinstruction. The number of arguments must exactly match what isspecified in ‘# call args’. The types must match the signature of‘target’.

The ‘transition parameters’ arguments contain an arbitrary list ofValues which need to be passed to GC transition code. They will belowered and passed as operands to the appropriate GC_TRANSITION nodesin the selection DAG. It is assumed that these arguments must beavailable before and after (but not necessarily during) the executionof the callee. The ‘# transition args’ field indicates how many operandsare to be interpreted as ‘transition parameters’.

The ‘deopt parameters’ arguments contain an arbitrary list of Valueswhich is meaningful to the runtime. The runtime may read any of thesevalues, but is assumed not to modify them. If the garbage collectormight need to modify one of these values, it must also be listed inthe ‘gc pointer’ argument list. The ‘# deopt args’ field indicateshow many operands are to be interpreted as ‘deopt parameters’.

The ‘gc parameters’ arguments contain every pointer to a garbagecollector object which potentially needs to be updated by the garbagecollector. Note that the argument list must explicitly contain a basepointer for every derived pointer listed. The order of arguments isunimportant. Unlike the other variable length parameter sets, thislist is not length prefixed.

Semantics:

A statepoint is assumed to read and write all memory. As a result,memory operations can not be reordered past a statepoint. It isillegal to mark a statepoint as being either ‘readonly’ or ‘readnone’.

Note that legal IR can not perform any memory operation on a ‘gcpointer’ argument of the statepoint in a location statically reachablefrom the statepoint. Instead, the explicitly relocated value (from agc.relocate) must be used.

‘llvm.experimental.gc.result’ Intrinsic

Syntax:

  1. declare type*
  2.   @llvm.experimental.gc.result(token %statepoint_token)

Overview:

gc.result extracts the result of the original call instructionwhich was replaced by the gc.statepoint. The gc.resultintrinsic is actually a family of three intrinsics due to animplementation limitation. Other than the type of the return value,the semantics are the same.

Operands:

The first and only argument is the gc.statepoint which startsthe safepoint sequence of which this gc.result is a part.Despite the typing of this as a generic token, only the value definedby a gc.statepoint is legal here.

Semantics:

The gc.result represents the return value of the call target ofthe statepoint. The type of the gc.result must exactly matchthe type of the target. If the call target returns void, there willbe no gc.result.

A gc.result is modeled as a ‘readnone’ pure function. It has noside effects since it is just a projection of the return value of theprevious call represented by the gc.statepoint.

‘llvm.experimental.gc.relocate’ Intrinsic

Syntax:

  1. declare <pointer type>
  2.   @llvm.experimental.gc.relocate(token %statepoint_token,
  3.                                  i32 %base_offset,
  4.                                  i32 %pointer_offset)

Overview:

A gc.relocate returns the potentially relocated value of a pointerat the safepoint.

Operands:

The first argument is the gc.statepoint which starts thesafepoint sequence of which this gc.relocation is a part.Despite the typing of this as a generic token, only the value definedby a gc.statepoint is legal here.

The second argument is an index into the statepoints list of argumentswhich specifies the allocation for the pointer being relocated.This index must land within the ‘gc parameter’ section of thestatepoint’s argument list. The associated value must be within theobject with which the pointer being relocated is associated. The optimizeris free to change which interior derived pointer is reported, provided thatit does not replace an actual base pointer with another interior derivedpointer. Collectors are allowed to rely on the base pointer operandremaining an actual base pointer if so constructed.

The third argument is an index into the statepoint’s list of argumentswhich specify the (potentially) derived pointer being relocated. Itis legal for this index to be the same as the second argumentif-and-only-if a base pointer is being relocated. This index must landwithin the ‘gc parameter’ section of the statepoint’s argument list.

Semantics:

The return value of gc.relocate is the potentially relocated valueof the pointer specified by its arguments. It is unspecified how thevalue of the returned pointer relates to the argument to thegc.statepoint other than that a) it points to the same sourcelanguage object with the same offset, and b) the ‘based-on’relationship of the newly relocated pointers is a projection of theunrelocated pointers. In particular, the integer value of the pointerreturned is unspecified.

A gc.relocate is modeled as a readnone pure function. It has noside effects since it is just a way to extract information about workdone during the actual call modeled by the gc.statepoint.

Stack Map Format

Locations for each pointer value which may need read and/or updated bythe runtime or collector are provided in a separate section of thegenerated object file as specified in the PatchPoint documentation.This special section is encoded per theStack Map format.

The general expectation is that a JIT compiler will parse and discard thisformat; it is not particularly memory efficient. If you need an alternateformat (e.g. for an ahead of time compiler), see discussion under:ref: open work items <OpenWork> below.

Each statepoint generates the following Locations:

  • Constant which describes the calling convention of the call target. Thisconstant is a valid calling convention identifier forthe version of LLVM used to generate the stackmap. No additional compatibilityguarantees are made for this constant over what LLVM provides elsewhere w.r.t.these identifiers.
  • Constant which describes the flags passed to the statepoint intrinsic
  • Constant which describes number of following deopt Locations (notoperands)
  • Variable number of Locations, one for each deopt parameter listed inthe IR statepoint (same number as described by previous Constant). Atthe moment, only deopt parameters with a bitwidth of 64 bits or lessare supported. Values of a type larger than 64 bits can be specifiedand reported only if a) the value is constant at the call site, and b)the constant can be represented with less than 64 bits (assuming zeroextension to the original bitwidth).
  • Variable number of relocation records, each of which consists ofexactly two Locations. Relocation records are described in detailbelow.

Each relocation record provides sufficient information for a collector torelocate one or more derived pointers. Each record consists of a pair ofLocations. The second element in the record represents the pointer (orpointers) which need updated. The first element in the record provides apointer to the base of the object with which the pointer(s) being relocated isassociated. This information is required for handling generalized derivedpointers since a pointer may be outside the bounds of the original allocation,but still needs to be relocated with the allocation. Additionally:

  • It is guaranteed that the base pointer must also appear explicitly as arelocation pair if used after the statepoint.
  • There may be fewer relocation records then gc parameters in the IRstatepoint. Each unique pair will occur at least once; duplicatesare possible.
  • The Locations within each record may either be of pointer size or amultiple of pointer size. In the later case, the record must beinterpreted as describing a sequence of pointers and their correspondingbase pointers. If the Location is of size N x sizeof(pointer), thenthere will be N records of one pointer each contained within the Location.Both Locations in a pair can be assumed to be of the same size.

Note that the Locations used in each section may describe the samephysical location. e.g. A stack slot may appear as a deopt location,a gc base pointer, and a gc derived pointer.

The LiveOut section of the StkMapRecord will be empty for a statepointrecord.

Safepoint Semantics & Verification

The fundamental correctness property for the compiled code’scorrectness w.r.t. the garbage collector is a dynamic one. It must bethe case that there is no dynamic trace such that a operationinvolving a potentially relocated pointer is observably-after asafepoint which could relocate it. ‘observably-after’ is this usagemeans that an outside observer could observe this sequence of eventsin a way which precludes the operation being performed before thesafepoint.

To understand why this ‘observable-after’ property is required,consider a null comparison performed on the original copy of arelocated pointer. Assuming that control flow follows the safepoint,there is no way to observe externally whether the null comparison isperformed before or after the safepoint. (Remember, the originalValue is unmodified by the safepoint.) The compiler is free to makeeither scheduling choice.

The actual correctness property implemented is slightly stronger thanthis. We require that there be no static path on which apotentially relocated pointer is ‘observably-after’ it may have beenrelocated. This is slightly stronger than is strictly necessary (andthus may disallow some otherwise valid programs), but greatlysimplifies reasoning about correctness of the compiled code.

By construction, this property will be upheld by the optimizer ifcorrectly established in the source IR. This is a key invariant ofthe design.

The existing IR Verifier pass has been extended to check most of thelocal restrictions on the intrinsics mentioned in their respectivedocumentation. The current implementation in LLVM does not check thekey relocation invariant, but this is ongoing work on developing sucha verifier. Please ask on llvm-dev if you’re interested inexperimenting with the current version.

Utility Passes for Safepoint Insertion

RewriteStatepointsForGC

The pass RewriteStatepointsForGC transforms a function’s IR to lower from theabstract machine model described above to the explicit statepoint model ofrelocations. To do this, it replaces all calls or invokes of functions whichmight contain a safepoint poll with a gc.statepoint and associated fullrelocation sequence, including all required gc.relocates.

Note that by default, this pass only runs for the “statepoint-example” or“core-clr” gc strategies. You will need to add your custom strategy to thiswhitelist or use one of the predefined ones.

As an example, given this code:

  1. define i8 addrspace(1)* @test1(i8 addrspace(1)* %obj)
  2.        gc "statepoint-example" {
  3.   call void @foo()
  4.   ret i8 addrspace(1)* %obj
  5. }

The pass would produce this IR:

  1. define i8 addrspace(1)* @test1(i8 addrspace(1)* %obj)
  2.        gc "statepoint-example" {
  3.   %0 = call token (i64, i32, void ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 2882400000, i32 0, void ()* @foo, i32 0, i32 0, i32 0, i32 5, i32 0, i32 -1, i32 0, i32 0, i32 0, i8 addrspace(1)* %obj)
  4.   %obj.relocated = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %0, i32 12, i32 12)
  5.   ret i8 addrspace(1)* %obj.relocated
  6. }

In the above examples, the addrspace(1) marker on the pointers is the mechanismthat the statepoint-example GC strategy uses to distinguish references fromnon references. The pass assumes that all addrspace(1) pointers are non-integralpointer types. Address space 1 is not globally reserved for this purpose.

This pass can be used an utility function by a language frontend that doesn’twant to manually reason about liveness, base pointers, or relocation whenconstructing IR. As currently implemented, RewriteStatepointsForGC must berun after SSA construction (i.e. mem2ref).

RewriteStatepointsForGC will ensure that appropriate base pointers are listedfor every relocation created. It will do so by duplicating code as needed topropagate the base pointer associated with each pointer being relocated tothe appropriate safepoints. The implementation assumes that the followingIR constructs produce base pointers: loads from the heap, addresses of globalvariables, function arguments, function return values. Constant pointers (suchas null) are also assumed to be base pointers. In practice, this constraintcan be relaxed to producing interior derived pointers provided the targetcollector can find the associated allocation from an arbitrary interiorderived pointer.

By default RewriteStatepointsForGC passes in 0xABCDEF00 as the statepointID and 0 as the number of patchable bytes to the newly constructedgc.statepoint. These values can be configured on a per-callsitebasis using the attributes "statepoint-id" and"statepoint-num-patch-bytes". If a call site is marked with a"statepoint-id" function attribute and its value is a positiveinteger (represented as a string), then that value is used as the IDof the newly constructed gc.statepoint. If a call site is markedwith a "statepoint-num-patch-bytes" function attribute and itsvalue is a positive integer, then that value is used as the ‘num patchbytes’ parameter of the newly constructed gc.statepoint. The"statepoint-id" and "statepoint-num-patch-bytes" attributesare not propagated to the gc.statepoint call or invoke if theycould be successfully parsed.

In practice, RewriteStatepointsForGC should be run much later in the passpipeline, after most optimization is already done. This helps to improvethe quality of the generated code when compiled with garbage collection support.

PlaceSafepoints

The pass PlaceSafepoints inserts safepoint polls sufficient to ensure runningcode checks for a safepoint request on a timely manner. This pass is expectedto be run before RewriteStatepointsForGC and thus does not produce fullrelocation sequences.

As an example, given input IR of the following:

  1. define void @test() gc "statepoint-example" {
  2.   call void @foo()
  3.   ret void
  4. }
  5.  
  6. declare void @do_safepoint()
  7. define void @gc.safepoint_poll() {
  8.   call void @do_safepoint()
  9.   ret void
  10. }

This pass would produce the following IR:

  1. define void @test() gc "statepoint-example" {
  2.   call void @do_safepoint()
  3.   call void @foo()
  4.   ret void
  5. }

In this case, we’ve added an (unconditional) entry safepoint poll. Note thatdespite appearances, the entry poll is not necessarily redundant. We’d have toknow that foo and test were not mutually recursive for the poll to beredundant. In practice, you’d probably want to your poll definition to containa conditional branch of some form.

At the moment, PlaceSafepoints can insert safepoint polls at method entry andloop backedges locations. Extending this to work with return polls would bestraight forward if desired.

PlaceSafepoints includes a number of optimizations to avoid placing safepointpolls at particular sites unless needed to ensure timely execution of a pollunder normal conditions. PlaceSafepoints does not attempt to ensure timelyexecution of a poll under worst case conditions such as heavy system paging.

The implementation of a safepoint poll action is specified by looking up afunction of the name gc.safepoint_poll in the containing Module. The bodyof this function is inserted at each poll site desired. While calls or invokesinside this method are transformed to a gc.statepoints, recursive pollinsertion is not performed.

This pass is useful for any language frontend which only has to supportgarbage collection semantics at safepoints. If you need other abstractframe information at safepoints (e.g. for deoptimization or introspection),you can insert safepoint polls in the frontend. If you have the later case,please ask on llvm-dev for suggestions. There’s been a good amount of workdone on making such a scheme work well in practice which is not yet documentedhere.

Supported Architectures

Support for statepoint generation requires some code for each backend.Today, only X86_64 is supported.

Limitations and Half Baked Ideas

Mixing References and Raw Pointers

Support for languages which allow unmanaged pointers to garbage collectedobjects (i.e. pass a pointer to an object to a C routine) in the abstractmachine model. At the moment, the best idea on how to approach thisinvolves an intrinsic or opaque function which hides the connection betweenthe reference value and the raw pointer. The problem is that having aptrtoint or inttoptr cast (which is common for such use cases) breaks therules used for inferring base pointers for arbitrary references whenlowering out of the abstract model to the explicit physical model. Notethat a frontend which lowers directly to the physical model doesn’t haveany problems here.

Objects on the Stack

As noted above, the explicit lowering supports objects allocated on thestack provided the collector can find a heap map given the stack address.

The missing pieces are a) integration with rewriting (RS4GC) from theabstract machine model and b) support for optionally decomposing on stackobjects so as not to require heap maps for them. The later is requiredfor ease of integration with some collectors.

Lowering Quality and Representation Overhead

The current statepoint lowering is known to be somewhat poor. In the verylong term, we’d like to integrate statepoints with the register allocator;in the near term this is unlikely to happen. We’ve found the quality oflowering to be relatively unimportant as hot-statepoints are almost alwaysinliner bugs.

Concerns have been raised that the statepoint representation results in alarge amount of IR being produced for some examples and that thiscontributes to higher than expected memory usage and compile times. There’sno immediate plans to make changes due to this, but alternate models may beexplored in the future.

Relocations Along Exceptional Edges

Relocations along exceptional paths are currently broken in ToT. Inparticular, there is current no way to represent a rethrow on a path whichalso has relocations. See this llvm-dev discussion for moredetail.

Support for alternate stackmap formats

For some use cases, it isdesirable to directly encode a final memory efficient stackmap format foruse by the runtime. This is particularly relevant for ahead of timecompilers which wish to directly link object files without the need forpost processing of each individual object file. While not implementedtoday for statepoints, there is precedent for a GCStrategy to be able toselect a customer GCMetataPrinter for this purpose. Patches to enablethis functionality upstream are welcome.

Bugs and Enhancements

Currently known bugs and enhancements under consideration can betracked by performing a bugzilla searchfor [Statepoint] in the summary field. When filing new bugs, pleaseuse this tag so that interested parties see the newly filed bug. Aswith most LLVM features, design discussions take place on llvm-dev, and patchesshould be sent to llvm-commits for review.