4 ms·
Generate good code from the beginning; don't generate bad code and optimize later Unfortunately this is something that no compiler I know of does, as evidenced
by userbinator 9y ago
Generate good code from the beginning; don't generate bad code and optimize later
Unfortunately this is something that no compiler I know of does, as evidenced by their -O0 being far worse than even what a naive Asm programmer (human) could do, and it's one of the things that irks me about compilers. Dataflow-directed, "work backwards" techniques might be the solution to this, but once again I don't know of any compilers that do it.
On the other hand, his points about using recursive-descent parsing seem to agree with the majority of widely-used compilers. However, this is factually incorrect:
I even think that the availability of powerful
bottom-up parser generators such as Yacc are responsible for the cryptic syntax of C.
Dennis Ritchie's first C compiler used recursive descent. Yacc itself was written in C, so it could not have come before. You can see the sources yourself here: https://news.ycombinator.com/item?id=5748672 https://news.ycombinator.com/item?id=5748672
- chubot 9y agoI agree he is wrong on that point. The recursive descent is easy to see here: http://minnie.tuhs.org/cgi-bin/utree.pl?file=V6/usr/source/c/c02.c http://minnie.tuhs.org/cgi-bin/utree.pl?file=V6/usr/source/c... Search for statement() and forstmt(). (This site has a more modern, easier-to-read version of the Github files, which at least has #defines rather than hard-coded ints!!!) But a large part of it is also Dijikstra's shunting yard algorithm: http://minnie.tuhs.org/cgi-bin/utree.pl?file=V6/usr/source/c/c00.c http://minnie.tuhs.org/cgi-bin/utree.pl?file=V6/usr/source/c... Read an expression and return a pointer to its tree. It's the classical bottom-up, priority-driven scheme. The initflg prevents the parse from going past "," or ":" because those delimitesrs are special in initializer (and some other) expressions. tree() Related post: Code for the Shunting Yard Algorithm, and More http://www.oilshell.org/blog/2017/04/22.html http://www.oilshell.org/blog/2017/04/22.html
- seanmcdirmid 9y agoPrecedence parsing is surprisingly robust and error tolerant, as well as being bottom up. Sans braces, it can be used for much of your expression syntax depending on how overloaded your terminals are.
- vidarh 9y agoYou can use it for braces too, with some relatively simple additional rules. Braces the way they're used in most languages are "just" a special case of parentheses: You need to recurse, and the closing parenthesis/brace needs to trigger reduce all the way to a single value. If you're willing to sacrifice a bit more generality you can parse a lot more. E.g. my (very much in-progress and incomplete) Ruby compiler uses precedence parsing with tweaks to parse most of the Ruby grammar, including blocks (do/end, {/}), array indices and initializers (foo[1], vs [1,2,3]) and more. It's been hell to adjust the priorities, and it's not correct yet, but I also think it can be cleaned up quite a bit more. The biggest pain point, actually, is tidying up the generated tree to remove superfluous nodes and flaten various bits, and that's where I'll need to do the most work to simplify. There are of course ugly parts of this with Ruby that ruined my originally quite nice and clean generic shunting yard code. E.g. if "foo" is a local variable "foo [1]" should parse as "foo.[](1)" (that is '[]' is a method name), while if "foo" is not a local variable, it is implicitly a method call, and "foo [1]" should parse as "foo([1])" with "self" as implicit receiver. I've for now resolved that by having a few "artificial" terminals to handle this and a few other ambiguities that are picked based on context and resolved later, but I'm really not happy about it. Worst case is I "surrender" and convert it to a recursive descent like the higher levels of the grammar, but I want to see what I can do with the current one first. Currently the full parser, which still lacks some parts of Ruby is about 1600 lines of Ruby (including the lexical tokenizer and some generic parser/scanner utility classes), which I'm distinctly displeased about - it's much smaller than MRI, but not as much smaller as I think should be possible, especially since it's still missing pieces; granted there's a lot of comments, but I think parsing Ruby in Ruby should be doable in <1000 lines of Ruby code using recursive descent + precedence parsing despite Ruby's many idiosyncracies. Less if you exclude the code for a decent generic parser library. I think that says a lot of the simplicity of applying both recursive descent and precedence parsing..
- seanmcdirmid 9y agoNote I was using brace synonymously with paren (to me, parens are just a special kind of brace, I assume you are equating brace with bracket). Sure, you can also deal with terminal overloading using adjacency if you want. However, the parser gets more complex and it becomes less worth it. In the parsers I build, I match braces in a separate earlier phase anyways (you don’t need a parser to do that, and it makes the parser much more robust if you do). However, the main drawback of a precedence parser is that you don’t get any parse errors out of it, and you have to manually go back and check that your trees are actually well formed. So I’ve went back to pure recursive descent.
- mojuba 9y ago> Unfortunately this is something that no compiler I know of does Turbo Pascal (and Delphi), originally influenced by Wirth's books did exactly that. It was an incredibly fast compiler that generated surprizingly decent binaries.
- e12e 9y agoI've seen people imply that latest generation c compilers (gcc,clang etc) generate quite a lot better code than these previous generation compilers. Partly I guess turbo Pascal didn't to much auto vectorization for example. Unsure about loop unrolling. I'm sure it helped that Pascal had a IMNHO saner calling convention (more like the current amd64 convention) - so would utilise register for passing arguments rather than always using the stack.
- Narishma 9y agoI doubt vectorization (automatic or not) was relevant during Turbo Pascal's era.
- e12e 9y agoTrue, but it's relevant today (since around 1996 with the mmx instruction set). And if some people are arguing today that you can have single pass, fast and simple, and get ~max performance on modern architecture. I'm not saying you can't, I'm just saying that "as fast machine code as early 90s era c compilers" might not translate to as fast as today's c++ compilers machine code.
- vidarh 9y ago>> Generate good code from the beginning; don't generate bad code and optimize later > Unfortunately this is something that no compiler I know of does, You're probably right compared to modern compilers. What you need to compare to are the compilers of the era, which were truly abysmal. It's not that the Wirth compilers generated fantastic code (e.g. at least one of Wirths students explored adding much more aggressive optimization to his Oberon compiler), but they generated code that was a great deal better than a lot of non-Wirth style compilers at the time. Some compilers of the time even depended on peephole optimizer passes because the code they generated was so bad that even simple 2-3 instruction peephole passes were enough to drastically improve the code. There was little reason for this. E.g. most of the time it was a matter of as basic stuff as passing on information about the registers to use rather than the dumb/naive approach of generating everything using scratch registers that you move things to/from. I remember back in my asm days that I once had the C source for a GUI component I wanted to use, but the code the C compiler I had available generated was so awful that in exasperation I compiled it, disassembled it, and proceeded to manually clean it up. I deleted about half the instructions of about several thousand lines of compiler output, with very minimal fixups.
- sitkack 9y agoI did something similar, I was a novice C programmer, and had a problem that could have used some `rot` instructions that weren't available, so I used the emit asm flag to generate stubs and wrote the function in asm, it would have taken me ages to do it from scratch, but fixing up the output of the C compiler took about an hour of experimentation.
- lboasso 9y agoWirth's compilers generated reasonably good code: 80% of the performance of optimizing compilers with 20% of the effort. The first Java client jit compiler, was developed by Robert Griesemer (former PhD student of Wirth). The design of the compiler is described in the paper "A compiler for the java hotspot virtual machine", published in the same book: "The School of Niklaus Wirth: The Art of Simplicity".
- gsg 9y agoThis is nonsense. Modern compilers don't work by generating the results you see with -O0 and then optimising; the poor quality of -O0 code is the result of skipping register allocation. > Dataflow-directed, "work backwards" techniques might be the solution Destination driven code generation is a known technique. It doesn't generate good enough results to have gotten much attention (better than what you get from -O0, though).