MLIR
15.0.0git

The information associated with an edge in the cost graph. More...
#include "Conversion/PDLToPDLInterp/RootOrdering.h"
Public Attributes  
std::pair< unsigned, unsigned >  cost 
The depth of the connector Value w.r.t. More...  
Value  connector 
The connector value in the intersection of the two subtrees rooted at the source and target root that results in that smallest depth w.r.t. More...  
The information associated with an edge in the cost graph.
Each node in the cost graph corresponds to a candidate root detected in the pdl.pattern, and each edge in the cost graph corresponds to connecting the two candidate roots via a chain of operations. The cost of an edge is the smallest number of upward traversals required to go from the source to the target root, and the connector is a Value
in the intersection of the two subtrees rooted at the source and target root that results in that smallest number of upward traversals. Consider the following pattern with 3 roots op3, op4, and op5:
argA > op1 > op2 > op3 > res3 ^ ^   argB argC   v v res4 < op4 op5 > res5 ^ ^   op6 op7
The cost of the edge op3 > op4 is 1 (the upward traversal argB > op4), with argB being the connector Value
and similarly for op3 > op5 (cost 1, connector argC). The cost of the edge op4 > op3 is 3 (upward traversals argB > op1 > op2 > op3, connector argB), while the cost of edge op5 > op3 is 2 (uwpard traversals argC > op2 > op3). There are no edges between op4 and op5 in the cost graph, because the subtrees rooted at these two roots do not intersect. It is easy to see that the optimal root for this pattern is op3, resulting in the spanning arborescence op3 > {op4, op5}.
Definition at line 59 of file RootOrdering.h.
Value mlir::pdl_to_pdl_interp::RootOrderingEntry::connector 
The connector value in the intersection of the two subtrees rooted at the source and target root that results in that smallest depth w.r.t.
the target root.
Definition at line 70 of file RootOrdering.h.
Referenced by buildCostGraph(), and buildPredicateList().
The depth of the connector Value
w.r.t.
the target root.
This is a pair where the first value is the additive cost (the depth of the connector), and the second value is a priority for breaking ties (with 0 being the highest). Typically, the priority is a unique edge ID.
Definition at line 65 of file RootOrdering.h.
Referenced by buildCostGraph(), buildPredicateList(), and mlir::pdl_to_pdl_interp::OptimalBranching::solve().