This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH 3/3][POPCOUNT] Remove unnecessary if condition in phiopt


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.
-- 
2.7.4


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]