LLVM  9.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 
93  : AAResultBase(std::move(RHS)), TLI(RHS.TLI) {}
95 
96 namespace {
97 
98 enum class MatchState : uint8_t {
99  // The following state represents S1 in the paper.
100  FlowFromReadOnly = 0,
101  // The following two states together represent S2 in the paper.
102  // The 'NoReadWrite' suffix indicates that there exists an alias path that
103  // does not contain assignment and reverse assignment edges.
104  // The 'ReadOnly' suffix indicates that there exists an alias path that
105  // contains reverse assignment edges only.
106  FlowFromMemAliasNoReadWrite,
107  FlowFromMemAliasReadOnly,
108  // The following two states together represent S3 in the paper.
109  // The 'WriteOnly' suffix indicates that there exists an alias path that
110  // contains assignment edges only.
111  // The 'ReadWrite' suffix indicates that there exists an alias path that
112  // contains both assignment and reverse assignment edges. Note that if X and Y
113  // are reachable at 'ReadWrite' state, it does NOT mean X is both read from
114  // and written to Y. Instead, it means that a third value Z is written to both
115  // X and Y.
116  FlowToWriteOnly,
117  FlowToReadWrite,
118  // The following two states together represent S4 in the paper.
119  FlowToMemAliasWriteOnly,
120  FlowToMemAliasReadWrite,
121 };
122 
123 using StateSet = std::bitset<7>;
124 
125 const unsigned ReadOnlyStateMask =
126  (1U << static_cast<uint8_t>(MatchState::FlowFromReadOnly)) |
127  (1U << static_cast<uint8_t>(MatchState::FlowFromMemAliasReadOnly));
128 const unsigned WriteOnlyStateMask =
129  (1U << static_cast<uint8_t>(MatchState::FlowToWriteOnly)) |
130  (1U << static_cast<uint8_t>(MatchState::FlowToMemAliasWriteOnly));
131 
132 // A pair that consists of a value and an offset
133 struct OffsetValue {
134  const Value *Val;
135  int64_t Offset;
136 };
137 
138 bool operator==(OffsetValue LHS, OffsetValue RHS) {
139  return LHS.Val == RHS.Val && LHS.Offset == RHS.Offset;
140 }
141 bool operator<(OffsetValue LHS, OffsetValue RHS) {
142  return std::less<const Value *>()(LHS.Val, RHS.Val) ||
143  (LHS.Val == RHS.Val && LHS.Offset < RHS.Offset);
144 }
145 
146 // A pair that consists of an InstantiatedValue and an offset
147 struct OffsetInstantiatedValue {
148  InstantiatedValue IVal;
149  int64_t Offset;
150 };
151 
152 bool operator==(OffsetInstantiatedValue LHS, OffsetInstantiatedValue RHS) {
153  return LHS.IVal == RHS.IVal && LHS.Offset == RHS.Offset;
154 }
155 
156 // We use ReachabilitySet to keep track of value aliases (The nonterminal "V" in
157 // the paper) during the analysis.
158 class ReachabilitySet {
159  using ValueStateMap = DenseMap<InstantiatedValue, StateSet>;
160  using ValueReachMap = DenseMap<InstantiatedValue, ValueStateMap>;
161 
162  ValueReachMap ReachMap;
163 
164 public:
165  using const_valuestate_iterator = ValueStateMap::const_iterator;
166  using const_value_iterator = ValueReachMap::const_iterator;
167 
168  // Insert edge 'From->To' at state 'State'
169  bool insert(InstantiatedValue From, InstantiatedValue To, MatchState State) {
170  assert(From != To);
171  auto &States = ReachMap[To][From];
172  auto Idx = static_cast<size_t>(State);
173  if (!States.test(Idx)) {
174  States.set(Idx);
175  return true;
176  }
177  return false;
178  }
179 
180  // Return the set of all ('From', 'State') pair for a given node 'To'
182  reachableValueAliases(InstantiatedValue V) const {
183  auto Itr = ReachMap.find(V);
184  if (Itr == ReachMap.end())
185  return make_range<const_valuestate_iterator>(const_valuestate_iterator(),
186  const_valuestate_iterator());
187  return make_range<const_valuestate_iterator>(Itr->second.begin(),
188  Itr->second.end());
189  }
190 
191  iterator_range<const_value_iterator> value_mappings() const {
192  return make_range<const_value_iterator>(ReachMap.begin(), ReachMap.end());
193  }
194 };
195 
196 // We use AliasMemSet to keep track of all memory aliases (the nonterminal "M"
197 // in the paper) during the analysis.
198 class AliasMemSet {
199  using MemSet = DenseSet<InstantiatedValue>;
200  using MemMapType = DenseMap<InstantiatedValue, MemSet>;
201 
202  MemMapType MemMap;
203 
204 public:
205  using const_mem_iterator = MemSet::const_iterator;
206 
207  bool insert(InstantiatedValue LHS, InstantiatedValue RHS) {
208  // Top-level values can never be memory aliases because one cannot take the
209  // addresses of them
210  assert(LHS.DerefLevel > 0 && RHS.DerefLevel > 0);
211  return MemMap[LHS].insert(RHS).second;
212  }
213 
214  const MemSet *getMemoryAliases(InstantiatedValue V) const {
215  auto Itr = MemMap.find(V);
216  if (Itr == MemMap.end())
217  return nullptr;
218  return &Itr->second;
219  }
220 };
221 
222 // We use AliasAttrMap to keep track of the AliasAttr of each node.
223 class AliasAttrMap {
225 
226  MapType AttrMap;
227 
228 public:
229  using const_iterator = MapType::const_iterator;
230 
231  bool add(InstantiatedValue V, AliasAttrs Attr) {
232  auto &OldAttr = AttrMap[V];
233  auto NewAttr = OldAttr | Attr;
234  if (OldAttr == NewAttr)
235  return false;
236  OldAttr = NewAttr;
237  return true;
238  }
239 
240  AliasAttrs getAttrs(InstantiatedValue V) const {
241  AliasAttrs Attr;
242  auto Itr = AttrMap.find(V);
243  if (Itr != AttrMap.end())
244  Attr = Itr->second;
245  return Attr;
246  }
247 
248  iterator_range<const_iterator> mappings() const {
249  return make_range<const_iterator>(AttrMap.begin(), AttrMap.end());
250  }
251 };
252 
253 struct WorkListItem {
256  MatchState State;
257 };
258 
259 struct ValueSummary {
260  struct Record {
261  InterfaceValue IValue;
262  unsigned DerefLevel;
263  };
264  SmallVector<Record, 4> FromRecords, ToRecords;
265 };
266 
267 } // end anonymous namespace
268 
269 namespace llvm {
270 
271 // Specialize DenseMapInfo for OffsetValue.
272 template <> struct DenseMapInfo<OffsetValue> {
273  static OffsetValue getEmptyKey() {
274  return OffsetValue{DenseMapInfo<const Value *>::getEmptyKey(),
276  }
277 
278  static OffsetValue getTombstoneKey() {
281  }
282 
283  static unsigned getHashValue(const OffsetValue &OVal) {
285  std::make_pair(OVal.Val, OVal.Offset));
286  }
287 
288  static bool isEqual(const OffsetValue &LHS, const OffsetValue &RHS) {
289  return LHS == RHS;
290  }
291 };
292 
293 // Specialize DenseMapInfo for OffsetInstantiatedValue.
294 template <> struct DenseMapInfo<OffsetInstantiatedValue> {
295  static OffsetInstantiatedValue getEmptyKey() {
296  return OffsetInstantiatedValue{
299  }
300 
301  static OffsetInstantiatedValue getTombstoneKey() {
302  return OffsetInstantiatedValue{
305  }
306 
307  static unsigned getHashValue(const OffsetInstantiatedValue &OVal) {
309  std::make_pair(OVal.IVal, OVal.Offset));
310  }
311 
312  static bool isEqual(const OffsetInstantiatedValue &LHS,
313  const OffsetInstantiatedValue &RHS) {
314  return LHS == RHS;
315  }
316 };
317 
318 } // end namespace llvm
319 
321  /// Map a value to other values that may alias it
322  /// Since the alias relation is symmetric, to save some space we assume values
323  /// are properly ordered: if a and b alias each other, and a < b, then b is in
324  /// AliasMap[a] but not vice versa.
326 
327  /// Map a value to its corresponding AliasAttrs
329 
330  /// Summary of externally visible effects.
331  AliasSummary Summary;
332 
333  Optional<AliasAttrs> getAttrs(const Value *) const;
334 
335 public:
337  const ReachabilitySet &, const AliasAttrMap &);
338 
339  bool mayAlias(const Value *, LocationSize, const Value *, LocationSize) const;
340  const AliasSummary &getAliasSummary() const { return Summary; }
341 };
342 
343 static bool hasReadOnlyState(StateSet Set) {
344  return (Set & StateSet(ReadOnlyStateMask)).any();
345 }
346 
347 static bool hasWriteOnlyState(StateSet Set) {
348  return (Set & StateSet(WriteOnlyStateMask)).any();
349 }
350 
353  const SmallVectorImpl<Value *> &RetVals) {
354  auto Val = IValue.Val;
355 
357  if (auto Arg = dyn_cast<Argument>(Val))
358  Index = Arg->getArgNo() + 1;
359  else if (is_contained(RetVals, Val))
360  Index = 0;
361 
362  if (Index)
363  return InterfaceValue{*Index, IValue.DerefLevel};
364  return None;
365 }
366 
368  const AliasAttrMap &AMap) {
369  for (const auto &Mapping : AMap.mappings()) {
370  auto IVal = Mapping.first;
371 
372  // Insert IVal into the map
373  auto &Attr = AttrMap[IVal.Val];
374  // AttrMap only cares about top-level values
375  if (IVal.DerefLevel == 0)
376  Attr |= Mapping.second;
377  }
378 }
379 
380 static void
381 populateAliasMap(DenseMap<const Value *, std::vector<OffsetValue>> &AliasMap,
382  const ReachabilitySet &ReachSet) {
383  for (const auto &OuterMapping : ReachSet.value_mappings()) {
384  // AliasMap only cares about top-level values
385  if (OuterMapping.first.DerefLevel > 0)
386  continue;
387 
388  auto Val = OuterMapping.first.Val;
389  auto &AliasList = AliasMap[Val];
390  for (const auto &InnerMapping : OuterMapping.second) {
391  // Again, AliasMap only cares about top-level values
392  if (InnerMapping.first.DerefLevel == 0)
393  AliasList.push_back(OffsetValue{InnerMapping.first.Val, UnknownOffset});
394  }
395 
396  // Sort AliasList for faster lookup
397  llvm::sort(AliasList);
398  }
399 }
400 
402  SmallVectorImpl<ExternalRelation> &ExtRelations, const Function &Fn,
403  const SmallVectorImpl<Value *> &RetVals, const ReachabilitySet &ReachSet) {
404  // If a function only returns one of its argument X, then X will be both an
405  // argument and a return value at the same time. This is an edge case that
406  // needs special handling here.
407  for (const auto &Arg : Fn.args()) {
408  if (is_contained(RetVals, &Arg)) {
409  auto ArgVal = InterfaceValue{Arg.getArgNo() + 1, 0};
410  auto RetVal = InterfaceValue{0, 0};
411  ExtRelations.push_back(ExternalRelation{ArgVal, RetVal, 0});
412  }
413  }
414 
415  // Below is the core summary construction logic.
416  // A naive solution of adding only the value aliases that are parameters or
417  // return values in ReachSet to the summary won't work: It is possible that a
418  // parameter P is written into an intermediate value I, and the function
419  // subsequently returns *I. In that case, *I is does not value alias anything
420  // in ReachSet, and the naive solution will miss a summary edge from (P, 1) to
421  // (I, 1).
422  // To account for the aforementioned case, we need to check each non-parameter
423  // and non-return value for the possibility of acting as an intermediate.
424  // 'ValueMap' here records, for each value, which InterfaceValues read from or
425  // write into it. If both the read list and the write list of a given value
426  // are non-empty, we know that a particular value is an intermidate and we
427  // need to add summary edges from the writes to the reads.
429  for (const auto &OuterMapping : ReachSet.value_mappings()) {
430  if (auto Dst = getInterfaceValue(OuterMapping.first, RetVals)) {
431  for (const auto &InnerMapping : OuterMapping.second) {
432  // If Src is a param/return value, we get a same-level assignment.
433  if (auto Src = getInterfaceValue(InnerMapping.first, RetVals)) {
434  // This may happen if both Dst and Src are return values
435  if (*Dst == *Src)
436  continue;
437 
438  if (hasReadOnlyState(InnerMapping.second))
439  ExtRelations.push_back(ExternalRelation{*Dst, *Src, UnknownOffset});
440  // No need to check for WriteOnly state, since ReachSet is symmetric
441  } else {
442  // If Src is not a param/return, add it to ValueMap
443  auto SrcIVal = InnerMapping.first;
444  if (hasReadOnlyState(InnerMapping.second))
445  ValueMap[SrcIVal.Val].FromRecords.push_back(
446  ValueSummary::Record{*Dst, SrcIVal.DerefLevel});
447  if (hasWriteOnlyState(InnerMapping.second))
448  ValueMap[SrcIVal.Val].ToRecords.push_back(
449  ValueSummary::Record{*Dst, SrcIVal.DerefLevel});
450  }
451  }
452  }
453  }
454 
455  for (const auto &Mapping : ValueMap) {
456  for (const auto &FromRecord : Mapping.second.FromRecords) {
457  for (const auto &ToRecord : Mapping.second.ToRecords) {
458  auto ToLevel = ToRecord.DerefLevel;
459  auto FromLevel = FromRecord.DerefLevel;
460  // Same-level assignments should have already been processed by now
461  if (ToLevel == FromLevel)
462  continue;
463 
464  auto SrcIndex = FromRecord.IValue.Index;
465  auto SrcLevel = FromRecord.IValue.DerefLevel;
466  auto DstIndex = ToRecord.IValue.Index;
467  auto DstLevel = ToRecord.IValue.DerefLevel;
468  if (ToLevel > FromLevel)
469  SrcLevel += ToLevel - FromLevel;
470  else
471  DstLevel += FromLevel - ToLevel;
472 
473  ExtRelations.push_back(ExternalRelation{
474  InterfaceValue{SrcIndex, SrcLevel},
475  InterfaceValue{DstIndex, DstLevel}, UnknownOffset});
476  }
477  }
478  }
479 
480  // Remove duplicates in ExtRelations
481  llvm::sort(ExtRelations);
482  ExtRelations.erase(std::unique(ExtRelations.begin(), ExtRelations.end()),
483  ExtRelations.end());
484 }
485 
487  SmallVectorImpl<ExternalAttribute> &ExtAttributes, const Function &Fn,
488  const SmallVectorImpl<Value *> &RetVals, const AliasAttrMap &AMap) {
489  for (const auto &Mapping : AMap.mappings()) {
490  if (auto IVal = getInterfaceValue(Mapping.first, RetVals)) {
491  auto Attr = getExternallyVisibleAttrs(Mapping.second);
492  if (Attr.any())
493  ExtAttributes.push_back(ExternalAttribute{*IVal, Attr});
494  }
495  }
496 }
497 
499  const Function &Fn, const SmallVectorImpl<Value *> &RetVals,
500  const ReachabilitySet &ReachSet, const AliasAttrMap &AMap) {
501  populateAttrMap(AttrMap, AMap);
502  populateExternalAttributes(Summary.RetParamAttributes, Fn, RetVals, AMap);
503  populateAliasMap(AliasMap, ReachSet);
504  populateExternalRelations(Summary.RetParamRelations, Fn, RetVals, ReachSet);
505 }
506 
508 CFLAndersAAResult::FunctionInfo::getAttrs(const Value *V) const {
509  assert(V != nullptr);
510 
511  auto Itr = AttrMap.find(V);
512  if (Itr != AttrMap.end())
513  return Itr->second;
514  return None;
515 }
516 
518  const Value *LHS, LocationSize MaybeLHSSize, const Value *RHS,
519  LocationSize MaybeRHSSize) const {
520  assert(LHS && RHS);
521 
522  // Check if we've seen LHS and RHS before. Sometimes LHS or RHS can be created
523  // after the analysis gets executed, and we want to be conservative in those
524  // cases.
525  auto MaybeAttrsA = getAttrs(LHS);
526  auto MaybeAttrsB = getAttrs(RHS);
527  if (!MaybeAttrsA || !MaybeAttrsB)
528  return true;
529 
530  // Check AliasAttrs before AliasMap lookup since it's cheaper
531  auto AttrsA = *MaybeAttrsA;
532  auto AttrsB = *MaybeAttrsB;
533  if (hasUnknownOrCallerAttr(AttrsA))
534  return AttrsB.any();
535  if (hasUnknownOrCallerAttr(AttrsB))
536  return AttrsA.any();
537  if (isGlobalOrArgAttr(AttrsA))
538  return isGlobalOrArgAttr(AttrsB);
539  if (isGlobalOrArgAttr(AttrsB))
540  return isGlobalOrArgAttr(AttrsA);
541 
542  // At this point both LHS and RHS should point to locally allocated objects
543 
544  auto Itr = AliasMap.find(LHS);
545  if (Itr != AliasMap.end()) {
546 
547  // Find out all (X, Offset) where X == RHS
548  auto Comparator = [](OffsetValue LHS, OffsetValue RHS) {
549  return std::less<const Value *>()(LHS.Val, RHS.Val);
550  };
551 #ifdef EXPENSIVE_CHECKS
552  assert(std::is_sorted(Itr->second.begin(), Itr->second.end(), Comparator));
553 #endif
554  auto RangePair = std::equal_range(Itr->second.begin(), Itr->second.end(),
555  OffsetValue{RHS, 0}, Comparator);
556 
557  if (RangePair.first != RangePair.second) {
558  // Be conservative about unknown sizes
559  if (MaybeLHSSize == LocationSize::unknown() ||
560  MaybeRHSSize == LocationSize::unknown())
561  return true;
562 
563  const uint64_t LHSSize = MaybeLHSSize.getValue();
564  const uint64_t RHSSize = MaybeRHSSize.getValue();
565 
566  for (const auto &OVal : make_range(RangePair)) {
567  // Be conservative about UnknownOffset
568  if (OVal.Offset == UnknownOffset)
569  return true;
570 
571  // We know that LHS aliases (RHS + OVal.Offset) if the control flow
572  // reaches here. The may-alias query essentially becomes integer
573  // range-overlap queries over two ranges [OVal.Offset, OVal.Offset +
574  // LHSSize) and [0, RHSSize).
575 
576  // Try to be conservative on super large offsets
577  if (LLVM_UNLIKELY(LHSSize > INT64_MAX || RHSSize > INT64_MAX))
578  return true;
579 
580  auto LHSStart = OVal.Offset;
581  // FIXME: Do we need to guard against integer overflow?
582  auto LHSEnd = OVal.Offset + static_cast<int64_t>(LHSSize);
583  auto RHSStart = 0;
584  auto RHSEnd = static_cast<int64_t>(RHSSize);
585  if (LHSEnd > RHSStart && LHSStart < RHSEnd)
586  return true;
587  }
588  }
589  }
590 
591  return false;
592 }
593 
595  MatchState State, ReachabilitySet &ReachSet,
596  std::vector<WorkListItem> &WorkList) {
597  if (From == To)
598  return;
599  if (ReachSet.insert(From, To, State))
600  WorkList.push_back(WorkListItem{From, To, State});
601 }
602 
603 static void initializeWorkList(std::vector<WorkListItem> &WorkList,
604  ReachabilitySet &ReachSet,
605  const CFLGraph &Graph) {
606  for (const auto &Mapping : Graph.value_mappings()) {
607  auto Val = Mapping.first;
608  auto &ValueInfo = Mapping.second;
609  assert(ValueInfo.getNumLevels() > 0);
610 
611  // Insert all immediate assignment neighbors to the worklist
612  for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I) {
613  auto Src = InstantiatedValue{Val, I};
614  // If there's an assignment edge from X to Y, it means Y is reachable from
615  // X at S3 and X is reachable from Y at S1
616  for (auto &Edge : ValueInfo.getNodeInfoAtLevel(I).Edges) {
617  propagate(Edge.Other, Src, MatchState::FlowFromReadOnly, ReachSet,
618  WorkList);
619  propagate(Src, Edge.Other, MatchState::FlowToWriteOnly, ReachSet,
620  WorkList);
621  }
622  }
623  }
624 }
625 
627  InstantiatedValue V) {
628  auto NodeBelow = InstantiatedValue{V.Val, V.DerefLevel + 1};
629  if (Graph.getNode(NodeBelow))
630  return NodeBelow;
631  return None;
632 }
633 
634 static void processWorkListItem(const WorkListItem &Item, const CFLGraph &Graph,
635  ReachabilitySet &ReachSet, AliasMemSet &MemSet,
636  std::vector<WorkListItem> &WorkList) {
637  auto FromNode = Item.From;
638  auto ToNode = Item.To;
639 
640  auto NodeInfo = Graph.getNode(ToNode);
641  assert(NodeInfo != nullptr);
642 
643  // TODO: propagate field offsets
644 
645  // FIXME: Here is a neat trick we can do: since both ReachSet and MemSet holds
646  // relations that are symmetric, we could actually cut the storage by half by
647  // sorting FromNode and ToNode before insertion happens.
648 
649  // The newly added value alias pair may potentially generate more memory
650  // alias pairs. Check for them here.
651  auto FromNodeBelow = getNodeBelow(Graph, FromNode);
652  auto ToNodeBelow = getNodeBelow(Graph, ToNode);
653  if (FromNodeBelow && ToNodeBelow &&
654  MemSet.insert(*FromNodeBelow, *ToNodeBelow)) {
655  propagate(*FromNodeBelow, *ToNodeBelow,
656  MatchState::FlowFromMemAliasNoReadWrite, ReachSet, WorkList);
657  for (const auto &Mapping : ReachSet.reachableValueAliases(*FromNodeBelow)) {
658  auto Src = Mapping.first;
659  auto MemAliasPropagate = [&](MatchState FromState, MatchState ToState) {
660  if (Mapping.second.test(static_cast<size_t>(FromState)))
661  propagate(Src, *ToNodeBelow, ToState, ReachSet, WorkList);
662  };
663 
664  MemAliasPropagate(MatchState::FlowFromReadOnly,
665  MatchState::FlowFromMemAliasReadOnly);
666  MemAliasPropagate(MatchState::FlowToWriteOnly,
667  MatchState::FlowToMemAliasWriteOnly);
668  MemAliasPropagate(MatchState::FlowToReadWrite,
669  MatchState::FlowToMemAliasReadWrite);
670  }
671  }
672 
673  // This is the core of the state machine walking algorithm. We expand ReachSet
674  // based on which state we are at (which in turn dictates what edges we
675  // should examine)
676  // From a high-level point of view, the state machine here guarantees two
677  // properties:
678  // - If *X and *Y are memory aliases, then X and Y are value aliases
679  // - If Y is an alias of X, then reverse assignment edges (if there is any)
680  // should precede any assignment edges on the path from X to Y.
681  auto NextAssignState = [&](MatchState State) {
682  for (const auto &AssignEdge : NodeInfo->Edges)
683  propagate(FromNode, AssignEdge.Other, State, ReachSet, WorkList);
684  };
685  auto NextRevAssignState = [&](MatchState State) {
686  for (const auto &RevAssignEdge : NodeInfo->ReverseEdges)
687  propagate(FromNode, RevAssignEdge.Other, State, ReachSet, WorkList);
688  };
689  auto NextMemState = [&](MatchState State) {
690  if (auto AliasSet = MemSet.getMemoryAliases(ToNode)) {
691  for (const auto &MemAlias : *AliasSet)
692  propagate(FromNode, MemAlias, State, ReachSet, WorkList);
693  }
694  };
695 
696  switch (Item.State) {
697  case MatchState::FlowFromReadOnly:
698  NextRevAssignState(MatchState::FlowFromReadOnly);
699  NextAssignState(MatchState::FlowToReadWrite);
700  NextMemState(MatchState::FlowFromMemAliasReadOnly);
701  break;
702 
703  case MatchState::FlowFromMemAliasNoReadWrite:
704  NextRevAssignState(MatchState::FlowFromReadOnly);
705  NextAssignState(MatchState::FlowToWriteOnly);
706  break;
707 
708  case MatchState::FlowFromMemAliasReadOnly:
709  NextRevAssignState(MatchState::FlowFromReadOnly);
710  NextAssignState(MatchState::FlowToReadWrite);
711  break;
712 
713  case MatchState::FlowToWriteOnly:
714  NextAssignState(MatchState::FlowToWriteOnly);
715  NextMemState(MatchState::FlowToMemAliasWriteOnly);
716  break;
717 
718  case MatchState::FlowToReadWrite:
719  NextAssignState(MatchState::FlowToReadWrite);
720  NextMemState(MatchState::FlowToMemAliasReadWrite);
721  break;
722 
723  case MatchState::FlowToMemAliasWriteOnly:
724  NextAssignState(MatchState::FlowToWriteOnly);
725  break;
726 
727  case MatchState::FlowToMemAliasReadWrite:
728  NextAssignState(MatchState::FlowToReadWrite);
729  break;
730  }
731 }
732 
733 static AliasAttrMap buildAttrMap(const CFLGraph &Graph,
734  const ReachabilitySet &ReachSet) {
735  AliasAttrMap AttrMap;
736  std::vector<InstantiatedValue> WorkList, NextList;
737 
738  // Initialize each node with its original AliasAttrs in CFLGraph
739  for (const auto &Mapping : Graph.value_mappings()) {
740  auto Val = Mapping.first;
741  auto &ValueInfo = Mapping.second;
742  for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I) {
743  auto Node = InstantiatedValue{Val, I};
744  AttrMap.add(Node, ValueInfo.getNodeInfoAtLevel(I).Attr);
745  WorkList.push_back(Node);
746  }
747  }
748 
749  while (!WorkList.empty()) {
750  for (const auto &Dst : WorkList) {
751  auto DstAttr = AttrMap.getAttrs(Dst);
752  if (DstAttr.none())
753  continue;
754 
755  // Propagate attr on the same level
756  for (const auto &Mapping : ReachSet.reachableValueAliases(Dst)) {
757  auto Src = Mapping.first;
758  if (AttrMap.add(Src, DstAttr))
759  NextList.push_back(Src);
760  }
761 
762  // Propagate attr to the levels below
763  auto DstBelow = getNodeBelow(Graph, Dst);
764  while (DstBelow) {
765  if (AttrMap.add(*DstBelow, DstAttr)) {
766  NextList.push_back(*DstBelow);
767  break;
768  }
769  DstBelow = getNodeBelow(Graph, *DstBelow);
770  }
771  }
772  WorkList.swap(NextList);
773  NextList.clear();
774  }
775 
776  return AttrMap;
777 }
778 
780 CFLAndersAAResult::buildInfoFrom(const Function &Fn) {
782  *this, TLI,
783  // Cast away the constness here due to GraphBuilder's API requirement
784  const_cast<Function &>(Fn));
785  auto &Graph = GraphBuilder.getCFLGraph();
786 
787  ReachabilitySet ReachSet;
788  AliasMemSet MemSet;
789 
790  std::vector<WorkListItem> WorkList, NextList;
791  initializeWorkList(WorkList, ReachSet, Graph);
792  // TODO: make sure we don't stop before the fix point is reached
793  while (!WorkList.empty()) {
794  for (const auto &Item : WorkList)
795  processWorkListItem(Item, Graph, ReachSet, MemSet, NextList);
796 
797  NextList.swap(WorkList);
798  NextList.clear();
799  }
800 
801  // Now that we have all the reachability info, propagate AliasAttrs according
802  // to it
803  auto IValueAttrMap = buildAttrMap(Graph, ReachSet);
804 
805  return FunctionInfo(Fn, GraphBuilder.getReturnValues(), ReachSet,
806  std::move(IValueAttrMap));
807 }
808 
809 void CFLAndersAAResult::scan(const Function &Fn) {
810  auto InsertPair = Cache.insert(std::make_pair(&Fn, Optional<FunctionInfo>()));
811  (void)InsertPair;
812  assert(InsertPair.second &&
813  "Trying to scan a function that has already been cached");
814 
815  // Note that we can't do Cache[Fn] = buildSetsFrom(Fn) here: the function call
816  // may get evaluated after operator[], potentially triggering a DenseMap
817  // resize and invalidating the reference returned by operator[]
818  auto FunInfo = buildInfoFrom(Fn);
819  Cache[&Fn] = std::move(FunInfo);
820  Handles.emplace_front(const_cast<Function *>(&Fn), this);
821 }
822 
823 void CFLAndersAAResult::evict(const Function *Fn) { Cache.erase(Fn); }
824 
826 CFLAndersAAResult::ensureCached(const Function &Fn) {
827  auto Iter = Cache.find(&Fn);
828  if (Iter == Cache.end()) {
829  scan(Fn);
830  Iter = Cache.find(&Fn);
831  assert(Iter != Cache.end());
832  assert(Iter->second.hasValue());
833  }
834  return Iter->second;
835 }
836 
838  auto &FunInfo = ensureCached(Fn);
839  if (FunInfo.hasValue())
840  return &FunInfo->getAliasSummary();
841  else
842  return nullptr;
843 }
844 
846  const MemoryLocation &LocB) {
847  auto *ValA = LocA.Ptr;
848  auto *ValB = LocB.Ptr;
849 
850  if (!ValA->getType()->isPointerTy() || !ValB->getType()->isPointerTy())
851  return NoAlias;
852 
853  auto *Fn = parentFunctionOfValue(ValA);
854  if (!Fn) {
855  Fn = parentFunctionOfValue(ValB);
856  if (!Fn) {
857  // The only times this is known to happen are when globals + InlineAsm are
858  // involved
859  LLVM_DEBUG(
860  dbgs()
861  << "CFLAndersAA: could not extract parent function information.\n");
862  return MayAlias;
863  }
864  } else {
865  assert(!parentFunctionOfValue(ValB) || parentFunctionOfValue(ValB) == Fn);
866  }
867 
868  assert(Fn != nullptr);
869  auto &FunInfo = ensureCached(*Fn);
870 
871  // AliasMap lookup
872  if (FunInfo->mayAlias(ValA, LocA.Size, ValB, LocB.Size))
873  return MayAlias;
874  return NoAlias;
875 }
876 
878  const MemoryLocation &LocB,
879  AAQueryInfo &AAQI) {
880  if (LocA.Ptr == LocB.Ptr)
881  return MustAlias;
882 
883  // Comparisons between global variables and other constants should be
884  // handled by BasicAA.
885  // CFLAndersAA may report NoAlias when comparing a GlobalValue and
886  // ConstantExpr, but every query needs to have at least one Value tied to a
887  // Function, and neither GlobalValues nor ConstantExprs are.
888  if (isa<Constant>(LocA.Ptr) && isa<Constant>(LocB.Ptr))
889  return AAResultBase::alias(LocA, LocB, AAQI);
890 
891  AliasResult QueryResult = query(LocA, LocB);
892  if (QueryResult == MayAlias)
893  return AAResultBase::alias(LocA, LocB, AAQI);
894 
895  return QueryResult;
896 }
897 
898 AnalysisKey CFLAndersAA::Key;
899 
902 }
903 
906  "Inclusion-Based CFL Alias Analysis", false, true)
907 
909  return new CFLAndersAAWrapperPass();
910 }
911 
914 }
915 
917  auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>();
918  Result.reset(new CFLAndersAAResult(TLIWP.getTLI()));
919 }
920 
922  AU.setPreservesAll();
924 }
static void populateExternalAttributes(SmallVectorImpl< ExternalAttribute > &ExtAttributes, const Function &Fn, const SmallVectorImpl< Value *> &RetVals, const AliasAttrMap &AMap)
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
void evict(const Function *Fn)
Evict the given function from cache.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h: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:191
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
static AliasAttrMap buildAttrMap(const CFLGraph &Graph, const ReachabilitySet &ReachSet)
FunctionInfo(const Function &, const SmallVectorImpl< Value *> &, const ReachabilitySet &, const AliasAttrMap &)
static bool isEqual(const OffsetValue &LHS, const OffsetValue &RHS)
#define INT64_MAX
Definition: DataTypes.h:77
CFLAndersAAResult(const TargetLibraryInfo &TLI)
const cflaa::AliasSummary * getAliasSummary(const Function &)
Get the alias summary for the given function Return nullptr if the summary is not found or not availa...
A CRTP-driven "mixin" base class to help implement the function alias analysis results concept...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
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:1122
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:196
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:72
const CFLGraph & getCFLGraph() const
Definition: CFLGraph.h:651
A container for analyses that lazily runs them and caches their results.
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1966
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:705
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:1251