BasicAliasAnalysis.cpp revision a5b31ca85686062408bca0f0a8aa43f9fe58e644
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::LongTy && V2->getType() != Type::LongTy) 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()->getPrimitiveSizeInBits() < 64) 462 C1 = ConstantExpr::getSignExtend(C1, Type::LongTy); 463 else if (C1->getType() == Type::ULongTy) 464 C1 = ConstantExpr::getBitCast(C1, Type::LongTy); 465 if (C2->getType()->getPrimitiveSizeInBits() < 64) 466 C2 = ConstantExpr::getSignExtend(C2, Type::LongTy); 467 else if (C2->getType() == Type::ULongTy) 468 C2 = ConstantExpr::getBitCast(C2, Type::LongTy); 469 return C1 == C2; 470 } 471 return false; 472} 473 474/// CheckGEPInstructions - Check two GEP instructions with known must-aliasing 475/// base pointers. This checks to see if the index expressions preclude the 476/// pointers from aliasing... 477AliasAnalysis::AliasResult 478BasicAliasAnalysis::CheckGEPInstructions( 479 const Type* BasePtr1Ty, std::vector<Value*> &GEP1Ops, unsigned G1S, 480 const Type *BasePtr2Ty, std::vector<Value*> &GEP2Ops, unsigned G2S) { 481 // We currently can't handle the case when the base pointers have different 482 // primitive types. Since this is uncommon anyway, we are happy being 483 // extremely conservative. 484 if (BasePtr1Ty != BasePtr2Ty) 485 return MayAlias; 486 487 const PointerType *GEPPointerTy = cast<PointerType>(BasePtr1Ty); 488 489 // Find the (possibly empty) initial sequence of equal values... which are not 490 // necessarily constants. 491 unsigned NumGEP1Operands = GEP1Ops.size(), NumGEP2Operands = GEP2Ops.size(); 492 unsigned MinOperands = std::min(NumGEP1Operands, NumGEP2Operands); 493 unsigned MaxOperands = std::max(NumGEP1Operands, NumGEP2Operands); 494 unsigned UnequalOper = 0; 495 while (UnequalOper != MinOperands && 496 IndexOperandsEqual(GEP1Ops[UnequalOper], GEP2Ops[UnequalOper])) { 497 // Advance through the type as we go... 498 ++UnequalOper; 499 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty)) 500 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[UnequalOper-1]); 501 else { 502 // If all operands equal each other, then the derived pointers must 503 // alias each other... 504 BasePtr1Ty = 0; 505 assert(UnequalOper == NumGEP1Operands && UnequalOper == NumGEP2Operands && 506 "Ran out of type nesting, but not out of operands?"); 507 return MustAlias; 508 } 509 } 510 511 // If we have seen all constant operands, and run out of indexes on one of the 512 // getelementptrs, check to see if the tail of the leftover one is all zeros. 513 // If so, return mustalias. 514 if (UnequalOper == MinOperands) { 515 if (GEP1Ops.size() < GEP2Ops.size()) std::swap(GEP1Ops, GEP2Ops); 516 517 bool AllAreZeros = true; 518 for (unsigned i = UnequalOper; i != MaxOperands; ++i) 519 if (!isa<Constant>(GEP1Ops[i]) || 520 !cast<Constant>(GEP1Ops[i])->isNullValue()) { 521 AllAreZeros = false; 522 break; 523 } 524 if (AllAreZeros) return MustAlias; 525 } 526 527 528 // So now we know that the indexes derived from the base pointers, 529 // which are known to alias, are different. We can still determine a 530 // no-alias result if there are differing constant pairs in the index 531 // chain. For example: 532 // A[i][0] != A[j][1] iff (&A[0][1]-&A[0][0] >= std::max(G1S, G2S)) 533 // 534 // We have to be careful here about array accesses. In particular, consider: 535 // A[1][0] vs A[0][i] 536 // In this case, we don't *know* that the array will be accessed in bounds: 537 // the index could even be negative. Because of this, we have to 538 // conservatively *give up* and return may alias. We disregard differing 539 // array subscripts that are followed by a variable index without going 540 // through a struct. 541 // 542 unsigned SizeMax = std::max(G1S, G2S); 543 if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work. 544 545 // Scan for the first operand that is constant and unequal in the 546 // two getelementptrs... 547 unsigned FirstConstantOper = UnequalOper; 548 for (; FirstConstantOper != MinOperands; ++FirstConstantOper) { 549 const Value *G1Oper = GEP1Ops[FirstConstantOper]; 550 const Value *G2Oper = GEP2Ops[FirstConstantOper]; 551 552 if (G1Oper != G2Oper) // Found non-equal constant indexes... 553 if (Constant *G1OC = dyn_cast<ConstantInt>(const_cast<Value*>(G1Oper))) 554 if (Constant *G2OC = dyn_cast<ConstantInt>(const_cast<Value*>(G2Oper))){ 555 if (G1OC->getType() != G2OC->getType()) { 556 // Sign extend both operands to long. 557 if (G1OC->getType()->getPrimitiveSizeInBits() < 64) 558 G1OC = ConstantExpr::getSignExtend(G1OC, Type::LongTy); 559 else if (G1OC->getType() == Type::ULongTy) 560 G1OC = ConstantExpr::getBitCast(G1OC, Type::LongTy); 561 if (G2OC->getType()->getPrimitiveSizeInBits() < 64) 562 G2OC = ConstantExpr::getSignExtend(G2OC, Type::LongTy); 563 else if (G2OC->getType() == Type::ULongTy) 564 G2OC = ConstantExpr::getBitCast(G2OC, Type::LongTy); 565 GEP1Ops[FirstConstantOper] = G1OC; 566 GEP2Ops[FirstConstantOper] = G2OC; 567 } 568 569 if (G1OC != G2OC) { 570 // Handle the "be careful" case above: if this is an array/packed 571 // subscript, scan for a subsequent variable array index. 572 if (isa<SequentialType>(BasePtr1Ty)) { 573 const Type *NextTy = 574 cast<SequentialType>(BasePtr1Ty)->getElementType(); 575 bool isBadCase = false; 576 577 for (unsigned Idx = FirstConstantOper+1; 578 Idx != MinOperands && isa<SequentialType>(NextTy); ++Idx) { 579 const Value *V1 = GEP1Ops[Idx], *V2 = GEP2Ops[Idx]; 580 if (!isa<Constant>(V1) || !isa<Constant>(V2)) { 581 isBadCase = true; 582 break; 583 } 584 NextTy = cast<SequentialType>(NextTy)->getElementType(); 585 } 586 587 if (isBadCase) G1OC = 0; 588 } 589 590 // Make sure they are comparable (ie, not constant expressions), and 591 // make sure the GEP with the smaller leading constant is GEP1. 592 if (G1OC) { 593 Constant *Compare = ConstantExpr::getSetGT(G1OC, G2OC); 594 if (ConstantBool *CV = dyn_cast<ConstantBool>(Compare)) { 595 if (CV->getValue()) // If they are comparable and G2 > G1 596 std::swap(GEP1Ops, GEP2Ops); // Make GEP1 < GEP2 597 break; 598 } 599 } 600 } 601 } 602 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(G1Oper); 603 } 604 605 // No shared constant operands, and we ran out of common operands. At this 606 // point, the GEP instructions have run through all of their operands, and we 607 // haven't found evidence that there are any deltas between the GEP's. 608 // However, one GEP may have more operands than the other. If this is the 609 // case, there may still be hope. Check this now. 610 if (FirstConstantOper == MinOperands) { 611 // Make GEP1Ops be the longer one if there is a longer one. 612 if (GEP1Ops.size() < GEP2Ops.size()) 613 std::swap(GEP1Ops, GEP2Ops); 614 615 // Is there anything to check? 616 if (GEP1Ops.size() > MinOperands) { 617 for (unsigned i = FirstConstantOper; i != MaxOperands; ++i) 618 if (isa<ConstantInt>(GEP1Ops[i]) && 619 !cast<Constant>(GEP1Ops[i])->isNullValue()) { 620 // Yup, there's a constant in the tail. Set all variables to 621 // constants in the GEP instruction to make it suiteable for 622 // TargetData::getIndexedOffset. 623 for (i = 0; i != MaxOperands; ++i) 624 if (!isa<ConstantInt>(GEP1Ops[i])) 625 GEP1Ops[i] = Constant::getNullValue(GEP1Ops[i]->getType()); 626 // Okay, now get the offset. This is the relative offset for the full 627 // instruction. 628 const TargetData &TD = getTargetData(); 629 int64_t Offset1 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops); 630 631 // Now crop off any constants from the end... 632 GEP1Ops.resize(MinOperands); 633 int64_t Offset2 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops); 634 635 // If the tail provided a bit enough offset, return noalias! 636 if ((uint64_t)(Offset2-Offset1) >= SizeMax) 637 return NoAlias; 638 } 639 } 640 641 // Couldn't find anything useful. 642 return MayAlias; 643 } 644 645 // If there are non-equal constants arguments, then we can figure 646 // out a minimum known delta between the two index expressions... at 647 // this point we know that the first constant index of GEP1 is less 648 // than the first constant index of GEP2. 649 650 // Advance BasePtr[12]Ty over this first differing constant operand. 651 BasePtr2Ty = cast<CompositeType>(BasePtr1Ty)-> 652 getTypeAtIndex(GEP2Ops[FirstConstantOper]); 653 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)-> 654 getTypeAtIndex(GEP1Ops[FirstConstantOper]); 655 656 // We are going to be using TargetData::getIndexedOffset to determine the 657 // offset that each of the GEP's is reaching. To do this, we have to convert 658 // all variable references to constant references. To do this, we convert the 659 // initial sequence of array subscripts into constant zeros to start with. 660 const Type *ZeroIdxTy = GEPPointerTy; 661 for (unsigned i = 0; i != FirstConstantOper; ++i) { 662 if (!isa<StructType>(ZeroIdxTy)) 663 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Type::UIntTy); 664 665 if (const CompositeType *CT = dyn_cast<CompositeType>(ZeroIdxTy)) 666 ZeroIdxTy = CT->getTypeAtIndex(GEP1Ops[i]); 667 } 668 669 // We know that GEP1Ops[FirstConstantOper] & GEP2Ops[FirstConstantOper] are ok 670 671 // Loop over the rest of the operands... 672 for (unsigned i = FirstConstantOper+1; i != MaxOperands; ++i) { 673 const Value *Op1 = i < GEP1Ops.size() ? GEP1Ops[i] : 0; 674 const Value *Op2 = i < GEP2Ops.size() ? GEP2Ops[i] : 0; 675 // If they are equal, use a zero index... 676 if (Op1 == Op2 && BasePtr1Ty == BasePtr2Ty) { 677 if (!isa<ConstantInt>(Op1)) 678 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Op1->getType()); 679 // Otherwise, just keep the constants we have. 680 } else { 681 if (Op1) { 682 if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) { 683 // If this is an array index, make sure the array element is in range. 684 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) { 685 if (Op1C->getZExtValue() >= AT->getNumElements()) 686 return MayAlias; // Be conservative with out-of-range accesses 687 } else if (const PackedType *PT = dyn_cast<PackedType>(BasePtr1Ty)) { 688 if (Op1C->getZExtValue() >= PT->getNumElements()) 689 return MayAlias; // Be conservative with out-of-range accesses 690 } 691 692 } else { 693 // GEP1 is known to produce a value less than GEP2. To be 694 // conservatively correct, we must assume the largest possible 695 // constant is used in this position. This cannot be the initial 696 // index to the GEP instructions (because we know we have at least one 697 // element before this one with the different constant arguments), so 698 // we know that the current index must be into either a struct or 699 // array. Because we know it's not constant, this cannot be a 700 // structure index. Because of this, we can calculate the maximum 701 // value possible. 702 // 703 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) 704 GEP1Ops[i] = ConstantInt::get(Type::LongTy, AT->getNumElements()-1); 705 else if (const PackedType *PT = dyn_cast<PackedType>(BasePtr1Ty)) 706 GEP1Ops[i] = ConstantInt::get(Type::LongTy, PT->getNumElements()-1); 707 708 } 709 } 710 711 if (Op2) { 712 if (const ConstantInt *Op2C = dyn_cast<ConstantInt>(Op2)) { 713 // If this is an array index, make sure the array element is in range. 714 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) { 715 if (Op2C->getZExtValue() >= AT->getNumElements()) 716 return MayAlias; // Be conservative with out-of-range accesses 717 } else if (const PackedType *PT = dyn_cast<PackedType>(BasePtr1Ty)) { 718 if (Op2C->getZExtValue() >= PT->getNumElements()) 719 return MayAlias; // Be conservative with out-of-range accesses 720 } 721 } else { // Conservatively assume the minimum value for this index 722 GEP2Ops[i] = Constant::getNullValue(Op2->getType()); 723 } 724 } 725 } 726 727 if (BasePtr1Ty && Op1) { 728 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty)) 729 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[i]); 730 else 731 BasePtr1Ty = 0; 732 } 733 734 if (BasePtr2Ty && Op2) { 735 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr2Ty)) 736 BasePtr2Ty = CT->getTypeAtIndex(GEP2Ops[i]); 737 else 738 BasePtr2Ty = 0; 739 } 740 } 741 742 if (GEPPointerTy->getElementType()->isSized()) { 743 int64_t Offset1 = getTargetData().getIndexedOffset(GEPPointerTy, GEP1Ops); 744 int64_t Offset2 = getTargetData().getIndexedOffset(GEPPointerTy, GEP2Ops); 745 assert(Offset1<Offset2 && "There is at least one different constant here!"); 746 747 if ((uint64_t)(Offset2-Offset1) >= SizeMax) { 748 //llvm_cerr << "Determined that these two GEP's don't alias [" 749 // << SizeMax << " bytes]: \n" << *GEP1 << *GEP2; 750 return NoAlias; 751 } 752 } 753 return MayAlias; 754} 755 756namespace { 757 struct StringCompare { 758 bool operator()(const char *LHS, const char *RHS) { 759 return strcmp(LHS, RHS) < 0; 760 } 761 }; 762} 763 764// Note that this list cannot contain libm functions (such as acos and sqrt) 765// that set errno on a domain or other error. 766static const char *DoesntAccessMemoryFns[] = { 767 "abs", "labs", "llabs", "imaxabs", "fabs", "fabsf", "fabsl", 768 "trunc", "truncf", "truncl", "ldexp", 769 770 "atan", "atanf", "atanl", "atan2", "atan2f", "atan2l", 771 "cbrt", 772 "cos", "cosf", "cosl", 773 "exp", "expf", "expl", 774 "hypot", 775 "sin", "sinf", "sinl", 776 "tan", "tanf", "tanl", "tanh", "tanhf", "tanhl", 777 778 "floor", "floorf", "floorl", "ceil", "ceilf", "ceill", 779 780 // ctype.h 781 "isalnum", "isalpha", "iscntrl", "isdigit", "isgraph", "islower", "isprint" 782 "ispunct", "isspace", "isupper", "isxdigit", "tolower", "toupper", 783 784 // wctype.h" 785 "iswalnum", "iswalpha", "iswcntrl", "iswdigit", "iswgraph", "iswlower", 786 "iswprint", "iswpunct", "iswspace", "iswupper", "iswxdigit", 787 788 "iswctype", "towctrans", "towlower", "towupper", 789 790 "btowc", "wctob", 791 792 "isinf", "isnan", "finite", 793 794 // C99 math functions 795 "copysign", "copysignf", "copysignd", 796 "nexttoward", "nexttowardf", "nexttowardd", 797 "nextafter", "nextafterf", "nextafterd", 798 799 // ISO C99: 800 "__signbit", "__signbitf", "__signbitl", 801}; 802 803 804static const char *OnlyReadsMemoryFns[] = { 805 "atoi", "atol", "atof", "atoll", "atoq", "a64l", 806 "bcmp", "memcmp", "memchr", "memrchr", "wmemcmp", "wmemchr", 807 808 // Strings 809 "strcmp", "strcasecmp", "strcoll", "strncmp", "strncasecmp", 810 "strchr", "strcspn", "strlen", "strpbrk", "strrchr", "strspn", "strstr", 811 "index", "rindex", 812 813 // Wide char strings 814 "wcschr", "wcscmp", "wcscoll", "wcscspn", "wcslen", "wcsncmp", "wcspbrk", 815 "wcsrchr", "wcsspn", "wcsstr", 816 817 // glibc 818 "alphasort", "alphasort64", "versionsort", "versionsort64", 819 820 // C99 821 "nan", "nanf", "nand", 822 823 // File I/O 824 "feof", "ferror", "fileno", 825 "feof_unlocked", "ferror_unlocked", "fileno_unlocked" 826}; 827 828static ManagedStatic<std::vector<const char*> > NoMemoryTable; 829static ManagedStatic<std::vector<const char*> > OnlyReadsMemoryTable; 830 831 832AliasAnalysis::ModRefBehavior 833BasicAliasAnalysis::getModRefBehavior(Function *F, CallSite CS, 834 std::vector<PointerAccessInfo> *Info) { 835 if (!F->isExternal()) return UnknownModRefBehavior; 836 837 static bool Initialized = false; 838 if (!Initialized) { 839 NoMemoryTable->insert(NoMemoryTable->end(), 840 DoesntAccessMemoryFns, 841 DoesntAccessMemoryFns+ 842 sizeof(DoesntAccessMemoryFns)/sizeof(DoesntAccessMemoryFns[0])); 843 844 OnlyReadsMemoryTable->insert(OnlyReadsMemoryTable->end(), 845 OnlyReadsMemoryFns, 846 OnlyReadsMemoryFns+ 847 sizeof(OnlyReadsMemoryFns)/sizeof(OnlyReadsMemoryFns[0])); 848#define GET_MODREF_BEHAVIOR 849#include "llvm/Intrinsics.gen" 850#undef GET_MODREF_BEHAVIOR 851 852 // Sort the table the first time through. 853 std::sort(NoMemoryTable->begin(), NoMemoryTable->end(), StringCompare()); 854 std::sort(OnlyReadsMemoryTable->begin(), OnlyReadsMemoryTable->end(), 855 StringCompare()); 856 Initialized = true; 857 } 858 859 std::vector<const char*>::iterator Ptr = 860 std::lower_bound(NoMemoryTable->begin(), NoMemoryTable->end(), 861 F->getName().c_str(), StringCompare()); 862 if (Ptr != NoMemoryTable->end() && *Ptr == F->getName()) 863 return DoesNotAccessMemory; 864 865 Ptr = std::lower_bound(OnlyReadsMemoryTable->begin(), 866 OnlyReadsMemoryTable->end(), 867 F->getName().c_str(), StringCompare()); 868 if (Ptr != OnlyReadsMemoryTable->end() && *Ptr == F->getName()) 869 return OnlyReadsMemory; 870 871 return UnknownModRefBehavior; 872} 873 874// Make sure that anything that uses AliasAnalysis pulls in this file... 875DEFINING_FILE_FOR(BasicAliasAnalysis) 876