编程语言详细课程ppt课件

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,*,第八章 代 码 生 成,本章内容,一个简单的代码生成算法,涉及存储管理，指令选择，寄存器分配和计算次序选择,等基本问题,前端,代 码,优 化,器,中间,代码,源程序,代码,生成,器,中间,代码,目标,程序,8.1,代码生成器的设计中的问题,8.1.1,目标程序,可执行目标模块,可重定位目标模块,允许程序模块分别编译,调用其它先前编译好的程序模块,汇编语言程序,免去编译器重复汇编器的工作,从教学角度，增加可读性,8.1,代码生成器的设计中的问题,8.1.2,指令的选择,目标机器指令系统的性质决定了指令选择的难易程度，指令系统的统一性和完备性是重要的因素,指令的速度和机器特点是另一些重要的因素,8.1,代码生成器的设计中的问题,若不考虑目标程序的效率，指令的选择是直截了当的,三地址语句,x = y + z,（x，y,和,z,都是静态分配）,MOVy,R0/,把,y,装入寄存器,R0,/,ADDz,R0 /,z,加到,R0,上,/,MOVR0,x /,把,R0,存入,x,中,/,逐个语句地产生代码，常常得到低质量的代码,8.1,代码生成器的设计中的问题,语句序列,a = b + c,d = a + e,的代码如下,MOV b,R0,ADDc,R0,MOVR0,a,MOVa,R0,ADDe,R0,MOVR0,d,8.1,代码生成器的设计中的问题,语句序列,a = b + c,d = a + e,的代码如下,MOV b,R0,ADDc,R0,MOVR0,a,MOVa,R0-,多余的指令,ADDe,R0,MOVR0,d,8.1,代码生成器的设计中的问题,语句序列,a = b + c,d = a + e,的代码如下,MOV b,R0,ADDc,R0,MOVR0,a,MOVa,R0-,多余的指令,ADDe,R0-,若,a,不再使用，第三条也,MOVR0,d-,多余,8.1,代码生成器的设计中的问题,8.1.3,寄存器分配,运算对象处于寄存器中的指令通常比运算对象处于内存的指令要短一些，执行也快一些,寄存器分配,选择驻留在寄存器中的一组变量,寄存器指派,挑选变量要驻留的具体寄存器,8.1,代码生成器的设计中的问题,8.1.4,计算次序的选择,某种计算次序可能会比其它次序需要较少的寄存器来保存中间结果,8.2,目 标 机 器,8.2.1,目标机器的指令系统,选择可作为几种微机代表的寄存器机器,四字节组成一个字，有,n,个通用寄存器,R0,R1, ,Rn-1。,二地址指令,op,源，目的,MOV,源传到目的,ADD,源加到目的,SUB,目的减去源,8.2,目 标 机 器,地址模式和它们的汇编语言形式及附加代价,模式 形式地址 附加代价,绝对地址,M M 1,寄存器,R R 0,变址,c,(R),c,+,contents,(R) 1,间接寄存器,R,contents,(R) 0,间接变址,c,(R,),contents,(,c,+,contents,(,R,) 1,直接量,#,cc,1,8.2,目 标 机 器,指令实例,MOVR0,M,MOV4(R0),M,contents,(4 +,contents,(R0),MOV,4(R0),M,contents,(,contents,(4 +,contents,(R0) ) ),MOV#1,R0,8.2,目 标 机 器,8.2.2,指令的代价,指令代价取成,1,加上它的源和目的地址模式的附加代价,指令代价,MOV R0,，,R11,MOV R5,，,M,2,ADD #1,，,R32,SUB 4(R0),12(R1) 3,8.2,目 标 机 器,a = b + c，a、b,和,c,都静态分配内存单元,MOV b, R0,ADD c, R0,代价= 6,MOV R0, a,8.2,目 标 机 器,a = b + c，a、b,和,c,都静态分配内存单元,MOV b, R0,ADD c, R0,代价= 6,MOV R0, a,MOV b, a,ADD c, a,代价,= 6,8.2,目 标 机 器,a = b + c，a、b,和,c,都静态分配内存单元,若,R0,，,R1,和,R2,分别含,a,，,b,和,c,的地址，则,MOV,R1,R0,ADD,R2,R0,代价,= 2,8.2,目 标 机 器,a = b + c，a、b,和,c,都静态分配内存单元,若,R0,，,R1,和,R2,分别含,a,，,b,和,c,的地址，则,MOV,R1,R0,ADD,R2,R0,代价,= 2,若,R1,和,R2,分别含,b,和,c,的值，并且,b,的值在这个,赋值后不再需要，则,ADD R2, R1,MOV R1, a,代价,= 3,8.3,基本块和流图,怎样为三地址语句序列生成目标代码？,|(1)prod = 0,prod = 0; |(2)i = 1,i = 1; |(3)t,1,= 4,i,do |(4)t,2,= at,1,prod = prod + ai,bi,; |(5 )t,3,= 4,i,i = i +1; |(6 )t,4,= bt,3, while (i = 20); |(7 )t,5,= t,2,t,4,|(8 )t,6,= prod + t,5,|(9 )prod = t,6,|(10)t,7,= i +1,|(11)i = t,7,|(12 )if i = 20,goto,(3),8.3,基本块和流图,8.3.1,基本块,基本块,：连续的语句序列，控制流从它的开始进入，并从它的末尾离开,再用有向边表示基本块之间的控制流信息，就能得到程序的流图,8.3,基本块和流图,三地址语句序列的,划分基本块,首先确定所有的,入口语句,序列的第一个语句是入口语句,能由条件转移语句或无条件转移语句转到的语句是入口语句,紧跟在条件转移语句或无条件转移语句后面的语句是入口语句,每个入口语句,到下一个,入口语句之前的语句序列构成一个基本块,8.3,基本块和流图,(1)prod = 0,(2)i = 1,(3)t,1,= 4,i,(4)t,2,= at,1,(5 )t,3,= 4,i,(6 )t,4,= bt,3,(7 )t,5,= t,2,t,4,(8 )t,6,= prod + t,5,(9 )prod = t,6,(10)t,7,= i +1,(11)i = t,7,(12 )if i = 20,goto,(3),(1)prod = 0,(2) i = 1,(3) t,1,= 4,i,(4) t,2,= at,1,(5) t,3,= 4,i,(6) t,4,= bt,3,(7) t,5,= t,2,t,4,(8) t,6,= prod + t,5,(9) prod = t,6,(10) t,7,= i +1,(11) i = t,7,(12) if i = 20,goto,(3),B,1,B,2,8.3,基本块和流图,8.3.2,基本块的优化,三地址语句,x = y + z,引用,y,和,z,并对,x,定值,一个名字的值在基本块的某一点以后还要引用的话，则说这个名字在该点是,活跃,的,基本块的等价,两个基本块计算一组同样的表达式,这些表达式的值分别代表同样的活跃名字的值,有很多等价变换可用于基本块,局部变换,全局变换,8.3,基本块和流图,删除局部公共子表达式,a = b + c a = b + c,b = a,db = a,d,c = b + c c = b + c,d = a,d d = b,删除死代码,定值,x = y + z,以后不再引用，,则称,x,为死变量,8.3,基本块和流图,交换相邻的独立语句,t,1,= b,+ c t,2,= x,+ y,t,2,= x,+ y t,1,= b,+ c,当且仅当,t,1,和,t,2,不相同,，,x,和,y,都不是,t,1,，,并且,b,和,c,都不是,t,2,代数变换,x = x + 0,可以删除,x = x,1,可以删除,x = y,2,改成,x = y,y,8.3,基本块和流图,8.3.3,流图,把控制流信息加到基本块集合，形成一个有向图来表示程序,首结点,、,前驱,、后继,8.3,基本块和流图,什么是循环,?,所有结点是,强连通,的,唯一的循环,入口,外循环和内循环,prod = 0,i = 1,t,1,= 4,i,t,2,= at,1,t,3,= 4,i,t,4,= bt,3,t,5,= t,2,t,4,t,6,= prod + t,5,prod = t,6,t,7,= i +1,i = t,7,if i = 20,goto,B,2,B,1,B,2,8.3,基本块和流图,8.3.4 下次引用信息,为每个三地址语句,x = y op z,决定,x、y,和,z,的下次引用信息,i:x = y op z,. . .,没有对,x,的赋值,j: = x ,. . .,没有对,x,的赋值,k: = x,8.3,基本块和流图,8.3.4 下次引用信息,为每个三地址语句,x = y op z,决定,x、y,和,z,的下次引用信息,i:x = y op z,. . .,没有对,x,的赋值,j: = x ,. . .,没有对,x,的赋值,k: = x,8.3,基本块和流图,对每个基本块从最后一个语句反向扫描到第一个语句,，可以得到下次引用信息,i:x = y op z,. . .,没有对,x,的赋值,j: = x ,. . .,没有对,x,的赋值,k: = x,8.3,基本块和流图,对每个基本块从最后一个语句反向扫描到第一个语句,，可以得到下次引用信息,i:x = y op z,. . .,没有对,x,的赋值,j: = x ,. . .,没有对,x,的赋值,k: = x,利用下次引用信息，可以压缩临时变量需要的空间,8.4,一个简单的代码生成器,依次考虑基本块的每个语句，为其产生代码,假定三地址语句的每种算符都有对应的目标机器算符,假定计算结果留在寄存器中尽可能长的时间,除非：,该寄存器要用于其它计算,，或者,到基本块结束,8.4,一个简单的代码生成器,在没有收集全局信息,前，暂且以基本块为,单位来生成代码,prod = 0,i = 1,t,1,= 4,i,t,2,= at,1,t,3,= 4,i,t,4,= bt,3,t,5,= t,2,t,4,t,6,= prod + t,5,prod = t,6,t,7,= i +1,i = t,7,if i = 20,goto,B,2,B,1,B,2,8.4,一个简单的代码生成器,8.4.1,寄存器描述和地址描述,例：对,a = b + c,如果寄存器,Ri,含,b,，,Rj,含,c,，,且,b,此后不再活跃,产生,ADD,Rj,Ri,，,结果,a,在,Ri,中,如果,Ri,含,b,，,但,c,在内存单元,，,b,仍然不再活跃,产生,ADD c,Ri,，,或者,MOV c,Rj,ADD,Rj,Ri,若,c,的值以后还要用,第二种代码比较有吸引力,8.4,一个简单的代码生成器,在代码生成过程中，需要跟踪寄存器的内容和,名字的地址,寄存器描述记住每个寄存器当前存的是什么,在任何一点，每个寄存器保存若干个(包括零个)名字的值,名字的地址描述记住运行时每个名字的当前值可以在哪个场所找到,这个场所可以是寄存器、栈单元、内存地址、甚至是它们的某个集合,这些信息可以存于符号表中,这两个描述在代码生成过程中是变化的,8.4,一个简单的代码生成器,8.4.2,代码生成算法,对每个三地址语句,x = y,op,z,调用函数,getreg,决定放,y,op,z,计算结果的场所,L,查看,y,的地址描述,确定,y,值当前的一个场所,y,.,如果,y,的值还不在,L,中，产生指令,MOV y,，,L,产生指令,op,z,，,L,，,其中,z,是,z,的当前场所之一,如果,y,和/或,z,的当前值不再引用，在块的出口也不活跃，并且还在寄存器中，那么修改寄存器描述,8.4,一个简单的代码生成器,8.4.3,寄存器选择函数,函数,getreg,返回保存,x = y,op,z,的,x,值的场所,L,如果名字,y,在,R,中，这个,R,不含其它名字的值,并且在执行,x = y,op,z,后,y,不再有下次引用，那么返回这个,R,作为,L,否则，返回一个空闲寄存器，如果有的话,否则，如果,x,在块中有下次引用，或者,op,是必须用寄存器的算符，那么找一个已被占用的寄存器,R(,可能产生,MOV R，M,指令，并修改,M,的描述 ),否则，如果,x,在基本块中不再引用，或者找不到适当的被占用寄存器，选择,x,的内存单元作为,L,8.4,一个简单的代码生成器,赋值语句,d = (a,b) + (a,c) + (a,c),编译产生三地址语句序列：,t,1,= a,b,t,2,= a,c,t,3,= t,1,+ t,2,d = t,3,+ t,2,8.4,一个简单的代码生成器,语,句,生成的代码,寄存器描述,名字地址描述,寄存器空,t,1,= a,b,MOV a, R0,SUB b, R0,R0,含,t,1,t,1,在,R0,中,t,2,= a,c,MOV a, R1,SUB c, R1,R0,含,t,1,R1,含,t,2,t,1,在,R0,中,t,2,在,R1,中,t,3,= t,1,+ t,2,ADD R1,R0,R0,含,t,3,R1,含,t,2,t,3,在,R0,中,t,2,在,R1,中,d = t,3,+ t,2,ADD R1,R0,R0,含,d,d,在,R0,中,MOV R0, d,d,在,R0,和内存中,8.4,一个简单的代码生成器,前三条指令可以修改，使执行代价降低,MOV a, R0MOV a, R0,SUB b, R0MOV R0,，,R1,MOV a, R1SUB b, R0,SUB c, R1SUB c, R1,. . . . . .,8.4,一个简单的代码生成器,8.4.4,为,变址和指针,语句产生代码,变址与指针运算的三地址语句的处理和二元算符的处理相同,8.4,一个简单的代码生成器,8.4.5,条件语句,实现条件转移有两种方式,根据寄存器的值是否为下面六个条件之一进行分支：负、零、正、非负、非零和非正,用条件码来表示计算的结果或装入寄存器的值是负、零还是正,8.4,一个简单的代码生成器,根据寄存器的值是否为下面六个条件之一进行,分支：负、零、正、非负、非零和非正,例如：,if x y,goto,z,把,x,减,y,的值存入寄存器,R,如果,R,的值为负，则跳到,z,8.4,一个简单的代码生成器,用条件码的例子,if x y,goto,zx = y + w,的实现：,if x 0,goto,z,CMP x,y,的实现：,CJzMOVy，R0,ADDw，R0,MOVR0，x,CJz,本 章 要 点,代码生成器设计中的主要问题：存储管理、计算次序的选择、寄存器的分配、指令的选择等,目标机器几种常用的地址模式和一些常用的指令,基本块和程序流图,简单的代码生成算法,例 题,1,在,SPARC/SUNOS,上，经某编译器编译，程序的结果,是120。把第4行的,abs(1),改成1的话，则程序结果是1,int,fact(),static,int,i=5;,if(i=0) return(1); ,else i=i-1; return(i+abs(1),fact();,main(),printf(factor,of 5 = %dn, fact();,例 题,2,下面的程序在,X86/Linux,机器上编译后的运行结,果是7，而在,SPARC/SUNOS,机器上编译后的运,行结果是6。试分析运行结果不同的原因。,main(),long i;,i = 0;,printf(%ldn, (+i)+(+i)+(+i) );,例 题,2,按一般的代码生成，,i = i +1,的计算结果保留在,寄存器中，因此这三个,i = i +1,的计算次序不会,影响最终的结果。结果应该是,6,。,+,+,=,=,=,i,i,+,1,i,i,+,1,i,i,+,1,例 题,2,按一般的代码生成，,i = i +1,的计算结果保留在,寄存器中，因此这三个,i = i +1,的计算次序不会,影响最终的结果。结果应该是,6,。,结果是,7,的话，一定是,某个,i = i +1,的结果未保,留在寄存器中,。,上层,计算对它的引用落在,计算另一个,i = i +1,的,后面,+,+,=,=,=,i,i,+,1,i,i,+,1,i,i,+,1,例 题,2,如果机器有,INC,指令的话，编译器极可能产生一条,INC,指令来完成,i = i +1,X86/Linux,机器上果真是这么做的,+,+,=,=,=,i,i,+,1,i,i,+,1,i,i,+,1,例 题,2,将表达式改成,(+,i)+(+i)+(+i),结果会怎样？,+,+,=,=,=,i,i,+,1,i,i,+,1,i,i,+,1,例 题,2,将表达式改成,(+,i)+(+i)+(+i),结果会怎样？,在,SPARC/SUNOS,机器上的结果仍然是6。,在,X86/Linux,机器上的结果是9。,+,+,=,=,=,i,i,+,1,i,i,+,1,i,i,+,1,例 题,3,下面,C,语言程序如下, 运行时输出105, 为什么？,main(),long i;,i=10;,i=(i+5) + (i=i,5);,printf(%dn,i,);,例 题,3,下面,C,语言程序如下, 运行时输出105, 为什么？,main(),long i;,i=10;,i=(i+5) + (i=i,5);,printf(%dn,i,);,二元运算,表达式,表达式,需,2个,R,需,3个,R,需,几个,R,例 题,4,下面是一个,C,语言程序和在,X86/Linux,机器上编译（未使用优化）该程序得到的汇编代码见下页（为便于理解，略去了和讨论本问题无关的部分，并改动了一个地方）,main(),long,i,j,;,if ( j ),i+;,else,while ( i ) j+;,例 题,4,main(),incl,-4(%ebp),jmp,.L3,long,i,j,;.L2: .L4:(,写在一行以省空间,),if ( j ),cmpl,$0,-4(%ebp),i+;,jne,.L6,else,jmp,.L5,while ( i ) j+;.L6:,incl,-8(%ebp),pushl,%,ebp,jmp,.L4,movl,%,esp,%ebp,.L5: .L3: .L1:,subl,$8,%esp,leave,cmpl,$0,-8(%ebp),ret,je,.L2,例 题,4,为什么会出现一条指令前有多个标号的情况，如,.L2,和,.L4,，还有,.L5,、,.L3,和,.L1,？从控制流语句的中间代码结构加以解释。,条件语句和循环语句的中间代码结构如下：,if (E) then S1 else S2while (E) do S,E,的代码,L4: E,的代码,假转,L2,真转,L6,S1,的代码转,L5,转,L3L6:S,的代码,L2:S2,的代码转,L4,L3:L5:,当,while,语句作为条件语句的,S2,时，会出现所说情况,例 题,4,每个函数都有这样的标号,.L1,，它的作用是什么，为什么本函数没有引用该标号的地方？,例 题,4,每个函数都有这样的标号,.L1,，它的作用是什么，为什么本函数没有引用该标号的地方？,.L1,标号定义的入口是返回调用者时该执行的指令，在函数内部有,return,语句时就会跳转到,.L1,。,习 题,第一次：8.4（只为8.1(,e),生成代码）,