+<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.</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 <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::ValueType</tt> 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 <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="#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 <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">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 optimizes 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. The <tt>-view-sunit-dags</tt> option views the ScheduleDAG, which is
+based on the final SelectionDAG, with nodes that must be scheduled as a unit
+bundled together into a single node, and with immediate operands and other
+nodes that aren't relevent 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>geteelementptr</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">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
+ <tt>addRegisterClass</tt> 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 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>
+</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 <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>ADD_PARTS</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>). 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 encounted, 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>MRegisterInfo::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">
+<pre>
+bool RegMapping_Fer::compatible_class(MachineFunction &mf,
+ unsigned v_reg,
+ unsigned p_reg) {
+ assert(MRegisterInfo::isPhysicalRegister(p_reg) &&
+ "Target register must be physical");
+ const TargetRegisterClass *trc = mf.getSSARegMap()->getRegClass(v_reg);
+ return trc->contains(p_reg);
+}
+</pre>
+</div>
+
+<p>Sometimes, mostly for debugging purposes, it is useful to change
+the number of physical registers available in the target
+architecture. This must be done statically, inside the
+<tt>TargetRegsterInfo.td</tt> file. Just <tt>grep</tt> for
+<tt>RegisterClass</tt>, the last parameter of which is a list of
+registers. Just commenting some out is one simple way to avoid them
+being used. A more polite way is to explicitly exclude some registers
+from the <i>allocation order</i>. See the definition of the
+<tt>GR</tt> register class in
+<tt>lib/Target/IA64/IA64RegisterInfo.td</tt> for an example of this
+(e.g., <tt>numReservedRegs</tt> registers are hidden.)</p>
+
+<p>Virtual registers are also denoted by integer numbers. Contrary to
+physical registers, different virtual registers never share the same
+number. The smallest virtual register is normally assigned the number
+1024. This may change, so, in order to know which is the first virtual
+register, you should access
+<tt>MRegisterInfo::FirstVirtualRegister</tt>. Any register whose
+number is greater than or equal to
+<tt>MRegisterInfo::FirstVirtualRegister</tt> is considered a virtual
+register. Whereas physical registers are statically defined in a
+<tt>TargetRegisterInfo.td</tt> file and cannot be created by the
+application developer, that is not the case with virtual registers.
+In order to create new virtual registers, use the method
+<tt>SSARegMap::createVirtualRegister()</tt>. This method will return a
+virtual register with the highest code.
+</p>
+
+<p>Before register allocation, the operands of an instruction are
+mostly virtual registers, although physical registers may also be
+used. In order to check if a given machine operand is a register, use
+the boolean function <tt>MachineOperand::isRegister()</tt>. To obtain
+the integer code of a register, use
+<tt>MachineOperand::getReg()</tt>. An instruction may define or use a
+register. For instance, <tt>ADD reg:1026 := reg:1025 reg:1024</tt>
+defines the registers 1024, and uses registers 1025 and 1026. Given a
+register operand, the method <tt>MachineOperand::isUse()</tt> informs
+if that register is being used by the instruction. The method
+<tt>MachineOperand::isDef()</tt> informs if that registers is being
+defined.</p>
+
+<p>We will call physical registers present in the LLVM bitcode before
+register allocation <i>pre-colored registers</i>. Pre-colored
+registers are used in many different situations, for instance, to pass
+parameters of functions calls, and to store results of particular
+instructions. There are two types of pre-colored registers: the ones
+<i>implicitly</i> defined, and those <i>explicitly</i>
+defined. Explicitly defined registers are normal operands, and can be
+accessed with <tt>MachineInstr::getOperand(int)::getReg()</tt>. In
+order to check which registers are implicitly defined by an
+instruction, use the
+<tt>TargetInstrInfo::get(opcode)::ImplicitDefs</tt>, where
+<tt>opcode</tt> is the opcode of the target instruction. One important
+difference between explicit and implicit physical registers is that
+the latter are defined statically for each instruction, whereas the
+former may vary depending on the program being compiled. For example,
+an instruction that represents a function call will always implicitly
+define or use the same set of physical registers. To read the
+registers implicitly used by an instruction, use
+<tt>TargetInstrInfo::get(opcode)::ImplicitUses</tt>. Pre-colored
+registers impose constraints on any register allocation algorithm. The
+register allocator must make sure that none of them is been
+overwritten by the values of virtual registers while still alive.</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+
+<div class="doc_subsubsection">
+ <a name="regAlloc_howTo">Mapping virtual registers to physical registers</a>
+</div>
+
+<div class="doc_text">
+
+<p>There are two ways to map virtual registers to physical registers (or to
+memory slots). The first way, that we will call <i>direct mapping</i>,
+is based on the use of methods of the classes <tt>MRegisterInfo</tt>,
+and <tt>MachineOperand</tt>. The second way, that we will call
+<i>indirect mapping</i>, relies on the <tt>VirtRegMap</tt> class in
+order to insert loads and stores sending and getting values to and from
+memory.</p>
+
+<p>The direct mapping provides more flexibility to the developer of
+the register allocator; however, it is more error prone, and demands
+more implementation work. Basically, the programmer will have to
+specify where load and store instructions should be inserted in the
+target function being compiled in order to get and store values in
+memory. To assign a physical register to a virtual register present in
+a given operand, use <tt>MachineOperand::setReg(p_reg)</tt>. To insert
+a store instruction, use
+<tt>MRegisterInfo::storeRegToStackSlot(...)</tt>, and to insert a load
+instruction, use <tt>MRegisterInfo::loadRegFromStackSlot</tt>.</p>
+
+<p>The indirect mapping shields the application developer from the
+complexities of inserting load and store instructions. In order to map
+a virtual register to a physical one, use
+<tt>VirtRegMap::assignVirt2Phys(vreg, preg)</tt>. In order to map a
+certain virtual register to memory, use
+<tt>VirtRegMap::assignVirt2StackSlot(vreg)</tt>. This method will
+return the stack slot where <tt>vreg</tt>'s value will be located. If
+it is necessary to map another virtual register to the same stack
+slot, use <tt>VirtRegMap::assignVirt2StackSlot(vreg,
+stack_location)</tt>. One important point to consider when using the
+indirect mapping, is that even if a virtual register is mapped to
+memory, it still needs to be mapped to a physical register. This
+physical register is the location where the virtual register is
+supposed to be found before being stored or after being reloaded.</p>
+
+<p>If the indirect strategy is used, after all the virtual registers
+have been mapped to physical registers or stack slots, it is necessary
+to use a spiller object to place load and store instructions in the
+code. Every virtual that has been mapped to a stack slot will be
+stored to memory after been defined and will be loaded before being
+used. The implementation of the spiller tries to recycle load/store
+instructions, avoiding unnecessary instructions. For an example of how
+to invoke the spiller, see
+<tt>RegAllocLinearScan::runOnMachineFunction</tt> in
+<tt>lib/CodeGen/RegAllocLinearScan.cpp</tt>.</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="regAlloc_twoAddr">Handling two address instructions</a>
+</div>
+
+<div class="doc_text">
+
+<p>With very rare exceptions (e.g., function calls), the LLVM machine
+code instructions are three address instructions. That is, each
+instruction is expected to define at most one register, and to use at
+most two registers. However, some architectures use two address
+instructions. In this case, the defined register is also one of the
+used register. For instance, an instruction such as <tt>ADD %EAX,
+%EBX</tt>, in X86 is actually equivalent to <tt>%EAX = %EAX +
+%EBX</tt>.</p>
+
+<p>In order to produce correct code, LLVM must convert three address
+instructions that represent two address instructions into true two
+address instructions. LLVM provides the pass
+<tt>TwoAddressInstructionPass</tt> for this specific purpose. It must
+be run before register allocation takes place. After its execution,
+the resulting code may no longer be in SSA form. This happens, for
+instance, in situations where an instruction such as <tt>%a = ADD %b
+%c</tt> is converted to two instructions such as:</p>
+
+<div class="doc_code">
+<pre>
+%a = MOVE %b
+%a = ADD %a %b
+</pre>
+</div>
+
+<p>Notice that, internally, the second instruction is represented as
+<tt>ADD %a[def/use] %b</tt>. I.e., the register operand <tt>%a</tt> is
+both used and defined by the instruction.</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="regAlloc_ssaDecon">The SSA deconstruction phase</a>
+</div>
+
+<div class="doc_text">
+
+<p>An important transformation that happens during register allocation is called
+the <i>SSA Deconstruction Phase</i>. The SSA form simplifies many
+analyses that are performed on the control flow graph of
+programs. However, traditional instruction sets do not implement
+PHI instructions. Thus, in order to generate executable code, compilers
+must replace PHI instructions with other instructions that preserve their
+semantics.</p>
+
+<p>There are many ways in which PHI instructions can safely be removed
+from the target code. The most traditional PHI deconstruction
+algorithm replaces PHI instructions with copy instructions. That is
+the strategy adopted by LLVM. The SSA deconstruction algorithm is
+implemented in n<tt>lib/CodeGen/>PHIElimination.cpp</tt>. In order to
+invoke this pass, the identifier <tt>PHIEliminationID</tt> must be
+marked as required in the code of the register allocator.</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="regAlloc_fold">Instruction folding</a>
+</div>
+
+<div class="doc_text">
+
+<p><i>Instruction folding</i> is an optimization performed during
+register allocation that removes unnecessary copy instructions. For
+instance, a sequence of instructions such as:</p>
+
+<div class="doc_code">
+<pre>
+%EBX = LOAD %mem_address
+%EAX = COPY %EBX
+</pre>
+</div>
+
+<p>can be safely substituted by the single instruction:
+
+<div class="doc_code">
+<pre>
+%EAX = LOAD %mem_address
+</pre>
+</div>
+
+<p>Instructions can be folded with the
+<tt>MRegisterInfo::foldMemoryOperand(...)</tt> method. Care must be
+taken when folding instructions; a folded instruction can be quite
+different from the original instruction. See
+<tt>LiveIntervals::addIntervalsForSpills</tt> in
+<tt>lib/CodeGen/LiveIntervalAnalysis.cpp</tt> for an example of its use.</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+
+<div class="doc_subsubsection">
+ <a name="regAlloc_builtIn">Built in register allocators</a>
+</div>
+
+<div class="doc_text">
+
+<p>The LLVM infrastructure provides the application developer with
+three different register allocators:</p>
+
+<ul>
+ <li><i>Simple</i> - This is a very simple implementation that does
+ not keep values in registers across instructions. This register
+ allocator immediately spills every value right after it is
+ computed, and reloads all used operands from memory to temporary
+ registers before each instruction.</li>
+ <li><i>Local</i> - This register allocator is an improvement on the
+ <i>Simple</i> implementation. It allocates registers on a basic
+ block level, attempting to keep values in registers and reusing
+ registers as appropriate.</li>
+ <li><i>Linear Scan</i> - <i>The default allocator</i>. This is the
+ well-know linear scan register allocator. Whereas the
+ <i>Simple</i> and <i>Local</i> algorithms use a direct mapping
+ implementation technique, the <i>Linear Scan</i> implementation
+ uses a spiller in order to place load and stores.</li>
+</ul>
+
+<p>The type of register allocator used in <tt>llc</tt> can be chosen with the
+command line option <tt>-regalloc=...</tt>:</p>
+
+<div class="doc_code">
+<pre>
+$ llc -f -regalloc=simple file.bc -o sp.s;
+$ llc -f -regalloc=local file.bc -o lc.s;
+$ llc -f -regalloc=linearscan file.bc -o ln.s;
+</pre>
+</div>
+
+</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_text"><p>To Be Written</p></div>
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="codeemit_asm">Generating Assembly Code</a>
+</div>
+<div class="doc_text"><p>To Be Written</p></div>
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="codeemit_bin">Generating Binary Machine Code</a>
+</div>
+
+<div class="doc_text">
+ <p>For the JIT or <tt>.o</tt> file writer</p>
+</div>
+
+
+<!-- *********************************************************************** -->
+<div class="doc_section">
+ <a name="targetimpls">Target-specific Implementation Notes</a>
+</div>
+<!-- *********************************************************************** -->
+
+<div class="doc_text">
+
+<p>This section of the document explains features or design decisions that