CbC/CbC_llvm: lib/Support/DAGDeltaAlgorithm.cpp comparison

comparison lib/Support/DAGDeltaAlgorithm.cpp @ 3:9ad51c7bc036

1st commit. remove git dir and add all files.

author	Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
date	Wed, 15 May 2013 06:43:32 +0900
parents
children	54457678186b

comparison

equal deleted inserted replaced

--1:000000000000
+:9ad51c7bc036
+//===--- 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 \p 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 \p Changes with
+/// \p 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) LLVM_OVERRIDE {
+DDAI.UpdatedSearchState(Changes, Sets, Required);
+}
+virtual bool ExecuteOneTest(const changeset_ty &S) LLVM_OVERRIDE {
+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::const_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;
+}
+void DAGDeltaAlgorithm::anchor() {
+}
+DAGDeltaAlgorithm::changeset_ty
+DAGDeltaAlgorithm::Run(const changeset_ty &Changes,
+const std::vector<edge_ty> &Dependencies) {
+return DAGDeltaAlgorithmImpl(*this, Changes, Dependencies).Run();
+}

Mercurial > hg > CbC > CbC_llvm

comparison lib/Support/DAGDeltaAlgorithm.cpp @ 3:9ad51c7bc036