1===================================== 2Garbage Collection Safepoints in LLVM 3===================================== 4 5.. contents:: 6 :local: 7 :depth: 2 8 9Status 10======= 11 12This document describes a set of extensions to LLVM to support garbage 13collection. By now, these mechanisms are well proven with commercial java 14implementation with a fully relocating collector having shipped using them. 15There are a couple places where bugs might still linger; these are called out 16below. 17 18They are still listed as "experimental" to indicate that no forward or backward 19compatibility guarantees are offered across versions. If your use case is such 20that you need some form of forward compatibility guarantee, please raise the 21issue on the llvm-dev mailing list. 22 23LLVM still supports an alternate mechanism for conservative garbage collection 24support using the ``gcroot`` intrinsic. The ``gcroot`` mechanism is mostly of 25historical interest at this point with one exception - its implementation of 26shadow stacks has been used successfully by a number of language frontends and 27is still supported. 28 29Overview & Core Concepts 30======================== 31 32To collect dead objects, garbage collectors must be able to identify 33any references to objects contained within executing code, and, 34depending on the collector, potentially update them. The collector 35does not need this information at all points in code - that would make 36the problem much harder - but only at well-defined points in the 37execution known as 'safepoints' For most collectors, it is sufficient 38to track at least one copy of each unique pointer value. However, for 39a collector which wishes to relocate objects directly reachable from 40running code, a higher standard is required. 41 42One additional challenge is that the compiler may compute intermediate 43results ("derived pointers") which point outside of the allocation or 44even into the middle of another allocation. The eventual use of this 45intermediate value must yield an address within the bounds of the 46allocation, but such "exterior derived pointers" may be visible to the 47collector. Given this, a garbage collector can not safely rely on the 48runtime value of an address to indicate the object it is associated 49with. If the garbage collector wishes to move any object, the 50compiler must provide a mapping, for each pointer, to an indication of 51its 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 the 58 machine load instruction, but before any use of the value loaded. 59 Depending on the collector, such a barrier may be needed for all 60 loads, merely loads of a particular type (in the original source 61 language), or none at all. 62 63#. Analogously, a store barrier is a code fragment that runs 64 immediately before the machine store instruction, but after the 65 computation of the value stored. The most common use of a store 66 barrier is to update a 'card table' in a generational garbage 67 collector. 68 69#. A safepoint is a location at which pointers visible to the compiled 70 code (i.e. currently in registers or on the stack) are allowed to 71 change. After the safepoint completes, the actual pointer value 72 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 to 76 both the location at which the machine state is parsable and the 77 coordination protocol involved in bring application threads to a 78 point at which the collector can safely use that information. The 79 term "statepoint" as used in this document refers exclusively to the 80 former. 81 82This document focuses on the last item - compiler support for 83safepoints in generated code. We will assume that an outside 84mechanism has decided where to place safepoints. From our 85perspective, all safepoints will be function calls. To support 86relocation 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 by 90 the compiler itself) at the safepoint, 91#. identify which object each pointer relates to, and 92#. potentially update each of those copies. 93 94This document describes the mechanism by which an LLVM based compiler 95can provide this information to a language runtime/collector, and 96ensure that all pointers can be read and updated if desired. 97 98Abstract Machine Model 99^^^^^^^^^^^^^^^^^^^^^^^ 100 101At a high level, LLVM has been extended to support compiling to an abstract 102machine which extends the actual target with a non-integral pointer type 103suitable for representing a garbage collected reference to an object. In 104particular, such non-integral pointer type have no defined mapping to an 105integer representation. This semantic quirk allows the runtime to pick a 106integer mapping for each point in the program allowing relocations of objects 107without visible effects. 108 109This high level abstract machine model is used for most of the optimizer. As 110a result, transform passes do not need to be extended to look through explicit 111relocation sequence. Before starting code generation, we switch 112representations to an explicit form. The exact location chosen for lowering 113is an implementation detail. 114 115Note that most of the value of the abstract machine model comes for collectors 116which need to model potentially relocatable objects. For a compiler which 117supports only a non-relocating collector, you may wish to consider starting 118with the fully explicit form. 119 120Warning: There is one currently known semantic hole in the definition of 121non-integral pointers which has not been addressed upstream. To work around 122this, you need to disable speculation of loads unless the memory type 123(non-integral pointer vs anything else) is known to unchanged. That is, it is 124not safe to speculate a load if doing causes a non-integral pointer value to 125be loaded as any other type or vice versa. In practice, this restriction is 126well isolated to isSafeToSpeculate in ValueTracking.cpp. 127 128Explicit Representation 129^^^^^^^^^^^^^^^^^^^^^^^ 130 131A frontend could directly generate this low level explicit form, but 132doing so may inhibit optimization. Instead, it is recommended that 133compilers with relocating collectors target the abstract machine model just 134described. 135 136The heart of the explicit approach is to construct (or rewrite) the IR in a 137manner where the possible updates performed by the garbage collector are 138explicitly visible in the IR. Doing so requires that we: 139 140#. create a new SSA value for each potentially relocated pointer, and 141 ensure that no uses of the original (non relocated) value is 142 reachable after the safepoint, 143#. specify the relocation in a way which is opaque to the compiler to 144 ensure that the optimizer can not introduce new uses of an 145 unrelocated value after a statepoint. This prevents the optimizer 146 from performing unsound optimizations. 147#. recording a mapping of live pointers (and the allocation they're 148 associated with) for each statepoint. 149 150At the most abstract level, inserting a safepoint can be thought of as 151replacing a call instruction with a call to a multiple return value 152function which both calls the original target of the call, returns 153its result, and returns updated values for any live pointers to 154garbage collected objects. 155 156 Note that the task of identifying all live pointers to garbage 157 collected values, transforming the IR to expose a pointer giving the 158 base object for every such live pointer, and inserting all the 159 intrinsics correctly is explicitly out of scope for this document. 160 The recommended approach is to use the :ref:`utility passes 161 <statepoint-utilities>` described below. 162 163This abstract function call is concretely represented by a sequence of 164intrinsic calls known collectively as a "statepoint relocation sequence". 165 166Let's consider a simple call in LLVM IR: 167 168.. code-block:: llvm 169 170 define i8 addrspace(1)* @test1(i8 addrspace(1)* %obj) 171 gc "statepoint-example" { 172 call void ()* @foo() 173 ret i8 addrspace(1)* %obj 174 } 175 176Depending on our language we may need to allow a safepoint during the execution 177of ``foo``. If so, we need to let the collector update local values in the 178current frame. If we don't, we'll be accessing a potential invalid reference 179once we eventually return from the call. 180 181In this example, we need to relocate the SSA value ``%obj``. Since we can't 182actually change the value in the SSA value ``%obj``, we need to introduce a new 183SSA value ``%obj.relocated`` which represents the potentially changed value of 184``%obj`` after the safepoint and update any following uses appropriately. The 185resulting relocation sequence is: 186 187.. code-block:: llvm 188 189 define i8 addrspace(1)* @test1(i8 addrspace(1)* %obj) 190 gc "statepoint-example" { 191 %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) 192 %obj.relocated = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %0, i32 7, i32 7) 193 ret i8 addrspace(1)* %obj.relocated 194 } 195 196Ideally, this sequence would have been represented as a M argument, N 197return value function (where M is the number of values being 198relocated + the original call arguments and N is the original return 199value + each relocated value), but LLVM does not easily support such a 200representation. 201 202Instead, the statepoint intrinsic marks the actual site of the 203safepoint or statepoint. The statepoint returns a token value (which 204exists only at compile time). To get back the original return value 205of the call, we use the ``gc.result`` intrinsic. To get the relocation 206of each pointer in turn, we use the ``gc.relocate`` intrinsic with the 207appropriate index. Note that both the ``gc.relocate`` and ``gc.result`` are 208tied to the statepoint. The combination forms a "statepoint relocation 209sequence" and represents the entirety of a parseable call or 'statepoint'. 210 211When lowered, this example would generate the following x86 assembly: 212 213.. code-block:: gas 214 215 .globl test1 216 .align 16, 0x90 217 pushq %rax 218 callq foo 219 .Ltmp1: 220 movq (%rsp), %rax # This load is redundant (oops!) 221 popq %rdx 222 retq 223 224Each of the potentially relocated values has been spilled to the 225stack, and a record of that location has been recorded to the 226:ref:`Stack Map section <stackmap-section>`. If the garbage collector 227needs to update any of these pointers during the call, it knows 228exactly what to change. 229 230The relevant parts of the StackMap section for our example are: 231 232.. code-block:: gas 233 234 # This describes the call site 235 # Stack Maps: callsite 2882400000 236 .quad 2882400000 237 .long .Ltmp1-test1 238 .short 0 239 # .. 8 entries skipped .. 240 # This entry describes the spill slot which is directly addressable 241 # off RSP with offset 0. Given the value was spilled with a pushq, 242 # that makes sense. 243 # Stack Maps: Loc 8: Direct RSP [encoding: .byte 2, .byte 8, .short 7, .int 0] 244 .byte 2 245 .byte 8 246 .short 7 247 .long 0 248 249This example was taken from the tests for the :ref:`RewriteStatepointsForGC` 250utility pass. As such, its full StackMap can be easily examined with the 251following command. 252 253.. code-block:: bash 254 255 opt -rewrite-statepoints-for-gc test/Transforms/RewriteStatepointsForGC/basics.ll -S | llc -debug-only=stackmaps 256 257Simplifications for Non-Relocating GCs 258^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 259 260Some of the complexity in the previous example is unnecessary for a 261non-relocating collector. While a non-relocating collector still needs the 262information about which location contain live references, it doesn't need to 263represent explicit relocations. As such, the previously described explicit 264lowering can be simplified to remove all of the ``gc.relocate`` intrinsic 265calls and leave uses in terms of the original reference value. 266 267Here's the explicit lowering for the previous example for a non-relocating 268collector: 269 270.. code-block:: llvm 271 272 define i8 addrspace(1)* @test1(i8 addrspace(1)* %obj) 273 gc "statepoint-example" { 274 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) 275 ret i8 addrspace(1)* %obj 276 } 277 278Recording On Stack Regions 279^^^^^^^^^^^^^^^^^^^^^^^^^^ 280 281In addition to the explicit relocation form previously described, the 282statepoint infrastructure also allows the listing of allocas within the gc 283pointer list. Allocas can be listed with or without additional explicit gc 284pointer values and relocations. 285 286An alloca in the gc region of the statepoint operand list will cause the 287address of the stack region to be listed in the stackmap for the statepoint. 288 289This mechanism can be used to describe explicit spill slots if desired. It 290then becomes the generator's responsibility to ensure that values are 291spill/filled to/from the alloca as needed on either side of the safepoint. 292Note that there is no way to indicate a corresponding base pointer for such 293an explicitly specified spill slot, so usage is restricted to values for 294which the associated collector can derive the object base from the pointer 295itself. 296 297This mechanism can be used to describe on stack objects containing 298references provided that the collector can map from the location on the 299stack to a heap map describing the internal layout of the references the 300collector needs to process. 301 302WARNING: At the moment, this alternate form is not well exercised. It is 303recommended to use this with caution and expect to have to fix a few bugs. 304In particular, the RewriteStatepointsForGC utility pass does not do 305anything for allocas today. 306 307Base & Derived Pointers 308^^^^^^^^^^^^^^^^^^^^^^^ 309 310A "base pointer" is one which points to the starting address of an allocation 311(object). A "derived pointer" is one which is offset from a base pointer by 312some amount. When relocating objects, a garbage collector needs to be able 313to relocate each derived pointer associated with an allocation to the same 314offset from the new address. 315 316"Interior derived pointers" remain within the bounds of the allocation 317they're associated with. As a result, the base object can be found at 318runtime provided the bounds of allocations are known to the runtime system. 319 320"Exterior derived pointers" are outside the bounds of the associated object; 321they may even fall within *another* allocations address range. As a result, 322there is no way for a garbage collector to determine which allocation they 323are associated with at runtime and compiler support is needed. 324 325The ``gc.relocate`` intrinsic supports an explicit operand for describing the 326allocation associated with a derived pointer. This operand is frequently 327referred to as the base operand, but does not strictly speaking have to be 328a base pointer, but it does need to lie within the bounds of the associated 329allocation. Some collectors may require that the operand be an actual base 330pointer rather than merely an internal derived pointer. Note that during 331lowering both the base and derived pointer operands are required to be live 332over the associated call safepoint even if the base is otherwise unused 333afterwards. 334 335If we extend our previous example to include a pointless derived pointer, 336we get: 337 338.. code-block:: llvm 339 340 define i8 addrspace(1)* @test1(i8 addrspace(1)* %obj) 341 gc "statepoint-example" { 342 %gep = getelementptr i8, i8 addrspace(1)* %obj, i64 20000 343 %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) 344 %obj.relocated = call i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %token, i32 7, i32 7) 345 %gep.relocated = call i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %token, i32 7, i32 8) 346 %p = getelementptr i8, i8 addrspace(1)* %gep, i64 -20000 347 ret i8 addrspace(1)* %p 348 } 349 350Note that in this example %p and %obj.relocate are the same address and we 351could replace one with the other, potentially removing the derived pointer 352from the live set at the safepoint entirely. 353 354.. _gc_transition_args: 355 356GC Transitions 357^^^^^^^^^^^^^^^^^^ 358 359As a practical consideration, many garbage-collected systems allow code that is 360collector-aware ("managed code") to call code that is not collector-aware 361("unmanaged code"). It is common that such calls must also be safepoints, since 362it is desirable to allow the collector to run during the execution of 363unmanaged code. Furthermore, it is common that coordinating the transition from 364managed to unmanaged code requires extra code generation at the call site to 365inform the collector of the transition. In order to support these needs, a 366statepoint may be marked as a GC transition, and data that is necessary to 367perform the transition (if any) may be provided as additional arguments to the 368statepoint. 369 370 Note that although in many cases statepoints may be inferred to be GC 371 transitions based on the function symbols involved (e.g. a call from a 372 function with GC strategy "foo" to a function with GC strategy "bar"), 373 indirect calls that are also GC transitions must also be supported. This 374 requirement is the driving force behind the decision to require that GC 375 transitions are explicitly marked. 376 377Let's revisit the sample given above, this time treating the call to ``@foo`` 378as a GC transition. Depending on our target, the transition code may need to 379access some extra state in order to inform the collector of the transition. 380Let's assume a hypothetical GC--somewhat unimaginatively named "hypothetical-gc" 381--that requires that a TLS variable must be written to before and after a call 382to unmanaged code. The resulting relocation sequence is: 383 384.. code-block:: llvm 385 386 @flag = thread_local global i32 0, align 4 387 388 define i8 addrspace(1)* @test1(i8 addrspace(1) *%obj) 389 gc "hypothetical-gc" { 390 391 %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) 392 %obj.relocated = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %0, i32 7, i32 7) 393 ret i8 addrspace(1)* %obj.relocated 394 } 395 396During lowering, this will result in an instruction selection DAG that looks 397something like: 398 399:: 400 401 CALLSEQ_START 402 ... 403 GC_TRANSITION_START (lowered i32 *@Flag), SRCVALUE i32* Flag 404 STATEPOINT 405 GC_TRANSITION_END (lowered i32 *@Flag), SRCVALUE i32 *Flag 406 ... 407 CALLSEQ_END 408 409In order to generate the necessary transition code, the backend for each target 410supported by "hypothetical-gc" must be modified to lower ``GC_TRANSITION_START`` 411and ``GC_TRANSITION_END`` nodes appropriately when the "hypothetical-gc" 412strategy is in use for a particular function. Assuming that such lowering has 413been added for X86, the generated assembly would be: 414 415.. code-block:: gas 416 417 .globl test1 418 .align 16, 0x90 419 pushq %rax 420 movl $1, %fs:Flag@TPOFF 421 callq foo 422 movl $0, %fs:Flag@TPOFF 423 .Ltmp1: 424 movq (%rsp), %rax # This load is redundant (oops!) 425 popq %rdx 426 retq 427 428Note that the design as presented above is not fully implemented: in particular, 429strategy-specific lowering is not present, and all GC transitions are emitted as 430as single no-op before and after the call instruction. These no-ops are often 431removed by the backend during dead machine instruction elimination. 432 433Before the abstract machine model is lowered to the explicit statepoint model 434of relocations by the :ref:`RewriteStatepointsForGC` pass it is possible for 435any derived pointer to get its base pointer and offset from the base pointer 436by using the ``gc.get.pointer.base`` and the ``gc.get.pointer.offset`` 437intrinsics respectively. These intrinsics are inlined by the 438:ref:`RewriteStatepointsForGC` pass and must not be used after this pass. 439 440 441.. _statepoint-stackmap-format: 442 443Stack Map Format 444================ 445 446Locations for each pointer value which may need read and/or updated by 447the runtime or collector are provided in a separate section of the 448generated object file as specified in the PatchPoint documentation. 449This special section is encoded per the 450:ref:`Stack Map format <stackmap-format>`. 451 452The general expectation is that a JIT compiler will parse and discard this 453format; it is not particularly memory efficient. If you need an alternate 454format (e.g. for an ahead of time compiler), see discussion under 455:ref: `open work items <OpenWork>` below. 456 457Each statepoint generates the following Locations: 458 459* Constant which describes the calling convention of the call target. This 460 constant is a valid :ref:`calling convention identifier <callingconv>` for 461 the version of LLVM used to generate the stackmap. No additional compatibility 462 guarantees are made for this constant over what LLVM provides elsewhere w.r.t. 463 these identifiers. 464* Constant which describes the flags passed to the statepoint intrinsic 465* Constant which describes number of following deopt *Locations* (not 466 operands). Will be 0 if no "deopt" bundle is provided. 467* Variable number of Locations, one for each deopt parameter listed in the 468 "deopt" operand bundle. At the moment, only deopt parameters with a bitwidth 469 of 64 bits or less are supported. Values of a type larger than 64 bits can be 470 specified and reported only if a) the value is constant at the call site, and 471 b) the constant can be represented with less than 64 bits (assuming zero 472 extension to the original bitwidth). 473* Variable number of relocation records, each of which consists of 474 exactly two Locations. Relocation records are described in detail 475 below. 476 477Each relocation record provides sufficient information for a collector to 478relocate one or more derived pointers. Each record consists of a pair of 479Locations. The second element in the record represents the pointer (or 480pointers) which need updated. The first element in the record provides a 481pointer to the base of the object with which the pointer(s) being relocated is 482associated. This information is required for handling generalized derived 483pointers since a pointer may be outside the bounds of the original allocation, 484but still needs to be relocated with the allocation. Additionally: 485 486* It is guaranteed that the base pointer must also appear explicitly as a 487 relocation pair if used after the statepoint. 488* There may be fewer relocation records then gc parameters in the IR 489 statepoint. Each *unique* pair will occur at least once; duplicates 490 are possible. 491* The Locations within each record may either be of pointer size or a 492 multiple of pointer size. In the later case, the record must be 493 interpreted as describing a sequence of pointers and their corresponding 494 base pointers. If the Location is of size N x sizeof(pointer), then 495 there will be N records of one pointer each contained within the Location. 496 Both Locations in a pair can be assumed to be of the same size. 497 498Note that the Locations used in each section may describe the same 499physical location. e.g. A stack slot may appear as a deopt location, 500a gc base pointer, and a gc derived pointer. 501 502The LiveOut section of the StkMapRecord will be empty for a statepoint 503record. 504 505Safepoint Semantics & Verification 506================================== 507 508The fundamental correctness property for the compiled code's 509correctness w.r.t. the garbage collector is a dynamic one. It must be 510the case that there is no dynamic trace such that an operation 511involving a potentially relocated pointer is observably-after a 512safepoint which could relocate it. 'observably-after' is this usage 513means that an outside observer could observe this sequence of events 514in a way which precludes the operation being performed before the 515safepoint. 516 517To understand why this 'observable-after' property is required, 518consider a null comparison performed on the original copy of a 519relocated pointer. Assuming that control flow follows the safepoint, 520there is no way to observe externally whether the null comparison is 521performed before or after the safepoint. (Remember, the original 522Value is unmodified by the safepoint.) The compiler is free to make 523either scheduling choice. 524 525The actual correctness property implemented is slightly stronger than 526this. We require that there be no *static path* on which a 527potentially relocated pointer is 'observably-after' it may have been 528relocated. This is slightly stronger than is strictly necessary (and 529thus may disallow some otherwise valid programs), but greatly 530simplifies reasoning about correctness of the compiled code. 531 532By construction, this property will be upheld by the optimizer if 533correctly established in the source IR. This is a key invariant of 534the design. 535 536The existing IR Verifier pass has been extended to check most of the 537local restrictions on the intrinsics mentioned in their respective 538documentation. The current implementation in LLVM does not check the 539key relocation invariant, but this is ongoing work on developing such 540a verifier. Please ask on llvm-dev if you're interested in 541experimenting with the current version. 542 543.. _statepoint-utilities: 544 545Utility Passes for Safepoint Insertion 546====================================== 547 548.. _RewriteStatepointsForGC: 549 550RewriteStatepointsForGC 551^^^^^^^^^^^^^^^^^^^^^^^^ 552 553The pass RewriteStatepointsForGC transforms a function's IR to lower from the 554abstract machine model described above to the explicit statepoint model of 555relocations. To do this, it replaces all calls or invokes of functions which 556might contain a safepoint poll with a ``gc.statepoint`` and associated full 557relocation sequence, including all required ``gc.relocates``. 558 559Note that by default, this pass only runs for the "statepoint-example" or 560"core-clr" gc strategies. You will need to add your custom strategy to this 561list or use one of the predefined ones. 562 563As an example, given this code: 564 565.. code-block:: llvm 566 567 define i8 addrspace(1)* @test1(i8 addrspace(1)* %obj) 568 gc "statepoint-example" { 569 call void @foo() 570 ret i8 addrspace(1)* %obj 571 } 572 573The pass would produce this IR: 574 575.. code-block:: llvm 576 577 define i8 addrspace(1)* @test1(i8 addrspace(1)* %obj) 578 gc "statepoint-example" { 579 %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) 580 %obj.relocated = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %0, i32 12, i32 12) 581 ret i8 addrspace(1)* %obj.relocated 582 } 583 584In the above examples, the addrspace(1) marker on the pointers is the mechanism 585that the ``statepoint-example`` GC strategy uses to distinguish references from 586non references. The pass assumes that all addrspace(1) pointers are non-integral 587pointer types. Address space 1 is not globally reserved for this purpose. 588 589This pass can be used an utility function by a language frontend that doesn't 590want to manually reason about liveness, base pointers, or relocation when 591constructing IR. As currently implemented, RewriteStatepointsForGC must be 592run after SSA construction (i.e. mem2ref). 593 594RewriteStatepointsForGC will ensure that appropriate base pointers are listed 595for every relocation created. It will do so by duplicating code as needed to 596propagate the base pointer associated with each pointer being relocated to 597the appropriate safepoints. The implementation assumes that the following 598IR constructs produce base pointers: loads from the heap, addresses of global 599variables, function arguments, function return values. Constant pointers (such 600as null) are also assumed to be base pointers. In practice, this constraint 601can be relaxed to producing interior derived pointers provided the target 602collector can find the associated allocation from an arbitrary interior 603derived pointer. 604 605By default RewriteStatepointsForGC passes in ``0xABCDEF00`` as the statepoint 606ID and ``0`` as the number of patchable bytes to the newly constructed 607``gc.statepoint``. These values can be configured on a per-callsite 608basis using the attributes ``"statepoint-id"`` and 609``"statepoint-num-patch-bytes"``. If a call site is marked with a 610``"statepoint-id"`` function attribute and its value is a positive 611integer (represented as a string), then that value is used as the ID 612of the newly constructed ``gc.statepoint``. If a call site is marked 613with a ``"statepoint-num-patch-bytes"`` function attribute and its 614value is a positive integer, then that value is used as the 'num patch 615bytes' parameter of the newly constructed ``gc.statepoint``. The 616``"statepoint-id"`` and ``"statepoint-num-patch-bytes"`` attributes 617are not propagated to the ``gc.statepoint`` call or invoke if they 618could be successfully parsed. 619 620In practice, RewriteStatepointsForGC should be run much later in the pass 621pipeline, after most optimization is already done. This helps to improve 622the quality of the generated code when compiled with garbage collection support. 623 624.. _RewriteStatepointsForGC_intrinsic_lowering: 625 626RewriteStatepointsForGC intrinsic lowering 627^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 628 629As a part of lowering to the explicit model of relocations 630RewriteStatepointsForGC performs GC specific lowering for the following 631intrinsics: 632 633* ``gc.get.pointer.base`` 634* ``gc.get.pointer.offset`` 635* ``llvm.memcpy.element.unordered.atomic.*`` 636* ``llvm.memmove.element.unordered.atomic.*`` 637 638There are two possible lowerings for the memcpy and memmove operations: 639GC leaf lowering and GC parseable lowering. If a call is explicitly marked with 640"gc-leaf-function" attribute the call is lowered to a GC leaf call to 641'``__llvm_memcpy_element_unordered_atomic_*``' or 642'``__llvm_memmove_element_unordered_atomic_*``' symbol. Such a call can not 643take a safepoint. Otherwise, the call is made GC parseable by wrapping the 644call into a statepoint. This makes it possible to take a safepoint during 645copy operation. Note that a GC parseable copy operation is not required to 646take a safepoint. For example, a short copy operation may be performed without 647taking a safepoint. 648 649GC parseable calls to '``llvm.memcpy.element.unordered.atomic.*``', 650'``llvm.memmove.element.unordered.atomic.*``' intrinsics are lowered to calls 651to '``__llvm_memcpy_element_unordered_atomic_safepoint_*``', 652'``__llvm_memmove_element_unordered_atomic_safepoint_*``' symbols respectively. 653This way the runtime can provide implementations of copy operations with and 654without safepoints. 655 656GC parseable lowering also involves adjusting the arguments for the call. 657Memcpy and memmove intrinsics take derived pointers as source and destination 658arguments. If a copy operation takes a safepoint it might need to relocate the 659underlying source and destination objects. This requires the corresponding base 660pointers to be available in the copy operation. In order to make the base 661pointers available RewriteStatepointsForGC replaces derived pointers with base 662pointer and offset pairs. For example: 663 664.. code-block:: llvm 665 666 declare void @__llvm_memcpy_element_unordered_atomic_safepoint_1( 667 i8 addrspace(1)* %dest_base, i64 %dest_offset, 668 i8 addrspace(1)* %src_base, i64 %src_offset, 669 i64 %length) 670 671 672.. _PlaceSafepoints: 673 674PlaceSafepoints 675^^^^^^^^^^^^^^^^ 676 677The pass PlaceSafepoints inserts safepoint polls sufficient to ensure running 678code checks for a safepoint request on a timely manner. This pass is expected 679to be run before RewriteStatepointsForGC and thus does not produce full 680relocation sequences. 681 682As an example, given input IR of the following: 683 684.. code-block:: llvm 685 686 define void @test() gc "statepoint-example" { 687 call void @foo() 688 ret void 689 } 690 691 declare void @do_safepoint() 692 define void @gc.safepoint_poll() { 693 call void @do_safepoint() 694 ret void 695 } 696 697 698This pass would produce the following IR: 699 700.. code-block:: llvm 701 702 define void @test() gc "statepoint-example" { 703 call void @do_safepoint() 704 call void @foo() 705 ret void 706 } 707 708In this case, we've added an (unconditional) entry safepoint poll. Note that 709despite appearances, the entry poll is not necessarily redundant. We'd have to 710know that ``foo`` and ``test`` were not mutually recursive for the poll to be 711redundant. In practice, you'd probably want to your poll definition to contain 712a conditional branch of some form. 713 714At the moment, PlaceSafepoints can insert safepoint polls at method entry and 715loop backedges locations. Extending this to work with return polls would be 716straight forward if desired. 717 718PlaceSafepoints includes a number of optimizations to avoid placing safepoint 719polls at particular sites unless needed to ensure timely execution of a poll 720under normal conditions. PlaceSafepoints does not attempt to ensure timely 721execution of a poll under worst case conditions such as heavy system paging. 722 723The implementation of a safepoint poll action is specified by looking up a 724function of the name ``gc.safepoint_poll`` in the containing Module. The body 725of this function is inserted at each poll site desired. While calls or invokes 726inside this method are transformed to a ``gc.statepoints``, recursive poll 727insertion is not performed. 728 729This pass is useful for any language frontend which only has to support 730garbage collection semantics at safepoints. If you need other abstract 731frame information at safepoints (e.g. for deoptimization or introspection), 732you can insert safepoint polls in the frontend. If you have the later case, 733please ask on llvm-dev for suggestions. There's been a good amount of work 734done on making such a scheme work well in practice which is not yet documented 735here. 736 737 738Supported Architectures 739======================= 740 741Support for statepoint generation requires some code for each backend. 742Today, only X86_64 is supported. 743 744.. _OpenWork: 745 746Limitations and Half Baked Ideas 747================================ 748 749Mixing References and Raw Pointers 750^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 751 752Support for languages which allow unmanaged pointers to garbage collected 753objects (i.e. pass a pointer to an object to a C routine) in the abstract 754machine model. At the moment, the best idea on how to approach this 755involves an intrinsic or opaque function which hides the connection between 756the reference value and the raw pointer. The problem is that having a 757ptrtoint or inttoptr cast (which is common for such use cases) breaks the 758rules used for inferring base pointers for arbitrary references when 759lowering out of the abstract model to the explicit physical model. Note 760that a frontend which lowers directly to the physical model doesn't have 761any problems here. 762 763Objects on the Stack 764^^^^^^^^^^^^^^^^^^^^ 765 766As noted above, the explicit lowering supports objects allocated on the 767stack provided the collector can find a heap map given the stack address. 768 769The missing pieces are a) integration with rewriting (RS4GC) from the 770abstract machine model and b) support for optionally decomposing on stack 771objects so as not to require heap maps for them. The later is required 772for ease of integration with some collectors. 773 774Lowering Quality and Representation Overhead 775^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 776 777The current statepoint lowering is known to be somewhat poor. In the very 778long term, we'd like to integrate statepoints with the register allocator; 779in the near term this is unlikely to happen. We've found the quality of 780lowering to be relatively unimportant as hot-statepoints are almost always 781inliner bugs. 782 783Concerns have been raised that the statepoint representation results in a 784large amount of IR being produced for some examples and that this 785contributes to higher than expected memory usage and compile times. There's 786no immediate plans to make changes due to this, but alternate models may be 787explored in the future. 788 789Relocations Along Exceptional Edges 790^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 791 792Relocations along exceptional paths are currently broken in ToT. In 793particular, there is current no way to represent a rethrow on a path which 794also has relocations. See `this llvm-dev discussion 795<https://groups.google.com/forum/#!topic/llvm-dev/AE417XjgxvI>`_ for more 796detail. 797 798Support for alternate stackmap formats 799^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 800 801For some use cases, it is 802desirable to directly encode a final memory efficient stackmap format for 803use by the runtime. This is particularly relevant for ahead of time 804compilers which wish to directly link object files without the need for 805post processing of each individual object file. While not implemented 806today for statepoints, there is precedent for a GCStrategy to be able to 807select a customer GCMetataPrinter for this purpose. Patches to enable 808this functionality upstream are welcome. 809 810Bugs and Enhancements 811===================== 812 813Currently known bugs and enhancements under consideration can be 814tracked by performing a `bugzilla search 815<https://bugs.llvm.org/buglist.cgi?cmdtype=runnamed&namedcmd=Statepoint%20Bugs&list_id=64342>`_ 816for [Statepoint] in the summary field. When filing new bugs, please 817use this tag so that interested parties see the newly filed bug. As 818with most LLVM features, design discussions take place on `llvm-dev 819<http://lists.llvm.org/mailman/listinfo/llvm-dev>`_, and patches 820should be sent to `llvm-commits 821<http://lists.llvm.org/mailman/listinfo/llvm-commits>`_ for review. 822 823