Message ID | 1335520861-29252-1-git-send-email-bonzini@gnu.org |
---|---|
State | New |
Headers | show |
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" } } */ > >
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" } } */
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.
> This caused: > > http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53144 Looks like a PPRE bug. Paolo
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
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~
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.
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
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" } } */