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