public inbox for gcc-cvs@sourceware.org help / color / mirror / Atom feed
From: Martin Liska <marxin@gcc.gnu.org> To: gcc-cvs@gcc.gnu.org Subject: [gcc(refs/users/marxin/heads/backport-11)] Speed up jump table switch detection. Date: Fri, 5 Nov 2021 14:43:36 +0000 (GMT) [thread overview] Message-ID: <20211105144336.6AB0C3858436@sourceware.org> (raw) https://gcc.gnu.org/g:64fbc25cb6983725fefe313bfedd3657df795d54 commit 64fbc25cb6983725fefe313bfedd3657df795d54 Author: Martin Liska <mliska@suse.cz> Date: Fri Aug 13 17:22:35 2021 +0200 Speed up jump table switch detection. 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. (cherry picked from commit c517cf2e685e2903b591d63c1034ff9726cb3822) Diff: --- 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 7f65c4ce839..8fc5eaa3033 100644 --- a/gcc/tree-switch-conversion.c +++ b/gcc/tree-switch-conversion.c @@ -1090,7 +1090,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 ()); @@ -1185,11 +1185,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; @@ -1200,10 +1213,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); } @@ -1241,7 +1259,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 @@ -1260,10 +1280,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. */ @@ -1277,18 +1293,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. */
next reply other threads:[~2021-11-05 14:43 UTC|newest] Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top 2021-11-05 14:43 Martin Liska [this message] -- strict thread matches above, loose matches on Subject: below -- 2021-08-16 11:40 Martin Liska
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=20211105144336.6AB0C3858436@sourceware.org \ --to=marxin@gcc.gnu.org \ --cc=gcc-cvs@gcc.gnu.org \ /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: linkBe 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).