What languages are better fit for generating efficient code for 8-bit CPU's than C?

Question

I found Why do C to Z80 compilers produce poor code? very interesting as it pointed out that C (which was leveraged to be an abstraction of a CPU for porting Unix) was not a very easy language to create efficient machine code from for the Z80. Apparently the same for 6502 where many dive directly in machine code. I read that the Sargon chess engine was very well suited for the 6502 due to the X and Y index registers.

I know that the Z80 and the 6502 are very different, but I was wondering if there are any languages on a higher level than assembly which can generate compact and efficient 8-bit machine code by design for either of them (or any other 8-bit CPU from that era), and how this was achieved?

Answer 1

One language that was popular on early 8-bit micros, including those that used the 6502 CPU, was Forth. Forth is exceptionally good for this use case, and superior to a C compiler, because Forth can make more efficient use of the 6502's hardware stack. Forth lacks any sophisticated methods of dealing with parameters. Everything is passed through the Forth stack and procedures just deal with the stack for both their input and output. This means the language doesn't require much from the CPU in terms of addressing modes or spend any time doing sophisticated effective address calculations.

Additionally, Forth provides a somewhat different paradigm than C in that it requires a program to be built up from very primitive and efficient units known as "Words" in Forth. By combining the primitive words into ever more complex combinations, the program is built up in a way similar to Functional Programming languages. This ensures Forth is very simple (and fast) to compile, even on 8-bit machines, and that the results execute very efficiently, given that the lowest level Words were coded to be efficient on the CPU.

According to some 6502 Forth users, the typical overhead incurred by Forth programs vs. similar functionality in Assembly is about 25%. And various Forth compilers for 6502 have been implemented in as little as 1.5 KiB. This fact makes Forth likely the only language compiler you will find running from an 8-bit computer ROM cartridge. So, it is both the low overhead of the compiler AND the efficiency of the resulting code that made it a favorite of early microcomputer programmers seeking something more "productive" than Assembly language.

Answer 2

C can be greatly improved as a language for the 6502 and Z80, as well as micros like the PIC and 8051, if one abandons the notion that implementations must provide for recursive subroutine calls, and adds qualifiers for things in zero page or pointers that are limited to accessing such things, and (for the Z80) adds qualifiers to identify objects that are known not to cross 256-byte boundaries.

Ironically, platforms like the PIC and 8051 which can't really support recursion at all and would thus seem unsuitable for C end up having better C compilers than those like the Z80 and 6502 which can barely support recursion, and thus generate code which is reentrant but inefficient instead of efficient non-reentrant code.

Answer 3

I know that the Z80 and the 6502 are very different, but I was wondering if there are any languages on a higher level than assembly which can generate compact and efficient 8-bit machine code by design, and how this was achieved?

Well, a prime candidate would be Ada.

It was a specific design goal for Ada to produce good code for tiny and 'odd' microprocessors (*1). Two basic approaches enabled this:

• the language itself was as non-assuming as possible, while at the same time
• offering tools to specify certain workings as detailed as possible - where needed -
• separating this to a great degree from generic code.

The high abstraction separates it from 'lower' languages like C or FORTH which are both built around certain assumptions about how a processor works and what functions it offers. In fact, C and Forth are great examples of two major pitfalls:

• Expecting a certain low-level behaviour of a CPU and
• ignoring high-level functions offered by a CPU

C for example is built on pointers and the assumption that everything has an address and is a series of bytes which can be iterated over (and may be structured further, but that can be ignored at will). CPUs with multiple address spaces or object storage or different understanding of data handling will inherently end up with less than desirable code.

The /370 is a great example here. While (register-based) pointers are an essential feature, the memory pointed to is handled as a block (or structure) with sub-blocks (fields) that can be manipulated with single instructions, not loops (*2). C-code forcing iteration onto a /370 can easy degrade (local) performance by a factor of 100 and more (*3).

Forth on the other hand is at its core built around the idea of a stack (or multiple stacks) and the ability for threaded code. Effective (stack) pointer handling and fast (and simple) moves to and from the stack are essential for performance. Both issues that 8-bit CPUs aren't inherently good at. The 6502 may have 128 pointers, but handling them is ugly. Indirect jumps, such as those needed for threaded code, are non-existent. Thus, fast implementations rely on self-modifying code. Then again, it is only marginally better on an 8080/Z80 as they have only one memory pointer (HL) and a backup (DE) which in turn is needed almost all the time.

Like C, Forth ignores higher-level function offerings, or has a hard time using them. Unlike C, it's a bit more open to changes in low-level behaviour.

Both languages are maybe higher than assemblers can operate on a more abstract level - if used carefully - but are not inherently abstract. They assume certain workings. If these are not basic machine instructions, performance will suffer.

A 'real' high-level language should not make such assumptions. Here, Pascal is a better candidate, as it assumes next to nothing. As a result, there are compilers for either line, 6502 and 8080/Z80, producing quite good code. I guess Turbo-Pascal for CP/M doesn't need any further introduction. On the 6502 side (Apple, Atari, Commodore) Kyan Pascal was considered a great way to work in high-level languages (*4).

Which brings us back to the original question, how to achieve good code performance on a wide range of machines:

• Don't expose any low-level working to the programmer.
• Have the compiler cover it.
• Have the programmer define the intended result, not the way it is achieved.

Essentially the goals set for Ada :)

---

P.S.:

... on a higher level than assembly ...

Serious? That statement feels quite offending :)

Assembly can and often is already on a higher level than some other languages. Assembly is the essential prototype of an extensible language. Everything can be done and nothing is impossible.

---

*1 - Note the 'produce' clause, having the compiler run on such machines is a different story.

*2 - It's always helpful to keep in mind that the /370 may have spearheaded many modern concepts, but it was designed with a punch card in mind. A punch card is a record, maybe pointed to by a register, holding information (fields) at fixed offset with fixed length. The whole instruction set for character (byte) manipulation is built to fit. No need to loop over two fields to move, compare, translate, pack or even search within, the most basic instructions (MVC, CLC, TR, PACK, TRT) already take care to handle fields at once.

*3 - This was a huge problem when C first became requested by users and implemented. By now compilers have evolved, and more importantly, CPU designers have added quite some 'changes' to cover up for the inefficiency of C.

*4 - Its only fault was its late 'birth' - too late to make a major impact.

Answer 4

"Forth" was the first name that jumped to my mind. Another is Action!, an Atari 8-bit-specific language. (Its manual can be found on the Internet Archive.)

Action! is a structured Algol-inspired language that borrowed constructs from other languages (in particular, it offered C-like pointers and arrays) and native types that mapped cleanly to the 6502's memory model. Techniques that usually required assembly were possible, such as positioning code/data and trapping interrupts. Action! kind of stood between a full-featured macro assembler and a high-level language like Pascal. (That it didn't have native floating-point support or recursion is a hint of how pared-down it really was. This page has a nice summary of its limitations.)

I couldn't find hard numbers showing it was more efficient or faster than the Atari C compilers of the time, but this article from Hi-Res magazine shows Action! finishing a Sieve benchmark in the approximate time of a Z-80 C program.

Action! also offered a surprisingly full-featured IDE before the acronym was coined: Integrated full-screen text editor, in-memory compilation (which made it quite fast), and a monitor for debugging. Action! showed me how good tools make a big difference in the edit-compile-debug loop.

Answer 5

Ada for cross compilation; though there WERE native Ada compilers (e.g. Janus Ada, with a Z80 (Ada-83) release here and reviewed in 1982 here) it was stretching the capabilities of a 64kbyte machine. Side note : the response to review was by Randy Brukardt; in 2020 he is still selling Janus Ada and actively contributing to the comp.lang.ada newsgroup!
So, Gnat (utilising gcc and soon LLVM) can run on any decent host, and optimise pretty well for small targets - nowadays, AVR or MSP430. Ada is in some ways easier to optimise than C.

But one other candidate worth mentioning for native compilation would be Modula-2. A much smaller simpler (and yes, more restricted) language, rather in the Pascal mode, but much more amenable to compile on a decent Z80 system. I had the FTL Modula-2 compiler running on a Z80 CP/M system.

I don't remember specific benchmarks on Z80, but on slightly larger 8086/8088 systems (where "small model" executables were 64K) the JPI Topspeed Modula-2 compiler of the 1980s was probably the most efficient compiler for 8086 of any language in the DOS era.

Answer 6

The main problem for high-level-languages on these platforms, and especially the 6502, is the small hardware stack. 256 bytes does not give one much room to work with for languages that intend to push large activation records on the stack.

As others have noted above, the solution is to remove recursion from your language definition, and in a more general sense, any "local" information.

Also worth mentioning, in the 1970s and early 80s when these machines were the bomb, the language all the cool people were working with were the many variations of ALGOL. Most mainframe systems had a "systems programming language" based to some degree on ALGOL layout, and Pascal once that became, effectively, the "new ALGOL". C did not become the universal solvent until the 16/32 bit machines had been in the market for some time.

So for instance, on the Atari you had Action!, an ALGOL-derived language with no recursion. This not only reduced the size of the stack use, but also greatly reduced the complexity of a proc call, you basically just did the branch. This later bit remains a topic of discussion to this day, as in Swift where Apple tries to convince you to use struct instead of class to reduce call overhead.

Raff mentioned Forth, which was designed as a multi-platform language that used its own stack structure to provide C-like capabilities on machines that lacked the requisite hardware support. While I guess it was a success in that respect, I recall trying to program in it and having feelings much the same as drinking way too much cheap gin.

Answer 7

Despite the other answers posted here, Forth generally performs significantly worse on the 6502 than an optimizing C cross-compiler like CC65. In tests I did comparing it to Tali Forth 2 for the 65C02 [1], which generates the fastest type of Forth code called STC, Forth code is sometimes on par with the C equivalent but more often 5-10 times slower. As far as I can tell, these are the main reasons:

1. All values pushed on the stack in Forth become 16 bit, which takes the 6502 a lot longer to manipulate than 8-bit values. C, on the other hand, has 8-bit types which are much faster to work with.

2. Forth words constantly adjust the data stack as they push and pop things, while C functions tend to do most of the stack allocation at the beginning and end of a function, which is much more efficient.

3. 6502 Forths don't generally do any optimization, even when enough information exists at compile time to do so. Something like "drop 5" in Forth will increase the stack pointer to do the drop then immediately decrease it to push the 5, so you get the useless series INX / INX / DEX / DEX. CC65 optimizes this type of inefficiency out in some but not all cases.

4. 6502 Forths also don't optimize for constants. CC65 outputs more efficient assembly for something like "foo<<3;" than "foo<<bar;" since the number of shifts is known at compile time. Forth generates the same code in both cases, always using the most compatible but slowest version.

5. Constraining the programmer to only modifying the top levels of the stack produces less efficient code. For example, you can't step over the first item on the stack and add something to the second. The equivalent "swap 5 + swap" wastes time on the two swap operations to get the value to the top of the stack and back into second place, while C can just directly modify any item on the stack.

CC65 is not perfect, but you're unlikely to get anything near as fast as that without writing the assembly yourself.

[1] http://calc6502.com/RobotGame/summary.html

Answer 8

For 8080, 8085 and Z80, possibly PL/M. That generated exactly what you told it. Also, it had special I/O instructions. With most other compilers, you had to call

output(0x20, 0x90)

but in PL/M it was built in

output(0x20) = 0x90

would generate the out instruction. There was a similar input instruction. The part of PL/M that always caught C programmers out was that even numbers were false and odd numbers were true. This gave rise to PL/M86 and PL/M286.

The use of Forth varies

1. as a compiled language
2. as a concept with a generic interpreter
3. as a concept using indirect threaded code (https://en.wikipedia.org/wiki/Threaded_code#Indirect_threading) with a home-brew interpreter
4. as a concept using knotted code (also known as token threads) with a home-brew interpreter.

I've seen 3 and 4 but not 1 or 2. Option 3 and 4 is normally used to reduce the code size but the program runs more slowly than if it were written in straight code. In the late 70s and early 80s, when information was obtained from journals, it wasn't easy to find a Forth compiler so most of the time it was a home brew version and everything was written in assembler.

Edit Token threads: Token Threads

I've looked through my old notes on Forth but I can't find the reference that describes the use of token threads in Forth so I'll describe it here. This is all about space saving on space limited machines.

Direct threading: In normal assembler, we have something like

main:  call func1
       call func2
       call func1
       call func3
       call func1
       call func2
       call func3
8/16-bits: 21 bytes
32-bits: 35 bytes

Just adding 32-bit for completeness. This does not apply to Z80s.

Indirect Threading: For a 16 bit machine, there are 3 bytes for every call. For a 32-bit machine, there are 5 bytes for every call. In most Forth implementations, there is a small piece of code (the exec) that reads the address and executes, a bit like an indirect function call in C/Fortran. This saves 1 byte per call, which is significant if the saving exceeds the size of the exec code

main: word func1
      word func2
      word func1
      word func3
      word func1
      word func2
      word func3
8/16-bits: 14 bytes
32-bits: 28 bytes

Token threading: If there is a large number of these, and there aren't more than 256 functions, it is possible to save more space by using a lookup table

lut:  word func1
      word func2
      word func3
main: byte 1
      byte 2
      byte 1
      byte 3
      byte 1
      byte 2
      byte 3
8/16-bits: 13 bytes
32-bits: 19 bytes

This is a further "saving" of 1 byte for every word in 16-bits and 3 bytes for every word in 32-bits: that is provided the "saving" exceeds the size of the exec.

One byte may not seem significant but in a tightly packed PROM, sometimes it makes the difference between having an 8K ROM or redesigning to accommodate a 16K ROM.

Answer 9

I suggest PLASMA (https://github.com/dschmenk/PLASMA), a C-like language that compiles to interpreted code. It has a much higher code-density than assembly language, and it's much faster than FORTH.

Answer 10

It only has to do with the effort put into the code generator back-end. C is an abstract language, it doesn't need to directly reflect what the machine is doing. But this is the sort of stuff that would be state-of-the-art in 2020, and would require significant investment. There's nothing inherently special about Z80 of 6502 in this respect - only that the impedance mismatch between some platforms and the code generator back-ends is very high. For Z80 and 6502 it wouldn't matter what the language is, because the specifics of the language are far away and dissolved by the time the intermediate representation gets to the optimizer and code generator. Any high-level compiled language would be just as bad on Z80 and 6502 as C is, pretty much.

We're spoiled with excellent modern compiler back-ends. The trouble is that they are commonplace that everyone thinks it's "easy" work. Not at all. They represent man-decades of effort if someone were just to reproduce them.

So, you can get excellent Z80 and 6502 code out of a C compiler if you hire a couple LLVM back-end experts out from Apple and Google, pay them the going rate, and let them at it for a couple of years. A couple million dollars is all it'd take, and you'd grace the world with absolutely amazing Z80 and 6502 code produced from both C and C++.

So: I'm sure the results would be excellent- but it requires lots of effort. It's the sort of effort that historically has not been expended by even major silicon vendors, with exception of Intel, Digital and IBM. Zilog's own compilers (all of them, doesn't matter what year was the release) are junk when you compare what they manage to cough up to x86 or ARM output from C code passed through Clang and LLVM, and all the man effort put up by, say, Zilog and Motorola compiler teams throughout the 70s, 80s and 90s, all together in total, was completely eclipsed by the man-hours that went into, say, Clang+LLVM in the first decade of the existence of both projects. Zilog's and Motorola's marketshare back when they still had plenty of it absolutely didn't improve matters here: they were a bit too early and the everyday techniques used by e.g. LLVM weren't available and/or they required so much memory and CPU cycles to run that it wasn't feasible to offer such products to wider audience, because you pretty much needed a heavy minicomputer or a top-notch workstation to do this sort of work.

Answer 11

I know that the Z80 and the 6502 are very different, but I was wondering if there are >any languages on a higher level than assembly which can generate compact and efficient >8-bit machine code by design for either of them (or any other 8-bit CPU from that era), >and how this was achieved?

I've been working on my own high-level language "Higgs" which targets 6502,65C02,68000,68040, RISC DSP and recently started working on Z80 backend.

The output (build script called from within Notepad++) is an assembler file that is then fed into the local assembler/linker of the respective platform.

The feature list of the language depends directly on the target platform's abilities. Each HW target has different set of unique features, dictated by the addressing modes / asm capabilities of the platform. Arrays on 6502 are very different than arrays on 68000 or DSP RISC.

Each target however supports global/local/register variables, global/local constants, structures, arrays, functions (with optional parameters), loops, conditions, nested blocks (helps with formatting and namespace pollution), 3-parameter math expressions, signed math (if present), increment/decrement (var++, var--).

My basic rule is that I never include a new feature unless I can guarantee that the code generated by my compiler is identical to the code I would write manually, directly in ASM.

From experience of writing my own game in it (~25,000 lines of Higgs so far), it's exponentially faster to write/debug/test new code compared to ASM. Less than 0.01% of code is still written in ASM, the rest is Higgs.

I will be adding Z80/Next backend soon.

If you could only have 3 features that would increase your productivity, this is what gives you most return:

1. conditions
2. math expressions
3. scope-based variables/constants {}

Here's an example (68000 target: hence d0-d7/a0-a7 registers, .b, .w, .l sizing, etc.), showing how high-level it is (compared to ASM) and that it really feels almost like C, and is thus very easy to come back to, after 6 months, and quickly understand and adjust the code (unlike hand-written ASM that mostly evokes deep WTF feelings):

Render_LaserShots:
{
    local long lpMain
{   ; Player LS
    colorQuad = #$FFA080
    SLaserShot.InitRegister (LaserShots)
    loop (lpMain = #MaxLaserShots)
    {
        if.l (SLaserShot.IsActive == #1)
        {
            d1 = #0 - SLaserShot.X
            d2 = SLaserShot.camY
            d3 = #0 - SLaserShot.camZ
            SetCamPos32 (d1,d2,d3)
            Render_obj3DList_Object (LaserShotMeshPtr,#PolyCount_LaserShot)
        }
        SLaserShot.Next ()
    }
}
{   ; ShootingEnemy  LS
    SEnemy.InitRegister (MainEnemy)
    if.l (SEnemy.State == #AI_STRAFE)
    {   ; Only Render Enemy's LS if he is active
        colorQuad = #$40FF40
        SLaserShot.InitRegister (EnemyLaserShots)
        loop (lpMain = #MaxLaserShots)
        {
            if.l (SLaserShot.IsActive == #1)
            {
                d1 = #0 - SLaserShot.X
                d2 = SLaserShot.camY
                d3 = #0 - SLaserShot.camZ
            ;   print3 (d1,d2,d3,#50,#20)
                SetCamPos32 (d1,d2,d3)
                Render_obj3DList_Object (LaserShotMeshPtr, #PolyCount_LaserShot)
            }
            SLaserShot.Next ()
        }
    }
}

rts
}

Answer 12

This is my experience with C on Z80 and 6502:

• Zilog Z80/z88dk

  The code generated is pretty decent, not as good as handwritten assembly but good enough for lots of purposes. One advantage on Z80 in relation to C is the existence of IX/IY registers that are used for local variable access / parameter passing. Of course they aren't as efficient as register parameters but it still works good with C paradigm. I tested switching to static variables and found there was a difference, but small.

• 6502/cc65

  I'm not familiar with 6502 assembly too much but aware of general architecture. Whether I compiled the code with or without static variables for 6502 the impact was very big (IIRC up to 50%). I can't compare with handwritten code since I have no experience.

Bottom line: there is a big difference in processor architecture. Zilog Z80 is much more C friendly, it has decent stack, index registers that allow quite straightforward implementation of many C paradigms, calling conventions, etc. While 6502 is much more limited in implementing re-enterable code or using stack-based variables.

Answer 13

The assumption in the question is incorrect. The common wisdom about C being a bad choice for the 6502, is wrong.

The choice of source language, does not gate the quality of generated code for the 6502.

In fact, code quality on the 6502 (or any other platform for that matter) is gated by the quality of lowering intermediate-representation code to MOS instructions.

Any 6502 codegen must take into account the 6502's architecture quirks: there are few real registers, but there's also a bunch of zero page memory.

High-quality C codegen on the 6502 is possible, but it's not quick to implement. It cannot be done with a toy or a hobbyist compiler, in particular.

See https://www.llvm-mos.org for an example of the foregoing.