整数の絶対値を得るビットトリック

2020-12-19

WASMで負の数を得る命令ってどうやるんだろうか?とC言語からコンパイルしてみたら、条件分岐のないイカしたビット操作のコードを出力してきた。

C言語で絶対値を得るコード:

#include <emscripten/emscripten.h>

#ifdef __cplusplus
extern "C" {
#endif

int EMSCRIPTEN_KEEPALIVE abs(int x) {
if (x >= 0)
return x;
else
return -x;
}

#ifdef __cplusplus
}
#endif

を書いて、EmscriptenでWASMにコンパイルして出力結果を見てみると:

$ emcc -s WASM=1 -s NO_EXIT_RUNTIME=1 -O1 neg.c && wasm2wat a.out.wasm
(module
...
(func (;1;) (type 1) (param i32) (result i32)
(local i32)
local.get 0
local.get 0
i32.const 31
i32.shr_s
local.tee 1
i32.add
local.get 1
i32.xor)
...

条件分岐がないコードを出力してくる。 一見何しているのかわからなかったので読み解いてみた。

  • 引数が負の場合(例: -5=1011b):
    • shr_s -5, 31 (= 1111b = -1): 符号ビットで埋めた値 -1 が得られる
    • tee でスタックトップをローカルに格納、しかし取り除かない
    • add -5, -1 (= 1010b = -6): 引数-1
    • xor -6, -1 (= 0101b = 5): 全ビット反転
    • 要するに2の補数を取っている
  • 正か0の場合(例: 5):
    • shr_s 5, 31 (= 0): 0
    • add 5, 0 (= 5): 変化なし
    • xor 5, 0 (= 5): 変化なし
    • 引数の値がそのまま得られる

出力されるコードが多少長くなっても条件分岐をさせないほうがパフォーマンスがいいということなんですかね。

x86の場合

試しにMacOS/x86のgcc(Clang)でコンパイルしてみたらまたちょっと違って、negl で符号反転した値を作って cmovl という条件付きムーブ命令で選択するコードが出力された:

$ gcc -S -O1 -fno-asynchronous-unwind-tables neg.c && cat neg.s
_abs:
pushq %rbp
movq %rsp, %rbp
movl %edi, %eax # %ediが引数、それを%eaxにコピー
negl %eax # 符号反転してみて
cmovll %edi, %eax # CMOVL(Move if less): 負だったら元の値を選択
popq %rbp
retq
$ gcc -v
Apple clang version 12.0.0 (clang-1200.0.32.27)
Target: x86_64-apple-darwin19.6.0

gcc/UbuntuではWASM版と同じような方法だった(xor を先に行って、add の代わりに sub)。