blob: 8b8106b950a0a5f1f939ce7c152bc1bfa373b8a3 [file] [log] [blame]
Chris Lattner7d58f8d2002-08-22 18:25:32 +00001//===- AliasAnalysis.cpp - Generic Alias Analysis Interface Implementation -==//
Misha Brukman01808ca2005-04-21 21:13:18 +00002//
John Criswell482202a2003-10-20 19:43:21 +00003// The LLVM Compiler Infrastructure
4//
Chris Lattnerf3ebc3f2007-12-29 20:36:04 +00005// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
Misha Brukman01808ca2005-04-21 21:13:18 +00007//
John Criswell482202a2003-10-20 19:43:21 +00008//===----------------------------------------------------------------------===//
Chris Lattner7d58f8d2002-08-22 18:25:32 +00009//
10// This file implements the generic AliasAnalysis interface which is used as the
11// common interface used by all clients and implementations of alias analysis.
12//
13// This file also implements the default version of the AliasAnalysis interface
14// that is to be used when no other implementation is specified. This does some
15// simple tests that detect obvious cases: two different global pointers cannot
16// alias, a global cannot alias a malloc, two different mallocs cannot alias,
17// etc.
18//
19// This alias analysis implementation really isn't very good for anything, but
20// it is very fast, and makes a nice clean default implementation. Because it
21// handles lots of little corner cases, other, more complex, alias analysis
22// implementations may choose to rely on this pass to resolve these simple and
23// easy cases.
24//
25//===----------------------------------------------------------------------===//
26
Chris Lattnerd6a2a992003-02-26 19:41:54 +000027#include "llvm/Analysis/AliasAnalysis.h"
Nick Lewycky0b682452013-07-27 01:24:00 +000028#include "llvm/Analysis/CFG.h"
Chandler Carruth8a8cd2b2014-01-07 11:48:04 +000029#include "llvm/Analysis/CaptureTracking.h"
Chad Rosiera968caf2012-05-14 20:35:04 +000030#include "llvm/Analysis/ValueTracking.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000031#include "llvm/IR/BasicBlock.h"
32#include "llvm/IR/DataLayout.h"
Chandler Carruth5ad5f152014-01-13 09:26:24 +000033#include "llvm/IR/Dominators.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000034#include "llvm/IR/Function.h"
35#include "llvm/IR/Instructions.h"
36#include "llvm/IR/IntrinsicInst.h"
37#include "llvm/IR/LLVMContext.h"
38#include "llvm/IR/Type.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000039#include "llvm/Pass.h"
Benjamin Kramer8bcc9712012-08-29 15:32:21 +000040#include "llvm/Target/TargetLibraryInfo.h"
Chris Lattnera67dbd02004-03-15 04:07:29 +000041using namespace llvm;
Brian Gaeke960707c2003-11-11 22:41:34 +000042
Chris Lattner7d58f8d2002-08-22 18:25:32 +000043// Register the AliasAnalysis interface, providing a nice name to refer to.
Owen Anderson6c18d1a2010-10-19 17:21:58 +000044INITIALIZE_ANALYSIS_GROUP(AliasAnalysis, "Alias Analysis", NoAA)
Devang Patel8c78a0b2007-05-03 01:11:54 +000045char AliasAnalysis::ID = 0;
Chris Lattner7d58f8d2002-08-22 18:25:32 +000046
Chris Lattner62c37002004-05-23 21:15:48 +000047//===----------------------------------------------------------------------===//
48// Default chaining methods
49//===----------------------------------------------------------------------===//
50
51AliasAnalysis::AliasResult
Dan Gohman41f14cf2010-09-14 21:25:10 +000052AliasAnalysis::alias(const Location &LocA, const Location &LocB) {
Chris Lattner62c37002004-05-23 21:15:48 +000053 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
Dan Gohman41f14cf2010-09-14 21:25:10 +000054 return AA->alias(LocA, LocB);
Chris Lattner62c37002004-05-23 21:15:48 +000055}
56
Dan Gohman9130bad2010-11-08 16:45:26 +000057bool AliasAnalysis::pointsToConstantMemory(const Location &Loc,
58 bool OrLocal) {
Chris Lattner62c37002004-05-23 21:15:48 +000059 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
Dan Gohman9130bad2010-11-08 16:45:26 +000060 return AA->pointsToConstantMemory(Loc, OrLocal);
Chris Lattner62c37002004-05-23 21:15:48 +000061}
62
Hal Finkel354e23b2014-07-17 01:28:25 +000063AliasAnalysis::Location
64AliasAnalysis::getArgLocation(ImmutableCallSite CS, unsigned ArgIdx,
65 AliasAnalysis::ModRefResult &Mask) {
66 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
67 return AA->getArgLocation(CS, ArgIdx, Mask);
68}
69
Chris Lattner62c37002004-05-23 21:15:48 +000070void AliasAnalysis::deleteValue(Value *V) {
71 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
72 AA->deleteValue(V);
73}
74
75void AliasAnalysis::copyValue(Value *From, Value *To) {
76 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
77 AA->copyValue(From, To);
78}
79
Owen Andersonb6e4ff02011-01-03 21:38:41 +000080void AliasAnalysis::addEscapingUse(Use &U) {
81 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
82 AA->addEscapingUse(U);
83}
84
85
Chris Lattner62c37002004-05-23 21:15:48 +000086AliasAnalysis::ModRefResult
Dan Gohman5f1702e2010-08-06 01:25:49 +000087AliasAnalysis::getModRefInfo(ImmutableCallSite CS,
Dan Gohman41f14cf2010-09-14 21:25:10 +000088 const Location &Loc) {
Dan Gohman1033ce62010-10-25 16:28:57 +000089 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
Dan Gohman5f1702e2010-08-06 01:25:49 +000090
91 ModRefBehavior MRB = getModRefBehavior(CS);
92 if (MRB == DoesNotAccessMemory)
93 return NoModRef;
94
95 ModRefResult Mask = ModRef;
Dan Gohman5d06f892010-11-09 20:06:55 +000096 if (onlyReadsMemory(MRB))
Dan Gohman5f1702e2010-08-06 01:25:49 +000097 Mask = Ref;
Dan Gohman5d06f892010-11-09 20:06:55 +000098
Dan Gohman066c1bb2010-11-10 18:17:28 +000099 if (onlyAccessesArgPointees(MRB)) {
Dan Gohman5f1702e2010-08-06 01:25:49 +0000100 bool doesAlias = false;
Hal Finkel354e23b2014-07-17 01:28:25 +0000101 ModRefResult AllArgsMask = NoModRef;
Dan Gohman39b3a1e2011-04-27 18:39:03 +0000102 if (doesAccessArgPointees(MRB)) {
Dan Gohman066c1bb2010-11-10 18:17:28 +0000103 for (ImmutableCallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end();
Dan Gohman39b3a1e2011-04-27 18:39:03 +0000104 AI != AE; ++AI) {
105 const Value *Arg = *AI;
106 if (!Arg->getType()->isPointerTy())
107 continue;
Hal Finkel354e23b2014-07-17 01:28:25 +0000108 ModRefResult ArgMask;
109 Location CSLoc =
110 getArgLocation(CS, (unsigned) std::distance(CS.arg_begin(), AI),
111 ArgMask);
Dan Gohman39b3a1e2011-04-27 18:39:03 +0000112 if (!isNoAlias(CSLoc, Loc)) {
Dan Gohman066c1bb2010-11-10 18:17:28 +0000113 doesAlias = true;
Hal Finkel354e23b2014-07-17 01:28:25 +0000114 AllArgsMask = ModRefResult(AllArgsMask | ArgMask);
Dan Gohman066c1bb2010-11-10 18:17:28 +0000115 }
Dan Gohman39b3a1e2011-04-27 18:39:03 +0000116 }
117 }
Dan Gohman5f1702e2010-08-06 01:25:49 +0000118 if (!doesAlias)
119 return NoModRef;
Hal Finkel354e23b2014-07-17 01:28:25 +0000120 Mask = ModRefResult(Mask & AllArgsMask);
Dan Gohman5f1702e2010-08-06 01:25:49 +0000121 }
122
Dan Gohman41f14cf2010-09-14 21:25:10 +0000123 // If Loc is a constant memory location, the call definitely could not
Dan Gohman5f1702e2010-08-06 01:25:49 +0000124 // modify the memory location.
Dan Gohman41f14cf2010-09-14 21:25:10 +0000125 if ((Mask & Mod) && pointsToConstantMemory(Loc))
Dan Gohman5f1702e2010-08-06 01:25:49 +0000126 Mask = ModRefResult(Mask & ~Mod);
127
Dan Gohmanabaf2d82010-10-25 16:29:52 +0000128 // If this is the end of the chain, don't forward.
Dan Gohman5f1702e2010-08-06 01:25:49 +0000129 if (!AA) return Mask;
130
131 // Otherwise, fall back to the next AA in the chain. But we can merge
132 // in any mask we've managed to compute.
Dan Gohman41f14cf2010-09-14 21:25:10 +0000133 return ModRefResult(AA->getModRefInfo(CS, Loc) & Mask);
Dan Gohman5f1702e2010-08-06 01:25:49 +0000134}
135
136AliasAnalysis::ModRefResult
Dan Gohman5442c712010-08-03 21:48:53 +0000137AliasAnalysis::getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2) {
Dan Gohman1033ce62010-10-25 16:28:57 +0000138 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
Dan Gohman5f1702e2010-08-06 01:25:49 +0000139
140 // If CS1 or CS2 are readnone, they don't interact.
141 ModRefBehavior CS1B = getModRefBehavior(CS1);
142 if (CS1B == DoesNotAccessMemory) return NoModRef;
143
144 ModRefBehavior CS2B = getModRefBehavior(CS2);
145 if (CS2B == DoesNotAccessMemory) return NoModRef;
146
147 // If they both only read from memory, there is no dependence.
Dan Gohman5d06f892010-11-09 20:06:55 +0000148 if (onlyReadsMemory(CS1B) && onlyReadsMemory(CS2B))
Dan Gohman5f1702e2010-08-06 01:25:49 +0000149 return NoModRef;
150
151 AliasAnalysis::ModRefResult Mask = ModRef;
152
153 // If CS1 only reads memory, the only dependence on CS2 can be
154 // from CS1 reading memory written by CS2.
Dan Gohman5d06f892010-11-09 20:06:55 +0000155 if (onlyReadsMemory(CS1B))
Dan Gohman5f1702e2010-08-06 01:25:49 +0000156 Mask = ModRefResult(Mask & Ref);
157
158 // If CS2 only access memory through arguments, accumulate the mod/ref
159 // information from CS1's references to the memory referenced by
160 // CS2's arguments.
Dan Gohman066c1bb2010-11-10 18:17:28 +0000161 if (onlyAccessesArgPointees(CS2B)) {
Dan Gohman5f1702e2010-08-06 01:25:49 +0000162 AliasAnalysis::ModRefResult R = NoModRef;
Dan Gohman39b3a1e2011-04-27 18:39:03 +0000163 if (doesAccessArgPointees(CS2B)) {
Dan Gohman066c1bb2010-11-10 18:17:28 +0000164 for (ImmutableCallSite::arg_iterator
165 I = CS2.arg_begin(), E = CS2.arg_end(); I != E; ++I) {
Dan Gohman39b3a1e2011-04-27 18:39:03 +0000166 const Value *Arg = *I;
167 if (!Arg->getType()->isPointerTy())
168 continue;
Hal Finkel354e23b2014-07-17 01:28:25 +0000169 ModRefResult ArgMask;
170 Location CS2Loc =
171 getArgLocation(CS2, (unsigned) std::distance(CS2.arg_begin(), I),
172 ArgMask);
173 // ArgMask indicates what CS2 might do to CS2Loc, and the dependence of
174 // CS1 on that location is the inverse.
175 if (ArgMask == Mod)
176 ArgMask = ModRef;
177 else if (ArgMask == Ref)
178 ArgMask = Mod;
179
180 R = ModRefResult((R | (getModRefInfo(CS1, CS2Loc) & ArgMask)) & Mask);
Dan Gohman066c1bb2010-11-10 18:17:28 +0000181 if (R == Mask)
182 break;
183 }
Dan Gohman39b3a1e2011-04-27 18:39:03 +0000184 }
Dan Gohman5f1702e2010-08-06 01:25:49 +0000185 return R;
186 }
187
188 // If CS1 only accesses memory through arguments, check if CS2 references
189 // any of the memory referenced by CS1's arguments. If not, return NoModRef.
Dan Gohman066c1bb2010-11-10 18:17:28 +0000190 if (onlyAccessesArgPointees(CS1B)) {
Dan Gohman5f1702e2010-08-06 01:25:49 +0000191 AliasAnalysis::ModRefResult R = NoModRef;
Dan Gohman39b3a1e2011-04-27 18:39:03 +0000192 if (doesAccessArgPointees(CS1B)) {
Dan Gohman066c1bb2010-11-10 18:17:28 +0000193 for (ImmutableCallSite::arg_iterator
Dan Gohman39b3a1e2011-04-27 18:39:03 +0000194 I = CS1.arg_begin(), E = CS1.arg_end(); I != E; ++I) {
195 const Value *Arg = *I;
196 if (!Arg->getType()->isPointerTy())
197 continue;
Hal Finkel354e23b2014-07-17 01:28:25 +0000198 ModRefResult ArgMask;
199 Location CS1Loc =
200 getArgLocation(CS1, (unsigned) std::distance(CS1.arg_begin(), I),
201 ArgMask);
202 // ArgMask indicates what CS1 might do to CS1Loc; if CS1 might Mod
203 // CS1Loc, then we care about either a Mod or a Ref by CS2. If CS1
204 // might Ref, then we care only about a Mod by CS2.
205 ModRefResult ArgR = getModRefInfo(CS2, CS1Loc);
206 if (((ArgMask & Mod) != NoModRef && (ArgR & ModRef) != NoModRef) ||
207 ((ArgMask & Ref) != NoModRef && (ArgR & Mod) != NoModRef))
208 R = ModRefResult((R | ArgMask) & Mask);
209
210 if (R == Mask)
Dan Gohman066c1bb2010-11-10 18:17:28 +0000211 break;
Dan Gohman39b3a1e2011-04-27 18:39:03 +0000212 }
213 }
Hal Finkel354e23b2014-07-17 01:28:25 +0000214 return R;
Dan Gohman5f1702e2010-08-06 01:25:49 +0000215 }
216
Dan Gohmanabaf2d82010-10-25 16:29:52 +0000217 // If this is the end of the chain, don't forward.
Dan Gohman5f1702e2010-08-06 01:25:49 +0000218 if (!AA) return Mask;
219
220 // Otherwise, fall back to the next AA in the chain. But we can merge
221 // in any mask we've managed to compute.
222 return ModRefResult(AA->getModRefInfo(CS1, CS2) & Mask);
223}
224
225AliasAnalysis::ModRefBehavior
226AliasAnalysis::getModRefBehavior(ImmutableCallSite CS) {
Dan Gohman1033ce62010-10-25 16:28:57 +0000227 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
Dan Gohman5f1702e2010-08-06 01:25:49 +0000228
229 ModRefBehavior Min = UnknownModRefBehavior;
230
231 // Call back into the alias analysis with the other form of getModRefBehavior
232 // to see if it can give a better response.
233 if (const Function *F = CS.getCalledFunction())
234 Min = getModRefBehavior(F);
235
Dan Gohmanabaf2d82010-10-25 16:29:52 +0000236 // If this is the end of the chain, don't forward.
Dan Gohman5f1702e2010-08-06 01:25:49 +0000237 if (!AA) return Min;
238
239 // Otherwise, fall back to the next AA in the chain. But we can merge
240 // in any result we've managed to compute.
Dan Gohman2694e142010-11-10 01:02:18 +0000241 return ModRefBehavior(AA->getModRefBehavior(CS) & Min);
Dan Gohman5f1702e2010-08-06 01:25:49 +0000242}
243
244AliasAnalysis::ModRefBehavior
245AliasAnalysis::getModRefBehavior(const Function *F) {
Chris Lattner62c37002004-05-23 21:15:48 +0000246 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
Dan Gohman5f1702e2010-08-06 01:25:49 +0000247 return AA->getModRefBehavior(F);
Chris Lattner62c37002004-05-23 21:15:48 +0000248}
249
Chris Lattner62c37002004-05-23 21:15:48 +0000250//===----------------------------------------------------------------------===//
251// AliasAnalysis non-virtual helper method implementation
252//===----------------------------------------------------------------------===//
253
Dan Gohman65316d62010-11-11 21:50:19 +0000254AliasAnalysis::Location AliasAnalysis::getLocation(const LoadInst *LI) {
255 return Location(LI->getPointerOperand(),
256 getTypeStoreSize(LI->getType()),
257 LI->getMetadata(LLVMContext::MD_tbaa));
258}
259
260AliasAnalysis::Location AliasAnalysis::getLocation(const StoreInst *SI) {
261 return Location(SI->getPointerOperand(),
262 getTypeStoreSize(SI->getValueOperand()->getType()),
263 SI->getMetadata(LLVMContext::MD_tbaa));
264}
265
266AliasAnalysis::Location AliasAnalysis::getLocation(const VAArgInst *VI) {
267 return Location(VI->getPointerOperand(),
268 UnknownSize,
269 VI->getMetadata(LLVMContext::MD_tbaa));
270}
271
Eli Friedman5c918912011-09-26 20:15:28 +0000272AliasAnalysis::Location
273AliasAnalysis::getLocation(const AtomicCmpXchgInst *CXI) {
274 return Location(CXI->getPointerOperand(),
275 getTypeStoreSize(CXI->getCompareOperand()->getType()),
276 CXI->getMetadata(LLVMContext::MD_tbaa));
277}
278
279AliasAnalysis::Location
280AliasAnalysis::getLocation(const AtomicRMWInst *RMWI) {
281 return Location(RMWI->getPointerOperand(),
282 getTypeStoreSize(RMWI->getValOperand()->getType()),
283 RMWI->getMetadata(LLVMContext::MD_tbaa));
284}
Chris Lattner663ba912010-11-21 07:51:27 +0000285
286AliasAnalysis::Location
287AliasAnalysis::getLocationForSource(const MemTransferInst *MTI) {
288 uint64_t Size = UnknownSize;
289 if (ConstantInt *C = dyn_cast<ConstantInt>(MTI->getLength()))
290 Size = C->getValue().getZExtValue();
291
Dan Gohmane1a17a32010-12-16 02:51:19 +0000292 // memcpy/memmove can have TBAA tags. For memcpy, they apply
293 // to both the source and the destination.
294 MDNode *TBAATag = MTI->getMetadata(LLVMContext::MD_tbaa);
295
296 return Location(MTI->getRawSource(), Size, TBAATag);
Chris Lattner663ba912010-11-21 07:51:27 +0000297}
298
299AliasAnalysis::Location
Chris Lattnerafbc0c22010-11-30 01:48:20 +0000300AliasAnalysis::getLocationForDest(const MemIntrinsic *MTI) {
Chris Lattner663ba912010-11-21 07:51:27 +0000301 uint64_t Size = UnknownSize;
302 if (ConstantInt *C = dyn_cast<ConstantInt>(MTI->getLength()))
303 Size = C->getValue().getZExtValue();
Dan Gohmane1a17a32010-12-16 02:51:19 +0000304
305 // memcpy/memmove can have TBAA tags. For memcpy, they apply
306 // to both the source and the destination.
307 MDNode *TBAATag = MTI->getMetadata(LLVMContext::MD_tbaa);
Chris Lattner663ba912010-11-21 07:51:27 +0000308
Dan Gohmane1a17a32010-12-16 02:51:19 +0000309 return Location(MTI->getRawDest(), Size, TBAATag);
Chris Lattner663ba912010-11-21 07:51:27 +0000310}
311
312
313
Chris Lattner3a311832003-02-26 19:26:51 +0000314AliasAnalysis::ModRefResult
Dan Gohman41f14cf2010-09-14 21:25:10 +0000315AliasAnalysis::getModRefInfo(const LoadInst *L, const Location &Loc) {
Eli Friedman5494ada2011-08-15 20:54:19 +0000316 // Be conservative in the face of volatile/atomic.
317 if (!L->isUnordered())
Dan Gohman6b4671b2010-08-06 18:11:28 +0000318 return ModRef;
319
Dan Gohman52f9d7d2010-08-03 17:27:43 +0000320 // If the load address doesn't alias the given address, it doesn't read
321 // or write the specified memory.
Dan Gohman65316d62010-11-11 21:50:19 +0000322 if (!alias(getLocation(L), Loc))
Dan Gohman52f9d7d2010-08-03 17:27:43 +0000323 return NoModRef;
324
Dan Gohman52f9d7d2010-08-03 17:27:43 +0000325 // Otherwise, a load just reads.
326 return Ref;
Chris Lattner7d58f8d2002-08-22 18:25:32 +0000327}
328
Chris Lattner3a311832003-02-26 19:26:51 +0000329AliasAnalysis::ModRefResult
Dan Gohman41f14cf2010-09-14 21:25:10 +0000330AliasAnalysis::getModRefInfo(const StoreInst *S, const Location &Loc) {
Eli Friedman5494ada2011-08-15 20:54:19 +0000331 // Be conservative in the face of volatile/atomic.
332 if (!S->isUnordered())
Dan Gohman6b4671b2010-08-06 18:11:28 +0000333 return ModRef;
334
Dan Gohman23976df2010-08-06 18:10:45 +0000335 // If the store address cannot alias the pointer in question, then the
336 // specified memory cannot be modified by the store.
Dan Gohman65316d62010-11-11 21:50:19 +0000337 if (!alias(getLocation(S), Loc))
Chris Lattner96055762004-01-30 22:16:42 +0000338 return NoModRef;
339
340 // If the pointer is a pointer to constant memory, then it could not have been
341 // modified by this store.
Dan Gohman41f14cf2010-09-14 21:25:10 +0000342 if (pointsToConstantMemory(Loc))
Dan Gohman52f9d7d2010-08-03 17:27:43 +0000343 return NoModRef;
344
345 // Otherwise, a store just writes.
346 return Mod;
Chris Lattner3a311832003-02-26 19:26:51 +0000347}
348
Dan Gohmane68958f2010-08-06 18:24:38 +0000349AliasAnalysis::ModRefResult
Dan Gohman41f14cf2010-09-14 21:25:10 +0000350AliasAnalysis::getModRefInfo(const VAArgInst *V, const Location &Loc) {
Dan Gohmane68958f2010-08-06 18:24:38 +0000351 // If the va_arg address cannot alias the pointer in question, then the
352 // specified memory cannot be accessed by the va_arg.
Dan Gohman65316d62010-11-11 21:50:19 +0000353 if (!alias(getLocation(V), Loc))
Dan Gohmane68958f2010-08-06 18:24:38 +0000354 return NoModRef;
355
356 // If the pointer is a pointer to constant memory, then it could not have been
357 // modified by this va_arg.
Dan Gohman41f14cf2010-09-14 21:25:10 +0000358 if (pointsToConstantMemory(Loc))
Dan Gohmane68958f2010-08-06 18:24:38 +0000359 return NoModRef;
360
361 // Otherwise, a va_arg reads and writes.
362 return ModRef;
363}
364
Eli Friedman5c918912011-09-26 20:15:28 +0000365AliasAnalysis::ModRefResult
366AliasAnalysis::getModRefInfo(const AtomicCmpXchgInst *CX, const Location &Loc) {
367 // Acquire/Release cmpxchg has properties that matter for arbitrary addresses.
Tim Northovere94a5182014-03-11 10:48:52 +0000368 if (CX->getSuccessOrdering() > Monotonic)
Eli Friedman5c918912011-09-26 20:15:28 +0000369 return ModRef;
370
371 // If the cmpxchg address does not alias the location, it does not access it.
372 if (!alias(getLocation(CX), Loc))
373 return NoModRef;
374
375 return ModRef;
376}
377
378AliasAnalysis::ModRefResult
379AliasAnalysis::getModRefInfo(const AtomicRMWInst *RMW, const Location &Loc) {
380 // Acquire/Release atomicrmw has properties that matter for arbitrary addresses.
381 if (RMW->getOrdering() > Monotonic)
382 return ModRef;
383
384 // If the atomicrmw address does not alias the location, it does not access it.
385 if (!alias(getLocation(RMW), Loc))
386 return NoModRef;
387
388 return ModRef;
389}
390
Chad Rosiera968caf2012-05-14 20:35:04 +0000391// FIXME: this is really just shoring-up a deficiency in alias analysis.
392// BasicAA isn't willing to spend linear time determining whether an alloca
393// was captured before or after this particular call, while we are. However,
394// with a smarter AA in place, this test is just wasting compile time.
395AliasAnalysis::ModRefResult
396AliasAnalysis::callCapturesBefore(const Instruction *I,
397 const AliasAnalysis::Location &MemLoc,
398 DominatorTree *DT) {
Rafael Espindola7c68beb2014-02-18 15:33:12 +0000399 if (!DT || !DL) return AliasAnalysis::ModRef;
Chad Rosiera968caf2012-05-14 20:35:04 +0000400
Rafael Espindola7c68beb2014-02-18 15:33:12 +0000401 const Value *Object = GetUnderlyingObject(MemLoc.Ptr, DL);
Chad Rosiera968caf2012-05-14 20:35:04 +0000402 if (!isIdentifiedObject(Object) || isa<GlobalValue>(Object) ||
403 isa<Constant>(Object))
404 return AliasAnalysis::ModRef;
405
406 ImmutableCallSite CS(I);
407 if (!CS.getInstruction() || CS.getInstruction() == Object)
408 return AliasAnalysis::ModRef;
409
Hal Finkelb0356212014-07-21 13:15:48 +0000410 if (llvm::PointerMayBeCapturedBefore(Object, /* ReturnCaptures */ true,
Hal Finkeld32803b2014-07-21 21:30:22 +0000411 /* StoreCaptures */ true, I, DT,
412 /* include Object */ true))
Chad Rosiera968caf2012-05-14 20:35:04 +0000413 return AliasAnalysis::ModRef;
414
415 unsigned ArgNo = 0;
Nick Lewyckyc0514622013-07-07 10:15:16 +0000416 AliasAnalysis::ModRefResult R = AliasAnalysis::NoModRef;
Chad Rosiera968caf2012-05-14 20:35:04 +0000417 for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
418 CI != CE; ++CI, ++ArgNo) {
419 // Only look at the no-capture or byval pointer arguments. If this
420 // pointer were passed to arguments that were neither of these, then it
421 // couldn't be no-capture.
422 if (!(*CI)->getType()->isPointerTy() ||
423 (!CS.doesNotCapture(ArgNo) && !CS.isByValArgument(ArgNo)))
424 continue;
425
426 // If this is a no-capture pointer argument, see if we can tell that it
427 // is impossible to alias the pointer we're checking. If not, we have to
428 // assume that the call could touch the pointer, even though it doesn't
429 // escape.
Nick Lewyckyc0514622013-07-07 10:15:16 +0000430 if (isNoAlias(AliasAnalysis::Location(*CI),
431 AliasAnalysis::Location(Object)))
432 continue;
433 if (CS.doesNotAccessMemory(ArgNo))
434 continue;
435 if (CS.onlyReadsMemory(ArgNo)) {
436 R = AliasAnalysis::Ref;
437 continue;
Chad Rosiera968caf2012-05-14 20:35:04 +0000438 }
Nick Lewyckyc0514622013-07-07 10:15:16 +0000439 return AliasAnalysis::ModRef;
Chad Rosiera968caf2012-05-14 20:35:04 +0000440 }
Nick Lewyckyc0514622013-07-07 10:15:16 +0000441 return R;
Chad Rosiera968caf2012-05-14 20:35:04 +0000442}
Eli Friedman5c918912011-09-26 20:15:28 +0000443
Chris Lattner7d58f8d2002-08-22 18:25:32 +0000444// AliasAnalysis destructor: DO NOT move this to the header file for
445// AliasAnalysis or else clients of the AliasAnalysis class may not depend on
446// the AliasAnalysis.o file in the current .a file, causing alias analysis
447// support to not be included in the tool correctly!
448//
449AliasAnalysis::~AliasAnalysis() {}
450
Dan Gohman7a68b662008-05-30 00:02:02 +0000451/// InitializeAliasAnalysis - Subclasses must call this method to initialize the
Chris Lattner3a311832003-02-26 19:26:51 +0000452/// AliasAnalysis interface before any other methods are called.
453///
454void AliasAnalysis::InitializeAliasAnalysis(Pass *P) {
Rafael Espindola93512512014-02-25 17:30:31 +0000455 DataLayoutPass *DLP = P->getAnalysisIfAvailable<DataLayoutPass>();
Craig Topper9f008862014-04-15 04:59:12 +0000456 DL = DLP ? &DLP->getDataLayout() : nullptr;
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000457 TLI = P->getAnalysisIfAvailable<TargetLibraryInfo>();
Chris Lattner62c37002004-05-23 21:15:48 +0000458 AA = &P->getAnalysis<AliasAnalysis>();
Chris Lattner3a311832003-02-26 19:26:51 +0000459}
460
461// getAnalysisUsage - All alias analysis implementations should invoke this
Dan Gohman43d19d62009-07-25 00:48:42 +0000462// directly (using AliasAnalysis::getAnalysisUsage(AU)).
Chris Lattner3a311832003-02-26 19:26:51 +0000463void AliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
Chris Lattner62c37002004-05-23 21:15:48 +0000464 AU.addRequired<AliasAnalysis>(); // All AA's chain
Chris Lattner3a311832003-02-26 19:26:51 +0000465}
466
Micah Villmowcdfe20b2012-10-08 16:38:25 +0000467/// getTypeStoreSize - Return the DataLayout store size for the given type,
Dan Gohman43d19d62009-07-25 00:48:42 +0000468/// if known, or a conservative value otherwise.
469///
Chris Lattner229907c2011-07-18 04:54:35 +0000470uint64_t AliasAnalysis::getTypeStoreSize(Type *Ty) {
Rafael Espindola7c68beb2014-02-18 15:33:12 +0000471 return DL ? DL->getTypeStoreSize(Ty) : UnknownSize;
Dan Gohman43d19d62009-07-25 00:48:42 +0000472}
473
Chris Lattnerd922a842002-08-22 22:46:39 +0000474/// canBasicBlockModify - Return true if it is possible for execution of the
475/// specified basic block to modify the value pointed to by Ptr.
476///
Chris Lattner3a311832003-02-26 19:26:51 +0000477bool AliasAnalysis::canBasicBlockModify(const BasicBlock &BB,
Dan Gohman41f14cf2010-09-14 21:25:10 +0000478 const Location &Loc) {
479 return canInstructionRangeModify(BB.front(), BB.back(), Loc);
Chris Lattner7d58f8d2002-08-22 18:25:32 +0000480}
481
Chris Lattnerd922a842002-08-22 22:46:39 +0000482/// canInstructionRangeModify - Return true if it is possible for the execution
483/// of the specified instructions to modify the value pointed to by Ptr. The
484/// instructions to consider are all of the instructions in the range of [I1,I2]
485/// INCLUSIVE. I1 and I2 must be in the same basic block.
486///
Chris Lattner7d58f8d2002-08-22 18:25:32 +0000487bool AliasAnalysis::canInstructionRangeModify(const Instruction &I1,
488 const Instruction &I2,
Dan Gohman41f14cf2010-09-14 21:25:10 +0000489 const Location &Loc) {
Chris Lattner7d58f8d2002-08-22 18:25:32 +0000490 assert(I1.getParent() == I2.getParent() &&
491 "Instructions not in same basic block!");
Dan Gohman5442c712010-08-03 21:48:53 +0000492 BasicBlock::const_iterator I = &I1;
493 BasicBlock::const_iterator E = &I2;
Chris Lattner7d58f8d2002-08-22 18:25:32 +0000494 ++E; // Convert from inclusive to exclusive range.
495
Chris Lattner3a311832003-02-26 19:26:51 +0000496 for (; I != E; ++I) // Check every instruction in range
Dan Gohman41f14cf2010-09-14 21:25:10 +0000497 if (getModRefInfo(I, Loc) & Mod)
Chris Lattner7d58f8d2002-08-22 18:25:32 +0000498 return true;
Chris Lattner7d58f8d2002-08-22 18:25:32 +0000499 return false;
500}
501
Dan Gohmanfb306c02009-02-03 01:28:32 +0000502/// isNoAliasCall - Return true if this pointer is returned by a noalias
503/// function.
504bool llvm::isNoAliasCall(const Value *V) {
505 if (isa<CallInst>(V) || isa<InvokeInst>(V))
Dan Gohman5442c712010-08-03 21:48:53 +0000506 return ImmutableCallSite(cast<Instruction>(V))
Bill Wendling3d7b0b82012-12-19 07:18:57 +0000507 .paramHasAttr(0, Attribute::NoAlias);
Dan Gohmanfb306c02009-02-03 01:28:32 +0000508 return false;
509}
510
Michael Kupersteinf3e663a2013-05-28 08:17:48 +0000511/// isNoAliasArgument - Return true if this is an argument with the noalias
512/// attribute.
513bool llvm::isNoAliasArgument(const Value *V)
514{
515 if (const Argument *A = dyn_cast<Argument>(V))
516 return A->hasNoAliasAttr();
517 return false;
518}
519
Dan Gohmanfb306c02009-02-03 01:28:32 +0000520/// isIdentifiedObject - Return true if this pointer refers to a distinct and
521/// identifiable object. This returns true for:
Dan Gohman1f59f012009-08-27 17:52:56 +0000522/// Global Variables and Functions (but not Global Aliases)
Dan Gohmanfb306c02009-02-03 01:28:32 +0000523/// Allocas and Mallocs
Dan Gohman00ef9322010-07-07 14:27:09 +0000524/// ByVal and NoAlias Arguments
525/// NoAlias returns
Dan Gohmanfb306c02009-02-03 01:28:32 +0000526///
Dan Gohman00ef9322010-07-07 14:27:09 +0000527bool llvm::isIdentifiedObject(const Value *V) {
Dan Gohman0824aff2010-06-29 00:50:39 +0000528 if (isa<AllocaInst>(V))
Dan Gohman1f59f012009-08-27 17:52:56 +0000529 return true;
530 if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V))
Dan Gohmanfb306c02009-02-03 01:28:32 +0000531 return true;
Dan Gohman00ef9322010-07-07 14:27:09 +0000532 if (isNoAliasCall(V))
533 return true;
534 if (const Argument *A = dyn_cast<Argument>(V))
535 return A->hasNoAliasAttr() || A->hasByValAttr();
Dan Gohmanfb306c02009-02-03 01:28:32 +0000536 return false;
537}
Hal Finkelc782aa52014-07-21 12:27:23 +0000538
539/// isIdentifiedFunctionLocal - Return true if V is umabigously identified
540/// at the function-level. Different IdentifiedFunctionLocals can't alias.
541/// Further, an IdentifiedFunctionLocal can not alias with any function
542/// arguments other than itself, which is not necessarily true for
543/// IdentifiedObjects.
544bool llvm::isIdentifiedFunctionLocal(const Value *V)
545{
546 return isa<AllocaInst>(V) || isNoAliasCall(V) || isNoAliasArgument(V);
547}
548