1//===- BasicAliasAnalysis.cpp - Stateless Alias Analysis Impl -------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines the primary stateless implementation of the 11// Alias Analysis interface that implements identities (two different 12// globals cannot alias, etc), but does no stateful analysis. 13// 14//===----------------------------------------------------------------------===// 15 16#include "llvm/Analysis/BasicAliasAnalysis.h" 17#include "llvm/ADT/SmallVector.h" 18#include "llvm/ADT/Statistic.h" 19#include "llvm/Analysis/AliasAnalysis.h" 20#include "llvm/Analysis/CFG.h" 21#include "llvm/Analysis/CaptureTracking.h" 22#include "llvm/Analysis/InstructionSimplify.h" 23#include "llvm/Analysis/LoopInfo.h" 24#include "llvm/Analysis/MemoryBuiltins.h" 25#include "llvm/Analysis/ValueTracking.h" 26#include "llvm/Analysis/AssumptionCache.h" 27#include "llvm/IR/Constants.h" 28#include "llvm/IR/DataLayout.h" 29#include "llvm/IR/DerivedTypes.h" 30#include "llvm/IR/Dominators.h" 31#include "llvm/IR/GlobalAlias.h" 32#include "llvm/IR/GlobalVariable.h" 33#include "llvm/IR/Instructions.h" 34#include "llvm/IR/IntrinsicInst.h" 35#include "llvm/IR/LLVMContext.h" 36#include "llvm/IR/Operator.h" 37#include "llvm/Pass.h" 38#include "llvm/Support/ErrorHandling.h" 39#include <algorithm> 40using namespace llvm; 41 42/// Enable analysis of recursive PHI nodes. 43static cl::opt<bool> EnableRecPhiAnalysis("basicaa-recphi", cl::Hidden, 44 cl::init(false)); 45 46/// SearchLimitReached / SearchTimes shows how often the limit of 47/// to decompose GEPs is reached. It will affect the precision 48/// of basic alias analysis. 49#define DEBUG_TYPE "basicaa" 50STATISTIC(SearchLimitReached, "Number of times the limit to " 51 "decompose GEPs is reached"); 52STATISTIC(SearchTimes, "Number of times a GEP is decomposed"); 53 54/// Cutoff after which to stop analysing a set of phi nodes potentially involved 55/// in a cycle. Because we are analysing 'through' phi nodes we need to be 56/// careful with value equivalence. We use reachability to make sure a value 57/// cannot be involved in a cycle. 58const unsigned MaxNumPhiBBsValueReachabilityCheck = 20; 59 60// The max limit of the search depth in DecomposeGEPExpression() and 61// GetUnderlyingObject(), both functions need to use the same search 62// depth otherwise the algorithm in aliasGEP will assert. 63static const unsigned MaxLookupSearchDepth = 6; 64 65//===----------------------------------------------------------------------===// 66// Useful predicates 67//===----------------------------------------------------------------------===// 68 69/// Returns true if the pointer is to a function-local object that never 70/// escapes from the function. 71static bool isNonEscapingLocalObject(const Value *V) { 72 // If this is a local allocation, check to see if it escapes. 73 if (isa<AllocaInst>(V) || isNoAliasCall(V)) 74 // Set StoreCaptures to True so that we can assume in our callers that the 75 // pointer is not the result of a load instruction. Currently 76 // PointerMayBeCaptured doesn't have any special analysis for the 77 // StoreCaptures=false case; if it did, our callers could be refined to be 78 // more precise. 79 return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true); 80 81 // If this is an argument that corresponds to a byval or noalias argument, 82 // then it has not escaped before entering the function. Check if it escapes 83 // inside the function. 84 if (const Argument *A = dyn_cast<Argument>(V)) 85 if (A->hasByValAttr() || A->hasNoAliasAttr()) 86 // Note even if the argument is marked nocapture we still need to check 87 // for copies made inside the function. The nocapture attribute only 88 // specifies that there are no copies made that outlive the function. 89 return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true); 90 91 return false; 92} 93 94/// Returns true if the pointer is one which would have been considered an 95/// escape by isNonEscapingLocalObject. 96static bool isEscapeSource(const Value *V) { 97 if (isa<CallInst>(V) || isa<InvokeInst>(V) || isa<Argument>(V)) 98 return true; 99 100 // The load case works because isNonEscapingLocalObject considers all 101 // stores to be escapes (it passes true for the StoreCaptures argument 102 // to PointerMayBeCaptured). 103 if (isa<LoadInst>(V)) 104 return true; 105 106 return false; 107} 108 109/// Returns the size of the object specified by V, or UnknownSize if unknown. 110static uint64_t getObjectSize(const Value *V, const DataLayout &DL, 111 const TargetLibraryInfo &TLI, 112 bool RoundToAlign = false) { 113 uint64_t Size; 114 if (getObjectSize(V, Size, DL, &TLI, RoundToAlign)) 115 return Size; 116 return MemoryLocation::UnknownSize; 117} 118 119/// Returns true if we can prove that the object specified by V is smaller than 120/// Size. 121static bool isObjectSmallerThan(const Value *V, uint64_t Size, 122 const DataLayout &DL, 123 const TargetLibraryInfo &TLI) { 124 // Note that the meanings of the "object" are slightly different in the 125 // following contexts: 126 // c1: llvm::getObjectSize() 127 // c2: llvm.objectsize() intrinsic 128 // c3: isObjectSmallerThan() 129 // c1 and c2 share the same meaning; however, the meaning of "object" in c3 130 // refers to the "entire object". 131 // 132 // Consider this example: 133 // char *p = (char*)malloc(100) 134 // char *q = p+80; 135 // 136 // In the context of c1 and c2, the "object" pointed by q refers to the 137 // stretch of memory of q[0:19]. So, getObjectSize(q) should return 20. 138 // 139 // However, in the context of c3, the "object" refers to the chunk of memory 140 // being allocated. So, the "object" has 100 bytes, and q points to the middle 141 // the "object". In case q is passed to isObjectSmallerThan() as the 1st 142 // parameter, before the llvm::getObjectSize() is called to get the size of 143 // entire object, we should: 144 // - either rewind the pointer q to the base-address of the object in 145 // question (in this case rewind to p), or 146 // - just give up. It is up to caller to make sure the pointer is pointing 147 // to the base address the object. 148 // 149 // We go for 2nd option for simplicity. 150 if (!isIdentifiedObject(V)) 151 return false; 152 153 // This function needs to use the aligned object size because we allow 154 // reads a bit past the end given sufficient alignment. 155 uint64_t ObjectSize = getObjectSize(V, DL, TLI, /*RoundToAlign*/ true); 156 157 return ObjectSize != MemoryLocation::UnknownSize && ObjectSize < Size; 158} 159 160/// Returns true if we can prove that the object specified by V has size Size. 161static bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &DL, 162 const TargetLibraryInfo &TLI) { 163 uint64_t ObjectSize = getObjectSize(V, DL, TLI); 164 return ObjectSize != MemoryLocation::UnknownSize && ObjectSize == Size; 165} 166 167//===----------------------------------------------------------------------===// 168// GetElementPtr Instruction Decomposition and Analysis 169//===----------------------------------------------------------------------===// 170 171/// Analyzes the specified value as a linear expression: "A*V + B", where A and 172/// B are constant integers. 173/// 174/// Returns the scale and offset values as APInts and return V as a Value*, and 175/// return whether we looked through any sign or zero extends. The incoming 176/// Value is known to have IntegerType and it may already be sign or zero 177/// extended. 178/// 179/// Note that this looks through extends, so the high bits may not be 180/// represented in the result. 181/*static*/ const Value *BasicAAResult::GetLinearExpression( 182 const Value *V, APInt &Scale, APInt &Offset, unsigned &ZExtBits, 183 unsigned &SExtBits, const DataLayout &DL, unsigned Depth, 184 AssumptionCache *AC, DominatorTree *DT, bool &NSW, bool &NUW) { 185 assert(V->getType()->isIntegerTy() && "Not an integer value"); 186 187 // Limit our recursion depth. 188 if (Depth == 6) { 189 Scale = 1; 190 Offset = 0; 191 return V; 192 } 193 194 if (const ConstantInt *Const = dyn_cast<ConstantInt>(V)) { 195 // if it's a constant, just convert it to an offset and remove the variable. 196 // If we've been called recursively the Offset bit width will be greater 197 // than the constant's (the Offset's always as wide as the outermost call), 198 // so we'll zext here and process any extension in the isa<SExtInst> & 199 // isa<ZExtInst> cases below. 200 Offset += Const->getValue().zextOrSelf(Offset.getBitWidth()); 201 assert(Scale == 0 && "Constant values don't have a scale"); 202 return V; 203 } 204 205 if (const BinaryOperator *BOp = dyn_cast<BinaryOperator>(V)) { 206 if (ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) { 207 208 // If we've been called recursively then Offset and Scale will be wider 209 // that the BOp operands. We'll always zext it here as we'll process sign 210 // extensions below (see the isa<SExtInst> / isa<ZExtInst> cases). 211 APInt RHS = RHSC->getValue().zextOrSelf(Offset.getBitWidth()); 212 213 switch (BOp->getOpcode()) { 214 default: 215 // We don't understand this instruction, so we can't decompose it any 216 // further. 217 Scale = 1; 218 Offset = 0; 219 return V; 220 case Instruction::Or: 221 // X|C == X+C if all the bits in C are unset in X. Otherwise we can't 222 // analyze it. 223 if (!MaskedValueIsZero(BOp->getOperand(0), RHSC->getValue(), DL, 0, AC, 224 BOp, DT)) { 225 Scale = 1; 226 Offset = 0; 227 return V; 228 } 229 // FALL THROUGH. 230 case Instruction::Add: 231 V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits, 232 SExtBits, DL, Depth + 1, AC, DT, NSW, NUW); 233 Offset += RHS; 234 break; 235 case Instruction::Sub: 236 V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits, 237 SExtBits, DL, Depth + 1, AC, DT, NSW, NUW); 238 Offset -= RHS; 239 break; 240 case Instruction::Mul: 241 V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits, 242 SExtBits, DL, Depth + 1, AC, DT, NSW, NUW); 243 Offset *= RHS; 244 Scale *= RHS; 245 break; 246 case Instruction::Shl: 247 V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits, 248 SExtBits, DL, Depth + 1, AC, DT, NSW, NUW); 249 Offset <<= RHS.getLimitedValue(); 250 Scale <<= RHS.getLimitedValue(); 251 // the semantics of nsw and nuw for left shifts don't match those of 252 // multiplications, so we won't propagate them. 253 NSW = NUW = false; 254 return V; 255 } 256 257 if (isa<OverflowingBinaryOperator>(BOp)) { 258 NUW &= BOp->hasNoUnsignedWrap(); 259 NSW &= BOp->hasNoSignedWrap(); 260 } 261 return V; 262 } 263 } 264 265 // Since GEP indices are sign extended anyway, we don't care about the high 266 // bits of a sign or zero extended value - just scales and offsets. The 267 // extensions have to be consistent though. 268 if (isa<SExtInst>(V) || isa<ZExtInst>(V)) { 269 Value *CastOp = cast<CastInst>(V)->getOperand(0); 270 unsigned NewWidth = V->getType()->getPrimitiveSizeInBits(); 271 unsigned SmallWidth = CastOp->getType()->getPrimitiveSizeInBits(); 272 unsigned OldZExtBits = ZExtBits, OldSExtBits = SExtBits; 273 const Value *Result = 274 GetLinearExpression(CastOp, Scale, Offset, ZExtBits, SExtBits, DL, 275 Depth + 1, AC, DT, NSW, NUW); 276 277 // zext(zext(%x)) == zext(%x), and similiarly for sext; we'll handle this 278 // by just incrementing the number of bits we've extended by. 279 unsigned ExtendedBy = NewWidth - SmallWidth; 280 281 if (isa<SExtInst>(V) && ZExtBits == 0) { 282 // sext(sext(%x, a), b) == sext(%x, a + b) 283 284 if (NSW) { 285 // We haven't sign-wrapped, so it's valid to decompose sext(%x + c) 286 // into sext(%x) + sext(c). We'll sext the Offset ourselves: 287 unsigned OldWidth = Offset.getBitWidth(); 288 Offset = Offset.trunc(SmallWidth).sext(NewWidth).zextOrSelf(OldWidth); 289 } else { 290 // We may have signed-wrapped, so don't decompose sext(%x + c) into 291 // sext(%x) + sext(c) 292 Scale = 1; 293 Offset = 0; 294 Result = CastOp; 295 ZExtBits = OldZExtBits; 296 SExtBits = OldSExtBits; 297 } 298 SExtBits += ExtendedBy; 299 } else { 300 // sext(zext(%x, a), b) = zext(zext(%x, a), b) = zext(%x, a + b) 301 302 if (!NUW) { 303 // We may have unsigned-wrapped, so don't decompose zext(%x + c) into 304 // zext(%x) + zext(c) 305 Scale = 1; 306 Offset = 0; 307 Result = CastOp; 308 ZExtBits = OldZExtBits; 309 SExtBits = OldSExtBits; 310 } 311 ZExtBits += ExtendedBy; 312 } 313 314 return Result; 315 } 316 317 Scale = 1; 318 Offset = 0; 319 return V; 320} 321 322/// If V is a symbolic pointer expression, decompose it into a base pointer 323/// with a constant offset and a number of scaled symbolic offsets. 324/// 325/// The scaled symbolic offsets (represented by pairs of a Value* and a scale 326/// in the VarIndices vector) are Value*'s that are known to be scaled by the 327/// specified amount, but which may have other unrepresented high bits. As 328/// such, the gep cannot necessarily be reconstructed from its decomposed form. 329/// 330/// When DataLayout is around, this function is capable of analyzing everything 331/// that GetUnderlyingObject can look through. To be able to do that 332/// GetUnderlyingObject and DecomposeGEPExpression must use the same search 333/// depth (MaxLookupSearchDepth). When DataLayout not is around, it just looks 334/// through pointer casts. 335/*static*/ const Value *BasicAAResult::DecomposeGEPExpression( 336 const Value *V, int64_t &BaseOffs, 337 SmallVectorImpl<VariableGEPIndex> &VarIndices, bool &MaxLookupReached, 338 const DataLayout &DL, AssumptionCache *AC, DominatorTree *DT) { 339 // Limit recursion depth to limit compile time in crazy cases. 340 unsigned MaxLookup = MaxLookupSearchDepth; 341 MaxLookupReached = false; 342 SearchTimes++; 343 344 BaseOffs = 0; 345 do { 346 // See if this is a bitcast or GEP. 347 const Operator *Op = dyn_cast<Operator>(V); 348 if (!Op) { 349 // The only non-operator case we can handle are GlobalAliases. 350 if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 351 if (!GA->mayBeOverridden()) { 352 V = GA->getAliasee(); 353 continue; 354 } 355 } 356 return V; 357 } 358 359 if (Op->getOpcode() == Instruction::BitCast || 360 Op->getOpcode() == Instruction::AddrSpaceCast) { 361 V = Op->getOperand(0); 362 continue; 363 } 364 365 const GEPOperator *GEPOp = dyn_cast<GEPOperator>(Op); 366 if (!GEPOp) { 367 // If it's not a GEP, hand it off to SimplifyInstruction to see if it 368 // can come up with something. This matches what GetUnderlyingObject does. 369 if (const Instruction *I = dyn_cast<Instruction>(V)) 370 // TODO: Get a DominatorTree and AssumptionCache and use them here 371 // (these are both now available in this function, but this should be 372 // updated when GetUnderlyingObject is updated). TLI should be 373 // provided also. 374 if (const Value *Simplified = 375 SimplifyInstruction(const_cast<Instruction *>(I), DL)) { 376 V = Simplified; 377 continue; 378 } 379 380 return V; 381 } 382 383 // Don't attempt to analyze GEPs over unsized objects. 384 if (!GEPOp->getOperand(0)->getType()->getPointerElementType()->isSized()) 385 return V; 386 387 unsigned AS = GEPOp->getPointerAddressSpace(); 388 // Walk the indices of the GEP, accumulating them into BaseOff/VarIndices. 389 gep_type_iterator GTI = gep_type_begin(GEPOp); 390 for (User::const_op_iterator I = GEPOp->op_begin() + 1, E = GEPOp->op_end(); 391 I != E; ++I) { 392 const Value *Index = *I; 393 // Compute the (potentially symbolic) offset in bytes for this index. 394 if (StructType *STy = dyn_cast<StructType>(*GTI++)) { 395 // For a struct, add the member offset. 396 unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue(); 397 if (FieldNo == 0) 398 continue; 399 400 BaseOffs += DL.getStructLayout(STy)->getElementOffset(FieldNo); 401 continue; 402 } 403 404 // For an array/pointer, add the element offset, explicitly scaled. 405 if (const ConstantInt *CIdx = dyn_cast<ConstantInt>(Index)) { 406 if (CIdx->isZero()) 407 continue; 408 BaseOffs += DL.getTypeAllocSize(*GTI) * CIdx->getSExtValue(); 409 continue; 410 } 411 412 uint64_t Scale = DL.getTypeAllocSize(*GTI); 413 unsigned ZExtBits = 0, SExtBits = 0; 414 415 // If the integer type is smaller than the pointer size, it is implicitly 416 // sign extended to pointer size. 417 unsigned Width = Index->getType()->getIntegerBitWidth(); 418 unsigned PointerSize = DL.getPointerSizeInBits(AS); 419 if (PointerSize > Width) 420 SExtBits += PointerSize - Width; 421 422 // Use GetLinearExpression to decompose the index into a C1*V+C2 form. 423 APInt IndexScale(Width, 0), IndexOffset(Width, 0); 424 bool NSW = true, NUW = true; 425 Index = GetLinearExpression(Index, IndexScale, IndexOffset, ZExtBits, 426 SExtBits, DL, 0, AC, DT, NSW, NUW); 427 428 // The GEP index scale ("Scale") scales C1*V+C2, yielding (C1*V+C2)*Scale. 429 // This gives us an aggregate computation of (C1*Scale)*V + C2*Scale. 430 BaseOffs += IndexOffset.getSExtValue() * Scale; 431 Scale *= IndexScale.getSExtValue(); 432 433 // If we already had an occurrence of this index variable, merge this 434 // scale into it. For example, we want to handle: 435 // A[x][x] -> x*16 + x*4 -> x*20 436 // This also ensures that 'x' only appears in the index list once. 437 for (unsigned i = 0, e = VarIndices.size(); i != e; ++i) { 438 if (VarIndices[i].V == Index && VarIndices[i].ZExtBits == ZExtBits && 439 VarIndices[i].SExtBits == SExtBits) { 440 Scale += VarIndices[i].Scale; 441 VarIndices.erase(VarIndices.begin() + i); 442 break; 443 } 444 } 445 446 // Make sure that we have a scale that makes sense for this target's 447 // pointer size. 448 if (unsigned ShiftBits = 64 - PointerSize) { 449 Scale <<= ShiftBits; 450 Scale = (int64_t)Scale >> ShiftBits; 451 } 452 453 if (Scale) { 454 VariableGEPIndex Entry = {Index, ZExtBits, SExtBits, 455 static_cast<int64_t>(Scale)}; 456 VarIndices.push_back(Entry); 457 } 458 } 459 460 // Analyze the base pointer next. 461 V = GEPOp->getOperand(0); 462 } while (--MaxLookup); 463 464 // If the chain of expressions is too deep, just return early. 465 MaxLookupReached = true; 466 SearchLimitReached++; 467 return V; 468} 469 470/// Returns whether the given pointer value points to memory that is local to 471/// the function, with global constants being considered local to all 472/// functions. 473bool BasicAAResult::pointsToConstantMemory(const MemoryLocation &Loc, 474 bool OrLocal) { 475 assert(Visited.empty() && "Visited must be cleared after use!"); 476 477 unsigned MaxLookup = 8; 478 SmallVector<const Value *, 16> Worklist; 479 Worklist.push_back(Loc.Ptr); 480 do { 481 const Value *V = GetUnderlyingObject(Worklist.pop_back_val(), DL); 482 if (!Visited.insert(V).second) { 483 Visited.clear(); 484 return AAResultBase::pointsToConstantMemory(Loc, OrLocal); 485 } 486 487 // An alloca instruction defines local memory. 488 if (OrLocal && isa<AllocaInst>(V)) 489 continue; 490 491 // A global constant counts as local memory for our purposes. 492 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) { 493 // Note: this doesn't require GV to be "ODR" because it isn't legal for a 494 // global to be marked constant in some modules and non-constant in 495 // others. GV may even be a declaration, not a definition. 496 if (!GV->isConstant()) { 497 Visited.clear(); 498 return AAResultBase::pointsToConstantMemory(Loc, OrLocal); 499 } 500 continue; 501 } 502 503 // If both select values point to local memory, then so does the select. 504 if (const SelectInst *SI = dyn_cast<SelectInst>(V)) { 505 Worklist.push_back(SI->getTrueValue()); 506 Worklist.push_back(SI->getFalseValue()); 507 continue; 508 } 509 510 // If all values incoming to a phi node point to local memory, then so does 511 // the phi. 512 if (const PHINode *PN = dyn_cast<PHINode>(V)) { 513 // Don't bother inspecting phi nodes with many operands. 514 if (PN->getNumIncomingValues() > MaxLookup) { 515 Visited.clear(); 516 return AAResultBase::pointsToConstantMemory(Loc, OrLocal); 517 } 518 for (Value *IncValue : PN->incoming_values()) 519 Worklist.push_back(IncValue); 520 continue; 521 } 522 523 // Otherwise be conservative. 524 Visited.clear(); 525 return AAResultBase::pointsToConstantMemory(Loc, OrLocal); 526 527 } while (!Worklist.empty() && --MaxLookup); 528 529 Visited.clear(); 530 return Worklist.empty(); 531} 532 533// FIXME: This code is duplicated with MemoryLocation and should be hoisted to 534// some common utility location. 535static bool isMemsetPattern16(const Function *MS, 536 const TargetLibraryInfo &TLI) { 537 if (TLI.has(LibFunc::memset_pattern16) && 538 MS->getName() == "memset_pattern16") { 539 FunctionType *MemsetType = MS->getFunctionType(); 540 if (!MemsetType->isVarArg() && MemsetType->getNumParams() == 3 && 541 isa<PointerType>(MemsetType->getParamType(0)) && 542 isa<PointerType>(MemsetType->getParamType(1)) && 543 isa<IntegerType>(MemsetType->getParamType(2))) 544 return true; 545 } 546 return false; 547} 548 549/// Returns the behavior when calling the given call site. 550FunctionModRefBehavior BasicAAResult::getModRefBehavior(ImmutableCallSite CS) { 551 if (CS.doesNotAccessMemory()) 552 // Can't do better than this. 553 return FMRB_DoesNotAccessMemory; 554 555 FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior; 556 557 // If the callsite knows it only reads memory, don't return worse 558 // than that. 559 if (CS.onlyReadsMemory()) 560 Min = FMRB_OnlyReadsMemory; 561 562 if (CS.onlyAccessesArgMemory()) 563 Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesArgumentPointees); 564 565 // The AAResultBase base class has some smarts, lets use them. 566 return FunctionModRefBehavior(AAResultBase::getModRefBehavior(CS) & Min); 567} 568 569/// Returns the behavior when calling the given function. For use when the call 570/// site is not known. 571FunctionModRefBehavior BasicAAResult::getModRefBehavior(const Function *F) { 572 // If the function declares it doesn't access memory, we can't do better. 573 if (F->doesNotAccessMemory()) 574 return FMRB_DoesNotAccessMemory; 575 576 FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior; 577 578 // If the function declares it only reads memory, go with that. 579 if (F->onlyReadsMemory()) 580 Min = FMRB_OnlyReadsMemory; 581 582 if (F->onlyAccessesArgMemory()) 583 Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesArgumentPointees); 584 585 // Otherwise be conservative. 586 return FunctionModRefBehavior(AAResultBase::getModRefBehavior(F) & Min); 587} 588 589/// Returns true if this is a writeonly (i.e Mod only) parameter. Currently, 590/// we don't have a writeonly attribute, so this only knows about builtin 591/// intrinsics and target library functions. We could consider adding a 592/// writeonly attribute in the future and moving all of these facts to either 593/// Intrinsics.td or InferFunctionAttr.cpp 594static bool isWriteOnlyParam(ImmutableCallSite CS, unsigned ArgIdx, 595 const TargetLibraryInfo &TLI) { 596 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) 597 switch (II->getIntrinsicID()) { 598 default: 599 break; 600 case Intrinsic::memset: 601 case Intrinsic::memcpy: 602 case Intrinsic::memmove: 603 // We don't currently have a writeonly attribute. All other properties 604 // of these intrinsics are nicely described via attributes in 605 // Intrinsics.td and handled generically. 606 if (ArgIdx == 0) 607 return true; 608 } 609 610 // We can bound the aliasing properties of memset_pattern16 just as we can 611 // for memcpy/memset. This is particularly important because the 612 // LoopIdiomRecognizer likes to turn loops into calls to memset_pattern16 613 // whenever possible. Note that all but the missing writeonly attribute are 614 // handled via InferFunctionAttr. 615 if (CS.getCalledFunction() && isMemsetPattern16(CS.getCalledFunction(), TLI)) 616 if (ArgIdx == 0) 617 return true; 618 619 // TODO: memset_pattern4, memset_pattern8 620 // TODO: _chk variants 621 // TODO: strcmp, strcpy 622 623 return false; 624} 625 626ModRefInfo BasicAAResult::getArgModRefInfo(ImmutableCallSite CS, 627 unsigned ArgIdx) { 628 629 // Emulate the missing writeonly attribute by checking for known builtin 630 // intrinsics and target library functions. 631 if (isWriteOnlyParam(CS, ArgIdx, TLI)) 632 return MRI_Mod; 633 634 if (CS.paramHasAttr(ArgIdx + 1, Attribute::ReadOnly)) 635 return MRI_Ref; 636 637 if (CS.paramHasAttr(ArgIdx + 1, Attribute::ReadNone)) 638 return MRI_NoModRef; 639 640 return AAResultBase::getArgModRefInfo(CS, ArgIdx); 641} 642 643static bool isAssumeIntrinsic(ImmutableCallSite CS) { 644 const IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction()); 645 return II && II->getIntrinsicID() == Intrinsic::assume; 646} 647 648#ifndef NDEBUG 649static const Function *getParent(const Value *V) { 650 if (const Instruction *inst = dyn_cast<Instruction>(V)) 651 return inst->getParent()->getParent(); 652 653 if (const Argument *arg = dyn_cast<Argument>(V)) 654 return arg->getParent(); 655 656 return nullptr; 657} 658 659static bool notDifferentParent(const Value *O1, const Value *O2) { 660 661 const Function *F1 = getParent(O1); 662 const Function *F2 = getParent(O2); 663 664 return !F1 || !F2 || F1 == F2; 665} 666#endif 667 668AliasResult BasicAAResult::alias(const MemoryLocation &LocA, 669 const MemoryLocation &LocB) { 670 assert(notDifferentParent(LocA.Ptr, LocB.Ptr) && 671 "BasicAliasAnalysis doesn't support interprocedural queries."); 672 673 // If we have a directly cached entry for these locations, we have recursed 674 // through this once, so just return the cached results. Notably, when this 675 // happens, we don't clear the cache. 676 auto CacheIt = AliasCache.find(LocPair(LocA, LocB)); 677 if (CacheIt != AliasCache.end()) 678 return CacheIt->second; 679 680 AliasResult Alias = aliasCheck(LocA.Ptr, LocA.Size, LocA.AATags, LocB.Ptr, 681 LocB.Size, LocB.AATags); 682 // AliasCache rarely has more than 1 or 2 elements, always use 683 // shrink_and_clear so it quickly returns to the inline capacity of the 684 // SmallDenseMap if it ever grows larger. 685 // FIXME: This should really be shrink_to_inline_capacity_and_clear(). 686 AliasCache.shrink_and_clear(); 687 VisitedPhiBBs.clear(); 688 return Alias; 689} 690 691/// Checks to see if the specified callsite can clobber the specified memory 692/// object. 693/// 694/// Since we only look at local properties of this function, we really can't 695/// say much about this query. We do, however, use simple "address taken" 696/// analysis on local objects. 697ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS, 698 const MemoryLocation &Loc) { 699 assert(notDifferentParent(CS.getInstruction(), Loc.Ptr) && 700 "AliasAnalysis query involving multiple functions!"); 701 702 const Value *Object = GetUnderlyingObject(Loc.Ptr, DL); 703 704 // If this is a tail call and Loc.Ptr points to a stack location, we know that 705 // the tail call cannot access or modify the local stack. 706 // We cannot exclude byval arguments here; these belong to the caller of 707 // the current function not to the current function, and a tail callee 708 // may reference them. 709 if (isa<AllocaInst>(Object)) 710 if (const CallInst *CI = dyn_cast<CallInst>(CS.getInstruction())) 711 if (CI->isTailCall()) 712 return MRI_NoModRef; 713 714 // If the pointer is to a locally allocated object that does not escape, 715 // then the call can not mod/ref the pointer unless the call takes the pointer 716 // as an argument, and itself doesn't capture it. 717 if (!isa<Constant>(Object) && CS.getInstruction() != Object && 718 isNonEscapingLocalObject(Object)) { 719 bool PassedAsArg = false; 720 unsigned ArgNo = 0; 721 for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 722 CI != CE; ++CI, ++ArgNo) { 723 // Only look at the no-capture or byval pointer arguments. If this 724 // pointer were passed to arguments that were neither of these, then it 725 // couldn't be no-capture. 726 if (!(*CI)->getType()->isPointerTy() || 727 (!CS.doesNotCapture(ArgNo) && !CS.isByValArgument(ArgNo))) 728 continue; 729 730 // If this is a no-capture pointer argument, see if we can tell that it 731 // is impossible to alias the pointer we're checking. If not, we have to 732 // assume that the call could touch the pointer, even though it doesn't 733 // escape. 734 AliasResult AR = 735 getBestAAResults().alias(MemoryLocation(*CI), MemoryLocation(Object)); 736 if (AR) { 737 PassedAsArg = true; 738 break; 739 } 740 } 741 742 if (!PassedAsArg) 743 return MRI_NoModRef; 744 } 745 746 // While the assume intrinsic is marked as arbitrarily writing so that 747 // proper control dependencies will be maintained, it never aliases any 748 // particular memory location. 749 if (isAssumeIntrinsic(CS)) 750 return MRI_NoModRef; 751 752 // The AAResultBase base class has some smarts, lets use them. 753 return AAResultBase::getModRefInfo(CS, Loc); 754} 755 756ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS1, 757 ImmutableCallSite CS2) { 758 // While the assume intrinsic is marked as arbitrarily writing so that 759 // proper control dependencies will be maintained, it never aliases any 760 // particular memory location. 761 if (isAssumeIntrinsic(CS1) || isAssumeIntrinsic(CS2)) 762 return MRI_NoModRef; 763 764 // The AAResultBase base class has some smarts, lets use them. 765 return AAResultBase::getModRefInfo(CS1, CS2); 766} 767 768/// Provide ad-hoc rules to disambiguate accesses through two GEP operators, 769/// both having the exact same pointer operand. 770static AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1, 771 uint64_t V1Size, 772 const GEPOperator *GEP2, 773 uint64_t V2Size, 774 const DataLayout &DL) { 775 776 assert(GEP1->getPointerOperand() == GEP2->getPointerOperand() && 777 "Expected GEPs with the same pointer operand"); 778 779 // Try to determine whether GEP1 and GEP2 index through arrays, into structs, 780 // such that the struct field accesses provably cannot alias. 781 // We also need at least two indices (the pointer, and the struct field). 782 if (GEP1->getNumIndices() != GEP2->getNumIndices() || 783 GEP1->getNumIndices() < 2) 784 return MayAlias; 785 786 // If we don't know the size of the accesses through both GEPs, we can't 787 // determine whether the struct fields accessed can't alias. 788 if (V1Size == MemoryLocation::UnknownSize || 789 V2Size == MemoryLocation::UnknownSize) 790 return MayAlias; 791 792 ConstantInt *C1 = 793 dyn_cast<ConstantInt>(GEP1->getOperand(GEP1->getNumOperands() - 1)); 794 ConstantInt *C2 = 795 dyn_cast<ConstantInt>(GEP2->getOperand(GEP2->getNumOperands() - 1)); 796 797 // If the last (struct) indices are constants and are equal, the other indices 798 // might be also be dynamically equal, so the GEPs can alias. 799 if (C1 && C2 && C1 == C2) 800 return MayAlias; 801 802 // Find the last-indexed type of the GEP, i.e., the type you'd get if 803 // you stripped the last index. 804 // On the way, look at each indexed type. If there's something other 805 // than an array, different indices can lead to different final types. 806 SmallVector<Value *, 8> IntermediateIndices; 807 808 // Insert the first index; we don't need to check the type indexed 809 // through it as it only drops the pointer indirection. 810 assert(GEP1->getNumIndices() > 1 && "Not enough GEP indices to examine"); 811 IntermediateIndices.push_back(GEP1->getOperand(1)); 812 813 // Insert all the remaining indices but the last one. 814 // Also, check that they all index through arrays. 815 for (unsigned i = 1, e = GEP1->getNumIndices() - 1; i != e; ++i) { 816 if (!isa<ArrayType>(GetElementPtrInst::getIndexedType( 817 GEP1->getSourceElementType(), IntermediateIndices))) 818 return MayAlias; 819 IntermediateIndices.push_back(GEP1->getOperand(i + 1)); 820 } 821 822 auto *Ty = GetElementPtrInst::getIndexedType( 823 GEP1->getSourceElementType(), IntermediateIndices); 824 StructType *LastIndexedStruct = dyn_cast<StructType>(Ty); 825 826 if (isa<SequentialType>(Ty)) { 827 // We know that: 828 // - both GEPs begin indexing from the exact same pointer; 829 // - the last indices in both GEPs are constants, indexing into a sequential 830 // type (array or pointer); 831 // - both GEPs only index through arrays prior to that. 832 // 833 // Because array indices greater than the number of elements are valid in 834 // GEPs, unless we know the intermediate indices are identical between 835 // GEP1 and GEP2 we cannot guarantee that the last indexed arrays don't 836 // partially overlap. We also need to check that the loaded size matches 837 // the element size, otherwise we could still have overlap. 838 const uint64_t ElementSize = 839 DL.getTypeStoreSize(cast<SequentialType>(Ty)->getElementType()); 840 if (V1Size != ElementSize || V2Size != ElementSize) 841 return MayAlias; 842 843 for (unsigned i = 0, e = GEP1->getNumIndices() - 1; i != e; ++i) 844 if (GEP1->getOperand(i + 1) != GEP2->getOperand(i + 1)) 845 return MayAlias; 846 847 // Now we know that the array/pointer that GEP1 indexes into and that 848 // that GEP2 indexes into must either precisely overlap or be disjoint. 849 // Because they cannot partially overlap and because fields in an array 850 // cannot overlap, if we can prove the final indices are different between 851 // GEP1 and GEP2, we can conclude GEP1 and GEP2 don't alias. 852 853 // If the last indices are constants, we've already checked they don't 854 // equal each other so we can exit early. 855 if (C1 && C2) 856 return NoAlias; 857 if (isKnownNonEqual(GEP1->getOperand(GEP1->getNumOperands() - 1), 858 GEP2->getOperand(GEP2->getNumOperands() - 1), 859 DL)) 860 return NoAlias; 861 return MayAlias; 862 } else if (!LastIndexedStruct || !C1 || !C2) { 863 return MayAlias; 864 } 865 866 // We know that: 867 // - both GEPs begin indexing from the exact same pointer; 868 // - the last indices in both GEPs are constants, indexing into a struct; 869 // - said indices are different, hence, the pointed-to fields are different; 870 // - both GEPs only index through arrays prior to that. 871 // 872 // This lets us determine that the struct that GEP1 indexes into and the 873 // struct that GEP2 indexes into must either precisely overlap or be 874 // completely disjoint. Because they cannot partially overlap, indexing into 875 // different non-overlapping fields of the struct will never alias. 876 877 // Therefore, the only remaining thing needed to show that both GEPs can't 878 // alias is that the fields are not overlapping. 879 const StructLayout *SL = DL.getStructLayout(LastIndexedStruct); 880 const uint64_t StructSize = SL->getSizeInBytes(); 881 const uint64_t V1Off = SL->getElementOffset(C1->getZExtValue()); 882 const uint64_t V2Off = SL->getElementOffset(C2->getZExtValue()); 883 884 auto EltsDontOverlap = [StructSize](uint64_t V1Off, uint64_t V1Size, 885 uint64_t V2Off, uint64_t V2Size) { 886 return V1Off < V2Off && V1Off + V1Size <= V2Off && 887 ((V2Off + V2Size <= StructSize) || 888 (V2Off + V2Size - StructSize <= V1Off)); 889 }; 890 891 if (EltsDontOverlap(V1Off, V1Size, V2Off, V2Size) || 892 EltsDontOverlap(V2Off, V2Size, V1Off, V1Size)) 893 return NoAlias; 894 895 return MayAlias; 896} 897 898/// Provides a bunch of ad-hoc rules to disambiguate a GEP instruction against 899/// another pointer. 900/// 901/// We know that V1 is a GEP, but we don't know anything about V2. 902/// UnderlyingV1 is GetUnderlyingObject(GEP1, DL), UnderlyingV2 is the same for 903/// V2. 904AliasResult BasicAAResult::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size, 905 const AAMDNodes &V1AAInfo, const Value *V2, 906 uint64_t V2Size, const AAMDNodes &V2AAInfo, 907 const Value *UnderlyingV1, 908 const Value *UnderlyingV2) { 909 int64_t GEP1BaseOffset; 910 bool GEP1MaxLookupReached; 911 SmallVector<VariableGEPIndex, 4> GEP1VariableIndices; 912 913 // If we have two gep instructions with must-alias or not-alias'ing base 914 // pointers, figure out if the indexes to the GEP tell us anything about the 915 // derived pointer. 916 if (const GEPOperator *GEP2 = dyn_cast<GEPOperator>(V2)) { 917 // Do the base pointers alias? 918 AliasResult BaseAlias = 919 aliasCheck(UnderlyingV1, MemoryLocation::UnknownSize, AAMDNodes(), 920 UnderlyingV2, MemoryLocation::UnknownSize, AAMDNodes()); 921 922 // Check for geps of non-aliasing underlying pointers where the offsets are 923 // identical. 924 if ((BaseAlias == MayAlias) && V1Size == V2Size) { 925 // Do the base pointers alias assuming type and size. 926 AliasResult PreciseBaseAlias = aliasCheck(UnderlyingV1, V1Size, V1AAInfo, 927 UnderlyingV2, V2Size, V2AAInfo); 928 if (PreciseBaseAlias == NoAlias) { 929 // See if the computed offset from the common pointer tells us about the 930 // relation of the resulting pointer. 931 int64_t GEP2BaseOffset; 932 bool GEP2MaxLookupReached; 933 SmallVector<VariableGEPIndex, 4> GEP2VariableIndices; 934 const Value *GEP2BasePtr = 935 DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, 936 GEP2MaxLookupReached, DL, &AC, DT); 937 const Value *GEP1BasePtr = 938 DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, 939 GEP1MaxLookupReached, DL, &AC, DT); 940 // DecomposeGEPExpression and GetUnderlyingObject should return the 941 // same result except when DecomposeGEPExpression has no DataLayout. 942 // FIXME: They always have a DataLayout so this should become an 943 // assert. 944 if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) { 945 return MayAlias; 946 } 947 // If the max search depth is reached the result is undefined 948 if (GEP2MaxLookupReached || GEP1MaxLookupReached) 949 return MayAlias; 950 951 // Same offsets. 952 if (GEP1BaseOffset == GEP2BaseOffset && 953 GEP1VariableIndices == GEP2VariableIndices) 954 return NoAlias; 955 GEP1VariableIndices.clear(); 956 } 957 } 958 959 // If we get a No or May, then return it immediately, no amount of analysis 960 // will improve this situation. 961 if (BaseAlias != MustAlias) 962 return BaseAlias; 963 964 // Otherwise, we have a MustAlias. Since the base pointers alias each other 965 // exactly, see if the computed offset from the common pointer tells us 966 // about the relation of the resulting pointer. 967 const Value *GEP1BasePtr = 968 DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, 969 GEP1MaxLookupReached, DL, &AC, DT); 970 971 int64_t GEP2BaseOffset; 972 bool GEP2MaxLookupReached; 973 SmallVector<VariableGEPIndex, 4> GEP2VariableIndices; 974 const Value *GEP2BasePtr = 975 DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, 976 GEP2MaxLookupReached, DL, &AC, DT); 977 978 // DecomposeGEPExpression and GetUnderlyingObject should return the 979 // same result except when DecomposeGEPExpression has no DataLayout. 980 // FIXME: They always have a DataLayout so this should become an assert. 981 if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) { 982 return MayAlias; 983 } 984 985 // If we know the two GEPs are based off of the exact same pointer (and not 986 // just the same underlying object), see if that tells us anything about 987 // the resulting pointers. 988 if (GEP1->getPointerOperand() == GEP2->getPointerOperand()) { 989 AliasResult R = aliasSameBasePointerGEPs(GEP1, V1Size, GEP2, V2Size, DL); 990 // If we couldn't find anything interesting, don't abandon just yet. 991 if (R != MayAlias) 992 return R; 993 } 994 995 // If the max search depth is reached the result is undefined 996 if (GEP2MaxLookupReached || GEP1MaxLookupReached) 997 return MayAlias; 998 999 // Subtract the GEP2 pointer from the GEP1 pointer to find out their 1000 // symbolic difference. 1001 GEP1BaseOffset -= GEP2BaseOffset; 1002 GetIndexDifference(GEP1VariableIndices, GEP2VariableIndices); 1003 1004 } else { 1005 // Check to see if these two pointers are related by the getelementptr 1006 // instruction. If one pointer is a GEP with a non-zero index of the other 1007 // pointer, we know they cannot alias. 1008 1009 // If both accesses are unknown size, we can't do anything useful here. 1010 if (V1Size == MemoryLocation::UnknownSize && 1011 V2Size == MemoryLocation::UnknownSize) 1012 return MayAlias; 1013 1014 AliasResult R = aliasCheck(UnderlyingV1, MemoryLocation::UnknownSize, 1015 AAMDNodes(), V2, V2Size, V2AAInfo); 1016 if (R != MustAlias) 1017 // If V2 may alias GEP base pointer, conservatively returns MayAlias. 1018 // If V2 is known not to alias GEP base pointer, then the two values 1019 // cannot alias per GEP semantics: "A pointer value formed from a 1020 // getelementptr instruction is associated with the addresses associated 1021 // with the first operand of the getelementptr". 1022 return R; 1023 1024 const Value *GEP1BasePtr = 1025 DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, 1026 GEP1MaxLookupReached, DL, &AC, DT); 1027 1028 // DecomposeGEPExpression and GetUnderlyingObject should return the 1029 // same result except when DecomposeGEPExpression has no DataLayout. 1030 // FIXME: They always have a DataLayout so this should become an assert. 1031 if (GEP1BasePtr != UnderlyingV1) { 1032 return MayAlias; 1033 } 1034 // If the max search depth is reached the result is undefined 1035 if (GEP1MaxLookupReached) 1036 return MayAlias; 1037 } 1038 1039 // In the two GEP Case, if there is no difference in the offsets of the 1040 // computed pointers, the resultant pointers are a must alias. This 1041 // hapens when we have two lexically identical GEP's (for example). 1042 // 1043 // In the other case, if we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 1044 // must aliases the GEP, the end result is a must alias also. 1045 if (GEP1BaseOffset == 0 && GEP1VariableIndices.empty()) 1046 return MustAlias; 1047 1048 // If there is a constant difference between the pointers, but the difference 1049 // is less than the size of the associated memory object, then we know 1050 // that the objects are partially overlapping. If the difference is 1051 // greater, we know they do not overlap. 1052 if (GEP1BaseOffset != 0 && GEP1VariableIndices.empty()) { 1053 if (GEP1BaseOffset >= 0) { 1054 if (V2Size != MemoryLocation::UnknownSize) { 1055 if ((uint64_t)GEP1BaseOffset < V2Size) 1056 return PartialAlias; 1057 return NoAlias; 1058 } 1059 } else { 1060 // We have the situation where: 1061 // + + 1062 // | BaseOffset | 1063 // ---------------->| 1064 // |-->V1Size |-------> V2Size 1065 // GEP1 V2 1066 // We need to know that V2Size is not unknown, otherwise we might have 1067 // stripped a gep with negative index ('gep <ptr>, -1, ...). 1068 if (V1Size != MemoryLocation::UnknownSize && 1069 V2Size != MemoryLocation::UnknownSize) { 1070 if (-(uint64_t)GEP1BaseOffset < V1Size) 1071 return PartialAlias; 1072 return NoAlias; 1073 } 1074 } 1075 } 1076 1077 if (!GEP1VariableIndices.empty()) { 1078 uint64_t Modulo = 0; 1079 bool AllPositive = true; 1080 for (unsigned i = 0, e = GEP1VariableIndices.size(); i != e; ++i) { 1081 1082 // Try to distinguish something like &A[i][1] against &A[42][0]. 1083 // Grab the least significant bit set in any of the scales. We 1084 // don't need std::abs here (even if the scale's negative) as we'll 1085 // be ^'ing Modulo with itself later. 1086 Modulo |= (uint64_t)GEP1VariableIndices[i].Scale; 1087 1088 if (AllPositive) { 1089 // If the Value could change between cycles, then any reasoning about 1090 // the Value this cycle may not hold in the next cycle. We'll just 1091 // give up if we can't determine conditions that hold for every cycle: 1092 const Value *V = GEP1VariableIndices[i].V; 1093 1094 bool SignKnownZero, SignKnownOne; 1095 ComputeSignBit(const_cast<Value *>(V), SignKnownZero, SignKnownOne, DL, 1096 0, &AC, nullptr, DT); 1097 1098 // Zero-extension widens the variable, and so forces the sign 1099 // bit to zero. 1100 bool IsZExt = GEP1VariableIndices[i].ZExtBits > 0 || isa<ZExtInst>(V); 1101 SignKnownZero |= IsZExt; 1102 SignKnownOne &= !IsZExt; 1103 1104 // If the variable begins with a zero then we know it's 1105 // positive, regardless of whether the value is signed or 1106 // unsigned. 1107 int64_t Scale = GEP1VariableIndices[i].Scale; 1108 AllPositive = 1109 (SignKnownZero && Scale >= 0) || (SignKnownOne && Scale < 0); 1110 } 1111 } 1112 1113 Modulo = Modulo ^ (Modulo & (Modulo - 1)); 1114 1115 // We can compute the difference between the two addresses 1116 // mod Modulo. Check whether that difference guarantees that the 1117 // two locations do not alias. 1118 uint64_t ModOffset = (uint64_t)GEP1BaseOffset & (Modulo - 1); 1119 if (V1Size != MemoryLocation::UnknownSize && 1120 V2Size != MemoryLocation::UnknownSize && ModOffset >= V2Size && 1121 V1Size <= Modulo - ModOffset) 1122 return NoAlias; 1123 1124 // If we know all the variables are positive, then GEP1 >= GEP1BasePtr. 1125 // If GEP1BasePtr > V2 (GEP1BaseOffset > 0) then we know the pointers 1126 // don't alias if V2Size can fit in the gap between V2 and GEP1BasePtr. 1127 if (AllPositive && GEP1BaseOffset > 0 && V2Size <= (uint64_t)GEP1BaseOffset) 1128 return NoAlias; 1129 1130 if (constantOffsetHeuristic(GEP1VariableIndices, V1Size, V2Size, 1131 GEP1BaseOffset, &AC, DT)) 1132 return NoAlias; 1133 } 1134 1135 // Statically, we can see that the base objects are the same, but the 1136 // pointers have dynamic offsets which we can't resolve. And none of our 1137 // little tricks above worked. 1138 // 1139 // TODO: Returning PartialAlias instead of MayAlias is a mild hack; the 1140 // practical effect of this is protecting TBAA in the case of dynamic 1141 // indices into arrays of unions or malloc'd memory. 1142 return PartialAlias; 1143} 1144 1145static AliasResult MergeAliasResults(AliasResult A, AliasResult B) { 1146 // If the results agree, take it. 1147 if (A == B) 1148 return A; 1149 // A mix of PartialAlias and MustAlias is PartialAlias. 1150 if ((A == PartialAlias && B == MustAlias) || 1151 (B == PartialAlias && A == MustAlias)) 1152 return PartialAlias; 1153 // Otherwise, we don't know anything. 1154 return MayAlias; 1155} 1156 1157/// Provides a bunch of ad-hoc rules to disambiguate a Select instruction 1158/// against another. 1159AliasResult BasicAAResult::aliasSelect(const SelectInst *SI, uint64_t SISize, 1160 const AAMDNodes &SIAAInfo, 1161 const Value *V2, uint64_t V2Size, 1162 const AAMDNodes &V2AAInfo) { 1163 // If the values are Selects with the same condition, we can do a more precise 1164 // check: just check for aliases between the values on corresponding arms. 1165 if (const SelectInst *SI2 = dyn_cast<SelectInst>(V2)) 1166 if (SI->getCondition() == SI2->getCondition()) { 1167 AliasResult Alias = aliasCheck(SI->getTrueValue(), SISize, SIAAInfo, 1168 SI2->getTrueValue(), V2Size, V2AAInfo); 1169 if (Alias == MayAlias) 1170 return MayAlias; 1171 AliasResult ThisAlias = 1172 aliasCheck(SI->getFalseValue(), SISize, SIAAInfo, 1173 SI2->getFalseValue(), V2Size, V2AAInfo); 1174 return MergeAliasResults(ThisAlias, Alias); 1175 } 1176 1177 // If both arms of the Select node NoAlias or MustAlias V2, then returns 1178 // NoAlias / MustAlias. Otherwise, returns MayAlias. 1179 AliasResult Alias = 1180 aliasCheck(V2, V2Size, V2AAInfo, SI->getTrueValue(), SISize, SIAAInfo); 1181 if (Alias == MayAlias) 1182 return MayAlias; 1183 1184 AliasResult ThisAlias = 1185 aliasCheck(V2, V2Size, V2AAInfo, SI->getFalseValue(), SISize, SIAAInfo); 1186 return MergeAliasResults(ThisAlias, Alias); 1187} 1188 1189/// Provide a bunch of ad-hoc rules to disambiguate a PHI instruction against 1190/// another. 1191AliasResult BasicAAResult::aliasPHI(const PHINode *PN, uint64_t PNSize, 1192 const AAMDNodes &PNAAInfo, const Value *V2, 1193 uint64_t V2Size, 1194 const AAMDNodes &V2AAInfo) { 1195 // Track phi nodes we have visited. We use this information when we determine 1196 // value equivalence. 1197 VisitedPhiBBs.insert(PN->getParent()); 1198 1199 // If the values are PHIs in the same block, we can do a more precise 1200 // as well as efficient check: just check for aliases between the values 1201 // on corresponding edges. 1202 if (const PHINode *PN2 = dyn_cast<PHINode>(V2)) 1203 if (PN2->getParent() == PN->getParent()) { 1204 LocPair Locs(MemoryLocation(PN, PNSize, PNAAInfo), 1205 MemoryLocation(V2, V2Size, V2AAInfo)); 1206 if (PN > V2) 1207 std::swap(Locs.first, Locs.second); 1208 // Analyse the PHIs' inputs under the assumption that the PHIs are 1209 // NoAlias. 1210 // If the PHIs are May/MustAlias there must be (recursively) an input 1211 // operand from outside the PHIs' cycle that is MayAlias/MustAlias or 1212 // there must be an operation on the PHIs within the PHIs' value cycle 1213 // that causes a MayAlias. 1214 // Pretend the phis do not alias. 1215 AliasResult Alias = NoAlias; 1216 assert(AliasCache.count(Locs) && 1217 "There must exist an entry for the phi node"); 1218 AliasResult OrigAliasResult = AliasCache[Locs]; 1219 AliasCache[Locs] = NoAlias; 1220 1221 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 1222 AliasResult ThisAlias = 1223 aliasCheck(PN->getIncomingValue(i), PNSize, PNAAInfo, 1224 PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)), 1225 V2Size, V2AAInfo); 1226 Alias = MergeAliasResults(ThisAlias, Alias); 1227 if (Alias == MayAlias) 1228 break; 1229 } 1230 1231 // Reset if speculation failed. 1232 if (Alias != NoAlias) 1233 AliasCache[Locs] = OrigAliasResult; 1234 1235 return Alias; 1236 } 1237 1238 SmallPtrSet<Value *, 4> UniqueSrc; 1239 SmallVector<Value *, 4> V1Srcs; 1240 bool isRecursive = false; 1241 for (Value *PV1 : PN->incoming_values()) { 1242 if (isa<PHINode>(PV1)) 1243 // If any of the source itself is a PHI, return MayAlias conservatively 1244 // to avoid compile time explosion. The worst possible case is if both 1245 // sides are PHI nodes. In which case, this is O(m x n) time where 'm' 1246 // and 'n' are the number of PHI sources. 1247 return MayAlias; 1248 1249 if (EnableRecPhiAnalysis) 1250 if (GEPOperator *PV1GEP = dyn_cast<GEPOperator>(PV1)) { 1251 // Check whether the incoming value is a GEP that advances the pointer 1252 // result of this PHI node (e.g. in a loop). If this is the case, we 1253 // would recurse and always get a MayAlias. Handle this case specially 1254 // below. 1255 if (PV1GEP->getPointerOperand() == PN && PV1GEP->getNumIndices() == 1 && 1256 isa<ConstantInt>(PV1GEP->idx_begin())) { 1257 isRecursive = true; 1258 continue; 1259 } 1260 } 1261 1262 if (UniqueSrc.insert(PV1).second) 1263 V1Srcs.push_back(PV1); 1264 } 1265 1266 // If this PHI node is recursive, set the size of the accessed memory to 1267 // unknown to represent all the possible values the GEP could advance the 1268 // pointer to. 1269 if (isRecursive) 1270 PNSize = MemoryLocation::UnknownSize; 1271 1272 AliasResult Alias = 1273 aliasCheck(V2, V2Size, V2AAInfo, V1Srcs[0], PNSize, PNAAInfo); 1274 1275 // Early exit if the check of the first PHI source against V2 is MayAlias. 1276 // Other results are not possible. 1277 if (Alias == MayAlias) 1278 return MayAlias; 1279 1280 // If all sources of the PHI node NoAlias or MustAlias V2, then returns 1281 // NoAlias / MustAlias. Otherwise, returns MayAlias. 1282 for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) { 1283 Value *V = V1Srcs[i]; 1284 1285 AliasResult ThisAlias = 1286 aliasCheck(V2, V2Size, V2AAInfo, V, PNSize, PNAAInfo); 1287 Alias = MergeAliasResults(ThisAlias, Alias); 1288 if (Alias == MayAlias) 1289 break; 1290 } 1291 1292 return Alias; 1293} 1294 1295/// Provides a bunch of ad-hoc rules to disambiguate in common cases, such as 1296/// array references. 1297AliasResult BasicAAResult::aliasCheck(const Value *V1, uint64_t V1Size, 1298 AAMDNodes V1AAInfo, const Value *V2, 1299 uint64_t V2Size, AAMDNodes V2AAInfo) { 1300 // If either of the memory references is empty, it doesn't matter what the 1301 // pointer values are. 1302 if (V1Size == 0 || V2Size == 0) 1303 return NoAlias; 1304 1305 // Strip off any casts if they exist. 1306 V1 = V1->stripPointerCasts(); 1307 V2 = V2->stripPointerCasts(); 1308 1309 // If V1 or V2 is undef, the result is NoAlias because we can always pick a 1310 // value for undef that aliases nothing in the program. 1311 if (isa<UndefValue>(V1) || isa<UndefValue>(V2)) 1312 return NoAlias; 1313 1314 // Are we checking for alias of the same value? 1315 // Because we look 'through' phi nodes we could look at "Value" pointers from 1316 // different iterations. We must therefore make sure that this is not the 1317 // case. The function isValueEqualInPotentialCycles ensures that this cannot 1318 // happen by looking at the visited phi nodes and making sure they cannot 1319 // reach the value. 1320 if (isValueEqualInPotentialCycles(V1, V2)) 1321 return MustAlias; 1322 1323 if (!V1->getType()->isPointerTy() || !V2->getType()->isPointerTy()) 1324 return NoAlias; // Scalars cannot alias each other 1325 1326 // Figure out what objects these things are pointing to if we can. 1327 const Value *O1 = GetUnderlyingObject(V1, DL, MaxLookupSearchDepth); 1328 const Value *O2 = GetUnderlyingObject(V2, DL, MaxLookupSearchDepth); 1329 1330 // Null values in the default address space don't point to any object, so they 1331 // don't alias any other pointer. 1332 if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O1)) 1333 if (CPN->getType()->getAddressSpace() == 0) 1334 return NoAlias; 1335 if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O2)) 1336 if (CPN->getType()->getAddressSpace() == 0) 1337 return NoAlias; 1338 1339 if (O1 != O2) { 1340 // If V1/V2 point to two different objects we know that we have no alias. 1341 if (isIdentifiedObject(O1) && isIdentifiedObject(O2)) 1342 return NoAlias; 1343 1344 // Constant pointers can't alias with non-const isIdentifiedObject objects. 1345 if ((isa<Constant>(O1) && isIdentifiedObject(O2) && !isa<Constant>(O2)) || 1346 (isa<Constant>(O2) && isIdentifiedObject(O1) && !isa<Constant>(O1))) 1347 return NoAlias; 1348 1349 // Function arguments can't alias with things that are known to be 1350 // unambigously identified at the function level. 1351 if ((isa<Argument>(O1) && isIdentifiedFunctionLocal(O2)) || 1352 (isa<Argument>(O2) && isIdentifiedFunctionLocal(O1))) 1353 return NoAlias; 1354 1355 // Most objects can't alias null. 1356 if ((isa<ConstantPointerNull>(O2) && isKnownNonNull(O1)) || 1357 (isa<ConstantPointerNull>(O1) && isKnownNonNull(O2))) 1358 return NoAlias; 1359 1360 // If one pointer is the result of a call/invoke or load and the other is a 1361 // non-escaping local object within the same function, then we know the 1362 // object couldn't escape to a point where the call could return it. 1363 // 1364 // Note that if the pointers are in different functions, there are a 1365 // variety of complications. A call with a nocapture argument may still 1366 // temporary store the nocapture argument's value in a temporary memory 1367 // location if that memory location doesn't escape. Or it may pass a 1368 // nocapture value to other functions as long as they don't capture it. 1369 if (isEscapeSource(O1) && isNonEscapingLocalObject(O2)) 1370 return NoAlias; 1371 if (isEscapeSource(O2) && isNonEscapingLocalObject(O1)) 1372 return NoAlias; 1373 } 1374 1375 // If the size of one access is larger than the entire object on the other 1376 // side, then we know such behavior is undefined and can assume no alias. 1377 if ((V1Size != MemoryLocation::UnknownSize && 1378 isObjectSmallerThan(O2, V1Size, DL, TLI)) || 1379 (V2Size != MemoryLocation::UnknownSize && 1380 isObjectSmallerThan(O1, V2Size, DL, TLI))) 1381 return NoAlias; 1382 1383 // Check the cache before climbing up use-def chains. This also terminates 1384 // otherwise infinitely recursive queries. 1385 LocPair Locs(MemoryLocation(V1, V1Size, V1AAInfo), 1386 MemoryLocation(V2, V2Size, V2AAInfo)); 1387 if (V1 > V2) 1388 std::swap(Locs.first, Locs.second); 1389 std::pair<AliasCacheTy::iterator, bool> Pair = 1390 AliasCache.insert(std::make_pair(Locs, MayAlias)); 1391 if (!Pair.second) 1392 return Pair.first->second; 1393 1394 // FIXME: This isn't aggressively handling alias(GEP, PHI) for example: if the 1395 // GEP can't simplify, we don't even look at the PHI cases. 1396 if (!isa<GEPOperator>(V1) && isa<GEPOperator>(V2)) { 1397 std::swap(V1, V2); 1398 std::swap(V1Size, V2Size); 1399 std::swap(O1, O2); 1400 std::swap(V1AAInfo, V2AAInfo); 1401 } 1402 if (const GEPOperator *GV1 = dyn_cast<GEPOperator>(V1)) { 1403 AliasResult Result = 1404 aliasGEP(GV1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, O1, O2); 1405 if (Result != MayAlias) 1406 return AliasCache[Locs] = Result; 1407 } 1408 1409 if (isa<PHINode>(V2) && !isa<PHINode>(V1)) { 1410 std::swap(V1, V2); 1411 std::swap(V1Size, V2Size); 1412 std::swap(V1AAInfo, V2AAInfo); 1413 } 1414 if (const PHINode *PN = dyn_cast<PHINode>(V1)) { 1415 AliasResult Result = aliasPHI(PN, V1Size, V1AAInfo, V2, V2Size, V2AAInfo); 1416 if (Result != MayAlias) 1417 return AliasCache[Locs] = Result; 1418 } 1419 1420 if (isa<SelectInst>(V2) && !isa<SelectInst>(V1)) { 1421 std::swap(V1, V2); 1422 std::swap(V1Size, V2Size); 1423 std::swap(V1AAInfo, V2AAInfo); 1424 } 1425 if (const SelectInst *S1 = dyn_cast<SelectInst>(V1)) { 1426 AliasResult Result = 1427 aliasSelect(S1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo); 1428 if (Result != MayAlias) 1429 return AliasCache[Locs] = Result; 1430 } 1431 1432 // If both pointers are pointing into the same object and one of them 1433 // accesses is accessing the entire object, then the accesses must 1434 // overlap in some way. 1435 if (O1 == O2) 1436 if ((V1Size != MemoryLocation::UnknownSize && 1437 isObjectSize(O1, V1Size, DL, TLI)) || 1438 (V2Size != MemoryLocation::UnknownSize && 1439 isObjectSize(O2, V2Size, DL, TLI))) 1440 return AliasCache[Locs] = PartialAlias; 1441 1442 // Recurse back into the best AA results we have, potentially with refined 1443 // memory locations. We have already ensured that BasicAA has a MayAlias 1444 // cache result for these, so any recursion back into BasicAA won't loop. 1445 AliasResult Result = getBestAAResults().alias(Locs.first, Locs.second); 1446 return AliasCache[Locs] = Result; 1447} 1448 1449/// Check whether two Values can be considered equivalent. 1450/// 1451/// In addition to pointer equivalence of \p V1 and \p V2 this checks whether 1452/// they can not be part of a cycle in the value graph by looking at all 1453/// visited phi nodes an making sure that the phis cannot reach the value. We 1454/// have to do this because we are looking through phi nodes (That is we say 1455/// noalias(V, phi(VA, VB)) if noalias(V, VA) and noalias(V, VB). 1456bool BasicAAResult::isValueEqualInPotentialCycles(const Value *V, 1457 const Value *V2) { 1458 if (V != V2) 1459 return false; 1460 1461 const Instruction *Inst = dyn_cast<Instruction>(V); 1462 if (!Inst) 1463 return true; 1464 1465 if (VisitedPhiBBs.empty()) 1466 return true; 1467 1468 if (VisitedPhiBBs.size() > MaxNumPhiBBsValueReachabilityCheck) 1469 return false; 1470 1471 // Make sure that the visited phis cannot reach the Value. This ensures that 1472 // the Values cannot come from different iterations of a potential cycle the 1473 // phi nodes could be involved in. 1474 for (auto *P : VisitedPhiBBs) 1475 if (isPotentiallyReachable(&P->front(), Inst, DT, LI)) 1476 return false; 1477 1478 return true; 1479} 1480 1481/// Computes the symbolic difference between two de-composed GEPs. 1482/// 1483/// Dest and Src are the variable indices from two decomposed GetElementPtr 1484/// instructions GEP1 and GEP2 which have common base pointers. 1485void BasicAAResult::GetIndexDifference( 1486 SmallVectorImpl<VariableGEPIndex> &Dest, 1487 const SmallVectorImpl<VariableGEPIndex> &Src) { 1488 if (Src.empty()) 1489 return; 1490 1491 for (unsigned i = 0, e = Src.size(); i != e; ++i) { 1492 const Value *V = Src[i].V; 1493 unsigned ZExtBits = Src[i].ZExtBits, SExtBits = Src[i].SExtBits; 1494 int64_t Scale = Src[i].Scale; 1495 1496 // Find V in Dest. This is N^2, but pointer indices almost never have more 1497 // than a few variable indexes. 1498 for (unsigned j = 0, e = Dest.size(); j != e; ++j) { 1499 if (!isValueEqualInPotentialCycles(Dest[j].V, V) || 1500 Dest[j].ZExtBits != ZExtBits || Dest[j].SExtBits != SExtBits) 1501 continue; 1502 1503 // If we found it, subtract off Scale V's from the entry in Dest. If it 1504 // goes to zero, remove the entry. 1505 if (Dest[j].Scale != Scale) 1506 Dest[j].Scale -= Scale; 1507 else 1508 Dest.erase(Dest.begin() + j); 1509 Scale = 0; 1510 break; 1511 } 1512 1513 // If we didn't consume this entry, add it to the end of the Dest list. 1514 if (Scale) { 1515 VariableGEPIndex Entry = {V, ZExtBits, SExtBits, -Scale}; 1516 Dest.push_back(Entry); 1517 } 1518 } 1519} 1520 1521bool BasicAAResult::constantOffsetHeuristic( 1522 const SmallVectorImpl<VariableGEPIndex> &VarIndices, uint64_t V1Size, 1523 uint64_t V2Size, int64_t BaseOffset, AssumptionCache *AC, 1524 DominatorTree *DT) { 1525 if (VarIndices.size() != 2 || V1Size == MemoryLocation::UnknownSize || 1526 V2Size == MemoryLocation::UnknownSize) 1527 return false; 1528 1529 const VariableGEPIndex &Var0 = VarIndices[0], &Var1 = VarIndices[1]; 1530 1531 if (Var0.ZExtBits != Var1.ZExtBits || Var0.SExtBits != Var1.SExtBits || 1532 Var0.Scale != -Var1.Scale) 1533 return false; 1534 1535 unsigned Width = Var1.V->getType()->getIntegerBitWidth(); 1536 1537 // We'll strip off the Extensions of Var0 and Var1 and do another round 1538 // of GetLinearExpression decomposition. In the example above, if Var0 1539 // is zext(%x + 1) we should get V1 == %x and V1Offset == 1. 1540 1541 APInt V0Scale(Width, 0), V0Offset(Width, 0), V1Scale(Width, 0), 1542 V1Offset(Width, 0); 1543 bool NSW = true, NUW = true; 1544 unsigned V0ZExtBits = 0, V0SExtBits = 0, V1ZExtBits = 0, V1SExtBits = 0; 1545 const Value *V0 = GetLinearExpression(Var0.V, V0Scale, V0Offset, V0ZExtBits, 1546 V0SExtBits, DL, 0, AC, DT, NSW, NUW); 1547 NSW = true, NUW = true; 1548 const Value *V1 = GetLinearExpression(Var1.V, V1Scale, V1Offset, V1ZExtBits, 1549 V1SExtBits, DL, 0, AC, DT, NSW, NUW); 1550 1551 if (V0Scale != V1Scale || V0ZExtBits != V1ZExtBits || 1552 V0SExtBits != V1SExtBits || !isValueEqualInPotentialCycles(V0, V1)) 1553 return false; 1554 1555 // We have a hit - Var0 and Var1 only differ by a constant offset! 1556 1557 // If we've been sext'ed then zext'd the maximum difference between Var0 and 1558 // Var1 is possible to calculate, but we're just interested in the absolute 1559 // minimum difference between the two. The minimum distance may occur due to 1560 // wrapping; consider "add i3 %i, 5": if %i == 7 then 7 + 5 mod 8 == 4, and so 1561 // the minimum distance between %i and %i + 5 is 3. 1562 APInt MinDiff = V0Offset - V1Offset, Wrapped = -MinDiff; 1563 MinDiff = APIntOps::umin(MinDiff, Wrapped); 1564 uint64_t MinDiffBytes = MinDiff.getZExtValue() * std::abs(Var0.Scale); 1565 1566 // We can't definitely say whether GEP1 is before or after V2 due to wrapping 1567 // arithmetic (i.e. for some values of GEP1 and V2 GEP1 < V2, and for other 1568 // values GEP1 > V2). We'll therefore only declare NoAlias if both V1Size and 1569 // V2Size can fit in the MinDiffBytes gap. 1570 return V1Size + std::abs(BaseOffset) <= MinDiffBytes && 1571 V2Size + std::abs(BaseOffset) <= MinDiffBytes; 1572} 1573 1574//===----------------------------------------------------------------------===// 1575// BasicAliasAnalysis Pass 1576//===----------------------------------------------------------------------===// 1577 1578char BasicAA::PassID; 1579 1580BasicAAResult BasicAA::run(Function &F, AnalysisManager<Function> *AM) { 1581 return BasicAAResult(F.getParent()->getDataLayout(), 1582 AM->getResult<TargetLibraryAnalysis>(F), 1583 AM->getResult<AssumptionAnalysis>(F), 1584 AM->getCachedResult<DominatorTreeAnalysis>(F), 1585 AM->getCachedResult<LoopAnalysis>(F)); 1586} 1587 1588BasicAAWrapperPass::BasicAAWrapperPass() : FunctionPass(ID) { 1589 initializeBasicAAWrapperPassPass(*PassRegistry::getPassRegistry()); 1590} 1591 1592char BasicAAWrapperPass::ID = 0; 1593void BasicAAWrapperPass::anchor() {} 1594 1595INITIALIZE_PASS_BEGIN(BasicAAWrapperPass, "basicaa", 1596 "Basic Alias Analysis (stateless AA impl)", true, true) 1597INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 1598INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 1599INITIALIZE_PASS_END(BasicAAWrapperPass, "basicaa", 1600 "Basic Alias Analysis (stateless AA impl)", true, true) 1601 1602FunctionPass *llvm::createBasicAAWrapperPass() { 1603 return new BasicAAWrapperPass(); 1604} 1605 1606bool BasicAAWrapperPass::runOnFunction(Function &F) { 1607 auto &ACT = getAnalysis<AssumptionCacheTracker>(); 1608 auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>(); 1609 auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>(); 1610 auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>(); 1611 1612 Result.reset(new BasicAAResult(F.getParent()->getDataLayout(), TLIWP.getTLI(), 1613 ACT.getAssumptionCache(F), 1614 DTWP ? &DTWP->getDomTree() : nullptr, 1615 LIWP ? &LIWP->getLoopInfo() : nullptr)); 1616 1617 return false; 1618} 1619 1620void BasicAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { 1621 AU.setPreservesAll(); 1622 AU.addRequired<AssumptionCacheTracker>(); 1623 AU.addRequired<TargetLibraryInfoWrapperPass>(); 1624} 1625 1626BasicAAResult llvm::createLegacyPMBasicAAResult(Pass &P, Function &F) { 1627 return BasicAAResult( 1628 F.getParent()->getDataLayout(), 1629 P.getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(), 1630 P.getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F)); 1631} 1632