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