This patch adds a two markers for llvm::GraphTraits:
- NodePairFilteredGraph
- EdgeFilteredGraph
Both these markers allow to specify a static predicate that is used to
filter edges.
This predicate is a boolean function such that:
- for NodePairFilteredGraph, it takes a pair of const NodeRef & that
are used to represent an edge, and it evaluates a given property of
that pair;
- for EdgeFilteredGraph, it takes a const EdgeRef & that represents an
edge, and it evaluates a given property on the edge.
The filtered graph contains only the edges for which the predicate
evaluates true.
Notice that the predicate must have static lifetime, meaning that all
the edge properties must be entirely evaluated on the pair of node (for
NodePairFilteredGraph) or on the edge (for EdgeFilteredGraph).
This means that you cannot pass mutable state to the predicate at
runtime.
The new markers are designed to interoperate well with llvm::Inverse and
to allow you to traverse the marked graphs with llvm::depth_first,
llvm::inverse_depth_first, llvm::breadth_first, and to compute dominator
trees and post-dominator trees on filtered graphs.
Alessandro Di Federico