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), a flag saying whether its scopes are disjoint, and an optional
16// descriptive string.
17//
18// !dom0 = metadata !{ metadata !"domain of foo()", i1 false }
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
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// If a domain is declared as having disjoint scopes, two memory accesses are
34// assumed not to alias if the they both have entries for that domain in their
35// `alias.scope` list and their `alias.scope` lists have no scopes in common for
36// that domain. Equivalently, an instruction with a set of scopes from a
37// disjoint-scope domain in its `alias.scope` list implicitly has all other
38// scopes in that domain in its `noalias` set. For example,
39//
40// !dom1 = metadata !{ metadata !dom1, i1 true, metadata !"disjoint domain" }
41// !scope3 = metadata !{ metadata !scope3, metadata !dom1 }
42// !scope4 = metadata !{ metadata !scope4, metadata !dom1 }
43//
44// ... = load %ptr3, !alias.scope !{ !scope3 } ; doesn't alias the load below
45// ... = load %ptr4, !alias.scope !{ !scope4 }
46//
47//===----------------------------------------------------------------------===//
48
49#include "llvm/Analysis/ScopedNoAliasAA.h"
50#include "llvm/ADT/SetOperations.h"
51#include "llvm/ADT/SmallPtrSet.h"
52#include "llvm/Analysis/MemoryLocation.h"
53#include "llvm/IR/InstrTypes.h"
54#include "llvm/IR/Instructions.h"
55#include "llvm/IR/LLVMContext.h"
56#include "llvm/IR/Metadata.h"
57#include "llvm/InitializePasses.h"
58#include "llvm/Pass.h"
59#include "llvm/Support/Casting.h"
60#include "llvm/Support/CommandLine.h"
61
62using namespace llvm;
63
64// A handy option for disabling scoped no-alias functionality. The same effect
65// can also be achieved by stripping the associated metadata tags from IR, but
66// this option is sometimes more convenient.
67static cl::opt<bool> EnableScopedNoAlias("enable-scoped-noalias",
68 cl::init(Val: true), cl::Hidden);
69
70AliasResult ScopedNoAliasAAResult::alias(const MemoryLocation &LocA,
71 const MemoryLocation &LocB) {
72 if (!EnableScopedNoAlias)
73 return AliasResult::MayAlias;
74
75 // Get the attached MDNodes.
76 const MDNode *AScopes = LocA.AATags.Scope, *BScopes = LocB.AATags.Scope;
77
78 const MDNode *ANoAlias = LocA.AATags.NoAlias, *BNoAlias = LocB.AATags.NoAlias;
79
80 if (!mayAliasInScopes(Scopes: AScopes, NoAlias: BNoAlias))
81 return AliasResult::NoAlias;
82
83 if (!mayAliasInScopes(Scopes: BScopes, NoAlias: ANoAlias))
84 return AliasResult::NoAlias;
85
86 if (!mayAliasInDisjointDomains(Scopes1: AScopes, Scopes2: BScopes))
87 return AliasResult::NoAlias;
88
89 return AliasResult::MayAlias;
90}
91
92AliasResult ScopedNoAliasAAResult::alias(const MemoryLocation &LocA,
93 const MemoryLocation &LocB,
94 AAQueryInfo &, const Instruction *) {
95 return alias(LocA, LocB);
96}
97
98ModRefInfo ScopedNoAliasAAResult::getModRefInfo(const CallBase *Call,
99 const MemoryLocation &Loc,
100 AAQueryInfo &AAQI) {
101 if (!EnableScopedNoAlias)
102 return ModRefInfo::ModRef;
103
104 if (!mayAliasInScopes(Scopes: Loc.AATags.Scope,
105 NoAlias: Call->getMetadata(KindID: LLVMContext::MD_noalias)))
106 return ModRefInfo::NoModRef;
107
108 if (!mayAliasInScopes(Scopes: Call->getMetadata(KindID: LLVMContext::MD_alias_scope),
109 NoAlias: Loc.AATags.NoAlias))
110 return ModRefInfo::NoModRef;
111
112 if (!mayAliasInDisjointDomains(
113 Scopes1: Loc.AATags.Scope, Scopes2: Call->getMetadata(KindID: LLVMContext::MD_alias_scope)))
114 return ModRefInfo::NoModRef;
115
116 return ModRefInfo::ModRef;
117}
118
119ModRefInfo ScopedNoAliasAAResult::getModRefInfo(const FenceInst *F,
120 const MemoryLocation &Loc,
121 AAQueryInfo &AAQI) {
122 if (!EnableScopedNoAlias)
123 return ModRefInfo::ModRef;
124
125 if (!mayAliasInScopes(Scopes: Loc.AATags.Scope,
126 NoAlias: F->getMetadata(KindID: LLVMContext::MD_noalias)))
127 return ModRefInfo::NoModRef;
128
129 if (!mayAliasInScopes(Scopes: F->getMetadata(KindID: LLVMContext::MD_alias_scope),
130 NoAlias: Loc.AATags.NoAlias))
131 return ModRefInfo::NoModRef;
132
133 if (!mayAliasInDisjointDomains(Scopes1: Loc.AATags.Scope,
134 Scopes2: F->getMetadata(KindID: LLVMContext::MD_alias_scope)))
135 return ModRefInfo::NoModRef;
136
137 return ModRefInfo::ModRef;
138}
139
140ModRefInfo ScopedNoAliasAAResult::getModRefInfo(const CallBase *Call1,
141 const CallBase *Call2,
142 AAQueryInfo &AAQI) {
143 if (!EnableScopedNoAlias)
144 return ModRefInfo::ModRef;
145
146 if (!mayAliasInScopes(Scopes: Call1->getMetadata(KindID: LLVMContext::MD_alias_scope),
147 NoAlias: Call2->getMetadata(KindID: LLVMContext::MD_noalias)))
148 return ModRefInfo::NoModRef;
149
150 if (!mayAliasInScopes(Scopes: Call2->getMetadata(KindID: LLVMContext::MD_alias_scope),
151 NoAlias: Call1->getMetadata(KindID: LLVMContext::MD_noalias)))
152 return ModRefInfo::NoModRef;
153
154 if (!mayAliasInDisjointDomains(
155 Scopes1: Call1->getMetadata(KindID: LLVMContext::MD_alias_scope),
156 Scopes2: Call2->getMetadata(KindID: LLVMContext::MD_alias_scope)))
157 return ModRefInfo::NoModRef;
158
159 return ModRefInfo::ModRef;
160}
161
162static void collectMDInDomain(const MDNode *List, const MDNode *Domain,
163 SmallPtrSetImpl<const MDNode *> &Nodes) {
164 for (const MDOperand &MDOp : List->operands())
165 if (const MDNode *MD = dyn_cast<MDNode>(Val: MDOp))
166 if (AliasScopeNode(MD).getDomain() == Domain)
167 Nodes.insert(Ptr: MD);
168}
169
170/// Collect the set of scoped domains relevant to the noalias scopes.
171void ScopedNoAliasAAResult::collectScopedDomains(
172 const MDNode *NoAlias, SmallPtrSetImpl<const MDNode *> &Domains,
173 bool DisjointOnly) {
174 if (!NoAlias)
175 return;
176 assert(Domains.empty() && "Domains should be empty");
177 for (const MDOperand &MDOp : NoAlias->operands())
178 if (const MDNode *NAMD = dyn_cast<MDNode>(Val: MDOp))
179 if (const MDNode *Domain = AliasScopeNode(NAMD).getDomain())
180 if (!DisjointOnly || AliasScopeDomainNode(Domain).hasDisjointScopes())
181 Domains.insert(Ptr: Domain);
182}
183
184bool ScopedNoAliasAAResult::mayAliasInScopes(const MDNode *Scopes,
185 const MDNode *NoAlias) {
186 if (!Scopes || !NoAlias)
187 return true;
188
189 // Collect the set of scope domains relevant to the noalias scopes.
190 SmallPtrSet<const MDNode *, 16> Domains;
191 collectScopedDomains(NoAlias, Domains);
192
193 // We alias unless, for some domain, the set of noalias scopes in that domain
194 // is a superset of the set of alias scopes in that domain.
195 for (const MDNode *Domain : Domains) {
196 SmallPtrSet<const MDNode *, 16> ScopeNodes;
197 collectMDInDomain(List: Scopes, Domain, Nodes&: ScopeNodes);
198 if (ScopeNodes.empty())
199 continue;
200
201 SmallPtrSet<const MDNode *, 16> NANodes;
202 collectMDInDomain(List: NoAlias, Domain, Nodes&: NANodes);
203
204 // To not alias, all of the nodes in ScopeNodes must be in NANodes.
205 if (llvm::set_is_subset(S1: ScopeNodes, S2: NANodes))
206 return false;
207 }
208
209 return true;
210}
211
212bool ScopedNoAliasAAResult::mayAliasInDisjointDomains(const MDNode *Scopes1,
213 const MDNode *Scopes2) {
214 if (!Scopes1 || !Scopes2)
215 return true;
216
217 // Collect the domains with disjoint scopes that the first access is in.
218 SmallPtrSet<const MDNode *, 16> Domains;
219 collectScopedDomains(NoAlias: Scopes1, Domains, /*DisjointOnly=*/true);
220
221 // The accesses don't alias if, for some domain, both accesses use at least
222 // one of its scopes and have no scopes in that domain in common.
223 for (const MDNode *Domain : Domains) {
224 SmallPtrSet<const MDNode *, 16> Nodes2;
225 collectMDInDomain(List: Scopes2, Domain, Nodes&: Nodes2);
226 if (Nodes2.empty())
227 continue;
228
229 SmallPtrSet<const MDNode *, 16> Nodes1;
230 collectMDInDomain(List: Scopes1, Domain, Nodes&: Nodes1);
231 if (!llvm::set_intersects(S1: Nodes1, S2: Nodes2))
232 return false;
233 }
234
235 return true;
236}
237
238AnalysisKey ScopedNoAliasAA::Key;
239
240ScopedNoAliasAAResult ScopedNoAliasAA::run(Function &F,
241 FunctionAnalysisManager &AM) {
242 return ScopedNoAliasAAResult();
243}
244
245char ScopedNoAliasAAWrapperPass::ID = 0;
246
247INITIALIZE_PASS(ScopedNoAliasAAWrapperPass, "scoped-noalias-aa",
248 "Scoped NoAlias Alias Analysis", false, true)
249
250ImmutablePass *llvm::createScopedNoAliasAAWrapperPass() {
251 return new ScopedNoAliasAAWrapperPass();
252}
253
254ScopedNoAliasAAWrapperPass::ScopedNoAliasAAWrapperPass() : ImmutablePass(ID) {}
255
256bool ScopedNoAliasAAWrapperPass::doInitialization(Module &M) {
257 Result.reset(p: new ScopedNoAliasAAResult());
258 return false;
259}
260
261bool ScopedNoAliasAAWrapperPass::doFinalization(Module &M) {
262 Result.reset();
263 return false;
264}
265
266void ScopedNoAliasAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
267 AU.setPreservesAll();
268}
269