LLVM 19.0.0git
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_SUPPORT_CFGDIFF_H
15#define LLVM_SUPPORT_CFGDIFF_H
16
18#include "llvm/ADT/iterator.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
33namespace llvm {
34
35namespace detail {
36template <typename Range>
37auto reverse_if_helper(Range &&R, std::integral_constant<bool, false>) {
38 return std::forward<Range>(R);
39}
40
41template <typename Range>
42auto reverse_if_helper(Range &&R, std::integral_constant<bool, true>) {
43 return llvm::reverse(std::forward<Range>(R));
44}
45
46template <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.
57template <typename NodePtr, bool InverseGraph = false> class GraphDiff {
58 struct DeletesInserts {
60 };
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
93public:
94 GraphDiff() : UpdatedAreReverseApplied(false) {}
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
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
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
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:529
This file defines the little GraphTraits<X> template class that should be specialized by classes that...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
bool erase(const KeyT &Val)
Definition: DenseMap.h:329
auto getLegalizedUpdates() const
Definition: CFGDiff.h:107
SmallVector< NodePtr, 8 > VectRet
Definition: CFGDiff.h:134
void print(raw_ostream &OS) const
Definition: CFGDiff.h:160
LLVM_DUMP_METHOD void dump() const
Definition: CFGDiff.h:172
VectRet getChildren(NodePtr N) const
Definition: CFGDiff.h:135
GraphDiff(ArrayRef< cfg::Update< NodePtr > > Updates, bool ReverseApplyUpdates=false)
Definition: CFGDiff.h:95
cfg::Update< NodePtr > popUpdateForIncrementalUpdates()
Definition: CFGDiff.h:113
unsigned getNumLegalizedUpdates() const
Definition: CFGDiff.h:111
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
auto reverse_if(Range &&R)
Definition: CFGDiff.h:46
auto reverse_if_helper(Range &&R, std::integral_constant< bool, false >)
Definition: CFGDiff.h:37
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
Definition: STLExtras.h:2053
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
Definition: STLExtras.h:2039
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:428
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
#define N