Re: [patch] [RFC] conditional loop-count expression

[Dorit Nuzman <DORIT at il dot ibm dot com>]

Zdenek Dvorak <rakdver@kam.mff.cuni.cz> wrote on 03/06/2007 17:12:50:

> Hello,
>

Thanks,

...
> > One possible solution is to provide an API that returns both the
> > number-of-iterations expression and the maybe-zero expression upon
which
> > the number-of-iterations depends. The calling function can decide what
to
> > do with this information.
>
> this looks ok (although creating a new function for this might not
> be necessary, you could just use number_of_iterations_exit directly).
>

ok (unfortunately I missed this comment before committing this patch to
autovect-branch - http://gcc.gnu.org/ml/gcc-patches/2007-06/msg00247.html -
but this is easily fixable)

> > So,
> > 1) why does force_gimple break the COND_EXPR to if-then-else? (isn't is
> > legal GIMPLE?)
>
> It is legal, however gimplifier does not generate it.
>

I see

> > 2) if COND_EXPR indeed has to be broken into an if-then-else, is there
a
> > proper API to use that would open new basic-blocks when needed (i.e.,
upon
> > insertion of conditional code)?
>
> No.
>

so we need to transform this:

      bb0:
      if (n_5(D) <= 0)
        {
          iftmp.27_9 = 0;
        }
      else
        {
          iftmp.27_10 = (unsigned int) n_5(D);
        }
      niters.26_11 = iftmp.27;

...into this:

      bb0:
      if (n_5(D) <= 0)
        goto bb1;
      else
        goto bb2;

      bb1:
          iftmp.27_9 = 0;
          goto bb3;

      bb2:
          iftmp.27_10 = (unsigned int) n_5(D);
          goto bb3;

      bb3:
      iftmp.27_100 = phi (iftmp.27_9, iftmp.27_10)
      niters.26_11 = iftmp.27_100;

...(right?). About replacing iftmp.27 with iftmp.27_100 - I'm not sure how
to handle that in the general case, but if we are allowed to expect only
the restricted pattern above, i.e. that the *only* un-named variable use
("niters.26_11 = iftmp.27") is immediately after the if-then-else and that
the two ssa-names defining it appear in the then and else, then in this
case it's easy to find the variable that the if-then-else defines. I think
that for the kind of cond_expr we are generating here, i.e: "niters =
(maybe_zero ? 0 : iters)", this should be a safe assumption...?

> > 3) given that the above problem is fixed - is this patch in he right
> > direction?
>
> Yes, I think this is a possible way how to solve the problem.  The other
> way would be to version the loop on the may_be_zero condition (of
> course, keeping just the executed part of the first iteration in one
> of the branches) -- this transformation could be useful also for other
> optimizations.
>

Right. http://gcc.gnu.org/ml/gcc-patches/2006-12/msg00695.html summarizes
some potential draw-backs of this approach (most of which I think you had
originally brought up...) that need to be carefully handled. I thought that
COND_EXPR would be the easiest and most compact thing to do (but the
gimplification thing makes it a bit less trivial than I thought...). Also,
my main motivation came from working on outer-loop vectorization where the
inner-loop bound could not be proved to be positive (
http://gcc.gnu.org/ml/gcc-patches/2007-06/msg00248.html), and I don't want
to complicate the outer-loop by inserting guards and loop-versions into it.

thanks,
dorit

> Zdenek
>
> > thanks,
> > dorit
> >
> > (See attached file: condlb.txt)
> > Index: tree-scalar-evolution.c
> > ===================================================================
> > *** tree-scalar-evolution.c   (revision 125292)
> > --- tree-scalar-evolution.c   (working copy)
> > *************** resolve_mixers (struct loop *loop, tree
> > *** 2437,2453 ****
> >      the loop body has been executed 6 times.  */
> >
> >   tree
> > ! number_of_latch_executions (struct loop *loop)
> >   {
> > !   tree res, type;
> >     edge exit;
> >     struct tree_niter_desc niter_desc;
> >
> >     /* Determine whether the number_of_iterations_in_loop has already
> >        been computed.  */
> >     res = loop->nb_iterations;
> >     if (res)
> >       return res;
> >     res = chrec_dont_know;
> >
> >     if (dump_file && (dump_flags & TDF_DETAILS))
> > --- 2437,2456 ----
> >      the loop body has been executed 6 times.  */
> >
> >   tree
> > ! number_of_latch_executions_1 (struct loop *loop, tree *may_be_zero)
> >   {
> > !   tree res;
> >     edge exit;
> >     struct tree_niter_desc niter_desc;
> >
> > +   *may_be_zero = NULL_TREE;
> > +
> >     /* Determine whether the number_of_iterations_in_loop has already
> >        been computed.  */
> >     res = loop->nb_iterations;
> >     if (res)
> >       return res;
> > +
> >     res = chrec_dont_know;
> >
> >     if (dump_file && (dump_flags & TDF_DETAILS))
> > *************** number_of_latch_executions (struct loop
> > *** 2460,2477 ****
> >     if (!number_of_iterations_exit (loop, exit, &niter_desc, false))
> >       goto end;
> >
> > !   type = TREE_TYPE (niter_desc.niter);
> > !   if (integer_nonzerop (niter_desc.may_be_zero))
> > !     res = build_int_cst (type, 0);
> > !   else if (integer_zerop (niter_desc.may_be_zero))
> > !     res = niter_desc.niter;
> > !   else
> > !     res = chrec_dont_know;
> >
> >   end:
> >     return set_nb_iterations_in_loop (loop, res);
> >   }
> >
> >   /* Returns the number of executions of the exit condition of LOOP,
> >      i.e., the number by one higher than number_of_latch_executions.
> >      Note that unline number_of_latch_executions, this number does
> > --- 2463,2498 ----
> >     if (!number_of_iterations_exit (loop, exit, &niter_desc, false))
> >       goto end;
> >
> > !   *may_be_zero = niter_desc.may_be_zero;
> > !   res = niter_desc.niter;
> >
> >   end:
> >     return set_nb_iterations_in_loop (loop, res);
> >   }
> >
> > +
> > + tree
> > + number_of_latch_executions (struct loop *loop)
> > + {
> > +   tree res, type;
> > +   tree may_be_zero;
> > +
> > +   res = number_of_latch_executions_1 (loop, &may_be_zero);
> > +
> > +   if (may_be_zero)
> > +     {
> > +       type = TREE_TYPE (res);
> > +       if (integer_nonzerop (may_be_zero))
> > +    res = build_int_cst (type, 0);
> > +       else if (integer_zerop (may_be_zero))
> > +    ;
> > +       else
> > +    res = chrec_dont_know;
> > +     }
> > +
> > +   return res;
> > + }
> > +
> >   /* Returns the number of executions of the exit condition of LOOP,
> >      i.e., the number by one higher than number_of_latch_executions.
> >      Note that unline number_of_latch_executions, this number does
> > *************** end:
> > *** 2483,2491 ****
> >      the possible overflow.  */
> >
> >   tree
> > ! number_of_exit_cond_executions (struct loop *loop)
> >   {
> > !   tree ret = number_of_latch_executions (loop);
> >     tree type = chrec_type (ret);
> >
> >     if (chrec_contains_undetermined (ret))
> > --- 2504,2512 ----
> >      the possible overflow.  */
> >
> >   tree
> > ! number_of_exit_cond_executions (struct loop *loop, tree *may_be_zero)
> >   {
> > !   tree ret = number_of_latch_executions_1 (loop, may_be_zero);
> >     tree type = chrec_type (ret);
> >
> >     if (chrec_contains_undetermined (ret))
> > Index: tree-scalar-evolution.h
> > ===================================================================
> > *** tree-scalar-evolution.h   (revision 125292)
> > --- tree-scalar-evolution.h   (working copy)
> > *************** Software Foundation, 51 Franklin Street,
> > *** 22,29 ****
> >   #ifndef GCC_TREE_SCALAR_EVOLUTION_H
> >   #define GCC_TREE_SCALAR_EVOLUTION_H
> >
> >   extern tree number_of_latch_executions (struct loop *);
> > ! extern tree number_of_exit_cond_executions (struct loop *);
> >   extern tree get_loop_exit_condition (struct loop *);
> >
> >   extern void scev_initialize (void);
> > --- 22,30 ----
> >   #ifndef GCC_TREE_SCALAR_EVOLUTION_H
> >   #define GCC_TREE_SCALAR_EVOLUTION_H
> >
> > + extern tree number_of_latch_executions_1 (struct loop *, tree *);
> >   extern tree number_of_latch_executions (struct loop *);
> > ! extern tree number_of_exit_cond_executions (struct loop *, tree *);
> >   extern tree get_loop_exit_condition (struct loop *);
> >
> >   extern void scev_initialize (void);
> > Index: tree-vect-analyze.c
> > ===================================================================
> > *** tree-vect-analyze.c   (revision 125292)
> > --- tree-vect-analyze.c   (working copy)
> > *************** static tree
> > *** 2515,2531 ****
> >   vect_get_loop_niters (struct loop *loop, tree *number_of_iterations)
> >   {
> >     tree niters;
> >
> >     if (vect_print_dump_info (REPORT_DETAILS))
> >       fprintf (vect_dump, "=== get_loop_niters ===");
> >
> > !   niters = number_of_exit_cond_executions (loop);
> >
> > !   if (niters != NULL_TREE
> > !       && niters != chrec_dont_know)
> >       {
> > !       *number_of_iterations = niters;
> >
> >         if (vect_print_dump_info (REPORT_DETAILS))
> >      {
> >        fprintf (vect_dump, "==> get_loop_niters:" );
> > --- 2515,2550 ----
> >   vect_get_loop_niters (struct loop *loop, tree *number_of_iterations)
> >   {
> >     tree niters;
> > +   tree may_be_zero;
> >
> >     if (vect_print_dump_info (REPORT_DETAILS))
> >       fprintf (vect_dump, "=== get_loop_niters ===");
> >
> > !   niters = number_of_exit_cond_executions (loop, &may_be_zero);
> >
> > !   if (niters != NULL_TREE && niters != chrec_dont_know)
> >       {
> > !       tree type = TREE_TYPE (niters);
> > !       tree zero = build_int_cst (type, 0);
> >
> > +       *number_of_iterations = niters;
> > +       if (may_be_zero)
> > +    {
> > +      if (integer_nonzerop (may_be_zero))
> > +        *number_of_iterations = zero;
> > +      else if (integer_zerop (may_be_zero))
> > +        ;
> > +      else
> > +        {
> > +          /* CHECKME: other things to check? */
> > +          if (COMPARISON_CLASS_P (may_be_zero))
> > +       *number_of_iterations =
> > +          build3 (COND_EXPR, type, may_be_zero, zero, niters);
> > +          else
> > +       *number_of_iterations = chrec_dont_know;
> > +        }
> > +    }
> > +
> >         if (vect_print_dump_info (REPORT_DETAILS))
> >      {
> >        fprintf (vect_dump, "==> get_loop_niters:" );
> > Index: tree-vect-transform.c
> > ===================================================================
> > *** tree-vect-transform.c   (revision 125292)
> > --- tree-vect-transform.c   (working copy)
> > *************** vect_generate_tmps_on_preheader (loop_ve
> > *** 4540,4547 ****
> >     int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
> >     tree log_vf;
> >
> > -   pe = loop_preheader_edge (loop);
> > -
> >     /* Generate temporary variable that contains
> >        number of iterations loop executes.  */
> >
> > --- 4540,4545 ----
>