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

  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.

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(-)
  

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
>
  

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

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
>
  

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

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

[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
> >
  

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