| commit | 9ab24a6e9af18ab9cd3261ae5e624ab4b692eb52 | [log] [tgz] |
|---|---|---|
| author | Stanislav Funiak <stano@cerebras.net> | Fri Nov 26 18:08:42 2021 +0530 |
| committer | Copybara-Service <copybara-worker@google.com> | Fri Nov 26 04:46:37 2021 -0800 |
| tree | 640c764b865aabec259935a7a7005921985aba7a | |
| parent | cbec331e1779e85c22225917f8644b8e3525841c [diff] |
Implementation of the root ordering algorithm This is commit 3 of 4 for the multi-root matching in PDL, discussed in https://llvm.discourse.group/t/rfc-multi-root-pdl-patterns-for-kernel-matching/4148 (topic flagged for review). We form a graph over the specified roots, provided in `pdl.rewrite`, where two roots are connected by a directed edge if the target root can be connected (via a chain of operations) in the underlying pattern to the source root. We place a restriction that the path connecting the two candidate roots must only contain the nodes in the subgraphs underneath these two roots. The cost of an edge is the smallest number of upward traversals (edges) 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 such upward traversals. Optimal root ordering is then formulated as the problem of finding a spanning arborescence (i.e., a directed spanning tree) of minimal weight. In order to determine the spanning arborescence (directed spanning tree) of minimum weight, we use the [Edmonds' algorithm](https://en.wikipedia.org/wiki/Edmonds%27_algorithm). The worst-case computational complexity of this algorithm is O(_N_^3) for a single root, where _N_ is the number of specified roots. The `pdl`-to-`pdl_interp` lowering calls this algorithm as a subroutine _N_ times (once for each candidate root), so the overall complexity of root ordering is O(_N_^4). If needed, this complexity 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). Therefore, we believe that the proposed (asymptotically suboptimal) implementation will suffice for now. Testing: a unit test of the algorithm Reviewed By: rriddle Differential Revision: https://reviews.llvm.org/D108549 GitOrigin-RevId: 6df7cc7f47d280d550f41fc167bdd75fea726a06
See https://mlir.llvm.org/ for more information.