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