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:

1. create a new SSA value for each potentially relocated pointer, andensure that no uses of the original (non relocated) value isreachable after the safepoint,

2. 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.

3. 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 theutility 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:

declarevoid@foo()defineptraddrspace(1)@test1(ptraddrspace(1)%obj)gc"statepoint-example"{callvoid@foo()retptraddrspace(1)%obj}

Depending on our language we may need to allow a safepoint during the executionoffoo. 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:

defineptraddrspace(1)@test(ptraddrspace(1)%obj)gc"statepoint-example"{%safepoint=calltoken(i64,i32,ptr,i32,i32,...)@llvm.experimental.gc.statepoint.p0f_isVoidf(i640,i320,ptrelementtype(void())@foo,i320,i320,i320,i320)["gc-live"(ptraddrspace(1)%obj)]%obj.relocated=callptraddrspace(1)@llvm.experimental.gc.relocate.p1(token%safepoint,i320,i320)retptraddrspace(1)%obj.relocated}

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 thegc.result intrinsic. To get the relocationof each pointer in turn, we use thegc.relocate intrinsic with theappropriate index. Note that both thegc.relocate andgc.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:

.globltest1.align16,0x90pushq%raxcallqfoo.Ltmp1:movq(%rsp),%rax# This load is redundant (oops!)popq%rdxretq

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:

# This describes the call site# Stack Maps: callsite 2882400000.quad2882400000.long.Ltmp1-test1.short0# .. 8 entries skipped ..# This entry describes the spill slot which is directly addressable# off RSP with offset 0.  Given the value was spilled with a pushq,# that makes sense.# Stack Maps:   Loc 8: Direct RSP     [encoding: .byte 2, .byte 8, .short 7, .int 0].byte2.byte8.short7.long0

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

opt-rewrite-statepoints-for-gctest/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 thegc.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:

definevoid@manual_frame(ptr%a,ptr%b)gc"statepoint-example"{%alloca=allocaptr%allocb=allocaptrstoreptr%a,ptr%allocastoreptr%b,ptr%allocbcalltoken(i64,i32,ptr,i32,i32,...)@llvm.experimental.gc.statepoint.p0(i640,i320,ptrelementtype(void())@func,i320,i320,i320,i320)["gc-live"(ptr%alloca,ptr%allocb)]retvoid}

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 withinanother 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.

Thegc.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.

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:

@flag=thread_localglobali320,align4definei8addrspace(1)*@test1(i8addrspace(1)*%obj)gc"hypothetical-gc"{%0=calltoken(i64,i32,void()*,i32,i32,...)*@llvm.experimental.gc.statepoint.p0f_isVoidf(i640,i320,void()*@foo,i320,i321,i32*@Flag,i320,i8addrspace(1)*%obj)%obj.relocated=callcoldcci8addrspace(1)*@llvm.experimental.gc.relocate.p1i8(token%0,i327,i327)reti8addrspace(1)*%obj.relocated}

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

CALLSEQ_START...GC_TRANSITION_START(loweredi32*@Flag),SRCVALUEi32*FlagSTATEPOINTGC_TRANSITION_END(loweredi32*@Flag),SRCVALUEi32*Flag...CALLSEQ_END

In order to generate the necessary transition code, the backend for each targetsupported by “hypothetical-gc” must be modified to lowerGC_TRANSITION_STARTandGC_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:

.globltest1.align16,0x90pushq%raxmovl$1,%fs:Flag@TPOFFcallqfoomovl$0,%fs:Flag@TPOFF.Ltmp1:movq(%rsp),%rax# This load is redundant (oops!)popq%rdxretq

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.

Before the abstract machine model is lowered to the explicit statepoint modelof relocations by theRewriteStatepointsForGC pass it is possible forany derived pointer to get its base pointer and offset from the base pointerby using thegc.get.pointer.base and thegc.get.pointer.offsetintrinsics respectively. These intrinsics are inlined by theRewriteStatepointsForGC pass and must not be used after this pass.

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 agc.statepoint and associated fullrelocation sequence, including all requiredgc.relocates.

This pass only applies to GCStrategy instances where theUseRS4GC flagis set. The two builtin GC strategies with this set are the“statepoint-example” and “coreclr” strategies.

As an example, given this code:

defineptraddrspace(1)@test1(ptraddrspace(1)%obj)gc"statepoint-example"{callvoid@foo()retptraddrspace(1)%obj}

The pass would produce this IR:

defineptraddrspace(1)@test_rs4gc(ptraddrspace(1)%obj)gc"statepoint-example"{%statepoint_token=calltoken(i64,i32,ptr,i32,i32,...)@llvm.experimental.gc.statepoint.p0(i642882400000,i320,ptrelementtype(void())@foo,i320,i320,i320,i320)["gc-live"(ptraddrspace(1)%obj)]%obj.relocated=callcoldccptraddrspace(1)@llvm.experimental.gc.relocate.p1(token%statepoint_token,i320,i320); (%obj, %obj)retptraddrspace(1)%obj.relocated}

In the above examples, the addrspace(1) marker on the pointers is the mechanismthat thestatepoint-example GC strategy uses to distinguish references fromnon references. This is controlled via GCStrategy::isGCManagedPointer. Thestatepoint-example andcoreclr strategies (the only two defaultstrategies that support statepoints) both use addrspace(1) to determine whichpointers are references, however custom strategies don’t have to follow thisconvention.

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 in0xABCDEF00 as the statepointID and0 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 constructedgc.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 constructedgc.statepoint. The"statepoint-id" and"statepoint-num-patch-bytes" attributesare not propagated to thegc.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.

RewriteStatepointsForGC intrinsic lowering¶

As a part of lowering to the explicit model of relocationsRewriteStatepointsForGC performs GC specific lowering for the followingintrinsics:

• gc.get.pointer.base

• gc.get.pointer.offset

• llvm.memcpy.element.unordered.atomic.*

• llvm.memmove.element.unordered.atomic.*

There are two possible lowerings for the memcpy and memmove operations:GC leaf lowering and GC parseable lowering. If a call is explicitly marked with“gc-leaf-function” attribute the call is lowered to a GC leaf call to‘__llvm_memcpy_element_unordered_atomic_*’ or‘__llvm_memmove_element_unordered_atomic_*’ symbol. Such a call can nottake a safepoint. Otherwise, the call is made GC parseable by wrapping thecall into a statepoint. This makes it possible to take a safepoint duringcopy operation. Note that a GC parseable copy operation is not required totake a safepoint. For example, a short copy operation may be performed withouttaking a safepoint.

GC parseable calls to ‘llvm.memcpy.element.unordered.atomic.*’,‘llvm.memmove.element.unordered.atomic.*’ intrinsics are lowered to callsto ‘__llvm_memcpy_element_unordered_atomic_safepoint_*’,‘__llvm_memmove_element_unordered_atomic_safepoint_*’ symbols respectively.This way the runtime can provide implementations of copy operations with andwithout safepoints.

GC parseable lowering also involves adjusting the arguments for the call.Memcpy and memmove intrinsics take derived pointers as source and destinationarguments. If a copy operation takes a safepoint it might need to relocate theunderlying source and destination objects. This requires the corresponding basepointers to be available in the copy operation. In order to make the basepointers available RewriteStatepointsForGC replaces derived pointers with basepointer and offset pairs. For example:

declarevoid@__llvm_memcpy_element_unordered_atomic_safepoint_1(i8addrspace(1)*%dest_base,i64%dest_offset,i8addrspace(1)*%src_base,i64%src_offset,i64%length)

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:

definevoid@test()gc"statepoint-example"{callvoid@foo()retvoid}declarevoid@do_safepoint()definevoid@gc.safepoint_poll(){callvoid@do_safepoint()retvoid}

This pass would produce the following IR:

definevoid@test()gc"statepoint-example"{callvoid@do_safepoint()callvoid@foo()retvoid}

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 thatfoo andtest 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 namegc.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 agc.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.

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. Seethis llvm-dev discussion for moredetail.