docs/AliasAnalysis.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
   2                       "http://www.w3.org/TR/html4/strict.dtd">
   3 <html>
   4 <head>
   5   <link rel="stylesheet" href="llvm.css" type="text/css">
   6   <title>Alias Analysis Infrastructure in LLVM</title>
   7 </head>
   8
   9 <body>
  10
  11 <div class="doc_title">
  12   Alias Analysis Infrastructure in LLVM
  13 </div>
  14
  15 <ol>
  16   <li><a href="#introduction">Introduction</a></li>
  17
  18   <li><a href="#overview">AliasAnalysis Overview</a>
  19     <ul>
  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>
  23     </ul></li>
  24
  25   <li><a href="#writingnew">Writing a new AliasAnalysis Implementation</a>
  26     <ul>
  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>
  32     </ul></li>
  33
  34   <li><a href="#using">Using AliasAnalysis results</a>
  35     <ul>
  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>
  39     </ul></li>
  40
  41   <li><a href="#tools">Helpful alias analysis related tools</a>
  42     <ul>
  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>
  47     </ul></li>
  48 </ol>
  49
  50 <div class="doc_text">
  51   <p><b>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></b></p>
  52 </div>
  53
  54 <!-- *********************************************************************** -->
  55 <div class="doc_section">
  56   <a name="introduction">Introduction</a>
  57 </div>
  58 <!-- *********************************************************************** -->
  59
  60 <div class="doc_text">
  61 <p>
  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
  67 known not to point to the same object.
  68 </p>
  69 <p>
  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
  76 together.
  77 </p>
  78 <p>
  79 This document contains information necessary to successfully implement this
  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
  82 or should be added, please <a href="mailto:sabre@nondot.org">let me
  83 know</a>.
  84 </p>
  85 </div>
  86
  87 <!-- *********************************************************************** -->
  88 <div class="doc_section">
  89   <a name="overview">AliasAnalysis Overview</a>
  90 </div>
  91 <!-- *********************************************************************** -->
  92
  93 <div class="doc_text">
  94 <p>
  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,
  99 respectively.
 100 </p>
 101 <p>
 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
 107 mod/ref information for arbitrary instructions.
 108 </p>
 109 </div>
 110
 111 <!-- ======================================================================= -->
 112 <div class="doc_subsection">
 113   <a name="pointers">Representation of Pointers</a>
 114 </div>
 115
 116 <div class="doc_text">
 117
 118 <p>Most importantly, the AliasAnalysis class provides several methods which are
 119 used to query whether or not pointers alias, whether function calls can modify
 120 or read memory, etc.</p>
 121
 122 <p>Representing memory objects as a starting address and a size is critically
 123 important for precise Alias Analyses.  For example, consider this (silly) C
 124 code:</p>
 125
 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>
 136
 137 <p>In this case, the <tt>basicaa</tt> pass will disambiguate the stores to
 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
 141 constrast, the following code:</p>
 142
 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>
 153
 154 <p>In this case, the two stores to C do alias each other, because the access to
 155 the <tt>&amp;C[0]</tt> element is a two byte access.  If size information wasn't
 156 available in the query, even the first case would have to conservatively assume
 157 that the accesses alias.</p>
 158
 159 </div>
 160
 161 <!-- ======================================================================= -->
 162 <div class="doc_subsection">
 163   <a name="MustMayNo">Must, May, and No Alias Responses</a>
 164 </div>
 165
 166 <div class="doc_text">
 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
 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
 176 the same location, MayAlias must be returned.</p>
 177
 178 </div>
 179
 180 <!-- ======================================================================= -->
 181 <div class="doc_subsection">
 182   <a name="ModRefInfo">The <tt>getModRefInfo</tt> methods</a>
 183 </div>
 184
 185 <div class="doc_text">
 186
 187 <p>The <tt>getModRefInfo</tt> methods return information about whether the
 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
 190 is returned.</p>
 191
 192 </div>
 193
 194 <!-- *********************************************************************** -->
 195 <div class="doc_section">
 196   <a name="writingnew">Writing a new AliasAnalysis Implementation</a>
 197 </div>
 198 <!-- *********************************************************************** -->
 199
 200 <div class="doc_text">
 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
 208 </div>
 209
 210 <!-- ======================================================================= -->
 211 <div class="doc_subsection">
 212   <a name="passsubclasses">Different Pass styles</a>
 213 </div>
 214
 215 <div class="doc_text">
 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
 223 <ol>
 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>
 231
 232 <p>In addition to the pass that you subclass, you should also inherit from the
 233 <tt>AliasAnalysis</tt> interface, of course, and use the
 234 <tt>RegisterAnalysisGroup</tt> template to register as an implementation of
 235 <tt>AliasAnalysis</tt>.</p>
 236
 237 </div>
 238
 239 <!-- ======================================================================= -->
 240 <div class="doc_subsection">
 241   <a name="requiredcalls">Required initialization calls</a>
 242 </div>
 243
 244 <div class="doc_text">
 245
 246 <p>Your subclass of AliasAnalysis is required to invoke two methods on the
 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
 252 like this:</p>
 253
 254 <pre>
 255     void getAnalysisUsage(AnalysisUsage &amp;AU) const {
 256       AliasAnalysis::getAnalysisUsage(AU);
 257       <i>// declare your dependencies here.</i>
 258     }
 259 </pre>
 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>,
 263 <tt>runOnFunction</tt> for a <tt>FunctionPass</tt>, <tt>runOnBasicBlock</tt> for
 264 a <tt>BasicBlockPass</tt>, or <tt>InitializeAliasAnalysis</tt> for an
 265 <tt>ImmutablePass</tt>).  For example (as part of a <tt>Pass</tt>):</p>
 266
 267 <pre>
 268     bool run(Module &amp;M) {
 269       InitializeAliasAnalysis(this);
 270       <i>// Perform analysis here...</i>
 271       return false;
 272     }
 273 </pre>
 274
 275 </div>
 276
 277 <!-- ======================================================================= -->
 278 <div class="doc_subsection">
 279   <a name="interfaces">Interfaces which may be specified</a>
 280 </div>
 281
 282 <div class="doc_text">
 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
 290 </div>
 291
 292 <!-- ======================================================================= -->
 293 <div class="doc_subsection">
 294   <a name="chaining">The AliasAnalysis chaining behavior</a>
 295 </div>
 296
 297 <div class="doc_text">
 298
 299 <p>With only two special exceptions (the <tt>basicaa</tt> and <a
 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
 305 MayAlias or Mod/Ref result, simply chain to a lower analysis.</p>
 306
 307 </div>
 308
 309 <!-- ======================================================================= -->
 310 <div class="doc_subsection">
 311   <a name="implefficiency">Efficiency Issues</a>
 312 </div>
 313
 314 <div class="doc_text">
 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
 323 </div>
 324
 325 <!-- *********************************************************************** -->
 326 <div class="doc_section">
 327   <a name="using">Using AliasAnalysis results</a>
 328 </div>
 329 <!-- *********************************************************************** -->
 330
 331 <div class="doc_text">
 332
 333 <p>There are several different ways to use alias analysis results.  In order of
 334 preference, these are...</p>
 335
 336 </div>
 337
 338 <!-- ======================================================================= -->
 339 <div class="doc_subsection">
 340   <a name="loadvn">Using the <tt>-load-vn</tt> Pass</a>
 341 </div>
 342
 343 <div class="doc_text">
 344
 345 <p>The <tt>load-vn</tt> pass uses alias analysis to provide value numbering
 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
 349 <tt>load-vn</tt> pass, which uses alias analysis.</p>
 350
 351 </div>
 352
 353 <!-- ======================================================================= -->
 354 <div class="doc_subsection">
 355   <a name="ast">Using the <tt>AliasSetTracker</tt> class</a>
 356 </div>
 357
 358 <div class="doc_text">
 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
 362 href="/doxygen/classAliasSetTracker.html">AliasSetTracker</a></tt> class is used
 363 to efficiently build these Alias Sets from the pairwise alias analysis
 364 information provided by the AliasAnalysis interface.</p>
 365
 366 <p>First you initialize the AliasSetTracker by use the "<tt>add</tt>" methods to
 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
 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
 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
 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
 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
 384 pointer argument is loop-invariant.</p>
 385
 386 </div>
 387
 388 <!-- ======================================================================= -->
 389 <div class="doc_subsection">
 390   <a name="direct">Using the AliasAnalysis interface directly</a>
 391 </div>
 392
 393 <div class="doc_text">
 394
 395 <p>As a last resort, your pass could use the AliasAnalysis interface directly to
 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
 398 needs to be added to LLVM.</p>
 399
 400 </div>
 401
 402 <!-- *********************************************************************** -->
 403 <div class="doc_section">
 404   <a name="tools">Helpful alias-analysis-related tools</a>
 405 </div>
 406 <!-- *********************************************************************** -->
 407
 408 <div class="doc_text">
 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
 414 </div>
 415
 416 <!-- ======================================================================= -->
 417 <div class="doc_subsection">
 418   <a name="no-aa">The <tt>-no-aa</tt> pass</a>
 419 </div>
 420
 421 <div class="doc_text">
 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
 429 </div>
 430
 431
 432 <!-- ======================================================================= -->
 433 <div class="doc_subsection">
 434   <a name="print-alias-sets">The <tt>-print-alias-sets</tt> pass</a>
 435 </div>
 436
 437 <div class="doc_text">
 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
 441 href="#ast"><tt>AliasSetTracker</tt></a> class.  This is useful if you're using
 442 the <tt>AliasSetTracker</tt>.</p>
 443
 444 </div>
 445
 446 <!-- ======================================================================= -->
 447 <div class="doc_subsection">
 448   <a name="count-aa">The <tt>-count-aa</tt> pass</a>
 449 </div>
 450
 451 <div class="doc_text">
 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
 457 <pre>
 458   $ opt -basicaa -count-aa -ds-aa -count-aa -licm
 459 </pre>
 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
 466 </div>
 467
 468 <!-- ======================================================================= -->
 469 <div class="doc_subsection">
 470   <a name="aa-eval">The <tt>-aa-eval</tt> pass</a>
 471 </div>
 472
 473 <div class="doc_text">
 474
 475 <p>The <tt>-aa-eval</tt> pass simply iterates through all pairs of pointers in a
 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
 478 printed.
 479 </p>
 480
 481 </div>
 482
 483 <!-- *********************************************************************** -->
 484
 485 <hr>
 486 <div class="doc_footer">
 487   <address><a href="mailto:sabre@nondot.org">Chris Lattner</a></address>
 488   <a href="http://llvm.cs.uiuc.edu">The LLVM Compiler Infrastructure</a>
 489   <br>
 490   Last modified: $Date$
 491 </div>
 492
 493 </body>
 494 </html>