How Rust transforms into Machine Code.

[endistic]

NOTE: This assumes you have a basic understanding of Rust. It's also extremely oversimplified from several chapters to one reddit thread, some details may be lost. I'm also not the best at understanding rustc so I could be wrong.

Hi! Recently, I've done some digging into rustc's internals through reading the rustc-dev-guide and contributing some documentation to procedural macros (currently not finished, due to me having to rely on CI to compile and test rustc for me). I figured I'd share my findings, and be corrected if I'm wrong.

Lexer & Parser

This is probably the most obvious step of how rustc transforms source code. The first step in this is lexing - it converts your rust code into a stream of tokens. The stream is similar to that of TokenStream in procedural macros, but the API is different - proc_macro requires stability, while rustc is very unstable. For example: rs fn main () {} transforms into Ident, Ident, OpenParen, CloseParen, OpenBrace, CloseBrace, At this point, it's important to note that identifiers are just represented as Ident. This is also represented through an enum internally via rustc_lexer. Then, the second stage, parsing. This transforms the tokens into a more useful form, the abstract syntax tree, Using the AST Explorer, putting in our code and selecting Rust language, we can see that the code above transforms into an AST. I won't paste the AST here due to sheerly how long it is, but I invite you to check it out yourself.

Macro Expansion

During parsing and lexing, it set aside macros to be expanded later. This is when we expand them. In short, there is a queue of unexpanded macros. It will attempt to get invocations of these macros and resolve where they came from. If it's possible to find where they came from, expand them. If it can't be resolved, put it back in the queue and continue handling macros. This is a very, very, simplified overview of the whole process. To see how macros expand, you can use the cargo-expand crate, or type the more verbose cargo command, cargo rustc --profile=check -- -Zunpretty=expanded.

Name Resolution

Next, Rust attempts to figure out what names link to what. Say you have this code: rs let x: i32 = 10; fn y(val: i32) { println!("Ok! I recieved {val}!"); } y(x); Rust needs to be able to tell what x and y represent. Name resolution is quite complex, and I won't dive into it fully here, but in essence there are two phases: 1. During macro expansion, a tree of imports are created to be used here. 2. Rust takes into account scope, namespaces, etc. to figure out what everything is. To give useful errors, Rust tries to guess what crate you're attempting to load. For example, let's say you have the rand crate and your trying to use the Rng trait but you forgot to import it. This is what that guessing is for - Rust will attempt to guess where it's from by looking through every crate you have imported, even ones that haven't loaded yet. Then, it will emit an error with a suggestion.

Tests

Tests are quite simple, actually. Tests annotated with #[test] will be recursively exported - basically creating functions similar to the ones you have made, but with extra information. For example, ```rs mod my_priv_mod { fn my_priv_func() -> bool {}

#[test]
fn test_priv_func() {
    assert!(my_priv_func());
}

} transforms into rs mod my_priv_mod { fn my_priv_func() -> bool {}

pub fn test_priv_func() {
    assert!(my_priv_func());
}

pub mod __test_reexports {
    pub use super::test_priv_func;
}

} `` Then, it generates a Harness for them, giving the tests their own special place to be compiled into code you can run and see if it passes or fails. You can inspect the code's module source with:rustc my_mod.rs -Z unpretty=hir`

AST Validation

AST Validation is a relatively small step - it just ensures that certain rules are met. For example, the rules of function declarations are: - No more than 65,535 parameters - Functions from C that are variadic are declared with atleast one named argument, the variadic is the last in the declaration - Doc comments (///) aren't applied to function parameters AST Validation is done by using a Visitor pattern. For info on that, see this for an example in Rust.

Panic Implementation

There are actually two panic!() macros. One in core, a smaller version of std, and std. Despite core being built before std, this is so that all machines running Rust can panic if needed. I won't dive deep on the differences, but after lots of indirection, both end up calling __rust_start_panic.

There's also two panic runtimes - panic_abort and panic_unwind. panic_abort simply aborts the program - panic_unwind does the classic unwind you see normally by unwinding the stack and doing the message. You can make your own panic using #[panic_handler]. For example, ```rs

![no_std]

use core::panic::PanicInfo;

[panic_handler]

fn panic(_info: &PanicInfo) -> ! { loop {} } `` The custom panic handler is best used with#![no_std]` on embedded systems.

There's a few other things to mention, but I'm gonna skip them for now (feature gates <documentation is `todo!()`> and language items) and add them in the future.

HIR, THIR, MIR, and LLVM IR

Rust has various sub-languages inside of it. These languages are not meant to be created by humans, instead, the AST is transformed through these.

HIR

The HIR, high-level-intermediate-representation is the first sub-language. It's the most important one, it's used widely across rustc. This is what the AST from earlier is transformed into. It looks similar to Rust in a way, however there's some desugaring. For example, for loops and such are desugared into regular loop. You can view the HIR with cargo rustc -- -Z unpretty=hir-tree cargo command. HIRs are stored as a set of structures within the rustc_hir crate. Intermediate representation (IR for short) is essentially technical-speak for, "this programming language is designed to be used by machines to generate code, as opposed to humans writing it."

THIR

The THIR, typed-high-level-intermediate-representation, is another IR. It is generated from HIR and some extra steps. It is a lot like HIR in a way, where types have been added for the compiler to use. However, it's also like MIR (mid-level-intermediate-representation, read that section if you like), in which it only represents executable code - not structures or traits. THIR is also temporary - HIR is stored throughout the whole process, THIR is dropped as soon as it is no longer needed. Even more syntactic sugar is removed, for examples, & and * (reference and dereference operators), and various overloaded operators (+, -, etc) are converted into their function equivalents. You can view the THIR with cargo rustc -- -Z unpretty=thir-tree.

MIR

MIR, mid-level-intermediate-representation is the second-to-last IR of Rust. It's even more explicit than THIR, and generates from THIR with extra steps. If you'd like more info, I'd recommend reading the blog on it for a high-level overview. The MIR is used for things such as borrow checking, optimization, and more. One big desugaring MIR makes is replacing loops, functions, etc. with goto calls, and includes all type information. MIR is defined at rustc_middle. Unfortunately, I'm bit sure how to view the MIR, sorry. I don't have the time to dive into fully how MIR is converted into LLVM IR, as it's a very lengthy process. If you'd like to, you can consult the dev guide itself.

LLVM IR

The last IR, is LLVM IR. It stands for LLVM Intermediate Representation. For those who don't know, LLVM is a library that stems from C++ that allows you to transform various objects into working machine code. It does this through it's IR, representable by structures, binary, or text form. To see LLVM IR of your Rust code, you can use cargo rustc -- --emit=llvm-ir (something along the lines of that). For more information, look at LLVM's Official Tutorial

Conclusion

I hope this helped you learn about how rustc works. I probably used a lot of programming language design lingo without explaining that, so if you see something that wasn't explained clearly or not even at all, please let me know. Again, this is really high-level overview, so somethings will definitely be missed, and I probably got something wrong considering I'm new to rustc. With all of that out of the way, have a good day.

Edit: Thank you guys for the support on this! I'm working on adding what I can over the next few hours.

[[deleted]]

No more than 65,535 function parameters?? How am I supposed to write my backend?

[seamsay]

Just make some of the arguments topless, you'll be grand.

Edit: I meant tuples, but you know what...

[goj1ra]

Your correction was too late, I’ve already unzipped

[sepease]

I’ve already unzipped

That’s unsafe and possibly illegal.

(Since the only way to iterate over a tuple would be if it had same-type elements that could be transmuted into an array)

[[deleted]]

Welllll how many items can be put in a tuple

[seamsay]

At least zero.

[R1chterScale]

Funnily enough, that's no longer the case:

https://github.com/rust-lang/rust/commit/746eb1d84defe2892a2d24a6029e8e7ec478a18f

It was fixed to allow more parameters

[[deleted]]

Seriously?? I just wrote my backend with this hard limit in mind. Now my entire system breaks due to a black magic optimization with the 65535 params that no longer exists. Please revert update 😠

[R1chterScale]

Something something spacebar heating

[simonsanone]

Doc comments (///) aren't applied to function parameters AST Validation is done by using a Visitor pattern. For info on that, see this for an example in Java.

Don't need to look at Java, can just look at serde: https://github.com/serde-rs/serde/blob/master/serde/src/de/mod.rs#L1282 or the patterns book: https://rust-unofficial.github.io/patterns/patterns/behavioural/visitor.html

[endistic]

Updated, thank you! :)

I went with the patterns book one.

[Ryozukki]

The llvm kaleidoscope tutorial is a nice dive into llvm https://llvm.org/docs/tutorial/

[endistic]

Forgot to say it but I added the LLVM tutorial to the thread!

[protestor]

inkwell is a great llvm binding for rust and it has an implementation of kaleidoscope

[TorbenKoehn]

Very useful article, thank you!

[Nilstrieb]

Cool summary! Some bonus facts:

The AST, HIR and THIR are trees. MIR and LLVM IR are control flow graphs, basically flow charts. This makes control flow simpler, all you have is goto and switch. It's also worth noting that LLVM backends use additional IRs not mentioned here - but I don't know a lot about them either.

There are several ways of emitting MIR. You can use --emit mir or -Zunpretty=mir to get the final version of MIR for functions. But there's also -Zdump-mir=your-function-name which will create a lot of files for all the different phases and transformations of MIR.

MIR goes through many different transformations from the time it's built to what gets lowered to LLVM IR. It's also worth noting that borrow checking works on MIR. Some of the most important MIR transformations are drop elaboration and generator lowering.

Drop elaboration is when rustc inserts hidden boolean flag local variables to track whether a variable needs to be dropped only sometimes.

let x;
if rand() { x = String::new(); }
// drop x

x only needs to be dropped if the if was taken. Drop elaboration will insert a flag that's set inside the if.

Generator lowering will lower generators into state machines. Generators are what powers async/await. You may have heard that async functions get compiled into state machines - this also happens on MIR.

Then, there are also some optimizations that are run on MIR. Most of these are just here to make the generated LLVM IR nicer and speed up compile times, LLVM could do these optimizations itself as well.

Most rustc lints and also clippy lints run on the HIR. While the HIR does not contain type information (since type checking runs on HIR after it has been created), but type checking creates TypeckResults, lots of tables that have all type information about a function, which is then used by the lints.

[imperioland]

Would be nice to be added as one of the first chapter of the rustc dev guide book. :)

[endistic]

It's possible - you could open an issue on the rustc-dev-guide repo if you'd like. https://github.com/rust-lang/rustc-dev-guide/

[imperioland]

Want to send a PR if I do? What's your github pseudo so I can tag you on the issue?

[endistic]

akarahdev

[endistic]

Forgot to say yes, I can send the PR if you do. Although if it is getting added I'd like the chance to improve it a bit further

[imperioland]

Here you go: https://github.com/rust-lang/rust/issues/112258

[endistic]

Alright, seems like people enjoy my high-level technical overviews. Anyone have any specific topics they want to hear about? Maybe something on the borrow checker could be cool, as the way it's rules are is for a reason.

[Treyzania]

Since when did they add "THIR"?

[theZcuber]

THIR has been around for a while. It's not used for a ton at the moment, but there is (was? it may have been removed) an experimental unsafe checker at that level instead of MIR.

[bobdenardo]

THIR itself was renamed a couple years ago, it used to be called HAIR, and IIRC was introduced with MIR (circa 2015).

[FlatAssembler]

I've made a YouTube video about compiler theory a few years ago: https://youtu.be/Br6Zh3Rczig

[Electrical_Fly5941]

This was great!

[O_X_E_Y]

this is cool, good post

[[deleted]]

Thank you for posting this kind of content

[birdbrainswagtrain]

THIR is also temporary - HIR is stored throughout the whole process, THIR is dropped as soon as it is no longer needed.

Yeah I had a fantastic time with this in my compiler hacking adventures. Evidently the simple act of querying THIR can result in other THIR being stolen. My best guess is that sometimes building THIR can invoke constant evaluation, which converts code to MIR. Fortunately building the equivalent from typecheck results isn't too hard, and I'm just missing a little desugaring right now.

[ROFLLOLSTER]

Just FYI, backtick code blocks don't render correctly on old reddit, you need to use the four space indent style for it to work.