理论教育 IR设计及其级别:编译器设计之路

IR设计及其级别:编译器设计之路

时间:2023-11-04 理论教育 版权反馈
【摘要】:一个实际编译器的IR通常是由该编译器设计者定义且仅供该编译器使用的一种语言,对于编译器的用户及程序设计语言本身都是透明的。编译器后端的算法设计及其性能很大程度上都是依赖于其IR的,因此,除了一些开源或者早期实验室级的编译器外,很少有商用编译器愿意公开其IR。IR的主要服务对象就是编译器后端,因此设计IR必须充分考虑目标机体系结构。这是一种最为常见的IR。

IR设计及其级别:编译器设计之路

一个实际编译器的IR通常是由该编译器设计者定义且仅供该编译器使用的一种语言,对于编译器的用户及程序设计语言本身都是透明的。除了一些特殊情况外,编译器的IR是不会公开的。在笔者看来,将IR视作一种资源或者财富是绝不为过的。编译器后端的算法设计及其性能很大程度上都是依赖于其IR的,因此,除了一些开源或者早期实验室级的编译器外,很少有商用编译器愿意公开其IR。

即便如此,关于IR设计可以借鉴的经验还是比较多的,也有一些设计原则可以指导编译器设计者定义IR。不少编译器设计大师都认为定义IR是一门艺术而不是科学,因为其优劣在很大程度上是无法使用非常科学或精确的方法来评价的。根据对经典编译器的理解并结合一些大师著作的观点,笔者总结得到如下几点建议,供读者参考。

(1)充分考虑目标机体系结构。IR的主要服务对象就是编译器后端,因此设计IR必须充分考虑目标机体系结构。当然,目标机的指令系统是其中一个最重要因素,但并不仅仅局限于此。例如,存储结构、总线结构、中断系统等也是比较重要的。不过,必须指出一点,充分考虑目标机体系结构,并不等同于过多依赖于目标机体系结构。恰恰相反,通常IR不应该包含太多目标机的细节,否则移植性、通用性都会大大降低。例如,有些目标机的指令系统不支持乘、除法,如果因此编译器的IR也不包含乘、除法操作,笔者认为这是完全没有必要的。再比如,在定义IR时,可以对寄存器分配的方案加以考虑,但不应该细化到某一种目标机的具体寄存器(如i386的EAX~EDX等)。简而言之,应充分考虑目标机的共性,舍弃目标机中过于个性的细节,除非是针对某一特定的目标机而设计专用编译器。

(2)兼顾优化算法的需要。优化技术是现代编译技术中最为复杂的话题之一,优化算法众多,其中一部分优化算法是基于IR实现的,即优化算法的输入、输出都将是IR。然而,正所谓众口难调,由于各种优化算法所面临的问题和解决的方案都存在较大的差异,它们对于IR的需求也不尽相同。例如,有些优化算法希望输入的IR尽可能高级,即比较接近于源语言形式,最大程度上保留源语言的特性。而有些优化算法则希望输入的IR尽可能低级,即更接近于目标语言形式,以便优化过程中更多地考虑目标机的特性。

在一些编译原理教材中,经常以经典的五个阶段为基础讨论编译技术。这样可能会给读者造成一个误区:编译过程中只存在一种IR形式。实际上,这种说法通常是错误的,因为一个编译器使用多种IR的情况并不罕见。设置多种IR的目的就是为了更好地适应各种优化算法的需求。一些商用编译器为了尽可能改善目标代码的性能,不惜生成多遍IR以适应各种算法的需要。当然,这个过程通常是串行的,以免编译过程对存储空间资源消耗过大。

(3)结构不宜过于复杂,应具有一定灵活易变性。根据经验,一些经典IR的逻辑结构都是比较简单的,如数组、树、DAG等。这样设计的主要目的有两个:第一,IR经常会以文件形式存储到外存中,供其他程序使用。逻辑结构过于复杂可能会给读取、存储增加难度,而且影响处理效率。第二,IR往往不是一成不变的,随着后端设计的细化,有时IR会有一定变化。通常,很难认为这种情况是由于初期设计不周所致,毕竟编译器设计的难度要远高于普通应用系统。从一些编译器大师的回忆录中不难发现,即使是Turbo Pascal、lcc、Delphi等经典编译器也是如此。因此,在这种情况下,能做的仅是使IR适应后端的需要。

(4)表达能力必须充分。前面已经讲过,编译过程就是将源语言程序等价变换成目标语言程序的过程,其中最核心的要点就是“等价”。如果翻译过程导致或者可能导致源语言程序与目标语言程序之间存在语义差异,那么本次编译过程是失败的。这也是编译优化技术讨论的前提,任何优化算法都不能违背这个原则,否则宁可不用,也不能使编译器存在任何隐患。IR是编译器后端的输入,也就是说,编译器后端可能已经无法知晓源语言程序的真实语义了,只能从输入的IR了解源语言程序的语义信息。在这种情况下,IR应该足以表述源语言所允许的任何语义,否则一定会违背“等价”原则。举个比较极端的例子,源语言存在IF、FOR等结构,而IR只允许存在顺序结构。那么,无论使用怎样的翻译方案也无法保证“等价”原则。

当然,参考一些现存的经典IR也是一种不错的选择,如GCC的RTL、SSA、lcc的DAG、Sun SPARC的SunIR、GEM的CIL和EIL、Intel的IL等。针对当前的源语言与目标机,虽然现存的IR未必是最优的解决方案,但是它们可以让一些经验不足的设计者方便地构造一套较为完整的IR。在这种情况下,设计者需要更多考虑这种IR对目标编译器的各种适应性问题及实现它所需付出的代价。

下面简单介绍一些常用IR。按IR的逻辑结构,通常可以分为如下几种:语法树、后缀表达式、DAG、三地址代码等。除了三地址代码之外,读者应该对提到的其他逻辑结构并不陌生,它们都是常见的数据结构。这里,笔者就不再给出其具体形式,只想就这些IR的特性简单评说几句,供读者参考。(www.daowen.com)

语法树、DAG(有向无环图):这两种形式者是比较直观的,在计算机科学中,基于树、图的算法资源比较丰富,关于它们的存储结构也存在许多经典的方案可供参考。语法树形式能较好地保存源程序的结构,所以常作为自下而上的语法分析过程的暂存数据结构。而DAG更多地被作为三地址代码的一种变体形式,在某些优化算法中,DAG有着其他形式所不具备的优势。

后缀表达式:也称为逆波兰表达式,这种形式简单明晰,便于存储。在处理表达式翻译时,后缀表达式有着其他形式无法比拟的优势。不过,由于后缀表达式的应用领域比较单一,所以很少独立作为一个实际编译器的IR存在。

三地址代码:也称为“四元组”,即操作符和三个操作数地址。这是一种最为常见的IR。甚至有些书籍认为IR就是中间代码(即三地址代码)。笔者认为这一说法并不是非常准确。从形式上而言,三地址代码与汇编代码比较类似,都是以代码列表形式存在的。所谓的三地址,指的就是每一行代码通常包含三个地址信息,即操作数1、操作数2、结果操作数。例如,(ADD A,1,C)这行三地址代码的含义就是A+l→C。这种形式初看与汇编语言有点类似,但是在生成三地址代码时,编译器并不需要计算操作数的实际地址,只是以标号形式给出即可。另外,读者也不必苛求三地址代码与汇编指令格式的统一,这是没有意义的。有些书上也提到了二地址代码(三元组)的形式,它和三地址代码比较类似,只是省略了结果操作数地址,而是将操作结果存入操作数1或操作数2的存储空间内。实际上,二地址代码形式可能更贴近于x86汇编指令的格式,但是它的通用性却不及三地址代码,因此并不常用。三地址代码的优点是便于编译器生成目标代码,编译器不必为复杂的IR结构的转换付出高昂的代价,而且也基本上能满足常用优化算法的需要。当然,三地址代码也不是完美的,由于它是相对离散的,在分析源程序结构方面,它就不及语法树便捷。Neo Pascal的IR也是三地址代码,在后续章节中,笔者还将详细讲解。

最后,再来谈谈IR的级别,即IR依赖于目标机的程度。按级别分类,可将IR分成三类:高级形式(HIR)、中级形式(MIR)、低级形式(LIR),也可称为高级中间语言、中级中间语言、低级中间语言。

高级形式(HIR)是一种尽可能保持了源语言程序结构的IR,这种形式能较好地保留源程序的原始语义信息。由于高级形式太接近源语言程序结构,所以很少有编译器将其独立作为IR传递给后端。

中级形式(MIR)既要以一种与语言无关的方式在一定程度上反映源语言的特性,又要能够适应多种体系结构的IR。中级形式是一种比较常用的IR,它兼顾了源语言、目标机的特性,又能适用于大多数优化算法。当一个编译器仅设计一种IR时,中级形式是较理想的选择。

低级形式(LIR)就是在一定程度上包含某些目标机特性的IR,比目标语言稍高级,常作为一些机器相关的优化算法的输入。不过,实际上,除了一些较大型的编译器需要使用低级形式之外,低级形式并不是很常见。因为更多编译器设计者更愿意直接基于目标语言作优化。

级别的概念在国内编译原理书籍中并不多见,不过,笔者却觉得这种分类比较科学,它揭示了IR的核心。有些国内编译原理书籍在讲述IR时,过份强调其逻辑结构(例如,后缀式、树、DAG、三元组等)。实际上,逻辑结构只是数据结构的讨论范畴而己,并不是设计IR的核心,从编译器设计角度而言,应该更关注IR的级别。在此,笔者不想过多讨论IR的各种逻辑结构,这可能是徒劳的。因为,在笔者看来,这个话题或许会让读者对IR产生错误的理解,认为优秀的IR所采用的逻辑结构就是书上所提及的那几种。实际上,出于对整体架构的考虑,一些经典编译器的IR可能是很奇特的,根本无法将其严格归类。即使如此,它却依然是经典的。例如,GCC的RTL,有些书坚持认为RTL是三地址代码,但笔者认为这种观点值得商榷,必竟它与三地址代码的形式相差甚远。

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

我要反馈