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