LLVM  16.0.0git
CFLAndersAliasAnalysis.cpp
Go to the documentation of this file.
1 //===- CFLAndersAliasAnalysis.cpp - Unification-based Alias Analysis ------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements a CFL-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.
17 //
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.
28 //
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
45 // read from.
46 //
47 //===----------------------------------------------------------------------===//
48 
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.
54 
56 #include "AliasAnalysisSummary.h"
57 #include "CFLGraph.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"
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"
78 #include <algorithm>
79 #include <bitset>
80 #include <cassert>
81 #include <cstddef>
82 #include <cstdint>
83 #include <functional>
84 #include <optional>
85 #include <utility>
86 #include <vector>
87 
88 using namespace llvm;
89 using namespace llvm::cflaa;
90 
91 #define DEBUG_TYPE "cfl-anders-aa"
92 
94  std::function<const TargetLibraryInfo &(Function &F)> GetTLI)
95  : GetTLI(std::move(GetTLI)) {}
97  : AAResultBase(std::move(RHS)), GetTLI(std::move(RHS.GetTLI)) {}
99 
100 namespace {
101 
102 enum class MatchState : uint8_t {
103  // The following state represents S1 in the paper.
104  FlowFromReadOnly = 0,
105  // The following two states together represent S2 in the paper.
106  // The 'NoReadWrite' suffix indicates that there exists an alias path that
107  // does not contain assignment and reverse assignment edges.
108  // The 'ReadOnly' suffix indicates that there exists an alias path that
109  // contains reverse assignment edges only.
110  FlowFromMemAliasNoReadWrite,
111  FlowFromMemAliasReadOnly,
112  // The following two states together represent S3 in the paper.
113  // The 'WriteOnly' suffix indicates that there exists an alias path that
114  // contains assignment edges only.
115  // The 'ReadWrite' suffix indicates that there exists an alias path that
116  // contains both assignment and reverse assignment edges. Note that if X and Y
117  // are reachable at 'ReadWrite' state, it does NOT mean X is both read from
118  // and written to Y. Instead, it means that a third value Z is written to both
119  // X and Y.
120  FlowToWriteOnly,
121  FlowToReadWrite,
122  // The following two states together represent S4 in the paper.
123  FlowToMemAliasWriteOnly,
124  FlowToMemAliasReadWrite,
125 };
126 
127 using StateSet = std::bitset<7>;
128 
129 const unsigned ReadOnlyStateMask =
130  (1U << static_cast<uint8_t>(MatchState::FlowFromReadOnly)) |
131  (1U << static_cast<uint8_t>(MatchState::FlowFromMemAliasReadOnly));
132 const unsigned WriteOnlyStateMask =
133  (1U << static_cast<uint8_t>(MatchState::FlowToWriteOnly)) |
134  (1U << static_cast<uint8_t>(MatchState::FlowToMemAliasWriteOnly));
135 
136 // A pair that consists of a value and an offset
137 struct OffsetValue {
138  const Value *Val;
139  int64_t Offset;
140 };
141 
142 bool operator==(OffsetValue LHS, OffsetValue RHS) {
143  return LHS.Val == RHS.Val && LHS.Offset == RHS.Offset;
144 }
145 bool operator<(OffsetValue LHS, OffsetValue RHS) {
146  return std::less<const Value *>()(LHS.Val, RHS.Val) ||
147  (LHS.Val == RHS.Val && LHS.Offset < RHS.Offset);
148 }
149 
150 // A pair that consists of an InstantiatedValue and an offset
151 struct OffsetInstantiatedValue {
152  InstantiatedValue IVal;
153  int64_t Offset;
154 };
155 
156 bool operator==(OffsetInstantiatedValue LHS, OffsetInstantiatedValue RHS) {
157  return LHS.IVal == RHS.IVal && LHS.Offset == RHS.Offset;
158 }
159 
160 // We use ReachabilitySet to keep track of value aliases (The nonterminal "V" in
161 // the paper) during the analysis.
162 class ReachabilitySet {
163  using ValueStateMap = DenseMap<InstantiatedValue, StateSet>;
164  using ValueReachMap = DenseMap<InstantiatedValue, ValueStateMap>;
165 
166  ValueReachMap ReachMap;
167 
168 public:
169  using const_valuestate_iterator = ValueStateMap::const_iterator;
170  using const_value_iterator = ValueReachMap::const_iterator;
171 
172  // Insert edge 'From->To' at state 'State'
173  bool insert(InstantiatedValue From, InstantiatedValue To, MatchState State) {
174  assert(From != To);
175  auto &States = ReachMap[To][From];
176  auto Idx = static_cast<size_t>(State);
177  if (!States.test(Idx)) {
178  States.set(Idx);
179  return true;
180  }
181  return false;
182  }
183 
184  // Return the set of all ('From', 'State') pair for a given node 'To'
186  reachableValueAliases(InstantiatedValue V) const {
187  auto Itr = ReachMap.find(V);
188  if (Itr == ReachMap.end())
189  return make_range<const_valuestate_iterator>(const_valuestate_iterator(),
190  const_valuestate_iterator());
191  return make_range<const_valuestate_iterator>(Itr->second.begin(),
192  Itr->second.end());
193  }
194 
195  iterator_range<const_value_iterator> value_mappings() const {
196  return make_range<const_value_iterator>(ReachMap.begin(), ReachMap.end());
197  }
198 };
199 
200 // We use AliasMemSet to keep track of all memory aliases (the nonterminal "M"
201 // in the paper) during the analysis.
202 class AliasMemSet {
203  using MemSet = DenseSet<InstantiatedValue>;
204  using MemMapType = DenseMap<InstantiatedValue, MemSet>;
205 
206  MemMapType MemMap;
207 
208 public:
209  using const_mem_iterator = MemSet::const_iterator;
210 
212  // Top-level values can never be memory aliases because one cannot take the
213  // addresses of them
214  assert(LHS.DerefLevel > 0 && RHS.DerefLevel > 0);
215  return MemMap[LHS].insert(RHS).second;
216  }
217 
218  const MemSet *getMemoryAliases(InstantiatedValue V) const {
219  auto Itr = MemMap.find(V);
220  if (Itr == MemMap.end())
221  return nullptr;
222  return &Itr->second;
223  }
224 };
225 
226 // We use AliasAttrMap to keep track of the AliasAttr of each node.
227 class AliasAttrMap {
229 
230  MapType AttrMap;
231 
232 public:
233  using const_iterator = MapType::const_iterator;
234 
235  bool add(InstantiatedValue V, AliasAttrs Attr) {
236  auto &OldAttr = AttrMap[V];
237  auto NewAttr = OldAttr | Attr;
238  if (OldAttr == NewAttr)
239  return false;
240  OldAttr = NewAttr;
241  return true;
242  }
243 
244  AliasAttrs getAttrs(InstantiatedValue V) const {
245  AliasAttrs Attr;
246  auto Itr = AttrMap.find(V);
247  if (Itr != AttrMap.end())
248  Attr = Itr->second;
249  return Attr;
250  }
251 
252  iterator_range<const_iterator> mappings() const {
253  return make_range<const_iterator>(AttrMap.begin(), AttrMap.end());
254  }
255 };
256 
257 struct WorkListItem {
260  MatchState State;
261 };
262 
263 struct ValueSummary {
264  struct Record {
265  InterfaceValue IValue;
266  unsigned DerefLevel;
267  };
268  SmallVector<Record, 4> FromRecords, ToRecords;
269 };
270 
271 } // end anonymous namespace
272 
273 namespace llvm {
274 
275 // Specialize DenseMapInfo for OffsetValue.
276 template <> struct DenseMapInfo<OffsetValue> {
277  static OffsetValue getEmptyKey() {
278  return OffsetValue{DenseMapInfo<const Value *>::getEmptyKey(),
280  }
281 
282  static OffsetValue getTombstoneKey() {
285  }
286 
287  static unsigned getHashValue(const OffsetValue &OVal) {
289  std::make_pair(OVal.Val, OVal.Offset));
290  }
291 
292  static bool isEqual(const OffsetValue &LHS, const OffsetValue &RHS) {
293  return LHS == RHS;
294  }
295 };
296 
297 // Specialize DenseMapInfo for OffsetInstantiatedValue.
298 template <> struct DenseMapInfo<OffsetInstantiatedValue> {
299  static OffsetInstantiatedValue getEmptyKey() {
300  return OffsetInstantiatedValue{
303  }
304 
305  static OffsetInstantiatedValue getTombstoneKey() {
306  return OffsetInstantiatedValue{
309  }
310 
311  static unsigned getHashValue(const OffsetInstantiatedValue &OVal) {
313  std::make_pair(OVal.IVal, OVal.Offset));
314  }
315 
316  static bool isEqual(const OffsetInstantiatedValue &LHS,
317  const OffsetInstantiatedValue &RHS) {
318  return LHS == RHS;
319  }
320 };
321 
322 } // end namespace llvm
323 
325  /// Map a value to other values that may alias it
326  /// Since the alias relation is symmetric, to save some space we assume values
327  /// are properly ordered: if a and b alias each other, and a < b, then b is in
328  /// AliasMap[a] but not vice versa.
330 
331  /// Map a value to its corresponding AliasAttrs
333 
334  /// Summary of externally visible effects.
335  AliasSummary Summary;
336 
337  Optional<AliasAttrs> getAttrs(const Value *) const;
338 
339 public:
341  const ReachabilitySet &, const AliasAttrMap &);
342 
343  bool mayAlias(const Value *, LocationSize, const Value *, LocationSize) const;
344  const AliasSummary &getAliasSummary() const { return Summary; }
345 };
346 
347 static bool hasReadOnlyState(StateSet Set) {
348  return (Set & StateSet(ReadOnlyStateMask)).any();
349 }
350 
351 static bool hasWriteOnlyState(StateSet Set) {
352  return (Set & StateSet(WriteOnlyStateMask)).any();
353 }
354 
355 static std::optional<InterfaceValue>
357  const SmallVectorImpl<Value *> &RetVals) {
358  auto Val = IValue.Val;
359 
360  std::optional<unsigned> Index;
361  if (auto Arg = dyn_cast<Argument>(Val))
362  Index = Arg->getArgNo() + 1;
363  else if (is_contained(RetVals, Val))
364  Index = 0;
365 
366  if (Index)
367  return InterfaceValue{*Index, IValue.DerefLevel};
368  return None;
369 }
370 
372  const AliasAttrMap &AMap) {
373  for (const auto &Mapping : AMap.mappings()) {
374  auto IVal = Mapping.first;
375 
376  // Insert IVal into the map
377  auto &Attr = AttrMap[IVal.Val];
378  // AttrMap only cares about top-level values
379  if (IVal.DerefLevel == 0)
380  Attr |= Mapping.second;
381  }
382 }
383 
384 static void
385 populateAliasMap(DenseMap<const Value *, std::vector<OffsetValue>> &AliasMap,
386  const ReachabilitySet &ReachSet) {
387  for (const auto &OuterMapping : ReachSet.value_mappings()) {
388  // AliasMap only cares about top-level values
389  if (OuterMapping.first.DerefLevel > 0)
390  continue;
391 
392  auto Val = OuterMapping.first.Val;
393  auto &AliasList = AliasMap[Val];
394  for (const auto &InnerMapping : OuterMapping.second) {
395  // Again, AliasMap only cares about top-level values
396  if (InnerMapping.first.DerefLevel == 0)
397  AliasList.push_back(OffsetValue{InnerMapping.first.Val, UnknownOffset});
398  }
399 
400  // Sort AliasList for faster lookup
401  llvm::sort(AliasList);
402  }
403 }
404 
406  SmallVectorImpl<ExternalRelation> &ExtRelations, const Function &Fn,
407  const SmallVectorImpl<Value *> &RetVals, const ReachabilitySet &ReachSet) {
408  // If a function only returns one of its argument X, then X will be both an
409  // argument and a return value at the same time. This is an edge case that
410  // needs special handling here.
411  for (const auto &Arg : Fn.args()) {
412  if (is_contained(RetVals, &Arg)) {
413  auto ArgVal = InterfaceValue{Arg.getArgNo() + 1, 0};
414  auto RetVal = InterfaceValue{0, 0};
415  ExtRelations.push_back(ExternalRelation{ArgVal, RetVal, 0});
416  }
417  }
418 
419  // Below is the core summary construction logic.
420  // A naive solution of adding only the value aliases that are parameters or
421  // return values in ReachSet to the summary won't work: It is possible that a
422  // parameter P is written into an intermediate value I, and the function
423  // subsequently returns *I. In that case, *I is does not value alias anything
424  // in ReachSet, and the naive solution will miss a summary edge from (P, 1) to
425  // (I, 1).
426  // To account for the aforementioned case, we need to check each non-parameter
427  // and non-return value for the possibility of acting as an intermediate.
428  // 'ValueMap' here records, for each value, which InterfaceValues read from or
429  // write into it. If both the read list and the write list of a given value
430  // are non-empty, we know that a particular value is an intermidate and we
431  // need to add summary edges from the writes to the reads.
433  for (const auto &OuterMapping : ReachSet.value_mappings()) {
434  if (auto Dst = getInterfaceValue(OuterMapping.first, RetVals)) {
435  for (const auto &InnerMapping : OuterMapping.second) {
436  // If Src is a param/return value, we get a same-level assignment.
437  if (auto Src = getInterfaceValue(InnerMapping.first, RetVals)) {
438  // This may happen if both Dst and Src are return values
439  if (*Dst == *Src)
440  continue;
441 
442  if (hasReadOnlyState(InnerMapping.second))
443  ExtRelations.push_back(ExternalRelation{*Dst, *Src, UnknownOffset});
444  // No need to check for WriteOnly state, since ReachSet is symmetric
445  } else {
446  // If Src is not a param/return, add it to ValueMap
447  auto SrcIVal = InnerMapping.first;
448  if (hasReadOnlyState(InnerMapping.second))
449  ValueMap[SrcIVal.Val].FromRecords.push_back(
450  ValueSummary::Record{*Dst, SrcIVal.DerefLevel});
451  if (hasWriteOnlyState(InnerMapping.second))
452  ValueMap[SrcIVal.Val].ToRecords.push_back(
453  ValueSummary::Record{*Dst, SrcIVal.DerefLevel});
454  }
455  }
456  }
457  }
458 
459  for (const auto &Mapping : ValueMap) {
460  for (const auto &FromRecord : Mapping.second.FromRecords) {
461  for (const auto &ToRecord : Mapping.second.ToRecords) {
462  auto ToLevel = ToRecord.DerefLevel;
463  auto FromLevel = FromRecord.DerefLevel;
464  // Same-level assignments should have already been processed by now
465  if (ToLevel == FromLevel)
466  continue;
467 
468  auto SrcIndex = FromRecord.IValue.Index;
469  auto SrcLevel = FromRecord.IValue.DerefLevel;
470  auto DstIndex = ToRecord.IValue.Index;
471  auto DstLevel = ToRecord.IValue.DerefLevel;
472  if (ToLevel > FromLevel)
473  SrcLevel += ToLevel - FromLevel;
474  else
475  DstLevel += FromLevel - ToLevel;
476 
477  ExtRelations.push_back(ExternalRelation{
478  InterfaceValue{SrcIndex, SrcLevel},
479  InterfaceValue{DstIndex, DstLevel}, UnknownOffset});
480  }
481  }
482  }
483 
484  // Remove duplicates in ExtRelations
485  llvm::sort(ExtRelations);
486  ExtRelations.erase(std::unique(ExtRelations.begin(), ExtRelations.end()),
487  ExtRelations.end());
488 }
489 
491  SmallVectorImpl<ExternalAttribute> &ExtAttributes, const Function &Fn,
492  const SmallVectorImpl<Value *> &RetVals, const AliasAttrMap &AMap) {
493  for (const auto &Mapping : AMap.mappings()) {
494  if (auto IVal = getInterfaceValue(Mapping.first, RetVals)) {
495  auto Attr = getExternallyVisibleAttrs(Mapping.second);
496  if (Attr.any())
497  ExtAttributes.push_back(ExternalAttribute{*IVal, Attr});
498  }
499  }
500 }
501 
503  const Function &Fn, const SmallVectorImpl<Value *> &RetVals,
504  const ReachabilitySet &ReachSet, const AliasAttrMap &AMap) {
505  populateAttrMap(AttrMap, AMap);
506  populateExternalAttributes(Summary.RetParamAttributes, Fn, RetVals, AMap);
507  populateAliasMap(AliasMap, ReachSet);
508  populateExternalRelations(Summary.RetParamRelations, Fn, RetVals, ReachSet);
509 }
510 
512 CFLAndersAAResult::FunctionInfo::getAttrs(const Value *V) const {
513  assert(V != nullptr);
514 
515  auto Itr = AttrMap.find(V);
516  if (Itr != AttrMap.end())
517  return Itr->second;
518  return None;
519 }
520 
522  const Value *LHS, LocationSize MaybeLHSSize, const Value *RHS,
523  LocationSize MaybeRHSSize) const {
524  assert(LHS && RHS);
525 
526  // Check if we've seen LHS and RHS before. Sometimes LHS or RHS can be created
527  // after the analysis gets executed, and we want to be conservative in those
528  // cases.
529  auto MaybeAttrsA = getAttrs(LHS);
530  auto MaybeAttrsB = getAttrs(RHS);
531  if (!MaybeAttrsA || !MaybeAttrsB)
532  return true;
533 
534  // Check AliasAttrs before AliasMap lookup since it's cheaper
535  auto AttrsA = *MaybeAttrsA;
536  auto AttrsB = *MaybeAttrsB;
537  if (hasUnknownOrCallerAttr(AttrsA))
538  return AttrsB.any();
539  if (hasUnknownOrCallerAttr(AttrsB))
540  return AttrsA.any();
541  if (isGlobalOrArgAttr(AttrsA))
542  return isGlobalOrArgAttr(AttrsB);
543  if (isGlobalOrArgAttr(AttrsB))
544  return isGlobalOrArgAttr(AttrsA);
545 
546  // At this point both LHS and RHS should point to locally allocated objects
547 
548  auto Itr = AliasMap.find(LHS);
549  if (Itr != AliasMap.end()) {
550 
551  // Find out all (X, Offset) where X == RHS
552  auto Comparator = [](OffsetValue LHS, OffsetValue RHS) {
553  return std::less<const Value *>()(LHS.Val, RHS.Val);
554  };
555 #ifdef EXPENSIVE_CHECKS
556  assert(llvm::is_sorted(Itr->second, Comparator));
557 #endif
558  auto RangePair = std::equal_range(Itr->second.begin(), Itr->second.end(),
559  OffsetValue{RHS, 0}, Comparator);
560 
561  if (RangePair.first != RangePair.second) {
562  // Be conservative about unknown sizes
563  if (!MaybeLHSSize.hasValue() || !MaybeRHSSize.hasValue())
564  return true;
565 
566  const uint64_t LHSSize = MaybeLHSSize.getValue();
567  const uint64_t RHSSize = MaybeRHSSize.getValue();
568 
569  for (const auto &OVal : make_range(RangePair)) {
570  // Be conservative about UnknownOffset
571  if (OVal.Offset == UnknownOffset)
572  return true;
573 
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).
578 
579  // Try to be conservative on super large offsets
580  if (LLVM_UNLIKELY(LHSSize > INT64_MAX || RHSSize > INT64_MAX))
581  return true;
582 
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);
586  auto RHSStart = 0;
587  auto RHSEnd = static_cast<int64_t>(RHSSize);
588  if (LHSEnd > RHSStart && LHSStart < RHSEnd)
589  return true;
590  }
591  }
592  }
593 
594  return false;
595 }
596 
598  MatchState State, ReachabilitySet &ReachSet,
599  std::vector<WorkListItem> &WorkList) {
600  if (From == To)
601  return;
602  if (ReachSet.insert(From, To, State))
603  WorkList.push_back(WorkListItem{From, To, State});
604 }
605 
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);
613 
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 (const auto &Edge : ValueInfo.getNodeInfoAtLevel(I).Edges) {
620  propagate(Edge.Other, Src, MatchState::FlowFromReadOnly, ReachSet,
621  WorkList);
622  propagate(Src, Edge.Other, MatchState::FlowToWriteOnly, ReachSet,
623  WorkList);
624  }
625  }
626  }
627 }
628 
629 static std::optional<InstantiatedValue> getNodeBelow(const CFLGraph &Graph,
630  InstantiatedValue V) {
631  auto NodeBelow = InstantiatedValue{V.Val, V.DerefLevel + 1};
632  if (Graph.getNode(NodeBelow))
633  return NodeBelow;
634  return None;
635 }
636 
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;
642 
643  auto NodeInfo = Graph.getNode(ToNode);
644  assert(NodeInfo != nullptr);
645 
646  // TODO: propagate field offsets
647 
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.
651 
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);
665  };
666 
667  MemAliasPropagate(MatchState::FlowFromReadOnly,
668  MatchState::FlowFromMemAliasReadOnly);
669  MemAliasPropagate(MatchState::FlowToWriteOnly,
670  MatchState::FlowToMemAliasWriteOnly);
671  MemAliasPropagate(MatchState::FlowToReadWrite,
672  MatchState::FlowToMemAliasReadWrite);
673  }
674  }
675 
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
678  // should examine)
679  // From a high-level point of view, the state machine here guarantees two
680  // properties:
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);
687  };
688  auto NextRevAssignState = [&](MatchState State) {
689  for (const auto &RevAssignEdge : NodeInfo->ReverseEdges)
690  propagate(FromNode, RevAssignEdge.Other, State, ReachSet, WorkList);
691  };
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);
696  }
697  };
698 
699  switch (Item.State) {
700  case MatchState::FlowFromReadOnly:
701  NextRevAssignState(MatchState::FlowFromReadOnly);
702  NextAssignState(MatchState::FlowToReadWrite);
703  NextMemState(MatchState::FlowFromMemAliasReadOnly);
704  break;
705 
706  case MatchState::FlowFromMemAliasNoReadWrite:
707  NextRevAssignState(MatchState::FlowFromReadOnly);
708  NextAssignState(MatchState::FlowToWriteOnly);
709  break;
710 
711  case MatchState::FlowFromMemAliasReadOnly:
712  NextRevAssignState(MatchState::FlowFromReadOnly);
713  NextAssignState(MatchState::FlowToReadWrite);
714  break;
715 
716  case MatchState::FlowToWriteOnly:
717  NextAssignState(MatchState::FlowToWriteOnly);
718  NextMemState(MatchState::FlowToMemAliasWriteOnly);
719  break;
720 
721  case MatchState::FlowToReadWrite:
722  NextAssignState(MatchState::FlowToReadWrite);
723  NextMemState(MatchState::FlowToMemAliasReadWrite);
724  break;
725 
726  case MatchState::FlowToMemAliasWriteOnly:
727  NextAssignState(MatchState::FlowToWriteOnly);
728  break;
729 
730  case MatchState::FlowToMemAliasReadWrite:
731  NextAssignState(MatchState::FlowToReadWrite);
732  break;
733  }
734 }
735 
736 static AliasAttrMap buildAttrMap(const CFLGraph &Graph,
737  const ReachabilitySet &ReachSet) {
738  AliasAttrMap AttrMap;
739  std::vector<InstantiatedValue> WorkList, NextList;
740 
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);
749  }
750  }
751 
752  while (!WorkList.empty()) {
753  for (const auto &Dst : WorkList) {
754  auto DstAttr = AttrMap.getAttrs(Dst);
755  if (DstAttr.none())
756  continue;
757 
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);
763  }
764 
765  // Propagate attr to the levels below
766  auto DstBelow = getNodeBelow(Graph, Dst);
767  while (DstBelow) {
768  if (AttrMap.add(*DstBelow, DstAttr)) {
769  NextList.push_back(*DstBelow);
770  break;
771  }
772  DstBelow = getNodeBelow(Graph, *DstBelow);
773  }
774  }
775  WorkList.swap(NextList);
776  NextList.clear();
777  }
778 
779  return AttrMap;
780 }
781 
783 CFLAndersAAResult::buildInfoFrom(const Function &Fn) {
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();
789 
790  ReachabilitySet ReachSet;
791  AliasMemSet MemSet;
792 
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);
799 
800  NextList.swap(WorkList);
801  NextList.clear();
802  }
803 
804  // Now that we have all the reachability info, propagate AliasAttrs according
805  // to it
806  auto IValueAttrMap = buildAttrMap(Graph, ReachSet);
807 
808  return FunctionInfo(Fn, GraphBuilder.getReturnValues(), ReachSet,
809  std::move(IValueAttrMap));
810 }
811 
812 void CFLAndersAAResult::scan(const Function &Fn) {
813  auto InsertPair = Cache.insert(std::make_pair(&Fn, Optional<FunctionInfo>()));
814  (void)InsertPair;
815  assert(InsertPair.second &&
816  "Trying to scan a function that has already been cached");
817 
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);
824 }
825 
826 void CFLAndersAAResult::evict(const Function *Fn) { Cache.erase(Fn); }
827 
829 CFLAndersAAResult::ensureCached(const Function &Fn) {
830  auto Iter = Cache.find(&Fn);
831  if (Iter == Cache.end()) {
832  scan(Fn);
833  Iter = Cache.find(&Fn);
834  assert(Iter != Cache.end());
835  assert(Iter->second);
836  }
837  return Iter->second;
838 }
839 
840 const AliasSummary *CFLAndersAAResult::getAliasSummary(const Function &Fn) {
841  auto &FunInfo = ensureCached(Fn);
842  if (FunInfo)
843  return &FunInfo->getAliasSummary();
844  else
845  return nullptr;
846 }
847 
849  const MemoryLocation &LocB) {
850  auto *ValA = LocA.Ptr;
851  auto *ValB = LocB.Ptr;
852 
853  if (!ValA->getType()->isPointerTy() || !ValB->getType()->isPointerTy())
854  return AliasResult::NoAlias;
855 
856  auto *Fn = parentFunctionOfValue(ValA);
857  if (!Fn) {
858  Fn = parentFunctionOfValue(ValB);
859  if (!Fn) {
860  // The only times this is known to happen are when globals + InlineAsm are
861  // involved
862  LLVM_DEBUG(
863  dbgs()
864  << "CFLAndersAA: could not extract parent function information.\n");
865  return AliasResult::MayAlias;
866  }
867  } else {
868  assert(!parentFunctionOfValue(ValB) || parentFunctionOfValue(ValB) == Fn);
869  }
870 
871  assert(Fn != nullptr);
872  auto &FunInfo = ensureCached(*Fn);
873 
874  // AliasMap lookup
875  if (FunInfo->mayAlias(ValA, LocA.Size, ValB, LocB.Size))
876  return AliasResult::MayAlias;
877  return AliasResult::NoAlias;
878 }
879 
880 AliasResult CFLAndersAAResult::alias(const MemoryLocation &LocA,
881  const MemoryLocation &LocB,
882  AAQueryInfo &AAQI) {
883  if (LocA.Ptr == LocB.Ptr)
884  return AliasResult::MustAlias;
885 
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);
893 
894  AliasResult QueryResult = query(LocA, LocB);
895  if (QueryResult == AliasResult::MayAlias)
896  return AAResultBase::alias(LocA, LocB, AAQI);
897 
898  return QueryResult;
899 }
900 
902 
904  auto GetTLI = [&AM](Function &F) -> TargetLibraryInfo & {
905  return AM.getResult<TargetLibraryAnalysis>(F);
906  };
907  return CFLAndersAAResult(GetTLI);
908 }
909 
912  "Inclusion-Based CFL Alias Analysis", false, true)
913 
915  return new CFLAndersAAWrapperPass();
916 }
917 
918 CFLAndersAAWrapperPass::CFLAndersAAWrapperPass() : ImmutablePass(ID) {
920 }
921 
923  auto GetTLI = [this](Function &F) -> TargetLibraryInfo & {
924  return this->getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
925  };
926  Result.reset(new CFLAndersAAResult(GetTLI));
927 }
928 
930  AU.setPreservesAll();
932 }
llvm::cflaa::CFLGraph
The Program Expression Graph (PEG) of CFL analysis CFLGraph is auxiliary data structure used by CFL-b...
Definition: CFLGraph.h:57
llvm::CFLAndersAAWrapperPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: CFLAndersAliasAnalysis.cpp:929
scan
static Expected< BitVector > scan(StringRef &S, StringRef Original)
Definition: GlobPattern.cpp:67
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::SmallVectorImpl::erase
iterator erase(const_iterator CI)
Definition: SmallVector.h:741
llvm::Function::args
iterator_range< arg_iterator > args()
Definition: Function.h:746
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
Optional.h
llvm::DenseMapInfo< OffsetValue >::getEmptyKey
static OffsetValue getEmptyKey()
Definition: CFLAndersAliasAnalysis.cpp:277
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
llvm::cflaa::InstantiatedValue::Val
Value * Val
Definition: AliasAnalysisSummary.h:203
llvm::createCFLAndersAAWrapperPass
ImmutablePass * createCFLAndersAAWrapperPass()
llvm::ImmutablePass
ImmutablePass class - This class is used to provide information that does not need to be run.
Definition: Pass.h:279
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
llvm::MemoryLocation::Ptr
const Value * Ptr
The address of the start of the location.
Definition: MemoryLocation.h:218
llvm::Function
Definition: Function.h:60
buildAttrMap
static AliasAttrMap buildAttrMap(const CFLGraph &Graph, const ReachabilitySet &ReachSet)
Definition: CFLAndersAliasAnalysis.cpp:736
Pass.h
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
llvm::DenseMapInfo< OffsetInstantiatedValue >::getHashValue
static unsigned getHashValue(const OffsetInstantiatedValue &OVal)
Definition: CFLAndersAliasAnalysis.cpp:311
AliasAnalysisSummary.h
llvm::AliasSummary
Alias summary information.
Definition: ModuleSummaryIndex.h:523
llvm::MemoryLocation::Size
LocationSize Size
The maximum size of the location, in address-units, or UnknownSize if the size is not known.
Definition: MemoryLocation.h:227
DenseMap.h
llvm::cflaa::CFLGraphBuilder
A builder class used to create CFLGraph instance from a given function The CFL-AA that uses this buil...
Definition: CFLGraph.h:163
llvm::Optional
Definition: APInt.h:33
llvm::cflaa::InterfaceValue
We use InterfaceValue to describe parameters/return value, as well as potential memory locations that...
Definition: AliasAnalysisSummary.h:114
llvm::AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:83
STLExtras.h
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::initializeCFLAndersAAWrapperPassPass
void initializeCFLAndersAAWrapperPassPass(PassRegistry &)
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::cflaa::InstantiatedValue::DerefLevel
unsigned DerefLevel
Definition: AliasAnalysisSummary.h:204
F
#define F(x, y, z)
Definition: MD5.cpp:55
AliasAnalysis.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::cflaa::ExternalRelation
We use ExternalRelation to describe an externally visible aliasing relations between parameters/retur...
Definition: AliasAnalysisSummary.h:153
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:187
llvm::AAQueryInfo
This class stores info we want to provide to or retain within an alias query.
Definition: AliasAnalysis.h:233
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
llvm::DenseMapInfo
An information struct used to provide DenseMap with the various necessary components for a given valu...
Definition: APInt.h:34
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::LocationSize
Definition: MemoryLocation.h:66
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::CFLAndersAAResult::FunctionInfo
Definition: CFLAndersAliasAnalysis.cpp:324
llvm::LocationSize::getValue
uint64_t getValue() const
Definition: MemoryLocation.h:159
llvm::CFLAndersAAResult::FunctionInfo::FunctionInfo
FunctionInfo(const Function &, const SmallVectorImpl< Value * > &, const ReachabilitySet &, const AliasAttrMap &)
Definition: CFLAndersAliasAnalysis.cpp:502
llvm::AliasSet
Definition: AliasSetTracker.h:49
llvm::AMDGPU::PALMD::Key
Key
PAL metadata keys.
Definition: AMDGPUMetadata.h:486
populateAttrMap
static void populateAttrMap(DenseMap< const Value *, AliasAttrs > &AttrMap, const AliasAttrMap &AMap)
Definition: CFLAndersAliasAnalysis.cpp:371
DenseSet.h
populateExternalAttributes
static void populateExternalAttributes(SmallVectorImpl< ExternalAttribute > &ExtAttributes, const Function &Fn, const SmallVectorImpl< Value * > &RetVals, const AliasAttrMap &AMap)
Definition: CFLAndersAliasAnalysis.cpp:490
llvm::dwarf::Index
Index
Definition: Dwarf.h:472
llvm::CFLAndersAAResult::FunctionInfo::getAliasSummary
const AliasSummary & getAliasSummary() const
Definition: CFLAndersAliasAnalysis.cpp:344
INT64_MAX
#define INT64_MAX
Definition: DataTypes.h:71
DebugLocVerifyLevel::None
@ None
llvm::DenseMapInfo< OffsetInstantiatedValue >::getEmptyKey
static OffsetInstantiatedValue getEmptyKey()
Definition: CFLAndersAliasAnalysis.cpp:299
CFLAndersAliasAnalysis.h
hasWriteOnlyState
static bool hasWriteOnlyState(StateSet Set)
Definition: CFLAndersAliasAnalysis.cpp:351
llvm::CFLAndersAAResult::CFLAndersAAResult
CFLAndersAAResult(std::function< const TargetLibraryInfo &(Function &F)> GetTLI)
Definition: CFLAndersAliasAnalysis.cpp:93
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
Type.h
llvm::ValueInfo
Struct that holds a reference to a particular GUID in a global value summary.
Definition: ModuleSummaryIndex.h:169
llvm::dxil::PointerTypeAnalysis::run
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
Definition: PointerTypeAnalysis.cpp:189
initializeWorkList
static void initializeWorkList(std::vector< WorkListItem > &WorkList, ReachabilitySet &ReachSet, const CFLGraph &Graph)
Definition: CFLAndersAliasAnalysis.cpp:606
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1657
INITIALIZE_PASS
INITIALIZE_PASS(CFLAndersAAWrapperPass, "cfl-anders-aa", "Inclusion-Based CFL Alias Analysis", false, true) ImmutablePass *llvm
Definition: CFLAndersAliasAnalysis.cpp:911
llvm::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
llvm::CFLAndersAAWrapperPass::initializePass
void initializePass() override
initializePass - This method may be overriden by immutable passes to allow them to perform various in...
Definition: CFLAndersAliasAnalysis.cpp:922
llvm::AMDGPU::Hwreg::Offset
Offset
Definition: SIDefines.h:416
Index
uint32_t Index
Definition: ELFObjHandler.cpp:83
llvm::TargetLibraryInfoWrapperPass
Definition: TargetLibraryInfo.h:475
uint64_t
llvm::LocationSize::hasValue
bool hasValue() const
Definition: MemoryLocation.h:156
llvm::cflaa::isGlobalOrArgAttr
bool isGlobalOrArgAttr(AliasAttrs Attr)
Definition: AliasAnalysisSummary.cpp:65
llvm::ARM_AM::add
@ add
Definition: ARMAddressingModes.h:39
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::DenseMapInfo< OffsetValue >::isEqual
static bool isEqual(const OffsetValue &LHS, const OffsetValue &RHS)
Definition: CFLAndersAliasAnalysis.cpp:292
MemoryLocation.h
llvm::DenseMap
Definition: DenseMap.h:714
llvm::CFLAndersAAWrapperPass
Legacy wrapper pass to provide the CFLAndersAAResult object.
Definition: CFLAndersAliasAnalysis.h:104
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
llvm::operator<
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:347
llvm::DenseMapInfo< OffsetInstantiatedValue >::getTombstoneKey
static OffsetInstantiatedValue getTombstoneKey()
Definition: CFLAndersAliasAnalysis.cpp:305
I
#define I(x, y, z)
Definition: MD5.cpp:58
propagate
static void propagate(InstantiatedValue From, InstantiatedValue To, MatchState State, ReachabilitySet &ReachSet, std::vector< WorkListItem > &WorkList)
Definition: CFLAndersAliasAnalysis.cpp:597
getInterfaceValue
static std::optional< InterfaceValue > getInterfaceValue(InstantiatedValue IValue, const SmallVectorImpl< Value * > &RetVals)
Definition: CFLAndersAliasAnalysis.cpp:356
llvm::is_contained
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:1843
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1836
llvm::cflaa
Definition: CFLAliasAnalysisUtils.h:23
llvm::operator==
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:2010
llvm::CFLAndersAAResult
Definition: CFLAndersAliasAnalysis.h:38
iterator_range.h
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:82
llvm::Record
Definition: Record.h:1573
CFLGraph.h
llvm::cflaa::UnknownOffset
static const int64_t UnknownOffset
Definition: AliasAnalysisSummary.h:142
None.h
Compiler.h
llvm::ValueMap
See the file comment.
Definition: ValueMap.h:85
llvm::cflaa::CFLGraph::value_mappings
iterator_range< const_value_iterator > value_mappings() const
Definition: CFLGraph.h:149
llvm::DenseMapInfo< OffsetValue >::getHashValue
static unsigned getHashValue(const OffsetValue &OVal)
Definition: CFLAndersAliasAnalysis.cpp:287
llvm::cflaa::parentFunctionOfValue
static const Function * parentFunctionOfValue(const Value *Val)
Definition: CFLAliasAnalysisUtils.h:46
Argument.h
llvm::cflaa::getExternallyVisibleAttrs
AliasAttrs getExternallyVisibleAttrs(AliasAttrs Attr)
Given an AliasAttrs, return a new AliasAttrs that only contains attributes meaningful to the caller.
Definition: AliasAnalysisSummary.cpp:72
std
Definition: BitVector.h:851
llvm::None
constexpr std::nullopt_t None
Definition: None.h:27
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
llvm::cflaa::InstantiatedValue
This is the result of instantiating InterfaceValue at a particular call.
Definition: AliasAnalysisSummary.h:202
llvm::CFLAndersAAResult::~CFLAndersAAResult
~CFLAndersAAResult()
query
static void query(const MachineInstr &MI, bool &Read, bool &Write, bool &Effects, bool &StackPointer)
Definition: WebAssemblyRegStackify.cpp:166
Casting.h
Function.h
PassManager.h
llvm::is_sorted
bool is_sorted(R &&Range, Compare C)
Wrapper function around std::is_sorted to check if elements in a range R are sorted with respect to a...
Definition: STLExtras.h:1858
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:226
llvm::unique
auto unique(Range &&R, Predicate P)
Definition: STLExtras.h:1940
llvm::CFLAndersAAResult::FunctionInfo::mayAlias
bool mayAlias(const Value *, LocationSize, const Value *, LocationSize) const
Definition: CFLAndersAliasAnalysis.cpp:521
SmallVector.h
populateExternalRelations
static void populateExternalRelations(SmallVectorImpl< ExternalRelation > &ExtRelations, const Function &Fn, const SmallVectorImpl< Value * > &RetVals, const ReachabilitySet &ReachSet)
Definition: CFLAndersAliasAnalysis.cpp:405
processWorkListItem
static void processWorkListItem(const WorkListItem &Item, const CFLGraph &Graph, ReachabilitySet &ReachSet, AliasMemSet &MemSet, std::vector< WorkListItem > &WorkList)
Definition: CFLAndersAliasAnalysis.cpp:637
llvm::cflaa::AliasAttrs
std::bitset< NumAliasAttrs > AliasAttrs
These are attributes that an alias analysis can use to mark certain special properties of a given poi...
Definition: AliasAnalysisSummary.h:61
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
llvm::SmallVectorImpl< Value * >
DenseMapInfo.h
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::DenseMapInfo< OffsetInstantiatedValue >::isEqual
static bool isEqual(const OffsetInstantiatedValue &LHS, const OffsetInstantiatedValue &RHS)
Definition: CFLAndersAliasAnalysis.cpp:316
llvm::DenseMapInfo< OffsetValue >::getTombstoneKey
static OffsetValue getTombstoneKey()
Definition: CFLAndersAliasAnalysis.cpp:282
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
hasReadOnlyState
static bool hasReadOnlyState(StateSet Set)
Definition: CFLAndersAliasAnalysis.cpp:347
populateAliasMap
static void populateAliasMap(DenseMap< const Value *, std::vector< OffsetValue >> &AliasMap, const ReachabilitySet &ReachSet)
Definition: CFLAndersAliasAnalysis.cpp:385
LLVM_UNLIKELY
#define LLVM_UNLIKELY(EXPR)
Definition: Compiler.h:210
raw_ostream.h
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::cflaa::ExternalAttribute
We use ExternalAttribute to describe an externally visible AliasAttrs for parameters/return value.
Definition: AliasAnalysisSummary.h:187
Debug.h
llvm::TargetLibraryAnalysis
Analysis pass providing the TargetLibraryInfo.
Definition: TargetLibraryInfo.h:450
llvm::AAResultBase
A base class to help implement the function alias analysis results concept.
Definition: AliasAnalysis.h:785
llvm::MemoryLocation
Representation for a specific memory location.
Definition: MemoryLocation.h:210
llvm::cflaa::hasUnknownOrCallerAttr
bool hasUnknownOrCallerAttr(AliasAttrs Attr)
Definition: AliasAnalysisSummary.cpp:37
getNodeBelow
static std::optional< InstantiatedValue > getNodeBelow(const CFLGraph &Graph, InstantiatedValue V)
Definition: CFLAndersAliasAnalysis.cpp:629