docs/AliasAnalysis.html

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