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