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