LLVM  6.0.0svn
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 
17 #include "llvm/ADT/APInt.h"
18 #include "llvm/ADT/SmallPtrSet.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/Statistic.h"
23 #include "llvm/Analysis/CFG.h"
26 #include "llvm/Analysis/LoopInfo.h"
31 #include "llvm/IR/Argument.h"
32 #include "llvm/IR/Attributes.h"
33 #include "llvm/IR/CallSite.h"
34 #include "llvm/IR/Constant.h"
35 #include "llvm/IR/Constants.h"
36 #include "llvm/IR/DataLayout.h"
37 #include "llvm/IR/DerivedTypes.h"
38 #include "llvm/IR/Dominators.h"
39 #include "llvm/IR/Function.h"
41 #include "llvm/IR/GlobalAlias.h"
42 #include "llvm/IR/GlobalVariable.h"
43 #include "llvm/IR/InstrTypes.h"
44 #include "llvm/IR/Instruction.h"
45 #include "llvm/IR/Instructions.h"
46 #include "llvm/IR/IntrinsicInst.h"
47 #include "llvm/IR/Intrinsics.h"
48 #include "llvm/IR/Metadata.h"
49 #include "llvm/IR/Operator.h"
50 #include "llvm/IR/Type.h"
51 #include "llvm/IR/User.h"
52 #include "llvm/IR/Value.h"
53 #include "llvm/Pass.h"
54 #include "llvm/Support/Casting.h"
56 #include "llvm/Support/Compiler.h"
57 #include "llvm/Support/KnownBits.h"
58 #include <cassert>
59 #include <cstdint>
60 #include <cstdlib>
61 #include <utility>
62 
63 #define DEBUG_TYPE "basicaa"
64 
65 using namespace llvm;
66 
67 /// Enable analysis of recursive PHI nodes.
68 static cl::opt<bool> EnableRecPhiAnalysis("basicaa-recphi", cl::Hidden,
69  cl::init(false));
70 /// SearchLimitReached / SearchTimes shows how often the limit of
71 /// to decompose GEPs is reached. It will affect the precision
72 /// of basic alias analysis.
73 STATISTIC(SearchLimitReached, "Number of times the limit to "
74  "decompose GEPs is reached");
75 STATISTIC(SearchTimes, "Number of times a GEP is decomposed");
76 
77 /// Cutoff after which to stop analysing a set of phi nodes potentially involved
78 /// in a cycle. Because we are analysing 'through' phi nodes, we need to be
79 /// careful with value equivalence. We use reachability to make sure a value
80 /// cannot be involved in a cycle.
82 
83 // The max limit of the search depth in DecomposeGEPExpression() and
84 // GetUnderlyingObject(), both functions need to use the same search
85 // depth otherwise the algorithm in aliasGEP will assert.
86 static const unsigned MaxLookupSearchDepth = 6;
87 
90  // We don't care if this analysis itself is preserved, it has no state. But
91  // we need to check that the analyses it depends on have been. Note that we
92  // may be created without handles to some analyses and in that case don't
93  // depend on them.
94  if (Inv.invalidate<AssumptionAnalysis>(F, PA) ||
95  (DT && Inv.invalidate<DominatorTreeAnalysis>(F, PA)) ||
96  (LI && Inv.invalidate<LoopAnalysis>(F, PA)))
97  return true;
98 
99  // Otherwise this analysis result remains valid.
100  return false;
101 }
102 
103 //===----------------------------------------------------------------------===//
104 // Useful predicates
105 //===----------------------------------------------------------------------===//
106 
107 /// Returns true if the pointer is to a function-local object that never
108 /// escapes from the function.
109 static bool isNonEscapingLocalObject(const Value *V) {
110  // If this is a local allocation, check to see if it escapes.
111  if (isa<AllocaInst>(V) || isNoAliasCall(V))
112  // Set StoreCaptures to True so that we can assume in our callers that the
113  // pointer is not the result of a load instruction. Currently
114  // PointerMayBeCaptured doesn't have any special analysis for the
115  // StoreCaptures=false case; if it did, our callers could be refined to be
116  // more precise.
117  return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true);
118 
119  // If this is an argument that corresponds to a byval or noalias argument,
120  // then it has not escaped before entering the function. Check if it escapes
121  // inside the function.
122  if (const Argument *A = dyn_cast<Argument>(V))
123  if (A->hasByValAttr() || A->hasNoAliasAttr())
124  // Note even if the argument is marked nocapture, we still need to check
125  // for copies made inside the function. The nocapture attribute only
126  // specifies that there are no copies made that outlive the function.
127  return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true);
128 
129  return false;
130 }
131 
132 /// Returns true if the pointer is one which would have been considered an
133 /// escape by isNonEscapingLocalObject.
134 static bool isEscapeSource(const Value *V) {
135  if (isa<CallInst>(V) || isa<InvokeInst>(V) || isa<Argument>(V))
136  return true;
137 
138  // The load case works because isNonEscapingLocalObject considers all
139  // stores to be escapes (it passes true for the StoreCaptures argument
140  // to PointerMayBeCaptured).
141  if (isa<LoadInst>(V))
142  return true;
143 
144  return false;
145 }
146 
147 /// Returns the size of the object specified by V or UnknownSize if unknown.
148 static uint64_t getObjectSize(const Value *V, const DataLayout &DL,
149  const TargetLibraryInfo &TLI,
150  bool RoundToAlign = false) {
151  uint64_t Size;
152  ObjectSizeOpts Opts;
153  Opts.RoundToAlign = RoundToAlign;
154  if (getObjectSize(V, Size, DL, &TLI, Opts))
155  return Size;
157 }
158 
159 /// Returns true if we can prove that the object specified by V is smaller than
160 /// Size.
161 static bool isObjectSmallerThan(const Value *V, uint64_t Size,
162  const DataLayout &DL,
163  const TargetLibraryInfo &TLI) {
164  // Note that the meanings of the "object" are slightly different in the
165  // following contexts:
166  // c1: llvm::getObjectSize()
167  // c2: llvm.objectsize() intrinsic
168  // c3: isObjectSmallerThan()
169  // c1 and c2 share the same meaning; however, the meaning of "object" in c3
170  // refers to the "entire object".
171  //
172  // Consider this example:
173  // char *p = (char*)malloc(100)
174  // char *q = p+80;
175  //
176  // In the context of c1 and c2, the "object" pointed by q refers to the
177  // stretch of memory of q[0:19]. So, getObjectSize(q) should return 20.
178  //
179  // However, in the context of c3, the "object" refers to the chunk of memory
180  // being allocated. So, the "object" has 100 bytes, and q points to the middle
181  // the "object". In case q is passed to isObjectSmallerThan() as the 1st
182  // parameter, before the llvm::getObjectSize() is called to get the size of
183  // entire object, we should:
184  // - either rewind the pointer q to the base-address of the object in
185  // question (in this case rewind to p), or
186  // - just give up. It is up to caller to make sure the pointer is pointing
187  // to the base address the object.
188  //
189  // We go for 2nd option for simplicity.
190  if (!isIdentifiedObject(V))
191  return false;
192 
193  // This function needs to use the aligned object size because we allow
194  // reads a bit past the end given sufficient alignment.
195  uint64_t ObjectSize = getObjectSize(V, DL, TLI, /*RoundToAlign*/ true);
196 
197  return ObjectSize != MemoryLocation::UnknownSize && ObjectSize < Size;
198 }
199 
200 /// Returns true if we can prove that the object specified by V has size Size.
201 static bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &DL,
202  const TargetLibraryInfo &TLI) {
203  uint64_t ObjectSize = getObjectSize(V, DL, TLI);
204  return ObjectSize != MemoryLocation::UnknownSize && ObjectSize == Size;
205 }
206 
207 //===----------------------------------------------------------------------===//
208 // GetElementPtr Instruction Decomposition and Analysis
209 //===----------------------------------------------------------------------===//
210 
211 /// Analyzes the specified value as a linear expression: "A*V + B", where A and
212 /// B are constant integers.
213 ///
214 /// Returns the scale and offset values as APInts and return V as a Value*, and
215 /// return whether we looked through any sign or zero extends. The incoming
216 /// Value is known to have IntegerType, and it may already be sign or zero
217 /// extended.
218 ///
219 /// Note that this looks through extends, so the high bits may not be
220 /// represented in the result.
221 /*static*/ const Value *BasicAAResult::GetLinearExpression(
222  const Value *V, APInt &Scale, APInt &Offset, unsigned &ZExtBits,
223  unsigned &SExtBits, const DataLayout &DL, unsigned Depth,
224  AssumptionCache *AC, DominatorTree *DT, bool &NSW, bool &NUW) {
225  assert(V->getType()->isIntegerTy() && "Not an integer value");
226 
227  // Limit our recursion depth.
228  if (Depth == 6) {
229  Scale = 1;
230  Offset = 0;
231  return V;
232  }
233 
234  if (const ConstantInt *Const = dyn_cast<ConstantInt>(V)) {
235  // If it's a constant, just convert it to an offset and remove the variable.
236  // If we've been called recursively, the Offset bit width will be greater
237  // than the constant's (the Offset's always as wide as the outermost call),
238  // so we'll zext here and process any extension in the isa<SExtInst> &
239  // isa<ZExtInst> cases below.
240  Offset += Const->getValue().zextOrSelf(Offset.getBitWidth());
241  assert(Scale == 0 && "Constant values don't have a scale");
242  return V;
243  }
244 
245  if (const BinaryOperator *BOp = dyn_cast<BinaryOperator>(V)) {
246  if (ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) {
247  // If we've been called recursively, then Offset and Scale will be wider
248  // than the BOp operands. We'll always zext it here as we'll process sign
249  // extensions below (see the isa<SExtInst> / isa<ZExtInst> cases).
250  APInt RHS = RHSC->getValue().zextOrSelf(Offset.getBitWidth());
251 
252  switch (BOp->getOpcode()) {
253  default:
254  // We don't understand this instruction, so we can't decompose it any
255  // further.
256  Scale = 1;
257  Offset = 0;
258  return V;
259  case Instruction::Or:
260  // X|C == X+C if all the bits in C are unset in X. Otherwise we can't
261  // analyze it.
262  if (!MaskedValueIsZero(BOp->getOperand(0), RHSC->getValue(), DL, 0, AC,
263  BOp, DT)) {
264  Scale = 1;
265  Offset = 0;
266  return V;
267  }
269  case Instruction::Add:
270  V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits,
271  SExtBits, DL, Depth + 1, AC, DT, NSW, NUW);
272  Offset += RHS;
273  break;
274  case Instruction::Sub:
275  V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits,
276  SExtBits, DL, Depth + 1, AC, DT, NSW, NUW);
277  Offset -= RHS;
278  break;
279  case Instruction::Mul:
280  V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits,
281  SExtBits, DL, Depth + 1, AC, DT, NSW, NUW);
282  Offset *= RHS;
283  Scale *= RHS;
284  break;
285  case Instruction::Shl:
286  V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits,
287  SExtBits, DL, Depth + 1, AC, DT, NSW, NUW);
288  Offset <<= RHS.getLimitedValue();
289  Scale <<= RHS.getLimitedValue();
290  // the semantics of nsw and nuw for left shifts don't match those of
291  // multiplications, so we won't propagate them.
292  NSW = NUW = false;
293  return V;
294  }
295 
296  if (isa<OverflowingBinaryOperator>(BOp)) {
297  NUW &= BOp->hasNoUnsignedWrap();
298  NSW &= BOp->hasNoSignedWrap();
299  }
300  return V;
301  }
302  }
303 
304  // Since GEP indices are sign extended anyway, we don't care about the high
305  // bits of a sign or zero extended value - just scales and offsets. The
306  // extensions have to be consistent though.
307  if (isa<SExtInst>(V) || isa<ZExtInst>(V)) {
308  Value *CastOp = cast<CastInst>(V)->getOperand(0);
309  unsigned NewWidth = V->getType()->getPrimitiveSizeInBits();
310  unsigned SmallWidth = CastOp->getType()->getPrimitiveSizeInBits();
311  unsigned OldZExtBits = ZExtBits, OldSExtBits = SExtBits;
312  const Value *Result =
313  GetLinearExpression(CastOp, Scale, Offset, ZExtBits, SExtBits, DL,
314  Depth + 1, AC, DT, NSW, NUW);
315 
316  // zext(zext(%x)) == zext(%x), and similarly for sext; we'll handle this
317  // by just incrementing the number of bits we've extended by.
318  unsigned ExtendedBy = NewWidth - SmallWidth;
319 
320  if (isa<SExtInst>(V) && ZExtBits == 0) {
321  // sext(sext(%x, a), b) == sext(%x, a + b)
322 
323  if (NSW) {
324  // We haven't sign-wrapped, so it's valid to decompose sext(%x + c)
325  // into sext(%x) + sext(c). We'll sext the Offset ourselves:
326  unsigned OldWidth = Offset.getBitWidth();
327  Offset = Offset.trunc(SmallWidth).sext(NewWidth).zextOrSelf(OldWidth);
328  } else {
329  // We may have signed-wrapped, so don't decompose sext(%x + c) into
330  // sext(%x) + sext(c)
331  Scale = 1;
332  Offset = 0;
333  Result = CastOp;
334  ZExtBits = OldZExtBits;
335  SExtBits = OldSExtBits;
336  }
337  SExtBits += ExtendedBy;
338  } else {
339  // sext(zext(%x, a), b) = zext(zext(%x, a), b) = zext(%x, a + b)
340 
341  if (!NUW) {
342  // We may have unsigned-wrapped, so don't decompose zext(%x + c) into
343  // zext(%x) + zext(c)
344  Scale = 1;
345  Offset = 0;
346  Result = CastOp;
347  ZExtBits = OldZExtBits;
348  SExtBits = OldSExtBits;
349  }
350  ZExtBits += ExtendedBy;
351  }
352 
353  return Result;
354  }
355 
356  Scale = 1;
357  Offset = 0;
358  return V;
359 }
360 
361 /// To ensure a pointer offset fits in an integer of size PointerSize
362 /// (in bits) when that size is smaller than 64. This is an issue in
363 /// particular for 32b programs with negative indices that rely on two's
364 /// complement wrap-arounds for precise alias information.
365 static int64_t adjustToPointerSize(int64_t Offset, unsigned PointerSize) {
366  assert(PointerSize <= 64 && "Invalid PointerSize!");
367  unsigned ShiftBits = 64 - PointerSize;
368  return (int64_t)((uint64_t)Offset << ShiftBits) >> ShiftBits;
369 }
370 
371 /// If V is a symbolic pointer expression, decompose it into a base pointer
372 /// with a constant offset and a number of scaled symbolic offsets.
373 ///
374 /// The scaled symbolic offsets (represented by pairs of a Value* and a scale
375 /// in the VarIndices vector) are Value*'s that are known to be scaled by the
376 /// specified amount, but which may have other unrepresented high bits. As
377 /// such, the gep cannot necessarily be reconstructed from its decomposed form.
378 ///
379 /// When DataLayout is around, this function is capable of analyzing everything
380 /// that GetUnderlyingObject can look through. To be able to do that
381 /// GetUnderlyingObject and DecomposeGEPExpression must use the same search
382 /// depth (MaxLookupSearchDepth). When DataLayout not is around, it just looks
383 /// through pointer casts.
384 bool BasicAAResult::DecomposeGEPExpression(const Value *V,
385  DecomposedGEP &Decomposed, const DataLayout &DL, AssumptionCache *AC,
386  DominatorTree *DT) {
387  // Limit recursion depth to limit compile time in crazy cases.
388  unsigned MaxLookup = MaxLookupSearchDepth;
389  SearchTimes++;
390 
391  Decomposed.StructOffset = 0;
392  Decomposed.OtherOffset = 0;
393  Decomposed.VarIndices.clear();
394  do {
395  // See if this is a bitcast or GEP.
396  const Operator *Op = dyn_cast<Operator>(V);
397  if (!Op) {
398  // The only non-operator case we can handle are GlobalAliases.
399  if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
400  if (!GA->isInterposable()) {
401  V = GA->getAliasee();
402  continue;
403  }
404  }
405  Decomposed.Base = V;
406  return false;
407  }
408 
409  if (Op->getOpcode() == Instruction::BitCast ||
410  Op->getOpcode() == Instruction::AddrSpaceCast) {
411  V = Op->getOperand(0);
412  continue;
413  }
414 
415  const GEPOperator *GEPOp = dyn_cast<GEPOperator>(Op);
416  if (!GEPOp) {
417  if (auto CS = ImmutableCallSite(V))
418  if (const Value *RV = CS.getReturnedArgOperand()) {
419  V = RV;
420  continue;
421  }
422 
423  // If it's not a GEP, hand it off to SimplifyInstruction to see if it
424  // can come up with something. This matches what GetUnderlyingObject does.
425  if (const Instruction *I = dyn_cast<Instruction>(V))
426  // TODO: Get a DominatorTree and AssumptionCache and use them here
427  // (these are both now available in this function, but this should be
428  // updated when GetUnderlyingObject is updated). TLI should be
429  // provided also.
430  if (const Value *Simplified =
431  SimplifyInstruction(const_cast<Instruction *>(I), DL)) {
432  V = Simplified;
433  continue;
434  }
435 
436  Decomposed.Base = V;
437  return false;
438  }
439 
440  // Don't attempt to analyze GEPs over unsized objects.
441  if (!GEPOp->getSourceElementType()->isSized()) {
442  Decomposed.Base = V;
443  return false;
444  }
445 
446  unsigned AS = GEPOp->getPointerAddressSpace();
447  // Walk the indices of the GEP, accumulating them into BaseOff/VarIndices.
448  gep_type_iterator GTI = gep_type_begin(GEPOp);
449  unsigned PointerSize = DL.getPointerSizeInBits(AS);
450  // Assume all GEP operands are constants until proven otherwise.
451  bool GepHasConstantOffset = true;
452  for (User::const_op_iterator I = GEPOp->op_begin() + 1, E = GEPOp->op_end();
453  I != E; ++I, ++GTI) {
454  const Value *Index = *I;
455  // Compute the (potentially symbolic) offset in bytes for this index.
456  if (StructType *STy = GTI.getStructTypeOrNull()) {
457  // For a struct, add the member offset.
458  unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue();
459  if (FieldNo == 0)
460  continue;
461 
462  Decomposed.StructOffset +=
463  DL.getStructLayout(STy)->getElementOffset(FieldNo);
464  continue;
465  }
466 
467  // For an array/pointer, add the element offset, explicitly scaled.
468  if (const ConstantInt *CIdx = dyn_cast<ConstantInt>(Index)) {
469  if (CIdx->isZero())
470  continue;
471  Decomposed.OtherOffset +=
472  DL.getTypeAllocSize(GTI.getIndexedType()) * CIdx->getSExtValue();
473  continue;
474  }
475 
476  GepHasConstantOffset = false;
477 
478  uint64_t Scale = DL.getTypeAllocSize(GTI.getIndexedType());
479  unsigned ZExtBits = 0, SExtBits = 0;
480 
481  // If the integer type is smaller than the pointer size, it is implicitly
482  // sign extended to pointer size.
483  unsigned Width = Index->getType()->getIntegerBitWidth();
484  if (PointerSize > Width)
485  SExtBits += PointerSize - Width;
486 
487  // Use GetLinearExpression to decompose the index into a C1*V+C2 form.
488  APInt IndexScale(Width, 0), IndexOffset(Width, 0);
489  bool NSW = true, NUW = true;
490  Index = GetLinearExpression(Index, IndexScale, IndexOffset, ZExtBits,
491  SExtBits, DL, 0, AC, DT, NSW, NUW);
492 
493  // The GEP index scale ("Scale") scales C1*V+C2, yielding (C1*V+C2)*Scale.
494  // This gives us an aggregate computation of (C1*Scale)*V + C2*Scale.
495  Decomposed.OtherOffset += IndexOffset.getSExtValue() * Scale;
496  Scale *= IndexScale.getSExtValue();
497 
498  // If we already had an occurrence of this index variable, merge this
499  // scale into it. For example, we want to handle:
500  // A[x][x] -> x*16 + x*4 -> x*20
501  // This also ensures that 'x' only appears in the index list once.
502  for (unsigned i = 0, e = Decomposed.VarIndices.size(); i != e; ++i) {
503  if (Decomposed.VarIndices[i].V == Index &&
504  Decomposed.VarIndices[i].ZExtBits == ZExtBits &&
505  Decomposed.VarIndices[i].SExtBits == SExtBits) {
506  Scale += Decomposed.VarIndices[i].Scale;
507  Decomposed.VarIndices.erase(Decomposed.VarIndices.begin() + i);
508  break;
509  }
510  }
511 
512  // Make sure that we have a scale that makes sense for this target's
513  // pointer size.
514  Scale = adjustToPointerSize(Scale, PointerSize);
515 
516  if (Scale) {
517  VariableGEPIndex Entry = {Index, ZExtBits, SExtBits,
518  static_cast<int64_t>(Scale)};
519  Decomposed.VarIndices.push_back(Entry);
520  }
521  }
522 
523  // Take care of wrap-arounds
524  if (GepHasConstantOffset) {
525  Decomposed.StructOffset =
526  adjustToPointerSize(Decomposed.StructOffset, PointerSize);
527  Decomposed.OtherOffset =
528  adjustToPointerSize(Decomposed.OtherOffset, PointerSize);
529  }
530 
531  // Analyze the base pointer next.
532  V = GEPOp->getOperand(0);
533  } while (--MaxLookup);
534 
535  // If the chain of expressions is too deep, just return early.
536  Decomposed.Base = V;
537  SearchLimitReached++;
538  return true;
539 }
540 
541 /// Returns whether the given pointer value points to memory that is local to
542 /// the function, with global constants being considered local to all
543 /// functions.
545  bool OrLocal) {
546  assert(Visited.empty() && "Visited must be cleared after use!");
547 
548  unsigned MaxLookup = 8;
550  Worklist.push_back(Loc.Ptr);
551  do {
552  const Value *V = GetUnderlyingObject(Worklist.pop_back_val(), DL);
553  if (!Visited.insert(V).second) {
554  Visited.clear();
555  return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
556  }
557 
558  // An alloca instruction defines local memory.
559  if (OrLocal && isa<AllocaInst>(V))
560  continue;
561 
562  // A global constant counts as local memory for our purposes.
563  if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) {
564  // Note: this doesn't require GV to be "ODR" because it isn't legal for a
565  // global to be marked constant in some modules and non-constant in
566  // others. GV may even be a declaration, not a definition.
567  if (!GV->isConstant()) {
568  Visited.clear();
569  return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
570  }
571  continue;
572  }
573 
574  // If both select values point to local memory, then so does the select.
575  if (const SelectInst *SI = dyn_cast<SelectInst>(V)) {
576  Worklist.push_back(SI->getTrueValue());
577  Worklist.push_back(SI->getFalseValue());
578  continue;
579  }
580 
581  // If all values incoming to a phi node point to local memory, then so does
582  // the phi.
583  if (const PHINode *PN = dyn_cast<PHINode>(V)) {
584  // Don't bother inspecting phi nodes with many operands.
585  if (PN->getNumIncomingValues() > MaxLookup) {
586  Visited.clear();
587  return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
588  }
589  for (Value *IncValue : PN->incoming_values())
590  Worklist.push_back(IncValue);
591  continue;
592  }
593 
594  // Otherwise be conservative.
595  Visited.clear();
596  return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
597  } while (!Worklist.empty() && --MaxLookup);
598 
599  Visited.clear();
600  return Worklist.empty();
601 }
602 
603 /// Returns the behavior when calling the given call site.
605  if (CS.doesNotAccessMemory())
606  // Can't do better than this.
608 
610 
611  // If the callsite knows it only reads memory, don't return worse
612  // than that.
613  if (CS.onlyReadsMemory())
614  Min = FMRB_OnlyReadsMemory;
615  else if (CS.doesNotReadMemory())
617 
618  if (CS.onlyAccessesArgMemory())
620 
621  // If CS has operand bundles then aliasing attributes from the function it
622  // calls do not directly apply to the CallSite. This can be made more
623  // precise in the future.
624  if (!CS.hasOperandBundles())
625  if (const Function *F = CS.getCalledFunction())
626  Min =
628 
629  return Min;
630 }
631 
632 /// Returns the behavior when calling the given function. For use when the call
633 /// site is not known.
635  // If the function declares it doesn't access memory, we can't do better.
636  if (F->doesNotAccessMemory())
638 
640 
641  // If the function declares it only reads memory, go with that.
642  if (F->onlyReadsMemory())
643  Min = FMRB_OnlyReadsMemory;
644  else if (F->doesNotReadMemory())
646 
647  if (F->onlyAccessesArgMemory())
649  else if (F->onlyAccessesInaccessibleMemory())
653 
654  return Min;
655 }
656 
657 /// Returns true if this is a writeonly (i.e Mod only) parameter.
658 static bool isWriteOnlyParam(ImmutableCallSite CS, unsigned ArgIdx,
659  const TargetLibraryInfo &TLI) {
660  if (CS.paramHasAttr(ArgIdx, Attribute::WriteOnly))
661  return true;
662 
663  // We can bound the aliasing properties of memset_pattern16 just as we can
664  // for memcpy/memset. This is particularly important because the
665  // LoopIdiomRecognizer likes to turn loops into calls to memset_pattern16
666  // whenever possible.
667  // FIXME Consider handling this in InferFunctionAttr.cpp together with other
668  // attributes.
669  LibFunc F;
670  if (CS.getCalledFunction() && TLI.getLibFunc(*CS.getCalledFunction(), F) &&
671  F == LibFunc_memset_pattern16 && TLI.has(F))
672  if (ArgIdx == 0)
673  return true;
674 
675  // TODO: memset_pattern4, memset_pattern8
676  // TODO: _chk variants
677  // TODO: strcmp, strcpy
678 
679  return false;
680 }
681 
683  unsigned ArgIdx) {
684  // Checking for known builtin intrinsics and target library functions.
685  if (isWriteOnlyParam(CS, ArgIdx, TLI))
686  return MRI_Mod;
687 
688  if (CS.paramHasAttr(ArgIdx, Attribute::ReadOnly))
689  return MRI_Ref;
690 
691  if (CS.paramHasAttr(ArgIdx, Attribute::ReadNone))
692  return MRI_NoModRef;
693 
694  return AAResultBase::getArgModRefInfo(CS, ArgIdx);
695 }
696 
699  return II && II->getIntrinsicID() == IID;
700 }
701 
702 #ifndef NDEBUG
703 static const Function *getParent(const Value *V) {
704  if (const Instruction *inst = dyn_cast<Instruction>(V)) {
705  if (!inst->getParent())
706  return nullptr;
707  return inst->getParent()->getParent();
708  }
709 
710  if (const Argument *arg = dyn_cast<Argument>(V))
711  return arg->getParent();
712 
713  return nullptr;
714 }
715 
716 static bool notDifferentParent(const Value *O1, const Value *O2) {
717 
718  const Function *F1 = getParent(O1);
719  const Function *F2 = getParent(O2);
720 
721  return !F1 || !F2 || F1 == F2;
722 }
723 #endif
724 
726  const MemoryLocation &LocB) {
727  assert(notDifferentParent(LocA.Ptr, LocB.Ptr) &&
728  "BasicAliasAnalysis doesn't support interprocedural queries.");
729 
730  // If we have a directly cached entry for these locations, we have recursed
731  // through this once, so just return the cached results. Notably, when this
732  // happens, we don't clear the cache.
733  auto CacheIt = AliasCache.find(LocPair(LocA, LocB));
734  if (CacheIt != AliasCache.end())
735  return CacheIt->second;
736 
737  AliasResult Alias = aliasCheck(LocA.Ptr, LocA.Size, LocA.AATags, LocB.Ptr,
738  LocB.Size, LocB.AATags);
739  // AliasCache rarely has more than 1 or 2 elements, always use
740  // shrink_and_clear so it quickly returns to the inline capacity of the
741  // SmallDenseMap if it ever grows larger.
742  // FIXME: This should really be shrink_to_inline_capacity_and_clear().
743  AliasCache.shrink_and_clear();
744  VisitedPhiBBs.clear();
745  return Alias;
746 }
747 
748 /// Checks to see if the specified callsite can clobber the specified memory
749 /// object.
750 ///
751 /// Since we only look at local properties of this function, we really can't
752 /// say much about this query. We do, however, use simple "address taken"
753 /// analysis on local objects.
755  const MemoryLocation &Loc) {
757  "AliasAnalysis query involving multiple functions!");
758 
759  const Value *Object = GetUnderlyingObject(Loc.Ptr, DL);
760 
761  // If this is a tail call and Loc.Ptr points to a stack location, we know that
762  // the tail call cannot access or modify the local stack.
763  // We cannot exclude byval arguments here; these belong to the caller of
764  // the current function not to the current function, and a tail callee
765  // may reference them.
766  if (isa<AllocaInst>(Object))
767  if (const CallInst *CI = dyn_cast<CallInst>(CS.getInstruction()))
768  if (CI->isTailCall())
769  return MRI_NoModRef;
770 
771  // If the pointer is to a locally allocated object that does not escape,
772  // then the call can not mod/ref the pointer unless the call takes the pointer
773  // as an argument, and itself doesn't capture it.
774  if (!isa<Constant>(Object) && CS.getInstruction() != Object &&
775  isNonEscapingLocalObject(Object)) {
776 
777  // Optimistically assume that call doesn't touch Object and check this
778  // assumption in the following loop.
779  ModRefInfo Result = MRI_NoModRef;
780 
781  unsigned OperandNo = 0;
782  for (auto CI = CS.data_operands_begin(), CE = CS.data_operands_end();
783  CI != CE; ++CI, ++OperandNo) {
784  // Only look at the no-capture or byval pointer arguments. If this
785  // pointer were passed to arguments that were neither of these, then it
786  // couldn't be no-capture.
787  if (!(*CI)->getType()->isPointerTy() ||
788  (!CS.doesNotCapture(OperandNo) &&
789  OperandNo < CS.getNumArgOperands() && !CS.isByValArgument(OperandNo)))
790  continue;
791 
792  // Call doesn't access memory through this operand, so we don't care
793  // if it aliases with Object.
794  if (CS.doesNotAccessMemory(OperandNo))
795  continue;
796 
797  // If this is a no-capture pointer argument, see if we can tell that it
798  // is impossible to alias the pointer we're checking.
799  AliasResult AR =
801 
802  // Operand doesnt alias 'Object', continue looking for other aliases
803  if (AR == NoAlias)
804  continue;
805  // Operand aliases 'Object', but call doesn't modify it. Strengthen
806  // initial assumption and keep looking in case if there are more aliases.
807  if (CS.onlyReadsMemory(OperandNo)) {
808  Result = static_cast<ModRefInfo>(Result | MRI_Ref);
809  continue;
810  }
811  // Operand aliases 'Object' but call only writes into it.
812  if (CS.doesNotReadMemory(OperandNo)) {
813  Result = static_cast<ModRefInfo>(Result | MRI_Mod);
814  continue;
815  }
816  // This operand aliases 'Object' and call reads and writes into it.
817  Result = MRI_ModRef;
818  break;
819  }
820 
821  // Early return if we improved mod ref information
822  if (Result != MRI_ModRef)
823  return Result;
824  }
825 
826  // If the CallSite is to malloc or calloc, we can assume that it doesn't
827  // modify any IR visible value. This is only valid because we assume these
828  // routines do not read values visible in the IR. TODO: Consider special
829  // casing realloc and strdup routines which access only their arguments as
830  // well. Or alternatively, replace all of this with inaccessiblememonly once
831  // that's implemented fully.
832  auto *Inst = CS.getInstruction();
833  if (isMallocOrCallocLikeFn(Inst, &TLI)) {
834  // Be conservative if the accessed pointer may alias the allocation -
835  // fallback to the generic handling below.
836  if (getBestAAResults().alias(MemoryLocation(Inst), Loc) == NoAlias)
837  return MRI_NoModRef;
838  }
839 
840  // The semantics of memcpy intrinsics forbid overlap between their respective
841  // operands, i.e., source and destination of any given memcpy must no-alias.
842  // If Loc must-aliases either one of these two locations, then it necessarily
843  // no-aliases the other.
844  if (auto *Inst = dyn_cast<MemCpyInst>(CS.getInstruction())) {
845  AliasResult SrcAA, DestAA;
846 
848  Loc)) == MustAlias)
849  // Loc is exactly the memcpy source thus disjoint from memcpy dest.
850  return MRI_Ref;
851  if ((DestAA = getBestAAResults().alias(MemoryLocation::getForDest(Inst),
852  Loc)) == MustAlias)
853  // The converse case.
854  return MRI_Mod;
855 
856  // It's also possible for Loc to alias both src and dest, or neither.
858  if (SrcAA != NoAlias)
859  rv = static_cast<ModRefInfo>(rv | MRI_Ref);
860  if (DestAA != NoAlias)
861  rv = static_cast<ModRefInfo>(rv | MRI_Mod);
862  return rv;
863  }
864 
865  // While the assume intrinsic is marked as arbitrarily writing so that
866  // proper control dependencies will be maintained, it never aliases any
867  // particular memory location.
868  if (isIntrinsicCall(CS, Intrinsic::assume))
869  return MRI_NoModRef;
870 
871  // Like assumes, guard intrinsics are also marked as arbitrarily writing so
872  // that proper control dependencies are maintained but they never mods any
873  // particular memory location.
874  //
875  // *Unlike* assumes, guard intrinsics are modeled as reading memory since the
876  // heap state at the point the guard is issued needs to be consistent in case
877  // the guard invokes the "deopt" continuation.
878  if (isIntrinsicCall(CS, Intrinsic::experimental_guard))
879  return MRI_Ref;
880 
881  // Like assumes, invariant.start intrinsics were also marked as arbitrarily
882  // writing so that proper control dependencies are maintained but they never
883  // mod any particular memory location visible to the IR.
884  // *Unlike* assumes (which are now modeled as NoModRef), invariant.start
885  // intrinsic is now modeled as reading memory. This prevents hoisting the
886  // invariant.start intrinsic over stores. Consider:
887  // *ptr = 40;
888  // *ptr = 50;
889  // invariant_start(ptr)
890  // int val = *ptr;
891  // print(val);
892  //
893  // This cannot be transformed to:
894  //
895  // *ptr = 40;
896  // invariant_start(ptr)
897  // *ptr = 50;
898  // int val = *ptr;
899  // print(val);
900  //
901  // The transformation will cause the second store to be ignored (based on
902  // rules of invariant.start) and print 40, while the first program always
903  // prints 50.
904  if (isIntrinsicCall(CS, Intrinsic::invariant_start))
905  return MRI_Ref;
906 
907  // The AAResultBase base class has some smarts, lets use them.
908  return AAResultBase::getModRefInfo(CS, Loc);
909 }
910 
912  ImmutableCallSite CS2) {
913  // While the assume intrinsic is marked as arbitrarily writing so that
914  // proper control dependencies will be maintained, it never aliases any
915  // particular memory location.
916  if (isIntrinsicCall(CS1, Intrinsic::assume) ||
917  isIntrinsicCall(CS2, Intrinsic::assume))
918  return MRI_NoModRef;
919 
920  // Like assumes, guard intrinsics are also marked as arbitrarily writing so
921  // that proper control dependencies are maintained but they never mod any
922  // particular memory location.
923  //
924  // *Unlike* assumes, guard intrinsics are modeled as reading memory since the
925  // heap state at the point the guard is issued needs to be consistent in case
926  // the guard invokes the "deopt" continuation.
927 
928  // NB! This function is *not* commutative, so we specical case two
929  // possibilities for guard intrinsics.
930 
931  if (isIntrinsicCall(CS1, Intrinsic::experimental_guard))
932  return getModRefBehavior(CS2) & MRI_Mod ? MRI_Ref : MRI_NoModRef;
933 
934  if (isIntrinsicCall(CS2, Intrinsic::experimental_guard))
935  return getModRefBehavior(CS1) & MRI_Mod ? MRI_Mod : MRI_NoModRef;
936 
937  // The AAResultBase base class has some smarts, lets use them.
938  return AAResultBase::getModRefInfo(CS1, CS2);
939 }
940 
941 /// Provide ad-hoc rules to disambiguate accesses through two GEP operators,
942 /// both having the exact same pointer operand.
944  uint64_t V1Size,
945  const GEPOperator *GEP2,
946  uint64_t V2Size,
947  const DataLayout &DL) {
950  GEP1->getPointerOperandType() == GEP2->getPointerOperandType() &&
951  "Expected GEPs with the same pointer operand");
952 
953  // Try to determine whether GEP1 and GEP2 index through arrays, into structs,
954  // such that the struct field accesses provably cannot alias.
955  // We also need at least two indices (the pointer, and the struct field).
956  if (GEP1->getNumIndices() != GEP2->getNumIndices() ||
957  GEP1->getNumIndices() < 2)
958  return MayAlias;
959 
960  // If we don't know the size of the accesses through both GEPs, we can't
961  // determine whether the struct fields accessed can't alias.
962  if (V1Size == MemoryLocation::UnknownSize ||
963  V2Size == MemoryLocation::UnknownSize)
964  return MayAlias;
965 
966  ConstantInt *C1 =
967  dyn_cast<ConstantInt>(GEP1->getOperand(GEP1->getNumOperands() - 1));
968  ConstantInt *C2 =
969  dyn_cast<ConstantInt>(GEP2->getOperand(GEP2->getNumOperands() - 1));
970 
971  // If the last (struct) indices are constants and are equal, the other indices
972  // might be also be dynamically equal, so the GEPs can alias.
973  if (C1 && C2 && C1->getSExtValue() == C2->getSExtValue())
974  return MayAlias;
975 
976  // Find the last-indexed type of the GEP, i.e., the type you'd get if
977  // you stripped the last index.
978  // On the way, look at each indexed type. If there's something other
979  // than an array, different indices can lead to different final types.
980  SmallVector<Value *, 8> IntermediateIndices;
981 
982  // Insert the first index; we don't need to check the type indexed
983  // through it as it only drops the pointer indirection.
984  assert(GEP1->getNumIndices() > 1 && "Not enough GEP indices to examine");
985  IntermediateIndices.push_back(GEP1->getOperand(1));
986 
987  // Insert all the remaining indices but the last one.
988  // Also, check that they all index through arrays.
989  for (unsigned i = 1, e = GEP1->getNumIndices() - 1; i != e; ++i) {
990  if (!isa<ArrayType>(GetElementPtrInst::getIndexedType(
991  GEP1->getSourceElementType(), IntermediateIndices)))
992  return MayAlias;
993  IntermediateIndices.push_back(GEP1->getOperand(i + 1));
994  }
995 
997  GEP1->getSourceElementType(), IntermediateIndices);
998  StructType *LastIndexedStruct = dyn_cast<StructType>(Ty);
999 
1000  if (isa<SequentialType>(Ty)) {
1001  // We know that:
1002  // - both GEPs begin indexing from the exact same pointer;
1003  // - the last indices in both GEPs are constants, indexing into a sequential
1004  // type (array or pointer);
1005  // - both GEPs only index through arrays prior to that.
1006  //
1007  // Because array indices greater than the number of elements are valid in
1008  // GEPs, unless we know the intermediate indices are identical between
1009  // GEP1 and GEP2 we cannot guarantee that the last indexed arrays don't
1010  // partially overlap. We also need to check that the loaded size matches
1011  // the element size, otherwise we could still have overlap.
1012  const uint64_t ElementSize =
1013  DL.getTypeStoreSize(cast<SequentialType>(Ty)->getElementType());
1014  if (V1Size != ElementSize || V2Size != ElementSize)
1015  return MayAlias;
1016 
1017  for (unsigned i = 0, e = GEP1->getNumIndices() - 1; i != e; ++i)
1018  if (GEP1->getOperand(i + 1) != GEP2->getOperand(i + 1))
1019  return MayAlias;
1020 
1021  // Now we know that the array/pointer that GEP1 indexes into and that
1022  // that GEP2 indexes into must either precisely overlap or be disjoint.
1023  // Because they cannot partially overlap and because fields in an array
1024  // cannot overlap, if we can prove the final indices are different between
1025  // GEP1 and GEP2, we can conclude GEP1 and GEP2 don't alias.
1026 
1027  // If the last indices are constants, we've already checked they don't
1028  // equal each other so we can exit early.
1029  if (C1 && C2)
1030  return NoAlias;
1031  {
1032  Value *GEP1LastIdx = GEP1->getOperand(GEP1->getNumOperands() - 1);
1033  Value *GEP2LastIdx = GEP2->getOperand(GEP2->getNumOperands() - 1);
1034  if (isa<PHINode>(GEP1LastIdx) || isa<PHINode>(GEP2LastIdx)) {
1035  // If one of the indices is a PHI node, be safe and only use
1036  // computeKnownBits so we don't make any assumptions about the
1037  // relationships between the two indices. This is important if we're
1038  // asking about values from different loop iterations. See PR32314.
1039  // TODO: We may be able to change the check so we only do this when
1040  // we definitely looked through a PHINode.
1041  if (GEP1LastIdx != GEP2LastIdx &&
1042  GEP1LastIdx->getType() == GEP2LastIdx->getType()) {
1043  KnownBits Known1 = computeKnownBits(GEP1LastIdx, DL);
1044  KnownBits Known2 = computeKnownBits(GEP2LastIdx, DL);
1045  if (Known1.Zero.intersects(Known2.One) ||
1046  Known1.One.intersects(Known2.Zero))
1047  return NoAlias;
1048  }
1049  } else if (isKnownNonEqual(GEP1LastIdx, GEP2LastIdx, DL))
1050  return NoAlias;
1051  }
1052  return MayAlias;
1053  } else if (!LastIndexedStruct || !C1 || !C2) {
1054  return MayAlias;
1055  }
1056 
1057  // We know that:
1058  // - both GEPs begin indexing from the exact same pointer;
1059  // - the last indices in both GEPs are constants, indexing into a struct;
1060  // - said indices are different, hence, the pointed-to fields are different;
1061  // - both GEPs only index through arrays prior to that.
1062  //
1063  // This lets us determine that the struct that GEP1 indexes into and the
1064  // struct that GEP2 indexes into must either precisely overlap or be
1065  // completely disjoint. Because they cannot partially overlap, indexing into
1066  // different non-overlapping fields of the struct will never alias.
1067 
1068  // Therefore, the only remaining thing needed to show that both GEPs can't
1069  // alias is that the fields are not overlapping.
1070  const StructLayout *SL = DL.getStructLayout(LastIndexedStruct);
1071  const uint64_t StructSize = SL->getSizeInBytes();
1072  const uint64_t V1Off = SL->getElementOffset(C1->getZExtValue());
1073  const uint64_t V2Off = SL->getElementOffset(C2->getZExtValue());
1074 
1075  auto EltsDontOverlap = [StructSize](uint64_t V1Off, uint64_t V1Size,
1076  uint64_t V2Off, uint64_t V2Size) {
1077  return V1Off < V2Off && V1Off + V1Size <= V2Off &&
1078  ((V2Off + V2Size <= StructSize) ||
1079  (V2Off + V2Size - StructSize <= V1Off));
1080  };
1081 
1082  if (EltsDontOverlap(V1Off, V1Size, V2Off, V2Size) ||
1083  EltsDontOverlap(V2Off, V2Size, V1Off, V1Size))
1084  return NoAlias;
1085 
1086  return MayAlias;
1087 }
1088 
1089 // If a we have (a) a GEP and (b) a pointer based on an alloca, and the
1090 // beginning of the object the GEP points would have a negative offset with
1091 // repsect to the alloca, that means the GEP can not alias pointer (b).
1092 // Note that the pointer based on the alloca may not be a GEP. For
1093 // example, it may be the alloca itself.
1094 // The same applies if (b) is based on a GlobalVariable. Note that just being
1095 // based on isIdentifiedObject() is not enough - we need an identified object
1096 // that does not permit access to negative offsets. For example, a negative
1097 // offset from a noalias argument or call can be inbounds w.r.t the actual
1098 // underlying object.
1099 //
1100 // For example, consider:
1101 //
1102 // struct { int f0, int f1, ...} foo;
1103 // foo alloca;
1104 // foo* random = bar(alloca);
1105 // int *f0 = &alloca.f0
1106 // int *f1 = &random->f1;
1107 //
1108 // Which is lowered, approximately, to:
1109 //
1110 // %alloca = alloca %struct.foo
1111 // %random = call %struct.foo* @random(%struct.foo* %alloca)
1112 // %f0 = getelementptr inbounds %struct, %struct.foo* %alloca, i32 0, i32 0
1113 // %f1 = getelementptr inbounds %struct, %struct.foo* %random, i32 0, i32 1
1114 //
1115 // Assume %f1 and %f0 alias. Then %f1 would point into the object allocated
1116 // by %alloca. Since the %f1 GEP is inbounds, that means %random must also
1117 // point into the same object. But since %f0 points to the beginning of %alloca,
1118 // the highest %f1 can be is (%alloca + 3). This means %random can not be higher
1119 // than (%alloca - 1), and so is not inbounds, a contradiction.
1120 bool BasicAAResult::isGEPBaseAtNegativeOffset(const GEPOperator *GEPOp,
1121  const DecomposedGEP &DecompGEP, const DecomposedGEP &DecompObject,
1122  uint64_t ObjectAccessSize) {
1123  // If the object access size is unknown, or the GEP isn't inbounds, bail.
1124  if (ObjectAccessSize == MemoryLocation::UnknownSize || !GEPOp->isInBounds())
1125  return false;
1126 
1127  // We need the object to be an alloca or a globalvariable, and want to know
1128  // the offset of the pointer from the object precisely, so no variable
1129  // indices are allowed.
1130  if (!(isa<AllocaInst>(DecompObject.Base) ||
1131  isa<GlobalVariable>(DecompObject.Base)) ||
1132  !DecompObject.VarIndices.empty())
1133  return false;
1134 
1135  int64_t ObjectBaseOffset = DecompObject.StructOffset +
1136  DecompObject.OtherOffset;
1137 
1138  // If the GEP has no variable indices, we know the precise offset
1139  // from the base, then use it. If the GEP has variable indices, we're in
1140  // a bit more trouble: we can't count on the constant offsets that come
1141  // from non-struct sources, since these can be "rewound" by a negative
1142  // variable offset. So use only offsets that came from structs.
1143  int64_t GEPBaseOffset = DecompGEP.StructOffset;
1144  if (DecompGEP.VarIndices.empty())
1145  GEPBaseOffset += DecompGEP.OtherOffset;
1146 
1147  return (GEPBaseOffset >= ObjectBaseOffset + (int64_t)ObjectAccessSize);
1148 }
1149 
1150 /// Provides a bunch of ad-hoc rules to disambiguate a GEP instruction against
1151 /// another pointer.
1152 ///
1153 /// We know that V1 is a GEP, but we don't know anything about V2.
1154 /// UnderlyingV1 is GetUnderlyingObject(GEP1, DL), UnderlyingV2 is the same for
1155 /// V2.
1156 AliasResult BasicAAResult::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size,
1157  const AAMDNodes &V1AAInfo, const Value *V2,
1158  uint64_t V2Size, const AAMDNodes &V2AAInfo,
1159  const Value *UnderlyingV1,
1160  const Value *UnderlyingV2) {
1161  DecomposedGEP DecompGEP1, DecompGEP2;
1162  bool GEP1MaxLookupReached =
1163  DecomposeGEPExpression(GEP1, DecompGEP1, DL, &AC, DT);
1164  bool GEP2MaxLookupReached =
1165  DecomposeGEPExpression(V2, DecompGEP2, DL, &AC, DT);
1166 
1167  int64_t GEP1BaseOffset = DecompGEP1.StructOffset + DecompGEP1.OtherOffset;
1168  int64_t GEP2BaseOffset = DecompGEP2.StructOffset + DecompGEP2.OtherOffset;
1169 
1170  assert(DecompGEP1.Base == UnderlyingV1 && DecompGEP2.Base == UnderlyingV2 &&
1171  "DecomposeGEPExpression returned a result different from "
1172  "GetUnderlyingObject");
1173 
1174  // If the GEP's offset relative to its base is such that the base would
1175  // fall below the start of the object underlying V2, then the GEP and V2
1176  // cannot alias.
1177  if (!GEP1MaxLookupReached && !GEP2MaxLookupReached &&
1178  isGEPBaseAtNegativeOffset(GEP1, DecompGEP1, DecompGEP2, V2Size))
1179  return NoAlias;
1180  // If we have two gep instructions with must-alias or not-alias'ing base
1181  // pointers, figure out if the indexes to the GEP tell us anything about the
1182  // derived pointer.
1183  if (const GEPOperator *GEP2 = dyn_cast<GEPOperator>(V2)) {
1184  // Check for the GEP base being at a negative offset, this time in the other
1185  // direction.
1186  if (!GEP1MaxLookupReached && !GEP2MaxLookupReached &&
1187  isGEPBaseAtNegativeOffset(GEP2, DecompGEP2, DecompGEP1, V1Size))
1188  return NoAlias;
1189  // Do the base pointers alias?
1190  AliasResult BaseAlias =
1191  aliasCheck(UnderlyingV1, MemoryLocation::UnknownSize, AAMDNodes(),
1192  UnderlyingV2, MemoryLocation::UnknownSize, AAMDNodes());
1193 
1194  // Check for geps of non-aliasing underlying pointers where the offsets are
1195  // identical.
1196  if ((BaseAlias == MayAlias) && V1Size == V2Size) {
1197  // Do the base pointers alias assuming type and size.
1198  AliasResult PreciseBaseAlias = aliasCheck(UnderlyingV1, V1Size, V1AAInfo,
1199  UnderlyingV2, V2Size, V2AAInfo);
1200  if (PreciseBaseAlias == NoAlias) {
1201  // See if the computed offset from the common pointer tells us about the
1202  // relation of the resulting pointer.
1203  // If the max search depth is reached the result is undefined
1204  if (GEP2MaxLookupReached || GEP1MaxLookupReached)
1205  return MayAlias;
1206 
1207  // Same offsets.
1208  if (GEP1BaseOffset == GEP2BaseOffset &&
1209  DecompGEP1.VarIndices == DecompGEP2.VarIndices)
1210  return NoAlias;
1211  }
1212  }
1213 
1214  // If we get a No or May, then return it immediately, no amount of analysis
1215  // will improve this situation.
1216  if (BaseAlias != MustAlias) {
1217  assert(BaseAlias == NoAlias || BaseAlias == MayAlias);
1218  return BaseAlias;
1219  }
1220 
1221  // Otherwise, we have a MustAlias. Since the base pointers alias each other
1222  // exactly, see if the computed offset from the common pointer tells us
1223  // about the relation of the resulting pointer.
1224  // If we know the two GEPs are based off of the exact same pointer (and not
1225  // just the same underlying object), see if that tells us anything about
1226  // the resulting pointers.
1228  GEP2->getPointerOperand()->stripPointerCastsAndBarriers() &&
1229  GEP1->getPointerOperandType() == GEP2->getPointerOperandType()) {
1230  AliasResult R = aliasSameBasePointerGEPs(GEP1, V1Size, GEP2, V2Size, DL);
1231  // If we couldn't find anything interesting, don't abandon just yet.
1232  if (R != MayAlias)
1233  return R;
1234  }
1235 
1236  // If the max search depth is reached, the result is undefined
1237  if (GEP2MaxLookupReached || GEP1MaxLookupReached)
1238  return MayAlias;
1239 
1240  // Subtract the GEP2 pointer from the GEP1 pointer to find out their
1241  // symbolic difference.
1242  GEP1BaseOffset -= GEP2BaseOffset;
1243  GetIndexDifference(DecompGEP1.VarIndices, DecompGEP2.VarIndices);
1244 
1245  } else {
1246  // Check to see if these two pointers are related by the getelementptr
1247  // instruction. If one pointer is a GEP with a non-zero index of the other
1248  // pointer, we know they cannot alias.
1249 
1250  // If both accesses are unknown size, we can't do anything useful here.
1251  if (V1Size == MemoryLocation::UnknownSize &&
1252  V2Size == MemoryLocation::UnknownSize)
1253  return MayAlias;
1254 
1255  AliasResult R = aliasCheck(UnderlyingV1, MemoryLocation::UnknownSize,
1257  V2AAInfo, nullptr, UnderlyingV2);
1258  if (R != MustAlias) {
1259  // If V2 may alias GEP base pointer, conservatively returns MayAlias.
1260  // If V2 is known not to alias GEP base pointer, then the two values
1261  // cannot alias per GEP semantics: "Any memory access must be done through
1262  // a pointer value associated with an address range of the memory access,
1263  // otherwise the behavior is undefined.".
1264  assert(R == NoAlias || R == MayAlias);
1265  return R;
1266  }
1267 
1268  // If the max search depth is reached the result is undefined
1269  if (GEP1MaxLookupReached)
1270  return MayAlias;
1271  }
1272 
1273  // In the two GEP Case, if there is no difference in the offsets of the
1274  // computed pointers, the resultant pointers are a must alias. This
1275  // happens when we have two lexically identical GEP's (for example).
1276  //
1277  // In the other case, if we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2
1278  // must aliases the GEP, the end result is a must alias also.
1279  if (GEP1BaseOffset == 0 && DecompGEP1.VarIndices.empty())
1280  return MustAlias;
1281 
1282  // If there is a constant difference between the pointers, but the difference
1283  // is less than the size of the associated memory object, then we know
1284  // that the objects are partially overlapping. If the difference is
1285  // greater, we know they do not overlap.
1286  if (GEP1BaseOffset != 0 && DecompGEP1.VarIndices.empty()) {
1287  if (GEP1BaseOffset >= 0) {
1288  if (V2Size != MemoryLocation::UnknownSize) {
1289  if ((uint64_t)GEP1BaseOffset < V2Size)
1290  return PartialAlias;
1291  return NoAlias;
1292  }
1293  } else {
1294  // We have the situation where:
1295  // + +
1296  // | BaseOffset |
1297  // ---------------->|
1298  // |-->V1Size |-------> V2Size
1299  // GEP1 V2
1300  // We need to know that V2Size is not unknown, otherwise we might have
1301  // stripped a gep with negative index ('gep <ptr>, -1, ...).
1302  if (V1Size != MemoryLocation::UnknownSize &&
1303  V2Size != MemoryLocation::UnknownSize) {
1304  if (-(uint64_t)GEP1BaseOffset < V1Size)
1305  return PartialAlias;
1306  return NoAlias;
1307  }
1308  }
1309  }
1310 
1311  if (!DecompGEP1.VarIndices.empty()) {
1312  uint64_t Modulo = 0;
1313  bool AllPositive = true;
1314  for (unsigned i = 0, e = DecompGEP1.VarIndices.size(); i != e; ++i) {
1315 
1316  // Try to distinguish something like &A[i][1] against &A[42][0].
1317  // Grab the least significant bit set in any of the scales. We
1318  // don't need std::abs here (even if the scale's negative) as we'll
1319  // be ^'ing Modulo with itself later.
1320  Modulo |= (uint64_t)DecompGEP1.VarIndices[i].Scale;
1321 
1322  if (AllPositive) {
1323  // If the Value could change between cycles, then any reasoning about
1324  // the Value this cycle may not hold in the next cycle. We'll just
1325  // give up if we can't determine conditions that hold for every cycle:
1326  const Value *V = DecompGEP1.VarIndices[i].V;
1327 
1328  KnownBits Known = computeKnownBits(V, DL, 0, &AC, nullptr, DT);
1329  bool SignKnownZero = Known.isNonNegative();
1330  bool SignKnownOne = Known.isNegative();
1331 
1332  // Zero-extension widens the variable, and so forces the sign
1333  // bit to zero.
1334  bool IsZExt = DecompGEP1.VarIndices[i].ZExtBits > 0 || isa<ZExtInst>(V);
1335  SignKnownZero |= IsZExt;
1336  SignKnownOne &= !IsZExt;
1337 
1338  // If the variable begins with a zero then we know it's
1339  // positive, regardless of whether the value is signed or
1340  // unsigned.
1341  int64_t Scale = DecompGEP1.VarIndices[i].Scale;
1342  AllPositive =
1343  (SignKnownZero && Scale >= 0) || (SignKnownOne && Scale < 0);
1344  }
1345  }
1346 
1347  Modulo = Modulo ^ (Modulo & (Modulo - 1));
1348 
1349  // We can compute the difference between the two addresses
1350  // mod Modulo. Check whether that difference guarantees that the
1351  // two locations do not alias.
1352  uint64_t ModOffset = (uint64_t)GEP1BaseOffset & (Modulo - 1);
1353  if (V1Size != MemoryLocation::UnknownSize &&
1354  V2Size != MemoryLocation::UnknownSize && ModOffset >= V2Size &&
1355  V1Size <= Modulo - ModOffset)
1356  return NoAlias;
1357 
1358  // If we know all the variables are positive, then GEP1 >= GEP1BasePtr.
1359  // If GEP1BasePtr > V2 (GEP1BaseOffset > 0) then we know the pointers
1360  // don't alias if V2Size can fit in the gap between V2 and GEP1BasePtr.
1361  if (AllPositive && GEP1BaseOffset > 0 && V2Size <= (uint64_t)GEP1BaseOffset)
1362  return NoAlias;
1363 
1364  if (constantOffsetHeuristic(DecompGEP1.VarIndices, V1Size, V2Size,
1365  GEP1BaseOffset, &AC, DT))
1366  return NoAlias;
1367  }
1368 
1369  // Statically, we can see that the base objects are the same, but the
1370  // pointers have dynamic offsets which we can't resolve. And none of our
1371  // little tricks above worked.
1372  return MayAlias;
1373 }
1374 
1376  // If the results agree, take it.
1377  if (A == B)
1378  return A;
1379  // A mix of PartialAlias and MustAlias is PartialAlias.
1380  if ((A == PartialAlias && B == MustAlias) ||
1381  (B == PartialAlias && A == MustAlias))
1382  return PartialAlias;
1383  // Otherwise, we don't know anything.
1384  return MayAlias;
1385 }
1386 
1387 /// Provides a bunch of ad-hoc rules to disambiguate a Select instruction
1388 /// against another.
1389 AliasResult BasicAAResult::aliasSelect(const SelectInst *SI, uint64_t SISize,
1390  const AAMDNodes &SIAAInfo,
1391  const Value *V2, uint64_t V2Size,
1392  const AAMDNodes &V2AAInfo,
1393  const Value *UnderV2) {
1394  // If the values are Selects with the same condition, we can do a more precise
1395  // check: just check for aliases between the values on corresponding arms.
1396  if (const SelectInst *SI2 = dyn_cast<SelectInst>(V2))
1397  if (SI->getCondition() == SI2->getCondition()) {
1398  AliasResult Alias = aliasCheck(SI->getTrueValue(), SISize, SIAAInfo,
1399  SI2->getTrueValue(), V2Size, V2AAInfo);
1400  if (Alias == MayAlias)
1401  return MayAlias;
1402  AliasResult ThisAlias =
1403  aliasCheck(SI->getFalseValue(), SISize, SIAAInfo,
1404  SI2->getFalseValue(), V2Size, V2AAInfo);
1405  return MergeAliasResults(ThisAlias, Alias);
1406  }
1407 
1408  // If both arms of the Select node NoAlias or MustAlias V2, then returns
1409  // NoAlias / MustAlias. Otherwise, returns MayAlias.
1410  AliasResult Alias =
1411  aliasCheck(V2, V2Size, V2AAInfo, SI->getTrueValue(),
1412  SISize, SIAAInfo, UnderV2);
1413  if (Alias == MayAlias)
1414  return MayAlias;
1415 
1416  AliasResult ThisAlias =
1417  aliasCheck(V2, V2Size, V2AAInfo, SI->getFalseValue(), SISize, SIAAInfo,
1418  UnderV2);
1419  return MergeAliasResults(ThisAlias, Alias);
1420 }
1421 
1422 /// Provide a bunch of ad-hoc rules to disambiguate a PHI instruction against
1423 /// another.
1424 AliasResult BasicAAResult::aliasPHI(const PHINode *PN, uint64_t PNSize,
1425  const AAMDNodes &PNAAInfo, const Value *V2,
1426  uint64_t V2Size, const AAMDNodes &V2AAInfo,
1427  const Value *UnderV2) {
1428  // Track phi nodes we have visited. We use this information when we determine
1429  // value equivalence.
1430  VisitedPhiBBs.insert(PN->getParent());
1431 
1432  // If the values are PHIs in the same block, we can do a more precise
1433  // as well as efficient check: just check for aliases between the values
1434  // on corresponding edges.
1435  if (const PHINode *PN2 = dyn_cast<PHINode>(V2))
1436  if (PN2->getParent() == PN->getParent()) {
1437  LocPair Locs(MemoryLocation(PN, PNSize, PNAAInfo),
1438  MemoryLocation(V2, V2Size, V2AAInfo));
1439  if (PN > V2)
1440  std::swap(Locs.first, Locs.second);
1441  // Analyse the PHIs' inputs under the assumption that the PHIs are
1442  // NoAlias.
1443  // If the PHIs are May/MustAlias there must be (recursively) an input
1444  // operand from outside the PHIs' cycle that is MayAlias/MustAlias or
1445  // there must be an operation on the PHIs within the PHIs' value cycle
1446  // that causes a MayAlias.
1447  // Pretend the phis do not alias.
1448  AliasResult Alias = NoAlias;
1449  assert(AliasCache.count(Locs) &&
1450  "There must exist an entry for the phi node");
1451  AliasResult OrigAliasResult = AliasCache[Locs];
1452  AliasCache[Locs] = NoAlias;
1453 
1454  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1455  AliasResult ThisAlias =
1456  aliasCheck(PN->getIncomingValue(i), PNSize, PNAAInfo,
1457  PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)),
1458  V2Size, V2AAInfo);
1459  Alias = MergeAliasResults(ThisAlias, Alias);
1460  if (Alias == MayAlias)
1461  break;
1462  }
1463 
1464  // Reset if speculation failed.
1465  if (Alias != NoAlias)
1466  AliasCache[Locs] = OrigAliasResult;
1467 
1468  return Alias;
1469  }
1470 
1471  SmallPtrSet<Value *, 4> UniqueSrc;
1472  SmallVector<Value *, 4> V1Srcs;
1473  bool isRecursive = false;
1474  for (Value *PV1 : PN->incoming_values()) {
1475  if (isa<PHINode>(PV1))
1476  // If any of the source itself is a PHI, return MayAlias conservatively
1477  // to avoid compile time explosion. The worst possible case is if both
1478  // sides are PHI nodes. In which case, this is O(m x n) time where 'm'
1479  // and 'n' are the number of PHI sources.
1480  return MayAlias;
1481 
1483  if (GEPOperator *PV1GEP = dyn_cast<GEPOperator>(PV1)) {
1484  // Check whether the incoming value is a GEP that advances the pointer
1485  // result of this PHI node (e.g. in a loop). If this is the case, we
1486  // would recurse and always get a MayAlias. Handle this case specially
1487  // below.
1488  if (PV1GEP->getPointerOperand() == PN && PV1GEP->getNumIndices() == 1 &&
1489  isa<ConstantInt>(PV1GEP->idx_begin())) {
1490  isRecursive = true;
1491  continue;
1492  }
1493  }
1494 
1495  if (UniqueSrc.insert(PV1).second)
1496  V1Srcs.push_back(PV1);
1497  }
1498 
1499  // If this PHI node is recursive, set the size of the accessed memory to
1500  // unknown to represent all the possible values the GEP could advance the
1501  // pointer to.
1502  if (isRecursive)
1503  PNSize = MemoryLocation::UnknownSize;
1504 
1505  AliasResult Alias =
1506  aliasCheck(V2, V2Size, V2AAInfo, V1Srcs[0],
1507  PNSize, PNAAInfo, UnderV2);
1508 
1509  // Early exit if the check of the first PHI source against V2 is MayAlias.
1510  // Other results are not possible.
1511  if (Alias == MayAlias)
1512  return MayAlias;
1513 
1514  // If all sources of the PHI node NoAlias or MustAlias V2, then returns
1515  // NoAlias / MustAlias. Otherwise, returns MayAlias.
1516  for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) {
1517  Value *V = V1Srcs[i];
1518 
1519  AliasResult ThisAlias =
1520  aliasCheck(V2, V2Size, V2AAInfo, V, PNSize, PNAAInfo, UnderV2);
1521  Alias = MergeAliasResults(ThisAlias, Alias);
1522  if (Alias == MayAlias)
1523  break;
1524  }
1525 
1526  return Alias;
1527 }
1528 
1529 /// Provides a bunch of ad-hoc rules to disambiguate in common cases, such as
1530 /// array references.
1531 AliasResult BasicAAResult::aliasCheck(const Value *V1, uint64_t V1Size,
1532  AAMDNodes V1AAInfo, const Value *V2,
1533  uint64_t V2Size, AAMDNodes V2AAInfo,
1534  const Value *O1, const Value *O2) {
1535  // If either of the memory references is empty, it doesn't matter what the
1536  // pointer values are.
1537  if (V1Size == 0 || V2Size == 0)
1538  return NoAlias;
1539 
1540  // Strip off any casts if they exist.
1541  V1 = V1->stripPointerCastsAndBarriers();
1542  V2 = V2->stripPointerCastsAndBarriers();
1543 
1544  // If V1 or V2 is undef, the result is NoAlias because we can always pick a
1545  // value for undef that aliases nothing in the program.
1546  if (isa<UndefValue>(V1) || isa<UndefValue>(V2))
1547  return NoAlias;
1548 
1549  // Are we checking for alias of the same value?
1550  // Because we look 'through' phi nodes, we could look at "Value" pointers from
1551  // different iterations. We must therefore make sure that this is not the
1552  // case. The function isValueEqualInPotentialCycles ensures that this cannot
1553  // happen by looking at the visited phi nodes and making sure they cannot
1554  // reach the value.
1555  if (isValueEqualInPotentialCycles(V1, V2))
1556  return MustAlias;
1557 
1558  if (!V1->getType()->isPointerTy() || !V2->getType()->isPointerTy())
1559  return NoAlias; // Scalars cannot alias each other
1560 
1561  // Figure out what objects these things are pointing to if we can.
1562  if (O1 == nullptr)
1563  O1 = GetUnderlyingObject(V1, DL, MaxLookupSearchDepth);
1564 
1565  if (O2 == nullptr)
1566  O2 = GetUnderlyingObject(V2, DL, MaxLookupSearchDepth);
1567 
1568  // Null values in the default address space don't point to any object, so they
1569  // don't alias any other pointer.
1570  if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O1))
1571  if (CPN->getType()->getAddressSpace() == 0)
1572  return NoAlias;
1573  if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O2))
1574  if (CPN->getType()->getAddressSpace() == 0)
1575  return NoAlias;
1576 
1577  if (O1 != O2) {
1578  // If V1/V2 point to two different objects, we know that we have no alias.
1579  if (isIdentifiedObject(O1) && isIdentifiedObject(O2))
1580  return NoAlias;
1581 
1582  // Constant pointers can't alias with non-const isIdentifiedObject objects.
1583  if ((isa<Constant>(O1) && isIdentifiedObject(O2) && !isa<Constant>(O2)) ||
1584  (isa<Constant>(O2) && isIdentifiedObject(O1) && !isa<Constant>(O1)))
1585  return NoAlias;
1586 
1587  // Function arguments can't alias with things that are known to be
1588  // unambigously identified at the function level.
1589  if ((isa<Argument>(O1) && isIdentifiedFunctionLocal(O2)) ||
1590  (isa<Argument>(O2) && isIdentifiedFunctionLocal(O1)))
1591  return NoAlias;
1592 
1593  // If one pointer is the result of a call/invoke or load and the other is a
1594  // non-escaping local object within the same function, then we know the
1595  // object couldn't escape to a point where the call could return it.
1596  //
1597  // Note that if the pointers are in different functions, there are a
1598  // variety of complications. A call with a nocapture argument may still
1599  // temporary store the nocapture argument's value in a temporary memory
1600  // location if that memory location doesn't escape. Or it may pass a
1601  // nocapture value to other functions as long as they don't capture it.
1603  return NoAlias;
1605  return NoAlias;
1606  }
1607 
1608  // If the size of one access is larger than the entire object on the other
1609  // side, then we know such behavior is undefined and can assume no alias.
1610  if ((V1Size != MemoryLocation::UnknownSize &&
1611  isObjectSmallerThan(O2, V1Size, DL, TLI)) ||
1612  (V2Size != MemoryLocation::UnknownSize &&
1613  isObjectSmallerThan(O1, V2Size, DL, TLI)))
1614  return NoAlias;
1615 
1616  // Check the cache before climbing up use-def chains. This also terminates
1617  // otherwise infinitely recursive queries.
1618  LocPair Locs(MemoryLocation(V1, V1Size, V1AAInfo),
1619  MemoryLocation(V2, V2Size, V2AAInfo));
1620  if (V1 > V2)
1621  std::swap(Locs.first, Locs.second);
1622  std::pair<AliasCacheTy::iterator, bool> Pair =
1623  AliasCache.insert(std::make_pair(Locs, MayAlias));
1624  if (!Pair.second)
1625  return Pair.first->second;
1626 
1627  // FIXME: This isn't aggressively handling alias(GEP, PHI) for example: if the
1628  // GEP can't simplify, we don't even look at the PHI cases.
1629  if (!isa<GEPOperator>(V1) && isa<GEPOperator>(V2)) {
1630  std::swap(V1, V2);
1631  std::swap(V1Size, V2Size);
1632  std::swap(O1, O2);
1633  std::swap(V1AAInfo, V2AAInfo);
1634  }
1635  if (const GEPOperator *GV1 = dyn_cast<GEPOperator>(V1)) {
1636  AliasResult Result =
1637  aliasGEP(GV1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, O1, O2);
1638  if (Result != MayAlias)
1639  return AliasCache[Locs] = Result;
1640  }
1641 
1642  if (isa<PHINode>(V2) && !isa<PHINode>(V1)) {
1643  std::swap(V1, V2);
1644  std::swap(O1, O2);
1645  std::swap(V1Size, V2Size);
1646  std::swap(V1AAInfo, V2AAInfo);
1647  }
1648  if (const PHINode *PN = dyn_cast<PHINode>(V1)) {
1649  AliasResult Result = aliasPHI(PN, V1Size, V1AAInfo,
1650  V2, V2Size, V2AAInfo, O2);
1651  if (Result != MayAlias)
1652  return AliasCache[Locs] = Result;
1653  }
1654 
1655  if (isa<SelectInst>(V2) && !isa<SelectInst>(V1)) {
1656  std::swap(V1, V2);
1657  std::swap(O1, O2);
1658  std::swap(V1Size, V2Size);
1659  std::swap(V1AAInfo, V2AAInfo);
1660  }
1661  if (const SelectInst *S1 = dyn_cast<SelectInst>(V1)) {
1662  AliasResult Result =
1663  aliasSelect(S1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, O2);
1664  if (Result != MayAlias)
1665  return AliasCache[Locs] = Result;
1666  }
1667 
1668  // If both pointers are pointing into the same object and one of them
1669  // accesses the entire object, then the accesses must overlap in some way.
1670  if (O1 == O2)
1671  if ((V1Size != MemoryLocation::UnknownSize &&
1672  isObjectSize(O1, V1Size, DL, TLI)) ||
1673  (V2Size != MemoryLocation::UnknownSize &&
1674  isObjectSize(O2, V2Size, DL, TLI)))
1675  return AliasCache[Locs] = PartialAlias;
1676 
1677  // Recurse back into the best AA results we have, potentially with refined
1678  // memory locations. We have already ensured that BasicAA has a MayAlias
1679  // cache result for these, so any recursion back into BasicAA won't loop.
1680  AliasResult Result = getBestAAResults().alias(Locs.first, Locs.second);
1681  return AliasCache[Locs] = Result;
1682 }
1683 
1684 /// Check whether two Values can be considered equivalent.
1685 ///
1686 /// In addition to pointer equivalence of \p V1 and \p V2 this checks whether
1687 /// they can not be part of a cycle in the value graph by looking at all
1688 /// visited phi nodes an making sure that the phis cannot reach the value. We
1689 /// have to do this because we are looking through phi nodes (That is we say
1690 /// noalias(V, phi(VA, VB)) if noalias(V, VA) and noalias(V, VB).
1691 bool BasicAAResult::isValueEqualInPotentialCycles(const Value *V,
1692  const Value *V2) {
1693  if (V != V2)
1694  return false;
1695 
1696  const Instruction *Inst = dyn_cast<Instruction>(V);
1697  if (!Inst)
1698  return true;
1699 
1700  if (VisitedPhiBBs.empty())
1701  return true;
1702 
1703  if (VisitedPhiBBs.size() > MaxNumPhiBBsValueReachabilityCheck)
1704  return false;
1705 
1706  // Make sure that the visited phis cannot reach the Value. This ensures that
1707  // the Values cannot come from different iterations of a potential cycle the
1708  // phi nodes could be involved in.
1709  for (auto *P : VisitedPhiBBs)
1710  if (isPotentiallyReachable(&P->front(), Inst, DT, LI))
1711  return false;
1712 
1713  return true;
1714 }
1715 
1716 /// Computes the symbolic difference between two de-composed GEPs.
1717 ///
1718 /// Dest and Src are the variable indices from two decomposed GetElementPtr
1719 /// instructions GEP1 and GEP2 which have common base pointers.
1720 void BasicAAResult::GetIndexDifference(
1722  const SmallVectorImpl<VariableGEPIndex> &Src) {
1723  if (Src.empty())
1724  return;
1725 
1726  for (unsigned i = 0, e = Src.size(); i != e; ++i) {
1727  const Value *V = Src[i].V;
1728  unsigned ZExtBits = Src[i].ZExtBits, SExtBits = Src[i].SExtBits;
1729  int64_t Scale = Src[i].Scale;
1730 
1731  // Find V in Dest. This is N^2, but pointer indices almost never have more
1732  // than a few variable indexes.
1733  for (unsigned j = 0, e = Dest.size(); j != e; ++j) {
1734  if (!isValueEqualInPotentialCycles(Dest[j].V, V) ||
1735  Dest[j].ZExtBits != ZExtBits || Dest[j].SExtBits != SExtBits)
1736  continue;
1737 
1738  // If we found it, subtract off Scale V's from the entry in Dest. If it
1739  // goes to zero, remove the entry.
1740  if (Dest[j].Scale != Scale)
1741  Dest[j].Scale -= Scale;
1742  else
1743  Dest.erase(Dest.begin() + j);
1744  Scale = 0;
1745  break;
1746  }
1747 
1748  // If we didn't consume this entry, add it to the end of the Dest list.
1749  if (Scale) {
1750  VariableGEPIndex Entry = {V, ZExtBits, SExtBits, -Scale};
1751  Dest.push_back(Entry);
1752  }
1753  }
1754 }
1755 
1756 bool BasicAAResult::constantOffsetHeuristic(
1757  const SmallVectorImpl<VariableGEPIndex> &VarIndices, uint64_t V1Size,
1758  uint64_t V2Size, int64_t BaseOffset, AssumptionCache *AC,
1759  DominatorTree *DT) {
1760  if (VarIndices.size() != 2 || V1Size == MemoryLocation::UnknownSize ||
1761  V2Size == MemoryLocation::UnknownSize)
1762  return false;
1763 
1764  const VariableGEPIndex &Var0 = VarIndices[0], &Var1 = VarIndices[1];
1765 
1766  if (Var0.ZExtBits != Var1.ZExtBits || Var0.SExtBits != Var1.SExtBits ||
1767  Var0.Scale != -Var1.Scale)
1768  return false;
1769 
1770  unsigned Width = Var1.V->getType()->getIntegerBitWidth();
1771 
1772  // We'll strip off the Extensions of Var0 and Var1 and do another round
1773  // of GetLinearExpression decomposition. In the example above, if Var0
1774  // is zext(%x + 1) we should get V1 == %x and V1Offset == 1.
1775 
1776  APInt V0Scale(Width, 0), V0Offset(Width, 0), V1Scale(Width, 0),
1777  V1Offset(Width, 0);
1778  bool NSW = true, NUW = true;
1779  unsigned V0ZExtBits = 0, V0SExtBits = 0, V1ZExtBits = 0, V1SExtBits = 0;
1780  const Value *V0 = GetLinearExpression(Var0.V, V0Scale, V0Offset, V0ZExtBits,
1781  V0SExtBits, DL, 0, AC, DT, NSW, NUW);
1782  NSW = true;
1783  NUW = true;
1784  const Value *V1 = GetLinearExpression(Var1.V, V1Scale, V1Offset, V1ZExtBits,
1785  V1SExtBits, DL, 0, AC, DT, NSW, NUW);
1786 
1787  if (V0Scale != V1Scale || V0ZExtBits != V1ZExtBits ||
1788  V0SExtBits != V1SExtBits || !isValueEqualInPotentialCycles(V0, V1))
1789  return false;
1790 
1791  // We have a hit - Var0 and Var1 only differ by a constant offset!
1792 
1793  // If we've been sext'ed then zext'd the maximum difference between Var0 and
1794  // Var1 is possible to calculate, but we're just interested in the absolute
1795  // minimum difference between the two. The minimum distance may occur due to
1796  // wrapping; consider "add i3 %i, 5": if %i == 7 then 7 + 5 mod 8 == 4, and so
1797  // the minimum distance between %i and %i + 5 is 3.
1798  APInt MinDiff = V0Offset - V1Offset, Wrapped = -MinDiff;
1799  MinDiff = APIntOps::umin(MinDiff, Wrapped);
1800  uint64_t MinDiffBytes = MinDiff.getZExtValue() * std::abs(Var0.Scale);
1801 
1802  // We can't definitely say whether GEP1 is before or after V2 due to wrapping
1803  // arithmetic (i.e. for some values of GEP1 and V2 GEP1 < V2, and for other
1804  // values GEP1 > V2). We'll therefore only declare NoAlias if both V1Size and
1805  // V2Size can fit in the MinDiffBytes gap.
1806  return V1Size + std::abs(BaseOffset) <= MinDiffBytes &&
1807  V2Size + std::abs(BaseOffset) <= MinDiffBytes;
1808 }
1809 
1810 //===----------------------------------------------------------------------===//
1811 // BasicAliasAnalysis Pass
1812 //===----------------------------------------------------------------------===//
1813 
1814 AnalysisKey BasicAA::Key;
1815 
1817  return BasicAAResult(F.getParent()->getDataLayout(),
1821  AM.getCachedResult<LoopAnalysis>(F));
1822 }
1823 
1826 }
1827 
1828 char BasicAAWrapperPass::ID = 0;
1829 
1830 void BasicAAWrapperPass::anchor() {}
1831 
1833  "Basic Alias Analysis (stateless AA impl)", true, true)
1838  "Basic Alias Analysis (stateless AA impl)", true, true)
1839 
1841  return new BasicAAWrapperPass();
1842 }
1843 
1845  auto &ACT = getAnalysis<AssumptionCacheTracker>();
1846  auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>();
1847  auto &DTWP = getAnalysis<DominatorTreeWrapperPass>();
1848  auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
1849 
1850  Result.reset(new BasicAAResult(F.getParent()->getDataLayout(), TLIWP.getTLI(),
1851  ACT.getAssumptionCache(F), &DTWP.getDomTree(),
1852  LIWP ? &LIWP->getLoopInfo() : nullptr));
1853 
1854  return false;
1855 }
1856 
1858  AU.setPreservesAll();
1862 }
1863 
1865  return BasicAAResult(
1866  F.getParent()->getDataLayout(),
1868  P.getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F));
1869 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL, const TargetLibraryInfo *TLI, ObjectSizeOpts Opts={})
Compute the size of the object pointed by Ptr.
bool onlyReadsMemory() const
Determine if the function does not access or only reads memory.
Definition: Function.h:403
The two locations precisely alias each other.
Definition: AliasAnalysis.h:91
static const unsigned MaxLookupSearchDepth
Basic Alias Analysis(stateless AA impl)"
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Handle invalidation events in the new pass manager.
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:109
bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA)
Trigger the invalidation of some other analysis pass if not already handled and return whether it was...
Definition: PassManager.h:577
BasicAAResult(const DataLayout &DL, const TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr)
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
static bool isIntrinsicCall(ImmutableCallSite CS, Intrinsic::ID IID)
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1542
APInt sext(unsigned width) const
Sign extend to a new width.
Definition: APInt.cpp:841
This class represents an incoming formal argument to a Function.
Definition: Argument.h:30
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:687
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
BasicAAResult createLegacyPMBasicAAResult(Pass &P, Function &F)
A helper for the legacy pass manager to create a BasicAAResult object populated to the best of our ab...
bool isSized(SmallPtrSetImpl< Type *> *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
Definition: Type.h:262
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal)
bool onlyAccessesArgMemory() const
Determine if the call can access memmory only using pointers based on its arguments.
Definition: CallSite.h:471
const Value * stripPointerCastsAndBarriers() const
Strip off pointer casts, all-zero GEPs, aliases and barriers.
Definition: Value.cpp:539
The two locations alias, but only due to a partial overlap.
Definition: AliasAnalysis.h:89
const StructLayout * getStructLayout(StructType *Ty) const
Returns a StructLayout object, indicating the alignment of the struct, its size, and the offsets of i...
Definition: DataLayout.cpp:562
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
This class represents a function call, abstracting a target machine&#39;s calling convention.
This file contains the declarations for metadata subclasses.
static bool isEscapeSource(const Value *V)
Returns true if the pointer is one which would have been considered an escape by isNonEscapingLocalOb...
An immutable pass that tracks lazily created AssumptionCache objects.
const Value * getTrueValue() const
unsigned getPointerAddressSpace() const
Method to return the address space of the pointer operand.
Definition: Operator.h:439
A cache of .assume calls within a function.
bool RoundToAlign
Whether to round the result up to the alignment of allocas, byval arguments, and global variables...
This is the AA result object for the basic, local, and stateless alias analysis.
APInt trunc(unsigned width) const
Truncate to new width.
Definition: APInt.cpp:818
unsigned getPointerSizeInBits(unsigned AS=0) const
Layout pointer size, in bits FIXME: The defaults need to be removed once all of the backends/clients ...
Definition: DataLayout.h:346
STATISTIC(NumFunctions, "Total number of functions")
The two locations do not alias at all.
Definition: AliasAnalysis.h:85
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:238
F(f)
bool isNoAliasCall(const Value *V)
Return true if this pointer is returned by a noalias function.
bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal)
Chases pointers until we find a (constant global) or not.
The access modifies the value stored in memory.
op_iterator op_begin()
Definition: User.h:214
The two locations may or may not alias. This is the least precise result.
Definition: AliasAnalysis.h:87
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1488
This indicates that the function could not be classified into one of the behaviors above...
bool onlyReadsMemory() const
Determine if the call does not access or only reads memory.
Definition: CallSite.h:454
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:191
AnalysisUsage & addRequired()
The only memory references in this function (if it has any) are references of memory that is otherwis...
Used to lazily calculate structure layout information for a target machine, based on the DataLayout s...
Definition: DataLayout.h:493
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
This class represents the LLVM &#39;select&#39; instruction.
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:361
Class to represent struct types.
Definition: DerivedTypes.h:201
APInt zextOrSelf(unsigned width) const
Zero extend or truncate to width.
Definition: APInt.cpp:899
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
Type * getPointerOperandType() const
Method to return the pointer operand as a PointerType.
Definition: Operator.h:431
const unsigned MaxNumPhiBBsValueReachabilityCheck
Cutoff after which to stop analysing a set of phi nodes potentially involved in a cycle...
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass...
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:197
This file contains the simple types necessary to represent the attributes associated with functions a...
InstrTy * getInstruction() const
Definition: CallSite.h:92
static AliasResult MergeAliasResults(AliasResult A, AliasResult B)
The access references the value stored in memory.
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:907
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
The function may perform non-volatile loads and stores of objects pointed to by its pointer-typed arg...
This file implements a class to represent arbitrary precision integral constant values and operations...
bool onlyAccessesInaccessibleMemory() const
Determine if the function may only access memory that is inaccessible from the IR.
Definition: Function.h:427
bool isIdentifiedObject(const Value *V)
Return true if this pointer refers to a distinct and identifiable object.
place backedge safepoints impl
IterTy data_operands_end() const
Definition: CallSite.h:249
int64_t getSExtValue() const
Get sign extended value.
Definition: APInt.h:1554
void shrink_and_clear()
Definition: DenseMap.h:1012
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
static MemoryLocation getForDest(const MemIntrinsic *MI)
Return a location representing the destination of a memory set or transfer.
unsigned getNumIndices() const
Definition: Operator.h:443
static cl::opt< bool > EnableRecPhiAnalysis("basicaa-recphi", cl::Hidden, cl::init(false))
Enable analysis of recursive PHI nodes.
bool isInBounds() const
Test whether this is an inbounds GEP, as defined by LangRef.html.
Definition: Operator.h:404
FunctionModRefBehavior
Summary of how a function affects memory in the program.
bool has(LibFunc F) const
Tests whether a library function is available.
bool paramHasAttr(unsigned ArgNo, Attribute::AttrKind Kind) const
Return true if the call or the callee has the given attribute.
Definition: CallSite.h:377
AnalysisType & getAnalysis() const
getAnalysis<AnalysisType>() - This function is used by subclasses to get to the analysis information ...
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:140
static bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &DL, const TargetLibraryInfo &TLI)
Returns true if we can prove that the object specified by V has size Size.
Value * getOperand(unsigned i) const
Definition: User.h:154
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:146
bool isNegative() const
Returns true if this value is known to be negative.
Definition: KnownBits.h:96
bool doesNotAccessMemory() const
Determine if the function does not access memory.
Definition: Function.h:395
The access neither references nor modifies the value stored in memory.
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:406
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
Definition: Constants.h:149
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
* if(!EatIfPresent(lltok::kw_thread_local)) return false
ParseOptionalThreadLocal := /*empty.
static bool isWriteOnlyParam(ImmutableCallSite CS, unsigned ArgIdx, const TargetLibraryInfo &TLI)
Returns true if this is a writeonly (i.e Mod only) parameter.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:92
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:116
This file contains the declarations for the subclasses of Constant, which represent the different fla...
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:221
bool MaskedValueIsZero(const Value *V, const APInt &Mask, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Return true if &#39;V & Mask&#39; is known to be zero.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:371
ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx)
FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS)
Returns the behavior when calling the given call site.
AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:79
Represent the analysis usage information of a pass.
op_iterator op_end()
Definition: User.h:216
bool hasOperandBundles() const
Definition: CallSite.h:517
The only memory references in this function (if it has any) are non-volatile loads and stores from ob...
Value * getPointerOperand()
Definition: Operator.h:420
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
bool isPotentiallyReachable(const Instruction *From, const Instruction *To, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)
Determine whether instruction &#39;To&#39; is reachable from &#39;From&#39;, returning true if uncertain.
Definition: CFG.cpp:186
ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc)
Checks to see if the specified callsite can clobber the specified memory object.
static bool isNonEscapingLocalObject(const Value *V)
Returns true if the pointer is to a function-local object that never escapes from the function...
const Value * getCondition() const
bool doesNotCapture(unsigned OpNo) const
Determine whether this data operand is not captured.
Definition: CallSite.h:575
const AMDGPUAS & AS
iterator erase(const_iterator CI)
Definition: SmallVector.h:449
unsigned getNumArgOperands() const
Definition: CallSite.h:293
bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, bool StoreCaptures)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
static AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1, uint64_t V1Size, const GEPOperator *GEP2, uint64_t V2Size, const DataLayout &DL)
Provide ad-hoc rules to disambiguate accesses through two GEP operators, both having the exact same p...
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Value * GetUnderlyingObject(Value *V, const DataLayout &DL, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value...
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
This function does not perform any non-local loads or stores to memory.
static int64_t adjustToPointerSize(int64_t Offset, unsigned PointerSize)
To ensure a pointer offset fits in an integer of size PointerSize (in bits) when that size is smaller...
const APInt & umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
Definition: APInt.h:2094
bool isIdentifiedFunctionLocal(const Value *V)
Return true if V is umabigously identified at the function-level.
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Definition: IntrinsicInst.h:51
const Value * Ptr
The address of the start of the location.
Representation for a specific memory location.
size_type size() const
Definition: SmallPtrSet.h:93
A function analysis which provides an AssumptionCache.
unsigned getNumOperands() const
Definition: User.h:176
bool doesNotReadMemory() const
Determine if the call does not access or only writes memory.
Definition: CallSite.h:462
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
This is a utility class that provides an abstraction for the common functionality between Instruction...
Definition: Operator.h:31
static bool isObjectSmallerThan(const Value *V, uint64_t Size, const DataLayout &DL, const TargetLibraryInfo &TLI)
Returns true if we can prove that the object specified by V is smaller than Size. ...
Provides information about what library functions are available for the current target.
INITIALIZE_PASS_BEGIN(BasicAAWrapperPass, "basicaa", "Basic Alias Analysis (stateless AA impl)", true, true) INITIALIZE_PASS_END(BasicAAWrapperPass
A constant pointer value that points to null.
Definition: Constants.h:530
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:642
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:385
uint64_t getSizeInBytes() const
Definition: DataLayout.h:501
IterTy data_operands_begin() const
data_operands_begin/data_operands_end - Return iterators iterating over the call / invoke argument li...
Definition: CallSite.h:245
unsigned getNumIncomingValues() const
Return the number of incoming edges.
This function does not perform any non-local stores or volatile loads, but may read from any memory l...
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:923
Class for arbitrary precision integers.
Definition: APInt.h:69
static bool notDifferentParent(const Value *O1, const Value *O2)
FunctionPass * createBasicAAWrapperPass()
void setPreservesAll()
Set by analyses that do not transform their input at all.
bool getLibFunc(StringRef funcName, LibFunc &F) const
Searches for a particular function name.
const Value * getFalseValue() const
bool doesNotAccessMemory() const
Determine if the call does not access memory.
Definition: CallSite.h:446
uint64_t getTypeAllocSize(Type *Ty) const
Returns the offset in bytes between successive objects of the specified type, including alignment pad...
Definition: DataLayout.h:405
Basic Alias true
AAMDNodes AATags
The metadata nodes which describes the aliasing of the location (each member is null if that kind of ...
bool intersects(const APInt &RHS) const
This operation tests if there are any pairs of corresponding bits between this APInt and RHS that are...
Definition: APInt.h:1300
uint64_t getElementOffset(unsigned Idx) const
Definition: DataLayout.h:515
static Type * getIndexedType(Type *Ty, ArrayRef< Value *> IdxList)
Returns the type of the element that would be loaded with a load instruction with the specified param...
unsigned getIntegerBitWidth() const
Definition: DerivedTypes.h:97
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value...
Definition: APInt.h:475
bool isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, bool LookThroughBitCast=false)
Tests if a value is a call or invoke to a library function that allocates memory similar to malloc or...
This file provides utility analysis objects describing memory locations.
Establish a view to a call site for examination.
Definition: CallSite.h:695
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
The access both references and modifies the value stored in memory.
#define I(x, y, z)
Definition: MD5.cpp:58
AAResultsProxy getBestAAResults()
Get a proxy for the best AA result set to query at this time.
APFloat abs(APFloat X)
Returns the absolute value of the argument.
Definition: APFloat.h:1213
bool onlyAccessesArgMemory() const
Determine if the call can access memmory only using pointers based on its arguments.
Definition: Function.h:420
iterator end()
Definition: DenseMap.h:79
bool doesNotReadMemory() const
Determine if the function does not access or only writes memory.
Definition: Function.h:411
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:706
bool onlyAccessesInaccessibleMemOrArgMem() const
Determine if the function may only access memory that is either inaccessible from the IR or pointed t...
Definition: Function.h:436
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:141
FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS)
bool isKnownNonEqual(const Value *V1, const Value *V2, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Return true if the given values are known to be non-equal when defined.
bool isByValArgument(unsigned ArgNo) const
Determine whether this argument is passed by value.
Definition: CallSite.h:580
ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc)
BasicAAResult run(Function &F, FunctionAnalysisManager &AM)
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:559
FunTy * getCalledFunction() const
Return the function being called if this is a direct call, otherwise return null (if it&#39;s an indirect...
Definition: CallSite.h:107
Analysis pass providing the TargetLibraryInfo.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
Definition: Type.cpp:115
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:545
LLVM Value Representation.
Definition: Value.h:73
ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx)
Get the location associated with a pointer argument of a callsite.
uint64_t getTypeStoreSize(Type *Ty) const
Returns the maximum number of bytes that may be overwritten by storing the specified type...
Definition: DataLayout.h:388
constexpr char Size[]
Key for Kernel::Arg::Metadata::mSize.
unsigned getOpcode() const
Return the opcode for this Instruction or ConstantExpr.
Definition: Operator.h:41
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
Definition: Compiler.h:235
static const Function * getParent(const Value *V)
This is the interface for LLVM&#39;s primary stateless and local alias analysis.
Various options to control the behavior of getObjectSize.
Type * getSourceElementType() const
Definition: Operator.cpp:23
bool isNonNegative() const
Returns true if this value is known to be non-negative.
Definition: KnownBits.h:99
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
int64_t getSExtValue() const
Return the constant as a 64-bit integer value after it has been sign extended as appropriate for the ...
Definition: Constants.h:157
op_range incoming_values()
Value * SimplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, OptimizationRemarkEmitter *ORE=nullptr)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:44
void initializeBasicAAWrapperPassPass(PassRegistry &)
const BasicBlock * getParent() const
Definition: Instruction.h:66
Legacy wrapper pass to provide the BasicAAResult object.
gep_type_iterator gep_type_begin(const User *GEP)
uint64_t Size
The maximum size of the location, in address-units, or UnknownSize if the size is not known...
static MemoryLocation getForSource(const MemTransferInst *MTI)
Return a location representing the source of a memory transfer.