From: Richard Biener <richard.guenther@gmail.com>
To: Roger Sayle <roger@nextmovesoftware.com>
Cc: gcc-patches@gcc.gnu.org
Subject: Re: [middle-end PATCH] Prefer PLUS over IOR in RTL expansion of multi-word shifts/rotates.
Date: Fri, 19 Jan 2024 14:49:53 +0100 [thread overview]
Message-ID: <CAFiYyc0+FbBfVohics0z9UnLTURwNJj7VEFbwTXBQ62a_ZWjBw@mail.gmail.com> (raw)
In-Reply-To: <002f01da4adb$16799150$436cb3f0$@nextmovesoftware.com>
On Fri, Jan 19, 2024 at 2:26 PM Roger Sayle <roger@nextmovesoftware.com> wrote:
>
>
> Hi Richard,
>
> Thanks for the speedy review. I completely agree this patch
> can wait for stage1, but it's related to some recent work Andrew
> Pinski has been doing in match.pd, so I thought I'd share it.
>
> Hypothetically, recognizing (x<<4)+(x>>60) as a rotation at the
> tree-level might lead to a code quality regression, if RTL
> expansion doesn't know to lower it back to use PLUS on
> those targets with lea but without rotate.
>
> > From: Richard Biener <richard.guenther@gmail.com>
> > Sent: 19 January 2024 11:04
> > On Thu, Jan 18, 2024 at 8:55 PM Roger Sayle <roger@nextmovesoftware.com>
> > wrote:
> > >
> > > This patch tweaks RTL expansion of multi-word shifts and rotates to
> > > use PLUS rather than IOR for disjunctive operations. During expansion
> > > of these operations, the middle-end creates RTL like (X<<C1) | (Y>>C2)
> > > where the constants C1 and C2 guarantee that bits don't overlap.
> > > Hence the IOR can be performed by any any_or_plus operation, such as
> > > IOR, XOR or PLUS; for word-size operations where carry chains aren't
> > > an issue these should all be equally fast (single-cycle) instructions.
> > > The benefit of this change is that targets with shift-and-add insns,
> > > like x86's lea, can benefit from the LSHIFT-ADD form.
> > >
> > > An example of a backend that benefits is ARC, which is demonstrated by
> > > these two simple functions:
> > >
> > > unsigned long long foo(unsigned long long x) { return x<<2; }
> > >
> > > which with -O2 is currently compiled to:
> > >
> > > foo: lsr r2,r0,30
> > > asl_s r1,r1,2
> > > asl_s r0,r0,2
> > > j_s.d [blink]
> > > or_s r1,r1,r2
> > >
> > > with this patch becomes:
> > >
> > > foo: lsr r2,r0,30
> > > add2 r1,r2,r1
> > > j_s.d [blink]
> > > asl_s r0,r0,2
> > >
> > > unsigned long long bar(unsigned long long x) { return (x<<2)|(x>>62);
> > > }
> > >
> > > which with -O2 is currently compiled to 6 insns + return:
> > >
> > > bar: lsr r12,r0,30
> > > asl_s r3,r1,2
> > > asl_s r0,r0,2
> > > lsr_s r1,r1,30
> > > or_s r0,r0,r1
> > > j_s.d [blink]
> > > or r1,r12,r3
> > >
> > > with this patch becomes 4 insns + return:
> > >
> > > bar: lsr r3,r1,30
> > > lsr r2,r0,30
> > > add2 r1,r2,r1
> > > j_s.d [blink]
> > > add2 r0,r3,r0
> > >
> > >
> > > This patch has been tested on x86_64-pc-linux-gnu with make bootstrap
> > > and make -k check, both with and without --target_board=unix{-m32}
> > > with no new failures. Ok for mainline?
> >
> > For expand_shift_1 you add
> >
> > + where C is the bitsize of A. If N cannot be zero,
> > + use PLUS instead of IOR.
> >
> > but I don't see a check ensuring this other than mabe CONST_INT_P (op1)
> > suggesting that we enver end up with const0_rtx here. OTOH why is N zero a
> > problem and why is it not in the optabs.cc case where I don't see any such check
> > (at least not obvious)?
>
> Excellent question. A common mistake in writing a rotate function in C
> or C++ is to write something like (x>>n)|(x<<(64-n)) or (x<<n)|(x>>(64-n))
> which invokes undefined behavior when n == 0. It's OK to recognize these
> as rotates (relying on the undefined behavior), but correct/portable code
> (and RTL) needs the correct idiom(x>>n)|(x<<((-n)&63), which never invokes
> undefined behaviour. One interesting property of this idiom, is that shift
> by zero is then calculated as (x>>0)|(x<<0) which is x|x. This should then
> reveal the problem, for all non-zero values the IOR can be replaced by PLUS,
> but for zero shifts, X|X isn't the same as X+X or X^X.
>
> This only applies for single word rotations, and not multi-word shifts
> nor multi-word rotates, which explains why this test is only in one place.
>
> In theory, we could use ranger to check whether a rotate by a variable
> amount can ever be by zero bits, but the simplification used here is to
> continue using IOR for variable shifts, and PLUS for fixed/known shift
> values. The last remaining insight is that we only need to check for
> CONST_INT_P, as rotations/shifts by const0_rtx are handled earlier in
> this function (and eliminated by the tree-optimizers), i.e. rotation by
> a known constant is implicitly a rotation by a known non-zero constant.
Ah, I see. It wasn't obvious the expmed.cc case was for rotations only.
The patch is OK as-is for stage1 (which also gives others plenty of time
to comment).
I wonder if you can add a testcase though?
Thanks,
Richard.
> This is a little clearer if you read/cite more of the comment that was
> changed. Fortunately, this case is also well covered by the testsuite.
> I'd be happy to change the code to read:
>
> (CONST_INT_P (op1) && op1 != const0_rtx)
> ? add_optab
> : ior_optab
>
> But the test "if (op1 == const0_rtx)" already appears on line 2570
> of expmed.cc.
>
>
> > Since this doesn't seem to fix a regression it probably has to wait for
> > stage1 to re-open.
> >
> > Thanks,
> > Richard.
> >
> > > 2024-01-18 Roger Sayle <roger@nextmovesoftware.com>
> > >
> > > gcc/ChangeLog
> > > * expmed.cc (expand_shift_1): Use add_optab instead of ior_optab
> > > to generate PLUS instead or IOR when unioning disjoint bitfields.
> > > * optabs.cc (expand_subword_shift): Likewise.
> > > (expand_binop): Likewise for double-word rotate.
> > >
>
>
> Thanks again.
>
next prev parent reply other threads:[~2024-01-19 13:50 UTC|newest]
Thread overview: 12+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-01-18 19:54 Roger Sayle
2024-01-19 11:03 ` Richard Biener
2024-01-19 13:26 ` Roger Sayle
2024-01-19 13:49 ` Richard Biener [this message]
2024-01-19 16:05 ` Georg-Johann Lay
2024-01-19 16:50 ` Jeff Law
2024-01-20 9:31 ` Uros Bizjak
2024-01-22 7:45 ` Richard Biener
2024-01-22 15:51 ` Jeff Law
2024-01-24 15:49 ` Georg-Johann Lay
2024-01-25 9:20 ` Richard Biener
2024-06-09 1:48 ` Jeff Law
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAFiYyc0+FbBfVohics0z9UnLTURwNJj7VEFbwTXBQ62a_ZWjBw@mail.gmail.com \
--to=richard.guenther@gmail.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=roger@nextmovesoftware.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).