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