スタックマシン向けコード生成とラベルバックパッチ
スタックマシン (pl0 のような単純な VM) を対象にした、yacc アクション中で命令列を組み立てるワンパスのコード生成手法。cmm→pl0 コンパイラの拡張を題材に整理する。実例は cmm-pl0-compiler。
スタックマシンと逆ポーランド
pl0 VM は値スタック s とトップ位置 t を持つ。式は 逆ポーランド (後置) の順で命令を並べれば評価できる。
- リテラルは
O_LITでプッシュ (s[++t] = a)。 - 単項演算は
s[t]を上書き (位置不変)。 - 二項演算は
--tしてからs[t]とs[t+1]を演算しs[t]に書き戻す。
例: a + b は「a のコード」「b のコード」「加算命令」の順に連結する。式の評価がそのままスタック操作に対応するため、AST を後行順 (post-order) に辿るのと等価。
命令列の合成 (makecode / mergecode)
pl0 命令は連結リスト struct CODE {next, f, l, a} で表され、cptr {h, t} がリストの head/tail を保持する。基本 API は 2 つ。
makecode(f, l, a): 1 命令を生成。例えば+はmakecode(O_OPR, 0, 2)。mergecode(c1, c2): 2 つの命令リストを連結。
yacc アクションでは下位規則の $n.code が部分式の命令列を持つので、それらを mergecode で順に繋いで $$.code に格納する。これは構文主導翻訳 (syntax-directed translation) の最小実装と言える。
mergecode の落とし穴
mergecode は内部で第2引数を free() するため、同じ $n.code を 2 回使うとセグフォになる。a % b を a - b*(a/b) のように a,b を複数回参照する形へ展開しようとすると破綻するので、命令リストの複製関数を作るか、後述のように VM 側に専用命令を足して回避する。
制御構造とラベル
分岐・ループは「ラベル発行 + 条件ジャンプ」で実現する。makelabel() が連番ラベルを返し、O_LAB/O_JMP/O_JPC (条件偽でジャンプ) を配置する。
for:<初期化> LAB L0 <条件> JPC L1 <本体> <更新> JMP L0 LAB L1。switch/case: 構文解析は下位規則から進むためcaseの時点では判定対象変数vが未知。各 case を一旦グローバル配列cases[](cond, stmt) に退避し、switch v規則でループしてまとめて生成する。breakは末尾end_labelへのJMP、defaultは条件をLIT 1(常時真) で表す。
ラベルバックパッチ (前方参照)
goto L; ... label L; のように使用が定義より前に来る 前方参照 では、その時点でラベル番号が未確定。対処として goto/label どちらの規則でも「文字列 L が未登録なら makelabel() して登録、登録済みならその番号で生成」という統一規則にする。ラベル文字列↔番号はグローバル labels[] + 線形探索 search_label() で管理 (C にハッシュマップが無いため)。これは一般のアセンブラが行う バックパッチ の素朴版。
VM 拡張による命令追加
コンパイラレベルで合成できない演算は VM に命令を足す。vm/code.h の opecode/oprcode enum に追記し、vm/inter.c の interpreter() の switch に処理を加える。
- 剰余
%/ 累乗**: 合成を諦めP_MOD/P_POWを新設。 - 論理
&&/||/!:P_AND/P_OR/P_NOT。 - 配列: 添字が変数になり定数アドレスの
LOD/STOでは不可。スタック値をアドレスとして使う 動的ロード/ストアO_DLD/O_DSTを追加。さらに変数宣言時の領域計算vd_backpatch()を、配列長を考慮して複数領域を確保するよう改修 (struct LISTにlengthを追加)。
関連
- 言語フロントエンドの上位手法: operator-precedence-parsing、parser-combinator。
- ツール: lex-yacc。
- 同系統の自作処理系: cmm-pl0-compiler、toy-llvm-compiler、arcturus-interpreter。
- バックエンド寄りの低レベル生成: instruction-selection-register-allocation。