1210006Srdivacky//===--- DAGDeltaAlgorithm.cpp - A DAG Minimization Algorithm --*- C++ -*--===// 2210006Srdivacky// 3210006Srdivacky// The LLVM Compiler Infrastructure 4210006Srdivacky// 5210006Srdivacky// This file is distributed under the University of Illinois Open Source 6210006Srdivacky// License. See LICENSE.TXT for details. 7210006Srdivacky//===----------------------------------------------------------------------===// 8210006Srdivacky// 9210006Srdivacky// The algorithm we use attempts to exploit the dependency information by 10210006Srdivacky// minimizing top-down. We start by constructing an initial root set R, and 11210006Srdivacky// then iteratively: 12210006Srdivacky// 13210006Srdivacky// 1. Minimize the set R using the test predicate: 14210006Srdivacky// P'(S) = P(S union pred*(S)) 15210006Srdivacky// 16210006Srdivacky// 2. Extend R to R' = R union pred(R). 17210006Srdivacky// 18210006Srdivacky// until a fixed point is reached. 19210006Srdivacky// 20210006Srdivacky// The idea is that we want to quickly prune entire portions of the graph, so we 21210006Srdivacky// try to find high-level nodes that can be eliminated with all of their 22210006Srdivacky// dependents. 23210006Srdivacky// 24210006Srdivacky// FIXME: The current algorithm doesn't actually provide a strong guarantee 25210006Srdivacky// about the minimality of the result. The problem is that after adding nodes to 26210006Srdivacky// the required set, we no longer consider them for elimination. For strictly 27210006Srdivacky// well formed predicates, this doesn't happen, but it commonly occurs in 28210006Srdivacky// practice when there are unmodelled dependencies. I believe we can resolve 29210006Srdivacky// this by allowing the required set to be minimized as well, but need more test 30210006Srdivacky// cases first. 31210006Srdivacky// 32210006Srdivacky//===----------------------------------------------------------------------===// 33210006Srdivacky 34210006Srdivacky#include "llvm/ADT/DAGDeltaAlgorithm.h" 35210006Srdivacky#include "llvm/ADT/DeltaAlgorithm.h" 36210006Srdivacky#include "llvm/Support/Debug.h" 37210006Srdivacky#include "llvm/Support/Format.h" 38210006Srdivacky#include "llvm/Support/raw_ostream.h" 39210006Srdivacky#include <algorithm> 40210006Srdivacky#include <cassert> 41210006Srdivacky#include <iterator> 42210006Srdivacky#include <map> 43210006Srdivackyusing namespace llvm; 44210006Srdivacky 45210006Srdivackynamespace { 46210006Srdivacky 47210006Srdivackyclass DAGDeltaAlgorithmImpl { 48210006Srdivacky friend class DeltaActiveSetHelper; 49210006Srdivacky 50210006Srdivackypublic: 51210006Srdivacky typedef DAGDeltaAlgorithm::change_ty change_ty; 52210006Srdivacky typedef DAGDeltaAlgorithm::changeset_ty changeset_ty; 53210006Srdivacky typedef DAGDeltaAlgorithm::changesetlist_ty changesetlist_ty; 54210006Srdivacky typedef DAGDeltaAlgorithm::edge_ty edge_ty; 55210006Srdivacky 56210006Srdivackyprivate: 57210006Srdivacky typedef std::vector<change_ty>::iterator pred_iterator_ty; 58210006Srdivacky typedef std::vector<change_ty>::iterator succ_iterator_ty; 59210006Srdivacky typedef std::set<change_ty>::iterator pred_closure_iterator_ty; 60210006Srdivacky typedef std::set<change_ty>::iterator succ_closure_iterator_ty; 61210006Srdivacky 62210006Srdivacky DAGDeltaAlgorithm &DDA; 63210006Srdivacky 64210006Srdivacky const changeset_ty &Changes; 65210006Srdivacky const std::vector<edge_ty> &Dependencies; 66210006Srdivacky 67210006Srdivacky std::vector<change_ty> Roots; 68210006Srdivacky 69210006Srdivacky /// Cache of failed test results. Successful test results are never cached 70210006Srdivacky /// since we always reduce following a success. We maintain an independent 71210006Srdivacky /// cache from that used by the individual delta passes because we may get 72210006Srdivacky /// hits across multiple individual delta invocations. 73210006Srdivacky mutable std::set<changeset_ty> FailedTestsCache; 74210006Srdivacky 75210006Srdivacky // FIXME: Gross. 76210006Srdivacky std::map<change_ty, std::vector<change_ty> > Predecessors; 77210006Srdivacky std::map<change_ty, std::vector<change_ty> > Successors; 78210006Srdivacky 79210006Srdivacky std::map<change_ty, std::set<change_ty> > PredClosure; 80210006Srdivacky std::map<change_ty, std::set<change_ty> > SuccClosure; 81210006Srdivacky 82210006Srdivackyprivate: 83210006Srdivacky pred_iterator_ty pred_begin(change_ty Node) { 84210006Srdivacky assert(Predecessors.count(Node) && "Invalid node!"); 85210006Srdivacky return Predecessors[Node].begin(); 86210006Srdivacky } 87210006Srdivacky pred_iterator_ty pred_end(change_ty Node) { 88210006Srdivacky assert(Predecessors.count(Node) && "Invalid node!"); 89210006Srdivacky return Predecessors[Node].end(); 90210006Srdivacky } 91210006Srdivacky 92210006Srdivacky pred_closure_iterator_ty pred_closure_begin(change_ty Node) { 93210006Srdivacky assert(PredClosure.count(Node) && "Invalid node!"); 94210006Srdivacky return PredClosure[Node].begin(); 95210006Srdivacky } 96210006Srdivacky pred_closure_iterator_ty pred_closure_end(change_ty Node) { 97210006Srdivacky assert(PredClosure.count(Node) && "Invalid node!"); 98210006Srdivacky return PredClosure[Node].end(); 99210006Srdivacky } 100210006Srdivacky 101210006Srdivacky succ_iterator_ty succ_begin(change_ty Node) { 102210006Srdivacky assert(Successors.count(Node) && "Invalid node!"); 103210006Srdivacky return Successors[Node].begin(); 104210006Srdivacky } 105210006Srdivacky succ_iterator_ty succ_end(change_ty Node) { 106210006Srdivacky assert(Successors.count(Node) && "Invalid node!"); 107210006Srdivacky return Successors[Node].end(); 108210006Srdivacky } 109210006Srdivacky 110210006Srdivacky succ_closure_iterator_ty succ_closure_begin(change_ty Node) { 111210006Srdivacky assert(SuccClosure.count(Node) && "Invalid node!"); 112210006Srdivacky return SuccClosure[Node].begin(); 113210006Srdivacky } 114210006Srdivacky succ_closure_iterator_ty succ_closure_end(change_ty Node) { 115210006Srdivacky assert(SuccClosure.count(Node) && "Invalid node!"); 116210006Srdivacky return SuccClosure[Node].end(); 117210006Srdivacky } 118210006Srdivacky 119210006Srdivacky void UpdatedSearchState(const changeset_ty &Changes, 120210006Srdivacky const changesetlist_ty &Sets, 121210006Srdivacky const changeset_ty &Required) { 122210006Srdivacky DDA.UpdatedSearchState(Changes, Sets, Required); 123210006Srdivacky } 124210006Srdivacky 125243830Sdim /// ExecuteOneTest - Execute a single test predicate on the change set \p S. 126210006Srdivacky bool ExecuteOneTest(const changeset_ty &S) { 127210006Srdivacky // Check dependencies invariant. 128210006Srdivacky DEBUG({ 129210006Srdivacky for (changeset_ty::const_iterator it = S.begin(), 130210006Srdivacky ie = S.end(); it != ie; ++it) 131210006Srdivacky for (succ_iterator_ty it2 = succ_begin(*it), 132210006Srdivacky ie2 = succ_end(*it); it2 != ie2; ++it2) 133210006Srdivacky assert(S.count(*it2) && "Attempt to run invalid changeset!"); 134210006Srdivacky }); 135210006Srdivacky 136210006Srdivacky return DDA.ExecuteOneTest(S); 137210006Srdivacky } 138210006Srdivacky 139210006Srdivackypublic: 140210006Srdivacky DAGDeltaAlgorithmImpl(DAGDeltaAlgorithm &_DDA, 141210006Srdivacky const changeset_ty &_Changes, 142210006Srdivacky const std::vector<edge_ty> &_Dependencies); 143210006Srdivacky 144210006Srdivacky changeset_ty Run(); 145210006Srdivacky 146243830Sdim /// GetTestResult - Get the test result for the active set \p Changes with 147243830Sdim /// \p Required changes from the cache, executing the test if necessary. 148210006Srdivacky /// 149210006Srdivacky /// \param Changes - The set of active changes being minimized, which should 150210006Srdivacky /// have their pred closure included in the test. 151210006Srdivacky /// \param Required - The set of changes which have previously been 152210006Srdivacky /// established to be required. 153210006Srdivacky /// \return - The test result. 154210006Srdivacky bool GetTestResult(const changeset_ty &Changes, const changeset_ty &Required); 155210006Srdivacky}; 156210006Srdivacky 157210006Srdivacky/// Helper object for minimizing an active set of changes. 158210006Srdivackyclass DeltaActiveSetHelper : public DeltaAlgorithm { 159210006Srdivacky DAGDeltaAlgorithmImpl &DDAI; 160210006Srdivacky 161210006Srdivacky const changeset_ty &Required; 162210006Srdivacky 163210006Srdivackyprotected: 164210006Srdivacky /// UpdatedSearchState - Callback used when the search state changes. 165210006Srdivacky virtual void UpdatedSearchState(const changeset_ty &Changes, 166243830Sdim const changesetlist_ty &Sets) LLVM_OVERRIDE { 167210006Srdivacky DDAI.UpdatedSearchState(Changes, Sets, Required); 168210006Srdivacky } 169210006Srdivacky 170243830Sdim virtual bool ExecuteOneTest(const changeset_ty &S) LLVM_OVERRIDE { 171210006Srdivacky return DDAI.GetTestResult(S, Required); 172210006Srdivacky } 173210006Srdivacky 174210006Srdivackypublic: 175210006Srdivacky DeltaActiveSetHelper(DAGDeltaAlgorithmImpl &_DDAI, 176210006Srdivacky const changeset_ty &_Required) 177210006Srdivacky : DDAI(_DDAI), Required(_Required) {} 178210006Srdivacky}; 179210006Srdivacky 180210006Srdivacky} 181210006Srdivacky 182210006SrdivackyDAGDeltaAlgorithmImpl::DAGDeltaAlgorithmImpl(DAGDeltaAlgorithm &_DDA, 183210006Srdivacky const changeset_ty &_Changes, 184210006Srdivacky const std::vector<edge_ty> 185210006Srdivacky &_Dependencies) 186210006Srdivacky : DDA(_DDA), 187210006Srdivacky Changes(_Changes), 188210006Srdivacky Dependencies(_Dependencies) 189210006Srdivacky{ 190210006Srdivacky for (changeset_ty::const_iterator it = Changes.begin(), 191210006Srdivacky ie = Changes.end(); it != ie; ++it) { 192210006Srdivacky Predecessors.insert(std::make_pair(*it, std::vector<change_ty>())); 193210006Srdivacky Successors.insert(std::make_pair(*it, std::vector<change_ty>())); 194210006Srdivacky } 195210006Srdivacky for (std::vector<edge_ty>::const_iterator it = Dependencies.begin(), 196210006Srdivacky ie = Dependencies.end(); it != ie; ++it) { 197210006Srdivacky Predecessors[it->second].push_back(it->first); 198210006Srdivacky Successors[it->first].push_back(it->second); 199210006Srdivacky } 200210006Srdivacky 201210006Srdivacky // Compute the roots. 202210006Srdivacky for (changeset_ty::const_iterator it = Changes.begin(), 203210006Srdivacky ie = Changes.end(); it != ie; ++it) 204210006Srdivacky if (succ_begin(*it) == succ_end(*it)) 205210006Srdivacky Roots.push_back(*it); 206210006Srdivacky 207210006Srdivacky // Pre-compute the closure of the successor relation. 208210006Srdivacky std::vector<change_ty> Worklist(Roots.begin(), Roots.end()); 209210006Srdivacky while (!Worklist.empty()) { 210210006Srdivacky change_ty Change = Worklist.back(); 211210006Srdivacky Worklist.pop_back(); 212210006Srdivacky 213210006Srdivacky std::set<change_ty> &ChangeSuccs = SuccClosure[Change]; 214210006Srdivacky for (pred_iterator_ty it = pred_begin(Change), 215210006Srdivacky ie = pred_end(Change); it != ie; ++it) { 216210006Srdivacky SuccClosure[*it].insert(Change); 217210006Srdivacky SuccClosure[*it].insert(ChangeSuccs.begin(), ChangeSuccs.end()); 218210006Srdivacky Worklist.push_back(*it); 219210006Srdivacky } 220210006Srdivacky } 221210006Srdivacky 222210006Srdivacky // Invert to form the predecessor closure map. 223210006Srdivacky for (changeset_ty::const_iterator it = Changes.begin(), 224210006Srdivacky ie = Changes.end(); it != ie; ++it) 225210006Srdivacky PredClosure.insert(std::make_pair(*it, std::set<change_ty>())); 226210006Srdivacky for (changeset_ty::const_iterator it = Changes.begin(), 227210006Srdivacky ie = Changes.end(); it != ie; ++it) 228210006Srdivacky for (succ_closure_iterator_ty it2 = succ_closure_begin(*it), 229210006Srdivacky ie2 = succ_closure_end(*it); it2 != ie2; ++it2) 230210006Srdivacky PredClosure[*it2].insert(*it); 231210006Srdivacky 232210006Srdivacky // Dump useful debug info. 233210006Srdivacky DEBUG({ 234210006Srdivacky llvm::errs() << "-- DAGDeltaAlgorithmImpl --\n"; 235210006Srdivacky llvm::errs() << "Changes: ["; 236210006Srdivacky for (changeset_ty::const_iterator it = Changes.begin(), 237210006Srdivacky ie = Changes.end(); it != ie; ++it) { 238210006Srdivacky if (it != Changes.begin()) llvm::errs() << ", "; 239210006Srdivacky llvm::errs() << *it; 240210006Srdivacky 241210006Srdivacky if (succ_begin(*it) != succ_end(*it)) { 242210006Srdivacky llvm::errs() << "("; 243210006Srdivacky for (succ_iterator_ty it2 = succ_begin(*it), 244210006Srdivacky ie2 = succ_end(*it); it2 != ie2; ++it2) { 245210006Srdivacky if (it2 != succ_begin(*it)) llvm::errs() << ", "; 246210006Srdivacky llvm::errs() << "->" << *it2; 247210006Srdivacky } 248210006Srdivacky llvm::errs() << ")"; 249210006Srdivacky } 250210006Srdivacky } 251210006Srdivacky llvm::errs() << "]\n"; 252210006Srdivacky 253210006Srdivacky llvm::errs() << "Roots: ["; 254210006Srdivacky for (std::vector<change_ty>::const_iterator it = Roots.begin(), 255210006Srdivacky ie = Roots.end(); it != ie; ++it) { 256210006Srdivacky if (it != Roots.begin()) llvm::errs() << ", "; 257210006Srdivacky llvm::errs() << *it; 258210006Srdivacky } 259210006Srdivacky llvm::errs() << "]\n"; 260210006Srdivacky 261210006Srdivacky llvm::errs() << "Predecessor Closure:\n"; 262210006Srdivacky for (changeset_ty::const_iterator it = Changes.begin(), 263210006Srdivacky ie = Changes.end(); it != ie; ++it) { 264210006Srdivacky llvm::errs() << format(" %-4d: [", *it); 265210006Srdivacky for (pred_closure_iterator_ty it2 = pred_closure_begin(*it), 266210006Srdivacky ie2 = pred_closure_end(*it); it2 != ie2; ++it2) { 267210006Srdivacky if (it2 != pred_closure_begin(*it)) llvm::errs() << ", "; 268210006Srdivacky llvm::errs() << *it2; 269210006Srdivacky } 270210006Srdivacky llvm::errs() << "]\n"; 271210006Srdivacky } 272210006Srdivacky 273210006Srdivacky llvm::errs() << "Successor Closure:\n"; 274210006Srdivacky for (changeset_ty::const_iterator it = Changes.begin(), 275210006Srdivacky ie = Changes.end(); it != ie; ++it) { 276210006Srdivacky llvm::errs() << format(" %-4d: [", *it); 277210006Srdivacky for (succ_closure_iterator_ty it2 = succ_closure_begin(*it), 278210006Srdivacky ie2 = succ_closure_end(*it); it2 != ie2; ++it2) { 279210006Srdivacky if (it2 != succ_closure_begin(*it)) llvm::errs() << ", "; 280210006Srdivacky llvm::errs() << *it2; 281210006Srdivacky } 282210006Srdivacky llvm::errs() << "]\n"; 283210006Srdivacky } 284210006Srdivacky 285210006Srdivacky llvm::errs() << "\n\n"; 286210006Srdivacky }); 287210006Srdivacky} 288210006Srdivacky 289210006Srdivackybool DAGDeltaAlgorithmImpl::GetTestResult(const changeset_ty &Changes, 290210006Srdivacky const changeset_ty &Required) { 291210006Srdivacky changeset_ty Extended(Required); 292210006Srdivacky Extended.insert(Changes.begin(), Changes.end()); 293210006Srdivacky for (changeset_ty::const_iterator it = Changes.begin(), 294210006Srdivacky ie = Changes.end(); it != ie; ++it) 295210006Srdivacky Extended.insert(pred_closure_begin(*it), pred_closure_end(*it)); 296210006Srdivacky 297210006Srdivacky if (FailedTestsCache.count(Extended)) 298210006Srdivacky return false; 299210006Srdivacky 300210006Srdivacky bool Result = ExecuteOneTest(Extended); 301210006Srdivacky if (!Result) 302210006Srdivacky FailedTestsCache.insert(Extended); 303210006Srdivacky 304210006Srdivacky return Result; 305210006Srdivacky} 306210006Srdivacky 307210006SrdivackyDAGDeltaAlgorithm::changeset_ty 308210006SrdivackyDAGDeltaAlgorithmImpl::Run() { 309210006Srdivacky // The current set of changes we are minimizing, starting at the roots. 310210006Srdivacky changeset_ty CurrentSet(Roots.begin(), Roots.end()); 311210006Srdivacky 312210006Srdivacky // The set of required changes. 313210006Srdivacky changeset_ty Required; 314210006Srdivacky 315210006Srdivacky // Iterate until the active set of changes is empty. Convergence is guaranteed 316210006Srdivacky // assuming input was a DAG. 317210006Srdivacky // 318210006Srdivacky // Invariant: CurrentSet intersect Required == {} 319210006Srdivacky // Invariant: Required == (Required union succ*(Required)) 320210006Srdivacky while (!CurrentSet.empty()) { 321210006Srdivacky DEBUG({ 322210006Srdivacky llvm::errs() << "DAG_DD - " << CurrentSet.size() << " active changes, " 323210006Srdivacky << Required.size() << " required changes\n"; 324210006Srdivacky }); 325210006Srdivacky 326210006Srdivacky // Minimize the current set of changes. 327210006Srdivacky DeltaActiveSetHelper Helper(*this, Required); 328210006Srdivacky changeset_ty CurrentMinSet = Helper.Run(CurrentSet); 329210006Srdivacky 330210006Srdivacky // Update the set of required changes. Since 331210006Srdivacky // CurrentMinSet subset CurrentSet 332210006Srdivacky // and after the last iteration, 333210006Srdivacky // succ(CurrentSet) subset Required 334210006Srdivacky // then 335210006Srdivacky // succ(CurrentMinSet) subset Required 336210006Srdivacky // and our invariant on Required is maintained. 337210006Srdivacky Required.insert(CurrentMinSet.begin(), CurrentMinSet.end()); 338210006Srdivacky 339210006Srdivacky // Replace the current set with the predecssors of the minimized set of 340210006Srdivacky // active changes. 341210006Srdivacky CurrentSet.clear(); 342210006Srdivacky for (changeset_ty::const_iterator it = CurrentMinSet.begin(), 343210006Srdivacky ie = CurrentMinSet.end(); it != ie; ++it) 344210006Srdivacky CurrentSet.insert(pred_begin(*it), pred_end(*it)); 345210006Srdivacky 346210006Srdivacky // FIXME: We could enforce CurrentSet intersect Required == {} here if we 347210006Srdivacky // wanted to protect against cyclic graphs. 348210006Srdivacky } 349210006Srdivacky 350210006Srdivacky return Required; 351210006Srdivacky} 352210006Srdivacky 353234353Sdimvoid DAGDeltaAlgorithm::anchor() { 354234353Sdim} 355234353Sdim 356210006SrdivackyDAGDeltaAlgorithm::changeset_ty 357210006SrdivackyDAGDeltaAlgorithm::Run(const changeset_ty &Changes, 358210006Srdivacky const std::vector<edge_ty> &Dependencies) { 359210006Srdivacky return DAGDeltaAlgorithmImpl(*this, Changes, Dependencies).Run(); 360210006Srdivacky} 361