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   <title>Alias Analysis Infrastructure in LLVM</title>
   6   <link rel="stylesheet" href="llvm.css" type="text/css">
   7 </head>
   8 <body>
   9
  10 <div class="doc_title">
  11   Alias Analysis Infrastructure in LLVM
  12 </div>
  13
  14 <ol>
  15   <li><a href="#introduction">Introduction</a></li>
  16
  17   <li><a href="#overview">AliasAnalysis Overview</a>
  18     <ul>
  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>
  22     </ul></li>
  23
  24   <li><a href="#writingnew">Writing a new AliasAnalysis Implementation</a>
  25     <ul>
  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>
  31     </ul></li>
  32
  33   <li><a href="#using">Using AliasAnalysis results</a>
  34     <ul>
  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>
  38     </ul></li>
  39
  40   <li><a href="#tools">Helpful alias analysis related tools</a>
  41     <ul>
  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>
  46     </ul></li>
  47 </ol>
  48
  49 <div class="doc_text">
  50   <p><b>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></b></p>
  51 </div>
  52
  53 <!-- *********************************************************************** -->
  54 <div class="doc_section">
  55   <a name="introduction">Introduction</a>
  56 </div>
  57 <!-- *********************************************************************** -->
  58
  59 <div class="doc_text">
  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
  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
  66 known not to point to the same object.</p>
  67
  68 <p>The <a href="/doxygen/classllvm_1_1AliasAnalysis.html">AliasAnalysis</a> class is the
  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
  74 together.</p>
  75
  76 <p>This document contains information necessary to successfully implement this
  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
  79 or should be added, please <a href="mailto:sabre@nondot.org">let me
  80 know</a>.</p>
  81
  82 </div>
  83
  84 <!-- *********************************************************************** -->
  85 <div class="doc_section">
  86   <a name="overview">AliasAnalysis Overview</a>
  87 </div>
  88 <!-- *********************************************************************** -->
  89
  90 <div class="doc_text">
  91
  92 <p>The <a href="/doxygen/classllvm_1_1AliasAnalysis.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
  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
 103 mod/ref information for arbitrary instructions.</p>
 104
 105 </div>
 106
 107 <!-- ======================================================================= -->
 108 <div class="doc_subsection">
 109   <a name="pointers">Representation of Pointers</a>
 110 </div>
 111
 112 <div class="doc_text">
 113
 114 <p>Most importantly, the AliasAnalysis class provides several methods which are
 115 used to query whether or not pointers alias, whether function calls can modify
 116 or read memory, etc.</p>
 117
 118 <p>Representing memory objects as a starting address and a size is critically
 119 important for precise Alias Analyses.  For example, consider this (silly) C
 120 code:</p>
 121
 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>
 132
 133 <p>In this case, the <tt>basicaa</tt> pass will disambiguate the stores to
 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
 137 constrast, the following code:</p>
 138
 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>
 149
 150 <p>In this case, the two stores to C do alias each other, because the access to
 151 the <tt>&amp;C[0]</tt> element is a two byte access.  If size information wasn't
 152 available in the query, even the first case would have to conservatively assume
 153 that the accesses alias.</p>
 154
 155 </div>
 156
 157 <!-- ======================================================================= -->
 158 <div class="doc_subsection">
 159   <a name="MustMayNo">Must, May, and No Alias Responses</a>
 160 </div>
 161
 162 <div class="doc_text">
 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
 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
 172 the same location, MayAlias must be returned.</p>
 173
 174 </div>
 175
 176 <!-- ======================================================================= -->
 177 <div class="doc_subsection">
 178   <a name="ModRefInfo">The <tt>getModRefInfo</tt> methods</a>
 179 </div>
 180
 181 <div class="doc_text">
 182
 183 <p>The <tt>getModRefInfo</tt> methods return information about whether the
 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
 186 is returned.</p>
 187
 188 </div>
 189
 190 <!-- *********************************************************************** -->
 191 <div class="doc_section">
 192   <a name="writingnew">Writing a new AliasAnalysis Implementation</a>
 193 </div>
 194 <!-- *********************************************************************** -->
 195
 196 <div class="doc_text">
 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/structllvm_1_1NoAA.html"><tt>no-aa</tt></a> implementation.</p>
 203
 204 </div>
 205
 206 <!-- ======================================================================= -->
 207 <div class="doc_subsection">
 208   <a name="passsubclasses">Different Pass styles</a>
 209 </div>
 210
 211 <div class="doc_text">
 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
 219 <ol>
 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>
 227
 228 <p>In addition to the pass that you subclass, you should also inherit from the
 229 <tt>AliasAnalysis</tt> interface, of course, and use the
 230 <tt>RegisterAnalysisGroup</tt> template to register as an implementation of
 231 <tt>AliasAnalysis</tt>.</p>
 232
 233 </div>
 234
 235 <!-- ======================================================================= -->
 236 <div class="doc_subsection">
 237   <a name="requiredcalls">Required initialization calls</a>
 238 </div>
 239
 240 <div class="doc_text">
 241
 242 <p>Your subclass of AliasAnalysis is required to invoke two methods on the
 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
 248 like this:</p>
 249
 250 <pre>
 251     void getAnalysisUsage(AnalysisUsage &amp;AU) const {
 252       AliasAnalysis::getAnalysisUsage(AU);
 253       <i>// declare your dependencies here.</i>
 254     }
 255 </pre>
 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>,
 259 <tt>runOnFunction</tt> for a <tt>FunctionPass</tt>, <tt>runOnBasicBlock</tt> for
 260 a <tt>BasicBlockPass</tt>, or <tt>InitializeAliasAnalysis</tt> for an
 261 <tt>ImmutablePass</tt>).  For example (as part of a <tt>Pass</tt>):</p>
 262
 263 <pre>
 264     bool run(Module &amp;M) {
 265       InitializeAliasAnalysis(this);
 266       <i>// Perform analysis here...</i>
 267       return false;
 268     }
 269 </pre>
 270
 271 </div>
 272
 273 <!-- ======================================================================= -->
 274 <div class="doc_subsection">
 275   <a name="interfaces">Interfaces which may be specified</a>
 276 </div>
 277
 278 <div class="doc_text">
 279
 280 <p>All of the <a href="/doxygen/classllvm_1_1AliasAnalysis.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
 286 </div>
 287
 288 <!-- ======================================================================= -->
 289 <div class="doc_subsection">
 290   <a name="chaining">The AliasAnalysis chaining behavior</a>
 291 </div>
 292
 293 <div class="doc_text">
 294
 295 <p>With only two special exceptions (the <tt>basicaa</tt> and <a
 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
 301 MayAlias or Mod/Ref result, simply chain to a lower analysis.</p>
 302
 303 </div>
 304
 305 <!-- ======================================================================= -->
 306 <div class="doc_subsection">
 307   <a name="implefficiency">Efficiency Issues</a>
 308 </div>
 309
 310 <div class="doc_text">
 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
 319 </div>
 320
 321 <!-- *********************************************************************** -->
 322 <div class="doc_section">
 323   <a name="using">Using AliasAnalysis results</a>
 324 </div>
 325 <!-- *********************************************************************** -->
 326
 327 <div class="doc_text">
 328
 329 <p>There are several different ways to use alias analysis results.  In order of
 330 preference, these are...</p>
 331
 332 </div>
 333
 334 <!-- ======================================================================= -->
 335 <div class="doc_subsection">
 336   <a name="loadvn">Using the <tt>-load-vn</tt> Pass</a>
 337 </div>
 338
 339 <div class="doc_text">
 340
 341 <p>The <tt>load-vn</tt> pass uses alias analysis to provide value numbering
 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
 345 <tt>load-vn</tt> pass, which uses alias analysis.</p>
 346
 347 </div>
 348
 349 <!-- ======================================================================= -->
 350 <div class="doc_subsection">
 351   <a name="ast">Using the <tt>AliasSetTracker</tt> class</a>
 352 </div>
 353
 354 <div class="doc_text">
 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
 358 href="/doxygen/classllvm_1_1AliasSetTracker.html">AliasSetTracker</a></tt> class is used
 359 to efficiently build these Alias Sets from the pairwise alias analysis
 360 information provided by the AliasAnalysis interface.</p>
 361
 362 <p>First you initialize the AliasSetTracker by use the "<tt>add</tt>" methods to
 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
 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 and volatility for the set, and
 370 keep track of whether or not all of the pointers in the set are Must aliases.
 371 The AliasSetTracker also makes sure that sets are properly folded due to call
 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
 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, promoting the memory location to a register for the
 380 duration of the loop nest.  Both of these transformations obviously only apply
 381 if the pointer argument is loop-invariant.</p>
 382
 383 </div>
 384
 385 <div class="doc_subsubsection">
 386   The AliasSetTracker implementation
 387 </div>
 388
 389 <div class="doc_text">
 390
 391 <p>The AliasSetTracker class is implemented to be as efficient as possible.  It
 392 uses the union-find algorithm to efficiently merge AliasSets when a pointer is
 393 inserted into the AliasSetTracker that aliases multiple sets.  The primary data
 394 structure is a hash table mapping pointers to the AliasSet they are in.</p>
 395
 396 <p>The AliasSetTracker class must maintain a list of all of the LLVM Value*'s
 397 that are in each AliasSet.  Since the hash table already has entries for each
 398 LLVM Value* of interest, the AliasesSets thread the linked list through these
 399 hash-table nodes to avoid having to allocate memory unnecessarily, and to make
 400 merging alias sets extremely efficient (the linked list merge is constant time).
 401 </p>
 402
 403 <p>You shouldn't need to understand these details if you are just a client of
 404 the AliasSetTracker, but if you look at the code, hopefully this brief
 405 description will help make sense of why things are designed the way they
 406 are.</p>
 407
 408 </div>
 409
 410
 411 <!-- ======================================================================= -->
 412 <div class="doc_subsection">
 413   <a name="direct">Using the AliasAnalysis interface directly</a>
 414 </div>
 415
 416 <div class="doc_text">
 417
 418 <p>As a last resort, your pass could use the AliasAnalysis interface directly to
 419 service your pass.  If you find the need to do this, please <a
 420 href="mailto:sabre@nondot.org">let me know</a> so I can see if something new
 421 needs to be added to LLVM.</p>
 422
 423 </div>
 424
 425 <!-- *********************************************************************** -->
 426 <div class="doc_section">
 427   <a name="tools">Helpful alias-analysis-related tools</a>
 428 </div>
 429 <!-- *********************************************************************** -->
 430
 431 <div class="doc_text">
 432
 433 <p>If you're going to be working with the AliasAnalysis infrastructure, there
 434 are several nice tools that may be useful for you and are worth knowing
 435 about...</p>
 436
 437 </div>
 438
 439 <!-- ======================================================================= -->
 440 <div class="doc_subsection">
 441   <a name="no-aa">The <tt>-no-aa</tt> pass</a>
 442 </div>
 443
 444 <div class="doc_text">
 445
 446 <p>The <tt>-no-aa</tt> analysis is just like what it sounds: an alias analysis
 447 that never returns any useful information.  This pass can be useful if you think
 448 that alias analysis is doing something wrong and are trying to narrow down a
 449 problem.  If you don't specify an alias analysis, the default will be to use the
 450 <tt>basicaa</tt> pass which does quite a bit of disambiguation on its own.</p>
 451
 452 </div>
 453
 454
 455 <!-- ======================================================================= -->
 456 <div class="doc_subsection">
 457   <a name="print-alias-sets">The <tt>-print-alias-sets</tt> pass</a>
 458 </div>
 459
 460 <div class="doc_text">
 461
 462 <p>The <tt>-print-alias-sets</tt> pass is exposed as part of the
 463 <tt>analyze</tt> tool to print out the Alias Sets formed by the <a
 464 href="#ast"><tt>AliasSetTracker</tt></a> class.  This is useful if you're using
 465 the <tt>AliasSetTracker</tt>.</p>
 466
 467 </div>
 468
 469 <!-- ======================================================================= -->
 470 <div class="doc_subsection">
 471   <a name="count-aa">The <tt>-count-aa</tt> pass</a>
 472 </div>
 473
 474 <div class="doc_text">
 475
 476 <p>The <tt>-count-aa</tt> pass is useful to see how many queries a particular
 477 pass is making and what kinds of responses are returned by the alias analysis.
 478 An example usage is:</p>
 479
 480 <pre>
 481   $ opt -basicaa -count-aa -ds-aa -count-aa -licm
 482 </pre>
 483
 484 <p>Which will print out how many queries (and what responses are returned) by
 485 the <tt>-licm</tt> pass (of the <tt>-ds-aa</tt> pass) and how many queries are
 486 made of the <tt>-basicaa</tt> pass by the <tt>-ds-aa</tt> pass.  This can be
 487 useful when evaluating an alias analysis for precision.</p>
 488
 489 </div>
 490
 491 <!-- ======================================================================= -->
 492 <div class="doc_subsection">
 493   <a name="aa-eval">The <tt>-aa-eval</tt> pass</a>
 494 </div>
 495
 496 <div class="doc_text">
 497
 498 <p>The <tt>-aa-eval</tt> pass simply iterates through all pairs of pointers in a
 499 function and asks an alias analysis whether or not the pointers alias.  This
 500 gives an indication of the precision of the alias analysis.  Statistics are
 501 printed.</p>
 502
 503 </div>
 504
 505 <!-- *********************************************************************** -->
 506
 507 <hr>
 508 <address>
 509   <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
 510   src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
 511   <a href="http://validator.w3.org/check/referer"><img
 512   src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!" /></a>
 513
 514   <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
 515   <a href="http://llvm.cs.uiuc.edu">The LLVM Compiler Infrastructure</a><br>
 516   Last modified: $Date$
 517 </address>
 518
 519 </body>
 520 </html>