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. Also,
  35 // a type is considered to alias all types in other trees, so that
  36 // bitcode produced from multiple front-ends is handled conservatively.
  37 //
  38 // If the third field is present, it's an integer which if equal to 1
  39 // indicates that the type is "constant" (meaning pointsToConstantMemory
  40 // should return true; see
  41 // http://llvm.org/docs/AliasAnalysis.html#OtherItfs).
  42 //
  43 // TODO: The current metadata format doesn't support struct
  44 // fields. For example:
  45 //   struct X {
  46 //     double d;
  47 //     int i;
  48 //   };
  49 //   void foo(struct X *x, struct X *y, double *p) {
  50 //     *x = *y;
  51 //     *p = 0.0;
  52 //   }
  53 // Struct X has a double member, so the store to *x can alias the store to *p.
  54 // Currently it's not possible to precisely describe all the things struct X
  55 // aliases, so struct assignments must use conservative TBAA nodes. There's
  56 // no scheme for attaching metadata to @llvm.memcpy yet either.
  57 //
  58 //===----------------------------------------------------------------------===//
  59
  60 #include "llvm/Analysis/AliasAnalysis.h"
  61 #include "llvm/Analysis/Passes.h"
  62 #include "llvm/LLVMContext.h"
  63 #include "llvm/Module.h"
  64 #include "llvm/Metadata.h"
  65 #include "llvm/Pass.h"
  66 #include "llvm/Support/CommandLine.h"
  67 using namespace llvm;
  68
  69 // A handy option for disabling TBAA functionality. The same effect can also be
  70 // achieved by stripping the !tbaa tags from IR, but this option is sometimes
  71 // more convenient.
  72 static cl::opt<bool> EnableTBAA("enable-tbaa", cl::init(true));
  73
  74 namespace {
  75   /// TBAANode - This is a simple wrapper around an MDNode which provides a
  76   /// higher-level interface by hiding the details of how alias analysis
  77   /// information is encoded in its operands.
  78   class TBAANode {
  79     const MDNode *Node;
  80
  81   public:
  82     TBAANode() : Node(0) {}
  83     explicit TBAANode(const MDNode *N) : Node(N) {}
  84
  85     /// getNode - Get the MDNode for this TBAANode.
  86     const MDNode *getNode() const { return Node; }
  87
  88     /// getParent - Get this TBAANode's Alias tree parent.
  89     TBAANode getParent() const {
  90       if (Node->getNumOperands() < 2)
  91         return TBAANode();
  92       MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(1));
  93       if (!P)
  94         return TBAANode();
  95       // Ok, this node has a valid parent. Return it.
  96       return TBAANode(P);
  97     }
  98
  99     /// TypeIsImmutable - Test if this TBAANode represents a type for objects
 100     /// which are not modified (by any means) in the context where this
 101     /// AliasAnalysis is relevant.
 102     bool TypeIsImmutable() const {
 103       if (Node->getNumOperands() < 3)
 104         return false;
 105       ConstantInt *CI = dyn_cast<ConstantInt>(Node->getOperand(2));
 106       if (!CI)
 107         return false;
 108       return CI->getValue()[0];
 109     }
 110   };
 111 }
 112
 113 namespace {
 114   /// TypeBasedAliasAnalysis - This is a simple alias analysis
 115   /// implementation that uses TypeBased to answer queries.
 116   class TypeBasedAliasAnalysis : public ImmutablePass,
 117                                  public AliasAnalysis {
 118   public:
 119     static char ID; // Class identification, replacement for typeinfo
 120     TypeBasedAliasAnalysis() : ImmutablePass(ID) {
 121       initializeTypeBasedAliasAnalysisPass(*PassRegistry::getPassRegistry());
 122     }
 123
 124     virtual void initializePass() {
 125       InitializeAliasAnalysis(this);
 126     }
 127
 128     /// getAdjustedAnalysisPointer - This method is used when a pass implements
 129     /// an analysis interface through multiple inheritance.  If needed, it
 130     /// should override this to adjust the this pointer as needed for the
 131     /// specified pass info.
 132     virtual void *getAdjustedAnalysisPointer(const void *PI) {
 133       if (PI == &AliasAnalysis::ID)
 134         return (AliasAnalysis*)this;
 135       return this;
 136     }
 137
 138     bool Aliases(const MDNode *A, const MDNode *B) const;
 139
 140   private:
 141     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 142     virtual AliasResult alias(const Location &LocA, const Location &LocB);
 143     virtual bool pointsToConstantMemory(const Location &Loc, bool OrLocal);
 144     virtual ModRefBehavior getModRefBehavior(ImmutableCallSite CS);
 145     virtual ModRefBehavior getModRefBehavior(const Function *F);
 146     virtual ModRefResult getModRefInfo(ImmutableCallSite CS,
 147                                        const Location &Loc);
 148     virtual ModRefResult getModRefInfo(ImmutableCallSite CS1,
 149                                        ImmutableCallSite CS2);
 150   };
 151 }  // End of anonymous namespace
 152
 153 // Register this pass...
 154 char TypeBasedAliasAnalysis::ID = 0;
 155 INITIALIZE_AG_PASS(TypeBasedAliasAnalysis, AliasAnalysis, "tbaa",
 156                    "Type-Based Alias Analysis", false, true, false)
 157
 158 ImmutablePass *llvm::createTypeBasedAliasAnalysisPass() {
 159   return new TypeBasedAliasAnalysis();
 160 }
 161
 162 void
 163 TypeBasedAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
 164   AU.setPreservesAll();
 165   AliasAnalysis::getAnalysisUsage(AU);
 166 }
 167
 168 /// Aliases - Test whether the type represented by A may alias the
 169 /// type represented by B.
 170 bool
 171 TypeBasedAliasAnalysis::Aliases(const MDNode *A,
 172                                 const MDNode *B) const {
 173   // Keep track of the root node for A and B.
 174   TBAANode RootA, RootB;
 175
 176   // Climb the tree from A to see if we reach B.
 177   for (TBAANode T(A); ; ) {
 178     if (T.getNode() == B)
 179       // B is an ancestor of A.
 180       return true;
 181
 182     RootA = T;
 183     T = T.getParent();
 184     if (!T.getNode())
 185       break;
 186   }
 187
 188   // Climb the tree from B to see if we reach A.
 189   for (TBAANode T(B); ; ) {
 190     if (T.getNode() == A)
 191       // A is an ancestor of B.
 192       return true;
 193
 194     RootB = T;
 195     T = T.getParent();
 196     if (!T.getNode())
 197       break;
 198   }
 199
 200   // Neither node is an ancestor of the other.
 201
 202   // If they have different roots, they're part of different potentially
 203   // unrelated type systems, so we must be conservative.
 204   if (RootA.getNode() != RootB.getNode())
 205     return true;
 206
 207   // If they have the same root, then we've proved there's no alias.
 208   return false;
 209 }
 210
 211 AliasAnalysis::AliasResult
 212 TypeBasedAliasAnalysis::alias(const Location &LocA,
 213                               const Location &LocB) {
 214   if (!EnableTBAA)
 215     return AliasAnalysis::alias(LocA, LocB);
 216
 217   // Get the attached MDNodes. If either value lacks a tbaa MDNode, we must
 218   // be conservative.
 219   const MDNode *AM = LocA.TBAATag;
 220   if (!AM) return AliasAnalysis::alias(LocA, LocB);
 221   const MDNode *BM = LocB.TBAATag;
 222   if (!BM) return AliasAnalysis::alias(LocA, LocB);
 223
 224   // If they may alias, chain to the next AliasAnalysis.
 225   if (Aliases(AM, BM))
 226     return AliasAnalysis::alias(LocA, LocB);
 227
 228   // Otherwise return a definitive result.
 229   return NoAlias;
 230 }
 231
 232 bool TypeBasedAliasAnalysis::pointsToConstantMemory(const Location &Loc,
 233                                                     bool OrLocal) {
 234   if (!EnableTBAA)
 235     return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal);
 236
 237   const MDNode *M = Loc.TBAATag;
 238   if (!M) return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal);
 239
 240   // If this is an "immutable" type, we can assume the pointer is pointing
 241   // to constant memory.
 242   if (TBAANode(M).TypeIsImmutable())
 243     return true;
 244
 245   return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal);
 246 }
 247
 248 AliasAnalysis::ModRefBehavior
 249 TypeBasedAliasAnalysis::getModRefBehavior(ImmutableCallSite CS) {
 250   if (!EnableTBAA)
 251     return AliasAnalysis::getModRefBehavior(CS);
 252
 253   ModRefBehavior Min = UnknownModRefBehavior;
 254
 255   // If this is an "immutable" type, we can assume the call doesn't write
 256   // to memory.
 257   if (const MDNode *M = CS.getInstruction()->getMetadata(LLVMContext::MD_tbaa))
 258     if (TBAANode(M).TypeIsImmutable())
 259       Min = OnlyReadsMemory;
 260
 261   return ModRefBehavior(AliasAnalysis::getModRefBehavior(CS) & Min);
 262 }
 263
 264 AliasAnalysis::ModRefBehavior
 265 TypeBasedAliasAnalysis::getModRefBehavior(const Function *F) {
 266   // Functions don't have metadata. Just chain to the next implementation.
 267   return AliasAnalysis::getModRefBehavior(F);
 268 }
 269
 270 AliasAnalysis::ModRefResult
 271 TypeBasedAliasAnalysis::getModRefInfo(ImmutableCallSite CS,
 272                                       const Location &Loc) {
 273   if (!EnableTBAA)
 274     return AliasAnalysis::getModRefInfo(CS, Loc);
 275
 276   if (const MDNode *L = Loc.TBAATag)
 277     if (const MDNode *M =
 278           CS.getInstruction()->getMetadata(LLVMContext::MD_tbaa))
 279       if (!Aliases(L, M))
 280         return NoModRef;
 281
 282   return AliasAnalysis::getModRefInfo(CS, Loc);
 283 }
 284
 285 AliasAnalysis::ModRefResult
 286 TypeBasedAliasAnalysis::getModRefInfo(ImmutableCallSite CS1,
 287                                       ImmutableCallSite CS2) {
 288   if (!EnableTBAA)
 289     return AliasAnalysis::getModRefInfo(CS1, CS2);
 290
 291   if (const MDNode *M1 =
 292         CS1.getInstruction()->getMetadata(LLVMContext::MD_tbaa))
 293     if (const MDNode *M2 =
 294           CS2.getInstruction()->getMetadata(LLVMContext::MD_tbaa))
 295       if (!Aliases(M1, M2))
 296         return NoModRef;
 297
 298   return AliasAnalysis::getModRefInfo(CS1, CS2);
 299 }