计算理论与编译原理

参考资料

• 计算理论导引
• 编译原理
• 计算机程序的构造与解释
• 软件分析

计算理论

TODO

编译原理

• 具体优化实现不记录

引论

• 编译器, 解释器, Java 语言处理器等常识

优化

• 软件分析在编译器优化中起着重要作用
• 编译的速度值得注意, 尤其是 JIT
• 对于体系结构的优化
  • 重点是缓存命中 + 流水线
  • 针对向量的优化也很多

一个简单的语法制导翻译器

略, 下文详叙

词法分析

工作

• 去掉空白与注释
• 预读, 因为词法单元对应的词素不一定是一个字符
• 区分常量, 标识符, 关键字

术语

• 词法单元
  • 单元名
  • 属性 (指向符号表的一行的指针)
• 模式
  • 词素的可能形式
• 词素
  • 词法单元的字符串部分

语言是某个字母表上字符串集合的一个子集

• 语言有并, 连接, 闭包, 正闭包操作
• 连接就是把两个语言的串连接起来, 例如 {a, b} * {c, d} = {ac, ad, bc, bd}
• 闭包就是自连接若干次 (连接一次指字母本身构成的串)
• 正闭包就是闭包去掉空串
• 正则表达式, 描述的就是语言

状态转移图

• 每个状态对应当前读取串可能形式
• 每个箭头对应一个字符
• 接受状态对应一个词素
• 针对关键字, 可以在图中添加状态, 也可以在符号表中添加一个特殊的条目
• 多个可选的接受状态选对应词素最长的

Lex 词法分析器生成工具

• 由声明, 转换规则, 辅助函数组成
• 声明
  • 变量与明示常量 (拷贝到生成的 C 代码中)
  • 词法单元的单元名与正则
• 转换规则
  • 正则对应的动作
• 辅助函数
  • 动作的代码实现 (拷贝到生成的 C 代码中)

有穷自动机

• 有穷自动机是识别器, 只能判定串
• 分为确定有穷自动机 (DFA) 和非确定有穷自动机 (NFA)
• NFA 对其边上的标号没有任何限制, 一个符号标记离开同一状态的多条边, 并且空串也可以作为标号
• DFA 反之
• 所有的 NFA 都可以转换为 DFA
  • 子集构造法, DFA 的状态是 NFA 状态的集合
• 有时直接模拟 NFA 效率更高
• McMaughton-Yamada-Thompson 算法将正则表达式转换为 NFA

词法分析优化

• 可以直接从正则表达式构造 DFA
• 可以从 DFA 构造最小 DFA
• 可以生成比标准二维表 (邻接矩阵表示法) 更加紧凑的转换表的表示方式

缓冲区

• 为了减少每次读取字符时的越界检查, 通常使用双缓冲区模式
• 并在缓冲区末尾加一个 EOF 哨兵

语法分析

产生式

• stmt -> if ( expr ) stmt else stmt
• if, (, ), else 叫终结符号 (terminal)
• stmt, expr 叫非终结符号 (non-terminal)
• 包括一个称为产生式头或左部的非终结符号, ->, 和一个称为产生式体或右部的由终结符号及非终结符号组成的序列
• 往往代表一个构造的书写方式

文法

• 四类文法
  • 0 型, 无约束, 递归可枚举语言, 图灵机
  • 1 型, 上下文决定推导 (越推约短就行), 上下文有关语言, 线性界限自动机
  • 2 型, 上下文无关推导 (产生式左侧只能是一个非终结符号), 上下文无关语言, 下推自动机
  • 3 型, 左右线性 (产生式体中只能有一个非终结符号), 正则表达式, 有限自动机
• 一个四元组 <N, Σ, P, S>
• N 是 non-terminal 符号的集合
• Σ 是 terminal 符号的集合
• P 是产生式的集合
• S 是开始符号 (non-terminal)
• 无限递归
  • 左递归 E -> E + T | T
  • 右递归 E -> T + E | T

语法分析树

• 根结点的标号为文法的开始符号
• 每个叶子结点的标号为一个终结符号或 \(ϵ\) (空)
• 每个内部结点的标号为一个非终结符号

算符优先文法

• 靠层次去决定算符的优先级
• 也可以形式化计算
  • Firstvt 集
    • 每个非终结符号递归展开的第一个终结符号的集合
    • 包括空串
  • Lastvt 集
    • 每个非终结符号递归展开的最后一个终结符号的集合
    • 包括空串
  • 一个算符前后的非终结符号的 Lastvt / Firstvt 集合内的算符优先级更大
• 有不冲突的算符优先关系的文法, 称算符优先文法
• 算符的优先级, 如果用表格呈现的话呢, 体积太大, 所以要降一个维度
• 优先关系具有传递性, 考虑将其建立为有向图, 进行拓扑排序, 通过赋予数值大小去压缩相对关系 (\(f(x)\) 与 \(g(x)\))

推导过程

• 从文法的开始符号开始, 用产生式替换非终结符号, 直到所有非终结符号都被替换为终结符号
• 推导过程当中的任意串都叫句型
• 一个非终结字符的展开形式, 可以称之为短语, 也就对应着语法分析树的一个子树
  • 如果展开之后只有终结字符, 那么就称之为直接短语, 也就是深度不大于 \(2\) 的子树
  • 最左侧的直接短语也叫句柄, 也就是我们应该首先处理的
• 如果一个短语当中存在终结字符, 那么我们称之为素短语, 在算符优先文法当中, 它是可以被直接归约的
  • 构建算符的优先级就是依赖于非终结符号的层次, 当前能够接触到非终结字符的, 一定是层次最低的
  • 最左素短语也就有了其意义

文法设计

• 二义性
  • 例如你忽略优先级, 1+2*3 可以是 (1+2)*3 也可以是 1+(2*3)
  • 式子一样语法树不同
  • 优先级往往依赖更外层的产生式实现, 将内层产生式 (内层优先级高) 抽象为一个非终结符号
  • 消除二义性, 加上中间状态
• 消除左递归
  • 转化为可选递归终点
  • E -> T E'
  • E' -> + T E' | ε
• 提取左公因子
  • A -> a B | a C
    • A -> a A1
    • A1 -> B | C
  • 先唯一确定一个中间状态
• 预测性
  • 无左递归 + 无左公因子保证预测性
  • 同一个终结符号的每个产生式的第一个终结符号互不相同

语法分析器

• 语法分析接受一个终结符号串作为输入, 找岀从文法的开始符号推导出这个串的方法, 推导失败报告语法错误
• 使用文法生成终结符号串 (隐式的语法分析树)
  • 对于任何上下文无关文法, 我们都可以构造出一个时间复杂度为 \(O(n^3)\) 的语法分析器
  • Cocke-Younger-Kasami 算法和 Earley 算法都是通用算法
  • 但是它们的时间复杂度太高
  • 我们常用自顶向下或自底向上分析
• 自顶向下或自底向上分析仅能分析上下文无关文法的子集

自顶向下分析

• 通用方法是递归下降分析方法 (回溯)
• 我们希望依赖预测性, 即每个非终结符号的每个可能的前缀都能唯一确定一个产生式
• 所需前缀词法单元数量 (向前看符号数量) 为 \(k\), 该文法为 \(LL(k)\) 文法
• \(LL(1)\) 文法
  • 预测性 + 无二义性是前提
  • 需要 First 集 + Follow 集
  • First 集
    • 每个非终结符号的第一个终结符号的集合
    • 印证无左公因子
  • Follow 集
    • 每个非终结符号的所有可能的后缀的集合
    • 当前字符不在 First 集中时, 才考虑 Follow 集, 表示当前非终结符号可以推导为空
  • Select 集
    • 如果该非终结符号不能推导为空, 那么 Select 集就是 First 集
    • 如果该非终结符号能推导为空, 那么 Select 集就是 Firsst 集 + Follow 集
  • 使用递归下降分析方法的简单实现, 预测分析法
    • 读到终结符号时预测并匹配
    • 读到非终结符号时递归
  • 实现简单, 表达能力差

自底向上分析

• 规约指匹配上一个产生式, 并将其替换为产生式头
  • 每一步规约都产生最右推导倒序的一个最右句型
  • 全流程的逆过程就是最右推导
• 匹配的子串就叫句柄
• 移入 - 归约语法分析技术
  • 用一个栈来保存文法符号
  • 用一个输入缓冲区来存放其余符号
• 二义性文法不可能是 \(LR\) 的
• 所需向前看符号数量 为 \(k\) (除了栈中的), 该文法为 \(LR(k)\) 文法 (默认 \(LR(1)\))
  • 表达能力强, 是 \(LL(k)\) 文法的真超集
• 我们对 LR 文法增广
  • 增加一个新的开始符号 \(S'\)
  • \(S' \to S\)
  • 规约到 \(S'\) 时, 分析成功
• \(LR(0)\) 文法
  • 存下来所有产生式前缀 (项)
  • 在这个 \(LR(0)\) 自动机中进行状态转换
  • 不能转换就规约
  • 要求不存在移进 - 规约冲突 / 规约 - 规约冲突
• \(SLR(1)\) 分析法 (简单 LR)
  • 一定程度上解决移进 - 规约冲突
  • 不允许规约 - 规约冲突
  • 要求冲突时, 所有规约的后继集合与所有移进的符号集合区分开
  • 所以要多存一个后继集合
• \(LR(1)\) 分析法
  • 一定程度上解决规约 - 规约冲突
  • 要求冲突时, 当前匹配规约的后继与可能的移进的符号集合区分开
  • 规约 - 规约冲突只要后继能区分开, 就不会冲突
  • 所以要多存好多个后继集合
  • 通过在项目中加入展望符, 可以区分不同的上下文
• \(LALR(1)\) 分析法
  • 合并同心状态
  • A -> α · β 与 A -> α · γ 是同心的
  • \(LALR(1)\) 的状态数量等于 \(LR(0)\)
  • 分析能力比 \(SLR(1)\) 强, 比 \(LR(1)\) 稍弱
  • 可能原来分得清的规约 - 规约冲突, 合并后就会冲突

错误处理

• 语法分析器在发现错误时, 要能报告错误的位置, 并能继续分析
• 恐慌模式
  • 当发现错误时, 立即报告错误, 并跳过到最近的一个同步点, 并重新开始分析
  • 需要文法有明确的同步点, 例如 C 语言的 ;
• 短语恢复
  • 修复出现错误的短语, 并继续分析
  • 有可能导致无限循环
• 错误产生式
  • 明确错误形式, 这使得错误诊断信息全面
• 全局纠正
  • 修复所有错误到最接近原始串的正确串, 并继续分析 (理论存在)
• 无论哪种错误处理方法, 都应该依赖文法特性进行优化

符号表

• 用哈希表实现
• 标识符与其属性的映射
• 一个作用域对应一个符号表
  • 用栈组织多个符号表的嵌套与代码块的处理顺序关系
  • 用树组织多个符号表的嵌套与代码块的处理顺序关系
• 一般情况, 语法分析器负责符号表的构建

Yacc 语法分析器生成工具

• 基于 \(LALR(1)\) 分析
• 由声明, 语法规则, 辅助函数组成 (三部分用 %% 分隔)
• 声明
  • C 代码嵌入: 头文件引用, 全局变量定义 (直接拷贝到生成的 C 代码顶部)
  • 终结符定义: %token 声明由 Lex 返回的词法单元
  • 优先级与结合性: %left, %right 解决移进 - 规约冲突 (如 +, * 的优先级)
  • 属性值类型: %union 定义符号值 (yylval) 的多种数据类型
• 语法规则
  • 产生式: 类似于 BNF 的文法描述 (如 E : E '+' T)
  • 语义动作: 规约时执行的 C 代码块 { ... }
  • 值传递机制: 使用伪变量进行属性计算
    • $$: 产生式左部非终结符的值 (返回值)
    • $1, $2: 产生式右部第 1, 2 个符号的属性值
• 辅助函数
  • 代码实现
  • 错误处理
  • 词法接口
• Yacc 处于主导地位, 它需要下一个 token 时, 就呼叫 Lex (yylex)

语法制导翻译

• 语法制导翻译是通过向一个文法的产生式附加一些规则或程序片段而得到的, 目的是一边分析一边翻译
• 用于类型检查和中间代码生成, 或者直接生成简单的目标代码

属性

• 表示与某个程序构造相关的任意的量
• 如果一个节点的属性依赖于它的直接子节点与自己 (包括自己的继承属性), 那么我们说这个属性是综合属性
• 如果一个节点的属性依赖于它的父节点和它的兄弟节点, 那么我们说这个属性是继承属性

语法制导定义

• 把每个文法符号和一个属性集合相关联, 并且把每个产生式和一组语义规则相关联,
• 这些规则用于计算与该产生式中符号相关联的属性值 (带属性 + 属性计算方式的文法)
• 没有副作用的语法制导定义有时也称为属性文法
• 注释分析树就是语法分析树每个结点上还标记有属性

依赖图

• 依赖图是一个有向图, 它的节点是属性实例, 边是属性实例之间的依赖关系
• 确定一棵给定的语法分析树中各个属性实例的求值顺序 (拓扑排序一下)

翻译方案

• 就是显式指定了语义规则的计算顺序的, 嵌入程序片段的语法制导定义
• 从算法到代码 (指编译器执行的代码)
• \(S\) 属性的语法制导定义
  • 要求每个属性都是综合属性
  • 翻译方案就是后序遍历语法分析树, 对每个节点执行语义动作
  • 显然适配 \(LR\) 分析
• \(L\) 属性的语法制导定义
  • 要求每个属性都是综合属性或者有限制的继承属性
  • 限制在于继承属性只能依赖于直接父节点的以及其左兄弟的属性
  • 换言之, 依赖图的边总是从左到右
  • 显然适配 \(LL\) 分析
• 非属性文法
  • 对于属性文法, 出一个翻译方案是简单的
  • 对于非属性文法, 可能在拓扑排序的基础上添加其它的约束
• 左递归消除
  • 当我们将一个左递归文法转换为右递归文法时, 属性计算规则也必须随之改变
  • 原来的综合属性往往会变成中间表示的继承属性, 并在其的递归展开中向下传递, 最后在 \(ϵ\) 处综合上来

实现 L 属性的语法制导定义

• 建立语法分析树并注释
• 构造语法分析树, 加入动作
• 用一个递归下降的语法分析器, 它为每个非终结符号都建立一个函数
  • 把这个函数改一改
  • 参数是继承属性
  • 返回值是综合属性
  • 展开同时计算属性
• 用一个递归下降的语法分析器, 以边扫描边生成的方式生成代码
  • 一般情况下, 我们的目的是生成一个为综合属性的主属性 (code)
  • 要求主属性必然是各个子节点主属性的顺序连接
  • 这样代码生成就简单了
• 与 \(LL\) 语法分析器结合, 实现一个 SDT
  • 自顶向下的递归栈中保存即将被执行的语义动作与非终结符号的综合属性值
• 与 \(LR\) 语法分析器结合, 实现一个 SDT
  • 矛盾在于继承属性的计算顺序与 \(LR\) 分析器的归约顺序不一致
  • 必须先构造语法分析树, 再执行翻译 (低级方案)
  • 使用标记非终结符来解决
    • 如果我们想在一个产生式中插入动作
    • 在动作的位置加上一个规约到空的标记非终结符
    • 一到那就会触发规约 -> 动作
  • 将算出来的属性存到标记非终结符的记录里
  • 后续的符号在归约时, 可以从 \(LR\) 分析栈里找到这个标记非终结符, 从而获取到之前计算出来的属性值
    • 栈的下面对应树的左边
  • 太远的属性找不到, 可以插入有逻辑的中转标记非终结符来传递 (复写规则)

生成中间代码

语法树及其变体

• 抽象语法树
  • 内部节点表示操作符
  • 叶子节点表示操作数
  • 抽象语法树是常见的中间代码, 可以表达算术表达式, 变量类型等
• 无环有向图
  • 将语法树中的公共子表达式提取出来, 用一个节点表示, 形成一个 DAG
• 三地址码
  • 由地址与指令组成
  • 地址可以是变量 / 临时变量 / 常量
  • 指令可以是
    • a = b op c
    • a= op b
    • a = b
    • goto L
    • if a goto L
    • if a relop b goto L
    • param a1
    • param a2
    • ...
    • param an
    • call p, n
    • return a
    • a[i], *a, &a 与 以上的组合
  • 四元式
    • op, arg1, arg2, result
  • 三元式
    • op, arg1, arg2 (函数式思想, 每个三元式本身就是 result)
    • 间接化, 一个指向三元式的指针的列表 (方便排序)
• 静态单赋值形式
  • 每个变量只被赋值一次 (不停重命名)
  • 每个变量的定义与使用之间没有复杂数据依赖
  • 每个变量的定义与使用之间没有复杂控制依赖
  • 但是分支赋值怎么办呢
    • 引入一个新的量子态, 同时表示两种结果

类型表达式

• 基本类型属于类型表达式, 通常包括整数, 浮点数, 字符, 布尔值, 空
• 类名是一个类型表达式
• 将类型构造算子 array 作用于一个数字和一个类型表达式可以得到一个类型表达式
• 记录是包含有名字段的数据结构, 将 record 类型构造算子应用于字段名和相应的类型可以构造得到一个类型表达式
• 可以构造得到函数类型的类型表达式 s -> t, s 是参数类型, t 是返回值类型
• 类型表达式可以包含取值为类型表达式的变量
• 以上可以嵌套
• 经常用图来表示类型表达式
  • 内部结点表示类型构造算子
  • 叶子结点是基本类型, 类型名或类型变量
• 重要工作是类型检查与偏移量计算

表达式的翻译

• 属性拼接法, 自底向上的生成, 传递 code 片段并连接 (编译慢)
• 增量生成, 因为我们是后序遍历的, 直接打印代码就行, 用到的变量一定是已经生成过的

类型检查

• 类型综合
  • 根据子表达式的类型构造出表达式的类型, 必须先声明
• 类型推导
  • 从表达式的上下文环境中, 推导出表达式的类型
• 工作
  • 类型转换
  • 函数和运算符的重载
  • 多态
• 置换与合一
  • 置换是一个从类型变量到类型表达式的映射
  • 对于一个类型表达式, 将其每个类型变量的所有出现都置换一下被称为实例
    • 例如, 对于类型表达式 list(α), 实例 list(int) 就是将所有的 α 都替换为 int
  • 给定两个类型表达式 t1 和 t2, 我们想找一个置换, 使得应用之后, 它们变得一模一样
    • 我们称该置换为合一替换
  • record(a:α,b:β) 与 record(a:int,b:β) 的一般合一替换为 {α → int}
    • 尽量少的置换类型变量
• 在编译器检查函数调用 f(x) 时
  • 尝试把实参类型填入形参类型
  • 检查实参类型和形参类型是否匹配
  • 就是找一个一般合一替换
• 合一算法
  • 并查集合并类型图中节点
  • 变量 <-> 变量不用动
  • 类型 <-> 类型, 直接比较是否相等
  • 类型 <-> 变量, 用类型指代变量 (小心嵌套, int -> list(int), 会导致无限递归类型)

控制流

• （&&, ||）不会出现在中间代码中作为操作符, 而是被转化为程序执行流的跳转逻辑
  • 如此实现短路求值
• 使用继承属性
  • 父节点传递信息, 如果子节点为真 / 假, 跳转的目标
  • 有时, 跳转的目标就是当前语句的下一条指令, 这时候就不需要跳转了 (优化)
  • 但是实现很麻烦
• 使用回填技术
  • 矛盾在于, 跳转时不知道目标标号
  • 先留空目标地址, 并保存到一个列表 (一个综合属性)
  • 当语法分析进行到能够确定目标标号的位置时, 再回填列表中的指令

Switch 语句的翻译

• 核心问题是根据 case 的数量和值的分布情况, 选择最合适的底层实现方式
• 线性扫描
  • 适用于 case 分支数量较少的情况
  • 就是转换为 if 的处理形式
• 二分查找
  • 适用于 case 分支数量中等的情况
  • 就是将 case 排序, 然后用二分查找的方式查找
  • 嵌套 if
• 散列表
  • 适用于 case 分支很多, 且值比较稀疏的情况
  • 就是用一个哈希表, 键是 case 的常量值, 值是对应的代码标号
• 跳转表
  • 适用于 case 的值位于一个较小的范围内, 且覆盖率较高的情况
  • 就是用一个数组, 数组的第 i 项存储 min + i 对应的代码标号
• 优化
  • 将所有的分支测试代码 (选路径) 放在后面, 而将 case 执行代码放在前面 (先进行一次代码转换)
  • 方便一次扫描生成, 而不是分两次扫描 / 回填

过程的中间代码

• 核心问题是函数的调用序列生成
• 调用
  • 参数求值
  • 参数传递
  • 执行调用
  • 获取返回值
• 定义
  • 符号表切换 (每个函数有自己的符号表)
  • 类型表示
  • 参数处理 (把参数的位置安排好)

运行时环境

概念

• 环境是一个从名字到存储位置的映射
• 状态是一个从内存位置到它们的值的映射
• 环境和状态可以动态 / 静态绑定
• 语言本身的动态与静态 (有无 runtime)
• 语言同时区分作用域的静态与动态
  • 静态作用域取决于声明位置
  • 动态作用域取决于调用位置
• 分派
  • 静态分派
    • 编译时根据类型确定调用的过程 (重载)
  • 动态分派
    • 运行时根据对象的实际类型来调用相应的方法 (虚函数)

活动记录

• 每个过程对应一个活动记录 (上下文, 也叫帧)
• 活动记录在控制栈上分配
• 活动树
  • 每个节点对应一个活动
  • 每个节点的子节点对应该节点调用的过程
  • 根节点是主过程
  • 一个子结点必须在其右兄弟结点的活动开始之前结束

调用代码序列

• 过程调用时, 父子都需要注入的代码片段
  • 我们希望尽可能多注入子过程
  • 这样复用该子过程时, 总注入代码少
• 实现
  • 参数值往往紧密放在子过程活动记录的开头 (父不需考虑子布局)
  • 然后放一些固定的调用代码
  • 栈顶指针指向这
  • 变长的放在最后 (所以偏移量是反的)
• 过程
  • 计算实参
  • 放返回地址 + 栈顶指针
  • 存当前状态
  • 初始化儿子
  • 放返回值
  • 帮父亲恢复状态

访问非局部变量

• 不允许声明嵌套过程的语言
  • 全局变量一定在静态区, 编译时就确定了地址
  • 局部变量在栈上分配, 运行时确定地址
• 允许声明嵌套过程的语言
  • 嵌套过程指在一个过程内部定义的过程
  • 按理说能访问外层的变量, 但是运行时父过程不一定是外层过程
  • 我们使用访问链来解决这个问题
    • 每个嵌套过程活动记录都有一个指向其外层活动记录的指针
    • 如果调用的嵌套深度小于自己, 一定是外层过程调用了内层过程, 访问链指向自己
    • 如果调用的嵌套深度等于自己, 访问链继承父过程的访问链
    • 如果调用的嵌套深度大于自己, 放最近公共祖先 (向上嵌套深度差值加一个位置)
    • 如果想把过程作为参数传递, 调用链的确定由你负责
  • 我们使用显示表来优化
    • 发现对于嵌套深度为 n 的过程, 一定指向栈中最高的嵌套深度为 n-1 的活动记录
    • 统一存在一个表里 d[n] 表示栈中最高的嵌套深度为 n 的活动记录位置
    • 注意函数返回时要修复旧的显示表
• 将函数作为一等公民返回的语言
  • 普通栈就失效了 (上下文不能因函数返回而释放)
  • Cactus Stack / 堆上存解决

堆管理

• 程序往往具有
  • 时间局限性, \(90 \%\) 的时间都在执行 \(10 \%\) 的指令
  • 空间局限性, \(90 \%\) 的内存访问都在使用 \(10 \%\) 的数据
• 使现实中的程序中碎片最少的一个良好策略是将请求的存储分配在满足请求的最小可用窗口中
  • 我们将堆预先切割为容器 (分离空闲表), 专有容器中的存储块大小一致, 留下一个可拓展的荒野块
  • 分配对象时, 先找专有容器
  • 如果没有, 就找最小容纳的容器 (有时也直接顺序放, 缓存友好)
  • 如果没有, 就创建一个容器
• 管理空闲空间
  • 对于专有容器, 一个位图解决
  • 边界标记
    • 每个存储块的开头和结尾都有一个边界标记
    • 用来判断存储块是否空闲以方便合并
  • 一个双重链接的, 嵌入式的空闲列表

垃圾回收

• 判断可达性决定垃圾
  • GC 的起点, 寄存器, 栈上的变量, 全局变量
  • 从根出发, 顺着引用链能找到的对象, 就是可达的
• 引用计数
  • 每个对象都有一个引用计数器
  • 当有新引用指向对象时, 计数器加一
  • 当引用被移除时, 计数器减一
  • 当计数器为零时, 对象被认为是垃圾, 可以被回收
  • 停顿时间短, 即时回收, 问题是可能存在循环引用
• 链路跟踪
  • 从根出发, 顺着引用链找
  • 解决循环引用, 吞吐量大, 但是有停顿
• 吞吐量, 停顿时间, 空间利用率不可能三角
• 弱引用机制
  • 一些引用, 比如缓存, 索引不应该阻止对象被回收
  • 当一个对象只有弱引用指向它时, 它就会被回收
• C / C++ 中内存不具有类型信息, 导致无法判断是否是指针
  • 所以只能用保守式 GC (最好别用 GC)

链路跟踪算法

• 标记-清除
  • 先从根遍历把活的对象标记, 然后遍历整个堆, 把没标记的回收
  • 优点: 简单, 实现成本低
  • 缺点: 有碎片
• 标记-压缩
  • 先从根遍历把活的对象标记, 然后遍历整个堆, 把活的对象压缩到一端, 把没标记的回收
  • 优点: 消除了碎片, 分配新对象极快
  • 缺点: 暂停时间长, 因为要移动对象
• 复制
  • 把内存一分为二, 只在 From 分配, 满了就把活的拷贝到 To, 清空 From, 下次互换
  • 优点: 没有碎片, 且只处理活对象
  • 缺点: 空间浪费, 内存利用率直接砍半

优化链路跟踪算法

• 核心目的是减少暂停时间
• 增量式 GC
  • 把一次大扫除分成多次小扫除, 让 GC 线程和用户线程交替执行, 减少了暂停时间
  • 问题是用户线程修改了引用, 而 GC 线程还在运行, 导致错误的回收
  • 解决方法是在用户线程修改引用时, 触发一个屏障代码, 记录下这次修改 (修改状态标记), 保证 GC 不漏标
  • 状态标方法是三色标记法
• 分代回收
  • 建立在绝大多数对象都是朝生夕死的的基础上
  • 对象根据年龄分为年轻代和老年代
  • 年轻代使用复制算法, 老年代使用标记-压缩或标记-清除
  • 痛点是不知道老年代对象引用了年轻代对象
  • 解决方法是使用记忆集 / 卡表记录老年代哪里引用了年轻代, 回收年轻代时, 把这些脏卡片作为根集的一部分, 从而避免扫描整个老年代
• 列车算法
  • 解决老年代回收停顿过长的问题
  • 把老年代划分成一个个车厢, 每次只回收一节车厢
  • 处理车厢之间的引用时非常复杂

代码生成

流程

• 输入为中间代码和符号表
• 为给定源程序生成一个最优的目标程序是不可判定问题
• 目标程序
  • 可重定位汇编语言 -> 可重定位目标语言 -> 目标语言
• 任务
  • 优化 IR
  • 指令选择 (如何用最短 / 最快的指令序列实现)
  • 寄存器分配 (最稀缺资源的利用)
  • 指令排序 (利用流水线, 避免停顿)

目标机器模型

• 指令代价
  • 简单模型下, 代价 = \(1\) + 操作数涉及的存储器访问次数
  • 复杂模型需考虑指令周期和流水线延迟

目标代码中的地址

• 复习一下
  • 环境是标识符到内存地址的映射
• 静态分配
  • 每个函数的局部变量和返回地址所需的空间在编译时就确定了位置
  • 每个函数只有一份固定的活动记录区域
  • 适用于不支持递归且不需要动态申请内存的语言
• 栈式分配
  • 活动记录不是固定的, 而是在栈上动态分配的
  • 使用一个寄存器 SP 始终指向栈顶
• 变量的地址
  • 静态变量: 地址 = 静态区基址 + 偏移量
  • 栈变量: 地址 = SP + 偏移量

生成一个试试

• 寄存器描述符
  • 跟踪每个寄存器当前存放的是哪个变量
• 地址描述符
  • 跟踪每个变量当前存放在哪些位置 (寄存器, 栈, 全局内存)
• 假设我们要翻译 x = y + z
  • 分配寄存器
  • 如果变量当前不在寄存器中, 则加载到寄存器中
  • 计算
  • 更新描述符
• 假设我们要翻译 x = y
  • 如果 y 已经在寄存器中, 记录该寄存器同时为 x & y
• 基本块结束时, 将还在寄存器中的活跃变量写回内存
• 设计一个寄存器分配算法
  • 目的是最小化内存访问次数
  • 如果某个变量在寄存器中, 则优先使用该寄存器
  • 否则, 选择一个空闲寄存器
  • 如果没有空闲寄存器
    • 覆盖一个以后不用的变量
    • 覆盖一个内存中有副本的变量
    • 实在没有办法了, 就溢出一个寄存器
      • 选择代价最小的溢出方法 (移动变量的指令数量)
  • 结果放在哪
    • 如果计算使用的寄存器之后不用了, 则结果放在该寄存器

指令选择

• 考虑输入的
  • IR 层次 (抽象层次)
  • 目标机器模型 (指令集, 寄存器, 内存)
  • 目标代码质量
• 树重写 / 树覆盖
  • 将 IR 表示为树
  • 将机器指令描述为树的模板
  • 用模板去覆盖 IR 树, 目标是总代价最小 (动态规划或贪心)

Ershov 数

• 一个标记在语法树节点上的数字
• 代表如果不把中间结果存回内存. 计算这个节点代表的表达式, 最少需要占用多少个寄存器
• 计算方法
  • 叶子节点标记为 \(1\)
  • 单子节点标号等于子节点的标号
  • 双子节点
    • 如果不相等 max(L, R)
    • 如果相等 L + 1
• 指导计算顺序
  • 寄存器足够时
    • 谁的标号大, 先算谁
    • 如果一样大, 通常先算右边的 (实现方便)
  • 寄存器不足时
    • 先算大子树, 结果放进内存

运行内存操作数的优化 (OP R, M 寄存器与内存运算)

• 自底向上计算代价向量
  • 对于语法树中的每个节点, 我们计算一个数组 C, 其中 C[i] 代表在有 \(i\) 个可用寄存器的情况下, 计算该子树并将结果留在寄存器中的最小代价
  • 叶子节点的 C[0] 为 \(0\), 其它 C[i] 为 \(1\) (加载到寄存器)
  • 内部节点的 C[i] 为所有可能的指令模式和计算顺序的最小值
    • 转移方程略
• 自顶向下决策
  • 根据刚算的 C[i] 选择最优的指令模式和计算顺序
    • 如果 C[i] 是通过先右后左得到的, 那就标记先处理右子树
    • 如果某个子树的计算需要把它存回内存, 那就标记该子树需要溢出
• 这就是现代编译器后端技术的雏形

寄存器分配

• 相比于指令选择, 寄存器分配对性能影响更大
• 到一个从寄存器到变量的最优指派也是 NP 完全的
• 使用方法
  • 执行一个运算时该运算的部分或全部运算分量必须存放在寄存器中
  • 寄存器很适合做临时变量
  • 寄存器用来存放在一个基本块中计算而在另一个基本块中使用的值 (循环下标)
  • 寄存器经常用来帮助进行运行时刻的存储管理
• 全局寄存器分配
  • 跨基本块热点变量全局分配一个寄存器
• 外层循环的寄存器指派
  • 进行内层循环时, 优先给外层循环的变量分配寄存器
• 图着色算法
  • 将寄存器分配问题转化为无向图的着色问题
  • 冲突图
    • 节点是变量
    • 如果两个变量同时存活, 则连一条边
  • K-着色
    • 如果图能用 \(K\) 种颜色着色 (\(K\) = 物理寄存器数量), 则分配成功

窥孔优化

• 先生产一个慢慢优化的思路
• 在生成的代码窗口 (窥孔) 上进行局部检查和替换
• 常见变换
  • 冗余指令消除 (如 MOV R0, R0)
  • 控制流优化 (如跳转到跳转 -> 直接跳转到目标)
  • 代数化简 (如 x = x + 0 删除)
  • 机器特有指令利用 (如自增指令)

机器无关优化

基本块与流图

• 目的是确定变量的后续使用信息
• 基本块
  • 连续的语句序列, 控制流只能从头进, 从尾出
• 划分算法
  • 首指令, 程序的入口, 跳转的目标, 跳转指令后的下一条指令都需要划分
  • Leader 及其后续直到下一个 Leader 之前的指令构成一个基本块
• 控制流图
  • 节点是基本块
  • 边表示控制流的跳转 (条件或无条件)

基本块的优化

• DAG 表示
  • 一个变量的初始值为一个节点
  • 每个语句都有一个相关的结点
    • 其子结点是基本块中的其他语句的对应结点
    • 这些语句是在该语句之前, 最后一个对该语句所使用的某个运算分量进行定值的语句
    • 该节点标号为 op
    • 记录在此基本块内最晚被进行定值的语句为该语句的变量
  • 某些节点为输出结点 (活跃变量)
    • 这些变量的值可能以后会在流图的另一个基本块中被使用到
• 可以用来
  • 消除局部公共子表达式
  • 消除死代码
  • 对相互独立的语句进行重新排序 (提高缓存命中)
  • 代数优化
• 代数优化
  • 代数恒等式
    • 如 x + 0 = x, x * 1 = x
  • 局部强度消减
    • 如 x * 2 不如 x << 1 / x + x 快
  • 常量合并, 编译时计算
• 数组元素访问时由于偏移量动态决定
  • 对数组的任何修改都会杀死所有对该数组的其他读取节点
• 聪明的已经发现指针将杀死所有节点
  • 所以先进行指针分析, 找出可能指向的子集地址
• 基本块 -> DAG -> 基本块
  • 指令的顺序必须遵守DAG中的结点的顺序
  • 对数组的赋值必须跟在所有在它之前的对同一数组的赋值或求值运算之后
  • 对数组元素的求值必须跟在所有在它之前的对同一数组的赋值指令之后
  • 一个变量的使用必须跟在所有在它之前的过程调用和指针间接赋值运算之后
  • 任何过程调用或者指针间接赋值都必须跟在所有在它之前的对任何变量的求值运算之后

全局优化

• 公共子表达式消除
  • 利用可用表达式分析, 删除重复计算
• 死代码消除
  • 利用活跃变量分析, 删除计算结果从未被使用的语句
  • 包括不可达代码消除
• 常量传播与折叠
  • 如果编译时能确定变量是常量, 直接替换并计算
• 复写传播
  • 遇到 x = y, 尽可能在后续把 x 替换为 y
  • 目的是减少赋值操作, 并为死代码消除创造机会
• 这些优化都依赖于数据流分析

数据流分析

• 语句的前后以及基本块的前后被称为程序点
• 路径就是程序点序列
• 程序分析把可能出现在某个程序点上的所有程序状态总结为有穷的特性集合
  • 不同的分析技术可以选择抽象掉不同的信息
• 到达定值
  • 分析在某点, 变量 \(x\) 的赋值是否可能来自某条语句
  • 它是前向数据流分析, 集合操作是并集
  • 应用: 循环不变量外提, 常量传播
  • 核心逻辑
    • 生成: 如果我在这一行给 \(x\) 赋值了, 我就生成了一个新的定值
    • 杀死: 如果我给 \(x\) 赋了新值, 那么旧的 \(x\) 的定值就被杀死了
  • 取并集, 只要有一条路径带来了一个定值, 那么这个定值就到达了
• 活跃变量分析
  • 分析在某点, 变量 \(x\) 的值在后续是否会被使用
  • 它是后向数据流分析, 集合操作是并集
  • 应用: 寄存器分配 (构建冲突图), 死代码消除
  • 核心逻辑
    • 使用: 如果我在这一行读取了 \(x\), 那么 \(x\) 在这就活了
    • 定值: 如果我在这一行给 \(x\) 赋值了, 那么 \(x\) 在这就死了
  • 取并集, 只要有一条路径用到了 \(x\), 那么 \(x\) 就活了
• 可用表达式
  • 分析在某点, 表达式 x op y 是否已经计算过且操作数未被修改
  • 它是前向数据流分析, 集合操作是交集
  • 应用: 公共子表达式消除
  • 核心逻辑
    • 生成: 计算了 x+y
    • 杀死: 如果我给 \(x\) 或 \(y\) 赋了新值, 那么 x+y 就死了
  • 取交集, 必须所有路径都用到了 \(x\) 和 \(y\), 那么 x+y 才活了
• 通用算法
  • 初始化: 给所有基本块的 OUT/IN 设置初值 (空集或全集)
  • 循环: 遍历所有基本块, 套用传递函数和控制流公式计算新的 OUT/IN
  • 终止条件: 直到某一次循环中, 所有的集合都不再发生变化 (收敛到不动点)

通用数据流分析框架

• 半格
  • 对于集合上的偏序关系, 并操作与交操作有一个满足有上确界和下确界就叫半格
  • 对于这个场景
    • 值域: 所有可能状态的集合
    • 交汇运算: 就是我们在基本块入口处做的合并操作 (交集 / 并集)
    • 顶元素: 表示初始状态或信息最少 / 最乐观的状态
    • 底元素: 表示最坏情况或信息最多 / 最悲观的状态
• 偏序
  • 对于格上的集合, \(x \le y\) 当且仅当 \(x \wedge y = x\)
  • 也就是格上位置更低的集合
  • 意味着 \(x\) 比 \(y\) 更低, 更安全, 或者包含了 \(y\) 的信息
    • 如果交汇运算为并集, 集合越大, 位置越低
    • 如果交汇运算为交集, 集合越小, 位置越低
• 传递函数
  • 定义: 传递函数 \(f\) 是一个从半格中一个元素到另一个元素的函数, 它描述了在每个基本块中, 信息是如何变化的
  • 传递函数必须是单调的, 即 \(f(x) \le f(y)\) 当且仅当 \(x \le y\)
    • 如果输入的信息包含了更多的事实, 那么输出的信息也必须包含更多的事实
    • 保证算法收敛到不动点
  • 传递函数必须是可分配的, 即 \(f(x \wedge y) = f(x) \wedge f(y)\)
    • 这确保了精确性, 先合并再计算, 结果与先计算再合并相同
    • 有时候也不一定
  • 需要保证每次数据经过一个基本块, 信息的变化是守规矩的
• 解
  • 理想中是遍历所有可能路径将结果合并 (不可能)
  • MOP 解 (理论上限)
    • 假设所有控制流图中的路径都可能被执行
  • MFP 解
    • 就是上一部分介绍的解法 (直到稳定)
    • 需要保证单调性
    • 如果框架是不可分配的, 算法的结果比 MOP 更保守 (更不精确), 但依然是安全的

常量传播

• 在之前的分析中, 我们处理的数据流值通常是有限集合
• 但常量传播不一样, 它处理的是数值域, 这个域是无限的
  • 它的格不再是简单的有限集合
  • 具备不可分配性, \(x\) 与 \(y\) 变化了, 合并后的结果可能不变化
• 状态
  • 未定义 (可能是任何常量)
  • 常量 (具体的数值)
  • 不是常量 (来自输入或动态变化)
• 交汇运算
  • 未定义 \(\wedge\) 任何东西 = 任何东西
  • 常量 (c) \(\wedge\) 常量 (c) = 常量 (c)
  • 常量 (c1) \(\wedge\) 常量 (c2) = 不是常量
  • 不是常量 \(\wedge\) 任何东西 = 不是常量

部分冗余消除

• 消除那些只在某些路径上重复计算的表达式, 同时把计算尽量往代码执行频率低的地方移 (比如移出循环)
• 懒惰代码移动不仅消除了冗余, 还保证了寄存器压力最小
• 算法
  • 预期执行 (从使用点)
    • 逆向交集
    • 从这个表达式被计算往上找看哪里必须计算 (这点之后所有路径都用得上)
  • 可用表达式 (从起点)
    • 前向交集
    • 对于每个表达式找哪里已经算过了
  • 得出 Earliest 点
    • 所有预期为真, 可用为假的点
  • 可后延表达式 (从 Earliest 点)
    • 前向交集
    • 尽量晚算
    • 得出 Latest 点
  • 被使用的表达式 (从使用点)
    • 逆向交集
    • 清理那些只赋值但没人用的死代码

循环优化

• 在数据流图中
  • 如果从入口走到结点 \(n\) 的所有路径都必须先经过结点 \(d\), 那么 \(d\) 支配 \(n\)
  • 形成一个支配树 (其实不是树)
  • 关注后退边 (环)
• 回边
  • 回退边回退的位置是到你的所有路径的必经之路
  • 如果流图中所有的后退边都是回边, 这个图就是可归约的
  • 除非你瞎用 goto, 否则现代语言写不出不可归约的图
  • 这就是一个自然循环
• 代码外提
  • 将循环中计算结果不变的语句移到循环前
• 归纳变量消除
  • 归纳变量: 在循环中每次增加固定值的变量 (如 i)
  • 派生归纳变量: 与基础归纳变量线性相关的变量 (如 addr = base + i * 4)
  • 消除: 最终去掉不再被使用的基础归纳变量 (如 i)
• 循环展开
  • 复制循环体, 减少循环控制 (比较和跳转) 的开销
  • 增加指令级并行的机会, 但会增加代码体积
• 循环分块
  • 针对嵌套循环访问大数组
  • 将大循环切分成小块, 使数据能装入 Cache, 提高缓存命中率

迭代算法的收敛速度

• 大多数问题的信息只需要沿着无环路径传播就够了
• 只有常量传播比较特殊, 它可能需要绕着环跑好几圈才能确定一个值
• 算法需要的迭代次数 = 流图的深度 + \(2\)
  • 流图的深度 = 嵌套最深的循环层数
  • 通常程序的深度很小所以迭代算法收敛极快

编译原理还有三章

• 不学了, 体系结构与软件分析中见面

计算机程序的构造与解释

TODO

软件分析

TODO