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