lib/Support/DAGDeltaAlgorithm.cpp

   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 }