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 |
Reid Spencer | 05fe4b0 | 2006-03-14 05:39:39 +0000 | [diff] [blame^] | 78 | href="http://llvm.org/doxygen/classllvm_1_1AliasAnalysis.html"><tt>AliasAnalysis</tt></a> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 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 |
Reid Spencer | 05fe4b0 | 2006-03-14 05:39:39 +0000 | [diff] [blame^] | 105 | href="http://llvm.org/doxygen/classllvm_1_1AliasAnalysis.html"><tt>AliasAnalysis</tt></a> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 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 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 277 | <!-- _______________________________________________________________________ --> |
| 278 | <div class="doc_subsubsection"> |
| 279 | <a name="simplemodref">The <tt>doesNotAccessMemory</tt> and |
| 280 | <tt>onlyReadsMemory</tt> methods</a> |
| 281 | </div> |
| 282 | |
| 283 | <div class="doc_text"> |
| 284 | |
| 285 | <p>These methods are used to provide very simple mod/ref information for |
| 286 | function calls. The <tt>doesNotAccessMemory</tt> method returns true for a |
| 287 | function if the analysis can prove that the function never reads or writes to |
| 288 | memory, or if the function only reads from constant memory. Functions with this |
| 289 | property are side-effect free and only depend on their input arguments, allowing |
| 290 | them to be eliminated if they form common subexpressions or be hoisted out of |
| 291 | loops. Many common functions behave this way (e.g., <tt>sin</tt> and |
| 292 | <tt>cos</tt>) but many others do not (e.g., <tt>acos</tt>, which modifies the |
| 293 | <tt>errno</tt> variable).</p> |
| 294 | |
| 295 | <p>The <tt>onlyReadsMemory</tt> method returns true for a function if analysis |
| 296 | can prove that (at most) the function only reads from non-volatile memory. |
| 297 | Functions with this property are side-effect free, only depending on their input |
| 298 | arguments and the state of memory when they are called. This property allows |
| 299 | calls to these functions to be eliminated and moved around, as long as there is |
| 300 | no store instruction that changes the contents of memory. Note that all |
| 301 | functions that satisfy the <tt>doesNotAccessMemory</tt> method also satisfies |
| 302 | <tt>onlyReadsMemory</tt>.</p> |
| 303 | |
| 304 | </div> |
| 305 | |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 306 | <!-- *********************************************************************** --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 307 | <div class="doc_section"> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 308 | <a name="writingnew">Writing a new <tt>AliasAnalysis</tt> Implementation</a> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 309 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 310 | <!-- *********************************************************************** --> |
| 311 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 312 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 313 | |
| 314 | <p>Writing a new alias analysis implementation for LLVM is quite |
| 315 | straight-forward. There are already several implementations that you can use |
| 316 | for examples, and the following information should help fill in any details. |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 317 | For a examples, take a look at the <a href="#impls">various alias analysis |
| 318 | implementations</a> included with LLVM.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 319 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 320 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 321 | |
| 322 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 323 | <div class="doc_subsection"> |
| 324 | <a name="passsubclasses">Different Pass styles</a> |
| 325 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 326 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 327 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 328 | |
| 329 | <p>The first step to determining what type of <a |
| 330 | href="WritingAnLLVMPass.html">LLVM pass</a> you need to use for your Alias |
| 331 | Analysis. As is the case with most other analyses and transformations, the |
| 332 | answer should be fairly obvious from what type of problem you are trying to |
| 333 | solve:</p> |
| 334 | |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 335 | <ol> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 336 | <li>If you require interprocedural analysis, it should be a |
| 337 | <tt>Pass</tt>.</li> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 338 | <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] | 339 | <li>If you don't need to look at the program at all, subclass |
| 340 | <tt>ImmutablePass</tt>.</li> |
| 341 | </ol> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 342 | |
| 343 | <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] | 344 | <tt>AliasAnalysis</tt> interface, of course, and use the |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 345 | <tt>RegisterAnalysisGroup</tt> template to register as an implementation of |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 346 | <tt>AliasAnalysis</tt>.</p> |
| 347 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 348 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 349 | |
| 350 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 351 | <div class="doc_subsection"> |
| 352 | <a name="requiredcalls">Required initialization calls</a> |
| 353 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 354 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 355 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 356 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 357 | <p>Your subclass of <tt>AliasAnalysis</tt> is required to invoke two methods on |
| 358 | the <tt>AliasAnalysis</tt> base class: <tt>getAnalysisUsage</tt> and |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 359 | <tt>InitializeAliasAnalysis</tt>. In particular, your implementation of |
| 360 | <tt>getAnalysisUsage</tt> should explicitly call into the |
| 361 | <tt>AliasAnalysis::getAnalysisUsage</tt> method in addition to doing any |
| 362 | declaring any pass dependencies your pass has. Thus you should have something |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 363 | like this:</p> |
| 364 | |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame] | 365 | <div class="doc_code"> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 366 | <pre> |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame] | 367 | void getAnalysisUsage(AnalysisUsage &AU) const { |
| 368 | AliasAnalysis::getAnalysisUsage(AU); |
| 369 | <i>// declare your dependencies here.</i> |
| 370 | } |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 371 | </pre> |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame] | 372 | </div> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 373 | |
| 374 | <p>Additionally, your must invoke the <tt>InitializeAliasAnalysis</tt> method |
| 375 | 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] | 376 | <tt>runOnFunction</tt> for a <tt>FunctionPass</tt>, or <tt>InitializePass</tt> |
| 377 | 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] | 378 | |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame] | 379 | <div class="doc_code"> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 380 | <pre> |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame] | 381 | bool run(Module &M) { |
| 382 | InitializeAliasAnalysis(this); |
| 383 | <i>// Perform analysis here...</i> |
| 384 | return false; |
| 385 | } |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 386 | </pre> |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame] | 387 | </div> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 388 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 389 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 390 | |
| 391 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 392 | <div class="doc_subsection"> |
| 393 | <a name="interfaces">Interfaces which may be specified</a> |
| 394 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 395 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 396 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 397 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 398 | <p>All of the <a |
| 399 | href="/doxygen/classllvm_1_1AliasAnalysis.html"><tt>AliasAnalysis</tt></a> |
| 400 | virtual methods default to providing <a href="#chaining">chaining</a> to another |
| 401 | alias analysis implementation, which ends up returning conservatively correct |
| 402 | 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] | 403 | respectively). Depending on the capabilities of the analysis you are |
| 404 | implementing, you just override the interfaces you can improve.</p> |
| 405 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 406 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 407 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 408 | |
| 409 | |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 410 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 411 | <div class="doc_subsection"> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 412 | <a name="chaining"><tt>AliasAnalysis</tt> chaining behavior</a> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 413 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 414 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 415 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 416 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 417 | <p>With only two special exceptions (the <tt><a |
| 418 | href="#basic-aa">basicaa</a></tt> and <a href="#no-aa"><tt>no-aa</tt></a> |
| 419 | passes) every alias analysis pass chains to another alias analysis |
| 420 | implementation (for example, the user can specify "<tt>-basicaa -ds-aa |
| 421 | -anders-aa -licm</tt>" to get the maximum benefit from the three alias |
| 422 | analyses). The alias analysis class automatically takes care of most of this |
| 423 | for methods that you don't override. For methods that you do override, in code |
| 424 | paths that return a conservative MayAlias or Mod/Ref result, simply return |
| 425 | whatever the superclass computes. For example:</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 426 | |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame] | 427 | <div class="doc_code"> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 428 | <pre> |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame] | 429 | AliasAnalysis::AliasResult alias(const Value *V1, unsigned V1Size, |
| 430 | const Value *V2, unsigned V2Size) { |
| 431 | if (...) |
| 432 | return NoAlias; |
| 433 | ... |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 434 | |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame] | 435 | <i>// Couldn't determine a must or no-alias result.</i> |
| 436 | return AliasAnalysis::alias(V1, V1Size, V2, V2Size); |
| 437 | } |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 438 | </pre> |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame] | 439 | </div> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 440 | |
| 441 | <p>In addition to analysis queries, you must make sure to unconditionally pass |
| 442 | LLVM <a href="#updating">update notification</a> methods to the superclass as |
| 443 | well if you override them, which allows all alias analyses in a change to be |
| 444 | updated.</p> |
| 445 | |
| 446 | </div> |
| 447 | |
| 448 | |
| 449 | <!-- ======================================================================= --> |
| 450 | <div class="doc_subsection"> |
| 451 | <a name="updating">Updating analysis results for transformations</a> |
| 452 | </div> |
| 453 | |
| 454 | <div class="doc_text"> |
| 455 | <p> |
| 456 | Alias analysis information is initially computed for a static snapshot of the |
| 457 | program, but clients will use this information to make transformations to the |
| 458 | code. All but the most trivial forms of alias analysis will need to have their |
| 459 | analysis results updated to reflect the changes made by these transformations. |
| 460 | </p> |
| 461 | |
| 462 | <p> |
| 463 | The <tt>AliasAnalysis</tt> interface exposes two methods which are used to |
| 464 | communicate program changes from the clients to the analysis implementations. |
| 465 | Various alias analysis implementations should use these methods to ensure that |
| 466 | their internal data structures are kept up-to-date as the program changes (for |
| 467 | example, when an instruction is deleted), and clients of alias analysis must be |
| 468 | sure to call these interfaces appropriately. |
| 469 | </p> |
| 470 | </div> |
| 471 | |
| 472 | <!-- _______________________________________________________________________ --> |
| 473 | <div class="doc_subsubsection">The <tt>deleteValue</tt> method</div> |
| 474 | |
| 475 | <div class="doc_text"> |
| 476 | The <tt>deleteValue</tt> method is called by transformations when they remove an |
| 477 | instruction or any other value from the program (including values that do not |
| 478 | use pointers). Typically alias analyses keep data structures that have entries |
| 479 | for each value in the program. When this method is called, they should remove |
| 480 | any entries for the specified value, if they exist. |
| 481 | </div> |
| 482 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 483 | <!-- _______________________________________________________________________ --> |
| 484 | <div class="doc_subsubsection">The <tt>copyValue</tt> method</div> |
| 485 | |
| 486 | <div class="doc_text"> |
| 487 | The <tt>copyValue</tt> method is used when a new value is introduced into the |
| 488 | program. There is no way to introduce a value into the program that did not |
| 489 | exist before (this doesn't make sense for a safe compiler transformation), so |
| 490 | this is the only way to introduce a new value. This method indicates that the |
| 491 | new value has exactly the same properties as the value being copied. |
| 492 | </div> |
| 493 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 494 | <!-- _______________________________________________________________________ --> |
| 495 | <div class="doc_subsubsection">The <tt>replaceWithNewValue</tt> method</div> |
| 496 | |
| 497 | <div class="doc_text"> |
| 498 | This method is a simple helper method that is provided to make clients easier to |
| 499 | use. It is implemented by copying the old analysis information to the new |
| 500 | value, then deleting the old value. This method cannot be overridden by alias |
| 501 | analysis implementations. |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 502 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 503 | |
| 504 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 505 | <div class="doc_subsection"> |
| 506 | <a name="implefficiency">Efficiency Issues</a> |
| 507 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 508 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 509 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 510 | |
| 511 | <p>From the LLVM perspective, the only thing you need to do to provide an |
| 512 | efficient alias analysis is to make sure that alias analysis <b>queries</b> are |
| 513 | serviced quickly. The actual calculation of the alias analysis results (the |
| 514 | "run" method) is only performed once, but many (perhaps duplicate) queries may |
| 515 | be performed. Because of this, try to move as much computation to the run |
| 516 | method as possible (within reason).</p> |
| 517 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 518 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 519 | |
| 520 | <!-- *********************************************************************** --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 521 | <div class="doc_section"> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 522 | <a name="using">Using alias analysis results</a> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 523 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 524 | <!-- *********************************************************************** --> |
| 525 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 526 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 527 | |
| 528 | <p>There are several different ways to use alias analysis results. In order of |
| 529 | preference, these are...</p> |
| 530 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 531 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 532 | |
| 533 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 534 | <div class="doc_subsection"> |
| 535 | <a name="loadvn">Using the <tt>-load-vn</tt> Pass</a> |
| 536 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 537 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 538 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 539 | |
| 540 | <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] | 541 | information for <tt>load</tt> instructions and pointer values. If your analysis |
| 542 | or transformation can be modeled in a form that uses value numbering |
| 543 | information, you don't have to do anything special to handle load instructions: |
| 544 | 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] | 545 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 546 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 547 | |
| 548 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 549 | <div class="doc_subsection"> |
| 550 | <a name="ast">Using the <tt>AliasSetTracker</tt> class</a> |
| 551 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 552 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 553 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 554 | |
| 555 | <p>Many transformations need information about alias <b>sets</b> that are active |
| 556 | in some scope, rather than information about pairwise aliasing. The <tt><a |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame] | 557 | href="/doxygen/classllvm_1_1AliasSetTracker.html">AliasSetTracker</a></tt> class |
| 558 | 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] | 559 | information provided by the <tt>AliasAnalysis</tt> interface.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 560 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 561 | <p>First you initialize the AliasSetTracker by using the "<tt>add</tt>" methods |
| 562 | to add information about various potentially aliasing instructions in the scope |
| 563 | you are interested in. Once all of the alias sets are completed, your pass |
| 564 | should simply iterate through the constructed alias sets, using the |
| 565 | <tt>AliasSetTracker</tt> <tt>begin()</tt>/<tt>end()</tt> methods.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 566 | |
| 567 | <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] | 568 | to be disjoint, calculate mod/ref information and volatility for the set, and |
| 569 | keep track of whether or not all of the pointers in the set are Must aliases. |
| 570 | 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] | 571 | instructions, and can provide a list of pointers in each set.</p> |
| 572 | |
| 573 | <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] | 574 | Invariant Code Motion</a> pass uses <tt>AliasSetTracker</tt>s to calculate alias |
| 575 | sets for each loop nest. If an <tt>AliasSet</tt> in a loop is not modified, |
| 576 | then all load instructions from that set may be hoisted out of the loop. If any |
| 577 | alias sets are stored to <b>and</b> are must alias sets, then the stores may be |
| 578 | sunk to outside of the loop, promoting the memory location to a register for the |
| 579 | duration of the loop nest. Both of these transformations only apply if the |
| 580 | pointer argument is loop-invariant.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 581 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 582 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 583 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 584 | <!-- _______________________________________________________________________ --> |
Chris Lattner | 539ca70 | 2003-12-19 08:43:07 +0000 | [diff] [blame] | 585 | <div class="doc_subsubsection"> |
| 586 | The AliasSetTracker implementation |
| 587 | </div> |
| 588 | |
| 589 | <div class="doc_text"> |
| 590 | |
| 591 | <p>The AliasSetTracker class is implemented to be as efficient as possible. It |
| 592 | uses the union-find algorithm to efficiently merge AliasSets when a pointer is |
| 593 | inserted into the AliasSetTracker that aliases multiple sets. The primary data |
| 594 | structure is a hash table mapping pointers to the AliasSet they are in.</p> |
| 595 | |
| 596 | <p>The AliasSetTracker class must maintain a list of all of the LLVM Value*'s |
| 597 | that are in each AliasSet. Since the hash table already has entries for each |
| 598 | LLVM Value* of interest, the AliasesSets thread the linked list through these |
| 599 | hash-table nodes to avoid having to allocate memory unnecessarily, and to make |
| 600 | merging alias sets extremely efficient (the linked list merge is constant time). |
| 601 | </p> |
| 602 | |
| 603 | <p>You shouldn't need to understand these details if you are just a client of |
| 604 | the AliasSetTracker, but if you look at the code, hopefully this brief |
| 605 | description will help make sense of why things are designed the way they |
| 606 | are.</p> |
| 607 | |
| 608 | </div> |
| 609 | |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 610 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 611 | <div class="doc_subsection"> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 612 | <a name="direct">Using the <tt>AliasAnalysis</tt> interface directly</a> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 613 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 614 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 615 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 616 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 617 | <p>If neither of these utility class are what your pass needs, you should use |
| 618 | the interfaces exposed by the <tt>AliasAnalysis</tt> class directly. Try to use |
| 619 | the higher-level methods when possible (e.g., use mod/ref information instead of |
| 620 | the <a href="#alias"><tt>alias</tt></a> method directly if possible) to get the |
| 621 | best precision and efficiency.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 622 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 623 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 624 | |
| 625 | <!-- *********************************************************************** --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 626 | <div class="doc_section"> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 627 | <a name="exist">Existing alias analysis implementations and clients</a> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 628 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 629 | <!-- *********************************************************************** --> |
| 630 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 631 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 632 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 633 | <p>If you're going to be working with the LLVM alias analysis infrastructure, |
| 634 | you should know what clients and implementations of alias analysis are |
| 635 | available. In particular, if you are implementing an alias analysis, you should |
| 636 | be aware of the <a href="#aliasanalysis-debug">the clients</a> that are useful |
| 637 | for monitoring and evaluating different implementations.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 638 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 639 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 640 | |
| 641 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 642 | <div class="doc_subsection"> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 643 | <a name="impls">Available <tt>AliasAnalysis</tt> implementations</a> |
| 644 | </div> |
| 645 | |
| 646 | <div class="doc_text"> |
| 647 | |
| 648 | <p>This section lists the various implementations of the <tt>AliasAnalysis</tt> |
| 649 | interface. With the exception of the <a href="#no-aa"><tt>-no-aa</tt></a> and |
| 650 | <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] | 651 | href="#chaining">chain</a> to other alias analysis implementations.</p> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 652 | |
| 653 | </div> |
| 654 | |
| 655 | <!-- _______________________________________________________________________ --> |
| 656 | <div class="doc_subsubsection"> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 657 | <a name="no-aa">The <tt>-no-aa</tt> pass</a> |
| 658 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 659 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 660 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 661 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 662 | <p>The <tt>-no-aa</tt> pass is just like what it sounds: an alias analysis that |
| 663 | never returns any useful information. This pass can be useful if you think that |
| 664 | alias analysis is doing something wrong and are trying to narrow down a |
| 665 | problem.</p> |
| 666 | |
| 667 | </div> |
| 668 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 669 | <!-- _______________________________________________________________________ --> |
| 670 | <div class="doc_subsubsection"> |
| 671 | <a name="basic-aa">The <tt>-basicaa</tt> pass</a> |
| 672 | </div> |
| 673 | |
| 674 | <div class="doc_text"> |
| 675 | |
| 676 | <p>The <tt>-basicaa</tt> pass is the default LLVM alias analysis. It is an |
| 677 | aggressive local analysis that "knows" many important facts:</p> |
| 678 | |
| 679 | <ul> |
| 680 | <li>Distinct globals, stack allocations, and heap allocations can never |
| 681 | alias.</li> |
| 682 | <li>Globals, stack allocations, and heap allocations never alias the null |
| 683 | pointer.</li> |
| 684 | <li>Different fields of a structure do not alias.</li> |
| 685 | <li>Indexes into arrays with statically differing subscripts cannot alias.</li> |
| 686 | <li>Many common standard C library functions <a |
| 687 | href="#simplemodref">never access memory or only read memory</a>.</li> |
| 688 | <li>Pointers that obviously point to constant globals |
| 689 | "<tt>pointToConstantMemory</tt>".</li> |
| 690 | <li>Function calls can not modify or references stack allocations if they never |
| 691 | escape from the function that allocates them (a common case for automatic |
| 692 | arrays).</li> |
| 693 | </ul> |
| 694 | |
| 695 | </div> |
| 696 | |
Chris Lattner | 100a4f8 | 2004-06-28 19:19:47 +0000 | [diff] [blame] | 697 | <!-- _______________________________________________________________________ --> |
| 698 | <div class="doc_subsubsection"> |
| 699 | <a name="globalsmodref">The <tt>-globalsmodref-aa</tt> pass</a> |
| 700 | </div> |
| 701 | |
| 702 | <div class="doc_text"> |
| 703 | |
| 704 | <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] | 705 | for internal global variables that don't "have their address taken". If a |
| 706 | global does not have its address taken, the pass knows that no pointers alias |
| 707 | the global. This pass also keeps track of functions that it knows never access |
| 708 | memory or never read memory. This allows certain optimizations (e.g. GCSE) to |
| 709 | eliminate call instructions entirely. |
Chris Lattner | 100a4f8 | 2004-06-28 19:19:47 +0000 | [diff] [blame] | 710 | </p> |
| 711 | |
| 712 | <p>The real power of this pass is that it provides context-sensitive mod/ref |
| 713 | information for call instructions. This allows the optimizer to know that |
| 714 | calls to a function do not clobber or read the value of the global, allowing |
| 715 | loads and stores to be eliminated.</p> |
| 716 | |
| 717 | <p>Note that this pass is somewhat limited in its scope (only support |
| 718 | non-address taken globals), but is very quick analysis.</p> |
| 719 | </div> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 720 | |
| 721 | <!-- _______________________________________________________________________ --> |
| 722 | <div class="doc_subsubsection"> |
| 723 | <a name="anders-aa">The <tt>-anders-aa</tt> pass</a> |
| 724 | </div> |
| 725 | |
| 726 | <div class="doc_text"> |
| 727 | |
| 728 | <p>The <tt>-anders-aa</tt> pass implements the well-known "Andersen's algorithm" |
| 729 | for interprocedural alias analysis. This algorithm is a subset-based, |
| 730 | flow-insensitive, context-insensitive, and field-insensitive alias analysis that |
| 731 | is widely believed to be fairly precise. Unfortunately, this algorithm is also |
| 732 | O(N<sup>3</sup>). The LLVM implementation currently does not implement any of |
| 733 | the refinements (such as "online cycle elimination" or "offline variable |
| 734 | substitution") to improve its efficiency, so it can be quite slow in common |
| 735 | cases. |
| 736 | </p> |
| 737 | |
| 738 | </div> |
| 739 | |
| 740 | <!-- _______________________________________________________________________ --> |
| 741 | <div class="doc_subsubsection"> |
| 742 | <a name="steens-aa">The <tt>-steens-aa</tt> pass</a> |
| 743 | </div> |
| 744 | |
| 745 | <div class="doc_text"> |
| 746 | |
| 747 | <p>The <tt>-steens-aa</tt> pass implements a variation on the well-known |
| 748 | "Steensgaard's algorithm" for interprocedural alias analysis. Steensgaard's |
| 749 | algorithm is a unification-based, flow-insensitive, context-insensitive, and |
| 750 | field-insensitive alias analysis that is also very scalable (effectively linear |
| 751 | time).</p> |
| 752 | |
| 753 | <p>The LLVM <tt>-steens-aa</tt> pass implements a "speculatively |
| 754 | field-<b>sensitive</b>" version of Steensgaard's algorithm using the Data |
| 755 | Structure Analysis framework. This gives it substantially more precision than |
| 756 | the standard algorithm while maintaining excellent analysis scalability.</p> |
| 757 | |
| 758 | </div> |
| 759 | |
| 760 | <!-- _______________________________________________________________________ --> |
| 761 | <div class="doc_subsubsection"> |
| 762 | <a name="ds-aa">The <tt>-ds-aa</tt> pass</a> |
| 763 | </div> |
| 764 | |
| 765 | <div class="doc_text"> |
| 766 | |
| 767 | <p>The <tt>-ds-aa</tt> pass implements the full Data Structure Analysis |
| 768 | algorithm. Data Structure Analysis is a modular unification-based, |
| 769 | flow-insensitive, context-<b>sensitive</b>, and speculatively |
| 770 | field-<b>sensitive</b> alias analysis that is also quite scalable, usually at |
| 771 | O(n*log(n)).</p> |
| 772 | |
| 773 | <p>This algorithm is capable of responding to a full variety of alias analysis |
| 774 | queries, and can provide context-sensitive mod/ref information as well. The |
| 775 | only major facility not implemented so far is support for must-alias |
| 776 | information.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 777 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 778 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 779 | |
| 780 | |
| 781 | <!-- ======================================================================= --> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 782 | <div class="doc_subsection"> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 783 | <a name="aliasanalysis-xforms">Alias analysis driven transformations</a> |
| 784 | </div> |
| 785 | |
| 786 | <div class="doc_text"> |
| 787 | LLVM includes several alias-analysis driven transformations which can be used |
| 788 | with any of the implementations above. |
| 789 | </div> |
| 790 | |
| 791 | <!-- _______________________________________________________________________ --> |
| 792 | <div class="doc_subsubsection"> |
| 793 | <a name="adce">The <tt>-adce</tt> pass</a> |
| 794 | </div> |
| 795 | |
| 796 | <div class="doc_text"> |
| 797 | |
| 798 | <p>The <tt>-adce</tt> pass, which implements Aggressive Dead Code Elimination |
| 799 | uses the <tt>AliasAnalysis</tt> interface to delete calls to functions that do |
| 800 | not have side-effects and are not used.</p> |
| 801 | |
| 802 | </div> |
| 803 | |
| 804 | |
| 805 | <!-- _______________________________________________________________________ --> |
| 806 | <div class="doc_subsubsection"> |
| 807 | <a name="licm">The <tt>-licm</tt> pass</a> |
| 808 | </div> |
| 809 | |
| 810 | <div class="doc_text"> |
| 811 | |
| 812 | <p>The <tt>-licm</tt> pass implements various Loop Invariant Code Motion related |
| 813 | transformations. It uses the <tt>AliasAnalysis</tt> interface for several |
| 814 | different transformations:</p> |
| 815 | |
| 816 | <ul> |
| 817 | <li>It uses mod/ref information to hoist or sink load instructions out of loops |
| 818 | if there are no instructions in the loop that modifies the memory loaded.</li> |
| 819 | |
| 820 | <li>It uses mod/ref information to hoist function calls out of loops that do not |
| 821 | write to memory and are loop-invariant.</li> |
| 822 | |
| 823 | <li>If uses alias information to promote memory objects that are loaded and |
| 824 | stored to in loops to live in a register instead. It can do this if there are |
| 825 | no may aliases to the loaded/stored memory location.</li> |
| 826 | </ul> |
| 827 | |
| 828 | </div> |
| 829 | |
| 830 | <!-- _______________________________________________________________________ --> |
| 831 | <div class="doc_subsubsection"> |
| 832 | <a name="argpromotion">The <tt>-argpromotion</tt> pass</a> |
| 833 | </div> |
| 834 | |
| 835 | <div class="doc_text"> |
| 836 | <p> |
| 837 | The <tt>-argpromotion</tt> pass promotes by-reference arguments to be passed in |
| 838 | by-value instead. In particular, if pointer arguments are only loaded from it |
| 839 | passes in the value loaded instead of the address to the function. This pass |
| 840 | uses alias information to make sure that the value loaded from the argument |
| 841 | pointer is not modified between the entry of the function and any load of the |
| 842 | pointer.</p> |
| 843 | </div> |
| 844 | |
| 845 | <!-- _______________________________________________________________________ --> |
| 846 | <div class="doc_subsubsection"> |
| 847 | <a name="gcseloadvn">The <tt>-load-vn</tt> & <tt>-gcse</tt> passes</a> |
| 848 | </div> |
| 849 | |
| 850 | <div class="doc_text"> |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame] | 851 | |
| 852 | <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] | 853 | number</a>" loads and pointers values, which is used by the GCSE pass to |
| 854 | eliminate instructions. The <tt>-load-vn</tt> pass relies on alias information |
| 855 | and must-alias information. This combination of passes can make the following |
| 856 | transformations:</p> |
| 857 | |
| 858 | <ul> |
| 859 | <li>Redundant load instructions are eliminated.</li> |
| 860 | <li>Load instructions that follow a store to the same location are replaced with |
| 861 | the stored value ("store forwarding").</li> |
| 862 | <li>Pointers values (e.g. formal arguments) that must-alias simpler expressions |
| 863 | (e.g. global variables or the null pointer) are replaced. Note that this |
| 864 | implements transformations like "virtual method resolution", turning indirect |
| 865 | calls into direct calls.</li> |
| 866 | </ul> |
| 867 | |
| 868 | </div> |
| 869 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 870 | <!-- ======================================================================= --> |
| 871 | <div class="doc_subsection"> |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame] | 872 | <a name="aliasanalysis-debug">Clients for debugging and evaluation of |
| 873 | implementations</a> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 874 | </div> |
| 875 | |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame] | 876 | <div class="doc_text"> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 877 | |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame] | 878 | <p>These passes are useful for evaluating the various alias analysis |
| 879 | implementations. You can use them with commands like '<tt>opt -anders-aa -ds-aa |
| 880 | -aa-eval foo.bc -disable-output -stats</tt>'.</p> |
| 881 | |
| 882 | </div> |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 883 | |
| 884 | <!-- _______________________________________________________________________ --> |
| 885 | <div class="doc_subsubsection"> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 886 | <a name="print-alias-sets">The <tt>-print-alias-sets</tt> pass</a> |
| 887 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 888 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 889 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 890 | |
| 891 | <p>The <tt>-print-alias-sets</tt> pass is exposed as part of the |
Chris Lattner | 05d5c9d | 2006-01-03 06:04:48 +0000 | [diff] [blame] | 892 | <tt>opt</tt> tool to print out the Alias Sets formed by the <a |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 893 | href="#ast"><tt>AliasSetTracker</tt></a> class. This is useful if you're using |
Chris Lattner | 05d5c9d | 2006-01-03 06:04:48 +0000 | [diff] [blame] | 894 | the <tt>AliasSetTracker</tt> class. To use it, use something like:</p> |
| 895 | |
| 896 | <div class="doc_code"> |
| 897 | <pre> |
| 898 | % opt -ds-aa -print-alias-sets -disable-output |
| 899 | </pre> |
| 900 | </div> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 901 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 902 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 903 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 904 | |
| 905 | <!-- _______________________________________________________________________ --> |
| 906 | <div class="doc_subsubsection"> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 907 | <a name="count-aa">The <tt>-count-aa</tt> pass</a> |
| 908 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 909 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 910 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 911 | |
| 912 | <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] | 913 | pass is making and what responses are returned by the alias analysis. As an |
| 914 | example,</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 915 | |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame] | 916 | <div class="doc_code"> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 917 | <pre> |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame] | 918 | % opt -basicaa -count-aa -ds-aa -count-aa -licm |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 919 | </pre> |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame] | 920 | </div> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 921 | |
Misha Brukman | 294611a | 2004-07-28 22:18:33 +0000 | [diff] [blame] | 922 | <p>will print out how many queries (and what responses are returned) by the |
| 923 | <tt>-licm</tt> pass (of the <tt>-ds-aa</tt> pass) and how many queries are made |
| 924 | of the <tt>-basicaa</tt> pass by the <tt>-ds-aa</tt> pass. This can be useful |
| 925 | when debugging a transformation or an alias analysis implementation.</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 926 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 927 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 928 | |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 929 | <!-- _______________________________________________________________________ --> |
| 930 | <div class="doc_subsubsection"> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 931 | <a name="aa-eval">The <tt>-aa-eval</tt> pass</a> |
| 932 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 933 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 934 | <div class="doc_text"> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 935 | |
| 936 | <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] | 937 | function and asks an alias analysis whether or not the pointers alias. This |
| 938 | gives an indication of the precision of the alias analysis. Statistics are |
Chris Lattner | ccc8065 | 2004-05-23 21:04:01 +0000 | [diff] [blame] | 939 | printed indicating the percent of no/may/must aliases found (a more precise |
| 940 | algorithm will have a lower number of may aliases).</p> |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 941 | |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 942 | </div> |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 943 | |
Chris Lattner | 9f64875 | 2003-03-04 19:37:49 +0000 | [diff] [blame] | 944 | <!-- *********************************************************************** --> |
| 945 | |
Misha Brukman | 3896be2 | 2003-10-24 18:06:11 +0000 | [diff] [blame] | 946 | <hr> |
Misha Brukman | 915cab2 | 2003-11-22 01:26:21 +0000 | [diff] [blame] | 947 | <address> |
Misha Brukman | 38847d5 | 2003-12-21 22:53:21 +0000 | [diff] [blame] | 948 | <a href="http://jigsaw.w3.org/css-validator/check/referer"><img |
Misha Brukman | 5feba4e | 2003-11-22 01:07:30 +0000 | [diff] [blame] | 949 | 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] | 950 | <a href="http://validator.w3.org/check/referer"><img |
Misha Brukman | f6acb51 | 2004-05-12 18:02:00 +0000 | [diff] [blame] | 951 | 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] | 952 | |
| 953 | <a href="mailto:sabre@nondot.org">Chris Lattner</a><br> |
Reid Spencer | 05fe4b0 | 2006-03-14 05:39:39 +0000 | [diff] [blame^] | 954 | <a href="http://llvm.org">LLVM Compiler Infrastructure</a><br> |
Misha Brukman | 915cab2 | 2003-11-22 01:26:21 +0000 | [diff] [blame] | 955 | Last modified: $Date$ |
| 956 | </address> |
Misha Brukman | cd11e45 | 2003-10-22 23:27:16 +0000 | [diff] [blame] | 957 | |
| 958 | </body> |
| 959 | </html> |