中科大2021－2022学年秋季第一学期《编译原理与技术》第十三讲 代码生成

1、代码生成代码生成代码生成的输入各种中间代码形式目标代码与目标机器模型简单的代码生成器基本块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简单代码生成器寄存器描述记录寄存器的使用情况，即某寄存器中存放的是哪（些）个名字（变量）的值。名字地址描述名字（变量）的当前值的

2、存放场所，如放在寄存器或主存（数据区）或者栈里等。简单代码生成器（续）代码生成算法对基本块中三地址代码，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）在块出口处，将所有活跃名字值刷新到相应存储单元。简单代码生成器（续）函数getR

3、eg（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 bu := a + cv := t + uw:= v + u可用寄存器R0，R1初始，名字a、b和c的值均在相应存储单

4、元中 TAC目标代码REG NAMEt:=a-bmov a, R0sub b, R0 R0含t t在R0u:=a+c mov a, R1 R0含t t在R0 add c, R1 R1含u u在R1v:=t+u add R1, R0 R0含v v在R0R1含u u在R1w:=v+u add R1, R0 R0含w w在R0e.g.1 简单代码生成其它语句的代码生成语句 i 在Ri i 在Mi i 在栈中 a := bi mov b(Ri),R mov Mi,R mov Si(bp),R mov b(R),R mov b(R),R ai := b mov b,a(Ri) mov Mi,R mov

5、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 x则转z AT&T汇编简介语法 INSTR Source， Dest e.g. movl (%ecx), %eax addl $1, %edx前缀与后缀% 寄存器前缀，如 %eax, %ebp$ 立即数前缀，如 ，

6、 $100(十进制）, $0 x99（十六进制）后缀 l , w , b 操作数大小，对应 long, word 和 byte, 如，movl %ebx, %ecxmovb %bl, %al内存寻址方式section : disp ( base, index, scale ) 计算方式如下： base + index * scale + disp section/disp/index/scale(包括base) 均可缺省。section用于实模式下。如，addl (%ebx,%ecx,0 x2), %edx (%ebx+%ecx*0 x2)+%edx %edxsubl 0 x20( %eax,

7、%ecx,0 x4), %ebx %ebx - (%eax+%ecx*0 x4+0 x20) %ebx内存寻址方式leal (%ebx, %ecx) , %eax %ebx + %ecx %eax 这里scale缺省为1。scale 和 disp 中的立即数不加前缀$。常用汇编指令addl , subl , movl , sall pushl , popl , leave , retleal , nop , incljmp , jle 等条件转移指令C语句 i = i * 10 对应汇编码 movl -4(%ebp),%edx / 取变量i的值到寄存器%edx movl %edx,%eax s

8、all $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 ie.g. 2 + 问题main() long i; i = 0;/printf(%ldn, (i=i+1)+(i=i+1)+(i=i+1); case 1/printf(%ldn, (+i)+(+i)+(+i); case 2/printf(%ldn,

9、(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

10、 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

11、 %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在其他结点边上有标记（x0 x的初始值除外），则去除这个标记；（4）x := y ，不必建立新结点而将x标记在y对应的结点

12、旁。基本块DAG构造4i0*t1t1 := 4 * it2 := a t1 t3 := 4 * it4 := b t3 t5 := t2 * t4t6 := prod + t5prod := t6t7 := i + 1i := t7if i = 20 goto (1)基本块DAG构造t1 := 4 * it2 := a t1 t3 := 4 * it4 := b t3 t5 := t2 * t4t6 := prod + t5prod := t6t7 := I + 1i := t7if i = 20 goto (1)4i0*t1a=t2基本块DAG构造t1 := 4 * it2 := a t1

13、t3 := 4 * it4 := b t3 t5 := t2 * t4t6 := prod + t5prod := t6t7 := i + 1i := t7if i = 20 goto (1)4i0* t1,t3a=t2基本块DAG构造t1 := 4 * it2 := a t1 t3 := 4 * it4 := b t3 t5 := t2 * t4t6 := prod + t5prod := t6t7 := i + 1i := t7if i = 20 goto (1)4i0* t1,t3a=t2b=t4基本块DAG构造t1 := 4 * it2 := a t1 t3 := 4 * it4 :=

14、 b t3 t5 := t2 * t4t6 := prod + t5prod := t6t7 := i + 1i := t7if i = 20 goto (1)4i0* t1,t3a=t2b=t4*t5基本块DAG构造t1 := 4 * it2 := a t1 t3 := 4 * it4 := b t3 t5 := t2 * t4t6 := prod + t5prod := t6t7 := i + 1i := t7if i = 20 goto (1)4i0* t1,t3a=t2b=t4*t5+prod0t6基本块DAG构造t1 := 4 * it2 := a t1 t3 := 4 * it4

15、:= b t3 t5 := t2 * t4t6 := prod + t5prod := t6t7 := i + 1i := t7if i = 20 goto (1)4i0* t1,t3a=t2b=t4*t5+prod0t6,prod基本块DAG构造t1 := 4 * it2 := a t1 t3 := 4 * it4 := b t3 t5 := t2 * t4t6 := prod + t5prod := t6t7 := i + 1i := t7if i = 20 goto (1)4i0* t1,t3a=t2b=t4*t5+prod0t6,prod1+t7基本块DAG构造t1 := 4 * it

16、2 := a t1 t3 := 4 * it4 := b t3 t5 := t2 * t4t6 := prod + t5prod := t6t7 := i + 1i := t7if i = 20 goto (1)4i0* t1,t3a=t2b=t4*t5+prod0t6,prod1+t7,i基本块DAG构造t1 := 4 * it2 := a t1 t3 := 4 * it4 := b t3 t5 := t2 * t4t6 := prod + t5prod := t6t7 := i + 1i := t7if i = 20 goto (1)4i0* t1,t3a=t2b=t4*t5+prod0t

17、6,prod1+t7,i20=(1)基本块DAG构造t1 := 4 * it2 := a t1 t3 := 4 * it4 := b t3 t5 := t2 * t4t6 := prod + t5prod := t6t7 := i + 1i := t7if i = 20 goto (1)t1 := 4 * it2 := a t1 t4 := b t1 t5 := t2 * t4prod := prod + t5i := i + 1if i = 20 goto (1)DAG优化后特殊情况下（副作用）注销节点数组元素指针访问过程调用多变量共享存贮基本块DAG构造基本块DAG构造x := a i a j := yz := a i x := a i z := xa j := yDAG优化后但如果 在 i=j 且 ai y时，变换前后语义不等价。解决方案：在构造a i 或a j 时，