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