BasicAliasAnalysis.cpp revision 845f0d2f0fd4a268ca1b3df9afb3de523f6dfa9d
1//===- BasicAliasAnalysis.cpp - Local Alias Analysis Impl -----------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// 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/IntrinsicInst.h" 25#include "llvm/Pass.h" 26#include "llvm/Target/TargetData.h" 27#include "llvm/ADT/SmallVector.h" 28#include "llvm/ADT/STLExtras.h" 29#include "llvm/Support/Compiler.h" 30#include "llvm/Support/GetElementPtrTypeIterator.h" 31#include "llvm/Support/ManagedStatic.h" 32#include <algorithm> 33using namespace llvm; 34 35namespace { 36 /// NoAA - This class implements the -no-aa pass, which always returns "I 37 /// don't know" for alias queries. NoAA is unlike other alias analysis 38 /// implementations, in that it does not chain to a previous analysis. As 39 /// such it doesn't follow many of the rules that other alias analyses must. 40 /// 41 struct VISIBILITY_HIDDEN NoAA : public ImmutablePass, public AliasAnalysis { 42 static char ID; // Class identification, replacement for typeinfo 43 NoAA() : ImmutablePass((intptr_t)&ID) {} 44 explicit NoAA(intptr_t PID) : ImmutablePass(PID) { } 45 46 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 47 AU.addRequired<TargetData>(); 48 } 49 50 virtual void initializePass() { 51 TD = &getAnalysis<TargetData>(); 52 } 53 54 virtual AliasResult alias(const Value *V1, unsigned V1Size, 55 const Value *V2, unsigned V2Size) { 56 return MayAlias; 57 } 58 59 virtual ModRefBehavior getModRefBehavior(Function *F, CallSite CS, 60 std::vector<PointerAccessInfo> *Info) { 61 return UnknownModRefBehavior; 62 } 63 64 virtual void getArgumentAccesses(Function *F, CallSite CS, 65 std::vector<PointerAccessInfo> &Info) { 66 assert(0 && "This method may not be called on this function!"); 67 } 68 69 virtual void getMustAliases(Value *P, std::vector<Value*> &RetVals) { } 70 virtual bool pointsToConstantMemory(const Value *P) { return false; } 71 virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size) { 72 return ModRef; 73 } 74 virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) { 75 return ModRef; 76 } 77 virtual bool hasNoModRefInfoForCalls() const { return true; } 78 79 virtual void deleteValue(Value *V) {} 80 virtual void copyValue(Value *From, Value *To) {} 81 }; 82} // End of anonymous namespace 83 84// Register this pass... 85char NoAA::ID = 0; 86static RegisterPass<NoAA> 87U("no-aa", "No Alias Analysis (always returns 'may' alias)", true, true); 88 89// Declare that we implement the AliasAnalysis interface 90static RegisterAnalysisGroup<AliasAnalysis> V(U); 91 92ImmutablePass *llvm::createNoAAPass() { return new NoAA(); } 93 94namespace { 95 /// BasicAliasAnalysis - This is the default alias analysis implementation. 96 /// Because it doesn't chain to a previous alias analysis (like -no-aa), it 97 /// derives from the NoAA class. 98 struct VISIBILITY_HIDDEN BasicAliasAnalysis : public NoAA { 99 static char ID; // Class identification, replacement for typeinfo 100 BasicAliasAnalysis() : NoAA((intptr_t)&ID) { } 101 AliasResult alias(const Value *V1, unsigned V1Size, 102 const Value *V2, unsigned V2Size); 103 104 ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size); 105 ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) { 106 return NoAA::getModRefInfo(CS1,CS2); 107 } 108 109 /// hasNoModRefInfoForCalls - We can provide mod/ref information against 110 /// non-escaping allocations. 111 virtual bool hasNoModRefInfoForCalls() const { return false; } 112 113 /// pointsToConstantMemory - Chase pointers until we find a (constant 114 /// global) or not. 115 bool pointsToConstantMemory(const Value *P); 116 117 private: 118 // CheckGEPInstructions - Check two GEP instructions with known 119 // must-aliasing base pointers. This checks to see if the index expressions 120 // preclude the pointers from aliasing... 121 AliasResult 122 CheckGEPInstructions(const Type* BasePtr1Ty, 123 Value **GEP1Ops, unsigned NumGEP1Ops, unsigned G1Size, 124 const Type *BasePtr2Ty, 125 Value **GEP2Ops, unsigned NumGEP2Ops, unsigned G2Size); 126 }; 127} // End of anonymous namespace 128 129// Register this pass... 130char BasicAliasAnalysis::ID = 0; 131static RegisterPass<BasicAliasAnalysis> 132X("basicaa", "Basic Alias Analysis (default AA impl)", false, true); 133 134// Declare that we implement the AliasAnalysis interface 135static RegisterAnalysisGroup<AliasAnalysis, true> Y(X); 136 137ImmutablePass *llvm::createBasicAliasAnalysisPass() { 138 return new BasicAliasAnalysis(); 139} 140 141/// getUnderlyingObject - This traverses the use chain to figure out what object 142/// the specified value points to. If the value points to, or is derived from, 143/// a unique object or an argument, return it. This returns: 144/// Arguments, GlobalVariables, Functions, Allocas, Mallocs. 145static const Value *getUnderlyingObject(const Value *V) { 146 if (!isa<PointerType>(V->getType())) return V; 147 148 // If we are at some type of object, return it. GlobalValues and Allocations 149 // have unique addresses. 150 if (isa<GlobalValue>(V) || isa<AllocationInst>(V) || isa<Argument>(V)) 151 return V; 152 153 // Traverse through different addressing mechanisms... 154 if (const Instruction *I = dyn_cast<Instruction>(V)) { 155 if (isa<BitCastInst>(I) || isa<GetElementPtrInst>(I)) 156 return getUnderlyingObject(I->getOperand(0)); 157 } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { 158 if (CE->getOpcode() == Instruction::BitCast || 159 CE->getOpcode() == Instruction::GetElementPtr) 160 return getUnderlyingObject(CE->getOperand(0)); 161 } 162 return V; 163} 164 165static const User *isGEP(const Value *V) { 166 if (isa<GetElementPtrInst>(V) || 167 (isa<ConstantExpr>(V) && 168 cast<ConstantExpr>(V)->getOpcode() == Instruction::GetElementPtr)) 169 return cast<User>(V); 170 return 0; 171} 172 173static const Value *GetGEPOperands(const Value *V, 174 SmallVector<Value*, 16> &GEPOps){ 175 assert(GEPOps.empty() && "Expect empty list to populate!"); 176 GEPOps.insert(GEPOps.end(), cast<User>(V)->op_begin()+1, 177 cast<User>(V)->op_end()); 178 179 // Accumulate all of the chained indexes into the operand array 180 V = cast<User>(V)->getOperand(0); 181 182 while (const User *G = isGEP(V)) { 183 if (!isa<Constant>(GEPOps[0]) || isa<GlobalValue>(GEPOps[0]) || 184 !cast<Constant>(GEPOps[0])->isNullValue()) 185 break; // Don't handle folding arbitrary pointer offsets yet... 186 GEPOps.erase(GEPOps.begin()); // Drop the zero index 187 GEPOps.insert(GEPOps.begin(), G->op_begin()+1, G->op_end()); 188 V = G->getOperand(0); 189 } 190 return V; 191} 192 193/// pointsToConstantMemory - Chase pointers until we find a (constant 194/// global) or not. 195bool BasicAliasAnalysis::pointsToConstantMemory(const Value *P) { 196 if (const GlobalVariable *GV = 197 dyn_cast<GlobalVariable>(getUnderlyingObject(P))) 198 return GV->isConstant(); 199 return false; 200} 201 202// Determine if an AllocationInst instruction escapes from the function it is 203// contained in. If it does not escape, there is no way for another function to 204// mod/ref it. We do this by looking at its uses and determining if the uses 205// can escape (recursively). 206static bool AddressMightEscape(const Value *V) { 207 for (Value::use_const_iterator UI = V->use_begin(), E = V->use_end(); 208 UI != E; ++UI) { 209 const Instruction *I = cast<Instruction>(*UI); 210 switch (I->getOpcode()) { 211 case Instruction::Load: 212 break; //next use. 213 case Instruction::Store: 214 if (I->getOperand(0) == V) 215 return true; // Escapes if the pointer is stored. 216 break; // next use. 217 case Instruction::GetElementPtr: 218 if (AddressMightEscape(I)) 219 return true; 220 break; // next use. 221 case Instruction::BitCast: 222 if (AddressMightEscape(I)) 223 return true; 224 break; // next use 225 case Instruction::Ret: 226 // If returned, the address will escape to calling functions, but no 227 // callees could modify it. 228 break; // next use 229 case Instruction::Call: 230 // If the call is to a few known safe intrinsics, we know that it does 231 // not escape 232 if (!isa<MemIntrinsic>(I)) 233 return true; 234 break; // next use 235 default: 236 return true; 237 } 238 } 239 return false; 240} 241 242// getModRefInfo - Check to see if the specified callsite can clobber the 243// specified memory object. Since we only look at local properties of this 244// function, we really can't say much about this query. We do, however, use 245// simple "address taken" analysis on local objects. 246// 247AliasAnalysis::ModRefResult 248BasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) { 249 if (!isa<Constant>(P)) { 250 const Value *Object = getUnderlyingObject(P); 251 252 // If this is a tail call and P points to a stack location, we know that 253 // the tail call cannot access or modify the local stack. 254 // We cannot exclude byval arguments here; these belong to the caller of 255 // the current function not to the current function, and a tail callee 256 // may reference them. 257 if (isa<AllocaInst>(Object)) 258 if (CallInst *CI = dyn_cast<CallInst>(CS.getInstruction())) 259 if (CI->isTailCall()) 260 return NoModRef; 261 262 // Allocations and byval arguments are "new" objects. 263 if (isa<AllocationInst>(Object) || isa<Argument>(Object)) { 264 // Okay, the pointer is to a stack allocated (or effectively so, for 265 // for noalias parameters) object. If the address of this object doesn't 266 // escape from this function body to a callee, then we know that no 267 // callees can mod/ref it unless they are actually passed it. 268 if (isa<AllocationInst>(Object) || 269 cast<Argument>(Object)->hasByValAttr() || 270 cast<Argument>(Object)->hasNoAliasAttr()) 271 if (!AddressMightEscape(Object)) { 272 bool passedAsArg = false; 273 for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 274 CI != CE; ++CI) 275 if (isa<PointerType>((*CI)->getType()) && 276 (getUnderlyingObject(*CI) == P || 277 alias(cast<Value>(CI), ~0U, P, ~0U) != NoAlias)) 278 passedAsArg = true; 279 280 if (!passedAsArg) 281 return NoModRef; 282 } 283 } 284 } 285 286 // The AliasAnalysis base class has some smarts, lets use them. 287 return AliasAnalysis::getModRefInfo(CS, P, Size); 288} 289 290/// isIdentifiedObject - Return true if this pointer refers to a distinct and 291/// identifiable object. This returns true for: 292/// Global Variables and Functions 293/// Allocas and Mallocs 294/// ByVal and NoAlias Arguments 295/// 296static bool isIdentifiedObject(const Value *V) { 297 if (isa<GlobalValue>(V) || isa<AllocationInst>(V)) 298 return true; 299 if (const Argument *A = dyn_cast<Argument>(V)) 300 return A->hasNoAliasAttr() || A->hasByValAttr(); 301 return false; 302} 303 304/// isKnownNonNull - Return true if we know that the specified value is never 305/// null. 306static bool isKnownNonNull(const Value *V) { 307 // Alloca never returns null, malloc might. 308 if (isa<AllocaInst>(V)) return true; 309 310 // A byval argument is never null. 311 if (const Argument *A = dyn_cast<Argument>(V)) 312 return A->hasByValAttr(); 313 314 // Global values are not null unless extern weak. 315 if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) 316 return !GV->hasExternalWeakLinkage(); 317 return false; 318} 319 320/// isNonEscapingLocalObject - Return true if the pointer is to a function-local 321/// object that never escapes from the function. 322static bool isNonEscapingLocalObject(const Value *V) { 323 // If this is a local allocation or byval argument, check to see if it 324 // escapes. 325 if (isa<AllocationInst>(V) || 326 (isa<Argument>(V) && cast<Argument>(V)->hasByValAttr())) 327 return !AddressMightEscape(V); 328 return false; 329} 330 331 332/// isObjectSmallerThan - Return true if we can prove that the object specified 333/// by V is smaller than Size. 334static bool isObjectSmallerThan(const Value *V, unsigned Size, 335 const TargetData &TD) { 336 const Type *AccessTy = 0; 337 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) 338 AccessTy = GV->getType()->getElementType(); 339 340 if (const AllocationInst *AI = dyn_cast<AllocationInst>(V)) 341 if (!AI->isArrayAllocation()) 342 AccessTy = AI->getType()->getElementType(); 343 344 if (const Argument *A = dyn_cast<Argument>(V)) 345 if (A->hasByValAttr()) 346 AccessTy = cast<PointerType>(A->getType())->getElementType(); 347 348 if (AccessTy && AccessTy->isSized()) 349 return TD.getABITypeSize(AccessTy) < Size; 350 return false; 351} 352 353// alias - Provide a bunch of ad-hoc rules to disambiguate in common cases, such 354// as array references. Note that this function is heavily tail recursive. 355// Hopefully we have a smart C++ compiler. :) 356// 357AliasAnalysis::AliasResult 358BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size, 359 const Value *V2, unsigned V2Size) { 360 // Strip off any constant expression casts if they exist 361 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V1)) 362 if (CE->isCast() && isa<PointerType>(CE->getOperand(0)->getType())) 363 V1 = CE->getOperand(0); 364 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V2)) 365 if (CE->isCast() && isa<PointerType>(CE->getOperand(0)->getType())) 366 V2 = CE->getOperand(0); 367 368 // Are we checking for alias of the same value? 369 if (V1 == V2) return MustAlias; 370 371 if ((!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType())) && 372 V1->getType() != Type::Int64Ty && V2->getType() != Type::Int64Ty) 373 return NoAlias; // Scalars cannot alias each other 374 375 // Strip off cast instructions... 376 if (const BitCastInst *I = dyn_cast<BitCastInst>(V1)) 377 return alias(I->getOperand(0), V1Size, V2, V2Size); 378 if (const BitCastInst *I = dyn_cast<BitCastInst>(V2)) 379 return alias(V1, V1Size, I->getOperand(0), V2Size); 380 381 // Figure out what objects these things are pointing to if we can... 382 const Value *O1 = getUnderlyingObject(V1); 383 const Value *O2 = getUnderlyingObject(V2); 384 385 if (O1 != O2) { 386 // If V1/V2 point to two different objects we know that we have no alias. 387 if (isIdentifiedObject(O1) && isIdentifiedObject(O2)) 388 return NoAlias; 389 390 // Incoming argument cannot alias locally allocated object! 391 if ((isa<Argument>(O1) && isa<AllocationInst>(O2)) || 392 (isa<Argument>(O2) && isa<AllocationInst>(O1))) 393 return NoAlias; 394 395 // Most objects can't alias null. 396 if ((isa<ConstantPointerNull>(V2) && isKnownNonNull(O1)) || 397 (isa<ConstantPointerNull>(V1) && isKnownNonNull(O2))) 398 return NoAlias; 399 } 400 401 // If the size of one access is larger than the entire object on the other 402 // side, then we know such behavior is undefined and can assume no alias. 403 const TargetData &TD = getTargetData(); 404 if ((V1Size != ~0U && isObjectSmallerThan(O2, V1Size, TD)) || 405 (V2Size != ~0U && isObjectSmallerThan(O1, V2Size, TD))) 406 return NoAlias; 407 408 // If one pointer is the result of a call/invoke and the other is a 409 // non-escaping local object, then we know the object couldn't escape to a 410 // point where the call could return it. 411 if ((isa<CallInst>(O1) || isa<InvokeInst>(O1)) && 412 isNonEscapingLocalObject(O2)) 413 return NoAlias; 414 if ((isa<CallInst>(O2) || isa<InvokeInst>(O2)) && 415 isNonEscapingLocalObject(O1)) 416 return NoAlias; 417 418 // If we have two gep instructions with must-alias'ing base pointers, figure 419 // out if the indexes to the GEP tell us anything about the derived pointer. 420 // Note that we also handle chains of getelementptr instructions as well as 421 // constant expression getelementptrs here. 422 // 423 if (isGEP(V1) && isGEP(V2)) { 424 // Drill down into the first non-gep value, to test for must-aliasing of 425 // the base pointers. 426 const User *G = cast<User>(V1); 427 while (isGEP(G->getOperand(0)) && 428 G->getOperand(1) == 429 Constant::getNullValue(G->getOperand(1)->getType())) 430 G = cast<User>(G->getOperand(0)); 431 const Value *BasePtr1 = G->getOperand(0); 432 433 G = cast<User>(V2); 434 while (isGEP(G->getOperand(0)) && 435 G->getOperand(1) == 436 Constant::getNullValue(G->getOperand(1)->getType())) 437 G = cast<User>(G->getOperand(0)); 438 const Value *BasePtr2 = G->getOperand(0); 439 440 // Do the base pointers alias? 441 AliasResult BaseAlias = alias(BasePtr1, ~0U, BasePtr2, ~0U); 442 if (BaseAlias == NoAlias) return NoAlias; 443 if (BaseAlias == MustAlias) { 444 // If the base pointers alias each other exactly, check to see if we can 445 // figure out anything about the resultant pointers, to try to prove 446 // non-aliasing. 447 448 // Collect all of the chained GEP operands together into one simple place 449 SmallVector<Value*, 16> GEP1Ops, GEP2Ops; 450 BasePtr1 = GetGEPOperands(V1, GEP1Ops); 451 BasePtr2 = GetGEPOperands(V2, GEP2Ops); 452 453 // If GetGEPOperands were able to fold to the same must-aliased pointer, 454 // do the comparison. 455 if (BasePtr1 == BasePtr2) { 456 AliasResult GAlias = 457 CheckGEPInstructions(BasePtr1->getType(), 458 &GEP1Ops[0], GEP1Ops.size(), V1Size, 459 BasePtr2->getType(), 460 &GEP2Ops[0], GEP2Ops.size(), V2Size); 461 if (GAlias != MayAlias) 462 return GAlias; 463 } 464 } 465 } 466 467 // Check to see if these two pointers are related by a getelementptr 468 // instruction. If one pointer is a GEP with a non-zero index of the other 469 // pointer, we know they cannot alias. 470 // 471 if (isGEP(V2)) { 472 std::swap(V1, V2); 473 std::swap(V1Size, V2Size); 474 } 475 476 if (V1Size != ~0U && V2Size != ~0U) 477 if (isGEP(V1)) { 478 SmallVector<Value*, 16> GEPOperands; 479 const Value *BasePtr = GetGEPOperands(V1, GEPOperands); 480 481 AliasResult R = alias(BasePtr, V1Size, V2, V2Size); 482 if (R == MustAlias) { 483 // If there is at least one non-zero constant index, we know they cannot 484 // alias. 485 bool ConstantFound = false; 486 bool AllZerosFound = true; 487 for (unsigned i = 0, e = GEPOperands.size(); i != e; ++i) 488 if (const Constant *C = dyn_cast<Constant>(GEPOperands[i])) { 489 if (!C->isNullValue()) { 490 ConstantFound = true; 491 AllZerosFound = false; 492 break; 493 } 494 } else { 495 AllZerosFound = false; 496 } 497 498 // If we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 must aliases 499 // the ptr, the end result is a must alias also. 500 if (AllZerosFound) 501 return MustAlias; 502 503 if (ConstantFound) { 504 if (V2Size <= 1 && V1Size <= 1) // Just pointer check? 505 return NoAlias; 506 507 // Otherwise we have to check to see that the distance is more than 508 // the size of the argument... build an index vector that is equal to 509 // the arguments provided, except substitute 0's for any variable 510 // indexes we find... 511 if (cast<PointerType>( 512 BasePtr->getType())->getElementType()->isSized()) { 513 for (unsigned i = 0; i != GEPOperands.size(); ++i) 514 if (!isa<ConstantInt>(GEPOperands[i])) 515 GEPOperands[i] = 516 Constant::getNullValue(GEPOperands[i]->getType()); 517 int64_t Offset = 518 getTargetData().getIndexedOffset(BasePtr->getType(), 519 &GEPOperands[0], 520 GEPOperands.size()); 521 522 if (Offset >= (int64_t)V2Size || Offset <= -(int64_t)V1Size) 523 return NoAlias; 524 } 525 } 526 } 527 } 528 529 return MayAlias; 530} 531 532// This function is used to determin if the indices of two GEP instructions are 533// equal. V1 and V2 are the indices. 534static bool IndexOperandsEqual(Value *V1, Value *V2) { 535 if (V1->getType() == V2->getType()) 536 return V1 == V2; 537 if (Constant *C1 = dyn_cast<Constant>(V1)) 538 if (Constant *C2 = dyn_cast<Constant>(V2)) { 539 // Sign extend the constants to long types, if necessary 540 if (C1->getType() != Type::Int64Ty) 541 C1 = ConstantExpr::getSExt(C1, Type::Int64Ty); 542 if (C2->getType() != Type::Int64Ty) 543 C2 = ConstantExpr::getSExt(C2, Type::Int64Ty); 544 return C1 == C2; 545 } 546 return false; 547} 548 549/// CheckGEPInstructions - Check two GEP instructions with known must-aliasing 550/// base pointers. This checks to see if the index expressions preclude the 551/// pointers from aliasing... 552AliasAnalysis::AliasResult 553BasicAliasAnalysis::CheckGEPInstructions( 554 const Type* BasePtr1Ty, Value **GEP1Ops, unsigned NumGEP1Ops, unsigned G1S, 555 const Type *BasePtr2Ty, Value **GEP2Ops, unsigned NumGEP2Ops, unsigned G2S) { 556 // We currently can't handle the case when the base pointers have different 557 // primitive types. Since this is uncommon anyway, we are happy being 558 // extremely conservative. 559 if (BasePtr1Ty != BasePtr2Ty) 560 return MayAlias; 561 562 const PointerType *GEPPointerTy = cast<PointerType>(BasePtr1Ty); 563 564 // Find the (possibly empty) initial sequence of equal values... which are not 565 // necessarily constants. 566 unsigned NumGEP1Operands = NumGEP1Ops, NumGEP2Operands = NumGEP2Ops; 567 unsigned MinOperands = std::min(NumGEP1Operands, NumGEP2Operands); 568 unsigned MaxOperands = std::max(NumGEP1Operands, NumGEP2Operands); 569 unsigned UnequalOper = 0; 570 while (UnequalOper != MinOperands && 571 IndexOperandsEqual(GEP1Ops[UnequalOper], GEP2Ops[UnequalOper])) { 572 // Advance through the type as we go... 573 ++UnequalOper; 574 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty)) 575 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[UnequalOper-1]); 576 else { 577 // If all operands equal each other, then the derived pointers must 578 // alias each other... 579 BasePtr1Ty = 0; 580 assert(UnequalOper == NumGEP1Operands && UnequalOper == NumGEP2Operands && 581 "Ran out of type nesting, but not out of operands?"); 582 return MustAlias; 583 } 584 } 585 586 // If we have seen all constant operands, and run out of indexes on one of the 587 // getelementptrs, check to see if the tail of the leftover one is all zeros. 588 // If so, return mustalias. 589 if (UnequalOper == MinOperands) { 590 if (NumGEP1Ops < NumGEP2Ops) { 591 std::swap(GEP1Ops, GEP2Ops); 592 std::swap(NumGEP1Ops, NumGEP2Ops); 593 } 594 595 bool AllAreZeros = true; 596 for (unsigned i = UnequalOper; i != MaxOperands; ++i) 597 if (!isa<Constant>(GEP1Ops[i]) || 598 !cast<Constant>(GEP1Ops[i])->isNullValue()) { 599 AllAreZeros = false; 600 break; 601 } 602 if (AllAreZeros) return MustAlias; 603 } 604 605 606 // So now we know that the indexes derived from the base pointers, 607 // which are known to alias, are different. We can still determine a 608 // no-alias result if there are differing constant pairs in the index 609 // chain. For example: 610 // A[i][0] != A[j][1] iff (&A[0][1]-&A[0][0] >= std::max(G1S, G2S)) 611 // 612 // We have to be careful here about array accesses. In particular, consider: 613 // A[1][0] vs A[0][i] 614 // In this case, we don't *know* that the array will be accessed in bounds: 615 // the index could even be negative. Because of this, we have to 616 // conservatively *give up* and return may alias. We disregard differing 617 // array subscripts that are followed by a variable index without going 618 // through a struct. 619 // 620 unsigned SizeMax = std::max(G1S, G2S); 621 if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work. 622 623 // Scan for the first operand that is constant and unequal in the 624 // two getelementptrs... 625 unsigned FirstConstantOper = UnequalOper; 626 for (; FirstConstantOper != MinOperands; ++FirstConstantOper) { 627 const Value *G1Oper = GEP1Ops[FirstConstantOper]; 628 const Value *G2Oper = GEP2Ops[FirstConstantOper]; 629 630 if (G1Oper != G2Oper) // Found non-equal constant indexes... 631 if (Constant *G1OC = dyn_cast<ConstantInt>(const_cast<Value*>(G1Oper))) 632 if (Constant *G2OC = dyn_cast<ConstantInt>(const_cast<Value*>(G2Oper))){ 633 if (G1OC->getType() != G2OC->getType()) { 634 // Sign extend both operands to long. 635 if (G1OC->getType() != Type::Int64Ty) 636 G1OC = ConstantExpr::getSExt(G1OC, Type::Int64Ty); 637 if (G2OC->getType() != Type::Int64Ty) 638 G2OC = ConstantExpr::getSExt(G2OC, Type::Int64Ty); 639 GEP1Ops[FirstConstantOper] = G1OC; 640 GEP2Ops[FirstConstantOper] = G2OC; 641 } 642 643 if (G1OC != G2OC) { 644 // Handle the "be careful" case above: if this is an array/vector 645 // subscript, scan for a subsequent variable array index. 646 if (isa<SequentialType>(BasePtr1Ty)) { 647 const Type *NextTy = 648 cast<SequentialType>(BasePtr1Ty)->getElementType(); 649 bool isBadCase = false; 650 651 for (unsigned Idx = FirstConstantOper+1; 652 Idx != MinOperands && isa<SequentialType>(NextTy); ++Idx) { 653 const Value *V1 = GEP1Ops[Idx], *V2 = GEP2Ops[Idx]; 654 if (!isa<Constant>(V1) || !isa<Constant>(V2)) { 655 isBadCase = true; 656 break; 657 } 658 NextTy = cast<SequentialType>(NextTy)->getElementType(); 659 } 660 661 if (isBadCase) G1OC = 0; 662 } 663 664 // Make sure they are comparable (ie, not constant expressions), and 665 // make sure the GEP with the smaller leading constant is GEP1. 666 if (G1OC) { 667 Constant *Compare = ConstantExpr::getICmp(ICmpInst::ICMP_SGT, 668 G1OC, G2OC); 669 if (ConstantInt *CV = dyn_cast<ConstantInt>(Compare)) { 670 if (CV->getZExtValue()) { // If they are comparable and G2 > G1 671 std::swap(GEP1Ops, GEP2Ops); // Make GEP1 < GEP2 672 std::swap(NumGEP1Ops, NumGEP2Ops); 673 } 674 break; 675 } 676 } 677 } 678 } 679 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(G1Oper); 680 } 681 682 // No shared constant operands, and we ran out of common operands. At this 683 // point, the GEP instructions have run through all of their operands, and we 684 // haven't found evidence that there are any deltas between the GEP's. 685 // However, one GEP may have more operands than the other. If this is the 686 // case, there may still be hope. Check this now. 687 if (FirstConstantOper == MinOperands) { 688 // Make GEP1Ops be the longer one if there is a longer one. 689 if (NumGEP1Ops < NumGEP2Ops) { 690 std::swap(GEP1Ops, GEP2Ops); 691 std::swap(NumGEP1Ops, NumGEP2Ops); 692 } 693 694 // Is there anything to check? 695 if (NumGEP1Ops > MinOperands) { 696 for (unsigned i = FirstConstantOper; i != MaxOperands; ++i) 697 if (isa<ConstantInt>(GEP1Ops[i]) && 698 !cast<ConstantInt>(GEP1Ops[i])->isZero()) { 699 // Yup, there's a constant in the tail. Set all variables to 700 // constants in the GEP instruction to make it suitable for 701 // TargetData::getIndexedOffset. 702 for (i = 0; i != MaxOperands; ++i) 703 if (!isa<ConstantInt>(GEP1Ops[i])) 704 GEP1Ops[i] = Constant::getNullValue(GEP1Ops[i]->getType()); 705 // Okay, now get the offset. This is the relative offset for the full 706 // instruction. 707 const TargetData &TD = getTargetData(); 708 int64_t Offset1 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops, 709 NumGEP1Ops); 710 711 // Now check without any constants at the end. 712 int64_t Offset2 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops, 713 MinOperands); 714 715 // Make sure we compare the absolute difference. 716 if (Offset1 > Offset2) 717 std::swap(Offset1, Offset2); 718 719 // If the tail provided a bit enough offset, return noalias! 720 if ((uint64_t)(Offset2-Offset1) >= SizeMax) 721 return NoAlias; 722 // Otherwise break - we don't look for another constant in the tail. 723 break; 724 } 725 } 726 727 // Couldn't find anything useful. 728 return MayAlias; 729 } 730 731 // If there are non-equal constants arguments, then we can figure 732 // out a minimum known delta between the two index expressions... at 733 // this point we know that the first constant index of GEP1 is less 734 // than the first constant index of GEP2. 735 736 // Advance BasePtr[12]Ty over this first differing constant operand. 737 BasePtr2Ty = cast<CompositeType>(BasePtr1Ty)-> 738 getTypeAtIndex(GEP2Ops[FirstConstantOper]); 739 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)-> 740 getTypeAtIndex(GEP1Ops[FirstConstantOper]); 741 742 // We are going to be using TargetData::getIndexedOffset to determine the 743 // offset that each of the GEP's is reaching. To do this, we have to convert 744 // all variable references to constant references. To do this, we convert the 745 // initial sequence of array subscripts into constant zeros to start with. 746 const Type *ZeroIdxTy = GEPPointerTy; 747 for (unsigned i = 0; i != FirstConstantOper; ++i) { 748 if (!isa<StructType>(ZeroIdxTy)) 749 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Type::Int32Ty); 750 751 if (const CompositeType *CT = dyn_cast<CompositeType>(ZeroIdxTy)) 752 ZeroIdxTy = CT->getTypeAtIndex(GEP1Ops[i]); 753 } 754 755 // We know that GEP1Ops[FirstConstantOper] & GEP2Ops[FirstConstantOper] are ok 756 757 // Loop over the rest of the operands... 758 for (unsigned i = FirstConstantOper+1; i != MaxOperands; ++i) { 759 const Value *Op1 = i < NumGEP1Ops ? GEP1Ops[i] : 0; 760 const Value *Op2 = i < NumGEP2Ops ? GEP2Ops[i] : 0; 761 // If they are equal, use a zero index... 762 if (Op1 == Op2 && BasePtr1Ty == BasePtr2Ty) { 763 if (!isa<ConstantInt>(Op1)) 764 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Op1->getType()); 765 // Otherwise, just keep the constants we have. 766 } else { 767 if (Op1) { 768 if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) { 769 // If this is an array index, make sure the array element is in range. 770 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) { 771 if (Op1C->getZExtValue() >= AT->getNumElements()) 772 return MayAlias; // Be conservative with out-of-range accesses 773 } else if (const VectorType *VT = dyn_cast<VectorType>(BasePtr1Ty)) { 774 if (Op1C->getZExtValue() >= VT->getNumElements()) 775 return MayAlias; // Be conservative with out-of-range accesses 776 } 777 778 } else { 779 // GEP1 is known to produce a value less than GEP2. To be 780 // conservatively correct, we must assume the largest possible 781 // constant is used in this position. This cannot be the initial 782 // index to the GEP instructions (because we know we have at least one 783 // element before this one with the different constant arguments), so 784 // we know that the current index must be into either a struct or 785 // array. Because we know it's not constant, this cannot be a 786 // structure index. Because of this, we can calculate the maximum 787 // value possible. 788 // 789 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) 790 GEP1Ops[i] = ConstantInt::get(Type::Int64Ty,AT->getNumElements()-1); 791 else if (const VectorType *VT = dyn_cast<VectorType>(BasePtr1Ty)) 792 GEP1Ops[i] = ConstantInt::get(Type::Int64Ty,VT->getNumElements()-1); 793 } 794 } 795 796 if (Op2) { 797 if (const ConstantInt *Op2C = dyn_cast<ConstantInt>(Op2)) { 798 // If this is an array index, make sure the array element is in range. 799 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr2Ty)) { 800 if (Op2C->getZExtValue() >= AT->getNumElements()) 801 return MayAlias; // Be conservative with out-of-range accesses 802 } else if (const VectorType *VT = dyn_cast<VectorType>(BasePtr2Ty)) { 803 if (Op2C->getZExtValue() >= VT->getNumElements()) 804 return MayAlias; // Be conservative with out-of-range accesses 805 } 806 } else { // Conservatively assume the minimum value for this index 807 GEP2Ops[i] = Constant::getNullValue(Op2->getType()); 808 } 809 } 810 } 811 812 if (BasePtr1Ty && Op1) { 813 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty)) 814 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[i]); 815 else 816 BasePtr1Ty = 0; 817 } 818 819 if (BasePtr2Ty && Op2) { 820 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr2Ty)) 821 BasePtr2Ty = CT->getTypeAtIndex(GEP2Ops[i]); 822 else 823 BasePtr2Ty = 0; 824 } 825 } 826 827 if (GEPPointerTy->getElementType()->isSized()) { 828 int64_t Offset1 = 829 getTargetData().getIndexedOffset(GEPPointerTy, GEP1Ops, NumGEP1Ops); 830 int64_t Offset2 = 831 getTargetData().getIndexedOffset(GEPPointerTy, GEP2Ops, NumGEP2Ops); 832 assert(Offset1 != Offset2 && 833 "There is at least one different constant here!"); 834 835 // Make sure we compare the absolute difference. 836 if (Offset1 > Offset2) 837 std::swap(Offset1, Offset2); 838 839 if ((uint64_t)(Offset2-Offset1) >= SizeMax) { 840 //cerr << "Determined that these two GEP's don't alias [" 841 // << SizeMax << " bytes]: \n" << *GEP1 << *GEP2; 842 return NoAlias; 843 } 844 } 845 return MayAlias; 846} 847 848// Make sure that anything that uses AliasAnalysis pulls in this file... 849DEFINING_FILE_FOR(BasicAliasAnalysis) 850