+<!-- ======================================================================= -->
+<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
+(<a href="#machineinstr">MachineInstr</a> 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 MachineBasicBlock 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
+(<a href="#machinebasicblock">MachineBasicBlock</a> 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
+the MachineConstantPool, MachineFrameInfo, MachineFunctionInfo,
+SSARegMap, and a set of live in and live out registers for the function. See
+<tt>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. In LLVM there are two main forms:
+the SelectionDAG based instruction selector framework and an old-style 'simple'
+instruction selector (which effectively peephole selects each LLVM instruction
+into a series of machine instructions). We recommend that all targets use the
+SelectionDAG infrastructure.
+</p>
+
+<p>Portions of the DAG instruction selector are generated from the target
+description files (<tt>*.td</tt>) files. Eventually, we aim for the entire
+instruction selector to be generated from these <tt>.td</tt> files.</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>SDOperand</tt> class, which is
+a <SDNode, unsigned> pair, indicating the node and result
+value being used, respectively. Each value produced by an SDNode has an
+associated MVT::ValueType, indicating what type 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 MVT::Other. These edges provide
+an ordering between nodes that have side effects (such as
+loads/stores/calls/return/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 ISD::EntryToken. The Root node is the
+final side-effecting node in the token chain. For example, in a single basic
+block function, this 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 any values of i1,
+i8, i16,
+or i64 type would be illegal, as would a DAG that uses a SREM or UREM operation.
+The <a href="#selectiondag_legalize">legalize</a>
+phase is 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 div/rem pairs) for
+ targets that support these meta operations. This makes the resultant code
+ more efficient and the 'select instructions from DAG' phase (below) simpler.
+</li>
+<li><a href="#selectiondag_legalize">Legalize SelectionDAG</a> - This stage
+ converts the illegal SelectionDAG to a legal SelectionDAG, by eliminating
+ unsupported operations and data types.</li>
+<li><a href="#selectiondag_optimize">Optimize SelectionDAG (#2)</a> - This
+ second run of the SelectionDAG optimized the newly legalized DAG, to
+ eliminate inefficiencies introduced by 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. In particular, the <tt>-view-isel-dags</tt>
+option pops up a window with the SelectionDAG input to the Select phase for all
+of the code compiled (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). The <tt>-view-sched-dags</tt> option
+views the SelectionDAG output from the Select phase and input to the Scheduler
+phase.
+</p>
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="selectiondag_build">Initial SelectionDAG Construction</a>
+</div>
+
+<div class="doc_text">
+
+<p>
+The initial SelectionDAG is naively peephole expanded from the LLVM input by
+the <tt>SelectionDAGLowering</tt> class in the SelectionDAGISel.cpp 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
+add turns into an SDNode add while a geteelementptr is expanded into the obvious
+arithmetic). This pass requires target-specific hooks to lower calls and
+returns, varargs, etc. For these features, the <a
+href="#targetlowering">TargetLowering</a> interface is
+used.
+</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 types and
+operations that are natively supported by the target. This involves two major
+tasks:</p>
+
+<ol>
+<li><p>Convert values of unsupported types to values of supported types.</p>
+ <p>There are two main ways of doing this: 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 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>A target implementation tells the legalizer which types are supported
+ (and which register class to use for them) by calling the
+ "addRegisterClass" method in its TargetLowering constructor.</p>
+</li>
+
+<li><p>Eliminate operations that are not 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 by open-coding
+ another sequence of operations to emulate the operation ("expansion"), by
+ promoting to a larger type that supports the operation
+ (promotion), or 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
+ "setOperationAction" method in its TargetLowering constructor.</p>
+</li>
+</ol>
+
+<p>
+Prior to the existance of the Legalize pass, 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 phase allows all of the
+cannonicalization patterns to be shared across targets, and makes it very
+easy to optimize the cannonicalized 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 twice for code generation: once
+immediately after the DAG is built and once after 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). The second run of the pass cleans up the messy code generated by the
+Legalize pass, which allows Legalize to be very simple (it can focus on making
+code legal instead of focusing on generating <i>good</i> 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>
+
+<pre>
+ %t1 = add float %W, %X
+ %t2 = mul float %t1, %Y
+ %t3 = add float %t2, %Z
+</pre>
+
+<p>This LLVM code corresponds to a SelectionDAG that looks basically like this:
+</p>
+
+<pre>
+ (fadd:f32 (fmul:f32 (fadd:f32 W, X), Y), Z)
+</pre>
+
+<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>
+
+<pre>
+ (FMADDS (FADDS W, X), Y, Z)
+</pre>
+
+<p>
+The FMADDS instruction is a ternary instruction that multiplies its first two
+operands and adds the third (as single-precision floating-point numbers). The
+FADDS instruction is a simple binary single-precision add instruction. To
+perform this pattern match, the PowerPC backend includes the following
+instruction definitions:
+</p>
+
+<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>
+
+<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 .td 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 tblgen 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 FMADDS case above, we didn't have to tell tblgen 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 F4RC 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 "(not x)"
+ operation is actually defined as a pattern fragment that expands as
+ "(xor x, -1)", since the SelectionDAG does not have a native 'not'
+ operation. Targets can define their own short-hand fragments as they see
+ fit. See the definition of 'not' and 'ineg' 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:
+
+ <pre>
+ // Arbitrary immediate support. Implement in terms of LIS/ORI.
+ def : Pat<(i32 imm:$imm),
+ (ORI (LIS (HI16 imm:$imm)), (LO16 imm:$imm))>;
+ </pre>
+
+ 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 ORI ('or a 16-bit immediate') and an LIS
+ ('load 16-bit immediate, where the immediate is shifted to the left 16
+ bits') instruction". To make this work, the LO16/HI16 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, in case 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. ADD_PARTS, LOAD, CALL, etc). This is the biggest
+ reason that you currently still <i>have to</i> write custom C++ code for
+ your instruction selector.</li>
+<li>There is no great way to support match 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>). 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 <a href="#machineinstr">MachineInstr</a>s and the
+Selection DAG 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 .td file.</li>
+</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="regalloc">Register Allocation</a>
+</div>
+<div class="doc_text"><p>To Be Written</p></div>
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="proepicode">Prolog/Epilog Code Insertion</a>
+</div>
+<div class="doc_text"><p>To Be Written</p></div>
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="latemco">Late Machine Code Optimizations</a>
+</div>
+<div class="doc_text"><p>To Be Written</p></div>
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="codeemit">Code Emission</a>
+</div>
+
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="codeemit_asm">Generating Assembly Code</a>
+</div>
+
+<div class="doc_text">
+
+</div>
+
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="codeemit_bin">Generating Binary Machine Code</a>
+</div>
+
+<div class="doc_text">
+ <p>For the JIT or .o file writer</p>
+</div>
+
+