LCC for the Gigatron. Take two.

[lb3361]

A couple years ago, there was an effort to port the LCC compiler (https://en.wikipedia.org/wiki/LCC_(compiler)) to the Gigatron vCPU. Although LCC is very well documents, it had dark corners (see https://github.com/kervinck/gigatron-rom/issues/76) and was eventually abandoned. There is still code in the gigatron-rom repository, but this code does not work anymore.

I decided to give it another try a few months ago. I studied the old compiler and stole the good ideas, such as having a combined assembler-linker written in python. I rewrote a very different code generator (with some novel ideas in fact) and I solved the register spilling problems. Then I started to write a C library with the idea of supporting as much of ANSI C as possible (to prevent the need for documentation) while keeping enough low-level stuff to write good Gigatron programs. Since this is an infinite task, and since what I have is definitely usable, I've decided to make a first release. See https://github.com/lb3361/gigatron-lcc. This works on Linux only for now.

Highlights:

• It has long integers and floating point.

• The library is missing a couple functions: fseek(), malloc() and some transcendental math functions such as sin(), cos(), ...

• I just finished printf() and scanf(). These functions are too heavy for the gigatron, but they're nice to have.

• A modified version "gtsim" of the emulator "gtemu" can run programs and redirect their standard i/o to the emulator console. This is achieved by linking a special library that intercepts stdio routines and talks to the emulator with fake SYS functions. This is my main debugging tool.

• Using this emulator, it is even possible to run Marcel's simple chess program (MSCP).

• One can also produce gt1 files for the real gigatron, btw.

Here is MSCP at work:

Screenshot from 2021-07-22 19-27-09.png (53.04 KiB) Viewed 16787 times

[lb3361]

Compiling the horizon program from https://forum.gigatron.io/viewtopic.php?p=1070#p1070

I had to make some changes to the code such as replacing the color constants by their actual values, replacing videoTop_DEVROM by videoTop_v5, and importing the code for BusyWait() found in the library of the old compiler. I also had to change the type of the macro screenMemory in my own include file in order to match that of the old compiler. The final file can be seen at https://github.com/lb3361/gigatron-lcc/ ... /horizon.c. It compiles into a very compact gt1 file of 1.4KB.

Code: Select all

# ./build/glcc stuff/horizon.c -o horizon_devrom.gt1

If one insists on using ROMv4, then the file is 1.7KB.

Code: Select all

# ./build/glcc stuff/horizon.c -rom=v4 -o horizon_v4.gt1

horizon_v4.gt1

(1.77 KiB) Downloaded 851 times

horizon_devrom.gt1

(1.43 KiB) Downloaded 845 times

Here is a screenshot from at67's excellent emulator:

Screenshot from 2021-07-22 21-21-55.png (5.89 KiB) Viewed 16783 times

[lb3361]

Floating point.

Code: Select all

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

int main()
{
	char buffer[20];
	const char *s = "pi";
	double x = 3.141592653589793;
	double y;
	for(;;) {
		printf("\fGigatron floating point\n\n");
		printf("- %s=%.8g\n", s, x);
		y = sqrt(x);
		printf("- y=sqrt(%s)=%.8g\n", s, y);
		printf("- y*y=%.8g\n", y*y);
		printf("- log(%s)=%.8g\n", s, log(x));
		printf("- log(y)=%.8g\n", log(y));
		s = "x";
		printf("\nYour number? ");
		fgets(buffer, 20, stdin);
		x = atof(buffer);
	}
}

This is a program that suffers from the absurd complexity of the printf function. To make it fit on a gigatron 32k and ROMv5a I need to use the reduced console with frees about 10KB of video memory by sharing the scanlines that separate the character lines.

Code: Select all

$ ./build/glcc -map=conx -rom=v5a stuff/yofp.c -o yofp_v5a_32k.gt1

yofp_v5a_32k.gt1

(13.09 KiB) Downloaded 825 times

Screenshot from 2021-07-22 21-49-55.png (4.71 KiB) Viewed 16782 times

Alternatively I can the normal console on a 64KB gigatron. I can even compile for ROMv4 which results in substantially larger code (17KB instead of 13KB). The three new instructions added to ROMv5a (CALLI, CMPHI, CMPHS) make that much of a difference. This mostly comes from CALLI which is used for all subroutine calls and is also used to make long jumps between code segments. With ROMv4, each of these operations takes 10 bytes instead of 3.

Code: Select all

$ ./build/glcc -map=64k -rom=v4 stuff/yofp.c -o yofp_v4_64k.gt1

yofp_v4_64k.gt1

(16.94 KiB) Downloaded 843 times

Screenshot from 2021-07-22 21-58-12.png (6.63 KiB) Viewed 16782 times

No we cannot take the square root of 2.

Screenshot from 2021-07-22 21-58-29.png (3.03 KiB) Viewed 16782 times

[lb3361]

Here is an equivalent code that totally bypasses stdio and calls instead the low level console code.

Code: Select all

#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <gigatron/console.h>
#include <gigatron/libc.h>

char buffer[128], buf2[64];

void pr(const char *s1, const char *s2, const char *s3, double d)
{
	
	strcpy(buffer,s1);
	if (s2) strcat(buffer, s2);
	if (s3) strcat(buffer, s3);
	strcat(buffer, dtoa(d, buf2, 'g', 6));
	strcat(buffer, "\n");
	console_print(buffer, 128);
}

int main()
{
	const char *s = "pi";
	double x = 3.141592653589793;
	double y;
	
	for(;;) {
		console_print("\fGigatron floating point\n\n", 999);
		pr("- ", s, "=", x);
		y = sqrt(x);
		pr("- y=sqrt(", s, ")=", y);
		pr("- y*y=", 0, 0, y*y);
		pr("- log(", s, ")=", log(x));
		pr("- log(y)=", 0, 0, log(y));
		s = "x";
		console_print("\nYour number? ", 999);
		console_readline(buffer,128);
		x = atof(buffer);
	}
}

Compiling in the same way (without the reduced console)

Code: Select all

./build/glcc  -rom=v5a stuff/yofp2.c -o yofp2_v5a_32k.gt1

produces a file that is 9KB long (instead of 13KB). The major offender now is dtoa() which alone takes 1KB because it implements three floating point number styles (e, f, and g) with variable precision, correct rounding, and good behavior with very small or very large numbers. This is actually tricky to get right. I have learned a lot of things doing it.

yofp2_v5a_32k.gt1

(9.05 KiB) Downloaded 849 times

Mandatory screenshot:

Screenshot from 2021-07-22 22-41-46.png (9.4 KiB) Viewed 16779 times

[at67]

I decided to give it another try a few months ago. I studied the old compiler and stole the good ideas, such as having a combined assembler-linker written in python. I rewrote a very different code generator (with some novel ideas in fact) and I solved the register spilling problems. Then I started to write a C library with the idea of supporting as much of ANSI C as possible (to prevent the need for documentation) while keeping enough low-level stuff to write good Gigatron programs. Since this is an infinite task, and since what I have is definitely usable, I've decided to make a first release. See https://github.com/lb3361/gigatron-lcc. This works on Linux only for now.

Awesome stuff, congratulations!

• It has long integers and floating point.

• The library is missing a couple functions: fseek(), malloc() and some transcendental math functions such as sin(), cos(), ...

• I just finished printf() and scanf(). These functions are too heavy for the gigatron, but they're nice to have.

• A modified version "gtsim" of the emulator "gtemu" can run programs and redirect their standard i/o to the emulator console. This is achieved by linking a special library that provided stdio routines that talk to the emulator with fake SYS functions. This is my main debugging tool.

• Using this emulator, it is even possible to run Marcel's simple chess program (MSCP).

• One can also produce gt1 files for the real gigatron, btw.

Fantastic!

Floating point.

Very impressive, I initially considered doing a 16bit half float and in the end just opted for 8.8 fixed point, (so very easy to implement and good enough for driving pixels around in real time).

This is a program that suffers from the absurd complexity of the printf function. To make it fit on a gigatron 32k and ROMv5a I need to use the reduced console with frees about 10KB of video memory by sharing the scanlines that separate the character lines.

My largest runtime routine is the input command which sits at around 200Bytes long

No we cannot take the square root of 2.

That's an amazing amount of work to handle floating point exceptions, I assume they are not IEEE conformant

Compiling the horizon program from https://forum.gigatron.io/viewtopic.php?p=1070#p1070
It compiles into a very compact gt1 file of 1.4KB.
If one insists on using ROMv4, then the file is 1.7KB.

Once again amazing! The original lcc implementation was around 3.5KB for Marcel's Horizon demo.

Not to turn this into a competition, but my compiler does the following for Horizon, (no inline assembler):

Code: Select all

- ROMv3		756 Bytes
- ROMv5a	731 Bytes
- ROMvX0	610 Bytes, (runtime is 216Bytes, code is 394Bytes).

[lb3361]

About code sizes. There are several factors here. The first one is that C mandates a way to do things which does not fit the gigatron limitations. For instance, when the horizon.c program accesses the video memory "char screenMemory[256][]" it computes offsets with full 16 bits arithmetic instead of smartly using the fact that each scanline is in a separate page. Another example are loops which always use 16 bit ints when they could use an 8 bit index and fast increment instructions. And the biggest example is the handling of the stack which is assumed very large in C. The second factor are the limitations of the LCC compiler itself, which can be very smart or very crude in surprising ways. The third factor are the limitations of my own implementation. For instance I believe that adding a peephole optimization could save 10% in code size. I have to find a way to do this without making the code generator too complicated.

A C compiler will never compete with a dedicated solution in that respect. On the other hand, there is a lot of C code that can be ported with minimal work to contain the code size. In addition, properly documenting a dedicated solution is almost as big a work as developing it. Here, the main documentation is the 1989 Ansi C standard https://web.archive.org/web/20161223125 ... ansi.c.txt, and the deviations are easily understood after reading short comments like those in https://github.com/lb3361/gigatron-lcc/ ... n/gigatron.

In conclusion, the Basic compiler and the C compiler serve different niches. It would be nice to have more interoperability though, such as calling a C library from the Basic compiler or vice versa. One first step is the runtime. I took care to code the long and floating point support in a manner that is compatible with the usual vCPU programs (no funky stack, only use the 0x81-0x8f block of memory.) My assembly code format is a bit different but that can be solved with a little bit of python work.

About the floating point exceptions: I only catch overflows and domain errors. The code underflows silently.

[lb3361]

I was curious to see how small a gt1 file the C compiler can produce for Horizon. This is also a good way to show how one can use compiler and linker options to change fine settings or investigate further.

• The first obvious change is to inline the function BusyWait, which causes main to first become a leaf function (a function that does not call another function) and, because we can allocate all variables into registers, it becomes a frameless function.

• Then we can play linker games. The first one is to use option --no-runtime-bss-initialization because, well, there is nothing to initialize and therefore no need to import the bss clearing code. The second one is to move the program into the 0x200-0x6ff area instead of splitting it into the video memory holes. I can achieve this by defining an overlay file, "horizon.ovl", that changes the segment allocation table of the 32k map.

Code: Select all

# horizon.ovl
# ------------size----addr----step----end---- flags (1=nocode, 2=nodata)
segments = [ (0x0500, 0x0200, None,   None,   0),
             (0x0060, 0x08a0, 0x0100, 0x80a0, 0) ]

The compilation command is

Code: Select all

$ ./build/glcc -rom=at67x -map=32k,./horizon.ovl stuff/horizon.c -o horizon_at67x.gt1 -Wl-d --no-runtime-bss-initialization 

Compiling with option --rom=at67x to target at67's rom, -map=32k,./horizon.ovl to use the 32kb map with the above overlay, and -Wl-d to give a lot of information about the code placement. The resulting file is 941 bytes long (compared to at67's 756) and runs fast because of at67's native multiplication and division.

horizon_at67x.gt1

(941 Bytes) Downloaded 863 times

The ROMv5 equivalent is 1133 bytes long. The main difference is that it has to include the division code instead of using the native one.

horizon_v5a.gt1

(1.11 KiB) Downloaded 842 times

Now we can look at all the information that comes with option -Wl-d. When it says that code fragment 'main is 372+10 bytes long, that means 372 bytes if all jumps are short, and 10 additional bytes for long jumps (with your rom, that's just for BRA). Functions marked 'nohop' are assembly code functions that are required to fit in a single page.

Code: Select all

$ ./build/glcc -rom=at67x -map=32k,./horizon.ovl stuff/horizon.c -o horizon_at67x.gt1 -Wl-d --no-runtime-bss-initialization 
(glink debug) reading '/tmp/lcc2206852.o'
(glink debug) synthetizing module '_gt1exec.s' at address 0x200
(glink debug) reading '/home/quartus/gigatron/gigatron-lcc/build/cpu6/libc.a'
(glink debug) including module 'libc.a(_start.s)' for symbol '_start'
(glink debug) - code fragment '_start' is 63+0 bytes long
(glink debug) - code fragment '.callchain' is 37 bytes long (nohop)
(glink debug) including module 'stuff/horizon.c' for symbol 'main'
(glink debug) - code fragment 'main' is 372+10 bytes long
(glink debug) including module 'libc.a(_exitm)' for symbol '_exitm'
(glink debug) - code fragment '_exitm' is 33 bytes long (nohop)
(glink debug) including module '_gt1exec.s' for symbol '_gt1exec'
(glink debug) - code fragment '_gt1exec' is 36 bytes long (org:0x200)
(glink debug) including module 'libc.a(rt_mods.s)' for symbol '_@_mods'
(glink debug) - code fragment '_@_mods' is 19+0 bytes long
(glink debug) including module 'libc.a(rt_divs.s)' for symbol '_@_divs'
(glink debug) - code fragment '_@_divs' is 61+0 bytes long
(glink debug) including module 'libc.a(raise.s)' for symbol '_@_raise'
(glink debug) - code fragment 'raise' is 45 bytes long (nohop)
(glink debug) including module 'libc.a(_exits.c)' for symbol '_exits'
(glink debug) - code fragment '_exitmsg' is 51+4 bytes long
(glink debug) - code fragment '_exits' is 58+0 bytes long
(glink debug) including module 'libc.a(rt_save.s)' for symbol '_@_save_c0'
(glink debug) - code fragment '_@_save_ff' is 31 bytes long (nohop)
(glink debug) - code fragment '_@_rtrn_ff' is 37 bytes long (nohop)
(glink debug) pass 1
(glink debug) pass 2
(glink debug) pass 3
(glink debug) pass 4
(glink debug) assembling code fragment '_gt1exec' at 0x200 in Segment(0x200,0x300)
(glink debug) assembling code fragment 'main' at 0x224 in Segment(0x200,0x300)
(glink debug) - continuing code fragment 'main' at 0x300 in Segment(0x300,0x400)
(glink debug) assembling code fragment '_start' at 0x39d in Segment(0x300,0x400)
(glink debug) assembling code fragment '.callchain' at 0x400 in Segment(0x400,0x500)
(glink debug) assembling code fragment '_exitm' at 0x3dc in Segment(0x300,0x400)
(glink debug) assembling code fragment 'raise' at 0x425 in Segment(0x400,0x500)
(glink debug) assembling code fragment '_exitmsg' at 0x452 in Segment(0x400,0x500)
(glink debug) assembling code fragment '_exits' at 0x485 in Segment(0x400,0x500)
(glink debug) assembling code fragment '_@_save_ff' at 0x4bf in Segment(0x400,0x500)
(glink debug) assembling code fragment '_@_rtrn_ff' at 0x500 in Segment(0x500,0x600)
(glink debug) assembling code fragment '_@_divs' at 0x525 in Segment(0x500,0x600)
(glink debug) assembling code fragment '_@_mods' at 0x4de in Segment(0x400,0x500)
(glink debug) assembling DATA fragment '__glink_magic_init' at 0x4f1 in Segment(0x400,0x500)
(glink debug) assembling DATA fragment '__glink_magic_fini' at 0x4f4 in Segment(0x400,0x500)
(glink debug) assembling DATA fragment '_exitm_msgfunc' at 0x4f6 in Segment(0x400,0x500)
(glink debug) assembling DATA fragment '.13' at 0x562 in Segment(0x500,0x600)
(glink debug) assembling DATA fragment '.12' at 0x57b in Segment(0x500,0x600)
(glink debug) assembling DATA fragment '.9' at 0x593 in Segment(0x500,0x600)
(glink debug) assembling DATA fragment '.4' at 0x4f8 in Segment(0x400,0x500)

The function main --which is the only function here-- takes only 377 bytes long (from 0x224 to 0x39d) which is about the same as the size reported by at67. This swells to 425 bytes if we compile for rom v5a. So the main difference is the runtime which is substantially larger than that of at67's basic. Because the division code can raise a division-by-zero exception, the linker includes the function raise() and the corresponding exit messages (see https://github.com/lb3361/gigatron-lcc/ ... c/_exits.c). They are useless because, in the absence of console support, they're not going to be printed ever. This is a bit silly but it does not bother me as much as the real weight of functions like scanf() or printf()...

There is a convenient option to produce the assembly code annotated with source code.

Code: Select all

$ ./build/glcc -rom=at67x -S -Wf-g,##### stuff/horizon.c

I had to disguise the resulting file as a text file to upload it. If you read the file, you'll notice some opcodes prefixed by an underscore (e.g., _MUL, _BEQ, etc.) These are defined by the assembler/linker glink.py. For instance _BEQ can be a short or a long branch, _LDI can be LDI, LDWI, or LDNI, _MUL calls a runtime routine, etc.

horizon.s.txt

(3.79 KiB) Downloaded 845 times

[lb3361]

In the last few days, the library gained a working malloc.
At this point it implements all of ANSI C except cos/sin/tan and friends.

So I've decide to call it GLCC-RELEASE-1.0

Code: Select all

#include <gigatron/console.h>

void main()
{
   console_print("Hello world!\n\n", 999);
   console_print("GLCC release 1.0\n", 999);
}

hello.gt1

(2.67 KiB) Downloaded 841 times

[at67]

Once again, awesome!

[james7780]

Yes this is awesome. I tried installing LCC for Gigatron on my Windows PC a few weeks ago, but could not get it right.

Looking forward to a useable Gigatron LCC