依存グラフを用いてアーキテクチャ独立な最適化と対象計算機の資源制約を調整する手法

• Item type: Trans(1)
• 公開日: 2001-02-15
• タイトル: 依存グラフを用いてアーキテクチャ独立な最適化と対象計算機の資源制約を調整する手法
• タイトル / 言語: en
• タイトル: Using Dependence -graph- based Code Transformation to Adjust Architecture Independent Optimizations to Machine Resource Constraint
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 通常論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 日本アイ・ビー・エム株式会社東京基礎研究所
• 著者所属: 日本アイ・ビー・エム株式会社東京基礎研究所
• 著者所属: 日本アイ・ビー・エム株式会社東京基礎研究所
• 著者所属(英): en
• 著者所属(英): Tokyo Research Laboratory, IBM Japan, Ltd.
• 著者所属(英): en
• 著者所属(英): Tokyo Research Laboratory, IBM Japan, Ltd.
• 著者所属(英): en
• 著者所属(英): Tokyo Research Laboratory, IBM Japan, Ltd.
• 著者名: 稲垣, 達氏; 古関, 聰; 小松, 秀昭
• 著者名(英): Tatsushi, Inagaki; Akira, Koseki; Hideaki, Komatsu
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: コンパイラにおける共通部分式削除やコピー伝搬などのアーキテクチャ独立な最適化と，レジスタ割付やコードスケジューリングなどのアーキテクチャ依存の最適化は，それぞれ独立したヒューリスティクスに基づいた，異なるパスとして実現されている．実際には共通部分式削除やコピー伝搬も，対象アーキテクチャの物理レジスタ数制約に対してトレードオフを持っている．しかし，これらの問題を完全に協調的に解くことは非常に計算コストが高く，現実的ではない．本研究では，アーキテクチャ独立な最適化とアーキテクチャ依存最適化の間に，物理レジスタ数の制約によるトレードオフを緩和するパスを設けることで，アーキテクチャ独立な最適化およびアーキテクチャ依存な最適化の効果を上げる手法を示す．本方式は，基本ブロック内の中間コードを演算子の依存グラフで表現し，使用レジスタ数を見積もりながら1パスの4つ組生成を行う．使用レジスタ数が少ない部分では，コードスケジューリングに対して不必要な制約を導入しないように，クリティカルパス上の演算子が連続するような4つ組生成を行う．使用レジスタ数が多い部分では，レジスタ割付時に余分なスピルコードを発生させないように，一時変数を減らすような順番で4つ組を生成する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In current compilers, architecture independent code optimizations, such as common subexpression elimination and copy propagation, and architecture dependent optimizations, such as register allocation and code scheduling, are implemented as separate passes that have mutually independent heuristics. Actually, common subexpression and copy propagation also have some tradeoff against the number of physical registers of the target architecture. However, cooperative solution of these problems requires high computation cost. In this paper, we solve this problem by inserting an additional pass between architecture independent code optimizations and architecture dependent optimizations to alleviate the constraint of the number of physical registers and improve results of both optimizations. Operations in a basic block are represented by DAG (directed acyclic graph). We apply one-pass quadruple generation algorithm that considers the number of currently used registers. When register pressure is low, operations on the critical path are continuously generated not to introduce unnecessary constraint for code scheduler. When register pressure is high, we prioritize operations that reduce the number of temporary variables so that register allocator does not generate unnecessary spill codes.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 42, 号 SIG02(PRO9), p. 71-80, 発行日 2001-02-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会