On Wed, 9 Sep 2026, [email protected] wrote:
> From: Kyrylo Tkachov <[email protected]>
>
> Named matches can keep operator iterators unexpanded until code generation.
> The decision tree compares these iterators by identity. Switch emission
> then expands each iterator into its concrete cases. For example:
>
> (for cmp (ge gt)
> (match overlap
> (cmp:c @0 @1)))
>
> (for cmp (lt le)
> (match overlap
> (cmp:c @0 @1)))
>
> produces these invalid labels:
>
> case GE_EXPR:
> case GT_EXPR:
> ...
> case LE_EXPR:
> case LT_EXPR:
> ...
> case LT_EXPR:
> case LE_EXPR:
> ...
> case GT_EXPR:
> case GE_EXPR:
> ...
>
> The last two label pairs duplicate the first two. Partially overlapping
> sets fail in the same way, so a sort or an equal-set merge is not sufficient.
>
> Partition sibling expression and function nodes into connected groups that
> share concrete switch cases. Emit the cases of each group once. Guard a
> matcher when its operator set covers only part of the group. Keep the
> existing decision-tree barriers. Do not merge a node across an intervening
> overlapping node. This keeps matcher bodies in source order. Treat
> NOP_EXPR and CONVERT_EXPR as the single CASE_CONVERT dispatch case.
>
> Reduced equal, partial, concrete, conversion, function, and arity overlaps
> generate and compile in GIMPLE and GENERIC modes. Runtime checks also keep
> source order across overlapping and repeated-capture paths.
>
> Bootstrapped and regression tested on aarch64-unknown-linux-gnu.
>
> Ok for trunk?
>
> Changes since v3:
> - Replace the COND_EXPR-specific eager substitution with general handling of
> overlapping delayed operator sets.
> - Preserve source order for overlapping decision-tree paths.
>
> gcc/ChangeLog:
>
> * genmatch.cc (case_convert_id_p): New function.
> (same_case_p): Likewise.
> (operation_has_case_p): Likewise.
> (operations_overlap_p): Likewise.
> (function_operation_p): Likewise.
> (operand_cases_overlap_p): Likewise.
> (cmp_operand): Handle conversion cases and function iterators.
> (nodes_overlap_p): New function.
> (decision_tree::find_node): Do not merge across an overlapping node.
> (fns_cmp): Remove.
> (dt_operand_group): New structure.
> (add_operation_cases): New function.
> (find_group): Likewise.
> (collect_operand_groups): Likewise.
> (release_operand_groups): Likewise.
> (operation_covers_group_p): Likewise.
> (emit_operation_test): Likewise.
> (emit_group_labels): Likewise.
> (emit_expr_group): Likewise.
> (emit_fn_group): Likewise.
> (dt_node::gen_kids): Do not sort function nodes.
> (dt_node::gen_kids_1): Emit groups with unique case labels.
>
> Signed-off-by: Kyrylo Tkachov <[email protected]>
> ---
> gcc/genmatch.cc | 500 ++++++++++++++++++++++++++++++++++++------------
> 1 file changed, 382 insertions(+), 118 deletions(-)
>
> diff --git a/gcc/genmatch.cc b/gcc/genmatch.cc
> index 71a47f95996..32ab083d9ff 100644
> --- a/gcc/genmatch.cc
> +++ b/gcc/genmatch.cc
> @@ -2666,6 +2666,91 @@ public:
> static void print_node (dt_node *, FILE *f = stderr, unsigned = 0);
> };
>
> +/* Return true if ID is a tree-code conversion dispatch key. */
> +
> +static bool
> +case_convert_id_p (id_base *id)
> +{
> + if (id->kind != id_base::CODE)
> + return false;
> + enum tree_code code = as_a <operator_id *> (id)->code;
> + return code == NOP_EXPR || code == CONVERT_EXPR;
> +}
> +
> +/* Return true if concrete operations ID1 and ID2 use the same case label.
> */
> +
> +static bool
> +same_case_p (id_base *id1, id_base *id2)
> +{
> + if (id1->kind != id2->kind)
> + return false;
> +
> + if (id1->kind == id_base::CODE)
> + return ((case_convert_id_p (id1) && case_convert_id_p (id2))
> + || (as_a <operator_id *> (id1)->code
> + == as_a <operator_id *> (id2)->code));
> +
> + if (id1->kind == id_base::FN)
> + return (as_a <fn_id *> (id1)->fn == as_a <fn_id *> (id2)->fn);
> +
> + return false;
> +}
> +
> +/* Return true if OPERATION dispatches on CASE_ID. */
> +
> +static bool
> +operation_has_case_p (id_base *operation, id_base *case_id)
> +{
> + if (user_id *u = dyn_cast <user_id *> (operation))
> + {
> + for (auto id : u->substitutes)
> + if (same_case_p (id, case_id))
> + return true;
> + return false;
> + }
> +
> + return same_case_p (operation, case_id);
> +}
> +
> +/* Return true if OP1 and OP2 have a common dispatch case. */
> +
> +static bool
> +operations_overlap_p (id_base *op1, id_base *op2)
> +{
> + if (user_id *u = dyn_cast <user_id *> (op1))
> + {
> + for (auto id : u->substitutes)
> + if (operation_has_case_p (op2, id))
> + return true;
> + return false;
> + }
> +
> + return operation_has_case_p (op2, op1);
> +}
> +
> +/* Return true if OPERATION denotes a function. */
> +
> +static bool
> +function_operation_p (id_base *operation)
> +{
> + if (user_id *u = dyn_cast <user_id *> (operation))
> + operation = u->substitutes[0];
> + return operation->kind == id_base::FN;
> +}
> +
> +/* Return true if O1 and O2 can use the same expression dispatch case. */
> +
> +static bool
> +operand_cases_overlap_p (operand *o1, operand *o2)
> +{
> + expr *e1 = dyn_cast <expr *> (o1);
> + expr *e2 = dyn_cast <expr *> (o2);
> + if (!e1 || !e2)
> + return false;
> +
> + return operations_overlap_p (e1->operation, e2->operation);
> +}
> +
> /* Compare two AST operands O1 and O2 and return true if they are equal. */
>
> bool
> @@ -2684,11 +2769,13 @@ cmp_operand (operand *o1, operand *o2)
> {
> expr *e1 = static_cast<expr *>(o1);
> expr *e2 = static_cast<expr *>(o2);
> - if (e1->operation != e2->operation
> + if ((e1->operation != e2->operation
> + && !(case_convert_id_p (e1->operation)
> + && case_convert_id_p (e2->operation)))
> || e1->is_generic != e2->is_generic
> || e1->match_phi != e2->match_phi)
> return false;
> - if (e1->operation->kind == id_base::FN
> + if (function_operation_p (e1->operation)
> /* For function calls also compare number of arguments. */
> && e1->ops.length () != e2->ops.length ())
> return false;
> @@ -2724,6 +2811,28 @@ decision_tree::cmp_node (dt_node *n1, dt_node *n2)
> return false;
> }
>
> +/* Return true if N1 and N2 can match at the same decision-tree point. */
> +
> +static bool
> +nodes_overlap_p (dt_node *n1, dt_node *n2)
> +{
> + if (!is_a <dt_operand *> (n1) || !is_a <dt_operand *> (n2))
> + return false;
> +
> + if (n1->type == dt_node::DT_MATCH || n2->type == dt_node::DT_MATCH)
> + return (n1->type == dt_node::DT_MATCH
> + || n1->type == dt_node::DT_OPERAND)
> + && (n2->type == dt_node::DT_MATCH
> + || n2->type == dt_node::DT_OPERAND);
> +
Hmm, isn't this rather
/* A DT_MATCH is emitted as an ordering barrier by gen_kids, so it
can be reached by anything that reaches its siblings. */
if (n1->type == dt_node::DT_TRUE || n2->type == dt_node::DT_TRUE)
return false;
if (n1->type == dt_node::DT_MATCH || n2->type == dt_node::DT_MATCH)
return true;
> + if (n1->type != dt_node::DT_OPERAND
> + || n2->type != dt_node::DT_OPERAND)
> + return false;
> +
> + return operand_cases_overlap_p (as_a <dt_operand *> (n1)->op,
> + as_a <dt_operand *> (n2)->op);
> +}
> +
> /* Search OPS for a decision tree node like P and return it if found. */
>
> dt_node *
> @@ -2735,6 +2844,7 @@ decision_tree::find_node (vec<dt_node *>& ops, dt_node
> *p)
> && ops.last ()->type == dt_node::DT_TRUE)
> return ops.last ();
> dt_operand *true_node = NULL;
> + dt_operand *overlap_node = NULL;
> for (int i = ops.length () - 1; i >= 0; --i)
> {
> /* But we can't merge across DT_TRUE nodes as they serve as
> @@ -2750,25 +2860,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)
> + if ((true_node
> + && true_node->for_id != current_id
> + && true_node->for_id > as_a <dt_operand *> (ops[i])->for_id)
> + || overlap_node)
> {
> if (verbose >= 1)
> {
> + dt_operand *barrier = overlap_node ? overlap_node : true_node;
> location_t p_loc = 0;
> - if (p->type == dt_node::DT_OPERAND)
> + if (is_a <dt_operand *> (p)
> + && as_a <dt_operand *> (p)->op)
> p_loc = as_a <dt_operand *> (p)->op->location;
> location_t op_loc = 0;
> - if (ops[i]->type == dt_node::DT_OPERAND)
> + if (is_a <dt_operand *> (ops[i])
> + && as_a <dt_operand *> (ops[i])->op)
> op_loc = as_a <dt_operand *> (ops[i])->op->location;
> - location_t true_loc = 0;
> - true_loc = true_node->op->location;
> + location_t barrier_loc = barrier->op->location;
> warning_at (p_loc,
> "failed to merge decision tree node");
> warning_at (op_loc,
> "with the following");
> - warning_at (true_loc,
> + warning_at (barrier_loc,
> "because of the following which serves as
> ordering "
> "barrier");
> }
> @@ -2776,6 +2889,10 @@ decision_tree::find_node (vec<dt_node *>& ops, dt_node
> *p)
> }
> return ops[i];
> }
> + if (is_a <dt_operand *> (ops[i])
> + && as_a <dt_operand *> (ops[i])->for_id != current_id
> + && nodes_overlap_p (ops[i], p))
> + overlap_node = as_a <dt_operand *> (ops[i]);
> }
> return NULL;
> }
> @@ -3954,24 +4071,210 @@ dt_operand::gen_generic_expr (FILE *f, int indent,
> const char *opname)
> return 0;
> }
>
> -/* Compare 2 fns or generic_fns vector entries for vector sorting.
> - Same operation entries with different number of arguments should
> - be adjacent. */
> +/* A connected set of decision-tree operands with overlapping dispatch
> + cases. */
>
> -static int
> -fns_cmp (const void *p1, const void *p2)
> -{
> - dt_operand *op1 = *(dt_operand *const *) p1;
> - dt_operand *op2 = *(dt_operand *const *) p2;
> - expr *e1 = as_a <expr *> (op1->op);
> - expr *e2 = as_a <expr *> (op2->op);
> - id_base *b1 = e1->operation;
> - id_base *b2 = e2->operation;
> - if (b1->hashval < b2->hashval)
> - return -1;
> - if (b1->hashval > b2->hashval)
> - return 1;
> - return strcmp (b1->id, b2->id);
> +struct dt_operand_group
> +{
> + vec<id_base *> cases;
> + vec<dt_operand *> operands;
please use auto_vec<> here, this should simplify lifetime
management in gen_kids_1.
> +
> + dt_operand_group () : cases (vNULL), operands (vNULL)
> + {}
> +};
> +
> +/* Add the concrete cases for OPERATION to CASES. */
> +
> +static void
> +add_operation_cases (vec<id_base *> &cases, id_base *operation)
> +{
> + if (user_id *u = dyn_cast <user_id *> (operation))
> + {
> + for (auto id : u->substitutes)
> + add_operation_cases (cases, id);
> + return;
> + }
> +
> + for (auto id : cases)
> + if (same_case_p (id, operation))
> + return;
> + cases.safe_push (operation);
> +}
> +
> +/* Find the representative of INDEX in PARENTS. */
> +
> +static unsigned
> +find_group (const vec<unsigned> &parents, unsigned index)
> +{
> + while (parents[index] != index)
> + index = parents[index];
> + return index;
> +}
> +
> +/* Partition OPS into overlap-connected GROUPS. */
> +
> +static void
> +collect_operand_groups (const vec<dt_operand *> &ops,
> + vec<dt_operand_group *> &groups)
> +{
> + auto_vec<unsigned> parents;
> + for (unsigned i = 0; i < ops.length (); ++i)
> + parents.safe_push (i);
> +
> + for (unsigned i = 0; i < ops.length (); ++i)
> + for (unsigned j = 0; j < i; ++j)
> + if (operand_cases_overlap_p (ops[i]->op, ops[j]->op))
> + {
> + unsigned root1 = find_group (parents, i);
> + unsigned root2 = find_group (parents, j);
> + if (root1 != root2)
> + parents[MAX (root1, root2)] = MIN (root1, root2);
> + }
> +
> + auto_vec<unsigned> roots;
> + for (unsigned i = 0; i < ops.length (); ++i)
> + {
> + unsigned root = find_group (parents, i);
> + unsigned group_index;
> + for (group_index = 0; group_index < roots.length (); ++group_index)
> + if (roots[group_index] == root)
> + break;
> + if (group_index == roots.length ())
> + {
> + roots.safe_push (root);
> + groups.safe_push (new dt_operand_group ());
> + }
> +
> + dt_operand_group *group = groups[group_index];
> + group->operands.safe_push (ops[i]);
> + expr *e = as_a <expr *> (ops[i]->op);
> + add_operation_cases (group->cases, e->operation);
> + }
> +}
> +
> +/* Release GROUPS and their vectors. */
> +
> +static void
> +release_operand_groups (vec<dt_operand_group *> &groups)
> +{
> + for (auto group : groups)
> + {
> + group->cases.release ();
> + group->operands.release ();
> + delete group;
> + }
> +}
> +
> +/* Return true if OPERATION covers all cases in GROUP. */
> +
> +static bool
> +operation_covers_group_p (id_base *operation, dt_operand_group *group)
> +{
> + for (auto id : group->cases)
> + if (!operation_has_case_p (operation, id))
> + return false;
> + return true;
> +}
> +
> +/* Emit an if condition that tests CODE against OPERATION. */
> +
> +static void
> +emit_operation_test (FILE *f, int indent, const char *code,
> + id_base *operation)
> +{
> + auto_vec<id_base *> cases;
> + add_operation_cases (cases, operation);
> +
> + fprintf_indent (f, indent, "if (");
> + for (unsigned i = 0; i < cases.length (); ++i)
> + {
> + if (i)
> + fprintf (f, "\n%*s|| ", indent + 4, "");
> + if (case_convert_id_p (cases[i]))
> + fprintf (f, "CONVERT_EXPR_CODE_P (%s)", code);
> + else
> + fprintf (f, "%s == %s", code, cases[i]->id);
> + }
> + fprintf (f, ")\n");
> +}
> +
> +/* Emit the labels for GROUP. */
> +
> +static void
> +emit_group_labels (FILE *f, int indent, dt_operand_group *group)
> +{
> + for (auto id : group->cases)
> + if (case_convert_id_p (id))
> + fprintf_indent (f, indent, "CASE_CONVERT:\n");
> + else
> + fprintf_indent (f, indent, "case %s:\n", id->id);
> +}
> +
> +/* Emit an expression GROUP. CODE is the dispatched tree code. */
> +
> +static void
> +emit_expr_group (FILE *f, int indent, bool gimple, int depth,
> + const char *code, dt_operand_group *group)
> +{
> + fprintf_indent (f, indent, " {\n");
> + bool multiple_p = group->operands.length () > 1;
> + for (auto op : group->operands)
> + {
> + expr *e = as_a <expr *> (op->op);
> + bool test_p = !operation_covers_group_p (e->operation, group);
> + if (test_p)
> + {
> + emit_operation_test (f, indent + 4, code, e->operation);
> + fprintf_indent (f, indent + 4, " {\n");
> + }
> + else if (multiple_p)
> + fprintf_indent (f, indent + 4, "{\n");
> +
> + op->gen (f, indent + ((test_p || multiple_p) ? 6 : 4),
> + gimple, depth);
> +
> + if (test_p)
> + fprintf_indent (f, indent + 4, " }\n");
> + else if (multiple_p)
> + fprintf_indent (f, indent + 4, "}\n");
> + }
> + fprintf_indent (f, indent, " break;\n");
> + fprintf_indent (f, indent, " }\n");
> +}
> +
> +/* Emit a function GROUP. CODE is the dispatched combined function. */
> +
> +static void
> +emit_fn_group (FILE *f, int indent, bool gimple, int depth,
> + const char *opname, const char *code, dt_operand_group *group)
> +{
> + for (auto op : group->operands)
> + {
> + expr *e = as_a <expr *> (op->op);
> + bool test_p = !operation_covers_group_p (e->operation, group);
> + if (test_p)
> + {
> + emit_operation_test (f, indent + 2, code, e->operation);
> + fprintf_indent (f, indent + 2, " {\n");
> + }
> +
> + int inner_indent = indent + (test_p ? 4 : 0);
> + if (gimple)
> + fprintf_indent (f, inner_indent,
> + " if (gimple_call_num_args (_c%d) == %d)\n",
> + depth, e->ops.length ());
> + else
> + fprintf_indent (f, inner_indent,
> + " if (call_expr_nargs (%s) == %d)\n",
> + opname, e->ops.length ());
> + fprintf_indent (f, inner_indent, " {\n");
> + op->gen (f, inner_indent + 6, gimple, depth);
> + fprintf_indent (f, inner_indent, " }\n");
> +
> + if (test_p)
> + fprintf_indent (f, indent + 2, " }\n");
> + }
> + fprintf_indent (f, indent, " break;\n");
> }
>
> /* Generate matching code for the children of the decision tree node. */
> @@ -4047,8 +4350,6 @@ dt_node::gen_kids (FILE *f, int indent, bool gimple,
> int depth, bool in_gcond)
> Like DT_TRUE, DT_MATCH serves as a barrier as it can cause
> dependent matches to get out-of-order. Generate code now
> for what we have collected sofar. */
> - fns.qsort (fns_cmp);
> - generic_fns.qsort (fns_cmp);
> gen_kids_1 (f, indent, gimple, depth, gimple_exprs, generic_exprs,
> fns, generic_fns, preds, others, in_gcond);
> /* And output the true operand itself. */
> @@ -4065,8 +4366,6 @@ dt_node::gen_kids (FILE *f, int indent, bool gimple,
> int depth, bool in_gcond)
> }
>
> /* Generate code for the remains. */
> - fns.qsort (fns_cmp);
> - generic_fns.qsort (fns_cmp);
> gen_kids_1 (f, indent, gimple, depth, gimple_exprs, generic_exprs,
> fns, generic_fns, preds, others, in_gcond);
> }
> @@ -4091,6 +4390,15 @@ dt_node::gen_kids_1 (FILE *f, int indent, bool gimple,
> int depth,
> unsigned fns_len = fns.length ();
> unsigned gfns_len = generic_fns.length ();
>
> + auto_vec<dt_operand_group *> gimple_expr_groups;
> + auto_vec<dt_operand_group *> generic_expr_groups;
> + auto_vec<dt_operand_group *> fn_groups;
> + auto_vec<dt_operand_group *> generic_fn_groups;
> + collect_operand_groups (gimple_exprs, gimple_expr_groups);
> + collect_operand_groups (generic_exprs, generic_expr_groups);
> + collect_operand_groups (fns, fn_groups);
> + collect_operand_groups (generic_fns, generic_fn_groups);
> +
> if (exprs_len || fns_len || gexprs_len || gfns_len)
> {
> if (exprs_len)
> @@ -4134,24 +4442,15 @@ dt_node::gen_kids_1 (FILE *f, int indent, bool
> gimple, int depth,
> for (unsigned i = 0; i < exprs_len; ++i)
> {
> expr *e = as_a <expr *> (gimple_exprs[i]->op);
> - if (user_id *u = dyn_cast <user_id *> (e->operation))
> - {
> - for (auto id : u->substitutes)
> - fprintf_indent (f, indent, "case %s:\n", id->id);
> - }
> - else
> - {
> - id_base *op = e->operation;
> - cond_expr_p |= (*op == COND_EXPR && e->match_phi);
> - if (*op == CONVERT_EXPR || *op == NOP_EXPR)
> - fprintf_indent (f, indent, "CASE_CONVERT:\n");
> - else
> - fprintf_indent (f, indent, "case %s:\n", op->id);
> - }
> - fprintf_indent (f, indent, " {\n");
> - gimple_exprs[i]->gen (f, indent + 4, true, depth);
> - fprintf_indent (f, indent, " break;\n");
> - fprintf_indent (f, indent, " }\n");
> + cond_expr_p |= (*e->operation == COND_EXPR && e->match_phi);
> + }
> + char code[64];
> + snprintf (code, sizeof (code),
> + "gimple_assign_rhs_code (_a%d)", depth);
> + for (auto group : gimple_expr_groups)
> + {
> + emit_group_labels (f, indent, group);
> + emit_expr_group (f, indent, true, depth, code, group);
> }
> fprintf_indent (f, indent, "default:;\n");
> fprintf_indent (f, indent, "}\n");
> @@ -4190,32 +4489,14 @@ dt_node::gen_kids_1 (FILE *f, int indent, bool
> gimple, int depth,
>
> indent += 4;
> fprintf_indent (f, indent, "{\n");
> - id_base *last_op = NULL;
> - for (unsigned i = 0; i < fns_len; ++i)
> + char code[64];
> + snprintf (code, sizeof (code),
> + "gimple_call_combined_fn (_c%d)", depth);
> + for (auto group : fn_groups)
> {
> - expr *e = as_a <expr *>(fns[i]->op);
> - if (e->operation != last_op)
> - {
> - if (i)
> - fprintf_indent (f, indent, " break;\n");
> - if (user_id *u = dyn_cast <user_id *> (e->operation))
> - for (auto id : u->substitutes)
> - fprintf_indent (f, indent, "case %s:\n", id->id);
> - else
> - fprintf_indent (f, indent, "case %s:\n", e->operation->id);
> - }
> - last_op = e->operation;
> - /* We need to be defensive against bogus prototypes allowing
> - calls with not enough arguments. */
> - fprintf_indent (f, indent,
> - " if (gimple_call_num_args (_c%d) == %d)\n",
> - depth, e->ops.length ());
> - fprintf_indent (f, indent, " {\n");
> - fns[i]->gen (f, indent + 6, true, depth);
> - fprintf_indent (f, indent, " }\n");
> + emit_group_labels (f, indent, group);
> + emit_fn_group (f, indent, true, depth, NULL, code, group);
> }
> -
> - fprintf_indent (f, indent, " break;\n");
> fprintf_indent (f, indent, "default:;\n");
> fprintf_indent (f, indent, "}\n");
> indent -= 4;
> @@ -4226,42 +4507,31 @@ dt_node::gen_kids_1 (FILE *f, int indent, bool
> gimple, int depth,
> fprintf_indent (f, indent, " }\n");
> /* See if there is SSA_NAME among generic_exprs and if yes, emit it
> here rather than in the next loop. */
> - for (unsigned i = 0; i < generic_exprs.length (); ++i)
> - {
> - expr *e = as_a <expr *>(generic_exprs[i]->op);
> - id_base *op = e->operation;
> - if (*op == SSA_NAME && (exprs_len || fns_len))
> + for (auto group : generic_expr_groups)
> + for (auto id : group->cases)
> + if (*id == SSA_NAME && (exprs_len || fns_len))
> {
> - fprintf_indent (f, indent + 4, "{\n");
> - generic_exprs[i]->gen (f, indent + 6, gimple, depth);
> - fprintf_indent (f, indent + 4, "}\n");
> + gcc_checking_assert (group->cases.length () == 1);
> + for (auto op : group->operands)
> + {
> + fprintf_indent (f, indent + 4, "{\n");
> + op->gen (f, indent + 6, gimple, depth);
> + fprintf_indent (f, indent + 4, "}\n");
> + }
> }
> - }
>
> fprintf_indent (f, indent, " break;\n");
> }
>
> - for (unsigned i = 0; i < generic_exprs.length (); ++i)
> + char generic_code[160];
> + snprintf (generic_code, sizeof (generic_code), "TREE_CODE (%s)",
> + kid_opname);
it looks like kid_opname is only filled in conditional on
if (exprs_len || fns_len || gexprs_len || gfns_len).
valgrind over match.pd produces
Conditional jump or move depends on uninitialised value(s)
at 0x484B2A9: strlen
by 0x49CF131: snprintf
by 0x40E1E0: dt_node::gen_kids_1(...) (genmatch.cc:4527)
by 0x40D637: dt_node::gen_kids(...) (genmatch.cc:4353)
...
Uninitialised value was created by a stack allocation
at 0x40D786: dt_node::gen_kids_1(...) (genmatch.cc:4384)
the snprintf can be sunk to where it's used and thus initialization
is guarded.
> + for (auto group : generic_expr_groups)
> {
> - expr *e = as_a <expr *>(generic_exprs[i]->op);
> - id_base *op = e->operation;
> - if (*op == CONVERT_EXPR || *op == NOP_EXPR)
> - fprintf_indent (f, indent, "CASE_CONVERT:\n");
> - else if (*op == SSA_NAME && (exprs_len || fns_len))
> - /* Already handled above. */
> + if (*group->cases[0] == SSA_NAME && (exprs_len || fns_len))
this test is inconsistent with the assert which also asserts
group->cases.length () == 1. Maybe you want to test that here
as well?
Maybe the loop invariant (eprs_len || fns_len) could be hoisted
to make the intent clearer?
It seems this patch also fixes processing order for sth like
(simplify (plus @0 @0) @0) ; #0
(simplify (plus @0 (minus @1 @2)) @1) ; #1
(simplify (plus @0 @0) (negate @0)) ; #2
where previously we matched (oops) #0, #2, #1 and now correctly
in order. But we lose the duplicate match warning on #0/#2
because the nodes are no longer siblings, not sure if it's
worth to attempt to preserve that?
Further, decision_tree::insert_operand (genmatch.cc:3040-3060) does
dt_operand temp (dt_node::DT_TRUE, 0, 0, 0, 0);
elm = decision_tree::find_node (p->kids, &temp);
if (elm == 0)
{
dt_operand match (dt_node::DT_MATCH, 0, match_op, 0, 0);
match.value_match = c->value_match;
elm = decision_tree::find_node (p->kids, &match);
}
...
at_assert_elm:
gcc_assert (elm->type == dt_node::DT_TRUE
|| elm->type == dt_node::DT_OPERAND
|| elm->type == dt_node::DT_MATCH);
The DT_MATCH probe has for_id == current_id, so before the patch it
could only be blocked by the true_node rule; with the new overlap rule
(see 3a) *any* preceding sibling dt_operand from a different pattern
sets overlap_node, so this find_node returns NULL far more readily, and
then "elm->type" is a NULL dereference.
Maybe clarify by adding an gcc_assert (elm) or handle NULL elm?
I'm not sure whether we can hit this case.
Otherwise looks good.
Thanks for reworking the original fix,
Richard.
> continue;
> - else
> - {
> - if (user_id *u = dyn_cast <user_id *> (op))
> - for (auto id : u->substitutes)
> - fprintf_indent (f, indent, "case %s:\n", id->id);
> - else
> - fprintf_indent (f, indent, "case %s:\n", op->id);
> - }
> - fprintf_indent (f, indent, " {\n");
> - generic_exprs[i]->gen (f, indent + 4, gimple, depth);
> - fprintf_indent (f, indent, " break;\n");
> - fprintf_indent (f, indent, " }\n");
> + emit_group_labels (f, indent, group);
> + emit_expr_group (f, indent, gimple, depth, generic_code, group);
> }
>
> if (gfns_len)
> @@ -4275,25 +4545,14 @@ dt_node::gen_kids_1 (FILE *f, int indent, bool
> gimple, int depth,
> " {\n");
> indent += 4;
>
> - id_base *last_op = NULL;
> - for (unsigned j = 0; j < generic_fns.length (); ++j)
> + char code[160];
> + snprintf (code, sizeof (code), "get_call_combined_fn (%s)",
> + kid_opname);
> + for (auto group : generic_fn_groups)
> {
> - expr *e = as_a <expr *>(generic_fns[j]->op);
> - gcc_assert (e->operation->kind == id_base::FN);
> -
> - if (e->operation != last_op)
> - {
> - if (j)
> - fprintf_indent (f, indent, " break;\n");
> - fprintf_indent (f, indent, "case %s:\n", e->operation->id);
> - }
> - last_op = e->operation;
> - fprintf_indent (f, indent, " if (call_expr_nargs (%s) == %d)\n"
> - " {\n", kid_opname, e->ops.length ());
> - generic_fns[j]->gen (f, indent + 6, false, depth);
> - fprintf_indent (f, indent, " }\n");
> + emit_group_labels (f, indent, group);
> + emit_fn_group (f, indent, false, depth, kid_opname, code, group);
> }
> - fprintf_indent (f, indent, " break;\n");
> fprintf_indent (f, indent, "default:;\n");
>
> indent -= 4;
> @@ -4337,6 +4596,11 @@ dt_node::gen_kids_1 (FILE *f, int indent, bool gimple,
> int depth,
>
> for (unsigned i = 0; i < others.length (); ++i)
> others[i]->gen (f, indent, gimple, depth);
> +
> + release_operand_groups (gimple_expr_groups);
> + release_operand_groups (generic_expr_groups);
> + release_operand_groups (fn_groups);
> + release_operand_groups (generic_fn_groups);
> }
>
> /* Generate matching code for the decision tree operand. */
>
--
Richard Biener <[email protected]>
SUSE Software Solutions Germany GmbH,
Frankenstrasse 146, 90461 Nuernberg, Germany;
GF: Jochen Jaser, Andrew McDonald, Abhinav Puri; (HRB 36809, AG Nuernberg)
