[PATCH] Fix PR14495, allow VRP to delete dead labels in SWITCH_EXPRs and dead edges out of it

[Richard Guenther <rguenther at suse dot de>]

This fixes PR14495 which is complaining that we don't use value range
information to prune out dead switch labels and destinations.  The patch
applies on top of the other tree patches I posted yesterday (it needs
the find_case_label_index() helper, otherwise it is independent).
(For reference: http://gcc.gnu.org/ml/gcc-patches/2007-04/msg00990.html)

The patch does achieve the goal by recognizing which CFG manipulations
and SWITCH_EXPR changes need to be done at substitute-and-fold time
(which is where we optimize COND_EXPRs) and later before we finalize
jump threading, remove the dead edges and updates the SWITCH_EXPRs.

Bootstrapped and tested on x86_64-unknown-linux-gnu.

Ok for mainline?

Thanks,
Richard.

:ADDPATCH VRP:

2007-04-16  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/14495
	* tree-vrp.c (struct switch_update): New structure.
	(to_remove_edges, to_update_switch_stmts): New VECs.
	(simplify_switch_using_ranges): New function.  Remove not taken
	case labels and edges.
	(simplify_stmt_using_ranges): Call it.
	(identify_jump_threads): Mark edges we have queued for removal
	so we don't thread them.
	(execute_vrp): Remove edges queued for removal, update SWITCH_STMT
	case label vector.

	* gcc.dg/tree-ssa/vrp36.c: New testcase.

Index: gcc/tree-vrp.c
===================================================================
*** gcc.orig/tree-vrp.c	2007-04-13 16:28:06.000000000 +0200
--- gcc/tree-vrp.c	2007-04-17 11:41:13.000000000 +0200
*************** static sbitmap blocks_visited;
*** 95,100 ****
--- 95,110 ----
     of values that SSA name N_I may take.  */
  static value_range_t **vr_value;
  
+ typedef struct {
+   tree stmt;
+   tree vec;
+ } switch_update;
+ 
+ static VEC (edge, heap) *to_remove_edges;
+ DEF_VEC_O(switch_update);
+ DEF_VEC_ALLOC_O(switch_update, heap);
+ static VEC (switch_update, heap) *to_update_switch_stmts;
+ 
  
  /* Return whether TYPE should use an overflow infinity distinct from
     TYPE_{MIN,MAX}_VALUE.  We use an overflow infinity value to
*************** simplify_cond_using_ranges (tree stmt)
*** 5731,5736 ****
--- 5736,5814 ----
      }
  }
  
+ /* Simplify a switch statement using the value range of the switch
+    argument.  */
+ 
+ static void
+ simplify_switch_using_ranges (tree stmt)
+ {
+   tree op = TREE_OPERAND (stmt, 0);
+   value_range_t *vr;
+   bool take_default;
+   edge e;
+   edge_iterator ei;
+   size_t i = 0, j = 0, n, n2;
+   tree vec, vec2;
+   switch_update su;
+ 
+   if (TREE_CODE (op) != SSA_NAME)
+     return;
+ 
+   vr = get_value_range (op);
+ 
+   /* We only can handle integer ranges.  */
+   if (vr->type != VR_RANGE
+       || symbolic_range_p (vr))
+     return;
+ 
+   /* Find case label for min/max of the value range.  */
+   vec = SWITCH_LABELS (stmt);
+   n = TREE_VEC_LENGTH (vec);
+   take_default = !find_case_label_index (vec, 0, vr->min, &i);
+   take_default |= !find_case_label_index (vec, i, vr->max, &j);
+   /* The following is just conservative.  */
+   take_default |= j > i;
+ 
+   /* Bail out if this is just all edges taken.  */
+   if (i == 0
+       && j == n - 2
+       && take_default)
+     return;
+ 
+   /* Build a new vector of taken case labels.  */
+   vec2 = make_tree_vec (j - i + 1 + (int)take_default);
+   for (n2 = 0; i <= j; ++i, ++n2)
+     TREE_VEC_ELT (vec2, n2) = TREE_VEC_ELT (vec, i);
+ 
+   /* Add the default edge, if necessary.  */
+   if (take_default)
+     TREE_VEC_ELT (vec2, n2++) = TREE_VEC_ELT (vec, n - 1);
+ 
+   /* Mark needed edges.  */
+   for (i = 0; i < n2; ++i)
+     {
+       e = find_edge (bb_for_stmt (stmt),
+ 		     label_to_block (CASE_LABEL (TREE_VEC_ELT (vec2, i))));
+       e->aux = (void *)-1;
+     }
+   /* Queue not needed edges for later removal.  */
+   FOR_EACH_EDGE (e, ei, bb_for_stmt (stmt)->succs)
+     {
+       if (e->aux == (void *)-1)
+ 	{
+ 	  e->aux = NULL;
+ 	  continue;
+ 	}
+ 
+       VEC_safe_push (edge, heap, to_remove_edges, e);
+     }
+ 
+   /* And queue an update for the stmt.  */
+   su.stmt = stmt;
+   su.vec = vec2;
+   VEC_safe_push (switch_update, heap, to_update_switch_stmts, &su);
+ }
+ 
  /* Simplify STMT using ranges if possible.  */
  
  void
*************** simplify_stmt_using_ranges (tree stmt)
*** 5757,5765 ****
      }
    else if (TREE_CODE (stmt) == COND_EXPR
  	   && COMPARISON_CLASS_P (COND_EXPR_COND (stmt)))
!     {
!       simplify_cond_using_ranges (stmt);
!     }
  }
  
  /* Stack of dest,src equivalency pairs that need to be restored after
--- 5835,5843 ----
      }
    else if (TREE_CODE (stmt) == COND_EXPR
  	   && COMPARISON_CLASS_P (COND_EXPR_COND (stmt)))
!     simplify_cond_using_ranges (stmt);
!   else if (TREE_CODE (stmt) == SWITCH_EXPR)
!     simplify_switch_using_ranges (stmt);
  }
  
  /* Stack of dest,src equivalency pairs that need to be restored after
*************** identify_jump_threads (void)
*** 5811,5816 ****
--- 5889,5896 ----
  {
    basic_block bb;
    tree dummy;
+   int i;
+   edge e;
  
    /* Ugh.  When substituting values earlier in this pass we can
       wipe the dominance information.  So rebuild the dominator
*************** identify_jump_threads (void)
*** 5824,5829 ****
--- 5904,5914 ----
       recompute it.  */
    mark_dfs_back_edges ();
  
+   /* Do not thread across edges we are about to remove.  Just marking
+      them as EDGE_DFS_BACK will do.  */
+   for (i = 0; VEC_iterate (edge, to_remove_edges, i, e); ++i)
+     e->flags |= EDGE_DFS_BACK;
+ 
    /* Allocate our unwinder stack to unwind any temporary equivalences
       that might be recorded.  */
    stack = VEC_alloc (tree, heap, 20);
*************** identify_jump_threads (void)
*** 5869,5875 ****
  	      && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))))
  	{
  	  edge_iterator ei;
- 	  edge e;
  
  	  /* We've got a block with multiple predecessors and multiple
  	     successors which also ends in a suitable conditional.  For
--- 5954,5959 ----
*************** vrp_finalize (void)
*** 6026,6037 ****
--- 6110,6128 ----
  static unsigned int
  execute_vrp (void)
  {
+   int i;
+   edge e;
+   switch_update *su;
+ 
    insert_range_assertions ();
  
    loop_optimizer_init (LOOPS_NORMAL);
    if (current_loops)
      scev_initialize ();
  
+   to_remove_edges = VEC_alloc (edge, heap, 10);
+   to_update_switch_stmts = VEC_alloc (switch_update, heap, 5);
+ 
    vrp_initialize ();
    ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node);
    vrp_finalize ();
*************** execute_vrp (void)
*** 6042,6047 ****
--- 6133,6152 ----
        loop_optimizer_finalize ();
      }
  
+   /* Remove dead edges from SWITCH_EXPR optimization.  This leaves the
+      CFG in a broken state and requires a cfg_cleanup run.  */
+   for (i = 0; VEC_iterate (edge, to_remove_edges, i, e); ++i)
+     remove_edge (e);
+   /* Update SWITCH_EXPR case label vector.  */
+   for (i = 0; VEC_iterate (switch_update, to_update_switch_stmts, i, su); ++i)
+     SWITCH_LABELS (su->stmt) = su->vec;
+ 
+   if (VEC_length (edge, to_remove_edges) > 0)
+     free_dominance_info (CDI_DOMINATORS);
+ 
+   VEC_free (edge, heap, to_remove_edges);
+   VEC_free (switch_update, heap, to_update_switch_stmts);
+ 
    /* ASSERT_EXPRs must be removed before finalizing jump threads
       as finalizing jump threads calls the CFG cleanup code which
       does not properly handle ASSERT_EXPRs.  */
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp36.c
===================================================================
*** /dev/null	1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/vrp36.c	2007-04-16 11:58:46.000000000 +0200
***************
*** 0 ****
--- 1,27 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-vrp1" } */
+ 
+ void bar0 (void);
+ void bar1 (void);
+ void bar2 (void);
+ void bar3 (void);
+ 
+ void
+ foo (int a)
+ {
+   if (a < 100)
+     return;
+   if (200 < a)
+     return;
+ 
+   switch (a)
+     {
+     case  99: bar0 (); return;
+     case 100: bar1 (); return;
+     case 101: bar2 (); return;
+     case 102: bar3 (); return;
+     }
+ }
+ 
+ /* { dg-final { scan-tree-dump-not "case 99:" "vrp1" } } */
+ /* { dg-final { cleanup-tree-dump "vrp1" } } */