diff options
| -rw-r--r-- | include/llvm/ADT/DAGDeltaAlgorithm.h | 73 | ||||
| -rw-r--r-- | lib/Support/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | lib/Support/DAGDeltaAlgorithm.cpp | 357 | ||||
| -rw-r--r-- | unittests/ADT/DAGDeltaAlgorithmTest.cpp | 122 |
4 files changed, 553 insertions, 0 deletions
diff --git a/include/llvm/ADT/DAGDeltaAlgorithm.h b/include/llvm/ADT/DAGDeltaAlgorithm.h new file mode 100644 index 0000000000..de91282dc4 --- /dev/null +++ b/include/llvm/ADT/DAGDeltaAlgorithm.h @@ -0,0 +1,73 @@ +//===--- DAGDeltaAlgorithm.h - A DAG Minimization Algorithm ----*- C++ -*--===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_DAGDELTAALGORITHM_H +#define LLVM_ADT_DAGDELTAALGORITHM_H + +#include <vector> +#include <set> + +namespace llvm { + +/// DAGDeltaAlgorithm - Implements a "delta debugging" algorithm for minimizing +/// directed acyclic graphs using a predicate function. +/// +/// The result of the algorithm is a subset of the input change set which is +/// guaranteed to satisfy the predicate, assuming that the input set did. For +/// well formed predicates, the result set is guaranteed to be such that +/// removing any single element not required by the dependencies on the other +/// elements would falsify the predicate. +/// +/// The DAG should be used to represent dependencies in the changes which are +/// likely to hold across the predicate function. That is, for a particular +/// changeset S and predicate P: +/// +/// P(S) => P(S union pred(S)) +/// +/// The minization algorithm uses this dependency information to attempt to +/// eagerly prune large subsets of changes. As with \see DeltaAlgorithm, the DAG +/// is not required to satisfy this property, but the algorithm will run +/// substantially fewer tests with appropriate dependencies. \see DeltaAlgorithm +/// for more information on the properties which the predicate function itself +/// should satisfy. +class DAGDeltaAlgorithm { +public: + typedef unsigned change_ty; + typedef std::pair<change_ty, change_ty> edge_ty; + + // FIXME: Use a decent data structure. + typedef std::set<change_ty> changeset_ty; + typedef std::vector<changeset_ty> changesetlist_ty; + +public: + /// Run - Minimize the DAG formed by the \arg Changes vertices and the \arg + /// Dependencies edges by executing \see ExecuteOneTest() on subsets of + /// changes and returning the smallest set which still satisfies the test + /// predicate and the input \arg Dependencies. + /// + /// \param Changes The list of changes. + /// + /// \param Dependencies The list of dependencies amongst changes. For each + /// (x,y) in \arg Dependencies, both x and y must be in \arg Changes. The + /// minimization algorithm guarantees that for each tested changed set S, x + /// \in S implies y \in S. It is an error to have cyclic dependencies. + changeset_ty Run(const changeset_ty &Changes, + const std::vector<edge_ty> &Dependencies); + + /// UpdatedSearchState - Callback used when the search state changes. + virtual void UpdatedSearchState(const changeset_ty &Changes, + const changesetlist_ty &Sets, + const changeset_ty &Required) {} + + /// ExecuteOneTest - Execute a single test predicate on the change set \arg S. + virtual bool ExecuteOneTest(const changeset_ty &S) = 0; +}; + +} // end namespace llvm + +#endif diff --git a/lib/Support/CMakeLists.txt b/lib/Support/CMakeLists.txt index f1347f9d0e..366d2f7992 100644 --- a/lib/Support/CMakeLists.txt +++ b/lib/Support/CMakeLists.txt @@ -8,6 +8,7 @@ add_llvm_library(LLVMSupport ConstantRange.cpp Debug.cpp DeltaAlgorithm.cpp + DAGDeltaAlgorithm.cpp Dwarf.cpp ErrorHandling.cpp FileUtilities.cpp diff --git a/lib/Support/DAGDeltaAlgorithm.cpp b/lib/Support/DAGDeltaAlgorithm.cpp new file mode 100644 index 0000000000..4da3fe34c8 --- /dev/null +++ b/lib/Support/DAGDeltaAlgorithm.cpp @@ -0,0 +1,357 @@ +//===--- DAGDeltaAlgorithm.cpp - A DAG Minimization Algorithm --*- C++ -*--===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +//===----------------------------------------------------------------------===// +// +// The algorithm we use attempts to exploit the dependency information by +// minimizing top-down. We start by constructing an initial root set R, and +// then iteratively: +// +// 1. Minimize the set R using the test predicate: +// P'(S) = P(S union pred*(S)) +// +// 2. Extend R to R' = R union pred(R). +// +// until a fixed point is reached. +// +// The idea is that we want to quickly prune entire portions of the graph, so we +// try to find high-level nodes that can be eliminated with all of their +// dependents. +// +// FIXME: The current algorithm doesn't actually provide a strong guarantee +// about the minimality of the result. The problem is that after adding nodes to +// the required set, we no longer consider them for elimination. For strictly +// well formed predicates, this doesn't happen, but it commonly occurs in +// practice when there are unmodelled dependencies. I believe we can resolve +// this by allowing the required set to be minimized as well, but need more test +// cases first. +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/DAGDeltaAlgorithm.h" +#include "llvm/ADT/DeltaAlgorithm.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/Format.h" +#include "llvm/Support/raw_ostream.h" +#include <algorithm> +#include <cassert> +#include <iterator> +#include <map> +using namespace llvm; + +namespace { + +class DAGDeltaAlgorithmImpl { + friend class DeltaActiveSetHelper; + +public: + typedef DAGDeltaAlgorithm::change_ty change_ty; + typedef DAGDeltaAlgorithm::changeset_ty changeset_ty; + typedef DAGDeltaAlgorithm::changesetlist_ty changesetlist_ty; + typedef DAGDeltaAlgorithm::edge_ty edge_ty; + +private: + typedef std::vector<change_ty>::iterator pred_iterator_ty; + typedef std::vector<change_ty>::iterator succ_iterator_ty; + typedef std::set<change_ty>::iterator pred_closure_iterator_ty; + typedef std::set<change_ty>::iterator succ_closure_iterator_ty; + + DAGDeltaAlgorithm &DDA; + + const changeset_ty &Changes; + const std::vector<edge_ty> &Dependencies; + + std::vector<change_ty> Roots; + + /// Cache of failed test results. Successful test results are never cached + /// since we always reduce following a success. We maintain an independent + /// cache from that used by the individual delta passes because we may get + /// hits across multiple individual delta invocations. + mutable std::set<changeset_ty> FailedTestsCache; + + // FIXME: Gross. + std::map<change_ty, std::vector<change_ty> > Predecessors; + std::map<change_ty, std::vector<change_ty> > Successors; + + std::map<change_ty, std::set<change_ty> > PredClosure; + std::map<change_ty, std::set<change_ty> > SuccClosure; + +private: + pred_iterator_ty pred_begin(change_ty Node) { + assert(Predecessors.count(Node) && "Invalid node!"); + return Predecessors[Node].begin(); + } + pred_iterator_ty pred_end(change_ty Node) { + assert(Predecessors.count(Node) && "Invalid node!"); + return Predecessors[Node].end(); + } + + pred_closure_iterator_ty pred_closure_begin(change_ty Node) { + assert(PredClosure.count(Node) && "Invalid node!"); + return PredClosure[Node].begin(); + } + pred_closure_iterator_ty pred_closure_end(change_ty Node) { + assert(PredClosure.count(Node) && "Invalid node!"); + return PredClosure[Node].end(); + } + + succ_iterator_ty succ_begin(change_ty Node) { + assert(Successors.count(Node) && "Invalid node!"); + return Successors[Node].begin(); + } + succ_iterator_ty succ_end(change_ty Node) { + assert(Successors.count(Node) && "Invalid node!"); + return Successors[Node].end(); + } + + succ_closure_iterator_ty succ_closure_begin(change_ty Node) { + assert(SuccClosure.count(Node) && "Invalid node!"); + return SuccClosure[Node].begin(); + } + succ_closure_iterator_ty succ_closure_end(change_ty Node) { + assert(SuccClosure.count(Node) && "Invalid node!"); + return SuccClosure[Node].end(); + } + + void UpdatedSearchState(const changeset_ty &Changes, + const changesetlist_ty &Sets, + const changeset_ty &Required) { + DDA.UpdatedSearchState(Changes, Sets, Required); + } + + /// ExecuteOneTest - Execute a single test predicate on the change set \arg S. + bool ExecuteOneTest(const changeset_ty &S) { + // Check dependencies invariant. + DEBUG({ + for (changeset_ty::const_iterator it = S.begin(), + ie = S.end(); it != ie; ++it) + for (succ_iterator_ty it2 = succ_begin(*it), + ie2 = succ_end(*it); it2 != ie2; ++it2) + assert(S.count(*it2) && "Attempt to run invalid changeset!"); + }); + + return DDA.ExecuteOneTest(S); + } + +public: + DAGDeltaAlgorithmImpl(DAGDeltaAlgorithm &_DDA, + const changeset_ty &_Changes, + const std::vector<edge_ty> &_Dependencies); + + changeset_ty Run(); + + /// GetTestResult - Get the test result for the active set \arg Changes with + /// \arg Required changes from the cache, executing the test if necessary. + /// + /// \param Changes - The set of active changes being minimized, which should + /// have their pred closure included in the test. + /// \param Required - The set of changes which have previously been + /// established to be required. + /// \return - The test result. + bool GetTestResult(const changeset_ty &Changes, const changeset_ty &Required); +}; + +/// Helper object for minimizing an active set of changes. +class DeltaActiveSetHelper : public DeltaAlgorithm { + DAGDeltaAlgorithmImpl &DDAI; + + const changeset_ty &Required; + +protected: + /// UpdatedSearchState - Callback used when the search state changes. + virtual void UpdatedSearchState(const changeset_ty &Changes, + const changesetlist_ty &Sets) { + DDAI.UpdatedSearchState(Changes, Sets, Required); + } + + virtual bool ExecuteOneTest(const changeset_ty &S) { + return DDAI.GetTestResult(S, Required); + } + +public: + DeltaActiveSetHelper(DAGDeltaAlgorithmImpl &_DDAI, + const changeset_ty &_Required) + : DDAI(_DDAI), Required(_Required) {} +}; + +} + +DAGDeltaAlgorithmImpl::DAGDeltaAlgorithmImpl(DAGDeltaAlgorithm &_DDA, + const changeset_ty &_Changes, + const std::vector<edge_ty> + &_Dependencies) + : DDA(_DDA), + Changes(_Changes), + Dependencies(_Dependencies) +{ + for (changeset_ty::const_iterator it = Changes.begin(), + ie = Changes.end(); it != ie; ++it) { + Predecessors.insert(std::make_pair(*it, std::vector<change_ty>())); + Successors.insert(std::make_pair(*it, std::vector<change_ty>())); + } + for (std::vector<edge_ty>::const_iterator it = Dependencies.begin(), + ie = Dependencies.end(); it != ie; ++it) { + Predecessors[it->second].push_back(it->first); + Successors[it->first].push_back(it->second); + } + + // Compute the roots. + for (changeset_ty::const_iterator it = Changes.begin(), + ie = Changes.end(); it != ie; ++it) + if (succ_begin(*it) == succ_end(*it)) + Roots.push_back(*it); + + // Pre-compute the closure of the successor relation. + std::vector<change_ty> Worklist(Roots.begin(), Roots.end()); + while (!Worklist.empty()) { + change_ty Change = Worklist.back(); + Worklist.pop_back(); + + std::set<change_ty> &ChangeSuccs = SuccClosure[Change]; + for (pred_iterator_ty it = pred_begin(Change), + ie = pred_end(Change); it != ie; ++it) { + SuccClosure[*it].insert(Change); + SuccClosure[*it].insert(ChangeSuccs.begin(), ChangeSuccs.end()); + Worklist.push_back(*it); + } + } + + // Invert to form the predecessor closure map. + for (changeset_ty::const_iterator it = Changes.begin(), + ie = Changes.end(); it != ie; ++it) + PredClosure.insert(std::make_pair(*it, std::set<change_ty>())); + for (changeset_ty::const_iterator it = Changes.begin(), + ie = Changes.end(); it != ie; ++it) + for (succ_closure_iterator_ty it2 = succ_closure_begin(*it), + ie2 = succ_closure_end(*it); it2 != ie2; ++it2) + PredClosure[*it2].insert(*it); + + // Dump useful debug info. + DEBUG({ + llvm::errs() << "-- DAGDeltaAlgorithmImpl --\n"; + llvm::errs() << "Changes: ["; + for (changeset_ty::const_iterator it = Changes.begin(), + ie = Changes.end(); it != ie; ++it) { + if (it != Changes.begin()) llvm::errs() << ", "; + llvm::errs() << *it; + + if (succ_begin(*it) != succ_end(*it)) { + llvm::errs() << "("; + for (succ_iterator_ty it2 = succ_begin(*it), + ie2 = succ_end(*it); it2 != ie2; ++it2) { + if (it2 != succ_begin(*it)) llvm::errs() << ", "; + llvm::errs() << "->" << *it2; + } + llvm::errs() << ")"; + } + } + llvm::errs() << "]\n"; + + llvm::errs() << "Roots: ["; + for (std::vector<change_ty>::const_iterator it = Roots.begin(), + ie = Roots.end(); it != ie; ++it) { + if (it != Roots.begin()) llvm::errs() << ", "; + llvm::errs() << *it; + } + llvm::errs() << "]\n"; + + llvm::errs() << "Predecessor Closure:\n"; + for (changeset_ty::const_iterator it = Changes.begin(), + ie = Changes.end(); it != ie; ++it) { + llvm::errs() << format(" %-4d: [", *it); + for (pred_closure_iterator_ty it2 = pred_closure_begin(*it), + ie2 = pred_closure_end(*it); it2 != ie2; ++it2) { + if (it2 != pred_closure_begin(*it)) llvm::errs() << ", "; + llvm::errs() << *it2; + } + llvm::errs() << "]\n"; + } + + llvm::errs() << "Successor Closure:\n"; + for (changeset_ty::const_iterator it = Changes.begin(), + ie = Changes.end(); it != ie; ++it) { + llvm::errs() << format(" %-4d: [", *it); + for (succ_closure_iterator_ty it2 = succ_closure_begin(*it), + ie2 = succ_closure_end(*it); it2 != ie2; ++it2) { + if (it2 != succ_closure_begin(*it)) llvm::errs() << ", "; + llvm::errs() << *it2; + } + llvm::errs() << "]\n"; + } + + llvm::errs() << "\n\n"; + }); +} + +bool DAGDeltaAlgorithmImpl::GetTestResult(const changeset_ty &Changes, + const changeset_ty &Required) { + changeset_ty Extended(Required); + Extended.insert(Changes.begin(), Changes.end()); + for (changeset_ty::iterator it = Changes.begin(), + ie = Changes.end(); it != ie; ++it) + Extended.insert(pred_closure_begin(*it), pred_closure_end(*it)); + + if (FailedTestsCache.count(Extended)) + return false; + + bool Result = ExecuteOneTest(Extended); + if (!Result) + FailedTestsCache.insert(Extended); + + return Result; +} + +DAGDeltaAlgorithm::changeset_ty +DAGDeltaAlgorithmImpl::Run() { + // The current set of changes we are minimizing, starting at the roots. + changeset_ty CurrentSet(Roots.begin(), Roots.end()); + + // The set of required changes. + changeset_ty Required; + + // Iterate until the active set of changes is empty. Convergence is guaranteed + // assuming input was a DAG. + // + // Invariant: CurrentSet intersect Required == {} + // Invariant: Required == (Required union succ*(Required)) + while (!CurrentSet.empty()) { + DEBUG({ + llvm::errs() << "DAG_DD - " << CurrentSet.size() << " active changes, " + << Required.size() << " required changes\n"; + }); + + // Minimize the current set of changes. + DeltaActiveSetHelper Helper(*this, Required); + changeset_ty CurrentMinSet = Helper.Run(CurrentSet); + + // Update the set of required changes. Since + // CurrentMinSet subset CurrentSet + // and after the last iteration, + // succ(CurrentSet) subset Required + // then + // succ(CurrentMinSet) subset Required + // and our invariant on Required is maintained. + Required.insert(CurrentMinSet.begin(), CurrentMinSet.end()); + + // Replace the current set with the predecssors of the minimized set of + // active changes. + CurrentSet.clear(); + for (changeset_ty::const_iterator it = CurrentMinSet.begin(), + ie = CurrentMinSet.end(); it != ie; ++it) + CurrentSet.insert(pred_begin(*it), pred_end(*it)); + + // FIXME: We could enforce CurrentSet intersect Required == {} here if we + // wanted to protect against cyclic graphs. + } + + return Required; +} + +DAGDeltaAlgorithm::changeset_ty +DAGDeltaAlgorithm::Run(const changeset_ty &Changes, + const std::vector<edge_ty> &Dependencies) { + return DAGDeltaAlgorithmImpl(*this, Changes, Dependencies).Run(); +} diff --git a/unittests/ADT/DAGDeltaAlgorithmTest.cpp b/unittests/ADT/DAGDeltaAlgorithmTest.cpp new file mode 100644 index 0000000000..b90e0c7fc2 --- /dev/null +++ b/unittests/ADT/DAGDeltaAlgorithmTest.cpp @@ -0,0 +1,122 @@ +//===- llvm/unittest/ADT/DAGDeltaAlgorithmTest.cpp ------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "gtest/gtest.h" +#include "llvm/ADT/DAGDeltaAlgorithm.h" +#include <algorithm> +#include <cstdarg> +using namespace llvm; + +namespace std { + +static std::ostream &operator<<(std::ostream &OS, + const std::set<unsigned> &S) { + OS << "{"; + for (std::set<unsigned>::const_iterator it = S.begin(), + ie = S.end(); it != ie; ++it) { + if (it != S.begin()) + OS << ","; + OS << *it; + } + OS << "}"; + return OS; +} + +} + +namespace { + +typedef DAGDeltaAlgorithm::edge_ty edge_ty; + +class FixedDAGDeltaAlgorithm : public DAGDeltaAlgorithm { + changeset_ty FailingSet; + unsigned NumTests; + +protected: + virtual bool ExecuteOneTest(const changeset_ty &Changes) { + ++NumTests; + return std::includes(Changes.begin(), Changes.end(), + FailingSet.begin(), FailingSet.end()); + } + +public: + FixedDAGDeltaAlgorithm(const changeset_ty &_FailingSet) + : FailingSet(_FailingSet), + NumTests(0) {} + + unsigned getNumTests() const { return NumTests; } +}; + +std::set<unsigned> fixed_set(unsigned N, ...) { + std::set<unsigned> S; + va_list ap; + va_start(ap, N); + for (unsigned i = 0; i != N; ++i) + S.insert(va_arg(ap, unsigned)); + va_end(ap); + return S; +} + +std::set<unsigned> range(unsigned Start, unsigned End) { + std::set<unsigned> S; + while (Start != End) + S.insert(Start++); + return S; +} + +std::set<unsigned> range(unsigned N) { + return range(0, N); +} + +TEST(DAGDeltaAlgorithmTest, Basic) { + std::vector<edge_ty> Deps; + + // Dependencies: + // 1 - 3 + Deps.clear(); + Deps.push_back(std::make_pair(3, 1)); + + // P = {3,5,7} \in S, + // [0, 20), + // should minimize to {1,3,5,7} in a reasonable number of tests. + FixedDAGDeltaAlgorithm FDA(fixed_set(3, 3, 5, 7)); + EXPECT_EQ(fixed_set(4, 1, 3, 5, 7), FDA.Run(range(20), Deps)); + EXPECT_GE(46U, FDA.getNumTests()); + + // Dependencies: + // 0 - 1 + // \- 2 - 3 + // \- 4 + Deps.clear(); + Deps.push_back(std::make_pair(1, 0)); + Deps.push_back(std::make_pair(2, 0)); + Deps.push_back(std::make_pair(4, 0)); + Deps.push_back(std::make_pair(3, 2)); + + // This is a case where we must hold required changes. + // + // P = {1,3} \in S, + // [0, 5), + // should minimize to {0,1,2,3} in a small number of tests. + FixedDAGDeltaAlgorithm FDA2(fixed_set(2, 1, 3)); + EXPECT_EQ(fixed_set(4, 0, 1, 2, 3), FDA2.Run(range(5), Deps)); + EXPECT_GE(9U, FDA2.getNumTests()); + + // This is a case where we should quickly prune part of the tree. + // + // P = {4} \in S, + // [0, 5), + // should minimize to {0,4} in a small number of tests. + FixedDAGDeltaAlgorithm FDA3(fixed_set(1, 4)); + EXPECT_EQ(fixed_set(2, 0, 4), FDA3.Run(range(5), Deps)); + EXPECT_GE(6U, FDA3.getNumTests()); +} + +} + |