Save 1 instruction in libdivide_u64_branchfree_do()

[kimwalisch]

I guess you could decrease the instruction count by 1 in libdivide_u64_branchfree_do() by using:

uint64_t libdivide_u64_branchfree_do(uint64_t numer, const struct libdivide_u64_branchfree_t *denom) {
    // same as alg 2
    uint64_t q = libdivide__mullhi_u64(denom->magic, numer);
    uint64_t t = ((numer - q) >> 1) + q;
    return t >> denom->more;
}

instead of:

uint64_t libdivide_u64_branchfree_do(uint64_t numer, const struct libdivide_u64_branchfree_t *denom) {
    // same as alg 2
    uint64_t q = libdivide__mullhi_u64(denom->magic, numer);
    uint64_t t = ((numer - q) >> 1) + q;
    return t >> (denom->more & LIBDIVIDE_64_SHIFT_MASK);
}

This would require a different initialization algorithm for libdivide_u64_branchfree_do(). I am not sure if it is worth it.

[ridiculousfish]

You'd think so, but (at least on x86) the mask is actually not emitted at all, because the shift instruction only looks at the bottom bits. So the mask currently costs 0 instructions.

This isn't true for the vector case, so we can leave this open to track that.

[kimwalisch]

Are you sure about this?

I compiled both versions using GCC -O2 -S and the 2nd version t >> (denom->more & LIBDIVIDE_64_SHIFT_MASK) contains many andl $63, %ecx instructions whereas the 1st version t >> denom->more contains none!

Here is the assembly diff of both versions (1st version t >> denom->more, 2nd version t >> (denom->more & LIBDIVIDE_64_SHIFT_MASK)):

$ diff S2_easy_libdivide_new.s S2_easy_libdivide_old.s 
333a334
>   andl    $63, %ecx
356a358
>   andl    $63, %ecx
398a401
>   andl    $63, %ecx
791a795
>   andl    $63, %ecx
811,815c815,816
<   leaq    (%rcx,%rdx), %rax
<   movq    48(%rsp), %rcx
<   subq    %rax, %rcx
<   shrq    %rcx
<   addq    %rcx, %rax
---
>   movq    48(%rsp), %rax
>   addq    %rcx, %rdx
816a818,821
>   subq    %rdx, %rax
>   shrq    %rax
>   addq    %rdx, %rax
>   andl    $63, %ecx
867a873
>   andl    $63, %ecx
1409a1416
>   andl    $63, %ecx
1429,1433c1436,1437
<   leaq    (%rcx,%rdx), %rax
<   movq    48(%rsp), %rcx
<   subq    %rax, %rcx
<   shrq    %rcx
<   addq    %rcx, %rax
---
>   movq    48(%rsp), %rax
>   addq    %rcx, %rdx
1434a1439,1442
>   subq    %rdx, %rax
>   shrq    %rax
>   addq    %rdx, %rax
>   andl    $63, %ecx
1485a1494
>   andl    $63, %ecx

So I still think you could save one andl $63, %ecx instruction in libdivide_u64_branchfree_do(). But I also think that it would not be faster because today's out of order CPUs can execute up to 4 independent instructions simultaneously.

[ridiculousfish]

Ugh, you're right, clang is getting it right, but gcc is being stupid here. Ok, I guess we ought to fix this. Nice catch!

[ridiculousfish]

Fixed by #13

[kimwalisch]

I have compiled my code using the very latest branchfree libdivide.h using GCC 5.2 and -std=c++11 and got some warnings which have been introduced by my Save 1 instruction in libdivide_u64_branchfree_do() code changes:

g++ -std=c++11 -DPACKAGE_NAME=\"primecount\" -DPACKAGE_TARNAME=\"primecount\" -DPACKAGE_VERSION=\"3.1\" "-DPACKAGE_STRING=\"primecount 3.1\"" -DPACKAGE_BUGREPORT=\"kim.walisch@gmail.com\" -DPACKAGE_URL=\"\" -DPACKAGE=\"primecount\" -DVERSION=\"3.1\" -DSTDC_HEADERS=1 -DHAVE_SYS_TYPES_H=1 -DHAVE_SYS_STAT_H=1 -DHAVE_STDLIB_H=1 -DHAVE_STRING_H=1 -DHAVE_MEMORY_H=1 -DHAVE_STRINGS_H=1 -DHAVE_INTTYPES_H=1 -DHAVE_STDINT_H=1 -DHAVE_UNISTD_H=1 -DHAVE_DLFCN_H=1 -DLT_OBJDIR=\".libs/\" -DNDEBUG=1 -DHAVE___BUILTIN_POPCOUNT=1 -DHAVE___BUILTIN_POPCOUNTLL=1 -DHAVE___INT128_T=1 -DHAVE_LIBDIVIDE=1 -I. -I./include -fopenmp -mpopcnt -DHAVE_POPCNT=1 -O2 -Iprimesieve-5.6.0/include -MT src/libprimecount_la-phi_libdivide.lo -MD -MP -MF src/.deps/libprimecount_la-phi_libdivide.Tpo -c src/phi_libdivide.cpp  -fPIC -DPIC -o src/.libs/libprimecount_la-phi_libdivide.o
In file included from src/phi_libdivide.cpp:22:0:
./include/libdivide.h: In function ‘{anonymous}::libdivide::libdivide_u32_branchfree_t {anonymous}::libdivide::libdivide_u32_branchfree_gen(uint32_t)’:
./include/libdivide.h:774:66: warning: narrowing conversion of ‘(((int)tmp.{anonymous}::libdivide::libdivide_u32_t::more) & 31)’ from ‘int’ to ‘uint8_t {aka unsigned char}’ inside { } [-Wnarrowing]
     struct libdivide_u32_branchfree_t ret = {tmp.magic, tmp.more & LIBDIVIDE_32_SHIFT_MASK};
                                                                  ^
./include/libdivide.h: In function ‘uint32_t {anonymous}::libdivide::libdivide_u32_branchfree_recover(const {anonymous}::libdivide::libdivide_u32_branchfree_t*)’:
./include/libdivide.h:833:67: warning: narrowing conversion of ‘(int)(((unsigned char)denom->{anonymous}::libdivide::libdivide_u32_branchfree_t::more) | 64u)’ from ‘int’ to ‘uint8_t {aka unsigned char}’ inside { } [-Wnarrowing]
     struct libdivide_u32_t denom_u32 = {denom->magic, denom->more | LIBDIVIDE_ADD_MARKER};
                                                                   ^
./include/libdivide.h: In function ‘{anonymous}::libdivide::libdivide_u64_branchfree_t {anonymous}::libdivide::libdivide_u64_branchfree_gen(uint64_t)’:
./include/libdivide.h:969:66: warning: narrowing conversion of ‘(((int)tmp.{anonymous}::libdivide::libdivide_u64_t::more) & 63)’ from ‘int’ to ‘uint8_t {aka unsigned char}’ inside { } [-Wnarrowing]
     struct libdivide_u64_branchfree_t ret = {tmp.magic, tmp.more & LIBDIVIDE_64_SHIFT_MASK};
                                                                  ^
./include/libdivide.h: In function ‘uint64_t {anonymous}::libdivide::libdivide_u64_branchfree_recover(const {anonymous}::libdivide::libdivide_u64_branchfree_t*)’:
./include/libdivide.h:1039:67: warning: narrowing conversion of ‘(int)(((unsigned char)denom->{anonymous}::libdivide::libdivide_u64_branchfree_t::more) | 64u)’ from ‘int’ to ‘uint8_t {aka unsigned char}’ inside { } [-Wnarrowing]
     struct libdivide_u64_t denom_u64 = {denom->magic, denom->more | LIBDIVIDE_ADD_MARKER};

In order to fix the warnings we must add a (uint8_t) cast at lines 774, 833, 969 and 1039.

For example:

struct libdivide_u64_t denom_u64 = {denom->magic, (uint8_t)(denom->more | LIBDIVIDE_ADD_MARKER)};