《编译原理 代码生成2.ppt》由会员分享，可在线阅读，更多相关《编译原理 代码生成2.ppt（38页珍藏版）》请在三一文库上搜索。
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）在块出口处，将所有活跃名字值刷新到
3、相应存储单元。,简单代码生成器（续）,函数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 +
4、 u 可用寄存器R0，R1 初始，名字a、b和c的值均在相应存储单元中,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,e.g.1 简单代码生成,其它语句的代码生成 语句 i 在Ri i 在Mi i 在栈中 a := bi mov b(Ri),R mov Mi,R mov Si(bp),R mov b(R),R
5、 mov b(R),R ai := 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 x则转z,AT&T汇编简介,语法,INSTR Source， Dest e.g. movl (%ecx), %eax addl $1, %edx,前缀与后缀,% 寄存器前缀，如 %eax, %ebp $ 立
6、即数前缀，如 ， $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
7、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 m
8、ovl %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(“%ldn“, (i=i+1)+(i=i+1)+(i=i+1); case 1 /printf(“%ldn“, (+i)+(+i)+(+i
9、); case 2 /printf(“%ldn“, (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
10、) 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,%e
11、dx 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在其他结点边上有标记（x0x的初始值除外），则
12、去除这个标记； （4）x := y ，不必建立新结点而将x标记在y对应的结点旁。,基本块DAG构造,4,i0,*,t1,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),基本块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 := t
13、7 if i = 20 goto (1),4,i0,*,t1,a,=,t2,基本块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),4,i0,*,t1,t3,a,=,t2,基本块DAG构造,t1 := 4 * i t2 := a t1 t3 := 4 * i t4 := b t3 t5 := t2 * t4 t6 := prod + t5 prod := t6 t7 := i + 1
14、 i := t7 if i = 20 goto (1),4,i0,*,t1,t3,a,=,t2,b,=,t4,基本块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),4,i0,*,t1,t3,a,=,t2,b,=,t4,*,t5,基本块DAG构造,t1 := 4 * i t2 := a t1 t3 := 4 * i t4 := b t3 t5 := t2 * t4 t6 := pro
15、d + t5 prod := t6 t7 := i + 1 i := t7 if i = 20 goto (1),4,i0,*,t1,t3,a,=,t2,b,=,t4,*,t5,+,prod0,t6,基本块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),4,i0,*,t1,t3,a,=,t2,b,=,t4,*,t5,+,prod0,t6,prod,基本块DAG构造,t1 := 4
16、* 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),4,i0,*,t1,t3,a,=,t2,b,=,t4,*,t5,+,prod0,t6,prod,1,+,t7,基本块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 g
17、oto (1),4,i0,*,t1,t3,a,=,t2,b,=,t4,*,t5,+,prod0,t6,prod,1,+,t7,i,基本块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),4,i0,*,t1,t3,a,=,t2,b,=,t4,*,t5,+,prod0,t6,prod,1,+,t7,i,20,=,(1),基本块DAG构造,t1 := 4 * i t2 := a t1 t3
18、 := 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 a j := y z := a i ,x := a i z :
19、= x a j := y,DAG优化后,但如果 在 i=j 且 ai 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,