lib/Analysis/BasicAliasAnalysis.cpp

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