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

[Richard Biener <richard dot guenther at gmail dot com>]

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.

+      || !zerop (gimple_cond_rhs (stmt))

use integer_zerop

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

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;


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