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