Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 1 | <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" |
| 2 | "http://www.w3.org/TR/html4/strict.dtd"> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 3 | <html> |
| 4 | <head> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 5 | <title>The LLVM Alias Analysis Infrastructure</title> |
Misha Brukman | 6e4afd0 | 2004-01-15 19:04:12 +0000 | [diff] [blame] | 6 | <link rel="stylesheet" href="llvm.css" type="text/css"> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 7 | </head> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 8 | <body> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 9 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 10 | <div class="doc_title"> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 11 | The LLVM Alias Analysis Infrastructure |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 12 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 13 | |
| 14 | <ol> |
Misha Brukman | b215425 | 2003-10-23 02:29:42 +0000 | [diff] [blame] | 15 | <li><a href="#introduction">Introduction</a></li> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 16 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 17 | <li><a href="#overview"><tt>AliasAnalysis</tt> Class Overview</a> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 18 | <ul> |
Misha Brukman | b215425 | 2003-10-23 02:29:42 +0000 | [diff] [blame] | 19 | <li><a href="#pointers">Representation of Pointers</a></li> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 20 | <li><a href="#alias">The <tt>alias</tt> method</a></li> |
Misha Brukman | b215425 | 2003-10-23 02:29:42 +0000 | [diff] [blame] | 21 | <li><a href="#ModRefInfo">The <tt>getModRefInfo</tt> methods</a></li> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 22 | <li><a href="#OtherItfs">Other useful <tt>AliasAnalysis</tt> methods</a></li> |
| 23 | </ul> |
| 24 | </li> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 25 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 26 | <li><a href="#writingnew">Writing a new <tt>AliasAnalysis</tt> Implementation</a> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 27 | <ul> |
Misha Brukman | b215425 | 2003-10-23 02:29:42 +0000 | [diff] [blame] | 28 | <li><a href="#passsubclasses">Different Pass styles</a></li> |
| 29 | <li><a href="#requiredcalls">Required initialization calls</a></li> |
| 30 | <li><a href="#interfaces">Interfaces which may be specified</a></li> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 31 | <li><a href="#chaining"><tt>AliasAnalysis</tt> chaining behavior</a></li> |
| 32 | <li><a href="#updating">Updating analysis results for transformations</a></li> |
Misha Brukman | b215425 | 2003-10-23 02:29:42 +0000 | [diff] [blame] | 33 | <li><a href="#implefficiency">Efficiency Issues</a></li> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 34 | </ul> |
| 35 | </li> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 36 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 37 | <li><a href="#using">Using alias analysis results</a> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 38 | <ul> |
Misha Brukman | b215425 | 2003-10-23 02:29:42 +0000 | [diff] [blame] | 39 | <li><a href="#loadvn">Using the <tt>-load-vn</tt> Pass</a></li> |
| 40 | <li><a href="#ast">Using the <tt>AliasSetTracker</tt> class</a></li> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 41 | <li><a href="#direct">Using the <tt>AliasAnalysis</tt> interface directly</a></li> |
| 42 | </ul> |
| 43 | </li> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 44 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 45 | <li><a href="#exist">Existing alias analysis implementations and clients</a> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 46 | <ul> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 47 | <li><a href="#impls">Available <tt>AliasAnalysis</tt> implementations</a></li> |
| 48 | <li><a href="#aliasanalysis-xforms">Alias analysis driven transformations</a></li> |
| 49 | <li><a href="#aliasanalysis-debug">Clients for debugging and evaluation of implementations</a></li> |
| 50 | </ul> |
| 51 | </li> |
Misha Brukman | b215425 | 2003-10-23 02:29:42 +0000 | [diff] [blame] | 52 | </ol> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 53 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 54 | <div class="doc_author"> |
| 55 | <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 56 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 57 | |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 58 | <!-- *********************************************************************** --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 59 | <div class="doc_section"> |
| 60 | <a name="introduction">Introduction</a> |
| 61 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 62 | <!-- *********************************************************************** --> |
| 63 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 64 | <div class="doc_text"> |
Misha Brukman | 1f254d5 | 2003-11-21 22:30:25 +0000 | [diff] [blame] | 65 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 66 | <p>Alias Analysis (aka Pointer Analysis) is a class of techniques which attempt |
| 67 | to determine whether or not two pointers ever can point to the same object in |
| 68 | memory. There are many different algorithms for alias analysis and many |
| 69 | different ways of classifying them: flow-sensitive vs flow-insensitive, |
| 70 | context-sensitive vs context-insensitive, field-sensitive vs field-insensitive, |
| 71 | unification-based vs subset-based, etc. Traditionally, alias analyses respond |
| 72 | to a query with a <a href="#MustNoMay">Must, May, or No</a> alias response, |
| 73 | indicating that two pointers always point to the same object, might point to the |
| 74 | same object, or are known to never point to the same object.</p> |
Misha Brukman | 1f254d5 | 2003-11-21 22:30:25 +0000 | [diff] [blame] | 75 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 76 | <p>The LLVM <a |
| 77 | href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1AliasAnalysis.html"><tt>AliasAnalysis</tt></a> |
| 78 | class is the primary interface used by clients and implementations of alias |
| 79 | analyses in the LLVM system. This class is the common interface between clients |
| 80 | of alias analysis information and the implementations providing it, and is |
| 81 | designed to support a wide range of implementations and clients (but currently |
| 82 | all clients are assumed to be flow-insensitive). In addition to simple alias |
| 83 | analysis information, this class exposes Mod/Ref information from those |
| 84 | implementations which can provide it, allowing for powerful analyses and |
| 85 | transformations to work well together.</p> |
Misha Brukman | 1f254d5 | 2003-11-21 22:30:25 +0000 | [diff] [blame] | 86 | |
| 87 | <p>This document contains information necessary to successfully implement this |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 88 | interface, use it, and to test both sides. It also explains some of the finer |
| 89 | points about what exactly results mean. If you feel that something is unclear |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 90 | or should be added, please <a href="mailto:sabre@nondot.org">let me |
Misha Brukman | 1f254d5 | 2003-11-21 22:30:25 +0000 | [diff] [blame] | 91 | know</a>.</p> |
| 92 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 93 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 94 | |
| 95 | <!-- *********************************************************************** --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 96 | <div class="doc_section"> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 97 | <a name="overview"><tt>AliasAnalysis</tt> Class Overview</a> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 98 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 99 | <!-- *********************************************************************** --> |
| 100 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 101 | <div class="doc_text"> |
Misha Brukman | 1f254d5 | 2003-11-21 22:30:25 +0000 | [diff] [blame] | 102 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 103 | <p>The <a |
| 104 | href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1AliasAnalysis.html"><tt>AliasAnalysis</tt></a> |
| 105 | class defines the interface that the various alias analysis implementations |
| 106 | should support. This class exports two important enums: <tt>AliasResult</tt> |
| 107 | and <tt>ModRefResult</tt> which represent the result of an alias query or a |
| 108 | mod/ref query, respectively.</p> |
Misha Brukman | 1f254d5 | 2003-11-21 22:30:25 +0000 | [diff] [blame] | 109 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 110 | <p>The <tt>AliasAnalysis</tt> interface exposes information about memory, |
| 111 | represented in several different ways. In particular, memory objects are |
| 112 | represented as a starting address and size, and function calls are represented |
| 113 | as the actual <tt>call</tt> or <tt>invoke</tt> instructions that performs the |
| 114 | call. The <tt>AliasAnalysis</tt> interface also exposes some helper methods |
| 115 | which allow you to get mod/ref information for arbitrary instructions.</p> |
Misha Brukman | 1f254d5 | 2003-11-21 22:30:25 +0000 | [diff] [blame] | 116 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 117 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 118 | |
| 119 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 120 | <div class="doc_subsection"> |
| 121 | <a name="pointers">Representation of Pointers</a> |
| 122 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 123 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 124 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 125 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 126 | <p>Most importantly, the <tt>AliasAnalysis</tt> class provides several methods |
| 127 | which are used to query whether or not two memory objects alias, whether |
| 128 | function calls can modify or read a memory object, etc. For all of these |
| 129 | queries, memory objects are represented as a pair of their starting address (a |
| 130 | symbolic LLVM <tt>Value*</tt>) and a static size.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 131 | |
| 132 | <p>Representing memory objects as a starting address and a size is critically |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 133 | important for correct Alias Analyses. For example, consider this (silly, but |
| 134 | possible) C code:</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 135 | |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 136 | <pre> |
| 137 | int i; |
| 138 | char C[2]; |
| 139 | char A[10]; |
| 140 | /* ... */ |
| 141 | for (i = 0; i != 10; ++i) { |
| 142 | C[0] = A[i]; /* One byte store */ |
| 143 | C[1] = A[9-i]; /* One byte store */ |
| 144 | } |
| 145 | </pre> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 146 | |
| 147 | <p>In this case, the <tt>basicaa</tt> pass will disambiguate the stores to |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 148 | <tt>C[0]</tt> and <tt>C[1]</tt> because they are accesses to two distinct |
| 149 | locations one byte apart, and the accesses are each one byte. In this case, the |
| 150 | LICM pass can use store motion to remove the stores from the loop. In |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 151 | constrast, the following code:</p> |
| 152 | |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 153 | <pre> |
| 154 | int i; |
| 155 | char C[2]; |
| 156 | char A[10]; |
| 157 | /* ... */ |
| 158 | for (i = 0; i != 10; ++i) { |
| 159 | ((short*)C)[0] = A[i]; /* Two byte store! */ |
| 160 | C[1] = A[9-i]; /* One byte store */ |
| 161 | } |
| 162 | </pre> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 163 | |
| 164 | <p>In this case, the two stores to C do alias each other, because the access to |
| 165 | the <tt>&C[0]</tt> element is a two byte access. If size information wasn't |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 166 | available in the query, even the first case would have to conservatively assume |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 167 | that the accesses alias.</p> |
| 168 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 169 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 170 | |
| 171 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 172 | <div class="doc_subsection"> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 173 | <a name="alias">The <tt>alias</tt> method</a> |
| 174 | </div> |
| 175 | |
| 176 | <div class="doc_text"> |
| 177 | The <tt>alias</tt> method is the primary interface used to determine whether or |
| 178 | not two memory objects alias each other. It takes two memory objects as input |
| 179 | and returns MustAlias, MayAlias, or NoAlias as appropriate. |
| 180 | </div> |
| 181 | |
| 182 | <!-- _______________________________________________________________________ --> |
| 183 | <div class="doc_subsubsection"> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 184 | <a name="MustMayNo">Must, May, and No Alias Responses</a> |
| 185 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 186 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 187 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 188 | |
| 189 | <p>An Alias Analysis implementation can return one of three responses: |
| 190 | MustAlias, MayAlias, and NoAlias. The No and May alias results are obvious: if |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 191 | the two pointers can never equal each other, return NoAlias, if they might, |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 192 | return MayAlias.</p> |
| 193 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 194 | <p>The MustAlias response is trickier though. In LLVM, the Must Alias response |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 195 | may only be returned if the two memory objects are guaranteed to always start at |
| 196 | exactly the same location. If two memory objects overlap, but do not start at |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 197 | the same location, return MayAlias.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 198 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 199 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 200 | |
| 201 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 202 | <div class="doc_subsection"> |
| 203 | <a name="ModRefInfo">The <tt>getModRefInfo</tt> methods</a> |
| 204 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 205 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 206 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 207 | |
| 208 | <p>The <tt>getModRefInfo</tt> methods return information about whether the |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 209 | execution of an instruction can read or modify a memory location. Mod/Ref |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 210 | information is always conservative: if an instruction <b>might</b> read or write |
| 211 | a location, ModRef is returned.</p> |
| 212 | |
| 213 | <p>The <tt>AliasAnalysis</tt> class also provides a <tt>getModRefInfo</tt> |
| 214 | method for testing dependencies between function calls. This method takes two |
| 215 | call sites (CS1 & CS2), returns NoModRef if the two calls refer to disjoint |
| 216 | memory locations, Ref if CS1 reads memory written by CS2, Mod if CS1 writes to |
| 217 | memory read or written by CS2, or ModRef if CS1 might read or write memory |
| 218 | accessed by CS2. Note that this relation is not commutative. Clients that use |
| 219 | this method should be predicated on the <tt>hasNoModRefInfoForCalls()</tt> |
| 220 | method, which indicates whether or not an analysis can provide mod/ref |
| 221 | information for function call pairs (most can not). If this predicate is false, |
| 222 | the client shouldn't waste analysis time querying the <tt>getModRefInfo</tt> |
| 223 | method many times.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 224 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 225 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 226 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 227 | |
| 228 | <!-- ======================================================================= --> |
| 229 | <div class="doc_subsection"> |
| 230 | <a name="OtherItfs">Other useful <tt>AliasAnalysis</tt> methods</a> |
| 231 | </div> |
| 232 | |
| 233 | <div class="doc_text"> |
| 234 | |
| 235 | <p> |
| 236 | Several other tidbits of information are often collected by various alias |
| 237 | analysis implementations and can be put to good use by various clients. |
| 238 | </p> |
| 239 | |
| 240 | </div> |
| 241 | |
| 242 | <!-- _______________________________________________________________________ --> |
| 243 | <div class="doc_subsubsection"> |
| 244 | The <tt>getMustAliases</tt> method |
| 245 | </div> |
| 246 | |
| 247 | <div class="doc_text"> |
| 248 | |
| 249 | <p>The <tt>getMustAliases</tt> method returns all values that are known to |
| 250 | always must alias a pointer. This information can be provided in some cases for |
| 251 | important objects like the null pointer and global values. Knowing that a |
| 252 | pointer always points to a particular function allows indirect calls to be |
| 253 | turned into direct calls, for example.</p> |
| 254 | |
| 255 | </div> |
| 256 | |
| 257 | <!-- _______________________________________________________________________ --> |
| 258 | <div class="doc_subsubsection"> |
| 259 | The <tt>pointsToConstantMemory</tt> method |
| 260 | </div> |
| 261 | |
| 262 | <div class="doc_text"> |
| 263 | |
| 264 | <p>The <tt>pointsToConstantMemory</tt> method returns true if and only if the |
| 265 | analysis can prove that the pointer only points to unchanging memory locations |
| 266 | (functions, constant global variables, and the null pointer). This information |
| 267 | can be used to refine mod/ref information: it is impossible for an unchanging |
| 268 | memory location to be modified.</p> |
| 269 | |
| 270 | </div> |
| 271 | |
| 272 | |
| 273 | <!-- _______________________________________________________________________ --> |
| 274 | <div class="doc_subsubsection"> |
| 275 | <a name="simplemodref">The <tt>doesNotAccessMemory</tt> and |
| 276 | <tt>onlyReadsMemory</tt> methods</a> |
| 277 | </div> |
| 278 | |
| 279 | <div class="doc_text"> |
| 280 | |
| 281 | <p>These methods are used to provide very simple mod/ref information for |
| 282 | function calls. The <tt>doesNotAccessMemory</tt> method returns true for a |
| 283 | function if the analysis can prove that the function never reads or writes to |
| 284 | memory, or if the function only reads from constant memory. Functions with this |
| 285 | property are side-effect free and only depend on their input arguments, allowing |
| 286 | them to be eliminated if they form common subexpressions or be hoisted out of |
| 287 | loops. Many common functions behave this way (e.g., <tt>sin</tt> and |
| 288 | <tt>cos</tt>) but many others do not (e.g., <tt>acos</tt>, which modifies the |
| 289 | <tt>errno</tt> variable).</p> |
| 290 | |
| 291 | <p>The <tt>onlyReadsMemory</tt> method returns true for a function if analysis |
| 292 | can prove that (at most) the function only reads from non-volatile memory. |
| 293 | Functions with this property are side-effect free, only depending on their input |
| 294 | arguments and the state of memory when they are called. This property allows |
| 295 | calls to these functions to be eliminated and moved around, as long as there is |
| 296 | no store instruction that changes the contents of memory. Note that all |
| 297 | functions that satisfy the <tt>doesNotAccessMemory</tt> method also satisfies |
| 298 | <tt>onlyReadsMemory</tt>.</p> |
| 299 | |
| 300 | </div> |
| 301 | |
| 302 | |
| 303 | |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 304 | <!-- *********************************************************************** --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 305 | <div class="doc_section"> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 306 | <a name="writingnew">Writing a new <tt>AliasAnalysis</tt> Implementation</a> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 307 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 308 | <!-- *********************************************************************** --> |
| 309 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 310 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 311 | |
| 312 | <p>Writing a new alias analysis implementation for LLVM is quite |
| 313 | straight-forward. There are already several implementations that you can use |
| 314 | for examples, and the following information should help fill in any details. |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 315 | For a examples, take a look at the <a href="#impls">various alias analysis |
| 316 | implementations</a> included with LLVM.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 317 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 318 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 319 | |
| 320 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 321 | <div class="doc_subsection"> |
| 322 | <a name="passsubclasses">Different Pass styles</a> |
| 323 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 324 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 325 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 326 | |
| 327 | <p>The first step to determining what type of <a |
| 328 | href="WritingAnLLVMPass.html">LLVM pass</a> you need to use for your Alias |
| 329 | Analysis. As is the case with most other analyses and transformations, the |
| 330 | answer should be fairly obvious from what type of problem you are trying to |
| 331 | solve:</p> |
| 332 | |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 333 | <ol> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 334 | <li>If you require interprocedural analysis, it should be a |
| 335 | <tt>Pass</tt>.</li> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 336 | <li>If you are a function-local analysis, subclass <tt>FunctionPass</tt>.</li> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 337 | <li>If you don't need to look at the program at all, subclass |
| 338 | <tt>ImmutablePass</tt>.</li> |
| 339 | </ol> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 340 | |
| 341 | <p>In addition to the pass that you subclass, you should also inherit from the |
Misha Brukman | 700fd49 | 2003-05-07 21:47:16 +0000 | [diff] [blame] | 342 | <tt>AliasAnalysis</tt> interface, of course, and use the |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 343 | <tt>RegisterAnalysisGroup</tt> template to register as an implementation of |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 344 | <tt>AliasAnalysis</tt>.</p> |
| 345 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 346 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 347 | |
| 348 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 349 | <div class="doc_subsection"> |
| 350 | <a name="requiredcalls">Required initialization calls</a> |
| 351 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 352 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 353 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 354 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 355 | <p>Your subclass of <tt>AliasAnalysis</tt> is required to invoke two methods on |
| 356 | the <tt>AliasAnalysis</tt> base class: <tt>getAnalysisUsage</tt> and |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 357 | <tt>InitializeAliasAnalysis</tt>. In particular, your implementation of |
| 358 | <tt>getAnalysisUsage</tt> should explicitly call into the |
| 359 | <tt>AliasAnalysis::getAnalysisUsage</tt> method in addition to doing any |
| 360 | declaring any pass dependencies your pass has. Thus you should have something |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 361 | like this:</p> |
| 362 | |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 363 | <pre> |
| 364 | void getAnalysisUsage(AnalysisUsage &AU) const { |
| 365 | AliasAnalysis::getAnalysisUsage(AU); |
| 366 | <i>// declare your dependencies here.</i> |
| 367 | } |
| 368 | </pre> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 369 | |
| 370 | <p>Additionally, your must invoke the <tt>InitializeAliasAnalysis</tt> method |
| 371 | from your analysis run method (<tt>run</tt> for a <tt>Pass</tt>, |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 372 | <tt>runOnFunction</tt> for a <tt>FunctionPass</tt>, or <tt>InitializePass</tt> |
| 373 | for an <tt>ImmutablePass</tt>). For example (as part of a <tt>Pass</tt>):</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 374 | |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 375 | <pre> |
| 376 | bool run(Module &M) { |
| 377 | InitializeAliasAnalysis(this); |
| 378 | <i>// Perform analysis here...</i> |
| 379 | return false; |
| 380 | } |
| 381 | </pre> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 382 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 383 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 384 | |
| 385 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 386 | <div class="doc_subsection"> |
| 387 | <a name="interfaces">Interfaces which may be specified</a> |
| 388 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 389 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 390 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 391 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 392 | <p>All of the <a |
| 393 | href="/doxygen/classllvm_1_1AliasAnalysis.html"><tt>AliasAnalysis</tt></a> |
| 394 | virtual methods default to providing <a href="#chaining">chaining</a> to another |
| 395 | alias analysis implementation, which ends up returning conservatively correct |
| 396 | information (returning "May" Alias and "Mod/Ref" for alias and mod/ref queries |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 397 | respectively). Depending on the capabilities of the analysis you are |
| 398 | implementing, you just override the interfaces you can improve.</p> |
| 399 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 400 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 401 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 402 | |
| 403 | |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 404 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 405 | <div class="doc_subsection"> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 406 | <a name="chaining"><tt>AliasAnalysis</tt> chaining behavior</a> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 407 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 408 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 409 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 410 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 411 | <p>With only two special exceptions (the <tt><a |
| 412 | href="#basic-aa">basicaa</a></tt> and <a href="#no-aa"><tt>no-aa</tt></a> |
| 413 | passes) every alias analysis pass chains to another alias analysis |
| 414 | implementation (for example, the user can specify "<tt>-basicaa -ds-aa |
| 415 | -anders-aa -licm</tt>" to get the maximum benefit from the three alias |
| 416 | analyses). The alias analysis class automatically takes care of most of this |
| 417 | for methods that you don't override. For methods that you do override, in code |
| 418 | paths that return a conservative MayAlias or Mod/Ref result, simply return |
| 419 | whatever the superclass computes. For example:</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 420 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 421 | <pre> |
| 422 | AliasAnalysis::AliasResult alias(const Value *V1, unsigned V1Size, |
| 423 | const Value *V2, unsigned V2Size) { |
| 424 | if (...) |
| 425 | return NoAlias; |
| 426 | ... |
| 427 | |
| 428 | <i>// Couldn't determine a must or no-alias result.</i> |
| 429 | return AliasAnalysis::alias(V1, V1Size, V2, V2Size); |
| 430 | } |
| 431 | </pre> |
| 432 | |
| 433 | <p>In addition to analysis queries, you must make sure to unconditionally pass |
| 434 | LLVM <a href="#updating">update notification</a> methods to the superclass as |
| 435 | well if you override them, which allows all alias analyses in a change to be |
| 436 | updated.</p> |
| 437 | |
| 438 | </div> |
| 439 | |
| 440 | |
| 441 | <!-- ======================================================================= --> |
| 442 | <div class="doc_subsection"> |
| 443 | <a name="updating">Updating analysis results for transformations</a> |
| 444 | </div> |
| 445 | |
| 446 | <div class="doc_text"> |
| 447 | <p> |
| 448 | Alias analysis information is initially computed for a static snapshot of the |
| 449 | program, but clients will use this information to make transformations to the |
| 450 | code. All but the most trivial forms of alias analysis will need to have their |
| 451 | analysis results updated to reflect the changes made by these transformations. |
| 452 | </p> |
| 453 | |
| 454 | <p> |
| 455 | The <tt>AliasAnalysis</tt> interface exposes two methods which are used to |
| 456 | communicate program changes from the clients to the analysis implementations. |
| 457 | Various alias analysis implementations should use these methods to ensure that |
| 458 | their internal data structures are kept up-to-date as the program changes (for |
| 459 | example, when an instruction is deleted), and clients of alias analysis must be |
| 460 | sure to call these interfaces appropriately. |
| 461 | </p> |
| 462 | </div> |
| 463 | |
| 464 | <!-- _______________________________________________________________________ --> |
| 465 | <div class="doc_subsubsection">The <tt>deleteValue</tt> method</div> |
| 466 | |
| 467 | <div class="doc_text"> |
| 468 | The <tt>deleteValue</tt> method is called by transformations when they remove an |
| 469 | instruction or any other value from the program (including values that do not |
| 470 | use pointers). Typically alias analyses keep data structures that have entries |
| 471 | for each value in the program. When this method is called, they should remove |
| 472 | any entries for the specified value, if they exist. |
| 473 | </div> |
| 474 | |
| 475 | |
| 476 | <!-- _______________________________________________________________________ --> |
| 477 | <div class="doc_subsubsection">The <tt>copyValue</tt> method</div> |
| 478 | |
| 479 | <div class="doc_text"> |
| 480 | The <tt>copyValue</tt> method is used when a new value is introduced into the |
| 481 | program. There is no way to introduce a value into the program that did not |
| 482 | exist before (this doesn't make sense for a safe compiler transformation), so |
| 483 | this is the only way to introduce a new value. This method indicates that the |
| 484 | new value has exactly the same properties as the value being copied. |
| 485 | </div> |
| 486 | |
| 487 | |
| 488 | <!-- _______________________________________________________________________ --> |
| 489 | <div class="doc_subsubsection">The <tt>replaceWithNewValue</tt> method</div> |
| 490 | |
| 491 | <div class="doc_text"> |
| 492 | This method is a simple helper method that is provided to make clients easier to |
| 493 | use. It is implemented by copying the old analysis information to the new |
| 494 | value, then deleting the old value. This method cannot be overridden by alias |
| 495 | analysis implementations. |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 496 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 497 | |
| 498 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 499 | <div class="doc_subsection"> |
| 500 | <a name="implefficiency">Efficiency Issues</a> |
| 501 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 502 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 503 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 504 | |
| 505 | <p>From the LLVM perspective, the only thing you need to do to provide an |
| 506 | efficient alias analysis is to make sure that alias analysis <b>queries</b> are |
| 507 | serviced quickly. The actual calculation of the alias analysis results (the |
| 508 | "run" method) is only performed once, but many (perhaps duplicate) queries may |
| 509 | be performed. Because of this, try to move as much computation to the run |
| 510 | method as possible (within reason).</p> |
| 511 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 512 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 513 | |
| 514 | <!-- *********************************************************************** --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 515 | <div class="doc_section"> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 516 | <a name="using">Using alias analysis results</a> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 517 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 518 | <!-- *********************************************************************** --> |
| 519 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 520 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 521 | |
| 522 | <p>There are several different ways to use alias analysis results. In order of |
| 523 | preference, these are...</p> |
| 524 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 525 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 526 | |
| 527 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 528 | <div class="doc_subsection"> |
| 529 | <a name="loadvn">Using the <tt>-load-vn</tt> Pass</a> |
| 530 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 531 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 532 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 533 | |
| 534 | <p>The <tt>load-vn</tt> pass uses alias analysis to provide value numbering |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 535 | information for <tt>load</tt> instructions and pointer values. If your analysis |
| 536 | or transformation can be modeled in a form that uses value numbering |
| 537 | information, you don't have to do anything special to handle load instructions: |
| 538 | just use the <tt>load-vn</tt> pass, which uses alias analysis.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 539 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 540 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 541 | |
| 542 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 543 | <div class="doc_subsection"> |
| 544 | <a name="ast">Using the <tt>AliasSetTracker</tt> class</a> |
| 545 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 546 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 547 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 548 | |
| 549 | <p>Many transformations need information about alias <b>sets</b> that are active |
| 550 | in some scope, rather than information about pairwise aliasing. The <tt><a |
Misha Brukman | e12e5f3 | 2003-12-17 23:10:49 +0000 | [diff] [blame] | 551 | href="/doxygen/classllvm_1_1AliasSetTracker.html">AliasSetTracker</a></tt> class is used |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 552 | to efficiently build these Alias Sets from the pairwise alias analysis |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 553 | information provided by the <tt>AliasAnalysis</tt> interface.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 554 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 555 | <p>First you initialize the AliasSetTracker by using the "<tt>add</tt>" methods |
| 556 | to add information about various potentially aliasing instructions in the scope |
| 557 | you are interested in. Once all of the alias sets are completed, your pass |
| 558 | should simply iterate through the constructed alias sets, using the |
| 559 | <tt>AliasSetTracker</tt> <tt>begin()</tt>/<tt>end()</tt> methods.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 560 | |
| 561 | <p>The <tt>AliasSet</tt>s formed by the <tt>AliasSetTracker</tt> are guaranteed |
Chris Lattner | 539ca70 | 2003-12-19 08:43:07 +0000 | [diff] [blame] | 562 | to be disjoint, calculate mod/ref information and volatility for the set, and |
| 563 | keep track of whether or not all of the pointers in the set are Must aliases. |
| 564 | The AliasSetTracker also makes sure that sets are properly folded due to call |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 565 | instructions, and can provide a list of pointers in each set.</p> |
| 566 | |
| 567 | <p>As an example user of this, the <a href="/doxygen/structLICM.html">Loop |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 568 | Invariant Code Motion</a> pass uses <tt>AliasSetTracker</tt>s to calculate alias |
| 569 | sets for each loop nest. If an <tt>AliasSet</tt> in a loop is not modified, |
| 570 | then all load instructions from that set may be hoisted out of the loop. If any |
| 571 | alias sets are stored to <b>and</b> are must alias sets, then the stores may be |
| 572 | sunk to outside of the loop, promoting the memory location to a register for the |
| 573 | duration of the loop nest. Both of these transformations only apply if the |
| 574 | pointer argument is loop-invariant.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 575 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 576 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 577 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 578 | <!-- _______________________________________________________________________ --> |
Chris Lattner | 539ca70 | 2003-12-19 08:43:07 +0000 | [diff] [blame] | 579 | <div class="doc_subsubsection"> |
| 580 | The AliasSetTracker implementation |
| 581 | </div> |
| 582 | |
| 583 | <div class="doc_text"> |
| 584 | |
| 585 | <p>The AliasSetTracker class is implemented to be as efficient as possible. It |
| 586 | uses the union-find algorithm to efficiently merge AliasSets when a pointer is |
| 587 | inserted into the AliasSetTracker that aliases multiple sets. The primary data |
| 588 | structure is a hash table mapping pointers to the AliasSet they are in.</p> |
| 589 | |
| 590 | <p>The AliasSetTracker class must maintain a list of all of the LLVM Value*'s |
| 591 | that are in each AliasSet. Since the hash table already has entries for each |
| 592 | LLVM Value* of interest, the AliasesSets thread the linked list through these |
| 593 | hash-table nodes to avoid having to allocate memory unnecessarily, and to make |
| 594 | merging alias sets extremely efficient (the linked list merge is constant time). |
| 595 | </p> |
| 596 | |
| 597 | <p>You shouldn't need to understand these details if you are just a client of |
| 598 | the AliasSetTracker, but if you look at the code, hopefully this brief |
| 599 | description will help make sense of why things are designed the way they |
| 600 | are.</p> |
| 601 | |
| 602 | </div> |
| 603 | |
| 604 | |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 605 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 606 | <div class="doc_subsection"> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 607 | <a name="direct">Using the <tt>AliasAnalysis</tt> interface directly</a> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 608 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 609 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 610 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 611 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 612 | <p>If neither of these utility class are what your pass needs, you should use |
| 613 | the interfaces exposed by the <tt>AliasAnalysis</tt> class directly. Try to use |
| 614 | the higher-level methods when possible (e.g., use mod/ref information instead of |
| 615 | the <a href="#alias"><tt>alias</tt></a> method directly if possible) to get the |
| 616 | best precision and efficiency.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 617 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 618 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 619 | |
| 620 | <!-- *********************************************************************** --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 621 | <div class="doc_section"> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 622 | <a name="exist">Existing alias analysis implementations and clients</a> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 623 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 624 | <!-- *********************************************************************** --> |
| 625 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 626 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 627 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 628 | <p>If you're going to be working with the LLVM alias analysis infrastructure, |
| 629 | you should know what clients and implementations of alias analysis are |
| 630 | available. In particular, if you are implementing an alias analysis, you should |
| 631 | be aware of the <a href="#aliasanalysis-debug">the clients</a> that are useful |
| 632 | for monitoring and evaluating different implementations.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 633 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 634 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 635 | |
| 636 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 637 | <div class="doc_subsection"> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 638 | <a name="impls">Available <tt>AliasAnalysis</tt> implementations</a> |
| 639 | </div> |
| 640 | |
| 641 | <div class="doc_text"> |
| 642 | |
| 643 | <p>This section lists the various implementations of the <tt>AliasAnalysis</tt> |
| 644 | interface. With the exception of the <a href="#no-aa"><tt>-no-aa</tt></a> and |
| 645 | <a href="#basic-aa"><tt>-basicaa</tt></a> implementations, all of these <a |
Chris Lattner | fcd3725 | 2004-06-21 22:52:48 +0000 | [diff] [blame] | 646 | href="#chaining">chain</a> to other alias analysis implementations.</p> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 647 | |
| 648 | </div> |
| 649 | |
| 650 | <!-- _______________________________________________________________________ --> |
| 651 | <div class="doc_subsubsection"> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 652 | <a name="no-aa">The <tt>-no-aa</tt> pass</a> |
| 653 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 654 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 655 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 656 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 657 | <p>The <tt>-no-aa</tt> pass is just like what it sounds: an alias analysis that |
| 658 | never returns any useful information. This pass can be useful if you think that |
| 659 | alias analysis is doing something wrong and are trying to narrow down a |
| 660 | problem.</p> |
| 661 | |
| 662 | </div> |
| 663 | |
| 664 | |
| 665 | <!-- _______________________________________________________________________ --> |
| 666 | <div class="doc_subsubsection"> |
| 667 | <a name="basic-aa">The <tt>-basicaa</tt> pass</a> |
| 668 | </div> |
| 669 | |
| 670 | <div class="doc_text"> |
| 671 | |
| 672 | <p>The <tt>-basicaa</tt> pass is the default LLVM alias analysis. It is an |
| 673 | aggressive local analysis that "knows" many important facts:</p> |
| 674 | |
| 675 | <ul> |
| 676 | <li>Distinct globals, stack allocations, and heap allocations can never |
| 677 | alias.</li> |
| 678 | <li>Globals, stack allocations, and heap allocations never alias the null |
| 679 | pointer.</li> |
| 680 | <li>Different fields of a structure do not alias.</li> |
| 681 | <li>Indexes into arrays with statically differing subscripts cannot alias.</li> |
| 682 | <li>Many common standard C library functions <a |
| 683 | href="#simplemodref">never access memory or only read memory</a>.</li> |
| 684 | <li>Pointers that obviously point to constant globals |
| 685 | "<tt>pointToConstantMemory</tt>".</li> |
| 686 | <li>Function calls can not modify or references stack allocations if they never |
| 687 | escape from the function that allocates them (a common case for automatic |
| 688 | arrays).</li> |
| 689 | </ul> |
| 690 | |
| 691 | </div> |
| 692 | |
Chris Lattner | 100a4f8 | 2004-06-28 19:19:47 +0000 | [diff] [blame^] | 693 | <!-- _______________________________________________________________________ --> |
| 694 | <div class="doc_subsubsection"> |
| 695 | <a name="globalsmodref">The <tt>-globalsmodref-aa</tt> pass</a> |
| 696 | </div> |
| 697 | |
| 698 | <div class="doc_text"> |
| 699 | |
| 700 | <p>This pass implements a simple context-sensitive mod/ref and alias analysis |
| 701 | for internal global variables that don't "have their address taken". If a |
| 702 | global does not have its address taken, the pass knows that no pointers alias |
| 703 | the global. |
| 704 | </p> |
| 705 | |
| 706 | <p>The real power of this pass is that it provides context-sensitive mod/ref |
| 707 | information for call instructions. This allows the optimizer to know that |
| 708 | calls to a function do not clobber or read the value of the global, allowing |
| 709 | loads and stores to be eliminated.</p> |
| 710 | |
| 711 | <p>Note that this pass is somewhat limited in its scope (only support |
| 712 | non-address taken globals), but is very quick analysis.</p> |
| 713 | </div> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 714 | |
| 715 | <!-- _______________________________________________________________________ --> |
| 716 | <div class="doc_subsubsection"> |
| 717 | <a name="anders-aa">The <tt>-anders-aa</tt> pass</a> |
| 718 | </div> |
| 719 | |
| 720 | <div class="doc_text"> |
| 721 | |
| 722 | <p>The <tt>-anders-aa</tt> pass implements the well-known "Andersen's algorithm" |
| 723 | for interprocedural alias analysis. This algorithm is a subset-based, |
| 724 | flow-insensitive, context-insensitive, and field-insensitive alias analysis that |
| 725 | is widely believed to be fairly precise. Unfortunately, this algorithm is also |
| 726 | O(N<sup>3</sup>). The LLVM implementation currently does not implement any of |
| 727 | the refinements (such as "online cycle elimination" or "offline variable |
| 728 | substitution") to improve its efficiency, so it can be quite slow in common |
| 729 | cases. |
| 730 | </p> |
| 731 | |
| 732 | </div> |
| 733 | |
| 734 | <!-- _______________________________________________________________________ --> |
| 735 | <div class="doc_subsubsection"> |
| 736 | <a name="steens-aa">The <tt>-steens-aa</tt> pass</a> |
| 737 | </div> |
| 738 | |
| 739 | <div class="doc_text"> |
| 740 | |
| 741 | <p>The <tt>-steens-aa</tt> pass implements a variation on the well-known |
| 742 | "Steensgaard's algorithm" for interprocedural alias analysis. Steensgaard's |
| 743 | algorithm is a unification-based, flow-insensitive, context-insensitive, and |
| 744 | field-insensitive alias analysis that is also very scalable (effectively linear |
| 745 | time).</p> |
| 746 | |
| 747 | <p>The LLVM <tt>-steens-aa</tt> pass implements a "speculatively |
| 748 | field-<b>sensitive</b>" version of Steensgaard's algorithm using the Data |
| 749 | Structure Analysis framework. This gives it substantially more precision than |
| 750 | the standard algorithm while maintaining excellent analysis scalability.</p> |
| 751 | |
| 752 | </div> |
| 753 | |
| 754 | <!-- _______________________________________________________________________ --> |
| 755 | <div class="doc_subsubsection"> |
| 756 | <a name="ds-aa">The <tt>-ds-aa</tt> pass</a> |
| 757 | </div> |
| 758 | |
| 759 | <div class="doc_text"> |
| 760 | |
| 761 | <p>The <tt>-ds-aa</tt> pass implements the full Data Structure Analysis |
| 762 | algorithm. Data Structure Analysis is a modular unification-based, |
| 763 | flow-insensitive, context-<b>sensitive</b>, and speculatively |
| 764 | field-<b>sensitive</b> alias analysis that is also quite scalable, usually at |
| 765 | O(n*log(n)).</p> |
| 766 | |
| 767 | <p>This algorithm is capable of responding to a full variety of alias analysis |
| 768 | queries, and can provide context-sensitive mod/ref information as well. The |
| 769 | only major facility not implemented so far is support for must-alias |
| 770 | information.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 771 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 772 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 773 | |
| 774 | |
| 775 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 776 | <div class="doc_subsection"> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 777 | <a name="aliasanalysis-xforms">Alias analysis driven transformations</a> |
| 778 | </div> |
| 779 | |
| 780 | <div class="doc_text"> |
| 781 | LLVM includes several alias-analysis driven transformations which can be used |
| 782 | with any of the implementations above. |
| 783 | </div> |
| 784 | |
| 785 | <!-- _______________________________________________________________________ --> |
| 786 | <div class="doc_subsubsection"> |
| 787 | <a name="adce">The <tt>-adce</tt> pass</a> |
| 788 | </div> |
| 789 | |
| 790 | <div class="doc_text"> |
| 791 | |
| 792 | <p>The <tt>-adce</tt> pass, which implements Aggressive Dead Code Elimination |
| 793 | uses the <tt>AliasAnalysis</tt> interface to delete calls to functions that do |
| 794 | not have side-effects and are not used.</p> |
| 795 | |
| 796 | </div> |
| 797 | |
| 798 | |
| 799 | <!-- _______________________________________________________________________ --> |
| 800 | <div class="doc_subsubsection"> |
| 801 | <a name="licm">The <tt>-licm</tt> pass</a> |
| 802 | </div> |
| 803 | |
| 804 | <div class="doc_text"> |
| 805 | |
| 806 | <p>The <tt>-licm</tt> pass implements various Loop Invariant Code Motion related |
| 807 | transformations. It uses the <tt>AliasAnalysis</tt> interface for several |
| 808 | different transformations:</p> |
| 809 | |
| 810 | <ul> |
| 811 | <li>It uses mod/ref information to hoist or sink load instructions out of loops |
| 812 | if there are no instructions in the loop that modifies the memory loaded.</li> |
| 813 | |
| 814 | <li>It uses mod/ref information to hoist function calls out of loops that do not |
| 815 | write to memory and are loop-invariant.</li> |
| 816 | |
| 817 | <li>If uses alias information to promote memory objects that are loaded and |
| 818 | stored to in loops to live in a register instead. It can do this if there are |
| 819 | no may aliases to the loaded/stored memory location.</li> |
| 820 | </ul> |
| 821 | |
| 822 | </div> |
| 823 | |
| 824 | <!-- _______________________________________________________________________ --> |
| 825 | <div class="doc_subsubsection"> |
| 826 | <a name="argpromotion">The <tt>-argpromotion</tt> pass</a> |
| 827 | </div> |
| 828 | |
| 829 | <div class="doc_text"> |
| 830 | <p> |
| 831 | The <tt>-argpromotion</tt> pass promotes by-reference arguments to be passed in |
| 832 | by-value instead. In particular, if pointer arguments are only loaded from it |
| 833 | passes in the value loaded instead of the address to the function. This pass |
| 834 | uses alias information to make sure that the value loaded from the argument |
| 835 | pointer is not modified between the entry of the function and any load of the |
| 836 | pointer.</p> |
| 837 | </div> |
| 838 | |
| 839 | <!-- _______________________________________________________________________ --> |
| 840 | <div class="doc_subsubsection"> |
| 841 | <a name="gcseloadvn">The <tt>-load-vn</tt> & <tt>-gcse</tt> passes</a> |
| 842 | </div> |
| 843 | |
| 844 | <div class="doc_text"> |
| 845 | <p> |
| 846 | The <tt>-load-vn</tt> pass uses alias analysis to "<a href="#loadvn">value |
| 847 | number</a>" loads and pointers values, which is used by the GCSE pass to |
| 848 | eliminate instructions. The <tt>-load-vn</tt> pass relies on alias information |
| 849 | and must-alias information. This combination of passes can make the following |
| 850 | transformations:</p> |
| 851 | |
| 852 | <ul> |
| 853 | <li>Redundant load instructions are eliminated.</li> |
| 854 | <li>Load instructions that follow a store to the same location are replaced with |
| 855 | the stored value ("store forwarding").</li> |
| 856 | <li>Pointers values (e.g. formal arguments) that must-alias simpler expressions |
| 857 | (e.g. global variables or the null pointer) are replaced. Note that this |
| 858 | implements transformations like "virtual method resolution", turning indirect |
| 859 | calls into direct calls.</li> |
| 860 | </ul> |
| 861 | |
| 862 | </div> |
| 863 | |
| 864 | |
| 865 | |
| 866 | |
| 867 | <!-- ======================================================================= --> |
| 868 | <div class="doc_subsection"> |
| 869 | <a name="aliasanalysis-debug">Clients for debugging and evaluation of implementations</a> |
| 870 | </div> |
| 871 | |
| 872 | These passes are useful for evaluating the various alias analysis |
| 873 | implementations. You can use them with commands like '<tt>opt -anders-aa -ds-aa |
| 874 | -aa-eval foo.bc -disable-output -stats</tt>'. |
| 875 | |
| 876 | |
| 877 | <!-- _______________________________________________________________________ --> |
| 878 | <div class="doc_subsubsection"> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 879 | <a name="print-alias-sets">The <tt>-print-alias-sets</tt> pass</a> |
| 880 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 881 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 882 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 883 | |
| 884 | <p>The <tt>-print-alias-sets</tt> pass is exposed as part of the |
| 885 | <tt>analyze</tt> tool to print out the Alias Sets formed by the <a |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 886 | href="#ast"><tt>AliasSetTracker</tt></a> class. This is useful if you're using |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 887 | the <tt>AliasSetTracker</tt> class.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 888 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 889 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 890 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 891 | |
| 892 | <!-- _______________________________________________________________________ --> |
| 893 | <div class="doc_subsubsection"> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 894 | <a name="count-aa">The <tt>-count-aa</tt> pass</a> |
| 895 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 896 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 897 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 898 | |
| 899 | <p>The <tt>-count-aa</tt> pass is useful to see how many queries a particular |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 900 | pass is making and what responses are returned by the alias analysis. An |
| 901 | example usage is:</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 902 | |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 903 | <pre> |
| 904 | $ opt -basicaa -count-aa -ds-aa -count-aa -licm |
| 905 | </pre> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 906 | |
| 907 | <p>Which will print out how many queries (and what responses are returned) by |
| 908 | the <tt>-licm</tt> pass (of the <tt>-ds-aa</tt> pass) and how many queries are |
| 909 | made of the <tt>-basicaa</tt> pass by the <tt>-ds-aa</tt> pass. This can be |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 910 | useful when debugging a transformation or an alias analysis implementation.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 911 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 912 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 913 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 914 | <!-- _______________________________________________________________________ --> |
| 915 | <div class="doc_subsubsection"> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 916 | <a name="aa-eval">The <tt>-aa-eval</tt> pass</a> |
| 917 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 918 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 919 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 920 | |
| 921 | <p>The <tt>-aa-eval</tt> pass simply iterates through all pairs of pointers in a |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 922 | function and asks an alias analysis whether or not the pointers alias. This |
| 923 | gives an indication of the precision of the alias analysis. Statistics are |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 924 | printed indicating the percent of no/may/must aliases found (a more precise |
| 925 | algorithm will have a lower number of may aliases).</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 926 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 927 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 928 | |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 929 | <!-- *********************************************************************** --> |
| 930 | |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 931 | <hr> |
Misha Brukman | 915cab2 | 2003-11-22 01:26:21 +0000 | [diff] [blame] | 932 | <address> |
Misha Brukman | 38847d5 | 2003-12-21 22:53:21 +0000 | [diff] [blame] | 933 | <a href="http://jigsaw.w3.org/css-validator/check/referer"><img |
Misha Brukman | 5feba4e | 2003-11-22 01:07:30 +0000 | [diff] [blame] | 934 | src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a> |
Misha Brukman | 915cab2 | 2003-11-22 01:26:21 +0000 | [diff] [blame] | 935 | <a href="http://validator.w3.org/check/referer"><img |
Misha Brukman | f6acb51 | 2004-05-12 18:02:00 +0000 | [diff] [blame] | 936 | src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a> |
Misha Brukman | 915cab2 | 2003-11-22 01:26:21 +0000 | [diff] [blame] | 937 | |
| 938 | <a href="mailto:sabre@nondot.org">Chris Lattner</a><br> |
Misha Brukman | f6acb51 | 2004-05-12 18:02:00 +0000 | [diff] [blame] | 939 | <a href="http://llvm.cs.uiuc.edu">LLVM Compiler Infrastructure</a><br> |
Misha Brukman | 915cab2 | 2003-11-22 01:26:21 +0000 | [diff] [blame] | 940 | Last modified: $Date$ |
| 941 | </address> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 942 | |
| 943 | </body> |
| 944 | </html> |