非循環グラフにおける支配関係の簡潔な検出算法

情報処理学会 Web Site 被引用文献1件 参考文献15件

書誌事項

タイトル別名
  • A Simple Algorithm to Identify Dominance Relations in DAG
  • ヒジュンカン グラフ ニ オケル シハイ カンケイ ノ カンケツ ナ ケンシュツ サンポウ

この論文をさがす

説明

本稿では，非循環有向グラフ（DAG; Directed Acyclic Graph）で表される制御フローグラフに対し，その支配関係を求める簡潔な算法を報告する．この算法は，頂点数 N，辺数 M のグラフに対して，大きさ N のスタックのプッシュとポップに基づき，N-1 回のリダクションを繰り返す．リダクションの進行中に，次のリダクション対象頂点を探す手続きはまったく必要としない．支配木と支配辺境の算出は，グラフに対する一連のリダクション操作がすべて終了したとき同時に完了する．本算法は計算量が O(N) の部分と O(M) の部分からなり，前者についての計算量は算法からほとんど自明である．後者については，N および M に対して独立な，グラフの構造の差異による若干の変動はあるものの，算法および計測の結果から，実用のプログラムでは，ほぼ M に比例し，O(M) であることが主張できる．SpecCFP92テストプログラムから約240本を選抜して実行した結果は，統計的に，M に対して，多少のばらつきをともなう線形性を示し，比例係数は平均1.5，最大2.5であった．これは既発表の他の方法より約3倍高速である．

In this paper, we report a compact algorithm for dominance analysis of control flow graph in the form of directed acyclic graph (DAG). This algorithm repeats N-1 reductions on the graph with N nodes and M edges, controled by push and pop of a stack of size N. There is no need of any search for next node to be reduced in the progress of reduction. The dominator tree construction as well as dominance frontier computation is completed at the end of the series of reductions for the graph. The algorithm has two sections of O(N) and O(M) complexity. The complexity of former is self-evident from the algorithm. The complexity of latter can be declared to be almost linear and O(M) for real programs from the algorithm and observation. Although we have a little variance from linearity, it is caused by the difference of graph structure which is independent of N or M. Our test using about 240 samples of real programs from SpecCFP92 resulted in scatter-diagram suggesting its linearity about M, and showed 1.5\,M in average and 2.5\,M at maximum, statistically for the O(M) section. This means that our algorithm is about 3 times faster than another one that has been published already.

収録刊行物

被引用文献 (1)*注記

もっと見る

参考文献 (15)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ