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