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