レジスタ割当
前提問題
Forth系の言語の場合、構文解析や意味解析はコンパイラをつくる時点では考える必要がない。詳細はプログラミング段階に回せるからだ。すると考えなければならないのは初っ端から最適化ということになる。今日のコンピュータはほとんどがレジスタマシンであるため、レジスタをどのように割り当てるかがまずは最重要課題となる。
レジスタマシンとは、レジスタと呼ばれる小さく高速な内部記憶装置を備えたコンピュータのことと思って良い。レジスタは変数の一種と考えてもよい。数値やメモリ内のデータをできるだけレジスタに保持して処理することで高速な処理が可能となる。64ビットマシンといわれるのは、このレジスタ1本で2進数の64桁まで記憶可能な機械のことである。３２ビットなら32桁である。x86は古い汎用機仕様であるため、もともとは、このレジスタは8本しかない。64ビット（8バイト）に拡張された際に個数が倍増され16本となった。64ビットモードは、これにさらに浮動小数点数（若干誤差のある小数）も整数も扱えるベクトル演算（一つの命令で並行して何個かの四則演算を同時にできる：最近は英語に似せてベクターということが多いようだが、自分にとってはベクトルは日本語だ）用の128ビット（16バイト）レジスタ16本が追加された。従来x86で小数演算に用いられた80ビットFPUレジスタ（x87）については今も8本に止まっているため、x86-64最適化の解説本では、通常の小数演算に関しても128ビットベクトルレジスタの下半分のビットを使うことが推奨されている。64ビットでいわゆるダブル(double)小数の規格を満たす。Mac OS X（あるいはGCCというべきか）はその推奨に遵っているようだ。iMopsでも同様である。
従来のx86から見れば16個のレジスタは極めて多いように見えるのかもしれないが、PowerMopsが稼働するPowerPCという機械は、整数および小数用に各32本のレジスタをもっている。さらに倍、である！これはRISCとCISCという仕組みの違いも絡む。しかし、概して言えば、レジスタが多い方が最適化しやすい。8本だと通常数値へのレジスタ利用は一つか二つが限度でほとんどあてにできない。逆に言えば最適なレジスタ割当など考えなくてもほぼ決まっている。16本あればまあまあ割り当てられるがまだ窮屈である。そして32本もあれば、もうふんだんにあるといって良い感じである — ただしforthを前提した場合であるが— 。16本というのは特に整数レジスタでは微妙なところなのである。ちなみに、コンパイラ技術ではレジスタ割当は高等な分野とされているらしいが、英文のコンパイラ上級テキストでも論文等でも、大抵は仮想的なRISCマシンでレジスタがふんだんにある状況を想定している。デスクトップで圧倒的なシェアのx86はCISCであるしレジスタ数も少ないので、あまり実践的想定とは言えない。スマートフォンなどで利用が拡大したARMはRISCだがレジスタ数は16本に止まる。（新しい64ビット規格では32本に増えたようである。）
そのようなわけで、16本の整数レジスタという微妙な数で最適化を目指すことになるわけである。ちなみに、小数レジスタの方は、16本もあれば十分という感じだった。整数レジスタと小数レジスタのこのような状況の差異は、メモリーアドレスは整数とされているという事実からくる。小数レジスタも実際はベクトルレジスタであるから整数を格納することはできるが、その値をメモリーアドレスとして扱う機械命令は組み込まれていないのである。そのため、内容となる値が整数であろうが小数であろうが、メモリーとの間で値をやり取りするときには必ず整数レジスタを一つそのために消費しなければならないことになる。それが整数値処理に割り当てられるレジスタを圧迫するのである。他方で小数レジスタは数値のみを扱えば良いので負担は軽く、同じ16でもその使用感は大きく異なるのである。
ノードグラフ
レジスタ割当はノードグラフで考える。
ここでいうグラフは、いわゆるグラフ理論の有限グラフだが、有限個のノード（結節点）の関連あるもの同士をエッジ（辺）で結んだもの、というイメージで良い。iMopsではこれをそのまま実装した。エッジは双方向リンクである。ノードとして何を採るかは色々あり得るのかも知れないが、iMopsではスタックアイテムを採った。普通の言語なら変数を採るところだろう。ノードは初めて用いられたときに生まれ、最後に用いられたときに死ぬ。このライフタイムが重なりあうノード同士は干渉する(interfere)という。干渉しあうノードには同じレジスタを割り当てることはできない。
これは「隣り合う領域同士は異なる色でなければならない」という条件のもとで、分割された小領域を分割数より少ない色数で色分けする有名なアルゴリズム問題と同値であることがわかる。“如何なる場合も効率的に解ける手順”というものはないらしい。一般の有名変数を用いる言語なら確かにあらゆる場合が考えられる。しかし、forthの変数にはスタックというデータ構造がある。この構造の制約を加えると配分問題はほとんど自明になるように思われた。というのは、スタックでは演算に供せられるノードはトップから順に取られ、一度使われればアイテムはなくなる。トップアイテムは直ちに使われて費消されるが、スタックの下方に行けばいくほど、長い間使われないことになる。とすれば、トップから順にレジスタを割り当てて、足りない部分はメモリアイテムを割り当てるのが、当然、最も合理的な配分であり、それで最適化はできたことになる。もっとも、スタックを深くかき回すワードもないではないので、そのような場合は別のやり方が最適になる場合もあり得るが、それはよっぽどヘタクソなforthプログラムでもなければ滅多に起こらないことだ。
そのようなわけで、レジスタ割り当ての最適化は極めて簡単になる。まずはトップから、ということだ。
ノードの連結
ノードの連結の問題は、スタックというデータ構造の特性をその基本的前提としている。ノードの同一視・保持の問題であれば値の同一性が基準となる。しかし、ここでいうノードの連結においては、その格納場所としての同一性、つまり変数としての同定こそが本質的である。
スタックアイテムは、一度使用されるとそこで消費され、そのアイテムに対応するノードは、そこで消滅することになる。これがforth系のノードを追跡する場合の際立った特徴となる。したがって、演算とともにノードの消滅と生成が繰り返されるのである。
そのような、いわば切れ切れのノードを、値の関連によって連結しようとするのがここでの問題である。
専門書や論文で前提とされているRISCマシンでは、例えば足し算などの二項演算は、二つの入力と一つの出力について、都合三つのレジスタが利用できる場合がほとんどである。しかし、x86では、通常は、二つしか使えない。つまり、一方に他方を足すという操作になるのであって、入力値の一つは破壊されてしまう。
演算によってアイテムが破壊されるスタック演算にとっては、これはそれほど困った事態ではない。しかし、問題は、このようなマシンの演算特性とスタックの状態をノードグラフにおいて結びつけるということである。
具体的にいえば、x86では破壊される入力オペランドは出力オペランドと一致するので、それらに対応するノード同士をリンクしておくのである。そうすれば、リンクを辿って同じ変数（レジスタないしスタックセル）を割り当てられる。このリンクがノードの関連ということであり、これをすることでスタックの状態とマシン演算が結びつけられるのである。
結局、二項演算では、破壊的に演算結果が格納されるレジスタは関連ノードとして接続されていき、もう一方の入力は、値は残っているものの、スタックアイテムとしては放棄されるので、ノードとしては消滅することになる。
ちなみに、多くのRISCマシンのように、出力に別レジスタを利用できるのであれば、ノードはバラバラのままでよく、連結などする必要はない。
最適化しないやり方（ノードグラフ不要）
x86はレジスタが少ない代わりに、メモリー領域を演算のオペランドにできる。ただし、メモリーアイテム同士で演算することはできない。少なくとも一方はレジスタでなければならない。そこで、直ちに考えつくのは、スタックのトップをまずレジスタにロードし、それに演算を加えていく、という手順である。このやり方だと、ノードグラフなど作る必要が無い。一つ一つの演算に適当なロード（ポップ）とストア（プッシュ）を付け足した上で順にコンパイルしていけばよいだけだ。
簡単な最適化
しかし、いちいちロード／ストアを繰り返すのは、キャッシュは効くとしても、いかにも効率が悪い。トップアイテムはできるだけレジスタに保持しておいて、どうしても必要なときだけスタックに退避させれば、それだけでも実行速度はかなり上がる。32ビットのforthの多くはこのような最適化を図っている。32ビットでは汎用レジスタが8本しかないが、アイテムキャッシュ用レジスタが一本だけあれば足りるこの方法なら実現可能である。この場合は、トップアイテムが現在どこにあるのかについて常時監視する必要があるだろう。しかし、グラフといえるほどのノードデータは必要ないのではないかと思われる。
最適化の方法
iMopsの採った効率化方法は単純である。演算をまず、ノードリストの上に書き込んでいくのである。最後に生まれたノードはスタックの頂上にある。演算は、生きているノードを上から取って演算項として、結果をまたノードリストに追加する。演算項として取られたノードは、その時点で死ぬわけである。操作一つ毎に、グローバルにステップを進めていく。X86はCISC型の演算で、二項演算は結果を入力項のどちらかに書き出すしかない。つまり、入力破壊的な演算である。そのため、演算項の一方は出力と同じレジスタ（メモリ）にならなければならない。そこで、スタックの下の入力ノードと出力ノードを相互リンクする。レジスタ割り当てのときには、このリンクを辿ってノードを統合していく。スタック操作ワードも、ノードのリンクで済ませる。結果として、演算直前のスタック操作は大抵何の動作も必要なくなる。
もう少し具体的に書いてみよう。
iMopsはヒープ上に256項目（1項目はスペア）のリストを持ち、各項目にはIDとして初期化の際に番号を打ってある。スタックノードは下方に伸びていく可能性もある（入力項目を消費していくばかりの場合）ので、リストのやや上方に基準点を設けて、そこから演算の疑似コンパイルを開始する。例えば、二項演算がコンパイルされれば、その入力として２つの項目が取られる。既に生きているノードが２つ以上あれば、そのトップ２つを取れば良いが、足りない場合は下方に伸ばしていく。そして、出力ノードは、上方に伸びるように取り、出力ノードの方に何の演算であるのかを書き込む。そして、入力ノードのID番号を入力として出力ノードのオペランドデータフィールドに記録し、上に述べたような双方向リンクを、通常は一方の入力ノードとの間に形成する。これを基本ブロックが尽きるまで続けていく。
リンクで結ばれているノードは、同じレジスターあるいは同じメモリーフィールドであることが望ましいノードである。したがって、レジスターをまずトップに配置し、リンクがあれば、それをたどって、リンクが尽きるか、他の理由によるレジスター配置と衝突（interfereないしcollision）する直前まで、同じレジスターを連続的に配備していく。スタックキャッシュ用のレジスターは4つ確保してあるので、その４つを、まだレジスター配置されていないノードを上から順に、同じようにたどって配置するのである。そして、レジスターを配置できなかったノードには、メモリーフィールドが配置される。スタックポインタからのオフセットが、そのアイテムを特徴付けることになる。
コンパイルに際しては、下の方のノードから演算表示を持つかどうかチェックし、コンパイルすべき演算表示をもつなら、入力ノードがレジスタかメモリーかをチェックしつつ、順にマシンインストラクションを生成していく。ノード上への演算記録が下から上へ向けて行われるのであるから、そのマシンインストラクションの順序は、記録された順序に一致するはずである。
基本は以上のようなものであって、若干の調整と、いくつかの細かい省略（最適化）が付け加えられるだけである。発想としては、多分、いわゆる「貪欲アルゴリズム」になるのだろう。考えは単純である。結果も、この場合は、まあまあのようである。
したがって、iMopsのコンパイルは二段構え（２パス）ともいえる。いったん、ノードグラフに書き込み、そこで可能な最適化を行っているからである。しかし、グローバルな最適化は特別にはしていない。Forth系言語の直截性のおかげで、構成もコーディングの段階で考えて確定できるからである。
具体的局面
iMopsでワードがコンパイルされるとき、具体的にコンパイルされると想定されているコードを説明してみよう。もちろん、これは予定通りに動いた場合であって、状況によってはあまりうまくいっていないかも知れない。
まず、ワード定義の初めの方にスタックアイテムを消費するインラインワード（四則演算やスタック操作ワードがそれに当たる）があれば、そこに必要な入力ノードと出力ノードが配置される。この位置では通常はレジスターが衝突することはない（４つまで）ので、入力出力ノードにはレジスタが割り当てられる。その場合、今定義しているワードの入力としてもレジスタが用いられるようになり、そのデータはワードに付帯するデータとしてディクショナリ内に記録される。このデータは、このワードをコールするときに利用される。
全般的レジスタ割り当てと実際のコンパイルは、何か他所でコロン定義したワードを呼び出したときや、ループ、条件分岐を引き金として起こる。
条件分岐もループも、基本的にはワード呼び出しの場合に準じた扱いになっている。したがって、ワードを呼び出す際に起こる状況を説明しよう。
まず、ワード呼び出しをコンパイラが感知したとき、呼び出されるワード(Callee)の入力および出力での利用レジスタのデータをディクショナリから読み取る。呼び出されるワードは既に機械語へのコンパイルが終わっているから、入出力レジスタの個数も、レジスタ番号も確定している。そこで、まず入力レジスタデータを用いて、まだコンパイルされていない呼び出し側の出力ノードに上からレジスタ配置する。
例えば、呼び出されるワードの入力レジスタが二つで、スタックの上からRDI、RSIであったとする。そのときは、ノードリストの生きているノードのうちトップ二つに、RDI、RSIを配置するのである。そして、まずRDIを、既に配置されているレジスタ状態と衝突しない限りにおいて、リンクをたどって遡る形で、最大限まで配置していく。これはいわゆるcoalescingされたノードである。次に、RSIが配置されたノードも、リンクが延ばせる限り、遡って配置する。
続いて、残ったノードにも、上から順にレジスタを配置する。これはつまり、後から生じたノードを優先的にレジスタ割り当てするということである。これも衝突しないように可能な限りリンクを遡って配置する。もしもリンクを遡ったとき、既にレジスタかメモリーが配置されているノードに行き当たったときには、その場所にMOV（ムーブ）オペレーションを指定しておく（まだコンパイルはしない）。どうしてもレジスタを割り当てられないノードにはメモリー上のスタックアイテムを指定しておく。
最後に、メモリーに指定したノードについて、スタックポインタからのオフセットを計算する。基本ブロックの最初の段階のスタックポインタの値が、ブロックの終了直前まで保持される。したがって、メモリーノードのオフセットは、それを基準として位置指定される。リンクされているノードはもちろん同じオフセットが入らなければならないので、まず、一つオフセットを指定したなら、その値を、やはりリンクを使って拡張していく。次からは、このノードと干渉するメモリーノードのオフセット指定に際して、このオフセットの値と矛盾しないように計算しなければならない。ここは少し面倒であった。
レジスタとメモリーの配置が終わったなら、基本ブロックの頭から、マシンコードに変換していく。
その後はスタックの調整をしなければならない。
まず、基本ブロック終了時に、呼び出されるワードの入力レジスタ個数２個を超えてスタックアイテムが生存している場合、それらのノードはスタックメモリーの適切な位置に格納しなければならない。生存ノードはメモリーノードの場合もレジスタノードの場合もあり得る。メモリーノードである場合は、臨時用のレジスタを経由してスタックの適当な場所に移す。実はこの部分がもっとも難しかった。というのは、スタックに残っているまだ有用な値を上書きすることなく、適切な順序で配置換えしなければならないからである。せっかくのレジスタアイテムまでここでメモリーに格納してしまうのは、スタックキャッシュ用のレジスタは、スクラッチで使うことになっているから、呼び出し前のレジスタの値が、戻ってきた後まで保持されている確率は極めて低いからである。加えて、決定的な理由は、呼び出されるワードの側は、入力レジスタ以外のスタックアイテムを使うかも知れず、そして、それはスタックメモリーにあると想定しているからである。
これで出力状態でのスタックの高さが決まる。これにあわせてスタックポインタレジスタの値を調整し、そしてCALLのインストラクションをコンパイルする。
終わりは、また新しいブロックを始める。その際に、呼び出されたワードの出力レジスタのデータを利用する。例えば、出力レジスタが１個で、RDIであったとすると、新しいブロックは、ノードが一つある所から始まる。そして、そのノードにはRDIが予め配置され、変更不可マークが付けられる。これが、次の基本ブロック開始時におけるスタックのトップアイテムになる。二つ目の基本ブロックからは、前のブロックの結果を前提につないでいかなければならないのである。
余談
コンパイラ設計ではレジスタ割り当て（割り付け）の問題は最適化の重要課題であるが、高級言語でも、プログラマーの意志で変数をレジスタに割り当てるように指定できたりする場合がある。この場合も、どの変数にレジスターを割り当てるのが最も実行速度向上に寄与するかを考える必要はある。しかし、現実問題としてこれは極めて難しい。「よく使う変数をレジスタに」という基準では、おそらくダメであろうということは容易に想像できる。これは、高級言語では、周辺がどういうコードで処理されているかが想像しにくいからである。
まず、レジスター変数を指定したとしても、どのレジスターが使用されるか当てにならない場合が多い。使用されるレジスターが、もともとサブルーチン呼び出しの前後に常に保存・回復されなければならないものとされているレジスターならばよいが、そうでない場合、レジスタ変数として使うことでメモリーへの保存・回復操作が追加されてしまうことになる。むしろ通常はスクラッチで使うレジスタを利用するから余分な保存・回復操作は普通は増える。レジスタ変数として指定したとしても、特別にレジスタの個数が多い場合を除けば、その変数のためのメモリー領域は、使おうが使うまいがとりあえず確保されなければならないだろう。大抵の言語では、サブルーチン（関数）のパラメターはスタックメモリー渡しであり、局所変数もスタックフレームをつくって割り当てる。そうだとすると、メモリーフレーム内にレジスタの内容を何度も保存したり読み出したりするくらいなら、原則としてメモリーレファレンスのまま使用し、必要に応じてレジスタに取り出す方が、高速な処理が期待できる。
実際、スタックフレームを固有データ域とするサブルーチンを単位とするような実装法の言語では、やみくもにレジスタ変数を指定しても効果は上がらないであろう。（昔はレジスタ変数指定をしても無視するコンパイラがほとんどだったとか。）リーフコール（他のルーチンを呼び出さないルーチン）最適化としてならば意味はあるかも知れない。けれども、その状況でさえ、コンパイラがどのようなコードを生成してくれるか分らない状況では、レジスタ変数指定しても高速化はほとんど当てにできないものと思われる。
最終更新：2019年06月28日 14:45
