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

第9章 目标代码生成,知识点：基本块、程序流图 下次引用信息 代码生成算法,2,9.2 基本块与流图,基本块：是指程序中一组顺序执行的语句序列,其中只有一个入口语句和一个出口语句。具有原子性的一组连续语句序列。控制从第一条语句流入，从最后一条语句流出，中途没有停止或分支如：t1:=a*at2:=b*bt3:=t1+t2,基本块：t1:=a*at2:=a*bt3:=2*t2t4:=t1+t3t5:=b*bt6:=t4+t5,3,基本块的划分方法,确定入口语句，下面的语句是入口语句：三地址代码的第一条语句（若从四元式序列确定基本块的入口语句，则四元式序列的第一个语句）goto语句转移到的语句紧跟在goto语句后面的语句确定基本块，与每一个入口语句相应的基本块：从一个入口语句（含该语句）到下一个入口语句（不含）之间的语句序列从一个入口语句（含该语句）到停止语句（含该语句）之间的语句序列,2.确定基本块的出口语句：下一个入口语句的前导语句转移语句(包括转移语句本身)停语句(包括停语句本身)入口语句和出口语句之间组成一个基本块。,4,例：给以下四元式序列划分基本块。,（1）read C（2）A=0（3）B=1（4）L1:A=A+B（5）if BC goto L2（6）B=B+1（7）goto L1（8）L2:write A（9）halt,根据划分基本块的算法可以确定四元式(1)(4)(6)(8)是入口语句;(3)(5)(7)(9)是出口语句，因此分为四个基本块,（4）L1:A=A+B（5）if BC goto L2,（6）B=B+1（7）goto L1,（8）L2:write A（9）halt,5,Pascal程序片断：,i:=1;while(i=10)do begin ai:=ai+bi;i:=i+1end,(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),6,流图,把控制信息加到基本块集合中，形成程序的有向图，称为流图（控制流图）流图的结点是基本块如果一个结点基本块的入口语句是程序的第一条语句，则称此基本块结点为首结点。如果在某个执行序列中，基本块B2紧跟在基本块B1之后执行，则从B1到B2有一条有向边，B1是B2的前驱，B2是B1的后继。即如果：有一个条件/无条件转移语句从B1的最后一条语句转移到B2的第一条语句；B1的最后一条语句不是转移语句，并且在程序的语句序列中，B2紧跟在B1之后。,7,流图示例：,8,举例,基本块划分：,9,流图：,10,书312页：9.1,B4,B5,B2,