LCOV - code coverage report
Current view: top level - lib/Support - DAGDeltaAlgorithm.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 75 77 97.4 %
Date: 2017-09-14 15:23:50 Functions: 7 10 70.0 %
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          21 : 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          80 :     return Predecessors[Node].begin();
      85             :   }
      86             :   pred_iterator_ty pred_end(change_ty Node) {
      87             :     assert(Predecessors.count(Node) && "Invalid node!");
      88          80 :     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         216 :     return PredClosure[Node].begin();
      94             :   }
      95             :   pred_closure_iterator_ty pred_closure_end(change_ty Node) {
      96             :     assert(PredClosure.count(Node) && "Invalid node!");
      97         216 :     return PredClosure[Node].end();
      98             :   }
      99             :   
     100             :   succ_iterator_ty succ_begin(change_ty Node) {
     101             :     assert(Successors.count(Node) && "Invalid node!");
     102          60 :     return Successors[Node].begin();
     103             :   }
     104             :   succ_iterator_ty succ_end(change_ty Node) {
     105             :     assert(Successors.count(Node) && "Invalid node!");
     106          60 :     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          60 :     return SuccClosure[Node].begin();
     112             :   }
     113             :   succ_closure_iterator_ty succ_closure_end(change_ty Node) {
     114             :     assert(SuccClosure.count(Node) && "Invalid node!");
     115          60 :     return SuccClosure[Node].end();
     116             :   }
     117             : 
     118             :   void UpdatedSearchState(const changeset_ty &Changes,
     119             :                           const changesetlist_ty &Sets,
     120             :                           const changeset_ty &Required) {
     121          18 :     DDA.UpdatedSearchState(Changes, Sets, Required);
     122             :   }
     123             : 
     124             :   /// ExecuteOneTest - Execute a single test predicate on the change set \p S.
     125             :   bool ExecuteOneTest(const changeset_ty &S) {
     126             :     // Check dependencies invariant.
     127             :     DEBUG({
     128             :         for (changeset_ty::const_iterator it = S.begin(),
     129             :                ie = S.end(); it != ie; ++it)
     130             :           for (succ_iterator_ty it2 = succ_begin(*it),
     131             :                  ie2 = succ_end(*it); it2 != ie2; ++it2)
     132             :             assert(S.count(*it2) && "Attempt to run invalid changeset!");
     133             :       });
     134             : 
     135          44 :     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          36 :     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          14 :       : 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          21 :     : DDA(DDA) {
     184           3 :   for (changeset_ty::const_iterator it = Changes.begin(),
     185           3 :          ie = Changes.end(); it != ie; ++it) {
     186         210 :     Predecessors.insert(std::make_pair(*it, std::vector<change_ty>()));
     187         210 :     Successors.insert(std::make_pair(*it, std::vector<change_ty>()));
     188             :   }
     189           6 :   for (std::vector<edge_ty>::const_iterator it = Dependencies.begin(),
     190          18 :          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           3 :   for (changeset_ty::const_iterator it = Changes.begin(),
     197           3 :          ie = Changes.end(); it != ie; ++it)
     198         150 :     if (succ_begin(*it) == succ_end(*it))
     199          42 :       Roots.push_back(*it);
     200             : 
     201             :   // Pre-compute the closure of the successor relation.
     202          15 :   std::vector<change_ty> Worklist(Roots.begin(), Roots.end());
     203          63 :   while (!Worklist.empty()) {
     204          30 :     change_ty Change = Worklist.back();
     205          30 :     Worklist.pop_back();
     206             : 
     207          30 :     std::set<change_ty> &ChangeSuccs = SuccClosure[Change];
     208          60 :     for (pred_iterator_ty it = pred_begin(Change), 
     209          99 :            ie = pred_end(Change); it != ie; ++it) {
     210          18 :       SuccClosure[*it].insert(Change);
     211          36 :       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           3 :   for (changeset_ty::const_iterator it = Changes.begin(),
     218           3 :          ie = Changes.end(); it != ie; ++it)
     219         210 :     PredClosure.insert(std::make_pair(*it, std::set<change_ty>()));
     220           3 :   for (changeset_ty::const_iterator it = Changes.begin(),
     221           3 :          ie = Changes.end(); it != ie; ++it)
     222          60 :     for (succ_closure_iterator_ty it2 = succ_closure_begin(*it),
     223          60 :            ie2 = succ_closure_end(*it); it2 != ie2; ++it2)
     224          33 :       PredClosure[*it2].insert(*it);
     225             :   
     226             :   // Dump useful debug info.
     227             :   DEBUG({
     228             :       llvm::errs() << "-- DAGDeltaAlgorithmImpl --\n";
     229             :       llvm::errs() << "Changes: [";
     230             :       for (changeset_ty::const_iterator it = Changes.begin(),
     231             :              ie = Changes.end(); it != ie; ++it) {
     232             :         if (it != Changes.begin()) 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),
     238             :                  ie2 = succ_end(*it); it2 != ie2; ++it2) {
     239             :             if (it2 != succ_begin(*it)) llvm::errs() << ", ";
     240             :             llvm::errs() << "->" << *it2;
     241             :           }
     242             :           llvm::errs() << ")";
     243             :         }
     244             :       }
     245             :       llvm::errs() << "]\n";
     246             : 
     247             :       llvm::errs() << "Roots: [";
     248             :       for (std::vector<change_ty>::const_iterator it = Roots.begin(),
     249             :              ie = Roots.end(); it != ie; ++it) {
     250             :         if (it != Roots.begin()) llvm::errs() << ", ";
     251             :         llvm::errs() << *it;
     252             :       }
     253             :       llvm::errs() << "]\n";
     254             : 
     255             :       llvm::errs() << "Predecessor Closure:\n";
     256             :       for (changeset_ty::const_iterator it = Changes.begin(),
     257             :              ie = Changes.end(); it != ie; ++it) {
     258             :         llvm::errs() << format("  %-4d: [", *it);
     259             :         for (pred_closure_iterator_ty it2 = pred_closure_begin(*it),
     260             :                ie2 = pred_closure_end(*it); it2 != ie2; ++it2) {
     261             :           if (it2 != pred_closure_begin(*it)) llvm::errs() << ", ";
     262             :           llvm::errs() << *it2;
     263             :         }
     264             :         llvm::errs() << "]\n";
     265             :       }
     266             :       
     267             :       llvm::errs() << "Successor Closure:\n";
     268             :       for (changeset_ty::const_iterator it = Changes.begin(),
     269             :              ie = Changes.end(); it != ie; ++it) {
     270             :         llvm::errs() << format("  %-4d: [", *it);
     271             :         for (succ_closure_iterator_ty it2 = succ_closure_begin(*it),
     272             :                ie2 = succ_closure_end(*it); it2 != ie2; ++it2) {
     273             :           if (it2 != succ_closure_begin(*it)) llvm::errs() << ", ";
     274             :           llvm::errs() << *it2;
     275             :         }
     276             :         llvm::errs() << "]\n";
     277             :       }
     278             : 
     279             :       llvm::errs() << "\n\n";
     280             :     });
     281           3 : }
     282             : 
     283          44 : bool DAGDeltaAlgorithmImpl::GetTestResult(const changeset_ty &Changes,
     284             :                                           const changeset_ty &Required) {
     285          88 :   changeset_ty Extended(Required);
     286         132 :   Extended.insert(Changes.begin(), Changes.end());
     287          44 :   for (changeset_ty::const_iterator it = Changes.begin(),
     288          44 :          ie = Changes.end(); it != ie; ++it)
     289         540 :     Extended.insert(pred_closure_begin(*it), pred_closure_end(*it));
     290             : 
     291          88 :   if (FailedTestsCache.count(Extended))
     292             :     return false;
     293             : 
     294          88 :   bool Result = ExecuteOneTest(Extended);
     295          44 :   if (!Result)
     296          36 :     FailedTestsCache.insert(Extended);
     297             : 
     298             :   return Result;
     299             : }
     300             : 
     301             : DAGDeltaAlgorithm::changeset_ty
     302           3 : DAGDeltaAlgorithmImpl::Run() {
     303             :   // The current set of changes we are minimizing, starting at the roots.
     304          12 :   changeset_ty CurrentSet(Roots.begin(), Roots.end());
     305             : 
     306             :   // The set of required changes.
     307             :   changeset_ty Required;
     308             : 
     309             :   // Iterate until the active set of changes is empty. Convergence is guaranteed
     310             :   // assuming input was a DAG.
     311             :   //
     312             :   // Invariant:  CurrentSet intersect Required == {}
     313             :   // Invariant:  Required == (Required union succ*(Required))
     314          17 :   while (!CurrentSet.empty()) {
     315             :     DEBUG({
     316             :         llvm::errs() << "DAG_DD - " << CurrentSet.size() << " active changes, "
     317             :                      << Required.size() << " required changes\n";
     318             :       });
     319             : 
     320             :     // Minimize the current set of changes.
     321          14 :     DeltaActiveSetHelper Helper(*this, Required);
     322          14 :     changeset_ty CurrentMinSet = Helper.Run(CurrentSet);
     323             : 
     324             :     // Update the set of required changes. Since
     325             :     //   CurrentMinSet subset CurrentSet
     326             :     // and after the last iteration,
     327             :     //   succ(CurrentSet) subset Required
     328             :     // then
     329             :     //   succ(CurrentMinSet) subset Required
     330             :     // and our invariant on Required is maintained.
     331          21 :     Required.insert(CurrentMinSet.begin(), CurrentMinSet.end());
     332             : 
     333             :     // Replace the current set with the predecssors of the minimized set of
     334             :     // active changes.
     335           7 :     CurrentSet.clear();
     336           7 :     for (changeset_ty::const_iterator it = CurrentMinSet.begin(),
     337           7 :            ie = CurrentMinSet.end(); it != ie; ++it)
     338          50 :       CurrentSet.insert(pred_begin(*it), pred_end(*it));
     339             : 
     340             :     // FIXME: We could enforce CurrentSet intersect Required == {} here if we
     341             :     // wanted to protect against cyclic graphs.
     342             :   }
     343             : 
     344           3 :   return Required;
     345             : }
     346             : 
     347           0 : void DAGDeltaAlgorithm::anchor() {
     348           0 : }
     349             : 
     350             : DAGDeltaAlgorithm::changeset_ty
     351           3 : DAGDeltaAlgorithm::Run(const changeset_ty &Changes,
     352             :                        const std::vector<edge_ty> &Dependencies) {
     353           3 :   return DAGDeltaAlgorithmImpl(*this, Changes, Dependencies).Run();
     354             : }

Generated by: LCOV version 1.13