コンパイラの構成と最適化
概要
本
かかった時間
60.8 時間
読む前の状態
OS についての本は何も読んでいなく、1 冊目として手を動かしながら概要を抑えるために読み始めた
読む前後の変化
最適化のために何を考えるかイメージが明確になった
命令の実行回数を減らす
より速い命令を使う
並列度を上げる
具体的にどのような手法が使われているかイメージが明確になった
アルゴリズムの詳細については追えていない
読書メモ
1章: はじめに
コンパイラとは、高級プログラム言語で書かれたプログラムを、機械向き言語のプログラムに翻訳するためのプログラム
機械向き言語には、仮想マシンの機械語も含む
原始プログラムのコンパイルから実行までに必要なすべてのシステムをあわせたものを言語処理系（または処理系）と呼ぶ
2章: コンパイラの簡単な例
記法の説明
中置記法（a+b）
前置記法（+ab）
ポーランド記法ともいう
後置記法（ab+）
逆ポーランド記法ともいう
後置記法の性質は、計算機で計算する時に都合がいい。計算機は後置記法の式の各項目を、並んでいる順番に計算すればいい
中置記法の式を後置記法に変換するアルゴリズム
スタックに左括弧（どの演算子よりも優先順位の低い演算子）を積む
中置記法の式を左から読みながら
演算数を読んだらそれをそのまま出力する（演算数:式が 1 つのもの。a とか）
演算子を読んだら、スタックの上にそれより優先順位の高い演算子があればそれを（あるだけ順に）スタックから降ろして出力し、読んだ演算子をスタックに積む。ただし、式の終わりになったら、右括弧（どの演算子よりも優先順位の低い演算子）を読んだことにする
コンパイラの論理的構造
原始プログラムから目的プログラムまでに以下の処理を通る
読み込み（行→文字）
字句解析（文字→符）
構文解析（符→構文木）
中間語作成（構文木→中間語）
最適化（中間語→機械語）
コンパイラにおける最適化とは、文字通りの最適化ではなく、最適なものに近づけるという意味
最適化は中間語のレベルで行うだけでなく、構文木のレベルや、中間語から目的コードを生成する時、生成されたコードの列に対しても行われる
コード生成（機械語→目的プログラム）
Pascal などのように、主ルーチンからサブルーチンまで、そのプログラムの実行に必要なプログラムをすべてまとめてコンパイルする時
目的プログラムと実行時ルーチンを結合して直ちに実行に入れる
C や Fortran などのように、主ルーチンやサブルーチンを別々にコンパイルする場合
目的プログラムは別々のファイルに出力されることになる。それらをまとめて 1 つの実行可能なプログラムにするのは、リンカと呼ばれるソフトウェア
ただし、実際に作られるコンパイラは、必ずしもこの論理的構造通りにならない
実行効率をよくするために、最適化に重点を置いたコンパイラは最適化コンパイラと呼ばれる
3章: 文法と言語
ALGOL60 は 1960 年にプログラム言語としては初めて国際的な組織で開発されたものであるが、その構文がバッカス記法によって定義されている。それ以来、多くのプログラム言語の構文規則はバッカス記法、またはそれを拡張した記法で記述されるようになった
末端に現れる記号を終端記号、それ以外のものを非終端記号と呼ぶ。またεは空を示す記号
構文規則を図式で表現したものを構文図式と呼ぶ
文脈自由文法 G は生成規則の集合 P と記号 S の組として定義される
G = {P, S}
S は開始記号または出発記号と呼ばれ、P の中の少なくとも 1 つの生成規則の左辺に現れていなければならない
文がどのような生成規則から生成されたか、構造を調べることを構文解析という。その結果得られた木は解析木と呼ばれる
ある文の解析木が 2 通り以上存在すれば、その文はあいまいであるという。あいまいな文を生成できる文法をあいまい文法という
4章: 字句解析
ここでは字句解析のプログラムを機械的に作り出す方法を解説
字句の形は文脈自由文法よりも簡単な正規表現で定義できる
字句の定義を正規表現で表現したものから、その字句を読み取る有限オートマトンを機械的に作成する方法を述べる
字句解析の流れ
読み込んだ原始プログラムの中で最後に返した文字の位置を覚えていて
呼ばれたら、その次の文字を返す。もし、返す文字がなかったらファイルから次のひとかたまりを読み込んで、その最初の文字を返す
本書では、字句解析の結果として得られる字句の内部表現のことをトークンまたは符と呼ぶ。字句読み取りのプログラムは、字句解析器や走査器とも呼ばれる
オートマトン
計算機の構造や動作を抽象化したモデルの 1 つ。内部に固有の状態と、状態を変化させる規則の集合を持ち、外部からの入力に応じて状態を変化させるもの
有限オートマトン（finite automaton）
有限個の内部状態を持ち、与えられた記号列を読みながら状態遷移し、その記号列がある言語の文であるかどうかを判定するもの
非決定性有限オートマトン（nondeterministic finite automaton, NFA）と決定性有限オートマトン（deterministic finite automaton, DFA）
NFA は 1 つの入力記号に対して、複数個の状態遷移の可能性がある
DFA は複数の遷移の可能性がない。1 つに決まる
DFA とは、以下の条件を満たす有限オートマトンである
εによる遷移がない
1 つの状態から同じ記号による異なった状態への遷移はない
DFA の作成方法。NFA に対応する DFA は以下の手順で作成できる
NFA の初期状態とその初期状態からε遷移で辿れるすべての状態からなる集合を DFA の初期状態とする (1)
状態の集合からの遷移は、その集合の要素からの遷移の合併とする (2)
上記 (2) を、新しい集合および遷移が得られなくなるまで繰り返す (3)
状態数最小化のアルゴリズム
与えられた DFA の状態を、その最終状態からなる集合と、それ以外の状態の集合の 2 つの集合にわける (1)
各集合を遷移の種類によって分割する。すなわち、その集合の要素 s, t からの遷移の種類が同じであれば同じ集合に入れ、そうでなければ別の集合に入れる (2)
各集合を遷移先によって分割する。すなわち、その集合の要素 s, t から同じ記号による遷移で別の集合（この分割前の集合で）の要素に行くものがあれば、s と t を別々の集合に入れる (3)
(3) を繰り返して、どの集合もさらに分割できなくなったら終わる
最長一致と最短一致
複数の分解方法が考えられる場合がある
できるだけ長い文字列を得ようとするのが最長一致、逆に短い文字列を得ようとするのが最短一致
場合によって、適するものが違う
5章: 構文解析
ここでは、まず構文解析の理論と実際の歴史を述べる。その後、構文解析の手法の代表的な 3 つを述べる
再帰的下向き構文解析 / LR 構文解析 / 演算子順位構文解析
これから読み込むものの形を先に仮定して、それに合致するかどうか調べていく構文解析法を「下向き構文解析法」と呼ぶ
その中で、構文解析のプログラムが再帰手続きで構成されるものを「再帰的下向き構文解析」と呼ぶ
下向き構文解析法の問題点は後戻りと左再帰性
後戻り: 探索の際、ある組み合わせが解でなかったなら、戻って別の組み合わせを試す。その組み合わせを試しても解でなかった場合、さらに探索木を戻り、新たな組み合わせを試すこと
左再帰性: ある非終端記号を展開した結果、その先頭（最も左）にその非終端記号自身があらわれるような再帰のこと
LL(1)文法
αまたはβのどちらかを選択する時、その時の入力の先頭記号を 1 つ見ることによって（後戻りの起こりえない）選択をできる文法
一般に k 個の記号を見ることによってうまく選択できるような文法を LL(k)文法という。ただし、実際のコンパイラでは k = 1 以外が使われることはあまりない
集合の定義
First(α): αの先頭の終端記号になりうるものの集合
Follow(A): 文形式の中で A の直後の終端記号になりうるものの集合
Director(A,α): A をαに展開すべきか判定するための終端記号の集合
上向き構文解析法
原始プログラムを左から右に走査しながら、還元できるものを順次還元していく方法。すでに解析をした結果はスタックに積んでおき、スタックの中に還元できるものがそろったら、それを還元しその結果で置き換えるという方法がとられる
シフトと還元の操作を適宜行う構文解析をシフト還元構文解析と呼ぶ
コンパイラで使われるシフト還元構文解析法は、各時点でシフトか還元か間違いなく決められるもので、後戻りなど必要ないもの。そのような構文解析法として、LR 構文解析法と演算子順位構文解析法がある
シフト / 還元競合、あるいは還元 / 還元競合があると、そのどちらを実行すればよいか一般には決まらない。そこで 1 つ先読みをして、それがどの Follow 集合に入っているかによって動作を決められるのが SLR(1)文法
SLR(1)文法では、競合を解決するのに Follow 集合だけを使っていたが、そこまでに読み込んでいた記号列も考慮するのが LR(1)文法
LR(1)の状態の中で、同じ核の集合を持つものを合併して作るのが LALR(1)状態
演算子順位構文解析法
演算子文法
演算子文法では、右辺に非終端記号が複数個あるときは、必ずその間に終端記号が入る。その終端記号が演算子にあたる
演算子順位文法
演算子文法の任意の 2 個の終端記号の間に =, <, > のうちたかだか 1 個の関係しか成り立たないならば、この文法は演算子順位文法といえる
構文解析法の選択
再帰的下向き構文解析
わかりやすい
欠点は適用できる文法の範囲が比較的小さいことと、式の場合などの構文解析の効率が演算子順位に比べれば落ちる
LR 構文解析
適用できる文法の範囲が広い
欠点は、構文解析表を人手で作成するのは困難なので、自動生成するプログラムが必要
演算子順位構文解析
一般的なアルゴリズムでは必ずしも効率はよくないが、対象を式に限定すれば、一番効率が良い
欠点は適用できる文法の範囲が比較的小さい
ある構文解析を適用しようとして、そのまま適用できない場合の対策には、以下が考えられる
意味情報を使う
意味解析に任せる
より強力な構文解析法を使う
複数パスで構文解析をする
文法の書き方を変える
言語を変える
ある言語の構文規則を与えたら、その言語の構文解析器を生成するのが、構文解析器生成系
6章: 意味解析
意味解析を行うためには、宣言された情報をまとめておく必要があり、一般に表の形にまとめられる。ここでは記号表と呼ぶ
意味規則を形式的に記述する方法として、属性文法（attribute grammer）がある。属性文法は構文規則に意味規則を付加したもの
記号表
記号表に入れる情報は一般に以下のようなもの（言語によって異なる）
名前 / 型 / 記憶域 / その他
記号表は、表の探索が効率良くできるように、一般には配列の形で実現される。記号表の中の各要素はエントリとも呼ばれる
記号表に対する操作は、記号表に新しいエントリを書き込む操作（登録）と、ある名前が記号表に入っているかどうか探す操作（探索）とがある
探索
探索で各要素を順番に調べる操作を探針と呼び、平均して (n+1)/2 回の探索が必要になる。この探索は線形探索と呼ばれる
速くする方法としては、二分探索とハッシュ法がある
二分探索: 名前をその大きさの順に登録しておき、名前の大小比較によって次に探索する場所を決めていくもの
探針の回数はほぼ [log2n]+1
n が大きい場合、探索の速度は線形探索よりずっと速くなるが、プログラムは少し複雑になる。登録操作が複雑になるのが欠点
ハッシュ法: 名前 x に対してある関数 f をほどこし、その結果の n=f(x) を使って表の第 n 番目を探すというもの
除算法 / 平方採中法 / 折り返し法などがある
ハッシュ法で表を引くアルゴリズムは次のように表される
名前 x からハッシュ関数 f を使って n=f(x) を求める
表の第 n 番目を調べて
そこに x が入っていたら、x は登録されていた
そこに何も入っていなかったら、x は登録されていない
そこに x 以外のものが入っていたら、衝突
衝突した場合の対応は大きく分けて、開番地法と連鎖法の 2 つがある
開番地法: fi(i=1,2,...) と複数個のハッシュ関数を用意しておき、fi で衝突したら fi+1 を使う。これを衝突がなくなるまで繰り返す
連鎖法: 衝突を起こしたものどうしをポインタでつなぐ方式。連鎖法には、連鎖の 2 つ目以降の名前を別領域に格納する方法もある（あふれハッシュ法）
どちらも一長一短あるが、初めから余裕を持って大きな表をとっておける場合は開番地法、そうでない場合はあふれハッシュ法がよい
ハッシュ表と記号表は分けたほうがよいことが多い
属性文法
解析木の上から下に値が決まっていくのは相続属性と呼ばれる。反対に下から上に値が決まっていくのは合成属性と呼ばれる
属性文法が与えられている時、G の任意の文の解析木に対して、その属性の評価を求めることができるプログラムが属性評価器
与えられた属性文法 AG が、そのどんな文の解析木に対しても依存グラフがサイクルを持たないようなものである時、AG は非循環属性文法と呼ばれる
解析木の上で依存グラフを重ねるのでなく、各生成規則の属性依存グラフをどのように重ねてもサイクルのない属性文法を絶対非循環属性文法という
絶対非循環属性文法であれば、その属性評価器を作ることができる
適用できる範囲があまり広くないが、効率のよい属性評価ができるクラスとして、構文解析と同時に属性評価ができるクラスがある
これらは、コンパイラの 1 つのパスで属性評価までできてしまうので、1 パス型の属性文法と呼ばれる
1 パス型属性文法
S 属性文法
どの構文解析法とも組み合わせることができる
合成属性だけを持ち、相続属性を持たない属性文法
L 属性文法
LL 構文解析法と組み合わせることができる
属性文法において、任意の生成規則 X0→X1X2...Xn があるとする。任意の Xk(1<=k<=n) の相続属性が、X0 の相続属性と Xi(1<=i<=k-1) の合成属性だけに依存するもの
LR 属性文法
LR 構文解析法と組み合わせることができる
属性文法が L 属性文法であり、その基底文脈自由文法のすべての LR 状態について、そこで必要な相続属性の値が求められるもの
7章: 誤りの処理
コンパイラにとって、正しく書かれたプログラムを正しく処理することはもちろん必要だが、誤ったプログラムを適切に処理することがそれに劣らず重要
誤りの処理には以下がある
誤りの発見 / 誤りの情報の出力 / 誤りの修復 / 正常処理への復帰など
誤りの発見
誤りには構文上の誤りと意味上の誤りがある
構文上の誤りには構文解析の時に発見できる
意味上の誤りとして見つけられる主なものは、ある名前の宣言とその使い方に矛盾があるものであり、意味解析の時に発見できる
誤りの情報の出力
原始プログラムの誤りを発見したら、それを使用者に知らせなければならない。その情報として出力するものをエラーメッセージという
誤りの修復
誤りの箇所を正しいもので置き換える、あるいは正しいものがそこにあったごとくに処理するのが誤りの修復
正常処理への復帰
一般に、原始プログラムには複数個の誤りがあると考えなければならないから、1 回のコンパイルでできるだけ多くの誤りを見つけるのが望ましい。そのためには誤りがあったらそこのコンパイルは正常に続けられないが、その処理をした後では、できるだけ早く正常の処理に復帰する必要がある。それはエラーからの回復と呼ばれる
8章: 実行時記憶と仮想マシン
ここでは実行時の記憶域管理の方法、原始プログラムから目的コード（仮想マシン語）への変換の方法、目的コードの実行方法（仮想マシンの通訳系）の説明をする
実行時記憶域
領域としては以下などがある
実行中に割り当ての変化しない静的記憶域
Fortran の common 変数など
ブロックへの出入りに応じてブロックごとの割り当て、解除を行うスタック型記憶域
各手続きの局所変数など
実行中に必要に応じてデータごとに割り当てていくヒープ領域
Pascal の new、C の malloc、Java の new など
仮想マシンと通訳系
仮想マシンとは、対象とするプログラム言語に適したマシンとして考えるもの
目的プログラムを実行するには、それを解釈して実行するプログラム（通訳系またはインタプリタという）があればいい
命令語は、通常、命令の機能を表す部分（機能部または操作部という）とその機能の対象を指す部分（番地部）からなる
命令には以下のようなものがある
ロード / ストア命令
演算命令
分岐命令
呼出し / 戻り命令
例外処理
その他のスタック操作命令
通常のレジスタマシンでは、どのレジスタに対してもその番号を指定して操作できるが、スタックでは常にその先頭に対してしか操作できない。そこでスタックにロードされているものを有効に利用するために、スタックの先頭 2 つを入れ替えたり、スタックの先頭にあるもののコピーを作って適当なところに入れる命令があるといい
9章: 目的コードの生成
ここでは目的コードとして、仮想マシンのコードではなく、機械語のコードを生成する方法を述べる
原始プログラムが構文解析され、意味解析された結果は中間語と呼ばれる形で表現される。コンパイラの前段階（フロントエンド）と後段階（バックエンド）とのインタフェースとなる
この中間語のプログラムを機械語のプログラムに変換するのがコード生成の仕事
中間語の様々な形式
構文木と有向非循環グラフ（directed acyclic graph）
3 番地コード
RTL（register transfer language）
式のコード生成
算術式に対しては、できるだけレジスタを有効に使って、途中結果をメモリに退避する回数を最小にする方法がある
式の中に関数参照があった場合、式の計算途中で関数呼び出しをするのではなく、関数呼び出しを先にやってから式全体の計算をしたほうがよい
文のコード生成
文には代入文、制御文、入出力文などがある。制御文には、繰り返し文・分岐文・手続き呼び出し文などがある
分岐文の or 条件の場合などでは、わかった時点で直ちに分岐を決定できる場合がある。そういう時に最後まで評価せず分岐を決定するものを「飛越し型」「短絡評価型」「制御フロー表現」と呼ぶ。最後まで評価するものを「数値表現」と呼ぶ
手続きの最初に実行されるコードをプロローグと呼ぶ。最後に実行されるコードはエピローグと呼ぶ
コード生成器生成系
いろんなマッチングがありうる時は、一般にはできるだけ大きいパターンにマッチするほうを選んだほうが良い。これを極大食い方式と呼ぶ
しかし、極大食いが常に最適な結果を与えるとはいえない
中間木をたどりながら、マッチするパターンの方法を複数組作っていき、最後にその中で最も効率の良いものを選ぶのがダイナミックプログラミングによるコード生成の方法
コード生成時にすべてを求めるやり方だけでなく、コード生成器作成時に求めておくやり方や、必要に応じてダイナミックプログラミングを行う方法が提案されている
実行時コード生成
コンパイル時にすべての目的コードを生成してしまうのでなく、実行時に全て、あるいは一部の目的コードを生成するのが実行時コード生成
実行時コード生成には以下の 2 つがある
実行時にならないとわからないデータを利用して、目的コードの一部を効率の良いコードにすることを目的とするもの（動的コード生成）
仮想マシン用に作られた目的コードを実計算機の機械語コードに変換するもの（JIT コンパイラ）
動的コード生成では、原始プログラムのどの部分に、動的コード生成を適用するかという問題がある。頻度高く実行される部分で、その中に実行時に定数となるものがあり、定数であることを利用した最適化の効果が大きい部分が良い
実行回数の目安は 1000 回から数万回くらい
JIT コンパイラ
Java の目的コードは、通常はバイトコードと呼ばれる仮想マシン語のコードであり、実行時にはそれが仮想マシン JVM（Java virtual machine）によって解釈実行される
バイトコードから機械語への変換は、一言で言えば、スタックマシンの機械語からレジスタマシンの機械語への変換
10章: 最適化とは
目的プログラムの最適化とは、効率の良い目的プログラムとすること
一般には最も良い目的コードを作り出すことは不可能であり、より良いコートとする努力をする
全然最適化していないものと比べれば、少しの努力でも相当な効果が得られる。しかし、ある程度の最適化をした後で、さらに効果を上げるためには大きな努力を必要とする
最適化には実行時間を短くする最適化と、所要記憶容量を小さくする最適化とがある
実行時間を短くするためにまず考えられるのは以下の 3 つ
命令の実行回数を減らす
より速い命令を使う
並列度を上げる
効果的な最適化を行うためには、プログラムの中で最も頻度高く実行される部分を最適化すれば良い
ループ内の命令ができるだけ並列実行されるようにする手法をソフトウェアパイプライニングという
ベクトル計算機は、一般にベクトル命令とスカラ命令を備えており、ベクトル命令による実行はスカラ命令のループによる実行よりも非常に高速。ベクトル計算機の性能を生かすためには、できるだけ多くのループをベクトル化する必要がある
並列計算機で効率よくプログラムを実行するためには、計算のロードをバランス良く各プロセッサに分配することと、各プロセッサでのメモリアクセスの局所性を高める必要がある
共有メモリ型の場合は、すべてのプロセッサからすべての変数に直接アクセスできる。プログラムのどの部分を並列に実行するか指定するだけで、並列実行が可能になる
分散メモリ型の並列計算機は、各プロセッサが独立のメモリを持ち、他のプロセッサのメモリにアクセスするためにはデータの転送（メッセージ転送）が必要。この転送のコストは他の演算に比べて一般に高いので、プロセッサ間のデータ転送を少なくすることが必要
11章: 最適化の方法
プログラム全体に渡って解析をして最適化するのは「大局的最適化」、プログラムのごく一部を解析して最適化するのは「局所的最適化」と呼ばれる
最適化が行われるのは、コンパイラの中では、構文解析と意味解析が終わった後である。一般には、ソースプログラムは中間語の形に変換され、その中間語のプログラムに対して最適化が行われる
中間語がいくつかの言語に対して共通のものであれば、その最適化は言語非依存の最適化であり、それらの言語のコンパイラで共用できる
中間語がいくつかの異なる計算機に対して共通のものであれば、中間語のプログラムをより効率の良い中間語のプログラムに変換する最適化は機械非依存の最適化であり、各マシンのコンパイラで共用できる
命令の実行回数を減らすためには、以下のような対応が考えられる
1 度実行した結果を再利用する
共通部分式の削除
コンパイル時に実行できるものはコンパイル時に実行してしまう
定数の畳込み
命令をより実行頻度の低いところへ移す
命令のループ外への移動
実行回数を減らすようにプログラムの形を変換する
ループの変換（ループつぶし、ループ融合、ループ展開、ループ if 展開）
式の性質を利用して実行を省略する
論理式の部分的評価、算術式の演算順序変更、式の簡素化
冗長な命令を取り除く
無用命令の削除、複写の削除
特殊化する
手続き呼び出しの展開、手続きの複製、オブジェクトのインライン割り当て、判定の置き換え
より速い命令を利用するには、以下のような対応が考えられる
必要なデータがなるべくレジスタに入っているようにする
計算機の持つ高性能な命令をできるだけ活用する
プログラムの局所性を高め、メモリアクセスを速くする
より単純な命令を利用する
レジスタ割り付け
大域的には、よく使われるデータはなるべくレジスタに入れておいたほうが良い
局所的には、一度レジスタに取り出したデータはできるだけそこにおいて利用したほうが良い
レジスタの割り付けをうまく行うためには、プログラム上でデータが生成されてから、それが参照されなくなるまでの生存期間を解析する必要がある
メモリ階層
レジスタ
一次キャッシュ
二次キャッシュ
主メモリ
ディスク
他プロセッサのメモリ
演算の強さの軽減
べき乗は乗算で、乗算は加算で、除算は乗算で置き換えるのが演算の強さの軽減
マシンによって違いはあるが、一般的には、演算の強さの軽減をしたほうが速度は速い
並列度を上げる
並列実行のレベルで分けると、以下の 2 つがある
命令レベルでの並列実行
命令の順序を選ぶのは、命令スケジューリングと呼ばれる
プロセッサレベルでの並列実行
同一のプログラムを実行するが扱うデータは異なるものをデータ並列という
並列機の台数の大小にあまり依存せずに適用でき、台数が多い時に大量の計算に適用した時の効果が大きい
異なるプログラムを実行しながら、お互いに同期をとったり、データのやり取りをするものをタスク並列という
タスク並列は、技術計算のプログラムでは並列性が比較的小さい
本書では主としてデータ並列を扱う
データ並列実行
（分散メモリの場合だけでなく）共有メモリの場合でも、メモリ上にデータをどのように分散するかが性能に大きな影響を与える
共有メモリの場合、各プロセッサにキャッシュを持たせてアクセス速度の向上を図っている
あるプロセッサ A のキャッシュに入っているブロックと同じブロックに対して、他のプロセッサ B が書き込みを行うとする
書き込まれたデータをプロセッサ A が参照していてもいなくても、A のそのブロックのキャッシュが無効になるため
共有メモリ型並列計算機の場合
各繰り返しに要する時間が一定でない場合は、最初に全部の繰り返しを割り当ててしまうのではなく、一部分を各プロセッサに割り当てる。それを実行し終わったタイミングで、次の残りの一部を割り当てるようにすれば良い
分散メモリ型並列計算機の場合
ユーザーにデータの配置の仕方を指定させる言語が考えられている
最適化の方法の適用順序
どのような順序で適用したらよいかを一般的に決めるのは難しい
一般的にはコンパイラではソースプログラムをまず高レベルの中間語に変換してから、次に低レベルの中間語に変換し、最後に機械語の目的コードに変換するものが多い
どのレベルで適用するかが決まっても、それぞれのレベルの中で、各種の最適化の操作をどのような順序で適用するかも簡単には決められない問題である
12章: 制御とデータの流れの解析
本章では、プログラムの大域的な解析の基本的な方法として、制御の流れの解析とデータの流れの解析方法を述べる
制御フローグラフ
制御の流れをグラフで表現したものを制御フローグラフという
制御フローグラフは、プログラムの分岐や合流の様子をグラフで表現するも。分岐も合流もない部分を節点として、それらの間を分岐や合流を表す有向辺で結んだ有向グラフ
データの流れの解析とは、どこの代入文によって定義された値がどこで使われるかといったことを解析することである。その結果を使って大域的な共通部分式の削除、命令のループ外への移動、無用命令の削除などをできる
共通部分式の削除
共通部分式を見つけるためには、同じ形の式で同じ値を持つものを探せば良い。さらに共通部分式の定義を広げて、違う形のものでも同じ値を持つものは共通部分式であるとして良い
手続き間解析
1 つの手続きの中での最適化のために他の手続きを解析するのが手続き間解析
手続き間の解析で得られる有用な情報は主に 2 つ
副作用があるか、すなわち呼ばれた手続きでどの引数の値が変わるか、どの引数の値は変わらないか
引数は定数か。ある場所からの呼び出しの時に定数であることがわかれば、手続きの複製を作って、そこではその引数を定数とできる
ポインタ解析
ポインタ解析は別名解析の 1 つ
別名とは、形が違うものが同じものを指していることをいう
ポインタ変数が指すものの解析、あるいはそれによって起こる別名を解析するのはポインタ解析と呼ばれる
13章: 静的単一代入形式（SSA 形式）
静的単一代入形式、または SSA 形式（static single assignment form）とは、プログラムの表現形式の 1 つ。そのプログラム上のすべての変数の使用に対して、その使用に対応する定義は 1 ヶ所しかないように表現したもの
SSA 形式による表現の利点
SSA 形式による表現は、変数の使用に対応する可能性のあるすべての定義を表現するのに比べて粗な表現であるから、メモリ消費量は少なくてすむ
従来の方法での大域的最適化のアルゴリズムは、基本ブロックを要素とした大域的アルゴリズムと基本ブロック内の局所的アルゴリズムの 2 つからなるものが多かったのに対して、大域的にも局所的にも同じアルゴリズムで最適化が行える
SSA 形式は以下の手順で得られる
流れグラフ（制御フローグラフ）から支配辺境を求める
支配辺境にφ関数を挿入する
変数の名前替えをする（ここまでが SSA 変換）
SSA 形式から通常の形式に戻す（SSA 逆変換）
制御依存グラフ
制御依存グラフは SSA 形式と直接関係ないが、その求め方が SSA 形式の求め方と関係が深いので、ここで述べる
分岐した時、何が実行されるかに重点を置いて、ブロックをまとめたものが制御依存グラフ
制御依存は、X からのある辺を辿るとその後必ず Y を通るが、別の辺を取れば Y は通らないことを表す
SSA 形式での最適化のアルゴリズム
以下のアルゴリズムに対して、SSA 形式を使うことができる
無用命令の削除 / 共通部分式の削除 / ループ外への移動 / 帰納変数 / 演算の強さの軽減と判定の置き換え / 定数伝播 / 部分冗長性の除去 / ポインタ解析
帰納変数とは、ループ内で定数刻みで値が変わる変数
14章: 命令スケジューリング（並列実行）
本章では、命令レベル並列実行ができるアーキテクチャのマシンで、その機能をできるだけ生かすコンパイラの最適化技法を述べる
命令スケジューリングのアルゴリズムは、プログラムの制御の流れを考慮する必要のない基本ブロックを対象としたものと、基本ブロック間の分岐を含んだフローグラフを対象とするものがある
基本ブロック内の命令スケジューリング
基本ブロックの中でのプログラムの各命令の依存関係は DAG（directed acyclic graph）と呼ばれる有向非循環グラフで表現できる
基本ブロク内の命令スケジューリングとしては、リストスケジューリングと呼ばれるものがよく使われる
基本ブロックにまたがった命令スケジューリング
基本ブロック内の命令スケジューリングだけでは効果は限られているから、より最適化するためには対象範囲を拡大する必要がある
ループやより一般的な分岐を対象とする命令スケジューリング法としては、トレーススケジューリング / パーコレーションスケジューリング / スーパブロックスケジューリングなどがある
トレーススケジューリング: 対象とするプログラムの中の各分岐命令についてどちらに分岐するかの確率を求めておき、確率の高い方を優先してスケジュールする方法
パーコレーションスケジューリング: 制御フローグラフの下から上に向かって命令を滲み出させていくことにより、並列度をあげようとする方法
スーパブロックスケジューリング: 頻度高く実行される命令列を 1 つのブロックのように考えて命令スケジューリングを行う方法
ソフトウェアパイプライニング
コードのサイズを増大させずに並列性を引き出す方法
ループの中に条件文がある場合には、ソフトウェアパイプライニングは単純にはできない
条件文がある場合は、階層的縮約や条件変換の方法が提案されている
階層的縮約: まず条件文をスケジュールし、その結果を 1 つの複合命令とみなして他の命令とあわせてスケジュールする方法
条件変換: 条件判定の結果によって then 部か else 部が実行される制御依存のプログラムを、述語付き命令を使った直線的なプログラムに変換する方法
15章: レジスタ割付け
13 章までに述べてきた最適化の手法は主として中間コードに適用して、より効率の良い中間コードを得るためのものであったが、中間コードから機械語の目的語のコードを生成するにはレジスタ割付けが必要になる
目的コードを生成するためには、どんな命令語を使うかという命令語の選択と、それにどのレジスタを使うかというレジスタ割付けが必要。また両者の前後関係もいろいろある
またどれだけの範囲を考慮して行うかも問題。広い範囲を考慮したほうがよりよい結果が得られる可能性がある。しかし、そのためには広い範囲の解析が必要になり、アルゴリズムは一般には複雑になる
簡単な割付け法
プログラムのどの範囲にどのレジスタ群を割り付けるかが決まったら、その範囲の中で候補となる変数が何回参照されているか調べ、参照頻度が高いものから順に割り付けていく方法
割り付けられるレジスタの数を n としたら、n-1 個までをこれで割り付け、それ以外の変数は 1 つ残したレジスタにその都度 Load することにする
対象とするプログラムの範囲全体に対して一挙にレジスタ割付けをする方法
対象とするプログラムの範囲の先頭から順次割り付けていく方法もある。退避させるものをどう決めるかはいくつかのやり方がある
その場所以降で次に使われる場所が一番遠くにある変数が入っているレジスタを選ぶ
その場所以降でその値の使用回数が最小のものを選ぶ
その値が最近使われたところからその場所までの長さが最も長いものを選ぶ（LRU、least recentry used）
生存区間を使ったレジスタ割付け
レジスタ割付けの一般的な方法は、変数の生 / 死の情報を使う方法
変数 x の生存区間と変数 y の生存区間に共通部分がなければ、x と y に同じレジスタを割り付けることができる。このことを生かしたレジスタ割付けのアルゴリズムはいくつかある
区間グラフ
循環区間グラフ
連接グラフ
螺旋グラフ
生存区間の干渉グラフを使ったレジスタ割付け
生存区間の干渉グラフとは、各生存区間を節とし、生存区間に重なりのある 2 つの生存区間を辺で結んだグラフ
生存区間に重なりのある 2 つの生存区間には同じレジスタを割り付けることができないから、その 2 つの生存区間はお互いに干渉するといわれる
この干渉グラフの制約条件のもとで、レジスタ割付けを考える
基本アルゴリズム
与えられた干渉グラフに対して、割付けに使用できるレジスタの個数が N とする。これは干渉グラフを N 色で彩色する問題になる
16章: 配列要素の依存解析
ベクトル化や並列化をするためには、ループの中の配列要素の依存解析をする必要がある
ベクトル化や並列化をするために、プログラム変換を行うには、データの依存関係が変わらないことを保証する必要がある
データの依存関係には以下のものがある
フロー依存（真の依存）
「a=...」のあとに「=...a」のような式がある場合
実行の順序を逆転するような変換はできない
逆依存
「=...a」のあとに「a=...」のような式がある場合
順序を逆転するような変換はできない
出力依存
「a=...」のあとに「a=...」のような式がある場合
両者の値に関係はないが、これ以降で使われる値には関係がある
入力依存
「=...a」のあとに「=...a」のような式がある場合
実行順序が変わっても結果に関係はなく、プログラム変換をする場合に考慮する必要はない。しかし、先にロードした配列要素の値が、後でも使える場合がある
ループ内の依存関係とベクトル化
配列要素の依存関係を矢印で表現したものを依存グラフと呼ぶ
ベクトル化するということは、S1(k)をすべての k(2<=k<=n)について実行してから S2 を同様に実行することを意味する
ベクトル化は一般に次のような手順で行えば良い
ループ内の変数のデータ依存関係を調べる
データ依存関係のグラフ（依存グラフ）を作る
依存グラフにサイクルがない場合は、必要ならば文を適当に並べ替えて、依存関係の矢印がすべて下向きになるようにする（このように並べ替えるのはトポロジカルソーティングと呼ばれる）。その結果をベクトル化できる
依存グラフにサイクルがあるときは、名前替えによるサイクルの解消を試みる。解消できないサイクルのベクトル化は諦め、それを 1 つの文のように扱う
データ依存関係の解析法
以下のような式で依存関係があるかどうかは、c*j+c0 = d*k+d0 となるような j と k があるかで決まる
17章: ループ変換
今までのループ変換では主として単一計算機でスカラ演算をする場合を考えていた。ここでは主としてベクトル計算機や並列計算機を目的計算機とする場合に有効なループ変換を考える
各種のループ変換
ループ分配
1 つのループを複数のループに変換するのがループ分配
効果
ベクトル化の変換である
依存の少ないループができる
完全入れ子ループができる
大きなループが小さなループに分割されアクセス範囲が狭くなる
データの局所性が悪くなる（短所）
ループの判定の回数が増える（短所）
ループ融合
複数のループを 1 つのループに変換する。ループ分配の逆の変換
効果
ループ分配の逆の効果となる
データの局所性が良くなり、ループの判定の回数が減る。しかし、ループが大きくなり、アクセスするデータの範囲が広くなる
ループ交換
多重の完全入れ子ループで入れ子の順序を交換するのがループ交換
効果
内側のループのデータの局所性が増す場合がある
最内側のループをベクトル化可能にする場合がある
外側のループを並列化可能とする場合がある
ループ逆転
あるループについて、繰り返しの順序を逆転するのがループ逆転
効果
他のループ変換を可能にする場合がある
ループの終了判定の目的コードが簡単になる
ループ傾斜
外側のあるループの制御変数の値を内側のあるループの制御変数に加える変換
効果
波頭計算のループを並列化可能にする
距離ベクトルに負の要素を含まないようにできる
その他
波頭変換 / ループ細分 / ループタイル化 / ループ展開 / ループ合体 / ループつぶし / ループ皮むき
18章: データ分散と通信
ここでは主として分散メモリ型の並列計算機で SPMD（single program multiple data）型のプログラムを考える
この場合、各プロセッサでは同じプログラムが並列に実行される。各プロセッサでの計算はそのプロセッサのメモリにあるデータを使って行われ、他のプロセッサにあるデータを必要とするときは、プロセッサ間のデータ転送あるいは通信を行って必要なデータを用意してから実行することになる
したがって、分散メモリ型の並列計算機で効率よく SPMD 型のプログラムを実行するためには、各プロセッサで必要とするデータはできるだけそのプロセッサに配置しておくことが重要である
大きな配列データを扱うプログラムでは、その配列のどの部分をどのプロセッサに置けば最も効率良い計算ができるかを考える必要がある。目的は並列性を最大にし、通信を最小にすること
各プロセッサでの私物化
並列化前の元のプログラムでは 1 つの変数であっても、それを各プロセッサに別々に私物化して持たせることによって通信の必要性が減り、並列性を高めることができる
配列分散の解析から通信の解析まで
HPF（high performance Fortran）のような言語で配列の分散を指定した場合は、それによって、配列のどの部分がどのプロセッサに置かれるかが決まる（配列分散の解析）
配列を各プロセッサに分散し、そのインデックス集合の計算ができたら、次には配列ループの繰り返し点を各プロセッサに分散する（計算分散の解析）
各プロセッサへの計算の分散ができたら、次に各プロセッサでの計算に必要なデータが各プロセッサにそろっているかどうかを解析し、必要なデータの転送命令を挿入する（通信の解析）
データの転送命令は、そのデータを必要とする計算の前に実行される必要がある。転送のオーバーヘッドを減らすために、できるだけまとめて転送するのがよい。これをメッセージのベクトル化と呼ぶ
19章: データの流れの解析の別法
データの流れを解析する従来の標準的な方法は、制御フローグラフの各ブロックに関してデータの流れの等式を解く方法か、SSA 形式を使う方法であった。ここではそれとは別の方法として、データ間の関係を Datalog 言語で表現し、それを二分決定グラフ（BDD: binary decision diagram）を使って解く方法を説明する
これらの方法は、主としてコピー文（右辺に演算のない代入文）によるデータの流れを解析するものであり、ポインタ解析などに使われる
Datalog 言語
Datalog 言語は演繹データベース記述言語として使われている言語であり、その構文は Prolog 言語のサブセットとなっている
二分決定グラフ BDD
Datalog プログラムあるいは集合や推論規則を使ったアルゴリズムを実行するのに二分決定グラフを使うことができる
二分決定グラフは真か偽かの値を返す関数をグラフで表現する方法
20章: オブジェクト指向言語での最適化
ここではオブジェクト指向言語特有の最適化の問題を、主として Java 言語を対象として説明する
オブジェクト指向言語では a.f(b) というメソッド呼び出しで、a は多様な型の値をとりうるので、実際に呼び出されるメソッド f はその方に応じて変わる可能性がある。このような多様性はメソッド呼び出しのオーバーヘッドの増加や最適化の難しさを引き起こす
コンパイル時にそのような多様性がないことが確かめられれば、メソッド呼び出しをインライン展開するなどして、高速化できる
Java での多様性のあるメソッド呼び出しには、仮想メソッド呼び出しとインタフェース呼び出しがある
メソッド呼び出しを効率よくするためには、実際に呼び出すメソッドが 1 つしかないとわかったときに、仮想メソッドテーブルを経由した仮想呼び出しを利用しないようにする。直接そのメソッドを呼び出すようにするか、呼び出している場所にインライン展開する
これを脱仮想化という
クラスの階層構造と各クラスで定義されているメソッドの情報を使って、呼び出されるメソッドの範囲を解析するのはクラス階層解析と呼ばれる
例外検査の除去
Java プログラムの実行時に行う例外検査には以下のようなものがある
オブジェクトが null でないかをチェックする null 検査
配列の添字式の値が配列の範囲にあるかをチェックする範囲検査
割り算が 0 による割り算であるかをチェックする 0 割り算検査
例外検査があると、それにかかる時間だけでなく、例外検査に依存する命令を自由に移動できないので最適化に制約を受ける
例外発生はありえない、という解析がコンパイル時にできれば、例外検査を除去できる
脱出解析
脱出解析とは、オブジェクトの生存区間が、そのオブジェクトを生成したメソッド内で閉じているかどうかの解析である。閉じていない場合は、そのメソッドから脱出しているといわれる
脱出していなければ、そのオブジェクトはヒープではなく、スタックに割り付けることが可能である。また、そのオブジェクトに関する同期操作を除去できる
例外ハンドラの見つけ方
例外はまれにしか発生しないものと考え、例外が発生した時は時間がかかっても通常の処理では例外に関する準備的な処理は何もしない、とするのが普通のやり方である
しかし、例外がしばしば発生するプログラムでは、例外発生時の処理の最適化が有効である
Last updated