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/Constants.h"
  25 #include "llvm/GlobalValue.h"
  26 #include "llvm/DerivedTypes.h"
  27 #include "llvm/Pass.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     const AliasAnalysis &AA;
  38     const Value *Ptr;
  39
  40     CanModify(const 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       assert(!SI.hasIndices() && "Only support stores without indexing!");
  51       return AA.alias(Ptr, SI.getOperand(1));
  52     }
  53
  54     // Other instructions do not alias anything.
  55     bool visitInstruction(Instruction &I) { return false; }
  56   };
  57 }
  58
  59 // AliasAnalysis destructor: DO NOT move this to the header file for
  60 // AliasAnalysis or else clients of the AliasAnalysis class may not depend on
  61 // the AliasAnalysis.o file in the current .a file, causing alias analysis
  62 // support to not be included in the tool correctly!
  63 //
  64 AliasAnalysis::~AliasAnalysis() {}
  65
  66 // canBasicBlockModify - Return true if it is possible for execution of the
  67 // specified basic block to modify the value pointed to by Ptr.
  68 //
  69 bool AliasAnalysis::canBasicBlockModify(const BasicBlock &bb,
  70                                         const Value *Ptr) const {
  71   CanModify CM(this, Ptr);
  72   BasicBlock &BB = const_cast<BasicBlock&>(bb);
  73
  74   for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I)
  75     if (CM.visit(I))        // Check every instruction in the basic block...
  76       return true;
  77
  78   return false;
  79 }
  80
  81 // canInstructionRangeModify - Return true if it is possible for the execution
  82 // of the specified instructions to modify the value pointed to by Ptr.  The
  83 // instructions to consider are all of the instructions in the range of [I1,I2]
  84 // INCLUSIVE.  I1 and I2 must be in the same basic block.
  85 //
  86 bool AliasAnalysis::canInstructionRangeModify(const Instruction &I1,
  87                                               const Instruction &I2,
  88                                               const Value *Ptr) const {
  89   assert(I1.getParent() == I2.getParent() &&
  90          "Instructions not in same basic block!");
  91   CanModify CM(this, Ptr);
  92   BasicBlock::iterator I = const_cast<Instruction*>(&I1);
  93   BasicBlock::iterator E = const_cast<Instruction*>(&I2);
  94   ++E;  // Convert from inclusive to exclusive range.
  95
  96   for (; I != E; ++I)
  97     if (CM.visit(I))        // Check every instruction in the basic block...
  98       return true;
  99
 100   return false;
 101 }
 102
 103 //===----------------------------------------------------------------------===//
 104 // BasicAliasAnalysis Pass Implementation
 105 //===----------------------------------------------------------------------===//
 106 //
 107 // Because of the way .a files work, the implementation of the
 108 // BasicAliasAnalysis class MUST be in the AliasAnalysis file itself, or else we
 109 // run the risk of AliasAnalysis being used, but the default implementation not
 110 // being linked into the tool that uses it.  As such, we register and implement
 111 // the class here.
 112 //
 113 namespace {
 114   // Register this pass...
 115   RegisterOpt<BasicAliasAnalysis>
 116   X("basicaa", "Basic Alias Analysis (default AA impl)");
 117
 118   // Declare that we implement the AliasAnalysis interface
 119   RegisterAnalysisGroup<AliasAnalysis, BasicAliasAnalysis, true> Y;
 120 }  // End of anonymous namespace
 121
 122
 123
 124 // hasUniqueAddress - Return true if the
 125 static inline bool hasUniqueAddress(const Value *V) {
 126   return isa<GlobalValue>(V) || isa<MallocInst>(V) || isa<AllocaInst>(V);
 127 }
 128
 129 AliasAnalysis::Result BasicAliasAnalysis::alias(const Value *V1,
 130                                                 const Value *V2) const {
 131   // Strip off constant pointer refs if they exist
 132   if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V1))
 133     V1 = CPR->getValue();
 134   if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V2))
 135     V2 = CPR->getValue();
 136
 137   // Are we checking for alias of the same value?
 138   if (V1 == V2) return MustAlias;
 139
 140   if (!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType()))
 141     return NoAlias;  // Scalars cannot alias each other
 142
 143   bool V1Unique = hasUniqueAddress(V1);
 144   bool V2Unique = hasUniqueAddress(V2);
 145
 146   if (V1Unique && V2Unique)
 147     return NoAlias;         // Can't alias if they are different unique values
 148
 149   if ((V1Unique && isa<ConstantPointerNull>(V2)) ||
 150       (V2Unique && isa<ConstantPointerNull>(V1)))
 151     return NoAlias;         // Unique values don't alias null
 152
 153   // TODO: Handle getelementptr with nonzero offset
 154
 155   return MayAlias;
 156 }