public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
From: "pinskia at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug middle-end/109907] Missed optimization for bit extraction (uses shift instead of single bit-test)
Date: Fri, 26 May 2023 23:11:13 +0000 [thread overview]
Message-ID: <bug-109907-4-pajU3y2oUd@http.gcc.gnu.org/bugzilla/> (raw)
In-Reply-To: <bug-109907-4@http.gcc.gnu.org/bugzilla/>
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109907
--- Comment #24 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Georg-Johann Lay from comment #23)
> Thank you so much for looking into this.
>
> For the test case from comment #21 though, the problem is somewhere in tree
> optimizations.
>
> > unsigned char lfsr32_mpp_ge0 (unsigned long number)
> > {
> > unsigned char b = 0;
> > if (number >= 0) b--;
> > if (number & (1UL << 29)) b++;
> > if (number & (1UL << 13)) b++;
> >
> > return b;
> > }
>
> The -fdump-tree-optimized dump reads:
>
> ;; Function lfsr32_mpp_ge0 (lfsr32_mpp_ge0, funcdef_no=0, decl_uid=1880,
> cgraph_uid=1, symbol_order=0)
>
> unsigned char lfsr32_mpp_ge0 (long unsigned int number)
> {
> unsigned char b;
> long unsigned int _1;
> long unsigned int _2;
> _Bool _3;
> unsigned char _8;
> _Bool _9;
> unsigned char _10;
> unsigned char _11;
>
> <bb 2> [local count: 1073741824]:
> _1 = number_5(D) & 536870912;
> _2 = number_5(D) & 8192;
> if (_2 != 0)
> goto <bb 4>; [50.00%]
> else
> goto <bb 3>; [50.00%]
>
> <bb 3> [local count: 536870912]:
> _9 = _1 == 0;
> _10 = (unsigned char) _9;
> _11 = -_10;
> goto <bb 5>; [100.00%]
>
> <bb 4> [local count: 536870913]:
> _3 = _1 != 0;
> _8 = (unsigned char) _3;
>
> <bb 5> [local count: 1073741824]:
> # b_4 = PHI <_11(3), _8(4)>
> return b_4;
> }
Oh yes this is where my
https://gcc.gnu.org/pipermail/gcc-patches/2023-May/619068.html patch actually
solves.
It should be able to detect that _1 has a non-zero bits of just one bit set and
expand using single_bit_test for _3.
For an example we get:
;; Generating RTL for gimple basic block 3
;; _11 = -_10;
(insn 10 9 11 (set (reg:QI 51)
(zero_extract:QI (subreg:QI (reg:SI 43 [ _1 ]) 3)
(const_int 1 [0x1])
(const_int 5 [0x5]))) "t21.c":5:6 -1
(nil))
(insn 11 10 12 (set (reg:QI 53)
(const_int 1 [0x1])) "t21.c":5:6 -1
(nil))
(insn 12 11 13 (set (reg:QI 52)
(xor:QI (reg:QI 51)
(reg:QI 53))) "t21.c":5:6 -1
(nil))
(insn 13 12 0 (set (reg/v:QI 48 [ <retval> ])
(neg:QI (reg:QI 52))) "t21.c":5:6 -1
(nil))
Which is exactly what you want right?
Overall we get:
```
lfsr32_mpp_ge0:
push r16
push r17
/* prologue: function */
/* frame size = 0 */
/* stack size = 2 */
.L__stack_usage = 2
mov r16,r22
mov r17,r23
mov r18,r24
mov r19,r25
mov r27,r19
mov r26,r18
mov r25,r17
mov r24,r16
clr r24
clr r25
clr r26
andi r27,32
bst r27,5
clr r24
bld r24,0
sbrs r17,5
subi r24,lo8(-(-1))
.L1:
/* epilogue start */
pop r17
pop r16
ret
```
Which is much better than it was before (still could be improved more though
but that is for a different time).
To finish this patch up, I am supposed to do some cost modelling and such which
I might get to this weekend.
Even for aarch64 we do slightly better:
```
lfsr32_mpp_ge0:
and x1, x0, 536870912
tbnz x0, 13, .L2
cmp x1, 0
csetm w0, eq
and w0, w0, 255
ret
.L2:
cmp x1, 0
cset w0, ne
ret
```
```
lfsr32_mpp_ge0:
and x1, x0, 536870912
tbnz x0, 13, .L2
ubfx x0, x1, 29, 1
eor w0, w0, 1
neg w0, w0
and w0, w0, 255
ret
.L2:
ubfx x0, x1, 29, 1
and w0, w0, 255
ret
```
Though if there would be a way to remove the first and's, that would be best
(and the last and, the last one is still there because of fuzziness with
combine trying to do ne there still).
Note even though it does increase in size, the cost of cset on some processors
is 2 cycles rather than 1.
next prev parent reply other threads:[~2023-05-26 23:11 UTC|newest]
Thread overview: 32+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-05-19 10:10 [Bug middle-end/109907] New: [avr] " gjl at gcc dot gnu.org
2023-05-19 14:14 ` [Bug middle-end/109907] " pinskia at gcc dot gnu.org
2023-05-19 15:42 ` [Bug middle-end/109907] " pinskia at gcc dot gnu.org
2023-05-19 15:45 ` pinskia at gcc dot gnu.org
2023-05-19 20:03 ` pinskia at gcc dot gnu.org
2023-05-19 20:12 ` pinskia at gcc dot gnu.org
2023-05-19 20:41 ` gjl at gcc dot gnu.org
2023-05-19 20:55 ` pinskia at gcc dot gnu.org
2023-05-19 20:59 ` gjl at gcc dot gnu.org
2023-05-20 0:46 ` pinskia at gcc dot gnu.org
2023-05-20 5:09 ` pinskia at gcc dot gnu.org
2023-05-20 7:36 ` gjl at gcc dot gnu.org
2023-05-20 7:50 ` gjl at gcc dot gnu.org
2023-05-20 22:23 ` pinskia at gcc dot gnu.org
2023-05-20 22:40 ` pinskia at gcc dot gnu.org
2023-05-21 5:15 ` pinskia at gcc dot gnu.org
2023-05-21 5:36 ` pinskia at gcc dot gnu.org
2023-05-21 9:09 ` gjl at gcc dot gnu.org
2023-05-21 9:55 ` gjl at gcc dot gnu.org
2023-05-23 9:58 ` gjl at gcc dot gnu.org
2023-05-26 8:49 ` gjl at gcc dot gnu.org
2023-05-26 11:14 ` gjl at gcc dot gnu.org
2023-05-26 15:21 ` pinskia at gcc dot gnu.org
2023-05-26 16:08 ` gjl at gcc dot gnu.org
2023-05-26 23:11 ` pinskia at gcc dot gnu.org [this message]
2023-05-26 23:34 ` pinskia at gcc dot gnu.org
2023-05-26 23:49 ` pinskia at gcc dot gnu.org
2023-05-27 0:36 ` pinskia at gcc dot gnu.org
2023-05-27 4:02 ` pinskia at gcc dot gnu.org
2023-05-27 20:09 ` pinskia at gcc dot gnu.org
2023-06-11 9:22 ` cvs-commit at gcc dot gnu.org
2023-06-11 9:26 ` gjl at gcc dot gnu.org
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=bug-109907-4-pajU3y2oUd@http.gcc.gnu.org/bugzilla/ \
--to=gcc-bugzilla@gcc.gnu.org \
--cc=gcc-bugs@gcc.gnu.org \
/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).