LCOV - code coverage report
 Current view: top level - include/llvm/ADT - DAGDeltaAlgorithm.h (source / functions) Hit Total Coverage Test: llvm-toolchain.info Lines: 2 2 100.0 % Date: 2018-05-20 00:06:23 Functions: 1 1 100.0 % Legend: Lines: hit not hit
  Line data Source code  1 : //===- DAGDeltaAlgorithm.h - A DAG Minimization Algorithm ------*- C++ -*--===// 2 : // 3 : // The LLVM Compiler Infrastructure 4 : // 5 : // This file is distributed under the University of Illinois Open Source 6 : // License. See LICENSE.TXT for details. 7 : //===----------------------------------------------------------------------===// 8 : 9 : #ifndef LLVM_ADT_DAGDELTAALGORITHM_H 10 : #define LLVM_ADT_DAGDELTAALGORITHM_H 11 : 12 : #include 13 : #include 14 : #include 15 : 16 : namespace llvm { 17 : 18 : /// DAGDeltaAlgorithm - Implements a "delta debugging" algorithm for minimizing 19 : /// directed acyclic graphs using a predicate function. 20 : /// 21 : /// The result of the algorithm is a subset of the input change set which is 22 : /// guaranteed to satisfy the predicate, assuming that the input set did. For 23 : /// well formed predicates, the result set is guaranteed to be such that 24 : /// removing any single element not required by the dependencies on the other 25 : /// elements would falsify the predicate. 26 : /// 27 : /// The DAG should be used to represent dependencies in the changes which are 28 : /// likely to hold across the predicate function. That is, for a particular 29 : /// changeset S and predicate P: 30 : /// 31 : /// P(S) => P(S union pred(S)) 32 : /// 33 : /// The minization algorithm uses this dependency information to attempt to 34 : /// eagerly prune large subsets of changes. As with \see DeltaAlgorithm, the DAG 35 : /// is not required to satisfy this property, but the algorithm will run 36 : /// substantially fewer tests with appropriate dependencies. \see DeltaAlgorithm 37 : /// for more information on the properties which the predicate function itself 38 : /// should satisfy. 39 : class DAGDeltaAlgorithm { 40 : virtual void anchor(); 41 : 42 : public: 43 : using change_ty = unsigned; 44 : using edge_ty = std::pair; 45 : 46 : // FIXME: Use a decent data structure. 47 : using changeset_ty = std::set; 48 : using changesetlist_ty = std::vector; 49 : 50 : public: 51 : virtual ~DAGDeltaAlgorithm() = default; 52 : 53 : /// Run - Minimize the DAG formed by the \p Changes vertices and the 54 : /// \p Dependencies edges by executing \see ExecuteOneTest() on subsets of 55 : /// changes and returning the smallest set which still satisfies the test 56 : /// predicate and the input \p Dependencies. 57 : /// 58 : /// \param Changes The list of changes. 59 : /// 60 : /// \param Dependencies The list of dependencies amongst changes. For each 61 : /// (x,y) in \p Dependencies, both x and y must be in \p Changes. The 62 : /// minimization algorithm guarantees that for each tested changed set S, 63 : /// \f$x \in S \f$ implies \f$y \in S \f$. It is an error to have cyclic 64 : /// dependencies. 65 : changeset_ty Run(const changeset_ty &Changes, 66 : const std::vector &Dependencies); 67 : 68 : /// UpdatedSearchState - Callback used when the search state changes. 69 18 : virtual void UpdatedSearchState(const changeset_ty &Changes, 70 : const changesetlist_ty &Sets, 71 18 : const changeset_ty &Required) {} 72 : 73 : /// ExecuteOneTest - Execute a single test predicate on the change set \p S. 74 : virtual bool ExecuteOneTest(const changeset_ty &S) = 0; 75 : }; 76 : 77 : } // end namespace llvm 78 : 79 : #endif // LLVM_ADT_DAGDELTAALGORITHM_H 

 Generated by: LCOV version 1.13