PDF跨语言互操作性的挑战
中间表示在编译器中日益增长的重要性
Fred Chow
程序编译是一个复杂的过程。编译器是一种软件程序，它将高级源代码程序翻译成可以在计算机上执行的形式。在编译器的早期发展过程中，设计者引入了IR（中间表示，也常被称为中间语言）来管理编译过程的复杂性。使用IR作为编译器内部的程序表示，使得编译器可以分解为多个阶段和组件，从而受益于模块化。
IR是任何可以表示程序而不会丢失信息的数据结构，以便可以准确地执行程序。它充当编译器组件之间的通用接口。由于其使用是编译器内部的，因此每个编译器都可以自由定义其IR的形式和细节，并且其规范只需要编译器编写者知道。它的存在可以是编译过程中的瞬态，也可以输出并作为文本或二进制文件处理。
IR对编译器的重要性
IR应该是通用的，以便它能够表示从多种语言翻译而来的程序。编译器编写者传统上将编程语言的语义内容称为高层。机器可执行代码的语义内容被认为是低层，因为它只保留了原始程序中足够的信息以允许其正确执行。从其较低级的形式重新创建源代码程序将是困难的（如果不是不可能的）。编译过程需要逐步降低程序表示的级别，从高级人类编程结构到低级真实或虚拟机器指令（图1）。为了使IR能够表示多种语言，它需要更接近机器级别，以表示所有语言的执行行为。机器可执行代码通常更长，因为它反映了执行所发生的机器的细节。
一个设计良好的IR应该可以翻译成不同的形式，以便在多个平台上执行。对于在目标处理器或CPU上执行，它需要翻译成该处理器的汇编语言，这通常是与处理器机器指令的一对一映射。由于存在具有不同ISA（指令集架构）的不同处理器，因此IR需要比典型的机器指令级别更高，并且不应假定任何特殊的机器特性。
使用IR使得编译器能够支持多个前端，这些前端从不同的编程语言进行翻译，以及多个后端，为不同的处理器目标生成代码（图2）。执行平台也可以是解释性的，即其执行由软件程序或虚拟机进行。在这种情况下，执行媒介可以在比汇编代码更高的级别，同时低于或等于IR的级别。
IR的采用使得可以将编译过程模块化为前端、中端和后端。前端专门处理编译器的编程语言方面。编程语言实现者只需要实现将语言准确地翻译成IR，就可以宣布工作完成。
后端考虑目标机器的特性，并将IR翻译成将在硬件上执行的机器指令。它还转换代码以利用任何有利于性能的硬件功能。通过从IR开始其翻译，后端实际上支持生成IR的不同语言。
中端是进行目标无关优化的阶段。中端阶段对IR执行不同的转换，以便程序可以更有效地运行。由于对IR的优化通常对所有目标都有利，因此IR在执行目标无关的优化转换方面起着重要作用。在这个角色中，其设计和规范变得更加重要。它需要编码任何有助于优化任务的源代码程序信息。IR的设计对优化效率有影响，而优化是编译过程中最耗时的部分。在现代编译器中，IR决定了编译器的基础设施和总体工程。对IR的任何重大更改都可能意味着编译器实现的重大改动。
不同的IR形式
IR的最低要求是提供足够的信息以正确执行原始程序。IR中的每个指令通常表示一个简单的操作。IR应该比任何典型的编程语言都具有更少的构造种类，因为它不需要功能丰富来方便人类的编程使用。编译器希望看到相同的编程构造或习惯用法被翻译成IR中的统一代码序列，而不管它们的源语言、编程风格或程序员选择的编码方式如何。在IR中强制使用规范形式减少了编译器在执行代码生成和优化时必须处理的代码模式的多样性。由于其对程序的更细粒度的表示，IR的指令可以多对一地映射到机器指令，因为一个机器指令可以执行多个操作，例如乘加或索引寻址。
IR的形式可以分为分层或扁平两种。分层IR允许嵌套结构。在典型的编程语言中，程序控制流（例如，if-then-else，do-loops）和算术表达式都是嵌套结构。因此，分层IR在形式上更接近典型的编程语言，并且被认为是更高级别的。分层IR可以在内部以树的形式（编译器首选的数据结构）表示，而不会损失准确性。
扁平IR通常被视为抽象或虚拟机指令。这些指令按顺序执行，就像在典型的处理器中一样，控制流由分支或跳转指令指定。每个指令接受多个操作数并产生一个结果。这种IR通常被指定为编译器构造教学中的编译目标。
介于分层IR和扁平IR之间的是抽象堆栈机器的语言。在堆栈机器中，算术计算的每个操作数都由一个将操作数压入堆栈的指令指定。每个算术表达式的求值都在从堆栈顶部弹出的操作数上完成，随后的结果被压回堆栈。IR的形式是扁平的，控制流由显式分支指令表示，但是用于算术计算的指令序列可以被视为对应于逆波兰表示法，它可以很容易地在内部以树数据结构表示。使用堆栈机器的语言作为IR一直是常见的做法，从为Pascal定义的第一个IR（称为p-code）1 到当今的Java字节码6 或CIL（通用中间语言2）。
除了表示代码执行之外，还有与IR互补的信息用于其他目的。编译器将原始程序中的命名空间编译成符号名称的集合。变量、函数和类型信息属于这些符号表，它们可以编码控制某些优化转换合法性的信息。它们还提供各种工具（如调试器和程序分析器）所需的信息。符号表可以被认为是IR的辅助工具。
C语言已被用作许多编程语言的翻译目标，因为它作为系统编程语言被广泛使用，并且能够表示任何机器操作。C语言可以被视为IR，因为它相对于大多数语言来说级别较低，但它并非旨在方便编译器操作或直接解释。尽管如此，许多IR的设计都紧密地模仿了C语言的语义。事实上，可以通过仔细剥离C语言的高级控制流结构和结构化数据类型，仅留下其原语，就可以构建一个良好的IR。许多IR也可以翻译成类似C语言的输出，以便编译器开发人员轻松阅读。然而，这种类似C语言的IR通常无法翻译成可以重新编译的C程序，因为C语言在表示某些编程概念（如异常处理、溢出检查或函数的多个入口点）方面存在缺陷。
用于程序交付的IR
随着联网计算机的广泛使用，人们很快理解了处理器和操作系统中立的执行媒介的优势。程序可以在任何机器上运行，分发和交付过程更加容易。这种一次编写，随处运行的方法可以通过虚拟机执行模型来实现，以适应系统硬件的多样性。
与编译执行相比，解释性执行会导致一定的性能损失，最初，它仅对非计算密集型应用程序有意义。然而，随着机器变得越来越快，一次编写，随处运行方法的优势在许多应用程序中超过了潜在的性能损失。这促成了Java等可以普遍部署的语言的流行。Java语言定义了Java字节码，这是一种IR形式，作为其分发媒介。只要安装了JVM（Java虚拟机）软件，Java字节码就可以在任何平台上运行。另一个例子是CIL，它是.NET Framework使用的CLI（公共语言基础设施）运行时环境的IR。
随着移动互联网的增长，应用程序通常被下载到手持设备上以立即运行。由于IR比机器可执行文件占用更少的存储空间，因此它们减少了网络传输开销，并实现了硬件无关的程序分发。
即时编译
随着虚拟机执行模型获得广泛接受，找到加速执行的方法变得重要。一种方法是JIT（即时）编译，也称为动态编译，它通过在执行期间将解释型程序编译为本机代码来加速底层机器上的执行，从而提高了解释型程序的性能。由于运行时编译会产生开销，从而减慢程序执行速度，因此只有在执行时间的减少很可能超过额外的编译时间时，才应谨慎地采用JIT路线。此外，动态编译器不能花费太多时间优化代码，因为优化产生的开销比翻译成本机代码要大得多。为了限制动态编译引起的开销，大多数JIT编译器仅编译执行期间最常采用的代码路径。
动态编译确实比静态编译有一些优势。首先，动态编译可以使用实时分析数据来更有效地优化生成的代码。其次，如果程序行为在执行期间发生变化，动态编译器可以重新编译以调整代码以适应新的配置文件。最后，随着共享（或动态）库的普遍使用，动态编译已成为执行整个程序分析和优化的唯一安全手段，其中编译范围跨越用户代码和库代码。JIT编译已成为许多以IR作为输入的虚拟机的执行引擎不可或缺的组成部分。目标是使为机器无关分发构建的程序的性能接近静态编译器生成的本机代码的性能。
近年来，计算机制造商已经意识到，计算性能的进一步提高不能再依赖于时钟频率的提高。这催生了专用处理器和协处理器，它们可以是DSP（数字信号处理器）、GPU或在ASIC（专用集成电路）或FPGA（现场可编程门阵列）中实现的加速器。计算平台甚至可以是异构的，其中不同类型的计算被移交给不同类型的处理器，每个处理器都有不同的指令集。特殊的语言或语言扩展，例如CUDA，3 OpenCL，8 和HMPP（混合多核并行编程），4 及其底层编译器，旨在使程序员更容易在异构环境中获得最大性能。
由于这些专用处理器旨在提高性能，因此必须将程序编译为在其本机指令中执行。随着专用硬件的普及速度加快，编译器供应商不可能为市场上存在或即将出现的多样化处理器提供定制支持。在这种情况下，定制硬件制造商负责提供后端编译器，该编译器将IR编译为定制机器指令，并且平台无关的程序交付变得更加重要。在实践中，IR可以在更早的时候编译，在安装时或在程序加载时，而不是在执行期间。如今，术语AOT （提前编译），与JIT相对，描述了在执行之前将IR编译为机器代码的过程。无论是JIT还是AOT，IR显然都在这种提供高性能计算平台的新方法中发挥着促进作用。
标准化IR
到目前为止，IR一直与各个编译器实现相关联，因为大多数编译器都以它们使用的IR而区分。然而，IR是可翻译的，并且可以将编译器A的IR翻译为编译器B的IR，因此编译器B可以从编译器A的工作中受益。随着过去二十年中开源软件的趋势，越来越多的编译器已经开源。9 当编译器变为开源时，它会向世界公开其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编译在特定平台上呈现可执行状态。可以指定一组合规性测试。软件供应商将只需要以这种媒介分发其软件产品。支持此标准的计算设备将能够运行以这种形式分发的所有软件。这种标准化的软件生态系统将为不同类型处理器的制造商创造公平的竞争环境，从而鼓励硬件创新。
• 编译器互操作性。具有优化的编译领域是一个难题。没有哪个编译器可以声称在所有方面都表现出色。编译器使用的算法可能对一个程序有效，但对另一个程序则不然。因此，开发编译器需要付出巨大的努力。即使对于已完成的编译器，仍然可能存在无数被认为是理想的增强功能。到目前为止，每个生产质量的编译器都在独立运行。本文讨论了IR翻译作为允许编译器协同工作的一种方式。如果标准IR被编译器创建者采用，则可以结合使用它的不同编译器的优势。这些编译器将不再需要合并完整的编译功能。它们可以作为编译模块进行开发和部署，它们的创建者可以选择使模块成为专有模块或开源模块。如果编译器模块想要使用其自己独特的内部程序表示，它可以选择仅将标准IR用作交换格式。标准IR将降低编译器编写者的入门门槛，因为他们的项目可以以较小的规模构思，从而使每个编译器编写者都可以专注于他或她的专业领域。IR标准还将使编译器之间的比较更容易，因为它们将生成相同的IR作为输出，这将导致更精细的调整。IR标准可以彻底改变当今的编译器行业，并将很好地服务于编译器编写者的利益。
此处概述了IR标准的两种愿景：第一种愿景以计算行业为中心，第二种愿景以编译器行业为中心。第一个愿景强调虚拟机方面，第二个愿景侧重于为编译的不同方面提供良好的支持。由于执行所需的程序信息少于编译，因此第二个目标将需要IR定义中比第一个目标更多的内容。换句话说，解决第一个目标的IR标准可能无法满足第二个目标的需求。目前也很难说一个定义明确的IR标准是否可以同时满足这两个目的。
HSA（异构系统架构）基金会成立于2012年，其章程是通过提出免版税规范和开源软件，使异构设备的编程变得异常容易。5 其成员打算建立一个扎根于开放免版税行业标准的异构软件生态系统。
最近，该基金会提出了HSAIL（HSA中间语言）的规范，HSAIL被定位为HSAIL虚拟机的ISA，适用于计划遵守该标准的任何计算设备。HSAIL相当低级，有点类似于RISC机器的汇编语言。它假定特定的程序和内存模型，以适应存在多个ISA的异构平台，其中一个ISA被指定为主机。它还指定了并行处理模型作为虚拟机的一部分。
尽管HSAIL与基于虚拟机的软件生态系统的愿景相一致，但其要求过于严格且缺乏通用性，因此将限制其在它所针对的计算行业的特定领域中的适用性。尽管HSAIL旨在作为编译器开发人员的编译目标，但由于HSAIL虚拟机的缺乏简单性，任何编译器都不太可能采用HSAIL作为编译期间的IR。然而，这是一个朝着正确方向迈出的一步。
IR设计属性
总之，以下是IR的重要设计属性的摘要，以及它们如何与此处讨论的两个愿景相关。前五个属性是两个愿景共有的。
• 完整性。 IR必须提供所有编程语言构造、概念和抽象的清晰表示，以便在计算设备上准确执行。此属性的一个良好测试是它是否可以轻松地与当今使用的各种编程语言的流行IR相互翻译。
• 语义差距。源语言和IR之间的语义差距必须足够大，以至于不可能恢复原始源代码程序，以便保护知识产权。这意味着IR的级别必须较低。
• 硬件中立性。 IR不得内置任何特殊硬件特性的假设。 IR中明显的任何执行模型都应反映编程语言，而不是硬件平台。 这将确保它可以编译到最广泛的机器，并意味着IR的级别不能太低。
• 手动可编程。使用IR编程类似于汇编编程。这使程序员可以选择手动优化他们的代码。这也是一个方便的功能，有助于编译器编写者在编译器开发期间进行开发。更高级别的IR通常更容易编程。
• 可扩展性。随着编程语言的不断发展，将需要支持新的编程范例。IR定义应为扩展提供空间，而不会破坏与早期版本的兼容性。
从编译器的角度来看，还有三个属性是重要的考虑因素，以便将IR用作编译期间的程序表示
• 简洁性。 IR应该具有尽可能少的构造，同时仍然能够表示从编程语言翻译而来的所有计算。编译器通常执行一个称为规范化的过程，该过程在执行各种优化之前将输入程序按摩成规范形式。尽可能少地表示计算方式实际上对编译器有利，因为编译器要覆盖的代码变化更少。
• 程序信息。最完整的程序信息存在于最初编写程序的源代码形式中，其中一些信息来自编程语言规则。除非IR提供了编码转义信息的方法，否则从编程语言中翻译出来将导致信息丢失。示例是高级类型和指针别名信息，程序执行不需要这些信息，但会影响某些转换是否可以在优化期间安全地执行。良好的IR应保留源代码程序中任何有助于编译器优化的信息。
• 分析信息。除了程序级别可用的信息外，程序转换和优化还依赖于编译器的程序分析生成的其他信息。示例是数据依赖性、use-def和别名分析信息。在IR中编码此类信息使其可供其他编译器组件使用，但是此类信息可能会因程序转换而失效。如果IR编码了此类分析信息，则需要在整个编译过程中维护它，这给转换阶段带来了额外的负担。因此，是否编码可以通过程序分析收集的信息是一个判断性决定。为了简单起见，可以省略或使其成为可选的。
通用IR的标准，可以实现目标无关的程序二进制分发，并且可以在内部被所有编译器使用，这听起来可能很理想化，但这是一个有益的事业，对整个计算行业都充满希望。
参考文献
1. Barron, D. W. (Ed.). 1981. Pascal–The Language and its Implementation. John Wiley.
2. CIL (通用中间语言); 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/openhmpp-directives/.
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.
喜欢它，讨厌它？ 让我们知道
Fred Chow ([email protected]) 开创了第一个用于 RISC 处理器的优化编译器，MIPS Ucode 编译器。 他是 SGI Pro64 编译器的首席架构师，后来开源为 Open64 编译器。 他后来创建了广为接受的 PathScale 版本的 Open64 编译器。 他开发的算法已被当今的编译器广泛采用。 他目前正在 ICube Corp 领导一个新处理器的编译器工作。 他获得了多伦多大学的理学学士学位，以及斯坦福大学的理学硕士和博士学位。
© 2013 1542-7730/13/1000 $10.00
最初发表于 Queue vol. 11, no. 10—
在 数字图书馆 中评论本文
更多相关文章
Matt Godbolt - C++ 编译器中的优化
在向编译器提供更多信息方面需要权衡：这会使编译速度变慢。 诸如链接时优化之类的技术可以为您提供两全其美的优势。 编译器中的优化不断改进，即将到来的间接调用和虚拟函数分派方面的改进可能很快导致更快的多态性。
Ulan Degenbaev, Michael Lippautz, Hannes Payer - 作为合资企业的垃圾回收
跨组件跟踪是一种解决跨组件边界的引用循环问题的方法。 只要组件可以形成具有跨 API 边界的非平凡所有权的任意对象图，就会出现此问题。 CCT 的增量版本在 V8 和 Blink 中实现，从而能够以安全的方式有效且高效地回收内存。
David Chisnall - C 语言不是低级语言
在最近的 Meltdown 和 Spectre 漏洞之后，值得花一些时间来研究根本原因。 这两个漏洞都涉及处理器推测性地执行超出某种访问检查的指令，并允许攻击者通过侧信道观察结果。 导致这些漏洞以及其他几个漏洞的功能被添加进来，是为了让 C 程序员继续相信他们正在使用低级语言编程，而这种情况已经几十年没有发生过了。
Tobias Lauinger, Abdelberi Chaabane, Christo Wilson - 你不应该依赖我
大多数网站都使用 JavaScript 库，其中许多库已知存在漏洞。 了解问题的范围以及包含库的许多意想不到的方式，只是改进情况的第一步。 这里的目标是，本文中包含的信息将有助于为社区提供更好的工具、开发实践和教育工作。
© 保留所有权利。