[PATCH] rtlanal: Correct cost regularization in pattern_cost

[PATCH] rtlanal: Correct cost regularization in pattern_cost

[HAO CHEN GUI]

Hi,
   The cost return from set_src_cost might be zero. Zero for
pattern_cost means unknown cost. So the regularization converts the zero
to COSTS_N_INSNS (1).

   // pattern_cost
   cost = set_src_cost (SET_SRC (set), GET_MODE (SET_DEST (set)), speed);
   return cost > 0 ? cost : COSTS_N_INSNS (1);

   But if set_src_cost returns a value less than COSTS_N_INSNS (1), it's
untouched and just returned by pattern_cost. Thus "zero" from set_src_cost
is higher than "one" from set_src_cost.

  For instance, i386 returns cost "one" for zero_extend op.
    //ix86_rtx_costs
    case ZERO_EXTEND:
      /* The zero extensions is often completely free on x86_64, so make
         it as cheap as possible.  */
      if (TARGET_64BIT && mode == DImode
          && GET_MODE (XEXP (x, 0)) == SImode)
        *total = 1;

  This patch fixes the problem by converting all costs which are less than
COSTS_N_INSNS (1) to COSTS_N_INSNS (1).

  Bootstrapped and tested on x86 and powerpc64-linux BE and LE with no
regressions. Is it OK for the trunk?

Thanks
Gui Haochen

ChangeLog
rtlanal: Correct cost regularization in pattern_cost

For the pattern_cost (insn_cost), the smallest known cost is
COSTS_N_INSNS (1) and zero means the cost is unknown.  The method calls
set_src_cost which might returns 0 or a value less than COSTS_N_INSNS (1).
For these cases, pattern_cost should always return COSTS_N_INSNS (1).
Current regularization is wrong and a value less than COSTS_N_INSNS (1)
but larger than 0 will be returned.  This patch corrects it.

gcc/
	* rtlanal.cc (pattern_cost): Return COSTS_N_INSNS (1) when the cost
	is less than COSTS_N_INSNS (1).

patch.diff
diff --git a/gcc/rtlanal.cc b/gcc/rtlanal.cc
index 4158a531bdd..f7b3d7d72ce 100644
--- a/gcc/rtlanal.cc
+++ b/gcc/rtlanal.cc
@@ -5762,7 +5762,7 @@ pattern_cost (rtx pat, bool speed)
     return 0;

   cost = set_src_cost (SET_SRC (set), GET_MODE (SET_DEST (set)), speed);
-  return cost > 0 ? cost : COSTS_N_INSNS (1);
+  return cost > COSTS_N_INSNS (1) ? cost : COSTS_N_INSNS (1);
 }

 /* Calculate the cost of a single instruction.  A return value of zero

Re: [PATCH] rtlanal: Correct cost regularization in pattern_cost

[Richard Biener]

On Fri, May 10, 2024 at 4:25 AM HAO CHEN GUI <guihaoc@linux.ibm.com> wrote:
>
> Hi,
>    The cost return from set_src_cost might be zero. Zero for
> pattern_cost means unknown cost. So the regularization converts the zero
> to COSTS_N_INSNS (1).
>
>    // pattern_cost
>    cost = set_src_cost (SET_SRC (set), GET_MODE (SET_DEST (set)), speed);
>    return cost > 0 ? cost : COSTS_N_INSNS (1);
>
>    But if set_src_cost returns a value less than COSTS_N_INSNS (1), it's
> untouched and just returned by pattern_cost. Thus "zero" from set_src_cost
> is higher than "one" from set_src_cost.
>
>   For instance, i386 returns cost "one" for zero_extend op.
>     //ix86_rtx_costs
>     case ZERO_EXTEND:
>       /* The zero extensions is often completely free on x86_64, so make
>          it as cheap as possible.  */
>       if (TARGET_64BIT && mode == DImode
>           && GET_MODE (XEXP (x, 0)) == SImode)
>         *total = 1;
>
>   This patch fixes the problem by converting all costs which are less than
> COSTS_N_INSNS (1) to COSTS_N_INSNS (1).
>
>   Bootstrapped and tested on x86 and powerpc64-linux BE and LE with no
> regressions. Is it OK for the trunk?

But if targets return sth < COSTS_N_INSNS (1) but > 0 this is now no
longer meaningful.  So shouldn't it instead be

  return cost > 0 ? cost : 1;

?  Alternatively returning fractions of COSTS_N_INSNS (1) from set_src_cost
is invalid and thus the target is at fault (I do think that making zero the
unknown value is quite bad since that makes it impossible to have zero
as cost represented).

It seems the check is to aovid pattern_cost return zero (unknown), so the
comment holds to pattern_cost the same (it returns an 'int' so the better
exceptional value would have been -1, avoiding the compare).

Richard.

> Thanks
> Gui Haochen
>
> ChangeLog
> rtlanal: Correct cost regularization in pattern_cost
>
> For the pattern_cost (insn_cost), the smallest known cost is
> COSTS_N_INSNS (1) and zero means the cost is unknown.  The method calls
> set_src_cost which might returns 0 or a value less than COSTS_N_INSNS (1).
> For these cases, pattern_cost should always return COSTS_N_INSNS (1).
> Current regularization is wrong and a value less than COSTS_N_INSNS (1)
> but larger than 0 will be returned.  This patch corrects it.
>
> gcc/
>         * rtlanal.cc (pattern_cost): Return COSTS_N_INSNS (1) when the cost
>         is less than COSTS_N_INSNS (1).
>
> patch.diff
> diff --git a/gcc/rtlanal.cc b/gcc/rtlanal.cc
> index 4158a531bdd..f7b3d7d72ce 100644
> --- a/gcc/rtlanal.cc
> +++ b/gcc/rtlanal.cc
> @@ -5762,7 +5762,7 @@ pattern_cost (rtx pat, bool speed)
>      return 0;
>
>    cost = set_src_cost (SET_SRC (set), GET_MODE (SET_DEST (set)), speed);
> -  return cost > 0 ? cost : COSTS_N_INSNS (1);
> +  return cost > COSTS_N_INSNS (1) ? cost : COSTS_N_INSNS (1);
>  }
>
>  /* Calculate the cost of a single instruction.  A return value of zero

Re: [PATCH] rtlanal: Correct cost regularization in pattern_cost

[HAO CHEN GUI]

Hi Richard,
  Thanks for your comments.

在 2024/5/10 15:16, Richard Biener 写道:
> But if targets return sth < COSTS_N_INSNS (1) but > 0 this is now no
> longer meaningful.  So shouldn't it instead be
> 
>   return cost > 0 ? cost : 1;
Yes, it's better.

> 
> ?  Alternatively returning fractions of COSTS_N_INSNS (1) from set_src_cost
> is invalid and thus the target is at fault (I do think that making zero the
> unknown value is quite bad since that makes it impossible to have zero
> as cost represented).
> 
> It seems the check is to aovid pattern_cost return zero (unknown), so the
> comment holds to pattern_cost the same (it returns an 'int' so the better
> exceptional value would have been -1, avoiding the compare).
But sometime it adds an insn cost. If the unknown cost is -1, the total cost
might be distorted.

> 
> Richard.

Thanks
Gui Haochen

Re: [PATCH] rtlanal: Correct cost regularization in pattern_cost

[Segher Boessenkool]

Hi!

On Fri, May 10, 2024 at 09:16:26AM +0200, Richard Biener wrote:
> On Fri, May 10, 2024 at 4:25 AM HAO CHEN GUI <guihaoc@linux.ibm.com> wrote:
> >    But if set_src_cost returns a value less than COSTS_N_INSNS (1), it's
> > untouched and just returned by pattern_cost. Thus "zero" from set_src_cost
> > is higher than "one" from set_src_cost.
> >
> >   For instance, i386 returns cost "one" for zero_extend op.
> >     //ix86_rtx_costs
> >     case ZERO_EXTEND:
> >       /* The zero extensions is often completely free on x86_64, so make
> >          it as cheap as possible.  */
> >       if (TARGET_64BIT && mode == DImode
> >           && GET_MODE (XEXP (x, 0)) == SImode)
> >         *total = 1;
> >
> >   This patch fixes the problem by converting all costs which are less than
> > COSTS_N_INSNS (1) to COSTS_N_INSNS (1).
> >
> >   Bootstrapped and tested on x86 and powerpc64-linux BE and LE with no
> > regressions. Is it OK for the trunk?
> 
> But if targets return sth < COSTS_N_INSNS (1) but > 0 this is now no
> longer meaningful.  So shouldn't it instead be
> 
>   return cost > 0 ? cost : 1;

I don't think either is very good.  Why does it want to convert "unknown
cost" to some known cost at all?  Fixing *that* would really improve
things!

> ?  Alternatively returning fractions of COSTS_N_INSNS (1) from set_src_cost
> is invalid and thus the target is at fault (I do think that making zero the
> unknown value is quite bad since that makes it impossible to have zero
> as cost represented).

No, we have COST_N_INSNS exactly because fractions of integer costs are
useful to have.  COST_N_INSNS (1) really stands for "the cost of a cheap
integer isns with latency 1", and many targets want to express some
insns are better than others, even if they have the same latency.
Perhaps some insns use less of some resource, etc.

> It seems the check is to aovid pattern_cost return zero (unknown), so the
> comment holds to pattern_cost the same (it returns an 'int' so the better
> exceptional value would have been -1, avoiding the compare).

Cost 0 for unkown is used in (almost) *all* cost things in RTL.  Pretty
much everything can deal with it just fine.  What is different here?

The abstraction "pattern_cost" is a lousy abstraction of course, but
where is this used?  Cost "unknown" can be passed through everywhere,
in principle.


Segher

Re: [PATCH] rtlanal: Correct cost regularization in pattern_cost

[Segher Boessenkool]

On Fri, May 10, 2024 at 04:50:10PM +0800, HAO CHEN GUI wrote:
> Hi Richard,
>   Thanks for your comments.
> 
> 在 2024/5/10 15:16, Richard Biener 写道:
> > But if targets return sth < COSTS_N_INSNS (1) but > 0 this is now no
> > longer meaningful.  So shouldn't it instead be
> > 
> >   return cost > 0 ? cost : 1;
> Yes, it's better.
> 
> > 
> > ?  Alternatively returning fractions of COSTS_N_INSNS (1) from set_src_cost
> > is invalid and thus the target is at fault (I do think that making zero the
> > unknown value is quite bad since that makes it impossible to have zero
> > as cost represented).
> > 
> > It seems the check is to aovid pattern_cost return zero (unknown), so the
> > comment holds to pattern_cost the same (it returns an 'int' so the better
> > exceptional value would have been -1, avoiding the compare).
> But sometime it adds an insn cost. If the unknown cost is -1, the total cost
> might be distorted.

*All* code using a cost will have to be inspected and possibly adjusted
if you decide to use a different value for "unknown" than what we have
had for ages.  All other cost functions interacting with this one, too.


Segher

Re: [PATCH] rtlanal: Correct cost regularization in pattern_cost

[Richard Biener]

On Fri, May 10, 2024 at 11:06 AM Segher Boessenkool
<segher@kernel.crashing.org> wrote:
>
> On Fri, May 10, 2024 at 04:50:10PM +0800, HAO CHEN GUI wrote:
> > Hi Richard,
> >   Thanks for your comments.
> >
> > 在 2024/5/10 15:16, Richard Biener 写道:
> > > But if targets return sth < COSTS_N_INSNS (1) but > 0 this is now no
> > > longer meaningful.  So shouldn't it instead be
> > >
> > >   return cost > 0 ? cost : 1;
> > Yes, it's better.
> >
> > >
> > > ?  Alternatively returning fractions of COSTS_N_INSNS (1) from set_src_cost
> > > is invalid and thus the target is at fault (I do think that making zero the
> > > unknown value is quite bad since that makes it impossible to have zero
> > > as cost represented).
> > >
> > > It seems the check is to aovid pattern_cost return zero (unknown), so the
> > > comment holds to pattern_cost the same (it returns an 'int' so the better
> > > exceptional value would have been -1, avoiding the compare).
> > But sometime it adds an insn cost. If the unknown cost is -1, the total cost
> > might be distorted.
>
> *All* code using a cost will have to be inspected and possibly adjusted
> if you decide to use a different value for "unknown" than what we have
> had for ages.  All other cost functions interacting with this one, too.

Btw, looking around pattern_cost is the only API documenting this special
value and the function after it using this function, insn_cost does the same
but

int
insn_cost (rtx_insn *insn, bool speed)
{
  if (targetm.insn_cost)
    return targetm.insn_cost (insn, speed);

and the target hook doesn't document this special value.  set_src_cost
doesn't either, btw (that just uses rtx_cost).  So I don't think how
pattern_cost handles the set_src_cost result is warranted.  There's
simply no way to detect whether set_src_cost returns an actual
value - on the contrary, it always does.

Richard.

>
> Segher

Re: [PATCH] rtlanal: Correct cost regularization in pattern_cost

[Segher Boessenkool]

On Fri, May 10, 2024 at 12:19:35PM +0200, Richard Biener wrote:
> On Fri, May 10, 2024 at 11:06 AM Segher Boessenkool
> <segher@kernel.crashing.org> wrote:
> > *All* code using a cost will have to be inspected and possibly adjusted
> > if you decide to use a different value for "unknown" than what we have
> > had for ages.  All other cost functions interacting with this one, too.
> 
> Btw, looking around pattern_cost is the only API documenting this special
> value and the function after it using this function, insn_cost does the same
> but
> 
> int
> insn_cost (rtx_insn *insn, bool speed)
> {
>   if (targetm.insn_cost)
>     return targetm.insn_cost (insn, speed);
> 
> and the target hook doesn't document this special value.  set_src_cost
> doesn't either, btw (that just uses rtx_cost).  So I don't think how
> pattern_cost handles the set_src_cost result is warranted.  There's
> simply no way to detect whether set_src_cost returns an actual
> value - on the contrary, it always does.

I introduced insn_cost.  I didn't think about documenting that 0 means
unknown, precisely because that is so pervasive!


Segher

Re: [PATCH] rtlanal: Correct cost regularization in pattern_cost

[Richard Biener]

On Fri, May 10, 2024 at 12:54 PM Segher Boessenkool
<segher@kernel.crashing.org> wrote:
>
> On Fri, May 10, 2024 at 12:19:35PM +0200, Richard Biener wrote:
> > On Fri, May 10, 2024 at 11:06 AM Segher Boessenkool
> > <segher@kernel.crashing.org> wrote:
> > > *All* code using a cost will have to be inspected and possibly adjusted
> > > if you decide to use a different value for "unknown" than what we have
> > > had for ages.  All other cost functions interacting with this one, too.
> >
> > Btw, looking around pattern_cost is the only API documenting this special
> > value and the function after it using this function, insn_cost does the same
> > but
> >
> > int
> > insn_cost (rtx_insn *insn, bool speed)
> > {
> >   if (targetm.insn_cost)
> >     return targetm.insn_cost (insn, speed);
> >
> > and the target hook doesn't document this special value.  set_src_cost
> > doesn't either, btw (that just uses rtx_cost).  So I don't think how
> > pattern_cost handles the set_src_cost result is warranted.  There's
> > simply no way to detect whether set_src_cost returns an actual
> > value - on the contrary, it always does.
>
> I introduced insn_cost.  I didn't think about documenting that 0 means
> unknown, precisely because that is so pervasive!

But for example a reg-reg move when optimizing for speed could have
a zero associated cost.  You might argue that's a bug since there's
an actual instruction and thus at least a size cost (and decode cost)
but then I've seen too much zero cost stuff in backends (like that
combine PR causing s390 backend making address-cost zero even
though it's just "same cost").

IMO give we're dispatching to the rtx_cost hook eventually it needs
documenting there or alternatively catching zero and adjusting its
result there.  Of course cost == 0 ? 1 : cost is wrong as it makes
zero vs. one the same cost - using cost + 1 when from rtx_cost
might be more correct, at least preserving relative costs.

Richard.

>
>
> Segher

Re: [PATCH] rtlanal: Correct cost regularization in pattern_cost

[Segher Boessenkool]

On Fri, May 10, 2024 at 02:50:56PM +0200, Richard Biener wrote:
> But for example a reg-reg move when optimizing for speed could have
> a zero associated cost.

Sure, but this is the way things always have been.  I'm sure there are
ways to change things so they become slightly easier to use, but that is
not what we have now (or what we ever have had).

> You might argue that's a bug since there's
> an actual instruction and thus at least a size cost (and decode cost)
> but then I've seen too much zero cost stuff in backends (like that
> combine PR causing s390 backend making address-cost zero even
> though it's just "same cost").

address_cost is something else entirely.  Many backends have that set
to 0 btw, and that means 0, not "unknown".  It means all forms of
address in valid machine instructions have the same execution (or size)
costs.

> IMO give we're dispatching to the rtx_cost hook eventually it needs
> documenting there or alternatively catching zero and adjusting its
> result there.  Of course cost == 0 ? 1 : cost is wrong as it makes
> zero vs. one the same cost - using cost + 1 when from rtx_cost
> might be more correct, at least preserving relative costs.

Most things should not use rtx_cost at all, only insn_cost.  Taking the
"cost" of any random RTL expression makes no sense at all.  Neither
conceptually, nor practically: it causes many problems, and solves none.

Most things already use only insn_cost, if you have the appropriate
hooks implemented in your backend (all one of them even).  This is so
much easier to use (you only need to recognise some big categories of
instructions, for a typical target core, instead of eighty different
RTX codes, and the combination of them), and gives way better results.


Segher

Re: [PATCH] rtlanal: Correct cost regularization in pattern_cost

[HAO CHEN GUI]

Hi,

在 2024/5/10 20:50, Richard Biener 写道:
> IMO give we're dispatching to the rtx_cost hook eventually it needs
> documenting there or alternatively catching zero and adjusting its
> result there.  Of course cost == 0 ? 1 : cost is wrong as it makes
> zero vs. one the same cost - using cost + 1 when from rtx_cost
> might be more correct, at least preserving relative costs.

I tested the draft patch which sets "cost > 0 ? cost + 1 : 1;". Some
regression cases are found on x86. The main problems are:

The cost compare with COSTS_N_INSNS (1) doesn't works any more with
the patch. As all costs are added with 1, the following compare
returns true when the cost is 5 but false originally.
      if (cost > COSTS_N_INSNS (1))

Another problem is the cost is from set_src_cost, it doesn't take dest
into consideration. For example, the cost of a store "[`x']=r109:SI"
is set to 1 as it only measure the cost of set_src. It seems
unreasonable.

IMHO, the cost less than COSTS_N_INSNS (1) is meaningful in rtx_cost
calculation but unreasonable for an insn. Should the minimum cost of
an insn be set to COSTS_N_INSNS (1)?

Thanks
Gui Haochen

Re: [PATCH] rtlanal: Correct cost regularization in pattern_cost

[Richard Sandiford]

Richard Biener <richard.guenther@gmail.com> writes:
> On Fri, May 10, 2024 at 4:25 AM HAO CHEN GUI <guihaoc@linux.ibm.com> wrote:
>>
>> Hi,
>>    The cost return from set_src_cost might be zero. Zero for
>> pattern_cost means unknown cost. So the regularization converts the zero
>> to COSTS_N_INSNS (1).
>>
>>    // pattern_cost
>>    cost = set_src_cost (SET_SRC (set), GET_MODE (SET_DEST (set)), speed);
>>    return cost > 0 ? cost : COSTS_N_INSNS (1);
>>
>>    But if set_src_cost returns a value less than COSTS_N_INSNS (1), it's
>> untouched and just returned by pattern_cost. Thus "zero" from set_src_cost
>> is higher than "one" from set_src_cost.
>>
>>   For instance, i386 returns cost "one" for zero_extend op.
>>     //ix86_rtx_costs
>>     case ZERO_EXTEND:
>>       /* The zero extensions is often completely free on x86_64, so make
>>          it as cheap as possible.  */
>>       if (TARGET_64BIT && mode == DImode
>>           && GET_MODE (XEXP (x, 0)) == SImode)
>>         *total = 1;
>>
>>   This patch fixes the problem by converting all costs which are less than
>> COSTS_N_INSNS (1) to COSTS_N_INSNS (1).
>>
>>   Bootstrapped and tested on x86 and powerpc64-linux BE and LE with no
>> regressions. Is it OK for the trunk?
>
> But if targets return sth < COSTS_N_INSNS (1) but > 0 this is now no
> longer meaningful.  So shouldn't it instead be
>
>   return cost > 0 ? cost : 1;
>
> ?  Alternatively returning fractions of COSTS_N_INSNS (1) from set_src_cost
> is invalid and thus the target is at fault (I do think that making zero the
> unknown value is quite bad since that makes it impossible to have zero
> as cost represented).

I agree zero is an unfortunate choice.  No-op moves should really have
zero cost, without having to be special-cased by callers.  And it came
as a surprise to me that we had this rule.

But like Segher says, it seems to have been around for a long time
(since 2004 by the looks of it, r0-59417).  Which just goes to show,
every day is a learning day. :)

IMO it would be nice to change it.  But then it would be even nicer
to get rid of pattern_cost and move everything to insn_cost.  And that's
going to be a lot of work to do together.

Maybe a compromise would be to open-code pattern_cost into insn_cost
and change the return value for insn_cost only?  That would still mean
auditing all current uses of insn_cost and all current target definitions
of the insn_cost hook, but at least it would be isolated from the work
of removing pattern_cost.

Thanks,
Richard