编译原理 代码生成2.ppt

代码生成,代码生成,代码生成的输入各种中间代码形式目标代码与目标机器模型简单的代码生成器基本块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 bu:=a+cv:=t+uw:=v+u可用寄存器R0，R1初始，名字a、b和c的值均在相应存储单元中,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在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 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$立即数前缀，如，$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,%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 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);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)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在其他结点边上有标记（x0 x的初始值除外），则去除这个标记；（4）x:=y，不必建立新结点而将x标记在y对应的结点旁。,基本块DAG构造,4,i0,*,t1,t1:=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),4,i0,*,t1,a,=,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),4,i0,*,t1,t3,a,=,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),4,i0,*,t1,t3,a,=,t2,b,=,t4,基本块DAG构造,t1:=4*it2:=a t1 t3:=4*it4:=b t3 t5:=t2*t4t6:=prod+t5prod:=t6t7:=i+1i:=t7if i=20 goto(1),4,i0,*,t1,t3,a,=,t2,b,=,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),4,i0,*,t1,t3,a,=,t2,b,=,t4,*,t5,+,prod0,t6,基本块DAG构造,t1:=4*it2:=a t1 t3:=4*it4:=b t3 t5:=t2*t4t6:=prod+t5prod:=t6t7:=i+1i:=t7if i=20 goto(1),4,i0,*,t1,t3,a,=,t2,b,=,t4,*,t5,+,prod0,t6,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),4,i0,*,t1,t3,a,=,t2,b,=,t4,*,t5,+,prod0,t6,prod,1,+,t7,基本块DAG构造,t1:=4*it2:=a t1 t3:=4*it4:=b t3 t5:=t2*t4t6:=prod+t5prod:=t6t7:=i+1i:=t7if i=20 goto(1),4,i0,*,t1,t3,a,=,t2,b,=,t4,*,t5,+,prod0,t6,prod,1,+,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),4,i0,*,t1,t3,a,=,t2,b,=,t4,*,t5,+,prod0,t6,prod,1,+,t7,i,20,=,(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:=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,