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

blob: bc99fb24928ae975652cee4dc5841adae196c35b [file] [log] [blame]

Chris Lattner	ce52b7e	2004-06-01 06:48:00 +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>
				5	<title>The LLVM Target-Independent Code Generator</title>
				6	<link rel="stylesheet" href="llvm.css" type="text/css">
				7	</head>
				8	<body>
				9
				10	<div class="doc_title">
				11	The LLVM Target-Independent Code Generator
				12	</div>
				13
				14	<ol>
				15	<li><a href="#introduction">Introduction</a>
				16	<ul>
				17	<li><a href="#required">Required components in the code generator</a></li>
Chris Lattner	e35d3bb	2005-10-16 00:36:38 +0000	[diff] [blame]	18	<li><a href="#high-level-design">The high-level design of the code
				19	generator</a></li>
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	20	<li><a href="#tablegen">Using TableGen for target description</a></li>
				21	</ul>
				22	</li>
				23	<li><a href="#targetdesc">Target description classes</a>
				24	<ul>
				25	<li><a href="#targetmachine">The <tt>TargetMachine</tt> class</a></li>
				26	<li><a href="#targetdata">The <tt>TargetData</tt> class</a></li>
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	27	<li><a href="#targetlowering">The <tt>TargetLowering</tt> class</a></li>
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	28	<li><a href="#mregisterinfo">The <tt>MRegisterInfo</tt> class</a></li>
				29	<li><a href="#targetinstrinfo">The <tt>TargetInstrInfo</tt> class</a></li>
				30	<li><a href="#targetframeinfo">The <tt>TargetFrameInfo</tt> class</a></li>
Chris Lattner	47adebb	2005-10-16 17:06:07 +0000	[diff] [blame]	31	<li><a href="#targetsubtarget">The <tt>TargetSubtarget</tt> class</a></li>
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	32	<li><a href="#targetjitinfo">The <tt>TargetJITInfo</tt> class</a></li>
				33	</ul>
				34	</li>
				35	<li><a href="#codegendesc">Machine code description classes</a>
Chris Lattner	ec94f80	2004-06-04 00:16:02 +0000	[diff] [blame]	36	<ul>
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	37	<li><a href="#machineinstr">The <tt>MachineInstr</tt> class</a></li>
Chris Lattner	32e89f2	2005-10-16 18:31:08 +0000	[diff] [blame]	38	<li><a href="#machinebasicblock">The <tt>MachineBasicBlock</tt>
				39	class</a></li>
				40	<li><a href="#machinefunction">The <tt>MachineFunction</tt> class</a></li>
Chris Lattner	ec94f80	2004-06-04 00:16:02 +0000	[diff] [blame]	41	</ul>
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	42	</li>
				43	<li><a href="#codegenalgs">Target-independent code generation algorithms</a>
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	44	<ul>
				45	<li><a href="#instselect">Instruction Selection</a>
				46	<ul>
				47	<li><a href="#selectiondag_intro">Introduction to SelectionDAGs</a></li>
				48	<li><a href="#selectiondag_process">SelectionDAG Code Generation
				49	Process</a></li>
				50	<li><a href="#selectiondag_build">Initial SelectionDAG
				51	Construction</a></li>
				52	<li><a href="#selectiondag_legalize">SelectionDAG Legalize Phase</a></li>
				53	<li><a href="#selectiondag_optimize">SelectionDAG Optimization
Chris Lattner	e35d3bb	2005-10-16 00:36:38 +0000	[diff] [blame]	54	Phase: the DAG Combiner</a></li>
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	55	<li><a href="#selectiondag_select">SelectionDAG Select Phase</a></li>
Chris Lattner	32e89f2	2005-10-16 18:31:08 +0000	[diff] [blame]	56	<li><a href="#selectiondag_sched">SelectionDAG Scheduling and Formation
Chris Lattner	e35d3bb	2005-10-16 00:36:38 +0000	[diff] [blame]	57	Phase</a></li>
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	58	<li><a href="#selectiondag_future">Future directions for the
				59	SelectionDAG</a></li>
				60	</ul></li>
Chris Lattner	32e89f2	2005-10-16 18:31:08 +0000	[diff] [blame]	61	<li><a href="#codeemit">Code Emission</a>
				62	<ul>
				63	<li><a href="#codeemit_asm">Generating Assembly Code</a></li>
				64	<li><a href="#codeemit_bin">Generating Binary Machine Code</a></li>
				65	</ul></li>
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	66	</ul>
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	67	</li>
Chris Lattner	32e89f2	2005-10-16 18:31:08 +0000	[diff] [blame]	68	<li><a href="#targetimpls">Target-specific Implementation Notes</a>
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	69	<ul>
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	70	<li><a href="#x86">The X86 backend</a></li>
Chris Lattner	10d6800	2004-06-01 17:18:11 +0000	[diff] [blame]	71	</ul>
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	72	</li>
				73
				74	</ol>
				75
				76	<div class="doc_author">
				77	<p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p>
				78	</div>
				79
Chris Lattner	10d6800	2004-06-01 17:18:11 +0000	[diff] [blame]	80	<div class="doc_warning">
				81	<p>Warning: This is a work in progress.</p>
				82	</div>
				83
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	84	<!-- *********************************************************************** -->
				85	<div class="doc_section">
				86	<a name="introduction">Introduction</a>
				87	</div>
				88	<!-- *********************************************************************** -->
				89
				90	<div class="doc_text">
				91
				92	<p>The LLVM target-independent code generator is a framework that provides a
				93	suite of reusable components for translating the LLVM internal representation to
				94	the machine code for a specified target -- either in assembly form (suitable for
				95	a static compiler) or in binary machine code format (usable for a JIT compiler).
Chris Lattner	ec94f80	2004-06-04 00:16:02 +0000	[diff] [blame]	96	The LLVM target-independent code generator consists of five main components:</p>
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	97
				98	<ol>
				99	<li><a href="#targetdesc">Abstract target description</a> interfaces which
Reid Spencer	bdbcb8a	2004-06-05 14:39:24 +0000	[diff] [blame]	100	capture important properties about various aspects of the machine, independently
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	101	of how they will be used. These interfaces are defined in
				102	<tt>include/llvm/Target/</tt>.</li>
				103
				104	<li>Classes used to represent the <a href="#codegendesc">machine code</a> being
Reid Spencer	bdbcb8a	2004-06-05 14:39:24 +0000	[diff] [blame]	105	generated for a target. These classes are intended to be abstract enough to
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	106	represent the machine code for <i>any</i> target machine. These classes are
				107	defined in <tt>include/llvm/CodeGen/</tt>.</li>
				108
				109	<li><a href="#codegenalgs">Target-independent algorithms</a> used to implement
				110	various phases of native code generation (register allocation, scheduling, stack
				111	frame representation, etc). This code lives in <tt>lib/CodeGen/</tt>.</li>
				112
				113	<li><a href="#targetimpls">Implementations of the abstract target description
				114	interfaces</a> for particular targets. These machine descriptions make use of
				115	the components provided by LLVM, and can optionally provide custom
				116	target-specific passes, to build complete code generators for a specific target.
				117	Target descriptions live in <tt>lib/Target/</tt>.</li>
				118
Chris Lattner	ec94f80	2004-06-04 00:16:02 +0000	[diff] [blame]	119	<li><a href="#jit">The target-independent JIT components</a>. The LLVM JIT is
				120	completely target independent (it uses the <tt>TargetJITInfo</tt> structure to
				121	interface for target-specific issues. The code for the target-independent
				122	JIT lives in <tt>lib/ExecutionEngine/JIT</tt>.</li>
				123
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	124	</ol>
				125
				126	<p>
				127	Depending on which part of the code generator you are interested in working on,
				128	different pieces of this will be useful to you. In any case, you should be
				129	familiar with the <a href="#targetdesc">target description</a> and <a
				130	href="#codegendesc">machine code representation</a> classes. If you want to add
Reid Spencer	bdbcb8a	2004-06-05 14:39:24 +0000	[diff] [blame]	131	a backend for a new target, you will need to <a href="#targetimpls">implement the
				132	target description</a> classes for your new target and understand the <a
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	133	href="LangRef.html">LLVM code representation</a>. If you are interested in
				134	implementing a new <a href="#codegenalgs">code generation algorithm</a>, it
				135	should only depend on the target-description and machine code representation
				136	classes, ensuring that it is portable.
				137	</p>
				138
				139	</div>
				140
				141	<!-- ======================================================================= -->
				142	<div class="doc_subsection">
				143	<a name="required">Required components in the code generator</a>
				144	</div>
				145
				146	<div class="doc_text">
				147
				148	<p>The two pieces of the LLVM code generator are the high-level interface to the
				149	code generator and the set of reusable components that can be used to build
				150	target-specific backends. The two most important interfaces (<a
				151	href="#targetmachine"><tt>TargetMachine</tt></a> and <a
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	152	href="#targetdata"><tt>TargetData</tt></a>) are the only ones that are
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	153	required to be defined for a backend to fit into the LLVM system, but the others
				154	must be defined if the reusable code generator components are going to be
				155	used.</p>
				156
				157	<p>This design has two important implications. The first is that LLVM can
				158	support completely non-traditional code generation targets. For example, the C
				159	backend does not require register allocation, instruction selection, or any of
				160	the other standard components provided by the system. As such, it only
				161	implements these two interfaces, and does its own thing. Another example of a
				162	code generator like this is a (purely hypothetical) backend that converts LLVM
				163	to the GCC RTL form and uses GCC to emit machine code for a target.</p>
				164
Reid Spencer	bdbcb8a	2004-06-05 14:39:24 +0000	[diff] [blame]	165	<p>This design also implies that it is possible to design and
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	166	implement radically different code generators in the LLVM system that do not
				167	make use of any of the built-in components. Doing so is not recommended at all,
				168	but could be required for radically different targets that do not fit into the
				169	LLVM machine description model: programmable FPGAs for example.</p>
Chris Lattner	900bf8c	2004-06-02 07:06:06 +0000	[diff] [blame]	170
				171	<p><b>Important Note:</b> For historical reasons, the LLVM SparcV9 code
				172	generator uses almost entirely different code paths than described in this
				173	document. For this reason, there are some deprecated interfaces (such as
Chris Lattner	32e89f2	2005-10-16 18:31:08 +0000	[diff] [blame]	174	<tt>TargetSchedInfo</tt>), which are only used by the
Chris Lattner	900bf8c	2004-06-02 07:06:06 +0000	[diff] [blame]	175	V9 backend and should not be used by any other targets. Also, all code in the
				176	<tt>lib/Target/SparcV9</tt> directory and subdirectories should be considered
				177	deprecated, and should not be used as the basis for future code generator work.
Misha Brukman	f3709d6	2004-06-03 16:55:57 +0000	[diff] [blame]	178	The SparcV9 backend is slowly being merged into the rest of the
				179	target-independent code generators, but this is a low-priority process with no
Chris Lattner	900bf8c	2004-06-02 07:06:06 +0000	[diff] [blame]	180	predictable completion date.</p>
				181
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	182	</div>
				183
				184	<!-- ======================================================================= -->
				185	<div class="doc_subsection">
Chris Lattner	10d6800	2004-06-01 17:18:11 +0000	[diff] [blame]	186	<a name="high-level-design">The high-level design of the code generator</a>
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	187	</div>
				188
				189	<div class="doc_text">
				190
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	191	<p>The LLVM target-independent code generator is designed to support efficient and
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	192	quality code generation for standard register-based microprocessors. Code
				193	generation in this model is divided into the following stages:</p>
				194
				195	<ol>
Chris Lattner	32e89f2	2005-10-16 18:31:08 +0000	[diff] [blame]	196	<li><b><a href="#instselect">Instruction Selection</a></b> - This phase
				197	determines an efficient way to express the input LLVM code in the target
				198	instruction set.
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	199	This stage produces the initial code for the program in the target instruction
				200	set, then makes use of virtual registers in SSA form and physical registers that
				201	represent any required register assignments due to target constraints or calling
Chris Lattner	32e89f2	2005-10-16 18:31:08 +0000	[diff] [blame]	202	conventions. This step turns the LLVM code into a DAG of target
				203	instructions.</li>
				204
				205	<li><b><a href="#selectiondag_sched">Scheduling and Formation</a></b> - This
				206	phase takes the DAG of target instructions produced by the instruction selection
				207	phase, determines an ordering of the instructions, then emits the instructions
				208	as <tt><a href="#machineinstr">MachineInstr</a></tt>s with that ordering.
				209	</li>
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	210
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	211	<li><b><a href="#ssamco">SSA-based Machine Code Optimizations</a></b> - This
				212	optional stage consists of a series of machine-code optimizations that
				213	operate on the SSA-form produced by the instruction selector. Optimizations
Chris Lattner	32e89f2	2005-10-16 18:31:08 +0000	[diff] [blame]	214	like modulo-scheduling or peephole optimization work here.
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	215	</li>
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	216
Chris Lattner	32e89f2	2005-10-16 18:31:08 +0000	[diff] [blame]	217	<li><b><a href="#regalloc">Register Allocation</a></b> - The
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	218	target code is transformed from an infinite virtual register file in SSA form
				219	to the concrete register file used by the target. This phase introduces spill
				220	code and eliminates all virtual register references from the program.</li>
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	221
Chris Lattner	32e89f2	2005-10-16 18:31:08 +0000	[diff] [blame]	222	<li><b><a href="#proepicode">Prolog/Epilog Code Insertion</a></b> - Once the
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	223	machine code has been generated for the function and the amount of stack space
				224	required is known (used for LLVM alloca's and spill slots), the prolog and
				225	epilog code for the function can be inserted and "abstract stack location
				226	references" can be eliminated. This stage is responsible for implementing
				227	optimizations like frame-pointer elimination and stack packing.</li>
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	228
Chris Lattner	32e89f2	2005-10-16 18:31:08 +0000	[diff] [blame]	229	<li><b><a href="#latemco">Late Machine Code Optimizations</a></b> - Optimizations
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	230	that operate on "final" machine code can go here, such as spill code scheduling
				231	and peephole optimizations.</li>
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	232
Chris Lattner	32e89f2	2005-10-16 18:31:08 +0000	[diff] [blame]	233	<li><b><a href="#codeemit">Code Emission</a></b> - The final stage actually
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	234	puts out the code for the current function, either in the target assembler
				235	format or in machine code.</li>
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	236
				237	</ol>
				238
				239	<p>
				240	The code generator is based on the assumption that the instruction selector will
				241	use an optimal pattern matching selector to create high-quality sequences of
Reid Spencer	bdbcb8a	2004-06-05 14:39:24 +0000	[diff] [blame]	242	native instructions. Alternative code generator designs based on pattern
				243	expansion and
				244	aggressive iterative peephole optimization are much slower. This design
				245	permits efficient compilation (important for JIT environments) and
				246	aggressive optimization (used when generating code offline) by allowing
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	247	components of varying levels of sophistication to be used for any step of
Reid Spencer	bdbcb8a	2004-06-05 14:39:24 +0000	[diff] [blame]	248	compilation.</p>
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	249
				250	<p>
				251	In addition to these stages, target implementations can insert arbitrary
				252	target-specific passes into the flow. For example, the X86 target uses a
				253	special pass to handle the 80x87 floating point stack architecture. Other
				254	targets with unusual requirements can be supported with custom passes as needed.
				255	</p>
				256
				257	</div>
				258
				259
				260	<!-- ======================================================================= -->
				261	<div class="doc_subsection">
Chris Lattner	10d6800	2004-06-01 17:18:11 +0000	[diff] [blame]	262	<a name="tablegen">Using TableGen for target description</a>
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	263	</div>
				264
				265	<div class="doc_text">
				266
Chris Lattner	5489e93	2004-06-01 18:35:00 +0000	[diff] [blame]	267	<p>The target description classes require a detailed description of the target
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	268	architecture. These target descriptions often have a large amount of common
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	269	information (e.g., an <tt>add</tt> instruction is almost identical to a
				270	<tt>sub</tt> instruction).
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	271	In order to allow the maximum amount of commonality to be factored out, the LLVM
				272	code generator uses the <a href="TableGenFundamentals.html">TableGen</a> tool to
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	273	describe big chunks of the target machine, which allows the use of
				274	domain-specific and target-specific abstractions to reduce the amount of
				275	repetition.
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	276	</p>
				277
Chris Lattner	32e89f2	2005-10-16 18:31:08 +0000	[diff] [blame]	278	<p>As LLVM continues to be developed and refined, we plan to move more and more
				279	of the target description to be in <tt>.td</tt> form. Doing so gives us a
				280	number of advantages. The most important is that it makes it easier to port
				281	LLVM, because it reduces the amount of C++ code that has to be written and the
				282	surface area of the code generator that needs to be understood before someone
				283	can get in an get something working. Second, it is also important to us because
				284	it makes it easier to change things: in particular, if tables and other things
				285	are all emitted by tblgen, we only need to change one place (tblgen) to update
				286	all of the targets to a new interface.</p>
				287
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	288	</div>
				289
				290	<!-- *********************************************************************** -->
				291	<div class="doc_section">
				292	<a name="targetdesc">Target description classes</a>
				293	</div>
				294	<!-- *********************************************************************** -->
				295
				296	<div class="doc_text">
				297
				298	<p>The LLVM target description classes (which are located in the
				299	<tt>include/llvm/Target</tt> directory) provide an abstract description of the
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	300	target machine; independent of any particular client. These classes are
				301	designed to capture the <i>abstract</i> properties of the target (such as the
				302	instructions and registers it has), and do not incorporate any particular pieces
Chris Lattner	32e89f2	2005-10-16 18:31:08 +0000	[diff] [blame]	303	of code generation algorithms.</p>
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	304
				305	<p>All of the target description classes (except the <tt><a
				306	href="#targetdata">TargetData</a></tt> class) are designed to be subclassed by
				307	the concrete target implementation, and have virtual methods implemented. To
Reid Spencer	bdbcb8a	2004-06-05 14:39:24 +0000	[diff] [blame]	308	get to these implementations, the <tt><a
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	309	href="#targetmachine">TargetMachine</a></tt> class provides accessors that
				310	should be implemented by the target.</p>
				311
				312	</div>
				313
				314	<!-- ======================================================================= -->
				315	<div class="doc_subsection">
				316	<a name="targetmachine">The <tt>TargetMachine</tt> class</a>
				317	</div>
				318
				319	<div class="doc_text">
				320
				321	<p>The <tt>TargetMachine</tt> class provides virtual methods that are used to
				322	access the target-specific implementations of the various target description
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	323	classes via the <tt>get*Info</tt> methods (<tt>getInstrInfo</tt>,
				324	<tt>getRegisterInfo</tt>, <tt>getFrameInfo</tt>, etc.). This class is
				325	designed to be specialized by
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	326	a concrete target implementation (e.g., <tt>X86TargetMachine</tt>) which
				327	implements the various virtual methods. The only required target description
				328	class is the <a href="#targetdata"><tt>TargetData</tt></a> class, but if the
				329	code generator components are to be used, the other interfaces should be
				330	implemented as well.</p>
				331
				332	</div>
				333
				334
				335	<!-- ======================================================================= -->
				336	<div class="doc_subsection">
				337	<a name="targetdata">The <tt>TargetData</tt> class</a>
				338	</div>
				339
				340	<div class="doc_text">
				341
				342	<p>The <tt>TargetData</tt> class is the only required target description class,
Chris Lattner	32e89f2	2005-10-16 18:31:08 +0000	[diff] [blame]	343	and it is the only class that is not extensible (you cannot derived a new
				344	class from it). <tt>TargetData</tt> specifies information about how the target
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	345	lays out memory for structures, the alignment requirements for various data
				346	types, the size of pointers in the target, and whether the target is
				347	little-endian or big-endian.</p>
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	348
				349	</div>
				350
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	351	<!-- ======================================================================= -->
				352	<div class="doc_subsection">
				353	<a name="targetlowering">The <tt>TargetLowering</tt> class</a>
				354	</div>
				355
				356	<div class="doc_text">
				357
				358	<p>The <tt>TargetLowering</tt> class is used by SelectionDAG based instruction
				359	selectors primarily to describe how LLVM code should be lowered to SelectionDAG
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	360	operations. Among other things, this class indicates:
Chris Lattner	32e89f2	2005-10-16 18:31:08 +0000	[diff] [blame]	361	<ul><li>an initial register class to use for various ValueTypes</li>
				362	<li>which operations are natively supported by the target machine</li>
				363	<li>the return type of setcc operations</li>
				364	<li>the type to use for shift amounts</li>
				365	<li>various high-level characteristics, like whether it is profitable to turn
				366	division by a constant into a multiplication sequence</li>
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	367	</ol></p>
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	368
				369	</div>
				370
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	371	<!-- ======================================================================= -->
				372	<div class="doc_subsection">
Chris Lattner	10d6800	2004-06-01 17:18:11 +0000	[diff] [blame]	373	<a name="mregisterinfo">The <tt>MRegisterInfo</tt> class</a>
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	374	</div>
				375
				376	<div class="doc_text">
				377
				378	<p>The <tt>MRegisterInfo</tt> class (which will eventually be renamed to
				379	<tt>TargetRegisterInfo</tt>) is used to describe the register file of the
				380	target and any interactions between the registers.</p>
				381
				382	<p>Registers in the code generator are represented in the code generator by
				383	unsigned numbers. Physical registers (those that actually exist in the target
				384	description) are unique small numbers, and virtual registers are generally
Chris Lattner	32e89f2	2005-10-16 18:31:08 +0000	[diff] [blame]	385	large. Note that register #0 is reserved as a flag value.</p>
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	386
				387	<p>Each register in the processor description has an associated
Chris Lattner	88a06d2	2005-09-30 17:46:55 +0000	[diff] [blame]	388	<tt>TargetRegisterDesc</tt> entry, which provides a textual name for the register
				389	(used for assembly output and debugging dumps) and a set of aliases (used to
				390	indicate that one register overlaps with another).
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	391	</p>
				392
				393	<p>In addition to the per-register description, the <tt>MRegisterInfo</tt> class
				394	exposes a set of processor specific register classes (instances of the
				395	<tt>TargetRegisterClass</tt> class). Each register class contains sets of
				396	registers that have the same properties (for example, they are all 32-bit
				397	integer registers). Each SSA virtual register created by the instruction
				398	selector has an associated register class. When the register allocator runs, it
				399	replaces virtual registers with a physical register in the set.</p>
				400
				401	<p>
				402	The target-specific implementations of these classes is auto-generated from a <a
				403	href="TableGenFundamentals.html">TableGen</a> description of the register file.
				404	</p>
				405
				406	</div>
				407
				408	<!-- ======================================================================= -->
				409	<div class="doc_subsection">
Chris Lattner	10d6800	2004-06-01 17:18:11 +0000	[diff] [blame]	410	<a name="targetinstrinfo">The <tt>TargetInstrInfo</tt> class</a>
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	411	</div>
				412
Reid Spencer	627cd00	2005-07-19 01:36:35 +0000	[diff] [blame]	413	<div class="doc_text">
				414	<p>The <tt>TargetInstrInfo</tt> class is used to describe the machine
				415	instructions supported by the target. It is essentially an array of
				416	<tt>TargetInstrDescriptor</tt> objects, each of which describes one
				417	instruction the target supports. Descriptors define things like the mnemonic
Chris Lattner	a307978	2005-07-19 03:37:48 +0000	[diff] [blame]	418	for the opcode, the number of operands, the list of implicit register uses
				419	and defs, whether the instruction has certain target-independent properties
				420	(accesses memory, is commutable, etc), and holds any target-specific flags.</p>
Reid Spencer	627cd00	2005-07-19 01:36:35 +0000	[diff] [blame]	421	</div>
				422
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	423	<!-- ======================================================================= -->
				424	<div class="doc_subsection">
Chris Lattner	10d6800	2004-06-01 17:18:11 +0000	[diff] [blame]	425	<a name="targetframeinfo">The <tt>TargetFrameInfo</tt> class</a>
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	426	</div>
				427
Reid Spencer	627cd00	2005-07-19 01:36:35 +0000	[diff] [blame]	428	<div class="doc_text">
				429	<p>The <tt>TargetFrameInfo</tt> class is used to provide information about the
				430	stack frame layout of the target. It holds the direction of stack growth,
				431	the known stack alignment on entry to each function, and the offset to the
				432	locals area. The offset to the local area is the offset from the stack
				433	pointer on function entry to the first location where function data (local
				434	variables, spill locations) can be stored.</p>
Reid Spencer	627cd00	2005-07-19 01:36:35 +0000	[diff] [blame]	435	</div>
Chris Lattner	47adebb	2005-10-16 17:06:07 +0000	[diff] [blame]	436
				437	<!-- ======================================================================= -->
				438	<div class="doc_subsection">
				439	<a name="targetsubtarget">The <tt>TargetSubtarget</tt> class</a>
				440	</div>
				441
				442	<div class="doc_text">
				443	<p>
				444	TODO
				445	</p>
				446	</div>
				447
				448
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	449	<!-- ======================================================================= -->
				450	<div class="doc_subsection">
Chris Lattner	10d6800	2004-06-01 17:18:11 +0000	[diff] [blame]	451	<a name="targetjitinfo">The <tt>TargetJITInfo</tt> class</a>
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	452	</div>
				453
				454	<!-- *********************************************************************** -->
				455	<div class="doc_section">
				456	<a name="codegendesc">Machine code description classes</a>
				457	</div>
				458	<!-- *********************************************************************** -->
				459
Chris Lattner	ec94f80	2004-06-04 00:16:02 +0000	[diff] [blame]	460	<div class="doc_text">
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	461
Chris Lattner	ec94f80	2004-06-04 00:16:02 +0000	[diff] [blame]	462	<p>
				463	At the high-level, LLVM code is translated to a machine specific representation
Chris Lattner	32e89f2	2005-10-16 18:31:08 +0000	[diff] [blame]	464	formed out of <a href="#machinefunction">MachineFunction</a>,
				465	<a href="#machinebasicblock">MachineBasicBlock</a>, and <a
Chris Lattner	ec94f80	2004-06-04 00:16:02 +0000	[diff] [blame]	466	href="#machineinstr"><tt>MachineInstr</tt></a> instances
				467	(defined in include/llvm/CodeGen). This representation is completely target
				468	agnostic, representing instructions in their most abstract form: an opcode and a
				469	series of operands. This representation is designed to support both SSA
				470	representation for machine code, as well as a register allocated, non-SSA form.
				471	</p>
				472
				473	</div>
				474
				475	<!-- ======================================================================= -->
				476	<div class="doc_subsection">
				477	<a name="machineinstr">The <tt>MachineInstr</tt> class</a>
				478	</div>
				479
				480	<div class="doc_text">
				481
				482	<p>Target machine instructions are represented as instances of the
				483	<tt>MachineInstr</tt> class. This class is an extremely abstract way of
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	484	representing machine instructions. In particular, it only keeps track of
				485	an opcode number and a set of operands.</p>
Chris Lattner	ec94f80	2004-06-04 00:16:02 +0000	[diff] [blame]	486
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	487	<p>The opcode number is a simple unsigned number that only has meaning to a
Chris Lattner	ec94f80	2004-06-04 00:16:02 +0000	[diff] [blame]	488	specific backend. All of the instructions for a target should be defined in
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	489	the <tt>*InstrInfo.td</tt> file for the target. The opcode enum values
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	490	are auto-generated from this description. The <tt>MachineInstr</tt> class does
				491	not have any information about how to interpret the instruction (i.e., what the
Chris Lattner	ec94f80	2004-06-04 00:16:02 +0000	[diff] [blame]	492	semantics of the instruction are): for that you must refer to the
				493	<tt><a href="#targetinstrinfo">TargetInstrInfo</a></tt> class.</p>
				494
				495	<p>The operands of a machine instruction can be of several different types:
				496	they can be a register reference, constant integer, basic block reference, etc.
				497	In addition, a machine operand should be marked as a def or a use of the value
				498	(though only registers are allowed to be defs).</p>
				499
				500	<p>By convention, the LLVM code generator orders instruction operands so that
				501	all register definitions come before the register uses, even on architectures
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	502	that are normally printed in other orders. For example, the SPARC add
Chris Lattner	ec94f80	2004-06-04 00:16:02 +0000	[diff] [blame]	503	instruction: "<tt>add %i1, %i2, %i3</tt>" adds the "%i1", and "%i2" registers
				504	and stores the result into the "%i3" register. In the LLVM code generator,
				505	the operands should be stored as "<tt>%i3, %i1, %i2</tt>": with the destination
				506	first.</p>
				507
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	508	<p>Keeping destination (definition) operands at the beginning of the operand
				509	list has several advantages. In particular, the debugging printer will print
				510	the instruction like this:</p>
Chris Lattner	ec94f80	2004-06-04 00:16:02 +0000	[diff] [blame]	511
				512	<pre>
				513	%r3 = add %i1, %i2
				514	</pre>
				515
				516	<p>If the first operand is a def, and it is also easier to <a
				517	href="#buildmi">create instructions</a> whose only def is the first
				518	operand.</p>
				519
				520	</div>
				521
				522	<!-- _______________________________________________________________________ -->
				523	<div class="doc_subsubsection">
				524	<a name="buildmi">Using the <tt>MachineInstrBuilder.h</tt> functions</a>
				525	</div>
				526
				527	<div class="doc_text">
				528
				529	<p>Machine instructions are created by using the <tt>BuildMI</tt> functions,
				530	located in the <tt>include/llvm/CodeGen/MachineInstrBuilder.h</tt> file. The
				531	<tt>BuildMI</tt> functions make it easy to build arbitrary machine
				532	instructions. Usage of the <tt>BuildMI</tt> functions look like this:
				533	</p>
				534
				535	<pre>
				536	// Create a 'DestReg = mov 42' (rendered in X86 assembly as 'mov DestReg, 42')
				537	// instruction. The '1' specifies how many operands will be added.
				538	MachineInstr *MI = BuildMI(X86::MOV32ri, 1, DestReg).addImm(42);
				539
				540	// Create the same instr, but insert it at the end of a basic block.
				541	MachineBasicBlock &MBB = ...
				542	BuildMI(MBB, X86::MOV32ri, 1, DestReg).addImm(42);
				543
				544	// Create the same instr, but insert it before a specified iterator point.
				545	MachineBasicBlock::iterator MBBI = ...
				546	BuildMI(MBB, MBBI, X86::MOV32ri, 1, DestReg).addImm(42);
				547
				548	// Create a 'cmp Reg, 0' instruction, no destination reg.
				549	MI = BuildMI(X86::CMP32ri, 2).addReg(Reg).addImm(0);
				550	// Create an 'sahf' instruction which takes no operands and stores nothing.
				551	MI = BuildMI(X86::SAHF, 0);
				552
				553	// Create a self looping branch instruction.
				554	BuildMI(MBB, X86::JNE, 1).addMBB(&MBB);
				555	</pre>
				556
				557	<p>
				558	The key thing to remember with the <tt>BuildMI</tt> functions is that you have
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	559	to specify the number of operands that the machine instruction will take. This
				560	allows for efficient memory allocation. You also need to specify if operands
				561	default to be uses of values, not definitions. If you need to add a definition
				562	operand (other than the optional destination register), you must explicitly
				563	mark it as such.
Chris Lattner	ec94f80	2004-06-04 00:16:02 +0000	[diff] [blame]	564	</p>
				565
				566	</div>
				567
				568	<!-- _______________________________________________________________________ -->
				569	<div class="doc_subsubsection">
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	570	<a name="fixedregs">Fixed (preassigned) registers</a>
Chris Lattner	ec94f80	2004-06-04 00:16:02 +0000	[diff] [blame]	571	</div>
				572
				573	<div class="doc_text">
				574
				575	<p>One important issue that the code generator needs to be aware of is the
				576	presence of fixed registers. In particular, there are often places in the
				577	instruction stream where the register allocator <em>must</em> arrange for a
				578	particular value to be in a particular register. This can occur due to
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	579	limitations of the instruction set (e.g., the X86 can only do a 32-bit divide
Chris Lattner	ec94f80	2004-06-04 00:16:02 +0000	[diff] [blame]	580	with the <tt>EAX</tt>/<tt>EDX</tt> registers), or external factors like calling
				581	conventions. In any case, the instruction selector should emit code that
				582	copies a virtual register into or out of a physical register when needed.</p>
				583
				584	<p>For example, consider this simple LLVM example:</p>
				585
				586	<pre>
				587	int %test(int %X, int %Y) {
				588	%Z = div int %X, %Y
				589	ret int %Z
				590	}
				591	</pre>
				592
				593	<p>The X86 instruction selector produces this machine code for the div
				594	and ret (use
				595	"<tt>llc X.bc -march=x86 -print-machineinstrs</tt>" to get this):</p>
				596
				597	<pre>
				598	;; Start of div
				599	%EAX = mov %reg1024 ;; Copy X (in reg1024) into EAX
				600	%reg1027 = sar %reg1024, 31
				601	%EDX = mov %reg1027 ;; Sign extend X into EDX
				602	idiv %reg1025 ;; Divide by Y (in reg1025)
				603	%reg1026 = mov %EAX ;; Read the result (Z) out of EAX
				604
				605	;; Start of ret
				606	%EAX = mov %reg1026 ;; 32-bit return value goes in EAX
				607	ret
				608	</pre>
				609
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	610	<p>By the end of code generation, the register allocator has coalesced
Chris Lattner	ec94f80	2004-06-04 00:16:02 +0000	[diff] [blame]	611	the registers and deleted the resultant identity moves, producing the
				612	following code:</p>
				613
				614	<pre>
				615	;; X is in EAX, Y is in ECX
				616	mov %EAX, %EDX
				617	sar %EDX, 31
				618	idiv %ECX
				619	ret
				620	</pre>
				621
				622	<p>This approach is extremely general (if it can handle the X86 architecture,
				623	it can handle anything!) and allows all of the target specific
				624	knowledge about the instruction stream to be isolated in the instruction
				625	selector. Note that physical registers should have a short lifetime for good
				626	code generation, and all physical registers are assumed dead on entry and
				627	exit of basic blocks (before register allocation). Thus if you need a value
				628	to be live across basic block boundaries, it <em>must</em> live in a virtual
				629	register.</p>
				630
				631	</div>
				632
				633	<!-- _______________________________________________________________________ -->
				634	<div class="doc_subsubsection">
				635	<a name="ssa">Machine code SSA form</a>
				636	</div>
				637
				638	<div class="doc_text">
				639
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	640	<p><tt>MachineInstr</tt>'s are initially selected in SSA-form, and
Chris Lattner	ec94f80	2004-06-04 00:16:02 +0000	[diff] [blame]	641	are maintained in SSA-form until register allocation happens. For the most
				642	part, this is trivially simple since LLVM is already in SSA form: LLVM PHI nodes
				643	become machine code PHI nodes, and virtual registers are only allowed to have a
				644	single definition.</p>
				645
				646	<p>After register allocation, machine code is no longer in SSA-form, as there
				647	are no virtual registers left in the code.</p>
				648
				649	</div>
				650
Chris Lattner	32e89f2	2005-10-16 18:31:08 +0000	[diff] [blame]	651	<!-- ======================================================================= -->
				652	<div class="doc_subsection">
				653	<a name="machinebasicblock">The <tt>MachineBasicBlock</tt> class</a>
				654	</div>
				655
				656	<div class="doc_text">
				657
				658	<p>The <tt>MachineBasicBlock</tt> class contains a list of machine instructions
				659	(<a href="#machineinstr">MachineInstr</a> instances). It roughly corresponds to
				660	the LLVM code input to the instruction selector, but there can be a one-to-many
				661	mapping (i.e. one LLVM basic block can map to multiple machine basic blocks).
				662	The MachineBasicBlock class has a "<tt>getBasicBlock</tt>" method, which returns
				663	the LLVM basic block that it comes from.
				664	</p>
				665
				666	</div>
				667
				668	<!-- ======================================================================= -->
				669	<div class="doc_subsection">
				670	<a name="machinefunction">The <tt>MachineFunction</tt> class</a>
				671	</div>
				672
				673	<div class="doc_text">
				674
				675	<p>The <tt>MachineFunction</tt> class contains a list of machine basic blocks
				676	(<a href="#machinebasicblock">MachineBasicBlock</a> instances). It corresponds
				677	one-to-one with the LLVM function input to the instruction selector. In
				678	addition to a list of basic blocks, the <tt>MachineFunction</tt> contains a
				679	the MachineConstantPool, MachineFrameInfo, MachineFunctionInfo,
				680	SSARegMap, and a set of live in and live out registers for the function. See
				681	<tt>MachineFunction.h</tt> for more information.
				682	</p>
				683
				684	</div>
				685
				686
				687
Chris Lattner	ec94f80	2004-06-04 00:16:02 +0000	[diff] [blame]	688	<!-- *********************************************************************** -->
				689	<div class="doc_section">
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	690	<a name="codegenalgs">Target-independent code generation algorithms</a>
				691	</div>
				692	<!-- *********************************************************************** -->
				693
				694	<div class="doc_text">
				695
				696	<p>This section documents the phases described in the <a
Chris Lattner	32e89f2	2005-10-16 18:31:08 +0000	[diff] [blame]	697	href="#high-level-design">high-level design of the code generator</a>. It
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	698	explains how they work and some of the rationale behind their design.</p>
				699
				700	</div>
				701
				702	<!-- ======================================================================= -->
				703	<div class="doc_subsection">
				704	<a name="instselect">Instruction Selection</a>
				705	</div>
				706
				707	<div class="doc_text">
				708	<p>
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	709	Instruction Selection is the process of translating LLVM code presented to the
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	710	code generator into target-specific machine instructions. There are several
				711	well-known ways to do this in the literature. In LLVM there are two main forms:
Chris Lattner	e35d3bb	2005-10-16 00:36:38 +0000	[diff] [blame]	712	the SelectionDAG based instruction selector framework and an old-style 'simple'
				713	instruction selector (which effectively peephole selects each LLVM instruction
				714	into a series of machine instructions). We recommend that all targets use the
				715	SelectionDAG infrastructure.
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	716	</p>
				717
Chris Lattner	e35d3bb	2005-10-16 00:36:38 +0000	[diff] [blame]	718	<p>Portions of the DAG instruction selector are generated from the target
				719	description files (<tt>*.td</tt>) files. Eventually, we aim for the entire
				720	instruction selector to be generated from these <tt>.td</tt> files.</p>
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	721	</div>
				722
				723	<!-- _______________________________________________________________________ -->
				724	<div class="doc_subsubsection">
				725	<a name="selectiondag_intro">Introduction to SelectionDAGs</a>
				726	</div>
				727
				728	<div class="doc_text">
				729
				730	<p>
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	731	The SelectionDAG provides an abstraction for code representation in a way that
				732	is amenable to instruction selection using automatic techniques
				733	(e.g. dynamic-programming based optimal pattern matching selectors), It is also
Chris Lattner	7a025c8	2005-10-16 20:02:19 +0000	[diff] [blame^]	734	well suited to other phases of code generation; in particular,
				735	instruction scheduling (SelectionDAG's are very close to scheduling DAGs
				736	post-selection). Additionally, the SelectionDAG provides a host representation
				737	where a large variety of very-low-level (but target-independent)
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	738	<a href="#selectiondag_optimize">optimizations</a> may be
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	739	performed: ones which require extensive information about the instructions
				740	efficiently supported by the target.
				741	</p>
				742
				743	<p>
				744	The SelectionDAG is a Directed-Acyclic-Graph whose nodes are instances of the
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	745	<tt>SDNode</tt> class. The primary payload of the <tt>SDNode</tt> is its
Chris Lattner	7a025c8	2005-10-16 20:02:19 +0000	[diff] [blame^]	746	operation code (Opcode) that indicates what operation the node performs and
				747	the operands to the operation.
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	748	The various operation node types are described at the top of the
Chris Lattner	7a025c8	2005-10-16 20:02:19 +0000	[diff] [blame^]	749	<tt>include/llvm/CodeGen/SelectionDAGNodes.h</tt> file.</p>
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	750
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	751	<p>Although most operations define a single value, each node in the graph may
				752	define multiple values. For example, a combined div/rem operation will define
				753	both the dividend and the remainder. Many other situations require multiple
				754	values as well. Each node also has some number of operands, which are edges
				755	to the node defining the used value. Because nodes may define multiple values,
				756	edges are represented by instances of the <tt>SDOperand</tt> class, which is
				757	a <SDNode, unsigned> pair, indicating the node and result
				758	value being used, respectively. Each value produced by an SDNode has an
				759	associated MVT::ValueType, indicating what type the value is.
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	760	</p>
				761
				762	<p>
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	763	SelectionDAGs contain two different kinds of values: those that represent data
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	764	flow and those that represent control flow dependencies. Data values are simple
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	765	edges with an integer or floating point value type. Control edges are
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	766	represented as "chain" edges which are of type MVT::Other. These edges provide
				767	an ordering between nodes that have side effects (such as
				768	loads/stores/calls/return/etc). All nodes that have side effects should take a
				769	token chain as input and produce a new one as output. By convention, token
				770	chain inputs are always operand #0, and chain results are always the last
				771	value produced by an operation.</p>
				772
				773	<p>
				774	A SelectionDAG has designated "Entry" and "Root" nodes. The Entry node is
Chris Lattner	e0c1317	2005-05-09 15:41:03 +0000	[diff] [blame]	775	always a marker node with an Opcode of ISD::EntryToken. The Root node is the
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	776	final side-effecting node in the token chain. For example, in a single basic
				777	block function, this would be the return node.
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	778	</p>
				779
				780	<p>
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	781	One important concept for SelectionDAGs is the notion of a "legal" vs. "illegal"
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	782	DAG. A legal DAG for a target is one that only uses supported operations and
Chris Lattner	7a025c8	2005-10-16 20:02:19 +0000	[diff] [blame^]	783	supported types. On a 32-bit PowerPC, for example, a DAG with any values of i1,
				784	i8, i16,
				785	or i64 type would be illegal, as would a DAG that uses a SREM or UREM operation.
				786	The <a href="#selectiondag_legalize">legalize</a>
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	787	phase is responsible for turning an illegal DAG into a legal DAG.
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	788	</p>
				789	</div>
				790
				791	<!-- _______________________________________________________________________ -->
				792	<div class="doc_subsubsection">
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	793	<a name="selectiondag_process">SelectionDAG Instruction Selection Process</a>
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	794	</div>
				795
				796	<div class="doc_text">
				797
				798	<p>
				799	SelectionDAG-based instruction selection consists of the following steps:
				800	</p>
				801
				802	<ol>
				803	<li><a href="#selectiondag_build">Build initial DAG</a> - This stage performs
				804	a simple translation from the input LLVM code to an illegal SelectionDAG.
				805	</li>
				806	<li><a href="#selectiondag_optimize">Optimize SelectionDAG</a> - This stage
				807	performs simple optimizations on the SelectionDAG to simplify it and
				808	recognize meta instructions (like rotates and div/rem pairs) for
				809	targets that support these meta operations. This makes the resultant code
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	810	more efficient and the 'select instructions from DAG' phase (below) simpler.
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	811	</li>
				812	<li><a href="#selectiondag_legalize">Legalize SelectionDAG</a> - This stage
				813	converts the illegal SelectionDAG to a legal SelectionDAG, by eliminating
				814	unsupported operations and data types.</li>
				815	<li><a href="#selectiondag_optimize">Optimize SelectionDAG (#2)</a> - This
				816	second run of the SelectionDAG optimized the newly legalized DAG, to
				817	eliminate inefficiencies introduced by legalization.</li>
				818	<li><a href="#selectiondag_select">Select instructions from DAG</a> - Finally,
				819	the target instruction selector matches the DAG operations to target
Chris Lattner	e35d3bb	2005-10-16 00:36:38 +0000	[diff] [blame]	820	instructions. This process translates the target-independent input DAG into
				821	another DAG of target instructions.</li>
Chris Lattner	32e89f2	2005-10-16 18:31:08 +0000	[diff] [blame]	822	<li><a href="#selectiondag_sched">SelectionDAG Scheduling and Formation</a>
Chris Lattner	e35d3bb	2005-10-16 00:36:38 +0000	[diff] [blame]	823	- The last phase assigns a linear order to the instructions in the
				824	target-instruction DAG and emits them into the MachineFunction being
				825	compiled. This step uses traditional prepass scheduling techniques.</li>
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	826	</ol>
				827
				828	<p>After all of these steps are complete, the SelectionDAG is destroyed and the
				829	rest of the code generation passes are run.</p>
				830
				831	</div>
				832
				833	<!-- _______________________________________________________________________ -->
				834	<div class="doc_subsubsection">
				835	<a name="selectiondag_build">Initial SelectionDAG Construction</a>
				836	</div>
				837
				838	<div class="doc_text">
				839
				840	<p>
				841	The initial SelectionDAG is naively peephole expanded from the LLVM input by
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	842	the <tt>SelectionDAGLowering</tt> class in the SelectionDAGISel.cpp file. The
				843	intent of this pass is to expose as much low-level, target-specific details
				844	to the SelectionDAG as possible. This pass is mostly hard-coded (e.g. an LLVM
				845	add turns into an SDNode add while a geteelementptr is expanded into the obvious
				846	arithmetic). This pass requires target-specific hooks to lower calls and
Chris Lattner	7a025c8	2005-10-16 20:02:19 +0000	[diff] [blame^]	847	returns, varargs, etc. For these features, the <a
				848	href="#targetlowering">TargetLowering</a> interface is
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	849	used.
				850	</p>
				851
				852	</div>
				853
				854	<!-- _______________________________________________________________________ -->
				855	<div class="doc_subsubsection">
				856	<a name="selectiondag_legalize">SelectionDAG Legalize Phase</a>
				857	</div>
				858
				859	<div class="doc_text">
				860
				861	<p>The Legalize phase is in charge of converting a DAG to only use the types and
				862	operations that are natively supported by the target. This involves two major
				863	tasks:</p>
				864
				865	<ol>
				866	<li><p>Convert values of unsupported types to values of supported types.</p>
Chris Lattner	7a025c8	2005-10-16 20:02:19 +0000	[diff] [blame^]	867	<p>There are two main ways of doing this: converting small types to
				868	larger types ("promoting"), and breaking up large integer types
				869	into smaller ones ("expanding"). For example, a target might require
				870	that all f32 values are promoted to f64 and that all i1/i8/i16 values
				871	are promoted to i32. The same target might require that all i64 values
				872	be expanded into i32 values. These changes can insert sign and zero
				873	extensions as
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	874	needed to make sure that the final code has the same behavior as the
				875	input.</p>
Chris Lattner	7a025c8	2005-10-16 20:02:19 +0000	[diff] [blame^]	876	<p>A target implementation tells the legalizer which types are supported
				877	(and which register class to use for them) by calling the
				878	"addRegisterClass" method in its TargetLowering constructor.</p>
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	879	</li>
				880
Chris Lattner	7a025c8	2005-10-16 20:02:19 +0000	[diff] [blame^]	881	<li><p>Eliminate operations that are not supported by the target.</p>
				882	<p>Targets often have weird constraints, such as not supporting every
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	883	operation on every supported datatype (e.g. X86 does not support byte
Chris Lattner	7a025c8	2005-10-16 20:02:19 +0000	[diff] [blame^]	884	conditional moves and PowerPC does not support sign-extending loads from
				885	a 16-bit memory location). Legalize takes care by open-coding
				886	another sequence of operations to emulate the operation ("expansion"), by
				887	promoting to a larger type that supports the operation
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	888	(promotion), or using a target-specific hook to implement the
Chris Lattner	7a025c8	2005-10-16 20:02:19 +0000	[diff] [blame^]	889	legalization (custom).</p>
				890	<p>A target implementation tells the legalizer which operations are not
				891	supported (and which of the above three actions to take) by calling the
				892	"setOperationAction" method in its TargetLowering constructor.</p>
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	893	</li>
				894	</ol>
				895
				896	<p>
Chris Lattner	7a025c8	2005-10-16 20:02:19 +0000	[diff] [blame^]	897	Prior to the existance of the Legalize pass, we required that every
				898	target <a href="#selectiondag_optimize">selector</a> supported and handled every
				899	operator and type even if they are not natively supported. The introduction of
				900	the Legalize phase allows all of the
				901	cannonicalization patterns to be shared across targets, and makes it very
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	902	easy to optimize the cannonicalized code because it is still in the form of
				903	a DAG.
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	904	</p>
				905
				906	</div>
				907
				908	<!-- _______________________________________________________________________ -->
				909	<div class="doc_subsubsection">
Chris Lattner	e35d3bb	2005-10-16 00:36:38 +0000	[diff] [blame]	910	<a name="selectiondag_optimize">SelectionDAG Optimization Phase: the DAG
				911	Combiner</a>
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	912	</div>
				913
				914	<div class="doc_text">
				915
				916	<p>
				917	The SelectionDAG optimization phase is run twice for code generation: once
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	918	immediately after the DAG is built and once after legalization. The first run
				919	of the pass allows the initial code to be cleaned up (e.g. performing
				920	optimizations that depend on knowing that the operators have restricted type
				921	inputs). The second run of the pass cleans up the messy code generated by the
Chris Lattner	7a025c8	2005-10-16 20:02:19 +0000	[diff] [blame^]	922	Legalize pass, which allows Legalize to be very simple (it can focus on making
				923	code legal instead of focusing on generating <i>good</i> and legal code).
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	924	</p>
				925
				926	<p>
Chris Lattner	e35d3bb	2005-10-16 00:36:38 +0000	[diff] [blame]	927	One important class of optimizations performed is optimizing inserted sign and
				928	zero extension instructions. We currently use ad-hoc techniques, but could move
				929	to more rigorous techniques in the future. Here are some good
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	930	papers on the subject:</p>
				931
				932	<p>
				933	"<a href="http://www.eecs.harvard.edu/~nr/pubs/widen-abstract.html">Widening
				934	integer arithmetic</a>"<br>
				935	Kevin Redwine and Norman Ramsey<br>
				936	International Conference on Compiler Construction (CC) 2004
				937	</p>
				938
				939
				940	<p>
				941	"<a href="http://portal.acm.org/citation.cfm?doid=512529.512552">Effective
				942	sign extension elimination</a>"<br>
				943	Motohiro Kawahito, Hideaki Komatsu, and Toshio Nakatani<br>
				944	Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language Design
				945	and Implementation.
				946	</p>
				947
				948	</div>
				949
				950	<!-- _______________________________________________________________________ -->
				951	<div class="doc_subsubsection">
				952	<a name="selectiondag_select">SelectionDAG Select Phase</a>
				953	</div>
				954
				955	<div class="doc_text">
				956
				957	<p>The Select phase is the bulk of the target-specific code for instruction
Chris Lattner	7a025c8	2005-10-16 20:02:19 +0000	[diff] [blame^]	958	selection. This phase takes a legal SelectionDAG as input,
				959	pattern matches the instructions supported by the target to this DAG, and
				960	produces a new DAG of target code. For example, consider the following LLVM
				961	fragment:</p>
				962
				963	<pre>
				964	%t1 = add float %W, %X
				965	%t2 = mul float %t1, %Y
				966	%t3 = add float %t2, %Z
				967	</pre>
				968
				969	<p>This LLVM code corresponds to a SelectionDAG that looks basically like this:
				970	</p>
				971
				972	<pre>
				973	(fadd:f32 (fmul:f32 (fadd:f32 W, X), Y), Z)
				974	</pre>
				975
				976	<p>If a target supports floating pointer multiple-and-add (FMA) operations, one
				977	of the adds can be merged with the multiply. On the PowerPC, for example, the
				978	output of the instruction selector might look like this DAG:</p>
				979
				980	<pre>
				981	(FMADDS (FADDS W, X), Y, Z)
				982	</pre>
				983
				984	<p>
				985	The FMADDS instruction is a ternary instruction that multiplies its first two
				986	operands and adds the third (as single-precision floating-point numbers). The
				987	FADDS instruction is a simple binary single-precision add instruction. To
				988	perform this pattern match, the PowerPC backend includes the following
				989	instruction definitions:
				990	</p>
				991
				992	<pre>
				993	def FMADDS : AForm_1<59, 29,
				994	(ops F4RC:$FRT, F4RC:$FRA, F4RC:$FRC, F4RC:$FRB),
				995	"fmadds $FRT, $FRA, $FRC, $FRB",
				996	[<b>(set F4RC:$FRT, (fadd (fmul F4RC:$FRA, F4RC:$FRC),
				997	F4RC:$FRB))</b>]>;
				998	def FADDS : AForm_2<59, 21,
				999	(ops F4RC:$FRT, F4RC:$FRA, F4RC:$FRB),
				1000	"fadds $FRT, $FRA, $FRB",
				1001	[<b>(set F4RC:$FRT, (fadd F4RC:$FRA, F4RC:$FRB))</b>]>;
				1002	</pre>
				1003
				1004	<p>The portion of the instruction definition in bold indicates the pattern used
				1005	to match the instruction. The DAG operators (like <tt>fmul</tt>/<tt>fadd</tt>)
				1006	are defined in the <tt>lib/Target/TargetSelectionDAG.td</tt> file.
				1007	"<tt>F4RC</tt>" is the register class of the input and result values.<p>
				1008
				1009	<p>The TableGen DAG instruction selector generator reads the instruction
				1010	patterns in the .td and automatically builds parts of the pattern matching code
				1011	for your target. It has the following strengths:</p>
				1012
				1013	<ul>
				1014	<li>At compiler-compiler time, it analyzes your instruction patterns and tells
				1015	you if things are legal or not.</li>
				1016	<li>It can handle arbitrary constraints on operands for the pattern match. In
				1017	particular, it is straight forward to say things like "match any immediate
				1018	that is a 13-bit sign-extended value". For examples, see the
				1019	<tt>immSExt16</tt> and related tblgen classes in the PowerPC backend.</li>
				1020	<li>It knows several important identities for the patterns defined. For
				1021	example, it knows that addition is commutative, so it allows the
				1022	<tt>FMADDS</tt> pattern above to match "<tt>(fadd X, (fmul Y, Z))</tt>" as
				1023	well as "<tt>(fadd (fmul X, Y), Z)</tt>", without the target author having
				1024	to specially handle this case.</li>
				1025	<li>It has a full strength type-inferencing system. In particular, you should
				1026	rarely have to explicitly tell the system what type parts of your patterns
				1027	are. In the FMADDS case above, we didn't have to tell tblgen that all of
				1028	the nodes in the pattern are of type 'f32'. It was able to infer and
				1029	propagate this knowledge from the fact that F4RC has type 'f32'.</li>
				1030	<li>Targets can define their own (and rely on built-in) "pattern fragments".
				1031	Pattern fragments are chunks of reusable patterns that get inlined into your
				1032	patterns during compiler-compiler time. For example, the integer "(not x)"
				1033	operation is actually defined as a pattern fragment that expands as
				1034	"(xor x, -1)", since the SelectionDAG does not have a native 'not'
				1035	operation. Targets can define their own short-hand fragments as they see
				1036	fit. See the definition of 'not' and 'ineg' for examples.</li>
				1037	<li>In addition to instructions, targets can specify arbitrary patterns that
				1038	map to one or more instructions, using the 'Pat' definition. For example,
				1039	the PowerPC has no way of loading an arbitrary integer immediate into a
				1040	register in one instruction. To tell tblgen how to do this, it defines:
				1041
				1042	<pre>
				1043	// Arbitrary immediate support. Implement in terms of LIS/ORI.
				1044	def : Pat<(i32 imm:$imm),
				1045	(ORI (LIS (HI16 imm:$imm)), (LO16 imm:$imm))>;
				1046	</pre>
				1047
				1048	If none of the single-instruction patterns for loading an immediate into a
				1049	register match, this will be used. This rule says "match an arbitrary i32
				1050	immediate, turning it into an ORI ('or a 16-bit immediate') and an LIS
				1051	('load 16-bit immediate, where the immediate is shifted to the left 16
				1052	bits') instruction". To make this work, the LO16/HI16 node transformations
				1053	are used to manipulate the input immediate (in this case, take the high or
				1054	low 16-bits of the immediate).
				1055	</li>
				1056	<li>While the system does automate a lot, it still allows you to write custom
				1057	C++ code to match special cases, in case there is something that is hard
				1058	to express.</li>
				1059	</ul>
				1060
				1061	<p>
				1062	While it has many strengths, the system currently has some limitations,
				1063	primarily because it is a work in progress and is not yet finished:
				1064	</p>
				1065
				1066	<ul>
				1067	<li>Overall, there is no way to define or match SelectionDAG nodes that define
				1068	multiple values (e.g. ADD_PARTS, LOAD, CALL, etc). This is the biggest
				1069	reason that you currently still <i>have to</i> write custom C++ code for
				1070	your instruction selector.</li>
				1071	<li>There is no great way to support match complex addressing modes yet. In the
				1072	future, we will extend pattern fragments to allow them to define multiple
				1073	values (e.g. the four operands of the <a href="#x86_memory">X86 addressing
				1074	mode</a>). In addition, we'll extend fragments so that a fragment can match
				1075	multiple different patterns.</li>
				1076	<li>We don't automatically infer flags like isStore/isLoad yet.</li>
				1077	<li>We don't automatically generate the set of supported registers and
				1078	operations for the <a href="#"selectiondag_legalize>Legalizer</a> yet.</li>
				1079	<li>We don't have a way of tying in custom legalized nodes yet.</li>
				1080	</li>
				1081
				1082	<p>Despite these limitations, the instruction selector generator is still quite
				1083	useful for most of the binary and logical operations in typical instruction
				1084	sets. If you run into any problems or can't figure out how to do something,
				1085	please let Chris know!</p>
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	1086
				1087	</div>
				1088
				1089	<!-- _______________________________________________________________________ -->
				1090	<div class="doc_subsubsection">
Chris Lattner	32e89f2	2005-10-16 18:31:08 +0000	[diff] [blame]	1091	<a name="selectiondag_sched">SelectionDAG Scheduling and Formation Phase</a>
Chris Lattner	e35d3bb	2005-10-16 00:36:38 +0000	[diff] [blame]	1092	</div>
				1093
				1094	<div class="doc_text">
				1095
				1096	<p>The scheduling phase takes the DAG of target instructions from the selection
				1097	phase and assigns an order. The scheduler can pick an order depending on
				1098	various constraints of the machines (i.e. order for minimal register pressure or
				1099	try to cover instruction latencies). Once an order is established, the DAG is
				1100	converted to a list of <a href="#machineinstr">MachineInstr</a>s and the
				1101	Selection DAG is destroyed.
				1102	</p>
				1103
				1104	</div>
				1105
				1106	<!-- _______________________________________________________________________ -->
				1107	<div class="doc_subsubsection">
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	1108	<a name="selectiondag_future">Future directions for the SelectionDAG</a>
				1109	</div>
				1110
				1111	<div class="doc_text">
				1112
				1113	<ol>
Chris Lattner	e35d3bb	2005-10-16 00:36:38 +0000	[diff] [blame]	1114	<li>Optional function-at-a-time selection.</li>
				1115	<li>Auto-generate entire selector from .td file.</li>
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	1116	</li>
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	1117	</ol>
				1118
				1119	</div>
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	1120
				1121	<!-- ======================================================================= -->
				1122	<div class="doc_subsection">
				1123	<a name="ssamco">SSA-based Machine Code Optimizations</a>
				1124	</div>
				1125	<div class="doc_text"><p>To Be Written</p></div>
				1126	<!-- ======================================================================= -->
				1127	<div class="doc_subsection">
				1128	<a name="regalloc">Register Allocation</a>
				1129	</div>
				1130	<div class="doc_text"><p>To Be Written</p></div>
				1131	<!-- ======================================================================= -->
				1132	<div class="doc_subsection">
				1133	<a name="proepicode">Prolog/Epilog Code Insertion</a>
				1134	</div>
				1135	<div class="doc_text"><p>To Be Written</p></div>
				1136	<!-- ======================================================================= -->
				1137	<div class="doc_subsection">
				1138	<a name="latemco">Late Machine Code Optimizations</a>
				1139	</div>
				1140	<div class="doc_text"><p>To Be Written</p></div>
				1141	<!-- ======================================================================= -->
				1142	<div class="doc_subsection">
Chris Lattner	32e89f2	2005-10-16 18:31:08 +0000	[diff] [blame]	1143	<a name="codeemit">Code Emission</a>
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	1144	</div>
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	1145
Chris Lattner	32e89f2	2005-10-16 18:31:08 +0000	[diff] [blame]	1146
				1147	<!-- _______________________________________________________________________ -->
				1148	<div class="doc_subsubsection">
				1149	<a name="codeemit_asm">Generating Assembly Code</a>
				1150	</div>
				1151
				1152	<div class="doc_text">
				1153
				1154	</div>
				1155
				1156
				1157	<!-- _______________________________________________________________________ -->
				1158	<div class="doc_subsubsection">
				1159	<a name="codeemit_bin">Generating Binary Machine Code</a>
				1160	</div>
				1161
				1162	<div class="doc_text">
				1163	<p>For the JIT or .o file writer</p>
				1164	</div>
				1165
				1166
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	1167	<!-- *********************************************************************** -->
				1168	<div class="doc_section">
Chris Lattner	32e89f2	2005-10-16 18:31:08 +0000	[diff] [blame]	1169	<a name="targetimpls">Target-specific Implementation Notes</a>
Chris Lattner	ec94f80	2004-06-04 00:16:02 +0000	[diff] [blame]	1170	</div>
				1171	<!-- *********************************************************************** -->
				1172
				1173	<div class="doc_text">
				1174
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	1175	<p>This section of the document explains features or design decisions that
Chris Lattner	ec94f80	2004-06-04 00:16:02 +0000	[diff] [blame]	1176	are specific to the code generator for a particular target.</p>
				1177
				1178	</div>
				1179
				1180
				1181	<!-- ======================================================================= -->
				1182	<div class="doc_subsection">
				1183	<a name="x86">The X86 backend</a>
				1184	</div>
				1185
				1186	<div class="doc_text">
				1187
				1188	<p>
				1189	The X86 code generator lives in the <tt>lib/Target/X86</tt> directory. This
				1190	code generator currently targets a generic P6-like processor. As such, it
				1191	produces a few P6-and-above instructions (like conditional moves), but it does
				1192	not make use of newer features like MMX or SSE. In the future, the X86 backend
Chris Lattner	aa5bcb5	2005-01-28 17:22:53 +0000	[diff] [blame]	1193	will have sub-target support added for specific processor families and
Chris Lattner	ec94f80	2004-06-04 00:16:02 +0000	[diff] [blame]	1194	implementations.</p>
				1195
				1196	</div>
				1197
				1198	<!-- _______________________________________________________________________ -->
				1199	<div class="doc_subsubsection">
Chris Lattner	9b988be	2005-07-12 00:20:49 +0000	[diff] [blame]	1200	<a name="x86_tt">X86 Target Triples Supported</a>
				1201	</div>
				1202
				1203	<div class="doc_text">
				1204	<p>
				1205	The following are the known target triples that are supported by the X86
				1206	backend. This is not an exhaustive list, but it would be useful to add those
				1207	that people test.
				1208	</p>
				1209
				1210	<ul>
				1211	<li><b>i686-pc-linux-gnu</b> - Linux</li>
				1212	<li><b>i386-unknown-freebsd5.3</b> - FreeBSD 5.3</li>
				1213	<li><b>i686-pc-cygwin</b> - Cygwin on Win32</li>
				1214	<li><b>i686-pc-mingw32</b> - MingW on Win32</li>
Chris Lattner	32e89f2	2005-10-16 18:31:08 +0000	[diff] [blame]	1215	<li><b>i686-apple-darwin*</b> - Apple Darwin on X86</li>
Chris Lattner	9b988be	2005-07-12 00:20:49 +0000	[diff] [blame]	1216	</ul>
				1217
				1218	</div>
				1219
				1220	<!-- _______________________________________________________________________ -->
				1221	<div class="doc_subsubsection">
Chris Lattner	ec94f80	2004-06-04 00:16:02 +0000	[diff] [blame]	1222	<a name="x86_memory">Representing X86 addressing modes in MachineInstrs</a>
				1223	</div>
				1224
				1225	<div class="doc_text">
				1226
Misha Brukman	600df45	2005-02-17 22:22:24 +0000	[diff] [blame]	1227	<p>The x86 has a very flexible way of accessing memory. It is capable of
Chris Lattner	ec94f80	2004-06-04 00:16:02 +0000	[diff] [blame]	1228	forming memory addresses of the following expression directly in integer
				1229	instructions (which use ModR/M addressing):</p>
				1230
				1231	<pre>
				1232	Base+[1,2,4,8]*IndexReg+Disp32
				1233	</pre>
				1234
Misha Brukman	600df45	2005-02-17 22:22:24 +0000	[diff] [blame]	1235	<p>In order to represent this, LLVM tracks no less than 4 operands for each
				1236	memory operand of this form. This means that the "load" form of 'mov' has the
				1237	following <tt>MachineOperand</tt>s in this order:</p>
Chris Lattner	ec94f80	2004-06-04 00:16:02 +0000	[diff] [blame]	1238
				1239	<pre>
				1240	Index: 0 \| 1 2 3 4
				1241	Meaning: DestReg, \| BaseReg, Scale, IndexReg, Displacement
				1242	OperandTy: VirtReg, \| VirtReg, UnsImm, VirtReg, SignExtImm
				1243	</pre>
				1244
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	1245	<p>Stores, and all other instructions, treat the four memory operands in the
				1246	same way, in the same order.</p>
Chris Lattner	ec94f80	2004-06-04 00:16:02 +0000	[diff] [blame]	1247
				1248	</div>
				1249
				1250	<!-- _______________________________________________________________________ -->
				1251	<div class="doc_subsubsection">
				1252	<a name="x86_names">Instruction naming</a>
				1253	</div>
				1254
				1255	<div class="doc_text">
				1256
				1257	<p>
Reid Spencer	ad1f0cd	2005-04-24 20:56:18 +0000	[diff] [blame]	1258	An instruction name consists of the base name, a default operand size, and a
				1259	a character per operand with an optional special size. For example:</p>
Chris Lattner	ec94f80	2004-06-04 00:16:02 +0000	[diff] [blame]	1260
				1261	<p>
				1262	<tt>ADD8rr</tt> -> add, 8-bit register, 8-bit register<br>
				1263	<tt>IMUL16rmi</tt> -> imul, 16-bit register, 16-bit memory, 16-bit immediate<br>
				1264	<tt>IMUL16rmi8</tt> -> imul, 16-bit register, 16-bit memory, 8-bit immediate<br>
				1265	<tt>MOVSX32rm16</tt> -> movsx, 32-bit register, 16-bit memory
				1266	</p>
				1267
				1268	</div>
Chris Lattner	ce52b7e	2004-06-01 06:48:00 +0000	[diff] [blame]	1269
				1270	<!-- *********************************************************************** -->
				1271	<hr>
				1272	<address>
				1273	<a href="http://jigsaw.w3.org/css-validator/check/referer"><img
				1274	src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
				1275	<a href="http://validator.w3.org/check/referer"><img
				1276	src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!" /></a>
				1277
				1278	<a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
				1279	<a href="http://llvm.cs.uiuc.edu">The LLVM Compiler Infrastructure</a><br>
				1280	Last modified: $Date$
				1281	</address>
				1282
				1283	</body>
				1284	</html>