Microsoft PowerPoint - lec11 [兼容模式]

Size: px

Start display at page:

Download "Microsoft PowerPoint - lec11 [兼容模式]"

恳龙
4 years ago
Views:

1 代码生成

2 代码生成代码生成的输入 - 各种中间代码形式目标代码与目标机器模型简单的代码生成器基本块 DAG 图及代码生成

3 目标代码绝对地址目标代码可重定位的目标 - linker/loader 汇编代码 - assembler

4 目标机器模型指令形式 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

5 简单代码生成器寄存器描述记录寄存器的使用情况, 即某寄存器中存放的是哪 ( 些 ) 个名字 ( 变量 ) 的值名字地址描述名字 ( 变量 ) 的当前值的存放场所, 如放在寄存器或主存 ( 数据区 ) 或者栈里等

6 简单代码生成器 ( 续 ) 代码生成算法对基本块中三地址代码,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) 在块出口处, 将所有活跃名字值刷新到相应存储单元

7 简单代码生成器 ( 续 ) - 函数 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 的存储单元

8 e.g.1 简单代码生成三地址码序列 : t := a b u := a + c v := t + u w:= v + u 可用寄存器 R0,R1 初始, 名字 a b 和 c 的值均在相应存储单元中

9 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

10 其它语句的代码生成语句 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

11 转移语句 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

12 AT&T 汇编简介

13 语法 INSTR Source, Dest e.g. movl (%ecx), %eax addl $1, %edx

14 前缀与后缀 % -- 寄存器前缀, 如 %eax, %ebp $ -- 立即数前缀, 如, $100( 十进制 ), $0x99( 十六进制 ) 后缀 l, w, b -- 操作数大小, 对应 long, word 和 byte, 如, movl %ebx, %ecx movb %bl, %al

15 内存寻址方式 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

16 内存寻址方式 leal (%ebx, %ecx), %eax %ebx + %ecx %eax 这里 scale 缺省为 1 scale 和 disp 中的立即数不加前缀 $

17 常用汇编指令 addl, subl, movl, sall pushl, popl, leave, ret leal, nop, incl jmp, jle 等条件转移指令

18 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

19 e.g 问题 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; }

20 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

21 基本块的 DAG 图示基本块内优化变换合并已知量删除冗余运算 - 公共子表达式删除死代码

22 基本块 DAG 构造 ( 不考虑别名数组或指针 ) 对于每条语句 :x := y op z (1) 分别寻找代表 y 或 z 的当前值的结点, 若没有的话, 构造它们的初始结点 ; (2) 利用已有的算符 op 的结点或新建一个 op 结点 ( 左右子树分别标记为 y 和 z), 将 x 标记在旁边 ; (3) 如果 x 在其他结点边上有标记 (x 0 -x 的初始值除外 ), 则去除这个标记 ; (4)x := y, 不必建立新结点而将 x 标记在 y 对应的结点旁

23 基本块 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

24 基本块 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

25 基本块 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

26 基本块 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

27 基本块 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

28 基本块 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

29 基本块 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

30 基本块 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

31 基本块 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

32 基本块 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

33 基本块 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)

34 基本块 DAG 构造特殊情况下 ( 副作用 ) 注销节点 -- 数组元素指针访问过程调用多变量共享存贮

35 基本块 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 ] 时, 注销所有 []= 或 =[] 节点, 即不利用已有节点 ( 做为公共子表达式 ), 而构造一个新的节点

36 由 DAG 生成代码 DAG 中节点重新排序 ( 计算次序 )- 启发式排序算法树最优代码生成 ( 略 )

37 DAG 启发式排序算法 while 还有未列出的内部节点 do { 选一个没有列出的内部节点 n, 其所有父节点均已列出 ; 列出 n; while n 的最左子节点 m 的所有父节点均已列出而且 m 不是叶子节点 do { 列出 m; n := m; } } 列出节点次序的逆序即为节点的最终计算次序

38 e.g. DAG 节点排序 * * c 7 d 11 e 12 a 9 b 10 计算次序 :

Static Enforcement of Security with Types

Static Enforcement of Security with Types 例题 1 一个 C 语言程序及其在 X86/Linux 操作系统上的编译结果如下根据所生成的汇编程序来解释程序中四个变量的存储分配生存期作用域和置初值方式等方面的区别 static long aa = 10; short bb = 20; func( ) { } static long cc = 30; short dd = 40; static long aa = 10; func(