LLVM  8.0.1
CFLAndersAliasAnalysis.cpp
Go to the documentation of this file.
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 
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"
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"
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 
94  : AAResultBase(std::move(RHS)), TLI(RHS.TLI) {}
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  return std::less<const Value *>()(LHS.Val, RHS.Val) ||
144  (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 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  bool insert(InstantiatedValue From, InstantiatedValue To, MatchState State) {
171  assert(From != To);
172  auto &States = ReachMap[To][From];
173  auto Idx = static_cast<size_t>(State);
174  if (!States.test(Idx)) {
175  States.set(Idx);
176  return true;
177  }
178  return false;
179  }
180 
181  // Return the set of all ('From', 'State') pair for a given node 'To'
183  reachableValueAliases(InstantiatedValue V) const {
184  auto Itr = ReachMap.find(V);
185  if (Itr == ReachMap.end())
186  return make_range<const_valuestate_iterator>(const_valuestate_iterator(),
187  const_valuestate_iterator());
188  return make_range<const_valuestate_iterator>(Itr->second.begin(),
189  Itr->second.end());
190  }
191 
192  iterator_range<const_value_iterator> value_mappings() const {
193  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 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  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  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 class AliasAttrMap {
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  if (OldAttr == NewAttr)
236  return false;
237  OldAttr = NewAttr;
238  return true;
239  }
240 
241  AliasAttrs getAttrs(InstantiatedValue V) const {
242  AliasAttrs Attr;
243  auto Itr = AttrMap.find(V);
244  if (Itr != AttrMap.end())
245  Attr = Itr->second;
246  return Attr;
247  }
248 
249  iterator_range<const_iterator> mappings() const {
250  return make_range<const_iterator>(AttrMap.begin(), AttrMap.end());
251  }
252 };
253 
254 struct WorkListItem {
257  MatchState State;
258 };
259 
260 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(),
277  }
278 
279  static OffsetValue getTombstoneKey() {
282  }
283 
284  static unsigned getHashValue(const OffsetValue &OVal) {
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{
300  }
301 
302  static OffsetInstantiatedValue getTombstoneKey() {
303  return OffsetInstantiatedValue{
306  }
307 
308  static unsigned getHashValue(const OffsetInstantiatedValue &OVal) {
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 
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.
327 
328  /// Map a value to its corresponding AliasAttrs
330 
331  /// Summary of externally visible effects.
332  AliasSummary Summary;
333 
334  Optional<AliasAttrs> getAttrs(const Value *) const;
335 
336 public:
338  const ReachabilitySet &, const AliasAttrMap &);
339 
340  bool mayAlias(const Value *, LocationSize, const Value *, LocationSize) const;
341  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 
354  const SmallVectorImpl<Value *> &RetVals) {
355  auto Val = IValue.Val;
356 
358  if (auto Arg = dyn_cast<Argument>(Val))
359  Index = Arg->getArgNo() + 1;
360  else if (is_contained(RetVals, Val))
361  Index = 0;
362 
363  if (Index)
364  return InterfaceValue{*Index, IValue.DerefLevel};
365  return None;
366 }
367 
369  const AliasAttrMap &AMap) {
370  for (const auto &Mapping : AMap.mappings()) {
371  auto IVal = Mapping.first;
372 
373  // Insert IVal into the map
374  auto &Attr = AttrMap[IVal.Val];
375  // AttrMap only cares about top-level values
376  if (IVal.DerefLevel == 0)
377  Attr |= Mapping.second;
378  }
379 }
380 
381 static void
382 populateAliasMap(DenseMap<const Value *, std::vector<OffsetValue>> &AliasMap,
383  const ReachabilitySet &ReachSet) {
384  for (const auto &OuterMapping : ReachSet.value_mappings()) {
385  // AliasMap only cares about top-level values
386  if (OuterMapping.first.DerefLevel > 0)
387  continue;
388 
389  auto Val = OuterMapping.first.Val;
390  auto &AliasList = AliasMap[Val];
391  for (const auto &InnerMapping : OuterMapping.second) {
392  // Again, AliasMap only cares about top-level values
393  if (InnerMapping.first.DerefLevel == 0)
394  AliasList.push_back(OffsetValue{InnerMapping.first.Val, UnknownOffset});
395  }
396 
397  // Sort AliasList for faster lookup
398  llvm::sort(AliasList);
399  }
400 }
401 
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  for (const auto &Arg : Fn.args()) {
409  if (is_contained(RetVals, &Arg)) {
410  auto ArgVal = InterfaceValue{Arg.getArgNo() + 1, 0};
411  auto RetVal = InterfaceValue{0, 0};
412  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.
430  for (const auto &OuterMapping : ReachSet.value_mappings()) {
431  if (auto Dst = getInterfaceValue(OuterMapping.first, RetVals)) {
432  for (const auto &InnerMapping : OuterMapping.second) {
433  // If Src is a param/return value, we get a same-level assignment.
434  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  if (hasReadOnlyState(InnerMapping.second))
440  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  auto SrcIVal = InnerMapping.first;
445  if (hasReadOnlyState(InnerMapping.second))
446  ValueMap[SrcIVal.Val].FromRecords.push_back(
447  ValueSummary::Record{*Dst, SrcIVal.DerefLevel});
448  if (hasWriteOnlyState(InnerMapping.second))
449  ValueMap[SrcIVal.Val].ToRecords.push_back(
450  ValueSummary::Record{*Dst, SrcIVal.DerefLevel});
451  }
452  }
453  }
454  }
455 
456  for (const auto &Mapping : ValueMap) {
457  for (const auto &FromRecord : Mapping.second.FromRecords) {
458  for (const auto &ToRecord : Mapping.second.ToRecords) {
459  auto ToLevel = ToRecord.DerefLevel;
460  auto FromLevel = FromRecord.DerefLevel;
461  // Same-level assignments should have already been processed by now
462  if (ToLevel == FromLevel)
463  continue;
464 
465  auto SrcIndex = FromRecord.IValue.Index;
466  auto SrcLevel = FromRecord.IValue.DerefLevel;
467  auto DstIndex = ToRecord.IValue.Index;
468  auto DstLevel = ToRecord.IValue.DerefLevel;
469  if (ToLevel > FromLevel)
470  SrcLevel += ToLevel - FromLevel;
471  else
472  DstLevel += FromLevel - ToLevel;
473 
474  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  ExtRelations.erase(std::unique(ExtRelations.begin(), ExtRelations.end()),
484  ExtRelations.end());
485 }
486 
488  SmallVectorImpl<ExternalAttribute> &ExtAttributes, const Function &Fn,
489  const SmallVectorImpl<Value *> &RetVals, const AliasAttrMap &AMap) {
490  for (const auto &Mapping : AMap.mappings()) {
491  if (auto IVal = getInterfaceValue(Mapping.first, RetVals)) {
492  auto Attr = getExternallyVisibleAttrs(Mapping.second);
493  if (Attr.any())
494  ExtAttributes.push_back(ExternalAttribute{*IVal, Attr});
495  }
496  }
497 }
498 
500  const Function &Fn, const SmallVectorImpl<Value *> &RetVals,
501  const ReachabilitySet &ReachSet, const AliasAttrMap &AMap) {
502  populateAttrMap(AttrMap, AMap);
503  populateExternalAttributes(Summary.RetParamAttributes, Fn, RetVals, AMap);
504  populateAliasMap(AliasMap, ReachSet);
505  populateExternalRelations(Summary.RetParamRelations, Fn, RetVals, ReachSet);
506 }
507 
509 CFLAndersAAResult::FunctionInfo::getAttrs(const Value *V) const {
510  assert(V != nullptr);
511 
512  auto Itr = AttrMap.find(V);
513  if (Itr != AttrMap.end())
514  return Itr->second;
515  return None;
516 }
517 
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  auto MaybeAttrsA = getAttrs(LHS);
527  auto MaybeAttrsB = getAttrs(RHS);
528  if (!MaybeAttrsA || !MaybeAttrsB)
529  return true;
530 
531  // Check AliasAttrs before AliasMap lookup since it's cheaper
532  auto AttrsA = *MaybeAttrsA;
533  auto AttrsB = *MaybeAttrsB;
534  if (hasUnknownOrCallerAttr(AttrsA))
535  return AttrsB.any();
536  if (hasUnknownOrCallerAttr(AttrsB))
537  return AttrsA.any();
538  if (isGlobalOrArgAttr(AttrsA))
539  return isGlobalOrArgAttr(AttrsB);
540  if (isGlobalOrArgAttr(AttrsB))
541  return isGlobalOrArgAttr(AttrsA);
542 
543  // At this point both LHS and RHS should point to locally allocated objects
544 
545  auto Itr = AliasMap.find(LHS);
546  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  OffsetValue{RHS, 0}, Comparator);
557 
558  if (RangePair.first != RangePair.second) {
559  // Be conservative about unknown sizes
560  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  for (const auto &OVal : make_range(RangePair)) {
568  // Be conservative about UnknownOffset
569  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  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  auto LHSEnd = OVal.Offset + static_cast<int64_t>(LHSSize);
584  auto RHSStart = 0;
585  auto RHSEnd = static_cast<int64_t>(RHSSize);
586  if (LHSEnd > RHSStart && LHSStart < RHSEnd)
587  return true;
588  }
589  }
590  }
591 
592  return false;
593 }
594 
596  MatchState State, ReachabilitySet &ReachSet,
597  std::vector<WorkListItem> &WorkList) {
598  if (From == To)
599  return;
600  if (ReachSet.insert(From, To, State))
601  WorkList.push_back(WorkListItem{From, To, State});
602 }
603 
604 static void initializeWorkList(std::vector<WorkListItem> &WorkList,
605  ReachabilitySet &ReachSet,
606  const CFLGraph &Graph) {
607  for (const auto &Mapping : Graph.value_mappings()) {
608  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  for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I) {
614  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  for (auto &Edge : ValueInfo.getNodeInfoAtLevel(I).Edges) {
618  propagate(Edge.Other, Src, MatchState::FlowFromReadOnly, ReachSet,
619  WorkList);
620  propagate(Src, Edge.Other, MatchState::FlowToWriteOnly, ReachSet,
621  WorkList);
622  }
623  }
624  }
625 }
626 
628  InstantiatedValue V) {
629  auto NodeBelow = InstantiatedValue{V.Val, V.DerefLevel + 1};
630  if (Graph.getNode(NodeBelow))
631  return NodeBelow;
632  return None;
633 }
634 
635 static void processWorkListItem(const WorkListItem &Item, const CFLGraph &Graph,
636  ReachabilitySet &ReachSet, AliasMemSet &MemSet,
637  std::vector<WorkListItem> &WorkList) {
638  auto FromNode = Item.From;
639  auto ToNode = Item.To;
640 
641  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  auto FromNodeBelow = getNodeBelow(Graph, FromNode);
653  auto ToNodeBelow = getNodeBelow(Graph, ToNode);
654  if (FromNodeBelow && ToNodeBelow &&
655  MemSet.insert(*FromNodeBelow, *ToNodeBelow)) {
656  propagate(*FromNodeBelow, *ToNodeBelow,
657  MatchState::FlowFromMemAliasNoReadWrite, ReachSet, WorkList);
658  for (const auto &Mapping : ReachSet.reachableValueAliases(*FromNodeBelow)) {
659  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  };
664 
665  MemAliasPropagate(MatchState::FlowFromReadOnly,
666  MatchState::FlowFromMemAliasReadOnly);
667  MemAliasPropagate(MatchState::FlowToWriteOnly,
668  MatchState::FlowToMemAliasWriteOnly);
669  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  };
686  auto NextRevAssignState = [&](MatchState State) {
687  for (const auto &RevAssignEdge : NodeInfo->ReverseEdges)
688  propagate(FromNode, RevAssignEdge.Other, State, ReachSet, WorkList);
689  };
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  };
696 
697  switch (Item.State) {
698  case MatchState::FlowFromReadOnly:
699  NextRevAssignState(MatchState::FlowFromReadOnly);
700  NextAssignState(MatchState::FlowToReadWrite);
701  NextMemState(MatchState::FlowFromMemAliasReadOnly);
702  break;
703 
704  case MatchState::FlowFromMemAliasNoReadWrite:
705  NextRevAssignState(MatchState::FlowFromReadOnly);
706  NextAssignState(MatchState::FlowToWriteOnly);
707  break;
708 
709  case MatchState::FlowFromMemAliasReadOnly:
710  NextRevAssignState(MatchState::FlowFromReadOnly);
711  NextAssignState(MatchState::FlowToReadWrite);
712  break;
713 
714  case MatchState::FlowToWriteOnly:
715  NextAssignState(MatchState::FlowToWriteOnly);
716  NextMemState(MatchState::FlowToMemAliasWriteOnly);
717  break;
718 
719  case MatchState::FlowToReadWrite:
720  NextAssignState(MatchState::FlowToReadWrite);
721  NextMemState(MatchState::FlowToMemAliasReadWrite);
722  break;
723 
724  case MatchState::FlowToMemAliasWriteOnly:
725  NextAssignState(MatchState::FlowToWriteOnly);
726  break;
727 
728  case MatchState::FlowToMemAliasReadWrite:
729  NextAssignState(MatchState::FlowToReadWrite);
730  break;
731  }
732 }
733 
734 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  for (const auto &Mapping : Graph.value_mappings()) {
741  auto Val = Mapping.first;
742  auto &ValueInfo = Mapping.second;
743  for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I) {
744  auto Node = InstantiatedValue{Val, I};
745  AttrMap.add(Node, ValueInfo.getNodeInfoAtLevel(I).Attr);
746  WorkList.push_back(Node);
747  }
748  }
749 
750  while (!WorkList.empty()) {
751  for (const auto &Dst : WorkList) {
752  auto DstAttr = AttrMap.getAttrs(Dst);
753  if (DstAttr.none())
754  continue;
755 
756  // Propagate attr on the same level
757  for (const auto &Mapping : ReachSet.reachableValueAliases(Dst)) {
758  auto Src = Mapping.first;
759  if (AttrMap.add(Src, DstAttr))
760  NextList.push_back(Src);
761  }
762 
763  // Propagate attr to the levels below
764  auto DstBelow = getNodeBelow(Graph, Dst);
765  while (DstBelow) {
766  if (AttrMap.add(*DstBelow, DstAttr)) {
767  NextList.push_back(*DstBelow);
768  break;
769  }
770  DstBelow = getNodeBelow(Graph, *DstBelow);
771  }
772  }
773  WorkList.swap(NextList);
774  NextList.clear();
775  }
776 
777  return AttrMap;
778 }
779 
781 CFLAndersAAResult::buildInfoFrom(const Function &Fn) {
783  *this, TLI,
784  // Cast away the constness here due to GraphBuilder's API requirement
785  const_cast<Function &>(Fn));
786  auto &Graph = GraphBuilder.getCFLGraph();
787 
788  ReachabilitySet ReachSet;
789  AliasMemSet MemSet;
790 
791  std::vector<WorkListItem> WorkList, NextList;
792  initializeWorkList(WorkList, ReachSet, Graph);
793  // TODO: make sure we don't stop before the fix point is reached
794  while (!WorkList.empty()) {
795  for (const auto &Item : WorkList)
796  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  auto IValueAttrMap = buildAttrMap(Graph, ReachSet);
805 
806  return FunctionInfo(Fn, GraphBuilder.getReturnValues(), ReachSet,
807  std::move(IValueAttrMap));
808 }
809 
810 void CFLAndersAAResult::scan(const Function &Fn) {
811  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  auto FunInfo = buildInfoFrom(Fn);
820  Cache[&Fn] = std::move(FunInfo);
821  Handles.emplace_front(const_cast<Function *>(&Fn), this);
822 }
823 
824 void CFLAndersAAResult::evict(const Function *Fn) { Cache.erase(Fn); }
825 
827 CFLAndersAAResult::ensureCached(const Function &Fn) {
828  auto Iter = Cache.find(&Fn);
829  if (Iter == Cache.end()) {
830  scan(Fn);
831  Iter = Cache.find(&Fn);
832  assert(Iter != Cache.end());
833  assert(Iter->second.hasValue());
834  }
835  return Iter->second;
836 }
837 
839  auto &FunInfo = ensureCached(Fn);
840  if (FunInfo.hasValue())
841  return &FunInfo->getAliasSummary();
842  else
843  return nullptr;
844 }
845 
847  const MemoryLocation &LocB) {
848  auto *ValA = LocA.Ptr;
849  auto *ValB = LocB.Ptr;
850 
851  if (!ValA->getType()->isPointerTy() || !ValB->getType()->isPointerTy())
852  return NoAlias;
853 
854  auto *Fn = parentFunctionOfValue(ValA);
855  if (!Fn) {
856  Fn = parentFunctionOfValue(ValB);
857  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  auto &FunInfo = ensureCached(*Fn);
871 
872  // AliasMap lookup
873  if (FunInfo->mayAlias(ValA, LocA.Size, ValB, LocB.Size))
874  return MayAlias;
875  return NoAlias;
876 }
877 
879  const MemoryLocation &LocB) {
880  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  if (isa<Constant>(LocA.Ptr) && isa<Constant>(LocB.Ptr))
889  return AAResultBase::alias(LocA, LocB);
890 
891  AliasResult QueryResult = query(LocA, LocB);
892  if (QueryResult == MayAlias)
893  return AAResultBase::alias(LocA, LocB);
894 
895  return QueryResult;
896 }
897 
898 AnalysisKey CFLAndersAA::Key;
899 
902 }
903 
906  "Inclusion-Based CFL Alias Analysis", false, true)
907 
909  return new CFLAndersAAWrapperPass();
910 }
911 
914 }
915 
917  auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>();
918  Result.reset(new CFLAndersAAResult(TLIWP.getTLI()));
919 }
920 
922  AU.setPreservesAll();
924 }
static void populateExternalAttributes(SmallVectorImpl< ExternalAttribute > &ExtAttributes, const Function &Fn, const SmallVectorImpl< Value *> &RetVals, const AliasAttrMap &AMap)
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
void evict(const Function *Fn)
Evict the given function from cache.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:770
This is the interface for LLVM&#39;s inclusion-based alias analysis implemented with CFL graph reachabili...
This class represents lattice values for constants.
Definition: AllocatorList.h:24
We use ExternalRelation to describe an externally visible aliasing relations between parameters/retur...
static void populateAliasMap(DenseMap< const Value *, std::vector< OffsetValue >> &AliasMap, const ReachabilitySet &ReachSet)
static bool mayAlias(MachineInstr &MIa, MachineInstr &MIb, AliasAnalysis *AA)
static constexpr LocationSize unknown()
Implements a dense probed hash-table based set.
Definition: DenseSet.h:250
This is the result of instantiating InterfaceValue at a particular callsite.
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
void initializeCFLAndersAAWrapperPassPass(PassRegistry &)
void initializePass() override
initializePass - This method may be overriden by immutable passes to allow them to perform various in...
The Program Expression Graph (PEG) of CFL analysis CFLGraph is auxiliary data structure used by CFL-b...
Definition: CFLGraph.h:59
The two locations do not alias at all.
Definition: AliasAnalysis.h:84
F(f)
static void populateAttrMap(DenseMap< const Value *, AliasAttrs > &AttrMap, const AliasAttrMap &AMap)
We use ExternalAttribute to describe an externally visible AliasAttrs for parameters/return value...
#define LLVM_UNLIKELY(EXPR)
Definition: Compiler.h:192
We use InterfaceValue to describe parameters/return value, as well as potential memory locations that...
AnalysisUsage & addRequired()
Definition: BitVector.h:938
static AliasAttrMap buildAttrMap(const CFLGraph &Graph, const ReachabilitySet &ReachSet)
FunctionInfo(const Function &, const SmallVectorImpl< Value *> &, const ReachabilitySet &, const AliasAttrMap &)
static bool isEqual(const OffsetValue &LHS, const OffsetValue &RHS)
#define INT64_MAX
Definition: DataTypes.h:77
CFLAndersAAResult(const TargetLibraryInfo &TLI)
const cflaa::AliasSummary * getAliasSummary(const Function &)
Get the alias summary for the given function Return nullptr if the summary is not found or not availa...
A CRTP-driven "mixin" base class to help implement the function alias analysis results concept...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
static bool isEqual(const OffsetInstantiatedValue &LHS, const OffsetInstantiatedValue &RHS)
AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:78
uint64_t getValue() const
static unsigned getHashValue(const OffsetInstantiatedValue &OVal)
AliasResult query(const MemoryLocation &, const MemoryLocation &)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:129
static bool hasWriteOnlyState(StateSet Set)
Legacy wrapper pass to provide the CFLAndersAAResult object.
static void populateExternalRelations(SmallVectorImpl< ExternalRelation > &ExtRelations, const Function &Fn, const SmallVectorImpl< Value *> &RetVals, const ReachabilitySet &ReachSet)
Represent the analysis usage information of a pass.
LocationSize Size
The maximum size of the location, in address-units, or UnknownSize if the size is not known...
const SmallVector< Value *, 4 > & getReturnValues() const
Definition: CFLGraph.h:646
bool isGlobalOrArgAttr(AliasAttrs Attr)
iterator erase(const_iterator CI)
Definition: SmallVector.h:445
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1116
Struct that holds a reference to a particular GUID in a global value summary.
The two locations may or may not alias. This is the least precise result.
Definition: AliasAnalysis.h:86
const Value * Ptr
The address of the start of the location.
Representation for a specific memory location.
The two locations precisely alias each other.
Definition: AliasAnalysis.h:90
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
See the file comment.
Definition: ValueMap.h:86
ImmutablePass class - This class is used to provide information that does not need to be run...
Definition: Pass.h:256
BlockVerifier::State From
static void initializeWorkList(std::vector< WorkListItem > &WorkList, ReachabilitySet &ReachSet, const CFLGraph &Graph)
INITIALIZE_PASS(CFLAndersAAWrapperPass, "cfl-anders-aa", "Inclusion-Based CFL Alias Analysis", false, true) ImmutablePass *llvm
AliasAttrs getExternallyVisibleAttrs(AliasAttrs Attr)
Given an AliasAttrs, return a new AliasAttrs that only contains attributes meaningful to the caller...
A builder class used to create CFLGraph instance from a given function The CFL-AA that uses this buil...
Definition: CFLGraph.h:165
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
Provides information about what library functions are available for the current target.
iterator_range< const_value_iterator > value_mappings() const
Definition: CFLGraph.h:151
Alias summary information.
This file defines various utility types and functions useful to summary-based alias analysis...
static Optional< InterfaceValue > getInterfaceValue(InstantiatedValue IValue, const SmallVectorImpl< Value *> &RetVals)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
A range adaptor for a pair of iterators.
void setPreservesAll()
Set by analyses that do not transform their input at all.
This file defines CFLGraph, an auxiliary data structure used by CFL-based alias analysis.
static void propagate(InstantiatedValue From, InstantiatedValue To, MatchState State, ReachabilitySet &ReachSet, std::vector< WorkListItem > &WorkList)
amdgpu Simplify well known AMD library false Value Value * Arg
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:133
static const int64_t UnknownOffset
This file provides utility analysis objects describing memory locations.
#define I(x, y, z)
Definition: MD5.cpp:58
static Optional< InstantiatedValue > getNodeBelow(const CFLGraph &Graph, InstantiatedValue V)
static void processWorkListItem(const WorkListItem &Item, const CFLGraph &Graph, ReachabilitySet &ReachSet, AliasMemSet &MemSet, std::vector< WorkListItem > &WorkList)
bool hasUnknownOrCallerAttr(AliasAttrs Attr)
std::bitset< NumAliasAttrs > AliasAttrs
These are attributes that an alias analysis can use to mark certain special properties of a given poi...
static bool hasReadOnlyState(StateSet Set)
const AliasSummary & getAliasSummary() const
Analysis pass providing the TargetLibraryInfo.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
CFLAndersAAResult run(Function &F, FunctionAnalysisManager &AM)
static const Function * parentFunctionOfValue(const Value *Val)
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:326
LLVM Value Representation.
Definition: Value.h:73
const CFLGraph & getCFLGraph() const
Definition: CFLGraph.h:645
A container for analyses that lazily runs them and caches their results.
AliasResult alias(const MemoryLocation &, const MemoryLocation &)
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1967
ImmutablePass * createCFLAndersAAWrapperPass()
bool mayAlias(const Value *, LocationSize, const Value *, LocationSize) const
static unsigned getHashValue(const OffsetValue &OVal)
This header defines various interfaces for pass management in LLVM.
#define LLVM_DEBUG(X)
Definition: Debug.h:123
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:71
iterator_range< arg_iterator > args()
Definition: Function.h:689
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1245