/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Analysis/ScopedNoAliasAA.cpp
Line | Count | Source (jump to first uncovered line) |
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/SmallPtrSet.h" |
36 | | #include "llvm/Analysis/MemoryLocation.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" |
42 | | #include "llvm/Support/CommandLine.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 | 862k | explicit AliasScopeNode(const MDNode *N) : Node(N) {} |
63 | | |
64 | | /// Get the MDNode for this AliasScopeNode. |
65 | 0 | const MDNode *getNode() const { return Node; } |
66 | | |
67 | | /// Get the MDNode for this AliasScopeNode's domain. |
68 | 862k | const MDNode *getDomain() const { |
69 | 862k | if (Node->getNumOperands() < 2) |
70 | 0 | return nullptr; |
71 | 862k | return dyn_cast_or_null<MDNode>(Node->getOperand(1)); |
72 | 862k | } |
73 | | }; |
74 | | |
75 | | } // end anonymous namespace |
76 | | |
77 | | AliasResult ScopedNoAliasAAResult::alias(const MemoryLocation &LocA, |
78 | | const MemoryLocation &LocB, |
79 | 43.3M | AAQueryInfo &AAQI) { |
80 | 43.3M | if (!EnableScopedNoAlias) |
81 | 0 | return AAResultBase::alias(LocA, LocB, AAQI); |
82 | 43.3M | |
83 | 43.3M | // Get the attached MDNodes. |
84 | 43.3M | const MDNode *AScopes = LocA.AATags.Scope, *BScopes = LocB.AATags.Scope; |
85 | 43.3M | |
86 | 43.3M | const MDNode *ANoAlias = LocA.AATags.NoAlias, *BNoAlias = LocB.AATags.NoAlias; |
87 | 43.3M | |
88 | 43.3M | if (!mayAliasInScopes(AScopes, BNoAlias)) |
89 | 89.9k | return NoAlias; |
90 | 43.2M | |
91 | 43.2M | if (!mayAliasInScopes(BScopes, ANoAlias)) |
92 | 105k | return NoAlias; |
93 | 43.1M | |
94 | 43.1M | // If they may alias, chain to the next AliasAnalysis. |
95 | 43.1M | return AAResultBase::alias(LocA, LocB, AAQI); |
96 | 43.1M | } |
97 | | |
98 | | ModRefInfo ScopedNoAliasAAResult::getModRefInfo(const CallBase *Call, |
99 | | const MemoryLocation &Loc, |
100 | 7.93M | AAQueryInfo &AAQI) { |
101 | 7.93M | if (!EnableScopedNoAlias) |
102 | 0 | return AAResultBase::getModRefInfo(Call, Loc, AAQI); |
103 | 7.93M | |
104 | 7.93M | if (!mayAliasInScopes(Loc.AATags.Scope, |
105 | 7.93M | Call->getMetadata(LLVMContext::MD_noalias))) |
106 | 1.93k | return ModRefInfo::NoModRef; |
107 | 7.93M | |
108 | 7.93M | if (!mayAliasInScopes(Call->getMetadata(LLVMContext::MD_alias_scope), |
109 | 7.93M | Loc.AATags.NoAlias)) |
110 | 1.08k | return ModRefInfo::NoModRef; |
111 | 7.93M | |
112 | 7.93M | return AAResultBase::getModRefInfo(Call, Loc, AAQI); |
113 | 7.93M | } |
114 | | |
115 | | ModRefInfo ScopedNoAliasAAResult::getModRefInfo(const CallBase *Call1, |
116 | | const CallBase *Call2, |
117 | 818k | AAQueryInfo &AAQI) { |
118 | 818k | if (!EnableScopedNoAlias) |
119 | 0 | return AAResultBase::getModRefInfo(Call1, Call2, AAQI); |
120 | 818k | |
121 | 818k | if (!mayAliasInScopes(Call1->getMetadata(LLVMContext::MD_alias_scope), |
122 | 818k | Call2->getMetadata(LLVMContext::MD_noalias))) |
123 | 203 | return ModRefInfo::NoModRef; |
124 | 817k | |
125 | 817k | if (!mayAliasInScopes(Call2->getMetadata(LLVMContext::MD_alias_scope), |
126 | 817k | Call1->getMetadata(LLVMContext::MD_noalias))) |
127 | 0 | return ModRefInfo::NoModRef; |
128 | 817k | |
129 | 817k | return AAResultBase::getModRefInfo(Call1, Call2, AAQI); |
130 | 817k | } |
131 | | |
132 | | static void collectMDInDomain(const MDNode *List, const MDNode *Domain, |
133 | 484k | SmallPtrSetImpl<const MDNode *> &Nodes) { |
134 | 484k | for (const MDOperand &MDOp : List->operands()) |
135 | 552k | if (const MDNode *MD = dyn_cast<MDNode>(MDOp)) |
136 | 552k | if (AliasScopeNode(MD).getDomain() == Domain) |
137 | 432k | Nodes.insert(MD); |
138 | 484k | } |
139 | | |
140 | | bool ScopedNoAliasAAResult::mayAliasInScopes(const MDNode *Scopes, |
141 | 104M | const MDNode *NoAlias) const { |
142 | 104M | if (!Scopes || !NoAlias609k ) |
143 | 103M | return true; |
144 | 242k | |
145 | 242k | // Collect the set of scope domains relevant to the noalias scopes. |
146 | 242k | SmallPtrSet<const MDNode *, 16> Domains; |
147 | 242k | for (const MDOperand &MDOp : NoAlias->operands()) |
148 | 310k | if (const MDNode *NAMD = dyn_cast<MDNode>(MDOp)) |
149 | 310k | if (const MDNode *Domain = AliasScopeNode(NAMD).getDomain()) |
150 | 310k | Domains.insert(Domain); |
151 | 242k | |
152 | 242k | // We alias unless, for some domain, the set of noalias scopes in that domain |
153 | 242k | // is a superset of the set of alias scopes in that domain. |
154 | 276k | for (const MDNode *Domain : Domains) { |
155 | 276k | SmallPtrSet<const MDNode *, 16> ScopeNodes; |
156 | 276k | collectMDInDomain(Scopes, Domain, ScopeNodes); |
157 | 276k | if (ScopeNodes.empty()) |
158 | 69.1k | continue; |
159 | 207k | |
160 | 207k | SmallPtrSet<const MDNode *, 16> NANodes; |
161 | 207k | collectMDInDomain(NoAlias, Domain, NANodes); |
162 | 207k | |
163 | 207k | // To not alias, all of the nodes in ScopeNodes must be in NANodes. |
164 | 207k | bool FoundAll = true; |
165 | 207k | for (const MDNode *SMD : ScopeNodes) |
166 | 207k | if (!NANodes.count(SMD)) { |
167 | 8.95k | FoundAll = false; |
168 | 8.95k | break; |
169 | 8.95k | } |
170 | 207k | |
171 | 207k | if (FoundAll) |
172 | 198k | return false; |
173 | 207k | } |
174 | 242k | |
175 | 242k | return true43.4k ; |
176 | 242k | } |
177 | | |
178 | | AnalysisKey ScopedNoAliasAA::Key; |
179 | | |
180 | | ScopedNoAliasAAResult ScopedNoAliasAA::run(Function &F, |
181 | 2.56k | FunctionAnalysisManager &AM) { |
182 | 2.56k | return ScopedNoAliasAAResult(); |
183 | 2.56k | } |
184 | | |
185 | | char ScopedNoAliasAAWrapperPass::ID = 0; |
186 | | |
187 | | INITIALIZE_PASS(ScopedNoAliasAAWrapperPass, "scoped-noalias", |
188 | | "Scoped NoAlias Alias Analysis", false, true) |
189 | | |
190 | 62.3k | ImmutablePass *llvm::createScopedNoAliasAAWrapperPass() { |
191 | 62.3k | return new ScopedNoAliasAAWrapperPass(); |
192 | 62.3k | } |
193 | | |
194 | 62.4k | ScopedNoAliasAAWrapperPass::ScopedNoAliasAAWrapperPass() : ImmutablePass(ID) { |
195 | 62.4k | initializeScopedNoAliasAAWrapperPassPass(*PassRegistry::getPassRegistry()); |
196 | 62.4k | } |
197 | | |
198 | 62.1k | bool ScopedNoAliasAAWrapperPass::doInitialization(Module &M) { |
199 | 62.1k | Result.reset(new ScopedNoAliasAAResult()); |
200 | 62.1k | return false; |
201 | 62.1k | } |
202 | | |
203 | 62.0k | bool ScopedNoAliasAAWrapperPass::doFinalization(Module &M) { |
204 | 62.0k | Result.reset(); |
205 | 62.0k | return false; |
206 | 62.0k | } |
207 | | |
208 | 62.1k | void ScopedNoAliasAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { |
209 | 62.1k | AU.setPreservesAll(); |
210 | 62.1k | } |