【作者】 曹厚华；

【导师】 吴国伟；

【作者基本信息】 大连理工大学 ， 软件工程， 2008， 硕士

【摘要】 衡量系统实时性的最重要的参数是任务的最坏情况执行时间(Worst Case ExceutionTime,WCET)。WCET分析的目的在于得到任务执行时间的上界约束,这需要综合考虑系统的软硬件特征。由于WCET的动态测量方法不能保证估计结果是安全的,所以现在一般学者都致力于静态分析方法的研究。随着软件规模及其复杂性的不断增长,使得快速地获得WCET估计值更加困难。在WCET程序流分析中,本文依据C的语言特点,给出了从抽象语法树到程序控制流图的构造,由程序控制流图到静态单赋值形式的转变。依据静态单赋值形式的控制流图得出数据依赖和数据依赖关系,然后就可以构造程序依赖图。对程序依赖图的扩展得到系统依赖图,利用图的可达性算法来对程序进行切片。本文还给出了一种不是基于依赖图的简单程序切片算法,该算法适合对程序中所有条件语句计算切片。经过程序切片后,采用抽象解释来自动导出程序流中循环迭代界限、不可行路径等约束信息,避免了手工标注。依据上述给出的程序流分析方法,本文给出了程序流分析工具的设计架构。实验结果表明,利用静态单赋值、程序切片、抽象解释理论进行WCET分析中的程序流信息分析,能够快速且有效地给出程序流事实。本文在图论、编译优化技术、程序切片技术的基础上,探讨了WCET流分析工具的整体实现策略,是对WCET流分析方法研究的一种尝试。更多还原

【Abstract】 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.更多还原