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