https://gcc.gnu.org/g:2b3533cd871f62923e7a4f06a826f37bf0f35c5c
commit r15-2416-g2b3533cd871f62923e7a4f06a826f37bf0f35c5c
Author: Filip Kastl <fka...@suse.cz>
Date: Tue Jul 30 18:40:29 2024 +0200
gimple ssa: Teach switch conversion to optimize powers of 2 switches
Sometimes a switch has case numbers that are powers of 2. Switch
conversion usually isn't able to optimize these switches. This patch
adds "exponential index transformation" to switch conversion. After
switch conversion applies this transformation on the switch the index
variable of the switch becomes the exponent instead of the whole value.
For example:
switch (i)
{
case (1 << 0): return 0;
case (1 << 1): return 1;
case (1 << 2): return 2;
...
case (1 << 30): return 30;
default: return 31;
}
gets transformed roughly into
switch (log2(i))
{
case 0: return 0;
case 1: return 1;
case 2: return 2;
...
case 30: return 30;
default: return 31;
}
This enables switch conversion to further optimize the switch.
This patch only enables this transformation if there are optabs for FFS
so that the base 2 logarithm can be computed efficiently at runtime.
gcc/ChangeLog:
* tree-switch-conversion.cc (can_log2): New static function to
check if gen_log2 can be used on current target.
(gen_log2): New static function to generate efficient GIMPLE
code for taking an exact base 2 log.
(gen_pow2p): New static function to generate efficient GIMPLE
code for checking if a value is a power of 2.
(switch_conversion::switch_conversion): Track if the
transformation happened.
(switch_conversion::is_exp_index_transform_viable): New function
to decide whether the transformation should be applied.
(switch_conversion::exp_index_transform): New function to
execute the transformation.
(switch_conversion::gen_inbound_check): Don't remove the default
BB if the transformation happened.
(switch_conversion::expand): Execute the transform if it is
viable. Skip the "sufficiently small case range" test if the
transformation is going to be executed.
* tree-switch-conversion.h: Add is_exp_index_transform_viable
and exp_index_transform.
gcc/testsuite/ChangeLog:
* gcc.dg/tree-ssa/switch-3.c: Disable switch conversion.
* gcc.target/i386/switch-exp-transform-1.c: New test.
* gcc.target/i386/switch-exp-transform-2.c: New test.
* gcc.target/i386/switch-exp-transform-3.c: New test.
Signed-off-by: Filip Kastl <fka...@suse.cz>
Diff:
---
gcc/testsuite/gcc.dg/tree-ssa/switch-3.c | 2 +-
.../gcc.target/i386/switch-exp-transform-1.c | 32 ++
.../gcc.target/i386/switch-exp-transform-2.c | 35 +++
.../gcc.target/i386/switch-exp-transform-3.c | 148 ++++++++++
gcc/tree-switch-conversion.cc | 326 ++++++++++++++++++++-
gcc/tree-switch-conversion.h | 18 ++
6 files changed, 555 insertions(+), 6 deletions(-)
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/switch-3.c
b/gcc/testsuite/gcc.dg/tree-ssa/switch-3.c
index 44981e1d1861..83aae3843e91 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/switch-3.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/switch-3.c
@@ -1,4 +1,4 @@
-/* { dg-options "-O2 -fdump-tree-switchlower1" } */
+/* { dg-options "-O2 -fdump-tree-switchlower1 -fdisable-tree-switchconv" } */
int cipher_to_alg(int cipher)
{
diff --git a/gcc/testsuite/gcc.target/i386/switch-exp-transform-1.c
b/gcc/testsuite/gcc.target/i386/switch-exp-transform-1.c
new file mode 100644
index 000000000000..53d31460ba37
--- /dev/null
+++ b/gcc/testsuite/gcc.target/i386/switch-exp-transform-1.c
@@ -0,0 +1,32 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-switchconv -mpopcnt -mbmi" } */
+
+/* Checks that exponential index transform enables switch conversion to convert
+ this switch into an array lookup. Also checks that the "index variable is a
+ power of two" check has been generated. */
+
+int foo(unsigned bar)
+{
+ switch (bar)
+ {
+ case (1 << 0):
+ return 1;
+ case (1 << 1):
+ return 2;
+ case (1 << 2):
+ return 3;
+ case (1 << 3):
+ return 4;
+ case (1 << 4):
+ return 8;
+ case (1 << 5):
+ return 13;
+ case (1 << 6):
+ return 21;
+ default:
+ return 0;
+ }
+}
+
+/* { dg-final { scan-tree-dump "CSWTCH" "switchconv" } } */
+/* { dg-final { scan-tree-dump "POPCOUNT" "switchconv" } } */
diff --git a/gcc/testsuite/gcc.target/i386/switch-exp-transform-2.c
b/gcc/testsuite/gcc.target/i386/switch-exp-transform-2.c
new file mode 100644
index 000000000000..f1a9a2d1ee94
--- /dev/null
+++ b/gcc/testsuite/gcc.target/i386/switch-exp-transform-2.c
@@ -0,0 +1,35 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-switchconv -mbmi" } */
+
+/* Checks that when exponential index transform is viable but switch conversion
+ decides that the switch cannot be converted, the exponential index transform
+ is not done. */
+
+int a;
+
+int foo(unsigned bar)
+{
+ switch (bar)
+ {
+ case (1 << 0):
+ return 0;
+ case (1 << 1):
+ return 1;
+ case (1 << 2):
+ return 2;
+ case (1 << 3):
+ return 3;
+ case (1 << 4):
+ return 4;
+ case (1 << 5):
+ a = 3;
+ return 5;
+ case (1 << 6):
+ return 6;
+ default:
+ return 0;
+ }
+}
+
+/* { dg-final { scan-tree-dump "Exponential index transform viable"
"switchconv" } } */
+/* { dg-final { scan-tree-dump-not "Applying exponential index transform"
"switchconv" } } */
diff --git a/gcc/testsuite/gcc.target/i386/switch-exp-transform-3.c
b/gcc/testsuite/gcc.target/i386/switch-exp-transform-3.c
new file mode 100644
index 000000000000..c8fae70692e5
--- /dev/null
+++ b/gcc/testsuite/gcc.target/i386/switch-exp-transform-3.c
@@ -0,0 +1,148 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-switchconv -mbmi" } */
+
+/* Checks that the exponential index transformation is done for all these types
+ of the index variable:
+ - (unsigned) int
+ - (unsigned) long
+ - (unsigned) long long */
+
+int unopt_int(int bit_position)
+{
+ switch (bit_position)
+ {
+ case (1 << 0):
+ return 0;
+ case (1 << 1):
+ return 1;
+ case (1 << 2):
+ return 2;
+ case (1 << 3):
+ return 3;
+ case (1 << 4):
+ return 4;
+ case (1 << 5):
+ return 5;
+ case (1 << 6):
+ return 6;
+ default:
+ return 0;
+ }
+}
+
+int unopt_unsigned_int(unsigned int bit_position)
+{
+ switch (bit_position)
+ {
+ case (1 << 0):
+ return 0;
+ case (1 << 1):
+ return 1;
+ case (1 << 2):
+ return 2;
+ case (1 << 3):
+ return 3;
+ case (1 << 4):
+ return 4;
+ case (1 << 5):
+ return 5;
+ case (1 << 6):
+ return 6;
+ default:
+ return 0;
+ }
+}
+
+int unopt_long(long bit_position)
+{
+ switch (bit_position)
+ {
+ case (1 << 0):
+ return 0;
+ case (1 << 1):
+ return 1;
+ case (1 << 2):
+ return 2;
+ case (1 << 3):
+ return 3;
+ case (1 << 4):
+ return 4;
+ case (1 << 5):
+ return 5;
+ case (1 << 6):
+ return 6;
+ default:
+ return 0;
+ }
+}
+
+int unopt_unsigned_long(unsigned long bit_position)
+{
+ switch (bit_position)
+ {
+ case (1 << 0):
+ return 0;
+ case (1 << 1):
+ return 1;
+ case (1 << 2):
+ return 2;
+ case (1 << 3):
+ return 3;
+ case (1 << 4):
+ return 4;
+ case (1 << 5):
+ return 5;
+ case (1 << 6):
+ return 6;
+ default:
+ return 0;
+ }
+}
+
+int unopt_long_long(long long bit_position)
+{
+ switch (bit_position)
+ {
+ case (1 << 0):
+ return 0;
+ case (1 << 1):
+ return 1;
+ case (1 << 2):
+ return 2;
+ case (1 << 3):
+ return 3;
+ case (1 << 4):
+ return 4;
+ case (1 << 5):
+ return 5;
+ case (1 << 6):
+ return 6;
+ default:
+ return 0;
+ }
+}
+
+int unopt_unsigned_long_long(unsigned long long bit_position)
+{
+ switch (bit_position)
+ {
+ case (1 << 0):
+ return 0;
+ case (1 << 1):
+ return 1;
+ case (1 << 2):
+ return 2;
+ case (1 << 3):
+ return 3;
+ case (1 << 4):
+ return 4;
+ case (1 << 5):
+ return 5;
+ case (1 << 6):
+ return 6;
+ default:
+ return 0;
+ }
+}
+
+/* { dg-final { scan-tree-dump-times "Applying exponential index transform" 6
"switchconv" } } */
diff --git a/gcc/tree-switch-conversion.cc b/gcc/tree-switch-conversion.cc
index 64629122ec63..4b11c8d25f44 100644
--- a/gcc/tree-switch-conversion.cc
+++ b/gcc/tree-switch-conversion.cc
@@ -52,6 +52,8 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston,
MA
#include "omp-general.h"
#include "gimple-range.h"
#include "tree-cfgcleanup.h"
+#include "hwint.h"
+#include "internal-fn.h"
/* ??? For lang_hooks.types.type_for_mode, but is there a word_mode
type in the GIMPLE type system that is language-independent? */
@@ -61,12 +63,73 @@ Software Foundation, 51 Franklin Street, Fifth Floor,
Boston, MA
using namespace tree_switch_conversion;
+/* Does the target have optabs needed to efficiently compute exact base two
+ logarithm of a value with type TYPE?
+
+ See gen_log2. */
+
+static bool
+can_log2 (tree type, optimization_type opt_type)
+{
+ /* Check if target supports FFS. */
+ return direct_internal_fn_supported_p (IFN_FFS, type, opt_type);
+}
+
+/* Assume that OP is a power of two. Build a sequence of gimple statements
+ efficiently computing the base two logarithm of OP using special optabs.
+ Return the ssa name represeting the result of the logarithm through RESULT.
+
+ Should only be used if target supports the needed optabs. See can_log2. */
+
+static gimple_seq
+gen_log2 (tree op, location_t loc, tree *result)
+{
+ tree type = TREE_TYPE (op);
+ gimple_seq stmts = NULL;
+ gimple_stmt_iterator gsi = gsi_last (stmts);
+ tree tmp1 = gimple_build (&gsi, false, GSI_NEW_STMT, loc, IFN_FFS, type, op);
+ tree tmp2 = gimple_build (&gsi, false, GSI_NEW_STMT, loc, MINUS_EXPR, type,
+ tmp1, build_one_cst (type));
+ *result = tmp2;
+ return stmts;
+}
+
+/* Build a sequence of gimple statements checking that OP is a power of 2. Use
+ special optabs if target supports them. Return the result as a
+ boolen_type_node ssa name through RESULT. */
+
+static gimple_seq
+gen_pow2p (tree op, location_t loc, optimization_type opt_type, tree *result)
+{
+ tree type = TREE_TYPE (op);
+ gimple_seq stmts = NULL;
+ gimple_stmt_iterator gsi = gsi_last (stmts);
+ if (direct_internal_fn_supported_p (IFN_POPCOUNT, type, opt_type))
+ {
+ tree tmp = gimple_build (&gsi, false, GSI_NEW_STMT, loc, IFN_POPCOUNT,
+ type, op);
+ *result = gimple_build (&gsi, false, GSI_NEW_STMT, loc, EQ_EXPR,
+ boolean_type_node, tmp, build_one_cst (type));
+ }
+ else
+ {
+ tree tmp1 = gimple_build (&gsi, false, GSI_NEW_STMT, loc, NEGATE_EXPR,
+ type, op);
+ tree tmp2 = gimple_build (&gsi, false, GSI_NEW_STMT, loc, BIT_AND_EXPR,
+ type, op, tmp1);
+ *result = gimple_build (&gsi, false, GSI_NEW_STMT, loc, EQ_EXPR,
+ boolean_type_node, tmp2, op);
+ }
+ return stmts;
+}
+
/* Constructor. */
switch_conversion::switch_conversion (): m_final_bb (NULL),
m_constructors (NULL), m_default_values (NULL),
m_arr_ref_first (NULL), m_arr_ref_last (NULL),
- m_reason (NULL), m_default_case_nonstandard (false), m_cfg_altered (false)
+ m_reason (NULL), m_default_case_nonstandard (false), m_cfg_altered (false),
+ m_exp_index_transform_applied (false)
{
}
@@ -202,6 +265,244 @@ switch_conversion::collect (gswitch *swtch)
}
}
+/* Check that the "exponential index transform" can be applied to this switch.
+
+ See comment of the exp_index_transform function for details about this
+ transformation.
+
+ We want:
+ - This form of the switch is more efficient
+ - Cases are powers of 2
+
+ Expects that SWTCH has at least one case. */
+
+bool
+switch_conversion::is_exp_index_transform_viable (gswitch *swtch)
+{
+ tree index = gimple_switch_index (swtch);
+ tree index_type = TREE_TYPE (index);
+ basic_block swtch_bb = gimple_bb (swtch);
+ unsigned num_labels = gimple_switch_num_labels (swtch);
+
+ optimization_type opt_type = bb_optimization_type (swtch_bb);
+ if (!can_log2 (index_type, opt_type))
+ return false;
+
+ /* Check that each case label corresponds only to one value
+ (no case 1..3). */
+ unsigned i;
+ for (i = 1; i < num_labels; i++)
+ {
+ tree label = gimple_switch_label (swtch, i);
+ if (CASE_HIGH (label))
+ return false;
+ }
+
+ /* Check that each label is nonnegative and a power of 2. */
+ for (i = 1; i < num_labels; i++)
+ {
+ tree label = gimple_switch_label (swtch, i);
+ wide_int label_wi = wi::to_wide (CASE_LOW (label));
+ if (!wi::ge_p (label_wi, 0, TYPE_SIGN (index_type)))
+ return false;
+ if (wi::exact_log2 (label_wi) == -1)
+ return false;
+ }
+
+ if (dump_file)
+ fprintf (dump_file, "Exponential index transform viable\n");
+
+ return true;
+}
+
+/* Perform the "exponential index transform".
+
+ Assume that cases of SWTCH are powers of 2. The transformation replaces the
+ cases by their exponents (2^k -> k). It also inserts a statement that
+ computes the exponent of the original index variable (basically taking the
+ logarithm) and then sets the result as the new index variable.
+
+ The transformation also inserts a conditional statement checking that the
+ incoming original index variable is a power of 2 with the false edge leading
+ to the default case.
+
+ The exponential index transform shrinks the range of case numbers which
+ helps switch conversion convert switches it otherwise could not.
+
+ Consider for example:
+
+ switch (i)
+ {
+ case (1 << 0): return 0;
+ case (1 << 1): return 1;
+ case (1 << 2): return 2;
+ ...
+ case (1 << 30): return 30;
+ default: return 31;
+ }
+
+ First, exponential index transform gets applied. Since each case becomes
+ case x: return x;, the rest of switch conversion is then able to get rid of
+ the switch statement.
+
+ if (i is power of 2)
+ return log2 (i);
+ else
+ return 31;
+
+ */
+
+void
+switch_conversion::exp_index_transform (gswitch *swtch)
+{
+ if (dump_file)
+ fprintf (dump_file, "Applying exponential index transform\n");
+
+ tree index = gimple_switch_index (swtch);
+ tree index_type = TREE_TYPE (index);
+ basic_block swtch_bb = gimple_bb (swtch);
+ unsigned num_labels = gimple_switch_num_labels (swtch);
+
+ /* Insert a cond stmt that checks if the index variable is a power of 2. */
+ gimple_stmt_iterator gsi = gsi_for_stmt (swtch);
+ gsi_prev (&gsi);
+ gimple *foo = gsi_stmt (gsi);
+ edge new_edge1 = split_block (swtch_bb, foo);
+
+ swtch_bb = new_edge1->dest;
+ basic_block cond_bb = new_edge1->src;
+ new_edge1->flags |= EDGE_TRUE_VALUE;
+ new_edge1->flags &= ~EDGE_FALLTHRU;
+ new_edge1->probability = profile_probability::even ();
+
+ basic_block default_bb = gimple_switch_default_bb (cfun, swtch);
+ edge new_edge2 = make_edge (cond_bb, default_bb, EDGE_FALSE_VALUE);
+ new_edge2->probability = profile_probability::even ();
+
+ tree tmp;
+ optimization_type opt_type = bb_optimization_type (cond_bb);
+ gimple_seq stmts = gen_pow2p (index, UNKNOWN_LOCATION, opt_type, &tmp);
+ gsi = gsi_last_bb (cond_bb);
+ gsi_insert_seq_after (&gsi, stmts, GSI_LAST_NEW_STMT);
+ gcond *stmt_cond = gimple_build_cond (NE_EXPR, tmp, boolean_false_node,
+ NULL, NULL);
+ gsi_insert_after (&gsi, stmt_cond, GSI_NEW_STMT);
+
+ /* We just added an edge going to default bb so fix PHI nodes in that bb:
+ For each PHI add new PHI arg. It will be the same arg as when comming to
+ the default bb from the switch bb. */
+ edge default_edge = find_edge (swtch_bb, default_bb);
+ for (gphi_iterator gsi = gsi_start_phis (default_bb);
+ !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gphi *phi = gsi.phi ();
+ tree arg = PHI_ARG_DEF_FROM_EDGE (phi, default_edge);
+ location_t loc = gimple_phi_arg_location_from_edge (phi, default_edge);
+ add_phi_arg (phi, arg, new_edge2, loc);
+ }
+
+ /* Insert a sequence of stmts that takes the log of the index variable. */
+ stmts = gen_log2 (index, UNKNOWN_LOCATION, &tmp);
+ gsi = gsi_after_labels (swtch_bb);
+ gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
+
+ /* Use the result of the logarithm as the new index variable. */
+ gimple_switch_set_index (swtch, tmp);
+ update_stmt (swtch);
+
+ /* Replace each case number with its logarithm. */
+ unsigned i;
+ for (i = 1; i < num_labels; i++)
+ {
+ tree label = gimple_switch_label (swtch, i);
+ CASE_LOW (label) = build_int_cst (index_type,
+ tree_log2 (CASE_LOW (label)));
+ }
+
+ /* Fix the dominator tree, if it is available. */
+ if (dom_info_available_p (CDI_DOMINATORS))
+ {
+ /* Analysis of how dominators should look after we add the edge E going
+ from the cond block to the default block.
+
+ 1 For the blocks between the switch block and the final block
+ (excluding the final block itself): They had the switch block as
+ their immediate dominator. That shouldn't change.
+
+ 2 The final block may now have the switch block or the cond block as
+ its immediate dominator. There's no easy way of knowing (consider
+ two cases where in both m_default_case_nonstandard = true, in one a
+ path through default intersects the final block and in one all paths
+ through default avoid the final block but intersect a successor of the
+ final block).
+
+ 3 Other blocks that had the switch block as their immediate dominator
+ should now have the cond block as their immediate dominator.
+
+ 4 Immediate dominators of the rest of the blocks shouldn't change.
+
+ Reasoning for 3 and 4:
+
+ We'll only consider blocks that do not fall into 1 or 2.
+
+ Consider a block X whose original imm dom was the switch block. All
+ paths to X must also intersect the cond block since it's the only
+ pred of the switch block. The final block doesn't dominate X so at
+ least one path P must lead through the default block. Let P' be P but
+ instead of going through the switch block, take E. The switch block
+ doesn't dominate X so its imm dom must now be the cond block.
+
+ Consider a block X whose original imm dom was Y != the switch block.
+ We only added an edge so all original paths to X are still present.
+ So X gained no new dominators. Observe that Y still dominates X.
+ There would have to be a path that avoids Y otherwise. But any block
+ we can avoid now except for the switch block we were able to avoid
+ before adding E. */
+
+ redirect_immediate_dominators (CDI_DOMINATORS, swtch_bb, cond_bb);
+
+ edge e;
+ edge_iterator ei;
+ FOR_EACH_EDGE (e, ei, swtch_bb->succs)
+ {
+ basic_block bb = e->dest;
+ if (bb == m_final_bb || bb == default_bb)
+ continue;
+ set_immediate_dominator (CDI_DOMINATORS, bb, swtch_bb);
+ }
+
+ vec<basic_block> v;
+ v.create (1);
+ v.quick_push (m_final_bb);
+ iterate_fix_dominators (CDI_DOMINATORS, v, true);
+ }
+
+ /* Update information about the switch statement. */
+ tree first_label = gimple_switch_label (swtch, 1);
+ tree last_label = gimple_switch_label (swtch, num_labels - 1);
+
+ m_range_min = CASE_LOW (first_label);
+ m_range_max = CASE_LOW (last_label);
+ m_index_expr = gimple_switch_index (swtch);
+ m_switch_bb = swtch_bb;
+
+ m_range_size = int_const_binop (MINUS_EXPR, m_range_max, m_range_min);
+
+ m_cfg_altered = true;
+
+ m_contiguous_range = true;
+ wide_int last_wi = wi::to_wide (CASE_LOW (first_label));
+ for (i = 2; i < num_labels; i++)
+ {
+ tree label = gimple_switch_label (swtch, i);
+ wide_int label_wi = wi::to_wide (CASE_LOW (label));
+ m_contiguous_range &= wi::eq_p (wi::add (last_wi, 1), label_wi);
+ last_wi = label_wi;
+ }
+
+ m_exp_index_transform_applied = true;
+}
+
/* Checks whether the range given by individual case statements of the switch
switch statement isn't too big and whether the number of branches actually
satisfies the size of the new array. */
@@ -973,8 +1274,9 @@ switch_conversion::gen_inbound_check ()
bbf->count = e1f->count () + e2f->count ();
/* Tidy blocks that have become unreachable. */
- prune_bbs (bbd, m_final_bb,
- m_default_case_nonstandard ? m_default_bb : NULL);
+ bool prune_default_bb = !m_default_case_nonstandard
+ && !m_exp_index_transform_applied;
+ prune_bbs (bbd, m_final_bb, prune_default_bb ? NULL : m_default_bb);
/* Fixup the PHI nodes in bbF. */
fix_phi_nodes (e1f, e2f, bbf);
@@ -1053,8 +1355,19 @@ switch_conversion::expand (gswitch *swtch)
return;
}
- /* Check the case label values are within reasonable range: */
- if (!check_range ())
+ /* Sometimes it is possible to use the "exponential index transform" to help
+ switch conversion convert switches which it otherwise could not convert.
+ However, we want to do this transform only when we know that switch
+ conversion will then really be able to convert the switch. So we first
+ check if the transformation is applicable and then maybe later do the
+ transformation. */
+ bool exp_transform_viable = is_exp_index_transform_viable (swtch);
+
+ /* Check the case label values are within reasonable range.
+
+ If we will be doing exponential index transform, the range will be always
+ reasonable. */
+ if (!exp_transform_viable && !check_range ())
{
gcc_assert (m_reason);
return;
@@ -1076,6 +1389,9 @@ switch_conversion::expand (gswitch *swtch)
/* At this point all checks have passed and we can proceed with the
transformation. */
+ if (exp_transform_viable)
+ exp_index_transform (swtch);
+
create_temp_arrays ();
gather_default_values (m_default_case_nonstandard
? gimple_switch_label (swtch, 1)
diff --git a/gcc/tree-switch-conversion.h b/gcc/tree-switch-conversion.h
index 6939eec6018f..1a865f85f3a4 100644
--- a/gcc/tree-switch-conversion.h
+++ b/gcc/tree-switch-conversion.h
@@ -743,6 +743,19 @@ public:
/* Collection information about SWTCH statement. */
void collect (gswitch *swtch);
+ /* Check that the 'exponential index transform' can be applied.
+
+ See the comment at the function definition for more details. */
+ bool is_exp_index_transform_viable (gswitch *swtch);
+
+ /* Perform the 'exponential index transform'.
+
+ The exponential index transform shrinks the range of case numbers which
+ helps switch conversion convert switches it otherwise could not.
+
+ See the comment at the function definition for more details. */
+ void exp_index_transform (gswitch *swtch);
+
/* Checks whether the range given by individual case statements of the switch
switch statement isn't too big and whether the number of branches actually
satisfies the size of the new array. */
@@ -900,6 +913,11 @@ public:
/* True if CFG has been changed. */
bool m_cfg_altered;
+
+ /* True if exponential index transform has been applied. See the comment at
+ the definition of exp_index_transform for details about the
+ transformation. */
+ bool m_exp_index_transform_applied;
};
void
