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