LLVM  10.0.0svn
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_IR_CFGDIFF_H
15 #define LLVM_IR_CFGDIFF_H
16 
17 #include "llvm/ADT/GraphTraits.h"
18 #include "llvm/ADT/iterator.h"
20 #include "llvm/IR/BasicBlock.h"
21 #include "llvm/IR/CFG.h"
22 #include "llvm/Support/CFGUpdate.h"
24 #include <cassert>
25 #include <cstddef>
26 #include <iterator>
27 
28 // Two booleans are used to define orders in graphs:
29 // InverseGraph defines when we need to reverse the whole graph and is as such
30 // also equivalent to applying updates in reverse.
31 // InverseEdge defines whether we want to change the edges direction. E.g., for
32 // a non-inversed graph, the children are naturally the successors when
33 // InverseEdge is false and the predecessors when InverseEdge is true.
34 
35 // We define two base clases that call into GraphDiff, one for successors
36 // (CFGSuccessors), where InverseEdge is false, and one for predecessors
37 // (CFGPredecessors), where InverseEdge is true.
38 // FIXME: Further refactoring may merge the two base classes into a single one
39 // templated / parametrized on using succ_iterator/pred_iterator and false/true
40 // for the InverseEdge.
41 
42 // CFGViewSuccessors and CFGViewPredecessors, both can be parametrized to
43 // consider the graph inverted or not (i.e. InverseGraph). Successors
44 // implicitly has InverseEdge = false and Predecessors implicitly has
45 // InverseEdge = true (see calls to GraphDiff methods in there). The GraphTraits
46 // instantiations that follow define the value of InverseGraph.
47 
48 // GraphTraits instantiations:
49 // - GraphDiff<BasicBlock *> is equivalent to InverseGraph = false
50 // - GraphDiff<Inverse<BasicBlock *>> is equivalent to InverseGraph = true
51 // - second pair item is BasicBlock *, then InverseEdge = false (so it inherits
52 // from CFGViewSuccessors).
53 // - second pair item is Inverse<BasicBlock *>, then InverseEdge = true (so it
54 // inherits from CFGViewPredecessors).
55 
56 // The 4 GraphTraits are as follows:
57 // 1. std::pair<const GraphDiff<BasicBlock *> *, BasicBlock *>> :
58 // CFGViewSuccessors<false>
59 // Regular CFG, children means successors, InverseGraph = false,
60 // InverseEdge = false.
61 // 2. std::pair<const GraphDiff<Inverse<BasicBlock *>> *, BasicBlock *>> :
62 // CFGViewSuccessors<true>
63 // Reverse the graph, get successors but reverse-apply updates,
64 // InverseGraph = true, InverseEdge = false.
65 // 3. std::pair<const GraphDiff<BasicBlock *> *, Inverse<BasicBlock *>>> :
66 // CFGViewPredecessors<false>
67 // Regular CFG, reverse edges, so children mean predecessors,
68 // InverseGraph = false, InverseEdge = true.
69 // 4. std::pair<const GraphDiff<Inverse<BasicBlock *>> *, Inverse<BasicBlock *>>
70 // : CFGViewPredecessors<true>
71 // Reverse the graph and the edges, InverseGraph = true, InverseEdge = true.
72 
73 namespace llvm {
74 
75 // GraphDiff defines a CFG snapshot: given a set of Update<NodePtr>, provide
76 // utilities to skip edges marked as deleted and return a set of edges marked as
77 // newly inserted. The current diff treats the CFG as a graph rather than a
78 // multigraph. Added edges are pruned to be unique, and deleted edges will
79 // remove all existing edges between two blocks.
80 template <typename NodePtr, bool InverseGraph = false> class GraphDiff {
82  UpdateMapType SuccInsert;
83  UpdateMapType SuccDelete;
84  UpdateMapType PredInsert;
85  UpdateMapType PredDelete;
86  // Using a singleton empty vector for all BasicBlock requests with no
87  // children.
89 
90  void printMap(raw_ostream &OS, const UpdateMapType &M) const {
91  for (auto Pair : M)
92  for (auto Child : Pair.second) {
93  OS << "(";
94  Pair.first->printAsOperand(OS, false);
95  OS << ", ";
96  Child->printAsOperand(OS, false);
97  OS << ") ";
98  }
99  OS << "\n";
100  }
101 
102 public:
105  SmallVector<cfg::Update<NodePtr>, 4> LegalizedUpdates;
106  cfg::LegalizeUpdates<NodePtr>(Updates, LegalizedUpdates, InverseGraph);
107  for (auto U : LegalizedUpdates) {
108  if (U.getKind() == cfg::UpdateKind::Insert) {
109  SuccInsert[U.getFrom()].push_back(U.getTo());
110  PredInsert[U.getTo()].push_back(U.getFrom());
111  } else {
112  SuccDelete[U.getFrom()].push_back(U.getTo());
113  PredDelete[U.getTo()].push_back(U.getFrom());
114  }
115  }
116  }
117 
118  bool ignoreChild(const NodePtr BB, NodePtr EdgeEnd, bool InverseEdge) const {
119  auto &DeleteChildren =
120  (InverseEdge != InverseGraph) ? PredDelete : SuccDelete;
121  auto It = DeleteChildren.find(BB);
122  if (It == DeleteChildren.end())
123  return false;
124  auto &EdgesForBB = It->second;
125  return llvm::find(EdgesForBB, EdgeEnd) != EdgesForBB.end();
126  }
127 
129  getAddedChildren(const NodePtr BB, bool InverseEdge) const {
130  auto &InsertChildren =
131  (InverseEdge != InverseGraph) ? PredInsert : SuccInsert;
132  auto It = InsertChildren.find(BB);
133  if (It == InsertChildren.end())
134  return make_range(Empty.begin(), Empty.end());
135  return make_range(It->second.begin(), It->second.end());
136  }
137 
138  void print(raw_ostream &OS) const {
139  OS << "===== GraphDiff: CFG edge changes to create a CFG snapshot. \n"
140  "===== (Note: notion of children/inverse_children depends on "
141  "the direction of edges and the graph.)\n";
142  OS << "Children to insert:\n\t";
143  printMap(OS, SuccInsert);
144  OS << "Children to delete:\n\t";
145  printMap(OS, SuccDelete);
146  OS << "Inverse_children to insert:\n\t";
147  printMap(OS, PredInsert);
148  OS << "Inverse_children to delete:\n\t";
149  printMap(OS, PredDelete);
150  OS << "\n";
151  }
152 
153 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
154  LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
155 #endif
156 };
157 
158 template <bool InverseGraph = false> struct CFGViewSuccessors {
160  using NodeRef = std::pair<DataRef, BasicBlock *>;
161 
162  using ExistingChildIterator =
167  bool operator()(NodeRef N) const {
168  return !N.first->ignoreChild(BB, N.second, false);
169  }
170  };
173 
175  using AddNewChildrenIterator =
177  using ChildIteratorType =
180 
181  static ChildIteratorType child_begin(NodeRef N) {
182  auto InsertVec = N.first->getAddedChildren(N.second, false);
183  // filter iterator init:
184  auto firstit = make_filter_range(
185  make_range<ExistingChildIterator>({succ_begin(N.second), N.first},
186  {succ_end(N.second), N.first}),
187  DeletedEdgesFilter(N.second));
188  // new inserts iterator init:
189  auto secondit = make_range<AddNewChildrenIterator>(
190  {InsertVec.begin(), N.first}, {InsertVec.end(), N.first});
191 
192  return concat_iterator<NodeRef, FilterExistingChildrenIterator,
193  AddNewChildrenIterator>(firstit, secondit);
194  }
195 
196  static ChildIteratorType child_end(NodeRef N) {
197  auto InsertVec = N.first->getAddedChildren(N.second, false);
198  // filter iterator init:
199  auto firstit = make_filter_range(
200  make_range<ExistingChildIterator>({succ_end(N.second), N.first},
201  {succ_end(N.second), N.first}),
202  DeletedEdgesFilter(N.second));
203  // new inserts iterator init:
204  auto secondit = make_range<AddNewChildrenIterator>(
205  {InsertVec.end(), N.first}, {InsertVec.end(), N.first});
206 
207  return concat_iterator<NodeRef, FilterExistingChildrenIterator,
208  AddNewChildrenIterator>(firstit, secondit);
209  }
210 };
211 
212 template <bool InverseGraph = false> struct CFGViewPredecessors {
214  using NodeRef = std::pair<DataRef, BasicBlock *>;
215 
216  using ExistingChildIterator =
221  bool operator()(NodeRef N) const {
222  return !N.first->ignoreChild(BB, N.second, true);
223  }
224  };
227 
229  using AddNewChildrenIterator =
231  using ChildIteratorType =
233  AddNewChildrenIterator>;
234 
235  static ChildIteratorType child_begin(NodeRef N) {
236  auto InsertVec = N.first->getAddedChildren(N.second, true);
237  // filter iterator init:
238  auto firstit = make_filter_range(
239  make_range<ExistingChildIterator>({pred_begin(N.second), N.first},
240  {pred_end(N.second), N.first}),
241  DeletedEdgesFilter(N.second));
242  // new inserts iterator init:
243  auto secondit = make_range<AddNewChildrenIterator>(
244  {InsertVec.begin(), N.first}, {InsertVec.end(), N.first});
245 
246  return concat_iterator<NodeRef, FilterExistingChildrenIterator,
247  AddNewChildrenIterator>(firstit, secondit);
248  }
249 
250  static ChildIteratorType child_end(NodeRef N) {
251  auto InsertVec = N.first->getAddedChildren(N.second, true);
252  // filter iterator init:
253  auto firstit = make_filter_range(
254  make_range<ExistingChildIterator>({pred_end(N.second), N.first},
255  {pred_end(N.second), N.first}),
256  DeletedEdgesFilter(N.second));
257  // new inserts iterator init:
258  auto secondit = make_range<AddNewChildrenIterator>(
259  {InsertVec.end(), N.first}, {InsertVec.end(), N.first});
260 
261  return concat_iterator<NodeRef, FilterExistingChildrenIterator,
262  AddNewChildrenIterator>(firstit, secondit);
263  }
264 };
265 
266 template <>
267 struct GraphTraits<
268  std::pair<const GraphDiff<BasicBlock *, false> *, BasicBlock *>>
269  : CFGViewSuccessors<false> {};
270 template <>
271 struct GraphTraits<
272  std::pair<const GraphDiff<BasicBlock *, true> *, BasicBlock *>>
273  : CFGViewSuccessors<true> {};
274 template <>
275 struct GraphTraits<
276  std::pair<const GraphDiff<BasicBlock *, false> *, Inverse<BasicBlock *>>>
277  : CFGViewPredecessors<false> {};
278 template <>
279 struct GraphTraits<
280  std::pair<const GraphDiff<BasicBlock *, true> *, Inverse<BasicBlock *>>>
281  : CFGViewPredecessors<true> {};
282 } // end namespace llvm
283 
284 #endif // LLVM_IR_CFGDIFF_H
This class represents lattice values for constants.
Definition: AllocatorList.h:23
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:473
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
static ChildIteratorType child_begin(NodeRef N)
Definition: CFGDiff.h:235
std::pair< DataRef, BasicBlock *> NodeRef
Definition: CFGDiff.h:214
static ChildIteratorType child_begin(NodeRef N)
Definition: CFGDiff.h:181
Definition: BitVector.h:937
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
LLVM_DUMP_METHOD void dump() const
Definition: CFGDiff.h:154
bool ignoreChild(const NodePtr BB, NodePtr EdgeEnd, bool InverseEdge) const
Definition: CFGDiff.h:118
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:102
std::pair< DataRef, BasicBlock *> NodeRef
Definition: CFGDiff.h:160
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:105
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:176
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:112
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:115
void print(raw_ostream &OS) const
Definition: CFGDiff.h:138
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1198
static ChildIteratorType child_end(NodeRef N)
Definition: CFGDiff.h:196
static ChildIteratorType child_end(NodeRef N)
Definition: CFGDiff.h:250
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
GraphDiff(ArrayRef< cfg::Update< NodePtr >> Updates)
Definition: CFGDiff.h:104
SmallVectorImpl< BasicBlock *>::const_iterator vec_iterator
Definition: CFGDiff.h:174
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.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
#define N
iterator_range< filter_iterator< detail::IterOfRange< RangeT >, PredicateT > > make_filter_range(RangeT &&Range, PredicateT Pred)
Convenience function that takes a range of elements and a predicate, and return a new filter_iterator...
Definition: STLExtras.h:434
iterator_range< typename SmallVectorImpl< NodePtr >::const_iterator > getAddedChildren(const NodePtr BB, bool InverseEdge) const
Definition: CFGDiff.h:129
SmallVectorImpl< BasicBlock *>::const_iterator vec_iterator
Definition: CFGDiff.h:228
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
Specialization of filter_iterator_base for forward iteration only.
Definition: STLExtras.h:360
Iterator wrapper that concatenates sequences together.
Definition: STLExtras.h:824