796 lines · plain
1=====================================2Garbage Collection Safepoints in LLVM3=====================================4 5.. contents::6 :local:7 :depth: 28 9Status10=======11 12This document describes a set of extensions to LLVM to support garbage13collection. By now, these mechanisms are well proven with commercial java14implementation with a fully relocating collector having shipped using them.15There are a couple places where bugs might still linger; these are called out16below.17 18They are still listed as "experimental" to indicate that no forward or backward19compatibility guarantees are offered across versions. If your use case is such20that you need some form of forward compatibility guarantee, please raise the21issue on the llvm-dev mailing list.22 23LLVM still supports an alternate mechanism for conservative garbage collection24support using the ``gcroot`` intrinsic. The ``gcroot`` mechanism is mostly of25historical interest at this point with one exception - its implementation of26shadow stacks has been used successfully by a number of language frontends and27is still supported.28 29Overview & Core Concepts30========================31 32To collect dead objects, garbage collectors must be able to identify33any references to objects contained within executing code, and,34depending on the collector, potentially update them. The collector35does not need this information at all points in code - that would make36the problem much harder - but only at well-defined points in the37execution known as 'safepoints' For most collectors, it is sufficient38to track at least one copy of each unique pointer value. However, for39a collector which wishes to relocate objects directly reachable from40running code, a higher standard is required.41 42One additional challenge is that the compiler may compute intermediate43results ("derived pointers") which point outside of the allocation or44even into the middle of another allocation. The eventual use of this45intermediate value must yield an address within the bounds of the46allocation, but such "exterior derived pointers" may be visible to the47collector. Given this, a garbage collector can not safely rely on the48runtime value of an address to indicate the object it is associated49with. If the garbage collector wishes to move any object, the50compiler must provide a mapping, for each pointer, to an indication of51its allocation.52 53To simplify the interaction between a collector and the compiled code,54most garbage collectors are organized in terms of three abstractions:55load barriers, store barriers, and safepoints.56 57#. A load barrier is a bit of code executed immediately after the58 machine load instruction, but before any use of the value loaded.59 Depending on the collector, such a barrier may be needed for all60 loads, merely loads of a particular type (in the original source61 language), or none at all.62 63#. Analogously, a store barrier is a code fragment that runs64 immediately before the machine store instruction, but after the65 computation of the value stored. The most common use of a store66 barrier is to update a 'card table' in a generational garbage67 collector.68 69#. A safepoint is a location at which pointers visible to the compiled70 code (i.e. currently in registers or on the stack) are allowed to71 change. After the safepoint completes, the actual pointer value72 may differ, but the 'object' (as seen by the source language)73 pointed to will not.74 75 Note that the term 'safepoint' is somewhat overloaded. It refers to76 both the location at which the machine state is parsable and the77 coordination protocol involved in bring application threads to a78 point at which the collector can safely use that information. The79 term "statepoint" as used in this document refers exclusively to the80 former.81 82This document focuses on the last item - compiler support for83safepoints in generated code. We will assume that an outside84mechanism has decided where to place safepoints. From our85perspective, all safepoints will be function calls. To support86relocation of objects directly reachable from values in compiled code,87the collector must be able to:88 89#. identify every copy of a pointer (including copies introduced by90 the compiler itself) at the safepoint,91#. identify which object each pointer relates to, and92#. potentially update each of those copies.93 94This document describes the mechanism by which an LLVM based compiler95can provide this information to a language runtime/collector, and96ensure that all pointers can be read and updated if desired.97 98Abstract Machine Model99^^^^^^^^^^^^^^^^^^^^^^^100 101At a high level, LLVM has been extended to support compiling to an abstract102machine which extends the actual target with a non-integral pointer type103suitable for representing a garbage collected reference to an object. In104particular, such non-integral pointer type have no defined mapping to an105integer representation. This semantic quirk allows the runtime to pick a106integer mapping for each point in the program allowing relocations of objects107without visible effects.108 109This high level abstract machine model is used for most of the optimizer. As110a result, transform passes do not need to be extended to look through explicit111relocation sequence. Before starting code generation, we switch112representations to an explicit form. The exact location chosen for lowering113is an implementation detail.114 115Note that most of the value of the abstract machine model comes for collectors116which need to model potentially relocatable objects. For a compiler which117supports only a non-relocating collector, you may wish to consider starting118with the fully explicit form.119 120Warning: There is one currently known semantic hole in the definition of121non-integral pointers which has not been addressed upstream. To work around122this, you need to disable speculation of loads unless the memory type123(non-integral pointer vs anything else) is known to unchanged. That is, it is124not safe to speculate a load if doing causes a non-integral pointer value to125be loaded as any other type or vice versa. In practice, this restriction is126well isolated to isSafeToSpeculate in ValueTracking.cpp.127 128Explicit Representation129^^^^^^^^^^^^^^^^^^^^^^^130 131A frontend could directly generate this low level explicit form, but132doing so may inhibit optimization. Instead, it is recommended that133compilers with relocating collectors target the abstract machine model just134described.135 136The heart of the explicit approach is to construct (or rewrite) the IR in a137manner where the possible updates performed by the garbage collector are138explicitly visible in the IR. Doing so requires that we:139 140#. create a new SSA value for each potentially relocated pointer, and141 ensure that no uses of the original (non relocated) value is142 reachable after the safepoint,143#. specify the relocation in a way which is opaque to the compiler to144 ensure that the optimizer can not introduce new uses of an145 unrelocated value after a statepoint. This prevents the optimizer146 from performing unsound optimizations.147#. recording a mapping of live pointers (and the allocation they're148 associated with) for each statepoint.149 150At the most abstract level, inserting a safepoint can be thought of as151replacing a call instruction with a call to a multiple return value152function which both calls the original target of the call, returns153its result, and returns updated values for any live pointers to154garbage collected objects.155 156 Note that the task of identifying all live pointers to garbage157 collected values, transforming the IR to expose a pointer giving the158 base object for every such live pointer, and inserting all the159 intrinsics correctly is explicitly out of scope for this document.160 The recommended approach is to use the :ref:`utility passes161 <statepoint-utilities>` described below.162 163This abstract function call is concretely represented by a sequence of164intrinsic calls known collectively as a "statepoint relocation sequence".165 166Let's consider a simple call in LLVM IR:167 168.. code-block:: llvm169 170 declare void @foo()171 define ptr addrspace(1) @test1(ptr addrspace(1) %obj)172 gc "statepoint-example" {173 call void @foo()174 ret ptr addrspace(1) %obj175 }176 177Depending on our language we may need to allow a safepoint during the execution178of ``foo``. If so, we need to let the collector update local values in the179current frame. If we don't, we'll be accessing a potential invalid reference180once we eventually return from the call.181 182In this example, we need to relocate the SSA value ``%obj``. Since we can't183actually change the value in the SSA value ``%obj``, we need to introduce a new184SSA value ``%obj.relocated`` which represents the potentially changed value of185``%obj`` after the safepoint and update any following uses appropriately. The186resulting relocation sequence is:187 188.. code-block:: llvm189 190 define ptr addrspace(1) @test(ptr addrspace(1) %obj)191 gc "statepoint-example" {192 %safepoint = call token (i64, i32, ptr, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, ptr elementtype(void ()) @foo, i32 0, i32 0, i32 0, i32 0) ["gc-live" (ptr addrspace(1) %obj)]193 %obj.relocated = call ptr addrspace(1) @llvm.experimental.gc.relocate.p1(token %safepoint, i32 0, i32 0)194 ret ptr addrspace(1) %obj.relocated195 }196 197Ideally, this sequence would have been represented as a M argument, N198return value function (where M is the number of values being199relocated + the original call arguments and N is the original return200value + each relocated value), but LLVM does not easily support such a201representation.202 203Instead, the statepoint intrinsic marks the actual site of the204safepoint or statepoint. The statepoint returns a token value (which205exists only at compile time). To get back the original return value206of the call, we use the ``gc.result`` intrinsic. To get the relocation207of each pointer in turn, we use the ``gc.relocate`` intrinsic with the208appropriate index. Note that both the ``gc.relocate`` and ``gc.result`` are209tied to the statepoint. The combination forms a "statepoint relocation210sequence" and represents the entirety of a parseable call or 'statepoint'.211 212When lowered, this example would generate the following x86 assembly:213 214.. code-block:: gas215 216 .globl test1217 .align 16, 0x90218 pushq %rax219 callq foo220 .Ltmp1:221 movq (%rsp), %rax # This load is redundant (oops!)222 popq %rdx223 retq224 225Each of the potentially relocated values has been spilled to the226stack, and a record of that location has been recorded to the227:ref:`Stack Map section <stackmap-section>`. If the garbage collector228needs to update any of these pointers during the call, it knows229exactly what to change.230 231The relevant parts of the StackMap section for our example are:232 233.. code-block:: gas234 235 # This describes the call site236 # Stack Maps: callsite 2882400000237 .quad 2882400000238 .long .Ltmp1-test1239 .short 0240 # .. 8 entries skipped ..241 # This entry describes the spill slot which is directly addressable242 # off RSP with offset 0. Given the value was spilled with a pushq,243 # that makes sense.244 # Stack Maps: Loc 8: Direct RSP [encoding: .byte 2, .byte 8, .short 7, .int 0]245 .byte 2246 .byte 8247 .short 7248 .long 0249 250This example was taken from the tests for the :ref:`RewriteStatepointsForGC`251utility pass. As such, its full StackMap can be easily examined with the252following command.253 254.. code-block:: bash255 256 opt -rewrite-statepoints-for-gc test/Transforms/RewriteStatepointsForGC/basics.ll -S | llc -debug-only=stackmaps257 258Simplifications for Non-Relocating GCs259^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^260 261Some of the complexity in the previous example is unnecessary for a262non-relocating collector. While a non-relocating collector still needs the263information about which location contain live references, it doesn't need to264represent explicit relocations. As such, the previously described explicit265lowering can be simplified to remove all of the ``gc.relocate`` intrinsic266calls and leave uses in terms of the original reference value.267 268Here's the explicit lowering for the previous example for a non-relocating269collector:270 271.. code-block:: llvm272 273 define void @manual_frame(ptr %a, ptr %b) gc "statepoint-example" {274 %alloca = alloca ptr275 %allocb = alloca ptr276 store ptr %a, ptr %alloca277 store ptr %b, ptr %allocb278 call token (i64, i32, ptr, i32, i32, ...) @llvm.experimental.gc.statepoint.p0(i64 0, i32 0, ptr elementtype(void ()) @func, i32 0, i32 0, i32 0, i32 0) ["gc-live" (ptr %alloca, ptr %allocb)]279 ret void280 }281 282Recording On Stack Regions283^^^^^^^^^^^^^^^^^^^^^^^^^^284 285In addition to the explicit relocation form previously described, the286statepoint infrastructure also allows the listing of allocas within the gc287pointer list. Allocas can be listed with or without additional explicit gc288pointer values and relocations.289 290An alloca in the gc region of the statepoint operand list will cause the291address of the stack region to be listed in the stackmap for the statepoint.292 293This mechanism can be used to describe explicit spill slots if desired. It294then becomes the generator's responsibility to ensure that values are295spill/filled to/from the alloca as needed on either side of the safepoint.296Note that there is no way to indicate a corresponding base pointer for such297an explicitly specified spill slot, so usage is restricted to values for298which the associated collector can derive the object base from the pointer299itself.300 301This mechanism can be used to describe on stack objects containing302references provided that the collector can map from the location on the303stack to a heap map describing the internal layout of the references the304collector needs to process.305 306WARNING: At the moment, this alternate form is not well exercised. It is307recommended to use this with caution and expect to have to fix a few bugs.308In particular, the RewriteStatepointsForGC utility pass does not do309anything for allocas today.310 311Base & Derived Pointers312^^^^^^^^^^^^^^^^^^^^^^^313 314A "base pointer" is one which points to the starting address of an allocation315(object). A "derived pointer" is one which is offset from a base pointer by316some amount. When relocating objects, a garbage collector needs to be able317to relocate each derived pointer associated with an allocation to the same318offset from the new address.319 320"Interior derived pointers" remain within the bounds of the allocation321they're associated with. As a result, the base object can be found at322runtime provided the bounds of allocations are known to the runtime system.323 324"Exterior derived pointers" are outside the bounds of the associated object;325they may even fall within *another* allocations address range. As a result,326there is no way for a garbage collector to determine which allocation they327are associated with at runtime and compiler support is needed.328 329The ``gc.relocate`` intrinsic supports an explicit operand for describing the330allocation associated with a derived pointer. This operand is frequently331referred to as the base operand, but does not strictly speaking have to be332a base pointer, but it does need to lie within the bounds of the associated333allocation. Some collectors may require that the operand be an actual base334pointer rather than merely an internal derived pointer. Note that during335lowering both the base and derived pointer operands are required to be live336over the associated call safepoint even if the base is otherwise unused337afterwards.338 339.. _gc_transition_args:340 341GC Transitions342^^^^^^^^^^^^^^^^^^343 344As a practical consideration, many garbage-collected systems allow code that is345collector-aware ("managed code") to call code that is not collector-aware346("unmanaged code"). It is common that such calls must also be safepoints, since347it is desirable to allow the collector to run during the execution of348unmanaged code. Furthermore, it is common that coordinating the transition from349managed to unmanaged code requires extra code generation at the call site to350inform the collector of the transition. In order to support these needs, a351statepoint may be marked as a GC transition, and data that is necessary to352perform the transition (if any) may be provided as additional arguments to the353statepoint.354 355 Note that although in many cases statepoints may be inferred to be GC356 transitions based on the function symbols involved (e.g. a call from a357 function with GC strategy "foo" to a function with GC strategy "bar"),358 indirect calls that are also GC transitions must also be supported. This359 requirement is the driving force behind the decision to require that GC360 transitions are explicitly marked.361 362Let's revisit the sample given above, this time treating the call to ``@foo``363as a GC transition. Depending on our target, the transition code may need to364access some extra state in order to inform the collector of the transition.365Let's assume a hypothetical GC--somewhat unimaginatively named "hypothetical-gc"366--that requires that a TLS variable must be written to before and after a call367to unmanaged code. The resulting relocation sequence is:368 369.. code-block:: llvm370 371 @flag = thread_local global i32 0, align 4372 373 define i8 addrspace(1)* @test1(i8 addrspace(1) *%obj)374 gc "hypothetical-gc" {375 376 %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)377 %obj.relocated = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %0, i32 7, i32 7)378 ret i8 addrspace(1)* %obj.relocated379 }380 381During lowering, this will result in an instruction selection DAG that looks382something like:383 384::385 386 CALLSEQ_START387 ...388 GC_TRANSITION_START (lowered i32 *@Flag), SRCVALUE i32* Flag389 STATEPOINT390 GC_TRANSITION_END (lowered i32 *@Flag), SRCVALUE i32 *Flag391 ...392 CALLSEQ_END393 394In order to generate the necessary transition code, the backend for each target395supported by "hypothetical-gc" must be modified to lower ``GC_TRANSITION_START``396and ``GC_TRANSITION_END`` nodes appropriately when the "hypothetical-gc"397strategy is in use for a particular function. Assuming that such lowering has398been added for X86, the generated assembly would be:399 400.. code-block:: gas401 402 .globl test1403 .align 16, 0x90404 pushq %rax405 movl $1, %fs:Flag@TPOFF406 callq foo407 movl $0, %fs:Flag@TPOFF408 .Ltmp1:409 movq (%rsp), %rax # This load is redundant (oops!)410 popq %rdx411 retq412 413Note that the design as presented above is not fully implemented: in particular,414strategy-specific lowering is not present, and all GC transitions are emitted as415as single no-op before and after the call instruction. These no-ops are often416removed by the backend during dead machine instruction elimination.417 418Before the abstract machine model is lowered to the explicit statepoint model419of relocations by the :ref:`RewriteStatepointsForGC` pass it is possible for420any derived pointer to get its base pointer and offset from the base pointer421by using the ``gc.get.pointer.base`` and the ``gc.get.pointer.offset``422intrinsics respectively. These intrinsics are inlined by the423:ref:`RewriteStatepointsForGC` pass and must not be used after this pass.424 425 426.. _statepoint-stackmap-format:427 428Stack Map Format429================430 431Locations for each pointer value which may need read and/or updated by432the runtime or collector are provided in a separate section of the433generated object file as specified in the PatchPoint documentation.434This special section is encoded per the435:ref:`Stack Map format <stackmap-format>`.436 437The general expectation is that a JIT compiler will parse and discard this438format; it is not particularly memory efficient. If you need an alternate439format (e.g. for an ahead of time compiler), see discussion under440:ref: `open work items <OpenWork>` below.441 442Each statepoint generates the following Locations:443 444* Constant which describes the calling convention of the call target. This445 constant is a valid :ref:`calling convention identifier <callingconv>` for446 the version of LLVM used to generate the stackmap. No additional compatibility447 guarantees are made for this constant over what LLVM provides elsewhere w.r.t.448 these identifiers.449* Constant which describes the flags passed to the statepoint intrinsic450* Constant which describes number of following deopt *Locations* (not451 operands). Will be 0 if no "deopt" bundle is provided.452* Variable number of Locations, one for each deopt parameter listed in the453 "deopt" operand bundle. At the moment, only deopt parameters with a bitwidth454 of 64 bits or less are supported. Values of a type larger than 64 bits can be455 specified and reported only if a) the value is constant at the call site, and456 b) the constant can be represented with less than 64 bits (assuming zero457 extension to the original bitwidth).458* Variable number of relocation records, each of which consists of459 exactly two Locations. Relocation records are described in detail460 below.461 462Each relocation record provides sufficient information for a collector to463relocate one or more derived pointers. Each record consists of a pair of464Locations. The second element in the record represents the pointer (or465pointers) which need updated. The first element in the record provides a466pointer to the base of the object with which the pointer(s) being relocated is467associated. This information is required for handling generalized derived468pointers since a pointer may be outside the bounds of the original allocation,469but still needs to be relocated with the allocation. Additionally:470 471* It is guaranteed that the base pointer must also appear explicitly as a472 relocation pair if used after the statepoint.473* There may be fewer relocation records then gc parameters in the IR474 statepoint. Each *unique* pair will occur at least once; duplicates475 are possible.476* The Locations within each record may either be of pointer size or a477 multiple of pointer size. In the later case, the record must be478 interpreted as describing a sequence of pointers and their corresponding479 base pointers. If the Location is of size N x sizeof(pointer), then480 there will be N records of one pointer each contained within the Location.481 Both Locations in a pair can be assumed to be of the same size.482 483Note that the Locations used in each section may describe the same484physical location. e.g. A stack slot may appear as a deopt location,485a gc base pointer, and a gc derived pointer.486 487The LiveOut section of the StkMapRecord will be empty for a statepoint488record.489 490Safepoint Semantics & Verification491==================================492 493The fundamental correctness property for the compiled code's494correctness w.r.t. the garbage collector is a dynamic one. It must be495the case that there is no dynamic trace such that an operation496involving a potentially relocated pointer is observably-after a497safepoint which could relocate it. 'observably-after' is this usage498means that an outside observer could observe this sequence of events499in a way which precludes the operation being performed before the500safepoint.501 502To understand why this 'observable-after' property is required,503consider a null comparison performed on the original copy of a504relocated pointer. Assuming that control flow follows the safepoint,505there is no way to observe externally whether the null comparison is506performed before or after the safepoint. (Remember, the original507Value is unmodified by the safepoint.) The compiler is free to make508either scheduling choice.509 510The actual correctness property implemented is slightly stronger than511this. We require that there be no *static path* on which a512potentially relocated pointer is 'observably-after' it may have been513relocated. This is slightly stronger than is strictly necessary (and514thus may disallow some otherwise valid programs), but greatly515simplifies reasoning about correctness of the compiled code.516 517By construction, this property will be upheld by the optimizer if518correctly established in the source IR. This is a key invariant of519the design.520 521The existing IR Verifier pass has been extended to check most of the522local restrictions on the intrinsics mentioned in their respective523documentation. The current implementation in LLVM does not check the524key relocation invariant, but this is ongoing work on developing such525a verifier. Please ask on llvm-dev if you're interested in526experimenting with the current version.527 528.. _statepoint-utilities:529 530Utility Passes for Safepoint Insertion531======================================532 533.. _RewriteStatepointsForGC:534 535RewriteStatepointsForGC536^^^^^^^^^^^^^^^^^^^^^^^^537 538The pass RewriteStatepointsForGC transforms a function's IR to lower from the539abstract machine model described above to the explicit statepoint model of540relocations. To do this, it replaces all calls or invokes of functions which541might contain a safepoint poll with a ``gc.statepoint`` and associated full542relocation sequence, including all required ``gc.relocates``.543 544This pass only applies to GCStrategy instances where the ``UseRS4GC`` flag545is set. The two builtin GC strategies with this set are the546"statepoint-example" and "coreclr" strategies.547 548As an example, given this code:549 550.. code-block:: llvm551 552 define ptr addrspace(1) @test1(ptr addrspace(1) %obj)553 gc "statepoint-example" {554 call void @foo()555 ret ptr addrspace(1) %obj556 }557 558The pass would produce this IR:559 560.. code-block:: llvm561 562 define ptr addrspace(1) @test_rs4gc(ptr addrspace(1) %obj) gc "statepoint-example" {563 %statepoint_token = call token (i64, i32, ptr, i32, i32, ...) @llvm.experimental.gc.statepoint.p0(i64 2882400000, i32 0, ptr elementtype(void ()) @foo, i32 0, i32 0, i32 0, i32 0) [ "gc-live"(ptr addrspace(1) %obj) ]564 %obj.relocated = call coldcc ptr addrspace(1) @llvm.experimental.gc.relocate.p1(token %statepoint_token, i32 0, i32 0) ; (%obj, %obj)565 ret ptr addrspace(1) %obj.relocated566 }567 568In the above examples, the addrspace(1) marker on the pointers is the mechanism569that the ``statepoint-example`` GC strategy uses to distinguish references from570non references. This is controlled via GCStrategy::isGCManagedPointer. The571``statepoint-example`` and ``coreclr`` strategies (the only two default572strategies that support statepoints) both use addrspace(1) to determine which573pointers are references, however custom strategies don't have to follow this574convention.575 576This pass can be used an utility function by a language frontend that doesn't577want to manually reason about liveness, base pointers, or relocation when578constructing IR. As currently implemented, RewriteStatepointsForGC must be579run after SSA construction (i.e. mem2ref).580 581RewriteStatepointsForGC will ensure that appropriate base pointers are listed582for every relocation created. It will do so by duplicating code as needed to583propagate the base pointer associated with each pointer being relocated to584the appropriate safepoints. The implementation assumes that the following585IR constructs produce base pointers: loads from the heap, addresses of global586variables, function arguments, function return values. Constant pointers (such587as null) are also assumed to be base pointers. In practice, this constraint588can be relaxed to producing interior derived pointers provided the target589collector can find the associated allocation from an arbitrary interior590derived pointer.591 592By default RewriteStatepointsForGC passes in ``0xABCDEF00`` as the statepoint593ID and ``0`` as the number of patchable bytes to the newly constructed594``gc.statepoint``. These values can be configured on a per-callsite595basis using the attributes ``"statepoint-id"`` and596``"statepoint-num-patch-bytes"``. If a call site is marked with a597``"statepoint-id"`` function attribute and its value is a positive598integer (represented as a string), then that value is used as the ID599of the newly constructed ``gc.statepoint``. If a call site is marked600with a ``"statepoint-num-patch-bytes"`` function attribute and its601value is a positive integer, then that value is used as the 'num patch602bytes' parameter of the newly constructed ``gc.statepoint``. The603``"statepoint-id"`` and ``"statepoint-num-patch-bytes"`` attributes604are not propagated to the ``gc.statepoint`` call or invoke if they605could be successfully parsed.606 607In practice, RewriteStatepointsForGC should be run much later in the pass608pipeline, after most optimization is already done. This helps to improve609the quality of the generated code when compiled with garbage collection support.610 611.. _RewriteStatepointsForGC_intrinsic_lowering:612 613RewriteStatepointsForGC intrinsic lowering614^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^615 616As a part of lowering to the explicit model of relocations617RewriteStatepointsForGC performs GC specific lowering for the following618intrinsics:619 620* ``gc.get.pointer.base``621* ``gc.get.pointer.offset``622* ``llvm.memcpy.element.unordered.atomic.*``623* ``llvm.memmove.element.unordered.atomic.*``624 625There are two possible lowerings for the memcpy and memmove operations:626GC leaf lowering and GC parseable lowering. If a call is explicitly marked with627"gc-leaf-function" attribute the call is lowered to a GC leaf call to628'``__llvm_memcpy_element_unordered_atomic_*``' or629'``__llvm_memmove_element_unordered_atomic_*``' symbol. Such a call can not630take a safepoint. Otherwise, the call is made GC parseable by wrapping the631call into a statepoint. This makes it possible to take a safepoint during632copy operation. Note that a GC parseable copy operation is not required to633take a safepoint. For example, a short copy operation may be performed without634taking a safepoint.635 636GC parseable calls to '``llvm.memcpy.element.unordered.atomic.*``',637'``llvm.memmove.element.unordered.atomic.*``' intrinsics are lowered to calls638to '``__llvm_memcpy_element_unordered_atomic_safepoint_*``',639'``__llvm_memmove_element_unordered_atomic_safepoint_*``' symbols respectively.640This way the runtime can provide implementations of copy operations with and641without safepoints.642 643GC parseable lowering also involves adjusting the arguments for the call.644Memcpy and memmove intrinsics take derived pointers as source and destination645arguments. If a copy operation takes a safepoint it might need to relocate the646underlying source and destination objects. This requires the corresponding base647pointers to be available in the copy operation. In order to make the base648pointers available RewriteStatepointsForGC replaces derived pointers with base649pointer and offset pairs. For example:650 651.. code-block:: llvm652 653 declare void @__llvm_memcpy_element_unordered_atomic_safepoint_1(654 i8 addrspace(1)* %dest_base, i64 %dest_offset,655 i8 addrspace(1)* %src_base, i64 %src_offset,656 i64 %length)657 658 659.. _PlaceSafepoints:660 661PlaceSafepoints662^^^^^^^^^^^^^^^^663 664The pass PlaceSafepoints inserts safepoint polls sufficient to ensure running665code checks for a safepoint request on a timely manner. This pass is expected666to be run before RewriteStatepointsForGC and thus does not produce full667relocation sequences.668 669As an example, given input IR of the following:670 671.. code-block:: llvm672 673 define void @test() gc "statepoint-example" {674 call void @foo()675 ret void676 }677 678 declare void @do_safepoint()679 define void @gc.safepoint_poll() {680 call void @do_safepoint()681 ret void682 }683 684 685This pass would produce the following IR:686 687.. code-block:: llvm688 689 define void @test() gc "statepoint-example" {690 call void @do_safepoint()691 call void @foo()692 ret void693 }694 695In this case, we've added an (unconditional) entry safepoint poll. Note that696despite appearances, the entry poll is not necessarily redundant. We'd have to697know that ``foo`` and ``test`` were not mutually recursive for the poll to be698redundant. In practice, you'd probably want to your poll definition to contain699a conditional branch of some form.700 701At the moment, PlaceSafepoints can insert safepoint polls at method entry and702loop backedges locations. Extending this to work with return polls would be703straight forward if desired.704 705PlaceSafepoints includes a number of optimizations to avoid placing safepoint706polls at particular sites unless needed to ensure timely execution of a poll707under normal conditions. PlaceSafepoints does not attempt to ensure timely708execution of a poll under worst case conditions such as heavy system paging.709 710The implementation of a safepoint poll action is specified by looking up a711function of the name ``gc.safepoint_poll`` in the containing Module. The body712of this function is inserted at each poll site desired. While calls or invokes713inside this method are transformed to a ``gc.statepoints``, recursive poll714insertion is not performed.715 716This pass is useful for any language frontend which only has to support717garbage collection semantics at safepoints. If you need other abstract718frame information at safepoints (e.g. for deoptimization or introspection),719you can insert safepoint polls in the frontend. If you have the later case,720please ask on llvm-dev for suggestions. There's been a good amount of work721done on making such a scheme work well in practice which is not yet documented722here.723 724 725Supported Architectures726=======================727 728Support for statepoint generation requires some code for each backend.729Today, only Aarch64 and X86_64 are supported.730 731.. _OpenWork:732 733Limitations and Half Baked Ideas734================================735 736Mixing References and Raw Pointers737^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^738 739Support for languages which allow unmanaged pointers to garbage collected740objects (i.e. pass a pointer to an object to a C routine) in the abstract741machine model. At the moment, the best idea on how to approach this742involves an intrinsic or opaque function which hides the connection between743the reference value and the raw pointer. The problem is that having a744ptrtoint or inttoptr cast (which is common for such use cases) breaks the745rules used for inferring base pointers for arbitrary references when746lowering out of the abstract model to the explicit physical model. Note747that a frontend which lowers directly to the physical model doesn't have748any problems here.749 750Objects on the Stack751^^^^^^^^^^^^^^^^^^^^752 753As noted above, the explicit lowering supports objects allocated on the754stack provided the collector can find a heap map given the stack address.755 756The missing pieces are a) integration with rewriting (RS4GC) from the757abstract machine model and b) support for optionally decomposing on stack758objects so as not to require heap maps for them. The later is required759for ease of integration with some collectors.760 761Lowering Quality and Representation Overhead762^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^763 764The current statepoint lowering is known to be somewhat poor. In the very765long term, we'd like to integrate statepoints with the register allocator;766in the near term this is unlikely to happen. We've found the quality of767lowering to be relatively unimportant as hot-statepoints are almost always768inliner bugs.769 770Concerns have been raised that the statepoint representation results in a771large amount of IR being produced for some examples and that this772contributes to higher than expected memory usage and compile times. There's773no immediate plans to make changes due to this, but alternate models may be774explored in the future.775 776Relocations Along Exceptional Edges777^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^778 779Relocations along exceptional paths are currently broken in ToT. In780particular, there is current no way to represent a rethrow on a path which781also has relocations. See `this llvm-dev discussion782<https://groups.google.com/forum/#!topic/llvm-dev/AE417XjgxvI>`_ for more783detail.784 785Bugs and Enhancements786=====================787 788Currently known bugs and enhancements under consideration can be789tracked by performing a `bugzilla search790<https://bugs.llvm.org/buglist.cgi?cmdtype=runnamed&namedcmd=Statepoint%20Bugs&list_id=64342>`_791for [Statepoint] in the summary field. When filing new bugs, please792use this tag so that interested parties see the newly filed bug. As793with most LLVM features, design discussions take place on the `Discourse forums <https://discourse.llvm.org>`_ and patches794should be sent to `llvm-commits795<http://lists.llvm.org/mailman/listinfo/llvm-commits>`_ for review.796