From: Kyrylo Tkachov <[email protected]> Each copy of a dispatch made by pass_duplicate_computed_gotos gets an edge to every target of the original. The number of new edges is therefore the product of the number of copies and the number of targets, which is quadratic in the size of an interpreter. The instruction budget does not bound this, since a copy of a shared-table dispatch is only a few insns.
Since -fduplicate-switch-dispatch became the default at -O2, compiling POVRay fnpovfpu.cpp copies a 971-target dispatch 830 times and adds about 660000 edges. Compared with -fno-duplicate-switch-dispatch, compile time grows by a factor of 8.5 and peak memory by a factor of 5.6, mostly in RTL-SSA construction for fold-mem-offsets and the AArch64 reorg pass. Add --param=max-goto-duplication-edges, the number of edges that the copies in one function may add. Charge each copy for its edges, and stop copying once the budget cannot cover another copy. The limit applies to computed gotos and to switch dispatches alike. The default of 131072 leaves the dispatch copies of CPython, QuickJS, Lua and mawk unchanged, the largest of which adds about 93000 edges. On fnpovfpu.cpp it keeps 165 of the 830 copies. At -O2 this reduces the compile time of that file by 77% and its peak memory by 67%, and the compile time of the whole of 511.povray_r by 12%. Duplication does not change the runtime of 511.povray_r, as the interpreter does not run in the benchmark. Bootstrapped and tested on aarch64-none-linux-gnu. Ok for trunk? Thanks, Kyrill Cc: Jeff Law <[email protected]> gcc/ChangeLog: PR target/128512 * params.opt (--param=max-goto-duplication-edges=): New param. * doc/params.texi (max-goto-duplication-edges): Document. * bb-reorder.cc (maybe_duplicate_dispatch): Add EDGE_BUDGET parameter. Stop copying once it cannot cover the edges of a copy. (duplicate_computed_gotos): Initialize it from the param. gcc/testsuite/ChangeLog: PR target/128512 * gcc.dg/duplicate-computed-goto-3.c: New test. * gcc.dg/switch-dispatch-6.c: New test. Signed-off-by: Kyrylo Tkachov <[email protected]> --- gcc/bb-reorder.cc | 21 +++++++++++++++---- gcc/doc/params.texi | 8 +++++++ gcc/params.opt | 4 ++++ .../gcc.dg/duplicate-computed-goto-3.c | 11 ++++++++++ gcc/testsuite/gcc.dg/switch-dispatch-6.c | 10 +++++++++ 5 files changed, 50 insertions(+), 4 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/duplicate-computed-goto-3.c create mode 100644 gcc/testsuite/gcc.dg/switch-dispatch-6.c diff --git a/gcc/bb-reorder.cc b/gcc/bb-reorder.cc index 81a1e0f9ddd..895f7000ba3 100644 --- a/gcc/bb-reorder.cc +++ b/gcc/bb-reorder.cc @@ -2862,10 +2862,13 @@ find_dispatch_chain (basic_block bb, int max_size, reached through, into the predecessors of that chain, where possible. MAX_SIZE limits the size of the chain, in units of duplication_unit. If REQUIRE_BACK_EDGE is true, first require a DFS back edge into the head - of the chain. Return whether anything is changed. */ + of the chain. EDGE_BUDGET is the number of CFG edges that the copies may + still add to the function. It is reduced by the edges of each copy, and + no further copy is made once it cannot cover one. Return whether anything + is changed. */ static bool maybe_duplicate_dispatch (basic_block bb, int max_size, - bool require_back_edge) + bool require_back_edge, int &edge_budget) { auto_vec<basic_block, 4> chain; basic_block head = find_dispatch_chain (bb, max_size, &chain); @@ -2902,6 +2905,12 @@ maybe_duplicate_dispatch (basic_block bb, int max_size, continue; } + /* A copy of the dispatch gets an edge to each target of the original. */ + int copy_edges = EDGE_COUNT (bb->succs); + if (copy_edges > edge_budget) + break; + edge_budget -= copy_edges; + if (dump_file) fprintf (dump_file, "Duplicating dispatch bb %d into bb %d\n", bb->index, pred->index); @@ -2958,7 +2967,8 @@ maybe_duplicate_dispatch (basic_block bb, int max_size, /* Try to merge the resulting dispatch block into further predecessors. */ if (can_dup_more) - maybe_duplicate_dispatch (first == last ? pred : last, max_size, false); + maybe_duplicate_dispatch (first == last ? pred : last, max_size, false, + edge_budget); } return changed; @@ -2979,6 +2989,8 @@ duplicate_computed_gotos (function *fun) /* Never copy a block larger than this. */ int max_size = duplication_unit () * param_max_goto_duplication_insns; + int edge_budget = param_max_goto_duplication_edges; + bool changed = false; bool back_edges_marked = false; @@ -3002,7 +3014,8 @@ duplicate_computed_gotos (function *fun) back_edges_marked = true; } - changed |= maybe_duplicate_dispatch (bb, max_size, tablejump); + changed |= maybe_duplicate_dispatch (bb, max_size, tablejump, + edge_budget); } fun->curr_properties &= ~PROP_rtl_allow_tablejump_duplication; diff --git a/gcc/doc/params.texi b/gcc/doc/params.texi index 43a1397971d..fadac385004 100644 --- a/gcc/doc/params.texi +++ b/gcc/doc/params.texi @@ -125,6 +125,14 @@ end of a basic blocks with no more than @code{max-goto-duplication-insns} are unfactored. With @option{-fduplicate-switch-dispatch}, the same limit applies to switch dispatches. +@paindex max-goto-duplication-edges +@item max-goto-duplication-edges +The maximum number of CFG edges that unfactoring computed gotos or switch +dispatches may add to a function. Each copy of a dispatch adds an edge to +every target of the original, so the number of edges grows with the product +of the number of copies and the number of targets. Once the limit is +reached the remaining dispatch blocks are left uncopied. + @paindex max-delay-slot-insn-search @item max-delay-slot-insn-search The maximum number of instructions to consider when looking for an diff --git a/gcc/params.opt b/gcc/params.opt index b1be4339bb6..c3ea736e05f 100644 --- a/gcc/params.opt +++ b/gcc/params.opt @@ -622,6 +622,10 @@ The maximum amount of memory to be allocated by GCSE, in kilobytes. Common Joined UInteger Var(param_max_goto_duplication_insns) Init(8) Param Optimization The maximum number of insns to duplicate when unfactoring computed gotos or switch dispatches. +-param=max-goto-duplication-edges= +Common Joined UInteger Var(param_max_goto_duplication_edges) Init(131072) Param Optimization +The maximum number of CFG edges that unfactoring computed gotos or switch dispatches may add to a function. + -param=max-grow-copy-bb-insns= Common Joined UInteger Var(param_max_grow_copy_bb_insns) Init(8) Param Optimization The maximum expansion factor when copying basic blocks. diff --git a/gcc/testsuite/gcc.dg/duplicate-computed-goto-3.c b/gcc/testsuite/gcc.dg/duplicate-computed-goto-3.c new file mode 100644 index 00000000000..aba39609594 --- /dev/null +++ b/gcc/testsuite/gcc.dg/duplicate-computed-goto-3.c @@ -0,0 +1,11 @@ +/* PR middle-end/128512 */ +/* { dg-do compile } */ +/* { dg-require-effective-target label_values } */ +/* { dg-require-effective-target indirect_jumps } */ +/* { dg-options "-O2 -fno-tree-slp-vectorize --param=max-goto-duplication-edges=0 -fdump-rtl-compgotos" } */ + +/* A zero edge budget disables computed goto duplication. */ + +#include "pr127246-1.c" + +/* { dg-final { scan-rtl-dump-not "Duplicating" "compgotos" } } */ diff --git a/gcc/testsuite/gcc.dg/switch-dispatch-6.c b/gcc/testsuite/gcc.dg/switch-dispatch-6.c new file mode 100644 index 00000000000..3e7216924a8 --- /dev/null +++ b/gcc/testsuite/gcc.dg/switch-dispatch-6.c @@ -0,0 +1,10 @@ +/* PR middle-end/128512 */ +/* { dg-do run } */ +/* { dg-options "-O2 --param=max-goto-duplication-insns=128 --param=max-goto-duplication-edges=0 --param=case-values-threshold=1 -fdump-rtl-compgotos-details" } */ + +/* A zero edge budget leaves the switch dispatches of + switch-dispatch-run-5.c uncopied. */ + +#include "torture/switch-dispatch-run-5.c" + +/* { dg-final { scan-rtl-dump-not "Duplicating" "compgotos" } } */ -- 2.54.0 (Apple Git-157)
