LLVM API Documentation
00001 //===- BasicAliasAnalysis.cpp - Local Alias Analysis Impl -----------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // 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/CaptureTracking.h" 00018 #include "llvm/Analysis/Passes.h" 00019 #include "llvm/Constants.h" 00020 #include "llvm/DerivedTypes.h" 00021 #include "llvm/Function.h" 00022 #include "llvm/GlobalVariable.h" 00023 #include "llvm/Instructions.h" 00024 #include "llvm/IntrinsicInst.h" 00025 #include "llvm/LLVMContext.h" 00026 #include "llvm/Operator.h" 00027 #include "llvm/Pass.h" 00028 #include "llvm/Target/TargetData.h" 00029 #include "llvm/ADT/SmallVector.h" 00030 #include "llvm/ADT/STLExtras.h" 00031 #include "llvm/Support/Compiler.h" 00032 #include "llvm/Support/ErrorHandling.h" 00033 #include "llvm/Support/GetElementPtrTypeIterator.h" 00034 #include <algorithm> 00035 using namespace llvm; 00036 00037 //===----------------------------------------------------------------------===// 00038 // Useful predicates 00039 //===----------------------------------------------------------------------===// 00040 00041 static const GEPOperator *isGEP(const Value *V) { 00042 return dyn_cast<GEPOperator>(V); 00043 } 00044 00045 static const Value *GetGEPOperands(const Value *V, 00046 SmallVector<Value*, 16> &GEPOps) { 00047 assert(GEPOps.empty() && "Expect empty list to populate!"); 00048 GEPOps.insert(GEPOps.end(), cast<User>(V)->op_begin()+1, 00049 cast<User>(V)->op_end()); 00050 00051 // Accumulate all of the chained indexes into the operand array 00052 V = cast<User>(V)->getOperand(0); 00053 00054 while (const User *G = isGEP(V)) { 00055 if (!isa<Constant>(GEPOps[0]) || isa<GlobalValue>(GEPOps[0]) || 00056 !cast<Constant>(GEPOps[0])->isNullValue()) 00057 break; // Don't handle folding arbitrary pointer offsets yet... 00058 GEPOps.erase(GEPOps.begin()); // Drop the zero index 00059 GEPOps.insert(GEPOps.begin(), G->op_begin()+1, G->op_end()); 00060 V = G->getOperand(0); 00061 } 00062 return V; 00063 } 00064 00065 /// isKnownNonNull - Return true if we know that the specified value is never 00066 /// null. 00067 static bool isKnownNonNull(const Value *V) { 00068 // Alloca never returns null, malloc might. 00069 if (isa<AllocaInst>(V)) return true; 00070 00071 // A byval argument is never null. 00072 if (const Argument *A = dyn_cast<Argument>(V)) 00073 return A->hasByValAttr(); 00074 00075 // Global values are not null unless extern weak. 00076 if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) 00077 return !GV->hasExternalWeakLinkage(); 00078 return false; 00079 } 00080 00081 /// isNonEscapingLocalObject - Return true if the pointer is to a function-local 00082 /// object that never escapes from the function. 00083 static bool isNonEscapingLocalObject(const Value *V) { 00084 // If this is a local allocation, check to see if it escapes. 00085 if (isa<AllocationInst>(V) || isNoAliasCall(V)) 00086 return !PointerMayBeCaptured(V, false); 00087 00088 // If this is an argument that corresponds to a byval or noalias argument, 00089 // then it has not escaped before entering the function. Check if it escapes 00090 // inside the function. 00091 if (const Argument *A = dyn_cast<Argument>(V)) 00092 if (A->hasByValAttr() || A->hasNoAliasAttr()) { 00093 // Don't bother analyzing arguments already known not to escape. 00094 if (A->hasNoCaptureAttr()) 00095 return true; 00096 return !PointerMayBeCaptured(V, false); 00097 } 00098 return false; 00099 } 00100 00101 00102 /// isObjectSmallerThan - Return true if we can prove that the object specified 00103 /// by V is smaller than Size. 00104 static bool isObjectSmallerThan(const Value *V, unsigned Size, 00105 const TargetData &TD) { 00106 const Type *AccessTy; 00107 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) { 00108 AccessTy = GV->getType()->getElementType(); 00109 } else if (const AllocationInst *AI = dyn_cast<AllocationInst>(V)) { 00110 if (!AI->isArrayAllocation()) 00111 AccessTy = AI->getType()->getElementType(); 00112 else 00113 return false; 00114 } else if (const Argument *A = dyn_cast<Argument>(V)) { 00115 if (A->hasByValAttr()) 00116 AccessTy = cast<PointerType>(A->getType())->getElementType(); 00117 else 00118 return false; 00119 } else { 00120 return false; 00121 } 00122 00123 if (AccessTy->isSized()) 00124 return TD.getTypeAllocSize(AccessTy) < Size; 00125 return false; 00126 } 00127 00128 //===----------------------------------------------------------------------===// 00129 // NoAA Pass 00130 //===----------------------------------------------------------------------===// 00131 00132 namespace { 00133 /// NoAA - This class implements the -no-aa pass, which always returns "I 00134 /// don't know" for alias queries. NoAA is unlike other alias analysis 00135 /// implementations, in that it does not chain to a previous analysis. As 00136 /// such it doesn't follow many of the rules that other alias analyses must. 00137 /// 00138 struct VISIBILITY_HIDDEN NoAA : public ImmutablePass, public AliasAnalysis { 00139 static char ID; // Class identification, replacement for typeinfo 00140 NoAA() : ImmutablePass(&ID) {} 00141 explicit NoAA(void *PID) : ImmutablePass(PID) { } 00142 00143 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00144 } 00145 00146 virtual void initializePass() { 00147 TD = getAnalysisIfAvailable<TargetData>(); 00148 } 00149 00150 virtual AliasResult alias(const Value *V1, unsigned V1Size, 00151 const Value *V2, unsigned V2Size) { 00152 return MayAlias; 00153 } 00154 00155 virtual void getArgumentAccesses(Function *F, CallSite CS, 00156 std::vector<PointerAccessInfo> &Info) { 00157 llvm_unreachable("This method may not be called on this function!"); 00158 } 00159 00160 virtual void getMustAliases(Value *P, std::vector<Value*> &RetVals) { } 00161 virtual bool pointsToConstantMemory(const Value *P) { return false; } 00162 virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size) { 00163 return ModRef; 00164 } 00165 virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) { 00166 return ModRef; 00167 } 00168 virtual bool hasNoModRefInfoForCalls() const { return true; } 00169 00170 virtual void deleteValue(Value *V) {} 00171 virtual void copyValue(Value *From, Value *To) {} 00172 }; 00173 } // End of anonymous namespace 00174 00175 // Register this pass... 00176 char NoAA::ID = 0; 00177 static RegisterPass<NoAA> 00178 U("no-aa", "No Alias Analysis (always returns 'may' alias)", true, true); 00179 00180 // Declare that we implement the AliasAnalysis interface 00181 static RegisterAnalysisGroup<AliasAnalysis> V(U); 00182 00183 ImmutablePass *llvm::createNoAAPass() { return new NoAA(); } 00184 00185 //===----------------------------------------------------------------------===// 00186 // BasicAA Pass 00187 //===----------------------------------------------------------------------===// 00188 00189 namespace { 00190 /// BasicAliasAnalysis - This is the default alias analysis implementation. 00191 /// Because it doesn't chain to a previous alias analysis (like -no-aa), it 00192 /// derives from the NoAA class. 00193 struct VISIBILITY_HIDDEN BasicAliasAnalysis : public NoAA { 00194 static char ID; // Class identification, replacement for typeinfo 00195 BasicAliasAnalysis() : NoAA(&ID) {} 00196 AliasResult alias(const Value *V1, unsigned V1Size, 00197 const Value *V2, unsigned V2Size); 00198 00199 ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size); 00200 ModRefResult getModRefInfo(CallSite CS1, CallSite CS2); 00201 00202 /// hasNoModRefInfoForCalls - We can provide mod/ref information against 00203 /// non-escaping allocations. 00204 virtual bool hasNoModRefInfoForCalls() const { return false; } 00205 00206 /// pointsToConstantMemory - Chase pointers until we find a (constant 00207 /// global) or not. 00208 bool pointsToConstantMemory(const Value *P); 00209 00210 private: 00211 // CheckGEPInstructions - Check two GEP instructions with known 00212 // must-aliasing base pointers. This checks to see if the index expressions 00213 // preclude the pointers from aliasing... 00214 AliasResult 00215 CheckGEPInstructions(const Type* BasePtr1Ty, 00216 Value **GEP1Ops, unsigned NumGEP1Ops, unsigned G1Size, 00217 const Type *BasePtr2Ty, 00218 Value **GEP2Ops, unsigned NumGEP2Ops, unsigned G2Size); 00219 }; 00220 } // End of anonymous namespace 00221 00222 // Register this pass... 00223 char BasicAliasAnalysis::ID = 0; 00224 static RegisterPass<BasicAliasAnalysis> 00225 X("basicaa", "Basic Alias Analysis (default AA impl)", false, true); 00226 00227 // Declare that we implement the AliasAnalysis interface 00228 static RegisterAnalysisGroup<AliasAnalysis, true> Y(X); 00229 00230 ImmutablePass *llvm::createBasicAliasAnalysisPass() { 00231 return new BasicAliasAnalysis(); 00232 } 00233 00234 00235 /// pointsToConstantMemory - Chase pointers until we find a (constant 00236 /// global) or not. 00237 bool BasicAliasAnalysis::pointsToConstantMemory(const Value *P) { 00238 if (const GlobalVariable *GV = 00239 dyn_cast<GlobalVariable>(P->getUnderlyingObject())) 00240 return GV->isConstant(); 00241 return false; 00242 } 00243 00244 00245 // getModRefInfo - Check to see if the specified callsite can clobber the 00246 // specified memory object. Since we only look at local properties of this 00247 // function, we really can't say much about this query. We do, however, use 00248 // simple "address taken" analysis on local objects. 00249 // 00250 AliasAnalysis::ModRefResult 00251 BasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) { 00252 if (!isa<Constant>(P)) { 00253 const Value *Object = P->getUnderlyingObject(); 00254 00255 // If this is a tail call and P points to a stack location, we know that 00256 // the tail call cannot access or modify the local stack. 00257 // We cannot exclude byval arguments here; these belong to the caller of 00258 // the current function not to the current function, and a tail callee 00259 // may reference them. 00260 if (isa<AllocaInst>(Object)) 00261 if (CallInst *CI = dyn_cast<CallInst>(CS.getInstruction())) 00262 if (CI->isTailCall()) 00263 return NoModRef; 00264 00265 // If the pointer is to a locally allocated object that does not escape, 00266 // then the call can not mod/ref the pointer unless the call takes the 00267 // argument without capturing it. 00268 if (isNonEscapingLocalObject(Object) && CS.getInstruction() != Object) { 00269 bool passedAsArg = false; 00270 // TODO: Eventually only check 'nocapture' arguments. 00271 for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 00272 CI != CE; ++CI) 00273 if (isa<PointerType>((*CI)->getType()) && 00274 alias(cast<Value>(CI), ~0U, P, ~0U) != NoAlias) 00275 passedAsArg = true; 00276 00277 if (!passedAsArg) 00278 return NoModRef; 00279 } 00280 } 00281 00282 // The AliasAnalysis base class has some smarts, lets use them. 00283 return AliasAnalysis::getModRefInfo(CS, P, Size); 00284 } 00285 00286 00287 AliasAnalysis::ModRefResult 00288 BasicAliasAnalysis::getModRefInfo(CallSite CS1, CallSite CS2) { 00289 // If CS1 or CS2 are readnone, they don't interact. 00290 ModRefBehavior CS1B = AliasAnalysis::getModRefBehavior(CS1); 00291 if (CS1B == DoesNotAccessMemory) return NoModRef; 00292 00293 ModRefBehavior CS2B = AliasAnalysis::getModRefBehavior(CS2); 00294 if (CS2B == DoesNotAccessMemory) return NoModRef; 00295 00296 // If they both only read from memory, just return ref. 00297 if (CS1B == OnlyReadsMemory && CS2B == OnlyReadsMemory) 00298 return Ref; 00299 00300 // Otherwise, fall back to NoAA (mod+ref). 00301 return NoAA::getModRefInfo(CS1, CS2); 00302 } 00303 00304 00305 // alias - Provide a bunch of ad-hoc rules to disambiguate in common cases, such 00306 // as array references. 00307 // 00308 AliasAnalysis::AliasResult 00309 BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size, 00310 const Value *V2, unsigned V2Size) { 00311 // Strip off any constant expression casts if they exist 00312 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V1)) 00313 if (CE->isCast() && isa<PointerType>(CE->getOperand(0)->getType())) 00314 V1 = CE->getOperand(0); 00315 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V2)) 00316 if (CE->isCast() && isa<PointerType>(CE->getOperand(0)->getType())) 00317 V2 = CE->getOperand(0); 00318 00319 // Are we checking for alias of the same value? 00320 if (V1 == V2) return MustAlias; 00321 00322 if (!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType())) 00323 return NoAlias; // Scalars cannot alias each other 00324 00325 // Strip off cast instructions. Since V1 and V2 are pointers, they must be 00326 // pointer<->pointer bitcasts. 00327 if (const BitCastInst *I = dyn_cast<BitCastInst>(V1)) 00328 return alias(I->getOperand(0), V1Size, V2, V2Size); 00329 if (const BitCastInst *I = dyn_cast<BitCastInst>(V2)) 00330 return alias(V1, V1Size, I->getOperand(0), V2Size); 00331 00332 // Figure out what objects these things are pointing to if we can. 00333 const Value *O1 = V1->getUnderlyingObject(); 00334 const Value *O2 = V2->getUnderlyingObject(); 00335 00336 if (O1 != O2) { 00337 // If V1/V2 point to two different objects we know that we have no alias. 00338 if (isIdentifiedObject(O1) && isIdentifiedObject(O2)) 00339 return NoAlias; 00340 00341 // Arguments can't alias with local allocations or noalias calls. 00342 if ((isa<Argument>(O1) && (isa<AllocationInst>(O2) || isNoAliasCall(O2))) || 00343 (isa<Argument>(O2) && (isa<AllocationInst>(O1) || isNoAliasCall(O1)))) 00344 return NoAlias; 00345 00346 // Most objects can't alias null. 00347 if ((isa<ConstantPointerNull>(V2) && isKnownNonNull(O1)) || 00348 (isa<ConstantPointerNull>(V1) && isKnownNonNull(O2))) 00349 return NoAlias; 00350 } 00351 00352 // If the size of one access is larger than the entire object on the other 00353 // side, then we know such behavior is undefined and can assume no alias. 00354 if (TD) 00355 if ((V1Size != ~0U && isObjectSmallerThan(O2, V1Size, *TD)) || 00356 (V2Size != ~0U && isObjectSmallerThan(O1, V2Size, *TD))) 00357 return NoAlias; 00358 00359 // If one pointer is the result of a call/invoke and the other is a 00360 // non-escaping local object, then we know the object couldn't escape to a 00361 // point where the call could return it. 00362 if ((isa<CallInst>(O1) || isa<InvokeInst>(O1)) && 00363 isNonEscapingLocalObject(O2) && O1 != O2) 00364 return NoAlias; 00365 if ((isa<CallInst>(O2) || isa<InvokeInst>(O2)) && 00366 isNonEscapingLocalObject(O1) && O1 != O2) 00367 return NoAlias; 00368 00369 // If we have two gep instructions with must-alias'ing base pointers, figure 00370 // out if the indexes to the GEP tell us anything about the derived pointer. 00371 // Note that we also handle chains of getelementptr instructions as well as 00372 // constant expression getelementptrs here. 00373 // 00374 if (isGEP(V1) && isGEP(V2)) { 00375 const User *GEP1 = cast<User>(V1); 00376 const User *GEP2 = cast<User>(V2); 00377 00378 // If V1 and V2 are identical GEPs, just recurse down on both of them. 00379 // This allows us to analyze things like: 00380 // P = gep A, 0, i, 1 00381 // Q = gep B, 0, i, 1 00382 // by just analyzing A and B. This is even safe for variable indices. 00383 if (GEP1->getType() == GEP2->getType() && 00384 GEP1->getNumOperands() == GEP2->getNumOperands() && 00385 GEP1->getOperand(0)->getType() == GEP2->getOperand(0)->getType() && 00386 // All operands are the same, ignoring the base. 00387 std::equal(GEP1->op_begin()+1, GEP1->op_end(), GEP2->op_begin()+1)) 00388 return alias(GEP1->getOperand(0), V1Size, GEP2->getOperand(0), V2Size); 00389 00390 00391 // Drill down into the first non-gep value, to test for must-aliasing of 00392 // the base pointers. 00393 while (isGEP(GEP1->getOperand(0)) && 00394 GEP1->getOperand(1) == 00395 Constant::getNullValue(GEP1->getOperand(1)->getType())) 00396 GEP1 = cast<User>(GEP1->getOperand(0)); 00397 const Value *BasePtr1 = GEP1->getOperand(0); 00398 00399 while (isGEP(GEP2->getOperand(0)) && 00400 GEP2->getOperand(1) == 00401 Constant::getNullValue(GEP2->getOperand(1)->getType())) 00402 GEP2 = cast<User>(GEP2->getOperand(0)); 00403 const Value *BasePtr2 = GEP2->getOperand(0); 00404 00405 // Do the base pointers alias? 00406 AliasResult BaseAlias = alias(BasePtr1, ~0U, BasePtr2, ~0U); 00407 if (BaseAlias == NoAlias) return NoAlias; 00408 if (BaseAlias == MustAlias) { 00409 // If the base pointers alias each other exactly, check to see if we can 00410 // figure out anything about the resultant pointers, to try to prove 00411 // non-aliasing. 00412 00413 // Collect all of the chained GEP operands together into one simple place 00414 SmallVector<Value*, 16> GEP1Ops, GEP2Ops; 00415 BasePtr1 = GetGEPOperands(V1, GEP1Ops); 00416 BasePtr2 = GetGEPOperands(V2, GEP2Ops); 00417 00418 // If GetGEPOperands were able to fold to the same must-aliased pointer, 00419 // do the comparison. 00420 if (BasePtr1 == BasePtr2) { 00421 AliasResult GAlias = 00422 CheckGEPInstructions(BasePtr1->getType(), 00423 &GEP1Ops[0], GEP1Ops.size(), V1Size, 00424 BasePtr2->getType(), 00425 &GEP2Ops[0], GEP2Ops.size(), V2Size); 00426 if (GAlias != MayAlias) 00427 return GAlias; 00428 } 00429 } 00430 } 00431 00432 // Check to see if these two pointers are related by a getelementptr 00433 // instruction. If one pointer is a GEP with a non-zero index of the other 00434 // pointer, we know they cannot alias. 00435 // 00436 if (isGEP(V2)) { 00437 std::swap(V1, V2); 00438 std::swap(V1Size, V2Size); 00439 } 00440 00441 if (V1Size != ~0U && V2Size != ~0U) 00442 if (isGEP(V1)) { 00443 SmallVector<Value*, 16> GEPOperands; 00444 const Value *BasePtr = GetGEPOperands(V1, GEPOperands); 00445 00446 AliasResult R = alias(BasePtr, V1Size, V2, V2Size); 00447 if (R == MustAlias) { 00448 // If there is at least one non-zero constant index, we know they cannot 00449 // alias. 00450 bool ConstantFound = false; 00451 bool AllZerosFound = true; 00452 for (unsigned i = 0, e = GEPOperands.size(); i != e; ++i) 00453 if (const Constant *C = dyn_cast<Constant>(GEPOperands[i])) { 00454 if (!C->isNullValue()) { 00455 ConstantFound = true; 00456 AllZerosFound = false; 00457 break; 00458 } 00459 } else { 00460 AllZerosFound = false; 00461 } 00462 00463 // If we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 must aliases 00464 // the ptr, the end result is a must alias also. 00465 if (AllZerosFound) 00466 return MustAlias; 00467 00468 if (ConstantFound) { 00469 if (V2Size <= 1 && V1Size <= 1) // Just pointer check? 00470 return NoAlias; 00471 00472 // Otherwise we have to check to see that the distance is more than 00473 // the size of the argument... build an index vector that is equal to 00474 // the arguments provided, except substitute 0's for any variable 00475 // indexes we find... 00476 if (TD && cast<PointerType>( 00477 BasePtr->getType())->getElementType()->isSized()) { 00478 for (unsigned i = 0; i != GEPOperands.size(); ++i) 00479 if (!isa<ConstantInt>(GEPOperands[i])) 00480 GEPOperands[i] = 00481 Constant::getNullValue(GEPOperands[i]->getType()); 00482 int64_t Offset = 00483 TD->getIndexedOffset(BasePtr->getType(), 00484 &GEPOperands[0], 00485 GEPOperands.size()); 00486 00487 if (Offset >= (int64_t)V2Size || Offset <= -(int64_t)V1Size) 00488 return NoAlias; 00489 } 00490 } 00491 } 00492 } 00493 00494 return MayAlias; 00495 } 00496 00497 // This function is used to determine if the indices of two GEP instructions are 00498 // equal. V1 and V2 are the indices. 00499 static bool IndexOperandsEqual(Value *V1, Value *V2, LLVMContext &Context) { 00500 if (V1->getType() == V2->getType()) 00501 return V1 == V2; 00502 if (Constant *C1 = dyn_cast<Constant>(V1)) 00503 if (Constant *C2 = dyn_cast<Constant>(V2)) { 00504 // Sign extend the constants to long types, if necessary 00505 if (C1->getType() != Type::getInt64Ty(Context)) 00506 C1 = ConstantExpr::getSExt(C1, Type::getInt64Ty(Context)); 00507 if (C2->getType() != Type::getInt64Ty(Context)) 00508 C2 = ConstantExpr::getSExt(C2, Type::getInt64Ty(Context)); 00509 return C1 == C2; 00510 } 00511 return false; 00512 } 00513 00514 /// CheckGEPInstructions - Check two GEP instructions with known must-aliasing 00515 /// base pointers. This checks to see if the index expressions preclude the 00516 /// pointers from aliasing... 00517 AliasAnalysis::AliasResult 00518 BasicAliasAnalysis::CheckGEPInstructions( 00519 const Type* BasePtr1Ty, Value **GEP1Ops, unsigned NumGEP1Ops, unsigned G1S, 00520 const Type *BasePtr2Ty, Value **GEP2Ops, unsigned NumGEP2Ops, unsigned G2S) { 00521 // We currently can't handle the case when the base pointers have different 00522 // primitive types. Since this is uncommon anyway, we are happy being 00523 // extremely conservative. 00524 if (BasePtr1Ty != BasePtr2Ty) 00525 return MayAlias; 00526 00527 const PointerType *GEPPointerTy = cast<PointerType>(BasePtr1Ty); 00528 00529 LLVMContext &Context = GEPPointerTy->getContext(); 00530 00531 // Find the (possibly empty) initial sequence of equal values... which are not 00532 // necessarily constants. 00533 unsigned NumGEP1Operands = NumGEP1Ops, NumGEP2Operands = NumGEP2Ops; 00534 unsigned MinOperands = std::min(NumGEP1Operands, NumGEP2Operands); 00535 unsigned MaxOperands = std::max(NumGEP1Operands, NumGEP2Operands); 00536 unsigned UnequalOper = 0; 00537 while (UnequalOper != MinOperands && 00538 IndexOperandsEqual(GEP1Ops[UnequalOper], GEP2Ops[UnequalOper], 00539 Context)) { 00540 // Advance through the type as we go... 00541 ++UnequalOper; 00542 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty)) 00543 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[UnequalOper-1]); 00544 else { 00545 // If all operands equal each other, then the derived pointers must 00546 // alias each other... 00547 BasePtr1Ty = 0; 00548 assert(UnequalOper == NumGEP1Operands && UnequalOper == NumGEP2Operands && 00549 "Ran out of type nesting, but not out of operands?"); 00550 return MustAlias; 00551 } 00552 } 00553 00554 // If we have seen all constant operands, and run out of indexes on one of the 00555 // getelementptrs, check to see if the tail of the leftover one is all zeros. 00556 // If so, return mustalias. 00557 if (UnequalOper == MinOperands) { 00558 if (NumGEP1Ops < NumGEP2Ops) { 00559 std::swap(GEP1Ops, GEP2Ops); 00560 std::swap(NumGEP1Ops, NumGEP2Ops); 00561 } 00562 00563 bool AllAreZeros = true; 00564 for (unsigned i = UnequalOper; i != MaxOperands; ++i) 00565 if (!isa<Constant>(GEP1Ops[i]) || 00566 !cast<Constant>(GEP1Ops[i])->isNullValue()) { 00567 AllAreZeros = false; 00568 break; 00569 } 00570 if (AllAreZeros) return MustAlias; 00571 } 00572 00573 00574 // So now we know that the indexes derived from the base pointers, 00575 // which are known to alias, are different. We can still determine a 00576 // no-alias result if there are differing constant pairs in the index 00577 // chain. For example: 00578 // A[i][0] != A[j][1] iff (&A[0][1]-&A[0][0] >= std::max(G1S, G2S)) 00579 // 00580 // We have to be careful here about array accesses. In particular, consider: 00581 // A[1][0] vs A[0][i] 00582 // In this case, we don't *know* that the array will be accessed in bounds: 00583 // the index could even be negative. Because of this, we have to 00584 // conservatively *give up* and return may alias. We disregard differing 00585 // array subscripts that are followed by a variable index without going 00586 // through a struct. 00587 // 00588 unsigned SizeMax = std::max(G1S, G2S); 00589 if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work. 00590 00591 // Scan for the first operand that is constant and unequal in the 00592 // two getelementptrs... 00593 unsigned FirstConstantOper = UnequalOper; 00594 for (; FirstConstantOper != MinOperands; ++FirstConstantOper) { 00595 const Value *G1Oper = GEP1Ops[FirstConstantOper]; 00596 const Value *G2Oper = GEP2Ops[FirstConstantOper]; 00597 00598 if (G1Oper != G2Oper) // Found non-equal constant indexes... 00599 if (Constant *G1OC = dyn_cast<ConstantInt>(const_cast<Value*>(G1Oper))) 00600 if (Constant *G2OC = dyn_cast<ConstantInt>(const_cast<Value*>(G2Oper))){ 00601 if (G1OC->getType() != G2OC->getType()) { 00602 // Sign extend both operands to long. 00603 if (G1OC->getType() != Type::getInt64Ty(Context)) 00604 G1OC = ConstantExpr::getSExt(G1OC, Type::getInt64Ty(Context)); 00605 if (G2OC->getType() != Type::getInt64Ty(Context)) 00606 G2OC = ConstantExpr::getSExt(G2OC, Type::getInt64Ty(Context)); 00607 GEP1Ops[FirstConstantOper] = G1OC; 00608 GEP2Ops[FirstConstantOper] = G2OC; 00609 } 00610 00611 if (G1OC != G2OC) { 00612 // Handle the "be careful" case above: if this is an array/vector 00613 // subscript, scan for a subsequent variable array index. 00614 if (const SequentialType *STy = 00615 dyn_cast<SequentialType>(BasePtr1Ty)) { 00616 const Type *NextTy = STy; 00617 bool isBadCase = false; 00618 00619 for (unsigned Idx = FirstConstantOper; 00620 Idx != MinOperands && isa<SequentialType>(NextTy); ++Idx) { 00621 const Value *V1 = GEP1Ops[Idx], *V2 = GEP2Ops[Idx]; 00622 if (!isa<Constant>(V1) || !isa<Constant>(V2)) { 00623 isBadCase = true; 00624 break; 00625 } 00626 // If the array is indexed beyond the bounds of the static type 00627 // at this level, it will also fall into the "be careful" case. 00628 // It would theoretically be possible to analyze these cases, 00629 // but for now just be conservatively correct. 00630 if (const ArrayType *ATy = dyn_cast<ArrayType>(STy)) 00631 if (cast<ConstantInt>(G1OC)->getZExtValue() >= 00632 ATy->getNumElements() || 00633 cast<ConstantInt>(G2OC)->getZExtValue() >= 00634 ATy->getNumElements()) { 00635 isBadCase = true; 00636 break; 00637 } 00638 if (const VectorType *VTy = dyn_cast<VectorType>(STy)) 00639 if (cast<ConstantInt>(G1OC)->getZExtValue() >= 00640 VTy->getNumElements() || 00641 cast<ConstantInt>(G2OC)->getZExtValue() >= 00642 VTy->getNumElements()) { 00643 isBadCase = true; 00644 break; 00645 } 00646 STy = cast<SequentialType>(NextTy); 00647 NextTy = cast<SequentialType>(NextTy)->getElementType(); 00648 } 00649 00650 if (isBadCase) G1OC = 0; 00651 } 00652 00653 // Make sure they are comparable (ie, not constant expressions), and 00654 // make sure the GEP with the smaller leading constant is GEP1. 00655 if (G1OC) { 00656 Constant *Compare = ConstantExpr::getICmp(ICmpInst::ICMP_SGT, 00657 G1OC, G2OC); 00658 if (ConstantInt *CV = dyn_cast<ConstantInt>(Compare)) { 00659 if (CV->getZExtValue()) { // If they are comparable and G2 > G1 00660 std::swap(GEP1Ops, GEP2Ops); // Make GEP1 < GEP2 00661 std::swap(NumGEP1Ops, NumGEP2Ops); 00662 } 00663 break; 00664 } 00665 } 00666 } 00667 } 00668 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(G1Oper); 00669 } 00670 00671 // No shared constant operands, and we ran out of common operands. At this 00672 // point, the GEP instructions have run through all of their operands, and we 00673 // haven't found evidence that there are any deltas between the GEP's. 00674 // However, one GEP may have more operands than the other. If this is the 00675 // case, there may still be hope. Check this now. 00676 if (FirstConstantOper == MinOperands) { 00677 // Without TargetData, we won't know what the offsets are. 00678 if (!TD) 00679 return MayAlias; 00680 00681 // Make GEP1Ops be the longer one if there is a longer one. 00682 if (NumGEP1Ops < NumGEP2Ops) { 00683 std::swap(GEP1Ops, GEP2Ops); 00684 std::swap(NumGEP1Ops, NumGEP2Ops); 00685 } 00686 00687 // Is there anything to check? 00688 if (NumGEP1Ops > MinOperands) { 00689 for (unsigned i = FirstConstantOper; i != MaxOperands; ++i) 00690 if (isa<ConstantInt>(GEP1Ops[i]) && 00691 !cast<ConstantInt>(GEP1Ops[i])->isZero()) { 00692 // Yup, there's a constant in the tail. Set all variables to 00693 // constants in the GEP instruction to make it suitable for 00694 // TargetData::getIndexedOffset. 00695 for (i = 0; i != MaxOperands; ++i) 00696 if (!isa<ConstantInt>(GEP1Ops[i])) 00697 GEP1Ops[i] = Constant::getNullValue(GEP1Ops[i]->getType()); 00698 // Okay, now get the offset. This is the relative offset for the full 00699 // instruction. 00700 int64_t Offset1 = TD->getIndexedOffset(GEPPointerTy, GEP1Ops, 00701 NumGEP1Ops); 00702 00703 // Now check without any constants at the end. 00704 int64_t Offset2 = TD->getIndexedOffset(GEPPointerTy, GEP1Ops, 00705 MinOperands); 00706 00707 // Make sure we compare the absolute difference. 00708 if (Offset1 > Offset2) 00709 std::swap(Offset1, Offset2); 00710 00711 // If the tail provided a bit enough offset, return noalias! 00712 if ((uint64_t)(Offset2-Offset1) >= SizeMax) 00713 return NoAlias; 00714 // Otherwise break - we don't look for another constant in the tail. 00715 break; 00716 } 00717 } 00718 00719 // Couldn't find anything useful. 00720 return MayAlias; 00721 } 00722 00723 // If there are non-equal constants arguments, then we can figure 00724 // out a minimum known delta between the two index expressions... at 00725 // this point we know that the first constant index of GEP1 is less 00726 // than the first constant index of GEP2. 00727 00728 // Advance BasePtr[12]Ty over this first differing constant operand. 00729 BasePtr2Ty = cast<CompositeType>(BasePtr1Ty)-> 00730 getTypeAtIndex(GEP2Ops[FirstConstantOper]); 00731 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)-> 00732 getTypeAtIndex(GEP1Ops[FirstConstantOper]); 00733 00734 // We are going to be using TargetData::getIndexedOffset to determine the 00735 // offset that each of the GEP's is reaching. To do this, we have to convert 00736 // all variable references to constant references. To do this, we convert the 00737 // initial sequence of array subscripts into constant zeros to start with. 00738 const Type *ZeroIdxTy = GEPPointerTy; 00739 for (unsigned i = 0; i != FirstConstantOper; ++i) { 00740 if (!isa<StructType>(ZeroIdxTy)) 00741 GEP1Ops[i] = GEP2Ops[i] = 00742 Constant::getNullValue(Type::getInt32Ty(Context)); 00743 00744 if (const CompositeType *CT = dyn_cast<CompositeType>(ZeroIdxTy)) 00745 ZeroIdxTy = CT->getTypeAtIndex(GEP1Ops[i]); 00746 } 00747 00748 // We know that GEP1Ops[FirstConstantOper] & GEP2Ops[FirstConstantOper] are ok 00749 00750 // Loop over the rest of the operands... 00751 for (unsigned i = FirstConstantOper+1; i != MaxOperands; ++i) { 00752 const Value *Op1 = i < NumGEP1Ops ? GEP1Ops[i] : 0; 00753 const Value *Op2 = i < NumGEP2Ops ? GEP2Ops[i] : 0; 00754 // If they are equal, use a zero index... 00755 if (Op1 == Op2 && BasePtr1Ty == BasePtr2Ty) { 00756 if (!isa<ConstantInt>(Op1)) 00757 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Op1->getType()); 00758 // Otherwise, just keep the constants we have. 00759 } else { 00760 if (Op1) { 00761 if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) { 00762 // If this is an array index, make sure the array element is in range. 00763 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) { 00764 if (Op1C->getZExtValue() >= AT->getNumElements()) 00765 return MayAlias; // Be conservative with out-of-range accesses 00766 } else if (const VectorType *VT = dyn_cast<VectorType>(BasePtr1Ty)) { 00767 if (Op1C->getZExtValue() >= VT->getNumElements()) 00768 return MayAlias; // Be conservative with out-of-range accesses 00769 } 00770 00771 } else { 00772 // GEP1 is known to produce a value less than GEP2. To be 00773 // conservatively correct, we must assume the largest possible 00774 // constant is used in this position. This cannot be the initial 00775 // index to the GEP instructions (because we know we have at least one 00776 // element before this one with the different constant arguments), so 00777 // we know that the current index must be into either a struct or 00778 // array. Because we know it's not constant, this cannot be a 00779 // structure index. Because of this, we can calculate the maximum 00780 // value possible. 00781 // 00782 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) 00783 GEP1Ops[i] = 00784 ConstantInt::get(Type::getInt64Ty(Context), 00785 AT->getNumElements()-1); 00786 else if (const VectorType *VT = dyn_cast<VectorType>(BasePtr1Ty)) 00787 GEP1Ops[i] = 00788 ConstantInt::get(Type::getInt64Ty(Context), 00789 VT->getNumElements()-1); 00790 } 00791 } 00792 00793 if (Op2) { 00794 if (const ConstantInt *Op2C = dyn_cast<ConstantInt>(Op2)) { 00795 // If this is an array index, make sure the array element is in range. 00796 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr2Ty)) { 00797 if (Op2C->getZExtValue() >= AT->getNumElements()) 00798 return MayAlias; // Be conservative with out-of-range accesses 00799 } else if (const VectorType *VT = dyn_cast<VectorType>(BasePtr2Ty)) { 00800 if (Op2C->getZExtValue() >= VT->getNumElements()) 00801 return MayAlias; // Be conservative with out-of-range accesses 00802 } 00803 } else { // Conservatively assume the minimum value for this index 00804 GEP2Ops[i] = Constant::getNullValue(Op2->getType()); 00805 } 00806 } 00807 } 00808 00809 if (BasePtr1Ty && Op1) { 00810 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty)) 00811 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[i]); 00812 else 00813 BasePtr1Ty = 0; 00814 } 00815 00816 if (BasePtr2Ty && Op2) { 00817 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr2Ty)) 00818 BasePtr2Ty = CT->getTypeAtIndex(GEP2Ops[i]); 00819 else 00820 BasePtr2Ty = 0; 00821 } 00822 } 00823 00824 if (TD && GEPPointerTy->getElementType()->isSized()) { 00825 int64_t Offset1 = 00826 TD->getIndexedOffset(GEPPointerTy, GEP1Ops, NumGEP1Ops); 00827 int64_t Offset2 = 00828 TD->getIndexedOffset(GEPPointerTy, GEP2Ops, NumGEP2Ops); 00829 assert(Offset1 != Offset2 && 00830 "There is at least one different constant here!"); 00831 00832 // Make sure we compare the absolute difference. 00833 if (Offset1 > Offset2) 00834 std::swap(Offset1, Offset2); 00835 00836 if ((uint64_t)(Offset2-Offset1) >= SizeMax) { 00837 //cerr << "Determined that these two GEP's don't alias [" 00838 // << SizeMax << " bytes]: \n" << *GEP1 << *GEP2; 00839 return NoAlias; 00840 } 00841 } 00842 return MayAlias; 00843 } 00844 00845 // Make sure that anything that uses AliasAnalysis pulls in this file... 00846 DEFINING_FILE_FOR(BasicAliasAnalysis)