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