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> 43 using namespace llvm; 44 45 #define DEBUG_TYPE "dag-delta" 46 47 namespace { 48 49 class DAGDeltaAlgorithmImpl { 50 friend class DeltaActiveSetHelper; 51 52 public: 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 58 private: 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 const changeset_ty &Changes; 67 const std::vector<edge_ty> &Dependencies; 68 69 std::vector<change_ty> Roots; 70 71 /// Cache of failed test results. Successful test results are never cached 72 /// since we always reduce following a success. We maintain an independent 73 /// cache from that used by the individual delta passes because we may get 74 /// hits across multiple individual delta invocations. 75 mutable std::set<changeset_ty> FailedTestsCache; 76 77 // FIXME: Gross. 78 std::map<change_ty, std::vector<change_ty> > Predecessors; 79 std::map<change_ty, std::vector<change_ty> > Successors; 80 81 std::map<change_ty, std::set<change_ty> > PredClosure; 82 std::map<change_ty, std::set<change_ty> > SuccClosure; 83 84 private: 85 pred_iterator_ty pred_begin(change_ty Node) { 86 assert(Predecessors.count(Node) && "Invalid node!"); 87 return Predecessors[Node].begin(); 88 } 89 pred_iterator_ty pred_end(change_ty Node) { 90 assert(Predecessors.count(Node) && "Invalid node!"); 91 return Predecessors[Node].end(); 92 } 93 94 pred_closure_iterator_ty pred_closure_begin(change_ty Node) { 95 assert(PredClosure.count(Node) && "Invalid node!"); 96 return PredClosure[Node].begin(); 97 } 98 pred_closure_iterator_ty pred_closure_end(change_ty Node) { 99 assert(PredClosure.count(Node) && "Invalid node!"); 100 return PredClosure[Node].end(); 101 } 102 103 succ_iterator_ty succ_begin(change_ty Node) { 104 assert(Successors.count(Node) && "Invalid node!"); 105 return Successors[Node].begin(); 106 } 107 succ_iterator_ty succ_end(change_ty Node) { 108 assert(Successors.count(Node) && "Invalid node!"); 109 return Successors[Node].end(); 110 } 111 112 succ_closure_iterator_ty succ_closure_begin(change_ty Node) { 113 assert(SuccClosure.count(Node) && "Invalid node!"); 114 return SuccClosure[Node].begin(); 115 } 116 succ_closure_iterator_ty succ_closure_end(change_ty Node) { 117 assert(SuccClosure.count(Node) && "Invalid node!"); 118 return SuccClosure[Node].end(); 119 } 120 121 void UpdatedSearchState(const changeset_ty &Changes, 122 const changesetlist_ty &Sets, 123 const changeset_ty &Required) { 124 DDA.UpdatedSearchState(Changes, Sets, Required); 125 } 126 127 /// ExecuteOneTest - Execute a single test predicate on the change set \p S. 128 bool ExecuteOneTest(const changeset_ty &S) { 129 // Check dependencies invariant. 130 DEBUG({ 131 for (changeset_ty::const_iterator it = S.begin(), 132 ie = S.end(); it != ie; ++it) 133 for (succ_iterator_ty it2 = succ_begin(*it), 134 ie2 = succ_end(*it); it2 != ie2; ++it2) 135 assert(S.count(*it2) && "Attempt to run invalid changeset!"); 136 }); 137 138 return DDA.ExecuteOneTest(S); 139 } 140 141 public: 142 DAGDeltaAlgorithmImpl(DAGDeltaAlgorithm &_DDA, 143 const changeset_ty &_Changes, 144 const std::vector<edge_ty> &_Dependencies); 145 146 changeset_ty Run(); 147 148 /// GetTestResult - Get the test result for the active set \p Changes with 149 /// \p Required changes from the cache, executing the test if necessary. 150 /// 151 /// \param Changes - The set of active changes being minimized, which should 152 /// have their pred closure included in the test. 153 /// \param Required - The set of changes which have previously been 154 /// established to be required. 155 /// \return - The test result. 156 bool GetTestResult(const changeset_ty &Changes, const changeset_ty &Required); 157 }; 158 159 /// Helper object for minimizing an active set of changes. 160 class DeltaActiveSetHelper : public DeltaAlgorithm { 161 DAGDeltaAlgorithmImpl &DDAI; 162 163 const changeset_ty &Required; 164 165 protected: 166 /// UpdatedSearchState - Callback used when the search state changes. 167 void UpdatedSearchState(const changeset_ty &Changes, 168 const changesetlist_ty &Sets) override { 169 DDAI.UpdatedSearchState(Changes, Sets, Required); 170 } 171 172 bool ExecuteOneTest(const changeset_ty &S) override { 173 return DDAI.GetTestResult(S, Required); 174 } 175 176 public: 177 DeltaActiveSetHelper(DAGDeltaAlgorithmImpl &_DDAI, 178 const changeset_ty &_Required) 179 : DDAI(_DDAI), Required(_Required) {} 180 }; 181 182 } 183 184 DAGDeltaAlgorithmImpl::DAGDeltaAlgorithmImpl(DAGDeltaAlgorithm &_DDA, 185 const changeset_ty &_Changes, 186 const std::vector<edge_ty> 187 &_Dependencies) 188 : DDA(_DDA), 189 Changes(_Changes), 190 Dependencies(_Dependencies) 191 { 192 for (changeset_ty::const_iterator it = Changes.begin(), 193 ie = Changes.end(); it != ie; ++it) { 194 Predecessors.insert(std::make_pair(*it, std::vector<change_ty>())); 195 Successors.insert(std::make_pair(*it, std::vector<change_ty>())); 196 } 197 for (std::vector<edge_ty>::const_iterator it = Dependencies.begin(), 198 ie = Dependencies.end(); it != ie; ++it) { 199 Predecessors[it->second].push_back(it->first); 200 Successors[it->first].push_back(it->second); 201 } 202 203 // Compute the roots. 204 for (changeset_ty::const_iterator it = Changes.begin(), 205 ie = Changes.end(); it != ie; ++it) 206 if (succ_begin(*it) == succ_end(*it)) 207 Roots.push_back(*it); 208 209 // Pre-compute the closure of the successor relation. 210 std::vector<change_ty> Worklist(Roots.begin(), Roots.end()); 211 while (!Worklist.empty()) { 212 change_ty Change = Worklist.back(); 213 Worklist.pop_back(); 214 215 std::set<change_ty> &ChangeSuccs = SuccClosure[Change]; 216 for (pred_iterator_ty it = pred_begin(Change), 217 ie = pred_end(Change); it != ie; ++it) { 218 SuccClosure[*it].insert(Change); 219 SuccClosure[*it].insert(ChangeSuccs.begin(), ChangeSuccs.end()); 220 Worklist.push_back(*it); 221 } 222 } 223 224 // Invert to form the predecessor closure map. 225 for (changeset_ty::const_iterator it = Changes.begin(), 226 ie = Changes.end(); it != ie; ++it) 227 PredClosure.insert(std::make_pair(*it, std::set<change_ty>())); 228 for (changeset_ty::const_iterator it = Changes.begin(), 229 ie = Changes.end(); it != ie; ++it) 230 for (succ_closure_iterator_ty it2 = succ_closure_begin(*it), 231 ie2 = succ_closure_end(*it); it2 != ie2; ++it2) 232 PredClosure[*it2].insert(*it); 233 234 // Dump useful debug info. 235 DEBUG({ 236 llvm::errs() << "-- DAGDeltaAlgorithmImpl --\n"; 237 llvm::errs() << "Changes: ["; 238 for (changeset_ty::const_iterator it = Changes.begin(), 239 ie = Changes.end(); it != ie; ++it) { 240 if (it != Changes.begin()) llvm::errs() << ", "; 241 llvm::errs() << *it; 242 243 if (succ_begin(*it) != succ_end(*it)) { 244 llvm::errs() << "("; 245 for (succ_iterator_ty it2 = succ_begin(*it), 246 ie2 = succ_end(*it); it2 != ie2; ++it2) { 247 if (it2 != succ_begin(*it)) llvm::errs() << ", "; 248 llvm::errs() << "->" << *it2; 249 } 250 llvm::errs() << ")"; 251 } 252 } 253 llvm::errs() << "]\n"; 254 255 llvm::errs() << "Roots: ["; 256 for (std::vector<change_ty>::const_iterator it = Roots.begin(), 257 ie = Roots.end(); it != ie; ++it) { 258 if (it != Roots.begin()) llvm::errs() << ", "; 259 llvm::errs() << *it; 260 } 261 llvm::errs() << "]\n"; 262 263 llvm::errs() << "Predecessor Closure:\n"; 264 for (changeset_ty::const_iterator it = Changes.begin(), 265 ie = Changes.end(); it != ie; ++it) { 266 llvm::errs() << format(" %-4d: [", *it); 267 for (pred_closure_iterator_ty it2 = pred_closure_begin(*it), 268 ie2 = pred_closure_end(*it); it2 != ie2; ++it2) { 269 if (it2 != pred_closure_begin(*it)) llvm::errs() << ", "; 270 llvm::errs() << *it2; 271 } 272 llvm::errs() << "]\n"; 273 } 274 275 llvm::errs() << "Successor Closure:\n"; 276 for (changeset_ty::const_iterator it = Changes.begin(), 277 ie = Changes.end(); it != ie; ++it) { 278 llvm::errs() << format(" %-4d: [", *it); 279 for (succ_closure_iterator_ty it2 = succ_closure_begin(*it), 280 ie2 = succ_closure_end(*it); it2 != ie2; ++it2) { 281 if (it2 != succ_closure_begin(*it)) llvm::errs() << ", "; 282 llvm::errs() << *it2; 283 } 284 llvm::errs() << "]\n"; 285 } 286 287 llvm::errs() << "\n\n"; 288 }); 289 } 290 291 bool DAGDeltaAlgorithmImpl::GetTestResult(const changeset_ty &Changes, 292 const changeset_ty &Required) { 293 changeset_ty Extended(Required); 294 Extended.insert(Changes.begin(), Changes.end()); 295 for (changeset_ty::const_iterator it = Changes.begin(), 296 ie = Changes.end(); it != ie; ++it) 297 Extended.insert(pred_closure_begin(*it), pred_closure_end(*it)); 298 299 if (FailedTestsCache.count(Extended)) 300 return false; 301 302 bool Result = ExecuteOneTest(Extended); 303 if (!Result) 304 FailedTestsCache.insert(Extended); 305 306 return Result; 307 } 308 309 DAGDeltaAlgorithm::changeset_ty 310 DAGDeltaAlgorithmImpl::Run() { 311 // The current set of changes we are minimizing, starting at the roots. 312 changeset_ty CurrentSet(Roots.begin(), Roots.end()); 313 314 // The set of required changes. 315 changeset_ty Required; 316 317 // Iterate until the active set of changes is empty. Convergence is guaranteed 318 // assuming input was a DAG. 319 // 320 // Invariant: CurrentSet intersect Required == {} 321 // Invariant: Required == (Required union succ*(Required)) 322 while (!CurrentSet.empty()) { 323 DEBUG({ 324 llvm::errs() << "DAG_DD - " << CurrentSet.size() << " active changes, " 325 << Required.size() << " required changes\n"; 326 }); 327 328 // Minimize the current set of changes. 329 DeltaActiveSetHelper Helper(*this, Required); 330 changeset_ty CurrentMinSet = Helper.Run(CurrentSet); 331 332 // Update the set of required changes. Since 333 // CurrentMinSet subset CurrentSet 334 // and after the last iteration, 335 // succ(CurrentSet) subset Required 336 // then 337 // succ(CurrentMinSet) subset Required 338 // and our invariant on Required is maintained. 339 Required.insert(CurrentMinSet.begin(), CurrentMinSet.end()); 340 341 // Replace the current set with the predecssors of the minimized set of 342 // active changes. 343 CurrentSet.clear(); 344 for (changeset_ty::const_iterator it = CurrentMinSet.begin(), 345 ie = CurrentMinSet.end(); it != ie; ++it) 346 CurrentSet.insert(pred_begin(*it), pred_end(*it)); 347 348 // FIXME: We could enforce CurrentSet intersect Required == {} here if we 349 // wanted to protect against cyclic graphs. 350 } 351 352 return Required; 353 } 354 355 void DAGDeltaAlgorithm::anchor() { 356 } 357 358 DAGDeltaAlgorithm::changeset_ty 359 DAGDeltaAlgorithm::Run(const changeset_ty &Changes, 360 const std::vector<edge_ty> &Dependencies) { 361 return DAGDeltaAlgorithmImpl(*this, Changes, Dependencies).Run(); 362 } 363