在分析源代码之前,本小节将介绍几个与定值、引用相关的数据结构。其中,有些数据结构不仅涉及数据流分析的实现,甚至贯穿整个优化过程的设计。
1.变量映射表
Neo Pascal的数据流分析主要是基于迭代思想实现的。在优化算法的实现中,将大量涉及位向量(变量表的一种映射形式)的迭代。不过,由于Neo Pascal的优化算法都是以过程为单位讨论的,一个过程可能涉及的变量仅为全局变量和本过程内的局部变量,所以没有必要将符号表内的所有变量都映射成位向量形式。建立变量映射表的主要目的就是为了便于使用位向量描述变量集合。变量映射表的声明形式如下:
【声明7-4】
map<int,int>VarMap;
在分析每个过程时,根据当前过程的信息,从符号表中提取出当前过程相关的变量集合,主要包含全局变量及当前过程的局部变量,并生成相应的VarMap。其中,第1个整型值用于描述变量在符号表中的位序号,而第2个整型值则用以描述变量在新构造的变量集合中的位序号。后续的优化算法大多数都是基于该变量集合讨论的,因此,VarMap是一个非常重要的数据结构。
2.定值集、引用集
在编译技术中,定值点、引用点的问题通常是基于变量讨论的。所谓“定值集”就是用于描述变量及其定值点集合的数据结构。在Neo Pascal中,定值集的声明形式如下:
【声明7-5】
其中,前者的字符串即为定值集的关键字。实际上,就是变量名的一种符号化形式,其描述形式为“过程位序号$变量位序号”。例如,过程aa和其过程内的局部变量a在符号表中的位序号分别为2、5,那么,a的关键字就是“2$5”。
vector<int>存储的就是该变量的所有定值点,也就是定值点IR在m_Codes中的位序号。(www.daowen.com)
所谓“引用集”就是用于描述变量及其引用点集合的数据结构。在Neo Pascal中,引用集的声明形式如下:
【声明7-6】
引用集的数据结构与定值数是完全一致的,不再赘述。
3.定值位向量、引用位向量
前面介绍了定值集、引用集的基本结构。这里再引入两个概念:定值位向量、引用位向量。这两个概念是基于基本块讨论的,每个基本块都有一个定值位向量和一个引用位向量。
所谓“位向量”就是指向量中的每个元素都是一个位(只能取“0”或“1”)。使用位向量而不是集合是为了适应迭代算法的需要。
定值位向量主要是应用位向量的形式描述所属基本块中变量定值的信息。在某些应用场合,相比定值的位置来说,编译器可能更关注的是在某个基本块中有哪些变量被定值了,而不关心详细的定值位置。最典型的是稍后将谈到的活跃变量分析。通常,定值位向量中的每个位元素都与VarMap中的一个变量关联。位值为0,则表示相应的变量在该定值位向量所属的基本块中没有定值,否则表示存在定值或可能定值。
引用位向量与定值位向量的结构基本一致,引用位向量主要是通过位向量的形式描述所属基本块中变量引用的信息。在Neo Pascal中,这两个位向量都是隶属于CBasicBlock结构的,声明形式如下:
【声明7—7】
由于不同过程的VarMap的个数是不同的,所以定值、引用位向量都是在编译过程中动态生成。注意,CBits是笔者设计的一个位向量类,同时,封装了一些在编译器设计中经常涉及的位向量操作。其源代码的实现并不复杂,读者可以自行参考阅读,这里就不再详细列出。
免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。