lib/Analysis/AliasAnalysis.cpp

   1 //===- AliasAnalysis.cpp - Generic Alias Analysis Interface Implementation -==//
   2 //
   3 // This file implements the generic AliasAnalysis interface which is used as the
   4 // common interface used by all clients and implementations of alias analysis.
   5 //
   6 // This file also implements the default version of the AliasAnalysis interface
   7 // that is to be used when no other implementation is specified.  This does some
   8 // simple tests that detect obvious cases: two different global pointers cannot
   9 // alias, a global cannot alias a malloc, two different mallocs cannot alias,
  10 // etc.
  11 //
  12 // This alias analysis implementation really isn't very good for anything, but
  13 // it is very fast, and makes a nice clean default implementation.  Because it
  14 // handles lots of little corner cases, other, more complex, alias analysis
  15 // implementations may choose to rely on this pass to resolve these simple and
  16 // easy cases.
  17 //
  18 //===----------------------------------------------------------------------===//
  19
  20 #include "llvm/Analysis/BasicAliasAnalysis.h"
  21 #include "llvm/BasicBlock.h"
  22 #include "llvm/Support/InstVisitor.h"
  23 #include "llvm/iMemory.h"
  24 #include "llvm/iOther.h"
  25 #include "llvm/Constants.h"
  26 #include "llvm/GlobalValue.h"
  27 #include "llvm/DerivedTypes.h"
  28
  29 // Register the AliasAnalysis interface, providing a nice name to refer to.
  30 static RegisterAnalysisGroup<AliasAnalysis> X("Alias Analysis");
  31
  32 // CanModify - Define a little visitor class that is used to check to see if
  33 // arbitrary chunks of code can modify a specified pointer.
  34 //
  35 namespace {
  36   struct CanModify : public InstVisitor<CanModify, bool> {
  37     AliasAnalysis &AA;
  38     const Value *Ptr;
  39
  40     CanModify(AliasAnalysis *aa, const Value *ptr)
  41       : AA(*aa), Ptr(ptr) {}
  42
  43     bool visitInvokeInst(InvokeInst &II) {
  44       return AA.canInvokeModify(II, Ptr);
  45     }
  46     bool visitCallInst(CallInst &CI) {
  47       return AA.canCallModify(CI, Ptr);
  48     }
  49     bool visitStoreInst(StoreInst &SI) {
  50       return AA.alias(Ptr, SI.getOperand(1));
  51     }
  52
  53     // Other instructions do not alias anything.
  54     bool visitInstruction(Instruction &I) { return false; }
  55   };
  56 }
  57
  58 // AliasAnalysis destructor: DO NOT move this to the header file for
  59 // AliasAnalysis or else clients of the AliasAnalysis class may not depend on
  60 // the AliasAnalysis.o file in the current .a file, causing alias analysis
  61 // support to not be included in the tool correctly!
  62 //
  63 AliasAnalysis::~AliasAnalysis() {}
  64
  65 /// canBasicBlockModify - Return true if it is possible for execution of the
  66 /// specified basic block to modify the value pointed to by Ptr.
  67 ///
  68 bool AliasAnalysis::canBasicBlockModify(const BasicBlock &bb,
  69                                         const Value *Ptr) {
  70   CanModify CM(this, Ptr);
  71   BasicBlock &BB = const_cast<BasicBlock&>(bb);
  72
  73   for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I)
  74     if (CM.visit(I))        // Check every instruction in the basic block...
  75       return true;
  76
  77   return false;
  78 }
  79
  80 /// canInstructionRangeModify - Return true if it is possible for the execution
  81 /// of the specified instructions to modify the value pointed to by Ptr.  The
  82 /// instructions to consider are all of the instructions in the range of [I1,I2]
  83 /// INCLUSIVE.  I1 and I2 must be in the same basic block.
  84 ///
  85 bool AliasAnalysis::canInstructionRangeModify(const Instruction &I1,
  86                                               const Instruction &I2,
  87                                               const Value *Ptr) {
  88   assert(I1.getParent() == I2.getParent() &&
  89          "Instructions not in same basic block!");
  90   CanModify CM(this, Ptr);
  91   BasicBlock::iterator I = const_cast<Instruction*>(&I1);
  92   BasicBlock::iterator E = const_cast<Instruction*>(&I2);
  93   ++E;  // Convert from inclusive to exclusive range.
  94
  95   for (; I != E; ++I)
  96     if (CM.visit(I))        // Check every instruction in the basic block...
  97       return true;
  98
  99   return false;
 100 }
 101
 102 //===----------------------------------------------------------------------===//
 103 // BasicAliasAnalysis Pass Implementation
 104 //===----------------------------------------------------------------------===//
 105 //
 106 // Because of the way .a files work, the implementation of the
 107 // BasicAliasAnalysis class MUST be in the AliasAnalysis file itself, or else we
 108 // run the risk of AliasAnalysis being used, but the default implementation not
 109 // being linked into the tool that uses it.  As such, we register and implement
 110 // the class here.
 111 //
 112 namespace {
 113   // Register this pass...
 114   RegisterOpt<BasicAliasAnalysis>
 115   X("basicaa", "Basic Alias Analysis (default AA impl)");
 116
 117   // Declare that we implement the AliasAnalysis interface
 118   RegisterAnalysisGroup<AliasAnalysis, BasicAliasAnalysis, true> Y;
 119 }  // End of anonymous namespace
 120
 121
 122
 123 // hasUniqueAddress - Return true if the
 124 static inline bool hasUniqueAddress(const Value *V) {
 125   return isa<GlobalValue>(V) || isa<MallocInst>(V) || isa<AllocaInst>(V);
 126 }
 127
 128 static const Value *getUnderlyingObject(const Value *V) {
 129   if (!isa<PointerType>(V->getType())) return 0;
 130
 131   // If we are at some type of object... return it.
 132   if (hasUniqueAddress(V)) return V;
 133
 134   // Traverse through different addressing mechanisms...
 135   if (const Instruction *I = dyn_cast<Instruction>(V)) {
 136     if (isa<CastInst>(I) || isa<GetElementPtrInst>(I))
 137       return getUnderlyingObject(I->getOperand(0));
 138   }
 139   return 0;
 140 }
 141
 142 // alias - Provide a bunch of ad-hoc rules to disambiguate in common cases, such
 143 // as array references.  Note that this function is heavily tail recursive.
 144 // Hopefully we have a smart C++ compiler.  :)
 145 //
 146 AliasAnalysis::Result BasicAliasAnalysis::alias(const Value *V1,
 147                                                 const Value *V2) {
 148   // Strip off constant pointer refs if they exist
 149   if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V1))
 150     V1 = CPR->getValue();
 151   if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V2))
 152     V2 = CPR->getValue();
 153
 154   // Are we checking for alias of the same value?
 155   if (V1 == V2) return MustAlias;
 156
 157   if ((!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType())) &&
 158       V1->getType() != Type::LongTy && V2->getType() != Type::LongTy)
 159     return NoAlias;  // Scalars cannot alias each other
 160
 161   // Strip off cast instructions...
 162   if (const Instruction *I = dyn_cast<CastInst>(V1))
 163     return alias(I->getOperand(0), V2);
 164   if (const Instruction *I = dyn_cast<CastInst>(V2))
 165     return alias(I->getOperand(0), V1);
 166
 167   // If we have two gep instructions with identical indices, return an alias
 168   // result equal to the alias result of the original pointer...
 169   //
 170   if (const GetElementPtrInst *GEP1 = dyn_cast<GetElementPtrInst>(V1))
 171     if (const GetElementPtrInst *GEP2 = dyn_cast<GetElementPtrInst>(V2))
 172       if (GEP1->getNumOperands() == GEP2->getNumOperands() &&
 173           GEP1->getOperand(0)->getType() == GEP2->getOperand(0)->getType()) {
 174         if (std::equal(GEP1->op_begin()+1, GEP1->op_end(), GEP2->op_begin()+1))
 175           return alias(GEP1->getOperand(0), GEP2->getOperand(0));
 176
 177         // If all of the indexes to the getelementptr are constant, but
 178         // different (well we already know they are different), then we know
 179         // that there cannot be an alias here if the two base pointers DO alias.
 180         //
 181         bool AllConstant = true;
 182         for (unsigned i = 1, e = GEP1->getNumOperands(); i != e; ++i)
 183           if (!isa<Constant>(GEP1->getOperand(i)) ||
 184               !isa<Constant>(GEP2->getOperand(i))) {
 185             AllConstant = false;
 186             break;
 187           }
 188
 189         // If we are all constant, then look at where the the base pointers
 190         // alias.  If they are known not to alias, then we are dealing with two
 191         // different arrays or something, so no alias is possible.  If they are
 192         // known to be the same object, then we cannot alias because we are
 193         // indexing into a different part of the object.  As usual, MayAlias
 194         // doesn't tell us anything.
 195         //
 196         if (AllConstant &&
 197             alias(GEP1->getOperand(0), GEP2->getOperand(1)) != MayAlias)
 198             return NoAlias;
 199       }
 200
 201   // Figure out what objects these things are pointing to if we can...
 202   const Value *O1 = getUnderlyingObject(V1);
 203   const Value *O2 = getUnderlyingObject(V2);
 204
 205   // Pointing at a discernable object?
 206   if (O1 && O2) {
 207     // If they are two different objects, we know that we have no alias...
 208     if (O1 != O2) return NoAlias;
 209
 210     // If they are the same object, they we can look at the indexes.  If they
 211     // index off of the object is the same for both pointers, they must alias.
 212     // If they are provably different, they must not alias.  Otherwise, we can't
 213     // tell anything.
 214   } else if (O1 && isa<ConstantPointerNull>(V2)) {
 215     return NoAlias;                    // Unique values don't alias null
 216   } else if (O2 && isa<ConstantPointerNull>(V1)) {
 217     return NoAlias;                    // Unique values don't alias null
 218   }
 219
 220   return MayAlias;
 221 }