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

blob: 1508bcf2231068fc44472d16f6f37a125cafdfb1 [file] [log] [blame]

Chris Lattner	0d8c2db	2004-05-23 21:02:20 +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	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	5	<meta http-equiv="Content-Type" Content="text/html; charset=UTF-8" >
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	6	<title>Accurate Garbage Collection with LLVM</title>
				7	<link rel="stylesheet" href="llvm.css" type="text/css">
Gordon Henriksen	326e24f	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>
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +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	c9c0b59	2009-03-02 03:47:20 +0000	[diff] [blame]	23	<li><a href="#feature">Goals and non-goals</a></li>
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	24	</ul>
				25	</li>
				26
Gordon Henriksen	c9c0b59	2009-03-02 03:47:20 +0000	[diff] [blame]	27	<li><a href="#quickstart">Getting started</a>
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	28	<ul>
Gordon Henriksen	e5abac4	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	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	32	</ul>
				33	</li>
				34
Gordon Henriksen	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	35	<li><a href="#core">Core support</a>
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	36	<ul>
Gordon Henriksen	ad93c4f	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	326e24f	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	c9c0b59	2009-03-02 03:47:20 +0000	[diff] [blame]	50	<li><a href="#plugin">Compiler plugin interface</a>
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	51	<ul>
Gordon Henriksen	326e24f	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	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	61	<tt>GCMetadataPrinter</tt></a></li>
Chris Lattner	0b02dbc	2004-07-09 05:03:54 +0000	[diff] [blame]	62	</ul>
Chris Lattner	9b2a184	2004-05-27 05:52:10 +0000	[diff] [blame]	63	</li>
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	64
Gordon Henriksen	326e24f	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
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	74	</ol>
				75
				76	<div class="doc_author">
Gordon Henriksen	326e24f	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>
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +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	326e24f	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:
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +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	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	98	information from the compiler. The
Jeff Cohen	65fc36b	2007-04-18 17:26:14 +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>
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	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	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	104	most cases). Identifying pointers at run-time requires compiler support to
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	105	locate all places that hold live pointer variables at run-time, including the
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	106	<a href="#gcroot">processor stack and registers</a>.</p>
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	107
Gordon Henriksen	326e24f	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
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +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	326e24f	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>
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	116
Gordon Henriksen	326e24f	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,
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	119	because the runtime must be able to identify and update all pointers active in
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	120	the program, some optimizations are less effective. In practice, however, the
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	121	locality and performance benefits of using aggressive garbage allocation
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	122	techniques dominates any low-level losses.</p>
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	123
Gordon Henriksen	326e24f	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>
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	126
				127	</div>
				128
				129	<!-- ======================================================================= -->
				130	<div class="doc_subsection">
Gordon Henriksen	c9c0b59	2009-03-02 03:47:20 +0000	[diff] [blame]	131	<a name="feature">Goals and non-goals</a>
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	132	</div>
				133
				134	<div class="doc_text">
				135
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	136	<p>LLVM's intermediate representation provides <a href="#intrinsics">garbage
Chris Lattner	05d6709	2008-04-24 05:59:56 +0000	[diff] [blame]	137	collection intrinsics</a> that offer support for a broad class of
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	138	collector models. For instance, the intrinsics permit:</p>
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	139
Gordon Henriksen	326e24f	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>
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	149
Gordon Henriksen	326e24f	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	c9c0b59	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	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	165
				166	<ul>
Gordon Henriksen	c9c0b59	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	e5abac4	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	c9c0b59	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	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	177	</ul>
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	178
Gordon Henriksen	c9c0b59	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	e5abac4	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	c9c0b59	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	e5abac4	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	c9c0b59	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
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	199	</div>
				200
				201	<!-- *********************************************************************** -->
				202	<div class="doc_section">
Gordon Henriksen	c9c0b59	2009-03-02 03:47:20 +0000	[diff] [blame]	203	<a name="quickstart">Getting started</a>
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	204	</div>
				205	<!-- *********************************************************************** -->
				206
				207	<div class="doc_text">
				208
Gordon Henriksen	c9c0b59	2009-03-02 03:47:20 +0000	[diff] [blame]	209	<p>Using a GC with LLVM implies many things, for example:</p>
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	210
				211	<ul>
Gordon Henriksen	c9c0b59	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	e5abac4	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	c9c0b59	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	e5abac4	2009-03-06 01:57:32 +0000	[diff] [blame]	219	<li>Design a binary interface for type maps, used to identify references
Gordon Henriksen	c9c0b59	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	e5abac4	2009-03-06 01:57:32 +0000	[diff] [blame]	232	<li>Generate type maps according to your runtime's binary interface.</li>
Gordon Henriksen	c9c0b59	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	e5abac4	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	c9c0b59	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	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	243	</ul>
				244
Gordon Henriksen	c9c0b59	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>
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	248
				249	</div>
				250
				251	<!-- ======================================================================= -->
				252	<div class="doc_subsection">
Gordon Henriksen	c9c0b59	2009-03-02 03:47:20 +0000	[diff] [blame]	253	<a name="quickstart-compiler">In your compiler</a>
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	254	</div>
				255
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	256	<div class="doc_text">
				257
Gordon Henriksen	c9c0b59	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	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	259
Gordon Henriksen	c9c0b59	2009-03-02 03:47:20 +0000	[diff] [blame]	260	<div class="doc_code"><pre
				261	>F.setGC("shadow-stack");</pre></div>
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	262
Gordon Henriksen	c9c0b59	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	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	275
				276	</div>
				277
				278	<!-- ======================================================================= -->
				279	<div class="doc_subsection">
Gordon Henriksen	c9c0b59	2009-03-02 03:47:20 +0000	[diff] [blame]	280	<a name="quickstart-runtime">In your runtime</a>
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	281	</div>
				282
				283	<div class="doc_text">
				284
Gordon Henriksen	c9c0b59	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	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	288
Gordon Henriksen	c9c0b59	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	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	294
				295	</div>
				296
Gordon Henriksen	c9c0b59	2009-03-02 03:47:20 +0000	[diff] [blame]	297	<div class="doc_code"><pre
Gordon Henriksen	e5abac4	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	c9c0b59	2009-03-02 03:47:20 +0000	[diff] [blame]	300	///
Gordon Henriksen	e5abac4	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	c9c0b59	2009-03-02 03:47:20 +0000	[diff] [blame]	303	struct FrameMap {
				304	int32_t NumRoots; //< Number of roots in stack frame.
Gordon Henriksen	e5abac4	2009-03-06 01:57:32 +0000	[diff] [blame]	305	int32_t NumMeta; //< Number of metadata entries. May be < NumRoots.
Gordon Henriksen	c9c0b59	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)
				337	Visitor(&R->Roots[i], R->Map->Meta[i]);
				338
				339	// For roots [NumMeta, NumRoots), the metadata pointer is null.
				340	for (unsigned e = R->Map->NumRoots; i != e; ++i)
				341	Visitor(&R->Roots[i], NULL);
				342	}
				343	}</pre></div>
				344
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	345	<!-- ======================================================================= -->
				346	<div class="doc_subsection">
Gordon Henriksen	c9c0b59	2009-03-02 03:47:20 +0000	[diff] [blame]	347	<a name="shadow-stack">About the shadow stack</a>
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	348	</div>
				349
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	350	<div class="doc_text">
				351
Gordon Henriksen	c9c0b59	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	e5abac4	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	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	360
Gordon Henriksen	c9c0b59	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	e5abac4	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	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	372
				373	</div>
				374
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	375	<!-- *********************************************************************** -->
				376	<div class="doc_section">
Gordon Henriksen	c9c0b59	2009-03-02 03:47:20 +0000	[diff] [blame]	377	<a name="core">IR features</a><a name="intrinsics"></a>
Gordon Henriksen	326e24f	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	c9c0b59	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	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	387
Gordon Henriksen	c9c0b59	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	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	392
				393	</div>
				394
				395	<!-- ======================================================================= -->
				396	<div class="doc_subsection">
Gordon Henriksen	ad93c4f	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>
Gordon Henriksen	c9c0b59	2009-03-02 03:47:20 +0000	[diff] [blame]	401	define <i>ty</i> @<i>name</i>(...) <u>gc "<i>name</i>"</u> { ...
Gordon Henriksen	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	402	</tt></div>
				403
				404	<div class="doc_text">
				405
Gordon Henriksen	c9c0b59	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	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	409
Gordon Henriksen	c9c0b59	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	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	417
				418	</div>
				419
				420	<!-- ======================================================================= -->
				421	<div class="doc_subsection">
Gordon Henriksen	326e24f	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
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	425	<div class="doc_code"><tt>
Chris Lattner	1734055	2008-04-24 06:00:30 +0000	[diff] [blame]	426	void @llvm.gcroot(i8** %ptrloc, i8* %metadata)
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	427	</tt></div>
				428
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	429	<div class="doc_text">
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	430
Gordon Henriksen	c9c0b59	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	326e24f	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	c9c0b59	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	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	456	<p>Consider the following fragment of Java code:</p>
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	457
				458	<pre>
				459	{
				460	Object X; // A null-initialized reference to an object
				461	...
				462	}
				463	</pre>
				464
Gordon Henriksen	326e24f	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>
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +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	326e24f	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	1734055	2008-04-24 06:00:30 +0000	[diff] [blame]	477	call void @llvm.gcroot(i8** %X, i8* null)
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	478	...
				479
				480	;; "CodeBlock" is the block corresponding to the start
Reid Spencer	03d186a	2004-05-25 08:45:31 +0000	[diff] [blame]	481	;; of the scope above.
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	482	CodeBlock:
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	483	;; Java null-initializes pointers.
				484	store %Object* null, %Object** %X
				485
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +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	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	498	<a name="barriers">Reading and writing references in the heap</a>
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	499	</div>
				500
				501	<div class="doc_text">
				502
Gordon Henriksen	326e24f	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>
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	510
Gordon Henriksen	326e24f	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	05d6709	2008-04-24 05:59:56 +0000	[diff] [blame]	517	<blockquote><pre>
				518	;; An array type.
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	519	%class.Array = type { %class.Object, i32, [0 x %class.Object*] }
Chris Lattner	05d6709	2008-04-24 05:59:56 +0000	[diff] [blame]	520	...
Gordon Henriksen	326e24f	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	05d6709	2008-04-24 05:59:56 +0000	[diff] [blame]	526	%derived = getelementptr %object, i32 0, i32 2, i32 %n</pre></blockquote>
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	527
Gordon Henriksen	c9c0b59	2009-03-02 03:47:20 +0000	[diff] [blame]	528	<p>The use of these intrinsics is naturally optional if the target GC does
				529	require the corresponding barrier. If so, the GC plugin will replace the
				530	intrinsic calls with the corresponding <tt>load</tt> or <tt>store</tt>
				531	instruction if they are used.</p>
				532
Gordon Henriksen	e5abac4	2009-03-06 01:57:32 +0000	[diff] [blame]	533	<p>LLVM does not enforce any particular relationship between the object and
				534	derived pointer (although a <a href="#plugin">plugin</a> might). However, it
				535	would be unusual that the derived pointer not be a <tt>getelementptr</tt> of the
				536	object pointer.</p>
				537
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	538	</div>
				539
				540	<!-- ======================================================================= -->
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	541	<div class="doc_subsubsection">
				542	<a name="gcwrite">Write barrier: <tt>llvm.gcwrite</tt></a>
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	543	</div>
				544
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	545	<div class="doc_code"><tt>
				546	void @llvm.gcwrite(i8* %value, i8* %object, i8** %derived)
				547	</tt></div>
				548
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	549	<div class="doc_text">
				550
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	551	<p>For write barriers, LLVM provides the <tt>llvm.gcwrite</tt> intrinsic
				552	function. It has exactly the same semantics as a non-volatile <tt>store</tt> to
Gordon Henriksen	c9c0b59	2009-03-02 03:47:20 +0000	[diff] [blame]	553	the derived pointer (the third argument). The exact code generated is specified
				554	by a <a href="#plugin">compiler plugin</a>.</p>
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	555
				556	<p>Many important algorithms require write barriers, including generational
				557	and concurrent collectors. Additionally, write barriers could be used to
				558	implement reference counting.</p>
				559
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	560	</div>
				561
				562	<!-- ======================================================================= -->
				563	<div class="doc_subsubsection">
				564	<a name="gcread">Read barrier: <tt>llvm.gcread</tt></a>
				565	</div>
				566
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	567	<div class="doc_code"><tt>
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	568	i8* @llvm.gcread(i8* %object, i8** %derived)<br>
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	569	</tt></div>
				570
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	571	<div class="doc_text">
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	572
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	573	<p>For read barriers, LLVM provides the <tt>llvm.gcread</tt> intrinsic function.
				574	It has exactly the same semantics as a non-volatile <tt>load</tt> from the
Gordon Henriksen	c9c0b59	2009-03-02 03:47:20 +0000	[diff] [blame]	575	derived pointer (the second argument). The exact code generated is specified by
				576	a <a href="#plugin">compiler plugin</a>.</p>
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	577
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	578	<p>Read barriers are needed by fewer algorithms than write barriers, and may
				579	have a greater performance impact since pointer reads are more frequent than
				580	writes.</p>
				581
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	582	</div>
				583
				584	<!-- *********************************************************************** -->
				585	<div class="doc_section">
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	586	<a name="plugin">Implementing a collector plugin</a>
				587	</div>
				588	<!-- *********************************************************************** -->
				589
				590	<div class="doc_text">
				591
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	592	<p>User code specifies which GC code generation to use with the <tt>gc</tt>
				593	function attribute or, equivalently, with the <tt>setGC</tt> method of
Gordon Henriksen	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	594	<tt>Function</tt>.</p>
				595
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	596	<p>To implement a GC plugin, it is necessary to subclass
				597	<tt>llvm::GCStrategy</tt>, which can be accomplished in a few lines of
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	598	boilerplate code. LLVM's infrastructure provides access to several important
Gordon Henriksen	e5abac4	2009-03-06 01:57:32 +0000	[diff] [blame]	599	algorithms. For an uncontroversial collector, all that remains may be to
				600	compile LLVM's computed stack map to assembly code (using the binary
				601	representation expected by the runtime library). This can be accomplished in
				602	about 100 lines of code.</p>
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	603
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	604	<p>This is not the appropriate place to implement a garbage collected heap or a
				605	garbage collector itself. That code should exist in the language's runtime
Gordon Henriksen	c9c0b59	2009-03-02 03:47:20 +0000	[diff] [blame]	606	library. The compiler plugin is responsible for generating code which
				607	conforms to the binary interface defined by library, most essentially the
Gordon Henriksen	e5abac4	2009-03-06 01:57:32 +0000	[diff] [blame]	608	<a href="#stack-map">stack map</a>.</p>
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	609
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	610	<p>To subclass <tt>llvm::GCStrategy</tt> and register it with the compiler:</p>
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	611
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	612	<blockquote><pre>// lib/MyGC/MyGC.cpp - Example LLVM GC plugin
				613
				614	#include "llvm/CodeGen/GCStrategy.h"
				615	#include "llvm/CodeGen/GCMetadata.h"
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	616	#include "llvm/Support/Compiler.h"
				617
				618	using namespace llvm;
				619
				620	namespace {
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	621	class VISIBILITY_HIDDEN MyGC : public GCStrategy {
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	622	public:
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	623	MyGC() {}
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	624	};
				625
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	626	GCRegistry::Add<MyGC>
Gordon Henriksen	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	627	X("mygc", "My bespoke garbage collector.");
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	628	}</pre></blockquote>
				629
Gordon Henriksen	e5abac4	2009-03-06 01:57:32 +0000	[diff] [blame]	630	<p>This boilerplate collector does nothing. More specifically:</p>
				631
				632	<ul>
				633	<li><tt>llvm.gcread</tt> calls are replaced with the corresponding
				634	<tt>load</tt> instruction.</li>
				635	<li><tt>llvm.gcwrite</tt> calls are replaced with the corresponding
				636	<tt>store</tt> instruction.</li>
				637	<li>No safe points are added to the code.</li>
				638	<li>The stack map is not compiled into the executable.</li>
				639	</ul>
				640
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	641	<p>Using the LLVM makefiles (like the <a
				642	href="http://llvm.org/viewvc/llvm-project/llvm/trunk/projects/sample/">sample
Gordon Henriksen	e5abac4	2009-03-06 01:57:32 +0000	[diff] [blame]	643	project</a>), this code can be compiled as a plugin using a simple
				644	makefile:</p>
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	645
				646	<blockquote><pre
				647	># lib/MyGC/Makefile
				648
				649	LEVEL := ../..
				650	LIBRARYNAME = <var>MyGC</var>
				651	LOADABLE_MODULE = 1
				652
				653	include $(LEVEL)/Makefile.common</pre></blockquote>
				654
Gordon Henriksen	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	655	<p>Once the plugin is compiled, code using it may be compiled using <tt>llc
				656	-load=<var>MyGC.so</var></tt> (though <var>MyGC.so</var> may have some other
				657	platform-specific extension):</p>
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	658
				659	<blockquote><pre
Gordon Henriksen	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	660	>$ cat sample.ll
				661	define void @f() gc "mygc" {
				662	entry:
				663	ret void
				664	}
				665	$ llvm-as < sample.ll \| llc -load=MyGC.so</pre></blockquote>
				666
				667	<p>It is also possible to statically link the collector plugin into tools, such
				668	as a language-specific compiler front-end.</p>
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	669
				670	</div>
				671
				672	<!-- ======================================================================= -->
				673	<div class="doc_subsection">
				674	<a name="collector-algos">Overview of available features</a>
				675	</div>
				676
				677	<div class="doc_text">
				678
Gordon Henriksen	e5abac4	2009-03-06 01:57:32 +0000	[diff] [blame]	679	<p><tt>GCStrategy</tt> provides a range of features through which a plugin
				680	may do useful work. Some of these are callbacks, some are algorithms that can
				681	be enabled, disabled, or customized. This matrix summarizes the supported (and
				682	planned) features and correlates them with the collection techniques which
				683	typically require them.</p>
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	684
				685	<table>
				686	<tr>
				687	<th>Algorithm</th>
				688	<th>Done</th>
				689	<th>shadow stack</th>
				690	<th>refcount</th>
				691	<th>mark-sweep</th>
				692	<th>copying</th>
				693	<th>incremental</th>
				694	<th>threaded</th>
				695	<th>concurrent</th>
				696	</tr>
				697	<tr>
				698	<th class="rowhead"><a href="#stack-map">stack map</a></th>
				699	<td>✔</td>
				700	<td></td>
				701	<td></td>
				702	<td>✘</td>
				703	<td>✘</td>
				704	<td>✘</td>
				705	<td>✘</td>
				706	<td>✘</td>
				707	</tr>
				708	<tr>
				709	<th class="rowhead"><a href="#init-roots">initialize roots</a></th>
				710	<td>✔</td>
				711	<td>✘</td>
				712	<td>✘</td>
				713	<td>✘</td>
				714	<td>✘</td>
				715	<td>✘</td>
				716	<td>✘</td>
				717	<td>✘</td>
				718	</tr>
				719	<tr class="doc_warning">
				720	<th class="rowhead">derived pointers</th>
				721	<td>NO</td>
				722	<td></td>
				723	<td></td>
				724	<td></td>
				725	<td></td>
				726	<td></td>
				727	<td>✘*</td>
				728	<td>✘*</td>
				729	</tr>
				730	<tr>
				731	<th class="rowhead"><em><a href="#custom">custom lowering</a></em></th>
				732	<td>✔</td>
				733	<th></th>
				734	<th></th>
				735	<th></th>
				736	<th></th>
				737	<th></th>
				738	<th></th>
				739	<th></th>
				740	</tr>
				741	<tr>
				742	<th class="rowhead indent">gcroot</th>
				743	<td>✔</td>
				744	<td>✘</td>
				745	<td>✘</td>
				746	<td></td>
				747	<td></td>
				748	<td></td>
				749	<td></td>
				750	<td></td>
				751	</tr>
				752	<tr>
				753	<th class="rowhead indent">gcwrite</th>
				754	<td>✔</td>
				755	<td></td>
				756	<td>✘</td>
				757	<td></td>
				758	<td></td>
				759	<td>✘</td>
				760	<td></td>
				761	<td>✘</td>
				762	</tr>
				763	<tr>
				764	<th class="rowhead indent">gcread</th>
				765	<td>✔</td>
				766	<td></td>
				767	<td></td>
				768	<td></td>
				769	<td></td>
				770	<td></td>
				771	<td></td>
				772	<td>✘</td>
				773	</tr>
				774	<tr>
				775	<th class="rowhead"><em><a href="#safe-points">safe points</a></em></th>
				776	<td></td>
				777	<th></th>
				778	<th></th>
				779	<th></th>
				780	<th></th>
				781	<th></th>
				782	<th></th>
				783	<th></th>
				784	</tr>
				785	<tr>
				786	<th class="rowhead indent">in calls</th>
				787	<td>✔</td>
				788	<td></td>
				789	<td></td>
				790	<td>✘</td>
				791	<td>✘</td>
				792	<td>✘</td>
				793	<td>✘</td>
				794	<td>✘</td>
				795	</tr>
				796	<tr>
				797	<th class="rowhead indent">before calls</th>
				798	<td>✔</td>
				799	<td></td>
				800	<td></td>
				801	<td></td>
				802	<td></td>
				803	<td></td>
				804	<td>✘</td>
				805	<td>✘</td>
				806	</tr>
				807	<tr class="doc_warning">
				808	<th class="rowhead indent">for loops</th>
				809	<td>NO</td>
				810	<td></td>
				811	<td></td>
				812	<td></td>
				813	<td></td>
				814	<td></td>
				815	<td>✘</td>
				816	<td>✘</td>
				817	</tr>
				818	<tr>
				819	<th class="rowhead indent">before escape</th>
				820	<td>✔</td>
				821	<td></td>
				822	<td></td>
				823	<td></td>
				824	<td></td>
				825	<td></td>
				826	<td>✘</td>
				827	<td>✘</td>
				828	</tr>
				829	<tr class="doc_warning">
				830	<th class="rowhead">emit code at safe points</th>
				831	<td>NO</td>
				832	<td></td>
				833	<td></td>
				834	<td></td>
				835	<td></td>
				836	<td></td>
				837	<td>✘</td>
				838	<td>✘</td>
				839	</tr>
				840	<tr>
				841	<th class="rowhead"><em>output</em></th>
				842	<td></td>
				843	<th></th>
				844	<th></th>
				845	<th></th>
				846	<th></th>
				847	<th></th>
				848	<th></th>
				849	<th></th>
				850	</tr>
				851	<tr>
				852	<th class="rowhead indent"><a href="#assembly">assembly</a></th>
				853	<td>✔</td>
				854	<td></td>
				855	<td></td>
				856	<td>✘</td>
				857	<td>✘</td>
				858	<td>✘</td>
				859	<td>✘</td>
				860	<td>✘</td>
				861	</tr>
				862	<tr class="doc_warning">
				863	<th class="rowhead indent">JIT</th>
				864	<td>NO</td>
				865	<td></td>
				866	<td></td>
				867	<td class="optl">✘</td>
				868	<td class="optl">✘</td>
				869	<td class="optl">✘</td>
				870	<td class="optl">✘</td>
				871	<td class="optl">✘</td>
				872	</tr>
				873	<tr class="doc_warning">
				874	<th class="rowhead indent">obj</th>
				875	<td>NO</td>
				876	<td></td>
				877	<td></td>
				878	<td class="optl">✘</td>
				879	<td class="optl">✘</td>
				880	<td class="optl">✘</td>
				881	<td class="optl">✘</td>
				882	<td class="optl">✘</td>
				883	</tr>
				884	<tr class="doc_warning">
				885	<th class="rowhead">live analysis</th>
				886	<td>NO</td>
				887	<td></td>
				888	<td></td>
				889	<td class="optl">✘</td>
				890	<td class="optl">✘</td>
				891	<td class="optl">✘</td>
				892	<td class="optl">✘</td>
				893	<td class="optl">✘</td>
				894	</tr>
				895	<tr class="doc_warning">
				896	<th class="rowhead">register map</th>
				897	<td>NO</td>
				898	<td></td>
				899	<td></td>
				900	<td class="optl">✘</td>
				901	<td class="optl">✘</td>
				902	<td class="optl">✘</td>
				903	<td class="optl">✘</td>
				904	<td class="optl">✘</td>
				905	</tr>
				906	<tr>
				907	<td colspan="10">
				908	<div><span class="doc_warning">*</span> Derived pointers only pose a
				909	hazard to copying collectors.</div>
				910	<div><span class="optl">✘</span> in gray denotes a feature which
				911	could be utilized if available.</div>
				912	</td>
				913	</tr>
				914	</table>
				915
				916	<p>To be clear, the collection techniques above are defined as:</p>
				917
				918	<dl>
				919	<dt>Shadow Stack</dt>
Gordon Henriksen	e5abac4	2009-03-06 01:57:32 +0000	[diff] [blame]	920	<dd>The mutator carefully maintains a linked list of stack roots.</dd>
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	921	<dt>Reference Counting</dt>
				922	<dd>The mutator maintains a reference count for each object and frees an
				923	object when its count falls to zero.</dd>
				924	<dt>Mark-Sweep</dt>
				925	<dd>When the heap is exhausted, the collector marks reachable objects starting
				926	from the roots, then deallocates unreachable objects in a sweep
				927	phase.</dd>
				928	<dt>Copying</dt>
				929	<dd>As reachability analysis proceeds, the collector copies objects from one
				930	heap area to another, compacting them in the process. Copying collectors
				931	enable highly efficient "bump pointer" allocation and can improve locality
				932	of reference.</dd>
				933	<dt>Incremental</dt>
				934	<dd>(Including generational collectors.) Incremental collectors generally have
				935	all the properties of a copying collector (regardless of whether the
				936	mature heap is compacting), but bring the added complexity of requiring
				937	write barriers.</dd>
				938	<dt>Threaded</dt>
				939	<dd>Denotes a multithreaded mutator; the collector must still stop the mutator
				940	("stop the world") before beginning reachability analysis. Stopping a
				941	multithreaded mutator is a complicated problem. It generally requires
				942	highly platform specific code in the runtime, and the production of
				943	carefully designed machine code at safe points.</dd>
				944	<dt>Concurrent</dt>
				945	<dd>In this technique, the mutator and the collector run concurrently, with
				946	the goal of eliminating pause times. In a <em>cooperative</em> collector,
				947	the mutator further aids with collection should a pause occur, allowing
				948	collection to take advantage of multiprocessor hosts. The "stop the world"
				949	problem of threaded collectors is generally still present to a limited
				950	extent. Sophisticated marking algorithms are necessary. Read barriers may
				951	be necessary.</dd>
				952	</dl>
				953
				954	<p>As the matrix indicates, LLVM's garbage collection infrastructure is already
				955	suitable for a wide variety of collectors, but does not currently extend to
				956	multithreaded programs. This will be added in the future as there is
				957	interest.</p>
				958
				959	</div>
				960
				961	<!-- ======================================================================= -->
				962	<div class="doc_subsection">
				963	<a name="stack-map">Computing stack maps</a>
				964	</div>
				965
				966	<div class="doc_text">
				967
Gordon Henriksen	e5abac4	2009-03-06 01:57:32 +0000	[diff] [blame]	968	<p>LLVM automatically computes a stack map. One of the most important features
				969	of a <tt>GCStrategy</tt> is to compile this information into the executable in
				970	the binary representation expected by the runtime library.</p>
				971
				972	<p>The stack map consists of the location and identity of each GC root in the
				973	each function in the module. For each root:</p>
				974
				975	<ul>
				976	<li><tt>RootNum</tt>: The index of the root.</li>
				977	<li><tt>StackOffset</tt>: The offset of the object relative to the frame
				978	pointer.</li>
				979	<li><tt>RootMetadata</tt>: The value passed as the <tt>%metadata</tt>
				980	parameter to the <a href="#gcroot"><tt>@llvm.gcroot</tt></a> intrinsic.</li>
				981	</ul>
				982
				983	<p>Also, for the function as a whole:</p>
				984
				985	<ul>
				986	<li><tt>getFrameSize()</tt>: The overall size of the function's initial
				987	stack frame, not accounting for any dynamic allocation.</li>
				988	<li><tt>roots_size()</tt>: The count of roots in the function.</li>
				989	</ul>
				990
				991	<p>To access the stack map, use <tt>GCFunctionMetadata::roots_begin()</tt> and
				992	-<tt>end()</tt> from the <tt><a
				993	href="#assembly">GCMetadataPrinter</a></tt>:</p>
				994
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	995	<blockquote><pre
Gordon Henriksen	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	996	>for (iterator I = begin(), E = end(); I != E; ++I) {
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	997	GCFunctionInfo FI = I;
				998	unsigned FrameSize = FI->getFrameSize();
				999	size_t RootCount = FI->roots_size();
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1000
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	1001	for (GCFunctionInfo::roots_iterator RI = FI->roots_begin(),
				1002	RE = FI->roots_end();
				1003	RI != RE; ++RI) {
Gordon Henriksen	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	1004	int RootNum = RI->Num;
				1005	int RootStackOffset = RI->StackOffset;
				1006	Constant *RootMetadata = RI->Metadata;
				1007	}
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1008	}</pre></blockquote>
				1009
Gordon Henriksen	e5abac4	2009-03-06 01:57:32 +0000	[diff] [blame]	1010	<p>If the <tt>llvm.gcroot</tt> intrinsic is eliminated before code generation by
				1011	a custom lowering pass, LLVM will compute an empty stack map. This may be useful
				1012	for collector plugins which implement reference counting or a shadow stack.</p>
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1013
				1014	</div>
				1015
				1016
				1017	<!-- ======================================================================= -->
				1018	<div class="doc_subsection">
				1019	<a name="init-roots">Initializing roots to null: <tt>InitRoots</tt></a>
				1020	</div>
				1021
				1022	<div class="doc_text">
				1023
				1024	<blockquote><pre
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	1025	>MyGC::MyGC() {
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1026	InitRoots = true;
				1027	}</pre></blockquote>
				1028
				1029	<p>When set, LLVM will automatically initialize each root to <tt>null</tt> upon
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	1030	entry to the function. This prevents the GC's sweep phase from visiting
				1031	uninitialized pointers, which will almost certainly cause it to crash. This
				1032	initialization occurs before custom lowering, so the two may be used
				1033	together.</p>
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1034
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	1035	<p>Since LLVM does not yet compute liveness information, there is no means of
				1036	distinguishing an uninitialized stack root from an initialized one. Therefore,
				1037	this feature should be used by all GC plugins. It is enabled by default.</p>
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1038
				1039	</div>
				1040
				1041
				1042	<!-- ======================================================================= -->
				1043	<div class="doc_subsection">
				1044	<a name="custom">Custom lowering of intrinsics: <tt>CustomRoots</tt>,
				1045	<tt>CustomReadBarriers</tt>, and <tt>CustomWriteBarriers</tt></a>
				1046	</div>
				1047
				1048	<div class="doc_text">
				1049
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	1050	<p>For GCs which use barriers or unusual treatment of stack roots, these
				1051	flags allow the collector to perform arbitrary transformations of the LLVM
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1052	IR:</p>
				1053
				1054	<blockquote><pre
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	1055	>class MyGC : public GCStrategy {
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1056	public:
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	1057	MyGC() {
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1058	CustomRoots = true;
				1059	CustomReadBarriers = true;
				1060	CustomWriteBarriers = true;
				1061	}
				1062
Gordon Henriksen	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	1063	virtual bool initializeCustomLowering(Module &M);
				1064	virtual bool performCustomLowering(Function &F);
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1065	};</pre></blockquote>
				1066
				1067	<p>If any of these flags are set, then LLVM suppresses its default lowering for
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	1068	the corresponding intrinsics and instead calls
				1069	<tt>performCustomLowering</tt>.</p>
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1070
				1071	<p>LLVM's default action for each intrinsic is as follows:</p>
				1072
				1073	<ul>
Gordon Henriksen	e5abac4	2009-03-06 01:57:32 +0000	[diff] [blame]	1074	<li><tt>llvm.gcroot</tt>: Leave it alone. The code generator must see it
				1075	or the stack map will not be computed.</li>
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1076	<li><tt>llvm.gcread</tt>: Substitute a <tt>load</tt> instruction.</li>
				1077	<li><tt>llvm.gcwrite</tt>: Substitute a <tt>store</tt> instruction.</li>
				1078	</ul>
				1079
				1080	<p>If <tt>CustomReadBarriers</tt> or <tt>CustomWriteBarriers</tt> are specified,
Gordon Henriksen	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	1081	then <tt>performCustomLowering</tt> <strong>must</strong> eliminate the
				1082	corresponding barriers.</p>
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1083
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	1084	<p><tt>performCustomLowering</tt> must comply with the same restrictions as <a
				1085	href="WritingAnLLVMPass.html#runOnFunction"><tt
				1086	>FunctionPass::runOnFunction</tt></a>.
				1087	Likewise, <tt>initializeCustomLowering</tt> has the same semantics as <a
				1088	href="WritingAnLLVMPass.html#doInitialization_mod"><tt
				1089	>Pass::doInitialization(Module&)</tt></a>.</p>
Gordon Henriksen	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	1090
				1091	<p>The following can be used as a template:</p>
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1092
				1093	<blockquote><pre
Gordon Henriksen	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	1094	>#include "llvm/Module.h"
Gordon Henriksen	0adede0	2007-12-22 23:32:32 +0000	[diff] [blame]	1095	#include "llvm/IntrinsicInst.h"
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1096
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	1097	bool MyGC::initializeCustomLowering(Module &M) {
Gordon Henriksen	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	1098	return false;
				1099	}
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1100
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	1101	bool MyGC::performCustomLowering(Function &F) {
Gordon Henriksen	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	1102	bool MadeChange = false;
				1103
				1104	for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
Gordon Henriksen	74f4ded	2007-12-22 23:34:26 +0000	[diff] [blame]	1105	for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; )
				1106	if (IntrinsicInst *CI = dyn_cast<IntrinsicInst>(II++))
Gordon Henriksen	0adede0	2007-12-22 23:32:32 +0000	[diff] [blame]	1107	if (Function *F = CI->getCalledFunction())
				1108	switch (F->getIntrinsicID()) {
				1109	case Intrinsic::gcwrite:
Gordon Henriksen	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	1110	// Handle llvm.gcwrite.
Gordon Henriksen	0adede0	2007-12-22 23:32:32 +0000	[diff] [blame]	1111	CI->eraseFromParent();
Gordon Henriksen	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	1112	MadeChange = true;
Gordon Henriksen	0adede0	2007-12-22 23:32:32 +0000	[diff] [blame]	1113	break;
				1114	case Intrinsic::gcread:
Gordon Henriksen	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	1115	// Handle llvm.gcread.
Gordon Henriksen	0adede0	2007-12-22 23:32:32 +0000	[diff] [blame]	1116	CI->eraseFromParent();
Gordon Henriksen	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	1117	MadeChange = true;
Gordon Henriksen	0adede0	2007-12-22 23:32:32 +0000	[diff] [blame]	1118	break;
				1119	case Intrinsic::gcroot:
Gordon Henriksen	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	1120	// Handle llvm.gcroot.
Gordon Henriksen	0adede0	2007-12-22 23:32:32 +0000	[diff] [blame]	1121	CI->eraseFromParent();
Gordon Henriksen	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	1122	MadeChange = true;
Gordon Henriksen	0adede0	2007-12-22 23:32:32 +0000	[diff] [blame]	1123	break;
Gordon Henriksen	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	1124	}
				1125
				1126	return MadeChange;
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1127	}</pre></blockquote>
				1128
				1129	</div>
				1130
				1131
				1132	<!-- ======================================================================= -->
				1133	<div class="doc_subsection">
				1134	<a name="safe-points">Generating safe points: <tt>NeededSafePoints</tt></a>
				1135	</div>
				1136
				1137	<div class="doc_text">
				1138
				1139	<p>LLVM can compute four kinds of safe points:</p>
				1140
				1141	<blockquote><pre
				1142	>namespace GC {
				1143	/// PointKind - The type of a collector-safe point.
				1144	///
				1145	enum PointKind {
				1146	Loop, //< Instr is a loop (backwards branch).
				1147	Return, //< Instr is a return instruction.
				1148	PreCall, //< Instr is a call instruction.
				1149	PostCall //< Instr is the return address of a call.
				1150	};
				1151	}</pre></blockquote>
				1152
				1153	<p>A collector can request any combination of the four by setting the
				1154	<tt>NeededSafePoints</tt> mask:</p>
				1155
				1156	<blockquote><pre
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	1157	>MyGC::MyGC() {
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1158	NeededSafePoints = 1 << GC::Loop
				1159	\| 1 << GC::Return
				1160	\| 1 << GC::PreCall
				1161	\| 1 << GC::PostCall;
				1162	}</pre></blockquote>
				1163
				1164	<p>It can then use the following routines to access safe points.</p>
				1165
Gordon Henriksen	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	1166	<blockquote><pre
				1167	>for (iterator I = begin(), E = end(); I != E; ++I) {
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	1168	GCFunctionInfo MD = I;
Gordon Henriksen	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	1169	size_t PointCount = MD->size();
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1170
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	1171	for (GCFunctionInfo::iterator PI = MD->begin(),
				1172	PE = MD->end(); PI != PE; ++PI) {
Gordon Henriksen	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	1173	GC::PointKind PointKind = PI->Kind;
				1174	unsigned PointNum = PI->Num;
				1175	}
				1176	}
				1177	</pre></blockquote>
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1178
				1179	<p>Almost every collector requires <tt>PostCall</tt> safe points, since these
				1180	correspond to the moments when the function is suspended during a call to a
				1181	subroutine.</p>
				1182
				1183	<p>Threaded programs generally require <tt>Loop</tt> safe points to guarantee
				1184	that the application will reach a safe point within a bounded amount of time,
				1185	even if it is executing a long-running loop which contains no function
				1186	calls.</p>
				1187
				1188	<p>Threaded collectors may also require <tt>Return</tt> and <tt>PreCall</tt>
				1189	safe points to implement "stop the world" techniques using self-modifying code,
				1190	where it is important that the program not exit the function without reaching a
				1191	safe point (because only the topmost function has been patched).</p>
				1192
				1193	</div>
				1194
				1195
				1196	<!-- ======================================================================= -->
				1197	<div class="doc_subsection">
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	1198	<a name="assembly">Emitting assembly code: <tt>GCMetadataPrinter</tt></a>
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1199	</div>
				1200
				1201	<div class="doc_text">
				1202
Gordon Henriksen	e5abac4	2009-03-06 01:57:32 +0000	[diff] [blame]	1203	<p>LLVM allows a plugin to print arbitrary assembly code before and after the
				1204	rest of a module's assembly code. At the end of the module, the GC can compile
				1205	the LLVM stack map into assembly code. (At the beginning, this information is not
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	1206	yet computed.)</p>
				1207
				1208	<p>Since AsmWriter and CodeGen are separate components of LLVM, a separate
				1209	abstract base class and registry is provided for printing assembly code, the
Gordon Henriksen	c9c0b59	2009-03-02 03:47:20 +0000	[diff] [blame]	1210	<tt>GCMetadaPrinter</tt> and <tt>GCMetadataPrinterRegistry</tt>. The AsmWriter
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	1211	will look for such a subclass if the <tt>GCStrategy</tt> sets
				1212	<tt>UsesMetadata</tt>:</p>
				1213
				1214	<blockquote><pre
				1215	>MyGC::MyGC() {
				1216	UsesMetadata = true;
				1217	}</pre></blockquote>
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1218
Gordon Henriksen	e5abac4	2009-03-06 01:57:32 +0000	[diff] [blame]	1219	<p>This separation allows JIT-only clients to be smaller.</p>
				1220
Gordon Henriksen	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	1221	<p>Note that LLVM does not currently have analogous APIs to support code
				1222	generation in the JIT, nor using the object writers.</p>
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1223
				1224	<blockquote><pre
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	1225	>// lib/MyGC/MyGCPrinter.cpp - Example LLVM GC printer
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1226
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	1227	#include "llvm/CodeGen/GCMetadataPrinter.h"
				1228	#include "llvm/Support/Compiler.h"
				1229
				1230	using namespace llvm;
				1231
				1232	namespace {
				1233	class VISIBILITY_HIDDEN MyGCPrinter : public GCMetadataPrinter {
				1234	public:
				1235	virtual void beginAssembly(std::ostream &OS, AsmPrinter &AP,
				1236	const TargetAsmInfo &TAI);
				1237
				1238	virtual void finishAssembly(std::ostream &OS, AsmPrinter &AP,
				1239	const TargetAsmInfo &TAI);
				1240	};
				1241
				1242	GCMetadataPrinterRegistry::Add<MyGCPrinter>
				1243	X("mygc", "My bespoke garbage collector.");
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1244	}</pre></blockquote>
				1245
				1246	<p>The collector should use <tt>AsmPrinter</tt> and <tt>TargetAsmInfo</tt> to
Gordon Henriksen	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	1247	print portable assembly code to the <tt>std::ostream</tt>. The collector itself
				1248	contains the stack map for the entire module, and may access the
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	1249	<tt>GCFunctionInfo</tt> using its own <tt>begin()</tt> and <tt>end()</tt>
Gordon Henriksen	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	1250	methods. Here's a realistic example:</p>
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1251
				1252	<blockquote><pre
				1253	>#include "llvm/CodeGen/AsmPrinter.h"
				1254	#include "llvm/Function.h"
Gordon Henriksen	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	1255	#include "llvm/Target/TargetMachine.h"
				1256	#include "llvm/Target/TargetData.h"
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1257	#include "llvm/Target/TargetAsmInfo.h"
				1258
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	1259	void MyGCPrinter::beginAssembly(std::ostream &OS, AsmPrinter &AP,
Gordon Henriksen	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	1260	const TargetAsmInfo &TAI) {
				1261	// Nothing to do.
				1262	}
				1263
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	1264	void MyGCPrinter::finishAssembly(std::ostream &OS, AsmPrinter &AP,
Gordon Henriksen	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	1265	const TargetAsmInfo &TAI) {
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1266	// Set up for emitting addresses.
				1267	const char *AddressDirective;
				1268	int AddressAlignLog;
Gordon Henriksen	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	1269	if (AP.TM.getTargetData()->getPointerSize() == sizeof(int32_t)) {
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1270	AddressDirective = TAI.getData32bitsDirective();
				1271	AddressAlignLog = 2;
				1272	} else {
				1273	AddressDirective = TAI.getData64bitsDirective();
				1274	AddressAlignLog = 3;
				1275	}
				1276
				1277	// Put this in the data section.
				1278	AP.SwitchToDataSection(TAI.getDataSection());
				1279
				1280	// For each function...
Gordon Henriksen	ad93c4f	2007-12-11 00:30:17 +0000	[diff] [blame]	1281	for (iterator FI = begin(), FE = end(); FI != FE; ++FI) {
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	1282	GCFunctionInfo &MD = **FI;
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1283
				1284	// Emit this data structure:
				1285	//
				1286	// struct {
				1287	// int32_t PointCount;
				1288	// struct {
				1289	// void *SafePointAddress;
				1290	// int32_t LiveCount;
				1291	// int32_t LiveOffsets[LiveCount];
				1292	// } Points[PointCount];
				1293	// } __gcmap_<FUNCTIONNAME>;
				1294
				1295	// Align to address width.
				1296	AP.EmitAlignment(AddressAlignLog);
				1297
Gordon Henriksen	e5abac4	2009-03-06 01:57:32 +0000	[diff] [blame]	1298	// Emit the symbol by which the stack map entry can be found.
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1299	std::string Symbol;
				1300	Symbol += TAI.getGlobalPrefix();
				1301	Symbol += "__gcmap_";
				1302	Symbol += MD.getFunction().getName();
				1303	if (const char *GlobalDirective = TAI.getGlobalDirective())
				1304	OS << GlobalDirective << Symbol << "\n";
				1305	OS << TAI.getGlobalPrefix() << Symbol << ":\n";
				1306
				1307	// Emit PointCount.
				1308	AP.EmitInt32(MD.size());
				1309	AP.EOL("safe point count");
				1310
				1311	// And each safe point...
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	1312	for (GCFunctionInfo::iterator PI = MD.begin(),
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1313	PE = MD.end(); PI != PE; ++PI) {
				1314	// Align to address width.
				1315	AP.EmitAlignment(AddressAlignLog);
				1316
				1317	// Emit the address of the safe point.
				1318	OS << AddressDirective
				1319	<< TAI.getPrivateGlobalPrefix() << "label" << PI->Num;
				1320	AP.EOL("safe point address");
				1321
				1322	// Emit the stack frame size.
				1323	AP.EmitInt32(MD.getFrameSize());
				1324	AP.EOL("stack frame size");
				1325
				1326	// Emit the number of live roots in the function.
				1327	AP.EmitInt32(MD.live_size(PI));
				1328	AP.EOL("live root count");
				1329
				1330	// And for each live root...
Gordon Henriksen	01571ef	2008-08-24 03:18:23 +0000	[diff] [blame]	1331	for (GCFunctionInfo::live_iterator LI = MD.live_begin(PI),
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1332	LE = MD.live_end(PI);
				1333	LI != LE; ++LI) {
				1334	// Print its offset within the stack frame.
				1335	AP.EmitInt32(LI->StackOffset);
				1336	AP.EOL("stack offset");
				1337	}
				1338	}
				1339	}
				1340	}
				1341	</pre></blockquote>
				1342
				1343	</div>
				1344
				1345
				1346	<!-- *********************************************************************** -->
				1347	<div class="doc_section">
Chris Lattner	9b2a184	2004-05-27 05:52:10 +0000	[diff] [blame]	1348	<a name="references">References</a>
				1349	</div>
				1350	<!-- *********************************************************************** -->
				1351
				1352	<div class="doc_text">
				1353
				1354	<p><a name="appel89">[Appel89]</a> Runtime Tags Aren't Necessary. Andrew
				1355	W. Appel. Lisp and Symbolic Computation 19(7):703-705, July 1989.</p>
				1356
				1357	<p><a name="goldberg91">[Goldberg91]</a> Tag-free garbage collection for
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1358	strongly typed programming languages. Benjamin Goldberg. ACM SIGPLAN
Chris Lattner	9b2a184	2004-05-27 05:52:10 +0000	[diff] [blame]	1359	PLDI'91.</p>
				1360
				1361	<p><a name="tolmach94">[Tolmach94]</a> Tag-free garbage collection using
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1362	explicit type parameters. Andrew Tolmach. Proceedings of the 1994 ACM
Chris Lattner	9b2a184	2004-05-27 05:52:10 +0000	[diff] [blame]	1363	conference on LISP and functional programming.</p>
				1364
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1365	<p><a name="henderson02">[Henderson2002]</a> <a
				1366	href="http://citeseer.ist.psu.edu/henderson02accurate.html">
				1367	Accurate Garbage Collection in an Uncooperative Environment</a>.
				1368	Fergus Henderson. International Symposium on Memory Management 2002.</p>
				1369
Chris Lattner	9b2a184	2004-05-27 05:52:10 +0000	[diff] [blame]	1370	</div>
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	1371
Gordon Henriksen	326e24f	2007-09-27 19:31:36 +0000	[diff] [blame]	1372
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	1373	<!-- *********************************************************************** -->
				1374
				1375	<hr>
				1376	<address>
				1377	<a href="http://jigsaw.w3.org/css-validator/check/referer"><img
Misha Brukman	4440870	2008-12-11 17:34:48 +0000	[diff] [blame]	1378	src="http://jigsaw.w3.org/css-validator/images/vcss-blue" alt="Valid CSS"></a>
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	1379	<a href="http://validator.w3.org/check/referer"><img
Misha Brukman	4440870	2008-12-11 17:34:48 +0000	[diff] [blame]	1380	src="http://www.w3.org/Icons/valid-html401-blue" alt="Valid HTML 4.01"></a>
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	1381
				1382	<a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
Reid Spencer	05fe4b0	2006-03-14 05:39:39 +0000	[diff] [blame]	1383	<a href="http://llvm.org">LLVM Compiler Infrastructure</a><br>
Chris Lattner	0d8c2db	2004-05-23 21:02:20 +0000	[diff] [blame]	1384	Last modified: $Date$
				1385	</address>
				1386
				1387	</body>
				1388	</html>