LLVM: include/llvm/Support/CFGDiff.h Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
14#ifndef LLVM_SUPPORT_CFGDIFF_H
15#define LLVM_SUPPORT_CFGDIFF_H
16
22#include
23#include
24
25
26
27
28
29
30
31
32namespace llvm {
33
35template
37 return std::forward(R);
38}
39
40template
44
48}
49
50
51
52
53
54
55template <typename NodePtr, bool InverseGraph = false> class GraphDiff {
56 struct DeletesInserts {
58 };
60 UpdateMapType Succ;
61 UpdateMapType Pred;
62
63
64
65
66
67 bool UpdatedAreReverseApplied;
68
69
70
71
73
74 void printMap(raw_ostream &OS, const UpdateMapType &M) const {
75 StringRef DIText[2] = {"Delete", "Insert"};
76 for (auto Pair : M) {
77 for (unsigned IsInsert = 0; IsInsert <= 1; ++IsInsert) {
78 OS << DIText[IsInsert] << " edges: \n";
79 for (auto Child : Pair.second.DI[IsInsert]) {
80 OS << "(";
81 Pair.first->printAsOperand(OS, false);
82 OS << ", ";
83 Child->printAsOperand(OS, false);
84 OS << ") ";
85 }
86 }
87 }
88 OS << "\n";
89 }
90
91public:
94 bool ReverseApplyUpdates = false) {
96 for (auto U : LegalizedUpdates) {
97 unsigned IsInsert =
99 Succ[U.getFrom()].DI[IsInsert].push_back(U.getTo());
100 Pred[U.getTo()].DI[IsInsert].push_back(U.getFrom());
101 }
102 UpdatedAreReverseApplied = ReverseApplyUpdates;
103 }
104
106 return make_range(LegalizedUpdates.begin(), LegalizedUpdates.end());
107 }
108
110
112 assert(!LegalizedUpdates.empty() && "No updates to apply!");
113 auto U = LegalizedUpdates.pop_back_val();
114 unsigned IsInsert =
116 auto &SuccDIList = Succ[U.getFrom()];
117 auto &SuccList = SuccDIList.DI[IsInsert];
118 assert(SuccList.back() == U.getTo());
119 SuccList.pop_back();
120 if (SuccList.empty() && SuccDIList.DI[!IsInsert].empty())
121 Succ.erase(U.getFrom());
122
123 auto &PredDIList = Pred[U.getTo()];
124 auto &PredList = PredDIList.DI[IsInsert];
125 assert(PredList.back() == U.getFrom());
126 PredList.pop_back();
127 if (PredList.empty() && PredDIList.DI[!IsInsert].empty())
128 Pred.erase(U.getTo());
129 return U;
130 }
131
134 using DirectedNodeT =
135 std::conditional_t<InverseEdge, Inverse, NodePtr>;
138
139
141
142 auto &Children = (InverseEdge != InverseGraph) ? Pred : Succ;
143 auto It = Children.find(N);
144 if (It == Children.end())
145 return Res;
146
147
148 for (auto *Child : It->second.DI[0])
150
151
152 auto &AddedChildren = It->second.DI[1];
154
155 return Res;
156 }
157
159 OS << "===== GraphDiff: CFG edge changes to create a CFG snapshot. \n"
160 "===== (Note: notion of children/inverse_children depends on "
161 "the direction of edges and the graph.)\n";
162 OS << "Children to delete/insert:\n\t";
163 printMap(OS, Succ);
164 OS << "Inverse_children to delete/insert:\n\t";
165 printMap(OS, Pred);
166 OS << "\n";
167 }
168
169#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
171#endif
172};
173}
174
175#endif
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This file defines the little GraphTraits template class that should be specialized by classes that...
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
auto getLegalizedUpdates() const
Definition CFGDiff.h:105
SmallVector< MachineBasicBlock *, 8 > VectRet
Definition CFGDiff.h:132
void print(raw_ostream &OS) const
Definition CFGDiff.h:158
LLVM_DUMP_METHOD void dump() const
Definition CFGDiff.h:170
GraphDiff()
Definition CFGDiff.h:92
VectRet getChildren(NodePtr N) const
Definition CFGDiff.h:133
GraphDiff(ArrayRef< cfg::Update< NodePtr > > Updates, bool ReverseApplyUpdates=false)
Definition CFGDiff.h:93
cfg::Update< NodePtr > popUpdateForIncrementalUpdates()
Definition CFGDiff.h:111
unsigned getNumLegalizedUpdates() const
Definition CFGDiff.h:109
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
This class implements an extremely fast bulk output stream that can only output to a stream.
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
void LegalizeUpdates(ArrayRef< Update< NodePtr > > AllUpdates, SmallVectorImpl< Update< NodePtr > > &Result, bool InverseGraph, bool ReverseResultOrder=false)
A self-contained host- and target-independent arbitrary-precision floating-point software implementat...
auto reverse_if(Range &&R)
Definition CFGDiff.h:45
auto reverse_if_helper(Range &&R, std::bool_constant< false >)
Definition CFGDiff.h:36
This is an optimization pass for GlobalISel generic memory operations.
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.
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
auto reverse(ContainerTy &&C)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)