「コンパイラの構成と最適化」

中田育男著, 朝倉書店,1999年9月


正誤表
本文の各節で参照されている文献のリストは以下の 参考文献 をご覧ください。そのリストで使われている文献の略記法は こちらにあります。
まえがき
第1部 コンパイラの概要

1.はじめに

1.1 コンパイラとは
1.2 変換系と通訳系

2.コンパイラの簡単な例

2.1 後置記法
2.2 スタック
2.3 簡単なコンパイラの例
2.4 コンパイラの論理的構造
2.5 コンパイラの物理的構造

第2部 コンパイラの構成

3.文法と言語
参考文献
3.1 バッカス記法
3.2 構文図式
3.3 文法と言語の形式的定義
3.4 解析木
3.5 あいまいな文法

4.字句解析
参考文献
4.1 文字読取り
4.2 字句読取り
4.3 正規表現と有限オートマトン
4.3.1 正規表現
4.3.2 正規表現から非決定性有限オートマトンへ
4.3.3 非決定性有限オートマトンから決定性有限オートマトンへ
4.3.4 有限オートマトンの状態数の最小化
4.3.5 字句解析器生成系
4.4 字句読取りプログラムの例
4.4.1 浮動小数点定数の読み取り
4.4.2 コメントの読取り
4.4.3 最長一致と最短一致

5.構文解析
参考文献
5.1 構文解析手法の簡単な歴史
5.2 下向き構文解析法
5.2.1 下向き構文解析法とその問題点
5.2.2 LL(1)文法
5.2.3 再帰的下向き構文解析プログラム
5.2.4 文法から再帰的下向き構文解析プログラムへ
5.2.5 非再帰的下向き構文解析法
5.2.6 あいまいな文法の扱い
5.3 LR構文解析法
5.3.1 上向き構文解析法
5.3.2 LR構文解析の概略
5.3.3 SLR(1)構文解析
5.3.4 LR(1)構文解析
5.3.5 LALR(1)構文解析
5.3.6 あいまいな文法の扱い
5.3.7 正規右辺文法のLR構文解析
5.4 演算子順位構文解析法
5.4.1 演算子順位文法
5.4.2 演算子順位行列による構文解析
5.4.3 演算子順位関数
5.5 構文解析法の選択
5.6 構文解析器生成系

6.意味解析
参考文献
6.1 意味解析とは
6.2 記号表
6.2.1 記号表の情報
6.2.2 記号表の探索
6.2.3 ブロック構造と記号表
6.3 属性文法
6.3.1 属性文法の簡単な例
6.3.2 属性文法の定義
6.3.3 属性評価器
6.3.4 1パス型属性文法
6.3.5 属性文法の拡張と応用

7. 誤りの処理
参考文献
7.1 誤りの発見
7.1.1 構文上の誤り
7.1.2 意味上の誤り
7.2 誤りの情報の出力
7.3 誤りの修復
7.4 正常処理への復帰

8. 実行時記憶域と仮想マシン
参考文献
8.1 実行時記憶域
8.1.1 基本データ型の表現
8.1.2 配列型と構造体型の表現
8.1.3 クラスの表現
8.1.4 手続き用の記憶域
8.2 仮想マシンと通訳系
8.2.1 仮想マシンとは
8.2.2 仮想マシンの命令
8.2.3 仮想マシン語への変換
8.2.4 仮想マシンの実現(通訳系)

9. 目的コードの生成
参考文献
9.1 中間語と機械語
9.2 式のコ−ド生成
9.2.1 オペランド参照のコ−ド
9.2.2 算術式のコ−ド
9.3 文のコ−ド生成
9.3.1 分岐文のコ−ド
9.3.2 手続き呼出しのコ−ド
9.3.3 例外処理のコ−ド
9.4 コ−ド生成器生成系
9.4.1 木のパターンマッチングによるコード生成
9.4.2 構文解析法によるパターンマッチングでのコード生成
9.4.3 ダイナミックプログラミングによるコード生成
9.5 実行時コード生成
9.5.1 動的コード生成
9.5.2 JITコンパイラ

第3部 目的コードの最適化

10.最適化とは
参考文献
10.1 最適化の例(行列の掛け算の例)
10.1.1 配列要素の配置と番地計算
10.1.2 最適化の例(スカラ計算機の場合)
10.1.3 最適化の例(アクセス効率とループ変換)
10.1.4 最適化の例(ベクトル計算機の場合)
10.1.5 最適化の例(並列計算機の場合)

11.最適化の方法
参考文献
11.1 命令の実行回数を減らす
11.1.1 共通部分式の削除
11.1.2 定数の畳み込み
11.1.3 命令のル−プの外への移動
11.1.4 部分冗長性の除去
11.1.5 ル−プの変換
11.1.6 式の性質を利用して実行を省略する
11.1.7 無用命令の削除
11.1.8 複写の削除
11.1.9 手続き呼出しの特殊化
11.1.10 オブジェクトのインライン割当
11.1.11 判定の置き換え
11.1.12 のぞき穴式最適化

11.2 より速い命令の利用
11.2.1 レジスタ割付け
11.2.2 特殊な命令の利用
11.2.3 メモリアクセス順序の最適化(メモリ階層の有効利用)
11.2.4 演算の強さの軽減

11.3 並列度を上げる
11.3.1 命令レベル並列実行
11.3.2 デ−タ並列実行

11.4 最適化の方法の適用順序

12.最適化のアルゴリズム

12.1 制御フロ−グラフ

12.2 デ−タの流れの解析
参考文献
12.2.1 共通部分式の削除(基本ブロックと拡張基本ブロック内)
12.2.2 変数の定義に対応する定義の解析
12.2.3 デ−タの流れの等式の一般形
12.2.4 共通部分式の削除(大域的)
12.2.5 ループ
12.2.6 ループの外への移動
12.2.7 変数の生と死の解析
12.2.8 無用命令の削除
12.2.9 定数伝播と畳み込み
12.2.10 部分冗長性の除去
12.2.11 手続き間解析
12.2.12 ポインタ解析
12.2.13 最適化の各操作の適用順序

12.3 静的単一代入形式(SSA形式)
参考文献
12.3.1 SSA形式の求め方
12.3.2 制御依存グラフとプログラム依存グラフ
12.3.3 無用命令の削除
12.3.4 共通部分式の削除
12.3.5 ループの外への移動
12.3.6 帰納変数
12.3.7 演算の強さの軽減と判定の置き換え
12.3.8 定数伝播
12.3.9 部分冗長性の除去
12.3.10 ポインタ解析

12.4 命令スケジューリング(並列実行)
参考文献
12.4.1 基本ブロック内の命令スケジューリング
12.4.2 基本ブロックにまたがった命令スケジューリング
12.4.3 ソフトウェア・パイプライニング
12.4.4 条件文がある場合のソフトウェア・パイプライニング
12.4.5 整数線形計画法によるソフトウェア・パイプライニング

12.5 レジスタ割付け
参考文献
12.5.1 簡単な割付け法
12.5.2 生存区間を使ったレジスタ割付
12.5.3 生存区間の干渉グラフを使ったレジスタ割付
12.5.4 整数線形計画法によるレジスタ割付け

12.6 配列要素の依存解析
参考文献
12.6.1 データの依存関係
12.6.2 1重ループ内の依存関係とベクトル化
12.6.3 多重ループにおける依存関係
12.6.4 データ依存関係の解析法

12.7 ループ変換
参考文献
12.7.1 ループ分配
12.7.2 ループ融合
12.7.3 ループ交換
12.7.4 ループ逆転
12.7.5 ループ傾斜
12.7.6 波頭変換
12.7.7 ループ細分
12.7.8 ループタイル化
12.7.9 ループ展開
12.7.10 ループ合体
12.7.11 ループつぶし
12.7.12 ループ皮むき
12.7.13 ループ変換の適用順序

12.8 データ分散と通信
参考文献
12.8.1 各プロセッサでの私物化
12.8.2 配列分散の解析
12.8.3 計算分散の解析
12.8.4 通信の解析
12.8.5 通信の最適化
12.8.6 デ−タ分散の自動化
12.8.7 配列へのアクセスが規則的でない場合


参考文献
あとがき