1. 概要

1-1. フロントエンドとバックエンドの分離

現在のところ、新バックエンドはフロントエンドとは独立したプログラムとなっている。 バックエンドはフロントエンドが吐きだした中間コードファイル(ASCII形式のLIR)を読みこんで、機械語を生成する。

これは、フロントエンドの開発とバックエンドの開発の同期をとる(相互のインターフェースの変更への対応)作業が軽減できるというメリットがあるので、開発の初期段階では有効と考える。

また、メモリ受けわたしだと責任分岐点がはっきりしないという問題もあり、仕様のはっきりしている印字形式のファイルを経由することによりその問題も軽減できる。

最終的には両者は一本のプログラムに統合され、中間コードはメモリで渡されるが、そのときもLIRはlispのS式の内部表現形式のような構造のない形で渡す予定である。

なおASCII形式のLIRを吐きだす版のフロントエンドは、現行のフロントエンドへのパッチという形で提供している。


1-2. バックエンド全体の構成

COINSバックエンドの構成は次のようになっている。
Loading
入力のASCII LIRファイルを読みこみ、内部表現に置きかえる。この段階でCFGへの分割も行われる。内部表現は、クラスModuleの単一のインスタンスにまとめられる。
Optimize
ターゲットに依存しない最適化や変換、そのための解析を行う。
Realization
ターゲットに依存するが機械語の生成はともなわない変換作業を行う。具体的には、CALL, PROLOGUE, EPILOGUE, JUMPN 等の命令をより単純な命令に分解する。
Instruction Selection
ターゲットCPUの命令を選択する。
Register Allocation & Code Scheduling
レジスタ割付と命令スケジューリング。
Final
覗き穴の最適化などをほどこした後アセンブラ言語を出力。
このうち、内部表現への変換処理の流れは次のようになる。

  1. まず、主プログラムが入力のS式表現のLIRを読みこみ、内部S式表現にする。 これは不変リストクラスImListおよび文字列クラスStringから成る表現で、LispのConsセルとシンボルアトムに対応するものである。 そしてこのImListオブジェクトをクラスModuleのコンストラクタに渡す。

  2. Moduleクラスは、渡されたリストをなめて、SYMTABに出あえばグローバルシンボル表(クラスSymTab)を作成し、DATAに出あえば初期化処理を行い、FUNCTIONを見たらその部分リストをFunctionのコンストラクタに渡してFunction型のインスタンスを作成する。 FunctionのインスタンスはリストfunctionListに格納される。リストは可変リストクラスBiListで表現される。

  3. クラスFunctionのコンストラクタは、渡されたS式表現のLIRを、ローカルシンボル表クラスSymTabクラスLirNodeのインスタンスからなる木構造のリストに変換する。 ラベルは、クラスLabelをもつハッシュ表で表現される。 S式表現に直接さわるのはクラスModuleとクラスFunctionだけで、他のクラスでは参照しない。 Functionは、できたLirNode treeのリストをクラスFlowGraphのコンストラクタに渡し、CFGに変換する。

  4. ラスFlowGraphのコンストラクタは、渡された一本のリストを走査して、基本ブロックの単位に分割する。分割はリストを実際に切断することによって行う。切断されたLirNode treeのリストは基本ブロッククラスBasicBlkのコンストラクタに渡されて、BasicBlkのインスタンスに変換される。

  5. クラスBasicBlkのコンストラクタは渡されたLirNodeのリストを調べ、先頭のDEFLABELをはがし、ラベルを変数labelに格納する。ラベルのないブロックには、適当なラベルを生成して張りつける。対応するLabelのインスタンスから当該ブロックを指すようセットする。

  6. 再びFlowGraphに戻る。作成されたBasicBlkのインスタンスをリストbasicBlkListに格納し、全部そろったところでsuccessor, predecessorの情報をセットする(BasicBlk#maintEdgesで行う)。