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