Hi Richard, On 29 June 2018 at 18:45, Richard Biener <[email protected]> wrote: > On Wed, Jun 27, 2018 at 7:09 AM Kugan Vivekanandarajah > <[email protected]> wrote: >> >> Hi Richard, >> >> Thanks for the review, >> >> On 25 June 2018 at 20:20, Richard Biener <[email protected]> wrote: >> > On Fri, Jun 22, 2018 at 11:16 AM Kugan Vivekanandarajah >> > <[email protected]> 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 <[email protected]> >> >> >> >> * 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 <[email protected]> >> >> >> >> * gcc.dg/tree-ssa/popcount3.c: New test.
From 1c84a02d568216ecef7ad44f4114ca34f29c537e Mon Sep 17 00:00:00 2001 From: Kugan Vivekanandarajah <[email protected]> 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. -- 2.7.4
