摘 要：在WCET分析中，最重要的一类工作就是Cache分析。目前，大多数的基于抽象解释技术的Cache分析中，分析算法是作用于整个程序的，如果能够根据程序的层次结构，挖掘程序执行在Cache中的局部特性，那么就可以有效的提高WCET的分析精度。基于这一需求，本文主要研究基于抽象解释技术的多层Cache分析，研究的主要内容包括：程序层次结构的分析，基于抽象解释技术的多层Cache分析和整数线性规划问题的建模与WCET求解，采用多层Cache分析能有效的提高WCET的分析精度。

关键词：WCET；抽象解释；多层Cache分析

中图分类号：TP311.1

本文设计并实现了“基于抽象解释技术的多层Cache分析”。该分析方法按照程序中循环的嵌套关系，首先将程序划分成若干个层次。之后，按照传统基于抽象解释技术的分析手段，针对每个层次对应的循环体，分别进行分析，探索程序的局部Cache访问特性。最终，根据各个层次的分析得到的结果，进行整数线性规划的编码，并计算出更加精确的WCET估计值。

1 系统总体设计

图1为WCET分析工具总体分析框架，展示了WCET分析工具完整的工作流程。其中绿色的模块表示的是本文研究的主体工作在整个工具中所处的位置。

在本工具中，待分析的程序为C代码编写，通过面向SimpleScalar平台的gcc交叉编译器，可以将源程序编译为PISA指令集的可执行程序，这个可执行程序就是WCET分析工具的直接输入。程序读入工具之后，分析工具将可执行程序进行反编译，提取详细的指令信息，并生成程序的CFG。程序的CFG表示了程序的流程结构，这一信息将成为处理器行为分析的输入。……