1 //===- CFLAndersAliasAnalysis.cpp - Unification-based Alias Analysis ------===//
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
7 //===----------------------------------------------------------------------===//
9 // This file implements a CFL-based, summary-based alias analysis algorithm. It
10 // differs from CFLSteensAliasAnalysis in its inclusion-based nature while
11 // CFLSteensAliasAnalysis is unification-based. This pass has worse performance
12 // than CFLSteensAliasAnalysis (the worst case complexity of
13 // CFLAndersAliasAnalysis is cubic, while the worst case complexity of
14 // CFLSteensAliasAnalysis is almost linear), but it is able to yield more
15 // precise analysis result. The precision of this analysis is roughly the same
16 // as that of an one level context-sensitive Andersen's algorithm.
18 // The algorithm used here is based on recursive state machine matching scheme
19 // proposed in "Demand-driven alias analysis for C" by Xin Zheng and Radu
20 // Rugina. The general idea is to extend the traditional transitive closure
21 // algorithm to perform CFL matching along the way: instead of recording
22 // "whether X is reachable from Y", we keep track of "whether X is reachable
23 // from Y at state Z", where the "state" field indicates where we are in the CFL
24 // matching process. To understand the matching better, it is advisable to have
25 // the state machine shown in Figure 3 of the paper available when reading the
26 // codes: all we do here is to selectively expand the transitive closure by
27 // discarding edges that are not recognized by the state machine.
29 // There are two differences between our current implementation and the one
30 // described in the paper:
31 // - Our algorithm eagerly computes all alias pairs after the CFLGraph is built,
32 // while in the paper the authors did the computation in a demand-driven
33 // fashion. We did not implement the demand-driven algorithm due to the
34 // additional coding complexity and higher memory profile, but if we found it
35 // necessary we may switch to it eventually.
36 // - In the paper the authors use a state machine that does not distinguish
37 // value reads from value writes. For example, if Y is reachable from X at state
38 // S3, it may be the case that X is written into Y, or it may be the case that
39 // there's a third value Z that writes into both X and Y. To make that
40 // distinction (which is crucial in building function summary as well as
41 // retrieving mod-ref info), we choose to duplicate some of the states in the
42 // paper's proposed state machine. The duplication does not change the set the
43 // machine accepts. Given a pair of reachable values, it only provides more
44 // detailed information on which value is being written into and which is being
47 //===----------------------------------------------------------------------===//
49 // N.B. AliasAnalysis as a whole is phrased as a FunctionPass at the moment, and
50 // CFLAndersAA is interprocedural. This is *technically* A Bad Thing, because
51 // FunctionPasses are only allowed to inspect the Function that they're being
52 // run on. Realistically, this likely isn't a problem until we allow
53 // FunctionPasses to run concurrently.
55 #include "llvm/Analysis/CFLAndersAliasAnalysis.h"
56 #include "AliasAnalysisSummary.h"
58 #include "llvm/ADT/DenseMap.h"
59 #include "llvm/ADT/DenseMapInfo.h"
60 #include "llvm/ADT/DenseSet.h"
61 #include "llvm/ADT/None.h"
62 #include "llvm/ADT/Optional.h"
63 #include "llvm/ADT/STLExtras.h"
64 #include "llvm/ADT/SmallVector.h"
65 #include "llvm/ADT/iterator_range.h"
66 #include "llvm/Analysis/AliasAnalysis.h"
67 #include "llvm/Analysis/MemoryLocation.h"
68 #include "llvm/IR/Argument.h"
69 #include "llvm/IR/Function.h"
70 #include "llvm/IR/PassManager.h"
71 #include "llvm/IR/Type.h"
72 #include "llvm/InitializePasses.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"
88 using namespace llvm::cflaa;
90 #define DEBUG_TYPE "cfl-anders-aa"
92 CFLAndersAAResult::CFLAndersAAResult(
93 std::function<const TargetLibraryInfo &(Function &F)> GetTLI)
94 : GetTLI(std::move(GetTLI)) {}
95 CFLAndersAAResult::CFLAndersAAResult(CFLAndersAAResult &&RHS)
96 : AAResultBase(std::move(RHS)), GetTLI(std::move(RHS.GetTLI)) {}
97 CFLAndersAAResult::~CFLAndersAAResult() = default;
101 enum class MatchState : uint8_t {
102 // The following state represents S1 in the paper.
103 FlowFromReadOnly = 0,
104 // The following two states together represent S2 in the paper.
105 // The 'NoReadWrite' suffix indicates that there exists an alias path that
106 // does not contain assignment and reverse assignment edges.
107 // The 'ReadOnly' suffix indicates that there exists an alias path that
108 // contains reverse assignment edges only.
109 FlowFromMemAliasNoReadWrite,
110 FlowFromMemAliasReadOnly,
111 // The following two states together represent S3 in the paper.
112 // The 'WriteOnly' suffix indicates that there exists an alias path that
113 // contains assignment edges only.
114 // The 'ReadWrite' suffix indicates that there exists an alias path that
115 // contains both assignment and reverse assignment edges. Note that if X and Y
116 // are reachable at 'ReadWrite' state, it does NOT mean X is both read from
117 // and written to Y. Instead, it means that a third value Z is written to both
121 // The following two states together represent S4 in the paper.
122 FlowToMemAliasWriteOnly,
123 FlowToMemAliasReadWrite,
126 using StateSet = std::bitset<7>;
128 const unsigned ReadOnlyStateMask =
129 (1U << static_cast<uint8_t>(MatchState::FlowFromReadOnly)) |
130 (1U << static_cast<uint8_t>(MatchState::FlowFromMemAliasReadOnly));
131 const unsigned WriteOnlyStateMask =
132 (1U << static_cast<uint8_t>(MatchState::FlowToWriteOnly)) |
133 (1U << static_cast<uint8_t>(MatchState::FlowToMemAliasWriteOnly));
135 // A pair that consists of a value and an offset
141 bool operator==(OffsetValue LHS, OffsetValue RHS) {
142 return LHS.Val == RHS.Val && LHS.Offset == RHS.Offset;
144 bool operator<(OffsetValue LHS, OffsetValue RHS) {
145 return std::less<const Value *>()(LHS.Val, RHS.Val) ||
146 (LHS.Val == RHS.Val && LHS.Offset < RHS.Offset);
149 // A pair that consists of an InstantiatedValue and an offset
150 struct OffsetInstantiatedValue {
151 InstantiatedValue IVal;
155 bool operator==(OffsetInstantiatedValue LHS, OffsetInstantiatedValue RHS) {
156 return LHS.IVal == RHS.IVal && LHS.Offset == RHS.Offset;
159 // We use ReachabilitySet to keep track of value aliases (The nonterminal "V" in
160 // the paper) during the analysis.
161 class ReachabilitySet {
162 using ValueStateMap = DenseMap<InstantiatedValue, StateSet>;
163 using ValueReachMap = DenseMap<InstantiatedValue, ValueStateMap>;
165 ValueReachMap ReachMap;
168 using const_valuestate_iterator = ValueStateMap::const_iterator;
169 using const_value_iterator = ValueReachMap::const_iterator;
171 // Insert edge 'From->To' at state 'State'
172 bool insert(InstantiatedValue From, InstantiatedValue To, MatchState State) {
174 auto &States = ReachMap[To][From];
175 auto Idx = static_cast<size_t>(State);
176 if (!States.test(Idx)) {
183 // Return the set of all ('From', 'State') pair for a given node 'To'
184 iterator_range<const_valuestate_iterator>
185 reachableValueAliases(InstantiatedValue V) const {
186 auto Itr = ReachMap.find(V);
187 if (Itr == ReachMap.end())
188 return make_range<const_valuestate_iterator>(const_valuestate_iterator(),
189 const_valuestate_iterator());
190 return make_range<const_valuestate_iterator>(Itr->second.begin(),
194 iterator_range<const_value_iterator> value_mappings() const {
195 return make_range<const_value_iterator>(ReachMap.begin(), ReachMap.end());
199 // We use AliasMemSet to keep track of all memory aliases (the nonterminal "M"
200 // in the paper) during the analysis.
202 using MemSet = DenseSet<InstantiatedValue>;
203 using MemMapType = DenseMap<InstantiatedValue, MemSet>;
208 using const_mem_iterator = MemSet::const_iterator;
210 bool insert(InstantiatedValue LHS, InstantiatedValue RHS) {
211 // Top-level values can never be memory aliases because one cannot take the
213 assert(LHS.DerefLevel > 0 && RHS.DerefLevel > 0);
214 return MemMap[LHS].insert(RHS).second;
217 const MemSet *getMemoryAliases(InstantiatedValue V) const {
218 auto Itr = MemMap.find(V);
219 if (Itr == MemMap.end())
225 // We use AliasAttrMap to keep track of the AliasAttr of each node.
227 using MapType = DenseMap<InstantiatedValue, AliasAttrs>;
232 using const_iterator = MapType::const_iterator;
234 bool add(InstantiatedValue V, AliasAttrs Attr) {
235 auto &OldAttr = AttrMap[V];
236 auto NewAttr = OldAttr | Attr;
237 if (OldAttr == NewAttr)
243 AliasAttrs getAttrs(InstantiatedValue V) const {
245 auto Itr = AttrMap.find(V);
246 if (Itr != AttrMap.end())
251 iterator_range<const_iterator> mappings() const {
252 return make_range<const_iterator>(AttrMap.begin(), AttrMap.end());
256 struct WorkListItem {
257 InstantiatedValue From;
258 InstantiatedValue To;
262 struct ValueSummary {
264 InterfaceValue IValue;
267 SmallVector<Record, 4> FromRecords, ToRecords;
270 } // end anonymous namespace
274 // Specialize DenseMapInfo for OffsetValue.
275 template <> struct DenseMapInfo<OffsetValue> {
276 static OffsetValue getEmptyKey() {
277 return OffsetValue{DenseMapInfo<const Value *>::getEmptyKey(),
278 DenseMapInfo<int64_t>::getEmptyKey()};
281 static OffsetValue getTombstoneKey() {
282 return OffsetValue{DenseMapInfo<const Value *>::getTombstoneKey(),
283 DenseMapInfo<int64_t>::getEmptyKey()};
286 static unsigned getHashValue(const OffsetValue &OVal) {
287 return DenseMapInfo<std::pair<const Value *, int64_t>>::getHashValue(
288 std::make_pair(OVal.Val, OVal.Offset));
291 static bool isEqual(const OffsetValue &LHS, const OffsetValue &RHS) {
296 // Specialize DenseMapInfo for OffsetInstantiatedValue.
297 template <> struct DenseMapInfo<OffsetInstantiatedValue> {
298 static OffsetInstantiatedValue getEmptyKey() {
299 return OffsetInstantiatedValue{
300 DenseMapInfo<InstantiatedValue>::getEmptyKey(),
301 DenseMapInfo<int64_t>::getEmptyKey()};
304 static OffsetInstantiatedValue getTombstoneKey() {
305 return OffsetInstantiatedValue{
306 DenseMapInfo<InstantiatedValue>::getTombstoneKey(),
307 DenseMapInfo<int64_t>::getEmptyKey()};
310 static unsigned getHashValue(const OffsetInstantiatedValue &OVal) {
311 return DenseMapInfo<std::pair<InstantiatedValue, int64_t>>::getHashValue(
312 std::make_pair(OVal.IVal, OVal.Offset));
315 static bool isEqual(const OffsetInstantiatedValue &LHS,
316 const OffsetInstantiatedValue &RHS) {
321 } // end namespace llvm
323 class CFLAndersAAResult::FunctionInfo {
324 /// Map a value to other values that may alias it
325 /// Since the alias relation is symmetric, to save some space we assume values
326 /// are properly ordered: if a and b alias each other, and a < b, then b is in
327 /// AliasMap[a] but not vice versa.
328 DenseMap<const Value *, std::vector<OffsetValue>> AliasMap;
330 /// Map a value to its corresponding AliasAttrs
331 DenseMap<const Value *, AliasAttrs> AttrMap;
333 /// Summary of externally visible effects.
334 AliasSummary Summary;
336 Optional<AliasAttrs> getAttrs(const Value *) const;
339 FunctionInfo(const Function &, const SmallVectorImpl<Value *> &,
340 const ReachabilitySet &, const AliasAttrMap &);
342 bool mayAlias(const Value *, LocationSize, const Value *, LocationSize) const;
343 const AliasSummary &getAliasSummary() const { return Summary; }
346 static bool hasReadOnlyState(StateSet Set) {
347 return (Set & StateSet(ReadOnlyStateMask)).any();
350 static bool hasWriteOnlyState(StateSet Set) {
351 return (Set & StateSet(WriteOnlyStateMask)).any();
354 static Optional<InterfaceValue>
355 getInterfaceValue(InstantiatedValue IValue,
356 const SmallVectorImpl<Value *> &RetVals) {
357 auto Val = IValue.Val;
359 Optional<unsigned> Index;
360 if (auto Arg = dyn_cast<Argument>(Val))
361 Index = Arg->getArgNo() + 1;
362 else if (is_contained(RetVals, Val))
366 return InterfaceValue{*Index, IValue.DerefLevel};
370 static void populateAttrMap(DenseMap<const Value *, AliasAttrs> &AttrMap,
371 const AliasAttrMap &AMap) {
372 for (const auto &Mapping : AMap.mappings()) {
373 auto IVal = Mapping.first;
375 // Insert IVal into the map
376 auto &Attr = AttrMap[IVal.Val];
377 // AttrMap only cares about top-level values
378 if (IVal.DerefLevel == 0)
379 Attr |= Mapping.second;
384 populateAliasMap(DenseMap<const Value *, std::vector<OffsetValue>> &AliasMap,
385 const ReachabilitySet &ReachSet) {
386 for (const auto &OuterMapping : ReachSet.value_mappings()) {
387 // AliasMap only cares about top-level values
388 if (OuterMapping.first.DerefLevel > 0)
391 auto Val = OuterMapping.first.Val;
392 auto &AliasList = AliasMap[Val];
393 for (const auto &InnerMapping : OuterMapping.second) {
394 // Again, AliasMap only cares about top-level values
395 if (InnerMapping.first.DerefLevel == 0)
396 AliasList.push_back(OffsetValue{InnerMapping.first.Val, UnknownOffset});
399 // Sort AliasList for faster lookup
400 llvm::sort(AliasList);
404 static void populateExternalRelations(
405 SmallVectorImpl<ExternalRelation> &ExtRelations, const Function &Fn,
406 const SmallVectorImpl<Value *> &RetVals, const ReachabilitySet &ReachSet) {
407 // If a function only returns one of its argument X, then X will be both an
408 // argument and a return value at the same time. This is an edge case that
409 // needs special handling here.
410 for (const auto &Arg : Fn.args()) {
411 if (is_contained(RetVals, &Arg)) {
412 auto ArgVal = InterfaceValue{Arg.getArgNo() + 1, 0};
413 auto RetVal = InterfaceValue{0, 0};
414 ExtRelations.push_back(ExternalRelation{ArgVal, RetVal, 0});
418 // Below is the core summary construction logic.
419 // A naive solution of adding only the value aliases that are parameters or
420 // return values in ReachSet to the summary won't work: It is possible that a
421 // parameter P is written into an intermediate value I, and the function
422 // subsequently returns *I. In that case, *I is does not value alias anything
423 // in ReachSet, and the naive solution will miss a summary edge from (P, 1) to
425 // To account for the aforementioned case, we need to check each non-parameter
426 // and non-return value for the possibility of acting as an intermediate.
427 // 'ValueMap' here records, for each value, which InterfaceValues read from or
428 // write into it. If both the read list and the write list of a given value
429 // are non-empty, we know that a particular value is an intermidate and we
430 // need to add summary edges from the writes to the reads.
431 DenseMap<Value *, ValueSummary> ValueMap;
432 for (const auto &OuterMapping : ReachSet.value_mappings()) {
433 if (auto Dst = getInterfaceValue(OuterMapping.first, RetVals)) {
434 for (const auto &InnerMapping : OuterMapping.second) {
435 // If Src is a param/return value, we get a same-level assignment.
436 if (auto Src = getInterfaceValue(InnerMapping.first, RetVals)) {
437 // This may happen if both Dst and Src are return values
441 if (hasReadOnlyState(InnerMapping.second))
442 ExtRelations.push_back(ExternalRelation{*Dst, *Src, UnknownOffset});
443 // No need to check for WriteOnly state, since ReachSet is symmetric
445 // If Src is not a param/return, add it to ValueMap
446 auto SrcIVal = InnerMapping.first;
447 if (hasReadOnlyState(InnerMapping.second))
448 ValueMap[SrcIVal.Val].FromRecords.push_back(
449 ValueSummary::Record{*Dst, SrcIVal.DerefLevel});
450 if (hasWriteOnlyState(InnerMapping.second))
451 ValueMap[SrcIVal.Val].ToRecords.push_back(
452 ValueSummary::Record{*Dst, SrcIVal.DerefLevel});
458 for (const auto &Mapping : ValueMap) {
459 for (const auto &FromRecord : Mapping.second.FromRecords) {
460 for (const auto &ToRecord : Mapping.second.ToRecords) {
461 auto ToLevel = ToRecord.DerefLevel;
462 auto FromLevel = FromRecord.DerefLevel;
463 // Same-level assignments should have already been processed by now
464 if (ToLevel == FromLevel)
467 auto SrcIndex = FromRecord.IValue.Index;
468 auto SrcLevel = FromRecord.IValue.DerefLevel;
469 auto DstIndex = ToRecord.IValue.Index;
470 auto DstLevel = ToRecord.IValue.DerefLevel;
471 if (ToLevel > FromLevel)
472 SrcLevel += ToLevel - FromLevel;
474 DstLevel += FromLevel - ToLevel;
476 ExtRelations.push_back(ExternalRelation{
477 InterfaceValue{SrcIndex, SrcLevel},
478 InterfaceValue{DstIndex, DstLevel}, UnknownOffset});
483 // Remove duplicates in ExtRelations
484 llvm::sort(ExtRelations);
485 ExtRelations.erase(std::unique(ExtRelations.begin(), ExtRelations.end()),
489 static void populateExternalAttributes(
490 SmallVectorImpl<ExternalAttribute> &ExtAttributes, const Function &Fn,
491 const SmallVectorImpl<Value *> &RetVals, const AliasAttrMap &AMap) {
492 for (const auto &Mapping : AMap.mappings()) {
493 if (auto IVal = getInterfaceValue(Mapping.first, RetVals)) {
494 auto Attr = getExternallyVisibleAttrs(Mapping.second);
496 ExtAttributes.push_back(ExternalAttribute{*IVal, Attr});
501 CFLAndersAAResult::FunctionInfo::FunctionInfo(
502 const Function &Fn, const SmallVectorImpl<Value *> &RetVals,
503 const ReachabilitySet &ReachSet, const AliasAttrMap &AMap) {
504 populateAttrMap(AttrMap, AMap);
505 populateExternalAttributes(Summary.RetParamAttributes, Fn, RetVals, AMap);
506 populateAliasMap(AliasMap, ReachSet);
507 populateExternalRelations(Summary.RetParamRelations, Fn, RetVals, ReachSet);
511 CFLAndersAAResult::FunctionInfo::getAttrs(const Value *V) const {
512 assert(V != nullptr);
514 auto Itr = AttrMap.find(V);
515 if (Itr != AttrMap.end())
520 bool CFLAndersAAResult::FunctionInfo::mayAlias(
521 const Value *LHS, LocationSize MaybeLHSSize, const Value *RHS,
522 LocationSize MaybeRHSSize) const {
525 // Check if we've seen LHS and RHS before. Sometimes LHS or RHS can be created
526 // after the analysis gets executed, and we want to be conservative in those
528 auto MaybeAttrsA = getAttrs(LHS);
529 auto MaybeAttrsB = getAttrs(RHS);
530 if (!MaybeAttrsA || !MaybeAttrsB)
533 // Check AliasAttrs before AliasMap lookup since it's cheaper
534 auto AttrsA = *MaybeAttrsA;
535 auto AttrsB = *MaybeAttrsB;
536 if (hasUnknownOrCallerAttr(AttrsA))
538 if (hasUnknownOrCallerAttr(AttrsB))
540 if (isGlobalOrArgAttr(AttrsA))
541 return isGlobalOrArgAttr(AttrsB);
542 if (isGlobalOrArgAttr(AttrsB))
543 return isGlobalOrArgAttr(AttrsA);
545 // At this point both LHS and RHS should point to locally allocated objects
547 auto Itr = AliasMap.find(LHS);
548 if (Itr != AliasMap.end()) {
550 // Find out all (X, Offset) where X == RHS
551 auto Comparator = [](OffsetValue LHS, OffsetValue RHS) {
552 return std::less<const Value *>()(LHS.Val, RHS.Val);
554 #ifdef EXPENSIVE_CHECKS
555 assert(llvm::is_sorted(Itr->second, Comparator));
557 auto RangePair = std::equal_range(Itr->second.begin(), Itr->second.end(),
558 OffsetValue{RHS, 0}, Comparator);
560 if (RangePair.first != RangePair.second) {
561 // Be conservative about unknown sizes
562 if (MaybeLHSSize == LocationSize::unknown() ||
563 MaybeRHSSize == LocationSize::unknown())
566 const uint64_t LHSSize = MaybeLHSSize.getValue();
567 const uint64_t RHSSize = MaybeRHSSize.getValue();
569 for (const auto &OVal : make_range(RangePair)) {
570 // Be conservative about UnknownOffset
571 if (OVal.Offset == UnknownOffset)
574 // We know that LHS aliases (RHS + OVal.Offset) if the control flow
575 // reaches here. The may-alias query essentially becomes integer
576 // range-overlap queries over two ranges [OVal.Offset, OVal.Offset +
577 // LHSSize) and [0, RHSSize).
579 // Try to be conservative on super large offsets
580 if (LLVM_UNLIKELY(LHSSize > INT64_MAX || RHSSize > INT64_MAX))
583 auto LHSStart = OVal.Offset;
584 // FIXME: Do we need to guard against integer overflow?
585 auto LHSEnd = OVal.Offset + static_cast<int64_t>(LHSSize);
587 auto RHSEnd = static_cast<int64_t>(RHSSize);
588 if (LHSEnd > RHSStart && LHSStart < RHSEnd)
597 static void propagate(InstantiatedValue From, InstantiatedValue To,
598 MatchState State, ReachabilitySet &ReachSet,
599 std::vector<WorkListItem> &WorkList) {
602 if (ReachSet.insert(From, To, State))
603 WorkList.push_back(WorkListItem{From, To, State});
606 static void initializeWorkList(std::vector<WorkListItem> &WorkList,
607 ReachabilitySet &ReachSet,
608 const CFLGraph &Graph) {
609 for (const auto &Mapping : Graph.value_mappings()) {
610 auto Val = Mapping.first;
611 auto &ValueInfo = Mapping.second;
612 assert(ValueInfo.getNumLevels() > 0);
614 // Insert all immediate assignment neighbors to the worklist
615 for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I) {
616 auto Src = InstantiatedValue{Val, I};
617 // If there's an assignment edge from X to Y, it means Y is reachable from
618 // X at S3 and X is reachable from Y at S1
619 for (auto &Edge : ValueInfo.getNodeInfoAtLevel(I).Edges) {
620 propagate(Edge.Other, Src, MatchState::FlowFromReadOnly, ReachSet,
622 propagate(Src, Edge.Other, MatchState::FlowToWriteOnly, ReachSet,
629 static Optional<InstantiatedValue> getNodeBelow(const CFLGraph &Graph,
630 InstantiatedValue V) {
631 auto NodeBelow = InstantiatedValue{V.Val, V.DerefLevel + 1};
632 if (Graph.getNode(NodeBelow))
637 static void processWorkListItem(const WorkListItem &Item, const CFLGraph &Graph,
638 ReachabilitySet &ReachSet, AliasMemSet &MemSet,
639 std::vector<WorkListItem> &WorkList) {
640 auto FromNode = Item.From;
641 auto ToNode = Item.To;
643 auto NodeInfo = Graph.getNode(ToNode);
644 assert(NodeInfo != nullptr);
646 // TODO: propagate field offsets
648 // FIXME: Here is a neat trick we can do: since both ReachSet and MemSet holds
649 // relations that are symmetric, we could actually cut the storage by half by
650 // sorting FromNode and ToNode before insertion happens.
652 // The newly added value alias pair may potentially generate more memory
653 // alias pairs. Check for them here.
654 auto FromNodeBelow = getNodeBelow(Graph, FromNode);
655 auto ToNodeBelow = getNodeBelow(Graph, ToNode);
656 if (FromNodeBelow && ToNodeBelow &&
657 MemSet.insert(*FromNodeBelow, *ToNodeBelow)) {
658 propagate(*FromNodeBelow, *ToNodeBelow,
659 MatchState::FlowFromMemAliasNoReadWrite, ReachSet, WorkList);
660 for (const auto &Mapping : ReachSet.reachableValueAliases(*FromNodeBelow)) {
661 auto Src = Mapping.first;
662 auto MemAliasPropagate = [&](MatchState FromState, MatchState ToState) {
663 if (Mapping.second.test(static_cast<size_t>(FromState)))
664 propagate(Src, *ToNodeBelow, ToState, ReachSet, WorkList);
667 MemAliasPropagate(MatchState::FlowFromReadOnly,
668 MatchState::FlowFromMemAliasReadOnly);
669 MemAliasPropagate(MatchState::FlowToWriteOnly,
670 MatchState::FlowToMemAliasWriteOnly);
671 MemAliasPropagate(MatchState::FlowToReadWrite,
672 MatchState::FlowToMemAliasReadWrite);
676 // This is the core of the state machine walking algorithm. We expand ReachSet
677 // based on which state we are at (which in turn dictates what edges we
679 // From a high-level point of view, the state machine here guarantees two
681 // - If *X and *Y are memory aliases, then X and Y are value aliases
682 // - If Y is an alias of X, then reverse assignment edges (if there is any)
683 // should precede any assignment edges on the path from X to Y.
684 auto NextAssignState = [&](MatchState State) {
685 for (const auto &AssignEdge : NodeInfo->Edges)
686 propagate(FromNode, AssignEdge.Other, State, ReachSet, WorkList);
688 auto NextRevAssignState = [&](MatchState State) {
689 for (const auto &RevAssignEdge : NodeInfo->ReverseEdges)
690 propagate(FromNode, RevAssignEdge.Other, State, ReachSet, WorkList);
692 auto NextMemState = [&](MatchState State) {
693 if (auto AliasSet = MemSet.getMemoryAliases(ToNode)) {
694 for (const auto &MemAlias : *AliasSet)
695 propagate(FromNode, MemAlias, State, ReachSet, WorkList);
699 switch (Item.State) {
700 case MatchState::FlowFromReadOnly:
701 NextRevAssignState(MatchState::FlowFromReadOnly);
702 NextAssignState(MatchState::FlowToReadWrite);
703 NextMemState(MatchState::FlowFromMemAliasReadOnly);
706 case MatchState::FlowFromMemAliasNoReadWrite:
707 NextRevAssignState(MatchState::FlowFromReadOnly);
708 NextAssignState(MatchState::FlowToWriteOnly);
711 case MatchState::FlowFromMemAliasReadOnly:
712 NextRevAssignState(MatchState::FlowFromReadOnly);
713 NextAssignState(MatchState::FlowToReadWrite);
716 case MatchState::FlowToWriteOnly:
717 NextAssignState(MatchState::FlowToWriteOnly);
718 NextMemState(MatchState::FlowToMemAliasWriteOnly);
721 case MatchState::FlowToReadWrite:
722 NextAssignState(MatchState::FlowToReadWrite);
723 NextMemState(MatchState::FlowToMemAliasReadWrite);
726 case MatchState::FlowToMemAliasWriteOnly:
727 NextAssignState(MatchState::FlowToWriteOnly);
730 case MatchState::FlowToMemAliasReadWrite:
731 NextAssignState(MatchState::FlowToReadWrite);
736 static AliasAttrMap buildAttrMap(const CFLGraph &Graph,
737 const ReachabilitySet &ReachSet) {
738 AliasAttrMap AttrMap;
739 std::vector<InstantiatedValue> WorkList, NextList;
741 // Initialize each node with its original AliasAttrs in CFLGraph
742 for (const auto &Mapping : Graph.value_mappings()) {
743 auto Val = Mapping.first;
744 auto &ValueInfo = Mapping.second;
745 for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I) {
746 auto Node = InstantiatedValue{Val, I};
747 AttrMap.add(Node, ValueInfo.getNodeInfoAtLevel(I).Attr);
748 WorkList.push_back(Node);
752 while (!WorkList.empty()) {
753 for (const auto &Dst : WorkList) {
754 auto DstAttr = AttrMap.getAttrs(Dst);
758 // Propagate attr on the same level
759 for (const auto &Mapping : ReachSet.reachableValueAliases(Dst)) {
760 auto Src = Mapping.first;
761 if (AttrMap.add(Src, DstAttr))
762 NextList.push_back(Src);
765 // Propagate attr to the levels below
766 auto DstBelow = getNodeBelow(Graph, Dst);
768 if (AttrMap.add(*DstBelow, DstAttr)) {
769 NextList.push_back(*DstBelow);
772 DstBelow = getNodeBelow(Graph, *DstBelow);
775 WorkList.swap(NextList);
782 CFLAndersAAResult::FunctionInfo
783 CFLAndersAAResult::buildInfoFrom(const Function &Fn) {
784 CFLGraphBuilder<CFLAndersAAResult> GraphBuilder(
785 *this, GetTLI(const_cast<Function &>(Fn)),
786 // Cast away the constness here due to GraphBuilder's API requirement
787 const_cast<Function &>(Fn));
788 auto &Graph = GraphBuilder.getCFLGraph();
790 ReachabilitySet ReachSet;
793 std::vector<WorkListItem> WorkList, NextList;
794 initializeWorkList(WorkList, ReachSet, Graph);
795 // TODO: make sure we don't stop before the fix point is reached
796 while (!WorkList.empty()) {
797 for (const auto &Item : WorkList)
798 processWorkListItem(Item, Graph, ReachSet, MemSet, NextList);
800 NextList.swap(WorkList);
804 // Now that we have all the reachability info, propagate AliasAttrs according
806 auto IValueAttrMap = buildAttrMap(Graph, ReachSet);
808 return FunctionInfo(Fn, GraphBuilder.getReturnValues(), ReachSet,
809 std::move(IValueAttrMap));
812 void CFLAndersAAResult::scan(const Function &Fn) {
813 auto InsertPair = Cache.insert(std::make_pair(&Fn, Optional<FunctionInfo>()));
815 assert(InsertPair.second &&
816 "Trying to scan a function that has already been cached");
818 // Note that we can't do Cache[Fn] = buildSetsFrom(Fn) here: the function call
819 // may get evaluated after operator[], potentially triggering a DenseMap
820 // resize and invalidating the reference returned by operator[]
821 auto FunInfo = buildInfoFrom(Fn);
822 Cache[&Fn] = std::move(FunInfo);
823 Handles.emplace_front(const_cast<Function *>(&Fn), this);
826 void CFLAndersAAResult::evict(const Function *Fn) { Cache.erase(Fn); }
828 const Optional<CFLAndersAAResult::FunctionInfo> &
829 CFLAndersAAResult::ensureCached(const Function &Fn) {
830 auto Iter = Cache.find(&Fn);
831 if (Iter == Cache.end()) {
833 Iter = Cache.find(&Fn);
834 assert(Iter != Cache.end());
835 assert(Iter->second.hasValue());
840 const AliasSummary *CFLAndersAAResult::getAliasSummary(const Function &Fn) {
841 auto &FunInfo = ensureCached(Fn);
842 if (FunInfo.hasValue())
843 return &FunInfo->getAliasSummary();
848 AliasResult CFLAndersAAResult::query(const MemoryLocation &LocA,
849 const MemoryLocation &LocB) {
850 auto *ValA = LocA.Ptr;
851 auto *ValB = LocB.Ptr;
853 if (!ValA->getType()->isPointerTy() || !ValB->getType()->isPointerTy())
856 auto *Fn = parentFunctionOfValue(ValA);
858 Fn = parentFunctionOfValue(ValB);
860 // The only times this is known to happen are when globals + InlineAsm are
864 << "CFLAndersAA: could not extract parent function information.\n");
868 assert(!parentFunctionOfValue(ValB) || parentFunctionOfValue(ValB) == Fn);
871 assert(Fn != nullptr);
872 auto &FunInfo = ensureCached(*Fn);
875 if (FunInfo->mayAlias(ValA, LocA.Size, ValB, LocB.Size))
880 AliasResult CFLAndersAAResult::alias(const MemoryLocation &LocA,
881 const MemoryLocation &LocB,
883 if (LocA.Ptr == LocB.Ptr)
886 // Comparisons between global variables and other constants should be
887 // handled by BasicAA.
888 // CFLAndersAA may report NoAlias when comparing a GlobalValue and
889 // ConstantExpr, but every query needs to have at least one Value tied to a
890 // Function, and neither GlobalValues nor ConstantExprs are.
891 if (isa<Constant>(LocA.Ptr) && isa<Constant>(LocB.Ptr))
892 return AAResultBase::alias(LocA, LocB, AAQI);
894 AliasResult QueryResult = query(LocA, LocB);
895 if (QueryResult == MayAlias)
896 return AAResultBase::alias(LocA, LocB, AAQI);
901 AnalysisKey CFLAndersAA::Key;
903 CFLAndersAAResult CFLAndersAA::run(Function &F, FunctionAnalysisManager &AM) {
904 auto GetTLI = [&AM](Function &F) -> TargetLibraryInfo & {
905 return AM.getResult<TargetLibraryAnalysis>(F);
907 return CFLAndersAAResult(GetTLI);
910 char CFLAndersAAWrapperPass::ID = 0;
911 INITIALIZE_PASS(CFLAndersAAWrapperPass, "cfl-anders-aa",
912 "Inclusion-Based CFL Alias Analysis", false, true)
914 ImmutablePass *llvm::createCFLAndersAAWrapperPass() {
915 return new CFLAndersAAWrapperPass();
918 CFLAndersAAWrapperPass::CFLAndersAAWrapperPass() : ImmutablePass(ID) {
919 initializeCFLAndersAAWrapperPassPass(*PassRegistry::getPassRegistry());
922 void CFLAndersAAWrapperPass::initializePass() {
923 auto GetTLI = [this](Function &F) -> TargetLibraryInfo & {
924 return this->getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
926 Result.reset(new CFLAndersAAResult(GetTLI));
929 void CFLAndersAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
930 AU.setPreservesAll();
931 AU.addRequired<TargetLibraryInfoWrapperPass>();