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       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) const {
  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) const {
  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 AliasAnalysis::Result BasicAliasAnalysis::alias(const Value *V1,
 129                                                 const Value *V2) const {
 130   // Strip off constant pointer refs if they exist
 131   if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V1))
 132     V1 = CPR->getValue();
 133   if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V2))
 134     V2 = CPR->getValue();
 135
 136   // Are we checking for alias of the same value?
 137   if (V1 == V2) return MustAlias;
 138
 139   if (!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType()))
 140     return NoAlias;  // Scalars cannot alias each other
 141
 142   bool V1Unique = hasUniqueAddress(V1);
 143   bool V2Unique = hasUniqueAddress(V2);
 144
 145   if (V1Unique && V2Unique)
 146     return NoAlias;         // Can't alias if they are different unique values
 147
 148   if ((V1Unique && isa<ConstantPointerNull>(V2)) ||
 149       (V2Unique && isa<ConstantPointerNull>(V1)))
 150     return NoAlias;         // Unique values don't alias null
 151
 152   // TODO: Handle getelementptr with nonzero offset
 153
 154   return MayAlias;
 155 }