述語付きソフトウェア・パイプラインへのSpiral Graphによるレジスタ割付け

概要

論文の詳細を見る
ソフトウェア・パイプラインによる最適化をハードウェアで補助する仕組みとして,レジスタ改名機構と述語付き命令実行機構がある.レジスタ改名機構向けのレジスタ割付け手法としてSpiral Graphを用いた方法が提案されているが,述語付き命令実行機構を備えた場合の割付け方法について詳しい解析がなされていなかった.本論文では,それら2つの補助機能を備えたIA-64のようなアーキテクチャに対するレジスタ割付け手法として,述語付きSpiral Graphを提案する.述語付きSpiral Graphは,従来のトラックを述語の値に応じた副トラックの集合と見なすことで,述語が異なる命令で別に定義される生存区間を適切に表現することができる.述語付きSpiral Graphを用いることで,必要レジスタ数を最小とするレジスタ割付けが多項式時間で行える.提案するアルゴリズムでは,必要レジスタ数の下界であるW_<max>本のレジスタで割付けが行えるか判定を行い,必要レジスタ数がW_<max>本の場合の割付け結果が得られ.そうでない場合には,W_<max>+1本での割付け結果が得られる.
2002-09-15