[PATCH] Optimize tablejumps for switch statements

[Roger Sayle <roger at eyesopen dot com>]

This is the second of two patches, and depends upon the one just
posted "[PATCH] Remove superfluous variable in expand_end_case".

GCC implements suitable dense switch statements using a tablejump.
The generated code subtracts the minimum case value from the index
expression and performs an unsigned comparison against maxval-minval
to check that the index is in the required range.

This run-time subtraction is currently always performed even for very
small minimum values, such as 1.  A simple optimization to avoid this
subtraction is to index the jump table from zero for suitable minimum
values, filling the extra slots with the address of the default branch.
This typically removes a "dec" or "sub" instruction at the expense
of one or two additional pointers in the jump table.  As this typically
increases the code size marginally, the patch below only enables the
optimization when not optimizing for code size.

This optimization is surprisingly applicable. An analysis of the 7086
switches compiled during a bootstrap of gcc-3.0.1 on i686-pc-linux-gnu
reveals 1229 (17%) have a minimum case value of zero, 2151 (30%) have a
minimum case value of one, 533 (7.5%) a value of two, and only 74 (1%)
a value of three.  By this analysis, one is the most common minimum case
value, including the parser's switch statements generated by flex.

The decision was made to apply the optimization to tablejumps but not
casei instructions.  It was assumed that "casei" had no additional
subtraction overhead, and may place the jump tables in-line potentially
causing cache issues.  Potentially a backend can enable or disable
this optimization by using "casei" rather than "tablejump" insns.
Targets, such as the s390, that already do this, are't be affected.

Bootstraped on i686-pc-linux-gnu with no regressions.


2001-10-24  Roger Sayle <roger@eyesopen.com>

	* stmt.c (expand_end_case): Index jumptables from zero for
	suitably small values of minval.


diff -c -3 -p -r1.221 stmt.c
*** stmt.c	2001/10/18 21:34:14	1.221
--- stmt.c	2001/10/21 22:34:11
*************** expand_end_case (orig_index)
*** 5533,5538 ****
--- 5533,5550 ----
  			    table_label, default_label))
  	    {
  	      index_type = thiscase->data.case_stmt.nominal_type;
+
+               /* Index jumptables from zero for suitable values of
+                  minval to avoid a subtraction.  */
+               if (! optimize_size
+                   && compare_tree_int (minval, 0) > 0
+                   && compare_tree_int (minval, 3) < 0
+                   && compare_tree_int (maxval, 0) >= 0)
+                 {
+                   minval = integer_zero_node;
+                   range = maxval;
+                 }
+
  	      if (! try_tablejump (index_type, index_expr, minval, range,
  				   table_label, default_label))
  		abort ();


--
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-438-3470