快速程序流分析方法的研究与应用
|
摘要
衡量系统实时性的最重要的参数是任务的最坏情况执行时间(Worst Case ExceutionTime,WCET)。WCET分析的目的在于得到任务执行时间的上界约束,这需要综合考虑系统的软硬件特征。由于WCET的动态测量方法不能保证估计结果是安全的,所以现在一般学者都致力于静态分析方法的研究。随着软件规模及其复杂性的不断增长,使得快速地获得WCET估计值更加困难。
在WCET程序流分析中,本文依据C的语言特点,给出了从抽象语法树到程序控制流图的构造,由程序控制流图到静态单赋值形式的转变。依据静态单赋值形式的控制流图得出数据依赖和数据依赖关系,然后就可以构造程序依赖图。对程序依赖图的扩展得到系统依赖图,利用图的可达性算法来对程序进行切片。本文还给出了一种不是基于依赖图的简单程序切片算法,该算法适合对程序中所有条件语句计算切片。经过程序切片后,采用抽象解释来自动导出程序流中循环迭代界限、不可行路径等约束信息,避免了手工标注。
依据上述给出的程序流分析方法,本文给出了程序流分析工具的设计架构。实验结果表明,利用静态单赋值、程序切片、抽象解释理论进行WCET分析中的程序流信息分析,能够快速且有效地给出程序流事实。本文在图论、编译优化技术、程序切片技术的基础上,探讨了WCET流分析工具的整体实现策略,是对WCET流分析方法研究的一种尝试。
The most important parameter judging the system is the Worst-Case Execution Time (WCET). The purpose of WCET estimation is getting the right limit of the certain task, which should consider the software and hardware configuration comprehensively. For the dynamic measure method of WCET can not pledge the safety of the estimation, most researchers apply themselves to analysis WCET by static method. With the development of the scale and complication of program, it makes fast WCET estimation become much hard.
In program flow analysis of WCET, this paper gives definition and its presentation based on the feature of the C programming language with algorithms for constructing control flow graph from abstract syntax tree, static single assignment form can be made from control flow graph, and then can get data dependency, control dependency and program dependency graph. System dependency graph can be extended from program dependency graph, and then the reachable graphic algorithm is used to compute the program slicing. We introduce a simple program slicing algorithm based-on data dependency, which is suitable for slicing all conditions. After program slicing, it uses abstract interpretation to automatically get the constraints of program flow, thereby avoiding the need for manual annotations.
We introduce a method of fast and automatic program flow analysis based on static single assignment, program slicing, abstract interpretation in the program flow analysis of WCET. To compare with former methods, the one we mentioned will get the constraints of program flow fact faster and effectively, which is applicable to the WCET flow analysis of the program with complicated software configuration. Based on graph theory, compiler optimization and program slicing, this paper, which is a trial for doing research on WCET program flow analysis, have discussed an integral strategy for implementing a tool in WCET program flow analysis.
在WCET程序流分析中,本文依据C的语言特点,给出了从抽象语法树到程序控制流图的构造,由程序控制流图到静态单赋值形式的转变。依据静态单赋值形式的控制流图得出数据依赖和数据依赖关系,然后就可以构造程序依赖图。对程序依赖图的扩展得到系统依赖图,利用图的可达性算法来对程序进行切片。本文还给出了一种不是基于依赖图的简单程序切片算法,该算法适合对程序中所有条件语句计算切片。经过程序切片后,采用抽象解释来自动导出程序流中循环迭代界限、不可行路径等约束信息,避免了手工标注。
依据上述给出的程序流分析方法,本文给出了程序流分析工具的设计架构。实验结果表明,利用静态单赋值、程序切片、抽象解释理论进行WCET分析中的程序流信息分析,能够快速且有效地给出程序流事实。本文在图论、编译优化技术、程序切片技术的基础上,探讨了WCET流分析工具的整体实现策略,是对WCET流分析方法研究的一种尝试。
The most important parameter judging the system is the Worst-Case Execution Time (WCET). The purpose of WCET estimation is getting the right limit of the certain task, which should consider the software and hardware configuration comprehensively. For the dynamic measure method of WCET can not pledge the safety of the estimation, most researchers apply themselves to analysis WCET by static method. With the development of the scale and complication of program, it makes fast WCET estimation become much hard.
In program flow analysis of WCET, this paper gives definition and its presentation based on the feature of the C programming language with algorithms for constructing control flow graph from abstract syntax tree, static single assignment form can be made from control flow graph, and then can get data dependency, control dependency and program dependency graph. System dependency graph can be extended from program dependency graph, and then the reachable graphic algorithm is used to compute the program slicing. We introduce a simple program slicing algorithm based-on data dependency, which is suitable for slicing all conditions. After program slicing, it uses abstract interpretation to automatically get the constraints of program flow, thereby avoiding the need for manual annotations.
We introduce a method of fast and automatic program flow analysis based on static single assignment, program slicing, abstract interpretation in the program flow analysis of WCET. To compare with former methods, the one we mentioned will get the constraints of program flow fact faster and effectively, which is applicable to the WCET flow analysis of the program with complicated software configuration. Based on graph theory, compiler optimization and program slicing, this paper, which is a trial for doing research on WCET program flow analysis, have discussed an integral strategy for implementing a tool in WCET program flow analysis.
引文
[1]J.Ganssle.Really real-time systems.In Proc.Embedded Systems Conference San Francisco 2001,April 2001.
[2]E.Kligerman,A.Stoyenko.Real-Time Euclid:A language for reliable real-time systems.IEEE Transactions on Software Engineering.1986,12(9):941-949.
[3]P.Puschner,C.Koza.Calculating the maximum execution time of real-time program.Real-Time Systems.1989,1(2):159-176.
[4]Raimund Kirner,Peter Puschner.Transformation of Path Information for WCET Analysis during Compilation.Proceedings of the 13th Euromicro International Conference on Real-Time Systems,2001(6):29-36.
[5]Raimund Kirner,Peter Puschner.Supporting Control-Dependent Execution Time on WCET Calculation.Proceedings of the WCET2OOO(Deutscbsprachige WCET Tagung,Paderborn,Germany).C-Lab,Paderborn,2000(10).
[6]Peter Puschner.Worst-Case Execution Time Analysis at Low Cost.Control Engineer Practic.1998(6):129-135.
[7]Chang Yun Park.Predicting Deterministic Execution Times of Real-Time Programs.PhD.Thesis,University of Washington,Seattle 98195,1992(8).
[8]Yau Tsun Steven Li,Sharad Malik.Performance Analysis of Embedded Software Using Implicit Path Enumeration.Proceedings of the 32nd ACM/IEEE Design Automation Conference,1995(6):456-461.
[9]Sung-Soo Lim,Young Hyun Bae,Gyu Tae Jang et al.An accurate worst case timing analysis technique for RISC processors.Proceedings of the 15th IEEE Real-Time Systems Symposium.1994(12):97-108.
[10]George S.Avrunin,James C.Corbett,Laura K.Dillon et al.Automated derivation of time bounds in uniprocessor concurrent systems,IEEE Transactions on Software Engineering,1994,20(9):708-719.
[11]J.Engblom,A.Ermedahl,M.Sjodin,et al.Towards industry-strength worst case execution time analysis[R].Advanced Software technology Center(ASTEC),Technical Report:ASTEC 99/02,1999.
[12]F.Stappert,P.Altenbernd.Complete worst-case execution time analysis of straight-line hard real-time programs.Journal of Systems Architecture,vol.46,2000:339-335.
[13]T.Lundqvist,P.Stensrom.Integrating path and timing analysis using instruction-level simulation techniques[C],The SIGPLAX Workshop on Languages,Compilers and Tools for Embedded Systems(LCTES' 98),Montreal,Canada,1998.
[14] C. Healy, R.Arnold, F.Mueller, et al. bounding pipeline and instruction cache performance[J]. IEEE Trans. On computers, 1999, 48(1):53-70.
[15] A. Colin, I. Puaut. A modular and retargetable framework for tree-based WCET analysis[C].The 13th Euromicro Conf. on Real-Time Systems(ECRTS' 01), Delft, the Netherlands,2001.
[16] Sung-Soo Lim, Young Hyun Bae, Gyu Tae Jang, et al. An accurate worst case timing analysis for RISC processors[C]. The 15th IEEE Real-Time Systems Symposium, San Juan, Puerto Rico, 1994.
[17] Lapkowski C., Hendren L J. Extended SSA Numbering: Introducing SSA Properties to Languages with Multi-level Pointers. ACAPS Technical Memo 102, School of Computer Science, McGill University, Mont&J, Canada, 1996-04
[18] Ferrante J, Ottenstein KJ, Warren J D. The program dependence graph and its use in optimization[J]. ACM Transactions on Programming Languages and Systems, 1987,9(3) :319 -349.
[19] Cousot P., Cousot R. Abstract Interpretation:A Unified Model for Static Analysis of Programs by Construction or Approximation of Fixpoints[C]. Proceedings of the 4th ACM Symposium on Principles of Programming Languages, Los Angeles, 1977:238-252.
[20] Tom R. Halfhill. Embedded Market Breaks New Ground. Microprocessor Report, January 17,2000.
[21] P. Puschner, A. Burns. Guest Editorial: A Review of Worst-Case Execution-Time Analysis,Real-Time Systems, May 2000, 18(2-3):115-128.
[22] Markus Lindgren.Measurement and Simulation based Techniques for Real-time Systems Analysis. Sweden: University Printers, Uppsala University, 2000.
[23] T. Lengauer and R. E. Tarjan. A fast algorithm for finding dominators in a flowgraph. ACM Transactions on Programming Languages and Systems, 1979, 7(1):115-120.
[24] Weiser M. Program slicing, IEEE Trans. on Software Engineering, 1984, 10(4):353-357.
[25] Christon Steindl. Program Slicing for Object-Oriented Programming Languages, Ph. D Thesis, 1999.
[26] Frank Tip. Generation of Program Analysis Tools, PhD thesis, University of Amsterdam,1995.
[27] K. J. Ottenstein and L. M. Ottenstein. The Program Dependence Graph in a Software Development Environment. In Proc. ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, 1984, 19(5):177-184.
[28] S. Horwitz, T. Reps, and D. Binkley. Interprocedural slicing using dependence graphs. ACM Transactions on Programming Languages and Systems, 1990, 12(1):26—60.
[29]William H.Harrison.Compiler Analysis of the Value Ranges for Variables[A].tEEE Trans.on Software Engineering,1977,3(3):243-250.
[30]姬孟洛.实时系统最差情况执行时间分析的研究:(博士学位论文).长沙:国防科学技术大学,2006.
[31]F.Nielson,H.R.Nielson,and C.Hankin.Principles of Program Analysis,2nd edition.Springer,2005.ISBN 3-540-65410-0.
[32]Raimund Kirner.The Programming Language wcetC.Tchnical report,Technische Universit(a|")t Wien,Institut f(u|")r Technische Informatik,Treitlstr.1-3/182-1,1040Vienna,Austria,2002.
[33]Hans B(o|")rjesson.Incorporating worst-ease execution time in a commercial compiler.Docsmsc thesis 95/96,Department of Computer Systems.Uppsala University,Sweden,Dec.1995.
[34]J.Engblom and A.Ermedahl.Modeling Complex Flows for Worst-Case Execution Time Analysis.In Proc.21th IEEE Real-Time Systems Symposium(RTSS' 00),November 2000.
[35]J.Gustafsson,A.Ermedahl,and B.Lisper.Towards a flow analysis for embedded system C programs.In Proc.10th IEEE International Workshop on Object-oriented Real-time Dependable Systems(WORDS 2005),Sedona,USA,February 2005.
[36]刘育芳,张立臣.实时系统最坏执行时间分忻[J].计算机应用研究,2005,22(11):8-10.
[37]吴国伟,姚琳.一种嵌入式软件WCET估计新方法[J].大连理工大学学报,2004,44(6):912-915.
[38]胡明华,汤铭端.基于分布函数的程序执行时间的静态预估[J].计算机工程与设计,2006,16(8):3045-3047.
[39]Niklas Holsti and Sami Saarinen.Status of the Bound-T WCET Tool.2nd International Workshop on Worst-Case Execution Time Analysis Satellite Event to ECRTS' 02,Technical University of Vienna,Austria,2002.
[40]Christian Ferdinand,Reinhold Heckmann,Henrik Theiling.Convenient User Annotations for a WCET Tool.3rd International Workshop on Worst-Case Execution Time Analysis(WCET 2003) Polytechnic Institute of Porto,Portugal,2003.
[41]Yua-Tsun,Steven hi,Sharad Malik,Andrew Wolef.Cache Modeling for Real-Time Sotfware:Beyond Direct Mapped Insurtction Caches.In Proceedings of the IEEE Real-Time Systems Symposium,December,1996.
[42]Christoper A.Healy,Mikael Sjodin,Viresh Rustagi et al.Supporting timing analysis by automatic bounding of loop iterations.Real-Time Systems,May 2000,121-148.
[43]Andersen L.O.Program Analysis and Specialization for the C Programming Language PhD.Thesis.DIKU(DIKU Report 94/19),University of Copenhagen,1994-05.
[44]陆仲达.面向对象程序分片中的数据流分析(硕士论文).西安:西安电子科技大学,2003.
[45] Rebecca Hasti and Susan Horwitz. Using static single assignment form to improve flow-insensitive pointer analysis. In Proceedings of the ACM SIGPLAN 1998 Conference on Programming Language Design and Implementation, 1998, 33(5):97-105.
[46] Choi J, Burke M, Carini P. Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects[M]. In Proceedings of the 20th Annual ACM Symposium on Principles of Programming Languages, 1993, 233-245.
[2]E.Kligerman,A.Stoyenko.Real-Time Euclid:A language for reliable real-time systems.IEEE Transactions on Software Engineering.1986,12(9):941-949.
[3]P.Puschner,C.Koza.Calculating the maximum execution time of real-time program.Real-Time Systems.1989,1(2):159-176.
[4]Raimund Kirner,Peter Puschner.Transformation of Path Information for WCET Analysis during Compilation.Proceedings of the 13th Euromicro International Conference on Real-Time Systems,2001(6):29-36.
[5]Raimund Kirner,Peter Puschner.Supporting Control-Dependent Execution Time on WCET Calculation.Proceedings of the WCET2OOO(Deutscbsprachige WCET Tagung,Paderborn,Germany).C-Lab,Paderborn,2000(10).
[6]Peter Puschner.Worst-Case Execution Time Analysis at Low Cost.Control Engineer Practic.1998(6):129-135.
[7]Chang Yun Park.Predicting Deterministic Execution Times of Real-Time Programs.PhD.Thesis,University of Washington,Seattle 98195,1992(8).
[8]Yau Tsun Steven Li,Sharad Malik.Performance Analysis of Embedded Software Using Implicit Path Enumeration.Proceedings of the 32nd ACM/IEEE Design Automation Conference,1995(6):456-461.
[9]Sung-Soo Lim,Young Hyun Bae,Gyu Tae Jang et al.An accurate worst case timing analysis technique for RISC processors.Proceedings of the 15th IEEE Real-Time Systems Symposium.1994(12):97-108.
[10]George S.Avrunin,James C.Corbett,Laura K.Dillon et al.Automated derivation of time bounds in uniprocessor concurrent systems,IEEE Transactions on Software Engineering,1994,20(9):708-719.
[11]J.Engblom,A.Ermedahl,M.Sjodin,et al.Towards industry-strength worst case execution time analysis[R].Advanced Software technology Center(ASTEC),Technical Report:ASTEC 99/02,1999.
[12]F.Stappert,P.Altenbernd.Complete worst-case execution time analysis of straight-line hard real-time programs.Journal of Systems Architecture,vol.46,2000:339-335.
[13]T.Lundqvist,P.Stensrom.Integrating path and timing analysis using instruction-level simulation techniques[C],The SIGPLAX Workshop on Languages,Compilers and Tools for Embedded Systems(LCTES' 98),Montreal,Canada,1998.
[14] C. Healy, R.Arnold, F.Mueller, et al. bounding pipeline and instruction cache performance[J]. IEEE Trans. On computers, 1999, 48(1):53-70.
[15] A. Colin, I. Puaut. A modular and retargetable framework for tree-based WCET analysis[C].The 13th Euromicro Conf. on Real-Time Systems(ECRTS' 01), Delft, the Netherlands,2001.
[16] Sung-Soo Lim, Young Hyun Bae, Gyu Tae Jang, et al. An accurate worst case timing analysis for RISC processors[C]. The 15th IEEE Real-Time Systems Symposium, San Juan, Puerto Rico, 1994.
[17] Lapkowski C., Hendren L J. Extended SSA Numbering: Introducing SSA Properties to Languages with Multi-level Pointers. ACAPS Technical Memo 102, School of Computer Science, McGill University, Mont&J, Canada, 1996-04
[18] Ferrante J, Ottenstein KJ, Warren J D. The program dependence graph and its use in optimization[J]. ACM Transactions on Programming Languages and Systems, 1987,9(3) :319 -349.
[19] Cousot P., Cousot R. Abstract Interpretation:A Unified Model for Static Analysis of Programs by Construction or Approximation of Fixpoints[C]. Proceedings of the 4th ACM Symposium on Principles of Programming Languages, Los Angeles, 1977:238-252.
[20] Tom R. Halfhill. Embedded Market Breaks New Ground. Microprocessor Report, January 17,2000.
[21] P. Puschner, A. Burns. Guest Editorial: A Review of Worst-Case Execution-Time Analysis,Real-Time Systems, May 2000, 18(2-3):115-128.
[22] Markus Lindgren.Measurement and Simulation based Techniques for Real-time Systems Analysis. Sweden: University Printers, Uppsala University, 2000.
[23] T. Lengauer and R. E. Tarjan. A fast algorithm for finding dominators in a flowgraph. ACM Transactions on Programming Languages and Systems, 1979, 7(1):115-120.
[24] Weiser M. Program slicing, IEEE Trans. on Software Engineering, 1984, 10(4):353-357.
[25] Christon Steindl. Program Slicing for Object-Oriented Programming Languages, Ph. D Thesis, 1999.
[26] Frank Tip. Generation of Program Analysis Tools, PhD thesis, University of Amsterdam,1995.
[27] K. J. Ottenstein and L. M. Ottenstein. The Program Dependence Graph in a Software Development Environment. In Proc. ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, 1984, 19(5):177-184.
[28] S. Horwitz, T. Reps, and D. Binkley. Interprocedural slicing using dependence graphs. ACM Transactions on Programming Languages and Systems, 1990, 12(1):26—60.
[29]William H.Harrison.Compiler Analysis of the Value Ranges for Variables[A].tEEE Trans.on Software Engineering,1977,3(3):243-250.
[30]姬孟洛.实时系统最差情况执行时间分析的研究:(博士学位论文).长沙:国防科学技术大学,2006.
[31]F.Nielson,H.R.Nielson,and C.Hankin.Principles of Program Analysis,2nd edition.Springer,2005.ISBN 3-540-65410-0.
[32]Raimund Kirner.The Programming Language wcetC.Tchnical report,Technische Universit(a|")t Wien,Institut f(u|")r Technische Informatik,Treitlstr.1-3/182-1,1040Vienna,Austria,2002.
[33]Hans B(o|")rjesson.Incorporating worst-ease execution time in a commercial compiler.Docsmsc thesis 95/96,Department of Computer Systems.Uppsala University,Sweden,Dec.1995.
[34]J.Engblom and A.Ermedahl.Modeling Complex Flows for Worst-Case Execution Time Analysis.In Proc.21th IEEE Real-Time Systems Symposium(RTSS' 00),November 2000.
[35]J.Gustafsson,A.Ermedahl,and B.Lisper.Towards a flow analysis for embedded system C programs.In Proc.10th IEEE International Workshop on Object-oriented Real-time Dependable Systems(WORDS 2005),Sedona,USA,February 2005.
[36]刘育芳,张立臣.实时系统最坏执行时间分忻[J].计算机应用研究,2005,22(11):8-10.
[37]吴国伟,姚琳.一种嵌入式软件WCET估计新方法[J].大连理工大学学报,2004,44(6):912-915.
[38]胡明华,汤铭端.基于分布函数的程序执行时间的静态预估[J].计算机工程与设计,2006,16(8):3045-3047.
[39]Niklas Holsti and Sami Saarinen.Status of the Bound-T WCET Tool.2nd International Workshop on Worst-Case Execution Time Analysis Satellite Event to ECRTS' 02,Technical University of Vienna,Austria,2002.
[40]Christian Ferdinand,Reinhold Heckmann,Henrik Theiling.Convenient User Annotations for a WCET Tool.3rd International Workshop on Worst-Case Execution Time Analysis(WCET 2003) Polytechnic Institute of Porto,Portugal,2003.
[41]Yua-Tsun,Steven hi,Sharad Malik,Andrew Wolef.Cache Modeling for Real-Time Sotfware:Beyond Direct Mapped Insurtction Caches.In Proceedings of the IEEE Real-Time Systems Symposium,December,1996.
[42]Christoper A.Healy,Mikael Sjodin,Viresh Rustagi et al.Supporting timing analysis by automatic bounding of loop iterations.Real-Time Systems,May 2000,121-148.
[43]Andersen L.O.Program Analysis and Specialization for the C Programming Language PhD.Thesis.DIKU(DIKU Report 94/19),University of Copenhagen,1994-05.
[44]陆仲达.面向对象程序分片中的数据流分析(硕士论文).西安:西安电子科技大学,2003.
[45] Rebecca Hasti and Susan Horwitz. Using static single assignment form to improve flow-insensitive pointer analysis. In Proceedings of the ACM SIGPLAN 1998 Conference on Programming Language Design and Implementation, 1998, 33(5):97-105.
[46] Choi J, Burke M, Carini P. Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects[M]. In Proceedings of the 20th Annual ACM Symposium on Principles of Programming Languages, 1993, 233-245.