(8.3.1)--第08章-代码生成3-基本块和流图_en.pdf

《(8.3.1)--第08章-代码生成3-基本块和流图_en.pdf》由会员分享，可在线阅读，更多相关《(8.3.1)--第08章-代码生成3-基本块和流图_en.pdf（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Compilers TechniquesCode GenerationHow to Generate Object Code for three address statement sequences?prod=0;i=1;do prod=prod+ai bi;i=i+1;while(i=20);(1)prod=0(2)i=1(3)t1=4 i(4)t2=at1(5)t3=4 i(6)t4=bt3(7)t5=t2 t4(8)t6=prod+t5(9)prod=t6(10)t7=i+1(11)i=t7(12)if i=20 goto(3)The three address code is sho

2、wn on the right.Basic Blocks and Flow GraphsBasic BlockBasic blocksA sequence of successive statements in which the control flow enters from its beginning and leaves from its end.Flow graphsThe directed edges are used to represent the control flow information between the basic blocks,and the flow gr

3、aph of the program can be obtained.Basic Blocks and Flow Graphs(1)prod=0(2)i=1(3)t1=4 i(4)t2=at1(5)t3=4 i(6)t4=bt3(7)t5=t2 t4(8)t6=prod+t5(9)prod=t6(10)t7=i+1(11)i=t7(12)if i=20 goto(3)The method of dividing basic blocks(1)First,determine all entry statements.(1)prod=0(2)i=1(3)t1=4 i(4)t2=at1(5)t3=4

4、 i(6)t4=bt3(7)t5=t2 t4(8)t6=prod+t5(9)prod=t6(10)t7=i+1(11)i=t7(12)if i=20 goto(3)The first statement in the sequence is an entry statement.Any statement that can be transferred from the transfer statement is an entry statement.Any statement immediately following the transfer statement is an entry s

5、tatement.(2)The sequence of statements from each entry statement to the next(or to the end of the program)constitutes a basic blockBasic Blocks and Flow Graphs(1)prod=0(2)i=1(3)t1=4 i(4)t2=at1(5)t3=4 i(6)t4=bt3(7)t5=t2 t4(8)t6=prod+t5(9)prod=t6(10)t7=i+1(11)i=t7(12)if i=20 goto(3)Basic Blocks and Fl

6、ow Graphsprod:=0i:=1t1:=4*it2:=at1t3:=4*It4:=bt3t5:=t2*t4t6:=prod+t5prod:=t6t7:=i+1i:=t7if i=20 goto(3)B1B2Term The three-address statement x=y+z refer to y and z and values x.If the value of a name is referenced after a certain point in the basic block,the name(variable)is said to be active at that

7、 point.Optimization of basic blocksEquivalence of basic blocks The exit points of the two basic blocks have the same set of active variables.For each variable,the two expressions that define its value are equal.There are many equivalent transformations available for basic blocks.Local transformation

8、 Global transformationBasic Blocks and Flow GraphsDelete a local public subexpressionDelete dead codeIf the fixed value x=y+z is no longer referenced,then x is called a dead variable.a=b+ca=b+cb=a db=a dc=b+cc=b+cd=a dd=bChange intoBasic Blocks and Flow GraphsOptimization of basic blocksSwap adjacen

9、t independent statementsAlgebraic transformationt1=b+ct2=x+yt2=x+yt1=b+cIf and only if t1and t2are different,neither x nor y is t1,and neither b norc is t2Change into:x=x+0can be deletedx=x 1can be deletedx=y 2change into x=y yBasic Blocks and Flow GraphsOptimization of basic blocksFlow graphs The c

10、ontrol flow information is added to the basic block set to form a directed graph to represent the program.Node in a flow graph:the first node,the predecessor,and the successor.Basic Blocks and Flow Graphsprod:=0i:=1t1:=4*it2:=at1t3:=4*It4:=bt3t5:=t2*t4t6:=prod+t5prod:=t6t7:=i+1i:=t7if i=20 goto B2B1

11、B2What is a cycle?External circulation and internal circulationAll nodes are strongly connected.Have only circular entrance.Basic Blocks and Flow Graphsprod:=0i:=1t1:=4*it2:=at1t3:=4*It4:=bt3t5:=t2*t4t6:=prod+t5prod:=t6t7:=i+1i:=t7if i=20 goto B2B1B2Flow graphsNext-use informationDetermine the next-

12、use information for x,y,and z for each three-address statement x=y op z.i:x =y op z.no assignment to xj:=x.no assignment to xk:=xUsing the next-use information,you can compress the space required by temporary variables.For each basic block,the next-use information can be obtained by scanning back from the last statement to the first statement.Basic Blocks and Flow GraphsCompilers TechniquesCode Generation