[LLVMbugs] [Bug 23590] New: Division/modulo by constant can be optimized to take bounds of the dividend into account

[bugzilla-daemon at llvm.org]

https://llvm.org/bugs/show_bug.cgi?id=23590

            Bug ID: 23590
           Summary: Division/modulo by constant can be optimized to take
                    bounds of the dividend into account
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: All
            Status: NEW
          Severity: normal
          Priority: P
         Component: Scalar Optimizations
          Assignee: unassignedbugs at nondot.org
          Reporter: ed at 80386.nl
                CC: llvmbugs at cs.uiuc.edu
    Classification: Unclassified

Consider the this piece of C code, for which clang r236483 with -O3 generates
the following machine code:

#include <stdint.h>

uint64_t func1(uint64_t a) {
  return (a % 12345) / 7;
}

0000000000000000 <func1>:
   0:   55                      push   %rbp
   1:   48 89 e5                mov    %rsp,%rbp
   4:   48 89 f9                mov    %rdi,%rcx
   7:   48 ba 1f c2 e7 18 c7    mov    $0x54f077c718e7c21f,%rdx
   e:   77 f0 54 
  11:   48 89 c8                mov    %rcx,%rax
  14:   48 f7 e2                mul    %rdx
  17:   48 c1 ea 0c             shr    $0xc,%rdx
  1b:   48 69 c2 39 30 00 00    imul   $0x3039,%rdx,%rax
  22:   48 29 c1                sub    %rax,%rcx
  25:   48 ba 93 24 49 92 24    mov    $0x2492492492492493,%rdx
  2c:   49 92 24 
  2f:   48 89 c8                mov    %rcx,%rax
  32:   48 f7 e2                mul    %rdx
  35:   48 29 d1                sub    %rdx,%rcx
  38:   48 d1 e9                shr    %rcx
  3b:   48 8d 04 11             lea    (%rcx,%rdx,1),%rax
  3f:   48 c1 e8 02             shr    $0x2,%rax
  43:   5d                      pop    %rbp
  44:   c3                      retq   

This function can be optimized, as we know that 'a % 12345' never has a value
exceeding 12344. It will thus fit in a 16-bit variable. If we add an additional
cast, Clang generates something smarter:

uint64_t func2(uint64_t a) {
  return (uint16_t)(a % 12345) / 7;
}

0000000000000000 <func2>:
   0:   55                      push   %rbp
   1:   48 89 e5                mov    %rsp,%rbp
   4:   48 89 f9                mov    %rdi,%rcx
   7:   48 ba 1f c2 e7 18 c7    mov    $0x54f077c718e7c21f,%rdx
   e:   77 f0 54 
  11:   48 89 c8                mov    %rcx,%rax
  14:   48 f7 e2                mul    %rdx
  17:   48 c1 ea 0c             shr    $0xc,%rdx
  1b:   48 69 c2 39 30 00 00    imul   $0x3039,%rdx,%rax
  22:   48 29 c1                sub    %rax,%rcx
  25:   48 69 c1 25 49 92 24    imul   $0x24924925,%rcx,%rax
  2c:   48 c1 e8 20             shr    $0x20,%rax
  30:   29 c1                   sub    %eax,%ecx
  32:   d1 e9                   shr    %ecx
  34:   01 c1                   add    %eax,%ecx
  36:   c1 e9 02                shr    $0x2,%ecx
  39:   48 89 c8                mov    %rcx,%rax
  3c:   5d                      pop    %rbp
  3d:   c3                      retq   

In my opinion Clang should be smart enough to derive these facts without
requiring me to add additional casts.

-- 
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/20150520/a4ea30f0/attachment.html>