commit: b6ea2bc8cb10601f270dfd82a9d1878862ebeffa Author: Sam James <sam <AT> gentoo <DOT> org> AuthorDate: Mon May 5 13:04:48 2025 +0000 Commit: Sam James <sam <AT> gentoo <DOT> org> CommitDate: Mon May 5 13:04:48 2025 +0000 URL: https://gitweb.gentoo.org/proj/gcc-patches.git/commit/?id=b6ea2bc8
16.0.0: revert switch conversion patches Breaks building LLVM and workarounds aren't feasible (PR120115, PR120116). Bug: https://gcc.gnu.org/PR120080 Bug: https://gcc.gnu.org/PR120115 Bug: https://gcc.gnu.org/PR120116 Signed-off-by: Sam James <sam <AT> gentoo.org> ...le-Switch-bit-test-lowering-testcases-for.patch | 141 +++++++++++ ...le-Don-t-warn-about-using-different-algs-.patch | 35 +++ ...le-Make-bit-test-switch-lowering-more-pow.patch | 258 +++++++++++++++++++++ ...le-Merge-slow-and-fast-bit-test-switch-lo.patch | 157 +++++++++++++ 4 files changed, 591 insertions(+) diff --git a/16.0.0/gentoo/85_all_PR120080_Revert-gimple-Switch-bit-test-lowering-testcases-for.patch b/16.0.0/gentoo/85_all_PR120080_Revert-gimple-Switch-bit-test-lowering-testcases-for.patch new file mode 100644 index 0000000..a6df8d9 --- /dev/null +++ b/16.0.0/gentoo/85_all_PR120080_Revert-gimple-Switch-bit-test-lowering-testcases-for.patch @@ -0,0 +1,141 @@ +From 4c57a4d3c280b249649495e032682f5eea41752b Mon Sep 17 00:00:00 2001 +Message-ID: <4c57a4d3c280b249649495e032682f5eea41752b.1746450157.git....@gentoo.org> +From: Sam James <[email protected]> +Date: Mon, 5 May 2025 14:02:03 +0100 +Subject: [PATCH 1/4] Revert "gimple: Switch bit-test lowering testcases for + the more powerful alg" + +This reverts commit 8444c4cc7648f4396e2a3726677f909438e92c80. +--- + gcc/testsuite/gcc.dg/tree-ssa/switch-5.c | 60 ------------------------ + gcc/testsuite/gcc.dg/tree-ssa/switch-6.c | 51 -------------------- + 2 files changed, 111 deletions(-) + delete mode 100644 gcc/testsuite/gcc.dg/tree-ssa/switch-5.c + delete mode 100644 gcc/testsuite/gcc.dg/tree-ssa/switch-6.c + +diff --git a/gcc/testsuite/gcc.dg/tree-ssa/switch-5.c b/gcc/testsuite/gcc.dg/tree-ssa/switch-5.c +deleted file mode 100644 +index b05742cf153c..000000000000 +--- a/gcc/testsuite/gcc.dg/tree-ssa/switch-5.c ++++ /dev/null +@@ -1,60 +0,0 @@ +-/* { dg-do compile { target { { x86_64-*-* aarch64-*-* ia64-*-* powerpc64-*-* } && lp64 } } } */ +-/* { dg-options "-O2 -fdump-tree-switchlower1" } */ +- +-int f0(); +-int f1(); +-int f2(); +-int f3(); +-int f4(); +- +-int foo(int a) +-{ +- switch (a) +- { +- case 0: +- case 2: +- case 4: +- case 6: +- return f0(); +- case 8: +- return f1(); +- case 10: +- case 14: +- case 16: +- case 18: +- return f2(); +- case 12: +- return f3(); +- case 20: +- return f4(); +- } +- return -1; +-} +- +-/* { dg-final { scan-tree-dump ";; GIMPLE switch case clusters: BT:0-8 BT:10-20" "switchlower1" } } */ +- +-int bar(int a) +-{ +- switch (a) +- { +- case 20: +- case 18: +- case 16: +- case 14: +- return f0(); +- case 12: +- return f1(); +- case 10: +- case 6: +- case 4: +- case 2: +- return f2(); +- case 8: +- return f3(); +- case 0: +- return f4(); +- } +- return -1; +-} +- +-/* { dg-final { scan-tree-dump ";; GIMPLE switch case clusters: BT:0-10 BT:12-20" "switchlower1" } } */ +diff --git a/gcc/testsuite/gcc.dg/tree-ssa/switch-6.c b/gcc/testsuite/gcc.dg/tree-ssa/switch-6.c +deleted file mode 100644 +index bbbc87462c40..000000000000 +--- a/gcc/testsuite/gcc.dg/tree-ssa/switch-6.c ++++ /dev/null +@@ -1,51 +0,0 @@ +-/* { dg-do compile { target { { x86_64-*-* aarch64-*-* ia64-*-* powerpc64-*-* } && lp64 } } } */ +-/* { dg-options "-O2 -fdump-tree-switchlower1 -fno-jump-tables" } */ +- +-/* Test that bit-test switch lowering can create cluster of size 64 (there was +- an of-by-one error causing it to only do 63 before). */ +- +-int f(); +- +-int foo(int a) +-{ +- switch (a) +- { +- case 0: +- case 3: +- case 5: +- case 7: +- case 9: +- case 11: +- case 13: +- case 15: +- case 17: +- case 19: +- case 21: +- case 23: +- case 25: +- case 27: +- case 29: +- case 31: +- case 33: +- case 35: +- case 37: +- case 39: +- case 41: +- case 43: +- case 45: +- case 47: +- case 49: +- case 51: +- case 53: +- case 55: +- case 57: +- case 59: +- case 61: +- case 63: +- return f(); +- default: +- return -1; +- } +-} +- +-/* { dg-final { scan-tree-dump ";; GIMPLE switch case clusters: BT:0-63" "switchlower1" } } */ +-- +2.49.0 + diff --git a/16.0.0/gentoo/86_all_PR120080_Revert-gimple-Don-t-warn-about-using-different-algs-.patch b/16.0.0/gentoo/86_all_PR120080_Revert-gimple-Don-t-warn-about-using-different-algs-.patch new file mode 100644 index 0000000..eed3cdb --- /dev/null +++ b/16.0.0/gentoo/86_all_PR120080_Revert-gimple-Don-t-warn-about-using-different-algs-.patch @@ -0,0 +1,35 @@ +From e11fc43562a4aaa15b757d5728dd5a514e128bee Mon Sep 17 00:00:00 2001 +Message-ID: <e11fc43562a4aaa15b757d5728dd5a514e128bee.1746450157.git....@gentoo.org> +In-Reply-To: <4c57a4d3c280b249649495e032682f5eea41752b.1746450157.git....@gentoo.org> +References: <4c57a4d3c280b249649495e032682f5eea41752b.1746450157.git....@gentoo.org> +From: Sam James <[email protected]> +Date: Mon, 5 May 2025 14:02:09 +0100 +Subject: [PATCH 2/4] Revert "gimple: Don't warn about using different algs for + big switch lowering [PR117091]" + +This reverts commit c14560907a9586ad405f26ab937881eb08f39497. +--- + gcc/tree-switch-conversion.cc | 7 +++++++ + 1 file changed, 7 insertions(+) + +diff --git a/gcc/tree-switch-conversion.cc b/gcc/tree-switch-conversion.cc +index dea217a01efb..4f0be8c43f07 100644 +--- a/gcc/tree-switch-conversion.cc ++++ b/gcc/tree-switch-conversion.cc +@@ -2257,6 +2257,13 @@ switch_decision_tree::analyze_switch_statement () + + reset_out_edges_aux (m_switch); + ++ if (l > (unsigned) param_switch_lower_slow_alg_max_cases) ++ warning_at (gimple_location (m_switch), OPT_Wdisabled_optimization, ++ "Using faster switch lowering algorithms. " ++ "Number of switch cases (%d) exceeds " ++ "%<--param=switch-lower-slow-alg-max-cases=%d%> limit.", ++ l, param_switch_lower_slow_alg_max_cases); ++ + /* Find bit-test clusters. */ + vec<cluster *> output = bit_test_cluster::find_bit_tests (clusters, max_c); + +-- +2.49.0 + diff --git a/16.0.0/gentoo/87_all_PR120080-Revert-gimple-Make-bit-test-switch-lowering-more-pow.patch b/16.0.0/gentoo/87_all_PR120080-Revert-gimple-Make-bit-test-switch-lowering-more-pow.patch new file mode 100644 index 0000000..bb246ad --- /dev/null +++ b/16.0.0/gentoo/87_all_PR120080-Revert-gimple-Make-bit-test-switch-lowering-more-pow.patch @@ -0,0 +1,258 @@ +From 22f45f552e6dfe51256f4f1c423a51b831ab46d8 Mon Sep 17 00:00:00 2001 +Message-ID: <22f45f552e6dfe51256f4f1c423a51b831ab46d8.1746450157.git....@gentoo.org> +In-Reply-To: <4c57a4d3c280b249649495e032682f5eea41752b.1746450157.git....@gentoo.org> +References: <4c57a4d3c280b249649495e032682f5eea41752b.1746450157.git....@gentoo.org> +From: Sam James <[email protected]> +Date: Mon, 5 May 2025 14:02:17 +0100 +Subject: [PATCH 3/4] Revert "gimple: Make bit-test switch lowering more + powerful" + +This reverts commit 1381a5114788a2e9234ff54e0cd7a3c810f0d02d. +--- + gcc/tree-switch-conversion.cc | 153 +++++++++++++++++++--------------- + gcc/tree-switch-conversion.h | 10 +++ + 2 files changed, 96 insertions(+), 67 deletions(-) + +diff --git a/gcc/tree-switch-conversion.cc b/gcc/tree-switch-conversion.cc +index 4f0be8c43f07..a70274b03372 100644 +--- a/gcc/tree-switch-conversion.cc ++++ b/gcc/tree-switch-conversion.cc +@@ -1783,98 +1783,58 @@ bit_test_cluster::find_bit_tests (vec<cluster *> &clusters, int max_c) + if (!is_enabled () || max_c == 1) + return clusters.copy (); + +- /* Dynamic programming algorithm. +- +- In: List of simple clusters +- Out: List of simple clusters and bit test clusters such that each bit test +- cluster can_be_handled() and is_beneficial() +- +- Tries to merge consecutive clusters into bigger (bit test) ones. Tries to +- end up with as few clusters as possible. */ +- + unsigned l = clusters.length (); + auto_vec<min_cluster_item> min; + min.reserve (l + 1); + +- gcc_checking_assert (l > 0); +- gcc_checking_assert (l <= INT_MAX); +- +- int bits_in_word = GET_MODE_BITSIZE (word_mode); ++ min.quick_push (min_cluster_item (0, 0, 0)); + +- /* First phase: Compute the minimum number of clusters for each prefix of the +- input list incrementally ++ unsigned bits_in_word = GET_MODE_BITSIZE (word_mode); + +- min[i] = (count, j, _) means that the prefix ending with the (i-1)-th +- element can be made to contain as few as count clusters and that in such +- clustering the last cluster is made up of input clusters [j, i-1] +- (inclusive). */ +- min.quick_push (min_cluster_item (0, 0, INT_MAX)); +- min.quick_push (min_cluster_item (1, 0, INT_MAX)); +- for (int i = 2; i <= (int) l; i++) ++ for (unsigned i = 1; i <= l; i++) + { +- auto_vec<unsigned, m_max_case_bit_tests> unique_labels; ++ /* Set minimal # of clusters with i-th item to infinite. */ ++ min.quick_push (min_cluster_item (INT_MAX, INT_MAX, INT_MAX)); + + /* Since each cluster contains at least one case number and one bit test + cluster can cover at most bits_in_word case numbers, we don't need to + look farther than bits_in_word clusters back. */ +- for (int j = i - 1; j >= 0 && j >= i - bits_in_word; j--) ++ unsigned j; ++ if (i - 1 >= bits_in_word) ++ j = i - 1 - bits_in_word; ++ else ++ j = 0; ++ for (; j < i; j++) + { +- /* Consider creating a bit test cluster from input clusters [j, i-1] +- (inclusive) */ +- +- simple_cluster *sc = static_cast<simple_cluster *> (clusters[j]); +- unsigned label = sc->m_case_bb->index; +- if (!unique_labels.contains (label)) +- { +- if (unique_labels.length () >= m_max_case_bit_tests) +- /* is_beneficial() will be false for this and the following +- iterations. */ +- break; +- unique_labels.quick_push (label); +- } +- +- unsigned new_count = min[j].m_count + 1; +- +- if (j == i - 1) +- { +- min.quick_push (min_cluster_item (new_count, j, INT_MAX)); +- continue; +- } +- +- unsigned HOST_WIDE_INT range +- = get_range (clusters[j]->get_low (), clusters[i-1]->get_high ()); +- if (new_count < min[i].m_count +- && can_be_handled (range, unique_labels.length ()) +- && is_beneficial (i - j, unique_labels.length ())) +- min[i] = min_cluster_item (new_count, j, INT_MAX); ++ if (min[j].m_count + 1 < min[i].m_count ++ && can_be_handled (clusters, j, i - 1)) ++ min[i] = min_cluster_item (min[j].m_count + 1, j, INT_MAX); + } ++ ++ gcc_checking_assert (min[i].m_count != INT_MAX); + } + ++ /* No result. */ + if (min[l].m_count == l) +- /* No bit test clustering opportunities. */ + return clusters.copy (); + + vec<cluster *> output; + output.create (4); + +- /* Second phase: Find and build the bit test clusters by traversing min +- array backwards. */ ++ /* Find and build the clusters. */ + for (unsigned end = l;;) + { +- unsigned start = min[end].m_start; +- gcc_checking_assert (start < end); +- +- /* This cluster will be made out of input clusters [start, end - 1]. */ ++ int start = min[end].m_start; + +- if (start == end - 1) +- /* Let the cluster be a simple cluster. */ +- output.safe_push (clusters[start]); +- else ++ if (is_beneficial (clusters, start, end - 1)) + { +- bool entire = start == 0 && end == l; ++ bool entire = start == 0 && end == clusters.length (); + output.safe_push (new bit_test_cluster (clusters, start, end - 1, + entire)); + } ++ else ++ for (int i = end - 1; i >= start; i--) ++ output.safe_push (clusters[i]); + + end = start; + +@@ -1897,25 +1857,84 @@ bit_test_cluster::can_be_handled (unsigned HOST_WIDE_INT range, + if (range == 0) + return false; + +- if (range > GET_MODE_BITSIZE (word_mode)) ++ if (range >= GET_MODE_BITSIZE (word_mode)) + return false; + + return uniq <= m_max_case_bit_tests; + } + ++/* Return true when cluster starting at START and ending at END (inclusive) ++ can build a bit test. */ ++ ++bool ++bit_test_cluster::can_be_handled (const vec<cluster *> &clusters, ++ unsigned start, unsigned end) ++{ ++ auto_vec<int, m_max_case_bit_tests> dest_bbs; ++ /* For algorithm correctness, bit test for a single case must return ++ true. We bail out in is_beneficial if it's called just for ++ a single case. */ ++ if (start == end) ++ return true; ++ ++ unsigned HOST_WIDE_INT range = get_range (clusters[start]->get_low (), ++ clusters[end]->get_high ()); ++ ++ /* Make a guess first. */ ++ if (!can_be_handled (range, m_max_case_bit_tests)) ++ return false; ++ ++ for (unsigned i = start; i <= end; i++) ++ { ++ simple_cluster *sc = static_cast<simple_cluster *> (clusters[i]); ++ /* m_max_case_bit_tests is very small integer, thus the operation ++ is constant. */ ++ if (!dest_bbs.contains (sc->m_case_bb->index)) ++ { ++ if (dest_bbs.length () >= m_max_case_bit_tests) ++ return false; ++ dest_bbs.quick_push (sc->m_case_bb->index); ++ } ++ } ++ ++ return true; ++} ++ + /* Return true when COUNT of cases of UNIQ labels is beneficial for bit test + transformation. */ + + bool + bit_test_cluster::is_beneficial (unsigned count, unsigned uniq) + { +- /* NOTE: When modifying this, keep in mind the value of +- m_max_case_bit_tests. */ + return (((uniq == 1 && count >= 3) + || (uniq == 2 && count >= 5) + || (uniq == 3 && count >= 6))); + } + ++/* Return true if cluster starting at START and ending at END (inclusive) ++ is profitable transformation. */ ++ ++bool ++bit_test_cluster::is_beneficial (const vec<cluster *> &clusters, ++ unsigned start, unsigned end) ++{ ++ /* Single case bail out. */ ++ if (start == end) ++ return false; ++ ++ auto_bitmap dest_bbs; ++ ++ for (unsigned i = start; i <= end; i++) ++ { ++ simple_cluster *sc = static_cast<simple_cluster *> (clusters[i]); ++ bitmap_set_bit (dest_bbs, sc->m_case_bb->index); ++ } ++ ++ unsigned uniq = bitmap_count_bits (dest_bbs); ++ unsigned count = end - start + 1; ++ return is_beneficial (count, uniq); ++} ++ + /* Comparison function for qsort to order bit tests by decreasing + probability of execution. */ + +diff --git a/gcc/tree-switch-conversion.h b/gcc/tree-switch-conversion.h +index b2b6ddc731fb..2ed7e1c7efc1 100644 +--- a/gcc/tree-switch-conversion.h ++++ b/gcc/tree-switch-conversion.h +@@ -423,10 +423,20 @@ public: + can build a bit test. */ + static bool can_be_handled (unsigned HOST_WIDE_INT range, unsigned uniq); + ++ /* Return true when cluster starting at START and ending at END (inclusive) ++ can build a bit test. */ ++ static bool can_be_handled (const vec<cluster *> &clusters, unsigned start, ++ unsigned end); ++ + /* Return true when COUNT of cases of UNIQ labels is beneficial for bit test + transformation. */ + static bool is_beneficial (unsigned count, unsigned uniq); + ++ /* Return true if cluster starting at START and ending at END (inclusive) ++ is profitable transformation. */ ++ static bool is_beneficial (const vec<cluster *> &clusters, unsigned start, ++ unsigned end); ++ + /* Split the basic block at the statement pointed to by GSIP, and insert + a branch to the target basic block of E_TRUE conditional on tree + expression COND. +-- +2.49.0 + diff --git a/16.0.0/gentoo/88_all_PR120080-Revert-gimple-Merge-slow-and-fast-bit-test-switch-lo.patch b/16.0.0/gentoo/88_all_PR120080-Revert-gimple-Merge-slow-and-fast-bit-test-switch-lo.patch new file mode 100644 index 0000000..ce952f0 --- /dev/null +++ b/16.0.0/gentoo/88_all_PR120080-Revert-gimple-Merge-slow-and-fast-bit-test-switch-lo.patch @@ -0,0 +1,157 @@ +From 3827851b3d589780a9dc072962a266bae18272ad Mon Sep 17 00:00:00 2001 +Message-ID: <3827851b3d589780a9dc072962a266bae18272ad.1746450157.git....@gentoo.org> +In-Reply-To: <4c57a4d3c280b249649495e032682f5eea41752b.1746450157.git....@gentoo.org> +References: <4c57a4d3c280b249649495e032682f5eea41752b.1746450157.git....@gentoo.org> +From: Sam James <[email protected]> +Date: Mon, 5 May 2025 14:02:25 +0100 +Subject: [PATCH 4/4] Revert "gimple: Merge slow and fast bit-test switch + lowering [PR117091]" + +This reverts commit 5274db0c9b8c0e2d2879b237eb2ab576543b6c37. +--- + gcc/tree-switch-conversion.cc | 107 ++++++++++++++++++++++++++++------ + 1 file changed, 90 insertions(+), 17 deletions(-) + +diff --git a/gcc/tree-switch-conversion.cc b/gcc/tree-switch-conversion.cc +index a70274b03372..39a8a893edde 100644 +--- a/gcc/tree-switch-conversion.cc ++++ b/gcc/tree-switch-conversion.cc +@@ -1773,38 +1773,92 @@ jump_table_cluster::is_beneficial (const vec<cluster *> &, + return end - start + 1 >= case_values_threshold (); + } + +-/* Find bit tests of given CLUSTERS, where all members of the vector +- are of type simple_cluster. MAX_C is the approx max number of cases per +- label. New clusters are returned. */ ++/* Find bit tests of given CLUSTERS, where all members of the vector are of ++ type simple_cluster. Use a fast algorithm that might not find the optimal ++ solution (minimal number of clusters on the output). New clusters are ++ returned. ++ ++ You should call find_bit_tests () instead of calling this function ++ directly. */ + + vec<cluster *> +-bit_test_cluster::find_bit_tests (vec<cluster *> &clusters, int max_c) ++bit_test_cluster::find_bit_tests_fast (vec<cluster *> &clusters) + { +- if (!is_enabled () || max_c == 1) +- return clusters.copy (); ++ unsigned l = clusters.length (); ++ vec<cluster *> output; ++ ++ output.create (l); ++ ++ /* Look at sliding BITS_PER_WORD sized windows in the switch value space ++ and determine if they are suitable for a bit test cluster. Worst case ++ this can examine every value BITS_PER_WORD-1 times. */ ++ unsigned k; ++ for (unsigned i = 0; i < l; i += k) ++ { ++ hash_set<basic_block> targets; ++ cluster *start_cluster = clusters[i]; ++ ++ /* Find the biggest k such that clusters i to i+k-1 can be turned into a ++ one big bit test cluster. */ ++ k = 0; ++ while (i + k < l) ++ { ++ cluster *end_cluster = clusters[i + k]; ++ ++ /* Does value range fit into the BITS_PER_WORD window? */ ++ HOST_WIDE_INT w = cluster::get_range (start_cluster->get_low (), ++ end_cluster->get_high ()); ++ if (w == 0 || w > BITS_PER_WORD) ++ break; ++ ++ /* Check for max # of targets. */ ++ if (targets.elements () == m_max_case_bit_tests ++ && !targets.contains (end_cluster->m_case_bb)) ++ break; ++ ++ targets.add (end_cluster->m_case_bb); ++ k++; ++ } ++ ++ if (is_beneficial (k, targets.elements ())) ++ { ++ output.safe_push (new bit_test_cluster (clusters, i, i + k - 1, ++ i == 0 && k == l)); ++ } ++ else ++ { ++ output.safe_push (clusters[i]); ++ /* ??? Might be able to skip more. */ ++ k = 1; ++ } ++ } + ++ return output; ++} ++ ++/* Find bit tests of given CLUSTERS, where all members of the vector ++ are of type simple_cluster. Use a slow (quadratic) algorithm that always ++ finds the optimal solution (minimal number of clusters on the output). New ++ clusters are returned. ++ ++ You should call find_bit_tests () instead of calling this function ++ directly. */ ++ ++vec<cluster *> ++bit_test_cluster::find_bit_tests_slow (vec<cluster *> &clusters) ++{ + unsigned l = clusters.length (); + auto_vec<min_cluster_item> min; + min.reserve (l + 1); + + min.quick_push (min_cluster_item (0, 0, 0)); + +- unsigned bits_in_word = GET_MODE_BITSIZE (word_mode); +- + 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)); + +- /* Since each cluster contains at least one case number and one bit test +- cluster can cover at most bits_in_word case numbers, we don't need to +- look farther than bits_in_word clusters back. */ +- unsigned j; +- if (i - 1 >= bits_in_word) +- j = i - 1 - bits_in_word; +- else +- j = 0; +- for (; j < i; j++) ++ for (unsigned j = 0; j < i; j++) + { + if (min[j].m_count + 1 < min[i].m_count + && can_be_handled (clusters, j, i - 1)) +@@ -1846,6 +1900,25 @@ bit_test_cluster::find_bit_tests (vec<cluster *> &clusters, int max_c) + return output; + } + ++/* Find bit tests of given CLUSTERS, where all members of the vector ++ are of type simple_cluster. MAX_C is the approx max number of cases per ++ label. New clusters are returned. */ ++ ++vec<cluster *> ++bit_test_cluster::find_bit_tests (vec<cluster *> &clusters, int max_c) ++{ ++ if (!is_enabled () || max_c == 1) ++ return clusters.copy (); ++ ++ unsigned l = clusters.length (); ++ ++ /* Note: l + 1 is the number of cases of the switch. */ ++ if (l + 1 > (unsigned) param_switch_lower_slow_alg_max_cases) ++ return find_bit_tests_fast (clusters); ++ else ++ return find_bit_tests_slow (clusters); ++} ++ + /* Return true when RANGE of case values with UNIQ labels + can build a bit test. */ + +-- +2.49.0 +
