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

Generated by: LCOV version 1.13