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

论文摘要

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

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 课题研究背景及意义
• 1.2 国内外研究现状和存在的问题
• 1.3 本文研究内容与结构
• 2 实时软件WCET分析
• 2.1 实时系统和嵌入式系统
• 2.2 WCET分析的基本概念
• 2.3 获取 WCET的方法
• 2.3.1 动态度量
• 2.3.2 静态分析
• 2.3.3 混合分析
• 2.4 程序流事实
• 2.4.1 手工标注和自动分析
• 2.4.2 程序流事实表示
• 3 基于静态单赋值的程序流分析
• 3.1 静态单赋值的基本概念
• 3.2 静态单赋值形式转化过程
• 3.2.1 构造控制流图
• 3.2.2 构造必经节点树
• 3.2.3 计算必经节点边界
• 3.2.4 插入（?）函数和变量重命名
• 3.3 静态单赋值形式还原
• 3.4 指针分析
• 4 基于程序切片的程序流分析
• 4.1 程序切片定义
• 4.2 程序切片分类
• 4.2.1 前向切片和后向切片
• 4.2.2 过程内切片和过程间切片
• 4.2.3 静态切片和动态切片
• 4.3 过程内切片
• 4.3.1 数据依赖图
• 4.3.2 控制依赖图
• 4.3.3 程序依赖图
• 4.3.4 图可达性算法
• 4.3.5 例子分析
• 4.4 过程间切片
• 4.5 简单切片算法
• 4.5.1 符号定义
• 4.5.2 算法
• 4.5.3 算法应用
• 4.6 程序切片在WCET分析中的应用
• 4.7 静态单赋值在流不敏感程序切片中的应用
• 4.8 本章小结
• 5 流分析工具原型及实验
• 5.1 WCET-SPIA的功能要求及结构
• 5.2 实验
• 5.2.1 程序执行时间的度量
• 5.2.2 程序切片实验
• 5.2.3 程序流分析速度
• 5.2.4 WCET估计精度
• 结论
• 参考文献
• 攻读硕士学位期间发表学术论文情况
• 致谢