[PATCH] Fix PR14495 (1/2)

[Richard Guenther <rguenther@suse.de>]

This patch from last year fixes one part of PR14495 (VRP cannot
simulate a switch stmt properly).  Namely it teaches VRP the case
of a single executable edge in a switch stmt.  I believe this
it likely to happen (only) with C++ and inlining after exposing
constant propagation opportunities.

It also introduces the find_case_label_index helper which will be
needed in (2/2).

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

Thanks,
Richard.

2008-03-28  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/14495
	* tree-vrp.c (vrp_visit_cond_stmt): Do not handle
	SWITCH_EXPR here ...
	(vrp_visit_switch_stmt): ... but here (new function).
	(find_case_label_index): New helper function.
	(vrp_visit_stmt): Dispatch to vrp_visit_switch_stmt.

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

Index: gcc/tree-vrp.c
===================================================================
*** gcc/tree-vrp.c.orig	2008-03-20 14:51:35.000000000 +0100
--- gcc/tree-vrp.c	2008-03-20 14:56:22.000000000 +0100
*************** vrp_visit_cond_stmt (tree stmt, edge *ta
*** 5300,5310 ****
    bool sop;
  
    *taken_edge_p = NULL;
- 
-   /* FIXME.  Handle SWITCH_EXPRs.  */
-   if (TREE_CODE (stmt) == SWITCH_EXPR)
-     return SSA_PROP_VARYING;
- 
    cond = COND_EXPR_COND (stmt);
  
    if (dump_file && (dump_flags & TDF_DETAILS))
--- 5300,5305 ----
*************** vrp_visit_cond_stmt (tree stmt, edge *ta
*** 5398,5403 ****
--- 5393,5539 ----
  }
  
  
+ /* Searches the case label vector VEC for the index *IDX the CASE_LABEL
+    includes the value VAL.  The search starts at index START_IDX and
+    true is returned if *IDX corresponds to such an index.  False is
+    returned in case VAL hits the default case label and *IDX in this
+    case is the next higher or the next lower case label index.  */
+ 
+ static bool
+ find_case_label_index (tree vec, size_t start_idx, tree val, size_t *idx)
+ {
+   size_t n = TREE_VEC_LENGTH (vec);
+   size_t low, high, i = start_idx;
+ 
+   /* Find case label for minimum of the value range or the next one.  */
+   for (low = start_idx - 1, high = n - 1; high - low > 1; )
+     {
+       tree t;
+       int cmp;
+       i = (high + low) / 2;
+       t = TREE_VEC_ELT (vec, i);
+ 
+       /* Cache the result of comparing CASE_LOW and val.  */
+       cmp = tree_int_cst_compare (CASE_LOW (t), val);
+ 
+       if (cmp > 0)
+         high = i;
+       else
+         low = i;
+ 
+       if (CASE_HIGH (t) == NULL)
+         {
+           /* A singe-valued case label.  */
+           if (cmp == 0)
+ 	    {
+ 	      *idx = i;
+ 	      return true;
+ 	    }
+         }
+       else
+         {
+           /* A case range.  We can only handle integer ranges.  */
+           if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
+ 	    {
+ 	      *idx = i;
+ 	      return true;
+ 	    }
+         }
+     }
+ 
+   *idx = i;
+   return false;
+ }
+ 
+ /* Visit switch statement STMT.  If we can determine which edge
+    will be taken out of STMT's basic block, record it in
+    *TAKEN_EDGE_P and return SSA_PROP_INTERESTING.  Otherwise, return
+    SSA_PROP_VARYING.  */
+ 
+ static enum ssa_prop_result
+ vrp_visit_switch_stmt (tree stmt, edge *taken_edge_p)
+ {
+   tree op, val;
+   value_range_t *vr;
+   size_t i = 0, j = 0, n;
+   tree vec;
+   bool min_take_default, max_take_default;
+ 
+   *taken_edge_p = NULL;
+   op = TREE_OPERAND (stmt, 0);
+   if (TREE_CODE (op) != SSA_NAME)
+     return SSA_PROP_VARYING;
+ 
+   vr = get_value_range (op);
+   if (dump_file && (dump_flags & TDF_DETAILS))
+     {
+       fprintf (dump_file, "\nVisiting switch expression with operand ");
+       print_generic_expr (dump_file, op, 0);
+       fprintf (dump_file, " with known range ");
+       dump_value_range (dump_file, vr);
+       fprintf (dump_file, "\n");
+     }
+ 
+   if (vr->type != VR_RANGE
+       || symbolic_range_p (vr))
+     return SSA_PROP_VARYING;
+ 
+   /* Find the single edge that is taken from the switch expression.  */
+   vec = SWITCH_LABELS (stmt);
+   n = TREE_VEC_LENGTH (vec);
+ 
+   /* Find case label for minimum of the value range or the next one.  */
+   min_take_default = !find_case_label_index (vec, 0, vr->min, &i);
+ 
+   /* Find case label for maximum of the value range or the previous one.  */
+   max_take_default = !find_case_label_index (vec, i, vr->max, &j);
+ 
+   /* Check if we reach the default label only.  */
+   if (j < i)
+     val = TREE_VEC_ELT (vec, n - 1);
+   /* Check if we reach exactly one label and not the default label.  */
+   else if (i == j
+ 	   && !min_take_default
+ 	   && !max_take_default)
+     val = TREE_VEC_ELT (vec, i);
+   else
+     {
+       /* Check if labels with index i to j are all reaching the same label.
+          If we don't hit a single case label only, the default case also has
+          to branch to the same label.  */
+       val = TREE_VEC_ELT (vec, i);
+       if (CASE_LABEL (TREE_VEC_ELT (vec, n - 1)) != CASE_LABEL (val))
+ 	{
+ 	  if (dump_file && (dump_flags & TDF_DETAILS))
+ 	    fprintf (dump_file, "  not a single destination for this "
+ 		     "range\n");
+           return SSA_PROP_VARYING;
+ 	}
+       for (++i; i <= j; ++i)
+         {
+           if (CASE_LABEL (TREE_VEC_ELT (vec, i)) != CASE_LABEL (val))
+ 	    {
+ 	      if (dump_file && (dump_flags & TDF_DETAILS))
+ 		fprintf (dump_file, "  not a single destination for this "
+ 			 "range\n");
+ 	      return SSA_PROP_VARYING;
+ 	    }
+         }
+     }
+ 
+   *taken_edge_p = find_edge (bb_for_stmt (stmt),
+ 			     label_to_block (CASE_LABEL (val)));
+ 
+   if (dump_file && (dump_flags & TDF_DETAILS))
+     {
+       fprintf (dump_file, "  will take edge to ");
+       print_generic_stmt (dump_file, CASE_LABEL (val), 0);
+     }
+ 
+   return SSA_PROP_INTERESTING;
+ }
+ 
+ 
  /* Evaluate statement STMT.  If the statement produces a useful range,
     return SSA_PROP_INTERESTING and record the SSA name with the
     interesting range into *OUTPUT_P.
*************** vrp_visit_stmt (tree stmt, edge *taken_e
*** 5436,5443 ****
  	  || ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
  	return vrp_visit_assignment (stmt, output_p);
      }
!   else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
      return vrp_visit_cond_stmt (stmt, taken_edge_p);
  
    /* All other statements produce nothing of interest for VRP, so mark
       their outputs varying and prevent further simulation.  */
--- 5572,5581 ----
  	  || ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
  	return vrp_visit_assignment (stmt, output_p);
      }
!   else if (TREE_CODE (stmt) == COND_EXPR)
      return vrp_visit_cond_stmt (stmt, taken_edge_p);
+   else if (TREE_CODE (stmt) == SWITCH_EXPR)
+     return vrp_visit_switch_stmt (stmt, taken_edge_p);
  
    /* All other statements produce nothing of interest for VRP, so mark
       their outputs varying and prevent further simulation.  */
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp38.c
===================================================================
*** /dev/null	1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/vrp38.c	2008-03-20 14:56:22.000000000 +0100
***************
*** 0 ****
--- 1,18 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-vrp1" } */
+ 
+ int f(int a) {
+     switch (a & 1) {
+       case 0:
+       case 1: return  3;
+       case 2: return  5;
+       case 3: return  7;
+       case 4: return 11;
+       case 5: return 13;
+       case 6: return 17;
+       case 7: return 19;
+     }
+ }
+ 
+ /* { dg-final { scan-tree-dump "return 3;" "vrp1" } } */
+ /* { dg-final { cleanup-tree-dump "vrp1" } } */