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