Re: [RFC][PR82479] missing popcount builtin detection

[Kugan Vivekanandarajah <kugan dot vivekanandarajah at linaro dot org>]

Hi Bin,

Thanks a lo for the review.

On 1 June 2018 at 03:45, Bin.Cheng <amker.cheng@gmail.com> wrote:
> On Thu, May 31, 2018 at 3:51 AM, Kugan Vivekanandarajah
> <kugan.vivekanandarajah@linaro.org> wrote:
>> Hi Bin,
>>
>> Thanks for the review. Please find the revised patch based on the
>> review comments.
>>
>> Thanks,
>> Kugan
>>
>> On 17 May 2018 at 19:56, Bin.Cheng <amker.cheng@gmail.com> wrote:
>>> On Thu, May 17, 2018 at 2:39 AM, Kugan Vivekanandarajah
>>> <kugan.vivekanandarajah@linaro.org> wrote:
>>>> Hi Richard,
>>>>
>>>> On 6 March 2018 at 02:24, Richard Biener <richard.guenther@gmail.com> wrote:
>>>>> On Thu, Feb 8, 2018 at 1:41 AM, Kugan Vivekanandarajah
>>>>> <kugan.vivekanandarajah@linaro.org> wrote:
>>>>>> Hi Richard,
>>>>>>
>
> Hi,
> Thanks very much for working.
>
>> +/* Utility function to check if OP is defined by a stmt
>> +   that is a val - 1.  If that is the case, set it to STMT.  */
>> +
>> +static bool
>> +ssa_defined_by_and_minus_one_stmt_p (tree op, tree val, gimple **stmt)
> This is checking if op is defined as val - 1, so name it as
> ssa_defined_by_minus_one_stmt_p?
>
>> +{
>> +  if (TREE_CODE (op) == SSA_NAME
>> +      && (*stmt = SSA_NAME_DEF_STMT (op))
>> +      && is_gimple_assign (*stmt)
>> +      && (gimple_assign_rhs_code (*stmt) == PLUS_EXPR)
>> +      && val == gimple_assign_rhs1 (*stmt)
>> +      && integer_minus_onep (gimple_assign_rhs2 (*stmt)))
>> +    return true;
>> +  else
>> +    return false;
> You can simply return the boolean condition.
Done.

>
>> +}
>> +
>> +/* See if LOOP is a popcout implementation of the form
> ...
>> +  rhs1 = gimple_assign_rhs1 (and_stmt);
>> +  rhs2 = gimple_assign_rhs2 (and_stmt);
>> +
>> +  if (ssa_defined_by_and_minus_one_stmt_p (rhs1, rhs2, &and_minus_one))
>> +    rhs1 = rhs2;
>> +  else if (ssa_defined_by_and_minus_one_stmt_p (rhs2, rhs1, &and_minus_one))
>> +    ;
>> +  else
>> +    return false;
>> +
>> +  /* Check the recurrence.  */
>> +  phi = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (and_minus_one));
> So gimple_assign_rhs1 (and_minus_one) == rhs1 is always true?  Please
> use rhs1 directly.

Done.
>> +  gimple *src_phi = SSA_NAME_DEF_STMT (rhs2);
> I think this is checking wrong thing and is redundant.  Either rhs2
> equals to rhs1 or is defined as (rhs1 - 1).  For (rhs2 == rhs1) case,
> the check duplicates checking on phi; for the latter, it's never a PHI
> stmt and shouldn't be checked.
>
>> +  if (gimple_code (phi) != GIMPLE_PHI
>> +      || gimple_code (src_phi) != GIMPLE_PHI)
>> +    return false;
>> +
>> +  dest = gimple_assign_lhs (count_stmt);
>> +  tree fn = builtin_decl_implicit (BUILT_IN_POPCOUNT);
>> +  tree src = gimple_phi_arg_def (src_phi, loop_preheader_edge (loop)->dest_idx);
>> +  if (adjust)
>> +    iter = fold_build2 (MINUS_EXPR, TREE_TYPE (dest),
>> +            build_call_expr (fn, 1, src),
>> +            build_int_cst (TREE_TYPE (dest), 1));
>> +  else
>> +    iter = build_call_expr (fn, 1, src);
> Note tree-ssa-loop-niters.c always use unsigned_type_for (IV-type) as
> niters type.  Though unsigned type is unnecessary in this case, but
> better to follow existing behavior?

Done.
>
>> +  max = int_cst_value (TYPE_MAX_VALUE (TREE_TYPE (dest)));
> As richi suggested, max should be the number of bits in type of IV.
>
>> +
>> +  niter->assumptions = boolean_false_node;
> Redundant.

Not sure I understand. If I remove this,  I am getting ICE
(segmentation fault). What is the expectation here?

>> +  niter->control.base = NULL_TREE;
>> +  niter->control.step = NULL_TREE;
>> +  niter->control.no_overflow = false;
>> +  niter->niter = iter;
>> +  niter->assumptions = boolean_true_node;
>> +  niter->may_be_zero = boolean_false_node;
>> +  niter->max = max;
>> +  niter->bound = NULL_TREE;
>> +  niter->cmp = ERROR_MARK;
>> +  return true;
>> +}
>> +
>> +
> Appology if these are nitpickings.
Thanks for the review. I am happy to make the changes needed to get it
to how it should be :)

Thanks,
Kugan

>
> Thanks,
> bin

From f45179c777d846731d2d899a142c45a36ab35fd1 Mon Sep 17 00:00:00 2001
From: Kugan Vivekanandarajah <kugan.vivekanandarajah@linaro.org>
Date: Thu, 10 May 2018 21:41:53 +1000
Subject: [PATCH] popcount

Change-Id: I10c1f990e5b9c9900cf7c93678df924f0463b72e
---
 gcc/ipa-fnsummary.c                       |   4 +
 gcc/testsuite/gcc.dg/tree-ssa/popcount.c  |  41 ++++++++
 gcc/testsuite/gcc.dg/tree-ssa/popcount2.c |  29 ++++++
 gcc/testsuite/gcc.dg/tree-ssa/popcount3.c |  28 ++++++
 gcc/tree-scalar-evolution.c               |   7 ++
 gcc/tree-ssa-loop-ivopts.c                |  10 ++
 gcc/tree-ssa-loop-niter.c                 | 152 +++++++++++++++++++++++++++++-
 7 files changed, 270 insertions(+), 1 deletion(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/popcount.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/popcount2.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/popcount3.c

diff --git a/gcc/ipa-fnsummary.c b/gcc/ipa-fnsummary.c
index bdf9ba1..4dc156a 100644
--- a/gcc/ipa-fnsummary.c
+++ b/gcc/ipa-fnsummary.c
@@ -1485,6 +1485,10 @@ will_be_nonconstant_expr_predicate (struct ipa_node_params *info,
 					       nonconstant_names);
       return p2.or_with (summary->conds, p1);
     }
+  else if (TREE_CODE (expr) == CALL_EXPR)
+    {
+      return false;
+    }
   else
     {
       debug_tree (expr);
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/popcount.c b/gcc/testsuite/gcc.dg/tree-ssa/popcount.c
new file mode 100644
index 0000000..86a66cb
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/popcount.c
@@ -0,0 +1,41 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -fdump-tree-optimized" } */
+
+extern int foo (int);
+
+int PopCount (long b) {
+    int c = 0;
+    b++;
+
+    while (b) {
+	b &= b - 1;
+	c++;
+    }
+    return c;
+}
+int PopCount2 (long b) {
+    int c = 0;
+
+    while (b) {
+	b &= b - 1;
+	c++;
+    }
+    foo (c);
+    return foo (c);
+}
+
+void PopCount3 (long b1) {
+
+    for (long i = 0; i < b1; ++i)
+      {
+	long b = i;
+	int c = 0;
+	while (b) {
+	    b &= b - 1;
+	    c++;
+	}
+	foo (c);
+      }
+}
+
+/* { dg-final { scan-tree-dump-times "__builtin_popcount" 3 "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/popcount2.c b/gcc/testsuite/gcc.dg/tree-ssa/popcount2.c
new file mode 100644
index 0000000..52afc2d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/popcount2.c
@@ -0,0 +1,29 @@
+/* { dg-do execute } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+__attribute__ ((noinline, noclone))
+foo (int i, long b)
+{
+    int c = i;
+
+    while (b) {
+	b &= b - 1;
+	c++;
+    }
+    return c;
+}
+
+int main()
+{
+
+  if (foo (1, 7) != 4)
+   __builtin_abort ();
+  if (foo (0, 0) != 0)
+   __builtin_abort ();
+  if (foo (8, 0xff) != 16)
+   __builtin_abort ();
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "__builtin_popcount" 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..0c69d97
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/popcount3.c
@@ -0,0 +1,28 @@
+/* { dg-do execute } */
+/* { dg-options "-O2 -fno-tree-ch -fdump-tree-optimized" } */
+
+int
+__attribute__ ((noinline, noclone))
+foo (long b)
+{
+    int c = i;
+
+    while (b) {
+	b &= b - 1;
+	c++;
+    }
+    return c;
+}
+
+int main()
+{
+  if (foo (7) != 3)
+   __builtin_abort ();
+  if (foo (0) != 0)
+   __builtin_abort ();
+  if (foo (0xff) != 8)
+   __builtin_abort ();
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "__builtin_popcount" 1 "optimized" } } */
diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c
index fefc9de..967b154 100644
--- a/gcc/tree-scalar-evolution.c
+++ b/gcc/tree-scalar-evolution.c
@@ -1984,6 +1984,7 @@ interpret_expr (struct loop *loop, gimple *at_stmt, tree expr)
     return expr;
 
   if (TREE_CODE (expr) == POLYNOMIAL_CHREC
+      || TREE_CODE (expr) == CALL_EXPR
       || get_gimple_rhs_class (TREE_CODE (expr)) == GIMPLE_TERNARY_RHS)
     return chrec_dont_know;
 
@@ -3472,6 +3473,7 @@ bool
 expression_expensive_p (tree expr)
 {
   enum tree_code code;
+  tree fndecl;
 
   if (is_gimple_val (expr))
     return false;
@@ -3492,6 +3494,11 @@ expression_expensive_p (tree expr)
       if (!integer_pow2p (TREE_OPERAND (expr, 1)))
 	return true;
     }
+  if (code == CALL_EXPR
+      && (fndecl = get_callee_fndecl (expr))
+      && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
+      && (BUILT_IN_POPCOUNT == DECL_FUNCTION_CODE (fndecl)))
+    return false;
 
   switch (TREE_CODE_CLASS (code))
     {
diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c
index b313571..519649a 100644
--- a/gcc/tree-ssa-loop-ivopts.c
+++ b/gcc/tree-ssa-loop-ivopts.c
@@ -985,6 +985,16 @@ contains_abnormal_ssa_name_p (tree expr)
   code = TREE_CODE (expr);
   codeclass = TREE_CODE_CLASS (code);
 
+  if (code == CALL_EXPR)
+    {
+      tree arg;
+      call_expr_arg_iterator iter;
+      FOR_EACH_CALL_EXPR_ARG (arg, iter, expr)
+	if (contains_abnormal_ssa_name_p (arg))
+	  return true;
+      return false;
+    }
+
   if (code == SSA_NAME)
     return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr) != 0;
 
diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index 7a54c5f..fde9245 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -2430,6 +2430,152 @@ number_of_iterations_exit_assumptions (struct loop *loop, edge exit,
   return (!integer_zerop (niter->assumptions));
 }
 
+/* Utility function to check if OP is defined by a stmt
+   that is a val - 1.  If that is the case, set it to STMT.  */
+
+static bool
+ssa_defined_by_minus_one_stmt_p (tree op, tree val, gimple **stmt)
+{
+  return (TREE_CODE (op) == SSA_NAME
+	  && (*stmt = SSA_NAME_DEF_STMT (op))
+	  && is_gimple_assign (*stmt)
+	  && (gimple_assign_rhs_code (*stmt) == PLUS_EXPR)
+	  && val == gimple_assign_rhs1 (*stmt)
+	  && integer_minus_onep (gimple_assign_rhs2 (*stmt)));
+}
+
+/* See if LOOP is a popcout implementation of the form
+
+    int c = 0;
+    while (b) {
+	b = b & (b - 1);
+	c++;
+    }
+
+    If popcount pattern, update NITER accordingly.
+    i.e., set NITER to  __builtin_popcount (b)
+    return true if we did, false otherwise.
+
+ */
+
+static bool
+number_of_iterations_popcount (loop_p loop, struct tree_niter_desc *niter)
+{
+  tree rhs1, rhs2;
+  tree dest;
+  gimple *and_minus_one;
+  gimple *phi;
+  int count = 0;
+  gimple *count_stmt = NULL;
+  bool adjust = true;
+  edge exit;
+  tree iter;
+  HOST_WIDE_INT max;
+
+  if (!(exit = single_exit (loop)))
+    return false;
+
+  /* Check loop terminating branch is like
+     if (b != 0).  */
+  gimple *stmt = last_stmt (loop->header);
+  if (!stmt
+      || gimple_code (stmt) != GIMPLE_COND
+      || gimple_cond_code (stmt) != NE_EXPR
+      || !zerop (gimple_cond_rhs (stmt))
+      || TREE_CODE (gimple_cond_lhs (stmt)) != SSA_NAME)
+    return false;
+
+  /* Check the loop closed SSA definition for just the variable c defined in
+     loop.  */
+  basic_block bb = exit->dest;
+  for (gphi_iterator gpi = gsi_start_phis (bb);
+       !gsi_end_p (gpi); gsi_next (&gpi))
+    {
+      phi = gpi.phi ();
+      count++;
+    }
+
+  if (count != 1)
+    return false;
+
+  rhs1 = gimple_phi_arg_def (phi, exit->dest_idx);
+  if (TREE_CODE (rhs1) != SSA_NAME)
+    return false;
+  count_stmt = SSA_NAME_DEF_STMT (rhs1);
+  gimple *and_stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt));
+
+  /* Depending on copy-header is performed, feeding PHI stmts might be in
+     the loop header or loop exit, handle this.  */
+  if (gimple_code (count_stmt) == GIMPLE_PHI)
+    {
+      tree t;
+      if (gimple_code (and_stmt) != GIMPLE_PHI
+	  || gimple_bb (and_stmt) != exit->src
+	  || gimple_bb (count_stmt) != exit->src)
+	return false;
+      t = gimple_phi_arg_def (count_stmt, loop_latch_edge (loop)->dest_idx);
+      if (TREE_CODE (t) != SSA_NAME)
+	return false;
+      count_stmt = SSA_NAME_DEF_STMT (t);
+      t = gimple_phi_arg_def (and_stmt, loop_latch_edge (loop)->dest_idx);
+      if (TREE_CODE (t) != SSA_NAME)
+	return false;
+      and_stmt = SSA_NAME_DEF_STMT (t);
+      adjust = false;
+    }
+
+  /* Make sure we have a count by one.  */
+  if (!is_gimple_assign (count_stmt)
+      || (gimple_assign_rhs_code (count_stmt) != PLUS_EXPR)
+      || !integer_onep (gimple_assign_rhs2 (count_stmt)))
+    return false;
+
+  /* Check "b = b & (b - 1)" is calculated.  */
+  if (!is_gimple_assign (and_stmt)
+      || gimple_assign_rhs_code (and_stmt) != BIT_AND_EXPR)
+    return false;
+
+  rhs1 = gimple_assign_rhs1 (and_stmt);
+  rhs2 = gimple_assign_rhs2 (and_stmt);
+
+  if (ssa_defined_by_minus_one_stmt_p (rhs1, rhs2, &and_minus_one))
+    std::swap (rhs1, rhs2);
+  else if (ssa_defined_by_minus_one_stmt_p (rhs2, rhs1, &and_minus_one))
+    ;
+  else
+    return false;
+
+  /* Check the recurrence.  */
+  phi = SSA_NAME_DEF_STMT (rhs1);
+  if (gimple_code (phi) != GIMPLE_PHI)
+    return false;
+
+  dest = gimple_assign_lhs (count_stmt);
+  tree utype = unsigned_type_for (TREE_TYPE (dest));
+  tree fn = builtin_decl_implicit (BUILT_IN_POPCOUNT);
+  tree src = gimple_phi_arg_def (phi, loop_preheader_edge (loop)->dest_idx);
+  if (adjust)
+    iter = fold_build2 (MINUS_EXPR, utype,
+			build_call_expr (fn, 1, src),
+			build_int_cst (utype, 1));
+  else
+    iter = fold_convert (utype, build_call_expr (fn, 1, src));
+  max = int_cst_value (TYPE_MAX_VALUE (TREE_TYPE (dest)));
+
+  niter->assumptions = boolean_false_node;
+  niter->control.base = NULL_TREE;
+  niter->control.step = NULL_TREE;
+  niter->control.no_overflow = false;
+  niter->niter = iter;
+  niter->assumptions = boolean_true_node;
+  niter->may_be_zero = boolean_false_node;
+  niter->max = max;
+  niter->bound = NULL_TREE;
+  niter->cmp = ERROR_MARK;
+  return true;
+}
+
+
 /* Like number_of_iterations_exit_assumptions, but return TRUE only if
    the niter information holds unconditionally.  */
 
@@ -2441,7 +2587,11 @@ number_of_iterations_exit (struct loop *loop, edge exit,
   gcond *stmt;
   if (!number_of_iterations_exit_assumptions (loop, exit, niter,
 					      &stmt, every_iteration))
-    return false;
+    {
+      if (number_of_iterations_popcount (loop, niter))
+	return true;
+      return false;
+    }
 
   if (integer_nonzerop (niter->assumptions))
     return true;
-- 
2.7.4