Xbyak - x86, x64 JIT assembler -

English
x86の究極の最適化手法?
What's this?
Xbyak(カイビャック)はx86(IA32), x64(AMD64, x86-64)のマシン語命令を生成するC++のクラスライブラリです. プログラム実行時に動的にアセンブルすることが可能なため, 柔軟な最適化(動的コード生成)が可能となります(利用シーン:量子化の高速化, 式の計算).
暗号ライブラリに使って高速な実装をしてみた(High-Speed Software Implementation of the Optimal Ate Pairing over Barreto-Naehrig Curves)
Download
https://github.com/herumi/xbyak
説明書
Feature
ヘッダファイルオンリー
xbyak.hをインクルードするだけですぐ利用することができます(32bit, 64bit両対応).
Windows Xp(32bit, 64bit), Vista/Linux(32bit, 64bit)/Intel Mac対応
VC++2005 Express Edition, VS2008 Pro, VC2010, gcc 4.xなどで動作確認をしています.
#gccではand, or, xorなどを演算子として解釈してしまうため, -fno-operator-namesオプションを追加してコンパイルしてください.
あるいはXBYAK_NO_OP_NAMESを定義するとand_, or_, xor_などを使うようになります.
外部ライブラリやツール不要
Makefileやプロジェクトファイルなどの設定に煩わされることもありません.
コンパクト
MMX/MMX2/SSE/SSE2/SSE3/SSSE3/SSE4/FPU/AVX/FMAサポート(FPUは80bit浮動小数は非サポート)で3000行程度
極力少ないバイト長で出力
たとえばcmp(eax, 5);と書けばNASMでcmp eax, byte 5と書いたのと同じです.
License
修正BSDライセンスに従います(The BSD 3-Clause License).
How to use
xbyak.h, xbyak_mnemonic.h, xbyak_bin2hex.hを同一のディレクトリ(たとえばxbyak)に入れて, コンパイル時にはそのディレクトリを指定します.
Xbyak::CodeGeneratorクラスを継承し, そのクラスメソッド内でx86, x64アセンブラを 記述します. そのメソッドを呼び出した後, getCode()メソッドを呼び出し, その戻り値を自分が使いたい関数ポインタに変換して利用します. アセンブルエラーは例外により通知されます.
New Feature
AutoGrowモード追加
これはメモリ伸長を動的に行うモードです. 今まではXbyak::CodeGenerator()に渡したメモリサイズを超えると例外が発生して いましたが,このモードでは内部でメモリを再確保して伸長します. ただし,getCode()を呼び出す前にジャンプ命令のアドレス解決をするためにready() 関数を呼ぶ必要があります.
次のように使います.
 struct Code : Xbyak::CodeGenerator {
   Code()
     : Xbyak::CodeGenerator(<デフォルトメモリサイズ>, Xbyak::AutoGrow)
   {
      ...
   }
 };
 Code c;
 c.ready(); // この呼び出しを忘れてはいけない
注意1. ready()を呼んで確定するまではgetCurr()で得たポインタは無効化されている 可能性があります.getSize()でoffsetを保持しておきready()のあとにgetCode()を 呼び出してからgetCode() + offsetで新しいポインタを取得してください.
注意2. AutoGrowモードでは64bitモードの相対アドレッシング[rip]は非サポートです.
Syntax
基本的にNASMの命令で括弧をつければよいです.
NASM              Xbyak
mov eax, ebx  --> mov(eax, ebx);
inc ecx       --> inc(ecx);
ret           --> ret();
アドレッシング
(ptr|dword|word|byte) [base + index * (1|2|4|8) + displacement]
                      [rip + 32bit disp] ; x64 only
という形で指定します. サイズを指定する必要がない限りptrを使えばよいです. セレクタはサポートしていません.
dword, word, byteはクラス変数ですので, typedefなどしないようご注意ください.
NASM                   Xbyak
mov eax, [ebx+ecx] --> mov (eax, ptr[ebx+ecx]);
test byte [esp], 4 --> test (byte [esp], 4);
AVX
大抵の3オペランド形式の命令はデスティネーションを省略した形で呼び出すことができます.
FMAについては簡略表記を導入するか検討中です(アイデア募集中).
vaddps(xmm1, xmm2, xmm3); // xmm1 <- xmm2 + xmm3
vaddps(xmm2, xmm3); // xmm2 <- xmm2 + xmm3

vfmadd231pd(xmm1, xmm2, xmm3); // xmm1 <- (xmm2 * xmm3) + xmm1
ラベル
L(文字列);
で定義します. ジャンプするときはその文字列を指定します. 後方参照も可能ですが, 相対アドレスが8ビットに収まらない場合はT_NEARをつけないと実行時に例外が発生します.
hasUndefinedLabel()を呼び出して真ならジャンプ先が存在しないことを示します. コードを見直してください.
L("L1");
    jmp ("L1");

    jmp ("L2");
    ...
    少しの命令の場合.
    ...
L("L2");

    jmp ("L3", T_NEAR);
    ...
    沢山の命令がある場合
    ...
L("L3");
MASMライクな@@, @f, @bを使えます.
  L("@@"); // <A>
  jmp("@b"); // jmp to <A>

  jmp("@f"); // jmp to <B>

  L("@@"); // <B>
  jmp("@b"); // jmp to <B>
ピリオドで始まるラベルをinLocalLabel(), outLocalLabel()で挟むことで局所化できます. inLocalLabel(), outLocalLabel()は入れ子にすることができます.
void func1()
{
    inLocalLabel();
    L(".lp"); // <A> ; ローカルラベル
    ...
    jmp(".lp"); // jmpt to <A>
   L("aaa"); // グローバルラベル
    outLocalLabel();
}

void func2()
{
    L(".lp"); // <B> ; ローカルラベル
    func1();
    jmp(".lp"); // jmp to <B>
}

上記サンプルではinLocalLabel(), outLocalLabel()が無いと, ".lp"ラベルの二重定義エラーになります.

コードサイズの最大値のデフォルトは2048(バイト)です. それより大きいコードを生成したい場合はCodeGenerator()の引き数に設定してください.
@param maxSize [in] コード生成最大サイズ(デフォルト2048byte)
@param userPtr [in] ユーザ指定メモリ

CodeGenerator(size_t maxSize = DEFAULT_MAX_CODE_SIZE, void *userPtr = 0);
SAMPLE
てっとり早く理解するために例をいくつか.
サンプル1
足し算関数の作成.
#include <stdio.h>
#include "xbyak/xbyak.h"

struct AddFunc : public Xbyak::CodeGenerator {
    AddFunc(int y)
    {
        mov(eax, ptr[esp+4]);
        add(eax, y);
        ret();
    }
};

int main()
{
    AddFunc a(3);
    int (*add3)(int) = (int (*)(int))a.getCode();
    printf("3 + 2 = %d\n", add3(2));
}
関数ポインタadd3が指す中身は
    mov    eax, dword ptr [esp+4]
    add    eax, 3
    ret
となります.
サンプル2
分岐の使い方.
/*!
    1からnまでの和を求める
*/
class Sample : public Xbyak::CodeGenerator {
public:
    Sample(int n)
    {
        mov(ecx, n); // -- (A)
        xor(eax, eax); // sum
        test(ecx, ecx);
        jbe("exit");
        xor(edx, edx); // i
    L("lp");
        add(eax, edx);
        inc(edx);
        cmp(edx, ecx);
        jbe("lp");
    L("exit");
        ret();
    }
};
int main(int argc, char *argv[])
{
    int n = argc < 2 ? 100 : atoi(argv[1]);
    try {
        Sample s(n);
        printf("1 + ... + %d = %d\n", n, ((int (*)())s.getCode())());
    } catch (Xbyak::Error err) {
        printf("ERR:%s(%d)\n", Xbyak::ConvertErrorToString(err), err);
    } catch (...) {
        printf("unkwon error\n");
    }
    return 0;
}
Sample()のコンストラクタ内で1からnまでを足す関数を生成します. (A)の部分が呼ばれたときはnは確定しているのでアセンブルできます. それ以外は普通のアセンブラを使うのと同じです.
Introduction to Xbyak
結局何ができるのか
文法はだいたい分かった. でも, 慣れない人には何に使うのかイメージしにくいかもしれません. だからもう少し実用的な例を出します. 以下はアセンブラの基本知識を若干仮定します. 全く知らない方は(こんなところ読まんと思うが)「x86アセンブリ言語入門」など参考にしてください.
まず, インラインアセンブラとは似て非なるものであることに注意してください. たとえば, インラインアセンブラで
func(int n)
{
    __asm {
        mov eax, n
    }
}
と書くと標準では自動的にスタックフレームを生成し,
    push    ebp
    mov     ebp, esp
    mov     eax, [ebp+8]
というコードが生成されるでしょう(最適化オプションによって変わる可能性はあります). しかし, Xbyakが生成するコードはコンパイラとは独立なのでそのようなことはしません(できません). サンプル1のように, mov(eax, n);はその関数呼び出しがあった時点でのnの値(たとえば3)を用いて, mov eax, 3という命令を生成します. スタックフレームなどは生成されたコードがどうユーザから呼び出されるかを考慮して, すべて自分で記述する必要があります*.
ま, それは外部アセンブラを使った場合も同じですが.
逆に, インラインアセンブラや外部アセンブラを使った通常のプログラミングでは, 確定していないnに対してmov eax, nのようなことはできません. 必ず, nのアドレスを読んでから, そのアドレスにある値を読むという二段構えになります. つまり, Xbyakの主要な目的はコンパイル時には未確定だが実行時には確定している部分において, 一層の高速化をしたい場合にあります.
パッケージに付属するquantize.cppを例に説明しましょう. JPEGやMPEGのエンコードには量子化という処理があります. これはある配列を予め決められた量子化テーブルという配列の値で割り算をする操作です.
void quantize(uint32 dest[64],
              const uint32 src[64], const uint32 qTbl[64])
{
    for (int i = 0; i < N; i++) {
        dest[i] = src[i] / qTbl[i];
    }
}
たとえばJPEGではエンコード中はqTbl[]は固定なのですが, その内容はエンコード時に指定する画質パラメータに依存して決まります.
さて, 割り算は足し算や掛け算に比べてはるかに重たい処理です(演算コスト比はdiv:mul:add=30〜40:3:1ぐらい). したがってコンパイラは固定の数で割る場合は割り算命令を使わないような最適化を行います. たとえば10で割る場合VC6++では次のようなコードを生成します.
// C
uint32 func(uint32 n)
{
    return n / 10;
}

// asm
    mov    eax, cccccccdH
    mul    DWORD PTR _n$[esp-4]
    mov    eax, edx
    shr    eax, 3
    ret
これはコンパイル時に割る数が決まっているからこそできる最適化技術であり, 上記quantize()内部では不可能です.
ならば数値が確定してから上記コンパイラが行う最適化と同等なことを, 実行中にさせましょう. そのためにJITアセンブラXbyakを使います.
quantize.cpp内のQuantize::udiv()は与えられた数に対して上記のような最適化された割り算コードを生成する関数です. そしてQuantizeのコンストラクタで与えられたqTblに対して上記quantize()と同じ処理をするコードを生成します.
擬似的に画質パラメータを変更して量子化した場合の処理時間を測定しました. 環境はPentium D 2.8GHz + VC2005 Express Editionです(表中の単位は1000万回ループにおける秒数).
通常の量子化とXbyakを用いた量子化の処理時間の比較
quantization speed
種別 q = 1(低画質) q = 10 q = 50 q = 100(高画質)
VC2005 8.0 8.0 8.0 8.0
Xbyak 1.6 0.8 0.5 0.5
VC2005では画質パラメータに関わらず8.0秒で一定です. 一つの量子化処理あたり8.0 * 2.8 * 109 / 64 / 107 = 35クロックかかっています. 常に割り算をするためです. これに対してXbyakでは高画質になるほど処理速度が上がっています(最大16倍速度). これは高画質では量子化単位が小さくなり(殆どすべて1で割る), 割り算処理を行わなくてすむからです. 実際, 生成コードをみると分かりますがq = 100ではほぼ単なるメモリコピーコードに変換されます.
; q = 1のときに実行時生成されたコード
    push        esi
    push        edi
    mov         edi,dword ptr [esp+0Ch]
    mov         esi,dword ptr [esp+10h]
    mov         eax,dword ptr [esi]
    shr         eax,4
    mov         dword ptr [edi],eax      ; 16で割る
    mov         eax,dword ptr [esi+4]
    mov         edx,0BA2E8BA3h
    mul         eax,edx
    shr         edx,3                    ; 11で割る
    ...

; q = 100のときに実行時生成されたコード
     push        esi
     push        edi
     mov         edi,dword ptr [esp+0Ch]
     mov         esi,dword ptr [esp+10h]
     mov         eax,dword ptr [esi]
     mov         dword ptr [edi],eax
     mov         eax,dword ptr [esi+4]    ; 1で割る
     mov         dword ptr [edi+4],eax
     mov         eax,dword ptr [esi+8]
     mov         dword ptr [edi+8],eax    ; 1で割る
     mov         eax,dword ptr [esi+0Ch]
     mov         dword ptr [edi+0Ch],eax
     ...
ま, 現実問題として量子化はSSE2をうまく適用したり, もっと別な最適化をしたりしますが, JITアセンブラを使う動機の一つの分かりやすい例ではないかと思います.
式の計算
もう一つ, 簡単な多項式の計算プログラムを作ってみました(calc.cpp).
変態的と言われる boost::spirit を使いました. 四則演算のみ, またSSE2レジスタを使い回すことにしたのでスタックは最大8個というしょぼいものですが, 最小限の機能はあります.
Xbyak::CodeGeneratorを継承したFuncGenには各定数, 変数x, 四則演算に応じたアクションをメンバ関数として作っておきます. メソッドの引き数はspiritの仕様に合わせます. こんな感じ.
    void genPush(double n)
    {
        if (constTblPos_ == MAX_CONST_NUM) throw;
        constTbl_[constTblPos_] = static_cast<float>(n);
        if (regIdx_ == 7) throw;
        movss(Xbyak::Xmm(++regIdx_), ptr[edx+constTblPos_*sizeof(float)]);
        constTblPos_++;
    }
    void genSub(const char*, const char*)
    {
        subss(Xbyak::Xmm(regIdx_ - 1), Xbyak::Xmm(regIdx_)); regIdx_--;
    }
それからspiritを使って文法を定義します. アクションをグローバルな関数にしてもよかったのですが, ちょっとかっこつけるためにboost::bindを使ってみました.
# spiritのaction([]の中)は(Iterator first, Iterator last)を持つ関数オブジェクトである必要がある.
struct Grammar : public boost::spirit::grammar<Grammar> {
    FuncGen& f_;
    Grammar(FuncGen& f) : f_(f) { }
    template<typename ScannerT>
    struct definition {
        boost::spirit::rule<ScannerT> exp0, exp1, exp2, val;

        definition(const Grammar& self)
        {
            using namespace boost;
            using namespace boost::spirit;

            exp0 = exp1 >> *(('+' >> exp1)[bind(&FuncGen::genAdd, ref(self.f_), _1, _2)]
                           | ('-' >> exp1)[bind(&FuncGen::genSub, ref(self.f_), _1, _2)]);
            exp1 = exp2 >> *(('*' >> exp2)[bind(&FuncGen::genMul, ref(self.f_), _1, _2)]
                           | ('/' >> exp2)[bind(&FuncGen::genDiv, ref(self.f_), _1, _2)]);
            val = ch_p('x')[bind(&FuncGen::genX, ref(self.f_))];
            exp2 = real_p[bind(&FuncGen::genPush, ref(self.f_), _1)]
                 | val
                 | '(' >> exp0 >> ')';
        }
        const boost::spirit::rule<ScannerT>& start() const { return exp0; }
    };
};
これだけで終わり(コメント除くと100行程度)なんですから, boostはやっぱり偉大ですね(しかし, よくこんなものがコンパイルできるなあ).
後はループで回してテストしてます.
    void (*func)(float *ret, const float *x) = (void (*)(float *, const float*))funcGen.getCode();
    for (float x = 0; x < 10; x += 0.7f) {
        float y;
        func(&y, &x);
        printf("f(%f)=%f\n", x, y);
    }
で, たとえば"x+2*(x*x+3/x)"を入力するとそれを計算する次のような関数を実行時に作成してくれます. ま, -O0 JITコンパイラみたいなもんです.
    ; @param y [out] f(x)
    ; @param x [in] x
    ; void func(float *y, const float *x);

    mov         eax,dword ptr [esp+8]
    mov         edx,12FEA8h
    movss       xmm0,dword ptr [eax]
    movss       xmm1,dword ptr [edx]
    movss       xmm2,dword ptr [eax]
    movss       xmm3,dword ptr [eax]
    mulss       xmm2,xmm3
    movss       xmm3,dword ptr [edx+4]
    movss       xmm4,dword ptr [eax]
    divss       xmm3,xmm4
    addss       xmm2,xmm3
    mulss       xmm1,xmm2
    addss       xmm0,xmm1
    mov         eax,dword ptr [esp+4]
    movss       dword ptr [eax],xmm0
    ret
実行結果
>calc "x*x+3*x+5"
f(0.000000)=5.000000
f(0.700000)=7.590000
f(1.400000)=11.160000
f(2.100000)=15.709999
f(2.800000)=21.240000
f(3.500000)=27.750000
f(4.200000)=35.239998
f(4.900000)=43.709995
f(5.599999)=53.159992
f(6.299999)=63.589989
f(6.999999)=74.999985
f(7.699999)=87.389977
f(8.399999)=100.759972
f(9.099998)=115.109970
f(9.799998)=130.439957
Note
MMX/SSE命令はほぼ全て実装されていますが, 3D Now!命令や, FPUの一部の命令, 一部の特殊な命令は現時点では実装されていません.
History
2012/11/17 see readme.txt for the latest info.
2012/11/09 ver 3.70 and()をand_()にするためのマクロXBYAK_NO_OP_NAMESを追加(thanks to Mattias)
2012/11/01 ver 3.62 add fwait/fnwait/finit/fninit
2012/11/09 ver 3.70 XBYAK_NO_OP_NAMESマクロを追加
2012/05/03 ver 3.60 Allocatorのインタフェース変更
2012/03/23 ver 3.51 userPtrモードがバグったのを修正
2012/03/20 ver 3.50 AutoGrowモード追加
2011/11/09 ver 3.05 ripのsizeパラメータのバグ修正 / movsxdサポート
2011/08/15 ver 3.04 add(dword [ebp-8], 0xda);などにおけるimm8の扱いのバグ修正(thanks to lolcat)
2011/06/16 ver 3.03 Macのgcc上での__GNUC_PREREQがミスってたのを修正(thanks to t_teruya)
2011/04/28 ver 3.02 Macのgcc上ではxgetbvをdisable
2011/03/24 ver 3.01 些細なtypo修正
2011/03/23 ver 3.00 vcmpeqpsなどのalias命令を追加
2011/02/16 ver 2.994 beta add vmovq for 32-bit mode(I forgot it)
2011/02/16 ver 2.993 beta remove cvtReg to avoid thread unsafe
2011/02/10 ver 2.992 beta fadd, fsubr, etc support st0 omitted parameter
2011/02/07 ver 2.991 beta fix pextrw reg, xmm, imm
2011/02/04 ver 2.99 beta support AVX
2010/12/08 ver 2.31 fix ptr [rip + 32bit offset], support rdtscp
2010/10/19 ver 2.30 support pclmulqdq, aesdec, aesdeclast, aesenc, aesenclast, aesimc, aeskeygenassist
2010/07/07 ver 2.29 fix call("label")
2010/06/20 ver 2.28 move some member functions to public
2010/06/01 ver 2.27 support encoding of mov(reg64, imm) like yasm(not nasm)
2010/05/24 ver 2.26 fix sub rsp, 1000
2010/04/26 ver 2.25 jc/jnc忘れてた…
2010/04/16 ver 2.24 change the prototype of rewrite() method
2010/04/15 ver 2.23 fix align() and xbyak_util.h for Mac
2010/02/16 ver 2.22 fix inLocalLabel()/outLocalLabel()
2009/12/09 ver 2.21 support cygwin(gcc 4.3)
2009/11/28 ver 2.20 FPUの一部命令サポート
2009/06/25 ver 2.11 64bitモードでの mov(qword[rax], imm); 修正(thanks to Martinさん)
2009/03/10 ver 2.10 jmp/call reg64の冗長なREG.W削除
2009/02/24 ver 2.09 movq reg64, mmx/xmm; movq mmx/xmm, reg64追加
2009/02/13 ver 2.08 movd(xmm7, dword[eax])が0x66を落とすバグ修正(thanks to Gabestさん)
2008/12/30 ver 2.07 call()の相対アドレスが8bit以下のときのバグ修正(thanks to katoさん)
2008/09/18 ver 2.06 @@, @f, @bとラベルの局所化機能追加(thanks to nobu-qさん)
2008/09/18 ver 2.05 ptr [rip + 32bit offset]サポート(thanks to 団子厨(Dango-Chu)さん)
2008/06/06 ver 2.04 mov(ptr[eax],1);などのエラー強化
2008/06/02 ver 2.03 ユーザ定義メモリインタフェースサポート
2008/05/26 ver 2.02 protect()(on Linux)で不正な設定になることがあるのを修正(thanks to sinichiro_hさん)
2008/04/30 ver 2.01 cmpxchg16b, cdqe追加
2008/04/29 ver 2.0 x86/x64-64版公開
2008/04/25 ver 1.9 x64版β公開
2008/04/14 ver 1.11 コード整理
2008/03/27 ver 1.10 bsf/bsr追加(忘れていた)
2008/02/14 ver 1.09 mov(eax, 1234);の出力コード修正
2007/11/03 ver 1.07 SSSE3/SSE4に対応
2007/09/25 ver 1.06 call((int)関数ポインタ); jmp((int)関数ポインタ);のサポート
2007/08/04 ver 1.05 細かい修正 Intel Macでの動作確認
2007/02/04 後方ジャンプで相対アドレスが8bitに収まらないときのバグ修正
2007/01/23 boost::spiritを使った式の計算サンプル追加
2007/01/21 [disp]の形のアドレス生成のバグ修正
2007/01/20 解説追加
2007/01/17 webページ作成, quantize.cppサンプル追加
2007/01/04 公開開始
1st:2007/1/17, last update:2016/08/29

御意見は光成滋生<herumi@nifty.com>までお願いします