Hi Richard,
Thanks for the review,
On 25 June 2018 at 20:20, Richard Biener <richard.guent...@gmail.com> wrote:
> On Fri, Jun 22, 2018 at 11:16 AM Kugan Vivekanandarajah
> <kugan.vivekanandara...@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 <kug...@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 <kug...@linaro.org>
>>
>> * gcc.dg/tree-ssa/popcount3.c: New test.
From 5b776871d99161653dbb7a7fc353268ab3be6880 Mon Sep 17 00:00:00 2001
From: Kugan Vivekanandarajah <kugan.vivekanandara...@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.
--
2.7.4
