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> popUpdateForIncrementalUpdates() {
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, 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
178