Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 1 | <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" |
| 2 | "http://www.w3.org/TR/html4/strict.dtd"> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 3 | <html> |
| 4 | <head> |
Misha Brukman | a97e6cb | 2004-07-01 15:33:24 +0000 | [diff] [blame] | 5 | <title>LLVM Alias Analysis Infrastructure</title> |
Misha Brukman | 6e4afd0 | 2004-01-15 19:04:12 +0000 | [diff] [blame] | 6 | <link rel="stylesheet" href="llvm.css" type="text/css"> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 7 | </head> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 8 | <body> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 9 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 10 | <div class="doc_title"> |
Misha Brukman | a97e6cb | 2004-07-01 15:33:24 +0000 | [diff] [blame] | 11 | LLVM Alias Analysis Infrastructure |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 12 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 13 | |
| 14 | <ol> |
Misha Brukman | b215425 | 2003-10-23 02:29:42 +0000 | [diff] [blame] | 15 | <li><a href="#introduction">Introduction</a></li> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 16 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 17 | <li><a href="#overview"><tt>AliasAnalysis</tt> Class Overview</a> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 18 | <ul> |
Misha Brukman | b215425 | 2003-10-23 02:29:42 +0000 | [diff] [blame] | 19 | <li><a href="#pointers">Representation of Pointers</a></li> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 20 | <li><a href="#alias">The <tt>alias</tt> method</a></li> |
Misha Brukman | b215425 | 2003-10-23 02:29:42 +0000 | [diff] [blame] | 21 | <li><a href="#ModRefInfo">The <tt>getModRefInfo</tt> methods</a></li> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 22 | <li><a href="#OtherItfs">Other useful <tt>AliasAnalysis</tt> methods</a></li> |
| 23 | </ul> |
| 24 | </li> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 25 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 26 | <li><a href="#writingnew">Writing a new <tt>AliasAnalysis</tt> Implementation</a> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 27 | <ul> |
Misha Brukman | b215425 | 2003-10-23 02:29:42 +0000 | [diff] [blame] | 28 | <li><a href="#passsubclasses">Different Pass styles</a></li> |
| 29 | <li><a href="#requiredcalls">Required initialization calls</a></li> |
| 30 | <li><a href="#interfaces">Interfaces which may be specified</a></li> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 31 | <li><a href="#chaining"><tt>AliasAnalysis</tt> chaining behavior</a></li> |
| 32 | <li><a href="#updating">Updating analysis results for transformations</a></li> |
Misha Brukman | b215425 | 2003-10-23 02:29:42 +0000 | [diff] [blame] | 33 | <li><a href="#implefficiency">Efficiency Issues</a></li> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 34 | </ul> |
| 35 | </li> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 36 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 37 | <li><a href="#using">Using alias analysis results</a> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 38 | <ul> |
Misha Brukman | b215425 | 2003-10-23 02:29:42 +0000 | [diff] [blame] | 39 | <li><a href="#loadvn">Using the <tt>-load-vn</tt> Pass</a></li> |
| 40 | <li><a href="#ast">Using the <tt>AliasSetTracker</tt> class</a></li> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 41 | <li><a href="#direct">Using the <tt>AliasAnalysis</tt> interface directly</a></li> |
| 42 | </ul> |
| 43 | </li> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 44 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 45 | <li><a href="#exist">Existing alias analysis implementations and clients</a> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 46 | <ul> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 47 | <li><a href="#impls">Available <tt>AliasAnalysis</tt> implementations</a></li> |
| 48 | <li><a href="#aliasanalysis-xforms">Alias analysis driven transformations</a></li> |
Misha Brukman | a97e6cb | 2004-07-01 15:33:24 +0000 | [diff] [blame] | 49 | <li><a href="#aliasanalysis-debug">Clients for debugging and evaluation of |
| 50 | implementations</a></li> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 51 | </ul> |
| 52 | </li> |
Misha Brukman | b215425 | 2003-10-23 02:29:42 +0000 | [diff] [blame] | 53 | </ol> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 54 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 55 | <div class="doc_author"> |
| 56 | <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 57 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 58 | |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 59 | <!-- *********************************************************************** --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 60 | <div class="doc_section"> |
| 61 | <a name="introduction">Introduction</a> |
| 62 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 63 | <!-- *********************************************************************** --> |
| 64 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 65 | <div class="doc_text"> |
Misha Brukman | 1f254d5 | 2003-11-21 22:30:25 +0000 | [diff] [blame] | 66 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 67 | <p>Alias Analysis (aka Pointer Analysis) is a class of techniques which attempt |
| 68 | to determine whether or not two pointers ever can point to the same object in |
| 69 | memory. There are many different algorithms for alias analysis and many |
| 70 | different ways of classifying them: flow-sensitive vs flow-insensitive, |
| 71 | context-sensitive vs context-insensitive, field-sensitive vs field-insensitive, |
| 72 | unification-based vs subset-based, etc. Traditionally, alias analyses respond |
| 73 | to a query with a <a href="#MustNoMay">Must, May, or No</a> alias response, |
| 74 | indicating that two pointers always point to the same object, might point to the |
| 75 | same object, or are known to never point to the same object.</p> |
Misha Brukman | 1f254d5 | 2003-11-21 22:30:25 +0000 | [diff] [blame] | 76 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 77 | <p>The LLVM <a |
| 78 | href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1AliasAnalysis.html"><tt>AliasAnalysis</tt></a> |
| 79 | class is the primary interface used by clients and implementations of alias |
| 80 | analyses in the LLVM system. This class is the common interface between clients |
| 81 | of alias analysis information and the implementations providing it, and is |
| 82 | designed to support a wide range of implementations and clients (but currently |
| 83 | all clients are assumed to be flow-insensitive). In addition to simple alias |
| 84 | analysis information, this class exposes Mod/Ref information from those |
| 85 | implementations which can provide it, allowing for powerful analyses and |
| 86 | transformations to work well together.</p> |
Misha Brukman | 1f254d5 | 2003-11-21 22:30:25 +0000 | [diff] [blame] | 87 | |
| 88 | <p>This document contains information necessary to successfully implement this |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 89 | interface, use it, and to test both sides. It also explains some of the finer |
| 90 | points about what exactly results mean. If you feel that something is unclear |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 91 | or should be added, please <a href="mailto:sabre@nondot.org">let me |
Misha Brukman | 1f254d5 | 2003-11-21 22:30:25 +0000 | [diff] [blame] | 92 | know</a>.</p> |
| 93 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 94 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 95 | |
| 96 | <!-- *********************************************************************** --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 97 | <div class="doc_section"> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 98 | <a name="overview"><tt>AliasAnalysis</tt> Class Overview</a> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 99 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 100 | <!-- *********************************************************************** --> |
| 101 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 102 | <div class="doc_text"> |
Misha Brukman | 1f254d5 | 2003-11-21 22:30:25 +0000 | [diff] [blame] | 103 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 104 | <p>The <a |
| 105 | href="http://llvm.cs.uiuc.edu/doxygen/classllvm_1_1AliasAnalysis.html"><tt>AliasAnalysis</tt></a> |
| 106 | class defines the interface that the various alias analysis implementations |
| 107 | should support. This class exports two important enums: <tt>AliasResult</tt> |
| 108 | and <tt>ModRefResult</tt> which represent the result of an alias query or a |
| 109 | mod/ref query, respectively.</p> |
Misha Brukman | 1f254d5 | 2003-11-21 22:30:25 +0000 | [diff] [blame] | 110 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 111 | <p>The <tt>AliasAnalysis</tt> interface exposes information about memory, |
| 112 | represented in several different ways. In particular, memory objects are |
| 113 | represented as a starting address and size, and function calls are represented |
| 114 | as the actual <tt>call</tt> or <tt>invoke</tt> instructions that performs the |
| 115 | call. The <tt>AliasAnalysis</tt> interface also exposes some helper methods |
| 116 | which allow you to get mod/ref information for arbitrary instructions.</p> |
Misha Brukman | 1f254d5 | 2003-11-21 22:30:25 +0000 | [diff] [blame] | 117 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 118 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 119 | |
| 120 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 121 | <div class="doc_subsection"> |
| 122 | <a name="pointers">Representation of Pointers</a> |
| 123 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 124 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 125 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 126 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 127 | <p>Most importantly, the <tt>AliasAnalysis</tt> class provides several methods |
| 128 | which are used to query whether or not two memory objects alias, whether |
| 129 | function calls can modify or read a memory object, etc. For all of these |
| 130 | queries, memory objects are represented as a pair of their starting address (a |
| 131 | symbolic LLVM <tt>Value*</tt>) and a static size.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 132 | |
| 133 | <p>Representing memory objects as a starting address and a size is critically |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 134 | important for correct Alias Analyses. For example, consider this (silly, but |
| 135 | possible) C code:</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 136 | |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame^] | 137 | <div class="doc_code"> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 138 | <pre> |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame^] | 139 | int i; |
| 140 | char C[2]; |
| 141 | char A[10]; |
| 142 | /* ... */ |
| 143 | for (i = 0; i != 10; ++i) { |
| 144 | C[0] = A[i]; /* One byte store */ |
| 145 | C[1] = A[9-i]; /* One byte store */ |
| 146 | } |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 147 | </pre> |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame^] | 148 | </div> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 149 | |
| 150 | <p>In this case, the <tt>basicaa</tt> pass will disambiguate the stores to |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 151 | <tt>C[0]</tt> and <tt>C[1]</tt> because they are accesses to two distinct |
| 152 | locations one byte apart, and the accesses are each one byte. In this case, the |
| 153 | LICM pass can use store motion to remove the stores from the loop. In |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 154 | constrast, the following code:</p> |
| 155 | |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame^] | 156 | <div class="doc_code"> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 157 | <pre> |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame^] | 158 | int i; |
| 159 | char C[2]; |
| 160 | char A[10]; |
| 161 | /* ... */ |
| 162 | for (i = 0; i != 10; ++i) { |
| 163 | ((short*)C)[0] = A[i]; /* Two byte store! */ |
| 164 | C[1] = A[9-i]; /* One byte store */ |
| 165 | } |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 166 | </pre> |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame^] | 167 | </div> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 168 | |
| 169 | <p>In this case, the two stores to C do alias each other, because the access to |
| 170 | the <tt>&C[0]</tt> element is a two byte access. If size information wasn't |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 171 | available in the query, even the first case would have to conservatively assume |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 172 | that the accesses alias.</p> |
| 173 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 174 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 175 | |
| 176 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 177 | <div class="doc_subsection"> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 178 | <a name="alias">The <tt>alias</tt> method</a> |
| 179 | </div> |
| 180 | |
| 181 | <div class="doc_text"> |
| 182 | The <tt>alias</tt> method is the primary interface used to determine whether or |
| 183 | not two memory objects alias each other. It takes two memory objects as input |
| 184 | and returns MustAlias, MayAlias, or NoAlias as appropriate. |
| 185 | </div> |
| 186 | |
| 187 | <!-- _______________________________________________________________________ --> |
| 188 | <div class="doc_subsubsection"> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 189 | <a name="MustMayNo">Must, May, and No Alias Responses</a> |
| 190 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 191 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 192 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 193 | |
| 194 | <p>An Alias Analysis implementation can return one of three responses: |
| 195 | MustAlias, MayAlias, and NoAlias. The No and May alias results are obvious: if |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 196 | the two pointers can never equal each other, return NoAlias, if they might, |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 197 | return MayAlias.</p> |
| 198 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 199 | <p>The MustAlias response is trickier though. In LLVM, the Must Alias response |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 200 | may only be returned if the two memory objects are guaranteed to always start at |
| 201 | exactly the same location. If two memory objects overlap, but do not start at |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 202 | the same location, return MayAlias.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 203 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 204 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 205 | |
| 206 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 207 | <div class="doc_subsection"> |
| 208 | <a name="ModRefInfo">The <tt>getModRefInfo</tt> methods</a> |
| 209 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 210 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 211 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 212 | |
| 213 | <p>The <tt>getModRefInfo</tt> methods return information about whether the |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 214 | execution of an instruction can read or modify a memory location. Mod/Ref |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 215 | information is always conservative: if an instruction <b>might</b> read or write |
| 216 | a location, ModRef is returned.</p> |
| 217 | |
| 218 | <p>The <tt>AliasAnalysis</tt> class also provides a <tt>getModRefInfo</tt> |
| 219 | method for testing dependencies between function calls. This method takes two |
| 220 | call sites (CS1 & CS2), returns NoModRef if the two calls refer to disjoint |
| 221 | memory locations, Ref if CS1 reads memory written by CS2, Mod if CS1 writes to |
| 222 | memory read or written by CS2, or ModRef if CS1 might read or write memory |
| 223 | accessed by CS2. Note that this relation is not commutative. Clients that use |
| 224 | this method should be predicated on the <tt>hasNoModRefInfoForCalls()</tt> |
| 225 | method, which indicates whether or not an analysis can provide mod/ref |
| 226 | information for function call pairs (most can not). If this predicate is false, |
| 227 | the client shouldn't waste analysis time querying the <tt>getModRefInfo</tt> |
| 228 | method many times.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 229 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 230 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 231 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 232 | |
| 233 | <!-- ======================================================================= --> |
| 234 | <div class="doc_subsection"> |
| 235 | <a name="OtherItfs">Other useful <tt>AliasAnalysis</tt> methods</a> |
| 236 | </div> |
| 237 | |
| 238 | <div class="doc_text"> |
| 239 | |
| 240 | <p> |
| 241 | Several other tidbits of information are often collected by various alias |
| 242 | analysis implementations and can be put to good use by various clients. |
| 243 | </p> |
| 244 | |
| 245 | </div> |
| 246 | |
| 247 | <!-- _______________________________________________________________________ --> |
| 248 | <div class="doc_subsubsection"> |
| 249 | The <tt>getMustAliases</tt> method |
| 250 | </div> |
| 251 | |
| 252 | <div class="doc_text"> |
| 253 | |
| 254 | <p>The <tt>getMustAliases</tt> method returns all values that are known to |
| 255 | always must alias a pointer. This information can be provided in some cases for |
| 256 | important objects like the null pointer and global values. Knowing that a |
| 257 | pointer always points to a particular function allows indirect calls to be |
| 258 | turned into direct calls, for example.</p> |
| 259 | |
| 260 | </div> |
| 261 | |
| 262 | <!-- _______________________________________________________________________ --> |
| 263 | <div class="doc_subsubsection"> |
| 264 | The <tt>pointsToConstantMemory</tt> method |
| 265 | </div> |
| 266 | |
| 267 | <div class="doc_text"> |
| 268 | |
| 269 | <p>The <tt>pointsToConstantMemory</tt> method returns true if and only if the |
| 270 | analysis can prove that the pointer only points to unchanging memory locations |
| 271 | (functions, constant global variables, and the null pointer). This information |
| 272 | can be used to refine mod/ref information: it is impossible for an unchanging |
| 273 | memory location to be modified.</p> |
| 274 | |
| 275 | </div> |
| 276 | |
| 277 | |
| 278 | <!-- _______________________________________________________________________ --> |
| 279 | <div class="doc_subsubsection"> |
| 280 | <a name="simplemodref">The <tt>doesNotAccessMemory</tt> and |
| 281 | <tt>onlyReadsMemory</tt> methods</a> |
| 282 | </div> |
| 283 | |
| 284 | <div class="doc_text"> |
| 285 | |
| 286 | <p>These methods are used to provide very simple mod/ref information for |
| 287 | function calls. The <tt>doesNotAccessMemory</tt> method returns true for a |
| 288 | function if the analysis can prove that the function never reads or writes to |
| 289 | memory, or if the function only reads from constant memory. Functions with this |
| 290 | property are side-effect free and only depend on their input arguments, allowing |
| 291 | them to be eliminated if they form common subexpressions or be hoisted out of |
| 292 | loops. Many common functions behave this way (e.g., <tt>sin</tt> and |
| 293 | <tt>cos</tt>) but many others do not (e.g., <tt>acos</tt>, which modifies the |
| 294 | <tt>errno</tt> variable).</p> |
| 295 | |
| 296 | <p>The <tt>onlyReadsMemory</tt> method returns true for a function if analysis |
| 297 | can prove that (at most) the function only reads from non-volatile memory. |
| 298 | Functions with this property are side-effect free, only depending on their input |
| 299 | arguments and the state of memory when they are called. This property allows |
| 300 | calls to these functions to be eliminated and moved around, as long as there is |
| 301 | no store instruction that changes the contents of memory. Note that all |
| 302 | functions that satisfy the <tt>doesNotAccessMemory</tt> method also satisfies |
| 303 | <tt>onlyReadsMemory</tt>.</p> |
| 304 | |
| 305 | </div> |
| 306 | |
| 307 | |
| 308 | |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 309 | <!-- *********************************************************************** --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 310 | <div class="doc_section"> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 311 | <a name="writingnew">Writing a new <tt>AliasAnalysis</tt> Implementation</a> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 312 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 313 | <!-- *********************************************************************** --> |
| 314 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 315 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 316 | |
| 317 | <p>Writing a new alias analysis implementation for LLVM is quite |
| 318 | straight-forward. There are already several implementations that you can use |
| 319 | for examples, and the following information should help fill in any details. |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 320 | For a examples, take a look at the <a href="#impls">various alias analysis |
| 321 | implementations</a> included with LLVM.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 322 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 323 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 324 | |
| 325 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 326 | <div class="doc_subsection"> |
| 327 | <a name="passsubclasses">Different Pass styles</a> |
| 328 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 329 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 330 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 331 | |
| 332 | <p>The first step to determining what type of <a |
| 333 | href="WritingAnLLVMPass.html">LLVM pass</a> you need to use for your Alias |
| 334 | Analysis. As is the case with most other analyses and transformations, the |
| 335 | answer should be fairly obvious from what type of problem you are trying to |
| 336 | solve:</p> |
| 337 | |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 338 | <ol> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 339 | <li>If you require interprocedural analysis, it should be a |
| 340 | <tt>Pass</tt>.</li> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 341 | <li>If you are a function-local analysis, subclass <tt>FunctionPass</tt>.</li> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 342 | <li>If you don't need to look at the program at all, subclass |
| 343 | <tt>ImmutablePass</tt>.</li> |
| 344 | </ol> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 345 | |
| 346 | <p>In addition to the pass that you subclass, you should also inherit from the |
Misha Brukman | 700fd49 | 2003-05-07 21:47:16 +0000 | [diff] [blame] | 347 | <tt>AliasAnalysis</tt> interface, of course, and use the |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 348 | <tt>RegisterAnalysisGroup</tt> template to register as an implementation of |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 349 | <tt>AliasAnalysis</tt>.</p> |
| 350 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 351 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 352 | |
| 353 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 354 | <div class="doc_subsection"> |
| 355 | <a name="requiredcalls">Required initialization calls</a> |
| 356 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 357 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 358 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 359 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 360 | <p>Your subclass of <tt>AliasAnalysis</tt> is required to invoke two methods on |
| 361 | the <tt>AliasAnalysis</tt> base class: <tt>getAnalysisUsage</tt> and |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 362 | <tt>InitializeAliasAnalysis</tt>. In particular, your implementation of |
| 363 | <tt>getAnalysisUsage</tt> should explicitly call into the |
| 364 | <tt>AliasAnalysis::getAnalysisUsage</tt> method in addition to doing any |
| 365 | declaring any pass dependencies your pass has. Thus you should have something |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 366 | like this:</p> |
| 367 | |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame^] | 368 | <div class="doc_code"> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 369 | <pre> |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame^] | 370 | void getAnalysisUsage(AnalysisUsage &AU) const { |
| 371 | AliasAnalysis::getAnalysisUsage(AU); |
| 372 | <i>// declare your dependencies here.</i> |
| 373 | } |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 374 | </pre> |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame^] | 375 | </div> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 376 | |
| 377 | <p>Additionally, your must invoke the <tt>InitializeAliasAnalysis</tt> method |
| 378 | from your analysis run method (<tt>run</tt> for a <tt>Pass</tt>, |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 379 | <tt>runOnFunction</tt> for a <tt>FunctionPass</tt>, or <tt>InitializePass</tt> |
| 380 | for an <tt>ImmutablePass</tt>). For example (as part of a <tt>Pass</tt>):</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 381 | |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame^] | 382 | <div class="doc_code"> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 383 | <pre> |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame^] | 384 | bool run(Module &M) { |
| 385 | InitializeAliasAnalysis(this); |
| 386 | <i>// Perform analysis here...</i> |
| 387 | return false; |
| 388 | } |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 389 | </pre> |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame^] | 390 | </div> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 391 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 392 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 393 | |
| 394 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 395 | <div class="doc_subsection"> |
| 396 | <a name="interfaces">Interfaces which may be specified</a> |
| 397 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 398 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 399 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 400 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 401 | <p>All of the <a |
| 402 | href="/doxygen/classllvm_1_1AliasAnalysis.html"><tt>AliasAnalysis</tt></a> |
| 403 | virtual methods default to providing <a href="#chaining">chaining</a> to another |
| 404 | alias analysis implementation, which ends up returning conservatively correct |
| 405 | information (returning "May" Alias and "Mod/Ref" for alias and mod/ref queries |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 406 | respectively). Depending on the capabilities of the analysis you are |
| 407 | implementing, you just override the interfaces you can improve.</p> |
| 408 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 409 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 410 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 411 | |
| 412 | |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 413 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 414 | <div class="doc_subsection"> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 415 | <a name="chaining"><tt>AliasAnalysis</tt> chaining behavior</a> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 416 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 417 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 418 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 419 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 420 | <p>With only two special exceptions (the <tt><a |
| 421 | href="#basic-aa">basicaa</a></tt> and <a href="#no-aa"><tt>no-aa</tt></a> |
| 422 | passes) every alias analysis pass chains to another alias analysis |
| 423 | implementation (for example, the user can specify "<tt>-basicaa -ds-aa |
| 424 | -anders-aa -licm</tt>" to get the maximum benefit from the three alias |
| 425 | analyses). The alias analysis class automatically takes care of most of this |
| 426 | for methods that you don't override. For methods that you do override, in code |
| 427 | paths that return a conservative MayAlias or Mod/Ref result, simply return |
| 428 | whatever the superclass computes. For example:</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 429 | |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame^] | 430 | <div class="doc_code"> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 431 | <pre> |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame^] | 432 | AliasAnalysis::AliasResult alias(const Value *V1, unsigned V1Size, |
| 433 | const Value *V2, unsigned V2Size) { |
| 434 | if (...) |
| 435 | return NoAlias; |
| 436 | ... |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 437 | |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame^] | 438 | <i>// Couldn't determine a must or no-alias result.</i> |
| 439 | return AliasAnalysis::alias(V1, V1Size, V2, V2Size); |
| 440 | } |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 441 | </pre> |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame^] | 442 | </div> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 443 | |
| 444 | <p>In addition to analysis queries, you must make sure to unconditionally pass |
| 445 | LLVM <a href="#updating">update notification</a> methods to the superclass as |
| 446 | well if you override them, which allows all alias analyses in a change to be |
| 447 | updated.</p> |
| 448 | |
| 449 | </div> |
| 450 | |
| 451 | |
| 452 | <!-- ======================================================================= --> |
| 453 | <div class="doc_subsection"> |
| 454 | <a name="updating">Updating analysis results for transformations</a> |
| 455 | </div> |
| 456 | |
| 457 | <div class="doc_text"> |
| 458 | <p> |
| 459 | Alias analysis information is initially computed for a static snapshot of the |
| 460 | program, but clients will use this information to make transformations to the |
| 461 | code. All but the most trivial forms of alias analysis will need to have their |
| 462 | analysis results updated to reflect the changes made by these transformations. |
| 463 | </p> |
| 464 | |
| 465 | <p> |
| 466 | The <tt>AliasAnalysis</tt> interface exposes two methods which are used to |
| 467 | communicate program changes from the clients to the analysis implementations. |
| 468 | Various alias analysis implementations should use these methods to ensure that |
| 469 | their internal data structures are kept up-to-date as the program changes (for |
| 470 | example, when an instruction is deleted), and clients of alias analysis must be |
| 471 | sure to call these interfaces appropriately. |
| 472 | </p> |
| 473 | </div> |
| 474 | |
| 475 | <!-- _______________________________________________________________________ --> |
| 476 | <div class="doc_subsubsection">The <tt>deleteValue</tt> method</div> |
| 477 | |
| 478 | <div class="doc_text"> |
| 479 | The <tt>deleteValue</tt> method is called by transformations when they remove an |
| 480 | instruction or any other value from the program (including values that do not |
| 481 | use pointers). Typically alias analyses keep data structures that have entries |
| 482 | for each value in the program. When this method is called, they should remove |
| 483 | any entries for the specified value, if they exist. |
| 484 | </div> |
| 485 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 486 | <!-- _______________________________________________________________________ --> |
| 487 | <div class="doc_subsubsection">The <tt>copyValue</tt> method</div> |
| 488 | |
| 489 | <div class="doc_text"> |
| 490 | The <tt>copyValue</tt> method is used when a new value is introduced into the |
| 491 | program. There is no way to introduce a value into the program that did not |
| 492 | exist before (this doesn't make sense for a safe compiler transformation), so |
| 493 | this is the only way to introduce a new value. This method indicates that the |
| 494 | new value has exactly the same properties as the value being copied. |
| 495 | </div> |
| 496 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 497 | <!-- _______________________________________________________________________ --> |
| 498 | <div class="doc_subsubsection">The <tt>replaceWithNewValue</tt> method</div> |
| 499 | |
| 500 | <div class="doc_text"> |
| 501 | This method is a simple helper method that is provided to make clients easier to |
| 502 | use. It is implemented by copying the old analysis information to the new |
| 503 | value, then deleting the old value. This method cannot be overridden by alias |
| 504 | analysis implementations. |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 505 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 506 | |
| 507 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 508 | <div class="doc_subsection"> |
| 509 | <a name="implefficiency">Efficiency Issues</a> |
| 510 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 511 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 512 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 513 | |
| 514 | <p>From the LLVM perspective, the only thing you need to do to provide an |
| 515 | efficient alias analysis is to make sure that alias analysis <b>queries</b> are |
| 516 | serviced quickly. The actual calculation of the alias analysis results (the |
| 517 | "run" method) is only performed once, but many (perhaps duplicate) queries may |
| 518 | be performed. Because of this, try to move as much computation to the run |
| 519 | method as possible (within reason).</p> |
| 520 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 521 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 522 | |
| 523 | <!-- *********************************************************************** --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 524 | <div class="doc_section"> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 525 | <a name="using">Using alias analysis results</a> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 526 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 527 | <!-- *********************************************************************** --> |
| 528 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 529 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 530 | |
| 531 | <p>There are several different ways to use alias analysis results. In order of |
| 532 | preference, these are...</p> |
| 533 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 534 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 535 | |
| 536 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 537 | <div class="doc_subsection"> |
| 538 | <a name="loadvn">Using the <tt>-load-vn</tt> Pass</a> |
| 539 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 540 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 541 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 542 | |
| 543 | <p>The <tt>load-vn</tt> pass uses alias analysis to provide value numbering |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 544 | information for <tt>load</tt> instructions and pointer values. If your analysis |
| 545 | or transformation can be modeled in a form that uses value numbering |
| 546 | information, you don't have to do anything special to handle load instructions: |
| 547 | just use the <tt>load-vn</tt> pass, which uses alias analysis.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 548 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 549 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 550 | |
| 551 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 552 | <div class="doc_subsection"> |
| 553 | <a name="ast">Using the <tt>AliasSetTracker</tt> class</a> |
| 554 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 555 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 556 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 557 | |
| 558 | <p>Many transformations need information about alias <b>sets</b> that are active |
| 559 | in some scope, rather than information about pairwise aliasing. The <tt><a |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame^] | 560 | href="/doxygen/classllvm_1_1AliasSetTracker.html">AliasSetTracker</a></tt> class |
| 561 | is used to efficiently build these Alias Sets from the pairwise alias analysis |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 562 | information provided by the <tt>AliasAnalysis</tt> interface.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 563 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 564 | <p>First you initialize the AliasSetTracker by using the "<tt>add</tt>" methods |
| 565 | to add information about various potentially aliasing instructions in the scope |
| 566 | you are interested in. Once all of the alias sets are completed, your pass |
| 567 | should simply iterate through the constructed alias sets, using the |
| 568 | <tt>AliasSetTracker</tt> <tt>begin()</tt>/<tt>end()</tt> methods.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 569 | |
| 570 | <p>The <tt>AliasSet</tt>s formed by the <tt>AliasSetTracker</tt> are guaranteed |
Chris Lattner | 539ca70 | 2003-12-19 08:43:07 +0000 | [diff] [blame] | 571 | to be disjoint, calculate mod/ref information and volatility for the set, and |
| 572 | keep track of whether or not all of the pointers in the set are Must aliases. |
| 573 | The AliasSetTracker also makes sure that sets are properly folded due to call |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 574 | instructions, and can provide a list of pointers in each set.</p> |
| 575 | |
| 576 | <p>As an example user of this, the <a href="/doxygen/structLICM.html">Loop |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 577 | Invariant Code Motion</a> pass uses <tt>AliasSetTracker</tt>s to calculate alias |
| 578 | sets for each loop nest. If an <tt>AliasSet</tt> in a loop is not modified, |
| 579 | then all load instructions from that set may be hoisted out of the loop. If any |
| 580 | alias sets are stored to <b>and</b> are must alias sets, then the stores may be |
| 581 | sunk to outside of the loop, promoting the memory location to a register for the |
| 582 | duration of the loop nest. Both of these transformations only apply if the |
| 583 | pointer argument is loop-invariant.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 584 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 585 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 586 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 587 | <!-- _______________________________________________________________________ --> |
Chris Lattner | 539ca70 | 2003-12-19 08:43:07 +0000 | [diff] [blame] | 588 | <div class="doc_subsubsection"> |
| 589 | The AliasSetTracker implementation |
| 590 | </div> |
| 591 | |
| 592 | <div class="doc_text"> |
| 593 | |
| 594 | <p>The AliasSetTracker class is implemented to be as efficient as possible. It |
| 595 | uses the union-find algorithm to efficiently merge AliasSets when a pointer is |
| 596 | inserted into the AliasSetTracker that aliases multiple sets. The primary data |
| 597 | structure is a hash table mapping pointers to the AliasSet they are in.</p> |
| 598 | |
| 599 | <p>The AliasSetTracker class must maintain a list of all of the LLVM Value*'s |
| 600 | that are in each AliasSet. Since the hash table already has entries for each |
| 601 | LLVM Value* of interest, the AliasesSets thread the linked list through these |
| 602 | hash-table nodes to avoid having to allocate memory unnecessarily, and to make |
| 603 | merging alias sets extremely efficient (the linked list merge is constant time). |
| 604 | </p> |
| 605 | |
| 606 | <p>You shouldn't need to understand these details if you are just a client of |
| 607 | the AliasSetTracker, but if you look at the code, hopefully this brief |
| 608 | description will help make sense of why things are designed the way they |
| 609 | are.</p> |
| 610 | |
| 611 | </div> |
| 612 | |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 613 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 614 | <div class="doc_subsection"> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 615 | <a name="direct">Using the <tt>AliasAnalysis</tt> interface directly</a> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 616 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 617 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 618 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 619 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 620 | <p>If neither of these utility class are what your pass needs, you should use |
| 621 | the interfaces exposed by the <tt>AliasAnalysis</tt> class directly. Try to use |
| 622 | the higher-level methods when possible (e.g., use mod/ref information instead of |
| 623 | the <a href="#alias"><tt>alias</tt></a> method directly if possible) to get the |
| 624 | best precision and efficiency.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 625 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 626 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 627 | |
| 628 | <!-- *********************************************************************** --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 629 | <div class="doc_section"> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 630 | <a name="exist">Existing alias analysis implementations and clients</a> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 631 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 632 | <!-- *********************************************************************** --> |
| 633 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 634 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 635 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 636 | <p>If you're going to be working with the LLVM alias analysis infrastructure, |
| 637 | you should know what clients and implementations of alias analysis are |
| 638 | available. In particular, if you are implementing an alias analysis, you should |
| 639 | be aware of the <a href="#aliasanalysis-debug">the clients</a> that are useful |
| 640 | for monitoring and evaluating different implementations.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 641 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 642 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 643 | |
| 644 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 645 | <div class="doc_subsection"> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 646 | <a name="impls">Available <tt>AliasAnalysis</tt> implementations</a> |
| 647 | </div> |
| 648 | |
| 649 | <div class="doc_text"> |
| 650 | |
| 651 | <p>This section lists the various implementations of the <tt>AliasAnalysis</tt> |
| 652 | interface. With the exception of the <a href="#no-aa"><tt>-no-aa</tt></a> and |
| 653 | <a href="#basic-aa"><tt>-basicaa</tt></a> implementations, all of these <a |
Chris Lattner | fcd3725 | 2004-06-21 22:52:48 +0000 | [diff] [blame] | 654 | href="#chaining">chain</a> to other alias analysis implementations.</p> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 655 | |
| 656 | </div> |
| 657 | |
| 658 | <!-- _______________________________________________________________________ --> |
| 659 | <div class="doc_subsubsection"> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 660 | <a name="no-aa">The <tt>-no-aa</tt> pass</a> |
| 661 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 662 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 663 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 664 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 665 | <p>The <tt>-no-aa</tt> pass is just like what it sounds: an alias analysis that |
| 666 | never returns any useful information. This pass can be useful if you think that |
| 667 | alias analysis is doing something wrong and are trying to narrow down a |
| 668 | problem.</p> |
| 669 | |
| 670 | </div> |
| 671 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 672 | <!-- _______________________________________________________________________ --> |
| 673 | <div class="doc_subsubsection"> |
| 674 | <a name="basic-aa">The <tt>-basicaa</tt> pass</a> |
| 675 | </div> |
| 676 | |
| 677 | <div class="doc_text"> |
| 678 | |
| 679 | <p>The <tt>-basicaa</tt> pass is the default LLVM alias analysis. It is an |
| 680 | aggressive local analysis that "knows" many important facts:</p> |
| 681 | |
| 682 | <ul> |
| 683 | <li>Distinct globals, stack allocations, and heap allocations can never |
| 684 | alias.</li> |
| 685 | <li>Globals, stack allocations, and heap allocations never alias the null |
| 686 | pointer.</li> |
| 687 | <li>Different fields of a structure do not alias.</li> |
| 688 | <li>Indexes into arrays with statically differing subscripts cannot alias.</li> |
| 689 | <li>Many common standard C library functions <a |
| 690 | href="#simplemodref">never access memory or only read memory</a>.</li> |
| 691 | <li>Pointers that obviously point to constant globals |
| 692 | "<tt>pointToConstantMemory</tt>".</li> |
| 693 | <li>Function calls can not modify or references stack allocations if they never |
| 694 | escape from the function that allocates them (a common case for automatic |
| 695 | arrays).</li> |
| 696 | </ul> |
| 697 | |
| 698 | </div> |
| 699 | |
Chris Lattner | 100a4f8 | 2004-06-28 19:19:47 +0000 | [diff] [blame] | 700 | <!-- _______________________________________________________________________ --> |
| 701 | <div class="doc_subsubsection"> |
| 702 | <a name="globalsmodref">The <tt>-globalsmodref-aa</tt> pass</a> |
| 703 | </div> |
| 704 | |
| 705 | <div class="doc_text"> |
| 706 | |
| 707 | <p>This pass implements a simple context-sensitive mod/ref and alias analysis |
Chris Lattner | ccb354b | 2004-07-27 07:50:07 +0000 | [diff] [blame] | 708 | for internal global variables that don't "have their address taken". If a |
| 709 | global does not have its address taken, the pass knows that no pointers alias |
| 710 | the global. This pass also keeps track of functions that it knows never access |
| 711 | memory or never read memory. This allows certain optimizations (e.g. GCSE) to |
| 712 | eliminate call instructions entirely. |
Chris Lattner | 100a4f8 | 2004-06-28 19:19:47 +0000 | [diff] [blame] | 713 | </p> |
| 714 | |
| 715 | <p>The real power of this pass is that it provides context-sensitive mod/ref |
| 716 | information for call instructions. This allows the optimizer to know that |
| 717 | calls to a function do not clobber or read the value of the global, allowing |
| 718 | loads and stores to be eliminated.</p> |
| 719 | |
| 720 | <p>Note that this pass is somewhat limited in its scope (only support |
| 721 | non-address taken globals), but is very quick analysis.</p> |
| 722 | </div> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 723 | |
| 724 | <!-- _______________________________________________________________________ --> |
| 725 | <div class="doc_subsubsection"> |
| 726 | <a name="anders-aa">The <tt>-anders-aa</tt> pass</a> |
| 727 | </div> |
| 728 | |
| 729 | <div class="doc_text"> |
| 730 | |
| 731 | <p>The <tt>-anders-aa</tt> pass implements the well-known "Andersen's algorithm" |
| 732 | for interprocedural alias analysis. This algorithm is a subset-based, |
| 733 | flow-insensitive, context-insensitive, and field-insensitive alias analysis that |
| 734 | is widely believed to be fairly precise. Unfortunately, this algorithm is also |
| 735 | O(N<sup>3</sup>). The LLVM implementation currently does not implement any of |
| 736 | the refinements (such as "online cycle elimination" or "offline variable |
| 737 | substitution") to improve its efficiency, so it can be quite slow in common |
| 738 | cases. |
| 739 | </p> |
| 740 | |
| 741 | </div> |
| 742 | |
| 743 | <!-- _______________________________________________________________________ --> |
| 744 | <div class="doc_subsubsection"> |
| 745 | <a name="steens-aa">The <tt>-steens-aa</tt> pass</a> |
| 746 | </div> |
| 747 | |
| 748 | <div class="doc_text"> |
| 749 | |
| 750 | <p>The <tt>-steens-aa</tt> pass implements a variation on the well-known |
| 751 | "Steensgaard's algorithm" for interprocedural alias analysis. Steensgaard's |
| 752 | algorithm is a unification-based, flow-insensitive, context-insensitive, and |
| 753 | field-insensitive alias analysis that is also very scalable (effectively linear |
| 754 | time).</p> |
| 755 | |
| 756 | <p>The LLVM <tt>-steens-aa</tt> pass implements a "speculatively |
| 757 | field-<b>sensitive</b>" version of Steensgaard's algorithm using the Data |
| 758 | Structure Analysis framework. This gives it substantially more precision than |
| 759 | the standard algorithm while maintaining excellent analysis scalability.</p> |
| 760 | |
| 761 | </div> |
| 762 | |
| 763 | <!-- _______________________________________________________________________ --> |
| 764 | <div class="doc_subsubsection"> |
| 765 | <a name="ds-aa">The <tt>-ds-aa</tt> pass</a> |
| 766 | </div> |
| 767 | |
| 768 | <div class="doc_text"> |
| 769 | |
| 770 | <p>The <tt>-ds-aa</tt> pass implements the full Data Structure Analysis |
| 771 | algorithm. Data Structure Analysis is a modular unification-based, |
| 772 | flow-insensitive, context-<b>sensitive</b>, and speculatively |
| 773 | field-<b>sensitive</b> alias analysis that is also quite scalable, usually at |
| 774 | O(n*log(n)).</p> |
| 775 | |
| 776 | <p>This algorithm is capable of responding to a full variety of alias analysis |
| 777 | queries, and can provide context-sensitive mod/ref information as well. The |
| 778 | only major facility not implemented so far is support for must-alias |
| 779 | information.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 780 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 781 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 782 | |
| 783 | |
| 784 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 785 | <div class="doc_subsection"> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 786 | <a name="aliasanalysis-xforms">Alias analysis driven transformations</a> |
| 787 | </div> |
| 788 | |
| 789 | <div class="doc_text"> |
| 790 | LLVM includes several alias-analysis driven transformations which can be used |
| 791 | with any of the implementations above. |
| 792 | </div> |
| 793 | |
| 794 | <!-- _______________________________________________________________________ --> |
| 795 | <div class="doc_subsubsection"> |
| 796 | <a name="adce">The <tt>-adce</tt> pass</a> |
| 797 | </div> |
| 798 | |
| 799 | <div class="doc_text"> |
| 800 | |
| 801 | <p>The <tt>-adce</tt> pass, which implements Aggressive Dead Code Elimination |
| 802 | uses the <tt>AliasAnalysis</tt> interface to delete calls to functions that do |
| 803 | not have side-effects and are not used.</p> |
| 804 | |
| 805 | </div> |
| 806 | |
| 807 | |
| 808 | <!-- _______________________________________________________________________ --> |
| 809 | <div class="doc_subsubsection"> |
| 810 | <a name="licm">The <tt>-licm</tt> pass</a> |
| 811 | </div> |
| 812 | |
| 813 | <div class="doc_text"> |
| 814 | |
| 815 | <p>The <tt>-licm</tt> pass implements various Loop Invariant Code Motion related |
| 816 | transformations. It uses the <tt>AliasAnalysis</tt> interface for several |
| 817 | different transformations:</p> |
| 818 | |
| 819 | <ul> |
| 820 | <li>It uses mod/ref information to hoist or sink load instructions out of loops |
| 821 | if there are no instructions in the loop that modifies the memory loaded.</li> |
| 822 | |
| 823 | <li>It uses mod/ref information to hoist function calls out of loops that do not |
| 824 | write to memory and are loop-invariant.</li> |
| 825 | |
| 826 | <li>If uses alias information to promote memory objects that are loaded and |
| 827 | stored to in loops to live in a register instead. It can do this if there are |
| 828 | no may aliases to the loaded/stored memory location.</li> |
| 829 | </ul> |
| 830 | |
| 831 | </div> |
| 832 | |
| 833 | <!-- _______________________________________________________________________ --> |
| 834 | <div class="doc_subsubsection"> |
| 835 | <a name="argpromotion">The <tt>-argpromotion</tt> pass</a> |
| 836 | </div> |
| 837 | |
| 838 | <div class="doc_text"> |
| 839 | <p> |
| 840 | The <tt>-argpromotion</tt> pass promotes by-reference arguments to be passed in |
| 841 | by-value instead. In particular, if pointer arguments are only loaded from it |
| 842 | passes in the value loaded instead of the address to the function. This pass |
| 843 | uses alias information to make sure that the value loaded from the argument |
| 844 | pointer is not modified between the entry of the function and any load of the |
| 845 | pointer.</p> |
| 846 | </div> |
| 847 | |
| 848 | <!-- _______________________________________________________________________ --> |
| 849 | <div class="doc_subsubsection"> |
| 850 | <a name="gcseloadvn">The <tt>-load-vn</tt> & <tt>-gcse</tt> passes</a> |
| 851 | </div> |
| 852 | |
| 853 | <div class="doc_text"> |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame^] | 854 | |
| 855 | <p>The <tt>-load-vn</tt> pass uses alias analysis to "<a href="#loadvn">value |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 856 | number</a>" loads and pointers values, which is used by the GCSE pass to |
| 857 | eliminate instructions. The <tt>-load-vn</tt> pass relies on alias information |
| 858 | and must-alias information. This combination of passes can make the following |
| 859 | transformations:</p> |
| 860 | |
| 861 | <ul> |
| 862 | <li>Redundant load instructions are eliminated.</li> |
| 863 | <li>Load instructions that follow a store to the same location are replaced with |
| 864 | the stored value ("store forwarding").</li> |
| 865 | <li>Pointers values (e.g. formal arguments) that must-alias simpler expressions |
| 866 | (e.g. global variables or the null pointer) are replaced. Note that this |
| 867 | implements transformations like "virtual method resolution", turning indirect |
| 868 | calls into direct calls.</li> |
| 869 | </ul> |
| 870 | |
| 871 | </div> |
| 872 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 873 | <!-- ======================================================================= --> |
| 874 | <div class="doc_subsection"> |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame^] | 875 | <a name="aliasanalysis-debug">Clients for debugging and evaluation of |
| 876 | implementations</a> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 877 | </div> |
| 878 | |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame^] | 879 | <div class="doc_text"> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 880 | |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame^] | 881 | <p>These passes are useful for evaluating the various alias analysis |
| 882 | implementations. You can use them with commands like '<tt>opt -anders-aa -ds-aa |
| 883 | -aa-eval foo.bc -disable-output -stats</tt>'.</p> |
| 884 | |
| 885 | </div> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 886 | |
| 887 | <!-- _______________________________________________________________________ --> |
| 888 | <div class="doc_subsubsection"> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 889 | <a name="print-alias-sets">The <tt>-print-alias-sets</tt> pass</a> |
| 890 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 891 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 892 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 893 | |
| 894 | <p>The <tt>-print-alias-sets</tt> pass is exposed as part of the |
| 895 | <tt>analyze</tt> tool to print out the Alias Sets formed by the <a |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 896 | href="#ast"><tt>AliasSetTracker</tt></a> class. This is useful if you're using |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 897 | the <tt>AliasSetTracker</tt> class.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 898 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 899 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 900 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 901 | |
| 902 | <!-- _______________________________________________________________________ --> |
| 903 | <div class="doc_subsubsection"> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 904 | <a name="count-aa">The <tt>-count-aa</tt> pass</a> |
| 905 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 906 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 907 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 908 | |
| 909 | <p>The <tt>-count-aa</tt> pass is useful to see how many queries a particular |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame^] | 910 | pass is making and what responses are returned by the alias analysis. As an |
| 911 | example,</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 912 | |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame^] | 913 | <div class="doc_code"> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 914 | <pre> |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame^] | 915 | % opt -basicaa -count-aa -ds-aa -count-aa -licm |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 916 | </pre> |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame^] | 917 | </div> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 918 | |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame^] | 919 | <p>will print out how many queries (and what responses are returned) by the |
| 920 | <tt>-licm</tt> pass (of the <tt>-ds-aa</tt> pass) and how many queries are made |
| 921 | of the <tt>-basicaa</tt> pass by the <tt>-ds-aa</tt> pass. This can be useful |
| 922 | when debugging a transformation or an alias analysis implementation.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 923 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 924 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 925 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 926 | <!-- _______________________________________________________________________ --> |
| 927 | <div class="doc_subsubsection"> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 928 | <a name="aa-eval">The <tt>-aa-eval</tt> pass</a> |
| 929 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 930 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 931 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 932 | |
| 933 | <p>The <tt>-aa-eval</tt> pass simply iterates through all pairs of pointers in a |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 934 | function and asks an alias analysis whether or not the pointers alias. This |
| 935 | gives an indication of the precision of the alias analysis. Statistics are |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 936 | printed indicating the percent of no/may/must aliases found (a more precise |
| 937 | algorithm will have a lower number of may aliases).</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 938 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 939 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 940 | |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 941 | <!-- *********************************************************************** --> |
| 942 | |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 943 | <hr> |
Misha Brukman | 915cab2 | 2003-11-22 01:26:21 +0000 | [diff] [blame] | 944 | <address> |
Misha Brukman | 38847d5 | 2003-12-21 22:53:21 +0000 | [diff] [blame] | 945 | <a href="http://jigsaw.w3.org/css-validator/check/referer"><img |
Misha Brukman | 5feba4e | 2003-11-22 01:07:30 +0000 | [diff] [blame] | 946 | src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a> |
Misha Brukman | 915cab2 | 2003-11-22 01:26:21 +0000 | [diff] [blame] | 947 | <a href="http://validator.w3.org/check/referer"><img |
Misha Brukman | f6acb51 | 2004-05-12 18:02:00 +0000 | [diff] [blame] | 948 | src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a> |
Misha Brukman | 915cab2 | 2003-11-22 01:26:21 +0000 | [diff] [blame] | 949 | |
| 950 | <a href="mailto:sabre@nondot.org">Chris Lattner</a><br> |
Misha Brukman | f6acb51 | 2004-05-12 18:02:00 +0000 | [diff] [blame] | 951 | <a href="http://llvm.cs.uiuc.edu">LLVM Compiler Infrastructure</a><br> |
Misha Brukman | 915cab2 | 2003-11-22 01:26:21 +0000 | [diff] [blame] | 952 | Last modified: $Date$ |
| 953 | </address> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 954 | |
| 955 | </body> |
| 956 | </html> |