ltmpc: CodeEmitterの解説

CodeEmitterでは、これまでで得られた型付きの抽象構文木と配置情報をもとに、x86(32bit)のアセンブリを出力します。 ターゲットとしてx86(32bit)を選んだ理由は、私が最も慣れ親しんでおり、呼び出し規約も簡単だからです。

CodeEmitterのコードは、ほんとうにぎりぎりの、公開日当日に数時間で書かれました。 そのため、ところどころでParserやTypeAnalysisやLocationの関数を使っているなど、かなり汚い設計になってしまっている上、ごく一部のコードしかコンパイルできません。 それでも、N-Queen問題を解くコードが動いた時には感動しました。

x86(32bit)の呼び出し規約(cdecl)

  • eax, ecx, edx を保存せずに使用してよい。
  • ebx, esi, edi, esp, ebp は保存せねばならない。
  • 引数は全て後ろから順番にスタックに積む。
  • 返り値はeaxレジスタに乗せる。
  • コールスタックの片づけは呼び出し側で行う。

コード生成の作戦

ちゃんとした最適化コンパイラであれば、スタック割り付けなどの仕事をする必要がありますが、ltmpcではとりあえずコンパイルするだけでよいため、そのような面倒な仕事はしたくありません。 x86(32bit)の機械語にはスタック操作命令が豊富なため、スタックマシンとして扱うことができます。抽象構文木を一対一にアセンブリに変換する場合、スタックマシンとして考えると非常に簡単になります。 その上、スタックマシンとして扱うとeax, ecx, edx, esp, ebp以外のレジスタを使わずに済みます(少し手間をかければ、(可変長配列がなければ)ebpも不要になります)。 espとebpの操作は定型文になり、技巧的な方法を使う必要はありません。ebx, esi, ediは使わないので保存レジスタですが気にする必要がなくなります。eaxは返り値、edxは剰余演算の返り値、ecxはシフト演算のオペランドとして、それぞれ専用の役割があるため絶対使わないというのはほぼ不可能ですが、幸い日保存レジスタになっています(他にも役割は存在します)。 関数ポインタを使った関数呼び出しと静的に確定する関数呼び出しとでは普通は別の命令を使いますが、なるべく例外を少なくするために、静的に確定する関数呼び出しの場合でも関数ポインタで呼び出すことにします。

Code, concat

Codeは、単なるTMPにおけるcharの配列です。concatは、二つのchar配列をつなげる関数です。ここで、concatの定義時(つまり、定義前)にdecltypeの中にconcatが出現しており、これは定義前再帰ですが、同じ名前空間のCodeが引数に入るため、ADLで検索されるので問題ありません(このせいでdetailの中に入っていないのです)。

Intro

アセンブリコードの最初に必要な定型文です。

ToString, ToOffset

非型テンプレート整数を10進文字列に変換する関数です。ToStringは非負整数用であり、ToOffsetは符号付整数用で常に符号付で出力します。displacementの部分に書く用です。

StringRef, FuncRef

それぞれ、文字列(char配列の先頭アドレス)、関数へのポインタ、をスタックに積むときに書くべき定型文です。

Dword, Byte

それぞれ、ポインタの型を表すための定型文です。Dwordの場合はそのアドレスから4Byte分、Byteの場合はそのアドレス1Byte分のメモリ操作になります。

ラベル関連

一意なラベル情報を実際に文字列化しています。まず関数の名前、ifのネストは連番の整数を文字列化、ループ構文の先頭・条件部・末尾はそれぞれB, C, Eを、それぞれアンダースコアつなぎにすることで一意になることを保証しています。

PraceはPlaceの間違いでしょうか……。あまりにあわてて作ったので気づきませんでした……。

SetCCの利用

普通、x86での比較命令はcmp命令ですが、フラグを使うのが面倒なのと、(a<b)+(c==d)みたいなコードに対処しないといけないことを考えると、0・1がそのまま出力されるSetCC命令を使うと簡単になります。

Compile

ここで具体的に抽象構文木のノードをアセンブリコードに落としていきます。リテラルの場合、即値をスタックに積むだけのコードになります。addやsubでは、オペランドがポインタであるかなどにより三通りのパターンがありますが、左辺のプログラムと右辺のプログラムを再帰的にコンパイルしてコードにした後に必要な処理をする形になっています。代入の場合は、左辺のプログラムにアドレスを要求している点が異なります。後置増分・減分の場合はcharintかポインタかで三通りのパターンがあります。

複雑なのは配列アクセスで、多次元配列の場合は値ではなくアドレスを返す点が特殊になっています。1[arr]のような変な書き方ができることと合わせて、四通りのパターンがあります。 関数コールは引数をスタックに積んだ後、関数ポインタをスタックに積み、それをポップしてレジスタ間接コールを行います。戻ってきたときはスタックを巻き戻します。

変数の場合は、右辺値なら値を、左辺値ならアドレスを、それぞれ返すコードを出力しなければいけません。値を返すコードはEmitCode、アドレスを返すコードはAddrに定義されるのですが、あわてて作った上に設計がめちゃめちゃなので、なぜこれで動くのかも私自身わかっていないところがあります。

StatementFold

構文ごとに対応するコードを出力する部分です。esp, ebp操作関連のコードはここで出力されます。

StringPoolFold

前回のLocationで回収した、文字列定数をグローバル領域に出力します。

GlobalStatementFold

グローバル変数と、関数定義と、文字列定数を出力する部分です。

おわりに

これで一通りすべてのモジュールの解説が終わりました。 まだまだ道のりは長いですが、ltmpcをより完成に近づけていけたらと考えています。

あまり関係ない話

これで書くことが尽きてしまったので、一か月くらいブログは休む気がします。またltmpcの進捗を公開できることを願って。