LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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