考虑指针别名的过程间分析技术研究
摘要
指针分析是近年来国际上编译技术领域中的一个研究热点。C语言程序中指针的广泛使用严重地影响了数据流分析的精确程度，从而严重地影响了程序优化和程序变换的效果。近年来，新兴体系结构的设计更加依赖于编译技术的支持，指针对代码效率的影响也更加严重。指针分析从而成为现代编译技术中的一个重要组成部分。
与传统的分析方法相比，本文采用了一个新的过程间策略来处理指针问题。我们的过程间策略基于我们对C语言中名字空间的抽象—参数化名字空间。由于参数化名字空间中程序上下文的数目是有限的，因而我们以此为基础，发展了一个上下文敏感的过程间指针分析算法。该算法一方面是上下文敏感的，另一方面由于有效地利用了参数化空间内的启发式因素，因而是高效的。
基于参数化空间的抽象和指针分析的结果，我们开发了一个过程间分析的统一框架，该框架将基本的过程间问题(指针分析、调用图求解、过程间MOD分析和过程间到达-定值分析)有机地结合在一起，从而对C语言过程间分析问题的有效解决作了有意义的实践。
本文的工作结果已经应用到一个实际的SIMD芯片的优化／并行化编译器中。对该编译器的使用和测试证明了我们的过程间分析框架是实际可用的，这使本文的工作超出了纯粹的学术研究的范畴。
Pointer analysis is a field of active research in recent years in compiler technology. The extensive use of pointers in languages such as C greatly affects the accuracy of data flow analysis which further affects the result of program optimization and program transformation. As the emerging computer architecture design requires more supports from compilers to exploit the ample hardware resources, the affection of pointer in the object code efficiency is more severe. Pointer analysis is hence becoming one of the most important components in modern compiler technology.
Comparing with the traditional analysis method, this paper adopts a new inter-procedural strategy to handle pointers. Our inter-procedural strategy is based on the abstraction of C's parameterized name space. We developed a context-sensitive inter-procedural pointer analysis algorithm because the program contexts are limit in the parameterized name space. One one hand, the algorithm is context-sensitive and provides very precise result, on the other hand, the algorithm is very efficient because we carefully apply heuristic techniques.
Based on the result of pointer analysis and the abstraction of parameterized name space, we developed a unified inter-procedural framework which integrated the basic inter-procedural problems include pointer analysis, call graph construction, inter-procedural MOD analysis and Reach Definition analysis construction. This framework provides a promising efficient method for solving C's inter-procedural problems.
The result of this research has been applied to a real optimizing and parallelizing compiler for a SIMD chip. The benchmarking and actual use of this compiler proves that our inter-procedural analysis is practical and efficient. This makes the work in this paper beyond pure academic research.
与传统的分析方法相比，本文采用了一个新的过程间策略来处理指针问题。我们的过程间策略基于我们对C语言中名字空间的抽象—参数化名字空间。由于参数化名字空间中程序上下文的数目是有限的，因而我们以此为基础，发展了一个上下文敏感的过程间指针分析算法。该算法一方面是上下文敏感的，另一方面由于有效地利用了参数化空间内的启发式因素，因而是高效的。
基于参数化空间的抽象和指针分析的结果，我们开发了一个过程间分析的统一框架，该框架将基本的过程间问题(指针分析、调用图求解、过程间MOD分析和过程间到达-定值分析)有机地结合在一起，从而对C语言过程间分析问题的有效解决作了有意义的实践。
本文的工作结果已经应用到一个实际的SIMD芯片的优化／并行化编译器中。对该编译器的使用和测试证明了我们的过程间分析框架是实际可用的，这使本文的工作超出了纯粹的学术研究的范畴。
Pointer analysis is a field of active research in recent years in compiler technology. The extensive use of pointers in languages such as C greatly affects the accuracy of data flow analysis which further affects the result of program optimization and program transformation. As the emerging computer architecture design requires more supports from compilers to exploit the ample hardware resources, the affection of pointer in the object code efficiency is more severe. Pointer analysis is hence becoming one of the most important components in modern compiler technology.
Comparing with the traditional analysis method, this paper adopts a new inter-procedural strategy to handle pointers. Our inter-procedural strategy is based on the abstraction of C's parameterized name space. We developed a context-sensitive inter-procedural pointer analysis algorithm because the program contexts are limit in the parameterized name space. One one hand, the algorithm is context-sensitive and provides very precise result, on the other hand, the algorithm is very efficient because we carefully apply heuristic techniques.
Based on the result of pointer analysis and the abstraction of parameterized name space, we developed a unified inter-procedural framework which integrated the basic inter-procedural problems include pointer analysis, call graph construction, inter-procedural MOD analysis and Reach Definition analysis construction. This framework provides a promising efficient method for solving C's inter-procedural problems.
The result of this research has been applied to a real optimizing and parallelizing compiler for a SIMD chip. The benchmarking and actual use of this compiler proves that our inter-procedural analysis is practical and efficient. This makes the work in this paper beyond pure academic research.
引文
[1] Alfred V. Aho, Ravi Sethi and Jeffrey D. Ullman, Compilers- Principles, Techniques and Tools. Addison-Wesley, 1986
[2] Hans Zima and Barbara Chapman. Supercompilers for Vector and Parallel Computers. Addison-Wesleym 1990
[3] M.J. Wolfe, Optimizing Supercompilers for Supercomputers, Pitman, London and MIT press, 1989
[4] Steven S. Muchnick, Advanced Compiler Design Implementation, Morgan Kaufmann, 1997
[5] D. Patternson et al. "A VLSI RISC", Computer, Sep. 1982, p8-21
[6] John L. Hennessy, David A. Patterns, "Computer Architecture: A quatitative approach", Morgan Kaufmann, 1996
[7] Kai. Huang, "Advanced Computer Architecture- Parallelism Scalarbility Programmingbility", McGraw-Hill, 1993
[8] M. Slater, " What is RISC? ", IEEE Micro, Jun. 1990, P95-96
[9] David W. Wall, Limits of instruction-level parallelism, In proceddings of the Fourth International Conference on Architecture Support for Programming languages and Operating Systems, P176-188, April 1991
[10] 李三立等，“RISC单发射与多发射体系结构”，清华大学出版社，1993
[11] 康宝祥等，“RISC体系结构及其实现技术”，科学出版社，1996
[12] W. Weihl, Interprocedural data flow analysis in the presence of pointers, procedure variables and label variables. In Conference Record of the Seventh Annual ACM Symposium on Principles of Programming Languages, p83-94, Jan. 1980.
[13] A. L. Chow and A. Rudmik. The design of a data flow analyzer. ACM SIGPLAN. SIGPLAN Notices, 17(6), June 1982
[14] D. S. Coutant. Retargetable high-level alias analysis. In Conference Record of the Thirteenth Annual ACM Symposium on Principles of Programming Languages, p100-118.
[15] J. D. Choi, M. Burke, and P. Carini. Efficient Flow-Sensitive Interprocedural Computation of Pointer-Induced Aliases and Side Effects. In Proceedings of the 20th Annual ACM Symposium on Principles of Programming Languages, pages 232-245, Jan. 1993.
[16] W. Landi and B. G. Ryder. A safe approximate algorithm for interprocedural pointer aliasing. In Proceedings of the SIGPLAN 92 Symposium on Programming Language Design and Implementation, p235-248, June 1992.
[17] W. A. Landi. Interprocedural Aliasing in the Presence of Pointers. PhD thesis, Rutgers University, 1992.
[18] T. J. Marlowe, W. A. Landi, B. G. Ryder, J. D. Choi, M. G. Burke, and P. Carini. Pointer-Induced Aliasing: A Clarification. ACM SIGPLAN Notices, 28(9):67-70, Sept. 1993.
[19] M. Emami, R. Ghiya, and L. J. Hendren. Context-Sensitive Interprocedural Points-to Analysis in the Presence of Function Pointers. In Proceedings of the ACM SIGPLAN'94 Conference on Programming Language Design and Implementation, pages 242-256, June 1994.
[20] M.Emami. A Practical Interprocedual Alias Analysis for an Optimizing/Parallelizing C Compiler. Master's thesis, School of Computer Science, McGill University, Aug. 1993.
[21] A. Deutsch. Interprocedural May-Alias Analysis for Pointers: beyond klimiting. In Proceedings of the A CM SIGPLAN'94 Conference on Programming Language Design and Implementation, pages 230-241, June 1994.
[22] Erik Ruf, Context Insensitive Alias Analysis Reconsidered. In Proceedings of the ACM SIGPLAN'95 Conference on Programming Language Design and Implementation, pages 13-22, 1995.
[23] R.P. Wilson and M. S. Lam, Efficient Context-Sensitive Pointer Analysis for C Programs. In Proceedings of the ACM SIGPLAN'95 Conference on Programming Language Design and Implementation, pages 1-12, 1995.
[24] D. R. Chase, M. Wegman and F. K. Zadeck. Analysis of pointers and structrues. In Proceedings of the SIGPLAN 90 Conference on Programming Language Design and Implementation, p296-310, June 1990.
[25] A. Deutsch. On determining lifetime and aliasing of dynamically allocated data in higher-order functional specifications. In Conference Record of the Seventeenth Annual ACM Symposium on Principles of Programming Languages, p157-168, Jan. 1990.
[26] A. Deutsch. A storeless model of aliasing and its abstractions using finite representations of right-regular equivalence relations. In Proceedings of the IEEE 1992 International Conference on Computer Languages, p2-13, Apr. 1992.
[27] R. Ghiya. Practical techniques for heap analysis. ACAPS Technical Note 46, School of Computer Science, McGill University, May 1993.
[28] L. J. Hendren and A. Nicolau. Parallelizing programs with recursive data structures. IEEE Transactions on Parallel and Distributed Systems, 1 (1): 35-47, Jan. 1990.
[29] J. M. Barth. An interprocedural data flow analysis algorithm.In Conference Record of the Sixth Annual ACM Symposium on Principles of Programming Languages, p119-131, Jan.1977.
[30] K. Cooper and K. Kennedy. Efficient computation of flow insensitive interprocedural summary information. In Proceedings of the SIGPLAN 84 Symposium on Compiler Construction, p247-258, June 1984.
[31] D. Callahan. The Program summary graph and flow-sensitive interprocedural data flow analysis. PLDI, June 1988.
[32] F. E. Allen. Interprocedural data flow analysis. In Proceedings of 1974 IFIP Congress, P398-402
[33] R. Ghiya. Interprocedural analysis in the presence of function pointers. ACAPS Technical Memo 62. School of Computer Science, McGill University, Dec. 1992.
[34] M.W. Hall, Managing Interprocedural Optimization, Ph D. thesis, April.1991, Rice University.
[35] B. Sridharan. An analysis framework for the McCAT compiler. Master's thesis, School of Computer Science, McGill University, Sep. 1992.
[36] T. C. Spillman. Exposing side-effects in a PL/I optimizing compiler. In Proceedings of the 1971 IEIPS Congress. North Holland Publishing Co., Amesterdam, 1971, p56-60.
[37] J.Banning, An efficient way to fred the side effect of procedure calls and the aliases of variables. In Conference Record of the Sixth Annual A CM Symposium on Principles of Programming Languages, pages 29-41, January 1979.
[38] K. Cooper and K. Kennedy. Interprocedural side-effect analysis in linear time. In proceedings of the SIGPLAN'88 Conference on Programming Language Design and Implementation, pages 57-66, June 1988.
[39] 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.
[40] H. D. Pande. Interprocedural Def-Usc Associations in C Program. ACM, P139-153.
[41] B. G. Ryder. Constructing the call graph of a program. IEEE Transactions on Software Engineering, SE-5(3): 216-226, May 1979.
[42] D. Callahan, A. Carle, M. W. Hall and K. Kennedy. Constructing the procedure call multigraph.IEEE Transactions on Software Engineering 16, 4, 1M83-487, Apr. 1990.
[43] M. W. Hall and K. Kennedy. Efficient call graph analysis. ACM Letters on Programming Languages and Systems, 1(3), p227-242, Sep. 1992.
[44] A. Lakhotia. Constructing call multigraphs using dependence graphs. In Conference Record of the Twentieth Annual ACM Symposium on Principles of Programming Languages, p273-284, Jan. 1993.
[45] L. J. Hendren, G. R. Gao and V. C. Sreedhar. ALPHA: A family of structured intermediate representations for a parallelizing C compiler. ACAPS Technical Memo 49, School of Computer Science, MeGill University, Nov. 1992.
[46] L. J. Hendren, C. Donawa, M. Emami, G. R. Gao, Justiani and B. Sridharan. Designing the McCAT compiler based on a family of structured intermediate representations. In Conference Record of the Fifth International Workshop on Languages and Compilers for Parallel Computing Science, p406-420. Spinger Verlag, 1993.
[47] S. Horwitz, P. Pfeiffer and T. Reps. Dependence analysis for pointer variables. In Proceedings of the SIGPLAN '89 Symposium on Programming Language Design and Implementation, p28-40, June 1989.
[48] E. W. Myers. A precise inter-procedural data flow algorithm. In Conference Record of the Nighth Annual ACM Symposium on Principles of Programming Languages, p219-230, Jan. 1981.
[49] A. Neirynck, P. Panangaden and A. J. Demers. Effect analysis in higher-order languages. International Journal of Parallel Programming, 18(1): 1-37, 1989.
[50] Zhang Zhaoqing, Gao Nianshu, Qiao Ruliang, and Liu Qiang, " Advanced Compilation Techniques Used in PORT System", I-SPAN'96, p460-465.
[51] Fang Xianhong, Zhang Zhaoqing, and Qiao Ruliang, " Interprocedural Constant Range Propagation and Alias Analysis by Mutiple version Method", Journal of Computer Science and Technology (English version)
[2] Hans Zima and Barbara Chapman. Supercompilers for Vector and Parallel Computers. Addison-Wesleym 1990
[3] M.J. Wolfe, Optimizing Supercompilers for Supercomputers, Pitman, London and MIT press, 1989
[4] Steven S. Muchnick, Advanced Compiler Design Implementation, Morgan Kaufmann, 1997
[5] D. Patternson et al. "A VLSI RISC", Computer, Sep. 1982, p8-21
[6] John L. Hennessy, David A. Patterns, "Computer Architecture: A quatitative approach", Morgan Kaufmann, 1996
[7] Kai. Huang, "Advanced Computer Architecture- Parallelism Scalarbility Programmingbility", McGraw-Hill, 1993
[8] M. Slater, " What is RISC? ", IEEE Micro, Jun. 1990, P95-96
[9] David W. Wall, Limits of instruction-level parallelism, In proceddings of the Fourth International Conference on Architecture Support for Programming languages and Operating Systems, P176-188, April 1991
[10] 李三立等，“RISC单发射与多发射体系结构”，清华大学出版社，1993
[11] 康宝祥等，“RISC体系结构及其实现技术”，科学出版社，1996
[12] W. Weihl, Interprocedural data flow analysis in the presence of pointers, procedure variables and label variables. In Conference Record of the Seventh Annual ACM Symposium on Principles of Programming Languages, p83-94, Jan. 1980.
[13] A. L. Chow and A. Rudmik. The design of a data flow analyzer. ACM SIGPLAN. SIGPLAN Notices, 17(6), June 1982
[14] D. S. Coutant. Retargetable high-level alias analysis. In Conference Record of the Thirteenth Annual ACM Symposium on Principles of Programming Languages, p100-118.
[15] J. D. Choi, M. Burke, and P. Carini. Efficient Flow-Sensitive Interprocedural Computation of Pointer-Induced Aliases and Side Effects. In Proceedings of the 20th Annual ACM Symposium on Principles of Programming Languages, pages 232-245, Jan. 1993.
[16] W. Landi and B. G. Ryder. A safe approximate algorithm for interprocedural pointer aliasing. In Proceedings of the SIGPLAN 92 Symposium on Programming Language Design and Implementation, p235-248, June 1992.
[17] W. A. Landi. Interprocedural Aliasing in the Presence of Pointers. PhD thesis, Rutgers University, 1992.
[18] T. J. Marlowe, W. A. Landi, B. G. Ryder, J. D. Choi, M. G. Burke, and P. Carini. Pointer-Induced Aliasing: A Clarification. ACM SIGPLAN Notices, 28(9):67-70, Sept. 1993.
[19] M. Emami, R. Ghiya, and L. J. Hendren. Context-Sensitive Interprocedural Points-to Analysis in the Presence of Function Pointers. In Proceedings of the ACM SIGPLAN'94 Conference on Programming Language Design and Implementation, pages 242-256, June 1994.
[20] M.Emami. A Practical Interprocedual Alias Analysis for an Optimizing/Parallelizing C Compiler. Master's thesis, School of Computer Science, McGill University, Aug. 1993.
[21] A. Deutsch. Interprocedural May-Alias Analysis for Pointers: beyond klimiting. In Proceedings of the A CM SIGPLAN'94 Conference on Programming Language Design and Implementation, pages 230-241, June 1994.
[22] Erik Ruf, Context Insensitive Alias Analysis Reconsidered. In Proceedings of the ACM SIGPLAN'95 Conference on Programming Language Design and Implementation, pages 13-22, 1995.
[23] R.P. Wilson and M. S. Lam, Efficient Context-Sensitive Pointer Analysis for C Programs. In Proceedings of the ACM SIGPLAN'95 Conference on Programming Language Design and Implementation, pages 1-12, 1995.
[24] D. R. Chase, M. Wegman and F. K. Zadeck. Analysis of pointers and structrues. In Proceedings of the SIGPLAN 90 Conference on Programming Language Design and Implementation, p296-310, June 1990.
[25] A. Deutsch. On determining lifetime and aliasing of dynamically allocated data in higher-order functional specifications. In Conference Record of the Seventeenth Annual ACM Symposium on Principles of Programming Languages, p157-168, Jan. 1990.
[26] A. Deutsch. A storeless model of aliasing and its abstractions using finite representations of right-regular equivalence relations. In Proceedings of the IEEE 1992 International Conference on Computer Languages, p2-13, Apr. 1992.
[27] R. Ghiya. Practical techniques for heap analysis. ACAPS Technical Note 46, School of Computer Science, McGill University, May 1993.
[28] L. J. Hendren and A. Nicolau. Parallelizing programs with recursive data structures. IEEE Transactions on Parallel and Distributed Systems, 1 (1): 35-47, Jan. 1990.
[29] J. M. Barth. An interprocedural data flow analysis algorithm.In Conference Record of the Sixth Annual ACM Symposium on Principles of Programming Languages, p119-131, Jan.1977.
[30] K. Cooper and K. Kennedy. Efficient computation of flow insensitive interprocedural summary information. In Proceedings of the SIGPLAN 84 Symposium on Compiler Construction, p247-258, June 1984.
[31] D. Callahan. The Program summary graph and flow-sensitive interprocedural data flow analysis. PLDI, June 1988.
[32] F. E. Allen. Interprocedural data flow analysis. In Proceedings of 1974 IFIP Congress, P398-402
[33] R. Ghiya. Interprocedural analysis in the presence of function pointers. ACAPS Technical Memo 62. School of Computer Science, McGill University, Dec. 1992.
[34] M.W. Hall, Managing Interprocedural Optimization, Ph D. thesis, April.1991, Rice University.
[35] B. Sridharan. An analysis framework for the McCAT compiler. Master's thesis, School of Computer Science, McGill University, Sep. 1992.
[36] T. C. Spillman. Exposing side-effects in a PL/I optimizing compiler. In Proceedings of the 1971 IEIPS Congress. North Holland Publishing Co., Amesterdam, 1971, p56-60.
[37] J.Banning, An efficient way to fred the side effect of procedure calls and the aliases of variables. In Conference Record of the Sixth Annual A CM Symposium on Principles of Programming Languages, pages 29-41, January 1979.
[38] K. Cooper and K. Kennedy. Interprocedural side-effect analysis in linear time. In proceedings of the SIGPLAN'88 Conference on Programming Language Design and Implementation, pages 57-66, June 1988.
[39] 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.
[40] H. D. Pande. Interprocedural Def-Usc Associations in C Program. ACM, P139-153.
[41] B. G. Ryder. Constructing the call graph of a program. IEEE Transactions on Software Engineering, SE-5(3): 216-226, May 1979.
[42] D. Callahan, A. Carle, M. W. Hall and K. Kennedy. Constructing the procedure call multigraph.IEEE Transactions on Software Engineering 16, 4, 1M83-487, Apr. 1990.
[43] M. W. Hall and K. Kennedy. Efficient call graph analysis. ACM Letters on Programming Languages and Systems, 1(3), p227-242, Sep. 1992.
[44] A. Lakhotia. Constructing call multigraphs using dependence graphs. In Conference Record of the Twentieth Annual ACM Symposium on Principles of Programming Languages, p273-284, Jan. 1993.
[45] L. J. Hendren, G. R. Gao and V. C. Sreedhar. ALPHA: A family of structured intermediate representations for a parallelizing C compiler. ACAPS Technical Memo 49, School of Computer Science, MeGill University, Nov. 1992.
[46] L. J. Hendren, C. Donawa, M. Emami, G. R. Gao, Justiani and B. Sridharan. Designing the McCAT compiler based on a family of structured intermediate representations. In Conference Record of the Fifth International Workshop on Languages and Compilers for Parallel Computing Science, p406-420. Spinger Verlag, 1993.
[47] S. Horwitz, P. Pfeiffer and T. Reps. Dependence analysis for pointer variables. In Proceedings of the SIGPLAN '89 Symposium on Programming Language Design and Implementation, p28-40, June 1989.
[48] E. W. Myers. A precise inter-procedural data flow algorithm. In Conference Record of the Nighth Annual ACM Symposium on Principles of Programming Languages, p219-230, Jan. 1981.
[49] A. Neirynck, P. Panangaden and A. J. Demers. Effect analysis in higher-order languages. International Journal of Parallel Programming, 18(1): 1-37, 1989.
[50] Zhang Zhaoqing, Gao Nianshu, Qiao Ruliang, and Liu Qiang, " Advanced Compilation Techniques Used in PORT System", I-SPAN'96, p460-465.
[51] Fang Xianhong, Zhang Zhaoqing, and Qiao Ruliang, " Interprocedural Constant Range Propagation and Alias Analysis by Mutiple version Method", Journal of Computer Science and Technology (English version)