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