支配辺境を用いた最小 SSA の計算

ウィキペディア小見出し辞書

支配辺境を用いた最小 SSA の計算

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/08 08:22 UTC 版)

「静的単一代入」の記事における「支配辺境を用いた最小 SSA の計算」の解説

まず、dominator の概念が必要である。制御フローのノード A が別のノード B を 厳密に支配する とき、A に到達しなければ B に到達することがないことを意味する。これは、B に到達していれば A のコードが動作していることが分かるため有用である。また A が B を 支配するとき、A が B を厳密に支配するか、A = B であることを意味する。 ここで、支配辺境(dominance frontier)を次のように定義することができる。A は B を厳密に支配していないが、B の直前にあるノードのいくつかを支配しているとき( A が B の直前にあれば、A 自身)、ノード B は A の支配辺境内にあるものとする。A から見ると、これらは A を介さず、最初に登場する制御パス上のノードである。 支配辺境は Φ 関数を必要とする場所を正確に捉えることができ、その定義のみ（あるいは再定義）が A の支配するノードに到達する。これらのノードを去り支配辺境に入る場合のみ、同じ変数を定義している箇所にそれ以外のフローを考慮すればよい。また、制御フローグラフ中に A の定義を扱う Φ 関数はそれ以上必要ない。 支配辺境を求めるアルゴリズムに一つとして、下記のものがある。 for each node b if the number of predecessors of b ? 2 for each p in predecessors of b runner := p while runner ≠ idom(b) add b to runner’s dominance frontier set runner := idom(runner) 注意：上記のコードでは、ノード n の前のノードは制御を n に渡す任意のノードであり、idom(n) がノードの n を直接支配する。 支配辺境を見つけるための効率的なアルゴリズムが存在し、論文 "Efficiently computing static single assignment form and the control dependence graph", by R. Cytron, J. Ferrante, B. Rosen, M. Wegman and F. Zadeck, ACM Trans. on Programming Languages and Systems 13(4) 1991 pp.451–490. において最初に示された。また "Modern compiler implementation in Java" by Andrew Appel (Cambridge University Press, 2002) も有用である。詳細は論文を参照のこと。 ライス大学の Keith D. Cooper, Timothy J. Harvey, Ken Kennedy は、論文 A Simple, Fast Dominance Algorithmにおいて、アルゴリズムを提唱した。このアルゴリズムはよく設計されたデータ構造を用いてパフォーマンスを改善させている。