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/Pass.h"
  18 #include "llvm/Argument.h"
  19 #include "llvm/iOther.h"
  20 #include "llvm/ConstantHandling.h"
  21 #include "llvm/GlobalValue.h"
  22 #include "llvm/DerivedTypes.h"
  23 #include "llvm/Target/TargetData.h"
  24 #include "llvm/Support/GetElementPtrTypeIterator.h"
  25 using namespace llvm;
  26
  27 // Make sure that anything that uses AliasAnalysis pulls in this file...
  28 namespace llvm { void BasicAAStub() {} }
  29
  30 namespace {
  31   struct BasicAliasAnalysis : public ImmutablePass, public AliasAnalysis {
  32
  33     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  34       AliasAnalysis::getAnalysisUsage(AU);
  35     }
  36
  37     virtual void initializePass();
  38
  39     // alias - This is the only method here that does anything interesting...
  40     //
  41     AliasResult alias(const Value *V1, unsigned V1Size,
  42                       const Value *V2, unsigned V2Size);
  43   private:
  44     // CheckGEPInstructions - Check two GEP instructions of compatible types and
  45     // equal number of arguments.  This checks to see if the index expressions
  46     // preclude the pointers from aliasing...
  47     AliasResult CheckGEPInstructions(GetElementPtrInst *GEP1, unsigned G1Size,
  48                                      GetElementPtrInst *GEP2, unsigned G2Size);
  49   };
  50
  51   // Register this pass...
  52   RegisterOpt<BasicAliasAnalysis>
  53   X("basicaa", "Basic Alias Analysis (default AA impl)");
  54
  55   // Declare that we implement the AliasAnalysis interface
  56   RegisterAnalysisGroup<AliasAnalysis, BasicAliasAnalysis, true> Y;
  57 }  // End of anonymous namespace
  58
  59 void BasicAliasAnalysis::initializePass() {
  60   InitializeAliasAnalysis(this);
  61 }
  62
  63 // hasUniqueAddress - Return true if the specified value points to something
  64 // with a unique, discernable, address.
  65 static inline bool hasUniqueAddress(const Value *V) {
  66   return isa<GlobalValue>(V) || isa<AllocationInst>(V);
  67 }
  68
  69 // getUnderlyingObject - This traverses the use chain to figure out what object
  70 // the specified value points to.  If the value points to, or is derived from, a
  71 // unique object or an argument, return it.
  72 static const Value *getUnderlyingObject(const Value *V) {
  73   if (!isa<PointerType>(V->getType())) return 0;
  74
  75   // If we are at some type of object... return it.
  76   if (hasUniqueAddress(V) || isa<Argument>(V)) return V;
  77
  78   // Traverse through different addressing mechanisms...
  79   if (const Instruction *I = dyn_cast<Instruction>(V)) {
  80     if (isa<CastInst>(I) || isa<GetElementPtrInst>(I))
  81       return getUnderlyingObject(I->getOperand(0));
  82   } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
  83     if (CE->getOpcode() == Instruction::Cast ||
  84         CE->getOpcode() == Instruction::GetElementPtr)
  85       return getUnderlyingObject(CE->getOperand(0));
  86   } else if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V)) {
  87     return CPR->getValue();
  88   }
  89   return 0;
  90 }
  91
  92
  93 // alias - Provide a bunch of ad-hoc rules to disambiguate in common cases, such
  94 // as array references.  Note that this function is heavily tail recursive.
  95 // Hopefully we have a smart C++ compiler.  :)
  96 //
  97 AliasAnalysis::AliasResult
  98 BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size,
  99                           const Value *V2, unsigned V2Size) {
 100   // Strip off constant pointer refs if they exist
 101   if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V1))
 102     V1 = CPR->getValue();
 103   if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V2))
 104     V2 = CPR->getValue();
 105
 106   // Are we checking for alias of the same value?
 107   if (V1 == V2) return MustAlias;
 108
 109   if ((!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType())) &&
 110       V1->getType() != Type::LongTy && V2->getType() != Type::LongTy)
 111     return NoAlias;  // Scalars cannot alias each other
 112
 113   // Strip off cast instructions...
 114   if (const Instruction *I = dyn_cast<CastInst>(V1))
 115     return alias(I->getOperand(0), V1Size, V2, V2Size);
 116   if (const Instruction *I = dyn_cast<CastInst>(V2))
 117     return alias(V1, V1Size, I->getOperand(0), V2Size);
 118
 119   // Figure out what objects these things are pointing to if we can...
 120   const Value *O1 = getUnderlyingObject(V1);
 121   const Value *O2 = getUnderlyingObject(V2);
 122
 123   // Pointing at a discernible object?
 124   if (O1 && O2) {
 125     if (isa<Argument>(O1)) {
 126       // Incoming argument cannot alias locally allocated object!
 127       if (isa<AllocationInst>(O2)) return NoAlias;
 128       // Otherwise, nothing is known...
 129     } else if (isa<Argument>(O2)) {
 130       // Incoming argument cannot alias locally allocated object!
 131       if (isa<AllocationInst>(O1)) return NoAlias;
 132       // Otherwise, nothing is known...
 133     } else {
 134       // If they are two different objects, we know that we have no alias...
 135       if (O1 != O2) return NoAlias;
 136     }
 137
 138     // If they are the same object, they we can look at the indexes.  If they
 139     // index off of the object is the same for both pointers, they must alias.
 140     // If they are provably different, they must not alias.  Otherwise, we can't
 141     // tell anything.
 142   } else if (O1 && !isa<Argument>(O1) && isa<ConstantPointerNull>(V2)) {
 143     return NoAlias;                    // Unique values don't alias null
 144   } else if (O2 && !isa<Argument>(O2) && isa<ConstantPointerNull>(V1)) {
 145     return NoAlias;                    // Unique values don't alias null
 146   }
 147
 148   // If we have two gep instructions with identical indices, return an alias
 149   // result equal to the alias result of the original pointer...
 150   //
 151   if (const GetElementPtrInst *GEP1 = dyn_cast<GetElementPtrInst>(V1))
 152     if (const GetElementPtrInst *GEP2 = dyn_cast<GetElementPtrInst>(V2))
 153       if (GEP1->getNumOperands() == GEP2->getNumOperands() &&
 154           GEP1->getOperand(0)->getType() == GEP2->getOperand(0)->getType()) {
 155         AliasResult GAlias =
 156           CheckGEPInstructions((GetElementPtrInst*)GEP1, V1Size,
 157                                (GetElementPtrInst*)GEP2, V2Size);
 158         if (GAlias != MayAlias)
 159           return GAlias;
 160       }
 161
 162   // Check to see if these two pointers are related by a getelementptr
 163   // instruction.  If one pointer is a GEP with a non-zero index of the other
 164   // pointer, we know they cannot alias.
 165   //
 166   if (isa<GetElementPtrInst>(V2)) {
 167     std::swap(V1, V2);
 168     std::swap(V1Size, V2Size);
 169   }
 170
 171   if (V1Size != ~0U && V2Size != ~0U)
 172     if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(V1)) {
 173       AliasResult R = alias(GEP->getOperand(0), V1Size, V2, V2Size);
 174       if (R == MustAlias) {
 175         // If there is at least one non-zero constant index, we know they cannot
 176         // alias.
 177         bool ConstantFound = false;
 178         for (unsigned i = 1, e = GEP->getNumOperands(); i != e; ++i)
 179           if (const Constant *C = dyn_cast<Constant>(GEP->getOperand(i)))
 180             if (!C->isNullValue()) {
 181               ConstantFound = true;
 182               break;
 183           }
 184         if (ConstantFound) {
 185           if (V2Size <= 1 && V1Size <= 1)  // Just pointer check?
 186             return NoAlias;
 187
 188           // Otherwise we have to check to see that the distance is more than
 189           // the size of the argument... build an index vector that is equal to
 190           // the arguments provided, except substitute 0's for any variable
 191           // indexes we find...
 192
 193           std::vector<Value*> Indices;
 194           Indices.reserve(GEP->getNumOperands()-1);
 195           for (unsigned i = 1; i != GEP->getNumOperands(); ++i)
 196             if (const Constant *C = dyn_cast<Constant>(GEP->getOperand(i)))
 197               Indices.push_back((Value*)C);
 198             else
 199               Indices.push_back(Constant::getNullValue(Type::LongTy));
 200           const Type *Ty = GEP->getOperand(0)->getType();
 201           int Offset = getTargetData().getIndexedOffset(Ty, Indices);
 202           if (Offset >= (int)V2Size || Offset <= -(int)V1Size)
 203             return NoAlias;
 204         }
 205       }
 206     }
 207
 208   return MayAlias;
 209 }
 210
 211 static Value *CheckArrayIndicesForOverflow(const Type *PtrTy,
 212                                            const std::vector<Value*> &Indices,
 213                                            const ConstantInt *Idx) {
 214   if (const ConstantSInt *IdxS = dyn_cast<ConstantSInt>(Idx)) {
 215     if (IdxS->getValue() < 0)   // Underflow on the array subscript?
 216       return Constant::getNullValue(Type::LongTy);
 217     else {                       // Check for overflow
 218       const ArrayType *ATy =
 219         cast<ArrayType>(GetElementPtrInst::getIndexedType(PtrTy, Indices,true));
 220       if (IdxS->getValue() >= (int64_t)ATy->getNumElements())
 221         return ConstantSInt::get(Type::LongTy, ATy->getNumElements()-1);
 222     }
 223   }
 224   return (Value*)Idx;  // Everything is acceptable.
 225 }
 226
 227 // CheckGEPInstructions - Check two GEP instructions of compatible types and
 228 // equal number of arguments.  This checks to see if the index expressions
 229 // preclude the pointers from aliasing...
 230 //
 231 AliasAnalysis::AliasResult
 232 BasicAliasAnalysis::CheckGEPInstructions(GetElementPtrInst *GEP1, unsigned G1S,
 233                                          GetElementPtrInst *GEP2, unsigned G2S){
 234   // Do the base pointers alias?
 235   AliasResult BaseAlias = alias(GEP1->getOperand(0), G1S,
 236                                 GEP2->getOperand(0), G2S);
 237   if (BaseAlias != MustAlias)   // No or May alias: We cannot add anything...
 238     return BaseAlias;
 239
 240   // Find the (possibly empty) initial sequence of equal values...
 241   unsigned NumGEPOperands = GEP1->getNumOperands();
 242   unsigned UnequalOper = 1;
 243   while (UnequalOper != NumGEPOperands &&
 244          GEP1->getOperand(UnequalOper) == GEP2->getOperand(UnequalOper))
 245     ++UnequalOper;
 246
 247   // If all operands equal each other, then the derived pointers must
 248   // alias each other...
 249   if (UnequalOper == NumGEPOperands) return MustAlias;
 250
 251   // So now we know that the indexes derived from the base pointers,
 252   // which are known to alias, are different.  We can still determine a
 253   // no-alias result if there are differing constant pairs in the index
 254   // chain.  For example:
 255   //        A[i][0] != A[j][1] iff (&A[0][1]-&A[0][0] >= std::max(G1S, G2S))
 256   //
 257   unsigned SizeMax = std::max(G1S, G2S);
 258   if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work...
 259
 260   // Scan for the first operand that is constant and unequal in the
 261   // two getelemenptrs...
 262   unsigned FirstConstantOper = UnequalOper;
 263   for (; FirstConstantOper != NumGEPOperands; ++FirstConstantOper) {
 264     const Value *G1Oper = GEP1->getOperand(FirstConstantOper);
 265     const Value *G2Oper = GEP2->getOperand(FirstConstantOper);
 266     if (G1Oper != G2Oper &&   // Found non-equal constant indexes...
 267         isa<Constant>(G1Oper) && isa<Constant>(G2Oper)) {
 268       // Make sure they are comparable...  and make sure the GEP with
 269       // the smaller leading constant is GEP1.
 270       ConstantBool *Compare =
 271         *cast<Constant>(GEP1->getOperand(FirstConstantOper)) >
 272         *cast<Constant>(GEP2->getOperand(FirstConstantOper));
 273       if (Compare) {  // If they are comparable...
 274         if (Compare->getValue())
 275           std::swap(GEP1, GEP2);  // Make GEP1 < GEP2
 276         break;
 277       }
 278     }
 279   }
 280
 281   // No constant operands, we cannot tell anything...
 282   if (FirstConstantOper == NumGEPOperands) return MayAlias;
 283
 284   // If there are non-equal constants arguments, then we can figure
 285   // out a minimum known delta between the two index expressions... at
 286   // this point we know that the first constant index of GEP1 is less
 287   // than the first constant index of GEP2.
 288   //
 289   std::vector<Value*> Indices1;
 290   Indices1.reserve(NumGEPOperands-1);
 291
 292   for (gep_type_iterator I = gep_type_begin(GEP1);
 293        I.getOperandNum() != FirstConstantOper; ++I)
 294     if (isa<StructType>(*I))
 295       Indices1.push_back(I.getOperand());
 296     else
 297       Indices1.push_back(Constant::getNullValue(Type::LongTy));
 298
 299   std::vector<Value*> Indices2;
 300   Indices2.reserve(NumGEPOperands-1);
 301   Indices2 = Indices1;           // Copy the zeros prefix...
 302
 303   // Add the two known constant operands...
 304   Indices1.push_back((Value*)GEP1->getOperand(FirstConstantOper));
 305   Indices2.push_back((Value*)GEP2->getOperand(FirstConstantOper));
 306
 307   const Type *GEPPointerTy = GEP1->getOperand(0)->getType();
 308
 309   // Loop over the rest of the operands...
 310   for (unsigned i = FirstConstantOper+1; i != NumGEPOperands; ++i) {
 311     const Value *Op1 = GEP1->getOperand(i);
 312     const Value *Op2 = GEP2->getOperand(i);
 313     if (Op1 == Op2) {   // If they are equal, use a zero index...
 314       if (!isa<Constant>(Op1)) {
 315         Indices1.push_back(Constant::getNullValue(Op1->getType()));
 316         Indices2.push_back(Indices1.back());
 317       } else {
 318         Indices1.push_back((Value*)Op1);
 319         Indices2.push_back((Value*)Op2);
 320       }
 321     } else {
 322       if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
 323         // If this is an array index, make sure the array element is in range...
 324         if (i != 1)   // The pointer index can be "out of range"
 325           Op1 = CheckArrayIndicesForOverflow(GEPPointerTy, Indices1, Op1C);
 326
 327         Indices1.push_back((Value*)Op1);
 328       } else {
 329         // GEP1 is known to produce a value less than GEP2.  To be
 330         // conservatively correct, we must assume the largest possible constant
 331         // is used in this position.  This cannot be the initial index to the
 332         // GEP instructions (because we know we have at least one element before
 333         // this one with the different constant arguments), so we know that the
 334         // current index must be into either a struct or array.  Because we know
 335         // it's not constant, this cannot be a structure index.  Because of
 336         // this, we can calculate the maximum value possible.
 337         //
 338         const ArrayType *ElTy =
 339           cast<ArrayType>(GEP1->getIndexedType(GEPPointerTy, Indices1, true));
 340         Indices1.push_back(ConstantSInt::get(Type::LongTy,
 341                                              ElTy->getNumElements()-1));
 342       }
 343
 344       if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op2)) {
 345         // If this is an array index, make sure the array element is in range...
 346         if (i != 1)   // The pointer index can be "out of range"
 347           Op1 = CheckArrayIndicesForOverflow(GEPPointerTy, Indices2, Op1C);
 348
 349         Indices2.push_back((Value*)Op2);
 350       }
 351       else // Conservatively assume the minimum value for this index
 352         Indices2.push_back(Constant::getNullValue(Op2->getType()));
 353     }
 354   }
 355
 356   int64_t Offset1 = getTargetData().getIndexedOffset(GEPPointerTy, Indices1);
 357   int64_t Offset2 = getTargetData().getIndexedOffset(GEPPointerTy, Indices2);
 358   assert(Offset1 < Offset2 &&"There is at least one different constant here!");
 359
 360   if ((uint64_t)(Offset2-Offset1) >= SizeMax) {
 361     //std::cerr << "Determined that these two GEP's don't alias ["
 362     //          << SizeMax << " bytes]: \n" << *GEP1 << *GEP2;
 363     return NoAlias;
 364   }
 365   return MayAlias;
 366 }
 367