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