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