diff options
author | Gordon Henriksen <gordonhenriksen@mac.com> | 2007-10-25 10:18:27 +0000 |
---|---|---|
committer | Gordon Henriksen <gordonhenriksen@mac.com> | 2007-10-25 10:18:27 +0000 |
commit | 951bc79a55cc4429958fb65e01dc8e22ba8cfc9d (patch) | |
tree | 41a707192941633fbd22ec60ee64ab4d0a267ffe /docs/Passes.html | |
parent | 335d87d3106fa32c5939b2dfa20af21c3e12bf9e (diff) | |
download | external_llvm-951bc79a55cc4429958fb65e01dc8e22ba8cfc9d.zip external_llvm-951bc79a55cc4429958fb65e01dc8e22ba8cfc9d.tar.gz external_llvm-951bc79a55cc4429958fb65e01dc8e22ba8cfc9d.tar.bz2 |
Fleshing out docs/Passes.html for some analyses.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@43337 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'docs/Passes.html')
-rw-r--r-- | docs/Passes.html | 222 |
1 files changed, 193 insertions, 29 deletions
diff --git a/docs/Passes.html b/docs/Passes.html index efa69fe..fb1359f 100644 --- a/docs/Passes.html +++ b/docs/Passes.html @@ -34,6 +34,10 @@ while (<HELP>) { print @x, @y; EOT +This (real) one-liner can also be helpful when converting comments to HTML: + +perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print " <p>\n" if !$on && $_ =~ /\S/; print " </p>\n" if $on && $_ =~ /^\s*$/; print " $_\n"; $on = ($_ =~ /\S/); } print " </p>\n" if $on' + --> <div class="doc_title">LLVM's Analysis and Transform Passes</div> @@ -46,7 +50,8 @@ EOT </ol> <div class="doc_author"> - <p>Written by <a href="mailto:rspencer@x10sys.com">Reid Spencer</a></p> + <p>Written by <a href="mailto:rspencer@x10sys.com">Reid Spencer</a> + and Gordon Henriksen</p> </div> <!-- ======================================================================= --> @@ -84,7 +89,6 @@ EOT <tr><td><a href="#domtree">-domtree</a></td><td>Dominator Tree Construction</td></tr> <tr><td><a href="#externalfnconstants">-externalfnconstants</a></td><td>Print external fn callsites passed constants</td></tr> <tr><td><a href="#globalsmodref-aa">-globalsmodref-aa</a></td><td>Simple mod/ref analysis for globals</td></tr> -<tr><td><a href="#gvn">-gvn</a></td><td>Global Value Numbering</td></tr> <tr><td><a href="#instcount">-instcount</a></td><td>Counts the various types of Instructions</td></tr> <tr><td><a href="#intervals">-intervals</a></td><td>Interval Partition Construction</td></tr> <tr><td><a href="#load-vn">-load-vn</a></td><td>Load Value Numbering</td></tr> @@ -124,6 +128,7 @@ EOT <tr><td><a href="#gcse">-gcse</a></td><td>Global Common Subexpression Elimination</td></tr> <tr><td><a href="#globaldce">-globaldce</a></td><td>Dead Global Elimination</td></tr> <tr><td><a href="#globalopt">-globalopt</a></td><td>Global Variable Optimizer</td></tr> +<tr><td><a href="#gvn">-gvn</a></td><td>Global Value Numbering</td></tr> <tr><td><a href="#gvnpre">-gvnpre</a></td><td>Global Value Numbering/Partial Redundancy Elimination</td></tr> <tr><td><a href="#indmemrem">-indmemrem</a></td><td>Indirect Malloc and Free Removal</td></tr> <tr><td><a href="#indvars">-indvars</a></td><td>Canonicalize Induction Variables</td></tr> @@ -192,7 +197,13 @@ EOT <a name="aa-eval">Exhaustive Alias Analysis Precision Evaluator</a> </div> <div class="doc_text"> - <p>Yet to be written.</p> + <p>This is a simple N^2 alias analysis accuracy evaluator. + Basically, for each function in the program, it simply queries to see how the + alias analysis implementation answers alias queries between each pair of + pointers in the function.</p> + + <p>This is inspired and adapted from code by: Naveen Neelakantam, Francesco + Spadini, and Wojciech Stryjewski.</p> </div> <!-------------------------------------------------------------------------- --> @@ -200,7 +211,67 @@ EOT <a name="anders-aa">Andersen's Interprocedural Alias Analysis</a> </div> <div class="doc_text"> - <p>Yet to be written.</p> + <p> + This is an implementation of Andersen's interprocedural alias + analysis + </p> + + <p> + In pointer analysis terms, this is a subset-based, flow-insensitive, + field-sensitive, and context-insensitive algorithm pointer algorithm. + </p> + + <p> + This algorithm is implemented as three stages: + </p> + + <ol> + <li>Object identification.</li> + <li>Inclusion constraint identification.</li> + <li>Offline constraint graph optimization.</li> + <li>Inclusion constraint solving.</li> + </ol> + + <p> + The object identification stage identifies all of the memory objects in the + program, which includes globals, heap allocated objects, and stack allocated + objects. + </p> + + <p> + The inclusion constraint identification stage finds all inclusion constraints + in the program by scanning the program, looking for pointer assignments and + other statements that effect the points-to graph. For a statement like + <code><var>A</var> = <var>B</var></code>, this statement is processed to + indicate that <var>A</var> can point to anything that <var>B</var> can point + to. Constraints can handle copies, loads, and stores, and address taking. + </p> + + <p> + The offline constraint graph optimization portion includes offline variable + substitution algorithms intended to computer pointer and location + equivalences. Pointer equivalences are those pointers that will have the + same points-to sets, and location equivalences are those variables that + always appear together in points-to sets. + </p> + + <p> + The inclusion constraint solving phase iteratively propagates the inclusion + constraints until a fixed point is reached. This is an O(<var>n</var>³) + algorithm. + </p> + + <p> + Function constraints are handled as if they were structs with <var>X</var> + fields. Thus, an access to argument <var>X</var> of function <var>Y</var> is + an access to node index <code>getNode(<var>Y</var>) + <var>X</var></code>. + This representation allows handling of indirect calls without any issues. To + wit, an indirect call <code><var>Y</var>(<var>a</var>,<var>b</var>)</code> is + equivalent to <code>*(<var>Y</var> + 1) = <var>a</var>, *(<var>Y</var> + 2) = + <var>b</var></code>. The return node for a function <var>F</var> is always + located at <code>getNode(<var>F</var>) + CallReturnPos</code>. The arguments + start at <code>getNode(<var>F</var>) + CallArgPos</code>. + </p> </div> <!-------------------------------------------------------------------------- --> @@ -208,7 +279,11 @@ EOT <a name="basicaa">Basic Alias Analysis (default AA impl)</a> </div> <div class="doc_text"> - <p>Yet to be written.</p> + <p> + This is the default implementation of the Alias Analysis interface + that simply implements a few identities (two different globals cannot alias, + etc), but otherwise does no analysis. + </p> </div> <!-------------------------------------------------------------------------- --> @@ -224,7 +299,12 @@ EOT <a name="basicvn">Basic Value Numbering (default GVN impl)</a> </div> <div class="doc_text"> - <p>Yet to be written.</p> + <p> + This is the default implementation of the <code>ValueNumbering</code> + interface. It walks the SSA def-use chains to trivially identify + lexically identical expressions. This does not require any ahead of time + analysis, so it is a very fast default implementation. + </p> </div> <!-------------------------------------------------------------------------- --> @@ -232,7 +312,11 @@ EOT <a name="callgraph">Print a call graph</a> </div> <div class="doc_text"> - <p>Yet to be written.</p> + <p> + This pass, only available in <code>opt</code>, prints + the call graph into a <code>.dot</code> graph. This graph can then be processed with the + "dot" tool to convert it to postscript or some other suitable format. + </p> </div> <!-------------------------------------------------------------------------- --> @@ -240,7 +324,10 @@ EOT <a name="callscc">Print SCCs of the Call Graph</a> </div> <div class="doc_text"> - <p>Yet to be written.</p> + <p> + This pass, only available in <code>opt</code>, prints + the SCCs of the call graph to standard output in a human-readable form. + </p> </div> <!-------------------------------------------------------------------------- --> @@ -248,7 +335,10 @@ EOT <a name="cfgscc">Print SCCs of each function CFG</a> </div> <div class="doc_text"> - <p>Yet to be written.</p> + <p> + This pass, only available in <code>opt</code>, prints + the SCCs of each function CFG to standard output in a human-readable form. + </p> </div> <!-------------------------------------------------------------------------- --> @@ -256,7 +346,11 @@ EOT <a name="codegenprepare">Optimize for code generation</a> </div> <div class="doc_text"> - <p>Yet to be written.</p> + <p> + This pass munges the code in the input function to better prepare it for + SelectionDAG-based code generation. This works around limitations in it's + basic-block-at-a-time approach. It should eventually be removed. + </p> </div> <!-------------------------------------------------------------------------- --> @@ -264,7 +358,10 @@ EOT <a name="count-aa">Count Alias Analysis Query Responses</a> </div> <div class="doc_text"> - <p>Yet to be written.</p> + <p> + A pass which can be used to count how many alias queries + are being made and how the alias analysis implementation being used responds. + </p> </div> <!-------------------------------------------------------------------------- --> @@ -272,7 +369,16 @@ EOT <a name="debug-aa">AA use debugger</a> </div> <div class="doc_text"> - <p>Yet to be written.</p> + <p> + This simple pass checks alias analysis users to ensure that if they + create a new value, they do not query AA without informing it of the value. + It acts as a shim over any other AA pass you want. + </p> + + <p> + Yes keeping track of every value in the program is expensive, but this is + a debugging pass. + </p> </div> <!-------------------------------------------------------------------------- --> @@ -280,7 +386,10 @@ EOT <a name="domfrontier">Dominance Frontier Construction</a> </div> <div class="doc_text"> - <p>Yet to be written.</p> + <p> + This pass is a simple dominator construction algorithm for finding forward + dominator frontiers. + </p> </div> <!-------------------------------------------------------------------------- --> @@ -288,7 +397,10 @@ EOT <a name="domtree">Dominator Tree Construction</a> </div> <div class="doc_text"> - <p>Yet to be written.</p> + <p> + This pass is a simple dominator construction algorithm for finding forward + dominators. + </p> </div> <!-------------------------------------------------------------------------- --> @@ -296,7 +408,12 @@ EOT <a name="externalfnconstants">Print external fn callsites passed constants</a> </div> <div class="doc_text"> - <p>Yet to be written.</p> + <p> + This pass, only available in <code>opt</code>, prints out call sites to + external functions that are called with constant arguments. This can be + useful when looking for standard library functions we should constant fold + or handle in alias analyses. + </p> </div> <!-------------------------------------------------------------------------- --> @@ -304,15 +421,12 @@ EOT <a name="globalsmodref-aa">Simple mod/ref analysis for globals</a> </div> <div class="doc_text"> - <p>Yet to be written.</p> -</div> - -<!-------------------------------------------------------------------------- --> -<div class="doc_subsection"> - <a name="gvn">Global Value Numbering</a> -</div> -<div class="doc_text"> - <p>Yet to be written.</p> + <p> + This simple pass provides alias and mod/ref information for global values + that do not have their address taken, and keeps track of whether functions + read or write memory (are "pure"). For this simple (but very common) case, + we can provide pretty accurate and useful information. + </p> </div> <!-------------------------------------------------------------------------- --> @@ -320,7 +434,9 @@ EOT <a name="instcount">Counts the various types of Instructions</a> </div> <div class="doc_text"> - <p>Yet to be written.</p> + <p> + This pass collects the count of all instructions and reports them + </p> </div> <!-------------------------------------------------------------------------- --> @@ -328,7 +444,15 @@ EOT <a name="intervals">Interval Partition Construction</a> </div> <div class="doc_text"> - <p>Yet to be written.</p> + <p> + This analysis calculates and represents the interval partition of a function, + or a preexisting interval partition. + </p> + + <p> + In this way, the interval partition may be used to reduce a flow graph down + to its degenerate single node interval partition (unless it is irreducible). + </p> </div> <!-------------------------------------------------------------------------- --> @@ -336,7 +460,21 @@ EOT <a name="load-vn">Load Value Numbering</a> </div> <div class="doc_text"> - <p>Yet to be written.</p> + <p> + This pass value numbers load and call instructions. To do this, it finds + lexically identical load instructions, and uses alias analysis to determine + which loads are guaranteed to produce the same value. To value number call + instructions, it looks for calls to functions that do not write to memory + which do not have intervening instructions that clobber the memory that is + read from. + </p> + + <p> + This pass builds off of another value numbering pass to implement value + numbering for non-load and non-call instructions. It uses Alias Analysis so + that it can disambiguate the load instructions. The more powerful these base + analyses are, the more powerful the resultant value numbering will be. + </p> </div> <!-------------------------------------------------------------------------- --> @@ -344,7 +482,12 @@ EOT <a name="loops">Natural Loop Construction</a> </div> <div class="doc_text"> - <p>Yet to be written.</p> + <p> + This analysis is used to identify natural loops and determine the loop depth + of various nodes of the CFG. Note that the loops identified may actually be + several natural loops that share the same header node... not just a single + natural loop. + </p> </div> <!-------------------------------------------------------------------------- --> @@ -506,6 +649,7 @@ EOT Code Positioning" by Pettis and Hansen, except that it uses basic block counts instead of edge counts. This could be improved in many ways, but is very simple for now.</p> + <p>Basically we "place" the entry block, then loop over all successors in a DFO, placing the most frequently executed successor until we run out of blocks. Did we mention that this was <b>extremely</b> simplistic? This is @@ -646,10 +790,30 @@ if (i == j) <!-------------------------------------------------------------------------- --> <div class="doc_subsection"> + <a name="gvn">Global Value Numbering</a> +</div> +<div class="doc_text"> + <p> + This pass performs global value numbering to eliminate fully redundant + instructions. It also performs simple dead load elimination. + </p> +</div> + +<!-------------------------------------------------------------------------- --> +<div class="doc_subsection"> <a name="gvnpre">Global Value Numbering/Partial Redundancy Elimination</a> </div> <div class="doc_text"> - <p>Yet to be written.</p> + <p> + This pass performs a hybrid of global value numbering and partial redundancy + elimination, known as GVN-PRE. It performs partial redundancy elimination on + values, rather than lexical expressions, allowing a more comprehensive view + the optimization. It replaces redundant values with uses of earlier + occurences of the same value. While this is beneficial in that it eliminates + unneeded computation, it also increases register pressure by creating large + live ranges, and should be used with caution on platforms that are very + sensitive to register pressure. + </p> </div> <!-------------------------------------------------------------------------- --> |