| commit | 0ac9d528ec3d3b5be428f550ab0faba4cbbf74df | [log] [tgz] |
|---|---|---|
| author | Stanislav Funiak <stano@cerebras.net> | Fri Nov 26 18:08:50 2021 +0530 |
| committer | Copybara-Service <copybara-worker@google.com> | Fri Nov 26 04:46:42 2021 -0800 |
| tree | d86844888fa98cca327236ba2a593bf0f62c328f | |
| parent | 9ab24a6e9af18ab9cd3261ae5e624ab4b692eb52 [diff] |
Multi-root PDL matching using upward traversals. This is commit 4 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). This PR integrates the various components (root ordering algorithm, nondeterministic execution of PDL bytecode) to implement multi-root PDL matching. The main idea is for the pattern to specify mulitple candidate roots. The PDL-to-PDLInterp lowering selects one of these roots and "hangs" the pattern from this root, traversing the edges downwards (from operation to its operands) when possible and upwards (from values to its uses) when needed. The root is selected by invoking the optimal matching multiple times, once for each candidate root, and the connectors are determined form the optimal matching. The costs in the directed graph are equal to the number of upward edges that need to be traversed when connecting the given two candidate roots. It can be shown that, for this choice of the cost function, "hanging" the pattern an inner node is no better than from the optimal root. The following three main additions were implemented as a part of this PR: 1. OperationPos predicate has been extended to allow tracing the operation accepting a value (the opposite of operation defining a value). 2. Predicate checking if two values are not equal - this is useful to ensure that we do not traverse the edge back downwards after we traversed it upwards. 3. Function for for building the cost graph among the candidate roots. 4. Updated buildPredicateList, building the predicates optimal branching has been determined. Testing: unit tests (an integration test to follow once the stack of commits has landed) Reviewed By: rriddle Differential Revision: https://reviews.llvm.org/D108550 GitOrigin-RevId: a76ee58f3cbcec6e31ff0d25e7d9a89b81a2ccc8
See https://mlir.llvm.org/ for more information.