【一个典型过程式语言的别名分析系统】刘阳.pdf

提要别名问题是许多静态程序分析所必须解决问题。两个名字代表同一个内存位置,这两个名字就说是互相别名.本文的工作主要是研究一个微小C语言的别名分析问题。微小C语言具有if,while语句,函数调用(允许递调用),递归结构,指针变量.它具备了C语言的大部分特性,这些也是大多数过程式语言所具有的特性.在文中提出了我们的分析的核心部分v格,它使我们能够描述三种基本的位置关系:一对一、一-对多、多对多关系。它尤其适合描述循环语句产生的规则的数据结构。之后我们给出了过程内和过程间的别名分析框架,并用固定点计算较好的解决了过程内别名分析中的循坏语句和过程间别名分析中的递归调用。

第一章前言第一章前言 1问题引出编译器以及其它各种程序工具大量使用静态程序分析。解决大部分程序分析问题都需要别名信息,也就是决定是否两个左值表达式在某个程序点可能/必然有同样的值。如果在程序执行过程中两个名宁或左值表达式在-个程序点指向同样的位置,则说它们互相别名。可能别名问题关心的是程序的某次执行能够发生的别名,而必然别名问题关心的是程序的所有执行都能发生的别名.别名信息与大多数数据流分析问题有关。许多问题是不进行别名分析就儿乎不能进行的。在代码移动、编译时无用单元回收、程序验证和调试、依赖性分析、程序并行化等方面有重要的应用。

第一章前言在我们的系统中可以表示为(X->(tl->)2hd.*,Y->(tl->)hd.*)}.我们的方法就是基于对上述三种基本结构的表述。第一种我们称之为一对-结构,第二种我们称之为一对多结构,第三种我们称之为多对多结构。在分析具体程序时的最坏情况就是认为两个数据结构之间有任意对应关系,也就是多对多结构.在处理循坏语句时,出于静态很难判断循环执行次数,因此我们使用一个固定点操作求模拟循环的执行效果。我们的描述方法保证做有限次循环即可满足循环退出条件。用图形可以表示为:其中的V表示将两个数据流用固定点操作合为一个数据流。