[LLVMbugs] [Bug 17904] New: requesting optimization of safe rotate functions

bugzilla-daemon at llvm.org bugzilla-daemon at llvm.org
Tue Nov 12 20:19:06 PST 2013


            Bug ID: 17904
           Summary: requesting optimization of safe rotate functions
           Product: new-bugs
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: new bugs
          Assignee: unassignedbugs at nondot.org
          Reporter: regehr at cs.utah.edu
                CC: llvmbugs at cs.uiuc.edu
    Classification: Unclassified

This is the obvious rotate idiom in C (this one is from Nettle):

#define ROTL32(n,x) (((x)<<(n)) | ((x)>>(32-(n))))

LLVM does an admirable job of recognizing the code and turning it into a rotate
instruction, when this is available.

The problem is that this code executes undefined behavior when n==0 or n==32.

Most crypto libraries are careful not to rotate by 32, but out of 10 libraries
that I examined, 5 execute undefined behavior when rotating by zero.

We can make the obvious modification to protect against undefined rotate by 0:

#define ROTL32(n,x) ((n)==0?(x):(((x)<<(n)) | ((x)>>(32-(n)))))

Notice that this can be turned into exactly the same object code as the earlier
macro since the rotate-by-0 case is already handled by the rotate instruction. 
However, this isn't what we get out of the compiler:

    testl    %esi, %esi
    je    .LBB2_2
    movb    %sil, %cl
    roll    %cl, %edi
    movl    %edi, %eax

I'm in the process or trying to convince crypto library maintainers to fix
their rotate functions and macros, and this will be easier if the fix doesn't
have a performance penalty.

So would it be possible for you folks to teach the compiler to emit the better
code for the safe rotate idiom?

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/20131113/7e53c20e/attachment.html>

More information about the llvm-bugs mailing list