LLVM  10.0.0svn
ScopedNoAliasAA.cpp
Go to the documentation of this file.
1 //===- ScopedNoAliasAA.cpp - Scoped No-Alias Alias Analysis ---------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines the ScopedNoAlias alias-analysis pass, which implements
10 // metadata-based scoped no-alias support.
11 //
12 // Alias-analysis scopes are defined by an id (which can be a string or some
13 // other metadata node), a domain node, and an optional descriptive string.
14 // A domain is defined by an id (which can be a string or some other metadata
15 // node), and an optional descriptive string.
16 //
17 // !dom0 = metadata !{ metadata !"domain of foo()" }
18 // !scope1 = metadata !{ metadata !scope1, metadata !dom0, metadata !"scope 1" }
19 // !scope2 = metadata !{ metadata !scope2, metadata !dom0, metadata !"scope 2" }
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 // has a set of noalias scopes in some domain that is a superset of the alias
29 // scopes in that domain of some other instruction, then the two memory
30 // accesses are assumed not to alias.
31 //
32 //===----------------------------------------------------------------------===//
33 
35 #include "llvm/ADT/SmallPtrSet.h"
37 #include "llvm/IR/Instruction.h"
38 #include "llvm/IR/LLVMContext.h"
39 #include "llvm/IR/Metadata.h"
40 #include "llvm/Pass.h"
41 #include "llvm/Support/Casting.h"
43 
44 using namespace llvm;
45 
46 // A handy option for disabling scoped no-alias functionality. The same effect
47 // can also be achieved by stripping the associated metadata tags from IR, but
48 // this option is sometimes more convenient.
49 static cl::opt<bool> EnableScopedNoAlias("enable-scoped-noalias",
50  cl::init(true), cl::Hidden);
51 
52 namespace {
53 
54 /// This is a simple wrapper around an MDNode which provides a higher-level
55 /// interface by hiding the details of how alias analysis information is encoded
56 /// in its operands.
57 class AliasScopeNode {
58  const MDNode *Node = nullptr;
59 
60 public:
61  AliasScopeNode() = default;
62  explicit AliasScopeNode(const MDNode *N) : Node(N) {}
63 
64  /// Get the MDNode for this AliasScopeNode.
65  const MDNode *getNode() const { return Node; }
66 
67  /// Get the MDNode for this AliasScopeNode's domain.
68  const MDNode *getDomain() const {
69  if (Node->getNumOperands() < 2)
70  return nullptr;
71  return dyn_cast_or_null<MDNode>(Node->getOperand(1));
72  }
73 };
74 
75 } // end anonymous namespace
76 
78  const MemoryLocation &LocB,
79  AAQueryInfo &AAQI) {
81  return AAResultBase::alias(LocA, LocB, AAQI);
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, AAQI);
96 }
97 
99  const MemoryLocation &Loc,
100  AAQueryInfo &AAQI) {
101  if (!EnableScopedNoAlias)
102  return AAResultBase::getModRefInfo(Call, Loc, AAQI);
103 
104  if (!mayAliasInScopes(Loc.AATags.Scope,
105  Call->getMetadata(LLVMContext::MD_noalias)))
106  return ModRefInfo::NoModRef;
107 
108  if (!mayAliasInScopes(Call->getMetadata(LLVMContext::MD_alias_scope),
109  Loc.AATags.NoAlias))
110  return ModRefInfo::NoModRef;
111 
112  return AAResultBase::getModRefInfo(Call, Loc, AAQI);
113 }
114 
116  const CallBase *Call2,
117  AAQueryInfo &AAQI) {
118  if (!EnableScopedNoAlias)
119  return AAResultBase::getModRefInfo(Call1, Call2, AAQI);
120 
121  if (!mayAliasInScopes(Call1->getMetadata(LLVMContext::MD_alias_scope),
122  Call2->getMetadata(LLVMContext::MD_noalias)))
123  return ModRefInfo::NoModRef;
124 
125  if (!mayAliasInScopes(Call2->getMetadata(LLVMContext::MD_alias_scope),
126  Call1->getMetadata(LLVMContext::MD_noalias)))
127  return ModRefInfo::NoModRef;
128 
129  return AAResultBase::getModRefInfo(Call1, Call2, AAQI);
130 }
131 
132 static void collectMDInDomain(const MDNode *List, const MDNode *Domain,
134  for (const MDOperand &MDOp : List->operands())
135  if (const MDNode *MD = dyn_cast<MDNode>(MDOp))
136  if (AliasScopeNode(MD).getDomain() == Domain)
137  Nodes.insert(MD);
138 }
139 
140 bool ScopedNoAliasAAResult::mayAliasInScopes(const MDNode *Scopes,
141  const MDNode *NoAlias) const {
142  if (!Scopes || !NoAlias)
143  return true;
144 
145  // Collect the set of scope domains relevant to the noalias scopes.
147  for (const MDOperand &MDOp : NoAlias->operands())
148  if (const MDNode *NAMD = dyn_cast<MDNode>(MDOp))
149  if (const MDNode *Domain = AliasScopeNode(NAMD).getDomain())
150  Domains.insert(Domain);
151 
152  // We alias unless, for some domain, the set of noalias scopes in that domain
153  // is a superset of the set of alias scopes in that domain.
154  for (const MDNode *Domain : Domains) {
156  collectMDInDomain(Scopes, Domain, ScopeNodes);
157  if (ScopeNodes.empty())
158  continue;
159 
161  collectMDInDomain(NoAlias, Domain, NANodes);
162 
163  // To not alias, all of the nodes in ScopeNodes must be in NANodes.
164  bool FoundAll = true;
165  for (const MDNode *SMD : ScopeNodes)
166  if (!NANodes.count(SMD)) {
167  FoundAll = false;
168  break;
169  }
170 
171  if (FoundAll)
172  return false;
173  }
174 
175  return true;
176 }
177 
178 AnalysisKey ScopedNoAliasAA::Key;
179 
182  return ScopedNoAliasAAResult();
183 }
184 
186 
188  "Scoped NoAlias Alias Analysis", false, true)
189 
191  return new ScopedNoAliasAAWrapperPass();
192 }
193 
196 }
197 
199  Result.reset(new ScopedNoAliasAAResult());
200  return false;
201 }
202 
204  Result.reset();
205  return false;
206 }
207 
209  AU.setPreservesAll();
210 }
Tracking metadata reference owned by Metadata.
Definition: Metadata.h:710
The access neither references nor modifies the value stored in memory.
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:660
This class represents lattice values for constants.
Definition: AllocatorList.h:23
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
This class stores info we want to provide to or retain within an alias query.
This file contains the declarations for metadata subclasses.
This is the interface for a metadata-based scoped no-alias analysis.
The two locations do not alias at all.
Definition: AliasAnalysis.h:84
INITIALIZE_PASS(ScopedNoAliasAAWrapperPass, "scoped-noalias", "Scoped NoAlias Alias Analysis", false, true) ImmutablePass *llvm
Metadata node.
Definition: Metadata.h:863
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1100
F(f)
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1068
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI)
ImmutablePass * createScopedNoAliasAAWrapperPass()
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
A simple AA result which uses scoped-noalias metadata to answer queries.
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI)
op_range operands() const
Definition: Metadata.h:1066
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:244
void initializeScopedNoAliasAAWrapperPassPass(PassRegistry &)
AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:78
Legacy wrapper pass to provide the ScopedNoAliasAAResult object.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:91
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:370
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:381
Representation for a specific memory location.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
ImmutablePass class - This class is used to provide information that does not need to be run...
Definition: Pass.h:255
static void collectMDInDomain(const MDNode *List, const MDNode *Domain, SmallPtrSetImpl< const MDNode *> &Nodes)
MDNode * NoAlias
The tag specifying the noalias scope.
Definition: Metadata.h:663
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.
const NodeList & List
Definition: RDFGraph.cpp:201
#define N
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, AAQueryInfo &AAQI)
static cl::opt< bool > EnableScopedNoAlias("enable-scoped-noalias", cl::init(true), cl::Hidden)
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
A container for analyses that lazily runs them and caches their results.
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1074
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, AAQueryInfo &AAQI)
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)