[PATCH] Fix PR14495 (1/2)

[PATCH] Fix PR14495 (1/2)

[Richard Guenther]

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" } } */

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

[Diego Novillo]

On Fri, Mar 28, 2008 at 10:52, Richard Guenther <rguenther@suse.de> wrote:

>  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.

OK.

Diego.

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

[Rafael Espindola]

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

I am trying to port this to tuples and I find it a bit hard to understand.

You test for the fact that the returned idx is < start_idx. Since all
assignments to idx are "*idx = i", this is only possible if "i <
start_idx". "i" is assigned "start_idx" initially and "(high + low)/2"
in the loop. Since "low >= start_idx - 1", "(high + low)/2 <
start_idx" is only possible if "high = start_idx and low = start_idx -
1". This cannot happen since the loop condition is "high -low > 1".

Just to make sure I am not getting the math wrong, I added "gcc_assert
(i >= start_idx)" in all returns. The code is bootstrapping at stage3
now :-)

Cheers,
-- 
Rafael Avila de Espindola

Google Ireland Ltd.
Gordon House
Barrow Street
Dublin 4
Ireland

Registered in Dublin, Ireland
Registration Number: 368047

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

[Richard Guenther]

On Mon, 14 Apr 2008, Rafael Espindola wrote:

> >  It also introduces the find_case_label_index helper which will be
> >  needed in (2/2).
> 
> I am trying to port this to tuples and I find it a bit hard to understand.
> 
> You test for the fact that the returned idx is < start_idx. Since all
> assignments to idx are "*idx = i", this is only possible if "i <
> start_idx". "i" is assigned "start_idx" initially and "(high + low)/2"
> in the loop. Since "low >= start_idx - 1", "(high + low)/2 <
> start_idx" is only possible if "high = start_idx and low = start_idx -
> 1". This cannot happen since the loop condition is "high -low > 1".

Quite possible - I more or less copied this routine from
find_case_label_for_value (which didn't exactly suit my needs).
Btw. which check do you exactly mean?  The

  /* Check if we reach the default label only.  */
  if (j < i)
    val = TREE_VEC_ELT (vec, n - 1);

one?  If that cannot be reached then something is either bogus or
missing optimizations.

> Just to make sure I am not getting the math wrong, I added "gcc_assert
> (i >= start_idx)" in all returns. The code is bootstrapping at stage3
> now :-)

Richard.

-- 
Richard Guenther <rguenther@suse.de>
Novell / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746 - GF: Markus Rex

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

[Rafael Espindola]

>  Quite possible - I more or less copied this routine from
>  find_case_label_for_value (which didn't exactly suit my needs).
>  Btw. which check do you exactly mean?  The
>
>
>   /* Check if we reach the default label only.  */
>   if (j < i)
>     val = TREE_VEC_ELT (vec, n - 1);
>
>  one?  If that cannot be reached then something is either bogus or
>  missing optimizations.

Yes, that the one.

Can you better describe what find_case_label_index is supposed to do
(do you have an example?)? I might be able to fix it.

>  Richard.
>
>  --
>
> Richard Guenther <rguenther@suse.de>
>  Novell / SUSE Labs
>  SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746 - GF: Markus Rex
>

Cheers,
-- 
Rafael Avila de Espindola

Google Ireland Ltd.
Gordon House
Barrow Street
Dublin 4
Ireland

Registered in Dublin, Ireland
Registration Number: 368047

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

[Richard Guenther]

On Tue, 15 Apr 2008, Rafael Espindola wrote:

> >  Quite possible - I more or less copied this routine from
> >  find_case_label_for_value (which didn't exactly suit my needs).
> >  Btw. which check do you exactly mean?  The
> >
> >
> >   /* Check if we reach the default label only.  */
> >   if (j < i)
> >     val = TREE_VEC_ELT (vec, n - 1);
> >
> >  one?  If that cannot be reached then something is either bogus or
> >  missing optimizations.
> 
> Yes, that the one.
> 
> Can you better describe what find_case_label_index is supposed to do
> (do you have an example?)? I might be able to fix it.

find_case_label_index is supposed to search for the index of the case
label in the case label vector that is supposed to handle the given
value.  start_idx is only an optimization as we know the vector is
sorted (in VRP we query for two label indices where we know the second
is always after (or the same as) the first).

So what we do in vrp_visit_switch_stmt is that we find the case label
indices for both ends of the value range [min, max] where we of course
need to handle the case of min or max hitting the default case label.

I belive j < i happens if both min and max reach the default label and
there is no case label for any value in the range [min, max].  But as
that patch was developed more than a year ago I don't remember exactly
(though it should be easy to create some testcases).

Richard.

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

[Rafael Espindola]

>  find_case_label_index is supposed to search for the index of the case
>  label in the case label vector that is supposed to handle the given
>  value.  start_idx is only an optimization as we know the vector is
>  sorted (in VRP we query for two label indices where we know the second
>  is always after (or the same as) the first).
>
>  So what we do in vrp_visit_switch_stmt is that we find the case label
>  indices for both ends of the value range [min, max] where we of course
>  need to handle the case of min or max hitting the default case label.
>
>  I belive j < i happens if both min and max reach the default label and
>  there is no case label for any value in the range [min, max].  But as
>  that patch was developed more than a year ago I don't remember exactly
>  (though it should be easy to create some testcases).


Thanks for the explanation. The attached patch is a draft of a fix to
find_case_label_index. Since its interface is a bit complex, I added a
wrapper find_case_label_range. Do you like the patch? I am testing it
and will should send you the final version today.

>  Richard.
>


Cheers,
-- 
Rafael Avila de Espindola

Google Ireland Ltd.
Gordon House
Barrow Street
Dublin 4
Ireland

Registered in Dublin, Ireland
Registration Number: 368047

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

[Rafael Espindola]

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

>  Thanks for the explanation. The attached patch is a draft of a fix to
>  find_case_label_index. Since its interface is a bit complex, I added a
>  wrapper find_case_label_range. Do you like the patch? I am testing it
>  and will should send you the final version today.

Now with the patch ....

Cheers,
-- 
Rafael Avila de Espindola

Google Ireland Ltd.
Gordon House
Barrow Street
Dublin 4
Ireland

Registered in Dublin, Ireland
Registration Number: 368047

[-- Attachment #2: fix.patch --]
[-- Type: application/octet-stream, Size: 7271 bytes --]

Index: gcc/tree-vrp.c
===================================================================
--- gcc/tree-vrp.c	(revision 134333)
+++ gcc/tree-vrp.c	(working copy)
@@ -5529,58 +5529,121 @@
 }
 
 
-/* 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.  */
+/* Searches the case label vector VEC for the index *IDX of the CASE_LABEL
+   that includes the value VAL.  The search is restricted to the range
+   [START_IDX, n - 2] where n is the size of VEC (n - 1 is the default label).
 
+   If there is a CASE_LABEL for VAL, its index is placed in IDX and true is
+   returned.
+
+   If there is no CASE_LABEL for VAL and the is one that is larger than VAL,
+   it is placed in IDX and false is returned.
+
+   If VAL is larger than any CASE_LABEL, n - 1 is placed on IDX and false is
+   returned. */
+
 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;
+  size_t low, high;
 
-  /* Find case label for minimum of the value range or the next one.  */
-  for (low = start_idx - 1, high = n - 1; high - low > 1; )
+  /* Find case label for minimum of the value range or the next one.
+     At each iteration we are searching in [low, high - 1]. */
+
+  for (low = start_idx, high = n - 1; high != low; )
     {
       tree t;
       int cmp;
-      i = (high + low) / 2;
+      /* Note that i != high, so we never ask for n - 1 */
+      size_t 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)
+      if (cmp == 0)
+	{
+	  /* Ranges cannot be empty (true?)*/
+	  gcc_assert(!CASE_HIGH (t)
+		     || tree_int_cst_compare (CASE_HIGH(t),
+					      CASE_LOW (t)) >= 0);
+	  *idx = i;
+	  return true;
+	}
+      else if (cmp > 0)
         high = i;
       else
-        low = i;
-
-      if (CASE_HIGH (t) == NULL)
-        {
-          /* A singe-valued case label.  */
-          if (cmp == 0)
+	{
+	  low = i + 1;
+	  if (CASE_HIGH (t) != NULL
+	      && tree_int_cst_compare (CASE_HIGH (t), val) >= 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;
+  *idx = high;
   return false;
 }
 
+/* Return true if the default label is not needed */
+static bool
+find_case_label_range (tree vec, tree min, tree max, size_t *min_idx, size_t *max_idx)
+{
+  size_t i, j;
+  bool min_take_default = !find_case_label_index (vec, 0, min, &i);
+  bool max_take_default = !find_case_label_index (vec, i, max, &j);
+
+  if (i == j
+      && !min_take_default
+      && !max_take_default)
+    {
+      *min_idx = i;
+      *max_idx = j;
+      return true;
+    }
+  else if (i == j
+	   && min_take_default
+	   && max_take_default)
+    {
+      *min_idx = 1;
+      *max_idx = 0;
+      return false;
+    }
+  else
+    {
+      bool take_default = min_take_default || max_take_default;
+      tree low, high;
+      size_t k;
+
+      if (max_take_default)
+	j--;
+
+      /* If the case label range is continuous, we do not need
+	 the default case label.  Verify that.  */
+      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));
+	}
+
+      return !take_default;
+    }
+}
+
 /* 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
@@ -5593,7 +5656,7 @@
   value_range_t *vr;
   size_t i = 0, j = 0, n;
   tree vec;
-  bool min_take_default, max_take_default;
+  bool take_default;
 
   *taken_edge_p = NULL;
   op = TREE_OPERAND (stmt, 0);
@@ -5618,27 +5681,23 @@
   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);
+  take_default = !find_case_label_range (vec, vr->min, vr->max, &i, &j);
 
-  /* 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);
+  /* Check if the range spans no CASE_LABEL. If so, we only reach the default
+     label */
+  if (i > j)
+    {
+      gcc_assert (take_default);
+      val = TREE_VEC_ELT (vec, n - 1);
+    }
   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.  */
+      /* Check if labels with index i to j and maybe the default label
+	 are all reaching the same label.  */
+
       val = TREE_VEC_ELT (vec, i);
-      if (CASE_LABEL (TREE_VEC_ELT (vec, n - 1)) != CASE_LABEL (val))
+      if (take_default
+	  && 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 "
@@ -6323,33 +6382,8 @@
   /* 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);
+  take_default = !find_case_label_range (vec, vr->min, vr->max, &i, &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

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

[Richard Guenther]

On Wed, 16 Apr 2008, Rafael Espindola wrote:

> >  Thanks for the explanation. The attached patch is a draft of a fix to
> >  find_case_label_index. Since its interface is a bit complex, I added a
> >  wrapper find_case_label_range. Do you like the patch? I am testing it
> >  and will should send you the final version today.
> 
> Now with the patch ....

Comments inline

Index: gcc/tree-vrp.c
===================================================================
--- gcc/tree-vrp.c	(revision 134333)
+++ gcc/tree-vrp.c	(working copy)
@@ -5529,58 +5529,121 @@
 }
 
 
-/* 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.  */
+/* Searches the case label vector VEC for the index *IDX of the CASE_LABEL
+   that includes the value VAL.  The search is restricted to the range
+   [START_IDX, n - 2] where n is the size of VEC (n - 1 is the default label).
 
+   If there is a CASE_LABEL for VAL, its index is placed in IDX and true is
+   returned.
+
+   If there is no CASE_LABEL for VAL and the is one that is larger than VAL,
+   it is placed in IDX and false is returned.
+
+   If VAL is larger than any CASE_LABEL, n - 1 is placed on IDX and false is
+   returned. */
+
 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;
+  size_t low, high;
 
-  /* Find case label for minimum of the value range or the next one.  */
-  for (low = start_idx - 1, high = n - 1; high - low > 1; )
+  /* Find case label for minimum of the value range or the next one.
+     At each iteration we are searching in [low, high - 1]. */
+
+  for (low = start_idx, high = n - 1; high != low; )
     {
       tree t;
       int cmp;
-      i = (high + low) / 2;
+      /* Note that i != high, so we never ask for n - 1 */

fullstop and extra space before */ required

+      size_t 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)
+      if (cmp == 0)
+	{
+	  /* Ranges cannot be empty (true?)*/

that's true (the assert imho is superfluous)

+	  gcc_assert(!CASE_HIGH (t)
+		     || tree_int_cst_compare (CASE_HIGH(t),
+					      CASE_LOW (t)) >= 0);
+	  *idx = i;
+	  return true;
+	}
+      else if (cmp > 0)
         high = i;
       else
-        low = i;
-
-      if (CASE_HIGH (t) == NULL)
-        {
-          /* A singe-valued case label.  */
-          if (cmp == 0)
+	{
+	  low = i + 1;
+	  if (CASE_HIGH (t) != NULL
+	      && tree_int_cst_compare (CASE_HIGH (t), val) >= 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;
+  *idx = high;
   return false;
 }

+/* Return true if the default label is not needed */

All parameters need documenting, especially ...

+static bool
+find_case_label_range (tree vec, tree min, tree max, size_t *min_idx, size_t *max_idx)
+{
+  size_t i, j;
+  bool min_take_default = !find_case_label_index (vec, 0, min, &i);
+  bool max_take_default = !find_case_label_index (vec, i, max, &j);
+
+  if (i == j
+      && !min_take_default
+      && !max_take_default)
+    {
+      *min_idx = i;
+      *max_idx = j;
+      return true;
+    }
+  else if (i == j
+	   && min_take_default
+	   && max_take_default)
+    {
+      *min_idx = 1;
+      *max_idx = 0;

... this looks weird to me.  Why not store i and j as well
(and merge it with the previous case - IMHO both need a
short comment, /* Exactly one case label reached.  */
and /* Only the default case label reached.  */).  Doesn't
your rewrite guarantee that you can simply do

 /* If we reach exactly one case label.  */
 if (i == j)
   {
     gcc_assert (min_take_default == max_take_default);
     *min_idx = i;
     *max_idx = j;
     return !min_take_default;
   }

?

Otherwise the patch looks fine.

Thanks,
Richard.


+      return false;
+    }
+  else
+    {
+      bool take_default = min_take_default || max_take_default;
+      tree low, high;
+      size_t k;
+
+      if (max_take_default)
+	j--;
+
+      /* If the case label range is continuous, we do not need
+	 the default case label.  Verify that.  */
+      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));
+	}
+
+      return !take_default;
+    }
+}
+
 /* 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
@@ -5593,7 +5656,7 @@
   value_range_t *vr;
   size_t i = 0, j = 0, n;
   tree vec;
-  bool min_take_default, max_take_default;
+  bool take_default;
 
   *taken_edge_p = NULL;
   op = TREE_OPERAND (stmt, 0);
@@ -5618,27 +5681,23 @@
   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);
+  take_default = !find_case_label_range (vec, vr->min, vr->max, &i, &j);
 
-  /* 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);
+  /* Check if the range spans no CASE_LABEL. If so, we only reach the default
+     label */
+  if (i > j)
+    {
+      gcc_assert (take_default);
+      val = TREE_VEC_ELT (vec, n - 1);
+    }
   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.  */
+      /* Check if labels with index i to j and maybe the default label
+	 are all reaching the same label.  */
+
       val = TREE_VEC_ELT (vec, i);
-      if (CASE_LABEL (TREE_VEC_ELT (vec, n - 1)) != CASE_LABEL (val))
+      if (take_default
+	  && 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 "
@@ -6323,33 +6382,8 @@
   /* 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);
+  take_default = !find_case_label_range (vec, vr->min, vr->max, &i, &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

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

[Rafael Espindola]

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

>  +  size_t i, j;
>  +  bool min_take_default = !find_case_label_index (vec, 0, min, &i);
>  +  bool max_take_default = !find_case_label_index (vec, i, max, &j);
>  +
>
> +  if (i == j
>  +      && !min_take_default
>  +      && !max_take_default)
>  +    {
>  +      *min_idx = i;
>  +      *max_idx = j;
>  +      return true;
>  +    }
>
> +  else if (i == j
>  +          && min_take_default
>  +          && max_take_default)
>  +    {
>  +      *min_idx = 1;
>  +      *max_idx = 0;
>
>  ... this looks weird to me.  Why not store i and j as well
>  (and merge it with the previous case - IMHO both need a
>  short comment, /* Exactly one case label reached.  */
>  and /* Only the default case label reached.  */).  Doesn't
>  your rewrite guarantee that you can simply do
>
>   /* If we reach exactly one case label.  */
>   if (i == j)
>    {
>      gcc_assert (min_take_default == max_take_default);
>      *min_idx = i;
>      *max_idx = j;
>      return !min_take_default;
>    }
>
>  ?

We must return an empty range if we use only the default statement.

>  Otherwise the patch looks fine.


I have updated the patch with your comments and some simplifications.
It is currently bootstrapping. OK if it has no regressions?

>  Thanks,
>  Richard.

Cheers,
-- 
Rafael Avila de Espindola

Google Ireland Ltd.
Gordon House
Barrow Street
Dublin 4
Ireland

Registered in Dublin, Ireland
Registration Number: 368047

[-- Attachment #2: vrp.patch --]
[-- Type: application/octet-stream, Size: 7454 bytes --]

Index: gcc/tree-vrp.c
===================================================================
--- gcc/tree-vrp.c	(revision 134344)
+++ gcc/tree-vrp.c	(working copy)
@@ -5528,59 +5528,120 @@
   return (*taken_edge_p) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
 }
 
+/* Searches the case label vector VEC for the index *IDX of the CASE_LABEL
+   that includes the value VAL.  The search is restricted to the range
+   [START_IDX, n - 2] where n is the size of VEC (n - 1 is the default label).
 
-/* 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.  */
+   If there is a CASE_LABEL for VAL, its index is placed in IDX and true is
+   returned.
 
+   If there is no CASE_LABEL for VAL and the is one that is larger than VAL,
+   it is placed in IDX and false is returned.
+
+   If VAL is larger than any CASE_LABEL, n - 1 is placed on IDX and false is
+   returned. */
+
 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;
+  size_t low, high;
 
-  /* Find case label for minimum of the value range or the next one.  */
-  for (low = start_idx - 1, high = n - 1; high - low > 1; )
+  /* Find case label for minimum of the value range or the next one.
+     At each iteration we are searching in [low, high - 1]. */
+
+  for (low = start_idx, high = n - 1; high != low; )
     {
       tree t;
       int cmp;
-      i = (high + low) / 2;
+      /* Note that i != high, so we never ask for n - 1. */
+      size_t 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)
+      if (cmp == 0)
+	{
+	  /* Ranges cannot be empty. */
+	  *idx = i;
+	  return true;
+	}
+      else if (cmp > 0)
         high = i;
       else
-        low = i;
-
-      if (CASE_HIGH (t) == NULL)
-        {
-          /* A singe-valued case label.  */
-          if (cmp == 0)
+	{
+	  low = i + 1;
+	  if (CASE_HIGH (t) != NULL
+	      && tree_int_cst_compare (CASE_HIGH (t), val) >= 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;
+  *idx = high;
   return false;
 }
 
+/* Searches the case label vector VEC for the range of CASE_LABELs that is used
+   for values between MIN and MAX. The first index is placed in MIN_IDX. The
+   last index is placed in MAX_IDX. If the range of CASE_LABELs is empty
+   then MAX_IDX < MIN_IDX.
+   Returns true if the default label is not needed. */
+
+static bool
+find_case_label_range (tree vec, tree min, tree max, size_t *min_idx, size_t *max_idx)
+{
+  size_t i, j;
+  bool min_take_default = !find_case_label_index (vec, 0, min, &i);
+  bool max_take_default = !find_case_label_index (vec, i, max, &j);
+
+  if (i == j
+      && min_take_default
+      && max_take_default)
+    {
+      /* Only the default case label reached. 
+         Return an empty range. */
+      *min_idx = 1;
+      *max_idx = 0;
+      return false;
+    }
+  else
+    {
+      bool take_default = min_take_default || max_take_default;
+      tree low, high;
+      size_t k;
+
+      if (max_take_default)
+	j--;
+
+      /* If the case label range is continuous, we do not need
+	 the default case label.  Verify that.  */
+      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));
+	}
+
+      *min_idx = i;
+      *max_idx = j;
+
+      return !take_default;
+    }
+}
+
 /* 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
@@ -5593,7 +5654,7 @@
   value_range_t *vr;
   size_t i = 0, j = 0, n;
   tree vec;
-  bool min_take_default, max_take_default;
+  bool take_default;
 
   *taken_edge_p = NULL;
   op = TREE_OPERAND (stmt, 0);
@@ -5618,27 +5679,23 @@
   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);
+  take_default = !find_case_label_range (vec, vr->min, vr->max, &i, &j);
 
-  /* 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.  */
+  /* Check if the range spans no CASE_LABEL. If so, we only reach the default
+     label */
   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);
+    {
+      gcc_assert (take_default);
+      val = TREE_VEC_ELT (vec, n - 1);
+    }
   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.  */
+      /* Check if labels with index i to j and maybe the default label
+	 are all reaching the same label.  */
+
       val = TREE_VEC_ELT (vec, i);
-      if (CASE_LABEL (TREE_VEC_ELT (vec, n - 1)) != CASE_LABEL (val))
+      if (take_default
+	  && 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 "
@@ -6323,33 +6380,8 @@
   /* 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);
+  take_default = !find_case_label_range (vec, vr->min, vr->max, &i, &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

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

[Richard Guenther]

On Wed, 16 Apr 2008, Rafael Espindola wrote:

> I have updated the patch with your comments and some simplifications.
> It is currently bootstrapping. OK if it has no regressions?

-    }
-
   /* Bail out if this is just all edges taken.  */
   if (i == 0
       && j == n - 2
       && take_default)
    return;

does this need adjustment now as n - 1 is returned if j takes the
default?  Thus

    if (i == 0
       && j >= n - 2
       && take_default)
    return;

?

Otherwise this is ok.

Thanks,
Richard.

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

[Rafael Espindola]

2008/4/16 Richard Guenther <rguenther@suse.de>:
> -    }
>  -
>    /* Bail out if this is just all edges taken.  */
>    if (i == 0
>        && j == n - 2
>        && take_default)
>     return;
>
>  does this need adjustment now as n - 1 is returned if j takes the
>  default?  Thus

That is done in find_case_label_range:

+      if (max_take_default)
+       j--;


>  Thanks,
>  Richard.
>

Cheers,
-- 
Rafael Avila de Espindola

Google Ireland Ltd.
Gordon House
Barrow Street
Dublin 4
Ireland

Registered in Dublin, Ireland
Registration Number: 368047