1//===- AliasAnalysis.cpp - Generic Alias Analysis Interface Implementation -==//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
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
27#include "llvm/Analysis/AliasAnalysis.h"
28#include "llvm/Analysis/CFG.h"
29#include "llvm/Analysis/CaptureTracking.h"
30#include "llvm/Analysis/ValueTracking.h"
31#include "llvm/IR/BasicBlock.h"
32#include "llvm/IR/DataLayout.h"
33#include "llvm/IR/Dominators.h"
34#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"
39#include "llvm/Pass.h"
40#include "llvm/Target/TargetLibraryInfo.h"
41using namespace llvm;
42
43// Register the AliasAnalysis interface, providing a nice name to refer to.
44INITIALIZE_ANALYSIS_GROUP(AliasAnalysis, "Alias Analysis", NoAA)
45char AliasAnalysis::ID = 0;
46
47//===----------------------------------------------------------------------===//
48// Default chaining methods
49//===----------------------------------------------------------------------===//
50
51AliasAnalysis::AliasResult
52AliasAnalysis::alias(const Location &LocA, const Location &LocB) {
53  assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
54  return AA->alias(LocA, LocB);
55}
56
57bool AliasAnalysis::pointsToConstantMemory(const Location &Loc,
58                                           bool OrLocal) {
59  assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
60  return AA->pointsToConstantMemory(Loc, OrLocal);
61}
62
63AliasAnalysis::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
70void 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
80void AliasAnalysis::addEscapingUse(Use &U) {
81  assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
82  AA->addEscapingUse(U);
83}
84
85
86AliasAnalysis::ModRefResult
87AliasAnalysis::getModRefInfo(ImmutableCallSite CS,
88                             const Location &Loc) {
89  assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
90
91  ModRefBehavior MRB = getModRefBehavior(CS);
92  if (MRB == DoesNotAccessMemory)
93    return NoModRef;
94
95  ModRefResult Mask = ModRef;
96  if (onlyReadsMemory(MRB))
97    Mask = Ref;
98
99  if (onlyAccessesArgPointees(MRB)) {
100    bool doesAlias = false;
101    ModRefResult AllArgsMask = NoModRef;
102    if (doesAccessArgPointees(MRB)) {
103      for (ImmutableCallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end();
104           AI != AE; ++AI) {
105        const Value *Arg = *AI;
106        if (!Arg->getType()->isPointerTy())
107          continue;
108        ModRefResult ArgMask;
109        Location CSLoc =
110          getArgLocation(CS, (unsigned) std::distance(CS.arg_begin(), AI),
111                         ArgMask);
112        if (!isNoAlias(CSLoc, Loc)) {
113          doesAlias = true;
114          AllArgsMask = ModRefResult(AllArgsMask | ArgMask);
115        }
116      }
117    }
118    if (!doesAlias)
119      return NoModRef;
120    Mask = ModRefResult(Mask & AllArgsMask);
121  }
122
123  // If Loc is a constant memory location, the call definitely could not
124  // modify the memory location.
125  if ((Mask & Mod) && pointsToConstantMemory(Loc))
126    Mask = ModRefResult(Mask & ~Mod);
127
128  // If this is the end of the chain, don't forward.
129  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.
133  return ModRefResult(AA->getModRefInfo(CS, Loc) & Mask);
134}
135
136AliasAnalysis::ModRefResult
137AliasAnalysis::getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2) {
138  assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
139
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.
148  if (onlyReadsMemory(CS1B) && onlyReadsMemory(CS2B))
149    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.
155  if (onlyReadsMemory(CS1B))
156    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.
161  if (onlyAccessesArgPointees(CS2B)) {
162    AliasAnalysis::ModRefResult R = NoModRef;
163    if (doesAccessArgPointees(CS2B)) {
164      for (ImmutableCallSite::arg_iterator
165           I = CS2.arg_begin(), E = CS2.arg_end(); I != E; ++I) {
166        const Value *Arg = *I;
167        if (!Arg->getType()->isPointerTy())
168          continue;
169        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);
181        if (R == Mask)
182          break;
183      }
184    }
185    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.
190  if (onlyAccessesArgPointees(CS1B)) {
191    AliasAnalysis::ModRefResult R = NoModRef;
192    if (doesAccessArgPointees(CS1B)) {
193      for (ImmutableCallSite::arg_iterator
194           I = CS1.arg_begin(), E = CS1.arg_end(); I != E; ++I) {
195        const Value *Arg = *I;
196        if (!Arg->getType()->isPointerTy())
197          continue;
198        ModRefResult ArgMask;
199        Location CS1Loc =
200          getArgLocation(CS1, (unsigned) std::distance(CS1.arg_begin(), I),
201                         ArgMask);
202        if ((getModRefInfo(CS2, CS1Loc) & ArgMask) != NoModRef) {
203          R = Mask;
204          break;
205        }
206      }
207    }
208    if (R == NoModRef)
209      return R;
210  }
211
212  // If this is the end of the chain, don't forward.
213  if (!AA) return Mask;
214
215  // Otherwise, fall back to the next AA in the chain. But we can merge
216  // in any mask we've managed to compute.
217  return ModRefResult(AA->getModRefInfo(CS1, CS2) & Mask);
218}
219
220AliasAnalysis::ModRefBehavior
221AliasAnalysis::getModRefBehavior(ImmutableCallSite CS) {
222  assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
223
224  ModRefBehavior Min = UnknownModRefBehavior;
225
226  // Call back into the alias analysis with the other form of getModRefBehavior
227  // to see if it can give a better response.
228  if (const Function *F = CS.getCalledFunction())
229    Min = getModRefBehavior(F);
230
231  // If this is the end of the chain, don't forward.
232  if (!AA) return Min;
233
234  // Otherwise, fall back to the next AA in the chain. But we can merge
235  // in any result we've managed to compute.
236  return ModRefBehavior(AA->getModRefBehavior(CS) & Min);
237}
238
239AliasAnalysis::ModRefBehavior
240AliasAnalysis::getModRefBehavior(const Function *F) {
241  assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
242  return AA->getModRefBehavior(F);
243}
244
245//===----------------------------------------------------------------------===//
246// AliasAnalysis non-virtual helper method implementation
247//===----------------------------------------------------------------------===//
248
249AliasAnalysis::Location AliasAnalysis::getLocation(const LoadInst *LI) {
250  return Location(LI->getPointerOperand(),
251                  getTypeStoreSize(LI->getType()),
252                  LI->getMetadata(LLVMContext::MD_tbaa));
253}
254
255AliasAnalysis::Location AliasAnalysis::getLocation(const StoreInst *SI) {
256  return Location(SI->getPointerOperand(),
257                  getTypeStoreSize(SI->getValueOperand()->getType()),
258                  SI->getMetadata(LLVMContext::MD_tbaa));
259}
260
261AliasAnalysis::Location AliasAnalysis::getLocation(const VAArgInst *VI) {
262  return Location(VI->getPointerOperand(),
263                  UnknownSize,
264                  VI->getMetadata(LLVMContext::MD_tbaa));
265}
266
267AliasAnalysis::Location
268AliasAnalysis::getLocation(const AtomicCmpXchgInst *CXI) {
269  return Location(CXI->getPointerOperand(),
270                  getTypeStoreSize(CXI->getCompareOperand()->getType()),
271                  CXI->getMetadata(LLVMContext::MD_tbaa));
272}
273
274AliasAnalysis::Location
275AliasAnalysis::getLocation(const AtomicRMWInst *RMWI) {
276  return Location(RMWI->getPointerOperand(),
277                  getTypeStoreSize(RMWI->getValOperand()->getType()),
278                  RMWI->getMetadata(LLVMContext::MD_tbaa));
279}
280
281AliasAnalysis::Location
282AliasAnalysis::getLocationForSource(const MemTransferInst *MTI) {
283  uint64_t Size = UnknownSize;
284  if (ConstantInt *C = dyn_cast<ConstantInt>(MTI->getLength()))
285    Size = C->getValue().getZExtValue();
286
287  // memcpy/memmove can have TBAA tags. For memcpy, they apply
288  // to both the source and the destination.
289  MDNode *TBAATag = MTI->getMetadata(LLVMContext::MD_tbaa);
290
291  return Location(MTI->getRawSource(), Size, TBAATag);
292}
293
294AliasAnalysis::Location
295AliasAnalysis::getLocationForDest(const MemIntrinsic *MTI) {
296  uint64_t Size = UnknownSize;
297  if (ConstantInt *C = dyn_cast<ConstantInt>(MTI->getLength()))
298    Size = C->getValue().getZExtValue();
299
300  // memcpy/memmove can have TBAA tags. For memcpy, they apply
301  // to both the source and the destination.
302  MDNode *TBAATag = MTI->getMetadata(LLVMContext::MD_tbaa);
303
304  return Location(MTI->getRawDest(), Size, TBAATag);
305}
306
307
308
309AliasAnalysis::ModRefResult
310AliasAnalysis::getModRefInfo(const LoadInst *L, const Location &Loc) {
311  // Be conservative in the face of volatile/atomic.
312  if (!L->isUnordered())
313    return ModRef;
314
315  // If the load address doesn't alias the given address, it doesn't read
316  // or write the specified memory.
317  if (!alias(getLocation(L), Loc))
318    return NoModRef;
319
320  // Otherwise, a load just reads.
321  return Ref;
322}
323
324AliasAnalysis::ModRefResult
325AliasAnalysis::getModRefInfo(const StoreInst *S, const Location &Loc) {
326  // Be conservative in the face of volatile/atomic.
327  if (!S->isUnordered())
328    return ModRef;
329
330  // If the store address cannot alias the pointer in question, then the
331  // specified memory cannot be modified by the store.
332  if (!alias(getLocation(S), Loc))
333    return NoModRef;
334
335  // If the pointer is a pointer to constant memory, then it could not have been
336  // modified by this store.
337  if (pointsToConstantMemory(Loc))
338    return NoModRef;
339
340  // Otherwise, a store just writes.
341  return Mod;
342}
343
344AliasAnalysis::ModRefResult
345AliasAnalysis::getModRefInfo(const VAArgInst *V, const Location &Loc) {
346  // If the va_arg address cannot alias the pointer in question, then the
347  // specified memory cannot be accessed by the va_arg.
348  if (!alias(getLocation(V), Loc))
349    return NoModRef;
350
351  // If the pointer is a pointer to constant memory, then it could not have been
352  // modified by this va_arg.
353  if (pointsToConstantMemory(Loc))
354    return NoModRef;
355
356  // Otherwise, a va_arg reads and writes.
357  return ModRef;
358}
359
360AliasAnalysis::ModRefResult
361AliasAnalysis::getModRefInfo(const AtomicCmpXchgInst *CX, const Location &Loc) {
362  // Acquire/Release cmpxchg has properties that matter for arbitrary addresses.
363  if (CX->getSuccessOrdering() > Monotonic)
364    return ModRef;
365
366  // If the cmpxchg address does not alias the location, it does not access it.
367  if (!alias(getLocation(CX), Loc))
368    return NoModRef;
369
370  return ModRef;
371}
372
373AliasAnalysis::ModRefResult
374AliasAnalysis::getModRefInfo(const AtomicRMWInst *RMW, const Location &Loc) {
375  // Acquire/Release atomicrmw has properties that matter for arbitrary addresses.
376  if (RMW->getOrdering() > Monotonic)
377    return ModRef;
378
379  // If the atomicrmw address does not alias the location, it does not access it.
380  if (!alias(getLocation(RMW), Loc))
381    return NoModRef;
382
383  return ModRef;
384}
385
386namespace {
387  /// Only find pointer captures which happen before the given instruction. Uses
388  /// the dominator tree to determine whether one instruction is before another.
389  /// Only support the case where the Value is defined in the same basic block
390  /// as the given instruction and the use.
391  struct CapturesBefore : public CaptureTracker {
392    CapturesBefore(const Instruction *I, DominatorTree *DT)
393      : BeforeHere(I), DT(DT), Captured(false) {}
394
395    void tooManyUses() override { Captured = true; }
396
397    bool shouldExplore(const Use *U) override {
398      Instruction *I = cast<Instruction>(U->getUser());
399      BasicBlock *BB = I->getParent();
400      // We explore this usage only if the usage can reach "BeforeHere".
401      // If use is not reachable from entry, there is no need to explore.
402      if (BeforeHere != I && !DT->isReachableFromEntry(BB))
403        return false;
404      // If the value is defined in the same basic block as use and BeforeHere,
405      // there is no need to explore the use if BeforeHere dominates use.
406      // Check whether there is a path from I to BeforeHere.
407      if (BeforeHere != I && DT->dominates(BeforeHere, I) &&
408          !isPotentiallyReachable(I, BeforeHere, DT))
409        return false;
410      return true;
411    }
412
413    bool captured(const Use *U) override {
414      Instruction *I = cast<Instruction>(U->getUser());
415      BasicBlock *BB = I->getParent();
416      // Same logic as in shouldExplore.
417      if (BeforeHere != I && !DT->isReachableFromEntry(BB))
418        return false;
419      if (BeforeHere != I && DT->dominates(BeforeHere, I) &&
420          !isPotentiallyReachable(I, BeforeHere, DT))
421        return false;
422      Captured = true;
423      return true;
424    }
425
426    const Instruction *BeforeHere;
427    DominatorTree *DT;
428
429    bool Captured;
430  };
431}
432
433// FIXME: this is really just shoring-up a deficiency in alias analysis.
434// BasicAA isn't willing to spend linear time determining whether an alloca
435// was captured before or after this particular call, while we are. However,
436// with a smarter AA in place, this test is just wasting compile time.
437AliasAnalysis::ModRefResult
438AliasAnalysis::callCapturesBefore(const Instruction *I,
439                                  const AliasAnalysis::Location &MemLoc,
440                                  DominatorTree *DT) {
441  if (!DT || !DL) return AliasAnalysis::ModRef;
442
443  const Value *Object = GetUnderlyingObject(MemLoc.Ptr, DL);
444  if (!isIdentifiedObject(Object) || isa<GlobalValue>(Object) ||
445      isa<Constant>(Object))
446    return AliasAnalysis::ModRef;
447
448  ImmutableCallSite CS(I);
449  if (!CS.getInstruction() || CS.getInstruction() == Object)
450    return AliasAnalysis::ModRef;
451
452  CapturesBefore CB(I, DT);
453  llvm::PointerMayBeCaptured(Object, &CB);
454  if (CB.Captured)
455    return AliasAnalysis::ModRef;
456
457  unsigned ArgNo = 0;
458  AliasAnalysis::ModRefResult R = AliasAnalysis::NoModRef;
459  for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
460       CI != CE; ++CI, ++ArgNo) {
461    // Only look at the no-capture or byval pointer arguments.  If this
462    // pointer were passed to arguments that were neither of these, then it
463    // couldn't be no-capture.
464    if (!(*CI)->getType()->isPointerTy() ||
465        (!CS.doesNotCapture(ArgNo) && !CS.isByValArgument(ArgNo)))
466      continue;
467
468    // If this is a no-capture pointer argument, see if we can tell that it
469    // is impossible to alias the pointer we're checking.  If not, we have to
470    // assume that the call could touch the pointer, even though it doesn't
471    // escape.
472    if (isNoAlias(AliasAnalysis::Location(*CI),
473		  AliasAnalysis::Location(Object)))
474      continue;
475    if (CS.doesNotAccessMemory(ArgNo))
476      continue;
477    if (CS.onlyReadsMemory(ArgNo)) {
478      R = AliasAnalysis::Ref;
479      continue;
480    }
481    return AliasAnalysis::ModRef;
482  }
483  return R;
484}
485
486// AliasAnalysis destructor: DO NOT move this to the header file for
487// AliasAnalysis or else clients of the AliasAnalysis class may not depend on
488// the AliasAnalysis.o file in the current .a file, causing alias analysis
489// support to not be included in the tool correctly!
490//
491AliasAnalysis::~AliasAnalysis() {}
492
493/// InitializeAliasAnalysis - Subclasses must call this method to initialize the
494/// AliasAnalysis interface before any other methods are called.
495///
496void AliasAnalysis::InitializeAliasAnalysis(Pass *P) {
497  DataLayoutPass *DLP = P->getAnalysisIfAvailable<DataLayoutPass>();
498  DL = DLP ? &DLP->getDataLayout() : nullptr;
499  TLI = P->getAnalysisIfAvailable<TargetLibraryInfo>();
500  AA = &P->getAnalysis<AliasAnalysis>();
501}
502
503// getAnalysisUsage - All alias analysis implementations should invoke this
504// directly (using AliasAnalysis::getAnalysisUsage(AU)).
505void AliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
506  AU.addRequired<AliasAnalysis>();         // All AA's chain
507}
508
509/// getTypeStoreSize - Return the DataLayout store size for the given type,
510/// if known, or a conservative value otherwise.
511///
512uint64_t AliasAnalysis::getTypeStoreSize(Type *Ty) {
513  return DL ? DL->getTypeStoreSize(Ty) : UnknownSize;
514}
515
516/// canBasicBlockModify - Return true if it is possible for execution of the
517/// specified basic block to modify the value pointed to by Ptr.
518///
519bool AliasAnalysis::canBasicBlockModify(const BasicBlock &BB,
520                                        const Location &Loc) {
521  return canInstructionRangeModify(BB.front(), BB.back(), Loc);
522}
523
524/// canInstructionRangeModify - Return true if it is possible for the execution
525/// of the specified instructions to modify the value pointed to by Ptr.  The
526/// instructions to consider are all of the instructions in the range of [I1,I2]
527/// INCLUSIVE.  I1 and I2 must be in the same basic block.
528///
529bool AliasAnalysis::canInstructionRangeModify(const Instruction &I1,
530                                              const Instruction &I2,
531                                              const Location &Loc) {
532  assert(I1.getParent() == I2.getParent() &&
533         "Instructions not in same basic block!");
534  BasicBlock::const_iterator I = &I1;
535  BasicBlock::const_iterator E = &I2;
536  ++E;  // Convert from inclusive to exclusive range.
537
538  for (; I != E; ++I) // Check every instruction in range
539    if (getModRefInfo(I, Loc) & Mod)
540      return true;
541  return false;
542}
543
544/// isNoAliasCall - Return true if this pointer is returned by a noalias
545/// function.
546bool llvm::isNoAliasCall(const Value *V) {
547  if (isa<CallInst>(V) || isa<InvokeInst>(V))
548    return ImmutableCallSite(cast<Instruction>(V))
549      .paramHasAttr(0, Attribute::NoAlias);
550  return false;
551}
552
553/// isNoAliasArgument - Return true if this is an argument with the noalias
554/// attribute.
555bool llvm::isNoAliasArgument(const Value *V)
556{
557  if (const Argument *A = dyn_cast<Argument>(V))
558    return A->hasNoAliasAttr();
559  return false;
560}
561
562/// isIdentifiedObject - Return true if this pointer refers to a distinct and
563/// identifiable object.  This returns true for:
564///    Global Variables and Functions (but not Global Aliases)
565///    Allocas and Mallocs
566///    ByVal and NoAlias Arguments
567///    NoAlias returns
568///
569bool llvm::isIdentifiedObject(const Value *V) {
570  if (isa<AllocaInst>(V))
571    return true;
572  if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V))
573    return true;
574  if (isNoAliasCall(V))
575    return true;
576  if (const Argument *A = dyn_cast<Argument>(V))
577    return A->hasNoAliasAttr() || A->hasByValAttr();
578  return false;
579}
580