순차감축 알고리즘과 지연감축 알고리즘을 이용한 효과적인 지배자 트리의 구현 = Implementation of Effective Dominator Trees Using Eager Reduction Algorithm and Delay Reduction Algorithm

국문 초록 (Abstract)

지배자 트리란 유향그래프에서 지배관계를 트리로 표현한 것이다. 임의의 유향그래프로부터 지배자 트리를 구성하기 위한 효과적인 알고리즘을 제시한다. 감축 가능한 흐름그래프는 지배자 계산을 한 후 지배자 트리로 감축된다. 감축 불가능한 흐름그래프는 정보 테이블의 연결가지 정보를 이용하여 지배자 연결그래프로 구성된다. 지배자 연결그래프에서 지배자 트리로 감축하기 위하여 효과적인 순차감축 알고리즘과 지연감축 알고리즘을 구현한다. 구현한 결과 순차감축 알고리즘 보다 지연감축 알고리즘의 실행시간이 빠르다. 따라서 흐름그래프에서 효과적인 지배자 트리로 감축된다.

다국어 초록 (Multilingual Abstract)

The dominator tree presents the dominance frontier from directed graph to the tree. we present the effective algorithm for constructing the dominator tree from arbitrary directed graph. The reducible flow graph was reduced to dominator tree after dominator calculation. And the irreducible flow graph was constructed to dominator-join graph using join-edge information of information table. For reducing the dominator tree from dominator-join graph, we implement the effective sequency reducible algorithm and delay reducible algorithm. As a result of implementation, we can see that the delay reducible algorithm takes less execution time than the sequency reducible algorithm. Therefore, we can reduce the flow graph to dominator tree effectively.

참고문헌 (Reference)

1 "자료 흐름 분석을 위한 효과적인 지배자 트리 알고리즘" 1998

2 "Incremental data flow update via attribute and dominator updates" In ACM SIGPLAN- SIGACT Symposium on the Principles of Programming Languages 274-284, 1988.01

3 "Incremental Computation of Dominator Trees" 30 (30): 1-12, 1995.

4 "Identifying Loops Using DJ Graphs" 18 (18): 649-658, 1996.

5 "An incremental algorithm for maintaining the dominator tree of a reducible flowgraph" In ACM SIGPLAN-SIGACT Symposium on the Principles of programming Languages 314-325, 1994.01

6 "A unified approach to path problems" 28 : -3, pp.577-593.1981b.

7 "A program data flow analysis procedure" 19 (19): 137-147, 1977.

8 "A New Framework for Elimination-Based Data Flow Analysis Using DJ Graphs" 20 (20): 388-435, 1998.