编译原理 - 中间表示

简介: 编译原理 - 中间表示

中间表示


中间代码


  • 高层表示,适用于程序源代码
  • 三地址码 (3-address code)
  • 低层表示,靠近目标机器
  • 更精细的三地址码,程序的图状表示
  • 适合做程序分析,程序优化等
  • 静态单赋值形式(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的语言更合适
  • 更加通用


基本操作


  • 标准的图论算法都可以用在控制流图的操作上
  • 各种遍历算法,生成树,必经节点结构等
  • 图节点的顺序有重要的应用
  • 拓扑序,逆拓扑序,近似拓扑序等
  • 使用死基本块删除优化来研究基本操作


数据流分析


  • 通过对程序代码进行静态分析,得到相关于程序数据相关的保守信息
  • 必须保证程序分析结果是安全的
  • 根据优化的目标不同,需要进行的数据流分析也不同
  • 到达定义分析
  • 活性分析


优化的一般模式


  • 程序分析
  • 控制流分析,数据流分析,依赖分析
  • 得到被优化程序的静态保守信息
  • 是对动态运行行为的近似
  • 程序重写
  • 以上一步得到的信息制导对程序的重写


到达定义分析


  • 对每个变量的使用点,有那些定义可以到达:该变量的值是在哪里赋值的


活性分析


  • 在代码生成的讨论中,我们假设目标机器有无限个寄存器
  • 简化了生成的算法
  • 对物理机器是个坏消息:机器只有有限个寄存器
  • 这是寄存器分配优化的任务
  • 需要进行活性分析
目录
相关文章
|
6月前
|
自然语言处理 算法 前端开发
编译原理 - 词法分析
编译原理 - 词法分析
70 0
|
5月前
|
存储 编译器 C++
详细解读C++编译原理
详细解读C++编译原理
32 0
|
自然语言处理
【编译原理】第二章,词法分析
【编译原理】第二章,词法分析
|
6月前
|
存储 自然语言处理 编译器
【编译原理】词法分析:C/C++实现
【编译原理】词法分析:C/C++实现
230 1
|
自然语言处理 Java 编译器
【编译原理】第一章,什么是编译原理?
【编译原理】第一章,什么是编译原理?
|
自然语言处理 IDE 开发工具
【编译原理】第三章语法分析
【编译原理】第三章语法分析
|
Java 程序员 C#
【C语言学习-复习_第一课】什么是C语言?什么是计算机语言?
人与人之间交流需要使用语言,中国人和中国人之间使用汉语,其他国家之间的交流也需要使用其他国家的语言,计算机也要进行交流,他们使用哪种语言了?当然有人说使用汉语,呼叫某某某小助手可以帮助我们进行和计算机交流,但是某某某小助手是通过怎样实现的,也是程序员使用中文和计算机对话设计出来的吗?当但不是了。这样的话我们人人都是程序员,人人都是大佬!
76 0
|
自然语言处理 前端开发 JavaScript
【问道】编译原理
​ 上篇 计算机er要掌握的计算机思维 推理得出,编译原理就是将高级语言翻译成汇编语言或机器语言的过程,本章我们详细介绍编译设计原理和过程,并佐以Graal编译器证明
【问道】编译原理
|
自然语言处理 前端开发 编译器
前端学编译原理(一):编译引论(下)
前端学编译原理(一):编译引论(下)
275 0