LCOV - code coverage report
Current view: top level - lib/Support - DAGDeltaAlgorithm.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 59 67 88.1 %
Date: 2018-10-20 13:21:21 Functions: 6 9 66.7 %
Legend: Lines: hit not hit

          Line data    Source code
       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             :   std::vector<change_ty> Roots;
      67             : 
      68             :   /// Cache of failed test results. Successful test results are never cached
      69             :   /// since we always reduce following a success. We maintain an independent
      70             :   /// cache from that used by the individual delta passes because we may get
      71             :   /// hits across multiple individual delta invocations.
      72             :   mutable std::set<changeset_ty> FailedTestsCache;
      73             : 
      74             :   // FIXME: Gross.
      75             :   std::map<change_ty, std::vector<change_ty> > Predecessors;
      76             :   std::map<change_ty, std::vector<change_ty> > Successors;
      77             : 
      78             :   std::map<change_ty, std::set<change_ty> > PredClosure;
      79             :   std::map<change_ty, std::set<change_ty> > SuccClosure;
      80             : 
      81             : private:
      82             :   pred_iterator_ty pred_begin(change_ty Node) {
      83             :     assert(Predecessors.count(Node) && "Invalid node!");
      84          40 :     return Predecessors[Node].begin();
      85             :   }
      86             :   pred_iterator_ty pred_end(change_ty Node) {
      87             :     assert(Predecessors.count(Node) && "Invalid node!");
      88          40 :     return Predecessors[Node].end();
      89             :   }
      90             : 
      91             :   pred_closure_iterator_ty pred_closure_begin(change_ty Node) {
      92             :     assert(PredClosure.count(Node) && "Invalid node!");
      93         108 :     return PredClosure[Node].begin();
      94             :   }
      95             :   pred_closure_iterator_ty pred_closure_end(change_ty Node) {
      96             :     assert(PredClosure.count(Node) && "Invalid node!");
      97         108 :     return PredClosure[Node].end();
      98             :   }
      99             : 
     100             :   succ_iterator_ty succ_begin(change_ty Node) {
     101             :     assert(Successors.count(Node) && "Invalid node!");
     102          30 :     return Successors[Node].begin();
     103             :   }
     104             :   succ_iterator_ty succ_end(change_ty Node) {
     105             :     assert(Successors.count(Node) && "Invalid node!");
     106          30 :     return Successors[Node].end();
     107             :   }
     108             : 
     109             :   succ_closure_iterator_ty succ_closure_begin(change_ty Node) {
     110             :     assert(SuccClosure.count(Node) && "Invalid node!");
     111          30 :     return SuccClosure[Node].begin();
     112             :   }
     113             :   succ_closure_iterator_ty succ_closure_end(change_ty Node) {
     114             :     assert(SuccClosure.count(Node) && "Invalid node!");
     115          30 :     return SuccClosure[Node].end();
     116             :   }
     117             : 
     118           0 :   void UpdatedSearchState(const changeset_ty &Changes,
     119             :                           const changesetlist_ty &Sets,
     120             :                           const changeset_ty &Required) {
     121           0 :     DDA.UpdatedSearchState(Changes, Sets, Required);
     122           0 :   }
     123             : 
     124             :   /// ExecuteOneTest - Execute a single test predicate on the change set \p S.
     125           0 :   bool ExecuteOneTest(const changeset_ty &S) {
     126             :     // Check dependencies invariant.
     127             :     LLVM_DEBUG({
     128             :       for (changeset_ty::const_iterator it = S.begin(), ie = S.end(); it != ie;
     129             :            ++it)
     130             :         for (succ_iterator_ty it2 = succ_begin(*it), ie2 = succ_end(*it);
     131             :              it2 != ie2; ++it2)
     132             :           assert(S.count(*it2) && "Attempt to run invalid changeset!");
     133             :     });
     134             : 
     135           0 :     return DDA.ExecuteOneTest(S);
     136             :   }
     137             : 
     138             : public:
     139             :   DAGDeltaAlgorithmImpl(DAGDeltaAlgorithm &DDA, const changeset_ty &Changes,
     140             :                         const std::vector<edge_ty> &Dependencies);
     141             : 
     142             :   changeset_ty Run();
     143             : 
     144             :   /// GetTestResult - Get the test result for the active set \p Changes with
     145             :   /// \p Required changes from the cache, executing the test if necessary.
     146             :   ///
     147             :   /// \param Changes - The set of active changes being minimized, which should
     148             :   /// have their pred closure included in the test.
     149             :   /// \param Required - The set of changes which have previously been
     150             :   /// established to be required.
     151             :   /// \return - The test result.
     152             :   bool GetTestResult(const changeset_ty &Changes, const changeset_ty &Required);
     153             : };
     154             : 
     155             : /// Helper object for minimizing an active set of changes.
     156           7 : class DeltaActiveSetHelper : public DeltaAlgorithm {
     157             :   DAGDeltaAlgorithmImpl &DDAI;
     158             : 
     159             :   const changeset_ty &Required;
     160             : 
     161             : protected:
     162             :   /// UpdatedSearchState - Callback used when the search state changes.
     163          18 :   void UpdatedSearchState(const changeset_ty &Changes,
     164             :                                   const changesetlist_ty &Sets) override {
     165          18 :     DDAI.UpdatedSearchState(Changes, Sets, Required);
     166          18 :   }
     167             : 
     168          44 :   bool ExecuteOneTest(const changeset_ty &S) override {
     169          44 :     return DDAI.GetTestResult(S, Required);
     170             :   }
     171             : 
     172             : public:
     173             :   DeltaActiveSetHelper(DAGDeltaAlgorithmImpl &DDAI,
     174             :                        const changeset_ty &Required)
     175           7 :       : DDAI(DDAI), Required(Required) {}
     176             : };
     177             : 
     178             : }
     179             : 
     180           3 : DAGDeltaAlgorithmImpl::DAGDeltaAlgorithmImpl(
     181             :     DAGDeltaAlgorithm &DDA, const changeset_ty &Changes,
     182           3 :     const std::vector<edge_ty> &Dependencies)
     183          15 :     : DDA(DDA) {
     184             :   for (changeset_ty::const_iterator it = Changes.begin(),
     185          33 :          ie = Changes.end(); it != ie; ++it) {
     186          30 :     Predecessors.insert(std::make_pair(*it, std::vector<change_ty>()));
     187          60 :     Successors.insert(std::make_pair(*it, std::vector<change_ty>()));
     188             :   }
     189           3 :   for (std::vector<edge_ty>::const_iterator it = Dependencies.begin(),
     190          12 :          ie = Dependencies.end(); it != ie; ++it) {
     191           9 :     Predecessors[it->second].push_back(it->first);
     192           9 :     Successors[it->first].push_back(it->second);
     193             :   }
     194             : 
     195             :   // Compute the roots.
     196             :   for (changeset_ty::const_iterator it = Changes.begin(),
     197          33 :          ie = Changes.end(); it != ie; ++it)
     198          30 :     if (succ_begin(*it) == succ_end(*it))
     199          21 :       Roots.push_back(*it);
     200             : 
     201             :   // Pre-compute the closure of the successor relation.
     202             :   std::vector<change_ty> Worklist(Roots.begin(), Roots.end());
     203          33 :   while (!Worklist.empty()) {
     204          30 :     change_ty Change = Worklist.back();
     205             :     Worklist.pop_back();
     206             : 
     207          30 :     std::set<change_ty> &ChangeSuccs = SuccClosure[Change];
     208          30 :     for (pred_iterator_ty it = pred_begin(Change),
     209          39 :            ie = pred_end(Change); it != ie; ++it) {
     210           9 :       SuccClosure[*it].insert(Change);
     211           9 :       SuccClosure[*it].insert(ChangeSuccs.begin(), ChangeSuccs.end());
     212           9 :       Worklist.push_back(*it);
     213             :     }
     214             :   }
     215             : 
     216             :   // Invert to form the predecessor closure map.
     217             :   for (changeset_ty::const_iterator it = Changes.begin(),
     218          33 :          ie = Changes.end(); it != ie; ++it)
     219          60 :     PredClosure.insert(std::make_pair(*it, std::set<change_ty>()));
     220             :   for (changeset_ty::const_iterator it = Changes.begin(),
     221          33 :          ie = Changes.end(); it != ie; ++it)
     222          30 :     for (succ_closure_iterator_ty it2 = succ_closure_begin(*it),
     223          41 :            ie2 = succ_closure_end(*it); it2 != ie2; ++it2)
     224          11 :       PredClosure[*it2].insert(*it);
     225             : 
     226             :   // Dump useful debug info.
     227             :   LLVM_DEBUG({
     228             :     llvm::errs() << "-- DAGDeltaAlgorithmImpl --\n";
     229             :     llvm::errs() << "Changes: [";
     230             :     for (changeset_ty::const_iterator it = Changes.begin(), ie = Changes.end();
     231             :          it != ie; ++it) {
     232             :       if (it != Changes.begin())
     233             :         llvm::errs() << ", ";
     234             :       llvm::errs() << *it;
     235             : 
     236             :       if (succ_begin(*it) != succ_end(*it)) {
     237             :         llvm::errs() << "(";
     238             :         for (succ_iterator_ty it2 = succ_begin(*it), ie2 = succ_end(*it);
     239             :              it2 != ie2; ++it2) {
     240             :           if (it2 != succ_begin(*it))
     241             :             llvm::errs() << ", ";
     242             :           llvm::errs() << "->" << *it2;
     243             :         }
     244             :         llvm::errs() << ")";
     245             :       }
     246             :     }
     247             :     llvm::errs() << "]\n";
     248             : 
     249             :     llvm::errs() << "Roots: [";
     250             :     for (std::vector<change_ty>::const_iterator it = Roots.begin(),
     251             :                                                 ie = Roots.end();
     252             :          it != ie; ++it) {
     253             :       if (it != Roots.begin())
     254             :         llvm::errs() << ", ";
     255             :       llvm::errs() << *it;
     256             :     }
     257             :     llvm::errs() << "]\n";
     258             : 
     259             :     llvm::errs() << "Predecessor Closure:\n";
     260             :     for (changeset_ty::const_iterator it = Changes.begin(), ie = Changes.end();
     261             :          it != ie; ++it) {
     262             :       llvm::errs() << format("  %-4d: [", *it);
     263             :       for (pred_closure_iterator_ty it2 = pred_closure_begin(*it),
     264             :                                     ie2 = pred_closure_end(*it);
     265             :            it2 != ie2; ++it2) {
     266             :         if (it2 != pred_closure_begin(*it))
     267             :           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(), ie = Changes.end();
     275             :          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);
     279             :            it2 != ie2; ++it2) {
     280             :         if (it2 != succ_closure_begin(*it))
     281             :           llvm::errs() << ", ";
     282             :         llvm::errs() << *it2;
     283             :       }
     284             :       llvm::errs() << "]\n";
     285             :     }
     286             : 
     287             :     llvm::errs() << "\n\n";
     288             :   });
     289           3 : }
     290             : 
     291          44 : bool DAGDeltaAlgorithmImpl::GetTestResult(const changeset_ty &Changes,
     292             :                                           const changeset_ty &Required) {
     293             :   changeset_ty Extended(Required);
     294          44 :   Extended.insert(Changes.begin(), Changes.end());
     295             :   for (changeset_ty::const_iterator it = Changes.begin(),
     296         152 :          ie = Changes.end(); it != ie; ++it)
     297         108 :     Extended.insert(pred_closure_begin(*it), pred_closure_end(*it));
     298             : 
     299             :   if (FailedTestsCache.count(Extended))
     300           0 :     return false;
     301             : 
     302          44 :   bool Result = ExecuteOneTest(Extended);
     303          44 :   if (!Result)
     304             :     FailedTestsCache.insert(Extended);
     305             : 
     306             :   return Result;
     307             : }
     308             : 
     309             : DAGDeltaAlgorithm::changeset_ty
     310           3 : DAGDeltaAlgorithmImpl::Run() {
     311             :   // The current set of changes we are minimizing, starting at the roots.
     312           3 :   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          10 :   while (!CurrentSet.empty()) {
     323             :     LLVM_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           7 :     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           7 :     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          17 :            ie = CurrentMinSet.end(); it != ie; ++it)
     346          10 :       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           3 :   return Required;
     353             : }
     354             : 
     355           0 : void DAGDeltaAlgorithm::anchor() {
     356           0 : }
     357             : 
     358             : DAGDeltaAlgorithm::changeset_ty
     359           3 : DAGDeltaAlgorithm::Run(const changeset_ty &Changes,
     360             :                        const std::vector<edge_ty> &Dependencies) {
     361           3 :   return DAGDeltaAlgorithmImpl(*this, Changes, Dependencies).Run();
     362             : }

Generated by: LCOV version 1.13