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,
 115                          Value **GEP1Ops, unsigned NumGEP1Ops, unsigned G1Size,
 116                          const Type *BasePtr2Ty,
 117                          Value **GEP2Ops, unsigned NumGEP2Ops, 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(),
 381                                &GEP1Ops[0], GEP1Ops.size(), V1Size,
 382                                BasePtr2->getType(),
 383                                &GEP2Ops[0], GEP2Ops.size(), 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(),
 442                                                &GEPOperands[0],
 443                                                GEPOperands.size());
 444
 445             if (Offset >= (int64_t)V2Size || Offset <= -(int64_t)V1Size)
 446               return NoAlias;
 447           }
 448         }
 449       }
 450     }
 451
 452   return MayAlias;
 453 }
 454
 455 // This function is used to determin if the indices of two GEP instructions are
 456 // equal. V1 and V2 are the indices.
 457 static bool IndexOperandsEqual(Value *V1, Value *V2) {
 458   if (V1->getType() == V2->getType())
 459     return V1 == V2;
 460   if (Constant *C1 = dyn_cast<Constant>(V1))
 461     if (Constant *C2 = dyn_cast<Constant>(V2)) {
 462       // Sign extend the constants to long types, if necessary
 463       if (C1->getType() != Type::Int64Ty)
 464         C1 = ConstantExpr::getSExt(C1, Type::Int64Ty);
 465       if (C2->getType() != Type::Int64Ty)
 466         C2 = ConstantExpr::getSExt(C2, Type::Int64Ty);
 467       return C1 == C2;
 468     }
 469   return false;
 470 }
 471
 472 /// CheckGEPInstructions - Check two GEP instructions with known must-aliasing
 473 /// base pointers.  This checks to see if the index expressions preclude the
 474 /// pointers from aliasing...
 475 AliasAnalysis::AliasResult
 476 BasicAliasAnalysis::CheckGEPInstructions(
 477   const Type* BasePtr1Ty, Value **GEP1Ops, unsigned NumGEP1Ops, unsigned G1S,
 478   const Type *BasePtr2Ty, Value **GEP2Ops, unsigned NumGEP2Ops, unsigned G2S) {
 479   // We currently can't handle the case when the base pointers have different
 480   // primitive types.  Since this is uncommon anyway, we are happy being
 481   // extremely conservative.
 482   if (BasePtr1Ty != BasePtr2Ty)
 483     return MayAlias;
 484
 485   const PointerType *GEPPointerTy = cast<PointerType>(BasePtr1Ty);
 486
 487   // Find the (possibly empty) initial sequence of equal values... which are not
 488   // necessarily constants.
 489   unsigned NumGEP1Operands = NumGEP1Ops, NumGEP2Operands = NumGEP2Ops;
 490   unsigned MinOperands = std::min(NumGEP1Operands, NumGEP2Operands);
 491   unsigned MaxOperands = std::max(NumGEP1Operands, NumGEP2Operands);
 492   unsigned UnequalOper = 0;
 493   while (UnequalOper != MinOperands &&
 494          IndexOperandsEqual(GEP1Ops[UnequalOper], GEP2Ops[UnequalOper])) {
 495     // Advance through the type as we go...
 496     ++UnequalOper;
 497     if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty))
 498       BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[UnequalOper-1]);
 499     else {
 500       // If all operands equal each other, then the derived pointers must
 501       // alias each other...
 502       BasePtr1Ty = 0;
 503       assert(UnequalOper == NumGEP1Operands && UnequalOper == NumGEP2Operands &&
 504              "Ran out of type nesting, but not out of operands?");
 505       return MustAlias;
 506     }
 507   }
 508
 509   // If we have seen all constant operands, and run out of indexes on one of the
 510   // getelementptrs, check to see if the tail of the leftover one is all zeros.
 511   // If so, return mustalias.
 512   if (UnequalOper == MinOperands) {
 513     if (NumGEP1Ops < NumGEP2Ops) {
 514       std::swap(GEP1Ops, GEP2Ops);
 515       std::swap(NumGEP1Ops, NumGEP2Ops);
 516     }
 517
 518     bool AllAreZeros = true;
 519     for (unsigned i = UnequalOper; i != MaxOperands; ++i)
 520       if (!isa<Constant>(GEP1Ops[i]) ||
 521           !cast<Constant>(GEP1Ops[i])->isNullValue()) {
 522         AllAreZeros = false;
 523         break;
 524       }
 525     if (AllAreZeros) return MustAlias;
 526   }
 527
 528
 529   // So now we know that the indexes derived from the base pointers,
 530   // which are known to alias, are different.  We can still determine a
 531   // no-alias result if there are differing constant pairs in the index
 532   // chain.  For example:
 533   //        A[i][0] != A[j][1] iff (&A[0][1]-&A[0][0] >= std::max(G1S, G2S))
 534   //
 535   // We have to be careful here about array accesses.  In particular, consider:
 536   //        A[1][0] vs A[0][i]
 537   // In this case, we don't *know* that the array will be accessed in bounds:
 538   // the index could even be negative.  Because of this, we have to
 539   // conservatively *give up* and return may alias.  We disregard differing
 540   // array subscripts that are followed by a variable index without going
 541   // through a struct.
 542   //
 543   unsigned SizeMax = std::max(G1S, G2S);
 544   if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work.
 545
 546   // Scan for the first operand that is constant and unequal in the
 547   // two getelementptrs...
 548   unsigned FirstConstantOper = UnequalOper;
 549   for (; FirstConstantOper != MinOperands; ++FirstConstantOper) {
 550     const Value *G1Oper = GEP1Ops[FirstConstantOper];
 551     const Value *G2Oper = GEP2Ops[FirstConstantOper];
 552
 553     if (G1Oper != G2Oper)   // Found non-equal constant indexes...
 554       if (Constant *G1OC = dyn_cast<ConstantInt>(const_cast<Value*>(G1Oper)))
 555         if (Constant *G2OC = dyn_cast<ConstantInt>(const_cast<Value*>(G2Oper))){
 556           if (G1OC->getType() != G2OC->getType()) {
 557             // Sign extend both operands to long.
 558             if (G1OC->getType() != Type::Int64Ty)
 559               G1OC = ConstantExpr::getSExt(G1OC, Type::Int64Ty);
 560             if (G2OC->getType() != Type::Int64Ty)
 561               G2OC = ConstantExpr::getSExt(G2OC, Type::Int64Ty);
 562             GEP1Ops[FirstConstantOper] = G1OC;
 563             GEP2Ops[FirstConstantOper] = G2OC;
 564           }
 565
 566           if (G1OC != G2OC) {
 567             // Handle the "be careful" case above: if this is an array/packed
 568             // subscript, scan for a subsequent variable array index.
 569             if (isa<SequentialType>(BasePtr1Ty))  {
 570               const Type *NextTy =
 571                 cast<SequentialType>(BasePtr1Ty)->getElementType();
 572               bool isBadCase = false;
 573
 574               for (unsigned Idx = FirstConstantOper+1;
 575                    Idx != MinOperands && isa<SequentialType>(NextTy); ++Idx) {
 576                 const Value *V1 = GEP1Ops[Idx], *V2 = GEP2Ops[Idx];
 577                 if (!isa<Constant>(V1) || !isa<Constant>(V2)) {
 578                   isBadCase = true;
 579                   break;
 580                 }
 581                 NextTy = cast<SequentialType>(NextTy)->getElementType();
 582               }
 583
 584               if (isBadCase) G1OC = 0;
 585             }
 586
 587             // Make sure they are comparable (ie, not constant expressions), and
 588             // make sure the GEP with the smaller leading constant is GEP1.
 589             if (G1OC) {
 590               Constant *Compare = ConstantExpr::getICmp(ICmpInst::ICMP_SGT,
 591                                                         G1OC, G2OC);
 592               if (ConstantInt *CV = dyn_cast<ConstantInt>(Compare)) {
 593                 if (CV->getZExtValue()) {  // If they are comparable and G2 > G1
 594                   std::swap(GEP1Ops, GEP2Ops);  // Make GEP1 < GEP2
 595                   std::swap(NumGEP1Ops, NumGEP2Ops);
 596                 }
 597                 break;
 598               }
 599             }
 600           }
 601         }
 602     BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(G1Oper);
 603   }
 604
 605   // No shared constant operands, and we ran out of common operands.  At this
 606   // point, the GEP instructions have run through all of their operands, and we
 607   // haven't found evidence that there are any deltas between the GEP's.
 608   // However, one GEP may have more operands than the other.  If this is the
 609   // case, there may still be hope.  Check this now.
 610   if (FirstConstantOper == MinOperands) {
 611     // Make GEP1Ops be the longer one if there is a longer one.
 612     if (NumGEP1Ops < NumGEP2Ops) {
 613       std::swap(GEP1Ops, GEP2Ops);
 614       std::swap(NumGEP1Ops, NumGEP2Ops);
 615     }
 616
 617     // Is there anything to check?
 618     if (NumGEP1Ops > MinOperands) {
 619       for (unsigned i = FirstConstantOper; i != MaxOperands; ++i)
 620         if (isa<ConstantInt>(GEP1Ops[i]) &&
 621             !cast<Constant>(GEP1Ops[i])->isNullValue()) {
 622           // Yup, there's a constant in the tail.  Set all variables to
 623           // constants in the GEP instruction to make it suiteable for
 624           // TargetData::getIndexedOffset.
 625           for (i = 0; i != MaxOperands; ++i)
 626             if (!isa<ConstantInt>(GEP1Ops[i]))
 627               GEP1Ops[i] = Constant::getNullValue(GEP1Ops[i]->getType());
 628           // Okay, now get the offset.  This is the relative offset for the full
 629           // instruction.
 630           const TargetData &TD = getTargetData();
 631           int64_t Offset1 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops,
 632                                                 NumGEP1Ops);
 633
 634           // Now check without any constants at the end.
 635           int64_t Offset2 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops,
 636                                                 MinOperands);
 637
 638           // If the tail provided a bit enough offset, return noalias!
 639           if ((uint64_t)(Offset2-Offset1) >= SizeMax)
 640             return NoAlias;
 641         }
 642     }
 643
 644     // Couldn't find anything useful.
 645     return MayAlias;
 646   }
 647
 648   // If there are non-equal constants arguments, then we can figure
 649   // out a minimum known delta between the two index expressions... at
 650   // this point we know that the first constant index of GEP1 is less
 651   // than the first constant index of GEP2.
 652
 653   // Advance BasePtr[12]Ty over this first differing constant operand.
 654   BasePtr2Ty = cast<CompositeType>(BasePtr1Ty)->
 655       getTypeAtIndex(GEP2Ops[FirstConstantOper]);
 656   BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->
 657       getTypeAtIndex(GEP1Ops[FirstConstantOper]);
 658
 659   // We are going to be using TargetData::getIndexedOffset to determine the
 660   // offset that each of the GEP's is reaching.  To do this, we have to convert
 661   // all variable references to constant references.  To do this, we convert the
 662   // initial sequence of array subscripts into constant zeros to start with.
 663   const Type *ZeroIdxTy = GEPPointerTy;
 664   for (unsigned i = 0; i != FirstConstantOper; ++i) {
 665     if (!isa<StructType>(ZeroIdxTy))
 666       GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Type::Int32Ty);
 667
 668     if (const CompositeType *CT = dyn_cast<CompositeType>(ZeroIdxTy))
 669       ZeroIdxTy = CT->getTypeAtIndex(GEP1Ops[i]);
 670   }
 671
 672   // We know that GEP1Ops[FirstConstantOper] & GEP2Ops[FirstConstantOper] are ok
 673
 674   // Loop over the rest of the operands...
 675   for (unsigned i = FirstConstantOper+1; i != MaxOperands; ++i) {
 676     const Value *Op1 = i < NumGEP1Ops ? GEP1Ops[i] : 0;
 677     const Value *Op2 = i < NumGEP2Ops ? GEP2Ops[i] : 0;
 678     // If they are equal, use a zero index...
 679     if (Op1 == Op2 && BasePtr1Ty == BasePtr2Ty) {
 680       if (!isa<ConstantInt>(Op1))
 681         GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Op1->getType());
 682       // Otherwise, just keep the constants we have.
 683     } else {
 684       if (Op1) {
 685         if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
 686           // If this is an array index, make sure the array element is in range.
 687           if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) {
 688             if (Op1C->getZExtValue() >= AT->getNumElements())
 689               return MayAlias;  // Be conservative with out-of-range accesses
 690           } else if (const PackedType *PT = dyn_cast<PackedType>(BasePtr1Ty)) {
 691             if (Op1C->getZExtValue() >= PT->getNumElements())
 692               return MayAlias;  // Be conservative with out-of-range accesses
 693           }
 694
 695         } else {
 696           // GEP1 is known to produce a value less than GEP2.  To be
 697           // conservatively correct, we must assume the largest possible
 698           // constant is used in this position.  This cannot be the initial
 699           // index to the GEP instructions (because we know we have at least one
 700           // element before this one with the different constant arguments), so
 701           // we know that the current index must be into either a struct or
 702           // array.  Because we know it's not constant, this cannot be a
 703           // structure index.  Because of this, we can calculate the maximum
 704           // value possible.
 705           //
 706           if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
 707             GEP1Ops[i] = ConstantInt::get(Type::Int64Ty,AT->getNumElements()-1);
 708           else if (const PackedType *PT = dyn_cast<PackedType>(BasePtr1Ty))
 709             GEP1Ops[i] = ConstantInt::get(Type::Int64Ty,PT->getNumElements()-1);
 710
 711         }
 712       }
 713
 714       if (Op2) {
 715         if (const ConstantInt *Op2C = dyn_cast<ConstantInt>(Op2)) {
 716           // If this is an array index, make sure the array element is in range.
 717           if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) {
 718             if (Op2C->getZExtValue() >= AT->getNumElements())
 719               return MayAlias;  // Be conservative with out-of-range accesses
 720           } else if (const PackedType *PT = dyn_cast<PackedType>(BasePtr1Ty)) {
 721             if (Op2C->getZExtValue() >= PT->getNumElements())
 722               return MayAlias;  // Be conservative with out-of-range accesses
 723           }
 724         } else {  // Conservatively assume the minimum value for this index
 725           GEP2Ops[i] = Constant::getNullValue(Op2->getType());
 726         }
 727       }
 728     }
 729
 730     if (BasePtr1Ty && Op1) {
 731       if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty))
 732         BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[i]);
 733       else
 734         BasePtr1Ty = 0;
 735     }
 736
 737     if (BasePtr2Ty && Op2) {
 738       if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr2Ty))
 739         BasePtr2Ty = CT->getTypeAtIndex(GEP2Ops[i]);
 740       else
 741         BasePtr2Ty = 0;
 742     }
 743   }
 744
 745   if (GEPPointerTy->getElementType()->isSized()) {
 746     int64_t Offset1 =
 747       getTargetData().getIndexedOffset(GEPPointerTy, GEP1Ops, NumGEP1Ops);
 748     int64_t Offset2 =
 749       getTargetData().getIndexedOffset(GEPPointerTy, GEP2Ops, NumGEP2Ops);
 750     assert(Offset1<Offset2 && "There is at least one different constant here!");
 751
 752     if ((uint64_t)(Offset2-Offset1) >= SizeMax) {
 753       //cerr << "Determined that these two GEP's don't alias ["
 754       //     << SizeMax << " bytes]: \n" << *GEP1 << *GEP2;
 755       return NoAlias;
 756     }
 757   }
 758   return MayAlias;
 759 }
 760
 761 namespace {
 762   struct VISIBILITY_HIDDEN StringCompare {
 763     bool operator()(const char *LHS, const char *RHS) {
 764       return strcmp(LHS, RHS) < 0;
 765     }
 766   };
 767 }
 768
 769 // Note that this list cannot contain libm functions (such as acos and sqrt)
 770 // that set errno on a domain or other error.
 771 static const char *DoesntAccessMemoryFns[] = {
 772   "abs", "labs", "llabs", "imaxabs", "fabs", "fabsf", "fabsl",
 773   "trunc", "truncf", "truncl", "ldexp",
 774
 775   "atan", "atanf", "atanl",   "atan2", "atan2f", "atan2l",
 776   "cbrt",
 777   "cos", "cosf", "cosl",
 778   "exp", "expf", "expl",
 779   "hypot",
 780   "sin", "sinf", "sinl",
 781   "tan", "tanf", "tanl",      "tanh", "tanhf", "tanhl",
 782
 783   "floor", "floorf", "floorl", "ceil", "ceilf", "ceill",
 784
 785   // ctype.h
 786   "isalnum", "isalpha", "iscntrl", "isdigit", "isgraph", "islower", "isprint"
 787   "ispunct", "isspace", "isupper", "isxdigit", "tolower", "toupper",
 788
 789   // wctype.h"
 790   "iswalnum", "iswalpha", "iswcntrl", "iswdigit", "iswgraph", "iswlower",
 791   "iswprint", "iswpunct", "iswspace", "iswupper", "iswxdigit",
 792
 793   "iswctype", "towctrans", "towlower", "towupper",
 794
 795   "btowc", "wctob",
 796
 797   "isinf", "isnan", "finite",
 798
 799   // C99 math functions
 800   "copysign", "copysignf", "copysignd",
 801   "nexttoward", "nexttowardf", "nexttowardd",
 802   "nextafter", "nextafterf", "nextafterd",
 803
 804   // ISO C99:
 805   "__signbit", "__signbitf", "__signbitl",
 806 };
 807
 808
 809 static const char *OnlyReadsMemoryFns[] = {
 810   "atoi", "atol", "atof", "atoll", "atoq", "a64l",
 811   "bcmp", "memcmp", "memchr", "memrchr", "wmemcmp", "wmemchr",
 812
 813   // Strings
 814   "strcmp", "strcasecmp", "strcoll", "strncmp", "strncasecmp",
 815   "strchr", "strcspn", "strlen", "strpbrk", "strrchr", "strspn", "strstr",
 816   "index", "rindex",
 817
 818   // Wide char strings
 819   "wcschr", "wcscmp", "wcscoll", "wcscspn", "wcslen", "wcsncmp", "wcspbrk",
 820   "wcsrchr", "wcsspn", "wcsstr",
 821
 822   // glibc
 823   "alphasort", "alphasort64", "versionsort", "versionsort64",
 824
 825   // C99
 826   "nan", "nanf", "nand",
 827
 828   // File I/O
 829   "feof", "ferror", "fileno",
 830   "feof_unlocked", "ferror_unlocked", "fileno_unlocked"
 831 };
 832
 833 static ManagedStatic<std::vector<const char*> > NoMemoryTable;
 834 static ManagedStatic<std::vector<const char*> > OnlyReadsMemoryTable;
 835
 836
 837 AliasAnalysis::ModRefBehavior
 838 BasicAliasAnalysis::getModRefBehavior(Function *F, CallSite CS,
 839                                       std::vector<PointerAccessInfo> *Info) {
 840   if (!F->isDeclaration()) return UnknownModRefBehavior;
 841
 842   static bool Initialized = false;
 843   if (!Initialized) {
 844     NoMemoryTable->insert(NoMemoryTable->end(),
 845                           DoesntAccessMemoryFns,
 846                           DoesntAccessMemoryFns+
 847                 sizeof(DoesntAccessMemoryFns)/sizeof(DoesntAccessMemoryFns[0]));
 848
 849     OnlyReadsMemoryTable->insert(OnlyReadsMemoryTable->end(),
 850                                 OnlyReadsMemoryFns,
 851                                 OnlyReadsMemoryFns+
 852                       sizeof(OnlyReadsMemoryFns)/sizeof(OnlyReadsMemoryFns[0]));
 853 #define GET_MODREF_BEHAVIOR
 854 #include "llvm/Intrinsics.gen"
 855 #undef GET_MODREF_BEHAVIOR
 856
 857     // Sort the table the first time through.
 858     std::sort(NoMemoryTable->begin(), NoMemoryTable->end(), StringCompare());
 859     std::sort(OnlyReadsMemoryTable->begin(), OnlyReadsMemoryTable->end(),
 860               StringCompare());
 861     Initialized = true;
 862   }
 863
 864   std::vector<const char*>::iterator Ptr =
 865     std::lower_bound(NoMemoryTable->begin(), NoMemoryTable->end(),
 866                      F->getName().c_str(), StringCompare());
 867   if (Ptr != NoMemoryTable->end() && *Ptr == F->getName())
 868     return DoesNotAccessMemory;
 869
 870   Ptr = std::lower_bound(OnlyReadsMemoryTable->begin(),
 871                          OnlyReadsMemoryTable->end(),
 872                          F->getName().c_str(), StringCompare());
 873   if (Ptr != OnlyReadsMemoryTable->end() && *Ptr == F->getName())
 874     return OnlyReadsMemory;
 875
 876   return UnknownModRefBehavior;
 877 }
 878
 879 // Make sure that anything that uses AliasAnalysis pulls in this file...
 880 DEFINING_FILE_FOR(BasicAliasAnalysis)