lib/Analysis/BasicAliasAnalysis.cpp

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