Blame - docs/GarbageCollection.html - platform/external/llvm

blob: d0b651eb64db5d533f07aa57ebc4282b6f66b91c [file] [log] [blame]

Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	1	<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
				2	"http://www.w3.org/TR/html4/strict.dtd">
				3	<html>
				4	<head>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	5	<meta http-equiv="Content-Type" Content="text/html; charset=UTF-8" >
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	6	<title>Accurate Garbage Collection with LLVM</title>
				7	<link rel="stylesheet" href="llvm.css" type="text/css">
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	8	<style type="text/css">
				9	.rowhead { text-align: left; background: inherit; }
				10	.indent { padding-left: 1em; }
				11	.optl { color: #BFBFBF; }
				12	</style>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	13	</head>
				14	<body>
				15
				16	<div class="doc_title">
				17	Accurate Garbage Collection with LLVM
				18	</div>
				19
				20	<ol>
				21	<li><a href="#introduction">Introduction</a>
				22	<ul>
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	23	<li><a href="#feature">Goals and non-goals</a></li>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	24	</ul>
				25	</li>
				26
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	27	<li><a href="#quickstart">Getting started</a>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	28	<ul>
Gordon Henriksen	562b544	2009-03-06 01:57:32 +0000	[diff] [blame]	29	<li><a href="#quickstart-compiler">In your compiler</a></li>
				30	<li><a href="#quickstart-runtime">In your runtime library</a></li>
				31	<li><a href="#shadow-stack">About the shadow stack</a></li>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	32	</ul>
				33	</li>
				34
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	35	<li><a href="#core">Core support</a>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	36	<ul>
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	37	<li><a href="#gcattr">Specifying GC code generation:
				38	<tt>gc "..."</tt></a></li>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	39	<li><a href="#gcroot">Identifying GC roots on the stack:
				40	<tt>llvm.gcroot</tt></a></li>
				41	<li><a href="#barriers">Reading and writing references in the heap</a>
				42	<ul>
				43	<li><a href="#gcwrite">Write barrier: <tt>llvm.gcwrite</tt></a></li>
				44	<li><a href="#gcread">Read barrier: <tt>llvm.gcread</tt></a></li>
				45	</ul>
				46	</li>
				47	</ul>
				48	</li>
				49
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	50	<li><a href="#plugin">Compiler plugin interface</a>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	51	<ul>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	52	<li><a href="#collector-algos">Overview of available features</a></li>
				53	<li><a href="#stack-map">Computing stack maps</a></li>
				54	<li><a href="#init-roots">Initializing roots to null:
				55	<tt>InitRoots</tt></a></li>
				56	<li><a href="#custom">Custom lowering of intrinsics: <tt>CustomRoots</tt>,
				57	<tt>CustomReadBarriers</tt>, and <tt>CustomWriteBarriers</tt></a></li>
				58	<li><a href="#safe-points">Generating safe points:
				59	<tt>NeededSafePoints</tt></a></li>
				60	<li><a href="#assembly">Emitting assembly code:
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	61	<tt>GCMetadataPrinter</tt></a></li>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	62	</ul>
				63	</li>
				64
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	65	<li><a href="#runtime-impl">Implementing a collector runtime</a>
				66	<ul>
				67	<li><a href="#gcdescriptors">Tracing GC pointers from heap
				68	objects</a></li>
				69	</ul>
				70	</li>
				71
				72	<li><a href="#references">References</a></li>
				73
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	74	</ol>
				75
				76	<div class="doc_author">
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	77	<p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a> and
				78	Gordon Henriksen</p>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	79	</div>
				80
				81	<!-- *********************************************************************** -->
				82	<div class="doc_section">
				83	<a name="introduction">Introduction</a>
				84	</div>
				85	<!-- *********************************************************************** -->
				86
				87	<div class="doc_text">
				88
				89	<p>Garbage collection is a widely used technique that frees the programmer from
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	90	having to know the lifetimes of heap objects, making software easier to produce
				91	and maintain. Many programming languages rely on garbage collection for
				92	automatic memory management. There are two primary forms of garbage collection:
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	93	conservative and accurate.</p>
				94
				95	<p>Conservative garbage collection often does not require any special support
				96	from either the language or the compiler: it can handle non-type-safe
				97	programming languages (such as C/C++) and does not require any special
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	98	information from the compiler. The
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	99	<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/">Boehm collector</a> is
				100	an example of a state-of-the-art conservative collector.</p>
				101
				102	<p>Accurate garbage collection requires the ability to identify all pointers in
				103	the program at run-time (which requires that the source-language be type-safe in
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	104	most cases). Identifying pointers at run-time requires compiler support to
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	105	locate all places that hold live pointer variables at run-time, including the
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	106	<a href="#gcroot">processor stack and registers</a>.</p>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	107
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	108	<p>Conservative garbage collection is attractive because it does not require any
				109	special compiler support, but it does have problems. In particular, because the
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	110	conservative garbage collector cannot <i>know</i> that a particular word in the
				111	machine is a pointer, it cannot move live objects in the heap (preventing the
				112	use of compacting and generational GC algorithms) and it can occasionally suffer
				113	from memory leaks due to integer values that happen to point to objects in the
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	114	program. In addition, some aggressive compiler transformations can break
				115	conservative garbage collectors (though these seem rare in practice).</p>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	116
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	117	<p>Accurate garbage collectors do not suffer from any of these problems, but
				118	they can suffer from degraded scalar optimization of the program. In particular,
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	119	because the runtime must be able to identify and update all pointers active in
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	120	the program, some optimizations are less effective. In practice, however, the
Chris Lattner	c47015e	2009-05-13 18:02:09 +0000	[diff] [blame]	121	locality and performance benefits of using aggressive garbage collection
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	122	techniques dominates any low-level losses.</p>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	123
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	124	<p>This document describes the mechanisms and interfaces provided by LLVM to
				125	support accurate garbage collection.</p>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	126
				127	</div>
				128
				129	<!-- ======================================================================= -->
				130	<div class="doc_subsection">
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	131	<a name="feature">Goals and non-goals</a>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	132	</div>
				133
				134	<div class="doc_text">
				135
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	136	<p>LLVM's intermediate representation provides <a href="#intrinsics">garbage
Chris Lattner	a7d94ba	2008-04-24 05:59:56 +0000	[diff] [blame]	137	collection intrinsics</a> that offer support for a broad class of
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	138	collector models. For instance, the intrinsics permit:</p>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	139
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	140	<ul>
				141	<li>semi-space collectors</li>
				142	<li>mark-sweep collectors</li>
				143	<li>generational collectors</li>
				144	<li>reference counting</li>
				145	<li>incremental collectors</li>
				146	<li>concurrent collectors</li>
				147	<li>cooperative collectors</li>
				148	</ul>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	149
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	150	<p>We hope that the primitive support built into the LLVM IR is sufficient to
				151	support a broad class of garbage collected languages including Scheme, ML, Java,
				152	C#, Perl, Python, Lua, Ruby, other scripting languages, and more.</p>
				153
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	154	<p>However, LLVM does not itself provide a garbage collectorthis should
				155	be part of your language's runtime library. LLVM provides a framework for
				156	compile time <a href="#plugin">code generation plugins</a>. The role of these
				157	plugins is to generate code and data structures which conforms to the <em>binary
				158	interface</em> specified by the <em>runtime library</em>. This is similar to the
				159	relationship between LLVM and DWARF debugging info, for example. The
				160	difference primarily lies in the lack of an established standard in the domain
				161	of garbage collectionthus the plugins.</p>
				162
				163	<p>The aspects of the binary interface with which LLVM's GC support is
				164	concerned are:</p>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	165
				166	<ul>
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	167	<li>Creation of GC-safe points within code where collection is allowed to
				168	execute safely.</li>
Gordon Henriksen	562b544	2009-03-06 01:57:32 +0000	[diff] [blame]	169	<li>Computation of the stack map. For each safe point in the code, object
				170	references within the stack frame must be identified so that the
				171	collector may traverse and perhaps update them.</li>
				172	<li>Write barriers when storing object references to the heap. These are
				173	commonly used to optimize incremental scans in generational
				174	collectors.</li>
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	175	<li>Emission of read barriers when loading object references. These are
				176	useful for interoperating with concurrent collectors.</li>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	177	</ul>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	178
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	179	<p>There are additional areas that LLVM does not directly address:</p>
				180
				181	<ul>
Gordon Henriksen	562b544	2009-03-06 01:57:32 +0000	[diff] [blame]	182	<li>Registration of global roots with the runtime.</li>
				183	<li>Registration of stack map entries with the runtime.</li>
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	184	<li>The functions used by the program to allocate memory, trigger a
				185	collection, etc.</li>
Gordon Henriksen	562b544	2009-03-06 01:57:32 +0000	[diff] [blame]	186	<li>Computation or compilation of type maps, or registration of them with
				187	the runtime. These are used to crawl the heap for object
				188	references.</li>
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	189	</ul>
				190
				191	<p>In general, LLVM's support for GC does not include features which can be
				192	adequately addressed with other features of the IR and does not specify a
				193	particular binary interface. On the plus side, this means that you should be
				194	able to integrate LLVM with an existing runtime. On the other hand, it leaves
				195	a lot of work for the developer of a novel language. However, it's easy to get
				196	started quickly and scale up to a more sophisticated implementation as your
				197	compiler matures.</p>
				198
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	199	</div>
				200
				201	<!-- *********************************************************************** -->
				202	<div class="doc_section">
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	203	<a name="quickstart">Getting started</a>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	204	</div>
				205	<!-- *********************************************************************** -->
				206
				207	<div class="doc_text">
				208
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	209	<p>Using a GC with LLVM implies many things, for example:</p>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	210
				211	<ul>
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	212	<li>Write a runtime library or find an existing one which implements a GC
				213	heap.<ol>
				214	<li>Implement a memory allocator.</li>
Gordon Henriksen	562b544	2009-03-06 01:57:32 +0000	[diff] [blame]	215	<li>Design a binary interface for the stack map, used to identify
				216	references within a stack frame on the machine stack.*</li>
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	217	<li>Implement a stack crawler to discover functions on the call stack.*</li>
				218	<li>Implement a registry for global roots.</li>
Gordon Henriksen	562b544	2009-03-06 01:57:32 +0000	[diff] [blame]	219	<li>Design a binary interface for type maps, used to identify references
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	220	within heap objects.</li>
				221	<li>Implement a collection routine bringing together all of the above.</li>
				222	</ol></li>
				223	<li>Emit compatible code from your compiler.<ul>
				224	<li>Initialization in the main function.</li>
				225	<li>Use the <tt>gc "..."</tt> attribute to enable GC code generation
				226	(or <tt>F.setGC("...")</tt>).</li>
				227	<li>Use <tt>@llvm.gcroot</tt> to mark stack roots.</li>
				228	<li>Use <tt>@llvm.gcread</tt> and/or <tt>@llvm.gcwrite</tt> to
				229	manipulate GC references, if necessary.</li>
				230	<li>Allocate memory using the GC allocation routine provided by the
				231	runtime library.</li>
Gordon Henriksen	562b544	2009-03-06 01:57:32 +0000	[diff] [blame]	232	<li>Generate type maps according to your runtime's binary interface.</li>
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	233	</ul></li>
				234	<li>Write a compiler plugin to interface LLVM with the runtime library.*<ul>
				235	<li>Lower <tt>@llvm.gcread</tt> and <tt>@llvm.gcwrite</tt> to appropriate
				236	code sequences.*</li>
Gordon Henriksen	562b544	2009-03-06 01:57:32 +0000	[diff] [blame]	237	<li>Compile LLVM's stack map to the binary form expected by the
				238	runtime.</li>
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	239	</ul></li>
				240	<li>Load the plugin into the compiler. Use <tt>llc -load</tt> or link the
				241	plugin statically with your language's compiler.*</li>
				242	<li>Link program executables with the runtime.</li>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	243	</ul>
				244
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	245	<p>To help with several of these tasks (those indicated with a *), LLVM
				246	includes a highly portable, built-in ShadowStack code generator. It is compiled
				247	into <tt>llc</tt> and works even with the interpreter and C backends.</p>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	248
				249	</div>
				250
				251	<!-- ======================================================================= -->
				252	<div class="doc_subsection">
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	253	<a name="quickstart-compiler">In your compiler</a>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	254	</div>
				255
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	256	<div class="doc_text">
				257
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	258	<p>To turn the shadow stack on for your functions, first call:</p>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	259
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	260	<div class="doc_code"><pre
				261	>F.setGC("shadow-stack");</pre></div>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	262
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	263	<p>for each function your compiler emits. Since the shadow stack is built into
				264	LLVM, you do not need to load a plugin.</p>
				265
				266	<p>Your compiler must also use <tt>@llvm.gcroot</tt> as documented.
				267	Don't forget to create a root for each intermediate value that is generated
				268	when evaluating an expression. In <tt>h(f(), g())</tt>, the result of
				269	<tt>f()</tt> could easily be collected if evaluating <tt>g()</tt> triggers a
				270	collection.</p>
				271
				272	<p>There's no need to use <tt>@llvm.gcread</tt> and <tt>@llvm.gcwrite</tt> over
				273	plain <tt>load</tt> and <tt>store</tt> for now. You will need them when
				274	switching to a more advanced GC.</p>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	275
				276	</div>
				277
				278	<!-- ======================================================================= -->
				279	<div class="doc_subsection">
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	280	<a name="quickstart-runtime">In your runtime</a>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	281	</div>
				282
				283	<div class="doc_text">
				284
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	285	<p>The shadow stack doesn't imply a memory allocation algorithm. A semispace
				286	collector or building atop <tt>malloc</tt> are great places to start, and can
				287	be implemented with very little code.</p>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	288
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	289	<p>When it comes time to collect, however, your runtime needs to traverse the
				290	stack roots, and for this it needs to integrate with the shadow stack. Luckily,
				291	doing so is very simple. (This code is heavily commented to help you
				292	understand the data structure, but there are only 20 lines of meaningful
				293	code.)</p>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	294
				295	</div>
				296
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	297	<div class="doc_code"><pre
Gordon Henriksen	562b544	2009-03-06 01:57:32 +0000	[diff] [blame]	298	>/// @brief The map for a single function's stack frame. One of these is
				299	/// compiled as constant data into the executable for each function.
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	300	///
Gordon Henriksen	562b544	2009-03-06 01:57:32 +0000	[diff] [blame]	301	/// Storage of metadata values is elided if the %metadata parameter to
				302	/// @llvm.gcroot is null.
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	303	struct FrameMap {
				304	int32_t NumRoots; //< Number of roots in stack frame.
Gordon Henriksen	562b544	2009-03-06 01:57:32 +0000	[diff] [blame]	305	int32_t NumMeta; //< Number of metadata entries. May be < NumRoots.
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	306	const void *Meta[0]; //< Metadata for each root.
				307	};
				308
				309	/// @brief A link in the dynamic shadow stack. One of these is embedded in the
				310	/// stack frame of each function on the call stack.
				311	struct StackEntry {
				312	StackEntry *Next; //< Link to next stack entry (the caller's).
				313	const FrameMap *Map; //< Pointer to constant FrameMap.
				314	void *Roots[0]; //< Stack roots (in-place array).
				315	};
				316
				317	/// @brief The head of the singly-linked list of StackEntries. Functions push
				318	/// and pop onto this in their prologue and epilogue.
				319	///
				320	/// Since there is only a global list, this technique is not threadsafe.
				321	StackEntry *llvm_gc_root_chain;
				322
				323	/// @brief Calls Visitor(root, meta) for each GC root on the stack.
				324	/// root and meta are exactly the values passed to
				325	/// <tt>@llvm.gcroot</tt>.
				326	///
				327	/// Visitor could be a function to recursively mark live objects. Or it
				328	/// might copy them to another heap or generation.
				329	///
				330	/// @param Visitor A function to invoke for every GC root on the stack.
				331	void visitGCRoots(void (Visitor)(void Root, const void Meta)) {
				332	for (StackEntry *R = llvm_gc_root_chain; R; R = R->Next) {
				333	unsigned i = 0;
				334
				335	// For roots [0, NumMeta), the metadata pointer is in the FrameMap.
				336	for (unsigned e = R->Map->NumMeta; i != e; ++i)
Benjamin Kramer	7b2136d	2009-08-05 15:42:44 +0000	[diff] [blame]	337	Visitor(&R->Roots[i], R->Map->Meta[i]);
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	338
				339	// For roots [NumMeta, NumRoots), the metadata pointer is null.
				340	for (unsigned e = R->Map->NumRoots; i != e; ++i)
Benjamin Kramer	7b2136d	2009-08-05 15:42:44 +0000	[diff] [blame]	341	Visitor(&R->Roots[i], NULL);
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	342	}
				343	}</pre></div>
				344
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	345	<!-- ======================================================================= -->
				346	<div class="doc_subsection">
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	347	<a name="shadow-stack">About the shadow stack</a>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	348	</div>
				349
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	350	<div class="doc_text">
				351
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	352	<p>Unlike many GC algorithms which rely on a cooperative code generator to
Gordon Henriksen	562b544	2009-03-06 01:57:32 +0000	[diff] [blame]	353	compile stack maps, this algorithm carefully maintains a linked list of stack
				354	roots [<a href="#henderson02">Henderson2002</a>]. This so-called "shadow stack"
				355	mirrors the machine stack. Maintaining this data structure is slower than using
				356	a stack map compiled into the executable as constant data, but has a significant
				357	portability advantage because it requires no special support from the target
				358	code generator, and does not require tricky platform-specific code to crawl
				359	the machine stack.</p>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	360
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	361	<p>The tradeoff for this simplicity and portability is:</p>
				362
				363	<ul>
				364	<li>High overhead per function call.</li>
				365	<li>Not thread-safe.</li>
				366	</ul>
				367
Gordon Henriksen	562b544	2009-03-06 01:57:32 +0000	[diff] [blame]	368	<p>Still, it's an easy way to get started. After your compiler and runtime are
				369	up and running, writing a <a href="#plugin">plugin</a> will allow you to take
				370	advantage of <a href="#collector-algos">more advanced GC features</a> of LLVM
				371	in order to improve performance.</p>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	372
				373	</div>
				374
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	375	<!-- *********************************************************************** -->
				376	<div class="doc_section">
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	377	<a name="core">IR features</a><a name="intrinsics"></a>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	378	</div>
				379	<!-- *********************************************************************** -->
				380
				381	<div class="doc_text">
				382
				383	<p>This section describes the garbage collection facilities provided by the
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	384	<a href="LangRef.html">LLVM intermediate representation</a>. The exact behavior
				385	of these IR features is specified by the binary interface implemented by a
				386	<a href="#plugin">code generation plugin</a>, not by this document.</p>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	387
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	388	<p>These facilities are limited to those strictly necessary; they are not
				389	intended to be a complete interface to any garbage collector. A program will
				390	need to interface with the GC library using the facilities provided by that
				391	program.</p>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	392
				393	</div>
				394
				395	<!-- ======================================================================= -->
				396	<div class="doc_subsection">
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	397	<a name="gcattr">Specifying GC code generation: <tt>gc "..."</tt></a>
				398	</div>
				399
				400	<div class="doc_code"><tt>
Benjamin Kramer	7b2136d	2009-08-05 15:42:44 +0000	[diff] [blame]	401	define <i>ty</i> @<i>name</i>(...) <span style="text-decoration: underline">gc "<i>name</i>"</span> { ...
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	402	</tt></div>
				403
				404	<div class="doc_text">
				405
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	406	<p>The <tt>gc</tt> function attribute is used to specify the desired GC style
				407	to the compiler. Its programmatic equivalent is the <tt>setGC</tt> method of
				408	<tt>Function</tt>.</p>
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	409
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	410	<p>Setting <tt>gc "<i>name</i>"</tt> on a function triggers a search for a
				411	matching code generation plugin "<i>name</i>"; it is that plugin which defines
				412	the exact nature of the code generated to support GC. If none is found, the
				413	compiler will raise an error.</p>
				414
				415	<p>Specifying the GC style on a per-function basis allows LLVM to link together
				416	programs that use different garbage collection algorithms (or none at all).</p>
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	417
				418	</div>
				419
				420	<!-- ======================================================================= -->
				421	<div class="doc_subsection">
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	422	<a name="gcroot">Identifying GC roots on the stack: <tt>llvm.gcroot</tt></a>
				423	</div>
				424
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	425	<div class="doc_code"><tt>
Chris Lattner	94dab0f	2008-04-24 06:00:30 +0000	[diff] [blame]	426	void @llvm.gcroot(i8** %ptrloc, i8* %metadata)
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	427	</tt></div>
				428
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	429	<div class="doc_text">
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	430
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	431	<p>The <tt>llvm.gcroot</tt> intrinsic is used to inform LLVM that a stack
				432	variable references an object on the heap and is to be tracked for garbage
				433	collection. The exact impact on generated code is specified by a <a
				434	href="#plugin">compiler plugin</a>.</p>
				435
				436	<p>A compiler which uses mem2reg to raise imperative code using <tt>alloca</tt>
				437	into SSA form need only add a call to <tt>@llvm.gcroot</tt> for those variables
				438	which a pointers into the GC heap.</p>
				439
				440	<p>It is also important to mark intermediate values with <tt>llvm.gcroot</tt>.
				441	For example, consider <tt>h(f(), g())</tt>. Beware leaking the result of
				442	<tt>f()</tt> in the case that <tt>g()</tt> triggers a collection.</p>
				443
				444	<p>The first argument <b>must</b> be a value referring to an alloca instruction
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	445	or a bitcast of an alloca. The second contains a pointer to metadata that
				446	should be associated with the pointer, and <b>must</b> be a constant or global
				447	value address. If your target collector uses tags, use a null pointer for
				448	metadata.</p>
				449
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	450	<p>The <tt>%metadata</tt> argument can be used to avoid requiring heap objects
				451	to have 'isa' pointers or tag bits. [<a href="#appel89">Appel89</a>, <a
				452	href="#goldberg91">Goldberg91</a>, <a href="#tolmach94">Tolmach94</a>] If
				453	specified, its value will be tracked along with the location of the pointer in
				454	the stack frame.</p>
				455
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	456	<p>Consider the following fragment of Java code:</p>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	457
				458	<pre>
				459	{
				460	Object X; // A null-initialized reference to an object
				461	...
				462	}
				463	</pre>
				464
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	465	<p>This block (which may be located in the middle of a function or in a loop
				466	nest), could be compiled to this LLVM code:</p>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	467
				468	<pre>
				469	Entry:
				470	;; In the entry block for the function, allocate the
				471	;; stack space for X, which is an LLVM pointer.
				472	%X = alloca %Object*
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	473
				474	;; Tell LLVM that the stack space is a stack root.
				475	;; Java has type-tags on objects, so we pass null as metadata.
				476	%tmp = bitcast %Object %X to i8
Chris Lattner	94dab0f	2008-04-24 06:00:30 +0000	[diff] [blame]	477	call void @llvm.gcroot(i8** %X, i8* null)
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	478	...
				479
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	480	;; "CodeBlock" is the block corresponding to the start
				481	;; of the scope above.
				482	CodeBlock:
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	483	;; Java null-initializes pointers.
				484	store %Object* null, %Object** %X
				485
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	486	...
				487
				488	;; As the pointer goes out of scope, store a null value into
				489	;; it, to indicate that the value is no longer live.
				490	store %Object* null, %Object** %X
				491	...
				492	</pre>
				493
				494	</div>
				495
				496	<!-- ======================================================================= -->
				497	<div class="doc_subsection">
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	498	<a name="barriers">Reading and writing references in the heap</a>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	499	</div>
				500
				501	<div class="doc_text">
				502
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	503	<p>Some collectors need to be informed when the mutator (the program that needs
				504	garbage collection) either reads a pointer from or writes a pointer to a field
				505	of a heap object. The code fragments inserted at these points are called
				506	<em>read barriers</em> and <em>write barriers</em>, respectively. The amount of
				507	code that needs to be executed is usually quite small and not on the critical
				508	path of any computation, so the overall performance impact of the barrier is
				509	tolerable.</p>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	510
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	511	<p>Barriers often require access to the <em>object pointer</em> rather than the
				512	<em>derived pointer</em> (which is a pointer to the field within the
				513	object). Accordingly, these intrinsics take both pointers as separate arguments
				514	for completeness. In this snippet, <tt>%object</tt> is the object pointer, and
				515	<tt>%derived</tt> is the derived pointer:</p>
				516
Chris Lattner	a7d94ba	2008-04-24 05:59:56 +0000	[diff] [blame]	517	<blockquote><pre>
				518	;; An array type.
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	519	%class.Array = type { %class.Object, i32, [0 x %class.Object*] }
Chris Lattner	a7d94ba	2008-04-24 05:59:56 +0000	[diff] [blame]	520	...
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	521
				522	;; Load the object pointer from a gcroot.
				523	%object = load %class.Array** %object_addr
				524
				525	;; Compute the derived pointer.
Chris Lattner	a7d94ba	2008-04-24 05:59:56 +0000	[diff] [blame]	526	%derived = getelementptr %object, i32 0, i32 2, i32 %n</pre></blockquote>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	527
Gordon Henriksen	183f6fc	2009-03-06 02:42:47 +0000	[diff] [blame]	528	<p>LLVM does not enforce this relationship between the object and derived
				529	pointer (although a <a href="#plugin">plugin</a> might). However, it would be
				530	an unusual collector that violated it.</p>
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	531
Gordon Henriksen	183f6fc	2009-03-06 02:42:47 +0000	[diff] [blame]	532	<p>The use of these intrinsics is naturally optional if the target GC does
				533	require the corresponding barrier. Such a GC plugin will replace the intrinsic
				534	calls with the corresponding <tt>load</tt> or <tt>store</tt> instruction if they
				535	are used.</p>
Gordon Henriksen	562b544	2009-03-06 01:57:32 +0000	[diff] [blame]	536
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	537	</div>
				538
				539	<!-- ======================================================================= -->
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	540	<div class="doc_subsubsection">
				541	<a name="gcwrite">Write barrier: <tt>llvm.gcwrite</tt></a>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	542	</div>
				543
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	544	<div class="doc_code"><tt>
				545	void @llvm.gcwrite(i8* %value, i8* %object, i8** %derived)
				546	</tt></div>
				547
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	548	<div class="doc_text">
				549
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	550	<p>For write barriers, LLVM provides the <tt>llvm.gcwrite</tt> intrinsic
				551	function. It has exactly the same semantics as a non-volatile <tt>store</tt> to
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	552	the derived pointer (the third argument). The exact code generated is specified
				553	by a <a href="#plugin">compiler plugin</a>.</p>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	554
				555	<p>Many important algorithms require write barriers, including generational
				556	and concurrent collectors. Additionally, write barriers could be used to
				557	implement reference counting.</p>
				558
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	559	</div>
				560
				561	<!-- ======================================================================= -->
				562	<div class="doc_subsubsection">
				563	<a name="gcread">Read barrier: <tt>llvm.gcread</tt></a>
				564	</div>
				565
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	566	<div class="doc_code"><tt>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	567	i8* @llvm.gcread(i8* %object, i8** %derived)<br>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	568	</tt></div>
				569
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	570	<div class="doc_text">
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	571
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	572	<p>For read barriers, LLVM provides the <tt>llvm.gcread</tt> intrinsic function.
				573	It has exactly the same semantics as a non-volatile <tt>load</tt> from the
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	574	derived pointer (the second argument). The exact code generated is specified by
				575	a <a href="#plugin">compiler plugin</a>.</p>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	576
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	577	<p>Read barriers are needed by fewer algorithms than write barriers, and may
				578	have a greater performance impact since pointer reads are more frequent than
				579	writes.</p>
				580
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	581	</div>
				582
				583	<!-- *********************************************************************** -->
				584	<div class="doc_section">
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	585	<a name="plugin">Implementing a collector plugin</a>
				586	</div>
				587	<!-- *********************************************************************** -->
				588
				589	<div class="doc_text">
				590
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	591	<p>User code specifies which GC code generation to use with the <tt>gc</tt>
				592	function attribute or, equivalently, with the <tt>setGC</tt> method of
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	593	<tt>Function</tt>.</p>
				594
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	595	<p>To implement a GC plugin, it is necessary to subclass
				596	<tt>llvm::GCStrategy</tt>, which can be accomplished in a few lines of
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	597	boilerplate code. LLVM's infrastructure provides access to several important
Gordon Henriksen	562b544	2009-03-06 01:57:32 +0000	[diff] [blame]	598	algorithms. For an uncontroversial collector, all that remains may be to
				599	compile LLVM's computed stack map to assembly code (using the binary
				600	representation expected by the runtime library). This can be accomplished in
				601	about 100 lines of code.</p>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	602
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	603	<p>This is not the appropriate place to implement a garbage collected heap or a
				604	garbage collector itself. That code should exist in the language's runtime
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	605	library. The compiler plugin is responsible for generating code which
				606	conforms to the binary interface defined by library, most essentially the
Gordon Henriksen	562b544	2009-03-06 01:57:32 +0000	[diff] [blame]	607	<a href="#stack-map">stack map</a>.</p>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	608
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	609	<p>To subclass <tt>llvm::GCStrategy</tt> and register it with the compiler:</p>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	610
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	611	<blockquote><pre>// lib/MyGC/MyGC.cpp - Example LLVM GC plugin
				612
				613	#include "llvm/CodeGen/GCStrategy.h"
				614	#include "llvm/CodeGen/GCMetadata.h"
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	615	#include "llvm/Support/Compiler.h"
				616
				617	using namespace llvm;
				618
				619	namespace {
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	620	class VISIBILITY_HIDDEN MyGC : public GCStrategy {
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	621	public:
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	622	MyGC() {}
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	623	};
				624
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	625	GCRegistry::Add<MyGC>
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	626	X("mygc", "My bespoke garbage collector.");
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	627	}</pre></blockquote>
				628
Gordon Henriksen	562b544	2009-03-06 01:57:32 +0000	[diff] [blame]	629	<p>This boilerplate collector does nothing. More specifically:</p>
				630
				631	<ul>
				632	<li><tt>llvm.gcread</tt> calls are replaced with the corresponding
				633	<tt>load</tt> instruction.</li>
				634	<li><tt>llvm.gcwrite</tt> calls are replaced with the corresponding
				635	<tt>store</tt> instruction.</li>
				636	<li>No safe points are added to the code.</li>
				637	<li>The stack map is not compiled into the executable.</li>
				638	</ul>
				639
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	640	<p>Using the LLVM makefiles (like the <a
				641	href="http://llvm.org/viewvc/llvm-project/llvm/trunk/projects/sample/">sample
Gordon Henriksen	562b544	2009-03-06 01:57:32 +0000	[diff] [blame]	642	project</a>), this code can be compiled as a plugin using a simple
				643	makefile:</p>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	644
				645	<blockquote><pre
				646	># lib/MyGC/Makefile
				647
				648	LEVEL := ../..
				649	LIBRARYNAME = <var>MyGC</var>
				650	LOADABLE_MODULE = 1
				651
				652	include $(LEVEL)/Makefile.common</pre></blockquote>
				653
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	654	<p>Once the plugin is compiled, code using it may be compiled using <tt>llc
				655	-load=<var>MyGC.so</var></tt> (though <var>MyGC.so</var> may have some other
				656	platform-specific extension):</p>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	657
				658	<blockquote><pre
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	659	>$ cat sample.ll
				660	define void @f() gc "mygc" {
				661	entry:
				662	ret void
				663	}
				664	$ llvm-as < sample.ll \| llc -load=MyGC.so</pre></blockquote>
				665
				666	<p>It is also possible to statically link the collector plugin into tools, such
				667	as a language-specific compiler front-end.</p>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	668
				669	</div>
				670
				671	<!-- ======================================================================= -->
				672	<div class="doc_subsection">
				673	<a name="collector-algos">Overview of available features</a>
				674	</div>
				675
				676	<div class="doc_text">
				677
Gordon Henriksen	562b544	2009-03-06 01:57:32 +0000	[diff] [blame]	678	<p><tt>GCStrategy</tt> provides a range of features through which a plugin
				679	may do useful work. Some of these are callbacks, some are algorithms that can
				680	be enabled, disabled, or customized. This matrix summarizes the supported (and
				681	planned) features and correlates them with the collection techniques which
				682	typically require them.</p>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	683
				684	<table>
				685	<tr>
				686	<th>Algorithm</th>
				687	<th>Done</th>
				688	<th>shadow stack</th>
				689	<th>refcount</th>
				690	<th>mark-sweep</th>
				691	<th>copying</th>
				692	<th>incremental</th>
				693	<th>threaded</th>
				694	<th>concurrent</th>
				695	</tr>
				696	<tr>
				697	<th class="rowhead"><a href="#stack-map">stack map</a></th>
				698	<td>✔</td>
				699	<td></td>
				700	<td></td>
				701	<td>✘</td>
				702	<td>✘</td>
				703	<td>✘</td>
				704	<td>✘</td>
				705	<td>✘</td>
				706	</tr>
				707	<tr>
				708	<th class="rowhead"><a href="#init-roots">initialize roots</a></th>
				709	<td>✔</td>
				710	<td>✘</td>
				711	<td>✘</td>
				712	<td>✘</td>
				713	<td>✘</td>
				714	<td>✘</td>
				715	<td>✘</td>
				716	<td>✘</td>
				717	</tr>
				718	<tr class="doc_warning">
				719	<th class="rowhead">derived pointers</th>
				720	<td>NO</td>
				721	<td></td>
				722	<td></td>
				723	<td></td>
				724	<td></td>
				725	<td></td>
				726	<td>✘*</td>
				727	<td>✘*</td>
				728	</tr>
				729	<tr>
				730	<th class="rowhead"><em><a href="#custom">custom lowering</a></em></th>
				731	<td>✔</td>
				732	<th></th>
				733	<th></th>
				734	<th></th>
				735	<th></th>
				736	<th></th>
				737	<th></th>
				738	<th></th>
				739	</tr>
				740	<tr>
				741	<th class="rowhead indent">gcroot</th>
				742	<td>✔</td>
				743	<td>✘</td>
				744	<td>✘</td>
				745	<td></td>
				746	<td></td>
				747	<td></td>
				748	<td></td>
				749	<td></td>
				750	</tr>
				751	<tr>
				752	<th class="rowhead indent">gcwrite</th>
				753	<td>✔</td>
				754	<td></td>
				755	<td>✘</td>
				756	<td></td>
				757	<td></td>
				758	<td>✘</td>
				759	<td></td>
				760	<td>✘</td>
				761	</tr>
				762	<tr>
				763	<th class="rowhead indent">gcread</th>
				764	<td>✔</td>
				765	<td></td>
				766	<td></td>
				767	<td></td>
				768	<td></td>
				769	<td></td>
				770	<td></td>
				771	<td>✘</td>
				772	</tr>
				773	<tr>
				774	<th class="rowhead"><em><a href="#safe-points">safe points</a></em></th>
				775	<td></td>
				776	<th></th>
				777	<th></th>
				778	<th></th>
				779	<th></th>
				780	<th></th>
				781	<th></th>
				782	<th></th>
				783	</tr>
				784	<tr>
				785	<th class="rowhead indent">in calls</th>
				786	<td>✔</td>
				787	<td></td>
				788	<td></td>
				789	<td>✘</td>
				790	<td>✘</td>
				791	<td>✘</td>
				792	<td>✘</td>
				793	<td>✘</td>
				794	</tr>
				795	<tr>
				796	<th class="rowhead indent">before calls</th>
				797	<td>✔</td>
				798	<td></td>
				799	<td></td>
				800	<td></td>
				801	<td></td>
				802	<td></td>
				803	<td>✘</td>
				804	<td>✘</td>
				805	</tr>
				806	<tr class="doc_warning">
				807	<th class="rowhead indent">for loops</th>
				808	<td>NO</td>
				809	<td></td>
				810	<td></td>
				811	<td></td>
				812	<td></td>
				813	<td></td>
				814	<td>✘</td>
				815	<td>✘</td>
				816	</tr>
				817	<tr>
				818	<th class="rowhead indent">before escape</th>
				819	<td>✔</td>
				820	<td></td>
				821	<td></td>
				822	<td></td>
				823	<td></td>
				824	<td></td>
				825	<td>✘</td>
				826	<td>✘</td>
				827	</tr>
				828	<tr class="doc_warning">
				829	<th class="rowhead">emit code at safe points</th>
				830	<td>NO</td>
				831	<td></td>
				832	<td></td>
				833	<td></td>
				834	<td></td>
				835	<td></td>
				836	<td>✘</td>
				837	<td>✘</td>
				838	</tr>
				839	<tr>
				840	<th class="rowhead"><em>output</em></th>
				841	<td></td>
				842	<th></th>
				843	<th></th>
				844	<th></th>
				845	<th></th>
				846	<th></th>
				847	<th></th>
				848	<th></th>
				849	</tr>
				850	<tr>
				851	<th class="rowhead indent"><a href="#assembly">assembly</a></th>
				852	<td>✔</td>
				853	<td></td>
				854	<td></td>
				855	<td>✘</td>
				856	<td>✘</td>
				857	<td>✘</td>
				858	<td>✘</td>
				859	<td>✘</td>
				860	</tr>
				861	<tr class="doc_warning">
				862	<th class="rowhead indent">JIT</th>
				863	<td>NO</td>
				864	<td></td>
				865	<td></td>
				866	<td class="optl">✘</td>
				867	<td class="optl">✘</td>
				868	<td class="optl">✘</td>
				869	<td class="optl">✘</td>
				870	<td class="optl">✘</td>
				871	</tr>
				872	<tr class="doc_warning">
				873	<th class="rowhead indent">obj</th>
				874	<td>NO</td>
				875	<td></td>
				876	<td></td>
				877	<td class="optl">✘</td>
				878	<td class="optl">✘</td>
				879	<td class="optl">✘</td>
				880	<td class="optl">✘</td>
				881	<td class="optl">✘</td>
				882	</tr>
				883	<tr class="doc_warning">
				884	<th class="rowhead">live analysis</th>
				885	<td>NO</td>
				886	<td></td>
				887	<td></td>
				888	<td class="optl">✘</td>
				889	<td class="optl">✘</td>
				890	<td class="optl">✘</td>
				891	<td class="optl">✘</td>
				892	<td class="optl">✘</td>
				893	</tr>
				894	<tr class="doc_warning">
				895	<th class="rowhead">register map</th>
				896	<td>NO</td>
				897	<td></td>
				898	<td></td>
				899	<td class="optl">✘</td>
				900	<td class="optl">✘</td>
				901	<td class="optl">✘</td>
				902	<td class="optl">✘</td>
				903	<td class="optl">✘</td>
				904	</tr>
				905	<tr>
				906	<td colspan="10">
				907	<div><span class="doc_warning">*</span> Derived pointers only pose a
				908	hazard to copying collectors.</div>
				909	<div><span class="optl">✘</span> in gray denotes a feature which
				910	could be utilized if available.</div>
				911	</td>
				912	</tr>
				913	</table>
				914
				915	<p>To be clear, the collection techniques above are defined as:</p>
				916
				917	<dl>
				918	<dt>Shadow Stack</dt>
Gordon Henriksen	562b544	2009-03-06 01:57:32 +0000	[diff] [blame]	919	<dd>The mutator carefully maintains a linked list of stack roots.</dd>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	920	<dt>Reference Counting</dt>
				921	<dd>The mutator maintains a reference count for each object and frees an
				922	object when its count falls to zero.</dd>
				923	<dt>Mark-Sweep</dt>
				924	<dd>When the heap is exhausted, the collector marks reachable objects starting
				925	from the roots, then deallocates unreachable objects in a sweep
				926	phase.</dd>
				927	<dt>Copying</dt>
				928	<dd>As reachability analysis proceeds, the collector copies objects from one
				929	heap area to another, compacting them in the process. Copying collectors
				930	enable highly efficient "bump pointer" allocation and can improve locality
				931	of reference.</dd>
				932	<dt>Incremental</dt>
				933	<dd>(Including generational collectors.) Incremental collectors generally have
				934	all the properties of a copying collector (regardless of whether the
				935	mature heap is compacting), but bring the added complexity of requiring
				936	write barriers.</dd>
				937	<dt>Threaded</dt>
				938	<dd>Denotes a multithreaded mutator; the collector must still stop the mutator
				939	("stop the world") before beginning reachability analysis. Stopping a
				940	multithreaded mutator is a complicated problem. It generally requires
				941	highly platform specific code in the runtime, and the production of
				942	carefully designed machine code at safe points.</dd>
				943	<dt>Concurrent</dt>
				944	<dd>In this technique, the mutator and the collector run concurrently, with
				945	the goal of eliminating pause times. In a <em>cooperative</em> collector,
				946	the mutator further aids with collection should a pause occur, allowing
				947	collection to take advantage of multiprocessor hosts. The "stop the world"
				948	problem of threaded collectors is generally still present to a limited
				949	extent. Sophisticated marking algorithms are necessary. Read barriers may
				950	be necessary.</dd>
				951	</dl>
				952
				953	<p>As the matrix indicates, LLVM's garbage collection infrastructure is already
				954	suitable for a wide variety of collectors, but does not currently extend to
				955	multithreaded programs. This will be added in the future as there is
				956	interest.</p>
				957
				958	</div>
				959
				960	<!-- ======================================================================= -->
				961	<div class="doc_subsection">
				962	<a name="stack-map">Computing stack maps</a>
				963	</div>
				964
				965	<div class="doc_text">
				966
Gordon Henriksen	562b544	2009-03-06 01:57:32 +0000	[diff] [blame]	967	<p>LLVM automatically computes a stack map. One of the most important features
				968	of a <tt>GCStrategy</tt> is to compile this information into the executable in
				969	the binary representation expected by the runtime library.</p>
				970
				971	<p>The stack map consists of the location and identity of each GC root in the
				972	each function in the module. For each root:</p>
				973
				974	<ul>
				975	<li><tt>RootNum</tt>: The index of the root.</li>
				976	<li><tt>StackOffset</tt>: The offset of the object relative to the frame
				977	pointer.</li>
				978	<li><tt>RootMetadata</tt>: The value passed as the <tt>%metadata</tt>
				979	parameter to the <a href="#gcroot"><tt>@llvm.gcroot</tt></a> intrinsic.</li>
				980	</ul>
				981
				982	<p>Also, for the function as a whole:</p>
				983
				984	<ul>
				985	<li><tt>getFrameSize()</tt>: The overall size of the function's initial
				986	stack frame, not accounting for any dynamic allocation.</li>
				987	<li><tt>roots_size()</tt>: The count of roots in the function.</li>
				988	</ul>
				989
				990	<p>To access the stack map, use <tt>GCFunctionMetadata::roots_begin()</tt> and
				991	-<tt>end()</tt> from the <tt><a
				992	href="#assembly">GCMetadataPrinter</a></tt>:</p>
				993
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	994	<blockquote><pre
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	995	>for (iterator I = begin(), E = end(); I != E; ++I) {
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	996	GCFunctionInfo FI = I;
				997	unsigned FrameSize = FI->getFrameSize();
				998	size_t RootCount = FI->roots_size();
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	999
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	1000	for (GCFunctionInfo::roots_iterator RI = FI->roots_begin(),
				1001	RE = FI->roots_end();
				1002	RI != RE; ++RI) {
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	1003	int RootNum = RI->Num;
				1004	int RootStackOffset = RI->StackOffset;
				1005	Constant *RootMetadata = RI->Metadata;
				1006	}
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1007	}</pre></blockquote>
				1008
Gordon Henriksen	562b544	2009-03-06 01:57:32 +0000	[diff] [blame]	1009	<p>If the <tt>llvm.gcroot</tt> intrinsic is eliminated before code generation by
				1010	a custom lowering pass, LLVM will compute an empty stack map. This may be useful
				1011	for collector plugins which implement reference counting or a shadow stack.</p>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1012
				1013	</div>
				1014
				1015
				1016	<!-- ======================================================================= -->
				1017	<div class="doc_subsection">
				1018	<a name="init-roots">Initializing roots to null: <tt>InitRoots</tt></a>
				1019	</div>
				1020
				1021	<div class="doc_text">
				1022
				1023	<blockquote><pre
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	1024	>MyGC::MyGC() {
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1025	InitRoots = true;
				1026	}</pre></blockquote>
				1027
				1028	<p>When set, LLVM will automatically initialize each root to <tt>null</tt> upon
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	1029	entry to the function. This prevents the GC's sweep phase from visiting
				1030	uninitialized pointers, which will almost certainly cause it to crash. This
				1031	initialization occurs before custom lowering, so the two may be used
				1032	together.</p>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1033
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	1034	<p>Since LLVM does not yet compute liveness information, there is no means of
				1035	distinguishing an uninitialized stack root from an initialized one. Therefore,
				1036	this feature should be used by all GC plugins. It is enabled by default.</p>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1037
				1038	</div>
				1039
				1040
				1041	<!-- ======================================================================= -->
				1042	<div class="doc_subsection">
				1043	<a name="custom">Custom lowering of intrinsics: <tt>CustomRoots</tt>,
				1044	<tt>CustomReadBarriers</tt>, and <tt>CustomWriteBarriers</tt></a>
				1045	</div>
				1046
				1047	<div class="doc_text">
				1048
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	1049	<p>For GCs which use barriers or unusual treatment of stack roots, these
				1050	flags allow the collector to perform arbitrary transformations of the LLVM
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1051	IR:</p>
				1052
				1053	<blockquote><pre
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	1054	>class MyGC : public GCStrategy {
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1055	public:
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	1056	MyGC() {
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1057	CustomRoots = true;
				1058	CustomReadBarriers = true;
				1059	CustomWriteBarriers = true;
				1060	}
				1061
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	1062	virtual bool initializeCustomLowering(Module &M);
				1063	virtual bool performCustomLowering(Function &F);
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1064	};</pre></blockquote>
				1065
				1066	<p>If any of these flags are set, then LLVM suppresses its default lowering for
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	1067	the corresponding intrinsics and instead calls
				1068	<tt>performCustomLowering</tt>.</p>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1069
				1070	<p>LLVM's default action for each intrinsic is as follows:</p>
				1071
				1072	<ul>
Gordon Henriksen	562b544	2009-03-06 01:57:32 +0000	[diff] [blame]	1073	<li><tt>llvm.gcroot</tt>: Leave it alone. The code generator must see it
				1074	or the stack map will not be computed.</li>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1075	<li><tt>llvm.gcread</tt>: Substitute a <tt>load</tt> instruction.</li>
				1076	<li><tt>llvm.gcwrite</tt>: Substitute a <tt>store</tt> instruction.</li>
				1077	</ul>
				1078
				1079	<p>If <tt>CustomReadBarriers</tt> or <tt>CustomWriteBarriers</tt> are specified,
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	1080	then <tt>performCustomLowering</tt> <strong>must</strong> eliminate the
				1081	corresponding barriers.</p>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1082
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	1083	<p><tt>performCustomLowering</tt> must comply with the same restrictions as <a
				1084	href="WritingAnLLVMPass.html#runOnFunction"><tt
				1085	>FunctionPass::runOnFunction</tt></a>.
				1086	Likewise, <tt>initializeCustomLowering</tt> has the same semantics as <a
				1087	href="WritingAnLLVMPass.html#doInitialization_mod"><tt
				1088	>Pass::doInitialization(Module&)</tt></a>.</p>
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	1089
				1090	<p>The following can be used as a template:</p>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1091
				1092	<blockquote><pre
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	1093	>#include "llvm/Module.h"
Gordon Henriksen	7459f14	2007-12-22 23:32:32 +0000	[diff] [blame]	1094	#include "llvm/IntrinsicInst.h"
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1095
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	1096	bool MyGC::initializeCustomLowering(Module &M) {
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	1097	return false;
				1098	}
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1099
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	1100	bool MyGC::performCustomLowering(Function &F) {
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	1101	bool MadeChange = false;
				1102
				1103	for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
Gordon Henriksen	8adc545	2007-12-22 23:34:26 +0000	[diff] [blame]	1104	for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; )
				1105	if (IntrinsicInst *CI = dyn_cast<IntrinsicInst>(II++))
Gordon Henriksen	7459f14	2007-12-22 23:32:32 +0000	[diff] [blame]	1106	if (Function *F = CI->getCalledFunction())
				1107	switch (F->getIntrinsicID()) {
				1108	case Intrinsic::gcwrite:
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	1109	// Handle llvm.gcwrite.
Gordon Henriksen	7459f14	2007-12-22 23:32:32 +0000	[diff] [blame]	1110	CI->eraseFromParent();
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	1111	MadeChange = true;
Gordon Henriksen	7459f14	2007-12-22 23:32:32 +0000	[diff] [blame]	1112	break;
				1113	case Intrinsic::gcread:
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	1114	// Handle llvm.gcread.
Gordon Henriksen	7459f14	2007-12-22 23:32:32 +0000	[diff] [blame]	1115	CI->eraseFromParent();
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	1116	MadeChange = true;
Gordon Henriksen	7459f14	2007-12-22 23:32:32 +0000	[diff] [blame]	1117	break;
				1118	case Intrinsic::gcroot:
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	1119	// Handle llvm.gcroot.
Gordon Henriksen	7459f14	2007-12-22 23:32:32 +0000	[diff] [blame]	1120	CI->eraseFromParent();
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	1121	MadeChange = true;
Gordon Henriksen	7459f14	2007-12-22 23:32:32 +0000	[diff] [blame]	1122	break;
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	1123	}
				1124
				1125	return MadeChange;
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1126	}</pre></blockquote>
				1127
				1128	</div>
				1129
				1130
				1131	<!-- ======================================================================= -->
				1132	<div class="doc_subsection">
				1133	<a name="safe-points">Generating safe points: <tt>NeededSafePoints</tt></a>
				1134	</div>
				1135
				1136	<div class="doc_text">
				1137
				1138	<p>LLVM can compute four kinds of safe points:</p>
				1139
				1140	<blockquote><pre
				1141	>namespace GC {
				1142	/// PointKind - The type of a collector-safe point.
				1143	///
				1144	enum PointKind {
				1145	Loop, //< Instr is a loop (backwards branch).
				1146	Return, //< Instr is a return instruction.
				1147	PreCall, //< Instr is a call instruction.
				1148	PostCall //< Instr is the return address of a call.
				1149	};
				1150	}</pre></blockquote>
				1151
				1152	<p>A collector can request any combination of the four by setting the
				1153	<tt>NeededSafePoints</tt> mask:</p>
				1154
				1155	<blockquote><pre
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	1156	>MyGC::MyGC() {
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1157	NeededSafePoints = 1 << GC::Loop
				1158	\| 1 << GC::Return
				1159	\| 1 << GC::PreCall
				1160	\| 1 << GC::PostCall;
				1161	}</pre></blockquote>
				1162
				1163	<p>It can then use the following routines to access safe points.</p>
				1164
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	1165	<blockquote><pre
				1166	>for (iterator I = begin(), E = end(); I != E; ++I) {
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	1167	GCFunctionInfo MD = I;
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	1168	size_t PointCount = MD->size();
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1169
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	1170	for (GCFunctionInfo::iterator PI = MD->begin(),
				1171	PE = MD->end(); PI != PE; ++PI) {
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	1172	GC::PointKind PointKind = PI->Kind;
				1173	unsigned PointNum = PI->Num;
				1174	}
				1175	}
				1176	</pre></blockquote>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1177
				1178	<p>Almost every collector requires <tt>PostCall</tt> safe points, since these
				1179	correspond to the moments when the function is suspended during a call to a
				1180	subroutine.</p>
				1181
				1182	<p>Threaded programs generally require <tt>Loop</tt> safe points to guarantee
				1183	that the application will reach a safe point within a bounded amount of time,
				1184	even if it is executing a long-running loop which contains no function
				1185	calls.</p>
				1186
				1187	<p>Threaded collectors may also require <tt>Return</tt> and <tt>PreCall</tt>
				1188	safe points to implement "stop the world" techniques using self-modifying code,
				1189	where it is important that the program not exit the function without reaching a
				1190	safe point (because only the topmost function has been patched).</p>
				1191
				1192	</div>
				1193
				1194
				1195	<!-- ======================================================================= -->
				1196	<div class="doc_subsection">
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	1197	<a name="assembly">Emitting assembly code: <tt>GCMetadataPrinter</tt></a>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1198	</div>
				1199
				1200	<div class="doc_text">
				1201
Gordon Henriksen	562b544	2009-03-06 01:57:32 +0000	[diff] [blame]	1202	<p>LLVM allows a plugin to print arbitrary assembly code before and after the
				1203	rest of a module's assembly code. At the end of the module, the GC can compile
				1204	the LLVM stack map into assembly code. (At the beginning, this information is not
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	1205	yet computed.)</p>
				1206
				1207	<p>Since AsmWriter and CodeGen are separate components of LLVM, a separate
				1208	abstract base class and registry is provided for printing assembly code, the
Gordon Henriksen	8c977e0	2009-03-02 03:47:20 +0000	[diff] [blame]	1209	<tt>GCMetadaPrinter</tt> and <tt>GCMetadataPrinterRegistry</tt>. The AsmWriter
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	1210	will look for such a subclass if the <tt>GCStrategy</tt> sets
				1211	<tt>UsesMetadata</tt>:</p>
				1212
				1213	<blockquote><pre
				1214	>MyGC::MyGC() {
				1215	UsesMetadata = true;
				1216	}</pre></blockquote>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1217
Gordon Henriksen	562b544	2009-03-06 01:57:32 +0000	[diff] [blame]	1218	<p>This separation allows JIT-only clients to be smaller.</p>
				1219
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	1220	<p>Note that LLVM does not currently have analogous APIs to support code
				1221	generation in the JIT, nor using the object writers.</p>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1222
				1223	<blockquote><pre
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	1224	>// lib/MyGC/MyGCPrinter.cpp - Example LLVM GC printer
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1225
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	1226	#include "llvm/CodeGen/GCMetadataPrinter.h"
				1227	#include "llvm/Support/Compiler.h"
				1228
				1229	using namespace llvm;
				1230
				1231	namespace {
				1232	class VISIBILITY_HIDDEN MyGCPrinter : public GCMetadataPrinter {
				1233	public:
				1234	virtual void beginAssembly(std::ostream &OS, AsmPrinter &AP,
				1235	const TargetAsmInfo &TAI);
				1236
				1237	virtual void finishAssembly(std::ostream &OS, AsmPrinter &AP,
				1238	const TargetAsmInfo &TAI);
				1239	};
				1240
				1241	GCMetadataPrinterRegistry::Add<MyGCPrinter>
				1242	X("mygc", "My bespoke garbage collector.");
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1243	}</pre></blockquote>
				1244
				1245	<p>The collector should use <tt>AsmPrinter</tt> and <tt>TargetAsmInfo</tt> to
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	1246	print portable assembly code to the <tt>std::ostream</tt>. The collector itself
				1247	contains the stack map for the entire module, and may access the
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	1248	<tt>GCFunctionInfo</tt> using its own <tt>begin()</tt> and <tt>end()</tt>
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	1249	methods. Here's a realistic example:</p>
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1250
				1251	<blockquote><pre
				1252	>#include "llvm/CodeGen/AsmPrinter.h"
				1253	#include "llvm/Function.h"
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	1254	#include "llvm/Target/TargetMachine.h"
				1255	#include "llvm/Target/TargetData.h"
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1256	#include "llvm/Target/TargetAsmInfo.h"
				1257
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	1258	void MyGCPrinter::beginAssembly(std::ostream &OS, AsmPrinter &AP,
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	1259	const TargetAsmInfo &TAI) {
				1260	// Nothing to do.
				1261	}
				1262
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	1263	void MyGCPrinter::finishAssembly(std::ostream &OS, AsmPrinter &AP,
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	1264	const TargetAsmInfo &TAI) {
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1265	// Set up for emitting addresses.
				1266	const char *AddressDirective;
				1267	int AddressAlignLog;
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	1268	if (AP.TM.getTargetData()->getPointerSize() == sizeof(int32_t)) {
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1269	AddressDirective = TAI.getData32bitsDirective();
				1270	AddressAlignLog = 2;
				1271	} else {
				1272	AddressDirective = TAI.getData64bitsDirective();
				1273	AddressAlignLog = 3;
				1274	}
				1275
				1276	// Put this in the data section.
				1277	AP.SwitchToDataSection(TAI.getDataSection());
				1278
				1279	// For each function...
Gordon Henriksen	c22962f	2007-12-11 00:30:17 +0000	[diff] [blame]	1280	for (iterator FI = begin(), FE = end(); FI != FE; ++FI) {
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	1281	GCFunctionInfo &MD = **FI;
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1282
				1283	// Emit this data structure:
				1284	//
				1285	// struct {
				1286	// int32_t PointCount;
				1287	// struct {
				1288	// void *SafePointAddress;
				1289	// int32_t LiveCount;
				1290	// int32_t LiveOffsets[LiveCount];
				1291	// } Points[PointCount];
				1292	// } __gcmap_<FUNCTIONNAME>;
				1293
				1294	// Align to address width.
				1295	AP.EmitAlignment(AddressAlignLog);
				1296
Gordon Henriksen	562b544	2009-03-06 01:57:32 +0000	[diff] [blame]	1297	// Emit the symbol by which the stack map entry can be found.
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1298	std::string Symbol;
				1299	Symbol += TAI.getGlobalPrefix();
				1300	Symbol += "__gcmap_";
				1301	Symbol += MD.getFunction().getName();
				1302	if (const char *GlobalDirective = TAI.getGlobalDirective())
				1303	OS << GlobalDirective << Symbol << "\n";
				1304	OS << TAI.getGlobalPrefix() << Symbol << ":\n";
				1305
				1306	// Emit PointCount.
				1307	AP.EmitInt32(MD.size());
				1308	AP.EOL("safe point count");
				1309
				1310	// And each safe point...
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	1311	for (GCFunctionInfo::iterator PI = MD.begin(),
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1312	PE = MD.end(); PI != PE; ++PI) {
				1313	// Align to address width.
				1314	AP.EmitAlignment(AddressAlignLog);
				1315
				1316	// Emit the address of the safe point.
				1317	OS << AddressDirective
				1318	<< TAI.getPrivateGlobalPrefix() << "label" << PI->Num;
				1319	AP.EOL("safe point address");
				1320
				1321	// Emit the stack frame size.
				1322	AP.EmitInt32(MD.getFrameSize());
				1323	AP.EOL("stack frame size");
				1324
				1325	// Emit the number of live roots in the function.
				1326	AP.EmitInt32(MD.live_size(PI));
				1327	AP.EOL("live root count");
				1328
				1329	// And for each live root...
Gordon Henriksen	8d1b224	2008-08-24 03:18:23 +0000	[diff] [blame]	1330	for (GCFunctionInfo::live_iterator LI = MD.live_begin(PI),
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1331	LE = MD.live_end(PI);
				1332	LI != LE; ++LI) {
				1333	// Print its offset within the stack frame.
				1334	AP.EmitInt32(LI->StackOffset);
				1335	AP.EOL("stack offset");
				1336	}
				1337	}
				1338	}
				1339	}
				1340	</pre></blockquote>
				1341
				1342	</div>
				1343
				1344
				1345	<!-- *********************************************************************** -->
				1346	<div class="doc_section">
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	1347	<a name="references">References</a>
				1348	</div>
				1349	<!-- *********************************************************************** -->
				1350
				1351	<div class="doc_text">
				1352
				1353	<p><a name="appel89">[Appel89]</a> Runtime Tags Aren't Necessary. Andrew
				1354	W. Appel. Lisp and Symbolic Computation 19(7):703-705, July 1989.</p>
				1355
				1356	<p><a name="goldberg91">[Goldberg91]</a> Tag-free garbage collection for
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1357	strongly typed programming languages. Benjamin Goldberg. ACM SIGPLAN
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	1358	PLDI'91.</p>
				1359
				1360	<p><a name="tolmach94">[Tolmach94]</a> Tag-free garbage collection using
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1361	explicit type parameters. Andrew Tolmach. Proceedings of the 1994 ACM
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	1362	conference on LISP and functional programming.</p>
				1363
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1364	<p><a name="henderson02">[Henderson2002]</a> <a
				1365	href="http://citeseer.ist.psu.edu/henderson02accurate.html">
				1366	Accurate Garbage Collection in an Uncooperative Environment</a>.
				1367	Fergus Henderson. International Symposium on Memory Management 2002.</p>
				1368
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	1369	</div>
				1370
Gordon Henriksen	fba997d	2007-09-27 19:31:36 +0000	[diff] [blame]	1371
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	1372	<!-- *********************************************************************** -->
				1373
				1374	<hr>
				1375	<address>
				1376	<a href="http://jigsaw.w3.org/css-validator/check/referer"><img
Misha Brukman	947321d	2008-12-11 17:34:48 +0000	[diff] [blame]	1377	src="http://jigsaw.w3.org/css-validator/images/vcss-blue" alt="Valid CSS"></a>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	1378	<a href="http://validator.w3.org/check/referer"><img
Misha Brukman	947321d	2008-12-11 17:34:48 +0000	[diff] [blame]	1379	src="http://www.w3.org/Icons/valid-html401-blue" alt="Valid HTML 4.01"></a>
Dan Gohman	f17a25c	2007-07-18 16:29:46 +0000	[diff] [blame]	1380
				1381	<a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
				1382	<a href="http://llvm.org">LLVM Compiler Infrastructure</a><br>
				1383	Last modified: $Date$
				1384	</address>
				1385
				1386	</body>
				1387	</html>