スタックマシン

このインタープリタでつくったtiny Cについて、コンパイラを 作っていくことにする。最終的には、マシンコードを直接出力するコンパイラ を作るが、コード生成の考え方を簡単にするために、初回に紹介したスタック マシンをターゲットにする。スタックマシンではレジスタを扱わなくても良い ため簡単になる。初回では単純な数式のコンパイルを考えたが、言語を実行す るためにはインタプリタでやったように関数呼び出しやローカル変数をどのよ うに作るかを考えなくてはならない。コンパイラのターゲットの仮想マシンの 解説からはじめることにしよう。

ここで考えるスタックマシンの「インタプリタ」のプログラムは、以下のプロ グラムである。 なお、このスタックマシンの作り方については、 こちら を参照のこと。

スタックマシンの命令

tiny Cのターゲットとして考えるマシンの命令は、以下の２０個の命令である。

命令コード 説明
POP　　stackから、１つpopする。
PUSHI n 整数nをpushする。
ADD stackの上２つをpopして足し算し、結果をpushする。
SUB stackの上２つをpopして引き算し、結果をpushする。
MUL stackの上２つをpopして引き算し、結果をpushする。
GT stackの上２つをpopして比較し、>なら１、それ以外は0をpushする。
LT stackの上２つをpopして比較し、<なら１、それ以外は0をpushする。
BEQ0 L stackからpopして、0だったら,ラベルLに分岐する。
LOADA n n番目の引数をpushする。
LOADL n n番目の局所変数をpushする。
STOREA n stackのtopの値をn番目の引数に格納する。
STOREL n stackのtopの値をn番目の局所に格納する。
JUMP　L ラベルLにジャンプする。
CALL　e 関数エントリeを関数呼び出しをする。
RET stackのtopの値を返り値として、関数呼び出しから帰る。
POPR　n n個の値をpopして、関数から帰った値をpushする。
FRAME n n個の局所変数領域を確保する。
PRINTLN s sのformatで、printlnを実行する。
ENTRY　e 関数の入口を示す。（擬似命令）
LABEL LラベルLを示す。（擬似命令）

スタックマシンでの演算

POPや、PUSHI, 演算ADD,SUBなどは、最初の講義で解説した 通り、スタックに値をセットしたり、演算したりする命令である。 コンパイラは、このスタックマシンのコードを使って、式を実行するコード列 を作る。

その手順は、

  1. 式が数字であれば、その数字をpushするコードを出す。
  2. 式は変数であれば、その値をpushするコードをだす。
  3. 式が演算であれば、左辺と右辺をコンパイルし、それぞれの結果をスタッ クにつむコードを出す。その後、演算子に対応したスタックマシンのコードを 出す。

制御文のコード

JUMP命令は、LABEL文で示されたところに制御を移す命令である。このスタッ クマシンは分岐命令は、BEQ0命令しかない。この命令は、スタック上の値を popして、これが0だったら、分岐する命令である。これを組みああわせてIF文 をコンパイルする。コードは次のようになる。 

...条件文のコード...
BEQ0 L0   /* もし、条件文が実行されて、結果が0だったら,Ｌに分岐*/
...thenの部分のコード...
JUMP L1
LABEL L0
... elseの部分のコード...
LABEL L1
IF文のコンパイルは以下のようになる。
  1. 条件式の部分のコンパイルする。これが実行されるスタック上には、条 件式の結果が積まれているはずである。
  2. ラベルL0を作って、BEQ L0を生成。
  3. then部分の式をコンパイルする。
  4. これが終わるとIF文を終わるため、ラベルL1を作って、ここにJUMPする命令を生成する。
  5. 条件文が0だったときに実行するコードを生成する前に、LABEL L0を生成する。
  6. else部の式をコンパイル。
  7. then部の実行が終わったときに飛ぶ先L1をここにおいておく。

関数呼び出しの構造

式だけを評価するならば、これでいいが、関数が使えるようにするためには、 スタックの使い方を工夫しなくてはならない。スタックマシンは以下の３つの レジスタを持つ。

関数の呼び出しの手順は、以下のようにする。
  1. スタック上に引数を積む。
  2. 現在のPCの次のアドレスをスタック上に保存(push)し、関数の先頭のア ドレスにjumpする。（CALL命令）
  3. 現在のFPをスタック上に保存し(push)し、ここを新たなFPとする。FPか ら、上の部分を局所変数の領域を確保し、ここを新たなスタックの先頭にする。 (FRAME命令)
  4. 式の評価のためのstackはここから始まる。
  5. 引数にアクセスするためには、FPから２つ離れたところにあるので、こ こからとればよい。(LOADA/STOREA命令)
  6. 局所変数にアクセスするためには、FPの上にあるので、ＦＰを基準にしてアクセスする。(LOADL/STOREL命令)
  7. 関数から帰る場合には、stackに積まれている値を戻り値にする。元の関 数に戻るためには、FPのところにSPを戻して、まず、前のFPを戻して、次に戻 りアドレスを取り出して、そこにjumpすればよい。(RET命令)
  8. 戻ったら、引数の部分をpopして、関数の戻り値をpushしておく。（POPR 命令）
このような構造を、関数フレームと呼ぶ。このような規則を 関数のリンク規則(linkage conventionあるいはcalling sequence) とよび、各マシンごとに定められている。

さて、関数定義に対するコードは以下のようになる。 

ENTRY foo
FRAME ローカル変数の個数
　.... 関数本体のコード....
RET
また、関数呼び出しは、 
引数１のpush ...
引数2のpush ...
  ....
CALL foo
POPR  pushした引数の個数
関数のコンパイルは、以下のようになる。
  1. まず関数の名前を取り出して、ENTRY funcを生成する。
  2. パラメータ変数に番号をつける。関数が呼ばれた場合にはこの順番でスタックに積まれていることになる。これをEnvをいれておく。
  3. 関数の本体をコンパイルする。
  4. 実行されると関数の本体の値がスタックに積まれているはずなので、ここでRET命令を生成する。
パラメータの変数や局所変数は、スタック上にその領域が確保されるが、どこに確保されるかを数えておかなくてはならない。

次回、スタックマシンに対するコンパイラ全体について、説明することにする。