https://gcc.gnu.org/g:8a312e7a448a81d5447729c2743ec7b69b581402
commit r17-4935-g8a312e7a448a81d5447729c2743ec7b69b581402 Author: Kyrylo Tkachov <[email protected]> Date: Mon Oct 5 22:47:09 2026 +0200 genmatch: Relax DT_TRUE ordering barrier in decision_tree::find_node The DT_TRUE merge barrier in find_node prevents a later pattern from merging into an earlier equal sibling when a DT_TRUE node lies between them. The barrier was introduced for PR 64084 (r218141) to preserve source order in cases where multiple patterns can match the same input. Today's match.pd is protected at a finer grain by the gen_kids flush: DT_TRUE and DT_MATCH kids each force a flush of collected alternatives before emitting their own subtrees. The flush guarantees that patterns before a DT_TRUE are tried before patterns after it, so the barrier in find_node is redundant for most cases. The remaining cases where the barrier is necessary are those where an intermediate sibling (between the earlier and later equal nodes) has a DT_MATCH descendant. A DT_MATCH descendant means the sibling's subtree can match any input value, including inputs matched by the later node's subtree. If the later node merged into the earlier one, it would be tried before the DT_MATCH sibling, violating source order for those inputs. When no intermediate sibling has a DT_MATCH descendant, every sibling matches a disjoint set of inputs (since the top-level operand overlap check already ensures no sibling's top-level operation overlaps with p's, and DT_MATCH is the only construct that can widen the match beyond a specific operation). In this case the merge is safe. Replace the unconditional DT_TRUE barrier refusal with a scan of the intermediate siblings: refuse only when at least one non-DT_TRUE sibling between the candidate and the insertion point has a DT_MATCH descendant. This reduces the generated GIMPLE matcher by about 0.4% and the GENERIC matcher by about 0.2%. gcc/ChangeLog: * genmatch.cc (subtree_has_match_p): New function. (decision_tree::find_node): Replace unconditional DT_TRUE barrier with a scan for DT_MATCH descendants in intermediate siblings. Signed-off-by: Kyrylo Tkachov <[email protected]> Diff: --- gcc/genmatch.cc | 39 +++++++++++++++++++++++++++++++++++---- 1 file changed, 35 insertions(+), 4 deletions(-) diff --git a/gcc/genmatch.cc b/gcc/genmatch.cc index 249741e77cc6..a67426b6313c 100644 --- a/gcc/genmatch.cc +++ b/gcc/genmatch.cc @@ -2851,6 +2851,19 @@ nodes_overlap_p (dt_node *n1, dt_node *n2) return operand_cases_overlap_p (op1, op2); } +/* Return true if N or any node in its subtree has type DT_MATCH. */ + +static bool +subtree_has_match_p (dt_node *n) +{ + if (n->type == dt_node::DT_MATCH) + return true; + for (auto kid : n->kids) + if (subtree_has_match_p (kid)) + return true; + return false; +} + /* Search OPS for a decision tree node like P and return it if found. */ dt_node * @@ -2878,10 +2891,28 @@ decision_tree::find_node (vec<dt_node *>& ops, dt_node *p) { /* Unless we are processing the same pattern or the blocking pattern is before the one we are going to merge with. */ - if ((true_node - && true_node->for_id != current_id - && true_node->for_id > as_a <dt_operand *> (ops[i])->for_id) - || overlap_node) + bool refused = overlap_node != NULL; + if (!refused + && true_node + && true_node->for_id != current_id + && true_node->for_id > as_a <dt_operand *> (ops[i])->for_id) + { + /* Refuse only when an intermediate sibling has a DT_MATCH + descendant. Such a sibling can match any input, and its + ordering relative to p must be preserved. When no + intermediate sibling has a DT_MATCH descendant, every + sibling matches a disjoint set of inputs, so the ordering + of p's subtree with respect to those siblings does not + affect which pattern fires. */ + for (int k = i + 1; k < (int) ops.length (); ++k) + if (ops[k]->type != dt_node::DT_TRUE + && subtree_has_match_p (ops[k])) + { + refused = true; + break; + } + } + if (refused) { if (verbose >= 1) {
