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 // hasUniqueAddress - Return true if the specified value points to something
 133 // with a unique, discernable, address.
 134 static inline bool hasUniqueAddress(const Value *V) {
 135   return isa<GlobalValue>(V) || isa<AllocationInst>(V);
 136 }
 137
 138 // getUnderlyingObject - This traverses the use chain to figure out what object
 139 // the specified value points to.  If the value points to, or is derived from, a
 140 // unique object or an argument, return it.
 141 static const Value *getUnderlyingObject(const Value *V) {
 142   if (!isa<PointerType>(V->getType())) return 0;
 143
 144   // If we are at some type of object... return it.
 145   if (hasUniqueAddress(V) || isa<Argument>(V)) return V;
 146
 147   // Traverse through different addressing mechanisms...
 148   if (const Instruction *I = dyn_cast<Instruction>(V)) {
 149     if (isa<CastInst>(I) || isa<GetElementPtrInst>(I))
 150       return getUnderlyingObject(I->getOperand(0));
 151   } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
 152     if (CE->getOpcode() == Instruction::Cast ||
 153         CE->getOpcode() == Instruction::GetElementPtr)
 154       return getUnderlyingObject(CE->getOperand(0));
 155   } else if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
 156     return GV;
 157   }
 158   return 0;
 159 }
 160
 161 static const User *isGEP(const Value *V) {
 162   if (isa<GetElementPtrInst>(V) ||
 163       (isa<ConstantExpr>(V) &&
 164        cast<ConstantExpr>(V)->getOpcode() == Instruction::GetElementPtr))
 165     return cast<User>(V);
 166   return 0;
 167 }
 168
 169 static const Value *GetGEPOperands(const Value *V, std::vector<Value*> &GEPOps){
 170   assert(GEPOps.empty() && "Expect empty list to populate!");
 171   GEPOps.insert(GEPOps.end(), cast<User>(V)->op_begin()+1,
 172                 cast<User>(V)->op_end());
 173
 174   // Accumulate all of the chained indexes into the operand array
 175   V = cast<User>(V)->getOperand(0);
 176
 177   while (const User *G = isGEP(V)) {
 178     if (!isa<Constant>(GEPOps[0]) || isa<GlobalValue>(GEPOps[0]) ||
 179         !cast<Constant>(GEPOps[0])->isNullValue())
 180       break;  // Don't handle folding arbitrary pointer offsets yet...
 181     GEPOps.erase(GEPOps.begin());   // Drop the zero index
 182     GEPOps.insert(GEPOps.begin(), G->op_begin()+1, G->op_end());
 183     V = G->getOperand(0);
 184   }
 185   return V;
 186 }
 187
 188 /// pointsToConstantMemory - Chase pointers until we find a (constant
 189 /// global) or not.
 190 bool BasicAliasAnalysis::pointsToConstantMemory(const Value *P) {
 191   if (const Value *V = getUnderlyingObject(P))
 192     if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
 193       return GV->isConstant();
 194   return false;
 195 }
 196
 197 static bool AddressMightEscape(const Value *V) {
 198   for (Value::use_const_iterator UI = V->use_begin(), E = V->use_end();
 199        UI != E; ++UI) {
 200     const Instruction *I = cast<Instruction>(*UI);
 201     switch (I->getOpcode()) {
 202     case Instruction::Load: break;
 203     case Instruction::Store:
 204       if (I->getOperand(0) == V)
 205         return true; // Escapes if the pointer is stored.
 206       break;
 207     case Instruction::GetElementPtr:
 208       if (AddressMightEscape(I)) return true;
 209       break;
 210     case Instruction::Cast:
 211       if (!isa<PointerType>(I->getType()))
 212         return true;
 213       if (AddressMightEscape(I)) return true;
 214       break;
 215     case Instruction::Ret:
 216       // If returned, the address will escape to calling functions, but no
 217       // callees could modify it.
 218       break;
 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->getOpcode() == Instruction::Cast &&
 263         isa<PointerType>(CE->getOperand(0)->getType()))
 264       V1 = CE->getOperand(0);
 265   if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V2))
 266     if (CE->getOpcode() == Instruction::Cast &&
 267         isa<PointerType>(CE->getOperand(0)->getType()))
 268       V2 = CE->getOperand(0);
 269
 270   // Are we checking for alias of the same value?
 271   if (V1 == V2) return MustAlias;
 272
 273   if ((!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType())) &&
 274       V1->getType() != Type::LongTy && V2->getType() != Type::LongTy)
 275     return NoAlias;  // Scalars cannot alias each other
 276
 277   // Strip off cast instructions...
 278   if (const Instruction *I = dyn_cast<CastInst>(V1))
 279     if (isa<PointerType>(I->getOperand(0)->getType()))
 280       return alias(I->getOperand(0), V1Size, V2, V2Size);
 281   if (const Instruction *I = dyn_cast<CastInst>(V2))
 282     if (isa<PointerType>(I->getOperand(0)->getType()))
 283       return alias(V1, V1Size, I->getOperand(0), V2Size);
 284
 285   // Figure out what objects these things are pointing to if we can...
 286   const Value *O1 = getUnderlyingObject(V1);
 287   const Value *O2 = getUnderlyingObject(V2);
 288
 289   // Pointing at a discernible object?
 290   if (O1) {
 291     if (O2) {
 292       if (isa<Argument>(O1)) {
 293         // Incoming argument cannot alias locally allocated object!
 294         if (isa<AllocationInst>(O2)) return NoAlias;
 295         // Otherwise, nothing is known...
 296       } else if (isa<Argument>(O2)) {
 297         // Incoming argument cannot alias locally allocated object!
 298         if (isa<AllocationInst>(O1)) return NoAlias;
 299         // Otherwise, nothing is known...
 300       } else if (O1 != O2) {
 301         // If they are two different objects, we know that we have no alias...
 302         return NoAlias;
 303       }
 304
 305       // If they are the same object, they we can look at the indexes.  If they
 306       // index off of the object is the same for both pointers, they must alias.
 307       // If they are provably different, they must not alias.  Otherwise, we
 308       // can't tell anything.
 309     }
 310
 311
 312     if (!isa<Argument>(O1) && isa<ConstantPointerNull>(V2))
 313       return NoAlias;                    // Unique values don't alias null
 314
 315     if (isa<GlobalVariable>(O1) ||
 316         (isa<AllocationInst>(O1) &&
 317          !cast<AllocationInst>(O1)->isArrayAllocation()))
 318       if (cast<PointerType>(O1->getType())->getElementType()->isSized()) {
 319         // If the size of the other access is larger than the total size of the
 320         // global/alloca/malloc, it cannot be accessing the global (it's
 321         // undefined to load or store bytes before or after an object).
 322         const Type *ElTy = cast<PointerType>(O1->getType())->getElementType();
 323         unsigned GlobalSize = getTargetData().getTypeSize(ElTy);
 324         if (GlobalSize < V2Size && V2Size != ~0U)
 325           return NoAlias;
 326       }
 327   }
 328
 329   if (O2) {
 330     if (!isa<Argument>(O2) && isa<ConstantPointerNull>(V1))
 331       return NoAlias;                    // Unique values don't alias null
 332
 333     if (isa<GlobalVariable>(O2) ||
 334         (isa<AllocationInst>(O2) &&
 335          !cast<AllocationInst>(O2)->isArrayAllocation()))
 336       if (cast<PointerType>(O2->getType())->getElementType()->isSized()) {
 337         // If the size of the other access is larger than the total size of the
 338         // global/alloca/malloc, it cannot be accessing the object (it's
 339         // undefined to load or store bytes before or after an object).
 340         const Type *ElTy = cast<PointerType>(O2->getType())->getElementType();
 341         unsigned GlobalSize = getTargetData().getTypeSize(ElTy);
 342         if (GlobalSize < V1Size && V1Size != ~0U)
 343           return NoAlias;
 344       }
 345   }
 346
 347   // If we have two gep instructions with must-alias'ing base pointers, figure
 348   // out if the indexes to the GEP tell us anything about the derived pointer.
 349   // Note that we also handle chains of getelementptr instructions as well as
 350   // constant expression getelementptrs here.
 351   //
 352   if (isGEP(V1) && isGEP(V2)) {
 353     // Drill down into the first non-gep value, to test for must-aliasing of
 354     // the base pointers.
 355     const Value *BasePtr1 = V1, *BasePtr2 = V2;
 356     do {
 357       BasePtr1 = cast<User>(BasePtr1)->getOperand(0);
 358     } while (isGEP(BasePtr1) &&
 359              cast<User>(BasePtr1)->getOperand(1) ==
 360        Constant::getNullValue(cast<User>(BasePtr1)->getOperand(1)->getType()));
 361     do {
 362       BasePtr2 = cast<User>(BasePtr2)->getOperand(0);
 363     } while (isGEP(BasePtr2) &&
 364              cast<User>(BasePtr2)->getOperand(1) ==
 365        Constant::getNullValue(cast<User>(BasePtr2)->getOperand(1)->getType()));
 366
 367     // Do the base pointers alias?
 368     AliasResult BaseAlias = alias(BasePtr1, V1Size, BasePtr2, V2Size);
 369     if (BaseAlias == NoAlias) return NoAlias;
 370     if (BaseAlias == MustAlias) {
 371       // If the base pointers alias each other exactly, check to see if we can
 372       // figure out anything about the resultant pointers, to try to prove
 373       // non-aliasing.
 374
 375       // Collect all of the chained GEP operands together into one simple place
 376       std::vector<Value*> GEP1Ops, GEP2Ops;
 377       BasePtr1 = GetGEPOperands(V1, GEP1Ops);
 378       BasePtr2 = GetGEPOperands(V2, GEP2Ops);
 379
 380       // If GetGEPOperands were able to fold to the same must-aliased pointer,
 381       // do the comparison.
 382       if (BasePtr1 == BasePtr2) {
 383         AliasResult GAlias =
 384           CheckGEPInstructions(BasePtr1->getType(), GEP1Ops, V1Size,
 385                                BasePtr2->getType(), GEP2Ops, V2Size);
 386         if (GAlias != MayAlias)
 387           return GAlias;
 388       }
 389     }
 390   }
 391
 392   // Check to see if these two pointers are related by a getelementptr
 393   // instruction.  If one pointer is a GEP with a non-zero index of the other
 394   // pointer, we know they cannot alias.
 395   //
 396   if (isGEP(V2)) {
 397     std::swap(V1, V2);
 398     std::swap(V1Size, V2Size);
 399   }
 400
 401   if (V1Size != ~0U && V2Size != ~0U)
 402     if (isGEP(V1)) {
 403       std::vector<Value*> GEPOperands;
 404       const Value *BasePtr = GetGEPOperands(V1, GEPOperands);
 405
 406       AliasResult R = alias(BasePtr, V1Size, V2, V2Size);
 407       if (R == MustAlias) {
 408         // If there is at least one non-zero constant index, we know they cannot
 409         // alias.
 410         bool ConstantFound = false;
 411         bool AllZerosFound = true;
 412         for (unsigned i = 0, e = GEPOperands.size(); i != e; ++i)
 413           if (const Constant *C = dyn_cast<Constant>(GEPOperands[i])) {
 414             if (!C->isNullValue()) {
 415               ConstantFound = true;
 416               AllZerosFound = false;
 417               break;
 418             }
 419           } else {
 420             AllZerosFound = false;
 421           }
 422
 423         // If we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 must aliases
 424         // the ptr, the end result is a must alias also.
 425         if (AllZerosFound)
 426           return MustAlias;
 427
 428         if (ConstantFound) {
 429           if (V2Size <= 1 && V1Size <= 1)  // Just pointer check?
 430             return NoAlias;
 431
 432           // Otherwise we have to check to see that the distance is more than
 433           // the size of the argument... build an index vector that is equal to
 434           // the arguments provided, except substitute 0's for any variable
 435           // indexes we find...
 436           if (cast<PointerType>(
 437                 BasePtr->getType())->getElementType()->isSized()) {
 438             for (unsigned i = 0; i != GEPOperands.size(); ++i)
 439               if (!isa<ConstantInt>(GEPOperands[i]))
 440                 GEPOperands[i] =
 441                   Constant::getNullValue(GEPOperands[i]->getType());
 442             int64_t Offset =
 443               getTargetData().getIndexedOffset(BasePtr->getType(), GEPOperands);
 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 static bool ValuesEqual(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.
 461       C1 = ConstantExpr::getSignExtend(C1, Type::LongTy);
 462       C2 = ConstantExpr::getSignExtend(C2, Type::LongTy);
 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          ValuesEqual(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             G1OC = ConstantExpr::getSignExtend(G1OC, Type::LongTy);
 552             G2OC = ConstantExpr::getSignExtend(G2OC, Type::LongTy);
 553             GEP1Ops[FirstConstantOper] = G1OC;
 554             GEP2Ops[FirstConstantOper] = G2OC;
 555           }
 556
 557           if (G1OC != G2OC) {
 558             // Handle the "be careful" case above: if this is an array
 559             // subscript, scan for a subsequent variable array index.
 560             if (isa<ArrayType>(BasePtr1Ty))  {
 561               const Type *NextTy =cast<ArrayType>(BasePtr1Ty)->getElementType();
 562               bool isBadCase = false;
 563
 564               for (unsigned Idx = FirstConstantOper+1;
 565                    Idx != MinOperands && isa<ArrayType>(NextTy); ++Idx) {
 566                 const Value *V1 = GEP1Ops[Idx], *V2 = GEP2Ops[Idx];
 567                 if (!isa<Constant>(V1) || !isa<Constant>(V2)) {
 568                   isBadCase = true;
 569                   break;
 570                 }
 571                 NextTy = cast<ArrayType>(NextTy)->getElementType();
 572               }
 573
 574               if (isBadCase) G1OC = 0;
 575             }
 576
 577             // Make sure they are comparable (ie, not constant expressions), and
 578             // make sure the GEP with the smaller leading constant is GEP1.
 579             if (G1OC) {
 580               Constant *Compare = ConstantExpr::getSetGT(G1OC, G2OC);
 581               if (ConstantBool *CV = dyn_cast<ConstantBool>(Compare)) {
 582                 if (CV->getValue())   // If they are comparable and G2 > G1
 583                   std::swap(GEP1Ops, GEP2Ops);  // Make GEP1 < GEP2
 584                 break;
 585               }
 586             }
 587           }
 588         }
 589     BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(G1Oper);
 590   }
 591
 592   // No shared constant operands, and we ran out of common operands.  At this
 593   // point, the GEP instructions have run through all of their operands, and we
 594   // haven't found evidence that there are any deltas between the GEP's.
 595   // However, one GEP may have more operands than the other.  If this is the
 596   // case, there may still be hope.  Check this now.
 597   if (FirstConstantOper == MinOperands) {
 598     // Make GEP1Ops be the longer one if there is a longer one.
 599     if (GEP1Ops.size() < GEP2Ops.size())
 600       std::swap(GEP1Ops, GEP2Ops);
 601
 602     // Is there anything to check?
 603     if (GEP1Ops.size() > MinOperands) {
 604       for (unsigned i = FirstConstantOper; i != MaxOperands; ++i)
 605         if (isa<ConstantInt>(GEP1Ops[i]) &&
 606             !cast<Constant>(GEP1Ops[i])->isNullValue()) {
 607           // Yup, there's a constant in the tail.  Set all variables to
 608           // constants in the GEP instruction to make it suiteable for
 609           // TargetData::getIndexedOffset.
 610           for (i = 0; i != MaxOperands; ++i)
 611             if (!isa<ConstantInt>(GEP1Ops[i]))
 612               GEP1Ops[i] = Constant::getNullValue(GEP1Ops[i]->getType());
 613           // Okay, now get the offset.  This is the relative offset for the full
 614           // instruction.
 615           const TargetData &TD = getTargetData();
 616           int64_t Offset1 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops);
 617
 618           // Now crop off any constants from the end...
 619           GEP1Ops.resize(MinOperands);
 620           int64_t Offset2 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops);
 621
 622           // If the tail provided a bit enough offset, return noalias!
 623           if ((uint64_t)(Offset2-Offset1) >= SizeMax)
 624             return NoAlias;
 625         }
 626     }
 627
 628     // Couldn't find anything useful.
 629     return MayAlias;
 630   }
 631
 632   // If there are non-equal constants arguments, then we can figure
 633   // out a minimum known delta between the two index expressions... at
 634   // this point we know that the first constant index of GEP1 is less
 635   // than the first constant index of GEP2.
 636
 637   // Advance BasePtr[12]Ty over this first differing constant operand.
 638   BasePtr2Ty = cast<CompositeType>(BasePtr1Ty)->
 639       getTypeAtIndex(GEP2Ops[FirstConstantOper]);
 640   BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->
 641       getTypeAtIndex(GEP1Ops[FirstConstantOper]);
 642
 643   // We are going to be using TargetData::getIndexedOffset to determine the
 644   // offset that each of the GEP's is reaching.  To do this, we have to convert
 645   // all variable references to constant references.  To do this, we convert the
 646   // initial sequence of array subscripts into constant zeros to start with.
 647   const Type *ZeroIdxTy = GEPPointerTy;
 648   for (unsigned i = 0; i != FirstConstantOper; ++i) {
 649     if (!isa<StructType>(ZeroIdxTy))
 650       GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Type::UIntTy);
 651
 652     if (const CompositeType *CT = dyn_cast<CompositeType>(ZeroIdxTy))
 653       ZeroIdxTy = CT->getTypeAtIndex(GEP1Ops[i]);
 654   }
 655
 656   // We know that GEP1Ops[FirstConstantOper] & GEP2Ops[FirstConstantOper] are ok
 657
 658   // Loop over the rest of the operands...
 659   for (unsigned i = FirstConstantOper+1; i != MaxOperands; ++i) {
 660     const Value *Op1 = i < GEP1Ops.size() ? GEP1Ops[i] : 0;
 661     const Value *Op2 = i < GEP2Ops.size() ? GEP2Ops[i] : 0;
 662     // If they are equal, use a zero index...
 663     if (Op1 == Op2 && BasePtr1Ty == BasePtr2Ty) {
 664       if (!isa<ConstantInt>(Op1))
 665         GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Op1->getType());
 666       // Otherwise, just keep the constants we have.
 667     } else {
 668       if (Op1) {
 669         if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
 670           // If this is an array index, make sure the array element is in range.
 671           if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
 672             if (Op1C->getZExtValue() >= AT->getNumElements())
 673               return MayAlias;  // Be conservative with out-of-range accesses
 674
 675         } else {
 676           // GEP1 is known to produce a value less than GEP2.  To be
 677           // conservatively correct, we must assume the largest possible
 678           // constant is used in this position.  This cannot be the initial
 679           // index to the GEP instructions (because we know we have at least one
 680           // element before this one with the different constant arguments), so
 681           // we know that the current index must be into either a struct or
 682           // array.  Because we know it's not constant, this cannot be a
 683           // structure index.  Because of this, we can calculate the maximum
 684           // value possible.
 685           //
 686           if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
 687             GEP1Ops[i] = ConstantInt::get(Type::LongTy, AT->getNumElements()-1);
 688         }
 689       }
 690
 691       if (Op2) {
 692         if (const ConstantInt *Op2C = dyn_cast<ConstantInt>(Op2)) {
 693           // If this is an array index, make sure the array element is in range.
 694           if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
 695             if (Op2C->getZExtValue() >= AT->getNumElements())
 696               return MayAlias;  // Be conservative with out-of-range accesses
 697         } else {  // Conservatively assume the minimum value for this index
 698           GEP2Ops[i] = Constant::getNullValue(Op2->getType());
 699         }
 700       }
 701     }
 702
 703     if (BasePtr1Ty && Op1) {
 704       if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty))
 705         BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[i]);
 706       else
 707         BasePtr1Ty = 0;
 708     }
 709
 710     if (BasePtr2Ty && Op2) {
 711       if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr2Ty))
 712         BasePtr2Ty = CT->getTypeAtIndex(GEP2Ops[i]);
 713       else
 714         BasePtr2Ty = 0;
 715     }
 716   }
 717
 718   if (GEPPointerTy->getElementType()->isSized()) {
 719     int64_t Offset1 = getTargetData().getIndexedOffset(GEPPointerTy, GEP1Ops);
 720     int64_t Offset2 = getTargetData().getIndexedOffset(GEPPointerTy, GEP2Ops);
 721     assert(Offset1<Offset2 && "There is at least one different constant here!");
 722
 723     if ((uint64_t)(Offset2-Offset1) >= SizeMax) {
 724       //std::cerr << "Determined that these two GEP's don't alias ["
 725       //          << SizeMax << " bytes]: \n" << *GEP1 << *GEP2;
 726       return NoAlias;
 727     }
 728   }
 729   return MayAlias;
 730 }
 731
 732 namespace {
 733   struct StringCompare {
 734     bool operator()(const char *LHS, const char *RHS) {
 735       return strcmp(LHS, RHS) < 0;
 736     }
 737   };
 738 }
 739
 740 // Note that this list cannot contain libm functions (such as acos and sqrt)
 741 // that set errno on a domain or other error.
 742 static const char *DoesntAccessMemoryFns[] = {
 743   "abs", "labs", "llabs", "imaxabs", "fabs", "fabsf", "fabsl",
 744   "trunc", "truncf", "truncl", "ldexp",
 745
 746   "atan", "atanf", "atanl",   "atan2", "atan2f", "atan2l",
 747   "cbrt",
 748   "cos", "cosf", "cosl",
 749   "exp", "expf", "expl",
 750   "hypot",
 751   "sin", "sinf", "sinl",
 752   "tan", "tanf", "tanl",      "tanh", "tanhf", "tanhl",
 753
 754   "floor", "floorf", "floorl", "ceil", "ceilf", "ceill",
 755
 756   // ctype.h
 757   "isalnum", "isalpha", "iscntrl", "isdigit", "isgraph", "islower", "isprint"
 758   "ispunct", "isspace", "isupper", "isxdigit", "tolower", "toupper",
 759
 760   // wctype.h"
 761   "iswalnum", "iswalpha", "iswcntrl", "iswdigit", "iswgraph", "iswlower",
 762   "iswprint", "iswpunct", "iswspace", "iswupper", "iswxdigit",
 763
 764   "iswctype", "towctrans", "towlower", "towupper",
 765
 766   "btowc", "wctob",
 767
 768   "isinf", "isnan", "finite",
 769
 770   // C99 math functions
 771   "copysign", "copysignf", "copysignd",
 772   "nexttoward", "nexttowardf", "nexttowardd",
 773   "nextafter", "nextafterf", "nextafterd",
 774
 775   // ISO C99:
 776   "__signbit", "__signbitf", "__signbitl",
 777 };
 778
 779
 780 static const char *OnlyReadsMemoryFns[] = {
 781   "atoi", "atol", "atof", "atoll", "atoq", "a64l",
 782   "bcmp", "memcmp", "memchr", "memrchr", "wmemcmp", "wmemchr",
 783
 784   // Strings
 785   "strcmp", "strcasecmp", "strcoll", "strncmp", "strncasecmp",
 786   "strchr", "strcspn", "strlen", "strpbrk", "strrchr", "strspn", "strstr",
 787   "index", "rindex",
 788
 789   // Wide char strings
 790   "wcschr", "wcscmp", "wcscoll", "wcscspn", "wcslen", "wcsncmp", "wcspbrk",
 791   "wcsrchr", "wcsspn", "wcsstr",
 792
 793   // glibc
 794   "alphasort", "alphasort64", "versionsort", "versionsort64",
 795
 796   // C99
 797   "nan", "nanf", "nand",
 798
 799   // File I/O
 800   "feof", "ferror", "fileno",
 801   "feof_unlocked", "ferror_unlocked", "fileno_unlocked"
 802 };
 803
 804 static ManagedStatic<std::vector<const char*> > NoMemoryTable;
 805 static ManagedStatic<std::vector<const char*> > OnlyReadsMemoryTable;
 806
 807
 808 AliasAnalysis::ModRefBehavior
 809 BasicAliasAnalysis::getModRefBehavior(Function *F, CallSite CS,
 810                                       std::vector<PointerAccessInfo> *Info) {
 811   if (!F->isExternal()) return UnknownModRefBehavior;
 812
 813   static bool Initialized = false;
 814   if (!Initialized) {
 815     NoMemoryTable->insert(NoMemoryTable->end(),
 816                           DoesntAccessMemoryFns,
 817                           DoesntAccessMemoryFns+
 818                 sizeof(DoesntAccessMemoryFns)/sizeof(DoesntAccessMemoryFns[0]));
 819
 820     OnlyReadsMemoryTable->insert(OnlyReadsMemoryTable->end(),
 821                                 OnlyReadsMemoryFns,
 822                                 OnlyReadsMemoryFns+
 823                       sizeof(OnlyReadsMemoryFns)/sizeof(OnlyReadsMemoryFns[0]));
 824 #define GET_MODREF_BEHAVIOR
 825 #include "llvm/Intrinsics.gen"
 826 #undef GET_MODREF_BEHAVIOR
 827
 828     // Sort the table the first time through.
 829     std::sort(NoMemoryTable->begin(), NoMemoryTable->end(), StringCompare());
 830     std::sort(OnlyReadsMemoryTable->begin(), OnlyReadsMemoryTable->end(),
 831               StringCompare());
 832     Initialized = true;
 833   }
 834
 835   std::vector<const char*>::iterator Ptr =
 836     std::lower_bound(NoMemoryTable->begin(), NoMemoryTable->end(),
 837                      F->getName().c_str(), StringCompare());
 838   if (Ptr != NoMemoryTable->end() && *Ptr == F->getName())
 839     return DoesNotAccessMemory;
 840
 841   Ptr = std::lower_bound(OnlyReadsMemoryTable->begin(),
 842                          OnlyReadsMemoryTable->end(),
 843                          F->getName().c_str(), StringCompare());
 844   if (Ptr != OnlyReadsMemoryTable->end() && *Ptr == F->getName())
 845     return OnlyReadsMemory;
 846
 847   return UnknownModRefBehavior;
 848 }
 849
 850 // Make sure that anything that uses AliasAnalysis pulls in this file...
 851 DEFINING_FILE_FOR(BasicAliasAnalysis)