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