lib/Analysis/TypeBasedAliasAnalysis.cpp

   1 //===- TypeBasedAliasAnalysis.cpp - Type-Based Alias Analysis -------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines the TypeBasedAliasAnalysis pass, which implements
  11 // metadata-based TBAA.
  12 //
  13 // In LLVM IR, memory does not have types, so LLVM's own type system is not
  14 // suitable for doing TBAA. Instead, metadata is added to the IR to describe
  15 // a type system of a higher level language.
  16 //
  17 // This pass is language-independent. The type system is encoded in
  18 // metadata. This allows this pass to support typical C and C++ TBAA, but
  19 // it can also support custom aliasing behavior for other languages.
  20 //
  21 // This is a work-in-progress. It doesn't work yet, and the metadata
  22 // format isn't stable.
  23 //
  24 // TODO: getModRefBehavior. The AliasAnalysis infrastructure will need to
  25 //       be extended.
  26 // TODO: struct fields
  27 //
  28 //===----------------------------------------------------------------------===//
  29
  30 #include "llvm/Analysis/AliasAnalysis.h"
  31 #include "llvm/Analysis/Passes.h"
  32 #include "llvm/Module.h"
  33 #include "llvm/Metadata.h"
  34 #include "llvm/Pass.h"
  35 #include "llvm/Support/CommandLine.h"
  36 using namespace llvm;
  37
  38 // For testing purposes, enable TBAA only via a special option.
  39 static cl::opt<bool> EnableTBAA("enable-tbaa");
  40
  41 namespace {
  42   /// TBAANode - This is a simple wrapper around an MDNode which provides a
  43   /// higher-level interface by hiding the details of how alias analysis
  44   /// information is encoded in its operands.
  45   class TBAANode {
  46     const MDNode *Node;
  47
  48   public:
  49     TBAANode() : Node(0) {}
  50     explicit TBAANode(const MDNode *N) : Node(N) {}
  51
  52     /// getNode - Get the MDNode for this TBAANode.
  53     const MDNode *getNode() const { return Node; }
  54
  55     /// getParent - Get this TBAANode's Alias DAG parent.
  56     TBAANode getParent() const {
  57       if (Node->getNumOperands() < 2)
  58         return TBAANode();
  59       MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(1));
  60       if (!P)
  61         return TBAANode();
  62       // Ok, this node has a valid parent. Return it.
  63       return TBAANode(P);
  64     }
  65
  66     /// TypeIsImmutable - Test if this TBAANode represents a type for objects
  67     /// which are not modified (by any means) in the context where this
  68     /// AliasAnalysis is relevant.
  69     bool TypeIsImmutable() const {
  70       if (Node->getNumOperands() < 3)
  71         return false;
  72       ConstantInt *CI = dyn_cast<ConstantInt>(Node->getOperand(2));
  73       if (!CI)
  74         return false;
  75       // TODO: Think about the encoding.
  76       return CI->isOne();
  77     }
  78   };
  79 }
  80
  81 namespace {
  82   /// TypeBasedAliasAnalysis - This is a simple alias analysis
  83   /// implementation that uses TypeBased to answer queries.
  84   class TypeBasedAliasAnalysis : public ImmutablePass,
  85                                  public AliasAnalysis {
  86   public:
  87     static char ID; // Class identification, replacement for typeinfo
  88     TypeBasedAliasAnalysis() : ImmutablePass(ID) {
  89       initializeTypeBasedAliasAnalysisPass(*PassRegistry::getPassRegistry());
  90     }
  91
  92     virtual void initializePass() {
  93       InitializeAliasAnalysis(this);
  94     }
  95
  96     /// getAdjustedAnalysisPointer - This method is used when a pass implements
  97     /// an analysis interface through multiple inheritance.  If needed, it
  98     /// should override this to adjust the this pointer as needed for the
  99     /// specified pass info.
 100     virtual void *getAdjustedAnalysisPointer(const void *PI) {
 101       if (PI == &AliasAnalysis::ID)
 102         return (AliasAnalysis*)this;
 103       return this;
 104     }
 105
 106   private:
 107     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 108     virtual AliasResult alias(const Location &LocA, const Location &LocB);
 109     virtual bool pointsToConstantMemory(const Location &Loc);
 110   };
 111 }  // End of anonymous namespace
 112
 113 // Register this pass...
 114 char TypeBasedAliasAnalysis::ID = 0;
 115 INITIALIZE_AG_PASS(TypeBasedAliasAnalysis, AliasAnalysis, "tbaa",
 116                    "Type-Based Alias Analysis", false, true, false)
 117
 118 ImmutablePass *llvm::createTypeBasedAliasAnalysisPass() {
 119   return new TypeBasedAliasAnalysis();
 120 }
 121
 122 void
 123 TypeBasedAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
 124   AU.setPreservesAll();
 125   AliasAnalysis::getAnalysisUsage(AU);
 126 }
 127
 128 AliasAnalysis::AliasResult
 129 TypeBasedAliasAnalysis::alias(const Location &LocA,
 130                               const Location &LocB) {
 131   if (!EnableTBAA)
 132     return AliasAnalysis::alias(LocA, LocB);
 133
 134   // Get the attached MDNodes. If either value lacks a tbaa MDNode, we must
 135   // be conservative.
 136   const MDNode *AM = LocA.TBAATag;
 137   if (!AM) return AliasAnalysis::alias(LocA, LocB);
 138   const MDNode *BM = LocB.TBAATag;
 139   if (!BM) return AliasAnalysis::alias(LocA, LocB);
 140
 141   // Keep track of the root node for A and B.
 142   TBAANode RootA, RootB;
 143
 144   // Climb the DAG from A to see if we reach B.
 145   for (TBAANode T(AM); ; ) {
 146     if (T.getNode() == BM)
 147       // B is an ancestor of A.
 148       return AliasAnalysis::alias(LocA, LocB);
 149
 150     RootA = T;
 151     T = T.getParent();
 152     if (!T.getNode())
 153       break;
 154   }
 155
 156   // Climb the DAG from B to see if we reach A.
 157   for (TBAANode T(BM); ; ) {
 158     if (T.getNode() == AM)
 159       // A is an ancestor of B.
 160       return AliasAnalysis::alias(LocA, LocB);
 161
 162     RootB = T;
 163     T = T.getParent();
 164     if (!T.getNode())
 165       break;
 166   }
 167
 168   // Neither node is an ancestor of the other.
 169
 170   // If they have the same root, then we've proved there's no alias.
 171   if (RootA.getNode() == RootB.getNode())
 172     return NoAlias;
 173
 174   // If they have different roots, they're part of different potentially
 175   // unrelated type systems, so we must be conservative.
 176   return AliasAnalysis::alias(LocA, LocB);
 177 }
 178
 179 bool TypeBasedAliasAnalysis::pointsToConstantMemory(const Location &Loc) {
 180   if (!EnableTBAA)
 181     return AliasAnalysis::pointsToConstantMemory(Loc);
 182
 183   const MDNode *M = Loc.TBAATag;
 184   if (!M) return false;
 185
 186   // If this is an "immutable" type, we can assume the pointer is pointing
 187   // to constant memory.
 188   if (TBAANode(M).TypeIsImmutable())
 189     return true;
 190
 191   return AliasAnalysis::pointsToConstantMemory(Loc);
 192 }