I've released my initial version of the Ronald Mak Pascal compiler on github.com. Professor Mak developed the referenced compiler as part of his book on compilers and interpreters: "Writing Compilers and Interpreters - An Applied Approach.", John Wiley & Sons, New York, NY, 1991.

Professor Mak has given me permission to release the M65C02A version of the compiler under an open source license. I've elected to release the M65C02A version of the compiler under the GPLv3 license. Professor Mak sent me the original source for the 8086 version of the compiler, which required some minor changes to make it compatible with my Visual C++ 6.0 development environment on Windows XP, and the Eclipse C++ SDK development environment on Linux (Mint).

Uncharacteristically, the README.md file included in the repository is very sparse at this time. I'll add to it in future updates, but at present, it simply states that the compiler is a simple recursive descent Pascal compiler for the M65C02A and 8086 processors. The text/book referenced above, also available for C++ and Java, provides a very good description of the theory and practice used in developing recursive descent compilers and interpreters. My contributions are (1) the translation of the Mak 8086 code generator elements into equivalent M65C02A code generator elements; (2) addition of the reference logic for global (level 1) and local variables of nested procedures and functions (level > 1); (3) correction of the integer division function for the 8086 compiler; and (4) some simple optimizations in the array index computations. (I had optimized the structure programming logic jumps, but lost those optimizations in a failure of my source code version control. Will add those optimizations back in soon.)

As provided in the repository, the M65C02A code generator elements are implemented in a brute force manner, and interspersed with the 8086 code generator elements. This was done to ensure that I had properly understood the 8086 instruction mappings and created the appropriate M65C02A instruction mappings. Professor Mak makes extensive use of the capabilities of the target assembler to implement some of the addressing modes used by the 8086 version of the compiler. In other words, the string substitution facilities of the Microsoft assembler are used to create base pointer relative symbolic variable references: STATIC_LINK EQU <WORD PTR [BP+4]>.

Mapping these features to the M65C02A core has not been too difficult, but it has meant that I've had to add some conditional tests in the code generator to ensure that absolute addressing is used when referencing variables declared at level 1, i.e. local variables of the main Pascal program, and base-relative addressing is used when reference variables declared at any level greater than 1. Luckily, Professor Mak provided a number of Pascal programs that exercise the features of the language to test the code generation of the compiler, and I've made extensive use of these programs to test that the M65C02A code generator matches the the 8086 code generator.

An example of the assembler output of the compiler, as currently constituted, is provided in the following code block for the Sieve of Eratosthenes program:


As can be seen, the extended instruction set of the M65C02A maps very well onto the 8086 register set that Professor Mak used to implement the Pascal virtual machine. Extensive use is made of base pointer relative addressing in many of the other example programs, but this simple program uses absolute addressing for level 1 variables, and the stack. Thus, the base-relative (M65C02A XTOS register) and stack relative addressing modes are very much needed to support an efficient mapping of the 8086 to the M65C02A.

One optimization that I've added to the compiler is evident where the load effective address and push register instruction sequence of the 8086 ISA is replaced by the psh #imm16 instruction of the M65C02A ISA. Another is evident where the asl.w instruction is used instead of an imul instruction to calculate the index into the array sieve_002. The adj #imm instruction is used to clean up the stack after procedure calls, or to remove pointers from the top of the stack without affecting registers or memory.

Also included in the repository is a partial assembler specific to the M65C02A instructions used by the compiler. I am using AWK to implement the assembler. I've not yet included a "linker" for the standard library functions, annd I will require a ASCII hexadecimal to binary translator to complete the process. The following code block is an example of the assembler's output for the code block provided above:

_________________
Michael A.

What a gift! Many thanks for making this and sharing it!

The M65C02A Pascal compiler, PC65, has been updated in some minor ways over the past few years. The primary changes in the code generator were (1) that stack-relative addressing was changed to 1-based instead of 0-based as originally implemented, and (2) resolving indirect addressing of pointers on the stack is now performed using the FORTH VM's IP register indirect addressing mode instead of stack-relative indirect addressing.

The AWK-based assembler has been replaced with a Python-based assembler, PyAsm65. In addition to supporting all of the M65C02A instructions, the PyAsm65 assembler provides a number of peephole optimizations that can be applied to the assembler file produced by the Pascal compiler. The peephole optimizations currently performed are as follows:

pho_ldaImmPha_to_pshImm(source)
pho_ldaImmSta_to_Stz(source)
pho_StackAdd_to_DirectAdd(source)
pho_StackCmp_to_DirectCmp(source)
pho_optimizeBooleanTest(source, balanced)
pho_optimizeBooleanTest2(source)
pho_ConvertAdc_to_Inc(source)
pho_optimize1DArrayLoad(source)
pho_optimize1DArrayWrite(source)
pho_ReduceConstantQuotient(source)
pho_ReduceVarImmProduct(source)
pho_ReduceImmVarProduct(source)

Most of these peephole optimizations are performed on the Sieve.asm source file. Some examples of the optimizations are provided below:
pho_ReduceConstantQuotient reduces the following quotient of constants:

into the following code:

pho_optimize1DArrayWrite optimizes 1D array assignment:

into the following code:

This set of peephole optimizations, when applied to Sieve.asm, result in significant improvements in the size and runtime of the Sieve benchmark: runtime is approximately 50% faster. Examples of the other peephole optimizations currently implemented in PyAsm65 can be found be comparing the Sieve.prn and Sieve2.prn files.

Note: the 1D array assignment and load / read peephole optimizations can be further improved. As currently implemented, these optimizations are not currently checking to see if the index is a constant or a variable. If the index is a constant, then a further optimization can be performed so that the dec and asl instructions could be replaced with a ldy #imm instruction. That optimization will be added to these peephole optimization functions in the near future.

_________________
Michael A.

Some results with the PC65 Pascal compiler and PyAsm65 6502/65C02/M65C02A assembler.

For a Pascal implementation of the Sieve of Eratosthenes, the following table (from this thread) provides various timings with and without peephole optimization (provided with the PyAsm65 assembler):
Also, a Fibonacci sequence computation program in Pascal was also generated. The same I/O functions required to implement the Sieve program were used. Three different programs were constructed. The first computes the maximum (signed) 16-bit Fibonacci number in "main", the second uses a function to calculate the maximum Fibonacci number with a single call from "main", and the third uses a recursive function to calculate the maximum Fibonacci number. In the case of the functions, a global array (in "main") is used to hold all of the representable Fibonacci numbers.

Unlike the Sieve program, which used a 1-based array, the Fibonacci programs used a 0-based array to store the Fibonacci numbers. This meant that the array index did not have to be decremented. This made the 1D array peephole optimization routines for the Sieve benchmark not work for the Fibonacci programs. Thus, some additional 1D array index calculation, load, and store peephole optimizers were added plus other optimizers that dealt with variables on the stack rather than in absolutely addressed memory.

The results for the Fibonacci programs are shown in the following table:
The Pascal code, the assembler, and Pascal / Assembler print files for these programs can be found in the TestPgms subdirectory of the PyAsm65 github repository.

Edit: added cross-link for Sieve performance table.

_________________
Michael A.