lib/Analysis/BasicAliasAnalysis.cpp

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