前回は条件分岐を行うためのEFLAGSレジスタと条件分岐命令について説明しました。
しかし、プログラミングにおける重要な制御構造でありながら、単純な条件分岐では実現できないものとして、C/C++言語で言うところのswitch構文があります。
今回は、このswitch構文について、アセンブラの視点から見てみましょう。
if分岐の限界
たとえば:
変数 "x
" に格納された値が0, 1, 2, 3, およびそれ以外の場合に、それぞれ異なる処理を行いたい。
という状況で、あまり手馴れていない人の実装は往々にして以下のようになります。
上記の例は、「それ以外」を除いた条件が4つなので、まだ許容範囲と言えなくもないですが、条件の数がNに増えた場合の条件判定回数は:
- 最悪の場合なら、常にN回の条件判定
- 値が均等に分散している場合でも、平均してN/2回の条件判定
となります(もちろん変数 "x
" の傾向次第ですが)ので、条件数Nが一定以上になる場合には、上記のようなif/elseを連ねる実装は妥当とは言えません。
このような場合、C/C++やそれに類する言語では、switch構文を使用するのが一般的です。
switch 構文を使用することで、リスト1の実装は以下のようになります。
switch構文での実装の場合、変数 x
の判定に要するコスト(=処理量)は、caseの数に関わりなく一定(※)となりますので、if/elseを連ねた実装よりも効率的な処理が可能です。
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の間の処理は、「値」とそれに対する「制御遷移先」の違いこそあれ、やっている処理は同一です。
これなら:
- 値
x
が MIN ≦ x ≦ MAX
か否かを判定
- 成立していないなら、
default
位置へ制御遷移
- 値
x
に応じて、対応する位置へ制御遷移
という手順に単純化できます。
「値に応じて、対応する位置」へと制御遷移させる処理は、値に対応する制御遷移位置の配列を、プログラム実装時点であらかじめ作っておくことで、単なる配列参照処理に落とし込むことができます。
対象値がMIN~MAXの間で連続していない場合に、配列参照で上手く機能するのか?
という疑問が出てくるかも知れません。しかし:
case
で列挙されていない値の場合はdefault
位置へ制御遷移
で良いわけですから、上記の「制御遷移位置の配列」において、case
列挙されていない値に対応する要素を、default
を指すものに設定してやれば良いのです。
switchの実現
それでは、いよいよアセンブラを使用してswitch処理を実現してみましょう。
アセンブラでの実装の元となる処理は、以下(リスト3)の実装に相当するものとします。
switchブロック部分の実装
まずはswitch構文のブロック部分(波カッコでくくられた部分)を実装してしまいます。
break
に相当する処理が、switch構文末尾位置への無条件分岐命令(JMP)を使用している以外は、C言語での記述からの単純な変換で済んでいることがわかります。
制御遷移先配列の作成
次は「値に対応する制御遷移先の配列」を作成します。
何やら堅苦しい表現をしてはいますが、特に難しく考える必要はありません。
見ての通り、アドレス情報を列挙することで、配列相当のデータ領域を作成しただけです。
元ソースのcase
で列挙されている値は、2、5、8といったように不連続なものですが、配列自体は全体を包含するサイズで作っておいて、列挙されていない数に相当する位置には、default
に相当するアドレスを設定しているのがミソです。
対応するcase位置への制御遷移
ここまで準備ができたなら、いよいよ値に応じて制御遷移させる処理を実装しましょう。
switch実現の肝になるのは、あらかじめ作成しておいた制御遷移先配列を使用して、適切な位置に制御遷移する部分です。
これまでの本連載における実装例では、分岐命令の制御遷移先の記述を、単純なアドレス値指定=直接アドレッシングで行っていましたが、今回はちょっと複雑なものになっています。このアドレッシングを仔細に見てみましょう。
- ベース値はレジスタ
ebx
の値(=addr_table
)
- レジスタ
eax
(=変数 "x" - 2)によるインデックス付き
- インデックスの倍数は4 =32ビットアドレスの格納サイズ
- 間接アドレッシング=メモリに格納されているアドレスを使用
以上のことから、このアドレッシングによって算出される制御遷移先は、
- 「
addr_table + (変数 "x" - 2) * 4
の位置に格納されたアドレス」
となります。
後は変数xおよびaの格納領域を確保する必要がありますので、リスト7のように記述します。
最終的なサンプルソースは、これまでに例示したソースを以下の順で並べたものとなります。
それでは実際に実行してみましょう。
値に応じて想定した位置に制御遷移していることがわかります。
低レイヤーから見たswitch
switch相当の機能実現に関する説明は以上で終わりですが、折角アセンブラのような低レイヤーからの視点で見ているわけですから、上位のソースコードからだけでは見えてこないトピックについて、幾つか触れてみようと思います。
データ量を減らすには
先述した switch実現例では、制御遷移先配列の格納の際には、制御遷移先のアドレス情報(32ビット=4バイト)をまるまる格納していました。
しかし、通常のプログラムで考えた場合、分岐命令の位置から分岐先までは高々数十バイト~数百バイト程度、つまり16ビット=2バイトもあれば十分表現できる範囲(※)にあります。このような状況で32bitのアドレスを丸々格納するのは、同一市内の友人に葉書を投函する際の宛先を、わざわざ国名から書き始めるような冗長さがあります。
たとえば、制御遷移処理をリスト7のように実装したとします。
上記実装での制御遷移先アドレスの算出では、制御遷移先配列から取り出した値と、switch_jmp
のアドレスを加算しています。そのため制御遷移先配列に格納する値はswitch_jmp
からの相対的な値、つまり switch_jmp
との差分だけを格納すれば良いことになりますから、両者が十分近い値であれば各要素の格納は16ビット=2バイト程度で済みます。
実行される命令数の増加=性能低下をある程度許容してでも、必要とされる総メモリ量の抑止を実現したいような場合であれば、制御遷移先配列の格納に必要な領域のサイズを低減させるための、このような実装方式も選択肢の1つになるでしょう。
制御遷移先は「既知」
初心者がswitch構文を使用する場合の代表的な間違いに:
変数を使ったcase列挙によるコンパイルエラー
というものがあるのではないでしょうか。
プログラミングに慣れるに従い:
switch構文のcaseには、変数を指定してはならない
というルールを理解するわけですが、アセンブラレベルでのswitchの実現方式を理解した今であれば:
コンパイル時点で、制御遷移先配列を格納=値の範囲を確定する必要があるため、実行時にならないと値が確定できない変数値は、caseでの列挙には使用できない
という理屈で理解できるようになっていることでしょう。
switchのコスト
先述したswitchの実現例を見て:
case
列挙の下限値~上限値の範囲判定が必要なので、if/elseを使用したものよりもswitchは余計な処理をしているのでは?
と思われるかも知れません。
必要な条件判定が2つ程度であるなら、その考えは正しいと言えます。
また、たとえば0~255の間に分散する値に応じて処理を切り替える必要がある場合、四角四面にswitchを使って実装するなら、4バイト×256=1Kバイトもの制御遷移先情報を格納する必要があります(32ビット環境で制御遷移先アドレスを丸々格納する場合)。
さらに上限値と下限値の開きが大きい場合、たとえば0~1024の間で値が分散する状況で制御遷移先情報を丸々格納するのは、とてもではありませんが現実的ではありません。
このようなケースでCコンパイラが生成するアセンブラコードは
- case で列挙されている値を大小で2つのグループに分割
- 中間値で大小判定
- どちらかのグループで一致が検出されるまで、分割~判定の手順を繰り返す
- 一致するcase値が判明したなら、該当する処理に制御遷移
- 一致するcase値が無いことが判明した場合は default 処理に制御遷移
といった二分探索(binary search)的な実行や、二分探索で値域を絞り込んでから制御遷移先配列を使用したswitch処理と組み合わせる、といったハイブリッドなものになるかもしれません。
コンパイラの最適化が上手くハマれば、下手に人手で書いたプログラムよりも適切なものになるとは思いますが、そもそもの「値判定に要するコスト(= 処理量)はcaseの数に関わりなく一定」という期待からは随分と異なる結果となります。
以上のように、常にswitchがif/elseの連続に対して常に優位であるわけではありません。
しかし、アセンブラレベルでのswitch実現方式を理解した今なら、実行時の性能オーバヘッドや、制御遷移先配列を格納するためのメモリ領域量といったものを勘案し、状況に応じて適切な選択を行うことが可能になっているのではないでしょうか。