1//===--- DAGDeltaAlgorithm.cpp - A DAG Minimization Algorithm --*- C++ -*--===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7//===----------------------------------------------------------------------===// 8// 9// The algorithm we use attempts to exploit the dependency information by 10// minimizing top-down. We start by constructing an initial root set R, and 11// then iteratively: 12// 13// 1. Minimize the set R using the test predicate: 14// P'(S) = P(S union pred*(S)) 15// 16// 2. Extend R to R' = R union pred(R). 17// 18// until a fixed point is reached. 19// 20// The idea is that we want to quickly prune entire portions of the graph, so we 21// try to find high-level nodes that can be eliminated with all of their 22// dependents. 23// 24// FIXME: The current algorithm doesn't actually provide a strong guarantee 25// about the minimality of the result. The problem is that after adding nodes to 26// the required set, we no longer consider them for elimination. For strictly 27// well formed predicates, this doesn't happen, but it commonly occurs in 28// practice when there are unmodelled dependencies. I believe we can resolve 29// this by allowing the required set to be minimized as well, but need more test 30// cases first. 31// 32//===----------------------------------------------------------------------===// 33 34#include "llvm/ADT/DAGDeltaAlgorithm.h" 35#include "llvm/ADT/DeltaAlgorithm.h" 36#include "llvm/Support/Debug.h" 37#include "llvm/Support/Format.h" 38#include "llvm/Support/raw_ostream.h" 39#include <algorithm> 40#include <cassert> 41#include <iterator> 42#include <map> 43using namespace llvm; 44 45#define DEBUG_TYPE "dag-delta" 46 47namespace { 48 49class DAGDeltaAlgorithmImpl { 50 friend class DeltaActiveSetHelper; 51 52public: 53 typedef DAGDeltaAlgorithm::change_ty change_ty; 54 typedef DAGDeltaAlgorithm::changeset_ty changeset_ty; 55 typedef DAGDeltaAlgorithm::changesetlist_ty changesetlist_ty; 56 typedef DAGDeltaAlgorithm::edge_ty edge_ty; 57 58private: 59 typedef std::vector<change_ty>::iterator pred_iterator_ty; 60 typedef std::vector<change_ty>::iterator succ_iterator_ty; 61 typedef std::set<change_ty>::iterator pred_closure_iterator_ty; 62 typedef std::set<change_ty>::iterator succ_closure_iterator_ty; 63 64 DAGDeltaAlgorithm &DDA; 65 66 std::vector<change_ty> Roots; 67 68 /// Cache of failed test results. Successful test results are never cached 69 /// since we always reduce following a success. We maintain an independent 70 /// cache from that used by the individual delta passes because we may get 71 /// hits across multiple individual delta invocations. 72 mutable std::set<changeset_ty> FailedTestsCache; 73 74 // FIXME: Gross. 75 std::map<change_ty, std::vector<change_ty> > Predecessors; 76 std::map<change_ty, std::vector<change_ty> > Successors; 77 78 std::map<change_ty, std::set<change_ty> > PredClosure; 79 std::map<change_ty, std::set<change_ty> > SuccClosure; 80 81private: 82 pred_iterator_ty pred_begin(change_ty Node) { 83 assert(Predecessors.count(Node) && "Invalid node!"); 84 return Predecessors[Node].begin(); 85 } 86 pred_iterator_ty pred_end(change_ty Node) { 87 assert(Predecessors.count(Node) && "Invalid node!"); 88 return Predecessors[Node].end(); 89 } 90 91 pred_closure_iterator_ty pred_closure_begin(change_ty Node) { 92 assert(PredClosure.count(Node) && "Invalid node!"); 93 return PredClosure[Node].begin(); 94 } 95 pred_closure_iterator_ty pred_closure_end(change_ty Node) { 96 assert(PredClosure.count(Node) && "Invalid node!"); 97 return PredClosure[Node].end(); 98 } 99 100 succ_iterator_ty succ_begin(change_ty Node) { 101 assert(Successors.count(Node) && "Invalid node!"); 102 return Successors[Node].begin(); 103 } 104 succ_iterator_ty succ_end(change_ty Node) { 105 assert(Successors.count(Node) && "Invalid node!"); 106 return Successors[Node].end(); 107 } 108 109 succ_closure_iterator_ty succ_closure_begin(change_ty Node) { 110 assert(SuccClosure.count(Node) && "Invalid node!"); 111 return SuccClosure[Node].begin(); 112 } 113 succ_closure_iterator_ty succ_closure_end(change_ty Node) { 114 assert(SuccClosure.count(Node) && "Invalid node!"); 115 return SuccClosure[Node].end(); 116 } 117 118 void UpdatedSearchState(const changeset_ty &Changes, 119 const changesetlist_ty &Sets, 120 const changeset_ty &Required) { 121 DDA.UpdatedSearchState(Changes, Sets, Required); 122 } 123 124 /// ExecuteOneTest - Execute a single test predicate on the change set \p S. 125 bool ExecuteOneTest(const changeset_ty &S) { 126 // Check dependencies invariant. 127 DEBUG({ 128 for (changeset_ty::const_iterator it = S.begin(), 129 ie = S.end(); it != ie; ++it) 130 for (succ_iterator_ty it2 = succ_begin(*it), 131 ie2 = succ_end(*it); it2 != ie2; ++it2) 132 assert(S.count(*it2) && "Attempt to run invalid changeset!"); 133 }); 134 135 return DDA.ExecuteOneTest(S); 136 } 137 138public: 139 DAGDeltaAlgorithmImpl(DAGDeltaAlgorithm &DDA, const changeset_ty &Changes, 140 const std::vector<edge_ty> &Dependencies); 141 142 changeset_ty Run(); 143 144 /// GetTestResult - Get the test result for the active set \p Changes with 145 /// \p Required changes from the cache, executing the test if necessary. 146 /// 147 /// \param Changes - The set of active changes being minimized, which should 148 /// have their pred closure included in the test. 149 /// \param Required - The set of changes which have previously been 150 /// established to be required. 151 /// \return - The test result. 152 bool GetTestResult(const changeset_ty &Changes, const changeset_ty &Required); 153}; 154 155/// Helper object for minimizing an active set of changes. 156class DeltaActiveSetHelper : public DeltaAlgorithm { 157 DAGDeltaAlgorithmImpl &DDAI; 158 159 const changeset_ty &Required; 160 161protected: 162 /// UpdatedSearchState - Callback used when the search state changes. 163 void UpdatedSearchState(const changeset_ty &Changes, 164 const changesetlist_ty &Sets) override { 165 DDAI.UpdatedSearchState(Changes, Sets, Required); 166 } 167 168 bool ExecuteOneTest(const changeset_ty &S) override { 169 return DDAI.GetTestResult(S, Required); 170 } 171 172public: 173 DeltaActiveSetHelper(DAGDeltaAlgorithmImpl &DDAI, 174 const changeset_ty &Required) 175 : DDAI(DDAI), Required(Required) {} 176}; 177 178} 179 180DAGDeltaAlgorithmImpl::DAGDeltaAlgorithmImpl( 181 DAGDeltaAlgorithm &DDA, const changeset_ty &Changes, 182 const std::vector<edge_ty> &Dependencies) 183 : DDA(DDA) { 184 for (changeset_ty::const_iterator it = Changes.begin(), 185 ie = Changes.end(); it != ie; ++it) { 186 Predecessors.insert(std::make_pair(*it, std::vector<change_ty>())); 187 Successors.insert(std::make_pair(*it, std::vector<change_ty>())); 188 } 189 for (std::vector<edge_ty>::const_iterator it = Dependencies.begin(), 190 ie = Dependencies.end(); it != ie; ++it) { 191 Predecessors[it->second].push_back(it->first); 192 Successors[it->first].push_back(it->second); 193 } 194 195 // Compute the roots. 196 for (changeset_ty::const_iterator it = Changes.begin(), 197 ie = Changes.end(); it != ie; ++it) 198 if (succ_begin(*it) == succ_end(*it)) 199 Roots.push_back(*it); 200 201 // Pre-compute the closure of the successor relation. 202 std::vector<change_ty> Worklist(Roots.begin(), Roots.end()); 203 while (!Worklist.empty()) { 204 change_ty Change = Worklist.back(); 205 Worklist.pop_back(); 206 207 std::set<change_ty> &ChangeSuccs = SuccClosure[Change]; 208 for (pred_iterator_ty it = pred_begin(Change), 209 ie = pred_end(Change); it != ie; ++it) { 210 SuccClosure[*it].insert(Change); 211 SuccClosure[*it].insert(ChangeSuccs.begin(), ChangeSuccs.end()); 212 Worklist.push_back(*it); 213 } 214 } 215 216 // Invert to form the predecessor closure map. 217 for (changeset_ty::const_iterator it = Changes.begin(), 218 ie = Changes.end(); it != ie; ++it) 219 PredClosure.insert(std::make_pair(*it, std::set<change_ty>())); 220 for (changeset_ty::const_iterator it = Changes.begin(), 221 ie = Changes.end(); it != ie; ++it) 222 for (succ_closure_iterator_ty it2 = succ_closure_begin(*it), 223 ie2 = succ_closure_end(*it); it2 != ie2; ++it2) 224 PredClosure[*it2].insert(*it); 225 226 // Dump useful debug info. 227 DEBUG({ 228 llvm::errs() << "-- DAGDeltaAlgorithmImpl --\n"; 229 llvm::errs() << "Changes: ["; 230 for (changeset_ty::const_iterator it = Changes.begin(), 231 ie = Changes.end(); it != ie; ++it) { 232 if (it != Changes.begin()) llvm::errs() << ", "; 233 llvm::errs() << *it; 234 235 if (succ_begin(*it) != succ_end(*it)) { 236 llvm::errs() << "("; 237 for (succ_iterator_ty it2 = succ_begin(*it), 238 ie2 = succ_end(*it); it2 != ie2; ++it2) { 239 if (it2 != succ_begin(*it)) llvm::errs() << ", "; 240 llvm::errs() << "->" << *it2; 241 } 242 llvm::errs() << ")"; 243 } 244 } 245 llvm::errs() << "]\n"; 246 247 llvm::errs() << "Roots: ["; 248 for (std::vector<change_ty>::const_iterator it = Roots.begin(), 249 ie = Roots.end(); it != ie; ++it) { 250 if (it != Roots.begin()) llvm::errs() << ", "; 251 llvm::errs() << *it; 252 } 253 llvm::errs() << "]\n"; 254 255 llvm::errs() << "Predecessor Closure:\n"; 256 for (changeset_ty::const_iterator it = Changes.begin(), 257 ie = Changes.end(); it != ie; ++it) { 258 llvm::errs() << format(" %-4d: [", *it); 259 for (pred_closure_iterator_ty it2 = pred_closure_begin(*it), 260 ie2 = pred_closure_end(*it); it2 != ie2; ++it2) { 261 if (it2 != pred_closure_begin(*it)) llvm::errs() << ", "; 262 llvm::errs() << *it2; 263 } 264 llvm::errs() << "]\n"; 265 } 266 267 llvm::errs() << "Successor Closure:\n"; 268 for (changeset_ty::const_iterator it = Changes.begin(), 269 ie = Changes.end(); it != ie; ++it) { 270 llvm::errs() << format(" %-4d: [", *it); 271 for (succ_closure_iterator_ty it2 = succ_closure_begin(*it), 272 ie2 = succ_closure_end(*it); it2 != ie2; ++it2) { 273 if (it2 != succ_closure_begin(*it)) llvm::errs() << ", "; 274 llvm::errs() << *it2; 275 } 276 llvm::errs() << "]\n"; 277 } 278 279 llvm::errs() << "\n\n"; 280 }); 281} 282 283bool DAGDeltaAlgorithmImpl::GetTestResult(const changeset_ty &Changes, 284 const changeset_ty &Required) { 285 changeset_ty Extended(Required); 286 Extended.insert(Changes.begin(), Changes.end()); 287 for (changeset_ty::const_iterator it = Changes.begin(), 288 ie = Changes.end(); it != ie; ++it) 289 Extended.insert(pred_closure_begin(*it), pred_closure_end(*it)); 290 291 if (FailedTestsCache.count(Extended)) 292 return false; 293 294 bool Result = ExecuteOneTest(Extended); 295 if (!Result) 296 FailedTestsCache.insert(Extended); 297 298 return Result; 299} 300 301DAGDeltaAlgorithm::changeset_ty 302DAGDeltaAlgorithmImpl::Run() { 303 // The current set of changes we are minimizing, starting at the roots. 304 changeset_ty CurrentSet(Roots.begin(), Roots.end()); 305 306 // The set of required changes. 307 changeset_ty Required; 308 309 // Iterate until the active set of changes is empty. Convergence is guaranteed 310 // assuming input was a DAG. 311 // 312 // Invariant: CurrentSet intersect Required == {} 313 // Invariant: Required == (Required union succ*(Required)) 314 while (!CurrentSet.empty()) { 315 DEBUG({ 316 llvm::errs() << "DAG_DD - " << CurrentSet.size() << " active changes, " 317 << Required.size() << " required changes\n"; 318 }); 319 320 // Minimize the current set of changes. 321 DeltaActiveSetHelper Helper(*this, Required); 322 changeset_ty CurrentMinSet = Helper.Run(CurrentSet); 323 324 // Update the set of required changes. Since 325 // CurrentMinSet subset CurrentSet 326 // and after the last iteration, 327 // succ(CurrentSet) subset Required 328 // then 329 // succ(CurrentMinSet) subset Required 330 // and our invariant on Required is maintained. 331 Required.insert(CurrentMinSet.begin(), CurrentMinSet.end()); 332 333 // Replace the current set with the predecssors of the minimized set of 334 // active changes. 335 CurrentSet.clear(); 336 for (changeset_ty::const_iterator it = CurrentMinSet.begin(), 337 ie = CurrentMinSet.end(); it != ie; ++it) 338 CurrentSet.insert(pred_begin(*it), pred_end(*it)); 339 340 // FIXME: We could enforce CurrentSet intersect Required == {} here if we 341 // wanted to protect against cyclic graphs. 342 } 343 344 return Required; 345} 346 347void DAGDeltaAlgorithm::anchor() { 348} 349 350DAGDeltaAlgorithm::changeset_ty 351DAGDeltaAlgorithm::Run(const changeset_ty &Changes, 352 const std::vector<edge_ty> &Dependencies) { 353 return DAGDeltaAlgorithmImpl(*this, Changes, Dependencies).Run(); 354} 355