LLVM  14.0.0git
CFGDiff.h
Go to the documentation of this file.
1 //===- CFGDiff.h - Define a CFG snapshot. -----------------------*- C++ -*-===//
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 defines specializations of GraphTraits that allows generic
10 // algorithms to see a different snapshot of a CFG.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_SUPPORT_CFGDIFF_H
15 #define LLVM_SUPPORT_CFGDIFF_H
16 
17 #include "llvm/ADT/GraphTraits.h"
18 #include "llvm/ADT/iterator.h"
20 #include "llvm/Support/CFGUpdate.h"
22 #include <cassert>
23 #include <cstddef>
24 #include <iterator>
25 
26 // Two booleans are used to define orders in graphs:
27 // InverseGraph defines when we need to reverse the whole graph and is as such
28 // also equivalent to applying updates in reverse.
29 // InverseEdge defines whether we want to change the edges direction. E.g., for
30 // a non-inversed graph, the children are naturally the successors when
31 // InverseEdge is false and the predecessors when InverseEdge is true.
32 
33 namespace llvm {
34 
35 namespace detail {
36 template <typename Range>
37 auto reverse_if_helper(Range &&R, std::integral_constant<bool, false>) {
38  return std::forward<Range>(R);
39 }
40 
41 template <typename Range>
42 auto reverse_if_helper(Range &&R, std::integral_constant<bool, true>) {
43  return llvm::reverse(std::forward<Range>(R));
44 }
45 
46 template <bool B, typename Range> auto reverse_if(Range &&R) {
47  return reverse_if_helper(std::forward<Range>(R),
48  std::integral_constant<bool, B>{});
49 }
50 } // namespace detail
51 
52 // GraphDiff defines a CFG snapshot: given a set of Update<NodePtr>, provides
53 // a getChildren method to get a Node's children based on the additional updates
54 // in the snapshot. The current diff treats the CFG as a graph rather than a
55 // multigraph. Added edges are pruned to be unique, and deleted edges will
56 // remove all existing edges between two blocks.
57 template <typename NodePtr, bool InverseGraph = false> class GraphDiff {
58  struct DeletesInserts {
60  };
62  UpdateMapType Succ;
63  UpdateMapType Pred;
64 
65  // By default, it is assumed that, given a CFG and a set of updates, we wish
66  // to apply these updates as given. If UpdatedAreReverseApplied is set, the
67  // updates will be applied in reverse: deleted edges are considered re-added
68  // and inserted edges are considered deleted when returning children.
69  bool UpdatedAreReverseApplied;
70 
71  // Keep the list of legalized updates for a deterministic order of updates
72  // when using a GraphDiff for incremental updates in the DominatorTree.
73  // The list is kept in reverse to allow popping from end.
74  SmallVector<cfg::Update<NodePtr>, 4> LegalizedUpdates;
75 
76  void printMap(raw_ostream &OS, const UpdateMapType &M) const {
77  StringRef DIText[2] = {"Delete", "Insert"};
78  for (auto Pair : M) {
79  for (unsigned IsInsert = 0; IsInsert <= 1; ++IsInsert) {
80  OS << DIText[IsInsert] << " edges: \n";
81  for (auto Child : Pair.second.DI[IsInsert]) {
82  OS << "(";
83  Pair.first->printAsOperand(OS, false);
84  OS << ", ";
85  Child->printAsOperand(OS, false);
86  OS << ") ";
87  }
88  }
89  }
90  OS << "\n";
91  }
92 
93 public:
94  GraphDiff() : UpdatedAreReverseApplied(false) {}
96  bool ReverseApplyUpdates = false) {
97  cfg::LegalizeUpdates<NodePtr>(Updates, LegalizedUpdates, InverseGraph);
98  for (auto U : LegalizedUpdates) {
99  unsigned IsInsert =
100  (U.getKind() == cfg::UpdateKind::Insert) == !ReverseApplyUpdates;
101  Succ[U.getFrom()].DI[IsInsert].push_back(U.getTo());
102  Pred[U.getTo()].DI[IsInsert].push_back(U.getFrom());
103  }
104  UpdatedAreReverseApplied = ReverseApplyUpdates;
105  }
106 
107  auto getLegalizedUpdates() const {
108  return make_range(LegalizedUpdates.begin(), LegalizedUpdates.end());
109  }
110 
111  unsigned getNumLegalizedUpdates() const { return LegalizedUpdates.size(); }
112 
114  assert(!LegalizedUpdates.empty() && "No updates to apply!");
115  auto U = LegalizedUpdates.pop_back_val();
116  unsigned IsInsert =
117  (U.getKind() == cfg::UpdateKind::Insert) == !UpdatedAreReverseApplied;
118  auto &SuccDIList = Succ[U.getFrom()];
119  auto &SuccList = SuccDIList.DI[IsInsert];
120  assert(SuccList.back() == U.getTo());
121  SuccList.pop_back();
122  if (SuccList.empty() && SuccDIList.DI[!IsInsert].empty())
123  Succ.erase(U.getFrom());
124 
125  auto &PredDIList = Pred[U.getTo()];
126  auto &PredList = PredDIList.DI[IsInsert];
127  assert(PredList.back() == U.getFrom());
128  PredList.pop_back();
129  if (PredList.empty() && PredDIList.DI[!IsInsert].empty())
130  Pred.erase(U.getTo());
131  return U;
132  }
133 
135  template <bool InverseEdge> VectRet getChildren(NodePtr N) const {
136  using DirectedNodeT =
137  std::conditional_t<InverseEdge, Inverse<NodePtr>, NodePtr>;
138  auto R = children<DirectedNodeT>(N);
139  VectRet Res = VectRet(detail::reverse_if<!InverseEdge>(R));
140 
141  // Remove nullptr children for clang.
142  llvm::erase_value(Res, nullptr);
143 
144  auto &Children = (InverseEdge != InverseGraph) ? Pred : Succ;
145  auto It = Children.find(N);
146  if (It == Children.end())
147  return Res;
148 
149  // Remove children present in the CFG but not in the snapshot.
150  for (auto *Child : It->second.DI[0])
151  llvm::erase_value(Res, Child);
152 
153  // Add children present in the snapshot for not in the real CFG.
154  auto &AddedChildren = It->second.DI[1];
155  llvm::append_range(Res, AddedChildren);
156 
157  return Res;
158  }
159 
160  void print(raw_ostream &OS) const {
161  OS << "===== GraphDiff: CFG edge changes to create a CFG snapshot. \n"
162  "===== (Note: notion of children/inverse_children depends on "
163  "the direction of edges and the graph.)\n";
164  OS << "Children to delete/insert:\n\t";
165  printMap(OS, Succ);
166  OS << "Inverse_children to delete/insert:\n\t";
167  printMap(OS, Pred);
168  OS << "\n";
169  }
170 
171 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
172  LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
173 #endif
174 };
175 } // end namespace llvm
176 
177 #endif // LLVM_SUPPORT_CFGDIFF_H
CFGUpdate.h
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:506
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::GraphDiff::GraphDiff
GraphDiff()
Definition: CFGDiff.h:94
llvm::cfg::UpdateKind::Insert
@ Insert
llvm::SmallVector< NodePtr, 2 >
llvm::SmallDenseMap< NodePtr, DeletesInserts >
llvm::DenseMapBase::erase
bool erase(const KeyT &Val)
Definition: DenseMap.h:302
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:359
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
llvm::GraphDiff::print
void print(raw_ostream &OS) const
Definition: CFGDiff.h:160
llvm::detail::reverse_if_helper
auto reverse_if_helper(Range &&R, std::integral_constant< bool, false >)
Definition: CFGDiff.h:37
llvm::GraphDiff
Definition: CFGDiff.h:57
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
GraphTraits.h
false
Definition: StackSlotColoring.cpp:142
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::erase_value
void erase_value(Container &C, ValueType V)
Wrapper function to remove a value from a container:
Definition: STLExtras.h:1789
llvm::GraphDiff::dump
LLVM_DUMP_METHOD void dump() const
Definition: CFGDiff.h:172
iterator.h
llvm::GraphDiff::getLegalizedUpdates
auto getLegalizedUpdates() const
Definition: CFGDiff.h:107
llvm::DenseMapBase::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::GraphDiff::getNumLegalizedUpdates
unsigned getNumLegalizedUpdates() const
Definition: CFGDiff.h:111
iterator_range.h
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1797
type_traits.h
llvm::GraphDiff::getChildren
VectRet getChildren(NodePtr N) const
Definition: CFGDiff.h:135
llvm::GraphDiff::VectRet
SmallVector< NodePtr, 8 > VectRet
Definition: CFGDiff.h:134
llvm::GraphDiff::popUpdateForIncrementalUpdates
cfg::Update< NodePtr > popUpdateForIncrementalUpdates()
Definition: CFGDiff.h:113
N
#define N
llvm::cfg::Update
Definition: CFGUpdate.h:28
llvm::detail::reverse_if
auto reverse_if(Range &&R)
Definition: CFGDiff.h:46
llvm::GraphDiff::GraphDiff
GraphDiff(ArrayRef< cfg::Update< NodePtr >> Updates, bool ReverseApplyUpdates=false)
Definition: CFGDiff.h:95