理论教育 编译器设计之路:流图数据结构

编译器设计之路:流图数据结构

时间:2023-11-04 理论教育 版权反馈
【摘要】:前面,已经详细介绍了流图的概念及其构造方法。下面,先来看看Neo Pascal中基本块的结构定义。由于Neo Pascal的IR是以顺序线性表形式存储的,所以只需两个数值类型的变量足以描述基本块入、出口。在Neo Pascal中,流图是以过程为单位生成的,也就是说,一张流图描述的是一个过程(函数)的控制结构,但并不描述过程之间的依赖关系。在Neo Pascal中,流图的结构声明如下:这是一个map表结构,它存储的是整个输入程序的流图集合。

编译器设计之路:流图数据结构

前面,已经详细介绍了流图的概念及其构造方法。在本小节中,将开始分析Neo Pascal中相关源代码的实现。

下面,先来看看Neo Pascal中基本块的结构定义。

【声明7-1】

iStart、iEnd两个属性是用于描述基本块入、出口语句的位序号。由于Neo Pascal的IR是以顺序线性表形式存储的,所以只需两个数值类型的变量足以描述基本块入、出口。

DownFlow、UpFlow两个属性用于描述基本块之间的关系,即流图中的边。由于流图是一个有向图,有读者可能认为根本不需要使用两个属性描述流图的边,而只需使用DownFlow描述其后继基本块即可。不过,这却不是一个好主意。实际上,很多优化算法不仅需要关心当前基本块的后继基本块,有时也需要了解当前基本块的前趋基本块。所以,比较理想的基本块结构一般都需要存储其前趋基本块的信息。

这里,值得读者注意的是基本块的结构的定义很大程度上取决于IR的组织形式。例如,编译器设计者使用链式结构组织IR,那么,基本块的结构也就可能复杂些。(www.daowen.com)

剩下的4个属性都是用于描述基本块数据流相关信息的,在此,读者并不需要深入研究。

下面,再来看看流图的结构定义。实际上,流图就是基本块的集合。在Neo Pascal中,流图是以过程为单位生成的,也就是说,一张流图描述的是一个过程(函数)的控制结构,但并不描述过程之间的依赖关系。因此,针对整个输入程序的控制流分析可能会生成多张流图。在Neo Pascal中,流图的结构声明如下:

【声明7-2】

这是一个map表结构,它存储的是整个输入程序的流图集合。其中,一个表项即表示一张流图,以过程序号为关键字进行索引

免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

我要反馈