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