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