LLVM API Documentation
00001 //===- BasicAliasAnalysis.cpp - Local Alias Analysis Impl -----------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file defines the default implementation of the Alias Analysis interface 00011 // that simply implements a few identities (two different globals cannot alias, 00012 // etc), but otherwise does no analysis. 00013 // 00014 //===----------------------------------------------------------------------===// 00015 00016 #include "llvm/Analysis/AliasAnalysis.h" 00017 #include "llvm/Constants.h" 00018 #include "llvm/DerivedTypes.h" 00019 #include "llvm/Function.h" 00020 #include "llvm/GlobalVariable.h" 00021 #include "llvm/Instructions.h" 00022 #include "llvm/Pass.h" 00023 #include "llvm/Target/TargetData.h" 00024 #include "llvm/Support/GetElementPtrTypeIterator.h" 00025 #include <algorithm> 00026 using namespace llvm; 00027 00028 // Make sure that anything that uses AliasAnalysis pulls in this file... 00029 void llvm::BasicAAStub() {} 00030 00031 namespace { 00032 /// NoAA - This class implements the -no-aa pass, which always returns "I 00033 /// don't know" for alias queries. NoAA is unlike other alias analysis 00034 /// implementations, in that it does not chain to a previous analysis. As 00035 /// such it doesn't follow many of the rules that other alias analyses must. 00036 /// 00037 struct NoAA : public ImmutablePass, public AliasAnalysis { 00038 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00039 AU.addRequired<TargetData>(); 00040 } 00041 00042 virtual void initializePass() { 00043 TD = &getAnalysis<TargetData>(); 00044 } 00045 00046 virtual AliasResult alias(const Value *V1, unsigned V1Size, 00047 const Value *V2, unsigned V2Size) { 00048 return MayAlias; 00049 } 00050 00051 virtual void getMustAliases(Value *P, std::vector<Value*> &RetVals) { } 00052 virtual bool pointsToConstantMemory(const Value *P) { return false; } 00053 virtual bool doesNotAccessMemory(Function *F) { return false; } 00054 virtual bool onlyReadsMemory(Function *F) { return false; } 00055 virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size) { 00056 return ModRef; 00057 } 00058 virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) { 00059 return ModRef; 00060 } 00061 virtual bool hasNoModRefInfoForCalls() const { return true; } 00062 00063 virtual void deleteValue(Value *V) {} 00064 virtual void copyValue(Value *From, Value *To) {} 00065 }; 00066 00067 // Register this pass... 00068 RegisterOpt<NoAA> 00069 U("no-aa", "No Alias Analysis (always returns 'may' alias)"); 00070 00071 // Declare that we implement the AliasAnalysis interface 00072 RegisterAnalysisGroup<AliasAnalysis, NoAA> V; 00073 } // End of anonymous namespace 00074 00075 00076 namespace { 00077 /// BasicAliasAnalysis - This is the default alias analysis implementation. 00078 /// Because it doesn't chain to a previous alias analysis (like -no-aa), it 00079 /// derives from the NoAA class. 00080 struct BasicAliasAnalysis : public NoAA { 00081 AliasResult alias(const Value *V1, unsigned V1Size, 00082 const Value *V2, unsigned V2Size); 00083 00084 ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size); 00085 00086 /// hasNoModRefInfoForCalls - We can provide mod/ref information against 00087 /// non-escaping allocations. 00088 virtual bool hasNoModRefInfoForCalls() const { return false; } 00089 00090 /// pointsToConstantMemory - Chase pointers until we find a (constant 00091 /// global) or not. 00092 bool pointsToConstantMemory(const Value *P); 00093 00094 virtual bool doesNotAccessMemory(Function *F); 00095 virtual bool onlyReadsMemory(Function *F); 00096 00097 private: 00098 // CheckGEPInstructions - Check two GEP instructions with known 00099 // must-aliasing base pointers. This checks to see if the index expressions 00100 // preclude the pointers from aliasing... 00101 AliasResult 00102 CheckGEPInstructions(const Type* BasePtr1Ty, std::vector<Value*> &GEP1Ops, 00103 unsigned G1Size, 00104 const Type *BasePtr2Ty, std::vector<Value*> &GEP2Ops, 00105 unsigned G2Size); 00106 }; 00107 00108 // Register this pass... 00109 RegisterOpt<BasicAliasAnalysis> 00110 X("basicaa", "Basic Alias Analysis (default AA impl)"); 00111 00112 // Declare that we implement the AliasAnalysis interface 00113 RegisterAnalysisGroup<AliasAnalysis, BasicAliasAnalysis, true> Y; 00114 } // End of anonymous namespace 00115 00116 // hasUniqueAddress - Return true if the specified value points to something 00117 // with a unique, discernable, address. 00118 static inline bool hasUniqueAddress(const Value *V) { 00119 return isa<GlobalValue>(V) || isa<AllocationInst>(V); 00120 } 00121 00122 // getUnderlyingObject - This traverses the use chain to figure out what object 00123 // the specified value points to. If the value points to, or is derived from, a 00124 // unique object or an argument, return it. 00125 static const Value *getUnderlyingObject(const Value *V) { 00126 if (!isa<PointerType>(V->getType())) return 0; 00127 00128 // If we are at some type of object... return it. 00129 if (hasUniqueAddress(V) || isa<Argument>(V)) return V; 00130 00131 // Traverse through different addressing mechanisms... 00132 if (const Instruction *I = dyn_cast<Instruction>(V)) { 00133 if (isa<CastInst>(I) || isa<GetElementPtrInst>(I)) 00134 return getUnderlyingObject(I->getOperand(0)); 00135 } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { 00136 if (CE->getOpcode() == Instruction::Cast || 00137 CE->getOpcode() == Instruction::GetElementPtr) 00138 return getUnderlyingObject(CE->getOperand(0)); 00139 } else if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) { 00140 return GV; 00141 } 00142 return 0; 00143 } 00144 00145 static const User *isGEP(const Value *V) { 00146 if (isa<GetElementPtrInst>(V) || 00147 (isa<ConstantExpr>(V) && 00148 cast<ConstantExpr>(V)->getOpcode() == Instruction::GetElementPtr)) 00149 return cast<User>(V); 00150 return 0; 00151 } 00152 00153 static const Value *GetGEPOperands(const Value *V, std::vector<Value*> &GEPOps){ 00154 assert(GEPOps.empty() && "Expect empty list to populate!"); 00155 GEPOps.insert(GEPOps.end(), cast<User>(V)->op_begin()+1, 00156 cast<User>(V)->op_end()); 00157 00158 // Accumulate all of the chained indexes into the operand array 00159 V = cast<User>(V)->getOperand(0); 00160 00161 while (const User *G = isGEP(V)) { 00162 if (!isa<Constant>(GEPOps[0]) || isa<GlobalValue>(GEPOps[0]) || 00163 !cast<Constant>(GEPOps[0])->isNullValue()) 00164 break; // Don't handle folding arbitrary pointer offsets yet... 00165 GEPOps.erase(GEPOps.begin()); // Drop the zero index 00166 GEPOps.insert(GEPOps.begin(), G->op_begin()+1, G->op_end()); 00167 V = G->getOperand(0); 00168 } 00169 return V; 00170 } 00171 00172 /// pointsToConstantMemory - Chase pointers until we find a (constant 00173 /// global) or not. 00174 bool BasicAliasAnalysis::pointsToConstantMemory(const Value *P) { 00175 if (const Value *V = getUnderlyingObject(P)) 00176 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) 00177 return GV->isConstant(); 00178 return false; 00179 } 00180 00181 static bool AddressMightEscape(const Value *V) { 00182 for (Value::use_const_iterator UI = V->use_begin(), E = V->use_end(); 00183 UI != E; ++UI) { 00184 const Instruction *I = cast<Instruction>(*UI); 00185 switch (I->getOpcode()) { 00186 case Instruction::Load: break; 00187 case Instruction::Store: 00188 if (I->getOperand(0) == V) 00189 return true; // Escapes if the pointer is stored. 00190 break; 00191 case Instruction::GetElementPtr: 00192 if (AddressMightEscape(I)) return true; 00193 break; 00194 case Instruction::Cast: 00195 if (!isa<PointerType>(I->getType())) 00196 return true; 00197 if (AddressMightEscape(I)) return true; 00198 break; 00199 case Instruction::Ret: 00200 // If returned, the address will escape to calling functions, but no 00201 // callees could modify it. 00202 break; 00203 default: 00204 return true; 00205 } 00206 } 00207 return false; 00208 } 00209 00210 // getModRefInfo - Check to see if the specified callsite can clobber the 00211 // specified memory object. Since we only look at local properties of this 00212 // function, we really can't say much about this query. We do, however, use 00213 // simple "address taken" analysis on local objects. 00214 // 00215 AliasAnalysis::ModRefResult 00216 BasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) { 00217 if (!isa<Constant>(P)) 00218 if (const AllocationInst *AI = 00219 dyn_cast_or_null<AllocationInst>(getUnderlyingObject(P))) { 00220 // Okay, the pointer is to a stack allocated object. If we can prove that 00221 // the pointer never "escapes", then we know the call cannot clobber it, 00222 // because it simply can't get its address. 00223 if (!AddressMightEscape(AI)) 00224 return NoModRef; 00225 } 00226 00227 // The AliasAnalysis base class has some smarts, lets use them. 00228 return AliasAnalysis::getModRefInfo(CS, P, Size); 00229 } 00230 00231 // alias - Provide a bunch of ad-hoc rules to disambiguate in common cases, such 00232 // as array references. Note that this function is heavily tail recursive. 00233 // Hopefully we have a smart C++ compiler. :) 00234 // 00235 AliasAnalysis::AliasResult 00236 BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size, 00237 const Value *V2, unsigned V2Size) { 00238 // Strip off any constant expression casts if they exist 00239 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V1)) 00240 if (CE->getOpcode() == Instruction::Cast && 00241 isa<PointerType>(CE->getOperand(0)->getType())) 00242 V1 = CE->getOperand(0); 00243 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V2)) 00244 if (CE->getOpcode() == Instruction::Cast && 00245 isa<PointerType>(CE->getOperand(0)->getType())) 00246 V2 = CE->getOperand(0); 00247 00248 // Are we checking for alias of the same value? 00249 if (V1 == V2) return MustAlias; 00250 00251 if ((!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType())) && 00252 V1->getType() != Type::LongTy && V2->getType() != Type::LongTy) 00253 return NoAlias; // Scalars cannot alias each other 00254 00255 // Strip off cast instructions... 00256 if (const Instruction *I = dyn_cast<CastInst>(V1)) 00257 if (isa<PointerType>(I->getOperand(0)->getType())) 00258 return alias(I->getOperand(0), V1Size, V2, V2Size); 00259 if (const Instruction *I = dyn_cast<CastInst>(V2)) 00260 if (isa<PointerType>(I->getOperand(0)->getType())) 00261 return alias(V1, V1Size, I->getOperand(0), V2Size); 00262 00263 // Figure out what objects these things are pointing to if we can... 00264 const Value *O1 = getUnderlyingObject(V1); 00265 const Value *O2 = getUnderlyingObject(V2); 00266 00267 // Pointing at a discernible object? 00268 if (O1) { 00269 if (O2) { 00270 if (isa<Argument>(O1)) { 00271 // Incoming argument cannot alias locally allocated object! 00272 if (isa<AllocationInst>(O2)) return NoAlias; 00273 // Otherwise, nothing is known... 00274 } else if (isa<Argument>(O2)) { 00275 // Incoming argument cannot alias locally allocated object! 00276 if (isa<AllocationInst>(O1)) return NoAlias; 00277 // Otherwise, nothing is known... 00278 } else if (O1 != O2) { 00279 // If they are two different objects, we know that we have no alias... 00280 return NoAlias; 00281 } 00282 00283 // If they are the same object, they we can look at the indexes. If they 00284 // index off of the object is the same for both pointers, they must alias. 00285 // If they are provably different, they must not alias. Otherwise, we 00286 // can't tell anything. 00287 } 00288 00289 00290 if (!isa<Argument>(O1) && isa<ConstantPointerNull>(V2)) 00291 return NoAlias; // Unique values don't alias null 00292 00293 if (isa<GlobalVariable>(O1) || isa<AllocationInst>(O1)) 00294 if (cast<PointerType>(O1->getType())->getElementType()->isSized()) { 00295 // If the size of the other access is larger than the total size of the 00296 // global/alloca/malloc, it cannot be accessing the global (it's 00297 // undefined to load or store bytes before or after an object). 00298 const Type *ElTy = cast<PointerType>(O1->getType())->getElementType(); 00299 unsigned GlobalSize = getTargetData().getTypeSize(ElTy); 00300 if (GlobalSize < V2Size && V2Size != ~0U) 00301 return NoAlias; 00302 } 00303 } 00304 00305 if (O2) { 00306 if (!isa<Argument>(O2) && isa<ConstantPointerNull>(V1)) 00307 return NoAlias; // Unique values don't alias null 00308 00309 if (isa<GlobalVariable>(O2) || isa<AllocationInst>(O2)) 00310 if (cast<PointerType>(O2->getType())->getElementType()->isSized()) { 00311 // If the size of the other access is larger than the total size of the 00312 // global/alloca/malloc, it cannot be accessing the object (it's 00313 // undefined to load or store bytes before or after an object). 00314 const Type *ElTy = cast<PointerType>(O2->getType())->getElementType(); 00315 unsigned GlobalSize = getTargetData().getTypeSize(ElTy); 00316 if (GlobalSize < V1Size && V1Size != ~0U) 00317 return NoAlias; 00318 } 00319 } 00320 00321 // If we have two gep instructions with must-alias'ing base pointers, figure 00322 // out if the indexes to the GEP tell us anything about the derived pointer. 00323 // Note that we also handle chains of getelementptr instructions as well as 00324 // constant expression getelementptrs here. 00325 // 00326 if (isGEP(V1) && isGEP(V2)) { 00327 // Drill down into the first non-gep value, to test for must-aliasing of 00328 // the base pointers. 00329 const Value *BasePtr1 = V1, *BasePtr2 = V2; 00330 do { 00331 BasePtr1 = cast<User>(BasePtr1)->getOperand(0); 00332 } while (isGEP(BasePtr1) && 00333 cast<User>(BasePtr1)->getOperand(1) == 00334 Constant::getNullValue(cast<User>(BasePtr1)->getOperand(1)->getType())); 00335 do { 00336 BasePtr2 = cast<User>(BasePtr2)->getOperand(0); 00337 } while (isGEP(BasePtr2) && 00338 cast<User>(BasePtr2)->getOperand(1) == 00339 Constant::getNullValue(cast<User>(BasePtr2)->getOperand(1)->getType())); 00340 00341 // Do the base pointers alias? 00342 AliasResult BaseAlias = alias(BasePtr1, V1Size, BasePtr2, V2Size); 00343 if (BaseAlias == NoAlias) return NoAlias; 00344 if (BaseAlias == MustAlias) { 00345 // If the base pointers alias each other exactly, check to see if we can 00346 // figure out anything about the resultant pointers, to try to prove 00347 // non-aliasing. 00348 00349 // Collect all of the chained GEP operands together into one simple place 00350 std::vector<Value*> GEP1Ops, GEP2Ops; 00351 BasePtr1 = GetGEPOperands(V1, GEP1Ops); 00352 BasePtr2 = GetGEPOperands(V2, GEP2Ops); 00353 00354 // If GetGEPOperands were able to fold to the same must-aliased pointer, 00355 // do the comparison. 00356 if (BasePtr1 == BasePtr2) { 00357 AliasResult GAlias = 00358 CheckGEPInstructions(BasePtr1->getType(), GEP1Ops, V1Size, 00359 BasePtr2->getType(), GEP2Ops, V2Size); 00360 if (GAlias != MayAlias) 00361 return GAlias; 00362 } 00363 } 00364 } 00365 00366 // Check to see if these two pointers are related by a getelementptr 00367 // instruction. If one pointer is a GEP with a non-zero index of the other 00368 // pointer, we know they cannot alias. 00369 // 00370 if (isGEP(V2)) { 00371 std::swap(V1, V2); 00372 std::swap(V1Size, V2Size); 00373 } 00374 00375 if (V1Size != ~0U && V2Size != ~0U) 00376 if (const User *GEP = isGEP(V1)) { 00377 std::vector<Value*> GEPOperands; 00378 const Value *BasePtr = GetGEPOperands(V1, GEPOperands); 00379 00380 AliasResult R = alias(BasePtr, V1Size, V2, V2Size); 00381 if (R == MustAlias) { 00382 // If there is at least one non-zero constant index, we know they cannot 00383 // alias. 00384 bool ConstantFound = false; 00385 bool AllZerosFound = true; 00386 for (unsigned i = 0, e = GEPOperands.size(); i != e; ++i) 00387 if (const Constant *C = dyn_cast<Constant>(GEPOperands[i])) { 00388 if (!C->isNullValue()) { 00389 ConstantFound = true; 00390 AllZerosFound = false; 00391 break; 00392 } 00393 } else { 00394 AllZerosFound = false; 00395 } 00396 00397 // If we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 must aliases 00398 // the ptr, the end result is a must alias also. 00399 if (AllZerosFound) 00400 return MustAlias; 00401 00402 if (ConstantFound) { 00403 if (V2Size <= 1 && V1Size <= 1) // Just pointer check? 00404 return NoAlias; 00405 00406 // Otherwise we have to check to see that the distance is more than 00407 // the size of the argument... build an index vector that is equal to 00408 // the arguments provided, except substitute 0's for any variable 00409 // indexes we find... 00410 for (unsigned i = 0; i != GEPOperands.size(); ++i) 00411 if (!isa<ConstantInt>(GEPOperands[i])) 00412 GEPOperands[i] =Constant::getNullValue(GEPOperands[i]->getType()); 00413 int64_t Offset = getTargetData().getIndexedOffset(BasePtr->getType(), 00414 GEPOperands); 00415 if (Offset >= (int64_t)V2Size || Offset <= -(int64_t)V1Size) 00416 return NoAlias; 00417 } 00418 } 00419 } 00420 00421 return MayAlias; 00422 } 00423 00424 static bool ValuesEqual(Value *V1, Value *V2) { 00425 if (V1->getType() == V2->getType()) 00426 return V1 == V2; 00427 if (Constant *C1 = dyn_cast<Constant>(V1)) 00428 if (Constant *C2 = dyn_cast<Constant>(V2)) { 00429 // Sign extend the constants to long types. 00430 C1 = ConstantExpr::getSignExtend(C1, Type::LongTy); 00431 C2 = ConstantExpr::getSignExtend(C2, Type::LongTy); 00432 return C1 == C2; 00433 } 00434 return false; 00435 } 00436 00437 /// CheckGEPInstructions - Check two GEP instructions with known must-aliasing 00438 /// base pointers. This checks to see if the index expressions preclude the 00439 /// pointers from aliasing... 00440 AliasAnalysis::AliasResult BasicAliasAnalysis:: 00441 CheckGEPInstructions(const Type* BasePtr1Ty, std::vector<Value*> &GEP1Ops, 00442 unsigned G1S, 00443 const Type *BasePtr2Ty, std::vector<Value*> &GEP2Ops, 00444 unsigned G2S) { 00445 // We currently can't handle the case when the base pointers have different 00446 // primitive types. Since this is uncommon anyway, we are happy being 00447 // extremely conservative. 00448 if (BasePtr1Ty != BasePtr2Ty) 00449 return MayAlias; 00450 00451 const Type *GEPPointerTy = BasePtr1Ty; 00452 00453 // Find the (possibly empty) initial sequence of equal values... which are not 00454 // necessarily constants. 00455 unsigned NumGEP1Operands = GEP1Ops.size(), NumGEP2Operands = GEP2Ops.size(); 00456 unsigned MinOperands = std::min(NumGEP1Operands, NumGEP2Operands); 00457 unsigned MaxOperands = std::max(NumGEP1Operands, NumGEP2Operands); 00458 unsigned UnequalOper = 0; 00459 while (UnequalOper != MinOperands && 00460 ValuesEqual(GEP1Ops[UnequalOper], GEP2Ops[UnequalOper])) { 00461 // Advance through the type as we go... 00462 ++UnequalOper; 00463 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty)) 00464 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[UnequalOper-1]); 00465 else { 00466 // If all operands equal each other, then the derived pointers must 00467 // alias each other... 00468 BasePtr1Ty = 0; 00469 assert(UnequalOper == NumGEP1Operands && UnequalOper == NumGEP2Operands && 00470 "Ran out of type nesting, but not out of operands?"); 00471 return MustAlias; 00472 } 00473 } 00474 00475 // If we have seen all constant operands, and run out of indexes on one of the 00476 // getelementptrs, check to see if the tail of the leftover one is all zeros. 00477 // If so, return mustalias. 00478 if (UnequalOper == MinOperands) { 00479 if (GEP1Ops.size() < GEP2Ops.size()) std::swap(GEP1Ops, GEP2Ops); 00480 00481 bool AllAreZeros = true; 00482 for (unsigned i = UnequalOper; i != MaxOperands; ++i) 00483 if (!isa<Constant>(GEP1Ops[i]) || 00484 !cast<Constant>(GEP1Ops[i])->isNullValue()) { 00485 AllAreZeros = false; 00486 break; 00487 } 00488 if (AllAreZeros) return MustAlias; 00489 } 00490 00491 00492 // So now we know that the indexes derived from the base pointers, 00493 // which are known to alias, are different. We can still determine a 00494 // no-alias result if there are differing constant pairs in the index 00495 // chain. For example: 00496 // A[i][0] != A[j][1] iff (&A[0][1]-&A[0][0] >= std::max(G1S, G2S)) 00497 // 00498 unsigned SizeMax = std::max(G1S, G2S); 00499 if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work. 00500 00501 // Scan for the first operand that is constant and unequal in the 00502 // two getelementptrs... 00503 unsigned FirstConstantOper = UnequalOper; 00504 for (; FirstConstantOper != MinOperands; ++FirstConstantOper) { 00505 const Value *G1Oper = GEP1Ops[FirstConstantOper]; 00506 const Value *G2Oper = GEP2Ops[FirstConstantOper]; 00507 00508 if (G1Oper != G2Oper) // Found non-equal constant indexes... 00509 if (Constant *G1OC = dyn_cast<ConstantInt>(const_cast<Value*>(G1Oper))) 00510 if (Constant *G2OC = dyn_cast<ConstantInt>(const_cast<Value*>(G2Oper))){ 00511 if (G1OC->getType() != G2OC->getType()) { 00512 // Sign extend both operands to long. 00513 G1OC = ConstantExpr::getSignExtend(G1OC, Type::LongTy); 00514 G2OC = ConstantExpr::getSignExtend(G2OC, Type::LongTy); 00515 GEP1Ops[FirstConstantOper] = G1OC; 00516 GEP2Ops[FirstConstantOper] = G2OC; 00517 } 00518 00519 if (G1OC != G2OC) { 00520 // Make sure they are comparable (ie, not constant expressions), and 00521 // make sure the GEP with the smaller leading constant is GEP1. 00522 Constant *Compare = ConstantExpr::getSetGT(G1OC, G2OC); 00523 if (ConstantBool *CV = dyn_cast<ConstantBool>(Compare)) { 00524 if (CV->getValue()) // If they are comparable and G2 > G1 00525 std::swap(GEP1Ops, GEP2Ops); // Make GEP1 < GEP2 00526 break; 00527 } 00528 } 00529 } 00530 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(G1Oper); 00531 } 00532 00533 // No shared constant operands, and we ran out of common operands. At this 00534 // point, the GEP instructions have run through all of their operands, and we 00535 // haven't found evidence that there are any deltas between the GEP's. 00536 // However, one GEP may have more operands than the other. If this is the 00537 // case, there may still be hope. Check this now. 00538 if (FirstConstantOper == MinOperands) { 00539 // Make GEP1Ops be the longer one if there is a longer one. 00540 if (GEP1Ops.size() < GEP2Ops.size()) 00541 std::swap(GEP1Ops, GEP2Ops); 00542 00543 // Is there anything to check? 00544 if (GEP1Ops.size() > MinOperands) { 00545 for (unsigned i = FirstConstantOper; i != MaxOperands; ++i) 00546 if (isa<ConstantInt>(GEP1Ops[i]) && 00547 !cast<Constant>(GEP1Ops[i])->isNullValue()) { 00548 // Yup, there's a constant in the tail. Set all variables to 00549 // constants in the GEP instruction to make it suiteable for 00550 // TargetData::getIndexedOffset. 00551 for (i = 0; i != MaxOperands; ++i) 00552 if (!isa<ConstantInt>(GEP1Ops[i])) 00553 GEP1Ops[i] = Constant::getNullValue(GEP1Ops[i]->getType()); 00554 // Okay, now get the offset. This is the relative offset for the full 00555 // instruction. 00556 const TargetData &TD = getTargetData(); 00557 int64_t Offset1 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops); 00558 00559 // Now crop off any constants from the end... 00560 GEP1Ops.resize(MinOperands); 00561 int64_t Offset2 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops); 00562 00563 // If the tail provided a bit enough offset, return noalias! 00564 if ((uint64_t)(Offset2-Offset1) >= SizeMax) 00565 return NoAlias; 00566 } 00567 } 00568 00569 // Couldn't find anything useful. 00570 return MayAlias; 00571 } 00572 00573 // If there are non-equal constants arguments, then we can figure 00574 // out a minimum known delta between the two index expressions... at 00575 // this point we know that the first constant index of GEP1 is less 00576 // than the first constant index of GEP2. 00577 00578 // Advance BasePtr[12]Ty over this first differing constant operand. 00579 BasePtr2Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(GEP2Ops[FirstConstantOper]); 00580 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(GEP1Ops[FirstConstantOper]); 00581 00582 // We are going to be using TargetData::getIndexedOffset to determine the 00583 // offset that each of the GEP's is reaching. To do this, we have to convert 00584 // all variable references to constant references. To do this, we convert the 00585 // initial equal sequence of variables into constant zeros to start with. 00586 for (unsigned i = 0; i != FirstConstantOper; ++i) 00587 if (!isa<ConstantInt>(GEP1Ops[i]) || !isa<ConstantInt>(GEP2Ops[i])) 00588 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Type::UIntTy); 00589 00590 // We know that GEP1Ops[FirstConstantOper] & GEP2Ops[FirstConstantOper] are ok 00591 00592 // Loop over the rest of the operands... 00593 for (unsigned i = FirstConstantOper+1; i != MaxOperands; ++i) { 00594 const Value *Op1 = i < GEP1Ops.size() ? GEP1Ops[i] : 0; 00595 const Value *Op2 = i < GEP2Ops.size() ? GEP2Ops[i] : 0; 00596 // If they are equal, use a zero index... 00597 if (Op1 == Op2 && BasePtr1Ty == BasePtr2Ty) { 00598 if (!isa<ConstantInt>(Op1)) 00599 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Op1->getType()); 00600 // Otherwise, just keep the constants we have. 00601 } else { 00602 if (Op1) { 00603 if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) { 00604 // If this is an array index, make sure the array element is in range. 00605 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) 00606 if (Op1C->getRawValue() >= AT->getNumElements()) 00607 return MayAlias; // Be conservative with out-of-range accesses 00608 00609 } else { 00610 // GEP1 is known to produce a value less than GEP2. To be 00611 // conservatively correct, we must assume the largest possible 00612 // constant is used in this position. This cannot be the initial 00613 // index to the GEP instructions (because we know we have at least one 00614 // element before this one with the different constant arguments), so 00615 // we know that the current index must be into either a struct or 00616 // array. Because we know it's not constant, this cannot be a 00617 // structure index. Because of this, we can calculate the maximum 00618 // value possible. 00619 // 00620 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) 00621 GEP1Ops[i] = ConstantSInt::get(Type::LongTy,AT->getNumElements()-1); 00622 } 00623 } 00624 00625 if (Op2) { 00626 if (const ConstantInt *Op2C = dyn_cast<ConstantInt>(Op2)) { 00627 // If this is an array index, make sure the array element is in range. 00628 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) 00629 if (Op2C->getRawValue() >= AT->getNumElements()) 00630 return MayAlias; // Be conservative with out-of-range accesses 00631 } else { // Conservatively assume the minimum value for this index 00632 GEP2Ops[i] = Constant::getNullValue(Op2->getType()); 00633 } 00634 } 00635 } 00636 00637 if (BasePtr1Ty && Op1) { 00638 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty)) 00639 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[i]); 00640 else 00641 BasePtr1Ty = 0; 00642 } 00643 00644 if (BasePtr2Ty && Op2) { 00645 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr2Ty)) 00646 BasePtr2Ty = CT->getTypeAtIndex(GEP2Ops[i]); 00647 else 00648 BasePtr2Ty = 0; 00649 } 00650 } 00651 00652 int64_t Offset1 = getTargetData().getIndexedOffset(GEPPointerTy, GEP1Ops); 00653 int64_t Offset2 = getTargetData().getIndexedOffset(GEPPointerTy, GEP2Ops); 00654 assert(Offset1 < Offset2 &&"There is at least one different constant here!"); 00655 00656 if ((uint64_t)(Offset2-Offset1) >= SizeMax) { 00657 //std::cerr << "Determined that these two GEP's don't alias [" 00658 // << SizeMax << " bytes]: \n" << *GEP1 << *GEP2; 00659 return NoAlias; 00660 } 00661 return MayAlias; 00662 } 00663 00664 namespace { 00665 struct StringCompare { 00666 bool operator()(const char *LHS, const char *RHS) { 00667 return strcmp(LHS, RHS) < 0; 00668 } 00669 }; 00670 } 00671 00672 // Note that this list cannot contain libm functions (such as acos and sqrt) 00673 // that set errno on a domain or other error. 00674 static const char *DoesntAccessMemoryTable[] = { 00675 // LLVM intrinsics: 00676 "llvm.frameaddress", "llvm.returnaddress", "llvm.readport", "llvm.isunordered", 00677 00678 "abs", "labs", "llabs", "imaxabs", "fabs", "fabsf", "fabsl", 00679 "trunc", "truncf", "truncl", "ldexp", 00680 00681 "atan", "atanf", "atanl", "atan2", "atan2f", "atan2l", 00682 "cbrt", 00683 "cos", "cosf", "cosl", "cosh", "coshf", "coshl", 00684 "exp", "expf", "expl", 00685 "hypot", 00686 "sin", "sinf", "sinl", "sinh", "sinhf", "sinhl", 00687 "tan", "tanf", "tanl", "tanh", "tanhf", "tanhl", 00688 00689 // ctype.h 00690 "isalnum", "isalpha", "iscntrl", "isdigit", "isgraph", "islower", "isprint" 00691 "ispunct", "isspace", "isupper", "isxdigit", "tolower", "toupper", 00692 00693 // wctype.h" 00694 "iswalnum", "iswalpha", "iswcntrl", "iswdigit", "iswgraph", "iswlower", 00695 "iswprint", "iswpunct", "iswspace", "iswupper", "iswxdigit", 00696 00697 "iswctype", "towctrans", "towlower", "towupper", 00698 00699 "btowc", "wctob", 00700 00701 "isinf", "isnan", "finite", 00702 00703 // C99 math functions 00704 "copysign", "copysignf", "copysignd", 00705 "nexttoward", "nexttowardf", "nexttowardd", 00706 "nextafter", "nextafterf", "nextafterd", 00707 00708 // glibc functions: 00709 "__fpclassify", "__fpclassifyf", "__fpclassifyl", 00710 "__signbit", "__signbitf", "__signbitl", 00711 }; 00712 00713 static const unsigned DAMTableSize = 00714 sizeof(DoesntAccessMemoryTable)/sizeof(DoesntAccessMemoryTable[0]); 00715 00716 /// doesNotAccessMemory - Return true if we know that the function does not 00717 /// access memory at all. Since basicaa does no analysis, we can only do simple 00718 /// things here. In particular, if we have an external function with the name 00719 /// of a standard C library function, we are allowed to assume it will be 00720 /// resolved by libc, so we can hardcode some entries in here. 00721 bool BasicAliasAnalysis::doesNotAccessMemory(Function *F) { 00722 if (!F->isExternal()) return false; 00723 00724 static bool Initialized = false; 00725 if (!Initialized) { 00726 // Sort the table the first time through. 00727 std::sort(DoesntAccessMemoryTable, DoesntAccessMemoryTable+DAMTableSize, 00728 StringCompare()); 00729 Initialized = true; 00730 } 00731 00732 const char **Ptr = std::lower_bound(DoesntAccessMemoryTable, 00733 DoesntAccessMemoryTable+DAMTableSize, 00734 F->getName().c_str(), StringCompare()); 00735 return Ptr != DoesntAccessMemoryTable+DAMTableSize && *Ptr == F->getName(); 00736 } 00737 00738 00739 static const char *OnlyReadsMemoryTable[] = { 00740 "atoi", "atol", "atof", "atoll", "atoq", "a64l", 00741 "bcmp", "memcmp", "memchr", "memrchr", "wmemcmp", "wmemchr", 00742 00743 // Strings 00744 "strcmp", "strcasecmp", "strcoll", "strncmp", "strncasecmp", 00745 "strchr", "strcspn", "strlen", "strpbrk", "strrchr", "strspn", "strstr", 00746 "index", "rindex", 00747 00748 // Wide char strings 00749 "wcschr", "wcscmp", "wcscoll", "wcscspn", "wcslen", "wcsncmp", "wcspbrk", 00750 "wcsrchr", "wcsspn", "wcsstr", 00751 00752 // glibc 00753 "alphasort", "alphasort64", "versionsort", "versionsort64", 00754 00755 // C99 00756 "nan", "nanf", "nand", 00757 00758 // File I/O 00759 "feof", "ferror", "fileno", 00760 "feof_unlocked", "ferror_unlocked", "fileno_unlocked" 00761 }; 00762 00763 static const unsigned ORMTableSize = 00764 sizeof(OnlyReadsMemoryTable)/sizeof(OnlyReadsMemoryTable[0]); 00765 00766 bool BasicAliasAnalysis::onlyReadsMemory(Function *F) { 00767 if (doesNotAccessMemory(F)) return true; 00768 if (!F->isExternal()) return false; 00769 00770 static bool Initialized = false; 00771 if (!Initialized) { 00772 // Sort the table the first time through. 00773 std::sort(OnlyReadsMemoryTable, OnlyReadsMemoryTable+ORMTableSize, 00774 StringCompare()); 00775 Initialized = true; 00776 } 00777 00778 const char **Ptr = std::lower_bound(OnlyReadsMemoryTable, 00779 OnlyReadsMemoryTable+ORMTableSize, 00780 F->getName().c_str(), StringCompare()); 00781 return Ptr != OnlyReadsMemoryTable+ORMTableSize && *Ptr == F->getName(); 00782 } 00783 00784