6 - 数理・計算科学専攻

コンパイラ最適化過程の
画面同期による可視化
東京工業大学
理学部
情報科学科
中川元貴
(0317754)
平成 18 年度卒業論文
指導教官佐々政孝教授
２月８日
目次
第1章
1.1
1.2
1.3
はじめに
背景 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
研究動機 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
研究概要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
第 2 章準備
2.1 COINS について . . . . . . . . . . . .
2.1.1 背景 . . . . . . . . . . . . . . .
2.1.2 構成 . . . . . . . . . . . . . . .
2.1.3 LIR の内部構造 . . . . . . . . .
2.2 制御フローグラフ . . . . . . . . . . . .
2.3 静的単一代入形式 . . . . . . . . . . . .
2.4 プログラムの最適化 . . . . . . . . . .
2.4.1 無用命令除去 . . . . . . . . . .
2.4.2 コピー伝播（定数伝播も含む）
2.4.3 ループ不変式の移動 . . . . . .
2.4.4 共通部分式除去 . . . . . . . . .
2.4.5 その他の最適化 . . . . . . . . .
4
4
4
5
.
.
.
.
.
.
.
.
.
.
.
.
6
6
6
6
7
11
14
14
14
15
15
15
16
第 3 章既存の COINS 可視化システム
3.1 CoVis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 trace2html . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
17
17
第4章
4.1
4.2
4.3
.
.
.
.
.
.
19
19
19
22
22
23
23
第 5 章プログラム最適化過程の可視化例
5.1 例 1.Appel の例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 例 2. バグ発見の例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
25
29
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
可視化プログラムの設計と実装
ユーザの要望 . . . . . . . . . . . . . . . . . . . . . .
html と javascript を利用した可視化プログラムの設計
実装 . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3.1 COINS の出力する LIR の構成 . . . . . . . . .
4.3.2 制御フローグラフの描画 . . . . . . . . . . . .
4.3.3 本手法での画面同期方法 . . . . . . . . . . . .
1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
第 6 章議論
6.1 評価 . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 関連研究 . . . . . . . . . . . . . . . . . . . . . . . .
6.2.1 COINS における既存のツール . . . . . . . .
6.2.2 コンパイラ最適化過程の可視化の研究 . . .
6.2.3 XML を用いた最適化過程の可視化の研究 . .
6.2.4 その他コンパイラ最適化過程の可視化の研究
第 7 章まとめ
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
33
33
33
33
34
34
34
35
2
図目次
2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8
2.9
2.10
COINS 構成図 . . . . . . . . .
Module クラスの内部表現 . .
FlowGraph クラスの内部表現
instrList の内部表現 . . . . . .
制御フローグラフ . . . . . . .
SSA 形式の例 . . . . . . . . .
無用命令除去 . . . . . . . . .
コピー伝播 . . . . . . . . . .
ループ不変式の移動 . . . . .
共通部分式除去 . . . . . . . .
.
.
.
.
.
.
.
.
.
.
7
8
9
10
12
14
14
15
15
15
3.1
3.2
CoVis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
trace2html . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
18
4.1 本手法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 実装の概要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
22
5.1
5.2
5.3
5.4
.
.
.
.
.
.
.
.
.
.
条件付定数伝播前の Appel の例
条件付定数伝播後の Appel の例
ループ不変式の移動前 . . . . .
ループ不変式の移動後 . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
27
28
31
32
第 1 章はじめに
1.1
背景
COINS [4] は、コンパイラ研究の基盤となる共通のコンパイラの作成を目標として研究
が進められているコンパイラ・インフラストラクチャである。つまり、組み合わせ可能な
コンパイラ部品で構成される共通インフラをつくり、その上に各企業や研究者がそれぞれ
の目的に合う機能部品を加えることができるようにすることを目的としている。
1.2
研究動機
COINS において、新しい最適化器を作った際にそれが正しく動いているかどうかを確認
することは重要である。それを確かめるひとつの方法として、COINS の出力する、制御フ
ローグラフ形式の低水準中間表現1 を含むトレース情報を見る方法があるが、トレース情報
のテキスト量は膨大であり、確認するのは大変である。
そこで現在 COINS には CoVis、trace2html の 2 つの可視化ツールが用意されている。
しかし、CoVis には制御フローグラフの表示機能はあるが各最適化器ごとに LIR を表示す
る機能がない。trace2html には各最適化器ごとに LIR を表示する機能はあったが、制御フ
ローグラフを表示する機能がなかった。
また、trace2html で使用される COINS コンパイラの出力する LIR についても、SSA 最
適化の LIR を出力することができなかったため、新たな SSA 最適化器を作ったときにその
最適化器の LIR を表示することができなかった。
そこでこの 2 つの機能をもつ新たな可視化ツールを持つものが期待され、さらに SSA 最
適化の LIR を出力する機能を COINS コンパイラに持たせることが要請されていた。
1
以下単に LIR
4
1.3
研究概要
本研究では、
• COINS コンパイラに SSA 最適化のトレース情報の出力をもたせる
• trace2html をベースに、各最適化器ごとにソースプログラム・LIR・lir2c2 ・制御フ
ローグラフを表示する
• ソースプログラム・LIR・lir2c・制御フローグラフの同期をとらせる
の 3 つの機能を実装した。
COINS コンパイラはトレースオプションを指定すると LIR 形式のトレース情報を出力す
ることができる。また同様にオプション指定することで lir2c を出力することもできるが、
ここではより簡単に lir2c を出力できるように COINS コンパイラを改良した。
今回実装した可視化ツール内ではこれらのファイルから DOT 言語を用いて Graphviz [2]
から制御フローグラフを作成し、アルゴリズムは既存の可視化ツールである trace2html を参
考としている。trace2html は html 言語に書き出すため、画面の同期を取るために javascript
を利用して表示することにした。
2
LIR を C 言語風に変換したもの
5
第 2 章準備
本論文の説明にあたって COINS の説明と制御フローグラフ、SSA 形式、プログラムの最
適化の知識が必要となる。本章ではこれらに関する説明を行う。
2.1
COINS について
本節では、本手法を実装、実験を行う際に利用した並列化コンパイラ向け共通インフラ
ストラクチャ(compiler infra structure, COINS) について説明を行う。
2.1.1
背景
COINS は、コンパイラ研究の基盤となる共通のコンパイラの作成を目的として 2000 年
度より研究が進められている [4]。つまり、組み合わせ可能なコンパイラ部品で構成された
共通インフラを作り、その上に各企業や研究者がそれぞれの目的に合う機能部品を加える
ことができるようにすることを目的としている。COINS では、SSA 最適化を行っている。
現在、多くの最適化コンパイラで SSA 最適化の実験が行われているが [6, 7, 9, 15]、本研究
室の佐々政孝教授が COINS の研究プロジェクトに携わっているため、本研究室では COINS
をインフラとして利用した研究が多く行われており、データの蓄積が行いやすいため、本
手法の実装を行うインフラに COINS を選択した。
2.1.2
構成
一般にコンパイラは、フロントエンド (front end) とバックエンド (back end) から構
成される。フロントエンドは、原始プログラム (source program) を中間コード (intermediate code) と呼ばれる内部形式に変換する。バックエンドは、中間コードを計算機の
機械コード (machine code) に変換する。フロントエンドはさらに、字句解析器 (lexical
analyzer)、構文解析器 (syntax analyzer) 、意味解析器 (semantic analyzer) に分け
られる。バックエンドは、最適化器 (optimizer) とコード生成器 (code generator) に分
けられる。これら各部分は、コンパイラのフェーズと呼ばれる。
COINS では、複数の入力言語、複数の対象機種に対応する 2 つの中間コードがある (図
2.1)。入力言語の論理構造に近いレベルの中間コードを、高水準中間表現 (high-level intermediate
representation, HIR) 1 と呼び、機械語に近いレベルの中間コードを、低水準中間表現
(low-level intermediate representation, LIR) 2 と呼ぶ。
1
2
以後 HIR と呼ぶ
以後 LIR と呼ぶ
6
図 2.1: COINS 構成図
2.1.3
LIR の内部構造
本節では、本手法で使用する中間表現である LIR の内部表現について説明する [10, 13]。
LIR では、ソースファイルごとに Module クラスが作成される。Module クラスの内部表
現を図 2.2 に示す。
図 2.2 に示したように、Module クラスはグローバル変数のシンボルテーブルである globalSymTab と、関数である Function クラスのリストから構成されている。また、Function
クラスはローカル変数のシンボルテーブルである localSymTab と、制御フローグラフであ
る FlowGraph クラスから構成されている。FlowGraph クラスの内部表現を図 2.3 に示す。
図 2.3 に示したように、FlowGraph クラスは基本ブロックである BasicBlk クラスのリス
トから構成されている。また、BasicBlk クラスは、先行ブロックのリストである predList、
後続ブロックのリストである succList、ブロック内の命令のリストである instrList から構
成されている。instrList の内部表現を図 2.4 に示す。
図 2.4 に示したように、instrList は LirNode クラスを要素とするリストである。LIR で
は命令を木構造で表し、LirNode はその木を構成するノードである。LirNode は抽象クラ
7
図 2.2: Module クラスの内部表現
8
図 2.3: FlowGraph クラスの内部表現
9
図 2.4: instrList の内部表現
10
スであり、実際のインスタンスはそれを継承した次のいずれかのクラスに属する。
• LirIconst: int 型定数を表すクラス。
• LirFconst: double 型定数を表すクラス。
• LirSymRef: シンボルを表すクラス。
• LirLabelRef: ラベルを表すクラス。
• LirUnaOp: 単項演算を表すクラス。
• LirBinOp: 二項演算を表すクラス。
• LirNaryOp: オペランドの数が 1、2 以外の式を表すクラス。
2.2
制御フローグラフ
この節では、制御フローグラフについての説明を行う。
まず、制御フローグラフの例を図 2.5 に示す。
11
0:
1:
a=1
b=1
c=1
if(...)
2:
c=c+1
if(...)
3:
b=b+3
4:
b=b+2
5:
a=b
6:
a=b+c
7:
b=1
if(...)
8:
b=b+2
c=c+1
9:
if(...)
10:
a=a+3
if(...)
11:
図 2.5: 制御フローグラフ
12
用語 2.1 (基本ブロック) 間に分岐も合流もない文 (statement) の列を基本ブロック (basic block) と呼ぶ。基本ブロック中の文は先頭から最後まで一直線に実行される。以後、
基本ブロックは単にブロックと呼ぶことがある。
用語 2.2 (制御フローグラフ) プログラムの制御の流れをグラフであらわしたものを制御
フローグラフ (control ﬂow graph) と呼ぶ。制御フローグラフは基本ブロック (basic
block) をノード (node) として、それらの間を分岐や合流をあらわす有向辺 (directed
edge) で結んだ有向グラフである。
用語 2.3 (有向辺) 制御フローグラフ等において、ブロック X からブロック Y に有向辺が
あるとき、X → Y と表記する。以後、有向辺のことを単に辺 (edge) と呼ぶことがある。
用語 2.4 (パス) ノードの列 X0 , X1 , ..., Xi (i ≥ 0) に対して、e1 : X0 → X1 , e2 : X1 →
X2 , ..., ei : Xi−1 → Xi (i ≥ 0) なる辺が存在すると仮定する。このとき X0 から Xi にパス
(path) が存在するという。
用語 2.5 (先行ブロック) X → Y であるとき、X は Y の先行ブロック (predecessor block)
と呼び、X の先行ブロックの集合を pred(X) とあらわす。図 2.5 のブロック 7 の場合、先
行ブロックはブロック 5、ブロック 6、ブロック 9 であり、pred(7) = {5, 6, 9} である。
用語 2.6 (後続ブロック) X → Y であるとき、Y は X の後続ブロック (successor block)
と呼び、X の後続ブロックの集合を succ(X) とあらわす。図 2.5 のブロック 7 の場合、後
続ブロックはブロック 8、ブロック 9 であり、succ(7) = {8, 9} である。
用語 2.7 (結合ブロック) 先行ブロックが複数あるブロックを結合ブロック (join block)
と呼ぶ。図 2.5 の結合ブロックはブロック 1、ブロック 5、ブロック 7、ブロック 9 である。
用語 2.8 (分岐ブロック) 後続ブロックが複数あるブロックを分岐ブロック (branch block)
と呼ぶ。図 2.5 の分岐ブロックはブロック 1、ブロック 2、ブロック 7、ブロック 9、ブロッ
ク 10 である。
用語 2.9 (入口ブロック) 先行ブロックがないブロックを入口ブロック (entry block) と
呼ぶ。図 2.5 では、入り口ブロックはブロック 0 である。
用語 2.10 (出口ブロック) 後続ブロックがないブロックを出口ブロック (exit block) と呼
ぶ。図 2.5 では、出口ブロックはブロック 11 である。処理の都合上、プログラム本体の前
に入口ブロック、後に出口ブロックを設けることが多い。
用語 2.11 (先行パス) プログラムの入口からブロック X に至る全てのパスを、X の先行
パス (predecessor path) と呼ぶ。
用語 2.12 (後続パス) ブロック X からプログラムの出口に至る全てのパスを、X の後続
パス (successor path) と呼ぶ。
用語 2.13 (後退辺) Y が X の後続パスであるとき、もし Y → X の辺があれば、これを後
退辺 (back edge) と呼ぶ。図 2.5 のブロック 9 → ブロック 7 は後退辺である。
13
2.3
静的単一代入形式
静的単一代入形式、または SSA 形式 (static single assignment form) とは、プログ
ラムの表現方法の一つで、そのプログラム上の全ての変数の使用に対して、その使用に対
応する定義が 1 箇所しかないように表現したものである。これは、変数の値の定義と使用
の関係を明確に表現する形式であり、従来のデータの流れの解析とは違う方法が、この形
式を使う事によって可能になる。この例を図 2.6 に示す。
図 2.6(a) では、a の使用に対応する定義は 2ヶ所にある。それを 1ヵ所にするために、結
合ブロックに (b) で示すような定義があると考える。その右辺にある関数は phi 関数と呼
ばれるもので、左のブロックからきたときは a1 の値、右からきたときは a2 の値をとる関
数である。SSA 形式について詳しくは文献 [1, 11] 等を参照されたい。
a=1
a=2
a1=1
a2=2
a3=phi(a1,a2)
=a3
=a
(b)
(a)
図 2.6: SSA 形式の例
2.4
2.4.1
プログラムの最適化
無用命令除去
定義した後使われない変数や，そこへ制御が移る事のないコードは，無用命令として除
去できる。
図 2.7: 無用命令除去
14
2.4.2
コピー伝播（定数伝播も含む）
x：= y というコピー文を実行すると、x は y と同じ値を持つようになるため、後に現れ
る x の使用は y の使用に置き換えられる。この文は後で無用命令除去できる可能性が高い。
伝播先の命令文が y と定数の演算の場合，y も定数だと，定数の畳み込みもできる。
図 2.8: コピー伝播
2.4.3
ループ不変式の移動
ループの繰り返しによらず一定な結果を与える計算をループの外に追い出す事によって，
計算の回数が減る．
図 2.9: ループ不変式の移動
2.4.4
共通部分式除去
同じ値を持つ部分式が 2 か所以上に現れた場合，それらを共通部分式という．計算した
結果を利用する事によって，演算の回数を減らす事ができる．
図 2.10: 共通部分式除去
15
2.4.5
その他の最適化
その他の最適化としては、条件分岐を考慮した定数畳み込みと定数伝播、ループの帰納
変数に関わる演算の強さの軽減と判定の置き換え等があるが、詳しくは COINS の最適化
仕様書 [5]、教科書 [14] 等を見られたい。
16
第 3 章既存の COINS 可視化システム
本章では既存の COINS 可視化システムについての説明を行う。
3.1
CoVis
CoVis とは、ソースプログラム、HIR、HIR の制御フローグラフ、LIR、LIR の制御フ
ローグラフなどの対応をグラフィカルに表示する可視化ツールである。
図 3.1 は、ソースプログラム matmult.c から HIR が生成された時の様子を CoVis で表示
したものである。図の左上は制御フローグラフ、左下は制御フローグラフに関する情報、右
上は HIR、右下はソースプログラムである。それぞれ赤や青の色のついた部分が対応して
いる。この図の中央上のボタンが示すように、（１）HIR が生成された時、（２）HIR での
最適化後、
（３）LIR が生成された時、
（４）LIR での最適化後、の４つの時点でこのような
表示をすることが出来る。また、制御フローグラフの基本ブロックをクリックすると、右
上のその基本ブロックに対応した部分が赤色に表示された部分、右下のその基本ブロック
に対応した部分が青色に表示されるようになっている。1
3.2
trace2html
trace2html は、コンパイラでもっとも複雑な過程の一つであるコード生成過程のデバッ
グを助けるための可視化ツールであり、それはバッグエンドの随所での変換過程を各種リ
ンクつきの html ファイルとして出力することによって実現されている。
図 3.2 は、コード生成過程のトレース表示をしたものである。左の欄にはトレース情報
をとった時点の名前が入っている。右上にはソースプログラム、右下にはある時点でのト
レース情報が表示されている。右下の下半分あたりに LIR とマシン命令記述とのパターン
マッチングの様子が示されている。右下の上半分あたりには、そのパターンマッチングの
前の時点でのある基本ブロックの中の LIR の列が表示されている。
そこにある [<<] をクリックすると、その基本ブロックが一つ前のフェーズの時点でどう
なっていたかを見ることが出来る。また、[>>] をクリックすると、その基本ブロックが一
つ後のフェーズの時点でどうなるかを見ることが出来る。
この trace2html は Perl 言語で実装されている。
1
以後 clickable な制御フローグラフと呼ぶ
17
図 3.1: CoVis
図 3.2: trace2html
18
第 4 章可視化プログラムの設計と実装
本章では、ユーザが実装してほしい可視化プログラムの内容と、実際に実装したプログ
ラムについて説明する。
4.1
ユーザの要望
最適化器開発者は、まず実装した最適化器が正しく動いているかどうか確認する必要が
ある。そこで、最適化器開発者が実装して欲しい機能としては、trace2html のような各最
適化ごとの LIR の表示と LIR を C 言語風に表現した lir2c の表示、さらに CoVis のように
clickable な制御フローグラフを表示するものが挙げられる。
つまり、各最適化ごとの
• ソースプログラムの表示
• LIR の表示
• lir2c の表示
• 制御フローグラフの表示
• clickable な制御フローグラフの実装
• それぞれの表示の同期
である。
4.2
html と javascript を利用した可視化プログラムの設計
本研究における実装は、各最適化ごとの LIR の表示がすでに可能であった trace2html を
参考にして行った。ただし、trace2html は Perl 言語 [12] で書かれていたため、これを Java
言語に書き直した。また、ソースプログラム・LIR・lir2c・制御フローグラフの同期をとる
ために html 言語で利用できる javascript を利用して実装した。
次にサンプルプログラムを quicksort.c とした本手法の例を示す。
19
図 4.1 は、本手法で作成したものの例である。左の欄 (以後 index 欄と呼ぶ) には LIR を
とった時点の名前と、関数名が入っている。関数名が入っていない場合はすべての関数の
LIR が表示される。中央上段 (以後ソース欄と呼ぶ) にはソースプログラム、中央中段 (以
後 LIR 欄と呼ぶ) にはある時点での LIR が表示されている。中央下段 (以後 lir2c 欄と呼ぶ)
は中央中段の LIR を lir2c で C 言語風に変換した情報が表示されている。右の欄 (以後制御
フローグラフ欄と呼ぶ) には各 LIR をとった時点の制御フローグラフが表示される。ただ
し、この場合の制御フローグラフは簡単のためブロック名のみとなっている。
ソース欄にある [>>] をクリックすると、そのソースコードが最初に LIR に変換された時
点を見ることが出来る。
LIR 欄にある [<<] をクリックすると、その基本ブロックが一つ前のフェーズでどうなっ
ていたかを見ることが出来る。また、[>>] をクリックすると、その基本ブロックが一つ後の
フェーズでどうなるかを見ることが出来る。この場合、表示が変化するのは LIR 欄と lir2c
欄、制御フローグラフ欄で、ソース欄は変わらない。[display] をクリックすると、その時
点での lir2c、制御フローグラフを見ることができる。つまり、lir2c 欄と制御フローグラフ
欄が更新される。
[source] をクリックするとその基本ブロックが含まれるソースコードを見ることができ
る。この場合、更新されるのはソース欄、lir2c 欄、制御フローグラフ欄の 3 つである。
lir2c 欄にある [display]、[source] をクリックした場合も LIR 欄にある同名のリンクをク
リックしたときと同様の動作をする。
制御フローグラフ欄にある制御フローグラフをクリックすると、その制御フローグラフ
が指す箇所を見ることができる。つまり、LIR 欄と lir2c 欄が更新される。
20
図 4.1: 本手法
21
4.3
実装
本手法では COINS コンパイラの出力する LIR を元にして html ファイルを生成する。そ
こで、本節ではプログラムの簡単な動きを説明する。
図 4.2: 実装の概要
4.3.1
COINS の出力する LIR の構成
COINS コンパイラの出力する LIR の構成は基本的に以下のようになる。
Before/After 最適化器名:
Function "関数名":
Local Symbol table:
...
Control Flow Graph:
#1 Basic Block(.L1): DFN=(1,1), <-() ->(#2,#3)
...
(JUMP (LABEL I32 ".L5" $2))
...
End Function
これは全て正規表現で解析可能となっている。
22
4.3.2
制御フローグラフの描画
本手法では制御フローグラフを作るために Graphviz というツールをプログラム内で呼
び出している。これは DOT 言語という言語で書かれたグラフ表現を GIF などのファイル
フォーマットに変換するプログラムである。本手法では、同期をとるためトレース情報を
読みつつ DOT プログラムを書いている。
具体的には、まず “#数字 Basic Block...”を正規表現で読み取る。
Java 言語は正規表現を扱うことが可能であり、また LIR の構成から分かるように “Basic
Block”は必ず “#数字 Basic Block(.L ブロック番号)...”の表現でしか扱われないため、こ
れを読み取る。
“Basic Block”を読み取ったら、直後の括弧内にある “.L ブロック番号”を読み取り、こ
れをファイルに書き出す。さらにそのブロック情報の最後にある JUMP または JUMPC 命令を
正規表現で読み取り、同様にしてジャンプ先のブロック情報を書き出すようにしている。
JUMP 命令は、LIR の構成から分かるように “(JUMP ... “.L ブロック番号” ... )”となって
おり、また JUMPC 命令も “(JUMPC ... “.L ブロック番号” ... “.L ブロック番号” ... )”となっ
ているため、ジャンプ先のブロック情報を正規表現で読み取ることは容易である。
例を示すと、
#1 Basic Block (.L1): DFN=(1,1), <-() ->(#2,#3)
...
(JUMP (LABEL I32 ".L3" $3))
は次のように書き出される。
L1 -> L3
これを各最適化器ごとに DOT ファイルに書き出し、Graphviz によって制御フローグラフ
を描画している。
4.3.3
本手法での画面同期方法
本手法では各最適化前後の同期を取るために chapter と名づけた変数を用意し、LIR 中
の “Before”または “After”を正規表現で読むたびこれを 1 ずつ増やして html ファイルに
埋め込んだ。トレース情報を読み始める段階では chapter=1 であり、各 “Before”または
“After”を正規表現で読み取るごとに chapter の値が 1 ずつ増加する。
また、本手法ではトレース情報を読みながら lir2c 欄、制御フローグラフを作成している
ため、これらの表示にも chapter を利用している。
さらに、基本ブロックにおけるフェーズの前後の同期を取るために、その基本ブロック
が現れた回数を保存しておく必要がある。html 内の LIR 欄における構成は、“#L.L ブロッ
ク番号-現れた回数”であり、lir2c 欄では “#L.L ブロック番号-現れた回数”となる。
これらをそれぞれ html ファイルに埋め込み、javascript によって同期させることで画面
同期を実装した。
例えば、chapter=12 の時に “After CommonSubexpressionElimination”を読んだ場合
LIR 欄の html ファイルは
23
<a name="link12">After CommonSubexpressionElimination</a>
とされる。lir2c 欄では
<a name="chapter12">After CommonSubexpressionElimination</a>
制御フローグラフ欄では
<a name="graph12"></a>...<img src="...gif">...
とされる。
index 欄には該当の名前に同時にジャンプできるように javascript を用いて
リンク “After CommonSubexpressionElimination”が追加される。
index 欄で用いられる javascript の使用例を示すと、
<a href="javascript:pageChangeWithGraph(
’trace_quicksort-body.html#link12’,
’trace_quicksort-likec.html#chapter12’,
’trace_quicksort-graph.html#graph12’);">
Before CommonSubexpressionElimination
(Common subexpression elimination on SSA form.):
</a>
となる。
LIR 欄での javascript 使用例を示すと、
<a href="javascript:pageChangeWithGraph
(’#L.L16-10’,’trace_quicksort-likec.html#LC.L16-10’,
’trace_quicksort-graph.html#graph12’);">
[<<]
</a>
となり、lir2c 欄では
<a href="javascript:showLIRandGraph
(’trace_quicksort-body.html#L.L1-10’,
’trace_quicksort-graph.html#graph12’);">
[display]
</a>
制御フローグラフ欄では、
<a href="javascript:pageChangeWithGraph
(’trace_quicksort-body.html#link12’,
’trace_quicksort-likec.html#chapter12’,
’trace_quicksort-graph.html#graph12’);">
<img src=".\graph_img/After_CommonSubexpressionElimination___sgetc_r_1.gif">
</a>
となる。
24
第 5 章プログラム最適化過程の可視化例
ここでは実際のプログラムの最適化過程の可視化例を示す。
5.1
例 1.Appel の例
まず Appel の本 [1] の Fig.19.4 にある、条件分岐を考慮した定数伝播の例のプログラム
を示す。
#include <stdio.h>
int main ()
{
int i;
int j;
int k;
i = 1;
j = 1;
k = 0;
while (k < 100) {
if (j < 20) {
j = i;
k = k + 1;
} else {
j = k;
k = k + 2;
}
}
printf("%d\n",j);
}
25
このプログラムは SSA 変換後に条件分岐を考慮した定数畳み込みと定数伝播 (Constant
Propagation with Conditional Branch) によって次のように最適化されることが知られて
いる。
void main(void)
{
while (
k2 = phi(0,k4); // 条件判定前に入るφ関数
k2 < 100) {
k4 = k2 + 1;
}
printf("%d\n",1);
}
実際、本手法でその様子を見てみると図 5.1 から図 5.2 のように変換される。図 5.2 では
明らかに制御フローグラフにおいて基本ブロック数が減っているし、LIR 欄、lir2c 欄を見
れば上に示したプログラムの通りになっていることが分かる。
26
図 5.1: 条件付定数伝播前の Appel の例
27
図 5.2: 条件付定数伝播後の Appel の例
28
5.2
例 2. バグ発見の例
COINS のループ不変式の移動におけるバグも本手法で見ることができる。まず問題のあ
るプログラムを示す。
#include <stdio.h>
void f(int x, int y);
main() {
f(1, 0);
}
void f(int x, int y) {
int i, t;
for (i = 0; i < 10; i++) {
if (y <= i && y == 0) return;
t = x / y;
}
printf("x / y = %d\n", t);
return;
}
このプログラムを divex/esplt/hli1 の順に SSA 最適化をかけるとエラーの発生するプログラ
ムを出力してしまう。具体的には中間言語レベルで次に対応するプログラムが生成される。
1
3 アドレス方式に変換/危険辺の分割/ループ不変式の移動
29
#include <stdio.h>
void f(int x, int y);
main() {
f(1, 0);
}
void f(int x, int y) {
int i_1 = 0, t = 0;
if (i_1 < 10) {
t = x / y;
while (i_2 = phi(i_3, i_1), // 条件判定前に入るφ関数
i_2 < 10 ) {
if (y <= i_2)
if (y == 0) return;
i_3 = i_2 + 1;
}
}
printf("x / y = %d\n", t);
return;
}
このプログラムは、本来 y が 0 でないことを確認してから y での割り算をしなければな
らないが、13 行目で (t = x / y) してはいけないループ不変式の巻上げを行っているため、
y が 0 であるにもかかわらず割り算を行ってしまっている。したがって、このプログラムは
正しく動かない。
実際に本手法で見てみると、次の図 5.3、5.4 において、少々分かりにくいが LIR 欄の基
本ブロック L35 で
(SET I32 (REG I32 "_hliI32_0") (DIVS I32 (REG I32 "x.9%_1") (REG I32 "y.10%_1")))
となり、lir2c 欄では
_hliI32_0 = x.9%_1/y.10%_1;
となっていることが分かる。
最適化器の記述者は、これを見ることで最適化が誤っていることの発見がしやすくなる。
30
図 5.3: ループ不変式の移動前
31
図 5.4: ループ不変式の移動後
32
第 6 章議論
6.1
評価
本手法では、既存のツール trace2html を改良し、
• COINS コンパイラに SSA 最適化の LIR の出力をもたせる
• 各最適化器ごとにソースファイル・LIR・lir2c・制御フローグラフを表示する
• ソースファイル・LIR・lir2c・制御フローグラフの同期をとらせる
の 3 つを行えるようにした。
本手法の結果、最適化器の正しさの確認、バグの発見を容易に行えるなど従来より強力
な最適化器開発のためのツールが作成できた。
しかし、制御フローグラフを簡略化したため、最適化手法によっては見づらい環境になっ
てしまっている。また、制御フローグラフの基本ブロックをクリックすることでデータフ
ロー情報が表示できる機能を実装することができなかった。
本手法の評価方法としては、あらかじめバグのある最適化器を用意しておき、何人かの
最適化器記述者にこのツールあり・なしの状況でバグ発見までの時間を測る、という方法
が挙げられる。
今後の課題としては、CoVis で実装されているようなクリックによる制御フローグラフ
の基本ブロックの中身の表示、またはポップアップなどによる制御フローグラフの基本ブ
ロックの中身の表示を実装し、さらに強力なツールの開発を目指していきたい。
6.2
6.2.1
関連研究
COINS における既存のツール
COINS における既存のツールに CoVis がある。このツールはソースプログラム、HIR、
HIR の制御フローグラフ、LIR、LIR の制御フローグラフなどの対応をグラフィカルに表示
する可視化ツールである。CoVis における利点としては、制御フローグラフで基本ブロッ
クをクリックすると詳しいデータフロー情報が表示できることである。欠点は表示のタイ
ミングが限定された幾つかの時点だけということである。
もう一つのツール、trace2html は、制御フローグラフが表示されないという欠点を持っ
ているが、表示のタイミングが全ての最適化器前後で可能であることは有用である。
33
6.2.2
コンパイラ最適化過程の可視化の研究
本研究以外のコンパイラ最適化過程の可視化の研究には、可視化とデバッガについての
研究 Graphical Visualization Of Compiler Optimizations [3] がある。これは、VPO コン
パイラ [18] において、新しいマシンへの対応のプロセスを容易にし、またそれを補助する
ことができるツールである。
6.2.3
XML を用いた最適化過程の可視化の研究
また、XML を用いたコンパイラ最適化過程の可視化の研究に、Performance Visualizations using XML Representations [17] がある。これは SUIF コンパイラ [16] や IMPACT コ
ンパイラ [8] などを対象としており、中間表現と共に XML ファイルを作成し、最適化過程
を可視化することができる。
6.2.4
その他コンパイラ最適化過程の可視化の研究
その他、コンパイラ最適化過程の可視化は開発現場で使われていると思われるが、ほと
んど公開されていない。
34
第 7 章まとめ
本研究ではコンパイラ最適化過程の可視化ツールの作成を行った。機能として、
• COINS コンパイラに SSA 最適化の LIR を含むトレース情報の出力の機能をもたせる
• 各最適化器ごとにソースファイル・LIR・lir2c・制御フローグラフを表示する
• ソースファイル・LIR・lir2c・制御フローグラフの同期をとらせる
の 3 つの特徴がある。
本研究により、さらに COINS における最適化器の正しさの確認がしやすくなり、新たな
最適化器作成を補助することができるようになった。
今後の課題としては、制御フローグラフの中身の表示を実装していきたい。しかし、html
ベースではこの機能の追加は難しいため、Java 言語などのプログラム言語を使って新たに
開発する必要がある。
35
謝辞
本研究を進めるにあたり多大なる御指導ご鞭撻を頂いた、東京工業大学数理・計算科学
専攻教授の佐々政孝先生に深く感謝の意を表します。
また、佐々研究室の皆様にはさまざまな面で助力を頂きました。あらためまして、ここ
に深くお礼申し上げます。
36
参考文献
[1] Andrew W. Appel. Modern compiler implementation in Java. Cambridge University
Press, 2nd edition, 2002.
[2] AT&T. Graphviz homepage. http://www.graphviz.org/.
[3] M. Boyd and D. Whalley. Graphical visualization of compiler optimization, 1995.
[4] COINS-Project. Coins homepage. http://www.coins-project.org/.
[5] 東京工業大学大学院情報理工学研究科佐々研究室. 静的単一代入形式最適化システ
ム外部仕様書. http://www.is.titech.ac.jp/∼sassa/coins-www-ssa/japanese/
ssa-external-japanese.pdf.
[6] Robert Fitzgerald, Todd B. Knoblock, Erik Ruf, Bjarne Steensgaard, and David
Tarditi. Marmot: an optimizing compiler for Java. Software - Practice and Experience, Vol. 30, No. 3, pp. 199–232, 2000.
[7] GNU-Project. Gcc homepage. http://gcc.gnu.org/.
[8] IMPACT Research Group. http://www.crhc.uiuc.edu/Impact/.
[9] IBM. Jikes research virtual machine. http://jikesrvm.sourceforge.net/.
[10] 森公一郎. COINS 新 LIR 内部構造, 2003. http://www.coins-project.org/050303/
base/BackEnd/NewLir.html.
[11] 中田育男. コンパイラの構成と最適化. 朝倉書店, 1999.
[12] Larry Wall, Tom Cbristiansen, and Jon Orwant. プログラミング Perl. 第 3 版.
[13] COINS Project. COINS プロジェクト LIR 仕様書, 2002. http://www.coins-project.
org/spec/lir.pdf.
[14] 佐々政孝. プログラミング言語処理系. 岩波書店, 1989.
[15] Scale Compiler Group. Scale homepage. http://www-ali.cs.umass.edu/Scale/.
[16] The SUIF Group. The stanford suif compiler group. http://suif.stanford.edu/.
[17] Yijun Yu, Kristof Beyls, and Erik H. D’Hollander. Performance visualizations using
XML representations. Proceedings of the Eighth International Conference on Information Visualisation( ’04), 2004.
37
[18] Zephyr. Zephyr very portable optimizer. http://www.cs.virginia.edu/zephyr/
vpo/.
38

Download Report