LLVM API Documentation

BasicAliasAnalysis.cpp

Go to the documentation of this file.
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)