MinCaml読解ノート改訂

MinCaml 0.0.9に合わせて改訂した。加えてレジスタ割り当ての項を大きく書き直したが、わかりやすくなったのかどうか。不勉強ながらレジスタ割り当ての様子についても理解したと思うところを筆を加えたが、こちらは正直言って自信がいまひとつである。

21st Century Compilersの一部(?)をオンラインで読む

2006年10月3日追記: いささか旧聞だが、先月頃に Compilers: Principles, Techniques, and Tools, 2nd Edition としてようやく出版され、入手できるようになった。以前と違った美しいイラストの表紙にちなんで、パープル・ドラゴン・ブックと呼ばれる(1986年出版の以前の版はレッド・ドラゴン・ブックと呼ばれた)。大著にも拘らずアマゾンで洋書ランキングで現在881位、さすがに待っていた人は多いようだ。

12月6日追記: Compilers 1/e plus Selected Online Chapters from 2/eが日本のamazonでも掲載され注文可能になったようだ。しかしお高い。

12月2日追記: 21st Century Compilersが日米amazonから消えてしまった模様である(ペーパーバックの方はまだ生きている)。出版を諦めた筈はあるまいから、"1/e plus online chapters" を出してから改めて予定に載せるつもりなのかも知れない。

「コンパイラ」(通称ドラゴンブック)の新版と楽しみにしているのに出版の遅れ続けている21st Century Compilers (ペーパーバックもあるようだ。少し安い) だが、それとは別にCompilers 1/e plus Selected Online Chapters from Compilers 2/eという出版予定がいつのまにか立っていた。どうもこの第2版というのが21st Century Compilersを指すように思われる。

このonline chaptersは既にプレビュー扱いで公開されていて、http://www.aw.com/dragonbookから辿ることができる。断り書きによれば2006年1月1日までは自由に見ることができ、以後は登録が必要となるとのことで、おそらく上記の「新しい初版」の購入が必要になるのだろう。

表示にはFlashが使われ、紙面と同様の体裁で一ページごとに表示される。Flashのバージョン6ではだめだったので、7か8以上が必要と思われる。文字は綺麗にアンチエイリアシングされるので見易いが、検索や栞といった機能はなく使い勝手はAcrobatに劣る。本公開でも同じ仕様になるのか、より使い易いインタフェースになるのかはわからないが、本公開も同じだとすると $105.20 は少々高すぎるように思う(しかも21st Century Compilersの予価よりも高価である)。 ただ、書籍の方も初版と同じ筈が何故か200ページほど増えているのでそちらの理由も多少気になる。

オンラインになるのは第5章から第11章で、予定の全12章中重要な部分はほとんど読めてしまうことになる。実際、ざっと見たところでは9章と10章は尻切れとんぼのようにも思えるものの、ほぼ全てのページを見ることができた。しかも気前のよいことに、プレビュー段階の現在でも印刷までできる。

穿った見方をすると、遅れに遅れた上に12章を書くにはまだ時間がかかりそうだから、おまけのような12章は措いてもとりあえず世に出すためにこのような体裁をとったとも考えられる。著者の先生方には頑張って仕上げて欲しいが、こういったサービスは嬉しい。

年が明けてしまうと無条件には読めなくなりそうだから、正月休みの暇潰しにしたい向きには今のうちに一手間かけた方がよいだろう。

Tutorial on Good Lisp Programming Style

Lambda the Ultimateより。 Peter NorvigとKent Pitmanによるスライド。

Lispのプログラミングスタイルとして出色であるが、そればかりでない。 名前の付け方、コメントの書き方、コードの書き方などにおける「なぜそうするのか」というwhy、つまり原理原則に重点が置かれており、Lispに限らず示唆に富む。

具体的なコーディングの話では、Lispの構文・機能面の話もあるもののえ主眼は4つの抽象化(Data Abstraction, Functional Abstraction, Control Abstraction, Syntactic Abstraction)によるdecompositionに置かれている。 具体的な悪いコードとよいコードの対比を理由つきで示して説明されていてわかりやすい。

マクロによるSyntax Abstractionはもちろん、 最近関数型言語を学んでようやく知るようになったControl Abstractionも CやC++といった手続き型でしか書けない言語の知識のみでは気付かないことで このようなスライドが1993年に書かれていたということ、それを生んだLispの力に驚く。

116ページの大作だが、スライドなのでpsnup -4して両面印刷すると15枚で読み易く収まる(元がレターサイズである点に注意)。LtUにはPDF版へのリンクもある。

MinCaml: 早期退避型レジスタ割り当ての後戻り解消

書いた後になってregAlloc.target-latespill.mlとして類似の構造が既にあったのに気が付いたので、説明は簡単にする。

MinCaml 0.0.9のオリジナルのregAlloc.mlはレジスタ溢れが発生するたびにToSpillを返して溢れた変数が定義された時点まで遡って処理をやり直す。 この構造は次の二点を目的としている。

1. 変数定義の直後に、変数をスタックに記録するSave仮想命令を挿入する。
2. (Forgetノードの効果) その命令の直後にForgetノードを挿入してレジスタから溢れる変数を以後使われないよう見せかけることで、やり直し時にレジスタ割り当てを意図したレジスタに行わせる。

Forgetは一見、挿入した直前の命令のみならずそれ以前の命令にも影響するように思えるが、溢れさせるレジスタの選択方式を考え合わせると実は影響がない。call命令直後に挿入するものは例外だが、これは自由変数の収集時にtargetと同じくcall命令より先は見ないという配慮をすれば不要にできる。

従ってやり直しはレジスタ溢れを起こした命令だけでよいので、後戻りなしでも同じレジスタ割り当てが可能である。

(上記は誤った理解に基いた記述であり、レジスタと変数の対応は変わり得る。コメント欄に頂いたご指摘及び改訂したMinCaml読解ノート: レジスタ割り当てを参照。ただしレジスタ溢れの発生回数については後戻りなしでも同じくすることがやはり可能であると考える。以後もそれを踏まえて読まれたい。)

この点を踏まえ、本変更では前述の二目的をそれぞれ次のように実現する。

1. Save仮想命令を全ての変数について挿入しておき、そのうち不要なものを最後に一括して取り除く。要不要は変数がRestoreされるかどうかで決定できる。
2. 次の命令に渡すregenv(レジスタと変数の割り当て表)を直接操作する。また、割り当てるレジスタを決定するときに、自由変数の収集を関数呼び出しより先は考慮しないようにする(targetが既に行っているのと同じ配慮)。

ソースファイルはregAlloc.target-earlyspill-nobacktrack.ml。前述のようにオリジナルのregAlloc.mlよりもregAlloc.target-latespill.mlに近く、わかりやすさはそれとほぼ同じ。

比較

ほとんどのケースで0.0.9のオリジナルのものと同等のコードを出力する。唯一、test/non-tail-if.sでは僅かによいコードを出力した。

追記: テストプログラムはないもののレジスタ割り当てが悪化するケースもあるとの指摘を頂いた。コメント欄参照。

応用

余分に挿入しておいて後から不要なものを削除する、若しくは必要なものを後から挿入するという手法はRestoreにも応用できる。

関数呼び出しによりレジスタが全て破壊されるが、ここで適当な変数を仮にRestoreしてしまうことで、その後に分岐があり一方の枝と分岐の合流後でその変数を参照するような場合にロードを削減できる場合がある。余分な仮のRestoreは最後に削除する。但しtargettingを阻害しないよう仮Restoreするレジスタには条件がつく。

regAlloc.mlのバリアント

最後に、MinCaml 0.0.9に含まれるregAlloc.mlのバリアントを簡単に紹介する。後のものほど前のものよりデグレードされている。

regAlloc.target-earlyspill.ml

regAlloc.mlと同一。

regAlloc.target-latespill.ml

後戻りなし。変数の退避を、レジスタから溢れる直前に行う。同じ変数が二度三度退避されることが起こり得る。また、割り当てるレジスタの決定では関数呼び出しより先の参照を考慮してしまう弱点が存在する(Forgetを使わないにも関わらず、前述のtargetと同様の配慮がなされないため)。

regAlloc.target-nospill.ml

後戻りなし。レジスタが不足したらコンパイルを断念する。

regAlloc.notarget-nospill.ml

後戻りなし。レジスタが不足したらコンパイルを断念する。レジスタ割り当ては次にどのレジスタに割り当てるのがよいかは考慮せず、空いているレジスタを番号の若いものから順に使う。

MinCaml 0.0.3から0.0.9の変化

MinCamlの現在のバージョンである0.0.9の、MinCaml読解ノートを作成したときのもの(バージョン0.0.3に相当するようだ)からの変化を整理した。字面や表現上の変更を除くと概ね以下の通り。

言語仕様の変更

• let recが関数定義を一つだけに簡略化された。相互再帰する関数をandで並べて定義することはできなくなった。

但し入れ子にすれば相互に呼び合う関数を定義することはできる。test/even-odd.mlを参照。

内部仕様・動作の変更

• 言語仕様の変更を反映し、構文木(Syntax.t)と中間コード(KNormal.t)でLetRecの保持する関数を一つに変更。
• Syntax.tからNEq, Ltを削除。Eq, LEとNotの組み合わせで代替する。KNormal.tの表現に合わせたもの。
• 字句解析器は負の数値リテラルを単項マイナスと非負数値の2つのトークンとして返すようになった。
• 浮動小数点レジスタはSPARCで使える16個全てを利用するようになった(以前は何故か8個だけだった)。
• 定数畳み込みで即値の伝播を浮動小数点数についても行うようになった(以前は忘れられていた)。(記述は追加されたがコメントアウトされている。意図して外していることを示すためと考えられるが、改訂した読解ノートでも指摘したように浮動小数点数でもこれを避ける理由はないように思われる。)

最後の二件は以前にMinCaml読解ノートでも指摘した点が修正されたもの。

尚、浮動小数点レジスタ個数の変更に付随してエンバグしている(実害はない)。sparcAsm.mlでのco_freg_tableの計算において、ループ回数が一回多い。

実装の変更

この二点が両バージョン間の実質的な改良点と言える。

• レジスタ割り当てコードの簡素化。参照した変数がレジスタ上にない場合の処理を、命令直前にRestore(退避した変数をレジスタへのロードする命令)を挿入した命令列のレジスタ割り当てに変換することで、問題を変数への代入時のレジスタ割り当てのみに帰着させた。
• 仮想マシンコード生成において、レコード(クロージャまたはタプル)の要素を一括してロードまたはストアするコードの生成方法が改善された。同等のコード(同一ではない)を出力しながらもロジックは単純になった。

regAlloc.mlでは関数のレジスタ割り当てを行うhからg_repeatに渡される引数がAns(Nop)からAns(Mov(a))に変更されているのだが、これの狙いはよくわからない。

このほか、理解しやすさを狙いレジスタ割り当ての処理を弱めたバリエーションが付属するようになった(regAlloc.{notarget-nospill,target-nospill,target-earlyspill,target-latespill}.ml)。

MinCaml 0.0.9

久しぶりにチェックすると版が進んでいた。以前読んだ時からの変化を確認するためにダウンロードし、まずはregAlloc.mlを読む。

読みながら頭の中を整理し直していると、ToSpillによる処理の後戻りをなくしても同じ実現できることに気がついた(レジスタ割り当てを行うregAlloc.mlは、レジスタが溢れる度に溢れた変数の定義時点まで立ち戻って処理をやり直すという大変面倒な作りになっている)。

実際にコードを変更して目論見通りの動作を確認。 付属のテストプログラムで確認したところ、オリジナルと同等のコードを生成した(実は一点だけわずかに良くなった)。SPARCを触れる環境にないため確認は生成したコードのdiffによっている。

後程、詳細を記事にする予定。合わせてレジスタ割り当ての解説の項をわかりやすく書き直す。