+<div class="doc_code">
+<pre>
+define i32 @test(i32 %X, i32 %Y) {
+ %Z = udiv i32 %X, %Y
+ ret i32 %Z
+}
+</pre>
+</div>
+
+<p>The X86 instruction selector produces this machine code for the <tt>div</tt>
+ and <tt>ret</tt> (use "<tt>llc X.bc -march=x86 -print-machineinstrs</tt>" to
+ get this):</p>
+
+<div class="doc_code">
+<pre>
+;; Start of div
+%EAX = mov %reg1024 ;; Copy X (in reg1024) into EAX
+%reg1027 = sar %reg1024, 31
+%EDX = mov %reg1027 ;; Sign extend X into EDX
+idiv %reg1025 ;; Divide by Y (in reg1025)
+%reg1026 = mov %EAX ;; Read the result (Z) out of EAX
+
+;; Start of ret
+%EAX = mov %reg1026 ;; 32-bit return value goes in EAX
+ret
+</pre>
+</div>
+
+<p>By the end of code generation, the register allocator has coalesced the
+ registers and deleted the resultant identity moves producing the following
+ code:</p>
+
+<div class="doc_code">
+<pre>
+;; X is in EAX, Y is in ECX
+mov %EAX, %EDX
+sar %EDX, 31
+idiv %ECX
+ret
+</pre>
+</div>
+
+<p>This approach is extremely general (if it can handle the X86 architecture, it
+ can handle anything!) and allows all of the target specific knowledge about
+ the instruction stream to be isolated in the instruction selector. Note that
+ physical registers should have a short lifetime for good code generation, and
+ all physical registers are assumed dead on entry to and exit from basic
+ blocks (before register allocation). Thus, if you need a value to be live
+ across basic block boundaries, it <em>must</em> live in a virtual
+ register.</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="ssa">Machine code in SSA form</a>
+</div>
+
+<div class="doc_text">
+
+<p><tt>MachineInstr</tt>'s are initially selected in SSA-form, and are
+ maintained in SSA-form until register allocation happens. For the most part,
+ this is trivially simple since LLVM is already in SSA form; LLVM PHI nodes
+ become machine code PHI nodes, and virtual registers are only allowed to have
+ a single definition.</p>
+
+<p>After register allocation, machine code is no longer in SSA-form because
+ there are no virtual registers left in the code.</p>
+
+</div>
+
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="machinebasicblock">The <tt>MachineBasicBlock</tt> class</a>
+</div>
+
+<div class="doc_text">
+
+<p>The <tt>MachineBasicBlock</tt> class contains a list of machine instructions
+ (<tt><a href="#machineinstr">MachineInstr</a></tt> instances). It roughly
+ corresponds to the LLVM code input to the instruction selector, but there can
+ be a one-to-many mapping (i.e. one LLVM basic block can map to multiple
+ machine basic blocks). The <tt>MachineBasicBlock</tt> class has a
+ "<tt>getBasicBlock</tt>" method, which returns the LLVM basic block that it
+ comes from.</p>
+
+</div>
+
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="machinefunction">The <tt>MachineFunction</tt> class</a>
+</div>
+
+<div class="doc_text">
+
+<p>The <tt>MachineFunction</tt> class contains a list of machine basic blocks
+ (<tt><a href="#machinebasicblock">MachineBasicBlock</a></tt> instances). It
+ corresponds one-to-one with the LLVM function input to the instruction
+ selector. In addition to a list of basic blocks,
+ the <tt>MachineFunction</tt> contains a a <tt>MachineConstantPool</tt>,
+ a <tt>MachineFrameInfo</tt>, a <tt>MachineFunctionInfo</tt>, and a
+ <tt>MachineRegisterInfo</tt>. See
+ <tt>include/llvm/CodeGen/MachineFunction.h</tt> for more information.</p>
+
+</div>
+
+<!-- *********************************************************************** -->
+<div class="doc_section">
+ <a name="codegenalgs">Target-independent code generation algorithms</a>
+</div>
+<!-- *********************************************************************** -->
+
+<div class="doc_text">
+
+<p>This section documents the phases described in the
+ <a href="#high-level-design">high-level design of the code generator</a>.
+ It explains how they work and some of the rationale behind their design.</p>
+
+</div>
+
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="instselect">Instruction Selection</a>
+</div>
+
+<div class="doc_text">
+
+<p>Instruction Selection is the process of translating LLVM code presented to
+ the code generator into target-specific machine instructions. There are
+ several well-known ways to do this in the literature. LLVM uses a
+ SelectionDAG based instruction selector.</p>
+
+<p>Portions of the DAG instruction selector are generated from the target
+ description (<tt>*.td</tt>) files. Our goal is for the entire instruction
+ selector to be generated from these <tt>.td</tt> files, though currently
+ there are still things that require custom C++ code.</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="selectiondag_intro">Introduction to SelectionDAGs</a>
+</div>
+
+<div class="doc_text">
+
+<p>The SelectionDAG provides an abstraction for code representation in a way
+ that is amenable to instruction selection using automatic techniques
+ (e.g. dynamic-programming based optimal pattern matching selectors). It is
+ also well-suited to other phases of code generation; in particular,
+ instruction scheduling (SelectionDAG's are very close to scheduling DAGs
+ post-selection). Additionally, the SelectionDAG provides a host
+ representation where a large variety of very-low-level (but
+ target-independent) <a href="#selectiondag_optimize">optimizations</a> may be
+ performed; ones which require extensive information about the instructions
+ efficiently supported by the target.</p>
+
+<p>The SelectionDAG is a Directed-Acyclic-Graph whose nodes are instances of the
+ <tt>SDNode</tt> class. The primary payload of the <tt>SDNode</tt> is its
+ operation code (Opcode) that indicates what operation the node performs and
+ the operands to the operation. The various operation node types are
+ described at the top of the <tt>include/llvm/CodeGen/SelectionDAGNodes.h</tt>
+ file.</p>
+
+<p>Although most operations define a single value, each node in the graph may
+ define multiple values. For example, a combined div/rem operation will
+ define both the dividend and the remainder. Many other situations require
+ multiple values as well. Each node also has some number of operands, which
+ are edges to the node defining the used value. Because nodes may define
+ multiple values, edges are represented by instances of the <tt>SDValue</tt>
+ class, which is a <tt><SDNode, unsigned></tt> pair, indicating the node
+ and result value being used, respectively. Each value produced by
+ an <tt>SDNode</tt> has an associated <tt>MVT</tt> (Machine Value Type)
+ indicating what the type of the value is.</p>
+
+<p>SelectionDAGs contain two different kinds of values: those that represent
+ data flow and those that represent control flow dependencies. Data values
+ are simple edges with an integer or floating point value type. Control edges
+ are represented as "chain" edges which are of type <tt>MVT::Other</tt>.
+ These edges provide an ordering between nodes that have side effects (such as
+ loads, stores, calls, returns, etc). All nodes that have side effects should
+ take a token chain as input and produce a new one as output. By convention,
+ token chain inputs are always operand #0, and chain results are always the
+ last value produced by an operation.</p>
+
+<p>A SelectionDAG has designated "Entry" and "Root" nodes. The Entry node is
+ always a marker node with an Opcode of <tt>ISD::EntryToken</tt>. The Root
+ node is the final side-effecting node in the token chain. For example, in a
+ single basic block function it would be the return node.</p>
+
+<p>One important concept for SelectionDAGs is the notion of a "legal" vs.
+ "illegal" DAG. A legal DAG for a target is one that only uses supported
+ operations and supported types. On a 32-bit PowerPC, for example, a DAG with
+ a value of type i1, i8, i16, or i64 would be illegal, as would a DAG that
+ uses a SREM or UREM operation. The
+ <a href="#selectinodag_legalize_types">legalize types</a> and
+ <a href="#selectiondag_legalize">legalize operations</a> phases are
+ responsible for turning an illegal DAG into a legal DAG.</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="selectiondag_process">SelectionDAG Instruction Selection Process</a>
+</div>
+
+<div class="doc_text">
+
+<p>SelectionDAG-based instruction selection consists of the following steps:</p>
+
+<ol>
+ <li><a href="#selectiondag_build">Build initial DAG</a> — This stage
+ performs a simple translation from the input LLVM code to an illegal
+ SelectionDAG.</li>
+
+ <li><a href="#selectiondag_optimize">Optimize SelectionDAG</a> — This
+ stage performs simple optimizations on the SelectionDAG to simplify it,
+ and recognize meta instructions (like rotates
+ and <tt>div</tt>/<tt>rem</tt> pairs) for targets that support these meta
+ operations. This makes the resultant code more efficient and
+ the <a href="#selectiondag_select">select instructions from DAG</a> phase
+ (below) simpler.</li>
+
+ <li><a href="#selectiondag_legalize_types">Legalize SelectionDAG Types</a>
+ — This stage transforms SelectionDAG nodes to eliminate any types
+ that are unsupported on the target.</li>
+
+ <li><a href="#selectiondag_optimize">Optimize SelectionDAG</a> — The
+ SelectionDAG optimizer is run to clean up redundancies exposed by type
+ legalization.</li>
+
+ <li><a href="#selectiondag_legalize">Legalize SelectionDAG Types</a> —
+ This stage transforms SelectionDAG nodes to eliminate any types that are
+ unsupported on the target.</li>
+
+ <li><a href="#selectiondag_optimize">Optimize SelectionDAG</a> — The
+ SelectionDAG optimizer is run to eliminate inefficiencies introduced by
+ operation legalization.</li>
+
+ <li><a href="#selectiondag_select">Select instructions from DAG</a> —
+ Finally, the target instruction selector matches the DAG operations to
+ target instructions. This process translates the target-independent input
+ DAG into another DAG of target instructions.</li>
+
+ <li><a href="#selectiondag_sched">SelectionDAG Scheduling and Formation</a>
+ — The last phase assigns a linear order to the instructions in the
+ target-instruction DAG and emits them into the MachineFunction being
+ compiled. This step uses traditional prepass scheduling techniques.</li>
+</ol>
+
+<p>After all of these steps are complete, the SelectionDAG is destroyed and the
+ rest of the code generation passes are run.</p>
+
+<p>One great way to visualize what is going on here is to take advantage of a
+ few LLC command line options. The following options pop up a window
+ displaying the SelectionDAG at specific times (if you only get errors printed
+ to the console while using this, you probably
+ <a href="ProgrammersManual.html#ViewGraph">need to configure your system</a>
+ to add support for it).</p>
+
+<ul>
+ <li><tt>-view-dag-combine1-dags</tt> displays the DAG after being built,
+ before the first optimization pass.</li>
+
+ <li><tt>-view-legalize-dags</tt> displays the DAG before Legalization.</li>
+
+ <li><tt>-view-dag-combine2-dags</tt> displays the DAG before the second
+ optimization pass.</li>
+
+ <li><tt>-view-isel-dags</tt> displays the DAG before the Select phase.</li>
+
+ <li><tt>-view-sched-dags</tt> displays the DAG before Scheduling.</li>
+</ul>
+
+<p>The <tt>-view-sunit-dags</tt> displays the Scheduler's dependency graph.
+ This graph is based on the final SelectionDAG, with nodes that must be
+ scheduled together bundled into a single scheduling-unit node, and with
+ immediate operands and other nodes that aren't relevant for scheduling
+ omitted.</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="selectiondag_build">Initial SelectionDAG Construction</a>
+</div>
+
+<div class="doc_text">
+
+<p>The initial SelectionDAG is naïvely peephole expanded from the LLVM
+ input by the <tt>SelectionDAGLowering</tt> class in the
+ <tt>lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp</tt> file. The intent of
+ this pass is to expose as much low-level, target-specific details to the
+ SelectionDAG as possible. This pass is mostly hard-coded (e.g. an
+ LLVM <tt>add</tt> turns into an <tt>SDNode add</tt> while a
+ <tt>getelementptr</tt> is expanded into the obvious arithmetic). This pass
+ requires target-specific hooks to lower calls, returns, varargs, etc. For
+ these features, the <tt><a href="#targetlowering">TargetLowering</a></tt>
+ interface is used.</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="selectiondag_legalize_types">SelectionDAG LegalizeTypes Phase</a>
+</div>
+
+<div class="doc_text">
+
+<p>The Legalize phase is in charge of converting a DAG to only use the types
+ that are natively supported by the target.</p>
+
+<p>There are two main ways of converting values of unsupported scalar types to
+ values of supported types: converting small types to larger types
+ ("promoting"), and breaking up large integer types into smaller ones
+ ("expanding"). For example, a target might require that all f32 values are
+ promoted to f64 and that all i1/i8/i16 values are promoted to i32. The same
+ target might require that all i64 values be expanded into pairs of i32
+ values. These changes can insert sign and zero extensions as needed to make
+ sure that the final code has the same behavior as the input.</p>
+
+<p>There are two main ways of converting values of unsupported vector types to
+ value of supported types: splitting vector types, multiple times if
+ necessary, until a legal type is found, and extending vector types by adding
+ elements to the end to round them out to legal types ("widening"). If a
+ vector gets split all the way down to single-element parts with no supported
+ vector type being found, the elements are converted to scalars
+ ("scalarizing").</p>
+
+<p>A target implementation tells the legalizer which types are supported (and
+ which register class to use for them) by calling the
+ <tt>addRegisterClass</tt> method in its TargetLowering constructor.</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="selectiondag_legalize">SelectionDAG Legalize Phase</a>
+</div>
+
+<div class="doc_text">
+
+<p>The Legalize phase is in charge of converting a DAG to only use the
+ operations that are natively supported by the target.</p>
+
+<p>Targets often have weird constraints, such as not supporting every operation
+ on every supported datatype (e.g. X86 does not support byte conditional moves
+ and PowerPC does not support sign-extending loads from a 16-bit memory
+ location). Legalize takes care of this by open-coding another sequence of
+ operations to emulate the operation ("expansion"), by promoting one type to a
+ larger type that supports the operation ("promotion"), or by using a
+ target-specific hook to implement the legalization ("custom").</p>
+
+<p>A target implementation tells the legalizer which operations are not
+ supported (and which of the above three actions to take) by calling the
+ <tt>setOperationAction</tt> method in its <tt>TargetLowering</tt>
+ constructor.</p>
+
+<p>Prior to the existence of the Legalize passes, we required that every target
+ <a href="#selectiondag_optimize">selector</a> supported and handled every
+ operator and type even if they are not natively supported. The introduction
+ of the Legalize phases allows all of the canonicalization patterns to be
+ shared across targets, and makes it very easy to optimize the canonicalized
+ code because it is still in the form of a DAG.</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="selectiondag_optimize">SelectionDAG Optimization Phase: the DAG
+ Combiner</a>
+</div>
+
+<div class="doc_text">
+
+<p>The SelectionDAG optimization phase is run multiple times for code
+ generation, immediately after the DAG is built and once after each
+ legalization. The first run of the pass allows the initial code to be
+ cleaned up (e.g. performing optimizations that depend on knowing that the
+ operators have restricted type inputs). Subsequent runs of the pass clean up
+ the messy code generated by the Legalize passes, which allows Legalize to be
+ very simple (it can focus on making code legal instead of focusing on
+ generating <em>good</em> and legal code).</p>
+
+<p>One important class of optimizations performed is optimizing inserted sign
+ and zero extension instructions. We currently use ad-hoc techniques, but
+ could move to more rigorous techniques in the future. Here are some good
+ papers on the subject:</p>
+
+<p>"<a href="http://www.eecs.harvard.edu/~nr/pubs/widen-abstract.html">Widening
+ integer arithmetic</a>"<br>
+ Kevin Redwine and Norman Ramsey<br>
+ International Conference on Compiler Construction (CC) 2004</p>
+
+<p>"<a href="http://portal.acm.org/citation.cfm?doid=512529.512552">Effective
+ sign extension elimination</a>"<br>
+ Motohiro Kawahito, Hideaki Komatsu, and Toshio Nakatani<br>
+ Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language Design
+ and Implementation.</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="selectiondag_select">SelectionDAG Select Phase</a>
+</div>
+
+<div class="doc_text">
+
+<p>The Select phase is the bulk of the target-specific code for instruction
+ selection. This phase takes a legal SelectionDAG as input, pattern matches
+ the instructions supported by the target to this DAG, and produces a new DAG
+ of target code. For example, consider the following LLVM fragment:</p>
+
+<div class="doc_code">
+<pre>
+%t1 = add float %W, %X
+%t2 = mul float %t1, %Y
+%t3 = add float %t2, %Z
+</pre>
+</div>
+
+<p>This LLVM code corresponds to a SelectionDAG that looks basically like
+ this:</p>
+
+<div class="doc_code">
+<pre>
+(fadd:f32 (fmul:f32 (fadd:f32 W, X), Y), Z)
+</pre>
+</div>
+
+<p>If a target supports floating point multiply-and-add (FMA) operations, one of
+ the adds can be merged with the multiply. On the PowerPC, for example, the
+ output of the instruction selector might look like this DAG:</p>
+
+<div class="doc_code">
+<pre>
+(FMADDS (FADDS W, X), Y, Z)
+</pre>
+</div>
+
+<p>The <tt>FMADDS</tt> instruction is a ternary instruction that multiplies its
+first two operands and adds the third (as single-precision floating-point
+numbers). The <tt>FADDS</tt> instruction is a simple binary single-precision
+add instruction. To perform this pattern match, the PowerPC backend includes
+the following instruction definitions:</p>
+
+<div class="doc_code">
+<pre>
+def FMADDS : AForm_1<59, 29,
+ (ops F4RC:$FRT, F4RC:$FRA, F4RC:$FRC, F4RC:$FRB),
+ "fmadds $FRT, $FRA, $FRC, $FRB",
+ [<b>(set F4RC:$FRT, (fadd (fmul F4RC:$FRA, F4RC:$FRC),
+ F4RC:$FRB))</b>]>;
+def FADDS : AForm_2<59, 21,
+ (ops F4RC:$FRT, F4RC:$FRA, F4RC:$FRB),
+ "fadds $FRT, $FRA, $FRB",
+ [<b>(set F4RC:$FRT, (fadd F4RC:$FRA, F4RC:$FRB))</b>]>;
+</pre>
+</div>
+
+<p>The portion of the instruction definition in bold indicates the pattern used
+ to match the instruction. The DAG operators
+ (like <tt>fmul</tt>/<tt>fadd</tt>) are defined in
+ the <tt>lib/Target/TargetSelectionDAG.td</tt> file. "<tt>F4RC</tt>" is the
+ register class of the input and result values.</p>
+
+<p>The TableGen DAG instruction selector generator reads the instruction
+ patterns in the <tt>.td</tt> file and automatically builds parts of the
+ pattern matching code for your target. It has the following strengths:</p>
+
+<ul>
+ <li>At compiler-compiler time, it analyzes your instruction patterns and tells
+ you if your patterns make sense or not.</li>
+
+ <li>It can handle arbitrary constraints on operands for the pattern match. In
+ particular, it is straight-forward to say things like "match any immediate
+ that is a 13-bit sign-extended value". For examples, see the
+ <tt>immSExt16</tt> and related <tt>tblgen</tt> classes in the PowerPC
+ backend.</li>
+
+ <li>It knows several important identities for the patterns defined. For
+ example, it knows that addition is commutative, so it allows the
+ <tt>FMADDS</tt> pattern above to match "<tt>(fadd X, (fmul Y, Z))</tt>" as
+ well as "<tt>(fadd (fmul X, Y), Z)</tt>", without the target author having
+ to specially handle this case.</li>
+
+ <li>It has a full-featured type-inferencing system. In particular, you should
+ rarely have to explicitly tell the system what type parts of your patterns
+ are. In the <tt>FMADDS</tt> case above, we didn't have to tell
+ <tt>tblgen</tt> that all of the nodes in the pattern are of type 'f32'.
+ It was able to infer and propagate this knowledge from the fact that
+ <tt>F4RC</tt> has type 'f32'.</li>
+
+ <li>Targets can define their own (and rely on built-in) "pattern fragments".
+ Pattern fragments are chunks of reusable patterns that get inlined into
+ your patterns during compiler-compiler time. For example, the integer
+ "<tt>(not x)</tt>" operation is actually defined as a pattern fragment
+ that expands as "<tt>(xor x, -1)</tt>", since the SelectionDAG does not
+ have a native '<tt>not</tt>' operation. Targets can define their own
+ short-hand fragments as they see fit. See the definition of
+ '<tt>not</tt>' and '<tt>ineg</tt>' for examples.</li>
+
+ <li>In addition to instructions, targets can specify arbitrary patterns that
+ map to one or more instructions using the 'Pat' class. For example, the
+ PowerPC has no way to load an arbitrary integer immediate into a register
+ in one instruction. To tell tblgen how to do this, it defines:
+ <br>
+ <br>
+<div class="doc_code">
+<pre>
+// Arbitrary immediate support. Implement in terms of LIS/ORI.
+def : Pat<(i32 imm:$imm),
+ (ORI (LIS (HI16 imm:$imm)), (LO16 imm:$imm))>;
+</pre>
+</div>
+ <br>
+ If none of the single-instruction patterns for loading an immediate into a
+ register match, this will be used. This rule says "match an arbitrary i32
+ immediate, turning it into an <tt>ORI</tt> ('or a 16-bit immediate') and
+ an <tt>LIS</tt> ('load 16-bit immediate, where the immediate is shifted to
+ the left 16 bits') instruction". To make this work, the
+ <tt>LO16</tt>/<tt>HI16</tt> node transformations are used to manipulate
+ the input immediate (in this case, take the high or low 16-bits of the
+ immediate).</li>
+
+ <li>While the system does automate a lot, it still allows you to write custom
+ C++ code to match special cases if there is something that is hard to
+ express.</li>
+</ul>
+
+<p>While it has many strengths, the system currently has some limitations,
+ primarily because it is a work in progress and is not yet finished:</p>
+
+<ul>
+ <li>Overall, there is no way to define or match SelectionDAG nodes that define
+ multiple values (e.g. <tt>SMUL_LOHI</tt>, <tt>LOAD</tt>, <tt>CALL</tt>,
+ etc). This is the biggest reason that you currently still <em>have
+ to</em> write custom C++ code for your instruction selector.</li>
+
+ <li>There is no great way to support matching complex addressing modes yet.
+ In the future, we will extend pattern fragments to allow them to define
+ multiple values (e.g. the four operands of the <a href="#x86_memory">X86
+ addressing mode</a>, which are currently matched with custom C++ code).
+ In addition, we'll extend fragments so that a fragment can match multiple
+ different patterns.</li>
+
+ <li>We don't automatically infer flags like isStore/isLoad yet.</li>
+
+ <li>We don't automatically generate the set of supported registers and
+ operations for the <a href="#selectiondag_legalize">Legalizer</a>
+ yet.</li>
+
+ <li>We don't have a way of tying in custom legalized nodes yet.</li>
+</ul>
+
+<p>Despite these limitations, the instruction selector generator is still quite
+ useful for most of the binary and logical operations in typical instruction
+ sets. If you run into any problems or can't figure out how to do something,
+ please let Chris know!</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="selectiondag_sched">SelectionDAG Scheduling and Formation Phase</a>
+</div>
+
+<div class="doc_text">
+
+<p>The scheduling phase takes the DAG of target instructions from the selection
+ phase and assigns an order. The scheduler can pick an order depending on
+ various constraints of the machines (i.e. order for minimal register pressure
+ or try to cover instruction latencies). Once an order is established, the
+ DAG is converted to a list
+ of <tt><a href="#machineinstr">MachineInstr</a></tt>s and the SelectionDAG is
+ destroyed.</p>
+
+<p>Note that this phase is logically separate from the instruction selection
+ phase, but is tied to it closely in the code because it operates on
+ SelectionDAGs.</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="selectiondag_future">Future directions for the SelectionDAG</a>
+</div>
+
+<div class="doc_text">
+
+<ol>
+ <li>Optional function-at-a-time selection.</li>
+
+ <li>Auto-generate entire selector from <tt>.td</tt> file.</li>
+</ol>
+
+</div>
+
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="ssamco">SSA-based Machine Code Optimizations</a>
+</div>
+<div class="doc_text"><p>To Be Written</p></div>
+
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="liveintervals">Live Intervals</a>
+</div>
+
+<div class="doc_text">
+
+<p>Live Intervals are the ranges (intervals) where a variable is <i>live</i>.
+ They are used by some <a href="#regalloc">register allocator</a> passes to
+ determine if two or more virtual registers which require the same physical
+ register are live at the same point in the program (i.e., they conflict).
+ When this situation occurs, one virtual register must be <i>spilled</i>.</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="livevariable_analysis">Live Variable Analysis</a>
+</div>
+
+<div class="doc_text">
+
+<p>The first step in determining the live intervals of variables is to calculate
+ the set of registers that are immediately dead after the instruction (i.e.,
+ the instruction calculates the value, but it is never used) and the set of
+ registers that are used by the instruction, but are never used after the
+ instruction (i.e., they are killed). Live variable information is computed
+ for each <i>virtual</i> register and <i>register allocatable</i> physical
+ register in the function. This is done in a very efficient manner because it
+ uses SSA to sparsely compute lifetime information for virtual registers
+ (which are in SSA form) and only has to track physical registers within a
+ block. Before register allocation, LLVM can assume that physical registers
+ are only live within a single basic block. This allows it to do a single,
+ local analysis to resolve physical register lifetimes within each basic
+ block. If a physical register is not register allocatable (e.g., a stack
+ pointer or condition codes), it is not tracked.</p>
+
+<p>Physical registers may be live in to or out of a function. Live in values are
+ typically arguments in registers. Live out values are typically return values
+ in registers. Live in values are marked as such, and are given a dummy
+ "defining" instruction during live intervals analysis. If the last basic
+ block of a function is a <tt>return</tt>, then it's marked as using all live
+ out values in the function.</p>
+
+<p><tt>PHI</tt> nodes need to be handled specially, because the calculation of
+ the live variable information from a depth first traversal of the CFG of the
+ function won't guarantee that a virtual register used by the <tt>PHI</tt>
+ node is defined before it's used. When a <tt>PHI</tt> node is encountered,
+ only the definition is handled, because the uses will be handled in other
+ basic blocks.</p>
+
+<p>For each <tt>PHI</tt> node of the current basic block, we simulate an
+ assignment at the end of the current basic block and traverse the successor
+ basic blocks. If a successor basic block has a <tt>PHI</tt> node and one of
+ the <tt>PHI</tt> node's operands is coming from the current basic block, then
+ the variable is marked as <i>alive</i> within the current basic block and all
+ of its predecessor basic blocks, until the basic block with the defining
+ instruction is encountered.</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="liveintervals_analysis">Live Intervals Analysis</a>
+</div>
+
+<div class="doc_text">
+
+<p>We now have the information available to perform the live intervals analysis
+ and build the live intervals themselves. We start off by numbering the basic
+ blocks and machine instructions. We then handle the "live-in" values. These
+ are in physical registers, so the physical register is assumed to be killed
+ by the end of the basic block. Live intervals for virtual registers are
+ computed for some ordering of the machine instructions <tt>[1, N]</tt>. A
+ live interval is an interval <tt>[i, j)</tt>, where <tt>1 <= i <= j
+ < N</tt>, for which a variable is live.</p>
+
+<p><i><b>More to come...</b></i></p>
+
+</div>
+
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="regalloc">Register Allocation</a>
+</div>
+
+<div class="doc_text">
+
+<p>The <i>Register Allocation problem</i> consists in mapping a program
+ <i>P<sub>v</sub></i>, that can use an unbounded number of virtual registers,
+ to a program <i>P<sub>p</sub></i> that contains a finite (possibly small)
+ number of physical registers. Each target architecture has a different number
+ of physical registers. If the number of physical registers is not enough to
+ accommodate all the virtual registers, some of them will have to be mapped
+ into memory. These virtuals are called <i>spilled virtuals</i>.</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+
+<div class="doc_subsubsection">
+ <a name="regAlloc_represent">How registers are represented in LLVM</a>
+</div>
+
+<div class="doc_text">
+
+<p>In LLVM, physical registers are denoted by integer numbers that normally
+ range from 1 to 1023. To see how this numbering is defined for a particular
+ architecture, you can read the <tt>GenRegisterNames.inc</tt> file for that
+ architecture. For instance, by
+ inspecting <tt>lib/Target/X86/X86GenRegisterNames.inc</tt> we see that the
+ 32-bit register <tt>EAX</tt> is denoted by 15, and the MMX register
+ <tt>MM0</tt> is mapped to 48.</p>
+
+<p>Some architectures contain registers that share the same physical location. A
+ notable example is the X86 platform. For instance, in the X86 architecture,
+ the registers <tt>EAX</tt>, <tt>AX</tt> and <tt>AL</tt> share the first eight
+ bits. These physical registers are marked as <i>aliased</i> in LLVM. Given a
+ particular architecture, you can check which registers are aliased by
+ inspecting its <tt>RegisterInfo.td</tt> file. Moreover, the method
+ <tt>TargetRegisterInfo::getAliasSet(p_reg)</tt> returns an array containing
+ all the physical registers aliased to the register <tt>p_reg</tt>.</p>
+
+<p>Physical registers, in LLVM, are grouped in <i>Register Classes</i>.
+ Elements in the same register class are functionally equivalent, and can be
+ interchangeably used. Each virtual register can only be mapped to physical
+ registers of a particular class. For instance, in the X86 architecture, some
+ virtuals can only be allocated to 8 bit registers. A register class is
+ described by <tt>TargetRegisterClass</tt> objects. To discover if a virtual
+ register is compatible with a given physical, this code can be used:</p>
+
+<div class="doc_code">