编译原理实战课
宫文学
北京原点代码 CEO
26065 人已学习
新⼈⾸单¥59
登录后,你可以任选4讲全文学习
课程目录
已完结/共 55 讲
真实编译器解析篇 (19讲)
编译原理实战课
15
15
1.0x
00:00/00:00
登录|注册

06 | 中间代码:不是只有一副面孔

主流的编译器都在采用SSA格式来设计IR
IR可能采取多种数据结构,每种结构适合不同的处理工作
根据抽象层次和使用目的不同,可以设计不同的IR
phi指令
静态单赋值
程序依赖图(PDG)
有向无环图(DAG)
树结构
类似TAC的线性结构
程序依赖图(PDG)
有向无环图(DAG)
树结构
线性结构
LIR:依赖于CPU架构做优化和代码生成
MIR:独立于源语言和CPU架构做分析和优化
HIR:基于源语言做一些分析和变换
课程小结
SSA格式的IR
IR的数据结构
IR的呈现格式
P-code:用于解释执行的IR
IR的用途和层次
中间代码(IR)知识关系脑图

该思维导图由 AI 生成,仅供参考

你好,我是宫文学。今天这一讲,我来带你认识一下中间代码(IR)。
IR,也就是中间代码(Intermediate Representation,有时也称 Intermediate Code,IC),它是编译器中很重要的一种数据结构。编译器在做完前端工作以后,首先就是生成 IR,并在此基础上执行各种优化算法,最后再生成目标代码。
所以说,编译技术的 IR 非常重要,它是运行各种优化算法、代码生成算法的基础。不过,鉴于 IR 的设计一般与编译器密切相关,而一些教科书可能更侧重于讲理论,所以对 IR 的介绍就不那么具体。这就导致我们对 IR 有非常多的疑问,比如:
IR 都有哪些不同的设计,可以分成什么类型?
IR 有像高级语言和汇编代码那样的标准书写格式吗?
IR 可以采用什么数据结构来实现?
为了帮助你把对 IR 的认识从抽象变得具体,我今天就从全局的视角和你一起梳理下 IR 有关的认知。
首先,我们来了解一下 IR 的用途,并一起看看由于用途不同导致 IR 分成的多个层次。

IR 的用途和层次

设计 IR 的目的,是要满足编译器中的各种需求。需求的不同,就会导致 IR 的设计不同。通常情况下,IR 有两种用途,一种是用来做分析和变换的,一种是直接用于解释执行的。我们先来看第一种。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

编译器中的中间代码(IR)在编译过程中扮演着关键角色,它是编译器在生成目标代码之前的中间数据结构。IR的设计取决于编译器的需求,通常分为HIR、MIR和LIR三类,分别用于高层语义分析、通用优化和与CPU架构相关的优化和代码生成。此外,P-code作为一种与具体机器无关的IR,用于直接解释执行。文章还介绍了IR的书写格式和设计原则,以及IR在不同编译器中的应用。通过了解IR的不同用途和设计,读者可以更清晰地理解IR的概念和在编译器中的作用。 文章还介绍了IR的数据结构,包括线性结构、树结构、有向无环图(DAG)和程序依赖图(PDG),并强调了根据具体处理工作的特点选择合适的数据结构的重要性。此外,文章详细介绍了SSA格式的IR设计范式,强调了SSA格式的优点以及在现代编译器中的广泛应用。最后,文章总结了IR的重要概念,包括不同的IR设计、数据结构以及SSA格式的优点,为读者提供了对编译过程的新视角。 总的来说,本文深入浅出地介绍了编译器中的中间代码(IR)的重要概念和设计原则,为读者提供了对IR在编译器中的作用和应用的全面了解。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《编译原理实战课》
新⼈⾸单¥59
立即购买
登录 后留言

全部留言(6)

  • 最新
  • 精选
  • 宫文学Richard
    置顶
    上一节的思考题很有意思,很值得琢磨。我在这里给大家解答一下。 在使用栈自动管理内存的时候,你注意到,其实生成的汇编代码只是改了栈顶指针(比如rsp寄存器)的值而已。你可以用代码直接修改寄存器的值,而像x86的push、pop、ret指令,也会修改栈顶指针。但是,只是修改一下一个寄存器的值,就会分配好内存吗?要知道,现代操作系统都是采用了虚拟内存的机制,我们程序所使用的内存地址,并不是物理内存地址,而是一个逻辑地址。操作系统负责为逻辑内存分配实际的物理内存,通常是分成一页一页来管理的。但是,对于栈来说,分配内存的过程是什么时候发生的呀? 你是不是会想,当我们修改栈指针寄存器的值的时候,就会自动触发内存申请或释放的动作? 但这并不会。我们已经在研究汇编层面的代码了。CPU只会忠实地执行我们生成的指令,并不会做额外的动作。 那,内存到底是怎么分配的呢? 原来,这里会用到一个延迟分配的技术。当你修改栈顶指针的时候,内存并不会马上被分配。但当你在栈里做读写操作的时候(比如修改一个本地变量的值),代码中使用的地址是逻辑地址,而CPU中会有一个MMU单元进行内存寻址,找到实际物理内存。而如果这个逻辑地址并没有对应到一个实际的页帧,也就是并没有分配物理内存,就会触发一个缺页错误(Page Fault)。这个缺页错误是一个中断。既然是中断,那么就要跳转到一个中断处理程序,也就是内核中一段代码,来进行内存的分配,分配完毕以后又跳回到用户态去执行应用程序的代码。对于我们的应用程序来说,触发缺页错误以及执行中断处理程序的过程,是透明的,不可见的。所以才会发生内存神奇地被自动分配的情况。 所以,你看这么一个过程,串联了CPU的知识和操作系统的知识,是不是很有趣呢? (在后面的章节中,以及在《编译原理之美》中,都有对栈指针进行操作的汇编代码,你可以留意一下。)
    2021-01-06
    2
    17
  • qinsi
    关于思考题,SSA只允许给变量赋一次值,如果是循环的话就意味着要创建循环次数那么多的临时变量了?如果SSA有函数/子程序的写法的话,是否就可以把循环改写成函数的递归调用呢?类似这样: int loop(i, a, result) { if (i < a) { int sum = result + i; return loop(i + 1, a, sum); } return result; } int bar(a) { int sum = 0; int i = 0; return loop(i, a, sum); } 如果是在实机上运行且没有尾递归优化的话,相当于是把临时变量都创建在栈上了。

    作者回复: 这个问题很有意思。你问的这个问题其实挺深入,涉及静态分析和动态分析的区别。 是这样的。我们在做编译的时候,大部分时候是做静态的分析,仅仅基于程序文本,不看它运行时的状态。 所以,我们说一个变量从词法角度(Lexically)做了一次赋值就行了。注意,我这里说的词法,不是指词法分析的词法,而是指仅通过程序文本的结构决定。词法作用域(Lexical Scope)中词法,也是同一个意思。 回到你的问题,SSA说的是词法角度的使用和定义(use-def)关系。因为我们的优化算法,基本上也都是静态分析。实际运行时被赋值多次,并不影响静态分析的结果。死代码消除也好,公共子表达式消除也好,都不影响。

    2020-06-12
    6
  • chris
    看过cliff click在95年左右的文章“A Simple Graph-Based Intermediate Representation”,“Global Code Motion Global Value Numbering”,“Combining Analysis, Combining Optimization”,也是介绍PDG的,老师推荐的这篇文章是87年的,之前不知道,想请教click的文章与老师推荐的文章大概是什么关系

    作者回复: click的文章时间更晚一点,描述得更具象一点,阅读起来也更容易,没有那么多数学公式。v8和Graal编译器相关的论文都引用了click的文章。我在第10讲,Graal IR部分,也加了click的论文的链接。 click除了描述基于图的IR,还有几篇论文是描述基于这种IR的算法实现。

    2020-06-14
    1
  • 茶底
    老师为啥go的内容只有一章啊,go内置token/ast等库,yacc三方库也有,写起轮子很舒服,希望宫老师能多讲一些go的。

    作者回复: 是这样的。因为各个编译器虽然有不同,但还是有共性的。有些内容,在前面的编译器里讲了,后面就不用重复了。 这也是我们课程设计的目的:分析每个编译器都是一次认知迭代。到最后,你认识每个编译器的速度会越来越快。

    2020-06-12
    1
  • Jxin
    看龙书。感觉也是只分了hir(中间表达形式)和lir(目标机器语言)。两者可以分别做机器无关代码优化和技术相关代码优化。

    作者回复: 对,高和低也就是个相对概念,没有绝对统一的标准。 Graal编译器(Java的一个JIT编译器)里也是用的hir和lir两个概念做区分就行了。

    2020-06-19
  • 阿木
    循环其实也是分支语句,只是它可以往上跳

    作者回复: 没错!

    2020-06-16
收起评论
显示
设置
留言
6
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部