BasicAliasAnalysis.cpp revision df344febe27b8fa68424032c4181e494307d6eaf
1//===- BasicAliasAnalysis.cpp - Local Alias Analysis Impl -----------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines the default implementation of the Alias Analysis interface 11// that simply implements a few identities (two different globals cannot alias, 12// etc), but otherwise does no analysis. 13// 14//===----------------------------------------------------------------------===// 15 16#include "llvm/Analysis/AliasAnalysis.h" 17#include "llvm/Analysis/Passes.h" 18#include "llvm/Constants.h" 19#include "llvm/DerivedTypes.h" 20#include "llvm/Function.h" 21#include "llvm/ParameterAttributes.h" 22#include "llvm/GlobalVariable.h" 23#include "llvm/Instructions.h" 24#include "llvm/Intrinsics.h" 25#include "llvm/Pass.h" 26#include "llvm/Target/TargetData.h" 27#include "llvm/ADT/SmallVector.h" 28#include "llvm/ADT/StringMap.h" 29#include "llvm/ADT/BitVector.h" 30#include "llvm/Support/Compiler.h" 31#include "llvm/Support/GetElementPtrTypeIterator.h" 32#include "llvm/Support/ManagedStatic.h" 33#include <algorithm> 34using namespace llvm; 35 36namespace { 37 /// NoAA - This class implements the -no-aa pass, which always returns "I 38 /// don't know" for alias queries. NoAA is unlike other alias analysis 39 /// implementations, in that it does not chain to a previous analysis. As 40 /// such it doesn't follow many of the rules that other alias analyses must. 41 /// 42 struct VISIBILITY_HIDDEN NoAA : public ImmutablePass, public AliasAnalysis { 43 static char ID; // Class identification, replacement for typeinfo 44 NoAA() : ImmutablePass((intptr_t)&ID) {} 45 explicit NoAA(intptr_t PID) : ImmutablePass(PID) { } 46 47 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 48 AU.addRequired<TargetData>(); 49 } 50 51 virtual void initializePass() { 52 TD = &getAnalysis<TargetData>(); 53 } 54 55 virtual AliasResult alias(const Value *V1, unsigned V1Size, 56 const Value *V2, unsigned V2Size) { 57 return MayAlias; 58 } 59 60 virtual ModRefBehavior getModRefBehavior(Function *F, CallSite CS, 61 std::vector<PointerAccessInfo> *Info) { 62 return UnknownModRefBehavior; 63 } 64 65 virtual void getArgumentAccesses(Function *F, CallSite CS, 66 std::vector<PointerAccessInfo> &Info) { 67 assert(0 && "This method may not be called on this function!"); 68 } 69 70 virtual void getMustAliases(Value *P, std::vector<Value*> &RetVals) { } 71 virtual bool pointsToConstantMemory(const Value *P) { return false; } 72 virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size) { 73 return ModRef; 74 } 75 virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) { 76 return ModRef; 77 } 78 virtual bool hasNoModRefInfoForCalls() const { return true; } 79 80 virtual void deleteValue(Value *V) {} 81 virtual void copyValue(Value *From, Value *To) {} 82 }; 83 84 // Register this pass... 85 char NoAA::ID = 0; 86 RegisterPass<NoAA> 87 U("no-aa", "No Alias Analysis (always returns 'may' alias)"); 88 89 // Declare that we implement the AliasAnalysis interface 90 RegisterAnalysisGroup<AliasAnalysis> V(U); 91} // End of anonymous namespace 92 93ImmutablePass *llvm::createNoAAPass() { return new NoAA(); } 94 95namespace { 96 /// BasicAliasAnalysis - This is the default alias analysis implementation. 97 /// Because it doesn't chain to a previous alias analysis (like -no-aa), it 98 /// derives from the NoAA class. 99 struct VISIBILITY_HIDDEN BasicAliasAnalysis : public NoAA { 100 static char ID; // Class identification, replacement for typeinfo 101 BasicAliasAnalysis() : NoAA((intptr_t)&ID) { } 102 AliasResult alias(const Value *V1, unsigned V1Size, 103 const Value *V2, unsigned V2Size); 104 105 ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size); 106 ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) { 107 return NoAA::getModRefInfo(CS1,CS2); 108 } 109 110 /// hasNoModRefInfoForCalls - We can provide mod/ref information against 111 /// non-escaping allocations. 112 virtual bool hasNoModRefInfoForCalls() const { return false; } 113 114 /// pointsToConstantMemory - Chase pointers until we find a (constant 115 /// global) or not. 116 bool pointsToConstantMemory(const Value *P); 117 118 virtual ModRefBehavior getModRefBehavior(Function *F, CallSite CS, 119 std::vector<PointerAccessInfo> *Info); 120 121 private: 122 // CheckGEPInstructions - Check two GEP instructions with known 123 // must-aliasing base pointers. This checks to see if the index expressions 124 // preclude the pointers from aliasing... 125 AliasResult 126 CheckGEPInstructions(const Type* BasePtr1Ty, 127 Value **GEP1Ops, unsigned NumGEP1Ops, unsigned G1Size, 128 const Type *BasePtr2Ty, 129 Value **GEP2Ops, unsigned NumGEP2Ops, unsigned G2Size); 130 }; 131 132 // Register this pass... 133 char BasicAliasAnalysis::ID = 0; 134 RegisterPass<BasicAliasAnalysis> 135 X("basicaa", "Basic Alias Analysis (default AA impl)"); 136 137 // Declare that we implement the AliasAnalysis interface 138 RegisterAnalysisGroup<AliasAnalysis, true> Y(X); 139} // End of anonymous namespace 140 141ImmutablePass *llvm::createBasicAliasAnalysisPass() { 142 return new BasicAliasAnalysis(); 143} 144 145// getUnderlyingObject - This traverses the use chain to figure out what object 146// the specified value points to. If the value points to, or is derived from, a 147// unique object or an argument, return it. 148static const Value *getUnderlyingObject(const Value *V) { 149 if (!isa<PointerType>(V->getType())) return 0; 150 151 // If we are at some type of object, return it. GlobalValues and Allocations 152 // have unique addresses. 153 if (isa<GlobalValue>(V) || isa<AllocationInst>(V) || isa<Argument>(V)) 154 return V; 155 156 // Traverse through different addressing mechanisms... 157 if (const Instruction *I = dyn_cast<Instruction>(V)) { 158 if (isa<BitCastInst>(I) || isa<GetElementPtrInst>(I)) 159 return getUnderlyingObject(I->getOperand(0)); 160 } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { 161 if (CE->getOpcode() == Instruction::BitCast || 162 CE->getOpcode() == Instruction::GetElementPtr) 163 return getUnderlyingObject(CE->getOperand(0)); 164 } 165 return 0; 166} 167 168static const User *isGEP(const Value *V) { 169 if (isa<GetElementPtrInst>(V) || 170 (isa<ConstantExpr>(V) && 171 cast<ConstantExpr>(V)->getOpcode() == Instruction::GetElementPtr)) 172 return cast<User>(V); 173 return 0; 174} 175 176static const Value *GetGEPOperands(const Value *V, 177 SmallVector<Value*, 16> &GEPOps){ 178 assert(GEPOps.empty() && "Expect empty list to populate!"); 179 GEPOps.insert(GEPOps.end(), cast<User>(V)->op_begin()+1, 180 cast<User>(V)->op_end()); 181 182 // Accumulate all of the chained indexes into the operand array 183 V = cast<User>(V)->getOperand(0); 184 185 while (const User *G = isGEP(V)) { 186 if (!isa<Constant>(GEPOps[0]) || isa<GlobalValue>(GEPOps[0]) || 187 !cast<Constant>(GEPOps[0])->isNullValue()) 188 break; // Don't handle folding arbitrary pointer offsets yet... 189 GEPOps.erase(GEPOps.begin()); // Drop the zero index 190 GEPOps.insert(GEPOps.begin(), G->op_begin()+1, G->op_end()); 191 V = G->getOperand(0); 192 } 193 return V; 194} 195 196/// pointsToConstantMemory - Chase pointers until we find a (constant 197/// global) or not. 198bool BasicAliasAnalysis::pointsToConstantMemory(const Value *P) { 199 if (const Value *V = getUnderlyingObject(P)) 200 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) 201 return GV->isConstant(); 202 return false; 203} 204 205// Determine if an AllocationInst instruction escapes from the function it is 206// contained in. If it does not escape, there is no way for another function to 207// mod/ref it. We do this by looking at its uses and determining if the uses 208// can escape (recursively). 209static bool AddressMightEscape(const Value *V) { 210 for (Value::use_const_iterator UI = V->use_begin(), E = V->use_end(); 211 UI != E; ++UI) { 212 const Instruction *I = cast<Instruction>(*UI); 213 switch (I->getOpcode()) { 214 case Instruction::Load: 215 break; //next use. 216 case Instruction::Store: 217 if (I->getOperand(0) == V) 218 return true; // Escapes if the pointer is stored. 219 break; // next use. 220 case Instruction::GetElementPtr: 221 if (AddressMightEscape(I)) 222 return true; 223 break; // next use. 224 case Instruction::BitCast: 225 if (!isa<PointerType>(I->getType())) 226 return true; 227 if (AddressMightEscape(I)) 228 return true; 229 break; // next use 230 case Instruction::Ret: 231 // If returned, the address will escape to calling functions, but no 232 // callees could modify it. 233 break; // next use 234 default: 235 return true; 236 } 237 } 238 return false; 239} 240 241// getModRefInfo - Check to see if the specified callsite can clobber the 242// specified memory object. Since we only look at local properties of this 243// function, we really can't say much about this query. We do, however, use 244// simple "address taken" analysis on local objects. 245// 246AliasAnalysis::ModRefResult 247BasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) { 248 if (!isa<Constant>(P)) 249 if (const AllocationInst *AI = 250 dyn_cast_or_null<AllocationInst>(getUnderlyingObject(P))) { 251 // Okay, the pointer is to a stack allocated object. If we can prove that 252 // the pointer never "escapes", then we know the call cannot clobber it, 253 // because it simply can't get its address. 254 if (!AddressMightEscape(AI)) 255 return NoModRef; 256 257 // If this is a tail call and P points to a stack location, we know that 258 // the tail call cannot access or modify the local stack. 259 if (CallInst *CI = dyn_cast<CallInst>(CS.getInstruction())) 260 if (CI->isTailCall() && isa<AllocaInst>(AI)) 261 return NoModRef; 262 } 263 264 // The AliasAnalysis base class has some smarts, lets use them. 265 return AliasAnalysis::getModRefInfo(CS, P, Size); 266} 267 268static bool isNoAliasArgument(const Argument *Arg) { 269 const Function *Func = Arg->getParent(); 270 const ParamAttrsList *Attr = Func->getFunctionType()->getParamAttrs(); 271 if (Attr) { 272 unsigned Idx = 1; 273 for (Function::const_arg_iterator I = Func->arg_begin(), 274 E = Func->arg_end(); I != E; ++I, ++Idx) { 275 if (&(*I) == Arg && 276 Attr->paramHasAttr(Idx, ParamAttr::NoAlias)) 277 return true; 278 } 279 } 280 return false; 281} 282 283// alias - Provide a bunch of ad-hoc rules to disambiguate in common cases, such 284// as array references. Note that this function is heavily tail recursive. 285// Hopefully we have a smart C++ compiler. :) 286// 287AliasAnalysis::AliasResult 288BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size, 289 const Value *V2, unsigned V2Size) { 290 // Strip off any constant expression casts if they exist 291 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V1)) 292 if (CE->isCast() && isa<PointerType>(CE->getOperand(0)->getType())) 293 V1 = CE->getOperand(0); 294 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V2)) 295 if (CE->isCast() && isa<PointerType>(CE->getOperand(0)->getType())) 296 V2 = CE->getOperand(0); 297 298 // Are we checking for alias of the same value? 299 if (V1 == V2) return MustAlias; 300 301 if ((!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType())) && 302 V1->getType() != Type::Int64Ty && V2->getType() != Type::Int64Ty) 303 return NoAlias; // Scalars cannot alias each other 304 305 // Strip off cast instructions... 306 if (const BitCastInst *I = dyn_cast<BitCastInst>(V1)) 307 return alias(I->getOperand(0), V1Size, V2, V2Size); 308 if (const BitCastInst *I = dyn_cast<BitCastInst>(V2)) 309 return alias(V1, V1Size, I->getOperand(0), V2Size); 310 311 // Figure out what objects these things are pointing to if we can... 312 const Value *O1 = getUnderlyingObject(V1); 313 const Value *O2 = getUnderlyingObject(V2); 314 315 // Pointing at a discernible object? 316 if (O1) { 317 if (O2) { 318 if (const Argument *O1Arg = dyn_cast<Argument>(O1)) { 319 // Incoming argument cannot alias locally allocated object! 320 if (isa<AllocationInst>(O2)) return NoAlias; 321 322 // If they are two different objects, and one is a noalias argument 323 // then they do not alias. 324 if (O1 != O2 && isNoAliasArgument(O1Arg)) 325 return NoAlias; 326 327 // Otherwise, nothing is known... 328 } 329 330 if (const Argument *O2Arg = dyn_cast<Argument>(O2)) { 331 // Incoming argument cannot alias locally allocated object! 332 if (isa<AllocationInst>(O1)) return NoAlias; 333 334 // If they are two different objects, and one is a noalias argument 335 // then they do not alias. 336 if (O1 != O2 && isNoAliasArgument(O2Arg)) 337 return NoAlias; 338 339 // Otherwise, nothing is known... 340 } else if (O1 != O2) { 341 // If they are two different objects, we know that we have no alias... 342 return NoAlias; 343 } 344 345 // If they are the same object, they we can look at the indexes. If they 346 // index off of the object is the same for both pointers, they must alias. 347 // If they are provably different, they must not alias. Otherwise, we 348 // can't tell anything. 349 } 350 351 352 if (!isa<Argument>(O1) && isa<ConstantPointerNull>(V2)) 353 return NoAlias; // Unique values don't alias null 354 355 if (isa<GlobalVariable>(O1) || 356 (isa<AllocationInst>(O1) && 357 !cast<AllocationInst>(O1)->isArrayAllocation())) 358 if (cast<PointerType>(O1->getType())->getElementType()->isSized()) { 359 // If the size of the other access is larger than the total size of the 360 // global/alloca/malloc, it cannot be accessing the global (it's 361 // undefined to load or store bytes before or after an object). 362 const Type *ElTy = cast<PointerType>(O1->getType())->getElementType(); 363 unsigned GlobalSize = getTargetData().getTypeSize(ElTy); 364 if (GlobalSize < V2Size && V2Size != ~0U) 365 return NoAlias; 366 } 367 } 368 369 if (O2) { 370 if (!isa<Argument>(O2) && isa<ConstantPointerNull>(V1)) 371 return NoAlias; // Unique values don't alias null 372 373 if (isa<GlobalVariable>(O2) || 374 (isa<AllocationInst>(O2) && 375 !cast<AllocationInst>(O2)->isArrayAllocation())) 376 if (cast<PointerType>(O2->getType())->getElementType()->isSized()) { 377 // If the size of the other access is larger than the total size of the 378 // global/alloca/malloc, it cannot be accessing the object (it's 379 // undefined to load or store bytes before or after an object). 380 const Type *ElTy = cast<PointerType>(O2->getType())->getElementType(); 381 unsigned GlobalSize = getTargetData().getTypeSize(ElTy); 382 if (GlobalSize < V1Size && V1Size != ~0U) 383 return NoAlias; 384 } 385 } 386 387 // If we have two gep instructions with must-alias'ing base pointers, figure 388 // out if the indexes to the GEP tell us anything about the derived pointer. 389 // Note that we also handle chains of getelementptr instructions as well as 390 // constant expression getelementptrs here. 391 // 392 if (isGEP(V1) && isGEP(V2)) { 393 // Drill down into the first non-gep value, to test for must-aliasing of 394 // the base pointers. 395 const Value *BasePtr1 = V1, *BasePtr2 = V2; 396 do { 397 BasePtr1 = cast<User>(BasePtr1)->getOperand(0); 398 } while (isGEP(BasePtr1) && 399 cast<User>(BasePtr1)->getOperand(1) == 400 Constant::getNullValue(cast<User>(BasePtr1)->getOperand(1)->getType())); 401 do { 402 BasePtr2 = cast<User>(BasePtr2)->getOperand(0); 403 } while (isGEP(BasePtr2) && 404 cast<User>(BasePtr2)->getOperand(1) == 405 Constant::getNullValue(cast<User>(BasePtr2)->getOperand(1)->getType())); 406 407 // Do the base pointers alias? 408 AliasResult BaseAlias = alias(BasePtr1, ~0U, BasePtr2, ~0U); 409 if (BaseAlias == NoAlias) return NoAlias; 410 if (BaseAlias == MustAlias) { 411 // If the base pointers alias each other exactly, check to see if we can 412 // figure out anything about the resultant pointers, to try to prove 413 // non-aliasing. 414 415 // Collect all of the chained GEP operands together into one simple place 416 SmallVector<Value*, 16> GEP1Ops, GEP2Ops; 417 BasePtr1 = GetGEPOperands(V1, GEP1Ops); 418 BasePtr2 = GetGEPOperands(V2, GEP2Ops); 419 420 // If GetGEPOperands were able to fold to the same must-aliased pointer, 421 // do the comparison. 422 if (BasePtr1 == BasePtr2) { 423 AliasResult GAlias = 424 CheckGEPInstructions(BasePtr1->getType(), 425 &GEP1Ops[0], GEP1Ops.size(), V1Size, 426 BasePtr2->getType(), 427 &GEP2Ops[0], GEP2Ops.size(), V2Size); 428 if (GAlias != MayAlias) 429 return GAlias; 430 } 431 } 432 } 433 434 // Check to see if these two pointers are related by a getelementptr 435 // instruction. If one pointer is a GEP with a non-zero index of the other 436 // pointer, we know they cannot alias. 437 // 438 if (isGEP(V2)) { 439 std::swap(V1, V2); 440 std::swap(V1Size, V2Size); 441 } 442 443 if (V1Size != ~0U && V2Size != ~0U) 444 if (isGEP(V1)) { 445 SmallVector<Value*, 16> GEPOperands; 446 const Value *BasePtr = GetGEPOperands(V1, GEPOperands); 447 448 AliasResult R = alias(BasePtr, V1Size, V2, V2Size); 449 if (R == MustAlias) { 450 // If there is at least one non-zero constant index, we know they cannot 451 // alias. 452 bool ConstantFound = false; 453 bool AllZerosFound = true; 454 for (unsigned i = 0, e = GEPOperands.size(); i != e; ++i) 455 if (const Constant *C = dyn_cast<Constant>(GEPOperands[i])) { 456 if (!C->isNullValue()) { 457 ConstantFound = true; 458 AllZerosFound = false; 459 break; 460 } 461 } else { 462 AllZerosFound = false; 463 } 464 465 // If we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 must aliases 466 // the ptr, the end result is a must alias also. 467 if (AllZerosFound) 468 return MustAlias; 469 470 if (ConstantFound) { 471 if (V2Size <= 1 && V1Size <= 1) // Just pointer check? 472 return NoAlias; 473 474 // Otherwise we have to check to see that the distance is more than 475 // the size of the argument... build an index vector that is equal to 476 // the arguments provided, except substitute 0's for any variable 477 // indexes we find... 478 if (cast<PointerType>( 479 BasePtr->getType())->getElementType()->isSized()) { 480 for (unsigned i = 0; i != GEPOperands.size(); ++i) 481 if (!isa<ConstantInt>(GEPOperands[i])) 482 GEPOperands[i] = 483 Constant::getNullValue(GEPOperands[i]->getType()); 484 int64_t Offset = 485 getTargetData().getIndexedOffset(BasePtr->getType(), 486 &GEPOperands[0], 487 GEPOperands.size()); 488 489 if (Offset >= (int64_t)V2Size || Offset <= -(int64_t)V1Size) 490 return NoAlias; 491 } 492 } 493 } 494 } 495 496 return MayAlias; 497} 498 499// This function is used to determin if the indices of two GEP instructions are 500// equal. V1 and V2 are the indices. 501static bool IndexOperandsEqual(Value *V1, Value *V2) { 502 if (V1->getType() == V2->getType()) 503 return V1 == V2; 504 if (Constant *C1 = dyn_cast<Constant>(V1)) 505 if (Constant *C2 = dyn_cast<Constant>(V2)) { 506 // Sign extend the constants to long types, if necessary 507 if (C1->getType() != Type::Int64Ty) 508 C1 = ConstantExpr::getSExt(C1, Type::Int64Ty); 509 if (C2->getType() != Type::Int64Ty) 510 C2 = ConstantExpr::getSExt(C2, Type::Int64Ty); 511 return C1 == C2; 512 } 513 return false; 514} 515 516/// CheckGEPInstructions - Check two GEP instructions with known must-aliasing 517/// base pointers. This checks to see if the index expressions preclude the 518/// pointers from aliasing... 519AliasAnalysis::AliasResult 520BasicAliasAnalysis::CheckGEPInstructions( 521 const Type* BasePtr1Ty, Value **GEP1Ops, unsigned NumGEP1Ops, unsigned G1S, 522 const Type *BasePtr2Ty, Value **GEP2Ops, unsigned NumGEP2Ops, unsigned G2S) { 523 // We currently can't handle the case when the base pointers have different 524 // primitive types. Since this is uncommon anyway, we are happy being 525 // extremely conservative. 526 if (BasePtr1Ty != BasePtr2Ty) 527 return MayAlias; 528 529 const PointerType *GEPPointerTy = cast<PointerType>(BasePtr1Ty); 530 531 // Find the (possibly empty) initial sequence of equal values... which are not 532 // necessarily constants. 533 unsigned NumGEP1Operands = NumGEP1Ops, NumGEP2Operands = NumGEP2Ops; 534 unsigned MinOperands = std::min(NumGEP1Operands, NumGEP2Operands); 535 unsigned MaxOperands = std::max(NumGEP1Operands, NumGEP2Operands); 536 unsigned UnequalOper = 0; 537 while (UnequalOper != MinOperands && 538 IndexOperandsEqual(GEP1Ops[UnequalOper], GEP2Ops[UnequalOper])) { 539 // Advance through the type as we go... 540 ++UnequalOper; 541 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty)) 542 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[UnequalOper-1]); 543 else { 544 // If all operands equal each other, then the derived pointers must 545 // alias each other... 546 BasePtr1Ty = 0; 547 assert(UnequalOper == NumGEP1Operands && UnequalOper == NumGEP2Operands && 548 "Ran out of type nesting, but not out of operands?"); 549 return MustAlias; 550 } 551 } 552 553 // If we have seen all constant operands, and run out of indexes on one of the 554 // getelementptrs, check to see if the tail of the leftover one is all zeros. 555 // If so, return mustalias. 556 if (UnequalOper == MinOperands) { 557 if (NumGEP1Ops < NumGEP2Ops) { 558 std::swap(GEP1Ops, GEP2Ops); 559 std::swap(NumGEP1Ops, NumGEP2Ops); 560 } 561 562 bool AllAreZeros = true; 563 for (unsigned i = UnequalOper; i != MaxOperands; ++i) 564 if (!isa<Constant>(GEP1Ops[i]) || 565 !cast<Constant>(GEP1Ops[i])->isNullValue()) { 566 AllAreZeros = false; 567 break; 568 } 569 if (AllAreZeros) return MustAlias; 570 } 571 572 573 // So now we know that the indexes derived from the base pointers, 574 // which are known to alias, are different. We can still determine a 575 // no-alias result if there are differing constant pairs in the index 576 // chain. For example: 577 // A[i][0] != A[j][1] iff (&A[0][1]-&A[0][0] >= std::max(G1S, G2S)) 578 // 579 // We have to be careful here about array accesses. In particular, consider: 580 // A[1][0] vs A[0][i] 581 // In this case, we don't *know* that the array will be accessed in bounds: 582 // the index could even be negative. Because of this, we have to 583 // conservatively *give up* and return may alias. We disregard differing 584 // array subscripts that are followed by a variable index without going 585 // through a struct. 586 // 587 unsigned SizeMax = std::max(G1S, G2S); 588 if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work. 589 590 // Scan for the first operand that is constant and unequal in the 591 // two getelementptrs... 592 unsigned FirstConstantOper = UnequalOper; 593 for (; FirstConstantOper != MinOperands; ++FirstConstantOper) { 594 const Value *G1Oper = GEP1Ops[FirstConstantOper]; 595 const Value *G2Oper = GEP2Ops[FirstConstantOper]; 596 597 if (G1Oper != G2Oper) // Found non-equal constant indexes... 598 if (Constant *G1OC = dyn_cast<ConstantInt>(const_cast<Value*>(G1Oper))) 599 if (Constant *G2OC = dyn_cast<ConstantInt>(const_cast<Value*>(G2Oper))){ 600 if (G1OC->getType() != G2OC->getType()) { 601 // Sign extend both operands to long. 602 if (G1OC->getType() != Type::Int64Ty) 603 G1OC = ConstantExpr::getSExt(G1OC, Type::Int64Ty); 604 if (G2OC->getType() != Type::Int64Ty) 605 G2OC = ConstantExpr::getSExt(G2OC, Type::Int64Ty); 606 GEP1Ops[FirstConstantOper] = G1OC; 607 GEP2Ops[FirstConstantOper] = G2OC; 608 } 609 610 if (G1OC != G2OC) { 611 // Handle the "be careful" case above: if this is an array/vector 612 // subscript, scan for a subsequent variable array index. 613 if (isa<SequentialType>(BasePtr1Ty)) { 614 const Type *NextTy = 615 cast<SequentialType>(BasePtr1Ty)->getElementType(); 616 bool isBadCase = false; 617 618 for (unsigned Idx = FirstConstantOper+1; 619 Idx != MinOperands && isa<SequentialType>(NextTy); ++Idx) { 620 const Value *V1 = GEP1Ops[Idx], *V2 = GEP2Ops[Idx]; 621 if (!isa<Constant>(V1) || !isa<Constant>(V2)) { 622 isBadCase = true; 623 break; 624 } 625 NextTy = cast<SequentialType>(NextTy)->getElementType(); 626 } 627 628 if (isBadCase) G1OC = 0; 629 } 630 631 // Make sure they are comparable (ie, not constant expressions), and 632 // make sure the GEP with the smaller leading constant is GEP1. 633 if (G1OC) { 634 Constant *Compare = ConstantExpr::getICmp(ICmpInst::ICMP_SGT, 635 G1OC, G2OC); 636 if (ConstantInt *CV = dyn_cast<ConstantInt>(Compare)) { 637 if (CV->getZExtValue()) { // If they are comparable and G2 > G1 638 std::swap(GEP1Ops, GEP2Ops); // Make GEP1 < GEP2 639 std::swap(NumGEP1Ops, NumGEP2Ops); 640 } 641 break; 642 } 643 } 644 } 645 } 646 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(G1Oper); 647 } 648 649 // No shared constant operands, and we ran out of common operands. At this 650 // point, the GEP instructions have run through all of their operands, and we 651 // haven't found evidence that there are any deltas between the GEP's. 652 // However, one GEP may have more operands than the other. If this is the 653 // case, there may still be hope. Check this now. 654 if (FirstConstantOper == MinOperands) { 655 // Make GEP1Ops be the longer one if there is a longer one. 656 if (NumGEP1Ops < NumGEP2Ops) { 657 std::swap(GEP1Ops, GEP2Ops); 658 std::swap(NumGEP1Ops, NumGEP2Ops); 659 } 660 661 // Is there anything to check? 662 if (NumGEP1Ops > MinOperands) { 663 for (unsigned i = FirstConstantOper; i != MaxOperands; ++i) 664 if (isa<ConstantInt>(GEP1Ops[i]) && 665 !cast<ConstantInt>(GEP1Ops[i])->isZero()) { 666 // Yup, there's a constant in the tail. Set all variables to 667 // constants in the GEP instruction to make it suiteable for 668 // TargetData::getIndexedOffset. 669 for (i = 0; i != MaxOperands; ++i) 670 if (!isa<ConstantInt>(GEP1Ops[i])) 671 GEP1Ops[i] = Constant::getNullValue(GEP1Ops[i]->getType()); 672 // Okay, now get the offset. This is the relative offset for the full 673 // instruction. 674 const TargetData &TD = getTargetData(); 675 int64_t Offset1 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops, 676 NumGEP1Ops); 677 678 // Now check without any constants at the end. 679 int64_t Offset2 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops, 680 MinOperands); 681 682 // If the tail provided a bit enough offset, return noalias! 683 if ((uint64_t)(Offset2-Offset1) >= SizeMax) 684 return NoAlias; 685 } 686 } 687 688 // Couldn't find anything useful. 689 return MayAlias; 690 } 691 692 // If there are non-equal constants arguments, then we can figure 693 // out a minimum known delta between the two index expressions... at 694 // this point we know that the first constant index of GEP1 is less 695 // than the first constant index of GEP2. 696 697 // Advance BasePtr[12]Ty over this first differing constant operand. 698 BasePtr2Ty = cast<CompositeType>(BasePtr1Ty)-> 699 getTypeAtIndex(GEP2Ops[FirstConstantOper]); 700 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)-> 701 getTypeAtIndex(GEP1Ops[FirstConstantOper]); 702 703 // We are going to be using TargetData::getIndexedOffset to determine the 704 // offset that each of the GEP's is reaching. To do this, we have to convert 705 // all variable references to constant references. To do this, we convert the 706 // initial sequence of array subscripts into constant zeros to start with. 707 const Type *ZeroIdxTy = GEPPointerTy; 708 for (unsigned i = 0; i != FirstConstantOper; ++i) { 709 if (!isa<StructType>(ZeroIdxTy)) 710 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Type::Int32Ty); 711 712 if (const CompositeType *CT = dyn_cast<CompositeType>(ZeroIdxTy)) 713 ZeroIdxTy = CT->getTypeAtIndex(GEP1Ops[i]); 714 } 715 716 // We know that GEP1Ops[FirstConstantOper] & GEP2Ops[FirstConstantOper] are ok 717 718 // Loop over the rest of the operands... 719 for (unsigned i = FirstConstantOper+1; i != MaxOperands; ++i) { 720 const Value *Op1 = i < NumGEP1Ops ? GEP1Ops[i] : 0; 721 const Value *Op2 = i < NumGEP2Ops ? GEP2Ops[i] : 0; 722 // If they are equal, use a zero index... 723 if (Op1 == Op2 && BasePtr1Ty == BasePtr2Ty) { 724 if (!isa<ConstantInt>(Op1)) 725 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Op1->getType()); 726 // Otherwise, just keep the constants we have. 727 } else { 728 if (Op1) { 729 if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) { 730 // If this is an array index, make sure the array element is in range. 731 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) { 732 if (Op1C->getZExtValue() >= AT->getNumElements()) 733 return MayAlias; // Be conservative with out-of-range accesses 734 } else if (const VectorType *PT = dyn_cast<VectorType>(BasePtr1Ty)) { 735 if (Op1C->getZExtValue() >= PT->getNumElements()) 736 return MayAlias; // Be conservative with out-of-range accesses 737 } 738 739 } else { 740 // GEP1 is known to produce a value less than GEP2. To be 741 // conservatively correct, we must assume the largest possible 742 // constant is used in this position. This cannot be the initial 743 // index to the GEP instructions (because we know we have at least one 744 // element before this one with the different constant arguments), so 745 // we know that the current index must be into either a struct or 746 // array. Because we know it's not constant, this cannot be a 747 // structure index. Because of this, we can calculate the maximum 748 // value possible. 749 // 750 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) 751 GEP1Ops[i] = ConstantInt::get(Type::Int64Ty,AT->getNumElements()-1); 752 else if (const VectorType *PT = dyn_cast<VectorType>(BasePtr1Ty)) 753 GEP1Ops[i] = ConstantInt::get(Type::Int64Ty,PT->getNumElements()-1); 754 755 } 756 } 757 758 if (Op2) { 759 if (const ConstantInt *Op2C = dyn_cast<ConstantInt>(Op2)) { 760 // If this is an array index, make sure the array element is in range. 761 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) { 762 if (Op2C->getZExtValue() >= AT->getNumElements()) 763 return MayAlias; // Be conservative with out-of-range accesses 764 } else if (const VectorType *PT = dyn_cast<VectorType>(BasePtr1Ty)) { 765 if (Op2C->getZExtValue() >= PT->getNumElements()) 766 return MayAlias; // Be conservative with out-of-range accesses 767 } 768 } else { // Conservatively assume the minimum value for this index 769 GEP2Ops[i] = Constant::getNullValue(Op2->getType()); 770 } 771 } 772 } 773 774 if (BasePtr1Ty && Op1) { 775 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty)) 776 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[i]); 777 else 778 BasePtr1Ty = 0; 779 } 780 781 if (BasePtr2Ty && Op2) { 782 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr2Ty)) 783 BasePtr2Ty = CT->getTypeAtIndex(GEP2Ops[i]); 784 else 785 BasePtr2Ty = 0; 786 } 787 } 788 789 if (GEPPointerTy->getElementType()->isSized()) { 790 int64_t Offset1 = 791 getTargetData().getIndexedOffset(GEPPointerTy, GEP1Ops, NumGEP1Ops); 792 int64_t Offset2 = 793 getTargetData().getIndexedOffset(GEPPointerTy, GEP2Ops, NumGEP2Ops); 794 assert(Offset1<Offset2 && "There is at least one different constant here!"); 795 796 if ((uint64_t)(Offset2-Offset1) >= SizeMax) { 797 //cerr << "Determined that these two GEP's don't alias [" 798 // << SizeMax << " bytes]: \n" << *GEP1 << *GEP2; 799 return NoAlias; 800 } 801 } 802 return MayAlias; 803} 804 805namespace { 806 struct VISIBILITY_HIDDEN StringCompare { 807 bool operator()(const char *LHS, const char *RHS) { 808 return strcmp(LHS, RHS) < 0; 809 } 810 }; 811} 812 813// Note that this list cannot contain libm functions (such as acos and sqrt) 814// that set errno on a domain or other error. 815static const char *DoesntAccessMemoryFns[] = { 816 "abs", "labs", "llabs", "imaxabs", "fabs", "fabsf", "fabsl", 817 "trunc", "truncf", "truncl", "ldexp", 818 819 "atan", "atanf", "atanl", "atan2", "atan2f", "atan2l", 820 "cbrt", 821 "cos", "cosf", "cosl", 822 "exp", "expf", "expl", 823 "hypot", 824 "sin", "sinf", "sinl", 825 "tan", "tanf", "tanl", "tanh", "tanhf", "tanhl", 826 827 "floor", "floorf", "floorl", "ceil", "ceilf", "ceill", 828 829 // ctype.h 830 "isalnum", "isalpha", "iscntrl", "isdigit", "isgraph", "islower", "isprint" 831 "ispunct", "isspace", "isupper", "isxdigit", "tolower", "toupper", 832 833 // wctype.h" 834 "iswalnum", "iswalpha", "iswcntrl", "iswdigit", "iswgraph", "iswlower", 835 "iswprint", "iswpunct", "iswspace", "iswupper", "iswxdigit", 836 837 "iswctype", "towctrans", "towlower", "towupper", 838 839 "btowc", "wctob", 840 841 "isinf", "isnan", "finite", 842 843 // C99 math functions 844 "copysign", "copysignf", "copysignd", 845 "nexttoward", "nexttowardf", "nexttowardd", 846 "nextafter", "nextafterf", "nextafterd", 847 848 // ISO C99: 849 "__signbit", "__signbitf", "__signbitl", 850}; 851 852 853static const char *OnlyReadsMemoryFns[] = { 854 "atoi", "atol", "atof", "atoll", "atoq", "a64l", 855 "bcmp", "memcmp", "memchr", "memrchr", "wmemcmp", "wmemchr", 856 857 // Strings 858 "strcmp", "strcasecmp", "strcoll", "strncmp", "strncasecmp", 859 "strchr", "strcspn", "strlen", "strpbrk", "strrchr", "strspn", "strstr", 860 "index", "rindex", 861 862 // Wide char strings 863 "wcschr", "wcscmp", "wcscoll", "wcscspn", "wcslen", "wcsncmp", "wcspbrk", 864 "wcsrchr", "wcsspn", "wcsstr", 865 866 // glibc 867 "alphasort", "alphasort64", "versionsort", "versionsort64", 868 869 // C99 870 "nan", "nanf", "nand", 871 872 // File I/O 873 "feof", "ferror", "fileno", 874 "feof_unlocked", "ferror_unlocked", "fileno_unlocked" 875}; 876 877static ManagedStatic<std::vector<const char*> > NoMemoryTable; 878static ManagedStatic<std::vector<const char*> > OnlyReadsMemoryTable; 879 880static ManagedStatic<BitVector> NoMemoryIntrinsics; 881static ManagedStatic<BitVector> OnlyReadsMemoryIntrinsics; 882 883 884AliasAnalysis::ModRefBehavior 885BasicAliasAnalysis::getModRefBehavior(Function *F, CallSite CS, 886 std::vector<PointerAccessInfo> *Info) { 887 if (!F->isDeclaration()) return UnknownModRefBehavior; 888 889 static bool Initialized = false; 890 if (!Initialized) { 891 NoMemoryTable->insert(NoMemoryTable->end(), 892 DoesntAccessMemoryFns, 893 DoesntAccessMemoryFns+ 894 sizeof(DoesntAccessMemoryFns)/sizeof(DoesntAccessMemoryFns[0])); 895 896 OnlyReadsMemoryTable->insert(OnlyReadsMemoryTable->end(), 897 OnlyReadsMemoryFns, 898 OnlyReadsMemoryFns+ 899 sizeof(OnlyReadsMemoryFns)/sizeof(OnlyReadsMemoryFns[0])); 900 901 // Sort the table the first time through. 902 std::sort(NoMemoryTable->begin(), NoMemoryTable->end(), StringCompare()); 903 std::sort(OnlyReadsMemoryTable->begin(), OnlyReadsMemoryTable->end(), 904 StringCompare()); 905 906 NoMemoryIntrinsics->resize(Intrinsic::num_intrinsics); 907 OnlyReadsMemoryIntrinsics->resize(Intrinsic::num_intrinsics); 908#define GET_MODREF_BEHAVIOR 909#include "llvm/Intrinsics.gen" 910#undef GET_MODREF_BEHAVIOR 911 912 Initialized = true; 913 } 914 915 // If this is an intrinsic, we can use lookup tables 916 if (unsigned id = F->getIntrinsicID()) { 917 if (NoMemoryIntrinsics->test(id)) 918 return DoesNotAccessMemory; 919 if (OnlyReadsMemoryIntrinsics->test(id)) 920 return OnlyReadsMemory; 921 922 return UnknownModRefBehavior; 923 } 924 925 ValueName *Name = F->getValueName(); 926 unsigned NameLen = Name->getKeyLength(); 927 const char *NamePtr = Name->getKeyData(); 928 929 // If there is an embedded nul character in the function name, we can never 930 // match it. 931 if (strlen(NamePtr) != NameLen) 932 return UnknownModRefBehavior; 933 934 std::vector<const char*>::iterator Ptr = 935 std::lower_bound(NoMemoryTable->begin(), NoMemoryTable->end(), 936 NamePtr, StringCompare()); 937 if (Ptr != NoMemoryTable->end() && strcmp(*Ptr, NamePtr) == 0) 938 return DoesNotAccessMemory; 939 940 Ptr = std::lower_bound(OnlyReadsMemoryTable->begin(), 941 OnlyReadsMemoryTable->end(), 942 NamePtr, StringCompare()); 943 if (Ptr != OnlyReadsMemoryTable->end() && strcmp(*Ptr, NamePtr) == 0) 944 return OnlyReadsMemory; 945 946 return UnknownModRefBehavior; 947} 948 949// Make sure that anything that uses AliasAnalysis pulls in this file... 950DEFINING_FILE_FOR(BasicAliasAnalysis) 951