LLVM API Documentation
#include <DAGDeltaAlgorithm.h>
Public Types | |
typedef unsigned | change_ty |
typedef std::pair< change_ty, change_ty > | edge_ty |
typedef std::set< change_ty > | changeset_ty |
typedef std::vector< changeset_ty > | changesetlist_ty |
Public Member Functions | |
virtual | ~DAGDeltaAlgorithm () |
changeset_ty | Run (const changeset_ty &Changes, const std::vector< edge_ty > &Dependencies) |
virtual void | UpdatedSearchState (const changeset_ty &Changes, const changesetlist_ty &Sets, const changeset_ty &Required) |
UpdatedSearchState - Callback used when the search state changes. | |
virtual bool | ExecuteOneTest (const changeset_ty &S)=0 |
ExecuteOneTest - Execute a single test predicate on the change set S . |
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
Definition at line 38 of file DAGDeltaAlgorithm.h.
Definition at line 41 of file DAGDeltaAlgorithm.h.
typedef std::set<change_ty> llvm::DAGDeltaAlgorithm::changeset_ty |
Definition at line 45 of file DAGDeltaAlgorithm.h.
typedef std::vector<changeset_ty> llvm::DAGDeltaAlgorithm::changesetlist_ty |
Definition at line 46 of file DAGDeltaAlgorithm.h.
typedef std::pair<change_ty, change_ty> llvm::DAGDeltaAlgorithm::edge_ty |
Definition at line 42 of file DAGDeltaAlgorithm.h.
virtual llvm::DAGDeltaAlgorithm::~DAGDeltaAlgorithm | ( | ) | [inline, virtual] |
Definition at line 49 of file DAGDeltaAlgorithm.h.
virtual bool llvm::DAGDeltaAlgorithm::ExecuteOneTest | ( | const changeset_ty & | S | ) | [pure virtual] |
ExecuteOneTest - Execute a single test predicate on the change set S
.
DAGDeltaAlgorithm::changeset_ty DAGDeltaAlgorithm::Run | ( | const changeset_ty & | Changes, |
const std::vector< edge_ty > & | Dependencies | ||
) |
Run - Minimize the DAG formed by the Changes
vertices and the Dependencies
edges by executing
Dependencies
.Changes | The list of changes. |
Dependencies | The list of dependencies amongst changes. For each (x,y) in Dependencies , both x and y must be in Changes . The minimization algorithm guarantees that for each tested changed set S, ![]() ![]() |
Definition at line 359 of file DAGDeltaAlgorithm.cpp.
virtual void llvm::DAGDeltaAlgorithm::UpdatedSearchState | ( | const changeset_ty & | Changes, |
const changesetlist_ty & | Sets, | ||
const changeset_ty & | Required | ||
) | [inline, virtual] |
UpdatedSearchState - Callback used when the search state changes.
Definition at line 67 of file DAGDeltaAlgorithm.h.