BasicAliasAnalysis.cpp revision c5b206b6be61d0d933b98b6af5e22f42edd48ad1
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 if (isa<PointerType>(I->getOperand(0)->getType())) 278 return alias(I->getOperand(0), V1Size, V2, V2Size); 279 if (const BitCastInst *I = dyn_cast<BitCastInst>(V2)) 280 if (isa<PointerType>(I->getOperand(0)->getType())) 281 return alias(V1, V1Size, I->getOperand(0), V2Size); 282 283 // Figure out what objects these things are pointing to if we can... 284 const Value *O1 = getUnderlyingObject(V1); 285 const Value *O2 = getUnderlyingObject(V2); 286 287 // Pointing at a discernible object? 288 if (O1) { 289 if (O2) { 290 if (isa<Argument>(O1)) { 291 // Incoming argument cannot alias locally allocated object! 292 if (isa<AllocationInst>(O2)) return NoAlias; 293 // Otherwise, nothing is known... 294 } else if (isa<Argument>(O2)) { 295 // Incoming argument cannot alias locally allocated object! 296 if (isa<AllocationInst>(O1)) return NoAlias; 297 // Otherwise, nothing is known... 298 } else if (O1 != O2) { 299 // If they are two different objects, we know that we have no alias... 300 return NoAlias; 301 } 302 303 // If they are the same object, they we can look at the indexes. If they 304 // index off of the object is the same for both pointers, they must alias. 305 // If they are provably different, they must not alias. Otherwise, we 306 // can't tell anything. 307 } 308 309 310 if (!isa<Argument>(O1) && isa<ConstantPointerNull>(V2)) 311 return NoAlias; // Unique values don't alias null 312 313 if (isa<GlobalVariable>(O1) || 314 (isa<AllocationInst>(O1) && 315 !cast<AllocationInst>(O1)->isArrayAllocation())) 316 if (cast<PointerType>(O1->getType())->getElementType()->isSized()) { 317 // If the size of the other access is larger than the total size of the 318 // global/alloca/malloc, it cannot be accessing the global (it's 319 // undefined to load or store bytes before or after an object). 320 const Type *ElTy = cast<PointerType>(O1->getType())->getElementType(); 321 unsigned GlobalSize = getTargetData().getTypeSize(ElTy); 322 if (GlobalSize < V2Size && V2Size != ~0U) 323 return NoAlias; 324 } 325 } 326 327 if (O2) { 328 if (!isa<Argument>(O2) && isa<ConstantPointerNull>(V1)) 329 return NoAlias; // Unique values don't alias null 330 331 if (isa<GlobalVariable>(O2) || 332 (isa<AllocationInst>(O2) && 333 !cast<AllocationInst>(O2)->isArrayAllocation())) 334 if (cast<PointerType>(O2->getType())->getElementType()->isSized()) { 335 // If the size of the other access is larger than the total size of the 336 // global/alloca/malloc, it cannot be accessing the object (it's 337 // undefined to load or store bytes before or after an object). 338 const Type *ElTy = cast<PointerType>(O2->getType())->getElementType(); 339 unsigned GlobalSize = getTargetData().getTypeSize(ElTy); 340 if (GlobalSize < V1Size && V1Size != ~0U) 341 return NoAlias; 342 } 343 } 344 345 // If we have two gep instructions with must-alias'ing base pointers, figure 346 // out if the indexes to the GEP tell us anything about the derived pointer. 347 // Note that we also handle chains of getelementptr instructions as well as 348 // constant expression getelementptrs here. 349 // 350 if (isGEP(V1) && isGEP(V2)) { 351 // Drill down into the first non-gep value, to test for must-aliasing of 352 // the base pointers. 353 const Value *BasePtr1 = V1, *BasePtr2 = V2; 354 do { 355 BasePtr1 = cast<User>(BasePtr1)->getOperand(0); 356 } while (isGEP(BasePtr1) && 357 cast<User>(BasePtr1)->getOperand(1) == 358 Constant::getNullValue(cast<User>(BasePtr1)->getOperand(1)->getType())); 359 do { 360 BasePtr2 = cast<User>(BasePtr2)->getOperand(0); 361 } while (isGEP(BasePtr2) && 362 cast<User>(BasePtr2)->getOperand(1) == 363 Constant::getNullValue(cast<User>(BasePtr2)->getOperand(1)->getType())); 364 365 // Do the base pointers alias? 366 AliasResult BaseAlias = alias(BasePtr1, V1Size, BasePtr2, V2Size); 367 if (BaseAlias == NoAlias) return NoAlias; 368 if (BaseAlias == MustAlias) { 369 // If the base pointers alias each other exactly, check to see if we can 370 // figure out anything about the resultant pointers, to try to prove 371 // non-aliasing. 372 373 // Collect all of the chained GEP operands together into one simple place 374 std::vector<Value*> GEP1Ops, GEP2Ops; 375 BasePtr1 = GetGEPOperands(V1, GEP1Ops); 376 BasePtr2 = GetGEPOperands(V2, GEP2Ops); 377 378 // If GetGEPOperands were able to fold to the same must-aliased pointer, 379 // do the comparison. 380 if (BasePtr1 == BasePtr2) { 381 AliasResult GAlias = 382 CheckGEPInstructions(BasePtr1->getType(), GEP1Ops, V1Size, 383 BasePtr2->getType(), GEP2Ops, V2Size); 384 if (GAlias != MayAlias) 385 return GAlias; 386 } 387 } 388 } 389 390 // Check to see if these two pointers are related by a getelementptr 391 // instruction. If one pointer is a GEP with a non-zero index of the other 392 // pointer, we know they cannot alias. 393 // 394 if (isGEP(V2)) { 395 std::swap(V1, V2); 396 std::swap(V1Size, V2Size); 397 } 398 399 if (V1Size != ~0U && V2Size != ~0U) 400 if (isGEP(V1)) { 401 std::vector<Value*> GEPOperands; 402 const Value *BasePtr = GetGEPOperands(V1, GEPOperands); 403 404 AliasResult R = alias(BasePtr, V1Size, V2, V2Size); 405 if (R == MustAlias) { 406 // If there is at least one non-zero constant index, we know they cannot 407 // alias. 408 bool ConstantFound = false; 409 bool AllZerosFound = true; 410 for (unsigned i = 0, e = GEPOperands.size(); i != e; ++i) 411 if (const Constant *C = dyn_cast<Constant>(GEPOperands[i])) { 412 if (!C->isNullValue()) { 413 ConstantFound = true; 414 AllZerosFound = false; 415 break; 416 } 417 } else { 418 AllZerosFound = false; 419 } 420 421 // If we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 must aliases 422 // the ptr, the end result is a must alias also. 423 if (AllZerosFound) 424 return MustAlias; 425 426 if (ConstantFound) { 427 if (V2Size <= 1 && V1Size <= 1) // Just pointer check? 428 return NoAlias; 429 430 // Otherwise we have to check to see that the distance is more than 431 // the size of the argument... build an index vector that is equal to 432 // the arguments provided, except substitute 0's for any variable 433 // indexes we find... 434 if (cast<PointerType>( 435 BasePtr->getType())->getElementType()->isSized()) { 436 for (unsigned i = 0; i != GEPOperands.size(); ++i) 437 if (!isa<ConstantInt>(GEPOperands[i])) 438 GEPOperands[i] = 439 Constant::getNullValue(GEPOperands[i]->getType()); 440 int64_t Offset = 441 getTargetData().getIndexedOffset(BasePtr->getType(), GEPOperands); 442 443 if (Offset >= (int64_t)V2Size || Offset <= -(int64_t)V1Size) 444 return NoAlias; 445 } 446 } 447 } 448 } 449 450 return MayAlias; 451} 452 453// This function is used to determin if the indices of two GEP instructions are 454// equal. V1 and V2 are the indices. 455static bool IndexOperandsEqual(Value *V1, Value *V2) { 456 if (V1->getType() == V2->getType()) 457 return V1 == V2; 458 if (Constant *C1 = dyn_cast<Constant>(V1)) 459 if (Constant *C2 = dyn_cast<Constant>(V2)) { 460 // Sign extend the constants to long types, if necessary 461 if (C1->getType() != Type::Int64Ty) 462 C1 = ConstantExpr::getSExt(C1, Type::Int64Ty); 463 if (C2->getType() != Type::Int64Ty) 464 C2 = ConstantExpr::getSExt(C2, Type::Int64Ty); 465 return C1 == C2; 466 } 467 return false; 468} 469 470/// CheckGEPInstructions - Check two GEP instructions with known must-aliasing 471/// base pointers. This checks to see if the index expressions preclude the 472/// pointers from aliasing... 473AliasAnalysis::AliasResult 474BasicAliasAnalysis::CheckGEPInstructions( 475 const Type* BasePtr1Ty, std::vector<Value*> &GEP1Ops, unsigned G1S, 476 const Type *BasePtr2Ty, std::vector<Value*> &GEP2Ops, unsigned G2S) { 477 // We currently can't handle the case when the base pointers have different 478 // primitive types. Since this is uncommon anyway, we are happy being 479 // extremely conservative. 480 if (BasePtr1Ty != BasePtr2Ty) 481 return MayAlias; 482 483 const PointerType *GEPPointerTy = cast<PointerType>(BasePtr1Ty); 484 485 // Find the (possibly empty) initial sequence of equal values... which are not 486 // necessarily constants. 487 unsigned NumGEP1Operands = GEP1Ops.size(), NumGEP2Operands = GEP2Ops.size(); 488 unsigned MinOperands = std::min(NumGEP1Operands, NumGEP2Operands); 489 unsigned MaxOperands = std::max(NumGEP1Operands, NumGEP2Operands); 490 unsigned UnequalOper = 0; 491 while (UnequalOper != MinOperands && 492 IndexOperandsEqual(GEP1Ops[UnequalOper], GEP2Ops[UnequalOper])) { 493 // Advance through the type as we go... 494 ++UnequalOper; 495 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty)) 496 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[UnequalOper-1]); 497 else { 498 // If all operands equal each other, then the derived pointers must 499 // alias each other... 500 BasePtr1Ty = 0; 501 assert(UnequalOper == NumGEP1Operands && UnequalOper == NumGEP2Operands && 502 "Ran out of type nesting, but not out of operands?"); 503 return MustAlias; 504 } 505 } 506 507 // If we have seen all constant operands, and run out of indexes on one of the 508 // getelementptrs, check to see if the tail of the leftover one is all zeros. 509 // If so, return mustalias. 510 if (UnequalOper == MinOperands) { 511 if (GEP1Ops.size() < GEP2Ops.size()) std::swap(GEP1Ops, GEP2Ops); 512 513 bool AllAreZeros = true; 514 for (unsigned i = UnequalOper; i != MaxOperands; ++i) 515 if (!isa<Constant>(GEP1Ops[i]) || 516 !cast<Constant>(GEP1Ops[i])->isNullValue()) { 517 AllAreZeros = false; 518 break; 519 } 520 if (AllAreZeros) return MustAlias; 521 } 522 523 524 // So now we know that the indexes derived from the base pointers, 525 // which are known to alias, are different. We can still determine a 526 // no-alias result if there are differing constant pairs in the index 527 // chain. For example: 528 // A[i][0] != A[j][1] iff (&A[0][1]-&A[0][0] >= std::max(G1S, G2S)) 529 // 530 // We have to be careful here about array accesses. In particular, consider: 531 // A[1][0] vs A[0][i] 532 // In this case, we don't *know* that the array will be accessed in bounds: 533 // the index could even be negative. Because of this, we have to 534 // conservatively *give up* and return may alias. We disregard differing 535 // array subscripts that are followed by a variable index without going 536 // through a struct. 537 // 538 unsigned SizeMax = std::max(G1S, G2S); 539 if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work. 540 541 // Scan for the first operand that is constant and unequal in the 542 // two getelementptrs... 543 unsigned FirstConstantOper = UnequalOper; 544 for (; FirstConstantOper != MinOperands; ++FirstConstantOper) { 545 const Value *G1Oper = GEP1Ops[FirstConstantOper]; 546 const Value *G2Oper = GEP2Ops[FirstConstantOper]; 547 548 if (G1Oper != G2Oper) // Found non-equal constant indexes... 549 if (Constant *G1OC = dyn_cast<ConstantInt>(const_cast<Value*>(G1Oper))) 550 if (Constant *G2OC = dyn_cast<ConstantInt>(const_cast<Value*>(G2Oper))){ 551 if (G1OC->getType() != G2OC->getType()) { 552 // Sign extend both operands to long. 553 if (G1OC->getType() != Type::Int64Ty) 554 G1OC = ConstantExpr::getSExt(G1OC, Type::Int64Ty); 555 if (G2OC->getType() != Type::Int64Ty) 556 G2OC = ConstantExpr::getSExt(G2OC, Type::Int64Ty); 557 GEP1Ops[FirstConstantOper] = G1OC; 558 GEP2Ops[FirstConstantOper] = G2OC; 559 } 560 561 if (G1OC != G2OC) { 562 // Handle the "be careful" case above: if this is an array/packed 563 // subscript, scan for a subsequent variable array index. 564 if (isa<SequentialType>(BasePtr1Ty)) { 565 const Type *NextTy = 566 cast<SequentialType>(BasePtr1Ty)->getElementType(); 567 bool isBadCase = false; 568 569 for (unsigned Idx = FirstConstantOper+1; 570 Idx != MinOperands && isa<SequentialType>(NextTy); ++Idx) { 571 const Value *V1 = GEP1Ops[Idx], *V2 = GEP2Ops[Idx]; 572 if (!isa<Constant>(V1) || !isa<Constant>(V2)) { 573 isBadCase = true; 574 break; 575 } 576 NextTy = cast<SequentialType>(NextTy)->getElementType(); 577 } 578 579 if (isBadCase) G1OC = 0; 580 } 581 582 // Make sure they are comparable (ie, not constant expressions), and 583 // make sure the GEP with the smaller leading constant is GEP1. 584 if (G1OC) { 585 Constant *Compare = ConstantExpr::getICmp(ICmpInst::ICMP_SGT, 586 G1OC, G2OC); 587 if (ConstantBool *CV = dyn_cast<ConstantBool>(Compare)) { 588 if (CV->getValue()) // If they are comparable and G2 > G1 589 std::swap(GEP1Ops, GEP2Ops); // Make GEP1 < GEP2 590 break; 591 } 592 } 593 } 594 } 595 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(G1Oper); 596 } 597 598 // No shared constant operands, and we ran out of common operands. At this 599 // point, the GEP instructions have run through all of their operands, and we 600 // haven't found evidence that there are any deltas between the GEP's. 601 // However, one GEP may have more operands than the other. If this is the 602 // case, there may still be hope. Check this now. 603 if (FirstConstantOper == MinOperands) { 604 // Make GEP1Ops be the longer one if there is a longer one. 605 if (GEP1Ops.size() < GEP2Ops.size()) 606 std::swap(GEP1Ops, GEP2Ops); 607 608 // Is there anything to check? 609 if (GEP1Ops.size() > MinOperands) { 610 for (unsigned i = FirstConstantOper; i != MaxOperands; ++i) 611 if (isa<ConstantInt>(GEP1Ops[i]) && 612 !cast<Constant>(GEP1Ops[i])->isNullValue()) { 613 // Yup, there's a constant in the tail. Set all variables to 614 // constants in the GEP instruction to make it suiteable for 615 // TargetData::getIndexedOffset. 616 for (i = 0; i != MaxOperands; ++i) 617 if (!isa<ConstantInt>(GEP1Ops[i])) 618 GEP1Ops[i] = Constant::getNullValue(GEP1Ops[i]->getType()); 619 // Okay, now get the offset. This is the relative offset for the full 620 // instruction. 621 const TargetData &TD = getTargetData(); 622 int64_t Offset1 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops); 623 624 // Now crop off any constants from the end... 625 GEP1Ops.resize(MinOperands); 626 int64_t Offset2 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops); 627 628 // If the tail provided a bit enough offset, return noalias! 629 if ((uint64_t)(Offset2-Offset1) >= SizeMax) 630 return NoAlias; 631 } 632 } 633 634 // Couldn't find anything useful. 635 return MayAlias; 636 } 637 638 // If there are non-equal constants arguments, then we can figure 639 // out a minimum known delta between the two index expressions... at 640 // this point we know that the first constant index of GEP1 is less 641 // than the first constant index of GEP2. 642 643 // Advance BasePtr[12]Ty over this first differing constant operand. 644 BasePtr2Ty = cast<CompositeType>(BasePtr1Ty)-> 645 getTypeAtIndex(GEP2Ops[FirstConstantOper]); 646 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)-> 647 getTypeAtIndex(GEP1Ops[FirstConstantOper]); 648 649 // We are going to be using TargetData::getIndexedOffset to determine the 650 // offset that each of the GEP's is reaching. To do this, we have to convert 651 // all variable references to constant references. To do this, we convert the 652 // initial sequence of array subscripts into constant zeros to start with. 653 const Type *ZeroIdxTy = GEPPointerTy; 654 for (unsigned i = 0; i != FirstConstantOper; ++i) { 655 if (!isa<StructType>(ZeroIdxTy)) 656 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Type::Int32Ty); 657 658 if (const CompositeType *CT = dyn_cast<CompositeType>(ZeroIdxTy)) 659 ZeroIdxTy = CT->getTypeAtIndex(GEP1Ops[i]); 660 } 661 662 // We know that GEP1Ops[FirstConstantOper] & GEP2Ops[FirstConstantOper] are ok 663 664 // Loop over the rest of the operands... 665 for (unsigned i = FirstConstantOper+1; i != MaxOperands; ++i) { 666 const Value *Op1 = i < GEP1Ops.size() ? GEP1Ops[i] : 0; 667 const Value *Op2 = i < GEP2Ops.size() ? GEP2Ops[i] : 0; 668 // If they are equal, use a zero index... 669 if (Op1 == Op2 && BasePtr1Ty == BasePtr2Ty) { 670 if (!isa<ConstantInt>(Op1)) 671 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Op1->getType()); 672 // Otherwise, just keep the constants we have. 673 } else { 674 if (Op1) { 675 if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) { 676 // If this is an array index, make sure the array element is in range. 677 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) { 678 if (Op1C->getZExtValue() >= AT->getNumElements()) 679 return MayAlias; // Be conservative with out-of-range accesses 680 } else if (const PackedType *PT = dyn_cast<PackedType>(BasePtr1Ty)) { 681 if (Op1C->getZExtValue() >= PT->getNumElements()) 682 return MayAlias; // Be conservative with out-of-range accesses 683 } 684 685 } else { 686 // GEP1 is known to produce a value less than GEP2. To be 687 // conservatively correct, we must assume the largest possible 688 // constant is used in this position. This cannot be the initial 689 // index to the GEP instructions (because we know we have at least one 690 // element before this one with the different constant arguments), so 691 // we know that the current index must be into either a struct or 692 // array. Because we know it's not constant, this cannot be a 693 // structure index. Because of this, we can calculate the maximum 694 // value possible. 695 // 696 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) 697 GEP1Ops[i] = ConstantInt::get(Type::Int64Ty, AT->getNumElements()-1); 698 else if (const PackedType *PT = dyn_cast<PackedType>(BasePtr1Ty)) 699 GEP1Ops[i] = ConstantInt::get(Type::Int64Ty, PT->getNumElements()-1); 700 701 } 702 } 703 704 if (Op2) { 705 if (const ConstantInt *Op2C = dyn_cast<ConstantInt>(Op2)) { 706 // If this is an array index, make sure the array element is in range. 707 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) { 708 if (Op2C->getZExtValue() >= AT->getNumElements()) 709 return MayAlias; // Be conservative with out-of-range accesses 710 } else if (const PackedType *PT = dyn_cast<PackedType>(BasePtr1Ty)) { 711 if (Op2C->getZExtValue() >= PT->getNumElements()) 712 return MayAlias; // Be conservative with out-of-range accesses 713 } 714 } else { // Conservatively assume the minimum value for this index 715 GEP2Ops[i] = Constant::getNullValue(Op2->getType()); 716 } 717 } 718 } 719 720 if (BasePtr1Ty && Op1) { 721 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty)) 722 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[i]); 723 else 724 BasePtr1Ty = 0; 725 } 726 727 if (BasePtr2Ty && Op2) { 728 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr2Ty)) 729 BasePtr2Ty = CT->getTypeAtIndex(GEP2Ops[i]); 730 else 731 BasePtr2Ty = 0; 732 } 733 } 734 735 if (GEPPointerTy->getElementType()->isSized()) { 736 int64_t Offset1 = getTargetData().getIndexedOffset(GEPPointerTy, GEP1Ops); 737 int64_t Offset2 = getTargetData().getIndexedOffset(GEPPointerTy, GEP2Ops); 738 assert(Offset1<Offset2 && "There is at least one different constant here!"); 739 740 if ((uint64_t)(Offset2-Offset1) >= SizeMax) { 741 //cerr << "Determined that these two GEP's don't alias [" 742 // << SizeMax << " bytes]: \n" << *GEP1 << *GEP2; 743 return NoAlias; 744 } 745 } 746 return MayAlias; 747} 748 749namespace { 750 struct StringCompare { 751 bool operator()(const char *LHS, const char *RHS) { 752 return strcmp(LHS, RHS) < 0; 753 } 754 }; 755} 756 757// Note that this list cannot contain libm functions (such as acos and sqrt) 758// that set errno on a domain or other error. 759static const char *DoesntAccessMemoryFns[] = { 760 "abs", "labs", "llabs", "imaxabs", "fabs", "fabsf", "fabsl", 761 "trunc", "truncf", "truncl", "ldexp", 762 763 "atan", "atanf", "atanl", "atan2", "atan2f", "atan2l", 764 "cbrt", 765 "cos", "cosf", "cosl", 766 "exp", "expf", "expl", 767 "hypot", 768 "sin", "sinf", "sinl", 769 "tan", "tanf", "tanl", "tanh", "tanhf", "tanhl", 770 771 "floor", "floorf", "floorl", "ceil", "ceilf", "ceill", 772 773 // ctype.h 774 "isalnum", "isalpha", "iscntrl", "isdigit", "isgraph", "islower", "isprint" 775 "ispunct", "isspace", "isupper", "isxdigit", "tolower", "toupper", 776 777 // wctype.h" 778 "iswalnum", "iswalpha", "iswcntrl", "iswdigit", "iswgraph", "iswlower", 779 "iswprint", "iswpunct", "iswspace", "iswupper", "iswxdigit", 780 781 "iswctype", "towctrans", "towlower", "towupper", 782 783 "btowc", "wctob", 784 785 "isinf", "isnan", "finite", 786 787 // C99 math functions 788 "copysign", "copysignf", "copysignd", 789 "nexttoward", "nexttowardf", "nexttowardd", 790 "nextafter", "nextafterf", "nextafterd", 791 792 // ISO C99: 793 "__signbit", "__signbitf", "__signbitl", 794}; 795 796 797static const char *OnlyReadsMemoryFns[] = { 798 "atoi", "atol", "atof", "atoll", "atoq", "a64l", 799 "bcmp", "memcmp", "memchr", "memrchr", "wmemcmp", "wmemchr", 800 801 // Strings 802 "strcmp", "strcasecmp", "strcoll", "strncmp", "strncasecmp", 803 "strchr", "strcspn", "strlen", "strpbrk", "strrchr", "strspn", "strstr", 804 "index", "rindex", 805 806 // Wide char strings 807 "wcschr", "wcscmp", "wcscoll", "wcscspn", "wcslen", "wcsncmp", "wcspbrk", 808 "wcsrchr", "wcsspn", "wcsstr", 809 810 // glibc 811 "alphasort", "alphasort64", "versionsort", "versionsort64", 812 813 // C99 814 "nan", "nanf", "nand", 815 816 // File I/O 817 "feof", "ferror", "fileno", 818 "feof_unlocked", "ferror_unlocked", "fileno_unlocked" 819}; 820 821static ManagedStatic<std::vector<const char*> > NoMemoryTable; 822static ManagedStatic<std::vector<const char*> > OnlyReadsMemoryTable; 823 824 825AliasAnalysis::ModRefBehavior 826BasicAliasAnalysis::getModRefBehavior(Function *F, CallSite CS, 827 std::vector<PointerAccessInfo> *Info) { 828 if (!F->isExternal()) return UnknownModRefBehavior; 829 830 static bool Initialized = false; 831 if (!Initialized) { 832 NoMemoryTable->insert(NoMemoryTable->end(), 833 DoesntAccessMemoryFns, 834 DoesntAccessMemoryFns+ 835 sizeof(DoesntAccessMemoryFns)/sizeof(DoesntAccessMemoryFns[0])); 836 837 OnlyReadsMemoryTable->insert(OnlyReadsMemoryTable->end(), 838 OnlyReadsMemoryFns, 839 OnlyReadsMemoryFns+ 840 sizeof(OnlyReadsMemoryFns)/sizeof(OnlyReadsMemoryFns[0])); 841#define GET_MODREF_BEHAVIOR 842#include "llvm/Intrinsics.gen" 843#undef GET_MODREF_BEHAVIOR 844 845 // Sort the table the first time through. 846 std::sort(NoMemoryTable->begin(), NoMemoryTable->end(), StringCompare()); 847 std::sort(OnlyReadsMemoryTable->begin(), OnlyReadsMemoryTable->end(), 848 StringCompare()); 849 Initialized = true; 850 } 851 852 std::vector<const char*>::iterator Ptr = 853 std::lower_bound(NoMemoryTable->begin(), NoMemoryTable->end(), 854 F->getName().c_str(), StringCompare()); 855 if (Ptr != NoMemoryTable->end() && *Ptr == F->getName()) 856 return DoesNotAccessMemory; 857 858 Ptr = std::lower_bound(OnlyReadsMemoryTable->begin(), 859 OnlyReadsMemoryTable->end(), 860 F->getName().c_str(), StringCompare()); 861 if (Ptr != OnlyReadsMemoryTable->end() && *Ptr == F->getName()) 862 return OnlyReadsMemory; 863 864 return UnknownModRefBehavior; 865} 866 867// Make sure that anything that uses AliasAnalysis pulls in this file... 868DEFINING_FILE_FOR(BasicAliasAnalysis) 869