LLVM  14.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 <utility>
85 #include <vector>
86 
87 using namespace llvm;
88 using namespace llvm::cflaa;
89 
90 #define DEBUG_TYPE "cfl-anders-aa"
91 
93  std::function<const TargetLibraryInfo &(Function &F)> GetTLI)
94  : GetTLI(std::move(GetTLI)) {}
96  : AAResultBase(std::move(RHS)), GetTLI(std::move(RHS.GetTLI)) {}
98 
99 namespace {
100 
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
118  // X and Y.
119  FlowToWriteOnly,
120  FlowToReadWrite,
121  // The following two states together represent S4 in the paper.
122  FlowToMemAliasWriteOnly,
123  FlowToMemAliasReadWrite,
124 };
125 
126 using StateSet = std::bitset<7>;
127 
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));
134 
135 // A pair that consists of a value and an offset
136 struct OffsetValue {
137  const Value *Val;
138  int64_t Offset;
139 };
140 
141 bool operator==(OffsetValue LHS, OffsetValue RHS) {
142  return LHS.Val == RHS.Val && LHS.Offset == RHS.Offset;
143 }
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);
147 }
148 
149 // A pair that consists of an InstantiatedValue and an offset
150 struct OffsetInstantiatedValue {
151  InstantiatedValue IVal;
152  int64_t Offset;
153 };
154 
155 bool operator==(OffsetInstantiatedValue LHS, OffsetInstantiatedValue RHS) {
156  return LHS.IVal == RHS.IVal && LHS.Offset == RHS.Offset;
157 }
158 
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>;
164 
165  ValueReachMap ReachMap;
166 
167 public:
168  using const_valuestate_iterator = ValueStateMap::const_iterator;
169  using const_value_iterator = ValueReachMap::const_iterator;
170 
171  // Insert edge 'From->To' at state 'State'
172  bool insert(InstantiatedValue From, InstantiatedValue To, MatchState State) {
173  assert(From != To);
174  auto &States = ReachMap[To][From];
175  auto Idx = static_cast<size_t>(State);
176  if (!States.test(Idx)) {
177  States.set(Idx);
178  return true;
179  }
180  return false;
181  }
182 
183  // Return the set of all ('From', 'State') pair for a given node 'To'
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(),
191  Itr->second.end());
192  }
193 
194  iterator_range<const_value_iterator> value_mappings() const {
195  return make_range<const_value_iterator>(ReachMap.begin(), ReachMap.end());
196  }
197 };
198 
199 // We use AliasMemSet to keep track of all memory aliases (the nonterminal "M"
200 // in the paper) during the analysis.
201 class AliasMemSet {
202  using MemSet = DenseSet<InstantiatedValue>;
203  using MemMapType = DenseMap<InstantiatedValue, MemSet>;
204 
205  MemMapType MemMap;
206 
207 public:
208  using const_mem_iterator = MemSet::const_iterator;
209 
210  bool insert(InstantiatedValue LHS, InstantiatedValue RHS) {
211  // Top-level values can never be memory aliases because one cannot take the
212  // addresses of them
213  assert(LHS.DerefLevel > 0 && RHS.DerefLevel > 0);
214  return MemMap[LHS].insert(RHS).second;
215  }
216 
217  const MemSet *getMemoryAliases(InstantiatedValue V) const {
218  auto Itr = MemMap.find(V);
219  if (Itr == MemMap.end())
220  return nullptr;
221  return &Itr->second;
222  }
223 };
224 
225 // We use AliasAttrMap to keep track of the AliasAttr of each node.
226 class AliasAttrMap {
228 
229  MapType AttrMap;
230 
231 public:
232  using const_iterator = MapType::const_iterator;
233 
234  bool add(InstantiatedValue V, AliasAttrs Attr) {
235  auto &OldAttr = AttrMap[V];
236  auto NewAttr = OldAttr | Attr;
237  if (OldAttr == NewAttr)
238  return false;
239  OldAttr = NewAttr;
240  return true;
241  }
242 
243  AliasAttrs getAttrs(InstantiatedValue V) const {
244  AliasAttrs Attr;
245  auto Itr = AttrMap.find(V);
246  if (Itr != AttrMap.end())
247  Attr = Itr->second;
248  return Attr;
249  }
250 
251  iterator_range<const_iterator> mappings() const {
252  return make_range<const_iterator>(AttrMap.begin(), AttrMap.end());
253  }
254 };
255 
256 struct WorkListItem {
259  MatchState State;
260 };
261 
262 struct ValueSummary {
263  struct Record {
264  InterfaceValue IValue;
265  unsigned DerefLevel;
266  };
267  SmallVector<Record, 4> FromRecords, ToRecords;
268 };
269 
270 } // end anonymous namespace
271 
272 namespace llvm {
273 
274 // Specialize DenseMapInfo for OffsetValue.
275 template <> struct DenseMapInfo<OffsetValue> {
276  static OffsetValue getEmptyKey() {
277  return OffsetValue{DenseMapInfo<const Value *>::getEmptyKey(),
279  }
280 
281  static OffsetValue getTombstoneKey() {
284  }
285 
286  static unsigned getHashValue(const OffsetValue &OVal) {
288  std::make_pair(OVal.Val, OVal.Offset));
289  }
290 
291  static bool isEqual(const OffsetValue &LHS, const OffsetValue &RHS) {
292  return LHS == RHS;
293  }
294 };
295 
296 // Specialize DenseMapInfo for OffsetInstantiatedValue.
297 template <> struct DenseMapInfo<OffsetInstantiatedValue> {
298  static OffsetInstantiatedValue getEmptyKey() {
299  return OffsetInstantiatedValue{
302  }
303 
304  static OffsetInstantiatedValue getTombstoneKey() {
305  return OffsetInstantiatedValue{
308  }
309 
310  static unsigned getHashValue(const OffsetInstantiatedValue &OVal) {
312  std::make_pair(OVal.IVal, OVal.Offset));
313  }
314 
315  static bool isEqual(const OffsetInstantiatedValue &LHS,
316  const OffsetInstantiatedValue &RHS) {
317  return LHS == RHS;
318  }
319 };
320 
321 } // end namespace llvm
322 
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.
329 
330  /// Map a value to its corresponding AliasAttrs
332 
333  /// Summary of externally visible effects.
334  AliasSummary Summary;
335 
336  Optional<AliasAttrs> getAttrs(const Value *) const;
337 
338 public:
340  const ReachabilitySet &, const AliasAttrMap &);
341 
342  bool mayAlias(const Value *, LocationSize, const Value *, LocationSize) const;
343  const AliasSummary &getAliasSummary() const { return Summary; }
344 };
345 
346 static bool hasReadOnlyState(StateSet Set) {
347  return (Set & StateSet(ReadOnlyStateMask)).any();
348 }
349 
350 static bool hasWriteOnlyState(StateSet Set) {
351  return (Set & StateSet(WriteOnlyStateMask)).any();
352 }
353 
356  const SmallVectorImpl<Value *> &RetVals) {
357  auto Val = IValue.Val;
358 
360  if (auto Arg = dyn_cast<Argument>(Val))
361  Index = Arg->getArgNo() + 1;
362  else if (is_contained(RetVals, Val))
363  Index = 0;
364 
365  if (Index)
366  return InterfaceValue{*Index, IValue.DerefLevel};
367  return None;
368 }
369 
371  const AliasAttrMap &AMap) {
372  for (const auto &Mapping : AMap.mappings()) {
373  auto IVal = Mapping.first;
374 
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;
380  }
381 }
382 
383 static void
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)
389  continue;
390 
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});
397  }
398 
399  // Sort AliasList for faster lookup
400  llvm::sort(AliasList);
401  }
402 }
403 
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});
415  }
416  }
417 
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
424  // (I, 1).
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.
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
438  if (*Dst == *Src)
439  continue;
440 
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
444  } else {
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});
453  }
454  }
455  }
456  }
457 
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)
465  continue;
466 
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;
473  else
474  DstLevel += FromLevel - ToLevel;
475 
476  ExtRelations.push_back(ExternalRelation{
477  InterfaceValue{SrcIndex, SrcLevel},
478  InterfaceValue{DstIndex, DstLevel}, UnknownOffset});
479  }
480  }
481  }
482 
483  // Remove duplicates in ExtRelations
484  llvm::sort(ExtRelations);
485  ExtRelations.erase(std::unique(ExtRelations.begin(), ExtRelations.end()),
486  ExtRelations.end());
487 }
488 
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);
495  if (Attr.any())
496  ExtAttributes.push_back(ExternalAttribute{*IVal, Attr});
497  }
498  }
499 }
500 
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);
508 }
509 
511 CFLAndersAAResult::FunctionInfo::getAttrs(const Value *V) const {
512  assert(V != nullptr);
513 
514  auto Itr = AttrMap.find(V);
515  if (Itr != AttrMap.end())
516  return Itr->second;
517  return None;
518 }
519 
521  const Value *LHS, LocationSize MaybeLHSSize, const Value *RHS,
522  LocationSize MaybeRHSSize) const {
523  assert(LHS && RHS);
524 
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
527  // cases.
528  auto MaybeAttrsA = getAttrs(LHS);
529  auto MaybeAttrsB = getAttrs(RHS);
530  if (!MaybeAttrsA || !MaybeAttrsB)
531  return true;
532 
533  // Check AliasAttrs before AliasMap lookup since it's cheaper
534  auto AttrsA = *MaybeAttrsA;
535  auto AttrsB = *MaybeAttrsB;
536  if (hasUnknownOrCallerAttr(AttrsA))
537  return AttrsB.any();
538  if (hasUnknownOrCallerAttr(AttrsB))
539  return AttrsA.any();
540  if (isGlobalOrArgAttr(AttrsA))
541  return isGlobalOrArgAttr(AttrsB);
542  if (isGlobalOrArgAttr(AttrsB))
543  return isGlobalOrArgAttr(AttrsA);
544 
545  // At this point both LHS and RHS should point to locally allocated objects
546 
547  auto Itr = AliasMap.find(LHS);
548  if (Itr != AliasMap.end()) {
549 
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);
553  };
554 #ifdef EXPENSIVE_CHECKS
555  assert(llvm::is_sorted(Itr->second, Comparator));
556 #endif
557  auto RangePair = std::equal_range(Itr->second.begin(), Itr->second.end(),
558  OffsetValue{RHS, 0}, Comparator);
559 
560  if (RangePair.first != RangePair.second) {
561  // Be conservative about unknown sizes
562  if (!MaybeLHSSize.hasValue() || !MaybeRHSSize.hasValue())
563  return true;
564 
565  const uint64_t LHSSize = MaybeLHSSize.getValue();
566  const uint64_t RHSSize = MaybeRHSSize.getValue();
567 
568  for (const auto &OVal : make_range(RangePair)) {
569  // Be conservative about UnknownOffset
570  if (OVal.Offset == UnknownOffset)
571  return true;
572 
573  // We know that LHS aliases (RHS + OVal.Offset) if the control flow
574  // reaches here. The may-alias query essentially becomes integer
575  // range-overlap queries over two ranges [OVal.Offset, OVal.Offset +
576  // LHSSize) and [0, RHSSize).
577 
578  // Try to be conservative on super large offsets
579  if (LLVM_UNLIKELY(LHSSize > INT64_MAX || RHSSize > INT64_MAX))
580  return true;
581 
582  auto LHSStart = OVal.Offset;
583  // FIXME: Do we need to guard against integer overflow?
584  auto LHSEnd = OVal.Offset + static_cast<int64_t>(LHSSize);
585  auto RHSStart = 0;
586  auto RHSEnd = static_cast<int64_t>(RHSSize);
587  if (LHSEnd > RHSStart && LHSStart < RHSEnd)
588  return true;
589  }
590  }
591  }
592 
593  return false;
594 }
595 
597  MatchState State, ReachabilitySet &ReachSet,
598  std::vector<WorkListItem> &WorkList) {
599  if (From == To)
600  return;
601  if (ReachSet.insert(From, To, State))
602  WorkList.push_back(WorkListItem{From, To, State});
603 }
604 
605 static void initializeWorkList(std::vector<WorkListItem> &WorkList,
606  ReachabilitySet &ReachSet,
607  const CFLGraph &Graph) {
608  for (const auto &Mapping : Graph.value_mappings()) {
609  auto Val = Mapping.first;
610  auto &ValueInfo = Mapping.second;
611  assert(ValueInfo.getNumLevels() > 0);
612 
613  // Insert all immediate assignment neighbors to the worklist
614  for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I) {
615  auto Src = InstantiatedValue{Val, I};
616  // If there's an assignment edge from X to Y, it means Y is reachable from
617  // X at S3 and X is reachable from Y at S1
618  for (auto &Edge : ValueInfo.getNodeInfoAtLevel(I).Edges) {
619  propagate(Edge.Other, Src, MatchState::FlowFromReadOnly, ReachSet,
620  WorkList);
621  propagate(Src, Edge.Other, MatchState::FlowToWriteOnly, ReachSet,
622  WorkList);
623  }
624  }
625  }
626 }
627 
629  InstantiatedValue V) {
630  auto NodeBelow = InstantiatedValue{V.Val, V.DerefLevel + 1};
631  if (Graph.getNode(NodeBelow))
632  return NodeBelow;
633  return None;
634 }
635 
636 static void processWorkListItem(const WorkListItem &Item, const CFLGraph &Graph,
637  ReachabilitySet &ReachSet, AliasMemSet &MemSet,
638  std::vector<WorkListItem> &WorkList) {
639  auto FromNode = Item.From;
640  auto ToNode = Item.To;
641 
642  auto NodeInfo = Graph.getNode(ToNode);
643  assert(NodeInfo != nullptr);
644 
645  // TODO: propagate field offsets
646 
647  // FIXME: Here is a neat trick we can do: since both ReachSet and MemSet holds
648  // relations that are symmetric, we could actually cut the storage by half by
649  // sorting FromNode and ToNode before insertion happens.
650 
651  // The newly added value alias pair may potentially generate more memory
652  // alias pairs. Check for them here.
653  auto FromNodeBelow = getNodeBelow(Graph, FromNode);
654  auto ToNodeBelow = getNodeBelow(Graph, ToNode);
655  if (FromNodeBelow && ToNodeBelow &&
656  MemSet.insert(*FromNodeBelow, *ToNodeBelow)) {
657  propagate(*FromNodeBelow, *ToNodeBelow,
658  MatchState::FlowFromMemAliasNoReadWrite, ReachSet, WorkList);
659  for (const auto &Mapping : ReachSet.reachableValueAliases(*FromNodeBelow)) {
660  auto Src = Mapping.first;
661  auto MemAliasPropagate = [&](MatchState FromState, MatchState ToState) {
662  if (Mapping.second.test(static_cast<size_t>(FromState)))
663  propagate(Src, *ToNodeBelow, ToState, ReachSet, WorkList);
664  };
665 
666  MemAliasPropagate(MatchState::FlowFromReadOnly,
667  MatchState::FlowFromMemAliasReadOnly);
668  MemAliasPropagate(MatchState::FlowToWriteOnly,
669  MatchState::FlowToMemAliasWriteOnly);
670  MemAliasPropagate(MatchState::FlowToReadWrite,
671  MatchState::FlowToMemAliasReadWrite);
672  }
673  }
674 
675  // This is the core of the state machine walking algorithm. We expand ReachSet
676  // based on which state we are at (which in turn dictates what edges we
677  // should examine)
678  // From a high-level point of view, the state machine here guarantees two
679  // properties:
680  // - If *X and *Y are memory aliases, then X and Y are value aliases
681  // - If Y is an alias of X, then reverse assignment edges (if there is any)
682  // should precede any assignment edges on the path from X to Y.
683  auto NextAssignState = [&](MatchState State) {
684  for (const auto &AssignEdge : NodeInfo->Edges)
685  propagate(FromNode, AssignEdge.Other, State, ReachSet, WorkList);
686  };
687  auto NextRevAssignState = [&](MatchState State) {
688  for (const auto &RevAssignEdge : NodeInfo->ReverseEdges)
689  propagate(FromNode, RevAssignEdge.Other, State, ReachSet, WorkList);
690  };
691  auto NextMemState = [&](MatchState State) {
692  if (auto AliasSet = MemSet.getMemoryAliases(ToNode)) {
693  for (const auto &MemAlias : *AliasSet)
694  propagate(FromNode, MemAlias, State, ReachSet, WorkList);
695  }
696  };
697 
698  switch (Item.State) {
699  case MatchState::FlowFromReadOnly:
700  NextRevAssignState(MatchState::FlowFromReadOnly);
701  NextAssignState(MatchState::FlowToReadWrite);
702  NextMemState(MatchState::FlowFromMemAliasReadOnly);
703  break;
704 
705  case MatchState::FlowFromMemAliasNoReadWrite:
706  NextRevAssignState(MatchState::FlowFromReadOnly);
707  NextAssignState(MatchState::FlowToWriteOnly);
708  break;
709 
710  case MatchState::FlowFromMemAliasReadOnly:
711  NextRevAssignState(MatchState::FlowFromReadOnly);
712  NextAssignState(MatchState::FlowToReadWrite);
713  break;
714 
715  case MatchState::FlowToWriteOnly:
716  NextAssignState(MatchState::FlowToWriteOnly);
717  NextMemState(MatchState::FlowToMemAliasWriteOnly);
718  break;
719 
720  case MatchState::FlowToReadWrite:
721  NextAssignState(MatchState::FlowToReadWrite);
722  NextMemState(MatchState::FlowToMemAliasReadWrite);
723  break;
724 
725  case MatchState::FlowToMemAliasWriteOnly:
726  NextAssignState(MatchState::FlowToWriteOnly);
727  break;
728 
729  case MatchState::FlowToMemAliasReadWrite:
730  NextAssignState(MatchState::FlowToReadWrite);
731  break;
732  }
733 }
734 
735 static AliasAttrMap buildAttrMap(const CFLGraph &Graph,
736  const ReachabilitySet &ReachSet) {
737  AliasAttrMap AttrMap;
738  std::vector<InstantiatedValue> WorkList, NextList;
739 
740  // Initialize each node with its original AliasAttrs in CFLGraph
741  for (const auto &Mapping : Graph.value_mappings()) {
742  auto Val = Mapping.first;
743  auto &ValueInfo = Mapping.second;
744  for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I) {
745  auto Node = InstantiatedValue{Val, I};
746  AttrMap.add(Node, ValueInfo.getNodeInfoAtLevel(I).Attr);
747  WorkList.push_back(Node);
748  }
749  }
750 
751  while (!WorkList.empty()) {
752  for (const auto &Dst : WorkList) {
753  auto DstAttr = AttrMap.getAttrs(Dst);
754  if (DstAttr.none())
755  continue;
756 
757  // Propagate attr on the same level
758  for (const auto &Mapping : ReachSet.reachableValueAliases(Dst)) {
759  auto Src = Mapping.first;
760  if (AttrMap.add(Src, DstAttr))
761  NextList.push_back(Src);
762  }
763 
764  // Propagate attr to the levels below
765  auto DstBelow = getNodeBelow(Graph, Dst);
766  while (DstBelow) {
767  if (AttrMap.add(*DstBelow, DstAttr)) {
768  NextList.push_back(*DstBelow);
769  break;
770  }
771  DstBelow = getNodeBelow(Graph, *DstBelow);
772  }
773  }
774  WorkList.swap(NextList);
775  NextList.clear();
776  }
777 
778  return AttrMap;
779 }
780 
782 CFLAndersAAResult::buildInfoFrom(const Function &Fn) {
784  *this, GetTLI(const_cast<Function &>(Fn)),
785  // Cast away the constness here due to GraphBuilder's API requirement
786  const_cast<Function &>(Fn));
787  auto &Graph = GraphBuilder.getCFLGraph();
788 
789  ReachabilitySet ReachSet;
790  AliasMemSet MemSet;
791 
792  std::vector<WorkListItem> WorkList, NextList;
793  initializeWorkList(WorkList, ReachSet, Graph);
794  // TODO: make sure we don't stop before the fix point is reached
795  while (!WorkList.empty()) {
796  for (const auto &Item : WorkList)
797  processWorkListItem(Item, Graph, ReachSet, MemSet, NextList);
798 
799  NextList.swap(WorkList);
800  NextList.clear();
801  }
802 
803  // Now that we have all the reachability info, propagate AliasAttrs according
804  // to it
805  auto IValueAttrMap = buildAttrMap(Graph, ReachSet);
806 
807  return FunctionInfo(Fn, GraphBuilder.getReturnValues(), ReachSet,
808  std::move(IValueAttrMap));
809 }
810 
811 void CFLAndersAAResult::scan(const Function &Fn) {
812  auto InsertPair = Cache.insert(std::make_pair(&Fn, Optional<FunctionInfo>()));
813  (void)InsertPair;
814  assert(InsertPair.second &&
815  "Trying to scan a function that has already been cached");
816 
817  // Note that we can't do Cache[Fn] = buildSetsFrom(Fn) here: the function call
818  // may get evaluated after operator[], potentially triggering a DenseMap
819  // resize and invalidating the reference returned by operator[]
820  auto FunInfo = buildInfoFrom(Fn);
821  Cache[&Fn] = std::move(FunInfo);
822  Handles.emplace_front(const_cast<Function *>(&Fn), this);
823 }
824 
825 void CFLAndersAAResult::evict(const Function *Fn) { Cache.erase(Fn); }
826 
828 CFLAndersAAResult::ensureCached(const Function &Fn) {
829  auto Iter = Cache.find(&Fn);
830  if (Iter == Cache.end()) {
831  scan(Fn);
832  Iter = Cache.find(&Fn);
833  assert(Iter != Cache.end());
834  assert(Iter->second.hasValue());
835  }
836  return Iter->second;
837 }
838 
839 const AliasSummary *CFLAndersAAResult::getAliasSummary(const Function &Fn) {
840  auto &FunInfo = ensureCached(Fn);
841  if (FunInfo.hasValue())
842  return &FunInfo->getAliasSummary();
843  else
844  return nullptr;
845 }
846 
848  const MemoryLocation &LocB) {
849  auto *ValA = LocA.Ptr;
850  auto *ValB = LocB.Ptr;
851 
852  if (!ValA->getType()->isPointerTy() || !ValB->getType()->isPointerTy())
853  return AliasResult::NoAlias;
854 
855  auto *Fn = parentFunctionOfValue(ValA);
856  if (!Fn) {
857  Fn = parentFunctionOfValue(ValB);
858  if (!Fn) {
859  // The only times this is known to happen are when globals + InlineAsm are
860  // involved
861  LLVM_DEBUG(
862  dbgs()
863  << "CFLAndersAA: could not extract parent function information.\n");
864  return AliasResult::MayAlias;
865  }
866  } else {
867  assert(!parentFunctionOfValue(ValB) || parentFunctionOfValue(ValB) == Fn);
868  }
869 
870  assert(Fn != nullptr);
871  auto &FunInfo = ensureCached(*Fn);
872 
873  // AliasMap lookup
874  if (FunInfo->mayAlias(ValA, LocA.Size, ValB, LocB.Size))
875  return AliasResult::MayAlias;
876  return AliasResult::NoAlias;
877 }
878 
879 AliasResult CFLAndersAAResult::alias(const MemoryLocation &LocA,
880  const MemoryLocation &LocB,
881  AAQueryInfo &AAQI) {
882  if (LocA.Ptr == LocB.Ptr)
883  return AliasResult::MustAlias;
884 
885  // Comparisons between global variables and other constants should be
886  // handled by BasicAA.
887  // CFLAndersAA may report NoAlias when comparing a GlobalValue and
888  // ConstantExpr, but every query needs to have at least one Value tied to a
889  // Function, and neither GlobalValues nor ConstantExprs are.
890  if (isa<Constant>(LocA.Ptr) && isa<Constant>(LocB.Ptr))
891  return AAResultBase::alias(LocA, LocB, AAQI);
892 
893  AliasResult QueryResult = query(LocA, LocB);
894  if (QueryResult == AliasResult::MayAlias)
895  return AAResultBase::alias(LocA, LocB, AAQI);
896 
897  return QueryResult;
898 }
899 
901 
903  auto GetTLI = [&AM](Function &F) -> TargetLibraryInfo & {
904  return AM.getResult<TargetLibraryAnalysis>(F);
905  };
906  return CFLAndersAAResult(GetTLI);
907 }
908 
911  "Inclusion-Based CFL Alias Analysis", false, true)
912 
914  return new CFLAndersAAWrapperPass();
915 }
916 
917 CFLAndersAAWrapperPass::CFLAndersAAWrapperPass() : ImmutablePass(ID) {
919 }
920 
922  auto GetTLI = [this](Function &F) -> TargetLibraryInfo & {
923  return this->getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
924  };
925  Result.reset(new CFLAndersAAResult(GetTLI));
926 }
927 
929  AU.setPreservesAll();
931 }
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:928
scan
static Expected< BitVector > scan(StringRef &S, StringRef Original)
Definition: GlobPattern.cpp:67
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::SmallVectorImpl::erase
iterator erase(const_iterator CI)
Definition: SmallVector.h:705
llvm::Function::args
iterator_range< arg_iterator > args()
Definition: Function.h:772
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:276
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:269
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:779
llvm::MemoryLocation::Ptr
const Value * Ptr
The address of the start of the location.
Definition: MemoryLocation.h:217
llvm::Function
Definition: Function.h:61
buildAttrMap
static AliasAttrMap buildAttrMap(const CFLGraph &Graph, const ReachabilitySet &ReachSet)
Definition: CFLAndersAliasAnalysis.cpp:735
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:1168
llvm::DenseMapInfo< OffsetInstantiatedValue >::getHashValue
static unsigned getHashValue(const OffsetInstantiatedValue &OVal)
Definition: CFLAndersAliasAnalysis.cpp:310
AliasAnalysisSummary.h
llvm::AliasSummary
Alias summary information.
Definition: ModuleSummaryIndex.h:449
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:226
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:82
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
STLExtras.h
getInterfaceValue
static Optional< InterfaceValue > getInterfaceValue(InstantiatedValue IValue, const SmallVectorImpl< Value * > &RetVals)
Definition: CFLAndersAliasAnalysis.cpp:355
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:56
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:206
llvm::AAQueryInfo
This class stores info we want to provide to or retain within an alias query.
Definition: AliasAnalysis.h:459
llvm::DenseMapInfo
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:31
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::LocationSize
Definition: MemoryLocation.h:65
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::CFLAndersAAResult::FunctionInfo
Definition: CFLAndersAliasAnalysis.cpp:323
llvm::LocationSize::getValue
uint64_t getValue() const
Definition: MemoryLocation.h:158
llvm::CFLAndersAAResult::FunctionInfo::FunctionInfo
FunctionInfo(const Function &, const SmallVectorImpl< Value * > &, const ReachabilitySet &, const AliasAttrMap &)
Definition: CFLAndersAliasAnalysis.cpp:501
llvm::AliasSet
Definition: AliasSetTracker.h:49
llvm::AMDGPU::PALMD::Key
Key
PAL metadata keys.
Definition: AMDGPUMetadata.h:481
populateAttrMap
static void populateAttrMap(DenseMap< const Value *, AliasAttrs > &AttrMap, const AliasAttrMap &AMap)
Definition: CFLAndersAliasAnalysis.cpp:370
DenseSet.h
populateExternalAttributes
static void populateExternalAttributes(SmallVectorImpl< ExternalAttribute > &ExtAttributes, const Function &Fn, const SmallVectorImpl< Value * > &RetVals, const AliasAttrMap &AMap)
Definition: CFLAndersAliasAnalysis.cpp:489
llvm::CFLAndersAAResult::FunctionInfo::getAliasSummary
const AliasSummary & getAliasSummary() const
Definition: CFLAndersAliasAnalysis.cpp:343
INT64_MAX
#define INT64_MAX
Definition: DataTypes.h:71
DebugLocVerifyLevel::None
@ None
llvm::DenseMapInfo< OffsetInstantiatedValue >::getEmptyKey
static OffsetInstantiatedValue getEmptyKey()
Definition: CFLAndersAliasAnalysis.cpp:298
CFLAndersAliasAnalysis.h
hasWriteOnlyState
static bool hasWriteOnlyState(StateSet Set)
Definition: CFLAndersAliasAnalysis.cpp:350
llvm::CFLAndersAAResult::CFLAndersAAResult
CFLAndersAAResult(std::function< const TargetLibraryInfo &(Function &F)> GetTLI)
Definition: CFLAndersAliasAnalysis.cpp:92
llvm::None
const NoneType None
Definition: None.h:23
Type.h
llvm::ValueInfo
Struct that holds a reference to a particular GUID in a global value summary.
Definition: ModuleSummaryIndex.h:168
initializeWorkList
static void initializeWorkList(std::vector< WorkListItem > &WorkList, ReachabilitySet &ReachSet, const CFLGraph &Graph)
Definition: CFLAndersAliasAnalysis.cpp:605
INITIALIZE_PASS
INITIALIZE_PASS(CFLAndersAAWrapperPass, "cfl-anders-aa", "Inclusion-Based CFL Alias Analysis", false, true) ImmutablePass *llvm
Definition: CFLAndersAliasAnalysis.cpp:910
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:921
query
static void query(const MachineInstr &MI, AliasAnalysis &AA, bool &Read, bool &Write, bool &Effects, bool &StackPointer)
Definition: WebAssemblyRegStackify.cpp:167
Index
uint32_t Index
Definition: ELFObjHandler.cpp:84
llvm::TargetLibraryInfoWrapperPass
Definition: TargetLibraryInfo.h:463
uint64_t
llvm::LocationSize::hasValue
bool hasValue() const
Definition: MemoryLocation.h:155
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:291
MemoryLocation.h
llvm::DenseMap
Definition: DenseMap.h:714
llvm::CFLAndersAAWrapperPass
Legacy wrapper pass to provide the CFLAndersAAResult object.
Definition: CFLAndersAliasAnalysis.h:106
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:72
llvm::operator<
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:338
llvm::DenseMapInfo< OffsetInstantiatedValue >::getTombstoneKey
static OffsetInstantiatedValue getTombstoneKey()
Definition: CFLAndersAliasAnalysis.cpp:304
I
#define I(x, y, z)
Definition: MD5.cpp:59
propagate
static void propagate(InstantiatedValue From, InstantiatedValue To, MatchState State, ReachabilitySet &ReachSet, std::vector< WorkListItem > &WorkList)
Definition: CFLAndersAliasAnalysis.cpp:596
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:1616
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:1609
llvm::cflaa
Definition: CFLAliasAnalysisUtils.h:21
llvm::operator==
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1974
llvm::CFLAndersAAResult
Definition: CFLAndersAliasAnalysis.h:38
iterator_range.h
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:83
llvm::Record
Definition: Record.h:1472
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:286
llvm::cflaa::parentFunctionOfValue
static const Function * parentFunctionOfValue(const Value *Val)
Definition: CFLAliasAnalysisUtils.h:44
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:838
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()
Casting.h
Function.h
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1492
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:1622
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:219
llvm::unique
auto unique(Range &&R, Predicate P)
Definition: STLExtras.h:1704
llvm::CFLAndersAAResult::FunctionInfo::mayAlias
bool mayAlias(const Value *, LocationSize, const Value *, LocationSize) const
Definition: CFLAndersAliasAnalysis.cpp:520
SmallVector.h
populateExternalRelations
static void populateExternalRelations(SmallVectorImpl< ExternalRelation > &ExtRelations, const Function &Fn, const SmallVectorImpl< Value * > &RetVals, const ReachabilitySet &ReachSet)
Definition: CFLAndersAliasAnalysis.cpp:404
processWorkListItem
static void processWorkListItem(const WorkListItem &Item, const CFLGraph &Graph, ReachabilitySet &ReachSet, AliasMemSet &MemSet, std::vector< WorkListItem > &WorkList)
Definition: CFLAndersAliasAnalysis.cpp:636
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 * >
getNodeBelow
static Optional< InstantiatedValue > getNodeBelow(const CFLGraph &Graph, InstantiatedValue V)
Definition: CFLAndersAliasAnalysis.cpp:628
DenseMapInfo.h
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
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:315
llvm::DenseMapInfo< OffsetValue >::getTombstoneKey
static OffsetValue getTombstoneKey()
Definition: CFLAndersAliasAnalysis.cpp:281
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
hasReadOnlyState
static bool hasReadOnlyState(StateSet Set)
Definition: CFLAndersAliasAnalysis.cpp:346
populateAliasMap
static void populateAliasMap(DenseMap< const Value *, std::vector< OffsetValue >> &AliasMap, const ReachabilitySet &ReachSet)
Definition: CFLAndersAliasAnalysis.cpp:384
LLVM_UNLIKELY
#define LLVM_UNLIKELY(EXPR)
Definition: Compiler.h:220
raw_ostream.h
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
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:438
llvm::AAResultBase
A CRTP-driven "mixin" base class to help implement the function alias analysis results concept.
Definition: AliasAnalysis.h:1131
llvm::MemoryLocation
Representation for a specific memory location.
Definition: MemoryLocation.h:209
llvm::cflaa::hasUnknownOrCallerAttr
bool hasUnknownOrCallerAttr(AliasAttrs Attr)
Definition: AliasAnalysisSummary.cpp:37
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37