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