diff options
Diffstat (limited to 'docs')
103 files changed, 33869 insertions, 0 deletions
diff --git a/docs/.cvsignore b/docs/.cvsignore new file mode 100644 index 0000000000..54953b3ca2 --- /dev/null +++ b/docs/.cvsignore @@ -0,0 +1,4 @@ +doxygen.cfg +doxygen +doxygen.out +*.tar.gz diff --git a/docs/AliasAnalysis.html b/docs/AliasAnalysis.html new file mode 100644 index 0000000000..d32aac593c --- /dev/null +++ b/docs/AliasAnalysis.html @@ -0,0 +1,953 @@ +<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" + "http://www.w3.org/TR/html4/strict.dtd"> +<html> +<head> + <title>LLVM Alias Analysis Infrastructure</title> + <link rel="stylesheet" href="llvm.css" type="text/css"> +</head> +<body> + +<div class="doc_title"> + LLVM Alias Analysis Infrastructure +</div> + +<ol> + <li><a href="#introduction">Introduction</a></li> + + <li><a href="#overview"><tt>AliasAnalysis</tt> Class Overview</a> + <ul> + <li><a href="#pointers">Representation of Pointers</a></li> + <li><a href="#alias">The <tt>alias</tt> method</a></li> + <li><a href="#ModRefInfo">The <tt>getModRefInfo</tt> methods</a></li> + <li><a href="#OtherItfs">Other useful <tt>AliasAnalysis</tt> methods</a></li> + </ul> + </li> + + <li><a href="#writingnew">Writing a new <tt>AliasAnalysis</tt> Implementation</a> + <ul> + <li><a href="#passsubclasses">Different Pass styles</a></li> + <li><a href="#requiredcalls">Required initialization calls</a></li> + <li><a href="#interfaces">Interfaces which may be specified</a></li> + <li><a href="#chaining"><tt>AliasAnalysis</tt> chaining behavior</a></li> + <li><a href="#updating">Updating analysis results for transformations</a></li> + <li><a href="#implefficiency">Efficiency Issues</a></li> + </ul> + </li> + + <li><a href="#using">Using alias analysis results</a> + <ul> + <li><a href="#loadvn">Using the <tt>-load-vn</tt> Pass</a></li> + <li><a href="#ast">Using the <tt>AliasSetTracker</tt> class</a></li> + <li><a href="#direct">Using the <tt>AliasAnalysis</tt> interface directly</a></li> + </ul> + </li> + + <li><a href="#exist">Existing alias analysis implementations and clients</a> + <ul> + <li><a href="#impls">Available <tt>AliasAnalysis</tt> implementations</a></li> + <li><a href="#aliasanalysis-xforms">Alias analysis driven transformations</a></li> + <li><a href="#aliasanalysis-debug">Clients for debugging and evaluation of + implementations</a></li> + </ul> + </li> +</ol> + +<div class="doc_author"> + <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p> +</div> + +<!-- *********************************************************************** --> +<div class="doc_section"> + <a name="introduction">Introduction</a> +</div> +<!-- *********************************************************************** --> + +<div class="doc_text"> + +<p>Alias Analysis (aka Pointer Analysis) is a class of techniques which attempt +to determine whether or not two pointers ever can point to the same object in +memory. There are many different algorithms for alias analysis and many +different ways of classifying them: flow-sensitive vs flow-insensitive, +context-sensitive vs context-insensitive, field-sensitive vs field-insensitive, +unification-based vs subset-based, etc. Traditionally, alias analyses respond +to a query with a <a href="#MustNoMay">Must, May, or No</a> alias response, +indicating that two pointers always point to the same object, might point to the +same object, or are known to never point to the same object.</p> + +<p>The LLVM <a +href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1AliasAnalysis.html"><tt>AliasAnalysis</tt></a> +class is the primary interface used by clients and implementations of alias +analyses in the LLVM system. This class is the common interface between clients +of alias analysis information and the implementations providing it, and is +designed to support a wide range of implementations and clients (but currently +all clients are assumed to be flow-insensitive). In addition to simple alias +analysis information, this class exposes Mod/Ref information from those +implementations which can provide it, allowing for powerful analyses and +transformations to work well together.</p> + +<p>This document contains information necessary to successfully implement this +interface, use it, and to test both sides. It also explains some of the finer +points about what exactly results mean. If you feel that something is unclear +or should be added, please <a href="mailto:sabre@nondot.org">let me +know</a>.</p> + +</div> + +<!-- *********************************************************************** --> +<div class="doc_section"> + <a name="overview"><tt>AliasAnalysis</tt> Class Overview</a> +</div> +<!-- *********************************************************************** --> + +<div class="doc_text"> + +<p>The <a +href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1AliasAnalysis.html"><tt>AliasAnalysis</tt></a> +class defines the interface that the various alias analysis implementations +should support. This class exports two important enums: <tt>AliasResult</tt> +and <tt>ModRefResult</tt> which represent the result of an alias query or a +mod/ref query, respectively.</p> + +<p>The <tt>AliasAnalysis</tt> interface exposes information about memory, +represented in several different ways. In particular, memory objects are +represented as a starting address and size, and function calls are represented +as the actual <tt>call</tt> or <tt>invoke</tt> instructions that performs the +call. The <tt>AliasAnalysis</tt> interface also exposes some helper methods +which allow you to get mod/ref information for arbitrary instructions.</p> + +</div> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="pointers">Representation of Pointers</a> +</div> + +<div class="doc_text"> + +<p>Most importantly, the <tt>AliasAnalysis</tt> class provides several methods +which are used to query whether or not two memory objects alias, whether +function calls can modify or read a memory object, etc. For all of these +queries, memory objects are represented as a pair of their starting address (a +symbolic LLVM <tt>Value*</tt>) and a static size.</p> + +<p>Representing memory objects as a starting address and a size is critically +important for correct Alias Analyses. For example, consider this (silly, but +possible) C code:</p> + +<div class="doc_code"> +<pre> +int i; +char C[2]; +char A[10]; +/* ... */ +for (i = 0; i != 10; ++i) { + C[0] = A[i]; /* One byte store */ + C[1] = A[9-i]; /* One byte store */ +} +</pre> +</div> + +<p>In this case, the <tt>basicaa</tt> pass will disambiguate the stores to +<tt>C[0]</tt> and <tt>C[1]</tt> because they are accesses to two distinct +locations one byte apart, and the accesses are each one byte. In this case, the +LICM pass can use store motion to remove the stores from the loop. In +constrast, the following code:</p> + +<div class="doc_code"> +<pre> +int i; +char C[2]; +char A[10]; +/* ... */ +for (i = 0; i != 10; ++i) { + ((short*)C)[0] = A[i]; /* Two byte store! */ + C[1] = A[9-i]; /* One byte store */ +} +</pre> +</div> + +<p>In this case, the two stores to C do alias each other, because the access to +the <tt>&C[0]</tt> element is a two byte access. If size information wasn't +available in the query, even the first case would have to conservatively assume +that the accesses alias.</p> + +</div> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="alias">The <tt>alias</tt> method</a> +</div> + +<div class="doc_text"> +The <tt>alias</tt> method is the primary interface used to determine whether or +not two memory objects alias each other. It takes two memory objects as input +and returns MustAlias, MayAlias, or NoAlias as appropriate. +</div> + +<!-- _______________________________________________________________________ --> +<div class="doc_subsubsection"> + <a name="MustMayNo">Must, May, and No Alias Responses</a> +</div> + +<div class="doc_text"> + +<p>An Alias Analysis implementation can return one of three responses: +MustAlias, MayAlias, and NoAlias. The No and May alias results are obvious: if +the two pointers can never equal each other, return NoAlias, if they might, +return MayAlias.</p> + +<p>The MustAlias response is trickier though. In LLVM, the Must Alias response +may only be returned if the two memory objects are guaranteed to always start at +exactly the same location. If two memory objects overlap, but do not start at +the same location, return MayAlias.</p> + +</div> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="ModRefInfo">The <tt>getModRefInfo</tt> methods</a> +</div> + +<div class="doc_text"> + +<p>The <tt>getModRefInfo</tt> methods return information about whether the +execution of an instruction can read or modify a memory location. Mod/Ref +information is always conservative: if an instruction <b>might</b> read or write +a location, ModRef is returned.</p> + +<p>The <tt>AliasAnalysis</tt> class also provides a <tt>getModRefInfo</tt> +method for testing dependencies between function calls. This method takes two +call sites (CS1 & CS2), returns NoModRef if the two calls refer to disjoint +memory locations, Ref if CS1 reads memory written by CS2, Mod if CS1 writes to +memory read or written by CS2, or ModRef if CS1 might read or write memory +accessed by CS2. Note that this relation is not commutative. Clients that use +this method should be predicated on the <tt>hasNoModRefInfoForCalls()</tt> +method, which indicates whether or not an analysis can provide mod/ref +information for function call pairs (most can not). If this predicate is false, +the client shouldn't waste analysis time querying the <tt>getModRefInfo</tt> +method many times.</p> |