修 修 修
修 士 士 士 士 論 論 論 論 文 文 文 文 概 概 概 概 要 要 要 要 書 書 書 書
CD 2008年 2月提出 学籍番号3606U107-3 専攻名（専門
分野）
情 報 ネ ッ ト ワー ク 専
攻 指 導
研究指導名 ソフトウエア開発工学
氏 名 山崎 敬史
教 員
深澤 良彰 印
研 究
題 目 レジスタ干渉グラフの分割によるコンパイルの高速化に関する研究
1 はじめに
レジスタ干渉グラフを用いたレジスタ割り付け は、プログラムを関数ごとにレジスタ干渉グラフ を作成している。レジスタ割り付けを行う時、レ ジスタ数が不足するとレジスタ干渉グラフを作成 し直す必要があるが、従来手法では、関数全体に 関するレジスタ干渉グラフを作成し直す必要があ る。そこで本手法では、関数を複数のブロックに 分割し、そのブロックごとにレジスタ干渉グラフ を作成する。こうすることで、作成し直すレジス タ干渉グラフのサイズを縮小し、レジスタ割り付 けにかかる時間を短縮し、コンパイル速度を上げ ることができる。
2 従来手法
2-1グラフ彩色法
レジスタ割り付けにおいて、まず生存区間解析 という操作を行う。生存区間解析とは、コンパイ ラが生成する一時的な変数(仮想レジスタ)の生存 区間を調べることである。仮想レジスタ同士の生 存区間が重なっている(干渉している)と、その仮想 レジスタは異なるレジスタに割り付けられ、生存 区間が重なっていなければ、同じレジスタに割り 付けることができる[1]。レジスタ干渉グラフを用 いたレジスタ割り付けでは、生存区間解析の情報 を元に仮想レジスタ同士の干渉情報をグラフにす る。そして、このレジスタ干渉グラフを干渉して いる仮想レジスタ同士は異なる色で彩色してい く。こうして実レジスタ数色以下でレジスタ干渉 グラフを彩色するという問題を解き、色を実レジ スタに対応付けすることで仮想レジスタを実レジ スタに割り付けることができる。彩色方法として は、レジスタ干渉グラフをGとし、K(レジスタ数) 個未満の干渉を持つ仮想レジスタをM とする。G からMを除去して得られるグラフがK-1色で彩色 できればGはK色で彩色可能である。よって、G からK個未満の干渉を持つ仮想レジスタを除去し ていく。すべての仮想レジスタが除去できれば、
仮想レジスタはすべてレジスタに割り付けること ができる。しかし、レジスタ数不足により、レジ
スタ数色以下でレジスタ干渉グラフを彩色できな いことがある。そういった時、仮想レジスタをメ モリに退避させる作業(スピル)が発生する。スピル が発生すると、仮想レジスタの生存区間情報が変 わるので、スピルのたびに仮想レジスタの生存区 間を調べ直し、レジスタ干渉グラフを作成し直す 必要がある[2]。
2-2 グラフ彩色法の問題点
従来の手法では、関数ごとにレジスタ干渉グラ フを作成しているので、スピルが発生した際に作 成し直すレジスタ干渉グラフのサイズが大きくな っている。スピルされる仮想レジスタの生存区間 が非常に短くても関数全体のレジスタ干渉グラフ を作成し直さなければならない。何度もスピルが 発生すると、関数全体のレジスタ干渉グラフを作 成し直すことはコンパイル速度の低下を引き起こ してしまう。
3 本手法の特徴
本手法では、プログラム中の関数をループ単位 で複数のブロックに分割する。ループには多重ル ープも存在するが、最も外側のループのみに着目 し、複数のループブロックを作成する。そして、
ループブロックに属さない部分を全てまとめて一 つのループ外ブロックとする。本手法では、この ブロックごとにレジスタ干渉グラフを作成する。
これにより、スピルが発生した際に作り直すレジ スタ干渉グラフのサイズが小さくなり、レジスタ 割り付けにかかる時間が短くなりコンパイル速度 を向上させることができる。
ループブロックを作成した際に、ループブロッ クの始めから終わりまでブロックを貫いて生存し ているにも関わらず、ループブロックでは一度も 参照されない仮想レジスタ(以後、スルーしている 仮想レジスタと呼ぶ)が存在することがある。スル ーしている仮想レジスタは、そのループブロック においてレジスタに割り付けられている必要はな く、スルーしている仮想レジスタがレジスタに割 り付けられることで参照される仮想レジスタがス ピルされる可能性が出てくる。よってスルーして いる仮想レジスタはレジスタ干渉グラフから除去
して、レジスタには割り付けないようにする。こ うすることでループブロックの仮想レジスタ数が 減少し、レジスタ干渉グラフのサイズを小さくす ることができ、よりコンパイル速度を向上させる ことができる。
4 実験結果
COINS コンパイラ(Ver.1.4.2.2)を改良すること
で、本手法のシステムを構築した。COINSコンパ イラと本手法を実装したコンパイラでバブルソー ト、行列の積、順列生成、スタンフォードのベン チマークのプログラムを20回ずつコンパイルし、
そのコンパイル時間の平均時間を求めた。以下に その結果を示す。
0 50 100 150 200 250 300
バブルソート 行列の積 順列生成 スタンフォード
(ms) COINS
本手法
COINS 本手法
バブルソート 124.9ms 117.4ms 行列の積 151ms 132.25ms 配列の入れ替え 121.05ms 141.25ms
スタンフォード 280.95ms 237.5ms バブルソートと行列の積とスタンフォードのベ ンチマークのプログラムにおいては、従来手法よ りも本手法の方がコンパイル速度が速くなった。
しかし、順列生成プログラムにおいては、本手法 の方が遅くなってしまった。
5 考察
順列生成のプログラムでは、本手法の方が遅く なった原因について考察する。順列生成のプログ ラムのブロック情報を調べたところ、ループブロ ックが1つとループ外ブロックが存在した。更に 各ブロックのレジスタ干渉グラフについて調べた ところ、干渉情報のほとんどがループブロックに 集中していることが分かった。ループブロックの 干渉情報は全体の干渉情報の約 95%もあり、ルー プ外ブロックの干渉情報は全体の約5%であった。
よって順列生成のプログラムにおいては、関数を ブロックに分割したにも関わらず、レジスタ干渉 グラフのサイズは、ループブロックに分割しない
ものとほとんど同じになってしまった。本手法の メリットは、関数を複数のブロックに分割するこ とで、スピルが発生した際に作成し直すレジスタ 干渉グラフのサイズを小さくすることでコンパイ ル速度を向上することである。よって、ループブ ロックのレジスタ干渉グラフのサイズが全体の約 95%もあるプログラムにおいては、本手法のメリ ットは発揮されない。また、本手法は従来手法に 加え、関数を複数のブロックに分割し、また、ス ルーしている仮想レジスタをレジスタ干渉グラフ から除去する、等の処理を行っている。そのため、
1 つのブロックに干渉情報が集中しているプログ ラムにおいては、従来手法よりもコンパイル速度 が低下してしまうことが分かる。
6 まとめ
本論文では、ループを基準としてプログラムの 関数を複数のブロックに分割し、そのブロックご とにレジスタ干渉グラフを作成した。こうするこ とで、スピルが発生した際に、スピルが発生した ブロックのレジスタ干渉グラフだけを作成し直す ことができ、他のブロックのレジスタ干渉グラフ は作成し直す必要がなくなる。また、ループブロ ックを作成することにより、ループブロックをス ルーしている仮想レジスタが存在するようになっ た。このスルーしている仮想レジスタはレジスタ に割り付けている必要はないので、スルーしてい る仮想レジスタをレジスタ干渉グラフから除去し た。これにより、レジスタ干渉グラフのサイズを 小さくなり、またスピルによるレジスタ干渉グラ フの作成し直す回数も減少させることができた。
よって、作成し直すレジスタ干渉グラフのサイズ を小さくし、レジスタ干渉グラフの作成時間を短 くすることができ、コンパイルを高速化すること ができる。
しかし、本手法はどのような状況においても有 効なわけではなく、本手法を適用することにより コンパイル速度が低下することもある。1 つのブ ロックに干渉情報が集中しているようなプログラ ムでは、本手法を適用するとコンパイル速度が低 下してしまう。本手法は、仮想レジスタの干渉情 報が複数のブロックに分散しているようなプログ ラムに対して適用すると効果的である。
参考文献
[1]A.W.Appel "Modern compiler implementation in java"CAMBRIDGE UNIVERSITY PRESS, 1998
[2] G.J.Chaitin "Register allocation and spilling via graph coloring"In Proceedings of the ACM SIGPLAN 1982 Symposium on Compiler Construction, pages 201-207, 1982
