[Bug tree-optimization/106865] New: addcarry pattern

[Bug tree-optimization/106865] New: addcarry pattern

[unlvsur at live dot com]

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

            Bug ID: 106865
           Summary: addcarry pattern
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: unlvsur at live dot com
  Target Milestone: ---

clang provides builtins like __builtin_addcll to deal with addcarry in a
generic way. However, i believe we can provide pattern matching in GCC so
existing programs may get benefit from the code, instead of adding new
builtins.

https://godbolt.org/z/3j18bPq8b

Take riscv as example:

https://godbolt.org/z/KWxfPWGz4

https://godbolt.org/z/b4r63oGqj

This proves GCC and clang can generate identical code EVEN without using adc
builtins.

I suggest to add pattern matching for code like this in GCC:

template<typename T>
inline constexpr T add_carry_no_carry_in(T a,T b,T& carryout) noexcept
{
    T res{a+b};
    carryout=res<a;
    return res;
}

template<typename T>
inline constexpr T add_carry(T a,T b,T carryin,T& carryout) noexcept
{
    if(carryin>1)
    {
        __builtin_unreachable();
    }
    a=add_carry_no_carry_in(carryin,a,carryout);
    a=add_carry_no_carry_in(a,b,carryin);
    carryout+=carryin;
    return a;
}

This should correctly identify carries for GCC without adding new builtins
while it keeps the same interface as clang's builtins.

[Bug tree-optimization/106865] addcarry pattern

[unlvsur at live dot com]

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

cqwrteur <unlvsur at live dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |unlvsur at live dot com

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

template<typename T>
inline constexpr bool add_carry2(bool carryin,T a,T b,T& res) noexcept
{
    res=carryin+a;
    T carry_temp{res<a};
    res+=b;
    carry_temp+=res<b;
    if(carry_temp>1u)
    {
        __builtin_unreachable();
    }
    return carry_temp;
}

Also pattern like this for msvc compatibility.

[Bug tree-optimization/106865] addcarry pattern

[unlvsur at live dot com]

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

--- Comment #2 from cqwrteur <unlvsur at live dot com> ---
template<typename T>
inline constexpr T add_carry(T a,T b,T carryin,T& carryout) noexcept
{
    a+=b;
    carryout=a<b;
    a+=carryin;
    carryout+=a<carryin;
    return a;
}


template<typename T>
inline constexpr T sub_carry(T a,T b,T carryin,T& carryout) noexcept
{
    a-=b;
    carryout=b<a;
    a-=carryin;
    carryout+=carryin<a;
    return a;
}

https://godbolt.org/z/ETnzKxGGd

This pattern is even better. It generates identical code with clang's builtin.
The only problem is that it does not work on archs that provide carry flags.