コンパイル速度の向上を目的とした非反復型レジスタ割付け手法

• Item type: Trans(1)
• 公開日: 2006-07-15
• タイトル: コンパイル速度の向上を目的とした非反復型レジスタ割付け手法
• タイトル / 言語: en
• タイトル: A Non-iterative Register Allocation Technique for Improving Compilation Speed
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 発表概要
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 早稲田大学大学院理工学研究科
• 著者所属: 早稲田大学大学院理工学研究科
• 著者所属: 日本IBM株式会社東京基礎研究所
• 著者所属: 日本IBM株式会社東京基礎研究所
• 著者所属: 早稲田大学大学院理工学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Science Engineering, Waseda University
• 著者所属(英): en
• 著者所属(英): Graduate School of Science Engineering, Waseda University
• 著者所属(英): en
• 著者所属(英): Tokyo Research Laboratory, IBM Japan Ltd.
• 著者所属(英): en
• 著者所属(英): Tokyo Research Laboratory, IBM Japan Ltd.
• 著者所属(英): en
• 著者所属(英): Graduate School of Science Engineering, Waseda University
• 著者名: 小川, 健一; 片岡, 正樹; 古関, 聰; 小松, 秀昭; 深澤, 良彰
• 著者名(英): Kenichi, Ogawa; Masaki, Kataoka; Akira, Koseki; Hideaki, Komatsu; Yoshiaki, Fukazawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 従来のグラフカラーリングを用いたレジスタ割付け手法は非常に有効であるが，スピルごとに反復しながら干渉グラフを再構築するため，レジスタの少ないアーキテクチャでは計算量が大きくなる．そのため，コンパイル時間が実行時間に含まれるダイナミックコンパイル環境では，レジスタ割付けにグラフカラーリングを適用することは難しかった．スピルごとに干渉グラフを再構築しないナイーブな方式としては，スピル用のレジスタを同命令で一度に使用されるオペランドの最大数だけリザーブするというものがあるが，x86のようなレジスタの少ないアーキテクチャには不向きである．本発表では，スピルごとに干渉グラフの再構築を行わず，かつリザーブされたレジスタを用いない新しい手法を提案する．この手法では，スピルされた変数をリザーブされたレジスタに割り当てるかわりに，スピルされていない変数にすでに割り当てられているレジスタを部分的に割り当てる．この操作は干渉グラフ上でノードの併合として表され，ノードの併合は最もコストが低くなるように行われる．このような方式を用いることで，スピル性能と実行速度の両方が高いレジスタ割付けが実現できる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Although the conventional graph-coloring-based register allocation is very effective, due to restructure the interference graph by repeating at each spill, the computational complexity grows in architecture with few registers. Therefore, it is difficult to apply graph coloring to register allocation in dynamic compilation that the compilation time is included in the execution time. There is a naive technique that the interference graph is not restructured at each spill. This technique is to reserve the register for spill for only maximum number of operands used at same time in an instruction. But, it is not adequate to the architecture with few registers like x86 architecture. We introduce a new register allocation technique that doesn't restructure the interference graph at each spill and doesn't use reserved registers. In this technique, instead of allocating the spilled variables to reserved registers, registers that have already been allocated in the non-spilled variables are partially allocated. This operation is shown as coalescing the node on the interference graph,and the node is coalesced so that costs become the lowest. Both the high spill performance and the high speed execution can be achieved by using such this method.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 47, 号 SIG11(PRO30), p. 54-54, 発行日 2006-07-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会