From: Richard Biener <richard.guenther@gmail.com>
To: "Martin Liška" <mliska@suse.cz>
Cc: GCC Patches <gcc-patches@gcc.gnu.org>
Subject: Re: [PATCH] Speed up jump table switch detection.
Date: Mon, 16 Aug 2021 13:27:57 +0200 [thread overview]
Message-ID: <CAFiYyc2ij8mwXAUkwJ4+qfiygoZe9bZ3ui_Qa1TfToupN6ZcCQ@mail.gmail.com> (raw)
In-Reply-To: <e6ae125a-596c-3a20-5ff6-02d2e3f28eee@suse.cz>
On Mon, Aug 16, 2021 at 10:28 AM Martin Liška <mliska@suse.cz> wrote:
>
> Hi.
>
> As mentioned in the PR, this patch speeds up rapidly jump table detection
> in switch lowering.
>
> Patch can bootstrap on x86_64-linux-gnu and survives regression tests.
>
> Ready to be installed?
OK.
> Thanks,
> Martin
>
> PR tree-optimization/100393
>
> gcc/ChangeLog:
>
> * tree-switch-conversion.c (group_cluster::dump): Use
> get_comparison_count.
> (jump_table_cluster::find_jump_tables): Pre-compute number of
> comparisons and then decrement it. Cache also max_ratio.
> (jump_table_cluster::can_be_handled): Change signature.
> * tree-switch-conversion.h (get_comparison_count): New.
> ---
> gcc/tree-switch-conversion.c | 42 ++++++++++++++++++++----------------
> gcc/tree-switch-conversion.h | 14 ++++++++++--
> 2 files changed, 35 insertions(+), 21 deletions(-)
>
> diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c
> index 294b5457008..244cf4be010 100644
> --- a/gcc/tree-switch-conversion.c
> +++ b/gcc/tree-switch-conversion.c
> @@ -1091,7 +1091,7 @@ group_cluster::dump (FILE *f, bool details)
> for (unsigned i = 0; i < m_cases.length (); i++)
> {
> simple_cluster *sc = static_cast<simple_cluster *> (m_cases[i]);
> - comparison_count += sc->m_range_p ? 2 : 1;
> + comparison_count += sc->get_comparison_count ();
> }
>
> unsigned HOST_WIDE_INT range = get_range (get_low (), get_high ());
> @@ -1186,11 +1186,24 @@ jump_table_cluster::find_jump_tables (vec<cluster *> &clusters)
>
> min.quick_push (min_cluster_item (0, 0, 0));
>
> + unsigned HOST_WIDE_INT max_ratio
> + = (optimize_insn_for_size_p ()
> + ? param_jump_table_max_growth_ratio_for_size
> + : param_jump_table_max_growth_ratio_for_speed);
> +
> for (unsigned i = 1; i <= l; i++)
> {
> /* Set minimal # of clusters with i-th item to infinite. */
> min.quick_push (min_cluster_item (INT_MAX, INT_MAX, INT_MAX));
>
> + /* Pre-calculate number of comparisons for the clusters. */
> + HOST_WIDE_INT comparison_count = 0;
> + for (unsigned k = 0; k <= i - 1; k++)
> + {
> + simple_cluster *sc = static_cast<simple_cluster *> (clusters[k]);
> + comparison_count += sc->get_comparison_count ();
> + }
> +
> for (unsigned j = 0; j < i; j++)
> {
> unsigned HOST_WIDE_INT s = min[j].m_non_jt_cases;
> @@ -1201,10 +1214,15 @@ jump_table_cluster::find_jump_tables (vec<cluster *> &clusters)
> if ((min[j].m_count + 1 < min[i].m_count
> || (min[j].m_count + 1 == min[i].m_count
> && s < min[i].m_non_jt_cases))
> - && can_be_handled (clusters, j, i - 1))
> + && can_be_handled (clusters, j, i - 1, max_ratio,
> + comparison_count))
> min[i] = min_cluster_item (min[j].m_count + 1, j, s);
> +
> + simple_cluster *sc = static_cast<simple_cluster *> (clusters[j]);
> + comparison_count -= sc->get_comparison_count ();
> }
>
> + gcc_checking_assert (comparison_count == 0);
> gcc_checking_assert (min[i].m_count != INT_MAX);
> }
>
> @@ -1242,7 +1260,9 @@ jump_table_cluster::find_jump_tables (vec<cluster *> &clusters)
>
> bool
> jump_table_cluster::can_be_handled (const vec<cluster *> &clusters,
> - unsigned start, unsigned end)
> + unsigned start, unsigned end,
> + unsigned HOST_WIDE_INT max_ratio,
> + unsigned HOST_WIDE_INT comparison_count)
> {
> /* If the switch is relatively small such that the cost of one
> indirect jump on the target are higher than the cost of a
> @@ -1261,10 +1281,6 @@ jump_table_cluster::can_be_handled (const vec<cluster *> &clusters,
> if (start == end)
> return true;
>
> - unsigned HOST_WIDE_INT max_ratio
> - = (optimize_insn_for_size_p ()
> - ? param_jump_table_max_growth_ratio_for_size
> - : param_jump_table_max_growth_ratio_for_speed);
> unsigned HOST_WIDE_INT range = get_range (clusters[start]->get_low (),
> clusters[end]->get_high ());
> /* Check overflow. */
> @@ -1278,18 +1294,6 @@ jump_table_cluster::can_be_handled (const vec<cluster *> &clusters,
> if (lhs < range)
> return false;
>
> - /* First make quick guess as each cluster
> - can add at maximum 2 to the comparison_count. */
> - if (lhs > 2 * max_ratio * (end - start + 1))
> - return false;
> -
> - unsigned HOST_WIDE_INT comparison_count = 0;
> - for (unsigned i = start; i <= end; i++)
> - {
> - simple_cluster *sc = static_cast<simple_cluster *> (clusters[i]);
> - comparison_count += sc->m_range_p ? 2 : 1;
> - }
> -
> return lhs <= max_ratio * comparison_count;
> }
>
> diff --git a/gcc/tree-switch-conversion.h b/gcc/tree-switch-conversion.h
> index d76f19b57f6..a375e52636e 100644
> --- a/gcc/tree-switch-conversion.h
> +++ b/gcc/tree-switch-conversion.h
> @@ -180,6 +180,13 @@ public:
> return tree_int_cst_equal (get_low (), get_high ());
> }
>
> + /* Return number of comparisons needed for the case. */
> + unsigned
> + get_comparison_count ()
> + {
> + return m_range_p ? 2 : 1;
> + }
> +
> /* Low value of the case. */
> tree m_low;
>
> @@ -267,9 +274,12 @@ public:
> static vec<cluster *> find_jump_tables (vec<cluster *> &clusters);
>
> /* Return true when cluster starting at START and ending at END (inclusive)
> - can build a jump-table. */
> + can build a jump-table. COMPARISON_COUNT is number of comparison
> + operations needed if the clusters are expanded as decision tree.
> + MAX_RATIO tells about the maximum code growth (in percent). */
> static bool can_be_handled (const vec<cluster *> &clusters, unsigned start,
> - unsigned end);
> + unsigned end, unsigned HOST_WIDE_INT max_ratio,
> + unsigned HOST_WIDE_INT comparison_count);
>
> /* Return true if cluster starting at START and ending at END (inclusive)
> is profitable transformation. */
> --
> 2.32.0
>
prev parent reply other threads:[~2021-08-16 11:28 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-08-16 8:28 Martin Liška
2021-08-16 11:27 ` Richard Biener [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAFiYyc2ij8mwXAUkwJ4+qfiygoZe9bZ3ui_Qa1TfToupN6ZcCQ@mail.gmail.com \
--to=richard.guenther@gmail.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=mliska@suse.cz \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).