Patchwork [RFA] Eliminate more unnecessary type conversions

login
register
mail settings
Submitter Jeff Law
Date April 26, 2013, 6:53 p.m.
Message ID <517ACD35.9060801@redhat.com>
Download mbox | patch
Permalink /patch/239997/
State New
Headers show

Comments

Jeff Law - April 26, 2013, 6:53 p.m.
So looking at more dumps made it pretty obvious that my previous patch 
to tree-vrp.c to eliminate useless casts to boolean types which fed into 
comparisons could and should be generalized.

Given:

   x1 = (T1) x0;
   if (x1 COND CONST)

If the known value range for x0 fits into T1, then we can rewrite as

   x1 = (T1) x0;
   if (x0 COND (T)CONST)

Which typically makes the first statement dead and may allow further 
simplifications.

Bootstrapped and regression tested on x86_64-unknown-linux-gnu.  OK for 
the trunk?
commit ad290c7270201042bfc3cde1d84c12e639e4bff7
Author: Jeff Law <law@redhat.com>
Date:   Fri Apr 26 12:52:06 2013 -0600

    	* tree-vrp.c (range_fits_type_p): Move to earlier point in file.
            (simplify_cond_using_ranges): Generalize code to simplify
            COND_EXPRs where one argument is a constant and the other
            is an SSA_NAME created by an integral type conversion.
    
    	* gcc.dg/tree-ssa/vrp88.c: New test.
Richard Guenther - April 29, 2013, 7:59 a.m.
On Fri, Apr 26, 2013 at 8:53 PM, Jeff Law <law@redhat.com> wrote:
>
> So looking at more dumps made it pretty obvious that my previous patch to
> tree-vrp.c to eliminate useless casts to boolean types which fed into
> comparisons could and should be generalized.
>
> Given:
>
>   x1 = (T1) x0;
>   if (x1 COND CONST)
>
> If the known value range for x0 fits into T1, then we can rewrite as
>
>   x1 = (T1) x0;
>   if (x0 COND (T)CONST)
>
> Which typically makes the first statement dead and may allow further
> simplifications.
>
> Bootstrapped and regression tested on x86_64-unknown-linux-gnu.  OK for the
> trunk?

Ok.

Thanks,
Richard.

>
> commit ad290c7270201042bfc3cde1d84c12e639e4bff7
> Author: Jeff Law <law@redhat.com>
> Date:   Fri Apr 26 12:52:06 2013 -0600
>
>         * tree-vrp.c (range_fits_type_p): Move to earlier point in file.
>             (simplify_cond_using_ranges): Generalize code to simplify
>             COND_EXPRs where one argument is a constant and the other
>             is an SSA_NAME created by an integral type conversion.
>
>         * gcc.dg/tree-ssa/vrp88.c: New test.
>
> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
> index d06eee6..f9b207c 100644
> --- a/gcc/ChangeLog
> +++ b/gcc/ChangeLog
> @@ -1,3 +1,10 @@
> +2013-04-26  Jeff Law  <law@redhat.com>
> +
> +       * tree-vrp.c (range_fits_type_p): Move to earlier point in file.
> +       (simplify_cond_using_ranges): Generalize code to simplify
> +       COND_EXPRs where one argument is a constant and the other
> +       is an SSA_NAME created by an integral type conversion.
> +
>  2013-04-26  Vladimir Makarov  <vmakarov@redhat.com>
>
>         * rtl.h (struct rtx_def): Add comment for field jump.
> diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
> index bbea9fa..6d7839f 100644
> --- a/gcc/testsuite/ChangeLog
> +++ b/gcc/testsuite/ChangeLog
> @@ -1,3 +1,7 @@
> +2013-04-26  Jeff Law  <law@redhat.com>
> +
> +       * gcc.dg/tree-ssa/vrp88.c: New test.
> +
>  2013-04-26  Jakub Jelinek  <jakub@redhat.com>
>
>         PR go/57045
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp88.c
> b/gcc/testsuite/gcc.dg/tree-ssa/vrp88.c
> new file mode 100644
> index 0000000..e43bdff
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp88.c
> @@ -0,0 +1,39 @@
> +/* { dg-do compile } */
> +
> +/* { dg-options "-O2 -fdump-tree-vrp1-details" } */
> +
> +
> +typedef const struct bitmap_head_def *const_bitmap;
> +typedef unsigned long BITMAP_WORD;
> +typedef struct bitmap_element_def {
> +  struct bitmap_element_def *next;
> +  BITMAP_WORD bits[((128 + (8 * 8 * 1u) - 1) / (8 * 8 * 1u))];
> +} bitmap_element;
> +typedef struct bitmap_head_def {
> +  bitmap_element *first;
> +} bitmap_head;
> +unsigned char
> +bitmap_single_bit_set_p (const_bitmap a)
> +{
> +  unsigned long count = 0;
> +  const bitmap_element *elt;
> +  unsigned ix;
> +  if ((!(a)->first))
> +    return 0;
> +  elt = a->first;
> +  if (elt->next != ((void *)0))
> +    return 0;
> +  for (ix = 0; ix != ((128 + (8 * 8 * 1u) - 1) / (8 * 8 * 1u)); ix++)
> +    {
> +      count += __builtin_popcountl (elt->bits[ix]);
> +      if (count > 1)
> + return 0;
> +    }
> +  return count == 1;
> +}
> +
> +/* Verify that VRP simplified an "if" statement.  */
> +/* { dg-final { scan-tree-dump "Folded into: if.*" "vrp1"} } */
> +/* { dg-final { cleanup-tree-dump "vrp1" } } */
> +
> +
> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> index cb4a09a..07e3e01 100644
> --- a/gcc/tree-vrp.c
> +++ b/gcc/tree-vrp.c
> @@ -8509,6 +8509,57 @@ test_for_singularity (enum tree_code cond_code, tree
> op0,
>    return NULL;
>  }
>
> +/* Return whether the value range *VR fits in an integer type specified
> +   by PRECISION and UNSIGNED_P.  */
> +
> +static bool
> +range_fits_type_p (value_range_t *vr, unsigned precision, bool unsigned_p)
> +{
> +  tree src_type;
> +  unsigned src_precision;
> +  double_int tem;
> +
> +  /* We can only handle integral and pointer types.  */
> +  src_type = TREE_TYPE (vr->min);
> +  if (!INTEGRAL_TYPE_P (src_type)
> +      && !POINTER_TYPE_P (src_type))
> +    return false;
> +
> +  /* An extension is fine unless VR is signed and unsigned_p,
> +     and so is an identity transform.  */
> +  src_precision = TYPE_PRECISION (TREE_TYPE (vr->min));
> +  if ((src_precision < precision
> +       && !(unsigned_p && !TYPE_UNSIGNED (src_type)))
> +      || (src_precision == precision
> +         && TYPE_UNSIGNED (src_type) == unsigned_p))
> +    return true;
> +
> +  /* Now we can only handle ranges with constant bounds.  */
> +  if (vr->type != VR_RANGE
> +      || TREE_CODE (vr->min) != INTEGER_CST
> +      || TREE_CODE (vr->max) != INTEGER_CST)
> +    return false;
> +
> +  /* For sign changes, the MSB of the double_int has to be clear.
> +     An unsigned value with its MSB set cannot be represented by
> +     a signed double_int, while a negative value cannot be represented
> +     by an unsigned double_int.  */
> +  if (TYPE_UNSIGNED (src_type) != unsigned_p
> +      && (TREE_INT_CST_HIGH (vr->min) | TREE_INT_CST_HIGH (vr->max)) < 0)
> +    return false;
> +
> +  /* Then we can perform the conversion on both ends and compare
> +     the result for equality.  */
> +  tem = tree_to_double_int (vr->min).ext (precision, unsigned_p);
> +  if (tree_to_double_int (vr->min) != tem)
> +    return false;
> +  tem = tree_to_double_int (vr->max).ext (precision, unsigned_p);
> +  if (tree_to_double_int (vr->max) != tem)
> +    return false;
> +
> +  return true;
> +}
> +
>  /* Simplify a conditional using a relational operator to an equality
>     test if the range information indicates only one value can satisfy
>     the original conditional.  */
> @@ -8590,18 +8641,15 @@ simplify_cond_using_ranges (gimple stmt)
>         }
>      }
>
> -  /* If we have a comparison of a SSA_NAME boolean against
> -     a constant (which obviously must be [0..1]), see if the
> -     SSA_NAME was set by a type conversion where the source
> -     of the conversion is another SSA_NAME with a range [0..1].
> +  /* If we have a comparison of an SSA_NAME (OP0) against a constant,
> +     see if OP0 was set by a type conversion where the source of
> +     the conversion is another SSA_NAME with a range that fits
> +     into the range of OP0's type.
>
> -     If so, we can replace the SSA_NAME in the comparison with
> -     the RHS of the conversion.  This will often make the type
> -     conversion dead code which DCE will clean up.  */
> +     If so, the conversion is redundant as the earlier SSA_NAME can be
> +     used for the comparison directly if we just massage the constant in
> the
> +     comparison.  */
>    if (TREE_CODE (op0) == SSA_NAME
> -      && (TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
> -         || (INTEGRAL_TYPE_P (TREE_TYPE (op0))
> -             && TYPE_PRECISION (TREE_TYPE (op0)) == 1))
>        && TREE_CODE (op1) == INTEGER_CST)
>      {
>        gimple def_stmt = SSA_NAME_DEF_STMT (op0);
> @@ -8618,8 +8666,9 @@ simplify_cond_using_ranges (gimple stmt)
>           value_range_t *vr = get_value_range (innerop);
>
>           if (range_int_cst_p (vr)
> -             && operand_equal_p (vr->min, integer_zero_node, 0)
> -             && operand_equal_p (vr->max, integer_one_node, 0))
> +             && range_fits_type_p (vr,
> +                                   TYPE_PRECISION (TREE_TYPE (op0)),
> +                                   TYPE_UNSIGNED (TREE_TYPE (op0))))
>             {
>               tree newconst = fold_convert (TREE_TYPE (innerop), op1);
>               gimple_cond_set_lhs (stmt, innerop);
> @@ -8809,57 +8858,6 @@ simplify_conversion_using_ranges (gimple stmt)
>    return true;
>  }
>
> -/* Return whether the value range *VR fits in an integer type specified
> -   by PRECISION and UNSIGNED_P.  */
> -
> -static bool
> -range_fits_type_p (value_range_t *vr, unsigned precision, bool unsigned_p)
> -{
> -  tree src_type;
> -  unsigned src_precision;
> -  double_int tem;
> -
> -  /* We can only handle integral and pointer types.  */
> -  src_type = TREE_TYPE (vr->min);
> -  if (!INTEGRAL_TYPE_P (src_type)
> -      && !POINTER_TYPE_P (src_type))
> -    return false;
> -
> -  /* An extension is fine unless VR is signed and unsigned_p,
> -     and so is an identity transform.  */
> -  src_precision = TYPE_PRECISION (TREE_TYPE (vr->min));
> -  if ((src_precision < precision
> -       && !(unsigned_p && !TYPE_UNSIGNED (src_type)))
> -      || (src_precision == precision
> -         && TYPE_UNSIGNED (src_type) == unsigned_p))
> -    return true;
> -
> -  /* Now we can only handle ranges with constant bounds.  */
> -  if (vr->type != VR_RANGE
> -      || TREE_CODE (vr->min) != INTEGER_CST
> -      || TREE_CODE (vr->max) != INTEGER_CST)
> -    return false;
> -
> -  /* For sign changes, the MSB of the double_int has to be clear.
> -     An unsigned value with its MSB set cannot be represented by
> -     a signed double_int, while a negative value cannot be represented
> -     by an unsigned double_int.  */
> -  if (TYPE_UNSIGNED (src_type) != unsigned_p
> -      && (TREE_INT_CST_HIGH (vr->min) | TREE_INT_CST_HIGH (vr->max)) < 0)
> -    return false;
> -
> -  /* Then we can perform the conversion on both ends and compare
> -     the result for equality.  */
> -  tem = tree_to_double_int (vr->min).ext (precision, unsigned_p);
> -  if (tree_to_double_int (vr->min) != tem)
> -    return false;
> -  tem = tree_to_double_int (vr->max).ext (precision, unsigned_p);
> -  if (tree_to_double_int (vr->max) != tem)
> -    return false;
> -
> -  return true;
> -}
> -
>  /* Simplify a conversion from integral SSA name to float in STMT.  */
>
>  static bool
>

Patch

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index d06eee6..f9b207c 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,10 @@ 
+2013-04-26  Jeff Law  <law@redhat.com>
+
+	* tree-vrp.c (range_fits_type_p): Move to earlier point in file.
+	(simplify_cond_using_ranges): Generalize code to simplify
+	COND_EXPRs where one argument is a constant and the other
+	is an SSA_NAME created by an integral type conversion.
+
 2013-04-26  Vladimir Makarov  <vmakarov@redhat.com>
 
 	* rtl.h (struct rtx_def): Add comment for field jump.
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index bbea9fa..6d7839f 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,7 @@ 
+2013-04-26  Jeff Law  <law@redhat.com>
+
+	* gcc.dg/tree-ssa/vrp88.c: New test.
+
 2013-04-26  Jakub Jelinek  <jakub@redhat.com>
 
 	PR go/57045
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp88.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp88.c
new file mode 100644
index 0000000..e43bdff
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp88.c
@@ -0,0 +1,39 @@ 
+/* { dg-do compile } */
+
+/* { dg-options "-O2 -fdump-tree-vrp1-details" } */
+
+
+typedef const struct bitmap_head_def *const_bitmap;
+typedef unsigned long BITMAP_WORD;
+typedef struct bitmap_element_def {
+  struct bitmap_element_def *next;
+  BITMAP_WORD bits[((128 + (8 * 8 * 1u) - 1) / (8 * 8 * 1u))];
+} bitmap_element;
+typedef struct bitmap_head_def {
+  bitmap_element *first;
+} bitmap_head;
+unsigned char
+bitmap_single_bit_set_p (const_bitmap a)
+{
+  unsigned long count = 0;
+  const bitmap_element *elt;
+  unsigned ix;
+  if ((!(a)->first))
+    return 0;
+  elt = a->first;
+  if (elt->next != ((void *)0))
+    return 0;
+  for (ix = 0; ix != ((128 + (8 * 8 * 1u) - 1) / (8 * 8 * 1u)); ix++)
+    {
+      count += __builtin_popcountl (elt->bits[ix]);
+      if (count > 1)
+ return 0;
+    }
+  return count == 1;
+}
+
+/* Verify that VRP simplified an "if" statement.  */
+/* { dg-final { scan-tree-dump "Folded into: if.*" "vrp1"} } */
+/* { dg-final { cleanup-tree-dump "vrp1" } } */
+
+
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index cb4a09a..07e3e01 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -8509,6 +8509,57 @@  test_for_singularity (enum tree_code cond_code, tree op0,
   return NULL;
 }
 
+/* Return whether the value range *VR fits in an integer type specified
+   by PRECISION and UNSIGNED_P.  */
+
+static bool
+range_fits_type_p (value_range_t *vr, unsigned precision, bool unsigned_p)
+{
+  tree src_type;
+  unsigned src_precision;
+  double_int tem;
+
+  /* We can only handle integral and pointer types.  */
+  src_type = TREE_TYPE (vr->min);
+  if (!INTEGRAL_TYPE_P (src_type)
+      && !POINTER_TYPE_P (src_type))
+    return false;
+
+  /* An extension is fine unless VR is signed and unsigned_p,
+     and so is an identity transform.  */
+  src_precision = TYPE_PRECISION (TREE_TYPE (vr->min));
+  if ((src_precision < precision
+       && !(unsigned_p && !TYPE_UNSIGNED (src_type)))
+      || (src_precision == precision
+	  && TYPE_UNSIGNED (src_type) == unsigned_p))
+    return true;
+
+  /* Now we can only handle ranges with constant bounds.  */
+  if (vr->type != VR_RANGE
+      || TREE_CODE (vr->min) != INTEGER_CST
+      || TREE_CODE (vr->max) != INTEGER_CST)
+    return false;
+
+  /* For sign changes, the MSB of the double_int has to be clear.
+     An unsigned value with its MSB set cannot be represented by
+     a signed double_int, while a negative value cannot be represented
+     by an unsigned double_int.  */
+  if (TYPE_UNSIGNED (src_type) != unsigned_p
+      && (TREE_INT_CST_HIGH (vr->min) | TREE_INT_CST_HIGH (vr->max)) < 0)
+    return false;
+
+  /* Then we can perform the conversion on both ends and compare
+     the result for equality.  */
+  tem = tree_to_double_int (vr->min).ext (precision, unsigned_p);
+  if (tree_to_double_int (vr->min) != tem)
+    return false;
+  tem = tree_to_double_int (vr->max).ext (precision, unsigned_p);
+  if (tree_to_double_int (vr->max) != tem)
+    return false;
+
+  return true;
+}
+
 /* Simplify a conditional using a relational operator to an equality
    test if the range information indicates only one value can satisfy
    the original conditional.  */
@@ -8590,18 +8641,15 @@  simplify_cond_using_ranges (gimple stmt)
 	}
     }
 
-  /* If we have a comparison of a SSA_NAME boolean against
-     a constant (which obviously must be [0..1]), see if the
-     SSA_NAME was set by a type conversion where the source
-     of the conversion is another SSA_NAME with a range [0..1].
+  /* If we have a comparison of an SSA_NAME (OP0) against a constant,
+     see if OP0 was set by a type conversion where the source of
+     the conversion is another SSA_NAME with a range that fits
+     into the range of OP0's type.
 
-     If so, we can replace the SSA_NAME in the comparison with
-     the RHS of the conversion.  This will often make the type
-     conversion dead code which DCE will clean up.  */
+     If so, the conversion is redundant as the earlier SSA_NAME can be
+     used for the comparison directly if we just massage the constant in the
+     comparison.  */
   if (TREE_CODE (op0) == SSA_NAME
-      && (TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
-	  || (INTEGRAL_TYPE_P (TREE_TYPE (op0))
-	      && TYPE_PRECISION (TREE_TYPE (op0)) == 1))
       && TREE_CODE (op1) == INTEGER_CST)
     {
       gimple def_stmt = SSA_NAME_DEF_STMT (op0);
@@ -8618,8 +8666,9 @@  simplify_cond_using_ranges (gimple stmt)
 	  value_range_t *vr = get_value_range (innerop);
 
 	  if (range_int_cst_p (vr)
-	      && operand_equal_p (vr->min, integer_zero_node, 0)
-	      && operand_equal_p (vr->max, integer_one_node, 0))
+	      && range_fits_type_p (vr,
+				    TYPE_PRECISION (TREE_TYPE (op0)),
+				    TYPE_UNSIGNED (TREE_TYPE (op0))))
 	    {
 	      tree newconst = fold_convert (TREE_TYPE (innerop), op1);
 	      gimple_cond_set_lhs (stmt, innerop);
@@ -8809,57 +8858,6 @@  simplify_conversion_using_ranges (gimple stmt)
   return true;
 }
 
-/* Return whether the value range *VR fits in an integer type specified
-   by PRECISION and UNSIGNED_P.  */
-
-static bool
-range_fits_type_p (value_range_t *vr, unsigned precision, bool unsigned_p)
-{
-  tree src_type;
-  unsigned src_precision;
-  double_int tem;
-
-  /* We can only handle integral and pointer types.  */
-  src_type = TREE_TYPE (vr->min);
-  if (!INTEGRAL_TYPE_P (src_type)
-      && !POINTER_TYPE_P (src_type))
-    return false;
-
-  /* An extension is fine unless VR is signed and unsigned_p,
-     and so is an identity transform.  */
-  src_precision = TYPE_PRECISION (TREE_TYPE (vr->min));
-  if ((src_precision < precision
-       && !(unsigned_p && !TYPE_UNSIGNED (src_type)))
-      || (src_precision == precision
-	  && TYPE_UNSIGNED (src_type) == unsigned_p))
-    return true;
-
-  /* Now we can only handle ranges with constant bounds.  */
-  if (vr->type != VR_RANGE
-      || TREE_CODE (vr->min) != INTEGER_CST
-      || TREE_CODE (vr->max) != INTEGER_CST)
-    return false;
-
-  /* For sign changes, the MSB of the double_int has to be clear.
-     An unsigned value with its MSB set cannot be represented by
-     a signed double_int, while a negative value cannot be represented
-     by an unsigned double_int.  */
-  if (TYPE_UNSIGNED (src_type) != unsigned_p
-      && (TREE_INT_CST_HIGH (vr->min) | TREE_INT_CST_HIGH (vr->max)) < 0)
-    return false;
-
-  /* Then we can perform the conversion on both ends and compare
-     the result for equality.  */
-  tem = tree_to_double_int (vr->min).ext (precision, unsigned_p);
-  if (tree_to_double_int (vr->min) != tem)
-    return false;
-  tem = tree_to_double_int (vr->max).ext (precision, unsigned_p);
-  if (tree_to_double_int (vr->max) != tem)
-    return false;
-
-  return true;
-}
-
 /* Simplify a conversion from integral SSA name to float in STMT.  */
 
 static bool