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