快速程序流分析方法的研究与应用

摘要

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

目录

文摘

英文文摘

声明

1 绪论

1.1 课题研究背景及意义

1.2 国内外研究现状和存在的问题

1.3 本文研究内容与结构

2 实时软件WCET分析

2.1 实时系统和嵌入式系统

2.2 WCET分析的基本概念

2.3 获取WCET的方法

2.4 程序流事实

3 基于静态单赋值的程序流分析

3.1 静态单赋值的基本概念

3.2 静态单赋值形式转化过程

3.3 静态单赋值形式还原

3.4 指针分析

4 基于程序切片的程序流分析

4.1 程序切片定义

4.2 程序切片分类

4.3 过程内切片

4.4 过程间切片

4.5 简单切片算法

4.6 程序切片在WCET分析中的应用

4.7 静态单赋值在流不敏感程序切片中的应用

4.8 本章小结

5 流分析工具原型及实验

5.1 WCET-SPIA的功能要求及结构

5.2 实验

结论

参考文献

攻读硕士学位期间发表学术论文情况

致谢