RE: [PATCH 1/3]middle-end: Add the ability to let the target decide the method of argument promotions.

[Tamar Christina <Tamar.Christina@arm.com>]

> -----Original Message-----
> From: Richard Sandiford <richard.sandiford@arm.com>
> Sent: Monday, May 16, 2022 2:24 PM
> To: Tamar Christina <Tamar.Christina@arm.com>
> Cc: gcc-patches@gcc.gnu.org; nd <nd@arm.com>; rguenther@suse.de;
> jeffreyalaw@gmail.com
> Subject: Re: [PATCH 1/3]middle-end: Add the ability to let the target decide
> the method of argument promotions.
> 
> Tamar Christina <Tamar.Christina@arm.com> writes:
> >> -----Original Message-----
> >> From: Richard Sandiford <richard.sandiford@arm.com>
> >> Sent: Monday, May 16, 2022 1:18 PM
> >> To: Tamar Christina <Tamar.Christina@arm.com>
> >> Cc: gcc-patches@gcc.gnu.org; nd <nd@arm.com>; rguenther@suse.de;
> >> jeffreyalaw@gmail.com
> >> Subject: Re: [PATCH 1/3]middle-end: Add the ability to let the target
> >> decide the method of argument promotions.
> >>
> >> Richard Sandiford via Gcc-patches <gcc-patches@gcc.gnu.org> writes:
> >> > Tamar Christina <Tamar.Christina@arm.com> writes:
> >> >>> -----Original Message-----
> >> >>> From: Richard Sandiford <richard.sandiford@arm.com>
> >> >>> Sent: Monday, May 16, 2022 12:36 PM
> >> >>> To: Tamar Christina <Tamar.Christina@arm.com>
> >> >>> Cc: gcc-patches@gcc.gnu.org; nd <nd@arm.com>;
> rguenther@suse.de;
> >> >>> jeffreyalaw@gmail.com
> >> >>> Subject: Re: [PATCH 1/3]middle-end: Add the ability to let the
> >> >>> target decide the method of argument promotions.
> >> >>>
> >> >>> Tamar Christina <tamar.christina@arm.com> writes:
> >> >>> > Hi All,
> >> >>> >
> >> >>> > Some targets require function parameters to be promoted to a
> >> >>> > different type on expand time because the target may not have
> >> >>> > native instructions to work on such types.  As an example the
> >> >>> > AArch64 port does not have native instructions working on
> >> >>> > integer
> >> >>> > 8- or 16-bit values.  As such it promotes every parameter of
> >> >>> > these
> >> types to 32-bits.
> >> >>>
> >> >>> This doesn't seem specific to parameters though.  It applies to
> >> >>> any
> >> >>> 8- or 16-bit variable.  E.g.:
> >> >>>
> >> >>> #include <stdint.h>
> >> >>> uint8_t foo(uint32_t x, uint32_t y) {
> >> >>>     uint8_t z = x != 0 ? x : y;
> >> >>>     return z + 1;
> >> >>> }
> >> >>>
> >> >>> generates:
> >> >>>
> >> >>> foo:
> >> >>>         cmp     w0, 0
> >> >>>         and     w1, w1, 255
> >> >>>         and     w0, w0, 255
> >> >>>         csel    w0, w1, w0, eq
> >> >>>         add     w0, w0, 1
> >> >>>         ret
> >> >>>
> >> >>> So I think the new behaviour is really a modification of the
> >> >>> PROMOTE_MODE behaviour rather than the
> >> PROMOTE_FUNCTION_MODE behaviour.
> >> >>>
> >> >>> FWIW, I agree with Richard that it would be better not to add a
> >> >>> new
> >> hook.
> >> >>> I think we're really making PROMOTE_MODE choose between
> >> SIGN_EXTEND,
> >> >>> ZERO_EXTEND or SUBREG (what LLVM would call “any
> >> >>> extend”) rather than the current SIGN_EXTEND vs. ZERO_EXTEND
> >> choice.
> >> >>
> >> >> Ah, I hadn't realized this also applied to locals.. ok I can
> >> >> modify PROMOTE_MODE then, but I also need the actual SSA_NAME
> and
> >> >> not just
> >> the type so will have to pass this along.
> >> >>
> >> >> From a practical point of view.. the actual hook however is
> >> >> implemented by 34 targets, would I need to CC maintainers for each
> >> >> of them or would global maintainer approval suffice for these
> >> >> mostly
> >> mechanical changes?
> >> >
> >> > Yeah, single approval should be enough mechanical changes.  It
> >> > would be good to do the interface change and mechanical target
> >> > changes as a separate prepatch if possible though.
> >> >
> >> > I'm not sure about passing the SSA name to the target though, or
> >> > the way that the aarch64 hook uses the info.  It looks like a
> >> > single cold comparison could defeat the optimisation for hot code.
> >
> > I'm not sure I follow why the likelihood of the comparison matters in this
> case..
> > I'll expand on it below..
> 
> I meant the likelihood that the comparison is executed at all, not which
> outcome is more likely.  E.g. suppose the only comparison occurs on a failure
> path that eventually calls abort, and that there are other paths (without
> comparisons of the same value) that would benefit from the any-extend
> optimisation.  We'd prioritise the cold comparison over optimising the other
> (hot) code.
> 
> I'm just suspicious of heuristics along the lines of “don't do X if there is a
> single instance of Y”. :-)

I'm probably very dense here sorry.. but if there's

1 use: the zero extend gets pushed down into the branch which needs it.

i.e. in:

extern void foo ();
extern void bar ();

uint8_t f (uint8_t a, uint8_t b)
{
  if (b) {
    if (a)
      foo ();
    else
      return f (a, b);
  } else {
      bar ();
  }
  return b;
}

The zero extend of a is only done in the true branch for if (b).  Secondly the zero
extended form is the basis for all other patterns we form, such as ands, which is
the combination of the zero extend and compare.

2 uses, both live:

extern void foo ();
extern void bar (uint8_t);

uint8_t f (uint8_t a, uint8_t b)
{
  if (b) {
    if (a)
      foo ();
    else
      return f (a, b);
  } else {
      bar (a);
  }
  return b;
}

In which case the extend of a is done before the if (b) and only the extended values
used.

Even if you had multiple cold/unused branches, I struggle to see any case where the
any-extend would be better.  Reload must keep the value live as it's a param. Either you:

1. have enough registers to keep the value live, in which case, instead of doing a "mov" to
     To copy the value and then later an AND or TST, it's better to just do an and instead of the mov.
      You keep the same number of registers live but in the best case you have 1 instruction less, and
       The worse case you have 0 instructions more.
2. You don't have enough registers to keep the value live, in which case the zero extended value is
     Still better because on the reload it can simply use ldrb ..., cbz as we use the load for an implicit
     zero extend. Which is still better than ldrb ..., tst, cbnz for an any-extend.

So I am genuinely struggling to see a case where any-extend is better for comparison. And the only
reason I am singling out comparisons is because in GIMPLE integer constants don't get an explicit
promotion to int.  Otherwise I wouldn't have needed to as it would have always required an extend
here.

> 
> >> > If we do try to make the decision based on uses at expand time, it
> >> > might be better for the analysis to be in target-independent code,
> >> > with help from the target to decide where extensions are cheap.  It
> >> > still feels a bit hacky though.
> >
> > I thought about it but can't see most target having this problem. I
> > did go with an optimistic heuristics. There are of course various ways
> > to defeat it but looking through the corpus of code I don't see any
> > but the simple cases in practice. (more below).
> >
> >> >
> >> > What stops us from forming cbz/cbnz when the extension is done
> >> > close to the comparison (from the comment in 2/3)?  If we can solve
> >> > that, could we simply do an any-extend all the time, and treat
> >> > removing redundant extensions as a global availability problem?
> >>
> >
> > In such cases there's no gain from doing the extension at all, e.g.
> > and w0, w0, 255
> > cmp w0, 0
> > b.eq .Lfoo
> >
> > will be optimized to
> >
> > tst w0, 0xff
> > b.ne .Lfoo
> >
> > already.
> >
> > In RTL the problem occurs when you have nested control flow like
> > nested if and switch statements The example in 2/3 was intended to
> > show that before what we'd do is
> >
> > and w22, w0, 255
> > .... <code that clobbers cc and caller saves> <switch1> cbz w22,
> > .Lfoo1 ....
> > <switch2>
> > cbz w22, .Lfoo2
> >
> > If we have a single comparison we already sink the zero_extend today.
> >
> > Now if we instead any-extend w0 we end up with:
> >
> > mov w22, w0
> > .... <code that clobbers cc and caller saves> <switch1> tst w22, 0xff
> > b.ne .Lfoo1 ....
> > <switch2>
> > tst w22, 0xff
> > b.ne .Lfoo2
> >
> > So you get an additional tst before each branch. You also can't perform the
> tst higher since CC is clobbered.
> > The cbz is nice because the zero extend doesn't use CC of course and
> > so having the value live allows us to optimize The branch.
> 
> Once the cbz has been formed (in combine), where does the optimisation of
> it happen?

There's no real "optimization". Combine combines the cmp 0 and br leaving the AND
behind.  Because of the live range required for the value reload must copy it away from
a caller save.  It chooses to move it to w22 in this case.

and w0, w0, 255
mov w22, w0

this simply gets simplified into and w22, w0, 255 by a zero extending move pattern.
The only optimization here is when the pattern isn't single use, it's simply not moved/folded.

The only options available to combine are

cmp, br = tst + br (in the case of a subreg where it can't tell what the top bits are)
and, cmp, br = ands + br (if value is single use)
cmp, br = cbz (in the case it knows that the top bits are 0).

If we emit a zero extend both operations above are possible, and we emit them depending on
value being single use or not.  If we emit a paradoxical subreg, we never form cbz unless the value
comes from an operation where GIMPLE has maintained C semantics.

But I am probably missing something.. so I'll just make the changes and see where we land 😊

> 
> > I don't think branch likeliness matters here as you must keep w22 live
> > in both cases somehow. In the SPECCPU 2017 Benchmark perlbench (which
> > uses a lot of nested switches) this pattern is responsible for an extra 0.3%
> codesize increase which the approach in 2/3 prevents.
> >
> >> (which would run after combine)
> >>
> >> >
> >> > What kind of code do we emit when do an extension just before an
> >> > operation?  If the DECL_RTL is (subreg:QI (reg:SI R) 0), say, then
> >> > it should be safe to do the extension directly into R:
> >> >
> >> >   (set (reg:SI X) (zero_extend:SI (subreg:QI (reg:SI X))))
> >>
> >> Oops, that should of course be:
> >>
> >>   (set (reg:SI R) (zero_extend:SI (subreg:QI (reg:SI R))))
> >>
> >> > which avoids the problem of having two values live at once (the
> >> > zero-extended value and the any-extended value)

I'm assuming R here is the hardreg which has the parameter? In which case
wouldn't the subreg be folded away? I.e you end up with

(set (reg:SI R) (zero_extend:SI (reg:QI R)))

? But that SET isn’t paradoxical, we wouldn't generate it.

We generate for e.g.:

#include <stdint.h>

uint16_t f8 (uint8_t xr, uint8_t xc){
    return (uint8_t)(xr * xc);
}

(insn 9 6 10 2 (set (reg:HI 101)                                                                                                                                                                                                                                                     (zero_extend:HI (reg/v:QI 96 [ xr ]))) "prom.c":4:16 -1                                                                                                                                                                                                                   (nil))                                                                                                                                                                                                                                                                  (insn 10 9 11 2 (set (reg:HI 102)                                                                                                                                                                                                                                                    (zero_extend:HI (reg/v:QI 98 [ xc ]))) "prom.c":4:16 -1                                                                                                                                                                                                                   (nil))                                                                                                                                                                                                                                                                  (insn 11 10 12 2 (set (reg:SI 103)                                                                                                                                                                                                                                                   (mult:SI (subreg:SI (reg:HI 101) 0)                                                                                                                                                                                                                                              (subreg:SI (reg:HI 102) 0))) "prom.c":4:16 -1                                                                                                                                                                                                                         (nil))

Out of expand. The paradoxical subreg isn't generated at all out of expand
unless it's needed. It does keep the original params around as unused:

(insn 2 7 4 2 (set (reg:QI 97)                                                                                                                                                                                                                                                       (reg:QI 0 x0 [ xr ])) "prom.c":3:37 -1                                                                                                                                                                                                                                    (nil))                                                                                                                                                                                                                                                                  (insn 4 2 3 2 (set (reg:QI 99)                                                                                                                                                                                                                                                       (reg:QI 1 x1 [ xc ])) "prom.c":3:37 -1                                                                                                                                                                                                                                    (nil))  

And the paradoxical subreg is moved into the first operation requiring it:

(insn 11 10 12 2 (set (reg:SI 103)                                                                                                                                                                                                                                                   (mult:SI (subreg:SI (reg:HI 101) 0)                                                                                                                                                                                                                                              (subreg:SI (reg:HI 102) 0))) "prom.c":4:16 -1                                                                                                                                                                                                                         (nil))

In any case, I'm still not totally sure what the objection here is.  Afaik,
compares need to be treated specially because in GIMPLE they already
are.  Afaik, C integer promotion rules state that in the comparison 0 should
have been promoted to an integer constant of rank int and so the comparison itself
should have been done as integer. i.e. extended.  And most of our patterns
are based around this.

Gimple however doesn't do this, the comparison is done in the rank of the
variable and there is no explicit conversion.  This happened to be fixed up
before during the forced promotion.  So to me the heuristic doesn't seem
to be that crazy..

But I'll respin the patch without the hook and see where things land.

Thanks,
Tamar

> >
> > I'm not sure it does, as the any-extended value must remain live. i.e.
> > above you can't get rid of w22, you can only choose between having it
> > be zero of any extended.  But I am not sure how you would do that after
> expand.
> 
> These per-operation extends are emitted during expand.  The question is
> whether we do them into fresh registers:
> 
>    (set (reg:SI Rtmp) (zero_extend:SI (subreg:QI (reg:SI R))))
> 
> which leaves both R and Rtmp live at the same time, or whether we do them
> in-situ:
> 
>    (set (reg:SI R) (zero_extend:SI (subreg:QI (reg:SI R))))
> 
> Expand should know that the latter is valid, given the DECL_RTL.
> 
> Thanks,
> Richard