Re: [PATCH 2/2] ivopts: Consider number of invariants when calculating register pressure.

[Richard Biener <richard.guenther@gmail.com>]

On Fri, Oct 28, 2022 at 3:39 PM Dimitrije Milosevic
<Dimitrije.Milosevic@syrmia.com> wrote:
>
> Hi Richard,
>
> > It's n_invs + 2 * n_cands?
>
> Correct, n_invs + 2 * n_cands, my apologies.
>
> > The comment says we want to prefer eliminating IVs over invariants.  Your patch
> > undoes that by weighting invariants the same so it does no longer have
> > the effect
> > of the comment.
>
> I see how my patch may have confused you.
> My concern is the "If we have enough registers." case - if we do have
> enough registers to store both the invariants and induction variables, I think the cost
> should be equal to the sum of those.
>
> I understand that adding another n_cands could be used as a tie-breaker for the two
> cases where we do have enough registers and the sum of n_invs and n_cands is equal,
> however I think there are two problems with that:
> - How often does it happen that we have two cases where we do have enough registers,
>   n_invs + n_cands sums are equal, and n_cands differ? I think that's pretty rare.
> - Bumping up the cost by another n_cands may lead to cost for the "If we do have
> enough registers." case to be higher than for other cases, which doesn't make sense.
> I can refer to the test case that I presented in [0] for the second point.

The odd thing I notice is that for all cases but the "we have enough
registers" case we
scale cost by target_reg_cost[speed] or target_spill_cost[speed] but
in that special
case we use the plain sum of n_invs + n_cands.

That makes this case "extra cheap" which is possibly OK.

Instead of adding another n_invs it would have been clearer to remove the add of
n_cands, no?  Or indeed as you say return n_new from the first case.

> Also worth noting is that the estimate_reg_pressure_cost function (used before c18101f)
> follows this:
>
>   /* If we have enough registers, we should use them and not restrict
>      the transformations unnecessarily.  */
>   if (regs_needed + target_res_regs <= available_regs)
>     return 0;
>
> As far as preferring to eliminate induction variables if possible, don't we already do that,
> for example:
>
>   /* If the number of candidates runs out available registers, we penalize
>      extra candidate registers using target_spill_cost * 2.  Because it is
>      more expensive to spill induction variable than invariant.  */
>   else
>     cost = target_reg_cost [speed] * available_regs
>            + target_spill_cost [speed] * (n_cands - available_regs) * 2
>            + target_spill_cost [speed] * (regs_needed - n_cands);
>
> To clarify, what my patch did was that it gave every case a base cost of
> n_invs + n_cands. This base cost gets bumped up accordingly, for each
> one of the cases (by the amount equal to "cost = ..." statement prior to
> the return statement in the ivopts_estimate_reg_pressure function).
> I agree that my patch isn't clear on my intention, and that it also does
> not correspond to the comment.
> What I could do is just return n_new as the cost for the
> "If we do have enough registers." case, but I would love to hear your
> thoughts, if I clarified my intention a little bit.

You did.  Note IVOPTs costing is tricky at best and I don't have a very good
feeling why biasing things with n_invs should be a general improvement.
The situation where it makes a difference should be as rare as the
situation you describe above.

I'd love to see the function a bit simplified, it seems we are going to compare
'cost' as computed by this function from different cases so making them
less apples vs. oranges would be good - I just don't see how your patch
does that.  It might be that the bias should be applied when computing
iv_ca_delta or when comparing two iv_ca rather than trying to magically
adjust 'cost'.  When that is really the problem you are trying to solve.

>
> [0] https://gcc.gnu.org/pipermail/gcc-patches/2022-October/604304.html
>
> Regards,
> Dimitrije
>
> From: Richard Biener <richard.guenther@gmail.com>
> Sent: Friday, October 28, 2022 9:38 AM
> To: Dimitrije Milosevic <Dimitrije.Milosevic@Syrmia.com>
> Cc: gcc-patches@gcc.gnu.org <gcc-patches@gcc.gnu.org>; Djordje Todorovic <Djordje.Todorovic@syrmia.com>
> Subject: Re: [PATCH 2/2] ivopts: Consider number of invariants when calculating register pressure.
>
> On Tue, Oct 25, 2022 at 3:00 PM Dimitrije Milosevic
> <Dimitrije.Milosevic@syrmia.com> wrote:
> >
> > Hi Richard,
> >
> > > don't you add n_invs twice now given
> > >
> > >  unsigned n_old = data->regs_used, n_new = n_invs + n_cands;
> > >  unsigned regs_needed = n_new + n_old, available_regs = target_avail_regs;
> > >
> > > ?
> >
> > If you are referring to the "If we have enough registers." case, correct. After c18101f,
> > for that case, the returned cost is equal to 2 * n_invs + n_cands.
>
> It's n_invs + 2 * n_cands?  And the comment states the reasoning.
>
>  Before c18101f, for
> > that case, the returned cost is equal to n_invs + n_cands. Another solution would be
> > to just return n_invs + n_cands if we have enough registers.
>
> The comment says we want to prefer eliminating IVs over invariants.  Your patch
> undoes that by weighting invariants the same so it does no longer have
> the effect
> of the comment.
>
> > Regards,
> > Dimitrije
> >
> >
> > From: Richard Biener <richard.guenther@gmail.com>
> > Sent: Tuesday, October 25, 2022 1:07 PM
> > To: Dimitrije Milosevic <Dimitrije.Milosevic@Syrmia.com>
> > Cc: gcc-patches@gcc.gnu.org <gcc-patches@gcc.gnu.org>; Djordje Todorovic <Djordje.Todorovic@syrmia.com>
> > Subject: Re: [PATCH 2/2] ivopts: Consider number of invariants when calculating register pressure.
> >
> > On Fri, Oct 21, 2022 at 3:57 PM Dimitrije Milosevic
> > <dimitrije.milosevic@syrmia.com> wrote:
> > >
> > > From: Dimitrije Milošević <dimitrije.milosevic@syrmia.com>
> > >
> > > This patch slightly modifies register pressure model function to consider
> > > both the number of invariants and the number of candidates, rather than
> > > just the number of candidates. This used to be the case before c18101f.
> >
> > don't you add n_invs twice now given
> >
> >   unsigned n_old = data->regs_used, n_new = n_invs + n_cands;
> >   unsigned regs_needed = n_new + n_old, available_regs = target_avail_regs;
> >
> > ?
> >
> > > gcc/ChangeLog:
> > >
> > >         * tree-ssa-loop-ivopts.cc (ivopts_estimate_reg_pressure): Adjust.
> > >
> > > Signed-off-by: Dimitrije Milosevic <dimitrije.milosevic@syrmia.com>
> > > ---
> > >  gcc/tree-ssa-loop-ivopts.cc | 6 +++---
> > >  1 file changed, 3 insertions(+), 3 deletions(-)
> > >
> > > diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc
> > > index d53ba05a4f6..9d0b669d671 100644
> > > --- a/gcc/tree-ssa-loop-ivopts.cc
> > > +++ b/gcc/tree-ssa-loop-ivopts.cc
> > > @@ -6409,9 +6409,9 @@ ivopts_estimate_reg_pressure (struct ivopts_data *data, unsigned n_invs,
> > >            + target_spill_cost [speed] * (n_cands - available_regs) * 2
> > >            + target_spill_cost [speed] * (regs_needed - n_cands);
> > >
> > > -  /* Finally, add the number of candidates, so that we prefer eliminating
> > > -     induction variables if possible.  */
> > > -  return cost + n_cands;
> > > +  /* Finally, add the number of invariants and the number of candidates,
> > > +     so that we prefer eliminating induction variables if possible.  */
> > > +  return cost + n_invs + n_cands;
> > >  }
> > >
> > >  /* For each size of the induction variable set determine the penalty.  */
> > > --
> > > 2.25.1
> > >