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