编译原理补充

本文最后更新于:2021年10月9日 下午

声明

本人的代码优化还是跟着kp学习的。步前人后尘
所有资料来源于skr_learning of kp,课件pdf来源于toronto,edx等处没有找到对应视频

前言

个人向笔记,仅作为cs143的补充

笔记

基础知识

作者认为,编译器可以从以下方面改善:

  • 最小化操作数
  • 用时间代价小的操作代替时间操作大的操作
  • 减少缓存缺失
  • 多线程工作

而在kp的md中,记录了代码优化的具体方法:

  • 删除公共子表达式:若x op y之前已被计算,且第二次出现时x op y的变量值没有改变,则x op y称为公共子表达式
  • 删除无用代码
  • 用常量代替某一个表达式值(推导出该表达式值为常量)
  • 代码移动:对不管循环多少次都得到相同结果的表达式在进入循环之前就求值
  • 用时间代价小的操作代替时间操作大的操作
  • 删除同步变化的归纳变量
    基础知识:
    basic block:一个3个地址的序列,他满足:
  • 只能从第一个statement开始执行
  • 连续执行到最后一个
    对basic block的优化是local optimization
    flow graph:
    由basic block作为node,若follow(bi)=bj,则建边bi–>bj
    在对basic block建图之后,就可以基于DAG去除无用代码

定义:

  • value numbering:每一个“value”都有一个自己的“number”,之前提到的公共子表达式有着相同的"number",他的作用是对程序中的value/time更敏感
    examples:
1
2
3
4
5
6
7
8
Assign: a->r1,b->r2,c->r3,d->r4
a = b+c; ADD t1 = r2,r3
CPY r1 = t1 //(a = t1)
b = a-d; SUB t2 = r1,r4
CPY r2 = t2 //(b = t2)
c = b+c; ADD t3 = r2,r3
CPY r3 = t3 //(c = t3)
d = a-d; CPY r2 = t2
  • data flow analysis:
    作用是分析每一个基本块的effect(1),组合基本块的效果以在基本块边界派生信息(2),从基本块边界,应用局部技术生成指令信息(3)
  1. 对于变量x以及程序语句点p,如果在流程图中沿着从p开始的某条路径会引用x在p的值,则称x在p是活跃的。显然对于每一个flow graph我们都可以判断活跃变量。
  2. 关于生成与杀死:

杀死:指的是在后续中如果需要计算x op y,则原先的计算结果不可使用,原因是x或y 可能 在这两个过程中间进行了定值操作

生成:指的是在后续中如果需要计算x op y,则原先的计算结果可以之间使用。

examples:

1
2
3
4
5
a = b + c // 生成表达式 b + c
d = e + f
g = b + c // 代码优化时,由于 b+c没有被杀死,所以这一步可以优化为 g = a
b = d // 注意:b被重新定值,与之相关的表达式 b + c被杀死
f = b + c // 由于b+c被杀死,所以代码优化时就 不能! 优化为f = a
  1. SSA 静态单一赋值
    与VN相似,SSA使每一个变量都有唯一的定义,假设程序对同一个变量有不相关的若干次使用,在SSA中会转变成对不同变量的使用

具体内容

消除无用控制流

该算法使用以下四个顺序变化:

  1. 合并冗余分支,如某分支的两个目标是同一个程序块,则替换为跳转语句
  2. 删除空程序块
  3. 合并程序块,
  4. 提升分支指令,若bi跳转到一个空程序块bj而bj以分支结束,则将bi的跳转替换为bj中分支指令的副本

消除冗余

使用VN消除冗余

缓式代码移动

1 计算可用表达式。LCM需要程序块末尾处的可用信息;2 为捕获可用于判断表达式反向移动的信息,LCM需要计算可预测性。3 如果给出了可用性和可预测性的解,对于每个表达式,编译器都可以判断在程序中最早于何处可以对该表达式进行求值。4 LCM中最后一个数据流问题用于判断何时一个最早置放能被推迟到CFG中稍后的一个位置,而仍然能够实现相同的结果。延迟分析表述为CFG上的一个前向数据流问题,其目标在于每个结点n关联的一个集合LaterIn(n),为每条边(i, j)关联一个集合Later(i, j)。5 利用从数据流计算推导出的知识重写代码。


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!