1 =====================================
2 Garbage Collection Safepoints in LLVM
3 =====================================
12 This document describes a set of experimental extensions to LLVM. Use
13 with caution. Because the intrinsics have experimental status,
14 compatibility across LLVM releases is not guaranteed.
16 LLVM currently supports an alternate mechanism for conservative
17 garbage collection support using the ``gcroot`` intrinsic. The mechanism
18 described here shares little in common with the alternate ``gcroot``
19 implementation and it is hoped that this mechanism will eventually
20 replace the gc_root mechanism.
25 To collect dead objects, garbage collectors must be able to identify
26 any references to objects contained within executing code, and,
27 depending on the collector, potentially update them. The collector
28 does not need this information at all points in code - that would make
29 the problem much harder - but only at well-defined points in the
30 execution known as 'safepoints' For most collectors, it is sufficient
31 to track at least one copy of each unique pointer value. However, for
32 a collector which wishes to relocate objects directly reachable from
33 running code, a higher standard is required.
35 One additional challenge is that the compiler may compute intermediate
36 results ("derived pointers") which point outside of the allocation or
37 even into the middle of another allocation. The eventual use of this
38 intermediate value must yield an address within the bounds of the
39 allocation, but such "exterior derived pointers" may be visible to the
40 collector. Given this, a garbage collector can not safely rely on the
41 runtime value of an address to indicate the object it is associated
42 with. If the garbage collector wishes to move any object, the
43 compiler must provide a mapping, for each pointer, to an indication of
46 To simplify the interaction between a collector and the compiled code,
47 most garbage collectors are organized in terms of three abstractions:
48 load barriers, store barriers, and safepoints.
50 #. A load barrier is a bit of code executed immediately after the
51 machine load instruction, but before any use of the value loaded.
52 Depending on the collector, such a barrier may be needed for all
53 loads, merely loads of a particular type (in the original source
54 language), or none at all.
56 #. Analogously, a store barrier is a code fragement that runs
57 immediately before the machine store instruction, but after the
58 computation of the value stored. The most common use of a store
59 barrier is to update a 'card table' in a generational garbage
62 #. A safepoint is a location at which pointers visible to the compiled
63 code (i.e. currently in registers or on the stack) are allowed to
64 change. After the safepoint completes, the actual pointer value
65 may differ, but the 'object' (as seen by the source language)
68 Note that the term 'safepoint' is somewhat overloaded. It refers to
69 both the location at which the machine state is parsable and the
70 coordination protocol involved in bring application threads to a
71 point at which the collector can safely use that information. The
72 term "statepoint" as used in this document refers exclusively to the
75 This document focuses on the last item - compiler support for
76 safepoints in generated code. We will assume that an outside
77 mechanism has decided where to place safepoints. From our
78 perspective, all safepoints will be function calls. To support
79 relocation of objects directly reachable from values in compiled code,
80 the collector must be able to:
82 #. identify every copy of a pointer (including copies introduced by
83 the compiler itself) at the safepoint,
84 #. identify which object each pointer relates to, and
85 #. potentially update each of those copies.
87 This document describes the mechanism by which an LLVM based compiler
88 can provide this information to a language runtime/collector, and
89 ensure that all pointers can be read and updated if desired. The
90 heart of the approach is to construct (or rewrite) the IR in a manner
91 where the possible updates performed by the garbage collector are
92 explicitly visible in the IR. Doing so requires that we:
94 #. create a new SSA value for each potentially relocated pointer, and
95 ensure that no uses of the original (non relocated) value is
96 reachable after the safepoint,
97 #. specify the relocation in a way which is opaque to the compiler to
98 ensure that the optimizer can not introduce new uses of an
99 unrelocated value after a statepoint. This prevents the optimizer
100 from performing unsound optimizations.
101 #. recording a mapping of live pointers (and the allocation they're
102 associated with) for each statepoint.
104 At the most abstract level, inserting a safepoint can be thought of as
105 replacing a call instruction with a call to a multiple return value
106 function which both calls the original target of the call, returns
107 it's result, and returns updated values for any live pointers to
108 garbage collected objects.
110 Note that the task of identifying all live pointers to garbage
111 collected values, transforming the IR to expose a pointer giving the
112 base object for every such live pointer, and inserting all the
113 intrinsics correctly is explicitly out of scope for this document.
114 The recommended approach is to use the :ref:`utility passes
115 <statepoint-utilities>` described below.
117 This abstract function call is concretely represented by a sequence of
118 intrinsic calls known as a 'statepoint sequence'.
121 Let's consider a simple call in LLVM IR:
124 Depending on our language we may need to allow a safepoint during the
125 execution of the function called from this site. If so, we need to
126 let the collector update local values in the current frame.
128 Let's say we need to relocate SSA values 'a', 'b', and 'c' at this
129 safepoint. To represent this, we would generate the statepoint
134 Ideally, this sequence would have been represented as a M argument, N
135 return value function (where M is the number of values being
136 relocated + the original call arguments and N is the original return
137 value + each relocated value), but LLVM does not easily support such a
140 Instead, the statepoint intrinsic marks the actual site of the
141 safepoint or statepoint. The statepoint returns a token value (which
142 exists only at compile time). To get back the original return value
143 of the call, we use the 'gc.result' intrinsic. To get the relocation
144 of each pointer in turn, we use the 'gc.relocate' intrinsic with the
145 appropriate index. Note that both the gc.relocate and gc.result are
146 tied to the statepoint. The combination forms a "statepoint sequence"
147 and represents the entitety of a parseable call or 'statepoint'.
149 When lowered, this example would generate the following x86 assembly::
152 Each of the potentially relocated values has been spilled to the
153 stack, and a record of that location has been recorded to the
154 :ref: `Stack Map section <stackmap-section>`. If the garbage collector
155 needs to update any of these pointers during the call, it knows
156 exactly what to change.
161 'llvm.experimental.gc.statepoint' Intrinsic
162 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
170 @llvm.experimental.gc.statepoint(func_type <target>,
171 i64 <#call args>. i64 <unused>,
172 ... (call parameters),
173 i64 <# deopt args>, ... (deopt parameters),
179 The statepoint intrinsic represents a call which is parse-able by the
185 The 'target' operand is the function actually being called. The
186 target can be specified as either a symbolic LLVM function, or as an
187 arbitrary Value of appropriate function type. Note that the function
188 type must match the signature of the callee and the types of the 'call
189 parameters' arguments.
191 The '#call args' operand is the number of arguments to the actual
192 call. It must exactly match the number of arguments passed in the
193 'call parameters' variable length section.
195 The 'unused' operand is unused and likely to be removed. Please do
198 The 'call parameters' arguments are simply the arguments which need to
199 be passed to the call target. They will be lowered according to the
200 specified calling convention and otherwise handled like a normal call
201 instruction. The number of arguments must exactly match what is
202 specified in '# call args'. The types must match the signature of
205 The 'deopt parameters' arguments contain an arbitrary list of Values
206 which is meaningful to the runtime. The runtime may read any of these
207 values, but is assumed not to modify them. If the garbage collector
208 might need to modify one of these values, it must also be listed in
209 the 'gc pointer' argument list. The '# deopt args' field indicates
210 how many operands are to be interpreted as 'deopt parameters'.
212 The 'gc parameters' arguments contain every pointer to a garbage
213 collector object which potentially needs to be updated by the garbage
214 collector. Note that the argument list must explicitly contain a base
215 pointer for every derived pointer listed. The order of arguments is
216 unimportant. Unlike the other variable length parameter sets, this
217 list is not length prefixed.
222 A statepoint is assumed to read and write all memory. As a result,
223 memory operations can not be reordered past a statepoint. It is
224 illegal to mark a statepoint as being either 'readonly' or 'readnone'.
226 Note that legal IR can not perform any memory operation on a 'gc
227 pointer' argument of the statepoint in a location statically reachable
228 from the statepoint. Instead, the explicitly relocated value (from a
229 ``gc.relocate``) must be used.
231 'llvm.experimental.gc.result' Intrinsic
232 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
240 @llvm.experimental.gc.result(i32 %statepoint_token)
245 ``gc.result`` extracts the result of the original call instruction
246 which was replaced by the ``gc.statepoint``. The ``gc.result``
247 intrinsic is actually a family of three intrinsics due to an
248 implementation limitation. Other than the type of the return value,
249 the semantics are the same.
254 The first and only argument is the ``gc.statepoint`` which starts
255 the safepoint sequence of which this ``gc.result`` is a part.
256 Despite the typing of this as a generic i32, *only* the value defined
257 by a ``gc.statepoint`` is legal here.
262 The ``gc.result`` represents the return value of the call target of
263 the ``statepoint``. The type of the ``gc.result`` must exactly match
264 the type of the target. If the call target returns void, there will
267 A ``gc.result`` is modeled as a 'readnone' pure function. It has no
268 side effects since it is just a projection of the return value of the
269 previous call represented by the ``gc.statepoint``.
271 'llvm.experimental.gc.relocate' Intrinsic
272 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
279 declare <pointer type>
280 @llvm.experimental.gc.relocate(i32 %statepoint_token,
287 A ``gc.relocate`` returns the potentially relocated value of a pointer
293 The first argument is the ``gc.statepoint`` which starts the
294 safepoint sequence of which this ``gc.relocation`` is a part.
295 Despite the typing of this as a generic i32, *only* the value defined
296 by a ``gc.statepoint`` is legal here.
298 The second argument is an index into the statepoints list of arguments
299 which specifies the base pointer for the pointer being relocated.
300 This index must land within the 'gc parameter' section of the
301 statepoint's argument list.
303 The third argument is an index into the statepoint's list of arguments
304 which specify the (potentially) derived pointer being relocated. It
305 is legal for this index to be the same as the second argument
306 if-and-only-if a base pointer is being relocated. This index must land
307 within the 'gc parameter' section of the statepoint's argument list.
312 The return value of ``gc.relocate`` is the potentially relocated value
313 of the pointer specified by it's arguments. It is unspecified how the
314 value of the returned pointer relates to the argument to the
315 ``gc.statepoint`` other than that a) it points to the same source
316 language object with the same offset, and b) the 'based-on'
317 relationship of the newly relocated pointers is a projection of the
318 unrelocated pointers. In particular, the integer value of the pointer
319 returned is unspecified.
321 A ``gc.relocate`` is modeled as a ``readnone`` pure function. It has no
322 side effects since it is just a way to extract information about work
323 done during the actual call modeled by the ``gc.statepoint``.
329 Locations for each pointer value which may need read and/or updated by
330 the runtime or collector are provided via the :ref:`Stack Map format
331 <stackmap-format>` specified in the PatchPoint documentation.
333 Each statepoint generates the following Locations:
335 * Constant which describes number of following deopt *Locations* (not
337 * Variable number of Locations, one for each deopt parameter listed in
338 the IR statepoint (same number as described by previous Constant)
339 * Variable number of Locations pairs, one pair for each unique pointer
340 which needs relocated. The first Location in each pair describes
341 the base pointer for the object. The second is the derived pointer
342 actually being relocated. It is guaranteed that the base pointer
343 must also appear explicitly as a relocation pair if used after the
344 statepoint. There may be fewer pairs then gc parameters in the IR
345 statepoint. Each *unique* pair will occur at least once; duplicates
348 Note that the Locations used in each section may describe the same
349 physical location. e.g. A stack slot may appear as a deopt location,
350 a gc base pointer, and a gc derived pointer.
352 The ID field of the 'StkMapRecord' for a statepoint is meaningless and
353 it's value is explicitly unspecified.
355 The LiveOut section of the StkMapRecord will be empty for a statepoint
358 Safepoint Semantics & Verification
359 ==================================
361 The fundamental correctness property for the compiled code's
362 correctness w.r.t. the garbage collector is a dynamic one. It must be
363 the case that there is no dynamic trace such that a operation
364 involving a potentially relocated pointer is observably-after a
365 safepoint which could relocate it. 'observably-after' is this usage
366 means that an outside observer could observe this sequence of events
367 in a way which precludes the operation being performed before the
370 To understand why this 'observable-after' property is required,
371 consider a null comparison performed on the original copy of a
372 relocated pointer. Assuming that control flow follows the safepoint,
373 there is no way to observe externally whether the null comparison is
374 performed before or after the safepoint. (Remember, the original
375 Value is unmodified by the safepoint.) The compiler is free to make
376 either scheduling choice.
378 The actual correctness property implemented is slightly stronger than
379 this. We require that there be no *static path* on which a
380 potentially relocated pointer is 'observably-after' it may have been
381 relocated. This is slightly stronger than is strictly necessary (and
382 thus may disallow some otherwise valid programs), but greatly
383 simplifies reasoning about correctness of the compiled code.
385 By construction, this property will be upheld by the optimizer if
386 correctly established in the source IR. This is a key invariant of
389 The existing IR Verifier pass has been extended to check most of the
390 local restrictions on the intrinsics mentioned in their respective
391 documentation. The current implementation in LLVM does not check the
392 key relocation invariant, but this is ongoing work on developing such
393 a verifier. Please ask on llvmdev if you're interested in
394 experimenting with the current version.
396 .. _statepoint-utilities:
398 Utility Passes for Safepoint Insertion
399 ======================================
401 .. _RewriteStatepointsForGC:
403 RewriteStatepointsForGC
404 ^^^^^^^^^^^^^^^^^^^^^^^^
406 The pass RewriteStatepointsForGC transforms a functions IR by replacing a
407 ``gc.statepoint`` (with an optional ``gc.result``) with a full relocation
408 sequence, including all required ``gc.relocates``. To function, the pass
409 requires that the GC strategy specified for the function be able to reliably
410 distinguish between GC references and non-GC references in IR it is given.
412 As an example, given this code:
416 define i8 addrspace(1)* @test1(i8 addrspace(1)* %obj)
417 gc "statepoint-example" {
418 call i32 (void ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_isVoidf(void ()* @foo, i32 0, i32 0, i32 5, i32 0, i32 -1, i32 0, i32 0, i32 0)
419 ret i8 addrspace(1)* %obj
422 The pass would produce this IR:
426 define i8 addrspace(1)* @test1(i8 addrspace(1)* %obj)
427 gc "statepoint-example" {
428 %0 = call i32 (void ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_isVoidf(void ()* @foo, i32 0, i32 0, i32 5, i32 0, i32 -1, i32 0, i32 0, i32 0, i8 addrspace(1)* %obj)
429 %obj.relocated = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(i32 %0, i32 9, i32 9)
430 ret i8 addrspace(1)* %obj.relocated
433 In the above examples, the addrspace(1) marker on the pointers is the mechanism
434 that the ``statepoint-example`` GC strategy uses to distinguish references from
435 non references. Address space 1 is not globally reserved for this purpose.
437 This pass can be used an utility function by a language frontend that doesn't
438 want to manually reason about liveness, base pointers, or relocation when
439 constructing IR. As currently implemented, RewriteStatepointsForGC must be
440 run after SSA construction (i.e. mem2ref).
443 In practice, RewriteStatepointsForGC can be run much later in the pass
444 pipeline, after most optimization is already done. This helps to improve
445 the quality of the generated code when compiled with garbage collection support.
446 In the long run, this is the intended usage model. At this time, a few details
447 have yet to be worked out about the semantic model required to guarantee this
448 is always correct. As such, please use with caution and report bugs.
455 The pass PlaceSafepoints transforms a function's IR by replacing any call or
456 invoke instructions with appropriate ``gc.statepoint`` and ``gc.result`` pairs,
457 and inserting safepoint polls sufficient to ensure running code checks for a
458 safepoint request on a timely manner. This pass is expected to be run before
459 RewriteStatepointsForGC and thus does not produce full relocation sequences.
461 At the moment, PlaceSafepoints can insert safepoint polls at method entry and
462 loop backedges locations. Extending this to work with return polls would be
463 straight forward if desired.
465 PlaceSafepoints includes a number of optimizations to avoid placing safepoint
466 polls at particular sites unless needed to ensure timely execution of a poll
467 under normal conditions. PlaceSafepoints does not attempt to ensure timely
468 execution of a poll under worst case conditions such as heavy system paging.
470 The implementation of a safepoint poll action is specified by looking up a
471 function of the name ``gc.safepoint_poll`` in the containing Module. The body
472 of this function is inserted at each poll site desired. While calls or invokes
473 inside this method are transformed to a ``gc.statepoints``, recursive poll
474 insertion is not performed.
476 If you are scheduling the RewriteStatepointsForGC pass late in the pass order,
477 you should probably schedule this pass immediately before it. The exception
478 would be if you need to preserve abstract frame information (e.g. for
479 deoptimization or introspection) at safepoints. In that case, ask on the
480 llvmdev mailing list for suggestions.
483 Bugs and Enhancements
484 =====================
486 Currently known bugs and enhancements under consideration can be
487 tracked by performing a `bugzilla search
488 <http://llvm.org/bugs/buglist.cgi?cmdtype=runnamed&namedcmd=Statepoint%20Bugs&list_id=64342>`_
489 for [Statepoint] in the summary field. When filing new bugs, please
490 use this tag so that interested parties see the newly filed bug. As
491 with most LLVM features, design discussions take place on `llvmdev
492 <http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev>`_, and patches
493 should be sent to `llvm-commits
494 <http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits>`_ for review.