Introducing MIR
blog.rust-lang.org
blog.rust-lang.org
It's also interesting that Swift, another LLVM-based project, has also transitioned to using their own language-specific intermediate representation (SIL). I think it's fascinating that, despite the availability of a robust and mature pluggable language backend, two professional languages independently decided that they needed another layer of abstraction between AST and LLVM IR. Not sure if this should be interpreted as a bug report against LLVM IR, or if it possibly represents a future trend in compiler design.
EDIT: I should also mention that MIR has been available on play.rust-lang.org for a while, if anyone would like to play with it in their browser: https://play.rust-lang.org/?gist=fee8ccf28bae2c89107d&versio...
What has changed are the boundaries. Traditionally, semantic analysis (including typechecking) operated on the parse tree, which resembled the human-written language extensively. Optimization operated on MIR, then it'd be lowered to an architecture-specific LIR via register allocation and instruction selection, and another round of optimization (instruction scheduling, etc.) would be applied. The purpose of all of this was to provide multiple language front-ends on top of a single compiler. In the 80s and 90s, compilers were often written by the hardware vendor, so they would tightly optimize the MIR and LIR for their own architecture, and use the parse-tree => MIR lowering to support multiple surface languages.
LLVM chose a LIR that's closer to what many compilers had been using as MIR, and then moved the optimization passes into the LIR, and hid the architecture-specific backends within the LLVM project itself, out of the eyes of language designers. It could do this because of open-source: with a shared body of compiler code owned by everyone and gradual consolidation of the hardware market, it became easier to contribute your backend to LLVM than to maintain your own compiler stack and fight for adoption. (GCC actually had a fairly similar architecture first, but the GCC IR was very difficult to comprehend if you weren't a GCC maintainer, which made it impractical as a compilation target for outside projects. They generated C code instead and let GCC compile it.) That in turn made it much easier to write a compiler and experiment with language design, since you only had to figure out how to translate your language to LLVM's IR rather than work out the details of scheduling and register allocation. That, in turn, allowed greater complexity in language features: Swift and Rust have language features that go beyond what cutting-edge research was <10 years ago, and do so in a production language that you can use now. And so it's not surprising that they're now re-introducing a MIR to manage the additional complexity introduced by the new language features.
[1] http://www.amazon.com/Advanced-Compiler-Design-Implementatio...
(upvote arrow) name xxx hours ago | parent | flag | (downvote arrow)
would make it less fat finger prone and still be pretty straightfoward to use (plus having downvote close to flag IMHO makes sense as well from a context perspective)
EDIT: great community, shitty website.
Such as?
And now Swift not only allows these in a way that's familiar to existing mainstream programmers, it interoperates fully with Objective-C and offers additional features like polymorphic literals. And when polymorphic literals (previously allowed only by Haskell, and then not with user-defined types) makes typechecking take 12 hours [5], it's widely decried for being poorly implemented.
On the Rust end - the whole concept of the borrow checker was borrowed (sorry) from Cyclone [6][7], a research language of the early 2000s. I remember seeing it occasionally pop up on Lambda: the Ultimate [8] around 2004-2005, people seemed intrigued, but few people really took notice. Rust's big accomplishment is to generalize this to an "industrial strength" programming language, figuring out all the corner cases around mutability, traits, move-semantics, boxes, etc. that you need for this to work in real programming.
[1] http://repository.cmu.edu/cgi/viewcontent.cgi?article=3059&c...
[2] http://research.microsoft.com/en-us/um/people/simonpj/Haskel...
[3] https://realworldocaml.org/v1/en/html/objects.html
[4] https://downloads.haskell.org/~ghc/latest/docs/html/users_gu...
[5] https://www.reddit.com/r/programming/comments/4givdg/go_home...
[6] http://www.bennetyee.org/ucsd-pages/Courses/cse227.w03/hando...
Not really. That's the lifetime system, which is not the same thing. "Existential Types for Imperative Languages", also by Dan Grossman, explains more of the motivation, but the borrow check is a hybrid of the two solutions he presents.
Borrowing itself is something with a long history, but the whole "unique loan paths" thing makes Rust's solution distinct from a lot of the stuff you find in the research literature.
It's more akin to C++ templates, where the type checker only has a bounded number of reductions it will do before it gives up. Aside from writing something that really is infinite and a limit of trillions of reductions - which wouldn't really be a useful program - it ends up as a type error as you'd expect. This also only happens with -XUndecidableInstances, which frankly isn't really one of the most common extensions, I'd say.
That said, in practice, most Haskell programmers seem to largely consider subtyping a misfeature anyway, and approximations of it elsewhere in the ecosystem use things like RankNTypes to give a 'feel' for subtyping where you can do things like "use any instance of a more general base type, in place of that type, right here". The infamous lens library does this to great effect.
> previously allowed only by Haskell, and then not with user-defined types
I don't know what you mean here - Haskell has, until recently, never allowed overloaded literals for certain syntactic forms, like lists. For the other cases, though, like numerics, you have always been able to have polymorphic literals, which can be instantiated to user-defined type. The most general type of `1` by itself with no defaulting is `1 :: Num a => a`, and there's certainly no problem with instantiating `a` to whatever user-defined type you have, providing it can sensibly be constructed from a base-10 decimal value (meaning, you have a function `toInteger :: Integer -> a`)
These days, lists are also syntactically overloadable by a similar convention, through value polymorphism/type classes.
Type inference in a OO language is still considered, if not impossible, at least very impractical. Swift, Scala and Rust avoid most algorithmic complexity and ambiguity by mostly supporting only type propagation instead of type inference, and thus require annotations on function parameters.
http://research.microsoft.com/en-us/um/people/moskal/pdf/msc...
In that regard, Apple and Microsoft do so much more to help developers improve their skill sets, given the programming languages and tools that they have brought into the market.
However, I do advocate Go for the use cases where developers still make use of C for user space applications, without any real need for C's low level features.
Also do believe that Go can actually be used for systems programming, even if not all scenarios from systems programming like for example, 8 and 16 bit embedded processors, can be covered.
The language is similar enough to Oberon and Limbo for it to be possible, just needs someone to write a bare metal runtime.
The parsing and type-checking produces a IR known as 'Core'. The middle-end optimizes it as a series of source-to-source transformations on Core code.
The back end of the compiler transforms Core code into an internal representation of a C dialect called C--, via yet another intermediate language STG (short for "Spineless Tagless G-machine").
Finally, the C-- code output can either be printed as C code for compilation with GCC, converted directly into native binary, or converted to LLVM virtual machine code for compilation with LLVM. Any output is linked against the Haskell runtime.
The innovation would come in creating the optimizations in the middle-end that could not be possible in the LLVM backend. Proof is in the pudding. Introducing another layer without any meaningful results is how projects bloat (NIH syndrome).
There is a LLVM backend that implements most if not all of the GHC "middle-end" optimizations[0] and should provide you with details/context you are seeking.
[0] http://blog.llvm.org/2010/05/glasgow-haskell-compiler-and-ll...
>There is a LLVM backend that implements most if not all of the GHC "middle-end" optimizations
I'm not sure I follow, are you saying that the optimisations are possible or not in LLVM? I don't think the LLVM optimisation passes can make guarantees such as is needed for (say) the rewrite rules that rely heavily on purity.
...There is one major issue remaining with the LLVM backend that I currently know of, its inability to implement a optimisation used by GHC called 'TABLES_NEXT_TO_CODE' (TNTC)...
The prologue support directly subsumes previous behavior (the `prefix` form) and is more flexible, and with it, GHC doesn't have to rely on shuffling assembly output in order to achieve TNTC.
There is still some inlining/smarts going on at the LLVM level, obviously, but it's nowhere near as aggressive as it is at the Core level in GHC. And obviously rewrite rules are user-definable - so they kick in much earlier. (As a side note, we actually spit out pretty optimized LLVM code from the C-- backend, in such a way that only some of LLVM's heaviest optimizations make a difference).
There are some specific optimizations that are simply not possible for LLVM in the general case and are better handled before conversion (for example, C-- at one point essentially gets CPS transformed in a way which LLVM cannot 'see through', and by that point you've lost the opportunity to do a number of simpler optimizations like basic constant propagation, while it's trivial to do earlier). But that's mostly the same in any compiler, and not unique to GHC...
"Faster execution time. You may have noticed that in the new compiler pipeline, optimization appears twice. That’s no accident: previously, the compiler relied solely on LLVM to perform optimizations, but with MIR, we can do some Rust-specific optimizations before ever hitting LLVM – or, for that matter, before monomorphizing code. Rust’s rich type system should provide fertile ground for going beyond LLVM’s optimizations."
LLVM is pretty low-level. It's a bit lower-level than C and has a very simple type system. It has no idea about unique pointers versus references, has no concept of borrowing, etc. I bet you could encode the necessary information for performing say borrow-checking into LLVM IR, but working with that would not necessarily be pleasant.
A good example of this is ARC optimization in Swift, which gets rid of unnecessary reference counting operations. That optimization operates on SIL, which has special instructions for reference counting. You could represent those instructions as magic intrinsics in LLVM IR, but you have no way of imposing any structural restrictions on how those intrinsics are used. Moreover, any pass which operated on LLVM IR to optimize uses of those intrinsics, would have to make deep assumptions about the semantics of those operations. Those assumptions, being Swift-specific, would mean the pass could not be used by other languages, which removes a lot of the benefit of making it an LLVM pass in the first place.
Some language rules and optimizations are easy to express in LLVM IR, but there are plenty that are not.
You could add metadata, but you'd probably have to extend how metadata works to support a bunch of things, and even then, the community would want metadata designs that multiple language frontends can use, not just yours.
Not sure what you're talking about here; what's wrong with negative indices in C?
int a[100];
int *p = &a[50];
a[0] = 666;
printf("%d\n", p[-50]);
(EDIT: formatting so HN doesn't misinterpret code point U+2A.)
See section 6.5.6, paragraph 8, of the ISO C standard, if you want the legalese. But this is pretty basic C that dates back to the beginning of the language.
If you implement a stack using an array and you track the top of stack by a pointer just past the last element, then you can index negatively into that pointer to access items on the stack:
// Create an empty stack.
int stack[100];
int* top = &stack;
// Push a couple of values.
*top++ = 123;
*top++ = 456;
// Peek the values.
printf("%d\n", top[-1]); // 456.
printf("%d\n", top[-2]); // 123.
printf("%d\n", *(top - 1)); // 456.
[1]: https://github.com/munificent/wren/blob/master/src/vm/wren_v...
Second, remember that even in C, you can't actually dereference things outside of the bounds of an object, even if you can form addresses to it.
In any case, the point was more than something like
struct foo C;
char *foo = &C
foo -= 7;
char whee = *foo;
fn handle_message(&mut self, find_node_query: messages::FindNodeQuery) {
let origin = node::UdpNode::deserialize(find_node_query.get_origin());
let target = Address::from_str(find_node_query.get_target());
{
// Borrow self.routing_table first time
let nodes: Vec<&Box<node::Node>> = self.routing_table.nearest_to(&target);
let response = Message::Response(
self.transaction_ids.generate(),
Response::FindNode(&self.self_node, nodes));
origin.send(response.serialize());
} // Done borrowing self.routing_table here
// Borrow self.routing_table again
self.routing_table.insert(origin);
}
For example, "do not create unecessary entities" maxim, which, it seems, is central for good language design (ML, Scheme, Haskell, Smalltalk, Erlang, Golang are small languages, the first three are even standardized). As long as we violate this genetal rule we end up in a mess like CL, C++, and of course Java as a peak of absurdity).
The meme that "implementation languages must be feature rich" does not hold beyond certain limits, and even Rust designers have realized that there must be certain restrictions. In fact, C - the oldest and most common implementation language is still alive and well (despite all the mess other people made of it since it left Bell Labs).
The best illustration I know is refusal of the Golang designers to complicate (to ruin the balance of simplicity and elegance with expressiveness, which is the most difficult to attain - every poet or artist will tell you that - to create an unbalanced pile of features is way easier) the language by adding generics in the language and runtime. For them interfaces (duck-typing) is good-enough).
"Explicit is better than implicit" is also a naively wrong maxim. Verbosity is bad. Period. Every good writer I know is non-verbose. Meaning behind words is what makes a good literature, not long words or elaborate passages half page long (ironically, common men think exactly opposite is true). Convention over configuration (evolved defaults instead of explicitly spelling every single rule over and over again) is the same notion from a different perspective.
Here comes Scheme - the greatest mostly-functional small language with balanced defaults, cohetent semantics (almost like in math), and unmatched expressiveness with almost no syntax at all (expressive power comes from coherent defaults that everything is an expression, everything (including lambdas) is a first-class value referenced by symbol, lexical scooping, very few standard special forms and the ability to create new ones.) as an good example. Smalltalk and Erlang are another ones for the emphasis on message passing and, in case of Erlang - pure functionality and isolation - the way vastly complex biological systems has been implemented by evolution.
So, those who have seen highly refined languages like Haskell or Scheme or Smalltalk would never be fooled by "features". The meme that "each project must first agree on which subset of C++ it would restrict itself to" is another good illustration. Rust, like Java, is already suffering from this kitchen sink syndrome, so the comment above is legitimate.
BTW, it seems that many of features should go from the language to sanitizers and checkers, like it is with clang tooling.
I could only repeat my question: How Common Lisp or even more pragmatic Golang are less safe? I am not asking about Haskell or Erlang.)
Compile time error for trying to use an old binding/reference? Is this memory safety?
Common Lisp and Golang use GC, which exacts a performance cost in some scenarios. Go also has highly dynamic semantics (e.g. with defer) which have unavoidable performance overhead, especially in an AOT compilation setting.
Good writing often allows (or even encourages) a reader to concoct their own inference of exactly what the author means. Witness discussions that last to this day of many ancient classics. Such ambiguity may be fine for writing, but it is obviously disastrous for large engineering projects.
That's fine - not all code is a large engineering project - but most of the people I know who work on very large code bases will take explicitness every time. And those are the kind of projects that Rust is aimed at tackling.
Actually, the language fells Rubysh - a bit of syntax from here and there. Swift has much more refined and concise syntax, because they paid way more attention to details.
Patter matching on type constructors could have been taken from Haskell - it won't hurt.
Block syntax with where clause (why?) is really bad.
The syntax inconsistency and awkwardness aren't major issues, but it is telling.
You say "explicitly passing self is lame" and then praise Golang for "feature restraint" when it does the exact same thing.
I don't know what "pattern matching on type constructors" means. You use the constructor syntax to pattern match in Rust.
There is no such thing as "block syntax with where clause". Where clauses go on signatures, not blocks. This is also the exact same syntax as Swift, which you praise for "more refined syntax".
The principles, rather idealistically, are outlined here:
http://karma-engineering.com/lab/wiki/Bootstraping
Pattern matching is technically almost unchanged since Standard ML, but in Haskell the syntax is refined by perfectionists (in best possible meaning of this word).
Swift, obviously, trying very hard to look familiar for [Objective-]C (but not Java) programmers, and to follow the principle of less astonishment, produced much more concise syntactic choices, and the devil is in the details.
BTW, if one wants to see another example of carefully crafted language, there is PLOT
Explicit passing of &self (or &mut self, or self) might be 'lame', but it also gives more clarity as to what the code is doing. I can't say it's ever once given me pause.
Rust would not work at all with the borrow check as a separate tool, by the way. It would be comically easy to write broken code.
fn handle_message(&mut self, find_node_query: messages::find_node_query) {
let origin = node::udp_node::deserialize(find_node_query.get_origin());
let target = address::from_str(find_node_query.get_target());
{
// Borrow self.routing_table first time
let nodes: vec<&box<node::node>> = self.routing_table.nearest_to(&target);
let response = message::response(
self.transaction_ids.generate(),
response::find_node(&self.self_node, nodes)
);
origin.send(response.serialize());
} // Done borrowing self.routing_table here
// Borrow self.routing_table again
self.routing_table.insert(origin);
}Here is example of compiler construction class: http://web.cs.ucla.edu/~palsberg/course/cs132/project.html
The mid languages were named after character in Winnie the Pooh, you can also see how factorial example looked in each stage.
Compilers have pretty much been the way (with the exception of GCC) since about 1975, if not earlier. :)
LLVM is deliberately low level. SWIFT uses a higher level IR because they want to do static analysis and language specific optimizations on it. This makes sense, LLVM's IR is not going to be good at that.
You could transmit metadata, but it's probably not a good architectural solution compared to progressive lowering of IR.
https://medium.com/@FredericJacobs/why-i-m-not-enabling-bitc...
[0] : "LLVM for a managed language: what we've learned" [1] : "Swift's High-Level IR: A Case Study of Complementing LLVM IR with Language-Specific Optimization" Both have slides and video here: http://llvm.org/devmtg/2015-10/
I also suspect that the act of designing a MIR for a language is a fun one, should be pretty damn enlightening. It really forces you to focus on what's "core" about the language.
In my own, limited, experience with language design and compilers, I've found that doing something like a MIR greatly simplifies other parts. Code written in MIR (in my case, it didn't even have a concrete syntax, just an abstract syntax tree) is full of duplication and is ridiculously explicit, but it's super easy to process in all kinds of ways.
Just plainly guessing, but based on this blog post, if I'd write a Rust interpreter, I'd probably run it on MIR and not on plain Rust or LLVM IR.
The reason that this could be really cool is that you could hypothetically hash these MIRs and store these hashes in a public database of open-source code. (You would have to include hashes of whatever functions they call/depend on, and you would have to solve foreign-function imports.)
Then you would have this cool language where modules are simply saying "here's a mapping of names to hashes in the public database," with automatic recognition of "hey, these two functions you're importing from these two modules are actually the same function, I don't need to disambiguate them." If your dependency graph isn't a tree and one of the branches can't cope with a dependency-upgrade, that's fine too -- you upgrade the dependency on the one branch only. The point is, all of your dependency-semantics are now reduced to a really straightforward reasoning about unique names.
Really want to "hash n cache" at all levels for best results.
Sounds similar to what Joe Armstrong described at the end of "The Mess We're In" (StrangeLoop 2014): https://www.youtube.com/watch?v=lKXe3HUG2l4
I'm wondering if MIR will make it possible to replace the backend IR. For instance, to use WebAssembly instead of LLVM IR.
Or is it still a better idea to base it off of LLVM?
However, in practice LLVM already has full support for sibling call optimization internally, so implementing such an optimization at the MIR level wouldn't really buy us anything over what we already have.
Nobody's tried implementing it recently, though.
I imagine LLVM is generating debug symbols from what it receives (which would be fairly representative of the original program).
Now with this extra step, won't LLVM generate debugging symbols for the MIR, which doesn't really map well to the original code (ie: LLVM won't know all those gotos were originally a loop)?
Avoiding branches, etc. in Rust doesn't mean LLVM won't add some as an optimization, which is frustrating to say the least. It would be awesome to be able to define a block - similar to "unsafe" - that tells the compiler to disable optimizations that could introduce non-constant time operations. When I started reading the article, I though maybe this new development would open the door to something like that, but it doesn't appear to be the case.
There's some work to do constant time ops in rust, but it's very experimental and untrustworthy. :/
Or do you have to pass the entire program at once to LLVM? Maybe the ability to disable optimizations only on certain functions is possible, idk, but I think it certainly would be nice.
[0] https://github.com/rust-lang/rust/issues/33205#issue-1509804...
Projects in Rust, like miri, hook directly into the compiler and use the datastructures as well, they don't parse the output you see here: https://github.com/tsion/miri/blob/master/src/bin/miri.rs
(The post has been amended to try to clear this up a bit)
I understand the desire to keep MIR private and avoid needing to stabilise a syntax and feature set for it, but there are benefits to doing so as well.
Surface syntax of the compiler IR isn't particularly important anyway.
If you are interested in more details, there was a talk two years about the compiler design: https://www.youtube.com/watch?v=osdeT-tWjzk (many type names and implementation details have changed since then, but conceptually it is still very applicable).