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