LCOV - code coverage report
Current view: top level - lib/Analysis - BasicAliasAnalysis.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 624 631 98.9 %
Date: 2017-09-14 15:23:50 Functions: 33 34 97.1 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13