On Tue, 6 Oct 2026, [email protected] wrote:
> From: Kyrylo Tkachov <[email protected]>
>
> 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%.
>
> Bootstrapped and tested on aarch64-none-linux-gnu.
> Ok for trunk?
>
> Thanks,
> Kyrill
>
> 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]>
> ---
> gcc/genmatch.cc | 36 ++++++++++++++++++++++++++++++++----
> 1 file changed, 32 insertions(+), 4 deletions(-)
>
> diff --git a/gcc/genmatch.cc b/gcc/genmatch.cc
> index 905ff420d6a..028283b9825 100644
> --- a/gcc/genmatch.cc
> +++ b/gcc/genmatch.cc
> @@ -2859,6 +2859,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 *
> @@ -2886,10 +2899,25 @@ 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; }
please fix formatting:
{
refused = true;
break;
}
OK with that change.
Thanks,
Richard.
> + }
> + if (refused)
> {
> if (verbose >= 1)
> {
>
--
Richard Biener <[email protected]>
SUSE Software Solutions Germany GmbH,
Frankenstrasse 146, 90461 Nuernberg, Germany;
GF: Stefan Gaiser, Jochen Jaser, Abhinav Puri; (HRB 36809, AG Nuernberg)
