Patchwork [tree-optimization] : Fix for PR/49806

login
register
mail settings
Submitter Kai Tietz
Date Nov. 7, 2011, 10:31 a.m.
Message ID <CAEwic4ZEEG9vG90oet7XMiCXeLT7eyR-3SW0mnOdX-2s_FKZcg@mail.gmail.com>
Download mbox | patch
Permalink /patch/124045/
State New
Headers show

Comments

Kai Tietz - Nov. 7, 2011, 10:31 a.m.
2011/8/1 Richard Guenther <richard.guenther@gmail.com>:
> On Fri, Jul 29, 2011 at 2:07 PM, Kai Tietz <ktietz@redhat.com> wrote:
>> Hello,
>>
>> this patch fixes regression of bug report PR middle-end/49806, which was caused due unhandled type-cast patterns reasoned by boolification of compares and type-cast preserving from/to boolean types.
>>
>>
>> ChangeLog
>>
>> 2011-07-29  Kai Tietz  <ktietz@redhat.com>
>>
>>        PR middle-end/49806
>>        * tree-vrp.c (has_operand_boolean_range): Helper function.
>>        (simplify_truth_ops_using_ranges): Factored out code pattern
>>        into new has_operand_boolean_range function and use it.
>>        (simplify_converted_bool_expr_using_ranges): New function.
>>        (simplify_stmt_using_ranges): Add new simplification function
>>        call.
>>
>>        * gcc.dg/tree-ssa/vrp47.c: Remove dom-dump and adjusted
>>        scan test for vrp result.
>>
>> Bootstrapped and regression tested for all languages (+ Ada, Obj-C++) on host x86_64-pc-linux-gnu.  Ok for apply?
>>
>> Regards,
>> Kai
>>
>> Index: gcc-head/gcc/tree-vrp.c
>> ===================================================================
>> --- gcc-head.orig/gcc/tree-vrp.c
>> +++ gcc-head/gcc/tree-vrp.c
>> @@ -6747,15 +6747,46 @@ varying:
>>   return SSA_PROP_VARYING;
>>  }
>>
>> +/* Returns true, if operand OP has either a one-bit type precision,
>> +   or if value-range of OP is between zero and one.  Otherwise false
>> +   is returned.  The destination of PSOP will be set to true, if a sign-
>> +   overflow on range-check occures.  PSOP might be NULL.  */
>> +static bool
>> +has_operand_boolean_range (tree op, bool *psop)
>> +{
>> +  tree val = NULL;
>> +  value_range_t *vr;
>> +  bool sop = false;
>> +
>> +  if (TYPE_PRECISION (TREE_TYPE (op)) == 1)
>> +    {
>> +      if (psop)
>> +        *psop = false;
>> +      return true;
>> +    }
>> +  if (TREE_CODE (op) != SSA_NAME)
>> +    return false;
>> +  vr = get_value_range (op);
>> +
>> +  val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
>> +  if (!val || !integer_onep (val))
>> +    return false;
>> +
>> +  val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
>> +  if (!val || !integer_onep (val))
>> +    return false;
>
> There is a much simpler and cheaper way to detect these cases.
>
> return vr->type == VR_RANGE
>   &&integer_zerop (vr->min) && integer_onep (vr->max);
>
> and all the strict-overflow stuff with *psop is not necessary.
>
>> +  if (psop)
>> +    *psop = sop;
>> +  return true;
>> +}
>> +
>>  /* Simplify boolean operations if the source is known
>>    to be already a boolean.  */
>>  static bool
>>  simplify_truth_ops_using_ranges (gimple_stmt_iterator *gsi, gimple stmt)
>>  {
>>   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
>> -  tree val = NULL;
>>   tree op0, op1;
>> -  value_range_t *vr;
>>   bool sop = false;
>>   bool need_conversion;
>>
>> @@ -6763,20 +6794,8 @@ simplify_truth_ops_using_ranges (gimple_
>>   gcc_assert (rhs_code == EQ_EXPR || rhs_code == NE_EXPR);
>>
>>   op0 = gimple_assign_rhs1 (stmt);
>> -  if (TYPE_PRECISION (TREE_TYPE (op0)) != 1)
>> -    {
>> -      if (TREE_CODE (op0) != SSA_NAME)
>> -       return false;
>> -      vr = get_value_range (op0);
>> -
>> -      val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
>> -      if (!val || !integer_onep (val))
>> -        return false;
>> -
>> -      val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
>> -      if (!val || !integer_onep (val))
>> -        return false;
>> -    }
>> +  if (!has_operand_boolean_range (op0, &sop))
>
> sounds backward.  We have op_with_constant_singledon_value_range,
> so why not op_with_boolean_range_p instead?
>
>> +    return false;
>>
>>   op1 = gimple_assign_rhs2 (stmt);
>>
>> @@ -6802,17 +6821,8 @@ simplify_truth_ops_using_ranges (gimple_
>>       if (rhs_code == EQ_EXPR)
>>        return false;
>>
>> -      if (TYPE_PRECISION (TREE_TYPE (op1)) != 1)
>> -       {
>> -         vr = get_value_range (op1);
>> -         val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
>> -         if (!val || !integer_onep (val))
>> -           return false;
>> -
>> -         val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
>> -         if (!val || !integer_onep (val))
>> -           return false;
>> -       }
>> +      if (!has_operand_boolean_range (op1, &sop))
>> +        return false;
>>     }
>>
>>   if (sop && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC))
>> @@ -7320,6 +7330,126 @@ simplify_switch_using_ranges (gimple stm
>>   return false;
>>  }
>>
>> +/* Simplify an integeral boolean-typed casted expression for the
>> +   following cases:
>> +   1) (type) ~ (bool) op1 -> op1 ^ 1
>> +   2) (type) ((bool)op1[0..1] & (bool)op2[0..1]) -> op1 & op2
>> +   3) (type) ((bool)op1[0..1] | (bool)op2[0..1]) -> op1 | op2
>> +   4) (type) ((bool)op1[0..1] ^ (bool)op2[0..1]) -> op2 ^ op2
>> +   5) (type) (val[0..1] == 0) -> val ^ 1
>> +   6) (type) (val[0..1] != 0) -> val
>
> 2) to 4) don't look in any way special for 'bool' but should treat all
> kinds of intermediate types.
>
> The description does suggest that (type) ~(bool) op1 -> op1 ^ 1 is
> always valid - it is not, unless op1 has a (sub-)range of [0..1].
>
>> +
>> +   Assuming op1 and op2 hav\EDng type TYPE.  */
>> +
>> +static bool
>> +simplify_converted_bool_expr_using_ranges (gimple_stmt_iterator *gsi, gimple stmt)
>> +{
>> +  tree finaltype, expr, op1, op2 = NULL_TREE;
>> +  gimple def;
>> +  enum tree_code expr_code;
>> +
>> +  finaltype = TREE_TYPE (gimple_assign_lhs (stmt));
>> +  if (!INTEGRAL_TYPE_P (finaltype))
>> +    return false;
>> +  expr = gimple_assign_rhs1 (stmt);
>> +
>> +  /* Check that cast is from a boolean-typed expression.  */
>> +  if (TREE_CODE (TREE_TYPE (expr)) != BOOLEAN_TYPE)
>> +    return false;
>
> No, you should use TYPE_PRECISION (...) == 1 here.
>
>> +  /* Check for assignment.  */
>
> That doesn't provide information that isn't trivially available.  Please
> instead write down the stmt patterns you match using the local
> variables you end up using.
>
>> +  def = SSA_NAME_DEF_STMT (expr);
>> +  if (!is_gimple_assign (def))
>> +    return false;
>> +
>> +  expr_code = gimple_assign_rhs_code (def);
>> +
>> +  op1 = gimple_assign_rhs1 (def);
>> +
>
> excess vertical space.
>
>> +  switch (expr_code)
>> +    {
>> +    /* (TYPE) ~ (bool) X -> X ^ 1, if X has compatible type to final type
>> +       and truth-valued range.  */
>> +    case BIT_NOT_EXPR:
>> +      /* Bitwise not is only a logical-not for 1-bit precisioned
>> +         types.  */
>> +      if (TYPE_PRECISION (TREE_TYPE (expr)) != 1)
>> +        return false;
>> +
>> +      /* Check that we have a type-conversion as operand of bitwise-not.  */
>> +      def = SSA_NAME_DEF_STMT (op1);
>> +      if (!is_gimple_assign (def)
>> +          || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def)))
>> +       return false;
>> +      op1 = gimple_assign_rhs1 (def);
>> +      /* Has X compatible type to final type and truth-valued range?  */
>> +      if (!useless_type_conversion_p (finaltype, TREE_TYPE (op1))
>> +          || !has_operand_boolean_range (op1, NULL))
>> +       return false;
>> +      expr_code = BIT_XOR_EXPR;
>> +      op2 = fold_convert (finaltype, integer_one_node);
>
> build_one_cst (finaltype)
>
>> +      break;
>> +
>> +    /* (TYPE) ((bool) X op (bool) Y) -> X op Y, if X and Y have compatible type
>> +       TYPE and having truth-valued ranges.  */
>> +    case BIT_AND_EXPR:
>> +    case BIT_IOR_EXPR:
>> +    case BIT_XOR_EXPR:
>
> See above - I think restricting these transformation to boolean ranges is
> not necessary.  In fact, see the patch(es) I posted as RFC.
>
>> +      op2 = gimple_assign_rhs2 (def);
>> +
>> +      def = SSA_NAME_DEF_STMT (op1);
>> +      if (!is_gimple_assign (def)
>> +          || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def)))
>> +       return false;
>> +      op1 = gimple_assign_rhs1 (def);
>> +      /* Has X compatible type to final type and truth-valued range?  */
>> +      if (!useless_type_conversion_p (finaltype, TREE_TYPE (op1))
>> +         || !has_operand_boolean_range (op1, NULL))
>> +        return false;
>> +
>> +      def = SSA_NAME_DEF_STMT (op2);
>> +      if (!is_gimple_assign (def)
>> +          || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def)))
>> +       return false;
>> +      op2 = gimple_assign_rhs1 (def);
>> +      /* Has Y compatible type to final type and truth-valued range?  */
>> +      if (!useless_type_conversion_p (finaltype, TREE_TYPE (op2))
>> +          || !has_operand_boolean_range (op2, NULL))
>> +        return false;
>> +      break;
>> +
>> +    /* If X has compatible type to final type and has truth-valued range,
>> +       tranform:
>> +       (TYPE) (X == 0) -> X ^ 1
>> +       (TYPE) (X != 0) -> X  */
>> +    case EQ_EXPR:
>> +    case NE_EXPR:
>> +      /* Is the comparison's second operand zero?  */
>> +      op2 = gimple_assign_rhs2 (def);
>> +      if (!INTEGRAL_TYPE_P (TREE_TYPE (op1))
>> +          || !integer_zerop (op2))
>> +        return false;
>> +      /* Is the type of comparison's first argument compatible to final type
>> +         and has it truth-valued range?  */
>> +      if (!useless_type_conversion_p (finaltype, TREE_TYPE (op1))
>> +         || !has_operand_boolean_range (op1, NULL))
>> +        return false;
>> +
>> +      op2 = NULL_TREE;
>> +      /* X == 0 -> X ^ 1.  */
>> +      if (expr_code == EQ_EXPR)
>> +       op2 = fold_convert (finaltype, integer_one_node);
>
> build_one_cst
>
>> +      expr_code = (!op2 ? SSA_NAME : BIT_XOR_EXPR);
>
> !op2 ? TREE_CODE (op1) : BIT_XOR_EXPR
>
> What about (T) x == 1?  For truthvalue x that is x as well.  (T) x != 1
> is x ^ 1, too.
>
> Btw, why doesn't this get handled in two steps already, first
> changing the comparisons into the respective bit operation and then
> eliminating the conversion?  The first step should be handled by
> simplify_truth_ops_using_ranges already, no?  So doesn't this just
> introduce duplicate code here?
>
> Thanks,
> Richard.

Hello,

This patch fixes regression of bug report PR middle-end/49806, which
are caused by unhandled type-cast patterns reasoned by boolification
of compares and type-cast preserving from/to boolean types.
I addressed in this patch your comment on intial patch.

ChangeLog

2011-11-07  Kai Tietz  <ktietz@redhat.com>

	PR middle-end/49806
	* tree-vrp.c (simplify_converted_bool_expr_using_ranges): New
	function.
	(simplify_stmt_using_ranges): use the new
	simplify_converted_bool_expr_using_ranges function.


 int h(int x, int y)
 {
@@ -36,13 +36,10 @@
    0 or 1.  */
 /* { dg-final { scan-tree-dump-times "\[xy\]\[^ \]* !=" 0 "vrp1" } } */

-/* This one needs more copy propagation that only happens in dom1.  */
-/* { dg-final { scan-tree-dump-times "x\[^ \]* & y" 1 "dom1" } } */
-/* { dg-final { scan-tree-dump-times "x\[^ \]* & y" 1 "vrp1" { xfail
*-*-* } } } */
+/* { dg-final { scan-tree-dump-times "x\[^ \]* & y" 1 "vrp1" } } */

 /* These two are fully simplified by VRP.  */
 /* { dg-final { scan-tree-dump-times "x\[^ \]* \[|\] y" 1 "vrp1" } } */
 /* { dg-final { scan-tree-dump-times "x\[^ \]* \\^ 1" 1 "vrp1" } } */

 /* { dg-final { cleanup-tree-dump "vrp1" } } */
-/* { dg-final { cleanup-tree-dump "dom1" } } */


Bootstrapped and regression tested for all languages (including Ada
and Obj-C++) on host x86_64-unknown-linux-gnu.  Ok for apply?

Regards,
Kai

Patch

Index: tree-vrp.c
===================================================================
--- tree-vrp.c	(revision 180840)
+++ tree-vrp.c	(working copy)
@@ -7246,6 +7246,141 @@ 
   return false;
 }

+/* Simplify an integeral-typed casted expression for the
+   following cases:
+   1) (type) ~ (bool) op1[0..1] -> op1[0..1] ^ 1
+   2) (type) ((type2)op1[0..1] & (type2)op2[0..1]) -> op1 & op2
+   3) (type) ((type2)op1[0..1] | (type2)op2[0..1]) -> op1 | op2
+   4) (type) ((type2)op1[0..1] ^ (type2)op2[0..1]) -> op2 ^ op2
+   5) (type) (val[0..1] == 0) -> val ^ 1
+   6) (type) (val[0..1] != 0) -> val
+
+   Assuming op1 and op2 having type TYPE and for case 2 up to 4 that
+   TYPE2 is an integral one.  */
+
+static bool
+simplify_converted_bool_expr_using_ranges (gimple_stmt_iterator *gsi,
gimple stmt)
+{
+  tree finaltype, expr, op1, op2 = NULL_TREE;
+  gimple def;
+  enum tree_code expr_code;
+  bool is_one_bit_cast = false;
+
+  finaltype = TREE_TYPE (gimple_assign_lhs (stmt));
+  if (!INTEGRAL_TYPE_P (finaltype))
+    return false;
+  expr = gimple_assign_rhs1 (stmt);
+
+  /* Inner type has to be of integral kind.  */
+  if (!INTEGRAL_TYPE_P (TREE_TYPE (expr)))
+    return false;
+
+  /* Check that cast is from a 1-bit integral-typed expression.  */
+  if (TYPE_PRECISION (TREE_TYPE (expr)) == 1)
+    is_one_bit_cast = true;
+
+  def = SSA_NAME_DEF_STMT (expr);
+  if (!is_gimple_assign (def))
+    return false;
+
+  expr_code = gimple_assign_rhs_code (def);
+  op1 = gimple_assign_rhs1 (def);
+
+  switch (expr_code)
+    {
+    /* (TYPE) ~ (bool) X[0..1] -> X ^ 1, if X has compatible type to final type
+       and truth-valued range.  */
+    case BIT_NOT_EXPR:
+      /* Bitwise not is only a logical-not for 1-bit precisioned
+         types.  */
+      if (!is_one_bit_cast)
+        return false;
+
+      /* Check that we have a type-conversion as operand of bitwise-not.  */
+      def = SSA_NAME_DEF_STMT (op1);
+      if (!is_gimple_assign (def)
+          || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def)))
+       return false;
+
+      op1 = gimple_assign_rhs1 (def);
+      /* Has X compatible type to final type and truth-valued range?  */
+      if (!useless_type_conversion_p (finaltype, TREE_TYPE (op1))
+          || !op_with_boolean_value_range_p (op1))
+        return false;
+      expr_code = BIT_XOR_EXPR;
+      op2 = build_one_cst (finaltype);
+      break;
+
+    /* (TYPE) ((type2) X op (ype2) Y) -> X op Y, if X and Y have
compatible type
+       TYPE and having truth-valued ranges.  */
+    case BIT_AND_EXPR:
+    case BIT_IOR_EXPR:
+    case BIT_XOR_EXPR:
+
+      op2 = gimple_assign_rhs2 (def);
+
+      def = SSA_NAME_DEF_STMT (op1);
+      if (!is_gimple_assign (def)
+          || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def)))
+       return false;
+      op1 = gimple_assign_rhs1 (def);
+
+      /* Has X compatible type to final type and truth-valued range?  */
+     if (!useless_type_conversion_p (finaltype, TREE_TYPE (op1))
+         || !op_with_boolean_value_range_p (op1))
+        return false;
+
+     def = SSA_NAME_DEF_STMT (op2);
+     if (!is_gimple_assign (def)
+         || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def)))
+       return false;
+     op2 = gimple_assign_rhs1 (def);
+     /* Has Y compatible type to final type and truth-valued range?  */
+     if (!useless_type_conversion_p (finaltype, TREE_TYPE (op2))
+         || !op_with_boolean_value_range_p (op2))
+       return false;
+     break;
+
+   /* If X has compatible type to final type and has truth-valued range,
+      tranform:
+      (TYPE) (X == 0) -> X ^ 1
+      (TYPE) (X != 0) -> X  */
+   case EQ_EXPR:
+   case NE_EXPR:
+
+     /* Is the comparison integral typed and second operand zero?  */
+     op2 = gimple_assign_rhs2 (def);
+     if (!INTEGRAL_TYPE_P (TREE_TYPE (op1))
+         || (!integer_zerop (op2)
+             && !integer_onep (op2)))
+       return false;
+
+     /* Is the type of comparison's first argument compatible to final type
+        and has it truth-valued range?  */
+     if (!useless_type_conversion_p (finaltype, TREE_TYPE (op1))
+         || !op_with_boolean_value_range_p (op1))
+       return false;
+
+     /* Normalize cases X ==/!= 1 to X !=/== 0 form.  */
+     if (integer_onep (op2))
+       expr_code = (expr_code == NE_EXPR ? EQ_EXPR : NE_EXPR);
+
+     op2 = NULL_TREE;
+     /* X == 0 -> X ^ 1.  */
+     if (expr_code == EQ_EXPR)
+       op2 = build_one_cst (finaltype);
+     expr_code = (!op2 ? TREE_CODE (op1) : BIT_XOR_EXPR);
+
+     break;
+
+   default:
+     return false;
+   }
+  gimple_assign_set_rhs_with_ops (gsi, expr_code, op1, op2);
+  update_stmt (gsi_stmt (*gsi));
+  return true;
+}
+
 /* Simplify an integral conversion from an SSA name in STMT.  */

 static bool
@@ -7479,7 +7614,11 @@ 
 	CASE_CONVERT:
 	  if (TREE_CODE (rhs1) == SSA_NAME
 	      && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
-	    return simplify_conversion_using_ranges (stmt);
+            {
+              if (simplify_conversion_using_ranges (stmt)
+                  || simplify_converted_bool_expr_using_ranges (gsi, stmt))
+                return true;
+            }
 	  break;

 	case FLOAT_EXPR:


ChangeLog testsuite/

2011-11-07  Kai Tietz  <ktietz@redhat.com>

	PR middle-end/49806
	* gcc.dg/tree-ssa/vrp47.c: Adjust testcase.

Index: vrp47.c
===================================================================
--- vrp47.c	(revision 180840)
+++ vrp47.c	(working copy)
@@ -4,8 +4,8 @@ 
    jumps when evaluating an && condition.  VRP is not able to optimize
    this.  */
 /* { dg-do compile { target { ! "mips*-*-* s390*-*-*  avr-*-*
mn10300-*-*" } } } */
-/* { dg-options "-O2 -fdump-tree-vrp1 -fdump-tree-dom1" } */
-/* { dg-options "-O2 -fdump-tree-vrp1 -fdump-tree-dom1 -march=i586" {
target { i?86-*-* && ilp32 } } } */
+/* { dg-options "-O2 -fdump-tree-vrp1" } */
+/* { dg-options "-O2 -fdump-tree-vrp1 -march=i586" { target {
i?86-*-* && ilp32 } } } */