lynn / chibicc Goto Github PK

The repo root is getting a bit cluttered.

This old version of chibicc only has signed integers, whereas apparently the chibicc comparison opcodes (GTH, LTH) are always unsigned. We don't correct for this right now, so this means <, <=, > and >= are probably wrong when one or the other operand is signed. Considering how two's-complement works, addition, subtraction and multiplication don't have a signed/unsigned distinction, but division does, so that's also probably wrong rn.

A related thing that's not really a bug, but is annoying, is you can't use hex for two's-complement bit patterns:

ffff.c:3:     return 0xffff;
           ^ integer literal is too large for type int (16-bit)

We could change to only having unsigned integers in C, but I think it shouldn't be too hard to support both unsigned and signed with some assembly tricks.

Changing this breaks stuff though 🤔

Hello :)

I have a couple more ideas for optimizations.

• I see in the generated code a few instances of #00 ORA, which could be removed.
• Static arithmetic in oneko, like ;theCursor_ #0004 ADD2, which could be merged into a LIT2.
• Another static arithmetic operation is #0100 SWP, this could be #0001.
• In the atoi implementation, you'll find DUP2 #0000 EQU2, which could be turned into ORAk #00 EQU
• #0000 SWP, to #0000

Right now something like

#include <uxn.h>

void main(void) {
  int n = asm("#1234");
}

compiles to

|0100
  LIT2r 0000 main_ POP2r BRK
( bss )
( data )
@L.data.0_
  "#1234    ( <---- oops 😅 )
( text )

@main_ ( -- result* )
    OVR2r LIT2r 0002 SUB2r #1234 STH2kr STA2
    #0000

  &return
    POP2r JMP2r

The expected behavior is not to emit @L.data.0_ "#1234.

If you do make test and disable the code in tests that makes failed assertions crash, uxnemu eventually complains you've gotten a working-stack overflow. I've also seen this in one of my own programs that has animation with the screen vector. So I assume there's some push/pop mismatch, a stack leak of sorts.

Hi,

First off, following the changes to chibicc is exhilarating! Amazing work you two.

The following suggestion is taking advantage of not using Harvard Achitecture, I was wondering if maybe instead of storing all the variables after the main() jump, it would be possible to store the variables locally. What I mean by that is that you could store the variable where it is first(or most frequently requested) as a literal, and have the variable pointer be at the location of that literal.

For example, here, the timer variable is stored localy and not only does it not need to be loaded(it's already a literal) - It can also be written using a single byte with STR.

@on-frame-trap ( -> )
	[ LIT &timer $1 ] DUP #07 AND ?&>no-blink
		DUP #03 SFT #01 AND #30 SFT INC <draw-filepath> &>no-blink
	INC ,&timer STR
	BRK

@lynn spotted this. It's a bug in my implementation of unsigned integers. Intuitively I think this is wrong, and the C standard says

If an int can represent all values of the original type (as restricted by the width, for a bit-field), the value is converted to an int; otherwise, it is converted to an unsigned int.

which by my reading agrees with me. short does have a lower “rank” than int but for all practical purposes that shouldn't mean anything when they're the same size.

Maybe we should modify the compiler so short and int are true aliases, not treated as distinct types, to avoid any more bugs like this? The simple fix is to just change the promotion logic (the problem currently is it says ty->kind < TY_INT, but TY_SHORT < TY_INT…)

If x and y are structs of the same type, y = x should copy all the fields, maybe using something like memcpy.

A test that should pass:

  assert(9, ({ struct {int a; int b; int c;} x = {2,3,4}, y = {0,0,0}; y = x; y.a + y.b + y.c; }),
              "struct {int a; int b; int c;} x = {2,3,4}, y = {0,0,0}; y = x; y.a + y.b + y.c;");

Right now it returns 2 (so we are only copying the first field).

Currently the caller of a function writes arguments to an in-memory stack (@rbp). If it instead just put them on the uxn working stack and let the callee (the function itself) write them to memory, it would reduce code size when a function is called more than once, and perhaps improve the general readability of the assembly. Maybe we could even use Uxntal's ( a -- b ) syntax for type-checking?

I didn't check if we support struct arguments, but if we do, they would have to be written to memory by the caller still, and then a pointer would be pushed to the uxn working stack.

Currently we do all arithmetic in 16-bit, even when the operands and destination are 8-bit (i.e. char types). This is a very single-pass-compiler and C thing to do (surely this is what the usual arithmetic conversions were designed for), but since uxn has native 8-bit operations and a limited stack size, it's neither efficient nor makes for particularly æsthetically-pleasing assembly. This will get worse if we start doing sign extension when promoting char to int (see #9).

So, it would be nice if (char)(some_char * 2 + 3) could be codegen'd as #02 MUL #03 ADD rather than #0002 MUL2 #0003 ADD2. As I see it there's two ways this could be done: in a “single-pass” fashion by changing the codegen step, or with some sort of later optimisation pass.

I am optimistic about the former approach. I think we could do it by propagating cast/conversion information downwards when doing codegen for expressions.

Currently the codegen behaviour is something like:

• When encountering (char)(some_char * 2 + 3):
  • Recurse to generate (some_char * 2 + 3)
    • Recurse to generate some_char * 2
      • Recurse to generate some_char
        • Output code for loading some_char
        • Output code to extend to int (something like 00 SWP)
      • Recurse to generate 2
        • Output 0002
      • Output MUL2
    • Recurse to generate 3
      • Output 0003
    • Output ADD2
  • Output code to truncate to char (something like NIP)
  • Output code to extend to int (something like 00 SWP)

In the new system there would be a new flag used in expression codegen, something like truncate_to_byte. Now the behaviour would look something like:

• When encountering (char)(some_char * 2 + 3):
  • Recurse to generate (some_char * 2 + 3) with truncate_to_byte set
    • Recurse to generate some_char * 2 with truncate_to_byte set
      • Recurse to generate some_char with truncate_to_byte set
        • Output code for loading some_char
        • Output code to extend to int (something like 00 SWP)
      • Recurse to generate 2 with truncate_to_byte set
        • Output 02 0002
      • Output MUL MUL2
    • Recurse to generate 3 with truncate_to_byte set
      • Output 03 0003
    • Output ADD ADD2
  • Output code to truncate to char (something like NIP)
  • Output code to extend to int (something like 00 SWP) but only if truncate_to_byte is not set

A more tricky case is something like (char)((1 << 8) >> 8), where we can't use 8-bit operations all the way down. That can be handled by not propagating truncate_to_byte when dealing with such operators.

An important thing to note here is that it's strictly a codegen optimisation: the type information isn't affected. I don't think it's possible to do the same trick during type assignment instead, it would break things.

I love looking at the resulting tal code from my little C programs, I've been trying to compile a 6502 assembler for uxn. When writing uxntal I have this tool called uxnli that does simple graph reduction and finds little optimizations, it found a couple of things, here's a few highlights:

• STH2kr LDA -> LDAkr STHr
• SWP ORA, ORA doesn't need a specific order
• DUP2 LDA -> LDAk
• #10 SFT -> DUP ADD
• #0002 ADD2 -> INC2 INC2
• #ffff NEQ2 -> INC2 ORA

Keep up the good work! xneko really made my day.

These aren't supported:

int x[2] = {1, 1};
int *y = x;

// or more commonly...
char *message = "hi";

The compiler will complain unsupported label+addend.

chibicc writes

// Only the following expressions are allowed in an initializer:
//
//  1. A constant such as a number or a string literal
//  2. An address of another global variable with an optional addend
//
// It is obvious that we can embed (1) to an object file as static data.
// (2) may not be obvious why that can result in static data, but
// the linker supports an expression consisting of a label address
// plus/minus an addend, so (2) is allowed.

But uxnasm doesn't really support (2) so I stubbed it out with this unsupported label+addend error message.

Instead what you'd need to do in uxnasm is put another label on the same data…

@x
@y 
    0001
    0001

@message
@.L.data.0
    68
    69

Which hurts the single-pass-y-ness a little bit. And if we want to support the "addend" thing, something like

int x[5] = {1, 2, 3, 4, 5};
int *y = x + 2;

would have to be

@x
    0001
    0002
@y  
    0003
    0004
    0005

which is even trickier.

Background: #9.

The main motivation is providing a performance boost, especially for right shifts and division, but the simpler zero-extension and comparison are nice too. Also, 0xFFFFu would be allowed, whereas currently the tokeniser rejects 0xFFFF, though maybe it shouldn't to begin with. The README should explain when using unsigned integers is beneficial, and how to use them, nothing that e.g. unsigned char stuff is normally promoted to signed int IIRC.

These are easy to do codegen for, we basically just use the code from before the signedness fixes. The tricky thing is the type system changes. We'll want to implement the “usual arithmetic conversions” and “integer promotions” correctly. Maybe modern chibicc's implementation will be helpful?

These two functions should behave the same, but don't:

char foo(void)
{
    return -1;
}
char bar(void)
{
    return 0xff;
}
void main(void)
{
    int f = foo();
    int b = bar();
}

Somewhere a truncation and extension should happen, but doesn't…

|0000 @rbp $2
|0100 #ff00 .rbp STZ2 main_ BRK
( bss )
( data )
( text )
@foo_
  #0000
  #0001
  SUB2
  !.L.return.foo
  #0000
@.L.return.foo
  JMP2r
@bar_
  #00ff
  !.L.return.bar
  #0000
@.L.return.bar
  JMP2r
@main_
  .rbp LDZ2 #0004 SUB2 .rbp STZ2
  #0002 .rbp LDZ2 ADD2
  foo_
  DUP2 ROT2 STA2
  POP2
  .rbp LDZ2
  bar_
  DUP2 ROT2 STA2
  POP2
  #0000
@.L.return.main
  .rbp LDZ2 #0004 ADD2 .rbp STZ2
  JMP2r

The version of uxnasm included in the macOS binary release at https://100r.co/site/uxn.html doesn't accept the output from this compiler right now:

$ gcc -I. -P -E examples/day3.c -o tmp.c
$ ./chibicc tmp.c > c.tal
$ uxnasm c.tal c.rom
Unknown token: main
Unknown token: main
Assembly: Failed to assemble rom.
$

lynn says it's because a bare token like main being a function call is a newish feature. It works when building the latest uxnasm from source (git clone https://git.sr.ht/~rabbits/uxn && cd uxn && ./build.sh).

I guess many other people might have one of these binary releases, so we might want to change the emitted function calls to work the old way.

C has a single address space for the stack and other variables.

I am building stack machines running Forth. I am considering buiding a Uxn compatible stack machine that can run your C compiler. My question is, can your C compiler access variables lower on the stack? The problem is that on FPGAs often stacks are implemented in registers, or in a different memory block. Forth only gives access to the top two elements of the stack.

If you do not allow access to items lower on the stack, perfect. If you do, then there would be a problem using this software.

Thank you.

In the case I looked at this isn't a big deal but I wasn't sure if it was evidence of a deeper problem or not.

I was testing using this program:

#include <varvara.h>

void main() {
    putchar('h');
    putchar('\n');
}

which generated the following uxntal:

|0100
  LIT2r 0000 main_ POP2r BRK
( bss )
( data )
( text )

@main_ ( -- result* )
    OVR2r #6818 DEO #0a18 DEO #0000

  &return
    POP2r JMP2r

I noticed that the final #0000 in main is not being popped or used. (I confirmed this by inspecting the stack just before BRK runs.)

Is this expected? Having one extra value on the data stack is not a big deal by itself but I wanted to report it in case it is evidence of a deeper issue.

First off, the asm code for the bresenham routine is very nice <3
Unfortunately, the demo only runs for a few seconds before:

Return-stack overflow, by e0 at 0x010e.

Background is #9.

The motivation is to let the programmer avoid the performance penalty involved with some signed integer operations. The README should explain when using unsigned integers is beneficial, and how to use them, nothing that e.g. unsigned char stuff is normally promoted to signed int IIRC.

The codegen for this is easy, it's the type system stuff (the “integer promotions” and “usual arithmetic conversions”) that is tricky.

Modern chibicc has unsigned integers so maybe that can be a reference.

Make #defines in uxn.h for all the remaining APIs on https://wiki.xxiivv.com/site/varvara.html.

I can't decide if I want these to be super faithful (should set_spr_x be set_screen_x?), also maybe they should be CamelCase given that they're macros idk.

Currently you have to write

unsigned int x;
unsigned int y = 2;
unsigned int *z;

instead of the handy unsigned int x, y = 2, *z;.

This seems like low-hanging fruit for optimization: something like deo(0x18, 'a'); deo2(0x8, 0xabcd); compiles to

  #0065
  NIP
  #0018
  NIP DEOk
  POP2

  #abcd
  #0008
  NIP DEO2k POP
  POP2

which could just be

  #0065
  NIP #18 DEO
  #abcd
  #08 DEO2

or even

  #6518 DEO
  #abcd
  #08 DEO2

This could be achieved by a series of peephole optimizations: DEO2k POP POP2 is just DEO2, and #0065 NIP is just #65, etc. See uxnlin.

It would be nice to support inline Uxntal, something like:

int max(int x, int y) {
    return asm(x, y, "LTH2k JMP SWP2 NIP2");
}

The syntax I'm picturing is: n values to push, followed by a literal string of Uxntal that leaves an int result on the stack.

Or maybe something top-level like this is even easier to implement, and more flexible in a way:

int max(int x, int y);
asm("@max_ LTH2k JMP SWP2 NIP2 JMP2r");

Currently, everything on the working stack and the "stack frames" is 2 bytes, and a char is just stored as an int (by putting a 00 byte in front of it).

The problem with this is that in void f(char a), accessing a implicitly involves dereferencing &a, which chibicc knows to be a char*.

uxn is big-endian, so it'll be the case that, for example, &a is 0xfef6, and (mem[0xfef6], mem[0xfef7]) == (0, 'H').

Because dereferencing a char* is implemented correctly, you end up accessing the 0, not the 'H'.

There are really two steps here:

1. Get the project to a point where chibicc-uxn.exe (running in Windows/Linux/etc) can compile the codebase to cc.rom, and this cc.rom can compile something FizzBuzz-sized.
2. Get the project to a point where even this cc.rom (running in Uxn) can compile the whole codebase, and reproduce itself.

The biggest limitation is uxn's limited memory. Right now, chibicc-uxn allocates more than 64kB of memory to compile any non-trivial program. So the former sounds difficult enough, and the latter feels a bit like a pipe dream.

Here's the work that needs to be done:

• Implement more standard library functions, like calloc and strtol and sprintf. A few of these are in lib/ already.
• Remove stuff we don't support from the chibicc source code (like long).
• Right now we rely on an external preprocessor. But such a thing doesn't exist in Uxn-land, so it's probably a bit more meaningful if we at least implement #include and #define. It could be a separate program.
• Severely reduce the memory usage somehow, or find a clever way to manage memory.

Currently all local variables and function arguments get written to and read from an in-memory stack (@rbp). This makes for pretty ugly and inefficient assembly. In many cases such variables never have their address taken, so it would be possible to skip this. Any modern compiler would optimise this away with a series of passes that do alias analysis etc, but we want to keep this compiler simple and single-pass-ish, so let's do things the old-fashioned way: implement the register keyword!

I was thinking of putting register variables on the uxn working stack, but after hearing my concerns about how many operations might be needed to access something buried deep in the stack by temporaries, lynn pointed out you can also use the uxn return stack to store data, so that might be worth trying instead. :3

For function arguments annotated with register, it would be nice to have this work together with #12 so they don't need copying within the callee at all.

I'm trying to see if I can compile rxi's fe with chibicc-uxn, and the former has a bunch of function pointer typedefs it uses all around the code:

typedef fe_Object* (*fe_CFunc)(fe_Context *ctx, fe_Object *args);
typedef void (*fe_ErrorFn)(fe_Context *ctx,  char *err, fe_Object *cl);
typedef void (*fe_WriteFn)(fe_Context *ctx, void *udata, char chr);
typedef char (*fe_ReadFn)(fe_Context *ctx, void *udata);

the typedefs seem to be parsed, but when it comes to actually using them, the compiler fails:

read_file(): allocated 22919 bytes
tokenize(): allocated 453561 bytes (sizeof(Token) = 64)
tmp.c:8: typedef struct { fe_CFunc error; fe_CFunc mark, gc; } fe_Handlers;
                          ^ typename expected

I could definitely change them to void*s, but that would make some parts of the code hard to read (if you're not used to fe's source, which I am)
this is my first issue, so I'm sorry if I'm missing on something, and I'll understand if they're not intended to be supported

As I understand it, we can't support stuff like int *b = &a + 1; because uxnasm has no way to express this, but int *b = &a; seems doable maybe?