0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1 =====================================
|
|
95
|
2 Garbage Collection with LLVM
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
3 =====================================
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
4
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
5 .. contents::
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
6 :local:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
7
|
|
95
|
8 Abstract
|
|
|
9 ========
|
|
|
10
|
|
|
11 This document covers how to integrate LLVM into a compiler for a language which
|
|
|
12 supports garbage collection. **Note that LLVM itself does not provide a
|
|
|
13 garbage collector.** You must provide your own.
|
|
|
14
|
|
|
15 Quick Start
|
|
|
16 ============
|
|
|
17
|
|
|
18 First, you should pick a collector strategy. LLVM includes a number of built
|
|
|
19 in ones, but you can also implement a loadable plugin with a custom definition.
|
|
|
20 Note that the collector strategy is a description of how LLVM should generate
|
|
|
21 code such that it interacts with your collector and runtime, not a description
|
|
|
22 of the collector itself.
|
|
|
23
|
|
|
24 Next, mark your generated functions as using your chosen collector strategy.
|
|
|
25 From c++, you can call:
|
|
|
26
|
|
|
27 .. code-block:: c++
|
|
|
28
|
|
|
29 F.setGC(<collector description name>);
|
|
|
30
|
|
|
31
|
|
|
32 This will produce IR like the following fragment:
|
|
|
33
|
|
|
34 .. code-block:: llvm
|
|
|
35
|
|
|
36 define void @foo() gc "<collector description name>" { ... }
|
|
|
37
|
|
|
38
|
|
|
39 When generating LLVM IR for your functions, you will need to:
|
|
|
40
|
|
|
41 * Use ``@llvm.gcread`` and/or ``@llvm.gcwrite`` in place of standard load and
|
|
|
42 store instructions. These intrinsics are used to represent load and store
|
|
|
43 barriers. If you collector does not require such barriers, you can skip
|
|
|
44 this step.
|
|
|
45
|
|
|
46 * Use the memory allocation routines provided by your garbage collector's
|
|
|
47 runtime library.
|
|
|
48
|
|
|
49 * If your collector requires them, generate type maps according to your
|
|
|
50 runtime's binary interface. LLVM is not involved in the process. In
|
|
|
51 particular, the LLVM type system is not suitable for conveying such
|
|
|
52 information though the compiler.
|
|
|
53
|
|
|
54 * Insert any coordination code required for interacting with your collector.
|
|
|
55 Many collectors require running application code to periodically check a
|
|
|
56 flag and conditionally call a runtime function. This is often referred to
|
|
|
57 as a safepoint poll.
|
|
|
58
|
|
|
59 You will need to identify roots (i.e. references to heap objects your collector
|
|
|
60 needs to know about) in your generated IR, so that LLVM can encode them into
|
|
|
61 your final stack maps. Depending on the collector strategy chosen, this is
|
|
|
62 accomplished by using either the ``@llvm.gcroot`` intrinsics or an
|
|
|
63 ``gc.statepoint`` relocation sequence.
|
|
|
64
|
|
|
65 Don't forget to create a root for each intermediate value that is generated when
|
|
|
66 evaluating an expression. In ``h(f(), g())``, the result of ``f()`` could
|
|
|
67 easily be collected if evaluating ``g()`` triggers a collection.
|
|
|
68
|
|
|
69 Finally, you need to link your runtime library with the generated program
|
|
|
70 executable (for a static compiler) or ensure the appropriate symbols are
|
|
|
71 available for the runtime linker (for a JIT compiler).
|
|
|
72
|
|
|
73
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
74 Introduction
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
75 ============
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
76
|
|
95
|
77 What is Garbage Collection?
|
|
|
78 ---------------------------
|
|
|
79
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
80 Garbage collection is a widely used technique that frees the programmer from
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
81 having to know the lifetimes of heap objects, making software easier to produce
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
82 and maintain. Many programming languages rely on garbage collection for
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
83 automatic memory management. There are two primary forms of garbage collection:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
84 conservative and accurate.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
85
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
86 Conservative garbage collection often does not require any special support from
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
87 either the language or the compiler: it can handle non-type-safe programming
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
88 languages (such as C/C++) and does not require any special information from the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
89 compiler. The `Boehm collector
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
90 <http://www.hpl.hp.com/personal/Hans_Boehm/gc/>`__ is an example of a
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
91 state-of-the-art conservative collector.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
92
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
93 Accurate garbage collection requires the ability to identify all pointers in the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
94 program at run-time (which requires that the source-language be type-safe in
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
95 most cases). Identifying pointers at run-time requires compiler support to
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
96 locate all places that hold live pointer variables at run-time, including the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
97 :ref:`processor stack and registers <gcroot>`.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
98
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
99 Conservative garbage collection is attractive because it does not require any
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
100 special compiler support, but it does have problems. In particular, because the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
101 conservative garbage collector cannot *know* that a particular word in the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
102 machine is a pointer, it cannot move live objects in the heap (preventing the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
103 use of compacting and generational GC algorithms) and it can occasionally suffer
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
104 from memory leaks due to integer values that happen to point to objects in the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
105 program. In addition, some aggressive compiler transformations can break
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
106 conservative garbage collectors (though these seem rare in practice).
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
107
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
108 Accurate garbage collectors do not suffer from any of these problems, but they
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
109 can suffer from degraded scalar optimization of the program. In particular,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
110 because the runtime must be able to identify and update all pointers active in
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
111 the program, some optimizations are less effective. In practice, however, the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
112 locality and performance benefits of using aggressive garbage collection
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
113 techniques dominates any low-level losses.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
114
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
115 This document describes the mechanisms and interfaces provided by LLVM to
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
116 support accurate garbage collection.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
117
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
118 Goals and non-goals
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
119 -------------------
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
120
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
121 LLVM's intermediate representation provides :ref:`garbage collection intrinsics
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
122 <gc_intrinsics>` that offer support for a broad class of collector models. For
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
123 instance, the intrinsics permit:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
124
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
125 * semi-space collectors
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
126
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
127 * mark-sweep collectors
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
128
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
129 * generational collectors
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
130
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
131 * incremental collectors
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
132
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
133 * concurrent collectors
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
134
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
135 * cooperative collectors
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
136
|
|
95
|
137 * reference counting
|
|
|
138
|
|
|
139 We hope that the support built into the LLVM IR is sufficient to support a
|
|
|
140 broad class of garbage collected languages including Scheme, ML, Java, C#,
|
|
|
141 Perl, Python, Lua, Ruby, other scripting languages, and more.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
142
|
|
95
|
143 Note that LLVM **does not itself provide a garbage collector** --- this should
|
|
|
144 be part of your language's runtime library. LLVM provides a framework for
|
|
|
145 describing the garbage collectors requirements to the compiler. In particular,
|
|
|
146 LLVM provides support for generating stack maps at call sites, polling for a
|
|
|
147 safepoint, and emitting load and store barriers. You can also extend LLVM -
|
|
|
148 possibly through a loadable :ref:`code generation plugins <plugin>` - to
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
149 generate code and data structures which conforms to the *binary interface*
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
150 specified by the *runtime library*. This is similar to the relationship between
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
151 LLVM and DWARF debugging info, for example. The difference primarily lies in
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
152 the lack of an established standard in the domain of garbage collection --- thus
|
|
95
|
153 the need for a flexible extension mechanism.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
154
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
155 The aspects of the binary interface with which LLVM's GC support is
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
156 concerned are:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
157
|
|
95
|
158 * Creation of GC safepoints within code where collection is allowed to execute
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
159 safely.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
160
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
161 * Computation of the stack map. For each safe point in the code, object
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
162 references within the stack frame must be identified so that the collector may
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
163 traverse and perhaps update them.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
164
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
165 * Write barriers when storing object references to the heap. These are commonly
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
166 used to optimize incremental scans in generational collectors.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
167
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
168 * Emission of read barriers when loading object references. These are useful
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
169 for interoperating with concurrent collectors.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
170
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
171 There are additional areas that LLVM does not directly address:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
172
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
173 * Registration of global roots with the runtime.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
174
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
175 * Registration of stack map entries with the runtime.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
176
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
177 * The functions used by the program to allocate memory, trigger a collection,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
178 etc.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
179
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
180 * Computation or compilation of type maps, or registration of them with the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
181 runtime. These are used to crawl the heap for object references.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
182
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
183 In general, LLVM's support for GC does not include features which can be
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
184 adequately addressed with other features of the IR and does not specify a
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
185 particular binary interface. On the plus side, this means that you should be
|
|
95
|
186 able to integrate LLVM with an existing runtime. On the other hand, it can
|
|
|
187 have the effect of leaving a lot of work for the developer of a novel
|
|
|
188 language. We try to mitigate this by providing built in collector strategy
|
|
|
189 descriptions that can work with many common collector designs and easy
|
|
|
190 extension points. If you don't already have a specific binary interface
|
|
|
191 you need to support, we recommend trying to use one of these built in collector
|
|
|
192 strategies.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
193
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
194 .. _gc_intrinsics:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
195
|
|
95
|
196 LLVM IR Features
|
|
|
197 ================
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
198
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
199 This section describes the garbage collection facilities provided by the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
200 :doc:`LLVM intermediate representation <LangRef>`. The exact behavior of these
|
|
95
|
201 IR features is specified by the selected :ref:`GC strategy description
|
|
|
202 <plugin>`.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
203
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
204 Specifying GC code generation: ``gc "..."``
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
205 -------------------------------------------
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
206
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
207 .. code-block:: llvm
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
208
|
|
95
|
209 define <returntype> @name(...) gc "name" { ... }
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
210
|
|
95
|
211 The ``gc`` function attribute is used to specify the desired GC strategy to the
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
212 compiler. Its programmatic equivalent is the ``setGC`` method of ``Function``.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
213
|
|
95
|
214 Setting ``gc "name"`` on a function triggers a search for a matching subclass
|
|
|
215 of GCStrategy. Some collector strategies are built in. You can add others
|
|
|
216 using either the loadable plugin mechanism, or by patching your copy of LLVM.
|
|
|
217 It is the selected GC strategy which defines the exact nature of the code
|
|
|
218 generated to support GC. If none is found, the compiler will raise an error.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
219
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
220 Specifying the GC style on a per-function basis allows LLVM to link together
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
221 programs that use different garbage collection algorithms (or none at all).
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
222
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
223 .. _gcroot:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
224
|
|
95
|
225 Identifying GC roots on the stack
|
|
|
226 ----------------------------------
|
|
|
227
|
|
|
228 LLVM currently supports two different mechanisms for describing references in
|
|
|
229 compiled code at safepoints. ``llvm.gcroot`` is the older mechanism;
|
|
|
230 ``gc.statepoint`` has been added more recently. At the moment, you can choose
|
|
|
231 either implementation (on a per :ref:`GC strategy <plugin>` basis). Longer
|
|
|
232 term, we will probably either migrate away from ``llvm.gcroot`` entirely, or
|
|
|
233 substantially merge their implementations. Note that most new development
|
|
|
234 work is focused on ``gc.statepoint``.
|
|
|
235
|
|
|
236 Using ``gc.statepoint``
|
|
|
237 ^^^^^^^^^^^^^^^^^^^^^^^^
|
|
|
238 :doc:`This page <Statepoints>` contains detailed documentation for
|
|
|
239 ``gc.statepoint``.
|
|
|
240
|
|
|
241 Using ``llvm.gcwrite``
|
|
|
242 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
243
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
244 .. code-block:: llvm
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
245
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
246 void @llvm.gcroot(i8** %ptrloc, i8* %metadata)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
247
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
248 The ``llvm.gcroot`` intrinsic is used to inform LLVM that a stack variable
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
249 references an object on the heap and is to be tracked for garbage collection.
|
|
95
|
250 The exact impact on generated code is specified by the Function's selected
|
|
|
251 :ref:`GC strategy <plugin>`. All calls to ``llvm.gcroot`` **must** reside
|
|
|
252 inside the first basic block.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
253
|
|
95
|
254 The first argument **must** be a value referring to an alloca instruction or a
|
|
|
255 bitcast of an alloca. The second contains a pointer to metadata that should be
|
|
|
256 associated with the pointer, and **must** be a constant or global value
|
|
|
257 address. If your target collector uses tags, use a null pointer for metadata.
|
|
|
258
|
|
|
259 A compiler which performs manual SSA construction **must** ensure that SSA
|
|
|
260 values representing GC references are stored in to the alloca passed to the
|
|
|
261 respective ``gcroot`` before every call site and reloaded after every call.
|
|
|
262 A compiler which uses mem2reg to raise imperative code using ``alloca`` into
|
|
|
263 SSA form need only add a call to ``@llvm.gcroot`` for those variables which
|
|
|
264 are pointers into the GC heap.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
265
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
266 It is also important to mark intermediate values with ``llvm.gcroot``. For
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
267 example, consider ``h(f(), g())``. Beware leaking the result of ``f()`` in the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
268 case that ``g()`` triggers a collection. Note, that stack variables must be
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
269 initialized and marked with ``llvm.gcroot`` in function's prologue.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
270
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
271 The ``%metadata`` argument can be used to avoid requiring heap objects to have
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
272 'isa' pointers or tag bits. [Appel89_, Goldberg91_, Tolmach94_] If specified,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
273 its value will be tracked along with the location of the pointer in the stack
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
274 frame.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
275
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
276 Consider the following fragment of Java code:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
277
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
278 .. code-block:: java
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
279
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
280 {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
281 Object X; // A null-initialized reference to an object
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
282 ...
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
283 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
284
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
285 This block (which may be located in the middle of a function or in a loop nest),
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
286 could be compiled to this LLVM code:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
287
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
288 .. code-block:: llvm
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
289
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
290 Entry:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
291 ;; In the entry block for the function, allocate the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
292 ;; stack space for X, which is an LLVM pointer.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
293 %X = alloca %Object*
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
294
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
295 ;; Tell LLVM that the stack space is a stack root.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
296 ;; Java has type-tags on objects, so we pass null as metadata.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
297 %tmp = bitcast %Object** %X to i8**
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
298 call void @llvm.gcroot(i8** %tmp, i8* null)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
299 ...
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
300
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
301 ;; "CodeBlock" is the block corresponding to the start
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
302 ;; of the scope above.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
303 CodeBlock:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
304 ;; Java null-initializes pointers.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
305 store %Object* null, %Object** %X
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
306
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
307 ...
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
308
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
309 ;; As the pointer goes out of scope, store a null value into
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
310 ;; it, to indicate that the value is no longer live.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
311 store %Object* null, %Object** %X
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
312 ...
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
313
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
314 Reading and writing references in the heap
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
315 ------------------------------------------
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
316
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
317 Some collectors need to be informed when the mutator (the program that needs
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
318 garbage collection) either reads a pointer from or writes a pointer to a field
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
319 of a heap object. The code fragments inserted at these points are called *read
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
320 barriers* and *write barriers*, respectively. The amount of code that needs to
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
321 be executed is usually quite small and not on the critical path of any
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
322 computation, so the overall performance impact of the barrier is tolerable.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
323
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
324 Barriers often require access to the *object pointer* rather than the *derived
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
325 pointer* (which is a pointer to the field within the object). Accordingly,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
326 these intrinsics take both pointers as separate arguments for completeness. In
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
327 this snippet, ``%object`` is the object pointer, and ``%derived`` is the derived
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
328 pointer:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
329
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
330 .. code-block:: llvm
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
331
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
332 ;; An array type.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
333 %class.Array = type { %class.Object, i32, [0 x %class.Object*] }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
334 ...
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
335
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
336 ;; Load the object pointer from a gcroot.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
337 %object = load %class.Array** %object_addr
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
338
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
339 ;; Compute the derived pointer.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
340 %derived = getelementptr %object, i32 0, i32 2, i32 %n
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
341
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
342 LLVM does not enforce this relationship between the object and derived pointer
|
|
95
|
343 (although a particular :ref:`collector strategy <plugin>` might). However, it
|
|
|
344 would be an unusual collector that violated it.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
345
|
|
95
|
346 The use of these intrinsics is naturally optional if the target GC does not
|
|
|
347 require the corresponding barrier. The GC strategy used with such a collector
|
|
|
348 should replace the intrinsic calls with the corresponding ``load`` or
|
|
|
349 ``store`` instruction if they are used.
|
|
|
350
|
|
|
351 One known deficiency with the current design is that the barrier intrinsics do
|
|
|
352 not include the size or alignment of the underlying operation performed. It is
|
|
|
353 currently assumed that the operation is of pointer size and the alignment is
|
|
|
354 assumed to be the target machine's default alignment.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
355
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
356 Write barrier: ``llvm.gcwrite``
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
357 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
358
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
359 .. code-block:: llvm
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
360
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
361 void @llvm.gcwrite(i8* %value, i8* %object, i8** %derived)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
362
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
363 For write barriers, LLVM provides the ``llvm.gcwrite`` intrinsic function. It
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
364 has exactly the same semantics as a non-volatile ``store`` to the derived
|
|
95
|
365 pointer (the third argument). The exact code generated is specified by the
|
|
|
366 Function's selected :ref:`GC strategy <plugin>`.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
367
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
368 Many important algorithms require write barriers, including generational and
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
369 concurrent collectors. Additionally, write barriers could be used to implement
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
370 reference counting.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
371
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
372 Read barrier: ``llvm.gcread``
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
373 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
374
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
375 .. code-block:: llvm
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
376
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
377 i8* @llvm.gcread(i8* %object, i8** %derived)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
378
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
379 For read barriers, LLVM provides the ``llvm.gcread`` intrinsic function. It has
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
380 exactly the same semantics as a non-volatile ``load`` from the derived pointer
|
|
95
|
381 (the second argument). The exact code generated is specified by the Function's
|
|
|
382 selected :ref:`GC strategy <plugin>`.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
383
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
384 Read barriers are needed by fewer algorithms than write barriers, and may have a
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
385 greater performance impact since pointer reads are more frequent than writes.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
386
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
387 .. _plugin:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
388
|
|
95
|
389 .. _builtin-gc-strategies:
|
|
|
390
|
|
|
391 Built In GC Strategies
|
|
|
392 ======================
|
|
|
393
|
|
|
394 LLVM includes built in support for several varieties of garbage collectors.
|
|
|
395
|
|
|
396 The Shadow Stack GC
|
|
|
397 ----------------------
|
|
|
398
|
|
|
399 To use this collector strategy, mark your functions with:
|
|
|
400
|
|
|
401 .. code-block:: c++
|
|
|
402
|
|
|
403 F.setGC("shadow-stack");
|
|
|
404
|
|
|
405 Unlike many GC algorithms which rely on a cooperative code generator to compile
|
|
|
406 stack maps, this algorithm carefully maintains a linked list of stack roots
|
|
|
407 [:ref:`Henderson2002 <henderson02>`]. This so-called "shadow stack" mirrors the
|
|
|
408 machine stack. Maintaining this data structure is slower than using a stack map
|
|
|
409 compiled into the executable as constant data, but has a significant portability
|
|
|
410 advantage because it requires no special support from the target code generator,
|
|
|
411 and does not require tricky platform-specific code to crawl the machine stack.
|
|
|
412
|
|
|
413 The tradeoff for this simplicity and portability is:
|
|
|
414
|
|
|
415 * High overhead per function call.
|
|
|
416
|
|
|
417 * Not thread-safe.
|
|
|
418
|
|
|
419 Still, it's an easy way to get started. After your compiler and runtime are up
|
|
|
420 and running, writing a :ref:`plugin <plugin>` will allow you to take advantage
|
|
|
421 of :ref:`more advanced GC features <collector-algos>` of LLVM in order to
|
|
|
422 improve performance.
|
|
|
423
|
|
|
424
|
|
|
425 The shadow stack doesn't imply a memory allocation algorithm. A semispace
|
|
|
426 collector or building atop ``malloc`` are great places to start, and can be
|
|
|
427 implemented with very little code.
|
|
|
428
|
|
|
429 When it comes time to collect, however, your runtime needs to traverse the stack
|
|
|
430 roots, and for this it needs to integrate with the shadow stack. Luckily, doing
|
|
|
431 so is very simple. (This code is heavily commented to help you understand the
|
|
|
432 data structure, but there are only 20 lines of meaningful code.)
|
|
|
433
|
|
|
434 .. code-block:: c++
|
|
|
435
|
|
|
436 /// @brief The map for a single function's stack frame. One of these is
|
|
|
437 /// compiled as constant data into the executable for each function.
|
|
|
438 ///
|
|
|
439 /// Storage of metadata values is elided if the %metadata parameter to
|
|
|
440 /// @llvm.gcroot is null.
|
|
|
441 struct FrameMap {
|
|
|
442 int32_t NumRoots; //< Number of roots in stack frame.
|
|
|
443 int32_t NumMeta; //< Number of metadata entries. May be < NumRoots.
|
|
|
444 const void *Meta[0]; //< Metadata for each root.
|
|
|
445 };
|
|
|
446
|
|
|
447 /// @brief A link in the dynamic shadow stack. One of these is embedded in
|
|
|
448 /// the stack frame of each function on the call stack.
|
|
|
449 struct StackEntry {
|
|
|
450 StackEntry *Next; //< Link to next stack entry (the caller's).
|
|
|
451 const FrameMap *Map; //< Pointer to constant FrameMap.
|
|
|
452 void *Roots[0]; //< Stack roots (in-place array).
|
|
|
453 };
|
|
|
454
|
|
|
455 /// @brief The head of the singly-linked list of StackEntries. Functions push
|
|
|
456 /// and pop onto this in their prologue and epilogue.
|
|
|
457 ///
|
|
|
458 /// Since there is only a global list, this technique is not threadsafe.
|
|
|
459 StackEntry *llvm_gc_root_chain;
|
|
|
460
|
|
|
461 /// @brief Calls Visitor(root, meta) for each GC root on the stack.
|
|
|
462 /// root and meta are exactly the values passed to
|
|
|
463 /// @llvm.gcroot.
|
|
|
464 ///
|
|
|
465 /// Visitor could be a function to recursively mark live objects. Or it
|
|
|
466 /// might copy them to another heap or generation.
|
|
|
467 ///
|
|
|
468 /// @param Visitor A function to invoke for every GC root on the stack.
|
|
|
469 void visitGCRoots(void (*Visitor)(void **Root, const void *Meta)) {
|
|
|
470 for (StackEntry *R = llvm_gc_root_chain; R; R = R->Next) {
|
|
|
471 unsigned i = 0;
|
|
|
472
|
|
|
473 // For roots [0, NumMeta), the metadata pointer is in the FrameMap.
|
|
|
474 for (unsigned e = R->Map->NumMeta; i != e; ++i)
|
|
|
475 Visitor(&R->Roots[i], R->Map->Meta[i]);
|
|
|
476
|
|
|
477 // For roots [NumMeta, NumRoots), the metadata pointer is null.
|
|
|
478 for (unsigned e = R->Map->NumRoots; i != e; ++i)
|
|
|
479 Visitor(&R->Roots[i], NULL);
|
|
|
480 }
|
|
|
481 }
|
|
|
482
|
|
|
483
|
|
|
484 The 'Erlang' and 'Ocaml' GCs
|
|
|
485 -----------------------------
|
|
|
486
|
|
|
487 LLVM ships with two example collectors which leverage the ``gcroot``
|
|
|
488 mechanisms. To our knowledge, these are not actually used by any language
|
|
|
489 runtime, but they do provide a reasonable starting point for someone interested
|
|
|
490 in writing an ``gcroot`` compatible GC plugin. In particular, these are the
|
|
|
491 only in tree examples of how to produce a custom binary stack map format using
|
|
|
492 a ``gcroot`` strategy.
|
|
|
493
|
|
|
494 As there names imply, the binary format produced is intended to model that
|
|
|
495 used by the Erlang and OCaml compilers respectively.
|
|
|
496
|
|
|
497 .. _statepoint_example_gc:
|
|
|
498
|
|
|
499 The Statepoint Example GC
|
|
|
500 -------------------------
|
|
|
501
|
|
|
502 .. code-block:: c++
|
|
|
503
|
|
|
504 F.setGC("statepoint-example");
|
|
|
505
|
|
|
506 This GC provides an example of how one might use the infrastructure provided
|
|
|
507 by ``gc.statepoint``. This example GC is compatible with the
|
|
|
508 :ref:`PlaceSafepoints` and :ref:`RewriteStatepointsForGC` utility passes
|
|
|
509 which simplify ``gc.statepoint`` sequence insertion. If you need to build a
|
|
|
510 custom GC strategy around the ``gc.statepoints`` mechanisms, it is recommended
|
|
|
511 that you use this one as a starting point.
|
|
|
512
|
|
|
513 This GC strategy does not support read or write barriers. As a result, these
|
|
|
514 intrinsics are lowered to normal loads and stores.
|
|
|
515
|
|
|
516 The stack map format generated by this GC strategy can be found in the
|
|
|
517 :ref:`stackmap-section` using a format documented :ref:`here
|
|
|
518 <statepoint-stackmap-format>`. This format is intended to be the standard
|
|
|
519 format supported by LLVM going forward.
|
|
|
520
|
|
|
521 The CoreCLR GC
|
|
|
522 -------------------------
|
|
|
523
|
|
|
524 .. code-block:: c++
|
|
|
525
|
|
|
526 F.setGC("coreclr");
|
|
|
527
|
|
|
528 This GC leverages the ``gc.statepoint`` mechanism to support the
|
|
|
529 `CoreCLR <https://github.com/dotnet/coreclr>`__ runtime.
|
|
|
530
|
|
|
531 Support for this GC strategy is a work in progress. This strategy will
|
|
|
532 differ from
|
|
|
533 :ref:`statepoint-example GC<statepoint_example_gc>` strategy in
|
|
|
534 certain aspects like:
|
|
|
535
|
|
|
536 * Base-pointers of interior pointers are not explicitly
|
|
|
537 tracked and reported.
|
|
|
538
|
|
|
539 * A different format is used for encoding stack maps.
|
|
|
540
|
|
|
541 * Safe-point polls are only needed before loop-back edges
|
|
|
542 and before tail-calls (not needed at function-entry).
|
|
|
543
|
|
|
544 Custom GC Strategies
|
|
|
545 ====================
|
|
|
546
|
|
|
547 If none of the built in GC strategy descriptions met your needs above, you will
|
|
|
548 need to define a custom GCStrategy and possibly, a custom LLVM pass to perform
|
|
|
549 lowering. Your best example of where to start defining a custom GCStrategy
|
|
|
550 would be to look at one of the built in strategies.
|
|
|
551
|
|
|
552 You may be able to structure this additional code as a loadable plugin library.
|
|
|
553 Loadable plugins are sufficient if all you need is to enable a different
|
|
|
554 combination of built in functionality, but if you need to provide a custom
|
|
|
555 lowering pass, you will need to build a patched version of LLVM. If you think
|
|
|
556 you need a patched build, please ask for advice on llvm-dev. There may be an
|
|
|
557 easy way we can extend the support to make it work for your use case without
|
|
|
558 requiring a custom build.
|
|
|
559
|
|
|
560 Collector Requirements
|
|
|
561 ----------------------
|
|
|
562
|
|
|
563 You should be able to leverage any existing collector library that includes the following elements:
|
|
|
564
|
|
|
565 #. A memory allocator which exposes an allocation function your compiled
|
|
|
566 code can call.
|
|
|
567
|
|
|
568 #. A binary format for the stack map. A stack map describes the location
|
|
|
569 of references at a safepoint and is used by precise collectors to identify
|
|
|
570 references within a stack frame on the machine stack. Note that collectors
|
|
|
571 which conservatively scan the stack don't require such a structure.
|
|
|
572
|
|
|
573 #. A stack crawler to discover functions on the call stack, and enumerate the
|
|
|
574 references listed in the stack map for each call site.
|
|
|
575
|
|
|
576 #. A mechanism for identifying references in global locations (e.g. global
|
|
|
577 variables).
|
|
|
578
|
|
|
579 #. If you collector requires them, an LLVM IR implementation of your collectors
|
|
|
580 load and store barriers. Note that since many collectors don't require
|
|
|
581 barriers at all, LLVM defaults to lowering such barriers to normal loads
|
|
|
582 and stores unless you arrange otherwise.
|
|
|
583
|
|
|
584
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
585 Implementing a collector plugin
|
|
95
|
586 -------------------------------
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
587
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
588 User code specifies which GC code generation to use with the ``gc`` function
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
589 attribute or, equivalently, with the ``setGC`` method of ``Function``.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
590
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
591 To implement a GC plugin, it is necessary to subclass ``llvm::GCStrategy``,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
592 which can be accomplished in a few lines of boilerplate code. LLVM's
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
593 infrastructure provides access to several important algorithms. For an
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
594 uncontroversial collector, all that remains may be to compile LLVM's computed
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
595 stack map to assembly code (using the binary representation expected by the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
596 runtime library). This can be accomplished in about 100 lines of code.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
597
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
598 This is not the appropriate place to implement a garbage collected heap or a
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
599 garbage collector itself. That code should exist in the language's runtime
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
600 library. The compiler plugin is responsible for generating code which conforms
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
601 to the binary interface defined by library, most essentially the :ref:`stack map
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
602 <stack-map>`.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
603
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
604 To subclass ``llvm::GCStrategy`` and register it with the compiler:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
605
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
606 .. code-block:: c++
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
607
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
608 // lib/MyGC/MyGC.cpp - Example LLVM GC plugin
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
609
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
610 #include "llvm/CodeGen/GCStrategy.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
611 #include "llvm/CodeGen/GCMetadata.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
612 #include "llvm/Support/Compiler.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
613
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
614 using namespace llvm;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
615
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
616 namespace {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
617 class LLVM_LIBRARY_VISIBILITY MyGC : public GCStrategy {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
618 public:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
619 MyGC() {}
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
620 };
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
621
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
622 GCRegistry::Add<MyGC>
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
623 X("mygc", "My bespoke garbage collector.");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
624 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
625
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
626 This boilerplate collector does nothing. More specifically:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
627
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
628 * ``llvm.gcread`` calls are replaced with the corresponding ``load``
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
629 instruction.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
630
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
631 * ``llvm.gcwrite`` calls are replaced with the corresponding ``store``
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
632 instruction.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
633
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
634 * No safe points are added to the code.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
635
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
636 * The stack map is not compiled into the executable.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
637
|
|
77
|
638 Using the LLVM makefiles, this code
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
639 can be compiled as a plugin using a simple makefile:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
640
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
641 .. code-block:: make
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
642
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
643 # lib/MyGC/Makefile
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
644
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
645 LEVEL := ../..
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
646 LIBRARYNAME = MyGC
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
647 LOADABLE_MODULE = 1
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
648
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
649 include $(LEVEL)/Makefile.common
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
650
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
651 Once the plugin is compiled, code using it may be compiled using ``llc
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
652 -load=MyGC.so`` (though MyGC.so may have some other platform-specific
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
653 extension):
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
654
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
655 ::
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
656
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
657 $ cat sample.ll
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
658 define void @f() gc "mygc" {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
659 entry:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
660 ret void
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
661 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
662 $ llvm-as < sample.ll | llc -load=MyGC.so
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
663
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
664 It is also possible to statically link the collector plugin into tools, such as
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
665 a language-specific compiler front-end.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
666
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
667 .. _collector-algos:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
668
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
669 Overview of available features
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
670 ------------------------------
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
671
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
672 ``GCStrategy`` provides a range of features through which a plugin may do useful
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
673 work. Some of these are callbacks, some are algorithms that can be enabled,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
674 disabled, or customized. This matrix summarizes the supported (and planned)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
675 features and correlates them with the collection techniques which typically
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
676 require them.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
677
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
678 .. |v| unicode:: 0x2714
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
679 :trim:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
680
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
681 .. |x| unicode:: 0x2718
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
682 :trim:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
683
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
684 +------------+------+--------+----------+-------+---------+-------------+----------+------------+
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
685 | Algorithm | Done | Shadow | refcount | mark- | copying | incremental | threaded | concurrent |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
686 | | | stack | | sweep | | | | |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
687 +============+======+========+==========+=======+=========+=============+==========+============+
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
688 | stack map | |v| | | | |x| | |x| | |x| | |x| | |x| |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
689 +------------+------+--------+----------+-------+---------+-------------+----------+------------+
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
690 | initialize | |v| | |x| | |x| | |x| | |x| | |x| | |x| | |x| |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
691 | roots | | | | | | | | |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
692 +------------+------+--------+----------+-------+---------+-------------+----------+------------+
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
693 | derived | NO | | | | | | **N**\* | **N**\* |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
694 | pointers | | | | | | | | |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
695 +------------+------+--------+----------+-------+---------+-------------+----------+------------+
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
696 | **custom | |v| | | | | | | | |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
697 | lowering** | | | | | | | | |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
698 +------------+------+--------+----------+-------+---------+-------------+----------+------------+
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
699 | *gcroot* | |v| | |x| | |x| | | | | | |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
700 +------------+------+--------+----------+-------+---------+-------------+----------+------------+
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
701 | *gcwrite* | |v| | | |x| | | | |x| | | |x| |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
702 +------------+------+--------+----------+-------+---------+-------------+----------+------------+
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
703 | *gcread* | |v| | | | | | | | |x| |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
704 +------------+------+--------+----------+-------+---------+-------------+----------+------------+
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
705 | **safe | | | | | | | | |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
706 | points** | | | | | | | | |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
707 +------------+------+--------+----------+-------+---------+-------------+----------+------------+
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
708 | *in | |v| | | | |x| | |x| | |x| | |x| | |x| |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
709 | calls* | | | | | | | | |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
710 +------------+------+--------+----------+-------+---------+-------------+----------+------------+
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
711 | *before | |v| | | | | | | |x| | |x| |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
712 | calls* | | | | | | | | |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
713 +------------+------+--------+----------+-------+---------+-------------+----------+------------+
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
714 | *for | NO | | | | | | **N** | **N** |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
715 | loops* | | | | | | | | |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
716 +------------+------+--------+----------+-------+---------+-------------+----------+------------+
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
717 | *before | |v| | | | | | | |x| | |x| |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
718 | escape* | | | | | | | | |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
719 +------------+------+--------+----------+-------+---------+-------------+----------+------------+
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
720 | emit code | NO | | | | | | **N** | **N** |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
721 | at safe | | | | | | | | |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
722 | points | | | | | | | | |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
723 +------------+------+--------+----------+-------+---------+-------------+----------+------------+
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
724 | **output** | | | | | | | | |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
725 +------------+------+--------+----------+-------+---------+-------------+----------+------------+
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
726 | *assembly* | |v| | | | |x| | |x| | |x| | |x| | |x| |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
727 +------------+------+--------+----------+-------+---------+-------------+----------+------------+
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
728 | *JIT* | NO | | | **?** | **?** | **?** | **?** | **?** |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
729 +------------+------+--------+----------+-------+---------+-------------+----------+------------+
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
730 | *obj* | NO | | | **?** | **?** | **?** | **?** | **?** |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
731 +------------+------+--------+----------+-------+---------+-------------+----------+------------+
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
732 | live | NO | | | **?** | **?** | **?** | **?** | **?** |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
733 | analysis | | | | | | | | |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
734 +------------+------+--------+----------+-------+---------+-------------+----------+------------+
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
735 | register | NO | | | **?** | **?** | **?** | **?** | **?** |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
736 | map | | | | | | | | |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
737 +------------+------+--------+----------+-------+---------+-------------+----------+------------+
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
738 | \* Derived pointers only pose a hasard to copying collections. |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
739 +------------+------+--------+----------+-------+---------+-------------+----------+------------+
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
740 | **?** denotes a feature which could be utilized if available. |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
741 +------------+------+--------+----------+-------+---------+-------------+----------+------------+
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
742
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
743 To be clear, the collection techniques above are defined as:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
744
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
745 Shadow Stack
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
746 The mutator carefully maintains a linked list of stack roots.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
747
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
748 Reference Counting
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
749 The mutator maintains a reference count for each object and frees an object
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
750 when its count falls to zero.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
751
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
752 Mark-Sweep
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
753 When the heap is exhausted, the collector marks reachable objects starting
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
754 from the roots, then deallocates unreachable objects in a sweep phase.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
755
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
756 Copying
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
757 As reachability analysis proceeds, the collector copies objects from one heap
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
758 area to another, compacting them in the process. Copying collectors enable
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
759 highly efficient "bump pointer" allocation and can improve locality of
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
760 reference.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
761
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
762 Incremental
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
763 (Including generational collectors.) Incremental collectors generally have all
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
764 the properties of a copying collector (regardless of whether the mature heap
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
765 is compacting), but bring the added complexity of requiring write barriers.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
766
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
767 Threaded
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
768 Denotes a multithreaded mutator; the collector must still stop the mutator
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
769 ("stop the world") before beginning reachability analysis. Stopping a
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
770 multithreaded mutator is a complicated problem. It generally requires highly
|
|
77
|
771 platform-specific code in the runtime, and the production of carefully
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
772 designed machine code at safe points.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
773
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
774 Concurrent
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
775 In this technique, the mutator and the collector run concurrently, with the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
776 goal of eliminating pause times. In a *cooperative* collector, the mutator
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
777 further aids with collection should a pause occur, allowing collection to take
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
778 advantage of multiprocessor hosts. The "stop the world" problem of threaded
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
779 collectors is generally still present to a limited extent. Sophisticated
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
780 marking algorithms are necessary. Read barriers may be necessary.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
781
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
782 As the matrix indicates, LLVM's garbage collection infrastructure is already
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
783 suitable for a wide variety of collectors, but does not currently extend to
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
784 multithreaded programs. This will be added in the future as there is
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
785 interest.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
786
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
787 .. _stack-map:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
788
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
789 Computing stack maps
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
790 --------------------
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
791
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
792 LLVM automatically computes a stack map. One of the most important features
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
793 of a ``GCStrategy`` is to compile this information into the executable in
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
794 the binary representation expected by the runtime library.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
795
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
796 The stack map consists of the location and identity of each GC root in the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
797 each function in the module. For each root:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
798
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
799 * ``RootNum``: The index of the root.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
800
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
801 * ``StackOffset``: The offset of the object relative to the frame pointer.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
802
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
803 * ``RootMetadata``: The value passed as the ``%metadata`` parameter to the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
804 ``@llvm.gcroot`` intrinsic.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
805
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
806 Also, for the function as a whole:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
807
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
808 * ``getFrameSize()``: The overall size of the function's initial stack frame,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
809 not accounting for any dynamic allocation.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
810
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
811 * ``roots_size()``: The count of roots in the function.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
812
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
813 To access the stack map, use ``GCFunctionMetadata::roots_begin()`` and
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
814 -``end()`` from the :ref:`GCMetadataPrinter <assembly>`:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
815
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
816 .. code-block:: c++
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
817
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
818 for (iterator I = begin(), E = end(); I != E; ++I) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
819 GCFunctionInfo *FI = *I;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
820 unsigned FrameSize = FI->getFrameSize();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
821 size_t RootCount = FI->roots_size();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
822
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
823 for (GCFunctionInfo::roots_iterator RI = FI->roots_begin(),
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
824 RE = FI->roots_end();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
825 RI != RE; ++RI) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
826 int RootNum = RI->Num;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
827 int RootStackOffset = RI->StackOffset;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
828 Constant *RootMetadata = RI->Metadata;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
829 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
830 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
831
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
832 If the ``llvm.gcroot`` intrinsic is eliminated before code generation by a
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
833 custom lowering pass, LLVM will compute an empty stack map. This may be useful
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
834 for collector plugins which implement reference counting or a shadow stack.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
835
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
836 .. _init-roots:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
837
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
838 Initializing roots to null: ``InitRoots``
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
839 -----------------------------------------
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
840
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
841 .. code-block:: c++
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
842
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
843 MyGC::MyGC() {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
844 InitRoots = true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
845 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
846
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
847 When set, LLVM will automatically initialize each root to ``null`` upon entry to
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
848 the function. This prevents the GC's sweep phase from visiting uninitialized
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
849 pointers, which will almost certainly cause it to crash. This initialization
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
850 occurs before custom lowering, so the two may be used together.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
851
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
852 Since LLVM does not yet compute liveness information, there is no means of
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
853 distinguishing an uninitialized stack root from an initialized one. Therefore,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
854 this feature should be used by all GC plugins. It is enabled by default.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
855
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
856 Custom lowering of intrinsics: ``CustomRoots``, ``CustomReadBarriers``, and ``CustomWriteBarriers``
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
857 ---------------------------------------------------------------------------------------------------
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
858
|
|
83
|
859 For GCs which use barriers or unusual treatment of stack roots, these
|
|
|
860 flags allow the collector to perform arbitrary transformations of the
|
|
|
861 LLVM IR:
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
862
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
863 .. code-block:: c++
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
864
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
865 class MyGC : public GCStrategy {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
866 public:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
867 MyGC() {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
868 CustomRoots = true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
869 CustomReadBarriers = true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
870 CustomWriteBarriers = true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
871 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
872 };
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
873
|
|
83
|
874 If any of these flags are set, LLVM suppresses its default lowering for
|
|
|
875 the corresponding intrinsics. Instead, you must provide a custom Pass
|
|
|
876 which lowers the intrinsics as desired. If you have opted in to custom
|
|
|
877 lowering of a particular intrinsic your pass **must** eliminate all
|
|
|
878 instances of the corresponding intrinsic in functions which opt in to
|
|
|
879 your GC. The best example of such a pass is the ShadowStackGC and it's
|
|
|
880 ShadowStackGCLowering pass.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
881
|
|
83
|
882 There is currently no way to register such a custom lowering pass
|
|
|
883 without building a custom copy of LLVM.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
884
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
885 .. _safe-points:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
886
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
887 Generating safe points: ``NeededSafePoints``
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
888 --------------------------------------------
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
889
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
890 LLVM can compute four kinds of safe points:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
891
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
892 .. code-block:: c++
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
893
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
894 namespace GC {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
895 /// PointKind - The type of a collector-safe point.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
896 ///
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
897 enum PointKind {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
898 Loop, //< Instr is a loop (backwards branch).
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
899 Return, //< Instr is a return instruction.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
900 PreCall, //< Instr is a call instruction.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
901 PostCall //< Instr is the return address of a call.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
902 };
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
903 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
904
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
905 A collector can request any combination of the four by setting the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
906 ``NeededSafePoints`` mask:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
907
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
908 .. code-block:: c++
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
909
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
910 MyGC::MyGC() {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
911 NeededSafePoints = 1 << GC::Loop
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
912 | 1 << GC::Return
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
913 | 1 << GC::PreCall
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
914 | 1 << GC::PostCall;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
915 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
916
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
917 It can then use the following routines to access safe points.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
918
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
919 .. code-block:: c++
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
920
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
921 for (iterator I = begin(), E = end(); I != E; ++I) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
922 GCFunctionInfo *MD = *I;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
923 size_t PointCount = MD->size();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
924
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
925 for (GCFunctionInfo::iterator PI = MD->begin(),
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
926 PE = MD->end(); PI != PE; ++PI) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
927 GC::PointKind PointKind = PI->Kind;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
928 unsigned PointNum = PI->Num;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
929 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
930 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
931
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
932 Almost every collector requires ``PostCall`` safe points, since these correspond
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
933 to the moments when the function is suspended during a call to a subroutine.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
934
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
935 Threaded programs generally require ``Loop`` safe points to guarantee that the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
936 application will reach a safe point within a bounded amount of time, even if it
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
937 is executing a long-running loop which contains no function calls.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
938
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
939 Threaded collectors may also require ``Return`` and ``PreCall`` safe points to
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
940 implement "stop the world" techniques using self-modifying code, where it is
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
941 important that the program not exit the function without reaching a safe point
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
942 (because only the topmost function has been patched).
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
943
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
944 .. _assembly:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
945
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
946 Emitting assembly code: ``GCMetadataPrinter``
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
947 ---------------------------------------------
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
948
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
949 LLVM allows a plugin to print arbitrary assembly code before and after the rest
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
950 of a module's assembly code. At the end of the module, the GC can compile the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
951 LLVM stack map into assembly code. (At the beginning, this information is not
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
952 yet computed.)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
953
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
954 Since AsmWriter and CodeGen are separate components of LLVM, a separate abstract
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
955 base class and registry is provided for printing assembly code, the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
956 ``GCMetadaPrinter`` and ``GCMetadataPrinterRegistry``. The AsmWriter will look
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
957 for such a subclass if the ``GCStrategy`` sets ``UsesMetadata``:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
958
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
959 .. code-block:: c++
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
960
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
961 MyGC::MyGC() {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
962 UsesMetadata = true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
963 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
964
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
965 This separation allows JIT-only clients to be smaller.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
966
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
967 Note that LLVM does not currently have analogous APIs to support code generation
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
968 in the JIT, nor using the object writers.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
969
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
970 .. code-block:: c++
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
971
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
972 // lib/MyGC/MyGCPrinter.cpp - Example LLVM GC printer
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
973
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
974 #include "llvm/CodeGen/GCMetadataPrinter.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
975 #include "llvm/Support/Compiler.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
976
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
977 using namespace llvm;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
978
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
979 namespace {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
980 class LLVM_LIBRARY_VISIBILITY MyGCPrinter : public GCMetadataPrinter {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
981 public:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
982 virtual void beginAssembly(AsmPrinter &AP);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
983
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
984 virtual void finishAssembly(AsmPrinter &AP);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
985 };
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
986
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
987 GCMetadataPrinterRegistry::Add<MyGCPrinter>
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
988 X("mygc", "My bespoke garbage collector.");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
989 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
990
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
991 The collector should use ``AsmPrinter`` to print portable assembly code. The
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
992 collector itself contains the stack map for the entire module, and may access
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
993 the ``GCFunctionInfo`` using its own ``begin()`` and ``end()`` methods. Here's
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
994 a realistic example:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
995
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
996 .. code-block:: c++
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
997
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
998 #include "llvm/CodeGen/AsmPrinter.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
999 #include "llvm/IR/Function.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1000 #include "llvm/IR/DataLayout.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1001 #include "llvm/Target/TargetAsmInfo.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1002 #include "llvm/Target/TargetMachine.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1003
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1004 void MyGCPrinter::beginAssembly(AsmPrinter &AP) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1005 // Nothing to do.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1006 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1007
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1008 void MyGCPrinter::finishAssembly(AsmPrinter &AP) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1009 MCStreamer &OS = AP.OutStreamer;
|
|
77
|
1010 unsigned IntPtrSize = AP.TM.getSubtargetImpl()->getDataLayout()->getPointerSize();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1011
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1012 // Put this in the data section.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1013 OS.SwitchSection(AP.getObjFileLowering().getDataSection());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1014
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1015 // For each function...
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1016 for (iterator FI = begin(), FE = end(); FI != FE; ++FI) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1017 GCFunctionInfo &MD = **FI;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1018
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1019 // A compact GC layout. Emit this data structure:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1020 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1021 // struct {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1022 // int32_t PointCount;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1023 // void *SafePointAddress[PointCount];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1024 // int32_t StackFrameSize; // in words
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1025 // int32_t StackArity;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1026 // int32_t LiveCount;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1027 // int32_t LiveOffsets[LiveCount];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1028 // } __gcmap_<FUNCTIONNAME>;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1029
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1030 // Align to address width.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1031 AP.EmitAlignment(IntPtrSize == 4 ? 2 : 3);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1032
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1033 // Emit PointCount.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1034 OS.AddComment("safe point count");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1035 AP.EmitInt32(MD.size());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1036
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1037 // And each safe point...
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1038 for (GCFunctionInfo::iterator PI = MD.begin(),
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1039 PE = MD.end(); PI != PE; ++PI) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1040 // Emit the address of the safe point.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1041 OS.AddComment("safe point address");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1042 MCSymbol *Label = PI->Label;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1043 AP.EmitLabelPlusOffset(Label/*Hi*/, 0/*Offset*/, 4/*Size*/);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1044 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1045
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1046 // Stack information never change in safe points! Only print info from the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1047 // first call-site.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1048 GCFunctionInfo::iterator PI = MD.begin();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1049
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1050 // Emit the stack frame size.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1051 OS.AddComment("stack frame size (in words)");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1052 AP.EmitInt32(MD.getFrameSize() / IntPtrSize);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1053
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1054 // Emit stack arity, i.e. the number of stacked arguments.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1055 unsigned RegisteredArgs = IntPtrSize == 4 ? 5 : 6;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1056 unsigned StackArity = MD.getFunction().arg_size() > RegisteredArgs ?
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1057 MD.getFunction().arg_size() - RegisteredArgs : 0;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1058 OS.AddComment("stack arity");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1059 AP.EmitInt32(StackArity);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1060
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1061 // Emit the number of live roots in the function.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1062 OS.AddComment("live root count");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1063 AP.EmitInt32(MD.live_size(PI));
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1064
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1065 // And for each live root...
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1066 for (GCFunctionInfo::live_iterator LI = MD.live_begin(PI),
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1067 LE = MD.live_end(PI);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1068 LI != LE; ++LI) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1069 // Emit live root's offset within the stack frame.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1070 OS.AddComment("stack index (offset / wordsize)");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1071 AP.EmitInt32(LI->StackOffset);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1072 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1073 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1074 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1075
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1076 References
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1077 ==========
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1078
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1079 .. _appel89:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1080
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1081 [Appel89] Runtime Tags Aren't Necessary. Andrew W. Appel. Lisp and Symbolic
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1082 Computation 19(7):703-705, July 1989.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1083
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1084 .. _goldberg91:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1085
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1086 [Goldberg91] Tag-free garbage collection for strongly typed programming
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1087 languages. Benjamin Goldberg. ACM SIGPLAN PLDI'91.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1088
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1089 .. _tolmach94:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1090
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1091 [Tolmach94] Tag-free garbage collection using explicit type parameters. Andrew
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1092 Tolmach. Proceedings of the 1994 ACM conference on LISP and functional
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1093 programming.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1094
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1095 .. _henderson02:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1096
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1097 [Henderson2002] `Accurate Garbage Collection in an Uncooperative Environment
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1098 <http://citeseer.ist.psu.edu/henderson02accurate.html>`__
|
