|
83
|
1 =====================================
|
|
|
2 Garbage Collection Safepoints in LLVM
|
|
|
3 =====================================
|
|
|
4
|
|
|
5 .. contents::
|
|
|
6 :local:
|
|
|
7 :depth: 2
|
|
|
8
|
|
|
9 Status
|
|
|
10 =======
|
|
|
11
|
|
|
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.
|
|
|
15
|
|
|
16 LLVM currently supports an alternate mechanism for conservative
|
|
95
|
17 garbage collection support using the ``gcroot`` intrinsic. The mechanism
|
|
|
18 described here shares little in common with the alternate ``gcroot``
|
|
83
|
19 implementation and it is hoped that this mechanism will eventually
|
|
|
20 replace the gc_root mechanism.
|
|
|
21
|
|
|
22 Overview
|
|
|
23 ========
|
|
|
24
|
|
|
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.
|
|
|
34
|
|
|
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
|
|
|
44 its allocation.
|
|
|
45
|
|
|
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.
|
|
|
49
|
|
|
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.
|
|
|
55
|
|
95
|
56 #. Analogously, a store barrier is a code fragment that runs
|
|
83
|
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.
|
|
|
61
|
|
|
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)
|
|
|
66 pointed to will not.
|
|
|
67
|
|
|
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
|
|
|
73 former.
|
|
|
74
|
|
|
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:
|
|
|
81
|
|
|
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.
|
|
|
86
|
|
|
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:
|
|
|
93
|
|
|
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.
|
|
|
103
|
|
|
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.
|
|
|
109
|
|
|
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.
|
|
95
|
114 The recommended approach is to use the :ref:`utility passes
|
|
|
115 <statepoint-utilities>` described below.
|
|
83
|
116
|
|
|
117 This abstract function call is concretely represented by a sequence of
|
|
95
|
118 intrinsic calls known collectively as a "statepoint relocation sequence".
|
|
83
|
119
|
|
|
120 Let's consider a simple call in LLVM IR:
|
|
95
|
121
|
|
|
122 .. code-block:: llvm
|
|
83
|
123
|
|
95
|
124 define i8 addrspace(1)* @test1(i8 addrspace(1)* %obj)
|
|
|
125 gc "statepoint-example" {
|
|
|
126 call void ()* @foo()
|
|
|
127 ret i8 addrspace(1)* %obj
|
|
|
128 }
|
|
|
129
|
|
|
130 Depending on our language we may need to allow a safepoint during the execution
|
|
|
131 of ``foo``. If so, we need to let the collector update local values in the
|
|
|
132 current frame. If we don't, we'll be accessing a potential invalid reference
|
|
|
133 once we eventually return from the call.
|
|
83
|
134
|
|
95
|
135 In this example, we need to relocate the SSA value ``%obj``. Since we can't
|
|
|
136 actually change the value in the SSA value ``%obj``, we need to introduce a new
|
|
|
137 SSA value ``%obj.relocated`` which represents the potentially changed value of
|
|
|
138 ``%obj`` after the safepoint and update any following uses appropriately. The
|
|
|
139 resulting relocation sequence is:
|
|
83
|
140
|
|
95
|
141 .. code-block:: llvm
|
|
|
142
|
|
|
143 define i8 addrspace(1)* @test1(i8 addrspace(1)* %obj)
|
|
|
144 gc "statepoint-example" {
|
|
100
|
145 %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)
|
|
|
146 %obj.relocated = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %0, i32 7, i32 7)
|
|
95
|
147 ret i8 addrspace(1)* %obj.relocated
|
|
|
148 }
|
|
83
|
149
|
|
|
150 Ideally, this sequence would have been represented as a M argument, N
|
|
|
151 return value function (where M is the number of values being
|
|
|
152 relocated + the original call arguments and N is the original return
|
|
|
153 value + each relocated value), but LLVM does not easily support such a
|
|
|
154 representation.
|
|
|
155
|
|
|
156 Instead, the statepoint intrinsic marks the actual site of the
|
|
|
157 safepoint or statepoint. The statepoint returns a token value (which
|
|
|
158 exists only at compile time). To get back the original return value
|
|
95
|
159 of the call, we use the ``gc.result`` intrinsic. To get the relocation
|
|
|
160 of each pointer in turn, we use the ``gc.relocate`` intrinsic with the
|
|
|
161 appropriate index. Note that both the ``gc.relocate`` and ``gc.result`` are
|
|
|
162 tied to the statepoint. The combination forms a "statepoint relocation
|
|
|
163 sequence" and represents the entirety of a parseable call or 'statepoint'.
|
|
|
164
|
|
|
165 When lowered, this example would generate the following x86 assembly:
|
|
83
|
166
|
|
95
|
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
|
|
83
|
177
|
|
|
178 Each of the potentially relocated values has been spilled to the
|
|
|
179 stack, and a record of that location has been recorded to the
|
|
|
180 :ref:`Stack Map section <stackmap-section>`. If the garbage collector
|
|
|
181 needs to update any of these pointers during the call, it knows
|
|
|
182 exactly what to change.
|
|
|
183
|
|
95
|
184 The 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
|
|
|
203 This 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 Base & Derived Pointers
|
|
|
210 ^^^^^^^^^^^^^^^^^^^^^^^
|
|
|
211
|
|
|
212 A "base pointer" is one which points to the starting address of an allocation
|
|
|
213 (object). A "derived pointer" is one which is offset from a base pointer by
|
|
|
214 some amount. When relocating objects, a garbage collector needs to be able
|
|
|
215 to relocate each derived pointer associated with an allocation to the same
|
|
|
216 offset from the new address.
|
|
|
217
|
|
|
218 "Interior derived pointers" remain within the bounds of the allocation
|
|
|
219 they're associated with. As a result, the base object can be found at
|
|
|
220 runtime provided the bounds of allocations are known to the runtime system.
|
|
|
221
|
|
|
222 "Exterior derived pointers" are outside the bounds of the associated object;
|
|
|
223 they may even fall within *another* allocations address range. As a result,
|
|
|
224 there is no way for a garbage collector to determine which allocation they
|
|
|
225 are associated with at runtime and compiler support is needed.
|
|
|
226
|
|
|
227 The ``gc.relocate`` intrinsic supports an explicit operand for describing the
|
|
|
228 allocation associated with a derived pointer. This operand is frequently
|
|
|
229 referred to as the base operand, but does not strictly speaking have to be
|
|
|
230 a base pointer, but it does need to lie within the bounds of the associated
|
|
|
231 allocation. Some collectors may require that the operand be an actual base
|
|
|
232 pointer rather than merely an internal derived pointer. Note that during
|
|
|
233 lowering both the base and derived pointer operands are required to be live
|
|
|
234 over the associated call safepoint even if the base is otherwise unused
|
|
|
235 afterwards.
|
|
|
236
|
|
|
237 If we extend our previous example to include a pointless derived pointer,
|
|
|
238 we get:
|
|
|
239
|
|
|
240 .. code-block:: llvm
|
|
|
241
|
|
|
242 define i8 addrspace(1)* @test1(i8 addrspace(1)* %obj)
|
|
|
243 gc "statepoint-example" {
|
|
|
244 %gep = getelementptr i8, i8 addrspace(1)* %obj, i64 20000
|
|
100
|
245 %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)
|
|
|
246 %obj.relocated = call i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %token, i32 7, i32 7)
|
|
|
247 %gep.relocated = call i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %token, i32 7, i32 8)
|
|
95
|
248 %p = getelementptr i8, i8 addrspace(1)* %gep, i64 -20000
|
|
|
249 ret i8 addrspace(1)* %p
|
|
|
250 }
|
|
|
251
|
|
|
252 Note that in this example %p and %obj.relocate are the same address and we
|
|
|
253 could replace one with the other, potentially removing the derived pointer
|
|
100
|
254 from the live set at the safepoint entirely.
|
|
|
255
|
|
|
256 .. _gc_transition_args:
|
|
95
|
257
|
|
|
258 GC Transitions
|
|
|
259 ^^^^^^^^^^^^^^^^^^
|
|
|
260
|
|
|
261 As a practical consideration, many garbage-collected systems allow code that is
|
|
|
262 collector-aware ("managed code") to call code that is not collector-aware
|
|
|
263 ("unmanaged code"). It is common that such calls must also be safepoints, since
|
|
|
264 it is desirable to allow the collector to run during the execution of
|
|
|
265 unmanaged code. Futhermore, it is common that coordinating the transition from
|
|
|
266 managed to unmanaged code requires extra code generation at the call site to
|
|
|
267 inform the collector of the transition. In order to support these needs, a
|
|
|
268 statepoint may be marked as a GC transition, and data that is necessary to
|
|
|
269 perform the transition (if any) may be provided as additional arguments to the
|
|
|
270 statepoint.
|
|
|
271
|
|
|
272 Note that although in many cases statepoints may be inferred to be GC
|
|
|
273 transitions based on the function symbols involved (e.g. a call from a
|
|
|
274 function with GC strategy "foo" to a function with GC strategy "bar"),
|
|
|
275 indirect calls that are also GC transitions must also be supported. This
|
|
|
276 requirement is the driving force behind the decision to require that GC
|
|
|
277 transitions are explicitly marked.
|
|
|
278
|
|
|
279 Let's revisit the sample given above, this time treating the call to ``@foo``
|
|
|
280 as a GC transition. Depending on our target, the transition code may need to
|
|
|
281 access some extra state in order to inform the collector of the transition.
|
|
|
282 Let's assume a hypothetical GC--somewhat unimaginatively named "hypothetical-gc"
|
|
|
283 --that requires that a TLS variable must be written to before and after a call
|
|
|
284 to unmanaged code. The resulting relocation sequence is:
|
|
|
285
|
|
|
286 .. code-block:: llvm
|
|
|
287
|
|
|
288 @flag = thread_local global i32 0, align 4
|
|
|
289
|
|
|
290 define i8 addrspace(1)* @test1(i8 addrspace(1) *%obj)
|
|
|
291 gc "hypothetical-gc" {
|
|
|
292
|
|
100
|
293 %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)
|
|
|
294 %obj.relocated = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %0, i32 7, i32 7)
|
|
95
|
295 ret i8 addrspace(1)* %obj.relocated
|
|
|
296 }
|
|
|
297
|
|
|
298 During lowering, this will result in a instruction selection DAG that looks
|
|
|
299 something like:
|
|
|
300
|
|
|
301 ::
|
|
|
302
|
|
|
303 CALLSEQ_START
|
|
|
304 ...
|
|
|
305 GC_TRANSITION_START (lowered i32 *@Flag), SRCVALUE i32* Flag
|
|
|
306 STATEPOINT
|
|
|
307 GC_TRANSITION_END (lowered i32 *@Flag), SRCVALUE i32 *Flag
|
|
|
308 ...
|
|
|
309 CALLSEQ_END
|
|
|
310
|
|
|
311 In order to generate the necessary transition code, the backend for each target
|
|
|
312 supported by "hypothetical-gc" must be modified to lower ``GC_TRANSITION_START``
|
|
|
313 and ``GC_TRANSITION_END`` nodes appropriately when the "hypothetical-gc"
|
|
|
314 strategy is in use for a particular function. Assuming that such lowering has
|
|
|
315 been added for X86, the generated assembly would be:
|
|
|
316
|
|
|
317 .. code-block:: gas
|
|
|
318
|
|
|
319 .globl test1
|
|
|
320 .align 16, 0x90
|
|
|
321 pushq %rax
|
|
|
322 movl $1, %fs:Flag@TPOFF
|
|
|
323 callq foo
|
|
|
324 movl $0, %fs:Flag@TPOFF
|
|
|
325 .Ltmp1:
|
|
|
326 movq (%rsp), %rax # This load is redundant (oops!)
|
|
|
327 popq %rdx
|
|
|
328 retq
|
|
|
329
|
|
|
330 Note that the design as presented above is not fully implemented: in particular,
|
|
|
331 strategy-specific lowering is not present, and all GC transitions are emitted as
|
|
|
332 as single no-op before and after the call instruction. These no-ops are often
|
|
|
333 removed by the backend during dead machine instruction elimination.
|
|
|
334
|
|
|
335
|
|
83
|
336 Intrinsics
|
|
|
337 ===========
|
|
|
338
|
|
95
|
339 'llvm.experimental.gc.statepoint' Intrinsic
|
|
|
340 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
|
83
|
341
|
|
|
342 Syntax:
|
|
|
343 """""""
|
|
|
344
|
|
|
345 ::
|
|
|
346
|
|
100
|
347 declare token
|
|
95
|
348 @llvm.experimental.gc.statepoint(i64 <id>, i32 <num patch bytes>,
|
|
|
349 func_type <target>,
|
|
|
350 i64 <#call args>, i64 <flags>,
|
|
|
351 ... (call parameters),
|
|
|
352 i64 <# transition args>, ... (transition parameters),
|
|
83
|
353 i64 <# deopt args>, ... (deopt parameters),
|
|
|
354 ... (gc parameters))
|
|
|
355
|
|
|
356 Overview:
|
|
|
357 """""""""
|
|
|
358
|
|
|
359 The statepoint intrinsic represents a call which is parse-able by the
|
|
|
360 runtime.
|
|
|
361
|
|
|
362 Operands:
|
|
|
363 """""""""
|
|
|
364
|
|
95
|
365 The 'id' operand is a constant integer that is reported as the ID
|
|
|
366 field in the generated stackmap. LLVM does not interpret this
|
|
|
367 parameter in any way and its meaning is up to the statepoint user to
|
|
|
368 decide. Note that LLVM is free to duplicate code containing
|
|
|
369 statepoint calls, and this may transform IR that had a unique 'id' per
|
|
|
370 lexical call to statepoint to IR that does not.
|
|
|
371
|
|
|
372 If 'num patch bytes' is non-zero then the call instruction
|
|
|
373 corresponding to the statepoint is not emitted and LLVM emits 'num
|
|
|
374 patch bytes' bytes of nops in its place. LLVM will emit code to
|
|
|
375 prepare the function arguments and retrieve the function return value
|
|
|
376 in accordance to the calling convention; the former before the nop
|
|
|
377 sequence and the latter after the nop sequence. It is expected that
|
|
|
378 the user will patch over the 'num patch bytes' bytes of nops with a
|
|
|
379 calling sequence specific to their runtime before executing the
|
|
|
380 generated machine code. There are no guarantees with respect to the
|
|
|
381 alignment of the nop sequence. Unlike :doc:`StackMaps` statepoints do
|
|
|
382 not have a concept of shadow bytes. Note that semantically the
|
|
|
383 statepoint still represents a call or invoke to 'target', and the nop
|
|
|
384 sequence after patching is expected to represent an operation
|
|
|
385 equivalent to a call or invoke to 'target'.
|
|
|
386
|
|
83
|
387 The 'target' operand is the function actually being called. The
|
|
|
388 target can be specified as either a symbolic LLVM function, or as an
|
|
|
389 arbitrary Value of appropriate function type. Note that the function
|
|
|
390 type must match the signature of the callee and the types of the 'call
|
|
|
391 parameters' arguments.
|
|
|
392
|
|
|
393 The '#call args' operand is the number of arguments to the actual
|
|
|
394 call. It must exactly match the number of arguments passed in the
|
|
|
395 'call parameters' variable length section.
|
|
|
396
|
|
95
|
397 The 'flags' operand is used to specify extra information about the
|
|
|
398 statepoint. This is currently only used to mark certain statepoints
|
|
|
399 as GC transitions. This operand is a 64-bit integer with the following
|
|
|
400 layout, where bit 0 is the least significant bit:
|
|
|
401
|
|
|
402 +-------+---------------------------------------------------+
|
|
|
403 | Bit # | Usage |
|
|
|
404 +=======+===================================================+
|
|
|
405 | 0 | Set if the statepoint is a GC transition, cleared |
|
|
|
406 | | otherwise. |
|
|
|
407 +-------+---------------------------------------------------+
|
|
|
408 | 1-63 | Reserved for future use; must be cleared. |
|
|
|
409 +-------+---------------------------------------------------+
|
|
83
|
410
|
|
|
411 The 'call parameters' arguments are simply the arguments which need to
|
|
|
412 be passed to the call target. They will be lowered according to the
|
|
|
413 specified calling convention and otherwise handled like a normal call
|
|
|
414 instruction. The number of arguments must exactly match what is
|
|
|
415 specified in '# call args'. The types must match the signature of
|
|
|
416 'target'.
|
|
|
417
|
|
95
|
418 The 'transition parameters' arguments contain an arbitrary list of
|
|
|
419 Values which need to be passed to GC transition code. They will be
|
|
|
420 lowered and passed as operands to the appropriate GC_TRANSITION nodes
|
|
|
421 in the selection DAG. It is assumed that these arguments must be
|
|
|
422 available before and after (but not necessarily during) the execution
|
|
|
423 of the callee. The '# transition args' field indicates how many operands
|
|
|
424 are to be interpreted as 'transition parameters'.
|
|
|
425
|
|
83
|
426 The 'deopt parameters' arguments contain an arbitrary list of Values
|
|
|
427 which is meaningful to the runtime. The runtime may read any of these
|
|
|
428 values, but is assumed not to modify them. If the garbage collector
|
|
|
429 might need to modify one of these values, it must also be listed in
|
|
|
430 the 'gc pointer' argument list. The '# deopt args' field indicates
|
|
|
431 how many operands are to be interpreted as 'deopt parameters'.
|
|
|
432
|
|
|
433 The 'gc parameters' arguments contain every pointer to a garbage
|
|
|
434 collector object which potentially needs to be updated by the garbage
|
|
|
435 collector. Note that the argument list must explicitly contain a base
|
|
|
436 pointer for every derived pointer listed. The order of arguments is
|
|
|
437 unimportant. Unlike the other variable length parameter sets, this
|
|
|
438 list is not length prefixed.
|
|
|
439
|
|
|
440 Semantics:
|
|
|
441 """"""""""
|
|
|
442
|
|
|
443 A statepoint is assumed to read and write all memory. As a result,
|
|
|
444 memory operations can not be reordered past a statepoint. It is
|
|
|
445 illegal to mark a statepoint as being either 'readonly' or 'readnone'.
|
|
|
446
|
|
|
447 Note that legal IR can not perform any memory operation on a 'gc
|
|
|
448 pointer' argument of the statepoint in a location statically reachable
|
|
|
449 from the statepoint. Instead, the explicitly relocated value (from a
|
|
95
|
450 ``gc.relocate``) must be used.
|
|
83
|
451
|
|
95
|
452 'llvm.experimental.gc.result' Intrinsic
|
|
|
453 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
|
83
|
454
|
|
|
455 Syntax:
|
|
|
456 """""""
|
|
|
457
|
|
|
458 ::
|
|
|
459
|
|
|
460 declare type*
|
|
100
|
461 @llvm.experimental.gc.result(token %statepoint_token)
|
|
83
|
462
|
|
|
463 Overview:
|
|
|
464 """""""""
|
|
|
465
|
|
95
|
466 ``gc.result`` extracts the result of the original call instruction
|
|
|
467 which was replaced by the ``gc.statepoint``. The ``gc.result``
|
|
83
|
468 intrinsic is actually a family of three intrinsics due to an
|
|
|
469 implementation limitation. Other than the type of the return value,
|
|
|
470 the semantics are the same.
|
|
|
471
|
|
|
472 Operands:
|
|
|
473 """""""""
|
|
|
474
|
|
95
|
475 The first and only argument is the ``gc.statepoint`` which starts
|
|
|
476 the safepoint sequence of which this ``gc.result`` is a part.
|
|
100
|
477 Despite the typing of this as a generic token, *only* the value defined
|
|
95
|
478 by a ``gc.statepoint`` is legal here.
|
|
83
|
479
|
|
|
480 Semantics:
|
|
|
481 """"""""""
|
|
|
482
|
|
95
|
483 The ``gc.result`` represents the return value of the call target of
|
|
|
484 the ``statepoint``. The type of the ``gc.result`` must exactly match
|
|
83
|
485 the type of the target. If the call target returns void, there will
|
|
95
|
486 be no ``gc.result``.
|
|
83
|
487
|
|
95
|
488 A ``gc.result`` is modeled as a 'readnone' pure function. It has no
|
|
83
|
489 side effects since it is just a projection of the return value of the
|
|
95
|
490 previous call represented by the ``gc.statepoint``.
|
|
83
|
491
|
|
95
|
492 'llvm.experimental.gc.relocate' Intrinsic
|
|
|
493 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
|
83
|
494
|
|
|
495 Syntax:
|
|
|
496 """""""
|
|
|
497
|
|
|
498 ::
|
|
|
499
|
|
95
|
500 declare <pointer type>
|
|
100
|
501 @llvm.experimental.gc.relocate(token %statepoint_token,
|
|
95
|
502 i32 %base_offset,
|
|
|
503 i32 %pointer_offset)
|
|
83
|
504
|
|
|
505 Overview:
|
|
|
506 """""""""
|
|
|
507
|
|
95
|
508 A ``gc.relocate`` returns the potentially relocated value of a pointer
|
|
83
|
509 at the safepoint.
|
|
|
510
|
|
|
511 Operands:
|
|
|
512 """""""""
|
|
|
513
|
|
95
|
514 The first argument is the ``gc.statepoint`` which starts the
|
|
|
515 safepoint sequence of which this ``gc.relocation`` is a part.
|
|
100
|
516 Despite the typing of this as a generic token, *only* the value defined
|
|
95
|
517 by a ``gc.statepoint`` is legal here.
|
|
83
|
518
|
|
|
519 The second argument is an index into the statepoints list of arguments
|
|
95
|
520 which specifies the allocation for the pointer being relocated.
|
|
83
|
521 This index must land within the 'gc parameter' section of the
|
|
95
|
522 statepoint's argument list. The associated value must be within the
|
|
|
523 object with which the pointer being relocated is associated. The optimizer
|
|
|
524 is free to change *which* interior derived pointer is reported, provided that
|
|
|
525 it does not replace an actual base pointer with another interior derived
|
|
|
526 pointer. Collectors are allowed to rely on the base pointer operand
|
|
|
527 remaining an actual base pointer if so constructed.
|
|
83
|
528
|
|
|
529 The third argument is an index into the statepoint's list of arguments
|
|
|
530 which specify the (potentially) derived pointer being relocated. It
|
|
|
531 is legal for this index to be the same as the second argument
|
|
|
532 if-and-only-if a base pointer is being relocated. This index must land
|
|
|
533 within the 'gc parameter' section of the statepoint's argument list.
|
|
|
534
|
|
|
535 Semantics:
|
|
|
536 """"""""""
|
|
|
537
|
|
95
|
538 The return value of ``gc.relocate`` is the potentially relocated value
|
|
83
|
539 of the pointer specified by it's arguments. It is unspecified how the
|
|
|
540 value of the returned pointer relates to the argument to the
|
|
95
|
541 ``gc.statepoint`` other than that a) it points to the same source
|
|
83
|
542 language object with the same offset, and b) the 'based-on'
|
|
|
543 relationship of the newly relocated pointers is a projection of the
|
|
|
544 unrelocated pointers. In particular, the integer value of the pointer
|
|
|
545 returned is unspecified.
|
|
|
546
|
|
95
|
547 A ``gc.relocate`` is modeled as a ``readnone`` pure function. It has no
|
|
83
|
548 side effects since it is just a way to extract information about work
|
|
95
|
549 done during the actual call modeled by the ``gc.statepoint``.
|
|
83
|
550
|
|
95
|
551 .. _statepoint-stackmap-format:
|
|
83
|
552
|
|
|
553 Stack Map Format
|
|
|
554 ================
|
|
|
555
|
|
|
556 Locations for each pointer value which may need read and/or updated by
|
|
|
557 the runtime or collector are provided via the :ref:`Stack Map format
|
|
|
558 <stackmap-format>` specified in the PatchPoint documentation.
|
|
|
559
|
|
|
560 Each statepoint generates the following Locations:
|
|
|
561
|
|
95
|
562 * Constant which describes the calling convention of the call target. This
|
|
|
563 constant is a valid :ref:`calling convention identifier <callingconv>` for
|
|
|
564 the version of LLVM used to generate the stackmap. No additional compatibility
|
|
|
565 guarantees are made for this constant over what LLVM provides elsewhere w.r.t.
|
|
|
566 these identifiers.
|
|
|
567 * Constant which describes the flags passed to the statepoint intrinsic
|
|
83
|
568 * Constant which describes number of following deopt *Locations* (not
|
|
|
569 operands)
|
|
|
570 * Variable number of Locations, one for each deopt parameter listed in
|
|
100
|
571 the IR statepoint (same number as described by previous Constant). At
|
|
|
572 the moment, only deopt parameters with a bitwidth of 64 bits or less
|
|
|
573 are supported. Values of a type larger than 64 bits can be specified
|
|
|
574 and reported only if a) the value is constant at the call site, and b)
|
|
|
575 the constant can be represented with less than 64 bits (assuming zero
|
|
|
576 extension to the original bitwidth).
|
|
|
577 * Variable number of relocation records, each of which consists of
|
|
|
578 exactly two Locations. Relocation records are described in detail
|
|
|
579 below.
|
|
|
580
|
|
|
581 Each relocation record provides sufficient information for a collector to
|
|
|
582 relocate one or more derived pointers. Each record consists of a pair of
|
|
|
583 Locations. The second element in the record represents the pointer (or
|
|
|
584 pointers) which need updated. The first element in the record provides a
|
|
|
585 pointer to the base of the object with which the pointer(s) being relocated is
|
|
|
586 associated. This information is required for handling generalized derived
|
|
|
587 pointers since a pointer may be outside the bounds of the original allocation,
|
|
|
588 but still needs to be relocated with the allocation. Additionally:
|
|
|
589
|
|
|
590 * It is guaranteed that the base pointer must also appear explicitly as a
|
|
|
591 relocation pair if used after the statepoint.
|
|
|
592 * There may be fewer relocation records then gc parameters in the IR
|
|
83
|
593 statepoint. Each *unique* pair will occur at least once; duplicates
|
|
100
|
594 are possible.
|
|
|
595 * The Locations within each record may either be of pointer size or a
|
|
|
596 multiple of pointer size. In the later case, the record must be
|
|
|
597 interpreted as describing a sequence of pointers and their corresponding
|
|
|
598 base pointers. If the Location is of size N x sizeof(pointer), then
|
|
|
599 there will be N records of one pointer each contained within the Location.
|
|
|
600 Both Locations in a pair can be assumed to be of the same size.
|
|
83
|
601
|
|
|
602 Note that the Locations used in each section may describe the same
|
|
|
603 physical location. e.g. A stack slot may appear as a deopt location,
|
|
|
604 a gc base pointer, and a gc derived pointer.
|
|
|
605
|
|
|
606 The LiveOut section of the StkMapRecord will be empty for a statepoint
|
|
|
607 record.
|
|
|
608
|
|
|
609 Safepoint Semantics & Verification
|
|
|
610 ==================================
|
|
|
611
|
|
|
612 The fundamental correctness property for the compiled code's
|
|
|
613 correctness w.r.t. the garbage collector is a dynamic one. It must be
|
|
|
614 the case that there is no dynamic trace such that a operation
|
|
|
615 involving a potentially relocated pointer is observably-after a
|
|
|
616 safepoint which could relocate it. 'observably-after' is this usage
|
|
|
617 means that an outside observer could observe this sequence of events
|
|
|
618 in a way which precludes the operation being performed before the
|
|
|
619 safepoint.
|
|
|
620
|
|
|
621 To understand why this 'observable-after' property is required,
|
|
|
622 consider a null comparison performed on the original copy of a
|
|
|
623 relocated pointer. Assuming that control flow follows the safepoint,
|
|
|
624 there is no way to observe externally whether the null comparison is
|
|
|
625 performed before or after the safepoint. (Remember, the original
|
|
|
626 Value is unmodified by the safepoint.) The compiler is free to make
|
|
|
627 either scheduling choice.
|
|
|
628
|
|
|
629 The actual correctness property implemented is slightly stronger than
|
|
|
630 this. We require that there be no *static path* on which a
|
|
|
631 potentially relocated pointer is 'observably-after' it may have been
|
|
|
632 relocated. This is slightly stronger than is strictly necessary (and
|
|
|
633 thus may disallow some otherwise valid programs), but greatly
|
|
|
634 simplifies reasoning about correctness of the compiled code.
|
|
|
635
|
|
|
636 By construction, this property will be upheld by the optimizer if
|
|
|
637 correctly established in the source IR. This is a key invariant of
|
|
|
638 the design.
|
|
|
639
|
|
|
640 The existing IR Verifier pass has been extended to check most of the
|
|
|
641 local restrictions on the intrinsics mentioned in their respective
|
|
|
642 documentation. The current implementation in LLVM does not check the
|
|
|
643 key relocation invariant, but this is ongoing work on developing such
|
|
95
|
644 a verifier. Please ask on llvm-dev if you're interested in
|
|
83
|
645 experimenting with the current version.
|
|
|
646
|
|
95
|
647 .. _statepoint-utilities:
|
|
|
648
|
|
|
649 Utility Passes for Safepoint Insertion
|
|
|
650 ======================================
|
|
|
651
|
|
|
652 .. _RewriteStatepointsForGC:
|
|
|
653
|
|
|
654 RewriteStatepointsForGC
|
|
|
655 ^^^^^^^^^^^^^^^^^^^^^^^^
|
|
|
656
|
|
|
657 The pass RewriteStatepointsForGC transforms a functions IR by replacing a
|
|
|
658 ``gc.statepoint`` (with an optional ``gc.result``) with a full relocation
|
|
|
659 sequence, including all required ``gc.relocates``. To function, the pass
|
|
|
660 requires that the GC strategy specified for the function be able to reliably
|
|
|
661 distinguish between GC references and non-GC references in IR it is given.
|
|
|
662
|
|
|
663 As an example, given this code:
|
|
|
664
|
|
|
665 .. code-block:: llvm
|
|
|
666
|
|
|
667 define i8 addrspace(1)* @test1(i8 addrspace(1)* %obj)
|
|
|
668 gc "statepoint-example" {
|
|
100
|
669 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)
|
|
95
|
670 ret i8 addrspace(1)* %obj
|
|
|
671 }
|
|
|
672
|
|
|
673 The pass would produce this IR:
|
|
|
674
|
|
|
675 .. code-block:: llvm
|
|
|
676
|
|
|
677 define i8 addrspace(1)* @test1(i8 addrspace(1)* %obj)
|
|
|
678 gc "statepoint-example" {
|
|
100
|
679 %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)
|
|
|
680 %obj.relocated = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %0, i32 12, i32 12)
|
|
95
|
681 ret i8 addrspace(1)* %obj.relocated
|
|
|
682 }
|
|
|
683
|
|
|
684 In the above examples, the addrspace(1) marker on the pointers is the mechanism
|
|
|
685 that the ``statepoint-example`` GC strategy uses to distinguish references from
|
|
|
686 non references. Address space 1 is not globally reserved for this purpose.
|
|
|
687
|
|
|
688 This pass can be used an utility function by a language frontend that doesn't
|
|
|
689 want to manually reason about liveness, base pointers, or relocation when
|
|
|
690 constructing IR. As currently implemented, RewriteStatepointsForGC must be
|
|
|
691 run after SSA construction (i.e. mem2ref).
|
|
|
692
|
|
|
693 RewriteStatepointsForGC will ensure that appropriate base pointers are listed
|
|
|
694 for every relocation created. It will do so by duplicating code as needed to
|
|
|
695 propagate the base pointer associated with each pointer being relocated to
|
|
|
696 the appropriate safepoints. The implementation assumes that the following
|
|
|
697 IR constructs produce base pointers: loads from the heap, addresses of global
|
|
|
698 variables, function arguments, function return values. Constant pointers (such
|
|
|
699 as null) are also assumed to be base pointers. In practice, this constraint
|
|
|
700 can be relaxed to producing interior derived pointers provided the target
|
|
|
701 collector can find the associated allocation from an arbitrary interior
|
|
|
702 derived pointer.
|
|
|
703
|
|
|
704 In practice, RewriteStatepointsForGC can be run much later in the pass
|
|
|
705 pipeline, after most optimization is already done. This helps to improve
|
|
|
706 the quality of the generated code when compiled with garbage collection support.
|
|
|
707 In the long run, this is the intended usage model. At this time, a few details
|
|
|
708 have yet to be worked out about the semantic model required to guarantee this
|
|
|
709 is always correct. As such, please use with caution and report bugs.
|
|
|
710
|
|
|
711 .. _PlaceSafepoints:
|
|
|
712
|
|
|
713 PlaceSafepoints
|
|
|
714 ^^^^^^^^^^^^^^^^
|
|
|
715
|
|
|
716 The pass PlaceSafepoints transforms a function's IR by replacing any call or
|
|
|
717 invoke instructions with appropriate ``gc.statepoint`` and ``gc.result`` pairs,
|
|
|
718 and inserting safepoint polls sufficient to ensure running code checks for a
|
|
|
719 safepoint request on a timely manner. This pass is expected to be run before
|
|
|
720 RewriteStatepointsForGC and thus does not produce full relocation sequences.
|
|
|
721
|
|
|
722 As an example, given input IR of the following:
|
|
|
723
|
|
|
724 .. code-block:: llvm
|
|
|
725
|
|
|
726 define void @test() gc "statepoint-example" {
|
|
|
727 call void @foo()
|
|
|
728 ret void
|
|
|
729 }
|
|
|
730
|
|
|
731 declare void @do_safepoint()
|
|
|
732 define void @gc.safepoint_poll() {
|
|
|
733 call void @do_safepoint()
|
|
|
734 ret void
|
|
|
735 }
|
|
|
736
|
|
|
737
|
|
|
738 This pass would produce the following IR:
|
|
|
739
|
|
|
740 .. code-block:: llvm
|
|
|
741
|
|
|
742 define void @test() gc "statepoint-example" {
|
|
100
|
743 %safepoint_token = call token (i64, i32, void ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 2882400000, i32 0, void ()* @do_safepoint, i32 0, i32 0, i32 0, i32 0)
|
|
|
744 %safepoint_token1 = 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 0)
|
|
95
|
745 ret void
|
|
|
746 }
|
|
|
747
|
|
|
748 In 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.
|
|
|
749
|
|
|
750
|
|
|
751 At the moment, PlaceSafepoints can insert safepoint polls at method entry and
|
|
|
752 loop backedges locations. Extending this to work with return polls would be
|
|
|
753 straight forward if desired.
|
|
|
754
|
|
|
755 PlaceSafepoints includes a number of optimizations to avoid placing safepoint
|
|
|
756 polls at particular sites unless needed to ensure timely execution of a poll
|
|
|
757 under normal conditions. PlaceSafepoints does not attempt to ensure timely
|
|
|
758 execution of a poll under worst case conditions such as heavy system paging.
|
|
|
759
|
|
|
760 The implementation of a safepoint poll action is specified by looking up a
|
|
|
761 function of the name ``gc.safepoint_poll`` in the containing Module. The body
|
|
|
762 of this function is inserted at each poll site desired. While calls or invokes
|
|
|
763 inside this method are transformed to a ``gc.statepoints``, recursive poll
|
|
|
764 insertion is not performed.
|
|
|
765
|
|
|
766 By default PlaceSafepoints passes in ``0xABCDEF00`` as the statepoint
|
|
|
767 ID and ``0`` as the number of patchable bytes to the newly constructed
|
|
|
768 ``gc.statepoint``. These values can be configured on a per-callsite
|
|
|
769 basis using the attributes ``"statepoint-id"`` and
|
|
|
770 ``"statepoint-num-patch-bytes"``. If a call site is marked with a
|
|
|
771 ``"statepoint-id"`` function attribute and its value is a positive
|
|
|
772 integer (represented as a string), then that value is used as the ID
|
|
|
773 of the newly constructed ``gc.statepoint``. If a call site is marked
|
|
|
774 with a ``"statepoint-num-patch-bytes"`` function attribute and its
|
|
|
775 value is a positive integer, then that value is used as the 'num patch
|
|
|
776 bytes' parameter of the newly constructed ``gc.statepoint``. The
|
|
|
777 ``"statepoint-id"`` and ``"statepoint-num-patch-bytes"`` attributes
|
|
|
778 are not propagated to the ``gc.statepoint`` call or invoke if they
|
|
|
779 could be successfully parsed.
|
|
|
780
|
|
|
781 If you are scheduling the RewriteStatepointsForGC pass late in the pass order,
|
|
|
782 you should probably schedule this pass immediately before it. The exception
|
|
|
783 would be if you need to preserve abstract frame information (e.g. for
|
|
|
784 deoptimization or introspection) at safepoints. In that case, ask on the
|
|
|
785 llvm-dev mailing list for suggestions.
|
|
|
786
|
|
|
787
|
|
|
788 Supported Architectures
|
|
|
789 =======================
|
|
|
790
|
|
|
791 Support for statepoint generation requires some code for each backend.
|
|
|
792 Today, only X86_64 is supported.
|
|
|
793
|
|
83
|
794 Bugs and Enhancements
|
|
|
795 =====================
|
|
|
796
|
|
|
797 Currently known bugs and enhancements under consideration can be
|
|
|
798 tracked by performing a `bugzilla search
|
|
|
799 <http://llvm.org/bugs/buglist.cgi?cmdtype=runnamed&namedcmd=Statepoint%20Bugs&list_id=64342>`_
|
|
|
800 for [Statepoint] in the summary field. When filing new bugs, please
|
|
|
801 use this tag so that interested parties see the newly filed bug. As
|
|
95
|
802 with most LLVM features, design discussions take place on `llvm-dev
|
|
|
803 <http://lists.llvm.org/mailman/listinfo/llvm-dev>`_, and patches
|
|
83
|
804 should be sent to `llvm-commits
|
|
95
|
805 <http://lists.llvm.org/mailman/listinfo/llvm-commits>`_ for review.
|
|
83
|
806
|
