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

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

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标志检查,因此我们得到了以下代码:

  1. XORL CX, CX
  2. POPCNTQ AX, CX
  3. CMPQ CX, $1
  4. SETEQ AL

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

  1. LEAQ -1(AX), CX
  2. TESTQ CX, AX
  3. JEQ 17
  4. TESTQ AX, AX
  5. SETNE CL
  6. JMP 19
  7. XORL CX, CX
  8. MOVL CX, AX

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

展开查看全部
gudnpqoy

gudnpqoy6#

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

6mw9ycah

6mw9ycah7#

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

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

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

  1. lea eax, [rdi - 1]
  2. test edi, eax
  3. sete cl
  4. test edi, edi
  5. setne al
  6. and al, cl
  7. ret

GCC:

  1. leaeax,[rdi-1]
  2. testeax,edi
  3. seteal
  4. testedi,edi
  5. setnedl
  6. andeax,edx
  7. ret

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

  1. LEAQ -1(AX),CX
  2. TESTQ CX,AX
  3. JEQ f_pc17
  4. TESTQ AX,AX
  5. SETNECL
  6. JMPf_pc19
  7. f_pc17:
  8. XORL CX,CX
  9. f_pc19:
  10. MOVL CX,AX
  11. RET

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

展开查看全部

相关问题