The IR design, type checking, and pre-optimizing

[NalaGinrut]

The current Rust compiler contains two IRs before GENERIC:

• HIR for type-checking
• MIR for borrow-checking and some pre-optimizing.

My previous experiences are more about functional programming language's compiler. That's relatively easier for coding, since there's pattern matching, and there're fewer side-effects (or even no) so that the optimizing is pretty easy: find the correct pattern, and inline the function or closure, then execute the rewriting rules. This process can cover many common optimizing, say, constant-fold, dead-variable-elimination, and dead-function-elimination, etc. For Rust, I think they're doing similar rewriting, but I need more researches.

The Rust compiler is written in Rust, so there's pattern matching. I guess we have to write more code for the tree node matching. After all, pattern matching is just syntax sugar, which expands more code that we have to write in C++.

I'm not sure if we can follow the exact design of HIR and MIR, since C++ may not be possible to cover the expressiveness exactly so that it's better to design a similar IR for taking advantage of C++ features. I'm just guessing, and I need more researches for the conclusion.

So I think the plan could be:

• Implementing HIR according to Rust's design
• Type-checking in HIR
• Implementing MIR
• HIR->MIR
• Borrow-checking
• Other pre-optimizing
• MIR->GENERIC

That's a rough plan, there're more things, including memory management, library interfaces, exceptions handling, etc. But I'm not sure where to put them in the pipeline. So I just listed them.

Comments?

[philberty]

We have HIR with @SimplyTheOther AST classes which are very expressive to do all the resolution and static analysis we need. That ticks off the top 3.

HIR->MIR i think for now using the Backend.h wrapper over GENERIC gcc tree's will work. I am not concerned about extra optimizations at this stage but there is the borrow checking and gccgro does its own escape analysis at this level so we will have to do that too.

I just want to avoid any other IR's because i think the AST and the Backened IR is enough for the front-end at least for now.

[NalaGinrut]

OK, then we may change the first item to "name resolution".
Do you mean we do the borrow-checking and escape-analysis in GENERIC tree? I've no idea if it's good enough for us, but we can try.

[philberty]

My only thing is that when we bring things down to the Backend abstraction GENERIC although thats what we feed GCC to get output i think we get alot of similar concepts as MIR not quite the same its still fairly high level but i would rather get this first project out of the way then look at it again where it could very well fit in to have another IR.

[NalaGinrut]

Agreed.

[SimplyTheOther]

According to the rustc dev guide and associated links, rustc used to have AST-based borrow-checking (and presumably type checking since it comes before borrow-checking), but they abandoned that approach due to difficulties with implementation (and for the borrow-checker, to allow "non-lexical lifetime" borrow checking, but that may not be a problem at this point with no borrow checker).

For now though, without complex features like borrow checking, I think the AST for IR alone could suffice (though it may make some things difficult).

[NalaGinrut]

@philberty @SimplyTheOther OK, let's try to do all the things with AST, if we found something too difficult, that's even better for us if we have to introduce special IR later.

[philberty]

I've been considering a lot of what @bjorn3 mentioned about the end architecture for the compiler. Working with the AST for now in theory we could squeeze out GIMPLE but i fear the compiler could be hard to maintain at that point in terms of generating all the glue necessary for everything to work correctly without having MIR.

Even at the moment doing type resolution using the AST i have butchered some of the AST classes with extra fields to have the data we need and created duplicated scope classes for lookups. I am starting to look at implementing HIR which does seem to map very closely to what the AST looks like post type resolution right now. It would also help clean the code up a lot and create a common reference point.

[bjorn3]

Rustc does translation to HIR before typechecking. It stores the typecheck results in a side-table (or rather query result) as the HIR is immutable.

[philberty]

We are loosely following the rustc pipeline:

The only missing piece is MIR, the abstraction over GCC GENERIC is very similar to mir and we may not need MIR.