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