[Bug middle-end/43883] missed optimization of constant __int128_t modulus

[Bug middle-end/43883] missed optimization of constant __int128_t modulus

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=43883

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
4.7 produces:
        shr     rsi, 63
        mov     rax, rdi
        xor     edi, edi
        add     rax, rsi
        xor     r10d, r10d
        mov     r9, rax
        mov     rdx, r10
        and     r9d, 1
        mov     rax, r9
        sub     rax, rsi
        sbb     rdx, rdi
        ret

4.9:
        mov     rcx, rsi
        sar     rcx, 63
        xor     rdi, rcx
        mov     rdx, rcx
        mov     rax, rdi
        sub     rax, rcx
        and     eax, 1
        xor     rax, rcx
        sub     rax, rcx
        sbb     rdx, rcx
        ret

7.1.0-7.3.0, 8.1.0-8.2.0 decides not to inline it:

        sub     rsp, 8
        .cfi_def_cfa_offset 16
        mov     edx, 2
        xor     ecx, ecx
        call    __modti3
        add     rsp, 8
        .cfi_def_cfa_offset 8
        ret

And then we are back to the 4.9 code gen for 7.4, 8.3 and 9.x

10.x produces:

        mov     r10, rsi
        mov     r8, rdi
        sar     r10, 63
        xor     r8, r10
        mov     rdx, r10
        mov     rax, r8
        sub     rax, r10
        and     eax, 1
        xor     rax, r10
        sub     rax, r10
        sbb     rdx, r10
        ret

GCC 11 and trunk is back to the 4.9 code gen

[Bug middle-end/43883] missed optimization of constant __int128_t modulus

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=43883

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement

--- Comment #8 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Note LLVM produces:
        mov     rdx, rsi
        mov     rax, rdi
        mov     rcx, rsi
        shr     rcx, 63
        add     rcx, rdi
        adc     rsi, 0
        and     rcx, -2
        sub     rax, rcx
        sbb     rdx, rsi

[Bug middle-end/43883] New: missed optimization of constant __int128_t modulus

[svfuerst at gmail dot com]

The following function gets optimized at -O3 to:

long long tmod2(long long x)
{
        return x % 2;
}


mov    %rdi,%rdx                                                   
shr    $0x3f,%rdx                                                  
lea    (%rdi,%rdx,1),%rax                                          
and    $0x1,%eax                                                   
sub    %rdx,%rax                                                   
retq

This is very good code.  Unfortunately, the 128 bit version doesn't get
optimized nearly so well.

__int128_t tmod2(__int128_t x)
{
        return x % 2;
}

mov    %rsi,%rdx
mov    %rdi,%r8
xor    %ecx,%ecx
shr    $0x3f,%rdx
push   %rbx
add    %rdx,%r8
xor    %edi,%edi
mov    %r8,%rsi
mov    %rdi,%r9
and    $0x1,%esi
mov    %rsi,%r8
sub    %rdx,%r8
sbb    %rcx,%r9
mov    %r8,%rax
mov    %r9,%rdx
pop    %rbx
retq

It looks like this simple variation of the 64bit algorithm will work for the
128 bit version:

mov    %rsi,%rdx    <--- Just changed rdi into rsi
shr    $0x3f,%rdx   <--- nicely already calculates high bytes in rdx
lea    (%rdi,%rdx,1),%rax
and    $0x1,%eax
sub    %rdx,%rax
retq


-- 
           Summary: missed optimization of constant __int128_t modulus
           Product: gcc
           Version: 4.5.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: middle-end
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: svfuerst at gmail dot com
 GCC build triplet: x86_64-linux
  GCC host triplet: x86_64-linux
GCC target triplet: x86_64-linux


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43883

[Bug middle-end/43883] missed optimization of constant __int128_t modulus

[ubizjak at gmail dot com]

------- Comment #5 from ubizjak at gmail dot com  2010-04-30 19:00 -------
(In reply to comment #4)
> Argh, the sar trick doesn't work when the number is negative and even.  Sorry
> about the extra noise.
> 
> This leaves as the best code:
> mov    %rsi,%rdx
> shr    $0x3f,%rdx
> lea    (%rdi,%rdx,1),%rax
> and    $0x1,%eax
> sub    %rdx,%rax
> sbb    %rdx,%rdx
> 
> This is still better than current version.  Of course, changing the and
> instruction will allow faster versions of x%4, x%8, x%16 etc.

Belive it or not, but the version that you show in the description is how gcc
handles subregs... it starts OK, but when register allocator comes into play...

Confirmed as RA problem, the same thing happens with "long long" and -m32.


-- 

ubizjak at gmail dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ubizjak at gmail dot com
             Status|UNCONFIRMED                 |NEW
          Component|target                      |middle-end
     Ever Confirmed|0                           |1
           Keywords|                            |ra
   Last reconfirmed|0000-00-00 00:00:00         |2010-04-30 19:00:41
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43883

[Bug middle-end/43883] missed optimization of constant __int128_t modulus

[svfuerst at gmail dot com]

------- Comment #6 from svfuerst at gmail dot com  2010-04-30 20:30 -------
For posterity, I might as well note that with the sbb added on the end we don't
need the initial mov instruction if we do some register renaming.  This leaves
the, hopefully optimal this time, five-instruction fragment as the goal:

shr    $0x3f,%rsi
lea    (%rdi,%rsi,1),%rax
and    $0x1,%eax
sub    %rsi,%rax
sbb    %rdx,%rdx


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43883