gihyo.jpサイトのロゴ

アンティーク・アセンブラ～Antique Assembler

第4回"case" の事情

2009-06-24

前回は条件分岐を行うためのEFLAGSレジスタと条件分岐命令について説明しました。

しかし、プログラミングにおける重要な制御構造でありながら、単純な条件分岐では実現できないものとして、C/C++言語で言うところのswitch構文があります。

今回は、このswitch構文について、アセンブラの視点から見てみましょう。

if分岐の限界

たとえば:

変数 "x" に格納された値が0, 1, 2, 3, およびそれ以外の場合に、それぞれ異なる処理を行いたい。

という状況で、あまり手馴れていない人の実装は往々にして以下のようになります。

リスト1　if 分岐による実装
if(x == 0){ .... }
else if(x == 1){ .... }
else if(x == 2){ .... }
else if(x == 3){ .... }
else{ .... }

上記の例は、「⁠それ以外」を除いた条件が4つなので、まだ許容範囲と言えなくもないですが、条件の数がNに増えた場合の条件判定回数は:

  • 最悪の場合なら、常にN回の条件判定
  • 値が均等に分散している場合でも、平均してN/2回の条件判定

となります（もちろん変数 "x" の傾向次第ですが）ので、条件数Nが一定以上になる場合には、上記のようなif／elseを連ねる実装は妥当とは言えません。

このような場合、C/C++やそれに類する言語では、switch構文を使用するのが一般的です。

switch 構文を使用することで、リスト1の実装は以下のようになります。

リスト2　switchによる実装
switch(x){
  case 0:
    ....; break;
  case 1:
    ....; break;
  case 2:
    ....; break;
  case 3:
    ....; break;
  default:
    ....; break;
}

switch構文での実装の場合、変数 xの判定に要するコスト（＝処理量）は、caseの数に関わりなく一定（※）となりますので、if／elseを連ねた実装よりも効率的な処理が可能です。

※）
詳細は後述しますが、caseで列挙される値次第では、必ずしもこの前提は成立しません。

switch の動作原理

アセンブラでswitch構文を実現するには、どのように実装したら良いでしょうか？

判定対象の値（先述した例なら「変数x⁠」⁠）を列挙されたcaseごとに比較していたのでは、冒頭で示したif/elseを連ねる「駄目な実装」に逆戻りですから、実現には別な手段を考える必要があります。

switch構文の振る舞いをもう少し細かく見てみると、caseに列挙されている最小値をMIN、最大値をMAXとした場合:

  • 対象値がMINなら、"case MIN" 位置へ
  • 対象値がMIN ＋ 1なら、"case MIN ＋ 1" 位置へ
  • 対象値がMIN ＋ 2なら、"case MIN ＋ 2" 位置へ
  • ....(省略)....
  • 対象値がMAX － 1なら、"case MAX － 1" 位置へ
  • 対象値がMAXなら、"case MAX" 位置へ
  • それ以外なら、"default" 位置へ

というのがswitch構文に期待される処理です。

対象値がMIN～MAXの間の処理は、「⁠値」とそれに対する「制御遷移先」の違いこそあれ、やっている処理は同一です。

これなら:

  1. 値xが MIN ≦ x ≦ MAX か否かを判定
  2. 成立していないなら、default位置へ制御遷移
  3. 値xに応じて、対応する位置へ制御遷移

という手順に単純化できます。

「値に応じて、対応する位置」へと制御遷移させる処理は、値に対応する制御遷移位置の配列を、プログラム実装時点であらかじめ作っておくことで、単なる配列参照処理に落とし込むことができます。

対象値がMIN～MAXの間で連続していない場合に、配列参照で上手く機能するのか？

という疑問が出てくるかも知れません。しかし:

caseで列挙されていない値の場合はdefault位置へ制御遷移

で良いわけですから、上記の「制御遷移位置の配列」において、case列挙されていない値に対応する要素を、defaultを指すものに設定してやれば良いのです。

switchの実現

それでは、いよいよアセンブラを使用してswitch処理を実現してみましょう。

アセンブラでの実装の元となる処理は、以下（リスト3）の実装に相当するものとします。

リスト3　C言語による元実装
switch(x){
  case 2:
    a = 1; break;
  case 5:
    a = 2; break;
  case 8:
    a = 3; break;
  default:
    a = 4; break;
}

switchブロック部分の実装

まずはswitch構文のブロック部分（波カッコでくくられた部分）を実装してしまいます。

リスト4　switchブロックの実装
switch_case_2:
    movl    $1, a
    jmp     switch_eob
switch_case_5:
    movl    $2, a
    jmp     switch_eob
switch_case_8:
    movl    $3, a
    jmp     switch_eob
switch_default:
    movl    $4, a
    jmp     switch_eob
switch_eob: # end of block

    .global end_of_program
end_of_program:
    int3        # プログラム実行の一時停止
    nop

breakに相当する処理が、switch構文末尾位置への無条件分岐命令（JMP）を使用している以外は、C言語での記述からの単純な変換で済んでいることがわかります。

制御遷移先配列の作成

次は「値に対応する制御遷移先の配列」を作成します。

何やら堅苦しい表現をしてはいますが、特に難しく考える必要はありません。

リスト5　制御遷移先配列の作成
addr_table:
    .long   switch_case_2  # 2(MIN + 0)
    .long   switch_default # 3(MIN + 1)
    .long   switch_default # 4(MIN + 2)
    .long   switch_case_5  # 5(MIN + 3)
    .long   switch_default # 6(MIN + 4)
    .long   switch_default # 7(MIN + 5)
    .long   switch_case_8  # 8(MIN + 6)

見ての通り、アドレス情報を列挙することで、配列相当のデータ領域を作成しただけです。

元ソースのcaseで列挙されている値は、2、5、8といったように不連続なものですが、配列自体は全体を包含するサイズで作っておいて、列挙されていない数に相当する位置には、defaultに相当するアドレスを設定しているのがミソです。

対応するcase位置への制御遷移

ここまで準備ができたなら、いよいよ値に応じて制御遷移させる処理を実装しましょう。

リスト6　制御遷移の実施
    .text
    .align  4

    .global entry_point
entry_point:
    int3        # プログラム実行の一時停止

    movl    x, %eax

    # 値域判定
    cmpl    $2, %eax
    jl      switch_default  # "x < 2" なら default
    cmpl    $8, %eax
    jg      switch_default  # "8 < x" なら default

    # 制御遷移先配列による制御遷移
    leal    addr_table, %ebx
    subl    $2, eax         # 最小値の 2 を減算
    jmp     *(%ebx, %eax, 4)

switch実現の肝になるのは、あらかじめ作成しておいた制御遷移先配列を使用して、適切な位置に制御遷移する部分です。

これまでの本連載における実装例では、分岐命令の制御遷移先の記述を、単純なアドレス値指定＝直接アドレッシングで行っていましたが、今回はちょっと複雑なものになっています。このアドレッシングを仔細に見てみましょう。

  • ベース値はレジスタ ebxの値（＝addr_table）
  • レジスタ eax（＝変数 "x" － 2）によるインデックス付き
  • インデックスの倍数は4 ＝32ビットアドレスの格納サイズ
  • 間接アドレッシング＝メモリに格納されているアドレスを使用

以上のことから、このアドレッシングによって算出される制御遷移先は、

  • 「addr_table + (変数 "x" - 2) * 4の位置に格納されたアドレス」

となります。

後は変数xおよびaの格納領域を確保する必要がありますので、リスト7のように記述します。

リスト7　変数領域の確保
    .data
    .align  4

    .global x
x:
    .long   0

    .global a
a:
    .long   0

最終的なサンプルソースは、これまでに例示したソースを以下の順で並べたものとなります。

  • リスト 7
  • リスト 5
  • リスト 6
  • リスト 4

それでは実際に実行してみましょう。

図1　switch実装の動作確認
(gdb) run
....
Program received signal SIGTRAP, Trace/breakpoint trap.
0x00401001 in entry_point ()
(gdb) disassemble entry_point
Dump of assembler code for function entry_point:
0x00401000 <entry_point+0>:  int3   
0x00401001 <entry_point+1>:  mov  0x402000,%eax
0x00401006 <entry_point+6>:  cmp  $0x2,%eax
0x00401009 <entry_point+9>:  jl   0x401040 <switch_default>
0x0040100b <entry_point+11>: cmp  $0x8,%eax
0x0040100e <entry_point+14>: jg   0x401040 <switch_default>
0x00401010 <entry_point+16>: lea  0x402008,%ebx
0x00401016 <entry_point+22>: sub  $0x2,%eax
0x00401019 <entry_point+25>: jmp  *(%ebx,%eax,4)
End of assembler dump.
(gdb) set var x=5
   ※ 変数 x を 5 に設定
(gdb) stepi
... "jmp  *(%ebx,%eax,4)" まで進める ...
0x00401019 in entry_point ()
(gdb) info register ebx eax
ebx            0x402008 4202504
eax            0x3      3
   ※ レジスタ値の確認
(gdb) stepi
0x00401028 in switch_case_5 ()
   ※ "case 5" 相当の位置に制御遷移
(gdb) x/1x 0x402008+3*4
0x402014 <addr_table+12>: 0x00401028
   ※ "%ebx + %eax * 4" の位置に "case 5" 相当の
       アドレスが格納されていることを確認
(gdb)

値に応じて想定した位置に制御遷移していることがわかります。

低レイヤーから見たswitch

switch相当の機能実現に関する説明は以上で終わりですが、折角アセンブラのような低レイヤーからの視点で見ているわけですから、上位のソースコードからだけでは見えてこないトピックについて、幾つか触れてみようと思います。

データ量を減らすには

先述した switch実現例では、制御遷移先配列の格納の際には、制御遷移先のアドレス情報（32ビット＝4バイト）をまるまる格納していました。

しかし、通常のプログラムで考えた場合、分岐命令の位置から分岐先までは高々数十バイト～数百バイト程度、つまり16ビット＝2バイトもあれば十分表現できる範囲（※）にあります。このような状況で32bitのアドレスを丸々格納するのは、同一市内の友人に葉書を投函する際の宛先を、わざわざ国名から書き始めるような冗長さがあります。

※）
ひょっとしたら、8ビット＝1バイトでも十分かもしれません。

たとえば、制御遷移処理をリスト7のように実装したとします。

リスト8　データ量を減らす制御遷移処理
    leal    addr_table, %ebx
    subl    $2, %eax
    movl    $0, %ecx
    # 16 ビット幅の転送なので、転送先レジスタ指定は
    # 32 ビット幅の ecx ではなく、16 ビット幅の cx。
    # インデックスの倍数も 4 ではなく 2。
    movw    (%ebx, %eax, 2), %cx
    # アドレス値としての switch_jmp を加算するので
    # 即値を示す $ を使用
    addl    $switch_jmp, %ecx
switch_jmp:
    # ecx の値が指すアドレスへ制御遷移
    jmp     *%ecx

上記実装での制御遷移先アドレスの算出では、制御遷移先配列から取り出した値と、switch_jmpのアドレスを加算しています。そのため制御遷移先配列に格納する値はswitch_jmpからの相対的な値、つまり switch_jmpとの差分だけを格納すれば良いことになりますから、両者が十分近い値であれば各要素の格納は16ビット＝2バイト程度で済みます。

リスト9　アドレス差分による制御遷移先配列
addr_table:
    .word  switch_case_2  - switch_jmp
    .word  switch_default - switch_jmp
    .word  switch_default - switch_jmp
    .word  switch_case_5  - switch_jmp
    .word  switch_default - switch_jmp
    .word  switch_default - switch_jmp
    .word  switch_case_8  - switch_jmp

実行される命令数の増加＝性能低下をある程度許容してでも、必要とされる総メモリ量の抑止を実現したいような場合であれば、制御遷移先配列の格納に必要な領域のサイズを低減させるための、このような実装方式も選択肢の1つになるでしょう。

制御遷移先は「既知」

初心者がswitch構文を使用する場合の代表的な間違いに:

変数を使ったcase列挙によるコンパイルエラー

というものがあるのではないでしょうか。

プログラミングに慣れるに従い:

switch構文のcaseには、変数を指定してはならない

というルールを理解するわけですが、アセンブラレベルでのswitchの実現方式を理解した今であれば:

コンパイル時点で、制御遷移先配列を格納＝値の範囲を確定する必要があるため、実行時にならないと値が確定できない変数値は、caseでの列挙には使用できない

という理屈で理解できるようになっていることでしょう。

switchのコスト

先述したswitchの実現例を見て:

case列挙の下限値～上限値の範囲判定が必要なので、if/elseを使用したものよりもswitchは余計な処理をしているのでは？

と思われるかも知れません。

必要な条件判定が2つ程度であるなら、その考えは正しいと言えます。

また、たとえば0～255の間に分散する値に応じて処理を切り替える必要がある場合、四角四面にswitchを使って実装するなら、4バイト×256＝1Kバイトもの制御遷移先情報を格納する必要があります（32ビット環境で制御遷移先アドレスを丸々格納する場合⁠）⁠。

さらに上限値と下限値の開きが大きい場合、たとえば0～1024の間で値が分散する状況で制御遷移先情報を丸々格納するのは、とてもではありませんが現実的ではありません。

このようなケースでCコンパイラが生成するアセンブラコードは

  1. case で列挙されている値を大小で2つのグループに分割
  2. 中間値で大小判定
  3. どちらかのグループで一致が検出されるまで、分割～判定の手順を繰り返す
  4. 一致するcase値が判明したなら、該当する処理に制御遷移
  5. 一致するcase値が無いことが判明した場合は default 処理に制御遷移

といった二分探索（binary search）的な実行や、二分探索で値域を絞り込んでから制御遷移先配列を使用したswitch処理と組み合わせる、といったハイブリッドなものになるかもしれません。

コンパイラの最適化が上手くハマれば、下手に人手で書いたプログラムよりも適切なものになるとは思いますが、そもそもの「値判定に要するコスト（＝ 処理量）はcaseの数に関わりなく一定」という期待からは随分と異なる結果となります。

以上のように、常にswitchがif/elseの連続に対して常に優位であるわけではありません。

しかし、アセンブラレベルでのswitch実現方式を理解した今なら、実行時の性能オーバヘッドや、制御遷移先配列を格納するためのメモリ領域量といったものを勘案し、状況に応じて適切な選択を行うことが可能になっているのではないでしょうか。

おすすめ記事

記事・ニュース一覧