BasicAliasAnalysis.cpp revision 04b75935462642641469fb264aab9f1110ce2666
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// FIXME: This could be extended for a very simple form of mod/ref information. 15// If a pointer is locally allocated (either malloc or alloca) and never passed 16// into a call or stored to memory, then we know that calls will not mod/ref the 17// memory. This can be important for tailcallelim, and can support CSE of loads 18// and dead store elimination across calls. This is particularly important for 19// stack allocated arrays. 20// 21//===----------------------------------------------------------------------===// 22 23#include "llvm/Analysis/AliasAnalysis.h" 24#include "llvm/Pass.h" 25#include "llvm/Argument.h" 26#include "llvm/iOther.h" 27#include "llvm/iMemory.h" 28#include "llvm/Constants.h" 29#include "llvm/GlobalVariable.h" 30#include "llvm/DerivedTypes.h" 31#include "llvm/Target/TargetData.h" 32#include "llvm/Support/GetElementPtrTypeIterator.h" 33using namespace llvm; 34 35// Make sure that anything that uses AliasAnalysis pulls in this file... 36void llvm::BasicAAStub() {} 37 38namespace { 39 struct BasicAliasAnalysis : public ImmutablePass, public AliasAnalysis { 40 41 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 42 AliasAnalysis::getAnalysisUsage(AU); 43 } 44 45 virtual void initializePass(); 46 47 AliasResult alias(const Value *V1, unsigned V1Size, 48 const Value *V2, unsigned V2Size); 49 50 ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size); 51 52 /// pointsToConstantMemory - Chase pointers until we find a (constant 53 /// global) or not. 54 bool pointsToConstantMemory(const Value *P); 55 56 private: 57 // CheckGEPInstructions - Check two GEP instructions with known 58 // must-aliasing base pointers. This checks to see if the index expressions 59 // preclude the pointers from aliasing... 60 AliasResult 61 CheckGEPInstructions(const Type* BasePtr1Ty, std::vector<Value*> &GEP1Ops, 62 unsigned G1Size, 63 const Type *BasePtr2Ty, std::vector<Value*> &GEP2Ops, 64 unsigned G2Size); 65 }; 66 67 // Register this pass... 68 RegisterOpt<BasicAliasAnalysis> 69 X("basicaa", "Basic Alias Analysis (default AA impl)"); 70 71 // Declare that we implement the AliasAnalysis interface 72 RegisterAnalysisGroup<AliasAnalysis, BasicAliasAnalysis, true> Y; 73} // End of anonymous namespace 74 75void BasicAliasAnalysis::initializePass() { 76 InitializeAliasAnalysis(this); 77} 78 79// hasUniqueAddress - Return true if the specified value points to something 80// with a unique, discernable, address. 81static inline bool hasUniqueAddress(const Value *V) { 82 return isa<GlobalValue>(V) || isa<AllocationInst>(V); 83} 84 85// getUnderlyingObject - This traverses the use chain to figure out what object 86// the specified value points to. If the value points to, or is derived from, a 87// unique object or an argument, return it. 88static const Value *getUnderlyingObject(const Value *V) { 89 if (!isa<PointerType>(V->getType())) return 0; 90 91 // If we are at some type of object... return it. 92 if (hasUniqueAddress(V) || isa<Argument>(V)) return V; 93 94 // Traverse through different addressing mechanisms... 95 if (const Instruction *I = dyn_cast<Instruction>(V)) { 96 if (isa<CastInst>(I) || isa<GetElementPtrInst>(I)) 97 return getUnderlyingObject(I->getOperand(0)); 98 } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { 99 if (CE->getOpcode() == Instruction::Cast || 100 CE->getOpcode() == Instruction::GetElementPtr) 101 return getUnderlyingObject(CE->getOperand(0)); 102 } else if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V)) { 103 return CPR->getValue(); 104 } 105 return 0; 106} 107 108static const User *isGEP(const Value *V) { 109 if (isa<GetElementPtrInst>(V) || 110 (isa<ConstantExpr>(V) && 111 cast<ConstantExpr>(V)->getOpcode() == Instruction::GetElementPtr)) 112 return cast<User>(V); 113 return 0; 114} 115 116static const Value *GetGEPOperands(const Value *V, std::vector<Value*> &GEPOps){ 117 assert(GEPOps.empty() && "Expect empty list to populate!"); 118 GEPOps.insert(GEPOps.end(), cast<User>(V)->op_begin()+1, 119 cast<User>(V)->op_end()); 120 121 // Accumulate all of the chained indexes into the operand array 122 V = cast<User>(V)->getOperand(0); 123 124 while (const User *G = isGEP(V)) { 125 if (!isa<Constant>(GEPOps[0]) || 126 !cast<Constant>(GEPOps[0])->isNullValue()) 127 break; // Don't handle folding arbitrary pointer offsets yet... 128 GEPOps.erase(GEPOps.begin()); // Drop the zero index 129 GEPOps.insert(GEPOps.begin(), G->op_begin()+1, G->op_end()); 130 V = G->getOperand(0); 131 } 132 return V; 133} 134 135/// pointsToConstantMemory - Chase pointers until we find a (constant 136/// global) or not. 137bool BasicAliasAnalysis::pointsToConstantMemory(const Value *P) { 138 if (const Value *V = getUnderlyingObject(P)) 139 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) 140 return GV->isConstant(); 141 return false; 142} 143 144static bool AddressMightEscape(const Value *V) { 145 for (Value::use_const_iterator UI = V->use_begin(), E = V->use_end(); 146 UI != E; ++UI) { 147 const Instruction *I = cast<Instruction>(*UI); 148 switch (I->getOpcode()) { 149 case Instruction::Load: break; 150 case Instruction::Store: 151 if (I->getOperand(0) == V) 152 return true; // Escapes if the pointer is stored. 153 break; 154 case Instruction::GetElementPtr: 155 if (AddressMightEscape(I)) return true; 156 break; 157 case Instruction::Cast: 158 if (!isa<PointerType>(I->getType())) 159 return true; 160 if (AddressMightEscape(I)) return true; 161 break; 162 case Instruction::PHI: 163 if (AddressMightEscape(I)) return true; 164 break; 165 default: 166 return true; 167 } 168 } 169 return false; 170} 171 172// getModRefInfo - Check to see if the specified callsite can clobber the 173// specified memory object. Since we only look at local properties of this 174// function, we really can't say much about this query. We do, however, use 175// simple "address taken" analysis on local objects. 176// 177AliasAnalysis::ModRefResult 178BasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) { 179 if (!isa<Constant>(P) && !isa<GlobalValue>(P)) 180 if (const AllocationInst *AI = 181 dyn_cast<AllocationInst>(getUnderlyingObject(P))) { 182 // Okay, the pointer is to a stack allocated object. If we can prove that 183 // the pointer never "escapes", then we know the call cannot clobber it, 184 // because it simply can't get its address. 185 if (!AddressMightEscape(AI)) 186 return NoModRef; 187 } 188 189 // If P points to a constant memory location, the call definitely could not 190 // modify the memory location. 191 return pointsToConstantMemory(P) ? Ref : ModRef; 192} 193 194// alias - Provide a bunch of ad-hoc rules to disambiguate in common cases, such 195// as array references. Note that this function is heavily tail recursive. 196// Hopefully we have a smart C++ compiler. :) 197// 198AliasAnalysis::AliasResult 199BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size, 200 const Value *V2, unsigned V2Size) { 201 // Strip off any constant expression casts if they exist 202 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V1)) 203 if (CE->getOpcode() == Instruction::Cast) 204 V1 = CE->getOperand(0); 205 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V2)) 206 if (CE->getOpcode() == Instruction::Cast) 207 V2 = CE->getOperand(0); 208 209 // Strip off constant pointer refs if they exist 210 if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V1)) 211 V1 = CPR->getValue(); 212 if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V2)) 213 V2 = CPR->getValue(); 214 215 // Are we checking for alias of the same value? 216 if (V1 == V2) return MustAlias; 217 218 if ((!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType())) && 219 V1->getType() != Type::LongTy && V2->getType() != Type::LongTy) 220 return NoAlias; // Scalars cannot alias each other 221 222 // Strip off cast instructions... 223 if (const Instruction *I = dyn_cast<CastInst>(V1)) 224 return alias(I->getOperand(0), V1Size, V2, V2Size); 225 if (const Instruction *I = dyn_cast<CastInst>(V2)) 226 return alias(V1, V1Size, I->getOperand(0), V2Size); 227 228 // Figure out what objects these things are pointing to if we can... 229 const Value *O1 = getUnderlyingObject(V1); 230 const Value *O2 = getUnderlyingObject(V2); 231 232 // Pointing at a discernible object? 233 if (O1 && O2) { 234 if (isa<Argument>(O1)) { 235 // Incoming argument cannot alias locally allocated object! 236 if (isa<AllocationInst>(O2)) return NoAlias; 237 // Otherwise, nothing is known... 238 } else if (isa<Argument>(O2)) { 239 // Incoming argument cannot alias locally allocated object! 240 if (isa<AllocationInst>(O1)) return NoAlias; 241 // Otherwise, nothing is known... 242 } else { 243 // If they are two different objects, we know that we have no alias... 244 if (O1 != O2) return NoAlias; 245 } 246 247 // If they are the same object, they we can look at the indexes. If they 248 // index off of the object is the same for both pointers, they must alias. 249 // If they are provably different, they must not alias. Otherwise, we can't 250 // tell anything. 251 } else if (O1 && !isa<Argument>(O1) && isa<ConstantPointerNull>(V2)) { 252 return NoAlias; // Unique values don't alias null 253 } else if (O2 && !isa<Argument>(O2) && isa<ConstantPointerNull>(V1)) { 254 return NoAlias; // Unique values don't alias null 255 } 256 257 // If we have two gep instructions with must-alias'ing base pointers, figure 258 // out if the indexes to the GEP tell us anything about the derived pointer. 259 // Note that we also handle chains of getelementptr instructions as well as 260 // constant expression getelementptrs here. 261 // 262 if (isGEP(V1) && isGEP(V2)) { 263 // Drill down into the first non-gep value, to test for must-aliasing of 264 // the base pointers. 265 const Value *BasePtr1 = V1, *BasePtr2 = V2; 266 do { 267 BasePtr1 = cast<User>(BasePtr1)->getOperand(0); 268 } while (isGEP(BasePtr1) && 269 cast<User>(BasePtr1)->getOperand(1) == 270 Constant::getNullValue(cast<User>(BasePtr1)->getOperand(1)->getType())); 271 do { 272 BasePtr2 = cast<User>(BasePtr2)->getOperand(0); 273 } while (isGEP(BasePtr2) && 274 cast<User>(BasePtr2)->getOperand(1) == 275 Constant::getNullValue(cast<User>(BasePtr2)->getOperand(1)->getType())); 276 277 // Do the base pointers alias? 278 AliasResult BaseAlias = alias(BasePtr1, V1Size, BasePtr2, V2Size); 279 if (BaseAlias == NoAlias) return NoAlias; 280 if (BaseAlias == MustAlias) { 281 // If the base pointers alias each other exactly, check to see if we can 282 // figure out anything about the resultant pointers, to try to prove 283 // non-aliasing. 284 285 // Collect all of the chained GEP operands together into one simple place 286 std::vector<Value*> GEP1Ops, GEP2Ops; 287 BasePtr1 = GetGEPOperands(V1, GEP1Ops); 288 BasePtr2 = GetGEPOperands(V2, GEP2Ops); 289 290 AliasResult GAlias = 291 CheckGEPInstructions(BasePtr1->getType(), GEP1Ops, V1Size, 292 BasePtr2->getType(), GEP2Ops, V2Size); 293 if (GAlias != MayAlias) 294 return GAlias; 295 } 296 } 297 298 // Check to see if these two pointers are related by a getelementptr 299 // instruction. If one pointer is a GEP with a non-zero index of the other 300 // pointer, we know they cannot alias. 301 // 302 if (isGEP(V2)) { 303 std::swap(V1, V2); 304 std::swap(V1Size, V2Size); 305 } 306 307 if (V1Size != ~0U && V2Size != ~0U) 308 if (const User *GEP = isGEP(V1)) { 309 std::vector<Value*> GEPOperands; 310 const Value *BasePtr = GetGEPOperands(V1, GEPOperands); 311 312 AliasResult R = alias(BasePtr, V1Size, V2, V2Size); 313 if (R == MustAlias) { 314 // If there is at least one non-zero constant index, we know they cannot 315 // alias. 316 bool ConstantFound = false; 317 bool AllZerosFound = true; 318 for (unsigned i = 0, e = GEPOperands.size(); i != e; ++i) 319 if (const Constant *C = dyn_cast<Constant>(GEPOperands[i])) { 320 if (!C->isNullValue()) { 321 ConstantFound = true; 322 AllZerosFound = false; 323 break; 324 } 325 } else { 326 AllZerosFound = false; 327 } 328 329 // If we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 must aliases 330 // the ptr, the end result is a must alias also. 331 if (AllZerosFound) 332 return MustAlias; 333 334 if (ConstantFound) { 335 if (V2Size <= 1 && V1Size <= 1) // Just pointer check? 336 return NoAlias; 337 338 // Otherwise we have to check to see that the distance is more than 339 // the size of the argument... build an index vector that is equal to 340 // the arguments provided, except substitute 0's for any variable 341 // indexes we find... 342 for (unsigned i = 0; i != GEPOperands.size(); ++i) 343 if (!isa<Constant>(GEPOperands[i]) || 344 isa<ConstantExpr>(GEPOperands[i])) 345 GEPOperands[i] =Constant::getNullValue(GEPOperands[i]->getType()); 346 int64_t Offset = getTargetData().getIndexedOffset(BasePtr->getType(), 347 GEPOperands); 348 if (Offset >= (int64_t)V2Size || Offset <= -(int64_t)V1Size) 349 return NoAlias; 350 } 351 } 352 } 353 354 return MayAlias; 355} 356 357/// CheckGEPInstructions - Check two GEP instructions with known must-aliasing 358/// base pointers. This checks to see if the index expressions preclude the 359/// pointers from aliasing... 360AliasAnalysis::AliasResult BasicAliasAnalysis:: 361CheckGEPInstructions(const Type* BasePtr1Ty, std::vector<Value*> &GEP1Ops, 362 unsigned G1S, 363 const Type *BasePtr2Ty, std::vector<Value*> &GEP2Ops, 364 unsigned G2S) { 365 // We currently can't handle the case when the base pointers have different 366 // primitive types. Since this is uncommon anyway, we are happy being 367 // extremely conservative. 368 if (BasePtr1Ty != BasePtr2Ty) 369 return MayAlias; 370 371 const Type *GEPPointerTy = BasePtr1Ty; 372 373 // Find the (possibly empty) initial sequence of equal values... which are not 374 // necessarily constants. 375 unsigned NumGEP1Operands = GEP1Ops.size(), NumGEP2Operands = GEP2Ops.size(); 376 unsigned MinOperands = std::min(NumGEP1Operands, NumGEP2Operands); 377 unsigned MaxOperands = std::max(NumGEP1Operands, NumGEP2Operands); 378 unsigned UnequalOper = 0; 379 while (UnequalOper != MinOperands && 380 GEP1Ops[UnequalOper] == GEP2Ops[UnequalOper]) { 381 // Advance through the type as we go... 382 ++UnequalOper; 383 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty)) 384 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[UnequalOper-1]); 385 else { 386 // If all operands equal each other, then the derived pointers must 387 // alias each other... 388 BasePtr1Ty = 0; 389 assert(UnequalOper == NumGEP1Operands && UnequalOper == NumGEP2Operands && 390 "Ran out of type nesting, but not out of operands?"); 391 return MustAlias; 392 } 393 } 394 395 // If we have seen all constant operands, and run out of indexes on one of the 396 // getelementptrs, check to see if the tail of the leftover one is all zeros. 397 // If so, return mustalias. 398 if (UnequalOper == MinOperands) { 399 if (GEP1Ops.size() < GEP2Ops.size()) std::swap(GEP1Ops, GEP2Ops); 400 401 bool AllAreZeros = true; 402 for (unsigned i = UnequalOper; i != MaxOperands; ++i) 403 if (!isa<Constant>(GEP1Ops[i]) || 404 !cast<Constant>(GEP1Ops[i])->isNullValue()) { 405 AllAreZeros = false; 406 break; 407 } 408 if (AllAreZeros) return MustAlias; 409 } 410 411 412 // So now we know that the indexes derived from the base pointers, 413 // which are known to alias, are different. We can still determine a 414 // no-alias result if there are differing constant pairs in the index 415 // chain. For example: 416 // A[i][0] != A[j][1] iff (&A[0][1]-&A[0][0] >= std::max(G1S, G2S)) 417 // 418 unsigned SizeMax = std::max(G1S, G2S); 419 if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work... 420 421 // Scan for the first operand that is constant and unequal in the 422 // two getelemenptrs... 423 unsigned FirstConstantOper = UnequalOper; 424 for (; FirstConstantOper != MinOperands; ++FirstConstantOper) { 425 const Value *G1Oper = GEP1Ops[FirstConstantOper]; 426 const Value *G2Oper = GEP2Ops[FirstConstantOper]; 427 428 if (G1Oper != G2Oper) // Found non-equal constant indexes... 429 if (Constant *G1OC = dyn_cast<Constant>(const_cast<Value*>(G1Oper))) 430 if (Constant *G2OC = dyn_cast<Constant>(const_cast<Value*>(G2Oper))) { 431 // Make sure they are comparable (ie, not constant expressions)... 432 // and make sure the GEP with the smaller leading constant is GEP1. 433 Constant *Compare = ConstantExpr::get(Instruction::SetGT, G1OC, G2OC); 434 if (ConstantBool *CV = dyn_cast<ConstantBool>(Compare)) { 435 if (CV->getValue()) // If they are comparable and G2 > G1 436 std::swap(GEP1Ops, GEP2Ops); // Make GEP1 < GEP2 437 break; 438 } 439 } 440 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(G1Oper); 441 } 442 443 // No shared constant operands, and we ran out of common operands. At this 444 // point, the GEP instructions have run through all of their operands, and we 445 // haven't found evidence that there are any deltas between the GEP's. 446 // However, one GEP may have more operands than the other. If this is the 447 // case, there may still be hope. This this now. 448 if (FirstConstantOper == MinOperands) { 449 // Make GEP1Ops be the longer one if there is a longer one. 450 if (GEP1Ops.size() < GEP2Ops.size()) 451 std::swap(GEP1Ops, GEP2Ops); 452 453 // Is there anything to check? 454 if (GEP1Ops.size() > MinOperands) { 455 for (unsigned i = FirstConstantOper; i != MaxOperands; ++i) 456 if (isa<Constant>(GEP1Ops[i]) && !isa<ConstantExpr>(GEP1Ops[i]) && 457 !cast<Constant>(GEP1Ops[i])->isNullValue()) { 458 // Yup, there's a constant in the tail. Set all variables to 459 // constants in the GEP instruction to make it suiteable for 460 // TargetData::getIndexedOffset. 461 for (i = 0; i != MaxOperands; ++i) 462 if (!isa<Constant>(GEP1Ops[i]) || isa<ConstantExpr>(GEP1Ops[i])) 463 GEP1Ops[i] = Constant::getNullValue(GEP1Ops[i]->getType()); 464 // Okay, now get the offset. This is the relative offset for the full 465 // instruction. 466 const TargetData &TD = getTargetData(); 467 int64_t Offset1 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops); 468 469 // Now crop off any constants from the end... 470 GEP1Ops.resize(MinOperands); 471 int64_t Offset2 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops); 472 473 // If the tail provided a bit enough offset, return noalias! 474 if ((uint64_t)(Offset2-Offset1) >= SizeMax) 475 return NoAlias; 476 } 477 } 478 479 // Couldn't find anything useful. 480 return MayAlias; 481 } 482 483 // If there are non-equal constants arguments, then we can figure 484 // out a minimum known delta between the two index expressions... at 485 // this point we know that the first constant index of GEP1 is less 486 // than the first constant index of GEP2. 487 488 // Advance BasePtr[12]Ty over this first differing constant operand. 489 BasePtr2Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(GEP2Ops[FirstConstantOper]); 490 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(GEP1Ops[FirstConstantOper]); 491 492 // We are going to be using TargetData::getIndexedOffset to determine the 493 // offset that each of the GEP's is reaching. To do this, we have to convert 494 // all variable references to constant references. To do this, we convert the 495 // initial equal sequence of variables into constant zeros to start with. 496 for (unsigned i = 0; i != FirstConstantOper; ++i) { 497 if (!isa<Constant>(GEP1Ops[i]) || isa<ConstantExpr>(GEP1Ops[i]) || 498 !isa<Constant>(GEP2Ops[i]) || isa<ConstantExpr>(GEP2Ops[i])) { 499 GEP1Ops[i] = Constant::getNullValue(GEP1Ops[i]->getType()); 500 GEP2Ops[i] = Constant::getNullValue(GEP2Ops[i]->getType()); 501 } 502 } 503 504 // We know that GEP1Ops[FirstConstantOper] & GEP2Ops[FirstConstantOper] are ok 505 506 // Loop over the rest of the operands... 507 for (unsigned i = FirstConstantOper+1; i != MaxOperands; ++i) { 508 const Value *Op1 = i < GEP1Ops.size() ? GEP1Ops[i] : 0; 509 const Value *Op2 = i < GEP2Ops.size() ? GEP2Ops[i] : 0; 510 // If they are equal, use a zero index... 511 if (Op1 == Op2 && BasePtr1Ty == BasePtr2Ty) { 512 if (!isa<Constant>(Op1) || isa<ConstantExpr>(Op1)) 513 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Op1->getType()); 514 // Otherwise, just keep the constants we have. 515 } else { 516 if (Op1) { 517 if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) { 518 // If this is an array index, make sure the array element is in range. 519 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) 520 if (Op1C->getRawValue() >= AT->getNumElements()) 521 return MayAlias; // Be conservative with out-of-range accesses 522 523 } else { 524 // GEP1 is known to produce a value less than GEP2. To be 525 // conservatively correct, we must assume the largest possible 526 // constant is used in this position. This cannot be the initial 527 // index to the GEP instructions (because we know we have at least one 528 // element before this one with the different constant arguments), so 529 // we know that the current index must be into either a struct or 530 // array. Because we know it's not constant, this cannot be a 531 // structure index. Because of this, we can calculate the maximum 532 // value possible. 533 // 534 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) 535 GEP1Ops[i] = ConstantSInt::get(Type::LongTy,AT->getNumElements()-1); 536 } 537 } 538 539 if (Op2) { 540 if (const ConstantInt *Op2C = dyn_cast<ConstantInt>(Op2)) { 541 // If this is an array index, make sure the array element is in range. 542 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) 543 if (Op2C->getRawValue() >= AT->getNumElements()) 544 return MayAlias; // Be conservative with out-of-range accesses 545 } else { // Conservatively assume the minimum value for this index 546 GEP2Ops[i] = Constant::getNullValue(Op2->getType()); 547 } 548 } 549 } 550 551 if (BasePtr1Ty && Op1) { 552 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty)) 553 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[i]); 554 else 555 BasePtr1Ty = 0; 556 } 557 558 if (BasePtr2Ty && Op2) { 559 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr2Ty)) 560 BasePtr2Ty = CT->getTypeAtIndex(GEP2Ops[i]); 561 else 562 BasePtr2Ty = 0; 563 } 564 } 565 566 int64_t Offset1 = getTargetData().getIndexedOffset(GEPPointerTy, GEP1Ops); 567 int64_t Offset2 = getTargetData().getIndexedOffset(GEPPointerTy, GEP2Ops); 568 assert(Offset1 < Offset2 &&"There is at least one different constant here!"); 569 570 if ((uint64_t)(Offset2-Offset1) >= SizeMax) { 571 //std::cerr << "Determined that these two GEP's don't alias [" 572 // << SizeMax << " bytes]: \n" << *GEP1 << *GEP2; 573 return NoAlias; 574 } 575 return MayAlias; 576} 577 578