Submitted by Cong Hou on Nov. 1, 2013, 12:03 a.m.

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