[cfe-dev] "Optimized implementations"?
Craig Topper via cfe-dev
cfe-dev at lists.llvm.org
Wed Sep 9 10:01:55 PDT 2020
I guess you were probably asking about __builtin_parity not the builtins
library. For __builtin_parity, the frontend emits a llvm.ctpop+ and w/ 1.
The backend has a peephole to pattern match this to the parity sequence.
But the peephole is part of a larger optimization pass that isn't
running in -O0 to save compile time. So it doesn't get pattern matched so
we emit the AND and an expand popcount. To fix this correctly for -O0 we
need to add a llvm.parity intrinsic that the frontend can emit directly
instead of the ctpop+and. Then we wouldn't need the peephole pattern match.
~Craig
On Wed, Sep 9, 2020 at 9:25 AM Craig Topper <craig.topper at gmail.com> wrote:
> The code in the builtins library is written in C and can't use
> __builtin_parity since it needs to compile with compilers that don't have
> __builtin_parity like MSVC. So to get the optimized code, we would have to
> have a version written in assembly for X86. Probably two assembly versions
> since MASM and gcc use different assembly syntax. So we'd have 3 different
> versions of parity for 3 different bit widths. Maybe some macros could
> allow us to share some bit widths or something. But ultimately it was a
> question of where to spend effort.
>
> ~Craig
>
>
> On Wed, Sep 9, 2020 at 9:08 AM Stefan Kanthak <stefan.kanthak at nexgo.de>
> wrote:
>
>> "Craig Topper" <craig.topper at gmail.com> wrote:
>>
>> > Turn on optimizations.
>>
>> What's the (deeper) reason NOT always to generate the optimised code for
>> __builtins_*?
>> Alternative question: do you also ship a library with unoptimised code
>> which
>> is linked when the -O option is not given?
>>
>> Just wondering about surprising behaviour
>> Stefan
>>
>> > On Wed, Sep 9, 2020 at 4:28 AM Stefan Kanthak <stefan.kanthak at nexgo.de>
>> > wrote:
>> >
>> >> "Craig Topper" <craig.topper at gmail.com> wrote:
>> >>
>> >> > __builtin_parity uses setnp on older x86 and popcnt with sse4.2
>> >>
>> >> Reality check, PLEASE:
>> >>
>> >> --- bug.c ---
>> >> int main(int argc, char *argv[]) {
>> >> return __builtin_parity(argc);
>> >> }
>> >> --- EOF ---
>> >>
>> >> clang -o- -target i386-pc-linux -S bug.c
>> >> clang version 10.0.0
>> >> Target: i386-pc-linux
>> >>
>> >> pushl %ebp
>> >> movl %esp, %ebp
>> >> subl $8, %esp
>> >> movl 8(%ebp), %eax
>> >> movl $0, -4(%ebp)
>> >> movl 8(%ebp), %ecx
>> >> movl %ecx, %edx
>> >> shrl %edx
>> >> andl $1431655765, %edx # imm = 0x55555555
>> >> subl %edx, %ecx
>> >> movl %ecx, %edx
>> >> andl $858993459, %edx # imm = 0x33333333
>> >> shrl $2, %ecx
>> >> andl $858993459, %ecx # imm = 0x33333333
>> >> addl %ecx, %edx
>> >> movl %edx, %ecx
>> >> shrl $4, %ecx
>> >> addl %ecx, %edx
>> >> andl $252645135, %edx # imm = 0xF0F0F0F
>> >> imull $16843009, %edx, %ecx # imm = 0x1010101
>> >> shrl $24, %ecx
>> >> andl $1, %ecx
>> >> movl %eax, -8(%ebp) # 4-byte Spill
>> >> movl %ecx, %eax
>> >> addl $8, %esp
>> >> popl %ebp
>> >> retl
>> >>
>> >>
>> >> clang -o- -target amd64-pc-linux -S bug.c
>> >>
>> >> pushq %rbp
>> >> .cfi_def_cfa_offset 16
>> >> .cfi_offset %rbp, -16
>> >> movq %rsp, %rbp
>> >> .cfi_def_cfa_register %rbp
>> >> movl $0, -4(%rbp)
>> >> movl %edi, -8(%rbp)
>> >> movl -8(%rbp), %eax
>> >> movl %eax, %ecx
>> >> shrl %ecx
>> >> andl $1431655765, %ecx # imm = 0x55555555
>> >> subl %ecx, %eax
>> >> movl %eax, %ecx
>> >> andl $858993459, %ecx # imm = 0x33333333
>> >> shrl $2, %eax
>> >> andl $858993459, %eax # imm = 0x33333333
>> >> addl %eax, %ecx
>> >> movl %ecx, %eax
>> >> shrl $4, %eax
>> >> addl %eax, %ecx
>> >> andl $252645135, %ecx # imm = 0xF0F0F0F
>> >> imull $16843009, %ecx, %eax # imm = 0x1010101
>> >> shrl $24, %eax
>> >> andl $1, %eax
>> >> popq %rbp
>> >> .cfi_def_cfa %rsp, 8
>> >> retq
>> >>
>> >> JFTR: this is the same unoptimised code as shipped in the builtins
>> library!
>> >>
>> >> Stefan
>> >>
>> >> > On Sun, Sep 6, 2020 at 1:32 PM Stefan Kanthak <
>> stefan.kanthak at nexgo.de>
>> >> > wrote:
>> >> >
>> >> >> "Craig Topper" <craig.topper at gmail.com> wrote;
>> >> >>
>> >> >>
>> >> >>
>> >> >> > Clang never generates calls to ___paritysi2, ___paritydi2,
>> ___cmpdi2,
>> >> or
>> >> >>
>> >> >> > ___ucmpdi2 on X86 so its not clear the performance of this
>> matters at
>> >> >> all.
>> >> >>
>> >> >>
>> >> >>
>> >> >> So you can safely remove them for X86 and all the other targets
>> where
>> >> such
>> >> >>
>> >> >> unoptimized code is never called!
>> >> >>
>> >> >> But fix these routines for targets where they are called.
>> >> >>
>> >> >>
>> >> >>
>> >> >> The statement does NOT make any exceptions, and it does not say
>> >> >>
>> >> >> | ships unoptimized routines the compiler never calls
>> >> >>
>> >> >> but
>> >> >>
>> >> >> | optimized target-independent implementations
>> >> >>
>> >> >>
>> >> >>
>> >> >> Stefan
>> >> >>
>> >> >>
>> >> >>
>> >> >> BTW: do builtins like __builtin_*parity* exist?
>> >> >>
>> >> >> If yes: do they generate the same bad code?
>> >> >>
>> >> >>
>> >> >>
>> >> >> > On Sun, Sep 6, 2020 at 12:31 PM Stefan Kanthak via cfe-dev <
>> >> >>
>> >> >> > cfe-dev at lists.llvm.org> wrote:
>> >> >>
>> >> >> >
>> >> >>
>> >> >> >> <https://compiler-rt.llvm.org/index.html> boasts:
>> >> >>
>> >> >> >>
>> >> >>
>> >> >> >> | The builtins library provides optimized implementations of this
>> >> >>
>> >> >> >> | and other low-level routines, either in target-independent C
>> form,
>> >> >>
>> >> >> >> | or as a heavily-optimized assembly.
>> >> >>
>> >> >> >>
>> >> >>
>> >> >> >> Really?
>> >> >>
>> >> >> >>
>> >> >>
>> >> >> >> Left: inperformant code shipped in # Right: slightly improved
>> >> code,
>> >> >>
>> >> >> >> clang_rt.builtins-* # which the
>> optimiser
>> >> >> REALLY
>> >> >>
>> >> >> >> # should have
>> generated
>> >> >>
>> >> >> >>
>> >> >>
>> >> >> >> ___cmpdi2:
>> >> >>
>> >> >> >> mov ecx, [esp+16] # mov ecx,
>> [esp+16]
>> >> >>
>> >> >> >> xor eax, eax # xor eax, eax
>> >> >>
>> >> >> >> cmp [esp+8], ecx # cmp ecx,
>> [esp+8]
>> >> >>
>> >> >> >> jl @f # jg @f
>> >> >>
>> >> >> >> mov eax, 2 # mov eax, 2
>> >> >>
>> >> >> >> jg @f # jl @f
>> >> >>
>> >> >> >> mov ecx, [esp+4] #
>> >> >>
>> >> >> >> mov edx, [esp+12] # mov ecx,
>> [esp+12]
>> >> >>
>> >> >> >> mov eax, 0 # xor eax, eax
>> >> >>
>> >> >> >> cmp ecx, edx # cmp ecx,
>> [esp+4]
>> >> >>
>> >> >> >> jb @f # ja @f
>> >> >>
>> >> >> >> cmp edx, ecx #
>> >> >>
>> >> >> >> mov eax, 1 #
>> >> >>
>> >> >> >> adc eax, 0 # adc eax, 1
>> >> >>
>> >> >> >> @@: # @@:
>> >> >>
>> >> >> >> ret # ret
>> >> >>
>> >> >> >>
>> >> >>
>> >> >> >> # 3 instructions less, 10
>> bytes
>> >> >> saved
>> >> >>
>> >> >> >>
>> >> >>
>> >> >> >> ___ucmpdi2:
>> >> >>
>> >> >> >> mov ecx, [esp+16] # mov ecx,
>> [esp+16]
>> >> >>
>> >> >> >> xor eax, eax # xor eax, eax
>> >> >>
>> >> >> >> cmp [esp+8], ecx # cmp ecx,
>> [esp+8]
>> >> >>
>> >> >> >> jb @f # ja @f
>> >> >>
>> >> >> >> mov eax, 2 # mov eax, 2
>> >> >>
>> >> >> >> ja @f # jb @f
>> >> >>
>> >> >> >> mov ecx, [esp+4] #
>> >> >>
>> >> >> >> mov edx, [esp+12] # mov ecx,
>> [esp+12]
>> >> >>
>> >> >> >> mov eax, 0 # xor eax, eax
>> >> >>
>> >> >> >> cmp ecx, edx # cmp ecx,
>> [esp+4]
>> >> >>
>> >> >> >> jb @f # ja @f
>> >> >>
>> >> >> >> cmp edx, ecx #
>> >> >>
>> >> >> >> mov eax, 1 #
>> >> >>
>> >> >> >> adc eax, 0 # adc eax, 1
>> >> >>
>> >> >> >> @@: # @@:
>> >> >>
>> >> >> >> ret # ret
>> >> >>
>> >> >> >>
>> >> >>
>> >> >> >> # 3 instructions less, 10
>> bytes
>> >> >> saved
>> >> >>
>> >> >> >>
>> >> >>
>> >> >> >>
>> >> >>
>> >> >> >> Now properly written code, of course branch-free, faster and
>> shorter:
>> >> >>
>> >> >> >>
>> >> >>
>> >> >> >> # Copyright (C) 2004-2020, Stefan Kanthak <
>> stefan.kanthak at nexgo.de>
>> >> >>
>> >> >> >>
>> >> >>
>> >> >> >> ___cmpdi2:
>> >> >>
>> >> >> >> mov ecx, [esp+4]
>> >> >>
>> >> >> >> mov edx, [esp+12]
>> >> >>
>> >> >> >> cmp ecx, edx
>> >> >>
>> >> >> >> mov eax, [esp+8]
>> >> >>
>> >> >> >> sbb eax, [esp+16]
>> >> >>
>> >> >> >> setl ah
>> >> >>
>> >> >> >> cmp edx, ecx
>> >> >>
>> >> >> >> mov edx, [esp+16]
>> >> >>
>> >> >> >> sbb edx, [esp+8]
>> >> >>
>> >> >> >> setl al
>> >> >>
>> >> >> >> sub al, ah
>> >> >>
>> >> >> >> movsx eax, al
>> >> >>
>> >> >> >> inc eax
>> >> >>
>> >> >> >> ret
>> >> >>
>> >> >> >>
>> >> >>
>> >> >> >> ___ucmpdi2:
>> >> >>
>> >> >> >> mov ecx, [esp+4]
>> >> >>
>> >> >> >> mov edx, [esp+12]
>> >> >>
>> >> >> >> cmp ecx, edx
>> >> >>
>> >> >> >> mov eax, [esp+8]
>> >> >>
>> >> >> >> sbb eax, [esp+16]
>> >> >>
>> >> >> >> sbb eax, eax
>> >> >>
>> >> >> >> cmp edx, ecx
>> >> >>
>> >> >> >> mov edx, [esp+16]
>> >> >>
>> >> >> >> sbb edx, [esp+8]
>> >> >>
>> >> >> >> adc eax, 1
>> >> >>
>> >> >> >> ret
>> >> >>
>> >> >> >>
>> >> >>
>> >> >> >>
>> >> >>
>> >> >> >> AGAIN:
>> >> >>
>> >> >> >> Remove every occurance of the word "optimized" on the above web
>> page.
>> >> >>
>> >> >> >>
>> >> >>
>> >> >> >> 'nuff said
>> >> >>
>> >> >> >> Stefan
>> >> >>
>> >> >> >> _______________________________________________
>> >> >>
>> >> >> >> cfe-dev mailing list
>> >> >>
>> >> >> >> cfe-dev at lists.llvm.org
>> >> >>
>> >> >> >> https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>> >> >>
>> >> >> >>
>> >> >>
>> >> >>
>> >> >
>> >> > --
>> >> > ~Craig
>> >> >
>> >>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20200909/90691d3a/attachment-0001.html>
More information about the cfe-dev
mailing list