On Mon, 14 Sep 2026, [email protected] wrote: > From: Kyrylo Tkachov <[email protected]> > > genmatch writes one function for each outer operation. Output partitioning > places these functions whole, so one operation matcher can dominate an output > part. On current trunk, gimple_simplify_COND_EXPR has 58,429 lines and > 1.9 MB of generated source. Compiling it with profile generation for Armv8-A > Thumb produces 1,152 "conditional branch out of range" assembler errors. > This causes arm-linux-gnueabihf lto profiledbootstrap to fail after my > recent "genmatch: Handle overlapping delayed operator sets" commit. > > Split large per-operation matchers between top-level alternatives. End each > chunk with a call in tail position to the next chunk, place the next chunk in > the shortest output part, and forward the matcher parameters. > > Keep each overlap-connected dispatch group and each DT_MATCH subtree in one > chunk. This keeps the pattern order unchanged. Use one tenth of the average > number of decision-tree nodes per output part as the target chunk size. A > complete group can exceed this target. Keep single-file output unchanged > because it has no shared declaration header. > > On aarch64-none-linux-gnu with the default ten parts, the largest-to-smallest > source size ratio changes from 2.43 to 1.10 for GIMPLE and from 1.60 to 1.09 > for GENERIC. This allows for the gimle-match stuff to compile faster > with parallel cores. > > The split Arm profile build compiles all ten GIMPLE parts. Its largest > COND_EXPR function is about 112 kB. A check of emitted pattern markers found > the same order in all 1,902 logical matcher functions with 2, 10, 40, and 64 > parts. > > Bootstrapped and regression tested on aarch64-none-linux-gnu. > The Armv8-A Thumb profile build of all ten GIMPLE matcher parts also passed. > Ok for trunk?
Wheee, this is a lot of code. I see it "works", but it also, for the COND_EXPR_chunk_*, jumps all over the place across .o files. What does this do to the iTLB? It would be nice if the function parts would be adjacent in the final executable [and the calls assembled to fall thru ...]. That said - are we not optimizing the wrong thing here? Does it work to use [[musttail]] for the tail calls? Can we use section attributes to magically (w/o linker script?) perform the desired placing? Do we have the ability (with -flto?) to adjust function placement based on trailing tail calls? That said, I'm tending to NACK as this optimizes GCCs own compile-time trading speed of GCC itself. Richard. > Thanks, > Kyrill > > gcc/ChangeLog: > > * genmatch.cc (MATCHER_FN_FILE_FRACTION): New constant. > (class fn_splitter): New class. > (fn_splitter::print_params, fn_splitter::print_args) > (fn_splitter::cut, fn_splitter::add_subtree) > (fn_splitter::emit_slice, fn_splitter::emit_alternatives): New > functions. > (collect_alt_units): New function. > (dt_node::gen_kids): Add an optional fn_splitter argument and use it > at valid function-level boundaries. > (decision_tree::gen): Set the matcher function budget and use > fn_splitter for large per-operation matchers. > > Signed-off-by: Kyrylo Tkachov <[email protected]> > --- > gcc/genmatch.cc | 327 ++++++++++++++++++++++++++++++++++++++++++++++-- > 1 file changed, 319 insertions(+), 8 deletions(-) > > diff --git a/gcc/genmatch.cc b/gcc/genmatch.cc > index 42a04436c57..155c7e13ac6 100644 > --- a/gcc/genmatch.cc > +++ b/gcc/genmatch.cc > @@ -2516,6 +2516,7 @@ lower (vec<simplify *>& simplifiers, bool gimple) > simplifies and has those as its leafs. */ > > class dt_simplify; > +class fn_splitter; > > /* A hash-map collecting semantically equivalent leafs in the decision > tree for splitting out to separate functions. */ > @@ -2571,7 +2572,7 @@ public: > > virtual void gen (FILE *, int, bool, int) {} > > - void gen_kids (FILE *, int, bool, int, bool); > + void gen_kids (FILE *, int, bool, int, bool, fn_splitter * = NULL); > void gen_kids_1 (FILE *, int, bool, int, > const vec<dt_operand *> &, const vec<dt_operand *> &, > const vec<dt_operand *> &, const vec<dt_operand *> &, > @@ -4259,11 +4260,277 @@ emit_fn_group (FILE *f, int indent, bool gimple, int > depth, > fprintf_indent (f, indent, " break;\n"); > } > > +/* Target matcher functions at this fraction of the decision-tree nodes that > + one output file receives on average. */ > + > +static const unsigned int MATCHER_FN_FILE_FRACTION = 10; > + > +/* Split a generated matcher across functions. Each new function continues > + matching where the previous function stopped. */ > + > +class fn_splitter > +{ > +public: > + /* These are the alternative vectors accepted by gen_kids_1, in their > + emission order. ALT_OTHERS identifies the separate dt_node vector. */ > + enum alt_cat > + { > + ALT_GIMPLE_EXPRS, > + ALT_FNS, > + ALT_GENERIC_EXPRS, > + ALT_GENERIC_FNS, > + ALT_PREDS, > + ALT_OTHERS > + }; > + > + /* One complete group from category CAT at INDEX. NODES estimates the > + amount of generated code for the group. */ > + struct alt_unit > + { > + alt_cat cat; > + unsigned index; > + unsigned nodes; > + }; > + > + fn_splitter (vec<FILE *> &files_, FILE *f_, const char *fname_, > + bool gimple_, unsigned nops_, unsigned budget_) > + : f (f_), files (files_), fname (fname_), gimple (gimple_), > + nops (nops_), budget (budget_), nchunks (0), nodes (0) > + {} > + > + FILE *add_subtree (dt_node *); > + void emit_alternatives (dt_node *, int, int, > + const vec<dt_operand *> &, > + const vec<dt_operand *> &, > + const vec<dt_operand *> &, > + const vec<dt_operand *> &, > + const vec<dt_operand *> &, > + const vec<dt_node *> &); > + > + /* The output file for the current function. */ > + FILE *f; > + > +private: > + /* Return true if adding MORE nodes to HAVE nodes requires a new function. > + Always let an empty function accept one complete alternative. A zero > + budget disables splitting. */ > + bool full (unsigned have, unsigned more) const > + { > + return budget && have && have + more > budget; > + } > + > + void print_params (FILE *); > + void print_args (FILE *); > + void cut (); > + void emit_slice (dt_node *, int, int, const vec<alt_unit> &, unsigned, > + unsigned, const vec<dt_operand_group *> *const *, > + const vec<dt_operand *> &, const vec<dt_node *> &); > + > + /* All output files used for the generated matcher. */ > + vec<FILE *> &files; > + /* The base name for new functions. */ > + const char *fname; > + /* True for GIMPLE matching and false for GENERIC matching. */ > + bool gimple; > + /* The number of operands passed to each function. */ > + unsigned nops; > + /* The target maximum number of nodes accumulated in one function. */ > + unsigned budget; > + /* The number of new functions. */ > + unsigned nchunks; > + /* The estimated nodes in the current function. */ > + unsigned nodes; > +}; > + > +/* Print the parameter list of a new function to TO. Also print its > + declaration to the generated header. */ > + > +void > +fn_splitter::print_params (FILE *to) > +{ > + if (gimple) > + fp_decl (to, " (gimple_match_op *ARG_UNUSED (res_op)," > + " gimple_seq *ARG_UNUSED (seq),\n" > + "\t\t tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n" > + "\t\t code_helper ARG_UNUSED (code)," > + " tree ARG_UNUSED (type)"); > + else > + fp_decl (to, " (location_t ARG_UNUSED (loc)," > + " enum tree_code ARG_UNUSED (code),\n" > + "\t\t const tree ARG_UNUSED (type)"); > + for (unsigned i = 0; i < nops; ++i) > + fp_decl (to, ", tree ARG_UNUSED (_p%d)", i); > + fp_decl (to, ")"); > +} > + > +/* Print to TO the arguments that forward the current matcher state to a new > + function. */ > + > +void > +fn_splitter::print_args (FILE *to) > +{ > + fputs (gimple ? " (res_op, seq, valueize, code, type" > + : " (loc, code, type", to); > + for (unsigned i = 0; i < nops; ++i) > + fprintf (to, ", _p%d", i); > + fputs (")", to); > +} > + > +/* End the current function with a call to a new function. Start the new > + function in the shortest output file. */ > + > +void > +fn_splitter::cut () > +{ > + /* Multiple output files require a header, which also carries the > + declarations for functions emitted in a different file. */ > + gcc_assert (header_file); > + > + const char *ret_type = gimple ? "bool" : "tree"; > + ++nchunks; > + fprintf (f, " return %s_chunk_%u", fname, nchunks); > + print_args (f); > + fputs (";\n}\n", f); > + > + f = choose_output (files); > + fp_decl (f, "\n%s\n%s_chunk_%u", ret_type, fname, nchunks); > + print_params (f); > + fp_decl_done (f, ""); > + fputs ("{\n", f); > + fprintf_indent (f, 2, "const bool debug_dump = " > + "dump_file && (dump_flags & TDF_FOLDING);\n"); > + nodes = 0; > +} > + > +/* Add NODE as a complete subtree. Start a new function before NODE if the > + current one is full. Return the output file for NODE. */ > + > +FILE * > +fn_splitter::add_subtree (dt_node *node) > +{ > + if (full (nodes, node->total_size)) > + cut (); > + nodes += node->total_size; > + return f; > +} > + > +/* Emit alternatives UNITS[FIRST, LAST) for NODE. GROUPS holds the grouped > + expression and function alternatives. PREDS and OTHERS hold the remaining > + operands and decision-tree nodes. */ > + > +void > +fn_splitter::emit_slice (dt_node *node, int indent, int depth, > + const vec<alt_unit> &units, unsigned first, > + unsigned last, > + const vec<dt_operand_group *> *const *groups, > + const vec<dt_operand *> &preds, > + const vec<dt_node *> &others) > +{ > + auto_vec<dt_operand *> sub[ALT_OTHERS]; > + auto_vec<dt_node *> sub_others; > + > + for (unsigned i = first; i < last; ++i) > + if (units[i].cat == ALT_OTHERS) > + sub_others.safe_push (others[units[i].index]); > + else if (units[i].cat == ALT_PREDS) > + sub[ALT_PREDS].safe_push (preds[units[i].index]); > + else > + for (auto op : (*groups[units[i].cat])[units[i].index]->operands) > + sub[units[i].cat].safe_push (op); > + > + node->gen_kids_1 (f, indent, gimple, depth, sub[ALT_GIMPLE_EXPRS], > + sub[ALT_GENERIC_EXPRS], sub[ALT_FNS], > + sub[ALT_GENERIC_FNS], sub[ALT_PREDS], sub_others, false); > +} > + > +/* Append the complete operand GROUPS to UNITS as category CAT. */ > + > +static void > +collect_alt_units (vec<fn_splitter::alt_unit> &units, > + fn_splitter::alt_cat cat, > + const vec<dt_operand_group *> &groups) > +{ > + for (unsigned i = 0; i < groups.length (); ++i) > + { > + /* Only alternatives with a level-one parent inspect a parameter of the > + matcher entry function. */ > + unsigned nodes = 0; > + for (auto op : groups[i]->operands) > + { > + gcc_assert (op->parent && op->parent->level == 1); > + nodes += op->total_size; > + } > + units.safe_push (fn_splitter::alt_unit { cat, i, nodes }); > + } > +} > + > +/* Emit the alternatives for NODE in their normal category order. Start a > + new function before an alternative that exceeds the remaining budget. */ > + > +void > +fn_splitter::emit_alternatives (dt_node *node, int indent, int depth, > + const vec<dt_operand *> &gimple_exprs, > + const vec<dt_operand *> &generic_exprs, > + const vec<dt_operand *> &fns, > + const vec<dt_operand *> &generic_fns, > + const vec<dt_operand *> &preds, > + const vec<dt_node *> &others) > +{ > + auto_delete_vec<dt_operand_group> group_storage[ALT_PREDS]; > + collect_operand_groups (gimple_exprs, group_storage[ALT_GIMPLE_EXPRS]); > + collect_operand_groups (fns, group_storage[ALT_FNS]); > + collect_operand_groups (generic_exprs, > + group_storage[ALT_GENERIC_EXPRS]); > + collect_operand_groups (generic_fns, group_storage[ALT_GENERIC_FNS]); > + > + const vec<dt_operand_group *> *groups[ALT_PREDS]; > + for (unsigned cat = ALT_GIMPLE_EXPRS; cat < ALT_PREDS; ++cat) > + groups[cat] = &group_storage[cat]; > + > + auto_vec<alt_unit> units; > + for (unsigned cat = ALT_GIMPLE_EXPRS; cat < ALT_PREDS; ++cat) > + collect_alt_units (units, (alt_cat) cat, *groups[cat]); > + for (unsigned i = 0; i < preds.length (); ++i) > + { > + gcc_assert (preds[i]->parent && preds[i]->parent->level == 1); > + units.safe_push (alt_unit { ALT_PREDS, i, preds[i]->total_size }); > + } > + for (unsigned i = 0; i < others.length (); ++i) > + units.safe_push (alt_unit { ALT_OTHERS, i, others[i]->total_size }); > + > + if (units.is_empty ()) > + return; > + > + unsigned first = 0; > + unsigned pending = 0; > + for (unsigned i = 0; i < units.length (); ++i) > + { > + if (full (nodes + pending, units[i].nodes)) > + { > + if (first != i) > + emit_slice (node, indent, depth, units, first, i, groups, preds, > + others); > + cut (); > + first = i; > + pending = 0; > + } > + pending += units[i].nodes; > + } > + emit_slice (node, indent, depth, units, first, units.length (), groups, > + preds, others); > + nodes += pending; > +} > + > /* Generate matching code for the children of the decision tree node. */ > > void > -dt_node::gen_kids (FILE *f, int indent, bool gimple, int depth, bool > in_gcond) > +dt_node::gen_kids (FILE *f, int indent, bool gimple, int depth, bool > in_gcond, > + fn_splitter *sp) > { > + /* A gcond matcher starts inside an open scope and is not a valid function > + boundary. */ > + gcc_assert (!sp || !in_gcond); > + > auto_vec<dt_operand *> gimple_exprs; > auto_vec<dt_operand *> generic_exprs; > auto_vec<dt_operand *> fns; > @@ -4332,10 +4599,31 @@ 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. */ > - gen_kids_1 (f, indent, gimple, depth, gimple_exprs, generic_exprs, > - fns, generic_fns, preds, others, in_gcond); > + if (sp) > + { > + sp->emit_alternatives (this, indent, depth, gimple_exprs, > + generic_exprs, fns, generic_fns, preds, > + others); > + f = sp->f; > + } > + else > + gen_kids_1 (f, indent, gimple, depth, gimple_exprs, > + generic_exprs, fns, generic_fns, preds, others, > + in_gcond); > /* And output the true operand itself. */ > - kids[i]->gen (f, indent, gimple, depth); > + if (sp && kids[i]->type == dt_node::DT_TRUE) > + { > + /* A DT_TRUE node emits no code and opens no scope. Its children > + remain valid function-level split points. */ > + kids[i]->gen_kids (f, indent, gimple, depth, false, sp); > + f = sp->f; > + } > + else > + { > + if (sp) > + f = sp->add_subtree (kids[i]); > + kids[i]->gen (f, indent, gimple, depth); > + } > gimple_exprs.truncate (0); > generic_exprs.truncate (0); > fns.truncate (0); > @@ -4348,8 +4636,12 @@ dt_node::gen_kids (FILE *f, int indent, bool gimple, > int depth, bool in_gcond) > } > > /* Generate code for the remains. */ > - gen_kids_1 (f, indent, gimple, depth, gimple_exprs, generic_exprs, > - fns, generic_fns, preds, others, in_gcond); > + if (sp) > + sp->emit_alternatives (this, indent, depth, gimple_exprs, generic_exprs, > + fns, generic_fns, preds, others); > + else > + gen_kids_1 (f, indent, gimple, depth, gimple_exprs, generic_exprs, > + fns, generic_fns, preds, others, in_gcond); > } > > /* Generate matching code for the children of the decision tree node. */ > @@ -5324,6 +5616,14 @@ decision_tree::gen (vec <FILE *> &files, bool gimple) > } > fprintf (stderr, "removed %u duplicate tails\n", rcnt); > > + /* A file receives about ROOT->TOTAL_SIZE / NFILES decision-tree nodes. > + Keep matcher functions small enough to spread them across the files. > + Keep single-file output unchanged. */ > + unsigned nfiles = files.length (); > + unsigned budget = (nfiles > 1 > + ? root->total_size / nfiles / MATCHER_FN_FILE_FRACTION > + : 0); > + > for (unsigned n = 1; n <= 7; ++n) > { > bool has_kids_p = false; > @@ -5366,7 +5666,18 @@ decision_tree::gen (vec <FILE *> &files, bool gimple) > fprintf (f, "{\n"); > fprintf_indent (f, 2, "const bool debug_dump = " > "dump_file && (dump_flags & TDF_FOLDING);\n"); > - dop->gen_kids (f, 2, gimple, 0, false); > + if (budget && dop->total_size > budget) > + { > + char *fname = xasprintf ("genmatch_%s_simplify_%s", > + gimple ? "gimple" : "generic", > + e->operation->id); > + fn_splitter sp (files, f, fname, gimple, n, budget); > + dop->gen_kids (f, 2, gimple, 0, false, &sp); > + f = sp.f; > + free (fname); > + } > + else > + dop->gen_kids (f, 2, gimple, 0, false); > if (gimple) > fprintf (f, " return false;\n"); > else > -- 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)
