lib/Analysis/BasicAliasAnalysis.cpp

   1 //===- BasicAliasAnalysis.cpp - Local Alias Analysis Impl -----------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines the default implementation of the Alias Analysis interface
  11 // that simply implements a few identities (two different globals cannot alias,
  12 // etc), but otherwise does no analysis.
  13 //
  14 // FIXME: This could be extended for a very simple form of mod/ref information.
  15 // If a pointer is locally allocated (either malloc or alloca) and never passed
  16 // into a call or stored to memory, then we know that calls will not mod/ref the
  17 // memory.  This can be important for tailcallelim, and can support CSE of loads
  18 // and dead store elimination across calls.  This is particularly important for
  19 // stack allocated arrays.
  20 //
  21 //===----------------------------------------------------------------------===//
  22
  23 #include "llvm/Analysis/AliasAnalysis.h"
  24 #include "llvm/Constants.h"
  25 #include "llvm/DerivedTypes.h"
  26 #include "llvm/Function.h"
  27 #include "llvm/GlobalVariable.h"
  28 #include "llvm/iOther.h"
  29 #include "llvm/iMemory.h"
  30 #include "llvm/Pass.h"
  31 #include "llvm/Target/TargetData.h"
  32 #include "llvm/Support/GetElementPtrTypeIterator.h"
  33 using namespace llvm;
  34
  35 // Make sure that anything that uses AliasAnalysis pulls in this file...
  36 void llvm::BasicAAStub() {}
  37
  38 namespace {
  39   struct BasicAliasAnalysis : public ImmutablePass, public AliasAnalysis {
  40
  41     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  42       AliasAnalysis::getAnalysisUsage(AU);
  43     }
  44
  45     virtual void initializePass();
  46
  47     AliasResult alias(const Value *V1, unsigned V1Size,
  48                       const Value *V2, unsigned V2Size);
  49
  50     ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size);
  51
  52     /// pointsToConstantMemory - Chase pointers until we find a (constant
  53     /// global) or not.
  54     bool pointsToConstantMemory(const Value *P);
  55
  56     virtual bool doesNotAccessMemory(Function *F);
  57     virtual bool onlyReadsMemory(Function *F);
  58
  59   private:
  60     // CheckGEPInstructions - Check two GEP instructions with known
  61     // must-aliasing base pointers.  This checks to see if the index expressions
  62     // preclude the pointers from aliasing...
  63     AliasResult
  64     CheckGEPInstructions(const Type* BasePtr1Ty, std::vector<Value*> &GEP1Ops,
  65                          unsigned G1Size,
  66                          const Type *BasePtr2Ty, std::vector<Value*> &GEP2Ops,
  67                          unsigned G2Size);
  68   };
  69
  70   // Register this pass...
  71   RegisterOpt<BasicAliasAnalysis>
  72   X("basicaa", "Basic Alias Analysis (default AA impl)");
  73
  74   // Declare that we implement the AliasAnalysis interface
  75   RegisterAnalysisGroup<AliasAnalysis, BasicAliasAnalysis, true> Y;
  76 }  // End of anonymous namespace
  77
  78 void BasicAliasAnalysis::initializePass() {
  79   InitializeAliasAnalysis(this);
  80 }
  81
  82 // hasUniqueAddress - Return true if the specified value points to something
  83 // with a unique, discernable, address.
  84 static inline bool hasUniqueAddress(const Value *V) {
  85   return isa<GlobalValue>(V) || isa<AllocationInst>(V);
  86 }
  87
  88 // getUnderlyingObject - This traverses the use chain to figure out what object
  89 // the specified value points to.  If the value points to, or is derived from, a
  90 // unique object or an argument, return it.
  91 static const Value *getUnderlyingObject(const Value *V) {
  92   if (!isa<PointerType>(V->getType())) return 0;
  93
  94   // If we are at some type of object... return it.
  95   if (hasUniqueAddress(V) || isa<Argument>(V)) return V;
  96
  97   // Traverse through different addressing mechanisms...
  98   if (const Instruction *I = dyn_cast<Instruction>(V)) {
  99     if (isa<CastInst>(I) || isa<GetElementPtrInst>(I))
 100       return getUnderlyingObject(I->getOperand(0));
 101   } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
 102     if (CE->getOpcode() == Instruction::Cast ||
 103         CE->getOpcode() == Instruction::GetElementPtr)
 104       return getUnderlyingObject(CE->getOperand(0));
 105   } else if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V)) {
 106     return CPR->getValue();
 107   }
 108   return 0;
 109 }
 110
 111 static const User *isGEP(const Value *V) {
 112   if (isa<GetElementPtrInst>(V) ||
 113       (isa<ConstantExpr>(V) &&
 114        cast<ConstantExpr>(V)->getOpcode() == Instruction::GetElementPtr))
 115     return cast<User>(V);
 116   return 0;
 117 }
 118
 119 static const Value *GetGEPOperands(const Value *V, std::vector<Value*> &GEPOps){
 120   assert(GEPOps.empty() && "Expect empty list to populate!");
 121   GEPOps.insert(GEPOps.end(), cast<User>(V)->op_begin()+1,
 122                 cast<User>(V)->op_end());
 123
 124   // Accumulate all of the chained indexes into the operand array
 125   V = cast<User>(V)->getOperand(0);
 126
 127   while (const User *G = isGEP(V)) {
 128     if (!isa<Constant>(GEPOps[0]) ||
 129         !cast<Constant>(GEPOps[0])->isNullValue())
 130       break;  // Don't handle folding arbitrary pointer offsets yet...
 131     GEPOps.erase(GEPOps.begin());   // Drop the zero index
 132     GEPOps.insert(GEPOps.begin(), G->op_begin()+1, G->op_end());
 133     V = G->getOperand(0);
 134   }
 135   return V;
 136 }
 137
 138 /// pointsToConstantMemory - Chase pointers until we find a (constant
 139 /// global) or not.
 140 bool BasicAliasAnalysis::pointsToConstantMemory(const Value *P) {
 141   if (const Value *V = getUnderlyingObject(P))
 142     if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
 143       return GV->isConstant();
 144   return false;
 145 }
 146
 147 static bool AddressMightEscape(const Value *V) {
 148   for (Value::use_const_iterator UI = V->use_begin(), E = V->use_end();
 149        UI != E; ++UI) {
 150     const Instruction *I = cast<Instruction>(*UI);
 151     switch (I->getOpcode()) {
 152     case Instruction::Load: break;
 153     case Instruction::Store:
 154       if (I->getOperand(0) == V)
 155         return true; // Escapes if the pointer is stored.
 156       break;
 157     case Instruction::GetElementPtr:
 158       if (AddressMightEscape(I)) return true;
 159       break;
 160     case Instruction::Cast:
 161       if (!isa<PointerType>(I->getType()))
 162         return true;
 163       if (AddressMightEscape(I)) return true;
 164       break;
 165     default:
 166       return true;
 167     }
 168   }
 169   return false;
 170 }
 171
 172 // getModRefInfo - Check to see if the specified callsite can clobber the
 173 // specified memory object.  Since we only look at local properties of this
 174 // function, we really can't say much about this query.  We do, however, use
 175 // simple "address taken" analysis on local objects.
 176 //
 177 AliasAnalysis::ModRefResult
 178 BasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) {
 179   if (!isa<Constant>(P) && !isa<GlobalValue>(P))
 180     if (const AllocationInst *AI =
 181                   dyn_cast_or_null<AllocationInst>(getUnderlyingObject(P))) {
 182       // Okay, the pointer is to a stack allocated object.  If we can prove that
 183       // the pointer never "escapes", then we know the call cannot clobber it,
 184       // because it simply can't get its address.
 185       if (!AddressMightEscape(AI))
 186         return NoModRef;
 187     }
 188
 189   // The AliasAnalysis base class has some smarts, lets use them.
 190   return AliasAnalysis::getModRefInfo(CS, P, Size);
 191 }
 192
 193 // alias - Provide a bunch of ad-hoc rules to disambiguate in common cases, such
 194 // as array references.  Note that this function is heavily tail recursive.
 195 // Hopefully we have a smart C++ compiler.  :)
 196 //
 197 AliasAnalysis::AliasResult
 198 BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size,
 199                           const Value *V2, unsigned V2Size) {
 200   // Strip off any constant expression casts if they exist
 201   if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V1))
 202     if (CE->getOpcode() == Instruction::Cast)
 203       V1 = CE->getOperand(0);
 204   if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V2))
 205     if (CE->getOpcode() == Instruction::Cast)
 206       V2 = CE->getOperand(0);
 207
 208   // Strip off constant pointer refs if they exist
 209   if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V1))
 210     V1 = CPR->getValue();
 211   if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V2))
 212     V2 = CPR->getValue();
 213
 214   // Are we checking for alias of the same value?
 215   if (V1 == V2) return MustAlias;
 216
 217   if ((!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType())) &&
 218       V1->getType() != Type::LongTy && V2->getType() != Type::LongTy)
 219     return NoAlias;  // Scalars cannot alias each other
 220
 221   // Strip off cast instructions...
 222   if (const Instruction *I = dyn_cast<CastInst>(V1))
 223     return alias(I->getOperand(0), V1Size, V2, V2Size);
 224   if (const Instruction *I = dyn_cast<CastInst>(V2))
 225     return alias(V1, V1Size, I->getOperand(0), V2Size);
 226
 227   // Figure out what objects these things are pointing to if we can...
 228   const Value *O1 = getUnderlyingObject(V1);
 229   const Value *O2 = getUnderlyingObject(V2);
 230
 231   // Pointing at a discernible object?
 232   if (O1 && O2) {
 233     if (isa<Argument>(O1)) {
 234       // Incoming argument cannot alias locally allocated object!
 235       if (isa<AllocationInst>(O2)) return NoAlias;
 236       // Otherwise, nothing is known...
 237     } else if (isa<Argument>(O2)) {
 238       // Incoming argument cannot alias locally allocated object!
 239       if (isa<AllocationInst>(O1)) return NoAlias;
 240       // Otherwise, nothing is known...
 241     } else {
 242       // If they are two different objects, we know that we have no alias...
 243       if (O1 != O2) return NoAlias;
 244     }
 245
 246     // If they are the same object, they we can look at the indexes.  If they
 247     // index off of the object is the same for both pointers, they must alias.
 248     // If they are provably different, they must not alias.  Otherwise, we can't
 249     // tell anything.
 250   } else if (O1 && !isa<Argument>(O1) && isa<ConstantPointerNull>(V2)) {
 251     return NoAlias;                    // Unique values don't alias null
 252   } else if (O2 && !isa<Argument>(O2) && isa<ConstantPointerNull>(V1)) {
 253     return NoAlias;                    // Unique values don't alias null
 254   }
 255
 256   // If we have two gep instructions with must-alias'ing base pointers, figure
 257   // out if the indexes to the GEP tell us anything about the derived pointer.
 258   // Note that we also handle chains of getelementptr instructions as well as
 259   // constant expression getelementptrs here.
 260   //
 261   if (isGEP(V1) && isGEP(V2)) {
 262     // Drill down into the first non-gep value, to test for must-aliasing of
 263     // the base pointers.
 264     const Value *BasePtr1 = V1, *BasePtr2 = V2;
 265     do {
 266       BasePtr1 = cast<User>(BasePtr1)->getOperand(0);
 267     } while (isGEP(BasePtr1) &&
 268              cast<User>(BasePtr1)->getOperand(1) ==
 269        Constant::getNullValue(cast<User>(BasePtr1)->getOperand(1)->getType()));
 270     do {
 271       BasePtr2 = cast<User>(BasePtr2)->getOperand(0);
 272     } while (isGEP(BasePtr2) &&
 273              cast<User>(BasePtr2)->getOperand(1) ==
 274        Constant::getNullValue(cast<User>(BasePtr2)->getOperand(1)->getType()));
 275
 276     // Do the base pointers alias?
 277     AliasResult BaseAlias = alias(BasePtr1, V1Size, BasePtr2, V2Size);
 278     if (BaseAlias == NoAlias) return NoAlias;
 279     if (BaseAlias == MustAlias) {
 280       // If the base pointers alias each other exactly, check to see if we can
 281       // figure out anything about the resultant pointers, to try to prove
 282       // non-aliasing.
 283
 284       // Collect all of the chained GEP operands together into one simple place
 285       std::vector<Value*> GEP1Ops, GEP2Ops;
 286       BasePtr1 = GetGEPOperands(V1, GEP1Ops);
 287       BasePtr2 = GetGEPOperands(V2, GEP2Ops);
 288
 289       AliasResult GAlias =
 290         CheckGEPInstructions(BasePtr1->getType(), GEP1Ops, V1Size,
 291                              BasePtr2->getType(), GEP2Ops, V2Size);
 292       if (GAlias != MayAlias)
 293         return GAlias;
 294     }
 295   }
 296
 297   // Check to see if these two pointers are related by a getelementptr
 298   // instruction.  If one pointer is a GEP with a non-zero index of the other
 299   // pointer, we know they cannot alias.
 300   //
 301   if (isGEP(V2)) {
 302     std::swap(V1, V2);
 303     std::swap(V1Size, V2Size);
 304   }
 305
 306   if (V1Size != ~0U && V2Size != ~0U)
 307     if (const User *GEP = isGEP(V1)) {
 308       std::vector<Value*> GEPOperands;
 309       const Value *BasePtr = GetGEPOperands(V1, GEPOperands);
 310
 311       AliasResult R = alias(BasePtr, V1Size, V2, V2Size);
 312       if (R == MustAlias) {
 313         // If there is at least one non-zero constant index, we know they cannot
 314         // alias.
 315         bool ConstantFound = false;
 316         bool AllZerosFound = true;
 317         for (unsigned i = 0, e = GEPOperands.size(); i != e; ++i)
 318           if (const Constant *C = dyn_cast<Constant>(GEPOperands[i])) {
 319             if (!C->isNullValue()) {
 320               ConstantFound = true;
 321               AllZerosFound = false;
 322               break;
 323             }
 324           } else {
 325             AllZerosFound = false;
 326           }
 327
 328         // If we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 must aliases
 329         // the ptr, the end result is a must alias also.
 330         if (AllZerosFound)
 331           return MustAlias;
 332
 333         if (ConstantFound) {
 334           if (V2Size <= 1 && V1Size <= 1)  // Just pointer check?
 335             return NoAlias;
 336
 337           // Otherwise we have to check to see that the distance is more than
 338           // the size of the argument... build an index vector that is equal to
 339           // the arguments provided, except substitute 0's for any variable
 340           // indexes we find...
 341           for (unsigned i = 0; i != GEPOperands.size(); ++i)
 342             if (!isa<Constant>(GEPOperands[i]) ||
 343                 isa<ConstantExpr>(GEPOperands[i]))
 344               GEPOperands[i] =Constant::getNullValue(GEPOperands[i]->getType());
 345           int64_t Offset = getTargetData().getIndexedOffset(BasePtr->getType(),
 346                                                             GEPOperands);
 347           if (Offset >= (int64_t)V2Size || Offset <= -(int64_t)V1Size)
 348             return NoAlias;
 349         }
 350       }
 351     }
 352
 353   return MayAlias;
 354 }
 355
 356 /// CheckGEPInstructions - Check two GEP instructions with known must-aliasing
 357 /// base pointers.  This checks to see if the index expressions preclude the
 358 /// pointers from aliasing...
 359 AliasAnalysis::AliasResult BasicAliasAnalysis::
 360 CheckGEPInstructions(const Type* BasePtr1Ty, std::vector<Value*> &GEP1Ops,
 361                      unsigned G1S,
 362                      const Type *BasePtr2Ty, std::vector<Value*> &GEP2Ops,
 363                      unsigned G2S) {
 364   // We currently can't handle the case when the base pointers have different
 365   // primitive types.  Since this is uncommon anyway, we are happy being
 366   // extremely conservative.
 367   if (BasePtr1Ty != BasePtr2Ty)
 368     return MayAlias;
 369
 370   const Type *GEPPointerTy = BasePtr1Ty;
 371
 372   // Find the (possibly empty) initial sequence of equal values... which are not
 373   // necessarily constants.
 374   unsigned NumGEP1Operands = GEP1Ops.size(), NumGEP2Operands = GEP2Ops.size();
 375   unsigned MinOperands = std::min(NumGEP1Operands, NumGEP2Operands);
 376   unsigned MaxOperands = std::max(NumGEP1Operands, NumGEP2Operands);
 377   unsigned UnequalOper = 0;
 378   while (UnequalOper != MinOperands &&
 379          GEP1Ops[UnequalOper] == GEP2Ops[UnequalOper]) {
 380     // Advance through the type as we go...
 381     ++UnequalOper;
 382     if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty))
 383       BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[UnequalOper-1]);
 384     else {
 385       // If all operands equal each other, then the derived pointers must
 386       // alias each other...
 387       BasePtr1Ty = 0;
 388       assert(UnequalOper == NumGEP1Operands && UnequalOper == NumGEP2Operands &&
 389              "Ran out of type nesting, but not out of operands?");
 390       return MustAlias;
 391     }
 392   }
 393
 394   // If we have seen all constant operands, and run out of indexes on one of the
 395   // getelementptrs, check to see if the tail of the leftover one is all zeros.
 396   // If so, return mustalias.
 397   if (UnequalOper == MinOperands) {
 398     if (GEP1Ops.size() < GEP2Ops.size()) std::swap(GEP1Ops, GEP2Ops);
 399
 400     bool AllAreZeros = true;
 401     for (unsigned i = UnequalOper; i != MaxOperands; ++i)
 402       if (!isa<Constant>(GEP1Ops[i]) ||
 403           !cast<Constant>(GEP1Ops[i])->isNullValue()) {
 404         AllAreZeros = false;
 405         break;
 406       }
 407     if (AllAreZeros) return MustAlias;
 408   }
 409
 410
 411   // So now we know that the indexes derived from the base pointers,
 412   // which are known to alias, are different.  We can still determine a
 413   // no-alias result if there are differing constant pairs in the index
 414   // chain.  For example:
 415   //        A[i][0] != A[j][1] iff (&A[0][1]-&A[0][0] >= std::max(G1S, G2S))
 416   //
 417   unsigned SizeMax = std::max(G1S, G2S);
 418   if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work...
 419
 420   // Scan for the first operand that is constant and unequal in the
 421   // two getelemenptrs...
 422   unsigned FirstConstantOper = UnequalOper;
 423   for (; FirstConstantOper != MinOperands; ++FirstConstantOper) {
 424     const Value *G1Oper = GEP1Ops[FirstConstantOper];
 425     const Value *G2Oper = GEP2Ops[FirstConstantOper];
 426
 427     if (G1Oper != G2Oper)   // Found non-equal constant indexes...
 428       if (Constant *G1OC = dyn_cast<Constant>(const_cast<Value*>(G1Oper)))
 429         if (Constant *G2OC = dyn_cast<Constant>(const_cast<Value*>(G2Oper))) {
 430           // Make sure they are comparable (ie, not constant expressions)...
 431           // and make sure the GEP with the smaller leading constant is GEP1.
 432           Constant *Compare = ConstantExpr::get(Instruction::SetGT, G1OC, G2OC);
 433           if (ConstantBool *CV = dyn_cast<ConstantBool>(Compare)) {
 434             if (CV->getValue())   // If they are comparable and G2 > G1
 435               std::swap(GEP1Ops, GEP2Ops);  // Make GEP1 < GEP2
 436             break;
 437           }
 438         }
 439     BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(G1Oper);
 440   }
 441
 442   // No shared constant operands, and we ran out of common operands.  At this
 443   // point, the GEP instructions have run through all of their operands, and we
 444   // haven't found evidence that there are any deltas between the GEP's.
 445   // However, one GEP may have more operands than the other.  If this is the
 446   // case, there may still be hope.  This this now.
 447   if (FirstConstantOper == MinOperands) {
 448     // Make GEP1Ops be the longer one if there is a longer one.
 449     if (GEP1Ops.size() < GEP2Ops.size())
 450       std::swap(GEP1Ops, GEP2Ops);
 451
 452     // Is there anything to check?
 453     if (GEP1Ops.size() > MinOperands) {
 454       for (unsigned i = FirstConstantOper; i != MaxOperands; ++i)
 455         if (isa<Constant>(GEP1Ops[i]) && !isa<ConstantExpr>(GEP1Ops[i]) &&
 456             !cast<Constant>(GEP1Ops[i])->isNullValue()) {
 457           // Yup, there's a constant in the tail.  Set all variables to
 458           // constants in the GEP instruction to make it suiteable for
 459           // TargetData::getIndexedOffset.
 460           for (i = 0; i != MaxOperands; ++i)
 461             if (!isa<Constant>(GEP1Ops[i]) || isa<ConstantExpr>(GEP1Ops[i]))
 462               GEP1Ops[i] = Constant::getNullValue(GEP1Ops[i]->getType());
 463           // Okay, now get the offset.  This is the relative offset for the full
 464           // instruction.
 465           const TargetData &TD = getTargetData();
 466           int64_t Offset1 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops);
 467
 468           // Now crop off any constants from the end...
 469           GEP1Ops.resize(MinOperands);
 470           int64_t Offset2 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops);
 471
 472           // If the tail provided a bit enough offset, return noalias!
 473           if ((uint64_t)(Offset2-Offset1) >= SizeMax)
 474             return NoAlias;
 475         }
 476     }
 477
 478     // Couldn't find anything useful.
 479     return MayAlias;
 480   }
 481
 482   // If there are non-equal constants arguments, then we can figure
 483   // out a minimum known delta between the two index expressions... at
 484   // this point we know that the first constant index of GEP1 is less
 485   // than the first constant index of GEP2.
 486
 487   // Advance BasePtr[12]Ty over this first differing constant operand.
 488   BasePtr2Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(GEP2Ops[FirstConstantOper]);
 489   BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(GEP1Ops[FirstConstantOper]);
 490
 491   // We are going to be using TargetData::getIndexedOffset to determine the
 492   // offset that each of the GEP's is reaching.  To do this, we have to convert
 493   // all variable references to constant references.  To do this, we convert the
 494   // initial equal sequence of variables into constant zeros to start with.
 495   for (unsigned i = 0; i != FirstConstantOper; ++i) {
 496     if (!isa<Constant>(GEP1Ops[i]) || isa<ConstantExpr>(GEP1Ops[i]) ||
 497         !isa<Constant>(GEP2Ops[i]) || isa<ConstantExpr>(GEP2Ops[i])) {
 498       GEP1Ops[i] = Constant::getNullValue(GEP1Ops[i]->getType());
 499       GEP2Ops[i] = Constant::getNullValue(GEP2Ops[i]->getType());
 500     }
 501   }
 502
 503   // We know that GEP1Ops[FirstConstantOper] & GEP2Ops[FirstConstantOper] are ok
 504
 505   // Loop over the rest of the operands...
 506   for (unsigned i = FirstConstantOper+1; i != MaxOperands; ++i) {
 507     const Value *Op1 = i < GEP1Ops.size() ? GEP1Ops[i] : 0;
 508     const Value *Op2 = i < GEP2Ops.size() ? GEP2Ops[i] : 0;
 509     // If they are equal, use a zero index...
 510     if (Op1 == Op2 && BasePtr1Ty == BasePtr2Ty) {
 511       if (!isa<Constant>(Op1) || isa<ConstantExpr>(Op1))
 512         GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Op1->getType());
 513       // Otherwise, just keep the constants we have.
 514     } else {
 515       if (Op1) {
 516         if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
 517           // If this is an array index, make sure the array element is in range.
 518           if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
 519             if (Op1C->getRawValue() >= AT->getNumElements())
 520               return MayAlias;  // Be conservative with out-of-range accesses
 521
 522         } else {
 523           // GEP1 is known to produce a value less than GEP2.  To be
 524           // conservatively correct, we must assume the largest possible
 525           // constant is used in this position.  This cannot be the initial
 526           // index to the GEP instructions (because we know we have at least one
 527           // element before this one with the different constant arguments), so
 528           // we know that the current index must be into either a struct or
 529           // array.  Because we know it's not constant, this cannot be a
 530           // structure index.  Because of this, we can calculate the maximum
 531           // value possible.
 532           //
 533           if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
 534             GEP1Ops[i] = ConstantSInt::get(Type::LongTy,AT->getNumElements()-1);
 535         }
 536       }
 537
 538       if (Op2) {
 539         if (const ConstantInt *Op2C = dyn_cast<ConstantInt>(Op2)) {
 540           // If this is an array index, make sure the array element is in range.
 541           if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
 542             if (Op2C->getRawValue() >= AT->getNumElements())
 543               return MayAlias;  // Be conservative with out-of-range accesses
 544         } else {  // Conservatively assume the minimum value for this index
 545           GEP2Ops[i] = Constant::getNullValue(Op2->getType());
 546         }
 547       }
 548     }
 549
 550     if (BasePtr1Ty && Op1) {
 551       if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty))
 552         BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[i]);
 553       else
 554         BasePtr1Ty = 0;
 555     }
 556
 557     if (BasePtr2Ty && Op2) {
 558       if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr2Ty))
 559         BasePtr2Ty = CT->getTypeAtIndex(GEP2Ops[i]);
 560       else
 561         BasePtr2Ty = 0;
 562     }
 563   }
 564
 565   int64_t Offset1 = getTargetData().getIndexedOffset(GEPPointerTy, GEP1Ops);
 566   int64_t Offset2 = getTargetData().getIndexedOffset(GEPPointerTy, GEP2Ops);
 567   assert(Offset1 < Offset2 &&"There is at least one different constant here!");
 568
 569   if ((uint64_t)(Offset2-Offset1) >= SizeMax) {
 570     //std::cerr << "Determined that these two GEP's don't alias ["
 571     //          << SizeMax << " bytes]: \n" << *GEP1 << *GEP2;
 572     return NoAlias;
 573   }
 574   return MayAlias;
 575 }
 576
 577 namespace {
 578   struct StringCompare {
 579     bool operator()(const char *LHS, const char *RHS) {
 580       return strcmp(LHS, RHS) < 0;
 581     }
 582   };
 583 }
 584
 585 // Note that this list cannot contain libm functions (such as acos and sqrt)
 586 // that set errno on a domain or other error.
 587 static const char *DoesntAccessMemoryTable[] = {
 588   "abs", "labs", "llabs", "imaxabs", "fabs", "fabsf", "fabsl",
 589   "trunc", "truncf", "truncl", "ldexp",
 590
 591   "atan", "atanf", "atanl",   "atan2", "atan2f", "atan2l",
 592   "cbrt",
 593   "cos", "cosf", "cosl",      "cosh", "coshf", "coshl",
 594   "exp", "expf", "expl",
 595   "hypot",
 596   "sin", "sinf", "sinl",      "sinh", "sinhf", "sinhl",
 597   "tan", "tanf", "tanl",      "tanh", "tanhf", "tanhl",
 598
 599   // ctype.h
 600   "isalnum", "isalpha", "iscntrl", "isdigit", "isgraph", "islower", "isprint"
 601   "ispunct", "isspace", "isupper", "isxdigit", "tolower", "toupper",
 602
 603   // wctype.h"
 604   "iswalnum", "iswalpha", "iswcntrl", "iswdigit", "iswgraph", "iswlower",
 605   "iswprint", "iswpunct", "iswspace", "iswupper", "iswxdigit",
 606
 607   "iswctype", "towctrans", "towlower", "towupper",
 608
 609   "btowc", "wctob",
 610
 611   "isinf", "isnan", "finite",
 612
 613   // C99 math functions
 614   "copysign", "copysignf", "copysignd",
 615   "nexttoward", "nexttowardf", "nexttowardd",
 616   "nextafter", "nextafterf", "nextafterd",
 617
 618   // glibc functions:
 619   "__fpclassify", "__fpclassifyf", "__fpclassifyl",
 620   "__signbit", "__signbitf", "__signbitl",
 621 };
 622
 623 static const unsigned DAMTableSize =
 624     sizeof(DoesntAccessMemoryTable)/sizeof(DoesntAccessMemoryTable[0]);
 625
 626 /// doesNotAccessMemory - Return true if we know that the function does not
 627 /// access memory at all.  Since basicaa does no analysis, we can only do simple
 628 /// things here.  In particular, if we have an external function with the name
 629 /// of a standard C library function, we are allowed to assume it will be
 630 /// resolved by libc, so we can hardcode some entries in here.
 631 bool BasicAliasAnalysis::doesNotAccessMemory(Function *F) {
 632   if (!F->isExternal()) return false;
 633
 634   static bool Initialized = false;
 635   if (!Initialized) {
 636     // Sort the table the first time through.
 637     std::sort(DoesntAccessMemoryTable, DoesntAccessMemoryTable+DAMTableSize,
 638               StringCompare());
 639     Initialized = true;
 640   }
 641
 642   const char **Ptr = std::lower_bound(DoesntAccessMemoryTable,
 643                                       DoesntAccessMemoryTable+DAMTableSize,
 644                                       F->getName().c_str(), StringCompare());
 645   return Ptr != DoesntAccessMemoryTable+DAMTableSize && *Ptr == F->getName();
 646 }
 647
 648
 649 static const char *OnlyReadsMemoryTable[] = {
 650   "atoi", "atol", "atof", "atoll", "atoq", "a64l",
 651   "bcmp", "memcmp", "memchr", "memrchr", "wmemcmp", "wmemchr",
 652
 653   // Strings
 654   "strcmp", "strcasecmp", "strcoll", "strncmp", "strncasecmp",
 655   "strchr", "strcspn", "strlen", "strpbrk", "strrchr", "strspn", "strstr",
 656   "index", "rindex",
 657
 658   // Wide char strings
 659   "wcschr", "wcscmp", "wcscoll", "wcscspn", "wcslen", "wcsncmp", "wcspbrk",
 660   "wcsrchr", "wcsspn", "wcsstr",
 661
 662   // glibc
 663   "alphasort", "alphasort64", "versionsort", "versionsort64",
 664
 665   // C99
 666   "nan", "nanf", "nand",
 667 };
 668
 669 static const unsigned ORMTableSize =
 670     sizeof(OnlyReadsMemoryTable)/sizeof(OnlyReadsMemoryTable[0]);
 671
 672 bool BasicAliasAnalysis::onlyReadsMemory(Function *F) {
 673   if (doesNotAccessMemory(F)) return true;
 674   if (!F->isExternal()) return false;
 675
 676   static bool Initialized = false;
 677   if (!Initialized) {
 678     // Sort the table the first time through.
 679     std::sort(OnlyReadsMemoryTable, OnlyReadsMemoryTable+ORMTableSize,
 680               StringCompare());
 681     Initialized = true;
 682   }
 683
 684   const char **Ptr = std::lower_bound(OnlyReadsMemoryTable,
 685                                       OnlyReadsMemoryTable+ORMTableSize,
 686                                       F->getName().c_str(), StringCompare());
 687   return Ptr != OnlyReadsMemoryTable+ORMTableSize && *Ptr == F->getName();
 688 }
 689
 690