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 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 }