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