[PATCH] Fix PR14495 (2/2)

[PATCH] Fix PR14495 (2/2)

[Richard Guenther]

This implements removal of never reached case labels in switch
statements in the VRP pass.  In particular this will also fix
PR34793 where we produce "may be used uninitialized" warnings
because CFG construction always inserts a default case label
which then feeds an undefined PHI argument ... thus this patch
also gets somewhat big as expansion and case label grouping
need to deal with switch stmts without a default label.

For small switch statements omitting the default label results
in non-insignificant code size savings, as often range checking
is present before these and most sources have a default case
label just to silence the compiler warning that not all possible
input values are covered.  I measured compile-time effects on
cc1files where I can measure nothing but noise.

Bootstrapped and tested on x86_64-unknown-linux-gnu, ok
for mainline?

Thanks,
Richard.

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

	PR tree-optimization/14495
	PR tree-optimization/34793
	* 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.
	* tree-cfg.c (group_case_labels): Deal with missing default label.
	(tree_verify_flow_info): Allow missing default label.
	* stmt.c (emit_case_bit_tests): Deal with NULL default_label.
	(emit_case_nodes): Likewise.
	(expand_case): Do not rely on the default label to be present.
	* expr.c (try_casesi): Deal with NULL default_label.
	(do_tablejump): Likewise.

	* gcc.dg/tree-ssa/vrp39.c: New testcase.
	* gcc.dg/tree-ssa/vrp40.c: Likewise.

Index: gcc/tree-vrp.c
===================================================================
*** gcc/tree-vrp.c.orig	2008-03-28 13:23:13.000000000 +0100
--- gcc/tree-vrp.c	2008-03-28 15:32:59.000000000 +0100
*************** static value_range_t **vr_value;
*** 102,107 ****
--- 102,117 ----
     node.  */
  static int *vr_phi_edge_counts;
  
+ 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)
*** 6168,6173 ****
--- 6178,6282 ----
      }
  }
  
+ /* 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);
+ 
+   /* If the case label range is continuous, we do not need to
+      preserve the default case label.  Verify that.  */
+   if (!take_default && j > i)
+     {
+       tree low, high;
+       size_t k;
+ 
+       high = CASE_LOW (TREE_VEC_ELT (vec, i));
+       if (CASE_HIGH (TREE_VEC_ELT (vec, i)))
+ 	high = CASE_HIGH (TREE_VEC_ELT (vec, i));
+       for (k = i + 1; k <= j; ++k)
+ 	{
+ 	  low = CASE_LOW (TREE_VEC_ELT (vec, k));
+ 	  if (!integer_onep (int_const_binop (MINUS_EXPR, low, high, 0)))
+ 	    {
+ 	      take_default = true;
+ 	      break;
+ 	    }
+ 	  high = low;
+ 	  if (CASE_HIGH (TREE_VEC_ELT (vec, k)))
+ 	    high = CASE_HIGH (TREE_VEC_ELT (vec, k));
+ 	}
+     }
+ 
+   /* 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;
+ 	}
+ 
+       if (dump_file && (dump_flags & TDF_DETAILS))
+ 	{
+ 	  fprintf (dump_file, "removing unreachable case label\n");
+ 	}
+       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)
*** 6194,6202 ****
      }
    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
--- 6303,6311 ----
      }
    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)
*** 6248,6253 ****
--- 6357,6364 ----
  {
    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)
*** 6261,6266 ****
--- 6372,6382 ----
       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)
*** 6306,6312 ****
  	      && 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
--- 6422,6427 ----
*************** record_numbers_of_iterations (void)
*** 6473,6478 ****
--- 6588,6597 ----
  static unsigned int
  execute_vrp (void)
  {
+   int i;
+   edge e;
+   switch_update *su;
+ 
    loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
    rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
    scev_initialize ();
*************** execute_vrp (void)
*** 6490,6499 ****
--- 6609,6635 ----
       ranges are corrected.  */
    record_numbers_of_iterations ();
  
+   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 ();
  
+   /* 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/vrp39.c
===================================================================
*** /dev/null	1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/vrp39.c	2008-03-28 13:23:18.000000000 +0100
***************
*** 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" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp40.c
===================================================================
*** /dev/null	1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/vrp40.c	2008-03-28 13:23:18.000000000 +0100
***************
*** 0 ****
--- 1,22 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -Wuninitialized" } */
+ 
+ int foo(int val)
+ {
+   int tmp;
+   if ((val > 5) && (val < 8))
+     {
+       switch (val)
+         {
+         case 6:
+           tmp = 1;
+           break;
+         case 7:
+           tmp = 2;
+           break;
+         }
+       return tmp; /* { dg-bogus "used uninitialized" } */
+     }
+   return 0;
+ }
+ 
Index: gcc/tree-cfg.c
===================================================================
*** gcc/tree-cfg.c.orig	2008-03-27 17:29:57.000000000 +0100
--- gcc/tree-cfg.c	2008-03-28 16:53:24.000000000 +0100
*************** group_case_labels (void)
*** 1060,1077 ****
  	  tree labels = SWITCH_LABELS (stmt);
  	  int old_size = TREE_VEC_LENGTH (labels);
  	  int i, j, new_size = old_size;
! 	  tree default_case = TREE_VEC_ELT (labels, old_size - 1);
! 	  tree default_label;
  
  	  /* The default label is always the last case in a switch
! 	     statement after gimplification.  */
! 	  default_label = CASE_LABEL (default_case);
  
! 	  /* Look for possible opportunities to merge cases.
! 	     Ignore the last element of the label vector because it
! 	     must be the default case.  */
            i = 0;
! 	  while (i < old_size - 1)
  	    {
  	      tree base_case, base_label, base_high;
  	      base_case = TREE_VEC_ELT (labels, i);
--- 1060,1082 ----
  	  tree labels = SWITCH_LABELS (stmt);
  	  int old_size = TREE_VEC_LENGTH (labels);
  	  int i, j, new_size = old_size;
! 	  tree default_case = NULL_TREE;
! 	  tree default_label = NULL_TREE;
  
  	  /* The default label is always the last case in a switch
! 	     statement after gimplification if it was not optimized
! 	     away.  */
! 	  if (!CASE_LOW (TREE_VEC_ELT (labels, old_size - 1))
! 	      && !CASE_HIGH (TREE_VEC_ELT (labels, old_size - 1)))
! 	    {
! 	      default_case = TREE_VEC_ELT (labels, old_size - 1);
! 	      default_label = CASE_LABEL (default_case);
! 	      old_size--;
! 	    }
  
! 	  /* Look for possible opportunities to merge cases.  */
            i = 0;
! 	  while (i < old_size)
  	    {
  	      tree base_case, base_label, base_high;
  	      base_case = TREE_VEC_ELT (labels, i);
*************** group_case_labels (void)
*** 1095,1101 ****
  	      /* Try to merge case labels.  Break out when we reach the end
  		 of the label vector or when we cannot merge the next case
  		 label with the current one.  */
! 	      while (i < old_size - 1)
  		{
  		  tree merge_case = TREE_VEC_ELT (labels, i);
  	          tree merge_label = CASE_LABEL (merge_case);
--- 1100,1106 ----
  	      /* Try to merge case labels.  Break out when we reach the end
  		 of the label vector or when we cannot merge the next case
  		 label with the current one.  */
! 	      while (i < old_size)
  		{
  		  tree merge_case = TREE_VEC_ELT (labels, i);
  	          tree merge_label = CASE_LABEL (merge_case);
*************** tree_verify_flow_info (void)
*** 4629,4641 ****
  
  	    /* Verify that the case labels are sorted.  */
  	    prev = TREE_VEC_ELT (vec, 0);
! 	    for (i = 1; i < n - 1; ++i)
  	      {
  		tree c = TREE_VEC_ELT (vec, i);
  		if (! CASE_LOW (c))
  		  {
! 		    error ("found default case not at end of case vector");
! 		    err = 1;
  		    continue;
  		  }
  		if (! tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c)))
--- 4634,4649 ----
  
  	    /* Verify that the case labels are sorted.  */
  	    prev = TREE_VEC_ELT (vec, 0);
! 	    for (i = 1; i < n; ++i)
  	      {
  		tree c = TREE_VEC_ELT (vec, i);
  		if (! CASE_LOW (c))
  		  {
! 		    if (i != n - 1)
! 		      {
! 			error ("found default case not at end of case vector");
! 			err = 1;
! 		      }
  		    continue;
  		  }
  		if (! tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c)))
*************** tree_verify_flow_info (void)
*** 4649,4659 ****
  		  }
  		prev = c;
  	      }
! 	    if (CASE_LOW (TREE_VEC_ELT (vec, n - 1)))
! 	      {
! 		error ("no default case found at end of case vector");
! 		err = 1;
! 	      }
  
  	    FOR_EACH_EDGE (e, ei, bb->succs)
  	      {
--- 4657,4665 ----
  		  }
  		prev = c;
  	      }
! 	    /* VRP will remove the default case if it can prove it will
! 	       never be executed.  So do not verify there always exists
! 	       a default case here.  */
  
  	    FOR_EACH_EDGE (e, ei, bb->succs)
  	      {
Index: gcc/stmt.c
===================================================================
*** gcc/stmt.c.orig	2007-12-05 15:34:03.000000000 +0100
--- gcc/stmt.c	2008-03-28 14:22:48.000000000 +0100
*************** emit_case_bit_tests (tree index_type, tr
*** 2259,2266 ****
  
    mode = TYPE_MODE (index_type);
    expr = expand_normal (range);
!   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,
--- 2259,2267 ----
  
    mode = TYPE_MODE (index_type);
    expr = expand_normal (range);
!   if (default_label)
!     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,
*************** emit_case_bit_tests (tree index_type, tr
*** 2275,2281 ****
  			       word_mode, 1, test[i].label);
      }
  
!   emit_jump (default_label);
  }
  
  #ifndef HAVE_casesi
--- 2276,2283 ----
  			       word_mode, 1, test[i].label);
      }
  
!   if (default_label)
!     emit_jump (default_label);
  }
  
  #ifndef HAVE_casesi
*************** expand_case (tree exp)
*** 2321,2327 ****
    struct case_node *case_list = 0;
  
    /* Label to jump to if no case matches.  */
!   tree default_label_decl;
  
    alloc_pool case_node_pool = create_alloc_pool ("struct case_node pool",
                                                   sizeof (struct case_node),
--- 2323,2329 ----
    struct case_node *case_list = 0;
  
    /* Label to jump to if no case matches.  */
!   tree default_label_decl = NULL_TREE;
  
    alloc_pool case_node_pool = create_alloc_pool ("struct case_node pool",
                                                   sizeof (struct case_node),
*************** expand_case (tree exp)
*** 2339,2356 ****
      {
        tree elt;
        bitmap label_bitmap;
  
        /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
  	 expressions being INTEGER_CST.  */
        gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
  
!       /* The default case is at the end of TREE_VEC.  */
!       elt = TREE_VEC_ELT (vec, TREE_VEC_LENGTH (vec) - 1);
!       gcc_assert (!CASE_HIGH (elt));
!       gcc_assert (!CASE_LOW (elt));
!       default_label_decl = CASE_LABEL (elt);
  
!       for (i = TREE_VEC_LENGTH (vec) - 1; --i >= 0; )
  	{
  	  tree low, high;
  	  elt = TREE_VEC_ELT (vec, i);
--- 2341,2361 ----
      {
        tree elt;
        bitmap label_bitmap;
+       int vl = TREE_VEC_LENGTH (vec);
  
        /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
  	 expressions being INTEGER_CST.  */
        gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
  
!       /* The default case, if ever taken, is at the end of TREE_VEC.  */
!       elt = TREE_VEC_ELT (vec, vl - 1);
!       if (!CASE_LOW (elt) && !CASE_HIGH (elt))
! 	{
! 	  default_label_decl = CASE_LABEL (elt);
! 	  --vl;
! 	}
  
!       for (i = vl - 1; i >= 0; --i)
  	{
  	  tree low, high;
  	  elt = TREE_VEC_ELT (vec, i);
*************** expand_case (tree exp)
*** 2369,2375 ****
  
  
        before_case = start = get_last_insn ();
!       default_label = label_rtx (default_label_decl);
  
        /* Get upper and lower bounds of case values.  */
  
--- 2374,2381 ----
  
  
        before_case = start = get_last_insn ();
!       if (default_label_decl)
! 	default_label = label_rtx (default_label_decl);
  
        /* Get upper and lower bounds of case values.  */
  
*************** expand_case (tree exp)
*** 2414,2420 ****
  	 type, so we may still get a zero here.  */
        if (count == 0)
  	{
! 	  emit_jump (default_label);
            free_alloc_pool (case_node_pool);
  	  return;
  	}
--- 2420,2427 ----
  	 type, so we may still get a zero here.  */
        if (count == 0)
  	{
! 	  if (default_label)
! 	    emit_jump (default_label);
            free_alloc_pool (case_node_pool);
  	  return;
  	}
*************** expand_case (tree exp)
*** 2510,2516 ****
  	       && estimate_case_costs (case_list));
  	  balance_case_nodes (&case_list, NULL);
  	  emit_case_nodes (index, case_list, default_label, index_type);
! 	  emit_jump (default_label);
  	}
        else
  	{
--- 2517,2524 ----
  	       && estimate_case_costs (case_list));
  	  balance_case_nodes (&case_list, NULL);
  	  emit_case_nodes (index, case_list, default_label, index_type);
! 	  if (default_label)
! 	    emit_jump (default_label);
  	}
        else
  	{
*************** expand_case (tree exp)
*** 2560,2568 ****
  	    }
  
  	  /* Fill in the gaps with the default.  */
! 	  for (i = 0; i < ncases; i++)
! 	    if (labelvec[i] == 0)
! 	      labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label);
  
  	  /* Output the table.  */
  	  emit_label (table_label);
--- 2568,2577 ----
  	    }
  
  	  /* Fill in the gaps with the default.  */
! 	  if (default_label)
! 	    for (i = 0; i < ncases; i++)
! 	      if (labelvec[i] == 0)
! 	        labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label);
  
  	  /* Output the table.  */
  	  emit_label (table_label);
*************** emit_case_nodes (rtx index, case_node_pt
*** 3044,3050 ****
  	      emit_case_nodes (index, node->left, default_label, index_type);
  	      /* If left-hand subtree does nothing,
  		 go to default.  */
! 	      emit_jump (default_label);
  
  	      /* Code branches here for the right-hand subtree.  */
  	      expand_label (test_label);
--- 3053,3060 ----
  	      emit_case_nodes (index, node->left, default_label, index_type);
  	      /* If left-hand subtree does nothing,
  		 go to default.  */
! 	      if (default_label)
! 	        emit_jump (default_label);
  
  	      /* Code branches here for the right-hand subtree.  */
  	      expand_label (test_label);
*************** emit_case_nodes (rtx index, case_node_pt
*** 3179,3185 ****
  	    {
  	      /* If the left-hand subtree fell through,
  		 don't let it fall into the right-hand subtree.  */
! 	      emit_jump (default_label);
  
  	      expand_label (test_label);
  	      emit_case_nodes (index, node->right, default_label, index_type);
--- 3189,3196 ----
  	    {
  	      /* If the left-hand subtree fell through,
  		 don't let it fall into the right-hand subtree.  */
! 	      if (default_label)
! 		emit_jump (default_label);
  
  	      expand_label (test_label);
  	      emit_case_nodes (index, node->right, default_label, index_type);
Index: gcc/expr.c
===================================================================
*** gcc/expr.c.orig	2008-03-19 11:37:33.000000000 +0100
--- gcc/expr.c	2008-03-28 16:29:22.000000000 +0100
*************** try_casesi (tree index_type, tree index_
*** 9884,9891 ****
  			   index_expr, minval);
        minval = integer_zero_node;
        index = expand_normal (index_expr);
!       emit_cmp_and_jump_insns (rangertx, index, LTU, NULL_RTX,
! 			       omode, 1, default_label);
        /* Now we can safely truncate.  */
        index = convert_to_mode (index_mode, index, 0);
      }
--- 9884,9892 ----
  			   index_expr, minval);
        minval = integer_zero_node;
        index = expand_normal (index_expr);
!       if (default_label)
!         emit_cmp_and_jump_insns (rangertx, index, LTU, NULL_RTX,
! 				 omode, 1, default_label);
        /* Now we can safely truncate.  */
        index = convert_to_mode (index_mode, index, 0);
      }
*************** do_tablejump (rtx index, enum machine_mo
*** 9964,9971 ****
       or equal to the minimum value of the range and less than or equal to
       the maximum value of the range.  */
  
!   emit_cmp_and_jump_insns (index, range, GTU, NULL_RTX, mode, 1,
! 			   default_label);
  
    /* If index is in range, it must fit in Pmode.
       Convert to Pmode so we can index with it.  */
--- 9965,9973 ----
       or equal to the minimum value of the range and less than or equal to
       the maximum value of the range.  */
  
!   if (default_label)
!     emit_cmp_and_jump_insns (index, range, GTU, NULL_RTX, mode, 1,
! 			     default_label);
  
    /* If index is in range, it must fit in Pmode.
       Convert to Pmode so we can index with it.  */

Re: [PATCH] Fix PR14495 (2/2)

[Diego Novillo]

[ Apologies for the duplicate.  The first one was rejected by the list. ]

2008/3/28 Richard Guenther <rguenther@suse.de <mailto:rguenther@suse.de>>:

 >
 > PR tree-optimization/14495
 > PR tree-optimization/34793
 > * 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.
 > * tree-cfg.c (group_case_labels): Deal with missing default label.
 > (tree_verify_flow_info): Allow missing default label.
 > * stmt.c (emit_case_bit_tests): Deal with NULL default_label.
 > (emit_case_nodes): Likewise.
 > (expand_case): Do not rely on the default label to be present.
 > * expr.c (try_casesi): Deal with NULL default_label.
 > (do_tablejump): Likewise.
 >
 > * gcc.dg/tree-ssa/vrp39.c: New testcase.
 > * gcc.dg/tree-ssa/vrp40.c: Likewise.

OK. Two nits:

 > + /* We only can handle integer ranges. */

s/only can/can only/

 > + }
 > + /* Queue not needed edges for later removal. */

Blank line before comment.

Rafael, the next tuples merge will need some fixes in this area. The
default label is treated differently in tuples (it's the first label
of the vector).


Diego.

Re: [PATCH] Fix PR14495 (2/2)

[Richard Guenther]

On Tue, 1 Apr 2008, Diego Novillo wrote:

> 2008/3/28 Richard Guenther <rguenther@suse.de <mailto:rguenther@suse.de>>:
> 
> >
> > PR tree-optimization/14495
> > PR tree-optimization/34793
> > * 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.
> > * tree-cfg.c (group_case_labels): Deal with missing default label.
> > (tree_verify_flow_info): Allow missing default label.
> > * stmt.c (emit_case_bit_tests): Deal with NULL default_label.
> > (emit_case_nodes): Likewise.
> > (expand_case): Do not rely on the default label to be present.
> > * expr.c (try_casesi): Deal with NULL default_label.
> > (do_tablejump): Likewise.
> >
> > * gcc.dg/tree-ssa/vrp39.c: New testcase.
> > * gcc.dg/tree-ssa/vrp40.c: Likewise.
> 
> OK. Two nits:
> 
> > + /* We only can handle integer ranges. */
> 
> s/only can/can only/
> 
> > + }
> > + /* Queue not needed edges for later removal. */
> 
> Blank line before comment.
> 
> Rafael, the next tuples merge will need some fixes in this area. The
> default label is treated differently in tuples (it's the first label
> of the vector).

Indeed.  If you need help there, just drop me a note.

Richard.

Re: [PATCH] Fix PR14495 (2/2)

[Eric Botcazou]

[-- Attachment #1: Type: text/plain, Size: 1716 bytes --]

> +   /* 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.  */

I think there is an ordering problem: the CFG is broken at this point (and 
dominance info is correctly wiped) and it will be rebuilt a few lines below
by the call to finalize_jump_threads.

However there is this line in-between

  /* If we exposed any new variables, go ahead and put them into
     SSA form now, before we handle jump threading.  This simplifies
     interactions between rewriting of _DECL nodes into SSA form
     and rewriting SSA_NAME nodes into SSA form after block
     duplication and CFG manipulation.  */
  update_ssa (TODO_update_ssa);

and the first thing update_ssa does is

  /* Ensure that the dominance information is up-to-date.  */
  calculate_dominance_info (CDI_DOMINATORS);

but the CFG is still broken so calculate_dominance_info may abort.

Ada testcase attached, to be compiled at O2 -gnatp on x86.  BB 18 has no 
predecessor after VRP2.

-- 
Eric Botcazou

[-- Attachment #2: q.ads --]
[-- Type: text/x-adasrc, Size: 1397 bytes --]

with GNAT.Dynamic_Tables;

package Q is

   procedure Add_Str_To_Name_Buffer (S : String);

   Names_Low_Bound : constant := 300_000_000;
   Names_High_Bound : constant := 399_999_999;
   type Name_Id is range Names_Low_Bound .. Names_High_Bound;
   No_Name : constant Name_Id := Names_Low_Bound;
   function Name_Find return Name_Id;

   type File_Name_Type is new Name_Id;
   No_File : constant File_Name_Type := File_Name_Type (No_Name);

   type Language_Index is new Natural;

   No_Language_Index          : constant Language_Index := 0;
   Ada_Language_Index         : constant Language_Index := 1;
   C_Language_Index           : constant Language_Index := 2;

   Last_Language_Index : Language_Index := No_Language_Index;

   type Spec_Or_Body is (Specification, Body_Part);

   type File_Name_Data is record
      Name : File_Name_Type := No_File;
   end record;

   type File_Names_Data is array (Spec_Or_Body) of File_Name_Data;

   type Unit_Data is record
      Name       : Name_Id;
      File_Names : File_Names_Data;
   end record;

   package Unit_Table is new GNAT.Dynamic_Tables
     (Table_Component_Type => Unit_Data,
      Table_Index_Type     => Natural,
      Table_Low_Bound      => 1,
      Table_Initial        => 100,
      Table_Increment      => 100);

   type Project_Tree_Ref is access all Unit_Table.Instance;

   procedure Set (Suffix : File_Name_Type);

end Q;

[-- Attachment #3: p.ads --]
[-- Type: text/x-adasrc, Size: 98 bytes --]

with Q; use Q;

package P is

   procedure Look_For_Sources (In_Tree : Project_Tree_Ref);

end P;

[-- Attachment #4: p.adb --]
[-- Type: text/x-adasrc, Size: 1152 bytes --]

package body P is

   function Suffix_For (Language : Language_Index) return File_Name_Type is
   begin
      case Language is
         when Ada_Language_Index =>
            Add_Str_To_Name_Buffer (".adb");
         when C_Language_Index =>
            Add_Str_To_Name_Buffer (".c");
         when others =>
            return No_File;
      end case;
      return Name_Find;
   end;

   procedure Look_For_Sources (In_Tree : Project_Tree_Ref) is
      Excluded : File_Name_Type := Name_Find;
      Unit     : Unit_Data;
   begin
      while Excluded /= No_File loop
         For_Each_Unit:
         for Index in Unit_Table.First .. Unit_Table.Last (In_Tree.all)
         loop
            Unit := In_Tree.Table (Index);
            for Kind in Spec_Or_Body'Range loop
               if Unit.File_Names (Kind).Name = Excluded then
                  exit For_Each_Unit;
               end if;
            Excluded := Unit.File_Names (Kind).Name;
            end loop;
         end loop For_Each_Unit;
      end loop;

      for Lang in Ada_Language_Index + 1 .. Last_Language_Index loop
         Set (Suffix_For (Lang));
      end loop;
   end;

end P;

Re: [PATCH] Fix PR14495 (2/2)

[Richard Guenther]

On Mon, 7 Apr 2008, Eric Botcazou wrote:

> > +   /* 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.  */
> 
> I think there is an ordering problem: the CFG is broken at this point (and 
> dominance info is correctly wiped) and it will be rebuilt a few lines below
> by the call to finalize_jump_threads.
> 
> However there is this line in-between
> 
>   /* If we exposed any new variables, go ahead and put them into
>      SSA form now, before we handle jump threading.  This simplifies
>      interactions between rewriting of _DECL nodes into SSA form
>      and rewriting SSA_NAME nodes into SSA form after block
>      duplication and CFG manipulation.  */
>   update_ssa (TODO_update_ssa);
> 
> and the first thing update_ssa does is
> 
>   /* Ensure that the dominance information is up-to-date.  */
>   calculate_dominance_info (CDI_DOMINATORS);
> 
> but the CFG is still broken so calculate_dominance_info may abort.
> 
> Ada testcase attached, to be compiled at O2 -gnatp on x86.  BB 18 has no 
> predecessor after VRP2.

Hrmpf.  I'll have a look later.  Can you open a bugzilla so I don't
forget?

Thanks,
Richard.

Re: [PATCH] Fix PR14495 (2/2)

[Eric Botcazou]

> Hrmpf.  I'll have a look later.  Can you open a bugzilla so I don't
> forget?

It's now PR tree-opt/35869.

-- 
Eric Botcazou