class DAGDeltaAlgorithm

Declaration

class DAGDeltaAlgorithm { /* full declaration omitted */ };

Description

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 minimization algorithm uses this dependency information to attempt to eagerly prune large subsets of changes. As with

Declared at: llvm/include/llvm/ADT/DAGDeltaAlgorithm.h:38

Method Overview

  • public virtual bool ExecuteOneTest(const llvm::DAGDeltaAlgorithm::changeset_ty & S)
  • public llvm::DAGDeltaAlgorithm::changeset_ty Run(const llvm::DAGDeltaAlgorithm::changeset_ty & Changes, const std::vector<edge_ty> & Dependencies)
  • public virtual void UpdatedSearchState(const llvm::DAGDeltaAlgorithm::changeset_ty & Changes, const llvm::DAGDeltaAlgorithm::changesetlist_ty & Sets, const llvm::DAGDeltaAlgorithm::changeset_ty & Required)
  • private virtual void anchor()
  • public virtual ~DAGDeltaAlgorithm()

Methods

virtual bool ExecuteOneTest(
    const llvm::DAGDeltaAlgorithm::changeset_ty&
        S)

Description

ExecuteOneTest - Execute a single test predicate on the change set \p S.

Declared at: llvm/include/llvm/ADT/DAGDeltaAlgorithm.h:73

Parameters

const llvm::DAGDeltaAlgorithm::changeset_ty& S

llvm::DAGDeltaAlgorithm::changeset_ty Run(
    const llvm::DAGDeltaAlgorithm::changeset_ty&
        Changes,
    const std::vector<edge_ty>& Dependencies)

Description

Run - Minimize the DAG formed by the \p Changes vertices and the\p Dependencies edges by executing implies . It is an error to have cyclic dependencies.

Declared at: llvm/include/llvm/ADT/DAGDeltaAlgorithm.h:64

Parameters

const llvm::DAGDeltaAlgorithm::changeset_ty& Changes
The list of changes.
const std::vector<edge_ty>& Dependencies
The list of dependencies amongst changes. For each (x,y) in \p Dependencies, both x and y must be in \p Changes. The minimization algorithm guarantees that for each tested changed set S,

virtual void UpdatedSearchState(
    const llvm::DAGDeltaAlgorithm::changeset_ty&
        Changes,
    const llvm::DAGDeltaAlgorithm::
        changesetlist_ty& Sets,
    const llvm::DAGDeltaAlgorithm::changeset_ty&
        Required)

Description

UpdatedSearchState - Callback used when the search state changes.

Declared at: llvm/include/llvm/ADT/DAGDeltaAlgorithm.h:68

Parameters

const llvm::DAGDeltaAlgorithm::changeset_ty& Changes
const llvm::DAGDeltaAlgorithm::changesetlist_ty& Sets
const llvm::DAGDeltaAlgorithm::changeset_ty& Required

virtual void anchor()

Declared at: llvm/include/llvm/ADT/DAGDeltaAlgorithm.h:39

virtual ~DAGDeltaAlgorithm()

Declared at: llvm/include/llvm/ADT/DAGDeltaAlgorithm.h:50