https://gcc.gnu.org/g:220e0570f0861c1fd531ef0b309692deb2509a67
commit r15-4761-g220e0570f0861c1fd531ef0b309692deb2509a67
Author: Andi Kleen <a...@gcc.gnu.org>
Date: Tue Oct 29 16:41:57 2024 -0700
Revert "Simplify switch bit test clustering algorithm"
This reverts commit 3d06e9c3e07e13eab715e19dafbcfc1a0b7e43d6.
Diff:
---
gcc/testsuite/gcc.dg/pr21643.c | 2 +-
gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-6.c | 2 +-
gcc/testsuite/gcc.dg/tree-ssa/switch-1.c | 2 +-
gcc/testsuite/gcc.target/aarch64/pr99988.c | 2 +-
gcc/tree-switch-conversion.cc | 79 ++++++++++++--------------
5 files changed, 40 insertions(+), 47 deletions(-)
diff --git a/gcc/testsuite/gcc.dg/pr21643.c b/gcc/testsuite/gcc.dg/pr21643.c
index a722a83ecb59..42517b5af1e5 100644
--- a/gcc/testsuite/gcc.dg/pr21643.c
+++ b/gcc/testsuite/gcc.dg/pr21643.c
@@ -1,6 +1,6 @@
/* PR tree-optimization/21643 */
/* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-reassoc1-details --param
logical-op-non-short-circuit=1 -fno-bit-tests" } */
+/* { dg-options "-O2 -fdump-tree-reassoc1-details --param
logical-op-non-short-circuit=1" } */
int
f1 (unsigned char c)
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-6.c
b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-6.c
index 657af770e438..b1640673eae1 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-6.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-6.c
@@ -39,4 +39,4 @@ int main(int argc, char **argv)
return 0;
}
-/* { dg-final { scan-tree-dump "Condition chain" "iftoswitch" } } */
+/* { dg-final { scan-tree-dump-not "Condition chain" "iftoswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/switch-1.c
b/gcc/testsuite/gcc.dg/tree-ssa/switch-1.c
index f1654aba6d99..6f70c9de0c19 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/switch-1.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/switch-1.c
@@ -107,4 +107,4 @@ int foo5 (int x)
}
}
-/* { dg-final { scan-tree-dump ";; GIMPLE switch case clusters: BT:10-62
600-700 BT:1000-1021 111111" "switchlower1" } } */
+/* { dg-final { scan-tree-dump ";; GIMPLE switch case clusters: BT:10-62
600-700 JT:1000-1021 111111" "switchlower1" } } */
diff --git a/gcc/testsuite/gcc.target/aarch64/pr99988.c
b/gcc/testsuite/gcc.target/aarch64/pr99988.c
index c09ce67c0fa9..7cca49629446 100644
--- a/gcc/testsuite/gcc.target/aarch64/pr99988.c
+++ b/gcc/testsuite/gcc.target/aarch64/pr99988.c
@@ -1,5 +1,5 @@
/* { dg-do compile { target lp64 } } */
-/* { dg-options "-O2 -mbranch-protection=standard -fno-bit-tests" } */
+/* { dg-options "-O2 -mbranch-protection=standard" } */
/* { dg-final { scan-assembler-times {bti j} 13 } } */
int a;
int c();
diff --git a/gcc/tree-switch-conversion.cc b/gcc/tree-switch-conversion.cc
index 9b4ddcd0146d..852419b2f4be 100644
--- a/gcc/tree-switch-conversion.cc
+++ b/gcc/tree-switch-conversion.cc
@@ -1783,62 +1783,55 @@ bit_test_cluster::find_bit_tests (vec<cluster *>
&clusters, int max_c)
return clusters.copy ();
unsigned l = clusters.length ();
- vec<cluster *> output;
+ auto_vec<min_cluster_item> min;
+ min.reserve (l + 1);
- output.create (l);
+ min.quick_push (min_cluster_item (0, 0, 0));
- /* 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 end;
- for (unsigned i = 0; i < l; i += end)
+ for (unsigned i = 1; i <= l; i++)
{
- HOST_WIDE_INT values = 0;
- hash_set<basic_block> targets;
- cluster *start_cluster = clusters[i];
+ /* Set minimal # of clusters with i-th item to infinite. */
+ min.quick_push (min_cluster_item (INT_MAX, INT_MAX, INT_MAX));
- end = 0;
- while (i + end < l)
+ for (unsigned j = 0; j < i; j++)
{
- cluster *end_cluster = clusters[i + end];
-
- /* 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;
-
- /* Compute # of values tested for new case. */
- HOST_WIDE_INT r = 1;
- if (!end_cluster->is_single_value_p ())
- r = cluster::get_range (end_cluster->get_low (),
- end_cluster->get_high ());
- if (r == 0)
- 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);
- values += r;
- end++;
+ 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);
}
- if (is_beneficial (values, targets.elements ()))
+ gcc_checking_assert (min[i].m_count != INT_MAX);
+ }
+
+ /* No result. */
+ if (min[l].m_count == l)
+ return clusters.copy ();
+
+ vec<cluster *> output;
+ output.create (4);
+
+ /* Find and build the clusters. */
+ for (unsigned end = l;;)
+ {
+ int start = min[end].m_start;
+
+ if (is_beneficial (clusters, start, end - 1))
{
- output.safe_push (new bit_test_cluster (clusters, i, i + end - 1,
- i == 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]);
- /* ??? Might be able to skip more. */
- end = 1;
- }
+
+ end = start;
+
+ if (start <= 0)
+ break;
}
+ output.reverse ();
return output;
}
