BasicAliasAnalysis.cpp revision a36635aba78d46d0e80dd296c3b0aff56ca94d5e
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 21class GetElementPtrInst; 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 } 73 return 0; 74} 75 76 77// alias - Provide a bunch of ad-hoc rules to disambiguate in common cases, such 78// as array references. Note that this function is heavily tail recursive. 79// Hopefully we have a smart C++ compiler. :) 80// 81AliasAnalysis::AliasResult 82BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size, 83 const Value *V2, unsigned V2Size) { 84 // Strip off constant pointer refs if they exist 85 if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V1)) 86 V1 = CPR->getValue(); 87 if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V2)) 88 V2 = CPR->getValue(); 89 90 // Are we checking for alias of the same value? 91 if (V1 == V2) return MustAlias; 92 93 if ((!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType())) && 94 V1->getType() != Type::LongTy && V2->getType() != Type::LongTy) 95 return NoAlias; // Scalars cannot alias each other 96 97 // Strip off cast instructions... 98 if (const Instruction *I = dyn_cast<CastInst>(V1)) 99 return alias(I->getOperand(0), V1Size, V2, V2Size); 100 if (const Instruction *I = dyn_cast<CastInst>(V2)) 101 return alias(V1, V1Size, I->getOperand(0), V2Size); 102 103 // Figure out what objects these things are pointing to if we can... 104 const Value *O1 = getUnderlyingObject(V1); 105 const Value *O2 = getUnderlyingObject(V2); 106 107 // Pointing at a discernable object? 108 if (O1 && O2) { 109 // If they are two different objects, we know that we have no alias... 110 if (O1 != O2) return NoAlias; 111 112 // If they are the same object, they we can look at the indexes. If they 113 // index off of the object is the same for both pointers, they must alias. 114 // If they are provably different, they must not alias. Otherwise, we can't 115 // tell anything. 116 } else if (O1 && isa<ConstantPointerNull>(V2)) { 117 return NoAlias; // Unique values don't alias null 118 } else if (O2 && isa<ConstantPointerNull>(V1)) { 119 return NoAlias; // Unique values don't alias null 120 } 121 122 // If we have two gep instructions with identical indices, return an alias 123 // result equal to the alias result of the original pointer... 124 // 125 if (const GetElementPtrInst *GEP1 = dyn_cast<GetElementPtrInst>(V1)) 126 if (const GetElementPtrInst *GEP2 = dyn_cast<GetElementPtrInst>(V2)) 127 if (GEP1->getNumOperands() == GEP2->getNumOperands() && 128 GEP1->getOperand(0)->getType() == GEP2->getOperand(0)->getType()) { 129 AliasResult GAlias = 130 CheckGEPInstructions((GetElementPtrInst*)GEP1, V1Size, 131 (GetElementPtrInst*)GEP2, V2Size); 132 if (GAlias != MayAlias) 133 return GAlias; 134 } 135 136 // Check to see if these two pointers are related by a getelementptr 137 // instruction. If one pointer is a GEP with a non-zero index of the other 138 // pointer, we know they cannot alias. 139 // 140 if (isa<GetElementPtrInst>(V2)) { 141 std::swap(V1, V2); 142 std::swap(V1Size, V2Size); 143 } 144 145 if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(V1)) { 146 AliasResult R = alias(GEP->getOperand(0), V1Size, V2, V2Size); 147 if (R == NoAlias) return NoAlias; 148 if (R == MustAlias) { 149 // If there is at least one non-zero constant index, we know they cannot 150 // alias. 151 for (unsigned i = 1, e = GEP->getNumOperands(); i != e; ++i) 152 if (const Constant *C = dyn_cast<Constant>(GEP->getOperand(i))) 153 if (!C->isNullValue()) 154 return NoAlias; 155 } 156 } 157 158 return MayAlias; 159} 160 161// CheckGEPInstructions - Check two GEP instructions of compatible types and 162// equal number of arguments. This checks to see if the index expressions 163// preclude the pointers from aliasing... 164// 165AliasAnalysis::AliasResult 166BasicAliasAnalysis::CheckGEPInstructions(GetElementPtrInst *GEP1, unsigned G1S, 167 GetElementPtrInst *GEP2, unsigned G2S){ 168 // Do the base pointers alias? 169 AliasResult BaseAlias = alias(GEP1->getOperand(0), G1S, 170 GEP2->getOperand(0), G2S); 171 if (BaseAlias != MustAlias) // No or May alias: We cannot add anything... 172 return BaseAlias; 173 174 // Find the (possibly empty) initial sequence of equal values... 175 unsigned NumGEPOperands = GEP1->getNumOperands(); 176 unsigned UnequalOper = 1; 177 while (UnequalOper != NumGEPOperands && 178 GEP1->getOperand(UnequalOper) == GEP2->getOperand(UnequalOper)) 179 ++UnequalOper; 180 181 // If all operands equal each other, then the derived pointers must 182 // alias each other... 183 if (UnequalOper == NumGEPOperands) return MustAlias; 184 185 // So now we know that the indexes derived from the base pointers, 186 // which are known to alias, are different. We can still determine a 187 // no-alias result if there are differing constant pairs in the index 188 // chain. For example: 189 // A[i][0] != A[j][1] iff (&A[0][1]-&A[0][0] >= std::max(G1S, G2S)) 190 // 191 unsigned SizeMax = std::max(G1S, G2S); 192 if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work... 193 194 // Scan for the first operand that is constant and unequal in the 195 // two getelemenptrs... 196 unsigned FirstConstantOper = UnequalOper; 197 for (; FirstConstantOper != NumGEPOperands; ++FirstConstantOper) { 198 const Value *G1Oper = GEP1->getOperand(FirstConstantOper); 199 const Value *G2Oper = GEP2->getOperand(FirstConstantOper); 200 if (G1Oper != G2Oper && // Found non-equal constant indexes... 201 isa<Constant>(G1Oper) && isa<Constant>(G2Oper)) { 202 // Make sure they are comparable... and make sure the GEP with 203 // the smaller leading constant is GEP1. 204 ConstantBool *Compare = 205 *cast<Constant>(GEP1->getOperand(FirstConstantOper)) > 206 *cast<Constant>(GEP2->getOperand(FirstConstantOper)); 207 if (Compare) { // If they are comparable... 208 if (Compare->getValue()) 209 std::swap(GEP1, GEP2); // Make GEP1 < GEP2 210 break; 211 } 212 } 213 } 214 215 // No constant operands, we cannot tell anything... 216 if (FirstConstantOper == NumGEPOperands) return MayAlias; 217 218 // If there are non-equal constants arguments, then we can figure 219 // out a minimum known delta between the two index expressions... at 220 // this point we know that the first constant index of GEP1 is less 221 // than the first constant index of GEP2. 222 // 223 std::vector<Value*> Indices1; 224 Indices1.reserve(NumGEPOperands-1); 225 for (unsigned i = 1; i != FirstConstantOper; ++i) 226 if (GEP1->getOperand(i)->getType() == Type::UByteTy) 227 Indices1.push_back(GEP1->getOperand(i)); 228 else 229 Indices1.push_back(Constant::getNullValue(Type::LongTy)); 230 std::vector<Value*> Indices2; 231 Indices2.reserve(NumGEPOperands-1); 232 Indices2 = Indices1; // Copy the zeros prefix... 233 234 // Add the two known constant operands... 235 Indices1.push_back((Value*)GEP1->getOperand(FirstConstantOper)); 236 Indices2.push_back((Value*)GEP2->getOperand(FirstConstantOper)); 237 238 const Type *GEPPointerTy = GEP1->getOperand(0)->getType(); 239 240 // Loop over the rest of the operands... 241 for (unsigned i = FirstConstantOper+1; i!=NumGEPOperands; ++i){ 242 const Value *Op1 = GEP1->getOperand(i); 243 const Value *Op2 = GEP2->getOperand(i); 244 if (Op1 == Op2) { // If they are equal, use a zero index... 245 Indices1.push_back(Constant::getNullValue(Op1->getType())); 246 Indices2.push_back(Indices1.back()); 247 } else { 248 if (isa<Constant>(Op1)) 249 Indices1.push_back((Value*)Op1); 250 else { 251 // GEP1 is known to produce a value less than GEP2. To be 252 // conservatively correct, we must assume the largest 253 // possible constant is used in this position. This cannot 254 // be the initial index to the GEP instructions (because we 255 // know we have at least one element before this one with 256 // the different constant arguments), so we know that the 257 // current index must be into either a struct or array. 258 // Because of this, we can calculate the maximum value 259 // possible. 260 // 261 const Type *ElTy = GEP1->getIndexedType(GEPPointerTy, 262 Indices1, true); 263 if (const StructType *STy = dyn_cast<StructType>(ElTy)) { 264 Indices1.push_back(ConstantUInt::get(Type::UByteTy, 265 STy->getNumContainedTypes())); 266 } else { 267 Indices1.push_back(ConstantSInt::get(Type::LongTy, 268 cast<ArrayType>(ElTy)->getNumElements())); 269 } 270 } 271 272 if (isa<Constant>(Op2)) 273 Indices2.push_back((Value*)Op2); 274 else // Conservatively assume the minimum value for this index 275 Indices2.push_back(Constant::getNullValue(Op1->getType())); 276 } 277 } 278 279 unsigned Offset1 = getTargetData().getIndexedOffset(GEPPointerTy, Indices1); 280 unsigned Offset2 = getTargetData().getIndexedOffset(GEPPointerTy, Indices2); 281 assert(Offset1 < Offset2 &&"There is at least one different constant here!"); 282 283 if (Offset2-Offset1 >= SizeMax) { 284 //std::cerr << "Determined that these two GEP's don't alias [" 285 // << SizeMax << " bytes]: \n" << *GEP1 << *GEP2; 286 return NoAlias; 287 } 288 return MayAlias; 289} 290 291