1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
2 "http://www.w3.org/TR/html4/strict.dtd">
5 <link rel="stylesheet" href="llvm.css" type="text/css">
6 <title>Alias Analysis Infrastructure in LLVM</title>
11 <div class="doc_title">
12 Alias Analysis Infrastructure in LLVM
16 <li><a href="#introduction">Introduction</a></li>
18 <li><a href="#overview">AliasAnalysis Overview</a>
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>
25 <li><a href="#writingnew">Writing a new AliasAnalysis Implementation</a>
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>
34 <li><a href="#using">Using AliasAnalysis results</a>
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>
41 <li><a href="#tools">Helpful alias analysis related tools</a>
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>
50 <div class="doc_text">
51 <p><b>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></b></p>
54 <!-- *********************************************************************** -->
55 <div class="doc_section">
56 <a name="introduction">Introduction</a>
58 <!-- *********************************************************************** -->
60 <div class="doc_text">
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.
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
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
87 <!-- *********************************************************************** -->
88 <div class="doc_section">
89 <a name="overview">AliasAnalysis Overview</a>
91 <!-- *********************************************************************** -->
93 <div class="doc_text">
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,
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.
111 <!-- ======================================================================= -->
112 <div class="doc_subsection">
113 <a name="pointers">Representation of Pointers</a>
116 <div class="doc_text">
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>
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
131 for (i = 0; i != 10; ++i) {
132 C[0] = A[i]; /* One byte store */
133 C[1] = A[9-i]; /* One byte store */
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>
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 */
154 <p>In this case, the two stores to C do alias each other, because the access to
155 the <tt>&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>
161 <!-- ======================================================================= -->
162 <div class="doc_subsection">
163 <a name="MustMayNo">Must, May, and No Alias Responses</a>
166 <div class="doc_text">
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,
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>
180 <!-- ======================================================================= -->
181 <div class="doc_subsection">
182 <a name="ModRefInfo">The <tt>getModRefInfo</tt> methods</a>
185 <div class="doc_text">
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
194 <!-- *********************************************************************** -->
195 <div class="doc_section">
196 <a name="writingnew">Writing a new AliasAnalysis Implementation</a>
198 <!-- *********************************************************************** -->
200 <div class="doc_text">
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>
210 <!-- ======================================================================= -->
211 <div class="doc_subsection">
212 <a name="passsubclasses">Different Pass styles</a>
215 <div class="doc_text">
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
224 <li>If you require interprocedural analysis, it should be a
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>
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>
239 <!-- ======================================================================= -->
240 <div class="doc_subsection">
241 <a name="requiredcalls">Required initialization calls</a>
244 <div class="doc_text">
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
255 void getAnalysisUsage(AnalysisUsage &AU) const {
256 AliasAnalysis::getAnalysisUsage(AU);
257 <i>// declare your dependencies here.</i>
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>
268 bool run(Module &M) {
269 InitializeAliasAnalysis(this);
270 <i>// Perform analysis here...</i>
277 <!-- ======================================================================= -->
278 <div class="doc_subsection">
279 <a name="interfaces">Interfaces which may be specified</a>
282 <div class="doc_text">
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>
292 <!-- ======================================================================= -->
293 <div class="doc_subsection">
294 <a name="chaining">The AliasAnalysis chaining behavior</a>
297 <div class="doc_text">
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>
309 <!-- ======================================================================= -->
310 <div class="doc_subsection">
311 <a name="implefficiency">Efficiency Issues</a>
314 <div class="doc_text">
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>
325 <!-- *********************************************************************** -->
326 <div class="doc_section">
327 <a name="using">Using AliasAnalysis results</a>
329 <!-- *********************************************************************** -->
331 <div class="doc_text">
333 <p>There are several different ways to use alias analysis results. In order of
334 preference, these are...</p>
338 <!-- ======================================================================= -->
339 <div class="doc_subsection">
340 <a name="loadvn">Using the <tt>-load-vn</tt> Pass</a>
343 <div class="doc_text">
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>
353 <!-- ======================================================================= -->
354 <div class="doc_subsection">
355 <a name="ast">Using the <tt>AliasSetTracker</tt> class</a>
358 <div class="doc_text">
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>
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>
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>
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>
388 <!-- ======================================================================= -->
389 <div class="doc_subsection">
390 <a name="direct">Using the AliasAnalysis interface directly</a>
393 <div class="doc_text">
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>
402 <!-- *********************************************************************** -->
403 <div class="doc_section">
404 <a name="tools">Helpful alias-analysis-related tools</a>
406 <!-- *********************************************************************** -->
408 <div class="doc_text">
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
416 <!-- ======================================================================= -->
417 <div class="doc_subsection">
418 <a name="no-aa">The <tt>-no-aa</tt> pass</a>
421 <div class="doc_text">
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>
432 <!-- ======================================================================= -->
433 <div class="doc_subsection">
434 <a name="print-alias-sets">The <tt>-print-alias-sets</tt> pass</a>
437 <div class="doc_text">
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>
446 <!-- ======================================================================= -->
447 <div class="doc_subsection">
448 <a name="count-aa">The <tt>-count-aa</tt> pass</a>
451 <div class="doc_text">
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>
458 $ opt -basicaa -count-aa -ds-aa -count-aa -licm
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>
468 <!-- ======================================================================= -->
469 <div class="doc_subsection">
470 <a name="aa-eval">The <tt>-aa-eval</tt> pass</a>
473 <div class="doc_text">
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
483 <!-- *********************************************************************** -->
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>
490 Last modified: $Date$