diff options
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/AliasAnalysis.html | 23 | ||||
| -rw-r--r-- | docs/Passes.html | 75 | ||||
| -rw-r--r-- | docs/ReleaseNotes.html | 2 |
3 files changed, 2 insertions, 98 deletions
diff --git a/docs/AliasAnalysis.html b/docs/AliasAnalysis.html index ebf6386..5b4eb93 100644 --- a/docs/AliasAnalysis.html +++ b/docs/AliasAnalysis.html @@ -403,7 +403,7 @@ implementing, you just override the interfaces you can improve.</p> href="#basic-aa">basicaa</a></tt> and <a href="#no-aa"><tt>no-aa</tt></a> passes) every alias analysis pass chains to another alias analysis implementation (for example, the user can specify "<tt>-basicaa -ds-aa --anders-aa -licm</tt>" to get the maximum benefit from the three alias +-licm</tt>" to get the maximum benefit from both alias analyses). The alias analysis class automatically takes care of most of this for methods that you don't override. For methods that you do override, in code paths that return a conservative MayAlias or Mod/Ref result, simply return @@ -705,25 +705,6 @@ non-address taken globals), but is very quick analysis.</p> <!-- _______________________________________________________________________ --> <div class="doc_subsubsection"> - <a name="anders-aa">The <tt>-anders-aa</tt> pass</a> -</div> - -<div class="doc_text"> - -<p>The <tt>-anders-aa</tt> pass implements the well-known "Andersen's algorithm" -for interprocedural alias analysis. This algorithm is a subset-based, -flow-insensitive, context-insensitive, and field-insensitive alias analysis that -is widely believed to be fairly precise. Unfortunately, this algorithm is also -O(N<sup>3</sup>). The LLVM implementation currently does not implement any of -the refinements (such as "online cycle elimination" or "offline variable -substitution") to improve its efficiency, so it can be quite slow in common -cases. -</p> - -</div> - -<!-- _______________________________________________________________________ --> -<div class="doc_subsubsection"> <a name="steens-aa">The <tt>-steens-aa</tt> pass</a> </div> @@ -855,7 +836,7 @@ pointer.</p> <div class="doc_text"> <p>These passes are useful for evaluating the various alias analysis -implementations. You can use them with commands like '<tt>opt -anders-aa -ds-aa +implementations. You can use them with commands like '<tt>opt -ds-aa -aa-eval foo.bc -disable-output -stats</tt>'.</p> </div> diff --git a/docs/Passes.html b/docs/Passes.html index bbf6b3d..a2bacf9 100644 --- a/docs/Passes.html +++ b/docs/Passes.html @@ -75,7 +75,6 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print " <p>\n" if ! <tr><th colspan="2"><b>ANALYSIS PASSES</b></th></tr> <tr><th>Option</th><th>Name</th></tr> <tr><td><a href="#aa-eval">-aa-eval</a></td><td>Exhaustive Alias Analysis Precision Evaluator</td></tr> -<tr><td><a href="#anders-aa">-anders-aa</a></td><td>Andersen's Interprocedural Alias Analysis</td></tr> <tr><td><a href="#basicaa">-basicaa</a></td><td>Basic Alias Analysis (default AA impl)</td></tr> <tr><td><a href="#basiccg">-basiccg</a></td><td>Basic CallGraph Construction</td></tr> <tr><td><a href="#codegenprepare">-codegenprepare</a></td><td>Optimize for code generation</td></tr> @@ -204,80 +203,6 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print " <p>\n" if ! <!-------------------------------------------------------------------------- --> <div class="doc_subsection"> - <a name="anders-aa">Andersen's Interprocedural Alias Analysis</a> -</div> -<div class="doc_text"> - <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> - - <p> - Please keep in mind that the current andersen's pass has many known - problems and bugs. It should be considered "research quality". - </p> - -</div> - -<!-------------------------------------------------------------------------- --> -<div class="doc_subsection"> <a name="basicaa">Basic Alias Analysis (default AA impl)</a> </div> <div class="doc_text"> diff --git a/docs/ReleaseNotes.html b/docs/ReleaseNotes.html index 84200c3..3b96432 100644 --- a/docs/ReleaseNotes.html +++ b/docs/ReleaseNotes.html @@ -66,7 +66,6 @@ Almost dead code. llvm/Analysis/PointerTracking.h => Edwin wants this, consider for 2.8. ABCD, SCCVN, GEPSplitterPass MSIL backend? - AndersAA -> Unsupported, zap after branch. --> @@ -734,7 +733,6 @@ href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">LLVMdev list</a>.</p> experimental.</li> <li>The <tt>llc</tt> "<tt>-filetype=asm</tt>" (the default) is the only supported value for this option. The ELF writer is experimental.</li> -<li>The implementation of Andersen's Alias Analysis has many known bugs.</li> </ul> </div> |