blob: d6576293dbdac114114f0568827d54d247edf24b [file] [log] [blame]
Philip Reamesf6123222014-12-02 19:37:00 +00001=====================================
2Garbage Collection Safepoints in LLVM
3=====================================
4
5.. contents::
6 :local:
7 :depth: 2
8
9Status
10=======
11
Philip Reamesdfc238b2015-01-02 19:46:49 +000012This document describes a set of experimental extensions to LLVM. Use
13with caution. Because the intrinsics have experimental status,
14compatibility across LLVM releases is not guaranteed.
Philip Reamesf6123222014-12-02 19:37:00 +000015
Philip Reamesdfc238b2015-01-02 19:46:49 +000016LLVM currently supports an alternate mechanism for conservative
Philip Reamese0dd0f22015-02-25 00:18:04 +000017garbage collection support using the ``gcroot`` intrinsic. The mechanism
18described here shares little in common with the alternate ``gcroot``
Philip Reamesdfc238b2015-01-02 19:46:49 +000019implementation and it is hoped that this mechanism will eventually
20replace the gc_root mechanism.
Philip Reamesf6123222014-12-02 19:37:00 +000021
22Overview
23========
24
Philip Reamesdfc238b2015-01-02 19:46:49 +000025To collect dead objects, garbage collectors must be able to identify
26any references to objects contained within executing code, and,
27depending on the collector, potentially update them. The collector
28does not need this information at all points in code - that would make
29the problem much harder - but only at well-defined points in the
30execution known as 'safepoints' For most collectors, it is sufficient
31to track at least one copy of each unique pointer value. However, for
32a collector which wishes to relocate objects directly reachable from
33running code, a higher standard is required.
Philip Reamesf6123222014-12-02 19:37:00 +000034
Philip Reamesdfc238b2015-01-02 19:46:49 +000035One additional challenge is that the compiler may compute intermediate
36results ("derived pointers") which point outside of the allocation or
37even into the middle of another allocation. The eventual use of this
38intermediate value must yield an address within the bounds of the
39allocation, but such "exterior derived pointers" may be visible to the
40collector. Given this, a garbage collector can not safely rely on the
41runtime value of an address to indicate the object it is associated
42with. If the garbage collector wishes to move any object, the
43compiler must provide a mapping, for each pointer, to an indication of
44its allocation.
Philip Reamesf6123222014-12-02 19:37:00 +000045
Philip Reamesdfc238b2015-01-02 19:46:49 +000046To simplify the interaction between a collector and the compiled code,
47most garbage collectors are organized in terms of three abstractions:
48load barriers, store barriers, and safepoints.
Philip Reamesf6123222014-12-02 19:37:00 +000049
Philip Reamesdfc238b2015-01-02 19:46:49 +000050#. 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.
Philip Reamesf6123222014-12-02 19:37:00 +000055
Philip Reamesdfc238b2015-01-02 19:46:49 +000056#. 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
60 collector.
Philip Reamesf6123222014-12-02 19:37:00 +000061
Philip Reamesdfc238b2015-01-02 19:46:49 +000062#. 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)
66 pointed to will not.
Philip Reamesf6123222014-12-02 19:37:00 +000067
Philip Reamesdfc238b2015-01-02 19:46:49 +000068 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
73 former.
Philip Reamesf6123222014-12-02 19:37:00 +000074
Philip Reamesdfc238b2015-01-02 19:46:49 +000075This document focuses on the last item - compiler support for
76safepoints in generated code. We will assume that an outside
77mechanism has decided where to place safepoints. From our
78perspective, all safepoints will be function calls. To support
79relocation of objects directly reachable from values in compiled code,
80the collector must be able to:
81
82#. identify every copy of a pointer (including copies introduced by
83 the compiler itself) at the safepoint,
Philip Reamesf6123222014-12-02 19:37:00 +000084#. identify which object each pointer relates to, and
85#. potentially update each of those copies.
86
Philip Reamesdfc238b2015-01-02 19:46:49 +000087This document describes the mechanism by which an LLVM based compiler
88can provide this information to a language runtime/collector, and
89ensure that all pointers can be read and updated if desired. The
90heart of the approach is to construct (or rewrite) the IR in a manner
91where the possible updates performed by the garbage collector are
92explicitly visible in the IR. Doing so requires that we:
Philip Reamesf6123222014-12-02 19:37:00 +000093
Philip Reamesdfc238b2015-01-02 19:46:49 +000094#. 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.
Philip Reamesf6123222014-12-02 19:37:00 +0000103
Philip Reamesdfc238b2015-01-02 19:46:49 +0000104At the most abstract level, inserting a safepoint can be thought of as
105replacing a call instruction with a call to a multiple return value
106function which both calls the original target of the call, returns
107it's result, and returns updated values for any live pointers to
108garbage collected objects.
Philip Reamesf6123222014-12-02 19:37:00 +0000109
Philip Reamesdfc238b2015-01-02 19:46:49 +0000110 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.
Philip Reamesc88d7322015-02-25 01:23:59 +0000114 The recommended approach is to use the :ref:`utility passes
115 <statepoint-utilities>` described below.
Philip Reamesf6123222014-12-02 19:37:00 +0000116
Philip Reamesdfc238b2015-01-02 19:46:49 +0000117This abstract function call is concretely represented by a sequence of
Philip Reames5017ab52015-02-26 01:18:21 +0000118intrinsic calls known collectively as a "statepoint relocation sequence".
Philip Reamesf6123222014-12-02 19:37:00 +0000119
120Let's consider a simple call in LLVM IR:
Philip Reamesf6123222014-12-02 19:37:00 +0000121
Philip Reames5017ab52015-02-26 01:18:21 +0000122.. code-block:: llvm
Philip Reamesf6123222014-12-02 19:37:00 +0000123
Philip Reames5017ab52015-02-26 01:18:21 +0000124 define i8 addrspace(1)* @test1(i8 addrspace(1)* %obj)
125 gc "statepoint-example" {
126 call void ()* @foo()
127 ret i8 addrspace(1)* %obj
128 }
Philip Reamesf6123222014-12-02 19:37:00 +0000129
Philip Reames5017ab52015-02-26 01:18:21 +0000130Depending on our language we may need to allow a safepoint during the execution
131of ``foo``. If so, we need to let the collector update local values in the
132current frame. If we don't, we'll be accessing a potential invalid reference
133once we eventually return from the call.
134
135In this example, we need to relocate the SSA value ``%obj``. Since we can't
136actually change the value in the SSA value ``%obj``, we need to introduce a new
137SSA value ``%obj.relocated`` which represents the potentially changed value of
138``%obj`` after the safepoint and update any following uses appropriately. The
139resulting relocation sequence is:
140
141.. code-block:: llvm
142
143 define i8 addrspace(1)* @test1(i8 addrspace(1)* %obj)
144 gc "statepoint-example" {
Pat Gavlincc0431d2015-05-08 18:07:42 +0000145 %0 = call i32 (void ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_isVoidf(void ()* @foo, i32 0, i32 0, i32 0, i8 addrspace(1)* %obj)
146 %obj.relocated = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(i32 %0, i32 4, i32 4)
Philip Reames5017ab52015-02-26 01:18:21 +0000147 ret i8 addrspace(1)* %obj.relocated
148 }
Philip Reamesf6123222014-12-02 19:37:00 +0000149
Philip Reamesdfc238b2015-01-02 19:46:49 +0000150Ideally, this sequence would have been represented as a M argument, N
151return value function (where M is the number of values being
152relocated + the original call arguments and N is the original return
153value + each relocated value), but LLVM does not easily support such a
154representation.
155
156Instead, the statepoint intrinsic marks the actual site of the
157safepoint or statepoint. The statepoint returns a token value (which
158exists only at compile time). To get back the original return value
Philip Reames5017ab52015-02-26 01:18:21 +0000159of the call, we use the ``gc.result`` intrinsic. To get the relocation
160of each pointer in turn, we use the ``gc.relocate`` intrinsic with the
161appropriate index. Note that both the ``gc.relocate`` and ``gc.result`` are
162tied to the statepoint. The combination forms a "statepoint relocation
163sequence" and represents the entitety of a parseable call or 'statepoint'.
Philip Reamesf6123222014-12-02 19:37:00 +0000164
Philip Reames5017ab52015-02-26 01:18:21 +0000165When lowered, this example would generate the following x86 assembly:
166
167.. code-block:: gas
168
169 .globl test1
170 .align 16, 0x90
171 pushq %rax
172 callq foo
173 .Ltmp1:
174 movq (%rsp), %rax # This load is redundant (oops!)
175 popq %rdx
176 retq
Philip Reamesf6123222014-12-02 19:37:00 +0000177
Philip Reamesdfc238b2015-01-02 19:46:49 +0000178Each of the potentially relocated values has been spilled to the
179stack, and a record of that location has been recorded to the
Philip Reames5017ab52015-02-26 01:18:21 +0000180:ref:`Stack Map section <stackmap-section>`. If the garbage collector
Philip Reamesdfc238b2015-01-02 19:46:49 +0000181needs to update any of these pointers during the call, it knows
182exactly what to change.
Philip Reamesf6123222014-12-02 19:37:00 +0000183
Philip Reames5017ab52015-02-26 01:18:21 +0000184The relevant parts of the StackMap section for our example are:
185
186.. code-block:: gas
187
188 # This describes the call site
189 # Stack Maps: callsite 2882400000
190 .quad 2882400000
191 .long .Ltmp1-test1
192 .short 0
193 # .. 8 entries skipped ..
194 # This entry describes the spill slot which is directly addressable
195 # off RSP with offset 0. Given the value was spilled with a pushq,
196 # that makes sense.
197 # Stack Maps: Loc 8: Direct RSP [encoding: .byte 2, .byte 8, .short 7, .int 0]
198 .byte 2
199 .byte 8
200 .short 7
201 .long 0
202
203This example was taken from the tests for the :ref:`RewriteStatepointsForGC` utility pass. As such, it's full StackMap can be easily examined with the following command.
204
205.. code-block:: bash
206
207 opt -rewrite-statepoints-for-gc test/Transforms/RewriteStatepointsForGC/basics.ll -S | llc -debug-only=stackmaps
208
209
Pat Gavlincc0431d2015-05-08 18:07:42 +0000210GC Transitions
211^^^^^^^^^^^^^^^^^^
Philip Reames5017ab52015-02-26 01:18:21 +0000212
Pat Gavlincc0431d2015-05-08 18:07:42 +0000213As a practical consideration, many garbage-collected systems allow code that is
214collector-aware ("managed code") to call code that is not collector-aware
215("unmanaged code"). It is common that such calls must also be safepoints, since
216it is desirable to allow the collector to run during the execution of
217unmanaged code. Futhermore, it is common that coordinating the transition from
218managed to unmanaged code requires extra code generation at the call site to
219inform the collector of the transition. In order to support these needs, a
220statepoint may be marked as a GC transition, and data that is necessary to
221perform the transition (if any) may be provided as additional arguments to the
222statepoint.
223
224 Note that although in many cases statepoints may be inferred to be GC
225 transitions based on the function symbols involved (e.g. a call from a
226 function with GC strategy "foo" to a function with GC strategy "bar"),
227 indirect calls that are also GC transitions must also be supported. This
228 requirement is the driving force behing the decision to require that GC
229 transitions are explicitly marked.
230
231Let's revisit the sample given above, this time treating the call to ``@foo``
232as a GC transition. Depending on our target, the transition code may need to
233access some extra state in order to inform the collector of the transition.
234Let's assume a hypothetical GC--somewhat unimaginatively named "hypothetical-gc"
235--that requires that a TLS variable must be written to before and after a call
236to unmanaged code. The resulting relocation sequence is:
237
238.. code-block:: llvm
239
240 @flag = thread_local global i32 0, align 4
241
242 define i8 addrspace(1)* @test1(i8 addrspace(1) *%obj)
243 gc "hypothetical-gc" {
244
245 %0 = call i32 (void ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_isVoidf(void ()* @foo, i32 0, i32 1, i32* @Flag, i32 0, i8 addrspace(1)* %obj)
246 %obj.relocated = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(i32 %0, i32 4, i32 4)
247 ret i8 addrspace(1)* %obj.relocated
248 }
249
250During lowering, this will result in a instruction selection DAG that looks
251something like:
252
Pat Gavlin7afaed22015-05-08 18:37:49 +0000253::
Pat Gavlincc0431d2015-05-08 18:07:42 +0000254
255 CALLSEQ_START
256 ...
257 GC_TRANSITION_START (lowered i32 *@Flag), SRCVALUE i32* Flag
258 STATEPOINT
259 GC_TRANSITION_END (lowered i32 *@Flag), SRCVALUE i32 *Flag
260 ...
261 CALLSEQ_END
262
263In order to generate the necessary transition code, the backend for each target
264supported by "hypothetical-gc" must be modified to lower ``GC_TRANSITION_START``
265and ``GC_TRANSITION_END`` nodes appropriately when the "hypothetical-gc"
266strategy is in use for a particular function. Assuming that such lowering has
267been added for X86, the generated assembly would be:
268
269.. code-block:: gas
270
271 .globl test1
272 .align 16, 0x90
273 pushq %rax
274 movl $1, %fs:Flag@TPOFF
275 callq foo
276 movl $0, %fs:Flag@TPOFF
277 .Ltmp1:
278 movq (%rsp), %rax # This load is redundant (oops!)
279 popq %rdx
280 retq
281
282Note that the design as presented above is not fully implemented: in particular,
283strategy-specific lowering is not present, and all GC transitions are emitted as
284as single no-op before and after the call instruction. These no-ops are often
285removed by the backend during dead machine instruction elimination.
Philip Reames5017ab52015-02-26 01:18:21 +0000286
287
Philip Reamesf6123222014-12-02 19:37:00 +0000288Intrinsics
289===========
290
Philip Reamesc0127282015-02-24 23:57:26 +0000291'llvm.experimental.gc.statepoint' Intrinsic
292^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Philip Reamesf6123222014-12-02 19:37:00 +0000293
294Syntax:
295"""""""
296
297::
298
299 declare i32
Philip Reamesc0127282015-02-24 23:57:26 +0000300 @llvm.experimental.gc.statepoint(func_type <target>,
Pat Gavlincc0431d2015-05-08 18:07:42 +0000301 i64 <#call args>. i64 <flags>,
Philip Reamesc0127282015-02-24 23:57:26 +0000302 ... (call parameters),
Pat Gavlincc0431d2015-05-08 18:07:42 +0000303 i64 <# transition args>, ... (transition parameters),
Philip Reamesf6123222014-12-02 19:37:00 +0000304 i64 <# deopt args>, ... (deopt parameters),
305 ... (gc parameters))
306
307Overview:
308"""""""""
309
Philip Reamesdfc238b2015-01-02 19:46:49 +0000310The statepoint intrinsic represents a call which is parse-able by the
311runtime.
Philip Reamesf6123222014-12-02 19:37:00 +0000312
313Operands:
314"""""""""
315
Philip Reamesdfc238b2015-01-02 19:46:49 +0000316The 'target' operand is the function actually being called. The
317target can be specified as either a symbolic LLVM function, or as an
318arbitrary Value of appropriate function type. Note that the function
319type must match the signature of the callee and the types of the 'call
320parameters' arguments.
Philip Reamesf6123222014-12-02 19:37:00 +0000321
Philip Reamesdfc238b2015-01-02 19:46:49 +0000322The '#call args' operand is the number of arguments to the actual
323call. It must exactly match the number of arguments passed in the
324'call parameters' variable length section.
Philip Reamesf6123222014-12-02 19:37:00 +0000325
Pat Gavlincc0431d2015-05-08 18:07:42 +0000326The 'flags' operand is used to specify extra information about the
327statepoint. This is currently only used to mark certain statepoints
328as GC transitions. This operand is a 64-bit integer with the following
329layout, where bit 0 is the least significant bit:
330
331 +-------+---------------------------------------------------+
332 | Bit # | Usage |
333 +=======+===================================================+
334 | 0 | Set if the statepoint is a GC transition, cleared |
335 | | otherwise. |
336 +-------+---------------------------------------------------+
337 | 1-63 | Reserved for future use; must be cleared. |
338 +-------+---------------------------------------------------+
Philip Reamesf6123222014-12-02 19:37:00 +0000339
Philip Reamesdfc238b2015-01-02 19:46:49 +0000340The 'call parameters' arguments are simply the arguments which need to
341be passed to the call target. They will be lowered according to the
342specified calling convention and otherwise handled like a normal call
343instruction. The number of arguments must exactly match what is
344specified in '# call args'. The types must match the signature of
345'target'.
Philip Reamesf6123222014-12-02 19:37:00 +0000346
Pat Gavlincc0431d2015-05-08 18:07:42 +0000347The 'transition parameters' arguments contain an arbitrary list of
348Values which need to be passed to GC transition code. They will be
349lowered and passed as operands to the appropriate GC_TRANSITION nodes
350in the selection DAG. It is assumed that these arguments must be
351available before and after (but not necessarily during) the execution
352of the callee. The '# transition args' field indicates how many operands
353are to be interpreted as 'transition parameters'.
354
Philip Reamesdfc238b2015-01-02 19:46:49 +0000355The 'deopt parameters' arguments contain an arbitrary list of Values
356which is meaningful to the runtime. The runtime may read any of these
357values, but is assumed not to modify them. If the garbage collector
358might need to modify one of these values, it must also be listed in
359the 'gc pointer' argument list. The '# deopt args' field indicates
360how many operands are to be interpreted as 'deopt parameters'.
Philip Reamesf6123222014-12-02 19:37:00 +0000361
Philip Reamesdfc238b2015-01-02 19:46:49 +0000362The 'gc parameters' arguments contain every pointer to a garbage
363collector object which potentially needs to be updated by the garbage
364collector. Note that the argument list must explicitly contain a base
365pointer for every derived pointer listed. The order of arguments is
366unimportant. Unlike the other variable length parameter sets, this
367list is not length prefixed.
Philip Reamesf6123222014-12-02 19:37:00 +0000368
369Semantics:
370""""""""""
371
Philip Reamesdfc238b2015-01-02 19:46:49 +0000372A statepoint is assumed to read and write all memory. As a result,
373memory operations can not be reordered past a statepoint. It is
374illegal to mark a statepoint as being either 'readonly' or 'readnone'.
Philip Reamesf6123222014-12-02 19:37:00 +0000375
Philip Reamesdfc238b2015-01-02 19:46:49 +0000376Note that legal IR can not perform any memory operation on a 'gc
377pointer' argument of the statepoint in a location statically reachable
378from the statepoint. Instead, the explicitly relocated value (from a
Philip Reamesc609a592015-02-25 00:22:07 +0000379``gc.relocate``) must be used.
Philip Reamesf6123222014-12-02 19:37:00 +0000380
Philip Reamesc0127282015-02-24 23:57:26 +0000381'llvm.experimental.gc.result' Intrinsic
382^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Philip Reamesf6123222014-12-02 19:37:00 +0000383
384Syntax:
385"""""""
386
387::
388
389 declare type*
Philip Reamesc0127282015-02-24 23:57:26 +0000390 @llvm.experimental.gc.result(i32 %statepoint_token)
Philip Reamesf6123222014-12-02 19:37:00 +0000391
392Overview:
393"""""""""
394
Philip Reamesc609a592015-02-25 00:22:07 +0000395``gc.result`` extracts the result of the original call instruction
396which was replaced by the ``gc.statepoint``. The ``gc.result``
Philip Reamesdfc238b2015-01-02 19:46:49 +0000397intrinsic is actually a family of three intrinsics due to an
398implementation limitation. Other than the type of the return value,
399the semantics are the same.
Philip Reamesf6123222014-12-02 19:37:00 +0000400
401Operands:
402"""""""""
403
Philip Reamesc609a592015-02-25 00:22:07 +0000404The first and only argument is the ``gc.statepoint`` which starts
405the safepoint sequence of which this ``gc.result`` is a part.
Philip Reamesdfc238b2015-01-02 19:46:49 +0000406Despite the typing of this as a generic i32, *only* the value defined
Philip Reamesc609a592015-02-25 00:22:07 +0000407by a ``gc.statepoint`` is legal here.
Philip Reamesf6123222014-12-02 19:37:00 +0000408
409Semantics:
410""""""""""
411
Philip Reamesc609a592015-02-25 00:22:07 +0000412The ``gc.result`` represents the return value of the call target of
413the ``statepoint``. The type of the ``gc.result`` must exactly match
Philip Reamesdfc238b2015-01-02 19:46:49 +0000414the type of the target. If the call target returns void, there will
Philip Reamesc609a592015-02-25 00:22:07 +0000415be no ``gc.result``.
Philip Reamesf6123222014-12-02 19:37:00 +0000416
Philip Reamesc609a592015-02-25 00:22:07 +0000417A ``gc.result`` is modeled as a 'readnone' pure function. It has no
Philip Reamesdfc238b2015-01-02 19:46:49 +0000418side effects since it is just a projection of the return value of the
Philip Reamesc609a592015-02-25 00:22:07 +0000419previous call represented by the ``gc.statepoint``.
Philip Reamesf6123222014-12-02 19:37:00 +0000420
Philip Reamesc0127282015-02-24 23:57:26 +0000421'llvm.experimental.gc.relocate' Intrinsic
422^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Philip Reamesf6123222014-12-02 19:37:00 +0000423
424Syntax:
425"""""""
426
427::
428
Philip Reamesc0127282015-02-24 23:57:26 +0000429 declare <pointer type>
430 @llvm.experimental.gc.relocate(i32 %statepoint_token,
431 i32 %base_offset,
432 i32 %pointer_offset)
Philip Reamesf6123222014-12-02 19:37:00 +0000433
434Overview:
435"""""""""
436
Philip Reamesc609a592015-02-25 00:22:07 +0000437A ``gc.relocate`` returns the potentially relocated value of a pointer
Philip Reamesdfc238b2015-01-02 19:46:49 +0000438at the safepoint.
Philip Reamesf6123222014-12-02 19:37:00 +0000439
440Operands:
441"""""""""
442
Philip Reamesc609a592015-02-25 00:22:07 +0000443The first argument is the ``gc.statepoint`` which starts the
444safepoint sequence of which this ``gc.relocation`` is a part.
Philip Reamesdfc238b2015-01-02 19:46:49 +0000445Despite the typing of this as a generic i32, *only* the value defined
Philip Reamesc609a592015-02-25 00:22:07 +0000446by a ``gc.statepoint`` is legal here.
Philip Reamesf6123222014-12-02 19:37:00 +0000447
Philip Reamesdfc238b2015-01-02 19:46:49 +0000448The second argument is an index into the statepoints list of arguments
449which specifies the base pointer for the pointer being relocated.
450This index must land within the 'gc parameter' section of the
451statepoint's argument list.
Philip Reamesf6123222014-12-02 19:37:00 +0000452
Philip Reamesdfc238b2015-01-02 19:46:49 +0000453The third argument is an index into the statepoint's list of arguments
454which specify the (potentially) derived pointer being relocated. It
455is legal for this index to be the same as the second argument
456if-and-only-if a base pointer is being relocated. This index must land
457within the 'gc parameter' section of the statepoint's argument list.
Philip Reamesf6123222014-12-02 19:37:00 +0000458
459Semantics:
460""""""""""
Philip Reamesf6123222014-12-02 19:37:00 +0000461
Philip Reamesc609a592015-02-25 00:22:07 +0000462The return value of ``gc.relocate`` is the potentially relocated value
Philip Reamesdfc238b2015-01-02 19:46:49 +0000463of the pointer specified by it's arguments. It is unspecified how the
464value of the returned pointer relates to the argument to the
Philip Reamesc609a592015-02-25 00:22:07 +0000465``gc.statepoint`` other than that a) it points to the same source
Philip Reamesdfc238b2015-01-02 19:46:49 +0000466language object with the same offset, and b) the 'based-on'
467relationship of the newly relocated pointers is a projection of the
468unrelocated pointers. In particular, the integer value of the pointer
469returned is unspecified.
470
Philip Reamesc609a592015-02-25 00:22:07 +0000471A ``gc.relocate`` is modeled as a ``readnone`` pure function. It has no
Philip Reamesdfc238b2015-01-02 19:46:49 +0000472side effects since it is just a way to extract information about work
Philip Reamesc609a592015-02-25 00:22:07 +0000473done during the actual call modeled by the ``gc.statepoint``.
Philip Reamesf6123222014-12-02 19:37:00 +0000474
Philip Reamese6625502015-02-25 23:22:43 +0000475.. _statepoint-stackmap-format:
Philip Reamesf6123222014-12-02 19:37:00 +0000476
Philip Reamesce5ff372014-12-04 00:45:23 +0000477Stack Map Format
Philip Reamesf6123222014-12-02 19:37:00 +0000478================
479
Philip Reamesdfc238b2015-01-02 19:46:49 +0000480Locations for each pointer value which may need read and/or updated by
481the runtime or collector are provided via the :ref:`Stack Map format
482<stackmap-format>` specified in the PatchPoint documentation.
Philip Reamesf6123222014-12-02 19:37:00 +0000483
484Each statepoint generates the following Locations:
485
Pat Gavlinc7dc6d6ee2015-05-12 19:50:19 +0000486* Constant which describes the calling convention of the call target. This
487 constant is a valid :ref:`calling convention identifier <callingconv>` for
488 the version of LLVM used to generate the stackmap. No additional compatibility
489 guarantees are made for this constant over what LLVM provides elsewhere w.r.t.
490 these identifiers.
491* Constant which describes the flags passed to the statepoint intrinsic
Philip Reamesdfc238b2015-01-02 19:46:49 +0000492* Constant which describes number of following deopt *Locations* (not
493 operands)
494* Variable number of Locations, one for each deopt parameter listed in
495 the IR statepoint (same number as described by previous Constant)
496* Variable number of Locations pairs, one pair for each unique pointer
497 which needs relocated. The first Location in each pair describes
498 the base pointer for the object. The second is the derived pointer
499 actually being relocated. It is guaranteed that the base pointer
500 must also appear explicitly as a relocation pair if used after the
501 statepoint. There may be fewer pairs then gc parameters in the IR
502 statepoint. Each *unique* pair will occur at least once; duplicates
503 are possible.
Philip Reamesf6123222014-12-02 19:37:00 +0000504
Philip Reamesdfc238b2015-01-02 19:46:49 +0000505Note that the Locations used in each section may describe the same
506physical location. e.g. A stack slot may appear as a deopt location,
507a gc base pointer, and a gc derived pointer.
Philip Reamesf6123222014-12-02 19:37:00 +0000508
Philip Reamesdfc238b2015-01-02 19:46:49 +0000509The ID field of the 'StkMapRecord' for a statepoint is meaningless and
510it's value is explicitly unspecified.
Philip Reamesf6123222014-12-02 19:37:00 +0000511
Philip Reamesdfc238b2015-01-02 19:46:49 +0000512The LiveOut section of the StkMapRecord will be empty for a statepoint
513record.
Philip Reamesf6123222014-12-02 19:37:00 +0000514
515Safepoint Semantics & Verification
516==================================
517
Philip Reamesdfc238b2015-01-02 19:46:49 +0000518The fundamental correctness property for the compiled code's
519correctness w.r.t. the garbage collector is a dynamic one. It must be
520the case that there is no dynamic trace such that a operation
521involving a potentially relocated pointer is observably-after a
522safepoint which could relocate it. 'observably-after' is this usage
523means that an outside observer could observe this sequence of events
524in a way which precludes the operation being performed before the
525safepoint.
Philip Reamesf6123222014-12-02 19:37:00 +0000526
Philip Reamesdfc238b2015-01-02 19:46:49 +0000527To understand why this 'observable-after' property is required,
528consider a null comparison performed on the original copy of a
529relocated pointer. Assuming that control flow follows the safepoint,
530there is no way to observe externally whether the null comparison is
531performed before or after the safepoint. (Remember, the original
532Value is unmodified by the safepoint.) The compiler is free to make
533either scheduling choice.
Philip Reamesf6123222014-12-02 19:37:00 +0000534
Philip Reamesdfc238b2015-01-02 19:46:49 +0000535The actual correctness property implemented is slightly stronger than
536this. We require that there be no *static path* on which a
537potentially relocated pointer is 'observably-after' it may have been
538relocated. This is slightly stronger than is strictly necessary (and
539thus may disallow some otherwise valid programs), but greatly
540simplifies reasoning about correctness of the compiled code.
Philip Reamesf6123222014-12-02 19:37:00 +0000541
Philip Reamesdfc238b2015-01-02 19:46:49 +0000542By construction, this property will be upheld by the optimizer if
543correctly established in the source IR. This is a key invariant of
544the design.
Philip Reamesf6123222014-12-02 19:37:00 +0000545
Philip Reamesdfc238b2015-01-02 19:46:49 +0000546The existing IR Verifier pass has been extended to check most of the
547local restrictions on the intrinsics mentioned in their respective
548documentation. The current implementation in LLVM does not check the
549key relocation invariant, but this is ongoing work on developing such
550a verifier. Please ask on llvmdev if you're interested in
551experimenting with the current version.
Philip Reamesf6123222014-12-02 19:37:00 +0000552
Philip Reamesc88d7322015-02-25 01:23:59 +0000553.. _statepoint-utilities:
554
555Utility Passes for Safepoint Insertion
556======================================
557
558.. _RewriteStatepointsForGC:
559
560RewriteStatepointsForGC
561^^^^^^^^^^^^^^^^^^^^^^^^
562
563The pass RewriteStatepointsForGC transforms a functions IR by replacing a
564``gc.statepoint`` (with an optional ``gc.result``) with a full relocation
565sequence, including all required ``gc.relocates``. To function, the pass
566requires that the GC strategy specified for the function be able to reliably
567distinguish between GC references and non-GC references in IR it is given.
568
569As an example, given this code:
570
571.. code-block:: llvm
572
573 define i8 addrspace(1)* @test1(i8 addrspace(1)* %obj)
574 gc "statepoint-example" {
Pat Gavlincc0431d2015-05-08 18:07:42 +0000575 call i32 (void ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_isVoidf(void ()* @foo, i32 0, i32 0, i32 0, i32 5, i32 0, i32 -1, i32 0, i32 0, i32 0)
Philip Reamesc88d7322015-02-25 01:23:59 +0000576 ret i8 addrspace(1)* %obj
577 }
578
579The pass would produce this IR:
580
581.. code-block:: llvm
582
583 define i8 addrspace(1)* @test1(i8 addrspace(1)* %obj)
584 gc "statepoint-example" {
Pat Gavlincc0431d2015-05-08 18:07:42 +0000585 %0 = call i32 (void ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_isVoidf(void ()* @foo, i32 0, i32 0, i32 0, i32 5, i32 0, i32 -1, i32 0, i32 0, i32 0, i8 addrspace(1)* %obj)
Philip Reamesc88d7322015-02-25 01:23:59 +0000586 %obj.relocated = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(i32 %0, i32 9, i32 9)
587 ret i8 addrspace(1)* %obj.relocated
588 }
589
590In the above examples, the addrspace(1) marker on the pointers is the mechanism
591that the ``statepoint-example`` GC strategy uses to distinguish references from
592non references. Address space 1 is not globally reserved for this purpose.
593
594This pass can be used an utility function by a language frontend that doesn't
595want to manually reason about liveness, base pointers, or relocation when
596constructing IR. As currently implemented, RewriteStatepointsForGC must be
597run after SSA construction (i.e. mem2ref).
598
599
600In practice, RewriteStatepointsForGC can be run much later in the pass
601pipeline, after most optimization is already done. This helps to improve
602the quality of the generated code when compiled with garbage collection support.
603In the long run, this is the intended usage model. At this time, a few details
604have yet to be worked out about the semantic model required to guarantee this
605is always correct. As such, please use with caution and report bugs.
606
607.. _PlaceSafepoints:
608
609PlaceSafepoints
610^^^^^^^^^^^^^^^^
611
612The pass PlaceSafepoints transforms a function's IR by replacing any call or
613invoke instructions with appropriate ``gc.statepoint`` and ``gc.result`` pairs,
614and inserting safepoint polls sufficient to ensure running code checks for a
615safepoint request on a timely manner. This pass is expected to be run before
616RewriteStatepointsForGC and thus does not produce full relocation sequences.
617
Philip Reames5017ab52015-02-26 01:18:21 +0000618As an example, given input IR of the following:
619
620.. code-block:: llvm
621
622 define void @test() gc "statepoint-example" {
623 call void @foo()
624 ret void
625 }
626
627 declare void @do_safepoint()
628 define void @gc.safepoint_poll() {
629 call void @do_safepoint()
630 ret void
631 }
632
633
634This pass would produce the following IR:
635
636.. code-block:: llvm
637
638 define void @test() gc "statepoint-example" {
Pat Gavlincc0431d2015-05-08 18:07:42 +0000639 %safepoint_token = call i32 (void ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_isVoidf(void ()* @do_safepoint, i32 0, i32 0, i32 0, i32 0)
640 %safepoint_token1 = call i32 (void ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_isVoidf(void ()* @foo, i32 0, i32 0, i32 0, i32 0)
Philip Reames5017ab52015-02-26 01:18:21 +0000641 ret void
642 }
643
644In this case, we've added an (unconditional) entry safepoint poll and converted the call into a ``gc.statepoint``. Note that despite appearances, the entry poll is not necessarily redundant. We'd have to know that ``foo`` and ``test`` were not mutually recursive for the poll to be redundant. In practice, you'd probably want to your poll definition to contain a conditional branch of some form.
645
646
Philip Reamesc88d7322015-02-25 01:23:59 +0000647At the moment, PlaceSafepoints can insert safepoint polls at method entry and
648loop backedges locations. Extending this to work with return polls would be
649straight forward if desired.
650
651PlaceSafepoints includes a number of optimizations to avoid placing safepoint
652polls at particular sites unless needed to ensure timely execution of a poll
653under normal conditions. PlaceSafepoints does not attempt to ensure timely
654execution of a poll under worst case conditions such as heavy system paging.
655
656The implementation of a safepoint poll action is specified by looking up a
657function of the name ``gc.safepoint_poll`` in the containing Module. The body
658of this function is inserted at each poll site desired. While calls or invokes
659inside this method are transformed to a ``gc.statepoints``, recursive poll
660insertion is not performed.
661
662If you are scheduling the RewriteStatepointsForGC pass late in the pass order,
663you should probably schedule this pass immediately before it. The exception
664would be if you need to preserve abstract frame information (e.g. for
665deoptimization or introspection) at safepoints. In that case, ask on the
666llvmdev mailing list for suggestions.
667
668
Philip Reames83331522014-12-04 18:33:28 +0000669Bugs and Enhancements
670=====================
Philip Reamesdfc238b2015-01-02 19:46:49 +0000671
672Currently known bugs and enhancements under consideration can be
673tracked by performing a `bugzilla search
674<http://llvm.org/bugs/buglist.cgi?cmdtype=runnamed&namedcmd=Statepoint%20Bugs&list_id=64342>`_
675for [Statepoint] in the summary field. When filing new bugs, please
676use this tag so that interested parties see the newly filed bug. As
677with most LLVM features, design discussions take place on `llvmdev
678<http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev>`_, and patches
679should be sent to `llvm-commits
680<http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits>`_ for review.
Philip Reames83331522014-12-04 18:33:28 +0000681