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 void llvm::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         bool AllZerosFound = true;
 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           } else {
 186             AllZerosFound = false;
 187           }
 188
 189         // If we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 must aliases
 190         // the ptr, the end result is a must alias also.
 191         if (AllZerosFound)
 192           return MustAlias;
 193
 194         if (ConstantFound) {
 195           if (V2Size <= 1 && V1Size <= 1)  // Just pointer check?
 196             return NoAlias;
 197
 198           // Otherwise we have to check to see that the distance is more than
 199           // the size of the argument... build an index vector that is equal to
 200           // the arguments provided, except substitute 0's for any variable
 201           // indexes we find...
 202
 203           std::vector<Value*> Indices;
 204           Indices.reserve(GEP->getNumOperands()-1);
 205           for (unsigned i = 1; i != GEP->getNumOperands(); ++i)
 206             if (const Constant *C = dyn_cast<Constant>(GEP->getOperand(i)))
 207               Indices.push_back((Value*)C);
 208             else
 209               Indices.push_back(Constant::getNullValue(Type::LongTy));
 210           const Type *Ty = GEP->getOperand(0)->getType();
 211           int Offset = getTargetData().getIndexedOffset(Ty, Indices);
 212           if (Offset >= (int)V2Size || Offset <= -(int)V1Size)
 213             return NoAlias;
 214         }
 215       }
 216     }
 217
 218   return MayAlias;
 219 }
 220
 221 static Value *CheckArrayIndicesForOverflow(const Type *PtrTy,
 222                                            const std::vector<Value*> &Indices,
 223                                            const ConstantInt *Idx) {
 224   if (const ConstantSInt *IdxS = dyn_cast<ConstantSInt>(Idx)) {
 225     if (IdxS->getValue() < 0)   // Underflow on the array subscript?
 226       return Constant::getNullValue(Type::LongTy);
 227     else {                       // Check for overflow
 228       const ArrayType *ATy =
 229         cast<ArrayType>(GetElementPtrInst::getIndexedType(PtrTy, Indices,true));
 230       if (IdxS->getValue() >= (int64_t)ATy->getNumElements())
 231         return ConstantSInt::get(Type::LongTy, ATy->getNumElements()-1);
 232     }
 233   }
 234   return (Value*)Idx;  // Everything is acceptable.
 235 }
 236
 237 // CheckGEPInstructions - Check two GEP instructions of compatible types and
 238 // equal number of arguments.  This checks to see if the index expressions
 239 // preclude the pointers from aliasing...
 240 //
 241 AliasAnalysis::AliasResult
 242 BasicAliasAnalysis::CheckGEPInstructions(GetElementPtrInst *GEP1, unsigned G1S,
 243                                          GetElementPtrInst *GEP2, unsigned G2S){
 244   // Do the base pointers alias?
 245   AliasResult BaseAlias = alias(GEP1->getOperand(0), G1S,
 246                                 GEP2->getOperand(0), G2S);
 247   if (BaseAlias != MustAlias)   // No or May alias: We cannot add anything...
 248     return BaseAlias;
 249
 250   // Find the (possibly empty) initial sequence of equal values...
 251   unsigned NumGEPOperands = GEP1->getNumOperands();
 252   unsigned UnequalOper = 1;
 253   while (UnequalOper != NumGEPOperands &&
 254          GEP1->getOperand(UnequalOper) == GEP2->getOperand(UnequalOper))
 255     ++UnequalOper;
 256
 257   // If all operands equal each other, then the derived pointers must
 258   // alias each other...
 259   if (UnequalOper == NumGEPOperands) return MustAlias;
 260
 261   // So now we know that the indexes derived from the base pointers,
 262   // which are known to alias, are different.  We can still determine a
 263   // no-alias result if there are differing constant pairs in the index
 264   // chain.  For example:
 265   //        A[i][0] != A[j][1] iff (&A[0][1]-&A[0][0] >= std::max(G1S, G2S))
 266   //
 267   unsigned SizeMax = std::max(G1S, G2S);
 268   if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work...
 269
 270   // Scan for the first operand that is constant and unequal in the
 271   // two getelemenptrs...
 272   unsigned FirstConstantOper = UnequalOper;
 273   for (; FirstConstantOper != NumGEPOperands; ++FirstConstantOper) {
 274     const Value *G1Oper = GEP1->getOperand(FirstConstantOper);
 275     const Value *G2Oper = GEP2->getOperand(FirstConstantOper);
 276     if (G1Oper != G2Oper &&   // Found non-equal constant indexes...
 277         isa<Constant>(G1Oper) && isa<Constant>(G2Oper)) {
 278       // Make sure they are comparable...  and make sure the GEP with
 279       // the smaller leading constant is GEP1.
 280       ConstantBool *Compare =
 281         *cast<Constant>(GEP1->getOperand(FirstConstantOper)) >
 282         *cast<Constant>(GEP2->getOperand(FirstConstantOper));
 283       if (Compare) {  // If they are comparable...
 284         if (Compare->getValue())
 285           std::swap(GEP1, GEP2);  // Make GEP1 < GEP2
 286         break;
 287       }
 288     }
 289   }
 290
 291   // No constant operands, we cannot tell anything...
 292   if (FirstConstantOper == NumGEPOperands) return MayAlias;
 293
 294   // If there are non-equal constants arguments, then we can figure
 295   // out a minimum known delta between the two index expressions... at
 296   // this point we know that the first constant index of GEP1 is less
 297   // than the first constant index of GEP2.
 298   //
 299   std::vector<Value*> Indices1;
 300   Indices1.reserve(NumGEPOperands-1);
 301
 302   for (gep_type_iterator I = gep_type_begin(GEP1);
 303        I.getOperandNum() != FirstConstantOper; ++I)
 304     if (isa<StructType>(*I))
 305       Indices1.push_back(I.getOperand());
 306     else
 307       Indices1.push_back(Constant::getNullValue(Type::LongTy));
 308
 309   std::vector<Value*> Indices2;
 310   Indices2.reserve(NumGEPOperands-1);
 311   Indices2 = Indices1;           // Copy the zeros prefix...
 312
 313   // Add the two known constant operands...
 314   Indices1.push_back((Value*)GEP1->getOperand(FirstConstantOper));
 315   Indices2.push_back((Value*)GEP2->getOperand(FirstConstantOper));
 316
 317   const Type *GEPPointerTy = GEP1->getOperand(0)->getType();
 318
 319   // Loop over the rest of the operands...
 320   for (unsigned i = FirstConstantOper+1; i != NumGEPOperands; ++i) {
 321     const Value *Op1 = GEP1->getOperand(i);
 322     const Value *Op2 = GEP2->getOperand(i);
 323     if (Op1 == Op2) {   // If they are equal, use a zero index...
 324       if (!isa<Constant>(Op1)) {
 325         Indices1.push_back(Constant::getNullValue(Op1->getType()));
 326         Indices2.push_back(Indices1.back());
 327       } else {
 328         Indices1.push_back((Value*)Op1);
 329         Indices2.push_back((Value*)Op2);
 330       }
 331     } else {
 332       if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
 333         // If this is an array index, make sure the array element is in range...
 334         if (i != 1)   // The pointer index can be "out of range"
 335           Op1 = CheckArrayIndicesForOverflow(GEPPointerTy, Indices1, Op1C);
 336
 337         Indices1.push_back((Value*)Op1);
 338       } else {
 339         // GEP1 is known to produce a value less than GEP2.  To be
 340         // conservatively correct, we must assume the largest possible constant
 341         // is used in this position.  This cannot be the initial index to the
 342         // GEP instructions (because we know we have at least one element before
 343         // this one with the different constant arguments), so we know that the
 344         // current index must be into either a struct or array.  Because we know
 345         // it's not constant, this cannot be a structure index.  Because of
 346         // this, we can calculate the maximum value possible.
 347         //
 348         const ArrayType *ElTy =
 349           cast<ArrayType>(GEP1->getIndexedType(GEPPointerTy, Indices1, true));
 350         Indices1.push_back(ConstantSInt::get(Type::LongTy,
 351                                              ElTy->getNumElements()-1));
 352       }
 353
 354       if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op2)) {
 355         // If this is an array index, make sure the array element is in range...
 356         if (i != 1)   // The pointer index can be "out of range"
 357           Op1 = CheckArrayIndicesForOverflow(GEPPointerTy, Indices2, Op1C);
 358
 359         Indices2.push_back((Value*)Op2);
 360       }
 361       else // Conservatively assume the minimum value for this index
 362         Indices2.push_back(Constant::getNullValue(Op2->getType()));
 363     }
 364   }
 365
 366   int64_t Offset1 = getTargetData().getIndexedOffset(GEPPointerTy, Indices1);
 367   int64_t Offset2 = getTargetData().getIndexedOffset(GEPPointerTy, Indices2);
 368   assert(Offset1 < Offset2 &&"There is at least one different constant here!");
 369
 370   if ((uint64_t)(Offset2-Offset1) >= SizeMax) {
 371     //std::cerr << "Determined that these two GEP's don't alias ["
 372     //          << SizeMax << " bytes]: \n" << *GEP1 << *GEP2;
 373     return NoAlias;
 374   }
 375   return MayAlias;
 376 }
 377