LLVM  mainline
BasicAliasAnalysis.cpp
Go to the documentation of this file.
00001 //===- BasicAliasAnalysis.cpp - Stateless Alias Analysis Impl -------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines the primary stateless implementation of the
00011 // Alias Analysis interface that implements identities (two different
00012 // globals cannot alias, etc), but does no stateful analysis.
00013 //
00014 //===----------------------------------------------------------------------===//
00015 
00016 #include "llvm/Analysis/BasicAliasAnalysis.h"
00017 #include "llvm/ADT/SmallVector.h"
00018 #include "llvm/ADT/Statistic.h"
00019 #include "llvm/Analysis/AliasAnalysis.h"
00020 #include "llvm/Analysis/CFG.h"
00021 #include "llvm/Analysis/CaptureTracking.h"
00022 #include "llvm/Analysis/InstructionSimplify.h"
00023 #include "llvm/Analysis/LoopInfo.h"
00024 #include "llvm/Analysis/MemoryBuiltins.h"
00025 #include "llvm/Analysis/ValueTracking.h"
00026 #include "llvm/Analysis/AssumptionCache.h"
00027 #include "llvm/IR/Constants.h"
00028 #include "llvm/IR/DataLayout.h"
00029 #include "llvm/IR/DerivedTypes.h"
00030 #include "llvm/IR/Dominators.h"
00031 #include "llvm/IR/GlobalAlias.h"
00032 #include "llvm/IR/GlobalVariable.h"
00033 #include "llvm/IR/Instructions.h"
00034 #include "llvm/IR/IntrinsicInst.h"
00035 #include "llvm/IR/LLVMContext.h"
00036 #include "llvm/IR/Operator.h"
00037 #include "llvm/Pass.h"
00038 #include "llvm/Support/ErrorHandling.h"
00039 #include <algorithm>
00040 using namespace llvm;
00041 
00042 /// Enable analysis of recursive PHI nodes.
00043 static cl::opt<bool> EnableRecPhiAnalysis("basicaa-recphi", cl::Hidden,
00044                                           cl::init(false));
00045 
00046 /// SearchLimitReached / SearchTimes shows how often the limit of
00047 /// to decompose GEPs is reached. It will affect the precision
00048 /// of basic alias analysis.
00049 #define DEBUG_TYPE "basicaa"
00050 STATISTIC(SearchLimitReached, "Number of times the limit to "
00051                               "decompose GEPs is reached");
00052 STATISTIC(SearchTimes, "Number of times a GEP is decomposed");
00053 
00054 /// Cutoff after which to stop analysing a set of phi nodes potentially involved
00055 /// in a cycle. Because we are analysing 'through' phi nodes, we need to be
00056 /// careful with value equivalence. We use reachability to make sure a value
00057 /// cannot be involved in a cycle.
00058 const unsigned MaxNumPhiBBsValueReachabilityCheck = 20;
00059 
00060 // The max limit of the search depth in DecomposeGEPExpression() and
00061 // GetUnderlyingObject(), both functions need to use the same search
00062 // depth otherwise the algorithm in aliasGEP will assert.
00063 static const unsigned MaxLookupSearchDepth = 6;
00064 
00065 //===----------------------------------------------------------------------===//
00066 // Useful predicates
00067 //===----------------------------------------------------------------------===//
00068 
00069 /// Returns true if the pointer is to a function-local object that never
00070 /// escapes from the function.
00071 static bool isNonEscapingLocalObject(const Value *V) {
00072   // If this is a local allocation, check to see if it escapes.
00073   if (isa<AllocaInst>(V) || isNoAliasCall(V))
00074     // Set StoreCaptures to True so that we can assume in our callers that the
00075     // pointer is not the result of a load instruction. Currently
00076     // PointerMayBeCaptured doesn't have any special analysis for the
00077     // StoreCaptures=false case; if it did, our callers could be refined to be
00078     // more precise.
00079     return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true);
00080 
00081   // If this is an argument that corresponds to a byval or noalias argument,
00082   // then it has not escaped before entering the function.  Check if it escapes
00083   // inside the function.
00084   if (const Argument *A = dyn_cast<Argument>(V))
00085     if (A->hasByValAttr() || A->hasNoAliasAttr())
00086       // Note even if the argument is marked nocapture, we still need to check
00087       // for copies made inside the function. The nocapture attribute only
00088       // specifies that there are no copies made that outlive the function.
00089       return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true);
00090 
00091   return false;
00092 }
00093 
00094 /// Returns true if the pointer is one which would have been considered an
00095 /// escape by isNonEscapingLocalObject.
00096 static bool isEscapeSource(const Value *V) {
00097   if (isa<CallInst>(V) || isa<InvokeInst>(V) || isa<Argument>(V))
00098     return true;
00099 
00100   // The load case works because isNonEscapingLocalObject considers all
00101   // stores to be escapes (it passes true for the StoreCaptures argument
00102   // to PointerMayBeCaptured).
00103   if (isa<LoadInst>(V))
00104     return true;
00105 
00106   return false;
00107 }
00108 
00109 /// Returns the size of the object specified by V or UnknownSize if unknown.
00110 static uint64_t getObjectSize(const Value *V, const DataLayout &DL,
00111                               const TargetLibraryInfo &TLI,
00112                               bool RoundToAlign = false) {
00113   uint64_t Size;
00114   if (getObjectSize(V, Size, DL, &TLI, RoundToAlign))
00115     return Size;
00116   return MemoryLocation::UnknownSize;
00117 }
00118 
00119 /// Returns true if we can prove that the object specified by V is smaller than
00120 /// Size.
00121 static bool isObjectSmallerThan(const Value *V, uint64_t Size,
00122                                 const DataLayout &DL,
00123                                 const TargetLibraryInfo &TLI) {
00124   // Note that the meanings of the "object" are slightly different in the
00125   // following contexts:
00126   //    c1: llvm::getObjectSize()
00127   //    c2: llvm.objectsize() intrinsic
00128   //    c3: isObjectSmallerThan()
00129   // c1 and c2 share the same meaning; however, the meaning of "object" in c3
00130   // refers to the "entire object".
00131   //
00132   //  Consider this example:
00133   //     char *p = (char*)malloc(100)
00134   //     char *q = p+80;
00135   //
00136   //  In the context of c1 and c2, the "object" pointed by q refers to the
00137   // stretch of memory of q[0:19]. So, getObjectSize(q) should return 20.
00138   //
00139   //  However, in the context of c3, the "object" refers to the chunk of memory
00140   // being allocated. So, the "object" has 100 bytes, and q points to the middle
00141   // the "object". In case q is passed to isObjectSmallerThan() as the 1st
00142   // parameter, before the llvm::getObjectSize() is called to get the size of
00143   // entire object, we should:
00144   //    - either rewind the pointer q to the base-address of the object in
00145   //      question (in this case rewind to p), or
00146   //    - just give up. It is up to caller to make sure the pointer is pointing
00147   //      to the base address the object.
00148   //
00149   // We go for 2nd option for simplicity.
00150   if (!isIdentifiedObject(V))
00151     return false;
00152 
00153   // This function needs to use the aligned object size because we allow
00154   // reads a bit past the end given sufficient alignment.
00155   uint64_t ObjectSize = getObjectSize(V, DL, TLI, /*RoundToAlign*/ true);
00156 
00157   return ObjectSize != MemoryLocation::UnknownSize && ObjectSize < Size;
00158 }
00159 
00160 /// Returns true if we can prove that the object specified by V has size Size.
00161 static bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &DL,
00162                          const TargetLibraryInfo &TLI) {
00163   uint64_t ObjectSize = getObjectSize(V, DL, TLI);
00164   return ObjectSize != MemoryLocation::UnknownSize && ObjectSize == Size;
00165 }
00166 
00167 //===----------------------------------------------------------------------===//
00168 // GetElementPtr Instruction Decomposition and Analysis
00169 //===----------------------------------------------------------------------===//
00170 
00171 /// Analyzes the specified value as a linear expression: "A*V + B", where A and
00172 /// B are constant integers.
00173 ///
00174 /// Returns the scale and offset values as APInts and return V as a Value*, and
00175 /// return whether we looked through any sign or zero extends.  The incoming
00176 /// Value is known to have IntegerType, and it may already be sign or zero
00177 /// extended.
00178 ///
00179 /// Note that this looks through extends, so the high bits may not be
00180 /// represented in the result.
00181 /*static*/ const Value *BasicAAResult::GetLinearExpression(
00182     const Value *V, APInt &Scale, APInt &Offset, unsigned &ZExtBits,
00183     unsigned &SExtBits, const DataLayout &DL, unsigned Depth,
00184     AssumptionCache *AC, DominatorTree *DT, bool &NSW, bool &NUW) {
00185   assert(V->getType()->isIntegerTy() && "Not an integer value");
00186 
00187   // Limit our recursion depth.
00188   if (Depth == 6) {
00189     Scale = 1;
00190     Offset = 0;
00191     return V;
00192   }
00193 
00194   if (const ConstantInt *Const = dyn_cast<ConstantInt>(V)) {
00195     // If it's a constant, just convert it to an offset and remove the variable.
00196     // If we've been called recursively, the Offset bit width will be greater
00197     // than the constant's (the Offset's always as wide as the outermost call),
00198     // so we'll zext here and process any extension in the isa<SExtInst> &
00199     // isa<ZExtInst> cases below.
00200     Offset += Const->getValue().zextOrSelf(Offset.getBitWidth());
00201     assert(Scale == 0 && "Constant values don't have a scale");
00202     return V;
00203   }
00204 
00205   if (const BinaryOperator *BOp = dyn_cast<BinaryOperator>(V)) {
00206     if (ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) {
00207 
00208       // If we've been called recursively, then Offset and Scale will be wider
00209       // than the BOp operands. We'll always zext it here as we'll process sign
00210       // extensions below (see the isa<SExtInst> / isa<ZExtInst> cases).
00211       APInt RHS = RHSC->getValue().zextOrSelf(Offset.getBitWidth());
00212 
00213       switch (BOp->getOpcode()) {
00214       default:
00215         // We don't understand this instruction, so we can't decompose it any
00216         // further.
00217         Scale = 1;
00218         Offset = 0;
00219         return V;
00220       case Instruction::Or:
00221         // X|C == X+C if all the bits in C are unset in X.  Otherwise we can't
00222         // analyze it.
00223         if (!MaskedValueIsZero(BOp->getOperand(0), RHSC->getValue(), DL, 0, AC,
00224                                BOp, DT)) {
00225           Scale = 1;
00226           Offset = 0;
00227           return V;
00228         }
00229       // FALL THROUGH.
00230       case Instruction::Add:
00231         V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits,
00232                                 SExtBits, DL, Depth + 1, AC, DT, NSW, NUW);
00233         Offset += RHS;
00234         break;
00235       case Instruction::Sub:
00236         V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits,
00237                                 SExtBits, DL, Depth + 1, AC, DT, NSW, NUW);
00238         Offset -= RHS;
00239         break;
00240       case Instruction::Mul:
00241         V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits,
00242                                 SExtBits, DL, Depth + 1, AC, DT, NSW, NUW);
00243         Offset *= RHS;
00244         Scale *= RHS;
00245         break;
00246       case Instruction::Shl:
00247         V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits,
00248                                 SExtBits, DL, Depth + 1, AC, DT, NSW, NUW);
00249         Offset <<= RHS.getLimitedValue();
00250         Scale <<= RHS.getLimitedValue();
00251         // the semantics of nsw and nuw for left shifts don't match those of
00252         // multiplications, so we won't propagate them.
00253         NSW = NUW = false;
00254         return V;
00255       }
00256 
00257       if (isa<OverflowingBinaryOperator>(BOp)) {
00258         NUW &= BOp->hasNoUnsignedWrap();
00259         NSW &= BOp->hasNoSignedWrap();
00260       }
00261       return V;
00262     }
00263   }
00264 
00265   // Since GEP indices are sign extended anyway, we don't care about the high
00266   // bits of a sign or zero extended value - just scales and offsets.  The
00267   // extensions have to be consistent though.
00268   if (isa<SExtInst>(V) || isa<ZExtInst>(V)) {
00269     Value *CastOp = cast<CastInst>(V)->getOperand(0);
00270     unsigned NewWidth = V->getType()->getPrimitiveSizeInBits();
00271     unsigned SmallWidth = CastOp->getType()->getPrimitiveSizeInBits();
00272     unsigned OldZExtBits = ZExtBits, OldSExtBits = SExtBits;
00273     const Value *Result =
00274         GetLinearExpression(CastOp, Scale, Offset, ZExtBits, SExtBits, DL,
00275                             Depth + 1, AC, DT, NSW, NUW);
00276 
00277     // zext(zext(%x)) == zext(%x), and similiarly for sext; we'll handle this
00278     // by just incrementing the number of bits we've extended by.
00279     unsigned ExtendedBy = NewWidth - SmallWidth;
00280 
00281     if (isa<SExtInst>(V) && ZExtBits == 0) {
00282       // sext(sext(%x, a), b) == sext(%x, a + b)
00283 
00284       if (NSW) {
00285         // We haven't sign-wrapped, so it's valid to decompose sext(%x + c)
00286         // into sext(%x) + sext(c). We'll sext the Offset ourselves:
00287         unsigned OldWidth = Offset.getBitWidth();
00288         Offset = Offset.trunc(SmallWidth).sext(NewWidth).zextOrSelf(OldWidth);
00289       } else {
00290         // We may have signed-wrapped, so don't decompose sext(%x + c) into
00291         // sext(%x) + sext(c)
00292         Scale = 1;
00293         Offset = 0;
00294         Result = CastOp;
00295         ZExtBits = OldZExtBits;
00296         SExtBits = OldSExtBits;
00297       }
00298       SExtBits += ExtendedBy;
00299     } else {
00300       // sext(zext(%x, a), b) = zext(zext(%x, a), b) = zext(%x, a + b)
00301 
00302       if (!NUW) {
00303         // We may have unsigned-wrapped, so don't decompose zext(%x + c) into
00304         // zext(%x) + zext(c)
00305         Scale = 1;
00306         Offset = 0;
00307         Result = CastOp;
00308         ZExtBits = OldZExtBits;
00309         SExtBits = OldSExtBits;
00310       }
00311       ZExtBits += ExtendedBy;
00312     }
00313 
00314     return Result;
00315   }
00316 
00317   Scale = 1;
00318   Offset = 0;
00319   return V;
00320 }
00321 
00322 /// If V is a symbolic pointer expression, decompose it into a base pointer
00323 /// with a constant offset and a number of scaled symbolic offsets.
00324 ///
00325 /// The scaled symbolic offsets (represented by pairs of a Value* and a scale
00326 /// in the VarIndices vector) are Value*'s that are known to be scaled by the
00327 /// specified amount, but which may have other unrepresented high bits. As
00328 /// such, the gep cannot necessarily be reconstructed from its decomposed form.
00329 ///
00330 /// When DataLayout is around, this function is capable of analyzing everything
00331 /// that GetUnderlyingObject can look through. To be able to do that
00332 /// GetUnderlyingObject and DecomposeGEPExpression must use the same search
00333 /// depth (MaxLookupSearchDepth). When DataLayout not is around, it just looks
00334 /// through pointer casts.
00335 /*static*/ const Value *BasicAAResult::DecomposeGEPExpression(
00336     const Value *V, int64_t &BaseOffs,
00337     SmallVectorImpl<VariableGEPIndex> &VarIndices, bool &MaxLookupReached,
00338     const DataLayout &DL, AssumptionCache *AC, DominatorTree *DT) {
00339   // Limit recursion depth to limit compile time in crazy cases.
00340   unsigned MaxLookup = MaxLookupSearchDepth;
00341   MaxLookupReached = false;
00342   SearchTimes++;
00343 
00344   BaseOffs = 0;
00345   do {
00346     // See if this is a bitcast or GEP.
00347     const Operator *Op = dyn_cast<Operator>(V);
00348     if (!Op) {
00349       // The only non-operator case we can handle are GlobalAliases.
00350       if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
00351         if (!GA->mayBeOverridden()) {
00352           V = GA->getAliasee();
00353           continue;
00354         }
00355       }
00356       return V;
00357     }
00358 
00359     if (Op->getOpcode() == Instruction::BitCast ||
00360         Op->getOpcode() == Instruction::AddrSpaceCast) {
00361       V = Op->getOperand(0);
00362       continue;
00363     }
00364 
00365     const GEPOperator *GEPOp = dyn_cast<GEPOperator>(Op);
00366     if (!GEPOp) {
00367       // If it's not a GEP, hand it off to SimplifyInstruction to see if it
00368       // can come up with something. This matches what GetUnderlyingObject does.
00369       if (const Instruction *I = dyn_cast<Instruction>(V))
00370         // TODO: Get a DominatorTree and AssumptionCache and use them here
00371         // (these are both now available in this function, but this should be
00372         // updated when GetUnderlyingObject is updated). TLI should be
00373         // provided also.
00374         if (const Value *Simplified =
00375                 SimplifyInstruction(const_cast<Instruction *>(I), DL)) {
00376           V = Simplified;
00377           continue;
00378         }
00379 
00380       return V;
00381     }
00382 
00383     // Don't attempt to analyze GEPs over unsized objects.
00384     if (!GEPOp->getSourceElementType()->isSized())
00385       return V;
00386 
00387     unsigned AS = GEPOp->getPointerAddressSpace();
00388     // Walk the indices of the GEP, accumulating them into BaseOff/VarIndices.
00389     gep_type_iterator GTI = gep_type_begin(GEPOp);
00390     for (User::const_op_iterator I = GEPOp->op_begin() + 1, E = GEPOp->op_end();
00391          I != E; ++I) {
00392       const Value *Index = *I;
00393       // Compute the (potentially symbolic) offset in bytes for this index.
00394       if (StructType *STy = dyn_cast<StructType>(*GTI++)) {
00395         // For a struct, add the member offset.
00396         unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue();
00397         if (FieldNo == 0)
00398           continue;
00399 
00400         BaseOffs += DL.getStructLayout(STy)->getElementOffset(FieldNo);
00401         continue;
00402       }
00403 
00404       // For an array/pointer, add the element offset, explicitly scaled.
00405       if (const ConstantInt *CIdx = dyn_cast<ConstantInt>(Index)) {
00406         if (CIdx->isZero())
00407           continue;
00408         BaseOffs += DL.getTypeAllocSize(*GTI) * CIdx->getSExtValue();
00409         continue;
00410       }
00411 
00412       uint64_t Scale = DL.getTypeAllocSize(*GTI);
00413       unsigned ZExtBits = 0, SExtBits = 0;
00414 
00415       // If the integer type is smaller than the pointer size, it is implicitly
00416       // sign extended to pointer size.
00417       unsigned Width = Index->getType()->getIntegerBitWidth();
00418       unsigned PointerSize = DL.getPointerSizeInBits(AS);
00419       if (PointerSize > Width)
00420         SExtBits += PointerSize - Width;
00421 
00422       // Use GetLinearExpression to decompose the index into a C1*V+C2 form.
00423       APInt IndexScale(Width, 0), IndexOffset(Width, 0);
00424       bool NSW = true, NUW = true;
00425       Index = GetLinearExpression(Index, IndexScale, IndexOffset, ZExtBits,
00426                                   SExtBits, DL, 0, AC, DT, NSW, NUW);
00427 
00428       // The GEP index scale ("Scale") scales C1*V+C2, yielding (C1*V+C2)*Scale.
00429       // This gives us an aggregate computation of (C1*Scale)*V + C2*Scale.
00430       BaseOffs += IndexOffset.getSExtValue() * Scale;
00431       Scale *= IndexScale.getSExtValue();
00432 
00433       // If we already had an occurrence of this index variable, merge this
00434       // scale into it.  For example, we want to handle:
00435       //   A[x][x] -> x*16 + x*4 -> x*20
00436       // This also ensures that 'x' only appears in the index list once.
00437       for (unsigned i = 0, e = VarIndices.size(); i != e; ++i) {
00438         if (VarIndices[i].V == Index && VarIndices[i].ZExtBits == ZExtBits &&
00439             VarIndices[i].SExtBits == SExtBits) {
00440           Scale += VarIndices[i].Scale;
00441           VarIndices.erase(VarIndices.begin() + i);
00442           break;
00443         }
00444       }
00445 
00446       // Make sure that we have a scale that makes sense for this target's
00447       // pointer size.
00448       if (unsigned ShiftBits = 64 - PointerSize) {
00449         Scale <<= ShiftBits;
00450         Scale = (int64_t)Scale >> ShiftBits;
00451       }
00452 
00453       if (Scale) {
00454         VariableGEPIndex Entry = {Index, ZExtBits, SExtBits,
00455                                   static_cast<int64_t>(Scale)};
00456         VarIndices.push_back(Entry);
00457       }
00458     }
00459 
00460     // Analyze the base pointer next.
00461     V = GEPOp->getOperand(0);
00462   } while (--MaxLookup);
00463 
00464   // If the chain of expressions is too deep, just return early.
00465   MaxLookupReached = true;
00466   SearchLimitReached++;
00467   return V;
00468 }
00469 
00470 /// Returns whether the given pointer value points to memory that is local to
00471 /// the function, with global constants being considered local to all
00472 /// functions.
00473 bool BasicAAResult::pointsToConstantMemory(const MemoryLocation &Loc,
00474                                            bool OrLocal) {
00475   assert(Visited.empty() && "Visited must be cleared after use!");
00476 
00477   unsigned MaxLookup = 8;
00478   SmallVector<const Value *, 16> Worklist;
00479   Worklist.push_back(Loc.Ptr);
00480   do {
00481     const Value *V = GetUnderlyingObject(Worklist.pop_back_val(), DL);
00482     if (!Visited.insert(V).second) {
00483       Visited.clear();
00484       return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
00485     }
00486 
00487     // An alloca instruction defines local memory.
00488     if (OrLocal && isa<AllocaInst>(V))
00489       continue;
00490 
00491     // A global constant counts as local memory for our purposes.
00492     if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) {
00493       // Note: this doesn't require GV to be "ODR" because it isn't legal for a
00494       // global to be marked constant in some modules and non-constant in
00495       // others.  GV may even be a declaration, not a definition.
00496       if (!GV->isConstant()) {
00497         Visited.clear();
00498         return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
00499       }
00500       continue;
00501     }
00502 
00503     // If both select values point to local memory, then so does the select.
00504     if (const SelectInst *SI = dyn_cast<SelectInst>(V)) {
00505       Worklist.push_back(SI->getTrueValue());
00506       Worklist.push_back(SI->getFalseValue());
00507       continue;
00508     }
00509 
00510     // If all values incoming to a phi node point to local memory, then so does
00511     // the phi.
00512     if (const PHINode *PN = dyn_cast<PHINode>(V)) {
00513       // Don't bother inspecting phi nodes with many operands.
00514       if (PN->getNumIncomingValues() > MaxLookup) {
00515         Visited.clear();
00516         return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
00517       }
00518       for (Value *IncValue : PN->incoming_values())
00519         Worklist.push_back(IncValue);
00520       continue;
00521     }
00522 
00523     // Otherwise be conservative.
00524     Visited.clear();
00525     return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
00526 
00527   } while (!Worklist.empty() && --MaxLookup);
00528 
00529   Visited.clear();
00530   return Worklist.empty();
00531 }
00532 
00533 // FIXME: This code is duplicated with MemoryLocation and should be hoisted to
00534 // some common utility location.
00535 static bool isMemsetPattern16(const Function *MS,
00536                               const TargetLibraryInfo &TLI) {
00537   if (TLI.has(LibFunc::memset_pattern16) &&
00538       MS->getName() == "memset_pattern16") {
00539     FunctionType *MemsetType = MS->getFunctionType();
00540     if (!MemsetType->isVarArg() && MemsetType->getNumParams() == 3 &&
00541         isa<PointerType>(MemsetType->getParamType(0)) &&
00542         isa<PointerType>(MemsetType->getParamType(1)) &&
00543         isa<IntegerType>(MemsetType->getParamType(2)))
00544       return true;
00545   }
00546   return false;
00547 }
00548 
00549 /// Returns the behavior when calling the given call site.
00550 FunctionModRefBehavior BasicAAResult::getModRefBehavior(ImmutableCallSite CS) {
00551   if (CS.doesNotAccessMemory())
00552     // Can't do better than this.
00553     return FMRB_DoesNotAccessMemory;
00554 
00555   FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior;
00556 
00557   // If the callsite knows it only reads memory, don't return worse
00558   // than that.
00559   if (CS.onlyReadsMemory())
00560     Min = FMRB_OnlyReadsMemory;
00561 
00562   if (CS.onlyAccessesArgMemory())
00563     Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesArgumentPointees);
00564 
00565   // The AAResultBase base class has some smarts, lets use them.
00566   return FunctionModRefBehavior(AAResultBase::getModRefBehavior(CS) & Min);
00567 }
00568 
00569 /// Returns the behavior when calling the given function. For use when the call
00570 /// site is not known.
00571 FunctionModRefBehavior BasicAAResult::getModRefBehavior(const Function *F) {
00572   // If the function declares it doesn't access memory, we can't do better.
00573   if (F->doesNotAccessMemory())
00574     return FMRB_DoesNotAccessMemory;
00575 
00576   FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior;
00577 
00578   // If the function declares it only reads memory, go with that.
00579   if (F->onlyReadsMemory())
00580     Min = FMRB_OnlyReadsMemory;
00581 
00582   if (F->onlyAccessesArgMemory())
00583     Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesArgumentPointees);
00584 
00585   // Otherwise be conservative.
00586   return FunctionModRefBehavior(AAResultBase::getModRefBehavior(F) & Min);
00587 }
00588 
00589 /// Returns true if this is a writeonly (i.e Mod only) parameter.  Currently,
00590 /// we don't have a writeonly attribute, so this only knows about builtin
00591 /// intrinsics and target library functions.  We could consider adding a
00592 /// writeonly attribute in the future and moving all of these facts to either
00593 /// Intrinsics.td or InferFunctionAttr.cpp
00594 static bool isWriteOnlyParam(ImmutableCallSite CS, unsigned ArgIdx,
00595                              const TargetLibraryInfo &TLI) {
00596   if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction()))
00597     switch (II->getIntrinsicID()) {
00598     default:
00599       break;
00600     case Intrinsic::memset:
00601     case Intrinsic::memcpy:
00602     case Intrinsic::memmove:
00603       // We don't currently have a writeonly attribute.  All other properties
00604       // of these intrinsics are nicely described via attributes in
00605       // Intrinsics.td and handled generically.
00606       if (ArgIdx == 0)
00607         return true;
00608     }
00609 
00610   // We can bound the aliasing properties of memset_pattern16 just as we can
00611   // for memcpy/memset.  This is particularly important because the
00612   // LoopIdiomRecognizer likes to turn loops into calls to memset_pattern16
00613   // whenever possible.  Note that all but the missing writeonly attribute are
00614   // handled via InferFunctionAttr.
00615   if (CS.getCalledFunction() && isMemsetPattern16(CS.getCalledFunction(), TLI))
00616     if (ArgIdx == 0)
00617       return true;
00618 
00619   // TODO: memset_pattern4, memset_pattern8
00620   // TODO: _chk variants
00621   // TODO: strcmp, strcpy
00622 
00623   return false;
00624 }
00625 
00626 ModRefInfo BasicAAResult::getArgModRefInfo(ImmutableCallSite CS,
00627                                            unsigned ArgIdx) {
00628 
00629   // Emulate the missing writeonly attribute by checking for known builtin
00630   // intrinsics and target library functions.
00631   if (isWriteOnlyParam(CS, ArgIdx, TLI))
00632     return MRI_Mod;
00633 
00634   if (CS.paramHasAttr(ArgIdx + 1, Attribute::ReadOnly))
00635     return MRI_Ref;
00636 
00637   if (CS.paramHasAttr(ArgIdx + 1, Attribute::ReadNone))
00638     return MRI_NoModRef;
00639 
00640   return AAResultBase::getArgModRefInfo(CS, ArgIdx);
00641 }
00642 
00643 static bool isAssumeIntrinsic(ImmutableCallSite CS) {
00644   const IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction());
00645   return II && II->getIntrinsicID() == Intrinsic::assume;
00646 }
00647 
00648 #ifndef NDEBUG
00649 static const Function *getParent(const Value *V) {
00650   if (const Instruction *inst = dyn_cast<Instruction>(V))
00651     return inst->getParent()->getParent();
00652 
00653   if (const Argument *arg = dyn_cast<Argument>(V))
00654     return arg->getParent();
00655 
00656   return nullptr;
00657 }
00658 
00659 static bool notDifferentParent(const Value *O1, const Value *O2) {
00660 
00661   const Function *F1 = getParent(O1);
00662   const Function *F2 = getParent(O2);
00663 
00664   return !F1 || !F2 || F1 == F2;
00665 }
00666 #endif
00667 
00668 AliasResult BasicAAResult::alias(const MemoryLocation &LocA,
00669                                  const MemoryLocation &LocB) {
00670   assert(notDifferentParent(LocA.Ptr, LocB.Ptr) &&
00671          "BasicAliasAnalysis doesn't support interprocedural queries.");
00672 
00673   // If we have a directly cached entry for these locations, we have recursed
00674   // through this once, so just return the cached results. Notably, when this
00675   // happens, we don't clear the cache.
00676   auto CacheIt = AliasCache.find(LocPair(LocA, LocB));
00677   if (CacheIt != AliasCache.end())
00678     return CacheIt->second;
00679 
00680   AliasResult Alias = aliasCheck(LocA.Ptr, LocA.Size, LocA.AATags, LocB.Ptr,
00681                                  LocB.Size, LocB.AATags);
00682   // AliasCache rarely has more than 1 or 2 elements, always use
00683   // shrink_and_clear so it quickly returns to the inline capacity of the
00684   // SmallDenseMap if it ever grows larger.
00685   // FIXME: This should really be shrink_to_inline_capacity_and_clear().
00686   AliasCache.shrink_and_clear();
00687   VisitedPhiBBs.clear();
00688   return Alias;
00689 }
00690 
00691 /// Checks to see if the specified callsite can clobber the specified memory
00692 /// object.
00693 ///
00694 /// Since we only look at local properties of this function, we really can't
00695 /// say much about this query.  We do, however, use simple "address taken"
00696 /// analysis on local objects.
00697 ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS,
00698                                         const MemoryLocation &Loc) {
00699   assert(notDifferentParent(CS.getInstruction(), Loc.Ptr) &&
00700          "AliasAnalysis query involving multiple functions!");
00701 
00702   const Value *Object = GetUnderlyingObject(Loc.Ptr, DL);
00703 
00704   // If this is a tail call and Loc.Ptr points to a stack location, we know that
00705   // the tail call cannot access or modify the local stack.
00706   // We cannot exclude byval arguments here; these belong to the caller of
00707   // the current function not to the current function, and a tail callee
00708   // may reference them.
00709   if (isa<AllocaInst>(Object))
00710     if (const CallInst *CI = dyn_cast<CallInst>(CS.getInstruction()))
00711       if (CI->isTailCall())
00712         return MRI_NoModRef;
00713 
00714   // If the pointer is to a locally allocated object that does not escape,
00715   // then the call can not mod/ref the pointer unless the call takes the pointer
00716   // as an argument, and itself doesn't capture it.
00717   if (!isa<Constant>(Object) && CS.getInstruction() != Object &&
00718       isNonEscapingLocalObject(Object)) {
00719     bool PassedAsArg = false;
00720     unsigned OperandNo = 0;
00721     for (auto CI = CS.data_operands_begin(), CE = CS.data_operands_end();
00722          CI != CE; ++CI, ++OperandNo) {
00723       // Only look at the no-capture or byval pointer arguments.  If this
00724       // pointer were passed to arguments that were neither of these, then it
00725       // couldn't be no-capture.
00726       if (!(*CI)->getType()->isPointerTy() ||
00727           (!CS.doesNotCapture(OperandNo) && !CS.isByValArgument(OperandNo)))
00728         continue;
00729 
00730       // If this is a no-capture pointer argument, see if we can tell that it
00731       // is impossible to alias the pointer we're checking.  If not, we have to
00732       // assume that the call could touch the pointer, even though it doesn't
00733       // escape.
00734       AliasResult AR =
00735           getBestAAResults().alias(MemoryLocation(*CI), MemoryLocation(Object));
00736       if (AR) {
00737         PassedAsArg = true;
00738         break;
00739       }
00740     }
00741 
00742     if (!PassedAsArg)
00743       return MRI_NoModRef;
00744   }
00745 
00746   // While the assume intrinsic is marked as arbitrarily writing so that
00747   // proper control dependencies will be maintained, it never aliases any
00748   // particular memory location.
00749   if (isAssumeIntrinsic(CS))
00750     return MRI_NoModRef;
00751 
00752   // The AAResultBase base class has some smarts, lets use them.
00753   return AAResultBase::getModRefInfo(CS, Loc);
00754 }
00755 
00756 ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS1,
00757                                         ImmutableCallSite CS2) {
00758   // While the assume intrinsic is marked as arbitrarily writing so that
00759   // proper control dependencies will be maintained, it never aliases any
00760   // particular memory location.
00761   if (isAssumeIntrinsic(CS1) || isAssumeIntrinsic(CS2))
00762     return MRI_NoModRef;
00763 
00764   // The AAResultBase base class has some smarts, lets use them.
00765   return AAResultBase::getModRefInfo(CS1, CS2);
00766 }
00767 
00768 /// Provide ad-hoc rules to disambiguate accesses through two GEP operators,
00769 /// both having the exact same pointer operand.
00770 static AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1,
00771                                             uint64_t V1Size,
00772                                             const GEPOperator *GEP2,
00773                                             uint64_t V2Size,
00774                                             const DataLayout &DL) {
00775 
00776   assert(GEP1->getPointerOperand() == GEP2->getPointerOperand() &&
00777          "Expected GEPs with the same pointer operand");
00778 
00779   // Try to determine whether GEP1 and GEP2 index through arrays, into structs,
00780   // such that the struct field accesses provably cannot alias.
00781   // We also need at least two indices (the pointer, and the struct field).
00782   if (GEP1->getNumIndices() != GEP2->getNumIndices() ||
00783       GEP1->getNumIndices() < 2)
00784     return MayAlias;
00785 
00786   // If we don't know the size of the accesses through both GEPs, we can't
00787   // determine whether the struct fields accessed can't alias.
00788   if (V1Size == MemoryLocation::UnknownSize ||
00789       V2Size == MemoryLocation::UnknownSize)
00790     return MayAlias;
00791 
00792   ConstantInt *C1 =
00793       dyn_cast<ConstantInt>(GEP1->getOperand(GEP1->getNumOperands() - 1));
00794   ConstantInt *C2 =
00795       dyn_cast<ConstantInt>(GEP2->getOperand(GEP2->getNumOperands() - 1));
00796 
00797   // If the last (struct) indices are constants and are equal, the other indices
00798   // might be also be dynamically equal, so the GEPs can alias.
00799   if (C1 && C2 && C1 == C2)
00800     return MayAlias;
00801 
00802   // Find the last-indexed type of the GEP, i.e., the type you'd get if
00803   // you stripped the last index.
00804   // On the way, look at each indexed type.  If there's something other
00805   // than an array, different indices can lead to different final types.
00806   SmallVector<Value *, 8> IntermediateIndices;
00807 
00808   // Insert the first index; we don't need to check the type indexed
00809   // through it as it only drops the pointer indirection.
00810   assert(GEP1->getNumIndices() > 1 && "Not enough GEP indices to examine");
00811   IntermediateIndices.push_back(GEP1->getOperand(1));
00812 
00813   // Insert all the remaining indices but the last one.
00814   // Also, check that they all index through arrays.
00815   for (unsigned i = 1, e = GEP1->getNumIndices() - 1; i != e; ++i) {
00816     if (!isa<ArrayType>(GetElementPtrInst::getIndexedType(
00817             GEP1->getSourceElementType(), IntermediateIndices)))
00818       return MayAlias;
00819     IntermediateIndices.push_back(GEP1->getOperand(i + 1));
00820   }
00821 
00822   auto *Ty = GetElementPtrInst::getIndexedType(
00823     GEP1->getSourceElementType(), IntermediateIndices);
00824   StructType *LastIndexedStruct = dyn_cast<StructType>(Ty);
00825 
00826   if (isa<SequentialType>(Ty)) {
00827     // We know that:
00828     // - both GEPs begin indexing from the exact same pointer;
00829     // - the last indices in both GEPs are constants, indexing into a sequential
00830     //   type (array or pointer);
00831     // - both GEPs only index through arrays prior to that.
00832     //
00833     // Because array indices greater than the number of elements are valid in
00834     // GEPs, unless we know the intermediate indices are identical between
00835     // GEP1 and GEP2 we cannot guarantee that the last indexed arrays don't
00836     // partially overlap. We also need to check that the loaded size matches
00837     // the element size, otherwise we could still have overlap.
00838     const uint64_t ElementSize =
00839         DL.getTypeStoreSize(cast<SequentialType>(Ty)->getElementType());
00840     if (V1Size != ElementSize || V2Size != ElementSize)
00841       return MayAlias;
00842 
00843     for (unsigned i = 0, e = GEP1->getNumIndices() - 1; i != e; ++i)
00844       if (GEP1->getOperand(i + 1) != GEP2->getOperand(i + 1))
00845         return MayAlias;
00846 
00847     // Now we know that the array/pointer that GEP1 indexes into and that
00848     // that GEP2 indexes into must either precisely overlap or be disjoint.
00849     // Because they cannot partially overlap and because fields in an array
00850     // cannot overlap, if we can prove the final indices are different between
00851     // GEP1 and GEP2, we can conclude GEP1 and GEP2 don't alias.
00852     
00853     // If the last indices are constants, we've already checked they don't
00854     // equal each other so we can exit early.
00855     if (C1 && C2)
00856       return NoAlias;
00857     if (isKnownNonEqual(GEP1->getOperand(GEP1->getNumOperands() - 1),
00858                         GEP2->getOperand(GEP2->getNumOperands() - 1),
00859                         DL))
00860       return NoAlias;
00861     return MayAlias;
00862   } else if (!LastIndexedStruct || !C1 || !C2) {
00863     return MayAlias;
00864   }
00865 
00866   // We know that:
00867   // - both GEPs begin indexing from the exact same pointer;
00868   // - the last indices in both GEPs are constants, indexing into a struct;
00869   // - said indices are different, hence, the pointed-to fields are different;
00870   // - both GEPs only index through arrays prior to that.
00871   //
00872   // This lets us determine that the struct that GEP1 indexes into and the
00873   // struct that GEP2 indexes into must either precisely overlap or be
00874   // completely disjoint.  Because they cannot partially overlap, indexing into
00875   // different non-overlapping fields of the struct will never alias.
00876 
00877   // Therefore, the only remaining thing needed to show that both GEPs can't
00878   // alias is that the fields are not overlapping.
00879   const StructLayout *SL = DL.getStructLayout(LastIndexedStruct);
00880   const uint64_t StructSize = SL->getSizeInBytes();
00881   const uint64_t V1Off = SL->getElementOffset(C1->getZExtValue());
00882   const uint64_t V2Off = SL->getElementOffset(C2->getZExtValue());
00883 
00884   auto EltsDontOverlap = [StructSize](uint64_t V1Off, uint64_t V1Size,
00885                                       uint64_t V2Off, uint64_t V2Size) {
00886     return V1Off < V2Off && V1Off + V1Size <= V2Off &&
00887            ((V2Off + V2Size <= StructSize) ||
00888             (V2Off + V2Size - StructSize <= V1Off));
00889   };
00890 
00891   if (EltsDontOverlap(V1Off, V1Size, V2Off, V2Size) ||
00892       EltsDontOverlap(V2Off, V2Size, V1Off, V1Size))
00893     return NoAlias;
00894 
00895   return MayAlias;
00896 }
00897 
00898 /// Provides a bunch of ad-hoc rules to disambiguate a GEP instruction against
00899 /// another pointer.
00900 ///
00901 /// We know that V1 is a GEP, but we don't know anything about V2.
00902 /// UnderlyingV1 is GetUnderlyingObject(GEP1, DL), UnderlyingV2 is the same for
00903 /// V2.
00904 AliasResult BasicAAResult::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size,
00905                                     const AAMDNodes &V1AAInfo, const Value *V2,
00906                                     uint64_t V2Size, const AAMDNodes &V2AAInfo,
00907                                     const Value *UnderlyingV1,
00908                                     const Value *UnderlyingV2) {
00909   int64_t GEP1BaseOffset;
00910   bool GEP1MaxLookupReached;
00911   SmallVector<VariableGEPIndex, 4> GEP1VariableIndices;
00912 
00913   // If we have two gep instructions with must-alias or not-alias'ing base
00914   // pointers, figure out if the indexes to the GEP tell us anything about the
00915   // derived pointer.
00916   if (const GEPOperator *GEP2 = dyn_cast<GEPOperator>(V2)) {
00917     // Do the base pointers alias?
00918     AliasResult BaseAlias =
00919         aliasCheck(UnderlyingV1, MemoryLocation::UnknownSize, AAMDNodes(),
00920                    UnderlyingV2, MemoryLocation::UnknownSize, AAMDNodes());
00921 
00922     // Check for geps of non-aliasing underlying pointers where the offsets are
00923     // identical.
00924     if ((BaseAlias == MayAlias) && V1Size == V2Size) {
00925       // Do the base pointers alias assuming type and size.
00926       AliasResult PreciseBaseAlias = aliasCheck(UnderlyingV1, V1Size, V1AAInfo,
00927                                                 UnderlyingV2, V2Size, V2AAInfo);
00928       if (PreciseBaseAlias == NoAlias) {
00929         // See if the computed offset from the common pointer tells us about the
00930         // relation of the resulting pointer.
00931         int64_t GEP2BaseOffset;
00932         bool GEP2MaxLookupReached;
00933         SmallVector<VariableGEPIndex, 4> GEP2VariableIndices;
00934         const Value *GEP2BasePtr =
00935             DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices,
00936                                    GEP2MaxLookupReached, DL, &AC, DT);
00937         const Value *GEP1BasePtr =
00938             DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices,
00939                                    GEP1MaxLookupReached, DL, &AC, DT);
00940         // DecomposeGEPExpression and GetUnderlyingObject should return the
00941         // same result except when DecomposeGEPExpression has no DataLayout.
00942         // FIXME: They always have a DataLayout, so this should become an
00943         // assert.
00944         if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) {
00945           return MayAlias;
00946         }
00947         // If the max search depth is reached the result is undefined
00948         if (GEP2MaxLookupReached || GEP1MaxLookupReached)
00949           return MayAlias;
00950 
00951         // Same offsets.
00952         if (GEP1BaseOffset == GEP2BaseOffset &&
00953             GEP1VariableIndices == GEP2VariableIndices)
00954           return NoAlias;
00955         GEP1VariableIndices.clear();
00956       }
00957     }
00958 
00959     // If we get a No or May, then return it immediately, no amount of analysis
00960     // will improve this situation.
00961     if (BaseAlias != MustAlias)
00962       return BaseAlias;
00963 
00964     // Otherwise, we have a MustAlias.  Since the base pointers alias each other
00965     // exactly, see if the computed offset from the common pointer tells us
00966     // about the relation of the resulting pointer.
00967     const Value *GEP1BasePtr =
00968         DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices,
00969                                GEP1MaxLookupReached, DL, &AC, DT);
00970 
00971     int64_t GEP2BaseOffset;
00972     bool GEP2MaxLookupReached;
00973     SmallVector<VariableGEPIndex, 4> GEP2VariableIndices;
00974     const Value *GEP2BasePtr =
00975         DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices,
00976                                GEP2MaxLookupReached, DL, &AC, DT);
00977 
00978     // DecomposeGEPExpression and GetUnderlyingObject should return the
00979     // same result except when DecomposeGEPExpression has no DataLayout.
00980     // FIXME: They always have a DataLayout, so this should become an assert.
00981     if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) {
00982       return MayAlias;
00983     }
00984 
00985     // If we know the two GEPs are based off of the exact same pointer (and not
00986     // just the same underlying object), see if that tells us anything about
00987     // the resulting pointers.
00988     if (GEP1->getPointerOperand() == GEP2->getPointerOperand()) {
00989       AliasResult R = aliasSameBasePointerGEPs(GEP1, V1Size, GEP2, V2Size, DL);
00990       // If we couldn't find anything interesting, don't abandon just yet.
00991       if (R != MayAlias)
00992         return R;
00993     }
00994 
00995     // If the max search depth is reached, the result is undefined
00996     if (GEP2MaxLookupReached || GEP1MaxLookupReached)
00997       return MayAlias;
00998 
00999     // Subtract the GEP2 pointer from the GEP1 pointer to find out their
01000     // symbolic difference.
01001     GEP1BaseOffset -= GEP2BaseOffset;
01002     GetIndexDifference(GEP1VariableIndices, GEP2VariableIndices);
01003 
01004   } else {
01005     // Check to see if these two pointers are related by the getelementptr
01006     // instruction.  If one pointer is a GEP with a non-zero index of the other
01007     // pointer, we know they cannot alias.
01008 
01009     // If both accesses are unknown size, we can't do anything useful here.
01010     if (V1Size == MemoryLocation::UnknownSize &&
01011         V2Size == MemoryLocation::UnknownSize)
01012       return MayAlias;
01013 
01014     AliasResult R = aliasCheck(UnderlyingV1, MemoryLocation::UnknownSize,
01015                                AAMDNodes(), V2, V2Size, V2AAInfo);
01016     if (R != MustAlias)
01017       // If V2 may alias GEP base pointer, conservatively returns MayAlias.
01018       // If V2 is known not to alias GEP base pointer, then the two values
01019       // cannot alias per GEP semantics: "A pointer value formed from a
01020       // getelementptr instruction is associated with the addresses associated
01021       // with the first operand of the getelementptr".
01022       return R;
01023 
01024     const Value *GEP1BasePtr =
01025         DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices,
01026                                GEP1MaxLookupReached, DL, &AC, DT);
01027 
01028     // DecomposeGEPExpression and GetUnderlyingObject should return the
01029     // same result except when DecomposeGEPExpression has no DataLayout.
01030     // FIXME: They always have a DataLayout, so this should become an assert.
01031     if (GEP1BasePtr != UnderlyingV1) {
01032       return MayAlias;
01033     }
01034     // If the max search depth is reached the result is undefined
01035     if (GEP1MaxLookupReached)
01036       return MayAlias;
01037   }
01038 
01039   // In the two GEP Case, if there is no difference in the offsets of the
01040   // computed pointers, the resultant pointers are a must alias.  This
01041   // happens when we have two lexically identical GEP's (for example).
01042   //
01043   // In the other case, if we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2
01044   // must aliases the GEP, the end result is a must alias also.
01045   if (GEP1BaseOffset == 0 && GEP1VariableIndices.empty())
01046     return MustAlias;
01047 
01048   // If there is a constant difference between the pointers, but the difference
01049   // is less than the size of the associated memory object, then we know
01050   // that the objects are partially overlapping.  If the difference is
01051   // greater, we know they do not overlap.
01052   if (GEP1BaseOffset != 0 && GEP1VariableIndices.empty()) {
01053     if (GEP1BaseOffset >= 0) {
01054       if (V2Size != MemoryLocation::UnknownSize) {
01055         if ((uint64_t)GEP1BaseOffset < V2Size)
01056           return PartialAlias;
01057         return NoAlias;
01058       }
01059     } else {
01060       // We have the situation where:
01061       // +                +
01062       // | BaseOffset     |
01063       // ---------------->|
01064       // |-->V1Size       |-------> V2Size
01065       // GEP1             V2
01066       // We need to know that V2Size is not unknown, otherwise we might have
01067       // stripped a gep with negative index ('gep <ptr>, -1, ...).
01068       if (V1Size != MemoryLocation::UnknownSize &&
01069           V2Size != MemoryLocation::UnknownSize) {
01070         if (-(uint64_t)GEP1BaseOffset < V1Size)
01071           return PartialAlias;
01072         return NoAlias;
01073       }
01074     }
01075   }
01076 
01077   if (!GEP1VariableIndices.empty()) {
01078     uint64_t Modulo = 0;
01079     bool AllPositive = true;
01080     for (unsigned i = 0, e = GEP1VariableIndices.size(); i != e; ++i) {
01081 
01082       // Try to distinguish something like &A[i][1] against &A[42][0].
01083       // Grab the least significant bit set in any of the scales. We
01084       // don't need std::abs here (even if the scale's negative) as we'll
01085       // be ^'ing Modulo with itself later.
01086       Modulo |= (uint64_t)GEP1VariableIndices[i].Scale;
01087 
01088       if (AllPositive) {
01089         // If the Value could change between cycles, then any reasoning about
01090         // the Value this cycle may not hold in the next cycle. We'll just
01091         // give up if we can't determine conditions that hold for every cycle:
01092         const Value *V = GEP1VariableIndices[i].V;
01093 
01094         bool SignKnownZero, SignKnownOne;
01095         ComputeSignBit(const_cast<Value *>(V), SignKnownZero, SignKnownOne, DL,
01096                        0, &AC, nullptr, DT);
01097 
01098         // Zero-extension widens the variable, and so forces the sign
01099         // bit to zero.
01100         bool IsZExt = GEP1VariableIndices[i].ZExtBits > 0 || isa<ZExtInst>(V);
01101         SignKnownZero |= IsZExt;
01102         SignKnownOne &= !IsZExt;
01103 
01104         // If the variable begins with a zero then we know it's
01105         // positive, regardless of whether the value is signed or
01106         // unsigned.
01107         int64_t Scale = GEP1VariableIndices[i].Scale;
01108         AllPositive =
01109             (SignKnownZero && Scale >= 0) || (SignKnownOne && Scale < 0);
01110       }
01111     }
01112 
01113     Modulo = Modulo ^ (Modulo & (Modulo - 1));
01114 
01115     // We can compute the difference between the two addresses
01116     // mod Modulo. Check whether that difference guarantees that the
01117     // two locations do not alias.
01118     uint64_t ModOffset = (uint64_t)GEP1BaseOffset & (Modulo - 1);
01119     if (V1Size != MemoryLocation::UnknownSize &&
01120         V2Size != MemoryLocation::UnknownSize && ModOffset >= V2Size &&
01121         V1Size <= Modulo - ModOffset)
01122       return NoAlias;
01123 
01124     // If we know all the variables are positive, then GEP1 >= GEP1BasePtr.
01125     // If GEP1BasePtr > V2 (GEP1BaseOffset > 0) then we know the pointers
01126     // don't alias if V2Size can fit in the gap between V2 and GEP1BasePtr.
01127     if (AllPositive && GEP1BaseOffset > 0 && V2Size <= (uint64_t)GEP1BaseOffset)
01128       return NoAlias;
01129 
01130     if (constantOffsetHeuristic(GEP1VariableIndices, V1Size, V2Size,
01131                                 GEP1BaseOffset, &AC, DT))
01132       return NoAlias;
01133   }
01134 
01135   // Statically, we can see that the base objects are the same, but the
01136   // pointers have dynamic offsets which we can't resolve. And none of our
01137   // little tricks above worked.
01138   //
01139   // TODO: Returning PartialAlias instead of MayAlias is a mild hack; the
01140   // practical effect of this is protecting TBAA in the case of dynamic
01141   // indices into arrays of unions or malloc'd memory.
01142   return PartialAlias;
01143 }
01144 
01145 static AliasResult MergeAliasResults(AliasResult A, AliasResult B) {
01146   // If the results agree, take it.
01147   if (A == B)
01148     return A;
01149   // A mix of PartialAlias and MustAlias is PartialAlias.
01150   if ((A == PartialAlias && B == MustAlias) ||
01151       (B == PartialAlias && A == MustAlias))
01152     return PartialAlias;
01153   // Otherwise, we don't know anything.
01154   return MayAlias;
01155 }
01156 
01157 /// Provides a bunch of ad-hoc rules to disambiguate a Select instruction
01158 /// against another.
01159 AliasResult BasicAAResult::aliasSelect(const SelectInst *SI, uint64_t SISize,
01160                                        const AAMDNodes &SIAAInfo,
01161                                        const Value *V2, uint64_t V2Size,
01162                                        const AAMDNodes &V2AAInfo) {
01163   // If the values are Selects with the same condition, we can do a more precise
01164   // check: just check for aliases between the values on corresponding arms.
01165   if (const SelectInst *SI2 = dyn_cast<SelectInst>(V2))
01166     if (SI->getCondition() == SI2->getCondition()) {
01167       AliasResult Alias = aliasCheck(SI->getTrueValue(), SISize, SIAAInfo,
01168                                      SI2->getTrueValue(), V2Size, V2AAInfo);
01169       if (Alias == MayAlias)
01170         return MayAlias;
01171       AliasResult ThisAlias =
01172           aliasCheck(SI->getFalseValue(), SISize, SIAAInfo,
01173                      SI2->getFalseValue(), V2Size, V2AAInfo);
01174       return MergeAliasResults(ThisAlias, Alias);
01175     }
01176 
01177   // If both arms of the Select node NoAlias or MustAlias V2, then returns
01178   // NoAlias / MustAlias. Otherwise, returns MayAlias.
01179   AliasResult Alias =
01180       aliasCheck(V2, V2Size, V2AAInfo, SI->getTrueValue(), SISize, SIAAInfo);
01181   if (Alias == MayAlias)
01182     return MayAlias;
01183 
01184   AliasResult ThisAlias =
01185       aliasCheck(V2, V2Size, V2AAInfo, SI->getFalseValue(), SISize, SIAAInfo);
01186   return MergeAliasResults(ThisAlias, Alias);
01187 }
01188 
01189 /// Provide a bunch of ad-hoc rules to disambiguate a PHI instruction against
01190 /// another.
01191 AliasResult BasicAAResult::aliasPHI(const PHINode *PN, uint64_t PNSize,
01192                                     const AAMDNodes &PNAAInfo, const Value *V2,
01193                                     uint64_t V2Size,
01194                                     const AAMDNodes &V2AAInfo) {
01195   // Track phi nodes we have visited. We use this information when we determine
01196   // value equivalence.
01197   VisitedPhiBBs.insert(PN->getParent());
01198 
01199   // If the values are PHIs in the same block, we can do a more precise
01200   // as well as efficient check: just check for aliases between the values
01201   // on corresponding edges.
01202   if (const PHINode *PN2 = dyn_cast<PHINode>(V2))
01203     if (PN2->getParent() == PN->getParent()) {
01204       LocPair Locs(MemoryLocation(PN, PNSize, PNAAInfo),
01205                    MemoryLocation(V2, V2Size, V2AAInfo));
01206       if (PN > V2)
01207         std::swap(Locs.first, Locs.second);
01208       // Analyse the PHIs' inputs under the assumption that the PHIs are
01209       // NoAlias.
01210       // If the PHIs are May/MustAlias there must be (recursively) an input
01211       // operand from outside the PHIs' cycle that is MayAlias/MustAlias or
01212       // there must be an operation on the PHIs within the PHIs' value cycle
01213       // that causes a MayAlias.
01214       // Pretend the phis do not alias.
01215       AliasResult Alias = NoAlias;
01216       assert(AliasCache.count(Locs) &&
01217              "There must exist an entry for the phi node");
01218       AliasResult OrigAliasResult = AliasCache[Locs];
01219       AliasCache[Locs] = NoAlias;
01220 
01221       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
01222         AliasResult ThisAlias =
01223             aliasCheck(PN->getIncomingValue(i), PNSize, PNAAInfo,
01224                        PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)),
01225                        V2Size, V2AAInfo);
01226         Alias = MergeAliasResults(ThisAlias, Alias);
01227         if (Alias == MayAlias)
01228           break;
01229       }
01230 
01231       // Reset if speculation failed.
01232       if (Alias != NoAlias)
01233         AliasCache[Locs] = OrigAliasResult;
01234 
01235       return Alias;
01236     }
01237 
01238   SmallPtrSet<Value *, 4> UniqueSrc;
01239   SmallVector<Value *, 4> V1Srcs;
01240   bool isRecursive = false;
01241   for (Value *PV1 : PN->incoming_values()) {
01242     if (isa<PHINode>(PV1))
01243       // If any of the source itself is a PHI, return MayAlias conservatively
01244       // to avoid compile time explosion. The worst possible case is if both
01245       // sides are PHI nodes. In which case, this is O(m x n) time where 'm'
01246       // and 'n' are the number of PHI sources.
01247       return MayAlias;
01248 
01249     if (EnableRecPhiAnalysis)
01250       if (GEPOperator *PV1GEP = dyn_cast<GEPOperator>(PV1)) {
01251         // Check whether the incoming value is a GEP that advances the pointer
01252         // result of this PHI node (e.g. in a loop). If this is the case, we
01253         // would recurse and always get a MayAlias. Handle this case specially
01254         // below.
01255         if (PV1GEP->getPointerOperand() == PN && PV1GEP->getNumIndices() == 1 &&
01256             isa<ConstantInt>(PV1GEP->idx_begin())) {
01257           isRecursive = true;
01258           continue;
01259         }
01260       }
01261 
01262     if (UniqueSrc.insert(PV1).second)
01263       V1Srcs.push_back(PV1);
01264   }
01265 
01266   // If this PHI node is recursive, set the size of the accessed memory to
01267   // unknown to represent all the possible values the GEP could advance the
01268   // pointer to.
01269   if (isRecursive)
01270     PNSize = MemoryLocation::UnknownSize;
01271 
01272   AliasResult Alias =
01273       aliasCheck(V2, V2Size, V2AAInfo, V1Srcs[0], PNSize, PNAAInfo);
01274 
01275   // Early exit if the check of the first PHI source against V2 is MayAlias.
01276   // Other results are not possible.
01277   if (Alias == MayAlias)
01278     return MayAlias;
01279 
01280   // If all sources of the PHI node NoAlias or MustAlias V2, then returns
01281   // NoAlias / MustAlias. Otherwise, returns MayAlias.
01282   for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) {
01283     Value *V = V1Srcs[i];
01284 
01285     AliasResult ThisAlias =
01286         aliasCheck(V2, V2Size, V2AAInfo, V, PNSize, PNAAInfo);
01287     Alias = MergeAliasResults(ThisAlias, Alias);
01288     if (Alias == MayAlias)
01289       break;
01290   }
01291 
01292   return Alias;
01293 }
01294 
01295 /// Provides a bunch of ad-hoc rules to disambiguate in common cases, such as
01296 /// array references.
01297 AliasResult BasicAAResult::aliasCheck(const Value *V1, uint64_t V1Size,
01298                                       AAMDNodes V1AAInfo, const Value *V2,
01299                                       uint64_t V2Size, AAMDNodes V2AAInfo) {
01300   // If either of the memory references is empty, it doesn't matter what the
01301   // pointer values are.
01302   if (V1Size == 0 || V2Size == 0)
01303     return NoAlias;
01304 
01305   // Strip off any casts if they exist.
01306   V1 = V1->stripPointerCasts();
01307   V2 = V2->stripPointerCasts();
01308 
01309   // If V1 or V2 is undef, the result is NoAlias because we can always pick a
01310   // value for undef that aliases nothing in the program.
01311   if (isa<UndefValue>(V1) || isa<UndefValue>(V2))
01312     return NoAlias;
01313 
01314   // Are we checking for alias of the same value?
01315   // Because we look 'through' phi nodes, we could look at "Value" pointers from
01316   // different iterations. We must therefore make sure that this is not the
01317   // case. The function isValueEqualInPotentialCycles ensures that this cannot
01318   // happen by looking at the visited phi nodes and making sure they cannot
01319   // reach the value.
01320   if (isValueEqualInPotentialCycles(V1, V2))
01321     return MustAlias;
01322 
01323   if (!V1->getType()->isPointerTy() || !V2->getType()->isPointerTy())
01324     return NoAlias; // Scalars cannot alias each other
01325 
01326   // Figure out what objects these things are pointing to if we can.
01327   const Value *O1 = GetUnderlyingObject(V1, DL, MaxLookupSearchDepth);
01328   const Value *O2 = GetUnderlyingObject(V2, DL, MaxLookupSearchDepth);
01329 
01330   // Null values in the default address space don't point to any object, so they
01331   // don't alias any other pointer.
01332   if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O1))
01333     if (CPN->getType()->getAddressSpace() == 0)
01334       return NoAlias;
01335   if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O2))
01336     if (CPN->getType()->getAddressSpace() == 0)
01337       return NoAlias;
01338 
01339   if (O1 != O2) {
01340     // If V1/V2 point to two different objects, we know that we have no alias.
01341     if (isIdentifiedObject(O1) && isIdentifiedObject(O2))
01342       return NoAlias;
01343 
01344     // Constant pointers can't alias with non-const isIdentifiedObject objects.
01345     if ((isa<Constant>(O1) && isIdentifiedObject(O2) && !isa<Constant>(O2)) ||
01346         (isa<Constant>(O2) && isIdentifiedObject(O1) && !isa<Constant>(O1)))
01347       return NoAlias;
01348 
01349     // Function arguments can't alias with things that are known to be
01350     // unambigously identified at the function level.
01351     if ((isa<Argument>(O1) && isIdentifiedFunctionLocal(O2)) ||
01352         (isa<Argument>(O2) && isIdentifiedFunctionLocal(O1)))
01353       return NoAlias;
01354 
01355     // Most objects can't alias null.
01356     if ((isa<ConstantPointerNull>(O2) && isKnownNonNull(O1)) ||
01357         (isa<ConstantPointerNull>(O1) && isKnownNonNull(O2)))
01358       return NoAlias;
01359 
01360     // If one pointer is the result of a call/invoke or load and the other is a
01361     // non-escaping local object within the same function, then we know the
01362     // object couldn't escape to a point where the call could return it.
01363     //
01364     // Note that if the pointers are in different functions, there are a
01365     // variety of complications. A call with a nocapture argument may still
01366     // temporary store the nocapture argument's value in a temporary memory
01367     // location if that memory location doesn't escape. Or it may pass a
01368     // nocapture value to other functions as long as they don't capture it.
01369     if (isEscapeSource(O1) && isNonEscapingLocalObject(O2))
01370       return NoAlias;
01371     if (isEscapeSource(O2) && isNonEscapingLocalObject(O1))
01372       return NoAlias;
01373   }
01374 
01375   // If the size of one access is larger than the entire object on the other
01376   // side, then we know such behavior is undefined and can assume no alias.
01377   if ((V1Size != MemoryLocation::UnknownSize &&
01378        isObjectSmallerThan(O2, V1Size, DL, TLI)) ||
01379       (V2Size != MemoryLocation::UnknownSize &&
01380        isObjectSmallerThan(O1, V2Size, DL, TLI)))
01381     return NoAlias;
01382 
01383   // Check the cache before climbing up use-def chains. This also terminates
01384   // otherwise infinitely recursive queries.
01385   LocPair Locs(MemoryLocation(V1, V1Size, V1AAInfo),
01386                MemoryLocation(V2, V2Size, V2AAInfo));
01387   if (V1 > V2)
01388     std::swap(Locs.first, Locs.second);
01389   std::pair<AliasCacheTy::iterator, bool> Pair =
01390       AliasCache.insert(std::make_pair(Locs, MayAlias));
01391   if (!Pair.second)
01392     return Pair.first->second;
01393 
01394   // FIXME: This isn't aggressively handling alias(GEP, PHI) for example: if the
01395   // GEP can't simplify, we don't even look at the PHI cases.
01396   if (!isa<GEPOperator>(V1) && isa<GEPOperator>(V2)) {
01397     std::swap(V1, V2);
01398     std::swap(V1Size, V2Size);
01399     std::swap(O1, O2);
01400     std::swap(V1AAInfo, V2AAInfo);
01401   }
01402   if (const GEPOperator *GV1 = dyn_cast<GEPOperator>(V1)) {
01403     AliasResult Result =
01404         aliasGEP(GV1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, O1, O2);
01405     if (Result != MayAlias)
01406       return AliasCache[Locs] = Result;
01407   }
01408 
01409   if (isa<PHINode>(V2) && !isa<PHINode>(V1)) {
01410     std::swap(V1, V2);
01411     std::swap(V1Size, V2Size);
01412     std::swap(V1AAInfo, V2AAInfo);
01413   }
01414   if (const PHINode *PN = dyn_cast<PHINode>(V1)) {
01415     AliasResult Result = aliasPHI(PN, V1Size, V1AAInfo, V2, V2Size, V2AAInfo);
01416     if (Result != MayAlias)
01417       return AliasCache[Locs] = Result;
01418   }
01419 
01420   if (isa<SelectInst>(V2) && !isa<SelectInst>(V1)) {
01421     std::swap(V1, V2);
01422     std::swap(V1Size, V2Size);
01423     std::swap(V1AAInfo, V2AAInfo);
01424   }
01425   if (const SelectInst *S1 = dyn_cast<SelectInst>(V1)) {
01426     AliasResult Result =
01427         aliasSelect(S1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo);
01428     if (Result != MayAlias)
01429       return AliasCache[Locs] = Result;
01430   }
01431 
01432   // If both pointers are pointing into the same object and one of them
01433   // accesses the entire object, then the accesses must overlap in some way.
01434   if (O1 == O2)
01435     if ((V1Size != MemoryLocation::UnknownSize &&
01436          isObjectSize(O1, V1Size, DL, TLI)) ||
01437         (V2Size != MemoryLocation::UnknownSize &&
01438          isObjectSize(O2, V2Size, DL, TLI)))
01439       return AliasCache[Locs] = PartialAlias;
01440 
01441   // Recurse back into the best AA results we have, potentially with refined
01442   // memory locations. We have already ensured that BasicAA has a MayAlias
01443   // cache result for these, so any recursion back into BasicAA won't loop.
01444   AliasResult Result = getBestAAResults().alias(Locs.first, Locs.second);
01445   return AliasCache[Locs] = Result;
01446 }
01447 
01448 /// Check whether two Values can be considered equivalent.
01449 ///
01450 /// In addition to pointer equivalence of \p V1 and \p V2 this checks whether
01451 /// they can not be part of a cycle in the value graph by looking at all
01452 /// visited phi nodes an making sure that the phis cannot reach the value. We
01453 /// have to do this because we are looking through phi nodes (That is we say
01454 /// noalias(V, phi(VA, VB)) if noalias(V, VA) and noalias(V, VB).
01455 bool BasicAAResult::isValueEqualInPotentialCycles(const Value *V,
01456                                                   const Value *V2) {
01457   if (V != V2)
01458     return false;
01459 
01460   const Instruction *Inst = dyn_cast<Instruction>(V);
01461   if (!Inst)
01462     return true;
01463 
01464   if (VisitedPhiBBs.empty())
01465     return true;
01466 
01467   if (VisitedPhiBBs.size() > MaxNumPhiBBsValueReachabilityCheck)
01468     return false;
01469 
01470   // Make sure that the visited phis cannot reach the Value. This ensures that
01471   // the Values cannot come from different iterations of a potential cycle the
01472   // phi nodes could be involved in.
01473   for (auto *P : VisitedPhiBBs)
01474     if (isPotentiallyReachable(&P->front(), Inst, DT, LI))
01475       return false;
01476 
01477   return true;
01478 }
01479 
01480 /// Computes the symbolic difference between two de-composed GEPs.
01481 ///
01482 /// Dest and Src are the variable indices from two decomposed GetElementPtr
01483 /// instructions GEP1 and GEP2 which have common base pointers.
01484 void BasicAAResult::GetIndexDifference(
01485     SmallVectorImpl<VariableGEPIndex> &Dest,
01486     const SmallVectorImpl<VariableGEPIndex> &Src) {
01487   if (Src.empty())
01488     return;
01489 
01490   for (unsigned i = 0, e = Src.size(); i != e; ++i) {
01491     const Value *V = Src[i].V;
01492     unsigned ZExtBits = Src[i].ZExtBits, SExtBits = Src[i].SExtBits;
01493     int64_t Scale = Src[i].Scale;
01494 
01495     // Find V in Dest.  This is N^2, but pointer indices almost never have more
01496     // than a few variable indexes.
01497     for (unsigned j = 0, e = Dest.size(); j != e; ++j) {
01498       if (!isValueEqualInPotentialCycles(Dest[j].V, V) ||
01499           Dest[j].ZExtBits != ZExtBits || Dest[j].SExtBits != SExtBits)
01500         continue;
01501 
01502       // If we found it, subtract off Scale V's from the entry in Dest.  If it
01503       // goes to zero, remove the entry.
01504       if (Dest[j].Scale != Scale)
01505         Dest[j].Scale -= Scale;
01506       else
01507         Dest.erase(Dest.begin() + j);
01508       Scale = 0;
01509       break;
01510     }
01511 
01512     // If we didn't consume this entry, add it to the end of the Dest list.
01513     if (Scale) {
01514       VariableGEPIndex Entry = {V, ZExtBits, SExtBits, -Scale};
01515       Dest.push_back(Entry);
01516     }
01517   }
01518 }
01519 
01520 bool BasicAAResult::constantOffsetHeuristic(
01521     const SmallVectorImpl<VariableGEPIndex> &VarIndices, uint64_t V1Size,
01522     uint64_t V2Size, int64_t BaseOffset, AssumptionCache *AC,
01523     DominatorTree *DT) {
01524   if (VarIndices.size() != 2 || V1Size == MemoryLocation::UnknownSize ||
01525       V2Size == MemoryLocation::UnknownSize)
01526     return false;
01527 
01528   const VariableGEPIndex &Var0 = VarIndices[0], &Var1 = VarIndices[1];
01529 
01530   if (Var0.ZExtBits != Var1.ZExtBits || Var0.SExtBits != Var1.SExtBits ||
01531       Var0.Scale != -Var1.Scale)
01532     return false;
01533 
01534   unsigned Width = Var1.V->getType()->getIntegerBitWidth();
01535 
01536   // We'll strip off the Extensions of Var0 and Var1 and do another round
01537   // of GetLinearExpression decomposition. In the example above, if Var0
01538   // is zext(%x + 1) we should get V1 == %x and V1Offset == 1.
01539 
01540   APInt V0Scale(Width, 0), V0Offset(Width, 0), V1Scale(Width, 0),
01541       V1Offset(Width, 0);
01542   bool NSW = true, NUW = true;
01543   unsigned V0ZExtBits = 0, V0SExtBits = 0, V1ZExtBits = 0, V1SExtBits = 0;
01544   const Value *V0 = GetLinearExpression(Var0.V, V0Scale, V0Offset, V0ZExtBits,
01545                                         V0SExtBits, DL, 0, AC, DT, NSW, NUW);
01546   NSW = true, NUW = true;
01547   const Value *V1 = GetLinearExpression(Var1.V, V1Scale, V1Offset, V1ZExtBits,
01548                                         V1SExtBits, DL, 0, AC, DT, NSW, NUW);
01549 
01550   if (V0Scale != V1Scale || V0ZExtBits != V1ZExtBits ||
01551       V0SExtBits != V1SExtBits || !isValueEqualInPotentialCycles(V0, V1))
01552     return false;
01553 
01554   // We have a hit - Var0 and Var1 only differ by a constant offset!
01555 
01556   // If we've been sext'ed then zext'd the maximum difference between Var0 and
01557   // Var1 is possible to calculate, but we're just interested in the absolute
01558   // minimum difference between the two. The minimum distance may occur due to
01559   // wrapping; consider "add i3 %i, 5": if %i == 7 then 7 + 5 mod 8 == 4, and so
01560   // the minimum distance between %i and %i + 5 is 3.
01561   APInt MinDiff = V0Offset - V1Offset, Wrapped = -MinDiff;
01562   MinDiff = APIntOps::umin(MinDiff, Wrapped);
01563   uint64_t MinDiffBytes = MinDiff.getZExtValue() * std::abs(Var0.Scale);
01564 
01565   // We can't definitely say whether GEP1 is before or after V2 due to wrapping
01566   // arithmetic (i.e. for some values of GEP1 and V2 GEP1 < V2, and for other
01567   // values GEP1 > V2). We'll therefore only declare NoAlias if both V1Size and
01568   // V2Size can fit in the MinDiffBytes gap.
01569   return V1Size + std::abs(BaseOffset) <= MinDiffBytes &&
01570          V2Size + std::abs(BaseOffset) <= MinDiffBytes;
01571 }
01572 
01573 //===----------------------------------------------------------------------===//
01574 // BasicAliasAnalysis Pass
01575 //===----------------------------------------------------------------------===//
01576 
01577 char BasicAA::PassID;
01578 
01579 BasicAAResult BasicAA::run(Function &F, AnalysisManager<Function> *AM) {
01580   return BasicAAResult(F.getParent()->getDataLayout(),
01581                        AM->getResult<TargetLibraryAnalysis>(F),
01582                        AM->getResult<AssumptionAnalysis>(F),
01583                        AM->getCachedResult<DominatorTreeAnalysis>(F),
01584                        AM->getCachedResult<LoopAnalysis>(F));
01585 }
01586 
01587 BasicAAWrapperPass::BasicAAWrapperPass() : FunctionPass(ID) {
01588     initializeBasicAAWrapperPassPass(*PassRegistry::getPassRegistry());
01589 }
01590 
01591 char BasicAAWrapperPass::ID = 0;
01592 void BasicAAWrapperPass::anchor() {}
01593 
01594 INITIALIZE_PASS_BEGIN(BasicAAWrapperPass, "basicaa",
01595                       "Basic Alias Analysis (stateless AA impl)", true, true)
01596 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
01597 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
01598 INITIALIZE_PASS_END(BasicAAWrapperPass, "basicaa",
01599                     "Basic Alias Analysis (stateless AA impl)", true, true)
01600 
01601 FunctionPass *llvm::createBasicAAWrapperPass() {
01602   return new BasicAAWrapperPass();
01603 }
01604 
01605 bool BasicAAWrapperPass::runOnFunction(Function &F) {
01606   auto &ACT = getAnalysis<AssumptionCacheTracker>();
01607   auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>();
01608   auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
01609   auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
01610 
01611   Result.reset(new BasicAAResult(F.getParent()->getDataLayout(), TLIWP.getTLI(),
01612                                  ACT.getAssumptionCache(F),
01613                                  DTWP ? &DTWP->getDomTree() : nullptr,
01614                                  LIWP ? &LIWP->getLoopInfo() : nullptr));
01615 
01616   return false;
01617 }
01618 
01619 void BasicAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
01620   AU.setPreservesAll();
01621   AU.addRequired<AssumptionCacheTracker>();
01622   AU.addRequired<TargetLibraryInfoWrapperPass>();
01623 }
01624 
01625 BasicAAResult llvm::createLegacyPMBasicAAResult(Pass &P, Function &F) {
01626   return BasicAAResult(
01627       F.getParent()->getDataLayout(),
01628       P.getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(),
01629       P.getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F));
01630 }