[Bug c++/110304] New: __builtin_adcs missing and you miss the point of builtin_adcb

[Bug c++/110304] New: __builtin_adcs missing and you miss the point of builtin_adcb

[unlvsur at live dot com]

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

            Bug ID: 110304
           Summary: __builtin_adcs missing and you miss the point of
                    builtin_adcb
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: unlvsur at live dot com
  Target Milestone: ---

https://github.com/gcc-mirror/gcc/commit/2b4e0415ad664cdb3ce87d1f7eee5ca26911a05b#

This does not include __builtin_adcb, __builtin_adcs and __builtin_subcb,
__builtin_subcs

"
While the design of these builtins in clang is questionable,
rather than being say
unsigned __builtin_addc (unsigned, unsigned, bool, bool *)
"

You miss the point of the point when it falls back to architectures like mips,
wasm, riscv or loongarch where they do not provide flags at all:

template<::std::unsigned_integral T>
inline constexpr T add_carry(T a,T b,T carryin,T& carryout) noexcept
{
    [[assume(carryin==0||carryin==1)]];
    a+=b;
    carryout=a<b;
    a+=carryin;
    carryout+=a<carryin;
    return a;
}


template<::std::unsigned_integral T>
inline constexpr T sub_carry(T a,T b,T carryin,T& carryout) noexcept
{
    [[assume(carryin==0||carryin==1)]];
    a-=b;
    carryout=b<a;
    a-=carryin;
    carryout+=carryin<a;
    return a;
}

Mine is much faster than your __builtin_uadd_overflow on these architectures.

 #define __builtin_addc(a,b,carry_in,carry_out) \
  ({ unsigned _s; \
     unsigned _c1 = __builtin_uadd_overflow (a, b, &_s); \
     unsigned _c2 = __builtin_uadd_overflow (_s, carry_in, &_s); \
     *(carry_out) = (_c1 | _c2); \
     _s; })

[Bug c++/110304] __builtin_adcs missing and jakub you miss the point of builtin_adcb

[unlvsur at live dot com]

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

--- Comment #1 from cqwrteur <unlvsur at live dot com> ---
Also mine is exactly what GCC would generate exactly the same as clang without
builtin. Clang internally implements this as mine one.

Since on wasm, riscv or loongarch where these architectures do not provide
carry flags. Introducing types like bool that would cause implicit cast would
create performance issues and instructions dependencies. Usually add
instruction can be pipelined very well due to tons of ALU ports are designed
for add.


template<::std::unsigned_integral T>
inline constexpr T add_carry(T a,T b,T carryin,T& carryout) noexcept
{
    [[assume(carryin==0||carryin==1)]];
    a+=b;
    carryout=a<b;
    a+=carryin;
    carryout+=a<carryin;
    return a;
}

Take add_carry as an example. Here you see, all operations are either move,
less than (which is minus technically) or add. The add and move ALU deals with
all the logic of carry here without any logic or bit operation. No branches or
bit operations are involved.

while __builtin_uadd_overflow clearly needs branches to know whether it
overflows.

[Bug c++/110304] __builtin_adcs missing and jakub you miss the point of builtin_adcb

[unlvsur at live dot com]

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

--- Comment #2 from cqwrteur <unlvsur at live dot com> ---
https://godbolt.org/z/bz3PjeMdY

[Bug c++/110304] __builtin_adcs missing and jakub you miss the point of builtin_adcb

[unlvsur at live dot com]

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

--- Comment #3 from cqwrteur <unlvsur at live dot com> ---
(In reply to cqwrteur from comment #2)
> https://godbolt.org/z/bz3PjeMdY

https://github.com/animetosho/md5-optimisation

Here was an example that shows + is faster than | since + uses a lot for
dependency reasons.

[Bug c++/110304] __builtin_adcs missing and jakub you miss the point of builtin_adcb

[jakub at gcc dot gnu.org]

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

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
__builtin_adcb, __builtin_adcs and __builtin_subcb, __builtin_subcs weren't
added intentionally, I doubt they are widely used in practice.  And
__builtin_u{add,sub}{,l,ll}_overflow isn't defined for them either.  One can
always use a pair of __builtin_{add,sub}_overflow if one really needs the
8-bit/16-bit ones.
As for code generation on mips, loongarch etc., it is up to the target
maintainers to make sure good code is generated out of __builtin_*_overflow for
the common cases (all same types for them), or they even have now the option to
implement the uaddc5/usubc5 optabs if it helps with the code generation for
these.

[Bug c++/110304] __builtin_adcs missing and jakub you miss the point of builtin_adcb

[jakub at gcc dot gnu.org]

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

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
The reason for | rather than + is clang compatibility with its misdesigned
interface.
It never returns 2 as carry-out, even if you add 0xffffffffU, 0xfffffffU and
0xfffffffU.
But, if pattern matching can prove the carry-in is only in [0, 1] range, then
all of
+, | or ^ act the same and if target provides uaddc5/usubc5 patterns, it will
be pattern matched.

[Bug c++/110304] __builtin_adcs missing and jakub you miss the point of builtin_adcb

[unlvsur at live dot com]

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

--- Comment #6 from cqwrteur <unlvsur at live dot com> ---
i can guarantee my implementation is optimal on these no flags architectures
without the need of optimizations from backend. Then there would be no need to
do backend specific optimizations on mips riscv and loongarch


Using the type itself prevents casting. It is the users responsibility to
ensure the value is either zero or one.


Get Outlook for Android<https://aka.ms/AAb9ysg>
________________________________
From: jakub at gcc dot gnu.org <gcc-bugzilla@gcc.gnu.org>
Sent: Monday, June 19, 2023 2:22:10 AM
To: unlvsur@live.com <unlvsur@live.com>
Subject: [Bug c++/110304] __builtin_adcs missing and jakub you miss the point
of builtin_adcb

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

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
The reason for | rather than + is clang compatibility with its misdesigned
interface.
It never returns 2 as carry-out, even if you add 0xffffffffU, 0xfffffffU and
0xfffffffU.
But, if pattern matching can prove the carry-in is only in [0, 1] range, then
all of
+, | or ^ act the same and if target provides uaddc5/usubc5 patterns, it will
be pattern matched.

--
You are receiving this mail because:
You are on the CC list for the bug.
You reported the bug.

[Bug c++/110304] __builtin_adcs missing and jakub you miss the point of builtin_adcb

[unlvsur at live dot com]

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

--- Comment #7 from cqwrteur <unlvsur at live dot com> ---
for example


lets assume  you design the interface with both bool carryin and bool *
carryout

char unsigned carryin=foo();

bool carryout

__builtin_addcl(a,b,carryin,&carryout);//carryin will do implicit cast for
carryin here, therefore there is an extra comparison instruction. carryin will
implicit cast to bool


clang's interface does not do any implicit cast for carryin




Get Outlook for Android<https://aka.ms/AAb9ysg>
________________________________
From: jakub at gcc dot gnu.org <gcc-bugzilla@gcc.gnu.org>
Sent: Monday, June 19, 2023 2:22:10 AM
To: unlvsur@live.com <unlvsur@live.com>
Subject: [Bug c++/110304] __builtin_adcs missing and jakub you miss the point
of builtin_adcb

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

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
The reason for | rather than + is clang compatibility with its misdesigned
interface.
It never returns 2 as carry-out, even if you add 0xffffffffU, 0xfffffffU and
0xfffffffU.
But, if pattern matching can prove the carry-in is only in [0, 1] range, then
all of
+, | or ^ act the same and if target provides uaddc5/usubc5 patterns, it will
be pattern matched.

--
You are receiving this mail because:
You are on the CC list for the bug.
You reported the bug.

[Bug c++/110304] __builtin_adcs missing and jakub you miss the point of builtin_adcb

[jakub at gcc dot gnu.org]

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

--- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to cqwrteur from comment #6)
> i can guarantee my implementation is optimal on these no flags architectures
> without the need of optimizations from backend. Then there would be no need
> to do backend specific optimizations on mips riscv and loongarch

Except that the clang builtins don't require [0, 1] range of carry-in and
actually support any other value.  So, I can't do assumptions like that when
I'm providing compatibility builtins.

[Bug c++/110304] __builtin_adcs missing and jakub you miss the point of builtin_adcb

[unlvsur at live dot com]

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

--- Comment #9 from cqwrteur <unlvsur at live dot com> ---
well. user can use __builtin_unreachablecor C++23 assume before calling that
then it would be safe to know it is zero or one

Get Outlook for Android<https://aka.ms/AAb9ysg>
________________________________
From: unlvsur unlvsur <unlvsur@live.com>
Sent: Monday, June 19, 2023 2:32:24 AM
To: jakub at gcc dot gnu.org <gcc-bugzilla@gcc.gnu.org>
Subject: Re: [Bug c++/110304] __builtin_adcs missing and jakub you miss the
point of builtin_adcb

for example


lets assume  you design the interface with both bool carryin and bool *
carryout

char unsigned carryin=foo();

bool carryout

__builtin_addcl(a,b,carryin,&carryout);//carryin will do implicit cast for
carryin here, therefore there is an extra comparison instruction. carryin will
implicit cast to bool


clang's interface does not do any implicit cast for carryin




Get Outlook for Android<https://aka.ms/AAb9ysg>
________________________________
From: jakub at gcc dot gnu.org <gcc-bugzilla@gcc.gnu.org>
Sent: Monday, June 19, 2023 2:22:10 AM
To: unlvsur@live.com <unlvsur@live.com>
Subject: [Bug c++/110304] __builtin_adcs missing and jakub you miss the point
of builtin_adcb

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

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
The reason for | rather than + is clang compatibility with its misdesigned
interface.
It never returns 2 as carry-out, even if you add 0xffffffffU, 0xfffffffU and
0xfffffffU.
But, if pattern matching can prove the carry-in is only in [0, 1] range, then
all of
+, | or ^ act the same and if target provides uaddc5/usubc5 patterns, it will
be pattern matched.

--
You are receiving this mail because:
You are on the CC list for the bug.
You reported the bug.

[Bug c++/110304] __builtin_adcs missing and jakub you miss the point of builtin_adcb

[unlvsur at live dot com]

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

--- Comment #10 from cqwrteur <unlvsur at live dot com> ---
i do not know whether | would provide the same performance as + here would due
to chain adding.


GMP uses all + it seems. Just like i do


https://gmplib.org/list-archives/gmp-devel/2021-September/006013.html



Get Outlook for Android<https://aka.ms/AAb9ysg>
________________________________
From: unlvsur unlvsur <unlvsur@live.com>
Sent: Monday, June 19, 2023 2:36:56 AM
To: jakub at gcc dot gnu.org <gcc-bugzilla@gcc.gnu.org>
Subject: Re: [Bug c++/110304] __builtin_adcs missing and jakub you miss the
point of builtin_adcb

well. user can use __builtin_unreachablecor C++23 assume before calling that
then it would be safe to know it is zero or one

Get Outlook for Android<https://aka.ms/AAb9ysg>
________________________________
From: unlvsur unlvsur <unlvsur@live.com>
Sent: Monday, June 19, 2023 2:32:24 AM
To: jakub at gcc dot gnu.org <gcc-bugzilla@gcc.gnu.org>
Subject: Re: [Bug c++/110304] __builtin_adcs missing and jakub you miss the
point of builtin_adcb

for example


lets assume  you design the interface with both bool carryin and bool *
carryout

char unsigned carryin=foo();

bool carryout

__builtin_addcl(a,b,carryin,&carryout);//carryin will do implicit cast for
carryin here, therefore there is an extra comparison instruction. carryin will
implicit cast to bool


clang's interface does not do any implicit cast for carryin




Get Outlook for Android<https://aka.ms/AAb9ysg>
________________________________
From: jakub at gcc dot gnu.org <gcc-bugzilla@gcc.gnu.org>
Sent: Monday, June 19, 2023 2:22:10 AM
To: unlvsur@live.com <unlvsur@live.com>
Subject: [Bug c++/110304] __builtin_adcs missing and jakub you miss the point
of builtin_adcb

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

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
The reason for | rather than + is clang compatibility with its misdesigned
interface.
It never returns 2 as carry-out, even if you add 0xffffffffU, 0xfffffffU and
0xfffffffU.
But, if pattern matching can prove the carry-in is only in [0, 1] range, then
all of
+, | or ^ act the same and if target provides uaddc5/usubc5 patterns, it will
be pattern matched.

--
You are receiving this mail because:
You are on the CC list for the bug.
You reported the bug.

[Bug c++/110304] __builtin_adcs missing and jakub you miss the point of builtin_adcb

[unlvsur at live dot com]

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

--- Comment #11 from cqwrteur <unlvsur at live dot com> ---
Actually mine 

template<::std::unsigned_integral T>
inline constexpr T add_carry(T a,T b,T carryin,T& carryout) noexcept
{
    [[assume(carryin==0||carryin==1)]];
    a+=b;
    carryout=a<b;
    a+=carryin;
    carryout+=a<carryin;
    return a;
}

can be pattern-matching without builtins. This might be more universal and be
optimized very early on.

[Bug c++/110304] __builtin_adcs missing and jakub you miss the point of builtin_adcb

[jakub at gcc dot gnu.org]

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

--- Comment #12 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to cqwrteur from comment #11)
> Actually mine 
> 
> template<::std::unsigned_integral T>
> inline constexpr T add_carry(T a,T b,T carryin,T& carryout) noexcept
> {
>     [[assume(carryin==0||carryin==1)]];
>     a+=b;
>     carryout=a<b;
>     a+=carryin;
>     carryout+=a<carryin;
>     return a;
> }
> 
> can be pattern-matching without builtins. This might be more universal and
> be optimized very early on.

And you are trying to say what with this?
This is pattern matched by the r14-1837 change, and covered in the
gcc.target/i386/pr79173-5.c testcase.

[Bug c++/110304] __builtin_adcs missing and jakub you miss the point of builtin_adcb

[unlvsur at live dot com]

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

--- Comment #13 from cqwrteur <unlvsur at live dot com> ---
See this:
https://godbolt.org/z/eozPahn9G


addcarry pattern it recognizes but not subcarry.
You can see it does not recognize the following:

template<typename T>
inline constexpr T sub_carry(T x,T y,T carryin,T& carryout) noexcept
{
#if __has_cpp_attribute(assume)
        [[assume(carryin==0||carryin==1)]];
#endif
        y=x-y;
        carryout=x<y;
        x=y-carryin;
        carryout+=y<x;
        return x;
}

I have iterated all values for char unsigned, and all my answer matches clang's
builtin.

Also see the pissmeoff2, the instructions GCC generates are very messy.



https://github.com/msotoodeh/curve25519/blob/23a656c5234758f50d0576b49e0e9eecff68063b/source/asm64/amd64.gnu/Sub.s#L51

Its quality is nowhere comparable to the one of original assembly
implementation.

[Bug c++/110304] __builtin_adcs missing and jakub you miss the point of builtin_adcb

[unlvsur at live dot com]

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

--- Comment #14 from cqwrteur <unlvsur at live dot com> ---
https://godbolt.org/z/4ej4dnr4b

I find a bug here:

    f0 = __builtin_subcl(f0,v,0,&carry);
    f1 = __builtin_subcl(f1,zero,carry,&carry);

The compiler generates:

  setb %cl//redundant
  movzbl %cl, %ecx//redundant
  subq %rcx, %rdx//redundant


They should be just one instruction which is sbbq $0, %rcx


I minus a constant, why would it give me so many redundant instructions??

[Bug c++/110304] __builtin_adcs missing and jakub you miss the point of builtin_adcb

[jakub at gcc dot gnu.org]

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

--- Comment #15 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to cqwrteur from comment #13)
> See this:
> https://godbolt.org/z/eozPahn9G
> 
> 
> addcarry pattern it recognizes but not subcarry.

And see this:
https://gcc.gnu.org/pipermail/gcc-patches/2023-June/620821.html
I've said that due to reassoc subcarry can't be matched because the different
limbs get intermingled too much.  And that one should be using the overflow
builtins (or now the clang compatible builtins) instead, at least for now.

> Also see the pissmeoff2, the instructions GCC generates are very messy.

Please carefully read the Code of Conduct that has been announced today.
https://gcc.gnu.org/conduct.html

[Bug c++/110304] __builtin_adcs missing and jakub you miss the point of builtin_adcb

[unlvsur at live dot com]

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

--- Comment #16 from cqwrteur <unlvsur at live dot com> ---
ok

Would you mind looking at the following link, https://godbolt.org/z/z7K79YMWr,
and sharing your thoughts? I would greatly appreciate your feedback. Thank you
very much.

[Bug c++/110304] __builtin_adcs missing and jakub you miss the point of builtin_adcb

[jakub at gcc dot gnu.org]

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

--- Comment #17 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Maybe later, I'm currently busy with _BitInt support.

[Bug c++/110304] __builtin_adcs missing and jakub you miss the point of builtin_adcb

[unlvsur at live dot com]

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

--- Comment #18 from cqwrteur <unlvsur at live dot com> ---
Would you mind if I clarified a few points regarding your query? I'm referring
to implementing "sub borrow" with sub_overflow, as demonstrated in the code
snippet at https://godbolt.org/z/ev3TfeTvd , correct?

Additionally, I'd like to inquire about the possibility of enabling the
compiler to comprehend the "carry + set value" pattern. For instance, in the
given example:
carry = sub_carry(false, a, b, c);
unsigned v { carry ? 38u : 0u };

To clarify, the intention is to utilize the carry flag for subtraction
operations where a register subtracts itself and then performs a bitwise AND
operation with a specified value.
carry = sub_carry(false, a, b, c);
unsigned v;
carry = sub_carry(carry, v, v, v);
v &= 38u;

[Bug c++/110304] __builtin_adcs missing and jakub you miss the point of builtin_adcb

[unlvsur at live dot com]

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

--- Comment #19 from cqwrteur <unlvsur at live dot com> ---
(In reply to cqwrteur from comment #18)
> Would you mind if I clarified a few points regarding your query? I'm
> referring to implementing "sub borrow" with sub_overflow, as demonstrated in
> the code snippet at https://godbolt.org/z/ev3TfeTvd , correct?
> 
> Additionally, I'd like to inquire about the possibility of enabling the
> compiler to comprehend the "carry + set value" pattern. For instance, in the
> given example:
> carry = sub_carry(false, a, b, c);
> unsigned v { carry ? 38u : 0u };
> 
> To clarify, the intention is to utilize the carry flag for subtraction
> operations where a register subtracts itself and then performs a bitwise AND
> operation with a specified value.
> carry = sub_carry(false, a, b, c);
> unsigned v;
> carry = sub_carry(carry, v, v, v);
> v &= 38u;

I have noticed that the generated assembly from the subzeroproblem function
does not align with my expectations.