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