LLVM  10.0.0svn
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/Pass.h"
73 #include "llvm/Support/Casting.h"
74 #include "llvm/Support/Compiler.h"
75 #include "llvm/Support/Debug.h"
77 #include <algorithm>
78 #include <bitset>
79 #include <cassert>
80 #include <cstddef>
81 #include <cstdint>
82 #include <functional>
83 #include <utility>
84 #include <vector>
85 
86 using namespace llvm;
87 using namespace llvm::cflaa;
88 
89 #define DEBUG_TYPE "cfl-anders-aa"
90 
92  std::function<const TargetLibraryInfo &(Function &F)> GetTLI)
93  : GetTLI(std::move(GetTLI)) {}
95  : AAResultBase(std::move(RHS)), GetTLI(std::move(RHS.GetTLI)) {}
97 
98 namespace {
99 
100 enum class MatchState : uint8_t {
101  // The following state represents S1 in the paper.
102  FlowFromReadOnly = 0,
103  // The following two states together represent S2 in the paper.
104  // The 'NoReadWrite' suffix indicates that there exists an alias path that
105  // does not contain assignment and reverse assignment edges.
106  // The 'ReadOnly' suffix indicates that there exists an alias path that
107  // contains reverse assignment edges only.
108  FlowFromMemAliasNoReadWrite,
109  FlowFromMemAliasReadOnly,
110  // The following two states together represent S3 in the paper.
111  // The 'WriteOnly' suffix indicates that there exists an alias path that
112  // contains assignment edges only.
113  // The 'ReadWrite' suffix indicates that there exists an alias path that
114  // contains both assignment and reverse assignment edges. Note that if X and Y
115  // are reachable at 'ReadWrite' state, it does NOT mean X is both read from
116  // and written to Y. Instead, it means that a third value Z is written to both
117  // X and Y.
118  FlowToWriteOnly,
119  FlowToReadWrite,
120  // The following two states together represent S4 in the paper.
121  FlowToMemAliasWriteOnly,
122  FlowToMemAliasReadWrite,
123 };
124 
125 using StateSet = std::bitset<7>;
126 
127 const unsigned ReadOnlyStateMask =
128  (1U << static_cast<uint8_t>(MatchState::FlowFromReadOnly)) |
129  (1U << static_cast<uint8_t>(MatchState::FlowFromMemAliasReadOnly));
130 const unsigned WriteOnlyStateMask =
131  (1U << static_cast<uint8_t>(MatchState::FlowToWriteOnly)) |
132  (1U << static_cast<uint8_t>(MatchState::FlowToMemAliasWriteOnly));
133 
134 // A pair that consists of a value and an offset
135 struct OffsetValue {
136  const Value *Val;
137  int64_t Offset;
138 };
139 
140 bool operator==(OffsetValue LHS, OffsetValue RHS) {
141  return LHS.Val == RHS.Val && LHS.Offset == RHS.Offset;
142 }
143 bool operator<(OffsetValue LHS, OffsetValue RHS) {
144  return std::less<const Value *>()(LHS.Val, RHS.Val) ||
145  (LHS.Val == RHS.Val && LHS.Offset < RHS.Offset);
146 }
147 
148 // A pair that consists of an InstantiatedValue and an offset
149 struct OffsetInstantiatedValue {
150  InstantiatedValue IVal;
151  int64_t Offset;
152 };
153 
154 bool operator==(OffsetInstantiatedValue LHS, OffsetInstantiatedValue RHS) {
155  return LHS.IVal == RHS.IVal && LHS.Offset == RHS.Offset;
156 }
157 
158 // We use ReachabilitySet to keep track of value aliases (The nonterminal "V" in
159 // the paper) during the analysis.
160 class ReachabilitySet {
161  using ValueStateMap = DenseMap<InstantiatedValue, StateSet>;
162  using ValueReachMap = DenseMap<InstantiatedValue, ValueStateMap>;
163 
164  ValueReachMap ReachMap;
165 
166 public:
167  using const_valuestate_iterator = ValueStateMap::const_iterator;
168  using const_value_iterator = ValueReachMap::const_iterator;
169 
170  // Insert edge 'From->To' at state 'State'
171  bool insert(InstantiatedValue From, InstantiatedValue To, MatchState State) {
172  assert(From != To);
173  auto &States = ReachMap[To][From];
174  auto Idx = static_cast<size_t>(State);
175  if (!States.test(Idx)) {
176  States.set(Idx);
177  return true;
178  }
179  return false;
180  }
181 
182  // Return the set of all ('From', 'State') pair for a given node 'To'
184  reachableValueAliases(InstantiatedValue V) const {
185  auto Itr = ReachMap.find(V);
186  if (Itr == ReachMap.end())
187  return make_range<const_valuestate_iterator>(const_valuestate_iterator(),
188  const_valuestate_iterator());
189  return make_range<const_valuestate_iterator>(Itr->second.begin(),
190  Itr->second.end());
191  }
192 
193  iterator_range<const_value_iterator> value_mappings() const {
194  return make_range<const_value_iterator>(ReachMap.begin(), ReachMap.end());
195  }
196 };
197 
198 // We use AliasMemSet to keep track of all memory aliases (the nonterminal "M"
199 // in the paper) during the analysis.
200 class AliasMemSet {
201  using MemSet = DenseSet<InstantiatedValue>;
202  using MemMapType = DenseMap<InstantiatedValue, MemSet>;
203 
204  MemMapType MemMap;
205 
206 public:
207  using const_mem_iterator = MemSet::const_iterator;
208 
209  bool insert(InstantiatedValue LHS, InstantiatedValue RHS) {
210  // Top-level values can never be memory aliases because one cannot take the
211  // addresses of them
212  assert(LHS.DerefLevel > 0 && RHS.DerefLevel > 0);
213  return MemMap[LHS].insert(RHS).second;
214  }
215 
216  const MemSet *getMemoryAliases(InstantiatedValue V) const {
217  auto Itr = MemMap.find(V);
218  if (Itr == MemMap.end())
219  return nullptr;
220  return &Itr->second;
221  }
222 };
223 
224 // We use AliasAttrMap to keep track of the AliasAttr of each node.
225 class AliasAttrMap {
227 
228  MapType AttrMap;
229 
230 public:
231  using const_iterator = MapType::const_iterator;
232 
233  bool add(InstantiatedValue V, AliasAttrs Attr) {
234  auto &OldAttr = AttrMap[V];
235  auto NewAttr = OldAttr | Attr;
236  if (OldAttr == NewAttr)
237  return false;
238  OldAttr = NewAttr;
239  return true;
240  }
241 
242  AliasAttrs getAttrs(InstantiatedValue V) const {
243  AliasAttrs Attr;
244  auto Itr = AttrMap.find(V);
245  if (Itr != AttrMap.end())
246  Attr = Itr->second;
247  return Attr;
248  }
249 
250  iterator_range<const_iterator> mappings() const {
251  return make_range<const_iterator>(AttrMap.begin(), AttrMap.end());
252  }
253 };
254 
255 struct WorkListItem {
258  MatchState State;
259 };
260 
261 struct ValueSummary {
262  struct Record {
263  InterfaceValue IValue;
264  unsigned DerefLevel;
265  };
266  SmallVector<Record, 4> FromRecords, ToRecords;
267 };
268 
269 } // end anonymous namespace
270 
271 namespace llvm {
272 
273 // Specialize DenseMapInfo for OffsetValue.
274 template <> struct DenseMapInfo<OffsetValue> {
275  static OffsetValue getEmptyKey() {
276  return OffsetValue{DenseMapInfo<const Value *>::getEmptyKey(),
278  }
279 
280  static OffsetValue getTombstoneKey() {
283  }
284 
285  static unsigned getHashValue(const OffsetValue &OVal) {
287  std::make_pair(OVal.Val, OVal.Offset));
288  }
289 
290  static bool isEqual(const OffsetValue &LHS, const OffsetValue &RHS) {
291  return LHS == RHS;
292  }
293 };
294 
295 // Specialize DenseMapInfo for OffsetInstantiatedValue.
296 template <> struct DenseMapInfo<OffsetInstantiatedValue> {
297  static OffsetInstantiatedValue getEmptyKey() {
298  return OffsetInstantiatedValue{
301  }
302 
303  static OffsetInstantiatedValue getTombstoneKey() {
304  return OffsetInstantiatedValue{
307  }
308 
309  static unsigned getHashValue(const OffsetInstantiatedValue &OVal) {
311  std::make_pair(OVal.IVal, OVal.Offset));
312  }
313 
314  static bool isEqual(const OffsetInstantiatedValue &LHS,
315  const OffsetInstantiatedValue &RHS) {
316  return LHS == RHS;
317  }
318 };
319 
320 } // end namespace llvm
321 
323  /// Map a value to other values that may alias it
324  /// Since the alias relation is symmetric, to save some space we assume values
325  /// are properly ordered: if a and b alias each other, and a < b, then b is in
326  /// AliasMap[a] but not vice versa.
328 
329  /// Map a value to its corresponding AliasAttrs
331 
332  /// Summary of externally visible effects.
333  AliasSummary Summary;
334 
335  Optional<AliasAttrs> getAttrs(const Value *) const;
336 
337 public:
339  const ReachabilitySet &, const AliasAttrMap &);
340 
341  bool mayAlias(const Value *, LocationSize, const Value *, LocationSize) const;
342  const AliasSummary &getAliasSummary() const { return Summary; }
343 };
344 
345 static bool hasReadOnlyState(StateSet Set) {
346  return (Set & StateSet(ReadOnlyStateMask)).any();
347 }
348 
349 static bool hasWriteOnlyState(StateSet Set) {
350  return (Set & StateSet(WriteOnlyStateMask)).any();
351 }
352 
355  const SmallVectorImpl<Value *> &RetVals) {
356  auto Val = IValue.Val;
357 
359  if (auto Arg = dyn_cast<Argument>(Val))
360  Index = Arg->getArgNo() + 1;
361  else if (is_contained(RetVals, Val))
362  Index = 0;
363 
364  if (Index)
365  return InterfaceValue{*Index, IValue.DerefLevel};
366  return None;
367 }
368 
370  const AliasAttrMap &AMap) {
371  for (const auto &Mapping : AMap.mappings()) {
372  auto IVal = Mapping.first;
373 
374  // Insert IVal into the map
375  auto &Attr = AttrMap[IVal.Val];
376  // AttrMap only cares about top-level values
377  if (IVal.DerefLevel == 0)
378  Attr |= Mapping.second;
379  }
380 }
381 
382 static void
383 populateAliasMap(DenseMap<const Value *, std::vector<OffsetValue>> &AliasMap,
384  const ReachabilitySet &ReachSet) {
385  for (const auto &OuterMapping : ReachSet.value_mappings()) {
386  // AliasMap only cares about top-level values
387  if (OuterMapping.first.DerefLevel > 0)
388  continue;
389 
390  auto Val = OuterMapping.first.Val;
391  auto &AliasList = AliasMap[Val];
392  for (const auto &InnerMapping : OuterMapping.second) {
393  // Again, AliasMap only cares about top-level values
394  if (InnerMapping.first.DerefLevel == 0)
395  AliasList.push_back(OffsetValue{InnerMapping.first.Val, UnknownOffset});
396  }
397 
398  // Sort AliasList for faster lookup
399  llvm::sort(AliasList);
400  }
401 }
402 
404  SmallVectorImpl<ExternalRelation> &ExtRelations, const Function &Fn,
405  const SmallVectorImpl<Value *> &RetVals, const ReachabilitySet &ReachSet) {
406  // If a function only returns one of its argument X, then X will be both an
407  // argument and a return value at the same time. This is an edge case that
408  // needs special handling here.
409  for (const auto &Arg : Fn.args()) {
410  if (is_contained(RetVals, &Arg)) {
411  auto ArgVal = InterfaceValue{Arg.getArgNo() + 1, 0};
412  auto RetVal = InterfaceValue{0, 0};
413  ExtRelations.push_back(ExternalRelation{ArgVal, RetVal, 0});
414  }
415  }
416 
417  // Below is the core summary construction logic.
418  // A naive solution of adding only the value aliases that are parameters or
419  // return values in ReachSet to the summary won't work: It is possible that a
420  // parameter P is written into an intermediate value I, and the function
421  // subsequently returns *I. In that case, *I is does not value alias anything
422  // in ReachSet, and the naive solution will miss a summary edge from (P, 1) to
423  // (I, 1).
424  // To account for the aforementioned case, we need to check each non-parameter
425  // and non-return value for the possibility of acting as an intermediate.
426  // 'ValueMap' here records, for each value, which InterfaceValues read from or
427  // write into it. If both the read list and the write list of a given value
428  // are non-empty, we know that a particular value is an intermidate and we
429  // need to add summary edges from the writes to the reads.
431  for (const auto &OuterMapping : ReachSet.value_mappings()) {
432  if (auto Dst = getInterfaceValue(OuterMapping.first, RetVals)) {
433  for (const auto &InnerMapping : OuterMapping.second) {
434  // If Src is a param/return value, we get a same-level assignment.
435  if (auto Src = getInterfaceValue(InnerMapping.first, RetVals)) {
436  // This may happen if both Dst and Src are return values
437  if (*Dst == *Src)
438  continue;
439 
440  if (hasReadOnlyState(InnerMapping.second))
441  ExtRelations.push_back(ExternalRelation{*Dst, *Src, UnknownOffset});
442  // No need to check for WriteOnly state, since ReachSet is symmetric
443  } else {
444  // If Src is not a param/return, add it to ValueMap
445  auto SrcIVal = InnerMapping.first;
446  if (hasReadOnlyState(InnerMapping.second))
447  ValueMap[SrcIVal.Val].FromRecords.push_back(
448  ValueSummary::Record{*Dst, SrcIVal.DerefLevel});
449  if (hasWriteOnlyState(InnerMapping.second))
450  ValueMap[SrcIVal.Val].ToRecords.push_back(
451  ValueSummary::Record{*Dst, SrcIVal.DerefLevel});
452  }
453  }
454  }
455  }
456 
457  for (const auto &Mapping : ValueMap) {
458  for (const auto &FromRecord : Mapping.second.FromRecords) {
459  for (const auto &ToRecord : Mapping.second.ToRecords) {
460  auto ToLevel = ToRecord.DerefLevel;
461  auto FromLevel = FromRecord.DerefLevel;
462  // Same-level assignments should have already been processed by now
463  if (ToLevel == FromLevel)
464  continue;
465 
466  auto SrcIndex = FromRecord.IValue.Index;
467  auto SrcLevel = FromRecord.IValue.DerefLevel;
468  auto DstIndex = ToRecord.IValue.Index;
469  auto DstLevel = ToRecord.IValue.DerefLevel;
470  if (ToLevel > FromLevel)
471  SrcLevel += ToLevel - FromLevel;
472  else
473  DstLevel += FromLevel - ToLevel;
474 
475  ExtRelations.push_back(ExternalRelation{
476  InterfaceValue{SrcIndex, SrcLevel},
477  InterfaceValue{DstIndex, DstLevel}, UnknownOffset});
478  }
479  }
480  }
481 
482  // Remove duplicates in ExtRelations
483  llvm::sort(ExtRelations);
484  ExtRelations.erase(std::unique(ExtRelations.begin(), ExtRelations.end()),
485  ExtRelations.end());
486 }
487 
489  SmallVectorImpl<ExternalAttribute> &ExtAttributes, const Function &Fn,
490  const SmallVectorImpl<Value *> &RetVals, const AliasAttrMap &AMap) {
491  for (const auto &Mapping : AMap.mappings()) {
492  if (auto IVal = getInterfaceValue(Mapping.first, RetVals)) {
493  auto Attr = getExternallyVisibleAttrs(Mapping.second);
494  if (Attr.any())
495  ExtAttributes.push_back(ExternalAttribute{*IVal, Attr});
496  }
497  }
498 }
499 
501  const Function &Fn, const SmallVectorImpl<Value *> &RetVals,
502  const ReachabilitySet &ReachSet, const AliasAttrMap &AMap) {
503  populateAttrMap(AttrMap, AMap);
504  populateExternalAttributes(Summary.RetParamAttributes, Fn, RetVals, AMap);
505  populateAliasMap(AliasMap, ReachSet);
506  populateExternalRelations(Summary.RetParamRelations, Fn, RetVals, ReachSet);
507 }
508 
510 CFLAndersAAResult::FunctionInfo::getAttrs(const Value *V) const {
511  assert(V != nullptr);
512 
513  auto Itr = AttrMap.find(V);
514  if (Itr != AttrMap.end())
515  return Itr->second;
516  return None;
517 }
518 
520  const Value *LHS, LocationSize MaybeLHSSize, const Value *RHS,
521  LocationSize MaybeRHSSize) const {
522  assert(LHS && RHS);
523 
524  // Check if we've seen LHS and RHS before. Sometimes LHS or RHS can be created
525  // after the analysis gets executed, and we want to be conservative in those
526  // cases.
527  auto MaybeAttrsA = getAttrs(LHS);
528  auto MaybeAttrsB = getAttrs(RHS);
529  if (!MaybeAttrsA || !MaybeAttrsB)
530  return true;
531 
532  // Check AliasAttrs before AliasMap lookup since it's cheaper
533  auto AttrsA = *MaybeAttrsA;
534  auto AttrsB = *MaybeAttrsB;
535  if (hasUnknownOrCallerAttr(AttrsA))
536  return AttrsB.any();
537  if (hasUnknownOrCallerAttr(AttrsB))
538  return AttrsA.any();
539  if (isGlobalOrArgAttr(AttrsA))
540  return isGlobalOrArgAttr(AttrsB);
541  if (isGlobalOrArgAttr(AttrsB))
542  return isGlobalOrArgAttr(AttrsA);
543 
544  // At this point both LHS and RHS should point to locally allocated objects
545 
546  auto Itr = AliasMap.find(LHS);
547  if (Itr != AliasMap.end()) {
548 
549  // Find out all (X, Offset) where X == RHS
550  auto Comparator = [](OffsetValue LHS, OffsetValue RHS) {
551  return std::less<const Value *>()(LHS.Val, RHS.Val);
552  };
553 #ifdef EXPENSIVE_CHECKS
554  assert(std::is_sorted(Itr->second.begin(), Itr->second.end(), Comparator));
555 #endif
556  auto RangePair = std::equal_range(Itr->second.begin(), Itr->second.end(),
557  OffsetValue{RHS, 0}, Comparator);
558 
559  if (RangePair.first != RangePair.second) {
560  // Be conservative about unknown sizes
561  if (MaybeLHSSize == LocationSize::unknown() ||
562  MaybeRHSSize == LocationSize::unknown())
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 
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 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 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 MayAlias;
876  return NoAlias;
877 }
878 
880  const MemoryLocation &LocB,
881  AAQueryInfo &AAQI) {
882  if (LocA.Ptr == LocB.Ptr)
883  return 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 == MayAlias)
895  return AAResultBase::alias(LocA, LocB, AAQI);
896 
897  return QueryResult;
898 }
899 
900 AnalysisKey CFLAndersAA::Key;
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 
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 }
static void populateExternalAttributes(SmallVectorImpl< ExternalAttribute > &ExtAttributes, const Function &Fn, const SmallVectorImpl< Value *> &RetVals, const AliasAttrMap &AMap)
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
void evict(const Function *Fn)
Evict the given function from cache.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:776
This is the interface for LLVM&#39;s inclusion-based alias analysis implemented with CFL graph reachabili...
This class represents lattice values for constants.
Definition: AllocatorList.h:23
We use ExternalRelation to describe an externally visible aliasing relations between parameters/retur...
static void populateAliasMap(DenseMap< const Value *, std::vector< OffsetValue >> &AliasMap, const ReachabilitySet &ReachSet)
static bool mayAlias(MachineInstr &MIa, MachineInstr &MIb, AliasAnalysis *AA)
#define LLVM_UNLIKELY(EXPR)
Definition: Compiler.h:204
static constexpr LocationSize unknown()
Implements a dense probed hash-table based set.
Definition: DenseSet.h:249
This is the result of instantiating InterfaceValue at a particular call.
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
void initializeCFLAndersAAWrapperPassPass(PassRegistry &)
This class stores info we want to provide to or retain within an alias query.
void initializePass() override
initializePass - This method may be overriden by immutable passes to allow them to perform various in...
The Program Expression Graph (PEG) of CFL analysis CFLGraph is auxiliary data structure used by CFL-b...
Definition: CFLGraph.h:57
The two locations do not alias at all.
Definition: AliasAnalysis.h:84
F(f)
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI)
static void populateAttrMap(DenseMap< const Value *, AliasAttrs > &AttrMap, const AliasAttrMap &AMap)
We use ExternalAttribute to describe an externally visible AliasAttrs for parameters/return value...
We use InterfaceValue to describe parameters/return value, as well as potential memory locations that...
AliasResult alias(const MemoryLocation &, const MemoryLocation &, AAQueryInfo &)
AnalysisUsage & addRequired()
Definition: BitVector.h:937
CFLAndersAAResult(std::function< const TargetLibraryInfo &(Function &F)> GetTLI)
static AliasAttrMap buildAttrMap(const CFLGraph &Graph, const ReachabilitySet &ReachSet)
FunctionInfo(const Function &, const SmallVectorImpl< Value *> &, const ReachabilitySet &, const AliasAttrMap &)
static bool isEqual(const OffsetValue &LHS, const OffsetValue &RHS)
#define INT64_MAX
Definition: DataTypes.h:77
const cflaa::AliasSummary * getAliasSummary(const Function &)
Get the alias summary for the given function Return nullptr if the summary is not found or not availa...
A CRTP-driven "mixin" base class to help implement the function alias analysis results concept...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
static bool isEqual(const OffsetInstantiatedValue &LHS, const OffsetInstantiatedValue &RHS)
AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:78
uint64_t getValue() const
static unsigned getHashValue(const OffsetInstantiatedValue &OVal)
AliasResult query(const MemoryLocation &, const MemoryLocation &)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static bool hasWriteOnlyState(StateSet Set)
Legacy wrapper pass to provide the CFLAndersAAResult object.
static void populateExternalRelations(SmallVectorImpl< ExternalRelation > &ExtRelations, const Function &Fn, const SmallVectorImpl< Value *> &RetVals, const ReachabilitySet &ReachSet)
Represent the analysis usage information of a pass.
LocationSize Size
The maximum size of the location, in address-units, or UnknownSize if the size is not known...
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
const SmallVector< Value *, 4 > & getReturnValues() const
Definition: CFLGraph.h:652
bool isGlobalOrArgAttr(AliasAttrs Attr)
iterator erase(const_iterator CI)
Definition: SmallVector.h:434
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1095
Struct that holds a reference to a particular GUID in a global value summary.
The two locations may or may not alias. This is the least precise result.
Definition: AliasAnalysis.h:86
const Value * Ptr
The address of the start of the location.
Representation for a specific memory location.
The two locations precisely alias each other.
Definition: AliasAnalysis.h:90
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
See the file comment.
Definition: ValueMap.h:85
ImmutablePass class - This class is used to provide information that does not need to be run...
Definition: Pass.h:255
BlockVerifier::State From
static void initializeWorkList(std::vector< WorkListItem > &WorkList, ReachabilitySet &ReachSet, const CFLGraph &Graph)
INITIALIZE_PASS(CFLAndersAAWrapperPass, "cfl-anders-aa", "Inclusion-Based CFL Alias Analysis", false, true) ImmutablePass *llvm
AliasAttrs getExternallyVisibleAttrs(AliasAttrs Attr)
Given an AliasAttrs, return a new AliasAttrs that only contains attributes meaningful to the caller...
static uint64_t add(uint64_t LeftOp, uint64_t RightOp)
Definition: FileCheck.cpp:214
A builder class used to create CFLGraph instance from a given function The CFL-AA that uses this buil...
Definition: CFLGraph.h:163
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
Provides information about what library functions are available for the current target.
iterator_range< const_value_iterator > value_mappings() const
Definition: CFLGraph.h:149
Alias summary information.
This file defines various utility types and functions useful to summary-based alias analysis...
static Optional< InterfaceValue > getInterfaceValue(InstantiatedValue IValue, const SmallVectorImpl< Value *> &RetVals)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
A range adaptor for a pair of iterators.
void setPreservesAll()
Set by analyses that do not transform their input at all.
This file defines CFLGraph, an auxiliary data structure used by CFL-based alias analysis.
static void propagate(InstantiatedValue From, InstantiatedValue To, MatchState State, ReachabilitySet &ReachSet, std::vector< WorkListItem > &WorkList)
static const int64_t UnknownOffset
This file provides utility analysis objects describing memory locations.
#define I(x, y, z)
Definition: MD5.cpp:58
static Optional< InstantiatedValue > getNodeBelow(const CFLGraph &Graph, InstantiatedValue V)
static void processWorkListItem(const WorkListItem &Item, const CFLGraph &Graph, ReachabilitySet &ReachSet, AliasMemSet &MemSet, std::vector< WorkListItem > &WorkList)
bool hasUnknownOrCallerAttr(AliasAttrs Attr)
std::bitset< NumAliasAttrs > AliasAttrs
These are attributes that an alias analysis can use to mark certain special properties of a given poi...
static bool hasReadOnlyState(StateSet Set)
const AliasSummary & getAliasSummary() const
Analysis pass providing the TargetLibraryInfo.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
CFLAndersAAResult run(Function &F, FunctionAnalysisManager &AM)
static const Function * parentFunctionOfValue(const Value *Val)
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:343
LLVM Value Representation.
Definition: Value.h:73
const CFLGraph & getCFLGraph() const
Definition: CFLGraph.h:651
print Print MemDeps of function
A container for analyses that lazily runs them and caches their results.
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1975
ImmutablePass * createCFLAndersAAWrapperPass()
bool mayAlias(const Value *, LocationSize, const Value *, LocationSize) const
static unsigned getHashValue(const OffsetValue &OVal)
This header defines various interfaces for pass management in LLVM.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70
iterator_range< arg_iterator > args()
Definition: Function.h:719
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:1224