编译原理：第九章目标代码生成(3)

1、9.4 多寄存器下的代码生成算法1. 描述表的扩展： RDLR1,R2,Rn;M2. 活跃信息属性扩展：x(L)RDL.M - 为变量是否在内存描述字段(多值)：9.4.1 扩展环境设置： LOCR(x) 取操作数x地址，寄存器优先被确认！ 寄存器、变量B、和变量C的现行值地址参与运算！ 若 LOCR(x)= Ri - x 值在寄存器 Ri 中！ 应用时：R、B和 C 分别代表:q 为四元式序号其中： 若 xRDL.M 则 x 现行值在内存中！ 相应的操作算符：+=（添加）；-=（删除）。3. 寻址函数 LOCR(x)设置,用以确认X现行值地址! x(n)不活跃；x(y)活跃；x(q) q是最

2、近应用点(活跃)；注9.4.2 基本块内活跃信息求解算法 支持: 在符号表上增设一个信息项（ L ） Lname活跃信息 四元式中变量 X 的附加信息项：X( L ) 取值： L=n/y/q(不活跃/活跃/q活跃) ； 初值：基本块内各变量 SYMBLX( L )分别填写：若 X为非临时变量 则置 X( y ); 否则置 X( n ) 逆序扫描基本块内各四元式(设为 q:( B C A) ):执行： QTq:A( L ):= SYMBLA( L ); SYMBLA( L ):=( n ); QTq:B,C( L ):= SYMBLB,C( L ); SYMBLB,C( L ):=( q );

3、算法 活跃信息生成过程示例： 【例9.11】基本块内下述四元式序列及活跃信息生成如下：QTq：q:( B( L ) C( L ) A( L )(+ a( ) b( ) t1( )(- c( ) d( ) t2( )(* t1( )t2( )t3( )(- a( ) t3( )t4( )(/ t1( ) 2 t5( ) (+ t4( )t5( ) x( ) y n n 6 n 6 y n 4 5 n 3 y y 3 4 yL abcdt1t2xt5t4t3SYMBLX( L )yyyynnynnnn66n5n44n33n22n11 支持: 设置描述表 RDLR1,R2,Rn;M， 设置寻址函数

4、LOCR(X),确认X现行值地址!算法登录寄存器Ri,变量X的现行值状态！ 设 当前扫描的四元式为 q:( B C A ).【主动释放】 若 B(y)且(BRDL.M 或 BA) 则 若有 RDL.Rj=0,则否则 CODE( ST Ri,B ); RDL.M+=B; RDL.Ri-=B; RETURN(R,B,C); 若有Ri，使 RDL.Ri=B ;则 CODE( ST Ri,Rj ); RDL.Rj:=B; R:=LOCR(Ri); B:=LOCR(B); C:=LOCR(C); 加入B删除B9.4.3 寄存器分配函数1- GETR(q,R,B,C)寄存器优先被确认！9.4.3 寄存器分

5、配函数2 若有Ri，使 RDL.Ri=C 且 可交换;则 交换B,C(改变四元式)；转 .;.【选空闲者】 非情况.时！ 若有RDL.Ri=0,则 R:=LOCR(Ri) ; .【强迫释放】 除,情况外！剥夺一 Ri( 剥夺条件: 不活跃/应用点远！ ) 若 D(y)且 DRDL.M 则 CODE( ST Ri,D ); RDL.M+=D; RDL.Ri:=0; RETURN(R,B,C); R:=LOCR(Ri); B:=LOCR(B); C:=LOCR(C); B:=LOCR(B); C:=LOCR(C); RETURN( R,B,C);- GETR(q,R,B,C)9.4.4 多寄存器下

6、目标生成算法设计. 表达式的目标代码生成 GETR(q,R,B,C); 若 RB; 则 CODE(LD R,B; R,C;);否则 CODE( R,C); 对所有Ri,有 RDL.Ri-=A; RDL.M-=A; RDL.R:=A; . 赋值四元式的目标代码生成 支持: 变量的活跃信息；寄存器分配算法； GETR(q,R,B,C); 若 RB; 则 CODE( LD R,B ); 对所有Ri,有 RDL.Ri-=A; RDL.M-=A; RDL.R:=A; 设当前四元式 q:( B C A ): 设当前四元式 q:( = B _ A ) : 多寄存器下目标代码生成过程示例 【例9.12】下述四

7、元式序列(仅标有活跃信息)的目标代码生成过程(设有两个寄存器)： OBJp QTqR0R1 MRDLLD R1,c SUB R1,dt1LD R0,a ADD R0,bt2ST R0,t1LD R1,axST R1,yDIV R1,R0 xADD R1,t111abMUL R0,R1t1y(+ a(4) b(y) t1(3)(- c(y) d(y) t2(3)(* t1(6)t2(n)x(5)(/ a(n) x(n) x(6)(= x(y) _ a(y)(= a(5) _ y(y)(+ x(n) t1(n) x(7)xa基本块出口：LD R1,acdST R1,x1312xa释放寄存器t1t2xyxxayST R0,a习题：【习题9.7】简要叙述在单寄存器下： 表达式的目标代码生成算法； 赋值语句目标代码生成算法；【习题9