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 a 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 433 434Intrinsics 435=========== 436 437.. _gc_statepoint: 438 439'llvm.experimental.gc.statepoint' Intrinsic 440^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 441 442Syntax: 443""""""" 444 445:: 446 447 declare token 448 @llvm.experimental.gc.statepoint(i64 <id>, i32 <num patch bytes>, 449 func_type <target>, 450 i64 <#call args>, i64 <flags>, 451 ... (call parameters), 452 i64 <# transition args>, ... (transition parameters), 453 i64 <# deopt args>, ... (deopt parameters), 454 ... (gc parameters)) 455 456Overview: 457""""""""" 458 459The statepoint intrinsic represents a call which is parse-able by the 460runtime. 461 462Operands: 463""""""""" 464 465The 'id' operand is a constant integer that is reported as the ID 466field in the generated stackmap. LLVM does not interpret this 467parameter in any way and its meaning is up to the statepoint user to 468decide. Note that LLVM is free to duplicate code containing 469statepoint calls, and this may transform IR that had a unique 'id' per 470lexical call to statepoint to IR that does not. 471 472If 'num patch bytes' is non-zero then the call instruction 473corresponding to the statepoint is not emitted and LLVM emits 'num 474patch bytes' bytes of nops in its place. LLVM will emit code to 475prepare the function arguments and retrieve the function return value 476in accordance to the calling convention; the former before the nop 477sequence and the latter after the nop sequence. It is expected that 478the user will patch over the 'num patch bytes' bytes of nops with a 479calling sequence specific to their runtime before executing the 480generated machine code. There are no guarantees with respect to the 481alignment of the nop sequence. Unlike :doc:`StackMaps` statepoints do 482not have a concept of shadow bytes. Note that semantically the 483statepoint still represents a call or invoke to 'target', and the nop 484sequence after patching is expected to represent an operation 485equivalent to a call or invoke to 'target'. 486 487The 'target' operand is the function actually being called. The 488target can be specified as either a symbolic LLVM function, or as an 489arbitrary Value of appropriate function type. Note that the function 490type must match the signature of the callee and the types of the 'call 491parameters' arguments. 492 493The '#call args' operand is the number of arguments to the actual 494call. It must exactly match the number of arguments passed in the 495'call parameters' variable length section. 496 497The 'flags' operand is used to specify extra information about the 498statepoint. This is currently only used to mark certain statepoints 499as GC transitions. This operand is a 64-bit integer with the following 500layout, where bit 0 is the least significant bit: 501 502 +-------+---------------------------------------------------+ 503 | Bit # | Usage | 504 +=======+===================================================+ 505 | 0 | Set if the statepoint is a GC transition, cleared | 506 | | otherwise. | 507 +-------+---------------------------------------------------+ 508 | 1-63 | Reserved for future use; must be cleared. | 509 +-------+---------------------------------------------------+ 510 511The 'call parameters' arguments are simply the arguments which need to 512be passed to the call target. They will be lowered according to the 513specified calling convention and otherwise handled like a normal call 514instruction. The number of arguments must exactly match what is 515specified in '# call args'. The types must match the signature of 516'target'. 517 518The 'transition parameters' arguments contain an arbitrary list of 519Values which need to be passed to GC transition code. They will be 520lowered and passed as operands to the appropriate GC_TRANSITION nodes 521in the selection DAG. It is assumed that these arguments must be 522available before and after (but not necessarily during) the execution 523of the callee. The '# transition args' field indicates how many operands 524are to be interpreted as 'transition parameters'. 525 526The 'deopt parameters' arguments contain an arbitrary list of Values 527which is meaningful to the runtime. The '# deopt args' field 528indicates how many operands are to be interpreted as 'deopt parameters'. 529 530The 'gc parameters' arguments contain every pointer to a garbage 531collector object which potentially needs to be updated by the garbage 532collector. Note that the argument list must explicitly contain a base 533pointer for every derived pointer listed. The order of arguments is 534unimportant. Unlike the other variable length parameter sets, this 535list is not length prefixed. Use of the 'gc parameters' list is 536deprecated and will eventually be replaced entirely with the 537:ref:`gc-live <ob_gc_live>` operand bundle. 538 539Semantics: 540"""""""""" 541 542A statepoint is assumed to read and write all memory. As a result, 543memory operations can not be reordered past a statepoint. It is 544illegal to mark a statepoint as being either 'readonly' or 'readnone'. 545 546Note that legal IR can not perform any memory operation on a 'gc 547pointer' argument of the statepoint in a location statically reachable 548from the statepoint. Instead, the explicitly relocated value (from a 549``gc.relocate``) must be used. 550 551'llvm.experimental.gc.result' Intrinsic 552^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 553 554Syntax: 555""""""" 556 557:: 558 559 declare type* 560 @llvm.experimental.gc.result(token %statepoint_token) 561 562Overview: 563""""""""" 564 565``gc.result`` extracts the result of the original call instruction 566which was replaced by the ``gc.statepoint``. The ``gc.result`` 567intrinsic is actually a family of three intrinsics due to an 568implementation limitation. Other than the type of the return value, 569the semantics are the same. 570 571Operands: 572""""""""" 573 574The first and only argument is the ``gc.statepoint`` which starts 575the safepoint sequence of which this ``gc.result`` is a part. 576Despite the typing of this as a generic token, *only* the value defined 577by a ``gc.statepoint`` is legal here. 578 579Semantics: 580"""""""""" 581 582The ``gc.result`` represents the return value of the call target of 583the ``statepoint``. The type of the ``gc.result`` must exactly match 584the type of the target. If the call target returns void, there will 585be no ``gc.result``. 586 587A ``gc.result`` is modeled as a 'readnone' pure function. It has no 588side effects since it is just a projection of the return value of the 589previous call represented by the ``gc.statepoint``. 590 591'llvm.experimental.gc.relocate' Intrinsic 592^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 593 594Syntax: 595""""""" 596 597:: 598 599 declare <pointer type> 600 @llvm.experimental.gc.relocate(token %statepoint_token, 601 i32 %base_offset, 602 i32 %pointer_offset) 603 604Overview: 605""""""""" 606 607A ``gc.relocate`` returns the potentially relocated value of a pointer 608at the safepoint. 609 610Operands: 611""""""""" 612 613The first argument is the ``gc.statepoint`` which starts the 614safepoint sequence of which this ``gc.relocation`` is a part. 615Despite the typing of this as a generic token, *only* the value defined 616by a ``gc.statepoint`` is legal here. 617 618The second and third arguments are both indices into operands of their 619corresponding statepoint. If the statepoint has a :ref:`gc-live <ob_gc_live>` 620operand bundle, then both arguments are indices into the operand bundle's 621operands. If there is no "gc-live" bundle, then the index is into the 622statepoint's list of arguments. This index must land within the 'gc 623parameter' section of the statepoint's argument list. Use of the "gc-live" 624form is recommended. 625 626The second argument is an index which specifies the allocation for the pointer 627being relocated. The associated value must be within the object with which the 628pointer being relocated is associated. The optimizer is free to change *which* 629interior derived pointer is reported, provided that it does not replace an 630actual base pointer with another interior derived pointer. Collectors are 631allowed to rely on the base pointer operand remaining an actual base pointer if 632so constructed. 633 634The third argument is an index which specify the (potentially) derived pointer 635being relocated. It is legal for this index to be the same as the second 636argument if-and-only-if a base pointer is being relocated. 637 638Semantics: 639"""""""""" 640 641The return value of ``gc.relocate`` is the potentially relocated value 642of the pointer specified by its arguments. It is unspecified how the 643value of the returned pointer relates to the argument to the 644``gc.statepoint`` other than that a) it points to the same source 645language object with the same offset, and b) the 'based-on' 646relationship of the newly relocated pointers is a projection of the 647unrelocated pointers. In particular, the integer value of the pointer 648returned is unspecified. 649 650A ``gc.relocate`` is modeled as a ``readnone`` pure function. It has no 651side effects since it is just a way to extract information about work 652done during the actual call modeled by the ``gc.statepoint``. 653 654.. _statepoint-stackmap-format: 655 656Stack Map Format 657================ 658 659Locations for each pointer value which may need read and/or updated by 660the runtime or collector are provided in a separate section of the 661generated object file as specified in the PatchPoint documentation. 662This special section is encoded per the 663:ref:`Stack Map format <stackmap-format>`. 664 665The general expectation is that a JIT compiler will parse and discard this 666format; it is not particularly memory efficient. If you need an alternate 667format (e.g. for an ahead of time compiler), see discussion under 668:ref: `open work items <OpenWork>` below. 669 670Each statepoint generates the following Locations: 671 672* Constant which describes the calling convention of the call target. This 673 constant is a valid :ref:`calling convention identifier <callingconv>` for 674 the version of LLVM used to generate the stackmap. No additional compatibility 675 guarantees are made for this constant over what LLVM provides elsewhere w.r.t. 676 these identifiers. 677* Constant which describes the flags passed to the statepoint intrinsic 678* Constant which describes number of following deopt *Locations* (not 679 operands) 680* Variable number of Locations, one for each deopt parameter listed in 681 the IR statepoint (same number as described by previous Constant). At 682 the moment, only deopt parameters with a bitwidth of 64 bits or less 683 are supported. Values of a type larger than 64 bits can be specified 684 and reported only if a) the value is constant at the call site, and b) 685 the constant can be represented with less than 64 bits (assuming zero 686 extension to the original bitwidth). 687* Variable number of relocation records, each of which consists of 688 exactly two Locations. Relocation records are described in detail 689 below. 690 691Each relocation record provides sufficient information for a collector to 692relocate one or more derived pointers. Each record consists of a pair of 693Locations. The second element in the record represents the pointer (or 694pointers) which need updated. The first element in the record provides a 695pointer to the base of the object with which the pointer(s) being relocated is 696associated. This information is required for handling generalized derived 697pointers since a pointer may be outside the bounds of the original allocation, 698but still needs to be relocated with the allocation. Additionally: 699 700* It is guaranteed that the base pointer must also appear explicitly as a 701 relocation pair if used after the statepoint. 702* There may be fewer relocation records then gc parameters in the IR 703 statepoint. Each *unique* pair will occur at least once; duplicates 704 are possible. 705* The Locations within each record may either be of pointer size or a 706 multiple of pointer size. In the later case, the record must be 707 interpreted as describing a sequence of pointers and their corresponding 708 base pointers. If the Location is of size N x sizeof(pointer), then 709 there will be N records of one pointer each contained within the Location. 710 Both Locations in a pair can be assumed to be of the same size. 711 712Note that the Locations used in each section may describe the same 713physical location. e.g. A stack slot may appear as a deopt location, 714a gc base pointer, and a gc derived pointer. 715 716The LiveOut section of the StkMapRecord will be empty for a statepoint 717record. 718 719Safepoint Semantics & Verification 720================================== 721 722The fundamental correctness property for the compiled code's 723correctness w.r.t. the garbage collector is a dynamic one. It must be 724the case that there is no dynamic trace such that a operation 725involving a potentially relocated pointer is observably-after a 726safepoint which could relocate it. 'observably-after' is this usage 727means that an outside observer could observe this sequence of events 728in a way which precludes the operation being performed before the 729safepoint. 730 731To understand why this 'observable-after' property is required, 732consider a null comparison performed on the original copy of a 733relocated pointer. Assuming that control flow follows the safepoint, 734there is no way to observe externally whether the null comparison is 735performed before or after the safepoint. (Remember, the original 736Value is unmodified by the safepoint.) The compiler is free to make 737either scheduling choice. 738 739The actual correctness property implemented is slightly stronger than 740this. We require that there be no *static path* on which a 741potentially relocated pointer is 'observably-after' it may have been 742relocated. This is slightly stronger than is strictly necessary (and 743thus may disallow some otherwise valid programs), but greatly 744simplifies reasoning about correctness of the compiled code. 745 746By construction, this property will be upheld by the optimizer if 747correctly established in the source IR. This is a key invariant of 748the design. 749 750The existing IR Verifier pass has been extended to check most of the 751local restrictions on the intrinsics mentioned in their respective 752documentation. The current implementation in LLVM does not check the 753key relocation invariant, but this is ongoing work on developing such 754a verifier. Please ask on llvm-dev if you're interested in 755experimenting with the current version. 756 757.. _statepoint-utilities: 758 759Utility Passes for Safepoint Insertion 760====================================== 761 762.. _RewriteStatepointsForGC: 763 764RewriteStatepointsForGC 765^^^^^^^^^^^^^^^^^^^^^^^^ 766 767The pass RewriteStatepointsForGC transforms a function's IR to lower from the 768abstract machine model described above to the explicit statepoint model of 769relocations. To do this, it replaces all calls or invokes of functions which 770might contain a safepoint poll with a ``gc.statepoint`` and associated full 771relocation sequence, including all required ``gc.relocates``. 772 773Note that by default, this pass only runs for the "statepoint-example" or 774"core-clr" gc strategies. You will need to add your custom strategy to this 775list or use one of the predefined ones. 776 777As an example, given this code: 778 779.. code-block:: llvm 780 781 define i8 addrspace(1)* @test1(i8 addrspace(1)* %obj) 782 gc "statepoint-example" { 783 call void @foo() 784 ret i8 addrspace(1)* %obj 785 } 786 787The pass would produce this IR: 788 789.. code-block:: llvm 790 791 define i8 addrspace(1)* @test1(i8 addrspace(1)* %obj) 792 gc "statepoint-example" { 793 %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) 794 %obj.relocated = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %0, i32 12, i32 12) 795 ret i8 addrspace(1)* %obj.relocated 796 } 797 798In the above examples, the addrspace(1) marker on the pointers is the mechanism 799that the ``statepoint-example`` GC strategy uses to distinguish references from 800non references. The pass assumes that all addrspace(1) pointers are non-integral 801pointer types. Address space 1 is not globally reserved for this purpose. 802 803This pass can be used an utility function by a language frontend that doesn't 804want to manually reason about liveness, base pointers, or relocation when 805constructing IR. As currently implemented, RewriteStatepointsForGC must be 806run after SSA construction (i.e. mem2ref). 807 808RewriteStatepointsForGC will ensure that appropriate base pointers are listed 809for every relocation created. It will do so by duplicating code as needed to 810propagate the base pointer associated with each pointer being relocated to 811the appropriate safepoints. The implementation assumes that the following 812IR constructs produce base pointers: loads from the heap, addresses of global 813variables, function arguments, function return values. Constant pointers (such 814as null) are also assumed to be base pointers. In practice, this constraint 815can be relaxed to producing interior derived pointers provided the target 816collector can find the associated allocation from an arbitrary interior 817derived pointer. 818 819By default RewriteStatepointsForGC passes in ``0xABCDEF00`` as the statepoint 820ID and ``0`` as the number of patchable bytes to the newly constructed 821``gc.statepoint``. These values can be configured on a per-callsite 822basis using the attributes ``"statepoint-id"`` and 823``"statepoint-num-patch-bytes"``. If a call site is marked with a 824``"statepoint-id"`` function attribute and its value is a positive 825integer (represented as a string), then that value is used as the ID 826of the newly constructed ``gc.statepoint``. If a call site is marked 827with a ``"statepoint-num-patch-bytes"`` function attribute and its 828value is a positive integer, then that value is used as the 'num patch 829bytes' parameter of the newly constructed ``gc.statepoint``. The 830``"statepoint-id"`` and ``"statepoint-num-patch-bytes"`` attributes 831are not propagated to the ``gc.statepoint`` call or invoke if they 832could be successfully parsed. 833 834In practice, RewriteStatepointsForGC should be run much later in the pass 835pipeline, after most optimization is already done. This helps to improve 836the quality of the generated code when compiled with garbage collection support. 837 838.. _PlaceSafepoints: 839 840PlaceSafepoints 841^^^^^^^^^^^^^^^^ 842 843The pass PlaceSafepoints inserts safepoint polls sufficient to ensure running 844code checks for a safepoint request on a timely manner. This pass is expected 845to be run before RewriteStatepointsForGC and thus does not produce full 846relocation sequences. 847 848As an example, given input IR of the following: 849 850.. code-block:: llvm 851 852 define void @test() gc "statepoint-example" { 853 call void @foo() 854 ret void 855 } 856 857 declare void @do_safepoint() 858 define void @gc.safepoint_poll() { 859 call void @do_safepoint() 860 ret void 861 } 862 863 864This pass would produce the following IR: 865 866.. code-block:: llvm 867 868 define void @test() gc "statepoint-example" { 869 call void @do_safepoint() 870 call void @foo() 871 ret void 872 } 873 874In this case, we've added an (unconditional) entry safepoint poll. Note that 875despite appearances, the entry poll is not necessarily redundant. We'd have to 876know that ``foo`` and ``test`` were not mutually recursive for the poll to be 877redundant. In practice, you'd probably want to your poll definition to contain 878a conditional branch of some form. 879 880At the moment, PlaceSafepoints can insert safepoint polls at method entry and 881loop backedges locations. Extending this to work with return polls would be 882straight forward if desired. 883 884PlaceSafepoints includes a number of optimizations to avoid placing safepoint 885polls at particular sites unless needed to ensure timely execution of a poll 886under normal conditions. PlaceSafepoints does not attempt to ensure timely 887execution of a poll under worst case conditions such as heavy system paging. 888 889The implementation of a safepoint poll action is specified by looking up a 890function of the name ``gc.safepoint_poll`` in the containing Module. The body 891of this function is inserted at each poll site desired. While calls or invokes 892inside this method are transformed to a ``gc.statepoints``, recursive poll 893insertion is not performed. 894 895This pass is useful for any language frontend which only has to support 896garbage collection semantics at safepoints. If you need other abstract 897frame information at safepoints (e.g. for deoptimization or introspection), 898you can insert safepoint polls in the frontend. If you have the later case, 899please ask on llvm-dev for suggestions. There's been a good amount of work 900done on making such a scheme work well in practice which is not yet documented 901here. 902 903 904Supported Architectures 905======================= 906 907Support for statepoint generation requires some code for each backend. 908Today, only X86_64 is supported. 909 910.. _OpenWork: 911 912Limitations and Half Baked Ideas 913================================ 914 915Mixing References and Raw Pointers 916^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 917 918Support for languages which allow unmanaged pointers to garbage collected 919objects (i.e. pass a pointer to an object to a C routine) in the abstract 920machine model. At the moment, the best idea on how to approach this 921involves an intrinsic or opaque function which hides the connection between 922the reference value and the raw pointer. The problem is that having a 923ptrtoint or inttoptr cast (which is common for such use cases) breaks the 924rules used for inferring base pointers for arbitrary references when 925lowering out of the abstract model to the explicit physical model. Note 926that a frontend which lowers directly to the physical model doesn't have 927any problems here. 928 929Objects on the Stack 930^^^^^^^^^^^^^^^^^^^^ 931 932As noted above, the explicit lowering supports objects allocated on the 933stack provided the collector can find a heap map given the stack address. 934 935The missing pieces are a) integration with rewriting (RS4GC) from the 936abstract machine model and b) support for optionally decomposing on stack 937objects so as not to require heap maps for them. The later is required 938for ease of integration with some collectors. 939 940Lowering Quality and Representation Overhead 941^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 942 943The current statepoint lowering is known to be somewhat poor. In the very 944long term, we'd like to integrate statepoints with the register allocator; 945in the near term this is unlikely to happen. We've found the quality of 946lowering to be relatively unimportant as hot-statepoints are almost always 947inliner bugs. 948 949Concerns have been raised that the statepoint representation results in a 950large amount of IR being produced for some examples and that this 951contributes to higher than expected memory usage and compile times. There's 952no immediate plans to make changes due to this, but alternate models may be 953explored in the future. 954 955Relocations Along Exceptional Edges 956^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 957 958Relocations along exceptional paths are currently broken in ToT. In 959particular, there is current no way to represent a rethrow on a path which 960also has relocations. See `this llvm-dev discussion 961<https://groups.google.com/forum/#!topic/llvm-dev/AE417XjgxvI>`_ for more 962detail. 963 964Support for alternate stackmap formats 965^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 966 967For some use cases, it is 968desirable to directly encode a final memory efficient stackmap format for 969use by the runtime. This is particularly relevant for ahead of time 970compilers which wish to directly link object files without the need for 971post processing of each individual object file. While not implemented 972today for statepoints, there is precedent for a GCStrategy to be able to 973select a customer GCMetataPrinter for this purpose. Patches to enable 974this functionality upstream are welcome. 975 976Bugs and Enhancements 977===================== 978 979Currently known bugs and enhancements under consideration can be 980tracked by performing a `bugzilla search 981<https://bugs.llvm.org/buglist.cgi?cmdtype=runnamed&namedcmd=Statepoint%20Bugs&list_id=64342>`_ 982for [Statepoint] in the summary field. When filing new bugs, please 983use this tag so that interested parties see the newly filed bug. As 984with most LLVM features, design discussions take place on `llvm-dev 985<http://lists.llvm.org/mailman/listinfo/llvm-dev>`_, and patches 986should be sent to `llvm-commits 987<http://lists.llvm.org/mailman/listinfo/llvm-commits>`_ for review. 988 989