编译原理之美
宫文学
北京物演科技CEO
立即订阅
8171 人已学习
课程目录
已完结 43 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 为什么你要学习编译原理?
免费
实现一门脚本语言 · 原理篇 (13讲)
01 | 理解代码:编译器的前端技术
02 | 正则文法和有限自动机:纯手工打造词法分析器
03 | 语法分析(一):纯手工打造公式计算器
04 | 语法分析(二):解决二元表达式中的难点
05 | 语法分析(三):实现一门简单的脚本语言
06 | 编译器前端工具(一):用Antlr生成词法、语法分析器
07 | 编译器前端工具(二):用Antlr重构脚本语言
08 | 作用域和生存期:实现块作用域和函数
09 | 面向对象:实现数据和方法的封装
10 | 闭包: 理解了原理,它就不反直觉了
11 | 语义分析(上):如何建立一个完善的类型系统?
12 | 语义分析(下):如何做上下文相关情况的处理?
13 | 继承和多态:面向对象运行期的动态特性
实现一门脚本语言 · 应用篇 (2讲)
14 | 前端技术应用(一):如何透明地支持数据库分库分表?
15 | 前端技术应用(二):如何设计一个报表工具?
实现一门脚本语言 · 算法篇 (3讲)
16 | NFA和DFA:如何自己实现一个正则表达式工具?
17 | First和Follow集合:用LL算法推演一个实例
18 | 移进和规约:用LR算法推演一个实例
实现一门脚本语言 · 热点答疑与用户故事 (2讲)
19 | 案例总结与热点问题答疑:对于左递归的语法,为什么我的推导不是左递归的?
用户故事 | 因为热爱,所以坚持
编译原理 · 期中考试周 (1讲)
期中考试 | 来赴一场100分的约定吧!
免费
实现一门编译型语言 · 原理篇 (12讲)
20 | 高效运行:编译器的后端技术
21 | 运行时机制:突破现象看本质,透过语法看运行时
22 | 生成汇编代码(一):汇编语言其实不难学
加餐 | 汇编代码编程与栈帧管理
23 | 生成汇编代码(二):把脚本编译成可执行文件
24 | 中间代码:兼容不同的语言和硬件
25 | 后端技术的重用:LLVM不仅仅让你高效
26 | 生成IR:实现静态编译的语言
27 | 代码优化:为什么你的代码比他的更高效?
28 | 数据流分析:你写的程序,它更懂
29 | 目标代码的生成和优化(一):如何适应各种硬件架构?
30 | 目标代码的生成和优化(二):如何适应各种硬件架构?
实现一门编译型语言 · 应用篇 (2讲)
31 | 内存计算:对海量数据做计算,到底可以有多快?
32 | 字节码生成:为什么Spring技术很强大?
实现一门编译型语言 · 扩展篇 (3讲)
33 | 垃圾收集:能否不停下整个世界?
34 | 运行时优化:即时编译的原理和作用
35 | 案例总结与热点问题答疑:后端部分真的比前端部分难吗?
面向未来的编程语言 (3讲)
36 | 当前技术的发展趋势以及其对编译技术的影响
37 | 云编程:云计算会如何改变编程模式?
38 | 元编程:一边写程序,一边写语言
结束语 (1讲)
结束语 | 用程序语言,推动这个世界的演化
编译原理之美
登录|注册

28 | 数据流分析:你写的程序,它更懂

宫文学 2019-10-28
上一讲,我提到了删除公共子表达式、拷贝传播等本地优化能做的工作,其实,这几个工作也可以在全局优化中进行。
只不过,全局优化中的算法,不会像在本地优化中一样,只针对一个基本块。而是更复杂一些,因为要覆盖多个基本块。这些基本块构成了一个 CFG,代码在运行时有多种可能的执行路径,这会造成多路径下,值的计算问题,比如活跃变量集合的计算。
当然了,还有些优化只能在全局优化中做,在本地优化中做不了,比如:
代码移动(code motion)能够将代码从一个基本块挪到另一个基本块,比如从循环内部挪到循环外部,来减少不必要的计算。
部分冗余删除(Partial Redundancy Elimination),它能把一个基本块都删掉。
总之,全局优化比本地优化能做的工作更多,分析算法也更复杂,因为 CFG 中可能存在多条执行路径。不过,我们可以在上一节课提到的本地优化的算法思路上,解决掉多路径情况下,V 值的计算问题。而这种基于 CFG 做优化分析的方法框架,就叫做数据流分析。
本节课,我会把全局优化的算法思路讲解清楚,借此引入数据流分析的完整框架。而且在解决多路径情况下,V 值的计算问题时,我还会带你学习一个数学工具:半格理论。这样,你会对基于数据流分析的代码优化思路建立清晰的认识,从而有能力根据需要编写自己的优化算法。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《编译原理之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(3)

  • 沉淀的梦想
    感觉常数传播这个lambda,本质上也是在求半格的最小上界,是不是我们只要定义好V的所有取值组成的半格,然后数据流分析框架就直接将其最小上界作为lambda,就能解决所有的数据流分析问题了?

    作者回复: 我会在答疑部分把数据流分析框架的理论模型再梳理一遍。

    是求最小上界,还是最大下界,主要是看如何比较半序集中元素的大小。

    国外有的人,把数据流框架定义得比较严格,比如Top跟所有的元素x的meet运算,结果都是x;Bottom跟所有元素x的meet运算,结果都是Bottom。按照这个定义,我们文稿中常量传播的Bottom和Top就要互换。

    但也有的人,不觉得必须遵守这个说法,只要有一套规则能计算meet后的结果就行。所以能看到不同的文献,采用不同的叙述方式。

    2019-10-28
    1
  • honnkyou
    是因为meet时有计算并集的情况,也有计算交集的情况,所以引入的半格理论这样理解对吗?
    这部分还是有一些没搞太清楚。
    2019-11-26
  • Lamont
    因为它前面的活变量集合{a}不包括 y,也就是不被后面的代码所使用

    这里的集合{a}是不是应该为{x}?

    作者回复: 是滴是滴,文稿写错了,跟图没对起来。
    多谢你细心的阅读!

    2019-11-21
收起评论
3
返回
顶部