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

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)
  ...

条件分岐がないコードを出力してくる。 一見何しているのかわからなかったので、符号付き4ビット整数で考えてみる：

• 引数が負の場合（例： 引数＝変数0＝-5=1011b、ブラケット内は現在のスタック）：
  • shr_s [-5, -5, 31] (=> 1111b = -1): 算術右シフトで、符号ビットで埋めた値 -1 が得られる
  • tee 1 [-5, -1] ローカル変数に格納で、スタックトップを変数1に格納（値は取り除かない）
  • add [-5, -1] (=> 1010b = -6): 加算、引数-1
  • xor [-6, -1] (=> 0101b = 5): 排他的論理和によって、全ビット反転
  • 要するに２の補数を取っている
• 正か0の場合（例： 引数＝変数0＝5）：
  • shr_s [5, 5, 31] (=> 0): 0
  • tee 1 [-5, 0]: 変化なし
  • add [5, 0] (=> 5): 変化なし
  • xor [5, 0] (=> 5): 変化なし
  • 引数の値がそのまま得られる

算術右シフトで負の場合は-1を、正または0の場合は0を得ることで、条件分岐をせずに済むようにしている。 出力されるコードが多少長くなってもそのほうがパフォーマンスがいいということなんですかね。

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）。