中间表示
中间代码
- 树和有向无环图（DAG）
- 高层表示，适用于程序源代码
- 三地址码 （3-address code）
- 低层表示，靠近目标机器
- 控制流图（CFG）
- 更精细的三地址码，程序的图状表示
- 适合做程序分析，程序优化等
- 静态单赋值形式（SSA）
- 更精细的控制流图
- 同时编码控制流信息和数据流信息
- 连续传递风格（CPS）
- 更一般的SSA
为什么划分中间表示
- 编译器工程上考虑
- 阶段划分：把整个编译过程划分为不同的阶段
- 任务分解：每个阶段只处理翻译过程的一个步骤
- 代码工程：代码更容易实现、错误、维护和演进
- 程序分析和代码优化的需要
- 两者都和程序的中间表示密切相关
- 许多优化在特定的中间表示上才可以或者才容易进行
三地址码
基本思想
- 给每个中间变量和计算结果命名
- 没有复合表达式
- 只有最基本的控制流
- 没有各种控制结构
- 只有goto call等
- 所以三地址码可以看成是抽象的指令集
- 通用的RISC
定义
S-> x = n // 常数赋值 | x = y ⊕ z // 二元运算 | x = ⊙ y // 一元运算 | x = y // 数据移动 | x[y] = z // 内存写 | x = y[v] // 内存读 | x = f(x1, ... xn) // 函数调用 | Cjmp (x1, L1, L2) // 条件跳转 | Jmp L // 无条件跳转 | Label L // 标号 | Return x // 函数返回
- 优点
- 所有的操作都是原子的
- 变量没有符合结构
- 控制流结构被简化了
- 只有跳转
- 是抽象的机器代码
- 向后做代码生成更容易
- 缺点
- 程序的控制流信息是隐式的
- 可以做进一步的控制流分析
控制流图
- 程序的控制流图表示可以代开很多的好处
- 控制流分析
- 对很多程序分析来说，程序的内部结构很重要
- 典型的问题：程序是否存在循环
- 可以进一步进行其他分析
- 例如数据流分析
- 现代编译器的早期阶段就会倾向于做控制流分析
- 方便后续阶段的分析
基本概念
- 基本块：是语句的一个序列，从第一条执行到最后一条
- 不能从中间进入
- 不能从中间退出
- 控制流图：控制流图是一个有向图G=(V,E)
- 节点V：是基本块
- 边E：是基本块之间的跳转关系
如何生成控制流图
- 可以直接从抽象语法树生成：
- 如果高层语言具有特别规整控制流结构的话比较容易
- 也可以先生成三地址码，然后继续生成控制流图：
- 对于像c这种包含goto的语言更合适
- 更加通用
基本操作
- 标准的图论算法都可以用在控制流图的操作上
- 各种遍历算法，生成树，必经节点结构等
- 图节点的顺序有重要的应用
- 拓扑序，逆拓扑序，近似拓扑序等
- 使用死基本块删除优化来研究基本操作
数据流分析
- 通过对程序代码进行静态分析，得到相关于程序数据相关的保守信息
- 必须保证程序分析结果是安全的
- 根据优化的目标不同，需要进行的数据流分析也不同
- 到达定义分析
- 活性分析
优化的一般模式
- 程序分析
- 控制流分析，数据流分析，依赖分析
- 得到被优化程序的静态保守信息
- 是对动态运行行为的近似
- 程序重写
- 以上一步得到的信息制导对程序的重写
到达定义分析
- 对每个变量的使用点，有那些定义可以到达：该变量的值是在哪里赋值的
活性分析
- 在代码生成的讨论中，我们假设目标机器有无限个寄存器
- 简化了生成的算法
- 对物理机器是个坏消息：机器只有有限个寄存器
- 这是寄存器分配优化的任务
- 需要进行活性分析
