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