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       } else if (O1 != O2) {
 342         if (!isa<Argument>(O1))
 343           // If they are two different objects, we know that we have no alias...
 344           return NoAlias;
 345       }
 346
 347       // If they are the same object, they we can look at the indexes.  If they
 348       // index off of the object is the same for both pointers, they must alias.
 349       // If they are provably different, they must not alias.  Otherwise, we
 350       // can't tell anything.
 351     }
 352
 353
 354     if (!isa<Argument>(O1) && isa<ConstantPointerNull>(V2))
 355       return NoAlias;                    // Unique values don't alias null
 356
 357     if (isa<GlobalVariable>(O1) ||
 358         (isa<AllocationInst>(O1) &&
 359          !cast<AllocationInst>(O1)->isArrayAllocation()))
 360       if (cast<PointerType>(O1->getType())->getElementType()->isSized()) {
 361         // If the size of the other access is larger than the total size of the
 362         // global/alloca/malloc, it cannot be accessing the global (it's
 363         // undefined to load or store bytes before or after an object).
 364         const Type *ElTy = cast<PointerType>(O1->getType())->getElementType();
 365         unsigned GlobalSize = getTargetData().getTypeSize(ElTy);
 366         if (GlobalSize < V2Size && V2Size != ~0U)
 367           return NoAlias;
 368       }
 369   }
 370
 371   if (O2) {
 372     if (!isa<Argument>(O2) && isa<ConstantPointerNull>(V1))
 373       return NoAlias;                    // Unique values don't alias null
 374
 375     if (isa<GlobalVariable>(O2) ||
 376         (isa<AllocationInst>(O2) &&
 377          !cast<AllocationInst>(O2)->isArrayAllocation()))
 378       if (cast<PointerType>(O2->getType())->getElementType()->isSized()) {
 379         // If the size of the other access is larger than the total size of the
 380         // global/alloca/malloc, it cannot be accessing the object (it's
 381         // undefined to load or store bytes before or after an object).
 382         const Type *ElTy = cast<PointerType>(O2->getType())->getElementType();
 383         unsigned GlobalSize = getTargetData().getTypeSize(ElTy);
 384         if (GlobalSize < V1Size && V1Size != ~0U)
 385           return NoAlias;
 386       }
 387   }
 388
 389   // If we have two gep instructions with must-alias'ing base pointers, figure
 390   // out if the indexes to the GEP tell us anything about the derived pointer.
 391   // Note that we also handle chains of getelementptr instructions as well as
 392   // constant expression getelementptrs here.
 393   //
 394   if (isGEP(V1) && isGEP(V2)) {
 395     // Drill down into the first non-gep value, to test for must-aliasing of
 396     // the base pointers.
 397     const Value *BasePtr1 = V1, *BasePtr2 = V2;
 398     do {
 399       BasePtr1 = cast<User>(BasePtr1)->getOperand(0);
 400     } while (isGEP(BasePtr1) &&
 401              cast<User>(BasePtr1)->getOperand(1) ==
 402        Constant::getNullValue(cast<User>(BasePtr1)->getOperand(1)->getType()));
 403     do {
 404       BasePtr2 = cast<User>(BasePtr2)->getOperand(0);
 405     } while (isGEP(BasePtr2) &&
 406              cast<User>(BasePtr2)->getOperand(1) ==
 407        Constant::getNullValue(cast<User>(BasePtr2)->getOperand(1)->getType()));
 408
 409     // Do the base pointers alias?
 410     AliasResult BaseAlias = alias(BasePtr1, ~0U, BasePtr2, ~0U);
 411     if (BaseAlias == NoAlias) return NoAlias;
 412     if (BaseAlias == MustAlias) {
 413       // If the base pointers alias each other exactly, check to see if we can
 414       // figure out anything about the resultant pointers, to try to prove
 415       // non-aliasing.
 416
 417       // Collect all of the chained GEP operands together into one simple place
 418       SmallVector<Value*, 16> GEP1Ops, GEP2Ops;
 419       BasePtr1 = GetGEPOperands(V1, GEP1Ops);
 420       BasePtr2 = GetGEPOperands(V2, GEP2Ops);
 421
 422       // If GetGEPOperands were able to fold to the same must-aliased pointer,
 423       // do the comparison.
 424       if (BasePtr1 == BasePtr2) {
 425         AliasResult GAlias =
 426           CheckGEPInstructions(BasePtr1->getType(),
 427                                &GEP1Ops[0], GEP1Ops.size(), V1Size,
 428                                BasePtr2->getType(),
 429                                &GEP2Ops[0], GEP2Ops.size(), V2Size);
 430         if (GAlias != MayAlias)
 431           return GAlias;
 432       }
 433     }
 434   }
 435
 436   // Check to see if these two pointers are related by a getelementptr
 437   // instruction.  If one pointer is a GEP with a non-zero index of the other
 438   // pointer, we know they cannot alias.
 439   //
 440   if (isGEP(V2)) {
 441     std::swap(V1, V2);
 442     std::swap(V1Size, V2Size);
 443   }
 444
 445   if (V1Size != ~0U && V2Size != ~0U)
 446     if (isGEP(V1)) {
 447       SmallVector<Value*, 16> GEPOperands;
 448       const Value *BasePtr = GetGEPOperands(V1, GEPOperands);
 449
 450       AliasResult R = alias(BasePtr, V1Size, V2, V2Size);
 451       if (R == MustAlias) {
 452         // If there is at least one non-zero constant index, we know they cannot
 453         // alias.
 454         bool ConstantFound = false;
 455         bool AllZerosFound = true;
 456         for (unsigned i = 0, e = GEPOperands.size(); i != e; ++i)
 457           if (const Constant *C = dyn_cast<Constant>(GEPOperands[i])) {
 458             if (!C->isNullValue()) {
 459               ConstantFound = true;
 460               AllZerosFound = false;
 461               break;
 462             }
 463           } else {
 464             AllZerosFound = false;
 465           }
 466
 467         // If we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 must aliases
 468         // the ptr, the end result is a must alias also.
 469         if (AllZerosFound)
 470           return MustAlias;
 471
 472         if (ConstantFound) {
 473           if (V2Size <= 1 && V1Size <= 1)  // Just pointer check?
 474             return NoAlias;
 475
 476           // Otherwise we have to check to see that the distance is more than
 477           // the size of the argument... build an index vector that is equal to
 478           // the arguments provided, except substitute 0's for any variable
 479           // indexes we find...
 480           if (cast<PointerType>(
 481                 BasePtr->getType())->getElementType()->isSized()) {
 482             for (unsigned i = 0; i != GEPOperands.size(); ++i)
 483               if (!isa<ConstantInt>(GEPOperands[i]))
 484                 GEPOperands[i] =
 485                   Constant::getNullValue(GEPOperands[i]->getType());
 486             int64_t Offset =
 487               getTargetData().getIndexedOffset(BasePtr->getType(),
 488                                                &GEPOperands[0],
 489                                                GEPOperands.size());
 490
 491             if (Offset >= (int64_t)V2Size || Offset <= -(int64_t)V1Size)
 492               return NoAlias;
 493           }
 494         }
 495       }
 496     }
 497
 498   return MayAlias;
 499 }
 500
 501 // This function is used to determin if the indices of two GEP instructions are
 502 // equal. V1 and V2 are the indices.
 503 static bool IndexOperandsEqual(Value *V1, Value *V2) {
 504   if (V1->getType() == V2->getType())
 505     return V1 == V2;
 506   if (Constant *C1 = dyn_cast<Constant>(V1))
 507     if (Constant *C2 = dyn_cast<Constant>(V2)) {
 508       // Sign extend the constants to long types, if necessary
 509       if (C1->getType() != Type::Int64Ty)
 510         C1 = ConstantExpr::getSExt(C1, Type::Int64Ty);
 511       if (C2->getType() != Type::Int64Ty)
 512         C2 = ConstantExpr::getSExt(C2, Type::Int64Ty);
 513       return C1 == C2;
 514     }
 515   return false;
 516 }
 517
 518 /// CheckGEPInstructions - Check two GEP instructions with known must-aliasing
 519 /// base pointers.  This checks to see if the index expressions preclude the
 520 /// pointers from aliasing...
 521 AliasAnalysis::AliasResult
 522 BasicAliasAnalysis::CheckGEPInstructions(
 523   const Type* BasePtr1Ty, Value **GEP1Ops, unsigned NumGEP1Ops, unsigned G1S,
 524   const Type *BasePtr2Ty, Value **GEP2Ops, unsigned NumGEP2Ops, unsigned G2S) {
 525   // We currently can't handle the case when the base pointers have different
 526   // primitive types.  Since this is uncommon anyway, we are happy being
 527   // extremely conservative.
 528   if (BasePtr1Ty != BasePtr2Ty)
 529     return MayAlias;
 530
 531   const PointerType *GEPPointerTy = cast<PointerType>(BasePtr1Ty);
 532
 533   // Find the (possibly empty) initial sequence of equal values... which are not
 534   // necessarily constants.
 535   unsigned NumGEP1Operands = NumGEP1Ops, NumGEP2Operands = NumGEP2Ops;
 536   unsigned MinOperands = std::min(NumGEP1Operands, NumGEP2Operands);
 537   unsigned MaxOperands = std::max(NumGEP1Operands, NumGEP2Operands);
 538   unsigned UnequalOper = 0;
 539   while (UnequalOper != MinOperands &&
 540          IndexOperandsEqual(GEP1Ops[UnequalOper], GEP2Ops[UnequalOper])) {
 541     // Advance through the type as we go...
 542     ++UnequalOper;
 543     if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty))
 544       BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[UnequalOper-1]);
 545     else {
 546       // If all operands equal each other, then the derived pointers must
 547       // alias each other...
 548       BasePtr1Ty = 0;
 549       assert(UnequalOper == NumGEP1Operands && UnequalOper == NumGEP2Operands &&
 550              "Ran out of type nesting, but not out of operands?");
 551       return MustAlias;
 552     }
 553   }
 554
 555   // If we have seen all constant operands, and run out of indexes on one of the
 556   // getelementptrs, check to see if the tail of the leftover one is all zeros.
 557   // If so, return mustalias.
 558   if (UnequalOper == MinOperands) {
 559     if (NumGEP1Ops < NumGEP2Ops) {
 560       std::swap(GEP1Ops, GEP2Ops);
 561       std::swap(NumGEP1Ops, NumGEP2Ops);
 562     }
 563
 564     bool AllAreZeros = true;
 565     for (unsigned i = UnequalOper; i != MaxOperands; ++i)
 566       if (!isa<Constant>(GEP1Ops[i]) ||
 567           !cast<Constant>(GEP1Ops[i])->isNullValue()) {
 568         AllAreZeros = false;
 569         break;
 570       }
 571     if (AllAreZeros) return MustAlias;
 572   }
 573
 574
 575   // So now we know that the indexes derived from the base pointers,
 576   // which are known to alias, are different.  We can still determine a
 577   // no-alias result if there are differing constant pairs in the index
 578   // chain.  For example:
 579   //        A[i][0] != A[j][1] iff (&A[0][1]-&A[0][0] >= std::max(G1S, G2S))
 580   //
 581   // We have to be careful here about array accesses.  In particular, consider:
 582   //        A[1][0] vs A[0][i]
 583   // In this case, we don't *know* that the array will be accessed in bounds:
 584   // the index could even be negative.  Because of this, we have to
 585   // conservatively *give up* and return may alias.  We disregard differing
 586   // array subscripts that are followed by a variable index without going
 587   // through a struct.
 588   //
 589   unsigned SizeMax = std::max(G1S, G2S);
 590   if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work.
 591
 592   // Scan for the first operand that is constant and unequal in the
 593   // two getelementptrs...
 594   unsigned FirstConstantOper = UnequalOper;
 595   for (; FirstConstantOper != MinOperands; ++FirstConstantOper) {
 596     const Value *G1Oper = GEP1Ops[FirstConstantOper];
 597     const Value *G2Oper = GEP2Ops[FirstConstantOper];
 598
 599     if (G1Oper != G2Oper)   // Found non-equal constant indexes...
 600       if (Constant *G1OC = dyn_cast<ConstantInt>(const_cast<Value*>(G1Oper)))
 601         if (Constant *G2OC = dyn_cast<ConstantInt>(const_cast<Value*>(G2Oper))){
 602           if (G1OC->getType() != G2OC->getType()) {
 603             // Sign extend both operands to long.
 604             if (G1OC->getType() != Type::Int64Ty)
 605               G1OC = ConstantExpr::getSExt(G1OC, Type::Int64Ty);
 606             if (G2OC->getType() != Type::Int64Ty)
 607               G2OC = ConstantExpr::getSExt(G2OC, Type::Int64Ty);
 608             GEP1Ops[FirstConstantOper] = G1OC;
 609             GEP2Ops[FirstConstantOper] = G2OC;
 610           }
 611
 612           if (G1OC != G2OC) {
 613             // Handle the "be careful" case above: if this is an array/vector
 614             // subscript, scan for a subsequent variable array index.
 615             if (isa<SequentialType>(BasePtr1Ty))  {
 616               const Type *NextTy =
 617                 cast<SequentialType>(BasePtr1Ty)->getElementType();
 618               bool isBadCase = false;
 619
 620               for (unsigned Idx = FirstConstantOper+1;
 621                    Idx != MinOperands && isa<SequentialType>(NextTy); ++Idx) {
 622                 const Value *V1 = GEP1Ops[Idx], *V2 = GEP2Ops[Idx];
 623                 if (!isa<Constant>(V1) || !isa<Constant>(V2)) {
 624                   isBadCase = true;
 625                   break;
 626                 }
 627                 NextTy = cast<SequentialType>(NextTy)->getElementType();
 628               }
 629
 630               if (isBadCase) G1OC = 0;
 631             }
 632
 633             // Make sure they are comparable (ie, not constant expressions), and
 634             // make sure the GEP with the smaller leading constant is GEP1.
 635             if (G1OC) {
 636               Constant *Compare = ConstantExpr::getICmp(ICmpInst::ICMP_SGT,
 637                                                         G1OC, G2OC);
 638               if (ConstantInt *CV = dyn_cast<ConstantInt>(Compare)) {
 639                 if (CV->getZExtValue()) {  // If they are comparable and G2 > G1
 640                   std::swap(GEP1Ops, GEP2Ops);  // Make GEP1 < GEP2
 641                   std::swap(NumGEP1Ops, NumGEP2Ops);
 642                 }
 643                 break;
 644               }
 645             }
 646           }
 647         }
 648     BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(G1Oper);
 649   }
 650
 651   // No shared constant operands, and we ran out of common operands.  At this
 652   // point, the GEP instructions have run through all of their operands, and we
 653   // haven't found evidence that there are any deltas between the GEP's.
 654   // However, one GEP may have more operands than the other.  If this is the
 655   // case, there may still be hope.  Check this now.
 656   if (FirstConstantOper == MinOperands) {
 657     // Make GEP1Ops be the longer one if there is a longer one.
 658     if (NumGEP1Ops < NumGEP2Ops) {
 659       std::swap(GEP1Ops, GEP2Ops);
 660       std::swap(NumGEP1Ops, NumGEP2Ops);
 661     }
 662
 663     // Is there anything to check?
 664     if (NumGEP1Ops > MinOperands) {
 665       for (unsigned i = FirstConstantOper; i != MaxOperands; ++i)
 666         if (isa<ConstantInt>(GEP1Ops[i]) &&
 667             !cast<ConstantInt>(GEP1Ops[i])->isZero()) {
 668           // Yup, there's a constant in the tail.  Set all variables to
 669           // constants in the GEP instruction to make it suiteable for
 670           // TargetData::getIndexedOffset.
 671           for (i = 0; i != MaxOperands; ++i)
 672             if (!isa<ConstantInt>(GEP1Ops[i]))
 673               GEP1Ops[i] = Constant::getNullValue(GEP1Ops[i]->getType());
 674           // Okay, now get the offset.  This is the relative offset for the full
 675           // instruction.
 676           const TargetData &TD = getTargetData();
 677           int64_t Offset1 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops,
 678                                                 NumGEP1Ops);
 679
 680           // Now check without any constants at the end.
 681           int64_t Offset2 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops,
 682                                                 MinOperands);
 683
 684           // If the tail provided a bit enough offset, return noalias!
 685           if ((uint64_t)(Offset2-Offset1) >= SizeMax)
 686             return NoAlias;
 687         }
 688     }
 689
 690     // Couldn't find anything useful.
 691     return MayAlias;
 692   }
 693
 694   // If there are non-equal constants arguments, then we can figure
 695   // out a minimum known delta between the two index expressions... at
 696   // this point we know that the first constant index of GEP1 is less
 697   // than the first constant index of GEP2.
 698
 699   // Advance BasePtr[12]Ty over this first differing constant operand.
 700   BasePtr2Ty = cast<CompositeType>(BasePtr1Ty)->
 701       getTypeAtIndex(GEP2Ops[FirstConstantOper]);
 702   BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->
 703       getTypeAtIndex(GEP1Ops[FirstConstantOper]);
 704
 705   // We are going to be using TargetData::getIndexedOffset to determine the
 706   // offset that each of the GEP's is reaching.  To do this, we have to convert
 707   // all variable references to constant references.  To do this, we convert the
 708   // initial sequence of array subscripts into constant zeros to start with.
 709   const Type *ZeroIdxTy = GEPPointerTy;
 710   for (unsigned i = 0; i != FirstConstantOper; ++i) {
 711     if (!isa<StructType>(ZeroIdxTy))
 712       GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Type::Int32Ty);
 713
 714     if (const CompositeType *CT = dyn_cast<CompositeType>(ZeroIdxTy))
 715       ZeroIdxTy = CT->getTypeAtIndex(GEP1Ops[i]);
 716   }
 717
 718   // We know that GEP1Ops[FirstConstantOper] & GEP2Ops[FirstConstantOper] are ok
 719
 720   // Loop over the rest of the operands...
 721   for (unsigned i = FirstConstantOper+1; i != MaxOperands; ++i) {
 722     const Value *Op1 = i < NumGEP1Ops ? GEP1Ops[i] : 0;
 723     const Value *Op2 = i < NumGEP2Ops ? GEP2Ops[i] : 0;
 724     // If they are equal, use a zero index...
 725     if (Op1 == Op2 && BasePtr1Ty == BasePtr2Ty) {
 726       if (!isa<ConstantInt>(Op1))
 727         GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Op1->getType());
 728       // Otherwise, just keep the constants we have.
 729     } else {
 730       if (Op1) {
 731         if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
 732           // If this is an array index, make sure the array element is in range.
 733           if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) {
 734             if (Op1C->getZExtValue() >= AT->getNumElements())
 735               return MayAlias;  // Be conservative with out-of-range accesses
 736           } else if (const VectorType *PT = dyn_cast<VectorType>(BasePtr1Ty)) {
 737             if (Op1C->getZExtValue() >= PT->getNumElements())
 738               return MayAlias;  // Be conservative with out-of-range accesses
 739           }
 740
 741         } else {
 742           // GEP1 is known to produce a value less than GEP2.  To be
 743           // conservatively correct, we must assume the largest possible
 744           // constant is used in this position.  This cannot be the initial
 745           // index to the GEP instructions (because we know we have at least one
 746           // element before this one with the different constant arguments), so
 747           // we know that the current index must be into either a struct or
 748           // array.  Because we know it's not constant, this cannot be a
 749           // structure index.  Because of this, we can calculate the maximum
 750           // value possible.
 751           //
 752           if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
 753             GEP1Ops[i] = ConstantInt::get(Type::Int64Ty,AT->getNumElements()-1);
 754           else if (const VectorType *PT = dyn_cast<VectorType>(BasePtr1Ty))
 755             GEP1Ops[i] = ConstantInt::get(Type::Int64Ty,PT->getNumElements()-1);
 756
 757         }
 758       }
 759
 760       if (Op2) {
 761         if (const ConstantInt *Op2C = dyn_cast<ConstantInt>(Op2)) {
 762           // If this is an array index, make sure the array element is in range.
 763           if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) {
 764             if (Op2C->getZExtValue() >= AT->getNumElements())
 765               return MayAlias;  // Be conservative with out-of-range accesses
 766           } else if (const VectorType *PT = dyn_cast<VectorType>(BasePtr1Ty)) {
 767             if (Op2C->getZExtValue() >= PT->getNumElements())
 768               return MayAlias;  // Be conservative with out-of-range accesses
 769           }
 770         } else {  // Conservatively assume the minimum value for this index
 771           GEP2Ops[i] = Constant::getNullValue(Op2->getType());
 772         }
 773       }
 774     }
 775
 776     if (BasePtr1Ty && Op1) {
 777       if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty))
 778         BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[i]);
 779       else
 780         BasePtr1Ty = 0;
 781     }
 782
 783     if (BasePtr2Ty && Op2) {
 784       if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr2Ty))
 785         BasePtr2Ty = CT->getTypeAtIndex(GEP2Ops[i]);
 786       else
 787         BasePtr2Ty = 0;
 788     }
 789   }
 790
 791   if (GEPPointerTy->getElementType()->isSized()) {
 792     int64_t Offset1 =
 793       getTargetData().getIndexedOffset(GEPPointerTy, GEP1Ops, NumGEP1Ops);
 794     int64_t Offset2 =
 795       getTargetData().getIndexedOffset(GEPPointerTy, GEP2Ops, NumGEP2Ops);
 796     assert(Offset1<Offset2 && "There is at least one different constant here!");
 797
 798     if ((uint64_t)(Offset2-Offset1) >= SizeMax) {
 799       //cerr << "Determined that these two GEP's don't alias ["
 800       //     << SizeMax << " bytes]: \n" << *GEP1 << *GEP2;
 801       return NoAlias;
 802     }
 803   }
 804   return MayAlias;
 805 }
 806
 807 namespace {
 808   struct VISIBILITY_HIDDEN StringCompare {
 809     bool operator()(const char *LHS, const char *RHS) {
 810       return strcmp(LHS, RHS) < 0;
 811     }
 812   };
 813 }
 814
 815 // Note that this list cannot contain libm functions (such as acos and sqrt)
 816 // that set errno on a domain or other error.
 817 static const char *DoesntAccessMemoryFns[] = {
 818   "abs", "labs", "llabs", "imaxabs", "fabs", "fabsf", "fabsl",
 819   "trunc", "truncf", "truncl", "ldexp",
 820
 821   "atan", "atanf", "atanl",   "atan2", "atan2f", "atan2l",
 822   "cbrt",
 823   "cos", "cosf", "cosl",
 824   "exp", "expf", "expl",
 825   "hypot",
 826   "sin", "sinf", "sinl",
 827   "tan", "tanf", "tanl",      "tanh", "tanhf", "tanhl",
 828
 829   "floor", "floorf", "floorl", "ceil", "ceilf", "ceill",
 830
 831   // ctype.h
 832   "isalnum", "isalpha", "iscntrl", "isdigit", "isgraph", "islower", "isprint"
 833   "ispunct", "isspace", "isupper", "isxdigit", "tolower", "toupper",
 834
 835   // wctype.h"
 836   "iswalnum", "iswalpha", "iswcntrl", "iswdigit", "iswgraph", "iswlower",
 837   "iswprint", "iswpunct", "iswspace", "iswupper", "iswxdigit",
 838
 839   "iswctype", "towctrans", "towlower", "towupper",
 840
 841   "btowc", "wctob",
 842
 843   "isinf", "isnan", "finite",
 844
 845   // C99 math functions
 846   "copysign", "copysignf", "copysignd",
 847   "nexttoward", "nexttowardf", "nexttowardd",
 848   "nextafter", "nextafterf", "nextafterd",
 849
 850   // ISO C99:
 851   "__signbit", "__signbitf", "__signbitl",
 852 };
 853
 854
 855 static const char *OnlyReadsMemoryFns[] = {
 856   "atoi", "atol", "atof", "atoll", "atoq", "a64l",
 857   "bcmp", "memcmp", "memchr", "memrchr", "wmemcmp", "wmemchr",
 858
 859   // Strings
 860   "strcmp", "strcasecmp", "strcoll", "strncmp", "strncasecmp",
 861   "strchr", "strcspn", "strlen", "strpbrk", "strrchr", "strspn", "strstr",
 862   "index", "rindex",
 863
 864   // Wide char strings
 865   "wcschr", "wcscmp", "wcscoll", "wcscspn", "wcslen", "wcsncmp", "wcspbrk",
 866   "wcsrchr", "wcsspn", "wcsstr",
 867
 868   // glibc
 869   "alphasort", "alphasort64", "versionsort", "versionsort64",
 870
 871   // C99
 872   "nan", "nanf", "nand",
 873
 874   // File I/O
 875   "feof", "ferror", "fileno",
 876   "feof_unlocked", "ferror_unlocked", "fileno_unlocked"
 877 };
 878
 879 static ManagedStatic<std::vector<const char*> > NoMemoryTable;
 880 static ManagedStatic<std::vector<const char*> > OnlyReadsMemoryTable;
 881
 882 static ManagedStatic<BitVector> NoMemoryIntrinsics;
 883 static ManagedStatic<BitVector> OnlyReadsMemoryIntrinsics;
 884
 885
 886 AliasAnalysis::ModRefBehavior
 887 BasicAliasAnalysis::getModRefBehavior(Function *F, CallSite CS,
 888                                       std::vector<PointerAccessInfo> *Info) {
 889   if (!F->isDeclaration()) return UnknownModRefBehavior;
 890
 891   static bool Initialized = false;
 892   if (!Initialized) {
 893     NoMemoryTable->insert(NoMemoryTable->end(),
 894                           DoesntAccessMemoryFns,
 895                           array_endof(DoesntAccessMemoryFns));
 896
 897     OnlyReadsMemoryTable->insert(OnlyReadsMemoryTable->end(),
 898                                  OnlyReadsMemoryFns,
 899                                  array_endof(OnlyReadsMemoryFns));
 900
 901     // Sort the table the first time through.
 902     std::sort(NoMemoryTable->begin(), NoMemoryTable->end(), StringCompare());
 903     std::sort(OnlyReadsMemoryTable->begin(), OnlyReadsMemoryTable->end(),
 904               StringCompare());
 905
 906     NoMemoryIntrinsics->resize(Intrinsic::num_intrinsics);
 907     OnlyReadsMemoryIntrinsics->resize(Intrinsic::num_intrinsics);
 908 #define GET_MODREF_BEHAVIOR
 909 #include "llvm/Intrinsics.gen"
 910 #undef GET_MODREF_BEHAVIOR
 911
 912     Initialized = true;
 913   }
 914
 915   // If this is an intrinsic, we can use lookup tables
 916   if (unsigned id = F->getIntrinsicID()) {
 917     if (NoMemoryIntrinsics->test(id))
 918       return DoesNotAccessMemory;
 919     if (OnlyReadsMemoryIntrinsics->test(id))
 920       return OnlyReadsMemory;
 921
 922     return UnknownModRefBehavior;
 923   }
 924
 925   ValueName *Name = F->getValueName();
 926   unsigned NameLen = Name->getKeyLength();
 927   const char *NamePtr = Name->getKeyData();
 928
 929   // If there is an embedded nul character in the function name, we can never
 930   // match it.
 931   if (strlen(NamePtr) != NameLen)
 932     return UnknownModRefBehavior;
 933
 934   std::vector<const char*>::iterator Ptr =
 935     std::lower_bound(NoMemoryTable->begin(), NoMemoryTable->end(),
 936                      NamePtr, StringCompare());
 937   if (Ptr != NoMemoryTable->end() && strcmp(*Ptr, NamePtr) == 0)
 938     return DoesNotAccessMemory;
 939
 940   Ptr = std::lower_bound(OnlyReadsMemoryTable->begin(),
 941                          OnlyReadsMemoryTable->end(),
 942                          NamePtr, StringCompare());
 943   if (Ptr != OnlyReadsMemoryTable->end() && strcmp(*Ptr, NamePtr) == 0)
 944     return OnlyReadsMemory;
 945
 946   return UnknownModRefBehavior;
 947 }
 948
 949 // Make sure that anything that uses AliasAnalysis pulls in this file...
 950 DEFINING_FILE_FOR(BasicAliasAnalysis)