目标代码生成-基本块与流图

单击此处编辑母版标题样式,*,第,9,章 目标代码生成,知识点：基本块、程序流图,下次引用信息,代码生成算法,9.2,基本块与流图,基本块：,是指程序中一组顺序执行的语句序列,其中只有一个入口语句和一个出口语句。,具有原子性的一组连续语句序列。,控制从第一条语句流入，从最后一条语句流出，中途没有停止或分支,如：,t,1,:=a*a,t,2,:=b*b,t,3,:=t,1,+t,2,基本块：,t,1,:=a*a,t,2,:=a*b,t,3,:=2*t,2,t,4,:=t,1,+t,3,t,5,:=b*b,t,6,:=t,4,+t,5,2,基本块的划分方法,确定入口语句,，下面的语句是入口语句：,三地址代码的第一条语句（若,从四元式序列确定基本块的入口语句，则四元式序列的第一个语句,）,goto,语句转移到的语句,紧跟在,goto,语句后面的语句,确定基本块,，与每一个入口语句相应的基本块：,从一个入口语句（含该语句）到下一个入口语句（不含）之间的语句序列,从一个入口语句（含该语句）到停止语句（含该语句）之间的语句序列,2.,确定基本块的出口语句：,下一个入口语句的前导语句,转移语句,(,包括转移语句本身,),停语句,(,包括停语句本身,),入口语句和出口语句之间组成一个基本块。,3,例：给以下四元式序列划分基本块。,（,1,）,read C,（,2,）,A=0,（,3,）,B=1,（,4,）,L,1,:A=A+B,（,5,）,if BC,goto,L,2,（,6,）,B=B+1,（,7,）,goto,L,1,（,8,）,L,2,:write A,（,9,）,halt,根据划分基本块的算法可以确定四元式,(1)(4)(6)(8),是入口语句,;(3)(5)(7)(9),是出口语句，因此分为四个基本块,（1）read C,（2）A=0,（3）B=1,（,4,）,L,1,:A=A+B,（,5,）,if BC,goto,L,2,（,6,）,B=B+1,（,7,）,goto,L,1,（8）L,2,:write A,（9）halt,4,B,1,B,2,B,3,B,5,B,4,Pascal,程序片断：,i:=1;,while(i=10)do,begin,ai,:=,ai+bi,;,i:=i+1,end,(1)i:=0,(2)if i=10,goto,(4),(3),goto,(17),(4)t1:=4*i,(5)t2:=a-4,(6)t3:=4*i,(7)t4:=a-4,(8)t5:=t4t3 /*t5=,ai,*/,(9)t6:=4*i,(10)t7:=b-4,(11)t8:=t7t6 /*t8=,bi,*/,(12)t9:=t5+t8,(13)t2t1:=t9,(14)t10:=i+1,(15)i:=t10,(16),goto,(2),(17),5,流图,把控制信息加到基本块集合中，形成程序的有向图，称为流图（控制流图）,流图的结点是基本块,如果一个结点基本块的入口语句是程序的第一条语句，则称此基本块结点为首结点。,如果在某个执行序列中，基本块,B,2,紧跟在基本块,B,1,之后执行，则从,B,1,到,B,2,有一条有向边，,B,1,是,B,2,的前驱，,B,2,是,B,1,的后继。即如果：,有一个条件,/,无条件转移语句从,B,1,的最后一条语句转移到,B,2,的第一条语句；,B,1,的最后一条语句不是转移语句，并且在程序的语句序列中，,B,2,紧跟在,B,1,之后。,6,流图示例：,(1)i:=1,B,1,(4)t,1,:=4*i,(5)t,2,:=a-4,(6)t,3,:=4*i,(7)t,4,:=a-4,(8)t,5,:=t,4,t,3,(9)t,6,:=4*i,(10)t,7,:=b-4,(11)t,8,:=t,7,t,6,(12)t,9,:=t,5,+t,8,(13)t,2,t,1,:=t,9,(14)t,10,:=i+1,(15)i:=t,10,(16),goto,B,2,B,4,(2)if i=10,goto,B,4,B,2,(3),goto,B,5,B,3,(17),B,5,7,举例,基本块划分：,(1)i:=m-1,(2)j:=n,(3)t,1,:=4*n,(4)v:=at,1,(5)i:=i+1,(6)t,2,:=4*i,(7)t,3,:=at,2,(8)if t,3,v,goto,(9),(13)if i=j,goto,(23),(14)t,6,:=4*i,(15)x:=at,6,(16)t,7,:=4*i,(17)t,8,:=4*j,(18)t,9,:=at,8,(19)at,7,:=t,9,(20)t,10,:=4*j,(21)at,10,:=x,(22),goto,(5),(23)t,11,:=4*i,(24)x:=at,11,(25)t,12,:=4*i,(26)t,13,:=4*n,(27)t,14,:=at,13,(28)at,12,:=t,14,(29)t,15,:=4*n,(30)at,15,:=x,B,1,B,2,B,3,B,4,B,5,B,6,8,流图：,(1)i:=m-1 (2)j:=n,(3)t,1,:=4*n (4)v:=at,1,(5)i:=i+1 (6)t,2,:=4*i,(7)t,3,:=at,2,(8)if t,3,v,goto,(9),(13)if i=j,goto,(23),(14)t,6,:=4*i,(15)x:=at,6,(16)t,7,:=4*i,(17)t,8,:=4*j,(18)t,9,:=at,8,(19)at,7,:=t,9,(20)t,10,:=4*j,(21)at,10,:=x,(22),goto,(5),(23)t,11,:=4*i,(24)x:=at,11,(25)t,12,:=4*i,(26)t,13,:=4*n,(27)t,14,:=at,13,(28)at,12,:=t,14,(29)t,15,:=4*n,(30)at,15,:=x,B,1,B,2,B,3,B,4,B,5,B,6,B,2,B,3,B,6,B,2,9,书,312,页：,9.1,B4,B5,B2,10,