実験結果、考察により、本手法は従来手法に比べて常に速くなるわけではなく、
遅くなる場合もあることが分かる。
本手法は １ つのブロックに干渉情報が集まっているプログラムには有効ではな い。1つのブロックに干渉情報が集まっているプログラムでは、本手法で作成され るレジスタ干渉グラフは、従来手法で作られるレジスタ干渉グラフとほぼ同様の サイズになってしまい、関数をブロックに分割しているメリットがなくなってしま う。具体的には、1つのループで関数全体のほとんどの作業をしているプログラム や、ループ内でほとんど仮想レジスタを使用しないプログラムなどである。また、
関数を複数のブロックに分割する作業やスルーしている仮想レジスタを除去する 作業を行っているため、そのようなプログラムに対して本手法を適用すると、従
来手法よりコンパイル速度が低下してしまう。また、スピルが発生しないプログ ラムにおいてもコンパイル速度は低下してしまう。
本手法は、複数のブロックに干渉情報が分散されているプログラムで、スピル が発生するプログラムに対して有効である。
6 おわりに
以上の結果をもとに、まとめと今後の課題について述べる。
6.1 まとめ
グラフ彩色法を用いたレジスタ割り付けは、プログラムの関数ごとにレジスタ 干渉グラフを作成している。そのため、スピルが発生した際に関数全体に関する レジスタ干渉グラフを作成し直す必要がある。スピルされる仮想レジスタがその 関数の一部でしか生存していなくても関数全体のレジスタ干渉グラフを作成し直 している。よって、スピルが発生した際に作成し直すレジスタ干渉グラフのサイズ が大きくなっており、これが高速なコンパイルへの妨げになると考えた。よって、
本論文では、ループを基準としてプログラムの関数を複数のブロックに分割し、そ のブロックごとにレジスタ干渉グラフを作成した。こうすることで、スピルが発生 した際に、スピルが発生したブロックのレジスタ干渉グラフだけを作成し直すこ とができ、他のブロックのレジスタ干渉グラフは作成し直す必要がなくなる。ま た、ループブロックを作成することにより、ループブロックをスルーしている仮 想レジスタが存在するようになった。このスルーしている仮想レジスタはレジス タに割り付けている必要はないので、スルーしている仮想レジスタをレジスタ干 渉グラフから除去した。これにより、レジスタ干渉グラフのサイズを小さくなり、
またスピルによるレジスタ干渉グラフの作成し直す回数も減少させることができ た。よって、作成し直すレジスタ干渉グラフのサイズを小さくし、レジスタ干渉 グラフの作成時間を短くすることができ、コンパイルを高速化することができる。
しかし、本手法はどのような状況においても有効なわけではなく、本手法を適 用することによりコンパイル速度が低下することもある。本手法が有効なプログ ラムは、仮想レジスタの干渉情報が複数のブロックに分散しているようなプログ ラムである。逆に 1 つのブロックに干渉情報が集中しているようなプログラムで は、本手法を適用するとコンパイル速度が低下してしまう。
6.2 将来課題
本手法を適用することで、複数のブロックに干渉情報が分散しているプログラ ムのコンパイル速度は向上したが、1つのブロックに干渉情報が集中しているプロ グラムではコンパイル速度は低下してしまった。よって、今後はループブロックよ
りも効果的な分割方法について検討し、より高速なコンパイルが可能なコンパイ ラについて検討していく予定である。
謝辞
本研究を進めるにあたり、数々のご指導を頂いた深澤良彰教授、本当に多くの御 指導・御助言を賜った、日本IBM（株）東京基礎研究所の小松秀昭氏、古関聰氏 に深く感謝致します。
また、研究に際して非常に多くのアドバイスをいただいた最適化班の片岡さん、
中林君、本当にありがとうございました。
最後になりましたが、大学4年間、修士2年間まで何不自由なく勉学をさせてい ただいた両親に深く感謝いたします。本当にありがとうございました。
参考文献
[1] andrew w.appel：modern compiler implementation in java
[2] G.J.Chaitin,M.A.Auslander,A.K.Chandra.J.Cocke,M.E.Hopkins,and P.W..Markstein:”Register allocation via coloring”,Language,6:47-57,1981 [3] 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
[4] R.Sethi. Complete register allocation problems. SIAM Journal on Computing,4(3):226-248,1975
[5] D.Callahan and B.Koblenz:”Register allocation via hierarchical graph color-ing”,In Proceedings of the ACM SIGPLAN 1992 Conference on Programming Language Design and Implementation,pages 192-203,1991
[6] T.A.Proebsting and C.N.Fischer:Probabilistic register allocation”,In Proceed-ings of the ACM SIGPLAN 1992 Conference on Programming Language Design and Implementation,pages 300-310,1992
[7] A.Koseki,H.Komatsu,and T.Nakatani:”Preference-directed graph coloring”,In Proceedings of the ACM SIGPLAN 1992 Conference on Programming Lan-guage Design andImplimentation,pages 33-44,2002
[8] G.J.Chaitin,M.A.Auslander,A.K.Chandra,J.Clcke,M.E.Hopkins,and
P.W.Markstein.Register allocation via coloring.Computer Languages,6:47-57,1981
[9] P.Briggs,K.D.Cooper,K.Kennedy,and L.Torczon.Coloring heutistics for regis-ter allocation.In Proceedings Language Design and Implementation,pages 275-284,1989.
[10] 中田育男:”コンパイラの構成と最適化”,朝倉書店,1999 [11] http://www.coins-project.org/