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