第八章代码生成

第八章代码生成内容摘要：

用的话 ， 我们说这个名字在该点是 活跃 的 • 基本块的等价 – 两个基本块计算一组同样的表达式 – 这些表达式的值分别代表同样的活跃名字的值 • 有很多等价变换可用于基本块 – 局部变换 – 全局变换 基本块和流图 • 删除局部公共子表达式 a := b + c a := b + c b := a  d b := a  d c := b + c c := b + c d := a  d d := b • 删除死代码 定值 x := y + z以后不再引用 ， 则称 x为死变量 基本块和流图 • 交换相邻的独立语句 t1 := b + c t2 := x + y t2 := x + y t1 := b + c 当且仅当 x和 y都不是 t1， b和 c都不是 t2 • 代数变换 x := x + 0 可以删除 x := x * 1 可以删除 x := y **2 改成 x := y * y 基本块和流图 流图 把控制流信息加到基本块集合 ， 形成一个有向图来表示程序 首结点 、 前 驱 、 后继 基本块和流图 • 什么是循环 ? – 所有结点是 强连通 的 – 唯一的循环 入口 • 外循环和内循环 prod := 0 i := 1 t1 := 4* i t2:= a[t1] t3 := 4* I t4 := b[t3] t5 := t2 * t4 t6 := prod + t5 prod := t6 t7 := i +1 i := t7 if i = 20 goto B2 B1 B2 基本块和流图 下次引用信息 为每个三地址语句 x := y op z决定 x、 y和 z的下次引用信息 i: x := y op z . . . 没有对 x的赋值 j: … := x … . . . 没有对 x的赋值 k: … := … x 基本块和流图 下次引用信息 为每个三地址语句 x := y op z决定 x、 y和 z的下次引用信息 i: x := y op z . . . 没有对 x的赋值 j: … := x … . . . 没有对 x的赋值 k: … := … x 基本块和流图 • 对每个基本块从最后一个语句反向扫描到第一个语句 ，可以得到下次引用信息 i: x := y op z . . . 没有对 x的赋值 j: … := x … . . . 没有对 x的赋值 k: … := … x 基本块和流图 • 对每个基本块从最后一个语句反向扫描到第一个语句 ，可以得到下次引用信息 i: x := y op z . . . 没有对 x的赋值 j: … := x … . . . 没有对 x的赋值 k: … := … x • 利用下次引用信息 ， 可以压缩临时变量需要的空间 一个简单的代码生成器 • 依次考虑基本块的每个语句 ， 为其产生代码 • 假定三地址语句的每种算符都有对应的目标机器算符 • 假定计算结果留在寄存器中尽可能长的时间 , 除非： – 该寄存器要用于其它计算 ， 或者 – 到基本块结束 一个简单的代码生成器 在没有收集全局信息 前 ， 暂且以基本块为 单位来生成代码 prod := 0 i := 1 t1 := 4* i t2:= a[t1] t3 := 4* I t4 := b[t3] t5 := t2 * t4 t6 := prod + t5 prod := t6 t7 := i +1 i := t7 if i = 20 goto B2 B1 B2 一个简单的。