[Bug tree-optimization/15524] [4.0 Regression] jump threading on trees is slow with switch statements with large # of cases

[Jeffrey A Law]

With loop bounds recording no longer charged to the expander it's time
to deal with the inefficiencies which are in the switch expander.

Basically we have code which does

for each case
  for each case
    see if the label in the outer loop matches any of the cases in the
    inner loop (up to the current case in the outer loop).

Needless to say this can get rather expensive.

This patch avoids the inner loop completely by keeping track of the
target labels we've seen in a bitmap and only incrementing the unique
target count when we encounter a target which hasn't been seen.

Before this patch we got the following times for expand in pr15524.


expand          :   6.53 ( 5%) usr   0.03 ( 4%) sys   6.56 ( 5%)

After this patch we see:

expand          :   0.71 ( 1%) usr   0.02 ( 3%) sys   0.75 ( 1%)


Not bad.  Unfortunately, no measurable difference on insn-attrtab.i
and friends.  Oh well.

Bootstrapped and regression tested on i686-pc-linux-gnu



-------------- next part --------------
	* stmt.c (expand_case): Speed up code to detect duplicate case
	label targets and count unique case label targets.

Index: stmt.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/stmt.c,v
retrieving revision 1.406
diff -c -p -r1.406 stmt.c
*** stmt.c	26 Oct 2004 17:25:32 -0000	1.406
--- stmt.c	3 Nov 2004 08:03:15 -0000
*************** expand_case (tree exp)
*** 2317,2323 ****
  {
    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;
--- 2317,2323 ----
  {
    tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
    rtx default_label = 0;
!   struct case_node *n;
    unsigned int count, uniq;
    rtx index;
    rtx table_label;
*************** expand_case (tree exp)
*** 2354,2359 ****
--- 2354,2360 ----
    if (index_type != error_mark_node)
      {
        tree elt;
+       bitmap label_bitmap;
  
        /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
  	 expressions being INTEGER_CST.  */
*************** expand_case (tree exp)
*** 2392,2397 ****
--- 2393,2399 ----
  
        uniq = 0;
        count = 0;
+       label_bitmap = BITMAP_XMALLOC ();
        for (n = case_list; n; n = n->right)
  	{
  	  /* Count the elements and track the largest and smallest
*************** expand_case (tree exp)
*** 2412,2428 ****
  	  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 = case_list; m != n; m = m->right)
!             if (label_rtx (m->code_label) == lab)
!               {
!                 uniq--;
!                 break;
!               }
  	}
  
        /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
  	 destination, such as one with a default case only.  */
        gcc_assert (count != 0);
--- 2414,2431 ----
  	  if (! tree_int_cst_equal (n->low, n->high))
  	    count++;
  
! 	  /* If we have not seen this label yet, then increase the
! 	     number of unique case node targets seen.  */
  	  lab = label_rtx (n->code_label);
! 	  if (!bitmap_bit_p (label_bitmap, CODE_LABEL_NUMBER (lab)))
! 	    {
! 	      bitmap_set_bit (label_bitmap, CODE_LABEL_NUMBER (lab));
! 	      uniq++;
! 	    }
  	}
  
+       BITMAP_XFREE (label_bitmap);
+ 
        /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
  	 destination, such as one with a default case only.  */
        gcc_assert (count != 0);