blob: 9583bbe5e342f939b8ead4c5dbd1dec8870ac324 [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
Chris Lattner62c37002004-05-23 21:15:48 +000063void AliasAnalysis::deleteValue(Value *V) {
64 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
65 AA->deleteValue(V);
66}
67
68void AliasAnalysis::copyValue(Value *From, Value *To) {
69 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
70 AA->copyValue(From, To);
71}
72
Owen Andersonb6e4ff02011-01-03 21:38:41 +000073void AliasAnalysis::addEscapingUse(Use &U) {
74 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
75 AA->addEscapingUse(U);
76}
77
78
Chris Lattner62c37002004-05-23 21:15:48 +000079AliasAnalysis::ModRefResult
Dan Gohman5f1702e2010-08-06 01:25:49 +000080AliasAnalysis::getModRefInfo(ImmutableCallSite CS,
Dan Gohman41f14cf2010-09-14 21:25:10 +000081 const Location &Loc) {
Dan Gohman1033ce62010-10-25 16:28:57 +000082 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
Dan Gohman5f1702e2010-08-06 01:25:49 +000083
84 ModRefBehavior MRB = getModRefBehavior(CS);
85 if (MRB == DoesNotAccessMemory)
86 return NoModRef;
87
88 ModRefResult Mask = ModRef;
Dan Gohman5d06f892010-11-09 20:06:55 +000089 if (onlyReadsMemory(MRB))
Dan Gohman5f1702e2010-08-06 01:25:49 +000090 Mask = Ref;
Dan Gohman5d06f892010-11-09 20:06:55 +000091
Dan Gohman066c1bb2010-11-10 18:17:28 +000092 if (onlyAccessesArgPointees(MRB)) {
Dan Gohman5f1702e2010-08-06 01:25:49 +000093 bool doesAlias = false;
Dan Gohman39b3a1e2011-04-27 18:39:03 +000094 if (doesAccessArgPointees(MRB)) {
95 MDNode *CSTag = CS.getInstruction()->getMetadata(LLVMContext::MD_tbaa);
Dan Gohman066c1bb2010-11-10 18:17:28 +000096 for (ImmutableCallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end();
Dan Gohman39b3a1e2011-04-27 18:39:03 +000097 AI != AE; ++AI) {
98 const Value *Arg = *AI;
99 if (!Arg->getType()->isPointerTy())
100 continue;
101 Location CSLoc(Arg, UnknownSize, CSTag);
102 if (!isNoAlias(CSLoc, Loc)) {
Dan Gohman066c1bb2010-11-10 18:17:28 +0000103 doesAlias = true;
104 break;
105 }
Dan Gohman39b3a1e2011-04-27 18:39:03 +0000106 }
107 }
Dan Gohman5f1702e2010-08-06 01:25:49 +0000108 if (!doesAlias)
109 return NoModRef;
110 }
111
Dan Gohman41f14cf2010-09-14 21:25:10 +0000112 // If Loc is a constant memory location, the call definitely could not
Dan Gohman5f1702e2010-08-06 01:25:49 +0000113 // modify the memory location.
Dan Gohman41f14cf2010-09-14 21:25:10 +0000114 if ((Mask & Mod) && pointsToConstantMemory(Loc))
Dan Gohman5f1702e2010-08-06 01:25:49 +0000115 Mask = ModRefResult(Mask & ~Mod);
116
Dan Gohmanabaf2d82010-10-25 16:29:52 +0000117 // If this is the end of the chain, don't forward.
Dan Gohman5f1702e2010-08-06 01:25:49 +0000118 if (!AA) return Mask;
119
120 // Otherwise, fall back to the next AA in the chain. But we can merge
121 // in any mask we've managed to compute.
Dan Gohman41f14cf2010-09-14 21:25:10 +0000122 return ModRefResult(AA->getModRefInfo(CS, Loc) & Mask);
Dan Gohman5f1702e2010-08-06 01:25:49 +0000123}
124
125AliasAnalysis::ModRefResult
Dan Gohman5442c712010-08-03 21:48:53 +0000126AliasAnalysis::getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2) {
Dan Gohman1033ce62010-10-25 16:28:57 +0000127 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
Dan Gohman5f1702e2010-08-06 01:25:49 +0000128
129 // If CS1 or CS2 are readnone, they don't interact.
130 ModRefBehavior CS1B = getModRefBehavior(CS1);
131 if (CS1B == DoesNotAccessMemory) return NoModRef;
132
133 ModRefBehavior CS2B = getModRefBehavior(CS2);
134 if (CS2B == DoesNotAccessMemory) return NoModRef;
135
136 // If they both only read from memory, there is no dependence.
Dan Gohman5d06f892010-11-09 20:06:55 +0000137 if (onlyReadsMemory(CS1B) && onlyReadsMemory(CS2B))
Dan Gohman5f1702e2010-08-06 01:25:49 +0000138 return NoModRef;
139
140 AliasAnalysis::ModRefResult Mask = ModRef;
141
142 // If CS1 only reads memory, the only dependence on CS2 can be
143 // from CS1 reading memory written by CS2.
Dan Gohman5d06f892010-11-09 20:06:55 +0000144 if (onlyReadsMemory(CS1B))
Dan Gohman5f1702e2010-08-06 01:25:49 +0000145 Mask = ModRefResult(Mask & Ref);
146
147 // If CS2 only access memory through arguments, accumulate the mod/ref
148 // information from CS1's references to the memory referenced by
149 // CS2's arguments.
Dan Gohman066c1bb2010-11-10 18:17:28 +0000150 if (onlyAccessesArgPointees(CS2B)) {
Dan Gohman5f1702e2010-08-06 01:25:49 +0000151 AliasAnalysis::ModRefResult R = NoModRef;
Dan Gohman39b3a1e2011-04-27 18:39:03 +0000152 if (doesAccessArgPointees(CS2B)) {
153 MDNode *CS2Tag = CS2.getInstruction()->getMetadata(LLVMContext::MD_tbaa);
Dan Gohman066c1bb2010-11-10 18:17:28 +0000154 for (ImmutableCallSite::arg_iterator
155 I = CS2.arg_begin(), E = CS2.arg_end(); I != E; ++I) {
Dan Gohman39b3a1e2011-04-27 18:39:03 +0000156 const Value *Arg = *I;
157 if (!Arg->getType()->isPointerTy())
158 continue;
159 Location CS2Loc(Arg, UnknownSize, CS2Tag);
160 R = ModRefResult((R | getModRefInfo(CS1, CS2Loc)) & Mask);
Dan Gohman066c1bb2010-11-10 18:17:28 +0000161 if (R == Mask)
162 break;
163 }
Dan Gohman39b3a1e2011-04-27 18:39:03 +0000164 }
Dan Gohman5f1702e2010-08-06 01:25:49 +0000165 return R;
166 }
167
168 // If CS1 only accesses memory through arguments, check if CS2 references
169 // any of the memory referenced by CS1's arguments. If not, return NoModRef.
Dan Gohman066c1bb2010-11-10 18:17:28 +0000170 if (onlyAccessesArgPointees(CS1B)) {
Dan Gohman5f1702e2010-08-06 01:25:49 +0000171 AliasAnalysis::ModRefResult R = NoModRef;
Dan Gohman39b3a1e2011-04-27 18:39:03 +0000172 if (doesAccessArgPointees(CS1B)) {
173 MDNode *CS1Tag = CS1.getInstruction()->getMetadata(LLVMContext::MD_tbaa);
Dan Gohman066c1bb2010-11-10 18:17:28 +0000174 for (ImmutableCallSite::arg_iterator
Dan Gohman39b3a1e2011-04-27 18:39:03 +0000175 I = CS1.arg_begin(), E = CS1.arg_end(); I != E; ++I) {
176 const Value *Arg = *I;
177 if (!Arg->getType()->isPointerTy())
178 continue;
179 Location CS1Loc(Arg, UnknownSize, CS1Tag);
180 if (getModRefInfo(CS2, CS1Loc) != NoModRef) {
Dan Gohman066c1bb2010-11-10 18:17:28 +0000181 R = Mask;
182 break;
183 }
Dan Gohman39b3a1e2011-04-27 18:39:03 +0000184 }
185 }
Dan Gohman5f1702e2010-08-06 01:25:49 +0000186 if (R == NoModRef)
187 return R;
188 }
189
Dan Gohmanabaf2d82010-10-25 16:29:52 +0000190 // If this is the end of the chain, don't forward.
Dan Gohman5f1702e2010-08-06 01:25:49 +0000191 if (!AA) return Mask;
192
193 // Otherwise, fall back to the next AA in the chain. But we can merge
194 // in any mask we've managed to compute.
195 return ModRefResult(AA->getModRefInfo(CS1, CS2) & Mask);
196}
197
198AliasAnalysis::ModRefBehavior
199AliasAnalysis::getModRefBehavior(ImmutableCallSite CS) {
Dan Gohman1033ce62010-10-25 16:28:57 +0000200 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
Dan Gohman5f1702e2010-08-06 01:25:49 +0000201
202 ModRefBehavior Min = UnknownModRefBehavior;
203
204 // Call back into the alias analysis with the other form of getModRefBehavior
205 // to see if it can give a better response.
206 if (const Function *F = CS.getCalledFunction())
207 Min = getModRefBehavior(F);
208
Dan Gohmanabaf2d82010-10-25 16:29:52 +0000209 // If this is the end of the chain, don't forward.
Dan Gohman5f1702e2010-08-06 01:25:49 +0000210 if (!AA) return Min;
211
212 // Otherwise, fall back to the next AA in the chain. But we can merge
213 // in any result we've managed to compute.
Dan Gohman2694e142010-11-10 01:02:18 +0000214 return ModRefBehavior(AA->getModRefBehavior(CS) & Min);
Dan Gohman5f1702e2010-08-06 01:25:49 +0000215}
216
217AliasAnalysis::ModRefBehavior
218AliasAnalysis::getModRefBehavior(const Function *F) {
Chris Lattner62c37002004-05-23 21:15:48 +0000219 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
Dan Gohman5f1702e2010-08-06 01:25:49 +0000220 return AA->getModRefBehavior(F);
Chris Lattner62c37002004-05-23 21:15:48 +0000221}
222
Chris Lattner62c37002004-05-23 21:15:48 +0000223//===----------------------------------------------------------------------===//
224// AliasAnalysis non-virtual helper method implementation
225//===----------------------------------------------------------------------===//
226
Dan Gohman65316d62010-11-11 21:50:19 +0000227AliasAnalysis::Location AliasAnalysis::getLocation(const LoadInst *LI) {
228 return Location(LI->getPointerOperand(),
229 getTypeStoreSize(LI->getType()),
230 LI->getMetadata(LLVMContext::MD_tbaa));
231}
232
233AliasAnalysis::Location AliasAnalysis::getLocation(const StoreInst *SI) {
234 return Location(SI->getPointerOperand(),
235 getTypeStoreSize(SI->getValueOperand()->getType()),
236 SI->getMetadata(LLVMContext::MD_tbaa));
237}
238
239AliasAnalysis::Location AliasAnalysis::getLocation(const VAArgInst *VI) {
240 return Location(VI->getPointerOperand(),
241 UnknownSize,
242 VI->getMetadata(LLVMContext::MD_tbaa));
243}
244
Eli Friedman5c918912011-09-26 20:15:28 +0000245AliasAnalysis::Location
246AliasAnalysis::getLocation(const AtomicCmpXchgInst *CXI) {
247 return Location(CXI->getPointerOperand(),
248 getTypeStoreSize(CXI->getCompareOperand()->getType()),
249 CXI->getMetadata(LLVMContext::MD_tbaa));
250}
251
252AliasAnalysis::Location
253AliasAnalysis::getLocation(const AtomicRMWInst *RMWI) {
254 return Location(RMWI->getPointerOperand(),
255 getTypeStoreSize(RMWI->getValOperand()->getType()),
256 RMWI->getMetadata(LLVMContext::MD_tbaa));
257}
Chris Lattner663ba912010-11-21 07:51:27 +0000258
259AliasAnalysis::Location
260AliasAnalysis::getLocationForSource(const MemTransferInst *MTI) {
261 uint64_t Size = UnknownSize;
262 if (ConstantInt *C = dyn_cast<ConstantInt>(MTI->getLength()))
263 Size = C->getValue().getZExtValue();
264
Dan Gohmane1a17a32010-12-16 02:51:19 +0000265 // memcpy/memmove can have TBAA tags. For memcpy, they apply
266 // to both the source and the destination.
267 MDNode *TBAATag = MTI->getMetadata(LLVMContext::MD_tbaa);
268
269 return Location(MTI->getRawSource(), Size, TBAATag);
Chris Lattner663ba912010-11-21 07:51:27 +0000270}
271
272AliasAnalysis::Location
Chris Lattnerafbc0c22010-11-30 01:48:20 +0000273AliasAnalysis::getLocationForDest(const MemIntrinsic *MTI) {
Chris Lattner663ba912010-11-21 07:51:27 +0000274 uint64_t Size = UnknownSize;
275 if (ConstantInt *C = dyn_cast<ConstantInt>(MTI->getLength()))
276 Size = C->getValue().getZExtValue();
Dan Gohmane1a17a32010-12-16 02:51:19 +0000277
278 // memcpy/memmove can have TBAA tags. For memcpy, they apply
279 // to both the source and the destination.
280 MDNode *TBAATag = MTI->getMetadata(LLVMContext::MD_tbaa);
Chris Lattner663ba912010-11-21 07:51:27 +0000281
Dan Gohmane1a17a32010-12-16 02:51:19 +0000282 return Location(MTI->getRawDest(), Size, TBAATag);
Chris Lattner663ba912010-11-21 07:51:27 +0000283}
284
285
286
Chris Lattner3a311832003-02-26 19:26:51 +0000287AliasAnalysis::ModRefResult
Dan Gohman41f14cf2010-09-14 21:25:10 +0000288AliasAnalysis::getModRefInfo(const LoadInst *L, const Location &Loc) {
Eli Friedman5494ada2011-08-15 20:54:19 +0000289 // Be conservative in the face of volatile/atomic.
290 if (!L->isUnordered())
Dan Gohman6b4671b2010-08-06 18:11:28 +0000291 return ModRef;
292
Dan Gohman52f9d7d2010-08-03 17:27:43 +0000293 // If the load address doesn't alias the given address, it doesn't read
294 // or write the specified memory.
Dan Gohman65316d62010-11-11 21:50:19 +0000295 if (!alias(getLocation(L), Loc))
Dan Gohman52f9d7d2010-08-03 17:27:43 +0000296 return NoModRef;
297
Dan Gohman52f9d7d2010-08-03 17:27:43 +0000298 // Otherwise, a load just reads.
299 return Ref;
Chris Lattner7d58f8d2002-08-22 18:25:32 +0000300}
301
Chris Lattner3a311832003-02-26 19:26:51 +0000302AliasAnalysis::ModRefResult
Dan Gohman41f14cf2010-09-14 21:25:10 +0000303AliasAnalysis::getModRefInfo(const StoreInst *S, const Location &Loc) {
Eli Friedman5494ada2011-08-15 20:54:19 +0000304 // Be conservative in the face of volatile/atomic.
305 if (!S->isUnordered())
Dan Gohman6b4671b2010-08-06 18:11:28 +0000306 return ModRef;
307
Dan Gohman23976df2010-08-06 18:10:45 +0000308 // If the store address cannot alias the pointer in question, then the
309 // specified memory cannot be modified by the store.
Dan Gohman65316d62010-11-11 21:50:19 +0000310 if (!alias(getLocation(S), Loc))
Chris Lattner96055762004-01-30 22:16:42 +0000311 return NoModRef;
312
313 // If the pointer is a pointer to constant memory, then it could not have been
314 // modified by this store.
Dan Gohman41f14cf2010-09-14 21:25:10 +0000315 if (pointsToConstantMemory(Loc))
Dan Gohman52f9d7d2010-08-03 17:27:43 +0000316 return NoModRef;
317
318 // Otherwise, a store just writes.
319 return Mod;
Chris Lattner3a311832003-02-26 19:26:51 +0000320}
321
Dan Gohmane68958f2010-08-06 18:24:38 +0000322AliasAnalysis::ModRefResult
Dan Gohman41f14cf2010-09-14 21:25:10 +0000323AliasAnalysis::getModRefInfo(const VAArgInst *V, const Location &Loc) {
Dan Gohmane68958f2010-08-06 18:24:38 +0000324 // If the va_arg address cannot alias the pointer in question, then the
325 // specified memory cannot be accessed by the va_arg.
Dan Gohman65316d62010-11-11 21:50:19 +0000326 if (!alias(getLocation(V), Loc))
Dan Gohmane68958f2010-08-06 18:24:38 +0000327 return NoModRef;
328
329 // If the pointer is a pointer to constant memory, then it could not have been
330 // modified by this va_arg.
Dan Gohman41f14cf2010-09-14 21:25:10 +0000331 if (pointsToConstantMemory(Loc))
Dan Gohmane68958f2010-08-06 18:24:38 +0000332 return NoModRef;
333
334 // Otherwise, a va_arg reads and writes.
335 return ModRef;
336}
337
Eli Friedman5c918912011-09-26 20:15:28 +0000338AliasAnalysis::ModRefResult
339AliasAnalysis::getModRefInfo(const AtomicCmpXchgInst *CX, const Location &Loc) {
340 // Acquire/Release cmpxchg has properties that matter for arbitrary addresses.
Tim Northovere94a5182014-03-11 10:48:52 +0000341 if (CX->getSuccessOrdering() > Monotonic)
Eli Friedman5c918912011-09-26 20:15:28 +0000342 return ModRef;
343
344 // If the cmpxchg address does not alias the location, it does not access it.
345 if (!alias(getLocation(CX), Loc))
346 return NoModRef;
347
348 return ModRef;
349}
350
351AliasAnalysis::ModRefResult
352AliasAnalysis::getModRefInfo(const AtomicRMWInst *RMW, const Location &Loc) {
353 // Acquire/Release atomicrmw has properties that matter for arbitrary addresses.
354 if (RMW->getOrdering() > Monotonic)
355 return ModRef;
356
357 // If the atomicrmw address does not alias the location, it does not access it.
358 if (!alias(getLocation(RMW), Loc))
359 return NoModRef;
360
361 return ModRef;
362}
363
Chad Rosiera968caf2012-05-14 20:35:04 +0000364namespace {
365 /// Only find pointer captures which happen before the given instruction. Uses
366 /// the dominator tree to determine whether one instruction is before another.
Manman Renfe5a61e2013-01-04 19:19:47 +0000367 /// Only support the case where the Value is defined in the same basic block
368 /// as the given instruction and the use.
Chad Rosiera968caf2012-05-14 20:35:04 +0000369 struct CapturesBefore : public CaptureTracker {
370 CapturesBefore(const Instruction *I, DominatorTree *DT)
371 : BeforeHere(I), DT(DT), Captured(false) {}
372
Craig Toppere9ba7592014-03-05 07:30:04 +0000373 void tooManyUses() override { Captured = true; }
Chad Rosiera968caf2012-05-14 20:35:04 +0000374
Chandler Carruth64e9aa52014-03-05 10:21:48 +0000375 bool shouldExplore(const Use *U) override {
Chad Rosiera968caf2012-05-14 20:35:04 +0000376 Instruction *I = cast<Instruction>(U->getUser());
377 BasicBlock *BB = I->getParent();
Manman Renfe5a61e2013-01-04 19:19:47 +0000378 // We explore this usage only if the usage can reach "BeforeHere".
379 // If use is not reachable from entry, there is no need to explore.
380 if (BeforeHere != I && !DT->isReachableFromEntry(BB))
381 return false;
382 // If the value is defined in the same basic block as use and BeforeHere,
383 // there is no need to explore the use if BeforeHere dominates use.
384 // Check whether there is a path from I to BeforeHere.
385 if (BeforeHere != I && DT->dominates(BeforeHere, I) &&
Nick Lewycky0b682452013-07-27 01:24:00 +0000386 !isPotentiallyReachable(I, BeforeHere, DT))
Chad Rosiera968caf2012-05-14 20:35:04 +0000387 return false;
388 return true;
389 }
390
Chandler Carruth64e9aa52014-03-05 10:21:48 +0000391 bool captured(const Use *U) override {
Chad Rosiera968caf2012-05-14 20:35:04 +0000392 Instruction *I = cast<Instruction>(U->getUser());
393 BasicBlock *BB = I->getParent();
Manman Renfe5a61e2013-01-04 19:19:47 +0000394 // Same logic as in shouldExplore.
395 if (BeforeHere != I && !DT->isReachableFromEntry(BB))
396 return false;
397 if (BeforeHere != I && DT->dominates(BeforeHere, I) &&
Nick Lewycky0b682452013-07-27 01:24:00 +0000398 !isPotentiallyReachable(I, BeforeHere, DT))
Chad Rosiera968caf2012-05-14 20:35:04 +0000399 return false;
400 Captured = true;
401 return true;
402 }
403
404 const Instruction *BeforeHere;
405 DominatorTree *DT;
406
407 bool Captured;
408 };
409}
410
411// FIXME: this is really just shoring-up a deficiency in alias analysis.
412// BasicAA isn't willing to spend linear time determining whether an alloca
413// was captured before or after this particular call, while we are. However,
414// with a smarter AA in place, this test is just wasting compile time.
415AliasAnalysis::ModRefResult
416AliasAnalysis::callCapturesBefore(const Instruction *I,
417 const AliasAnalysis::Location &MemLoc,
418 DominatorTree *DT) {
Rafael Espindola7c68beb2014-02-18 15:33:12 +0000419 if (!DT || !DL) return AliasAnalysis::ModRef;
Chad Rosiera968caf2012-05-14 20:35:04 +0000420
Rafael Espindola7c68beb2014-02-18 15:33:12 +0000421 const Value *Object = GetUnderlyingObject(MemLoc.Ptr, DL);
Chad Rosiera968caf2012-05-14 20:35:04 +0000422 if (!isIdentifiedObject(Object) || isa<GlobalValue>(Object) ||
423 isa<Constant>(Object))
424 return AliasAnalysis::ModRef;
425
426 ImmutableCallSite CS(I);
427 if (!CS.getInstruction() || CS.getInstruction() == Object)
428 return AliasAnalysis::ModRef;
429
430 CapturesBefore CB(I, DT);
431 llvm::PointerMayBeCaptured(Object, &CB);
432 if (CB.Captured)
433 return AliasAnalysis::ModRef;
434
435 unsigned ArgNo = 0;
Nick Lewyckyc0514622013-07-07 10:15:16 +0000436 AliasAnalysis::ModRefResult R = AliasAnalysis::NoModRef;
Chad Rosiera968caf2012-05-14 20:35:04 +0000437 for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
438 CI != CE; ++CI, ++ArgNo) {
439 // Only look at the no-capture or byval pointer arguments. If this
440 // pointer were passed to arguments that were neither of these, then it
441 // couldn't be no-capture.
442 if (!(*CI)->getType()->isPointerTy() ||
443 (!CS.doesNotCapture(ArgNo) && !CS.isByValArgument(ArgNo)))
444 continue;
445
446 // If this is a no-capture pointer argument, see if we can tell that it
447 // is impossible to alias the pointer we're checking. If not, we have to
448 // assume that the call could touch the pointer, even though it doesn't
449 // escape.
Nick Lewyckyc0514622013-07-07 10:15:16 +0000450 if (isNoAlias(AliasAnalysis::Location(*CI),
451 AliasAnalysis::Location(Object)))
452 continue;
453 if (CS.doesNotAccessMemory(ArgNo))
454 continue;
455 if (CS.onlyReadsMemory(ArgNo)) {
456 R = AliasAnalysis::Ref;
457 continue;
Chad Rosiera968caf2012-05-14 20:35:04 +0000458 }
Nick Lewyckyc0514622013-07-07 10:15:16 +0000459 return AliasAnalysis::ModRef;
Chad Rosiera968caf2012-05-14 20:35:04 +0000460 }
Nick Lewyckyc0514622013-07-07 10:15:16 +0000461 return R;
Chad Rosiera968caf2012-05-14 20:35:04 +0000462}
Eli Friedman5c918912011-09-26 20:15:28 +0000463
Chris Lattner7d58f8d2002-08-22 18:25:32 +0000464// AliasAnalysis destructor: DO NOT move this to the header file for
465// AliasAnalysis or else clients of the AliasAnalysis class may not depend on
466// the AliasAnalysis.o file in the current .a file, causing alias analysis
467// support to not be included in the tool correctly!
468//
469AliasAnalysis::~AliasAnalysis() {}
470
Dan Gohman7a68b662008-05-30 00:02:02 +0000471/// InitializeAliasAnalysis - Subclasses must call this method to initialize the
Chris Lattner3a311832003-02-26 19:26:51 +0000472/// AliasAnalysis interface before any other methods are called.
473///
474void AliasAnalysis::InitializeAliasAnalysis(Pass *P) {
Rafael Espindola93512512014-02-25 17:30:31 +0000475 DataLayoutPass *DLP = P->getAnalysisIfAvailable<DataLayoutPass>();
476 DL = DLP ? &DLP->getDataLayout() : 0;
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000477 TLI = P->getAnalysisIfAvailable<TargetLibraryInfo>();
Chris Lattner62c37002004-05-23 21:15:48 +0000478 AA = &P->getAnalysis<AliasAnalysis>();
Chris Lattner3a311832003-02-26 19:26:51 +0000479}
480
481// getAnalysisUsage - All alias analysis implementations should invoke this
Dan Gohman43d19d62009-07-25 00:48:42 +0000482// directly (using AliasAnalysis::getAnalysisUsage(AU)).
Chris Lattner3a311832003-02-26 19:26:51 +0000483void AliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
Chris Lattner62c37002004-05-23 21:15:48 +0000484 AU.addRequired<AliasAnalysis>(); // All AA's chain
Chris Lattner3a311832003-02-26 19:26:51 +0000485}
486
Micah Villmowcdfe20b2012-10-08 16:38:25 +0000487/// getTypeStoreSize - Return the DataLayout store size for the given type,
Dan Gohman43d19d62009-07-25 00:48:42 +0000488/// if known, or a conservative value otherwise.
489///
Chris Lattner229907c2011-07-18 04:54:35 +0000490uint64_t AliasAnalysis::getTypeStoreSize(Type *Ty) {
Rafael Espindola7c68beb2014-02-18 15:33:12 +0000491 return DL ? DL->getTypeStoreSize(Ty) : UnknownSize;
Dan Gohman43d19d62009-07-25 00:48:42 +0000492}
493
Chris Lattnerd922a842002-08-22 22:46:39 +0000494/// canBasicBlockModify - Return true if it is possible for execution of the
495/// specified basic block to modify the value pointed to by Ptr.
496///
Chris Lattner3a311832003-02-26 19:26:51 +0000497bool AliasAnalysis::canBasicBlockModify(const BasicBlock &BB,
Dan Gohman41f14cf2010-09-14 21:25:10 +0000498 const Location &Loc) {
499 return canInstructionRangeModify(BB.front(), BB.back(), Loc);
Chris Lattner7d58f8d2002-08-22 18:25:32 +0000500}
501
Chris Lattnerd922a842002-08-22 22:46:39 +0000502/// canInstructionRangeModify - Return true if it is possible for the execution
503/// of the specified instructions to modify the value pointed to by Ptr. The
504/// instructions to consider are all of the instructions in the range of [I1,I2]
505/// INCLUSIVE. I1 and I2 must be in the same basic block.
506///
Chris Lattner7d58f8d2002-08-22 18:25:32 +0000507bool AliasAnalysis::canInstructionRangeModify(const Instruction &I1,
508 const Instruction &I2,
Dan Gohman41f14cf2010-09-14 21:25:10 +0000509 const Location &Loc) {
Chris Lattner7d58f8d2002-08-22 18:25:32 +0000510 assert(I1.getParent() == I2.getParent() &&
511 "Instructions not in same basic block!");
Dan Gohman5442c712010-08-03 21:48:53 +0000512 BasicBlock::const_iterator I = &I1;
513 BasicBlock::const_iterator E = &I2;
Chris Lattner7d58f8d2002-08-22 18:25:32 +0000514 ++E; // Convert from inclusive to exclusive range.
515
Chris Lattner3a311832003-02-26 19:26:51 +0000516 for (; I != E; ++I) // Check every instruction in range
Dan Gohman41f14cf2010-09-14 21:25:10 +0000517 if (getModRefInfo(I, Loc) & Mod)
Chris Lattner7d58f8d2002-08-22 18:25:32 +0000518 return true;
Chris Lattner7d58f8d2002-08-22 18:25:32 +0000519 return false;
520}
521
Dan Gohmanfb306c02009-02-03 01:28:32 +0000522/// isNoAliasCall - Return true if this pointer is returned by a noalias
523/// function.
524bool llvm::isNoAliasCall(const Value *V) {
525 if (isa<CallInst>(V) || isa<InvokeInst>(V))
Dan Gohman5442c712010-08-03 21:48:53 +0000526 return ImmutableCallSite(cast<Instruction>(V))
Bill Wendling3d7b0b82012-12-19 07:18:57 +0000527 .paramHasAttr(0, Attribute::NoAlias);
Dan Gohmanfb306c02009-02-03 01:28:32 +0000528 return false;
529}
530
Michael Kupersteinf3e663a2013-05-28 08:17:48 +0000531/// isNoAliasArgument - Return true if this is an argument with the noalias
532/// attribute.
533bool llvm::isNoAliasArgument(const Value *V)
534{
535 if (const Argument *A = dyn_cast<Argument>(V))
536 return A->hasNoAliasAttr();
537 return false;
538}
539
Dan Gohmanfb306c02009-02-03 01:28:32 +0000540/// isIdentifiedObject - Return true if this pointer refers to a distinct and
541/// identifiable object. This returns true for:
Dan Gohman1f59f012009-08-27 17:52:56 +0000542/// Global Variables and Functions (but not Global Aliases)
Dan Gohmanfb306c02009-02-03 01:28:32 +0000543/// Allocas and Mallocs
Dan Gohman00ef9322010-07-07 14:27:09 +0000544/// ByVal and NoAlias Arguments
545/// NoAlias returns
Dan Gohmanfb306c02009-02-03 01:28:32 +0000546///
Dan Gohman00ef9322010-07-07 14:27:09 +0000547bool llvm::isIdentifiedObject(const Value *V) {
Dan Gohman0824aff2010-06-29 00:50:39 +0000548 if (isa<AllocaInst>(V))
Dan Gohman1f59f012009-08-27 17:52:56 +0000549 return true;
550 if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V))
Dan Gohmanfb306c02009-02-03 01:28:32 +0000551 return true;
Dan Gohman00ef9322010-07-07 14:27:09 +0000552 if (isNoAliasCall(V))
553 return true;
554 if (const Argument *A = dyn_cast<Argument>(V))
555 return A->hasNoAliasAttr() || A->hasByValAttr();
Dan Gohmanfb306c02009-02-03 01:28:32 +0000556 return false;
557}