llvm dev - Nov 2018 - A pattern for portable __builtin_add_overflow()

Hi LLVM, clang,

I'm trying to write a portable version of __builtin_add_overflow() it a way
that the compiler would
recognize the pattern and use the add_overflow intrinsic / the best
possible machine instruction.

Here are docs about these builtins:
https://clang.llvm.org/docs/LanguageExtensions.html#checked-arithmetic-builtins
.

With unsigned types this is easy:

int uaddo_native(unsigned a, unsigned b, unsigned* s)
{
return __builtin_add_overflow(a, b, s);
}

int uaddo_portable(unsigned a, unsigned b, unsigned* s)
{
*s = a + b;
return *s < a;
}

We get exactly the same assembly:
uaddo_native: # @uaddo_native
xor eax, eax
add edi, esi
setb al
mov dword ptr [rdx], edi
ret
uaddo_portable: # @uaddo_portable
xor eax, eax
add edi, esi
setb al
mov dword ptr [rdx], edi
ret

But with signed types it is not so easy. I tried 2 versions, but the result
is quite far away from the optimal assembly.


int saddo_native(int a, int b, int* s)
{
return __builtin_add_overflow(a, b, s);
}

int saddo_portable(int a, int b, int* s)
{
*s = (unsigned)a + (unsigned)b;
return (a > 0) ? *s <= b : *s > b;
}

int saddo_portable2(int a, int b, int* s)
{
*s = (unsigned)a + (unsigned)b;
int cond = a > 0;
int check = *s > b;
return (cond & !check) | (!cond & check);
}

Assembly:

saddo_native: # @saddo_native
xor eax, eax
add edi, esi
seto al
mov dword ptr [rdx], edi
ret
saddo_portable: # @saddo_portable
lea eax, [rsi + rdi]
mov dword ptr [rdx], eax
cmp eax, esi
setle al
setg cl
test edi, edi
jg .LBB3_2
mov eax, ecx
.LBB3_2:
movzx eax, al
ret
saddo_portable2: # @saddo_portable2
lea eax, [rsi + rdi]
mov dword ptr [rdx], eax
test edi, edi
setg cl
cmp eax, esi
setg al
xor al, cl
movzx eax, al
ret


Do you know the trick to force the compiler to use the seto instruction?

I also noticed that the transformation for uaddo_portable happens in
CodeGen, not in IR.

Bests,
Paweł
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20181120/1779e2db/attachment-0001.html>

Going by InstCombiner::foldICmpWithConstant,
https://gcc.godbolt.org/z/To_qmm should work.

-- Sanjoy
On Tue, Nov 20, 2018 at 2:46 AM Paweł Bylica via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
>
> Hi LLVM, clang,
>
> I'm trying to write a portable version of __builtin_add_overflow() it a
way that the compiler would
> recognize the pattern and use the add_overflow intrinsic / the best
possible machine instruction.
>
> Here are docs about these builtins:
https://clang.llvm.org/docs/LanguageExtensions.html#checked-arithmetic-builtins.
>
> With unsigned types this is easy:
>
> int uaddo_native(unsigned a, unsigned b, unsigned* s)
> {
> return __builtin_add_overflow(a, b, s);
> }
>
> int uaddo_portable(unsigned a, unsigned b, unsigned* s)
> {
> *s = a + b;
> return *s < a;
> }
>
> We get exactly the same assembly:
> uaddo_native: # @uaddo_native
> xor eax, eax
> add edi, esi
> setb al
> mov dword ptr [rdx], edi
> ret
> uaddo_portable: # @uaddo_portable
> xor eax, eax
> add edi, esi
> setb al
> mov dword ptr [rdx], edi
> ret
>
> But with signed types it is not so easy. I tried 2 versions, but the result
is quite far away from the optimal assembly.
>
>
> int saddo_native(int a, int b, int* s)
> {
> return __builtin_add_overflow(a, b, s);
> }
>
> int saddo_portable(int a, int b, int* s)
> {
> *s = (unsigned)a + (unsigned)b;
> return (a > 0) ? *s <= b : *s > b;
> }
>
> int saddo_portable2(int a, int b, int* s)
> {
> *s = (unsigned)a + (unsigned)b;
> int cond = a > 0;
> int check = *s > b;
> return (cond & !check) | (!cond & check);
> }
>
> Assembly:
>
> saddo_native: # @saddo_native
> xor eax, eax
> add edi, esi
> seto al
> mov dword ptr [rdx], edi
> ret
> saddo_portable: # @saddo_portable
> lea eax, [rsi + rdi]
> mov dword ptr [rdx], eax
> cmp eax, esi
> setle al
> setg cl
> test edi, edi
> jg .LBB3_2
> mov eax, ecx
> .LBB3_2:
> movzx eax, al
> ret
> saddo_portable2: # @saddo_portable2
> lea eax, [rsi + rdi]
> mov dword ptr [rdx], eax
> test edi, edi
> setg cl
> cmp eax, esi
> setg al
> xor al, cl
> movzx eax, al
> ret
>
>
> Do you know the trick to force the compiler to use the seto instruction?
>
> I also noticed that the transformation for uaddo_portable happens in
CodeGen, not in IR.
>
> Bests,
> Paweł
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

Thanks Sanjoy,

It looks it works only up to 32-bit integers (
http://llvm.org/doxygen/InstCombineCompares_8cpp_source.html#l01255).
I will need it also for 64-bit integers.

Even if the pattern match would handle the 64-bit case I would need to use
128-bit types what is not portable still.

// P.

On Thu, Nov 22, 2018 at 6:54 PM Sanjoy Das <sanjoy at
playingwithpointers.com>
wrote:
> Going by InstCombiner::foldICmpWithConstant,
> https://gcc.godbolt.org/z/To_qmm should work.
>
> -- Sanjoy
> On Tue, Nov 20, 2018 at 2:46 AM Paweł Bylica via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
> >
> > Hi LLVM, clang,
> >
> > I'm trying to write a portable version of __builtin_add_overflow()
it a
> way that the compiler would
> > recognize the pattern and use the add_overflow intrinsic / the best
> possible machine instruction.
> >
> > Here are docs about these builtins:
>
https://clang.llvm.org/docs/LanguageExtensions.html#checked-arithmetic-builtins
> .
> >
> > With unsigned types this is easy:
> >
> > int uaddo_native(unsigned a, unsigned b, unsigned* s)
> > {
> > return __builtin_add_overflow(a, b, s);
> > }
> >
> > int uaddo_portable(unsigned a, unsigned b, unsigned* s)
> > {
> > *s = a + b;
> > return *s < a;
> > }
> >
> > We get exactly the same assembly:
> > uaddo_native: # @uaddo_native
> > xor eax, eax
> > add edi, esi
> > setb al
> > mov dword ptr [rdx], edi
> > ret
> > uaddo_portable: # @uaddo_portable
> > xor eax, eax
> > add edi, esi
> > setb al
> > mov dword ptr [rdx], edi
> > ret
> >
> > But with signed types it is not so easy. I tried 2 versions, but the
> result is quite far away from the optimal assembly.
> >
> >
> > int saddo_native(int a, int b, int* s)
> > {
> > return __builtin_add_overflow(a, b, s);
> > }
> >
> > int saddo_portable(int a, int b, int* s)
> > {
> > *s = (unsigned)a + (unsigned)b;
> > return (a > 0) ? *s <= b : *s > b;
> > }
> >
> > int saddo_portable2(int a, int b, int* s)
> > {
> > *s = (unsigned)a + (unsigned)b;
> > int cond = a > 0;
> > int check = *s > b;
> > return (cond & !check) | (!cond & check);
> > }
> >
> > Assembly:
> >
> > saddo_native: # @saddo_native
> > xor eax, eax
> > add edi, esi
> > seto al
> > mov dword ptr [rdx], edi
> > ret
> > saddo_portable: # @saddo_portable
> > lea eax, [rsi + rdi]
> > mov dword ptr [rdx], eax
> > cmp eax, esi
> > setle al
> > setg cl
> > test edi, edi
> > jg .LBB3_2
> > mov eax, ecx
> > .LBB3_2:
> > movzx eax, al
> > ret
> > saddo_portable2: # @saddo_portable2
> > lea eax, [rsi + rdi]
> > mov dword ptr [rdx], eax
> > test edi, edi
> > setg cl
> > cmp eax, esi
> > setg al
> > xor al, cl
> > movzx eax, al
> > ret
> >
> >
> > Do you know the trick to force the compiler to use the seto
instruction?
> >
> > I also noticed that the transformation for uaddo_portable happens in
> CodeGen, not in IR.
> >
> > Bests,
> > Paweł
> >
> >
> > _______________________________________________
> > LLVM Developers mailing list
> > llvm-dev at lists.llvm.org
> > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20181122/27ebe627/attachment.html>