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