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

IPSJ Web Site 20 References

Bibliographic Information

Other Title
  • セイテキ タンイツ ダイニュウ ケイシキジョウ デ ツウジョウ ケイシキ ブブン ジョウチョウ ジョキョ オ ジツゲンスル ハンヨウテキ シュホウ
  • A Generalized Method for Realizing PRE on SSA Form

Search this article

Abstract

部分冗長除去（PRE）は，部分的に冗長な式を除去する変換で，共通部分式除去とループ不変式移動の効果を含んだ効果的なプログラム最適化である．このPREを，最適化に適した形式である静的単一代入（SSA）形式上で行おうという従来研究がいくつかあるが，これは一般には容易ではない．その理由は，SSA形式の特徴である，変数名の一意性に関する規則がPREの実装の妨げになるからである．たとえば，同じ名前であった変数どうしがSSA形式化にともない異なる名前になり，変数名の同一性の判断ができなくなるといった問題があげられる．このような問題に対し，従来手法では，PREをSSA形式上で実現するために特別なデータ構造を用いるなど複雑な処理を行っていた．これに対し本論文では，SSA形式でありながら通常形式にも近い性質を持つCSSA形式とphicongruence classというものを利用すれば，SSA形式でも通常形式における変数名の同一性が判断できることに着目した．その事実に基づいて，通常形式のPREアルゴリズムをSSA形式に適用する手法を提案した．この手法は汎用的なものであり，挿入点の決定・式の挿入・式の置き換え（冗長性の除去）という通常の手順に従うPREであれば，原則としてアルゴリズムによらずSSA形式に対応させることができ，また元々のPREのアルゴリズムの枠組みを変える必要もない．本手法を確かめる実験として，代表的なPREアルゴリズムの1 つであるLazy Code MotionをSSA形式上のアルゴリズムに変換し，変換後でも部分冗長除去の効果が変わりなく発揮されていることを確認した．

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.

Journal

References(20)*help

See more

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top