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