具有可适应性的程序分析技术
|
摘要
编译器在发掘高性能计算机系统并行性的过程中起着非常重要的作用，而其中程序分析又是编译器开发并行性的关键步骤之一。然而，对编译器精度和功能的要求的逐步提高，导致程序分析日益复杂，难于编写、移植和维护。因此，程序分析部分的可适应性问题成为编译领域的研究热点之一。本文在对程序分析算法本身及程序分析对不同并行体系结构的支持方式进行了较为深入的研究后，得到了一个能解决程序分析可适应性问题的整体方案，该方案通过运用多视图的编程范式、过程间分析优化程序自动生成和增量式分析算法等手段，取到了比较好的效果。
本文的主要贡献有：
1．提出一个能适用于所有过程间数据流分析问题的模型。这个模型中过程间分析问题完全是过程内分析问题的扩展，克服了以前其它模型把过程间和过程内分析问题割裂开来的缺点。通过这种模型，我们可以采用统一的、相互协作的过程间和过程内算法解决数据流分析问题，并得到较为精确的上下文敏感的分析结果。
2．根据以上问题模型，提出并实现了一个过程间分析优化程序生成器——IGEN。在IGEN中，我们主要解决了用户描述方法，算法框架选择等问题。由于以上问题的很好解决，IGEN可以生成过程间分析程序和优化程序，并且，它生成的程序具有独立于中间表示，可在一定范围内拼装、选择算法，可增量式维护信息等特点。所以，IGEN既能大幅度减轻程序员的劳动，又能大大提高过程间分析优化部分的可适应性。
3．提出了用多视图的编程范式编制程序分析部分的方案。这里，我们主要解决了视图的划分和定义，算法抽象层次的确定等问题，该方案的运用使程序分析部分从多个方面具备了较高程度的可适应性。
4．提出了一种增量式分析算法。该算法可以适用于所有类型的流图——包括可归约流图和不可归约流图。另外，它实现也比较简单，能方便地运用于分析程序自动生成器中。
5．根据以上算法和设计，实现了一个具有可适应性的程序分析高层模块，并将这个模块分别运用在几个不同的编译系统中，对该模块从正确性、效率和可适应性等几方面进行了验证。
Compiler is very critical to exploit the parallelism for all kinds of parallel processing systems. Program analysis is the most important way to find the parallelism among all phases of a compiler. But the increasing requirement on the aspects of accuracy and functionality causes that the program analysis phase become more and more complicated to be developed, ported and maintained. So, the research on the flexibility of the program analysis has become a hotspot on the compilation field. After the deeply study of the algorithm and the way to support different parallel architectures of the program analysis, this paper presents an integral approach to improve the flexibility of the program analysis phase. By using many useful techniques, such as multi-view programming paradigm, automatic generation of the interprocedural analyzer and optimizer and incremental analysis, the approach can acquire fairly good effect.
The main contributions of this paper are listed below.
Present an interprocedural model, which can describe all data flow problem. In the model, each interprocedural problem is the extension of its corresponding intraprocedural problem, which can avoid solving the interprocedural problems and the intraprocedural problems completely separately. By using this model, we can solve an interprocedural problem by applying an algorithm consisting of two cooperative parts— the interprocedural part and the intraprocedural part and can get context-sensitive analysis result.
Present and implement an automatic generator of analyzers and optimizers — IGEN. In the design, we provide a proper description method to users and select the compatible frameworks for the interprocedural part and the intraprocedural part. IGEN can generate interprocedural analyzers and optimizers and the features of its products are: they are independent of intermediate representation; they can maintain the analysis information incrementally; they provide several selections to users to select algorithms. Generally, IGEN can not only save a lot of developing work of programmers, but also improve the flexibility of the program analysis phase greatly.
Present an approach of using multi-view programming paradigm to construct the program analysis phase, which mainly solve such problems as the decision of the size of views, the division of views and the abstractive level of algorithms.
本文的主要贡献有：
1．提出一个能适用于所有过程间数据流分析问题的模型。这个模型中过程间分析问题完全是过程内分析问题的扩展，克服了以前其它模型把过程间和过程内分析问题割裂开来的缺点。通过这种模型，我们可以采用统一的、相互协作的过程间和过程内算法解决数据流分析问题，并得到较为精确的上下文敏感的分析结果。
2．根据以上问题模型，提出并实现了一个过程间分析优化程序生成器——IGEN。在IGEN中，我们主要解决了用户描述方法，算法框架选择等问题。由于以上问题的很好解决，IGEN可以生成过程间分析程序和优化程序，并且，它生成的程序具有独立于中间表示，可在一定范围内拼装、选择算法，可增量式维护信息等特点。所以，IGEN既能大幅度减轻程序员的劳动，又能大大提高过程间分析优化部分的可适应性。
3．提出了用多视图的编程范式编制程序分析部分的方案。这里，我们主要解决了视图的划分和定义，算法抽象层次的确定等问题，该方案的运用使程序分析部分从多个方面具备了较高程度的可适应性。
4．提出了一种增量式分析算法。该算法可以适用于所有类型的流图——包括可归约流图和不可归约流图。另外，它实现也比较简单，能方便地运用于分析程序自动生成器中。
5．根据以上算法和设计，实现了一个具有可适应性的程序分析高层模块，并将这个模块分别运用在几个不同的编译系统中，对该模块从正确性、效率和可适应性等几方面进行了验证。
Compiler is very critical to exploit the parallelism for all kinds of parallel processing systems. Program analysis is the most important way to find the parallelism among all phases of a compiler. But the increasing requirement on the aspects of accuracy and functionality causes that the program analysis phase become more and more complicated to be developed, ported and maintained. So, the research on the flexibility of the program analysis has become a hotspot on the compilation field. After the deeply study of the algorithm and the way to support different parallel architectures of the program analysis, this paper presents an integral approach to improve the flexibility of the program analysis phase. By using many useful techniques, such as multi-view programming paradigm, automatic generation of the interprocedural analyzer and optimizer and incremental analysis, the approach can acquire fairly good effect.
The main contributions of this paper are listed below.
Present an interprocedural model, which can describe all data flow problem. In the model, each interprocedural problem is the extension of its corresponding intraprocedural problem, which can avoid solving the interprocedural problems and the intraprocedural problems completely separately. By using this model, we can solve an interprocedural problem by applying an algorithm consisting of two cooperative parts— the interprocedural part and the intraprocedural part and can get context-sensitive analysis result.
Present and implement an automatic generator of analyzers and optimizers — IGEN. In the design, we provide a proper description method to users and select the compatible frameworks for the interprocedural part and the intraprocedural part. IGEN can generate interprocedural analyzers and optimizers and the features of its products are: they are independent of intermediate representation; they can maintain the analysis information incrementally; they provide several selections to users to select algorithms. Generally, IGEN can not only save a lot of developing work of programmers, but also improve the flexibility of the program analysis phase greatly.
Present an approach of using multi-view programming paradigm to construct the program analysis phase, which mainly solve such problems as the decision of the size of views, the division of views and the abstractive level of algorithms.
引文
[Aho88] A.V.Aho, R.Sethi, and J.D.Ullman. Compiler: Principles, Techniques and Tools. Addison-Wesley, 1988.
[Allen97] Allen L., Prop Language Reference Manual, Tech. Report, Courant Institute of Mathematical Sciences, 1997.
[Blume94] Blume B., Eigenmann R., Faign K., Grout J., Hoeflinger J., Padua D., Petersen P., Pottenger B., Raughwerger L., Tu P., Weatherford S., Polaris: The Next Generation in Parallelizing Compilers, Proceedings of the 7th Workshop on Languages and Compilers for Parallel Computing, August 1994.
[Burke90a] Michael G. Burke, An Interval-based Approach to Exhaustive and Incremental Interprocedural Data-Flow Analysis. ACM Transactions on Programming Languages and Systems, Vol. 12, No.3, p341-395, July 1990.
[Burke90i] Michael G. Burke and Barbara Gershon Ryder, A Critical Analysis of Incremental Iterative Data Flow Analysis Algorithm, In IEEE Transactions on Software Engineering, Vol. 16, No.7, July 1990.
[Callahan88] D. Callahan. The Program Summary Graph and Flow-Sensitive Interprocedural Data Flow Analysis. In proceeding of PLDI'88, June 1988.
[Canfora98] Gerardo Canfora and Aniello Cimitile, An Extensible System for Source Code Analysis. In IEEE Transactions on Software Engineering, Vol.24, No.9, September 1998.
[Carol188] M. D. Carroll and B. G. Ryder, Incremental Data Flow Analysis via Dominator and Attribute Updates, in Conference Record of the Fifteenth Annual ACM Symposium on Principles of Programming Languages, p274-184, Jan. 1988,.
[CCl99] 张兆庆，吴承勇，并行程序设计环境关键技术子项目计划书——通用编译基础设施，1999。
[Chaitin82] Chaitin G. J., Register Allocation and Spilling via Graph Coloring, In Proceeding of the ACM SIGPLAN Symposium on Compiler Construction,Boston, 1982.
[Charles92] Charles W. Krueger, Software Reuse, ACM Computing Surveys, Vol.24,No. 2, June 1992.
[Chen93] William Yu-wei Chen, Data Preload for Superscalar and VLIW Processors,Ph.D. Dissertation, UIUC,1993.
[Cooper84] K.Cooper and K.Kennedy, Efficient Computation of Flow Insensitive Interprocedure Summary Information, SIGPLAN Notices, vol.19, no.6,p247-258, June 1984.
[Cytron91] Ron Cytron, Jeanne Ferrante, Varry K.Rosen and Mark N.Wegman,Efficiently Computing Static Single Assignment Form and the Control Dependence Graph, ACM Transaction on Programming Languages and Systems, Vol.13, No4, p451-490, October 1991.
[Dev96] P. Devanbu, D. Rosenblum and A. Wolf. Generating Testing and Analysis Tools with Aria, ACM Transactions on Software Engineering and Methodology, vol. 5, p42-62, January 1996.
[Dirk93] Dirk G. and Harini S., Data Flow Equations for Explicitly Parallel Programs, Proceedings of the Fourth ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming, San Diego, California,May 1993.
[Farrow75] Farrow, Rodney, Ken Kennedy and Linda Zucconi. Graph Grammars and Global Program Flow Analysis, In Proceedings of the 17~(th) IEEE Symposium on Foundations of Computing Science, Houston, TX, Now.1975.
[FSF95] Free Software Foundation, GCC User Manual, 1995.
[Gordon97] Gordon S. Novak Jr, Software Reuse by Specialization of Generic Procedures through Views, IEEE Transactions on Software Engineering,Vol. 23,No. 7,July 1997.
[Hall93] M.W. Hall. FIAT: A Framework for Interprocedural Analysis and Transformation. In the proceeding of the 6~(th) international workshop of languages and compilers for parallel computing, Oregen, USA, August,LNCS 768,p522-545, 1993.
[Harrold97] Mary Jean Horrold, Aristotle: A System for Research on and Development of Program-Analysis-Based Tools,http://www.cis.ohio-state.edu/～harrold/organnon/dev1/code, 1997.
[Hecht75] M.S.Hecht and J.D.Ullman, A Simple Algorithm for Global Data-Flow Analysis Problems, SIAM J. Compt. 4, p519-532, December 1975.
[http:suif] http://suif.stanford.edu/ , SUIF Home Page.
[James 93] James C. Dehnert and Ross A. Towle, Compiling for the Cydra 5. In the Journal of Supercomputing, Vol. 7, 1993.
[Jaspal93] Jaspal Subholk, James M. Stichnoth, David R. O'Hallaron, Thomas Gross,Exploiting Task and Data Parallellism on a Multicomputer, Proceedings of the Fourth ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming, San Diego, California, May 1993.
[Johan96] Johan Janssen and Henk Corporal, Controlled Node Splitting, In the proceedings of the 6~(th) international conference of compiler construction,Sweden, April 1996.
[Kaldill73] Gary A. Kildall. A Unified Approach to Global Program Optimization, in proceedings of the 1~(st) Annual ACM Symposium on Principles of Programming Languages, p194-206, 1973.
[Kic96] Gregor Kiczales, Aspect-Oriented Programming, Position Paper from the Aspect-Oriented Programming Project, http://www.parc.xerox.xom/spl/projects/aop/loc
[Kuck81] Kuck. D.J., Kuhn. R.H., Padua.D.A., Leasure.B, and Wolfe.M.M,Dependence Graphs and Compiler Optimizations. In Proceedings of the 8~(th) Annual ACM Symposium on Principles of Programming Languages, New York,p207-218.
[Lam91] Lam.M, Rinard.M, Coarse-Grain Parallel Programming in Jade. In Proceedings of the Third ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Williamsburg, VA, April 1991.
[Landi93] W. Landi, B. G. Ryder and S. Zhang, Interprocedural Modification Side Effect Analysis with Pointer Aliasing, In SIGPLAN 93 Symposium on Programming Language Design and Implementation, p56-67, June 1993.
[Lee87] Lee.E.A, Messerschmitt.D.G, Static Scheduling of Synchronous Data Flow Programs for Digital Signal Processing, IEEE Transactions on Computers,Jan. 1987.
[LenT79] Lengauer, Thomas and Robert E. Tarjan. A Fast Algorithm for Finding Dominators in a Flow Graph, ACM TOPLAS, Vol, No.1, July 1979, p121-141.
[Lopes95] Cristina Videira Lopes, AP/S++: Case-study of a MOP for Purposes of Semantics, ACM Symposium on POPL'87.
[Lowney93] P.Geoffery Lowney, The Multiflow Trace Scheduling Compiler, In the Journal of Supercomputing, Vol. 7,1993.
[Mahlke96] Scott Alan Mahlke, Exploiting ILP In the Present of Conditional Branch,Ph.D. Dissertation, UIUC, 1996.
[Marlowe90] T.J.Marlowe and B.G.Ryder, An Efficient Hybrid Algorithm for Incremental Data Flow Analysis, in Conference Record of the Seventeenth Annual ACM Symposium on Principle of Programming Languages,p184-196, Jan. 1990.
[Mary96] Mary W. Hall, Seema hiranandani, Ken Kennedy, Chaw-Wen Tseng: Interprocedure Compilation on FortranD, Journal of Parallel and Distributed Computing 38(2), p114-129, 1996.
[Maydan92] Dror Eliezer Maydan, Accurate Analysis of Array Reference, Ph.D. Dissertation, Stanford university.
[NCI97] The National Compiler Infrastructure Project,http://www.cs.virginia.edu/users/novak
[Obri95] O'brien K. et al, XIL and YIL: The Intermediate Language of TOBEY,ACM SIGPLAN Workshop on Intermediate Representation, CA, Jan. 1995.
[Pande91] H.D.Pande and William Landi. Interprocedural Def-Use Associations in C Program, In Proceeding of Symposium on Testing, Analysis and Verification,p139-153, 1991.
[PCF91] Parallel Computing Forum. PCF Parallel FORTRAN Extensions. FORTRAN Forum, September 1991.
[Pollock89] L.Pollock and M.Soffa, An Incremental Version of Iterative Data Flow Analysis ", IEEE Transactions on Software Engineering, Vol.15, no.12,Dec. 1989.
[Proe92] Todd A. Proebsting, Code Generation Techniques, Ph.D. thesis,University of Wisconsin, 1992.
[Rau93] B.Ramakrishna Rau and Joseph A. Fisher, Instruction-Level Parallel Processing: Histroy, Overview and Perspective. In the Journal of supercomputing, Vol. 7,1993.
[Ryder88] Barbara G. Ryder and Marven C. Paull, Incremental Data-Flow Analysis Algorithms, In ACM Transactions on Programming Languages and Systems, Vol.10, No.1, p1-50, January 1988.
[SCG94] Stanford Compiler Group, the SUIF Library, 1994.
[Shar80] Sharir, Micha. Structural Analysis : A New Approach to Flow Analysis in Optimizing Compilers, Computer Languages, p141-153, Vol.5,1980.
[Sreedhar95] Sreedhar, V.C., Gao,G.R., and Lee,Y. Incremental Computation of Dominator trees. In ACM SIGPLAN Workshop on Intermediate Representation, Jan. 1995. Also appears in SIGPLAN Notices Volume 30,Number 4,1995.
[Sreedhar96] Sreedhar,V.C., Gao,G.R., and Lee,Y. A New Framework for Exhaustive and Incremental Data Flow Analysis Using DJ Graphs, In Proceeding of PLDI'96, p278- 290.
[Steven97] Steven S. Muchnick, Advanced Compiler Design and Implementation,1997.
[Tarjan72] Tarjan, Robert Endre, Depth First Search and Linear Graph Algorithm, SIAM J. of Computing, Vol. 1, No.2, p355-365,1972.
[Tarjan81] R. E. Tarjan, Fast Algorithm for Solving Path Problems, Journal of ACM Vol.28, No.3, p594-614, July 1981.
[Tji92] Steven W. K. Tjiang and John L. Hennessy, Sharlit—A Tool for Building Optimizers, In proceeding of PLDI'92, p82-93, 1992.
[Tjiang93] Steven Weng-Kiang Tjiang, Automatic Generation of Data Flow Analyzers: A Tool For Building Optimizers, Ph.D. dissertation of Stanford University, 1993.
[Ullm73] Ullman, Jeffrey D., Fast algorithm for the Elimination of Common Subexpressions, Acta Informatica, Vol. 2, Fasc. 3, p 191-213, July 1973.
[Wolfe94] Michael Wolfe, High Performance Compilers for Parallel Computing, 1994. http://www.parc.xerox.com/spl/proiects/sop/loc
[冯99] 冯晓兵，数据分布全局优化技术，中科院计算所博士论文，1999。
[胡98] 胡伟平，可扩展编译系统的关键技术研究，中科院计算所博士论文，1998。
[刘98] 刘强，考虑指针别名的过程间分析技术研究，中科院计算所博士论文，1998。
[黄95] 黄铠，高等计算机系统结构——并行性，可扩展性，可编程性，1995。
[汪99] 汪建平，HPF并行编译系统技术研究与对数据并行计算模型的探索，北京大学博士论文，1999。
[吴00] 吴承勇，指令级并行编译中的若干关键问题的研究，中科院计算所博士论文，2000。
[臧99] 臧斌宇，并行化编译系统AFT的构造，复旦大学博士论文，1999。
[Allen97] Allen L., Prop Language Reference Manual, Tech. Report, Courant Institute of Mathematical Sciences, 1997.
[Blume94] Blume B., Eigenmann R., Faign K., Grout J., Hoeflinger J., Padua D., Petersen P., Pottenger B., Raughwerger L., Tu P., Weatherford S., Polaris: The Next Generation in Parallelizing Compilers, Proceedings of the 7th Workshop on Languages and Compilers for Parallel Computing, August 1994.
[Burke90a] Michael G. Burke, An Interval-based Approach to Exhaustive and Incremental Interprocedural Data-Flow Analysis. ACM Transactions on Programming Languages and Systems, Vol. 12, No.3, p341-395, July 1990.
[Burke90i] Michael G. Burke and Barbara Gershon Ryder, A Critical Analysis of Incremental Iterative Data Flow Analysis Algorithm, In IEEE Transactions on Software Engineering, Vol. 16, No.7, July 1990.
[Callahan88] D. Callahan. The Program Summary Graph and Flow-Sensitive Interprocedural Data Flow Analysis. In proceeding of PLDI'88, June 1988.
[Canfora98] Gerardo Canfora and Aniello Cimitile, An Extensible System for Source Code Analysis. In IEEE Transactions on Software Engineering, Vol.24, No.9, September 1998.
[Carol188] M. D. Carroll and B. G. Ryder, Incremental Data Flow Analysis via Dominator and Attribute Updates, in Conference Record of the Fifteenth Annual ACM Symposium on Principles of Programming Languages, p274-184, Jan. 1988,.
[CCl99] 张兆庆，吴承勇，并行程序设计环境关键技术子项目计划书——通用编译基础设施，1999。
[Chaitin82] Chaitin G. J., Register Allocation and Spilling via Graph Coloring, In Proceeding of the ACM SIGPLAN Symposium on Compiler Construction,Boston, 1982.
[Charles92] Charles W. Krueger, Software Reuse, ACM Computing Surveys, Vol.24,No. 2, June 1992.
[Chen93] William Yu-wei Chen, Data Preload for Superscalar and VLIW Processors,Ph.D. Dissertation, UIUC,1993.
[Cooper84] K.Cooper and K.Kennedy, Efficient Computation of Flow Insensitive Interprocedure Summary Information, SIGPLAN Notices, vol.19, no.6,p247-258, June 1984.
[Cytron91] Ron Cytron, Jeanne Ferrante, Varry K.Rosen and Mark N.Wegman,Efficiently Computing Static Single Assignment Form and the Control Dependence Graph, ACM Transaction on Programming Languages and Systems, Vol.13, No4, p451-490, October 1991.
[Dev96] P. Devanbu, D. Rosenblum and A. Wolf. Generating Testing and Analysis Tools with Aria, ACM Transactions on Software Engineering and Methodology, vol. 5, p42-62, January 1996.
[Dirk93] Dirk G. and Harini S., Data Flow Equations for Explicitly Parallel Programs, Proceedings of the Fourth ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming, San Diego, California,May 1993.
[Farrow75] Farrow, Rodney, Ken Kennedy and Linda Zucconi. Graph Grammars and Global Program Flow Analysis, In Proceedings of the 17~(th) IEEE Symposium on Foundations of Computing Science, Houston, TX, Now.1975.
[FSF95] Free Software Foundation, GCC User Manual, 1995.
[Gordon97] Gordon S. Novak Jr, Software Reuse by Specialization of Generic Procedures through Views, IEEE Transactions on Software Engineering,Vol. 23,No. 7,July 1997.
[Hall93] M.W. Hall. FIAT: A Framework for Interprocedural Analysis and Transformation. In the proceeding of the 6~(th) international workshop of languages and compilers for parallel computing, Oregen, USA, August,LNCS 768,p522-545, 1993.
[Harrold97] Mary Jean Horrold, Aristotle: A System for Research on and Development of Program-Analysis-Based Tools,http://www.cis.ohio-state.edu/～harrold/organnon/dev1/code, 1997.
[Hecht75] M.S.Hecht and J.D.Ullman, A Simple Algorithm for Global Data-Flow Analysis Problems, SIAM J. Compt. 4, p519-532, December 1975.
[http:suif] http://suif.stanford.edu/ , SUIF Home Page.
[James 93] James C. Dehnert and Ross A. Towle, Compiling for the Cydra 5. In the Journal of Supercomputing, Vol. 7, 1993.
[Jaspal93] Jaspal Subholk, James M. Stichnoth, David R. O'Hallaron, Thomas Gross,Exploiting Task and Data Parallellism on a Multicomputer, Proceedings of the Fourth ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming, San Diego, California, May 1993.
[Johan96] Johan Janssen and Henk Corporal, Controlled Node Splitting, In the proceedings of the 6~(th) international conference of compiler construction,Sweden, April 1996.
[Kaldill73] Gary A. Kildall. A Unified Approach to Global Program Optimization, in proceedings of the 1~(st) Annual ACM Symposium on Principles of Programming Languages, p194-206, 1973.
[Kic96] Gregor Kiczales, Aspect-Oriented Programming, Position Paper from the Aspect-Oriented Programming Project, http://www.parc.xerox.xom/spl/projects/aop/loc
[Kuck81] Kuck. D.J., Kuhn. R.H., Padua.D.A., Leasure.B, and Wolfe.M.M,Dependence Graphs and Compiler Optimizations. In Proceedings of the 8~(th) Annual ACM Symposium on Principles of Programming Languages, New York,p207-218.
[Lam91] Lam.M, Rinard.M, Coarse-Grain Parallel Programming in Jade. In Proceedings of the Third ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Williamsburg, VA, April 1991.
[Landi93] W. Landi, B. G. Ryder and S. Zhang, Interprocedural Modification Side Effect Analysis with Pointer Aliasing, In SIGPLAN 93 Symposium on Programming Language Design and Implementation, p56-67, June 1993.
[Lee87] Lee.E.A, Messerschmitt.D.G, Static Scheduling of Synchronous Data Flow Programs for Digital Signal Processing, IEEE Transactions on Computers,Jan. 1987.
[LenT79] Lengauer, Thomas and Robert E. Tarjan. A Fast Algorithm for Finding Dominators in a Flow Graph, ACM TOPLAS, Vol, No.1, July 1979, p121-141.
[Lopes95] Cristina Videira Lopes, AP/S++: Case-study of a MOP for Purposes of Semantics, ACM Symposium on POPL'87.
[Lowney93] P.Geoffery Lowney, The Multiflow Trace Scheduling Compiler, In the Journal of Supercomputing, Vol. 7,1993.
[Mahlke96] Scott Alan Mahlke, Exploiting ILP In the Present of Conditional Branch,Ph.D. Dissertation, UIUC, 1996.
[Marlowe90] T.J.Marlowe and B.G.Ryder, An Efficient Hybrid Algorithm for Incremental Data Flow Analysis, in Conference Record of the Seventeenth Annual ACM Symposium on Principle of Programming Languages,p184-196, Jan. 1990.
[Mary96] Mary W. Hall, Seema hiranandani, Ken Kennedy, Chaw-Wen Tseng: Interprocedure Compilation on FortranD, Journal of Parallel and Distributed Computing 38(2), p114-129, 1996.
[Maydan92] Dror Eliezer Maydan, Accurate Analysis of Array Reference, Ph.D. Dissertation, Stanford university.
[NCI97] The National Compiler Infrastructure Project,http://www.cs.virginia.edu/users/novak
[Obri95] O'brien K. et al, XIL and YIL: The Intermediate Language of TOBEY,ACM SIGPLAN Workshop on Intermediate Representation, CA, Jan. 1995.
[Pande91] H.D.Pande and William Landi. Interprocedural Def-Use Associations in C Program, In Proceeding of Symposium on Testing, Analysis and Verification,p139-153, 1991.
[PCF91] Parallel Computing Forum. PCF Parallel FORTRAN Extensions. FORTRAN Forum, September 1991.
[Pollock89] L.Pollock and M.Soffa, An Incremental Version of Iterative Data Flow Analysis ", IEEE Transactions on Software Engineering, Vol.15, no.12,Dec. 1989.
[Proe92] Todd A. Proebsting, Code Generation Techniques, Ph.D. thesis,University of Wisconsin, 1992.
[Rau93] B.Ramakrishna Rau and Joseph A. Fisher, Instruction-Level Parallel Processing: Histroy, Overview and Perspective. In the Journal of supercomputing, Vol. 7,1993.
[Ryder88] Barbara G. Ryder and Marven C. Paull, Incremental Data-Flow Analysis Algorithms, In ACM Transactions on Programming Languages and Systems, Vol.10, No.1, p1-50, January 1988.
[SCG94] Stanford Compiler Group, the SUIF Library, 1994.
[Shar80] Sharir, Micha. Structural Analysis : A New Approach to Flow Analysis in Optimizing Compilers, Computer Languages, p141-153, Vol.5,1980.
[Sreedhar95] Sreedhar, V.C., Gao,G.R., and Lee,Y. Incremental Computation of Dominator trees. In ACM SIGPLAN Workshop on Intermediate Representation, Jan. 1995. Also appears in SIGPLAN Notices Volume 30,Number 4,1995.
[Sreedhar96] Sreedhar,V.C., Gao,G.R., and Lee,Y. A New Framework for Exhaustive and Incremental Data Flow Analysis Using DJ Graphs, In Proceeding of PLDI'96, p278- 290.
[Steven97] Steven S. Muchnick, Advanced Compiler Design and Implementation,1997.
[Tarjan72] Tarjan, Robert Endre, Depth First Search and Linear Graph Algorithm, SIAM J. of Computing, Vol. 1, No.2, p355-365,1972.
[Tarjan81] R. E. Tarjan, Fast Algorithm for Solving Path Problems, Journal of ACM Vol.28, No.3, p594-614, July 1981.
[Tji92] Steven W. K. Tjiang and John L. Hennessy, Sharlit—A Tool for Building Optimizers, In proceeding of PLDI'92, p82-93, 1992.
[Tjiang93] Steven Weng-Kiang Tjiang, Automatic Generation of Data Flow Analyzers: A Tool For Building Optimizers, Ph.D. dissertation of Stanford University, 1993.
[Ullm73] Ullman, Jeffrey D., Fast algorithm for the Elimination of Common Subexpressions, Acta Informatica, Vol. 2, Fasc. 3, p 191-213, July 1973.
[Wolfe94] Michael Wolfe, High Performance Compilers for Parallel Computing, 1994. http://www.parc.xerox.com/spl/proiects/sop/loc
[冯99] 冯晓兵，数据分布全局优化技术，中科院计算所博士论文，1999。
[胡98] 胡伟平，可扩展编译系统的关键技术研究，中科院计算所博士论文，1998。
[刘98] 刘强，考虑指针别名的过程间分析技术研究，中科院计算所博士论文，1998。
[黄95] 黄铠，高等计算机系统结构——并行性，可扩展性，可编程性，1995。
[汪99] 汪建平，HPF并行编译系统技术研究与对数据并行计算模型的探索，北京大学博士论文，1999。
[吴00] 吴承勇，指令级并行编译中的若干关键问题的研究，中科院计算所博士论文，2000。
[臧99] 臧斌宇，并行化编译系统AFT的构造，复旦大学博士论文，1999。