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