llvm/lib/Support/DAGDeltaAlgorithm.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-exception
   6 //===----------------------------------------------------------------------===//
   7 //
   8 // The algorithm we use attempts to exploit the dependency information by
   9 // minimizing top-down. We start by constructing an initial root set R, and
  10 // 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 we
  20 // try to find high-level nodes that can be eliminated with all of their
  21 // dependents.
  22 //
  23 // FIXME: The current algorithm doesn't actually provide a strong guarantee
  24 // about the minimality of the result. The problem is that after adding nodes to
  25 // the required set, we no longer consider them for elimination. For strictly
  26 // well formed predicates, this doesn't happen, but it commonly occurs in
  27 // practice when there are unmodelled dependencies. I believe we can resolve
  28 // this by allowing the required set to be minimized as well, but need more test
  29 // 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 <algorithm>
  39 #include <cassert>
  40 #include <map>
  41 using namespace llvm;
  42
  43 #define DEBUG_TYPE "dag-delta"
  44
  45 namespace {
  46
  47 class DAGDeltaAlgorithmImpl {
  48   friend class DeltaActiveSetHelper;
  49
  50 public:
  51   typedef DAGDeltaAlgorithm::change_ty change_ty;
  52   typedef DAGDeltaAlgorithm::changeset_ty changeset_ty;
  53   typedef DAGDeltaAlgorithm::changesetlist_ty changesetlist_ty;
  54   typedef DAGDeltaAlgorithm::edge_ty edge_ty;
  55
  56 private:
  57   typedef std::vector<change_ty>::iterator pred_iterator_ty;
  58   typedef std::vector<change_ty>::iterator succ_iterator_ty;
  59   typedef std::set<change_ty>::iterator pred_closure_iterator_ty;
  60   typedef std::set<change_ty>::iterator succ_closure_iterator_ty;
  61
  62   DAGDeltaAlgorithm &DDA;
  63
  64   std::vector<change_ty> Roots;
  65
  66   /// Cache of failed test results. Successful test results are never cached
  67   /// since we always reduce following a success. We maintain an independent
  68   /// cache from that used by the individual delta passes because we may get
  69   /// hits across multiple individual delta invocations.
  70   mutable std::set<changeset_ty> FailedTestsCache;
  71
  72   // FIXME: Gross.
  73   std::map<change_ty, std::vector<change_ty> > Predecessors;
  74   std::map<change_ty, std::vector<change_ty> > Successors;
  75
  76   std::map<change_ty, std::set<change_ty> > PredClosure;
  77   std::map<change_ty, std::set<change_ty> > SuccClosure;
  78
  79 private:
  80   pred_iterator_ty pred_begin(change_ty Node) {
  81     assert(Predecessors.count(Node) && "Invalid node!");
  82     return Predecessors[Node].begin();
  83   }
  84   pred_iterator_ty pred_end(change_ty Node) {
  85     assert(Predecessors.count(Node) && "Invalid node!");
  86     return Predecessors[Node].end();
  87   }
  88
  89   pred_closure_iterator_ty pred_closure_begin(change_ty Node) {
  90     assert(PredClosure.count(Node) && "Invalid node!");
  91     return PredClosure[Node].begin();
  92   }
  93   pred_closure_iterator_ty pred_closure_end(change_ty Node) {
  94     assert(PredClosure.count(Node) && "Invalid node!");
  95     return PredClosure[Node].end();
  96   }
  97
  98   succ_iterator_ty succ_begin(change_ty Node) {
  99     assert(Successors.count(Node) && "Invalid node!");
 100     return Successors[Node].begin();
 101   }
 102   succ_iterator_ty succ_end(change_ty Node) {
 103     assert(Successors.count(Node) && "Invalid node!");
 104     return Successors[Node].end();
 105   }
 106
 107   succ_closure_iterator_ty succ_closure_begin(change_ty Node) {
 108     assert(SuccClosure.count(Node) && "Invalid node!");
 109     return SuccClosure[Node].begin();
 110   }
 111   succ_closure_iterator_ty succ_closure_end(change_ty Node) {
 112     assert(SuccClosure.count(Node) && "Invalid node!");
 113     return SuccClosure[Node].end();
 114   }
 115
 116   void UpdatedSearchState(const changeset_ty &Changes,
 117                           const changesetlist_ty &Sets,
 118                           const changeset_ty &Required) {
 119     DDA.UpdatedSearchState(Changes, Sets, Required);
 120   }
 121
 122   /// ExecuteOneTest - Execute a single test predicate on the change set \p S.
 123   bool ExecuteOneTest(const changeset_ty &S) {
 124     // Check dependencies invariant.
 125     LLVM_DEBUG({
 126       for (changeset_ty::const_iterator it = S.begin(), ie = S.end(); it != ie;
 127            ++it)
 128         for (succ_iterator_ty it2 = succ_begin(*it), ie2 = succ_end(*it);
 129              it2 != ie2; ++it2)
 130           assert(S.count(*it2) && "Attempt to run invalid changeset!");
 131     });
 132
 133     return DDA.ExecuteOneTest(S);
 134   }
 135
 136 public:
 137   DAGDeltaAlgorithmImpl(DAGDeltaAlgorithm &DDA, const changeset_ty &Changes,
 138                         const std::vector<edge_ty> &Dependencies);
 139
 140   changeset_ty Run();
 141
 142   /// GetTestResult - Get the test result for the active set \p Changes with
 143   /// \p Required changes from the cache, executing the test if necessary.
 144   ///
 145   /// \param Changes - The set of active changes being minimized, which should
 146   /// have their pred closure included in the test.
 147   /// \param Required - The set of changes which have previously been
 148   /// established to be required.
 149   /// \return - The test result.
 150   bool GetTestResult(const changeset_ty &Changes, const changeset_ty &Required);
 151 };
 152
 153 /// Helper object for minimizing an active set of changes.
 154 class DeltaActiveSetHelper : public DeltaAlgorithm {
 155   DAGDeltaAlgorithmImpl &DDAI;
 156
 157   const changeset_ty &Required;
 158
 159 protected:
 160   /// UpdatedSearchState - Callback used when the search state changes.
 161   void UpdatedSearchState(const changeset_ty &Changes,
 162                                   const changesetlist_ty &Sets) override {
 163     DDAI.UpdatedSearchState(Changes, Sets, Required);
 164   }
 165
 166   bool ExecuteOneTest(const changeset_ty &S) override {
 167     return DDAI.GetTestResult(S, Required);
 168   }
 169
 170 public:
 171   DeltaActiveSetHelper(DAGDeltaAlgorithmImpl &DDAI,
 172                        const changeset_ty &Required)
 173       : DDAI(DDAI), Required(Required) {}
 174 };
 175
 176 } // namespace
 177
 178 DAGDeltaAlgorithmImpl::DAGDeltaAlgorithmImpl(
 179     DAGDeltaAlgorithm &DDA, const changeset_ty &Changes,
 180     const std::vector<edge_ty> &Dependencies)
 181     : DDA(DDA) {
 182   for (change_ty Change : Changes) {
 183     Predecessors.insert(std::make_pair(Change, std::vector<change_ty>()));
 184     Successors.insert(std::make_pair(Change, std::vector<change_ty>()));
 185   }
 186   for (const edge_ty &Dep : Dependencies) {
 187     Predecessors[Dep.second].push_back(Dep.first);
 188     Successors[Dep.first].push_back(Dep.second);
 189   }
 190
 191   // Compute the roots.
 192   for (change_ty Change : Changes)
 193     if (succ_begin(Change) == succ_end(Change))
 194       Roots.push_back(Change);
 195
 196   // Pre-compute the closure of the successor relation.
 197   std::vector<change_ty> Worklist(Roots.begin(), Roots.end());
 198   while (!Worklist.empty()) {
 199     change_ty Change = Worklist.back();
 200     Worklist.pop_back();
 201
 202     std::set<change_ty> &ChangeSuccs = SuccClosure[Change];
 203     for (pred_iterator_ty it = pred_begin(Change),
 204            ie = pred_end(Change); it != ie; ++it) {
 205       SuccClosure[*it].insert(Change);
 206       SuccClosure[*it].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.insert(std::make_pair(Change, std::set<change_ty>()));
 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
 283 bool 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
 300 DAGDeltaAlgorithm::changeset_ty
 301 DAGDeltaAlgorithmImpl::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 guaranteed
 309   // 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. Since
 324     //   CurrentMinSet subset CurrentSet
 325     // and after the last iteration,
 326     //   succ(CurrentSet) subset Required
 327     // then
 328     //   succ(CurrentMinSet) subset Required
 329     // 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 of
 333     // 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 we
 339     // wanted to protect against cyclic graphs.
 340   }
 341
 342   return Required;
 343 }
 344
 345 void DAGDeltaAlgorithm::anchor() {
 346 }
 347
 348 DAGDeltaAlgorithm::changeset_ty
 349 DAGDeltaAlgorithm::Run(const changeset_ty &Changes,
 350                        const std::vector<edge_ty> &Dependencies) {
 351   return DAGDeltaAlgorithmImpl(*this, Changes, Dependencies).Run();
 352 }