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