[QUESTION] About RTL optimization at forward propagation

[QUESTION] About RTL optimization at forward propagation

[xiezhiheng]

Hi,
  I find there exists some restricts in function fwprop preventing it to forward propagate addresses into loops.
/* Go through all the uses.  df_uses_create will create new ones at the
   end, and we'll go through them as well.

   Do not forward propagate addresses into loops until after unrolling.
   CSE did so because it was able to fix its own mess, but we are not.  */
for (i = 0; i < DF_USES_TABLE_SIZE (); i++)
  {
    if (!propagations_left)
      break;

    df_ref use = DF_USES_GET (i);
    if (use)
      {
        if (DF_REF_TYPE (use) == DF_REF_REG_USE
            || DF_REF_BB (use)->loop_father == NULL                    <<<<<<<<<<
            /* The outer most loop is not really a loop.  */
            || loop_outer (DF_REF_BB (use)->loop_father) == NULL)
          forward_propagate_into (use, fwprop_addr_p);

        else if (fwprop_addr_p)
          forward_propagate_into (use, false);
      }
  }

  And I have two questions.
  1) What are the reasons or background for not forward propagating addresses into loops ?
  2) Can we still forward propagate addresses if the def and use are in the same loop ?
  I mean something like:
diff -Nurp a/gcc/fwprop.c b/gcc/fwprop.c
--- a/gcc/fwprop.c      2020-03-27 03:17:50.704000000 -0400
+++ b/gcc/fwprop.c      2020-03-27 04:58:35.148000000 -0400
@@ -1573,10 +1573,12 @@ fwprop (bool fwprop_addr_p)
       df_ref use = DF_USES_GET (i);
       if (use)
        {
+         df_ref def = get_def_for_use (use);
          if (DF_REF_TYPE (use) == DF_REF_REG_USE
              || DF_REF_BB (use)->loop_father == NULL
              /* The outer most loop is not really a loop.  */
-             || loop_outer (DF_REF_BB (use)->loop_father) == NULL)
+             || loop_outer (DF_REF_BB (use)->loop_father) == NULL
+             || (def && DF_REF_BB (def)->loop_father == DF_REF_BB (use)->loop_father))
            forward_propagate_into (use, fwprop_addr_p);

          else if (fwprop_addr_p)

I would be grateful if anyone could help.

Best regards

Re: [QUESTION] About RTL optimization at forward propagation

[Richard Biener]

On Sat, Mar 28, 2020 at 4:19 AM xiezhiheng <xiezhiheng@huawei.com> wrote:
>
> Hi,
>   I find there exists some restricts in function fwprop preventing it to forward propagate addresses into loops.
> /* Go through all the uses.  df_uses_create will create new ones at the
>    end, and we'll go through them as well.
>
>    Do not forward propagate addresses into loops until after unrolling.
>    CSE did so because it was able to fix its own mess, but we are not.  */
> for (i = 0; i < DF_USES_TABLE_SIZE (); i++)
>   {
>     if (!propagations_left)
>       break;
>
>     df_ref use = DF_USES_GET (i);
>     if (use)
>       {
>         if (DF_REF_TYPE (use) == DF_REF_REG_USE
>             || DF_REF_BB (use)->loop_father == NULL                    <<<<<<<<<<
>             /* The outer most loop is not really a loop.  */
>             || loop_outer (DF_REF_BB (use)->loop_father) == NULL)
>           forward_propagate_into (use, fwprop_addr_p);
>
>         else if (fwprop_addr_p)
>           forward_propagate_into (use, false);
>       }
>   }
>
>   And I have two questions.
>   1) What are the reasons or background for not forward propagating addresses into loops ?
>   2) Can we still forward propagate addresses if the def and use are in the same loop ?
>   I mean something like:

The condiition indeed looks odd, the canonical way would be to check

  !flow_loop_nested_p (DF_REF_BB (def)->loop_father, DF_REF_BB
(use)->loop_father)

which would allow propagating addresses defined in loops outside as well.
And loop_father should never be NULL I think.

> diff -Nurp a/gcc/fwprop.c b/gcc/fwprop.c
> --- a/gcc/fwprop.c      2020-03-27 03:17:50.704000000 -0400
> +++ b/gcc/fwprop.c      2020-03-27 04:58:35.148000000 -0400
> @@ -1573,10 +1573,12 @@ fwprop (bool fwprop_addr_p)
>        df_ref use = DF_USES_GET (i);
>        if (use)
>         {
> +         df_ref def = get_def_for_use (use);
>           if (DF_REF_TYPE (use) == DF_REF_REG_USE
>               || DF_REF_BB (use)->loop_father == NULL
>               /* The outer most loop is not really a loop.  */
> -             || loop_outer (DF_REF_BB (use)->loop_father) == NULL)
> +             || loop_outer (DF_REF_BB (use)->loop_father) == NULL
> +             || (def && DF_REF_BB (def)->loop_father == DF_REF_BB (use)->loop_father))
>             forward_propagate_into (use, fwprop_addr_p);
>
>           else if (fwprop_addr_p)
>
> I would be grateful if anyone could help.
>
> Best regards

RE: [QUESTION] About RTL optimization at forward propagation

[xiezhiheng]

> -----Original Message-----
> From: Richard Biener [mailto:richard.guenther@gmail.com]
> Sent: Monday, March 30, 2020 4:39 PM
> To: xiezhiheng <xiezhiheng@huawei.com>
> Cc: gcc@gcc.gnu.org
> Subject: Re: [QUESTION] About RTL optimization at forward propagation
> 
> On Sat, Mar 28, 2020 at 4:19 AM xiezhiheng <xiezhiheng@huawei.com>
> wrote:
> >
> > Hi,
> >   I find there exists some restricts in function fwprop preventing it to
> > forward propagate addresses into loops.
> > /* Go through all the uses.  df_uses_create will create new ones at the
> >    end, and we'll go through them as well.
> >
> >    Do not forward propagate addresses into loops until after unrolling.
> >    CSE did so because it was able to fix its own mess, but we are not.  */
> > for (i = 0; i < DF_USES_TABLE_SIZE (); i++)
> >   {
> >     if (!propagations_left)
> >       break;
> >
> >     df_ref use = DF_USES_GET (i);
> >     if (use)
> >       {
> >         if (DF_REF_TYPE (use) == DF_REF_REG_USE
> >             || DF_REF_BB (use)->loop_father == NULL
> > <<<<<<<<<<
> >             /* The outer most loop is not really a loop.  */
> >             || loop_outer (DF_REF_BB (use)->loop_father) == NULL)
> >           forward_propagate_into (use, fwprop_addr_p);
> >
> >         else if (fwprop_addr_p)
> >           forward_propagate_into (use, false);
> >       }
> >   }
> >
> >   And I have two questions.
> >   1) What are the reasons or background for not forward propagating
> > addresses into loops ?
> >   2) Can we still forward propagate addresses if the def and use are in the
> > same loop ?
> >   I mean something like:
> 
> The condiition indeed looks odd, the canonical way would be to check
> 
>   !flow_loop_nested_p (DF_REF_BB (def)->loop_father, DF_REF_BB
> (use)->loop_father)
> 
> which would allow propagating addresses defined in loops outside as well.
> And loop_father should never be NULL I think.

Thanks for replying!

I think your change will also propagate addresses from one loop to another.
If def's loop is less frequent than use's, maybe it'll get worse performance.
I suggest we can go with the following condition
  DF_REF_BB(def)->loop_father == DF_REF_BB(use)->loop_father
  || flow_loop_nested_p (DF_REF_BB(use)->loop_father,
                       DF_REF_BB(def)->loop_father)


Also I find that function should_replace_address returns true
when it has a positive gain.
/* OLD is a memory address.  Return whether it is good to use NEW instead,
   for a memory access in the given MODE.  */
static bool
should_replace_address (rtx old_rtx, rtx new_rtx, machine_mode mode,
                        addr_space_t as, bool speed)
{
  int gain;

  if (rtx_equal_p (old_rtx, new_rtx)
      || !memory_address_addr_space_p (mode, new_rtx, as))
    return false;

  /* Copy propagation is always ok.  */
  if (REG_P (old_rtx) && REG_P (new_rtx))
    return true;

  /* Prefer the new address if it is less expensive.  */
  gain = (address_cost (old_rtx, mode, as, speed)
          - address_cost (new_rtx, mode, as, speed));

  /* If the addresses have equivalent cost, prefer the new address
     if it has the highest `set_src_cost'.  That has the potential of
     eliminating the most insns without additional costs, and it
     is the same that cse.c used to do.  */
  if (gain == 0)
    gain = (set_src_cost (new_rtx, VOIDmode, speed)
            - set_src_cost (old_rtx, VOIDmode, speed));

  return (gain > 0);  <<<<<<<<
}

Actually we can choose the new address if they have the same cost,
because we may get some other benefits.
Compare
a) m = n + 10
  MEM[m + 20] = 0
and
b) m = n + 10
  MEM[n + 30] = 0
Although we have no gain in memory operation (they have the same
` address_cost' and ` set_src_cost'), we may have a chance to eliminate
the dead code ` m = n + 10' in (b).

Best regards!

> 
> > diff -Nurp a/gcc/fwprop.c b/gcc/fwprop.c
> > --- a/gcc/fwprop.c      2020-03-27 03:17:50.704000000 -0400
> > +++ b/gcc/fwprop.c      2020-03-27 04:58:35.148000000 -0400
> > @@ -1573,10 +1573,12 @@ fwprop (bool fwprop_addr_p)
> >        df_ref use = DF_USES_GET (i);
> >        if (use)
> >         {
> > +         df_ref def = get_def_for_use (use);
> >           if (DF_REF_TYPE (use) == DF_REF_REG_USE
> >               || DF_REF_BB (use)->loop_father == NULL
> >               /* The outer most loop is not really a loop.  */
> > -             || loop_outer (DF_REF_BB (use)->loop_father) == NULL)
> > +             || loop_outer (DF_REF_BB (use)->loop_father) == NULL
> > +             || (def && DF_REF_BB (def)->loop_father == DF_REF_BB
> > (use)->loop_father))
> >             forward_propagate_into (use, fwprop_addr_p);
> >
> >           else if (fwprop_addr_p)
> >
> > I would be grateful if anyone could help.
> >
> > Best regards