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; }
+ }
+ if (refused)
{
if (verbose >= 1)
{
--
2.50.1 (Apple Git-155)
