Cコンパイラ作りで心が折れそうになってるポイント

rui314 さんのブログを見て刺激されたので、3月末くらいからCコンパイラをのんびり作ってる。
低レイヤを知りたい人のためのCコンパイラ作成入門

ただ、最近は「ここ作りにくいな・・・」って思う点が出てきて、心が折れかかってるので、自分の頭で悩んでる点について吐き出してみる。

Cプリプロセッサは、チューリング互換で無いにしても、Cとは別の言語系である。
そのため、「プリプロセッサのためのパーサー」が必要に感じてくる。

例えば、プリプロセッサだと、次の書き方は正しい。

#if defined EXIST_MACRO
  /* 文法的に正しいコード */
#else
  /* 文法的に間違ってるコード */
#endif

つまり「最初に全部トークン化して、その後にプリプロセッサに渡す」という設計は間違っていた。
また、上記のように、#if は 式 を受け取るため、プリプロセッサの時点でパーサーおよびその評価機構が必要になってくる。

今は、プリプロセッサ用のパーサーと評価機構を用意してるけど、再トークン化や数値型評価など、 C用パーサーとほぼ同じ所が沢山出てきてるので、設計がどこかおかしい気がしてきてる・・・

浮動小数点型は整数型と異なり、別のレジスタや命令を使わないといけない。
整数型用に作ってたコンパイラに浮動小数点型を導入しようとしたところ、命令生成のところで浮動小数点型に対する分岐が大量に入ることになった。

特に、a ==b の等値比較は、整数型なら1回の比較で終わるのに、浮動小数点型だと2回比較をしないといけない。これは、ステータスフラグの ZF と PF を1回で評価する命令が無いのが原因だと思われる。
Tips IA32 x87命令一覧比較命令と分類命令 FCOMI/FCOMIP/FUCOMI/FUCOMIP命令

そのため、パース結果の足し算ノードについて、被演算型を判別して命令を生成するか、そもそも足し算ノードを整数型用・浮動小数点型用で用意するかした方が良さそうに感じている。

(整数 + 浮動小数用の命令も使いたいなら、この設計はいろいろヤバくなる)

ここは完全に勉強不足。

上記ブログはスタック型だけど、エンジニアなら、スリムなレジスタ型に変えるのが常識だろう。[要出典]
普通に考えるなら「SSA形式に直して」「干渉グラフを作って」「ゴリゴリ彩色する」のだろう。

例えば、SSA形式だと、どうやってφ関数を作成するのかが分からない。

i = 0;
while (i < 10) {
  i = i + 1;
}

  %1 = 0;

WHILE:
  // %1 = phi(%1, %2) とする？
  if (%1 < 10) {
    %2 = %1 + 1;
    goto WHILE;
  }

たぶん、BasicBlockごとに「右辺に来る変数」「左辺に来る変数」を採取して、その共通項からφ関数に入れる物を決めるんだろうけど、まだ実装に落とし込めるほど、アルゴリズムを調べきれてない。

そして、一番の問題は、ここから干渉グラフを作ること。

loop:
  %1 = phi(%1, %999)
  %3 = %1 + %2;
  /* ながーいコード */
  %999 = %997 + %998;
  goto loop;

このようになった場合、%1 と %999 それぞれの生存区間を求めて、干渉グラフ上でマージすればいい気がする。そうしないと、%1 と %999 が別レジスタに割り付けられて、ループがおかしいことになってしまう。

・・・こう書いてて、なんか出来そうな気がしてきた。

Cのパース、予想以上に面倒事が多い。

また、ジェネレータについても、面倒事が多い。

現在の開発環境が windows 64bit なので、今はそっちのみに集中する。

コンパイラ作り楽しい！✌('ω'✌ )三✌('ω')✌三( ✌'ω')✌