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

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): 全ビット反転
  • 要するに２の補数を取っている
• 正か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）。