Archive

Archive for February, 2010

Control Flow Graph Linearisation in OWL BASIC

February 14th, 2010 No comments

To compile the code comprising an OWL BASIC procedure, function or main program into CIL, we must linearise the Control Flow Graph (CFG) representing the program statements. The CFG undergoes many transformations during compilation, for example to eliminate unreachable code or convert GOSUB routines into named procedures. Generation of CIL using Reflection.Emit requires that we can define branch targets in advance of generating branch instructions or marking the target instruction and of course we want to do this in a manner which minimises the number of branches required to represent the code. The structure of the graph may be quite complex, especially for traditional BASIC spaghetti code which uses GOTO excessively rather than the more structured alternatives such as procedures and functions or the control structures introduced in BBC BASIC V .

Consider the following procedure from Sphinx Adventure. It contains three loops, one on line 271 formed with a GOTO back to the start of the line, and two REPEAT .. UNTIL loops.

266 DEF PROCL(L)
267 LOCAL I,J:CO=0:CN=0
268 IF L=1 THEN278
269 PRINT’: RESTORE L: IF O?31<>0 THEN O?31=0:DW=1
270 READ R$,R$:R$="You are "+R$
271 IF LEN(R$)+ POS>CO-CN+39 THEN R$= FNS(R$,39+CO-CN):CO=CO+39: GOTO271
272 PRINT R$: IFL=136 OR L=15 THEN O?56=L
273 IF L=16 AND FL=1 THEN PRINT"The walls are very hot!" ELSE IF L=16 THEN PRINT "The walls are steaming!"
274 IF L<>3 AND L<>142 AND L<>143 THEN PROCEX(L): IF ABS(L-19)=1 AND CH=1 THEN PRINT ELSE IF ABS(L-42)=1 AND VO=1 THEN PRINT
275 IF CH=1 AND ABS(L-19)=1 THEN PROC R(22): PRINT "chasm.":O?53=L
276 IF VO=1 AND ABS(L-42)=1 THEN PROCR(22): PRINT"glacier.":O?53=L
277 IF L=26 OR L=27 THEN O?53=L
278 J=0:I=0:CO=0
279 REPEAT:J=J+1: IF O?J=L THEN CO=CO+1
280 UNTIL J=52: IF CO=0 AND L=1 THEN PROCR(L): GOTO 284 ELSE IF CO=0 AND L<>1 THEN 284 ELSE PRINT:MAX=CO
281 IF L=1 THEN PROCR(3) ELSE PROCR(4)
282 CN=0:CO=MAX: REPEAT I=I+1: IF O?I=L THEN PROCOT(I,CO):CO=CO-1
283 UNTIL I=52
284 IF D<>0 THEN O?31=L
285 IF CF=1 AND L=94 THEN PRINT’"The casket is open."
286 IF L=24 AND SA=1 THEN PRINT’"The safe door is open."
287 PRINT: ENDPROC

The CFG for this code is shown below. Each program statement is shown as a purple box, with control flow to the following statement(s). Conditionals are shown in diamond boxes. The numbers in each purple box are source line numbers, where known.

Careful comparison of the source above and the diagram below will reveal some of the transformations that have been applied to the program; for example, READ R$,R$ on line 270 has been transformed into two consecutive assignment statements which actually take the form R$ = READ() where READ() is a function not available in the source language.

The statement level CFG has been analysed to identify basic-blocks, shown as yellow group nodes, thereby defining a higher level basic-block level CFG. Each basic block has only one entry point statement; none of the statement within the basic block are destinations of other jump instructions. Furthermore, each block has only one exit point.

More text follows this long diagram…

Control Flow Graph for PROC L in Sphinx Adventure

Generating the CIL code for a single basic block is straightforward enough – we can simply iterate through the statements comprising the basic block in order and generate the code for each in turn. However, there are many possible orders in which the code for the basic block themselves could be representing in the CIL, since we can branch from the end of any block to the next block, although of course we must start at the entry block for the procedure. Although any order starting with the entry block can be made to work, where possible we would like program control to flow smoothly from the end of a block to one of its successors without requiring a branch.

At first sight, some sort of topological ordering would seem to be appropriate, but a topological ordering is only well defined for a directed acyclic graph (DAG), and a DAG this program is not. The key to this conundrum is to reduce the directed graph to a DAG by identifying strongly connected components. By contracting each SCC to a single node we obtain what is called the condensation of the CFG which will be a DAG. To the resulting DAG we can apply a topological ordering. The ordering of vertices with each SCC is chosen by starting at the vertex with the greatest in-degree.

In order to identify and contract the SCCs we use an implementation of Tarjan’s algorithm during depth first traversal of the CFG. The reverse post ordering of the primary depth first traversal is used to generate the topological ordering of the condensed CFG.

The resulting ordering of basic blocks is shown in the diagram by the numeric labels to the top-left of each. This will be the order in which the CIL code for them is generated, and it can be seen that in about half of the cases, fall through from one block to the next (consecutive block numbers) without explicit branching can be exploited. Future optimisations will focus on further simplifying the generated code by removing vertices, such as block 31, which contain only jumps.

Categories: .NET, computing, OWL BASIC Tags: ,