Xbyak - x86, x64 JIT assembler -
x86の究極の最適化手法?
What's this?
Xbyak(カイビャック)はx86(IA32), x64(AMD64, x86-64)のマシン語命令を生成するC++のクラスライブラリです.
プログラム実行時に動的にアセンブルすることが可能なため,
柔軟な最適化(動的コード生成)が可能となります(利用シーン:
量子化の高速化,
式の計算).
暗号ライブラリに使って高速な実装をしてみた(
very fast etaT pairing for Core 2 Duo)
Download
Feature
- ヘッダファイルオンリー
- xbyak.hをインクルードするだけですぐ利用することができます(32bit, 64bit両対応).
- Windows Xp(32bit, 64bit), Vista/Linux(32bit, 64bit)/Intel Mac対応
- VC++2005 Express Edition, VS2008 Pro, gcc 4.xなどで動作確認をしています.
#gccではand, or, xorなどを演算子として解釈してしまうため, -fno-operator-namesオプションを追加してコンパイルしてください.
- 外部ライブラリやツール不要
- Makefileやプロジェクトファイルなどの設定に煩わされることもありません.
- コンパクト
- MMX/MMX2/SSE/SSE2/SSE3/SSSE3/SSE4サポート(現在FPU非サポート)でわずか2000行
- 極力少ないバイト長で出力
- たとえばcmp(eax, 5);と書けばNASMでcmp eax, byte 5と書いたのと同じです.
License
How to use
xbyak.h, xbyak_mnemonic.h, xbyak_bin2hex.hを同一のディレクトリ(たとえばxbyak)に入れて,
コンパイル時にはそのディレクトリを指定します.
Xbyak::CodeGeneratorクラスを継承し, そのクラスメソッド内でx86, x64アセンブラを
記述します.
そのメソッドを呼び出した後, getCode()メソッドを呼び出し,
その戻り値を自分が使いたい関数ポインタに変換して利用します.
アセンブルエラーは例外により通知されます.
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]
という形で指定します.
サイズを指定する必要がない限りptrを使えばよいです.
セレクタはサポートしていません.
dword, word, byteはクラス変数ですので, typedefなどしないようご注意ください.
NASM Xbyak
mov eax, [ebx+ecx] --> mov (eax, ptr[ebx+ecx]);
test byte [esp], 4 --> test (byte [esp], 4);
ラベル
L(文字列);
で定義します.
ジャンプするときはその文字列を指定します.
後方参照も可能ですが, 相対アドレスが8ビットに収まらない場合はT_NEARをつけないと実行時に例外が発生します.
hasUndefinedLabel()を呼び出して真ならジャンプ先が存在しないことを示します. コードを見直してください.
L("L1");
jmp ("L1");
jmp ("L2");
...
少しの命令の場合.
...
L("L2");
jmp ("L3", T_NEAR);
...
沢山の命令がある場合
...
L("L3");
コードサイズ
コードサイズの最大値のデフォルトは2048(バイト)です.
それより大きいコードを生成したい場合はCodeGenerator()の引き数に設定してください.
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を用いた量子化の処理時間の比較
| 種別 | 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を使ってみました.
# spritの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命令はほぼ全て実装されていますが, FPU, 3D Now!命令や,
一部の特殊な命令は現時点では実装されていません.
History
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 x86版β公開
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:2008/07/05
御意見は光成滋生<herumi@nifty.com>までお願いします