前言
这里是编译器设计读书笔记第 2 部分, 前一部分的位置在这里.
第 4 章 上下文相关分析
老规矩, 先来看一堆概念.
上下文相关分析, 又称语义推敲, 按我理解, 就和之前的词法分析, 语法分析一样, 上下文相关分析也是编译器的一趟处理; 在这里, 编译器会收集更多与源代码相关的信息, 并基于这些信息做一些处理, 比如来判断源程序是否符合语义; 毕竟语法分析通过只是意味着源程序符合语法, 并不意味着源程序符合语义, 如在 C 语言中, 但从语法角度来看, 代码片段: "hidva.com" + 33 是符合表达式语法的, 是能通过语法分析的, 但是很显然不符合语义, 无法通过语义检查.
属性语法; 属性语法是用来进行上下文相关分析的一种机制, 属性语法更像是学术界搞出来的玩意儿, 在现实世界的编译器中很少会使用属性语法来进行上下文相关分析的. 属性语法就是属性化的上下文无关语法, 等同于上下文无关语法加上一些属性规则. 这些规则与特定的产生式关联, 为产生式中特定的符号定义了属性以及属性的取值. 这里的属性是指, 如果把产生式中语法符号视为一个对象的, 属性就是指对象的数据成员. 规则在定义语法符号属性的取值时可能会使用其他语法符号某些属性的值, 此时就建立了一种依赖关系(又称定义了一个依赖项), 描述起来就是语法符号 A 的属性 i A.i 依赖语法符号 B 的属性 j B.j; 所有规则定义的依赖项会形成属性依赖关系图. 在不存在循环依赖的情况下, 属性依赖关系图会是一个 DAG, 若属性依赖关系图中存在环, 则表明存在循环依赖的情况, 此时属性语法认为是病态的. 综合属性, 继承属性, 其定义参见原文.
属性语法的求值; 在编译器完成语法分析生成语法分析树后, 为树中每一个必要的节点创建一个属性实例, 存放着属性规则为该符号定义的属性, 此时在属性实例中, 属性的取值尚未被确定. 然后根据属性依赖关系图定义的依赖关系开始逐一地对属性进行求值.
特设语法制导转换; 也是用来进行上下文相关分析的一种机制, 而且也是现实世界的编译器常用的一种操作, 如此拗口的名字是怎么起出来的!. 其大致形式就是定义一组与特定产生式关联的操作, 然后在语法分析器完成对相关产生式的归约之后执行相关的操作, 就像是为每一个产生式都定义一个类似 OnXXX 的 callback, 然后语法分析器在完成归约之后会调用该 callback.
特设语法制导转换中操作之间值是如何传递的? 参见原文图 4-11, 这其中值 val 是如何传递的呢? 在属性语法中, 通过将属性保存在语法分析树的节点中来在属性规则之间进行值的传递. 而在特设语法制导转换中, 语法分析树一般不会显式构建, 所以只能将值保存在语法分析器的内部栈之中, 并以此来实现在操作之间值的传递, 具体操作参考原文. 值的引用, 在产生式关联的操作之中, 通过 \($_i\) 来引用第 i 个右侧符号对应的值, 会将符号 $$ 的取值作为产生式左侧符号对应的值压入栈中.
如果想要在每次移进时也执行指定的 callback 该咋整? 根据上面的介绍, callback 只能在归约一个产生式时执行, 所以如果想要在每次移进时都执行 callback, 具体姿势参见原文.
第 5 章 中间表示
中间表示; IR; 是一种数据结构, 用来存放当前编译器推导出来的所有信息. 从宏观上来看, 编译器编译的整个流程是由若干趟处理组成的, 每一趟处理的输入是一种形式的 IR, 输出是另外一种形式的 IR. 本章主要介绍各种形式的 IR, 并未详细介绍每种 IR 详细结构, 存放了哪些数据; 可能是由于 IR 都是与特定的处理阶段关联的, 所以特定 IR 的生成以及如何使用会放在后续特定的章节来描述.
对 IR 的要求: 编译器使用的 IR 必须有足够的表达力, 才能记录各趟之间传递的所有事实. IR 提供的操作要足够高效, 毕竟编译器操作大头都在与 IR 的交互中. IR 还要尽量保持可读性以及可调试性.
IR 具有的属性; 可以从结构性的组织, 抽象层次, 命名规范三个维度来描述 IR. 结构性组织属性描述了 IR 的结构, 由于部分大佬认为树和图是程序的自然表示, 所以有树形 IR, 图形 IR. 又由于大多数处理器的本机语言都是线性的汇编语言, 所以又有线性 IR, 线性 IR 一般是某个抽象 CPU 的汇编代码. 最后为了获取图形 IR 与线性 IR 的优势而避免其弱点, 又整出来图形线性混合型 IR. 抽象层次描述了 IR 所处地抽象层, 一般可以用 IR 中一个操作对应着目标处理器多少条指令来衡量一个 IR 所处地抽象层次; 比如高抽象层次的 IR 中一个操作可能需要由多条处理器指令来实现, 而低抽象层次的 IR 中, 可能多个 IR 中操作才对应着一条处理器指令; IR 抽象层次越低, 暴漏出来地细节就越多, 优化空间就越大; 毕竟编译器只能根据 IR 暴漏出来的细节来进行优化. 命名规范用来规定如何为 IR 中的各种值起一个名字, 比如一个用来表示表达式的 IR 中可能会有多个临时变量, 命名规范指定了如何为这些临时变量起个适合的名字, 本来我以为这是个很随意地事呢, 后面来看可不简单呐.
5.2 图 IR
语法分析树; 语法分析树也是一种 IR 哟, 语法分析树相关知识参见之前语法分析的介绍.
AST, 抽象语法树 Abstract Syntax Tree, 是语法分析树的简化版本, 将语法分析树中对编译器其余部分没有实质用途的节点抽象掉; 参见原文中表达式 “a * 2 + a * 2 * b” 对应的语法分析树以及 AST, AST 是真的抽象掉不少节点啊. 参见原文 4.4.2 节第 3 部分来了解如何在语法分析过程中建立 AST.
DAG, 有向无环图, DAG 是具有共享机制的 AST, 这里的共享是指 AST 中相同的子树只会实例化一份, 当然编译器要确保此时子树的合并不会更改源程序的语义. 还是根据表达式 “a * 2 + a * 2 * b” 举例, 由于这时可以证明两个 ‘a * 2’ 的计算结果是相同的, 因此可以只创建一个 ‘a * 2’ 的子树, 此时的 DAG 参见原文. 但是对于表达式 ‘a * 2 + (a = 33) + a * 2 * b’ 而言, 由于无法证明此时两个 ‘a * 2’ 计算结果相同, 所以此时不能共享 ‘a * 2’ 对应的子树.
基本程序块, 前导指令; 基本程序块是具有最长长度的无分支代码序列, 基本程序块中第一条指令被称为是前导指令. 在 CFG 中, 控制流仅能转移到某个基本程序块的前导指令上, 即基本程序块中除前导指令之外的指令不允许被控制流直接跳转的. 按我理解如果允许控制流直接跳转到基本程序块中某条指令 i, 那么在对该基本程序块中的指令进行编译期乱序时, 指令 i 就像是一个 barrier 了, 指令 i 之后的指令不能乱序到指令 i 之前, 指令 i 之前的指令也不能乱序到指令 i 之后, 很显然这增加了复杂性. 基本程序块基本上使用线性 IR 来表示.
CFG, 控制流图, 每一个 CFG 是一个有向图 G=(N, E); 其中每个节点 n 对应着一个基本程序块; 每条边 \(e = (n_i, n_j) \in E\) 对应于从块 \(n_i\) 到块 \(n_j\) 的一个可能控制转移. CFG 生成算法会确保最终生成的 CFG 只有一个入口, 一个出口, 若在程序的源代码中, 与该 CFG 对应的部分有多个入口或多个出口, 那生成算法会通过插入额外的节点与边确保最终生成的 CFG 只有一个入口, 一个出口.
单语句块, 对应于源代码层次上单一语句的代码块. 这里语句的概念之前在这里介绍过, 语句表明一个完整的执行单元. 某些 CFG 的节点可能是一个单语句块.
数据依赖关系图; 数据依赖关系图表示了值从定义到使用的流动, 这里的定义并不是 C 语言中那种变量定义, 此时会把每一次对变量的赋值都视为对变量的重新定义. 在数据依赖关系图中, 节点表示操作, 操作包括了值的定义以及使用, 可以认为节点是个单语句块, 使用了一个或多个变量的值来定义一个或多个变量. 数据依赖关系图中的边从定义变量 i 的节点指向使用变量 i 的节点. 参见原文图 5-3 了解数据依赖关系图大致形式, 注意这里 \(r_arp\) 是隐式定义, 但是被显式使用的. 数据依赖关系图同时也以偏序的形式指定了操作必须遵守的执行次序, 此时编译器或 CPU 可以在保证这种偏序的情况下任意调整操作的顺序从而来最大程度地利用 CPU.
过程间技术, 过程内技术; 定义参考原文了解一下即可.
调用图; 表示运行时过程之间的控制转移. 此时每个节点表明调用过程. 每个边表明一种可能的调用位置. 在某些情况下, 源代码中可能会以函数指针的形式来调用函数, 此时的调用位置被称为二义性的调用位置.
5.3 线性 IR
老规矩, 还是先看一波概念. 按我理解, 原文这里使用的 ‘操作’ 概念大概就是 CPU ‘指令’ 的意思吧.
采纳分支, 非采纳分支(落空分支), 概念参考原文, 这里 ISA 是指令集架构的意思.
破坏性操作; 破坏性的操作总会使用操作的结果来重新定义一个操作数, 即总会使用其中一个操作数来保存操作结果. 如 X86 的 ADD 指令 就是一个破坏性操作.
常见的线性 IR: 单地址, 二地址, 三地址; 按我理解, 这里的 ‘地址’ 是指指令所能接受操作数数目的意思, 单地址是指指令仅能接受一个操作数, 二地址指指令可以接受 2 个操作数等. 每一种线性 IR 都或多或少能看出现实世界中某款类型的计算设备的影子, 如从单地址线性 IR 中可以看到累加器, 堆栈机的影子, 从 3 地址线性 IR 中能看出 RISC 机器的影子等.
堆栈机代码, 是一种单地址线性 IR. 堆栈机的模型, 堆栈机假定操作数存放在栈中, 堆栈机提供的大部分指令会依据指令所需操作数的数目从栈中弹出相应的元素, 然后运算并将结果压入栈中. 堆栈机代码的形式可以参考原文了解一波. 堆栈机中的栈本身建立了一个隐式的命名空间, 从而消除了 IR 中的许多名字, 比如在堆栈机代码中就不需要为 ‘a - 2 * b’ 中 ‘2 * b’ 产生的临时变量再整个名字了; 所以这能大幅缩减 IR 形式下代码的大小.
字节码; 说实话我也一直好奇为啥是叫字节码, 主要原因参考原文.
三地址代码; 三地址代码是什么, 之前已经介绍过了; 关于三地址代码的优点可以参考原文了解一下. 另外再看一下原文举得 mvcl 例子了解三地址代码中也会使用一些高抽象层次的操作.
三地址代码的表示; 在三地址代码的表示中, 使用 Tuple 来存放三地址代码中一条指令, Tuple 中包括一个 opcode, 表明操作码, 以及一个操作数列表, 存放着操作所需操作数集合. 三地址代码的表示可以使用 std::vector<Tuple>, std::vector<Tuple*>, std::list<Tuple>, 这三种结构各自具有优缺点, 可以参考原文简单了解一下.
5.4 将值映射到名字
在编译器中, 给代码生成的各种临时变量取名可真不是一件随意的事儿啊~
SSA, 静态单赋值形式; 是一种命名规范, 其规定每个名字唯一对应着代码中特定的定义位置, 即是说每次重新定义变量时都需要使用一个新的名字来标识着本次定义, 即此时每个名字标识的变量仅会被赋值一次之后值就保持不变, 这可能也是 SSA 中 ‘单赋值’ 的来源. 所以在使用 SSA 的前提下, 当编译器在表达式地不同位置看到 ‘t4 + t5’ 时, 编译器就知道了这些位置的 ‘t4 + t5’ 总会生成相同的结果. SSA, 也是一种 IR, 虽然我是怎么都觉得不想, 但既然原文那么说了, 我就只能想着法子圆了. 毕竟在使用 SSA 时, 名字本身也编码了编译器推导出来的一些信息: 值不会再次被改变了.
程序符合 SSA 所要遵守的约束: 参考原文, 很明显就是根据 SSA 的约定来定义的.
程序的 SSA 改造, 这里程序一般是某个线性 IR; 这里关于改造原文说的很含糊, 可以参考原文简单了解一下, 具体详细改造算法原文在后续章节也给出了.
后语
至此, 关于对编译器设计这本书的学习就告一段落了; 主要是从我自身需求出发, 我只需要编译器设计这本书前 5 章的知识, 后续章节会放在以后有空的时候慢慢学习了.
参考
编译器设计, 第 2 版.
