Cのswtich文がどのようにアセンブラになるかの話。
これが教科書に載っているCのソースです。
switch (k) { case 0:f = i + j; break; /* k = 0 */ case 1:f = g + h; break; /* k = 1 */ case 2:f = g - h; break; /* k = 2 */ case 3:f = i - j; break; /* k = 3 */ }
とりあえず、gcc-sdeでコンパイルしてみました。
もとのCソースはここ、PCSpimで動くように修正したアセンブラはここです。PCSpimは変数名にjが使えないのでlに変更しています。
switch文の処理を追って見る
順番に処理を見ていきましょう。
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) sw $2,4($fp)
この辺りswitch文と関係無いので飛ばして。
li $2,1 # 0x1 lw $3,4($fp) # $3に引数のk beq $3,$2,.L5 # $3と$2が同じならL5へ飛んでg+h nop
li $2,1で、レジスタ$2に1を代入。lw $3,4($fp)の命令で、スタックから引数kを取り出し$3に入れています。この2つのレジスタが等しければ、つまり引数が1ならば、L5へジャンプしてg+hを実行します。等しくなければそのまま下へ。
lw $3,4($fp) slt $2,$3,2 beq $2,$0,.L8 # $3が0ならL8へ飛んでg+h nop
lw $3,4($fp)で引数kを$3に入れています。slt命令によってkと2を比較し、比較結果を$2へ入れています。kが2より小さい場合(less than)$2は1になりますので、kが2以上の時はL8へ飛びます。
lw $2,4($fp) # $2に引数のk beq $2,$0,.L4 # kが0ならL4へ飛んで i+l nop b .L3 # 何もしない nop
ここに来た時点で、引数kは0以下の値です。kと0を比較して、kが0ならL4へ飛びます。kが0以外の場合、何も処理をしないでL3へ飛びswitch文を抜けます。
.L8: li $2,2 # 0x2 lw $3,4($fp) # k = 2 ならL6 beq $3,$2,.L6 nop li $2,3 # 0x3 lw $3,4($fp) # k = 3 ならL7 beq $3,$2,.L7 nop b .L3 # 何もしない nop
ここに来た時点で、kは2以上の値です。kと2を比較し同じならばL6へ飛び、kと3を比較し同じならばL7へ飛びます。kが2でも3でも無いとき、何もせずにL3へ飛びswitch文を抜けます。
.L4: # i + l /* k = 0 */ lw $2,i lw $3,l addu $2,$2,$3 sw $2,0($fp) b .L3 nop .L5: # g + h /* k = 1 */ lw $2,g lw $3,h addu $2,$2,$3 sw $2,0($fp) b .L3 nop .L6: # g - h /* k = 2 */ lw $2,g lw $3,h subu $2,$2,$3 sw $2,0($fp) b .L3 nop .L7: # i - l /* k = 3 */ lw $2,i lw $3,l subu $2,$2,$3 sw $2,0($fp)
この部分は実際に足したり引いたりしているところです。
.L3: #return lw $2,0($fp) move $sp,$fp lw $fp,8($sp) addiu $sp,$sp,16 j $31 nop
ここは戻り値の処理ですのでswitch文とは関係ありませんが、L3がswitch文終了の飛び先になっています。
Cに戻してみると
上のアセンブラをもう一度Cに戻してみるとこうなります。
if(k == 1){ f = g + h; } else if(k < 2) { if(k == 0) { f = i + l; } else { /* nothing */ } } else { if(k == 2) { f = g - h; } else if(k == 3) { f = i - l; } else { /* nothing */ } }
想像しているよりは、面倒な比較を行っています。
switch (k) { case 0:f = i + j; break; /* k = 0 */ case 1:f = g + h; break; /* k = 1 */ case 2:f = g - h; break; /* k = 2 */ case 3:f = i - j; break; /* k = 3 */ }
Cにおいて上のswitch文は、if(k==0){f = i + j;}else if(k=1){f = g + h;}・・・・と等価では無い事がわかるでしょうか。if文の場合はまずkと0が比較されるのが保証されるのに対し、switch文では比較の順序は保証されません。
高速化の為にswitch文を避ける
処理速度に厳しい環境では、あえてswitch文を使わないことで高速化を図るケースがあります。switch文一つでまとめると綺麗に書ける場合でも、高速化の為にわざと先頭にif文を持ってきています。switch文の代わりにif-else文が並んでいるときもあります。
if(k == 0){ /* do someting */ return; } switch (k) { /* case 0:f = i + j; break; k = 0 */ case 1:f = g + h; break; /* k = 1 */ case 2:f = g - h; break; /* k = 2 */ case 3:f = i - j; break; /* k = 3 */ }
よくある使い方としては
・最初のif文が成立する可能性が非常に高い時、先に比較することで平均の処理時間を短縮する。
・if文が成立する可能性が低くても応答速度が非常に厳しい時、先に比較することで特定の処理の時間を短縮する。
組み込みの割り込み処理などでは、ときどき見かけるテクニックです。これはcase文の方が綺麗に書けると思っても、生暖かくそのままにしておきましょう。
実際の最適化の例(2008/8/29追加)
もっと実践的な環境（VMの高速化）での事例です。
http://d.hatena.ne.jp/hogelog/20080706/p1
