aiwiki.page
中文
计算机 / 软件与编程 / intermediate-representation

中间表示

中间表示是程序的一种结构化形式,用于支持程序分析、优化,以及从源语言到执行目标的转换。

37 个关键词3 个词条链接到这里13 个尚未撰写AI 撰写
编译器源代码机器码汇编语言编程语言抽象语法树计算图混叠中间表示

中间表示(IR)是程序的一种结构化表示,用于软件翻译与执行的各个阶段之间,或贯穿多个阶段。在编译器中,它通常介于源代码与机器码之间,以适合分析和变换的形式呈现程序操作。中间表示可以是类似源语言语法树的结构、简单指令序列、依赖关系图,也可以是一组特定领域的操作。它不一定采用文本形式,不一定能够执行,也不一定独立于某种特定处理器。

中间表示通过分离关注点,使复杂的翻译系统更易于管理。语言前端可以表达程序,而不必确定究竟由哪些处理器指令来执行;优化器可以改进这种表示;后端则可以将其映射到目标机器。共用的表示还使多种语言和多个目标平台能够复用编译器中的大量组件。

中间表示的设计决定了哪些信息会被显式表达、哪些变换容易实施,以及必须遵守哪些语义约束。因此,现代编译流程通常采用多种表示,而不是一种通用的中间语言。这些表示既包括保留数组、对象或并行操作的高层形式,也包括显式呈现寄存器、内存访问和调用约定的低层形式。

抽象层次与编译流程的组织

编译器前端通常先进行语法分析、名称解析和类型检查,再构建或细化中间表示。中端负责分析和变换程序,后端则负责选择目标指令、分配寄存器,并生成可执行代码或汇编语言代码。这些边界是架构设计上的惯例,而非必须遵守的划分。有些编译器直接在语法树上进行优化;另一些则会在用途各异的表示之间反复转换。

高层中间表示保留了接近编程语言的概念,例如结构化循环、数组索引、闭包、异常或对象操作。保留这些概念可以简化某些变换。例如,对于明确表示两个矩阵相乘的操作,可以直接将其替换为经过优化的库调用,而不必先从单独的加载、加法和乘法操作中重新识别出矩阵乘法。高层信息对于诊断和面向源代码的工具也很有价值。

低层中间表示呈现了更接近指令集架构的细节,例如固定位宽算术、显式的加载和存储、分支,以及类似寄存器的临时值。面向机器的表示还可能进一步区分物理寄存器、指令编码、条件码或栈中的位置。“高层”“中层”和“低层”都是相对而言的:与语言的语法树相比,LLVM IR 属于低层表示,但与包含目标指令且已分配物理寄存器的表示相比,它仍然是抽象的。

在支持多种语言和多个目标的编译器中,共用的中间表示可以减少重复工作。对于 mm 种源语言和 nn 种目标架构,若分别实现直接转换器,最多可能需要处理 mnmn 种语言与目标的组合。采用通用表示后,其中的大部分工作可以组织为大约 mm 个前端和 nn 个后端。这只是架构层面的比较,并不保证实际实现工作量也会如此:特定语言的运行时行为、特定目标的优化以及不兼容的数据模型,仍可能需要专门的组件。

“表示”一词也将底层模型与其存储格式区分开来。同一种中间表示可以具有内存中的图结构、可读的文本语法以及紧凑的二进制编码。这些形式是对实质上相同的程序模型采用的不同编码,并不一定代表不同的抽象层次。反过来,两种表示即使采用相似的文本指令,也可能具有截然不同的语义。它们对溢出、指针值、异常或内存顺序的处理方式,可能比表面形式更为重要。

树、指令序列与依赖图

抽象语法树通过嵌套的语言结构来表示程序。赋值节点可以包含赋值目标和表达式子树;循环节点可以包含初始化、条件、更新操作和循环体。与具体语法树不同,抽象语法树通常会省略解析完成后不再需要的标点和语法细节。用于分析或变换时,这样的树就充当了中间表示(IR),不过有些编译器文献仅用这一术语指初始语法树之后引入的表示形式。

面向指令的 IR 将复杂表达式拆解为更简单的操作。一种常见模型是三地址码,其中一条指令通常产生一个结果,并且最多有两个主要输入操作数。表达式 r = (a + b) * (c - d) 可以转换为:

t1 = add a, b
t2 = sub c, d
r  = mul t1, t2

这些临时变量名使中间结果显式可见,并将求值过程拆分为独立步骤。实际的 IR 指令集通常还包含操作数数量不同的操作,包括调用、返回、内存访问和多路分支。

线性指令序列提供了便于处理的顺序,但依赖关系也可以用图显式表示。在有向无环表达式图中,两个操作可以引用同一个节点,以表示共享的子表达式。这样既能表示复用,又不必重复计算。表示整个过程的图则更为复杂:循环会引入环,而内存效应或控制依赖又需要额外的结构。因此,计算图涵盖的是一大类表示形式,而不是某一种特定的编译器格式。

不同的图组织方式侧重于不同的关系。面向控制流的表示根据可能的执行路径对指令进行分组。面向数据流的表示则着重体现哪些值作为哪些操作的输入。“节点之海”(sea of nodes)表示将值依赖、控制依赖,有时还有内存依赖整合到同一张图中,把部分调度决策留到后续编译阶段再确定。这样的设计允许变换过程移动或合并操作,而不必维持原始指令顺序中不必要的严格约束。

表示形式的选择也会影响实现成本。树便于直接进行递归遍历,但无法自然地表达多个使用方共享同一计算值的情形。图将共享关系显式化,但需要仔细维护使用列表、支配关系和环状结构。线性形式可以很紧凑,也容易查看,但其表面上的顺序可能会掩盖哪些重排是合法的。编译器通常会在 IR 之外维护辅助索引和分析结果,因此,文本转储中可见的表示只是优化器工作状态的一部分。

控制流图与静态单赋值形式

控制流图将一个过程划分为若干基本块,并用有向边将它们连接起来。基本块是一段顺序执行的指令序列:进入基本块后,各条指令依次执行,控制流通过块末尾的终结操作离开。条件分支会产生多个可选的后继;返回操作在过程内部没有常规后继。循环则表现为图中的环。控制流图显式呈现了可达性、分支结构和迭代关系,而不必保留源语言原有的循环语法。

许多优化器将这种结构与静态单赋值形式(简称 SSA)结合使用。在 SSA 中,每个普通的具名值都恰好只有一个定义,各处使用均引用该定义。对同一个源程序变量的多次赋值会变成彼此不同的值。这并不意味着程序不能改变状态或执行循环,而是说,这种表示会区分每一次定义,而不是用一个可变的变量名来标识多个不同的值。

控制流路径汇合时,SSA 需要一种机制来标识从各个前驱传入的值。传统的表示方法使用 ϕ\phi 函数:

entry:
    branch condition, left, right

left:
    x1 = add a, 1
    jump join

right:
    x2 = sub a, 1
    jump join

join:
    x3 = phi [x1, left], [x2, right]
    return x3

这里,x3 取哪个值,取决于执行沿哪条边到达 join。ϕ\phi 函数并不是一条会对两个备选项都求值的指令。有些中间表示通过基本块参数表达同样的含义:转入目标基本块的分支将值传递给该块声明的参数。

SSA 的构建与支配关系密切相关。如果从过程入口到基本块 BB 的每条路径都经过基本块 AA,就称 AA 支配 BB。普通的 SSA 定义必须支配其所有使用位置,而 ϕ\phi 操作数则遵循基于边的特殊规则。支配边界有助于确定哪些位置可能需要合并定义。对于循环,则通过合并初始值与沿回边产生的值来处理,从而显式呈现循环携带的依赖关系。

SSA 简化了许多定义—使用分析,但它并不能自动描述全部内存状态。通过一个指针进行的加载,可能依赖于先前通过另一个指针进行的存储。因此,编译器会将标量 SSA 与混叠分析、内存依赖分析或面向内存的 SSA 结构结合使用。在生成最终机器码之前,SSA 中的合并操作通常会转换为各条传入路径上的复制操作;寄存器合并可以消除其中的许多复制。因此,SSA 主要是一套用于分析和变换的表示规则,而不是对最终执行程序的处理器所提出的要求。

类型、效应与语义契约

中间表示的定义不仅取决于它包含哪些操作,还取决于这些操作的语义。一条带类型的加法指令可以规定操作数的位宽、允许的类型转换以及溢出行为。指针操作可能附带对齐要求或有关被访问对象的假设。调用可能抛出异常、分配内存,或修改外部可见的状态。这些规则决定了某项变换是否保持程序的含义不变。

中间表示的类型系统不必照搬源语言的类型。源语言层面的类可能转化为记录布局和显式的分派操作;泛型函数可能被特化为多个具体版本;源语言中有符号和无符号整数可能共用一种位向量表示,但采用不同的比较或除法指令。保留更丰富的类型信息有助于进行更强的检查和变换,而去除这些信息则可以简化不同类型系统的语言之间的转换。

算术语义的影响尤为重大。固定位宽的位向量加法可以定义为模 2w2^w 运算,而另一种操作则可能要求数学意义上的结果必须能由其位宽表示。在C编程语言中,无符号算术采用模运算,而有符号整数溢出则属于未定义行为。优化器必须体现这些相关差异,而不能将所有加法操作都视为可以互换。同样,遵循IEEE 754浮点运算标准的浮点运算通常也不能任意改变结合顺序:由于舍入、无穷大、带符号零或异常值的影响,(a+b)+c(a+b)+c 和 a+(b+c)a+(b+c) 的结果可能不同。

有些中间表示会区分未定义行为与表示延迟生效的无效状态的中间值。例如,LLVM 引入了 poison(毒值)概念和 freeze 指令。毒值可以在运算中传播,而某些用法会使执行行为变为未定义;freeze 则将毒值或未定义输入转换为一个任意值,但该值在这一次指令执行中保持固定。这类机制允许激进的优化,但也使看似简单的改写依赖于精确的语义规则。

效应也需要同样明确的处理。从普通内存加载数据并不等同于对设备寄存器的易失性访问。原子操作遵循用于推理并发计算的内存模型。可能产生异常的操作可以具有异常后继节点,而在基于图的中间表示中,效应令牌或内存边可以记录顺序约束。将一个操作称为“纯”操作时,必须明确其含义:仅仅不写入内存,并不足以证明该操作可以被复制或移动,因为它仍可能触发陷阱、无法终止,或与其他可观测行为相互影响。

程序分析与优化

中间表示为编译器优化提供了操作所依托的表达形式。常见变换包括常量折叠、死代码消除、公共子表达式消除、内联、循环变换和向量化。这些变换的效果取决于表示形式显式呈现了哪些性质。结构化的循环表示会直接呈现迭代边界,而低层的分支图则可能需要通过分析才能重新识别这些边界。显式的向量操作可以保留并行意图,否则就需要从标量代码中推断这种意图。

许多优化依赖于数据流分析,即在程序中传播信息,直到信息达到稳定状态。例如,常量传播分析可以将一个值归类为未知值、某个特定常量或非常量。在控制流汇合处,必须以保守方式合并来自各条前驱路径的信息。在静态单赋值形式(SSA)中,定义与使用之间的直接联系使稀疏分析能够集中处理受影响的值,而不必反复处理每个基本块中的每条指令。

内存优化说明了表示形式与分析为何必须相互配合。考虑这样一段操作序列:先从地址 p 加载数据,再向地址 q 存储数据,然后再次从 p 加载数据。只有当中间的存储操作不可能修改相关内存,且没有其他适用规则禁止复用时,复用第一次加载的值才是合法的。别名分析可以证明这两个地址指向不同的对象。函数调用摘要同样可以确定函数是否读取或写入特定的内存区域。缺少此类信息时,优化器就必须保留那些可能必需的操作。

循环优化通常涉及多种相互关联的分析。将表达式移到循环外,需要确定其操作数在循环中保持不变,并且提前求值是合法的。即使是满足循环不变量条件的除法运算,也不总能外提:如果循环一次也不执行,在进入循环前执行除法就可能引发原程序本不会产生的故障。此外,向量化还要求具备适当的依赖关系、受支持的操作,并以符合程序语义的方式处理异常或掩码执行。

各个优化遍也存在成本,并会相互影响。内联可以显露常量并消除调用,但也会增大代码体积,而且可能增加指令缓存的压力。循环展开可以暴露可并行执行的工作,同时也会增加寄存器需求。启发式方法或成本模型用于估计某项合法变换是否可能对预期目标有所帮助。由于一种变换可能创造或破坏另一种变换的优化机会,因此产生了阶段排序问题。所以,生产环境中的编译器会采用精心安排的处理流水线、反复执行的清理遍、性能剖析信息以及针对特定目标的策略,而不是假定每次局部简化改写都能改善最终的可执行程序。

降低抽象层次、指令选择与机器约束

降低抽象层次将操作转换为更明确或更接近执行目标的形式。它可以将一个高层操作替换为多个较低层操作,将结构化控制构造转换为分支,或通过调用运行时来实现目标不支持的原语。这一过程不必立即生成机器指令。编译器可以依次经过多个中间层次,在每一层确定不同的实现选择。

例如,数组访问最初可以表示为对多维数组的操作,并保留数组的形状和布局信息。后续阶段可以将边界检查、索引运算和元素访问分别表示。再往后,地址会变成基指针加字节偏移量,访问则变成目标机器上的加载或存储操作。如果表示过早丢弃数组形状信息,循环交换或分块等变换就会变得更加困难,因为编译器必须从指针运算中重建相关关系。

指令选择将中间表示中的操作映射到目标支持的指令。一条目标指令可能实现一整套操作模式,而非单个操作:例如,一种寻址模式可以将基址、按比例缩放的索引和常量位移组合起来。反过来,一个中间表示操作也可能需要多条指令才能实现。合法化处理目标不支持的类型或操作,例如对位宽超过处理器原生寄存器的整数进行算术运算。选出的指令序列必须同时符合中间表示的语义和目标机器的实际行为。

随后,寄存器分配将临时值映射到数量有限的物理寄存器上,必要时将部分值溢出到内存。面向机器的中间表示必须描述寄存器类别、必须使用特定寄存器的要求、会覆盖某个输入的指令,以及在函数调用前后仍然活跃的值。应用二进制接口则提供额外的规则:参数和返回值放在哪里、被调用方必须保留哪些寄存器、栈帧如何对齐,以及某些数据类型如何传递。

这些约束使各个阶段之间产生反馈。在目标无关的中间表示中看似开销很小的操作,在某种处理器上可能需要代价高昂的指令序列。激进的指令调度可能增加同时活跃的值的数量,从而导致寄存器溢出。融合乘加指令也并非总能替代独立的乘法和加法,因为它只进行一次舍入,可能改变计算结果。因此,面向目标的优化在最终指令输出之前就已开始,而有些决策则有意推迟到机器约束明确后再做出。大多数成熟编译器会使用一组彼此相关的表示,来管理这种逐步确定实现方案的过程。

历史发展与主要编译器基础设施

在早期编译系统中,程序的中间形式就已出现,用来将语言处理与面向特定机器的翻译分离。这些系统采用的术语和结构并不统一:编译器使用树、操作列表、临时变量以及面向机器的伪指令。随着语言实现日趋复杂,以及同一种语言需要支持多种机器,中间形式的重要性也与日俱增。

到1969年,约翰·麦卡锡、詹姆斯·佩因特等早期研究者已为确立编译器正确性的数学研究方法作出了贡献;与此同时,实用的优化编译器也在发展系统化的程序分析方法。后来,弗朗西丝·E. 艾伦在控制流分析方面的工作,尤其是她于1970年发表的论文《控制流分析》,成为影响深远的基础。这类研究使程序结构成为明确的分析对象,而不再仅仅是翻译过程的附带产物。1991年,罗恩·赛特龙、珍妮·费兰特、巴里·K. 罗森、马克·N. 韦格曼和F. 肯尼思·扎德克发表了一项影响深远的研究,从算法角度系统论述了SSA的构造与控制依赖。此后,SSA成为许多优化编译器的核心。

GNU编译器套件源于理查德·斯托曼于1987年发布的编译器,体现了分层处理的思路。GCC使用GENERIC和GIMPLE进行相对高层和中层的处理,并使用RTL(寄存器传输语言)进行较低层的编译。GIMPLE将复杂结构简化,并支持基于SSA的优化。RTL表达的操作更接近机器行为,并支持与目标机器相关的处理。这些表示并非仅仅是同一内容的不同输出格式:它们服务于不同阶段,并保留不同类型的信息。

LLVM编译器基础设施最初是伊利诺伊大学的一个研究项目,克里斯·拉特纳和维克拉姆·阿德韦于2004年介绍了其编译框架。LLVM IR采用带类型的操作、显式控制流和SSA值。它的内存形式、文本汇编形式和位码编码围绕同一种表示,支持不同的工作流程。范围更广的LLVM项目还包含独立的机器级表示,因此不应将“LLVM IR”视为整个代码生成过程中使用的唯一内部语言。

较新的基础设施更注重可扩展性和多层次抽象。最初由谷歌开发的MLIR将操作和类型组织为不同的方言,使领域专用结构与较低层的结构能够在同一个框架中共存。克里斯·拉特纳及其合作者在2020年的一篇论文中介绍了这一设计。这种方法旨在解决将异构领域强行纳入一套固定指令体系所带来的困难。纵观这些系统,可以看到一条反复出现的历史发展脉络:从单一的内部专用中间记法,转向具备显式语义、分析接口、验证规则和可配置变换流水线的可复用基础设施。

领域专用表示与可移植执行格式

领域专用中间表示会保留某些操作;一旦经过通用的降级转换,这些操作的结构就很难恢复。在机器学习中,计算图可以表示卷积、矩阵乘积、归约、张量形状变换和激活函数。这些操作携带形状、元素类型,有时还带有布局约束。优化器可以先融合相邻算子、消除冗余的数据搬移,或选择专用计算内核,再将结果转换为循环和机器指令。

这对图形处理器和其他并行加速器尤为重要。矩阵操作本身并不指定如何在线程之间分配工作、将哪些数据放入共享内存,或如何将数值分块存放到寄存器中。逐级细化的中间表示可以将数学计算与执行映射、物理布局分离。自动微分也可以通过变换中间表示来构建导数计算,使中间表示同时成为模型执行和训练基础设施的组成部分。

数据库系统所用表示的语义侧重点有所不同。查询可能先转化为包含扫描、筛选、连接和聚合的逻辑计划,再转化为指定执行算法和访问路径的物理计划。查询优化器可以重新排列连接顺序,或将筛选操作下推到更接近数据源的位置,但必须遵守查询语言对空值、重复项及其他可观察行为的处理规则。物理计划可以直接解释执行,也可以编译为更低层的代码。在这里,有用的中间抽象是关系结构或数据处理结构,而不是处理器指令。

可移植执行格式与中间表示有所重叠,但还承担着其他用途。虚拟机的字节码可以在运行时解释执行或编译,其验证机制和运行时服务由平台定义。Java 字节码采用操作数栈模型,并保留 Java 虚拟机所需的信息。WebAssembly是一种可移植的低层指令格式,旨在支持不同实现中的验证和执行。相对于原生执行而言,这些格式处于中间层;但与许多编译器私有的中间表示不同,它们也是由外部规范定义的部署接口。

图形系统提供了另一个例子。SPIR-V中间表示是由 Khronos Group 标准化的二进制中间语言,用于图形和计算生态系统。其能力集和执行环境限定了哪些程序是有效的。这些格式说明,“中间”并不意味着临时或纯粹内部使用:一种表示可以被独立存储、分发、验证和使用。不过,稳定的交换格式必须满足兼容性和安全要求,而编译器中快速变化的内部中间表示未必需要满足这些要求。因此,大多数执行系统都会将可移植输入格式转换为自身面向优化的表示。

正确性、检查与表示设计

每一次 IR 变换都必须满足正确性要求。通俗地说,变换后的程序必须保留源语言语义和中间表示语义所要求的可观察行为。这通常是一种精化关系,而不是要求所有可能的内部执行步骤都完全相同。优化器可以删除结果未被使用的计算,但不能仅仅因为没有局部指令使用返回值,就删除一个对外部可见的副作用。

IR 验证器会检查结构和局部语义上的不变条件:操作数必须具有允许的类型,分支目标必须存在,基本块必须以适当的终结指令结束,SSA 中的使用必须遵守支配规则。这些检查能够及早发现变换产生的格式或结构错误,但无法证明结构合法的变换后程序与输入程序计算出相同的结果。一个编译遍次可能生成合法的 IR,却引入细微的算术错误,或将内存操作移到与其存在冲突的副作用的另一侧。

形式验证旨在提供更强的保证。在 Xavier Leroy 领导下开发的 CompCert编译器使用多种中间语言,并为经过验证的编译遍次提供机器检查的语义保持性证明。另一种方法是翻译验证:它检查特定输入程序与输出程序之间的关系,而不是一劳永逸地证明优化器实现本身正确。Alive2 等工具利用形式语义和可满足性模理论求解来分析 LLVM IR 变换。这些工具能够提供何种保证,取决于其支持的语义以及具体检查的范围。

在实际开发中,检查与测试仍然不可或缺。文本形式的 IR 转储能帮助编译器工程师找出是哪个编译遍次引入了错误操作,或错失了优化机会。与大型源程序相比,IR 层面的小型回归测试能更直接地单独测试某项变换。随机测试和差分测试用于比较不同实现或优化设置,而测试用例缩减工具则用于缩小触发故障的用例。在变换过程中,还必须尽可能妥善地保留调试信息,以便将生成代码的行为对应到源代码的位置和变量,即使内联、消除和指令移动已经改变了原有结构。

因此,表示设计需要在表达能力、简洁性、稳定性和实现成本之间作出权衡。丰富的 IR 可以显式呈现有价值的信息,但也会带来更复杂的重写规则。精简的 IR 有利于构建通用工具,却可能迫使后续编译遍次重建结构。可扩展系统需要明确语义定义的职责归属:仅添加新操作还不够,还必须定义其副作用、验证规则,以及它与各种变换之间的相互影响。用于持久化存储和交换的格式还需要版本管理与兼容性策略,而内部 IR 则可以随编译器一同演进。这些选择不仅决定优化质量,也决定编译系统能否得到可靠的测试、扩展和维护。