if 文と jump 命令の性質の違いを説明する
はじめに
Human Resource Machine というゲームがある。 Steam 等で入手することができる。
このゲームを雑に説明してしまうと、このゲーム固有の命令セットを持つようなプロセッサが処理できる、アセンブリプログラミングをするというようなゲームである。ここでは人間がプロセッサに代わって命令通りに行動し、状態を保持するレジスタは工場の区画として表現される。入出力は数字だが、数字はあたかもその「実体」を持つように扱われる。したがって、アルゴリズム上のいくつかの概念はまさにアセンブリプログラミングをする時とまさに同じような形で実装しなければならない*1。現実の CPU と同様の制約も存在する*2。
ところで、条件付きの jump 命令（jump if negative, jump if zero）が登場した時に、その扱い方が高級言語の if 文と異なるので、混乱することがあるだろう。ここでは、その性質の違いを説明してみたいと思う。なお、文中で厳密さを欠いた説明をしていることをお許しいただきたい。（例えば一般に Windows は x86-64 の CPU 上で動作するというステートメントは、Windows 9x 系や ARM 版 Windows について無視していることになるが、そうした部分についてはご容赦いただきたい。）
CPU とアセンブリプログラミングにおける一般論
CPUは命令列によって動作する。パンチカードの時代から、プロセッサは常に一列の命令列を順に処理していく。つまり基本的には、CPU は与えられた命令を順序通り処理するように設計されている。しかしそれだけでは制御構造が実装できないので、CPU が読み取ることができる命令列は機械語である。あらゆるソフトウェアは最終的にはその機械語に翻訳されて実行される。ところで、CPU の種類によって実行できる命令列のパターンが異なっている。これはいわば、異なる言語が CPU ごとに存在していて、CPU ごとに異なる言い方をしないとその CPU が動作しない、というようなものだ。
一般に低レイヤーに近い、つまり CPU やメモリといった資源の配分をするようなレイヤーのコードは、CPUの機能を直接利用することになるため、CPU に特化したコードを書くことになる。例えば OS のカーネルがそれに該当し、 最近の Windows は x86_64 という命令セットが動作する CPU 上で動作するし、 最近の Mac や iOS は ARM という命令セットが動作する CPU 上で動作するようになっている。さらには、同じ命令セットが動作する CPU であっても、そのOS上で実行できる実行ファイルのフォーマットが異なるので、たとえ同一のソフトウェアであっても Windows と Mac、 Linux で実行するバイナリが異なることがある *3。OSごとにダウンロードするファイルが異なるというのはそのためである。フォーマットの違いは、共有ライブラリの呼び出しの方法や、ヘッダの違いなどに起因している。
命令セットの違いとは何か？
機械語は基本的には 0/1 の二進数で表現されるものである。CPU のアーキテクチャによってその命令セットは異なることは説明したが、それが具体的にはどのように記述するかを説明したい。よくCPU には 64bit のものと 32 bit のものがあることが知られているが、その違いは何だろうか。よくある間違いとしては、1つの命令の長さは 64 bit の CPU では 64bit で、 32 bit の CPU では 32bit である、というわけでは必ずしもない。
ここであるように、x86_64 は可変長だが、その他の固定長のアーキテクチャ(いわゆるRISC)では64 bit の CPU であっても 32 bit であることがわかる。その場合では、一般に1つの命令につき32個の0と1で表現されるということになる。 では 64 bit の CPU は何が 64 bit かというと、汎用レジスタのサイズが 64 bit であるということである。つまり、1つのレジスタに64 個の 0/1 の数字を格納することができる、というわけである。
これは単純に、例えば浮動小数点を倍精度で扱うときに1つのレジスタで済むので処理を高速化できるといったような利点もあるが、大きな利点は大きいメモリを利用できるということだろう。具体的には 32 bit のレジスタで指し示すことのできるメモリ空間は 232 ~ 4GB 程度だが、メモリが 4GB しか使えないとなると現代においてはかなり強い制約となる。仮にOSが 32 bit のメモリ空間しか利用できないならば、その上で動作するソフトウェアも同様の制約を受けることになってしまう。個々のソフトウェア単位でも、例えば動画編集や3Dアニメーションを利用しようとするとすぐに4GB のメモリを消費してしまうだろう。これが 64 bit のメモリアドレス空間を利用できるとなると、理想的には 264 のメモリ空間を利用できるため、一般的な用途として十分である。
よくバイナリをダウンロードするときに、32 bit 版と 64 bit 版を選ばせる。どちらをダウンロードすればよいか悩む場合があるが、それは 32 bit のマシンでは 64 bit のレジスタが存在することを前提とした命令セットを用いてビルドされたバイナリは実行できないが、逆は可能である。では 64 bitの環境でも 32 bit のバイナリを使っておけば問題がないような気もするが、先述の通り、32 bit 版のバイナリでは利用できるメモリサイズが限られてしまう以上、 64 bit 版のバイナリを利用した方が少なくともメモリに関する制約を回避することはできる。
固定命令長の命令セットにおいて、命令長サイズが 32 bit であっても、64 bit のメモリのアドレスの先を指し示すことができるのか？というのが次に疑問として湧いてくるかもしれないが、一般には 64 bit のレジスタにアクセスしたいメモリのアドレスを入れておいて、そのアドレスを読み出す、というように二段階でメモリ上の値を読み書きするため、 1つの命令がメモリアドレスを指し示す必要は必ずしもないのだ。大抵の場合でレジスタの本数は 8 bit に収まるため、 32 bit の命令長があれば、レジスタを指し示すことは十分にできる。そこで、基本的には計算は全てレジスタ上で行う。これをロードストアアーキテクチャなどと呼んだりする。
ともかく、0/1で表現された機械語の命令を CPU は読み込んで実行していくと仕組みになっており、基本的には命令の順番通りに実行される *4。
機械語とアセンブリ言語、高級言語の関係
機械語を人間が読み書きして理解することは一般には極めて困難である。機械語の代わりに命令やレジスタを、ニーモニックと呼ばれる文字列で表現することがある。これがアセンブリ言語である。アセンブリ言語はその意味では機械語とほぼ同じであるといえるが、幾分リーダビリティが高いといえる。
今見てきたように、アセンブリ言語は CPU の命令セットに依存する。つまりあるプログラムを書くときに、アセンブリ言語で記述しようとすると、その CPU の仕様を熟知していなければならないし、異なる命令セットのマシンで同じプログラムを動かす（移植する）ことが極めて難しくなってしまう。低レイヤーのプログラムや速度を重視したプログラムでは CPU の機能をダイレクトに使うために、そのようなコードを書かなければならないのは仕方ないが、そうではない場合、言い換えると一般のプログラムを記述する場合では、CPU 上での具体的な動作（例えば変数をどのレジスタに置くか）を気にせずに書きたい。そこで、アセンブリ言語より抽象的な言語でプログラムを書いておいて、実際にプログラムを実行する前に、そのソースコードをそのマシンで実行できるように機械語に翻訳するという仕組みを設けることを考える。この仕組みをコンパイルと呼び、より抽象的な言語のことを高級言語と一括りに呼ぶことがある。別の方法として、ソースコードを解釈して実行するプログラムを用いることもある。この仕組みはインタプリタと呼ばれる。高級言語の中にはC言語とか Python とか Ruby とかが含まれる。
こうした高級言語とコンパイル（あるいはインタプリタ）の仕組みがあることによって、普段我々はどの CPU 上で動作するマシンかということをそれほど気にしなくても、抽象的に命令を記述することができる。しかしながら、こうした高級言語のプログラミングのやり方と、アセンブリ言語でのプログラミングのやり方が異なるがゆえに、先入観によってアセンブリ言語ではどのように書けば良いのかということがわからなくなってしまうというのが、ここで取り上げたい話題である。
if 文による世界と jump 命令による世界がある
よく見る高級言語では、条件分岐があったときにこのように書きたいと思う。これが普通の人が想像しやすい if 文の書き方である。
if x == 0 # do something if the condition is satisfied else # do something if the condition is not satisfied end # do finally
if 文の下には、if 条件を満たしている場合の処理を記述する。これをフローチャートで記述すると、以下のようになるだろう。
ここで、 jump 命令でこの if 文相当の処理を書くとしたらどうなるだろうか。ここでは、 無条件で jump する命令と、条件付きで jump する命令を使って、例えば PowerPC 風の記述で書くとこのようになるだろう。条件付きの jump 命令とは、jump if negative であれば負の時にジャンプ、 jump if zero であれば0の時にジャンプ、といったものである。
(前略)
be %cr7, .IfZero
# do something if the condition is not satisfied
b .Finally
.IfZero
# do something if the condition is satisfied
.Finally
# do finally
ここでの記法を説明すると、ドットで書き始めている行はラベルであり、b は、無条件でラベルの行にジャンプする命令、be は、条件付き（ここでは、0に等しい時）でラベルの行にジャンプする命令、 %cr7 は適当に指定したレジスタであるとみなしてほしい。ここで、先ほどの if 文を使ったプログラムに比べて、いくつか注意しなければならないことがあることがわかる。
be命令の下に書くのは、条件が満たさない場合の処理であって、条件が満たされている場合の処理は jump した先に書かなければならない。- プログラムは上から下に処理されるので、
jump命令で.IfZeroラベルの中身をスキップしないと、.IfZeroラベルに下に書かれた行の処理も順に実行されてしまう。
つまり、if 文では暗黙のうちに「if 節の処理を行なった場合は else 節はスキップされる」ということが仮定されているが、それらの処理を全て明示的に jump 命令を使って記述しなければならない、ということである。これをフローチャートで表現すると以下である。
抽象的なフローチャートをトポロジカルソートしたい
つまり条件分岐がある時に、脳内で想起される最初のif文のフローチャートを、jump 型のフローチャートで表現されるように、全ての処理を一列に並び替えて記述する必要がある。そして、次に行いたい処理が1行以上飛んだ先になる場合は、jump 命令でその間をスキップする必要がある。なので、プログラムに分岐が発生する場合、路線図で言うところの、別の路線に分岐して、最終的に合流する、と言うような路線ではなく、路線の中で快速と特別快速で停車駅が異なって、千鳥停車になっている、というような路線であるというように想像する必要がある。肝心なのは、if 分岐をしたい時にこうした構造を想起して、コードに書き起こすということを毎回する必要がある、ということである。
これをどう理解するかについて、 一つのアイディアとしては、 if 文を書きたい場合は、まずは jump 命令を用いて枠組みを作って、その中に条件が真の時の処理、偽の時の処理というように書く、とパターンで認識することもできるが、ただしこれも、 else 節の処理があるかないか、 finally の処理があるかないか、あるいは入れ子の if 文があるか、ということによって、実際にはさらに最適化できるコードにはなってしまう。やはり原理に立ち返って、あくまで記述の通りに処理を忠実に行なっていく、ということを理解してプログラムを作っていくのが良いのではないだろうか。
