[LLVMbugs] [Bug 14148] New: Inefficient code generated for k mod (2^n + 1)

[bugzilla-daemon at llvm.org]

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

             Bug #: 14148
           Summary: Inefficient code generated for k mod (2^n + 1)
           Product: libraries
           Version: trunk
          Platform: PC
        OS/Version: Linux
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Scalar Optimizations
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: richard-llvm at metafoo.co.uk
                CC: llvmbugs at cs.uiuc.edu
    Classification: Unclassified


For this:

  extern unsigned int a;
  int b = a % 65537;

LLVM generates this code, performing a divide-and-subtract:

        movl    $4294901761, %ecx       # imm = 0xFFFF0001
        movl    a(%rip), %eax
        imulq   %rax, %rcx
        shrq    $48, %rcx
        imull   $65537, %ecx, %ecx      # imm = 0x10001
        subl    %ecx, %eax
        movl    %eax, b(%rip)
        ret

g++ generates similar code, but manages to remove both muls. But notice that:

  a % 65537 == ((a & 65535) + (a >> 16) * 65536) % 65537
            == ((a & 65535) + (a >> 16) * -1) % 65537
            == ((a & 65535) - (a >> 16)) % 65537

... where the parenthetical is in the range [-65535, 65535], so we can express
the % as a cmov.

This came up in some code I was experimenting with for use in ubsan.

-- 
Configure bugmail: http://llvm.org/bugs/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.