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