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