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