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