| Message ID | CAK=A3=2=9GqGSA4AqAYkMuuZ7YqT11uRbSRr7woGuW=xZRXeBA@mail.gmail.com |
|---|---|
| State | New |
| Headers | show |
On 10/31/13 18:03, Cong Hou wrote: > (This patch is for the bug 58728: > http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58728) > > As in the bug report, consider the following loop: > > int foo(unsigned int n) > { > if (n != 0) > if (n != 1) > if (n != 2) > if (n != 3) > if (n != 4) > return ++n; > return n; > } > > The range test optimization should be able to merge all those five > conditions into one in reassoc pass, but I fails to do so. The reason > is that the phi arg of n is replaced by the constant it compares to in > case of == or != comparisons (in vrp pass). GCC checks there is no > side effect on n between any two neighboring conditions by examining > if they defined the same phi arg in the join node. But as the phi arg > is replace by a constant, the check fails. > > This patch deals with this situation by considering the existence of > == or != comparisons, which is attached below (a text file is also > attached with proper tabs). Bootstrap and make check both get passed. > > Any comment? + bool is_eq_expr = is_cond && (gimple_cond_code (stmt) == NE_EXPR + || gimple_cond_code (stmt) == EQ_EXPR) + && TREE_CODE (phi_arg) == INTEGER_CST; + + if (is_eq_expr) + { + lhs = gimple_cond_lhs (stmt); + rhs = gimple_cond_rhs (stmt); + + if (operand_equal_p (lhs, phi_arg, 0)) + { + tree t = lhs; + lhs = rhs; + rhs = t; + } + if (operand_equal_p (rhs, phi_arg, 0) + && operand_equal_p (lhs, phi_arg2, 0)) + continue; + } + + gimple stmt2 = last_stmt (test_bb); + bool is_eq_expr2 = gimple_code (stmt2) == GIMPLE_COND + && (gimple_cond_code (stmt2) == NE_EXPR + || gimple_cond_code (stmt2) == EQ_EXPR) + && TREE_CODE (phi_arg2) == INTEGER_CST; + + if (is_eq_expr2) + { + lhs2 = gimple_cond_lhs (stmt2); + rhs2 = gimple_cond_rhs (stmt2); + + if (operand_equal_p (lhs2, phi_arg2, 0)) + { + tree t = lhs2; + lhs2 = rhs2; + rhs2 = t; + } + if (operand_equal_p (rhs2, phi_arg2, 0) + && operand_equal_p (lhs2, phi_arg, 0)) + continue; + } Can you factor those two hunks of nearly identical code into a single function and call it twice? I'm also curious if you really need the code to swap lhs/rhs. When can the LHS of a cond be an integer constant? Don't we canonicalize it as <ssa_name> <COND> <constant>? I'd probably write the ChangeLog as: * tree-ssa-reassoc.c (suitable_cond_bb): Handle constant PHI operands resulting from propagation of edge equivalences. I'm also curious -- did this code show up in a particular benchmark, if so, which one? jeff
On Tue, Nov 05, 2013 at 01:23:00PM -0700, Jeff Law wrote: > On 10/31/13 18:03, Cong Hou wrote: > >(This patch is for the bug 58728: > >http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58728) > > > >As in the bug report, consider the following loop: > > > >int foo(unsigned int n) > >{ > > if (n != 0) > > if (n != 1) > > if (n != 2) > > if (n != 3) > > if (n != 4) > > return ++n; > > return n; > >} > > > >The range test optimization should be able to merge all those five > >conditions into one in reassoc pass, but I fails to do so. The reason > >is that the phi arg of n is replaced by the constant it compares to in > >case of == or != comparisons (in vrp pass). GCC checks there is no > >side effect on n between any two neighboring conditions by examining > >if they defined the same phi arg in the join node. But as the phi arg > >is replace by a constant, the check fails. I can't reproduce this, at least not on x86_64-linux with -O2, the ifcombine pass already merges those. Jakub
It seems there are some changes in GCC. But if you change the type of
n into signed int, the issue appears again:
int foo(int n)
{
if (n != 0)
if (n != 1)
if (n != 2)
if (n != 3)
if (n != 4)
return ++n;
return n;
}
Also, ifcombine also suffers from the same issue here.
thanks,
Cong
On Tue, Nov 5, 2013 at 12:53 PM, Jakub Jelinek <jakub@redhat.com> wrote:
> On Tue, Nov 05, 2013 at 01:23:00PM -0700, Jeff Law wrote:
>> On 10/31/13 18:03, Cong Hou wrote:
>> >(This patch is for the bug 58728:
>> >http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58728)
>> >
>> >As in the bug report, consider the following loop:
>> >
>> >int foo(unsigned int n)
>> >{
>> > if (n != 0)
>> > if (n != 1)
>> > if (n != 2)
>> > if (n != 3)
>> > if (n != 4)
>> > return ++n;
>> > return n;
>> >}
>> >
>> >The range test optimization should be able to merge all those five
>> >conditions into one in reassoc pass, but I fails to do so. The reason
>> >is that the phi arg of n is replaced by the constant it compares to in
>> >case of == or != comparisons (in vrp pass). GCC checks there is no
>> >side effect on n between any two neighboring conditions by examining
>> >if they defined the same phi arg in the join node. But as the phi arg
>> >is replace by a constant, the check fails.
>
> I can't reproduce this, at least not on x86_64-linux with -O2,
> the ifcombine pass already merges those.
>
> Jakub
On Tue, Nov 5, 2013 at 12:23 PM, Jeff Law <law@redhat.com> wrote: > On 10/31/13 18:03, Cong Hou wrote: >> >> (This patch is for the bug 58728: >> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58728) >> >> As in the bug report, consider the following loop: >> >> int foo(unsigned int n) >> { >> if (n != 0) >> if (n != 1) >> if (n != 2) >> if (n != 3) >> if (n != 4) >> return ++n; >> return n; >> } >> >> The range test optimization should be able to merge all those five >> conditions into one in reassoc pass, but I fails to do so. The reason >> is that the phi arg of n is replaced by the constant it compares to in >> case of == or != comparisons (in vrp pass). GCC checks there is no >> side effect on n between any two neighboring conditions by examining >> if they defined the same phi arg in the join node. But as the phi arg >> is replace by a constant, the check fails. >> >> This patch deals with this situation by considering the existence of >> == or != comparisons, which is attached below (a text file is also >> attached with proper tabs). Bootstrap and make check both get passed. >> >> Any comment? > > > + bool is_eq_expr = is_cond && (gimple_cond_code (stmt) == NE_EXPR > + || gimple_cond_code (stmt) == > EQ_EXPR) > + && TREE_CODE (phi_arg) == INTEGER_CST; > + > + if (is_eq_expr) > + { > + lhs = gimple_cond_lhs (stmt); > + rhs = gimple_cond_rhs (stmt); > + > + if (operand_equal_p (lhs, phi_arg, 0)) > + { > + tree t = lhs; > + lhs = rhs; > + rhs = t; > + } > + if (operand_equal_p (rhs, phi_arg, 0) > + && operand_equal_p (lhs, phi_arg2, 0)) > + continue; > + } > + > + gimple stmt2 = last_stmt (test_bb); > + bool is_eq_expr2 = gimple_code (stmt2) == GIMPLE_COND > + && (gimple_cond_code (stmt2) == NE_EXPR > + || gimple_cond_code (stmt2) == EQ_EXPR) > + && TREE_CODE (phi_arg2) == INTEGER_CST; > + > + if (is_eq_expr2) > + { > + lhs2 = gimple_cond_lhs (stmt2); > + rhs2 = gimple_cond_rhs (stmt2); > + > + if (operand_equal_p (lhs2, phi_arg2, 0)) > + { > + tree t = lhs2; > + lhs2 = rhs2; > + rhs2 = t; > + } > + if (operand_equal_p (rhs2, phi_arg2, 0) > + && operand_equal_p (lhs2, phi_arg, 0)) > + continue; > + } > > Can you factor those two hunks of nearly identical code into a single > function and call it twice? I'm also curious if you really need the code to > swap lhs/rhs. When can the LHS of a cond be an integer constant? Don't we > canonicalize it as <ssa_name> <COND> <constant>? I was not aware that the comparison between a variable and a constant will always be canonicalized as <ssa_name> <COND> <constant>. Then I will remove the swap, and as the code is much smaller, I think it may not be necessary to create a function for them. > > I'd probably write the ChangeLog as: > > * tree-ssa-reassoc.c (suitable_cond_bb): Handle constant PHI > operands resulting from propagation of edge equivalences. > > OK, much better than mine ;) > I'm also curious -- did this code show up in a particular benchmark, if so, > which one? I didn't find this problem from any benchmark, but from another concern about loop upper bound estimation. Look at the following code: int foo(unsigned int n, int r) { int i; if (n > 0) if (n < 4) { do { --n; r *= 2; } while (n > 0); } return r+n; } In order to get the upper bound of the loop in this function, GCC traverses conditions n<4 and n>0 separately and tries to get any useful information. But as those two conditions cannot be combined into one due to this issue (note that n>0 will be transformed into n!=0), when GCC sees n<4, it will consider the possibility that n may be equal to 0, in which case the upper bound is UINT_MAX. If those two conditions can be combined into one, which is n-1<=2, then we can get the correct upper bound of the loop. thanks, Cong > > jeff
On 11/05/13 15:00, Cong Hou wrote: >> >> Can you factor those two hunks of nearly identical code into a single >> function and call it twice? I'm also curious if you really need the code to >> swap lhs/rhs. When can the LHS of a cond be an integer constant? Don't we >> canonicalize it as <ssa_name> <COND> <constant>? > > > I was not aware that the comparison between a variable and a constant > will always be canonicalized as <ssa_name> <COND> <constant>. Then I > will remove the swap, and as the code is much smaller, I think it may > not be necessary to create a function for them. Hmm, looking at is_gimple_condexpr, it appears to accept both forms: /* Return true if T is a GIMPLE condition. */ bool is_gimple_condexpr (tree t) { return (is_gimple_val (t) || (COMPARISON_CLASS_P (t) && !tree_could_throw_p (t) && is_gimple_val (TREE_OPERAND (t, 0)) && is_gimple_val (TREE_OPERAND (t, 1)))); } Sigh. So you probably still need to handle both forms :( > > I didn't find this problem from any benchmark, but from another > concern about loop upper bound estimation. Look at the following code: > > int foo(unsigned int n, int r) > { > int i; > if (n > 0) > if (n < 4) > { > do { > --n; > r *= 2; > } while (n > 0); > } > return r+n; > } > > > In order to get the upper bound of the loop in this function, GCC > traverses conditions n<4 and n>0 separately and tries to get any > useful information. But as those two conditions cannot be combined > into one due to this issue (note that n>0 will be transformed into > n!=0), when GCC sees n<4, it will consider the possibility that n may > be equal to 0, in which case the upper bound is UINT_MAX. If those two > conditions can be combined into one, which is n-1<=2, then we can get > the correct upper bound of the loop. Ah. Ok. Thanks. jeff
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 8a38316..9247222 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,11 @@ +2013-10-31 Cong Hou <congh@google.com> + + PR tree-optimization/58728 + * tree-ssa-reassoc.c (suitable_cond_bb): Consider the situtation + that ==/!= comparisons between a variable and a constant may lead + to that the later phi arg of the variable is substitued by the + constant from prior passes, during range test optimization. + 2013-10-14 David Malcolm <dmalcolm@redhat.com> * dumpfile.h (gcc::dump_manager): New class, to hold state diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 075d071..44a5e70 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,8 @@ +2013-10-31 Cong Hou <congh@google.com> + + PR tree-optimization/58728 + * gcc.dg/tree-ssa/pr58728: New test. + 2013-10-14 Tobias Burnus <burnus@net-b.de> PR fortran/58658 diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr58728.c b/gcc/testsuite/gcc.dg/tree-ssa/pr58728.c new file mode 100644 index 0000000..312aebc --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr58728.c @@ -0,0 +1,25 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-reassoc1-details" } */ + +int foo (unsigned int n) +{ + if (n != 0) + if (n != 1) + return ++n; + return n; +} + +int bar (unsigned int n) +{ + if (n == 0) + ; + else if (n == 1) + ; + else + return ++n; + return n; +} + + +/* { dg-final { scan-tree-dump-times "Optimizing range tests" 2 "reassoc1" } } */ +/* { dg-final { cleanup-tree-dump "reassoc1" } } */ diff --git a/gcc/tree-ssa-reassoc.c b/gcc/tree-ssa-reassoc.c index 6859518..bccf99f 100644 --- a/gcc/tree-ssa-reassoc.c +++ b/gcc/tree-ssa-reassoc.c @@ -2426,11 +2426,70 @@ suitable_cond_bb (basic_block bb, basic_block test_bb, basic_block *other_bb, for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi)) { gimple phi = gsi_stmt (gsi); + tree phi_arg = gimple_phi_arg_def (phi, e->dest_idx); + tree phi_arg2 = gimple_phi_arg_def (phi, e2->dest_idx); + /* If both BB and TEST_BB end with GIMPLE_COND, all PHI arguments corresponding to BB and TEST_BB predecessor must be the same. */ - if (!operand_equal_p (gimple_phi_arg_def (phi, e->dest_idx), - gimple_phi_arg_def (phi, e2->dest_idx), 0)) - { + if (!operand_equal_p (phi_arg, phi_arg2, 0)) + { + /* If the condition in BB or TEST_BB is an NE or EQ comparison like + if (n != N) or if (n == N), it is possible that the corresponding + def of n in the phi function is replaced by N. We should still allow + range test optimization in this case. */ + + tree lhs = NULL, rhs = NULL, + lhs2 = NULL, rhs2 = NULL; + bool is_eq_expr = is_cond && (gimple_cond_code (stmt) == NE_EXPR + || gimple_cond_code (stmt) == EQ_EXPR) + && TREE_CODE (phi_arg) == INTEGER_CST; + + if (is_eq_expr) + { + lhs = gimple_cond_lhs (stmt); + rhs = gimple_cond_rhs (stmt); + + if (operand_equal_p (lhs, phi_arg, 0)) + { + tree t = lhs; + lhs = rhs; + rhs = t; + } + if (operand_equal_p (rhs, phi_arg, 0) + && operand_equal_p (lhs, phi_arg2, 0)) + continue; + } + + gimple stmt2 = last_stmt (test_bb); + bool is_eq_expr2 = gimple_code (stmt2) == GIMPLE_COND + && (gimple_cond_code (stmt2) == NE_EXPR + || gimple_cond_code (stmt2) == EQ_EXPR) + && TREE_CODE (phi_arg2) == INTEGER_CST; + + if (is_eq_expr2) + { + lhs2 = gimple_cond_lhs (stmt2); + rhs2 = gimple_cond_rhs (stmt2); + + if (operand_equal_p (lhs2, phi_arg2, 0)) + { + tree t = lhs2; + lhs2 = rhs2; + rhs2 = t; + } + if (operand_equal_p (rhs2, phi_arg2, 0) + && operand_equal_p (lhs2, phi_arg, 0)) + continue; + } + + if (is_eq_expr && is_eq_expr2) + { + if (operand_equal_p (rhs, phi_arg, 0) + && operand_equal_p (rhs2, phi_arg2, 0) + && operand_equal_p (lhs, lhs2, 0)) + continue; + } + /* Otherwise, if one of the blocks doesn't end with GIMPLE_COND, one of the PHIs should have the lhs of the last stmt in
(This patch is for the bug 58728: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58728) As in the bug report, consider the following loop: int foo(unsigned int n) { if (n != 0) if (n != 1) if (n != 2) if (n != 3) if (n != 4) return ++n; return n; } The range test optimization should be able to merge all those five conditions into one in reassoc pass, but I fails to do so. The reason is that the phi arg of n is replaced by the constant it compares to in case of == or != comparisons (in vrp pass). GCC checks there is no side effect on n between any two neighboring conditions by examining if they defined the same phi arg in the join node. But as the phi arg is replace by a constant, the check fails. This patch deals with this situation by considering the existence of == or != comparisons, which is attached below (a text file is also attached with proper tabs). Bootstrap and make check both get passed. Any comment? thanks, Cong that block as PHI arg and that PHI should have 0 or 1 @@ -2438,21 +2497,16 @@ suitable_cond_bb (basic_block bb, basic_block test_bb, basic_block *other_bb, considered. */ if (!is_cond) { - if (gimple_phi_arg_def (phi, e->dest_idx) - == gimple_assign_lhs (stmt) - && (integer_zerop (gimple_phi_arg_def (phi, e2->dest_idx)) - || integer_onep (gimple_phi_arg_def (phi, - e2->dest_idx)))) + if (phi_arg == gimple_assign_lhs (stmt) + && (integer_zerop (phi_arg2) || integer_onep (phi_arg2))) continue; } else { gimple test_last = last_stmt (test_bb); if (gimple_code (test_last) != GIMPLE_COND - && gimple_phi_arg_def (phi, e2->dest_idx) - == gimple_assign_lhs (test_last) - && (integer_zerop (gimple_phi_arg_def (phi, e->dest_idx)) - || integer_onep (gimple_phi_arg_def (phi, e->dest_idx)))) + && phi_arg2 == gimple_assign_lhs (test_last) + && (integer_zerop (phi_arg) || integer_onep (phi_arg))) continue; } diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 8a38316..9247222 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,11 @@ +2013-10-31 Cong Hou <congh@google.com> + + PR tree-optimization/58728 + * tree-ssa-reassoc.c (suitable_cond_bb): Consider the situtation + that ==/!= comparisons between a variable and a constant may lead + to that the later phi arg of the variable is substitued by the + constant from prior passes, during range test optimization. + 2013-10-14 David Malcolm <dmalcolm@redhat.com> * dumpfile.h (gcc::dump_manager): New class, to hold state diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 075d071..44a5e70 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,8 @@ +2013-10-31 Cong Hou <congh@google.com> + + PR tree-optimization/58728 + * gcc.dg/tree-ssa/pr58728: New test. + 2013-10-14 Tobias Burnus <burnus@net-b.de> PR fortran/58658 diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr58728.c b/gcc/testsuite/gcc.dg/tree-ssa/pr58728.c new file mode 100644 index 0000000..312aebc --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr58728.c @@ -0,0 +1,25 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-reassoc1-details" } */ + +int foo (unsigned int n) +{ + if (n != 0) + if (n != 1) + return ++n; + return n; +} + +int bar (unsigned int n) +{ + if (n == 0) + ; + else if (n == 1) + ; + else + return ++n; + return n; +} + + +/* { dg-final { scan-tree-dump-times "Optimizing range tests" 2 "reassoc1" } } */ +/* { dg-final { cleanup-tree-dump "reassoc1" } } */ diff --git a/gcc/tree-ssa-reassoc.c b/gcc/tree-ssa-reassoc.c index 6859518..bccf99f 100644 --- a/gcc/tree-ssa-reassoc.c +++ b/gcc/tree-ssa-reassoc.c @@ -2426,11 +2426,70 @@ suitable_cond_bb (basic_block bb, basic_block test_bb, basic_block *other_bb, for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi)) { gimple phi = gsi_stmt (gsi); + tree phi_arg = gimple_phi_arg_def (phi, e->dest_idx); + tree phi_arg2 = gimple_phi_arg_def (phi, e2->dest_idx); + /* If both BB and TEST_BB end with GIMPLE_COND, all PHI arguments corresponding to BB and TEST_BB predecessor must be the same. */ - if (!operand_equal_p (gimple_phi_arg_def (phi, e->dest_idx), - gimple_phi_arg_def (phi, e2->dest_idx), 0)) - { + if (!operand_equal_p (phi_arg, phi_arg2, 0)) + { + /* If the condition in BB or TEST_BB is an NE or EQ comparison like + if (n != N) or if (n == N), it is possible that the corresponding + def of n in the phi function is replaced by N. We should still allow + range test optimization in this case. */ + + tree lhs = NULL, rhs = NULL, + lhs2 = NULL, rhs2 = NULL; + bool is_eq_expr = is_cond && (gimple_cond_code (stmt) == NE_EXPR + || gimple_cond_code (stmt) == EQ_EXPR) + && TREE_CODE (phi_arg) == INTEGER_CST; + + if (is_eq_expr) + { + lhs = gimple_cond_lhs (stmt); + rhs = gimple_cond_rhs (stmt); + + if (operand_equal_p (lhs, phi_arg, 0)) + { + tree t = lhs; + lhs = rhs; + rhs = t; + } + if (operand_equal_p (rhs, phi_arg, 0) + && operand_equal_p (lhs, phi_arg2, 0)) + continue; + } + + gimple stmt2 = last_stmt (test_bb); + bool is_eq_expr2 = gimple_code (stmt2) == GIMPLE_COND + && (gimple_cond_code (stmt2) == NE_EXPR + || gimple_cond_code (stmt2) == EQ_EXPR) + && TREE_CODE (phi_arg2) == INTEGER_CST; + + if (is_eq_expr2) + { + lhs2 = gimple_cond_lhs (stmt2); + rhs2 = gimple_cond_rhs (stmt2); + + if (operand_equal_p (lhs2, phi_arg2, 0)) + { + tree t = lhs2; + lhs2 = rhs2; + rhs2 = t; + } + if (operand_equal_p (rhs2, phi_arg2, 0) + && operand_equal_p (lhs2, phi_arg, 0)) + continue; + } + + if (is_eq_expr && is_eq_expr2) + { + if (operand_equal_p (rhs, phi_arg, 0) + && operand_equal_p (rhs2, phi_arg2, 0) + && operand_equal_p (lhs, lhs2, 0)) + continue; + } + /* Otherwise, if one of the blocks doesn't end with GIMPLE_COND, one of the PHIs should have the lhs of the last stmt in that block as PHI arg and that PHI should have 0 or 1 @@ -2438,21 +2497,16 @@ suitable_cond_bb (basic_block bb, basic_block test_bb, basic_block *other_bb, considered. */ if (!is_cond) { - if (gimple_phi_arg_def (phi, e->dest_idx) - == gimple_assign_lhs (stmt) - && (integer_zerop (gimple_phi_arg_def (phi, e2->dest_idx)) - || integer_onep (gimple_phi_arg_def (phi, - e2->dest_idx)))) + if (phi_arg == gimple_assign_lhs (stmt) + && (integer_zerop (phi_arg2) || integer_onep (phi_arg2))) continue; } else { gimple test_last = last_stmt (test_bb); if (gimple_code (test_last) != GIMPLE_COND - && gimple_phi_arg_def (phi, e2->dest_idx) - == gimple_assign_lhs (test_last) - && (integer_zerop (gimple_phi_arg_def (phi, e->dest_idx)) - || integer_onep (gimple_phi_arg_def (phi, e->dest_idx)))) + && phi_arg2 == gimple_assign_lhs (test_last) + && (integer_zerop (phi_arg) || integer_onep (phi_arg))) continue; }