LLVM API Documentation

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
BasicAliasAnalysis.cpp
Go to the documentation of this file.
1 //===- BasicAliasAnalysis.cpp - Stateless Alias Analysis Impl -------------===//
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 defines the primary stateless implementation of the
11 // Alias Analysis interface that implements identities (two different
12 // globals cannot alias, etc), but does no stateful analysis.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "llvm/Analysis/Passes.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/SmallVector.h"
24 #include "llvm/IR/Constants.h"
25 #include "llvm/IR/DataLayout.h"
26 #include "llvm/IR/DerivedTypes.h"
27 #include "llvm/IR/Function.h"
28 #include "llvm/IR/GlobalAlias.h"
29 #include "llvm/IR/GlobalVariable.h"
30 #include "llvm/IR/Instructions.h"
31 #include "llvm/IR/IntrinsicInst.h"
32 #include "llvm/IR/LLVMContext.h"
33 #include "llvm/IR/Operator.h"
34 #include "llvm/Pass.h"
38 #include <algorithm>
39 using namespace llvm;
40 
41 //===----------------------------------------------------------------------===//
42 // Useful predicates
43 //===----------------------------------------------------------------------===//
44 
45 /// isNonEscapingLocalObject - Return true if the pointer is to a function-local
46 /// object that never escapes from the function.
47 static bool isNonEscapingLocalObject(const Value *V) {
48  // If this is a local allocation, check to see if it escapes.
49  if (isa<AllocaInst>(V) || isNoAliasCall(V))
50  // Set StoreCaptures to True so that we can assume in our callers that the
51  // pointer is not the result of a load instruction. Currently
52  // PointerMayBeCaptured doesn't have any special analysis for the
53  // StoreCaptures=false case; if it did, our callers could be refined to be
54  // more precise.
55  return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true);
56 
57  // If this is an argument that corresponds to a byval or noalias argument,
58  // then it has not escaped before entering the function. Check if it escapes
59  // inside the function.
60  if (const Argument *A = dyn_cast<Argument>(V))
61  if (A->hasByValAttr() || A->hasNoAliasAttr())
62  // Note even if the argument is marked nocapture we still need to check
63  // for copies made inside the function. The nocapture attribute only
64  // specifies that there are no copies made that outlive the function.
65  return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true);
66 
67  return false;
68 }
69 
70 /// isEscapeSource - Return true if the pointer is one which would have
71 /// been considered an escape by isNonEscapingLocalObject.
72 static bool isEscapeSource(const Value *V) {
73  if (isa<CallInst>(V) || isa<InvokeInst>(V) || isa<Argument>(V))
74  return true;
75 
76  // The load case works because isNonEscapingLocalObject considers all
77  // stores to be escapes (it passes true for the StoreCaptures argument
78  // to PointerMayBeCaptured).
79  if (isa<LoadInst>(V))
80  return true;
81 
82  return false;
83 }
84 
85 /// getObjectSize - Return the size of the object specified by V, or
86 /// UnknownSize if unknown.
87 static uint64_t getObjectSize(const Value *V, const DataLayout &TD,
88  const TargetLibraryInfo &TLI,
89  bool RoundToAlign = false) {
90  uint64_t Size;
91  if (getObjectSize(V, Size, &TD, &TLI, RoundToAlign))
92  return Size;
94 }
95 
96 /// isObjectSmallerThan - Return true if we can prove that the object specified
97 /// by V is smaller than Size.
98 static bool isObjectSmallerThan(const Value *V, uint64_t Size,
99  const DataLayout &TD,
100  const TargetLibraryInfo &TLI) {
101  // Note that the meanings of the "object" are slightly different in the
102  // following contexts:
103  // c1: llvm::getObjectSize()
104  // c2: llvm.objectsize() intrinsic
105  // c3: isObjectSmallerThan()
106  // c1 and c2 share the same meaning; however, the meaning of "object" in c3
107  // refers to the "entire object".
108  //
109  // Consider this example:
110  // char *p = (char*)malloc(100)
111  // char *q = p+80;
112  //
113  // In the context of c1 and c2, the "object" pointed by q refers to the
114  // stretch of memory of q[0:19]. So, getObjectSize(q) should return 20.
115  //
116  // However, in the context of c3, the "object" refers to the chunk of memory
117  // being allocated. So, the "object" has 100 bytes, and q points to the middle
118  // the "object". In case q is passed to isObjectSmallerThan() as the 1st
119  // parameter, before the llvm::getObjectSize() is called to get the size of
120  // entire object, we should:
121  // - either rewind the pointer q to the base-address of the object in
122  // question (in this case rewind to p), or
123  // - just give up. It is up to caller to make sure the pointer is pointing
124  // to the base address the object.
125  //
126  // We go for 2nd option for simplicity.
127  if (!isIdentifiedObject(V))
128  return false;
129 
130  // This function needs to use the aligned object size because we allow
131  // reads a bit past the end given sufficient alignment.
132  uint64_t ObjectSize = getObjectSize(V, TD, TLI, /*RoundToAlign*/true);
133 
134  return ObjectSize != AliasAnalysis::UnknownSize && ObjectSize < Size;
135 }
136 
137 /// isObjectSize - Return true if we can prove that the object specified
138 /// by V has size Size.
139 static bool isObjectSize(const Value *V, uint64_t Size,
140  const DataLayout &TD, const TargetLibraryInfo &TLI) {
141  uint64_t ObjectSize = getObjectSize(V, TD, TLI);
142  return ObjectSize != AliasAnalysis::UnknownSize && ObjectSize == Size;
143 }
144 
145 /// isIdentifiedFunctionLocal - Return true if V is umabigously identified
146 /// at the function-level. Different IdentifiedFunctionLocals can't alias.
147 /// Further, an IdentifiedFunctionLocal can not alias with any function
148 /// arguments other than itself, which is not neccessarily true for
149 /// IdentifiedObjects.
150 static bool isIdentifiedFunctionLocal(const Value *V)
151 {
152  return isa<AllocaInst>(V) || isNoAliasCall(V) || isNoAliasArgument(V);
153 }
154 
155 
156 //===----------------------------------------------------------------------===//
157 // GetElementPtr Instruction Decomposition and Analysis
158 //===----------------------------------------------------------------------===//
159 
160 namespace {
162  EK_NotExtended,
163  EK_SignExt,
164  EK_ZeroExt
165  };
166 
167  struct VariableGEPIndex {
168  const Value *V;
169  ExtensionKind Extension;
170  int64_t Scale;
171 
172  bool operator==(const VariableGEPIndex &Other) const {
173  return V == Other.V && Extension == Other.Extension &&
174  Scale == Other.Scale;
175  }
176 
177  bool operator!=(const VariableGEPIndex &Other) const {
178  return !operator==(Other);
179  }
180  };
181 }
182 
183 
184 /// GetLinearExpression - Analyze the specified value as a linear expression:
185 /// "A*V + B", where A and B are constant integers. Return the scale and offset
186 /// values as APInts and return V as a Value*, and return whether we looked
187 /// through any sign or zero extends. The incoming Value is known to have
188 /// IntegerType and it may already be sign or zero extended.
189 ///
190 /// Note that this looks through extends, so the high bits may not be
191 /// represented in the result.
192 static Value *GetLinearExpression(Value *V, APInt &Scale, APInt &Offset,
193  ExtensionKind &Extension,
194  const DataLayout &TD, unsigned Depth) {
195  assert(V->getType()->isIntegerTy() && "Not an integer value");
196 
197  // Limit our recursion depth.
198  if (Depth == 6) {
199  Scale = 1;
200  Offset = 0;
201  return V;
202  }
203 
204  if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(V)) {
205  if (ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) {
206  switch (BOp->getOpcode()) {
207  default: break;
208  case Instruction::Or:
209  // X|C == X+C if all the bits in C are unset in X. Otherwise we can't
210  // analyze it.
211  if (!MaskedValueIsZero(BOp->getOperand(0), RHSC->getValue(), &TD))
212  break;
213  // FALL THROUGH.
214  case Instruction::Add:
215  V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension,
216  TD, Depth+1);
217  Offset += RHSC->getValue();
218  return V;
219  case Instruction::Mul:
220  V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension,
221  TD, Depth+1);
222  Offset *= RHSC->getValue();
223  Scale *= RHSC->getValue();
224  return V;
225  case Instruction::Shl:
226  V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension,
227  TD, Depth+1);
228  Offset <<= RHSC->getValue().getLimitedValue();
229  Scale <<= RHSC->getValue().getLimitedValue();
230  return V;
231  }
232  }
233  }
234 
235  // Since GEP indices are sign extended anyway, we don't care about the high
236  // bits of a sign or zero extended value - just scales and offsets. The
237  // extensions have to be consistent though.
238  if ((isa<SExtInst>(V) && Extension != EK_ZeroExt) ||
239  (isa<ZExtInst>(V) && Extension != EK_SignExt)) {
240  Value *CastOp = cast<CastInst>(V)->getOperand(0);
241  unsigned OldWidth = Scale.getBitWidth();
242  unsigned SmallWidth = CastOp->getType()->getPrimitiveSizeInBits();
243  Scale = Scale.trunc(SmallWidth);
244  Offset = Offset.trunc(SmallWidth);
245  Extension = isa<SExtInst>(V) ? EK_SignExt : EK_ZeroExt;
246 
247  Value *Result = GetLinearExpression(CastOp, Scale, Offset, Extension,
248  TD, Depth+1);
249  Scale = Scale.zext(OldWidth);
250  Offset = Offset.zext(OldWidth);
251 
252  return Result;
253  }
254 
255  Scale = 1;
256  Offset = 0;
257  return V;
258 }
259 
260 /// DecomposeGEPExpression - If V is a symbolic pointer expression, decompose it
261 /// into a base pointer with a constant offset and a number of scaled symbolic
262 /// offsets.
263 ///
264 /// The scaled symbolic offsets (represented by pairs of a Value* and a scale in
265 /// the VarIndices vector) are Value*'s that are known to be scaled by the
266 /// specified amount, but which may have other unrepresented high bits. As such,
267 /// the gep cannot necessarily be reconstructed from its decomposed form.
268 ///
269 /// When DataLayout is around, this function is capable of analyzing everything
270 /// that GetUnderlyingObject can look through. When not, it just looks
271 /// through pointer casts.
272 ///
273 static const Value *
274 DecomposeGEPExpression(const Value *V, int64_t &BaseOffs,
276  const DataLayout *TD) {
277  // Limit recursion depth to limit compile time in crazy cases.
278  unsigned MaxLookup = 6;
279 
280  BaseOffs = 0;
281  do {
282  // See if this is a bitcast or GEP.
283  const Operator *Op = dyn_cast<Operator>(V);
284  if (Op == 0) {
285  // The only non-operator case we can handle are GlobalAliases.
286  if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
287  if (!GA->mayBeOverridden()) {
288  V = GA->getAliasee();
289  continue;
290  }
291  }
292  return V;
293  }
294 
295  if (Op->getOpcode() == Instruction::BitCast) {
296  V = Op->getOperand(0);
297  continue;
298  }
299 
300  const GEPOperator *GEPOp = dyn_cast<GEPOperator>(Op);
301  if (GEPOp == 0) {
302  // If it's not a GEP, hand it off to SimplifyInstruction to see if it
303  // can come up with something. This matches what GetUnderlyingObject does.
304  if (const Instruction *I = dyn_cast<Instruction>(V))
305  // TODO: Get a DominatorTree and use it here.
306  if (const Value *Simplified =
307  SimplifyInstruction(const_cast<Instruction *>(I), TD)) {
308  V = Simplified;
309  continue;
310  }
311 
312  return V;
313  }
314 
315  // Don't attempt to analyze GEPs over unsized objects.
316  if (!GEPOp->getOperand(0)->getType()->getPointerElementType()->isSized())
317  return V;
318 
319  // If we are lacking DataLayout information, we can't compute the offets of
320  // elements computed by GEPs. However, we can handle bitcast equivalent
321  // GEPs.
322  if (TD == 0) {
323  if (!GEPOp->hasAllZeroIndices())
324  return V;
325  V = GEPOp->getOperand(0);
326  continue;
327  }
328 
329  unsigned AS = GEPOp->getPointerAddressSpace();
330  // Walk the indices of the GEP, accumulating them into BaseOff/VarIndices.
331  gep_type_iterator GTI = gep_type_begin(GEPOp);
332  for (User::const_op_iterator I = GEPOp->op_begin()+1,
333  E = GEPOp->op_end(); I != E; ++I) {
334  Value *Index = *I;
335  // Compute the (potentially symbolic) offset in bytes for this index.
336  if (StructType *STy = dyn_cast<StructType>(*GTI++)) {
337  // For a struct, add the member offset.
338  unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue();
339  if (FieldNo == 0) continue;
340 
341  BaseOffs += TD->getStructLayout(STy)->getElementOffset(FieldNo);
342  continue;
343  }
344 
345  // For an array/pointer, add the element offset, explicitly scaled.
346  if (ConstantInt *CIdx = dyn_cast<ConstantInt>(Index)) {
347  if (CIdx->isZero()) continue;
348  BaseOffs += TD->getTypeAllocSize(*GTI)*CIdx->getSExtValue();
349  continue;
350  }
351 
352  uint64_t Scale = TD->getTypeAllocSize(*GTI);
353  ExtensionKind Extension = EK_NotExtended;
354 
355  // If the integer type is smaller than the pointer size, it is implicitly
356  // sign extended to pointer size.
357  unsigned Width = Index->getType()->getIntegerBitWidth();
358  if (TD->getPointerSizeInBits(AS) > Width)
359  Extension = EK_SignExt;
360 
361  // Use GetLinearExpression to decompose the index into a C1*V+C2 form.
362  APInt IndexScale(Width, 0), IndexOffset(Width, 0);
363  Index = GetLinearExpression(Index, IndexScale, IndexOffset, Extension,
364  *TD, 0);
365 
366  // The GEP index scale ("Scale") scales C1*V+C2, yielding (C1*V+C2)*Scale.
367  // This gives us an aggregate computation of (C1*Scale)*V + C2*Scale.
368  BaseOffs += IndexOffset.getSExtValue()*Scale;
369  Scale *= IndexScale.getSExtValue();
370 
371  // If we already had an occurrence of this index variable, merge this
372  // scale into it. For example, we want to handle:
373  // A[x][x] -> x*16 + x*4 -> x*20
374  // This also ensures that 'x' only appears in the index list once.
375  for (unsigned i = 0, e = VarIndices.size(); i != e; ++i) {
376  if (VarIndices[i].V == Index &&
377  VarIndices[i].Extension == Extension) {
378  Scale += VarIndices[i].Scale;
379  VarIndices.erase(VarIndices.begin()+i);
380  break;
381  }
382  }
383 
384  // Make sure that we have a scale that makes sense for this target's
385  // pointer size.
386  if (unsigned ShiftBits = 64 - TD->getPointerSizeInBits(AS)) {
387  Scale <<= ShiftBits;
388  Scale = (int64_t)Scale >> ShiftBits;
389  }
390 
391  if (Scale) {
392  VariableGEPIndex Entry = {Index, Extension,
393  static_cast<int64_t>(Scale)};
394  VarIndices.push_back(Entry);
395  }
396  }
397 
398  // Analyze the base pointer next.
399  V = GEPOp->getOperand(0);
400  } while (--MaxLookup);
401 
402  // If the chain of expressions is too deep, just return early.
403  return V;
404 }
405 
406 /// GetIndexDifference - Dest and Src are the variable indices from two
407 /// decomposed GetElementPtr instructions GEP1 and GEP2 which have common base
408 /// pointers. Subtract the GEP2 indices from GEP1 to find the symbolic
409 /// difference between the two pointers.
412  if (Src.empty()) return;
413 
414  for (unsigned i = 0, e = Src.size(); i != e; ++i) {
415  const Value *V = Src[i].V;
416  ExtensionKind Extension = Src[i].Extension;
417  int64_t Scale = Src[i].Scale;
418 
419  // Find V in Dest. This is N^2, but pointer indices almost never have more
420  // than a few variable indexes.
421  for (unsigned j = 0, e = Dest.size(); j != e; ++j) {
422  if (Dest[j].V != V || Dest[j].Extension != Extension) continue;
423 
424  // If we found it, subtract off Scale V's from the entry in Dest. If it
425  // goes to zero, remove the entry.
426  if (Dest[j].Scale != Scale)
427  Dest[j].Scale -= Scale;
428  else
429  Dest.erase(Dest.begin()+j);
430  Scale = 0;
431  break;
432  }
433 
434  // If we didn't consume this entry, add it to the end of the Dest list.
435  if (Scale) {
436  VariableGEPIndex Entry = { V, Extension, -Scale };
437  Dest.push_back(Entry);
438  }
439  }
440 }
441 
442 //===----------------------------------------------------------------------===//
443 // BasicAliasAnalysis Pass
444 //===----------------------------------------------------------------------===//
445 
446 #ifndef NDEBUG
447 static const Function *getParent(const Value *V) {
448  if (const Instruction *inst = dyn_cast<Instruction>(V))
449  return inst->getParent()->getParent();
450 
451  if (const Argument *arg = dyn_cast<Argument>(V))
452  return arg->getParent();
453 
454  return NULL;
455 }
456 
457 static bool notDifferentParent(const Value *O1, const Value *O2) {
458 
459  const Function *F1 = getParent(O1);
460  const Function *F2 = getParent(O2);
461 
462  return !F1 || !F2 || F1 == F2;
463 }
464 #endif
465 
466 namespace {
467  /// BasicAliasAnalysis - This is the primary alias analysis implementation.
468  struct BasicAliasAnalysis : public ImmutablePass, public AliasAnalysis {
469  static char ID; // Class identification, replacement for typeinfo
470  BasicAliasAnalysis() : ImmutablePass(ID) {
472  }
473 
474  virtual void initializePass() {
475  InitializeAliasAnalysis(this);
476  }
477 
478  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
481  }
482 
483  virtual AliasResult alias(const Location &LocA,
484  const Location &LocB) {
485  assert(AliasCache.empty() && "AliasCache must be cleared after use!");
486  assert(notDifferentParent(LocA.Ptr, LocB.Ptr) &&
487  "BasicAliasAnalysis doesn't support interprocedural queries.");
488  AliasResult Alias = aliasCheck(LocA.Ptr, LocA.Size, LocA.TBAATag,
489  LocB.Ptr, LocB.Size, LocB.TBAATag);
490  // AliasCache rarely has more than 1 or 2 elements, always use
491  // shrink_and_clear so it quickly returns to the inline capacity of the
492  // SmallDenseMap if it ever grows larger.
493  // FIXME: This should really be shrink_to_inline_capacity_and_clear().
494  AliasCache.shrink_and_clear();
495  return Alias;
496  }
497 
498  virtual ModRefResult getModRefInfo(ImmutableCallSite CS,
499  const Location &Loc);
500 
501  virtual ModRefResult getModRefInfo(ImmutableCallSite CS1,
502  ImmutableCallSite CS2) {
503  // The AliasAnalysis base class has some smarts, lets use them.
504  return AliasAnalysis::getModRefInfo(CS1, CS2);
505  }
506 
507  /// pointsToConstantMemory - Chase pointers until we find a (constant
508  /// global) or not.
509  virtual bool pointsToConstantMemory(const Location &Loc, bool OrLocal);
510 
511  /// getModRefBehavior - Return the behavior when calling the given
512  /// call site.
513  virtual ModRefBehavior getModRefBehavior(ImmutableCallSite CS);
514 
515  /// getModRefBehavior - Return the behavior when calling the given function.
516  /// For use when the call site is not known.
517  virtual ModRefBehavior getModRefBehavior(const Function *F);
518 
519  /// getAdjustedAnalysisPointer - This method is used when a pass implements
520  /// an analysis interface through multiple inheritance. If needed, it
521  /// should override this to adjust the this pointer as needed for the
522  /// specified pass info.
523  virtual void *getAdjustedAnalysisPointer(const void *ID) {
524  if (ID == &AliasAnalysis::ID)
525  return (AliasAnalysis*)this;
526  return this;
527  }
528 
529  private:
530  // AliasCache - Track alias queries to guard against recursion.
531  typedef std::pair<Location, Location> LocPair;
532  typedef SmallDenseMap<LocPair, AliasResult, 8> AliasCacheTy;
533  AliasCacheTy AliasCache;
534 
535  // Visited - Track instructions visited by pointsToConstantMemory.
537 
538  // aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP
539  // instruction against another.
540  AliasResult aliasGEP(const GEPOperator *V1, uint64_t V1Size,
541  const MDNode *V1TBAAInfo,
542  const Value *V2, uint64_t V2Size,
543  const MDNode *V2TBAAInfo,
544  const Value *UnderlyingV1, const Value *UnderlyingV2);
545 
546  // aliasPHI - Provide a bunch of ad-hoc rules to disambiguate a PHI
547  // instruction against another.
548  AliasResult aliasPHI(const PHINode *PN, uint64_t PNSize,
549  const MDNode *PNTBAAInfo,
550  const Value *V2, uint64_t V2Size,
551  const MDNode *V2TBAAInfo);
552 
553  /// aliasSelect - Disambiguate a Select instruction against another value.
554  AliasResult aliasSelect(const SelectInst *SI, uint64_t SISize,
555  const MDNode *SITBAAInfo,
556  const Value *V2, uint64_t V2Size,
557  const MDNode *V2TBAAInfo);
558 
559  AliasResult aliasCheck(const Value *V1, uint64_t V1Size,
560  const MDNode *V1TBAATag,
561  const Value *V2, uint64_t V2Size,
562  const MDNode *V2TBAATag);
563  };
564 } // End of anonymous namespace
565 
566 // Register this pass...
567 char BasicAliasAnalysis::ID = 0;
568 INITIALIZE_AG_PASS_BEGIN(BasicAliasAnalysis, AliasAnalysis, "basicaa",
569  "Basic Alias Analysis (stateless AA impl)",
570  false, true, false)
573  "Basic Alias Analysis (stateless AA impl)",
575 
576 
578  return new BasicAliasAnalysis();
579 }
580 
581 /// pointsToConstantMemory - Returns whether the given pointer value
582 /// points to memory that is local to the function, with global constants being
583 /// considered local to all functions.
584 bool
585 BasicAliasAnalysis::pointsToConstantMemory(const Location &Loc, bool OrLocal) {
586  assert(Visited.empty() && "Visited must be cleared after use!");
587 
588  unsigned MaxLookup = 8;
590  Worklist.push_back(Loc.Ptr);
591  do {
592  const Value *V = GetUnderlyingObject(Worklist.pop_back_val(), TD);
593  if (!Visited.insert(V)) {
594  Visited.clear();
595  return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal);
596  }
597 
598  // An alloca instruction defines local memory.
599  if (OrLocal && isa<AllocaInst>(V))
600  continue;
601 
602  // A global constant counts as local memory for our purposes.
603  if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) {
604  // Note: this doesn't require GV to be "ODR" because it isn't legal for a
605  // global to be marked constant in some modules and non-constant in
606  // others. GV may even be a declaration, not a definition.
607  if (!GV->isConstant()) {
608  Visited.clear();
609  return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal);
610  }
611  continue;
612  }
613 
614  // If both select values point to local memory, then so does the select.
615  if (const SelectInst *SI = dyn_cast<SelectInst>(V)) {
616  Worklist.push_back(SI->getTrueValue());
617  Worklist.push_back(SI->getFalseValue());
618  continue;
619  }
620 
621  // If all values incoming to a phi node point to local memory, then so does
622  // the phi.
623  if (const PHINode *PN = dyn_cast<PHINode>(V)) {
624  // Don't bother inspecting phi nodes with many operands.
625  if (PN->getNumIncomingValues() > MaxLookup) {
626  Visited.clear();
627  return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal);
628  }
629  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
630  Worklist.push_back(PN->getIncomingValue(i));
631  continue;
632  }
633 
634  // Otherwise be conservative.
635  Visited.clear();
636  return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal);
637 
638  } while (!Worklist.empty() && --MaxLookup);
639 
640  Visited.clear();
641  return Worklist.empty();
642 }
643 
644 /// getModRefBehavior - Return the behavior when calling the given call site.
646 BasicAliasAnalysis::getModRefBehavior(ImmutableCallSite CS) {
647  if (CS.doesNotAccessMemory())
648  // Can't do better than this.
649  return DoesNotAccessMemory;
650 
651  ModRefBehavior Min = UnknownModRefBehavior;
652 
653  // If the callsite knows it only reads memory, don't return worse
654  // than that.
655  if (CS.onlyReadsMemory())
656  Min = OnlyReadsMemory;
657 
658  // The AliasAnalysis base class has some smarts, lets use them.
660 }
661 
662 /// getModRefBehavior - Return the behavior when calling the given function.
663 /// For use when the call site is not known.
665 BasicAliasAnalysis::getModRefBehavior(const Function *F) {
666  // If the function declares it doesn't access memory, we can't do better.
667  if (F->doesNotAccessMemory())
668  return DoesNotAccessMemory;
669 
670  // For intrinsics, we can check the table.
671  if (unsigned iid = F->getIntrinsicID()) {
672 #define GET_INTRINSIC_MODREF_BEHAVIOR
673 #include "llvm/IR/Intrinsics.gen"
674 #undef GET_INTRINSIC_MODREF_BEHAVIOR
675  }
676 
677  ModRefBehavior Min = UnknownModRefBehavior;
678 
679  // If the function declares it only reads memory, go with that.
680  if (F->onlyReadsMemory())
681  Min = OnlyReadsMemory;
682 
683  // Otherwise be conservative.
685 }
686 
687 /// getModRefInfo - Check to see if the specified callsite can clobber the
688 /// specified memory object. Since we only look at local properties of this
689 /// function, we really can't say much about this query. We do, however, use
690 /// simple "address taken" analysis on local objects.
692 BasicAliasAnalysis::getModRefInfo(ImmutableCallSite CS,
693  const Location &Loc) {
694  assert(notDifferentParent(CS.getInstruction(), Loc.Ptr) &&
695  "AliasAnalysis query involving multiple functions!");
696 
697  const Value *Object = GetUnderlyingObject(Loc.Ptr, TD);
698 
699  // If this is a tail call and Loc.Ptr points to a stack location, we know that
700  // the tail call cannot access or modify the local stack.
701  // We cannot exclude byval arguments here; these belong to the caller of
702  // the current function not to the current function, and a tail callee
703  // may reference them.
704  if (isa<AllocaInst>(Object))
705  if (const CallInst *CI = dyn_cast<CallInst>(CS.getInstruction()))
706  if (CI->isTailCall())
707  return NoModRef;
708 
709  // If the pointer is to a locally allocated object that does not escape,
710  // then the call can not mod/ref the pointer unless the call takes the pointer
711  // as an argument, and itself doesn't capture it.
712  if (!isa<Constant>(Object) && CS.getInstruction() != Object &&
713  isNonEscapingLocalObject(Object)) {
714  bool PassedAsArg = false;
715  unsigned ArgNo = 0;
716  for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
717  CI != CE; ++CI, ++ArgNo) {
718  // Only look at the no-capture or byval pointer arguments. If this
719  // pointer were passed to arguments that were neither of these, then it
720  // couldn't be no-capture.
721  if (!(*CI)->getType()->isPointerTy() ||
722  (!CS.doesNotCapture(ArgNo) && !CS.isByValArgument(ArgNo)))
723  continue;
724 
725  // If this is a no-capture pointer argument, see if we can tell that it
726  // is impossible to alias the pointer we're checking. If not, we have to
727  // assume that the call could touch the pointer, even though it doesn't
728  // escape.
729  if (!isNoAlias(Location(*CI), Location(Object))) {
730  PassedAsArg = true;
731  break;
732  }
733  }
734 
735  if (!PassedAsArg)
736  return NoModRef;
737  }
738 
739  const TargetLibraryInfo &TLI = getAnalysis<TargetLibraryInfo>();
740  ModRefResult Min = ModRef;
741 
742  // Finally, handle specific knowledge of intrinsics.
744  if (II != 0)
745  switch (II->getIntrinsicID()) {
746  default: break;
747  case Intrinsic::memcpy:
748  case Intrinsic::memmove: {
749  uint64_t Len = UnknownSize;
750  if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getArgOperand(2)))
751  Len = LenCI->getZExtValue();
752  Value *Dest = II->getArgOperand(0);
753  Value *Src = II->getArgOperand(1);
754  // If it can't overlap the source dest, then it doesn't modref the loc.
755  if (isNoAlias(Location(Dest, Len), Loc)) {
756  if (isNoAlias(Location(Src, Len), Loc))
757  return NoModRef;
758  // If it can't overlap the dest, then worst case it reads the loc.
759  Min = Ref;
760  } else if (isNoAlias(Location(Src, Len), Loc)) {
761  // If it can't overlap the source, then worst case it mutates the loc.
762  Min = Mod;
763  }
764  break;
765  }
766  case Intrinsic::memset:
767  // Since memset is 'accesses arguments' only, the AliasAnalysis base class
768  // will handle it for the variable length case.
769  if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getArgOperand(2))) {
770  uint64_t Len = LenCI->getZExtValue();
771  Value *Dest = II->getArgOperand(0);
772  if (isNoAlias(Location(Dest, Len), Loc))
773  return NoModRef;
774  }
775  // We know that memset doesn't load anything.
776  Min = Mod;
777  break;
781  uint64_t PtrSize =
782  cast<ConstantInt>(II->getArgOperand(0))->getZExtValue();
783  if (isNoAlias(Location(II->getArgOperand(1),
784  PtrSize,
786  Loc))
787  return NoModRef;
788  break;
789  }
791  uint64_t PtrSize =
792  cast<ConstantInt>(II->getArgOperand(1))->getZExtValue();
793  if (isNoAlias(Location(II->getArgOperand(2),
794  PtrSize,
796  Loc))
797  return NoModRef;
798  break;
799  }
801  // LLVM's vld1 and vst1 intrinsics currently only support a single
802  // vector register.
803  uint64_t Size =
804  TD ? TD->getTypeStoreSize(II->getType()) : UnknownSize;
805  if (isNoAlias(Location(II->getArgOperand(0), Size,
807  Loc))
808  return NoModRef;
809  break;
810  }
812  uint64_t Size =
813  TD ? TD->getTypeStoreSize(II->getArgOperand(1)->getType()) : UnknownSize;
814  if (isNoAlias(Location(II->getArgOperand(0), Size,
816  Loc))
817  return NoModRef;
818  break;
819  }
820  }
821 
822  // We can bound the aliasing properties of memset_pattern16 just as we can
823  // for memcpy/memset. This is particularly important because the
824  // LoopIdiomRecognizer likes to turn loops into calls to memset_pattern16
825  // whenever possible.
826  else if (TLI.has(LibFunc::memset_pattern16) &&
827  CS.getCalledFunction() &&
828  CS.getCalledFunction()->getName() == "memset_pattern16") {
829  const Function *MS = CS.getCalledFunction();
830  FunctionType *MemsetType = MS->getFunctionType();
831  if (!MemsetType->isVarArg() && MemsetType->getNumParams() == 3 &&
832  isa<PointerType>(MemsetType->getParamType(0)) &&
833  isa<PointerType>(MemsetType->getParamType(1)) &&
834  isa<IntegerType>(MemsetType->getParamType(2))) {
835  uint64_t Len = UnknownSize;
836  if (const ConstantInt *LenCI = dyn_cast<ConstantInt>(CS.getArgument(2)))
837  Len = LenCI->getZExtValue();
838  const Value *Dest = CS.getArgument(0);
839  const Value *Src = CS.getArgument(1);
840  // If it can't overlap the source dest, then it doesn't modref the loc.
841  if (isNoAlias(Location(Dest, Len), Loc)) {
842  // Always reads 16 bytes of the source.
843  if (isNoAlias(Location(Src, 16), Loc))
844  return NoModRef;
845  // If it can't overlap the dest, then worst case it reads the loc.
846  Min = Ref;
847  // Always reads 16 bytes of the source.
848  } else if (isNoAlias(Location(Src, 16), Loc)) {
849  // If it can't overlap the source, then worst case it mutates the loc.
850  Min = Mod;
851  }
852  }
853  }
854 
855  // The AliasAnalysis base class has some smarts, lets use them.
856  return ModRefResult(AliasAnalysis::getModRefInfo(CS, Loc) & Min);
857 }
858 
861  unsigned Size1 = Indices1.size();
862  unsigned Size2 = Indices2.size();
863 
864  if (Size1 != Size2)
865  return false;
866 
867  for (unsigned I = 0; I != Size1; ++I)
868  if (Indices1[I] != Indices2[I])
869  return false;
870 
871  return true;
872 }
873 
874 /// aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP instruction
875 /// against another pointer. We know that V1 is a GEP, but we don't know
876 /// anything about V2. UnderlyingV1 is GetUnderlyingObject(GEP1, TD),
877 /// UnderlyingV2 is the same for V2.
878 ///
880 BasicAliasAnalysis::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size,
881  const MDNode *V1TBAAInfo,
882  const Value *V2, uint64_t V2Size,
883  const MDNode *V2TBAAInfo,
884  const Value *UnderlyingV1,
885  const Value *UnderlyingV2) {
886  int64_t GEP1BaseOffset;
887  SmallVector<VariableGEPIndex, 4> GEP1VariableIndices;
888 
889  // If we have two gep instructions with must-alias or not-alias'ing base
890  // pointers, figure out if the indexes to the GEP tell us anything about the
891  // derived pointer.
892  if (const GEPOperator *GEP2 = dyn_cast<GEPOperator>(V2)) {
893  // Do the base pointers alias?
894  AliasResult BaseAlias = aliasCheck(UnderlyingV1, UnknownSize, 0,
895  UnderlyingV2, UnknownSize, 0);
896 
897  // Check for geps of non-aliasing underlying pointers where the offsets are
898  // identical.
899  if ((BaseAlias == MayAlias) && V1Size == V2Size) {
900  // Do the base pointers alias assuming type and size.
901  AliasResult PreciseBaseAlias = aliasCheck(UnderlyingV1, V1Size,
902  V1TBAAInfo, UnderlyingV2,
903  V2Size, V2TBAAInfo);
904  if (PreciseBaseAlias == NoAlias) {
905  // See if the computed offset from the common pointer tells us about the
906  // relation of the resulting pointer.
907  int64_t GEP2BaseOffset;
908  SmallVector<VariableGEPIndex, 4> GEP2VariableIndices;
909  const Value *GEP2BasePtr =
910  DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, TD);
911  const Value *GEP1BasePtr =
912  DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD);
913  // DecomposeGEPExpression and GetUnderlyingObject should return the
914  // same result except when DecomposeGEPExpression has no DataLayout.
915  if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) {
916  assert(TD == 0 &&
917  "DecomposeGEPExpression and GetUnderlyingObject disagree!");
918  return MayAlias;
919  }
920  // Same offsets.
921  if (GEP1BaseOffset == GEP2BaseOffset &&
922  areVarIndicesEqual(GEP1VariableIndices, GEP2VariableIndices))
923  return NoAlias;
924  GEP1VariableIndices.clear();
925  }
926  }
927 
928  // If we get a No or May, then return it immediately, no amount of analysis
929  // will improve this situation.
930  if (BaseAlias != MustAlias) return BaseAlias;
931 
932  // Otherwise, we have a MustAlias. Since the base pointers alias each other
933  // exactly, see if the computed offset from the common pointer tells us
934  // about the relation of the resulting pointer.
935  const Value *GEP1BasePtr =
936  DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD);
937 
938  int64_t GEP2BaseOffset;
939  SmallVector<VariableGEPIndex, 4> GEP2VariableIndices;
940  const Value *GEP2BasePtr =
941  DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, TD);
942 
943  // DecomposeGEPExpression and GetUnderlyingObject should return the
944  // same result except when DecomposeGEPExpression has no DataLayout.
945  if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) {
946  assert(TD == 0 &&
947  "DecomposeGEPExpression and GetUnderlyingObject disagree!");
948  return MayAlias;
949  }
950 
951  // Subtract the GEP2 pointer from the GEP1 pointer to find out their
952  // symbolic difference.
953  GEP1BaseOffset -= GEP2BaseOffset;
954  GetIndexDifference(GEP1VariableIndices, GEP2VariableIndices);
955 
956  } else {
957  // Check to see if these two pointers are related by the getelementptr
958  // instruction. If one pointer is a GEP with a non-zero index of the other
959  // pointer, we know they cannot alias.
960 
961  // If both accesses are unknown size, we can't do anything useful here.
962  if (V1Size == UnknownSize && V2Size == UnknownSize)
963  return MayAlias;
964 
965  AliasResult R = aliasCheck(UnderlyingV1, UnknownSize, 0,
966  V2, V2Size, V2TBAAInfo);
967  if (R != MustAlias)
968  // If V2 may alias GEP base pointer, conservatively returns MayAlias.
969  // If V2 is known not to alias GEP base pointer, then the two values
970  // cannot alias per GEP semantics: "A pointer value formed from a
971  // getelementptr instruction is associated with the addresses associated
972  // with the first operand of the getelementptr".
973  return R;
974 
975  const Value *GEP1BasePtr =
976  DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD);
977 
978  // DecomposeGEPExpression and GetUnderlyingObject should return the
979  // same result except when DecomposeGEPExpression has no DataLayout.
980  if (GEP1BasePtr != UnderlyingV1) {
981  assert(TD == 0 &&
982  "DecomposeGEPExpression and GetUnderlyingObject disagree!");
983  return MayAlias;
984  }
985  }
986 
987  // In the two GEP Case, if there is no difference in the offsets of the
988  // computed pointers, the resultant pointers are a must alias. This
989  // hapens when we have two lexically identical GEP's (for example).
990  //
991  // In the other case, if we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2
992  // must aliases the GEP, the end result is a must alias also.
993  if (GEP1BaseOffset == 0 && GEP1VariableIndices.empty())
994  return MustAlias;
995 
996  // If there is a constant difference between the pointers, but the difference
997  // is less than the size of the associated memory object, then we know
998  // that the objects are partially overlapping. If the difference is
999  // greater, we know they do not overlap.
1000  if (GEP1BaseOffset != 0 && GEP1VariableIndices.empty()) {
1001  if (GEP1BaseOffset >= 0) {
1002  if (V2Size != UnknownSize) {
1003  if ((uint64_t)GEP1BaseOffset < V2Size)
1004  return PartialAlias;
1005  return NoAlias;
1006  }
1007  } else {
1008  if (V1Size != UnknownSize) {
1009  if (-(uint64_t)GEP1BaseOffset < V1Size)
1010  return PartialAlias;
1011  return NoAlias;
1012  }
1013  }
1014  }
1015 
1016  // Try to distinguish something like &A[i][1] against &A[42][0].
1017  // Grab the least significant bit set in any of the scales.
1018  if (!GEP1VariableIndices.empty()) {
1019  uint64_t Modulo = 0;
1020  for (unsigned i = 0, e = GEP1VariableIndices.size(); i != e; ++i)
1021  Modulo |= (uint64_t)GEP1VariableIndices[i].Scale;
1022  Modulo = Modulo ^ (Modulo & (Modulo - 1));
1023 
1024  // We can compute the difference between the two addresses
1025  // mod Modulo. Check whether that difference guarantees that the
1026  // two locations do not alias.
1027  uint64_t ModOffset = (uint64_t)GEP1BaseOffset & (Modulo - 1);
1028  if (V1Size != UnknownSize && V2Size != UnknownSize &&
1029  ModOffset >= V2Size && V1Size <= Modulo - ModOffset)
1030  return NoAlias;
1031  }
1032 
1033  // Statically, we can see that the base objects are the same, but the
1034  // pointers have dynamic offsets which we can't resolve. And none of our
1035  // little tricks above worked.
1036  //
1037  // TODO: Returning PartialAlias instead of MayAlias is a mild hack; the
1038  // practical effect of this is protecting TBAA in the case of dynamic
1039  // indices into arrays of unions or malloc'd memory.
1040  return PartialAlias;
1041 }
1042 
1045  // If the results agree, take it.
1046  if (A == B)
1047  return A;
1048  // A mix of PartialAlias and MustAlias is PartialAlias.
1052  // Otherwise, we don't know anything.
1053  return AliasAnalysis::MayAlias;
1054 }
1055 
1056 /// aliasSelect - Provide a bunch of ad-hoc rules to disambiguate a Select
1057 /// instruction against another.
1059 BasicAliasAnalysis::aliasSelect(const SelectInst *SI, uint64_t SISize,
1060  const MDNode *SITBAAInfo,
1061  const Value *V2, uint64_t V2Size,
1062  const MDNode *V2TBAAInfo) {
1063  // If the values are Selects with the same condition, we can do a more precise
1064  // check: just check for aliases between the values on corresponding arms.
1065  if (const SelectInst *SI2 = dyn_cast<SelectInst>(V2))
1066  if (SI->getCondition() == SI2->getCondition()) {
1067  AliasResult Alias =
1068  aliasCheck(SI->getTrueValue(), SISize, SITBAAInfo,
1069  SI2->getTrueValue(), V2Size, V2TBAAInfo);
1070  if (Alias == MayAlias)
1071  return MayAlias;
1072  AliasResult ThisAlias =
1073  aliasCheck(SI->getFalseValue(), SISize, SITBAAInfo,
1074  SI2->getFalseValue(), V2Size, V2TBAAInfo);
1075  return MergeAliasResults(ThisAlias, Alias);
1076  }
1077 
1078  // If both arms of the Select node NoAlias or MustAlias V2, then returns
1079  // NoAlias / MustAlias. Otherwise, returns MayAlias.
1080  AliasResult Alias =
1081  aliasCheck(V2, V2Size, V2TBAAInfo, SI->getTrueValue(), SISize, SITBAAInfo);
1082  if (Alias == MayAlias)
1083  return MayAlias;
1084 
1085  AliasResult ThisAlias =
1086  aliasCheck(V2, V2Size, V2TBAAInfo, SI->getFalseValue(), SISize, SITBAAInfo);
1087  return MergeAliasResults(ThisAlias, Alias);
1088 }
1089 
1090 // aliasPHI - Provide a bunch of ad-hoc rules to disambiguate a PHI instruction
1091 // against another.
1093 BasicAliasAnalysis::aliasPHI(const PHINode *PN, uint64_t PNSize,
1094  const MDNode *PNTBAAInfo,
1095  const Value *V2, uint64_t V2Size,
1096  const MDNode *V2TBAAInfo) {
1097  // If the values are PHIs in the same block, we can do a more precise
1098  // as well as efficient check: just check for aliases between the values
1099  // on corresponding edges.
1100  if (const PHINode *PN2 = dyn_cast<PHINode>(V2))
1101  if (PN2->getParent() == PN->getParent()) {
1102  LocPair Locs(Location(PN, PNSize, PNTBAAInfo),
1103  Location(V2, V2Size, V2TBAAInfo));
1104  if (PN > V2)
1105  std::swap(Locs.first, Locs.second);
1106  // Analyse the PHIs' inputs under the assumption that the PHIs are
1107  // NoAlias.
1108  // If the PHIs are May/MustAlias there must be (recursively) an input
1109  // operand from outside the PHIs' cycle that is MayAlias/MustAlias or
1110  // there must be an operation on the PHIs within the PHIs' value cycle
1111  // that causes a MayAlias.
1112  // Pretend the phis do not alias.
1113  AliasResult Alias = NoAlias;
1114  assert(AliasCache.count(Locs) &&
1115  "There must exist an entry for the phi node");
1116  AliasResult OrigAliasResult = AliasCache[Locs];
1117  AliasCache[Locs] = NoAlias;
1118 
1119  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1120  AliasResult ThisAlias =
1121  aliasCheck(PN->getIncomingValue(i), PNSize, PNTBAAInfo,
1122  PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)),
1123  V2Size, V2TBAAInfo);
1124  Alias = MergeAliasResults(ThisAlias, Alias);
1125  if (Alias == MayAlias)
1126  break;
1127  }
1128 
1129  // Reset if speculation failed.
1130  if (Alias != NoAlias)
1131  AliasCache[Locs] = OrigAliasResult;
1132 
1133  return Alias;
1134  }
1135 
1136  SmallPtrSet<Value*, 4> UniqueSrc;
1137  SmallVector<Value*, 4> V1Srcs;
1138  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1139  Value *PV1 = PN->getIncomingValue(i);
1140  if (isa<PHINode>(PV1))
1141  // If any of the source itself is a PHI, return MayAlias conservatively
1142  // to avoid compile time explosion. The worst possible case is if both
1143  // sides are PHI nodes. In which case, this is O(m x n) time where 'm'
1144  // and 'n' are the number of PHI sources.
1145  return MayAlias;
1146  if (UniqueSrc.insert(PV1))
1147  V1Srcs.push_back(PV1);
1148  }
1149 
1150  AliasResult Alias = aliasCheck(V2, V2Size, V2TBAAInfo,
1151  V1Srcs[0], PNSize, PNTBAAInfo);
1152  // Early exit if the check of the first PHI source against V2 is MayAlias.
1153  // Other results are not possible.
1154  if (Alias == MayAlias)
1155  return MayAlias;
1156 
1157  // If all sources of the PHI node NoAlias or MustAlias V2, then returns
1158  // NoAlias / MustAlias. Otherwise, returns MayAlias.
1159  for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) {
1160  Value *V = V1Srcs[i];
1161 
1162  AliasResult ThisAlias = aliasCheck(V2, V2Size, V2TBAAInfo,
1163  V, PNSize, PNTBAAInfo);
1164  Alias = MergeAliasResults(ThisAlias, Alias);
1165  if (Alias == MayAlias)
1166  break;
1167  }
1168 
1169  return Alias;
1170 }
1171 
1172 // aliasCheck - Provide a bunch of ad-hoc rules to disambiguate in common cases,
1173 // such as array references.
1174 //
1176 BasicAliasAnalysis::aliasCheck(const Value *V1, uint64_t V1Size,
1177  const MDNode *V1TBAAInfo,
1178  const Value *V2, uint64_t V2Size,
1179  const MDNode *V2TBAAInfo) {
1180  // If either of the memory references is empty, it doesn't matter what the
1181  // pointer values are.
1182  if (V1Size == 0 || V2Size == 0)
1183  return NoAlias;
1184 
1185  // Strip off any casts if they exist.
1186  V1 = V1->stripPointerCasts();
1187  V2 = V2->stripPointerCasts();
1188 
1189  // Are we checking for alias of the same value?
1190  if (V1 == V2) return MustAlias;
1191 
1192  if (!V1->getType()->isPointerTy() || !V2->getType()->isPointerTy())
1193  return NoAlias; // Scalars cannot alias each other
1194 
1195  // Figure out what objects these things are pointing to if we can.
1196  const Value *O1 = GetUnderlyingObject(V1, TD);
1197  const Value *O2 = GetUnderlyingObject(V2, TD);
1198 
1199  // Null values in the default address space don't point to any object, so they
1200  // don't alias any other pointer.
1201  if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O1))
1202  if (CPN->getType()->getAddressSpace() == 0)
1203  return NoAlias;
1204  if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O2))
1205  if (CPN->getType()->getAddressSpace() == 0)
1206  return NoAlias;
1207 
1208  if (O1 != O2) {
1209  // If V1/V2 point to two different objects we know that we have no alias.
1210  if (isIdentifiedObject(O1) && isIdentifiedObject(O2))
1211  return NoAlias;
1212 
1213  // Constant pointers can't alias with non-const isIdentifiedObject objects.
1214  if ((isa<Constant>(O1) && isIdentifiedObject(O2) && !isa<Constant>(O2)) ||
1215  (isa<Constant>(O2) && isIdentifiedObject(O1) && !isa<Constant>(O1)))
1216  return NoAlias;
1217 
1218  // Function arguments can't alias with things that are known to be
1219  // unambigously identified at the function level.
1220  if ((isa<Argument>(O1) && isIdentifiedFunctionLocal(O2)) ||
1221  (isa<Argument>(O2) && isIdentifiedFunctionLocal(O1)))
1222  return NoAlias;
1223 
1224  // Most objects can't alias null.
1225  if ((isa<ConstantPointerNull>(O2) && isKnownNonNull(O1)) ||
1226  (isa<ConstantPointerNull>(O1) && isKnownNonNull(O2)))
1227  return NoAlias;
1228 
1229  // If one pointer is the result of a call/invoke or load and the other is a
1230  // non-escaping local object within the same function, then we know the
1231  // object couldn't escape to a point where the call could return it.
1232  //
1233  // Note that if the pointers are in different functions, there are a
1234  // variety of complications. A call with a nocapture argument may still
1235  // temporary store the nocapture argument's value in a temporary memory
1236  // location if that memory location doesn't escape. Or it may pass a
1237  // nocapture value to other functions as long as they don't capture it.
1239  return NoAlias;
1241  return NoAlias;
1242  }
1243 
1244  // If the size of one access is larger than the entire object on the other
1245  // side, then we know such behavior is undefined and can assume no alias.
1246  if (TD)
1247  if ((V1Size != UnknownSize && isObjectSmallerThan(O2, V1Size, *TD, *TLI)) ||
1248  (V2Size != UnknownSize && isObjectSmallerThan(O1, V2Size, *TD, *TLI)))
1249  return NoAlias;
1250 
1251  // Check the cache before climbing up use-def chains. This also terminates
1252  // otherwise infinitely recursive queries.
1253  LocPair Locs(Location(V1, V1Size, V1TBAAInfo),
1254  Location(V2, V2Size, V2TBAAInfo));
1255  if (V1 > V2)
1256  std::swap(Locs.first, Locs.second);
1257  std::pair<AliasCacheTy::iterator, bool> Pair =
1258  AliasCache.insert(std::make_pair(Locs, MayAlias));
1259  if (!Pair.second)
1260  return Pair.first->second;
1261 
1262  // FIXME: This isn't aggressively handling alias(GEP, PHI) for example: if the
1263  // GEP can't simplify, we don't even look at the PHI cases.
1264  if (!isa<GEPOperator>(V1) && isa<GEPOperator>(V2)) {
1265  std::swap(V1, V2);
1266  std::swap(V1Size, V2Size);
1267  std::swap(O1, O2);
1268  std::swap(V1TBAAInfo, V2TBAAInfo);
1269  }
1270  if (const GEPOperator *GV1 = dyn_cast<GEPOperator>(V1)) {
1271  AliasResult Result = aliasGEP(GV1, V1Size, V1TBAAInfo, V2, V2Size, V2TBAAInfo, O1, O2);
1272  if (Result != MayAlias) return AliasCache[Locs] = Result;
1273  }
1274 
1275  if (isa<PHINode>(V2) && !isa<PHINode>(V1)) {
1276  std::swap(V1, V2);
1277  std::swap(V1Size, V2Size);
1278  std::swap(V1TBAAInfo, V2TBAAInfo);
1279  }
1280  if (const PHINode *PN = dyn_cast<PHINode>(V1)) {
1281  AliasResult Result = aliasPHI(PN, V1Size, V1TBAAInfo,
1282  V2, V2Size, V2TBAAInfo);
1283  if (Result != MayAlias) return AliasCache[Locs] = Result;
1284  }
1285 
1286  if (isa<SelectInst>(V2) && !isa<SelectInst>(V1)) {
1287  std::swap(V1, V2);
1288  std::swap(V1Size, V2Size);
1289  std::swap(V1TBAAInfo, V2TBAAInfo);
1290  }
1291  if (const SelectInst *S1 = dyn_cast<SelectInst>(V1)) {
1292  AliasResult Result = aliasSelect(S1, V1Size, V1TBAAInfo,
1293  V2, V2Size, V2TBAAInfo);
1294  if (Result != MayAlias) return AliasCache[Locs] = Result;
1295  }
1296 
1297  // If both pointers are pointing into the same object and one of them
1298  // accesses is accessing the entire object, then the accesses must
1299  // overlap in some way.
1300  if (TD && O1 == O2)
1301  if ((V1Size != UnknownSize && isObjectSize(O1, V1Size, *TD, *TLI)) ||
1302  (V2Size != UnknownSize && isObjectSize(O2, V2Size, *TD, *TLI)))
1303  return AliasCache[Locs] = PartialAlias;
1304 
1305  AliasResult Result =
1306  AliasAnalysis::alias(Location(V1, V1Size, V1TBAAInfo),
1307  Location(V2, V2Size, V2TBAAInfo));
1308  return AliasCache[Locs] = Result;
1309 }
Basic Alias Analysis(stateless AA impl)"
Pointers differ, but pointees overlap.
Basic Alias false
virtual bool pointsToConstantMemory(const Location &Loc, bool OrLocal=false)
static PassRegistry * getPassRegistry()
LLVM Argument representation.
Definition: Argument.h:35
ModRefResult getModRefInfo(const Instruction *I, const Location &Loc)
bool onlyReadsMemory() const
Determine if the function does not access or only reads memory.
Definition: Function.h:246
unsigned getNumParams() const
Definition: DerivedTypes.h:133
IterTy arg_end() const
Definition: CallSite.h:143
Intrinsic::ID getIntrinsicID() const
Definition: IntrinsicInst.h:43
static const Value * DecomposeGEPExpression(const Value *V, int64_t &BaseOffs, SmallVectorImpl< VariableGEPIndex > &VarIndices, const DataLayout *TD)
enable_if_c<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:266
bool MaskedValueIsZero(Value *V, const APInt &Mask, const DataLayout *TD=0, unsigned Depth=0)
static bool isEscapeSource(const Value *V)
bool insert(PtrType Ptr)
Definition: SmallPtrSet.h:253
bool isKnownNonNull(const Value *V, const TargetLibraryInfo *TLI=0)
uint64_t getLimitedValue(uint64_t Limit=~0ULL) const
Definition: APInt.h:408
MDNode - a tuple of other values.
Definition: Metadata.h:69
F(f)
bool isNoAliasCall(const Value *V)
op_iterator op_begin()
Definition: User.h:116
ValTy * getArgument(unsigned ArgNo) const
Definition: CallSite.h:111
Type * getPointerElementType() const
Definition: Type.h:373
StringRef getName() const
Definition: Value.cpp:167
Value * GetUnderlyingObject(Value *V, const DataLayout *TD=0, unsigned MaxLookup=6)
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:167
const StructLayout * getStructLayout(StructType *Ty) const
Definition: DataLayout.cpp:445
bool has(LibFunc::Func F) const
T LLVM_ATTRIBUTE_UNUSED_RESULT pop_back_val()
Definition: SmallVector.h:430
Definition: Use.h:60
static bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &TD, const TargetLibraryInfo &TLI)
static AliasAnalysis::AliasResult MergeAliasResults(AliasAnalysis::AliasResult A, AliasAnalysis::AliasResult B)
ID
LLVM Calling Convention Representation.
Definition: CallingConv.h:26
bool isIdentifiedObject(const Value *V)
static bool isIdentifiedFunctionLocal(const Value *V)
bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const
Definition: SmallVector.h:56
ImmutablePass * createBasicAliasAnalysisPass()
INITIALIZE_AG_PASS_BEGIN(BasicAliasAnalysis, AliasAnalysis,"basicaa","Basic Alias Analysis (stateless AA impl)", false, true, false) INITIALIZE_AG_PASS_END(BasicAliasAnalysis
static bool areVarIndicesEqual(SmallVectorImpl< VariableGEPIndex > &Indices1, SmallVectorImpl< VariableGEPIndex > &Indices2)
bool doesNotAccessMemory() const
Determine if the function does not access memory.
Definition: Function.h:237
unsigned getNumIncomingValues() const
uint64_t getElementOffset(unsigned Idx) const
Definition: DataLayout.h:442
void memset_pattern16(void *b, const void *pattern16, size_t len);
User::const_op_iterator arg_iterator
Definition: CallSite.h:133
Type * getParamType(unsigned i) const
Parameter type accessors.
Definition: DerivedTypes.h:128
APInt LLVM_ATTRIBUTE_UNUSED_RESULT trunc(unsigned width) const
Truncate to new width.
Definition: APInt.cpp:919
InstrTy * getInstruction() const
Definition: CallSite.h:79
unsigned getIntrinsicID() const LLVM_READONLY
Definition: Function.cpp:371
virtual AliasResult alias(const Location &LocA, const Location &LocB)
const Value * getCondition() const
int64_t getSExtValue() const
Get sign extended value.
Definition: APInt.h:1318
APInt Or(const APInt &LHS, const APInt &RHS)
Bitwise OR function for APInt.
Definition: APInt.h:1845
#define ModRefBehavior
op_iterator op_end()
Definition: User.h:118
BasicBlock * getIncomingBlock(unsigned i) const
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1252
Value * getOperand(unsigned i) const
Definition: User.h:88
static void GetIndexDifference(SmallVectorImpl< VariableGEPIndex > &Dest, const SmallVectorImpl< VariableGEPIndex > &Src)
static bool isNonEscapingLocalObject(const Value *V)
bool isPointerTy() const
Definition: Type.h:220
iterator erase(iterator I)
Definition: SmallVector.h:478
Value * SimplifyInstruction(Instruction *I, const DataLayout *TD=0, const TargetLibraryInfo *TLI=0, const DominatorTree *DT=0)
bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, bool StoreCaptures)
void initializeBasicAliasAnalysisPass(PassRegistry &)
bool onlyReadsMemory() const
Determine if the call does not access or only reads memory.
Definition: CallSite.h:224
virtual ModRefBehavior getModRefBehavior(ImmutableCallSite CS)
getModRefBehavior - Return the behavior when calling the given call site.
const Value * getTrueValue() const
unsigned getIntegerBitWidth() const
Definition: Type.cpp:178
Class for constant integers.
Definition: Constants.h:51
bool doesNotAccessMemory() const
Determine if the call does not access memory.
Definition: CallSite.h:216
bool isByValArgument(unsigned ArgNo) const
Determine whether this argument is passed by value.
Definition: CallSite.h:256
Value * getIncomingValue(unsigned i) const
uint64_t getTypeAllocSize(Type *Ty) const
Definition: DataLayout.h:326
Type * getType() const
Definition: Value.h:111
MDNode * getMetadata(unsigned KindID) const
Definition: Instruction.h:140
static Value * GetLinearExpression(Value *V, APInt &Scale, APInt &Offset, ExtensionKind &Extension, const DataLayout &TD, unsigned Depth)
bool hasAllZeroIndices() const
Definition: Operator.h:415
Value * stripPointerCasts()
Strips off any unneeded pointer casts, all-zero GEPs and aliases from the specified value...
Definition: Value.cpp:385
bool doesNotCapture(unsigned ArgNo) const
Determine whether this argument is not captured.
Definition: CallSite.h:251
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:591
Value * getArgOperand(unsigned i) const
Class for arbitrary precision integers.
Definition: APInt.h:75
static bool notDifferentParent(const Value *O1, const Value *O2)
bool isIntegerTy() const
Definition: Type.h:196
unsigned getOpcode() const
Definition: Operator.h:51
bool operator!=(uint64_t V1, const APInt &V2)
Definition: APInt.h:1686
static bool isObjectSmallerThan(const Value *V, uint64_t Size, const DataLayout &TD, const TargetLibraryInfo &TLI)
ImmutableCallSite - establish a view to a call site for examination.
Definition: CallSite.h:318
#define I(x, y, z)
Definition: MD5.cpp:54
FunctionType * getFunctionType() const
Definition: Function.cpp:171
unsigned getPointerSizeInBits(unsigned AS=0) const
Definition: DataLayout.h:271
unsigned getPointerAddressSpace() const
Definition: Operator.h:400
unsigned getPrimitiveSizeInBits() const
Definition: Type.cpp:117
uint64_t getTypeStoreSize(Type *Ty) const
Definition: DataLayout.h:311
static uint64_t const UnknownSize
Definition: AliasAnalysis.h:84
IterTy arg_begin() const
Definition: CallSite.h:137
bool isVarArg() const
Definition: DerivedTypes.h:120
Module * getParent()
Definition: GlobalValue.h:286
LLVM Value Representation.
Definition: Value.h:66
static const Function * getParent(const Value *V)
bool isSized() const
Definition: Type.h:278
#define INITIALIZE_AG_PASS_END(passName, agName, arg, n, cfg, analysis, def)
Definition: PassSupport.h:289
const Value * getFalseValue() const
APInt LLVM_ATTRIBUTE_UNUSED_RESULT zext(unsigned width) const
Zero extend to a new width.
Definition: APInt.cpp:983
bool isNoAliasArgument(const Value *V)
bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout *DL, const TargetLibraryInfo *TLI, bool RoundToAlign=false)
Compute the size of the object pointed by Ptr. Returns true and the object size in Size if successful...
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1684
const BasicBlock * getParent() const
Definition: Instruction.h:52
INITIALIZE_PASS(GlobalMerge,"global-merge","Global Merge", false, false) bool GlobalMerge const DataLayout * TD
FunTy * getCalledFunction() const
Definition: CallSite.h:93
gep_type_iterator gep_type_begin(const User *GEP)
Basic Alias true