simplify_switch_using_ranges has never been converted over properly to
use irange. It still uses get_legacy_range, and as a result, is very
limited in how it processes cases labels. In particular it is unable to
remove cases in the middle which are not possible to call.
This patch rewrites the routine to work in a similar way to how switches
are processed in the gimple-range-edge component. It starts with the
range of the switch operand, uses that as the initial default case, and
the walks the labels determining if the case is reachable at all via an
intersection with the index range.
If the result is UNDEFINED, then the case label is unreachable. If the
result is something smaller then it was originally, then the lower and
upper bounds are adjusted.
The range of the case is then removed from the default range, and we
move on to the next one.
When done, any case labels which are still in use (including the default
label) are built into a new vector and a new switch is constructed,
similar to the way it was handled before.
I had to adjust the testcase tree-ssa/ssa-dom-thread-7.c as the default
label is now removed in that test, and this changes the thread count.
aarch64 use to have a different threadcount, presumably all spawned via
the default case, but now produces the same result on my cross
compiler. I left the seperate comparison in the test case just in case
in the wild it still comes out different.
The testcase that is added shows a case in the middle of the switch
being removed that we couldn't remove before.
The resulting routine is fairly straightforward and removes a lot of
complexity, so it is pretty maintainable. Performance shows an
insignificant compile time increase across all of GCC.
The second patch in the set focuses on improvements resulting from
better utilizing the bitmask when it is present.
Have I missed anything tricky about switches?
Bootstraps on x86_64-pc-linux-gnu with no regressions. OK for trunk?
Andrew
From f3709725b4656a3b75334c89d14d0f1da40e4be5 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacl...@redhat.com>
Date: Wed, 28 May 2025 11:16:05 -0400
Subject: [PATCH] Simplify switches utilizing subranges.
Adjust simplify_switch_using_ranges to use irange rather than relying
on the older legacy_range mechaism.
PR tree-optimization/119039
gcc/
* vr-values.cc (simplify_using_ranges::legacy_fold_cond): Remove.
(simplify_using_ranges::simplify_switch_using_ranges): Adjust.
gcc/testsuite/
* gcc.dg/pr119039-1.c: New.
* gcc.dg/tree-ssa/ssa-dom-thread-7.c: Adjust thread counts.
---
gcc/testsuite/gcc.dg/pr119039-1.c | 32 ++
.../gcc.dg/tree-ssa/ssa-dom-thread-7.c | 4 +-
gcc/vr-values.cc | 281 +++++-------------
3 files changed, 106 insertions(+), 211 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/pr119039-1.c
diff --git a/gcc/testsuite/gcc.dg/pr119039-1.c b/gcc/testsuite/gcc.dg/pr119039-1.c
new file mode 100644
index 00000000000..5ca65638853
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr119039-1.c
@@ -0,0 +1,32 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-evrp" } */
+
+extern void foo (void);
+extern void bar (void);
+extern void baz (void);
+
+/* Tests the ability to remove cases that are subranges. */
+
+void
+test (int i)
+{
+ if (i < 0 || i > 45)
+ return;
+ if (i >= 7 && i <= 8)
+ return;
+
+ switch (i)
+ {
+ case 1:
+ bar ();
+ break;
+ case 7 ... 8:
+ foo ();
+ case 14:
+ baz ();
+ break;
+ default:
+ break;
+ }
+}
+/* { dg-final { scan-tree-dump-not "foo" "evrp" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c
index 59891f29132..1c2cfa4fa8d 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c
@@ -11,8 +11,8 @@
to change decisions in switch expansion which in turn can expose new
jump threading opportunities. Skip the later tests on aarch64. */
/* { dg-final { scan-tree-dump-not "Jumps threaded" "dom3" { target { ! aarch64*-*-* } } } } */
-/* { dg-final { scan-tree-dump "Jumps threaded: 10" "thread2" { target { ! aarch64*-*-* } } } } */
-/* { dg-final { scan-tree-dump "Jumps threaded: 17" "thread2" { target { aarch64*-*-* } } } } */
+/* { dg-final { scan-tree-dump "Jumps threaded: 8" "thread2" { target { ! aarch64*-*-* } } } } */
+/* { dg-final { scan-tree-dump "Jumps threaded: 8" "thread2" { target { aarch64*-*-* } } } } */
enum STATE {
S0=0,
diff --git a/gcc/vr-values.cc b/gcc/vr-values.cc
index 4c787593b95..799f1bfd91d 100644
--- a/gcc/vr-values.cc
+++ b/gcc/vr-values.cc
@@ -513,85 +513,6 @@ simplify_using_ranges::legacy_fold_cond (gcond *stmt, edge *taken_edge_p)
}
}
-/* Searches the case label vector VEC for the ranges of CASE_LABELs that are
- used in range VR. The indices are placed in MIN_IDX1, MAX_IDX, MIN_IDX2 and
- MAX_IDX2. If the ranges of CASE_LABELs are empty then MAX_IDX1 < MIN_IDX1.
- Returns true if the default label is not needed. */
-
-static bool
-find_case_label_ranges (gswitch *stmt, const irange *vr,
- size_t *min_idx1, size_t *max_idx1,
- size_t *min_idx2, size_t *max_idx2)
-{
- size_t i, j, k, l;
- unsigned int n = gimple_switch_num_labels (stmt);
- bool take_default;
- tree case_low, case_high;
- tree min, max;
- value_range_kind kind = get_legacy_range (*vr, min, max);
-
- gcc_checking_assert (!vr->varying_p () && !vr->undefined_p ());
-
- take_default = !find_case_label_range (stmt, min, max, &i, &j);
-
- /* Set second range to empty. */
- *min_idx2 = 1;
- *max_idx2 = 0;
-
- if (kind == VR_RANGE)
- {
- *min_idx1 = i;
- *max_idx1 = j;
- return !take_default;
- }
-
- /* Set first range to all case labels. */
- *min_idx1 = 1;
- *max_idx1 = n - 1;
-
- if (i > j)
- return false;
-
- /* Make sure all the values of case labels [i , j] are contained in
- range [MIN, MAX]. */
- case_low = CASE_LOW (gimple_switch_label (stmt, i));
- case_high = CASE_HIGH (gimple_switch_label (stmt, j));
- if (tree_int_cst_compare (case_low, min) < 0)
- i += 1;
- if (case_high != NULL_TREE
- && tree_int_cst_compare (max, case_high) < 0)
- j -= 1;
-
- if (i > j)
- return false;
-
- /* If the range spans case labels [i, j], the corresponding anti-range spans
- the labels [1, i - 1] and [j + 1, n - 1]. */
- k = j + 1;
- l = n - 1;
- if (k > l)
- {
- k = 1;
- l = 0;
- }
-
- j = i - 1;
- i = 1;
- if (i > j)
- {
- i = k;
- j = l;
- k = 1;
- l = 0;
- }
-
- *min_idx1 = i;
- *max_idx1 = j;
- *min_idx2 = k;
- *max_idx2 = l;
- return false;
-}
-
/* Simplify boolean operations if the source is known
to be already a boolean. */
bool
@@ -1374,157 +1295,99 @@ bool
simplify_using_ranges::simplify_switch_using_ranges (gswitch *stmt)
{
tree op = gimple_switch_index (stmt);
- int_range_max vr;
- bool take_default;
+ tree type = TREE_TYPE (op);
+ int_range_max op_range (type);
+ int_range_max default_range (type);
+ auto_vec<unsigned> cases;
+ cases.truncate (0);
edge e;
- edge_iterator ei;
- size_t i = 0, j = 0, n, n2;
- tree vec2;
switch_update su;
- size_t k = 1, l = 0;
- if (TREE_CODE (op) == SSA_NAME)
- {
- if (!query->range_of_expr (vr, op, stmt)
- || vr.varying_p () || vr.undefined_p ())
- return false;
-
- /* Find case label for min/max of the value range. */
- take_default = !find_case_label_ranges (stmt, &vr, &i, &j, &k, &l);
- }
- else if (TREE_CODE (op) == INTEGER_CST)
- {
- take_default = !find_case_label_index (stmt, 1, op, &i);
- if (take_default)
- {
- i = 1;
- j = 0;
- }
- else
- {
- j = i;
- }
- }
- else
+ // Abort if we don't have a useful range for the switch index.
+ if (!query->range_of_expr (op_range, op, stmt)
+ || op_range.varying_p () || op_range.undefined_p ())
return false;
- n = gimple_switch_num_labels (stmt);
+ // Default range starts with full known range of op.
+ default_range = op_range;
+ edge default_edge = gimple_switch_default_edge (cfun, stmt);
- /* We can truncate the case label ranges that partially overlap with OP's
- value range. */
- size_t min_idx = 1, max_idx = 0;
- tree min, max;
- value_range_kind kind = get_legacy_range (vr, min, max);
- if (!vr.undefined_p ())
- find_case_label_range (stmt, min, max, &min_idx, &max_idx);
- if (min_idx <= max_idx)
+ unsigned x, lim = gimple_switch_num_labels (stmt);
+ for (x = 1; x < lim; x++)
{
- tree min_label = gimple_switch_label (stmt, min_idx);
- tree max_label = gimple_switch_label (stmt, max_idx);
+ e = gimple_switch_edge (cfun, stmt, x);
+ tree label = gimple_switch_label (stmt, x);
+
+ // If this edge is the same as the default edge, do nothing else.
+ if (e == default_edge)
+ continue;
+ // Ada sometimes has mismatched labels and index. Just bail.
+ if (TREE_TYPE (CASE_LOW (label)) != type)
+ return false;
- /* Avoid changing the type of the case labels when truncating. */
- tree case_label_type = TREE_TYPE (CASE_LOW (min_label));
- tree vr_min = fold_convert (case_label_type, min);
- tree vr_max = fold_convert (case_label_type, max);
+ wide_int low = wi::to_wide (CASE_LOW (label));
+ wide_int high;
+ // Singleton cases have no CASE_HIGH.
+ tree tree_high = CASE_HIGH (label);
+ if (tree_high)
+ high = wi::to_wide (tree_high);
+ else
+ high = low;
- if (kind == VR_RANGE)
- {
- /* If OP's value range is [2,8] and the low label range is
- 0 ... 3, truncate the label's range to 2 .. 3. */
- if (tree_int_cst_compare (CASE_LOW (min_label), vr_min) < 0
- && CASE_HIGH (min_label) != NULL_TREE
- && tree_int_cst_compare (CASE_HIGH (min_label), vr_min) >= 0)
- CASE_LOW (min_label) = vr_min;
-
- /* If OP's value range is [2,8] and the high label range is
- 7 ... 10, truncate the label's range to 7 .. 8. */
- if (tree_int_cst_compare (CASE_LOW (max_label), vr_max) <= 0
- && CASE_HIGH (max_label) != NULL_TREE
- && tree_int_cst_compare (CASE_HIGH (max_label), vr_max) > 0)
- CASE_HIGH (max_label) = vr_max;
- }
- else if (kind == VR_ANTI_RANGE)
+ // If the case range is fully contained in op_range, leave the
+ // case as it is, otherwise adjust the labels.
+ int_range_max case_range (type, low, high);
+ if (case_range.intersect (op_range))
{
- tree one_cst = build_one_cst (case_label_type);
-
- if (min_label == max_label)
- {
- /* If OP's value range is ~[7,8] and the label's range is
- 7 ... 10, truncate the label's range to 9 ... 10. */
- if (tree_int_cst_compare (CASE_LOW (min_label), vr_min) == 0
- && CASE_HIGH (min_label) != NULL_TREE
- && tree_int_cst_compare (CASE_HIGH (min_label), vr_max) > 0)
- CASE_LOW (min_label)
- = int_const_binop (PLUS_EXPR, vr_max, one_cst);
-
- /* If OP's value range is ~[7,8] and the label's range is
- 5 ... 8, truncate the label's range to 5 ... 6. */
- if (tree_int_cst_compare (CASE_LOW (min_label), vr_min) < 0
- && CASE_HIGH (min_label) != NULL_TREE
- && tree_int_cst_compare (CASE_HIGH (min_label), vr_max) == 0)
- CASE_HIGH (min_label)
- = int_const_binop (MINUS_EXPR, vr_min, one_cst);
- }
+ // If none of the label is in op_range, skip this label.
+ if (case_range.undefined_p ())
+ continue;
+
+ // Part of the label is in op_range, but not all of it. CASE_RANGE
+ // contains the part that is. Adjust the case range to
+ // the new min/max.
+ if (case_range.lower_bound () != low)
+ CASE_LOW (label) = wide_int_to_tree (type,
+ case_range.lower_bound ());
+ if (case_range.singleton_p ())
+ CASE_HIGH (label) = NULL_TREE;
else
- {
- /* If OP's value range is ~[2,8] and the low label range is
- 0 ... 3, truncate the label's range to 0 ... 1. */
- if (tree_int_cst_compare (CASE_LOW (min_label), vr_min) < 0
- && CASE_HIGH (min_label) != NULL_TREE
- && tree_int_cst_compare (CASE_HIGH (min_label), vr_min) >= 0)
- CASE_HIGH (min_label)
- = int_const_binop (MINUS_EXPR, vr_min, one_cst);
-
- /* If OP's value range is ~[2,8] and the high label range is
- 7 ... 10, truncate the label's range to 9 ... 10. */
- if (tree_int_cst_compare (CASE_LOW (max_label), vr_max) <= 0
- && CASE_HIGH (max_label) != NULL_TREE
- && tree_int_cst_compare (CASE_HIGH (max_label), vr_max) > 0)
- CASE_LOW (max_label)
- = int_const_binop (PLUS_EXPR, vr_max, one_cst);
- }
+ if (case_range.upper_bound () != high)
+ CASE_HIGH (label) = wide_int_to_tree (type,
+ case_range.upper_bound ());
}
-
- /* Canonicalize singleton case ranges. */
- if (tree_int_cst_equal (CASE_LOW (min_label), CASE_HIGH (min_label)))
- CASE_HIGH (min_label) = NULL_TREE;
- if (tree_int_cst_equal (CASE_LOW (max_label), CASE_HIGH (max_label)))
- CASE_HIGH (max_label) = NULL_TREE;
+ // Add case label to the keep list.
+ cases.safe_push (x);
+ // Remove case_range from needing to be handled by the default.
+ case_range.invert ();
+ default_range.intersect (case_range);
}
- /* We can also eliminate case labels that lie completely outside OP's value
- range. */
-
- /* Bail out if this is just all edges taken. */
- if (i == 1
- && j == n - 1
- && take_default)
+ // An undefined DEFAULT range means the current default case is not needed.
+ unsigned idx = default_range.undefined_p () ? 0 : 1;
+ unsigned vec_size = cases.length () + idx;
+ if (vec_size == lim)
return false;
- /* Build a new vector of taken case labels. */
- vec2 = make_tree_vec (j - i + 1 + l - k + 1 + (int)take_default);
- n2 = 0;
-
- /* Add the default edge, if necessary. */
- if (take_default)
- TREE_VEC_ELT (vec2, n2++) = gimple_switch_default_label (stmt);
-
- for (; i <= j; ++i, ++n2)
- TREE_VEC_ELT (vec2, n2) = gimple_switch_label (stmt, i);
-
- for (; k <= l; ++k, ++n2)
- TREE_VEC_ELT (vec2, n2) = gimple_switch_label (stmt, k);
+ tree vec2 = make_tree_vec (vec_size);
+ // Add default label if there is one.
+ if (idx)
+ {
+ TREE_VEC_ELT (vec2, 0) = gimple_switch_default_label (stmt);
+ e = gimple_switch_edge (cfun, stmt, 0);
+ e->aux = (void *)-1;
+ }
- /* Mark needed edges. */
- for (i = 0; i < n2; ++i)
+ for (x = 0; x < cases.length (); x++)
{
- e = find_edge (gimple_bb (stmt),
- label_to_block (cfun,
- CASE_LABEL (TREE_VEC_ELT (vec2, i))));
- e->aux = (void *)-1;
+ unsigned swi = cases[x];
+ TREE_VEC_ELT (vec2, idx++) = gimple_switch_label (stmt, swi);
+ e = gimple_switch_edge (cfun, stmt, swi);
+ e->aux = (void *)-1;
}
/* Queue not needed edges for later removal. */
+ edge_iterator ei;
FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs)
{
if (e->aux == (void *)-1)
--
2.45.0
