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