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

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

Hi Richard,

Thanks for the review.

On 5 June 2018 at 21:25, Richard Biener <richard.guenther@gmail.com> wrote:
> On Tue, Jun 5, 2018 at 10:59 AM Kugan Vivekanandarajah
> <kugan.vivekanandarajah@linaro.org> wrote:
>>
>> Hi Richard,
>>
>> Thanks for the review.
>>
>> On 1 June 2018 at 23:12, Richard Biener <richard.guenther@gmail.com> wrote:
>> > On Fri, Jun 1, 2018 at 12:06 PM Bin.Cheng <amker.cheng@gmail.com> wrote:
>> >>
>> >> On Fri, Jun 1, 2018 at 9:56 AM, Kugan Vivekanandarajah
>> >> <kugan.vivekanandarajah@linaro.org> wrote:
>> >> > 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?
>> >> Is it a simple typo?  Because assumptions is set to boolean_true_node
>> >> just 5 lines below?
>> >> The niters part looks good for me with this change.  You may need
>> >> richi's approval for other parts?
>> >
>> > 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);
>> >
>> > I'd return true here instead - we don't want to track popcount() in
>> > predicates.  Also unnecessary braces.
>> >
>> > @@ -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;
>> >
>> > please use
>> >
>> >     if (code == CALL_EXPR)
>> >      {
>> >          if (!is_inexpensive_builtin (get_callee_fndecl (expr)))
>> >            return true;
>> >          FOR_EACH_CALL_EXPR_ARG (arg, iter, expr)
>> >              if (expression_expensive_p (arg))
>> >                 return true;
>> >          return false;
>> >      }
>> >
>> > instead.
>> Done.
>>
>> >
>> > +  /* 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;
>> >
>> > so the powers of match-and-simplify let you add sth like the following to
>> > match.pd:
>> >
>> > #if GIMPLE
>> > (match (b_bit_and_b_minus_one @0)
>> >  (bit_and:c @0 (plus @0 integer_minus_onep)))
>> > #endif
>> >
>> > and then use it like
>> >
>> >    extern bool gimple_b_bit_and_b_minus_one (tree, tree *, tree (*)(tree));
>> >    if (!gimple_b_bit_and_b_minus_one (gimple_assign_lhs (and_stmt),
>> > &rhs1, NULL))
>> >       return false;
>> >
>> > note you need to explicitely declare the matcher as there's no header
>> > file generated
>> > for them.  It would be also the first user for this "feature" and at
>> > some point I
>> > considered using in-line source markup (and sth like GTY_FILES for
>> > what files to scan)
>> > to gather patterns.
>> >
>> > +  /* 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++;
>> > +    }
>> >
>> > I don't understand why you are checking for this - isn't the number of
>> > iterations
>> I am trying to be overly conservative. I have removed it now and adjusted.
>>
>> > independent on the rest of the loop-closed PHIs?  That is, even for just
>> >
>> >  while (b) { b = b & (b-1); }
>> >
>> > the number of iterations is popcount (b).  So it's enough to check
>> > the exit condition?  In fact you are coming from number_of_iterations_exit
>> > and thus are asked for a specific exit and thus
>> >
>> > +  if (!(exit = single_exit (loop)))
>> > +    return false;
>> Ok, changed it.
>>
>>
>> > is premature.  That is, for
>> >
>> >   while (b) { b = b & (b - 1); if (--c == 0) break; }
>> >
>> > still should have popcount (b) iterations for the exit involving the
>> > while (b) test.
>> >
>> > So please simplify (and thus genericize) the code accordingly.  Do so
>> > without the match.pd trick for now, I think we can simplify the current
>> > beast down enough to not need the factored out function.
>> I am not using match.pd changes as you have asked. Please let me know
>> if you want that to be included as well.
>>
>> >
>> > You then also can handle replacing
>> >
>> > int c = 0;
>> > while (b) { b = b & (b-1); c+=3; }
>> >
>> > with 3 * popcount (b);
>> Made to handle this too. But, there are still cases we don't handle. I
>> am not sure if it is worth the complexity handling all the possible
>> cases.
>>
>> Is the attached patch looks better now?
>
> +  /* Check loop terminating branch is like
> +     if (b != 0).  */
> +  gimple *stmt = last_stmt (loop->header);
> +  if (!stmt
>
> this should now look at exit->src instead of loop->header.
Done.

>
> +      || !zerop (gimple_cond_rhs (stmt))
>
> use integer_zerop
Done.

>
> +  gimple *count_stmt = SSA_NAME_DEF_STMT (rhs1);
>
> you still didn't remove the whole count-stmt stuff.  It's unrelated
> and is not required at all.  Only the GIMPLE_COND lhs def-use
> cycle is interesting for niter purposes.
Changed it.

>
> Please adjust accordingly.
>
> @@ -2441,7 +2578,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, exit, niter))
> +       return true;
> +      return false;
> +    }
>
> this should be done in number_of_iterations_exit_assumptions.  I realize
> you want to do it only if that fails but in that process you have to be
> sure to properly handle every_iteration & friends which is much easier
> to do in number_of_iterations_exit_assumptions.  So please put it
> where that fails for this kind of IVs:
>
>   tree iv0_niters = NULL_TREE;
>   if (!simple_iv_with_niters (loop, loop_containing_stmt (stmt),
>                               op0, &iv0, safe ? &iv0_niters : NULL, false))
> ^^^ here
>     return false;

Done.

Is this OK now. Regression tested and bootstrapped on x86-linux-gnu
with no new regressions.

Thanks,
Kugan
>
>
> Thanks,
> Richard.
>
>> Thanks,
>> Kugan
>>
>>
>> >
>> > Richard.
>> >
>> >> Thanks,
>> >> bin
>> >> >
>> >> >>> +  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 93723ba9de05b8f065f6d0f98bb5536a76215211 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: I3f75f807c1b3ed2bbfbd7ab8455cb28a28c68b1a
---
 gcc/ipa-fnsummary.c                       |   2 +
 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               |  15 ++++
 gcc/tree-ssa-loop-ivopts.c                |  10 +++
 gcc/tree-ssa-loop-niter.c                 | 125 +++++++++++++++++++++++++++++-
 7 files changed, 249 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..feb1c9e 100644
--- a/gcc/ipa-fnsummary.c
+++ b/gcc/ipa-fnsummary.c
@@ -1485,6 +1485,8 @@ 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 true;
   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..362d835
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/popcount2.c
@@ -0,0 +1,29 @@
+/* { dg-do run } */
+/* { 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..9096c6b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/popcount3.c
@@ -0,0 +1,28 @@
+/* { dg-do run } */
+/* { dg-options "-O2 -fno-tree-ch -fdump-tree-optimized" } */
+
+int
+__attribute__ ((noinline, noclone))
+foo (long b)
+{
+    int c = 0;
+
+    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..4b0ec02 100644
--- a/gcc/tree-scalar-evolution.c
+++ b/gcc/tree-scalar-evolution.c
@@ -281,6 +281,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-ssa-propagate.h"
 #include "gimple-fold.h"
 #include "tree-into-ssa.h"
+#include "builtins.h"
 
 static tree analyze_scalar_evolution_1 (struct loop *, tree);
 static tree analyze_scalar_evolution_for_address_of (struct loop *loop,
@@ -1984,6 +1985,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;
 
@@ -3493,6 +3495,19 @@ expression_expensive_p (tree expr)
 	return true;
     }
 
+  if (code == CALL_EXPR)
+    {
+      tree arg;
+      call_expr_arg_iterator iter;
+
+      if (!is_inexpensive_builtin (get_callee_fndecl (expr)))
+	return true;
+      FOR_EACH_CALL_EXPR_ARG (arg, iter, expr)
+	if (expression_expensive_p (arg))
+	  return true;
+      return false;
+    }
+
   switch (TREE_CODE_CLASS (code))
     {
     case tcc_binary:
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..5064681 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -63,6 +63,9 @@ struct bounds
   mpz_t below, up;
 };
 
+static bool number_of_iterations_popcount (loop_p loop, edge exit,
+					   struct tree_niter_desc *niter);
+
 
 /* Splits expression EXPR to a variable part VAR and constant OFFSET.  */
 
@@ -2357,7 +2360,7 @@ number_of_iterations_exit_assumptions (struct loop *loop, edge exit,
   tree iv0_niters = NULL_TREE;
   if (!simple_iv_with_niters (loop, loop_containing_stmt (stmt),
 			      op0, &iv0, safe ? &iv0_niters : NULL, false))
-    return false;
+    return number_of_iterations_popcount (loop, exit, niter);
   tree iv1_niters = NULL_TREE;
   if (!simple_iv_with_niters (loop, loop_containing_stmt (stmt),
 			      op1, &iv1, safe ? &iv1_niters : NULL, false))
@@ -2430,6 +2433,126 @@ 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.  */
+
+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, edge exit,
+			       struct tree_niter_desc *niter)
+{
+  tree rhs1, rhs2;
+  bool adjust = true;
+  tree iter;
+  HOST_WIDE_INT max;
+  adjust = true;
+
+  /* Check loop terminating branch is like
+     if (b != 0).  */
+  gimple *stmt = last_stmt (exit->src);
+  if (!stmt
+      || gimple_code (stmt) != GIMPLE_COND
+      || gimple_cond_code (stmt) != NE_EXPR
+      || !integer_zerop (gimple_cond_rhs (stmt))
+      || TREE_CODE (gimple_cond_lhs (stmt)) != SSA_NAME)
+    return false;
+
+  gphi_iterator gpi = gsi_start_phis (exit->dest);
+  if (gsi_end_p (gpi))
+    return false;
+  rhs1 = gimple_phi_arg_def (gpi.phi (), exit->dest_idx);
+  if (TREE_CODE (rhs1) != SSA_NAME)
+    return false;
+
+  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 (and_stmt) == GIMPLE_PHI
+      && gimple_bb (and_stmt) == exit->src
+      && gimple_phi_num_args (and_stmt) == 2
+      && (TREE_CODE (gimple_phi_arg_def (and_stmt,
+					 loop_latch_edge (loop)->dest_idx))
+	  == SSA_NAME))
+    {
+      tree t = gimple_phi_arg_def (and_stmt, loop_latch_edge (loop)->dest_idx);
+      and_stmt = SSA_NAME_DEF_STMT (t);
+      adjust = 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))
+    std::swap (rhs1, rhs2);
+  else if (ssa_defined_by_minus_one_stmt_p (rhs2, rhs1))
+    ;
+  else
+    return false;
+
+  /* Check the recurrence.  */
+  gimple *phi = SSA_NAME_DEF_STMT (rhs1);
+  if (gimple_code (phi) != GIMPLE_PHI)
+    return false;
+
+  tree fn = builtin_decl_implicit (BUILT_IN_POPCOUNT);
+  tree src = gimple_phi_arg_def (phi, loop_preheader_edge (loop)->dest_idx);
+  tree call = build_call_expr (fn, 1, src);
+  tree utype = unsigned_type_for (TREE_TYPE (call));
+  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 (utype));
+
+  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.  */
 
-- 
2.7.4