Stream: t-compiler/wg-mir-opt

Topic: Pinned basic blocks?


Hanna Kruppe (Apr 18 2020 at 10:29, on Zulip):

This might be very off the rails, but I wanted to write it up at least: what if we gave every basic block (more precisely, BasicBlockData) a stable memory location and effectively made the CFG an intrusive data structure? The BasicBlock(u32) indices might still exist to enable deterministic iteration order and IndexedVec in each pass, but direct and mutual pointers could potentially be helpful elsewhere:

eddyb (Apr 18 2020 at 11:26, on Zulip):

you don't need actual pointers for this

eddyb (Apr 18 2020 at 11:26, on Zulip):

I think this is how Cranelift works

bjorn3 (Apr 18 2020 at 11:30, on Zulip):

eddyb said:

I think this is how Cranelift works

Yes, pretty much. You can append blocks to the layout in any order.

Hanna Kruppe (Apr 18 2020 at 11:45, on Zulip):

Yes, you could also have "stable IDs" instead of stable pointers, but why would you? Most ways to implement such IDs lead to more unnecessary indirection and lookups, and all of them result in inconvenient APIs where you always have to combine the ID with various context objects to do anything. The ability to use integers smaller than a pointer does not seem significant for basic blocks, since they are not as frequently referenced and maintaining such IDs required extra data structures on the side. Until recently, the killer argument was the inability to safely encapsulate intrusive object graphs, but that's exactly what pinning enables nowadays.

Hanna Kruppe (Apr 18 2020 at 11:53, on Zulip):

However, I am worried whether mutation of blocks and their contents can be adequately modeled with lifetimes, Pin<&T> vs Pin<&mut T>, and traversal methods. If some kind of interior mutability with runtime checks is needed for the access patterns needed in rustc, in contrast to the "no aliasing guarantees about the indices floating around, but actual mutation goes through short-lived &muts" style of newtyped indices that would suck.

Hanna Kruppe (Apr 18 2020 at 11:54, on Zulip):

This is more of an API design problem independent of how you actually implement it under the hood, but it might eat up some of the advantages of stable pointers (either performance or API simplicity).

eddyb (Apr 18 2020 at 12:15, on Zulip):

Most ways to implement such IDs lead to more unnecessary indirection and lookups, and all of them result in inconvenient APIs where you always have to combine the ID with various context objects to do anything.

IME it works great :P

eddyb (Apr 18 2020 at 12:16, on Zulip):

and Cranelift is also a success story AFAIK

eddyb (Apr 18 2020 at 12:16, on Zulip):

compared to worrying about pointers and all of the restrictions that imposes

eddyb (Apr 18 2020 at 12:16, on Zulip):

frankly we could get a lot of mileage out of just making the start block a field in the mir::Body instead of a constant

Hanna Kruppe (Apr 18 2020 at 12:47, on Zulip):

As I said before, I'm not sure there is anything to my idea, especially w.r.t. "can you make the API nice or does the borrow checker get in the way". But I'm curious, and I think basic blocks in MIR have different trade-offs than MIR statements and Cranelift's basic blocks (e.g., in Cranelift, every single instruction has a parent reference, while in current MIR and under my proposal, most blocks are only referenced from a single digit number of places in total).

bjorn3 (Apr 18 2020 at 12:49, on Zulip):

in Cranelift, every single instruction has a parent reference

No, the instruction itself doesn't know where it is in the layout. The Layout is the things that knows where instructions are located.

bjorn3 (Apr 18 2020 at 12:54, on Zulip):

Thinking about it again. The Layout does have a map from Inst -> Block.

Hanna Kruppe (Apr 18 2020 at 12:54, on Zulip):

Sorry, I was imprecise about where it's stored, but there is one BB reference per instruction, right?

bjorn3 (Apr 18 2020 at 12:55, on Zulip):

Yes

Hanna Kruppe (Apr 18 2020 at 12:56, on Zulip):

Then the point I was trying to make still stands: Cranelift has many more references to blocks, so representing those as smaller integers is more useful than in rustc.

eddyb (Apr 18 2020 at 12:57, on Zulip):

I don't want integers because they're small, I want them because they're simple

eddyb (Apr 18 2020 at 12:59, on Zulip):

you can just not renumber BBs if you can specify a non-0 starting basic block

eddyb (Apr 18 2020 at 12:59, on Zulip):

and it's a tradeoff: anything O(BasicBlocks) may get slowed down by the lack of renumbering

eddyb (Apr 18 2020 at 12:59, on Zulip):

(or worse, superlinear in the number of basic blocks)

Hanna Kruppe (Apr 18 2020 at 13:04, on Zulip):

It's not that simple. Today, the renumbering also happens when removing blocks, to keep a compact Vec<BasicBlockData> and corresponding IndexVecs in various passes. If you don't renumber, then you have to start treating it as something like a pool, maintain a free list, deal with non-consecutive IDs somehow, etc.

eddyb (Apr 18 2020 at 13:07, on Zulip):

or you can just not

eddyb (Apr 18 2020 at 13:09, on Zulip):

like I said, it's a tradeoff and you can choose to keep it simple at the cost of some later perf loss (which could be marginal, depending on the input and what you're doing to it)

Hanna Kruppe (Apr 18 2020 at 13:13, on Zulip):

There are definitely many trade-offs in this area, but FWIW if not freeing dead basic blocks is an option you're willing to entertain, then most of the implementation complexity relating to pointers goes away too.

eddyb (Apr 18 2020 at 13:13, on Zulip):

the difference is mutation

eddyb (Apr 18 2020 at 13:13, on Zulip):

if you can get away with interning then yes. otherwise, pointers are still a nightmare to mutate behind

Hanna Kruppe (Apr 18 2020 at 13:17, on Zulip):

We're getting to a point where it's so conceptual that I don't think it makes much sense to continue like this. Maybe I'll noodle around with API design and find something concrete that maybe works and we can talk about its trade-offs, or maybe I won't.

eddyb (Apr 18 2020 at 13:22, on Zulip):

maybe I should make it really clear that I've gone off the deep end on interning entire DAG IRs using integers, and ended up loving it, and neither interning nor integers might be a good fit for MIR

eddyb (Apr 18 2020 at 13:23, on Zulip):

but combining pointers with mutation for a graph also gives me a really unsettling vibe. like a kneejerk I suppose

eddyb (Apr 18 2020 at 13:23, on Zulip):

oh yeah it's sharing + mutation. duh

eddyb (Apr 18 2020 at 13:24, on Zulip):

if you use interior mutability inside each block then it's probably fine

eddyb (Apr 18 2020 at 13:26, on Zulip):

I guess "intrusive linked list" could mean you start with a &mut for the entry/start block and can mutate anywhere in the CFG by following the edges? that seems pretty restricted tbh

eddyb (Apr 18 2020 at 13:26, on Zulip):

there are some things that use Location to index a statement/terminator in O(1)

eddyb (Apr 18 2020 at 13:26, on Zulip):

and mutate it

eddyb (Apr 18 2020 at 13:27, on Zulip):

that seems hard w/ pointers and w/o interior mutability

Hanna Kruppe (Apr 18 2020 at 13:32, on Zulip):

This kind of "could touch anything" mutation seems to require (short-lived) mutable access to the whole Body anyway, no matter whether you use pointers or IDs, so the only question is whether you need to do it while holding references to other things derived from the Body. I think for basic blocks this is more feasible to avoid than for statements, but we'll see.

RalfJ (Apr 19 2020 at 08:23, on Zulip):

eddyb said:

I don't want integers because they're small, I want them because they're simple

pointers were simple. then we (as in compiler engineers) made them complicated. now we need to resort to integers and reinvent that wheel. ;)

Hanna Kruppe (Apr 19 2020 at 09:20, on Zulip):

For the record: I took a stab at this idea and quickly became very frustrated with how badly interior mutability composes with the collections needed for the successor/predecessor links. For a bunch of things, a Cell<Vec<_>> works (badly) if you take() it temporarily and restore it after the (non-reentrant) modification, but I quit by the time I got to successor/predecessor iterators. I can see a way to make them work (store pointer to block and an index) but given the lack of aliasing guarantees, I expect this would generally optimize badly (extra loads and bounds check on every iteration).

And then there's the old issue of iterator invalidation: I can make it safe to modify the CFG structure while iterating, but it likely indicates a bug whenever it happens, and it would be better to rule this out statically. Which is precisely what mutable-xor-shared enables and interior mutability doesn't. I've been thinking about ways to uphold "need &mut to modify the CFG structure" but when each block contains some interior-mutable pieces, it's hard to square "can hold exclusive access to multiple blocks" with "mutating one block fiddles with some data in another block", and even if you only needed mutable access to one block at a time, special care would be needed around self-loops.

Hanna Kruppe (Apr 19 2020 at 09:48, on Zulip):

From this perspective, I would say the advantage of integers isn't simplicity, it's that they are more dumb and kind of circumvent the borrow checker. By not tracking that they're effectively a shared reference to some data in the CFG outside of when you actually access that data, they enable you to create temporary mutable borrows when you need them because there's no conflicting long-lived shared borrows. Which makes them a little like &RefCell<BasicBlockData>! Except that dynamic checks are replaced with more coarse-grained static borrows of the whole Body: instead of bb.borrow_mut() preventing concurrent access to the same block, you do &mut body.statements[bb] and statically rule out access to any other basic block.

Hanna Kruppe (Apr 19 2020 at 11:11, on Zulip):

I believe the same API pattern (untracked handles that can be upgraded to real references via a borrow of the Body) can be ported to direct pointers too, but some extra cleverness is needed to limit the blast radius of dangling handles (integer IDs easily avoid UB by bounds checking against the underlying Vec) and while there are some ways to use lifetimes for this without conflicting with the mutable borrows needed for the actual data accesses, as far as I can tell this makes the API way too convoluted to be worth it.

Last update: Sep 28 2020 at 16:15UTC