最適化の為のアセンブラ

やっぱりアセンブラが一番！

処理速度が必要なクリティカルなコードを作るためにアセンブラは未だに必需品です。
どんなにコンパイラが進化しようとマシンの真の性能を引き出すのはアセンブラ以外にはあり得ません(ただし大規模のプログラムとなると性能を引き出す以前に作成不可能な気もするけど)。
ということでアセンブラの勉強です。対象CPUは一番メジャーであると考えられる Intel Pentiumです。

開発環境はVisualC++5とします。 基本的にCで開発して処理速度の必要な部分をインラインアセンブラを使うことを前提にします(C/C++は理解しているのが前提とします)。 理由はインラインアセンブラだとコンパイルが容易だし、関数の引数の受け渡しが楽だからです。 (その簡単さが仇になることもありますが)

とりあえず最初にx86CPUの基礎から。 まずCPUを使うにはレジスタの種類とアドレッシングモード(メモリにアクセスする方法)と 命令を知っていなければ話になりません。 といってもよく使うのは非常に少ないので簡単に覚えられます。

レジスタについて

汎用レジスタ
eax/ax/ah/al	アキュムレータ
ebx/bx/bh/bl	ベース・レジスタ
ecx/cx/ch/cl	カウンタ・レジスタ	ループをカウントするのに使う、事もある
edx/dx/dh/dl	データ・レジスタ
アドレス指定用レジスタ
esp/sp	スタック・ポインタ	スタックの頭を示す
ebp/bp	ベース・ポインタ	普通Cだとコンパイラがスタックフレームを形成するときに使う
esi/si	ソース・インデックス	メモリの間接指定をするために使う(Cでいうポインタ)
edi/di	ディスティネーション・インデックス	メモリの間接指定をするために使う(Cでいうポインタ)


eax/ax/ah/alとあるのは「eaxは32bitを全部扱う」「axは下位16bitを扱う」「ahは下位16bitの中の上位8bitを扱う」「alは下位16bitの中の下位8bitを扱う」という意味です。
eaxに12345678hを代入するとaxは5678h、ahは56h、alは78hになります。
また、レジスタには一応それぞれの意味合いがあるのですが32bitになった時点で殆ど全てのレジスタが汎用化しています。ので意味は気にする必要はあまりありません。

アドレッシングモードについて

[eax]のようにするとEAXの指すアドレスに格納されている値を指定することになります。 いわゆる間接指定。Cでいう *eax です。
これさえ分かればバッチリです。
[eax+定数]とか[eax*2]とか[eax][ebx](←これは[eax+ebx]のこと)とか直ぐ理解できると思います。
なおeaxで書きましたが32bitレジスタならesp以外なら殆ど同様に使用可能です。

詳しいアドレッシングモードについては追々説明することにします。

命令

全部書くのはしんどいのでFPU命令は除いたよく使う命令を書いておきます。


Opcode	Operands	Clock cycles	Pairability
NOP		1	uv
MOV	r/m, r/m/i	1	uv
MOV	r/m, sr	1	np
MOV	sr, r/m	>= 2 b)	np
XCHG	(E)AX, r	2	np
XCHG	r,r	3	np
XCHG	r,m	>20	np
XLAT		1	np
PUSH	r/i	1	uv
POP	r	1	uv
PUSH	m	2	np
POP	m	3	np
PUSH	sr	1	np
POP	sr	>=3	np
PUSHF		4	np
POPF		6	np
PUSHA POPA		5	np
LAHF SAHF		2	np
MOVSX	r,r/m	3	np
MOVZX	r,r/m	3	np
LEA	r/m	1	np
LDS LES LFS LGS LSS	m	4	np
ADD SUB AND OR XOR	r,r/i	1	uv
ADD SUB AND OR XOR	r,m	2	uv
ADD SUB AND OR XOR	m,r/i	3	uv
CMP	r,r/i	1	uv
CMP	m,r/i	2	uv
TEST	r,r	1	uv
TEST	m,r	2	uv
TEST	r,i	1	※f
TEST	m,i	2	np
ADC SBB	r/m,r/m/i	1/3	u
INC DEC	r	1	uv
INC DEC	m	3	uv
NEG NOT	r/m	1/3	np
MUL IMUL	r/r16/m8/m16	11	np
MUL IMUL	他の組み合わせ	9	np
DIV	r8/r16/r32	17/25/41	np
IDIV	r8/r16/r32	22/30/46	np
CBW CWDE		3	np
CWD CDQ		2	np
SHR SHL SAR SAL	r,i	1	u
SHR SHL SAR SAL	m,i	3	u
SHR SHL SAR SAL	r/m,CL	4/5	np
ROR ROL RCR RCL	r/m,1	1/3	u
ROR ROL	r/m,i(!=1)	1/3	np
ROR ROL	r/m,CL	4/5	np
RCR RCL	r/m.i(!=1)	8/10	np
RCR RCL	r/m,CL	7/9	np
SHLD SHRD	r,i/CL	4	np
SHLD SHRD	m,i/CL	5	np
BT	r,r/i	4	np
BT	m,i	4	np
BT	m,r	9	np
BTR BTS BTC	r,r/i	7	np
BTR BTS BTC	m,i	8	np
BTR BTS BTC	m,r	14	np
BSF BSR	r,r/m	7-23	np
SETcc	r/m	1	np
JMP CALL	short/near	1	v
JMP CALL	far	>=3	np
条件JMP	short/near	1/4/5	v
CALL JMP	r/m	2	np
RETN		2	np
RETN	i	3	np
RETF		4	np
RETF	i	5	np
J(E)CXZ	short	5-10	np
LOOP	short	5-10	np
BOUND	r,m	8	np
CLC STC CMC CLS STD		2	np
CLI STI		6-7	np
LODS		2	np
REP LODS		7+3*n	np
STOS		3	np
REP STOS		10+n	np
MOVS		4	np
REP MOVSB		12+1.8*n	np
REP MOVSW		12+1.5*n	np
REP MOVSD		12+n	np
SCAS		4
REP(N)E SCAS		9+4*n
CMPS		5	np
REP(N)E CMPS		8+5*n	np
BSWAP		1	np

表の見方

Clock cycles	命令を終えるのに掛かる時間
Pairability	どのパイプラインで組み合わせるかを示します np 組み合わせ不可能 u Uパイプで組み合わせ可能 v Vパイプで組み合わせ可能 uv 両方のパイプで組み合わせ可能

※f	1byte instruction code + 4bytes data のときだけpairingできる

と、表を書きましたが最初は何のことだかサッパリだと思うので よく使う命令だけ分かりやすい形で書いてみました。

ニーモニック		動作
mov	a,b	;a=b
push	a	;aをstackに積む
pop	a	;stackから取り出してaに代入
lea	a,b	;実行アドレスのロード

算術演算命令
add	a,b	;a+=b
sub	a,b	;a-=b
mul	a	;eax*=a	(符号無し)
imul	a,b,c	;a=b*c	(符号有り)
div	a	;eax/=a	(符号無し)
idiv	a	;eax/=a	(符号有り)

cmp	a,b	;aとbの比較(内部で減算をしているだけ)

論理演算
not	a	;a=~a
and	a,b	;a&=b
or	a,b	;a|=b
xor	a,b	;a^=b
shl	a,b	;a<<=b (符号無し)
shr	a,b	;a>>=b (符号無し)
sal	a,b	;a<<=b (符号有り)
sar	a,b	;a>>=b (符号有り)

分岐
call	adress	;サブルーチンコール
jmp	adress	;ジャンプ


条件分岐
	符号無し	符号有り
a>b	ja(jnbe)	jg(jnle)
a>=b	jae(jnb)	jge(jnl)
a=b	je(jz)	je(jz)
a<=b	jbe(jna)	jle(jng)
a<b	jb(jnae)	jl(jnge)
a!=b	jne(jnz)	jne(jnz)



資料が無くてもVCの混合モードがあれば無敵です。 やりたいことをCで書いてコンパイルしてみれば直ぐアセンブラでそのやり方が分かるので。

とりあえず使う

で、アセンブラは一体どうやって使用すればよいのでしょうか。
答は簡単で__asm疑似命令を使います。



//a+bの値を返す関数
int f(int a,int b)
{
__asm
{
	mov eax,a	;eaxにaを代入します
	mov ebx,b	;ebxにbを代入します
	add eax,ebx	;eaxにebxを加算します
}
}


みたいな感じです。
簡単にプログラムの解説をすると__asmでアセンブラの開始の合図をして、movでレジスタに値を代入していきます。aもbも32bit型なので32bitレジスタのeax,ebxに代入します。そしてadd(加算)します。C/C++の関数の返値はeaxに入れるのが掟なのでこのまま関数を終わってしまえばOK。

ところで、関数の引数はそのままアセンブラの命令のオペランドに使えます。
なぜかというと、関数に引数を渡すときはスタックに積んで渡しますが、関数側でそれを参照しようとするといちいちpopしなければなりません。それはちょっとナンセンスなのでコンパイラはローカル変数の確保の必要もあるのでespをebpにコピーして使います。
すると[ebp+定数]のようなアドレッシングモードが使えるためいちいちpopしなくても引数の値が参照できるというわけです。だから
mov eax,a
という文でも実際は
mov eax,[ebp+??]
という形に置き換えてアセンブルしているわけです。
そのことを知らずにebpの値を変えたりすると引数が参照出来なくなるので注意して下さい。

あと、関数内で使用して良いレジスタですがespさえ保持していれば何を使っても構いません。コンパイラが勝手に使うレジスタを関数の始まりで保存(push)して終わりで復元(pop)するので。 ここらへんもインラインアセンブラの楽なところです。

同様に


static int a[1024];
void f(int n)	//配列変数から値を取り出す
{
__asm
{
	mov ebx,n
	mov eax,[a+ebx*4]
}
}


みたいにグローバル変数にもアクセスできます。ここでひとつ注意。
mov eax,[a+n*4]
でいいじゃん、と思うかもしれませんが、これはダメです。なぜかというと実際は、
mov eax[a+[ebp+??]*4]
ということになるのですが、こんな複雑なアドレッシングモードはx86CPUにはありません。諦めましょう。

最適化への道

最適化するときに気を付けることをあげます。
• 出来る限りpairingするようにする。 ペンティアム(P5)の最適化の基本はpairing(ペアリング,組み合わせ)にあります。 P5は知っての通り命令を処理するパイプラインが２つあり、２つの命令を同時に実行できます。 ただ、一緒に実行できる命令と出来ない命令があり、可能な限り同時に実行していくように 組むのが最適化への道です。 で、pairingは命令表には簡単に書いてありますが、実際はかなり複雑なルールが適用されます。
  1. 最初の命令はU-pipeで実行され、２つ目の命令はV-pipeで実行される
  2. 最初の命令で書き込まれたレジスタには、２つ目の命令で読むことも書くことも出来ない。
     

         MOV EAX, EBX / MOV ECX, EAX     ; 書いた後に読むのでpairing不可
         MOV EAX, 1   / MOV EAX, 2       ; 書いた後に書くのでpairing不可
     

  3. 分割されたレジスタは分割されていない状態で扱われる。

         MOV AL, BL  /  MOV AH, 0        ; 同じレジスタの違った場所に書くのはpairing不可
     

  4. 同じ4bytes境界のメモリ空間に同時にアクセスできない。

     P5の場合メモリ空間は4byte(dword)単位で扱っています。
         MOV AL, [ESI] / MOV BL, [ESI+1]   ; 同じdwordに書くのでダメ
         MOV AL, [ESI+3] / MOV BL, [ESI+4] ; 違うdwordに書くので良い
     

  5. 上のルールの例外で2つのアドレスの2-4bitが同じだった場合、その差が32で割れてはいけない。(?)

         MOV [ESI], EAX / MOV [ESI+32000], EBX ; だめ
         MOV [ESI], EAX / MOV [ESI+32004], EBX ; OK
     

  6. 2と3のルールに反してフラグレジスタには同時に書き込まれることが許される。

     確かにフラグが変化するのが駄目だとしたらpairingなんて価値ないわな(^^;
         SHR EAX,4 / INC EBX   ; OK
     

  7. 2のルールに反して最初の命令でフラグレジスタに書き込まれたものを、次の命令が条件ジャンプなら読み出せる。

         CMP EAX, 2 / JA LabelBigger   ; OK
     

  8. 以下のスタック操作はpairingできる。
     PUSH + PUSH, PUSH + CALL, POP + POP

         PUSH EAX / CALL MySub  ; OK
         PUSH AX  / PUSH BX     ; 32bitmodeのときはOK
                                ; 16bitmodeのとき、もしSPが4で割れるなら4つめのルールによりpairing不可
     

  9. pairingを制限する場合
     • 標準でないセグメントを使う
     • 32bitmodeのとき16bitデータを扱う,またその逆、
     • リピート命令を使う
     • LOCKプリフィックスがある
     • P5 without MMXで8086には無い命令(先頭に0fhが付く) 有名なものだと、
       
       MOVZX, MOVSX, PUSH FS, POP FS, PUSH GS, POP GS, LFS, LGS, LSS, SETcc, BT, BTC, BTR, BTS, BSF, BSR, SHLD, SHRD, and IMUL with two operands and no immediate operand.
     MMXが無い場合前の命令は、条件分岐を除いてU-pipeでしか実行できない。 MMXがある場合は、セグメントとリピートとLOCKがあるとU-pipeでしか実行できないが それ以外はUV両方で使える。
     
     
  10. １つの命令にディスプレースメントとイミディエイトが同時に含まれている場合、 MMXがないとき、pairingは出来ない。MMXがあれば、U-pipeでのみpairingができる。

           MOV DWORD PTR DS:[1000], 0    ; not pairable or only in U-pipe
           CMP BYTE PTR [EBX+8], 1       ; not pairable or only in U-pipe
           CMP BYTE PTR [EBX], 1         ; pairable
           CMP BYTE PTR [EBX+8], AL      ; pairable
      

• 乗除算は出来るだけ使わない。
  乗算は9clock(np)もかかりますし、除算なんて最悪46clock(np)もかかります。 MOV等基本的な命令が1clock(uv)で済むことを考えればいかに遅いかが分かるでしょう。 出来る限りMOVやシフト命令などで済ませたいところです。
  どうしても大量の乗算が必要ならFPUで行いましょう。 彼は乗算を3clock(後半2clockはpairing可能なので実質1clock!!)で済ませます。 鬼です。
  
  
• キャッシュ効率を考える
  書いてあるclock数はあくまでもキャッシュなどが全てヒットしたときの理想の値です。 だからやたらあちこちのメモリを参照したりするとキャッシュに全然ヒットしないので遅くなるでしょう。demo codingでもテーブルの大きさは64kbに収めるとか、よく聞きますし。
  分岐予測のことを考えると条件分岐も少なくした方がよいでしょう。 特にPRO以降は分岐予測に失敗したときのペナルティーが大きくなっています。なんか10-15clockだとかいう話(怖えー)。分岐予測のアルゴリズムが良くなったらしいけどそのせいかねえ。P2では多少は改善されているとは思われますが。あとPROだとpush+pushとかpush+call等のpairingが不可能になってます。ううむ。

クイズ大会

まあクイズ大会と言っても問題は拾ってきた奴ばかりですが(^^; 気にしない気にしない(^^;;;



問題.１

eaxを217倍する最速コードは？


解答(下の空白を選択して反転させて見て下さい)

普通
imul	eax,217		;11clock
と考えるかもしれませんが答えはなんと
mov	ecx,eax		;1 U-pipe
shl	eax,3		;2 U-pipe(SHLはU固定)
sub	eax,ecx		;3 U-pipe(eax書き込んだ後だからpairing不可)
mov	ecx,eax		;4 U-pipe(eax書き込んだ後だからpairing不可)
shl	eax,5		;5 U-pipe(SHLはU固定)
sub	eax,ecx		;6 U-pipe(eax書き込んだ後だからpairing不可)

ことごとくpairing出来ませんがそれでも6clockで終わります。





問題.２

それでは分かる人には一発で分かる問題。
ebxとecx*8を足して1000を引いてeaxに代入する最速コードは?


解答(下の空白を選択して反転させて見て下さい)

lea eax,[ebx+ecx*8-1000]	;実効アドレスのロード
			;なのでebx+8*ecx-1000の指す内容を代入しているわけではありません

です(笑)。うーむ恐ろしいまでに強力なアドレッシングモード(^^;;





問題.３

これは簡単かもしれません。
eaxを10倍する最速コードは?


解答(下の空白を選択して反転させて見て下さい)

lea eax,[eax+eax*4]
add eax,eax

これまたアドレッシングモードを利用した技でした。