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