| Message ID | CAELXzTO1v8+bgXdcR1GCMUvpOn=PXgZYHQqW_5cxxyrT4z+SYg@mail.gmail.com |
|---|---|
| State | New |
| Headers | show |
| Series | [1/3,POPCOUNT] Handle COND_EXPR in expression_expensive_p | expand |
On Fri, Jun 22, 2018 at 11:16 AM Kugan Vivekanandarajah <kugan.vivekanandarajah@linaro.org> wrote: > > gcc/ChangeLog: @@ -1516,6 +1521,114 @@ minmax_replacement (basic_block cond_bb, basic_block middle_bb, return true; } +/* Convert + + <bb 2> + if (b_4(D) != 0) + goto <bb 3> vertical space before the comment. + edge e0 ATTRIBUTE_UNUSED, edge e1 ATTRIBUTE_UNUSED, why pass them if they are unused? + if (stmt_count != 2) + return false; so what about the case when there is no conversion? + /* Check that we have a popcount builtin. */ + if (!is_gimple_call (popcount) + || !gimple_call_builtin_p (popcount, BUILT_IN_NORMAL)) + return false; + tree fndecl = gimple_call_fndecl (popcount); + if ((DECL_FUNCTION_CODE (fndecl) != BUILT_IN_POPCOUNT) + && (DECL_FUNCTION_CODE (fndecl) != BUILT_IN_POPCOUNTL) + && (DECL_FUNCTION_CODE (fndecl) != BUILT_IN_POPCOUNTLL)) + return false; look at popcount handling in tree-vrp.c how to properly also handle IFN_POPCOUNT. (CASE_CFN_POPCOUNT) + /* Cond_bb has a check for b_4 != 0 before calling the popcount + builtin. */ + if (gimple_code (cond) != GIMPLE_COND + || gimple_cond_code (cond) != NE_EXPR + || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME + || rhs != gimple_cond_lhs (cond)) + return false; The check for SSA_NAME is redundant. You fail to check that gimple_cond_rhs is zero. + /* Remove the popcount builtin and cast stmt. */ + gsi = gsi_for_stmt (popcount); + gsi_remove (&gsi, true); + gsi = gsi_for_stmt (cast); + gsi_remove (&gsi, true); + + /* And insert the popcount builtin and cast stmt before the cond_bb. */ + gsi = gsi_last_bb (cond_bb); + gsi_insert_before (&gsi, popcount, GSI_NEW_STMT); + gsi_insert_before (&gsi, cast, GSI_NEW_STMT); use gsi_move_before (). You need to reset flow sensitive info on the LHS of the popcount call as well as on the LHS of the cast. You fail to check the PHI operand on the false edge. Consider if (b != 0) res = __builtin_popcount (b); else res = 1; You fail to check the PHI operand on the true edge. Consider res = 0; if (b != 0) { __builtin_popcount (b); res = 2; } and using -fno-tree-dce and whatever you need to keep the popcount call in the IL. A gimple testcase for phiopt will do. Your testcase relies on popcount detection. Please write it using __builtin_popcount instead. Write one with a cast and one without. Thanks, Richard. > 2018-06-22 Kugan Vivekanandarajah <kuganv@linaro.org> > > * tree-ssa-phiopt.c (cond_removal_in_popcount_pattern): New. > (tree_ssa_phiopt_worker): Call cond_removal_in_popcount_pattern. > > gcc/testsuite/ChangeLog: > > 2018-06-22 Kugan Vivekanandarajah <kuganv@linaro.org> > > * gcc.dg/tree-ssa/popcount3.c: New test.
Hi Richard, Thanks for the review, On 25 June 2018 at 20:20, Richard Biener <richard.guenther@gmail.com> wrote: > On Fri, Jun 22, 2018 at 11:16 AM Kugan Vivekanandarajah > <kugan.vivekanandarajah@linaro.org> wrote: >> >> gcc/ChangeLog: > > @@ -1516,6 +1521,114 @@ minmax_replacement (basic_block cond_bb, > basic_block middle_bb, > > return true; > } > +/* Convert > + > + <bb 2> > + if (b_4(D) != 0) > + goto <bb 3> > > vertical space before the comment. Done. > > + edge e0 ATTRIBUTE_UNUSED, edge e1 > ATTRIBUTE_UNUSED, > > why pass them if they are unused? Removed. > > + if (stmt_count != 2) > + return false; > > so what about the case when there is no conversion? Done. > > + /* Check that we have a popcount builtin. */ > + if (!is_gimple_call (popcount) > + || !gimple_call_builtin_p (popcount, BUILT_IN_NORMAL)) > + return false; > + tree fndecl = gimple_call_fndecl (popcount); > + if ((DECL_FUNCTION_CODE (fndecl) != BUILT_IN_POPCOUNT) > + && (DECL_FUNCTION_CODE (fndecl) != BUILT_IN_POPCOUNTL) > + && (DECL_FUNCTION_CODE (fndecl) != BUILT_IN_POPCOUNTLL)) > + return false; > > look at popcount handling in tree-vrp.c how to properly also handle > IFN_POPCOUNT. > (CASE_CFN_POPCOUNT) Done. > > + /* Cond_bb has a check for b_4 != 0 before calling the popcount > + builtin. */ > + if (gimple_code (cond) != GIMPLE_COND > + || gimple_cond_code (cond) != NE_EXPR > + || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME > + || rhs != gimple_cond_lhs (cond)) > + return false; > > The check for SSA_NAME is redundant. > You fail to check that gimple_cond_rhs is zero. Done. > > + /* Remove the popcount builtin and cast stmt. */ > + gsi = gsi_for_stmt (popcount); > + gsi_remove (&gsi, true); > + gsi = gsi_for_stmt (cast); > + gsi_remove (&gsi, true); > + > + /* And insert the popcount builtin and cast stmt before the cond_bb. */ > + gsi = gsi_last_bb (cond_bb); > + gsi_insert_before (&gsi, popcount, GSI_NEW_STMT); > + gsi_insert_before (&gsi, cast, GSI_NEW_STMT); > > use gsi_move_before (). You need to reset flow sensitive info on the > LHS of the popcount call as well as on the LHS of the cast. Done. > > You fail to check the PHI operand on the false edge. Consider > > if (b != 0) > res = __builtin_popcount (b); > else > res = 1; > > You fail to check the PHI operand on the true edge. Consider > > res = 0; > if (b != 0) > { > __builtin_popcount (b); > res = 2; > } > > and using -fno-tree-dce and whatever you need to keep the > popcount call in the IL. A gimple testcase for phiopt will do. > > Your testcase relies on popcount detection. Please write it > using __builtin_popcount instead. Write one with a cast and > one without. Added the testcases. Is this OK now. Thanks, Kugan > > Thanks, > Richard. > > >> 2018-06-22 Kugan Vivekanandarajah <kuganv@linaro.org> >> >> * tree-ssa-phiopt.c (cond_removal_in_popcount_pattern): New. >> (tree_ssa_phiopt_worker): Call cond_removal_in_popcount_pattern. >> >> gcc/testsuite/ChangeLog: >> >> 2018-06-22 Kugan Vivekanandarajah <kuganv@linaro.org> >> >> * gcc.dg/tree-ssa/popcount3.c: New test. From 5b776871d99161653dbb7a7fc353268ab3be6880 Mon Sep 17 00:00:00 2001 From: Kugan Vivekanandarajah <kugan.vivekanandarajah@linaro.org> Date: Fri, 22 Jun 2018 14:16:21 +1000 Subject: [PATCH 3/3] improve phiopt for builtin popcount Change-Id: Iab8861cc15590cc2603be9967ca9477a223c90a8 --- gcc/testsuite/gcc.dg/tree-ssa/phi-opt-16.c | 12 +++ gcc/testsuite/gcc.dg/tree-ssa/phi-opt-17.c | 12 +++ gcc/testsuite/gcc.dg/tree-ssa/phi-opt-18.c | 14 ++++ gcc/testsuite/gcc.dg/tree-ssa/phi-opt-19.c | 15 ++++ gcc/testsuite/gcc.dg/tree-ssa/popcount3.c | 15 ++++ gcc/tree-ssa-phiopt.c | 127 +++++++++++++++++++++++++++++ 6 files changed, 195 insertions(+) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi-opt-16.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi-opt-17.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi-opt-18.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi-opt-19.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/popcount3.c diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-16.c b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-16.c new file mode 100644 index 0000000..e7a2711 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-16.c @@ -0,0 +1,12 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int foo (int a) +{ + int c = 0; + if (a != 0) + c = __builtin_popcount (a); + return c; +} + +/* { dg-final { scan-tree-dump-not "if" "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-17.c b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-17.c new file mode 100644 index 0000000..25ba096 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-17.c @@ -0,0 +1,12 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int foo (unsigned int a) +{ + int c = 0; + if (a != 0) + c = __builtin_popcount (a); + return c; +} + +/* { dg-final { scan-tree-dump-not "if" "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-18.c b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-18.c new file mode 100644 index 0000000..cf1aaf5 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-18.c @@ -0,0 +1,14 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int foo (int a) +{ + int c = 0; + if (a != 0) + c = __builtin_popcount (a); + else + c = 1; + return c; +} + +/* { dg-final { scan-tree-dump-times "if " 1 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-19.c b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-19.c new file mode 100644 index 0000000..1f44066 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-19.c @@ -0,0 +1,15 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized -fno-tree-dce" } */ + +int foo (int a) +{ + int c = 0; + if (a != 0) + { + __builtin_popcount (a); + c = 2; + } + return c; +} + +/* { dg-final { scan-tree-dump-times "if " 1 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/popcount3.c b/gcc/testsuite/gcc.dg/tree-ssa/popcount3.c new file mode 100644 index 0000000..293beb9 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/popcount3.c @@ -0,0 +1,15 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fdump-tree-phiopt3 -fdump-tree-optimized" } */ + +int PopCount (long b) { + int c = 0; + + while (b) { + b &= b - 1; + c++; + } + return c; +} + +/* { dg-final { scan-tree-dump-times "__builtin_popcount" 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times "if" 0 "phiopt3" } } */ diff --git a/gcc/tree-ssa-phiopt.c b/gcc/tree-ssa-phiopt.c index 8e94f6a..8c8ee04 100644 --- a/gcc/tree-ssa-phiopt.c +++ b/gcc/tree-ssa-phiopt.c @@ -45,6 +45,7 @@ along with GCC; see the file COPYING3. If not see #include "tree-scalar-evolution.h" #include "tree-inline.h" #include "params.h" +#include "case-cfn-macros.h" static unsigned int tree_ssa_phiopt_worker (bool, bool); static bool conditional_replacement (basic_block, basic_block, @@ -57,6 +58,8 @@ static bool minmax_replacement (basic_block, basic_block, edge, edge, gimple *, tree, tree); static bool abs_replacement (basic_block, basic_block, edge, edge, gimple *, tree, tree); +static bool cond_removal_in_popcount_pattern (basic_block, basic_block, + edge, gimple *, tree, tree); static bool cond_store_replacement (basic_block, basic_block, edge, edge, hash_set<tree> *); static bool cond_if_else_store_replacement (basic_block, basic_block, basic_block); @@ -332,6 +335,9 @@ tree_ssa_phiopt_worker (bool do_store_elim, bool do_hoist_loads) cfgchanged = true; else if (abs_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) cfgchanged = true; + else if (cond_removal_in_popcount_pattern (bb, bb1, e2, + phi, arg0, arg1)) + cfgchanged = true; else if (minmax_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) cfgchanged = true; } @@ -1517,6 +1523,127 @@ minmax_replacement (basic_block cond_bb, basic_block middle_bb, return true; } +/* Convert + + <bb 2> + if (b_4(D) != 0) + goto <bb 3> + else + goto <bb 4> + + <bb 3> + _2 = (unsigned long) b_4(D); + _9 = __builtin_popcountl (_2); + OR + _9 = __builtin_popcountl (b_4(D)); + + <bb 4> + c_12 = PHI <0(2), _9(3)> + + Into + <bb 2> + _2 = (unsigned long) b_4(D); + _9 = __builtin_popcountl (_2); + OR + _9 = __builtin_popcountl (b_4(D)); + + <bb 4> + c_12 = PHI <_9(2)> +*/ + +static bool +cond_removal_in_popcount_pattern (basic_block cond_bb, basic_block middle_bb, + edge e2, gimple *phi, tree arg0, tree arg1) +{ + gimple *cond; + gimple_stmt_iterator gsi, gsi_from; + gimple *popcount; + gimple *cast = NULL; + tree lhs, arg; + unsigned stmt_count = 0; + + /* Check that + _2 = (unsigned long) b_4(D); + _9 = __builtin_popcountl (_2); + OR + _9 = __builtin_popcountl (b_4(D)); + are the only stmts in the middle_bb. */ + + for (gsi = gsi_start_bb (middle_bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple *stmt = gsi_stmt (gsi); + if (is_gimple_debug (stmt)) + continue; + stmt_count++; + } + + if (stmt_count != 1 && stmt_count != 2) + return false; + + popcount = last_stmt (middle_bb); + if (popcount == NULL) + return false; + + /* Check that we have a popcount builtin. */ + if (!is_gimple_call (popcount)) + return false; + combined_fn cfn = gimple_call_combined_fn (popcount); + switch (cfn) + { + CASE_CFN_POPCOUNT: + break; + default: + return false; + } + + arg = gimple_call_arg (popcount, 0); + lhs = gimple_get_lhs (popcount); + + if (stmt_count == 2) + { + /* We have a cast stmt feeding popcount builtin. */ + cast = first_stmt (middle_bb); + /* Check that we have a cast prior to that. */ + if (gimple_code (cast) != GIMPLE_ASSIGN + || gimple_assign_rhs_code (cast) != NOP_EXPR) + return false; + /* Result of the cast stmt is the argument to the builtin. */ + if (arg != gimple_assign_lhs (cast)) + return false; + arg = gimple_assign_rhs1 (cast); + } + + /* Check PHI arguments. */ + if (lhs != arg0 || !integer_zerop (arg1)) + return false; + + cond = last_stmt (cond_bb); + + /* Cond_bb has a check for b_4 != 0 before calling the popcount + builtin. */ + if (gimple_code (cond) != GIMPLE_COND + || gimple_cond_code (cond) != NE_EXPR + || !integer_zerop (gimple_cond_rhs (cond)) + || arg != gimple_cond_lhs (cond)) + return false; + + /* And insert the popcount builtin and cast stmt before the cond_bb. */ + gsi = gsi_last_bb (cond_bb); + if (stmt_count == 2) + { + gsi_from = gsi_for_stmt (cast); + gsi_move_before (&gsi_from, &gsi); + reset_flow_sensitive_info (gimple_get_lhs (cast)); + } + gsi_from = gsi_for_stmt (popcount); + gsi_move_before (&gsi_from, &gsi); + reset_flow_sensitive_info (gimple_get_lhs (popcount)); + + /* Now update the PHI and remove unneeded bbs. */ + replace_phi_edge_with_variable (cond_bb, e2, phi, lhs); + return true; +} + /* The function absolute_replacement does the main work of doing the absolute replacement. Return true if the replacement is done. Otherwise return false.
On Wed, Jun 27, 2018 at 7:09 AM Kugan Vivekanandarajah <kugan.vivekanandarajah@linaro.org> wrote: > > Hi Richard, > > Thanks for the review, > > On 25 June 2018 at 20:20, Richard Biener <richard.guenther@gmail.com> wrote: > > On Fri, Jun 22, 2018 at 11:16 AM Kugan Vivekanandarajah > > <kugan.vivekanandarajah@linaro.org> wrote: > >> > >> gcc/ChangeLog: > > > > @@ -1516,6 +1521,114 @@ minmax_replacement (basic_block cond_bb, > > basic_block middle_bb, > > > > return true; > > } > > +/* Convert > > + > > + <bb 2> > > + if (b_4(D) != 0) > > + goto <bb 3> > > > > vertical space before the comment. > Done. > > > > > + edge e0 ATTRIBUTE_UNUSED, edge e1 > > ATTRIBUTE_UNUSED, > > > > why pass them if they are unused? > Removed. > > > > > + if (stmt_count != 2) > > + return false; > > > > so what about the case when there is no conversion? > Done. > > > > > + /* Check that we have a popcount builtin. */ > > + if (!is_gimple_call (popcount) > > + || !gimple_call_builtin_p (popcount, BUILT_IN_NORMAL)) > > + return false; > > + tree fndecl = gimple_call_fndecl (popcount); > > + if ((DECL_FUNCTION_CODE (fndecl) != BUILT_IN_POPCOUNT) > > + && (DECL_FUNCTION_CODE (fndecl) != BUILT_IN_POPCOUNTL) > > + && (DECL_FUNCTION_CODE (fndecl) != BUILT_IN_POPCOUNTLL)) > > + return false; > > > > look at popcount handling in tree-vrp.c how to properly also handle > > IFN_POPCOUNT. > > (CASE_CFN_POPCOUNT) > Done. > > > > + /* Cond_bb has a check for b_4 != 0 before calling the popcount > > + builtin. */ > > + if (gimple_code (cond) != GIMPLE_COND > > + || gimple_cond_code (cond) != NE_EXPR > > + || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME > > + || rhs != gimple_cond_lhs (cond)) > > + return false; > > > > The check for SSA_NAME is redundant. > > You fail to check that gimple_cond_rhs is zero. > Done. > > > > > + /* Remove the popcount builtin and cast stmt. */ > > + gsi = gsi_for_stmt (popcount); > > + gsi_remove (&gsi, true); > > + gsi = gsi_for_stmt (cast); > > + gsi_remove (&gsi, true); > > + > > + /* And insert the popcount builtin and cast stmt before the cond_bb. */ > > + gsi = gsi_last_bb (cond_bb); > > + gsi_insert_before (&gsi, popcount, GSI_NEW_STMT); > > + gsi_insert_before (&gsi, cast, GSI_NEW_STMT); > > > > use gsi_move_before (). You need to reset flow sensitive info on the > > LHS of the popcount call as well as on the LHS of the cast. > Done. > > > > > You fail to check the PHI operand on the false edge. Consider > > > > if (b != 0) > > res = __builtin_popcount (b); > > else > > res = 1; > > > > You fail to check the PHI operand on the true edge. Consider > > > > res = 0; > > if (b != 0) > > { > > __builtin_popcount (b); > > res = 2; > > } > > > > and using -fno-tree-dce and whatever you need to keep the > > popcount call in the IL. A gimple testcase for phiopt will do. > > > > Your testcase relies on popcount detection. Please write it > > using __builtin_popcount instead. Write one with a cast and > > one without. > Added the testcases. > > Is this OK now. + for (gsi = gsi_start_bb (middle_bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { use gsi_after_labels (middle_bb) + popcount = last_stmt (middle_bb); + if (popcount == NULL) + return false; after the counting this test is always false, remove it. + /* We have a cast stmt feeding popcount builtin. */ + cast = first_stmt (middle_bb); looking at the implementation of first_stmt this will give you a label in case the BB has one. I think it's better to merge this and the above with the "counting" like gsi = gsi_start_nondebug_after_labels_bb (middle_bb); if (gsi_end_p (gsi)) return false; cast = gsi_stmt (gsi); gsi_next_nondebug (&gsi); if (!gsi_end_p (gsi)) { popcount = gsi_stmt (gsi); gsi_next_nondebug (&gsi); if (!gsi_end_p (gsi)) return false; } else { popcount = cast; cast = NULL; } + /* Check that we have a cast prior to that. */ + if (gimple_code (cast) != GIMPLE_ASSIGN + || gimple_assign_rhs_code (cast) != NOP_EXPR) + return false; CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (cast)) + /* Check PHI arguments. */ + if (lhs != arg0 || !integer_zerop (arg1)) + return false; that is not sufficient, you do not know whether arg0 is the true value or the false value. The edge flags will tell you. Otherwise looks OK. Richard. > Thanks, > Kugan > > > > Thanks, > > Richard. > > > > > >> 2018-06-22 Kugan Vivekanandarajah <kuganv@linaro.org> > >> > >> * tree-ssa-phiopt.c (cond_removal_in_popcount_pattern): New. > >> (tree_ssa_phiopt_worker): Call cond_removal_in_popcount_pattern. > >> > >> gcc/testsuite/ChangeLog: > >> > >> 2018-06-22 Kugan Vivekanandarajah <kuganv@linaro.org> > >> > >> * gcc.dg/tree-ssa/popcount3.c: New test.
Hi Richard, On 29 June 2018 at 18:45, Richard Biener <richard.guenther@gmail.com> wrote: > On Wed, Jun 27, 2018 at 7:09 AM Kugan Vivekanandarajah > <kugan.vivekanandarajah@linaro.org> wrote: >> >> Hi Richard, >> >> Thanks for the review, >> >> On 25 June 2018 at 20:20, Richard Biener <richard.guenther@gmail.com> wrote: >> > On Fri, Jun 22, 2018 at 11:16 AM Kugan Vivekanandarajah >> > <kugan.vivekanandarajah@linaro.org> wrote: >> >> >> >> gcc/ChangeLog: >> > >> > @@ -1516,6 +1521,114 @@ minmax_replacement (basic_block cond_bb, >> > basic_block middle_bb, >> > >> > return true; >> > } >> > +/* Convert >> > + >> > + <bb 2> >> > + if (b_4(D) != 0) >> > + goto <bb 3> >> > >> > vertical space before the comment. >> Done. >> >> > >> > + edge e0 ATTRIBUTE_UNUSED, edge e1 >> > ATTRIBUTE_UNUSED, >> > >> > why pass them if they are unused? >> Removed. >> >> > >> > + if (stmt_count != 2) >> > + return false; >> > >> > so what about the case when there is no conversion? >> Done. >> >> > >> > + /* Check that we have a popcount builtin. */ >> > + if (!is_gimple_call (popcount) >> > + || !gimple_call_builtin_p (popcount, BUILT_IN_NORMAL)) >> > + return false; >> > + tree fndecl = gimple_call_fndecl (popcount); >> > + if ((DECL_FUNCTION_CODE (fndecl) != BUILT_IN_POPCOUNT) >> > + && (DECL_FUNCTION_CODE (fndecl) != BUILT_IN_POPCOUNTL) >> > + && (DECL_FUNCTION_CODE (fndecl) != BUILT_IN_POPCOUNTLL)) >> > + return false; >> > >> > look at popcount handling in tree-vrp.c how to properly also handle >> > IFN_POPCOUNT. >> > (CASE_CFN_POPCOUNT) >> Done. >> > >> > + /* Cond_bb has a check for b_4 != 0 before calling the popcount >> > + builtin. */ >> > + if (gimple_code (cond) != GIMPLE_COND >> > + || gimple_cond_code (cond) != NE_EXPR >> > + || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME >> > + || rhs != gimple_cond_lhs (cond)) >> > + return false; >> > >> > The check for SSA_NAME is redundant. >> > You fail to check that gimple_cond_rhs is zero. >> Done. >> >> > >> > + /* Remove the popcount builtin and cast stmt. */ >> > + gsi = gsi_for_stmt (popcount); >> > + gsi_remove (&gsi, true); >> > + gsi = gsi_for_stmt (cast); >> > + gsi_remove (&gsi, true); >> > + >> > + /* And insert the popcount builtin and cast stmt before the cond_bb. */ >> > + gsi = gsi_last_bb (cond_bb); >> > + gsi_insert_before (&gsi, popcount, GSI_NEW_STMT); >> > + gsi_insert_before (&gsi, cast, GSI_NEW_STMT); >> > >> > use gsi_move_before (). You need to reset flow sensitive info on the >> > LHS of the popcount call as well as on the LHS of the cast. >> Done. >> >> > >> > You fail to check the PHI operand on the false edge. Consider >> > >> > if (b != 0) >> > res = __builtin_popcount (b); >> > else >> > res = 1; >> > >> > You fail to check the PHI operand on the true edge. Consider >> > >> > res = 0; >> > if (b != 0) >> > { >> > __builtin_popcount (b); >> > res = 2; >> > } >> > >> > and using -fno-tree-dce and whatever you need to keep the >> > popcount call in the IL. A gimple testcase for phiopt will do. >> > >> > Your testcase relies on popcount detection. Please write it >> > using __builtin_popcount instead. Write one with a cast and >> > one without. >> Added the testcases. >> >> Is this OK now. > > + for (gsi = gsi_start_bb (middle_bb); !gsi_end_p (gsi); gsi_next (&gsi)) > + { > > use gsi_after_labels (middle_bb) > > + popcount = last_stmt (middle_bb); > + if (popcount == NULL) > + return false; > > after the counting this test is always false, remove it. > > + /* We have a cast stmt feeding popcount builtin. */ > + cast = first_stmt (middle_bb); > > looking at the implementation of first_stmt this will > give you a label in case the BB has one. I think it's better > to merge this and the above with the "counting" like > > gsi = gsi_start_nondebug_after_labels_bb (middle_bb); > if (gsi_end_p (gsi)) > return false; > cast = gsi_stmt (gsi); > gsi_next_nondebug (&gsi); > if (!gsi_end_p (gsi)) > { > popcount = gsi_stmt (gsi); > gsi_next_nondebug (&gsi); > if (!gsi_end_p (gsi)) > return false; > } > else > { > popcount = cast; > cast = NULL; > } Done. > > + /* Check that we have a cast prior to that. */ > + if (gimple_code (cast) != GIMPLE_ASSIGN > + || gimple_assign_rhs_code (cast) != NOP_EXPR) > + return false; > > CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (cast)) > Done. > + /* Check PHI arguments. */ > + if (lhs != arg0 || !integer_zerop (arg1)) > + return false; > > that is not sufficient, you do not know whether arg0 is the true > value or the false value. The edge flags will tell you. Done. Please find the modified patch. Is this OK. Bootstrapped and regression tested with no new regressions. Thanks, Kugan > > Otherwise looks OK. > > Richard. > >> Thanks, >> Kugan >> > >> > Thanks, >> > Richard. >> > >> > >> >> 2018-06-22 Kugan Vivekanandarajah <kuganv@linaro.org> >> >> >> >> * tree-ssa-phiopt.c (cond_removal_in_popcount_pattern): New. >> >> (tree_ssa_phiopt_worker): Call cond_removal_in_popcount_pattern. >> >> >> >> gcc/testsuite/ChangeLog: >> >> >> >> 2018-06-22 Kugan Vivekanandarajah <kuganv@linaro.org> >> >> >> >> * gcc.dg/tree-ssa/popcount3.c: New test. From 1c84a02d568216ecef7ad44f4114ca34f29c537e Mon Sep 17 00:00:00 2001 From: Kugan Vivekanandarajah <kugan.vivekanandarajah@linaro.org> Date: Fri, 22 Jun 2018 14:16:21 +1000 Subject: [PATCH 3/3] improve phiopt for builtin popcount Change-Id: Ibad062599eb04f96cd582bab34203bcf84273fe9 --- gcc/testsuite/gcc.dg/tree-ssa/phi-opt-16.c | 12 +++ gcc/testsuite/gcc.dg/tree-ssa/phi-opt-17.c | 12 +++ gcc/testsuite/gcc.dg/tree-ssa/phi-opt-18.c | 14 +++ gcc/testsuite/gcc.dg/tree-ssa/phi-opt-19.c | 15 ++++ gcc/testsuite/gcc.dg/tree-ssa/popcount3.c | 15 ++++ gcc/tree-ssa-phiopt.c | 136 +++++++++++++++++++++++++++++ 6 files changed, 204 insertions(+) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi-opt-16.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi-opt-17.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi-opt-18.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi-opt-19.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/popcount3.c diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-16.c b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-16.c new file mode 100644 index 0000000..e7a2711 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-16.c @@ -0,0 +1,12 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int foo (int a) +{ + int c = 0; + if (a != 0) + c = __builtin_popcount (a); + return c; +} + +/* { dg-final { scan-tree-dump-not "if" "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-17.c b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-17.c new file mode 100644 index 0000000..25ba096 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-17.c @@ -0,0 +1,12 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int foo (unsigned int a) +{ + int c = 0; + if (a != 0) + c = __builtin_popcount (a); + return c; +} + +/* { dg-final { scan-tree-dump-not "if" "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-18.c b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-18.c new file mode 100644 index 0000000..cf1aaf5 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-18.c @@ -0,0 +1,14 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int foo (int a) +{ + int c = 0; + if (a != 0) + c = __builtin_popcount (a); + else + c = 1; + return c; +} + +/* { dg-final { scan-tree-dump-times "if " 1 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-19.c b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-19.c new file mode 100644 index 0000000..1f44066 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-19.c @@ -0,0 +1,15 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized -fno-tree-dce" } */ + +int foo (int a) +{ + int c = 0; + if (a != 0) + { + __builtin_popcount (a); + c = 2; + } + return c; +} + +/* { dg-final { scan-tree-dump-times "if " 1 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/popcount3.c b/gcc/testsuite/gcc.dg/tree-ssa/popcount3.c new file mode 100644 index 0000000..293beb9 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/popcount3.c @@ -0,0 +1,15 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fdump-tree-phiopt3 -fdump-tree-optimized" } */ + +int PopCount (long b) { + int c = 0; + + while (b) { + b &= b - 1; + c++; + } + return c; +} + +/* { dg-final { scan-tree-dump-times "__builtin_popcount" 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times "if" 0 "phiopt3" } } */ diff --git a/gcc/tree-ssa-phiopt.c b/gcc/tree-ssa-phiopt.c index 8e94f6a..b2575f1 100644 --- a/gcc/tree-ssa-phiopt.c +++ b/gcc/tree-ssa-phiopt.c @@ -45,6 +45,7 @@ along with GCC; see the file COPYING3. If not see #include "tree-scalar-evolution.h" #include "tree-inline.h" #include "params.h" +#include "case-cfn-macros.h" static unsigned int tree_ssa_phiopt_worker (bool, bool); static bool conditional_replacement (basic_block, basic_block, @@ -57,6 +58,8 @@ static bool minmax_replacement (basic_block, basic_block, edge, edge, gimple *, tree, tree); static bool abs_replacement (basic_block, basic_block, edge, edge, gimple *, tree, tree); +static bool cond_removal_in_popcount_pattern (basic_block, basic_block, + edge, edge, gimple *, tree, tree); static bool cond_store_replacement (basic_block, basic_block, edge, edge, hash_set<tree> *); static bool cond_if_else_store_replacement (basic_block, basic_block, basic_block); @@ -332,6 +335,9 @@ tree_ssa_phiopt_worker (bool do_store_elim, bool do_hoist_loads) cfgchanged = true; else if (abs_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) cfgchanged = true; + else if (cond_removal_in_popcount_pattern (bb, bb1, e1, e2, + phi, arg0, arg1)) + cfgchanged = true; else if (minmax_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) cfgchanged = true; } @@ -1517,6 +1523,136 @@ minmax_replacement (basic_block cond_bb, basic_block middle_bb, return true; } +/* Convert + + <bb 2> + if (b_4(D) != 0) + goto <bb 3> + else + goto <bb 4> + + <bb 3> + _2 = (unsigned long) b_4(D); + _9 = __builtin_popcountl (_2); + OR + _9 = __builtin_popcountl (b_4(D)); + + <bb 4> + c_12 = PHI <0(2), _9(3)> + + Into + <bb 2> + _2 = (unsigned long) b_4(D); + _9 = __builtin_popcountl (_2); + OR + _9 = __builtin_popcountl (b_4(D)); + + <bb 4> + c_12 = PHI <_9(2)> +*/ + +static bool +cond_removal_in_popcount_pattern (basic_block cond_bb, basic_block middle_bb, + edge e1, edge e2, + gimple *phi, tree arg0, tree arg1) +{ + gimple *cond; + gimple_stmt_iterator gsi, gsi_from; + gimple *popcount; + gimple *cast = NULL; + tree lhs, arg; + + /* Check that + _2 = (unsigned long) b_4(D); + _9 = __builtin_popcountl (_2); + OR + _9 = __builtin_popcountl (b_4(D)); + are the only stmts in the middle_bb. */ + + gsi = gsi_start_nondebug_after_labels_bb (middle_bb); + if (gsi_end_p (gsi)) + return false; + cast = gsi_stmt (gsi); + gsi_next_nondebug (&gsi); + if (!gsi_end_p (gsi)) + { + popcount = gsi_stmt (gsi); + gsi_next_nondebug (&gsi); + if (!gsi_end_p (gsi)) + return false; + } + else + { + popcount = cast; + cast = NULL; + } + + /* Check that we have a popcount builtin. */ + if (!is_gimple_call (popcount)) + return false; + combined_fn cfn = gimple_call_combined_fn (popcount); + switch (cfn) + { + CASE_CFN_POPCOUNT: + break; + default: + return false; + } + + arg = gimple_call_arg (popcount, 0); + lhs = gimple_get_lhs (popcount); + + if (cast) + { + /* We have a cast stmt feeding popcount builtin. */ + /* Check that we have a cast prior to that. */ + if (gimple_code (cast) != GIMPLE_ASSIGN + || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (cast))) + return false; + /* Result of the cast stmt is the argument to the builtin. */ + if (arg != gimple_assign_lhs (cast)) + return false; + arg = gimple_assign_rhs1 (cast); + } + + /* Canonicalize. */ + if (e2->flags & EDGE_TRUE_VALUE) + { + std::swap (arg0, arg1); + std::swap (e1, e2); + } + + /* Check PHI arguments. */ + if (lhs != arg0 || !integer_zerop (arg1)) + return false; + + cond = last_stmt (cond_bb); + + /* Cond_bb has a check for b_4 != 0 before calling the popcount + builtin. */ + if (gimple_code (cond) != GIMPLE_COND + || gimple_cond_code (cond) != NE_EXPR + || !integer_zerop (gimple_cond_rhs (cond)) + || arg != gimple_cond_lhs (cond)) + return false; + + /* And insert the popcount builtin and cast stmt before the cond_bb. */ + gsi = gsi_last_bb (cond_bb); + if (cast) + { + gsi_from = gsi_for_stmt (cast); + gsi_move_before (&gsi_from, &gsi); + reset_flow_sensitive_info (gimple_get_lhs (cast)); + } + gsi_from = gsi_for_stmt (popcount); + gsi_move_before (&gsi_from, &gsi); + reset_flow_sensitive_info (gimple_get_lhs (popcount)); + + /* Now update the PHI and remove unneeded bbs. */ + replace_phi_edge_with_variable (cond_bb, e2, phi, lhs); + return true; +} + /* The function absolute_replacement does the main work of doing the absolute replacement. Return true if the replacement is done. Otherwise return false.
On Mon, Jul 2, 2018 at 3:15 AM Kugan Vivekanandarajah <kugan.vivekanandarajah@linaro.org> wrote: > > Hi Richard, > > On 29 June 2018 at 18:45, Richard Biener <richard.guenther@gmail.com> wrote: > > On Wed, Jun 27, 2018 at 7:09 AM Kugan Vivekanandarajah > > <kugan.vivekanandarajah@linaro.org> wrote: > >> > >> Hi Richard, > >> > >> Thanks for the review, > >> > >> On 25 June 2018 at 20:20, Richard Biener <richard.guenther@gmail.com> wrote: > >> > On Fri, Jun 22, 2018 at 11:16 AM Kugan Vivekanandarajah > >> > <kugan.vivekanandarajah@linaro.org> wrote: > >> >> > >> >> gcc/ChangeLog: > >> > > >> > @@ -1516,6 +1521,114 @@ minmax_replacement (basic_block cond_bb, > >> > basic_block middle_bb, > >> > > >> > return true; > >> > } > >> > +/* Convert > >> > + > >> > + <bb 2> > >> > + if (b_4(D) != 0) > >> > + goto <bb 3> > >> > > >> > vertical space before the comment. > >> Done. > >> > >> > > >> > + edge e0 ATTRIBUTE_UNUSED, edge e1 > >> > ATTRIBUTE_UNUSED, > >> > > >> > why pass them if they are unused? > >> Removed. > >> > >> > > >> > + if (stmt_count != 2) > >> > + return false; > >> > > >> > so what about the case when there is no conversion? > >> Done. > >> > >> > > >> > + /* Check that we have a popcount builtin. */ > >> > + if (!is_gimple_call (popcount) > >> > + || !gimple_call_builtin_p (popcount, BUILT_IN_NORMAL)) > >> > + return false; > >> > + tree fndecl = gimple_call_fndecl (popcount); > >> > + if ((DECL_FUNCTION_CODE (fndecl) != BUILT_IN_POPCOUNT) > >> > + && (DECL_FUNCTION_CODE (fndecl) != BUILT_IN_POPCOUNTL) > >> > + && (DECL_FUNCTION_CODE (fndecl) != BUILT_IN_POPCOUNTLL)) > >> > + return false; > >> > > >> > look at popcount handling in tree-vrp.c how to properly also handle > >> > IFN_POPCOUNT. > >> > (CASE_CFN_POPCOUNT) > >> Done. > >> > > >> > + /* Cond_bb has a check for b_4 != 0 before calling the popcount > >> > + builtin. */ > >> > + if (gimple_code (cond) != GIMPLE_COND > >> > + || gimple_cond_code (cond) != NE_EXPR > >> > + || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME > >> > + || rhs != gimple_cond_lhs (cond)) > >> > + return false; > >> > > >> > The check for SSA_NAME is redundant. > >> > You fail to check that gimple_cond_rhs is zero. > >> Done. > >> > >> > > >> > + /* Remove the popcount builtin and cast stmt. */ > >> > + gsi = gsi_for_stmt (popcount); > >> > + gsi_remove (&gsi, true); > >> > + gsi = gsi_for_stmt (cast); > >> > + gsi_remove (&gsi, true); > >> > + > >> > + /* And insert the popcount builtin and cast stmt before the cond_bb. */ > >> > + gsi = gsi_last_bb (cond_bb); > >> > + gsi_insert_before (&gsi, popcount, GSI_NEW_STMT); > >> > + gsi_insert_before (&gsi, cast, GSI_NEW_STMT); > >> > > >> > use gsi_move_before (). You need to reset flow sensitive info on the > >> > LHS of the popcount call as well as on the LHS of the cast. > >> Done. > >> > >> > > >> > You fail to check the PHI operand on the false edge. Consider > >> > > >> > if (b != 0) > >> > res = __builtin_popcount (b); > >> > else > >> > res = 1; > >> > > >> > You fail to check the PHI operand on the true edge. Consider > >> > > >> > res = 0; > >> > if (b != 0) > >> > { > >> > __builtin_popcount (b); > >> > res = 2; > >> > } > >> > > >> > and using -fno-tree-dce and whatever you need to keep the > >> > popcount call in the IL. A gimple testcase for phiopt will do. > >> > > >> > Your testcase relies on popcount detection. Please write it > >> > using __builtin_popcount instead. Write one with a cast and > >> > one without. > >> Added the testcases. > >> > >> Is this OK now. > > > > + for (gsi = gsi_start_bb (middle_bb); !gsi_end_p (gsi); gsi_next (&gsi)) > > + { > > > > use gsi_after_labels (middle_bb) > > > > + popcount = last_stmt (middle_bb); > > + if (popcount == NULL) > > + return false; > > > > after the counting this test is always false, remove it. > > > > + /* We have a cast stmt feeding popcount builtin. */ > > + cast = first_stmt (middle_bb); > > > > looking at the implementation of first_stmt this will > > give you a label in case the BB has one. I think it's better > > to merge this and the above with the "counting" like > > > > gsi = gsi_start_nondebug_after_labels_bb (middle_bb); > > if (gsi_end_p (gsi)) > > return false; > > cast = gsi_stmt (gsi); > > gsi_next_nondebug (&gsi); > > if (!gsi_end_p (gsi)) > > { > > popcount = gsi_stmt (gsi); > > gsi_next_nondebug (&gsi); > > if (!gsi_end_p (gsi)) > > return false; > > } > > else > > { > > popcount = cast; > > cast = NULL; > > } > > Done. > > > > + /* Check that we have a cast prior to that. */ > > + if (gimple_code (cast) != GIMPLE_ASSIGN > > + || gimple_assign_rhs_code (cast) != NOP_EXPR) > > + return false; > > > > CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (cast)) > > > Done. > > > + /* Check PHI arguments. */ > > + if (lhs != arg0 || !integer_zerop (arg1)) > > + return false; > > > > that is not sufficient, you do not know whether arg0 is the true > > value or the false value. The edge flags will tell you. > > Done. > > Please find the modified patch. Is this OK. Bootstrapped and > regression tested with no new regressions. OK. Richard. > Thanks, > Kugan > > > > Otherwise looks OK. > > > > Richard. > > > >> Thanks, > >> Kugan > >> > > >> > Thanks, > >> > Richard. > >> > > >> > > >> >> 2018-06-22 Kugan Vivekanandarajah <kuganv@linaro.org> > >> >> > >> >> * tree-ssa-phiopt.c (cond_removal_in_popcount_pattern): New. > >> >> (tree_ssa_phiopt_worker): Call cond_removal_in_popcount_pattern. > >> >> > >> >> gcc/testsuite/ChangeLog: > >> >> > >> >> 2018-06-22 Kugan Vivekanandarajah <kuganv@linaro.org> > >> >> > >> >> * gcc.dg/tree-ssa/popcount3.c: New test.
From fa2cca6b186b70668a3334c23ea4b906dac454d4 Mon Sep 17 00:00:00 2001 From: Kugan Vivekanandarajah <kugan.vivekanandarajah@linaro.org> Date: Fri, 22 Jun 2018 14:16:21 +1000 Subject: [PATCH 3/3] improve phiopt for builtin popcount Change-Id: Id1a5997c78fc3ceded3ed7fb0c544ce2bd1a2b34 --- gcc/testsuite/gcc.dg/tree-ssa/popcount3.c | 15 ++++ gcc/tree-ssa-phiopt.c | 113 ++++++++++++++++++++++++++++++ 2 files changed, 128 insertions(+) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/popcount3.c diff --git a/gcc/testsuite/gcc.dg/tree-ssa/popcount3.c b/gcc/testsuite/gcc.dg/tree-ssa/popcount3.c new file mode 100644 index 0000000..293beb9 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/popcount3.c @@ -0,0 +1,15 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fdump-tree-phiopt3 -fdump-tree-optimized" } */ + +int PopCount (long b) { + int c = 0; + + while (b) { + b &= b - 1; + c++; + } + return c; +} + +/* { dg-final { scan-tree-dump-times "__builtin_popcount" 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times "if" 0 "phiopt3" } } */ diff --git a/gcc/tree-ssa-phiopt.c b/gcc/tree-ssa-phiopt.c index 8e94f6a..1db5226 100644 --- a/gcc/tree-ssa-phiopt.c +++ b/gcc/tree-ssa-phiopt.c @@ -57,6 +57,8 @@ static bool minmax_replacement (basic_block, basic_block, edge, edge, gimple *, tree, tree); static bool abs_replacement (basic_block, basic_block, edge, edge, gimple *, tree, tree); +static bool cond_removal_in_popcount_pattern (basic_block, basic_block, + edge, edge, gimple *, tree, tree); static bool cond_store_replacement (basic_block, basic_block, edge, edge, hash_set<tree> *); static bool cond_if_else_store_replacement (basic_block, basic_block, basic_block); @@ -332,6 +334,9 @@ tree_ssa_phiopt_worker (bool do_store_elim, bool do_hoist_loads) cfgchanged = true; else if (abs_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) cfgchanged = true; + else if (cond_removal_in_popcount_pattern (bb, bb1, e1, e2, + phi, arg0, arg1)) + cfgchanged = true; else if (minmax_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) cfgchanged = true; } @@ -1516,6 +1521,114 @@ minmax_replacement (basic_block cond_bb, basic_block middle_bb, return true; } +/* Convert + + <bb 2> + if (b_4(D) != 0) + goto <bb 3> + else + goto <bb 4> + + <bb 3> + _2 = (unsigned long) b_4(D); + _9 = __builtin_popcountl (_2); + + <bb 4> + c_12 = PHI <0(2), _9(3)> + + Into + <bb 2> + _2 = (unsigned long) b_4(D); + _9 = __builtin_popcountl (_2); + + <bb 4> + c_12 = PHI <_9(2)> +*/ + +static bool +cond_removal_in_popcount_pattern (basic_block cond_bb, basic_block middle_bb, + edge e0 ATTRIBUTE_UNUSED, edge e1 ATTRIBUTE_UNUSED, + gimple *phi, tree arg0, tree arg1) +{ + gimple *cond; + gimple_stmt_iterator gsi; + gimple *popcount; + gimple *cast; + tree rhs, lhs, arg; + unsigned stmt_count = 0; + + /* Check that + _2 = (unsigned long) b_4(D); + _9 = __builtin_popcountl (_2); + are the only stmts in the middle_bb. */ + + for (gsi = gsi_start_bb (middle_bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple *stmt = gsi_stmt (gsi); + if (is_gimple_debug (stmt)) + continue; + stmt_count++; + } + if (stmt_count != 2) + return false; + + cast = first_stmt (middle_bb); + popcount = last_stmt (middle_bb); + if (popcount == NULL || cast == NULL) + return false; + + /* Check that we have a popcount builtin. */ + if (!is_gimple_call (popcount) + || !gimple_call_builtin_p (popcount, BUILT_IN_NORMAL)) + return false; + tree fndecl = gimple_call_fndecl (popcount); + if ((DECL_FUNCTION_CODE (fndecl) != BUILT_IN_POPCOUNT) + && (DECL_FUNCTION_CODE (fndecl) != BUILT_IN_POPCOUNTL) + && (DECL_FUNCTION_CODE (fndecl) != BUILT_IN_POPCOUNTLL)) + return false; + + /* Check that we have a cast prior to that. */ + if (gimple_code (cast) != GIMPLE_ASSIGN + || gimple_assign_rhs_code (cast) != NOP_EXPR) + return false; + + rhs = gimple_assign_rhs1 (cast); + lhs = gimple_get_lhs (popcount); + arg = gimple_call_arg (popcount, 0); + + /* Result of the cast stmt is the argument to the builtin. */ + if (arg != gimple_assign_lhs (cast)) + return false; + + if (lhs != arg0 + && lhs != arg1) + return false; + + cond = last_stmt (cond_bb); + + /* Cond_bb has a check for b_4 != 0 before calling the popcount + builtin. */ + if (gimple_code (cond) != GIMPLE_COND + || gimple_cond_code (cond) != NE_EXPR + || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME + || rhs != gimple_cond_lhs (cond)) + return false; + + /* Remove the popcount builtin and cast stmt. */ + gsi = gsi_for_stmt (popcount); + gsi_remove (&gsi, true); + gsi = gsi_for_stmt (cast); + gsi_remove (&gsi, true); + + /* And insert the popcount builtin and cast stmt before the cond_bb. */ + gsi = gsi_last_bb (cond_bb); + gsi_insert_before (&gsi, popcount, GSI_NEW_STMT); + gsi_insert_before (&gsi, cast, GSI_NEW_STMT); + + /* Now update the PHI and remove unneeded bbs. */ + replace_phi_edge_with_variable (cond_bb, e1, phi, lhs); + return true; +} /* The function absolute_replacement does the main work of doing the absolute replacement. Return true if the replacement is done. Otherwise return -- 2.7.4
gcc/ChangeLog: 2018-06-22 Kugan Vivekanandarajah <kuganv@linaro.org> * tree-ssa-phiopt.c (cond_removal_in_popcount_pattern): New. (tree_ssa_phiopt_worker): Call cond_removal_in_popcount_pattern. gcc/testsuite/ChangeLog: 2018-06-22 Kugan Vivekanandarajah <kuganv@linaro.org> * gcc.dg/tree-ssa/popcount3.c: New test.