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 GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
 147     return GV;
 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]) || isa<GlobalValue>(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))
 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   // Are we checking for alias of the same value?
 250   if (V1 == V2) return MustAlias;
 251
 252   if ((!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType())) &&
 253       V1->getType() != Type::LongTy && V2->getType() != Type::LongTy)
 254     return NoAlias;  // Scalars cannot alias each other
 255
 256   // Strip off cast instructions...
 257   if (const Instruction *I = dyn_cast<CastInst>(V1))
 258     return alias(I->getOperand(0), V1Size, V2, V2Size);
 259   if (const Instruction *I = dyn_cast<CastInst>(V2))
 260     return alias(V1, V1Size, I->getOperand(0), V2Size);
 261
 262   // Figure out what objects these things are pointing to if we can...
 263   const Value *O1 = getUnderlyingObject(V1);
 264   const Value *O2 = getUnderlyingObject(V2);
 265
 266   // Pointing at a discernible object?
 267   if (O1 && O2) {
 268     if (isa<Argument>(O1)) {
 269       // Incoming argument cannot alias locally allocated object!
 270       if (isa<AllocationInst>(O2)) return NoAlias;
 271       // Otherwise, nothing is known...
 272     } else if (isa<Argument>(O2)) {
 273       // Incoming argument cannot alias locally allocated object!
 274       if (isa<AllocationInst>(O1)) return NoAlias;
 275       // Otherwise, nothing is known...
 276     } else {
 277       // If they are two different objects, we know that we have no alias...
 278       if (O1 != O2) return NoAlias;
 279     }
 280
 281     // If they are the same object, they we can look at the indexes.  If they
 282     // index off of the object is the same for both pointers, they must alias.
 283     // If they are provably different, they must not alias.  Otherwise, we can't
 284     // tell anything.
 285   } else if (O1 && !isa<Argument>(O1) && isa<ConstantPointerNull>(V2)) {
 286     return NoAlias;                    // Unique values don't alias null
 287   } else if (O2 && !isa<Argument>(O2) && isa<ConstantPointerNull>(V1)) {
 288     return NoAlias;                    // Unique values don't alias null
 289   }
 290
 291   // If we have two gep instructions with must-alias'ing base pointers, figure
 292   // out if the indexes to the GEP tell us anything about the derived pointer.
 293   // Note that we also handle chains of getelementptr instructions as well as
 294   // constant expression getelementptrs here.
 295   //
 296   if (isGEP(V1) && isGEP(V2)) {
 297     // Drill down into the first non-gep value, to test for must-aliasing of
 298     // the base pointers.
 299     const Value *BasePtr1 = V1, *BasePtr2 = V2;
 300     do {
 301       BasePtr1 = cast<User>(BasePtr1)->getOperand(0);
 302     } while (isGEP(BasePtr1) &&
 303              cast<User>(BasePtr1)->getOperand(1) ==
 304        Constant::getNullValue(cast<User>(BasePtr1)->getOperand(1)->getType()));
 305     do {
 306       BasePtr2 = cast<User>(BasePtr2)->getOperand(0);
 307     } while (isGEP(BasePtr2) &&
 308              cast<User>(BasePtr2)->getOperand(1) ==
 309        Constant::getNullValue(cast<User>(BasePtr2)->getOperand(1)->getType()));
 310
 311     // Do the base pointers alias?
 312     AliasResult BaseAlias = alias(BasePtr1, V1Size, BasePtr2, V2Size);
 313     if (BaseAlias == NoAlias) return NoAlias;
 314     if (BaseAlias == MustAlias) {
 315       // If the base pointers alias each other exactly, check to see if we can
 316       // figure out anything about the resultant pointers, to try to prove
 317       // non-aliasing.
 318
 319       // Collect all of the chained GEP operands together into one simple place
 320       std::vector<Value*> GEP1Ops, GEP2Ops;
 321       BasePtr1 = GetGEPOperands(V1, GEP1Ops);
 322       BasePtr2 = GetGEPOperands(V2, GEP2Ops);
 323
 324       AliasResult GAlias =
 325         CheckGEPInstructions(BasePtr1->getType(), GEP1Ops, V1Size,
 326                              BasePtr2->getType(), GEP2Ops, V2Size);
 327       if (GAlias != MayAlias)
 328         return GAlias;
 329     }
 330   }
 331
 332   // Check to see if these two pointers are related by a getelementptr
 333   // instruction.  If one pointer is a GEP with a non-zero index of the other
 334   // pointer, we know they cannot alias.
 335   //
 336   if (isGEP(V2)) {
 337     std::swap(V1, V2);
 338     std::swap(V1Size, V2Size);
 339   }
 340
 341   if (V1Size != ~0U && V2Size != ~0U)
 342     if (const User *GEP = isGEP(V1)) {
 343       std::vector<Value*> GEPOperands;
 344       const Value *BasePtr = GetGEPOperands(V1, GEPOperands);
 345
 346       AliasResult R = alias(BasePtr, V1Size, V2, V2Size);
 347       if (R == MustAlias) {
 348         // If there is at least one non-zero constant index, we know they cannot
 349         // alias.
 350         bool ConstantFound = false;
 351         bool AllZerosFound = true;
 352         for (unsigned i = 0, e = GEPOperands.size(); i != e; ++i)
 353           if (const Constant *C = dyn_cast<Constant>(GEPOperands[i])) {
 354             if (!C->isNullValue()) {
 355               ConstantFound = true;
 356               AllZerosFound = false;
 357               break;
 358             }
 359           } else {
 360             AllZerosFound = false;
 361           }
 362
 363         // If we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 must aliases
 364         // the ptr, the end result is a must alias also.
 365         if (AllZerosFound)
 366           return MustAlias;
 367
 368         if (ConstantFound) {
 369           if (V2Size <= 1 && V1Size <= 1)  // Just pointer check?
 370             return NoAlias;
 371
 372           // Otherwise we have to check to see that the distance is more than
 373           // the size of the argument... build an index vector that is equal to
 374           // the arguments provided, except substitute 0's for any variable
 375           // indexes we find...
 376           for (unsigned i = 0; i != GEPOperands.size(); ++i)
 377             if (!isa<Constant>(GEPOperands[i]) || isa<GlobalValue>(GEPOperands[i]) ||
 378                 isa<ConstantExpr>(GEPOperands[i]))
 379               GEPOperands[i] =Constant::getNullValue(GEPOperands[i]->getType());
 380           int64_t Offset = getTargetData().getIndexedOffset(BasePtr->getType(),
 381                                                             GEPOperands);
 382           if (Offset >= (int64_t)V2Size || Offset <= -(int64_t)V1Size)
 383             return NoAlias;
 384         }
 385       }
 386     }
 387
 388   return MayAlias;
 389 }
 390
 391 static bool ValuesEqual(Value *V1, Value *V2) {
 392   if (V1->getType() == V2->getType())
 393     return V1 == V2;
 394   if (Constant *C1 = dyn_cast<Constant>(V1))
 395     if (Constant *C2 = dyn_cast<Constant>(V2)) {
 396       // Sign extend the constants to long types.
 397       C1 = ConstantExpr::getSignExtend(C1, Type::LongTy);
 398       C2 = ConstantExpr::getSignExtend(C2, Type::LongTy);
 399       return C1 == C2;
 400     }
 401   return false;
 402 }
 403
 404 /// CheckGEPInstructions - Check two GEP instructions with known must-aliasing
 405 /// base pointers.  This checks to see if the index expressions preclude the
 406 /// pointers from aliasing...
 407 AliasAnalysis::AliasResult BasicAliasAnalysis::
 408 CheckGEPInstructions(const Type* BasePtr1Ty, std::vector<Value*> &GEP1Ops,
 409                      unsigned G1S,
 410                      const Type *BasePtr2Ty, std::vector<Value*> &GEP2Ops,
 411                      unsigned G2S) {
 412   // We currently can't handle the case when the base pointers have different
 413   // primitive types.  Since this is uncommon anyway, we are happy being
 414   // extremely conservative.
 415   if (BasePtr1Ty != BasePtr2Ty)
 416     return MayAlias;
 417
 418   const Type *GEPPointerTy = BasePtr1Ty;
 419
 420   // Find the (possibly empty) initial sequence of equal values... which are not
 421   // necessarily constants.
 422   unsigned NumGEP1Operands = GEP1Ops.size(), NumGEP2Operands = GEP2Ops.size();
 423   unsigned MinOperands = std::min(NumGEP1Operands, NumGEP2Operands);
 424   unsigned MaxOperands = std::max(NumGEP1Operands, NumGEP2Operands);
 425   unsigned UnequalOper = 0;
 426   while (UnequalOper != MinOperands &&
 427          ValuesEqual(GEP1Ops[UnequalOper], GEP2Ops[UnequalOper])) {
 428     // Advance through the type as we go...
 429     ++UnequalOper;
 430     if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty))
 431       BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[UnequalOper-1]);
 432     else {
 433       // If all operands equal each other, then the derived pointers must
 434       // alias each other...
 435       BasePtr1Ty = 0;
 436       assert(UnequalOper == NumGEP1Operands && UnequalOper == NumGEP2Operands &&
 437              "Ran out of type nesting, but not out of operands?");
 438       return MustAlias;
 439     }
 440   }
 441
 442   // If we have seen all constant operands, and run out of indexes on one of the
 443   // getelementptrs, check to see if the tail of the leftover one is all zeros.
 444   // If so, return mustalias.
 445   if (UnequalOper == MinOperands) {
 446     if (GEP1Ops.size() < GEP2Ops.size()) std::swap(GEP1Ops, GEP2Ops);
 447
 448     bool AllAreZeros = true;
 449     for (unsigned i = UnequalOper; i != MaxOperands; ++i)
 450       if (!isa<Constant>(GEP1Ops[i]) ||
 451           !cast<Constant>(GEP1Ops[i])->isNullValue()) {
 452         AllAreZeros = false;
 453         break;
 454       }
 455     if (AllAreZeros) return MustAlias;
 456   }
 457
 458
 459   // So now we know that the indexes derived from the base pointers,
 460   // which are known to alias, are different.  We can still determine a
 461   // no-alias result if there are differing constant pairs in the index
 462   // chain.  For example:
 463   //        A[i][0] != A[j][1] iff (&A[0][1]-&A[0][0] >= std::max(G1S, G2S))
 464   //
 465   unsigned SizeMax = std::max(G1S, G2S);
 466   if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work...
 467
 468   // Scan for the first operand that is constant and unequal in the
 469   // two getelementptrs...
 470   unsigned FirstConstantOper = UnequalOper;
 471   for (; FirstConstantOper != MinOperands; ++FirstConstantOper) {
 472     const Value *G1Oper = GEP1Ops[FirstConstantOper];
 473     const Value *G2Oper = GEP2Ops[FirstConstantOper];
 474
 475     if (G1Oper != G2Oper)   // Found non-equal constant indexes...
 476       if (Constant *G1OC = dyn_cast<Constant>(const_cast<Value*>(G1Oper)))
 477         if (Constant *G2OC = dyn_cast<Constant>(const_cast<Value*>(G2Oper))) {
 478           if (G1OC->getType() != G2OC->getType()) {
 479             // Sign extend both operands to long.
 480             G1OC = ConstantExpr::getSignExtend(G1OC, Type::LongTy);
 481             G2OC = ConstantExpr::getSignExtend(G2OC, Type::LongTy);
 482             GEP1Ops[FirstConstantOper] = G1OC;
 483             GEP2Ops[FirstConstantOper] = G2OC;
 484           }
 485
 486           if (G1OC != G2OC) {
 487             // Make sure they are comparable (ie, not constant expressions)...
 488             // and make sure the GEP with the smaller leading constant is GEP1.
 489             Constant *Compare = ConstantExpr::getSetGT(G1OC, G2OC);
 490             if (ConstantBool *CV = dyn_cast<ConstantBool>(Compare)) {
 491               if (CV->getValue())   // If they are comparable and G2 > G1
 492                 std::swap(GEP1Ops, GEP2Ops);  // Make GEP1 < GEP2
 493               break;
 494             }
 495           }
 496         }
 497     BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(G1Oper);
 498   }
 499
 500   // No shared constant operands, and we ran out of common operands.  At this
 501   // point, the GEP instructions have run through all of their operands, and we
 502   // haven't found evidence that there are any deltas between the GEP's.
 503   // However, one GEP may have more operands than the other.  If this is the
 504   // case, there may still be hope.  Check this now.
 505   if (FirstConstantOper == MinOperands) {
 506     // Make GEP1Ops be the longer one if there is a longer one.
 507     if (GEP1Ops.size() < GEP2Ops.size())
 508       std::swap(GEP1Ops, GEP2Ops);
 509
 510     // Is there anything to check?
 511     if (GEP1Ops.size() > MinOperands) {
 512       for (unsigned i = FirstConstantOper; i != MaxOperands; ++i)
 513         if (isa<ConstantInt>(GEP1Ops[i]) &&
 514             !cast<Constant>(GEP1Ops[i])->isNullValue()) {
 515           // Yup, there's a constant in the tail.  Set all variables to
 516           // constants in the GEP instruction to make it suiteable for
 517           // TargetData::getIndexedOffset.
 518           for (i = 0; i != MaxOperands; ++i)
 519             if (!isa<ConstantInt>(GEP1Ops[i]))
 520               GEP1Ops[i] = Constant::getNullValue(GEP1Ops[i]->getType());
 521           // Okay, now get the offset.  This is the relative offset for the full
 522           // instruction.
 523           const TargetData &TD = getTargetData();
 524           int64_t Offset1 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops);
 525
 526           // Now crop off any constants from the end...
 527           GEP1Ops.resize(MinOperands);
 528           int64_t Offset2 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops);
 529
 530           // If the tail provided a bit enough offset, return noalias!
 531           if ((uint64_t)(Offset2-Offset1) >= SizeMax)
 532             return NoAlias;
 533         }
 534     }
 535
 536     // Couldn't find anything useful.
 537     return MayAlias;
 538   }
 539
 540   // If there are non-equal constants arguments, then we can figure
 541   // out a minimum known delta between the two index expressions... at
 542   // this point we know that the first constant index of GEP1 is less
 543   // than the first constant index of GEP2.
 544
 545   // Advance BasePtr[12]Ty over this first differing constant operand.
 546   BasePtr2Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(GEP2Ops[FirstConstantOper]);
 547   BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(GEP1Ops[FirstConstantOper]);
 548
 549   // We are going to be using TargetData::getIndexedOffset to determine the
 550   // offset that each of the GEP's is reaching.  To do this, we have to convert
 551   // all variable references to constant references.  To do this, we convert the
 552   // initial equal sequence of variables into constant zeros to start with.
 553   for (unsigned i = 0; i != FirstConstantOper; ++i) {
 554     if (!isa<Constant>(GEP1Ops[i]) || isa<ConstantExpr>(GEP1Ops[i]) ||
 555         !isa<Constant>(GEP2Ops[i]) || isa<ConstantExpr>(GEP2Ops[i]))
 556       GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Type::UIntTy);
 557   }
 558
 559   // We know that GEP1Ops[FirstConstantOper] & GEP2Ops[FirstConstantOper] are ok
 560
 561   // Loop over the rest of the operands...
 562   for (unsigned i = FirstConstantOper+1; i != MaxOperands; ++i) {
 563     const Value *Op1 = i < GEP1Ops.size() ? GEP1Ops[i] : 0;
 564     const Value *Op2 = i < GEP2Ops.size() ? GEP2Ops[i] : 0;
 565     // If they are equal, use a zero index...
 566     if (Op1 == Op2 && BasePtr1Ty == BasePtr2Ty) {
 567       if (!isa<Constant>(Op1) || isa<ConstantExpr>(Op1))
 568         GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Op1->getType());
 569       // Otherwise, just keep the constants we have.
 570     } else {
 571       if (Op1) {
 572         if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
 573           // If this is an array index, make sure the array element is in range.
 574           if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
 575             if (Op1C->getRawValue() >= AT->getNumElements())
 576               return MayAlias;  // Be conservative with out-of-range accesses
 577
 578         } else {
 579           // GEP1 is known to produce a value less than GEP2.  To be
 580           // conservatively correct, we must assume the largest possible
 581           // constant is used in this position.  This cannot be the initial
 582           // index to the GEP instructions (because we know we have at least one
 583           // element before this one with the different constant arguments), so
 584           // we know that the current index must be into either a struct or
 585           // array.  Because we know it's not constant, this cannot be a
 586           // structure index.  Because of this, we can calculate the maximum
 587           // value possible.
 588           //
 589           if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
 590             GEP1Ops[i] = ConstantSInt::get(Type::LongTy,AT->getNumElements()-1);
 591         }
 592       }
 593
 594       if (Op2) {
 595         if (const ConstantInt *Op2C = dyn_cast<ConstantInt>(Op2)) {
 596           // If this is an array index, make sure the array element is in range.
 597           if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
 598             if (Op2C->getRawValue() >= AT->getNumElements())
 599               return MayAlias;  // Be conservative with out-of-range accesses
 600         } else {  // Conservatively assume the minimum value for this index
 601           GEP2Ops[i] = Constant::getNullValue(Op2->getType());
 602         }
 603       }
 604     }
 605
 606     if (BasePtr1Ty && Op1) {
 607       if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty))
 608         BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[i]);
 609       else
 610         BasePtr1Ty = 0;
 611     }
 612
 613     if (BasePtr2Ty && Op2) {
 614       if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr2Ty))
 615         BasePtr2Ty = CT->getTypeAtIndex(GEP2Ops[i]);
 616       else
 617         BasePtr2Ty = 0;
 618     }
 619   }
 620
 621   int64_t Offset1 = getTargetData().getIndexedOffset(GEPPointerTy, GEP1Ops);
 622   int64_t Offset2 = getTargetData().getIndexedOffset(GEPPointerTy, GEP2Ops);
 623   assert(Offset1 < Offset2 &&"There is at least one different constant here!");
 624
 625   if ((uint64_t)(Offset2-Offset1) >= SizeMax) {
 626     //std::cerr << "Determined that these two GEP's don't alias ["
 627     //          << SizeMax << " bytes]: \n" << *GEP1 << *GEP2;
 628     return NoAlias;
 629   }
 630   return MayAlias;
 631 }
 632
 633 namespace {
 634   struct StringCompare {
 635     bool operator()(const char *LHS, const char *RHS) {
 636       return strcmp(LHS, RHS) < 0;
 637     }
 638   };
 639 }
 640
 641 // Note that this list cannot contain libm functions (such as acos and sqrt)
 642 // that set errno on a domain or other error.
 643 static const char *DoesntAccessMemoryTable[] = {
 644   // LLVM intrinsics:
 645   "llvm.frameaddress", "llvm.returnaddress", "llvm.readport", "llvm.isunordered",
 646
 647   "abs", "labs", "llabs", "imaxabs", "fabs", "fabsf", "fabsl",
 648   "trunc", "truncf", "truncl", "ldexp",
 649
 650   "atan", "atanf", "atanl",   "atan2", "atan2f", "atan2l",
 651   "cbrt",
 652   "cos", "cosf", "cosl",      "cosh", "coshf", "coshl",
 653   "exp", "expf", "expl",
 654   "hypot",
 655   "sin", "sinf", "sinl",      "sinh", "sinhf", "sinhl",
 656   "tan", "tanf", "tanl",      "tanh", "tanhf", "tanhl",
 657
 658   // ctype.h
 659   "isalnum", "isalpha", "iscntrl", "isdigit", "isgraph", "islower", "isprint"
 660   "ispunct", "isspace", "isupper", "isxdigit", "tolower", "toupper",
 661
 662   // wctype.h"
 663   "iswalnum", "iswalpha", "iswcntrl", "iswdigit", "iswgraph", "iswlower",
 664   "iswprint", "iswpunct", "iswspace", "iswupper", "iswxdigit",
 665
 666   "iswctype", "towctrans", "towlower", "towupper",
 667
 668   "btowc", "wctob",
 669
 670   "isinf", "isnan", "finite",
 671
 672   // C99 math functions
 673   "copysign", "copysignf", "copysignd",
 674   "nexttoward", "nexttowardf", "nexttowardd",
 675   "nextafter", "nextafterf", "nextafterd",
 676
 677   // glibc functions:
 678   "__fpclassify", "__fpclassifyf", "__fpclassifyl",
 679   "__signbit", "__signbitf", "__signbitl",
 680 };
 681
 682 static const unsigned DAMTableSize =
 683     sizeof(DoesntAccessMemoryTable)/sizeof(DoesntAccessMemoryTable[0]);
 684
 685 /// doesNotAccessMemory - Return true if we know that the function does not
 686 /// access memory at all.  Since basicaa does no analysis, we can only do simple
 687 /// things here.  In particular, if we have an external function with the name
 688 /// of a standard C library function, we are allowed to assume it will be
 689 /// resolved by libc, so we can hardcode some entries in here.
 690 bool BasicAliasAnalysis::doesNotAccessMemory(Function *F) {
 691   if (!F->isExternal()) return false;
 692
 693   static bool Initialized = false;
 694   if (!Initialized) {
 695     // Sort the table the first time through.
 696     std::sort(DoesntAccessMemoryTable, DoesntAccessMemoryTable+DAMTableSize,
 697               StringCompare());
 698     Initialized = true;
 699   }
 700
 701   const char **Ptr = std::lower_bound(DoesntAccessMemoryTable,
 702                                       DoesntAccessMemoryTable+DAMTableSize,
 703                                       F->getName().c_str(), StringCompare());
 704   return Ptr != DoesntAccessMemoryTable+DAMTableSize && *Ptr == F->getName();
 705 }
 706
 707
 708 static const char *OnlyReadsMemoryTable[] = {
 709   "atoi", "atol", "atof", "atoll", "atoq", "a64l",
 710   "bcmp", "memcmp", "memchr", "memrchr", "wmemcmp", "wmemchr",
 711
 712   // Strings
 713   "strcmp", "strcasecmp", "strcoll", "strncmp", "strncasecmp",
 714   "strchr", "strcspn", "strlen", "strpbrk", "strrchr", "strspn", "strstr",
 715   "index", "rindex",
 716
 717   // Wide char strings
 718   "wcschr", "wcscmp", "wcscoll", "wcscspn", "wcslen", "wcsncmp", "wcspbrk",
 719   "wcsrchr", "wcsspn", "wcsstr",
 720
 721   // glibc
 722   "alphasort", "alphasort64", "versionsort", "versionsort64",
 723
 724   // C99
 725   "nan", "nanf", "nand",
 726
 727   // File I/O
 728   "feof", "ferror", "fileno",
 729   "feof_unlocked", "ferror_unlocked", "fileno_unlocked"
 730 };
 731
 732 static const unsigned ORMTableSize =
 733     sizeof(OnlyReadsMemoryTable)/sizeof(OnlyReadsMemoryTable[0]);
 734
 735 bool BasicAliasAnalysis::onlyReadsMemory(Function *F) {
 736   if (doesNotAccessMemory(F)) return true;
 737   if (!F->isExternal()) return false;
 738
 739   static bool Initialized = false;
 740   if (!Initialized) {
 741     // Sort the table the first time through.
 742     std::sort(OnlyReadsMemoryTable, OnlyReadsMemoryTable+ORMTableSize,
 743               StringCompare());
 744     Initialized = true;
 745   }
 746
 747   const char **Ptr = std::lower_bound(OnlyReadsMemoryTable,
 748                                       OnlyReadsMemoryTable+ORMTableSize,
 749                                       F->getName().c_str(), StringCompare());
 750   return Ptr != OnlyReadsMemoryTable+ORMTableSize && *Ptr == F->getName();
 751 }
 752
 753