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> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 5 | <link rel="stylesheet" href="llvm.css" type="text/css"> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 6 | <title>Alias Analysis Infrastructure in LLVM</title> |
| 7 | </head> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 8 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 9 | <body> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 10 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 11 | <div class="doc_title"> |
| 12 | Alias Analysis Infrastructure in LLVM |
| 13 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 14 | |
| 15 | <ol> |
Misha Brukman | b215425 | 2003-10-23 02:29:42 +0000 | [diff] [blame] | 16 | <li><a href="#introduction">Introduction</a></li> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 17 | |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 18 | <li><a href="#overview">AliasAnalysis Overview</a> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 19 | <ul> |
Misha Brukman | b215425 | 2003-10-23 02:29:42 +0000 | [diff] [blame] | 20 | <li><a href="#pointers">Representation of Pointers</a></li> |
| 21 | <li><a href="#MustMayNo">Must, May, and No Alias Responses</a></li> |
| 22 | <li><a href="#ModRefInfo">The <tt>getModRefInfo</tt> methods</a></li> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 23 | </ul></li> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 24 | |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 25 | <li><a href="#writingnew">Writing a new AliasAnalysis Implementation</a> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 26 | <ul> |
Misha Brukman | b215425 | 2003-10-23 02:29:42 +0000 | [diff] [blame] | 27 | <li><a href="#passsubclasses">Different Pass styles</a></li> |
| 28 | <li><a href="#requiredcalls">Required initialization calls</a></li> |
| 29 | <li><a href="#interfaces">Interfaces which may be specified</a></li> |
| 30 | <li><a href="#chaining">The AliasAnalysis chaining behavior</a></li> |
| 31 | <li><a href="#implefficiency">Efficiency Issues</a></li> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 32 | </ul></li> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 33 | |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 34 | <li><a href="#using">Using AliasAnalysis results</a> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 35 | <ul> |
Misha Brukman | b215425 | 2003-10-23 02:29:42 +0000 | [diff] [blame] | 36 | <li><a href="#loadvn">Using the <tt>-load-vn</tt> Pass</a></li> |
| 37 | <li><a href="#ast">Using the <tt>AliasSetTracker</tt> class</a></li> |
| 38 | <li><a href="#direct">Using the AliasAnalysis interface directly</a></li> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 39 | </ul></li> |
| 40 | |
| 41 | <li><a href="#tools">Helpful alias analysis related tools</a> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 42 | <ul> |
Misha Brukman | b215425 | 2003-10-23 02:29:42 +0000 | [diff] [blame] | 43 | <li><a href="#no-aa">The <tt>-no-aa</tt> pass</a></li> |
| 44 | <li><a href="#print-alias-sets">The <tt>-print-alias-sets</tt> pass</a></li> |
| 45 | <li><a href="#count-aa">The <tt>-count-aa</tt> pass</a></li> |
| 46 | <li><a href="#aa-eval">The <tt>-aa-eval</tt> pass</a></li> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 47 | </ul></li> |
Misha Brukman | b215425 | 2003-10-23 02:29:42 +0000 | [diff] [blame] | 48 | </ol> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 49 | |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 50 | <div class="doc_text"> |
| 51 | <p><b>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></b></p> |
| 52 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 53 | |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 54 | <!-- *********************************************************************** --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 55 | <div class="doc_section"> |
| 56 | <a name="introduction">Introduction</a> |
| 57 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 58 | <!-- *********************************************************************** --> |
| 59 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 60 | <div class="doc_text"> |
| 61 | <p> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 62 | Alias Analysis (or Pointer Analysis) is a technique which attempts to determine |
| 63 | whether or not two pointers ever can point to the same object in memory. |
| 64 | Traditionally, Alias Analyses respond to a query with either a <a |
| 65 | href="#MustNoMay">Must, May, or No</a> alias response, indicating that two |
| 66 | pointers do point to the same object, might point to the same object, or are |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 67 | known not to point to the same object. |
| 68 | </p> |
| 69 | <p> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 70 | The <a href="/doxygen/classAliasAnalysis.html">AliasAnalysis</a> class is the |
| 71 | centerpiece of the LLVM Alias Analysis related infrastructure. This class is |
| 72 | the common interface between clients of alias analysis information and the |
| 73 | implementations providing it. In addition to simple alias analysis information, |
| 74 | this class exposes Mod/Ref information from those implementations which can |
| 75 | provide it, allowing for powerful analyses and transformations to work well |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 76 | together. |
| 77 | </p> |
| 78 | <p> |
Misha Brukman | 5560c9d | 2003-08-18 14:43:39 +0000 | [diff] [blame] | 79 | This document contains information necessary to successfully implement this |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 80 | interface, use it, and to test both sides. It also explains some of the finer |
| 81 | 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] | 82 | or should be added, please <a href="mailto:sabre@nondot.org">let me |
| 83 | know</a>. |
| 84 | </p> |
| 85 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 86 | |
| 87 | <!-- *********************************************************************** --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 88 | <div class="doc_section"> |
| 89 | <a name="overview">AliasAnalysis Overview</a> |
| 90 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 91 | <!-- *********************************************************************** --> |
| 92 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 93 | <div class="doc_text"> |
| 94 | <p> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 95 | The <a href="/doxygen/classAliasAnalysis.html">AliasAnalysis</a> class defines |
| 96 | the interface that Alias Analysis implementations should support. This class |
| 97 | exports two important enums: <tt>AliasResult</tt> and <tt>ModRefResult</tt> |
| 98 | which represent the result of an alias query or a mod/ref query, |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 99 | respectively. |
| 100 | </p> |
| 101 | <p> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 102 | The AliasAnalysis interface exposes information about memory, represented in |
| 103 | several different ways. In particular, memory objects are represented as a |
| 104 | starting address and size, and function calls are represented as the actual |
| 105 | <tt>call</tt> or <tt>invoke</tt> instructions that performs the call. The |
| 106 | AliasAnalysis interface also exposes some helper methods which allow you to get |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 107 | mod/ref information for arbitrary instructions. |
| 108 | </p> |
| 109 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 110 | |
| 111 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 112 | <div class="doc_subsection"> |
| 113 | <a name="pointers">Representation of Pointers</a> |
| 114 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 115 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 116 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 117 | |
| 118 | <p>Most importantly, the AliasAnalysis class provides several methods which are |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 119 | used to query whether or not pointers alias, whether function calls can modify |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 120 | or read memory, etc.</p> |
| 121 | |
| 122 | <p>Representing memory objects as a starting address and a size is critically |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 123 | important for precise Alias Analyses. For example, consider this (silly) C |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 124 | code:</p> |
| 125 | |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 126 | <pre> |
| 127 | int i; |
| 128 | char C[2]; |
| 129 | char A[10]; |
| 130 | /* ... */ |
| 131 | for (i = 0; i != 10; ++i) { |
| 132 | C[0] = A[i]; /* One byte store */ |
| 133 | C[1] = A[9-i]; /* One byte store */ |
| 134 | } |
| 135 | </pre> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 136 | |
| 137 | <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] | 138 | <tt>C[0]</tt> and <tt>C[1]</tt> because they are accesses to two distinct |
| 139 | locations one byte apart, and the accesses are each one byte. In this case, the |
| 140 | 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] | 141 | constrast, the following code:</p> |
| 142 | |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 143 | <pre> |
| 144 | int i; |
| 145 | char C[2]; |
| 146 | char A[10]; |
| 147 | /* ... */ |
| 148 | for (i = 0; i != 10; ++i) { |
| 149 | ((short*)C)[0] = A[i]; /* Two byte store! */ |
| 150 | C[1] = A[9-i]; /* One byte store */ |
| 151 | } |
| 152 | </pre> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 153 | |
| 154 | <p>In this case, the two stores to C do alias each other, because the access to |
| 155 | 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] | 156 | 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] | 157 | that the accesses alias.</p> |
| 158 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 159 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 160 | |
| 161 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 162 | <div class="doc_subsection"> |
| 163 | <a name="MustMayNo">Must, May, and No Alias Responses</a> |
| 164 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 165 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 166 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 167 | |
| 168 | <p>An Alias Analysis implementation can return one of three responses: |
| 169 | MustAlias, MayAlias, and NoAlias. The No and May alias results are obvious: if |
| 170 | the two pointers may never equal each other, return NoAlias, if they might, |
| 171 | return MayAlias.</p> |
| 172 | |
| 173 | <p>The Must Alias response is trickier though. In LLVM, the Must Alias response |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 174 | may only be returned if the two memory objects are guaranteed to always start at |
| 175 | exactly the same location. If two memory objects overlap, but do not start at |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 176 | the same location, MayAlias must be returned.</p> |
| 177 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 178 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 179 | |
| 180 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 181 | <div class="doc_subsection"> |
| 182 | <a name="ModRefInfo">The <tt>getModRefInfo</tt> methods</a> |
| 183 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 184 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 185 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 186 | |
| 187 | <p>The <tt>getModRefInfo</tt> methods return information about whether the |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 188 | execution of an instruction can read or modify a memory location. Mod/Ref |
| 189 | information is always conservative: if an action <b>may</b> read a location, Ref |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 190 | is returned.</p> |
| 191 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 192 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 193 | |
| 194 | <!-- *********************************************************************** --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 195 | <div class="doc_section"> |
| 196 | <a name="writingnew">Writing a new AliasAnalysis Implementation</a> |
| 197 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 198 | <!-- *********************************************************************** --> |
| 199 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 200 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 201 | |
| 202 | <p>Writing a new alias analysis implementation for LLVM is quite |
| 203 | straight-forward. There are already several implementations that you can use |
| 204 | for examples, and the following information should help fill in any details. |
| 205 | For a minimal example, take a look at the <a |
| 206 | href="/doxygen/structNoAA.html"><tt>no-aa</tt></a> implementation.</p> |
| 207 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 208 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 209 | |
| 210 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 211 | <div class="doc_subsection"> |
| 212 | <a name="passsubclasses">Different Pass styles</a> |
| 213 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 214 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 215 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 216 | |
| 217 | <p>The first step to determining what type of <a |
| 218 | href="WritingAnLLVMPass.html">LLVM pass</a> you need to use for your Alias |
| 219 | Analysis. As is the case with most other analyses and transformations, the |
| 220 | answer should be fairly obvious from what type of problem you are trying to |
| 221 | solve:</p> |
| 222 | |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 223 | <ol> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 224 | <li>If you require interprocedural analysis, it should be a |
| 225 | <tt>Pass</tt>.</li> |
| 226 | <li>If you are a global analysis, subclass <tt>FunctionPass</tt>.</li> |
| 227 | <li>If you are a local pass, subclass <tt>BasicBlockPass</tt>.</li> |
| 228 | <li>If you don't need to look at the program at all, subclass |
| 229 | <tt>ImmutablePass</tt>.</li> |
| 230 | </ol> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 231 | |
| 232 | <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] | 233 | <tt>AliasAnalysis</tt> interface, of course, and use the |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 234 | <tt>RegisterAnalysisGroup</tt> template to register as an implementation of |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 235 | <tt>AliasAnalysis</tt>.</p> |
| 236 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 237 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 238 | |
| 239 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 240 | <div class="doc_subsection"> |
| 241 | <a name="requiredcalls">Required initialization calls</a> |
| 242 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 243 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 244 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 245 | |
| 246 | <p>Your subclass of AliasAnalysis is required to invoke two methods on the |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 247 | AliasAnalysis base class: <tt>getAnalysisUsage</tt> and |
| 248 | <tt>InitializeAliasAnalysis</tt>. In particular, your implementation of |
| 249 | <tt>getAnalysisUsage</tt> should explicitly call into the |
| 250 | <tt>AliasAnalysis::getAnalysisUsage</tt> method in addition to doing any |
| 251 | declaring any pass dependencies your pass has. Thus you should have something |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 252 | like this:</p> |
| 253 | |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 254 | <pre> |
| 255 | void getAnalysisUsage(AnalysisUsage &AU) const { |
| 256 | AliasAnalysis::getAnalysisUsage(AU); |
| 257 | <i>// declare your dependencies here.</i> |
| 258 | } |
| 259 | </pre> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 260 | |
| 261 | <p>Additionally, your must invoke the <tt>InitializeAliasAnalysis</tt> method |
| 262 | from your analysis run method (<tt>run</tt> for a <tt>Pass</tt>, |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 263 | <tt>runOnFunction</tt> for a <tt>FunctionPass</tt>, <tt>runOnBasicBlock</tt> for |
| 264 | a <tt>BasicBlockPass</tt>, or <tt>InitializeAliasAnalysis</tt> for an |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 265 | <tt>ImmutablePass</tt>). For example (as part of a <tt>Pass</tt>):</p> |
| 266 | |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 267 | <pre> |
| 268 | bool run(Module &M) { |
| 269 | InitializeAliasAnalysis(this); |
| 270 | <i>// Perform analysis here...</i> |
| 271 | return false; |
| 272 | } |
| 273 | </pre> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 274 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 275 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 276 | |
| 277 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 278 | <div class="doc_subsection"> |
| 279 | <a name="interfaces">Interfaces which may be specified</a> |
| 280 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 281 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 282 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 283 | |
| 284 | <p>All of the <a href="/doxygen/classAliasAnalysis.html">AliasAnalysis</a> |
| 285 | virtual methods default to providing conservatively correct information |
| 286 | (returning "May" Alias and "Mod/Ref" for alias and mod/ref queries |
| 287 | respectively). Depending on the capabilities of the analysis you are |
| 288 | implementing, you just override the interfaces you can improve.</p> |
| 289 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 290 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 291 | |
| 292 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 293 | <div class="doc_subsection"> |
| 294 | <a name="chaining">The AliasAnalysis chaining behavior</a> |
| 295 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 296 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 297 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 298 | |
| 299 | <p>With only two special exceptions (the <tt>basicaa</tt> and <a |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 300 | href="#no-aa"><tt>no-aa</tt></a> passes) every alias analysis pass should chain |
| 301 | to another alias analysis implementation (for example, you could specify |
| 302 | "<tt>-basic-aa -ds-aa -andersens-aa -licm</tt>" to get the maximum benefit from |
| 303 | the three alias analyses). To do this, simply "Require" AliasAnalysis in your |
| 304 | <tt>getAnalysisUsage</tt> method, and if you need to return a conservative |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 305 | MayAlias or Mod/Ref result, simply chain to a lower analysis.</p> |
| 306 | |
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_subsection"> |
| 311 | <a name="implefficiency">Efficiency Issues</a> |
| 312 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 313 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 314 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 315 | |
| 316 | <p>From the LLVM perspective, the only thing you need to do to provide an |
| 317 | efficient alias analysis is to make sure that alias analysis <b>queries</b> are |
| 318 | serviced quickly. The actual calculation of the alias analysis results (the |
| 319 | "run" method) is only performed once, but many (perhaps duplicate) queries may |
| 320 | be performed. Because of this, try to move as much computation to the run |
| 321 | method as possible (within reason).</p> |
| 322 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 323 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 324 | |
| 325 | <!-- *********************************************************************** --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 326 | <div class="doc_section"> |
| 327 | <a name="using">Using AliasAnalysis results</a> |
| 328 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 329 | <!-- *********************************************************************** --> |
| 330 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 331 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 332 | |
| 333 | <p>There are several different ways to use alias analysis results. In order of |
| 334 | preference, these are...</p> |
| 335 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 336 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 337 | |
| 338 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 339 | <div class="doc_subsection"> |
| 340 | <a name="loadvn">Using the <tt>-load-vn</tt> Pass</a> |
| 341 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 342 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 343 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 344 | |
| 345 | <p>The <tt>load-vn</tt> pass uses alias analysis to provide value numbering |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 346 | information for <tt>load</tt> instructions. If your analysis or transformation |
| 347 | can be modelled in a form that uses value numbering information, you don't have |
| 348 | to do anything special to handle load instructions: just use the |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 349 | <tt>load-vn</tt> pass, which uses alias analysis.</p> |
| 350 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 351 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 352 | |
| 353 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 354 | <div class="doc_subsection"> |
| 355 | <a name="ast">Using the <tt>AliasSetTracker</tt> class</a> |
| 356 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 357 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 358 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 359 | |
| 360 | <p>Many transformations need information about alias <b>sets</b> that are active |
| 361 | in some scope, rather than information about pairwise aliasing. The <tt><a |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 362 | href="/doxygen/classAliasSetTracker.html">AliasSetTracker</a></tt> class is used |
| 363 | to efficiently build these Alias Sets from the pairwise alias analysis |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 364 | information provided by the AliasAnalysis interface.</p> |
| 365 | |
| 366 | <p>First you initialize the AliasSetTracker by use the "<tt>add</tt>" methods to |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 367 | add information about various potentially aliasing instructions in the scope you |
| 368 | are interested in. Once all of the alias sets are completed, your pass should |
| 369 | simply iterate through the constructed alias sets, using the AliasSetTracker |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 370 | <tt>begin()</tt>/<tt>end()</tt> methods.</p> |
| 371 | |
| 372 | <p>The <tt>AliasSet</tt>s formed by the <tt>AliasSetTracker</tt> are guaranteed |
| 373 | to be disjoint, calculate mod/ref information for the set, and keep track of |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 374 | whether or not all of the pointers in the set are Must aliases. The |
| 375 | AliasSetTracker also makes sure that sets are properly folded due to call |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 376 | instructions, and can provide a list of pointers in each set.</p> |
| 377 | |
| 378 | <p>As an example user of this, the <a href="/doxygen/structLICM.html">Loop |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 379 | Invariant Code Motion</a> pass uses AliasSetTrackers to build alias information |
| 380 | about each loop nest. If an AliasSet in a loop is not modified, then all load |
| 381 | instructions from that set may be hoisted out of the loop. If any alias sets |
| 382 | are stored <b>and</b> are must alias sets, then the stores may be sunk to |
| 383 | outside of the loop. Both of these transformations obviously only apply if the |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 384 | pointer argument is loop-invariant.</p> |
| 385 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 386 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 387 | |
| 388 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 389 | <div class="doc_subsection"> |
| 390 | <a name="direct">Using the AliasAnalysis interface directly</a> |
| 391 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 392 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 393 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 394 | |
| 395 | <p>As a last resort, your pass could use the AliasAnalysis interface directly to |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 396 | service your pass. If you find the need to do this, please <a |
| 397 | href="mailto:sabre@nondot.org">let me know</a> so I can see if something new |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 398 | needs to be added to LLVM.</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 | |
| 402 | <!-- *********************************************************************** --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 403 | <div class="doc_section"> |
| 404 | <a name="tools">Helpful alias-analysis-related tools</a> |
| 405 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 406 | <!-- *********************************************************************** --> |
| 407 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 408 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 409 | |
| 410 | <p>If you're going to be working with the AliasAnalysis infrastructure, there |
| 411 | are several nice tools that may be useful for you and are worth knowing |
| 412 | about...</p> |
| 413 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 414 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 415 | |
| 416 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 417 | <div class="doc_subsection"> |
| 418 | <a name="no-aa">The <tt>-no-aa</tt> pass</a> |
| 419 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 420 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 421 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 422 | |
| 423 | <p>The <tt>-no-aa</tt> analysis is just like what it sounds: an alias analysis |
| 424 | that never returns any useful information. This pass can be useful if you think |
| 425 | that alias analysis is doing something wrong and are trying to narrow down a |
| 426 | problem. If you don't specify an alias analysis, the default will be to use the |
| 427 | <tt>basicaa</tt> pass which does quite a bit of disambiguation on its own.</p> |
| 428 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 429 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 430 | |
| 431 | |
| 432 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 433 | <div class="doc_subsection"> |
| 434 | <a name="print-alias-sets">The <tt>-print-alias-sets</tt> pass</a> |
| 435 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 436 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 437 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 438 | |
| 439 | <p>The <tt>-print-alias-sets</tt> pass is exposed as part of the |
| 440 | <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] | 441 | href="#ast"><tt>AliasSetTracker</tt></a> class. This is useful if you're using |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 442 | the <tt>AliasSetTracker</tt>.</p> |
| 443 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 444 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 445 | |
| 446 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 447 | <div class="doc_subsection"> |
| 448 | <a name="count-aa">The <tt>-count-aa</tt> pass</a> |
| 449 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 450 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 451 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 452 | |
| 453 | <p>The <tt>-count-aa</tt> pass is useful to see how many queries a particular |
| 454 | pass is making and what kinds of responses are returned by the alias analysis. |
| 455 | An example usage is:</p> |
| 456 | |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 457 | <pre> |
| 458 | $ opt -basicaa -count-aa -ds-aa -count-aa -licm |
| 459 | </pre> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 460 | |
| 461 | <p>Which will print out how many queries (and what responses are returned) by |
| 462 | the <tt>-licm</tt> pass (of the <tt>-ds-aa</tt> pass) and how many queries are |
| 463 | made of the <tt>-basicaa</tt> pass by the <tt>-ds-aa</tt> pass. This can be |
| 464 | useful when evaluating an alias analysis for precision.</p> |
| 465 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 466 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 467 | |
| 468 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 469 | <div class="doc_subsection"> |
| 470 | <a name="aa-eval">The <tt>-aa-eval</tt> pass</a> |
| 471 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 472 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 473 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 474 | |
| 475 | <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] | 476 | function and asks an alias analysis whether or not the pointers alias. This |
| 477 | gives an indication of the precision of the alias analysis. Statistics are |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 478 | printed. |
| 479 | </p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 480 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 481 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 482 | |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 483 | <!-- *********************************************************************** --> |
| 484 | |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 485 | <hr> |
| 486 | <div class="doc_footer"> |
| 487 | <address><a href="mailto:sabre@nondot.org">Chris Lattner</a></address> |
John Criswell | 0f6d7c0 | 2003-10-27 18:18:16 +0000 | [diff] [blame^] | 488 | <a href="http://llvm.cs.uiuc.edu">The LLVM Compiler Infrastructure</a> |
| 489 | <br> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 490 | Last modified: $Date$ |
| 491 | </div> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 492 | |
| 493 | </body> |
| 494 | </html> |