代码生成

代码生成 代码生成的输入 －各种中间代码形式 目标代码与目标机器模型 简单的代码生成器 基本块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 在Ri i 在Mi i 在栈中 a := b[i] mov b(Ri),R mov Mi,R mov Si(bp),R mov b(R),R mov b(R),R a[i] := b mov b,a(Ri) mov Mi,R mov Si(bp),R mov b,a(R) mov b,a(R) Si是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（十六进制） $ －－ 立即数前缀，如 ， $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 -4(%ebp),%eax movl -4(%ebp),%edx addl %edx,%eax movl %eax,%edx addl -4(%ebp),%edx pushl %edx incl -4(%ebp) pushl $.LC0 call printf movl $0,-4(%ebp) movl -4(%ebp),%edx incl %edx movl %edx,%eax movl %eax,-4(%ebp) movl %edx,%ecx movl %ecx,-4(%ebp) addl %ecx,%eax pushl %eax pushl $.LC0 call printf movl $0,-4(%ebp) incl -4(%ebp) movl -4(%ebp),%eax movl -4(%ebp),%edx addl %edx,%eax addl -4(%ebp),%eax pushl %eax pushl $.LC0 call printf

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

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

基本块DAG构造 * t1 i0 4 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 (1) * t1 4 i0

基本块DAG构造 * t2 t1 a i0 4 =[] 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 (1) =[] t2 * t1 a 4 i0

基本块DAG构造 * t2 t1,t3 a i0 4 =[] 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 (1) =[] t2 * t1,t3 a 4 i0

基本块DAG构造 * t4 t2 t1,t3 a b 4 i0 =[] =[] t1 := 4 * i t2 := a [ t1 ] t4 := b [ t3 ] t5 := t2 * t4 t6 := prod + t5 prod := t6 t7 := i + 1 i := t7 if i <= 20 goto (1) =[] t4 =[] t2 * t1,t3 a b 4 i0

基本块DAG构造 t5 t4 t2 * t1,t3 a b 4 i0 * =[] =[] 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 (1) t5 * =[] t4 =[] t2 * t1,t3 a b 4 i0

基本块DAG构造 t6 t5 prod0 t4 t2 * t1,t3 a b 4 i0 + * =[] =[] 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 (1) + t6 t5 prod0 * =[] t4 =[] t2 * t1,t3 a b 4 i0

基本块DAG构造 t6,prod t5 prod0 t4 t2 * t1,t3 a b 4 i0 + * =[] =[] 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 (1) + t6,prod t5 prod0 * =[] t4 =[] t2 * t1,t3 a b 4 i0

基本块DAG构造 t6,prod t5 prod0 t4 t2 + t7 * t1,t3 a b 4 i0 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 (1) + t6,prod t5 prod0 * =[] t4 =[] t2 + t7 * t1,t3 a b 4 i0 1

基本块DAG构造 t6,prod t5 prod0 t4 t2 + t7,i * t1,t3 a b 4 i0 1 + * =[] =[] 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 (1) + t6,prod t5 prod0 * =[] t4 =[] t2 + t7,i * t1,t3 a b 4 i0 1

基本块DAG构造 t6,prod t5 (1) prod0 <= t4 20 t2 + t7,i * t1,t3 a b 4 i0 1 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 (1) + t6,prod t5 (1) prod0 * <= =[] t4 20 =[] t2 + t7,i * t1,t3 a b 4 i0 1

基本块DAG构造 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 (1) t1 := 4 * i t2 := a [ t1 ] t4 := b [ t1 ] t5 := t2 * t4 prod := prod + t5 i := i + 1 if i <= 20 goto (1) DAG优化后

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

基本块DAG构造 x := a[ i ] x := a[ i ] a[ j ] := y z := x z := a[ i ] 但如果 在 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节点排序 计算次序：8 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 10 11 12 * + - a b e c 1 2 3 4 5 6 7 8 9 10 11 12 计算次序：8 6 5 4 3 2 1