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 4573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbarnamespace { 4673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 4773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbarclass DAGDeltaAlgorithmImpl { 4873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar friend class DeltaActiveSetHelper; 4973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 5073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbarpublic: 5173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar typedef DAGDeltaAlgorithm::change_ty change_ty; 5273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar typedef DAGDeltaAlgorithm::changeset_ty changeset_ty; 5373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar typedef DAGDeltaAlgorithm::changesetlist_ty changesetlist_ty; 5473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar typedef DAGDeltaAlgorithm::edge_ty edge_ty; 5573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 5673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbarprivate: 5773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar typedef std::vector<change_ty>::iterator pred_iterator_ty; 5873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar typedef std::vector<change_ty>::iterator succ_iterator_ty; 5973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar typedef std::set<change_ty>::iterator pred_closure_iterator_ty; 6073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar typedef std::set<change_ty>::iterator succ_closure_iterator_ty; 6173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 6273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar DAGDeltaAlgorithm &DDA; 6373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 6473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar const changeset_ty &Changes; 6573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar const std::vector<edge_ty> &Dependencies; 6673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 6773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar std::vector<change_ty> Roots; 6873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 6973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar /// Cache of failed test results. Successful test results are never cached 7073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar /// since we always reduce following a success. We maintain an independent 7173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar /// cache from that used by the individual delta passes because we may get 7273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar /// hits across multiple individual delta invocations. 7373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar mutable std::set<changeset_ty> FailedTestsCache; 7473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 7573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // FIXME: Gross. 7673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar std::map<change_ty, std::vector<change_ty> > Predecessors; 7773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar std::map<change_ty, std::vector<change_ty> > Successors; 7873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 7973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar std::map<change_ty, std::set<change_ty> > PredClosure; 8073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar std::map<change_ty, std::set<change_ty> > SuccClosure; 8173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 8273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbarprivate: 8373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar pred_iterator_ty pred_begin(change_ty Node) { 8473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar assert(Predecessors.count(Node) && "Invalid node!"); 8573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar return Predecessors[Node].begin(); 8673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 8773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar pred_iterator_ty pred_end(change_ty Node) { 8873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar assert(Predecessors.count(Node) && "Invalid node!"); 8973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar return Predecessors[Node].end(); 9073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 9173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 9273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar pred_closure_iterator_ty pred_closure_begin(change_ty Node) { 9373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar assert(PredClosure.count(Node) && "Invalid node!"); 9473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar return PredClosure[Node].begin(); 9573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 9673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar pred_closure_iterator_ty pred_closure_end(change_ty Node) { 9773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar assert(PredClosure.count(Node) && "Invalid node!"); 9873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar return PredClosure[Node].end(); 9973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 10073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 10173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar succ_iterator_ty succ_begin(change_ty Node) { 10273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar assert(Successors.count(Node) && "Invalid node!"); 10373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar return Successors[Node].begin(); 10473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 10573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar succ_iterator_ty succ_end(change_ty Node) { 10673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar assert(Successors.count(Node) && "Invalid node!"); 10773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar return Successors[Node].end(); 10873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 10973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 11073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar succ_closure_iterator_ty succ_closure_begin(change_ty Node) { 11173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar assert(SuccClosure.count(Node) && "Invalid node!"); 11273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar return SuccClosure[Node].begin(); 11373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 11473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar succ_closure_iterator_ty succ_closure_end(change_ty Node) { 11573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar assert(SuccClosure.count(Node) && "Invalid node!"); 11673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar return SuccClosure[Node].end(); 11773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 11873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 11973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar void UpdatedSearchState(const changeset_ty &Changes, 12073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar const changesetlist_ty &Sets, 12173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar const changeset_ty &Required) { 12273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar DDA.UpdatedSearchState(Changes, Sets, Required); 12373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 12473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 12573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar /// ExecuteOneTest - Execute a single test predicate on the change set \arg S. 12673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar bool ExecuteOneTest(const changeset_ty &S) { 12773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // Check dependencies invariant. 12873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar DEBUG({ 12973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (changeset_ty::const_iterator it = S.begin(), 13073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie = S.end(); it != ie; ++it) 13173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (succ_iterator_ty it2 = succ_begin(*it), 13273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie2 = succ_end(*it); it2 != ie2; ++it2) 13373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar assert(S.count(*it2) && "Attempt to run invalid changeset!"); 13473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar }); 13573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 13673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar return DDA.ExecuteOneTest(S); 13773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 13873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 13973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbarpublic: 14073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar DAGDeltaAlgorithmImpl(DAGDeltaAlgorithm &_DDA, 14173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar const changeset_ty &_Changes, 14273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar const std::vector<edge_ty> &_Dependencies); 14373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 14473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar changeset_ty Run(); 14573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 14673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar /// GetTestResult - Get the test result for the active set \arg Changes with 14773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar /// \arg Required changes from the cache, executing the test if necessary. 14873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar /// 14973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar /// \param Changes - The set of active changes being minimized, which should 15073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar /// have their pred closure included in the test. 15173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar /// \param Required - The set of changes which have previously been 15273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar /// established to be required. 15373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar /// \return - The test result. 15473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar bool GetTestResult(const changeset_ty &Changes, const changeset_ty &Required); 15573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar}; 15673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 15773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar/// Helper object for minimizing an active set of changes. 15873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbarclass DeltaActiveSetHelper : public DeltaAlgorithm { 15973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar DAGDeltaAlgorithmImpl &DDAI; 16073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 16173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar const changeset_ty &Required; 16273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 16373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbarprotected: 16473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar /// UpdatedSearchState - Callback used when the search state changes. 16573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar virtual void UpdatedSearchState(const changeset_ty &Changes, 16673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar const changesetlist_ty &Sets) { 16773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar DDAI.UpdatedSearchState(Changes, Sets, Required); 16873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 16973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 17073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar virtual bool ExecuteOneTest(const changeset_ty &S) { 17173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar return DDAI.GetTestResult(S, Required); 17273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 17373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 17473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbarpublic: 17573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar DeltaActiveSetHelper(DAGDeltaAlgorithmImpl &_DDAI, 17673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar const changeset_ty &_Required) 17773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar : DDAI(_DDAI), Required(_Required) {} 17873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar}; 17973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 18073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar} 18173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 18273c6031a2546ad18ab0b454fe5d711715620d140Daniel DunbarDAGDeltaAlgorithmImpl::DAGDeltaAlgorithmImpl(DAGDeltaAlgorithm &_DDA, 18373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar const changeset_ty &_Changes, 18473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar const std::vector<edge_ty> 18573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar &_Dependencies) 18673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar : DDA(_DDA), 18773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar Changes(_Changes), 18873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar Dependencies(_Dependencies) 18973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar{ 19073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (changeset_ty::const_iterator it = Changes.begin(), 19173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie = Changes.end(); it != ie; ++it) { 19273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar Predecessors.insert(std::make_pair(*it, std::vector<change_ty>())); 19373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar Successors.insert(std::make_pair(*it, std::vector<change_ty>())); 19473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 19573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (std::vector<edge_ty>::const_iterator it = Dependencies.begin(), 19673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie = Dependencies.end(); it != ie; ++it) { 19773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar Predecessors[it->second].push_back(it->first); 19873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar Successors[it->first].push_back(it->second); 19973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 20073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 20173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // Compute the roots. 20273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (changeset_ty::const_iterator it = Changes.begin(), 20373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie = Changes.end(); it != ie; ++it) 20473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar if (succ_begin(*it) == succ_end(*it)) 20573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar Roots.push_back(*it); 20673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 20773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // Pre-compute the closure of the successor relation. 20873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar std::vector<change_ty> Worklist(Roots.begin(), Roots.end()); 20973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar while (!Worklist.empty()) { 21073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar change_ty Change = Worklist.back(); 21173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar Worklist.pop_back(); 21273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 21373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar std::set<change_ty> &ChangeSuccs = SuccClosure[Change]; 21473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (pred_iterator_ty it = pred_begin(Change), 21573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie = pred_end(Change); it != ie; ++it) { 21673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar SuccClosure[*it].insert(Change); 21773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar SuccClosure[*it].insert(ChangeSuccs.begin(), ChangeSuccs.end()); 21873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar Worklist.push_back(*it); 21973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 22073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 22173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 22273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // Invert to form the predecessor closure map. 22373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (changeset_ty::const_iterator it = Changes.begin(), 22473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie = Changes.end(); it != ie; ++it) 22573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar PredClosure.insert(std::make_pair(*it, std::set<change_ty>())); 22673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (changeset_ty::const_iterator it = Changes.begin(), 22773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie = Changes.end(); it != ie; ++it) 22873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (succ_closure_iterator_ty it2 = succ_closure_begin(*it), 22973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie2 = succ_closure_end(*it); it2 != ie2; ++it2) 23073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar PredClosure[*it2].insert(*it); 23173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 23273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // Dump useful debug info. 23373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar DEBUG({ 23473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << "-- DAGDeltaAlgorithmImpl --\n"; 23573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << "Changes: ["; 23673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (changeset_ty::const_iterator it = Changes.begin(), 23773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie = Changes.end(); it != ie; ++it) { 23873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar if (it != Changes.begin()) llvm::errs() << ", "; 23973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << *it; 24073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 24173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar if (succ_begin(*it) != succ_end(*it)) { 24273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << "("; 24373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (succ_iterator_ty it2 = succ_begin(*it), 24473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie2 = succ_end(*it); it2 != ie2; ++it2) { 24573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar if (it2 != succ_begin(*it)) llvm::errs() << ", "; 24673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << "->" << *it2; 24773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 24873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << ")"; 24973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 25073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 25173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << "]\n"; 25273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 25373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << "Roots: ["; 25473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (std::vector<change_ty>::const_iterator it = Roots.begin(), 25573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie = Roots.end(); it != ie; ++it) { 25673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar if (it != Roots.begin()) llvm::errs() << ", "; 25773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << *it; 25873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 25973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << "]\n"; 26073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 26173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << "Predecessor Closure:\n"; 26273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (changeset_ty::const_iterator it = Changes.begin(), 26373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie = Changes.end(); it != ie; ++it) { 26473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << format(" %-4d: [", *it); 26573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (pred_closure_iterator_ty it2 = pred_closure_begin(*it), 26673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie2 = pred_closure_end(*it); it2 != ie2; ++it2) { 26773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar if (it2 != pred_closure_begin(*it)) llvm::errs() << ", "; 26873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << *it2; 26973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 27073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << "]\n"; 27173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 27273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 27373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << "Successor Closure:\n"; 27473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (changeset_ty::const_iterator it = Changes.begin(), 27573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie = Changes.end(); it != ie; ++it) { 27673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << format(" %-4d: [", *it); 27773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (succ_closure_iterator_ty it2 = succ_closure_begin(*it), 27873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie2 = succ_closure_end(*it); it2 != ie2; ++it2) { 27973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar if (it2 != succ_closure_begin(*it)) llvm::errs() << ", "; 28073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << *it2; 28173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 28273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << "]\n"; 28373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 28473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 28573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << "\n\n"; 28673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar }); 28773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar} 28873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 28973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbarbool DAGDeltaAlgorithmImpl::GetTestResult(const changeset_ty &Changes, 29073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar const changeset_ty &Required) { 29173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar changeset_ty Extended(Required); 29273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar Extended.insert(Changes.begin(), Changes.end()); 293ef45832d7cc6a846cc194ef2764b76ac994fe137Daniel Dunbar for (changeset_ty::const_iterator it = Changes.begin(), 29473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie = Changes.end(); it != ie; ++it) 29573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar Extended.insert(pred_closure_begin(*it), pred_closure_end(*it)); 29673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 29773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar if (FailedTestsCache.count(Extended)) 29873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar return false; 29973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 30073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar bool Result = ExecuteOneTest(Extended); 30173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar if (!Result) 30273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar FailedTestsCache.insert(Extended); 30373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 30473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar return Result; 30573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar} 30673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 30773c6031a2546ad18ab0b454fe5d711715620d140Daniel DunbarDAGDeltaAlgorithm::changeset_ty 30873c6031a2546ad18ab0b454fe5d711715620d140Daniel DunbarDAGDeltaAlgorithmImpl::Run() { 30973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // The current set of changes we are minimizing, starting at the roots. 31073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar changeset_ty CurrentSet(Roots.begin(), Roots.end()); 31173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 31273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // The set of required changes. 31373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar changeset_ty Required; 31473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 31573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // Iterate until the active set of changes is empty. Convergence is guaranteed 31673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // assuming input was a DAG. 31773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // 31873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // Invariant: CurrentSet intersect Required == {} 31973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // Invariant: Required == (Required union succ*(Required)) 32073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar while (!CurrentSet.empty()) { 32173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar DEBUG({ 32273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar llvm::errs() << "DAG_DD - " << CurrentSet.size() << " active changes, " 32373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar << Required.size() << " required changes\n"; 32473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar }); 32573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 32673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // Minimize the current set of changes. 32773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar DeltaActiveSetHelper Helper(*this, Required); 32873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar changeset_ty CurrentMinSet = Helper.Run(CurrentSet); 32973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 33073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // Update the set of required changes. Since 33173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // CurrentMinSet subset CurrentSet 33273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // and after the last iteration, 33373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // succ(CurrentSet) subset Required 33473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // then 33573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // succ(CurrentMinSet) subset Required 33673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // and our invariant on Required is maintained. 33773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar Required.insert(CurrentMinSet.begin(), CurrentMinSet.end()); 33873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 33973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // Replace the current set with the predecssors of the minimized set of 34073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // active changes. 34173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar CurrentSet.clear(); 34273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (changeset_ty::const_iterator it = CurrentMinSet.begin(), 34373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ie = CurrentMinSet.end(); it != ie; ++it) 34473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar CurrentSet.insert(pred_begin(*it), pred_end(*it)); 34573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 34673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // FIXME: We could enforce CurrentSet intersect Required == {} here if we 34773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // wanted to protect against cyclic graphs. 34873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 34973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 35073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar return Required; 35173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar} 35273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 3535729c5848c74a2413cc1d32a5f3c746aff5d9cccDavid Blaikievoid DAGDeltaAlgorithm::anchor() { 3545729c5848c74a2413cc1d32a5f3c746aff5d9cccDavid Blaikie} 3555729c5848c74a2413cc1d32a5f3c746aff5d9cccDavid Blaikie 35673c6031a2546ad18ab0b454fe5d711715620d140Daniel DunbarDAGDeltaAlgorithm::changeset_ty 35773c6031a2546ad18ab0b454fe5d711715620d140Daniel DunbarDAGDeltaAlgorithm::Run(const changeset_ty &Changes, 35873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar const std::vector<edge_ty> &Dependencies) { 35973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar return DAGDeltaAlgorithmImpl(*this, Changes, Dependencies).Run(); 36073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar} 361