LLVM  6.0.0svn
ScopedNoAliasAA.cpp
Go to the documentation of this file.
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 by an id (which can be a string or some
14 // other metadata node), a domain node, and an optional descriptive string.
15 // A domain is defined by an id (which can be a string or some other metadata
16 // node), and an optional descriptive string.
17 //
18 // !dom0 = metadata !{ metadata !"domain of foo()" }
19 // !scope1 = metadata !{ metadata !scope1, metadata !dom0, metadata !"scope 1" }
20 // !scope2 = metadata !{ metadata !scope2, metadata !dom0, metadata !"scope 2" }
21 //
22 // Loads and stores can be tagged with an alias-analysis scope, and also, with
23 // a noalias tag for a specific scope:
24 //
25 // ... = load %ptr1, !alias.scope !{ !scope1 }
26 // ... = load %ptr2, !alias.scope !{ !scope1, !scope2 }, !noalias !{ !scope1 }
27 //
28 // When evaluating an aliasing query, if one of the instructions is associated
29 // has a set of noalias scopes in some domain that is a superset of the alias
30 // scopes in that domain of some other instruction, then the two memory
31 // accesses are assumed not to alias.
32 //
33 //===----------------------------------------------------------------------===//
34 
36 #include "llvm/ADT/SmallPtrSet.h"
38 #include "llvm/IR/Instruction.h"
39 #include "llvm/IR/LLVMContext.h"
40 #include "llvm/IR/Metadata.h"
41 #include "llvm/Pass.h"
42 #include "llvm/Support/Casting.h"
44 
45 using namespace llvm;
46 
47 // A handy option for disabling scoped no-alias functionality. The same effect
48 // can also be achieved by stripping the associated metadata tags from IR, but
49 // this option is sometimes more convenient.
50 static cl::opt<bool> EnableScopedNoAlias("enable-scoped-noalias",
51  cl::init(true));
52 
53 namespace {
54 
55 /// This is a simple wrapper around an MDNode which provides a higher-level
56 /// interface by hiding the details of how alias analysis information is encoded
57 /// in its operands.
58 class AliasScopeNode {
59  const MDNode *Node = nullptr;
60 
61 public:
62  AliasScopeNode() = default;
63  explicit AliasScopeNode(const MDNode *N) : Node(N) {}
64 
65  /// Get the MDNode for this AliasScopeNode.
66  const MDNode *getNode() const { return Node; }
67 
68  /// Get the MDNode for this AliasScopeNode's domain.
69  const MDNode *getDomain() const {
70  if (Node->getNumOperands() < 2)
71  return nullptr;
72  return dyn_cast_or_null<MDNode>(Node->getOperand(1));
73  }
74 };
75 
76 } // end anonymous namespace
77 
79  const MemoryLocation &LocB) {
81  return AAResultBase::alias(LocA, LocB);
82 
83  // Get the attached MDNodes.
84  const MDNode *AScopes = LocA.AATags.Scope, *BScopes = LocB.AATags.Scope;
85 
86  const MDNode *ANoAlias = LocA.AATags.NoAlias, *BNoAlias = LocB.AATags.NoAlias;
87 
88  if (!mayAliasInScopes(AScopes, BNoAlias))
89  return NoAlias;
90 
91  if (!mayAliasInScopes(BScopes, ANoAlias))
92  return NoAlias;
93 
94  // If they may alias, chain to the next AliasAnalysis.
95  return AAResultBase::alias(LocA, LocB);
96 }
97 
99  const MemoryLocation &Loc) {
100  if (!EnableScopedNoAlias)
101  return AAResultBase::getModRefInfo(CS, Loc);
102 
103  if (!mayAliasInScopes(Loc.AATags.Scope, CS.getInstruction()->getMetadata(
105  return MRI_NoModRef;
106 
107  if (!mayAliasInScopes(
109  Loc.AATags.NoAlias))
110  return MRI_NoModRef;
111 
112  return AAResultBase::getModRefInfo(CS, Loc);
113 }
114 
116  ImmutableCallSite CS2) {
117  if (!EnableScopedNoAlias)
118  return AAResultBase::getModRefInfo(CS1, CS2);
119 
120  if (!mayAliasInScopes(
123  return MRI_NoModRef;
124 
125  if (!mayAliasInScopes(
128  return MRI_NoModRef;
129 
130  return AAResultBase::getModRefInfo(CS1, CS2);
131 }
132 
133 static void collectMDInDomain(const MDNode *List, const MDNode *Domain,
135  for (const MDOperand &MDOp : List->operands())
136  if (const MDNode *MD = dyn_cast<MDNode>(MDOp))
137  if (AliasScopeNode(MD).getDomain() == Domain)
138  Nodes.insert(MD);
139 }
140 
141 bool ScopedNoAliasAAResult::mayAliasInScopes(const MDNode *Scopes,
142  const MDNode *NoAlias) const {
143  if (!Scopes || !NoAlias)
144  return true;
145 
146  // Collect the set of scope domains relevant to the noalias scopes.
148  for (const MDOperand &MDOp : NoAlias->operands())
149  if (const MDNode *NAMD = dyn_cast<MDNode>(MDOp))
150  if (const MDNode *Domain = AliasScopeNode(NAMD).getDomain())
151  Domains.insert(Domain);
152 
153  // We alias unless, for some domain, the set of noalias scopes in that domain
154  // is a superset of the set of alias scopes in that domain.
155  for (const MDNode *Domain : Domains) {
157  collectMDInDomain(Scopes, Domain, ScopeNodes);
158  if (ScopeNodes.empty())
159  continue;
160 
162  collectMDInDomain(NoAlias, Domain, NANodes);
163 
164  // To not alias, all of the nodes in ScopeNodes must be in NANodes.
165  bool FoundAll = true;
166  for (const MDNode *SMD : ScopeNodes)
167  if (!NANodes.count(SMD)) {
168  FoundAll = false;
169  break;
170  }
171 
172  if (FoundAll)
173  return false;
174  }
175 
176  return true;
177 }
178 
179 AnalysisKey ScopedNoAliasAA::Key;
180 
183  return ScopedNoAliasAAResult();
184 }
185 
187 
189  "Scoped NoAlias Alias Analysis", false, true)
190 
192  return new ScopedNoAliasAAWrapperPass();
193 }
194 
197 }
198 
200  Result.reset(new ScopedNoAliasAAResult());
201  return false;
202 }
203 
205  Result.reset();
206  return false;
207 }
208 
210  AU.setPreservesAll();
211 }
Tracking metadata reference owned by Metadata.
Definition: Metadata.h:709
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
MDNode * Scope
The tag for alias scope specification (used with noalias).
Definition: Metadata.h:659
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
This file contains the declarations for metadata subclasses.
This is the interface for a metadata-based scoped no-alias analysis.
INITIALIZE_PASS(ScopedNoAliasAAWrapperPass, "scoped-noalias", "Scoped NoAlias Alias Analysis", false, true) ImmutablePass *llvm
Metadata node.
Definition: Metadata.h:862
The two locations do not alias at all.
Definition: AliasAnalysis.h:85
F(f)
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1067
ImmutablePass * createScopedNoAliasAAWrapperPass()
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
A simple AA result which uses scoped-noalias metadata to answer queries.
InstrTy * getInstruction() const
Definition: CallSite.h:92
static cl::opt< bool > EnableScopedNoAlias("enable-scoped-noalias", cl::init(true))
op_range operands() const
Definition: Metadata.h:1065
bool doFinalization(Module &M) override
doFinalization - Virtual method overriden by subclasses to do any necessary clean up after all passes...
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:194
void initializeScopedNoAliasAAWrapperPassPass(PassRegistry &)
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
The access neither references nor modifies the value stored in memory.
Legacy wrapper pass to provide the ScopedNoAliasAAResult object.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:406
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:92
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:371
AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:79
Represent the analysis usage information of a pass.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
Representation for a specific memory location.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
ImmutablePass class - This class is used to provide information that does not need to be run...
Definition: Pass.h:256
static void collectMDInDomain(const MDNode *List, const MDNode *Domain, SmallPtrSetImpl< const MDNode *> &Nodes)
MDNode * NoAlias
The tag specifying the noalias scope.
Definition: Metadata.h:662
void setPreservesAll()
Set by analyses that do not transform their input at all.
bool doInitialization(Module &M) override
doInitialization - Virtual method overridden by subclasses to do any necessary initialization before ...
AAMDNodes AATags
The metadata nodes which describes the aliasing of the location (each member is null if that kind of ...
This file provides utility analysis objects describing memory locations.
Establish a view to a call site for examination.
Definition: CallSite.h:713
const NodeList & List
Definition: RDFGraph.cpp:210
#define N
ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc)
ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc)
A container for analyses that lazily runs them and caches their results.
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1073
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70
ScopedNoAliasAAResult run(Function &F, FunctionAnalysisManager &AM)