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 
34 #include "llvm/Analysis/ScopedNoAliasAA.h"
35 #include "llvm/ADT/SetOperations.h"
36 #include "llvm/ADT/SmallPtrSet.h"
37 #include "llvm/Analysis/MemoryLocation.h"
38 #include "llvm/IR/InstrTypes.h"
39 #include "llvm/IR/LLVMContext.h"
40 #include "llvm/IR/Metadata.h"
41 #include "llvm/InitializePasses.h"
42 #include "llvm/Pass.h"
43 #include "llvm/Support/Casting.h"
44 #include "llvm/Support/CommandLine.h"
45 
46 using namespace llvm;
47 
48 // A handy option for disabling scoped no-alias functionality. The same effect
49 // can also be achieved by stripping the associated metadata tags from IR, but
50 // this option is sometimes more convenient.
51 static cl::opt<bool> EnableScopedNoAlias("enable-scoped-noalias",
52                                          cl::init(true), cl::Hidden);
53 
54 AliasResult ScopedNoAliasAAResult::alias(const MemoryLocation &LocA,
55                                          const MemoryLocation &LocB,
56                                          AAQueryInfo &AAQI,
57                                          const Instruction *) {
58   if (!EnableScopedNoAlias)
59     return AAResultBase::alias(LocA, LocB, AAQI, nullptr);
60 
61   // Get the attached MDNodes.
62   const MDNode *AScopes = LocA.AATags.Scope, *BScopes = LocB.AATags.Scope;
63 
64   const MDNode *ANoAlias = LocA.AATags.NoAlias, *BNoAlias = LocB.AATags.NoAlias;
65 
66   if (!mayAliasInScopes(AScopes, BNoAlias))
67     return AliasResult::NoAlias;
68 
69   if (!mayAliasInScopes(BScopes, ANoAlias))
70     return AliasResult::NoAlias;
71 
72   // If they may alias, chain to the next AliasAnalysis.
73   return AAResultBase::alias(LocA, LocB, AAQI, nullptr);
74 }
75 
76 ModRefInfo ScopedNoAliasAAResult::getModRefInfo(const CallBase *Call,
77                                                 const MemoryLocation &Loc,
78                                                 AAQueryInfo &AAQI) {
79   if (!EnableScopedNoAlias)
80     return AAResultBase::getModRefInfo(Call, Loc, AAQI);
81 
82   if (!mayAliasInScopes(Loc.AATags.Scope,
83                         Call->getMetadata(LLVMContext::MD_noalias)))
84     return ModRefInfo::NoModRef;
85 
86   if (!mayAliasInScopes(Call->getMetadata(LLVMContext::MD_alias_scope),
87                         Loc.AATags.NoAlias))
88     return ModRefInfo::NoModRef;
89 
90   return AAResultBase::getModRefInfo(Call, Loc, AAQI);
91 }
92 
93 ModRefInfo ScopedNoAliasAAResult::getModRefInfo(const CallBase *Call1,
94                                                 const CallBase *Call2,
95                                                 AAQueryInfo &AAQI) {
96   if (!EnableScopedNoAlias)
97     return AAResultBase::getModRefInfo(Call1, Call2, AAQI);
98 
99   if (!mayAliasInScopes(Call1->getMetadata(LLVMContext::MD_alias_scope),
100                         Call2->getMetadata(LLVMContext::MD_noalias)))
101     return ModRefInfo::NoModRef;
102 
103   if (!mayAliasInScopes(Call2->getMetadata(LLVMContext::MD_alias_scope),
104                         Call1->getMetadata(LLVMContext::MD_noalias)))
105     return ModRefInfo::NoModRef;
106 
107   return AAResultBase::getModRefInfo(Call1, Call2, AAQI);
108 }
109 
110 static void collectMDInDomain(const MDNode *List, const MDNode *Domain,
111                               SmallPtrSetImpl<const MDNode *> &Nodes) {
112   for (const MDOperand &MDOp : List->operands())
113     if (const MDNode *MD = dyn_cast<MDNode>(MDOp))
114       if (AliasScopeNode(MD).getDomain() == Domain)
115         Nodes.insert(MD);
116 }
117 
118 bool ScopedNoAliasAAResult::mayAliasInScopes(const MDNode *Scopes,
119                                              const MDNode *NoAlias) const {
120   if (!Scopes || !NoAlias)
121     return true;
122 
123   // Collect the set of scope domains relevant to the noalias scopes.
124   SmallPtrSet<const MDNode *, 16> Domains;
125   for (const MDOperand &MDOp : NoAlias->operands())
126     if (const MDNode *NAMD = dyn_cast<MDNode>(MDOp))
127       if (const MDNode *Domain = AliasScopeNode(NAMD).getDomain())
128         Domains.insert(Domain);
129 
130   // We alias unless, for some domain, the set of noalias scopes in that domain
131   // is a superset of the set of alias scopes in that domain.
132   for (const MDNode *Domain : Domains) {
133     SmallPtrSet<const MDNode *, 16> ScopeNodes;
134     collectMDInDomain(Scopes, Domain, ScopeNodes);
135     if (ScopeNodes.empty())
136       continue;
137 
138     SmallPtrSet<const MDNode *, 16> NANodes;
139     collectMDInDomain(NoAlias, Domain, NANodes);
140 
141     // To not alias, all of the nodes in ScopeNodes must be in NANodes.
142     if (llvm::set_is_subset(ScopeNodes, NANodes))
143       return false;
144   }
145 
146   return true;
147 }
148 
149 AnalysisKey ScopedNoAliasAA::Key;
150 
151 ScopedNoAliasAAResult ScopedNoAliasAA::run(Function &F,
152                                            FunctionAnalysisManager &AM) {
153   return ScopedNoAliasAAResult();
154 }
155 
156 char ScopedNoAliasAAWrapperPass::ID = 0;
157 
158 INITIALIZE_PASS(ScopedNoAliasAAWrapperPass, "scoped-noalias-aa",
159                 "Scoped NoAlias Alias Analysis", false, true)
160 
161 ImmutablePass *llvm::createScopedNoAliasAAWrapperPass() {
162   return new ScopedNoAliasAAWrapperPass();
163 }
164 
165 ScopedNoAliasAAWrapperPass::ScopedNoAliasAAWrapperPass() : ImmutablePass(ID) {
166   initializeScopedNoAliasAAWrapperPassPass(*PassRegistry::getPassRegistry());
167 }
168 
169 bool ScopedNoAliasAAWrapperPass::doInitialization(Module &M) {
170   Result.reset(new ScopedNoAliasAAResult());
171   return false;
172 }
173 
174 bool ScopedNoAliasAAWrapperPass::doFinalization(Module &M) {
175   Result.reset();
176   return false;
177 }
178 
179 void ScopedNoAliasAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
180   AU.setPreservesAll();
181 }
182