public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug middle-end/62263] New: Good codegen for bitwise rotate requires code that is technically undefined behavior
@ 2014-08-26 0:45 oneill+gccbugs at cs dot hmc.edu
2014-08-26 0:50 ` [Bug middle-end/62263] " oneill+gccbugs at cs dot hmc.edu
` (5 more replies)
0 siblings, 6 replies; 7+ messages in thread
From: oneill+gccbugs at cs dot hmc.edu @ 2014-08-26 0:45 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62263
Bug ID: 62263
Summary: Good codegen for bitwise rotate requires code that is
technically undefined behavior
Product: gcc
Version: 4.9.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: middle-end
Assignee: unassigned at gcc dot gnu.org
Reporter: oneill+gccbugs at cs dot hmc.edu
LLVM lacks an intrinsic for performing bitwise rotation, relying instead on
spotting the classic C idioms for specifying rotation using two shifts.
Unfortunately, when the rotation is defined by variable, its ability to spot
rotation code is poor.
Code that supports a variable rotation also needs to handle rotation-by-zero,
which the underlying instruction has no problem with, but when translated into
the classic C idiom, results in an undefined shift (because shifting a 32-bit
integer by 32 bits isn't allowed).
In the following code, only rotate32_undefined1, rotate32_undefined2 and
_rotl32_doubleand1 compiles to a simple rotate instruction. rotl32_zerocheck
also compiles to a rotate, but it contains a redundant test for zero -- a test
that is necessary in the C code but not necessary for the rotate.
Somewhat annoyingly, Clang 3.5 also has poor rotation detection, and only
detects it for rotl_doubleand2 and rotl_doubleand3, as well as
rotl32_undefined2. It is filed as http://llvm.org/bugs/show_bug.cgi?id=20750
Thus GCC and Clang differ as to which code they want for a rotate, and neither
is good at recognizing variations of the rotate idiom.
--- C code ---
unsigned int rotl32_undefined1(unsigned int v, unsigned char r)
{
r = r & 31;
return (v << r) | (v >> (32 - r));
}
unsigned int rotl32_undefined2(unsigned int v, unsigned char r)
{
return (v << (r & 31)) | (v >> (32 - (r & 31)));
}
unsigned int rotl32_zerocheck(unsigned int v, unsigned char r)
{
r = r & 31;
return r ? (v << r) | (v >> (32 - r)) : v;
}
unsigned int rotl32_doubleand1(unsigned int v, unsigned char r)
{
r = r & 31;
return (v << r) | (v >> ((32 - r) & 31));
}
unsigned int rotl32_doubleand2(unsigned int v, unsigned char r)
{
return (v << (r & 31)) | (v >> ((32 - (r & 31)) & 31));
}
unsigned int rotl32_doubleand3(unsigned int v, unsigned char r)
{
return (v << (r & 31)) | (v >> ((32 - r) & 31));
}
--- Assembly output, gcc 4.9.0 -O3 -fomit-frame-pointer ---
_rotl32_undefined1:
LFB0:
movl %esi, %ecx
movl %edi, %eax
andl $31, %ecx
roll %cl, %eax
ret
LFE0:
.section __TEXT,__text_cold,regular,pure_instructions
LCOLDE0:
.text
LHOTE0:
.section __TEXT,__text_cold,regular,pure_instructions
LCOLDB1:
.text
LHOTB1:
.align 4,0x90
.globl _rotl32_undefined2
_rotl32_undefined2:
LFB1:
movl %esi, %ecx
movl %edi, %eax
andl $31, %ecx
roll %cl, %eax
ret
LFE1:
.section __TEXT,__text_cold,regular,pure_instructions
LCOLDE1:
.text
LHOTE1:
.section __TEXT,__text_cold,regular,pure_instructions
LCOLDB2:
.text
LHOTB2:
.align 4,0x90
.globl _rotl32_zerocheck
_rotl32_zerocheck:
LFB2:
movl %esi, %ecx
movl %edi, %eax
andl $31, %ecx
roll %cl, %eax
testb %cl, %cl
cmove %edi, %eax
ret
LFE2:
.section __TEXT,__text_cold,regular,pure_instructions
LCOLDE2:
.text
LHOTE2:
.section __TEXT,__text_cold,regular,pure_instructions
LCOLDB3:
.text
LHOTB3:
.align 4,0x90
.globl _rotl32_doubleand1
_rotl32_doubleand1:
LFB3:
movl %esi, %ecx
movl %edi, %eax
andl $31, %ecx
roll %cl, %eax
ret
LFE3:
.section __TEXT,__text_cold,regular,pure_instructions
LCOLDE3:
.text
LHOTE3:
.section __TEXT,__text_cold,regular,pure_instructions
LCOLDB4:
.text
LHOTB4:
.align 4,0x90
.globl _rotl32_doubleand2
_rotl32_doubleand2:
LFB4:
movl %esi, %ecx
movl %edi, %eax
negl %ecx
shrl %cl, %eax
movl %esi, %ecx
andl $31, %ecx
sall %cl, %edi
orl %edi, %eax
ret
^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug middle-end/62263] Good codegen for bitwise rotate requires code that is technically undefined behavior
2014-08-26 0:45 [Bug middle-end/62263] New: Good codegen for bitwise rotate requires code that is technically undefined behavior oneill+gccbugs at cs dot hmc.edu
@ 2014-08-26 0:50 ` oneill+gccbugs at cs dot hmc.edu
2014-08-26 11:18 ` rguenth at gcc dot gnu.org
` (4 subsequent siblings)
5 siblings, 0 replies; 7+ messages in thread
From: oneill+gccbugs at cs dot hmc.edu @ 2014-08-26 0:50 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62263
--- Comment #1 from M.E. O'Neill <oneill+gccbugs at cs dot hmc.edu> ---
Possibly this should have been filed as a tree-level bug? Also, see
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=17886 which mostly is about issues
with wider types, but may also cover this bug.
^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug middle-end/62263] Good codegen for bitwise rotate requires code that is technically undefined behavior
2014-08-26 0:45 [Bug middle-end/62263] New: Good codegen for bitwise rotate requires code that is technically undefined behavior oneill+gccbugs at cs dot hmc.edu
2014-08-26 0:50 ` [Bug middle-end/62263] " oneill+gccbugs at cs dot hmc.edu
@ 2014-08-26 11:18 ` rguenth at gcc dot gnu.org
2014-08-26 11:38 ` mpolacek at gcc dot gnu.org
` (3 subsequent siblings)
5 siblings, 0 replies; 7+ messages in thread
From: rguenth at gcc dot gnu.org @ 2014-08-26 11:18 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62263
Richard Biener <rguenth at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |jakub at gcc dot gnu.org
--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
I believe we handle at least some "correct" forms now - Jakub?
^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug middle-end/62263] Good codegen for bitwise rotate requires code that is technically undefined behavior
2014-08-26 0:45 [Bug middle-end/62263] New: Good codegen for bitwise rotate requires code that is technically undefined behavior oneill+gccbugs at cs dot hmc.edu
2014-08-26 0:50 ` [Bug middle-end/62263] " oneill+gccbugs at cs dot hmc.edu
2014-08-26 11:18 ` rguenth at gcc dot gnu.org
@ 2014-08-26 11:38 ` mpolacek at gcc dot gnu.org
2014-08-26 12:15 ` glisse at gcc dot gnu.org
` (2 subsequent siblings)
5 siblings, 0 replies; 7+ messages in thread
From: mpolacek at gcc dot gnu.org @ 2014-08-26 11:38 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62263
Marek Polacek <mpolacek at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |mpolacek at gcc dot gnu.org
--- Comment #3 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
We handle at least
(x << n) | (x >> ((-n) & 31))
(N can be 0 here) since PR57157.
^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug middle-end/62263] Good codegen for bitwise rotate requires code that is technically undefined behavior
2014-08-26 0:45 [Bug middle-end/62263] New: Good codegen for bitwise rotate requires code that is technically undefined behavior oneill+gccbugs at cs dot hmc.edu
` (2 preceding siblings ...)
2014-08-26 11:38 ` mpolacek at gcc dot gnu.org
@ 2014-08-26 12:15 ` glisse at gcc dot gnu.org
2014-08-26 12:31 ` glisse at gcc dot gnu.org
2014-08-26 17:12 ` oneill+gccbugs at cs dot hmc.edu
5 siblings, 0 replies; 7+ messages in thread
From: glisse at gcc dot gnu.org @ 2014-08-26 12:15 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62263
--- Comment #4 from Marc Glisse <glisse at gcc dot gnu.org> ---
Problem here is conversions that happen in places where we don't handle them. A
couple more patterns should do it (it could be a good test for the optional
convert feature in the match branch).
For the zerocheck version, it would work if r was an int, but here we get 2
insns in the branch (convert+rotate) which is quite a bit harder to handle than
a single rotate insn.
^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug middle-end/62263] Good codegen for bitwise rotate requires code that is technically undefined behavior
2014-08-26 0:45 [Bug middle-end/62263] New: Good codegen for bitwise rotate requires code that is technically undefined behavior oneill+gccbugs at cs dot hmc.edu
` (3 preceding siblings ...)
2014-08-26 12:15 ` glisse at gcc dot gnu.org
@ 2014-08-26 12:31 ` glisse at gcc dot gnu.org
2014-08-26 17:12 ` oneill+gccbugs at cs dot hmc.edu
5 siblings, 0 replies; 7+ messages in thread
From: glisse at gcc dot gnu.org @ 2014-08-26 12:31 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62263
--- Comment #5 from Marc Glisse <glisse at gcc dot gnu.org> ---
Also, I would have expected the pattern *<rotate_insn><mode>3_mask to avoid
generating 'andl' before 'roll'.
^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug middle-end/62263] Good codegen for bitwise rotate requires code that is technically undefined behavior
2014-08-26 0:45 [Bug middle-end/62263] New: Good codegen for bitwise rotate requires code that is technically undefined behavior oneill+gccbugs at cs dot hmc.edu
` (4 preceding siblings ...)
2014-08-26 12:31 ` glisse at gcc dot gnu.org
@ 2014-08-26 17:12 ` oneill+gccbugs at cs dot hmc.edu
5 siblings, 0 replies; 7+ messages in thread
From: oneill+gccbugs at cs dot hmc.edu @ 2014-08-26 17:12 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62263
--- Comment #6 from M.E. O'Neill <oneill+gccbugs at cs dot hmc.edu> ---
(In reply to Marek Polacek from comment #3)
> We handle at least
> (x << n) | (x >> ((-n) & 31))
> (N can be 0 here) since PR57157.
Although this code does work with LLVM, testing with GCC 4.9.0, and this
implementation
unsigned int rotl32_doubleand4(unsigned int v, unsigned char r)
{
return (v << (r & 31)) | (v >> ((-r) & 31));
}
(or variations with r being a char or int) produces code like this:
_rotl32_doubleand4:
LFB6:
movl %esi, %ecx
movl %edi, %eax
negl %ecx
shrl %cl, %eax
movl %esi, %ecx
sall %cl, %edi
orl %edi, %eax
ret
... so it failed to spot the idiom entirely.
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2014-08-26 17:12 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2014-08-26 0:45 [Bug middle-end/62263] New: Good codegen for bitwise rotate requires code that is technically undefined behavior oneill+gccbugs at cs dot hmc.edu
2014-08-26 0:50 ` [Bug middle-end/62263] " oneill+gccbugs at cs dot hmc.edu
2014-08-26 11:18 ` rguenth at gcc dot gnu.org
2014-08-26 11:38 ` mpolacek at gcc dot gnu.org
2014-08-26 12:15 ` glisse at gcc dot gnu.org
2014-08-26 12:31 ` glisse at gcc dot gnu.org
2014-08-26 17:12 ` oneill+gccbugs at cs dot hmc.edu
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).