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