Some documentation for LegalizeTypes.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@59962 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 78 insertions, 54 deletions

diff --git a/docs/CodeGenerator.html b/docs/CodeGenerator.html
index a43baee..10d2de3 100644
--- a/docs/CodeGenerator.html
+++ b/docs/CodeGenerator.html
@@ -50,6 +50,7 @@
                                           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>
@@ -813,8 +814,9 @@ basic block function it would be the return node.</p>
 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>
 
@@ -837,12 +839,18 @@ an illegal DAG into a legal DAG.</p>
     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
@@ -876,7 +884,7 @@ add support for it).</p>
 <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 relevent for scheduling
+immediate operands and other nodes that aren't relevant for scheduling
 omitted.
 </p>
 
@@ -903,51 +911,67 @@ returns, varargs, etc.  For these features, the
 
 <!-- _______________________________________________________________________ -->
 <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 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>
@@ -960,12 +984,12 @@ because it is still in the form of a DAG.</p>
 
 <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
@@ -1228,7 +1252,7 @@ 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
+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>
 
@@ -1722,7 +1746,7 @@ that people test.</p>
 
 <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
@@ -1829,7 +1853,7 @@ pointer is free to grow or shrink.  A base pointer is also used if llvm-gcc is
 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">
@@ -1938,7 +1962,7 @@ passed in registers, with the space in the parameter area unused.  However, if
 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
@@ -1960,7 +1984,7 @@ shifted to top of stack, and the new space is available immediately below the
 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">