非再試行型レジスタ割付けとその評価

情報処理学会 Web Site 参考文献8件

書誌事項

タイトル別名
  • ヒサイシコウガタ レジスタ ワリツケ ト ソノ ヒョウカ
  • Non-retrial Register Allocation and Its Evaluation

この論文をさがす

抄録

グラフ彩色法は，レジスタの多いアーキテクチャにおいては効果的である．なぜなら，スピルコードが出なかった場合，そのレジスタ割付けの結果は最適解だからである．しかし，このアルゴリズムには，レジスタの少ないアーキテクチャにおいて，特に長い処理時間がかかるという問題がある．なぜなら，このアルゴリズムは，干渉グラフが彩色可能になるまで，変数の生存区間分割による干渉グラフの再構築という全過程を繰り返すからである．そこで，我々は，エッジを重み付き双方向エッジにした干渉グラフを用いて，レジスタの少ないアーキテクチャにおける静的コンパイラ向けの，新しい高速なレジスタ割付け手法を提案する．我々の手法は，物理レジスタ数をK とすれば，仮想レジスタをK 色以上の色で塗り分ける．そして，グラフ変形のみでスピルコードを挿入することによりK 色まで色数を減らしている．このようにして，我々の手法は，高速なレジスタ割付けと，生成されたコード内のスピルコード削減を可能にしている．我々の手法を組み込んだコンパイラは，GNU Cコンパイラバージョン3.4.4（gcc-3.4.4）よりも約8%高速であった．また，スタンフォードベンチマークにおいて，我々のコンパイラが生成したコードは，gcc-3.4.4の生成したコードより，約5%高速であった．

Graph coloring is effective for architectures with a large number of registers, because the results of register allocation are optimal if there is no spill code. However, this algorithm has a problem that it particularly takes long time in register allocation for architectures with a small number of registers, because the algorithm iterates the entire process that an interference graph must be rebuilt by spilling live range of a variable until the graph becomes colorable. Thus, we propose a new faster register allocation algorithm in a static compiler for architectures with a small number of registers by using an interference graph with weighted bidirectional edges. Our method applies colors of more than K-colors to virtual registers if K is the numbers of physical registers. Then the number of colors is reduced to K-colors by insertion of spill codes with only transformation of the graph. Thus, our method enables to allocate registers fast and to reduce spill codes in generated codes. A compiler that our method is applied to runs about 8% faster than GNU C Compiler version 3.4.4 (gcc-3.4.4).Also, the codes generated by our compiler run about 5% faster than the codes generated by gcc-3.4.4 in the Stanford Benchmark.

収録刊行物

参考文献 (8)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ