Sufficiently Small

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…

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.

After a long haul, and diversions into other more important projects — including starting a family — OWL BASIC today produced its first executable. Its not much. In fact its hardly anything. Just 2048 bytes of Windows PE executable containing the global variable declarations from Acornsoft’s 1982 Sphinx Adventure. Each file of BASIC source code will be converted to a single .NET static class, with the global variables as private static fields.

The first executable produced from OWL BASIC.

Above you can see the executable loaded up into .NET Reflector, which can be used to introspect the executable, and in this case attempt to disassemble it into C#. Now we see what makes .NET such a great platform for compiler construction; below is the IronPython source code for the embryonic assembly generation function. It clocks in at fewer than ten lines of code to create an assembly, create a module, create a class, add one private static field to it for each global variable, and save the result as an .exe.

def generateAssembly(name, global_symbols):
    domain = Thread.GetDomain()
    assembly_name = AssemblyName(name)
    assembly_builder = domain.DefineDynamicAssembly(assembly_name, AssemblyBuilderAccess.RunAndSave)
    module_builder = assembly_builder.DefineDynamicModule(name + ".exe")
    type_builder = module_builder.DefineType(name, TypeAttributes.Class | TypeAttributes.Public, object().GetType())

    # Add global variables to the class
    for symbol in global_symbols.symbols.values():
        field_builder = type_builder.DefineField(symbol.name, ctsType(symbol),
                                                 FieldAttributes.Private | FieldAttributes.Static)

    result = type_builder.CreateType()
    assembly_builder.Save(name + ".exe")

where global_symbols is the global symbol table constructed during traversal of the Abstract Syntax Tree and the Control Flow Graph and the ctsType function maps OWL BASIC types to their equivalent Common Type System types for .NET. Everything else is provided by Reflection.Emit and other parts of .NET.

Its interesting that no validation was applied to the variable names supplied to Reflection.Emit. As you can see, the variable names still include the sigil suffixes for variable typing (e.g. $ for string) and Reflector happily dissassembles these into invalid C# identifiers. For the final version these names will need to be mangled (Hungarian notation?), or merely de-sigiled if no conflicts result, for compatibility with other .NET languages and tools.

After 15 years programming in C++, I was surprised to discover today that throw in C++ is an expression rather than a statement. As a result, throw may be used as part of larger expressions.

int x = 5;
int y = x > 4 ? x : throw std::out_of_range;

The only use I’ve found for this — and in fact the speculative attempt by which I discovered it — is range checking within constructor initializer lists.

RangeChecked::RangeChecked(int x) :
    int_member(x > 0 ? x : throw std::out_of_range)
{
}

It’s academic what the type of a throw expression is, since it will never be returned, but for type-checking purposes the compiler seems to be happy to use it in place of any type.