Line data Source code
1 : //===- CFGDiff.h - Define a CFG snapshot. -----------------------*- C++ -*-===//
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 defines specializations of GraphTraits that allows generic
11 : // algorithms to see a different snapshot of a CFG.
12 : //
13 : //===----------------------------------------------------------------------===//
14 :
15 : #ifndef LLVM_IR_CFGDIFF_H
16 : #define LLVM_IR_CFGDIFF_H
17 :
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"
25 : #include <cassert>
26 : #include <cstddef>
27 : #include <iterator>
28 :
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.
35 :
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.
42 :
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.
48 :
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).
56 :
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.
73 :
74 : namespace llvm {
75 :
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
88 : // children.
89 : SmallVector<NodePtr, 1> Empty;
90 :
91 : void printMap(raw_ostream &OS, const UpdateMapType &M) const {
92 : for (auto Pair : M)
93 : for (auto Child : Pair.second) {
94 : OS << "(";
95 : Pair.first->printAsOperand(OS, false);
96 : OS << ", ";
97 : Child->printAsOperand(OS, false);
98 : OS << ") ";
99 : }
100 : OS << "\n";
101 : }
102 :
103 : public:
104 128 : GraphDiff() {}
105 0 : GraphDiff(ArrayRef<cfg::Update<NodePtr>> Updates) {
106 : SmallVector<cfg::Update<NodePtr>, 4> LegalizedUpdates;
107 0 : cfg::LegalizeUpdates<NodePtr>(Updates, LegalizedUpdates, InverseGraph);
108 0 : for (auto U : LegalizedUpdates) {
109 0 : if (U.getKind() == cfg::UpdateKind::Insert) {
110 0 : SuccInsert[U.getFrom()].push_back(U.getTo());
111 0 : PredInsert[U.getTo()].push_back(U.getFrom());
112 : } else {
113 0 : SuccDelete[U.getFrom()].push_back(U.getTo());
114 0 : PredDelete[U.getTo()].push_back(U.getFrom());
115 : }
116 : }
117 0 : }
118 :
119 9511 : bool ignoreChild(const NodePtr BB, NodePtr EdgeEnd, bool InverseEdge) const {
120 9511 : auto &DeleteChildren =
121 : (InverseEdge != InverseGraph) ? PredDelete : SuccDelete;
122 9511 : auto It = DeleteChildren.find(BB);
123 9511 : if (It == DeleteChildren.end())
124 : return false;
125 : auto &EdgesForBB = It->second;
126 0 : return llvm::find(EdgesForBB, EdgeEnd) != EdgesForBB.end();
127 : }
128 0 :
129 0 : iterator_range<typename SmallVectorImpl<NodePtr>::const_iterator>
130 18274 : getAddedChildren(const NodePtr BB, bool InverseEdge) const {
131 18274 : auto &InsertChildren =
132 0 : (InverseEdge != InverseGraph) ? PredInsert : SuccInsert;
133 18274 : auto It = InsertChildren.find(BB);
134 18274 : if (It == InsertChildren.end())
135 0 : return make_range(Empty.begin(), Empty.end());
136 : return make_range(It->second.begin(), It->second.end());
137 0 : }
138 0 :
139 : void print(raw_ostream &OS) const {
140 0 : OS << "===== GraphDiff: CFG edge changes to create a CFG snapshot. \n"
141 0 : "===== (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 0 : printMap(OS, SuccInsert);
145 : OS << "Children to delete:\n\t";
146 : printMap(OS, SuccDelete);
147 : OS << "Inverse_children to insert:\n\t";
148 0 : printMap(OS, PredInsert);
149 0 : OS << "Inverse_children to delete:\n\t";
150 : printMap(OS, PredDelete);
151 0 : OS << "\n";
152 0 : }
153 :
154 : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
155 : LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
156 0 : #endif
157 0 : };
158 :
159 0 : template <bool InverseGraph = false> struct CFGViewSuccessors {
160 0 : using DataRef = const GraphDiff<BasicBlock *, InverseGraph> *;
161 : using NodeRef = std::pair<DataRef, BasicBlock *>;
162 :
163 : using ExistingChildIterator =
164 0 : WrappedPairNodeDataIterator<succ_iterator, NodeRef, DataRef>;
165 0 : struct DeletedEdgesFilter {
166 : BasicBlock *BB;
167 0 : DeletedEdgesFilter(BasicBlock *BB) : BB(BB){};
168 0 : bool operator()(NodeRef N) const {
169 : return !N.first->ignoreChild(BB, N.second, false);
170 : }
171 : };
172 : using FilterExistingChildrenIterator =
173 : filter_iterator<ExistingChildIterator, DeletedEdgesFilter>;
174 :
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>;
181 :
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});
192 :
193 : return concat_iterator<NodeRef, FilterExistingChildrenIterator,
194 : AddNewChildrenIterator>(firstit, secondit);
195 : }
196 :
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 0 : make_range<ExistingChildIterator>({succ_end(N.second), N.first},
202 0 : {succ_end(N.second), N.first}),
203 0 : DeletedEdgesFilter(N.second));
204 : // new inserts iterator init:
205 : auto secondit = make_range<AddNewChildrenIterator>(
206 : {InsertVec.end(), N.first}, {InsertVec.end(), N.first});
207 :
208 : return concat_iterator<NodeRef, FilterExistingChildrenIterator,
209 : AddNewChildrenIterator>(firstit, secondit);
210 : }
211 : };
212 :
213 : template <bool InverseGraph = false> struct CFGViewPredecessors {
214 : using DataRef = const GraphDiff<BasicBlock *, InverseGraph> *;
215 : using NodeRef = std::pair<DataRef, BasicBlock *>;
216 0 :
217 0 : using ExistingChildIterator =
218 : WrappedPairNodeDataIterator<pred_iterator, NodeRef, DataRef>;
219 0 : struct DeletedEdgesFilter {
220 0 : BasicBlock *BB;
221 9137 : DeletedEdgesFilter(BasicBlock *BB) : BB(BB){};
222 0 : bool operator()(NodeRef N) const {
223 9511 : return !N.first->ignoreChild(BB, N.second, true);
224 0 : }
225 : };
226 : using FilterExistingChildrenIterator =
227 : filter_iterator<ExistingChildIterator, DeletedEdgesFilter>;
228 0 :
229 : using vec_iterator = SmallVectorImpl<BasicBlock *>::const_iterator;
230 : using AddNewChildrenIterator =
231 0 : WrappedPairNodeDataIterator<vec_iterator, NodeRef, DataRef>;
232 0 : using ChildIteratorType =
233 : concat_iterator<NodeRef, FilterExistingChildrenIterator,
234 0 : AddNewChildrenIterator>;
235 0 :
236 9137 : static ChildIteratorType child_begin(NodeRef N) {
237 9137 : auto InsertVec = N.first->getAddedChildren(N.second, true);
238 : // filter iterator init:
239 9137 : auto firstit = make_filter_range(
240 9137 : make_range<ExistingChildIterator>({pred_begin(N.second), N.first},
241 : {pred_end(N.second), N.first}),
242 : DeletedEdgesFilter(N.second));
243 0 : // new inserts iterator init:
244 9137 : auto secondit = make_range<AddNewChildrenIterator>(
245 : {InsertVec.begin(), N.first}, {InsertVec.end(), N.first});
246 :
247 : return concat_iterator<NodeRef, FilterExistingChildrenIterator,
248 9137 : AddNewChildrenIterator>(firstit, secondit);
249 : }
250 :
251 9137 : static ChildIteratorType child_end(NodeRef N) {
252 9137 : auto InsertVec = N.first->getAddedChildren(N.second, true);
253 : // filter iterator init:
254 9137 : auto firstit = make_filter_range(
255 9137 : make_range<ExistingChildIterator>({pred_end(N.second), N.first},
256 0 : {pred_end(N.second), N.first}),
257 0 : DeletedEdgesFilter(N.second));
258 : // new inserts iterator init:
259 : auto secondit = make_range<AddNewChildrenIterator>(
260 : {InsertVec.end(), N.first}, {InsertVec.end(), N.first});
261 :
262 : return concat_iterator<NodeRef, FilterExistingChildrenIterator,
263 9137 : AddNewChildrenIterator>(firstit, secondit);
264 : }
265 : };
266 :
267 : template <>
268 : struct GraphTraits<
269 : std::pair<const GraphDiff<BasicBlock *, false> *, BasicBlock *>>
270 0 : : CFGViewSuccessors<false> {};
271 0 : template <>
272 : struct GraphTraits<
273 0 : std::pair<const GraphDiff<BasicBlock *, true> *, BasicBlock *>>
274 0 : : CFGViewSuccessors<true> {};
275 : template <>
276 : struct GraphTraits<
277 : std::pair<const GraphDiff<BasicBlock *, false> *, Inverse<BasicBlock *>>>
278 0 : : CFGViewPredecessors<false> {};
279 : template <>
280 : struct GraphTraits<
281 : std::pair<const GraphDiff<BasicBlock *, true> *, Inverse<BasicBlock *>>>
282 0 : : CFGViewPredecessors<true> {};
283 : } // end namespace llvm
284 :
285 0 : #endif // LLVM_IR_CFGDIFF_H
|
