臺灣博碩士論文加值系統

可化簡流程圖(reducible flowgraphs)在程式碼最佳化和資料流程分析中扮演很重要的角色。
如果我們在一個可化簡流程圖裡增加額外的邊，將導致此圖失去可化簡的特性，則我們稱此圖為最大可化簡流程圖(maximal reducible flowgraphs)。
根據最大可化簡流程圖的分解定理(decomposition theorem)[Congr. Numer. 139 (1999) 9--20]，我們推導出計算最大可化簡流程圖中所有環路個數的公式。
此外，若給定最大可化簡流程圖所對應的分解樹，則我們提供一列舉演算法以產生此圖的所有環路。
另外，化簡流程圖的邊賦予權重， 那麼我們可以使用動態程式規劃(dynamic programming)的技巧，設計一演算法以找出此圖的最大加權環路。

Reducible flowgraphs serve as useful vehicle in code optimization and data-flow analysis of computer programs. A reducible flowgraph is maximal (MRF for short) if no more edge can be added without violating reducibility. Based on a decomposition theorem of MRFs proposed in [Congr. Numer. 139 (1999) 9–20], a formula for
counting the number of elementary cycles in MRFs is derived. Moreover, we propose an algorithm for generating all elementary cycles when its corresponding decomposition tree is given. Additionally, if an MRF G is considered to be in weighted case, we
propose an algorithm that finds a heaviest cycle of G using dynamic programming approach.

摘要 I
Abstract II
誌謝 III
Contents IV
List of Figures V
1 Introduction 1
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1
1.2 Motivation and Intentions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3
2 Preliminaries 4
2.1 Flowgraphs and Reducible Flowgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4
2.2 Maximal Reducible Flowgraphs and Their Decompositions . . . . . . . . . . . . . . . . .7
3 Counting the Number of Elementary Cycles in MRFs 10
3.1 Recursive Formulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10
3.2 An Enumeration Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .14
4 On the Heaviest Cycle in MRFs 20
4.1 The Heaviest Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20
5 Conclusion and Future Work 27
Bibliography 28
Appendix 31

[1] J. M. Adams, J. M. Phelan, and R. H. Stark, A note on the Hecht-Ullman characterization of nonreducible flow graphs, SIAM J. Comput. 3 (1974) 222–223.
[2] A. V. Aho, R. Sethi, and J. D. Ullman, Compilers: Principles, Techniques and Tools, Addison-Wesley, Reading, MA, 1986.
[3] A. V. Aho and J. D. Ullman, The Theory of Parsing, Translation and Compiling, Prentice-Hall, Englewood Cliffs, NJ, 1973.
[4] M. D. Carrol and B. G. Ryder, Incremental data flow analysis via dominator and attribute updates, Proceedings of the 15th Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, 1988, pp. 274–284.
[5] S. Chen and D. R. Ryan, A comparison of three algorithms for finding fundamental cycles in a directed graph, Networks 11 (1981) 1–12.
[6] M. S. Hecht and J. D. Ullman, Flow graph reducibility, SIAM J. Comput. 1 (1972) 188–202.
[7] M. S. Hecht and J. D. Ullman, Characterization of reducible flow graphs, J. Assoc. Comput. Mach. 21 (1974) 367–375.
[8] M. S. Hecht and J. D. Ullman, A simple algorithm for global data flow analysis problems, SIAM J. Comput. 4 (1975) 519–532.
[9] A. Nijenhuis and H. Wilf, Combinatorial Algorithms for Computers and Calculators, Academic Press, Orlando, FL, 1978.
[10] V. Ramachandran, A minimax arc theorem for reducible flow graphs, SIAM J. Disc. Math. 3 (1990) 554–560.
[11] G. Ramalingam and T. Reps, An incremental algorithm for maintaining the dominator tree of a reducible flowgraph, Conference Record of the 21st ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, 1994, pp. 287–296.
[12] R. C. Read and R. E. Tarjan, Bounds on backtrack algorithms for listing cycles, paths, and spanning trees, Networks 5 (1975) 237–252.
[13] E. M. Reingold, J. Nievergelt, and N. Deo, Combinatorial Algorithms: Theory and Practice, Prentice-Hall, Englewood Cliffs, NJ, 1977.
[14] A. Shamir, A linear time algorithm for finding minimum cutsets in reducible flowgraphs, SIAM J. Comput. 8 (1979) 645–655.
[15] V. C. Sreedhar, Efficient program analysis using DJ-Graphs, Ph.D. Thesis, School of Computer Science, McGill University, Montreal, Canada, 1995.
[16] V. C. Sreedhar, Y-F. Lee, G. R. Gao, Incremental computation of dominator trees, Proceedings of the ACM SIGPLAN Workshop on Intermediate Representations, 1995, pp. 1–12.
[17] J. L. Szwarcfiter, On digraphs with a rooted tree structure, Networks 15 (1985) 49–57.
[18] R. E. Tarjan, Enumeration of elementary circuits of a directed graph, SIAM J. Comput. 2 (1974) 211–216.
[19] J. C. Tiernan, An efficient search algorithm to find the elementary circuits of a graph, Comm. ACM 13 (1970) 722–726.
[20] O. Vernet, Maximalidade em grafos de fluxo redutiveis, D.Sc. Thesis, COPPE, Universidade Federal do Rio de Janeiro, Rio de Janeiro, RJ, Brasil, 1997.
[21] O. Vernet and L. Markenzon, Hamiltonian problems for reducible flowgraphs, Proceedings of the XVII International Conference of the Chilean Computer Science Society, Valparaiso, Chile, 1997, pp. 264–267.
[22] O. Vernet and L. Markenzon, Characterizations and properties of maximal reducible flowgraphs, Congr. Numer. 139 (1999) 9–20.
[23] O. Vernet and L. Markenzon, Solving problems for maximal reducible flowgraphs, Discrete Appl. Math. 136 (2004) 341–348.
[24] H. Weinblatt, A new search algorithm for finding the simple cycles of a finite directed graph, J. ACM 19 (1973) 43–56.
[25] J. T. Welch, A mechanical analysis of the cyclic structure of undirected linear graphs, J. ACM 13 (1966) 205–210.