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