4 ms·

I’m in the early stages of working a compiler in Rust and haven’t gotten to the IR infrastructure yet. With Rust’s borrow checker, how can I make the IR graph s

by aarchi 5y ago

I’m in the early stages of working a compiler in Rust and haven’t gotten to the IR infrastructure yet. With Rust’s borrow checker, how can I make the IR graph safe, with its control flow preds and succs and data flow inputs that make it so there isn’t a clear owner for any node. How does rustc do this?

eddyb 5y ago
You could look at Cranelift, which I believe uses integer indices, and several datastructures for control-flow vs dataflow. There is no SSA IR in rustc itself (MIR, regrettably, only lowers control-flow, but uses variables instead of representing dataflow).
- jhgb 5y ago
  > which I believe uses integer indices So basically it sidesteps the type system issues in a similar way that an inconvenient car trip instead of taking a flight sidesteps the TSA issues? ;)
  - aarchi 5y ago
    Adjacency matrices would make ownership clear and solve the single-writer/multiple-reader issue because nodes wouldn't directly reference each other, but it keeps the exact same relationship between nodes, so any memory leaks are still possible (e.g. not cleaning up dead code because it is cyclic and appears to have references). If I'm going to defeat the type system, it seems like raw pointers would be easier.
weavie 5y ago
It looks like this project is using typed arenas a fair bit - https://github.com/SomewhatML/sml-compiler/blob/master/crates/sml-core/src/arenas.rs https://github.com/SomewhatML/sml-compiler/blob/master/crate... I don't know the details of how this is being used in the project, but it might be worth investigating.
brabel 5y ago
I struggled with this as well, and ended up making the lexer itself have a lifetime which is that of the full String read from a file, so that every token (and AST node) has the lifetime of the parsed file. I keep their indexes as well so that I can show error messages like rustc itself does (with code snippets and all) which would be hard to do if I didn't have the full source code text available. Hope that helps.
- amelius 5y ago
  This sounds a bit like cheating. What if you want to parse a really big file and delete the tokens as soon as you don't need them? If Rust claims to solve memory management, then we should not fool ourselves by allocating everything in a huge chunk which is then freed when the program ends.
  - steveklabnik 5y ago
    If this is cheating, many real compilers “cheat.” Heck, some of them famously don’t even free it when the program ends, leaving that up to the operating system!
    - amelius 5y ago
      The solution doesn't scale. The moment you need to deal with very large inputs, you will have to rewrite your entire application from scratch.
  - scns 5y ago
    I prolonged my own path many times in my life, by making things harder than they need to be. (edit) Aspirations acting as a anti-shortcut somehow.
  - brabel 5y ago
    That's why this was not my first choice... but it was just far too hard to implement it otherwise... and then again, once you really think about it, you must keep ALL tokens/AST nodes in memory to be able to analyse and type-check/lint any decent language... so keeping a big Sring in memory while all nodes just point to slices of it is not nearly as wasteful as it might appear at a first glance.
shpongled 5y ago
Author of the posted repo here! As another commenter posted, I used typed arenas quite a bit, it's not the most ergonomic way to do stuff, but it's quite performant and gets around the lifetime issues.
nybble41 5y ago
You may find this paper interesting: GhostCell: Separating Permissions from Data in Rust <https://plv.mpi-sws.org/rustbelt/ghostcell/paper.pdf https://plv.mpi-sws.org/rustbelt/ghostcell/paper.pdf> The essential idea is that you can use one of these "GhostCell" structures to assign a lifetime to a related collection of objects (such as the nodes in a graph), which allows the entire graph to be treated as if it had a single owner and a single lifetime rather than a separate owner and lifetime per node. The paper is relatively recent (2021), and GhostCell is not, so far as I am aware, used in rustc at this point.

by aarchi 5y ago

eddyb 5y ago

You could look at Cranelift, which I believe uses integer indices, and several datastructures for control-flow vs dataflow. There is no SSA IR in rustc itself (MIR, regrettably, only lowers control-flow, but uses variables instead of representing dataflow).

jhgb 5y ago
> which I believe uses integer indices So basically it sidesteps the type system issues in a similar way that an inconvenient car trip instead of taking a flight sidesteps the TSA issues? ;)
- aarchi 5y ago
  Adjacency matrices would make ownership clear and solve the single-writer/multiple-reader issue because nodes wouldn't directly reference each other, but it keeps the exact same relationship between nodes, so any memory leaks are still possible (e.g. not cleaning up dead code because it is cyclic and appears to have references). If I'm going to defeat the type system, it seems like raw pointers would be easier.

weavie 5y ago

It looks like this project is using typed arenas a fair bit - https://github.com/SomewhatML/sml-compiler/blob/master/crates/sml-core/src/arenas.rs https://github.com/SomewhatML/sml-compiler/blob/master/crate... I don't know the details of how this is being used in the project, but it might be worth investigating.

brabel 5y ago

I struggled with this as well, and ended up making the lexer itself have a lifetime which is that of the full String read from a file, so that every token (and AST node) has the lifetime of the parsed file. I keep their indexes as well so that I can show error messages like rustc itself does (with code snippets and all) which would be hard to do if I didn't have the full source code text available. Hope that helps.

amelius 5y ago
This sounds a bit like cheating. What if you want to parse a really big file and delete the tokens as soon as you don't need them? If Rust claims to solve memory management, then we should not fool ourselves by allocating everything in a huge chunk which is then freed when the program ends.
- steveklabnik 5y ago
  If this is cheating, many real compilers “cheat.” Heck, some of them famously don’t even free it when the program ends, leaving that up to the operating system!
  - amelius 5y ago
    The solution doesn't scale. The moment you need to deal with very large inputs, you will have to rewrite your entire application from scratch.
- scns 5y ago
  I prolonged my own path many times in my life, by making things harder than they need to be. (edit) Aspirations acting as a anti-shortcut somehow.
- brabel 5y ago
  That's why this was not my first choice... but it was just far too hard to implement it otherwise... and then again, once you really think about it, you must keep ALL tokens/AST nodes in memory to be able to analyse and type-check/lint any decent language... so keeping a big Sring in memory while all nodes just point to slices of it is not nearly as wasteful as it might appear at a first glance.

shpongled 5y ago

Author of the posted repo here! As another commenter posted, I used typed arenas quite a bit, it's not the most ergonomic way to do stuff, but it's quite performant and gets around the lifetime issues.

nybble41 5y ago

You may find this paper interesting: GhostCell: Separating Permissions from Data in Rust <https://plv.mpi-sws.org/rustbelt/ghostcell/paper.pdf https://plv.mpi-sws.org/rustbelt/ghostcell/paper.pdf> The essential idea is that you can use one of these "GhostCell" structures to assign a lifetime to a related collection of objects (such as the nodes in a graph), which allows the entire graph to be treated as if it had a single owner and a single lifetime rather than a separate owner and lifetime per node. The paper is relatively recent (2021), and GhostCell is not, so far as I am aware, used in rustc at this point.