Micro Pascal: from code to p-code

The Micro Pascal cross-compiler is coming a long nicely. User-defined functions or procedures aren’t supported yet. Neither are 8-bit characters or strings. FOR loops, IF-THEN-ELSE statements and 16-bit (unsigned) arithmetic operations do work! It can compile simple PASCAL programs like this:

VAR K : INTEGER;
BEGIN
    FOR K:=20 DOWNTO 1 DO
    BEGIN
       WRITE(K*K);
    END
END

Virtual machine instructions

The compiler emits instructions for a simple stack-based virtual machine. For example, the program above compiles to the following instructions:

0000 RESERVE 0002
0003 LIT 0014
0006 STOREP 0000
0009 LOAD 0000
000C LIT 0001
000F CGE
0010 JZ 0025
0013 LOAD 0000
0016 LOAD 0000
0019 MUL
001A WRITE
001B LOAD 0000
001E DEC
001F STOREP 0000
0022 JMP 0009

The ‘RESERVE 0002’ instruction allocates room for local variables on the call/return stack. In this case two bytes for the 16-bit integer K. ‘LIT 0014’ loads 14 hex (20 decimal) onto the operand stack. ‘STOREP 0000’ stores the value at the top of the operand stack (14 hex) into local memory 0, which is where K is stored. At the same time, the value is popped off the operand stack. So, these two instructions set K := 20.

Next, the value stored at memory location 0, again K, is loaded onto the stack. Then, a value of 1 is pushed onto the operand stack. The ‘CGE’, which means Compare Greater or Equal, compares the two top-most values on the stack, pops them off the stack, and pushes a 1 if the condition is true, or 0 if the condition is false.

If the top-most stack value is 0, JZ jumps to the address given as its argument. If not, it continues execution. The top-most stack value is always popped off. Here, the CGE and JZ check if we’re at the end of the loop. If so, a jump to address 25 is made: the program ends.

The instructions from 0013 to 001A square the value of K and print the result to the console. The instructions from 001B to 001F decrement the loop counter K. Finally, a jump to the end-of-loop code is made and the loop is conditionally executed again.

The abstract syntax tree

The Micro Pascal compiler generates the virtual machine code in the traditional way. A lexical analyzer reads the PASCAL source code and recognizes integers, strings, keywords, operators (+,-,/,*,:=,=,<,>,<=,>=,<>, ; , :), keywords (BEGIN, END, FOR, TO, DOWNTO, IF, THEN, ELSE, VAR, CONSTANT, WRITE, etc) and identifiers (variable/procedure/function names). When a part of the input is recognized, the type and position of occurrence is stored. This is termed a token.

When the entire source code as been tokenised, a parser checks the validity of the program. This is done by comparing the order of the tokens against a set of rules that describe the Micro Pascal language. For example, here is the rule that describes the IF-THEN-ELSE construct:

if_then_else

We see that an IF-THEN-ELSE construct must start with an IF token, which must be followed by an expression. The expression is not a token, but rather another construct that is defined elsewhere. The expression must be followed by a THEN token, which must be followed by a statement construct. Now there are two possibilities: we either encounter an ELSE token followed by another statement, or we have nothing (sometimes referred to as an epsilon).

During the parsing process, the parser collects information about the meaning of the program. For instance, it will find which operations are part of the expression and statements found in the IF-THEN-ELSE construct above. The collected information is then represented as a tree, termed the abstract syntax tree, or AST for short.

The Micro Pascal compiler has an option to dump the AST as a Graphviz .dot file for visualization. The compiling the example program results in the following graphical representation of the AST:

program

Each node in the tree corresponds to a language construct.

VM code generation

To generate the p-code for the vitual machine, the p-code generator traverses the tree, starting at the top, going left and depth first. Let’s do that for the example AST.

We start at the BLOCK node. No p-code needs to be emitted for this node, but it does indicate a new stack frame is needed to store local variables. We go left, to the VARDECL. Here we traverse all the child nodes (INT K, in this case) and collect their size in bytes so we can emit a RESERVE instruction. In this step, each variable is also allocated their storage address, which is address 0 for K.

Now we go up the tree again, to the second branch of the BLOCK node, down through the PROGBLOCK to the FOR node. We see that the FOR node uses ‘K’ as the loop variable. The left-most leaf-node is the FOR loop start expression (20), so we the p-code for K:=20. Then we check the loop variable for the end-of-loop condition, i.e. K<1, and exit the current PROGBLOCK if it is true. Now we emit the p-code belonging to the last FOR leaf-node; a PROGBLOCK.

Again, down the tree we go until we end up at the left-most ‘VAR K’ node. This node simply pushes the variable K onto the stack. We go back to the *-node and down to the other ‘VAR K’ node. Again, we push the variable K onto the stack. Now, we’re back at the *-node and emit a MUL operation. Back up the tree, to the WRITE node, where we emit the WRITE p-code. We keep going back until we reach the FOR node again.

Now, we emit the code to update the loop variable K. The parser has already stored the information on what to do, namely: decrement (–) it. We continue to go back up the tree until we reach the BLOCK node, and we’re done!

Address fixups

During the tree traversal, jump instructions are generated. For example, a conditional jump by the FOR node, to exit the FOR loop. At the time the jump instruction is emitted, the address to jump to is not yet known because the loop body code has not yet been generated. To solve this problem, a placeholder is inserted, termed a label, instead of the actual address. Only when all the p-code has been generated, and all the addresses are known, the labels are replaced with the correct addresses in a processes that is called fixup.

Up next…

There is still a lot to do; Micro Pascal still needs functions and procedures. Also, the 16-bit integer is the only available variable type. To comfortably work with characters and strings, an 8-bit character data type needs to be introduced. This is more complex than it might seem. Having more than one data type requires type checking to be implemented as well as extensions to the p-code instruction set.

Writing software for the HD6309 computer: Micro Pascal

At the time of writing, the HD6309 computer does not have an operating system. It can, however, load binary/SREC files via the UART terminal. I have been using the LWTOOLS toolchain to write programs in MC6809/HD6309 assembly language. This has been workable but not very efficient in terms of the time it takes to write them.

I have been searching for compilers and interpreters that I can port to the HD6309 computer. Several exist in the form of FLEX or OS9 binaries. None, that I could find, were available in source code format. Grant Searle solved this by recreating BASIC from the Tandy Color Computer based on the Unravelled series of books. I wanted a more structured language than basic, something more like C or PASCAL.

My search lead to a series of articles on the implementation of Tiny Pascal in BYTE magazine, which contains the full source code in BASIC. This piqued my interest because it, like many early PASCAL systems, produces byte code (also termed p-code) for a simple virtual machine, instead of code that runs directly on the CPU.
The rationale behind this is that it is much easier to port the virtual machine to new architectures and CPUs, compared to creating an architecture-dependent native code generator. The price to pay is lower execution speed; something I’m willing to live with.

Liking the idea of a virtual machine, I set out to re-write the Tiny Pascal compiler in C/C++. With an abundance of C/C++ compilers available for Windows, Linux and OSX, I though it would make a nice contribution to the retro community.
While the original BASIC code is well documented and the article explains most of it, I gave up — I had overestimated my tolerance level of BASIC 🙂 .

Not wanting to abandon the idea, I’m now in the process of writing a new Tiny Pascal-inspired cross-compiler called Micro Pascal.

Micro Pascal will have the following features:
* 16-bit integers.
* 8-bit characters.
* string constants.
* FOR .. DO loop.
* IF .. THEN .. ELSE.
* logical and arithmetic operations.
* direct memory access through built-in MEM[] function.
* a stack-based virtual machine.
* well-documented byte code.

The work-in-progress compiler is available via my GITHUB account. Check back from time to time for progress updates!

Post Retro Challenge update

Yesterday ended with the pizzazz of a wet newspaper when I couldn’t get the HD6309 computer working. Of course, I couldn’t just let this slide, so today I took another shot at bringing up the board.

With a fresh mind and a strong cup of coffee I examined the board that had thwarted me yesterday. The first thing I tried was to add 100pF capacitors tot the clock oscillators as the signals to the processor and UART were ringing like there’s no tomorrow. The divided down E and Q signals, which are generated by the CPU based on this clock, looked fine. However, it’s unclear if the undivided clock signal is used internally by the CPU, so better safe than sorry. That didn’t fix things either.

WinCUPL

At this point I took a look at the programs for the memory and IO decoder GALs. I use WinCUPL to compile these into fuse maps that the TL866 programmer can read. WinCUPL generates quite a few files and one of them is a report that has a .doc extension. It contains the simplified/optimised logic equations for the GAL.

WinCUPL lets you write the logic equations in a high-level manner, such as:

io_cs_n   = !(addr:'B'1110XXXXXXXXXXXX);

Here, addr is a 16-bit address, X means ‘don’t care’ and ‘!’ means negation, so IO_CS_N will go low if the top four bits of the address are 1110. At least, that’s the idea. It turns out that WinCUPL has a bug in it that will not apply the negation. You won’t see that in the waveform simulation of your design, but it will show up in the .doc file equations!

wincuplsim1

The .doc file will show:

io_cs_n =>
    a15
  & a14
  & a13
  & !a12

,which is wrong!

To work around this problem, I directly wrote the simplified equation, instead of relying on the compiler:

io_cs_n = !a15 # !a14 # !a13 # a12;

,where ‘#’ means OR in the WinCUPL language.

There were several other places in the memory and IO decoder programs that caused erroneous compiler output. It is even a documented bug, which they claim has been fixed. Not the case, so watch out if you’re using WinCUPL.

I also noticed an error on my part; I didn’t use the IO_CS_N signal in the IO decoder GAL, which means that IO devices were being selected at the same time as the RAM or ROM! Two devices were competing for the same bus, which won’t give the best outcome.

Fixing both GALs instantly turned the machine into something predictable. It no longer did random things when I pressed the reset button. Progress!

One more thing…

I could see the CPU executing the code I had written:

START:
    JMP START

It was reading only from ROM and the address lines were not toggling, except for a few least-significant ones.

It was time to try the bootloader I had developed and tested using the emulator. No luck, the UART wasn’t responding. The cause of the problem manifested itself when I probed the RESET line and I accidentally ‘shorted’ the RESET pin to OUT1, which was outputting a logic ‘1’. The UART spang to life! During my handling of the board, the bodge wire I had connected to the RESET of the UART must have come loose!

Resoldering the reset wire finally fixed the computer and I’m now greeted with the bootloader screen every time I press the reset button!

working_screenshot

9600 baud — the world is my oyster!

Most of the system seems to be working, including the RAM, which the bootloader checks by reading and writing patterns.

During development I disabled the expansion port and memory mapper. I will have to update the GALs to get them working, but that’s something for another time…

 

Retro Challenge update #8

oh_well

It’s 23:00, the 30th of May. For me, this marks the end of the Retro Challenge 2017/04. I wish I had something working by now, but I must admit defeat — for now.

I did manage to get the HD6309 computer working once when it produced a continuous string of the letter E via the UART. This convinces me that all the connections are correct but that there are timing or glitching issues. The CPU seems to be running some program, just not the one I wrote 🙂 .

To eliminate a partially dead CPU, I replaced it with another one. No change. The CPUs came from EBAY, all from the same seller. Maybe they’re all factory rejects, who knows?

The TL866A programmer has served me well, but I’ve done the “EEPROM dance” more times than I care to remember.

I went over the circuit several times using the oscilloscope. Apart from ringing on the READ, WRITE and E lines, nothing appeared to be overly wrong.

As a last-ditch effort, I added 100pF capacitors to ground on the READ and WRITE lines, which removed much of the ringing. That didn’t make it work any better however. The ringing is most likely a consequence of using “modern” parts, such as the two ATF16V8B GALs. They are pretty fast devices and it shows.

The 150ns access time of the ROM should short enough to supply a HD63C09 running at just over 1.8 MHz with data. The RAM is definitely fast enough, having an access time of 55ns. I might try reducing the clock speed in the future, just to make sure.

I’m glad I participated in the Retro Challenge and it was a challenge indeed! Part of the fun was helping Alan with his 68000 project and seeing others building and developing things: recreations of Andy Warhol classics, a COSMAC system, a TMS9900 CPU implemented in an FPGA and many others.

I’ll probably partake in the Retro Challenge again in the future, although I’m not sure I’d take on a completely self-designed computer with a PCB anytime soon. Speaking of which, I will upload all the design files and software to my GITHUB account sometime this week.

I hope you enjoyed this journey as much as I did. That’s it for now!

Retro Challenge update #7

HD6309_computer_30_4_2017_2_small

Today is the last day of the Retrochallenge 2017/04! Yesterday I tried to get the HD6309 computer up and running. The short version is that it still doesn’t run properly but it is “doing things”. By this I mean it behaves erratically.

When ordering the components, the AT28C64B I had planned to use was out of stock, so I ordered an AT28C256. They come in the same DIP28 package and use two additional pins (1 and 26) for addressing that are labeled not connected on the AT28C64B. So I wired those to ground on the back of the board.

To test the board, I wrote a program that lights up the LEDs connected to OUT1 and OUT2 pins of the SC16C550 UART and continuously sends 0xAA on the TX line. This seems like a small test but for this to work, the CPU, ROM, UART and two GALs must be fully working. Of course, it “didn’t work”.

Using an oscilloscope, I checked for clock signals. They were all there. Then I checked to see if the CPU was toggling its address lines: yes! The ROM_CS and IO_CS lines on the memory decoder GAL are next. Yes, they have activity too! So its very likely the program is actually running and trying to access the UART.

The SC16C550B UART

At this point, the main suspect is the UART. So I started looking at the schematic to see if I had made any mistakes in connecting up the data lines, address lines or the read/write lines. They all seemed fine. Then I spotted a potential mistake… Can you see it?

UART_reset_problem

Anyone, anyone? Bueller? The reset pin on the component does not have a negation bar but the driving reset signal does. It is very uncommon to have an active high reset but I’m also quite meticulous when it comes to making schematic symbols. To be sure this is a problem, I checked the SC16C550B datasheet:

UART_reset_problem_datasheet

It is indeed an active high reset! So, I cut the reset trace going to the UART on the back of the board and connected it to ground. This way, the UART won’t be reset but I hope by writing to all the necessary registers I can put the UART in a defined state. This assumes that the UART doesn’t contain any internal/non-accessible flip-flops that need to be reset for it to function properly.

Almost working?

With the UART reset fix in place, I tried again. Something is happening on the UART TX line but the LEDs still won’t light up :-/ . At least the UART is doing something!

The first thing to check is the baud rate. Using my oscilloscope I measured the on time of the narrowest part of the bit pattern. Remember I’m sending 0xAA? I chose that because the bit pattern is ‘10101010’, which is ideal for measuring.

I expected to be close to 9600 baud, but it was way off! Hmm, that’s not a good sign. The registers of the UART aren’t receiving data correctly or correct data. This also explains why the LEDs aren’t lighting up. To make matters worse, the behaviour of the system changes every time I press the reset button.

The reset line has a 10uF timing capacitor on. This gives a long reset time but it also means that the voltage on the reset pin rises very slowly — too slowly perhaps. So I replaced the capacitor with a 100nF one. This didn’t fix the problem.

As an extra precaution, I inserted some NOP instructions between the UART accesses to increase the time between writes. That did seem to change the behaviour but everything is still unpredictable.

Unfortunately, this is one of those cases where a lot of things can cause this. Here’s a list of causes in order of hopefulness:

  1. The UART interface won’t work properly without a reset pulse.
  2. Bad solder joints.
  3. The data or address lines aren’t stable when data is written to UART.
  4. The CPU isn’t reading the ROM correctly.
  5. The CPU isn’t working properly.

Next up…

I’ll first try and see if I can write data to the 8-bit expansion port. This will give me an idea if the bus timings are okay and that the CPU is behaving correctly.