[Bug middle-end/62263] New: Good codegen for bitwise rotate requires code that is technically undefined behavior

[Bug middle-end/62263] New: Good codegen for bitwise rotate requires code that is technically undefined behavior

[oneill+gccbugs at cs dot hmc.edu]

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

[Bug middle-end/62263] Good codegen for bitwise rotate requires code that is technically undefined behavior

[oneill+gccbugs at cs dot hmc.edu]

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.

[Bug middle-end/62263] Good codegen for bitwise rotate requires code that is technically undefined behavior

[rguenth at gcc dot gnu.org]

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?

[Bug middle-end/62263] Good codegen for bitwise rotate requires code that is technically undefined behavior

[mpolacek at gcc dot gnu.org]

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.

[Bug middle-end/62263] Good codegen for bitwise rotate requires code that is technically undefined behavior

[glisse at gcc dot gnu.org]

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.

[Bug middle-end/62263] Good codegen for bitwise rotate requires code that is technically undefined behavior

[glisse at gcc dot gnu.org]

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'.

[Bug middle-end/62263] Good codegen for bitwise rotate requires code that is technically undefined behavior

[oneill+gccbugs at cs dot hmc.edu]

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.