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