A new well-known compiler

Since we do not have native C compilers on the Oric, this forum will be mostly be used by people using CC65 or the OSDK. But any general C related post will be welcome !
User avatar
iss
Wing Commander
Posts: 1637
Joined: Sat Apr 03, 2010 5:43 pm
Location: Bulgaria
Contact:

Re: A new well-known compiler

Post by iss »

Thanks Dbug for the nice (short and meaningful!) list. I'll definitely use it and report back.
Here is one 'real-life' example - aes256 algo :).
aes256-sources.zip
aes256 source files
(5.57 KiB) Downloaded 596 times
Looking in sources:

Code: Select all

file aes256.c @line 25:
#define BACK_TO_TABLES
If it's uncommented the algo obviously uses tables for calculations and the speed is high:
CC65: 1.72 sec, 9503 bytes
aes256-tab-cc65.tap
aes256 using tables CC65
(9.28 KiB) Downloaded 612 times
OSDK: 1.70 sec, 13350 bytes
aes256-tab-osdk.tap
aes256 using tables OSDK
(13.04 KiB) Downloaded 653 times
If the above line is commented (i.e. not using tables)
CC65: 23.63 sec, 9302 bytes
aes256-tab-cc65.tap
aes256 using tables CC65
(9.28 KiB) Downloaded 612 times
OSDK: ??.?? sec, 14385 bytes
aes256-tab-osdk.tap
aes256 using tables OSDK
(13.04 KiB) Downloaded 653 times
Unfortunately the encryption fails and the back decryption never ends...
Count this as 'OSDK bug report' :).
User avatar
iss
Wing Commander
Posts: 1637
Joined: Sat Apr 03, 2010 5:43 pm
Location: Bulgaria
Contact:

Re: A new well-known compiler

Post by iss »

Continued ...
TXT - plain text
KEY - encryption key
ENC - encrypted message
TST - test - how the encrypted message should look like
DEC - decrypted plain text (i.e = TXT)
Here is what to expect as proper result:
snapshot.jpg
snapshot.jpg (18.03 KiB) Viewed 21272 times
User avatar
Dbug
Site Admin
Posts: 4437
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

Re: A new well-known compiler

Post by Dbug »

You wrote CC65, so I guess you are not testing the gcc 6502?
Do you think you could get CC65 to output an assembler source code and attach it as well to your post?

This 9 KB vs 14 KB size different is indeed interesting, looks like CC65 has improved since when we were checking with Jede (more than 10 years ago).
Godzil
Squad Leader
Posts: 774
Joined: Sat May 21, 2011 7:21 pm
Location: Between UK and France
Contact:

Re: A new well-known compiler

Post by Godzil »

You also didn't tell that gcc wasn't designed for anything that have less than 32bit... There isn't any official 16bit cpu backend..

I cant expect it to make correct code for an 8bit cpu without lots and lots of changes inside and until it's official expect that it can disappear in a second
User avatar
iss
Wing Commander
Posts: 1637
Joined: Sat Apr 03, 2010 5:43 pm
Location: Bulgaria
Contact:

Re: A new well-known compiler

Post by iss »

@Godzil: Good points. I agree with you.

@Dbug: Yes, currently I have OSDK and CC65 working side-by-side. I'm using common Makefile per project, so it's easy to compile everything with both toolchains. And yes, CC65 seams to be actively developped (unfortunately most changes are related to Commodore).
I hope to have GCC as an option soon too, but for now I succeeded only in building the compiler. My checks with dejagnu regression tests are far from the announced on the maintainer's site. I'm waiting his feedback.
Attached is aes256 demo compiled with CC65 with preprocessed files (look for *.c1 files :))
aes256-src+asm.zip
(79.02 KiB) Downloaded 628 times
User avatar
NekoNoNiaow
Flight Lieutenant
Posts: 272
Joined: Sun Jan 15, 2006 10:08 pm
Location: Montreal, Canadia

Re: A new well-known compiler

Post by NekoNoNiaow »

Allow me to resurrect this very interesting thread/topic. ;)

I have been working on optimizing a demo effect written in C these past weeks/months (a few hours at a time) and I have reached a point where further optimizations of the C code do not produce the expected result.
=> The generated code ends up being slower or the same when it should definitely be faster (even accounting for the limited register set of the CPU).

Looking at the assembler output it is clear that the quality of the produced machine code is responsible for the algorithm optimizations not translating into actual results:
  • the code shuffles data back and forth between zero-page-simulated-registers and memory, it looks like it spends more time doing that than actual useful work. ;)
  • the Y register is only used as an index, never as a temporary storage to avoid a Load/Store
  • the X register is used only once in a blue moon and only when the wind blows to the South :D
  • many successive operations are redundant and unnecessary (ex: LDA tmp0; STA tmp0 -> \(ToT)/ )
  • as a consequence of the above the code is much larger than it needs to be
This leads me to think that the topic of switching compilers or enhancing the current one would be worth discussing again. ;)

I see several avenues:
  • Enhancing the current compiler. To some extent that can be done very cheaply by implementing a simple peephole optimizer, these are usually very simple to implement and there are multiple open source implementations to start from (ex: http://aminet.net/package/dev/asm/popt an m68k peephole optimizer written by a friend of mine when I was in College).
  • Offering multiple compiler choice for the OSDK (after all, the current compiler works so there is no need to remove it) by allowing to work with ISS's version of CC65 (or whichever other one that works). (And http://www.6502.org/tools/asm/ lists a lot of possible alternatives, many likely are not maintained anymore though I suppose.)
@ISS, did your attempts to work with CC65 lead you to a result that can be integrated to the OSDK?

Update: Obviously my memory is failing me because there is already a peephole optimizer available (cf viewtopic.php?t=1805#p17427) but it is currently disabled because it is not 100% reliable.
I am updating to the latest OSDK (1.13) and will give a go at fixing it.
User avatar
Chema
Game master
Posts: 3013
Joined: Tue Jan 17, 2006 10:55 am
Location: Gijón, SPAIN
Contact:

Re: A new well-known compiler

Post by Chema »

That would be great indeed!

However, if I remember correctly, the compiler generates fat code mainly because the backend is designed for 16-bit systems (I mean, it is using the standard 16-bit integer size), so it does not optimize things such as small numbers (8-bit), counters and loops. Besides, as the 6502 only has one stack, the C stack frame has to be simulated and passing parameters to functions is also quite slow.

The backend also generates macros which are then substituted using the preprocessor with asm code, with no further optimization, thus the crappy code.

I really think that you need, either some kind of specifically C version for 8-bit processors (with 8-bit integers, for instance, and 16-bit for long integers) and a good compiler, or a totally different language, aimed to generate optimized asm code.

The best thing is, of course, use asm directly for key routines, as Dbug many times suggested. The 6502 asm is quite easy and straightforward when compared to others (68000, 6809 or z80).
User avatar
NekoNoNiaow
Flight Lieutenant
Posts: 272
Joined: Sun Jan 15, 2006 10:08 pm
Location: Montreal, Canadia

Re: A new well-known compiler

Post by NekoNoNiaow »

Chema wrote: Mon Dec 17, 2018 6:18 pm [snip]

I really think that you need, either some kind of specifically C version for 8-bit processors (with 8-bit integers, for instance, and 16-bit for long integers) and a good compiler, or a totally different language, aimed to generate optimized asm code.
Clearly. That is why I hoped ISS would chime in since he apparently has used CC65 a few times on the Oric (if I read his posts correctly) but alas he has not yet. ;)
Chema wrote: Mon Dec 17, 2018 6:18 pm The best thing is, of course, use asm directly for key routines, as Dbug many times suggested. The 6502 asm is quite easy and straightforward when compared to others (68000, 6809 or z80).
I will eventually convert the C code to assembly language but I first want to improve the algorithm's logic. Moving to assembly too early would make it significantly harder to test algorithmic changes.
User avatar
iss
Wing Commander
Posts: 1637
Joined: Sat Apr 03, 2010 5:43 pm
Location: Bulgaria
Contact:

Re: A new well-known compiler

Post by iss »

NekoNoNiaow wrote: Tue Nov 27, 2018 2:26 am@ISS, did your attempts to work with CC65 lead you to a result that can be integrated to the OSDK?
Sorry, I missed your message.
What I did is: I've created Makefiles with the same build rules for CC65 and for OSDK's compiler, so I can easy include them in a local Makefile (call it 'Project makefile', which contains the names of source files and some per project parameters) and compile with both compilers. I made this mainly to be able to use the OSDK tools ('header', 'tap2dsk' etc.) with CC65 compiler or let say so - to have the best from both toolchains in one place. :)
Maybe I don't fully understand your question but what's the point to integrate CC65 to OSDK?
User avatar
NekoNoNiaow
Flight Lieutenant
Posts: 272
Joined: Sun Jan 15, 2006 10:08 pm
Location: Montreal, Canadia

Re: A new well-known compiler

Post by NekoNoNiaow »

iss wrote: Tue Jan 15, 2019 10:52 am What I did is: I've created Makefiles with the same build rules for CC65 and for OSDK's compiler, so I can easy include them in a local Makefile (call it 'Project makefile', which contains the names of source files and some per project parameters) and compile with both compilers. I made this mainly to be able to use the OSDK tools ('header', 'tap2dsk' etc.) with CC65 compiler or let say so - to have the best from both toolchains in one place. :)
Thanks for these details!
iss wrote: Tue Jan 15, 2019 10:52 am Maybe I don't fully understand your question but what's the point to integrate CC65 to OSDK?
Lcc produces really crappy code so I am looking for a better alternative (cc65, fixing lcc's peephole optimizer, love-6502, etc.) which would still work as is with the OSDK whike leaving everyone the freedom to choose their compiler of choice.
User avatar
NekoNoNiaow
Flight Lieutenant
Posts: 272
Joined: Sun Jan 15, 2006 10:08 pm
Location: Montreal, Canadia

Re: A new well-known compiler

Post by NekoNoNiaow »

iss wrote: Tue Jan 15, 2019 10:52 am What I did is: I've created Makefiles with the same build rules for CC65 and for OSDK's compiler, so I can easy include them in a local Makefile (call it 'Project makefile', which contains the names of source files and some per project parameters) and compile with both compilers. I made this mainly to be able to use the OSDK tools ('header', 'tap2dsk' etc.) with CC65 compiler or let say so - to have the best from both toolchains in one place. :)
Do you have these changes publicly available somewhere? I plan to do the same but if I could avoid reinventing the wheel that would save me some time. ;)

Btw, when you mention makefiles, are they any different from the ones Jylam wrote for the Linux version of the OSDK?
Cf https://github.com/nekoniaow/OSDK/commi ... 7dd9e87f23 for the commit where he created the Linux makefiles. (Sorry for the GitHub link, I wanted to post an SVN one but I could not find it on the defence-force site.)
User avatar
iss
Wing Commander
Posts: 1637
Joined: Sat Apr 03, 2010 5:43 pm
Location: Bulgaria
Contact:

Re: A new well-known compiler

Post by iss »

NekoNoNiaow wrote: Tue Feb 05, 2019 1:19 am Do you have these changes publicly available somewhere?
...
Btw, when you mention makefiles, are they any different from the ones Jylam wrote for the Linux version of the OSDK?
@NekoNoNiaow: Well, we talking about two different Makefiles.
1. Makefiles to compile the OSDK sources from DF SVN repository to native executable for Linux.
I'm using the Jylam's Makefiles found in OSDK sub-directories (they are good), but I've created my version of the 'rules.mak' to suit some my special needs, to allow me easy to patch some sources and to add more tools to the toolchain which I want.
2. Makefiles to compile Oric binaries (i.e. TAP and DSK) from sources using the above native Linux compiled OSDK.
These are actually the rules how to call the assembler, compiler, linker... i.e. the same what the BAT-files do but using make's syntax. That's it.

Long time ago I made both public available but because of no interest I removed them. Now I checkout DF SVN from time-to-time and if there are updates I compile the toolchain (the same I do with CC65). I'm happy with that solution - I know every detail and can easy to do fixes and patches when needed, but I really doubt that I'll put it back public - simply I don't have the time to maintain, support, explain and document it for more than one user ;).
User avatar
Chema
Game master
Posts: 3013
Joined: Tue Jan 17, 2006 10:55 am
Location: Gijón, SPAIN
Contact:

Re: A new well-known compiler

Post by Chema »

Let's face it, guys... a C compiler will never generate good code for a 6502 architecture. Simply C is not designed for so limited 8-bit processors.
1/ lack of 16 bit registers and operations (arithmetical operations suffer, pointer management...). Remember the base type in C is 16-bit (int) and everything is implicitly casted to int in many occasions.
2/ lack of a real stack. Having it tied to page 1, 256 bytes-only and no user stack... this means creating a "custom" C stack and managing it. C makes extensive use of this stack, so there is a problem. But even if the use of the processor stack were possible, only P and A can be pushed to the stack, leaving really the only available general-purpose register A (the only available to perform arithmetic operations and, remember, 8-bit only) as the option to store things on the stack.

There are possibly other things that make things complicated, but you get the idea. A compiler may generate code which is less stupid than another with more aggressive optimizations and clever tricks, but nothing that would generate a really much faster code, in my opinion. And for the size, you can make it small filling everything with subroutines, but that will make everything much slower!

A specific mini-C with 8-bit integers as default type, with lots of restrictions may do. That is, another completely different language.
User avatar
NekoNoNiaow
Flight Lieutenant
Posts: 272
Joined: Sun Jan 15, 2006 10:08 pm
Location: Montreal, Canadia

Re: A new well-known compiler

Post by NekoNoNiaow »

iss wrote: Tue Feb 05, 2019 11:27 am @NekoNoNiaow: Well, we talking about two different Makefiles.
1. Makefiles to compile the OSDK sources from DF SVN repository to native executable for Linux.
I'm using the Jylam's Makefiles found in OSDK sub-directories (they are good), but I've created my version of the 'rules.mak' to suit some my special needs, to allow me easy to patch some sources and to add more tools to the toolchain which I want.
2. Makefiles to compile Oric binaries (i.e. TAP and DSK) from sources using the above native Linux compiled OSDK.
These are actually the rules how to call the assembler, compiler, linker... i.e. the same what the BAT-files do but using make's syntax. That's it.
Okies, these seem indeed specific to your needs. I thought that they were related to including c65 as part of the OSDK.
iss wrote: Tue Feb 05, 2019 11:27 am Long time ago I made both public available but because of no interest I removed them. Now I checkout DF SVN from time-to-time and if there are updates I compile the toolchain (the same I do with CC65). I'm happy with that solution - I know every detail and can easy to do fixes and patches when needed, but I really doubt that I'll put it back public - simply I don't have the time to maintain, support, explain and document it for more than one user ;).
Reading the post you linked, it seems like DBug was awaiting for you to bring your changes back into SVN. The discussion seems to have been left at that stage.

This said, there are no reasons why you could not bring your changes back into the OSDK even now.
We can merge them progressively and fix any incompatibilities one after the other in a separate branch until everything can be smoothly merged into main/master/whatever-the-name-is.

Having your sources on a public repository of some kind would certainly help. Is there one available?

In any case, I think you should not abandon the idea of bringing back your changes to the community. If they are helpful to you, they should be helpful to many of us too, maybe not most, but at least this would avoid duplicate effort (and time/effort is precious in our community ;)! ).
Chema wrote: Tue Feb 05, 2019 2:59 pm Let's face it, guys... a C compiler will never generate good code for a 6502 architecture. Simply C is not designed for so limited 8-bit processors.
I disagree and for many reasons, but first of all I want to state that I am not looking for the perfect optimizing C compiler for the Oric, just one that is moderately good and allows me to test algorithms before I convert them to ASM.
Currently, lcc65 (without peephole optimizations) is just too bad for that purpose hence my search for a better one. ;)

It should also be noted that I am currently working on making opt65 (the peephole optimizer of lcc65) work again so it can be used on the OSDK to produce better code than it does now. When I will be done, we will have a better C compiler even if it is not perfect.

Now on to the low level details... ;)
Chema wrote: Tue Feb 05, 2019 2:59 pm 1/ lack of 16 bit registers and operations (arithmetical operations suffer, pointer management...). Remember the base type in C is 16-bit (int) and everything is implicitly casted to int in many occasions.
C does supports 8 bit data types without issue (char and unsigned char).
Modern compilers are actually *really* good at register usage optimization even with very few registers since they use robust and well tested resource allocation algorithms. GCC and LLVM should have no issues juggling with the 6502 register set.
Chema wrote: Tue Feb 05, 2019 2:59 pm 2/ lack of a real stack. Having it tied to page 1, 256 bytes-only and no user stack... this means creating a "custom" C stack and managing it. C makes extensive use of this stack, so there is a problem. But even if the use of the processor stack were possible, only P and A can be pushed to the stack, leaving really the only available general-purpose register A (the only available to perform arithmetic operations and, remember, 8-bit only) as the option to store things on the stack.
C uses only as much stack as the programmer tells it to. And that is a secondary problem for my purpose since I am testing algorithms inner loops, not deeply recursive functions. So I am fine even if a software stack is slow. ;)
GCC and LLVM can be taught to use the stack only for storing return addresses anyway and to use other methods for register passing and/or temporary variables. (That is what cc65 does by the way.)
Chema wrote: Tue Feb 05, 2019 2:59 pm There are possibly other things that make things complicated, but you get the idea. A compiler may generate code which is less stupid than another with more aggressive optimizations and clever tricks, but nothing that would generate a really much faster code, in my opinion. And for the size, you can make it small filling everything with subroutines, but that will make everything much slower!
Once again, I am not looking for a compiler which can fully replace assembly language code, I even specified that many times. ;)
I just want to test algorithms at a higher level than assembly and not have to deal with register allocation.

Even if the compiler reaches only half of the speed of a human it does not matter for me since that is good enough to evaluate the sanity of my algorithm before I switch to assembly. Even between humans coding in assembly, a difference of half speed is very easy to reach so that would be already good. Hell, even one quarter or one height speed would be fine.

This said, figures speak louder than speculations: a brave soul has actually adapted GCC for the 6502 for use with 8-bit Atari machines.
https://atariage.com/forums/topic/27614 ... 2-vs-cc65/

To illustrate the gains obtained by using an industrial grade compiler here is how it performs on the classic computation of prime numbers using the classic Sieve of Eratosthenes compared to cc65:

cc65: 301 ticks (6.02s)
gcc: 97 ticks (1.94s)

-> three times faster. Not bad heh? ;)
Executables are larger but in some cases that might be worth it. (and in my case to test just a single function, that is definitely worth it).
User avatar
Chema
Game master
Posts: 3013
Joined: Tue Jan 17, 2006 10:55 am
Location: Gijón, SPAIN
Contact:

Re: A new well-known compiler

Post by Chema »

I did not want to start a debate, really. I find them fun and an opportunity to learn a lot (and I am always curious and willing to learn from others). I understand that you want a decent C compiler so you can test things, maybe mix with asm... It is perfectly OK and I understand that. lcc65 is crappy and the generated code is horrible. So finding another compiler, with better performance would be nice indeed.

That being said...
NekoNoNiaow wrote: Tue Feb 12, 2019 1:09 am Now on to the low level details... ;)
Chema wrote: Tue Feb 05, 2019 2:59 pm 1/ lack of 16 bit registers and operations (arithmetical operations suffer, pointer management...). Remember the base type in C is 16-bit (int) and everything is implicitly casted to int in many occasions.
C does supports 8 bit data types without issue (char and unsigned char).
Modern compilers are actually *really* good at register usage optimization even with very few registers since they use robust and well tested resource allocation algorithms. GCC and LLVM should have no issues juggling with the 6502 register set.
Yeah, I know. But nasty things start happening with automatic int promotions, such as:

Code: Select all

    unsigned char a=200, b=200,c;
    
    c=(a+b)/2;
should result in c equal 200, as a and b are automatically promoted to int before proceeding with the operation.

Indexing also produces sub-optimal results. You can manage arrays quite quickly on the 6502 if they are less than 256 bytes long. But the C compiler does not know about this and uses 16-bit arithmetic. You probably won't have string functions using Y indexing which only work for strings < 256 chars...

And the register usage... well if only we had a few general-purpose registers... but there is only A, then the indexes, which can be used partially for some operations. You can use page zero, of course, which is what most compilers do, but beware that some (namely cc65) uses almost all the zero page for its needs (or that I read).
Chema wrote: Tue Feb 05, 2019 2:59 pm 2/ lack of a real stack. Having it tied to page 1, 256 bytes-only and no user stack... this means creating a "custom" C stack and managing it. C makes extensive use of this stack, so there is a problem. But even if the use of the processor stack were possible, only P and A can be pushed to the stack, leaving really the only available general-purpose register A (the only available to perform arithmetic operations and, remember, 8-bit only) as the option to store things on the stack.
C uses only as much stack as the programmer tells it to. And that is a secondary problem for my purpose since I am testing algorithms inner loops, not deeply recursive functions. So I am fine even if a software stack is slow. ;)
GCC and LLVM can be taught to use the stack only for storing return addresses anyway and to use other methods for register passing and/or temporary variables. (That is what cc65 does by the way.)

Of course, you can avoid parameters and function calls to make the use of the software stack minimal. I wanted to state that, as the 6502 does not have a proper user stack or a way to access it including offsets, and besides, it is so small and restricted in usage, it makes the use of stack frames slow.

You have a good example of how cc65 generates poor code here: https://www.xtof.info/blog/?p=714

In any case, it was my fault jumping with my personal rants :wink: into your thread, because, as you said, you have clearly stated your idea many times, and my post was along another different path, and (frankly) completely unhelpful. I am really sorry for that. As I said it was just my discussion-eager me :mrgreen:

I sincerely apologize.
This said, figures speak louder than speculations: a brave soul has actually adapted GCC for the 6502 for use with 8-bit Atari machines.
https://atariage.com/forums/topic/27614 ... 2-vs-cc65/

To illustrate the gains obtained by using an industrial grade compiler here is how it performs on the classic computation of prime numbers using the classic Sieve of Eratosthenes compared to cc65:

cc65: 301 ticks (6.02s)
gcc: 97 ticks (1.94s)

-> three times faster. Not bad heh? ;)
Executables are larger but in some cases that might be worth it. (and in my case to test just a single function, that is definitely worth it).
And that is indeed impressive! I know Fabrice Frances once took a look at the 65C02 target for gcc, but never adapted it for 6502... http://oric.free.fr/software.html
Post Reply