[LLVMbugs] [Bug 20750] New: Good codegen for bitwise rotate requires code that is technically undefined behavior

[bugzilla-daemon at llvm.org]

http://llvm.org/bugs/show_bug.cgi?id=20750

            Bug ID: 20750
           Summary: Good codegen for bitwise rotate requires code that is
                    technically undefined behavior
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: All
            Status: NEW
          Severity: normal
          Priority: P
         Component: Common Code Generator Code
          Assignee: unassignedbugs at nondot.org
          Reporter: oneill+llvmbugs at cs.hmc.edu
                CC: llvmbugs at cs.uiuc.edu
    Classification: Unclassified

Created attachment 12935
  --> http://llvm.org/bugs/attachment.cgi?id=12935&action=edit
Five implementations of rotate32.

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 enclosed code, only rotate32_undefined2 compiles to a simple rotate
instruction.   rotate32_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.

Swapping a zero test for an and operation causes codegen to miss the idiom.

(Compiled with -O3 -fomit-frame-pointer to reduce clutter.)

_rotate32_undefined1:                   ## @rotate32_undefined1
    .cfi_startproc
## BB#0:                                ## %entry
    movb    %sil, %al
    andb    $31, %al
    movzbl    %al, %eax
    movl    %edi, %edx
    movb    %sil, %cl
    shll    %cl, %edx
    movl    $32, %ecx
    subl    %eax, %ecx
                                        ## kill: CL<def> CL<kill> ECX<kill>
    shrl    %cl, %edi
    orl    %edx, %edi
    movl    %edi, %eax
    retq
    .cfi_endproc

    .globl    _rotate32_undefined2
    .align    4, 0x90
_rotate32_undefined2:                   ## @rotate32_undefined2
    .cfi_startproc
## BB#0:                                ## %entry
    movb    %sil, %cl
    roll    %cl, %edi
    movl    %edi, %eax
    retq
    .cfi_endproc

    .globl    _rotate32_zerocheck
    .align    4, 0x90
_rotate32_zerocheck:                    ## @rotate32_zerocheck
    .cfi_startproc
## BB#0:                                ## %entry
    testb    $31, %sil
    je    LBB2_2
## BB#1:                                ## %cond.true
    andl    $31, %esi
    movb    %sil, %cl
    roll    %cl, %edi
LBB2_2:                                 ## %cond.end
    movl    %edi, %eax
    retq
    .cfi_endproc

    .globl    _rotate32_doubleand1
    .align    4, 0x90
_rotate32_doubleand1:                   ## @rotate32_doubleand1
    .cfi_startproc
## BB#0:                                ## %entry
    testb    $31, %sil
    je    LBB3_2
## BB#1:                                ## %cond.true
    andl    $31, %esi
    movl    %edi, %eax
    movb    %sil, %cl
    shll    %cl, %eax
    movl    $32, %ecx
    subl    %esi, %ecx
                                        ## kill: CL<def> CL<kill> ECX<kill>
    shrl    %cl, %edi
    andl    $31, %edi
    orl    %eax, %edi
LBB3_2:                                 ## %cond.end
    movl    %edi, %eax
    retq
    .cfi_endproc

    .globl    _rotate32_doubleand2
    .align    4, 0x90
_rotate32_doubleand2:                   ## @rotate32_doubleand2
    .cfi_startproc
## BB#0:                                ## %entry
    testb    %sil, %sil
    je    LBB4_2
## BB#1:                                ## %cond.true
    movzbl    %sil, %ecx
    andl    $31, %ecx
    movl    %edi, %edx
    shll    %cl, %edx
    movl    $32, %eax
    subl    %ecx, %eax
    movb    %al, %cl
    shrl    %cl, %edi
    andl    $31, %edi
    orl    %edx, %edi
LBB4_2:                                 ## %cond.end
    movl    %edi, %eax
    retq
    .cfi_endproc

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20140825/7608dce9/attachment.html>