第２版まえがき

第１版を世に出してからほぼ10年が経過した． その間に自分が経験したこと，世の中で研究されたこと などを付け加え，また，第１版で記述が十分でなかったところを 充実させて，第２版を出すことにした．

第１版の「まえがき」では 「本書は，いままでコンパイラに関して積み重ねられてきた技術や最近研究されていることをできるだけ一冊の本にまとめてみようとして書き始めたものである」 といったが，この第２版はその継続である．

その間に自分が経験したこととしては，COINSコンパイラ・インフラストラクチャ （注：http://www.coins-project.org/） の開発がある．これは2000年から2005年にかけての文部科学省の プロジェクトとして開発し，2006年にはIPA（独立行政法人 情報処理推進機構） のプロジェクトとして追加開発をし， その後も改良や保守を継続しているものである． 筆者はそのプロジェクトから多くのことを学んだ． またその間もコンパイラの最適化に関しては多くの研究がなされてきた． 第２版にはそれらのことをできるだけ盛り込むようにした．

第２版では，第１版と次の点が異なる．
全体的な変更としては以下の3点がある．

  1. 第１版では，本文中での英字のフォントはほとんど1種類だけが 使われていたが，第２版では変数名として使われる英字はイタリック体 にするなどして，表現を明確にした．
  2. 最近の参考文献とそれを参照する文を追加した．
  3. 第１版の第12章「最適化のアルゴリズム」 の内容が第２版では増えたので，その各節を章に昇格させた． また，第19章「データの流れの解析の別法」と第20章「オブジェクト指向言語 での最適化」を新たに設けた．

内容を充実させたり新設した箇所としては以下のものがある．

  1. 第９章「目的コードの生成」では，主として リターゲッタブルコード生成の技術についての記述を充実させた． 具体的には，コード生成器生成系（9.4節）について， コンパイル時のダイナミックプログラミングによるコード生成（9.4.3）， コード生成器作成時のダイナミックプログラミング（9.4.4）， JIT 向きの方法（9.4.5）， SSA グラフと二次計画法による命令選択（9.4.6）， リターゲッタブルコード生成の実装（9.4.7）の各項を記述した．この 最後のリターゲッタブルコード生成の実装は，COINSでの開発の経験 に基づいて記述したものである．

    なお，9.5.2項「JIT コンパイラ」では，実際にどんなJITコンパイラが 開発されているかを簡単に紹介した．

  2. 第13章「静的単一代入形式（SSA 形式）」では，第１版で記述が 不十分であったSSA 形式から通常の形式に戻す方法についての問題点や解決法 を記述した（13.2.4）．また，SSA形式での部分冗長性の除去については， COINSのメンバ（滝本氏）が新たに考案したものであり，COINSに実装されている方法を 簡単に紹介している．
  3. 第14章「命令スケジューリング（並列実行）」では 筆者が新たに考案したものであり，COINSに実装されているソフトウェアパイプライニング の一方法を記述している（14.3.3 ループの終了判定命令）．
  4. 第15章「レジスタ割付け」では， 最近も盛んに研究されているレジスタ割付けのいろいろな新しい方法を紹介している．

    15.1節「簡単な割付法」では，JITコンパイラなどに採用されている 「線形走査レジスタ割付け」を紹介している．

    15.3.4項「SSA 形式の利用」では，SSA 形式のプログラムから作った 干渉グラフではレジスタ圧（register pressure）の最大値が彩色数 （chromatic number）になるということを利用したレジスタ割付けの方法 を紹介している．

    15.3.5項「レジスタの特異性への対処」では， レジスタ割付け問題を，空いているレジスタ空間を各プログラム 点で必要となるレジスタで埋めていくパズルとして解く方法も紹介している．

    15.5節では，二次計画法によるレジスタ割付けの方法を紹介している．

  5. 第19章「データの流れの解析の別法」では， 新しい解析の方法として最近使われているDatalog 言語， 二分決定グラフ（BDD: binary decision diagram），文脈自由言語到達性 などを紹介し，それらを使った種々のポインタ解析の方法を紹介している． また，ポインタが指す可能性のある変数の集合の包含関係を使う解析法も 紹介している．
  6. 第20章「オブジェクト指向言語での最適化」では， 第１版では不十分であったオブジェクト指向言語特有の 最適化の方法のいくつかを紹介している．それらは， メソッド呼出しの高速化， 例外検査の除去， 脱出解析，などである．

コンパイラは成熟した技術であると言われるが，最適化の技術については 相変わらず活発に研究・開発が続けられている．そのことは， 文献の略記法として取り上げたコンパイラ関係の雑誌や プロシーディングスの種類の数が，第１版では 13であったのが，第２版では24に増えていることからもうかがわれる．

それらの研究・開発は今まで蓄積されてきた技術をベースとして その上に構築されていくものである．本書が，そのベースとなる 技術の理解に役立つものとなれば幸いである．