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

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 shown 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 graph 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 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 statement.(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 Flow 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 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 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 adjacent 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 control 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 B2B1B2What 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-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