Patchwork [tree-optimization] : Avoid !=/== 0/1 comparisons for boolean-typed argument

login
register
mail settings
Submitter Kai Tietz
Date Aug. 2, 2011, 10:17 a.m.
Message ID <CAEwic4ZWdoL0atU0jaXhzE=Uey6c8M8U7HbUzUZ1qvhj91dMsg@mail.gmail.com>
Download mbox | patch
Permalink /patch/107882/
State New
Headers show

Comments

Kai Tietz - Aug. 2, 2011, 10:17 a.m.
Hello,

this patch removes in forward-propagation useless comparisons X != 0
and X != ~0 for boolean-typed X.  For one-bit precision typed X we
simplifiy X == 0 (and X != ~0) to ~X, and for X != 0 (and X == ~0) to
X.
For none one-bit precisione typed X, we simplify here X == 0 -> X ^ 1,
and for X != 0 -> X.  We can do this as even for Ada - which has only
boolean-type with none-one-bit precision - the truth-value is one.

Additionally this patch changes for function
forward_propagate_comparison the meaning of true-result.  As this
result wasn't used and it is benefitial to use this propagation also
in second loop in function ssa_forward_propagate_and_combine, it
returns true iff statement was altered.  Additionally this function
handles now the boolean-typed simplifications.

For the hunk in gimple.c for function canonicalize_cond_expr_cond:
This change seems to show no real effect, but IMHO it makes sense to
add here the check for cast from boolean-type to be consitant.

ChangeLog

2011-08-02  Kai Tietz  <ktietz@redhat.com>

        * gimple.c (canonicalize_cond_expr_cond): Handle cast from boolean-type.
        * tree-ssa-forwprop.c (forward_propagate_comparison): Return
true iff statement was modified.
        Handle boolean-typed simplification for EQ_EXPR/NE_EXPR.
        (ssa_forward_propagate_and_combine): Call
forward_propagate_comparison for comparisons.

2011-08-02  Kai Tietz  <ktietz@redhat.com>

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


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

Regards,
Kai
Richard Guenther - Aug. 2, 2011, 11:06 a.m.
On Tue, Aug 2, 2011 at 12:17 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
> Hello,
>
> this patch removes in forward-propagation useless comparisons X != 0
> and X != ~0 for boolean-typed X.  For one-bit precision typed X we
> simplifiy X == 0 (and X != ~0) to ~X, and for X != 0 (and X == ~0) to
> X.
> For none one-bit precisione typed X, we simplify here X == 0 -> X ^ 1,
> and for X != 0 -> X.  We can do this as even for Ada - which has only
> boolean-type with none-one-bit precision - the truth-value is one.

This isn't a simplification but a canonicalization and thus should be
done by fold_stmt instead (we are not propagating anything after all).
In fact, fold_stmt should do parts of this already by means of its
canonicalizations via fold.

> Additionally this patch changes for function
> forward_propagate_comparison the meaning of true-result.  As this
> result wasn't used and it is benefitial to use this propagation also

which is a bug - for a true return value we need to set cfg_changed to true.

> in second loop in function ssa_forward_propagate_and_combine, it
> returns true iff statement was altered.  Additionally this function
> handles now the boolean-typed simplifications.

why call it twice?  How should that be "beneficial"?  I think that
forward_propagate_into_comparison should instead fold the changed
statement.

> For the hunk in gimple.c for function canonicalize_cond_expr_cond:
> This change seems to show no real effect, but IMHO it makes sense to
> add here the check for cast from boolean-type to be consitant.

Probably yes.

Thanks,
Richard.

> ChangeLog
>
> 2011-08-02  Kai Tietz  <ktietz@redhat.com>
>
>        * gimple.c (canonicalize_cond_expr_cond): Handle cast from boolean-type.
>        * tree-ssa-forwprop.c (forward_propagate_comparison): Return
> true iff statement was modified.
>        Handle boolean-typed simplification for EQ_EXPR/NE_EXPR.
>        (ssa_forward_propagate_and_combine): Call
> forward_propagate_comparison for comparisons.
>
> 2011-08-02  Kai Tietz  <ktietz@redhat.com>
>
>        * gcc.dg/tree-ssa/forwprop-9.c: New testcase.
>
>
> Bootstrapped and regression tested for all languages (including Ada
> and Obj-C++) on host x86_64-pc-linux-gnu.  Ok for apply?
>
> Regards,
> Kai
>
> Index: gcc/gcc/gimple.c
> ===================================================================
> --- gcc.orig/gcc/gimple.c
> +++ gcc/gcc/gimple.c
> @@ -3160,7 +3160,9 @@ canonicalize_cond_expr_cond (tree t)
>  {
>   /* Strip conversions around boolean operations.  */
>   if (CONVERT_EXPR_P (t)
> -      && truth_value_p (TREE_CODE (TREE_OPERAND (t, 0))))
> +      && (truth_value_p (TREE_CODE (TREE_OPERAND (t, 0)))
> +          || TREE_CODE (TREE_TYPE (TREE_OPERAND (t, 0)))
> +            == BOOLEAN_TYPE))
>     t = TREE_OPERAND (t, 0);
>
>   /* For !x use x == 0.  */
> Index: gcc/gcc/tree-ssa-forwprop.c
> ===================================================================
> --- gcc.orig/gcc/tree-ssa-forwprop.c
> +++ gcc/gcc/tree-ssa-forwprop.c
> @@ -1114,7 +1114,18 @@ forward_propagate_addr_expr (tree name,
>      a_1 = (T')cond_1
>      a_1 = !cond_1
>      a_1 = cond_1 != 0
> -   Returns true if stmt is now unused.  */
> +     For boolean typed comparisons with type-precision of one
> +     X == 0 -> ~X
> +     X != ~0 -> ~X
> +     X != 0 -> X
> +     X == ~0 -> X
> +     For boolean typed comparison with none one-bit type-precision
> +     we can assume that truth-value is one, and false-value is zero.
> +     X == 1 -> X
> +     X != 1 -> X ^ 1
> +     X == 0 -> X ^ 1
> +     X != 0 -> X
> +   Returns true if stmt is changed.  */
>
>  static bool
>  forward_propagate_comparison (gimple stmt)
> @@ -1123,9 +1134,48 @@ forward_propagate_comparison (gimple stm
>   gimple use_stmt;
>   tree tmp = NULL_TREE;
>   gimple_stmt_iterator gsi;
> -  enum tree_code code;
> +  enum tree_code code = gimple_assign_rhs_code (stmt);
>   tree lhs;
>
> +  /* Simplify X != 0 -> X and X == 0 -> ~X, if X is boolean-typed
> +     and X has a compatible type to the comparison-expression.  */
> +  if ((code == EQ_EXPR || code == NE_EXPR)
> +      && TREE_CODE (TREE_TYPE (gimple_assign_rhs1 (stmt))) == BOOLEAN_TYPE
> +      && TREE_CODE (gimple_assign_rhs2 (stmt)) == INTEGER_CST
> +      /* A comparison is always boolean-typed, but there might be
> +        differences in mode-size.  */
> +      && useless_type_conversion_p (TREE_TYPE (name),
> +                                   TREE_TYPE (gimple_assign_rhs1 (stmt))))
> +    {
> +      tree tmp2;
> +
> +      /* Normalize to reduce cases.  */
> +      if (!integer_zerop (gimple_assign_rhs2 (stmt)))
> +        code = (code == EQ_EXPR ? NE_EXPR : EQ_EXPR);
> +      tmp = gimple_assign_rhs1 (stmt);
> +      tmp2 = NULL_TREE;
> +
> +      /* Convert X == 0 -> ~X for 1-bit precision boolean-type.
> +        Otherwise convert X == 0 -> X ^ 1.  */
> +      if (code == EQ_EXPR)
> +       {
> +         if (TYPE_PRECISION (TREE_TYPE (tmp)) == 1)
> +           code = BIT_NOT_EXPR;
> +         else
> +           {
> +             code = BIT_XOR_EXPR;
> +             tmp2 = build_one_cst (TREE_TYPE (tmp));
> +           }
> +       }
> +      else
> +       code = TREE_CODE (tmp);
> +      gsi = gsi_for_stmt (stmt);
> +      gimple_assign_set_rhs_with_ops (&gsi, code,
> +                                     tmp, tmp2);
> +      update_stmt (stmt);
> +      return true;
> +    }
> +
>   /* Don't propagate ssa names that occur in abnormal phis.  */
>   if ((TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
>        && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt)))
> @@ -1179,7 +1229,8 @@ forward_propagate_comparison (gimple stm
>     }
>
>   /* Remove defining statements.  */
> -  return remove_prop_source_from_use (name);
> +  remove_prop_source_from_use (name);
> +  return true;
>  }
>
>
> @@ -2459,6 +2510,9 @@ ssa_forward_propagate_and_combine (void)
>                        (!no_warning && changed,
>                         stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
>                    changed = did_something != 0;
> +                   if (!changed)
> +                     changed = forward_propagate_comparison (stmt);
> +
>                  }
>                else if (code == BIT_AND_EXPR
>                         || code == BIT_IOR_EXPR
> Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/forwprop-9.c
> ===================================================================
> --- gcc.orig/gcc/testsuite/gcc.dg/tree-ssa/forwprop-9.c
> +++ gcc/gcc/testsuite/gcc.dg/tree-ssa/forwprop-9.c
> @@ -1,21 +1,14 @@
>  /* { dg-do compile } */
> -/* { dg-options "-O1 -fdump-tree-optimized -fdump-tree-fre1 -W -Wall
> -fno-early-inlining" } */
> +/* { dg-options "-O2 -fdump-tree-forwprop1" }  */
>
> -int b;
> -unsigned a;
> -static inline int *g(void)
> +_Bool
> +foo (_Bool a, _Bool b, _Bool c
>  {
> -  a = 1;
> -  return (int*)&a;
> +  _Bool r1 = a == 0 & b != 0;
> +  _Bool r2 = b != 0 & c == 0;
> +  return (r1 == 0 & r2 == 0);
>  }
> -void f(void)
> -{
> -   b = *g();
> -}
> -
> -/* We should have converted the assignments to two = 1.  FRE does this.  */
>
> -/* { dg-final { scan-tree-dump-times " = 1" 2 "optimized"} } */
> -/* { dg-final { scan-tree-dump-not " = a;" "fre1"} } */
> -/* { dg-final { cleanup-tree-dump "fre1" } } */
> -/* { dg-final { cleanup-tree-dump "optimized" } } */
> +/* { dg-final { scan-tree-dump-times " == " 0 "forwprop1" } } */
> +/* { dg-final { scan-tree-dump-times " != " 0 "forwprop1" } } */
> +/* { dg-final { cleanup-tree-dump "forwprop1" } } */
>

Patch

Index: gcc/gcc/gimple.c
===================================================================
--- gcc.orig/gcc/gimple.c
+++ gcc/gcc/gimple.c
@@ -3160,7 +3160,9 @@  canonicalize_cond_expr_cond (tree t)
 {
   /* Strip conversions around boolean operations.  */
   if (CONVERT_EXPR_P (t)
-      && truth_value_p (TREE_CODE (TREE_OPERAND (t, 0))))
+      && (truth_value_p (TREE_CODE (TREE_OPERAND (t, 0)))
+          || TREE_CODE (TREE_TYPE (TREE_OPERAND (t, 0)))
+	     == BOOLEAN_TYPE))
     t = TREE_OPERAND (t, 0);

   /* For !x use x == 0.  */
Index: gcc/gcc/tree-ssa-forwprop.c
===================================================================
--- gcc.orig/gcc/tree-ssa-forwprop.c
+++ gcc/gcc/tree-ssa-forwprop.c
@@ -1114,7 +1114,18 @@  forward_propagate_addr_expr (tree name,
      a_1 = (T')cond_1
      a_1 = !cond_1
      a_1 = cond_1 != 0
-   Returns true if stmt is now unused.  */
+     For boolean typed comparisons with type-precision of one
+     X == 0 -> ~X
+     X != ~0 -> ~X
+     X != 0 -> X
+     X == ~0 -> X
+     For boolean typed comparison with none one-bit type-precision
+     we can assume that truth-value is one, and false-value is zero.
+     X == 1 -> X
+     X != 1 -> X ^ 1
+     X == 0 -> X ^ 1
+     X != 0 -> X
+   Returns true if stmt is changed.  */

 static bool
 forward_propagate_comparison (gimple stmt)
@@ -1123,9 +1134,48 @@  forward_propagate_comparison (gimple stm
   gimple use_stmt;
   tree tmp = NULL_TREE;
   gimple_stmt_iterator gsi;
-  enum tree_code code;
+  enum tree_code code = gimple_assign_rhs_code (stmt);
   tree lhs;

+  /* Simplify X != 0 -> X and X == 0 -> ~X, if X is boolean-typed
+     and X has a compatible type to the comparison-expression.  */
+  if ((code == EQ_EXPR || code == NE_EXPR)
+      && TREE_CODE (TREE_TYPE (gimple_assign_rhs1 (stmt))) == BOOLEAN_TYPE
+      && TREE_CODE (gimple_assign_rhs2 (stmt)) == INTEGER_CST
+      /* A comparison is always boolean-typed, but there might be
+	 differences in mode-size.  */
+      && useless_type_conversion_p (TREE_TYPE (name),
+				    TREE_TYPE (gimple_assign_rhs1 (stmt))))
+    {
+      tree tmp2;
+
+      /* Normalize to reduce cases.  */
+      if (!integer_zerop (gimple_assign_rhs2 (stmt)))
+        code = (code == EQ_EXPR ? NE_EXPR : EQ_EXPR);
+      tmp = gimple_assign_rhs1 (stmt);
+      tmp2 = NULL_TREE;
+
+      /* Convert X == 0 -> ~X for 1-bit precision boolean-type.
+	 Otherwise convert X == 0 -> X ^ 1.  */
+      if (code == EQ_EXPR)
+	{
+	  if (TYPE_PRECISION (TREE_TYPE (tmp)) == 1)
+	    code = BIT_NOT_EXPR;
+	  else
+	    {
+	      code = BIT_XOR_EXPR;
+	      tmp2 = build_one_cst (TREE_TYPE (tmp));
+	    }
+	}
+      else
+	code = TREE_CODE (tmp);
+      gsi = gsi_for_stmt (stmt);
+      gimple_assign_set_rhs_with_ops (&gsi, code,
+				      tmp, tmp2);
+      update_stmt (stmt);
+      return true;
+    }
+
   /* Don't propagate ssa names that occur in abnormal phis.  */
   if ((TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
        && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt)))
@@ -1179,7 +1229,8 @@  forward_propagate_comparison (gimple stm
     }

   /* Remove defining statements.  */
-  return remove_prop_source_from_use (name);
+  remove_prop_source_from_use (name);
+  return true;
 }


@@ -2459,6 +2510,9 @@  ssa_forward_propagate_and_combine (void)
 			(!no_warning && changed,
 			 stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
 		    changed = did_something != 0;
+		    if (!changed)
+		      changed = forward_propagate_comparison (stmt);
+
 		  }
 		else if (code == BIT_AND_EXPR
 			 || code == BIT_IOR_EXPR
Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/forwprop-9.c
===================================================================
--- gcc.orig/gcc/testsuite/gcc.dg/tree-ssa/forwprop-9.c
+++ gcc/gcc/testsuite/gcc.dg/tree-ssa/forwprop-9.c
@@ -1,21 +1,14 @@ 
 /* { dg-do compile } */
-/* { dg-options "-O1 -fdump-tree-optimized -fdump-tree-fre1 -W -Wall
-fno-early-inlining" } */
+/* { dg-options "-O2 -fdump-tree-forwprop1" }  */

-int b;
-unsigned a;
-static inline int *g(void)
+_Bool
+foo (_Bool a, _Bool b, _Bool c
 {
-  a = 1;
-  return (int*)&a;
+  _Bool r1 = a == 0 & b != 0;
+  _Bool r2 = b != 0 & c == 0;
+  return (r1 == 0 & r2 == 0);
 }
-void f(void)
-{
-   b = *g();
-}
-
-/* We should have converted the assignments to two = 1.  FRE does this.  */

-/* { dg-final { scan-tree-dump-times " = 1" 2 "optimized"} } */
-/* { dg-final { scan-tree-dump-not " = a;" "fre1"} } */
-/* { dg-final { cleanup-tree-dump "fre1" } } */
-/* { dg-final { cleanup-tree-dump "optimized" } } */
+/* { dg-final { scan-tree-dump-times " == " 0 "forwprop1" } } */
+/* { dg-final { scan-tree-dump-times " != " 0 "forwprop1" } } */
+/* { dg-final { cleanup-tree-dump "forwprop1" } } */