BasicAliasAnalysis.cpp revision 7765d71304f0f26ab348deb41af9b6ae033aae4d
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// hasUniqueAddress - Return true if the specified value points to something 133// with a unique, discernable, address. 134static inline bool hasUniqueAddress(const Value *V) { 135 return isa<GlobalValue>(V) || isa<AllocationInst>(V); 136} 137 138// getUnderlyingObject - This traverses the use chain to figure out what object 139// the specified value points to. If the value points to, or is derived from, a 140// unique object or an argument, return it. 141static const Value *getUnderlyingObject(const Value *V) { 142 if (!isa<PointerType>(V->getType())) return 0; 143 144 // If we are at some type of object... return it. 145 if (hasUniqueAddress(V) || isa<Argument>(V)) return V; 146 147 // Traverse through different addressing mechanisms... 148 if (const Instruction *I = dyn_cast<Instruction>(V)) { 149 if (isa<CastInst>(I) || isa<GetElementPtrInst>(I)) 150 return getUnderlyingObject(I->getOperand(0)); 151 } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { 152 if (CE->getOpcode() == Instruction::Cast || 153 CE->getOpcode() == Instruction::GetElementPtr) 154 return getUnderlyingObject(CE->getOperand(0)); 155 } else if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) { 156 return GV; 157 } 158 return 0; 159} 160 161static const User *isGEP(const Value *V) { 162 if (isa<GetElementPtrInst>(V) || 163 (isa<ConstantExpr>(V) && 164 cast<ConstantExpr>(V)->getOpcode() == Instruction::GetElementPtr)) 165 return cast<User>(V); 166 return 0; 167} 168 169static const Value *GetGEPOperands(const Value *V, std::vector<Value*> &GEPOps){ 170 assert(GEPOps.empty() && "Expect empty list to populate!"); 171 GEPOps.insert(GEPOps.end(), cast<User>(V)->op_begin()+1, 172 cast<User>(V)->op_end()); 173 174 // Accumulate all of the chained indexes into the operand array 175 V = cast<User>(V)->getOperand(0); 176 177 while (const User *G = isGEP(V)) { 178 if (!isa<Constant>(GEPOps[0]) || isa<GlobalValue>(GEPOps[0]) || 179 !cast<Constant>(GEPOps[0])->isNullValue()) 180 break; // Don't handle folding arbitrary pointer offsets yet... 181 GEPOps.erase(GEPOps.begin()); // Drop the zero index 182 GEPOps.insert(GEPOps.begin(), G->op_begin()+1, G->op_end()); 183 V = G->getOperand(0); 184 } 185 return V; 186} 187 188/// pointsToConstantMemory - Chase pointers until we find a (constant 189/// global) or not. 190bool BasicAliasAnalysis::pointsToConstantMemory(const Value *P) { 191 if (const Value *V = getUnderlyingObject(P)) 192 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) 193 return GV->isConstant(); 194 return false; 195} 196 197static bool AddressMightEscape(const Value *V) { 198 for (Value::use_const_iterator UI = V->use_begin(), E = V->use_end(); 199 UI != E; ++UI) { 200 const Instruction *I = cast<Instruction>(*UI); 201 switch (I->getOpcode()) { 202 case Instruction::Load: break; 203 case Instruction::Store: 204 if (I->getOperand(0) == V) 205 return true; // Escapes if the pointer is stored. 206 break; 207 case Instruction::GetElementPtr: 208 if (AddressMightEscape(I)) return true; 209 break; 210 case Instruction::Cast: 211 if (!isa<PointerType>(I->getType())) 212 return true; 213 if (AddressMightEscape(I)) return true; 214 break; 215 case Instruction::Ret: 216 // If returned, the address will escape to calling functions, but no 217 // callees could modify it. 218 break; 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->getOpcode() == Instruction::Cast && 263 isa<PointerType>(CE->getOperand(0)->getType())) 264 V1 = CE->getOperand(0); 265 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V2)) 266 if (CE->getOpcode() == Instruction::Cast && 267 isa<PointerType>(CE->getOperand(0)->getType())) 268 V2 = CE->getOperand(0); 269 270 // Are we checking for alias of the same value? 271 if (V1 == V2) return MustAlias; 272 273 if ((!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType())) && 274 V1->getType() != Type::LongTy && V2->getType() != Type::LongTy) 275 return NoAlias; // Scalars cannot alias each other 276 277 // Strip off cast instructions... 278 if (const Instruction *I = dyn_cast<CastInst>(V1)) 279 if (isa<PointerType>(I->getOperand(0)->getType())) 280 return alias(I->getOperand(0), V1Size, V2, V2Size); 281 if (const Instruction *I = dyn_cast<CastInst>(V2)) 282 if (isa<PointerType>(I->getOperand(0)->getType())) 283 return alias(V1, V1Size, I->getOperand(0), V2Size); 284 285 // Figure out what objects these things are pointing to if we can... 286 const Value *O1 = getUnderlyingObject(V1); 287 const Value *O2 = getUnderlyingObject(V2); 288 289 // Pointing at a discernible object? 290 if (O1) { 291 if (O2) { 292 if (isa<Argument>(O1)) { 293 // Incoming argument cannot alias locally allocated object! 294 if (isa<AllocationInst>(O2)) return NoAlias; 295 // Otherwise, nothing is known... 296 } else if (isa<Argument>(O2)) { 297 // Incoming argument cannot alias locally allocated object! 298 if (isa<AllocationInst>(O1)) return NoAlias; 299 // Otherwise, nothing is known... 300 } else if (O1 != O2) { 301 // If they are two different objects, we know that we have no alias... 302 return NoAlias; 303 } 304 305 // If they are the same object, they we can look at the indexes. If they 306 // index off of the object is the same for both pointers, they must alias. 307 // If they are provably different, they must not alias. Otherwise, we 308 // can't tell anything. 309 } 310 311 312 if (!isa<Argument>(O1) && isa<ConstantPointerNull>(V2)) 313 return NoAlias; // Unique values don't alias null 314 315 if (isa<GlobalVariable>(O1) || 316 (isa<AllocationInst>(O1) && 317 !cast<AllocationInst>(O1)->isArrayAllocation())) 318 if (cast<PointerType>(O1->getType())->getElementType()->isSized()) { 319 // If the size of the other access is larger than the total size of the 320 // global/alloca/malloc, it cannot be accessing the global (it's 321 // undefined to load or store bytes before or after an object). 322 const Type *ElTy = cast<PointerType>(O1->getType())->getElementType(); 323 unsigned GlobalSize = getTargetData().getTypeSize(ElTy); 324 if (GlobalSize < V2Size && V2Size != ~0U) 325 return NoAlias; 326 } 327 } 328 329 if (O2) { 330 if (!isa<Argument>(O2) && isa<ConstantPointerNull>(V1)) 331 return NoAlias; // Unique values don't alias null 332 333 if (isa<GlobalVariable>(O2) || 334 (isa<AllocationInst>(O2) && 335 !cast<AllocationInst>(O2)->isArrayAllocation())) 336 if (cast<PointerType>(O2->getType())->getElementType()->isSized()) { 337 // If the size of the other access is larger than the total size of the 338 // global/alloca/malloc, it cannot be accessing the object (it's 339 // undefined to load or store bytes before or after an object). 340 const Type *ElTy = cast<PointerType>(O2->getType())->getElementType(); 341 unsigned GlobalSize = getTargetData().getTypeSize(ElTy); 342 if (GlobalSize < V1Size && V1Size != ~0U) 343 return NoAlias; 344 } 345 } 346 347 // If we have two gep instructions with must-alias'ing base pointers, figure 348 // out if the indexes to the GEP tell us anything about the derived pointer. 349 // Note that we also handle chains of getelementptr instructions as well as 350 // constant expression getelementptrs here. 351 // 352 if (isGEP(V1) && isGEP(V2)) { 353 // Drill down into the first non-gep value, to test for must-aliasing of 354 // the base pointers. 355 const Value *BasePtr1 = V1, *BasePtr2 = V2; 356 do { 357 BasePtr1 = cast<User>(BasePtr1)->getOperand(0); 358 } while (isGEP(BasePtr1) && 359 cast<User>(BasePtr1)->getOperand(1) == 360 Constant::getNullValue(cast<User>(BasePtr1)->getOperand(1)->getType())); 361 do { 362 BasePtr2 = cast<User>(BasePtr2)->getOperand(0); 363 } while (isGEP(BasePtr2) && 364 cast<User>(BasePtr2)->getOperand(1) == 365 Constant::getNullValue(cast<User>(BasePtr2)->getOperand(1)->getType())); 366 367 // Do the base pointers alias? 368 AliasResult BaseAlias = alias(BasePtr1, V1Size, BasePtr2, V2Size); 369 if (BaseAlias == NoAlias) return NoAlias; 370 if (BaseAlias == MustAlias) { 371 // If the base pointers alias each other exactly, check to see if we can 372 // figure out anything about the resultant pointers, to try to prove 373 // non-aliasing. 374 375 // Collect all of the chained GEP operands together into one simple place 376 std::vector<Value*> GEP1Ops, GEP2Ops; 377 BasePtr1 = GetGEPOperands(V1, GEP1Ops); 378 BasePtr2 = GetGEPOperands(V2, GEP2Ops); 379 380 // If GetGEPOperands were able to fold to the same must-aliased pointer, 381 // do the comparison. 382 if (BasePtr1 == BasePtr2) { 383 AliasResult GAlias = 384 CheckGEPInstructions(BasePtr1->getType(), GEP1Ops, V1Size, 385 BasePtr2->getType(), GEP2Ops, V2Size); 386 if (GAlias != MayAlias) 387 return GAlias; 388 } 389 } 390 } 391 392 // Check to see if these two pointers are related by a getelementptr 393 // instruction. If one pointer is a GEP with a non-zero index of the other 394 // pointer, we know they cannot alias. 395 // 396 if (isGEP(V2)) { 397 std::swap(V1, V2); 398 std::swap(V1Size, V2Size); 399 } 400 401 if (V1Size != ~0U && V2Size != ~0U) 402 if (isGEP(V1)) { 403 std::vector<Value*> GEPOperands; 404 const Value *BasePtr = GetGEPOperands(V1, GEPOperands); 405 406 AliasResult R = alias(BasePtr, V1Size, V2, V2Size); 407 if (R == MustAlias) { 408 // If there is at least one non-zero constant index, we know they cannot 409 // alias. 410 bool ConstantFound = false; 411 bool AllZerosFound = true; 412 for (unsigned i = 0, e = GEPOperands.size(); i != e; ++i) 413 if (const Constant *C = dyn_cast<Constant>(GEPOperands[i])) { 414 if (!C->isNullValue()) { 415 ConstantFound = true; 416 AllZerosFound = false; 417 break; 418 } 419 } else { 420 AllZerosFound = false; 421 } 422 423 // If we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 must aliases 424 // the ptr, the end result is a must alias also. 425 if (AllZerosFound) 426 return MustAlias; 427 428 if (ConstantFound) { 429 if (V2Size <= 1 && V1Size <= 1) // Just pointer check? 430 return NoAlias; 431 432 // Otherwise we have to check to see that the distance is more than 433 // the size of the argument... build an index vector that is equal to 434 // the arguments provided, except substitute 0's for any variable 435 // indexes we find... 436 if (cast<PointerType>( 437 BasePtr->getType())->getElementType()->isSized()) { 438 for (unsigned i = 0; i != GEPOperands.size(); ++i) 439 if (!isa<ConstantInt>(GEPOperands[i])) 440 GEPOperands[i] = 441 Constant::getNullValue(GEPOperands[i]->getType()); 442 int64_t Offset = 443 getTargetData().getIndexedOffset(BasePtr->getType(), GEPOperands); 444 445 if (Offset >= (int64_t)V2Size || Offset <= -(int64_t)V1Size) 446 return NoAlias; 447 } 448 } 449 } 450 } 451 452 return MayAlias; 453} 454 455static bool ValuesEqual(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. 461 C1 = ConstantExpr::getSignExtend(C1, Type::LongTy); 462 C2 = ConstantExpr::getSignExtend(C2, Type::LongTy); 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 ValuesEqual(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 G1OC = ConstantExpr::getSignExtend(G1OC, Type::LongTy); 552 G2OC = ConstantExpr::getSignExtend(G2OC, Type::LongTy); 553 GEP1Ops[FirstConstantOper] = G1OC; 554 GEP2Ops[FirstConstantOper] = G2OC; 555 } 556 557 if (G1OC != G2OC) { 558 // Handle the "be careful" case above: if this is an array/packed 559 // subscript, scan for a subsequent variable array index. 560 if (isa<SequentialType>(BasePtr1Ty)) { 561 const Type *NextTy = 562 cast<SequentialType>(BasePtr1Ty)->getElementType(); 563 bool isBadCase = false; 564 565 for (unsigned Idx = FirstConstantOper+1; 566 Idx != MinOperands && isa<SequentialType>(NextTy); ++Idx) { 567 const Value *V1 = GEP1Ops[Idx], *V2 = GEP2Ops[Idx]; 568 if (!isa<Constant>(V1) || !isa<Constant>(V2)) { 569 isBadCase = true; 570 break; 571 } 572 NextTy = cast<SequentialType>(NextTy)->getElementType(); 573 } 574 575 if (isBadCase) G1OC = 0; 576 } 577 578 // Make sure they are comparable (ie, not constant expressions), and 579 // make sure the GEP with the smaller leading constant is GEP1. 580 if (G1OC) { 581 Constant *Compare = ConstantExpr::getSetGT(G1OC, G2OC); 582 if (ConstantBool *CV = dyn_cast<ConstantBool>(Compare)) { 583 if (CV->getValue()) // If they are comparable and G2 > G1 584 std::swap(GEP1Ops, GEP2Ops); // Make GEP1 < GEP2 585 break; 586 } 587 } 588 } 589 } 590 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(G1Oper); 591 } 592 593 // No shared constant operands, and we ran out of common operands. At this 594 // point, the GEP instructions have run through all of their operands, and we 595 // haven't found evidence that there are any deltas between the GEP's. 596 // However, one GEP may have more operands than the other. If this is the 597 // case, there may still be hope. Check this now. 598 if (FirstConstantOper == MinOperands) { 599 // Make GEP1Ops be the longer one if there is a longer one. 600 if (GEP1Ops.size() < GEP2Ops.size()) 601 std::swap(GEP1Ops, GEP2Ops); 602 603 // Is there anything to check? 604 if (GEP1Ops.size() > MinOperands) { 605 for (unsigned i = FirstConstantOper; i != MaxOperands; ++i) 606 if (isa<ConstantInt>(GEP1Ops[i]) && 607 !cast<Constant>(GEP1Ops[i])->isNullValue()) { 608 // Yup, there's a constant in the tail. Set all variables to 609 // constants in the GEP instruction to make it suiteable for 610 // TargetData::getIndexedOffset. 611 for (i = 0; i != MaxOperands; ++i) 612 if (!isa<ConstantInt>(GEP1Ops[i])) 613 GEP1Ops[i] = Constant::getNullValue(GEP1Ops[i]->getType()); 614 // Okay, now get the offset. This is the relative offset for the full 615 // instruction. 616 const TargetData &TD = getTargetData(); 617 int64_t Offset1 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops); 618 619 // Now crop off any constants from the end... 620 GEP1Ops.resize(MinOperands); 621 int64_t Offset2 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops); 622 623 // If the tail provided a bit enough offset, return noalias! 624 if ((uint64_t)(Offset2-Offset1) >= SizeMax) 625 return NoAlias; 626 } 627 } 628 629 // Couldn't find anything useful. 630 return MayAlias; 631 } 632 633 // If there are non-equal constants arguments, then we can figure 634 // out a minimum known delta between the two index expressions... at 635 // this point we know that the first constant index of GEP1 is less 636 // than the first constant index of GEP2. 637 638 // Advance BasePtr[12]Ty over this first differing constant operand. 639 BasePtr2Ty = cast<CompositeType>(BasePtr1Ty)-> 640 getTypeAtIndex(GEP2Ops[FirstConstantOper]); 641 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)-> 642 getTypeAtIndex(GEP1Ops[FirstConstantOper]); 643 644 // We are going to be using TargetData::getIndexedOffset to determine the 645 // offset that each of the GEP's is reaching. To do this, we have to convert 646 // all variable references to constant references. To do this, we convert the 647 // initial sequence of array subscripts into constant zeros to start with. 648 const Type *ZeroIdxTy = GEPPointerTy; 649 for (unsigned i = 0; i != FirstConstantOper; ++i) { 650 if (!isa<StructType>(ZeroIdxTy)) 651 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Type::UIntTy); 652 653 if (const CompositeType *CT = dyn_cast<CompositeType>(ZeroIdxTy)) 654 ZeroIdxTy = CT->getTypeAtIndex(GEP1Ops[i]); 655 } 656 657 // We know that GEP1Ops[FirstConstantOper] & GEP2Ops[FirstConstantOper] are ok 658 659 // Loop over the rest of the operands... 660 for (unsigned i = FirstConstantOper+1; i != MaxOperands; ++i) { 661 const Value *Op1 = i < GEP1Ops.size() ? GEP1Ops[i] : 0; 662 const Value *Op2 = i < GEP2Ops.size() ? GEP2Ops[i] : 0; 663 // If they are equal, use a zero index... 664 if (Op1 == Op2 && BasePtr1Ty == BasePtr2Ty) { 665 if (!isa<ConstantInt>(Op1)) 666 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Op1->getType()); 667 // Otherwise, just keep the constants we have. 668 } else { 669 if (Op1) { 670 if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) { 671 // If this is an array index, make sure the array element is in range. 672 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) { 673 if (Op1C->getZExtValue() >= AT->getNumElements()) 674 return MayAlias; // Be conservative with out-of-range accesses 675 } else if (const PackedType *PT = dyn_cast<PackedType>(BasePtr1Ty)) { 676 if (Op1C->getZExtValue() >= PT->getNumElements()) 677 return MayAlias; // Be conservative with out-of-range accesses 678 } 679 680 } else { 681 // GEP1 is known to produce a value less than GEP2. To be 682 // conservatively correct, we must assume the largest possible 683 // constant is used in this position. This cannot be the initial 684 // index to the GEP instructions (because we know we have at least one 685 // element before this one with the different constant arguments), so 686 // we know that the current index must be into either a struct or 687 // array. Because we know it's not constant, this cannot be a 688 // structure index. Because of this, we can calculate the maximum 689 // value possible. 690 // 691 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) 692 GEP1Ops[i] = ConstantInt::get(Type::LongTy, AT->getNumElements()-1); 693 else if (const PackedType *PT = dyn_cast<PackedType>(BasePtr1Ty)) 694 GEP1Ops[i] = ConstantInt::get(Type::LongTy, PT->getNumElements()-1); 695 696 } 697 } 698 699 if (Op2) { 700 if (const ConstantInt *Op2C = dyn_cast<ConstantInt>(Op2)) { 701 // If this is an array index, make sure the array element is in range. 702 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) { 703 if (Op2C->getZExtValue() >= AT->getNumElements()) 704 return MayAlias; // Be conservative with out-of-range accesses 705 } else if (const PackedType *PT = dyn_cast<PackedType>(BasePtr1Ty)) { 706 if (Op2C->getZExtValue() >= PT->getNumElements()) 707 return MayAlias; // Be conservative with out-of-range accesses 708 } 709 } else { // Conservatively assume the minimum value for this index 710 GEP2Ops[i] = Constant::getNullValue(Op2->getType()); 711 } 712 } 713 } 714 715 if (BasePtr1Ty && Op1) { 716 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty)) 717 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[i]); 718 else 719 BasePtr1Ty = 0; 720 } 721 722 if (BasePtr2Ty && Op2) { 723 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr2Ty)) 724 BasePtr2Ty = CT->getTypeAtIndex(GEP2Ops[i]); 725 else 726 BasePtr2Ty = 0; 727 } 728 } 729 730 if (GEPPointerTy->getElementType()->isSized()) { 731 int64_t Offset1 = getTargetData().getIndexedOffset(GEPPointerTy, GEP1Ops); 732 int64_t Offset2 = getTargetData().getIndexedOffset(GEPPointerTy, GEP2Ops); 733 assert(Offset1<Offset2 && "There is at least one different constant here!"); 734 735 if ((uint64_t)(Offset2-Offset1) >= SizeMax) { 736 //std::cerr << "Determined that these two GEP's don't alias [" 737 // << SizeMax << " bytes]: \n" << *GEP1 << *GEP2; 738 return NoAlias; 739 } 740 } 741 return MayAlias; 742} 743 744namespace { 745 struct StringCompare { 746 bool operator()(const char *LHS, const char *RHS) { 747 return strcmp(LHS, RHS) < 0; 748 } 749 }; 750} 751 752// Note that this list cannot contain libm functions (such as acos and sqrt) 753// that set errno on a domain or other error. 754static const char *DoesntAccessMemoryFns[] = { 755 "abs", "labs", "llabs", "imaxabs", "fabs", "fabsf", "fabsl", 756 "trunc", "truncf", "truncl", "ldexp", 757 758 "atan", "atanf", "atanl", "atan2", "atan2f", "atan2l", 759 "cbrt", 760 "cos", "cosf", "cosl", 761 "exp", "expf", "expl", 762 "hypot", 763 "sin", "sinf", "sinl", 764 "tan", "tanf", "tanl", "tanh", "tanhf", "tanhl", 765 766 "floor", "floorf", "floorl", "ceil", "ceilf", "ceill", 767 768 // ctype.h 769 "isalnum", "isalpha", "iscntrl", "isdigit", "isgraph", "islower", "isprint" 770 "ispunct", "isspace", "isupper", "isxdigit", "tolower", "toupper", 771 772 // wctype.h" 773 "iswalnum", "iswalpha", "iswcntrl", "iswdigit", "iswgraph", "iswlower", 774 "iswprint", "iswpunct", "iswspace", "iswupper", "iswxdigit", 775 776 "iswctype", "towctrans", "towlower", "towupper", 777 778 "btowc", "wctob", 779 780 "isinf", "isnan", "finite", 781 782 // C99 math functions 783 "copysign", "copysignf", "copysignd", 784 "nexttoward", "nexttowardf", "nexttowardd", 785 "nextafter", "nextafterf", "nextafterd", 786 787 // ISO C99: 788 "__signbit", "__signbitf", "__signbitl", 789}; 790 791 792static const char *OnlyReadsMemoryFns[] = { 793 "atoi", "atol", "atof", "atoll", "atoq", "a64l", 794 "bcmp", "memcmp", "memchr", "memrchr", "wmemcmp", "wmemchr", 795 796 // Strings 797 "strcmp", "strcasecmp", "strcoll", "strncmp", "strncasecmp", 798 "strchr", "strcspn", "strlen", "strpbrk", "strrchr", "strspn", "strstr", 799 "index", "rindex", 800 801 // Wide char strings 802 "wcschr", "wcscmp", "wcscoll", "wcscspn", "wcslen", "wcsncmp", "wcspbrk", 803 "wcsrchr", "wcsspn", "wcsstr", 804 805 // glibc 806 "alphasort", "alphasort64", "versionsort", "versionsort64", 807 808 // C99 809 "nan", "nanf", "nand", 810 811 // File I/O 812 "feof", "ferror", "fileno", 813 "feof_unlocked", "ferror_unlocked", "fileno_unlocked" 814}; 815 816static ManagedStatic<std::vector<const char*> > NoMemoryTable; 817static ManagedStatic<std::vector<const char*> > OnlyReadsMemoryTable; 818 819 820AliasAnalysis::ModRefBehavior 821BasicAliasAnalysis::getModRefBehavior(Function *F, CallSite CS, 822 std::vector<PointerAccessInfo> *Info) { 823 if (!F->isExternal()) return UnknownModRefBehavior; 824 825 static bool Initialized = false; 826 if (!Initialized) { 827 NoMemoryTable->insert(NoMemoryTable->end(), 828 DoesntAccessMemoryFns, 829 DoesntAccessMemoryFns+ 830 sizeof(DoesntAccessMemoryFns)/sizeof(DoesntAccessMemoryFns[0])); 831 832 OnlyReadsMemoryTable->insert(OnlyReadsMemoryTable->end(), 833 OnlyReadsMemoryFns, 834 OnlyReadsMemoryFns+ 835 sizeof(OnlyReadsMemoryFns)/sizeof(OnlyReadsMemoryFns[0])); 836#define GET_MODREF_BEHAVIOR 837#include "llvm/Intrinsics.gen" 838#undef GET_MODREF_BEHAVIOR 839 840 // Sort the table the first time through. 841 std::sort(NoMemoryTable->begin(), NoMemoryTable->end(), StringCompare()); 842 std::sort(OnlyReadsMemoryTable->begin(), OnlyReadsMemoryTable->end(), 843 StringCompare()); 844 Initialized = true; 845 } 846 847 std::vector<const char*>::iterator Ptr = 848 std::lower_bound(NoMemoryTable->begin(), NoMemoryTable->end(), 849 F->getName().c_str(), StringCompare()); 850 if (Ptr != NoMemoryTable->end() && *Ptr == F->getName()) 851 return DoesNotAccessMemory; 852 853 Ptr = std::lower_bound(OnlyReadsMemoryTable->begin(), 854 OnlyReadsMemoryTable->end(), 855 F->getName().c_str(), StringCompare()); 856 if (Ptr != OnlyReadsMemoryTable->end() && *Ptr == F->getName()) 857 return OnlyReadsMemory; 858 859 return UnknownModRefBehavior; 860} 861 862// Make sure that anything that uses AliasAnalysis pulls in this file... 863DEFINING_FILE_FOR(BasicAliasAnalysis) 864