Message ID | OFA82D021E.63AEB8EC-ONC2257751.002876BC-C2257751.002C40BD@il.ibm.com |
---|---|
State | New |
Headers | show |
On Tue, Jun 29, 2010 at 10:03 AM, Ira Rosen <IRAR@il.ibm.com> wrote: > > Hi, > > For the following minloc loop (which I am trying to vectorize): > > for (i = 0; i < N; i++) > if (arr[i] < limit) > { > pos = i + 1; > limit = arr[i]; > } > > if-conversion generates > > # pos_22 = PHI <pos_1(8), 1(3)> > # i_23 = PHI <prephitmp.8_2(8), 0(3)> > # limit_24 = PHI <limit_4(8), 1.28e+2(3)> > limit_10 = arr[i_23]; > pos_11 = i_23 + 1; > pretmp.7_3 = i_23 + 1; > pos_1 = [cond_expr] limit_10 >= limit_24 ? pos_22 : pos_11; > limit_4 = [cond_expr] limit_10 >= limit_24 ? limit_24 : limit_10; > prephitmp.8_2 = [cond_expr] limit_10 >= limit_24 ? pretmp.7_3 : pos_11; > if (prephitmp.8_2 < n_9(D)) > goto <bb 8>; > else > goto <bb 9>; > > > For > > prephitmp.8_2 = [cond_expr] limit_10 >= limit_24 ? pretmp.7_3 : pos_11; > > then and else clauses are equivalent, so > > prephitmp.8_2 = pretmp.7_3; > > should be enough. > > > Does the following patch make sense? (Meanwhile, I only tested it with > vectorizer testsuite). Can you provide a complete testcase? PRE should have recognized the equivalecy already. Richard. > Thanks, > Ira > > ChangeLog: > > * tree-if-conv.c (replace_phi_with_cond_gimple_assign_stmt): > If then and else clauses are equivalent, use one of them as a > rhs. > > Index: tree-if-conv.c > =================================================================== > --- tree-if-conv.c (revision 161484) > +++ tree-if-conv.c (working copy) > @@ -925,6 +925,8 @@ replace_phi_with_cond_gimple_assign_stmt > basic_block bb; > tree rhs; > tree arg; > + gimple def_stmt0, def_stmt1; > + enum tree_code code; > > gcc_assert (gimple_code (phi) == GIMPLE_PHI > && gimple_phi_num_args (phi) == 2); > @@ -949,9 +951,35 @@ replace_phi_with_cond_gimple_assign_stmt > arg_1 = gimple_phi_arg_def (phi, 1); > } > > - /* Build new RHS using selected condition and arguments. */ > - rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)), > - unshare_expr (cond), arg_0, arg_1); > + if (TREE_CODE (arg_0) == SSA_NAME && TREE_CODE (arg_1) == SSA_NAME > + && (def_stmt0 = SSA_NAME_DEF_STMT (arg_0)) > + && (def_stmt1 = SSA_NAME_DEF_STMT (arg_1)) > + && is_gimple_assign (def_stmt0) > + && is_gimple_assign (def_stmt1) > + && (code = gimple_assign_rhs_code (def_stmt0)) > + == gimple_assign_rhs_code (def_stmt1) > + && ((get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS > + && operand_equal_p (gimple_assign_rhs1 (def_stmt0), > + gimple_assign_rhs1 (def_stmt1), 0)) > + || (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS > + && operand_equal_p (gimple_assign_rhs1 (def_stmt0), > + gimple_assign_rhs1 (def_stmt1), 0) > + && operand_equal_p (gimple_assign_rhs2 (def_stmt0), > + gimple_assign_rhs2 (def_stmt1), 0)) > + || (get_gimple_rhs_class (code) == GIMPLE_TERNARY_RHS > + && operand_equal_p (gimple_assign_rhs1 (def_stmt0), > + gimple_assign_rhs1 (def_stmt1), 0) > + && operand_equal_p (gimple_assign_rhs2 (def_stmt0), > + gimple_assign_rhs2 (def_stmt1), 0) > + && operand_equal_p (gimple_assign_rhs3 (def_stmt0), > + gimple_assign_rhs3 (def_stmt1), > 0)))) > + /* Since then and else parts are equivalent, make RHS to be one of > + them. */ > + rhs = arg_0; > + else > + /* Build new RHS using selected condition and arguments. */ > + rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)), > + unshare_expr (cond), arg_0, arg_1); > } > > new_stmt = gimple_build_assign (PHI_RESULT (phi), rhs); > >
Richard Guenther <richard.guenther@gmail.com> wrote on 29/06/2010 12:46:52 PM: > On Tue, Jun 29, 2010 at 10:03 AM, Ira Rosen <IRAR@il.ibm.com> wrote: > > > > Hi, > > > > For the following minloc loop (which I am trying to vectorize): > > > > for (i = 0; i < N; i++) > > if (arr[i] < limit) > > { > > pos = i + 1; > > limit = arr[i]; > > } > > > > if-conversion generates > > > > # pos_22 = PHI <pos_1(8), 1(3)> > > # i_23 = PHI <prephitmp.8_2(8), 0(3)> > > # limit_24 = PHI <limit_4(8), 1.28e+2(3)> > > limit_10 = arr[i_23]; > > pos_11 = i_23 + 1; > > pretmp.7_3 = i_23 + 1; > > pos_1 = [cond_expr] limit_10 >= limit_24 ? pos_22 : pos_11; > > limit_4 = [cond_expr] limit_10 >= limit_24 ? limit_24 : limit_10; > > prephitmp.8_2 = [cond_expr] limit_10 >= limit_24 ? pretmp.7_3 : pos_11; > > if (prephitmp.8_2 < n_9(D)) > > goto <bb 8>; > > else > > goto <bb 9>; > > > > > > For > > > > prephitmp.8_2 = [cond_expr] limit_10 >= limit_24 ? pretmp.7_3 : pos_11; > > > > then and else clauses are equivalent, so > > > > prephitmp.8_2 = pretmp.7_3; > > > > should be enough. > > > > > > Does the following patch make sense? (Meanwhile, I only tested it with > > vectorizer testsuite). > > Can you provide a complete testcase? PRE should have recognized > the equivalecy already. (See attached file: test.c) Thanks, Ira > > Richard. > > > Thanks, > > Ira > > > > ChangeLog: > > > > * tree-if-conv.c (replace_phi_with_cond_gimple_assign_stmt): > > If then and else clauses are equivalent, use one of them as a > > rhs. > > > > Index: tree-if-conv.c > > =================================================================== > > --- tree-if-conv.c (revision 161484) > > +++ tree-if-conv.c (working copy) > > @@ -925,6 +925,8 @@ replace_phi_with_cond_gimple_assign_stmt > > basic_block bb; > > tree rhs; > > tree arg; > > + gimple def_stmt0, def_stmt1; > > + enum tree_code code; > > > > gcc_assert (gimple_code (phi) == GIMPLE_PHI > > && gimple_phi_num_args (phi) == 2); > > @@ -949,9 +951,35 @@ replace_phi_with_cond_gimple_assign_stmt > > arg_1 = gimple_phi_arg_def (phi, 1); > > } > > > > - /* Build new RHS using selected condition and arguments. */ > > - rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)), > > - unshare_expr (cond), arg_0, arg_1); > > + if (TREE_CODE (arg_0) == SSA_NAME && TREE_CODE (arg_1) == SSA_NAME > > + && (def_stmt0 = SSA_NAME_DEF_STMT (arg_0)) > > + && (def_stmt1 = SSA_NAME_DEF_STMT (arg_1)) > > + && is_gimple_assign (def_stmt0) > > + && is_gimple_assign (def_stmt1) > > + && (code = gimple_assign_rhs_code (def_stmt0)) > > + == gimple_assign_rhs_code (def_stmt1) > > + && ((get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS > > + && operand_equal_p (gimple_assign_rhs1 (def_stmt0), > > + gimple_assign_rhs1 (def_stmt1), 0)) > > + || (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS > > + && operand_equal_p (gimple_assign_rhs1 (def_stmt0), > > + gimple_assign_rhs1 (def_stmt1), 0) > > + && operand_equal_p (gimple_assign_rhs2 (def_stmt0), > > + gimple_assign_rhs2 (def_stmt1), 0)) > > + || (get_gimple_rhs_class (code) == GIMPLE_TERNARY_RHS > > + && operand_equal_p (gimple_assign_rhs1 (def_stmt0), > > + gimple_assign_rhs1 (def_stmt1), 0) > > + && operand_equal_p (gimple_assign_rhs2 (def_stmt0), > > + gimple_assign_rhs2 (def_stmt1), 0) > > + && operand_equal_p (gimple_assign_rhs3 (def_stmt0), > > + gimple_assign_rhs3 (def_stmt1), > > 0)))) > > + /* Since then and else parts are equivalent, make RHS to be one of > > + them. */ > > + rhs = arg_0; > > + else > > + /* Build new RHS using selected condition and arguments. */ > > + rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)), > > + unshare_expr (cond), arg_0, arg_1); > > } > > > > new_stmt = gimple_build_assign (PHI_RESULT (phi), rhs); > > > >
On Tue, Jun 29, 2010 at 11:58 AM, Ira Rosen <IRAR@il.ibm.com> wrote: > > > > Richard Guenther <richard.guenther@gmail.com> wrote on 29/06/2010 12:46:52 > PM: > >> On Tue, Jun 29, 2010 at 10:03 AM, Ira Rosen <IRAR@il.ibm.com> wrote: >> > >> > Hi, >> > >> > For the following minloc loop (which I am trying to vectorize): >> > >> > for (i = 0; i < N; i++) >> > if (arr[i] < limit) >> > { >> > pos = i + 1; >> > limit = arr[i]; >> > } >> > >> > if-conversion generates >> > >> > # pos_22 = PHI <pos_1(8), 1(3)> >> > # i_23 = PHI <prephitmp.8_2(8), 0(3)> >> > # limit_24 = PHI <limit_4(8), 1.28e+2(3)> >> > limit_10 = arr[i_23]; >> > pos_11 = i_23 + 1; >> > pretmp.7_3 = i_23 + 1; >> > pos_1 = [cond_expr] limit_10 >= limit_24 ? pos_22 : pos_11; >> > limit_4 = [cond_expr] limit_10 >= limit_24 ? limit_24 : limit_10; >> > prephitmp.8_2 = [cond_expr] limit_10 >= limit_24 ? pretmp.7_3 : > pos_11; >> > if (prephitmp.8_2 < n_9(D)) >> > goto <bb 8>; >> > else >> > goto <bb 9>; >> > >> > >> > For >> > >> > prephitmp.8_2 = [cond_expr] limit_10 >= limit_24 ? pretmp.7_3 : pos_11; >> > >> > then and else clauses are equivalent, so >> > >> > prephitmp.8_2 = pretmp.7_3; >> > >> > should be enough. >> > >> > >> > Does the following patch make sense? (Meanwhile, I only tested it with >> > vectorizer testsuite). >> >> Can you provide a complete testcase? PRE should have recognized >> the equivalecy already. > > (See attached file: test.c) So the reason is our heuristic in PRE to not introduce new IVs: Found partial redundancy for expression {plus_expr,i_24,1} (0005) Skipping insertion of phi for partial redundancy: Looks like an induction variable Inserted pretmp.4_2 = i_13 + 1; in predecessor 8 Found partial redundancy for expression {plus_expr,i_24,1} (0005) Inserted pretmp.4_22 = i_24 + 1; in predecessor 7 Created phi prephitmp.5_21 = PHI <pretmp.4_22(7), pos_11(4)> in block 5 Found partial redundancy for expression {plus_expr,i_24,1} (0005) Skipping insertion of phi for partial redundancy: Looks like an induction variable Replaced i_24 + 1 with prephitmp.5_21 in i_13 = i_24 + 1; Removing unnecessary insertion:pretmp.4_2 = i_13 + 1; we do not want to insert into block 3, so we are left with <bb 3>: # pos_23 = PHI <pos_1(8), 1(2)> # i_24 = PHI <i_13(8), 0(2)> # limit_25 = PHI <limit_4(8), 1.28e+2(2)> limit_9 = arr[i_24]; D.3841_10 = limit_9 < limit_25; if (D.3841_10 != 0) goto <bb 4>; else goto <bb 7>; <bb 7>: pretmp.4_22 = i_24 + 1; goto <bb 5>; <bb 4>: pos_11 = i_24 + 1; <bb 5>: # pos_1 = PHI <pos_23(7), pos_11(4)> # limit_4 = PHI <limit_25(7), limit_9(4)> # prephitmp.5_21 = PHI <pretmp.4_22(7), pos_11(4)> i_13 = prephitmp.5_21; where there is no full redundancy for i_24 + 1 now (that is, we did some useless half-way PRE because of that IV heuristic ...). Can you file a bug about this, too? It should be fixed in PRE, not worked around in if-conversion. Thanks, Richard.
Index: tree-if-conv.c =================================================================== --- tree-if-conv.c (revision 161484) +++ tree-if-conv.c (working copy) @@ -925,6 +925,8 @@ replace_phi_with_cond_gimple_assign_stmt basic_block bb; tree rhs; tree arg; + gimple def_stmt0, def_stmt1; + enum tree_code code; gcc_assert (gimple_code (phi) == GIMPLE_PHI && gimple_phi_num_args (phi) == 2); @@ -949,9 +951,35 @@ replace_phi_with_cond_gimple_assign_stmt arg_1 = gimple_phi_arg_def (phi, 1); } - /* Build new RHS using selected condition and arguments. */ - rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)), - unshare_expr (cond), arg_0, arg_1); + if (TREE_CODE (arg_0) == SSA_NAME && TREE_CODE (arg_1) == SSA_NAME + && (def_stmt0 = SSA_NAME_DEF_STMT (arg_0)) + && (def_stmt1 = SSA_NAME_DEF_STMT (arg_1)) + && is_gimple_assign (def_stmt0) + && is_gimple_assign (def_stmt1) + && (code = gimple_assign_rhs_code (def_stmt0)) + == gimple_assign_rhs_code (def_stmt1) + && ((get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS + && operand_equal_p (gimple_assign_rhs1 (def_stmt0), + gimple_assign_rhs1 (def_stmt1), 0)) + || (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS + && operand_equal_p (gimple_assign_rhs1 (def_stmt0), + gimple_assign_rhs1 (def_stmt1), 0) + && operand_equal_p (gimple_assign_rhs2 (def_stmt0), + gimple_assign_rhs2 (def_stmt1), 0)) + || (get_gimple_rhs_class (code) == GIMPLE_TERNARY_RHS + && operand_equal_p (gimple_assign_rhs1 (def_stmt0), + gimple_assign_rhs1 (def_stmt1), 0) + && operand_equal_p (gimple_assign_rhs2 (def_stmt0), + gimple_assign_rhs2 (def_stmt1), 0) + && operand_equal_p (gimple_assign_rhs3 (def_stmt0), + gimple_assign_rhs3 (def_stmt1), 0)))) + /* Since then and else parts are equivalent, make RHS to be one of + them. */ + rhs = arg_0; + else + /* Build new RHS using selected condition and arguments. */ + rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)), + unshare_expr (cond), arg_0, arg_1); }