//===- RootOrdering.h - Optimal root ordering ------------------*- C++ -*-===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // // This file contains definition for a cost graph over candidate roots and // an implementation of an algorithm to determine the optimal ordering over // these roots. Each edge in this graph indicates that the target root can be // connected (via a chain of positions) to the source root, and their cost // indicates the estimated cost of such traversal. The optimal root ordering // is then formulated as that of finding a spanning arborescence (i.e., a // directed spanning tree) of minimal weight. // //===----------------------------------------------------------------------===// #ifndef MLIR_LIB_CONVERSION_PDLTOPDLINTERP_ROOTORDERING_H_ #define MLIR_LIB_CONVERSION_PDLTOPDLINTERP_ROOTORDERING_H_ #include "mlir/IR/Value.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallVector.h" #include <functional> #include <vector> namespace mlir { namespace pdl_to_pdl_interp { /// 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}. struct RootOrderingEntry { … }; /// A directed graph representing the cost of ordering the roots in the /// predicate tree. It is represented as an adjacency map, where the outer map /// is indexed by the target node, and the inner map is indexed by the source /// node. Each edge is associated with a cost and the underlying connector /// value. RootOrderingGraph; /// The optimal branching algorithm solver. This solver accepts a graph and the /// root in its constructor, and is invoked via the solve() member function. /// This is a direct implementation of the Edmonds' algorithm, see /// https://en.wikipedia.org/wiki/Edmonds%27_algorithm. The worst-case /// computational complexity of this algorithm is O(N^3), for a single root. /// The PDL-to-PDLInterp lowering calls this N times (once for each candidate /// root), so the overall complexity root ordering is O(N^4). If needed, this /// could be reduced to O(N^3) with a more efficient algorithm. However, note /// that the underlying implementation is very efficient, and N in our /// instances tends to be very small (<10). class OptimalBranching { … }; } // namespace pdl_to_pdl_interp } // namespace mlir #endif // MLIR_CONVERSION_PDLTOPDLINTERP_ROOTORDERING_H_
Codebase Browser
llvm