1 //===- CFGDiff.h - Define a CFG snapshot. -----------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines specializations of GraphTraits that allows generic
11 // algorithms to see a different snapshot of a CFG.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_IR_CFGDIFF_H
16 #define LLVM_IR_CFGDIFF_H
18 #include "llvm/ADT/GraphTraits.h"
19 #include "llvm/ADT/iterator.h"
20 #include "llvm/ADT/iterator_range.h"
21 #include "llvm/IR/BasicBlock.h"
22 #include "llvm/IR/CFG.h"
23 #include "llvm/Support/CFGUpdate.h"
24 #include "llvm/Support/type_traits.h"
29 // Two booleans are used to define orders in graphs:
30 // InverseGraph defines when we need to reverse the whole graph and is as such
31 // also equivalent to applying updates in reverse.
32 // InverseEdge defines whether we want to change the edges direction. E.g., for
33 // a non-inversed graph, the children are naturally the successors when
34 // InverseEdge is false and the predecessors when InverseEdge is true.
36 // We define two base clases that call into GraphDiff, one for successors
37 // (CFGSuccessors), where InverseEdge is false, and one for predecessors
38 // (CFGPredecessors), where InverseEdge is true.
39 // FIXME: Further refactoring may merge the two base classes into a single one
40 // templated / parametrized on using succ_iterator/pred_iterator and false/true
41 // for the InverseEdge.
43 // CFGViewSuccessors and CFGViewPredecessors, both can be parametrized to
44 // consider the graph inverted or not (i.e. InverseGraph). Successors
45 // implicitly has InverseEdge = false and Predecessors implicitly has
46 // InverseEdge = true (see calls to GraphDiff methods in there). The GraphTraits
47 // instantiations that follow define the value of InverseGraph.
49 // GraphTraits instantiations:
50 // - GraphDiff<BasicBlock *> is equivalent to InverseGraph = false
51 // - GraphDiff<Inverse<BasicBlock *>> is equivalent to InverseGraph = true
52 // - second pair item is BasicBlock *, then InverseEdge = false (so it inherits
53 // from CFGViewSuccessors).
54 // - second pair item is Inverse<BasicBlock *>, then InverseEdge = true (so it
55 // inherits from CFGViewPredecessors).
57 // The 4 GraphTraits are as follows:
58 // 1. std::pair<const GraphDiff<BasicBlock *> *, BasicBlock *>> :
59 // CFGViewSuccessors<false>
60 // Regular CFG, children means successors, InverseGraph = false,
61 // InverseEdge = false.
62 // 2. std::pair<const GraphDiff<Inverse<BasicBlock *>> *, BasicBlock *>> :
63 // CFGViewSuccessors<true>
64 // Reverse the graph, get successors but reverse-apply updates,
65 // InverseGraph = true, InverseEdge = false.
66 // 3. std::pair<const GraphDiff<BasicBlock *> *, Inverse<BasicBlock *>>> :
67 // CFGViewPredecessors<false>
68 // Regular CFG, reverse edges, so children mean predecessors,
69 // InverseGraph = false, InverseEdge = true.
70 // 4. std::pair<const GraphDiff<Inverse<BasicBlock *>> *, Inverse<BasicBlock *>>
71 // : CFGViewPredecessors<true>
72 // Reverse the graph and the edges, InverseGraph = true, InverseEdge = true.
76 // GraphDiff defines a CFG snapshot: given a set of Update<NodePtr>, provide
77 // utilities to skip edges marked as deleted and return a set of edges marked as
78 // newly inserted. The current diff treats the CFG as a graph rather than a
79 // multigraph. Added edges are pruned to be unique, and deleted edges will
80 // remove all existing edges between two blocks.
81 template <typename NodePtr, bool InverseGraph = false> class GraphDiff {
82 using UpdateMapType = SmallDenseMap<NodePtr, SmallVector<NodePtr, 2>>;
83 UpdateMapType SuccInsert;
84 UpdateMapType SuccDelete;
85 UpdateMapType PredInsert;
86 UpdateMapType PredDelete;
87 // Using a singleton empty vector for all BasicBlock requests with no
89 SmallVector<NodePtr, 1> Empty;
91 void printMap(raw_ostream &OS, const UpdateMapType &M) const {
93 for (auto Child : Pair.second) {
95 Pair.first->printAsOperand(OS, false);
97 Child->printAsOperand(OS, false);
105 GraphDiff(ArrayRef<cfg::Update<NodePtr>> Updates) {
106 SmallVector<cfg::Update<NodePtr>, 4> LegalizedUpdates;
107 cfg::LegalizeUpdates<NodePtr>(Updates, LegalizedUpdates, InverseGraph);
108 for (auto U : LegalizedUpdates) {
109 if (U.getKind() == cfg::UpdateKind::Insert) {
110 SuccInsert[U.getFrom()].push_back(U.getTo());
111 PredInsert[U.getTo()].push_back(U.getFrom());
113 SuccDelete[U.getFrom()].push_back(U.getTo());
114 PredDelete[U.getTo()].push_back(U.getFrom());
119 bool ignoreChild(const NodePtr BB, NodePtr EdgeEnd, bool InverseEdge) const {
120 auto &DeleteChildren =
121 (InverseEdge != InverseGraph) ? PredDelete : SuccDelete;
122 auto It = DeleteChildren.find(BB);
123 if (It == DeleteChildren.end())
125 auto &EdgesForBB = It->second;
126 return llvm::find(EdgesForBB, EdgeEnd) != EdgesForBB.end();
129 iterator_range<typename SmallVectorImpl<NodePtr>::const_iterator>
130 getAddedChildren(const NodePtr BB, bool InverseEdge) const {
131 auto &InsertChildren =
132 (InverseEdge != InverseGraph) ? PredInsert : SuccInsert;
133 auto It = InsertChildren.find(BB);
134 if (It == InsertChildren.end())
135 return make_range(Empty.begin(), Empty.end());
136 return make_range(It->second.begin(), It->second.end());
139 void print(raw_ostream &OS) const {
140 OS << "===== GraphDiff: CFG edge changes to create a CFG snapshot. \n"
141 "===== (Note: notion of children/inverse_children depends on "
142 "the direction of edges and the graph.)\n";
143 OS << "Children to insert:\n\t";
144 printMap(OS, SuccInsert);
145 OS << "Children to delete:\n\t";
146 printMap(OS, SuccDelete);
147 OS << "Inverse_children to insert:\n\t";
148 printMap(OS, PredInsert);
149 OS << "Inverse_children to delete:\n\t";
150 printMap(OS, PredDelete);
154 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
155 LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
159 template <bool InverseGraph = false> struct CFGViewSuccessors {
160 using DataRef = const GraphDiff<BasicBlock *, InverseGraph> *;
161 using NodeRef = std::pair<DataRef, BasicBlock *>;
163 using ExistingChildIterator =
164 WrappedPairNodeDataIterator<succ_iterator, NodeRef, DataRef>;
165 struct DeletedEdgesFilter {
167 DeletedEdgesFilter(BasicBlock *BB) : BB(BB){};
168 bool operator()(NodeRef N) const {
169 return !N.first->ignoreChild(BB, N.second, false);
172 using FilterExistingChildrenIterator =
173 filter_iterator<ExistingChildIterator, DeletedEdgesFilter>;
175 using vec_iterator = SmallVectorImpl<BasicBlock *>::const_iterator;
176 using AddNewChildrenIterator =
177 WrappedPairNodeDataIterator<vec_iterator, NodeRef, DataRef>;
178 using ChildIteratorType =
179 concat_iterator<NodeRef, FilterExistingChildrenIterator,
180 AddNewChildrenIterator>;
182 static ChildIteratorType child_begin(NodeRef N) {
183 auto InsertVec = N.first->getAddedChildren(N.second, false);
184 // filter iterator init:
185 auto firstit = make_filter_range(
186 make_range<ExistingChildIterator>({succ_begin(N.second), N.first},
187 {succ_end(N.second), N.first}),
188 DeletedEdgesFilter(N.second));
189 // new inserts iterator init:
190 auto secondit = make_range<AddNewChildrenIterator>(
191 {InsertVec.begin(), N.first}, {InsertVec.end(), N.first});
193 return concat_iterator<NodeRef, FilterExistingChildrenIterator,
194 AddNewChildrenIterator>(firstit, secondit);
197 static ChildIteratorType child_end(NodeRef N) {
198 auto InsertVec = N.first->getAddedChildren(N.second, false);
199 // filter iterator init:
200 auto firstit = make_filter_range(
201 make_range<ExistingChildIterator>({succ_end(N.second), N.first},
202 {succ_end(N.second), N.first}),
203 DeletedEdgesFilter(N.second));
204 // new inserts iterator init:
205 auto secondit = make_range<AddNewChildrenIterator>(
206 {InsertVec.end(), N.first}, {InsertVec.end(), N.first});
208 return concat_iterator<NodeRef, FilterExistingChildrenIterator,
209 AddNewChildrenIterator>(firstit, secondit);
213 template <bool InverseGraph = false> struct CFGViewPredecessors {
214 using DataRef = const GraphDiff<BasicBlock *, InverseGraph> *;
215 using NodeRef = std::pair<DataRef, BasicBlock *>;
217 using ExistingChildIterator =
218 WrappedPairNodeDataIterator<pred_iterator, NodeRef, DataRef>;
219 struct DeletedEdgesFilter {
221 DeletedEdgesFilter(BasicBlock *BB) : BB(BB){};
222 bool operator()(NodeRef N) const {
223 return !N.first->ignoreChild(BB, N.second, true);
226 using FilterExistingChildrenIterator =
227 filter_iterator<ExistingChildIterator, DeletedEdgesFilter>;
229 using vec_iterator = SmallVectorImpl<BasicBlock *>::const_iterator;
230 using AddNewChildrenIterator =
231 WrappedPairNodeDataIterator<vec_iterator, NodeRef, DataRef>;
232 using ChildIteratorType =
233 concat_iterator<NodeRef, FilterExistingChildrenIterator,
234 AddNewChildrenIterator>;
236 static ChildIteratorType child_begin(NodeRef N) {
237 auto InsertVec = N.first->getAddedChildren(N.second, true);
238 // filter iterator init:
239 auto firstit = make_filter_range(
240 make_range<ExistingChildIterator>({pred_begin(N.second), N.first},
241 {pred_end(N.second), N.first}),
242 DeletedEdgesFilter(N.second));
243 // new inserts iterator init:
244 auto secondit = make_range<AddNewChildrenIterator>(
245 {InsertVec.begin(), N.first}, {InsertVec.end(), N.first});
247 return concat_iterator<NodeRef, FilterExistingChildrenIterator,
248 AddNewChildrenIterator>(firstit, secondit);
251 static ChildIteratorType child_end(NodeRef N) {
252 auto InsertVec = N.first->getAddedChildren(N.second, true);
253 // filter iterator init:
254 auto firstit = make_filter_range(
255 make_range<ExistingChildIterator>({pred_end(N.second), N.first},
256 {pred_end(N.second), N.first}),
257 DeletedEdgesFilter(N.second));
258 // new inserts iterator init:
259 auto secondit = make_range<AddNewChildrenIterator>(
260 {InsertVec.end(), N.first}, {InsertVec.end(), N.first});
262 return concat_iterator<NodeRef, FilterExistingChildrenIterator,
263 AddNewChildrenIterator>(firstit, secondit);
269 std::pair<const GraphDiff<BasicBlock *, false> *, BasicBlock *>>
270 : CFGViewSuccessors<false> {};
273 std::pair<const GraphDiff<BasicBlock *, true> *, BasicBlock *>>
274 : CFGViewSuccessors<true> {};
277 std::pair<const GraphDiff<BasicBlock *, false> *, Inverse<BasicBlock *>>>
278 : CFGViewPredecessors<false> {};
281 std::pair<const GraphDiff<BasicBlock *, true> *, Inverse<BasicBlock *>>>
282 : CFGViewPredecessors<true> {};
283 } // end namespace llvm
285 #endif // LLVM_IR_CFGDIFF_H