Process</a></li>
<li><a href="#selectiondag_build">Initial SelectionDAG
Construction</a></li>
+ <li><a href="#selectiondag_legalize_types">SelectionDAG LegalizeTypes Phase</a></li>
<li><a href="#selectiondag_legalize">SelectionDAG Legalize Phase</a></li>
<li><a href="#selectiondag_optimize">SelectionDAG Optimization
Phase: the DAG Combiner</a></li>
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
+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
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>
+<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>
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_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
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.
+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>
<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
+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 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>
+<p>The Legalize phase is in charge of converting a DAG to only use the
+operations that are natively supported by the target.</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>
+<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>
-<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>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 existance of the Legalize pass, we required that every target
+<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 phase allows all of the cannonicalization patterns to be shared
-across targets, and makes it very easy to optimize the cannonicalized code
+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_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
+<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). 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
+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
<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>
+"<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
<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
+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>
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
+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 class="doc_code">
<pre>
%a = MOVE %b
-%a = ADD %a %b
+%a = ADD %a %c
</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
+<tt>ADD %a[def/use] %c</tt>. I.e., the register operand <tt>%a</tt> is
both used and defined by the instruction.</p>
</div>
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
+implemented in <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>
</pre>
</div>
-<p>can be safely substituted by the single instruction:
+<p>can be safely substituted by the single instruction:</p>
<div class="doc_code">
<pre>
<div class="doc_text">
-<p>The folowing target-specific calling conventions are known to backend:</p>
+<p>The following target-specific calling conventions are known to backend:</p>
<ul>
<li><b>x86_StdCall</b> - stdcall calling convention seen on Microsoft Windows
not passed the -fomit-frame-pointer flag. The stack pointer is always aligned to
16 bytes, so that space allocated for altivec vectors will be properly
aligned.</p>
-<p>An invocation frame is layed out as follows (low memory at top);</p>
+<p>An invocation frame is laid out as follows (low memory at top);</p>
</div>
<div class="doc_text">
there are not enough registers or the callee is a thunk or vararg function,
these register arguments can be spilled into the parameter area. Thus, the
parameter area must be large enough to store all the parameters for the largest
-call sequence made by the caller. The size must also be mimimally large enough
+call sequence made by the caller. The size must also be minimally large enough
to spill registers r3-r10. This allows callees blind to the call signature,
such as thunks and vararg functions, enough space to cache the argument
registers. Therefore, the parameter area is minimally 32 bytes (64 bytes in 64
linkage and parameter areas. The cost of shifting the linkage and parameter
areas is minor since only the link value needs to be copied. The link value can
be easily fetched by adding the original frame size to the base pointer. Note
-that allocations in the dynamic space need to observe 16 byte aligment.</p>
+that allocations in the dynamic space need to observe 16 byte alignment.</p>
</div>
<div class="doc_text">
<hr>
<address>
<a href="http://jigsaw.w3.org/css-validator/check/referer"><img
- src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
+ src="http://jigsaw.w3.org/css-validator/images/vcss-blue" alt="Valid CSS"></a>
<a href="http://validator.w3.org/check/referer"><img
- src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!" /></a>
+ src="http://www.w3.org/Icons/valid-html401-blue" alt="Valid HTML 4.01"></a>
<a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
<a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
projects / oota-llvm.git / blobdiff