《编译原理：第九章目标代码生成(2)》由会员分享，可在线阅读，更多相关《编译原理：第九章目标代码生成(2)（18页珍藏版）》请在金锄头文库上搜索。
1、【例例9.69.6】单寄存器单寄存器( (R R) )下下表达式表达式目标代码生成目标代码生成示例示例：(+ a(+ a(y) (y) b b(y) (y) t t1(y)1(y) )(- c(- c(y) (y) d d(y) (y) t t2(y)2(y) )(* (* t t1(y)1(y)t t2(n)2(n)t t3(y)3(y) )(- a(- a(y) (y) t t3(n)3(n)t t4(y)4(y) )(/ t(/ t1(n) 1(n) 2 2 t t5(y)5(y) )(+ t(+ t4(n)4(n)t t5(n) 5(n) x x(y)(y) )ST R,tST R,t
2、1 1LD R,aLD R,aSUB R,dSUB R,dMUL R,tMUL R,t1 1 ST R,t ST R,t3 3SUB R,tSUB R,t3 3ST R,tST R,t1212DIV R,2DIV R,21313ADD R,ADD R,t t4 41111LD R,tLD R,t1 1人工翻译目标代码：人工翻译目标代码：LD R,cLD R,cADD R,bADD R,bLD R,aLD R,a9.2 9.2 目标代码生成算法设计目标代码生成算法设计注注需要需要随时观察随时观察寄存器状态寄存器状态 ！【例例9.79.7】单寄存器单寄存器( (R R) )下下, ,条件语句条件语
3、句目标代码生成目标代码生成示例示例：如：如：if(ab)x=(a+b)*c; if(ab)x=(a+b)*c; ( a( a(y) (y) b b(y) (y) t t1(y)1(y) )(if t(if t1(n) _ 1(n) _ _ )_ )(+ a(+ a(y) (y) b b(y) (y) t t2(y)2(y) )(* t(* t2(n) 2(n) c c(y) (y) x x(y)(y) )(el _(el _ _ _ _ _ ) )(* a(* a(y) (y) b b(y) (y) t t3(y)3(y) )(- 5(- 5 t t3(n)3(n) x x(y)(y) )(
4、(ieie _ _ _ _ _ ) _ )FJ R,FJ R,？LD R,aLD R,aLD R,aLD R,aMUL R,cMUL R,cJMP_,JMP_,？ ST R, ST R,t t3 312121313SUB R,tSUB R,t3 31414ST R,xST R,x15151515ST R,xST R,x1111GT R,bGT R,belse x=5-a*b;else x=5-a*b;LD R,5LD R,5人人工工翻翻译译过过程程ADD R,bADD R,bMUL R,bMUL R,bLD R,aLD R,a待返待返填填1 1待返待返填填2 2返填返填时机时机1 1返填返填时
5、机时机2 2划分基本块划分基本块注注需要需要及时处理及时处理跳转地址返填跳转地址返填 ！9.2.1 9.2.1 目标代码目标代码生成要点生成要点和和生成环境生成环境 【释放寄存器释放寄存器】编存储指令编存储指令, ,保存占有寄存器的活保存占有寄存器的活跃变量值；通常发生在如下两个时刻：跃变量值；通常发生在如下两个时刻：注注 为结果变量申请寄存器时；为结果变量申请寄存器时； 基本块出口时；基本块出口时； 目标代码生成是在一个目标代码生成是在一个基本块基本块上进行的上进行的： 入口入口: :寄存器寄存器空闲空闲； 出口出口: :释放释放寄存器。寄存器。 目标代码生成是以目标代码生成是以四元式四元式
6、为为对象对象的：的： 表达式、赋值四元式；表达式、赋值四元式；首先对结果变量首先对结果变量申请申请寄存器寄存器； 转向四元式；转向四元式；首先保存占用寄存器的活跃变量值；首先保存占用寄存器的活跃变量值；然后再编跳转指令（不完备！）；然后再编跳转指令（不完备！）；同时记住待返填地址！同时记住待返填地址！然后然后编目标指令编目标指令；并；并修改修改描述表描述表。生成要点生成要点v 虚拟机虚拟机：单一寄存器：单一寄存器 R R ; ; 指令形式指令形式 p:(op R,M )p:(op R,M )变量内变量内存地址存地址v 表、区和栈表、区和栈： QTqQTq 四元式区四元式区( (附有变量的附有变
7、量的活跃信息活跃信息) )； OBJpOBJp 目标代码区；目标代码区； SEMmSEMm 语义栈（登记待返填的目标地址）；语义栈（登记待返填的目标地址）；R:= R:= (R)op(M)(R)op(M)含义：含义：R:= op(M)R:= op(M)或或v 变量和函数变量和函数：RDL= 0 (RRDL= 0 (R空闲空闲) ) ； RDL= X (RRDL= X (R被被X X占用占用) )； BACKBACK(p(pi i,p,pk k)()(返填函数返填函数) )把地址把地址 p pk k 返填到地址返填到地址 p pi i中；中； SYMBLiSYMBLi 符号表；符号表； RDLR
8、 RDLR 寄存器描述表；寄存器描述表； CODECODE(op R,M;)(op R,M;)(送代码函数送代码函数) )把目标代码送目标区；把目标代码送目标区；生成环境生成环境9.2.2 9.2.2 表达式四元式表达式四元式目标代码生成算法：目标代码生成算法： 设当前扫描的四元式设当前扫描的四元式 q q:(:( B C A B C A) ) 为为 A 预分配器存器，编目标预分配器存器，编目标： 算符算符 对应对应的的操作码操作码 若若 RDL=0RDL=0 则则 CODE( CODE( LD R,BLD R,B ； R,CR,C ); ); 若若 RDL=BRDL=B 则则 若若 B(y)
9、B(y) 则则 CODE( CODE( ST R,BST R,B ； R,CR,C ); ); 否则否则 CODE( CODE( R,C R,C ); ); 若若 RDL=CRDL=C 且且 可交换可交换 则则 若若 C(y)C(y) 则则 CODE( CODE( ST R,CST R,C ； R,BR,B ); ); 否则否则 CODE( CODE( R,B R,B ); ); 若若 D D(y)(y) 则则 CODE( CODE( ST R,DST R,D ; ; LD R,BLD R,B ; ; R,C R,C ); );否则否则 CODE( CODE( LD R,BLD R,B ; ;
10、 R,C R,C ); ); 变量变量 A A 登录到描述表中：登录到描述表中： RDL:= A ; RDL:= A ; 若若 RDL=DRDL=D（上述三种情况之外上述三种情况之外 ） 则则 设当前四元式设当前四元式 q q:(:(= B _ A= B _ A) )9.2.3 9.2.3 赋值四元式赋值四元式目标代码生成算法：目标代码生成算法： 若若 RDL=0RDL=0 若若 RDL=BRDL=B 则则 若若 RDL=DRDL=D（D!=B,D!=AD!=B,D!=A ） 则则 若若 D D(y)(y) 则则 CODE( CODE( ST R,DST R,D ; ; LD R,B LD R
11、,B ););否则否则 CODE( CODE( LD R,B LD R,B ); ); 为为 A 预分配器存器，编目标预分配器存器，编目标： 变量变量 A A 登录到描述表中：登录到描述表中： RDL:= A ; RDL:= A ; 若若 B(y)B(y) 则则 CODE( CODE( ST R,B ST R,B ); ); 则则 CODE( CODE( LD R,B LD R,B ); ); 计算机目标代码计算机目标代码生成过程生成过程示例示例：【例【例9.79.7】 if(ab)x=(a+b)*c;else x=5-a*b;if(ab)x=(a+b)*c;else x=5-a*b; OBJ
12、p OBJp QUATq QUATqB BSEMSEMRDLRDL( a( a(y) (y) b b(y) (y) t t1(y)1(y) )(if t(if t1(n) _ 1(n) _ _ )_ )(+ a(+ a(y) (y) b b(y) (y) t t2(y)2(y) )(* t(* t2(n) 2(n) c c(y) (y) x x(y)(y) )(el _(el _ _ _ _ _ ) )(* a(* a(y) (y) b b(y) (y) t t3(y)3(y) )(- 5(- 5 t t3(y)3(y) x x(y)(y) )( (ieie _ _ _ _ _ ) _ )FJ
13、 R,?FJ R,?t t1 1LD R,aLD R,at t2 2LD R,a ADD R,bLD R,a ADD R,bMUL R,cMUL R,cx xJMP_,?JMP_,? LD R,a LD R,a MUL R,bMUL R,bt t3 3 ST R,t ST R,t3 3 LD R,5 LD R,512121313SUB R,SUB R,t t3 3x x1414ST R,xST R,x15151515ST R,xST R,x 1111GT R,bGT R,bt t1 1t t2 2x xt t3 3x x实践中，先返实践中，先返填，后编跳转填，后编跳转指令！指令！9.2.4 9
14、.2.4 条件语句四元式条件语句四元式目标代码生成算法目标代码生成算法：( (接前页接前页) ) 若若 RDV=DRDV=D（D!=BD!=B） 则则 PUSH(p)PUSH(p) ；RDL:=0;RDL:=0; 若若 D D(y)(y) 则则 CODE( CODE( ST R,D ; LD R,B ; FJ R,_ST R,D ; LD R,B ; FJ R,_ );); 否则否则 CODE( CODE( LD R,B ; FJ R,_LD R,B ; FJ R,_ ); ); 设当前四元式设当前四元式 q q:(:(if B _ _ if B _ _ ) ) 若若 RDV=BRDV=B 则
15、则 若若 RDV=0RDV=0 则则 CODE( CODE( LD R,B ; FJ R,_LD R,B ; FJ R,_ ); ); PUSH(p)PUSH(p)； 若若 B(y)B(y) 则则 CODE( CODE( ST R,B ; FJ R,_ST R,B ; FJ R,_ ); ); 否则否则 CODE( CODE( FJ R,_FJ R,_ ); ); PUSH(p) PUSH(p)；RDL:=0;RDL:=0;条件语句的四元式结构条件语句的四元式结构 算法设计：算法设计： 设当前四元式设当前四元式 q q:( :( ieie _ _ _ _ _ _ ) ) 返填转向地址返填转向地
16、址： POP(p); BACK(p,p+2)POP(p); BACK(p,p+2) 返填转向地址返填转向地址： POP(p);BACK(p,p+1)POP(p);BACK(p,p+1) 编转向指令编转向指令：CODE( CODE( JMP _, _JMP _, _ ); PUSH(p); PUSH(p)把这个地把这个地址填到址填到 pp中中 设当前四元式设当前四元式 q q:( :( el _ _ _ el _ _ _ ) )SEMSEM栈顶栈顶地址弹到地址弹到pp中中( (接前页接前页) )条件语句的四元式结构条件语句的四元式结构 若若 RDV=X RDV=X 且且 X(y)X(y) 则则
17、CODE( CODE( ST R,X ; ST R,X ; ); ); 若若 RDV=X RDV=X 且且 X(y)X(y) 则则 CODE( CODE( ST R,X ; ST R,X ; ); ); 计算机目标代码计算机目标代码生成过程生成过程示例示例：【例【例9.79.7】 while (ab) x=(a+b)*c;while (ab) x=(a+b)*c; OBJp OBJp QUATq QUATqB BSEMSEMRDLRDL(2)( a( a(y) (y) b b(y) (y) t t1(y)1(y) )(3)(do t(do t1(n) _ 1(n) _ _ )_ )(4)(+
18、a(+ a(y) (y) b b(y) (y) t t2(y)2(y) )(5)(* t(* t2(n) 2(n) c c(y) (y) x x(y)(y) )(6)(we _(we _ _ _ _ _ ) )FJ R,?FJ R,?t t1 1 LD R,a LD R,at t2 2LD R,a ADD R,bLD R,a ADD R,bMUL R,cMUL R,cx xJMP_,?JMP_,? 1 1ST R,xST R,x GT R,bGT R,bt t1 1t t2 2x x实践中，先返实践中，先返填，后编跳转填，后编跳转指令！指令！ 9.2.5 9.2.5 循环语句四元式循环语句四元
19、式目标代码生成算法目标代码生成算法：(1)(wh _ _ _)( (接前页接前页) ) 设当前四元式设当前四元式 q q:(:(whwh _ _ _ _ _ _ ) )PUSH(p)PUSH(p)； 算法设计：算法设计：( (接前页接前页) ) 若若 RDV=DRDV=D（D!=BD!=B） 则则 PUSH(p)PUSH(p) ；RDL:=0;RDL:=0; 若若 D D(y)(y) 则则 CODE( CODE( ST R,D ; LD R,B ; FJ R,_ST R,D ; LD R,B ; FJ R,_ );); 否则否则 CODE( CODE( LD R,B ; FJ R,_LD R,
20、B ; FJ R,_ ); ); 若若 RDV=BRDV=B 则则 若若 RDV=0RDV=0 则则 CODE( CODE( LD R,B ; FJ R,_LD R,B ; FJ R,_ ); ); PUSH(p)PUSH(p)； 若若 B(y)B(y) 则则 CODE( CODE( ST R,B ; FJ R,_ST R,B ; FJ R,_ ); ); 否则否则 CODE( CODE( FJ R,_FJ R,_ ); ); PUSH(p) PUSH(p)；RDL:=0;RDL:=0; 算法设计：算法设计： 设当前四元式设当前四元式 q q:( :( do B _ _ do B _ _ )
21、) 设当前四元式设当前四元式 q q:( :( we _ _ _ we _ _ _ ) )(3) 返填转向地址返填转向地址： POP(p);BACK(p,p+2)POP(p);BACK(p,p+2)跳转到跳转到 pp去去SEMSEM栈顶栈顶地址弹到地址弹到pp中中( (接前页接前页) ) 若若 RDV=X RDV=X 且且 X(y)X(y) 则则 CODE( CODE( ST R,X ; ST R,X ; ); ); (4) POP(p)POP(p) ; ;(5) CODE(CODE(JMP _, JMP _, pp ););(2) RDL:=0;RDL:=0;9.3 9.3 一个简单代码生成
22、器的实现一个简单代码生成器的实现开始开始预处理预处理取下一取下一基本块基本块取到了取到了变量变量活跃信息活跃信息生成生成取下一取下一四元式四元式：q q基本块基本块出口出口结束结束结束处理结束处理释放寄存器释放寄存器编写编写 目标指令目标指令y yy yn nn n包括划分包括划分基本块基本块 主控程序主控程序 OBJp OBJp QTq QTqB BSEMSEMRDLRDL 表达式与赋值四元式表达式与赋值四元式【例例9.89.8】设有赋值语句（四元式序列）：设有赋值语句（四元式序列）：x=a*(a+b-d)x=a*(a+b-d)；a=(a+b)/2; y=5;a=(a+b)/2; y=5;目
23、标代码生成示例：目标代码生成示例：(* (* a(a(n n) t) t2(n) 2(n) x x(y)(y) )(+ a(+ a(y) (y) b b(y) (y) t t1(y)1(y) )(- t(- t1(y) 1(y) d d(y)(y)t t2(y)2(y) )(/ t(/ t1(n) 1(n) 2 2 a a(y)(y) )(:= (:= 5 _ 5 _ y y(y)(y) )ST R,tST R,t1 1 SUB R,d SUB R,dt t1 1LD R,a ADD R,bLD R,a ADD R,bt t2 2MUL R,aMUL R,ax xDIV R,2DIV R,2a
24、 a9 9ST R,aST R,ay yST ST R,xR,x LD R,tLD R,t1 1 基本块出口基本块出口1111ST R,yST R,y1010LD R,5LD R,5t t1 1t t2 2x xa ay y释放寄释放寄存器！存器！ 条件语句目标代码生成示例：条件语句目标代码生成示例：【例例9.99.9】单寄存器下单寄存器下条件语句条件语句目标代码生成：目标代码生成：如：如：if(ab)x=(a+b)*c;else x=5-a*b;if(ab)x=(a+b)*c;else x=5-a*b; OBJp OBJp QUATq QUATqB BSEMSEMRDLRDL( a( a(y
25、) (y) b b(y) (y) t t1(y)1(y) )(if t(if t1(n) _ 1(n) _ _ )_ )(+ a(+ a(y) (y) b b(y) (y) t t2(y)2(y) )(* t(* t2(n) 2(n) c c(y) (y) x x(y)(y) )(el _(el _ _ _ _ _ ) )(* a(* a(y) (y) b b(y) (y) t t3(y)3(y) )(- 5(- 5 t t3(y)3(y) x x(y)(y) )( (ieie _ _ _ _ _ ) _ )FJ R,?FJ R,?t t1 1LD R,aLD R,at t2 2LD R,a
26、ADD R,bLD R,a ADD R,bMUL R,cMUL R,cx xJMP_,?JMP_,? LD R,a LD R,a MUL R,bMUL R,bt t3 3 ST R,t ST R,t3 3 LD R,5 LD R,512121313SUB R,SUB R,t t3 3x x1414ST R,xST R,x15151515ST R,xST R,x 1111GT R,bGT R,bt t1 1t t2 2x xt t3 3x x习题：习题：【习题习题9.49.4】解释下列词语：解释下列词语： 寄存器状态变量寄存器状态变量 ； 释放寄存器；释放寄存器；【习题习题9.59.5】简要叙述
27、代码生成器简要叙述代码生成器( (控制器控制器) )的过程；的过程；【习题习题9.69.6】已知下列语句：已知下列语句： if(a+bc) x=(a+b)/(c-d)+(a+b);if(a+bc) x=(a+b)/(c-d)+(a+b); 试分别解答：试分别解答： 写出优化的四元式序列；写出优化的四元式序列； 标记变量的活跃信息；标记变量的活跃信息； 描述单寄存器描述单寄存器R R下的目标代码生成过程。下的目标代码生成过程。 条件语句条件语句的的四元式结构四元式结构：quat(Equat(E) )q q1 1(if (if res(Eres(E)_ _ )_ _ )quat(S1)quat(S1)q q2 2(el _ _ _ )(el _ _ _ )quat(S2)quat(S2)q q3 3(ie _ _ _ )(ie _ _ _ )设设 条件语句：条件语句： ifif（E E）S1 ; else S2 ;S1 ; else S2 ;则则 四元式结构：四元式结构：q q2 2(el _ _ _ )(el _ _ _ )注注的下面就是的下面就是 S2 S2 语句的入口。语句的入口。
