lib/Analysis/ScopedNoAliasAA.cpp

   1 //===- ScopedNoAliasAA.cpp - Scoped No-Alias 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 ScopedNoAlias alias-analysis pass, which implements
  11 // metadata-based scoped no-alias support.
  12 //
  13 // Alias-analysis scopes are defined similar to TBAA nodes:
  14 //
  15 // !scope0 = metadata !{ metadata !"scope of foo()" }
  16 // !scope1 = metadata !{ metadata !"scope 1", metadata !scope0 }
  17 // !scope2 = metadata !{ metadata !"scope 2", metadata !scope0 }
  18 // !scope3 = metadata !{ metadata !"scope 2.1", metadata !scope2 }
  19 // !scope4 = metadata !{ metadata !"scope 2.2", metadata !scope2 }
  20 //
  21 // Loads and stores can be tagged with an alias-analysis scope, and also, with
  22 // a noalias tag for a specific scope:
  23 //
  24 // ... = load %ptr1, !alias.scope !{ !scope1 }
  25 // ... = load %ptr2, !alias.scope !{ !scope1, !scope2 }, !noalias !{ !scope1 }
  26 //
  27 // When evaluating an aliasing query, if one of the instructions is associated
  28 // with an alias.scope id that is identical to the noalias scope associated
  29 // with the other instruction, or is a descendant (in the scope hierarchy) of
  30 // the noalias scope associated with the other instruction, then the two memory
  31 // accesses are assumed not to alias.
  32 //
  33 // Note that if the first element of the scope metadata is a string, then it
  34 // can be combined accross functions and translation units. The string can be
  35 // replaced by a self-reference to create globally unqiue scope identifiers.
  36 //
  37 //===----------------------------------------------------------------------===//
  38
  39 #include "llvm/Analysis/Passes.h"
  40 #include "llvm/Analysis/AliasAnalysis.h"
  41 #include "llvm/IR/Constants.h"
  42 #include "llvm/IR/LLVMContext.h"
  43 #include "llvm/IR/Metadata.h"
  44 #include "llvm/IR/Module.h"
  45 #include "llvm/Pass.h"
  46 #include "llvm/Support/CommandLine.h"
  47 using namespace llvm;
  48
  49 // A handy option for disabling scoped no-alias functionality. The same effect
  50 // can also be achieved by stripping the associated metadata tags from IR, but
  51 // this option is sometimes more convenient.
  52 static cl::opt<bool>
  53 EnableScopedNoAlias("enable-scoped-noalias", cl::init(true));
  54
  55 namespace {
  56 /// AliasScopeNode - This is a simple wrapper around an MDNode which provides
  57 /// a higher-level interface by hiding the details of how alias analysis
  58 /// information is encoded in its operands.
  59 class AliasScopeNode {
  60   const MDNode *Node;
  61
  62 public:
  63   AliasScopeNode() : Node(0) {}
  64   explicit AliasScopeNode(const MDNode *N) : Node(N) {}
  65
  66   /// getNode - Get the MDNode for this AliasScopeNode.
  67   const MDNode *getNode() const { return Node; }
  68
  69   /// getParent - Get this AliasScopeNode's Alias tree parent.
  70   AliasScopeNode getParent() const {
  71     if (Node->getNumOperands() < 2)
  72       return AliasScopeNode();
  73     MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(1));
  74     if (!P)
  75       return AliasScopeNode();
  76     // Ok, this node has a valid parent. Return it.
  77     return AliasScopeNode(P);
  78   }
  79 };
  80
  81 /// ScopedNoAliasAA - This is a simple alias analysis
  82 /// implementation that uses scoped-noalias metadata to answer queries.
  83 class ScopedNoAliasAA : public ImmutablePass, public AliasAnalysis {
  84 public:
  85   static char ID; // Class identification, replacement for typeinfo
  86   ScopedNoAliasAA() : ImmutablePass(ID) {
  87     initializeScopedNoAliasAAPass(*PassRegistry::getPassRegistry());
  88   }
  89
  90   virtual void initializePass() {
  91     InitializeAliasAnalysis(this);
  92   }
  93
  94   /// getAdjustedAnalysisPointer - This method is used when a pass implements
  95   /// an analysis interface through multiple inheritance.  If needed, it
  96   /// should override this to adjust the this pointer as needed for the
  97   /// specified pass info.
  98   virtual void *getAdjustedAnalysisPointer(const void *PI) {
  99     if (PI == &AliasAnalysis::ID)
 100       return (AliasAnalysis*)this;
 101     return this;
 102   }
 103
 104 protected:
 105   bool mayAlias(const MDNode *A, const MDNode *B) const;
 106   bool mayAliasInScopes(const MDNode *Scopes, const MDNode *NoAlias) const;
 107
 108 private:
 109   virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 110   virtual AliasResult alias(const Location &LocA, const Location &LocB);
 111   virtual bool pointsToConstantMemory(const Location &Loc, bool OrLocal);
 112   virtual ModRefBehavior getModRefBehavior(ImmutableCallSite CS);
 113   virtual ModRefBehavior getModRefBehavior(const Function *F);
 114   virtual ModRefResult getModRefInfo(ImmutableCallSite CS,
 115                                      const Location &Loc);
 116   virtual ModRefResult getModRefInfo(ImmutableCallSite CS1,
 117                                      ImmutableCallSite CS2);
 118 };
 119 }  // End of anonymous namespace
 120
 121 // Register this pass...
 122 char ScopedNoAliasAA::ID = 0;
 123 INITIALIZE_AG_PASS(ScopedNoAliasAA, AliasAnalysis, "scoped-noalias",
 124                    "Scoped NoAlias Alias Analysis", false, true, false)
 125
 126 ImmutablePass *llvm::createScopedNoAliasAAPass() {
 127   return new ScopedNoAliasAA();
 128 }
 129
 130 void
 131 ScopedNoAliasAA::getAnalysisUsage(AnalysisUsage &AU) const {
 132   AU.setPreservesAll();
 133   AliasAnalysis::getAnalysisUsage(AU);
 134 }
 135
 136 /// mayAlias - Test whether the scope represented by A may alias the
 137 /// scope represented by B. Specifically, A is the target scope, and B is the
 138 /// noalias scope.
 139 bool
 140 ScopedNoAliasAA::mayAlias(const MDNode *A,
 141                           const MDNode *B) const {
 142   // Climb the tree from A to see if we reach B.
 143   for (AliasScopeNode T(A); ; ) {
 144     if (T.getNode() == B)
 145       // B is an ancestor of A.
 146       return false;
 147
 148     T = T.getParent();
 149     if (!T.getNode())
 150       break;
 151   }
 152
 153   return true;
 154 }
 155
 156 bool
 157 ScopedNoAliasAA::mayAliasInScopes(const MDNode *Scopes,
 158                                   const MDNode *NoAlias) const {
 159   if (!Scopes || !NoAlias)
 160     return true;
 161
 162   for (unsigned i = 0, ie = Scopes->getNumOperands(); i != ie; ++i)
 163     if (const MDNode *SMD = dyn_cast<MDNode>(Scopes->getOperand(i)))
 164       for (unsigned j = 0, je = NoAlias->getNumOperands(); j != je; ++j)
 165         if (const MDNode *NAMD = dyn_cast<MDNode>(NoAlias->getOperand(j)))
 166           if (!mayAlias(SMD, NAMD))
 167             return false;
 168
 169   return true;
 170 }
 171
 172 AliasAnalysis::AliasResult
 173 ScopedNoAliasAA::alias(const Location &LocA, const Location &LocB) {
 174   if (!EnableScopedNoAlias)
 175     return AliasAnalysis::alias(LocA, LocB);
 176
 177   // Get the attached MDNodes.
 178   const MDNode *AScopes = LocA.AATags.Scope,
 179                *BScopes = LocB.AATags.Scope;
 180
 181   const MDNode *ANoAlias = LocA.AATags.NoAlias,
 182                *BNoAlias = LocB.AATags.NoAlias;
 183
 184   if (!mayAliasInScopes(AScopes, BNoAlias))
 185     return NoAlias;
 186
 187   if (!mayAliasInScopes(BScopes, ANoAlias))
 188     return NoAlias;
 189
 190   // If they may alias, chain to the next AliasAnalysis.
 191   return AliasAnalysis::alias(LocA, LocB);
 192 }
 193
 194 bool ScopedNoAliasAA::pointsToConstantMemory(const Location &Loc,
 195                                              bool OrLocal) {
 196   return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal);
 197 }
 198
 199 AliasAnalysis::ModRefBehavior
 200 ScopedNoAliasAA::getModRefBehavior(ImmutableCallSite CS) {
 201   return AliasAnalysis::getModRefBehavior(CS);
 202 }
 203
 204 AliasAnalysis::ModRefBehavior
 205 ScopedNoAliasAA::getModRefBehavior(const Function *F) {
 206   return AliasAnalysis::getModRefBehavior(F);
 207 }
 208
 209 AliasAnalysis::ModRefResult
 210 ScopedNoAliasAA::getModRefInfo(ImmutableCallSite CS, const Location &Loc) {
 211   if (!EnableScopedNoAlias)
 212     return AliasAnalysis::getModRefInfo(CS, Loc);
 213
 214   if (!mayAliasInScopes(Loc.AATags.Scope,
 215         CS.getInstruction()->getMetadata(LLVMContext::MD_noalias)))
 216     return NoModRef;
 217
 218   if (!mayAliasInScopes(
 219         CS.getInstruction()->getMetadata(LLVMContext::MD_alias_scope),
 220         Loc.AATags.NoAlias))
 221     return NoModRef;
 222
 223   return AliasAnalysis::getModRefInfo(CS, Loc);
 224 }
 225
 226 AliasAnalysis::ModRefResult
 227 ScopedNoAliasAA::getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2) {
 228   if (!EnableScopedNoAlias)
 229     return AliasAnalysis::getModRefInfo(CS1, CS2);
 230
 231   if (!mayAliasInScopes(
 232         CS1.getInstruction()->getMetadata(LLVMContext::MD_alias_scope),
 233         CS2.getInstruction()->getMetadata(LLVMContext::MD_noalias)))
 234     return NoModRef;
 235
 236   if (!mayAliasInScopes(
 237         CS2.getInstruction()->getMetadata(LLVMContext::MD_alias_scope),
 238         CS1.getInstruction()->getMetadata(LLVMContext::MD_noalias)))
 239     return NoModRef;
 240
 241   return AliasAnalysis::getModRefInfo(CS1, CS2);
 242 }
 243