Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

TinyCompiler: A compiler in a week-end

ssloy.github.io

Post reply on HN
Print view View original

71–80 of 120 posts

Re: TinyCompiler: A compiler in a week-end

#71

Post by contificate »

sitkack wrote: post #68
sylware wrote: post #22

On the same way than cproc+QBE I guess, 70% of gcc speed in my benchmarks. The more real-life alternatives to those abominations of gcc and clang, the merrier. I wish the linux kernel devs did care to keep the door _reasonably_ open for such compilers (with assembler source files as alternative to inline assembly, some extensions avoidance and niche expensive compiler features). This is another case of why super comp…

QBE is ... problematic. The source has no comments, single letter variable names. It is not written to be extended by anyone else other than the author. I would recommend libfirm over QBE by at least 10km. https://libfirm.github.io/ https://github.com/libfirm/libfirm

On the topic of QBE, I've always felt that someone aiming to do the same scope of project ought to make their IR a syntactic subset of LLVM IR. If you do that, your test suite can involve invoking LLVM for a comparison.

As for QBE itself, many of the core transformations are fairly standard, which makes it somewhat more approachable for me (e.g. Cooper et al's dominance algorithm, Rideau et al's parallel moves algorithm, etc.). Of course, this doesn't negate the fact that it's not as "hackable" as they probably intended.

Re: TinyCompiler: A compiler in a week-end

#72

Post by delta_p_delta_x »

RossBencina wrote: post #26
sieve wrote: post #11

Earlier quoted context omitted.

If you know basic programming (js/python), a day is more than enough to get the concept across using a tiny language. Could probably be done in an hour. The problem, always, is people are given terrible reading recommendations which makes the subject more complicated than it is.

I never took a compilers course. The first reading recommendation I got was The Dragon Book. Perhaps not the worst starting place at the time (mid 90s) but my memory of it was that the book was front-loaded with automata and parser theory. At the time I didn't really make it past the front end. It would be interesting to see a compiler tutorial that started at codegen and worked backwards (or started at the ends: lex…

> It would be interesting to see a compiler tutorial that started at codegen and worked backwards (or started at the ends: lexing and codegen, and worked towards the middle in alternating chapters)

This is exactly how my university's compiler course did it[1]. It was really nice to start with assembly and go upwards. We had all the lexing/parsing stuff being discussed around the middle of the semester rather than being saddled with theory-heavy regex, automata theory, etc right at the beginning.

[1]: https://ilyasergey.net/CS4212/

Re: TinyCompiler: A compiler in a week-end

#73

Post by haqreu »

contificate wrote: post #70
haqreu wrote: post #64

Earlier quoted context omitted.

I'd argue that Lengauer-Tarjan is overrated. While it is neat, it's premature optimization IMHO. Fully maximal SSA (at the entry of each block insert a phi-node for each variable) + dead code elimination (we need it anyways) is much simpler.

Typical implementations of Lengauer-Tarjan are often taken verbatim from Andrew Appel's book and involve higher constant factors than alternative algorithms - such as Cooper et al's "engineered" version of the usual fixpoint algorithm, which is very neat, simple, and performs well. If you are saying that constructing SSA following the classical approach is a premature optimisation, perhaps you would prefer Braun et a…

Thank you for the reference, I'll check it.

Why not fully maximal SSA + DCE? I mean, other than timings consideration. Fully maximal does not even need any graph traversal, it is entirely local to each block.

Re: TinyCompiler: A compiler in a week-end

#74

Post by delta_p_delta_x »

Interesting off-topic—I noticed this paragraph:

> Personally, I get a twisted pleasure wearing a T-shirt with this print in the 2020s, even though I hate being a walking billboard. But the number of angry comments from confused people makes up for any moral discomfort of advertising on my belly!

It's possible the 'angry comments' are from people who may have mistaken it for an antisemitic, white supremacist symbol[1].

[1]: https://www.adl.org/resources/hate-symbol/not-equal

Re: TinyCompiler: A compiler in a week-end

#75

Post by nurettin »

glouwbug wrote: post #2

I appreciate how wonderfully simple and dependency free this is. More often than not people just want to write a compiler of sorts without bison or yacc, or LLVM, and just convert expressions into assembler or vm-like instructions that _just run_. This is a great starting point for that, and I wish I had something like it 10 years ago. (Crenshaw's Let's Build a Compiler is an excellent source too if you want to go on…

Not to take away from the author or you, but we had things like this 10 years ago https://github.com/ymyzk/tinyc/tree/master/tinyc

Re: TinyCompiler: A compiler in a week-end

#76

Post by contificate »

haqreu wrote: post #73
contificate wrote: post #70

Earlier quoted context omitted.

Typical implementations of Lengauer-Tarjan are often taken verbatim from Andrew Appel's book and involve higher constant factors than alternative algorithms - such as Cooper et al's "engineered" version of the usual fixpoint algorithm, which is very neat, simple, and performs well. If you are saying that constructing SSA following the classical approach is a premature optimisation, perhaps you would prefer Braun et a…

Thank you for the reference, I'll check it. Why not fully maximal SSA + DCE? I mean, other than timings consideration. Fully maximal does not even need any graph traversal, it is entirely local to each block.

I think it will introduce too many redundant phis, but I've never used it in practice - so I can only speculate. I'm not convinced DCE will clean maximal SSA up substantially. Even the classic Cytron et al algorithm must be combined with liveness analysis to avoid placing dead phis (that is, it does not produce pruned SSA by default). In the past, there was always a fear that SSA has the potential to cause quadratic blowup in the number of variables - this concern is mostly theoretical but probably influenced some of the design decision around algorithms for constructing SSA.

Braun et al's algorithm works backwards from uses (which generate liveness), so you get pruned SSA out. In the case of reducible control flow graphs, you also get minimal SSA. This is all without any liveness or dominance computation beforehand. Granted, you may want those things later, but it's nice that you can construct a decent quality SSA with a fairly intuitive algorithm. Also shown in the paper is that you can incorporate a few light optimisations during SSA construction (constant folding, for example).

Re: TinyCompiler: A compiler in a week-end

#77

Post by haqreu »

contificate wrote: post #76
haqreu wrote: post #73

Earlier quoted context omitted.

Thank you for the reference, I'll check it. Why not fully maximal SSA + DCE? I mean, other than timings consideration. Fully maximal does not even need any graph traversal, it is entirely local to each block.

I think it will introduce too many redundant phis, but I've never used it in practice - so I can only speculate. I'm not convinced DCE will clean maximal SSA up substantially. Even the classic Cytron et al algorithm must be combined with liveness analysis to avoid placing dead phis (that is, it does not produce pruned SSA by default). In the past, there was always a fear that SSA has the potential to cause quadratic…

Thank you!

Re: TinyCompiler: A compiler in a week-end

#78

Post by haqreu »

delta_p_delta_x wrote: post #74

Interesting off-topic—I noticed this paragraph: > Personally, I get a twisted pleasure wearing a T-shirt with this print in the 2020s, even though I hate being a walking billboard. But the number of angry comments from confused people makes up for any moral discomfort of advertising on my belly! It's possible the 'angry comments' are from people who may have mistaken it for an antisemitic, white supremacist symbol[1]…

Hum. Did not anticipate that, thank you for pointing out.

Re: TinyCompiler: A compiler in a week-end

#79

Post by fooker »

glouwbug wrote: post #2

I appreciate how wonderfully simple and dependency free this is. More often than not people just want to write a compiler of sorts without bison or yacc, or LLVM, and just convert expressions into assembler or vm-like instructions that _just run_. This is a great starting point for that, and I wish I had something like it 10 years ago. (Crenshaw's Let's Build a Compiler is an excellent source too if you want to go on…

I’d argue that you should start with doing an interpreter and push it as long as you can.

But once you’re ready to generate code, use llvm or something like that because you are going to hit very problematic roadblocks early in your effort that will kill your interest in compilers otherwise.

Some examples are: ensuring you can compare expressions for equality, ensuring that changed expressions don’t violate dominance, SSA conversion, avoiding infinite loops when analyzing cfgs. If you don’t start with knowledge of several things like this, you are looking at rewriting your compiler a dozen times. That is a great way to learn about compilers, but perhaps not the first compiler you make.

Re: TinyCompiler: A compiler in a week-end

#80

Post by kragen »

fogleman wrote: post #31

I've been a big fan of the author's tiny renderer. Nice to see a tiny compiler too!

That sounds interesting! He seems to have four tiny renderers pinned on his GitHub page; is https://github.com/ssloy/tinyrenderer the one you're recommending? What do you like about it?
Post reply on HN