3 ms·

I think one of the issue is that the register allocation algorithm -- alongside the SSA generation -- is not enough. Generally after the SSA pass, you convert

by stevefan1999 8mo ago

I think one of the issue is that the register allocation algorithm -- alongside the SSA generation -- is not enough. Generally after the SSA pass, you convert all of them into register transfer language (RTL) and then do register allocation pass. And for GCC's case it is even more extreme -- You have GIMPLE in the middle that does more aggressive optimization, similar to rustc's MIR. CCC doesn't have all that, and for register allocation you can try to do simple linear scan just as the usual JIT compiler would do though (and from my understanding, something CCC should do at a simple cost), but most of the "hard part" of compiler today is actually optimization -- frontend is mostly a solved problem if you accept some hacks, unlike me who is still looking for an elegant academic solution to the typedef problem.

hackyhacky 8mo ago
What is the typedef problem?
- nxobject 8mo ago
  If stevefan1999's referring to a nasty frontend issue, it might be due to the fact that a name introduced by a typedef and an identical identifier can mingle in the same scope, which makes parsing pretty nasty – e.g. (example from source at end): typedef int AA; void foo() { AA AA; /\* OK - define variable AA of type AA */ int BB = AA * 2; /\* OK - AA is just a variable name here \*/ } void bar() { int aa = sizeof(AA), AA, bb = sizeof(AA); } https://eli.thegreenplace.net/2011/05/02/the-context-sensitivity-of-cs-grammar-revisited https://eli.thegreenplace.net/2011/05/02/the-context-sensiti... I don't know off the top of my head whether there's a parser framework that makes this parse "straightforward" to express.
  - delusional 8mo ago
    In your example bar is actually trivial, since both the type AA and the variable AA are ints both aa and bb ends up as 4 no matter how you parse it. AA has to be typedef'd to something other than int.
- wahern 8mo ago
  Lexical parsing C is simple, except that typedef's technically make it non-context-free. See https://en.wikipedia.org/wiki/Lexer_hack https://en.wikipedia.org/wiki/Lexer_hack When handwriting a parser, it's no big deal, but it's often a stumbling block for parser generators or other formal approaches. Though, I recall there's a PEG-based parser for C99/C11 floating around that was supposed to be compliant. But I'm having trouble finding a link, and maybe it was using something like LPeg, which has features beyond pure PEG that help with context dependent parsing.
  - nextaccountic 8mo ago
    Clang's solution (presented at the end of the Wikipedia article you linked) seem much better - just use a single lexical token for both types and variables. Then, only the parser needs to be context sensitive, for the A* B; construct which is either a no-op multiplication (if A is a variable) or a variable declaration of a pointer type (if A is a type)
    - stevefan1999 8mo ago
      Well, as you see this is inherently taking the spirit of GLL/GLR parser -- defer parse until we have all the information. The academic solution to this is not to do it on token level but introduce a parse tree that is "forkable", meaning a new persistent data structure is needed to "compress" the tree when we have different routes, and that thing is called: graph structured stack (https://en.wikipedia.org/wiki/Graph-structured_stack https://en.wikipedia.org/wiki/Graph-structured_stack)
  - mahmoudimus 8mo ago
    I think you're referring to this one: https://github.com/jhjourdan/C11parser https://github.com/jhjourdan/C11parser
    - wahern 8mo ago
      What I had specifically in mind definitely wasn't using OCaml or Menhir, but that's a very useful resource, as is the associated paper, "A simple, possibly correct LR parser for C11", https://jhjourdan.mketjh.fr/pdf/jourdan2017simple.pdf https://jhjourdan.mketjh.fr/pdf/jourdan2017simple.pdf This is closer to what I remember, but I'm not convinced it's what I had in mind, either: https://github.com/edubart/lpegrex/blob/main/parsers/c11.lua https://github.com/edubart/lpegrex/blob/main/parsers/c11.lua It uses LPeg's match-time capture feature (not a pure PEG construct) to dynamically memorize typedef's and condition subsequent matches. In fact, it's effectively identical to what C11Parser is doing, down to the two dynamically invoked helper functions: declare_typedefname/is_typedefname vs set_typedef/is_typedef. C11Parser and the paper are older, so maybe the lpegrex parser is derivative. (And probably what I had in mind, if not lpegrex, was derivative, too.)
adgjlsfhk1 8mo ago
Note that the LLVM approach to IR is probably a bit more sane than the GCC one. GCC has ~3 completely different IRs at different stages in the pipeline, while LLVM mostly has only canonical IR form for passing data around through the optimization passes (and individual passes will sometimes make their own temporary IR locally to make a specific analysis easier).

hackyhacky 8mo ago

What is the typedef problem?

nxobject 8mo ago
If stevefan1999's referring to a nasty frontend issue, it might be due to the fact that a name introduced by a typedef and an identical identifier can mingle in the same scope, which makes parsing pretty nasty – e.g. (example from source at end): typedef int AA; void foo() { AA AA; /\* OK - define variable AA of type AA */ int BB = AA * 2; /\* OK - AA is just a variable name here \*/ } void bar() { int aa = sizeof(AA), AA, bb = sizeof(AA); } https://eli.thegreenplace.net/2011/05/02/the-context-sensitivity-of-cs-grammar-revisited https://eli.thegreenplace.net/2011/05/02/the-context-sensiti... I don't know off the top of my head whether there's a parser framework that makes this parse "straightforward" to express.
- delusional 8mo ago
  In your example bar is actually trivial, since both the type AA and the variable AA are ints both aa and bb ends up as 4 no matter how you parse it. AA has to be typedef'd to something other than int.
wahern 8mo ago
Lexical parsing C is simple, except that typedef's technically make it non-context-free. See https://en.wikipedia.org/wiki/Lexer_hack https://en.wikipedia.org/wiki/Lexer_hack When handwriting a parser, it's no big deal, but it's often a stumbling block for parser generators or other formal approaches. Though, I recall there's a PEG-based parser for C99/C11 floating around that was supposed to be compliant. But I'm having trouble finding a link, and maybe it was using something like LPeg, which has features beyond pure PEG that help with context dependent parsing.
- nextaccountic 8mo ago
  Clang's solution (presented at the end of the Wikipedia article you linked) seem much better - just use a single lexical token for both types and variables. Then, only the parser needs to be context sensitive, for the A* B; construct which is either a no-op multiplication (if A is a variable) or a variable declaration of a pointer type (if A is a type)
  - stevefan1999 8mo ago
    Well, as you see this is inherently taking the spirit of GLL/GLR parser -- defer parse until we have all the information. The academic solution to this is not to do it on token level but introduce a parse tree that is "forkable", meaning a new persistent data structure is needed to "compress" the tree when we have different routes, and that thing is called: graph structured stack (https://en.wikipedia.org/wiki/Graph-structured_stack https://en.wikipedia.org/wiki/Graph-structured_stack)
- mahmoudimus 8mo ago
  I think you're referring to this one: https://github.com/jhjourdan/C11parser https://github.com/jhjourdan/C11parser
  - wahern 8mo ago
    What I had specifically in mind definitely wasn't using OCaml or Menhir, but that's a very useful resource, as is the associated paper, "A simple, possibly correct LR parser for C11", https://jhjourdan.mketjh.fr/pdf/jourdan2017simple.pdf https://jhjourdan.mketjh.fr/pdf/jourdan2017simple.pdf This is closer to what I remember, but I'm not convinced it's what I had in mind, either: https://github.com/edubart/lpegrex/blob/main/parsers/c11.lua https://github.com/edubart/lpegrex/blob/main/parsers/c11.lua It uses LPeg's match-time capture feature (not a pure PEG construct) to dynamically memorize typedef's and condition subsequent matches. In fact, it's effectively identical to what C11Parser is doing, down to the two dynamically invoked helper functions: declare_typedefname/is_typedefname vs set_typedef/is_typedef. C11Parser and the paper are older, so maybe the lpegrex parser is derivative. (And probably what I had in mind, if not lpegrex, was derivative, too.)

adgjlsfhk1 8mo ago

Note that the LLVM approach to IR is probably a bit more sane than the GCC one. GCC has ~3 completely different IRs at different stages in the pipeline, while LLVM mostly has only canonical IR form for passing data around through the optimization passes (and individual passes will sometimes make their own temporary IR locally to make a specific analysis easier).