BasicAliasAnalysis.cpp revision c1820036bdedea566c89d2bd47bbbbe4384bdc73
1//===- llvm/Analysis/BasicAliasAnalysis.h - Alias Analysis Impl -*- C++ -*-===// 2// 3// This file defines the default implementation of the Alias Analysis interface 4// that simply implements a few identities (two different globals cannot alias, 5// etc), but otherwise does no analysis. 6// 7//===----------------------------------------------------------------------===// 8 9#include "llvm/Analysis/AliasAnalysis.h" 10#include "llvm/Pass.h" 11#include "llvm/Argument.h" 12#include "llvm/iMemory.h" 13#include "llvm/iOther.h" 14#include "llvm/ConstantHandling.h" 15#include "llvm/GlobalValue.h" 16#include "llvm/DerivedTypes.h" 17#include "llvm/Target/TargetData.h" 18 19// Make sure that anything that uses AliasAnalysis pulls in this file... 20void BasicAAStub() {} 21 22 23namespace { 24 struct BasicAliasAnalysis : public ImmutablePass, public AliasAnalysis { 25 26 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 27 AliasAnalysis::getAnalysisUsage(AU); 28 } 29 30 virtual void initializePass(); 31 32 // alias - This is the only method here that does anything interesting... 33 // 34 AliasResult alias(const Value *V1, unsigned V1Size, 35 const Value *V2, unsigned V2Size); 36 private: 37 // CheckGEPInstructions - Check two GEP instructions of compatible types and 38 // equal number of arguments. This checks to see if the index expressions 39 // preclude the pointers from aliasing... 40 AliasResult CheckGEPInstructions(GetElementPtrInst *GEP1, unsigned G1Size, 41 GetElementPtrInst *GEP2, unsigned G2Size); 42 }; 43 44 // Register this pass... 45 RegisterOpt<BasicAliasAnalysis> 46 X("basicaa", "Basic Alias Analysis (default AA impl)"); 47 48 // Declare that we implement the AliasAnalysis interface 49 RegisterAnalysisGroup<AliasAnalysis, BasicAliasAnalysis, true> Y; 50} // End of anonymous namespace 51 52void BasicAliasAnalysis::initializePass() { 53 InitializeAliasAnalysis(this); 54} 55 56 57 58// hasUniqueAddress - Return true if the specified value points to something 59// with a unique, discernable, address. 60static inline bool hasUniqueAddress(const Value *V) { 61 return isa<GlobalValue>(V) || isa<AllocationInst>(V); 62} 63 64// getUnderlyingObject - This traverses the use chain to figure out what object 65// the specified value points to. If the value points to, or is derived from, a 66// unique object or an argument, return it. 67static const Value *getUnderlyingObject(const Value *V) { 68 if (!isa<PointerType>(V->getType())) return 0; 69 70 // If we are at some type of object... return it. 71 if (hasUniqueAddress(V) || isa<Argument>(V)) return V; 72 73 // Traverse through different addressing mechanisms... 74 if (const Instruction *I = dyn_cast<Instruction>(V)) { 75 if (isa<CastInst>(I) || isa<GetElementPtrInst>(I)) 76 return getUnderlyingObject(I->getOperand(0)); 77 } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { 78 if (CE->getOpcode() == Instruction::Cast || 79 CE->getOpcode() == Instruction::GetElementPtr) 80 return getUnderlyingObject(CE->getOperand(0)); 81 } else if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V)) { 82 return CPR->getValue(); 83 } 84 return 0; 85} 86 87 88// alias - Provide a bunch of ad-hoc rules to disambiguate in common cases, such 89// as array references. Note that this function is heavily tail recursive. 90// Hopefully we have a smart C++ compiler. :) 91// 92AliasAnalysis::AliasResult 93BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size, 94 const Value *V2, unsigned V2Size) { 95 // Strip off constant pointer refs if they exist 96 if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V1)) 97 V1 = CPR->getValue(); 98 if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V2)) 99 V2 = CPR->getValue(); 100 101 // Are we checking for alias of the same value? 102 if (V1 == V2) return MustAlias; 103 104 if ((!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType())) && 105 V1->getType() != Type::LongTy && V2->getType() != Type::LongTy) 106 return NoAlias; // Scalars cannot alias each other 107 108 // Strip off cast instructions... 109 if (const Instruction *I = dyn_cast<CastInst>(V1)) 110 return alias(I->getOperand(0), V1Size, V2, V2Size); 111 if (const Instruction *I = dyn_cast<CastInst>(V2)) 112 return alias(V1, V1Size, I->getOperand(0), V2Size); 113 114 // Figure out what objects these things are pointing to if we can... 115 const Value *O1 = getUnderlyingObject(V1); 116 const Value *O2 = getUnderlyingObject(V2); 117 118 // Pointing at a discernible object? 119 if (O1 && O2) { 120 if (isa<Argument>(O1)) { 121 // Incoming argument cannot alias locally allocated object! 122 if (isa<AllocationInst>(O2)) return NoAlias; 123 // Otherwise, nothing is known... 124 } else if (isa<Argument>(O2)) { 125 // Incoming argument cannot alias locally allocated object! 126 if (isa<AllocationInst>(O1)) return NoAlias; 127 // Otherwise, nothing is known... 128 } else { 129 // If they are two different objects, we know that we have no alias... 130 if (O1 != O2) return NoAlias; 131 } 132 133 // If they are the same object, they we can look at the indexes. If they 134 // index off of the object is the same for both pointers, they must alias. 135 // If they are provably different, they must not alias. Otherwise, we can't 136 // tell anything. 137 } else if (O1 && !isa<Argument>(O1) && isa<ConstantPointerNull>(V2)) { 138 return NoAlias; // Unique values don't alias null 139 } else if (O2 && !isa<Argument>(O2) && isa<ConstantPointerNull>(V1)) { 140 return NoAlias; // Unique values don't alias null 141 } 142 143 // If we have two gep instructions with identical indices, return an alias 144 // result equal to the alias result of the original pointer... 145 // 146 if (const GetElementPtrInst *GEP1 = dyn_cast<GetElementPtrInst>(V1)) 147 if (const GetElementPtrInst *GEP2 = dyn_cast<GetElementPtrInst>(V2)) 148 if (GEP1->getNumOperands() == GEP2->getNumOperands() && 149 GEP1->getOperand(0)->getType() == GEP2->getOperand(0)->getType()) { 150 AliasResult GAlias = 151 CheckGEPInstructions((GetElementPtrInst*)GEP1, V1Size, 152 (GetElementPtrInst*)GEP2, V2Size); 153 if (GAlias != MayAlias) 154 return GAlias; 155 } 156 157 // Check to see if these two pointers are related by a getelementptr 158 // instruction. If one pointer is a GEP with a non-zero index of the other 159 // pointer, we know they cannot alias. 160 // 161 if (isa<GetElementPtrInst>(V2)) { 162 std::swap(V1, V2); 163 std::swap(V1Size, V2Size); 164 } 165 166 if (V1Size != ~0U && V2Size != ~0U) 167 if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(V1)) { 168 AliasResult R = alias(GEP->getOperand(0), V1Size, V2, V2Size); 169 if (R == MustAlias) { 170 // If there is at least one non-zero constant index, we know they cannot 171 // alias. 172 bool ConstantFound = false; 173 for (unsigned i = 1, e = GEP->getNumOperands(); i != e; ++i) 174 if (const Constant *C = dyn_cast<Constant>(GEP->getOperand(i))) 175 if (!C->isNullValue()) { 176 ConstantFound = true; 177 break; 178 } 179 if (ConstantFound) { 180 if (V2Size <= 1 && V1Size <= 1) // Just pointer check? 181 return NoAlias; 182 183 // Otherwise we have to check to see that the distance is more than 184 // the size of the argument... build an index vector that is equal to 185 // the arguments provided, except substitute 0's for any variable 186 // indexes we find... 187 188 std::vector<Value*> Indices; 189 Indices.reserve(GEP->getNumOperands()-1); 190 for (unsigned i = 1; i != GEP->getNumOperands(); ++i) 191 if (const Constant *C = dyn_cast<Constant>(GEP->getOperand(i))) 192 Indices.push_back((Value*)C); 193 else 194 Indices.push_back(Constant::getNullValue(Type::LongTy)); 195 const Type *Ty = GEP->getOperand(0)->getType(); 196 int Offset = getTargetData().getIndexedOffset(Ty, Indices); 197 if (Offset >= (int)V2Size || Offset <= -(int)V1Size) 198 return NoAlias; 199 } 200 } 201 } 202 203 return MayAlias; 204} 205 206static Value *CheckArrayIndicesForOverflow(const Type *PtrTy, 207 const std::vector<Value*> &Indices, 208 const ConstantInt *Idx) { 209 if (const ConstantSInt *IdxS = dyn_cast<ConstantSInt>(Idx)) { 210 if (IdxS->getValue() < 0) // Underflow on the array subscript? 211 return Constant::getNullValue(Type::LongTy); 212 else { // Check for overflow 213 const ArrayType *ATy = 214 cast<ArrayType>(GetElementPtrInst::getIndexedType(PtrTy, Indices,true)); 215 if (IdxS->getValue() >= (int64_t)ATy->getNumElements()) 216 return ConstantSInt::get(Type::LongTy, ATy->getNumElements()-1); 217 } 218 } 219 return (Value*)Idx; // Everything is acceptable. 220} 221 222// CheckGEPInstructions - Check two GEP instructions of compatible types and 223// equal number of arguments. This checks to see if the index expressions 224// preclude the pointers from aliasing... 225// 226AliasAnalysis::AliasResult 227BasicAliasAnalysis::CheckGEPInstructions(GetElementPtrInst *GEP1, unsigned G1S, 228 GetElementPtrInst *GEP2, unsigned G2S){ 229 // Do the base pointers alias? 230 AliasResult BaseAlias = alias(GEP1->getOperand(0), G1S, 231 GEP2->getOperand(0), G2S); 232 if (BaseAlias != MustAlias) // No or May alias: We cannot add anything... 233 return BaseAlias; 234 235 // Find the (possibly empty) initial sequence of equal values... 236 unsigned NumGEPOperands = GEP1->getNumOperands(); 237 unsigned UnequalOper = 1; 238 while (UnequalOper != NumGEPOperands && 239 GEP1->getOperand(UnequalOper) == GEP2->getOperand(UnequalOper)) 240 ++UnequalOper; 241 242 // If all operands equal each other, then the derived pointers must 243 // alias each other... 244 if (UnequalOper == NumGEPOperands) return MustAlias; 245 246 // So now we know that the indexes derived from the base pointers, 247 // which are known to alias, are different. We can still determine a 248 // no-alias result if there are differing constant pairs in the index 249 // chain. For example: 250 // A[i][0] != A[j][1] iff (&A[0][1]-&A[0][0] >= std::max(G1S, G2S)) 251 // 252 unsigned SizeMax = std::max(G1S, G2S); 253 if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work... 254 255 // Scan for the first operand that is constant and unequal in the 256 // two getelemenptrs... 257 unsigned FirstConstantOper = UnequalOper; 258 for (; FirstConstantOper != NumGEPOperands; ++FirstConstantOper) { 259 const Value *G1Oper = GEP1->getOperand(FirstConstantOper); 260 const Value *G2Oper = GEP2->getOperand(FirstConstantOper); 261 if (G1Oper != G2Oper && // Found non-equal constant indexes... 262 isa<Constant>(G1Oper) && isa<Constant>(G2Oper)) { 263 // Make sure they are comparable... and make sure the GEP with 264 // the smaller leading constant is GEP1. 265 ConstantBool *Compare = 266 *cast<Constant>(GEP1->getOperand(FirstConstantOper)) > 267 *cast<Constant>(GEP2->getOperand(FirstConstantOper)); 268 if (Compare) { // If they are comparable... 269 if (Compare->getValue()) 270 std::swap(GEP1, GEP2); // Make GEP1 < GEP2 271 break; 272 } 273 } 274 } 275 276 // No constant operands, we cannot tell anything... 277 if (FirstConstantOper == NumGEPOperands) return MayAlias; 278 279 // If there are non-equal constants arguments, then we can figure 280 // out a minimum known delta between the two index expressions... at 281 // this point we know that the first constant index of GEP1 is less 282 // than the first constant index of GEP2. 283 // 284 std::vector<Value*> Indices1; 285 Indices1.reserve(NumGEPOperands-1); 286 for (unsigned i = 1; i != FirstConstantOper; ++i) 287 if (GEP1->getOperand(i)->getType() == Type::UByteTy) 288 Indices1.push_back(GEP1->getOperand(i)); 289 else 290 Indices1.push_back(Constant::getNullValue(Type::LongTy)); 291 std::vector<Value*> Indices2; 292 Indices2.reserve(NumGEPOperands-1); 293 Indices2 = Indices1; // Copy the zeros prefix... 294 295 // Add the two known constant operands... 296 Indices1.push_back((Value*)GEP1->getOperand(FirstConstantOper)); 297 Indices2.push_back((Value*)GEP2->getOperand(FirstConstantOper)); 298 299 const Type *GEPPointerTy = GEP1->getOperand(0)->getType(); 300 301 // Loop over the rest of the operands... 302 for (unsigned i = FirstConstantOper+1; i != NumGEPOperands; ++i) { 303 const Value *Op1 = GEP1->getOperand(i); 304 const Value *Op2 = GEP2->getOperand(i); 305 if (Op1 == Op2) { // If they are equal, use a zero index... 306 if (!isa<Constant>(Op1)) { 307 Indices1.push_back(Constant::getNullValue(Op1->getType())); 308 Indices2.push_back(Indices1.back()); 309 } else { 310 Indices1.push_back((Value*)Op1); 311 Indices2.push_back((Value*)Op2); 312 } 313 } else { 314 if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) { 315 // If this is an array index, make sure the array element is in range... 316 if (i != 1) // The pointer index can be "out of range" 317 Op1 = CheckArrayIndicesForOverflow(GEPPointerTy, Indices1, Op1C); 318 319 Indices1.push_back((Value*)Op1); 320 } else { 321 // GEP1 is known to produce a value less than GEP2. To be 322 // conservatively correct, we must assume the largest possible constant 323 // is used in this position. This cannot be the initial index to the 324 // GEP instructions (because we know we have at least one element before 325 // this one with the different constant arguments), so we know that the 326 // current index must be into either a struct or array. Because we know 327 // it's not constant, this cannot be a structure index. Because of 328 // this, we can calculate the maximum value possible. 329 // 330 const ArrayType *ElTy = 331 cast<ArrayType>(GEP1->getIndexedType(GEPPointerTy, Indices1, true)); 332 Indices1.push_back(ConstantSInt::get(Type::LongTy, 333 ElTy->getNumElements()-1)); 334 } 335 336 if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op2)) { 337 // If this is an array index, make sure the array element is in range... 338 if (i != 1) // The pointer index can be "out of range" 339 Op1 = CheckArrayIndicesForOverflow(GEPPointerTy, Indices2, Op1C); 340 341 Indices2.push_back((Value*)Op2); 342 } 343 else // Conservatively assume the minimum value for this index 344 Indices2.push_back(Constant::getNullValue(Op2->getType())); 345 } 346 } 347 348 int64_t Offset1 = getTargetData().getIndexedOffset(GEPPointerTy, Indices1); 349 int64_t Offset2 = getTargetData().getIndexedOffset(GEPPointerTy, Indices2); 350 assert(Offset1 < Offset2 &&"There is at least one different constant here!"); 351 352 if ((uint64_t)(Offset2-Offset1) >= SizeMax) { 353 //std::cerr << "Determined that these two GEP's don't alias [" 354 // << SizeMax << " bytes]: \n" << *GEP1 << *GEP2; 355 return NoAlias; 356 } 357 return MayAlias; 358} 359 360