CSc 453Compilers and Systems Software15 : Intermediate Code IIIDepartment of Computer ScienceUniversity of [email protected]° 2009 Christian CollbergBasic Blocks and Flow GraphsControl Flow GraphsWe divide the intermediate code of each procedure into basicblocks. A basic block is a piece of straight line code, i.e. thereare no jumps in or out of the middle of a block.The basic blocks within one procedure are organized as a(control) flow graph, or CFG. A flow-graph hasbasic blocks B1· · · Bnas nodes,a directed edge B1→ B2if control can flow from B1to B2.Special nodes ENTER and EXIT that are the source and sinkof the graph.Inside each basic block can be any of the IRs we’ve seen:tuples, trees, DAGs, etc.ENTERSource nodeEXITSink nodeB2if ... goto B2B3if ... goto B3B4if ... goto B6B6B5goto B2x := a * 5B1y := Z[x]a := a + 1Straight line codeBlockIf-StatementLoopBasicControl Flow Graphs. . .Source Code:X := 20; WHILE X < 10 DOX := X-1; A[X] := 10;IF X = 4 THEN X := X - 2; ENDIF;ENDDO; Y := X + 5;Intermediate Code:(1) X := 20(2) if X>=10 goto (8)(3) X := X-1(4) A[X] := 10(5) if X<>4 goto (7)(6) X := X-2(7) goto (2)(8) Y := X+5Control Flow Graphs. . .Flow Graph:ENTEREXITgoto B2B6X := X − 2;B5Y := X + 5;B4X := X−1;A[X] := 10;if X <> 4 goto B6if x >= 10 goto B4B2B3X := 20;B1:=>=10B4XX4B6<>EXITX−X2gotoB2:=XY+5X:=20ENTER:=X−1X[]A X:=10B2B6B4B5B3B1Constructing Basic BlocksConstructing Basic BlocksAssume that the input is a list of tuples. How do we find thebeginning and end of each basic block?1First determine a set of leaders, the first tuple of basicblocks:1The first tuple is a leader.2Tuple L is a leader if there is a tuple if ...goto L orgoto L.3Tuple L is a leader if it immediately follows a tupleif ...goto Bor goto B .2A basic block consists of a leader and all the following tuplesuntil the next leader.Basic Blocks. . .P := 0; I := 1;REPEATP := P + I;IF P > 60 THENP := 0;I := 5ENDIF;I := I * 2 + 1;UNTIL I > 20;K := P * 3(1) P := 0 ⇐ (Rule 1.a)(2) I := 1(3)P := P + I ⇐ (Rule 1.b)(4) IF P <= 60 GOTO (7)(5)P := 0 ⇐ (Rule 1.c)(6) I := 5(7)T1 := I * 2 ⇐ (Rule 1.b)(8) I := T1 + 1(9) IF I <= 20 GOTO (3)(10) K := P * 3 ⇐ (Rule 1.c)Basic Blocks. . .B1: [(1) P:=0; (2) I:=1]B2: [(3) P:=P+I;(4) IF P<=60 GOTO B4]B3: [(5) P:=0; (6) I:=5]B4: [(7) T1:=I*2; (8) I:=T1+1;(9) IF I<=20 GOTO B2]B5: [(10) K:=P*3]B4P := 0I := 1B1K := P * 3 B5I := T1 + 1IF I <= 20 GOTO B2T1 := I * 2B3I := 5P := 0P := P + IIF P <= 60 GOTO B4B2SummaryReadings and ReferencesRead Louden:Flow Graphs 475–477Or, read the Dragon book:Basic Blocks 528–530Flow Graphs 532–534SummaryA Control Flow Graph (CFG) is a graph whose nodes are basicblocks. There is an edge from basic block B1to B2if controlcan flow from B1to B2.Control flows in and out of a CFG through two special nodesENTER and EXIT.We construct a CFG for each procedure. This representationis used during code generation and optimization.Java bytecode is a stack-based IR. It was never intended as anUNCOL, but people have still built compilers for Ada, Schemeand other languages that generate Java bytecode. It is painful.Microsoft’s MSIL is the latest UNCOL attempt.HomeworkHomework ITranslate the program below into quadruples. Identify beginningsand ends of basic blocks. Build the control flow graph.PROGRAM P;VAR X : INTEGER; Y : REAL;BEGINX := 1; Y := 5.5;WHILE X < 10 DOY := Y + FLOAT(X);X := X + 1;IF Y > 10 THEN Y := Y * 2.2; ENDIF;ENDDO;END.Exam QuestionDraw the control flow graph for the tuples.int A[5],x,i,n;for (i=1; i<=n; i++) {if (i<n) {x = A[i];} else {while (x>4) {x = x*2+A[i];};};x = x+5;}(1) i := 1(2) IF i>n GOTO (14)(3) IF i>=n GOTO (6)(4) x := A[i](5) GOTO (11)(6) IF x<=4 GOTO (11)(7) T1 := x*2(8) T2 := A[i](9) x := T1+T2(10) GOTO (6)(11) x := x+5(12) i := i+1(13) GOTO
View Full Document
Unlocking...