Line data Source code
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 :
35 : #include "llvm/Analysis/ScopedNoAliasAA.h"
36 : #include "llvm/ADT/SmallPtrSet.h"
37 : #include "llvm/Analysis/MemoryLocation.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"
43 : #include "llvm/Support/CommandLine.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), cl::Hidden);
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 0 : const MDNode *getDomain() const {
70 39673 : if (Node->getNumOperands() < 2)
71 0 : return nullptr;
72 : return dyn_cast_or_null<MDNode>(Node->getOperand(1));
73 : }
74 : };
75 :
76 : } // end anonymous namespace
77 :
78 6590440 : AliasResult ScopedNoAliasAAResult::alias(const MemoryLocation &LocA,
79 : const MemoryLocation &LocB) {
80 6590440 : if (!EnableScopedNoAlias)
81 : return AAResultBase::alias(LocA, LocB);
82 :
83 : // Get the attached MDNodes.
84 6590440 : const MDNode *AScopes = LocA.AATags.Scope, *BScopes = LocB.AATags.Scope;
85 :
86 6590440 : const MDNode *ANoAlias = LocA.AATags.NoAlias, *BNoAlias = LocB.AATags.NoAlias;
87 :
88 6590440 : if (!mayAliasInScopes(AScopes, BNoAlias))
89 : return NoAlias;
90 :
91 6584410 : if (!mayAliasInScopes(BScopes, ANoAlias))
92 5432 : return NoAlias;
93 :
94 : // If they may alias, chain to the next AliasAnalysis.
95 : return AAResultBase::alias(LocA, LocB);
96 : }
97 :
98 5407971 : ModRefInfo ScopedNoAliasAAResult::getModRefInfo(ImmutableCallSite CS,
99 : const MemoryLocation &Loc) {
100 5407971 : if (!EnableScopedNoAlias)
101 : return AAResultBase::getModRefInfo(CS, Loc);
102 :
103 5407971 : if (!mayAliasInScopes(Loc.AATags.Scope, CS.getInstruction()->getMetadata(
104 : LLVMContext::MD_noalias)))
105 : return ModRefInfo::NoModRef;
106 :
107 5407960 : if (!mayAliasInScopes(
108 : CS.getInstruction()->getMetadata(LLVMContext::MD_alias_scope),
109 5407960 : Loc.AATags.NoAlias))
110 43 : return ModRefInfo::NoModRef;
111 :
112 : return AAResultBase::getModRefInfo(CS, Loc);
113 : }
114 :
115 2172925 : ModRefInfo ScopedNoAliasAAResult::getModRefInfo(ImmutableCallSite CS1,
116 : ImmutableCallSite CS2) {
117 2172925 : if (!EnableScopedNoAlias)
118 : return AAResultBase::getModRefInfo(CS1, CS2);
119 :
120 2172925 : if (!mayAliasInScopes(
121 : CS1.getInstruction()->getMetadata(LLVMContext::MD_alias_scope),
122 : CS2.getInstruction()->getMetadata(LLVMContext::MD_noalias)))
123 : return ModRefInfo::NoModRef;
124 :
125 2172906 : if (!mayAliasInScopes(
126 : CS2.getInstruction()->getMetadata(LLVMContext::MD_alias_scope),
127 : CS1.getInstruction()->getMetadata(LLVMContext::MD_noalias)))
128 18 : return ModRefInfo::NoModRef;
129 :
130 : return AAResultBase::getModRefInfo(CS1, CS2);
131 : }
132 :
133 24193 : static void collectMDInDomain(const MDNode *List, const MDNode *Domain,
134 : SmallPtrSetImpl<const MDNode *> &Nodes) {
135 50030 : for (const MDOperand &MDOp : List->operands())
136 : if (const MDNode *MD = dyn_cast<MDNode>(MDOp))
137 25837 : if (AliasScopeNode(MD).getDomain() == Domain)
138 25599 : Nodes.insert(MD);
139 24193 : }
140 :
141 28336612 : bool ScopedNoAliasAAResult::mayAliasInScopes(const MDNode *Scopes,
142 : const MDNode *NoAlias) const {
143 28336612 : if (!Scopes || !NoAlias)
144 : return true;
145 :
146 : // Collect the set of scope domains relevant to the noalias scopes.
147 : SmallPtrSet<const MDNode *, 16> Domains;
148 26045 : for (const MDOperand &MDOp : NoAlias->operands())
149 : if (const MDNode *NAMD = dyn_cast<MDNode>(MDOp))
150 : if (const MDNode *Domain = AliasScopeNode(NAMD).getDomain())
151 13836 : 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 12868 : for (const MDNode *Domain : Domains) {
156 : SmallPtrSet<const MDNode *, 16> ScopeNodes;
157 12212 : collectMDInDomain(Scopes, Domain, ScopeNodes);
158 12212 : if (ScopeNodes.empty())
159 : continue;
160 :
161 : SmallPtrSet<const MDNode *, 16> NANodes;
162 11981 : collectMDInDomain(NoAlias, Domain, NANodes);
163 :
164 : // To not alias, all of the nodes in ScopeNodes must be in NANodes.
165 : bool FoundAll = true;
166 23540 : for (const MDNode *SMD : ScopeNodes)
167 11987 : if (!NANodes.count(SMD)) {
168 : FoundAll = false;
169 : break;
170 : }
171 :
172 11981 : if (FoundAll)
173 : return false;
174 : }
175 :
176 656 : return true;
177 : }
178 :
179 : AnalysisKey ScopedNoAliasAA::Key;
180 :
181 175 : ScopedNoAliasAAResult ScopedNoAliasAA::run(Function &F,
182 : FunctionAnalysisManager &AM) {
183 175 : return ScopedNoAliasAAResult();
184 : }
185 :
186 : char ScopedNoAliasAAWrapperPass::ID = 0;
187 :
188 211682 : INITIALIZE_PASS(ScopedNoAliasAAWrapperPass, "scoped-noalias",
189 : "Scoped NoAlias Alias Analysis", false, true)
190 :
191 30109 : ImmutablePass *llvm::createScopedNoAliasAAWrapperPass() {
192 30109 : return new ScopedNoAliasAAWrapperPass();
193 : }
194 :
195 60244 : ScopedNoAliasAAWrapperPass::ScopedNoAliasAAWrapperPass() : ImmutablePass(ID) {
196 30122 : initializeScopedNoAliasAAWrapperPassPass(*PassRegistry::getPassRegistry());
197 30122 : }
198 :
199 29980 : bool ScopedNoAliasAAWrapperPass::doInitialization(Module &M) {
200 29980 : Result.reset(new ScopedNoAliasAAResult());
201 29980 : return false;
202 : }
203 :
204 29828 : bool ScopedNoAliasAAWrapperPass::doFinalization(Module &M) {
205 : Result.reset();
206 29829 : return false;
207 : }
208 :
209 29984 : void ScopedNoAliasAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
210 : AU.setPreservesAll();
211 29984 : }
|
