Hacker News Reader

Comment by pcwalton | Hacker News Reader

> And actually we’re now entering a world where at minimum supporting LLVM as a backend option is mandatory.

I would have said this too a few years ago, but Go is a huge counterexample. It's become very popular without using LLVM, and the compiler that does use a mature, optimizing backend (gccgo) doesn't get nearly as much use as the Plan 9-based one.

I should also mention that increasingly it's become popular to have a mid-level IR that you lower the AST to before lowering to LLVM IR. GHC does it, Swift is doing it, and Rust is working on doing it. The reasons are (a) you can do language-specific optimizations like devirtualization, which are often pretty hard to do in LLVM; (b) going from AST to LLVM IR is often a big, messy leap for any language that isn't C.

View on HN

It's actually quite messy for C as well. I guess I should qualify that: it's messy for C as used in practice as well.

#pragma weak, asm labels, always_inline, debug information, attribute regparm, inline assembly, etc...

All of this is doable via incremental lowering from the AST (this is how clang does it) but it is fairly painful.

Even the relatively banal:

  enum e;
  void (*fp)(enum e);
  enum e { v = 1ULL << 32 };

results in quite a bit of gymnastics! (https://github.com/llvm-mirror/clang/blob/202433cccd87a4e7d1...)

Go is an outlier, a social phenomenon brought about by just the right combination of people, companies and the niche it occupies. Something like Go won't happen again in the near future, not at this scale for sure.

Which can be a bad or good thing, depending on how you decide to look at the issue.

> I would have said this too a few years ago, but Go is a huge counterexample.

I've been wondering about this ever since Go came out. If I recall correctly, LLVM was already a viable option back then.

The latest release of Go earlier this week featured a pretty big revamp of their backend with a new SSA-based middle/backend. I wonder how much work went into that and could they have achieved that faster had they been on LLVM since day 1.

I'd like to know what is the downside of using LLVM. Why did they choose to write their own optimizer?

Anyway, the most difficult part of writing the compiler was probably the garbage collector.

Maybe the biggest issue is optimizing register allocation while providing the information for all roots for the garbage collection... For non-GC languages you don't need to care about it and just agressively optimize register allocation. For GC languages you have to be careful, because the GC must know 1) which registers are holding references and which not 2) which of those registers are "alive" and which are not in use anymore (and therefore ready for garbage collection)...

LLVM has full support for precise garbage collection.

Russ Cox gave a really good answer to this question. I have to paraphrase because I can't find the original comment.

It was done for implementation speed. They had a compiler backend which they, the early Go team, were all familiar with. It was small so they could quickly change it to suit Go, rather than the other way around.

Russ Cox expressed the sentiment that if they had tried to use LLVM there would have been a lot of up front work that would have taken a long time and the Go project probably would have fizzled out. Using the plan 9 tool chain they were up and running very quickly allowing them to focus on the most important work, designing the language itself.

(Probably shouldn't attribute this to Russ Cox, I've probably read into his (rather briefer than what I wrote above) comments)

In my opinion this was the right choice. If LLVM turns out to be the best backend for Go it's easy to use it later. However, the language itself is largely fixed after 1.0. Better to focus on the language than the compiler backend which can be swapped out later.

> I'd like to know what is the downside of using LLVM.

Depending on C++ code and keep alive the belief that you can only create compilers in C and C++?

As many without experience in compiler development think.

Also, and this is specially painful when compiling Rust or Swift from source, saving themselves the pain of waiting around 4h for a clean compile.

LLVM does take a long time to compile, but four hours is an exaggeration. A mid-range computer can compile it in 30 minutes with -j4, and a good computer can compile it in 10 with -j8.

Core duo netbook with 4GB RAM and 5400 RPM hard disk.

I can assure you it really does take 4 hours.

And to bring the point home, I can link you to the Swift issue where I was discussing this matter.

A core duo isn't even in the realm of mid-range. That's very nearly a 10 year old processor!

Yeah, but it works perfectly well as a travel netbook for coding on the go.

Also I never had 4h builds with single core processors back when I was working full time with C++. The slowest ones were around 2h.

A core duo would run circles around those computer systems, hence my dismay how much hardware LLVM requires for building.

I would imagine compiler design has become much more complex in 10 years, and a low end i3 is something like at least 3 times faster than a core duo.

I would agree if other compilers, not LLVM based, took as much to compile.

Also that is surely a side effect how they are using C++, which desperately needs modules.

Those compilers don't do nearly as much optimization as LLVM does. It's hard to overstate how wide the gap between the classical compilers you like and LLVM/GCC truly is. LLVM has no fewer than three IRs, each with a full suite of compiler optimizations (four if you count ScheduleDAG). LICM, just to name one example, runs at each stage (see MachineLICM.cpp). Turbo Pascal did nowhere near that level of optimization, and it produced unacceptably slow programs by modern standards.

Heh, I was in this same boat two years ago. Servo used to build its own Rust back then, and that involved building llvm. I hadn't yet discovered ccache[1] and I had an old 4GB RAM laptop with a Core something processor. Took 4-6 hours total IIRC. This was also a really old laptop, so that was understandable. But very very annoying, since sometimes I'd need to rebase over a rustup and then wait hours for the build to work. This was a large part of my impetus to move servo to a state where we download Rust snapshots.

[1]: Btw, if LLVM compile times are getting to you, Use. Ccache. It is amazeballs.

Is LLVM that well supported on windows ? Go aims at running on as much platforms and it seems to me a lot of languages built with LLVM don't run on windows (Swift,Crystal,...).

LLVM works well on Windows and can even be built with Visual Studio.

There's an "official answer" in the FAQ [1] ("We considered using LLVM for gc but we felt it was too large and slow to meet our performance goals." Note: lowercase gc refers to Go compiler, whereas uppercase GC would refer to Garbage Collector). That said, I seem to recall other additional/more detailed reasons were given on various occasions too, including:

- ease of iteration and freedom to make huge breaking changes (and they did make use of it, see e.g. various generations of the GC, or the SSA work);

- thorough knowledge of the internals of the compiler they used (given they were it's authors; also this is linked to the reason I listed above);

- one of the explicit goals for the Go toolchain was that it must compile very fast (which I believe is also somewhat at odds with advanced optimizations, like those used in LLVM) - they even quipped something like "we designed Go while waiting for C++ to compile";

- additionally, though I'm not sure if it was ever spelled explicitly, I suppose they wouldn't want to get tied to the LLVM as a huge dependency, including having to adjust to each and every change in LLVM API, regardless if sensible or not (I seem to recall from so me articles that LLVM does introduce breaking changes in API from time to time?);

[1] https://golang.org/doc/faq#What_compiler_technology_is_used_...

> which I believe is also somewhat at odds with advanced optimizations, like those used in LLVM

You can configure the optimization level to 0, then only constant folding is performed when the IR is built, and nothing else is done.

Yes, GC is a big issue... or was back when Go was just getting started. GC support in LLVM should be MUCH better now. Ie. it has everything you need to hook up a GC in it, but there isn't a built-in GC in it.

And the fact that the first people working on Go have a good knowledge of the Plan9 toolchain probably gave them a head start. But that benefit has probably eroded long ago.

And I completely disagree with the Go team's emphasis on compile times. Fast result programs are far more important than fast compile times. Fast compile times are nice to have, but not much more than that. But this is just my opinion, it's as good as anyone else's.

Fast compile times let you use Go as a scripting language, which has been key to its adoption from the python/ruby community.

Fast compile times also let you run your test suite every time you hit ctrl + s.

Fast compile times also let you run tools like gomft without feeling like it is slowing you down.

I agree that fast programs are essential and (ideally) not mutually exclusive with fast compile times.

> I agree that fast programs are essential and (ideally) not mutually exclusive with fast compile times.

They are. It is always a tradeoff.

    Rust is working on doing it

That's interesting. Is this still MIR [1], or has this evolved? The MIR design document is from 2015.

[1] http://blog.rust-lang.org/2015/08/14/Next-year.html

Yes, there are no immediate plans for anything other than MIR at the imperative-semantic level (the compiler also uses HIR, which is mostly a desugared AST and not related to LLVM IR).

Currently, initial support for lowering MIR to LLVM IR is close to complete and it might be enabled in the next beta (or the one after that).

None of the analysis passes have started their transition to MIR, though (there is a well-typed check to catch bugs in MIR generation, but that's about it).

There's also talk of using MIR for compile-time (pure) function evaluation [1] and some out-of-tree experimentation with interpreting it [2].

[1] https://internals.rust-lang.org/t/mir-constant-evaluation/31...

[2] https://github.com/tsion/miri

Thanks.

MIR looks a bit more low-level than Haskell's Core. Like Core, MIR is typed, but unlike Core, match statements disappear. This is interesting, because matching is really the main computational engine of Core. I wonder if there's a good explanation why it was deemed advantageous to desugar match.

I also wonder if there are plans to integrate the MIR interpreter into the compiler. IIRC, interpretation of Core between optimisation phases is used to good effect in Haskell.

Depends what you mean by "match" statements: if you're referring to complex patterns, yes, they get desugared.

If you're instead referring to matching over ADT (enum) variants, that is a MIR primitive, the "Switch" terminator (there is also a "SwitchInt" for integer-like values, as in C or LLVM IR).

As for the interpreter, it's quite likely that we'll use (something like) it for evaluating constants, but not entirely certain atm.

I personally hope we can get the CTFE semantics I described (see [1] above), which despite being pure, go far beyond C++17 constexpr capabilities (e.g. you could potentially run an entire compiler for a different language at compile-time).

Aha, I had overlooked the switch stuff, so yes, it's like Core.

I imagine that if Rust plugs in full CTFE then a lot of compiler optimisations can be written at the MIR level, which should simplify the compiler.

We don't really have our own optimizations atm, but we do want MIR optimization passes.

The benefits would be two-fold:

We could do transformations LLVM can't figure out itself, like NVRO: `fn bar() -> T {let mut x = ...; foo(&mut x); x} ... box bar()` can (theoretically) end up calling `foo` with a pointer to the heap instead of having to copy `x` from the stack later.

And we can lift the burden of LLVM trudging through monomorphized instances from MIR: since MIR still has type parameters, you can transform it and simplify the resulting LLVM IR for all instances, e.g.:

mem::replace(mut_ref, x) is {mem::swap(mut_ref, &mut x); x} which can be reduced once to {Return = * arg0; * arg0 = arg1;} in MIR and translated to a load, a store and a ret (for immediates) or two memcpy's (for indirect argument & return), depending on the type.

As most of the time rustc spends is in LLVM optimizations, this will result in compilation time speedups linear in the number of instances, sometimes exponential in the size of the original code.

All true, but there is more. SPJ and S Marlow [1] list the following additional advantages of using a typed intermediate representation, which would/could apply to MIR too.

1. Running a type-checker on the IR "is a very powerful consistency check on the compiler itself. Imagine that you write an 'optimisation; that accidentally generates code that treats an integer value as a function, and tries to call it. The chances are that the program will segmentation fault, or fail at runtime in a bizarre way. Tracing a seg-fault back to the particular optimisation pass that broke the program is a long road. Now imagine instead that we run [the type-checker on the IR] after every optimisation pass: it will report a precisely located error immediately after the offending optimisation. What a blessing [...] in practice we have found that it is surprisingly hard to accidentally write optimisations that are type-correct but not semantically correct."

2. Running a type-checker after translation to IR serves as a "100% independent check on the type inference engine".

3. A high-level typed IR is a "[s]anity check on the design of the source language."

All quotes from [1].

[1] S. Marlow, S. Peyton-Jones, The Glasgow Haskell Compiler. http://www.aosabook.org/en/ghc.html

That's what the well-typed check I mentioned before is, see https://github.com/rust-lang/rust/pull/31474

> I should also mention that increasingly it's become popular to have a mid-level IR that you lower the AST to before lowering to LLVM IR.

I would say that is just mainstream compiler development catching up with how mainframes work.

The idea of using some form of IL that gets JIT or AOT compiled goes back to the mainframe years.

IBM i (aka OS/400) and Unisys Libra (aka Burroughs) are probably the best examples still alive.

Hence why Apple, Google and Microsoft ideas of distributing IL instead of pure native code in their OSes, isn't actually that new.

Good point. Also, there is CoreCLR which is now open source and may compete with LLVM on some levels.

Reply on news.ycombinator.com