8 ms·

Diving into GCC Internals

212 points by penguin_booze 4y ago

cptwunderlich 4y ago
Gosh, I really wish GCC had more/better documentation. Especially big picture stuff. E.g., I would like to know what register allocation algorithms it uses (and how certain details are handled), but looking at that code I noped out...
- astrange 4y ago
  You can read GCC Summit presentations for things like that. The register allocator is called IRA/LRA. It used to have a ball of mud called reload that isn’t worth understanding because it doesn’t make much sense. GCC’s code style is strange because the original authors wanted to make it look like Lisp for some reason.
  - touisteur 4y ago
    Err I always thought it looked strange because it was in C with classes before or after some holy war. While gcc (and in general compiler) plugins are some of the most interesting tech enablers (be it for fuzzing,, static analysis, or runtime checks injection) 'People competently maintaining gcc plugins' (a sect I'm not a part anymore, thank dog) are amongst the most patient, devoted, unsung angels of this world.
    - astrange 4y ago
      It’s in C++ now. The weird spacing and functions ending in _p are Lispisms. It’s also garbage collected so it’s still not “normal” C++ but neither is LLVM. Not sure about the plugin API, but C++ is basically impossible to use with plugins because it’s so hard to keep ABI contracts, so it might not have changed.
      - UncleEntity 4y ago
        Isn’t the compiler the one who makes the ABI contract? And I’ve seen _p and friends all over the place usually to differentiate between a pointer and, umm, not pointer. I thought it was a C++ism to be honest.
        astrange 4y ago
        C++ has things like the fragile base class problem meaning you can accidentally break it easily. There's issues with throwing exceptions across different libraries on some platforms (maybe just Windows?) but I forget the reason why. p is short for predicate.
        pjmlp 4y ago
        Fragile base class problem affects all languages that offer some kind of inheritance, not only C++.
        valleyer 4y ago
        You are of course correct in a broad sense. However, when the discussion already mentions "ABI contracts", they're probably referring specifically to the "fragile binary interface problem" (especially regarding member field access), which does not affect all languages that offer inheritance. As the Wikipedia article mentions, this more specific problem is (confusingly) often referred to just as the "fragile base class problem". https://en.wikipedia.org/wiki/Fragile_binary_interface_problem https://en.wikipedia.org/wiki/Fragile_binary_interface_probl...
        pjmlp 4y ago
        It still affects all compiled languages that offer inheritance, and OOP ABIs like COM.
        valleyer 4y ago
  - iib 4y ago
    Maybe the lispism are Stallman's legacy. He is a great lisp proponent after all.
- chrisseaton 4y ago
  It uses something they call IRA and LRA on the RTL representation. But bottom line is: it's graph colouring. https://gcc.gnu.org/onlinedocs/gccint/RTL-passes.html https://gcc.gnu.org/onlinedocs/gccint/RTL-passes.html There's really quite a lot of documentation and published papers when you actually look: https://github.com/gcc-mirror/gcc/blob/751f306688508b08842d0ab967dee8e6c3b91351/gcc/ira.cc#L21-L363 https://github.com/gcc-mirror/gcc/blob/751f306688508b08842d0...
- Analemma_ 4y ago
  This might be less true now, but for a long time gcc's code was terrible and undocumented on purpose. rms wanted it that way, to make it harder for it to be forked or EEE'd by corporations. Whether that was a good plan is up for debate, but there you go.
  - WalterBright 4y ago
    People say that dmd's backend is terrible and undocumented, but I don't know what they're talking about: https://github.com/dlang/dmd/tree/master/src/dmd/backend https://github.com/dlang/dmd/tree/master/src/dmd/backend
- mhh__ 4y ago
  LLVM: Lots of documentation for frontend authors, not so much for backend stuff. GCC: Lots of documentation for backend authors, actively made difficult to being used for frontends for many years (although things have improved dramatically)
  - est31 4y ago
    How have things evolved for LLVM backend authors? Has it improved too?
- pif 4y ago
  > I would like to know what register allocation algorithms it uses I'm wondering why you'd like to know. If it is just for your curiosity, that's very good. If you want to participate in the compiler development effort, hat tip! But if you are thinking about tuning your code to such an internal detail, please don't! Coding to an implementation, rather than an interface, is never a good idea.
bragr 4y ago
- deleted 4y ago
  [deleted]
- ketralnis 4y ago
  I don't know what the sarcasm is helping. Somebody's working on documenting it and they're not done yet, and they're documenting that too.
  - bragr 4y ago
    Yeah, I'm being salty, but at the same gcc is notoriously unapproachable while also struggling to pull in new blood. Considering the long, but sporadic update history [1] of this documentation, I am not optimistic about this effort turning it around. Seems more likely to become yet another one of the out of date or incomplete tutorials lying around [2]. GCC's own contribution docs [3] cop to the fact that most new contributors are doing paid work on behalf of chip and system designers, so for GCC's sake I hope it remains the must have compiler for new chips because that seems to be its main source of fresh blood at this point. This blog post [4] from a GCC and autotools developer popped up on here a month ago, and while it doesn't address GCC, if you squint I think you can apply most of the criticisms to GCC as well. [1] https://github.com/davidmalcolm/gcc-newbies-guide/commits/master https://github.com/davidmalcolm/gcc-newbies-guide/commits/ma... [2] https://gcc.gnu.org/wiki/GettingStarted https://gcc.gnu.org/wiki/GettingStarted [3] https://gcc.gnu.org/contributewhy.html https://gcc.gnu.org/contributewhy.html [4] https://www.owlfolio.org/development/autoconf-swot/ https://www.owlfolio.org/development/autoconf-swot/
    - dralley 4y ago
      It'll lose that too as more and more low-level software is written in LLVM-backed languages.
    - pvg 4y ago
      Yeah, I'm being salty You've hit upon a reliable way to turn that kind of comment into a good comment which is to imagine the grumpcomment getting downvoted, flagged, complained about or mod-scolded, writing a defense of the grumpcomment and then just posting that, instead of the original comment. Works every time way more than 60% of the time.
deleted 4y ago
[deleted]
mhh__ 4y ago
GCC really needs to get it's act together if it wants to not die. Basic things like onboarding and spectating on other people's code being reviewed is pretty hard to do from a mailing list. GCC is already basically non-existent in academic research now, although the inner essentials of the compiler are still pretty damn good and is the benchmark for open source compilers, the stuff around the outside is suffering.
- edelsohn 4y ago
  As policies for academics to own intellectual property and form companies, the license also has come into play. The license also has influenced corporate choices and advocacy for toolchain projects. Documentation and actively encouraging new developers is important, but not the only impact on the project.
- deleted 4y ago
  [deleted]
- matheusmoreira 4y ago
  Pretty interesting history behind the current status quo. Looks like GCC deliberately resisted an interoperable design in an attempt to exclude proprietary code integration. It's only natural that interoperable alternatives would emerge and threaten its dominance. https://lwn.net/Articles/582697/ https://lwn.net/Articles/582697/ > GCC's developers have actively resisted allowing it to be modularized in a way that would allow GCC's internal representation of a program to be read and used by proprietary compilation tools or optimizers. Learning about this changed the way I looked at all GNU software. > Basic things like onboarding and spectating on other people's code being reviewed is pretty hard to do from a mailing list. Participation is even harder. I made some mistakes when I tried to reply to people on the GPG mailing list because I didn't really understand how mailing lists worked. Thankfully a person made a bug report on the issue tracker. I still don't fully understand how they work. Many times I thought twice before getting involved in projects because I don't want to risk accidentally emailing people directly instead of the list thread again.
  - mshockwave 4y ago
soc340 4y ago
Gives me PTSD to my operating systems class in university. Once upon a time I knew how a linker actually worked under the hood, but those days are long gone.
- deleted 4y ago
  [deleted]
slavik81 4y ago
If anyone wants to make an easy but useful improvement to GCC, might I suggest: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=58770 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=58770 Summary: headers that use pragma once are tracked using a list resulting in slow uniqueness checks. The performance fix is to use a hash table.
- rurban 4y ago
  The generated switch statements for large sparse lists should be generated to hash tables, perfect tables even. A not so trivial task.
- deleted 4y ago
  [deleted]
- colejohnson66 4y ago
  Wait. So gcc uses a linked list? OK, but why? If the whole point of #pragma once is to replace include guards, why would they use something as inefficient as a linked list (O(n^2) for this situation[a]) for that, but something quicker for include guards? That’s nonsense! And then for each .c/.cpp file, the compiler has to do the whole rigamarole all over again because modules are too new for everyone to use. [a]: or worse when you have a full project!
  - bregma 4y ago
    Basic CS fail. Most translation units have maybe 100 header files or fewer. While a hash map might be O(1) (O(n^2) worst case) and a linked list O(n^2), the overhead of every insertion into a hash map is significantly greater than into a linked list. If you have such a tiny n, a linked list is almost always more time- and space-efficient. Switching to a more inappropriate data structure is more likely to negatively impact the performance of your toolchain. Of course the best answer is to make the change and collect measurements before and after using a spectrum of data sets, then compare. Don't let me stop you. But remember for that small a number of items bubble sort is usually the fastest, most efficient algorithm. Also remember that looking up a header name at preprocessor time, no matter how slow, will likely not show up on your profile graph when you turn on the optimizer.
deleted 4y ago
[deleted]
winrid 4y ago
One thing I've heard about even modern compilers is that they don't really release memory during compilation, as it's faster just to use the memory and release it all when the process exits. How true is that?
- melissalobos 4y ago
  It is true that that is of course faster. However, clang and GCC, both do release memory since with modern C++ software projects, it can take huge amounts of ram to compile them. https://dmalcolm.fedorapeople.org/gcc/newbies-guide/memory-management.html https://dmalcolm.fedorapeople.org/gcc/newbies-guide/memory-m...
  - chrisseaton 4y ago
    > It is true that that is of course faster. Is it? What do you base that on? I would guess that this hypothesis was true at one time, but is no longer, due to relative memory latencies increasing that mean that the resulting lack of locality becomes a very big problem. I think this is empirically support by for example this research result, where epsilon collectors are not the highest throughput. https://users.cecs.anu.edu.au/~steveb/pubs/papers/lbo-ispass-2022.pdf https://users.cecs.anu.edu.au/~steveb/pubs/papers/lbo-ispass...
    - deleted 4y ago
      [deleted]
- octoberfranklin 4y ago
  The nix programming language's interpreter deliberately has no memory garbage collector based on this argument. This decision does force a few other architectural decisions, and as a result has led to a few firey debates. Most nix users are surprised to learn that nix has no GC. It's unfortunately hard to search for details about this since nix uses the phrase "garbage collection" to describe something it does to the filesystem, rather than memory.
- deleted 4y ago
  [deleted]

212 points by penguin_booze 4y ago

Gosh, I really wish GCC had more/better documentation. Especially big picture stuff. E.g., I would like to know what register allocation algorithms it uses (and how certain details are handled), but looking at that code I noped out...

astrange 4y ago
You can read GCC Summit presentations for things like that. The register allocator is called IRA/LRA. It used to have a ball of mud called reload that isn’t worth understanding because it doesn’t make much sense. GCC’s code style is strange because the original authors wanted to make it look like Lisp for some reason.
- touisteur 4y ago
  Err I always thought it looked strange because it was in C with classes before or after some holy war. While gcc (and in general compiler) plugins are some of the most interesting tech enablers (be it for fuzzing,, static analysis, or runtime checks injection) 'People competently maintaining gcc plugins' (a sect I'm not a part anymore, thank dog) are amongst the most patient, devoted, unsung angels of this world.
  - astrange 4y ago
    It’s in C++ now. The weird spacing and functions ending in _p are Lispisms. It’s also garbage collected so it’s still not “normal” C++ but neither is LLVM. Not sure about the plugin API, but C++ is basically impossible to use with plugins because it’s so hard to keep ABI contracts, so it might not have changed.
    - UncleEntity 4y ago
      Isn’t the compiler the one who makes the ABI contract? And I’ve seen _p and friends all over the place usually to differentiate between a pointer and, umm, not pointer. I thought it was a C++ism to be honest.
      - astrange 4y ago
        C++ has things like the fragile base class problem meaning you can accidentally break it easily. There's issues with throwing exceptions across different libraries on some platforms (maybe just Windows?) but I forget the reason why. p is short for predicate.
        pjmlp 4y ago
        Fragile base class problem affects all languages that offer some kind of inheritance, not only C++.
        valleyer 4y ago
        You are of course correct in a broad sense. However, when the discussion already mentions "ABI contracts", they're probably referring specifically to the "fragile binary interface problem" (especially regarding member field access), which does not affect all languages that offer inheritance. As the Wikipedia article mentions, this more specific problem is (confusingly) often referred to just as the "fragile base class problem". https://en.wikipedia.org/wiki/Fragile_binary_interface_problem https://en.wikipedia.org/wiki/Fragile_binary_interface_probl...
        pjmlp 4y ago
        It still affects all compiled languages that offer inheritance, and OOP ABIs like COM.
        valleyer 4y ago
- iib 4y ago
  Maybe the lispism are Stallman's legacy. He is a great lisp proponent after all.
chrisseaton 4y ago
It uses something they call IRA and LRA on the RTL representation. But bottom line is: it's graph colouring. https://gcc.gnu.org/onlinedocs/gccint/RTL-passes.html https://gcc.gnu.org/onlinedocs/gccint/RTL-passes.html There's really quite a lot of documentation and published papers when you actually look: https://github.com/gcc-mirror/gcc/blob/751f306688508b08842d0ab967dee8e6c3b91351/gcc/ira.cc#L21-L363 https://github.com/gcc-mirror/gcc/blob/751f306688508b08842d0...
Analemma_ 4y ago
This might be less true now, but for a long time gcc's code was terrible and undocumented on purpose. rms wanted it that way, to make it harder for it to be forked or EEE'd by corporations. Whether that was a good plan is up for debate, but there you go.
- WalterBright 4y ago
  People say that dmd's backend is terrible and undocumented, but I don't know what they're talking about: https://github.com/dlang/dmd/tree/master/src/dmd/backend https://github.com/dlang/dmd/tree/master/src/dmd/backend
mhh__ 4y ago
LLVM: Lots of documentation for frontend authors, not so much for backend stuff. GCC: Lots of documentation for backend authors, actively made difficult to being used for frontends for many years (although things have improved dramatically)
- est31 4y ago
  How have things evolved for LLVM backend authors? Has it improved too?
pif 4y ago
> I would like to know what register allocation algorithms it uses I'm wondering why you'd like to know. If it is just for your curiosity, that's very good. If you want to participate in the compiler development effort, hat tip! But if you are thinking about tuning your code to such an internal detail, please don't! Coding to an implementation, rather than an interface, is never a good idea.

bragr 4y ago

deleted 4y ago
[deleted]
ketralnis 4y ago
I don't know what the sarcasm is helping. Somebody's working on documenting it and they're not done yet, and they're documenting that too.
- bragr 4y ago
  Yeah, I'm being salty, but at the same gcc is notoriously unapproachable while also struggling to pull in new blood. Considering the long, but sporadic update history [1] of this documentation, I am not optimistic about this effort turning it around. Seems more likely to become yet another one of the out of date or incomplete tutorials lying around [2]. GCC's own contribution docs [3] cop to the fact that most new contributors are doing paid work on behalf of chip and system designers, so for GCC's sake I hope it remains the must have compiler for new chips because that seems to be its main source of fresh blood at this point. This blog post [4] from a GCC and autotools developer popped up on here a month ago, and while it doesn't address GCC, if you squint I think you can apply most of the criticisms to GCC as well. [1] https://github.com/davidmalcolm/gcc-newbies-guide/commits/master https://github.com/davidmalcolm/gcc-newbies-guide/commits/ma... [2] https://gcc.gnu.org/wiki/GettingStarted https://gcc.gnu.org/wiki/GettingStarted [3] https://gcc.gnu.org/contributewhy.html https://gcc.gnu.org/contributewhy.html [4] https://www.owlfolio.org/development/autoconf-swot/ https://www.owlfolio.org/development/autoconf-swot/
  - dralley 4y ago
    It'll lose that too as more and more low-level software is written in LLVM-backed languages.
  - pvg 4y ago
    Yeah, I'm being salty You've hit upon a reliable way to turn that kind of comment into a good comment which is to imagine the grumpcomment getting downvoted, flagged, complained about or mod-scolded, writing a defense of the grumpcomment and then just posting that, instead of the original comment. Works every time way more than 60% of the time.

deleted 4y ago

[deleted]

mhh__ 4y ago

GCC really needs to get it's act together if it wants to not die. Basic things like onboarding and spectating on other people's code being reviewed is pretty hard to do from a mailing list. GCC is already basically non-existent in academic research now, although the inner essentials of the compiler are still pretty damn good and is the benchmark for open source compilers, the stuff around the outside is suffering.

edelsohn 4y ago
As policies for academics to own intellectual property and form companies, the license also has come into play. The license also has influenced corporate choices and advocacy for toolchain projects. Documentation and actively encouraging new developers is important, but not the only impact on the project.
deleted 4y ago
[deleted]
matheusmoreira 4y ago
Pretty interesting history behind the current status quo. Looks like GCC deliberately resisted an interoperable design in an attempt to exclude proprietary code integration. It's only natural that interoperable alternatives would emerge and threaten its dominance. https://lwn.net/Articles/582697/ https://lwn.net/Articles/582697/ > GCC's developers have actively resisted allowing it to be modularized in a way that would allow GCC's internal representation of a program to be read and used by proprietary compilation tools or optimizers. Learning about this changed the way I looked at all GNU software. > Basic things like onboarding and spectating on other people's code being reviewed is pretty hard to do from a mailing list. Participation is even harder. I made some mistakes when I tried to reply to people on the GPG mailing list because I didn't really understand how mailing lists worked. Thankfully a person made a bug report on the issue tracker. I still don't fully understand how they work. Many times I thought twice before getting involved in projects because I don't want to risk accidentally emailing people directly instead of the list thread again.
- mshockwave 4y ago

soc340 4y ago

Gives me PTSD to my operating systems class in university. Once upon a time I knew how a linker actually worked under the hood, but those days are long gone.

deleted 4y ago
[deleted]

slavik81 4y ago

If anyone wants to make an easy but useful improvement to GCC, might I suggest: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=58770 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=58770 Summary: headers that use pragma once are tracked using a list resulting in slow uniqueness checks. The performance fix is to use a hash table.

rurban 4y ago
The generated switch statements for large sparse lists should be generated to hash tables, perfect tables even. A not so trivial task.
deleted 4y ago
[deleted]
colejohnson66 4y ago
Wait. So gcc uses a linked list? OK, but why? If the whole point of #pragma once is to replace include guards, why would they use something as inefficient as a linked list (O(n^2) for this situation[a]) for that, but something quicker for include guards? That’s nonsense! And then for each .c/.cpp file, the compiler has to do the whole rigamarole all over again because modules are too new for everyone to use. [a]: or worse when you have a full project!
- bregma 4y ago
  Basic CS fail. Most translation units have maybe 100 header files or fewer. While a hash map might be O(1) (O(n^2) worst case) and a linked list O(n^2), the overhead of every insertion into a hash map is significantly greater than into a linked list. If you have such a tiny n, a linked list is almost always more time- and space-efficient. Switching to a more inappropriate data structure is more likely to negatively impact the performance of your toolchain. Of course the best answer is to make the change and collect measurements before and after using a spectrum of data sets, then compare. Don't let me stop you. But remember for that small a number of items bubble sort is usually the fastest, most efficient algorithm. Also remember that looking up a header name at preprocessor time, no matter how slow, will likely not show up on your profile graph when you turn on the optimizer.

deleted 4y ago

[deleted]

winrid 4y ago

One thing I've heard about even modern compilers is that they don't really release memory during compilation, as it's faster just to use the memory and release it all when the process exits. How true is that?

melissalobos 4y ago
It is true that that is of course faster. However, clang and GCC, both do release memory since with modern C++ software projects, it can take huge amounts of ram to compile them. https://dmalcolm.fedorapeople.org/gcc/newbies-guide/memory-management.html https://dmalcolm.fedorapeople.org/gcc/newbies-guide/memory-m...
- chrisseaton 4y ago
  > It is true that that is of course faster. Is it? What do you base that on? I would guess that this hypothesis was true at one time, but is no longer, due to relative memory latencies increasing that mean that the resulting lack of locality becomes a very big problem. I think this is empirically support by for example this research result, where epsilon collectors are not the highest throughput. https://users.cecs.anu.edu.au/~steveb/pubs/papers/lbo-ispass-2022.pdf https://users.cecs.anu.edu.au/~steveb/pubs/papers/lbo-ispass...
  - deleted 4y ago
    [deleted]
octoberfranklin 4y ago
The nix programming language's interpreter deliberately has no memory garbage collector based on this argument. This decision does force a few other architectural decisions, and as a result has led to a few firey debates. Most nix users are surprised to learn that nix has no GC. It's unfortunately hard to search for details about this since nix uses the phrase "garbage collection" to describe something it does to the filesystem, rather than memory.
deleted 4y ago
[deleted]