Line data Source code
1 : //===- CFLAndersAliasAnalysis.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-based, summary-based alias analysis algorithm. It
11 : // differs from CFLSteensAliasAnalysis in its inclusion-based nature while
12 : // CFLSteensAliasAnalysis is unification-based. This pass has worse performance
13 : // than CFLSteensAliasAnalysis (the worst case complexity of
14 : // CFLAndersAliasAnalysis is cubic, while the worst case complexity of
15 : // CFLSteensAliasAnalysis is almost linear), but it is able to yield more
16 : // precise analysis result. The precision of this analysis is roughly the same
17 : // as that of an one level context-sensitive Andersen's algorithm.
18 : //
19 : // The algorithm used here is based on recursive state machine matching scheme
20 : // proposed in "Demand-driven alias analysis for C" by Xin Zheng and Radu
21 : // Rugina. The general idea is to extend the traditional transitive closure
22 : // algorithm to perform CFL matching along the way: instead of recording
23 : // "whether X is reachable from Y", we keep track of "whether X is reachable
24 : // from Y at state Z", where the "state" field indicates where we are in the CFL
25 : // matching process. To understand the matching better, it is advisable to have
26 : // the state machine shown in Figure 3 of the paper available when reading the
27 : // codes: all we do here is to selectively expand the transitive closure by
28 : // discarding edges that are not recognized by the state machine.
29 : //
30 : // There are two differences between our current implementation and the one
31 : // described in the paper:
32 : // - Our algorithm eagerly computes all alias pairs after the CFLGraph is built,
33 : // while in the paper the authors did the computation in a demand-driven
34 : // fashion. We did not implement the demand-driven algorithm due to the
35 : // additional coding complexity and higher memory profile, but if we found it
36 : // necessary we may switch to it eventually.
37 : // - In the paper the authors use a state machine that does not distinguish
38 : // value reads from value writes. For example, if Y is reachable from X at state
39 : // S3, it may be the case that X is written into Y, or it may be the case that
40 : // there's a third value Z that writes into both X and Y. To make that
41 : // distinction (which is crucial in building function summary as well as
42 : // retrieving mod-ref info), we choose to duplicate some of the states in the
43 : // paper's proposed state machine. The duplication does not change the set the
44 : // machine accepts. Given a pair of reachable values, it only provides more
45 : // detailed information on which value is being written into and which is being
46 : // read from.
47 : //
48 : //===----------------------------------------------------------------------===//
49 :
50 : // N.B. AliasAnalysis as a whole is phrased as a FunctionPass at the moment, and
51 : // CFLAndersAA is interprocedural. This is *technically* A Bad Thing, because
52 : // FunctionPasses are only allowed to inspect the Function that they're being
53 : // run on. Realistically, this likely isn't a problem until we allow
54 : // FunctionPasses to run concurrently.
55 :
56 : #include "llvm/Analysis/CFLAndersAliasAnalysis.h"
57 : #include "AliasAnalysisSummary.h"
58 : #include "CFLGraph.h"
59 : #include "llvm/ADT/DenseMap.h"
60 : #include "llvm/ADT/DenseMapInfo.h"
61 : #include "llvm/ADT/DenseSet.h"
62 : #include "llvm/ADT/None.h"
63 : #include "llvm/ADT/Optional.h"
64 : #include "llvm/ADT/STLExtras.h"
65 : #include "llvm/ADT/SmallVector.h"
66 : #include "llvm/ADT/iterator_range.h"
67 : #include "llvm/Analysis/AliasAnalysis.h"
68 : #include "llvm/Analysis/MemoryLocation.h"
69 : #include "llvm/IR/Argument.h"
70 : #include "llvm/IR/Function.h"
71 : #include "llvm/IR/PassManager.h"
72 : #include "llvm/IR/Type.h"
73 : #include "llvm/Pass.h"
74 : #include "llvm/Support/Casting.h"
75 : #include "llvm/Support/Compiler.h"
76 : #include "llvm/Support/Debug.h"
77 : #include "llvm/Support/raw_ostream.h"
78 : #include <algorithm>
79 : #include <bitset>
80 : #include <cassert>
81 : #include <cstddef>
82 : #include <cstdint>
83 : #include <functional>
84 : #include <utility>
85 : #include <vector>
86 :
87 : using namespace llvm;
88 : using namespace llvm::cflaa;
89 :
90 : #define DEBUG_TYPE "cfl-anders-aa"
91 :
92 61 : CFLAndersAAResult::CFLAndersAAResult(const TargetLibraryInfo &TLI) : TLI(TLI) {}
93 82 : CFLAndersAAResult::CFLAndersAAResult(CFLAndersAAResult &&RHS)
94 82 : : AAResultBase(std::move(RHS)), TLI(RHS.TLI) {}
95 : CFLAndersAAResult::~CFLAndersAAResult() = default;
96 :
97 : namespace {
98 :
99 : enum class MatchState : uint8_t {
100 : // The following state represents S1 in the paper.
101 : FlowFromReadOnly = 0,
102 : // The following two states together represent S2 in the paper.
103 : // The 'NoReadWrite' suffix indicates that there exists an alias path that
104 : // does not contain assignment and reverse assignment edges.
105 : // The 'ReadOnly' suffix indicates that there exists an alias path that
106 : // contains reverse assignment edges only.
107 : FlowFromMemAliasNoReadWrite,
108 : FlowFromMemAliasReadOnly,
109 : // The following two states together represent S3 in the paper.
110 : // The 'WriteOnly' suffix indicates that there exists an alias path that
111 : // contains assignment edges only.
112 : // The 'ReadWrite' suffix indicates that there exists an alias path that
113 : // contains both assignment and reverse assignment edges. Note that if X and Y
114 : // are reachable at 'ReadWrite' state, it does NOT mean X is both read from
115 : // and written to Y. Instead, it means that a third value Z is written to both
116 : // X and Y.
117 : FlowToWriteOnly,
118 : FlowToReadWrite,
119 : // The following two states together represent S4 in the paper.
120 : FlowToMemAliasWriteOnly,
121 : FlowToMemAliasReadWrite,
122 : };
123 :
124 : using StateSet = std::bitset<7>;
125 :
126 : const unsigned ReadOnlyStateMask =
127 : (1U << static_cast<uint8_t>(MatchState::FlowFromReadOnly)) |
128 : (1U << static_cast<uint8_t>(MatchState::FlowFromMemAliasReadOnly));
129 : const unsigned WriteOnlyStateMask =
130 : (1U << static_cast<uint8_t>(MatchState::FlowToWriteOnly)) |
131 : (1U << static_cast<uint8_t>(MatchState::FlowToMemAliasWriteOnly));
132 :
133 : // A pair that consists of a value and an offset
134 : struct OffsetValue {
135 : const Value *Val;
136 : int64_t Offset;
137 : };
138 :
139 : bool operator==(OffsetValue LHS, OffsetValue RHS) {
140 : return LHS.Val == RHS.Val && LHS.Offset == RHS.Offset;
141 : }
142 : bool operator<(OffsetValue LHS, OffsetValue RHS) {
143 0 : return std::less<const Value *>()(LHS.Val, RHS.Val) ||
144 0 : (LHS.Val == RHS.Val && LHS.Offset < RHS.Offset);
145 : }
146 :
147 : // A pair that consists of an InstantiatedValue and an offset
148 : struct OffsetInstantiatedValue {
149 : InstantiatedValue IVal;
150 : int64_t Offset;
151 : };
152 :
153 : bool operator==(OffsetInstantiatedValue LHS, OffsetInstantiatedValue RHS) {
154 : return LHS.IVal == RHS.IVal && LHS.Offset == RHS.Offset;
155 : }
156 :
157 : // We use ReachabilitySet to keep track of value aliases (The nonterminal "V" in
158 : // the paper) during the analysis.
159 95 : class ReachabilitySet {
160 : using ValueStateMap = DenseMap<InstantiatedValue, StateSet>;
161 : using ValueReachMap = DenseMap<InstantiatedValue, ValueStateMap>;
162 :
163 : ValueReachMap ReachMap;
164 :
165 : public:
166 : using const_valuestate_iterator = ValueStateMap::const_iterator;
167 : using const_value_iterator = ValueReachMap::const_iterator;
168 :
169 : // Insert edge 'From->To' at state 'State'
170 1014 : bool insert(InstantiatedValue From, InstantiatedValue To, MatchState State) {
171 : assert(From != To);
172 1014 : auto &States = ReachMap[To][From];
173 1014 : auto Idx = static_cast<size_t>(State);
174 1014 : if (!States.test(Idx)) {
175 948 : States.set(Idx);
176 948 : return true;
177 : }
178 : return false;
179 : }
180 :
181 : // Return the set of all ('From', 'State') pair for a given node 'To'
182 : iterator_range<const_valuestate_iterator>
183 526 : reachableValueAliases(InstantiatedValue V) const {
184 526 : auto Itr = ReachMap.find(V);
185 526 : if (Itr == ReachMap.end())
186 : return make_range<const_valuestate_iterator>(const_valuestate_iterator(),
187 : const_valuestate_iterator());
188 263 : return make_range<const_valuestate_iterator>(Itr->second.begin(),
189 263 : Itr->second.end());
190 : }
191 :
192 : iterator_range<const_value_iterator> value_mappings() const {
193 190 : return make_range<const_value_iterator>(ReachMap.begin(), ReachMap.end());
194 : }
195 : };
196 :
197 : // We use AliasMemSet to keep track of all memory aliases (the nonterminal "M"
198 : // in the paper) during the analysis.
199 95 : class AliasMemSet {
200 : using MemSet = DenseSet<InstantiatedValue>;
201 : using MemMapType = DenseMap<InstantiatedValue, MemSet>;
202 :
203 : MemMapType MemMap;
204 :
205 : public:
206 : using const_mem_iterator = MemSet::const_iterator;
207 :
208 40 : bool insert(InstantiatedValue LHS, InstantiatedValue RHS) {
209 : // Top-level values can never be memory aliases because one cannot take the
210 : // addresses of them
211 : assert(LHS.DerefLevel > 0 && RHS.DerefLevel > 0);
212 40 : return MemMap[LHS].insert(RHS).second;
213 : }
214 :
215 : const MemSet *getMemoryAliases(InstantiatedValue V) const {
216 : auto Itr = MemMap.find(V);
217 : if (Itr == MemMap.end())
218 : return nullptr;
219 : return &Itr->second;
220 : }
221 : };
222 :
223 : // We use AliasAttrMap to keep track of the AliasAttr of each node.
224 95 : class AliasAttrMap {
225 : using MapType = DenseMap<InstantiatedValue, AliasAttrs>;
226 :
227 : MapType AttrMap;
228 :
229 : public:
230 : using const_iterator = MapType::const_iterator;
231 :
232 : bool add(InstantiatedValue V, AliasAttrs Attr) {
233 : auto &OldAttr = AttrMap[V];
234 : auto NewAttr = OldAttr | Attr;
235 1027 : if (OldAttr == NewAttr)
236 : return false;
237 248 : OldAttr = NewAttr;
238 : return true;
239 : }
240 :
241 778 : AliasAttrs getAttrs(InstantiatedValue V) const {
242 : AliasAttrs Attr;
243 778 : auto Itr = AttrMap.find(V);
244 778 : if (Itr != AttrMap.end())
245 778 : Attr = Itr->second;
246 778 : return Attr;
247 : }
248 :
249 : iterator_range<const_iterator> mappings() const {
250 95 : return make_range<const_iterator>(AttrMap.begin(), AttrMap.end());
251 : }
252 : };
253 :
254 : struct WorkListItem {
255 : InstantiatedValue From;
256 : InstantiatedValue To;
257 : MatchState State;
258 : };
259 :
260 56 : struct ValueSummary {
261 : struct Record {
262 : InterfaceValue IValue;
263 : unsigned DerefLevel;
264 : };
265 : SmallVector<Record, 4> FromRecords, ToRecords;
266 : };
267 :
268 : } // end anonymous namespace
269 :
270 : namespace llvm {
271 :
272 : // Specialize DenseMapInfo for OffsetValue.
273 : template <> struct DenseMapInfo<OffsetValue> {
274 : static OffsetValue getEmptyKey() {
275 : return OffsetValue{DenseMapInfo<const Value *>::getEmptyKey(),
276 : DenseMapInfo<int64_t>::getEmptyKey()};
277 : }
278 :
279 : static OffsetValue getTombstoneKey() {
280 : return OffsetValue{DenseMapInfo<const Value *>::getTombstoneKey(),
281 : DenseMapInfo<int64_t>::getEmptyKey()};
282 : }
283 :
284 : static unsigned getHashValue(const OffsetValue &OVal) {
285 : return DenseMapInfo<std::pair<const Value *, int64_t>>::getHashValue(
286 : std::make_pair(OVal.Val, OVal.Offset));
287 : }
288 :
289 : static bool isEqual(const OffsetValue &LHS, const OffsetValue &RHS) {
290 : return LHS == RHS;
291 : }
292 : };
293 :
294 : // Specialize DenseMapInfo for OffsetInstantiatedValue.
295 : template <> struct DenseMapInfo<OffsetInstantiatedValue> {
296 : static OffsetInstantiatedValue getEmptyKey() {
297 : return OffsetInstantiatedValue{
298 : DenseMapInfo<InstantiatedValue>::getEmptyKey(),
299 : DenseMapInfo<int64_t>::getEmptyKey()};
300 : }
301 :
302 : static OffsetInstantiatedValue getTombstoneKey() {
303 : return OffsetInstantiatedValue{
304 : DenseMapInfo<InstantiatedValue>::getTombstoneKey(),
305 : DenseMapInfo<int64_t>::getEmptyKey()};
306 : }
307 :
308 : static unsigned getHashValue(const OffsetInstantiatedValue &OVal) {
309 : return DenseMapInfo<std::pair<InstantiatedValue, int64_t>>::getHashValue(
310 : std::make_pair(OVal.IVal, OVal.Offset));
311 : }
312 :
313 : static bool isEqual(const OffsetInstantiatedValue &LHS,
314 : const OffsetInstantiatedValue &RHS) {
315 : return LHS == RHS;
316 : }
317 : };
318 :
319 : } // end namespace llvm
320 :
321 : class CFLAndersAAResult::FunctionInfo {
322 : /// Map a value to other values that may alias it
323 : /// Since the alias relation is symmetric, to save some space we assume values
324 : /// are properly ordered: if a and b alias each other, and a < b, then b is in
325 : /// AliasMap[a] but not vice versa.
326 : DenseMap<const Value *, std::vector<OffsetValue>> AliasMap;
327 :
328 : /// Map a value to its corresponding AliasAttrs
329 : DenseMap<const Value *, AliasAttrs> AttrMap;
330 :
331 : /// Summary of externally visible effects.
332 : AliasSummary Summary;
333 :
334 : Optional<AliasAttrs> getAttrs(const Value *) const;
335 :
336 : public:
337 : FunctionInfo(const Function &, const SmallVectorImpl<Value *> &,
338 : const ReachabilitySet &, const AliasAttrMap &);
339 :
340 : bool mayAlias(const Value *, LocationSize, const Value *, LocationSize) const;
341 64 : const AliasSummary &getAliasSummary() const { return Summary; }
342 : };
343 :
344 : static bool hasReadOnlyState(StateSet Set) {
345 : return (Set & StateSet(ReadOnlyStateMask)).any();
346 : }
347 :
348 : static bool hasWriteOnlyState(StateSet Set) {
349 : return (Set & StateSet(WriteOnlyStateMask)).any();
350 : }
351 :
352 : static Optional<InterfaceValue>
353 0 : getInterfaceValue(InstantiatedValue IValue,
354 : const SmallVectorImpl<Value *> &RetVals) {
355 0 : auto Val = IValue.Val;
356 :
357 : Optional<unsigned> Index;
358 : if (auto Arg = dyn_cast<Argument>(Val))
359 0 : Index = Arg->getArgNo() + 1;
360 0 : else if (is_contained(RetVals, Val))
361 : Index = 0;
362 :
363 0 : if (Index)
364 0 : return InterfaceValue{*Index, IValue.DerefLevel};
365 : return None;
366 : }
367 :
368 95 : static void populateAttrMap(DenseMap<const Value *, AliasAttrs> &AttrMap,
369 : const AliasAttrMap &AMap) {
370 657 : for (const auto &Mapping : AMap.mappings()) {
371 562 : auto IVal = Mapping.first;
372 :
373 : // Insert IVal into the map
374 562 : auto &Attr = AttrMap[IVal.Val];
375 : // AttrMap only cares about top-level values
376 562 : if (IVal.DerefLevel == 0)
377 : Attr |= Mapping.second;
378 : }
379 95 : }
380 :
381 : static void
382 95 : populateAliasMap(DenseMap<const Value *, std::vector<OffsetValue>> &AliasMap,
383 : const ReachabilitySet &ReachSet) {
384 409 : for (const auto &OuterMapping : ReachSet.value_mappings()) {
385 : // AliasMap only cares about top-level values
386 314 : if (OuterMapping.first.DerefLevel > 0)
387 : continue;
388 :
389 201 : auto Val = OuterMapping.first.Val;
390 201 : auto &AliasList = AliasMap[Val];
391 897 : for (const auto &InnerMapping : OuterMapping.second) {
392 : // Again, AliasMap only cares about top-level values
393 495 : if (InnerMapping.first.DerefLevel == 0)
394 262 : AliasList.push_back(OffsetValue{InnerMapping.first.Val, UnknownOffset});
395 : }
396 :
397 : // Sort AliasList for faster lookup
398 : llvm::sort(AliasList);
399 : }
400 95 : }
401 :
402 95 : static void populateExternalRelations(
403 : SmallVectorImpl<ExternalRelation> &ExtRelations, const Function &Fn,
404 : const SmallVectorImpl<Value *> &RetVals, const ReachabilitySet &ReachSet) {
405 : // If a function only returns one of its argument X, then X will be both an
406 : // argument and a return value at the same time. This is an edge case that
407 : // needs special handling here.
408 183 : for (const auto &Arg : Fn.args()) {
409 176 : if (is_contained(RetVals, &Arg)) {
410 3 : auto ArgVal = InterfaceValue{Arg.getArgNo() + 1, 0};
411 : auto RetVal = InterfaceValue{0, 0};
412 3 : ExtRelations.push_back(ExternalRelation{ArgVal, RetVal, 0});
413 : }
414 : }
415 :
416 : // Below is the core summary construction logic.
417 : // A naive solution of adding only the value aliases that are parameters or
418 : // return values in ReachSet to the summary won't work: It is possible that a
419 : // parameter P is written into an intermediate value I, and the function
420 : // subsequently returns *I. In that case, *I is does not value alias anything
421 : // in ReachSet, and the naive solution will miss a summary edge from (P, 1) to
422 : // (I, 1).
423 : // To account for the aforementioned case, we need to check each non-parameter
424 : // and non-return value for the possibility of acting as an intermediate.
425 : // 'ValueMap' here records, for each value, which InterfaceValues read from or
426 : // write into it. If both the read list and the write list of a given value
427 : // are non-empty, we know that a particular value is an intermidate and we
428 : // need to add summary edges from the writes to the reads.
429 : DenseMap<Value *, ValueSummary> ValueMap;
430 409 : for (const auto &OuterMapping : ReachSet.value_mappings()) {
431 314 : if (auto Dst = getInterfaceValue(OuterMapping.first, RetVals)) {
432 217 : for (const auto &InnerMapping : OuterMapping.second) {
433 : // If Src is a param/return value, we get a same-level assignment.
434 83 : if (auto Src = getInterfaceValue(InnerMapping.first, RetVals)) {
435 : // This may happen if both Dst and Src are return values
436 : if (*Dst == *Src)
437 : continue;
438 :
439 18 : if (hasReadOnlyState(InnerMapping.second))
440 9 : ExtRelations.push_back(ExternalRelation{*Dst, *Src, UnknownOffset});
441 : // No need to check for WriteOnly state, since ReachSet is symmetric
442 : } else {
443 : // If Src is not a param/return, add it to ValueMap
444 65 : auto SrcIVal = InnerMapping.first;
445 65 : if (hasReadOnlyState(InnerMapping.second))
446 76 : ValueMap[SrcIVal.Val].FromRecords.push_back(
447 38 : ValueSummary::Record{*Dst, SrcIVal.DerefLevel});
448 65 : if (hasWriteOnlyState(InnerMapping.second))
449 54 : ValueMap[SrcIVal.Val].ToRecords.push_back(
450 27 : ValueSummary::Record{*Dst, SrcIVal.DerefLevel});
451 : }
452 : }
453 : }
454 : }
455 :
456 151 : for (const auto &Mapping : ValueMap) {
457 94 : for (const auto &FromRecord : Mapping.second.FromRecords) {
458 47 : for (const auto &ToRecord : Mapping.second.ToRecords) {
459 9 : auto ToLevel = ToRecord.DerefLevel;
460 9 : auto FromLevel = FromRecord.DerefLevel;
461 : // Same-level assignments should have already been processed by now
462 9 : if (ToLevel == FromLevel)
463 : continue;
464 :
465 9 : auto SrcIndex = FromRecord.IValue.Index;
466 9 : auto SrcLevel = FromRecord.IValue.DerefLevel;
467 9 : auto DstIndex = ToRecord.IValue.Index;
468 9 : auto DstLevel = ToRecord.IValue.DerefLevel;
469 9 : if (ToLevel > FromLevel)
470 3 : SrcLevel += ToLevel - FromLevel;
471 : else
472 6 : DstLevel += FromLevel - ToLevel;
473 :
474 9 : ExtRelations.push_back(ExternalRelation{
475 : InterfaceValue{SrcIndex, SrcLevel},
476 : InterfaceValue{DstIndex, DstLevel}, UnknownOffset});
477 : }
478 : }
479 : }
480 :
481 : // Remove duplicates in ExtRelations
482 : llvm::sort(ExtRelations);
483 95 : ExtRelations.erase(std::unique(ExtRelations.begin(), ExtRelations.end()),
484 : ExtRelations.end());
485 95 : }
486 :
487 0 : static void populateExternalAttributes(
488 : SmallVectorImpl<ExternalAttribute> &ExtAttributes, const Function &Fn,
489 : const SmallVectorImpl<Value *> &RetVals, const AliasAttrMap &AMap) {
490 0 : for (const auto &Mapping : AMap.mappings()) {
491 0 : if (auto IVal = getInterfaceValue(Mapping.first, RetVals)) {
492 0 : auto Attr = getExternallyVisibleAttrs(Mapping.second);
493 0 : if (Attr.any())
494 0 : ExtAttributes.push_back(ExternalAttribute{*IVal, Attr});
495 : }
496 : }
497 0 : }
498 :
499 95 : CFLAndersAAResult::FunctionInfo::FunctionInfo(
500 : const Function &Fn, const SmallVectorImpl<Value *> &RetVals,
501 95 : const ReachabilitySet &ReachSet, const AliasAttrMap &AMap) {
502 95 : populateAttrMap(AttrMap, AMap);
503 95 : populateExternalAttributes(Summary.RetParamAttributes, Fn, RetVals, AMap);
504 95 : populateAliasMap(AliasMap, ReachSet);
505 95 : populateExternalRelations(Summary.RetParamRelations, Fn, RetVals, ReachSet);
506 95 : }
507 :
508 : Optional<AliasAttrs>
509 1330 : CFLAndersAAResult::FunctionInfo::getAttrs(const Value *V) const {
510 : assert(V != nullptr);
511 :
512 1330 : auto Itr = AttrMap.find(V);
513 1330 : if (Itr != AttrMap.end())
514 : return Itr->second;
515 : return None;
516 : }
517 :
518 665 : bool CFLAndersAAResult::FunctionInfo::mayAlias(
519 : const Value *LHS, LocationSize MaybeLHSSize, const Value *RHS,
520 : LocationSize MaybeRHSSize) const {
521 : assert(LHS && RHS);
522 :
523 : // Check if we've seen LHS and RHS before. Sometimes LHS or RHS can be created
524 : // after the analysis gets executed, and we want to be conservative in those
525 : // cases.
526 665 : auto MaybeAttrsA = getAttrs(LHS);
527 665 : auto MaybeAttrsB = getAttrs(RHS);
528 665 : if (!MaybeAttrsA || !MaybeAttrsB)
529 : return true;
530 :
531 : // Check AliasAttrs before AliasMap lookup since it's cheaper
532 664 : auto AttrsA = *MaybeAttrsA;
533 664 : auto AttrsB = *MaybeAttrsB;
534 664 : if (hasUnknownOrCallerAttr(AttrsA))
535 148 : return AttrsB.any();
536 516 : if (hasUnknownOrCallerAttr(AttrsB))
537 10 : return AttrsA.any();
538 506 : if (isGlobalOrArgAttr(AttrsA))
539 48 : return isGlobalOrArgAttr(AttrsB);
540 458 : if (isGlobalOrArgAttr(AttrsB))
541 74 : return isGlobalOrArgAttr(AttrsA);
542 :
543 : // At this point both LHS and RHS should point to locally allocated objects
544 :
545 384 : auto Itr = AliasMap.find(LHS);
546 384 : if (Itr != AliasMap.end()) {
547 :
548 : // Find out all (X, Offset) where X == RHS
549 : auto Comparator = [](OffsetValue LHS, OffsetValue RHS) {
550 : return std::less<const Value *>()(LHS.Val, RHS.Val);
551 : };
552 : #ifdef EXPENSIVE_CHECKS
553 : assert(std::is_sorted(Itr->second.begin(), Itr->second.end(), Comparator));
554 : #endif
555 : auto RangePair = std::equal_range(Itr->second.begin(), Itr->second.end(),
556 296 : OffsetValue{RHS, 0}, Comparator);
557 :
558 296 : if (RangePair.first != RangePair.second) {
559 : // Be conservative about unknown sizes
560 108 : if (MaybeLHSSize == LocationSize::unknown() ||
561 : MaybeRHSSize == LocationSize::unknown())
562 : return true;
563 :
564 : const uint64_t LHSSize = MaybeLHSSize.getValue();
565 : const uint64_t RHSSize = MaybeRHSSize.getValue();
566 :
567 108 : for (const auto &OVal : make_range(RangePair)) {
568 : // Be conservative about UnknownOffset
569 108 : if (OVal.Offset == UnknownOffset)
570 : return true;
571 :
572 : // We know that LHS aliases (RHS + OVal.Offset) if the control flow
573 : // reaches here. The may-alias query essentially becomes integer
574 : // range-overlap queries over two ranges [OVal.Offset, OVal.Offset +
575 : // LHSSize) and [0, RHSSize).
576 :
577 : // Try to be conservative on super large offsets
578 0 : if (LLVM_UNLIKELY(LHSSize > INT64_MAX || RHSSize > INT64_MAX))
579 : return true;
580 :
581 : auto LHSStart = OVal.Offset;
582 : // FIXME: Do we need to guard against integer overflow?
583 0 : auto LHSEnd = OVal.Offset + static_cast<int64_t>(LHSSize);
584 : auto RHSStart = 0;
585 : auto RHSEnd = static_cast<int64_t>(RHSSize);
586 0 : if (LHSEnd > RHSStart && LHSStart < RHSEnd)
587 : return true;
588 : }
589 : }
590 : }
591 :
592 : return false;
593 : }
594 :
595 1290 : static void propagate(InstantiatedValue From, InstantiatedValue To,
596 : MatchState State, ReachabilitySet &ReachSet,
597 : std::vector<WorkListItem> &WorkList) {
598 1290 : if (From == To)
599 : return;
600 1014 : if (ReachSet.insert(From, To, State))
601 948 : WorkList.push_back(WorkListItem{From, To, State});
602 : }
603 :
604 95 : static void initializeWorkList(std::vector<WorkListItem> &WorkList,
605 : ReachabilitySet &ReachSet,
606 : const CFLGraph &Graph) {
607 464 : for (const auto &Mapping : Graph.value_mappings()) {
608 369 : auto Val = Mapping.first;
609 : auto &ValueInfo = Mapping.second;
610 : assert(ValueInfo.getNumLevels() > 0);
611 :
612 : // Insert all immediate assignment neighbors to the worklist
613 931 : for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I) {
614 562 : auto Src = InstantiatedValue{Val, I};
615 : // If there's an assignment edge from X to Y, it means Y is reachable from
616 : // X at S2 and X is reachable from Y at S1
617 754 : for (auto &Edge : ValueInfo.getNodeInfoAtLevel(I).Edges) {
618 192 : propagate(Edge.Other, Src, MatchState::FlowFromReadOnly, ReachSet,
619 : WorkList);
620 192 : propagate(Src, Edge.Other, MatchState::FlowToWriteOnly, ReachSet,
621 : WorkList);
622 : }
623 : }
624 : }
625 95 : }
626 :
627 0 : static Optional<InstantiatedValue> getNodeBelow(const CFLGraph &Graph,
628 : InstantiatedValue V) {
629 2403 : auto NodeBelow = InstantiatedValue{V.Val, V.DerefLevel + 1};
630 2403 : if (Graph.getNode(NodeBelow))
631 : return NodeBelow;
632 : return None;
633 : }
634 :
635 948 : static void processWorkListItem(const WorkListItem &Item, const CFLGraph &Graph,
636 : ReachabilitySet &ReachSet, AliasMemSet &MemSet,
637 : std::vector<WorkListItem> &WorkList) {
638 948 : auto FromNode = Item.From;
639 948 : auto ToNode = Item.To;
640 :
641 948 : auto NodeInfo = Graph.getNode(ToNode);
642 : assert(NodeInfo != nullptr);
643 :
644 : // TODO: propagate field offsets
645 :
646 : // FIXME: Here is a neat trick we can do: since both ReachSet and MemSet holds
647 : // relations that are symmetric, we could actually cut the storage by half by
648 : // sorting FromNode and ToNode before insertion happens.
649 :
650 : // The newly added value alias pair may potentially generate more memory
651 : // alias pairs. Check for them here.
652 948 : auto FromNodeBelow = getNodeBelow(Graph, FromNode);
653 948 : auto ToNodeBelow = getNodeBelow(Graph, ToNode);
654 988 : if (FromNodeBelow && ToNodeBelow &&
655 40 : MemSet.insert(*FromNodeBelow, *ToNodeBelow)) {
656 36 : propagate(*FromNodeBelow, *ToNodeBelow,
657 : MatchState::FlowFromMemAliasNoReadWrite, ReachSet, WorkList);
658 153 : for (const auto &Mapping : ReachSet.reachableValueAliases(*FromNodeBelow)) {
659 117 : auto Src = Mapping.first;
660 : auto MemAliasPropagate = [&](MatchState FromState, MatchState ToState) {
661 : if (Mapping.second.test(static_cast<size_t>(FromState)))
662 : propagate(Src, *ToNodeBelow, ToState, ReachSet, WorkList);
663 117 : };
664 :
665 117 : MemAliasPropagate(MatchState::FlowFromReadOnly,
666 : MatchState::FlowFromMemAliasReadOnly);
667 117 : MemAliasPropagate(MatchState::FlowToWriteOnly,
668 : MatchState::FlowToMemAliasWriteOnly);
669 117 : MemAliasPropagate(MatchState::FlowToReadWrite,
670 : MatchState::FlowToMemAliasReadWrite);
671 : }
672 : }
673 :
674 : // This is the core of the state machine walking algorithm. We expand ReachSet
675 : // based on which state we are at (which in turn dictates what edges we
676 : // should examine)
677 : // From a high-level point of view, the state machine here guarantees two
678 : // properties:
679 : // - If *X and *Y are memory aliases, then X and Y are value aliases
680 : // - If Y is an alias of X, then reverse assignment edges (if there is any)
681 : // should precede any assignment edges on the path from X to Y.
682 : auto NextAssignState = [&](MatchState State) {
683 : for (const auto &AssignEdge : NodeInfo->Edges)
684 : propagate(FromNode, AssignEdge.Other, State, ReachSet, WorkList);
685 948 : };
686 : auto NextRevAssignState = [&](MatchState State) {
687 : for (const auto &RevAssignEdge : NodeInfo->ReverseEdges)
688 : propagate(FromNode, RevAssignEdge.Other, State, ReachSet, WorkList);
689 948 : };
690 : auto NextMemState = [&](MatchState State) {
691 : if (auto AliasSet = MemSet.getMemoryAliases(ToNode)) {
692 : for (const auto &MemAlias : *AliasSet)
693 : propagate(FromNode, MemAlias, State, ReachSet, WorkList);
694 : }
695 948 : };
696 :
697 948 : switch (Item.State) {
698 294 : case MatchState::FlowFromReadOnly:
699 294 : NextRevAssignState(MatchState::FlowFromReadOnly);
700 294 : NextAssignState(MatchState::FlowToReadWrite);
701 294 : NextMemState(MatchState::FlowFromMemAliasReadOnly);
702 294 : break;
703 :
704 36 : case MatchState::FlowFromMemAliasNoReadWrite:
705 36 : NextRevAssignState(MatchState::FlowFromReadOnly);
706 36 : NextAssignState(MatchState::FlowToWriteOnly);
707 36 : break;
708 :
709 28 : case MatchState::FlowFromMemAliasReadOnly:
710 28 : NextRevAssignState(MatchState::FlowFromReadOnly);
711 28 : NextAssignState(MatchState::FlowToReadWrite);
712 28 : break;
713 :
714 304 : case MatchState::FlowToWriteOnly:
715 304 : NextAssignState(MatchState::FlowToWriteOnly);
716 304 : NextMemState(MatchState::FlowToMemAliasWriteOnly);
717 304 : break;
718 :
719 210 : case MatchState::FlowToReadWrite:
720 210 : NextAssignState(MatchState::FlowToReadWrite);
721 210 : NextMemState(MatchState::FlowToMemAliasReadWrite);
722 210 : break;
723 :
724 18 : case MatchState::FlowToMemAliasWriteOnly:
725 18 : NextAssignState(MatchState::FlowToWriteOnly);
726 18 : break;
727 :
728 58 : case MatchState::FlowToMemAliasReadWrite:
729 58 : NextAssignState(MatchState::FlowToReadWrite);
730 58 : break;
731 : }
732 948 : }
733 :
734 95 : static AliasAttrMap buildAttrMap(const CFLGraph &Graph,
735 : const ReachabilitySet &ReachSet) {
736 : AliasAttrMap AttrMap;
737 : std::vector<InstantiatedValue> WorkList, NextList;
738 :
739 : // Initialize each node with its original AliasAttrs in CFLGraph
740 464 : for (const auto &Mapping : Graph.value_mappings()) {
741 369 : auto Val = Mapping.first;
742 : auto &ValueInfo = Mapping.second;
743 931 : for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I) {
744 562 : auto Node = InstantiatedValue{Val, I};
745 562 : AttrMap.add(Node, ValueInfo.getNodeInfoAtLevel(I).Attr);
746 562 : WorkList.push_back(Node);
747 : }
748 : }
749 :
750 281 : while (!WorkList.empty()) {
751 964 : for (const auto &Dst : WorkList) {
752 778 : auto DstAttr = AttrMap.getAttrs(Dst);
753 778 : if (DstAttr.none())
754 288 : continue;
755 :
756 : // Propagate attr on the same level
757 814 : for (const auto &Mapping : ReachSet.reachableValueAliases(Dst)) {
758 324 : auto Src = Mapping.first;
759 232 : if (AttrMap.add(Src, DstAttr))
760 92 : NextList.push_back(Src);
761 : }
762 :
763 : // Propagate attr to the levels below
764 490 : auto DstBelow = getNodeBelow(Graph, Dst);
765 507 : while (DstBelow) {
766 141 : if (AttrMap.add(*DstBelow, DstAttr)) {
767 124 : NextList.push_back(*DstBelow);
768 124 : break;
769 : }
770 17 : DstBelow = getNodeBelow(Graph, *DstBelow);
771 : }
772 : }
773 : WorkList.swap(NextList);
774 : NextList.clear();
775 : }
776 :
777 95 : return AttrMap;
778 : }
779 :
780 : CFLAndersAAResult::FunctionInfo
781 95 : CFLAndersAAResult::buildInfoFrom(const Function &Fn) {
782 : CFLGraphBuilder<CFLAndersAAResult> GraphBuilder(
783 : *this, TLI,
784 : // Cast away the constness here due to GraphBuilder's API requirement
785 190 : const_cast<Function &>(Fn));
786 : auto &Graph = GraphBuilder.getCFLGraph();
787 :
788 : ReachabilitySet ReachSet;
789 : AliasMemSet MemSet;
790 :
791 : std::vector<WorkListItem> WorkList, NextList;
792 95 : initializeWorkList(WorkList, ReachSet, Graph);
793 : // TODO: make sure we don't stop before the fix point is reached
794 270 : while (!WorkList.empty()) {
795 1123 : for (const auto &Item : WorkList)
796 948 : processWorkListItem(Item, Graph, ReachSet, MemSet, NextList);
797 :
798 : NextList.swap(WorkList);
799 : NextList.clear();
800 : }
801 :
802 : // Now that we have all the reachability info, propagate AliasAttrs according
803 : // to it
804 95 : auto IValueAttrMap = buildAttrMap(Graph, ReachSet);
805 :
806 : return FunctionInfo(Fn, GraphBuilder.getReturnValues(), ReachSet,
807 95 : std::move(IValueAttrMap));
808 : }
809 :
810 95 : void CFLAndersAAResult::scan(const Function &Fn) {
811 190 : auto InsertPair = Cache.insert(std::make_pair(&Fn, Optional<FunctionInfo>()));
812 : (void)InsertPair;
813 : assert(InsertPair.second &&
814 : "Trying to scan a function that has already been cached");
815 :
816 : // Note that we can't do Cache[Fn] = buildSetsFrom(Fn) here: the function call
817 : // may get evaluated after operator[], potentially triggering a DenseMap
818 : // resize and invalidating the reference returned by operator[]
819 95 : auto FunInfo = buildInfoFrom(Fn);
820 95 : Cache[&Fn] = std::move(FunInfo);
821 95 : Handles.emplace_front(const_cast<Function *>(&Fn), this);
822 95 : }
823 :
824 0 : void CFLAndersAAResult::evict(const Function *Fn) { Cache.erase(Fn); }
825 :
826 : const Optional<CFLAndersAAResult::FunctionInfo> &
827 729 : CFLAndersAAResult::ensureCached(const Function &Fn) {
828 729 : auto Iter = Cache.find(&Fn);
829 729 : if (Iter == Cache.end()) {
830 95 : scan(Fn);
831 95 : Iter = Cache.find(&Fn);
832 : assert(Iter != Cache.end());
833 : assert(Iter->second.hasValue());
834 : }
835 729 : return Iter->second;
836 : }
837 :
838 64 : const AliasSummary *CFLAndersAAResult::getAliasSummary(const Function &Fn) {
839 64 : auto &FunInfo = ensureCached(Fn);
840 64 : if (FunInfo.hasValue())
841 64 : return &FunInfo->getAliasSummary();
842 : else
843 : return nullptr;
844 : }
845 :
846 665 : AliasResult CFLAndersAAResult::query(const MemoryLocation &LocA,
847 : const MemoryLocation &LocB) {
848 665 : auto *ValA = LocA.Ptr;
849 665 : auto *ValB = LocB.Ptr;
850 :
851 1330 : if (!ValA->getType()->isPointerTy() || !ValB->getType()->isPointerTy())
852 : return NoAlias;
853 :
854 : auto *Fn = parentFunctionOfValue(ValA);
855 651 : if (!Fn) {
856 : Fn = parentFunctionOfValue(ValB);
857 14 : if (!Fn) {
858 : // The only times this is known to happen are when globals + InlineAsm are
859 : // involved
860 : LLVM_DEBUG(
861 : dbgs()
862 : << "CFLAndersAA: could not extract parent function information.\n");
863 : return MayAlias;
864 : }
865 : } else {
866 : assert(!parentFunctionOfValue(ValB) || parentFunctionOfValue(ValB) == Fn);
867 : }
868 :
869 : assert(Fn != nullptr);
870 665 : auto &FunInfo = ensureCached(*Fn);
871 :
872 : // AliasMap lookup
873 665 : if (FunInfo->mayAlias(ValA, LocA.Size, ValB, LocB.Size))
874 273 : return MayAlias;
875 : return NoAlias;
876 : }
877 :
878 665 : AliasResult CFLAndersAAResult::alias(const MemoryLocation &LocA,
879 : const MemoryLocation &LocB) {
880 665 : if (LocA.Ptr == LocB.Ptr)
881 : return MustAlias;
882 :
883 : // Comparisons between global variables and other constants should be
884 : // handled by BasicAA.
885 : // CFLAndersAA may report NoAlias when comparing a GlobalValue and
886 : // ConstantExpr, but every query needs to have at least one Value tied to a
887 : // Function, and neither GlobalValues nor ConstantExprs are.
888 665 : if (isa<Constant>(LocA.Ptr) && isa<Constant>(LocB.Ptr))
889 : return AAResultBase::alias(LocA, LocB);
890 :
891 665 : AliasResult QueryResult = query(LocA, LocB);
892 665 : if (QueryResult == MayAlias)
893 273 : return AAResultBase::alias(LocA, LocB);
894 :
895 : return QueryResult;
896 : }
897 :
898 : AnalysisKey CFLAndersAA::Key;
899 :
900 41 : CFLAndersAAResult CFLAndersAA::run(Function &F, FunctionAnalysisManager &AM) {
901 41 : return CFLAndersAAResult(AM.getResult<TargetLibraryAnalysis>(F));
902 : }
903 :
904 : char CFLAndersAAWrapperPass::ID = 0;
905 181580 : INITIALIZE_PASS(CFLAndersAAWrapperPass, "cfl-anders-aa",
906 : "Inclusion-Based CFL Alias Analysis", false, true)
907 :
908 0 : ImmutablePass *llvm::createCFLAndersAAWrapperPass() {
909 0 : return new CFLAndersAAWrapperPass();
910 : }
911 :
912 40 : CFLAndersAAWrapperPass::CFLAndersAAWrapperPass() : ImmutablePass(ID) {
913 20 : initializeCFLAndersAAWrapperPassPass(*PassRegistry::getPassRegistry());
914 20 : }
915 :
916 20 : void CFLAndersAAWrapperPass::initializePass() {
917 20 : auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>();
918 20 : Result.reset(new CFLAndersAAResult(TLIWP.getTLI()));
919 20 : }
920 :
921 20 : void CFLAndersAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
922 : AU.setPreservesAll();
923 : AU.addRequired<TargetLibraryInfoWrapperPass>();
924 20 : }
|
