6 ms·

Chibicc – A Small C Compiler

189 points by agluszak 4y ago

userbinator 4y ago
The book covers the vast topic with an incremental approach; in the first chapter, readers will implement a "compiler" that accepts just a single number as a "language", which will then gain one feature at a time in each section of the book until the language that the compiler accepts matches what the C11 spec specifies. I took this incremental approach from the paper by Abdulaziz Ghuloum. Crenshaw's "Let's Build a Compiler" tutorial series --- from the late 80s/early 90s --- uses exactly the same approach: https://compilers.iecc.com/crenshaw/tutor2.txt https://compilers.iecc.com/crenshaw/tutor2.txt
rui314 4y ago
Author here. I'm amused that I opened HN thinking that https://docs.google.com/document/d/1kiW9qmNlJ9oQZM6r5o4_N54sX5F8_ccwCy0zpGh3MXk/edit https://docs.google.com/document/d/1kiW9qmNlJ9oQZM6r5o4_N54s... (which I posted today) might come to the front page and found this post instead. So the chibicc book is not available yet. I'm busy working on the other project (the mold linker) and don't have time to work on it. That being said, I believe the repo is still very valuable for those who want to learn how easy it is to implement a simple C compiler. chibicc's each commit was carefully written so that you can read one commit at a time. I'd recommend starting from the initial commit and observe how each feature (`if`, `for`, local variables, global variables, etc.) is implemented by following each commit.
- Rochus 4y ago
  > If they need to buy a license, that's fine, that's part of their usual business Why not release mold linker under a dual license (open source and commercial) and sell them a commercial license?
  - rui314 4y ago
    It didn't work. If it is available as open-source, they don't _need_ a different license. Anyway, it's off-topic.
    - Rochus 4y ago
      Did you have a look at Qt (https://www.qt.io/ https://www.qt.io/, https://www.qt.io/terms-conditions/ https://www.qt.io/terms-conditions/) how they do it? They sell a lot of licenses e.g. to car industry. Note that most of their products are available under LGPL, so users are not forced to open source unless they buy a commercial license.
      - deleted 4y ago
        [deleted]
    - enriquto 4y ago
      > It didn't work. If it is available as open-source, they don't _need_ a different license. Don't they? I'm surprised to hear that. I have sold a few proprietary versions of my AGPL codes (which were identical to the original one, but with the license stripped). Not enough to make a living, but I can buy some fancy bikes with the money. In some cases, they even paid --separately-- for support and a few features of the software that were of particular interest to them. For some reason, many companies are extremely frightened of the AGPL, but a dual AGPL/commercial licensing seems to fit them very well. This is a nice model for free software distribution, but it only suits small projects that do not get external contributors.
      - rui314 4y ago
        I could buy bikes too, but as you wrote that's not enough to make a living. This is my full time project. I could earn a mid 6 figure salary if I work for a big tech, and I think I'm creating a more valuable program than I did when I was working for a big tech, and in return I make money that counts in "fancy bicycle" unit... I think it's not wrong to say it didn't work quite well.
        gavinray 4y ago
        I might get shit on for saying this here, but I agree with you that it's very difficult to make a decent living on fully "free" software. I've had orgs not bat at an eye paying a few thousand for a software license if there are justifiable productivity returns and the license is required for us to continue to use the software. If that license is not required, we would never give you a dime. It's sad, but true. Those few thousand, to many companies, are pennies on the dollar. Just price it graciously so you don't leave the little guys out. You'll get grumbles but do what you need to survive if you want to do this full time and for a living. God knows you, of all people, have earned it.
- samatman 4y ago
  I'm charmed by projects like this, thanks for sharing. What I want to see is a program like this, with very simple assembly/object code, and very fast compilation, and uses DynASM to build the executable in-memory. Then use a tracing JIT to make it fast. Having good, tiny, reference C compilers is a prerequisite for that, so I'm always happy to see work in that field.
  - samsquire 4y ago
    I am interested in this too. I would do different tradeoffs. I am more interested in optional garbage collection, the parallelism and async story in the language such as threading and coroutines or both together. I suspect combining garbage collection, exceptions, closures, tail call optimisation, parallelism, JIT compilation and coroutines is difficult to do orthogonally. On eatonphil's discord someone recently shared this link: This is a framework for building high performance language runtimes https://github.com/eclipse/omr https://github.com/eclipse/omr I am currently implementing a programming language and compiler and interpreter in my multiversion-concurrency-control repository. https://github.com/samsquire/multiversion-concurrency-control https://github.com/samsquire/multiversion-concurrency-contro... I am doing codegen that is interpreted by my imaginary interpreter. My assembly has primitives for thread safe multithreading.
  - foonathan 4y ago
    I'm currently writing an interpreter for C, I plan on adding a JIT at some point as well: https://github.com/foonathan/clauf https://github.com/foonathan/clauf
- svnpenn 4y ago
  > Business Source License I am using this one: https://polyformproject.org/licenses/noncommercial/1.0.0 https://polyformproject.org/licenses/noncommercial/1.0.0
- stefanos82 4y ago
  Rui, can you open a new Discussions thread at https://github.com/rui314/mold https://github.com/rui314/mold so we can transfer the whole conversation there? We could ask for advice from other project developers that have succeeded on their own journey.
- carapace 4y ago
  I think I recall you saying that you elided the bugs, yeah? (Am I under-caffeinated this morning?) If so, you could write a second book about the bugs and issues you encountered while implementing chibicc and, uh, that would be awesome too! (I'd buy a copy.) - - - - Fantastic work, congrats and thank you!
- stefantalpalaru 4y ago
habibur 4y ago
10k LOC of *.c including comments and tests within sources. Binary size of compiler is 300kb where libc is the only dependency. My test case shows generated binary takes 3x time during execution compared with gcc -O2. Not surprising as it's not optimizing compiler. I would say excellent.
- vitiral 4y ago
  These are the stats I was looking for, very impressive indeed.
  - habibur 4y ago
    Thing I missed. No memory manager. allocate() but never free(). This makes the stats a little bit darker. You can't use it for anything other than this compiler. And adding a memory manager would possibly have added 3x more code and complexity than what's here.
agluszak 4y ago
You can consider sponsoring the author (rui314) on GitHub[1]. They're the one behind the mold linker and are considering switching the license[2] because of lack of funding. [1] - https://github.com/sponsors/rui314 https://github.com/sponsors/rui314 [2] - https://docs.google.com/document/d/1kiW9qmNlJ9oQZM6r5o4_N54sX5F8_ccwCy0zpGh3MXk/edit https://docs.google.com/document/d/1kiW9qmNlJ9oQZM6r5o4_N54s...
einpoklum 4y ago
Overall, a commendable initiative, but: > portability is not my goal at this moment. It may or may not work on systems other than Ubuntu 20.04. ... that is not good. On the contrary, you should make it so that portability is not an _issue_. IIUC, this should not depend on much beyond libc, or even just libc, so - why should it be Ubuntu-specific?
- rui314 4y ago
  CRT object files which contain process startup routines are not in a fixed directory. Unfortunately compilers have to be hard-coded to contain an appropriate directory name.
  - einpoklum 4y ago
    Well, can't that be made a build parameter, that can be determined during build configuration? CMake'ifying the project might help you get there perhaps?
    - messe 4y ago
      Or just check for an environment variable in the Makefile? No need to add the complexity of cmake.
- samsquire 4y ago
  It's an extremely large amount of work to be cross platform and cross tool chain. Packaging for Linux is thankless tedious work.
  - einpoklum 4y ago
    1. We're talking sources, not binaries. 2. Assuming chibicc doesn't also implement the C standard library, then I doubt that it's an extremely large amount of work. 3. It's not thankless - you are thanked by your users, who aren't forced to get Ubuntu 20.
    - 4y ago
simonkagedal 4y ago
> Last but not least, chibicc allocates memory using calloc but never calls free. Allocated heap memory is not freed until the process exits. I'm sure that this memory management policy (or lack thereof) looks very odd, but it makes sense for short-lived programs such as compilers. I’ve thought about this – why isn’t this a more common thing to do for short-lived programs such as cli programs? Or is it common – could anyone give some examples of well-used programs that do this? The reasons to not do it that I could think of is: 1. “It’s just bad practice” 2. You may suddenly find yourself having written some kind of malloc bomb, more easily than you think
- teo_zero 4y ago
  I always use this technique. It make no sense to free() all the memory just before the exit(). But the prerequisite isn't whether the program is short-lived, but rather that the memory usage pattern is "alloc often, free at the end".
  - simonkagedal 4y ago
    With ”short-lived”, I rather meant something like: ”does one job and then exits”, as opposed to something more dynamic – of course, that it takes a long or short time to execute isn’t by itself relevant.
- rui314 4y ago
  It caused a flame war, so #1 factor is not negligible.
  - simonkagedal 4y ago
    Haha, I bet! If you happen to have the link, I’d be curious! (And let me take the opportunity to give kudos, this looks super cool!)
- liuliu 4y ago
  If you know it will always be short lived, that's fine. But even compilers are not strictly short lived nowadays. Both Swift and Rust (I think) maintains a daemon process to assist incremental compilation.
Narishma 4y ago
This is a C compiler that is small, not a Small-C compiler that I initially thought it would be. https://en.wikipedia.org/wiki/Small-C https://en.wikipedia.org/wiki/Small-C
revskill 4y ago
My main concern with reading C code, is global variable everywhere, or am i missing something ?
- wolf550e 4y ago
  `static` variables are file-scoped, similar to module-scoped in other languages. Truly global variables are accessible from any file. Those should be very rare.
geijoenr 4y ago
I know about this project for long time and in my opinion is an excellent educational resource. As an exercise I re-targeted chibicc to z80 without any problem and it was lots of fun. Now I am trying to write an optimizer on top of it.
pfdietz 4y ago
Have you done differential testing vs. other compilers with program generators like Csmith or Yarpgen?

189 points by agluszak 4y ago

The book covers the vast topic with an incremental approach; in the first chapter, readers will implement a "compiler" that accepts just a single number as a "language", which will then gain one feature at a time in each section of the book until the language that the compiler accepts matches what the C11 spec specifies. I took this incremental approach from the paper by Abdulaziz Ghuloum. Crenshaw's "Let's Build a Compiler" tutorial series --- from the late 80s/early 90s --- uses exactly the same approach: https://compilers.iecc.com/crenshaw/tutor2.txt https://compilers.iecc.com/crenshaw/tutor2.txt

rui314 4y ago

Author here. I'm amused that I opened HN thinking that https://docs.google.com/document/d/1kiW9qmNlJ9oQZM6r5o4_N54sX5F8_ccwCy0zpGh3MXk/edit https://docs.google.com/document/d/1kiW9qmNlJ9oQZM6r5o4_N54s... (which I posted today) might come to the front page and found this post instead. So the chibicc book is not available yet. I'm busy working on the other project (the mold linker) and don't have time to work on it. That being said, I believe the repo is still very valuable for those who want to learn how easy it is to implement a simple C compiler. chibicc's each commit was carefully written so that you can read one commit at a time. I'd recommend starting from the initial commit and observe how each feature (`if`, `for`, local variables, global variables, etc.) is implemented by following each commit.

Rochus 4y ago
> If they need to buy a license, that's fine, that's part of their usual business Why not release mold linker under a dual license (open source and commercial) and sell them a commercial license?
- rui314 4y ago
  It didn't work. If it is available as open-source, they don't _need_ a different license. Anyway, it's off-topic.
  - Rochus 4y ago
    Did you have a look at Qt (https://www.qt.io/ https://www.qt.io/, https://www.qt.io/terms-conditions/ https://www.qt.io/terms-conditions/) how they do it? They sell a lot of licenses e.g. to car industry. Note that most of their products are available under LGPL, so users are not forced to open source unless they buy a commercial license.
    - deleted 4y ago
      [deleted]
  - enriquto 4y ago
    > It didn't work. If it is available as open-source, they don't _need_ a different license. Don't they? I'm surprised to hear that. I have sold a few proprietary versions of my AGPL codes (which were identical to the original one, but with the license stripped). Not enough to make a living, but I can buy some fancy bikes with the money. In some cases, they even paid --separately-- for support and a few features of the software that were of particular interest to them. For some reason, many companies are extremely frightened of the AGPL, but a dual AGPL/commercial licensing seems to fit them very well. This is a nice model for free software distribution, but it only suits small projects that do not get external contributors.
    - rui314 4y ago
      I could buy bikes too, but as you wrote that's not enough to make a living. This is my full time project. I could earn a mid 6 figure salary if I work for a big tech, and I think I'm creating a more valuable program than I did when I was working for a big tech, and in return I make money that counts in "fancy bicycle" unit... I think it's not wrong to say it didn't work quite well.
      - gavinray 4y ago
        I might get shit on for saying this here, but I agree with you that it's very difficult to make a decent living on fully "free" software. I've had orgs not bat at an eye paying a few thousand for a software license if there are justifiable productivity returns and the license is required for us to continue to use the software. If that license is not required, we would never give you a dime. It's sad, but true. Those few thousand, to many companies, are pennies on the dollar. Just price it graciously so you don't leave the little guys out. You'll get grumbles but do what you need to survive if you want to do this full time and for a living. God knows you, of all people, have earned it.
samatman 4y ago
I'm charmed by projects like this, thanks for sharing. What I want to see is a program like this, with very simple assembly/object code, and very fast compilation, and uses DynASM to build the executable in-memory. Then use a tracing JIT to make it fast. Having good, tiny, reference C compilers is a prerequisite for that, so I'm always happy to see work in that field.
- samsquire 4y ago
  I am interested in this too. I would do different tradeoffs. I am more interested in optional garbage collection, the parallelism and async story in the language such as threading and coroutines or both together. I suspect combining garbage collection, exceptions, closures, tail call optimisation, parallelism, JIT compilation and coroutines is difficult to do orthogonally. On eatonphil's discord someone recently shared this link: This is a framework for building high performance language runtimes https://github.com/eclipse/omr https://github.com/eclipse/omr I am currently implementing a programming language and compiler and interpreter in my multiversion-concurrency-control repository. https://github.com/samsquire/multiversion-concurrency-control https://github.com/samsquire/multiversion-concurrency-contro... I am doing codegen that is interpreted by my imaginary interpreter. My assembly has primitives for thread safe multithreading.
- foonathan 4y ago
  I'm currently writing an interpreter for C, I plan on adding a JIT at some point as well: https://github.com/foonathan/clauf https://github.com/foonathan/clauf
svnpenn 4y ago
> Business Source License I am using this one: https://polyformproject.org/licenses/noncommercial/1.0.0 https://polyformproject.org/licenses/noncommercial/1.0.0
stefanos82 4y ago
Rui, can you open a new Discussions thread at https://github.com/rui314/mold https://github.com/rui314/mold so we can transfer the whole conversation there? We could ask for advice from other project developers that have succeeded on their own journey.
carapace 4y ago
I think I recall you saying that you elided the bugs, yeah? (Am I under-caffeinated this morning?) If so, you could write a second book about the bugs and issues you encountered while implementing chibicc and, uh, that would be awesome too! (I'd buy a copy.) - - - - Fantastic work, congrats and thank you!
stefantalpalaru 4y ago

habibur 4y ago

10k LOC of *.c including comments and tests within sources. Binary size of compiler is 300kb where libc is the only dependency. My test case shows generated binary takes 3x time during execution compared with gcc -O2. Not surprising as it's not optimizing compiler. I would say excellent.

vitiral 4y ago
These are the stats I was looking for, very impressive indeed.
- habibur 4y ago
  Thing I missed. No memory manager. allocate() but never free(). This makes the stats a little bit darker. You can't use it for anything other than this compiler. And adding a memory manager would possibly have added 3x more code and complexity than what's here.

agluszak 4y ago

You can consider sponsoring the author (rui314) on GitHub[1]. They're the one behind the mold linker and are considering switching the license[2] because of lack of funding. [1] - https://github.com/sponsors/rui314 https://github.com/sponsors/rui314 [2] - https://docs.google.com/document/d/1kiW9qmNlJ9oQZM6r5o4_N54sX5F8_ccwCy0zpGh3MXk/edit https://docs.google.com/document/d/1kiW9qmNlJ9oQZM6r5o4_N54s...

einpoklum 4y ago

Overall, a commendable initiative, but: > portability is not my goal at this moment. It may or may not work on systems other than Ubuntu 20.04. ... that is not good. On the contrary, you should make it so that portability is not an _issue_. IIUC, this should not depend on much beyond libc, or even just libc, so - why should it be Ubuntu-specific?

rui314 4y ago
CRT object files which contain process startup routines are not in a fixed directory. Unfortunately compilers have to be hard-coded to contain an appropriate directory name.
- einpoklum 4y ago
  Well, can't that be made a build parameter, that can be determined during build configuration? CMake'ifying the project might help you get there perhaps?
  - messe 4y ago
    Or just check for an environment variable in the Makefile? No need to add the complexity of cmake.
samsquire 4y ago
It's an extremely large amount of work to be cross platform and cross tool chain. Packaging for Linux is thankless tedious work.
- einpoklum 4y ago
  1. We're talking sources, not binaries. 2. Assuming chibicc doesn't also implement the C standard library, then I doubt that it's an extremely large amount of work. 3. It's not thankless - you are thanked by your users, who aren't forced to get Ubuntu 20.
  - 4y ago

simonkagedal 4y ago

> Last but not least, chibicc allocates memory using calloc but never calls free. Allocated heap memory is not freed until the process exits. I'm sure that this memory management policy (or lack thereof) looks very odd, but it makes sense for short-lived programs such as compilers. I’ve thought about this – why isn’t this a more common thing to do for short-lived programs such as cli programs? Or is it common – could anyone give some examples of well-used programs that do this? The reasons to not do it that I could think of is: 1. “It’s just bad practice” 2. You may suddenly find yourself having written some kind of malloc bomb, more easily than you think

teo_zero 4y ago
I always use this technique. It make no sense to free() all the memory just before the exit(). But the prerequisite isn't whether the program is short-lived, but rather that the memory usage pattern is "alloc often, free at the end".
- simonkagedal 4y ago
  With ”short-lived”, I rather meant something like: ”does one job and then exits”, as opposed to something more dynamic – of course, that it takes a long or short time to execute isn’t by itself relevant.
rui314 4y ago
It caused a flame war, so #1 factor is not negligible.
- simonkagedal 4y ago
  Haha, I bet! If you happen to have the link, I’d be curious! (And let me take the opportunity to give kudos, this looks super cool!)
liuliu 4y ago
If you know it will always be short lived, that's fine. But even compilers are not strictly short lived nowadays. Both Swift and Rust (I think) maintains a daemon process to assist incremental compilation.

Narishma 4y ago

This is a C compiler that is small, not a Small-C compiler that I initially thought it would be. https://en.wikipedia.org/wiki/Small-C https://en.wikipedia.org/wiki/Small-C

revskill 4y ago

My main concern with reading C code, is global variable everywhere, or am i missing something ?

wolf550e 4y ago
`static` variables are file-scoped, similar to module-scoped in other languages. Truly global variables are accessible from any file. Those should be very rare.

geijoenr 4y ago

I know about this project for long time and in my opinion is an excellent educational resource. As an exercise I re-targeted chibicc to z80 without any problem and it was lots of fun. Now I am trying to write an optimizer on top of it.

pfdietz 4y ago

Have you done differential testing vs. other compilers with program generators like Csmith or Yarpgen?