173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar//===--- DAGDeltaAlgorithm.cpp - A DAG Minimization Algorithm --*- C++ -*--===// 273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// 373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// The LLVM Compiler Infrastructure 473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// 573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// This file is distributed under the University of Illinois Open Source 673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// License. See LICENSE.TXT for details. 773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar//===----------------------------------------------------------------------===// 873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// 973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// The algorithm we use attempts to exploit the dependency information by 1073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// minimizing top-down. We start by constructing an initial root set R, and 1173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// then iteratively: 1273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// 1373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// 1. Minimize the set R using the test predicate: 1473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// P'(S) = P(S union pred*(S)) 1573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// 1673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// 2. Extend R to R' = R union pred(R). 1773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// 1873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// until a fixed point is reached. 1973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// 2073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// The idea is that we want to quickly prune entire portions of the graph, so we 2173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// try to find high-level nodes that can be eliminated with all of their 2273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// dependents. 2373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// 2473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// FIXME: The current algorithm doesn't actually provide a strong guarantee 2573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// about the minimality of the result. The problem is that after adding nodes to 2673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// the required set, we no longer consider them for elimination. For strictly 2773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// well formed predicates, this doesn't happen, but it commonly occurs in 2873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// practice when there are unmodelled dependencies. I believe we can resolve 2973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// this by allowing the required set to be minimized as well, but need more test 3073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// cases first. 3173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// 3273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar//===----------------------------------------------------------------------===// 3373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 3473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar#include "llvm/ADT/DAGDeltaAlgorithm.h" 3573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar#include "llvm/ADT/DeltaAlgorithm.h" 3673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar#include "llvm/Support/Debug.h" 3773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar#include "llvm/Support/Format.h" 3873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar#include "llvm/Support/raw_ostream.h" 3973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar#include <algorithm> 4073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar#include <cassert> 4173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar#include <iterator> 4273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar#include <map> 4373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbarusing namespace llvm; 4473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 45dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "dag-delta" 46dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 4773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbarnamespace { 4873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 4973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbarclass DAGDeltaAlgorithmImpl { 5073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar friend class DeltaActiveSetHelper; 5173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 5273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbarpublic: 5373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar typedef DAGDeltaAlgorithm::change_ty change_ty; 5473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar typedef DAGDeltaAlgorithm::changeset_ty changeset_ty; 5573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar typedef DAGDeltaAlgorithm::changesetlist_ty changesetlist_ty; 5673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar typedef DAGDeltaAlgorithm::edge_ty edge_ty; 5773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 5873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbarprivate: 5973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar typedef std::vector<change_ty>::iterator pred_iterator_ty; 6073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar typedef std::vector<change_ty>::iterator succ_iterator_ty; 6173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar typedef std::set<change_ty>::iterator pred_closure_iterator_ty; 6273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar typedef std::set<change_ty>::iterator succ_closure_iterator_ty; 6373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 6473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar DAGDeltaAlgorithm &DDA; 6573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 6673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar const changeset_ty &Changes; 6773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar const std::vector<edge_ty> &Dependencies; 6873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 6973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar std::vector<change_ty> Roots; 7073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 7173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar /// Cache of failed test results. Successful test results are never cached 7273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar /// since we always reduce following a success. We maintain an independent 7373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar /// cache from that used by the individual delta passes because we may get 7473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar /// hits across multiple individual delta invocations. 7573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar mutable std::set<changeset_ty> FailedTestsCache; 7673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 7773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // FIXME: Gross. 7873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar std::map<change_ty, std::vector<change_ty> > Predecessors; 7973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar std::map<change_ty, std::vector<change_ty> > Successors; 8073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 8173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar std::map<change_ty, std::set<change_ty> > PredClosure; 8273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar std::map<change_ty, std::set<change_ty> > SuccClosure; 8373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 8473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbarprivate: 8573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar pred_iterator_ty pred_begin(change_ty Node) { 8673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar assert(Predecessors.count(Node) && "Invalid node!"); 8773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar return Predecessors[Node].begin(); 8873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 8973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar pred_iterator_ty pred_end(change_ty Node) { 9073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar assert(Predecessors.count(Node) && "Invalid node!"); 9173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar return Predecessors[Node].end(); 9273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 9373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 9473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar pred_closure_iterator_ty pred_closure_begin(change_ty Node) { 9573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar assert(PredClosure.count(Node) && "Invalid node!"); 9673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar return PredClosure[Node].begin(); 9773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 9873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar pred_closure_iterator_ty pred_closure_end(change_ty Node) { 9973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar assert(PredClosure.count(Node) && "Invalid node!"); 10073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar return PredClosure[Node].end(); 10173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 10273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 10373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar succ_iterator_ty succ_begin(change_ty Node) { 10473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar assert(Successors.count(Node) && "Invalid node!"); 10573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar return Successors[Node].begin(); 10673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 10773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar succ_iterator_ty succ_end(change_ty Node) { 10873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar assert(Successors.count(Node) && "Invalid node!"); 10973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar return Successors[Node].end(); 11073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 11173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 11273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar succ_closure_iterator_ty succ_closure_begin(change_ty Node) { 11373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar assert(SuccClosure.count(Node) && "Invalid node!"); 11473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar return SuccClosure[Node].begin(); 11573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 11673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar succ_closure_iterator_ty succ_closure_end(change_ty Node) { 11773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar assert(SuccClosure.count(Node) && "Invalid node!"); 11873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar return SuccClosure[Node].end(); 11973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 12073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 12173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar void UpdatedSearchState(const changeset_ty &Changes, 12273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar const changesetlist_ty &Sets, 12373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar const changeset_ty &Required) { 12473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar DDA.UpdatedSearchState(Changes, Sets, Required); 12573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 12673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 127c5252da873d547a19069eaf9030fec203f128f66Dmitri Gribenko /// ExecuteOneTest - Execute a single test predicate on the change set \p S. 12873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar bool ExecuteOneTest(const changeset_ty &S) { 12973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // Check dependencies invariant. 13073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar DEBUG({ 13173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (changeset_ty::const_iterator it = S.begin(), 13273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie = S.end(); it != ie; ++it) 13373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (succ_iterator_ty it2 = succ_begin(*it), 13473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie2 = succ_end(*it); it2 != ie2; ++it2) 13573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar assert(S.count(*it2) && "Attempt to run invalid changeset!"); 13673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar }); 13773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 13873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar return DDA.ExecuteOneTest(S); 13973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 14073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 14173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbarpublic: 14273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar DAGDeltaAlgorithmImpl(DAGDeltaAlgorithm &_DDA, 14373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar const changeset_ty &_Changes, 14473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar const std::vector<edge_ty> &_Dependencies); 14573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 14673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar changeset_ty Run(); 14773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 148c5252da873d547a19069eaf9030fec203f128f66Dmitri Gribenko /// GetTestResult - Get the test result for the active set \p Changes with 149c5252da873d547a19069eaf9030fec203f128f66Dmitri Gribenko /// \p Required changes from the cache, executing the test if necessary. 15073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar /// 15173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar /// \param Changes - The set of active changes being minimized, which should 15273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar /// have their pred closure included in the test. 15373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar /// \param Required - The set of changes which have previously been 15473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar /// established to be required. 15573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar /// \return - The test result. 15673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar bool GetTestResult(const changeset_ty &Changes, const changeset_ty &Required); 15773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar}; 15873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 15973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar/// Helper object for minimizing an active set of changes. 16073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbarclass DeltaActiveSetHelper : public DeltaAlgorithm { 16173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar DAGDeltaAlgorithmImpl &DDAI; 16273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 16373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar const changeset_ty &Required; 16473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 16573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbarprotected: 16673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar /// UpdatedSearchState - Callback used when the search state changes. 16736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void UpdatedSearchState(const changeset_ty &Changes, 16836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const changesetlist_ty &Sets) override { 16973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar DDAI.UpdatedSearchState(Changes, Sets, Required); 17073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 17173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 17236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool ExecuteOneTest(const changeset_ty &S) override { 17373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar return DDAI.GetTestResult(S, Required); 17473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 17573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 17673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbarpublic: 17773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar DeltaActiveSetHelper(DAGDeltaAlgorithmImpl &_DDAI, 17873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar const changeset_ty &_Required) 17973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar : DDAI(_DDAI), Required(_Required) {} 18073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar}; 18173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 18273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar} 18373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 18473c6031a2546ad18ab0b454fe5d711715620d140Daniel DunbarDAGDeltaAlgorithmImpl::DAGDeltaAlgorithmImpl(DAGDeltaAlgorithm &_DDA, 18573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar const changeset_ty &_Changes, 18673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar const std::vector<edge_ty> 18773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar &_Dependencies) 18873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar : DDA(_DDA), 18973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar Changes(_Changes), 19073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar Dependencies(_Dependencies) 19173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar{ 19273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (changeset_ty::const_iterator it = Changes.begin(), 19373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie = Changes.end(); it != ie; ++it) { 19473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar Predecessors.insert(std::make_pair(*it, std::vector<change_ty>())); 19573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar Successors.insert(std::make_pair(*it, std::vector<change_ty>())); 19673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 19773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (std::vector<edge_ty>::const_iterator it = Dependencies.begin(), 19873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie = Dependencies.end(); it != ie; ++it) { 19973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar Predecessors[it->second].push_back(it->first); 20073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar Successors[it->first].push_back(it->second); 20173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 20273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 20373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // Compute the roots. 20473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (changeset_ty::const_iterator it = Changes.begin(), 20573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie = Changes.end(); it != ie; ++it) 20673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar if (succ_begin(*it) == succ_end(*it)) 20773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar Roots.push_back(*it); 20873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 20973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // Pre-compute the closure of the successor relation. 21073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar std::vector<change_ty> Worklist(Roots.begin(), Roots.end()); 21173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar while (!Worklist.empty()) { 21273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar change_ty Change = Worklist.back(); 21373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar Worklist.pop_back(); 21473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 21573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar std::set<change_ty> &ChangeSuccs = SuccClosure[Change]; 21673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (pred_iterator_ty it = pred_begin(Change), 21773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie = pred_end(Change); it != ie; ++it) { 21873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar SuccClosure[*it].insert(Change); 21973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar SuccClosure[*it].insert(ChangeSuccs.begin(), ChangeSuccs.end()); 22073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar Worklist.push_back(*it); 22173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 22273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 22373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 22473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // Invert to form the predecessor closure map. 22573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (changeset_ty::const_iterator it = Changes.begin(), 22673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie = Changes.end(); it != ie; ++it) 22773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar PredClosure.insert(std::make_pair(*it, std::set<change_ty>())); 22873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (changeset_ty::const_iterator it = Changes.begin(), 22973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie = Changes.end(); it != ie; ++it) 23073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (succ_closure_iterator_ty it2 = succ_closure_begin(*it), 23173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie2 = succ_closure_end(*it); it2 != ie2; ++it2) 23273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar PredClosure[*it2].insert(*it); 23373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 23473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // Dump useful debug info. 23573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar DEBUG({ 23673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << "-- DAGDeltaAlgorithmImpl --\n"; 23773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << "Changes: ["; 23873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (changeset_ty::const_iterator it = Changes.begin(), 23973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie = Changes.end(); it != ie; ++it) { 24073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar if (it != Changes.begin()) llvm::errs() << ", "; 24173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << *it; 24273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 24373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar if (succ_begin(*it) != succ_end(*it)) { 24473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << "("; 24573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (succ_iterator_ty it2 = succ_begin(*it), 24673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie2 = succ_end(*it); it2 != ie2; ++it2) { 24773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar if (it2 != succ_begin(*it)) llvm::errs() << ", "; 24873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << "->" << *it2; 24973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 25073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << ")"; 25173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 25273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 25373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << "]\n"; 25473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 25573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << "Roots: ["; 25673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (std::vector<change_ty>::const_iterator it = Roots.begin(), 25773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie = Roots.end(); it != ie; ++it) { 25873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar if (it != Roots.begin()) llvm::errs() << ", "; 25973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << *it; 26073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 26173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << "]\n"; 26273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 26373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << "Predecessor Closure:\n"; 26473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (changeset_ty::const_iterator it = Changes.begin(), 26573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie = Changes.end(); it != ie; ++it) { 26673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << format(" %-4d: [", *it); 26773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (pred_closure_iterator_ty it2 = pred_closure_begin(*it), 26873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie2 = pred_closure_end(*it); it2 != ie2; ++it2) { 26973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar if (it2 != pred_closure_begin(*it)) llvm::errs() << ", "; 27073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << *it2; 27173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 27273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << "]\n"; 27373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 27473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 27573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << "Successor Closure:\n"; 27673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (changeset_ty::const_iterator it = Changes.begin(), 27773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie = Changes.end(); it != ie; ++it) { 27873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << format(" %-4d: [", *it); 27973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (succ_closure_iterator_ty it2 = succ_closure_begin(*it), 28073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie2 = succ_closure_end(*it); it2 != ie2; ++it2) { 28173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar if (it2 != succ_closure_begin(*it)) llvm::errs() << ", "; 28273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << *it2; 28373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 28473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << "]\n"; 28573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 28673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 28773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << "\n\n"; 28873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar }); 28973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar} 29073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 29173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbarbool DAGDeltaAlgorithmImpl::GetTestResult(const changeset_ty &Changes, 29273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar const changeset_ty &Required) { 29373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar changeset_ty Extended(Required); 29473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar Extended.insert(Changes.begin(), Changes.end()); 295ef45832d7cc6a846cc194ef2764b76ac994fe137Daniel Dunbar for (changeset_ty::const_iterator it = Changes.begin(), 29673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie = Changes.end(); it != ie; ++it) 29773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar Extended.insert(pred_closure_begin(*it), pred_closure_end(*it)); 29873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 29973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar if (FailedTestsCache.count(Extended)) 30073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar return false; 30173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 30273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar bool Result = ExecuteOneTest(Extended); 30373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar if (!Result) 30473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar FailedTestsCache.insert(Extended); 30573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 30673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar return Result; 30773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar} 30873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 30973c6031a2546ad18ab0b454fe5d711715620d140Daniel DunbarDAGDeltaAlgorithm::changeset_ty 31073c6031a2546ad18ab0b454fe5d711715620d140Daniel DunbarDAGDeltaAlgorithmImpl::Run() { 31173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // The current set of changes we are minimizing, starting at the roots. 31273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar changeset_ty CurrentSet(Roots.begin(), Roots.end()); 31373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 31473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // The set of required changes. 31573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar changeset_ty Required; 31673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 31773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // Iterate until the active set of changes is empty. Convergence is guaranteed 31873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // assuming input was a DAG. 31973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // 32073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // Invariant: CurrentSet intersect Required == {} 32173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // Invariant: Required == (Required union succ*(Required)) 32273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar while (!CurrentSet.empty()) { 32373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar DEBUG({ 32473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << "DAG_DD - " << CurrentSet.size() << " active changes, " 32573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar << Required.size() << " required changes\n"; 32673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar }); 32773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 32873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // Minimize the current set of changes. 32973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar DeltaActiveSetHelper Helper(*this, Required); 33073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar changeset_ty CurrentMinSet = Helper.Run(CurrentSet); 33173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 33273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // Update the set of required changes. Since 33373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // CurrentMinSet subset CurrentSet 33473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // and after the last iteration, 33573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // succ(CurrentSet) subset Required 33673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // then 33773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // succ(CurrentMinSet) subset Required 33873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // and our invariant on Required is maintained. 33973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar Required.insert(CurrentMinSet.begin(), CurrentMinSet.end()); 34073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 34173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // Replace the current set with the predecssors of the minimized set of 34273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // active changes. 34373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar CurrentSet.clear(); 34473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (changeset_ty::const_iterator it = CurrentMinSet.begin(), 34573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie = CurrentMinSet.end(); it != ie; ++it) 34673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar CurrentSet.insert(pred_begin(*it), pred_end(*it)); 34773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 34873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // FIXME: We could enforce CurrentSet intersect Required == {} here if we 34973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // wanted to protect against cyclic graphs. 35073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 35173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 35273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar return Required; 35373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar} 35473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 3555729c5848c74a2413cc1d32a5f3c746aff5d9cccDavid Blaikievoid DAGDeltaAlgorithm::anchor() { 3565729c5848c74a2413cc1d32a5f3c746aff5d9cccDavid Blaikie} 3575729c5848c74a2413cc1d32a5f3c746aff5d9cccDavid Blaikie 35873c6031a2546ad18ab0b454fe5d711715620d140Daniel DunbarDAGDeltaAlgorithm::changeset_ty 35973c6031a2546ad18ab0b454fe5d711715620d140Daniel DunbarDAGDeltaAlgorithm::Run(const changeset_ty &Changes, 36073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar const std::vector<edge_ty> &Dependencies) { 36173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar return DAGDeltaAlgorithmImpl(*this, Changes, Dependencies).Run(); 36273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar} 363