LLVM  6.0.0svn
CFLAndersAliasAnalysis.cpp
Go to the documentation of this file.
1 //===- CFLAndersAliasAnalysis.cpp - Unification-based Alias Analysis ------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements a CFL-based, summary-based alias analysis algorithm. It
11 // differs from CFLSteensAliasAnalysis in its inclusion-based nature while
12 // CFLSteensAliasAnalysis is unification-based. This pass has worse performance
13 // than CFLSteensAliasAnalysis (the worst case complexity of
14 // CFLAndersAliasAnalysis is cubic, while the worst case complexity of
15 // CFLSteensAliasAnalysis is almost linear), but it is able to yield more
16 // precise analysis result. The precision of this analysis is roughly the same
17 // as that of an one level context-sensitive Andersen's algorithm.
18 //
19 // The algorithm used here is based on recursive state machine matching scheme
20 // proposed in "Demand-driven alias analysis for C" by Xin Zheng and Radu
21 // Rugina. The general idea is to extend the tranditional transitive closure
22 // algorithm to perform CFL matching along the way: instead of recording
23 // "whether X is reachable from Y", we keep track of "whether X is reachable
24 // from Y at state Z", where the "state" field indicates where we are in the CFL
25 // matching process. To understand the matching better, it is advisable to have
26 // the state machine shown in Figure 3 of the paper available when reading the
27 // codes: all we do here is to selectively expand the transitive closure by
28 // discarding edges that are not recognized by the state machine.
29 //
30 // There are two differences between our current implementation and the one
31 // described in the paper:
32 // - Our algorithm eagerly computes all alias pairs after the CFLGraph is built,
33 // while in the paper the authors did the computation in a demand-driven
34 // fashion. We did not implement the demand-driven algorithm due to the
35 // additional coding complexity and higher memory profile, but if we found it
36 // necessary we may switch to it eventually.
37 // - In the paper the authors use a state machine that does not distinguish
38 // value reads from value writes. For example, if Y is reachable from X at state
39 // S3, it may be the case that X is written into Y, or it may be the case that
40 // there's a third value Z that writes into both X and Y. To make that
41 // distinction (which is crucial in building function summary as well as
42 // retrieving mod-ref info), we choose to duplicate some of the states in the
43 // paper's proposed state machine. The duplication does not change the set the
44 // machine accepts. Given a pair of reachable values, it only provides more
45 // detailed information on which value is being written into and which is being
46 // read from.
47 //
48 //===----------------------------------------------------------------------===//
49 
50 // N.B. AliasAnalysis as a whole is phrased as a FunctionPass at the moment, and
51 // CFLAndersAA is interprocedural. This is *technically* A Bad Thing, because
52 // FunctionPasses are only allowed to inspect the Function that they're being
53 // run on. Realistically, this likely isn't a problem until we allow
54 // FunctionPasses to run concurrently.
55 
57 #include "AliasAnalysisSummary.h"
58 #include "CFLGraph.h"
59 #include "llvm/ADT/DenseMap.h"
60 #include "llvm/ADT/DenseMapInfo.h"
61 #include "llvm/ADT/DenseSet.h"
62 #include "llvm/ADT/None.h"
63 #include "llvm/ADT/Optional.h"
64 #include "llvm/ADT/STLExtras.h"
65 #include "llvm/ADT/SmallVector.h"
69 #include "llvm/IR/Argument.h"
70 #include "llvm/IR/Function.h"
71 #include "llvm/IR/PassManager.h"
72 #include "llvm/IR/Type.h"
73 #include "llvm/Pass.h"
74 #include "llvm/Support/Casting.h"
75 #include "llvm/Support/Compiler.h"
76 #include "llvm/Support/Debug.h"
78 #include <algorithm>
79 #include <bitset>
80 #include <cassert>
81 #include <cstddef>
82 #include <cstdint>
83 #include <functional>
84 #include <utility>
85 #include <vector>
86 
87 using namespace llvm;
88 using namespace llvm::cflaa;
89 
90 #define DEBUG_TYPE "cfl-anders-aa"
91 
94  : AAResultBase(std::move(RHS)), TLI(RHS.TLI) {}
96 
97 namespace {
98 
99 enum class MatchState : uint8_t {
100  // The following state represents S1 in the paper.
101  FlowFromReadOnly = 0,
102  // The following two states together represent S2 in the paper.
103  // The 'NoReadWrite' suffix indicates that there exists an alias path that
104  // does not contain assignment and reverse assignment edges.
105  // The 'ReadOnly' suffix indicates that there exists an alias path that
106  // contains reverse assignment edges only.
107  FlowFromMemAliasNoReadWrite,
108  FlowFromMemAliasReadOnly,
109  // The following two states together represent S3 in the paper.
110  // The 'WriteOnly' suffix indicates that there exists an alias path that
111  // contains assignment edges only.
112  // The 'ReadWrite' suffix indicates that there exists an alias path that
113  // contains both assignment and reverse assignment edges. Note that if X and Y
114  // are reachable at 'ReadWrite' state, it does NOT mean X is both read from
115  // and written to Y. Instead, it means that a third value Z is written to both
116  // X and Y.
117  FlowToWriteOnly,
118  FlowToReadWrite,
119  // The following two states together represent S4 in the paper.
120  FlowToMemAliasWriteOnly,
121  FlowToMemAliasReadWrite,
122 };
123 
124 using StateSet = std::bitset<7>;
125 
126 const unsigned ReadOnlyStateMask =
127  (1U << static_cast<uint8_t>(MatchState::FlowFromReadOnly)) |
128  (1U << static_cast<uint8_t>(MatchState::FlowFromMemAliasReadOnly));
129 const unsigned WriteOnlyStateMask =
130  (1U << static_cast<uint8_t>(MatchState::FlowToWriteOnly)) |
131  (1U << static_cast<uint8_t>(MatchState::FlowToMemAliasWriteOnly));
132 
133 // A pair that consists of a value and an offset
134 struct OffsetValue {
135  const Value *Val;
136  int64_t Offset;
137 };
138 
139 bool operator==(OffsetValue LHS, OffsetValue RHS) {
140  return LHS.Val == RHS.Val && LHS.Offset == RHS.Offset;
141 }
142 bool operator<(OffsetValue LHS, OffsetValue RHS) {
143  return std::less<const Value *>()(LHS.Val, RHS.Val) ||
144  (LHS.Val == RHS.Val && LHS.Offset < RHS.Offset);
145 }
146 
147 // A pair that consists of an InstantiatedValue and an offset
148 struct OffsetInstantiatedValue {
149  InstantiatedValue IVal;
150  int64_t Offset;
151 };
152 
153 bool operator==(OffsetInstantiatedValue LHS, OffsetInstantiatedValue RHS) {
154  return LHS.IVal == RHS.IVal && LHS.Offset == RHS.Offset;
155 }
156 
157 // We use ReachabilitySet to keep track of value aliases (The nonterminal "V" in
158 // the paper) during the analysis.
159 class ReachabilitySet {
160  using ValueStateMap = DenseMap<InstantiatedValue, StateSet>;
161  using ValueReachMap = DenseMap<InstantiatedValue, ValueStateMap>;
162 
163  ValueReachMap ReachMap;
164 
165 public:
166  using const_valuestate_iterator = ValueStateMap::const_iterator;
167  using const_value_iterator = ValueReachMap::const_iterator;
168 
169  // Insert edge 'From->To' at state 'State'
170  bool insert(InstantiatedValue From, InstantiatedValue To, MatchState State) {
171  assert(From != To);
172  auto &States = ReachMap[To][From];
173  auto Idx = static_cast<size_t>(State);
174  if (!States.test(Idx)) {
175  States.set(Idx);
176  return true;
177  }
178  return false;
179  }
180 
181  // Return the set of all ('From', 'State') pair for a given node 'To'
183  reachableValueAliases(InstantiatedValue V) const {
184  auto Itr = ReachMap.find(V);
185  if (Itr == ReachMap.end())
186  return make_range<const_valuestate_iterator>(const_valuestate_iterator(),
187  const_valuestate_iterator());
188  return make_range<const_valuestate_iterator>(Itr->second.begin(),
189  Itr->second.end());
190  }
191 
192  iterator_range<const_value_iterator> value_mappings() const {
193  return make_range<const_value_iterator>(ReachMap.begin(), ReachMap.end());
194  }
195 };
196 
197 // We use AliasMemSet to keep track of all memory aliases (the nonterminal "M"
198 // in the paper) during the analysis.
199 class AliasMemSet {
200  using MemSet = DenseSet<InstantiatedValue>;
201  using MemMapType = DenseMap<InstantiatedValue, MemSet>;
202 
203  MemMapType MemMap;
204 
205 public:
206  using const_mem_iterator = MemSet::const_iterator;
207 
208  bool insert(InstantiatedValue LHS, InstantiatedValue RHS) {
209  // Top-level values can never be memory aliases because one cannot take the
210  // addresses of them
211  assert(LHS.DerefLevel > 0 && RHS.DerefLevel > 0);
212  return MemMap[LHS].insert(RHS).second;
213  }
214 
215  const MemSet *getMemoryAliases(InstantiatedValue V) const {
216  auto Itr = MemMap.find(V);
217  if (Itr == MemMap.end())
218  return nullptr;
219  return &Itr->second;
220  }
221 };
222 
223 // We use AliasAttrMap to keep track of the AliasAttr of each node.
224 class AliasAttrMap {
226 
227  MapType AttrMap;
228 
229 public:
230  using const_iterator = MapType::const_iterator;
231 
232  bool add(InstantiatedValue V, AliasAttrs Attr) {
233  auto &OldAttr = AttrMap[V];
234  auto NewAttr = OldAttr | Attr;
235  if (OldAttr == NewAttr)
236  return false;
237  OldAttr = NewAttr;
238  return true;
239  }
240 
241  AliasAttrs getAttrs(InstantiatedValue V) const {
242  AliasAttrs Attr;
243  auto Itr = AttrMap.find(V);
244  if (Itr != AttrMap.end())
245  Attr = Itr->second;
246  return Attr;
247  }
248 
249  iterator_range<const_iterator> mappings() const {
250  return make_range<const_iterator>(AttrMap.begin(), AttrMap.end());
251  }
252 };
253 
254 struct WorkListItem {
255  InstantiatedValue From;
257  MatchState State;
258 };
259 
260 struct ValueSummary {
261  struct Record {
262  InterfaceValue IValue;
263  unsigned DerefLevel;
264  };
265  SmallVector<Record, 4> FromRecords, ToRecords;
266 };
267 
268 } // end anonymous namespace
269 
270 namespace llvm {
271 
272 // Specialize DenseMapInfo for OffsetValue.
273 template <> struct DenseMapInfo<OffsetValue> {
274  static OffsetValue getEmptyKey() {
275  return OffsetValue{DenseMapInfo<const Value *>::getEmptyKey(),
277  }
278 
279  static OffsetValue getTombstoneKey() {
282  }
283 
284  static unsigned getHashValue(const OffsetValue &OVal) {
286  std::make_pair(OVal.Val, OVal.Offset));
287  }
288 
289  static bool isEqual(const OffsetValue &LHS, const OffsetValue &RHS) {
290  return LHS == RHS;
291  }
292 };
293 
294 // Specialize DenseMapInfo for OffsetInstantiatedValue.
295 template <> struct DenseMapInfo<OffsetInstantiatedValue> {
296  static OffsetInstantiatedValue getEmptyKey() {
297  return OffsetInstantiatedValue{
300  }
301 
302  static OffsetInstantiatedValue getTombstoneKey() {
303  return OffsetInstantiatedValue{
306  }
307 
308  static unsigned getHashValue(const OffsetInstantiatedValue &OVal) {
310  std::make_pair(OVal.IVal, OVal.Offset));
311  }
312 
313  static bool isEqual(const OffsetInstantiatedValue &LHS,
314  const OffsetInstantiatedValue &RHS) {
315  return LHS == RHS;
316  }
317 };
318 
319 } // end namespace llvm
320 
322  /// Map a value to other values that may alias it
323  /// Since the alias relation is symmetric, to save some space we assume values
324  /// are properly ordered: if a and b alias each other, and a < b, then b is in
325  /// AliasMap[a] but not vice versa.
327 
328  /// Map a value to its corresponding AliasAttrs
330 
331  /// Summary of externally visible effects.
332  AliasSummary Summary;
333 
334  Optional<AliasAttrs> getAttrs(const Value *) const;
335 
336 public:
338  const ReachabilitySet &, const AliasAttrMap &);
339 
340  bool mayAlias(const Value *, uint64_t, const Value *, uint64_t) const;
341  const AliasSummary &getAliasSummary() const { return Summary; }
342 };
343 
344 static bool hasReadOnlyState(StateSet Set) {
345  return (Set & StateSet(ReadOnlyStateMask)).any();
346 }
347 
348 static bool hasWriteOnlyState(StateSet Set) {
349  return (Set & StateSet(WriteOnlyStateMask)).any();
350 }
351 
354  const SmallVectorImpl<Value *> &RetVals) {
355  auto Val = IValue.Val;
356 
357  Optional<unsigned> Index;
358  if (auto Arg = dyn_cast<Argument>(Val))
359  Index = Arg->getArgNo() + 1;
360  else if (is_contained(RetVals, Val))
361  Index = 0;
362 
363  if (Index)
364  return InterfaceValue{*Index, IValue.DerefLevel};
365  return None;
366 }
367 
369  const AliasAttrMap &AMap) {
370  for (const auto &Mapping : AMap.mappings()) {
371  auto IVal = Mapping.first;
372 
373  // Insert IVal into the map
374  auto &Attr = AttrMap[IVal.Val];
375  // AttrMap only cares about top-level values
376  if (IVal.DerefLevel == 0)
377  Attr |= Mapping.second;
378  }
379 }
380 
381 static void
382 populateAliasMap(DenseMap<const Value *, std::vector<OffsetValue>> &AliasMap,
383  const ReachabilitySet &ReachSet) {
384  for (const auto &OuterMapping : ReachSet.value_mappings()) {
385  // AliasMap only cares about top-level values
386  if (OuterMapping.first.DerefLevel > 0)
387  continue;
388 
389  auto Val = OuterMapping.first.Val;
390  auto &AliasList = AliasMap[Val];
391  for (const auto &InnerMapping : OuterMapping.second) {
392  // Again, AliasMap only cares about top-level values
393  if (InnerMapping.first.DerefLevel == 0)
394  AliasList.push_back(OffsetValue{InnerMapping.first.Val, UnknownOffset});
395  }
396 
397  // Sort AliasList for faster lookup
398  std::sort(AliasList.begin(), AliasList.end());
399  }
400 }
401 
403  SmallVectorImpl<ExternalRelation> &ExtRelations, const Function &Fn,
404  const SmallVectorImpl<Value *> &RetVals, const ReachabilitySet &ReachSet) {
405  // If a function only returns one of its argument X, then X will be both an
406  // argument and a return value at the same time. This is an edge case that
407  // needs special handling here.
408  for (const auto &Arg : Fn.args()) {
409  if (is_contained(RetVals, &Arg)) {
410  auto ArgVal = InterfaceValue{Arg.getArgNo() + 1, 0};
411  auto RetVal = InterfaceValue{0, 0};
412  ExtRelations.push_back(ExternalRelation{ArgVal, RetVal, 0});
413  }
414  }
415 
416  // Below is the core summary construction logic.
417  // A naive solution of adding only the value aliases that are parameters or
418  // return values in ReachSet to the summary won't work: It is possible that a
419  // parameter P is written into an intermediate value I, and the function
420  // subsequently returns *I. In that case, *I is does not value alias anything
421  // in ReachSet, and the naive solution will miss a summary edge from (P, 1) to
422  // (I, 1).
423  // To account for the aforementioned case, we need to check each non-parameter
424  // and non-return value for the possibility of acting as an intermediate.
425  // 'ValueMap' here records, for each value, which InterfaceValues read from or
426  // write into it. If both the read list and the write list of a given value
427  // are non-empty, we know that a particular value is an intermidate and we
428  // need to add summary edges from the writes to the reads.
430  for (const auto &OuterMapping : ReachSet.value_mappings()) {
431  if (auto Dst = getInterfaceValue(OuterMapping.first, RetVals)) {
432  for (const auto &InnerMapping : OuterMapping.second) {
433  // If Src is a param/return value, we get a same-level assignment.
434  if (auto Src = getInterfaceValue(InnerMapping.first, RetVals)) {
435  // This may happen if both Dst and Src are return values
436  if (*Dst == *Src)
437  continue;
438 
439  if (hasReadOnlyState(InnerMapping.second))
440  ExtRelations.push_back(ExternalRelation{*Dst, *Src, UnknownOffset});
441  // No need to check for WriteOnly state, since ReachSet is symmetric
442  } else {
443  // If Src is not a param/return, add it to ValueMap
444  auto SrcIVal = InnerMapping.first;
445  if (hasReadOnlyState(InnerMapping.second))
446  ValueMap[SrcIVal.Val].FromRecords.push_back(
447  ValueSummary::Record{*Dst, SrcIVal.DerefLevel});
448  if (hasWriteOnlyState(InnerMapping.second))
449  ValueMap[SrcIVal.Val].ToRecords.push_back(
450  ValueSummary::Record{*Dst, SrcIVal.DerefLevel});
451  }
452  }
453  }
454  }
455 
456  for (const auto &Mapping : ValueMap) {
457  for (const auto &FromRecord : Mapping.second.FromRecords) {
458  for (const auto &ToRecord : Mapping.second.ToRecords) {
459  auto ToLevel = ToRecord.DerefLevel;
460  auto FromLevel = FromRecord.DerefLevel;
461  // Same-level assignments should have already been processed by now
462  if (ToLevel == FromLevel)
463  continue;
464 
465  auto SrcIndex = FromRecord.IValue.Index;
466  auto SrcLevel = FromRecord.IValue.DerefLevel;
467  auto DstIndex = ToRecord.IValue.Index;
468  auto DstLevel = ToRecord.IValue.DerefLevel;
469  if (ToLevel > FromLevel)
470  SrcLevel += ToLevel - FromLevel;
471  else
472  DstLevel += FromLevel - ToLevel;
473 
474  ExtRelations.push_back(ExternalRelation{
475  InterfaceValue{SrcIndex, SrcLevel},
476  InterfaceValue{DstIndex, DstLevel}, UnknownOffset});
477  }
478  }
479  }
480 
481  // Remove duplicates in ExtRelations
482  std::sort(ExtRelations.begin(), ExtRelations.end());
483  ExtRelations.erase(std::unique(ExtRelations.begin(), ExtRelations.end()),
484  ExtRelations.end());
485 }
486 
488  SmallVectorImpl<ExternalAttribute> &ExtAttributes, const Function &Fn,
489  const SmallVectorImpl<Value *> &RetVals, const AliasAttrMap &AMap) {
490  for (const auto &Mapping : AMap.mappings()) {
491  if (auto IVal = getInterfaceValue(Mapping.first, RetVals)) {
492  auto Attr = getExternallyVisibleAttrs(Mapping.second);
493  if (Attr.any())
494  ExtAttributes.push_back(ExternalAttribute{*IVal, Attr});
495  }
496  }
497 }
498 
500  const Function &Fn, const SmallVectorImpl<Value *> &RetVals,
501  const ReachabilitySet &ReachSet, const AliasAttrMap &AMap) {
502  populateAttrMap(AttrMap, AMap);
503  populateExternalAttributes(Summary.RetParamAttributes, Fn, RetVals, AMap);
504  populateAliasMap(AliasMap, ReachSet);
505  populateExternalRelations(Summary.RetParamRelations, Fn, RetVals, ReachSet);
506 }
507 
509 CFLAndersAAResult::FunctionInfo::getAttrs(const Value *V) const {
510  assert(V != nullptr);
511 
512  auto Itr = AttrMap.find(V);
513  if (Itr != AttrMap.end())
514  return Itr->second;
515  return None;
516 }
517 
519  uint64_t LHSSize,
520  const Value *RHS,
521  uint64_t RHSSize) 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 UnknownSize
561  if (LHSSize == MemoryLocation::UnknownSize ||
562  RHSSize == MemoryLocation::UnknownSize)
563  return true;
564 
565  for (const auto &OVal : make_range(RangePair)) {
566  // Be conservative about UnknownOffset
567  if (OVal.Offset == UnknownOffset)
568  return true;
569 
570  // We know that LHS aliases (RHS + OVal.Offset) if the control flow
571  // reaches here. The may-alias query essentially becomes integer
572  // range-overlap queries over two ranges [OVal.Offset, OVal.Offset +
573  // LHSSize) and [0, RHSSize).
574 
575  // Try to be conservative on super large offsets
576  if (LLVM_UNLIKELY(LHSSize > INT64_MAX || RHSSize > INT64_MAX))
577  return true;
578 
579  auto LHSStart = OVal.Offset;
580  // FIXME: Do we need to guard against integer overflow?
581  auto LHSEnd = OVal.Offset + static_cast<int64_t>(LHSSize);
582  auto RHSStart = 0;
583  auto RHSEnd = static_cast<int64_t>(RHSSize);
584  if (LHSEnd > RHSStart && LHSStart < RHSEnd)
585  return true;
586  }
587  }
588  }
589 
590  return false;
591 }
592 
594  MatchState State, ReachabilitySet &ReachSet,
595  std::vector<WorkListItem> &WorkList) {
596  if (From == To)
597  return;
598  if (ReachSet.insert(From, To, State))
599  WorkList.push_back(WorkListItem{From, To, State});
600 }
601 
602 static void initializeWorkList(std::vector<WorkListItem> &WorkList,
603  ReachabilitySet &ReachSet,
604  const CFLGraph &Graph) {
605  for (const auto &Mapping : Graph.value_mappings()) {
606  auto Val = Mapping.first;
607  auto &ValueInfo = Mapping.second;
608  assert(ValueInfo.getNumLevels() > 0);
609 
610  // Insert all immediate assignment neighbors to the worklist
611  for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I) {
612  auto Src = InstantiatedValue{Val, I};
613  // If there's an assignment edge from X to Y, it means Y is reachable from
614  // X at S2 and X is reachable from Y at S1
615  for (auto &Edge : ValueInfo.getNodeInfoAtLevel(I).Edges) {
616  propagate(Edge.Other, Src, MatchState::FlowFromReadOnly, ReachSet,
617  WorkList);
618  propagate(Src, Edge.Other, MatchState::FlowToWriteOnly, ReachSet,
619  WorkList);
620  }
621  }
622  }
623 }
624 
626  InstantiatedValue V) {
627  auto NodeBelow = InstantiatedValue{V.Val, V.DerefLevel + 1};
628  if (Graph.getNode(NodeBelow))
629  return NodeBelow;
630  return None;
631 }
632 
633 static void processWorkListItem(const WorkListItem &Item, const CFLGraph &Graph,
634  ReachabilitySet &ReachSet, AliasMemSet &MemSet,
635  std::vector<WorkListItem> &WorkList) {
636  auto FromNode = Item.From;
637  auto ToNode = Item.To;
638 
639  auto NodeInfo = Graph.getNode(ToNode);
640  assert(NodeInfo != nullptr);
641 
642  // TODO: propagate field offsets
643 
644  // FIXME: Here is a neat trick we can do: since both ReachSet and MemSet holds
645  // relations that are symmetric, we could actually cut the storage by half by
646  // sorting FromNode and ToNode before insertion happens.
647 
648  // The newly added value alias pair may pontentially generate more memory
649  // alias pairs. Check for them here.
650  auto FromNodeBelow = getNodeBelow(Graph, FromNode);
651  auto ToNodeBelow = getNodeBelow(Graph, ToNode);
652  if (FromNodeBelow && ToNodeBelow &&
653  MemSet.insert(*FromNodeBelow, *ToNodeBelow)) {
654  propagate(*FromNodeBelow, *ToNodeBelow,
655  MatchState::FlowFromMemAliasNoReadWrite, ReachSet, WorkList);
656  for (const auto &Mapping : ReachSet.reachableValueAliases(*FromNodeBelow)) {
657  auto Src = Mapping.first;
658  auto MemAliasPropagate = [&](MatchState FromState, MatchState ToState) {
659  if (Mapping.second.test(static_cast<size_t>(FromState)))
660  propagate(Src, *ToNodeBelow, ToState, ReachSet, WorkList);
661  };
662 
663  MemAliasPropagate(MatchState::FlowFromReadOnly,
664  MatchState::FlowFromMemAliasReadOnly);
665  MemAliasPropagate(MatchState::FlowToWriteOnly,
666  MatchState::FlowToMemAliasWriteOnly);
667  MemAliasPropagate(MatchState::FlowToReadWrite,
668  MatchState::FlowToMemAliasReadWrite);
669  }
670  }
671 
672  // This is the core of the state machine walking algorithm. We expand ReachSet
673  // based on which state we are at (which in turn dictates what edges we
674  // should examine)
675  // From a high-level point of view, the state machine here guarantees two
676  // properties:
677  // - If *X and *Y are memory aliases, then X and Y are value aliases
678  // - If Y is an alias of X, then reverse assignment edges (if there is any)
679  // should precede any assignment edges on the path from X to Y.
680  auto NextAssignState = [&](MatchState State) {
681  for (const auto &AssignEdge : NodeInfo->Edges)
682  propagate(FromNode, AssignEdge.Other, State, ReachSet, WorkList);
683  };
684  auto NextRevAssignState = [&](MatchState State) {
685  for (const auto &RevAssignEdge : NodeInfo->ReverseEdges)
686  propagate(FromNode, RevAssignEdge.Other, State, ReachSet, WorkList);
687  };
688  auto NextMemState = [&](MatchState State) {
689  if (auto AliasSet = MemSet.getMemoryAliases(ToNode)) {
690  for (const auto &MemAlias : *AliasSet)
691  propagate(FromNode, MemAlias, State, ReachSet, WorkList);
692  }
693  };
694 
695  switch (Item.State) {
696  case MatchState::FlowFromReadOnly:
697  NextRevAssignState(MatchState::FlowFromReadOnly);
698  NextAssignState(MatchState::FlowToReadWrite);
699  NextMemState(MatchState::FlowFromMemAliasReadOnly);
700  break;
701 
702  case MatchState::FlowFromMemAliasNoReadWrite:
703  NextRevAssignState(MatchState::FlowFromReadOnly);
704  NextAssignState(MatchState::FlowToWriteOnly);
705  break;
706 
707  case MatchState::FlowFromMemAliasReadOnly:
708  NextRevAssignState(MatchState::FlowFromReadOnly);
709  NextAssignState(MatchState::FlowToReadWrite);
710  break;
711 
712  case MatchState::FlowToWriteOnly:
713  NextAssignState(MatchState::FlowToWriteOnly);
714  NextMemState(MatchState::FlowToMemAliasWriteOnly);
715  break;
716 
717  case MatchState::FlowToReadWrite:
718  NextAssignState(MatchState::FlowToReadWrite);
719  NextMemState(MatchState::FlowToMemAliasReadWrite);
720  break;
721 
722  case MatchState::FlowToMemAliasWriteOnly:
723  NextAssignState(MatchState::FlowToWriteOnly);
724  break;
725 
726  case MatchState::FlowToMemAliasReadWrite:
727  NextAssignState(MatchState::FlowToReadWrite);
728  break;
729  }
730 }
731 
732 static AliasAttrMap buildAttrMap(const CFLGraph &Graph,
733  const ReachabilitySet &ReachSet) {
734  AliasAttrMap AttrMap;
735  std::vector<InstantiatedValue> WorkList, NextList;
736 
737  // Initialize each node with its original AliasAttrs in CFLGraph
738  for (const auto &Mapping : Graph.value_mappings()) {
739  auto Val = Mapping.first;
740  auto &ValueInfo = Mapping.second;
741  for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I) {
742  auto Node = InstantiatedValue{Val, I};
743  AttrMap.add(Node, ValueInfo.getNodeInfoAtLevel(I).Attr);
744  WorkList.push_back(Node);
745  }
746  }
747 
748  while (!WorkList.empty()) {
749  for (const auto &Dst : WorkList) {
750  auto DstAttr = AttrMap.getAttrs(Dst);
751  if (DstAttr.none())
752  continue;
753 
754  // Propagate attr on the same level
755  for (const auto &Mapping : ReachSet.reachableValueAliases(Dst)) {
756  auto Src = Mapping.first;
757  if (AttrMap.add(Src, DstAttr))
758  NextList.push_back(Src);
759  }
760 
761  // Propagate attr to the levels below
762  auto DstBelow = getNodeBelow(Graph, Dst);
763  while (DstBelow) {
764  if (AttrMap.add(*DstBelow, DstAttr)) {
765  NextList.push_back(*DstBelow);
766  break;
767  }
768  DstBelow = getNodeBelow(Graph, *DstBelow);
769  }
770  }
771  WorkList.swap(NextList);
772  NextList.clear();
773  }
774 
775  return AttrMap;
776 }
777 
779 CFLAndersAAResult::buildInfoFrom(const Function &Fn) {
781  *this, TLI,
782  // Cast away the constness here due to GraphBuilder's API requirement
783  const_cast<Function &>(Fn));
784  auto &Graph = GraphBuilder.getCFLGraph();
785 
786  ReachabilitySet ReachSet;
787  AliasMemSet MemSet;
788 
789  std::vector<WorkListItem> WorkList, NextList;
790  initializeWorkList(WorkList, ReachSet, Graph);
791  // TODO: make sure we don't stop before the fix point is reached
792  while (!WorkList.empty()) {
793  for (const auto &Item : WorkList)
794  processWorkListItem(Item, Graph, ReachSet, MemSet, NextList);
795 
796  NextList.swap(WorkList);
797  NextList.clear();
798  }
799 
800  // Now that we have all the reachability info, propagate AliasAttrs according
801  // to it
802  auto IValueAttrMap = buildAttrMap(Graph, ReachSet);
803 
804  return FunctionInfo(Fn, GraphBuilder.getReturnValues(), ReachSet,
805  std::move(IValueAttrMap));
806 }
807 
808 void CFLAndersAAResult::scan(const Function &Fn) {
809  auto InsertPair = Cache.insert(std::make_pair(&Fn, Optional<FunctionInfo>()));
810  (void)InsertPair;
811  assert(InsertPair.second &&
812  "Trying to scan a function that has already been cached");
813 
814  // Note that we can't do Cache[Fn] = buildSetsFrom(Fn) here: the function call
815  // may get evaluated after operator[], potentially triggering a DenseMap
816  // resize and invalidating the reference returned by operator[]
817  auto FunInfo = buildInfoFrom(Fn);
818  Cache[&Fn] = std::move(FunInfo);
819  Handles.emplace_front(const_cast<Function *>(&Fn), this);
820 }
821 
822 void CFLAndersAAResult::evict(const Function *Fn) { Cache.erase(Fn); }
823 
825 CFLAndersAAResult::ensureCached(const Function &Fn) {
826  auto Iter = Cache.find(&Fn);
827  if (Iter == Cache.end()) {
828  scan(Fn);
829  Iter = Cache.find(&Fn);
830  assert(Iter != Cache.end());
831  assert(Iter->second.hasValue());
832  }
833  return Iter->second;
834 }
835 
837  auto &FunInfo = ensureCached(Fn);
838  if (FunInfo.hasValue())
839  return &FunInfo->getAliasSummary();
840  else
841  return nullptr;
842 }
843 
845  const MemoryLocation &LocB) {
846  auto *ValA = LocA.Ptr;
847  auto *ValB = LocB.Ptr;
848 
849  if (!ValA->getType()->isPointerTy() || !ValB->getType()->isPointerTy())
850  return NoAlias;
851 
852  auto *Fn = parentFunctionOfValue(ValA);
853  if (!Fn) {
854  Fn = parentFunctionOfValue(ValB);
855  if (!Fn) {
856  // The only times this is known to happen are when globals + InlineAsm are
857  // involved
858  DEBUG(dbgs()
859  << "CFLAndersAA: could not extract parent function information.\n");
860  return MayAlias;
861  }
862  } else {
863  assert(!parentFunctionOfValue(ValB) || parentFunctionOfValue(ValB) == Fn);
864  }
865 
866  assert(Fn != nullptr);
867  auto &FunInfo = ensureCached(*Fn);
868 
869  // AliasMap lookup
870  if (FunInfo->mayAlias(ValA, LocA.Size, ValB, LocB.Size))
871  return MayAlias;
872  return NoAlias;
873 }
874 
876  const MemoryLocation &LocB) {
877  if (LocA.Ptr == LocB.Ptr)
878  return MustAlias;
879 
880  // Comparisons between global variables and other constants should be
881  // handled by BasicAA.
882  // CFLAndersAA may report NoAlias when comparing a GlobalValue and
883  // ConstantExpr, but every query needs to have at least one Value tied to a
884  // Function, and neither GlobalValues nor ConstantExprs are.
885  if (isa<Constant>(LocA.Ptr) && isa<Constant>(LocB.Ptr))
886  return AAResultBase::alias(LocA, LocB);
887 
888  AliasResult QueryResult = query(LocA, LocB);
889  if (QueryResult == MayAlias)
890  return AAResultBase::alias(LocA, LocB);
891 
892  return QueryResult;
893 }
894 
895 AnalysisKey CFLAndersAA::Key;
896 
899 }
900 
903  "Inclusion-Based CFL Alias Analysis", false, true)
904 
906  return new CFLAndersAAWrapperPass();
907 }
908 
911 }
912 
914  auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>();
915  Result.reset(new CFLAndersAAResult(TLIWP.getTLI()));
916 }
917 
919  AU.setPreservesAll();
921 }
The two locations precisely alias each other.
Definition: AliasAnalysis.h:91
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:687
This is the interface for LLVM&#39;s inclusion-based alias analysis implemented with CFL graph reachabili...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
We use ExternalRelation to describe an externally visible aliasing relations between parameters/retur...
static void populateAliasMap(DenseMap< const Value *, std::vector< OffsetValue >> &AliasMap, const ReachabilitySet &ReachSet)
static bool mayAlias(MachineInstr &MIa, MachineInstr &MIb, AliasAnalysis *AA)
#define LLVM_UNLIKELY(EXPR)
Definition: Compiler.h:176
Implements a dense probed hash-table based set.
Definition: DenseSet.h:221
This is the result of instantiating InterfaceValue at a particular callsite.
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
void initializeCFLAndersAAWrapperPassPass(PassRegistry &)
void initializePass() override
initializePass - This method may be overriden by immutable passes to allow them to perform various in...
The Program Expression Graph (PEG) of CFL analysis CFLGraph is auxiliary data structure used by CFL-b...
Definition: CFLGraph.h:59
The two locations do not alias at all.
Definition: AliasAnalysis.h:85
F(f)
The two locations may or may not alias. This is the least precise result.
Definition: AliasAnalysis.h:87
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...
AnalysisUsage & addRequired()
Definition: BitVector.h:920
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)
CFLAndersAAResult(const TargetLibraryInfo &TLI)
const cflaa::AliasSummary * getAliasSummary(const Function &)
Get the alias summary for the given function Return nullptr if the summary is not found or not availa...
A CRTP-driven "mixin" base class to help implement the function alias analysis results concept...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
static bool isEqual(const OffsetInstantiatedValue &LHS, const OffsetInstantiatedValue &RHS)
static unsigned getHashValue(const OffsetInstantiatedValue &OVal)
AliasResult query(const MemoryLocation &, const MemoryLocation &)
bool mayAlias(const Value *, uint64_t, const Value *, uint64_t) const
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:116
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)
AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:79
Represent the analysis usage information of a pass.
const SmallVector< Value *, 4 > & getReturnValues() const
Definition: CFLGraph.h:663
bool isGlobalOrArgAttr(AliasAttrs Attr)
iterator erase(const_iterator CI)
Definition: SmallVector.h:449
Struct that holds a reference to a particular GUID in a global value summary.
const Value * Ptr
The address of the start of the location.
Representation for a specific memory location.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
See the file comment.
Definition: ValueMap.h:86
ImmutablePass class - This class is used to provide information that does not need to be run...
Definition: Pass.h:256
static void initializeWorkList(std::vector< WorkListItem > &WorkList, ReachabilitySet &ReachSet, const CFLGraph &Graph)
INITIALIZE_PASS(CFLAndersAAWrapperPass, "cfl-anders-aa", "Inclusion-Based CFL Alias Analysis", false, true) ImmutablePass *llvm
AliasAttrs getExternallyVisibleAttrs(AliasAttrs Attr)
Given an AliasAttrs, return a new AliasAttrs that only contains attributes meaningful to the caller...
A builder class used to create CFLGraph instance from a given function The CFL-AA that uses this buil...
Definition: CFLGraph.h:165
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
Provides information about what library functions are available for the current target.
iterator_range< const_value_iterator > value_mappings() const
Definition: CFLGraph.h:151
Alias summary information.
This file defines various utility types and functions useful to summary-based alias analysis...
static Optional< InterfaceValue > getInterfaceValue(InstantiatedValue IValue, const SmallVectorImpl< Value *> &RetVals)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp: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)
amdgpu Simplify well known AMD library false Value Value * Arg
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:120
static const int64_t UnknownOffset
This file provides utility analysis objects describing memory locations.
#define I(x, y, z)
Definition: MD5.cpp:58
static Optional< InstantiatedValue > getNodeBelow(const CFLGraph &Graph, InstantiatedValue V)
static void processWorkListItem(const WorkListItem &Item, const CFLGraph &Graph, ReachabilitySet &ReachSet, AliasMemSet &MemSet, std::vector< WorkListItem > &WorkList)
bool hasUnknownOrCallerAttr(AliasAttrs Attr)
std::bitset< NumAliasAttrs > AliasAttrs
These are attributes that an alias analysis can use to mark certain special properties of a given poi...
static bool hasReadOnlyState(StateSet Set)
const AliasSummary & getAliasSummary() const
Analysis pass providing the TargetLibraryInfo.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
CFLAndersAAResult run(Function &F, FunctionAnalysisManager &AM)
static const Function * parentFunctionOfValue(const Value *Val)
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:326
LLVM Value Representation.
Definition: Value.h:73
const CFLGraph & getCFLGraph() const
Definition: CFLGraph.h:662
#define DEBUG(X)
Definition: Debug.h:118
A container for analyses that lazily runs them and caches their results.
AliasResult alias(const MemoryLocation &, const MemoryLocation &)
void sort(Policy policy, RandomAccessIterator Start, RandomAccessIterator End, const Comparator &Comp=Comparator())
Definition: Parallel.h:199
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1946
ImmutablePass * createCFLAndersAAWrapperPass()
static unsigned getHashValue(const OffsetValue &OVal)
This header defines various interfaces for pass management in LLVM.
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:621
uint64_t Size
The maximum size of the location, in address-units, or UnknownSize if the size is not known...
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:821