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