/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Analysis/CFLSteensAliasAnalysis.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===- CFLSteensAliasAnalysis.cpp - Unification-based 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 implements a CFL-base, summary-based alias analysis algorithm. It |
10 | | // does not depend on types. The algorithm is a mixture of the one described in |
11 | | // "Demand-driven alias analysis for C" by Xin Zheng and Radu Rugina, and "Fast |
12 | | // algorithms for Dyck-CFL-reachability with applications to Alias Analysis" by |
13 | | // Zhang Q, Lyu M R, Yuan H, and Su Z. -- to summarize the papers, we build a |
14 | | // graph of the uses of a variable, where each node is a memory location, and |
15 | | // each edge is an action that happened on that memory location. The "actions" |
16 | | // can be one of Dereference, Reference, or Assign. The precision of this |
17 | | // analysis is roughly the same as that of an one level context-sensitive |
18 | | // Steensgaard's algorithm. |
19 | | // |
20 | | // Two variables are considered as aliasing iff you can reach one value's node |
21 | | // from the other value's node and the language formed by concatenating all of |
22 | | // the edge labels (actions) conforms to a context-free grammar. |
23 | | // |
24 | | // Because this algorithm requires a graph search on each query, we execute the |
25 | | // algorithm outlined in "Fast algorithms..." (mentioned above) |
26 | | // in order to transform the graph into sets of variables that may alias in |
27 | | // ~nlogn time (n = number of variables), which makes queries take constant |
28 | | // time. |
29 | | //===----------------------------------------------------------------------===// |
30 | | |
31 | | // N.B. AliasAnalysis as a whole is phrased as a FunctionPass at the moment, and |
32 | | // CFLSteensAA is interprocedural. This is *technically* A Bad Thing, because |
33 | | // FunctionPasses are only allowed to inspect the Function that they're being |
34 | | // run on. Realistically, this likely isn't a problem until we allow |
35 | | // FunctionPasses to run concurrently. |
36 | | |
37 | | #include "llvm/Analysis/CFLSteensAliasAnalysis.h" |
38 | | #include "AliasAnalysisSummary.h" |
39 | | #include "CFLGraph.h" |
40 | | #include "StratifiedSets.h" |
41 | | #include "llvm/ADT/DenseMap.h" |
42 | | #include "llvm/ADT/Optional.h" |
43 | | #include "llvm/ADT/SmallVector.h" |
44 | | #include "llvm/Analysis/TargetLibraryInfo.h" |
45 | | #include "llvm/IR/Constants.h" |
46 | | #include "llvm/IR/Function.h" |
47 | | #include "llvm/IR/Type.h" |
48 | | #include "llvm/IR/Value.h" |
49 | | #include "llvm/Pass.h" |
50 | | #include "llvm/Support/Debug.h" |
51 | | #include "llvm/Support/raw_ostream.h" |
52 | | #include <algorithm> |
53 | | #include <cassert> |
54 | | #include <limits> |
55 | | #include <memory> |
56 | | #include <utility> |
57 | | |
58 | | using namespace llvm; |
59 | | using namespace llvm::cflaa; |
60 | | |
61 | | #define DEBUG_TYPE "cfl-steens-aa" |
62 | | |
63 | | CFLSteensAAResult::CFLSteensAAResult(const TargetLibraryInfo &TLI) |
64 | 77 | : AAResultBase(), TLI(TLI) {} |
65 | | CFLSteensAAResult::CFLSteensAAResult(CFLSteensAAResult &&Arg) |
66 | 84 | : AAResultBase(std::move(Arg)), TLI(Arg.TLI) {} |
67 | 161 | CFLSteensAAResult::~CFLSteensAAResult() = default; |
68 | | |
69 | | /// Information we have about a function and would like to keep around. |
70 | | class CFLSteensAAResult::FunctionInfo { |
71 | | StratifiedSets<InstantiatedValue> Sets; |
72 | | AliasSummary Summary; |
73 | | |
74 | | public: |
75 | | FunctionInfo(Function &Fn, const SmallVectorImpl<Value *> &RetVals, |
76 | | StratifiedSets<InstantiatedValue> S); |
77 | | |
78 | 2.79k | const StratifiedSets<InstantiatedValue> &getStratifiedSets() const { |
79 | 2.79k | return Sets; |
80 | 2.79k | } |
81 | | |
82 | 64 | const AliasSummary &getAliasSummary() const { return Summary; } |
83 | | }; |
84 | | |
85 | | const StratifiedIndex StratifiedLink::SetSentinel = |
86 | | std::numeric_limits<StratifiedIndex>::max(); |
87 | | |
88 | | //===----------------------------------------------------------------------===// |
89 | | // Function declarations that require types defined in the namespace above |
90 | | //===----------------------------------------------------------------------===// |
91 | | |
92 | | /// Determines whether it would be pointless to add the given Value to our sets. |
93 | 932 | static bool canSkipAddingToSets(Value *Val) { |
94 | 932 | // Constants can share instances, which may falsely unify multiple |
95 | 932 | // sets, e.g. in |
96 | 932 | // store i32* null, i32** %ptr1 |
97 | 932 | // store i32* null, i32** %ptr2 |
98 | 932 | // clearly ptr1 and ptr2 should not be unified into the same set, so |
99 | 932 | // we should filter out the (potentially shared) instance to |
100 | 932 | // i32* null. |
101 | 932 | if (isa<Constant>(Val)) { |
102 | 48 | // TODO: Because all of these things are constant, we can determine whether |
103 | 48 | // the data is *actually* mutable at graph building time. This will probably |
104 | 48 | // come for free/cheap with offset awareness. |
105 | 48 | bool CanStoreMutableData = isa<GlobalValue>(Val) || |
106 | 48 | isa<ConstantExpr>(Val)12 || |
107 | 48 | isa<ConstantAggregate>(Val)0 ; |
108 | 48 | return !CanStoreMutableData; |
109 | 48 | } |
110 | 884 | |
111 | 884 | return false; |
112 | 884 | } |
113 | | |
114 | | CFLSteensAAResult::FunctionInfo::FunctionInfo( |
115 | | Function &Fn, const SmallVectorImpl<Value *> &RetVals, |
116 | | StratifiedSets<InstantiatedValue> S) |
117 | 116 | : Sets(std::move(S)) { |
118 | 116 | // Historically, an arbitrary upper-bound of 50 args was selected. We may want |
119 | 116 | // to remove this if it doesn't really matter in practice. |
120 | 116 | if (Fn.arg_size() > MaxSupportedArgsInSummary) |
121 | 0 | return; |
122 | 116 | |
123 | 116 | DenseMap<StratifiedIndex, InterfaceValue> InterfaceMap; |
124 | 116 | |
125 | 116 | // Our intention here is to record all InterfaceValues that share the same |
126 | 116 | // StratifiedIndex in RetParamRelations. For each valid InterfaceValue, we |
127 | 116 | // have its StratifiedIndex scanned here and check if the index is presented |
128 | 116 | // in InterfaceMap: if it is not, we add the correspondence to the map; |
129 | 116 | // otherwise, an aliasing relation is found and we add it to |
130 | 116 | // RetParamRelations. |
131 | 116 | |
132 | 116 | auto AddToRetParamRelations = [&](unsigned InterfaceIndex, |
133 | 164 | StratifiedIndex SetIndex) { |
134 | 164 | unsigned Level = 0; |
135 | 321 | while (true) { |
136 | 321 | InterfaceValue CurrValue{InterfaceIndex, Level}; |
137 | 321 | |
138 | 321 | auto Itr = InterfaceMap.find(SetIndex); |
139 | 321 | if (Itr != InterfaceMap.end()) { |
140 | 33 | if (CurrValue != Itr->second) |
141 | 33 | Summary.RetParamRelations.push_back( |
142 | 33 | ExternalRelation{CurrValue, Itr->second, UnknownOffset}); |
143 | 33 | break; |
144 | 33 | } |
145 | 288 | |
146 | 288 | auto &Link = Sets.getLink(SetIndex); |
147 | 288 | InterfaceMap.insert(std::make_pair(SetIndex, CurrValue)); |
148 | 288 | auto ExternalAttrs = getExternallyVisibleAttrs(Link.Attrs); |
149 | 288 | if (ExternalAttrs.any()) |
150 | 35 | Summary.RetParamAttributes.push_back( |
151 | 35 | ExternalAttribute{CurrValue, ExternalAttrs}); |
152 | 288 | |
153 | 288 | if (!Link.hasBelow()) |
154 | 131 | break; |
155 | 157 | |
156 | 157 | ++Level; |
157 | 157 | SetIndex = Link.Below; |
158 | 157 | } |
159 | 164 | }; |
160 | 116 | |
161 | 116 | // Populate RetParamRelations for return values |
162 | 116 | for (auto *RetVal : RetVals) { |
163 | 24 | assert(RetVal != nullptr); |
164 | 24 | assert(RetVal->getType()->isPointerTy()); |
165 | 24 | auto RetInfo = Sets.find(InstantiatedValue{RetVal, 0}); |
166 | 24 | if (RetInfo.hasValue()) |
167 | 24 | AddToRetParamRelations(0, RetInfo->Index); |
168 | 24 | } |
169 | 116 | |
170 | 116 | // Populate RetParamRelations for parameters |
171 | 116 | unsigned I = 0; |
172 | 152 | for (auto &Param : Fn.args()) { |
173 | 152 | if (Param.getType()->isPointerTy()) { |
174 | 140 | auto ParamInfo = Sets.find(InstantiatedValue{&Param, 0}); |
175 | 140 | if (ParamInfo.hasValue()) |
176 | 140 | AddToRetParamRelations(I + 1, ParamInfo->Index); |
177 | 140 | } |
178 | 152 | ++I; |
179 | 152 | } |
180 | 116 | } |
181 | | |
182 | | // Builds the graph + StratifiedSets for a function. |
183 | 116 | CFLSteensAAResult::FunctionInfo CFLSteensAAResult::buildSetsFrom(Function *Fn) { |
184 | 116 | CFLGraphBuilder<CFLSteensAAResult> GraphBuilder(*this, TLI, *Fn); |
185 | 116 | StratifiedSetsBuilder<InstantiatedValue> SetBuilder; |
186 | 116 | |
187 | 116 | // Add all CFLGraph nodes and all Dereference edges to StratifiedSets |
188 | 116 | auto &Graph = GraphBuilder.getCFLGraph(); |
189 | 466 | for (const auto &Mapping : Graph.value_mappings()) { |
190 | 466 | auto Val = Mapping.first; |
191 | 466 | if (canSkipAddingToSets(Val)) |
192 | 0 | continue; |
193 | 466 | auto &ValueInfo = Mapping.second; |
194 | 466 | |
195 | 466 | assert(ValueInfo.getNumLevels() > 0); |
196 | 466 | SetBuilder.add(InstantiatedValue{Val, 0}); |
197 | 466 | SetBuilder.noteAttributes(InstantiatedValue{Val, 0}, |
198 | 466 | ValueInfo.getNodeInfoAtLevel(0).Attr); |
199 | 724 | for (unsigned I = 0, E = ValueInfo.getNumLevels() - 1; I < E; ++I258 ) { |
200 | 258 | SetBuilder.add(InstantiatedValue{Val, I + 1}); |
201 | 258 | SetBuilder.noteAttributes(InstantiatedValue{Val, I + 1}, |
202 | 258 | ValueInfo.getNodeInfoAtLevel(I + 1).Attr); |
203 | 258 | SetBuilder.addBelow(InstantiatedValue{Val, I}, |
204 | 258 | InstantiatedValue{Val, I + 1}); |
205 | 258 | } |
206 | 466 | } |
207 | 116 | |
208 | 116 | // Add all assign edges to StratifiedSets |
209 | 466 | for (const auto &Mapping : Graph.value_mappings()) { |
210 | 466 | auto Val = Mapping.first; |
211 | 466 | if (canSkipAddingToSets(Val)) |
212 | 0 | continue; |
213 | 466 | auto &ValueInfo = Mapping.second; |
214 | 466 | |
215 | 1.19k | for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I724 ) { |
216 | 724 | auto Src = InstantiatedValue{Val, I}; |
217 | 724 | for (auto &Edge : ValueInfo.getNodeInfoAtLevel(I).Edges) |
218 | 219 | SetBuilder.addWith(Src, Edge.Other); |
219 | 724 | } |
220 | 466 | } |
221 | 116 | |
222 | 116 | return FunctionInfo(*Fn, GraphBuilder.getReturnValues(), SetBuilder.build()); |
223 | 116 | } |
224 | | |
225 | 116 | void CFLSteensAAResult::scan(Function *Fn) { |
226 | 116 | auto InsertPair = Cache.insert(std::make_pair(Fn, Optional<FunctionInfo>())); |
227 | 116 | (void)InsertPair; |
228 | 116 | assert(InsertPair.second && |
229 | 116 | "Trying to scan a function that has already been cached"); |
230 | 116 | |
231 | 116 | // Note that we can't do Cache[Fn] = buildSetsFrom(Fn) here: the function call |
232 | 116 | // may get evaluated after operator[], potentially triggering a DenseMap |
233 | 116 | // resize and invalidating the reference returned by operator[] |
234 | 116 | auto FunInfo = buildSetsFrom(Fn); |
235 | 116 | Cache[Fn] = std::move(FunInfo); |
236 | 116 | |
237 | 116 | Handles.emplace_front(Fn, this); |
238 | 116 | } |
239 | | |
240 | 0 | void CFLSteensAAResult::evict(Function *Fn) { Cache.erase(Fn); } |
241 | | |
242 | | /// Ensures that the given function is available in the cache, and returns the |
243 | | /// entry. |
244 | | const Optional<CFLSteensAAResult::FunctionInfo> & |
245 | 2.85k | CFLSteensAAResult::ensureCached(Function *Fn) { |
246 | 2.85k | auto Iter = Cache.find(Fn); |
247 | 2.85k | if (Iter == Cache.end()) { |
248 | 116 | scan(Fn); |
249 | 116 | Iter = Cache.find(Fn); |
250 | 116 | assert(Iter != Cache.end()); |
251 | 116 | assert(Iter->second.hasValue()); |
252 | 116 | } |
253 | 2.85k | return Iter->second; |
254 | 2.85k | } |
255 | | |
256 | 64 | const AliasSummary *CFLSteensAAResult::getAliasSummary(Function &Fn) { |
257 | 64 | auto &FunInfo = ensureCached(&Fn); |
258 | 64 | if (FunInfo.hasValue()) |
259 | 64 | return &FunInfo->getAliasSummary(); |
260 | 0 | else |
261 | 0 | return nullptr; |
262 | 64 | } |
263 | | |
264 | | AliasResult CFLSteensAAResult::query(const MemoryLocation &LocA, |
265 | 2.79k | const MemoryLocation &LocB) { |
266 | 2.79k | auto *ValA = const_cast<Value *>(LocA.Ptr); |
267 | 2.79k | auto *ValB = const_cast<Value *>(LocB.Ptr); |
268 | 2.79k | |
269 | 2.79k | if (!ValA->getType()->isPointerTy() || !ValB->getType()->isPointerTy()) |
270 | 0 | return NoAlias; |
271 | 2.79k | |
272 | 2.79k | Function *Fn = nullptr; |
273 | 2.79k | Function *MaybeFnA = const_cast<Function *>(parentFunctionOfValue(ValA)); |
274 | 2.79k | Function *MaybeFnB = const_cast<Function *>(parentFunctionOfValue(ValB)); |
275 | 2.79k | if (!MaybeFnA && !MaybeFnB45 ) { |
276 | 2 | // The only times this is known to happen are when globals + InlineAsm are |
277 | 2 | // involved |
278 | 2 | LLVM_DEBUG( |
279 | 2 | dbgs() |
280 | 2 | << "CFLSteensAA: could not extract parent function information.\n"); |
281 | 2 | return MayAlias; |
282 | 2 | } |
283 | 2.79k | |
284 | 2.79k | if (MaybeFnA) { |
285 | 2.75k | Fn = MaybeFnA; |
286 | 2.75k | assert((!MaybeFnB || MaybeFnB == MaybeFnA) && |
287 | 2.75k | "Interprocedural queries not supported"); |
288 | 2.75k | } else { |
289 | 43 | Fn = MaybeFnB; |
290 | 43 | } |
291 | 2.79k | |
292 | 2.79k | assert(Fn != nullptr); |
293 | 2.79k | auto &MaybeInfo = ensureCached(Fn); |
294 | 2.79k | assert(MaybeInfo.hasValue()); |
295 | 2.79k | |
296 | 2.79k | auto &Sets = MaybeInfo->getStratifiedSets(); |
297 | 2.79k | auto MaybeA = Sets.find(InstantiatedValue{ValA, 0}); |
298 | 2.79k | if (!MaybeA.hasValue()) |
299 | 5 | return MayAlias; |
300 | 2.79k | |
301 | 2.79k | auto MaybeB = Sets.find(InstantiatedValue{ValB, 0}); |
302 | 2.79k | if (!MaybeB.hasValue()) |
303 | 1 | return MayAlias; |
304 | 2.78k | |
305 | 2.78k | auto SetA = *MaybeA; |
306 | 2.78k | auto SetB = *MaybeB; |
307 | 2.78k | auto AttrsA = Sets.getLink(SetA.Index).Attrs; |
308 | 2.78k | auto AttrsB = Sets.getLink(SetB.Index).Attrs; |
309 | 2.78k | |
310 | 2.78k | // If both values are local (meaning the corresponding set has attribute |
311 | 2.78k | // AttrNone or AttrEscaped), then we know that CFLSteensAA fully models them: |
312 | 2.78k | // they may-alias each other if and only if they are in the same set. |
313 | 2.78k | // If at least one value is non-local (meaning it either is global/argument or |
314 | 2.78k | // it comes from unknown sources like integer cast), the situation becomes a |
315 | 2.78k | // bit more interesting. We follow three general rules described below: |
316 | 2.78k | // - Non-local values may alias each other |
317 | 2.78k | // - AttrNone values do not alias any non-local values |
318 | 2.78k | // - AttrEscaped do not alias globals/arguments, but they may alias |
319 | 2.78k | // AttrUnknown values |
320 | 2.78k | if (SetA.Index == SetB.Index) |
321 | 546 | return MayAlias; |
322 | 2.24k | if (AttrsA.none() || AttrsB.none()1.95k ) |
323 | 336 | return NoAlias; |
324 | 1.90k | if (hasUnknownOrCallerAttr(AttrsA) || hasUnknownOrCallerAttr(AttrsB)1.18k ) |
325 | 1.17k | return MayAlias; |
326 | 731 | if (isGlobalOrArgAttr(AttrsA) && isGlobalOrArgAttr(AttrsB)700 ) |
327 | 698 | return MayAlias; |
328 | 33 | return NoAlias; |
329 | 33 | } |
330 | | |
331 | | AnalysisKey CFLSteensAA::Key; |
332 | | |
333 | 42 | CFLSteensAAResult CFLSteensAA::run(Function &F, FunctionAnalysisManager &AM) { |
334 | 42 | return CFLSteensAAResult(AM.getResult<TargetLibraryAnalysis>(F)); |
335 | 42 | } |
336 | | |
337 | | char CFLSteensAAWrapperPass::ID = 0; |
338 | | INITIALIZE_PASS(CFLSteensAAWrapperPass, "cfl-steens-aa", |
339 | | "Unification-Based CFL Alias Analysis", false, true) |
340 | | |
341 | 0 | ImmutablePass *llvm::createCFLSteensAAWrapperPass() { |
342 | 0 | return new CFLSteensAAWrapperPass(); |
343 | 0 | } |
344 | | |
345 | 35 | CFLSteensAAWrapperPass::CFLSteensAAWrapperPass() : ImmutablePass(ID) { |
346 | 35 | initializeCFLSteensAAWrapperPassPass(*PassRegistry::getPassRegistry()); |
347 | 35 | } |
348 | | |
349 | 35 | void CFLSteensAAWrapperPass::initializePass() { |
350 | 35 | auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>(); |
351 | 35 | Result.reset(new CFLSteensAAResult(TLIWP.getTLI())); |
352 | 35 | } |
353 | | |
354 | 35 | void CFLSteensAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { |
355 | 35 | AU.setPreservesAll(); |
356 | 35 | AU.addRequired<TargetLibraryInfoWrapperPass>(); |
357 | 35 | } |