静的単一代入形式上で通常形式部分冗長除去を実現する汎用的手法

• Item type: Trans(1)
• 公開日: 2008-01-15
• タイトル: 静的単一代入形式上で通常形式部分冗長除去を実現する汎用的手法
• タイトル / 言語: en
• タイトル: A Generalized Method for Realizing PRE on SSA Form
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 通常論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 東京工業大学大学院情報理工学研究科数理・計算科学専攻
• 著者所属: 東京工業大学大学院情報理工学研究科数理・計算科学専攻 現在，NEC
• 著者所属: 東京工業大学大学院情報理工学研究科数理・計算科学専攻
• 著者所属(英): en
• 著者所属(英): Department of Mathematical and Computing Sciences,Graduate School of Information Science and Engineering,Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Mathematical and Computing Sciences,Graduate School of Information Science and Engineering,Tokyo Institute of Technology, Presently with NEC Corporation
• 著者所属(英): en
• 著者所属(英): Department of Mathematical and Computing Sciences,Graduate School of Information Science and Engineering,Tokyo Institute of Technology
• 著者名: 今橋, 孝典; 伊藤陽; 佐々, 政孝
• 著者名(英): Takanori, Imahashi; Yo, Ito; Masataka, Sassa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 部分冗長除去（PRE）は，部分的に冗長な式を除去する変換で，共通部分式除去とループ不変式移動の効果を含んだ効果的なプログラム最適化である．このPREを，最適化に適した形式である静的単一代入（SSA）形式上で行おうという従来研究がいくつかあるが，これは一般には容易ではない．その理由は，SSA形式の特徴である，変数名の一意性に関する規則がPREの実装の妨げになるからである．たとえば，同じ名前であった変数どうしがSSA形式化にともない異なる名前になり，変数名の同一性の判断ができなくなるといった問題があげられる．このような問題に対し，従来手法では，PREをSSA形式上で実現するために特別なデータ構造を用いるなど複雑な処理を行っていた．これに対し本論文では，SSA形式でありながら通常形式にも近い性質を持つCSSA形式とphicongruence classというものを利用すれば，SSA形式でも通常形式における変数名の同一性が判断できることに着目した．その事実に基づいて，通常形式のPREアルゴリズムをSSA形式に適用する手法を提案した．この手法は汎用的なものであり，挿入点の決定・式の挿入・式の置き換え（冗長性の除去）という通常の手順に従うPREであれば，原則としてアルゴリズムによらずSSA形式に対応させることができ，また元々のPREのアルゴリズムの枠組みを変える必要もない．本手法を確かめる実験として，代表的なPREアルゴリズムの1 つであるLazy Code MotionをSSA形式上のアルゴリズムに変換し，変換後でも部分冗長除去の効果が変わりなく発揮されていることを確認した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Partial Redundancy Elimination (PRE) is an effective optimization for eliminating partially redundant expressions and contains effects of common subexpression elimination and hoisting loop invariant. There have been some previous attempts to apply PRE to Static Single Assignment(SSA) form that is a suitable intermediate form for optimization. But such attempts have general difficulty because of the characteristics of variable names in SSA form. For example,variables which have the same name on normal form may have different names on SSA form. So, it becomes difficult to identify the same variables in SSA form. To handle such problems, previous methods perform complicated processing by using special data structures and so on. To deal with this problem, we pay attention to the so-called CSSA form and phi congruence class (pcc). With CSSA form and pcc, we can identify the same variables on SSA form. Based on this fact, we propose a method for transforming PRE algorithms for normal form to those for SSA form. This tranformation is a universal one. So, in principle, it can transform any PRE algorithm which has ordinary process (deciding insertion point, insertion of expression, and replacing expressions), and does not change the framework of the original PRE algorithm. Finally, as an experiment, we apply this method to Lazy code motion (LCM) that is one of representative PRE algorithms. We confirmed that the transformed LCM in SSA form performs PRE correctly and produces object code with the same efficiency as the one in normal form.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 49, 号 SIG1(PRO35), p. 84-95, 発行日 2008-01-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会