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