This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] Implement switch statements with bit tests (take 2)
- From: Roger Sayle <roger at www dot eyesopen dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Sat, 25 Jan 2003 07:54:18 -0700 (MST)
- Subject: [PATCH] Implement switch statements with bit tests (take 2)
This patch is an updated and improved version of my recent patch to
implement C/C++ switch statements using bit tests. For details, see
http://gcc.gnu.org/ml/gcc-patches/2003-01/msg01733.html
This revision incorporates most of the excellent suggestions made
to the list. Based on feed-back from Richard Henderson and Richard
Kenner, the bit tests are now performed in "word_mode", i.e. using
64-bits on 64-bit hosts, from suggestions made by Geoff Keating, it
now determines whether "1 << x" is cheap using rtx_cost [via the
new function lshift_cheap_p()], and from comments from Kaveh Ghazi
I've also added a test case that checks that suitable switch statements
function correctly, even when "x < 0" and "x > 64".
Admittedly there are still two ideas that haven't yet been implemented.
The first is RTH's suggestion to narrow the mode of the bit tests where
possible, and the second from Falk Hueffner and Richard Earnshaw for
shifting the constant rather than the one, and testing via the either
sign-bit or the least significant bit. Both excellent improvements, but
optimizations rather the being required for correctness. I'd prefer to
request approval for this current version that I'm confident in, and have
further optimizations submitted as follow-up patches that may be reverted
independently.
The following patch has been retested on i686-pc-linux-gnu, with a
complete "make bootstrap", all languages except Ada and treelang, and
with a full "make -k check" with no new regressions. I also tried
to test on alphaev67-dec-osf5.1 (for the 64-bit changes) but it looks
like config.guess is currently fails on HP/Compaq Tru64.
Ok for mainline?
2003-01-25 Roger Sayle <roger@eyesopen.com>
* stmt.c (emit_case_bit_tests): New routine to implement suitable
switch statements using the equivalent of "if ((1<<x) & cst) ... ".
(case_bit_test_cmp): New comparison function for "qsort" to order
case_bit_tests by decreasing number of destination nodes.
(lshift_cheap_p): New function to determine if "1 << x" is cheap.
(expand_end_case_type): Use emit_case_bit_tests to implement
suitable switch statments.
(CASE_USE_BIT_TESTS): New target macro to disable the above.
* Makefile.in (stmt.o): Add dependency on optab.h.
* doc/tm.texi (CASE_USE_BIT_TESTS): Document new target macro.
* gcc.c-torture/execute/switch-1.c: New test case.
Index: stmt.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/stmt.c,v
retrieving revision 1.286
diff -c -3 -p -r1.286 stmt.c
*** stmt.c 21 Jan 2003 20:52:44 -0000 1.286
--- stmt.c 24 Jan 2003 22:03:35 -0000
*************** Software Foundation, 59 Temple Place - S
*** 56,61 ****
--- 56,62 ----
#include "ggc.h"
#include "langhooks.h"
#include "predict.h"
+ #include "optabs.h"
/* Assume that case vectors are not pc-relative. */
#ifndef CASE_VECTOR_PC_RELATIVE
*************** static void do_jump_if_equal PARAMS ((r
*** 420,425 ****
--- 421,430 ----
static int estimate_case_costs PARAMS ((case_node_ptr));
static bool same_case_target_p PARAMS ((rtx, rtx));
static void strip_default_case_nodes PARAMS ((case_node_ptr *, rtx));
+ static bool lshift_cheap_p PARAMS ((void));
+ static int case_bit_test_cmp PARAMS ((const void *, const void *));
+ static void emit_case_bit_tests PARAMS ((tree, tree, tree, tree,
+ case_node_ptr, rtx));
static void group_case_nodes PARAMS ((case_node_ptr));
static void balance_case_nodes PARAMS ((case_node_ptr *,
case_node_ptr));
*************** check_for_full_enumeration_handling (typ
*** 5180,5185 ****
--- 5185,5338 ----
}
+ /* Maximum number of case bit tests. */
+ #define MAX_CASE_BIT_TESTS 3
+
+ /* By default, enable case bit tests on targets with ashlsi3. */
+ #ifndef CASE_USE_BIT_TESTS
+ #define CASE_USE_BIT_TESTS (ashl_optab->handlers[word_mode].insn_code \
+ != CODE_FOR_nothing)
+ #endif
+
+
+ /* A case_bit_test represents a set of case nodes that may be
+ selected from using a bit-wise comparison. HI and LO hold
+ the integer to be tested against, LABEL contains the label
+ to jump to upon success and BITS counts the number of case
+ nodes handled by this test, typically the number of bits
+ set in HI:LO. */
+
+ struct case_bit_test
+ {
+ HOST_WIDE_INT hi;
+ HOST_WIDE_INT lo;
+ rtx label;
+ int bits;
+ };
+
+ /* Determine whether "1 << x" is relatively cheap in word_mode. */
+
+ static bool lshift_cheap_p ()
+ {
+ static bool init = false;
+ static bool cheap = true;
+
+ if (!init)
+ {
+ rtx reg = gen_rtx_REG (word_mode, 10000);
+ int cost = rtx_cost (gen_rtx_ASHIFT (word_mode, const1_rtx, reg), SET);
+ cheap = cost < COSTS_N_INSNS (3);
+ init = true;
+ }
+
+ return cheap;
+ }
+
+ /* Comparison function for qsort to order bit tests by decreasing
+ number of case nodes, i.e. the node with the most cases gets
+ tested first. */
+
+ static int case_bit_test_cmp (p1, p2)
+ const void *p1;
+ const void *p2;
+ {
+ const struct case_bit_test *d1 = p1;
+ const struct case_bit_test *d2 = p2;
+
+ return d2->bits - d1->bits;
+ }
+
+ /* Expand a switch statement by a short sequence of bit-wise
+ comparisons. "switch(x)" is effectively converted into
+ "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
+ integer constants.
+
+ INDEX_EXPR is the value being switched on, which is of
+ type INDEX_TYPE. MINVAL is the lowest case value of in
+ the case nodes, of INDEX_TYPE type, and RANGE is highest
+ value minus MINVAL, also of type INDEX_TYPE. NODES is
+ the set of case nodes, and DEFAULT_LABEL is the label to
+ branch to should none of the cases match.
+
+ There *MUST* be MAX_CASE_BIT_TESTS or less unique case
+ node targets. */
+
+ static void
+ emit_case_bit_tests (index_type, index_expr, minval, range,
+ nodes, default_label)
+ tree index_type, index_expr, minval, range;
+ case_node_ptr nodes;
+ rtx default_label;
+ {
+ struct case_bit_test test[MAX_CASE_BIT_TESTS];
+ enum machine_mode mode;
+ rtx expr, index, label;
+ unsigned int i,j,lo,hi;
+ struct case_node *n;
+ unsigned int count;
+
+ count = 0;
+ for (n = nodes; n; n = n->right)
+ {
+ label = label_rtx (n->code_label);
+ for (i = 0; i < count; i++)
+ if (same_case_target_p (label, test[i].label))
+ break;
+
+ if (i == count)
+ {
+ if (count >= MAX_CASE_BIT_TESTS)
+ abort ();
+ test[i].hi = 0;
+ test[i].lo = 0;
+ test[i].label = label;
+ test[i].bits = 1;
+ count++;
+ }
+ else
+ test[i].bits++;
+
+ lo = tree_low_cst (fold (build (MINUS_EXPR, index_type,
+ n->low, minval)), 1);
+ hi = tree_low_cst (fold (build (MINUS_EXPR, index_type,
+ n->high, minval)), 1);
+ for (j = lo; j <= hi; j++)
+ if (j >= HOST_BITS_PER_WIDE_INT)
+ test[i].hi |= (HOST_WIDE_INT) 1 << (j - HOST_BITS_PER_INT);
+ else
+ test[i].lo |= (HOST_WIDE_INT) 1 << j;
+ }
+
+ qsort (test, count, sizeof(*test), case_bit_test_cmp);
+
+ index_expr = fold (build (MINUS_EXPR, index_type,
+ convert (index_type, index_expr),
+ convert (index_type, minval)));
+ index = expand_expr (index_expr, NULL_RTX, VOIDmode, 0);
+ emit_queue ();
+ index = protect_from_queue (index, 0);
+ do_pending_stack_adjust ();
+
+ mode = TYPE_MODE (index_type);
+ expr = expand_expr (range, NULL_RTX, VOIDmode, 0);
+ emit_cmp_and_jump_insns (index, expr, GTU, NULL_RTX, mode, 1,
+ default_label);
+
+ index = convert_to_mode (word_mode, index, 0);
+ index = expand_binop (word_mode, ashl_optab, const1_rtx,
+ index, NULL_RTX, 1, OPTAB_WIDEN);
+
+ for (i = 0; i < count; i++)
+ {
+ expr = immed_double_const (test[i].lo, test[i].hi, word_mode);
+ expr = expand_binop (word_mode, and_optab, index, expr,
+ NULL_RTX, 1, OPTAB_WIDEN);
+ emit_cmp_and_jump_insns (expr, const0_rtx, NE, NULL_RTX,
+ word_mode, 1, test[i].label);
+ }
+
+ emit_jump (default_label);
+ }
/* Terminate a case (Pascal) or switch (C) statement
in which ORIG_INDEX is the expression to be tested.
*************** expand_end_case_type (orig_index, orig_t
*** 5193,5206 ****
{
tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
rtx default_label = 0;
! struct case_node *n;
! unsigned int count;
rtx index;
rtx table_label;
int ncases;
rtx *labelvec;
int i;
! rtx before_case, end;
struct nesting *thiscase = case_stack;
tree index_expr, index_type;
bool exit_done = false;
--- 5346,5359 ----
{
tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
rtx default_label = 0;
! struct case_node *n, *m;
! unsigned int count, uniq;
rtx index;
rtx table_label;
int ncases;
rtx *labelvec;
int i;
! rtx before_case, end, lab;
struct nesting *thiscase = case_stack;
tree index_expr, index_type;
bool exit_done = false;
*************** expand_end_case_type (orig_index, orig_t
*** 5275,5280 ****
--- 5428,5434 ----
/* Get upper and lower bounds of case values.
Also convert all the case values to the index expr's data type. */
+ uniq = 0;
count = 0;
for (n = thiscase->data.case_stmt.case_list; n; n = n->right)
{
*************** expand_end_case_type (orig_index, orig_t
*** 5304,5309 ****
--- 5458,5473 ----
/* A range counts double, since it requires two compares. */
if (! tree_int_cst_equal (n->low, n->high))
count++;
+
+ /* Count the number of unique case node targets. */
+ uniq++;
+ lab = label_rtx (n->code_label);
+ for (m = thiscase->data.case_stmt.case_list; m != n; m = m->right)
+ if (same_case_target_p (label_rtx (m->code_label), lab))
+ {
+ uniq--;
+ break;
+ }
}
/* Compute span of values. */
*************** expand_end_case_type (orig_index, orig_t
*** 5317,5322 ****
--- 5481,5511 ----
expand_expr (index_expr, const0_rtx, VOIDmode, 0);
emit_queue ();
emit_jump (default_label);
+ }
+
+ /* Try implementing this switch statement by a short sequence of
+ bit-wise comparisons. However, we let the binary-tree case
+ below handle constant index expressions. */
+ else if (CASE_USE_BIT_TESTS
+ && ! TREE_CONSTANT (index_expr)
+ && compare_tree_int (range, GET_MODE_BITSIZE (word_mode)) < 0
+ && lshift_cheap_p ()
+ && ((uniq == 1 && count >= 3)
+ || (uniq == 2 && count >= 5)
+ || (uniq == 3 && count >= 6)))
+ {
+ /* Optimize the case where all the case values fit in a
+ word without having to subtract MINVAL. In this case,
+ we can optimize away the subtraction. */
+ if (compare_tree_int (minval, 0) > 0
+ && compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0)
+ {
+ minval = integer_zero_node;
+ range = maxval;
+ }
+ emit_case_bit_tests (index_type, index_expr, minval, range,
+ thiscase->data.case_stmt.case_list,
+ default_label);
}
/* If range of values is much bigger than number of values,
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.975
diff -c -3 -p -r1.975 Makefile.in
*** Makefile.in 22 Jan 2003 04:58:26 -0000 1.975
--- Makefile.in 24 Jan 2003 22:03:36 -0000
*************** function.o : function.c $(CONFIG_H) $(SY
*** 1460,1466 ****
stmt.o : stmt.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) $(TREE_H) flags.h \
function.h insn-config.h hard-reg-set.h $(EXPR_H) libfuncs.h except.h \
$(LOOP_H) $(RECOG_H) toplev.h output.h varray.h $(GGC_H) $(TM_P_H) \
! langhooks.h $(PREDICT_H) gt-stmt.h
except.o : except.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) $(TREE_H) \
flags.h except.h function.h $(EXPR_H) libfuncs.h integrate.h langhooks.h \
insn-config.h hard-reg-set.h $(BASIC_BLOCK_H) output.h \
--- 1460,1466 ----
stmt.o : stmt.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) $(TREE_H) flags.h \
function.h insn-config.h hard-reg-set.h $(EXPR_H) libfuncs.h except.h \
$(LOOP_H) $(RECOG_H) toplev.h output.h varray.h $(GGC_H) $(TM_P_H) \
! langhooks.h $(PREDICT_H) gt-stmt.h $(OPTABS_H)
except.o : except.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) $(TREE_H) \
flags.h except.h function.h $(EXPR_H) libfuncs.h integrate.h langhooks.h \
insn-config.h hard-reg-set.h $(BASIC_BLOCK_H) output.h \
Index: doc/tm.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/tm.texi,v
retrieving revision 1.191
diff -c -3 -p -r1.191 tm.texi
*** doc/tm.texi 19 Jan 2003 13:04:23 -0000 1.191
--- doc/tm.texi 24 Jan 2003 22:03:39 -0000
*************** is best to use a jump-table instead of a
*** 8618,8623 ****
--- 8618,8633 ----
The default is four for machines with a @code{casesi} instruction and
five otherwise. This is best for most machines.
+ @findex CASE_USE_BIT_TESTS
+ @item CASE_USE_BIT_TESTS
+ Define this macro to be a C expression to indicate whether C switch
+ statements may be implemented by a sequence of bit tests. This is
+ advantageous on processors that can efficiently implement left shift
+ of 1 by the number of bits held in a register, but inappropriate on
+ targets that would require a loop. By default, this macro returns
+ @code{true} if the target defines an @code{ashlsi3} pattern, and
+ @code{false} otherwise.
+
@findex WORD_REGISTER_OPERATIONS
@item WORD_REGISTER_OPERATIONS
Define this macro if operations between registers with integral mode
*** /dev/null Thu Aug 30 14:30:55 2001
--- gcc.c-torture/execute/switch-1.c Sat Jan 25 07:38:06 2003
***************
*** 0 ****
--- 1,57 ----
+ /* Copyright (C) 2003 Free Software Foundation.
+
+ Test that switch statements suitable using case bit tests are
+ implemented correctly.
+
+ Written by Roger Sayle, 01/25/2001. */
+
+ extern void abort (void);
+
+ int
+ foo (int x)
+ {
+ switch (x)
+ {
+ case 4:
+ case 6:
+ case 9:
+ case 11:
+ return 30;
+ }
+ return 31;
+ }
+
+ int
+ main (int argc)
+ {
+ int i, r;
+
+ for (i=-1; i<66; i++)
+ {
+ r = foo (i);
+ if (i == 4)
+ {
+ if (r != 30)
+ abort ();
+ }
+ else if (i == 6)
+ {
+ if (r != 30)
+ abort ();
+ }
+ else if (i == 9)
+ {
+ if (r != 30)
+ abort ();
+ }
+ else if (i == 11)
+ {
+ if (r != 30)
+ abort ();
+ }
+ else if (r != 31)
+ abort ();
+ }
+ return 0;
+ }
+
Roger
--
Roger Sayle, E-mail: roger@eyesopen.com
OpenEye Scientific Software, WWW: http://www.eyesopen.com/
Suite 1107, 3600 Cerrillos Road, Tel: (+1) 505-473-7385
Santa Fe, New Mexico, 87507. Fax: (+1) 505-473-0833