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

