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. This can be used to implement
  16 // typical C/C++ TBAA, but it can also be used to implement custom alias
  17 // analysis behavior for other languages.
  18 //
  19 // The current metadata format is very simple. TBAA MDNodes have up to
  20 // three fields, e.g.:
  21 //   !0 = metadata !{ metadata !"an example type tree" }
  22 //   !1 = metadata !{ metadata !"int", metadata !0 }
  23 //   !2 = metadata !{ metadata !"float", metadata !0 }
  24 //   !3 = metadata !{ metadata !"const float", metadata !2, i64 1 }
  25 //
  26 // The first field is an identity field. It can be any value, usually
  27 // an MDString, which uniquely identifies the type. The most important
  28 // name in the tree is the name of the root node. Two trees with
  29 // different root node names are entirely disjoint, even if they
  30 // have leaves with common names.
  31 //
  32 // The second field identifies the type's parent node in the tree, or
  33 // is null or omitted for a root node. A type is considered to alias
  34 // all of its decendents and all of its ancestors in the tree.
  35 //
  36 // If the third field is present, it's an integer which if equal to 1
  37 // indicates that the type is "constant" (meaning pointsToConstantMemory
  38 // should return true; see
  39 // http://llvm.org/docs/AliasAnalysis.html#OtherItfs).
  40 //
  41 // TODO: The current metadata format doesn't support struct
  42 // fields. For example:
  43 //   struct X {
  44 //     double d;
  45 //     int i;
  46 //   };
  47 //   void foo(struct X *x, struct X *y, double *p) {
  48 //     *x = *y;
  49 //     *p = 0.0;
  50 //   }
  51 // Struct X has a double member, so the store to *x can alias the store to *p.
  52 // Currently it's not possible to precisely describe all the things struct X
  53 // aliases, so struct assignments must use conservative TBAA nodes. There's
  54 // no scheme for attaching metadata to @llvm.memcpy yet either.
  55 //
  56 //===----------------------------------------------------------------------===//
  57
  58 #include "llvm/Analysis/AliasAnalysis.h"
  59 #include "llvm/Analysis/Passes.h"
  60 #include "llvm/Module.h"
  61 #include "llvm/Metadata.h"
  62 #include "llvm/Pass.h"
  63 #include "llvm/Support/CommandLine.h"
  64 using namespace llvm;
  65
  66 // For testing purposes, enable TBAA only via a special option.
  67 static cl::opt<bool> EnableTBAA("enable-tbaa");
  68
  69 namespace {
  70   /// TBAANode - This is a simple wrapper around an MDNode which provides a
  71   /// higher-level interface by hiding the details of how alias analysis
  72   /// information is encoded in its operands.
  73   class TBAANode {
  74     const MDNode *Node;
  75
  76   public:
  77     TBAANode() : Node(0) {}
  78     explicit TBAANode(const MDNode *N) : Node(N) {}
  79
  80     /// getNode - Get the MDNode for this TBAANode.
  81     const MDNode *getNode() const { return Node; }
  82
  83     /// getParent - Get this TBAANode's Alias tree parent.
  84     TBAANode getParent() const {
  85       if (Node->getNumOperands() < 2)
  86         return TBAANode();
  87       MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(1));
  88       if (!P)
  89         return TBAANode();
  90       // Ok, this node has a valid parent. Return it.
  91       return TBAANode(P);
  92     }
  93
  94     /// TypeIsImmutable - Test if this TBAANode represents a type for objects
  95     /// which are not modified (by any means) in the context where this
  96     /// AliasAnalysis is relevant.
  97     bool TypeIsImmutable() const {
  98       if (Node->getNumOperands() < 3)
  99         return false;
 100       ConstantInt *CI = dyn_cast<ConstantInt>(Node->getOperand(2));
 101       if (!CI)
 102         return false;
 103       // TODO: Think about the encoding.
 104       return CI->isOne();
 105     }
 106   };
 107 }
 108
 109 namespace {
 110   /// TypeBasedAliasAnalysis - This is a simple alias analysis
 111   /// implementation that uses TypeBased to answer queries.
 112   class TypeBasedAliasAnalysis : public ImmutablePass,
 113                                  public AliasAnalysis {
 114   public:
 115     static char ID; // Class identification, replacement for typeinfo
 116     TypeBasedAliasAnalysis() : ImmutablePass(ID) {
 117       initializeTypeBasedAliasAnalysisPass(*PassRegistry::getPassRegistry());
 118     }
 119
 120     virtual void initializePass() {
 121       InitializeAliasAnalysis(this);
 122     }
 123
 124     /// getAdjustedAnalysisPointer - This method is used when a pass implements
 125     /// an analysis interface through multiple inheritance.  If needed, it
 126     /// should override this to adjust the this pointer as needed for the
 127     /// specified pass info.
 128     virtual void *getAdjustedAnalysisPointer(const void *PI) {
 129       if (PI == &AliasAnalysis::ID)
 130         return (AliasAnalysis*)this;
 131       return this;
 132     }
 133
 134     bool Aliases(const MDNode *A, const MDNode *B) const;
 135
 136   private:
 137     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 138     virtual AliasResult alias(const Location &LocA, const Location &LocB);
 139     virtual bool pointsToConstantMemory(const Location &Loc);
 140   };
 141 }  // End of anonymous namespace
 142
 143 // Register this pass...
 144 char TypeBasedAliasAnalysis::ID = 0;
 145 INITIALIZE_AG_PASS(TypeBasedAliasAnalysis, AliasAnalysis, "tbaa",
 146                    "Type-Based Alias Analysis", false, true, false)
 147
 148 ImmutablePass *llvm::createTypeBasedAliasAnalysisPass() {
 149   return new TypeBasedAliasAnalysis();
 150 }
 151
 152 void
 153 TypeBasedAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
 154   AU.setPreservesAll();
 155   AliasAnalysis::getAnalysisUsage(AU);
 156 }
 157
 158 /// Aliases - Test whether the type represented by A may alias the
 159 /// type represented by B.
 160 bool
 161 TypeBasedAliasAnalysis::Aliases(const MDNode *A,
 162                                 const MDNode *B) const {
 163   // Keep track of the root node for A and B.
 164   TBAANode RootA, RootB;
 165
 166   // Climb the tree from A to see if we reach B.
 167   for (TBAANode T(A); ; ) {
 168     if (T.getNode() == B)
 169       // B is an ancestor of A.
 170       return true;
 171
 172     RootA = T;
 173     T = T.getParent();
 174     if (!T.getNode())
 175       break;
 176   }
 177
 178   // Climb the tree from B to see if we reach A.
 179   for (TBAANode T(B); ; ) {
 180     if (T.getNode() == A)
 181       // A is an ancestor of B.
 182       return true;
 183
 184     RootB = T;
 185     T = T.getParent();
 186     if (!T.getNode())
 187       break;
 188   }
 189
 190   // Neither node is an ancestor of the other.
 191
 192   // If they have different roots, they're part of different potentially
 193   // unrelated type systems, so we must be conservative.
 194   if (RootA.getNode() != RootB.getNode())
 195     return true;
 196
 197   // If they have the same root, then we've proved there's no alias.
 198   return false;
 199 }
 200
 201 AliasAnalysis::AliasResult
 202 TypeBasedAliasAnalysis::alias(const Location &LocA,
 203                               const Location &LocB) {
 204   if (!EnableTBAA)
 205     return AliasAnalysis::alias(LocA, LocB);
 206
 207   // Get the attached MDNodes. If either value lacks a tbaa MDNode, we must
 208   // be conservative.
 209   const MDNode *AM = LocA.TBAATag;
 210   if (!AM) return AliasAnalysis::alias(LocA, LocB);
 211   const MDNode *BM = LocB.TBAATag;
 212   if (!BM) return AliasAnalysis::alias(LocA, LocB);
 213
 214   // If they may alias, chain to the next AliasAnalysis.
 215   if (Aliases(AM, BM))
 216     return AliasAnalysis::alias(LocA, LocB);
 217
 218   // Otherwise return a definitive result.
 219   return NoAlias;
 220 }
 221
 222 bool TypeBasedAliasAnalysis::pointsToConstantMemory(const Location &Loc) {
 223   if (!EnableTBAA)
 224     return AliasAnalysis::pointsToConstantMemory(Loc);
 225
 226   const MDNode *M = Loc.TBAATag;
 227   if (!M) return false;
 228
 229   // If this is an "immutable" type, we can assume the pointer is pointing
 230   // to constant memory.
 231   if (TBAANode(M).TypeIsImmutable())
 232     return true;
 233
 234   return AliasAnalysis::pointsToConstantMemory(Loc);
 235 }