New SSA Back End for the Go Compiler (2015)
docs.google.com
docs.google.com
I think one could read too much into the "single-assignment" part of SSA. Sure, functional languages don't tend to rebind variables either, but that's really all SSA has in common with them.
I'm familiar with Appel's "SSA is a functional language" article, but the vibe I got was more than he was trying to build some bridges between the SSA and CPS camps to try to get some cross-pollination going and knowldge sharing between them.
I think he could have just as easily called it "CPS is an imperative language", but my hunch is the FP folks are more persnickety and wouldn't have swallowed that as easily as imperative folks would accept the other title.
CPS is typically used to handle imperative control structures by impure functional programming languages, so it should indeed be of interest to imperative compiler authors.
It seems as though C-like imperative languages and x86 are baked in forever... but the world is actually parallel.
By analogy, of course, I am suggesting that the Church model of computation might have served us better as a foundation than the Turing model has done, since it seems that everything's turning up lambdas as the technology S-curve for silicon computers continues to flatten out.
In contrast, the Church model doesn't really have any notion of time, so it's not clear how to reason about I/O. What evaluation order is used?
In terms of computation, they're of course equivalent, so you can execute the Church model on the Turing-like machines (or more specifically a Von Neumann architecture). So maybe that was the right "choice" (if there ever was one).
There was an entire movement around dataflow processors AND dataflow languages in the 80's, where the instruction sets were not totally ordered (e.g. SISAL was single assignment). But these didn't fare well in the market.
Closer to the ground, there is a pattern of "throwing away information at interfaces" in computing. Interfaces like x86, C, Unix, etc. get solidified by evolutionary forces. The cost of that modularity is global inefficiency.
Another good example of that is the Java code gen architecture. People say "static types in Java code let you generated better code!" Well, no. The Java compiler throws out all the type information, generating Java byte code, which is dynamically typed. Then the JIT takes the byte code and has to re-infer all the type invariants to generate machine code.
My understanding is that the dataflow architectures didn't fare well for technical reasons. The instruction-level parallelism they worked with turned out to be too fine-grained, i.e. the cost of scheduling was greater than the win of parallelism for many programs, especially normal sequential programs that still need to be fast. This led to research in coarse-grained dataflow, but it doesn't seem that much has come of that.
https://www.cs.ucf.edu/~dcm/Teaching/COT4810-Fall%202012/Lit...
It's a bit more thrilling to think of it that way, as a matter of scale. When space and time resources are scarce, thinking of the computer as a big piece of RAM that we mutate in-place makes the most sense. As we push upwards and outwards into enough resources and a bigger need for parallelism, it suddenly makes more sense to switch perspectives and reason in terms of binding and substitution.
You can see the same pattern with IO models. We have programming languages descended from 50s-era concepts of computing in which the program drives the machine, but that just isn't true at all. A computer is a passive machine, not an active one: it reacts when you poke it with an interrupt, until it reaches a steady state and settles down again. Operating systems go to a great deal of trouble to simulate the kind of top-down flow control environment our imperative tradition wants to think it is operating in, but in order to get any real performance out of these systems, we all end up building asynchronous, reactive layers on top of the simulated batch-job anyway.
We'd all be better off if we flipped the paradigm, imagining the process of building a program not in terms of writing instructions for the computer to perform, but in terms of creating a structure which will react appropriately in response to whichever events may be brought to its attention.
Instead, we'll probably still be starting young programmers out with for-loops counting from 1 to 10 and printing the result on an imaginary console for decades to come, even though none of that is even remotely relevant to what's actually happening anymore, and once they've crossed that hurdle they'll promptly begin unlearning all that stuff in order to start getting real work done.
On an unrelated note, I spent a while last fall/winter playing around with the idea of a very low level functional language - could we use these techniques in memory-constrained environments too? I didn't find the model I was looking for, but I think it's probably out there, and it would be very interesting to develop a functional/type-safe/immutable language suitable for microcontroller programming, with no garbage collection or implicit allocation. It may be that the Turing model is a better fit for computing in the small, but I suspect that we may find dataflow and functional composition to be useful at all scales. That way of looking at the world has some profound philosophical strength, after all - "you cannot step twice into the same river" and all that.
Wait another month and a half and I'll be getting around to writing my blog post in support of VLIW, and why previous attempts have failed miserably.
We'll have actual hardware development/evaluation kits available this fall, so feel free to contact us or sign up for our mailing list to be alerted when we release details on all of that. As I said in a previous post here, I strongly believe that most people do not care about something that they can not physically touch, so I expect that most developers would much rather start to learn about and work on an architecture that actually has silicon available.
Another problem with Mill is that they have been around for a little over 10 years, and have not released anything publicly (though have given a number of very detailed talks). They have had a lot of trouble getting their design into FPGAs, and even more trouble with having working compilers. When I started REX, I believed in getting it into silicon as fast as possible, as that is the point when people would take us seriously. We closed funding in July of 2015, and are taping out our first silicon next month... While many have called us crazy (and we will be giving real information on why we are not that crazy), I definitely don't want to be called vaporware.
At least for myself and my computer architecture friends/colleagues, most of us just throw Mill into the stack machine box even if it is not entirely true... the benefits of the Belt architecture over the traditional stack machine are there in concept, but Mill has also not released any real concrete information on their compilers (at least from what I have seen).
It doesn't matter how it's structured, just that it's faster.
SSA is fairly well studied, there are many algorithms to transform an IR into SSA and also lots of algorithms for optimizing programs in SSA form.
A common question that comes up is “why not just convert to the IR of {llvm,gcc,...} and go from there?” I think there are 3 major reasons:
- Compiler speed. I intend our SSA IR, and the optimizer passes implemented on top of that IR, to be fast by design. We’ll aim for linear-time algorithms wherever possible. The backends of other possible compilers weren’t really designed with fast compile speed in mind.
- Runtime information. The runtime needs accurate maps of stack frames for both GC and stack copying, something that is not available from standard backends today.
- An additional dependence. Do we want a {llvm,gcc,...} backend as a prerequisite for building Go? (Note that this would only be an issue for those developing Go, not those writing Go programs.)
I’m happy to be convinced otherwise - maybe we should throw our effort into getting frame maps out of {llvm,gcc,...} and figuring out how to configure the backend (e.g. which optimizations to turn on) to make it compile quickly.
1. LLVM's SSA based compiler currently uses more linear time algorithms than Go's SSA backend (IE phi placement, etc), and in more places. So yeah. While parts of LLVM definitely could be sped up (particularly the backend), it was originally designed with fast compile speed in mind, just like go! Given how many years it's taken so far, you easily could have gotten the same thing out of LLVM. Would it have been more work? Probably, but not much. Are the other reasons not to do it? Yes. But the idea that their compiler is somehow the only one designed with fast compile time in mind is, honestly, pretty arrogant
2. Stack maps have been supported for quite a while, and statepoint support now exists and is used by real people in real places.
But i'll also just point out he's never actually asked, or talked to the LLVM folks about it (search the mailing list, see if you can find any mail about it).
Note: I honestly don't care whether they write their own compiler or not. I suspect it's better for them to do it because of the community they want to build, because of how much control they want over their toolchain, etc.
But i'm not a fan of saying "someone else's infrastructure sucks, so we are doing it", when
1. That's not the real reason as far as i can tell
2. People are using, in production, the very things they claim don't exist (and they've been told this, it turns out)
3. Answers about linear time algorithms are honestly just BS.
Of course, there is also gccgo and llgo, so once the SSA backend is in stable Go, useful comparisons can be made.
languages that have their own tools built with themselves are cool... but it has zero practical value imo. the number of C/C++ programmers interested in Go and capable of contributing meaningfully far outweighs the number of programmers who do not know C/C++ and are interested in Go
I think it's a matter of tradeoffs. LLVM has multiple IRs on the way to machine code, some quite large, which let it emit pretty good output, on par with gcc. But other designs are possible that avoid a lot of that overhead, and can be far faster than LLVM, like JS VMs, B3 [1] and SubZero [2]. And clang is overall more or less comparable with gcc these days in terms of speed, it's no longer clearly faster [3] (although that also takes into account the frontend).
With all that said, I agree with you that making such a decision without talking to LLVM is a little silly. But, I doubt it would change the outcome: If Go wants fast compile times, has the resources to write its own compiler, and is ok with trading off throughput for compile time, then it's a reasonable decision to avoid LLVM.
[1] https://webkit.org/blog/5852/introducing-the-b3-jit-compiler...
[2] https://github.com/stichnot/subzero
[3] http://hubicka.blogspot.com/2016/03/building-libreoffice-wit...
[1] Well, OK, I'm not a fan of SelectionDAGISel's interpreter. But switching that to AOT won't result in huge differences in compile times. (Note that it's been a couple of years since I really worked with LLVM closely.)
Of course, some tradeoffs are made, but actually I don't see why they substantially limit B3's output code quality. Perhaps slightly, but in return for a massive speedup in compilation times.
But this proves the overall point: B3 is able to specifically say "we are going to be faster than LLVM because we are replacing RAUW with identities, packing multiple operands into an Inst, fusing operations into macro-ops, using arrays instead of linked lists, etc." Those are specific technical decisions that the WebKit authors believe will make things faster than LLVM, and they aren't based on misunderstandings of the things that LLVM provides.
Edit: That said, there's skepticism that B3's advantages will persist in the long term. See: https://news.ycombinator.com/item?id=11107082 and http://lists.llvm.org/pipermail/llvm-dev/2016-February/09546...
In theory, LLVM might support both a very fast compilation model and a slower and more efficient one. But supporting two complete codegen backends is a lot more effort.
And overall, codegen compilation speed has never been a priority for LLVM to anywhere near the extent that it is for JS VMs. It still doesn't have parallel codegen, while all JS VMs do. That shows the very different focuses on those projects.
Actually, it can be done. It's just not the default.
It's more "nobody has had the time to erase this particular technical debt yet". Chandler, for example, is focused on erasing the debt of the old pass manager first. The B3 guys, had they focused on doing this in llvm instead of writing a new JIT + new passes + .... probably could have done that in less time.
But at this point, there are concrete plans to erase it, so as you suggest, it is highly unlikely advantages will persist in the long term :)
The B3 JIT link describes things that LLVM plans on doing in the next year, precisely for these reasons, so ...
Had they emailed the list, ever, they would have known this.
It's not like these were design decisions that someone said "we should never change these", they were design decisions that were good at the time, but like anything else, need to grow and change over time.
If you give up and rewrite an entire jit/compiler every time it might require rearchitecting, that may be fun but it doesn't make a lot of progress. You will spend years to get to a no-regressions vs old compiler state (unless your old compiler was truly bad)
LLVM based toolchains compile hairy native code faster than any other tools i've seen... GCC, MS, Intel compilers for C/C++ are all very slow by comparison and the benefits are marginal (but still valuable).
for JIT or dynamic stuff LLVM is a poor fit. it doesn't surprise me that JS VMs do better with JS than LLVM, because there is no actual compilation involved as such - its a completely different class of problem, and its just not designed for that kind of language and environment, which is highly derivative, dynamically late binding and built in many layers, the vast majority of which are themselves compiled with C/C++ toolchains like Clang/LLVM, GCC or the MS compiler from necessity...
quoting that first article you link: "it isn’t specifically designed for the optimization challenges of dynamic languages like JavaScript."
[1] http://lists.llvm.org/pipermail/llvm-dev/2015-July/087832.ht...
If Go adds all the optimizations that LLVM does, then I have no reason to believe that it won't end up just as slow as LLVM.
There's active work to fix both (a) and (b): for (a) there are ideas for an O(1) unifier in typechecking, and for (b) we're working on MIR (which is now able to self-host) to do higher-level optimizations on a language-specific IR to avoid punting them to LLVM, where it may take more work to figure out. (For instance, we can do inlining on polymorphic functions, reducing the time complexity from O(number of instantiations) to O(1).) But the biggest wins will come from incremental compilation, which there's been a ton of progress on lately and might just fix the compilation time issues once and for all in practice.
So my non-expert, just-a-normal-programmer feeling is something still doesn't add up -- I feel like you could compile C++ with optimizations off, and it would still lose at compile time, and really lose at runtime, to Go.
So somehow Go is compiling quickly and running fastishly.
So "it doesn't do optimization is why it compiles fast" is confusing.
Is the story that Go, as a simpler language, is able to compile to decently fast code w/ fewer compiler optimizations?
I'm thinking along the lines of C++ zero-runtime-overhead template stuff is very-large-overhead w/o optimizations.
I've only played a tiny bit with Rust, and it was a long time ago, but my experience is there was no "fast compile time, decent runtime" configuration available. Naturally, that's a really good configuration to have accessible if possible!
Go's compiler is not competitive with a mature backend like GCC or LLVM. It's "fastish" for the niche it's in, but there's no substitute for the nonstop 10+ years of optimization work that has gone into the flagship open source compilers. I don't see LICM in Go's source at all, for instance, and that's a really basic one.
> I've only played a tiny bit with Rust, and it was a long time ago, but my experience is there was no "fast compile time, decent runtime" configuration available. Naturally, that's a really good configuration to have accessible if possible!
There is -O1, but it has basically the same compile time as -O2, so it's not used in practice.
I guess complex is an ambiguous word. Let's just agree that template-heavy "modern" C++ needs more optimizations turned on to get decent performance. So more optimizations => longer compiler times. (Not to even mention all of the parsing the headers multiple times, plus generating multiple versions of the code for all of the various type specializations!)
From the other replies, I feel like there's more to it than just optimizations though -- but as just a compiler-user, not a compiler-writer, I'm out of my depth and just reading tea leaves. :)
Reading those tea leaves, I'll be sadly surprised if the Go compiler ends up slow and happily surprised if a C++ compiler ever ends up as fast.
(I don't know enough about Rust to make any predictions. ;)
(PS. No disagreement that C++ has a higher performance ceiling than Go; of course hand-rolled asm still goes higher than that (ever tried running x264 w/o the assembly bits? it's painfully slow).)
Sort of. But it's also that you're making bad comparisons. C++ has an include based compilation model and heavy reliance on template specialisation that means it'll never be fast.
What you should instead be comparing it to is Java, which is also a simple language, only slightly more complex than Go. However, that comparison is rarely made, because it'd show that compiling fast is not so special a trick ... Java also compiles extremely fast at every level, that's why it's possible to use a JIT compiler with it at all.
Given that "compiles fast" is Go's number one claim to fame, the reluctance to compare to the most popular compiled language is the elephant in the room.
The only elephant in the room is the bloated, insecure platform sitting on many servers. Competition showed one could do much more with less CPU, memory, or money invested in tooling itself.
Few people are as consistently right in their field as Cliff Click is with JITs and language runtimes.
Yes, Pascal/Delphi also compiles very fast, it's true, but they also forbid circular dependencies and impose other restrictions that caused a lot of developer pain.
1. Interpreted vs compiled language.
2. Simple, Oberon-like type checks vs Rust or Ada.
3. Several pages of BNF in grammar vs 1 or 2.
4. Designed for abstract, heap machine or just above real, stack machine?
5. Number of steps needed between source and efficient exdcution.
6. Number of times you perform those steps (eg AOT vs JIT).
7. Cache-awareness of design.
These are a few key differences between Java and Wirth-style languages then. They made compiles rapid on P3. Updating to multicore or 64-bit would be trivial given each update at ETH was a few undergrads work for 6mo-2yr. So, do lessons learned that those attributes Wirth-style greatly aid performance of compilers and runtime still apply today?
I think so given what Go accomplished in its time and resources. Other languages too with design decisions that proved out over time. It took truly epic work and investment to get Java to its current situation.
I havent heard people say Pascal caused them lots of pain aside from functional crowd or some wanting a few C++ features. What specifics bothered you? And why did you need circular dependencies?
https://github.com/rust-lang/rfcs/blob/master/text/1298-incr...
Now, the only thing left is a real-time interpreter with live code updates. I recall the LISP box could do instant changes interpreted for exploratory stuff on running image. Solidify that super fast with per-function, typed compiles. Plus do whole program compiles if you had to. So yall getting close but what's odds of those other features happening?
Note: Live, interpreted image with save the world also makes it easier to debug stuff locslly and remotely. Send devs the whole, running state.
Personally, I would love to see this as part of an IDE that can execute _parts_ of a Rust file with various inputs to quickly see if a function behaves as expected (this could also be easily converted into test cases.)
Rapid development cycle doing features this way.
2) Since we are talking order of magnitude more time, Will optimized code from LLVM will be order of magnitude faster than Go?
It depends on the language. It would be interesting to see -O0 LLVM vs. 6g/8g on Go code.
> 2) Since we are talking order of magnitude more time, Will optimized code from LLVM will be order of magnitude faster than Go?
Maybe? If you vectorize it sure could be. But I don't see why it's relevant. Who cares if your final release builds for your browser are 10x slower if you're shipping them to 100 million users and they get a 3x speedup?
I guess you will agree business applications are far more commonly written than browser engines. For my business application in Java it is neither super fast to compile (~20sec from ant script). Quite slow to start due to VM startup time, and ok performance. I would really like if compile times are much faster.
Remember the SSA backend of Go was slower than the normal go compiler for the vast majority of it's life as well.
In any case, people like to build shiny new things they think they can do better at, instead of fixing things that are, in actuality, probably better for what they want but need a little work.
The truth is that there is no magic in building good compilers, so it's not like anyone comes along, waves a wand, and produces a compiler that is X times faster or better than anyone else's.
I can think of a lot of good reasons to write their compiler in go, and not use LLVM. Technical reasons are ... not any of them :)
Go 1.7 in August will be first release with SSA backend. So I do not understand what is that vast majority of life besides development phase of 1 year or so.
> In any case, people like to build shiny new things they think they can do better at, instead of fixing things that are, in actuality, probably better for what they want but need a little work.
I agree with that. It could just be a comment on our society.
> I can think of a lot of good reasons to write their compiler in go, and not use LLVM. Technical reasons are ... not any of them :)
I think goroutine and segmented stacks support was mentioned as technical reason.
DannyBee addressed most of these points, however I just wanted to note that even if LLVM didn't provide stack maps, it's easy to recover stack information using lazy pointer stacks [1]
[1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.158....
This doesn't sound very exciting.
Those compilers are at least 16 years old so Pike and Thompson aren't as incompetent as you think them to be.