ACM通信
实践
中间表示
来源:iStockPhoto.com
程序编译是一个复杂的过程。编译器是一种软件程序，它将高级源语言程序转换为可以在计算机上执行的形式。在编译器发展的早期，设计人员引入了中间表示(IRs，也通常称为中间语言)来管理编译过程的复杂性。使用IR作为编译器对程序的内部表示，可以将编译器分解为多个阶段和组件，从而受益于模块化。
IR是任何数据结构，它可以在不丢失信息的情况下表示程序，从而可以准确地执行程序。它充当编译器组件之间的公共接口。因为它的使用是编译器内部的，所以每个编译器都可以自由地定义IR的形式和细节，而且它的规范只需要编译器作者知道。它可以在编译过程中暂时存在，也可以作为文本或二进制文件输出和处理。IR应该是通用的，这样它就能够表示从多种语言翻译过来的程序。编译器编写者通常认为编程语言的语义内容是高的。机器可执行代码的语义内容被认为是低的，因为它只从原始程序中保留了足够的信息，以允许其正确执行。从较低的形式重新创建源程序是困难的(如果不是不可能的话)。编译过程需要逐步降低程序表示，从高级的人类编程构造到低级的真实或虚拟机指令(参见图1)．为了使IR能够表示多种语言，它需要更接近于机器级别，以表示所有语言的执行行为。较长的代码序列通常伴随着机器可执行代码，因为它反映了执行所处机器的细节。
设计良好的IR应该可以转换成不同的形式，以便在多个平台上执行。为了在目标处理器或CPU上执行，需要将其翻译成该处理器的汇编语言，这通常是到处理器的机器指令的一对一映射。由于不同的处理器具有不同的指令集体系结构(isa)，因此IR需要处于比典型机器指令更高的级别，因为它不需要承担任何特殊的机器特性。
使用IR使编译器能够支持从不同编程语言翻译过来的多个前端和多个后端，从而为不同的处理器目标生成代码(参见图2)．执行平台也可以是解释性的，因为它的执行是由软件程序或虚拟机执行的。在这种情况下，执行媒介的级别可能高于程序集代码，而低于或与IR相同。
IRs的采用支持将编译过程模块化到前端、中间端和后端。前端专门处理编译器的编程语言方面。编程语言实现者只需要在声明工作完成之前实现语言到IR的精确翻译。
后端考虑目标机器的细节，并将IR转换为要在硬件上执行的机器指令。它还对代码进行转换，以利用任何有利于性能的硬件特性。通过从IR开始翻译，后端实际上支持产生IR的不同语言。
中间端是发生与目标无关的优化的地方。中端阶段在IR上执行不同的转换，因此程序可以更有效地运行。由于IR上的优化通常有利于所有目标，因此IR充当了执行与目标无关的优化转换的媒介的重要角色。在这个角色中，它的设计和规范变得更加重要。它需要对任何有助于优化任务的源程序信息进行编码。IR的设计关系到优化效率，优化是编译过程中最耗时的部分。在现代编译器中，IR规定了编译器的基础结构和整体工程。对IR的任何重大更改都可能意味着编译器实现的重大修改。
不同的IR格式
IR的最低要求是为原始程序的正确执行提供足够的信息。IR中的每条指令通常表示一个简单的操作。与任何典型的编程语言相比，IR应该具有更少的构造类型，因为它不需要具有丰富的特性来方便人类编程使用。编译器喜欢看到相同的编程结构或习惯用法在IR中被翻译成统一的代码序列，而不管它们的源语言、编程风格或程序员选择的编码方式是什么。在IRs中引入规范形式可以减少编译器在执行代码生成和优化时必须处理的代码模式的种类。由于IR的程序表示更细粒度，它的指令可以将多对一映射到机器指令，因为一个机器指令可以执行多个操作，如在乘法或索引寻址中。
IR的形式可以分为层次化或平面化。分级IR允许嵌套结构。在典型的编程语言中，程序控制流(例如if-then-else、do-loops)和算术表达式都是嵌套结构。因此，分层IR在形式上更接近于典型的编程语言，并且被认为处于更高的级别。层次化IR可以在内部以树的形式表示(编译器首选的数据结构)，而不会损失准确性。
平面IR通常被视为抽象机或虚拟机的指令。指令按顺序执行，就像在典型的处理器中一样，控制流由分支或跳转指令指定。每个指令接受多个操作数并产生一个结果。在编译器构造的教学中，经常指定这样的IRs作为编译目标。
抽象堆栈机器的语言介于层次化和平面化之间。在堆栈机器中，用于算术计算的每个操作数由一条指令指定，该指令将操作数推入堆栈。每个算术表达式的计算都是在从堆栈顶部弹出的操作数上完成的，而后续的结果则被推回堆栈上。IR的形式是平面的，控制流由显式的分支指令表示，但用于算术计算的指令序列可视为对应于反向波兰表示法，可以很容易地在树数据结构中内部表示。使用堆栈机的语言作为IR是一种常见的实践，可以追溯到为Pascal语言定义的第一个IR，称为p-code，1到当前的Java字节码6或通用中间语言(CIL)2)．
与任何典型的编程语言相比，IR应该具有更少的构造类型，因为它不需要具有丰富的特性来方便人类编程使用。
除了表示代码执行之外，还有一些补充IR的信息。编译器将原始程序中的命名空间编译为符号名称的集合。变量、函数和类型信息属于这些符号表，它们可以对控制某些优化转换合法性的信息进行编码。它们还提供各种工具(如调试器和程序分析器)所需的信息。符号表可以被认为是IRs的附属。
由于C语言作为一种系统编程语言的广泛使用以及它能够表示任何机器操作的能力，它一直被用作许多编程语言的翻译目标。C可以被视为IR，因为它相对于大多数语言的级别较低，但它不是为编译器容易操作或直接解释而设计的。尽管如此，许多IRs都是通过密切建模C语言语义来设计的。事实上，一个好的IR可以通过仔细地剥离C语言的高级控制流构造和结构化数据类型来构造，只留下它的原语。许多IRs也可以翻译成类似c语言的输出，便于编译器开发人员阅读。然而，由于C语言在表示某些编程概念(如异常处理、溢出检查或函数的多个入口点)方面的缺陷，此类类C语言的IRs通常不能转换为可以重新编译的C程序。
用于程序交付的IRs
随着网络计算机的广泛使用，人们很快就理解了与处理器和操作系统无关的执行媒介的优势。使用可以在任何机器上运行的程序，分发和交付过程更容易。这种一次编写、随处运行的方法可以通过虚拟机执行模型来实现，以适应系统硬件的多样性。
与编译执行相比，解释性执行会导致一些性能损失，最初它只适用于计算密集型不高的应用程序。然而，随着机器变得越来越快，在许多应用程序中，一次编写、随处运行方法的优势超过了潜在的性能损失。这使得像Java这样可以被普遍部署的语言变得流行起来。Java语言将Java字节码定义为其分发媒介，这是IR的一种形式。只要安装了Java虚拟机(JVM)软件，Java字节码就可以在任何平台上运行。另一个例子是CIL，它是。net框架使用的公共语言基础设施(CLI)运行时环境的IR。
随着移动互联网的发展，应用程序经常被下载到手持设备上立即运行。由于IRs比机器可执行文件占用更少的存储空间，因此它们可以降低网络传输开销，并支持独立于硬件的程序分发。
即时编译
随着虚拟机执行模型得到广泛接受，寻找加快执行速度的方法变得非常重要。一种方法是即时(JIT)编译，也称为动态编译，它通过在执行期间将解释程序编译为本机代码来提高底层计算机上的执行速度，从而提高解释程序的性能。由于在运行时进行编译会产生降低程序执行速度的开销，所以只有在执行时间减少的结果很可能超过额外产生的编译时间的情况下，才应该谨慎地采用JIT路线。此外，动态编译器不能花太多时间优化代码，因为优化带来的开销比转换到本地代码大得多。为了抑制动态编译引起的开销，大多数JIT编译器只编译执行期间最频繁使用的代码路径。
计算机制造商已经认识到，进一步提高计算性能不能再依赖于时钟频率的增加。
动态编译确实比静态编译有一些优点。首先，动态编译可以使用实时分析数据更有效地优化生成的代码。其次，如果程序行为在执行过程中发生了变化，动态编译器可以重新编译以调整代码以适应新的概要文件。最后，随着共享(或动态)库的普遍使用，动态编译已经成为执行整个程序分析和优化的唯一安全方法，在这种方法中，编译的范围跨越了用户代码和库代码。JIT编译已经成为许多将IRs作为输入的虚拟机的执行引擎中不可缺少的组件。其目标是使为独立于机器的分布而构建的程序的性能接近由静态编译器生成的本地代码的性能。
近年来，计算机制造商已经认识到，进一步提高计算性能不能再依赖于时钟频率的增加。这就产生了特殊用途的处理器和协处理器，它们可以是数字信号处理器(dsp)、gpu或在ASIC或现场可编程门阵列(FPGA)中实现的加速器。计算平台甚至可以是异构的，不同类型的计算被传递给不同类型的处理器，每个处理器具有不同的指令集。特殊语言或语言扩展，如CUDA，3.OpenCL,8和混合多核并行编程(HMPP)，4及其底层编译器，都被设计为使程序员更容易在异构设置中获得最大性能。
因为这些特殊的处理器是为了提高性能而设计的，所以必须编译程序以在它们的原生指令中执行。随着专用硬件的快速发展，编译器供应商不可能为市场上现有的或即将出现的各种处理器提供定制的支持。在这种设置中，定制硬件制造商负责提供将IR编译为定制机器指令的后端编译器，平台独立的程序交付变得更加重要。实际上，编译可以在安装时或在程序加载时进行，而不是在执行期间。如今，这个词AOT(提前)，与JIT相反，它的特点是在执行前将IRs编译成机器代码。然而，无论是JIT还是AOT, IRs显然在这种提供高性能计算平台的新方法中发挥了促进作用。
标准化国税局
到目前为止，由于大多数编译器都是根据它们所使用的IRs来区分的，所以IRs都被链接到各个编译器实现。然而，IR是可翻译的，并且有可能将编译器A的IR翻译成编译器B的IR，因此编译器B可以从编译器A的工作中受益。随着过去20年向开源软件发展的趋势，越来越多的编译器已经是开源的。9当一个编译器变成开源的，它就向世界公开了它的IR定义。随着编译器开发人员社区的发展，它有促进其IR的作用。然而，使用IR受制于其编译器的开放源码许可条款，该条款通常禁止将IR与其他类型的开放源码许可混合使用。在许可证冲突的情况下，在实现此类IR翻译之前，需要与许可证提供者制定特殊协议。总之，IR翻译支持编译器之间的协作。
Java字节码是具有独立于编译器的开放标准定义的IR的第一个例子，因为JVM被广泛接受，它产生了许多编译器和VM实现。JVM的流行导致许多其他语言被翻译成Java字节码，7但是因为它最初被定义为只服务于Java语言，所以对Java中不存在的高级抽象的支持不是不直接就是不存在。这种缺乏通用性限制了Java字节码作为通用IR的使用。
由于IR可以通过简化程序交付，同时在每个处理器上实现最大的编译代码性能，从而解决不同处理器之间的对象代码兼容性问题，因此在IR上进行标准化将很好地服务于计算行业。经验告诉我们，所有相关方面都需要时间才能就一个标准达成一致;大多数现有标准的制定需要数年时间，有时相互竞争的标准需要花时间整合成一个标准。开始制定IR标准的时机已经成熟。一旦这样的标准到位，只要它能不断地扩展，以捕捉最新的技术趋势，它就不会扼杀创新。
标准IR将解决计算行业中存在的两个不同问题:
- 软件兼容性．当两个软件位于不同isa的不同本机代码中时，它们是不兼容的。即使它们的isa是相同的，如果它们是使用不同的应用程序二进制接口(abi)构建的，或者是在具有不同目标文件格式的不同操作系统下构建的，那么它们仍然可能是不兼容的。因此，今天存在许多不同的不兼容的软件生态系统。如果能定义一种大多数计算平台(如果不是所有计算平台)都能接受的标准软件分发媒介，计算行业将得到很好的服务。这样的分发媒介可以基于抽象机器的IR。它将通过AOT或JIT编译在特定平台上呈现为可执行的。可以指定一组遵从性测试。软件供应商将需要只在这种媒介上发布他们的软件产品。支持该标准的计算设备将能够运行以这种形式分发的所有软件。 This standardized software ecosystem will create a level playing field for manufacturers of different types of processors, thus encouraging innovation in hardware.
- 编译器的互操作性．带有优化的编译领域是一个难题。没有一个单独的编译器可以宣称自己在所有方面都出类拔萃。编译器使用的算法可能对一个程序很有效，但对另一个程序就不是那么好了。因此，开发一个编译器需要付出巨大的努力。即使对于一个已完成的编译器，仍然可能有无尽的增强被认为是可取的。到目前为止，每个产品质量的编译器都是独立运行的。本文讨论了作为一种允许编译器一起工作的方法的IR翻译。标准IR如果被编译器采用，就可以将使用它的不同编译器的优点结合起来。这些编译器不再需要合并完整的编译功能。 They can be developed and deployed as compilation modules, and their creators can choose to make the modules either proprietary or open source. If a compiler module desires to operate using its own unique internal program representation, it can choose to use the standard IR only as an interchange format. A standard IR lowers the entry barrier for compiler writers, because their projects can be conceived at smaller scales, allowing each compiler writer to focus on his or her specialties. An IR standard also makes it easier to do comparisons among the compilers when they produce the same IR as output, which will lead to more fine-tuning. An IR standard will have the potential to revolutionize today's compiler industry and will serve the interests of compiler writers very well.
这里概述了IR标准的两个愿景:第一个聚焦于计算行业，第二个聚焦于编译器行业。第一个强调虚拟机方面，第二个侧重于为编译的不同方面提供良好的支持。因为执行比编译需要更少的程序信息，所以与第一个目标相比，第二个目标需要IR定义中更多的内容。换句话说，满足第一个目标的IR标准可能无法满足第二个目标的需求。在这一点上也很难说一个定义良好的IR标准是否可以同时满足这两个目的。
异构系统架构(HSA)基金会成立于2012年，通过提出免版税的规范和开源软件，大大简化了异构设备的编程。5它的成员打算建立一个植根于开放的免版税行业标准的异构软件生态系统。
最近，该基金会提出了HSAIL (HSA中间语言)的规范，它被定位为HSAIL虚拟机的ISA，用于计划遵循该标准的任何计算设备。HSAIL是相当低级别的，有点类似于RISC机器的汇编语言。它还假设有一个特定的程序和内存模型，以满足异构平台的需求，其中存在多个isa，其中一个指定为主机。它还指定了作为虚拟机一部分的并行处理模型。
尽管HSAIL与支持基于虚拟机的软件生态系统的愿景相一致，但它的要求太过强烈且缺乏通用性，因此将限制其对其目标计算行业的特定部分的适用性。尽管HSAIL作为编译器开发人员的编译目标，但由于HSAIL虚拟机缺乏简单性，任何编译器都不太可能在编译过程中采用HSAIL作为IR。然而，这是朝着正确方向迈出的一步。
IR设计属性
总之，这里总结了IRs的重要设计属性，以及它们如何与本文讨论的两个愿景相关联。前五个属性是两种视角所共有的。
- 完整性．IR必须提供所有编程语言结构、概念和抽象的清晰表示，以便在计算设备上精确执行。对该属性的一个很好的测试是，它是否可以很容易地在各种编程语言中使用的流行IRs之间进行翻译。
- 语义鸿沟．为了保护知识产权，源语言和IR之间的语义差距必须足够大，以至于无法恢复原始源程序。这意味着IR的水平一定很低。
- 硬件中立．IR必须没有任何特殊硬件特性的内置假设。IR中的任何执行模型都应该反映编程语言，而不是硬件平台。这确保了它可以被编译到最广泛的机器上，并意味着IR的级别不能太低。
- 手动编程．IRs中的编程类似于汇编编程。这让程序员可以选择手工优化他们的代码。它也是一个方便的特性，可以在编译器开发过程中帮助编译器编写者。更高级别的IR通常更容易编程。
- 可扩展性．随着编程语言的不断发展，将会有支持新的编程范式的需求。IR定义应该在不破坏与早期版本的兼容性的前提下为扩展提供空间。
从编译器的角度来看，在编译期间将IR用作程序表示还有三个重要的考虑因素:
- 简单．IR应该拥有尽可能少的结构，同时能够表示从编程语言翻译过来的所有计算。编译器通常执行一个称为规范化的过程，在执行各种优化之前将输入程序转换为规范化形式。拥有尽可能少的表示计算的方法实际上对编译器是有好处的，因为编译器需要覆盖的代码变体更少。
- 程序信息．最完整的程序信息存在于最初编写程序的源形式中，其中一些来自于编程语言规则。除非IR提供对转义信息进行编码的方法，否则从编程语言转换出来将导致信息丢失。示例包括高级类型和指针别名信息，它们不是程序执行所需要的，但会影响在优化期间是否可以安全地执行某些转换。一个好的IR应该在源程序中保留任何有助于编译器优化的信息。
- 分析信息．除了在程序级别上容易获得的信息外，程序转换和优化依赖于编译器对程序分析生成的附加信息。例如数据依赖、usedef和别名分析信息。在IR中编码这样的信息可以让其他编译器组件使用它，但是这样的信息也可以通过程序转换而失效。如果IR对此类分析信息进行编码，则需要在整个编译过程中对其进行维护，这将给转换阶段增加额外的负担。因此，是否对可以通过程序分析收集的信息进行编码是一种判断。为了简单起见，它可以被省略或可选。
一个通用IR的标准能够实现与目标无关的程序二进制分发，并且所有编译器都可以在内部使用，这听起来可能很理想，但这是一个很好的事业，为整个计算行业带来了希望。
相关文章
在queue.acm.org
您的所有数据库都属于我们
埃里克·梅耶尔
http://queue.acm.org/detail.cfm?id=2338507
流处理器:可编程性和效率
William J. Dally, Ujval J. Kapasi, Brucek Khailany, Jung Ho Ahn, Abhishek Das
http://queue.acm.org/detail.cfm?id=984486
使用代码映射进行软件开发
罗伯特·德琳，吉娜·维诺莉娅，还有凯尔·罗文
http://queue.acm.org/detail.cfm?id=1831329
参考文献
1.巴伦(D.W.)。语言及其实现．约翰·威利，1981年。
2.通用中间语言;http://en.wikipedia.org/wiki/Common_Intermediate_Language．
3.CUDA;http://www.nvidia.com/object/cuda_home_new.html．
4.HMPP;http://www.caps-entreprise.com/openhmppdirectives/．
5.HSA的基础;http://www.hsafoundation.com/．
6.Java字节码;http://www.javaworld.com/jw-09-1996/jw-09-bytecodes.html．
7.JVM语言;http://en.wikipedia.org/wiki/List_of_JVM_languages．
8.OpenCL;http://www.khronos.org/opencl/．
9.开源编译器;http://en.wikipedia.org/wiki/List_of_compilers#Open_source_compilers．
©2013 acm 0001-0782/13/12
允许为个人或课堂使用部分或全部作品制作数字或硬拷贝，但不得为盈利或商业利益而复制或分发，且副本在首页上附有本通知和完整的引用。除ACM外，本作品的其他组件的版权必须受到尊重。允许有信用的文摘。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，都需要事先获得特定的许可和/或费用。请求发布的权限permissions@acm.org传真(212)869-0481。
数字图书馆是由计算机协会出版的。版权所有©2013 ACM, Inc.
没有找到条目