[Bug rtl-optimization/97437] New: builtins subcarry and addcarry still not generate the right code. Not get optimized to immediate value

[Bug rtl-optimization/97437] New: builtins subcarry and addcarry still not generate the right code. Not get optimized to immediate value

[euloanty at live dot com]

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

            Bug ID: 97437
           Summary: builtins subcarry and addcarry still not generate the
                    right code. Not get optimized to immediate value
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: rtl-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: euloanty at live dot com
  Target Milestone: ---

#include<cstdint>
#include<array>
#if defined(_MSC_VER)
#include<intrin.h>
#elif defined(__x86_64__) || defined(__i386__)
#include<immintrin.h>
#endif

struct field_number
{
        using value_type =
std::conditional_t<sizeof(std::size_t)>=8,std::uint64_t,std::uint32_t>;
        value_type content[32/sizeof(value_type)];
        inline constexpr value_type const& operator[](std::size_t pos) const
noexcept
        {
                return content[pos];
        }
        inline constexpr value_type& operator[](std::size_t pos) noexcept
        {
                return content[pos];
        }
};

namespace intrinsics
{
template<typename T>
#if __cpp_lib_concepts >= 202002L
requires (std::unsigned_integral<T>)
#endif
inline constexpr bool sub_borrow(bool borrow,T a,T b,T& out) noexcept
{
#if defined(_MSC_VER) || defined(__x86_64__) || defined(__i386__)
#if __cpp_lib_is_constant_evaluated >= 201811L
        if(std::is_constant_evaluated())
                return (out=a-b-borrow)>=a;
        else
#endif
        {
                if constexpr(sizeof(T)==8)
#if defined(__x86_64__)
                        return _subborrow_u64(borrow,a,b,
#if !defined(__INTEL_COMPILER ) &&(defined(__GNUC__) || defined(__clang__))
                        reinterpret_cast<unsigned long long*>(&out));
#else
                        &out);
#endif
#else
                        return (out=a-b-borrow)>=a;
#endif

                if constexpr(sizeof(T)==4)
                        return
_subborrow_u32(borrow,a,b,reinterpret_cast<std::uint32_t*>(&out));
                else if constexpr(sizeof(T)==2)
                        return
_subborrow_u16(borrow,a,b,reinterpret_cast<std::uint16_t*>(&out));
                else if constexpr(sizeof(T)==1)
                        return
_subborrow_u8(borrow,a,b,reinterpret_cast<std::uint8_t*>(&out));
        }
#else
        return (out=a-b-borrow)>=a;
#endif
}

}


field_number operator-(field_number const& x,field_number const& y) noexcept
{
        using namespace intrinsics;
        using unsigned_type = field_number::value_type;
        constexpr unsigned_type zero{};
        field_number f;
        bool borrow{sub_borrow(false,x[0],y[0],f[0])};
        borrow=sub_borrow(borrow,x[1],y[1],f[1]);
        borrow=sub_borrow(borrow,x[2],y[2],f[2]);
        borrow=sub_borrow(borrow,x[3],y[3],f[3]);
        unsigned_type v{};
        sub_borrow(borrow,v,v,v);
        v&=static_cast<unsigned_type>(38);
        borrow=sub_borrow(false,f[0],v,f[0]);
        borrow=sub_borrow(borrow,f[1],zero,f[1]);
        borrow=sub_borrow(borrow,f[2],zero,f[2]);
        borrow=sub_borrow(borrow,f[3],zero,f[3]);
        sub_borrow(borrow,v,v,v);
        v&=static_cast<unsigned_type>(38);
        borrow=sub_borrow(false,f[0],v,f[0]);
        borrow=sub_borrow(borrow,f[1],zero,f[1]);
        borrow=sub_borrow(borrow,f[2],zero,f[2]);
        borrow=sub_borrow(borrow,f[2],zero,f[3]);
        return f;
}

https://godbolt.org/z/xM8xef

operator-(field_number const&, field_number const&):
        movq    (%rsi), %r9
        subq    (%rdx), %r9
        movq    %rdi, %r8
        movq    %rdx, %rax
        movq    %r9, (%rdi)
        movq    8(%rsi), %rdi
        sbbq    8(%rdx), %rdi
        movq    %rdi, 8(%r8)
        movq    16(%rsi), %rdx
        sbbq    16(%rax), %rdx
        movq    %rdx, 16(%r8)
        movq    24(%rax), %rax
        movq    24(%rsi), %rsi
        sbbq    %rax, %rsi

//Here is an output dependency. No need movl 0 to %eax.
        movl    $0, %eax
        movq    %rax, %rcx
        sbbq    %rax, %rcx
        andl    $38, %ecx
        subq    %rcx, %r9
        sbbq    %rax, %rdi// why sbbq %rax,%rdi instead of sbbq 0 %rdi ????
//The %rax register should not get allocated or used in GCC
        sbbq    %rax, %rdx
        sbbq    %rax, %rsi
        sbbq    %rcx, %rcx
        andl    $38, %ecx
        subq    %rcx, %r9
        sbbq    %rax, %rdi
        movq    %r9, (%r8)
        sbbq    %rax, %rdx
        movq    %rdi, 8(%r8)
        movq    %rdx, 16(%r8)
        sbbq    %rax, %rdx
        movq    %r8, %rax
        movq    %rdx, 24(%r8)
        ret


The assembly GCC generated is still worse than clang. although clang does not
generate the optimal one either.

The subborrow instruction in GCC does not get optimized as immediate value

The "correct" assembly it generates should be like what clang generates (you
can use different registers no problem) minus that xorl    %ecx, %ecx clean up
instruction.


operator-(field_number const&, field_number const&):                #
@operator-(field_number const&, field_number const&)
        movq    %rdi, %rax
        movq    (%rsi), %r8
        subq    (%rdx), %r8
        movq    8(%rsi), %r9
        sbbq    8(%rdx), %r9
        movq    16(%rsi), %rdi
        sbbq    16(%rdx), %rdi
        movq    24(%rsi), %rsi
        sbbq    24(%rdx), %rsi
        sbbq    %rcx, %rcx
        andl    $38, %ecx
        subq    %rcx, %r8
        sbbq    $0, %r9
        sbbq    $0, %rdi
        sbbq    $0, %rsi
        sbbq    %rcx, %rcx
        andl    $38, %ecx
        subq    %rcx, %r8
        sbbq    $0, %r9
        movq    %r8, (%rax)
        movq    %r9, 8(%rax)
        sbbq    $0, %rdi
        movq    %rdi, 16(%rax)
        sbbq    $0, %rdi
        movq    %rdi, 24(%rax)
        retq

[Bug target/97437] builtins subcarry and addcarry still not generate the right code. Not get optimized to immediate value

[jakub at gcc dot gnu.org]

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

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
I don't see anything undesirable on that.  The 0 aka %rax is used in 7
different instructions later on besides the move, so either we just clear %ecx
(can't use xorl for that as the flags register needs to be live), or clear %eax
and copy to %ecx (3 bytes more), but then gain 7 bytes back because we don't
really use an immediate form.

[Bug target/97437] builtins subcarry and addcarry still not generate the right code. Not get optimized to immediate value

[jakub at gcc dot gnu.org]

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

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Anyway,
#include <x86intrin.h>

void
foo (unsigned int a[4], unsigned int b[4])
{
  unsigned char carry = 0;
  carry = _addcarry_u32 (carry, 42, b[0], &a[0]);
  carry = _addcarry_u32 (carry, b[1], 43, &a[1]);
  carry = _addcarry_u32 (carry, 0, b[2], &a[2]);
  _addcarry_u32 (carry, b[3], 1, &a[3]);
}

void
bar (unsigned int a[4], unsigned int b[4])
{
  unsigned char carry = 0;
  carry = _subborrow_u32 (carry, a[0], 42, &a[0]);
  carry = _subborrow_u32 (carry, a[1], 43, &a[1]);
  carry = _subborrow_u32 (carry, a[2], 0, &a[2]);
  _subborrow_u32 (carry, a[3], 1, &a[3]);
}

void
baz (unsigned long long a[4], unsigned long long b[4])
{
  unsigned char carry = 0;
  carry = _addcarry_u64 (carry, 42, b[0], &a[0]);
  carry = _addcarry_u64 (carry, b[1], 43, &a[1]);
  carry = _addcarry_u64 (carry, 0, b[2], &a[2]);
  _addcarry_u64 (carry, b[3], 1, &a[3]);
}

void
qux (unsigned long long a[4], unsigned long long b[4])
{
  unsigned char carry = 0;
  carry = _subborrow_u64 (carry, a[0], 42, &a[0]);
  carry = _subborrow_u64 (carry, a[1], 43, &a[1]);
  carry = _subborrow_u64 (carry, a[2], 0, &a[2]);
  _subborrow_u64 (carry, a[3], 1, &a[3]);
}
shows an optimization problem, here the immediates aren't used multiple times,
so it would be certainly beneficial to use the immediate forms.
The problem is that neither the addcarry<mode> nor subborrow<mode> patterns do
allow immediates, addcarry<mode> has *addcarry<mode>_1 alternative that should
handle them but isn't matched in this case, and subborrow<mode> doesn't have
any.  The problem is that in order to describe what the patterns are doing in
detail we need to zero_extend the operands, but having zero_extend of a
const_int is not valid RTL.  Unfortunately when combiner substitutes immediates
into these, it simplifies the patterns too and we lose the CCCmode that the
patterns need, and unlike the fix committed yesterday, SELECT_CC_MODE can't
really do anything about that, because the comparisons aren't really specific
to CCCmode.

[Bug target/97437] builtins subcarry and addcarry still not generate the right code. Not get optimized to immediate value

[jakub at gcc dot gnu.org]

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

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
And fwprop that perhaps wouldn't "simplify" them that much punts on these
because the instructions are multiple sets.  It is unclear why, I mean, sure,
it can't be adding REG_EQUAL notes in that case, but otherwise why can't it
propagate at least constants to all the SET_SRCs of the pattern and try to
validate all the changes at once?

[Bug target/97437] builtins subcarry and addcarry still not generate the right code. Not get optimized to immediate value

[euloanty at live dot com]

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

--- Comment #4 from fdlbxtqi <euloanty at live dot com> ---
(In reply to Jakub Jelinek from comment #1)
> I don't see anything undesirable on that.  The 0 aka %rax is used in 7
> different instructions later on besides the move, so either we just clear
> %ecx (can't use xorl for that as the flags register needs to be live), or
> clear %eax and copy to %ecx (3 bytes more), but then gain 7 bytes back
> because we don't really use an immediate form.

Hello Jakub.

std::uint64_t a{};//must assign as 0 or it is UB.
sub_borrow(borrow,a,a,a);

sbbq %any_new_rigster,%any_new_rigster

means
std::uint64_t a;
if(borrow)
    a=std::numeric_limits<std::uint64_t>::max();
else
    a=0;

but faster, use less instructions and without any branch (to prevent side
channel attack)

And all those 

sub_borrow(borrow,f[2],zero,f[3]);

So, you do not need to use %rax register for the calculations at all. %rax
would just be used for RVO.

clang does not do the right thing either if I do not write

constexpr unsigned_type zero{};

to tell compiler it is zero, it does not know that either.

I think because _addcarry_, _subborrow_ was not frequently used in GCC, it
lacks many optimizations points here. That is probably why GMP, OpenSSL etc,
they frequently rewrote assemblies for doing the stuff since the compiler does
not guarantee the instructions that got generated as optimal. I know this is
probably the cost of any abstraction, particularly here I combine the usage of
OOP, concepts, templates, if constexpr, constant_evaluated(), RVO and intrinsic
together. Probably interfere with the compiler optimizations. it does not
guarantee to generate the assembly that is optimal compared to assembly.

[Bug target/97437] builtins subcarry and addcarry still not generate the right code. Not get optimized to immediate value

[segher at gcc dot gnu.org]

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

--- Comment #5 from Segher Boessenkool <segher at gcc dot gnu.org> ---
Trying 7 -> 9:
    7: r97:SI=0x2a
    9: {flags:CCC=cmp(r97:SI+r98:SI,r97:SI);r99:SI=r97:SI+r98:SI;}
      REG_DEAD r98:SI
      REG_DEAD r97:SI
Failed to match this instruction:
(parallel [
        (set (reg:CC 17 flags)
            (compare:CC (reg:SI 98 [ *b_12(D) ])
                (const_int -42 [0xffffffffffffffd6])))
        (set (reg:SI 99)
            (plus:SI (reg:SI 98 [ *b_12(D) ])
                (const_int 42 [0x2a])))
    ])

On rs6000 we have four special variants for the immediate add-with-carry
insn patterns: imm 0, imm -1, imm pos, imm neg.  All of these have
different canonical RTL.

[Bug target/97437] builtins subcarry and addcarry still not generate the right code. Not get optimized to immediate value

[segher at gcc dot gnu.org]

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

--- Comment #6 from Segher Boessenkool <segher at gcc dot gnu.org> ---
I forgot to add: subtract immediate is the same as add immediate for us,
we don't change the sense of the carry bit to a "borrow bit" (and instead,
we have a subtract-from-immediate).  But this doesn't change much at all
to the situation here.

[Bug target/97437] builtins subcarry and addcarry still not generate the right code. Not get optimized to immediate value

[jakub at gcc dot gnu.org]

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

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to Segher Boessenkool from comment #5)
> Trying 7 -> 9:
>     7: r97:SI=0x2a
>     9: {flags:CCC=cmp(r97:SI+r98:SI,r97:SI);r99:SI=r97:SI+r98:SI;}
>       REG_DEAD r98:SI
>       REG_DEAD r97:SI
> Failed to match this instruction:
> (parallel [
>         (set (reg:CC 17 flags)
>             (compare:CC (reg:SI 98 [ *b_12(D) ])
>                 (const_int -42 [0xffffffffffffffd6])))
>         (set (reg:SI 99)
>             (plus:SI (reg:SI 98 [ *b_12(D) ])
>                 (const_int 42 [0x2a])))
>     ])
> 
> On rs6000 we have four special variants for the immediate add-with-carry
> insn patterns: imm 0, imm -1, imm pos, imm neg.  All of these have
> different canonical RTL.

The i386 backend has various patterns for that too, the problem is with that
CCmode vs. CCCmode that was used originally here (otherwise sure, I can add
more).
These patterns ensure only CF is valid and so need to use CCCmode which ensures
that users will only query CF flag and nothing else.

[Bug target/97437] builtins subcarry and addcarry still not generate the right code. Not get optimized to immediate value

[segher at gcc dot gnu.org]

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

--- Comment #8 from Segher Boessenkool <segher at gcc dot gnu.org> ---
So is that something than can/should be improved in ix86_cc_mode?

[Bug target/97437] builtins subcarry and addcarry still not generate the right code. Not get optimized to immediate value

[jakub at gcc dot gnu.org]

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

--- Comment #9 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
I don't think it is really possible, because there is nothing magic about the
operands of the comparison, it can be done in both CCmode or CCCmode.  The
problem is that during simplification combiner takes that comparison apart and
recreates a new one with SELECT_CC_MODE determined one; what really matters is
the previous mode the comparison was using, or perhaps what the flags user
uses.
So, if there e.g. was a SELECT_CC_MODE alternative that would be passed also
either the earlier mode of the comparison that is being simplified, or the df
use of thee CC*mode setter, then it could decide based on that.

[Bug target/97437] builtins subcarry and addcarry still not generate the right code. Not get optimized to immediate value

[segher at gcc dot gnu.org]

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

--- Comment #10 from Segher Boessenkool <segher at gcc dot gnu.org> ---
Not even an alternative SELECT_CC_MODE; just add an argument to it, giving
the original mode?  We already have that in combine, so we can trivially
pass it.  Will that work for x86 here?