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: AA chaining
  27 // TODO: struct fields
  28 //
  29 //===----------------------------------------------------------------------===//
  30
  31 #include "llvm/Analysis/AliasAnalysis.h"
  32 #include "llvm/Analysis/Passes.h"
  33 #include "llvm/Module.h"
  34 #include "llvm/Metadata.h"
  35 #include "llvm/Pass.h"
  36 using namespace llvm;
  37
  38 namespace {
  39   /// TBAANode - This is a simple wrapper around an MDNode which provides a
  40   /// higher-level interface by hiding the details of how alias analysis
  41   /// information is encoded in its operands.
  42   class TBAANode {
  43     const MDNode *Node;
  44
  45   public:
  46     TBAANode() : Node(0) {}
  47     explicit TBAANode(MDNode *N) : Node(N) {}
  48
  49     /// getNode - Get the MDNode for this TBAANode.
  50     const MDNode *getNode() const { return Node; }
  51
  52     /// getParent - Get this TBAANode's Alias DAG parent.
  53     TBAANode getParent() const {
  54       if (Node->getNumOperands() < 2)
  55         return TBAANode();
  56       MDNode *P = dyn_cast<MDNode>(Node->getOperand(1));
  57       if (!P)
  58         return TBAANode();
  59       // Ok, this node has a valid parent. Return it.
  60       return TBAANode(P);
  61     }
  62
  63     /// TypeIsImmutable - Test if this TBAANode represents a type for objects
  64     /// which are not modified (by any means) in the context where this
  65     /// AliasAnalysis is relevant.
  66     bool TypeIsImmutable() const {
  67       if (Node->getNumOperands() < 3)
  68         return false;
  69       ConstantInt *CI = dyn_cast<ConstantInt>(Node->getOperand(2));
  70       if (!CI)
  71         return false;
  72       // TODO: Think about the encoding.
  73       return CI->isOne();
  74     }
  75   };
  76 }
  77
  78 namespace {
  79   /// TypeBasedAliasAnalysis - This is a simple alias analysis
  80   /// implementation that uses TypeBased to answer queries.
  81   class TypeBasedAliasAnalysis : public ImmutablePass,
  82                                  public AliasAnalysis {
  83   public:
  84     static char ID; // Class identification, replacement for typeinfo
  85     TypeBasedAliasAnalysis() : ImmutablePass(ID) {}
  86
  87     /// getAdjustedAnalysisPointer - This method is used when a pass implements
  88     /// an analysis interface through multiple inheritance.  If needed, it
  89     /// should override this to adjust the this pointer as needed for the
  90     /// specified pass info.
  91     virtual void *getAdjustedAnalysisPointer(const void *PI) {
  92       if (PI == &AliasAnalysis::ID)
  93         return (AliasAnalysis*)this;
  94       return this;
  95     }
  96
  97   private:
  98     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
  99     virtual AliasResult alias(const Value *V1, unsigned V1Size,
 100                               const Value *V2, unsigned V2Size);
 101     virtual bool pointsToConstantMemory(const Value *P);
 102   };
 103 }  // End of anonymous namespace
 104
 105 // Register this pass...
 106 char TypeBasedAliasAnalysis::ID = 0;
 107 INITIALIZE_AG_PASS(TypeBasedAliasAnalysis, AliasAnalysis, "tbaa",
 108                    "Type-Based Alias Analysis", false, true, false);
 109
 110 ImmutablePass *llvm::createTypeBasedAliasAnalysisPass() {
 111   return new TypeBasedAliasAnalysis();
 112 }
 113
 114 void
 115 TypeBasedAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
 116   AU.setPreservesAll();
 117   AliasAnalysis::getAnalysisUsage(AU);
 118 }
 119
 120 AliasAnalysis::AliasResult
 121 TypeBasedAliasAnalysis::alias(const Value *A, unsigned ASize,
 122                               const Value *B, unsigned BSize) {
 123   // Currently, metadata can only be attached to Instructions.
 124   const Instruction *AI = dyn_cast<Instruction>(A);
 125   if (!AI) return MayAlias;
 126   const Instruction *BI = dyn_cast<Instruction>(B);
 127   if (!BI) return MayAlias;
 128
 129   // Get the attached MDNodes. If either value lacks a tbaa MDNode, we must
 130   // be conservative.
 131   MDNode *AM =
 132     AI->getMetadata(AI->getParent()->getParent()->getParent()
 133                       ->getMDKindID("tbaa"));
 134   if (!AM) return MayAlias;
 135   MDNode *BM =
 136     BI->getMetadata(BI->getParent()->getParent()->getParent()
 137                       ->getMDKindID("tbaa"));
 138   if (!BM) return MayAlias;
 139
 140   // Keep track of the root node for A and B.
 141   TBAANode RootA, RootB;
 142
 143   // Climb the DAG from A to see if we reach B.
 144   for (TBAANode T(AM); ; ) {
 145     if (T.getNode() == BM)
 146       // B is an ancestor of A.
 147       return MayAlias;
 148
 149     RootA = T;
 150     T = T.getParent();
 151     if (!T.getNode())
 152       break;
 153   }
 154
 155   // Climb the DAG from B to see if we reach A.
 156   for (TBAANode T(BM); ; ) {
 157     if (T.getNode() == AM)
 158       // A is an ancestor of B.
 159       return MayAlias;
 160
 161     RootB = T;
 162     T = T.getParent();
 163     if (!T.getNode())
 164       break;
 165   }
 166
 167   // Neither node is an ancestor of the other.
 168
 169   // If they have the same root, then we've proved there's no alias.
 170   if (RootA.getNode() == RootB.getNode())
 171     return NoAlias;
 172
 173   // If they have different roots, they're part of different potentially
 174   // unrelated type systems, so we must be conservative.
 175   return MayAlias;
 176 }
 177
 178 bool TypeBasedAliasAnalysis::pointsToConstantMemory(const Value *P) {
 179   // Currently, metadata can only be attached to Instructions.
 180   const Instruction *I = dyn_cast<Instruction>(P);
 181   if (!I) return false;
 182
 183   MDNode *M =
 184     I->getMetadata(I->getParent()->getParent()->getParent()
 185                     ->getMDKindID("tbaa"));
 186   if (!M) return false;
 187
 188   // If this is an "immutable" type, we can assume the pointer is pointing
 189   // to constant memory.
 190   return TBAANode(M).TypeIsImmutable();
 191 }