lib/Analysis/BasicAliasAnalysis.cpp

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