代码生成
代码生成 代码生成的输入 - 各种中间代码形式 目标代码与目标机器模型 简单的代码生成器 基本块 DAG 图及代码生成
目标代码 绝对地址目标代码 可重定位的目标 - linker/loader 汇编代码 - assembler
目标机器模型 指令形式 op 源, 目的 寻址模式 - 绝对地址 :op M, R R op (M) R - 寄存器 :op R1,R2 R2 op R1 R2 - 变址 :op R1,c(R2) (c+r2) op R1 (c+r2) - 间接变址 间接寄存器 - 直接量 op $C, R R + C R
简单代码生成器 寄存器描述记录寄存器的使用情况, 即某寄存器中存放的是哪 ( 些 ) 个名字 ( 变量 ) 的值 名字地址描述名字 ( 变量 ) 的当前值的存放场所, 如放在寄存器或主存 ( 数据区 ) 或者栈里等
简单代码生成器 ( 续 ) 代码生成算法 对基本块中三地址代码,p: x := y op z, 1) 调用函数 getreg( ), 返回存放计算结果的场所 L( 一般为寄存器 R, 也可能是存储单元 ); 2) 若 y 的值不在 L 中, 产生指令 :mov y, L ( 查 y 的名字地址描述获得 y 值的存放场所 y ); 3) 产生指令 :op z,l ( z 是 z 值的存放场所 ), 修改 x 的名字描述和相关寄存器描述 ; 4) 若 y 和 / 或 z 在 p 之后不再引用 出口不活跃且其值在寄存器中, 则修改其相应寄存器和名字地址描述 ; 5) 在块出口处, 将所有活跃名字值刷新到相应存储单元
简单代码生成器 ( 续 ) - 函数 getreg(p:x := y op z): 返回计算结果存放场所 L, 1) 若某寄存器 R 仅含 y 的值且 p 后不再引用和不活跃, 则返回 R;( 好处是可以省掉装载 y 值的指令 mov y,l) 2) 返回某个空闲寄存器 R; 3) 若 x 必须使用寄存器, 则此时 抢占 某个寄存器 R 查看 R 的描述, 如果名字 a 的值在 R 中则产生转储指令 mov R,Ma (Ma:a 的存储单元 ), 并修改相应的描述 ;( 关键是如何抢占及剥夺哪些名字的寄存器使用权 ) 4) 使用 x 的存储单元
e.g.1 简单代码生成 三地址码序列 : t := a b u := a + c v := t + u w:= v + u 可用寄存器 R0,R1 初始, 名字 a b 和 c 的值均在相应存储单元中
e.g.1 简单代码生成 TAC 目标代码 REG NAME t:=a-b mov a, R0 sub b, R0 R0 含 t t 在 R0 u:=a+c mov a, R1 R0 含 t t 在 R0 add c, R1 R1 含 u u 在 R1 v:=t+u add R1, R0 R0 含 v v 在 R0 R1 含 u u 在 R1 w:=v+u add R1, R0 R0 含 w w 在 R0
其它语句的代码生成语句 i 在 R i i 在 M i i 在栈中 a := b[i] mov b(r i ),R mov M i,r mov S i (bp),r mov b(r),r mov b(r),r a[i] := b mov b,a(r i ) mov M i,r mov S i (bp),r mov b,a(r) mov b,a(r) S i 是 i 在栈中偏移,bp 是当前活动记录基址 指针操作语句 :a := * b *a := b
转移语句 goto X JMP X if x op y goto z - 根据寄存器内容是否满足以下条件 : 负 零 正 非负 非零 非正如 if x < y goto z : y x R 判别 R 非负 ( 实施转移 ) - 根据条件码转移如 if x < y goto z : cmp x, y jg z // 若 y > x 则转 z
AT&T 汇编简介
语法 INSTR Source, Dest e.g. movl (%ecx), %eax addl $1, %edx
前缀与后缀 % -- 寄存器前缀, 如 %eax, %ebp $ -- 立即数前缀, 如, $100( 十进制 ), $0x99( 十六进制 ) 后缀 l, w, b -- 操作数大小, 对应 long, word 和 byte, 如, movl %ebx, %ecx movb %bl, %al
内存寻址方式 section : disp ( base, index, scale ) 计算方式如下 : base + index * scale + disp section/disp/index/scale( 包括 base) 均可缺省 section 用于实模式下 如, addl (%ebx,%ecx,0x2), %edx (%ebx+%ecx*0x2)+%edx %edx subl 0x20( %eax,%ecx,0x4), %ebx %ebx - (%eax+%ecx*0x4+0x20) %ebx
内存寻址方式 leal (%ebx, %ecx), %eax %ebx + %ecx %eax 这里 scale 缺省为 1 scale 和 disp 中的立即数不加前缀 $
常用汇编指令 addl, subl, movl, sall pushl, popl, leave, ret leal, nop, incl jmp, jle 等条件转移指令
C 语句 i = i * 10 对应汇编码 movl -4(%ebp),%edx // 取变量 i 的值到寄存器 %edx movl %edx,%eax sall $2,%eax // 左移寄存器 %eax 2 位, %eax == 4 * i addl %edx,%eax // %eax == 5 * i leal 0(,%eax,2),%edx // %eax * 2 %edx, %edx == 10 * i // 为何不用 sall $1, %eax movl %edx,-4(%ebp) // 10 * i i
e.g. 2 ++ 问题 main() { long i; i = 0; //printf("%ld\n", (i=i+1)+(i=i+1)+(i=i+1)); case 1 //printf("%ld\n", (++i)+(++i)+(++i)); case 2 //printf("%ld\n", (i++)+(i++)+(i++)); case 3 return 0; }
case 1 case 2 case 3 movl $0,-4(%ebp) movl -4(%ebp),%edx incl %edx movl %edx,%eax movl %eax,-4(%ebp) movl -4(%ebp),%edx incl %edx movl %edx,%ecx movl %ecx,-4(%ebp) addl %ecx,%eax movl -4(%ebp),%edx incl %edx movl %edx,%ecx movl %ecx,-4(%ebp) addl %ecx,%eax pushl %eax pushl $.LC0 call printf movl $0,-4(%ebp) incl -4(%ebp) incl -4(%ebp) movl -4(%ebp),%eax movl -4(%ebp),%edx addl %edx,%eax incl -4(%ebp) addl -4(%ebp),%eax pushl %eax pushl $.LC0 call printf movl $0,-4(%ebp) movl -4(%ebp),%eax movl -4(%ebp),%edx addl %edx,%eax movl %eax,%edx addl -4(%ebp),%edx pushl %edx incl -4(%ebp) incl -4(%ebp) incl -4(%ebp) pushl $.LC0 call printf
基本块的 DAG 图示 基本块内优化变换 合并已知量 删除冗余运算 - 公共子表达式 删除死代码
基本块 DAG 构造 ( 不考虑别名 数组或指针 ) 对于每条语句 :x := y op z (1) 分别寻找代表 y 或 z 的当前值的结点, 若没有的话, 构造它们的初始结点 ; (2) 利用已有的算符 op 的结点或新建一个 op 结点 ( 左 右子树分别标记为 y 和 z), 将 x 标记在旁边 ; (3) 如果 x 在其他结点边上有标记 (x 0 -x 的初始值除外 ), 则去除这个标记 ; (4)x := y, 不必建立新结点而将 x 标记在 y 对应的结点旁
基本块 DAG 构造 (1) t1 := 4 * i (2) t2 := a [ t1 ] (3) t3 := 4 * i (4) t4 := b [ t3 ] (5) t5 := t2 * t4 (6) t6 := prod + t5 (7) prod := t6 (8) t7 := i + 1 (9) i := t7 (10) if i <= 20 goto (1) * t1 4 i 0
基本块 DAG 构造 (1) t1 := 4 * i (2) t2 := a [ t1 ] (3) t3 := 4 * i (4) t4 := b [ t3 ] (5) t5 := t2 * t4 (6) t6 := prod + t5 (7) prod := t6 (8) t7 := I + 1 (9) i := t7 =[] t2 * t1 (10) if i <= 20 goto (1) a 4 i 0
基本块 DAG 构造 (1) t1 := 4 * i (2) t2 := a [ t1 ] (3) t3 := 4 * i (4) t4 := b [ t3 ] (5) t5 := t2 * t4 (6) t6 := prod + t5 (7) prod := t6 (8) t7 := i + 1 (9) i := t7 =[] t2 * t1,t3 (10) if i <= 20 goto (1) a 4 i 0
基本块 DAG 构造 (1) t1 := 4 * i (2) t2 := a [ t1 ] (3) t3 := 4 * i (4) t4 := b [ t3 ] (5) t5 := t2 * t4 (6) t6 := prod + t5 (7) prod := t6 (8) t7 := i + 1 (9) i := t7 =[] t4 =[] t2 * t1,t3 (10) if i <= 20 goto (1) a b 4 i 0
基本块 DAG 构造 (1) t1 := 4 * i (2) t2 := a [ t1 ] (3) t3 := 4 * i (4) t4 := b [ t3 ] (5) t5 := t2 * t4 (6) t6 := prod + t5 (7) prod := t6 (8) t7 := i + 1 (9) i := t7 * t5 =[] t4 =[] t2 * t1,t3 (10) if i <= 20 goto (1) a b 4 i 0
基本块 DAG 构造 (1) t1 := 4 * i (2) t2 := a [ t1 ] (3) t3 := 4 * i (4) t4 := b [ t3 ] (5) t5 := t2 * t4 (6) t6 := prod + t5 (7) prod := t6 (8) t7 := i + 1 (9) i := t7 + t6 prod 0 * t5 =[] t4 =[] t2 * t1,t3 (10) if i <= 20 goto (1) a b 4 i 0
基本块 DAG 构造 (1) t1 := 4 * i (2) t2 := a [ t1 ] (3) t3 := 4 * i (4) t4 := b [ t3 ] (5) t5 := t2 * t4 (6) t6 := prod + t5 (7) prod := t6 (8) t7 := i + 1 (9) i := t7 + t6,prod prod 0 * t5 =[] t4 =[] t2 * t1,t3 (10) if i <= 20 goto (1) a b 4 i 0
基本块 DAG 构造 (1) t1 := 4 * i (2) t2 := a [ t1 ] (3) t3 := 4 * i (4) t4 := b [ t3 ] (5) t5 := t2 * t4 (6) t6 := prod + t5 (7) prod := t6 (8) t7 := i + 1 (9) i := t7 + t6,prod prod 0 * t5 =[] t4 =[] t2 * t1,t3 (10) if i <= 20 goto (1) a b 4 i 0 + t7 1
基本块 DAG 构造 (1) t1 := 4 * i (2) t2 := a [ t1 ] (3) t3 := 4 * i (4) t4 := b [ t3 ] (5) t5 := t2 * t4 (6) t6 := prod + t5 (7) prod := t6 (8) t7 := i + 1 (9) i := t7 + t6,prod prod 0 * t5 =[] t4 =[] t2 * t1,t3 (10) if i <= 20 goto (1) a b 4 i 0 + t7,i 1
基本块 DAG 构造 (1) t1 := 4 * i (2) t2 := a [ t1 ] (3) t3 := 4 * i (4) t4 := b [ t3 ] (5) t5 := t2 * t4 (6) t6 := prod + t5 (7) prod := t6 (8) t7 := i + 1 (9) i := t7 + t6,prod prod 0 * t5 =[] t4 =[] t2 * t1,t3 (10) if i <= 20 goto (1) a b 4 i 0 <= (1) + t7,i 20 1
基本块 DAG 构造 (1) t1 := 4 * i (2) t2 := a [ t1 ] (3) t3 := 4 * i (4) t4 := b [ t3 ] (5) t5 := t2 * t4 (6) t6 := prod + t5 (7) prod := t6 (8) t7 := i + 1 (9) i := t7 (10) if i <= 20 goto (1) DAG 优化后 (1) t1 := 4 * i (2) t2 := a [ t1 ] (3) t4 := b [ t1 ] (4) t5 := t2 * t4 (5) prod := prod + t5 (6) i := i + 1 (7) if i <= 20 goto (1)
基本块 DAG 构造 特殊情况下 ( 副作用 ) 注销节点 -- 数组元素指针访问过程调用多变量共享存贮
基本块 DAG 构造 x := a[ i ] a[ j ] := y z := a[ i ] DAG 优化后 x := a[ i ] z := x a[ j ]:= y 但如果在 i=j 且 a[i] y 时, 变换前后语义不等价 解决方案 : 在构造 a[ i ] 或 a[ j ] 时, 注销所有 []= 或 =[] 节点, 即不利用已有节点 ( 做为公共子表达式 ), 而构造一个新的节点
由 DAG 生成代码 DAG 中节点重新排序 ( 计算次序 )- 启发式排序算法 树最优代码生成 ( 略 )
DAG 启发式排序算法 while 还有未列出的内部节点 do { 选一个没有列出的内部节点 n, 其所有父节点均已列出 ; 列出 n; while n 的最左子节点 m 的所有父节点均已列出而且 m 不是叶子节点 do { 列出 m; n := m; } } 列出节点次序的逆序即为节点的最终计算次序
e.g. DAG 节点排序 * 1 + 2-3 - 5 * 4 + 8 + 6 c 7 d 11 e 12 a 9 b 10 计算次序 :8 6 5 4 3 2 1