10 ms·

9cc: A Small C Compiler

132 points by matt_d 8y ago

aidenn0 8y ago
It lists a goal as "compiling real-world programs such as the linux kernel" The last time I investigated the linux kernel had so many gcc-isms that it was probably true that if you could compile the linux kernel, you could probably compile any program targeted to gcc.
- ggm 8y ago
  BSD kernel is maybe a cleaner target?
- nickpsecurity 8y ago
  xv6 might be nicer start: https://pdos.csail.mit.edu/6.828/2012/xv6.html https://pdos.csail.mit.edu/6.828/2012/xv6.html For bootstrapping, the overall consensus is you make enough C to compile, without optimizations, early version of GCC which compiles itself from there until you reach current version. Several folks are trying to compile TCC instead to leverage it and dwheeler's work.
- wtracy 8y ago
  Other "alternative" compilers like tcc have pulled it off, supposedly without patching the kernel, so it is doable.
  - e12e 8y ago
    Does tcc compile a vanilla kernel? I know tccboot added some minor patches: https://bellard.org/tcc/tccboot_readme.html https://bellard.org/tcc/tccboot_readme.html
kazinator 8y ago
Small nitpick. Functions in C that take no arguments are written name(void){...} not name(){...}. This latter form is an old-style definition which doesn't introduce a prototype into the scope. For functions that have prototypes, it is okay, but when they do not, you're losing type checking (yes, even on the number of arguments). The following program compiles with no diagnostics for me with -W -Wall -ansi -pedantic, with GCC 7.3 on Ubuntu 18: int func() { return 0; } int main() { func(3); return 0; } -std=c11 (as you're using) makes no difference. The same is not true of C++: func() in C++ is a prototype definition. C++ supports (void) for compatibility with C, but even in nonsensical contexts: class::class(void);
- sesutton 8y ago
  Clang (tested with v7) however does issue a warning even with no flags set.
  - kazinator 8y ago
    Any compiler should because as a definition, int foo() { } does in fact inform us that the function can only be correctly called with no arguments. Formally, this is not introduced into the scope as type information according to the language spec, but that's no reason not to warn about it informally.
- rui314 8y ago
  Quote from 6.7.6.3.14 of the C++11 spec (http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1548.pdf http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1548.pdf): > An identifier list declares only the identifiers of the parameters of the function. An empty list in a function declarator that is part of a definition of that function specifies that the function has no parameters. The empty list in a function declarator that is not part of a definition of that function specifies that no information about the number or types of the parameters is supplied. So, my interpretation is that the following two function definitions define the same function of the exact same type void func() {} void func(void) {} although the following two function declarations declare two functions of different types void func(); void func(void);
  - deleted 8y ago
    [deleted]
  - kazinator 8y ago
    That is of course the C11 (draft) spec, not C++. Interesting find there. The wording is also in the C99 draft; it is not new. It is in fact saying that the empty list in a definition is a special case and does declare that the function takes no parameters. To "specify" here can be understood to mean as inserting information about type into the declaration scope; that which a declaration does. So that's a bit of a bug in GCC there; it should be treating this the same as (void) and therefore diagnosing that way. If not by default, then at least when -pedantic is applied. But nope: $ gcc -Wall -W -std=c11 -pedantic proto.c $
csours 8y ago
I wonder if this is a reference to the band 10cc - https://en.wikipedia.org/wiki/10cc https://en.wikipedia.org/wiki/10cc
- brabara 8y ago
  From the 2015 discussion about 8cc, the author states that "I chose a random character to append before 'cc'." https://news.ycombinator.com/item?id=9125912 https://news.ycombinator.com/item?id=9125912
- rpz 8y ago
  G is the 7th letter of the alphabet
  - csours 8y ago
    It took me a distressingly long time to figure out what you meant by this.
- chriscappuccio 8y ago
  his last C compiler was called 8cc
kazinator 8y ago
Regarding your Makefile; you should still pass CFLAGS through to the compiler when linking, not only LDFLAGS. Suppose CFLAGS contains -m32 (supported by an x86-64-targetted GCC to do 32 bit). You compile the .o files with that, but then link without it, which fails trying to make a 64 bit executable out of 32 bit .o's. Some crazy distros pass a --sysroot in CFLAGS; if you don't have that, your build finds the wrong library and header files. Even when linking, don't call "cc", but "$(CC)". You're relying on the implicit rule to compile your .c to .o which will use $(CC). $(CC) could be some ARM cross-compiler supplied by a distro. When you link using "cc", you end up using the build-machine's native compiler. Write the build system like this is an awesome program that major distros will be eager to pick up, and make it easy for the package maintainer. :) Speaking of CFLAGS, only set that conditionally; don't clobber it: CFLAGS ?= -O2 # Only if CFLAGS is not specified externally, use this default for things that your program needs in order to build right, put that in other variables of your own: DIALECT_CFLAGS := -std=c11 CFLAGS += $(DIALECT_CFLAGS) # integrate external CFLAGS with our own. Same deal with LDFLAGS. Both CFLAGS and LDFLAGS can include important things that cause a bad build if you mess with them.
- Zelizz 8y ago
  Where would one go to find more of this conventional Makefile wisdom? I've had so many issues trying to use make the "right" way (flexible, clean, terse, etc.). I feel like one of the best ways to acquire this wisdom is to post a project with lots of mistakes and let people tear it apart.
  - kazinator 8y ago
    I got it from working on lots of C for almost thirty years, and also by putting together a from-scratch embedded GNU/Linux distro some decade ago, and more recently doing distro work also. As far as knowing GNU Make, I recommend just reading the manual from beginning to end, perhaps twice.
  - simonblack 8y ago
    I bought what seemed to be overstock or maybe it was just being remaindered in a 50%-off Uni Bookshop sale about 20 years ago. It's a tiny (80 page) little book called "Managing Projects with make" by Steve Talbot and printed by O'Reilly and Associates. Most of what I know about 'make' I learned from this book.
mshockwave 8y ago
>no memory management is the memory management policy in 9cc. We allocate memory using malloc() but never call free(). >I know that people find the policy odd, but this is actually a reasonable design choice for short-lived programs such as compilers. I'm strongly disagree at this point. Memory management is important even for short-lived programs. It would bring burden to the OS if you invoke this kind of "short-lived, memory-management-free" programs multiple times. >This policy greatly simplifies code and also eliminates use-after-free bugs entirely Not facing it is definitely not a good way to solve a problem. It's a bad attitude as a programmer be honestly.
- cperciva 8y ago
  > Memory management is important even for short-lived programs. It would bring burden to the OS if you invoke this kind of "short-lived, memory-management-free" programs multiple times. All the memory is freed when the process exits. Why does it matter if you run the program multiple times?
  - sifoobar 8y ago
    It will put more pressure on the allocator when running, doing that a lot will likely have some kind of cumulative consequence down the line. I know from experience [0] that even reusing allocated memory rather than bouncing it back to malloc can have dramatic effects. [0] https://gitlab.com/sifoo/snigl/blob/master/src/snigl/pool.h https://gitlab.com/sifoo/snigl/blob/master/src/snigl/pool.h
    - cperciva 8y ago
      Sure, but if you're not freeing memory you don't need a real malloc. You allocation function can be just "top += allocsize".
      - wrs 8y ago
        Yes, that's commonly known as "arena allocation" and has been used for decades in programs that have well-defined phases that create lots of connected objects with the same lifetime, like compiler passes, RPC serialization layers, or query planners.
akkartik 8y ago
https://github.com/rui314/9cc/blob/882e4b2dd8/main.c#L7 https://github.com/rui314/9cc/blob/882e4b2dd8/main.c#L7 int main(int argc, char **argv) { ... Vector *tokens = tokenize(path, true); Program *prog = parse(tokens); sema(prog); gen_ir(prog); if (dump_ir1) dump_ir(prog->funcs); optimize(prog); liveness(prog); alloc_regs(prog); if (dump_ir2) dump_ir(prog->funcs); gen_x86(prog); return 0; } This is wonderful.
- mmirate 8y ago
  And also wonderfully devoid of error-handling, too. It's the most common way for beautiful-looking C code to look beautiful.
  - caf 8y ago
    A compiler is in the happy position where there is little point in continuing to run after encountering an error, so it can bail right out with exit(2) after reporting the error to the user. This means that the contract on parse(), for example, can be that if it returns, it has succeeded.
    - vlovich123 8y ago
      Except of course LLVM has proven the value in not assuming this pattern & building your compiler as a library of which the executable entrypoint is but one frontend.
      - Asooka 8y ago
        Exceptions are the exit() of libraries. Or if you're using plain C, setjmp/longjmp might be a good idea, depending on what you're doing.
  - cheez 8y ago
    Unless the programmer uses the null object pattern in which case everything is hunky dory. For example, an empty "Program" would probably do the job.
userbinator 8y ago
Good to see more C/subset-C compilers being written. Besides the immense pedagogical value, they are also useful for preventing the "trusting trust" attack: https://dwheeler.com/trusting-trust/ https://dwheeler.com/trusting-trust/ I will also make a suggestion to use precedence climbing instead of plain recursive descent for the parser; it makes the parser even simpler and table-driven, which is important with a language like C that has many precedence levels.
- marktangotango 8y ago
  Interesting, do you have any useful links related to this concept?
  - userbinator 8y ago
    Here is the discussion of the original Trusting Trust attack: https://news.ycombinator.com/item?id=13569275 https://news.ycombinator.com/item?id=13569275
    - marktangotango 8y ago
      Thanks I was referring to precedence climbing parser part of GP reply.
      - catpolice 8y ago
        https://eli.thegreenplace.net/2012/08/02/parsing-expressions-by-precedence-climbing https://eli.thegreenplace.net/2012/08/02/parsing-expressions... Precedence climbing is also (intimately) related to Pratt parsing, and there's a useful series of articles about the two here: https://www.oilshell.org/blog/2017/03/31.html https://www.oilshell.org/blog/2017/03/31.html
      - userbinator 8y ago
        https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#climbing https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#climbing
rpz 8y ago
kparc.com/b
utam0k 8y ago
I'm rewriting 9cc with Rust from first commit. https://github.com/utam0k/r9cc https://github.com/utam0k/r9cc
bakul 8y ago
How does this compare to Nils Holm’s subc compiler that has somewhat similar goals? There is a book describing the compiler as well (though the current version of the compiler supports a larger subset of the C language). https://www.t3x.org/subc/index.html https://www.t3x.org/subc/index.html
pjmlp 8y ago
I really wish people would choose better names, we just had an hyphen and it becomes a C dialect from the early 80's. https://en.wikipedia.org/wiki/Small-C https://en.wikipedia.org/wiki/Small-C
- creatornator 8y ago
  "a small c compiler" is just the description, "9cc" is the name itself, so there's not much similarity there...
jokoon 8y ago
How does this compare with tcc?
EdSchouten 8y ago
Interesting to mention: the author of this compiler, Rui Ueyama, is also a developer at the LLVM project. He's one of the most active developers of LLD, LLVM's linker.

132 points by matt_d 8y ago

It lists a goal as "compiling real-world programs such as the linux kernel" The last time I investigated the linux kernel had so many gcc-isms that it was probably true that if you could compile the linux kernel, you could probably compile any program targeted to gcc.

ggm 8y ago
BSD kernel is maybe a cleaner target?
nickpsecurity 8y ago
xv6 might be nicer start: https://pdos.csail.mit.edu/6.828/2012/xv6.html https://pdos.csail.mit.edu/6.828/2012/xv6.html For bootstrapping, the overall consensus is you make enough C to compile, without optimizations, early version of GCC which compiles itself from there until you reach current version. Several folks are trying to compile TCC instead to leverage it and dwheeler's work.
wtracy 8y ago
Other "alternative" compilers like tcc have pulled it off, supposedly without patching the kernel, so it is doable.
- e12e 8y ago
  Does tcc compile a vanilla kernel? I know tccboot added some minor patches: https://bellard.org/tcc/tccboot_readme.html https://bellard.org/tcc/tccboot_readme.html

kazinator 8y ago

Small nitpick. Functions in C that take no arguments are written name(void){...} not name(){...}. This latter form is an old-style definition which doesn't introduce a prototype into the scope. For functions that have prototypes, it is okay, but when they do not, you're losing type checking (yes, even on the number of arguments). The following program compiles with no diagnostics for me with -W -Wall -ansi -pedantic, with GCC 7.3 on Ubuntu 18: int func() { return 0; } int main() { func(3); return 0; } -std=c11 (as you're using) makes no difference. The same is not true of C++: func() in C++ is a prototype definition. C++ supports (void) for compatibility with C, but even in nonsensical contexts: class::class(void);

sesutton 8y ago
Clang (tested with v7) however does issue a warning even with no flags set.
- kazinator 8y ago
  Any compiler should because as a definition, int foo() { } does in fact inform us that the function can only be correctly called with no arguments. Formally, this is not introduced into the scope as type information according to the language spec, but that's no reason not to warn about it informally.
rui314 8y ago
Quote from 6.7.6.3.14 of the C++11 spec (http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1548.pdf http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1548.pdf): > An identifier list declares only the identifiers of the parameters of the function. An empty list in a function declarator that is part of a definition of that function specifies that the function has no parameters. The empty list in a function declarator that is not part of a definition of that function specifies that no information about the number or types of the parameters is supplied. So, my interpretation is that the following two function definitions define the same function of the exact same type void func() {} void func(void) {} although the following two function declarations declare two functions of different types void func(); void func(void);
- deleted 8y ago
  [deleted]
- kazinator 8y ago
  That is of course the C11 (draft) spec, not C++. Interesting find there. The wording is also in the C99 draft; it is not new. It is in fact saying that the empty list in a definition is a special case and does declare that the function takes no parameters. To "specify" here can be understood to mean as inserting information about type into the declaration scope; that which a declaration does. So that's a bit of a bug in GCC there; it should be treating this the same as (void) and therefore diagnosing that way. If not by default, then at least when -pedantic is applied. But nope: $ gcc -Wall -W -std=c11 -pedantic proto.c $

csours 8y ago

I wonder if this is a reference to the band 10cc - https://en.wikipedia.org/wiki/10cc https://en.wikipedia.org/wiki/10cc

brabara 8y ago
From the 2015 discussion about 8cc, the author states that "I chose a random character to append before 'cc'." https://news.ycombinator.com/item?id=9125912 https://news.ycombinator.com/item?id=9125912
rpz 8y ago
G is the 7th letter of the alphabet
- csours 8y ago
  It took me a distressingly long time to figure out what you meant by this.
chriscappuccio 8y ago
his last C compiler was called 8cc

kazinator 8y ago

Regarding your Makefile; you should still pass CFLAGS through to the compiler when linking, not only LDFLAGS. Suppose CFLAGS contains -m32 (supported by an x86-64-targetted GCC to do 32 bit). You compile the .o files with that, but then link without it, which fails trying to make a 64 bit executable out of 32 bit .o's. Some crazy distros pass a --sysroot in CFLAGS; if you don't have that, your build finds the wrong library and header files. Even when linking, don't call "cc", but "$(CC)". You're relying on the implicit rule to compile your .c to .o which will use $(CC). $(CC) could be some ARM cross-compiler supplied by a distro. When you link using "cc", you end up using the build-machine's native compiler. Write the build system like this is an awesome program that major distros will be eager to pick up, and make it easy for the package maintainer. :) Speaking of CFLAGS, only set that conditionally; don't clobber it: CFLAGS ?= -O2 # Only if CFLAGS is not specified externally, use this default for things that your program needs in order to build right, put that in other variables of your own: DIALECT_CFLAGS := -std=c11 CFLAGS += $(DIALECT_CFLAGS) # integrate external CFLAGS with our own. Same deal with LDFLAGS. Both CFLAGS and LDFLAGS can include important things that cause a bad build if you mess with them.

Zelizz 8y ago
Where would one go to find more of this conventional Makefile wisdom? I've had so many issues trying to use make the "right" way (flexible, clean, terse, etc.). I feel like one of the best ways to acquire this wisdom is to post a project with lots of mistakes and let people tear it apart.
- kazinator 8y ago
  I got it from working on lots of C for almost thirty years, and also by putting together a from-scratch embedded GNU/Linux distro some decade ago, and more recently doing distro work also. As far as knowing GNU Make, I recommend just reading the manual from beginning to end, perhaps twice.
- simonblack 8y ago
  I bought what seemed to be overstock or maybe it was just being remaindered in a 50%-off Uni Bookshop sale about 20 years ago. It's a tiny (80 page) little book called "Managing Projects with make" by Steve Talbot and printed by O'Reilly and Associates. Most of what I know about 'make' I learned from this book.

mshockwave 8y ago

>no memory management is the memory management policy in 9cc. We allocate memory using malloc() but never call free(). >I know that people find the policy odd, but this is actually a reasonable design choice for short-lived programs such as compilers. I'm strongly disagree at this point. Memory management is important even for short-lived programs. It would bring burden to the OS if you invoke this kind of "short-lived, memory-management-free" programs multiple times. >This policy greatly simplifies code and also eliminates use-after-free bugs entirely Not facing it is definitely not a good way to solve a problem. It's a bad attitude as a programmer be honestly.

cperciva 8y ago
> Memory management is important even for short-lived programs. It would bring burden to the OS if you invoke this kind of "short-lived, memory-management-free" programs multiple times. All the memory is freed when the process exits. Why does it matter if you run the program multiple times?
- sifoobar 8y ago
  It will put more pressure on the allocator when running, doing that a lot will likely have some kind of cumulative consequence down the line. I know from experience [0] that even reusing allocated memory rather than bouncing it back to malloc can have dramatic effects. [0] https://gitlab.com/sifoo/snigl/blob/master/src/snigl/pool.h https://gitlab.com/sifoo/snigl/blob/master/src/snigl/pool.h
  - cperciva 8y ago
    Sure, but if you're not freeing memory you don't need a real malloc. You allocation function can be just "top += allocsize".
    - wrs 8y ago
      Yes, that's commonly known as "arena allocation" and has been used for decades in programs that have well-defined phases that create lots of connected objects with the same lifetime, like compiler passes, RPC serialization layers, or query planners.

akkartik 8y ago

https://github.com/rui314/9cc/blob/882e4b2dd8/main.c#L7 https://github.com/rui314/9cc/blob/882e4b2dd8/main.c#L7 int main(int argc, char **argv) { ... Vector *tokens = tokenize(path, true); Program *prog = parse(tokens); sema(prog); gen_ir(prog); if (dump_ir1) dump_ir(prog->funcs); optimize(prog); liveness(prog); alloc_regs(prog); if (dump_ir2) dump_ir(prog->funcs); gen_x86(prog); return 0; } This is wonderful.

mmirate 8y ago
And also wonderfully devoid of error-handling, too. It's the most common way for beautiful-looking C code to look beautiful.
- caf 8y ago
  A compiler is in the happy position where there is little point in continuing to run after encountering an error, so it can bail right out with exit(2) after reporting the error to the user. This means that the contract on parse(), for example, can be that if it returns, it has succeeded.
  - vlovich123 8y ago
    Except of course LLVM has proven the value in not assuming this pattern & building your compiler as a library of which the executable entrypoint is but one frontend.
    - Asooka 8y ago
      Exceptions are the exit() of libraries. Or if you're using plain C, setjmp/longjmp might be a good idea, depending on what you're doing.
- cheez 8y ago
  Unless the programmer uses the null object pattern in which case everything is hunky dory. For example, an empty "Program" would probably do the job.

userbinator 8y ago

Good to see more C/subset-C compilers being written. Besides the immense pedagogical value, they are also useful for preventing the "trusting trust" attack: https://dwheeler.com/trusting-trust/ https://dwheeler.com/trusting-trust/ I will also make a suggestion to use precedence climbing instead of plain recursive descent for the parser; it makes the parser even simpler and table-driven, which is important with a language like C that has many precedence levels.

marktangotango 8y ago
Interesting, do you have any useful links related to this concept?
- userbinator 8y ago
  Here is the discussion of the original Trusting Trust attack: https://news.ycombinator.com/item?id=13569275 https://news.ycombinator.com/item?id=13569275
  - marktangotango 8y ago
    Thanks I was referring to precedence climbing parser part of GP reply.
    - catpolice 8y ago
      https://eli.thegreenplace.net/2012/08/02/parsing-expressions-by-precedence-climbing https://eli.thegreenplace.net/2012/08/02/parsing-expressions... Precedence climbing is also (intimately) related to Pratt parsing, and there's a useful series of articles about the two here: https://www.oilshell.org/blog/2017/03/31.html https://www.oilshell.org/blog/2017/03/31.html
    - userbinator 8y ago
      https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#climbing https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#climbing

rpz 8y ago

kparc.com/b

utam0k 8y ago

I'm rewriting 9cc with Rust from first commit. https://github.com/utam0k/r9cc https://github.com/utam0k/r9cc

bakul 8y ago

How does this compare to Nils Holm’s subc compiler that has somewhat similar goals? There is a book describing the compiler as well (though the current version of the compiler supports a larger subset of the C language). https://www.t3x.org/subc/index.html https://www.t3x.org/subc/index.html

pjmlp 8y ago

I really wish people would choose better names, we just had an hyphen and it becomes a C dialect from the early 80's. https://en.wikipedia.org/wiki/Small-C https://en.wikipedia.org/wiki/Small-C

creatornator 8y ago
"a small c compiler" is just the description, "9cc" is the name itself, so there's not much similarity there...

jokoon 8y ago

How does this compare with tcc?

EdSchouten 8y ago

Interesting to mention: the author of this compiler, Rui Ueyama, is also a developer at the LLVM project. He's one of the most active developers of LLD, LLVM's linker.