go ``` cmd/compile: 优化 bits.OnesCount(x) == 1 ```

vjhs03f7  于 5个月前  发布在  Go
关注(0)|答案(7)|浏览(66)

It'd be nice for the compiler to be able to optimize bits.OnesCount(x) == 1 to x&(x-1) != 0 && x != 0 .
This is a bit tricky, because by the time we get to the rewrite rules, there's already a branch to check cpu feature availability.
If we figure this out, there might be other math/bits function result comparisons we want to optimize.
Implementation ideas welcome.

xam8gpfp

xam8gpfp1#

https://golang.org/cl/229127提到了这个问题:cmd/compile: use cheaper implementation of oneBit

qrjkbowd

qrjkbowd2#

我猜你不喜欢在编译器达到SSA之前做这件事?可能成本大于收益,并且会干扰早期阶段?

kmb7vmvb

kmb7vmvb3#

成本超过了收益,并且在早期阶段造成了混乱?
没错。

carvr3hs

carvr3hs4#

https://golang.org/cl/229197提到了这个问题:cmd/compile: use cheaper implementation of oneBit

pu82cl6c

pu82cl6c5#

作为附带说明,至少在GOAMD64=v2及以上版本中,没有CPU标志检查,因此我们得到了以下代码:

XORL	CX, CX
POPCNTQ	AX, CX
CMPQ	CX, $1
SETEQ	AL

没有调用math/bits.OnesCount(SB)
为了完整性,建议的替换模式x&(x-1) != 0 && x != 0被编译为:

LEAQ	-1(AX), CX
TESTQ	CX, AX
JEQ	17
TESTQ	AX, AX
SETNE	CL
JMP	19
XORL	CX, CX
MOVL	CX, AX

在Go tip上进行了测试(嗯,不是最新的一个,但足够接近:fad67f8)。

gudnpqoy

gudnpqoy6#

替换后的编译代码中不应该有任何跳转。我们肯定遗漏了一条或三条重写规则。

6mw9ycah

6mw9ycah7#

好的,抱歉再次提出这个问题,但我正在盯着最初提出的替换方案,它看起来并不完全正确。
也许我计算出了一些错误。
或许它应该像这样?

- ((x&(x-1)) != 0) && x != 0
+ ((x&(x-1)) == 0) && x != 0

考虑到这一点,这里是与不同编译器输出的比较。
Clang ( https://godbolt.org/z/o9PzM49TG ):

lea     eax, [rdi - 1]
        test    edi, eax
        sete    cl
        test    edi, edi
        setne   al
        and     al, cl
        ret

GCC:

leaeax,[rdi-1]
testeax,edi
seteal
testedi,edi
setnedl
andeax,edx
ret

Go ( https://godbolt.org/z/nfKjKe93a ):

LEAQ    -1(AX),CX
TESTQ   CX,AX
JEQ     f_pc17
TESTQ   AX,AX
SETNECL
JMPf_pc19
f_pc17:
XORL    CX,CX
f_pc19:
MOVL    CX,AX
RET

看起来Go也应该能够在这里移除一些分支。

相关问题