jump tableとは何か
jump tableとは、アセンブラやCにおいて制御の飛び先(jump先)を配列にして並べた物です。jump tableのイメージ図はこのようになります。
Cのswtich文のように、同じような条件で複数の飛び先がある場合を考えます。
int foo(int k){ int f = 0; switch (k) { case 0:f = i + l; break; /* k = 0 */ case 1:f = g + h; break; /* k = 1 */ case 2:f = g - h; break; /* k = 2 */ case 3:f = i - l; break; /* k = 3 */ case 4:f = i * l; break; /* k = 4 */ case 5:f = g * h; break; /* k = 5 */ case 6:f = g / h; break; /* k = 6 */ case 7:f = i / l; break; /* k = 7 */ default:f = 100; } return f; }
このようなswitch文の場合、caseの数だけif文を繰り返すのではなく、caseにでてくる0、1、2という値をそのまま使って、飛び先を求めることで比較回数を減らすことが出来ます。上の例でk=2の場合、case 2:の場合の飛び先を「飛び先2」の所に格納しておけば、テーブルの先頭＋2で「飛び先2」を求めることができます。
図で書くとこのようになります。
実際の例
上に出てきたCのソースをsde-gccでコンパイルしてみました。もとのソースがここ、コンパイル後のアセンブラがここです。コンパイル後のアセンブラは、PCspimで動作するように変更しています。
foo: .frame $fp,16,$31 # vars= 8, regs= 1/0, args= 0, gp= 0 .mask 0x40000000,-8 .fmask 0x00000000,0 addiu $sp,$sp,-16 sw $fp,8($sp) move $fp,$sp sw $4,16($fp) sw $0,0($fp)
この辺りはさくっと飛ばします。
lw $2,16($fp) sltu $2,$2,8 beq $2,$0,.L12 nop
lw命令で、$2に関数foo()の引数である6が入ります。次のsltu命令で引数が8より小さいかどうかを調べています。8より小さければそのまま処理を行い、8以上であればCのdafaultの処理を行うL12に飛びます。sltu命令を使いunsignedで比較することで、引数が負の値の場合もL12に飛ぶようになっています。
lw $2,16($fp) sll $3,$2,2
lw命令で、もう一度$2に引数の値6を入れます。sll命令にて$2を4倍しています。jump tableの1つの大きさが32bit(4バイト)なので、先頭のアドレス＋オフセットでアクセスするために4倍しています。
la $2, .L13 addu $2,$3,$2 lw $2,0($2) j $2 nop
ここでテーブルの先頭アドレス(L13)を取得し、addu命令で先ほど4倍したオフセットを足しています。最後に、lw命令で実際の飛び先をjump tableから取得し、j命令でjumpを行っています。
.rdata .align 2 .L13: .word .L4 .word .L5 .word .L6 .word .L7 .word .L8 .word .L9 .word .L10 .word .L11 .text
これがjump tableの本体です。実際には、ジャンプの飛び先であるアドレスが並ぶことになります。
.L4: lw $2,i lw $3,l addu $2,$2,$3 sw $2,0($fp) b .L3 nop
L4〜L11までがswitch文によって分かれた先の処理になります。
.L12: li $2,100 # 0x64 sw $2,0($fp)
ここはdafault:の飛び先で、default:f = 100;を実行しています。
このようにjump tableを使うことで、switch文を何回も比較することなく、数回の比較で目的の処理をしています。
gccの出したアセンブラをPCspimで動かすためにしたこと
lui $2,%hi(.L13) addiu $2,$2,%lo(.L13)
この2命令は、$2に.L13のアドレスを持ってきているだけなので、la $2, .L13に変換しました。la自体が疑似命令です。実際には等価な2命令になります。
teq $2,$0,7 mflo $2
gccが出すアセンブラでは、割り算を実行する前に割る数が0かどうかを確認しています。PCspimがteq命令をサポートしていなそうなので、teq命令は削除しました。
jump tableの応用例
jump tableにもいくつかのバリエーションがあります。私が今まで見たことのある物をいくつか紹介します。
ジャンプ命令そのものをテーブルにする。
飛び先ではなく、ジャンプ命令そのものをテーブルにします。遅延スロットのないCPUの割り込みベクターなどで使われます。レジスタに飛び先を持ってくるのではなく、jump tableの該当箇所に直接jumpします。jump先の命令が目的の場所へ飛ぶjump命令なので、もう一度jumpして目的の場所へ飛びます。レジスタに持ってくる手間が省けることとと、実はテーブルの一番最後はジャンプしなくて良いというメリットがあります。
ARMのFIQがこの手法をとっています。FIQを割り込みベクターの最後に配置する事で、ジャンプ命令を無くし高速化を図っています。
飛び先の一部だけ格納する。
ROMモニタープログラムで見かけたパターンです。上のCソースで作られたjump tableをdumpするとこうなります。
0: 00000078 4: 00000090 8: 000000a8 c: 000000c0 10: 000000d8 14: 000000f0 18: 00000108 1c: 00000128
よく見てみると、32bitのうち下位10bit程度しか使っていませんね。少なくとも上位16bit程は無駄です。この例は相対位置のjump先になっていますが、絶対番地でも同じ事で上位側は同じ値が並ぶはずです。さらに見ると、下位2bitは常に0なのでこれも無駄ですね。
ROMモニターで使われる逆アセルーチンでは、命令のデコードにテーブルがよく使われます。よく似た命令が集まっているようでそうでもなく、不規則に何も無いところがあるからです。1バイトでもROM領域を減らしたいため、飛び先を直接テーブルに入れるのではなく、必要なオフセットだけを格納することでROM領域を減らすことができます。
2次元テーブルにする
通信物のファームウェアを作った時に使いました。現状の状態(発信中、通話中など)に対して、発生するイベント(回線断等)の組み合わせで飛び先を決めます。jump_table[cur_state][event]のような感じで、飛び先を簡単に求めることができます。
当時はCで関数のポインタのテーブルを用意し、配列にアクセスすると同時に()演算子でそのまま呼び出していました。こんな事が出来る俺格好いい！と最初は思ったのですが、静的解析ツールとの相性が悪く、デバッグの過程でドキュメントと実際のテーブルがどんどん乖離していき酷い目にあいました。どうでも良いところでは小技を披露してはいけない、と心に強く刻み込む結果になりました。（当時はコードの自動生成のような発想がありませんでした）
さらに勉強するために
より突っ込んだ話には、こちらが参考になります。
ホワット・ア・ワンダフル・ワールド http://alohakun.blog7.fc2.com/blog-entry-878.html
はじめてのにき http://shinh.skr.jp/m/?date=20071121
2008/8/29 追加
大学6年生のhogelog http://d.hatena.ne.jp/hogelog/20080706/p1
