Mopsでは、forth一般の傾向に反して、伝統的にLocals（局所変数）に比較的高い優先順位を与えている。Localsを定義した場合、少なくともいくつかはレジスタ変数にすることで、局所変数を効率の良いものにしようとしている（PowerMopsでは全てレジスタ変数で、10個まで可能である）。ここでは、その実装法について説明してみようと思う。コンパイラー作成上での局所変数の実装法一般の話としても意味があるのではないかと思う。
局所変数の実装
一般論
局所変数とは、一般に、１つのサブルーチンの定義の中だけで同一性を保つ変数のことといえると思う。プログラム上は変数名で特定される。数値格納領域は、理屈の上ではどこにあってもよいわけだが、普通は、リターンスタックにメモリー枠を確保する。そして、コンパイル中は、プログラム上の変数名と、スタック内のメモリーフーレム中の特定の場所とが結びつけられることになる。
レジスターが少ない環境（x86のような）では、全部メモリーアイテムとして設定するのが標準的なやり方で、そのフレームの端のポインターを特定のレジスター（R(E)BPというレジスタがそれ用だったようだ。名前のBPもベースポインタである。）にエントリー時に格納して、それからのオフセット（メモリーアドレスのズレ幅）が、各変数名と同一視される。つまり、ベースからその分だけズレた位置にあるメモリーフィールドが、その変数の格納領域なわけである。局所変数用に配置されたメモリー領域は、そのサブルーチンからリターンするときに、まるごと捨てられる。といっても、何か廃棄のための処理するわけではなく、リターンスタックポインターレジスター（R(E)SP）の値を、入ってきたときと同じ値に、ガクンと変更するだけであって、機械命令としてはたった一つ、場合によっては、リターン命令の中に含まれてしまっていることもある。つまり、ゴミは単に置き去りにされるだけである。その同じ領域が、後から全く別のルーチンの別の局所変数のための場所としても使われるので、使おうが使うまいがいつも領域を保有し続ける大域変数と比べ、局所変数はメモリー効率はよい、ということになる。
他方、そのようなものなので、局所変数の値の初期化を忘れてそのまま使ったりすると、前に誰が残したのか分からない変数のゴミの値、それどころか、その一部の破片が、新しい変数の値として使われたりすることもあるのである。また、ヒープにメモリー枠を確保して、そのポインターを局所変数に格納したまま解放し忘れてリターンすると、そのまま行方が分からなくなって、メモリーリークということにもなる。
以上が標準的な局所変数実装の特徴である。
レジスタ変数
スタックフレームに割り当てられた変数でも、演算上の必要で一時的にレジスター上に存在していることは当然あるのだが、ここでいうレジスター変数とは、１サブルーチンの実行中一貫してレジスターに結びつけられる変数のことである。
レジスタ上の値の操作は、データキャッシュがバッチリ効いたメモリー上の値と比べても数倍速い（CPUによるが）。だから変数をレジスター上に配置できれば、より高速な演算が期待できる。それでは、サブルーチンとしてみた場合、レジスタ変数をたくさん保持した方がいつも高速かというと、実際は必ずしもそうではないのである。
どういうことかというと、サブルーチンは、普通、別のサブルーチンを呼び出していることが多いのである。変数用に割り当てたレジスターが、呼び出し先のどこかで利用されるかも知れない。だから、他のサブルーチンの呼び出しの前後でレジスタ変数の値を同一に保つには、レジスタの保存回復操作が必要になる。もし、１０個のレジスター変数を持っていて、他のルーチンを１０回呼び出したとすると、素朴にやれば、レジスタ１００個分のメモリー保存と、１００個分のメモリー読み出しが追加されることになるのである。もともと変数がメモリーフレームに配置してあれば、呼び出しの前後で何もしなくても値はそのままなのだから、その保存回復操作は要らない。ここでの効率云々は、メモリーアクセスというのは遅い、という話だったのだから、この、変数用レジスタの保存回復の負担分を上回るような演算処理上の利点がない場合には、レジスタ変数というだけでは、コードサイズの問題も含めて、全然効率化にはならないのである。
Forth系であるMopsでは、この辺の判断はプログラマーに任せるという方針である。ただ、リターンスタックを一時変数に使う方法より、局所変数は使いやすい。それで局所変数に頼りがちになる。規準としては変数値の参照回数が多いときには局所変数が有利である。それでも、コードサイズは別として、局所変数を使えば、実行速度がリターンスタックを使うより極端に遅くなることはなく、一般には、より高速である。
それはともあれ、上で触れたような変数レジスタの保存回復の実装方法について考えたこと、具体的には、実装法の選択肢、気づいた問題点、そして実際の選択を、以下で説明したいと思う。
レジスタ変数実装の手順
二つの方法
というわけで、レジスター変数実装のポイントは、レジスタの保存回復（Save-Restore）である。その方法として、２つのやり方が考えられる。つまり、
- 呼び出し側のルーチンが、他ルーチンのコールの前と後に、自分が使っている変数用レジスターを保存回復する方法
- 呼び出される側のルーチンが、自分がこれから使う変数用レジスタの値を入り口で保存、最後に出口で回復する方法
どちらにも、長所と短所がある。
素朴に考えると初めの方法がまず思いつく。実際、これは自然なやり方であって、多分、普通のコンパイラー（だいたいはC言語系）は、そういう処理をするのではないかと思う。けれども、アレコレ考えて、結局は、iMopsでは後者の方法を採用している。実はPowerMopsも後者である。
第一の方法の短所 つまり 第二の方法の長所
呼び出し毎にレジスタを保存回復しているとメモリーアクセスは増える。これが短所である。そもそも、局所変数はforth系では例外的存在である。局所変数を使用しないワードの方が圧倒的に多い（対して、C言語系では局所変数を使用しないルーチンはほとんど無いだろう）。呼び出される側のルーチンがレジスタの値を荒らさない場合でも、使用中のレジスタを全部、保存・回復するのは無駄に思える。呼び出される側がそのレジスターを使うかどうか確認して、使用する場合だけ保存すればよい、と思われるかも知れないが、直接の呼び出し先についてはその情報が得られたとしても、そのルーチンもまた別のルーチンをいくつも呼び出しているかも知れない。呼び出されるルーチンも自分にとって必要な分しか保存回復していないので、呼び出し元ではその次の（呼び出されるルーチンが呼び出す）ルーチンで荒らされるレジスターも知らないといけない。そして、さらにその先も、、となるとコンパイル過程は相当複雑になる。それに見合う分の効率化が期待できるかどうか疑問である。そのようなわけで、結局、値の同一性を保っていて欲しいものは、いつも全部、保存回復することになるのである。
他方、第二の方法は、そのワードが局所変数を使うときだけ、自分が使うレジスタの値をリターン時に元に戻して返す。したがって、呼び出し側では、レジスタ変数を利用していても、保存とか回復とか考えることなく、他ルーチンをそのまま呼び出すことができる。呼び出されるワードの系列の中でレジスタ変数が使われないときには、レジスタの保存回復は全く行われないのである。結果として、レジスターの保存回復は最小限に押さえられ、ワード呼び出しは非常に軽くなるのである。
第二の方法の短所 つまり 第一の方法の長所
第二の方法では、しかし、レジスタ変数として用いるレジスタを固定的に確保しておかなければならないのである。
レジスタについては、スタック上の値をキャッシュするために、スクラッチで使うのが主たる使用法である。このためのレジスタを多く配備できれば、スタック上の計算を主とするforth系環境では、より高速で効率のよいコードを生成するコンパイラをつくることができる。
しかし、変数レジスタは、使用の前後に保存・回復しなければならない。特定レジスタを保存回復するのは、他のルーチンもそれを変数レジスタとして使っているかも知れないと分かっているからである。つまり、この方法の前提として、変数のために利用されるレジスタは、システム全体として特定のものに決まっている、のである。しかも、そのレジスタはスタックキャッシュ用には利用できない。スタックは無名変数であるからその値についてレジスタがどのように使われるかは、事実上予見不可能だからである。下手をするとレジスタは入り口と出口で全て保存回復しないといけなくなる。これでは第二の方法の利点が飛んでしまう。
結局、変数用のレジスタは、それ専用に確保しなければならないということにつながる。その分、スタック計算にまわせるレジスタが減る。
PowerMopsがこの第二の方法を採用しているのには非常に合理的な理由がある。PowerPCはレジスタの個数が非常に多い（整数、小数、各３２本）ので、１０個程度レジスタ変数専用に確保しても、残りはまだx86-64より多い。だから、スタックキャッシュ用のレジスターが不足する事態はほとんど起こらない。
他方、第一の方法を採れば、他のサブルーチンが、どのレジスタをどのように使おうとかまわない。当のサブルーチンが、変数として値を維持しておきたいレジスタだけを保存回復するからである。そうなると、サブルーチン内でのレジスタの使い方は自由になる。局所変数を使わないワードであれば、すべてのレジスタをスタックキャッシュにまわすことができる。要するに、サブルーチン限りでレジスタの使用法を最適化できるのである。
選択
レジスタ割り当てによる最大限の最適化を図るなら、第一の方法を採ることになるのではないかと思う。
普通のレジスタ割り当ての文献では、サブルーチン内でレジスタを自由に使うということが前提となっている。
Mopsの創作者であるMichael Horeさんも、現在、そのレジスターを自由に使う効率化を用いたPowerPCコードジェネレーターの実験をしているらしい。いずれは、iMopsもこの方法を実験してみるかも知れない。
けれども、敢えて第二の方法を採用した。その理由の１つは、呼び出しを可能な限り軽くしたいということであるが、もう１つ、決定的に重要な理由がある。スタックアイテムの「編み上げ」が、思いの外に面倒なのである。これは、変数を名前で特定する方法では生じ得ない問題であり、forthのスタックという無名変数的なコンテキストで起こる特徴的な問題である。
例えば、ワードPの定義中で、データスタックの上から順に、w,x,y,zの値があり、それぞれ、レジスタA,B,C,Dに格納されているとする。
このとき、この値をパラメターとして別のワードQに渡すことを考える。Qはスタックの上からw,x,y,zの値を入力として予定しているとする。値だけならストレートに渡せば良いだけである。しかし、ワードQとしては、それぞれの値がB,D,A,Cのレジスタに格納されていると予定している、という場合が起こり得る。呼び出されるQは通常は、既定義ワードであるから、このレジスタ配置はもう動かせない。それならば、呼び出し側のPの中でのレジスタの使い方をQにあわせればよい。それはそうなのだが、このw,x,y,zの値も別のワードRから返された値であって、Rの戻り値は順にA,B,C,Dのレジスタということで既にコンパイル済みという場合には、どうにもならない。すると、これらのレジスタの値をQに合うように入れ替えてからQを呼び出さなければならない、ということになる。これが、上でいった「編み上げ」である。基本的に単なる置換群であるが、組ひも変換にちょっと似ている。
上の例でいえば
A -> B
B -> D
C -> A
D -> C
というMOVEの変換が必要である。けれども、そのまま順に実行してはいけない。最初にレジスタAをBに写してしまうと、Bの値が破壊されてしまう。ちょうど良い順番と１つ余分に値を取り置く場所があれば、まあ、うまくゆく。けれども、その「ちょうど良い順番」をいつも計算で出せるようなアルゴリズムは、意外に難しい。
まあ、具体的には、数学の置換群の表記法でよくあるように、循環する部分を切り取ればよいのではないかと思われる。上の例では、全体が循環している。どこから初めてもよいが、一番上のAから始めれば、A->B->D->C->Aである。で、Aの値をどこかに保存して、逆順で写していけばよい。つまり、C->A、D->C、B->D、で、最後に、Bには、取っておいたAの値をコピーするのである。
とはいえ、循環の様は、かなり多様になる。特に、メンバーが多くなれば小循環の多様性は増す。
もしレジスタの個数が三つまでなら、変換の全可能性はたった６つ（無変換も含む）である。４つなら２４個。これはかなり面倒だが、想像できる範囲内である。要するに言いたいのは、このアイテム数が増えていくと、組み合わせ、というより順列だが、その可能性の数が飛躍的に増大していくのである。
現状、iMopsで、スタックキャッシュに使われるレジスタの個数は、整数で原則４つ、小数で６つである。もし、利用できるレジスタを全てスタックに用いたとすると、整数で７つになる。７つの値の順列は５０４０通りである。ほぼ、人が直観できる限界を超えている。もちろん、実際の多様性はそこまで多くないだろうが、バグがあったときには、ほとんど追跡できないだろうと思われる。
実際には、コンパイルのときに置換群の問題を解いているわけではなくて、必要に応じてレジスタ値のエクスチェンジの機械命令を用いている（なるべく避けたい）。現在の所、比較的複雑な場合にもバグは顕在化していない。理屈としては、この方法で７つのレジスタを操作することは可能だと思われる。けれども、複雑な機構はできるだけ避けるべきであると思う。問題が出たとき収拾がつかなくなるからである。そして、スタックキャッシュも、レジスタが４つもあれば大抵は十分な気がするからである。あまりに自由化してしまうと、それを調整する手間のせいで、かえって非効率にならないとも限らない。もっとも、あと１つか２つはあった方がいいかな、と思うこともあるのだが。
スタックキャッシュ用に自由にレジスタを使えるというところを除けば、第一の方法には、あまりメリットは無い。他方で、自由にレジスタを使うと、複雑さの問題が生じてくる。第二の方法で、局所変数専用のレジスタを確保しても、スタックキャッシュ用レジスタが減ることによる圧力は大したことではないかも知れない。
ということで、第二の方法が採用されたわけである。
それでも、「編み上げ」の部分は、コード生成のプログラムの、一番キツかった部分のように記憶している。というか、ここが大体テストにパスするようになったところで、なんかできそうな気がしてきた、という感じである。
iMopsの方法
そのようなわけで、iMopsでは局所変数専用のレジスタを３本確保している。６４ビット化で追加されたR15, R14, R13を充てている。この個数を超えると、リターンスタックにフレームをつくることになる。つまりlocalsは、４つ目からはメモリーアイテムである。
局所変数を持つワードは、その冒頭でまず、使う分だけのレジスタをリターンスタックにプッシュする。また、そのワードの実行が終わってリターンする直前にポップされる。
必要レジスタをリターンスタックにプッシュした直後に、局所変数は初期化される。初期値をスタックから取るものは「名前付き引数(named parameter)」ともいう。それ以外の局所変数は、0で初期化している。
初期値をスタックから取る場合、呼び出し側でいったん全てスタックメモリーに格納して、呼び出された側の名前付き引数レジスタは、スタックメモリーから値を取るという方法が、ある意味、一番楽である。けれども、局所変数を用いないワードでは、スタック入力値がある場合、レジスタで受け取ることが多い。この方法が局所変数を用いると使えないのは、何となく不利に思われた。
そこで、名前付き引数レジスタの分のスタックアイテムは、すべてレジスタで受けることにした。
ところが、局所変数用レジスタをそのまま入力レジスタに使うわけにはいかない。というのは、入力レジスタはスタックアイテムキャッシュとみなされて、呼び出し側の定義で遡及的に延長してスタックアイテムキャッシュに利用するようになっているからである。そこで先に値を格納されてしまうと、呼び出された側でレジスタの値を保存回復しても意味が無い。
そのようなわけで、まずはスタックアイテムキャッシュ用のレジスタを入力レジスタとして指定し、名前付き引数の初期化は、レジスタ間のMOVEで受け渡すということにした。無駄なコピーではあるが、メモリーを経由するよりは軽いであろう。局所変数レジスタは最大三本であるが、スタックキャッシュ用レジスタは四本あるので、結局、レジスタ局所変数の分は全て、メモリーを経由せずに扱うことができた。名前付き引数が３つより多い場合には、越えた部分はスタックから渡される。したがって、スタックから値を取り出して、局所変数フレームに移すという作業が追加されることになる。
この種のことを機械命令に変換してコンパイルするには、op-codeなど必要な記号（通常バイト単位）を定数として準備し、
それに必要なフラグを追加して、順にバイトアレイに追加していけばよい。
そのバイトアレイが実行コード部分、UNIX風にいうとtextの部分、ということになる。
ちなみに、PowerMopsでは、局所変数は9~10個の個数制限を受けるが、全てレジスタ変数である。スタックキャッシュとの関係は、ほぼiMopsと同じような実装になっている。（というよりも、iMopsの方でPowerMopsにできるだけ似せているのであるが。）
Localsのデータについては、通常のディクショナリとは別に確保された領域に特別なディクショナリーリストを構築する。ワード定義のコンパイル中、局所変数に関するデータはそこから引き出す。このリストのための領域は、iMopsでは、オブジェクトとしてコード生成機構内に常駐する。PowerMopsではディクショナリの空き領域を用いる。
Localsを持つワード定義中は、変数名は、そのリストの中から初めに検索され、ディクショナリデータに応じて、特定のレジスタなり、スタックフレーム内のオフセットなりに結びつけられて、コードがコンパイルされることになる。
この局所変数ディクショナリ内のデータは、その有効範囲の終了とともに廃棄される。
最終更新：2014年12月06日 08:28
