- CS143 编译原理笔记 5 - Optimization
- 总结
- IR
- Optimization overview
- Block
- control-flow graph
- Optimization 的 3 个粒度
- Local Optimization
- 优化 1：代数化简
- 优化 2：compile time computation
- 优化 3：死代码删除
- SSA - Single assignment form
- 小结
- Peephole Optimization
- dataflow analysis
- Constant propagation
- 问题定义
- Rules
- 完整算法
- Orderings
- Liveness analysis
- 问题定义
- Rules
- 完整算法
CS143 编译原理笔记 5 - Optimization
CS143 编译原理笔记 5 - Optimization
2023年6月21日创建
528
587
总结
本文是 Stanford CS143 Compilers 课程 Week 8 的笔记，讲 Optimization 阶段。
weeks | topic | 视频时长 | 用时/二刷 |
week 8 | optimization | 2h | 4h |
Optimization 是 compiler 的核心，博大精深。这个课只是入门介绍，但很精髓。
提纲：
1.
Optimization 的关键概念：IR，basic block， control-flow graph。
2.
Optimization 的 3 个粒度：local，global，Inter-procedural。
3.
dataflow analysis 的 2 个例子：constant propagation 和 liveness analysis
其他一些 highlight:
1.
optimization 的 2 个利器：basic block，single assignment form。
2.
block 里面不含 control flow，而 cfg（control-flow graph）里可以有。
3.
block 的代码 fully predictable，优化更简单。
4.
optimization 的中文是最优化。有误导，实际上，只是 improvement，并无法保证 best。
5.
dataflow analysis，用一些 rules 描述信息在 statements 之间的 change，不断 apply rules，直到全部满足。
6.
rules 有优先级（ordering） 且 statements 数量有限，因此可证，有限次重复 apply rules 必然能全部满足。
IR
1.
介于 source code 和 target code 之间的一种 language，提供 intermediate level 的抽象能力，简化 optimization 算法。
2.
拥有无限的 register，所以，IR 的 codegen 简单了很多。
3.
表达式的形式，一般采用 three-address code