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