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