mlir::pdl_to_pdl_interp::RootOrderingEntry Struct Reference

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...

Detailed Description

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.

Member Data Documentation

connector

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 buildPredicateList().

cost

std::pair<unsigned, unsigned> mlir::pdl_to_pdl_interp::RootOrderingEntry::cost

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 buildPredicateList(), and mlir::pdl_to_pdl_interp::OptimalBranching::solve().

---

The documentation for this struct was generated from the following file:

• lib/Conversion/PDLToPDLInterp/RootOrdering.h