LLVM  15.0.0git
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/ScopeExit.h"
18 #include "llvm/ADT/SmallPtrSet.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/Statistic.h"
23 #include "llvm/Analysis/CFG.h"
30 #include "llvm/IR/Argument.h"
31 #include "llvm/IR/Attributes.h"
32 #include "llvm/IR/Constant.h"
33 #include "llvm/IR/ConstantRange.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/Operator.h"
48 #include "llvm/IR/Type.h"
49 #include "llvm/IR/User.h"
50 #include "llvm/IR/Value.h"
51 #include "llvm/InitializePasses.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("basic-aa-recphi", cl::Hidden,
68  cl::init(true));
69 
70 /// SearchLimitReached / SearchTimes shows how often the limit of
71 /// to decompose GEPs is reached. It will affect the precision
72 /// of basic alias analysis.
73 STATISTIC(SearchLimitReached, "Number of times the limit to "
74  "decompose GEPs is reached");
75 STATISTIC(SearchTimes, "Number of times a GEP is decomposed");
76 
77 /// Cutoff after which to stop analysing a set of phi nodes potentially involved
78 /// in a cycle. Because we are analysing 'through' phi nodes, we need to be
79 /// careful with value equivalence. We use reachability to make sure a value
80 /// cannot be involved in a cycle.
82 
83 // The max limit of the search depth in DecomposeGEPExpression() and
84 // getUnderlyingObject().
85 static const unsigned MaxLookupSearchDepth = 6;
86 
89  // We don't care if this analysis itself is preserved, it has no state. But
90  // we need to check that the analyses it depends on have been. Note that we
91  // may be created without handles to some analyses and in that case don't
92  // depend on them.
93  if (Inv.invalidate<AssumptionAnalysis>(Fn, PA) ||
94  (DT && Inv.invalidate<DominatorTreeAnalysis>(Fn, PA)) ||
95  (PV && Inv.invalidate<PhiValuesAnalysis>(Fn, PA)))
96  return true;
97 
98  // Otherwise this analysis result remains valid.
99  return false;
100 }
101 
102 //===----------------------------------------------------------------------===//
103 // Useful predicates
104 //===----------------------------------------------------------------------===//
105 
106 /// Returns true if the pointer is one which would have been considered an
107 /// escape by isNonEscapingLocalObject.
108 static bool isEscapeSource(const Value *V) {
109  if (isa<CallBase>(V))
110  return true;
111 
112  // The load case works because isNonEscapingLocalObject considers all
113  // stores to be escapes (it passes true for the StoreCaptures argument
114  // to PointerMayBeCaptured).
115  if (isa<LoadInst>(V))
116  return true;
117 
118  // The inttoptr case works because isNonEscapingLocalObject considers all
119  // means of converting or equating a pointer to an int (ptrtoint, ptr store
120  // which could be followed by an integer load, ptr<->int compare) as
121  // escaping, and objects located at well-known addresses via platform-specific
122  // means cannot be considered non-escaping local objects.
123  if (isa<IntToPtrInst>(V))
124  return true;
125 
126  return false;
127 }
128 
129 /// Returns the size of the object specified by V or UnknownSize if unknown.
130 static uint64_t getObjectSize(const Value *V, const DataLayout &DL,
131  const TargetLibraryInfo &TLI,
132  bool NullIsValidLoc,
133  bool RoundToAlign = false) {
134  uint64_t Size;
135  ObjectSizeOpts Opts;
136  Opts.RoundToAlign = RoundToAlign;
137  Opts.NullIsUnknownSize = NullIsValidLoc;
138  if (getObjectSize(V, Size, DL, &TLI, Opts))
139  return Size;
141 }
142 
143 /// Returns true if we can prove that the object specified by V is smaller than
144 /// Size.
145 static bool isObjectSmallerThan(const Value *V, uint64_t Size,
146  const DataLayout &DL,
147  const TargetLibraryInfo &TLI,
148  bool NullIsValidLoc) {
149  // Note that the meanings of the "object" are slightly different in the
150  // following contexts:
151  // c1: llvm::getObjectSize()
152  // c2: llvm.objectsize() intrinsic
153  // c3: isObjectSmallerThan()
154  // c1 and c2 share the same meaning; however, the meaning of "object" in c3
155  // refers to the "entire object".
156  //
157  // Consider this example:
158  // char *p = (char*)malloc(100)
159  // char *q = p+80;
160  //
161  // In the context of c1 and c2, the "object" pointed by q refers to the
162  // stretch of memory of q[0:19]. So, getObjectSize(q) should return 20.
163  //
164  // However, in the context of c3, the "object" refers to the chunk of memory
165  // being allocated. So, the "object" has 100 bytes, and q points to the middle
166  // the "object". In case q is passed to isObjectSmallerThan() as the 1st
167  // parameter, before the llvm::getObjectSize() is called to get the size of
168  // entire object, we should:
169  // - either rewind the pointer q to the base-address of the object in
170  // question (in this case rewind to p), or
171  // - just give up. It is up to caller to make sure the pointer is pointing
172  // to the base address the object.
173  //
174  // We go for 2nd option for simplicity.
175  if (!isIdentifiedObject(V))
176  return false;
177 
178  // This function needs to use the aligned object size because we allow
179  // reads a bit past the end given sufficient alignment.
180  uint64_t ObjectSize = getObjectSize(V, DL, TLI, NullIsValidLoc,
181  /*RoundToAlign*/ true);
182 
183  return ObjectSize != MemoryLocation::UnknownSize && ObjectSize < Size;
184 }
185 
186 /// Return the minimal extent from \p V to the end of the underlying object,
187 /// assuming the result is used in an aliasing query. E.g., we do use the query
188 /// location size and the fact that null pointers cannot alias here.
190  const LocationSize &LocSize,
191  const DataLayout &DL,
192  bool NullIsValidLoc) {
193  // If we have dereferenceability information we know a lower bound for the
194  // extent as accesses for a lower offset would be valid. We need to exclude
195  // the "or null" part if null is a valid pointer. We can ignore frees, as an
196  // access after free would be undefined behavior.
197  bool CanBeNull, CanBeFreed;
198  uint64_t DerefBytes =
199  V.getPointerDereferenceableBytes(DL, CanBeNull, CanBeFreed);
200  DerefBytes = (CanBeNull && NullIsValidLoc) ? 0 : DerefBytes;
201  // If queried with a precise location size, we assume that location size to be
202  // accessed, thus valid.
203  if (LocSize.isPrecise())
204  DerefBytes = std::max(DerefBytes, LocSize.getValue());
205  return DerefBytes;
206 }
207 
208 /// Returns true if we can prove that the object specified by V has size Size.
209 static bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &DL,
210  const TargetLibraryInfo &TLI, bool NullIsValidLoc) {
211  uint64_t ObjectSize = getObjectSize(V, DL, TLI, NullIsValidLoc);
212  return ObjectSize != MemoryLocation::UnknownSize && ObjectSize == Size;
213 }
214 
215 //===----------------------------------------------------------------------===//
216 // CaptureInfo implementations
217 //===----------------------------------------------------------------------===//
218 
219 CaptureInfo::~CaptureInfo() = default;
220 
222  const Instruction *I) {
223  return isNonEscapingLocalObject(Object, &IsCapturedCache);
224 }
225 
227  const Instruction *I) {
229  return false;
230 
231  auto Iter = EarliestEscapes.insert({Object, nullptr});
232  if (Iter.second) {
233  Instruction *EarliestCapture = FindEarliestCapture(
234  Object, *const_cast<Function *>(I->getFunction()),
235  /*ReturnCaptures=*/false, /*StoreCaptures=*/true, DT, EphValues);
236  if (EarliestCapture) {
237  auto Ins = Inst2Obj.insert({EarliestCapture, {}});
238  Ins.first->second.push_back(Object);
239  }
240  Iter.first->second = EarliestCapture;
241  }
242 
243  // No capturing instruction.
244  if (!Iter.first->second)
245  return true;
246 
247  return I != Iter.first->second &&
248  !isPotentiallyReachable(Iter.first->second, I, nullptr, &DT, &LI);
249 }
250 
252  auto Iter = Inst2Obj.find(I);
253  if (Iter != Inst2Obj.end()) {
254  for (const Value *Obj : Iter->second)
255  EarliestEscapes.erase(Obj);
256  Inst2Obj.erase(I);
257  }
258 }
259 
260 //===----------------------------------------------------------------------===//
261 // GetElementPtr Instruction Decomposition and Analysis
262 //===----------------------------------------------------------------------===//
263 
264 namespace {
265 /// Represents zext(sext(trunc(V))).
266 struct CastedValue {
267  const Value *V;
268  unsigned ZExtBits = 0;
269  unsigned SExtBits = 0;
270  unsigned TruncBits = 0;
271 
272  explicit CastedValue(const Value *V) : V(V) {}
273  explicit CastedValue(const Value *V, unsigned ZExtBits, unsigned SExtBits,
274  unsigned TruncBits)
275  : V(V), ZExtBits(ZExtBits), SExtBits(SExtBits), TruncBits(TruncBits) {}
276 
277  unsigned getBitWidth() const {
278  return V->getType()->getPrimitiveSizeInBits() - TruncBits + ZExtBits +
279  SExtBits;
280  }
281 
282  CastedValue withValue(const Value *NewV) const {
283  return CastedValue(NewV, ZExtBits, SExtBits, TruncBits);
284  }
285 
286  /// Replace V with zext(NewV)
287  CastedValue withZExtOfValue(const Value *NewV) const {
288  unsigned ExtendBy = V->getType()->getPrimitiveSizeInBits() -
289  NewV->getType()->getPrimitiveSizeInBits();
290  if (ExtendBy <= TruncBits)
291  return CastedValue(NewV, ZExtBits, SExtBits, TruncBits - ExtendBy);
292 
293  // zext(sext(zext(NewV))) == zext(zext(zext(NewV)))
294  ExtendBy -= TruncBits;
295  return CastedValue(NewV, ZExtBits + SExtBits + ExtendBy, 0, 0);
296  }
297 
298  /// Replace V with sext(NewV)
299  CastedValue withSExtOfValue(const Value *NewV) const {
300  unsigned ExtendBy = V->getType()->getPrimitiveSizeInBits() -
301  NewV->getType()->getPrimitiveSizeInBits();
302  if (ExtendBy <= TruncBits)
303  return CastedValue(NewV, ZExtBits, SExtBits, TruncBits - ExtendBy);
304 
305  // zext(sext(sext(NewV)))
306  ExtendBy -= TruncBits;
307  return CastedValue(NewV, ZExtBits, SExtBits + ExtendBy, 0);
308  }
309 
310  APInt evaluateWith(APInt N) const {
311  assert(N.getBitWidth() == V->getType()->getPrimitiveSizeInBits() &&
312  "Incompatible bit width");
313  if (TruncBits) N = N.trunc(N.getBitWidth() - TruncBits);
314  if (SExtBits) N = N.sext(N.getBitWidth() + SExtBits);
315  if (ZExtBits) N = N.zext(N.getBitWidth() + ZExtBits);
316  return N;
317  }
318 
319  ConstantRange evaluateWith(ConstantRange N) const {
320  assert(N.getBitWidth() == V->getType()->getPrimitiveSizeInBits() &&
321  "Incompatible bit width");
322  if (TruncBits) N = N.truncate(N.getBitWidth() - TruncBits);
323  if (SExtBits) N = N.signExtend(N.getBitWidth() + SExtBits);
324  if (ZExtBits) N = N.zeroExtend(N.getBitWidth() + ZExtBits);
325  return N;
326  }
327 
328  bool canDistributeOver(bool NUW, bool NSW) const {
329  // zext(x op<nuw> y) == zext(x) op<nuw> zext(y)
330  // sext(x op<nsw> y) == sext(x) op<nsw> sext(y)
331  // trunc(x op y) == trunc(x) op trunc(y)
332  return (!ZExtBits || NUW) && (!SExtBits || NSW);
333  }
334 
335  bool hasSameCastsAs(const CastedValue &Other) const {
336  return ZExtBits == Other.ZExtBits && SExtBits == Other.SExtBits &&
337  TruncBits == Other.TruncBits;
338  }
339 };
340 
341 /// Represents zext(sext(trunc(V))) * Scale + Offset.
342 struct LinearExpression {
343  CastedValue Val;
344  APInt Scale;
345  APInt Offset;
346 
347  /// True if all operations in this expression are NSW.
348  bool IsNSW;
349 
350  LinearExpression(const CastedValue &Val, const APInt &Scale,
351  const APInt &Offset, bool IsNSW)
352  : Val(Val), Scale(Scale), Offset(Offset), IsNSW(IsNSW) {}
353 
354  LinearExpression(const CastedValue &Val) : Val(Val), IsNSW(true) {
355  unsigned BitWidth = Val.getBitWidth();
356  Scale = APInt(BitWidth, 1);
357  Offset = APInt(BitWidth, 0);
358  }
359 
360  LinearExpression mul(const APInt &Other, bool MulIsNSW) const {
361  // The check for zero offset is necessary, because generally
362  // (X +nsw Y) *nsw Z does not imply (X *nsw Z) +nsw (Y *nsw Z).
363  bool NSW = IsNSW && (Other.isOne() || (MulIsNSW && Offset.isZero()));
364  return LinearExpression(Val, Scale * Other, Offset * Other, NSW);
365  }
366 };
367 }
368 
369 /// Analyzes the specified value as a linear expression: "A*V + B", where A and
370 /// B are constant integers.
371 static LinearExpression GetLinearExpression(
372  const CastedValue &Val, const DataLayout &DL, unsigned Depth,
373  AssumptionCache *AC, DominatorTree *DT) {
374  // Limit our recursion depth.
375  if (Depth == 6)
376  return Val;
377 
378  if (const ConstantInt *Const = dyn_cast<ConstantInt>(Val.V))
379  return LinearExpression(Val, APInt(Val.getBitWidth(), 0),
380  Val.evaluateWith(Const->getValue()), true);
381 
382  if (const BinaryOperator *BOp = dyn_cast<BinaryOperator>(Val.V)) {
383  if (ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) {
384  APInt RHS = Val.evaluateWith(RHSC->getValue());
385  // The only non-OBO case we deal with is or, and only limited to the
386  // case where it is both nuw and nsw.
387  bool NUW = true, NSW = true;
388  if (isa<OverflowingBinaryOperator>(BOp)) {
389  NUW &= BOp->hasNoUnsignedWrap();
390  NSW &= BOp->hasNoSignedWrap();
391  }
392  if (!Val.canDistributeOver(NUW, NSW))
393  return Val;
394 
395  // While we can distribute over trunc, we cannot preserve nowrap flags
396  // in that case.
397  if (Val.TruncBits)
398  NUW = NSW = false;
399 
400  LinearExpression E(Val);
401  switch (BOp->getOpcode()) {
402  default:
403  // We don't understand this instruction, so we can't decompose it any
404  // further.
405  return Val;
406  case Instruction::Or:
407  // X|C == X+C if all the bits in C are unset in X. Otherwise we can't
408  // analyze it.
409  if (!MaskedValueIsZero(BOp->getOperand(0), RHSC->getValue(), DL, 0, AC,
410  BOp, DT))
411  return Val;
412 
414  case Instruction::Add: {
415  E = GetLinearExpression(Val.withValue(BOp->getOperand(0)), DL,
416  Depth + 1, AC, DT);
417  E.Offset += RHS;
418  E.IsNSW &= NSW;
419  break;
420  }
421  case Instruction::Sub: {
422  E = GetLinearExpression(Val.withValue(BOp->getOperand(0)), DL,
423  Depth + 1, AC, DT);
424  E.Offset -= RHS;
425  E.IsNSW &= NSW;
426  break;
427  }
428  case Instruction::Mul:
429  E = GetLinearExpression(Val.withValue(BOp->getOperand(0)), DL,
430  Depth + 1, AC, DT)
431  .mul(RHS, NSW);
432  break;
433  case Instruction::Shl:
434  // We're trying to linearize an expression of the kind:
435  // shl i8 -128, 36
436  // where the shift count exceeds the bitwidth of the type.
437  // We can't decompose this further (the expression would return
438  // a poison value).
439  if (RHS.getLimitedValue() > Val.getBitWidth())
440  return Val;
441 
442  E = GetLinearExpression(Val.withValue(BOp->getOperand(0)), DL,
443  Depth + 1, AC, DT);
444  E.Offset <<= RHS.getLimitedValue();
445  E.Scale <<= RHS.getLimitedValue();
446  E.IsNSW &= NSW;
447  break;
448  }
449  return E;
450  }
451  }
452 
453  if (isa<ZExtInst>(Val.V))
454  return GetLinearExpression(
455  Val.withZExtOfValue(cast<CastInst>(Val.V)->getOperand(0)),
456  DL, Depth + 1, AC, DT);
457 
458  if (isa<SExtInst>(Val.V))
459  return GetLinearExpression(
460  Val.withSExtOfValue(cast<CastInst>(Val.V)->getOperand(0)),
461  DL, Depth + 1, AC, DT);
462 
463  return Val;
464 }
465 
466 /// To ensure a pointer offset fits in an integer of size IndexSize
467 /// (in bits) when that size is smaller than the maximum index size. This is
468 /// an issue, for example, in particular for 32b pointers with negative indices
469 /// that rely on two's complement wrap-arounds for precise alias information
470 /// where the maximum index size is 64b.
471 static APInt adjustToIndexSize(const APInt &Offset, unsigned IndexSize) {
472  assert(IndexSize <= Offset.getBitWidth() && "Invalid IndexSize!");
473  unsigned ShiftBits = Offset.getBitWidth() - IndexSize;
474  return (Offset << ShiftBits).ashr(ShiftBits);
475 }
476 
477 namespace {
478 // A linear transformation of a Value; this class represents
479 // ZExt(SExt(Trunc(V, TruncBits), SExtBits), ZExtBits) * Scale.
480 struct VariableGEPIndex {
481  CastedValue Val;
482  APInt Scale;
483 
484  // Context instruction to use when querying information about this index.
485  const Instruction *CxtI;
486 
487  /// True if all operations in this expression are NSW.
488  bool IsNSW;
489 
490  void dump() const {
491  print(dbgs());
492  dbgs() << "\n";
493  }
494  void print(raw_ostream &OS) const {
495  OS << "(V=" << Val.V->getName()
496  << ", zextbits=" << Val.ZExtBits
497  << ", sextbits=" << Val.SExtBits
498  << ", truncbits=" << Val.TruncBits
499  << ", scale=" << Scale << ")";
500  }
501 };
502 }
503 
504 // Represents the internal structure of a GEP, decomposed into a base pointer,
505 // constant offsets, and variable scaled indices.
507  // Base pointer of the GEP
508  const Value *Base;
509  // Total constant offset from base.
511  // Scaled variable (non-constant) indices.
513  // Are all operations inbounds GEPs or non-indexing operations?
514  // (None iff expression doesn't involve any geps)
516 
517  void dump() const {
518  print(dbgs());
519  dbgs() << "\n";
520  }
521  void print(raw_ostream &OS) const {
522  OS << "(DecomposedGEP Base=" << Base->getName()
523  << ", Offset=" << Offset
524  << ", VarIndices=[";
525  for (size_t i = 0; i < VarIndices.size(); i++) {
526  if (i != 0)
527  OS << ", ";
528  VarIndices[i].print(OS);
529  }
530  OS << "])";
531  }
532 };
533 
534 
535 /// If V is a symbolic pointer expression, decompose it into a base pointer
536 /// with a constant offset and a number of scaled symbolic offsets.
537 ///
538 /// The scaled symbolic offsets (represented by pairs of a Value* and a scale
539 /// in the VarIndices vector) are Value*'s that are known to be scaled by the
540 /// specified amount, but which may have other unrepresented high bits. As
541 /// such, the gep cannot necessarily be reconstructed from its decomposed form.
543 BasicAAResult::DecomposeGEPExpression(const Value *V, const DataLayout &DL,
544  AssumptionCache *AC, DominatorTree *DT) {
545  // Limit recursion depth to limit compile time in crazy cases.
546  unsigned MaxLookup = MaxLookupSearchDepth;
547  SearchTimes++;
548  const Instruction *CxtI = dyn_cast<Instruction>(V);
549 
550  unsigned MaxIndexSize = DL.getMaxIndexSizeInBits();
551  DecomposedGEP Decomposed;
552  Decomposed.Offset = APInt(MaxIndexSize, 0);
553  do {
554  // See if this is a bitcast or GEP.
555  const Operator *Op = dyn_cast<Operator>(V);
556  if (!Op) {
557  // The only non-operator case we can handle are GlobalAliases.
558  if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
559  if (!GA->isInterposable()) {
560  V = GA->getAliasee();
561  continue;
562  }
563  }
564  Decomposed.Base = V;
565  return Decomposed;
566  }
567 
568  if (Op->getOpcode() == Instruction::BitCast ||
569  Op->getOpcode() == Instruction::AddrSpaceCast) {
570  V = Op->getOperand(0);
571  continue;
572  }
573 
574  const GEPOperator *GEPOp = dyn_cast<GEPOperator>(Op);
575  if (!GEPOp) {
576  if (const auto *PHI = dyn_cast<PHINode>(V)) {
577  // Look through single-arg phi nodes created by LCSSA.
578  if (PHI->getNumIncomingValues() == 1) {
579  V = PHI->getIncomingValue(0);
580  continue;
581  }
582  } else if (const auto *Call = dyn_cast<CallBase>(V)) {
583  // CaptureTracking can know about special capturing properties of some
584  // intrinsics like launder.invariant.group, that can't be expressed with
585  // the attributes, but have properties like returning aliasing pointer.
586  // Because some analysis may assume that nocaptured pointer is not
587  // returned from some special intrinsic (because function would have to
588  // be marked with returns attribute), it is crucial to use this function
589  // because it should be in sync with CaptureTracking. Not using it may
590  // cause weird miscompilations where 2 aliasing pointers are assumed to
591  // noalias.
592  if (auto *RP = getArgumentAliasingToReturnedPointer(Call, false)) {
593  V = RP;
594  continue;
595  }
596  }
597 
598  Decomposed.Base = V;
599  return Decomposed;
600  }
601 
602  // Track whether we've seen at least one in bounds gep, and if so, whether
603  // all geps parsed were in bounds.
604  if (Decomposed.InBounds == None)
605  Decomposed.InBounds = GEPOp->isInBounds();
606  else if (!GEPOp->isInBounds())
607  Decomposed.InBounds = false;
608 
609  assert(GEPOp->getSourceElementType()->isSized() && "GEP must be sized");
610 
611  // Don't attempt to analyze GEPs if index scale is not a compile-time
612  // constant.
613  if (isa<ScalableVectorType>(GEPOp->getSourceElementType())) {
614  Decomposed.Base = V;
615  return Decomposed;
616  }
617 
618  unsigned AS = GEPOp->getPointerAddressSpace();
619  // Walk the indices of the GEP, accumulating them into BaseOff/VarIndices.
620  gep_type_iterator GTI = gep_type_begin(GEPOp);
621  unsigned IndexSize = DL.getIndexSizeInBits(AS);
622  // Assume all GEP operands are constants until proven otherwise.
623  bool GepHasConstantOffset = true;
624  for (User::const_op_iterator I = GEPOp->op_begin() + 1, E = GEPOp->op_end();
625  I != E; ++I, ++GTI) {
626  const Value *Index = *I;
627  // Compute the (potentially symbolic) offset in bytes for this index.
628  if (StructType *STy = GTI.getStructTypeOrNull()) {
629  // For a struct, add the member offset.
630  unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue();
631  if (FieldNo == 0)
632  continue;
633 
634  Decomposed.Offset += DL.getStructLayout(STy)->getElementOffset(FieldNo);
635  continue;
636  }
637 
638  // For an array/pointer, add the element offset, explicitly scaled.
639  if (const ConstantInt *CIdx = dyn_cast<ConstantInt>(Index)) {
640  if (CIdx->isZero())
641  continue;
642  Decomposed.Offset +=
643  DL.getTypeAllocSize(GTI.getIndexedType()).getFixedSize() *
644  CIdx->getValue().sextOrTrunc(MaxIndexSize);
645  continue;
646  }
647 
648  GepHasConstantOffset = false;
649 
650  // If the integer type is smaller than the index size, it is implicitly
651  // sign extended or truncated to index size.
652  unsigned Width = Index->getType()->getIntegerBitWidth();
653  unsigned SExtBits = IndexSize > Width ? IndexSize - Width : 0;
654  unsigned TruncBits = IndexSize < Width ? Width - IndexSize : 0;
655  LinearExpression LE = GetLinearExpression(
656  CastedValue(Index, 0, SExtBits, TruncBits), DL, 0, AC, DT);
657 
658  // Scale by the type size.
659  unsigned TypeSize =
660  DL.getTypeAllocSize(GTI.getIndexedType()).getFixedSize();
661  LE = LE.mul(APInt(IndexSize, TypeSize), GEPOp->isInBounds());
662  Decomposed.Offset += LE.Offset.sext(MaxIndexSize);
663  APInt Scale = LE.Scale.sext(MaxIndexSize);
664 
665  // If we already had an occurrence of this index variable, merge this
666  // scale into it. For example, we want to handle:
667  // A[x][x] -> x*16 + x*4 -> x*20
668  // This also ensures that 'x' only appears in the index list once.
669  for (unsigned i = 0, e = Decomposed.VarIndices.size(); i != e; ++i) {
670  if (Decomposed.VarIndices[i].Val.V == LE.Val.V &&
671  Decomposed.VarIndices[i].Val.hasSameCastsAs(LE.Val)) {
672  Scale += Decomposed.VarIndices[i].Scale;
673  Decomposed.VarIndices.erase(Decomposed.VarIndices.begin() + i);
674  break;
675  }
676  }
677 
678  // Make sure that we have a scale that makes sense for this target's
679  // index size.
680  Scale = adjustToIndexSize(Scale, IndexSize);
681 
682  if (!!Scale) {
683  VariableGEPIndex Entry = {LE.Val, Scale, CxtI, LE.IsNSW};
684  Decomposed.VarIndices.push_back(Entry);
685  }
686  }
687 
688  // Take care of wrap-arounds
689  if (GepHasConstantOffset)
690  Decomposed.Offset = adjustToIndexSize(Decomposed.Offset, IndexSize);
691 
692  // Analyze the base pointer next.
693  V = GEPOp->getOperand(0);
694  } while (--MaxLookup);
695 
696  // If the chain of expressions is too deep, just return early.
697  Decomposed.Base = V;
698  SearchLimitReached++;
699  return Decomposed;
700 }
701 
702 /// Returns whether the given pointer value points to memory that is local to
703 /// the function, with global constants being considered local to all
704 /// functions.
706  AAQueryInfo &AAQI, bool OrLocal) {
707  assert(Visited.empty() && "Visited must be cleared after use!");
708 
709  unsigned MaxLookup = 8;
711  Worklist.push_back(Loc.Ptr);
712  do {
713  const Value *V = getUnderlyingObject(Worklist.pop_back_val());
714  if (!Visited.insert(V).second) {
715  Visited.clear();
716  return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal);
717  }
718 
719  // An alloca instruction defines local memory.
720  if (OrLocal && isa<AllocaInst>(V))
721  continue;
722 
723  // A global constant counts as local memory for our purposes.
724  if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) {
725  // Note: this doesn't require GV to be "ODR" because it isn't legal for a
726  // global to be marked constant in some modules and non-constant in
727  // others. GV may even be a declaration, not a definition.
728  if (!GV->isConstant()) {
729  Visited.clear();
730  return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal);
731  }
732  continue;
733  }
734 
735  // If both select values point to local memory, then so does the select.
736  if (const SelectInst *SI = dyn_cast<SelectInst>(V)) {
737  Worklist.push_back(SI->getTrueValue());
738  Worklist.push_back(SI->getFalseValue());
739  continue;
740  }
741 
742  // If all values incoming to a phi node point to local memory, then so does
743  // the phi.
744  if (const PHINode *PN = dyn_cast<PHINode>(V)) {
745  // Don't bother inspecting phi nodes with many operands.
746  if (PN->getNumIncomingValues() > MaxLookup) {
747  Visited.clear();
748  return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal);
749  }
750  append_range(Worklist, PN->incoming_values());
751  continue;
752  }
753 
754  // Otherwise be conservative.
755  Visited.clear();
756  return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal);
757  } while (!Worklist.empty() && --MaxLookup);
758 
759  Visited.clear();
760  return Worklist.empty();
761 }
762 
763 static bool isIntrinsicCall(const CallBase *Call, Intrinsic::ID IID) {
764  const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Call);
765  return II && II->getIntrinsicID() == IID;
766 }
767 
768 /// Returns the behavior when calling the given call site.
770  if (Call->doesNotAccessMemory())
771  // Can't do better than this.
773 
775 
776  // If the callsite knows it only reads memory, don't return worse
777  // than that.
778  if (Call->onlyReadsMemory())
779  Min = FMRB_OnlyReadsMemory;
780  else if (Call->onlyWritesMemory())
781  Min = FMRB_OnlyWritesMemory;
782 
783  if (Call->onlyAccessesArgMemory())
785  else if (Call->onlyAccessesInaccessibleMemory())
787  else if (Call->onlyAccessesInaccessibleMemOrArgMem())
789 
790  // If the call has operand bundles then aliasing attributes from the function
791  // it calls do not directly apply to the call. This can be made more precise
792  // in the future.
793  if (!Call->hasOperandBundles())
794  if (const Function *F = Call->getCalledFunction())
795  Min =
797 
798  return Min;
799 }
800 
801 /// Returns the behavior when calling the given function. For use when the call
802 /// site is not known.
804  // If the function declares it doesn't access memory, we can't do better.
805  if (F->doesNotAccessMemory())
807 
809 
810  // If the function declares it only reads memory, go with that.
811  if (F->onlyReadsMemory())
812  Min = FMRB_OnlyReadsMemory;
813  else if (F->onlyWritesMemory())
814  Min = FMRB_OnlyWritesMemory;
815 
816  if (F->onlyAccessesArgMemory())
818  else if (F->onlyAccessesInaccessibleMemory())
820  else if (F->onlyAccessesInaccessibleMemOrArgMem())
822 
823  return Min;
824 }
825 
826 /// Returns true if this is a writeonly (i.e Mod only) parameter.
827 static bool isWriteOnlyParam(const CallBase *Call, unsigned ArgIdx,
828  const TargetLibraryInfo &TLI) {
829  if (Call->paramHasAttr(ArgIdx, Attribute::WriteOnly))
830  return true;
831 
832  // We can bound the aliasing properties of memset_pattern16 just as we can
833  // for memcpy/memset. This is particularly important because the
834  // LoopIdiomRecognizer likes to turn loops into calls to memset_pattern16
835  // whenever possible.
836  // FIXME Consider handling this in InferFunctionAttr.cpp together with other
837  // attributes.
838  LibFunc F;
839  if (Call->getCalledFunction() &&
840  TLI.getLibFunc(*Call->getCalledFunction(), F) &&
841  F == LibFunc_memset_pattern16 && TLI.has(F))
842  if (ArgIdx == 0)
843  return true;
844 
845  // TODO: memset_pattern4, memset_pattern8
846  // TODO: _chk variants
847  // TODO: strcmp, strcpy
848 
849  return false;
850 }
851 
853  unsigned ArgIdx) {
854  // Checking for known builtin intrinsics and target library functions.
855  if (isWriteOnlyParam(Call, ArgIdx, TLI))
856  return ModRefInfo::Mod;
857 
858  if (Call->paramHasAttr(ArgIdx, Attribute::ReadOnly))
859  return ModRefInfo::Ref;
860 
861  if (Call->paramHasAttr(ArgIdx, Attribute::ReadNone))
862  return ModRefInfo::NoModRef;
863 
864  return AAResultBase::getArgModRefInfo(Call, ArgIdx);
865 }
866 
867 #ifndef NDEBUG
868 static const Function *getParent(const Value *V) {
869  if (const Instruction *inst = dyn_cast<Instruction>(V)) {
870  if (!inst->getParent())
871  return nullptr;
872  return inst->getParent()->getParent();
873  }
874 
875  if (const Argument *arg = dyn_cast<Argument>(V))
876  return arg->getParent();
877 
878  return nullptr;
879 }
880 
881 static bool notDifferentParent(const Value *O1, const Value *O2) {
882 
883  const Function *F1 = getParent(O1);
884  const Function *F2 = getParent(O2);
885 
886  return !F1 || !F2 || F1 == F2;
887 }
888 #endif
889 
891  const MemoryLocation &LocB,
892  AAQueryInfo &AAQI) {
893  assert(notDifferentParent(LocA.Ptr, LocB.Ptr) &&
894  "BasicAliasAnalysis doesn't support interprocedural queries.");
895  return aliasCheck(LocA.Ptr, LocA.Size, LocB.Ptr, LocB.Size, AAQI);
896 }
897 
898 /// Checks to see if the specified callsite can clobber the specified memory
899 /// object.
900 ///
901 /// Since we only look at local properties of this function, we really can't
902 /// say much about this query. We do, however, use simple "address taken"
903 /// analysis on local objects.
905  const MemoryLocation &Loc,
906  AAQueryInfo &AAQI) {
907  assert(notDifferentParent(Call, Loc.Ptr) &&
908  "AliasAnalysis query involving multiple functions!");
909 
910  const Value *Object = getUnderlyingObject(Loc.Ptr);
911 
912  // Calls marked 'tail' cannot read or write allocas from the current frame
913  // because the current frame might be destroyed by the time they run. However,
914  // a tail call may use an alloca with byval. Calling with byval copies the
915  // contents of the alloca into argument registers or stack slots, so there is
916  // no lifetime issue.
917  if (isa<AllocaInst>(Object))
918  if (const CallInst *CI = dyn_cast<CallInst>(Call))
919  if (CI->isTailCall() &&
920  !CI->getAttributes().hasAttrSomewhere(Attribute::ByVal))
921  return ModRefInfo::NoModRef;
922 
923  // Stack restore is able to modify unescaped dynamic allocas. Assume it may
924  // modify them even though the alloca is not escaped.
925  if (auto *AI = dyn_cast<AllocaInst>(Object))
926  if (!AI->isStaticAlloca() && isIntrinsicCall(Call, Intrinsic::stackrestore))
927  return ModRefInfo::Mod;
928 
929  // If the pointer is to a locally allocated object that does not escape,
930  // then the call can not mod/ref the pointer unless the call takes the pointer
931  // as an argument, and itself doesn't capture it.
932  if (!isa<Constant>(Object) && Call != Object &&
933  AAQI.CI->isNotCapturedBeforeOrAt(Object, Call)) {
934 
935  // Optimistically assume that call doesn't touch Object and check this
936  // assumption in the following loop.
938  bool IsMustAlias = true;
939 
940  unsigned OperandNo = 0;
941  for (auto CI = Call->data_operands_begin(), CE = Call->data_operands_end();
942  CI != CE; ++CI, ++OperandNo) {
943  // Only look at the no-capture or byval pointer arguments. If this
944  // pointer were passed to arguments that were neither of these, then it
945  // couldn't be no-capture.
946  if (!(*CI)->getType()->isPointerTy() ||
947  (!Call->doesNotCapture(OperandNo) && OperandNo < Call->arg_size() &&
948  !Call->isByValArgument(OperandNo)))
949  continue;
950 
951  // Call doesn't access memory through this operand, so we don't care
952  // if it aliases with Object.
953  if (Call->doesNotAccessMemory(OperandNo))
954  continue;
955 
956  // If this is a no-capture pointer argument, see if we can tell that it
957  // is impossible to alias the pointer we're checking.
958  AliasResult AR = getBestAAResults().alias(
961  if (AR != AliasResult::MustAlias)
962  IsMustAlias = false;
963  // Operand doesn't alias 'Object', continue looking for other aliases
964  if (AR == AliasResult::NoAlias)
965  continue;
966  // Operand aliases 'Object', but call doesn't modify it. Strengthen
967  // initial assumption and keep looking in case if there are more aliases.
968  if (Call->onlyReadsMemory(OperandNo)) {
969  Result = setRef(Result);
970  continue;
971  }
972  // Operand aliases 'Object' but call only writes into it.
973  if (Call->onlyWritesMemory(OperandNo)) {
974  Result = setMod(Result);
975  continue;
976  }
977  // This operand aliases 'Object' and call reads and writes into it.
978  // Setting ModRef will not yield an early return below, MustAlias is not
979  // used further.
980  Result = ModRefInfo::ModRef;
981  break;
982  }
983 
984  // No operand aliases, reset Must bit. Add below if at least one aliases
985  // and all aliases found are MustAlias.
986  if (isNoModRef(Result))
987  IsMustAlias = false;
988 
989  // Early return if we improved mod ref information
990  if (!isModAndRefSet(Result)) {
991  if (isNoModRef(Result))
992  return ModRefInfo::NoModRef;
993  return IsMustAlias ? setMust(Result) : clearMust(Result);
994  }
995  }
996 
997  // If the call is malloc/calloc like, we can assume that it doesn't
998  // modify any IR visible value. This is only valid because we assume these
999  // routines do not read values visible in the IR. TODO: Consider special
1000  // casing realloc and strdup routines which access only their arguments as
1001  // well. Or alternatively, replace all of this with inaccessiblememonly once
1002  // that's implemented fully.
1003  if (isMallocOrCallocLikeFn(Call, &TLI)) {
1004  // Be conservative if the accessed pointer may alias the allocation -
1005  // fallback to the generic handling below.
1007  AAQI) == AliasResult::NoAlias)
1008  return ModRefInfo::NoModRef;
1009  }
1010 
1011  // Ideally, there should be no need to special case for memcpy/memove
1012  // intrinsics here since general machinery (based on memory attributes) should
1013  // already handle it just fine. Unfortunately, it doesn't due to deficiency in
1014  // operand bundles support. At the moment it's not clear if complexity behind
1015  // enhancing general mechanism worths it.
1016  // TODO: Consider improving operand bundles support in general mechanism.
1017  if (auto *Inst = dyn_cast<AnyMemTransferInst>(Call)) {
1018  AliasResult SrcAA =
1019  getBestAAResults().alias(MemoryLocation::getForSource(Inst), Loc, AAQI);
1020  AliasResult DestAA =
1021  getBestAAResults().alias(MemoryLocation::getForDest(Inst), Loc, AAQI);
1022  // It's also possible for Loc to alias both src and dest, or neither.
1024  if (SrcAA != AliasResult::NoAlias || Call->hasReadingOperandBundles())
1025  rv = setRef(rv);
1026  if (DestAA != AliasResult::NoAlias || Call->hasClobberingOperandBundles())
1027  rv = setMod(rv);
1028  return rv;
1029  }
1030 
1031  // Guard intrinsics are marked as arbitrarily writing so that proper control
1032  // dependencies are maintained but they never mods any particular memory
1033  // location.
1034  //
1035  // *Unlike* assumes, guard intrinsics are modeled as reading memory since the
1036  // heap state at the point the guard is issued needs to be consistent in case
1037  // the guard invokes the "deopt" continuation.
1038  if (isIntrinsicCall(Call, Intrinsic::experimental_guard))
1039  return ModRefInfo::Ref;
1040  // The same applies to deoptimize which is essentially a guard(false).
1041  if (isIntrinsicCall(Call, Intrinsic::experimental_deoptimize))
1042  return ModRefInfo::Ref;
1043 
1044  // Like assumes, invariant.start intrinsics were also marked as arbitrarily
1045  // writing so that proper control dependencies are maintained but they never
1046  // mod any particular memory location visible to the IR.
1047  // *Unlike* assumes (which are now modeled as NoModRef), invariant.start
1048  // intrinsic is now modeled as reading memory. This prevents hoisting the
1049  // invariant.start intrinsic over stores. Consider:
1050  // *ptr = 40;
1051  // *ptr = 50;
1052  // invariant_start(ptr)
1053  // int val = *ptr;
1054  // print(val);
1055  //
1056  // This cannot be transformed to:
1057  //
1058  // *ptr = 40;
1059  // invariant_start(ptr)
1060  // *ptr = 50;
1061  // int val = *ptr;
1062  // print(val);
1063  //
1064  // The transformation will cause the second store to be ignored (based on
1065  // rules of invariant.start) and print 40, while the first program always
1066  // prints 50.
1067  if (isIntrinsicCall(Call, Intrinsic::invariant_start))
1068  return ModRefInfo::Ref;
1069 
1070  // The AAResultBase base class has some smarts, lets use them.
1071  return AAResultBase::getModRefInfo(Call, Loc, AAQI);
1072 }
1073 
1075  const CallBase *Call2,
1076  AAQueryInfo &AAQI) {
1077  // Guard intrinsics are marked as arbitrarily writing so that proper control
1078  // dependencies are maintained but they never mods any particular memory
1079  // location.
1080  //
1081  // *Unlike* assumes, guard intrinsics are modeled as reading memory since the
1082  // heap state at the point the guard is issued needs to be consistent in case
1083  // the guard invokes the "deopt" continuation.
1084 
1085  // NB! This function is *not* commutative, so we special case two
1086  // possibilities for guard intrinsics.
1087 
1088  if (isIntrinsicCall(Call1, Intrinsic::experimental_guard))
1090  ? ModRefInfo::Ref
1092 
1093  if (isIntrinsicCall(Call2, Intrinsic::experimental_guard))
1095  ? ModRefInfo::Mod
1097 
1098  // The AAResultBase base class has some smarts, lets use them.
1099  return AAResultBase::getModRefInfo(Call1, Call2, AAQI);
1100 }
1101 
1102 /// Return true if we know V to the base address of the corresponding memory
1103 /// object. This implies that any address less than V must be out of bounds
1104 /// for the underlying object. Note that just being isIdentifiedObject() is
1105 /// not enough - For example, a negative offset from a noalias argument or call
1106 /// can be inbounds w.r.t the actual underlying object.
1107 static bool isBaseOfObject(const Value *V) {
1108  // TODO: We can handle other cases here
1109  // 1) For GC languages, arguments to functions are often required to be
1110  // base pointers.
1111  // 2) Result of allocation routines are often base pointers. Leverage TLI.
1112  return (isa<AllocaInst>(V) || isa<GlobalVariable>(V));
1113 }
1114 
1115 /// Provides a bunch of ad-hoc rules to disambiguate a GEP instruction against
1116 /// another pointer.
1117 ///
1118 /// We know that V1 is a GEP, but we don't know anything about V2.
1119 /// UnderlyingV1 is getUnderlyingObject(GEP1), UnderlyingV2 is the same for
1120 /// V2.
1121 AliasResult BasicAAResult::aliasGEP(
1122  const GEPOperator *GEP1, LocationSize V1Size,
1123  const Value *V2, LocationSize V2Size,
1124  const Value *UnderlyingV1, const Value *UnderlyingV2, AAQueryInfo &AAQI) {
1125  if (!V1Size.hasValue() && !V2Size.hasValue()) {
1126  // TODO: This limitation exists for compile-time reasons. Relax it if we
1127  // can avoid exponential pathological cases.
1128  if (!isa<GEPOperator>(V2))
1129  return AliasResult::MayAlias;
1130 
1131  // If both accesses have unknown size, we can only check whether the base
1132  // objects don't alias.
1133  AliasResult BaseAlias = getBestAAResults().alias(
1134  MemoryLocation::getBeforeOrAfter(UnderlyingV1),
1135  MemoryLocation::getBeforeOrAfter(UnderlyingV2), AAQI);
1136  return BaseAlias == AliasResult::NoAlias ? AliasResult::NoAlias
1138  }
1139 
1140  DecomposedGEP DecompGEP1 = DecomposeGEPExpression(GEP1, DL, &AC, DT);
1141  DecomposedGEP DecompGEP2 = DecomposeGEPExpression(V2, DL, &AC, DT);
1142 
1143  // Bail if we were not able to decompose anything.
1144  if (DecompGEP1.Base == GEP1 && DecompGEP2.Base == V2)
1145  return AliasResult::MayAlias;
1146 
1147  // Subtract the GEP2 pointer from the GEP1 pointer to find out their
1148  // symbolic difference.
1149  subtractDecomposedGEPs(DecompGEP1, DecompGEP2);
1150 
1151  // If an inbounds GEP would have to start from an out of bounds address
1152  // for the two to alias, then we can assume noalias.
1153  if (*DecompGEP1.InBounds && DecompGEP1.VarIndices.empty() &&
1154  V2Size.hasValue() && DecompGEP1.Offset.sge(V2Size.getValue()) &&
1155  isBaseOfObject(DecompGEP2.Base))
1156  return AliasResult::NoAlias;
1157 
1158  if (isa<GEPOperator>(V2)) {
1159  // Symmetric case to above.
1160  if (*DecompGEP2.InBounds && DecompGEP1.VarIndices.empty() &&
1161  V1Size.hasValue() && DecompGEP1.Offset.sle(-V1Size.getValue()) &&
1162  isBaseOfObject(DecompGEP1.Base))
1163  return AliasResult::NoAlias;
1164  }
1165 
1166  // For GEPs with identical offsets, we can preserve the size and AAInfo
1167  // when performing the alias check on the underlying objects.
1168  if (DecompGEP1.Offset == 0 && DecompGEP1.VarIndices.empty())
1169  return getBestAAResults().alias(MemoryLocation(DecompGEP1.Base, V1Size),
1170  MemoryLocation(DecompGEP2.Base, V2Size),
1171  AAQI);
1172 
1173  // Do the base pointers alias?
1174  AliasResult BaseAlias = getBestAAResults().alias(
1175  MemoryLocation::getBeforeOrAfter(DecompGEP1.Base),
1176  MemoryLocation::getBeforeOrAfter(DecompGEP2.Base), AAQI);
1177 
1178  // If we get a No or May, then return it immediately, no amount of analysis
1179  // will improve this situation.
1180  if (BaseAlias != AliasResult::MustAlias) {
1181  assert(BaseAlias == AliasResult::NoAlias ||
1182  BaseAlias == AliasResult::MayAlias);
1183  return BaseAlias;
1184  }
1185 
1186  // If there is a constant difference between the pointers, but the difference
1187  // is less than the size of the associated memory object, then we know
1188  // that the objects are partially overlapping. If the difference is
1189  // greater, we know they do not overlap.
1190  if (DecompGEP1.VarIndices.empty()) {
1191  APInt &Off = DecompGEP1.Offset;
1192 
1193  // Initialize for Off >= 0 (V2 <= GEP1) case.
1194  const Value *LeftPtr = V2;
1195  const Value *RightPtr = GEP1;
1196  LocationSize VLeftSize = V2Size;
1197  LocationSize VRightSize = V1Size;
1198  const bool Swapped = Off.isNegative();
1199 
1200  if (Swapped) {
1201  // Swap if we have the situation where:
1202  // + +
1203  // | BaseOffset |
1204  // ---------------->|
1205  // |-->V1Size |-------> V2Size
1206  // GEP1 V2
1207  std::swap(LeftPtr, RightPtr);
1208  std::swap(VLeftSize, VRightSize);
1209  Off = -Off;
1210  }
1211 
1212  if (!VLeftSize.hasValue())
1213  return AliasResult::MayAlias;
1214 
1215  const uint64_t LSize = VLeftSize.getValue();
1216  if (Off.ult(LSize)) {
1217  // Conservatively drop processing if a phi was visited and/or offset is
1218  // too big.
1220  if (VRightSize.hasValue() && Off.ule(INT32_MAX) &&
1221  (Off + VRightSize.getValue()).ule(LSize)) {
1222  // Memory referenced by right pointer is nested. Save the offset in
1223  // cache. Note that originally offset estimated as GEP1-V2, but
1224  // AliasResult contains the shift that represents GEP1+Offset=V2.
1225  AR.setOffset(-Off.getSExtValue());
1226  AR.swap(Swapped);
1227  }
1228  return AR;
1229  }
1230  return AliasResult::NoAlias;
1231  }
1232 
1233  // We need to know both acess sizes for all the following heuristics.
1234  if (!V1Size.hasValue() || !V2Size.hasValue())
1235  return AliasResult::MayAlias;
1236 
1237  APInt GCD;
1238  ConstantRange OffsetRange = ConstantRange(DecompGEP1.Offset);
1239  for (unsigned i = 0, e = DecompGEP1.VarIndices.size(); i != e; ++i) {
1240  const VariableGEPIndex &Index = DecompGEP1.VarIndices[i];
1241  const APInt &Scale = Index.Scale;
1242  APInt ScaleForGCD = Scale;
1243  if (!Index.IsNSW)
1244  ScaleForGCD = APInt::getOneBitSet(Scale.getBitWidth(),
1245  Scale.countTrailingZeros());
1246 
1247  if (i == 0)
1248  GCD = ScaleForGCD.abs();
1249  else
1250  GCD = APIntOps::GreatestCommonDivisor(GCD, ScaleForGCD.abs());
1251 
1252  ConstantRange CR = computeConstantRange(Index.Val.V, /* ForSigned */ false,
1253  true, &AC, Index.CxtI);
1254  KnownBits Known =
1255  computeKnownBits(Index.Val.V, DL, 0, &AC, Index.CxtI, DT);
1256  CR = CR.intersectWith(
1257  ConstantRange::fromKnownBits(Known, /* Signed */ true),
1259  CR = Index.Val.evaluateWith(CR).sextOrTrunc(OffsetRange.getBitWidth());
1260 
1261  assert(OffsetRange.getBitWidth() == Scale.getBitWidth() &&
1262  "Bit widths are normalized to MaxIndexSize");
1263  if (Index.IsNSW)
1264  OffsetRange = OffsetRange.add(CR.smul_sat(ConstantRange(Scale)));
1265  else
1266  OffsetRange = OffsetRange.add(CR.smul_fast(ConstantRange(Scale)));
1267  }
1268 
1269  // We now have accesses at two offsets from the same base:
1270  // 1. (...)*GCD + DecompGEP1.Offset with size V1Size
1271  // 2. 0 with size V2Size
1272  // Using arithmetic modulo GCD, the accesses are at
1273  // [ModOffset..ModOffset+V1Size) and [0..V2Size). If the first access fits
1274  // into the range [V2Size..GCD), then we know they cannot overlap.
1275  APInt ModOffset = DecompGEP1.Offset.srem(GCD);
1276  if (ModOffset.isNegative())
1277  ModOffset += GCD; // We want mod, not rem.
1278  if (ModOffset.uge(V2Size.getValue()) &&
1279  (GCD - ModOffset).uge(V1Size.getValue()))
1280  return AliasResult::NoAlias;
1281 
1282  // Compute ranges of potentially accessed bytes for both accesses. If the
1283  // interseciton is empty, there can be no overlap.
1284  unsigned BW = OffsetRange.getBitWidth();
1285  ConstantRange Range1 = OffsetRange.add(
1286  ConstantRange(APInt(BW, 0), APInt(BW, V1Size.getValue())));
1287  ConstantRange Range2 =
1288  ConstantRange(APInt(BW, 0), APInt(BW, V2Size.getValue()));
1289  if (Range1.intersectWith(Range2).isEmptySet())
1290  return AliasResult::NoAlias;
1291 
1292  // Try to determine the range of values for VarIndex such that
1293  // VarIndex <= -MinAbsVarIndex || MinAbsVarIndex <= VarIndex.
1294  Optional<APInt> MinAbsVarIndex;
1295  if (DecompGEP1.VarIndices.size() == 1) {
1296  // VarIndex = Scale*V.
1297  const VariableGEPIndex &Var = DecompGEP1.VarIndices[0];
1298  if (Var.Val.TruncBits == 0 &&
1299  isKnownNonZero(Var.Val.V, DL, 0, &AC, Var.CxtI, DT)) {
1300  // If V != 0, then abs(VarIndex) > 0.
1301  MinAbsVarIndex = APInt(Var.Scale.getBitWidth(), 1);
1302 
1303  // Check if abs(V*Scale) >= abs(Scale) holds in the presence of
1304  // potentially wrapping math.
1305  auto MultiplyByScaleNoWrap = [](const VariableGEPIndex &Var) {
1306  if (Var.IsNSW)
1307  return true;
1308 
1309  int ValOrigBW = Var.Val.V->getType()->getPrimitiveSizeInBits();
1310  // If Scale is small enough so that abs(V*Scale) >= abs(Scale) holds.
1311  // The max value of abs(V) is 2^ValOrigBW - 1. Multiplying with a
1312  // constant smaller than 2^(bitwidth(Val) - ValOrigBW) won't wrap.
1313  int MaxScaleValueBW = Var.Val.getBitWidth() - ValOrigBW;
1314  if (MaxScaleValueBW <= 0)
1315  return false;
1316  return Var.Scale.ule(
1317  APInt::getMaxValue(MaxScaleValueBW).zext(Var.Scale.getBitWidth()));
1318  };
1319  // Refine MinAbsVarIndex, if abs(Scale*V) >= abs(Scale) holds in the
1320  // presence of potentially wrapping math.
1321  if (MultiplyByScaleNoWrap(Var)) {
1322  // If V != 0 then abs(VarIndex) >= abs(Scale).
1323  MinAbsVarIndex = Var.Scale.abs();
1324  }
1325  }
1326  } else if (DecompGEP1.VarIndices.size() == 2) {
1327  // VarIndex = Scale*V0 + (-Scale)*V1.
1328  // If V0 != V1 then abs(VarIndex) >= abs(Scale).
1329  // Check that VisitedPhiBBs is empty, to avoid reasoning about
1330  // inequality of values across loop iterations.
1331  const VariableGEPIndex &Var0 = DecompGEP1.VarIndices[0];
1332  const VariableGEPIndex &Var1 = DecompGEP1.VarIndices[1];
1333  if (Var0.Scale == -Var1.Scale && Var0.Val.TruncBits == 0 &&
1334  Var0.Val.hasSameCastsAs(Var1.Val) && VisitedPhiBBs.empty() &&
1335  isKnownNonEqual(Var0.Val.V, Var1.Val.V, DL, &AC, /* CxtI */ nullptr,
1336  DT))
1337  MinAbsVarIndex = Var0.Scale.abs();
1338  }
1339 
1340  if (MinAbsVarIndex) {
1341  // The constant offset will have added at least +/-MinAbsVarIndex to it.
1342  APInt OffsetLo = DecompGEP1.Offset - *MinAbsVarIndex;
1343  APInt OffsetHi = DecompGEP1.Offset + *MinAbsVarIndex;
1344  // We know that Offset <= OffsetLo || Offset >= OffsetHi
1345  if (OffsetLo.isNegative() && (-OffsetLo).uge(V1Size.getValue()) &&
1346  OffsetHi.isNonNegative() && OffsetHi.uge(V2Size.getValue()))
1347  return AliasResult::NoAlias;
1348  }
1349 
1350  if (constantOffsetHeuristic(DecompGEP1, V1Size, V2Size, &AC, DT))
1351  return AliasResult::NoAlias;
1352 
1353  // Statically, we can see that the base objects are the same, but the
1354  // pointers have dynamic offsets which we can't resolve. And none of our
1355  // little tricks above worked.
1356  return AliasResult::MayAlias;
1357 }
1358 
1360  // If the results agree, take it.
1361  if (A == B)
1362  return A;
1363  // A mix of PartialAlias and MustAlias is PartialAlias.
1367  // Otherwise, we don't know anything.
1368  return AliasResult::MayAlias;
1369 }
1370 
1371 /// Provides a bunch of ad-hoc rules to disambiguate a Select instruction
1372 /// against another.
1374 BasicAAResult::aliasSelect(const SelectInst *SI, LocationSize SISize,
1375  const Value *V2, LocationSize V2Size,
1376  AAQueryInfo &AAQI) {
1377  // If the values are Selects with the same condition, we can do a more precise
1378  // check: just check for aliases between the values on corresponding arms.
1379  if (const SelectInst *SI2 = dyn_cast<SelectInst>(V2))
1380  if (SI->getCondition() == SI2->getCondition()) {
1381  AliasResult Alias = getBestAAResults().alias(
1382  MemoryLocation(SI->getTrueValue(), SISize),
1383  MemoryLocation(SI2->getTrueValue(), V2Size), AAQI);
1384  if (Alias == AliasResult::MayAlias)
1385  return AliasResult::MayAlias;
1386  AliasResult ThisAlias = getBestAAResults().alias(
1387  MemoryLocation(SI->getFalseValue(), SISize),
1388  MemoryLocation(SI2->getFalseValue(), V2Size), AAQI);
1389  return MergeAliasResults(ThisAlias, Alias);
1390  }
1391 
1392  // If both arms of the Select node NoAlias or MustAlias V2, then returns
1393  // NoAlias / MustAlias. Otherwise, returns MayAlias.
1394  AliasResult Alias =
1395  getBestAAResults().alias(MemoryLocation(SI->getTrueValue(), SISize),
1396  MemoryLocation(V2, V2Size), AAQI);
1397  if (Alias == AliasResult::MayAlias)
1398  return AliasResult::MayAlias;
1399 
1400  AliasResult ThisAlias =
1401  getBestAAResults().alias(MemoryLocation(SI->getFalseValue(), SISize),
1402  MemoryLocation(V2, V2Size), AAQI);
1403  return MergeAliasResults(ThisAlias, Alias);
1404 }
1405 
1406 /// Provide a bunch of ad-hoc rules to disambiguate a PHI instruction against
1407 /// another.
1408 AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize,
1409  const Value *V2, LocationSize V2Size,
1410  AAQueryInfo &AAQI) {
1411  if (!PN->getNumIncomingValues())
1412  return AliasResult::NoAlias;
1413  // If the values are PHIs in the same block, we can do a more precise
1414  // as well as efficient check: just check for aliases between the values
1415  // on corresponding edges.
1416  if (const PHINode *PN2 = dyn_cast<PHINode>(V2))
1417  if (PN2->getParent() == PN->getParent()) {
1418  Optional<AliasResult> Alias;
1419  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1420  AliasResult ThisAlias = getBestAAResults().alias(
1421  MemoryLocation(PN->getIncomingValue(i), PNSize),
1423  PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)), V2Size),
1424  AAQI);
1425  if (Alias)
1426  *Alias = MergeAliasResults(*Alias, ThisAlias);
1427  else
1428  Alias = ThisAlias;
1429  if (*Alias == AliasResult::MayAlias)
1430  break;
1431  }
1432  return *Alias;
1433  }
1434 
1435  SmallVector<Value *, 4> V1Srcs;
1436  // If a phi operand recurses back to the phi, we can still determine NoAlias
1437  // if we don't alias the underlying objects of the other phi operands, as we
1438  // know that the recursive phi needs to be based on them in some way.
1439  bool isRecursive = false;
1440  auto CheckForRecPhi = [&](Value *PV) {
1441  if (!EnableRecPhiAnalysis)
1442  return false;
1443  if (getUnderlyingObject(PV) == PN) {
1444  isRecursive = true;
1445  return true;
1446  }
1447  return false;
1448  };
1449 
1450  if (PV) {
1451  // If we have PhiValues then use it to get the underlying phi values.
1452  const PhiValues::ValueSet &PhiValueSet = PV->getValuesForPhi(PN);
1453  // If we have more phi values than the search depth then return MayAlias
1454  // conservatively to avoid compile time explosion. The worst possible case
1455  // is if both sides are PHI nodes. In which case, this is O(m x n) time
1456  // where 'm' and 'n' are the number of PHI sources.
1457  if (PhiValueSet.size() > MaxLookupSearchDepth)
1458  return AliasResult::MayAlias;
1459  // Add the values to V1Srcs
1460  for (Value *PV1 : PhiValueSet) {
1461  if (CheckForRecPhi(PV1))
1462  continue;
1463  V1Srcs.push_back(PV1);
1464  }
1465  } else {
1466  // If we don't have PhiInfo then just look at the operands of the phi itself
1467  // FIXME: Remove this once we can guarantee that we have PhiInfo always
1468  SmallPtrSet<Value *, 4> UniqueSrc;
1469  Value *OnePhi = nullptr;
1470  for (Value *PV1 : PN->incoming_values()) {
1471  if (isa<PHINode>(PV1)) {
1472  if (OnePhi && OnePhi != PV1) {
1473  // To control potential compile time explosion, we choose to be
1474  // conserviate when we have more than one Phi input. It is important
1475  // that we handle the single phi case as that lets us handle LCSSA
1476  // phi nodes and (combined with the recursive phi handling) simple
1477  // pointer induction variable patterns.
1478  return AliasResult::MayAlias;
1479  }
1480  OnePhi = PV1;
1481  }
1482 
1483  if (CheckForRecPhi(PV1))
1484  continue;
1485 
1486  if (UniqueSrc.insert(PV1).second)
1487  V1Srcs.push_back(PV1);
1488  }
1489 
1490  if (OnePhi && UniqueSrc.size() > 1)
1491  // Out of an abundance of caution, allow only the trivial lcssa and
1492  // recursive phi cases.
1493  return AliasResult::MayAlias;
1494  }
1495 
1496  // If V1Srcs is empty then that means that the phi has no underlying non-phi
1497  // value. This should only be possible in blocks unreachable from the entry
1498  // block, but return MayAlias just in case.
1499  if (V1Srcs.empty())
1500  return AliasResult::MayAlias;
1501 
1502  // If this PHI node is recursive, indicate that the pointer may be moved
1503  // across iterations. We can only prove NoAlias if different underlying
1504  // objects are involved.
1505  if (isRecursive)
1507 
1508  // In the recursive alias queries below, we may compare values from two
1509  // different loop iterations. Keep track of visited phi blocks, which will
1510  // be used when determining value equivalence.
1511  bool BlockInserted = VisitedPhiBBs.insert(PN->getParent()).second;
1512  auto _ = make_scope_exit([&]() {
1513  if (BlockInserted)
1514  VisitedPhiBBs.erase(PN->getParent());
1515  });
1516 
1517  // If we inserted a block into VisitedPhiBBs, alias analysis results that
1518  // have been cached earlier may no longer be valid. Perform recursive queries
1519  // with a new AAQueryInfo.
1520  AAQueryInfo NewAAQI = AAQI.withEmptyCache();
1521  AAQueryInfo *UseAAQI = BlockInserted ? &NewAAQI : &AAQI;
1522 
1523  AliasResult Alias = getBestAAResults().alias(
1524  MemoryLocation(V1Srcs[0], PNSize), MemoryLocation(V2, V2Size), *UseAAQI);
1525 
1526  // Early exit if the check of the first PHI source against V2 is MayAlias.
1527  // Other results are not possible.
1528  if (Alias == AliasResult::MayAlias)
1529  return AliasResult::MayAlias;
1530  // With recursive phis we cannot guarantee that MustAlias/PartialAlias will
1531  // remain valid to all elements and needs to conservatively return MayAlias.
1532  if (isRecursive && Alias != AliasResult::NoAlias)
1533  return AliasResult::MayAlias;
1534 
1535  // If all sources of the PHI node NoAlias or MustAlias V2, then returns
1536  // NoAlias / MustAlias. Otherwise, returns MayAlias.
1537  for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) {
1538  Value *V = V1Srcs[i];
1539 
1540  AliasResult ThisAlias = getBestAAResults().alias(
1541  MemoryLocation(V, PNSize), MemoryLocation(V2, V2Size), *UseAAQI);
1542  Alias = MergeAliasResults(ThisAlias, Alias);
1543  if (Alias == AliasResult::MayAlias)
1544  break;
1545  }
1546 
1547  return Alias;
1548 }
1549 
1550 /// Provides a bunch of ad-hoc rules to disambiguate in common cases, such as
1551 /// array references.
1552 AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size,
1553  const Value *V2, LocationSize V2Size,
1554  AAQueryInfo &AAQI) {
1555  // If either of the memory references is empty, it doesn't matter what the
1556  // pointer values are.
1557  if (V1Size.isZero() || V2Size.isZero())
1558  return AliasResult::NoAlias;
1559 
1560  // Strip off any casts if they exist.
1562  V2 = V2->stripPointerCastsForAliasAnalysis();
1563 
1564  // If V1 or V2 is undef, the result is NoAlias because we can always pick a
1565  // value for undef that aliases nothing in the program.
1566  if (isa<UndefValue>(V1) || isa<UndefValue>(V2))
1567  return AliasResult::NoAlias;
1568 
1569  // Are we checking for alias of the same value?
1570  // Because we look 'through' phi nodes, we could look at "Value" pointers from
1571  // different iterations. We must therefore make sure that this is not the
1572  // case. The function isValueEqualInPotentialCycles ensures that this cannot
1573  // happen by looking at the visited phi nodes and making sure they cannot
1574  // reach the value.
1575  if (isValueEqualInPotentialCycles(V1, V2))
1576  return AliasResult::MustAlias;
1577 
1578  if (!V1->getType()->isPointerTy() || !V2->getType()->isPointerTy())
1579  return AliasResult::NoAlias; // Scalars cannot alias each other
1580 
1581  // Figure out what objects these things are pointing to if we can.
1584 
1585  // Null values in the default address space don't point to any object, so they
1586  // don't alias any other pointer.
1587  if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O1))
1588  if (!NullPointerIsDefined(&F, CPN->getType()->getAddressSpace()))
1589  return AliasResult::NoAlias;
1590  if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O2))
1591  if (!NullPointerIsDefined(&F, CPN->getType()->getAddressSpace()))
1592  return AliasResult::NoAlias;
1593 
1594  if (O1 != O2) {
1595  // If V1/V2 point to two different objects, we know that we have no alias.
1596  if (isIdentifiedObject(O1) && isIdentifiedObject(O2))
1597  return AliasResult::NoAlias;
1598 
1599  // Constant pointers can't alias with non-const isIdentifiedObject objects.
1600  if ((isa<Constant>(O1) && isIdentifiedObject(O2) && !isa<Constant>(O2)) ||
1601  (isa<Constant>(O2) && isIdentifiedObject(O1) && !isa<Constant>(O1)))
1602  return AliasResult::NoAlias;
1603 
1604  // Function arguments can't alias with things that are known to be
1605  // unambigously identified at the function level.
1606  if ((isa<Argument>(O1) && isIdentifiedFunctionLocal(O2)) ||
1607  (isa<Argument>(O2) && isIdentifiedFunctionLocal(O1)))
1608  return AliasResult::NoAlias;
1609 
1610  // If one pointer is the result of a call/invoke or load and the other is a
1611  // non-escaping local object within the same function, then we know the
1612  // object couldn't escape to a point where the call could return it.
1613  //
1614  // Note that if the pointers are in different functions, there are a
1615  // variety of complications. A call with a nocapture argument may still
1616  // temporary store the nocapture argument's value in a temporary memory
1617  // location if that memory location doesn't escape. Or it may pass a
1618  // nocapture value to other functions as long as they don't capture it.
1619  if (isEscapeSource(O1) &&
1620  AAQI.CI->isNotCapturedBeforeOrAt(O2, cast<Instruction>(O1)))
1621  return AliasResult::NoAlias;
1622  if (isEscapeSource(O2) &&
1623  AAQI.CI->isNotCapturedBeforeOrAt(O1, cast<Instruction>(O2)))
1624  return AliasResult::NoAlias;
1625  }
1626 
1627  // If the size of one access is larger than the entire object on the other
1628  // side, then we know such behavior is undefined and can assume no alias.
1629  bool NullIsValidLocation = NullPointerIsDefined(&F);
1630  if ((isObjectSmallerThan(
1631  O2, getMinimalExtentFrom(*V1, V1Size, DL, NullIsValidLocation), DL,
1632  TLI, NullIsValidLocation)) ||
1634  O1, getMinimalExtentFrom(*V2, V2Size, DL, NullIsValidLocation), DL,
1635  TLI, NullIsValidLocation)))
1636  return AliasResult::NoAlias;
1637 
1638  // If one the accesses may be before the accessed pointer, canonicalize this
1639  // by using unknown after-pointer sizes for both accesses. This is
1640  // equivalent, because regardless of which pointer is lower, one of them
1641  // will always came after the other, as long as the underlying objects aren't
1642  // disjoint. We do this so that the rest of BasicAA does not have to deal
1643  // with accesses before the base pointer, and to improve cache utilization by
1644  // merging equivalent states.
1645  if (V1Size.mayBeBeforePointer() || V2Size.mayBeBeforePointer()) {
1646  V1Size = LocationSize::afterPointer();
1647  V2Size = LocationSize::afterPointer();
1648  }
1649 
1650  // FIXME: If this depth limit is hit, then we may cache sub-optimal results
1651  // for recursive queries. For this reason, this limit is chosen to be large
1652  // enough to be very rarely hit, while still being small enough to avoid
1653  // stack overflows.
1654  if (AAQI.Depth >= 512)
1655  return AliasResult::MayAlias;
1656 
1657  // Check the cache before climbing up use-def chains. This also terminates
1658  // otherwise infinitely recursive queries.
1659  AAQueryInfo::LocPair Locs({V1, V1Size}, {V2, V2Size});
1660  const bool Swapped = V1 > V2;
1661  if (Swapped)
1662  std::swap(Locs.first, Locs.second);
1663  const auto &Pair = AAQI.AliasCache.try_emplace(
1665  if (!Pair.second) {
1666  auto &Entry = Pair.first->second;
1667  if (!Entry.isDefinitive()) {
1668  // Remember that we used an assumption.
1669  ++Entry.NumAssumptionUses;
1670  ++AAQI.NumAssumptionUses;
1671  }
1672  // Cache contains sorted {V1,V2} pairs but we should return original order.
1673  auto Result = Entry.Result;
1674  Result.swap(Swapped);
1675  return Result;
1676  }
1677 
1678  int OrigNumAssumptionUses = AAQI.NumAssumptionUses;
1679  unsigned OrigNumAssumptionBasedResults = AAQI.AssumptionBasedResults.size();
1681  aliasCheckRecursive(V1, V1Size, V2, V2Size, AAQI, O1, O2);
1682 
1683  auto It = AAQI.AliasCache.find(Locs);
1684  assert(It != AAQI.AliasCache.end() && "Must be in cache");
1685  auto &Entry = It->second;
1686 
1687  // Check whether a NoAlias assumption has been used, but disproven.
1688  bool AssumptionDisproven =
1689  Entry.NumAssumptionUses > 0 && Result != AliasResult::NoAlias;
1690  if (AssumptionDisproven)
1692 
1693  // This is a definitive result now, when considered as a root query.
1694  AAQI.NumAssumptionUses -= Entry.NumAssumptionUses;
1695  Entry.Result = Result;
1696  // Cache contains sorted {V1,V2} pairs.
1697  Entry.Result.swap(Swapped);
1698  Entry.NumAssumptionUses = -1;
1699 
1700  // If the assumption has been disproven, remove any results that may have
1701  // been based on this assumption. Do this after the Entry updates above to
1702  // avoid iterator invalidation.
1703  if (AssumptionDisproven)
1704  while (AAQI.AssumptionBasedResults.size() > OrigNumAssumptionBasedResults)
1706 
1707  // The result may still be based on assumptions higher up in the chain.
1708  // Remember it, so it can be purged from the cache later.
1709  if (OrigNumAssumptionUses != AAQI.NumAssumptionUses &&
1710  Result != AliasResult::MayAlias)
1711  AAQI.AssumptionBasedResults.push_back(Locs);
1712  return Result;
1713 }
1714 
1715 AliasResult BasicAAResult::aliasCheckRecursive(
1716  const Value *V1, LocationSize V1Size,
1717  const Value *V2, LocationSize V2Size,
1718  AAQueryInfo &AAQI, const Value *O1, const Value *O2) {
1719  if (const GEPOperator *GV1 = dyn_cast<GEPOperator>(V1)) {
1720  AliasResult Result = aliasGEP(GV1, V1Size, V2, V2Size, O1, O2, AAQI);
1721  if (Result != AliasResult::MayAlias)
1722  return Result;
1723  } else if (const GEPOperator *GV2 = dyn_cast<GEPOperator>(V2)) {
1724  AliasResult Result = aliasGEP(GV2, V2Size, V1, V1Size, O2, O1, AAQI);
1725  Result.swap();
1726  if (Result != AliasResult::MayAlias)
1727  return Result;
1728  }
1729 
1730  if (const PHINode *PN = dyn_cast<PHINode>(V1)) {
1731  AliasResult Result = aliasPHI(PN, V1Size, V2, V2Size, AAQI);
1732  if (Result != AliasResult::MayAlias)
1733  return Result;
1734  } else if (const PHINode *PN = dyn_cast<PHINode>(V2)) {
1735  AliasResult Result = aliasPHI(PN, V2Size, V1, V1Size, AAQI);
1736  Result.swap();
1737  if (Result != AliasResult::MayAlias)
1738  return Result;
1739  }
1740 
1741  if (const SelectInst *S1 = dyn_cast<SelectInst>(V1)) {
1742  AliasResult Result = aliasSelect(S1, V1Size, V2, V2Size, AAQI);
1743  if (Result != AliasResult::MayAlias)
1744  return Result;
1745  } else if (const SelectInst *S2 = dyn_cast<SelectInst>(V2)) {
1746  AliasResult Result = aliasSelect(S2, V2Size, V1, V1Size, AAQI);
1747  Result.swap();
1748  if (Result != AliasResult::MayAlias)
1749  return Result;
1750  }
1751 
1752  // If both pointers are pointing into the same object and one of them
1753  // accesses the entire object, then the accesses must overlap in some way.
1754  if (O1 == O2) {
1755  bool NullIsValidLocation = NullPointerIsDefined(&F);
1756  if (V1Size.isPrecise() && V2Size.isPrecise() &&
1757  (isObjectSize(O1, V1Size.getValue(), DL, TLI, NullIsValidLocation) ||
1758  isObjectSize(O2, V2Size.getValue(), DL, TLI, NullIsValidLocation)))
1760  }
1761 
1762  return AliasResult::MayAlias;
1763 }
1764 
1765 /// Check whether two Values can be considered equivalent.
1766 ///
1767 /// In addition to pointer equivalence of \p V1 and \p V2 this checks whether
1768 /// they can not be part of a cycle in the value graph by looking at all
1769 /// visited phi nodes an making sure that the phis cannot reach the value. We
1770 /// have to do this because we are looking through phi nodes (That is we say
1771 /// noalias(V, phi(VA, VB)) if noalias(V, VA) and noalias(V, VB).
1772 bool BasicAAResult::isValueEqualInPotentialCycles(const Value *V,
1773  const Value *V2) {
1774  if (V != V2)
1775  return false;
1776 
1777  const Instruction *Inst = dyn_cast<Instruction>(V);
1778  if (!Inst)
1779  return true;
1780 
1781  if (VisitedPhiBBs.empty())
1782  return true;
1783 
1784  if (VisitedPhiBBs.size() > MaxNumPhiBBsValueReachabilityCheck)
1785  return false;
1786 
1787  // Make sure that the visited phis cannot reach the Value. This ensures that
1788  // the Values cannot come from different iterations of a potential cycle the
1789  // phi nodes could be involved in.
1790  for (auto *P : VisitedPhiBBs)
1791  if (isPotentiallyReachable(&P->front(), Inst, nullptr, DT))
1792  return false;
1793 
1794  return true;
1795 }
1796 
1797 /// Computes the symbolic difference between two de-composed GEPs.
1798 void BasicAAResult::subtractDecomposedGEPs(DecomposedGEP &DestGEP,
1799  const DecomposedGEP &SrcGEP) {
1800  DestGEP.Offset -= SrcGEP.Offset;
1801  for (const VariableGEPIndex &Src : SrcGEP.VarIndices) {
1802  // Find V in Dest. This is N^2, but pointer indices almost never have more
1803  // than a few variable indexes.
1804  bool Found = false;
1805  for (auto I : enumerate(DestGEP.VarIndices)) {
1806  VariableGEPIndex &Dest = I.value();
1807  if (!isValueEqualInPotentialCycles(Dest.Val.V, Src.Val.V) ||
1808  !Dest.Val.hasSameCastsAs(Src.Val))
1809  continue;
1810 
1811  // If we found it, subtract off Scale V's from the entry in Dest. If it
1812  // goes to zero, remove the entry.
1813  if (Dest.Scale != Src.Scale) {
1814  Dest.Scale -= Src.Scale;
1815  Dest.IsNSW = false;
1816  } else {
1817  DestGEP.VarIndices.erase(DestGEP.VarIndices.begin() + I.index());
1818  }
1819  Found = true;
1820  break;
1821  }
1822 
1823  // If we didn't consume this entry, add it to the end of the Dest list.
1824  if (!Found) {
1825  VariableGEPIndex Entry = {Src.Val, -Src.Scale, Src.CxtI, Src.IsNSW};
1826  DestGEP.VarIndices.push_back(Entry);
1827  }
1828  }
1829 }
1830 
1831 bool BasicAAResult::constantOffsetHeuristic(
1832  const DecomposedGEP &GEP, LocationSize MaybeV1Size,
1833  LocationSize MaybeV2Size, AssumptionCache *AC, DominatorTree *DT) {
1834  if (GEP.VarIndices.size() != 2 || !MaybeV1Size.hasValue() ||
1835  !MaybeV2Size.hasValue())
1836  return false;
1837 
1838  const uint64_t V1Size = MaybeV1Size.getValue();
1839  const uint64_t V2Size = MaybeV2Size.getValue();
1840 
1841  const VariableGEPIndex &Var0 = GEP.VarIndices[0], &Var1 = GEP.VarIndices[1];
1842 
1843  if (Var0.Val.TruncBits != 0 || !Var0.Val.hasSameCastsAs(Var1.Val) ||
1844  Var0.Scale != -Var1.Scale ||
1845  Var0.Val.V->getType() != Var1.Val.V->getType())
1846  return false;
1847 
1848  // We'll strip off the Extensions of Var0 and Var1 and do another round
1849  // of GetLinearExpression decomposition. In the example above, if Var0
1850  // is zext(%x + 1) we should get V1 == %x and V1Offset == 1.
1851 
1852  LinearExpression E0 =
1853  GetLinearExpression(CastedValue(Var0.Val.V), DL, 0, AC, DT);
1854  LinearExpression E1 =
1855  GetLinearExpression(CastedValue(Var1.Val.V), DL, 0, AC, DT);
1856  if (E0.Scale != E1.Scale || !E0.Val.hasSameCastsAs(E1.Val) ||
1857  !isValueEqualInPotentialCycles(E0.Val.V, E1.Val.V))
1858  return false;
1859 
1860  // We have a hit - Var0 and Var1 only differ by a constant offset!
1861 
1862  // If we've been sext'ed then zext'd the maximum difference between Var0 and
1863  // Var1 is possible to calculate, but we're just interested in the absolute
1864  // minimum difference between the two. The minimum distance may occur due to
1865  // wrapping; consider "add i3 %i, 5": if %i == 7 then 7 + 5 mod 8 == 4, and so
1866  // the minimum distance between %i and %i + 5 is 3.
1867  APInt MinDiff = E0.Offset - E1.Offset, Wrapped = -MinDiff;
1868  MinDiff = APIntOps::umin(MinDiff, Wrapped);
1869  APInt MinDiffBytes =
1870  MinDiff.zextOrTrunc(Var0.Scale.getBitWidth()) * Var0.Scale.abs();
1871 
1872  // We can't definitely say whether GEP1 is before or after V2 due to wrapping
1873  // arithmetic (i.e. for some values of GEP1 and V2 GEP1 < V2, and for other
1874  // values GEP1 > V2). We'll therefore only declare NoAlias if both V1Size and
1875  // V2Size can fit in the MinDiffBytes gap.
1876  return MinDiffBytes.uge(V1Size + GEP.Offset.abs()) &&
1877  MinDiffBytes.uge(V2Size + GEP.Offset.abs());
1878 }
1879 
1880 //===----------------------------------------------------------------------===//
1881 // BasicAliasAnalysis Pass
1882 //===----------------------------------------------------------------------===//
1883 
1884 AnalysisKey BasicAA::Key;
1885 
1887  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
1888  auto &AC = AM.getResult<AssumptionAnalysis>(F);
1889  auto *DT = &AM.getResult<DominatorTreeAnalysis>(F);
1890  auto *PV = AM.getCachedResult<PhiValuesAnalysis>(F);
1891  return BasicAAResult(F.getParent()->getDataLayout(), F, TLI, AC, DT, PV);
1892 }
1893 
1896 }
1897 
1898 char BasicAAWrapperPass::ID = 0;
1899 
1900 void BasicAAWrapperPass::anchor() {}
1901 
1903  "Basic Alias Analysis (stateless AA impl)", true, true)
1909  "Basic Alias Analysis (stateless AA impl)", true, true)
1910 
1912  return new BasicAAWrapperPass();
1913 }
1914 
1916  auto &ACT = getAnalysis<AssumptionCacheTracker>();
1917  auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>();
1918  auto &DTWP = getAnalysis<DominatorTreeWrapperPass>();
1919  auto *PVWP = getAnalysisIfAvailable<PhiValuesWrapperPass>();
1920 
1921  Result.reset(new BasicAAResult(F.getParent()->getDataLayout(), F,
1922  TLIWP.getTLI(F), ACT.getAssumptionCache(F),
1923  &DTWP.getDomTree(),
1924  PVWP ? &PVWP->getResult() : nullptr));
1925 
1926  return false;
1927 }
1928 
1930  AU.setPreservesAll();
1935 }
1936 
1938  return BasicAAResult(
1939  F.getParent()->getDataLayout(), F,
1940  P.getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F),
1941  P.getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F));
1942 }
i
i
Definition: README.txt:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::ModRefInfo::NoModRef
@ NoModRef
The access neither references nor modifies the value stored in memory.
llvm::Argument
This class represents an incoming formal argument to a Function.
Definition: Argument.h:28
AssumptionCache.h
llvm::Type::isSized
bool isSized(SmallPtrSetImpl< Type * > *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
Definition: Type.h:264
llvm::AliasResult::MayAlias
@ MayAlias
The two locations may or may not alias.
Definition: AliasAnalysis.h:102
llvm::EarliestEscapeInfo::removeInstruction
void removeInstruction(Instruction *I)
Definition: BasicAliasAnalysis.cpp:251
llvm::AliasResult::PartialAlias
@ PartialAlias
The two locations alias, but only due to a partial overlap.
Definition: AliasAnalysis.h:104
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::Operator
This is a utility class that provides an abstraction for the common functionality between Instruction...
Definition: Operator.h:32
llvm::SmallPtrSetImpl::erase
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
Definition: SmallPtrSet.h:379
llvm::MaskedValueIsZero
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 'V & Mask' is known to be zero.
Definition: ValueTracking.cpp:391
llvm::PHINode::incoming_values
op_range incoming_values()
Definition: Instructions.h:2750
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::isModAndRefSet
LLVM_NODISCARD bool isModAndRefSet(const ModRefInfo MRI)
Definition: AliasAnalysis.h:192
llvm::BasicAA::run
BasicAAResult run(Function &F, FunctionAnalysisManager &AM)
Definition: BasicAliasAnalysis.cpp:1886
llvm::generic_gep_type_iterator
Definition: GetElementPtrTypeIterator.h:31
llvm::LocationSize::afterPointer
constexpr static LocationSize afterPointer()
Any location after the base pointer (but still within the underlying object).
Definition: MemoryLocation.h:124
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:189
IntrinsicInst.h
llvm::Type::isPointerTy
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:218
llvm::isNonEscapingLocalObject
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.
Definition: CaptureTracking.cpp:489
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:780
llvm::MemoryLocation::Ptr
const Value * Ptr
The address of the start of the location.
Definition: MemoryLocation.h:218
llvm::Function
Definition: Function.h:60
llvm::AnalysisManager::Invalidator::invalidate
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:685
getMinimalExtentFrom
static uint64_t getMinimalExtentFrom(const Value &V, const LocationSize &LocSize, const DataLayout &DL, bool NullIsValidLoc)
Return the minimal extent from V to the end of the underlying object, assuming the result is used in ...
Definition: BasicAliasAnalysis.cpp:189
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
Pass.h
llvm::IntrinsicInst::getIntrinsicID
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Definition: IntrinsicInst.h:53
llvm::BasicAAResult::DecomposedGEP::print
void print(raw_ostream &OS) const
Definition: BasicAliasAnalysis.cpp:521
llvm::SetVector::size
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:77
GetElementPtrTypeIterator.h
llvm::SmallVector< VariableGEPIndex, 4 >
Statistic.h
CaptureTracking.h
llvm::enumerate
detail::enumerator< R > enumerate(R &&TheRange)
Given an input range, returns a new range whose values are are pair (A,B) such that A is the 0-based ...
Definition: STLExtras.h:2045
llvm::initializeBasicAAWrapperPassPass
void initializeBasicAAWrapperPassPass(PassRegistry &)
llvm::APInt::getMaxValue
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
Definition: APInt.h:186
llvm::GlobalVariable
Definition: GlobalVariable.h:39
llvm::APInt::zextOrTrunc
APInt zextOrTrunc(unsigned width) const
Zero extend or truncate to width.
Definition: APInt.cpp:994
llvm::createModRefInfo
LLVM_NODISCARD ModRefInfo createModRefInfo(const FunctionModRefBehavior FMRB)
Definition: AliasAnalysis.h:377
llvm::BasicAAWrapperPass::runOnFunction
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Definition: BasicAliasAnalysis.cpp:1915
llvm::GlobalAlias
Definition: GlobalAlias.h:28
ValueTracking.h
MaxLookupSearchDepth
static const unsigned MaxLookupSearchDepth
Definition: BasicAliasAnalysis.cpp:85
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
llvm::DenseMapBase::erase
bool erase(const KeyT &Val)
Definition: DenseMap.h:304
llvm::isKnownNonZero
bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the given value is known to be non-zero when defined.
Definition: ValueTracking.cpp:340
llvm::PhiValuesWrapperPass
Wrapper pass for the legacy pass manager.
Definition: PhiValues.h:138
APInt.h
llvm::Depth
@ Depth
Definition: SIMachineScheduler.h:36
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1909
llvm::MemoryLocation::Size
LocationSize Size
The maximum size of the location, in address-units, or UnknownSize if the size is not known.
Definition: MemoryLocation.h:227
llvm::APInt::getBitWidth
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1423
MemoryBuiltins.h
llvm::ObjectSizeOpts::NullIsUnknownSize
bool NullIsUnknownSize
If this is true, null pointers in address space 0 will be treated as though they can't be evaluated.
Definition: MemoryBuiltins.h:155
GetLinearExpression
static LinearExpression GetLinearExpression(const CastedValue &Val, const DataLayout &DL, unsigned Depth, AssumptionCache *AC, DominatorTree *DT)
Analyzes the specified value as a linear expression: "A*V + B", where A and B are constant integers.
Definition: BasicAliasAnalysis.cpp:371
isIntrinsicCall
static bool isIntrinsicCall(const CallBase *Call, Intrinsic::ID IID)
Definition: BasicAliasAnalysis.cpp:763
llvm::BasicAAResult::DecomposedGEP::dump
void dump() const
Definition: BasicAliasAnalysis.cpp:517
llvm::Optional< bool >
llvm::AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:81
llvm::SmallPtrSet< Value *, 4 >
llvm::ObjectSizeOpts::RoundToAlign
bool RoundToAlign
Whether to round the result up to the alignment of allocas, byval arguments, and global variables.
Definition: MemoryBuiltins.h:151
impl
place backedge safepoints impl
Definition: PlaceSafepoints.cpp:613
Operator.h
getBitWidth
static unsigned getBitWidth(Type *Ty, const DataLayout &DL)
Returns the bitwidth of the given scalar or pointer type.
Definition: ValueTracking.cpp:98
llvm::dump
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Definition: SparseBitVector.h:877
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:654
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::gep_type_begin
gep_type_iterator gep_type_begin(const User *GEP)
Definition: GetElementPtrTypeIterator.h:123
llvm::LocationSize::isPrecise
bool isPrecise() const
Definition: MemoryLocation.h:166
BasicAliasAnalysis.h
llvm::FMRB_UnknownModRefBehavior
@ FMRB_UnknownModRefBehavior
This indicates that the function could not be classified into one of the behaviors above.
Definition: AliasAnalysis.h:368
llvm::BasicAAWrapperPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: BasicAliasAnalysis.cpp:1929
llvm::APIntOps::umin
const APInt & umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be unsigned.
Definition: APInt.h:2149
llvm::BasicAAResult::DecomposedGEP::VarIndices
SmallVector< VariableGEPIndex, 4 > VarIndices
Definition: BasicAliasAnalysis.cpp:512
F
#define F(x, y, z)
Definition: MD5.cpp:55
isEscapeSource
static bool isEscapeSource(const Value *V)
Returns true if the pointer is one which would have been considered an escape by isNonEscapingLocalOb...
Definition: BasicAliasAnalysis.cpp:108
llvm::FMRB_OnlyAccessesInaccessibleMem
@ FMRB_OnlyAccessesInaccessibleMem
The only memory references in this function (if it has any) are references of memory that is otherwis...
Definition: AliasAnalysis.h:315
KnownBits.h
AliasAnalysis.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::ConstantRange::Signed
@ Signed
Definition: ConstantRange.h:319
llvm::isIdentifiedFunctionLocal
bool isIdentifiedFunctionLocal(const Value *V)
Return true if V is umabigously identified at the function-level.
Definition: AliasAnalysis.cpp:986
llvm::ConstantPointerNull
A constant pointer value that points to null.
Definition: Constants.h:534
llvm::AAQueryInfo
This class stores info we want to provide to or retain within an alias query.
Definition: AliasAnalysis.h:462
isObjectSmallerThan
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.
Definition: BasicAliasAnalysis.cpp:145
Instruction.h
CommandLine.h
llvm::FMRB_OnlyAccessesInaccessibleOrArgMem
@ FMRB_OnlyAccessesInaccessibleOrArgMem
The function may perform non-volatile loads and stores of objects pointed to by its pointer-typed arg...
Definition: AliasAnalysis.h:347
llvm::APInt::uge
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
Definition: APInt.h:1171
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::LocationSize::mayBeBeforePointer
bool mayBeBeforePointer() const
Whether accesses before the base pointer are possible.
Definition: MemoryLocation.h:174
llvm::APInt::isNonNegative
bool isNonNegative() const
Determine if this APInt Value is non-negative (>= 0)
Definition: APInt.h:317
llvm::APInt::isNegative
bool isNegative() const
Determine sign of this APInt.
Definition: APInt.h:312
llvm::CaptureInfo::~CaptureInfo
virtual ~CaptureInfo()=0
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::ModRefInfo::Ref
@ Ref
The access may reference the value stored in memory.
Constants.h
llvm::BasicAAWrapperPass::ID
static char ID
Definition: BasicAliasAnalysis.h:179
llvm::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2760
llvm::BasicAAResult::DecomposedGEP::Base
const Value * Base
Definition: BasicAliasAnalysis.cpp:508
llvm::AArch64::RP
@ RP
Definition: AArch64ISelLowering.h:480
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::LocationSize
Definition: MemoryLocation.h:66
llvm::LibFunc
LibFunc
Definition: TargetLibraryInfo.h:35
Intrinsics.h
InstrTypes.h
llvm::EarliestEscapeInfo::isNotCapturedBeforeOrAt
bool isNotCapturedBeforeOrAt(const Value *Object, const Instruction *I) override
Definition: BasicAliasAnalysis.cpp:226
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::MemoryLocation::getForSource
static MemoryLocation getForSource(const MemTransferInst *MTI)
Return a location representing the source of a memory transfer.
Definition: MemoryLocation.cpp:93
llvm::LocationSize::getValue
uint64_t getValue() const
Definition: MemoryLocation.h:159
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
llvm::AAQueryInfo::CI
CaptureInfo * CI
Definition: AliasAnalysis.h:476
TargetLibraryInfo.h
llvm::dwarf::Index
Index
Definition: Dwarf.h:472
llvm::isPotentiallyReachable
bool isPotentiallyReachable(const Instruction *From, const Instruction *To, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet=nullptr, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)
Determine whether instruction 'To' is reachable from 'From', without passing through any blocks in Ex...
Definition: CFG.cpp:236
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::TargetLibraryInfo::getLibFunc
bool getLibFunc(StringRef funcName, LibFunc &F) const
Searches for a particular function name.
Definition: TargetLibraryInfo.h:294
llvm::make_scope_exit
LLVM_NODISCARD detail::scope_exit< typename std::decay< Callable >::type > make_scope_exit(Callable &&F)
Definition: ScopeExit.h:59
llvm::Instruction
Definition: Instruction.h:42
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
llvm::AArch64CC::LE
@ LE
Definition: AArch64BaseInfo.h:268
llvm::AAQueryInfo::AssumptionBasedResults
SmallVector< AAQueryInfo::LocPair, 4 > AssumptionBasedResults
Location pairs for which an assumption based result is currently stored.
Definition: AliasAnalysis.h:487
llvm::getArgumentAliasingToReturnedPointer
const Value * getArgumentAliasingToReturnedPointer(const CallBase *Call, bool MustPreserveNullness)
This function returns call pointer argument that is considered the same by aliasing rules.
Definition: ValueTracking.cpp:4288
llvm::getUnderlyingObject
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value,...
Definition: ValueTracking.cpp:4343
SmallPtrSet.h
MaxNumPhiBBsValueReachabilityCheck
const unsigned MaxNumPhiBBsValueReachabilityCheck
Cutoff after which to stop analysing a set of phi nodes potentially involved in a cycle.
Definition: BasicAliasAnalysis.cpp:81
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(BasicAAWrapperPass, "basic-aa", "Basic Alias Analysis (stateless AA impl)", true, true) INITIALIZE_PASS_END(BasicAAWrapperPass
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:667
isObjectSize
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.
Definition: BasicAliasAnalysis.cpp:209
llvm::ConstantRange::add
ConstantRange add(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an addition of a value in this ran...
Definition: ConstantRange.cpp:989
llvm::APInt::countTrailingZeros
unsigned countTrailingZeros() const
Count the number of trailing zero bits.
Definition: APInt.h:1555
llvm::generic_gep_type_iterator::getStructTypeOrNull
StructType * getStructTypeOrNull() const
Definition: GetElementPtrTypeIterator.h:116
llvm::isModSet
LLVM_NODISCARD bool isModSet(const ModRefInfo MRI)
Definition: AliasAnalysis.h:196
llvm::ConstantRange::smul_fast
ConstantRange smul_fast(const ConstantRange &Other) const
Return range of possible values for a signed multiplication of this and Other.
Definition: ConstantRange.cpp:1139
llvm::getObjectSize
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.
Definition: MemoryBuiltins.cpp:558
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2756
llvm::None
const NoneType None
Definition: None.h:24
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
Type.h
llvm::APInt::srem
APInt srem(const APInt &RHS) const
Function for signed remainder operation.
Definition: APInt.cpp:1752
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::PhiValues::getValuesForPhi
const ValueSet & getValuesForPhi(const PHINode *PN)
Get the underlying values of a phi.
Definition: PhiValues.cpp:125
llvm::setRef
LLVM_NODISCARD ModRefInfo setRef(const ModRefInfo MRI)
Definition: AliasAnalysis.h:210
llvm::BasicAAResult::pointsToConstantMemory
bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, bool OrLocal)
Chases pointers until we find a (constant global) or not.
Definition: BasicAliasAnalysis.cpp:705
llvm::OutputFileType::Object
@ Object
llvm::clearMust
LLVM_NODISCARD ModRefInfo clearMust(const ModRefInfo MRI)
Definition: AliasAnalysis.h:228
llvm::APInt::getOneBitSet
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
Definition: APInt.h:222
llvm::AAQueryInfo::LocPair
std::pair< AACacheLoc, AACacheLoc > LocPair
Definition: AliasAnalysis.h:464
llvm::BasicAAResult::alias
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI)
Definition: BasicAliasAnalysis.cpp:890
llvm::cl::opt< bool >
llvm::CaptureInfo::isNotCapturedBeforeOrAt
virtual bool isNotCapturedBeforeOrAt(const Value *Object, const Instruction *I)=0
llvm::FindEarliestCapture
Instruction * FindEarliestCapture(const Value *V, Function &F, bool ReturnCaptures, bool StoreCaptures, const DominatorTree &DT, const SmallPtrSetImpl< const Value * > &EphValues, unsigned MaxUsesToExplore=0)
Definition: CaptureTracking.cpp:294
llvm::BasicAAResult::invalidate
bool invalidate(Function &Fn, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Handle invalidation events in the new pass manager.
Definition: BasicAliasAnalysis.cpp:87
llvm::isNoModRef
LLVM_NODISCARD bool isNoModRef(const ModRefInfo MRI)
Definition: AliasAnalysis.h:185
llvm::ConstantRange::getBitWidth
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
Definition: ConstantRange.h:204
llvm::Value::getPointerDereferenceableBytes
uint64_t getPointerDereferenceableBytes(const DataLayout &DL, bool &CanBeNull, bool &CanBeFreed) const
Returns the number of bytes known to be dereferenceable for the pointer value.
Definition: Value.cpp:840
llvm::AMDGPU::Hwreg::Offset
Offset
Definition: SIDefines.h:409
llvm::FMRB_OnlyAccessesArgumentPointees
@ FMRB_OnlyAccessesArgumentPointees
The only memory references in this function (if it has any) are non-volatile loads and stores from ob...
Definition: AliasAnalysis.h:294
llvm::TargetLibraryInfoWrapperPass
Definition: TargetLibraryInfo.h:468
uint64_t
llvm::LocationSize::hasValue
bool hasValue() const
Definition: MemoryLocation.h:156
llvm::LocationSize::isZero
bool isZero() const
Definition: MemoryLocation.h:171
llvm::GlobalValue::getParent
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:577
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:173
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::BasicAAWrapperPass
Legacy wrapper pass to provide the BasicAAResult object.
Definition: BasicAliasAnalysis.h:173
llvm::AAQueryInfo::NumAssumptionUses
int NumAssumptionUses
How many active NoAlias assumption uses there are.
Definition: AliasAnalysis.h:482
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
MemoryLocation.h
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
llvm::PhiValuesAnalysis
The analysis pass which yields a PhiValues.
Definition: PhiValues.h:115
llvm::isKnownNonEqual
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.
Definition: ValueTracking.cpp:379
adjustToIndexSize
static APInt adjustToIndexSize(const APInt &Offset, unsigned IndexSize)
To ensure a pointer offset fits in an integer of size IndexSize (in bits) when that size is smaller t...
Definition: BasicAliasAnalysis.cpp:471
llvm::ConstantRange::smul_sat
ConstantRange smul_sat(const ConstantRange &Other) const
Perform a signed saturating multiplication of two constant ranges.
Definition: ConstantRange.cpp:1579
llvm::DenseMapBase::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:152
llvm::computeKnownBits
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...
Definition: ValueTracking.cpp:222
llvm::ModRefInfo
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
Definition: AliasAnalysis.h:148
llvm::AAQueryInfo::CacheEntry
Definition: AliasAnalysis.h:465
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
llvm::AliasResult::setOffset
void setOffset(int32_t NewOffset)
Definition: AliasAnalysis.h:122
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::generic_gep_type_iterator::getIndexedType
Type * getIndexedType() const
Definition: GetElementPtrTypeIterator.h:70
llvm::Value::stripPointerCastsForAliasAnalysis
const Value * stripPointerCastsForAliasAnalysis() const
Strip off pointer casts, all-zero GEPs, single-argument phi nodes and invariant group info.
Definition: Value.cpp:698
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1737
llvm::TargetLibraryInfo::has
bool has(LibFunc F) const
Tests whether a library function is available.
Definition: TargetLibraryInfo.h:328
llvm::BasicAAResult::DecomposedGEP::Offset
APInt Offset
Definition: BasicAliasAnalysis.cpp:510
llvm::FMRB_DoesNotAccessMemory
@ FMRB_DoesNotAccessMemory
This function does not perform any non-local loads or stores to memory.
Definition: AliasAnalysis.h:268
llvm::AAResultBase::getArgModRefInfo
ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx)
Definition: AliasAnalysis.h:1232
llvm::AMDGPU::IsaInfo::TargetIDSetting::Off
@ Off
llvm::GEPOperator
Definition: Operator.h:375
_
#define _
Definition: HexagonMCCodeEmitter.cpp:47
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
CFG.h
llvm::AliasResult::swap
void swap(bool DoSwap=true)
Helper for processing AliasResult for swapped memory location pairs.
Definition: AliasAnalysis.h:130
llvm::BasicAAResult::DecomposedGEP::InBounds
Optional< bool > InBounds
Definition: BasicAliasAnalysis.cpp:515
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:202
llvm::BinaryOperator
Definition: InstrTypes.h:188
Mul
BinaryOperator * Mul
Definition: X86PartialReduction.cpp:70
llvm::BasicAAResult::getModRefInfo
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, AAQueryInfo &AAQI)
Checks to see if the specified callsite can clobber the specified memory object.
Definition: BasicAliasAnalysis.cpp:904
DataLayout.h
llvm::StructType
Class to represent struct types.
Definition: DerivedTypes.h:213
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::BasicAAResult::getArgModRefInfo
ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx)
Get the location associated with a pointer argument of a callsite.
Definition: BasicAliasAnalysis.cpp:852
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:868
llvm::FMRB_OnlyReadsMemory
@ FMRB_OnlyReadsMemory
This function does not perform any non-local stores or volatile loads, but may read from any memory l...
Definition: AliasAnalysis.h:357
llvm::AliasResult::NoAlias
@ NoAlias
The two locations do not alias at all.
Definition: AliasAnalysis.h:99
Compiler.h
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1811
llvm::ModRefInfo::Mod
@ Mod
The access may modify the value stored in memory.
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::computeConstantRange
ConstantRange computeConstantRange(const Value *V, bool ForSigned, bool UseInstrInfo=true, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Determine the possible constant range of an integer or vector of integer value.
Definition: ValueTracking.cpp:7081
ConstantRange.h
llvm::AliasResult::MustAlias
@ MustAlias
The two locations precisely alias each other.
Definition: AliasAnalysis.h:106
llvm::TargetLibraryInfoWrapperPass::getTLI
TargetLibraryInfo & getTLI(const Function &F)
Definition: TargetLibraryInfo.h:480
llvm::ObjectSizeOpts
Various options to control the behavior of getObjectSize.
Definition: MemoryBuiltins.h:135
llvm::FunctionModRefBehavior
FunctionModRefBehavior
Summary of how a function affects memory in the program.
Definition: AliasAnalysis.h:262
llvm::BasicAAResult
This is the AA result object for the basic, local, and stateless alias analysis.
Definition: BasicAliasAnalysis.h:44
LLVM_FALLTHROUGH
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
Definition: Compiler.h:280
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:305
llvm::SimpleCaptureInfo::isNotCapturedBeforeOrAt
bool isNotCapturedBeforeOrAt(const Value *Object, const Instruction *I) override
Definition: BasicAliasAnalysis.cpp:221
llvm::SmallPtrSetImplBase::size
size_type size() const
Definition: SmallPtrSet.h:93
llvm::AAResultBase::getModRefInfo
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, AAQueryInfo &AAQI)
Definition: AliasAnalysis.h:1244
Argument.h
llvm::APInt::zext
APInt zext(unsigned width) const
Zero extend to a new width.
Definition: APInt.cpp:973
llvm::GEPOperator::getPointerAddressSpace
unsigned getPointerAddressSpace() const
Method to return the address space of the pointer operand.
Definition: Operator.h:435
PhiValues.h
llvm::BasicAAWrapperPass::BasicAAWrapperPass
BasicAAWrapperPass()
Definition: BasicAliasAnalysis.cpp:1894
llvm::createBasicAAWrapperPass
FunctionPass * createBasicAAWrapperPass()
Definition: BasicAliasAnalysis.cpp:1911
Attributes.h
Constant.h
llvm::NVPTX::PTXLdStInstCode::V2
@ V2
Definition: NVPTX.h:123
llvm::KnownBits
Definition: KnownBits.h:23
llvm::isIdentifiedObject
bool isIdentifiedObject(const Value *V)
Return true if this pointer refers to a distinct and identifiable object.
Definition: AliasAnalysis.cpp:974
EnableRecPhiAnalysis
static cl::opt< bool > EnableRecPhiAnalysis("basic-aa-recphi", cl::Hidden, cl::init(true))
Enable analysis of recursive PHI nodes.
llvm::AssumptionCacheTracker::getAssumptionCache
AssumptionCache & getAssumptionCache(Function &F)
Get the cached assumptions for a function.
Definition: AssumptionCache.cpp:285
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
llvm::LocationSize::beforeOrAfterPointer
constexpr static LocationSize beforeOrAfterPointer()
Any location before or after the base pointer (but still within the underlying object).
Definition: MemoryLocation.h:130
llvm::DenseMapBase::end
iterator end()
Definition: DenseMap.h:84
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:341
llvm::GEPOperator::isInBounds
bool isInBounds() const
Test whether this is an inbounds GEP, as defined by LangRef.html.
Definition: Operator.h:392
GlobalVariable.h
llvm::TypeSize
Definition: TypeSize.h:421
llvm::AnalysisManager::getCachedResult
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:799
Casting.h
Function.h
llvm::AAQueryInfo::AliasCache
AliasCacheT AliasCache
Definition: AliasAnalysis.h:474
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:222
isWriteOnlyParam
static bool isWriteOnlyParam(const CallBase *Call, unsigned ArgIdx, const TargetLibraryInfo &TLI)
Returns true if this is a writeonly (i.e Mod only) parameter.
Definition: BasicAliasAnalysis.cpp:827
llvm::AAResultBase::pointsToConstantMemory
bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, bool OrLocal)
Definition: AliasAnalysis.h:1227
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:185
GlobalAlias.h
llvm::AMDGPU::Hwreg::Width
Width
Definition: SIDefines.h:432
llvm::ConstantRange
This class represents a range of values.
Definition: ConstantRange.h:47
llvm::AAQueryInfo::withEmptyCache
AAQueryInfo withEmptyCache()
Create a new AAQueryInfo based on this one, but with the cache cleared.
Definition: AliasAnalysis.h:494
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:46
llvm::BasicAAResult::DecomposedGEP
Definition: BasicAliasAnalysis.cpp:506
llvm::APInt::abs
APInt abs() const
Get the absolute value.
Definition: APInt.h:1698
AA
llvm::createLegacyPMBasicAAResult
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...
Definition: BasicAliasAnalysis.cpp:1937
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
llvm::FMRB_OnlyWritesMemory
@ FMRB_OnlyWritesMemory
Definition: AliasAnalysis.h:364
llvm::AAResultBase< BasicAAResult >::getBestAAResults
AAResultsProxy getBestAAResults()
Get a proxy for the best AA result set to query at this time.
Definition: AliasAnalysis.h:1219
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
aa
basic aa
Definition: BasicAliasAnalysis.cpp:1908
Instructions.h
llvm::MemoryLocation::UnknownSize
@ UnknownSize
Definition: MemoryLocation.h:215
llvm::GEPOperator::getSourceElementType
Type * getSourceElementType() const
Definition: Operator.cpp:47
llvm::ConstantRange::intersectWith
ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
Definition: ConstantRange.cpp:523
SmallVector.h
User.h
llvm::ConstantRange::fromKnownBits
static ConstantRange fromKnownBits(const KnownBits &Known, bool IsSigned)
Initialize a range based on a known bits constraint.
Definition: ConstantRange.cpp:58
llvm::User::op_begin
op_iterator op_begin()
Definition: User.h:234
Dominators.h
llvm::APIntOps::GreatestCommonDivisor
APInt GreatestCommonDivisor(APInt A, APInt B)
Compute GCD of two unsigned APInt values.
Definition: APInt.cpp:759
llvm::SmallPtrSetImplBase::empty
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:92
N
#define N
llvm::DenseMapBase::try_emplace
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&... Args)
Definition: DenseMap.h:224
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2780
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::setMust
LLVM_NODISCARD ModRefInfo setMust(const ModRefInfo MRI)
Definition: AliasAnalysis.h:214
llvm::PHINode
Definition: Instructions.h:2664
ScopeExit.h
llvm::MipsISD::Ins
@ Ins
Definition: MipsISelLowering.h:160
llvm::MemoryLocation::getBeforeOrAfter
static MemoryLocation getBeforeOrAfter(const Value *Ptr, const AAMDNodes &AATags=AAMDNodes())
Return a location that may access any location before or after Ptr, while remaining within the underl...
Definition: MemoryLocation.h:278
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1174
llvm::AnalysisUsage::addRequiredTransitive
AnalysisUsage & addRequiredTransitive()
Definition: PassAnalysisSupport.h:81
DerivedTypes.h
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::AnalysisUsage::addUsedIfAvailable
AnalysisUsage & addUsedIfAvailable()
Add the specified Pass class to the set of analyses used by this pass.
Definition: PassAnalysisSupport.h:117
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1474
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:172
llvm::MemoryLocation::getForDest
static MemoryLocation getForDest(const MemIntrinsic *MI)
Return a location representing the destination of a memory set or transfer.
Definition: MemoryLocation.cpp:106
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::ConstantRange::isEmptySet
bool isEmptySet() const
Return true if this set contains no members.
Definition: ConstantRange.cpp:370
llvm::NullPointerIsDefined
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:2039
Value.h
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::TargetLibraryAnalysis
Analysis pass providing the TargetLibraryInfo.
Definition: TargetLibraryInfo.h:443
llvm::BasicAAResult::getModRefBehavior
FunctionModRefBehavior getModRefBehavior(const CallBase *Call)
Returns the behavior when calling the given call site.
Definition: BasicAliasAnalysis.cpp:769
llvm::ModRefInfo::ModRef
@ ModRef
The access may reference and may modify the value stored in memory.
llvm::MemoryLocation
Representation for a specific memory location.
Definition: MemoryLocation.h:210
llvm::isMallocOrCallocLikeFn
bool isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI)
Tests if a value is a call or invoke to a library function that allocates memory similar to malloc or...
Definition: MemoryBuiltins.cpp:301
MergeAliasResults
static AliasResult MergeAliasResults(AliasResult A, AliasResult B)
Definition: BasicAliasAnalysis.cpp:1359
llvm::AAQueryInfo::Depth
unsigned Depth
Query depth used to distinguish recursive queries.
Definition: AliasAnalysis.h:479
llvm::setMod
LLVM_NODISCARD ModRefInfo setMod(const ModRefInfo MRI)
Definition: AliasAnalysis.h:206
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1225
notDifferentParent
static bool notDifferentParent(const Value *O1, const Value *O2)
Definition: BasicAliasAnalysis.cpp:881
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::Type::getPrimitiveSizeInBits
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
Definition: Type.cpp:164
isBaseOfObject
static bool isBaseOfObject(const Value *V)
Return true if we know V to the base address of the corresponding memory object.
Definition: BasicAliasAnalysis.cpp:1107
llvm::SmallPtrSetImpl::insert
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:365
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37
llvm::User::op_end
op_iterator op_end()
Definition: User.h:236