1218893Sdim//===- BasicAliasAnalysis.cpp - Stateless Alias Analysis Impl -------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10218893Sdim// This file defines the primary stateless implementation of the 11218893Sdim// Alias Analysis interface that implements identities (two different 12218893Sdim// globals cannot alias, etc), but does no stateful analysis. 13193323Sed// 14193323Sed//===----------------------------------------------------------------------===// 15193323Sed 16296417Sdim#include "llvm/Analysis/BasicAliasAnalysis.h" 17249423Sdim#include "llvm/ADT/SmallVector.h" 18296417Sdim#include "llvm/ADT/Statistic.h" 19193323Sed#include "llvm/Analysis/AliasAnalysis.h" 20276479Sdim#include "llvm/Analysis/CFG.h" 21199989Srdivacky#include "llvm/Analysis/CaptureTracking.h" 22249423Sdim#include "llvm/Analysis/InstructionSimplify.h" 23265925Sdim#include "llvm/Analysis/LoopInfo.h" 24199989Srdivacky#include "llvm/Analysis/MemoryBuiltins.h" 25199989Srdivacky#include "llvm/Analysis/ValueTracking.h" 26296417Sdim#include "llvm/Analysis/AssumptionCache.h" 27249423Sdim#include "llvm/IR/Constants.h" 28249423Sdim#include "llvm/IR/DataLayout.h" 29249423Sdim#include "llvm/IR/DerivedTypes.h" 30276479Sdim#include "llvm/IR/Dominators.h" 31249423Sdim#include "llvm/IR/GlobalAlias.h" 32249423Sdim#include "llvm/IR/GlobalVariable.h" 33249423Sdim#include "llvm/IR/Instructions.h" 34249423Sdim#include "llvm/IR/IntrinsicInst.h" 35249423Sdim#include "llvm/IR/LLVMContext.h" 36249423Sdim#include "llvm/IR/Operator.h" 37249423Sdim#include "llvm/Pass.h" 38198090Srdivacky#include "llvm/Support/ErrorHandling.h" 39193323Sed#include <algorithm> 40193323Sedusing namespace llvm; 41193323Sed 42296417Sdim/// Enable analysis of recursive PHI nodes. 43296417Sdimstatic cl::opt<bool> EnableRecPhiAnalysis("basicaa-recphi", cl::Hidden, 44296417Sdim cl::init(false)); 45296417Sdim 46296417Sdim/// SearchLimitReached / SearchTimes shows how often the limit of 47296417Sdim/// to decompose GEPs is reached. It will affect the precision 48296417Sdim/// of basic alias analysis. 49296417Sdim#define DEBUG_TYPE "basicaa" 50296417SdimSTATISTIC(SearchLimitReached, "Number of times the limit to " 51296417Sdim "decompose GEPs is reached"); 52296417SdimSTATISTIC(SearchTimes, "Number of times a GEP is decomposed"); 53296417Sdim 54265925Sdim/// Cutoff after which to stop analysing a set of phi nodes potentially involved 55265925Sdim/// in a cycle. Because we are analysing 'through' phi nodes we need to be 56265925Sdim/// careful with value equivalence. We use reachability to make sure a value 57265925Sdim/// cannot be involved in a cycle. 58265925Sdimconst unsigned MaxNumPhiBBsValueReachabilityCheck = 20; 59265925Sdim 60276479Sdim// The max limit of the search depth in DecomposeGEPExpression() and 61276479Sdim// GetUnderlyingObject(), both functions need to use the same search 62276479Sdim// depth otherwise the algorithm in aliasGEP will assert. 63276479Sdimstatic const unsigned MaxLookupSearchDepth = 6; 64276479Sdim 65193323Sed//===----------------------------------------------------------------------===// 66193323Sed// Useful predicates 67193323Sed//===----------------------------------------------------------------------===// 68193323Sed 69296417Sdim/// Returns true if the pointer is to a function-local object that never 70296417Sdim/// escapes from the function. 71193323Sedstatic bool isNonEscapingLocalObject(const Value *V) { 72193323Sed // If this is a local allocation, check to see if it escapes. 73198892Srdivacky if (isa<AllocaInst>(V) || isNoAliasCall(V)) 74199989Srdivacky // Set StoreCaptures to True so that we can assume in our callers that the 75199989Srdivacky // pointer is not the result of a load instruction. Currently 76199989Srdivacky // PointerMayBeCaptured doesn't have any special analysis for the 77199989Srdivacky // StoreCaptures=false case; if it did, our callers could be refined to be 78199989Srdivacky // more precise. 79199989Srdivacky return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true); 80193323Sed 81193323Sed // If this is an argument that corresponds to a byval or noalias argument, 82193323Sed // then it has not escaped before entering the function. Check if it escapes 83193323Sed // inside the function. 84193323Sed if (const Argument *A = dyn_cast<Argument>(V)) 85243830Sdim if (A->hasByValAttr() || A->hasNoAliasAttr()) 86243830Sdim // Note even if the argument is marked nocapture we still need to check 87243830Sdim // for copies made inside the function. The nocapture attribute only 88243830Sdim // specifies that there are no copies made that outlive the function. 89199989Srdivacky return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true); 90243830Sdim 91193323Sed return false; 92193323Sed} 93193323Sed 94296417Sdim/// Returns true if the pointer is one which would have been considered an 95296417Sdim/// escape by isNonEscapingLocalObject. 96210299Sedstatic bool isEscapeSource(const Value *V) { 97210299Sed if (isa<CallInst>(V) || isa<InvokeInst>(V) || isa<Argument>(V)) 98210299Sed return true; 99193323Sed 100210299Sed // The load case works because isNonEscapingLocalObject considers all 101210299Sed // stores to be escapes (it passes true for the StoreCaptures argument 102210299Sed // to PointerMayBeCaptured). 103210299Sed if (isa<LoadInst>(V)) 104210299Sed return true; 105210299Sed 106210299Sed return false; 107210299Sed} 108210299Sed 109296417Sdim/// Returns the size of the object specified by V, or UnknownSize if unknown. 110276479Sdimstatic uint64_t getObjectSize(const Value *V, const DataLayout &DL, 111243830Sdim const TargetLibraryInfo &TLI, 112234353Sdim bool RoundToAlign = false) { 113239462Sdim uint64_t Size; 114288943Sdim if (getObjectSize(V, Size, DL, &TLI, RoundToAlign)) 115239462Sdim return Size; 116288943Sdim return MemoryLocation::UnknownSize; 117193323Sed} 118193323Sed 119296417Sdim/// Returns true if we can prove that the object specified by V is smaller than 120296417Sdim/// Size. 121218893Sdimstatic bool isObjectSmallerThan(const Value *V, uint64_t Size, 122276479Sdim const DataLayout &DL, 123243830Sdim const TargetLibraryInfo &TLI) { 124251662Sdim // Note that the meanings of the "object" are slightly different in the 125251662Sdim // following contexts: 126251662Sdim // c1: llvm::getObjectSize() 127251662Sdim // c2: llvm.objectsize() intrinsic 128251662Sdim // c3: isObjectSmallerThan() 129251662Sdim // c1 and c2 share the same meaning; however, the meaning of "object" in c3 130251662Sdim // refers to the "entire object". 131251662Sdim // 132251662Sdim // Consider this example: 133251662Sdim // char *p = (char*)malloc(100) 134251662Sdim // char *q = p+80; 135251662Sdim // 136251662Sdim // In the context of c1 and c2, the "object" pointed by q refers to the 137251662Sdim // stretch of memory of q[0:19]. So, getObjectSize(q) should return 20. 138251662Sdim // 139251662Sdim // However, in the context of c3, the "object" refers to the chunk of memory 140251662Sdim // being allocated. So, the "object" has 100 bytes, and q points to the middle 141251662Sdim // the "object". In case q is passed to isObjectSmallerThan() as the 1st 142251662Sdim // parameter, before the llvm::getObjectSize() is called to get the size of 143251662Sdim // entire object, we should: 144251662Sdim // - either rewind the pointer q to the base-address of the object in 145251662Sdim // question (in this case rewind to p), or 146251662Sdim // - just give up. It is up to caller to make sure the pointer is pointing 147251662Sdim // to the base address the object. 148261991Sdim // 149251662Sdim // We go for 2nd option for simplicity. 150251662Sdim if (!isIdentifiedObject(V)) 151251662Sdim return false; 152251662Sdim 153234353Sdim // This function needs to use the aligned object size because we allow 154234353Sdim // reads a bit past the end given sufficient alignment. 155296417Sdim uint64_t ObjectSize = getObjectSize(V, DL, TLI, /*RoundToAlign*/ true); 156261991Sdim 157288943Sdim return ObjectSize != MemoryLocation::UnknownSize && ObjectSize < Size; 158218893Sdim} 159193323Sed 160296417Sdim/// Returns true if we can prove that the object specified by V has size Size. 161296417Sdimstatic bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &DL, 162296417Sdim const TargetLibraryInfo &TLI) { 163276479Sdim uint64_t ObjectSize = getObjectSize(V, DL, TLI); 164288943Sdim return ObjectSize != MemoryLocation::UnknownSize && ObjectSize == Size; 165218893Sdim} 166193323Sed 167193323Sed//===----------------------------------------------------------------------===// 168212904Sdim// GetElementPtr Instruction Decomposition and Analysis 169212904Sdim//===----------------------------------------------------------------------===// 170212904Sdim 171296417Sdim/// Analyzes the specified value as a linear expression: "A*V + B", where A and 172296417Sdim/// B are constant integers. 173212904Sdim/// 174296417Sdim/// Returns the scale and offset values as APInts and return V as a Value*, and 175296417Sdim/// return whether we looked through any sign or zero extends. The incoming 176296417Sdim/// Value is known to have IntegerType and it may already be sign or zero 177296417Sdim/// extended. 178296417Sdim/// 179212904Sdim/// Note that this looks through extends, so the high bits may not be 180212904Sdim/// represented in the result. 181296417Sdim/*static*/ const Value *BasicAAResult::GetLinearExpression( 182296417Sdim const Value *V, APInt &Scale, APInt &Offset, unsigned &ZExtBits, 183296417Sdim unsigned &SExtBits, const DataLayout &DL, unsigned Depth, 184296417Sdim AssumptionCache *AC, DominatorTree *DT, bool &NSW, bool &NUW) { 185212904Sdim assert(V->getType()->isIntegerTy() && "Not an integer value"); 186212904Sdim 187212904Sdim // Limit our recursion depth. 188212904Sdim if (Depth == 6) { 189212904Sdim Scale = 1; 190212904Sdim Offset = 0; 191212904Sdim return V; 192212904Sdim } 193261991Sdim 194296417Sdim if (const ConstantInt *Const = dyn_cast<ConstantInt>(V)) { 195296417Sdim // if it's a constant, just convert it to an offset and remove the variable. 196296417Sdim // If we've been called recursively the Offset bit width will be greater 197296417Sdim // than the constant's (the Offset's always as wide as the outermost call), 198296417Sdim // so we'll zext here and process any extension in the isa<SExtInst> & 199296417Sdim // isa<ZExtInst> cases below. 200296417Sdim Offset += Const->getValue().zextOrSelf(Offset.getBitWidth()); 201296417Sdim assert(Scale == 0 && "Constant values don't have a scale"); 202296417Sdim return V; 203296417Sdim } 204296417Sdim 205296417Sdim if (const BinaryOperator *BOp = dyn_cast<BinaryOperator>(V)) { 206212904Sdim if (ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) { 207296417Sdim 208296417Sdim // If we've been called recursively then Offset and Scale will be wider 209296417Sdim // that the BOp operands. We'll always zext it here as we'll process sign 210296417Sdim // extensions below (see the isa<SExtInst> / isa<ZExtInst> cases). 211296417Sdim APInt RHS = RHSC->getValue().zextOrSelf(Offset.getBitWidth()); 212296417Sdim 213212904Sdim switch (BOp->getOpcode()) { 214296417Sdim default: 215296417Sdim // We don't understand this instruction, so we can't decompose it any 216296417Sdim // further. 217296417Sdim Scale = 1; 218296417Sdim Offset = 0; 219296417Sdim return V; 220212904Sdim case Instruction::Or: 221212904Sdim // X|C == X+C if all the bits in C are unset in X. Otherwise we can't 222212904Sdim // analyze it. 223288943Sdim if (!MaskedValueIsZero(BOp->getOperand(0), RHSC->getValue(), DL, 0, AC, 224296417Sdim BOp, DT)) { 225296417Sdim Scale = 1; 226296417Sdim Offset = 0; 227296417Sdim return V; 228296417Sdim } 229296417Sdim // FALL THROUGH. 230212904Sdim case Instruction::Add: 231296417Sdim V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits, 232296417Sdim SExtBits, DL, Depth + 1, AC, DT, NSW, NUW); 233296417Sdim Offset += RHS; 234296417Sdim break; 235296417Sdim case Instruction::Sub: 236296417Sdim V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits, 237296417Sdim SExtBits, DL, Depth + 1, AC, DT, NSW, NUW); 238296417Sdim Offset -= RHS; 239296417Sdim break; 240212904Sdim case Instruction::Mul: 241296417Sdim V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits, 242296417Sdim SExtBits, DL, Depth + 1, AC, DT, NSW, NUW); 243296417Sdim Offset *= RHS; 244296417Sdim Scale *= RHS; 245296417Sdim break; 246212904Sdim case Instruction::Shl: 247296417Sdim V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits, 248296417Sdim SExtBits, DL, Depth + 1, AC, DT, NSW, NUW); 249296417Sdim Offset <<= RHS.getLimitedValue(); 250296417Sdim Scale <<= RHS.getLimitedValue(); 251296417Sdim // the semantics of nsw and nuw for left shifts don't match those of 252296417Sdim // multiplications, so we won't propagate them. 253296417Sdim NSW = NUW = false; 254212904Sdim return V; 255212904Sdim } 256296417Sdim 257296417Sdim if (isa<OverflowingBinaryOperator>(BOp)) { 258296417Sdim NUW &= BOp->hasNoUnsignedWrap(); 259296417Sdim NSW &= BOp->hasNoSignedWrap(); 260296417Sdim } 261296417Sdim return V; 262212904Sdim } 263212904Sdim } 264261991Sdim 265212904Sdim // Since GEP indices are sign extended anyway, we don't care about the high 266212904Sdim // bits of a sign or zero extended value - just scales and offsets. The 267212904Sdim // extensions have to be consistent though. 268296417Sdim if (isa<SExtInst>(V) || isa<ZExtInst>(V)) { 269212904Sdim Value *CastOp = cast<CastInst>(V)->getOperand(0); 270296417Sdim unsigned NewWidth = V->getType()->getPrimitiveSizeInBits(); 271212904Sdim unsigned SmallWidth = CastOp->getType()->getPrimitiveSizeInBits(); 272296417Sdim unsigned OldZExtBits = ZExtBits, OldSExtBits = SExtBits; 273296417Sdim const Value *Result = 274296417Sdim GetLinearExpression(CastOp, Scale, Offset, ZExtBits, SExtBits, DL, 275296417Sdim Depth + 1, AC, DT, NSW, NUW); 276212904Sdim 277296417Sdim // zext(zext(%x)) == zext(%x), and similiarly for sext; we'll handle this 278296417Sdim // by just incrementing the number of bits we've extended by. 279296417Sdim unsigned ExtendedBy = NewWidth - SmallWidth; 280261991Sdim 281296417Sdim if (isa<SExtInst>(V) && ZExtBits == 0) { 282296417Sdim // sext(sext(%x, a), b) == sext(%x, a + b) 283296417Sdim 284296417Sdim if (NSW) { 285296417Sdim // We haven't sign-wrapped, so it's valid to decompose sext(%x + c) 286296417Sdim // into sext(%x) + sext(c). We'll sext the Offset ourselves: 287296417Sdim unsigned OldWidth = Offset.getBitWidth(); 288296417Sdim Offset = Offset.trunc(SmallWidth).sext(NewWidth).zextOrSelf(OldWidth); 289296417Sdim } else { 290296417Sdim // We may have signed-wrapped, so don't decompose sext(%x + c) into 291296417Sdim // sext(%x) + sext(c) 292296417Sdim Scale = 1; 293296417Sdim Offset = 0; 294296417Sdim Result = CastOp; 295296417Sdim ZExtBits = OldZExtBits; 296296417Sdim SExtBits = OldSExtBits; 297296417Sdim } 298296417Sdim SExtBits += ExtendedBy; 299296417Sdim } else { 300296417Sdim // sext(zext(%x, a), b) = zext(zext(%x, a), b) = zext(%x, a + b) 301296417Sdim 302296417Sdim if (!NUW) { 303296417Sdim // We may have unsigned-wrapped, so don't decompose zext(%x + c) into 304296417Sdim // zext(%x) + zext(c) 305296417Sdim Scale = 1; 306296417Sdim Offset = 0; 307296417Sdim Result = CastOp; 308296417Sdim ZExtBits = OldZExtBits; 309296417Sdim SExtBits = OldSExtBits; 310296417Sdim } 311296417Sdim ZExtBits += ExtendedBy; 312296417Sdim } 313296417Sdim 314212904Sdim return Result; 315212904Sdim } 316261991Sdim 317212904Sdim Scale = 1; 318212904Sdim Offset = 0; 319212904Sdim return V; 320212904Sdim} 321212904Sdim 322296417Sdim/// If V is a symbolic pointer expression, decompose it into a base pointer 323296417Sdim/// with a constant offset and a number of scaled symbolic offsets. 324212904Sdim/// 325296417Sdim/// The scaled symbolic offsets (represented by pairs of a Value* and a scale 326296417Sdim/// in the VarIndices vector) are Value*'s that are known to be scaled by the 327296417Sdim/// specified amount, but which may have other unrepresented high bits. As 328296417Sdim/// such, the gep cannot necessarily be reconstructed from its decomposed form. 329212904Sdim/// 330243830Sdim/// When DataLayout is around, this function is capable of analyzing everything 331276479Sdim/// that GetUnderlyingObject can look through. To be able to do that 332276479Sdim/// GetUnderlyingObject and DecomposeGEPExpression must use the same search 333296417Sdim/// depth (MaxLookupSearchDepth). When DataLayout not is around, it just looks 334296417Sdim/// through pointer casts. 335296417Sdim/*static*/ const Value *BasicAAResult::DecomposeGEPExpression( 336296417Sdim const Value *V, int64_t &BaseOffs, 337296417Sdim SmallVectorImpl<VariableGEPIndex> &VarIndices, bool &MaxLookupReached, 338296417Sdim const DataLayout &DL, AssumptionCache *AC, DominatorTree *DT) { 339212904Sdim // Limit recursion depth to limit compile time in crazy cases. 340276479Sdim unsigned MaxLookup = MaxLookupSearchDepth; 341276479Sdim MaxLookupReached = false; 342296417Sdim SearchTimes++; 343261991Sdim 344212904Sdim BaseOffs = 0; 345212904Sdim do { 346212904Sdim // See if this is a bitcast or GEP. 347212904Sdim const Operator *Op = dyn_cast<Operator>(V); 348276479Sdim if (!Op) { 349212904Sdim // The only non-operator case we can handle are GlobalAliases. 350212904Sdim if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 351212904Sdim if (!GA->mayBeOverridden()) { 352212904Sdim V = GA->getAliasee(); 353212904Sdim continue; 354212904Sdim } 355212904Sdim } 356212904Sdim return V; 357212904Sdim } 358261991Sdim 359276479Sdim if (Op->getOpcode() == Instruction::BitCast || 360276479Sdim Op->getOpcode() == Instruction::AddrSpaceCast) { 361212904Sdim V = Op->getOperand(0); 362212904Sdim continue; 363212904Sdim } 364218893Sdim 365223017Sdim const GEPOperator *GEPOp = dyn_cast<GEPOperator>(Op); 366276479Sdim if (!GEPOp) { 367223017Sdim // If it's not a GEP, hand it off to SimplifyInstruction to see if it 368223017Sdim // can come up with something. This matches what GetUnderlyingObject does. 369223017Sdim if (const Instruction *I = dyn_cast<Instruction>(V)) 370280031Sdim // TODO: Get a DominatorTree and AssumptionCache and use them here 371280031Sdim // (these are both now available in this function, but this should be 372280031Sdim // updated when GetUnderlyingObject is updated). TLI should be 373280031Sdim // provided also. 374223017Sdim if (const Value *Simplified = 375296417Sdim SimplifyInstruction(const_cast<Instruction *>(I), DL)) { 376223017Sdim V = Simplified; 377223017Sdim continue; 378223017Sdim } 379261991Sdim 380212904Sdim return V; 381223017Sdim } 382261991Sdim 383212904Sdim // Don't attempt to analyze GEPs over unsized objects. 384261991Sdim if (!GEPOp->getOperand(0)->getType()->getPointerElementType()->isSized()) 385212904Sdim return V; 386261991Sdim 387261991Sdim unsigned AS = GEPOp->getPointerAddressSpace(); 388212904Sdim // Walk the indices of the GEP, accumulating them into BaseOff/VarIndices. 389212904Sdim gep_type_iterator GTI = gep_type_begin(GEPOp); 390296417Sdim for (User::const_op_iterator I = GEPOp->op_begin() + 1, E = GEPOp->op_end(); 391296417Sdim I != E; ++I) { 392296417Sdim const Value *Index = *I; 393212904Sdim // Compute the (potentially symbolic) offset in bytes for this index. 394226633Sdim if (StructType *STy = dyn_cast<StructType>(*GTI++)) { 395212904Sdim // For a struct, add the member offset. 396212904Sdim unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue(); 397296417Sdim if (FieldNo == 0) 398296417Sdim continue; 399261991Sdim 400288943Sdim BaseOffs += DL.getStructLayout(STy)->getElementOffset(FieldNo); 401212904Sdim continue; 402212904Sdim } 403261991Sdim 404212904Sdim // For an array/pointer, add the element offset, explicitly scaled. 405296417Sdim if (const ConstantInt *CIdx = dyn_cast<ConstantInt>(Index)) { 406296417Sdim if (CIdx->isZero()) 407296417Sdim continue; 408288943Sdim BaseOffs += DL.getTypeAllocSize(*GTI) * CIdx->getSExtValue(); 409212904Sdim continue; 410212904Sdim } 411261991Sdim 412288943Sdim uint64_t Scale = DL.getTypeAllocSize(*GTI); 413296417Sdim unsigned ZExtBits = 0, SExtBits = 0; 414261991Sdim 415212904Sdim // If the integer type is smaller than the pointer size, it is implicitly 416212904Sdim // sign extended to pointer size. 417261991Sdim unsigned Width = Index->getType()->getIntegerBitWidth(); 418296417Sdim unsigned PointerSize = DL.getPointerSizeInBits(AS); 419296417Sdim if (PointerSize > Width) 420296417Sdim SExtBits += PointerSize - Width; 421261991Sdim 422212904Sdim // Use GetLinearExpression to decompose the index into a C1*V+C2 form. 423212904Sdim APInt IndexScale(Width, 0), IndexOffset(Width, 0); 424296417Sdim bool NSW = true, NUW = true; 425296417Sdim Index = GetLinearExpression(Index, IndexScale, IndexOffset, ZExtBits, 426296417Sdim SExtBits, DL, 0, AC, DT, NSW, NUW); 427261991Sdim 428212904Sdim // The GEP index scale ("Scale") scales C1*V+C2, yielding (C1*V+C2)*Scale. 429212904Sdim // This gives us an aggregate computation of (C1*Scale)*V + C2*Scale. 430296417Sdim BaseOffs += IndexOffset.getSExtValue() * Scale; 431218893Sdim Scale *= IndexScale.getSExtValue(); 432261991Sdim 433221345Sdim // If we already had an occurrence of this index variable, merge this 434212904Sdim // scale into it. For example, we want to handle: 435212904Sdim // A[x][x] -> x*16 + x*4 -> x*20 436212904Sdim // This also ensures that 'x' only appears in the index list once. 437212904Sdim for (unsigned i = 0, e = VarIndices.size(); i != e; ++i) { 438296417Sdim if (VarIndices[i].V == Index && VarIndices[i].ZExtBits == ZExtBits && 439296417Sdim VarIndices[i].SExtBits == SExtBits) { 440212904Sdim Scale += VarIndices[i].Scale; 441296417Sdim VarIndices.erase(VarIndices.begin() + i); 442212904Sdim break; 443212904Sdim } 444212904Sdim } 445261991Sdim 446212904Sdim // Make sure that we have a scale that makes sense for this target's 447212904Sdim // pointer size. 448296417Sdim if (unsigned ShiftBits = 64 - PointerSize) { 449212904Sdim Scale <<= ShiftBits; 450218893Sdim Scale = (int64_t)Scale >> ShiftBits; 451212904Sdim } 452261991Sdim 453212904Sdim if (Scale) { 454296417Sdim VariableGEPIndex Entry = {Index, ZExtBits, SExtBits, 455226633Sdim static_cast<int64_t>(Scale)}; 456212904Sdim VarIndices.push_back(Entry); 457212904Sdim } 458212904Sdim } 459261991Sdim 460212904Sdim // Analyze the base pointer next. 461212904Sdim V = GEPOp->getOperand(0); 462212904Sdim } while (--MaxLookup); 463261991Sdim 464212904Sdim // If the chain of expressions is too deep, just return early. 465276479Sdim MaxLookupReached = true; 466296417Sdim SearchLimitReached++; 467212904Sdim return V; 468212904Sdim} 469212904Sdim 470296417Sdim/// Returns whether the given pointer value points to memory that is local to 471296417Sdim/// the function, with global constants being considered local to all 472296417Sdim/// functions. 473296417Sdimbool BasicAAResult::pointsToConstantMemory(const MemoryLocation &Loc, 474296417Sdim bool OrLocal) { 475218893Sdim assert(Visited.empty() && "Visited must be cleared after use!"); 476193323Sed 477218893Sdim unsigned MaxLookup = 8; 478218893Sdim SmallVector<const Value *, 16> Worklist; 479218893Sdim Worklist.push_back(Loc.Ptr); 480218893Sdim do { 481296417Sdim const Value *V = GetUnderlyingObject(Worklist.pop_back_val(), DL); 482280031Sdim if (!Visited.insert(V).second) { 483218893Sdim Visited.clear(); 484296417Sdim return AAResultBase::pointsToConstantMemory(Loc, OrLocal); 485218893Sdim } 486212904Sdim 487218893Sdim // An alloca instruction defines local memory. 488218893Sdim if (OrLocal && isa<AllocaInst>(V)) 489218893Sdim continue; 490218893Sdim 491218893Sdim // A global constant counts as local memory for our purposes. 492218893Sdim if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) { 493218893Sdim // Note: this doesn't require GV to be "ODR" because it isn't legal for a 494218893Sdim // global to be marked constant in some modules and non-constant in 495218893Sdim // others. GV may even be a declaration, not a definition. 496218893Sdim if (!GV->isConstant()) { 497218893Sdim Visited.clear(); 498296417Sdim return AAResultBase::pointsToConstantMemory(Loc, OrLocal); 499218893Sdim } 500218893Sdim continue; 501218893Sdim } 502218893Sdim 503218893Sdim // If both select values point to local memory, then so does the select. 504218893Sdim if (const SelectInst *SI = dyn_cast<SelectInst>(V)) { 505218893Sdim Worklist.push_back(SI->getTrueValue()); 506218893Sdim Worklist.push_back(SI->getFalseValue()); 507218893Sdim continue; 508218893Sdim } 509218893Sdim 510218893Sdim // If all values incoming to a phi node point to local memory, then so does 511218893Sdim // the phi. 512218893Sdim if (const PHINode *PN = dyn_cast<PHINode>(V)) { 513218893Sdim // Don't bother inspecting phi nodes with many operands. 514218893Sdim if (PN->getNumIncomingValues() > MaxLookup) { 515218893Sdim Visited.clear(); 516296417Sdim return AAResultBase::pointsToConstantMemory(Loc, OrLocal); 517218893Sdim } 518288943Sdim for (Value *IncValue : PN->incoming_values()) 519288943Sdim Worklist.push_back(IncValue); 520218893Sdim continue; 521218893Sdim } 522218893Sdim 523218893Sdim // Otherwise be conservative. 524218893Sdim Visited.clear(); 525296417Sdim return AAResultBase::pointsToConstantMemory(Loc, OrLocal); 526218893Sdim 527218893Sdim } while (!Worklist.empty() && --MaxLookup); 528218893Sdim 529218893Sdim Visited.clear(); 530218893Sdim return Worklist.empty(); 531193323Sed} 532193323Sed 533288943Sdim// FIXME: This code is duplicated with MemoryLocation and should be hoisted to 534288943Sdim// some common utility location. 535276479Sdimstatic bool isMemsetPattern16(const Function *MS, 536276479Sdim const TargetLibraryInfo &TLI) { 537276479Sdim if (TLI.has(LibFunc::memset_pattern16) && 538276479Sdim MS->getName() == "memset_pattern16") { 539276479Sdim FunctionType *MemsetType = MS->getFunctionType(); 540276479Sdim if (!MemsetType->isVarArg() && MemsetType->getNumParams() == 3 && 541276479Sdim isa<PointerType>(MemsetType->getParamType(0)) && 542276479Sdim isa<PointerType>(MemsetType->getParamType(1)) && 543276479Sdim isa<IntegerType>(MemsetType->getParamType(2))) 544276479Sdim return true; 545276479Sdim } 546276479Sdim return false; 547276479Sdim} 548276479Sdim 549296417Sdim/// Returns the behavior when calling the given call site. 550296417SdimFunctionModRefBehavior BasicAAResult::getModRefBehavior(ImmutableCallSite CS) { 551212904Sdim if (CS.doesNotAccessMemory()) 552212904Sdim // Can't do better than this. 553296417Sdim return FMRB_DoesNotAccessMemory; 554193323Sed 555296417Sdim FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior; 556212904Sdim 557212904Sdim // If the callsite knows it only reads memory, don't return worse 558212904Sdim // than that. 559212904Sdim if (CS.onlyReadsMemory()) 560296417Sdim Min = FMRB_OnlyReadsMemory; 561212904Sdim 562288943Sdim if (CS.onlyAccessesArgMemory()) 563296417Sdim Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesArgumentPointees); 564288943Sdim 565296417Sdim // The AAResultBase base class has some smarts, lets use them. 566296417Sdim return FunctionModRefBehavior(AAResultBase::getModRefBehavior(CS) & Min); 567212904Sdim} 568212904Sdim 569296417Sdim/// Returns the behavior when calling the given function. For use when the call 570296417Sdim/// site is not known. 571296417SdimFunctionModRefBehavior BasicAAResult::getModRefBehavior(const Function *F) { 572218893Sdim // If the function declares it doesn't access memory, we can't do better. 573212904Sdim if (F->doesNotAccessMemory()) 574296417Sdim return FMRB_DoesNotAccessMemory; 575218893Sdim 576296417Sdim FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior; 577218893Sdim 578218893Sdim // If the function declares it only reads memory, go with that. 579212904Sdim if (F->onlyReadsMemory()) 580296417Sdim Min = FMRB_OnlyReadsMemory; 581212904Sdim 582288943Sdim if (F->onlyAccessesArgMemory()) 583296417Sdim Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesArgumentPointees); 584288943Sdim 585218893Sdim // Otherwise be conservative. 586296417Sdim return FunctionModRefBehavior(AAResultBase::getModRefBehavior(F) & Min); 587212904Sdim} 588212904Sdim 589296417Sdim/// Returns true if this is a writeonly (i.e Mod only) parameter. Currently, 590296417Sdim/// we don't have a writeonly attribute, so this only knows about builtin 591296417Sdim/// intrinsics and target library functions. We could consider adding a 592296417Sdim/// writeonly attribute in the future and moving all of these facts to either 593296417Sdim/// Intrinsics.td or InferFunctionAttr.cpp 594296417Sdimstatic bool isWriteOnlyParam(ImmutableCallSite CS, unsigned ArgIdx, 595296417Sdim const TargetLibraryInfo &TLI) { 596288943Sdim if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) 597276479Sdim switch (II->getIntrinsicID()) { 598288943Sdim default: 599288943Sdim break; 600276479Sdim case Intrinsic::memset: 601276479Sdim case Intrinsic::memcpy: 602288943Sdim case Intrinsic::memmove: 603296417Sdim // We don't currently have a writeonly attribute. All other properties 604296417Sdim // of these intrinsics are nicely described via attributes in 605296417Sdim // Intrinsics.td and handled generically. 606296417Sdim if (ArgIdx == 0) 607296417Sdim return true; 608276479Sdim } 609276479Sdim 610276479Sdim // We can bound the aliasing properties of memset_pattern16 just as we can 611276479Sdim // for memcpy/memset. This is particularly important because the 612276479Sdim // LoopIdiomRecognizer likes to turn loops into calls to memset_pattern16 613296417Sdim // whenever possible. Note that all but the missing writeonly attribute are 614296417Sdim // handled via InferFunctionAttr. 615296417Sdim if (CS.getCalledFunction() && isMemsetPattern16(CS.getCalledFunction(), TLI)) 616296417Sdim if (ArgIdx == 0) 617296417Sdim return true; 618276479Sdim 619296417Sdim // TODO: memset_pattern4, memset_pattern8 620296417Sdim // TODO: _chk variants 621296417Sdim // TODO: strcmp, strcpy 622296417Sdim 623296417Sdim return false; 624276479Sdim} 625276479Sdim 626296417SdimModRefInfo BasicAAResult::getArgModRefInfo(ImmutableCallSite CS, 627296417Sdim unsigned ArgIdx) { 628296417Sdim 629296417Sdim // Emulate the missing writeonly attribute by checking for known builtin 630296417Sdim // intrinsics and target library functions. 631296417Sdim if (isWriteOnlyParam(CS, ArgIdx, TLI)) 632296417Sdim return MRI_Mod; 633296417Sdim 634296417Sdim if (CS.paramHasAttr(ArgIdx + 1, Attribute::ReadOnly)) 635296417Sdim return MRI_Ref; 636296417Sdim 637296417Sdim if (CS.paramHasAttr(ArgIdx + 1, Attribute::ReadNone)) 638296417Sdim return MRI_NoModRef; 639296417Sdim 640296417Sdim return AAResultBase::getArgModRefInfo(CS, ArgIdx); 641296417Sdim} 642296417Sdim 643280031Sdimstatic bool isAssumeIntrinsic(ImmutableCallSite CS) { 644280031Sdim const IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction()); 645296417Sdim return II && II->getIntrinsicID() == Intrinsic::assume; 646296417Sdim} 647280031Sdim 648296417Sdim#ifndef NDEBUG 649296417Sdimstatic const Function *getParent(const Value *V) { 650296417Sdim if (const Instruction *inst = dyn_cast<Instruction>(V)) 651296417Sdim return inst->getParent()->getParent(); 652296417Sdim 653296417Sdim if (const Argument *arg = dyn_cast<Argument>(V)) 654296417Sdim return arg->getParent(); 655296417Sdim 656296417Sdim return nullptr; 657280031Sdim} 658280031Sdim 659296417Sdimstatic bool notDifferentParent(const Value *O1, const Value *O2) { 660296417Sdim 661296417Sdim const Function *F1 = getParent(O1); 662296417Sdim const Function *F2 = getParent(O2); 663296417Sdim 664296417Sdim return !F1 || !F2 || F1 == F2; 665288943Sdim} 666296417Sdim#endif 667288943Sdim 668296417SdimAliasResult BasicAAResult::alias(const MemoryLocation &LocA, 669296417Sdim const MemoryLocation &LocB) { 670296417Sdim assert(notDifferentParent(LocA.Ptr, LocB.Ptr) && 671296417Sdim "BasicAliasAnalysis doesn't support interprocedural queries."); 672296417Sdim 673296417Sdim // If we have a directly cached entry for these locations, we have recursed 674296417Sdim // through this once, so just return the cached results. Notably, when this 675296417Sdim // happens, we don't clear the cache. 676296417Sdim auto CacheIt = AliasCache.find(LocPair(LocA, LocB)); 677296417Sdim if (CacheIt != AliasCache.end()) 678296417Sdim return CacheIt->second; 679296417Sdim 680296417Sdim AliasResult Alias = aliasCheck(LocA.Ptr, LocA.Size, LocA.AATags, LocB.Ptr, 681296417Sdim LocB.Size, LocB.AATags); 682296417Sdim // AliasCache rarely has more than 1 or 2 elements, always use 683296417Sdim // shrink_and_clear so it quickly returns to the inline capacity of the 684296417Sdim // SmallDenseMap if it ever grows larger. 685296417Sdim // FIXME: This should really be shrink_to_inline_capacity_and_clear(). 686296417Sdim AliasCache.shrink_and_clear(); 687296417Sdim VisitedPhiBBs.clear(); 688296417Sdim return Alias; 689296417Sdim} 690296417Sdim 691296417Sdim/// Checks to see if the specified callsite can clobber the specified memory 692296417Sdim/// object. 693296417Sdim/// 694296417Sdim/// Since we only look at local properties of this function, we really can't 695296417Sdim/// say much about this query. We do, however, use simple "address taken" 696296417Sdim/// analysis on local objects. 697296417SdimModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS, 698296417Sdim const MemoryLocation &Loc) { 699218893Sdim assert(notDifferentParent(CS.getInstruction(), Loc.Ptr) && 700210299Sed "AliasAnalysis query involving multiple functions!"); 701210299Sed 702296417Sdim const Value *Object = GetUnderlyingObject(Loc.Ptr, DL); 703261991Sdim 704218893Sdim // If this is a tail call and Loc.Ptr points to a stack location, we know that 705199989Srdivacky // the tail call cannot access or modify the local stack. 706199989Srdivacky // We cannot exclude byval arguments here; these belong to the caller of 707199989Srdivacky // the current function not to the current function, and a tail callee 708199989Srdivacky // may reference them. 709199989Srdivacky if (isa<AllocaInst>(Object)) 710212904Sdim if (const CallInst *CI = dyn_cast<CallInst>(CS.getInstruction())) 711199989Srdivacky if (CI->isTailCall()) 712296417Sdim return MRI_NoModRef; 713261991Sdim 714199989Srdivacky // If the pointer is to a locally allocated object that does not escape, 715199989Srdivacky // then the call can not mod/ref the pointer unless the call takes the pointer 716199989Srdivacky // as an argument, and itself doesn't capture it. 717199989Srdivacky if (!isa<Constant>(Object) && CS.getInstruction() != Object && 718199989Srdivacky isNonEscapingLocalObject(Object)) { 719199989Srdivacky bool PassedAsArg = false; 720199989Srdivacky unsigned ArgNo = 0; 721212904Sdim for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 722199989Srdivacky CI != CE; ++CI, ++ArgNo) { 723223017Sdim // Only look at the no-capture or byval pointer arguments. If this 724223017Sdim // pointer were passed to arguments that were neither of these, then it 725223017Sdim // couldn't be no-capture. 726204642Srdivacky if (!(*CI)->getType()->isPointerTy() || 727234353Sdim (!CS.doesNotCapture(ArgNo) && !CS.isByValArgument(ArgNo))) 728199989Srdivacky continue; 729261991Sdim 730218893Sdim // If this is a no-capture pointer argument, see if we can tell that it 731199989Srdivacky // is impossible to alias the pointer we're checking. If not, we have to 732199989Srdivacky // assume that the call could touch the pointer, even though it doesn't 733199989Srdivacky // escape. 734296417Sdim AliasResult AR = 735296417Sdim getBestAAResults().alias(MemoryLocation(*CI), MemoryLocation(Object)); 736296417Sdim if (AR) { 737199989Srdivacky PassedAsArg = true; 738198113Srdivacky break; 739198090Srdivacky } 740198090Srdivacky } 741261991Sdim 742199989Srdivacky if (!PassedAsArg) 743296417Sdim return MRI_NoModRef; 744193323Sed } 745193323Sed 746280031Sdim // While the assume intrinsic is marked as arbitrarily writing so that 747280031Sdim // proper control dependencies will be maintained, it never aliases any 748280031Sdim // particular memory location. 749280031Sdim if (isAssumeIntrinsic(CS)) 750296417Sdim return MRI_NoModRef; 751280031Sdim 752296417Sdim // The AAResultBase base class has some smarts, lets use them. 753296417Sdim return AAResultBase::getModRefInfo(CS, Loc); 754193323Sed} 755193323Sed 756296417SdimModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS1, 757296417Sdim ImmutableCallSite CS2) { 758280031Sdim // While the assume intrinsic is marked as arbitrarily writing so that 759280031Sdim // proper control dependencies will be maintained, it never aliases any 760280031Sdim // particular memory location. 761280031Sdim if (isAssumeIntrinsic(CS1) || isAssumeIntrinsic(CS2)) 762296417Sdim return MRI_NoModRef; 763280031Sdim 764296417Sdim // The AAResultBase base class has some smarts, lets use them. 765296417Sdim return AAResultBase::getModRefInfo(CS1, CS2); 766280031Sdim} 767280031Sdim 768296417Sdim/// Provide ad-hoc rules to disambiguate accesses through two GEP operators, 769296417Sdim/// both having the exact same pointer operand. 770288943Sdimstatic AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1, 771288943Sdim uint64_t V1Size, 772288943Sdim const GEPOperator *GEP2, 773288943Sdim uint64_t V2Size, 774288943Sdim const DataLayout &DL) { 775288943Sdim 776288943Sdim assert(GEP1->getPointerOperand() == GEP2->getPointerOperand() && 777288943Sdim "Expected GEPs with the same pointer operand"); 778288943Sdim 779288943Sdim // Try to determine whether GEP1 and GEP2 index through arrays, into structs, 780288943Sdim // such that the struct field accesses provably cannot alias. 781288943Sdim // We also need at least two indices (the pointer, and the struct field). 782288943Sdim if (GEP1->getNumIndices() != GEP2->getNumIndices() || 783288943Sdim GEP1->getNumIndices() < 2) 784288943Sdim return MayAlias; 785288943Sdim 786288943Sdim // If we don't know the size of the accesses through both GEPs, we can't 787288943Sdim // determine whether the struct fields accessed can't alias. 788288943Sdim if (V1Size == MemoryLocation::UnknownSize || 789288943Sdim V2Size == MemoryLocation::UnknownSize) 790288943Sdim return MayAlias; 791288943Sdim 792288943Sdim ConstantInt *C1 = 793288943Sdim dyn_cast<ConstantInt>(GEP1->getOperand(GEP1->getNumOperands() - 1)); 794288943Sdim ConstantInt *C2 = 795288943Sdim dyn_cast<ConstantInt>(GEP2->getOperand(GEP2->getNumOperands() - 1)); 796288943Sdim 797296417Sdim // If the last (struct) indices are constants and are equal, the other indices 798296417Sdim // might be also be dynamically equal, so the GEPs can alias. 799296417Sdim if (C1 && C2 && C1 == C2) 800288943Sdim return MayAlias; 801288943Sdim 802288943Sdim // Find the last-indexed type of the GEP, i.e., the type you'd get if 803288943Sdim // you stripped the last index. 804288943Sdim // On the way, look at each indexed type. If there's something other 805288943Sdim // than an array, different indices can lead to different final types. 806288943Sdim SmallVector<Value *, 8> IntermediateIndices; 807288943Sdim 808288943Sdim // Insert the first index; we don't need to check the type indexed 809288943Sdim // through it as it only drops the pointer indirection. 810288943Sdim assert(GEP1->getNumIndices() > 1 && "Not enough GEP indices to examine"); 811288943Sdim IntermediateIndices.push_back(GEP1->getOperand(1)); 812288943Sdim 813288943Sdim // Insert all the remaining indices but the last one. 814288943Sdim // Also, check that they all index through arrays. 815288943Sdim for (unsigned i = 1, e = GEP1->getNumIndices() - 1; i != e; ++i) { 816288943Sdim if (!isa<ArrayType>(GetElementPtrInst::getIndexedType( 817288943Sdim GEP1->getSourceElementType(), IntermediateIndices))) 818288943Sdim return MayAlias; 819288943Sdim IntermediateIndices.push_back(GEP1->getOperand(i + 1)); 820288943Sdim } 821288943Sdim 822296417Sdim auto *Ty = GetElementPtrInst::getIndexedType( 823296417Sdim GEP1->getSourceElementType(), IntermediateIndices); 824296417Sdim StructType *LastIndexedStruct = dyn_cast<StructType>(Ty); 825288943Sdim 826296417Sdim if (isa<SequentialType>(Ty)) { 827296417Sdim // We know that: 828296417Sdim // - both GEPs begin indexing from the exact same pointer; 829296417Sdim // - the last indices in both GEPs are constants, indexing into a sequential 830296417Sdim // type (array or pointer); 831296417Sdim // - both GEPs only index through arrays prior to that. 832296417Sdim // 833296417Sdim // Because array indices greater than the number of elements are valid in 834296417Sdim // GEPs, unless we know the intermediate indices are identical between 835296417Sdim // GEP1 and GEP2 we cannot guarantee that the last indexed arrays don't 836296417Sdim // partially overlap. We also need to check that the loaded size matches 837296417Sdim // the element size, otherwise we could still have overlap. 838296417Sdim const uint64_t ElementSize = 839296417Sdim DL.getTypeStoreSize(cast<SequentialType>(Ty)->getElementType()); 840296417Sdim if (V1Size != ElementSize || V2Size != ElementSize) 841296417Sdim return MayAlias; 842296417Sdim 843296417Sdim for (unsigned i = 0, e = GEP1->getNumIndices() - 1; i != e; ++i) 844296417Sdim if (GEP1->getOperand(i + 1) != GEP2->getOperand(i + 1)) 845296417Sdim return MayAlias; 846296417Sdim 847296417Sdim // Now we know that the array/pointer that GEP1 indexes into and that 848296417Sdim // that GEP2 indexes into must either precisely overlap or be disjoint. 849296417Sdim // Because they cannot partially overlap and because fields in an array 850296417Sdim // cannot overlap, if we can prove the final indices are different between 851296417Sdim // GEP1 and GEP2, we can conclude GEP1 and GEP2 don't alias. 852296417Sdim 853296417Sdim // If the last indices are constants, we've already checked they don't 854296417Sdim // equal each other so we can exit early. 855296417Sdim if (C1 && C2) 856296417Sdim return NoAlias; 857296417Sdim if (isKnownNonEqual(GEP1->getOperand(GEP1->getNumOperands() - 1), 858296417Sdim GEP2->getOperand(GEP2->getNumOperands() - 1), 859296417Sdim DL)) 860296417Sdim return NoAlias; 861288943Sdim return MayAlias; 862296417Sdim } else if (!LastIndexedStruct || !C1 || !C2) { 863296417Sdim return MayAlias; 864296417Sdim } 865288943Sdim 866288943Sdim // We know that: 867288943Sdim // - both GEPs begin indexing from the exact same pointer; 868288943Sdim // - the last indices in both GEPs are constants, indexing into a struct; 869288943Sdim // - said indices are different, hence, the pointed-to fields are different; 870288943Sdim // - both GEPs only index through arrays prior to that. 871288943Sdim // 872288943Sdim // This lets us determine that the struct that GEP1 indexes into and the 873288943Sdim // struct that GEP2 indexes into must either precisely overlap or be 874288943Sdim // completely disjoint. Because they cannot partially overlap, indexing into 875288943Sdim // different non-overlapping fields of the struct will never alias. 876288943Sdim 877288943Sdim // Therefore, the only remaining thing needed to show that both GEPs can't 878288943Sdim // alias is that the fields are not overlapping. 879288943Sdim const StructLayout *SL = DL.getStructLayout(LastIndexedStruct); 880288943Sdim const uint64_t StructSize = SL->getSizeInBytes(); 881288943Sdim const uint64_t V1Off = SL->getElementOffset(C1->getZExtValue()); 882288943Sdim const uint64_t V2Off = SL->getElementOffset(C2->getZExtValue()); 883288943Sdim 884288943Sdim auto EltsDontOverlap = [StructSize](uint64_t V1Off, uint64_t V1Size, 885288943Sdim uint64_t V2Off, uint64_t V2Size) { 886288943Sdim return V1Off < V2Off && V1Off + V1Size <= V2Off && 887288943Sdim ((V2Off + V2Size <= StructSize) || 888288943Sdim (V2Off + V2Size - StructSize <= V1Off)); 889288943Sdim }; 890288943Sdim 891288943Sdim if (EltsDontOverlap(V1Off, V1Size, V2Off, V2Size) || 892288943Sdim EltsDontOverlap(V2Off, V2Size, V1Off, V1Size)) 893288943Sdim return NoAlias; 894288943Sdim 895288943Sdim return MayAlias; 896288943Sdim} 897288943Sdim 898296417Sdim/// Provides a bunch of ad-hoc rules to disambiguate a GEP instruction against 899296417Sdim/// another pointer. 900199989Srdivacky/// 901296417Sdim/// We know that V1 is a GEP, but we don't know anything about V2. 902296417Sdim/// UnderlyingV1 is GetUnderlyingObject(GEP1, DL), UnderlyingV2 is the same for 903296417Sdim/// V2. 904296417SdimAliasResult BasicAAResult::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size, 905296417Sdim const AAMDNodes &V1AAInfo, const Value *V2, 906296417Sdim uint64_t V2Size, const AAMDNodes &V2AAInfo, 907296417Sdim const Value *UnderlyingV1, 908296417Sdim const Value *UnderlyingV2) { 909199989Srdivacky int64_t GEP1BaseOffset; 910276479Sdim bool GEP1MaxLookupReached; 911212904Sdim SmallVector<VariableGEPIndex, 4> GEP1VariableIndices; 912199989Srdivacky 913243830Sdim // If we have two gep instructions with must-alias or not-alias'ing base 914243830Sdim // pointers, figure out if the indexes to the GEP tell us anything about the 915243830Sdim // derived pointer. 916199989Srdivacky if (const GEPOperator *GEP2 = dyn_cast<GEPOperator>(V2)) { 917249423Sdim // Do the base pointers alias? 918288943Sdim AliasResult BaseAlias = 919288943Sdim aliasCheck(UnderlyingV1, MemoryLocation::UnknownSize, AAMDNodes(), 920288943Sdim UnderlyingV2, MemoryLocation::UnknownSize, AAMDNodes()); 921249423Sdim 922243830Sdim // Check for geps of non-aliasing underlying pointers where the offsets are 923243830Sdim // identical. 924249423Sdim if ((BaseAlias == MayAlias) && V1Size == V2Size) { 925243830Sdim // Do the base pointers alias assuming type and size. 926296417Sdim AliasResult PreciseBaseAlias = aliasCheck(UnderlyingV1, V1Size, V1AAInfo, 927296417Sdim UnderlyingV2, V2Size, V2AAInfo); 928243830Sdim if (PreciseBaseAlias == NoAlias) { 929243830Sdim // See if the computed offset from the common pointer tells us about the 930243830Sdim // relation of the resulting pointer. 931243830Sdim int64_t GEP2BaseOffset; 932276479Sdim bool GEP2MaxLookupReached; 933243830Sdim SmallVector<VariableGEPIndex, 4> GEP2VariableIndices; 934243830Sdim const Value *GEP2BasePtr = 935280031Sdim DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, 936296417Sdim GEP2MaxLookupReached, DL, &AC, DT); 937243830Sdim const Value *GEP1BasePtr = 938280031Sdim DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, 939296417Sdim GEP1MaxLookupReached, DL, &AC, DT); 940243830Sdim // DecomposeGEPExpression and GetUnderlyingObject should return the 941243830Sdim // same result except when DecomposeGEPExpression has no DataLayout. 942296417Sdim // FIXME: They always have a DataLayout so this should become an 943296417Sdim // assert. 944243830Sdim if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) { 945243830Sdim return MayAlias; 946243830Sdim } 947276479Sdim // If the max search depth is reached the result is undefined 948276479Sdim if (GEP2MaxLookupReached || GEP1MaxLookupReached) 949276479Sdim return MayAlias; 950276479Sdim 951243830Sdim // Same offsets. 952243830Sdim if (GEP1BaseOffset == GEP2BaseOffset && 953276479Sdim GEP1VariableIndices == GEP2VariableIndices) 954243830Sdim return NoAlias; 955243830Sdim GEP1VariableIndices.clear(); 956243830Sdim } 957243830Sdim } 958261991Sdim 959199989Srdivacky // If we get a No or May, then return it immediately, no amount of analysis 960199989Srdivacky // will improve this situation. 961296417Sdim if (BaseAlias != MustAlias) 962296417Sdim return BaseAlias; 963261991Sdim 964199989Srdivacky // Otherwise, we have a MustAlias. Since the base pointers alias each other 965199989Srdivacky // exactly, see if the computed offset from the common pointer tells us 966199989Srdivacky // about the relation of the resulting pointer. 967199989Srdivacky const Value *GEP1BasePtr = 968280031Sdim DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, 969296417Sdim GEP1MaxLookupReached, DL, &AC, DT); 970261991Sdim 971199989Srdivacky int64_t GEP2BaseOffset; 972276479Sdim bool GEP2MaxLookupReached; 973212904Sdim SmallVector<VariableGEPIndex, 4> GEP2VariableIndices; 974199989Srdivacky const Value *GEP2BasePtr = 975280031Sdim DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, 976296417Sdim GEP2MaxLookupReached, DL, &AC, DT); 977261991Sdim 978243830Sdim // DecomposeGEPExpression and GetUnderlyingObject should return the 979243830Sdim // same result except when DecomposeGEPExpression has no DataLayout. 980296417Sdim // FIXME: They always have a DataLayout so this should become an assert. 981199989Srdivacky if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) { 982199989Srdivacky return MayAlias; 983199989Srdivacky } 984288943Sdim 985288943Sdim // If we know the two GEPs are based off of the exact same pointer (and not 986288943Sdim // just the same underlying object), see if that tells us anything about 987288943Sdim // the resulting pointers. 988296417Sdim if (GEP1->getPointerOperand() == GEP2->getPointerOperand()) { 989296417Sdim AliasResult R = aliasSameBasePointerGEPs(GEP1, V1Size, GEP2, V2Size, DL); 990288943Sdim // If we couldn't find anything interesting, don't abandon just yet. 991288943Sdim if (R != MayAlias) 992288943Sdim return R; 993288943Sdim } 994288943Sdim 995276479Sdim // If the max search depth is reached the result is undefined 996276479Sdim if (GEP2MaxLookupReached || GEP1MaxLookupReached) 997276479Sdim return MayAlias; 998261991Sdim 999199989Srdivacky // Subtract the GEP2 pointer from the GEP1 pointer to find out their 1000199989Srdivacky // symbolic difference. 1001199989Srdivacky GEP1BaseOffset -= GEP2BaseOffset; 1002212904Sdim GetIndexDifference(GEP1VariableIndices, GEP2VariableIndices); 1003261991Sdim 1004199989Srdivacky } else { 1005199989Srdivacky // Check to see if these two pointers are related by the getelementptr 1006199989Srdivacky // instruction. If one pointer is a GEP with a non-zero index of the other 1007199989Srdivacky // pointer, we know they cannot alias. 1008193323Sed 1009199989Srdivacky // If both accesses are unknown size, we can't do anything useful here. 1010288943Sdim if (V1Size == MemoryLocation::UnknownSize && 1011288943Sdim V2Size == MemoryLocation::UnknownSize) 1012199989Srdivacky return MayAlias; 1013193323Sed 1014288943Sdim AliasResult R = aliasCheck(UnderlyingV1, MemoryLocation::UnknownSize, 1015288943Sdim AAMDNodes(), V2, V2Size, V2AAInfo); 1016199989Srdivacky if (R != MustAlias) 1017199989Srdivacky // If V2 may alias GEP base pointer, conservatively returns MayAlias. 1018199989Srdivacky // If V2 is known not to alias GEP base pointer, then the two values 1019199989Srdivacky // cannot alias per GEP semantics: "A pointer value formed from a 1020199989Srdivacky // getelementptr instruction is associated with the addresses associated 1021199989Srdivacky // with the first operand of the getelementptr". 1022199989Srdivacky return R; 1023193323Sed 1024199989Srdivacky const Value *GEP1BasePtr = 1025280031Sdim DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, 1026296417Sdim GEP1MaxLookupReached, DL, &AC, DT); 1027261991Sdim 1028243830Sdim // DecomposeGEPExpression and GetUnderlyingObject should return the 1029243830Sdim // same result except when DecomposeGEPExpression has no DataLayout. 1030296417Sdim // FIXME: They always have a DataLayout so this should become an assert. 1031199989Srdivacky if (GEP1BasePtr != UnderlyingV1) { 1032199989Srdivacky return MayAlias; 1033193323Sed } 1034276479Sdim // If the max search depth is reached the result is undefined 1035276479Sdim if (GEP1MaxLookupReached) 1036276479Sdim return MayAlias; 1037193323Sed } 1038261991Sdim 1039199989Srdivacky // In the two GEP Case, if there is no difference in the offsets of the 1040199989Srdivacky // computed pointers, the resultant pointers are a must alias. This 1041199989Srdivacky // hapens when we have two lexically identical GEP's (for example). 1042193323Sed // 1043199989Srdivacky // In the other case, if we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 1044199989Srdivacky // must aliases the GEP, the end result is a must alias also. 1045199989Srdivacky if (GEP1BaseOffset == 0 && GEP1VariableIndices.empty()) 1046198090Srdivacky return MustAlias; 1047193323Sed 1048226633Sdim // If there is a constant difference between the pointers, but the difference 1049226633Sdim // is less than the size of the associated memory object, then we know 1050226633Sdim // that the objects are partially overlapping. If the difference is 1051226633Sdim // greater, we know they do not overlap. 1052218893Sdim if (GEP1BaseOffset != 0 && GEP1VariableIndices.empty()) { 1053226633Sdim if (GEP1BaseOffset >= 0) { 1054288943Sdim if (V2Size != MemoryLocation::UnknownSize) { 1055226633Sdim if ((uint64_t)GEP1BaseOffset < V2Size) 1056226633Sdim return PartialAlias; 1057226633Sdim return NoAlias; 1058226633Sdim } 1059226633Sdim } else { 1060265925Sdim // We have the situation where: 1061265925Sdim // + + 1062265925Sdim // | BaseOffset | 1063265925Sdim // ---------------->| 1064265925Sdim // |-->V1Size |-------> V2Size 1065265925Sdim // GEP1 V2 1066265925Sdim // We need to know that V2Size is not unknown, otherwise we might have 1067265925Sdim // stripped a gep with negative index ('gep <ptr>, -1, ...). 1068288943Sdim if (V1Size != MemoryLocation::UnknownSize && 1069288943Sdim V2Size != MemoryLocation::UnknownSize) { 1070226633Sdim if (-(uint64_t)GEP1BaseOffset < V1Size) 1071226633Sdim return PartialAlias; 1072226633Sdim return NoAlias; 1073226633Sdim } 1074226633Sdim } 1075218893Sdim } 1076218893Sdim 1077226633Sdim if (!GEP1VariableIndices.empty()) { 1078226633Sdim uint64_t Modulo = 0; 1079296417Sdim bool AllPositive = true; 1080296417Sdim for (unsigned i = 0, e = GEP1VariableIndices.size(); i != e; ++i) { 1081296417Sdim 1082296417Sdim // Try to distinguish something like &A[i][1] against &A[42][0]. 1083296417Sdim // Grab the least significant bit set in any of the scales. We 1084296417Sdim // don't need std::abs here (even if the scale's negative) as we'll 1085296417Sdim // be ^'ing Modulo with itself later. 1086296417Sdim Modulo |= (uint64_t)GEP1VariableIndices[i].Scale; 1087296417Sdim 1088296417Sdim if (AllPositive) { 1089296417Sdim // If the Value could change between cycles, then any reasoning about 1090296417Sdim // the Value this cycle may not hold in the next cycle. We'll just 1091296417Sdim // give up if we can't determine conditions that hold for every cycle: 1092296417Sdim const Value *V = GEP1VariableIndices[i].V; 1093296417Sdim 1094296417Sdim bool SignKnownZero, SignKnownOne; 1095296417Sdim ComputeSignBit(const_cast<Value *>(V), SignKnownZero, SignKnownOne, DL, 1096296417Sdim 0, &AC, nullptr, DT); 1097296417Sdim 1098296417Sdim // Zero-extension widens the variable, and so forces the sign 1099296417Sdim // bit to zero. 1100296417Sdim bool IsZExt = GEP1VariableIndices[i].ZExtBits > 0 || isa<ZExtInst>(V); 1101296417Sdim SignKnownZero |= IsZExt; 1102296417Sdim SignKnownOne &= !IsZExt; 1103296417Sdim 1104296417Sdim // If the variable begins with a zero then we know it's 1105296417Sdim // positive, regardless of whether the value is signed or 1106296417Sdim // unsigned. 1107296417Sdim int64_t Scale = GEP1VariableIndices[i].Scale; 1108296417Sdim AllPositive = 1109296417Sdim (SignKnownZero && Scale >= 0) || (SignKnownOne && Scale < 0); 1110296417Sdim } 1111296417Sdim } 1112296417Sdim 1113226633Sdim Modulo = Modulo ^ (Modulo & (Modulo - 1)); 1114226633Sdim 1115226633Sdim // We can compute the difference between the two addresses 1116226633Sdim // mod Modulo. Check whether that difference guarantees that the 1117226633Sdim // two locations do not alias. 1118226633Sdim uint64_t ModOffset = (uint64_t)GEP1BaseOffset & (Modulo - 1); 1119288943Sdim if (V1Size != MemoryLocation::UnknownSize && 1120288943Sdim V2Size != MemoryLocation::UnknownSize && ModOffset >= V2Size && 1121288943Sdim V1Size <= Modulo - ModOffset) 1122198090Srdivacky return NoAlias; 1123296417Sdim 1124296417Sdim // If we know all the variables are positive, then GEP1 >= GEP1BasePtr. 1125296417Sdim // If GEP1BasePtr > V2 (GEP1BaseOffset > 0) then we know the pointers 1126296417Sdim // don't alias if V2Size can fit in the gap between V2 and GEP1BasePtr. 1127296417Sdim if (AllPositive && GEP1BaseOffset > 0 && V2Size <= (uint64_t)GEP1BaseOffset) 1128296417Sdim return NoAlias; 1129296417Sdim 1130296417Sdim if (constantOffsetHeuristic(GEP1VariableIndices, V1Size, V2Size, 1131296417Sdim GEP1BaseOffset, &AC, DT)) 1132296417Sdim return NoAlias; 1133198090Srdivacky } 1134226633Sdim 1135223017Sdim // Statically, we can see that the base objects are the same, but the 1136223017Sdim // pointers have dynamic offsets which we can't resolve. And none of our 1137223017Sdim // little tricks above worked. 1138223017Sdim // 1139223017Sdim // TODO: Returning PartialAlias instead of MayAlias is a mild hack; the 1140223017Sdim // practical effect of this is protecting TBAA in the case of dynamic 1141234353Sdim // indices into arrays of unions or malloc'd memory. 1142223017Sdim return PartialAlias; 1143193323Sed} 1144193323Sed 1145288943Sdimstatic AliasResult MergeAliasResults(AliasResult A, AliasResult B) { 1146223017Sdim // If the results agree, take it. 1147223017Sdim if (A == B) 1148223017Sdim return A; 1149223017Sdim // A mix of PartialAlias and MustAlias is PartialAlias. 1150288943Sdim if ((A == PartialAlias && B == MustAlias) || 1151288943Sdim (B == PartialAlias && A == MustAlias)) 1152288943Sdim return PartialAlias; 1153223017Sdim // Otherwise, we don't know anything. 1154288943Sdim return MayAlias; 1155223017Sdim} 1156223017Sdim 1157296417Sdim/// Provides a bunch of ad-hoc rules to disambiguate a Select instruction 1158296417Sdim/// against another. 1159296417SdimAliasResult BasicAAResult::aliasSelect(const SelectInst *SI, uint64_t SISize, 1160296417Sdim const AAMDNodes &SIAAInfo, 1161296417Sdim const Value *V2, uint64_t V2Size, 1162296417Sdim const AAMDNodes &V2AAInfo) { 1163198892Srdivacky // If the values are Selects with the same condition, we can do a more precise 1164198892Srdivacky // check: just check for aliases between the values on corresponding arms. 1165198892Srdivacky if (const SelectInst *SI2 = dyn_cast<SelectInst>(V2)) 1166198892Srdivacky if (SI->getCondition() == SI2->getCondition()) { 1167296417Sdim AliasResult Alias = aliasCheck(SI->getTrueValue(), SISize, SIAAInfo, 1168296417Sdim SI2->getTrueValue(), V2Size, V2AAInfo); 1169198892Srdivacky if (Alias == MayAlias) 1170198892Srdivacky return MayAlias; 1171198892Srdivacky AliasResult ThisAlias = 1172296417Sdim aliasCheck(SI->getFalseValue(), SISize, SIAAInfo, 1173296417Sdim SI2->getFalseValue(), V2Size, V2AAInfo); 1174223017Sdim return MergeAliasResults(ThisAlias, Alias); 1175198892Srdivacky } 1176198892Srdivacky 1177198892Srdivacky // If both arms of the Select node NoAlias or MustAlias V2, then returns 1178198892Srdivacky // NoAlias / MustAlias. Otherwise, returns MayAlias. 1179198892Srdivacky AliasResult Alias = 1180296417Sdim aliasCheck(V2, V2Size, V2AAInfo, SI->getTrueValue(), SISize, SIAAInfo); 1181198892Srdivacky if (Alias == MayAlias) 1182198892Srdivacky return MayAlias; 1183210299Sed 1184198892Srdivacky AliasResult ThisAlias = 1185296417Sdim aliasCheck(V2, V2Size, V2AAInfo, SI->getFalseValue(), SISize, SIAAInfo); 1186223017Sdim return MergeAliasResults(ThisAlias, Alias); 1187198892Srdivacky} 1188198892Srdivacky 1189296417Sdim/// Provide a bunch of ad-hoc rules to disambiguate a PHI instruction against 1190296417Sdim/// another. 1191296417SdimAliasResult BasicAAResult::aliasPHI(const PHINode *PN, uint64_t PNSize, 1192296417Sdim const AAMDNodes &PNAAInfo, const Value *V2, 1193296417Sdim uint64_t V2Size, 1194296417Sdim const AAMDNodes &V2AAInfo) { 1195265925Sdim // Track phi nodes we have visited. We use this information when we determine 1196265925Sdim // value equivalence. 1197265925Sdim VisitedPhiBBs.insert(PN->getParent()); 1198265925Sdim 1199198892Srdivacky // If the values are PHIs in the same block, we can do a more precise 1200198892Srdivacky // as well as efficient check: just check for aliases between the values 1201198892Srdivacky // on corresponding edges. 1202198892Srdivacky if (const PHINode *PN2 = dyn_cast<PHINode>(V2)) 1203198892Srdivacky if (PN2->getParent() == PN->getParent()) { 1204288943Sdim LocPair Locs(MemoryLocation(PN, PNSize, PNAAInfo), 1205288943Sdim MemoryLocation(V2, V2Size, V2AAInfo)); 1206243830Sdim if (PN > V2) 1207243830Sdim std::swap(Locs.first, Locs.second); 1208249423Sdim // Analyse the PHIs' inputs under the assumption that the PHIs are 1209249423Sdim // NoAlias. 1210249423Sdim // If the PHIs are May/MustAlias there must be (recursively) an input 1211249423Sdim // operand from outside the PHIs' cycle that is MayAlias/MustAlias or 1212249423Sdim // there must be an operation on the PHIs within the PHIs' value cycle 1213249423Sdim // that causes a MayAlias. 1214249423Sdim // Pretend the phis do not alias. 1215249423Sdim AliasResult Alias = NoAlias; 1216249423Sdim assert(AliasCache.count(Locs) && 1217249423Sdim "There must exist an entry for the phi node"); 1218249423Sdim AliasResult OrigAliasResult = AliasCache[Locs]; 1219249423Sdim AliasCache[Locs] = NoAlias; 1220243830Sdim 1221249423Sdim for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 1222198892Srdivacky AliasResult ThisAlias = 1223296417Sdim aliasCheck(PN->getIncomingValue(i), PNSize, PNAAInfo, 1224296417Sdim PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)), 1225296417Sdim V2Size, V2AAInfo); 1226223017Sdim Alias = MergeAliasResults(ThisAlias, Alias); 1227223017Sdim if (Alias == MayAlias) 1228223017Sdim break; 1229198892Srdivacky } 1230243830Sdim 1231243830Sdim // Reset if speculation failed. 1232249423Sdim if (Alias != NoAlias) 1233243830Sdim AliasCache[Locs] = OrigAliasResult; 1234243830Sdim 1235198892Srdivacky return Alias; 1236198892Srdivacky } 1237198892Srdivacky 1238296417Sdim SmallPtrSet<Value *, 4> UniqueSrc; 1239296417Sdim SmallVector<Value *, 4> V1Srcs; 1240296417Sdim bool isRecursive = false; 1241288943Sdim for (Value *PV1 : PN->incoming_values()) { 1242198090Srdivacky if (isa<PHINode>(PV1)) 1243198090Srdivacky // If any of the source itself is a PHI, return MayAlias conservatively 1244198090Srdivacky // to avoid compile time explosion. The worst possible case is if both 1245198090Srdivacky // sides are PHI nodes. In which case, this is O(m x n) time where 'm' 1246198090Srdivacky // and 'n' are the number of PHI sources. 1247198090Srdivacky return MayAlias; 1248296417Sdim 1249296417Sdim if (EnableRecPhiAnalysis) 1250296417Sdim if (GEPOperator *PV1GEP = dyn_cast<GEPOperator>(PV1)) { 1251296417Sdim // Check whether the incoming value is a GEP that advances the pointer 1252296417Sdim // result of this PHI node (e.g. in a loop). If this is the case, we 1253296417Sdim // would recurse and always get a MayAlias. Handle this case specially 1254296417Sdim // below. 1255296417Sdim if (PV1GEP->getPointerOperand() == PN && PV1GEP->getNumIndices() == 1 && 1256296417Sdim isa<ConstantInt>(PV1GEP->idx_begin())) { 1257296417Sdim isRecursive = true; 1258296417Sdim continue; 1259296417Sdim } 1260296417Sdim } 1261296417Sdim 1262280031Sdim if (UniqueSrc.insert(PV1).second) 1263198090Srdivacky V1Srcs.push_back(PV1); 1264198090Srdivacky } 1265198090Srdivacky 1266296417Sdim // If this PHI node is recursive, set the size of the accessed memory to 1267296417Sdim // unknown to represent all the possible values the GEP could advance the 1268296417Sdim // pointer to. 1269296417Sdim if (isRecursive) 1270296417Sdim PNSize = MemoryLocation::UnknownSize; 1271296417Sdim 1272296417Sdim AliasResult Alias = 1273296417Sdim aliasCheck(V2, V2Size, V2AAInfo, V1Srcs[0], PNSize, PNAAInfo); 1274296417Sdim 1275198090Srdivacky // Early exit if the check of the first PHI source against V2 is MayAlias. 1276198090Srdivacky // Other results are not possible. 1277198090Srdivacky if (Alias == MayAlias) 1278198090Srdivacky return MayAlias; 1279198090Srdivacky 1280198090Srdivacky // If all sources of the PHI node NoAlias or MustAlias V2, then returns 1281198090Srdivacky // NoAlias / MustAlias. Otherwise, returns MayAlias. 1282198090Srdivacky for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) { 1283198090Srdivacky Value *V = V1Srcs[i]; 1284198892Srdivacky 1285296417Sdim AliasResult ThisAlias = 1286296417Sdim aliasCheck(V2, V2Size, V2AAInfo, V, PNSize, PNAAInfo); 1287223017Sdim Alias = MergeAliasResults(ThisAlias, Alias); 1288223017Sdim if (Alias == MayAlias) 1289223017Sdim break; 1290198090Srdivacky } 1291198090Srdivacky 1292198090Srdivacky return Alias; 1293198090Srdivacky} 1294198090Srdivacky 1295296417Sdim/// Provides a bunch of ad-hoc rules to disambiguate in common cases, such as 1296296417Sdim/// array references. 1297296417SdimAliasResult BasicAAResult::aliasCheck(const Value *V1, uint64_t V1Size, 1298296417Sdim AAMDNodes V1AAInfo, const Value *V2, 1299296417Sdim uint64_t V2Size, AAMDNodes V2AAInfo) { 1300207618Srdivacky // If either of the memory references is empty, it doesn't matter what the 1301207618Srdivacky // pointer values are. 1302207618Srdivacky if (V1Size == 0 || V2Size == 0) 1303207618Srdivacky return NoAlias; 1304207618Srdivacky 1305198090Srdivacky // Strip off any casts if they exist. 1306198090Srdivacky V1 = V1->stripPointerCasts(); 1307198090Srdivacky V2 = V2->stripPointerCasts(); 1308198090Srdivacky 1309288943Sdim // If V1 or V2 is undef, the result is NoAlias because we can always pick a 1310288943Sdim // value for undef that aliases nothing in the program. 1311288943Sdim if (isa<UndefValue>(V1) || isa<UndefValue>(V2)) 1312288943Sdim return NoAlias; 1313288943Sdim 1314198090Srdivacky // Are we checking for alias of the same value? 1315265925Sdim // Because we look 'through' phi nodes we could look at "Value" pointers from 1316265925Sdim // different iterations. We must therefore make sure that this is not the 1317265925Sdim // case. The function isValueEqualInPotentialCycles ensures that this cannot 1318265925Sdim // happen by looking at the visited phi nodes and making sure they cannot 1319265925Sdim // reach the value. 1320265925Sdim if (isValueEqualInPotentialCycles(V1, V2)) 1321265925Sdim return MustAlias; 1322198090Srdivacky 1323204642Srdivacky if (!V1->getType()->isPointerTy() || !V2->getType()->isPointerTy()) 1324296417Sdim return NoAlias; // Scalars cannot alias each other 1325198090Srdivacky 1326198090Srdivacky // Figure out what objects these things are pointing to if we can. 1327296417Sdim const Value *O1 = GetUnderlyingObject(V1, DL, MaxLookupSearchDepth); 1328296417Sdim const Value *O2 = GetUnderlyingObject(V2, DL, MaxLookupSearchDepth); 1329198090Srdivacky 1330199481Srdivacky // Null values in the default address space don't point to any object, so they 1331199481Srdivacky // don't alias any other pointer. 1332199481Srdivacky if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O1)) 1333199481Srdivacky if (CPN->getType()->getAddressSpace() == 0) 1334199481Srdivacky return NoAlias; 1335199481Srdivacky if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O2)) 1336199481Srdivacky if (CPN->getType()->getAddressSpace() == 0) 1337199481Srdivacky return NoAlias; 1338199481Srdivacky 1339198090Srdivacky if (O1 != O2) { 1340198090Srdivacky // If V1/V2 point to two different objects we know that we have no alias. 1341198090Srdivacky if (isIdentifiedObject(O1) && isIdentifiedObject(O2)) 1342198090Srdivacky return NoAlias; 1343199481Srdivacky 1344199481Srdivacky // Constant pointers can't alias with non-const isIdentifiedObject objects. 1345199481Srdivacky if ((isa<Constant>(O1) && isIdentifiedObject(O2) && !isa<Constant>(O2)) || 1346199481Srdivacky (isa<Constant>(O2) && isIdentifiedObject(O1) && !isa<Constant>(O1))) 1347199481Srdivacky return NoAlias; 1348199481Srdivacky 1349261991Sdim // Function arguments can't alias with things that are known to be 1350261991Sdim // unambigously identified at the function level. 1351261991Sdim if ((isa<Argument>(O1) && isIdentifiedFunctionLocal(O2)) || 1352261991Sdim (isa<Argument>(O2) && isIdentifiedFunctionLocal(O1))) 1353198090Srdivacky return NoAlias; 1354198090Srdivacky 1355198090Srdivacky // Most objects can't alias null. 1356210299Sed if ((isa<ConstantPointerNull>(O2) && isKnownNonNull(O1)) || 1357210299Sed (isa<ConstantPointerNull>(O1) && isKnownNonNull(O2))) 1358198090Srdivacky return NoAlias; 1359261991Sdim 1360210299Sed // If one pointer is the result of a call/invoke or load and the other is a 1361210299Sed // non-escaping local object within the same function, then we know the 1362210299Sed // object couldn't escape to a point where the call could return it. 1363210299Sed // 1364210299Sed // Note that if the pointers are in different functions, there are a 1365210299Sed // variety of complications. A call with a nocapture argument may still 1366210299Sed // temporary store the nocapture argument's value in a temporary memory 1367210299Sed // location if that memory location doesn't escape. Or it may pass a 1368210299Sed // nocapture value to other functions as long as they don't capture it. 1369210299Sed if (isEscapeSource(O1) && isNonEscapingLocalObject(O2)) 1370210299Sed return NoAlias; 1371210299Sed if (isEscapeSource(O2) && isNonEscapingLocalObject(O1)) 1372210299Sed return NoAlias; 1373198090Srdivacky } 1374210299Sed 1375198090Srdivacky // If the size of one access is larger than the entire object on the other 1376198090Srdivacky // side, then we know such behavior is undefined and can assume no alias. 1377296417Sdim if ((V1Size != MemoryLocation::UnknownSize && 1378296417Sdim isObjectSmallerThan(O2, V1Size, DL, TLI)) || 1379296417Sdim (V2Size != MemoryLocation::UnknownSize && 1380296417Sdim isObjectSmallerThan(O1, V2Size, DL, TLI))) 1381296417Sdim return NoAlias; 1382261991Sdim 1383223017Sdim // Check the cache before climbing up use-def chains. This also terminates 1384223017Sdim // otherwise infinitely recursive queries. 1385288943Sdim LocPair Locs(MemoryLocation(V1, V1Size, V1AAInfo), 1386288943Sdim MemoryLocation(V2, V2Size, V2AAInfo)); 1387223017Sdim if (V1 > V2) 1388223017Sdim std::swap(Locs.first, Locs.second); 1389223017Sdim std::pair<AliasCacheTy::iterator, bool> Pair = 1390296417Sdim AliasCache.insert(std::make_pair(Locs, MayAlias)); 1391223017Sdim if (!Pair.second) 1392223017Sdim return Pair.first->second; 1393223017Sdim 1394199989Srdivacky // FIXME: This isn't aggressively handling alias(GEP, PHI) for example: if the 1395199989Srdivacky // GEP can't simplify, we don't even look at the PHI cases. 1396198396Srdivacky if (!isa<GEPOperator>(V1) && isa<GEPOperator>(V2)) { 1397198090Srdivacky std::swap(V1, V2); 1398198090Srdivacky std::swap(V1Size, V2Size); 1399199989Srdivacky std::swap(O1, O2); 1400280031Sdim std::swap(V1AAInfo, V2AAInfo); 1401198090Srdivacky } 1402218893Sdim if (const GEPOperator *GV1 = dyn_cast<GEPOperator>(V1)) { 1403296417Sdim AliasResult Result = 1404296417Sdim aliasGEP(GV1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, O1, O2); 1405296417Sdim if (Result != MayAlias) 1406296417Sdim return AliasCache[Locs] = Result; 1407218893Sdim } 1408198090Srdivacky 1409198090Srdivacky if (isa<PHINode>(V2) && !isa<PHINode>(V1)) { 1410198090Srdivacky std::swap(V1, V2); 1411198090Srdivacky std::swap(V1Size, V2Size); 1412280031Sdim std::swap(V1AAInfo, V2AAInfo); 1413198090Srdivacky } 1414218893Sdim if (const PHINode *PN = dyn_cast<PHINode>(V1)) { 1415296417Sdim AliasResult Result = aliasPHI(PN, V1Size, V1AAInfo, V2, V2Size, V2AAInfo); 1416296417Sdim if (Result != MayAlias) 1417296417Sdim return AliasCache[Locs] = Result; 1418218893Sdim } 1419198090Srdivacky 1420198892Srdivacky if (isa<SelectInst>(V2) && !isa<SelectInst>(V1)) { 1421198892Srdivacky std::swap(V1, V2); 1422198892Srdivacky std::swap(V1Size, V2Size); 1423280031Sdim std::swap(V1AAInfo, V2AAInfo); 1424198892Srdivacky } 1425218893Sdim if (const SelectInst *S1 = dyn_cast<SelectInst>(V1)) { 1426296417Sdim AliasResult Result = 1427296417Sdim aliasSelect(S1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo); 1428296417Sdim if (Result != MayAlias) 1429296417Sdim return AliasCache[Locs] = Result; 1430218893Sdim } 1431198892Srdivacky 1432218893Sdim // If both pointers are pointing into the same object and one of them 1433218893Sdim // accesses is accessing the entire object, then the accesses must 1434218893Sdim // overlap in some way. 1435296417Sdim if (O1 == O2) 1436288943Sdim if ((V1Size != MemoryLocation::UnknownSize && 1437296417Sdim isObjectSize(O1, V1Size, DL, TLI)) || 1438288943Sdim (V2Size != MemoryLocation::UnknownSize && 1439296417Sdim isObjectSize(O2, V2Size, DL, TLI))) 1440223017Sdim return AliasCache[Locs] = PartialAlias; 1441218893Sdim 1442296417Sdim // Recurse back into the best AA results we have, potentially with refined 1443296417Sdim // memory locations. We have already ensured that BasicAA has a MayAlias 1444296417Sdim // cache result for these, so any recursion back into BasicAA won't loop. 1445296417Sdim AliasResult Result = getBestAAResults().alias(Locs.first, Locs.second); 1446223017Sdim return AliasCache[Locs] = Result; 1447198090Srdivacky} 1448265925Sdim 1449296417Sdim/// Check whether two Values can be considered equivalent. 1450296417Sdim/// 1451296417Sdim/// In addition to pointer equivalence of \p V1 and \p V2 this checks whether 1452296417Sdim/// they can not be part of a cycle in the value graph by looking at all 1453296417Sdim/// visited phi nodes an making sure that the phis cannot reach the value. We 1454296417Sdim/// have to do this because we are looking through phi nodes (That is we say 1455296417Sdim/// noalias(V, phi(VA, VB)) if noalias(V, VA) and noalias(V, VB). 1456296417Sdimbool BasicAAResult::isValueEqualInPotentialCycles(const Value *V, 1457296417Sdim const Value *V2) { 1458265925Sdim if (V != V2) 1459265925Sdim return false; 1460265925Sdim 1461265925Sdim const Instruction *Inst = dyn_cast<Instruction>(V); 1462265925Sdim if (!Inst) 1463265925Sdim return true; 1464265925Sdim 1465288943Sdim if (VisitedPhiBBs.empty()) 1466288943Sdim return true; 1467288943Sdim 1468265925Sdim if (VisitedPhiBBs.size() > MaxNumPhiBBsValueReachabilityCheck) 1469265925Sdim return false; 1470265925Sdim 1471265925Sdim // Make sure that the visited phis cannot reach the Value. This ensures that 1472265925Sdim // the Values cannot come from different iterations of a potential cycle the 1473265925Sdim // phi nodes could be involved in. 1474280031Sdim for (auto *P : VisitedPhiBBs) 1475296417Sdim if (isPotentiallyReachable(&P->front(), Inst, DT, LI)) 1476265925Sdim return false; 1477265925Sdim 1478265925Sdim return true; 1479265925Sdim} 1480265925Sdim 1481296417Sdim/// Computes the symbolic difference between two de-composed GEPs. 1482296417Sdim/// 1483296417Sdim/// Dest and Src are the variable indices from two decomposed GetElementPtr 1484296417Sdim/// instructions GEP1 and GEP2 which have common base pointers. 1485296417Sdimvoid BasicAAResult::GetIndexDifference( 1486265925Sdim SmallVectorImpl<VariableGEPIndex> &Dest, 1487265925Sdim const SmallVectorImpl<VariableGEPIndex> &Src) { 1488265925Sdim if (Src.empty()) 1489265925Sdim return; 1490265925Sdim 1491265925Sdim for (unsigned i = 0, e = Src.size(); i != e; ++i) { 1492265925Sdim const Value *V = Src[i].V; 1493296417Sdim unsigned ZExtBits = Src[i].ZExtBits, SExtBits = Src[i].SExtBits; 1494265925Sdim int64_t Scale = Src[i].Scale; 1495265925Sdim 1496265925Sdim // Find V in Dest. This is N^2, but pointer indices almost never have more 1497265925Sdim // than a few variable indexes. 1498265925Sdim for (unsigned j = 0, e = Dest.size(); j != e; ++j) { 1499265925Sdim if (!isValueEqualInPotentialCycles(Dest[j].V, V) || 1500296417Sdim Dest[j].ZExtBits != ZExtBits || Dest[j].SExtBits != SExtBits) 1501265925Sdim continue; 1502265925Sdim 1503265925Sdim // If we found it, subtract off Scale V's from the entry in Dest. If it 1504265925Sdim // goes to zero, remove the entry. 1505265925Sdim if (Dest[j].Scale != Scale) 1506265925Sdim Dest[j].Scale -= Scale; 1507265925Sdim else 1508265925Sdim Dest.erase(Dest.begin() + j); 1509265925Sdim Scale = 0; 1510265925Sdim break; 1511265925Sdim } 1512265925Sdim 1513265925Sdim // If we didn't consume this entry, add it to the end of the Dest list. 1514265925Sdim if (Scale) { 1515296417Sdim VariableGEPIndex Entry = {V, ZExtBits, SExtBits, -Scale}; 1516265925Sdim Dest.push_back(Entry); 1517265925Sdim } 1518265925Sdim } 1519265925Sdim} 1520296417Sdim 1521296417Sdimbool BasicAAResult::constantOffsetHeuristic( 1522296417Sdim const SmallVectorImpl<VariableGEPIndex> &VarIndices, uint64_t V1Size, 1523296417Sdim uint64_t V2Size, int64_t BaseOffset, AssumptionCache *AC, 1524296417Sdim DominatorTree *DT) { 1525296417Sdim if (VarIndices.size() != 2 || V1Size == MemoryLocation::UnknownSize || 1526296417Sdim V2Size == MemoryLocation::UnknownSize) 1527296417Sdim return false; 1528296417Sdim 1529296417Sdim const VariableGEPIndex &Var0 = VarIndices[0], &Var1 = VarIndices[1]; 1530296417Sdim 1531296417Sdim if (Var0.ZExtBits != Var1.ZExtBits || Var0.SExtBits != Var1.SExtBits || 1532296417Sdim Var0.Scale != -Var1.Scale) 1533296417Sdim return false; 1534296417Sdim 1535296417Sdim unsigned Width = Var1.V->getType()->getIntegerBitWidth(); 1536296417Sdim 1537296417Sdim // We'll strip off the Extensions of Var0 and Var1 and do another round 1538296417Sdim // of GetLinearExpression decomposition. In the example above, if Var0 1539296417Sdim // is zext(%x + 1) we should get V1 == %x and V1Offset == 1. 1540296417Sdim 1541296417Sdim APInt V0Scale(Width, 0), V0Offset(Width, 0), V1Scale(Width, 0), 1542296417Sdim V1Offset(Width, 0); 1543296417Sdim bool NSW = true, NUW = true; 1544296417Sdim unsigned V0ZExtBits = 0, V0SExtBits = 0, V1ZExtBits = 0, V1SExtBits = 0; 1545296417Sdim const Value *V0 = GetLinearExpression(Var0.V, V0Scale, V0Offset, V0ZExtBits, 1546296417Sdim V0SExtBits, DL, 0, AC, DT, NSW, NUW); 1547296417Sdim NSW = true, NUW = true; 1548296417Sdim const Value *V1 = GetLinearExpression(Var1.V, V1Scale, V1Offset, V1ZExtBits, 1549296417Sdim V1SExtBits, DL, 0, AC, DT, NSW, NUW); 1550296417Sdim 1551296417Sdim if (V0Scale != V1Scale || V0ZExtBits != V1ZExtBits || 1552296417Sdim V0SExtBits != V1SExtBits || !isValueEqualInPotentialCycles(V0, V1)) 1553296417Sdim return false; 1554296417Sdim 1555296417Sdim // We have a hit - Var0 and Var1 only differ by a constant offset! 1556296417Sdim 1557296417Sdim // If we've been sext'ed then zext'd the maximum difference between Var0 and 1558296417Sdim // Var1 is possible to calculate, but we're just interested in the absolute 1559296417Sdim // minimum difference between the two. The minimum distance may occur due to 1560296417Sdim // wrapping; consider "add i3 %i, 5": if %i == 7 then 7 + 5 mod 8 == 4, and so 1561296417Sdim // the minimum distance between %i and %i + 5 is 3. 1562296417Sdim APInt MinDiff = V0Offset - V1Offset, Wrapped = -MinDiff; 1563296417Sdim MinDiff = APIntOps::umin(MinDiff, Wrapped); 1564296417Sdim uint64_t MinDiffBytes = MinDiff.getZExtValue() * std::abs(Var0.Scale); 1565296417Sdim 1566296417Sdim // We can't definitely say whether GEP1 is before or after V2 due to wrapping 1567296417Sdim // arithmetic (i.e. for some values of GEP1 and V2 GEP1 < V2, and for other 1568296417Sdim // values GEP1 > V2). We'll therefore only declare NoAlias if both V1Size and 1569296417Sdim // V2Size can fit in the MinDiffBytes gap. 1570296417Sdim return V1Size + std::abs(BaseOffset) <= MinDiffBytes && 1571296417Sdim V2Size + std::abs(BaseOffset) <= MinDiffBytes; 1572296417Sdim} 1573296417Sdim 1574296417Sdim//===----------------------------------------------------------------------===// 1575296417Sdim// BasicAliasAnalysis Pass 1576296417Sdim//===----------------------------------------------------------------------===// 1577296417Sdim 1578296417Sdimchar BasicAA::PassID; 1579296417Sdim 1580296417SdimBasicAAResult BasicAA::run(Function &F, AnalysisManager<Function> *AM) { 1581296417Sdim return BasicAAResult(F.getParent()->getDataLayout(), 1582296417Sdim AM->getResult<TargetLibraryAnalysis>(F), 1583296417Sdim AM->getResult<AssumptionAnalysis>(F), 1584296417Sdim AM->getCachedResult<DominatorTreeAnalysis>(F), 1585296417Sdim AM->getCachedResult<LoopAnalysis>(F)); 1586296417Sdim} 1587296417Sdim 1588296417SdimBasicAAWrapperPass::BasicAAWrapperPass() : FunctionPass(ID) { 1589296417Sdim initializeBasicAAWrapperPassPass(*PassRegistry::getPassRegistry()); 1590296417Sdim} 1591296417Sdim 1592296417Sdimchar BasicAAWrapperPass::ID = 0; 1593296417Sdimvoid BasicAAWrapperPass::anchor() {} 1594296417Sdim 1595296417SdimINITIALIZE_PASS_BEGIN(BasicAAWrapperPass, "basicaa", 1596296417Sdim "Basic Alias Analysis (stateless AA impl)", true, true) 1597296417SdimINITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 1598296417SdimINITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 1599296417SdimINITIALIZE_PASS_END(BasicAAWrapperPass, "basicaa", 1600296417Sdim "Basic Alias Analysis (stateless AA impl)", true, true) 1601296417Sdim 1602296417SdimFunctionPass *llvm::createBasicAAWrapperPass() { 1603296417Sdim return new BasicAAWrapperPass(); 1604296417Sdim} 1605296417Sdim 1606296417Sdimbool BasicAAWrapperPass::runOnFunction(Function &F) { 1607296417Sdim auto &ACT = getAnalysis<AssumptionCacheTracker>(); 1608296417Sdim auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>(); 1609296417Sdim auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>(); 1610296417Sdim auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>(); 1611296417Sdim 1612296417Sdim Result.reset(new BasicAAResult(F.getParent()->getDataLayout(), TLIWP.getTLI(), 1613296417Sdim ACT.getAssumptionCache(F), 1614296417Sdim DTWP ? &DTWP->getDomTree() : nullptr, 1615296417Sdim LIWP ? &LIWP->getLoopInfo() : nullptr)); 1616296417Sdim 1617296417Sdim return false; 1618296417Sdim} 1619296417Sdim 1620296417Sdimvoid BasicAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { 1621296417Sdim AU.setPreservesAll(); 1622296417Sdim AU.addRequired<AssumptionCacheTracker>(); 1623296417Sdim AU.addRequired<TargetLibraryInfoWrapperPass>(); 1624296417Sdim} 1625296417Sdim 1626296417SdimBasicAAResult llvm::createLegacyPMBasicAAResult(Pass &P, Function &F) { 1627296417Sdim return BasicAAResult( 1628296417Sdim F.getParent()->getDataLayout(), 1629296417Sdim P.getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(), 1630296417Sdim P.getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F)); 1631296417Sdim} 1632