Patchwork teach phi-opt to produce -(a COND b)

login
register
mail settings
Submitter Paolo Bonzini
Date April 27, 2012, 10:01 a.m.
Message ID <1335520861-29252-1-git-send-email-bonzini@gnu.org>
Download mbox | patch
Permalink /patch/155454/
State New
Headers show

Comments

Paolo Bonzini - April 27, 2012, 10:01 a.m.
This patch teaches phiopt to look at phis whose arguments are -1 and 0,
and produce negated setcc statements.

Bootstrapped/regtested x86_64-pc-linux-gnu, together with the patch
for pr53138.  Ok for mainline?

Paolo

2012-04-27  Paolo Bonzini  <bonzini@gnu.org>

        * tree-ssa-phiopt.c (conditional_replacement): Replace PHIs
	whose arguments are -1 and 0, by negating the result of the
	conditional.

2012-04-27  Paolo Bonzini  <bonzini@gnu.org>

        * gcc.c-torture/execute/20120427-2.c: New testcase.
        * gcc.dg/tree-ssa/phi-opt-10.c: New testcase.
Richard Guenther - April 27, 2012, 10:28 a.m.
On Fri, 27 Apr 2012, Paolo Bonzini wrote:

> This patch teaches phiopt to look at phis whose arguments are -1 and 0,
> and produce negated setcc statements.
> 
> Bootstrapped/regtested x86_64-pc-linux-gnu, together with the patch
> for pr53138.  Ok for mainline?

Ok.

Thanks,
Richard.

> Paolo
> 
> 2012-04-27  Paolo Bonzini  <bonzini@gnu.org>
> 
>         * tree-ssa-phiopt.c (conditional_replacement): Replace PHIs
> 	whose arguments are -1 and 0, by negating the result of the
> 	conditional.
> 
> 2012-04-27  Paolo Bonzini  <bonzini@gnu.org>
> 
>         * gcc.c-torture/execute/20120427-2.c: New testcase.
>         * gcc.dg/tree-ssa/phi-opt-10.c: New testcase.
> 
> 
> Index: tree-ssa-phiopt.c
> ===================================================================
> --- tree-ssa-phiopt.c	(revisione 186859)
> +++ tree-ssa-phiopt.c	(copia locale)
> @@ -536,17 +536,21 @@
>    gimple_stmt_iterator gsi;
>    edge true_edge, false_edge;
>    tree new_var, new_var2;
> +  bool neg;
>  
>    /* FIXME: Gimplification of complex type is too hard for now.  */
>    if (TREE_CODE (TREE_TYPE (arg0)) == COMPLEX_TYPE
>        || TREE_CODE (TREE_TYPE (arg1)) == COMPLEX_TYPE)
>      return false;
>  
> -  /* The PHI arguments have the constants 0 and 1, then convert
> -     it to the conditional.  */
> +  /* The PHI arguments have the constants 0 and 1, or 0 and -1, then
> +     convert it to the conditional.  */
>    if ((integer_zerop (arg0) && integer_onep (arg1))
>        || (integer_zerop (arg1) && integer_onep (arg0)))
> -    ;
> +    neg = false;
> +  else if ((integer_zerop (arg0) && integer_all_onesp (arg1))
> +	   || (integer_zerop (arg1) && integer_all_onesp (arg0)))
> +    neg = true;
>    else
>      return false;
>  
> @@ -558,7 +562,7 @@
>       falls through into BB.
>  
>       There is a single PHI node at the join point (BB) and its arguments
> -     are constants (0, 1).
> +     are constants (0, 1) or (0, -1).
>  
>       So, given the condition COND, and the two PHI arguments, we can
>       rewrite this PHI into non-branching code:
> @@ -585,12 +589,20 @@
>       edge so that we know when to invert the condition below.  */
>    extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
>    if ((e0 == true_edge && integer_zerop (arg0))
> -      || (e0 == false_edge && integer_onep (arg0))
> +      || (e0 == false_edge && !integer_zerop (arg0))
>        || (e1 == true_edge && integer_zerop (arg1))
> -      || (e1 == false_edge && integer_onep (arg1)))
> +      || (e1 == false_edge && !integer_zerop (arg1)))
>      cond = fold_build1_loc (gimple_location (stmt),
> -			    TRUTH_NOT_EXPR, TREE_TYPE (cond), cond);
> +                            TRUTH_NOT_EXPR, TREE_TYPE (cond), cond);
>  
> +  if (neg)
> +    {
> +      cond = fold_convert_loc (gimple_location (stmt),
> +                               TREE_TYPE (result), cond);
> +      cond = fold_build1_loc (gimple_location (stmt),
> +                              NEGATE_EXPR, TREE_TYPE (cond), cond);
> +    }
> +
>    /* Insert our new statements at the end of conditional block before the
>       COND_STMT.  */
>    gsi = gsi_for_stmt (stmt);
> Index: testsuite/gcc.c-torture/execute/20120427-2.c
> ===================================================================
> --- testsuite/gcc.c-torture/execute/20120427-2.c	(revisione 0)
> +++ testsuite/gcc.c-torture/execute/20120427-2.c	(revisione 0)
> @@ -0,0 +1,38 @@
> +typedef struct sreal
> +{
> +  unsigned sig;		/* Significant.  */
> +  int exp;		/* Exponent.  */
> +} sreal;
> +
> +sreal_compare (sreal *a, sreal *b)
> +{
> +  if (a->exp > b->exp)
> +    return 1;
> +  if (a->exp < b->exp)
> +    return -1;
> +  if (a->sig > b->sig)
> +    return 1;
> +  if (a->sig < b->sig)
> +    return -1;
> +  return 0;
> +}
> +
> +sreal a[] = {
> +   { 0, 0 },
> +   { 1, 0 },
> +   { 0, 1 },
> +   { 1, 1 }
> +};
> +
> +int main()
> +{
> +  int i, j;
> +  for (i = 0; i <= 3; i++) {
> +    for (j = 0; j < 3; j++) {
> +      if (i < j && sreal_compare(&a[i], &a[j]) != -1) abort();
> +      if (i == j && sreal_compare(&a[i], &a[j]) != 0) abort();
> +      if (i > j && sreal_compare(&a[i], &a[j]) != 1) abort();
> +    }
> +  }
> +  return 0;
> +}
> Index: testsuite/gcc.dg/tree-ssa/phi-opt-10.c
> ===================================================================
> --- testsuite/gcc.dg/tree-ssa/phi-opt-10.c	(revisione 0)
> +++ testsuite/gcc.dg/tree-ssa/phi-opt-10.c	(revisione 0)
> @@ -0,0 +1,11 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O1 -fdump-tree-optimized" } */
> +
> +int nem1_phi (unsigned long a) { return a ? -1 : 0; }
> +int eqm1_phi (unsigned long a) { return a ? 0 : -1; }
> +
> +int spaceship1 (long a) { return a > 0 ? 1 : a < 0 ? -1 : 0; }
> +int spaceship2 (long a) { return a > 0 ? 1 : a == 0 ? 0 : -1; }
> +
> +/* { dg-final { scan-tree-dump-times " = -D" 4 "optimized"} } */
> +/* { dg-final { cleanup-tree-dump "optimized" } } */
> 
>
Andrew Pinski - April 27, 2012, 3:47 p.m.
On Fri, Apr 27, 2012 at 3:01 AM, Paolo Bonzini <bonzini@gnu.org> wrote:
> This patch teaches phiopt to look at phis whose arguments are -1 and 0,
> and produce negated setcc statements.
>
> Bootstrapped/regtested x86_64-pc-linux-gnu, together with the patch
> for pr53138.  Ok for mainline?

I came up with this same patch independently.  I was going to submit
it but I never got around to it.
Thanks for submitting this.

-- Andrew Pinski

>
> Paolo
>
> 2012-04-27  Paolo Bonzini  <bonzini@gnu.org>
>
>        * tree-ssa-phiopt.c (conditional_replacement): Replace PHIs
>        whose arguments are -1 and 0, by negating the result of the
>        conditional.
>
> 2012-04-27  Paolo Bonzini  <bonzini@gnu.org>
>
>        * gcc.c-torture/execute/20120427-2.c: New testcase.
>        * gcc.dg/tree-ssa/phi-opt-10.c: New testcase.
>
>
> Index: tree-ssa-phiopt.c
> ===================================================================
> --- tree-ssa-phiopt.c   (revisione 186859)
> +++ tree-ssa-phiopt.c   (copia locale)
> @@ -536,17 +536,21 @@
>   gimple_stmt_iterator gsi;
>   edge true_edge, false_edge;
>   tree new_var, new_var2;
> +  bool neg;
>
>   /* FIXME: Gimplification of complex type is too hard for now.  */
>   if (TREE_CODE (TREE_TYPE (arg0)) == COMPLEX_TYPE
>       || TREE_CODE (TREE_TYPE (arg1)) == COMPLEX_TYPE)
>     return false;
>
> -  /* The PHI arguments have the constants 0 and 1, then convert
> -     it to the conditional.  */
> +  /* The PHI arguments have the constants 0 and 1, or 0 and -1, then
> +     convert it to the conditional.  */
>   if ((integer_zerop (arg0) && integer_onep (arg1))
>       || (integer_zerop (arg1) && integer_onep (arg0)))
> -    ;
> +    neg = false;
> +  else if ((integer_zerop (arg0) && integer_all_onesp (arg1))
> +          || (integer_zerop (arg1) && integer_all_onesp (arg0)))
> +    neg = true;
>   else
>     return false;
>
> @@ -558,7 +562,7 @@
>      falls through into BB.
>
>      There is a single PHI node at the join point (BB) and its arguments
> -     are constants (0, 1).
> +     are constants (0, 1) or (0, -1).
>
>      So, given the condition COND, and the two PHI arguments, we can
>      rewrite this PHI into non-branching code:
> @@ -585,12 +589,20 @@
>      edge so that we know when to invert the condition below.  */
>   extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
>   if ((e0 == true_edge && integer_zerop (arg0))
> -      || (e0 == false_edge && integer_onep (arg0))
> +      || (e0 == false_edge && !integer_zerop (arg0))
>       || (e1 == true_edge && integer_zerop (arg1))
> -      || (e1 == false_edge && integer_onep (arg1)))
> +      || (e1 == false_edge && !integer_zerop (arg1)))
>     cond = fold_build1_loc (gimple_location (stmt),
> -                           TRUTH_NOT_EXPR, TREE_TYPE (cond), cond);
> +                            TRUTH_NOT_EXPR, TREE_TYPE (cond), cond);
>
> +  if (neg)
> +    {
> +      cond = fold_convert_loc (gimple_location (stmt),
> +                               TREE_TYPE (result), cond);
> +      cond = fold_build1_loc (gimple_location (stmt),
> +                              NEGATE_EXPR, TREE_TYPE (cond), cond);
> +    }
> +
>   /* Insert our new statements at the end of conditional block before the
>      COND_STMT.  */
>   gsi = gsi_for_stmt (stmt);
> Index: testsuite/gcc.c-torture/execute/20120427-2.c
> ===================================================================
> --- testsuite/gcc.c-torture/execute/20120427-2.c        (revisione 0)
> +++ testsuite/gcc.c-torture/execute/20120427-2.c        (revisione 0)
> @@ -0,0 +1,38 @@
> +typedef struct sreal
> +{
> +  unsigned sig;                /* Significant.  */
> +  int exp;             /* Exponent.  */
> +} sreal;
> +
> +sreal_compare (sreal *a, sreal *b)
> +{
> +  if (a->exp > b->exp)
> +    return 1;
> +  if (a->exp < b->exp)
> +    return -1;
> +  if (a->sig > b->sig)
> +    return 1;
> +  if (a->sig < b->sig)
> +    return -1;
> +  return 0;
> +}
> +
> +sreal a[] = {
> +   { 0, 0 },
> +   { 1, 0 },
> +   { 0, 1 },
> +   { 1, 1 }
> +};
> +
> +int main()
> +{
> +  int i, j;
> +  for (i = 0; i <= 3; i++) {
> +    for (j = 0; j < 3; j++) {
> +      if (i < j && sreal_compare(&a[i], &a[j]) != -1) abort();
> +      if (i == j && sreal_compare(&a[i], &a[j]) != 0) abort();
> +      if (i > j && sreal_compare(&a[i], &a[j]) != 1) abort();
> +    }
> +  }
> +  return 0;
> +}
> Index: testsuite/gcc.dg/tree-ssa/phi-opt-10.c
> ===================================================================
> --- testsuite/gcc.dg/tree-ssa/phi-opt-10.c      (revisione 0)
> +++ testsuite/gcc.dg/tree-ssa/phi-opt-10.c      (revisione 0)
> @@ -0,0 +1,11 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O1 -fdump-tree-optimized" } */
> +
> +int nem1_phi (unsigned long a) { return a ? -1 : 0; }
> +int eqm1_phi (unsigned long a) { return a ? 0 : -1; }
> +
> +int spaceship1 (long a) { return a > 0 ? 1 : a < 0 ? -1 : 0; }
> +int spaceship2 (long a) { return a > 0 ? 1 : a == 0 ? 0 : -1; }
> +
> +/* { dg-final { scan-tree-dump-times " = -D" 4 "optimized"} } */
> +/* { dg-final { cleanup-tree-dump "optimized" } } */
H.J. Lu - April 27, 2012, 4:43 p.m.
On Fri, Apr 27, 2012 at 3:01 AM, Paolo Bonzini <bonzini@gnu.org> wrote:
> This patch teaches phiopt to look at phis whose arguments are -1 and 0,
> and produce negated setcc statements.
>
> Bootstrapped/regtested x86_64-pc-linux-gnu, together with the patch
> for pr53138.  Ok for mainline?
>
> Paolo
>
> 2012-04-27  Paolo Bonzini  <bonzini@gnu.org>
>
>        * tree-ssa-phiopt.c (conditional_replacement): Replace PHIs
>        whose arguments are -1 and 0, by negating the result of the
>        conditional.
>

This caused:

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53144

H.J.
Paolo Bonzini - April 27, 2012, 8:39 p.m.
> This caused:
>
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53144

Looks like a PPRE bug.

Paolo
Paolo Bonzini - April 28, 2012, 3:51 p.m.
Il 27/04/2012 18:43, H.J. Lu ha scritto:
> On Fri, Apr 27, 2012 at 3:01 AM, Paolo Bonzini <bonzini@gnu.org> wrote:
>> This patch teaches phiopt to look at phis whose arguments are -1 and 0,
>> and produce negated setcc statements.
>>
>> Bootstrapped/regtested x86_64-pc-linux-gnu, together with the patch
>> for pr53138.  Ok for mainline?
>>
>> Paolo
>>
>> 2012-04-27  Paolo Bonzini  <bonzini@gnu.org>
>>
>>        * tree-ssa-phiopt.c (conditional_replacement): Replace PHIs
>>        whose arguments are -1 and 0, by negating the result of the
>>        conditional.
>>
> 
> This caused:
> 
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53144

The bug exists even in 4.7.0, so in some sense it's a good thing that
the testsuite reminds about it. :)

Paolo
Richard Henderson - May 1, 2012, 5:40 p.m.
On 04/27/2012 03:01 AM, Paolo Bonzini wrote:
> This patch teaches phiopt to look at phis whose arguments are -1 and 0,
> and produce negated setcc statements.

Is this really a win over a COND_EXPR, i.e. (a < b ? -1 : 0)?

There is quite a bit of logic inside the rtl and backend expansion of
cmove that would seem to be being bypassed by committing to this form.


r~
Richard Guenther - May 2, 2012, 8:38 a.m.
On Tue, 1 May 2012, Richard Henderson wrote:

> On 04/27/2012 03:01 AM, Paolo Bonzini wrote:
> > This patch teaches phiopt to look at phis whose arguments are -1 and 0,
> > and produce negated setcc statements.
> 
> Is this really a win over a COND_EXPR, i.e. (a < b ? -1 : 0)?
> 
> There is quite a bit of logic inside the rtl and backend expansion of
> cmove that would seem to be being bypassed by committing to this form.

Well, it's a choice of representation on GIMPLE.  Allowing COND_EXPRs
on the RHS is quite new (and does not play well with standard optimization
passes).  If RTL expansion logic prefers COND_EXPRs over the
CFG/PHI style then we should see to present it with COND_EXPRs when
we go out of SSA form (well we don't, but we do SSA name partitioning
and certainly at that time we should adjust/optimize PHI nodes - also
re-instantiating the now missing feature of splitting blocks to enable
PHI argument CSE).

Richard.
H.J. Lu - June 22, 2012, 12:23 p.m.
On Fri, Apr 27, 2012 at 9:43 AM, H.J. Lu <hjl.tools@gmail.com> wrote:
> On Fri, Apr 27, 2012 at 3:01 AM, Paolo Bonzini <bonzini@gnu.org> wrote:
>> This patch teaches phiopt to look at phis whose arguments are -1 and 0,
>> and produce negated setcc statements.
>>
>> Bootstrapped/regtested x86_64-pc-linux-gnu, together with the patch
>> for pr53138.  Ok for mainline?
>>
>> Paolo
>>
>> 2012-04-27  Paolo Bonzini  <bonzini@gnu.org>
>>
>>        * tree-ssa-phiopt.c (conditional_replacement): Replace PHIs
>>        whose arguments are -1 and 0, by negating the result of the
>>        conditional.
>>
>
> This caused:
>
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53144
>

This also caused:

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53748

Patch

Index: tree-ssa-phiopt.c
===================================================================
--- tree-ssa-phiopt.c	(revisione 186859)
+++ tree-ssa-phiopt.c	(copia locale)
@@ -536,17 +536,21 @@ 
   gimple_stmt_iterator gsi;
   edge true_edge, false_edge;
   tree new_var, new_var2;
+  bool neg;
 
   /* FIXME: Gimplification of complex type is too hard for now.  */
   if (TREE_CODE (TREE_TYPE (arg0)) == COMPLEX_TYPE
       || TREE_CODE (TREE_TYPE (arg1)) == COMPLEX_TYPE)
     return false;
 
-  /* The PHI arguments have the constants 0 and 1, then convert
-     it to the conditional.  */
+  /* The PHI arguments have the constants 0 and 1, or 0 and -1, then
+     convert it to the conditional.  */
   if ((integer_zerop (arg0) && integer_onep (arg1))
       || (integer_zerop (arg1) && integer_onep (arg0)))
-    ;
+    neg = false;
+  else if ((integer_zerop (arg0) && integer_all_onesp (arg1))
+	   || (integer_zerop (arg1) && integer_all_onesp (arg0)))
+    neg = true;
   else
     return false;
 
@@ -558,7 +562,7 @@ 
      falls through into BB.
 
      There is a single PHI node at the join point (BB) and its arguments
-     are constants (0, 1).
+     are constants (0, 1) or (0, -1).
 
      So, given the condition COND, and the two PHI arguments, we can
      rewrite this PHI into non-branching code:
@@ -585,12 +589,20 @@ 
      edge so that we know when to invert the condition below.  */
   extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
   if ((e0 == true_edge && integer_zerop (arg0))
-      || (e0 == false_edge && integer_onep (arg0))
+      || (e0 == false_edge && !integer_zerop (arg0))
       || (e1 == true_edge && integer_zerop (arg1))
-      || (e1 == false_edge && integer_onep (arg1)))
+      || (e1 == false_edge && !integer_zerop (arg1)))
     cond = fold_build1_loc (gimple_location (stmt),
-			    TRUTH_NOT_EXPR, TREE_TYPE (cond), cond);
+                            TRUTH_NOT_EXPR, TREE_TYPE (cond), cond);
 
+  if (neg)
+    {
+      cond = fold_convert_loc (gimple_location (stmt),
+                               TREE_TYPE (result), cond);
+      cond = fold_build1_loc (gimple_location (stmt),
+                              NEGATE_EXPR, TREE_TYPE (cond), cond);
+    }
+
   /* Insert our new statements at the end of conditional block before the
      COND_STMT.  */
   gsi = gsi_for_stmt (stmt);
Index: testsuite/gcc.c-torture/execute/20120427-2.c
===================================================================
--- testsuite/gcc.c-torture/execute/20120427-2.c	(revisione 0)
+++ testsuite/gcc.c-torture/execute/20120427-2.c	(revisione 0)
@@ -0,0 +1,38 @@ 
+typedef struct sreal
+{
+  unsigned sig;		/* Significant.  */
+  int exp;		/* Exponent.  */
+} sreal;
+
+sreal_compare (sreal *a, sreal *b)
+{
+  if (a->exp > b->exp)
+    return 1;
+  if (a->exp < b->exp)
+    return -1;
+  if (a->sig > b->sig)
+    return 1;
+  if (a->sig < b->sig)
+    return -1;
+  return 0;
+}
+
+sreal a[] = {
+   { 0, 0 },
+   { 1, 0 },
+   { 0, 1 },
+   { 1, 1 }
+};
+
+int main()
+{
+  int i, j;
+  for (i = 0; i <= 3; i++) {
+    for (j = 0; j < 3; j++) {
+      if (i < j && sreal_compare(&a[i], &a[j]) != -1) abort();
+      if (i == j && sreal_compare(&a[i], &a[j]) != 0) abort();
+      if (i > j && sreal_compare(&a[i], &a[j]) != 1) abort();
+    }
+  }
+  return 0;
+}
Index: testsuite/gcc.dg/tree-ssa/phi-opt-10.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/phi-opt-10.c	(revisione 0)
+++ testsuite/gcc.dg/tree-ssa/phi-opt-10.c	(revisione 0)
@@ -0,0 +1,11 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O1 -fdump-tree-optimized" } */
+
+int nem1_phi (unsigned long a) { return a ? -1 : 0; }
+int eqm1_phi (unsigned long a) { return a ? 0 : -1; }
+
+int spaceship1 (long a) { return a > 0 ? 1 : a < 0 ? -1 : 0; }
+int spaceship2 (long a) { return a > 0 ? 1 : a == 0 ? 0 : -1; }
+
+/* { dg-final { scan-tree-dump-times " = -D" 4 "optimized"} } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */