编译原理chapter8 代码生成ppt课件

1、 第八章 代码生成 序8.1 目的机器8.2 运转存储管理8.3 根本块和流图8.4 下次援用信息8.5 一个简单的代码生成器序代码生成器中间代码符号表目的代码中间代码: 后缀式，三地址代码，语法树。符号表中的项：名字，类型， 嵌套深度，偏移量目的代码：绝对机器代码，可再定位代码， 汇编81 目的机器目的机器 按字节编址，以按字节编址，以4个字节为一个字个字节为一个字. 通用存放器通用存放器R0，R1，Rn-1。 两地址指令方式：两地址指令方式： op source，destination 其中其中op是一个操作码，是一个操作码，source和和destination称为源和目的，是数据域。例

2、称为源和目的，是数据域。例如有如下的操作码：如有如下的操作码： MOV 将源移到目的中将源移到目的中 ADD 将源加到目的中将源加到目的中 SUB 在目的中减去源在目的中减去源 contents(a)表示由a所代表的存放器或存储单元的内容。有关地址方式及它们的汇编言语方式和有关开销如表8.1所示。 表81 目的机器的地址方式 地址方式汇编地址开销直接地址方式MM1寄存器方式RR0间接寄存器*RContents(R)0索引方式c( R)C+ Contents(R)1间接索引方式 *c(R)c(c+ contents(R)1指令开销指令开销开销是与一条指令的长度按字计算相对开销是与一条指令的长度按

3、字计算相对应的。对绝大多数机器和绝大多数指令而言，应的。对绝大多数机器和绝大多数指令而言，用来从存储器中获取一条指令的时间超越了执用来从存储器中获取一条指令的时间超越了执行该指令的时间。行该指令的时间。指令开销指令开销=源地址开销源地址开销+目的地址开销目的地址开销+11MOVR0，R112MOVR5，M23ADD#1，R324SUB4R0，*12R13contents(contents(12contents(R1)contents(4+contents(R0) 生成高质量目的机器代码的一些困难。如， a:=bc用不同的指令序列来实现： 1MOV b , R0 ADD c ，R0 cost6

4、MOV R0 , a 2MOV b , a ADD c , a cost=6 假定R0,R1和R2中分别存放了a,b和c的 地址： 3MOV *R1 , *R0 ADD *R2 , *R0 cost2 假定R1和R2中分别包含b和c的值，并且b的 值 在这个赋值以后不再需求，那么我们还有: 4ADD R2 , R1 MOV R1 , a cost3 有效地利用它的地址才干和存放器。 82 运转存储管理运转存储管理 运转时辰管理活动记录应生成哪些代码，运转时辰管理活动记录应生成哪些代码，静态分配和栈式分配。静态分配和栈式分配。 运转时活动记录的分配和释放是作为过运转时活动记录的分配和释放是作为过

5、程调用和前往序列的一部分，集中讨论如下程调用和前往序列的一部分，集中讨论如下三地址语句生成哪些代码：三地址语句生成哪些代码： 1 call 调用；调用； 2 return 前往；前往； 3 halt 暂停；暂停； 4 action 动作，为其它语句占有动作，为其它语句占有位置。位置。三地址代码 /*s的代码 */ action1 call p action2 halt /*p的代码 */ action3 returnS的活动记录前往地址 arr i jp的活动记录前往地址 buf n8.2.1静态分配管理 call调用语句 MOV #here20，callee.static-area GOTO

6、 callee.code-area MOV指令存放前往地址。 GOTO指令将控制转移到被凋用过程的目的代码。callee.staticarea和callee.codearea分别指示被调用过程活动记录的始址和第一条指令的地址。 从过程callee的前往： GOTO *callee.staticarea822 栈式分配管理栈式分配管理 第一个过程的代码初始化栈：第一个过程的代码初始化栈： MOV #stackstart，SP *初始化初始化栈栈* call p ADD caller. recordsize，SP*将将调用过程的活动记录的长度参与到调用过程的活动记录的长度参与到SP中中* MOV

7、here16，*SP*存储前往地存储前往地址址* GOTO callee.codearea*转移到被转移到被调用过程的代码的第一条指令调用过程的代码的第一条指令* 属性属性caller.recordsize代表一个活动记代表一个活动记录的大小。录的大小。MOVtop,spADD#caller.recordsize,top前往序列包括两个部分：前往序列包括两个部分：GOTO*0SP*前往到调用过程前往到调用过程*MOVsp,topSUB#caller.recordsize,SP823名字的运转地址名字的运转地址x：0静态分配区域的开场地址是静态分配区域的开场地址是static,x的相对地址的相对

8、地址12,那么那么x的的实践地址应为实践地址应为static12。static12：0 假设静态区域是从地址100开场,那么上述语句的目的代码为： MOV #0，112 栈式分配，用一个display表存取非部分名字，又假定该display表是存放在一些存放器中，并且x是部分于一个活动记录的变量，该活动记录的display表指针在存放器R3中，那么，x：0翻译成为如下三地址语句； t1：12R3 *t1：0 其中t1中存放的是x的地址。 这个序列可翻译成如下的机器指令： MOV 0， 12R3留意在存放器R3中的值不能在编译时确定。83 根本块和流图 三地址语句序列的一种图表示法称为流图，它对

9、了解代码生成算法是很有用的。流图中的结点表示计算，边表示控制流向。 831 根本块根本块 定义定义 一个根本块是这样一个延续语一个根本块是这样一个延续语句序列句序列:其中控制流从第一条语句称为入其中控制流从第一条语句称为入口进入，从最后一条语句称为出口口进入，从最后一条语句称为出口分开，中途没有停顿或分枝。例如：分开，中途没有停顿或分枝。例如： t1：a * a t2：a * b t3：2 *t2 t4：t1+t2 t5：b * b t6：t4+t5一条三地址语句x：yz称为对x定值并援用y和z。在一个根本块中的一个名字，所谓在程序中的某个给定点是活泼的，是指如果在程序中包括在本根本块或在其它

10、根本块中它的值在该点以后被援用。算法81划分三地址程序构成根本块输入：一个三地址语句序列。输出：一个根本块表，其中每一条三地址 语句仅在一个块中。方法：1首先确定各个根本块的入口语句。采用如下首先确定各个根本块的入口语句。采用如下 规那么：规那么： a代码序列的第一个语句。代码序列的第一个语句。 b任何一个条件或无条件转移语句转移到任何一个条件或无条件转移语句转移到 的那条语句。的那条语句。 c任何紧接在一个条件或无条件转移语句任何紧接在一个条件或无条件转移语句 之后的那条语句。之后的那条语句。2对每一个入口语句。其根本块是由该入口对每一个入口语句。其根本块是由该入口 语句到下一个入口语句不包

11、括此入口语语句到下一个入口语句不包括此入口语 句、或到一个转移语句包括此转移语句、或到一个转移语句包括此转移语 句、或到一个停语句句、或到一个停语句(包括此停语句之包括此停语句之 间的语句序列组成。间的语句序列组成。例8.3 计算两个长度为20的向量a和b的点积。 begin prod：0; i:=1; do begin prod:=prodprod ai *bi; i:=i1; while i=20 end; 图86 计算向量点积程序1prod:=011prod:=t82i:=112t9:=i1(3t1:=4*i13i:t94t2:=a-l14ifi20goto35t3:=t2t16t4:=

12、4*i7t5:=b48t6:=t5t49t7:=t3*t6(10t8:=prod+t7图图87计算向量点积的三地址代码计算向量点积的三地址代码832 流图流图 (控制流程图控制流程图 定义定义 一个控制流程图是具有独一首一个控制流程图是具有独一首结点的有向图，表示成结点的有向图，表示成 G=(N, E, n0)其中，其中， N是根本块集；是根本块集； n0是首结点，是含有第一条语是首结点，是含有第一条语句的基句的基 本块；本块； E是有向边集。是有向边集。 E的构成如下：根本块的构成如下：根本块Bi和根本块和根本块Bj满满足如下条件之一，那么从足如下条件之一，那么从Bi引一条有向边到引一条有向

13、边到Bj 。 1. Bj紧跟在紧跟在Bi之后，且之后，且Bi的出口语句不是的出口语句不是 goto语句或停语句。语句或停语句。2. Bi的出口语句是“ifgoto L语句，而L是 Bj 的入口语句， Bi是Bj的前驱结点。例： L1: if ab goto L2 goto Lnext L2: if cd goto L3 goto L4 L3: t1 :=y+z x :=t1 goto L1 L4: t2 :=y-z x :=t2 goto L1 L1: if ab goto L2 goto Lnext L2: if cd goto L3 goto L4 L3: t1 :=y+z x :=t1

14、goto L1 L4: t2 :=y-z x :=t2 goto L184 下次援用信息下次援用信息 一一.下次援用信息的用途下次援用信息的用途 充分利用存放器充分利用存放器,把根本块内还要被援把根本块内还要被援用的变量值尽能够保管在存放器中，同时把用的变量值尽能够保管在存放器中，同时把根本块内不再被援用的变量所占用的存放器根本块内不再被援用的变量所占用的存放器及早释放掉。及早释放掉。 术语：下次援用信息，或说下一个援用术语：下次援用信息，或说下一个援用点。点。 每当翻译一条三地址语句每当翻译一条三地址语句x：y op z时，我们需求知道，时，我们需求知道，x，y，z能否还会在根能否还会在根本

15、块内被援用以及用于哪些三地址语句中。本块内被援用以及用于哪些三地址语句中。 i : x:= . j: := xj是i中x的下次援用信息在根本块之内。二. 搜集根本块中关于名字的下次援用信息 假定变量的符号表表项中含有记录下次援用信息和活泼信息的域,一切的非暂时变量在出口处都是活泼的 。1. 开场时，把根本块中各变量的符号表表项开场时，把根本块中各变量的符号表表项 中的下次援用信息域置为中的下次援用信息域置为“无下次援用，无下次援用， 活泼信息域置为活泼信息域置为“活泼。活泼。 2从根本块出口到根本块入口由后向前依次从根本块出口到根本块入口由后向前依次 处置各个三地址语句。对每一个三地址处置各个

16、三地址语句。对每一个三地址 语句语句 i：x：=y op z，依次执行下述步骤：，依次执行下述步骤：a把当前符号表中变量把当前符号表中变量x的下次援用信息的下次援用信息 和活泼信息附加到语句和活泼信息附加到语句i上；上； b把符号表中把符号表中x的下次援用信息和活泼信的下次援用信息和活泼信 息分别置为息分别置为“无下次援用和无下次援用和“非活泼；非活泼；c把当前符号表中变量把当前符号表中变量y和和z的下次援用信的下次援用信 息和活泼信息附加到语句息和活泼信息附加到语句i上；上；d把符号表中把符号表中y和和z的下次援用信息均置的下次援用信息均置 为为i，活泼信息均置为，活泼信息均置为“活泼。活泼

17、。留意留意: 以上次序不可颠倒，由于以上次序不可颠倒，由于y和和z也能够也能够 是是x。例：例： t :=a-b u:=a-c v:=t+u d:=v+u1t:=a+b2u:=a-c3v:=t+u4d:=v+u名字 下次援用 活泼 t 无 非 a 无 活 b 无 活 c 无 活 d 无 活 u 无 活 v 无 活d,u,v:无，活无非44活活u,v:4,活;t:无，非无非3活活3u:3,活；a,c:无，活无非22活活a:2,活；b:无，活无非11活活t:3,活；85一个简单的代码生成器一个简单的代码生成器充分利用存放器，即，一方面尽能够地让充分利用存放器，即，一方面尽能够地让变量的值保管在存放

18、器中即不编出把该变变量的值保管在存放器中即不编出把该变量的值存到内存单元的指令，直到该存放量的值存到内存单元的指令，直到该存放器必需用来存放别的变量值或者已到达根本器必需用来存放别的变量值或者已到达根本块出口为止；另一方面，后续的目的代码尽块出口为止；另一方面，后续的目的代码尽能够地援用变量在存放器中的值，而不访问能够地援用变量在存放器中的值，而不访问主存。主存。例如，例如，a：bc1Ri中存放了中存放了b的值，而的值，而Rj中存放了中存放了c的的值值,且且b在此语句之后不再活泼。在此语句之后不再活泼。ADDRj，Ri其开销为其开销为1，结果在，结果在Ri中。中。作业：写出for语句参考375

19、页题7.9给出 的for语句一样含义序列的三地址 代码，画出其流图。2b存放在Ri中，而c在一个存储单元里，并假定b不再活泼。 ADD c，Ri其开销为2 3或者 MOV c，Rj ADD Rj，Ri 其开销为3851存放器描画器和地址描画器 代码生成算法将运用存放器描画器和地址描画器来记录存放器的内容和名字的地址。 1存放器描画器记录每个存放器的当前内 容，每当需求一个新的存放器时，首先 查看此描画器。假定在初始时存放器描 器指示一切的存放器均为空。当对根本 块进展代码生成时，每个存放器在任一 给 定时辰将保管零个或多个名字的值。 2地址描画器记录在运转时辰的一个名字 的当前值存放的一个位置或多个位置。 它能够是一个存放器地址、一个栈地址 、一个存储单元地址、或这些地址的 一个集合。852 代码生成算法 对每个形如 i：x：y op z 下次援用信息依次执行下述步骤：1 L：= getregi：x:=y op z L经常是一个存放器，也能够是一个存 储单元，用来存放计算y op z所得的结果。2. 思索y的地址描画器以确定y，y 为y的 值当前的存放位置。假设y的值同时在主 存中和一个存放器中，那么y 取存放器 更好。假设y的值尚不在L中，那么生成指令: MOV y，L 3生成指令 op z，L 其中z为z的值存放的地址。同样，假设z的值同时存放在主存中和一个存放器中，那么