docs/AliasAnalysis.html

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