44 #define DEBUG_TYPE "dag-delta" 48 class DAGDeltaAlgorithmImpl {
49 friend class DeltaActiveSetHelper;
58 typedef std::vector<change_ty>::iterator pred_iterator_ty;
59 typedef std::vector<change_ty>::iterator succ_iterator_ty;
60 typedef std::set<change_ty>::iterator pred_closure_iterator_ty;
61 typedef std::set<change_ty>::iterator succ_closure_iterator_ty;
65 std::vector<change_ty> Roots;
71 mutable std::set<changeset_ty> FailedTestsCache;
74 std::map<change_ty, std::vector<change_ty> > Predecessors;
75 std::map<change_ty, std::vector<change_ty> > Successors;
77 std::map<change_ty, std::set<change_ty> > PredClosure;
78 std::map<change_ty, std::set<change_ty> > SuccClosure;
82 assert(Predecessors.count(Node) &&
"Invalid node!");
83 return Predecessors[Node].begin();
85 pred_iterator_ty
pred_end(change_ty Node) {
86 assert(Predecessors.count(Node) &&
"Invalid node!");
87 return Predecessors[Node].end();
90 pred_closure_iterator_ty pred_closure_begin(change_ty Node) {
91 assert(PredClosure.count(Node) &&
"Invalid node!");
92 return PredClosure[Node].begin();
94 pred_closure_iterator_ty pred_closure_end(change_ty Node) {
95 assert(PredClosure.count(Node) &&
"Invalid node!");
96 return PredClosure[Node].end();
100 assert(Successors.count(Node) &&
"Invalid node!");
101 return Successors[Node].begin();
103 succ_iterator_ty
succ_end(change_ty Node) {
104 assert(Successors.count(Node) &&
"Invalid node!");
105 return Successors[Node].end();
108 succ_closure_iterator_ty succ_closure_begin(change_ty Node) {
109 assert(SuccClosure.count(Node) &&
"Invalid node!");
110 return SuccClosure[Node].begin();
112 succ_closure_iterator_ty succ_closure_end(change_ty Node) {
113 assert(SuccClosure.count(Node) &&
"Invalid node!");
114 return SuccClosure[Node].end();
117 void UpdatedSearchState(
const changeset_ty &Changes,
118 const changesetlist_ty &Sets,
124 bool ExecuteOneTest(
const changeset_ty &S) {
127 for (changeset_ty::const_iterator it = S.begin(), ie = S.end(); it != ie;
131 assert(S.count(*it2) &&
"Attempt to run invalid changeset!");
139 const std::vector<edge_ty> &Dependencies);
151 bool GetTestResult(
const changeset_ty &Changes,
const changeset_ty &Required);
156 DAGDeltaAlgorithmImpl &DDAI;
162 void UpdatedSearchState(
const changeset_ty &Changes,
163 const changesetlist_ty &Sets)
override {
164 DDAI.UpdatedSearchState(Changes, Sets, Required);
167 bool ExecuteOneTest(
const changeset_ty &S)
override {
168 return DDAI.GetTestResult(S, Required);
172 DeltaActiveSetHelper(DAGDeltaAlgorithmImpl &DDAI,
173 const changeset_ty &Required)
179 DAGDeltaAlgorithmImpl::DAGDeltaAlgorithmImpl(
181 const std::vector<edge_ty> &Dependencies)
183 for (changeset_ty::const_iterator it = Changes.begin(),
184 ie = Changes.end(); it != ie; ++it) {
185 Predecessors.insert(std::make_pair(*it, std::vector<change_ty>()));
186 Successors.insert(std::make_pair(*it, std::vector<change_ty>()));
188 for (std::vector<edge_ty>::const_iterator it = Dependencies.begin(),
189 ie = Dependencies.end(); it != ie; ++it) {
190 Predecessors[it->second].push_back(it->first);
191 Successors[it->first].push_back(it->second);
195 for (changeset_ty::const_iterator it = Changes.begin(),
196 ie = Changes.end(); it != ie; ++it)
198 Roots.push_back(*it);
201 std::vector<change_ty> Worklist(Roots.begin(), Roots.end());
202 while (!Worklist.empty()) {
203 change_ty Change = Worklist.back();
206 std::set<change_ty> &ChangeSuccs = SuccClosure[Change];
207 for (pred_iterator_ty it =
pred_begin(Change),
208 ie =
pred_end(Change); it != ie; ++it) {
209 SuccClosure[*it].insert(Change);
210 SuccClosure[*it].insert(ChangeSuccs.begin(), ChangeSuccs.end());
211 Worklist.push_back(*it);
216 for (changeset_ty::const_iterator it = Changes.begin(),
217 ie = Changes.end(); it != ie; ++it)
218 PredClosure.insert(std::make_pair(*it, std::set<change_ty>()));
219 for (changeset_ty::const_iterator it = Changes.begin(),
220 ie = Changes.end(); it != ie; ++it)
221 for (succ_closure_iterator_ty it2 = succ_closure_begin(*it),
222 ie2 = succ_closure_end(*it); it2 != ie2; ++it2)
223 PredClosure[*it2].insert(*it);
227 llvm::errs() <<
"-- DAGDeltaAlgorithmImpl --\n";
229 for (changeset_ty::const_iterator it = Changes.begin(), ie = Changes.end();
231 if (it != Changes.begin())
249 for (std::vector<change_ty>::const_iterator it = Roots.begin(),
252 if (it != Roots.begin())
259 for (changeset_ty::const_iterator it = Changes.begin(), ie = Changes.end();
262 for (pred_closure_iterator_ty it2 = pred_closure_begin(*it),
263 ie2 = pred_closure_end(*it);
265 if (it2 != pred_closure_begin(*it))
273 for (changeset_ty::const_iterator it = Changes.begin(), ie = Changes.end();
276 for (succ_closure_iterator_ty it2 = succ_closure_begin(*it),
277 ie2 = succ_closure_end(*it);
279 if (it2 != succ_closure_begin(*it))
290 bool DAGDeltaAlgorithmImpl::GetTestResult(
const changeset_ty &Changes,
292 changeset_ty Extended(Required);
293 Extended.insert(Changes.begin(), Changes.end());
294 for (changeset_ty::const_iterator it = Changes.begin(),
295 ie = Changes.end(); it != ie; ++it)
296 Extended.insert(pred_closure_begin(*it), pred_closure_end(*it));
298 if (FailedTestsCache.count(Extended))
301 bool Result = ExecuteOneTest(Extended);
303 FailedTestsCache.insert(Extended);
309 DAGDeltaAlgorithmImpl::Run() {
311 changeset_ty CurrentSet(Roots.begin(), Roots.end());
321 while (!CurrentSet.empty()) {
323 llvm::errs() <<
"DAG_DD - " << CurrentSet.size() <<
" active changes, " 324 << Required.size() <<
" required changes\n";
328 DeltaActiveSetHelper Helper(*
this, Required);
329 changeset_ty CurrentMinSet = Helper.Run(CurrentSet);
338 Required.insert(CurrentMinSet.begin(), CurrentMinSet.end());
343 for (changeset_ty::const_iterator it = CurrentMinSet.begin(),
344 ie = CurrentMinSet.end(); it != ie; ++it)
354 void DAGDeltaAlgorithm::anchor() {
359 const std::vector<edge_ty> &Dependencies) {
360 return DAGDeltaAlgorithmImpl(*
this, Changes, Dependencies).Run();
raw_ostream & errs()
This returns a reference to a raw_ostream for standard error.
DAGDeltaAlgorithm - Implements a "delta debugging" algorithm for minimizing directed acyclic graphs u...
This class represents lattice values for constants.
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
std::set< change_ty > changeset_ty
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
std::vector< changeset_ty > changesetlist_ty
Interval::succ_iterator succ_end(Interval *I)
DeltaAlgorithm - Implements the delta debugging algorithm (A.
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Interval::pred_iterator pred_end(Interval *I)
virtual bool ExecuteOneTest(const changeset_ty &S)=0
ExecuteOneTest - Execute a single test predicate on the change set S.
std::pair< change_ty, change_ty > edge_ty
changeset_ty Run(const changeset_ty &Changes, const std::vector< edge_ty > &Dependencies)
Run - Minimize the DAG formed by the Changes vertices and the Dependencies edges by executing...
virtual void UpdatedSearchState(const changeset_ty &Changes, const changesetlist_ty &Sets, const changeset_ty &Required)
UpdatedSearchState - Callback used when the search state changes.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())