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" |
19 | #include "llvm/ADT/iterator_range.h" |
20 | #include "llvm/Support/CFGUpdate.h" |
21 | #include "llvm/Support/type_traits.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 { |
59 | SmallVector<NodePtr, 2> DI[2]; |
60 | }; |
61 | using UpdateMapType = SmallDenseMap<NodePtr, DeletesInserts>; |
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) {} |
95 | GraphDiff(ArrayRef<cfg::Update<NodePtr>> Updates, |
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 | |
113 | cfg::Update<NodePtr> () { |
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 | |
134 | using VectRet = SmallVector<NodePtr, 8>; |
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(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(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, M: Succ); |
166 | OS << "Inverse_children to delete/insert:\n\t" ; |
167 | printMap(OS, M: Pred); |
168 | OS << "\n" ; |
169 | } |
170 | |
171 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
172 | LLVM_DUMP_METHOD void dump() const { print(OS&: dbgs()); } |
173 | #endif |
174 | }; |
175 | } // end namespace llvm |
176 | |
177 | #endif // LLVM_SUPPORT_CFGDIFF_H |
178 | |