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?
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
--
2.50.1 (Apple Git-155)
