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