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