Stream: t-compiler

Topic: design meeting 2019-11-08


nikomatsakis (Nov 08 2019 at 14:54, on Zulip):

Hey @T-compiler/meeting -- design meeting in 7 minutes.

The topic for the day will be a proposal for a unified dataflow framework, and there is a rough agenda thoughtfully prepared by @ecstatic-morse.

This is compiler-team#202.

nikomatsakis (Nov 08 2019 at 14:54, on Zulip):

OK, 6 minutes now.

nikomatsakis (Nov 08 2019 at 14:54, on Zulip):

Please :wave: to show you're here =)

nikomatsakis (Nov 08 2019 at 14:55, on Zulip):

In the meantime, feel free to post

Announcements

centril (Nov 08 2019 at 14:58, on Zulip):

- Splitting libsyntax is nearly done, https://github.com/rust-lang/rust/pull/65324

centril (Nov 08 2019 at 15:00, on Zulip):

- Would like y'all's opinion on moving the error codes into a new crate librustc_error_codes (in a way that should improve incremental rather than pessimizing), and then perhaps moving things eventually into .md files or something (potentially for internationalization) -- https://github.com/rust-lang/rust/issues/66210

nikomatsakis (Nov 08 2019 at 15:05, on Zulip):

OK, 5 minutes in -- do we expect @eddyb or @oli to make it?

nikomatsakis (Nov 08 2019 at 15:05, on Zulip):

Or @nagisa

nikomatsakis (Nov 08 2019 at 15:06, on Zulip):

I think we could get started, in any case

nikomatsakis (Nov 08 2019 at 15:07, on Zulip):

all right, @ecstatic-morse, do you want me to try and "drive" based on your agenda?

nikomatsakis (Nov 08 2019 at 15:07, on Zulip):

you can also drive if you like

nikomatsakis (Nov 08 2019 at 15:07, on Zulip):

er, wait, you're commenting in the wrong topic :)

ecstatic-morse (Nov 08 2019 at 15:07, on Zulip):

Yes that'd be good. I'll just chime in. We should start with the background.

ecstatic-morse (Nov 08 2019 at 15:07, on Zulip):

You saw nothing!

nikomatsakis (Nov 08 2019 at 15:07, on Zulip):

ok, let's do it

background :)

nikomatsakis (Nov 08 2019 at 15:07, on Zulip):

/me drives :racecar:

ecstatic-morse (Nov 08 2019 at 15:08, on Zulip):

For background, doing const-qualification on complex MIR bodies required a dataflow framework that was slightly more powerful than the current one, which only allowed gen/kill problems

nikomatsakis (Nov 08 2019 at 15:08, on Zulip):

In particular, it is still moving sets around, but it sometimes has a transfer function that is more complex than can be captured in a gen/kill set structure?

ecstatic-morse (Nov 08 2019 at 15:08, on Zulip):

Those can't handle assignments, so we couldn't propagate qualifs across them.

ecstatic-morse (Nov 08 2019 at 15:09, on Zulip):

Correct. So I implemented a new framework in #64566 that allowed for Fn(&mut State) transfer functions

ecstatic-morse (Nov 08 2019 at 15:09, on Zulip):

It will converge slower, because you cannot coalesce transfer functions for a whole basic block as you can with a pure gen/kill transfer functions

pnkfelix (Nov 08 2019 at 15:10, on Zulip):

that is exactly what I was about to ask

pnkfelix (Nov 08 2019 at 15:10, on Zulip):

is there some way to support both?

ecstatic-morse (Nov 08 2019 at 15:10, on Zulip):

#64470 was then implemented, and the perf impacts are pretty negligible

pnkfelix (Nov 08 2019 at 15:10, on Zulip):

i.e. for an analysis that is a gen-kill analysis, support coalescing the transfer-function?

nikomatsakis (Nov 08 2019 at 15:10, on Zulip):

(I presume that's partly what the motivation for this meeting is about?)

nikomatsakis (Nov 08 2019 at 15:11, on Zulip):

#64470 was then implemented, and the perf impacts are pretty negligible

wait can you elaborate on this

ecstatic-morse (Nov 08 2019 at 15:11, on Zulip):

Yes, the prototype accomplishes this using an adapter type

nikomatsakis (Nov 08 2019 at 15:11, on Zulip):

perf impacts comparing what to what?

nikomatsakis (Nov 08 2019 at 15:11, on Zulip):

like, the older system was using the old dataflow system for const qualification specifically?

nikomatsakis (Nov 08 2019 at 15:11, on Zulip):

and the new system is using the newer framework

nikomatsakis (Nov 08 2019 at 15:11, on Zulip):

(right?)

ecstatic-morse (Nov 08 2019 at 15:11, on Zulip):

No, the old system was using no dataflow (it didn't support branches)

nikomatsakis (Nov 08 2019 at 15:12, on Zulip):

OK, good, I was a bit surprised to hear that it used the dataflow framework :)

nikomatsakis (Nov 08 2019 at 15:12, on Zulip):

I was like "hmm I'm out of date, well, I better not admit I don't know how it works" ;)

ecstatic-morse (Nov 08 2019 at 15:12, on Zulip):

And compile times were not destroyed after we added the new dataflow-based one on top of the existing analysis

nikomatsakis (Nov 08 2019 at 15:12, on Zulip):

ok, so the add'l cost of the new analysis was small

ecstatic-morse (Nov 08 2019 at 15:12, on Zulip):

(we're now working to remove the old one)

nikomatsakis (Nov 08 2019 at 15:13, on Zulip):

this analysis runs on all MIR...?

ecstatic-morse (Nov 08 2019 at 15:13, on Zulip):

Yes, but it's because it only ever runs on consts. We still need to coalesce block transfer functions. It's very important

nikomatsakis (Nov 08 2019 at 15:13, on Zulip):

ok

pnkfelix (Nov 08 2019 at 15:13, on Zulip):

Am I correct in inferring that we do not yet have data on the time-overhead from switching any particular analysis from the old dataflow to the new dataflow ?

nikomatsakis (Nov 08 2019 at 15:13, on Zulip):

(Ah, right, this is const validation, not qualification)

ecstatic-morse (Nov 08 2019 at 15:14, on Zulip):

Am I correct in inferring that we do not yet have data on the time-overhead from switching any particular analysis from the old dataflow to the new dataflow ?

Correct

pnkfelix (Nov 08 2019 at 15:14, on Zulip):

i.e. the new dataflow was solely used for the new analysis; not for porting any of the old ones?

pnkfelix (Nov 08 2019 at 15:14, on Zulip):

okay thanks

ecstatic-morse (Nov 08 2019 at 15:15, on Zulip):

So the prototype framework handles this by having two constructors for a single Engine type. Each constructor creates an adapter, one of which holds cached block transfer functions, and each of the adapters implements the BlockEffects trait.

ecstatic-morse (Nov 08 2019 at 15:15, on Zulip):

https://github.com/rust-lang/rust/pull/65672/files#diff-3178a84d77e986f6ef17ef4ff334f111R358

ecstatic-morse (Nov 08 2019 at 15:15, on Zulip):

Actually, I'm sorry I'm getting ahead of myself

nikomatsakis (Nov 08 2019 at 15:15, on Zulip):

Wait, one sec, so, back to the narative maybe? we had:

ecstatic-morse (Nov 08 2019 at 15:16, on Zulip):

This is correct. The downside is that there's now a bunch of code that could be shared, especially graphviz debugging, that is replicated

ecstatic-morse (Nov 08 2019 at 15:18, on Zulip):

So my immediate thought was to have a single "dataflow engine" that would coalesce transfer functions if possible, and replace both frameworks

pnkfelix (Nov 08 2019 at 15:18, on Zulip):

Yes, the prototype accomplishes this using an adapter type

the "adapter type" you reference here: is that the sub-trait pub trait GenKillAnalysis<'tcx>: Analysis<'tcx> { ... } in your hackmd?

ecstatic-morse (Nov 08 2019 at 15:19, on Zulip):

Yes, the prototype accomplishes this using an adapter type

the "adapter type" you reference here: is that the sub-trait pub trait GenKillAnalysis<'tcx>: Analysis<'tcx> { ..> } in your hackmd?

It's actually a struct that wraps a GenKillAnalysis and also stores an IndexVec<BasicBlock, GenKillSet>

varkor (Nov 08 2019 at 15:19, on Zulip):

this is a basic question, but what does const qualification do vs validation?

varkor (Nov 08 2019 at 15:19, on Zulip):

I didn't see qualification explicitly mentioned in the design doc

varkor (Nov 08 2019 at 15:19, on Zulip):

is this the best reference: https://github.com/rust-lang/rust/issues/53819 ?

ecstatic-morse (Nov 08 2019 at 15:19, on Zulip):

this is a basic question, but what does const qualification do vs validation?

No one knows XD. I call "qualification" the part that tracks NeedsDrop and HasMutInterior inside a const body

ecstatic-morse (Nov 08 2019 at 15:20, on Zulip):

While "validation" (which i now call const-checking to avoid conflict with MIRI's validation) checks for calls to non-const fn etc.

nikomatsakis (Nov 08 2019 at 15:20, on Zulip):

in terms of the intention, the idea is this:

nikomatsakis (Nov 08 2019 at 15:20, on Zulip):
nikomatsakis (Nov 08 2019 at 15:21, on Zulip):
nikomatsakis (Nov 08 2019 at 15:21, on Zulip):

(I think?)

nikomatsakis (Nov 08 2019 at 15:21, on Zulip):

maybe I'm confused too :)

varkor (Nov 08 2019 at 15:21, on Zulip):

okay, great :+1:

centril (Nov 08 2019 at 15:21, on Zulip):

in other words "validation" is ensuring "const safety/soundness" as in https://www.ralfj.de/blog/2018/07/19/const.html (?)

nikomatsakis (Nov 08 2019 at 15:22, on Zulip):

(to the extent we've agreed on that approach, seems right)

ecstatic-morse (Nov 08 2019 at 15:22, on Zulip):

My plan was to write this up for the rustc guide after I finish replacing the old qualification logic

nikomatsakis (Nov 08 2019 at 15:22, on Zulip):

(time check, 22 minutes in)

ecstatic-morse (Nov 08 2019 at 15:22, on Zulip):

But we're getting too far afield

ecstatic-morse (Nov 08 2019 at 15:22, on Zulip):

Next heading niko?

ecstatic-morse (Nov 08 2019 at 15:22, on Zulip):

/me takes wheel

centril (Nov 08 2019 at 15:23, on Zulip):

My plan was to write this up for the rustc guide after I finish replacing the old qualification logic

:tada: -- if this could include "dataflow for dummies" for some toy problem that would be sweet

nikomatsakis (Nov 08 2019 at 15:23, on Zulip):

heh, I was going to say that let's turn a bit to discuss the plan for merging

nikomatsakis (Nov 08 2019 at 15:23, on Zulip):

I think we all agree that:

nikomatsakis (Nov 08 2019 at 15:23, on Zulip):
nikomatsakis (Nov 08 2019 at 15:23, on Zulip):
nikomatsakis (Nov 08 2019 at 15:23, on Zulip):

it might be worth explaining a bit more about those

nikomatsakis (Nov 08 2019 at 15:23, on Zulip):

I can take a stab

nikomatsakis (Nov 08 2019 at 15:24, on Zulip):

in MIR, you have a basic block like

BB {
   statement 1;
   ...
   statement N;
}
nikomatsakis (Nov 08 2019 at 15:24, on Zulip):

each one has some "effect" on the thing you are computing -- e.g., which variables are live

nikomatsakis (Nov 08 2019 at 15:24, on Zulip):

in a gen/kill set, you express that effect as "things to add to the set" and "things to take away"

nikomatsakis (Nov 08 2019 at 15:24, on Zulip):

the neat thing about this is that it's entirely independent of the old value of the set

nikomatsakis (Nov 08 2019 at 15:24, on Zulip):

so you can compute it once for each basic block and kind of "coallesce" this into a gen/kill set for the whole block

nikomatsakis (Nov 08 2019 at 15:25, on Zulip):

then to compute the final values, you can compute the set on entry to the block, apply the gen/kill set for the block as a whole to that set, and that gives you the result on exit from the block

nikomatsakis (Nov 08 2019 at 15:25, on Zulip):

then you propagate until a fixed point across all the basic block boundaries

nikomatsakis (Nov 08 2019 at 15:25, on Zulip):

now you know the values at the edges of each basic block, but you don't know the values for individual statements

nikomatsakis (Nov 08 2019 at 15:25, on Zulip):

for those you have to step in and "re-apply" the gen/kill set for each statement in turn

nikomatsakis (Nov 08 2019 at 15:26, on Zulip):

each one has some "effect" on the thing you are computing -- e.g., which variables are live

maybe a bad example, as liveness is a backwards flow analysis and our framework doesn't support that yet...

nikomatsakis (Nov 08 2019 at 15:26, on Zulip):

anyway, the more general function approach isn't necessarily "coallescable" in this way,

nikomatsakis (Nov 08 2019 at 15:26, on Zulip):

so in that case if the set at the entry to a block changes,

nikomatsakis (Nov 08 2019 at 15:26, on Zulip):

you have to walk through each statement in turn

nikomatsakis (Nov 08 2019 at 15:26, on Zulip):

to get the result at the exit

nikomatsakis (Nov 08 2019 at 15:26, on Zulip):

that's obviously more work

nikomatsakis (Nov 08 2019 at 15:27, on Zulip):

(seems about right? anything I missed or got wrong?)

pnkfelix (Nov 08 2019 at 15:27, on Zulip):

sounds right to me

ecstatic-morse (Nov 08 2019 at 15:27, on Zulip):

All correct

nikomatsakis (Nov 08 2019 at 15:27, on Zulip):

so the trick is

nikomatsakis (Nov 08 2019 at 15:27, on Zulip):

we want to permit the general functions

nikomatsakis (Nov 08 2019 at 15:27, on Zulip):

but recognize the special cases

nikomatsakis (Nov 08 2019 at 15:27, on Zulip):

I guess just the one special case

nikomatsakis (Nov 08 2019 at 15:27, on Zulip):

it's also just nicer if you have express your fn in terms of gen/kill to write it that way

nikomatsakis (Nov 08 2019 at 15:27, on Zulip):

(more DRY)

ecstatic-morse (Nov 08 2019 at 15:27, on Zulip):

One thing I want to mention before we get into how we go about this.

ecstatic-morse (Nov 08 2019 at 15:28, on Zulip):

Right now there's exactly one consumer of the "generic" framework, which is const qualification

nikomatsakis (Nov 08 2019 at 15:29, on Zulip):

(is there more?)

ecstatic-morse (Nov 08 2019 at 15:29, on Zulip):

So the second point on the agenda was: do we want to work on implementing a more powerful framework (datafrog, something with arbitrary dataflow lattices) which would unlock other optimizations

ecstatic-morse (Nov 08 2019 at 15:29, on Zulip):

(slow typer)

pnkfelix (Nov 08 2019 at 15:29, on Zulip):

hmm

pnkfelix (Nov 08 2019 at 15:30, on Zulip):

I have perhaps a slightly less grandiose question

ecstatic-morse (Nov 08 2019 at 15:30, on Zulip):

And port the const qualification to that?

pnkfelix (Nov 08 2019 at 15:30, on Zulip):

I did notice the new dataflow API still has the fn apply_call_return_effect( method

ecstatic-morse (Nov 08 2019 at 15:30, on Zulip):

rather than work on combining the two and having to split them up again when datafrog gets merged.

pnkfelix (Nov 08 2019 at 15:30, on Zulip):

back when we were designing the old dataflow, I think "we" (ariel, me, and probably nagisa and niko) all agreed that method was a nasty hack

pnkfelix (Nov 08 2019 at 15:31, on Zulip):

(a nasty hack I will take the blame for)

nikomatsakis (Nov 08 2019 at 15:31, on Zulip):

my opinion is:

nikomatsakis (Nov 08 2019 at 15:31, on Zulip):

I did notice the new dataflow API still has the fn apply_call_return_effect( method

and yes that is a nasty hack :)

pnkfelix (Nov 08 2019 at 15:31, on Zulip):

I was curious whether you had looked into options for ... um. .. getting rid of it?

eddyb (Nov 08 2019 at 15:31, on Zulip):

@nikomatsakis a better example for gen/kill is "definitely initialized" and/or "maybe uninitialized" (they're the same analysis, just one is a negation of the other)

ecstatic-morse (Nov 08 2019 at 15:32, on Zulip):

Some background again, function calls always need to be at the end of a basic block, because they take one path if they unwind, and another if they return normally

nikomatsakis (Nov 08 2019 at 15:32, on Zulip):

consider

BB1 {
    X = CALL(...) goto BB2 unwind BB3
}
ecstatic-morse (Nov 08 2019 at 15:32, on Zulip):

apply_call_return_effect is called only if a function returns successfully, not if it panics

nikomatsakis (Nov 08 2019 at 15:33, on Zulip):

Here, when you enter BB2 (no unwinding), X is initialized

nikomatsakis (Nov 08 2019 at 15:33, on Zulip):

but when you enter BB3, it is not

nikomatsakis (Nov 08 2019 at 15:33, on Zulip):

so you can't summarize the "effect" of that terminator in a uniform way

pnkfelix (Nov 08 2019 at 15:33, on Zulip):

right, and the effect on the bitset can differ between the two branches, right?

nikomatsakis (Nov 08 2019 at 15:33, on Zulip):

its effect varies per the edge

ecstatic-morse (Nov 08 2019 at 15:33, on Zulip):

To answer your question @pnkfelix, I didn't see a way to get rid of it.

ecstatic-morse (Nov 08 2019 at 15:33, on Zulip):

I did make it more uniform with the other effect methods

pnkfelix (Nov 08 2019 at 15:33, on Zulip):

ah well. sobeit

ecstatic-morse (Nov 08 2019 at 15:34, on Zulip):

i.e. it is also resricted to a gen/kill set in the new GenKillAnalysis, while it is not in the old one

nikomatsakis (Nov 08 2019 at 15:34, on Zulip):

my opinion is:

I'm curious if others agree on this :) -- if so, maybe discuss that second bullet a bit?

ecstatic-morse (Nov 08 2019 at 15:34, on Zulip):

(this was fine because it always came at the end of a block)

eddyb (Nov 08 2019 at 15:35, on Zulip):

@ecstatic-morse oh btw since the new framework is a more general fixpoint iteration, do you know how hard it would be to replace the bitsets with arbitrary data?

eddyb (Nov 08 2019 at 15:35, on Zulip):

to let e.g. constant folding use it? or do you think it's pointless to do that w/o switching to, say, datafrog?

ecstatic-morse (Nov 08 2019 at 15:36, on Zulip):

@eddyb I think not hard. There's some question about how to define the supertraitsGenKillAnalysis, since it only works on bit vectors, not arbitrary lattices

nikomatsakis (Nov 08 2019 at 15:36, on Zulip):

actually, time check, we're at 30 minutes, I'm wondering what's most imporant things to cover. In particular, I remember there was also some discussion of a "cursor-based" accessing API, for example.

ecstatic-morse (Nov 08 2019 at 15:36, on Zulip):

But I believe everything will work out.

nikomatsakis (Nov 08 2019 at 15:36, on Zulip):

maybe we can summarize the things that remain and pick a direction?

pnkfelix (Nov 08 2019 at 15:36, on Zulip):

i.e. it is also resricted to a gen/kill set in the new GenKillAnalysis, while it is not in the old BitDenotation one

hmm. I just realized something, I think: So the more general analysis, the state &mut BitSet it has access to ...

nikomatsakis (Nov 08 2019 at 15:36, on Zulip):

in particular, I feel kind of like the gen/kill set thing is "just" a matter of programming -- the key thing is that we want to recover the optimization

pnkfelix (Nov 08 2019 at 15:36, on Zulip):

... that state must summarize more than just the current point in the control flow, right?

pnkfelix (Nov 08 2019 at 15:37, on Zulip):

i.e. you must be able to mutate the state for the two different branches of control flow for a terminator (specifically call ) ?

eddyb (Nov 08 2019 at 15:37, on Zulip):

@ecstatic-morse I remember @nagisa and maybe someone else tried to get something like that merged a while back but it never landed, might be good to look into what that tried to achieve and the path it took

pnkfelix (Nov 08 2019 at 15:37, on Zulip):

and therefore it must have access to the state for multiple blocks?

nikomatsakis (Nov 08 2019 at 15:38, on Zulip):

(too many threads here:)

nikomatsakis (Nov 08 2019 at 15:38, on Zulip):

and therefore it must have access to the state for multiple blocks?

let's start with this question that @pnkfelix raised

ecstatic-morse (Nov 08 2019 at 15:38, on Zulip):

@pnkfelix The effect ends up in the entry set for both successors?

ecstatic-morse (Nov 08 2019 at 15:38, on Zulip):

(the unwind one and the successful return one)

ecstatic-morse (Nov 08 2019 at 15:38, on Zulip):

/me is being overwhelmed

nikomatsakis (Nov 08 2019 at 15:39, on Zulip):

I thought the whole point of apply_call_return_effect is that it covers those effects that are specific to the "normal" return path

pnkfelix (Nov 08 2019 at 15:39, on Zulip):

Right, I'm starting with the assumption that it must be able to handle a non-uniform effect

nikomatsakis (Nov 08 2019 at 15:39, on Zulip):

(and hence which do not apply to unwinding)

ecstatic-morse (Nov 08 2019 at 15:39, on Zulip):

I'm sorry, the block effect ends up in the entry set for both successors

pnkfelix (Nov 08 2019 at 15:39, on Zulip):

i.e. it is also resricted to a gen/kill set in the new GenKillAnalysis, while it is not in the old BitDenotation one

or no, hold on, I think I misunderstood the above comment

ecstatic-morse (Nov 08 2019 at 15:40, on Zulip):

While the success successor gets the block effect + call return effect

pnkfelix (Nov 08 2019 at 15:40, on Zulip):

I thought this meant that apply_call_return_effect was only present on the GenKillAnalysis trait

ecstatic-morse (Nov 08 2019 at 15:40, on Zulip):

I think we need to address @nikomatsakis bullet points real quck

pnkfelix (Nov 08 2019 at 15:40, on Zulip):

but re-reading the hackmd.io now, I see that even the general Analysis trait has that method. Sorry for the noise.

ecstatic-morse (Nov 08 2019 at 15:40, on Zulip):

Does anyone have thoughts on this?

nikomatsakis (Nov 08 2019 at 15:41, on Zulip):

my opinion is:

  • I suspect datafrog would be awesome, but I think we should wait until polonius proves itself, and not let perfect be the enemy of the good
  • I think we should discuss how to merge the gen/kill sets into this new framework first

I'm curious if others agree on this :) -- if so, maybe discuss that second bullet a bit?

nikomatsakis (Nov 08 2019 at 15:41, on Zulip):

that first bullet also applies to a more generalized, non-set-based analysis, imo

ecstatic-morse (Nov 08 2019 at 15:41, on Zulip):

Because the next thing to discuss are the particulars of the prototype implementation

pnkfelix (Nov 08 2019 at 15:41, on Zulip):

I think the sketch(es) from the hackmd on how to merge the gen/kill sets into this framework sounds fine to me.

pnkfelix (Nov 08 2019 at 15:42, on Zulip):

(there are slight variations on the idea, bu

nikomatsakis (Nov 08 2019 at 15:42, on Zulip):

(I felt the same; it seemed like it would work)

pnkfelix (Nov 08 2019 at 15:42, on Zulip):

but the point is: It seems to be able to recover coalescing across a block.

ecstatic-morse (Nov 08 2019 at 15:43, on Zulip):

Correct, the prototype is not fundamentally less fast than BitDenotation for gen/kill problems

varkor (Nov 08 2019 at 15:43, on Zulip):

does anyone have any estimate of how much work it would take to trial a datafrog version to compare them?

varkor (Nov 08 2019 at 15:43, on Zulip):

without any data, it's hard to justify one approach over the other, apart from in ease of implementation

nikomatsakis (Nov 08 2019 at 15:43, on Zulip):

does anyone have any estimate of how much work it would take to trial a datafrog version to compare them?

I'd have to think about it, it seems .. not entirely trivial to me

pnkfelix (Nov 08 2019 at 15:43, on Zulip):

well this seems close to being able to land. Datafrog would be a big leap I think.

nikomatsakis (Nov 08 2019 at 15:44, on Zulip):

I definitely think datafrog should prove itself on polonius first

nikomatsakis (Nov 08 2019 at 15:44, on Zulip):

and I say this as a massive proponent

nikomatsakis (Nov 08 2019 at 15:45, on Zulip):

but e.g. right now polonius takes the CFG as a vector of tuples and so forth; we may find that is too slow, or needs to be refined, or there are OOM problems, etc

ecstatic-morse (Nov 08 2019 at 15:45, on Zulip):

In the interest of time, these are the list of small API decisions made by the prototype, phrased as questions
- How do we feel about the {before_,}*_effect naming convention? It takes a bit of getting used to, and doesn’t extend nicely to backwards dataflow.
- Should we be passing a mir::Statement to the statement effect methods? What about mir::Body to bits_per_block?
- Should we use specialization to implement this?’
- Should the Analysis methods take &self or &mut self?
- Are we okay with a ResultsCursor becoming the common way to inspect results?
- How do we implement a zipped ResultsVisitor?

nikomatsakis (Nov 08 2019 at 15:45, on Zulip):

I'd rather we answer those in an experimental capacity

ecstatic-morse (Nov 08 2019 at 15:45, on Zulip):

https://paper.dropbox.com/doc/Unified-Dataflow-Framework-Meeting-Agenda--AoNHyM8tWZVmfMj~Kkh0gZaTAg-6pHEscQ9H696tawihH2nE

nikomatsakis (Nov 08 2019 at 15:45, on Zulip):

nice, I was about to make such a list

ecstatic-morse (Nov 08 2019 at 15:45, on Zulip):

(the third section)

pnkfelix (Nov 08 2019 at 15:46, on Zulip):

I'd rather we answer those in an experimental capacity

sorry, is this referring to the API decisions, or the stuff with polonius/datafrog?

nikomatsakis (Nov 08 2019 at 15:46, on Zulip):

(datafrog)

ecstatic-morse (Nov 08 2019 at 15:46, on Zulip):

Is there anything that stands out to people? These could also be discussed on a PR, though. They're small.

nikomatsakis (Nov 08 2019 at 15:46, on Zulip):

most of those API questions, though, don't seem that important --

pnkfelix (Nov 08 2019 at 15:46, on Zulip):

I personally would prefer avoiding using specialization to implement this, if we can help it

nikomatsakis (Nov 08 2019 at 15:46, on Zulip):

Yes, I agree, but I don't even see what we would need it for

nikomatsakis (Nov 08 2019 at 15:47, on Zulip):

But let's not get into it :P

nikomatsakis (Nov 08 2019 at 15:47, on Zulip):

I think i'd like to briefly discuss the results cursor

ecstatic-morse (Nov 08 2019 at 15:47, on Zulip):

Okay, if we don't wanna discuss the details now, can we discuss extensions in the next section?

nikomatsakis (Nov 08 2019 at 15:47, on Zulip):

the older approach basically used calbacks, right?

nikomatsakis (Nov 08 2019 at 15:47, on Zulip):

i.e., you have some callback that gets invoked with the results at each point?

ecstatic-morse (Nov 08 2019 at 15:48, on Zulip):

Yep, it used a Visitor pattern

nikomatsakis (Nov 08 2019 at 15:48, on Zulip):

I'm trying to remember

centril (Nov 08 2019 at 15:48, on Zulip):

Agreed re. specialization, except for perf, if hidden in a reasonable way (same policy as applies to standard library)

nikomatsakis (Nov 08 2019 at 15:48, on Zulip):

I remember thinking that this cursor would be useful in borrow check

ecstatic-morse (Nov 08 2019 at 15:48, on Zulip):

https://github.com/rust-lang/rust/blob/76ade3e8ac42cd7a7b7c3c5ef54818ab68e3ebdc/src/librustc_mir/dataflow/mod.rs#L309

nikomatsakis (Nov 08 2019 at 15:48, on Zulip):

So I guess I mostly wanted to say that I'm a proponent of it -- I think it's useful primarily in error handling, where you might like to be able to jump back to a certain point to get results

pnkfelix (Nov 08 2019 at 15:49, on Zulip):

I think the callback system was in part to work around lack of StreamingIterator? But I'm not 100% sure

ecstatic-morse (Nov 08 2019 at 15:49, on Zulip):

I remember thinking that this cursor would be useful in borrow check

We have a cursor for BitDenotation as well, so we could talk more about improving this.

nikomatsakis (Nov 08 2019 at 15:49, on Zulip):

Well, ok, so we're 50 minutes in -- my sense is that right now, there is a general consensus that we should do this, subject to experimental results?

nikomatsakis (Nov 08 2019 at 15:49, on Zulip):

(I thnk we can discuss extensions, too, but I'd like to establish this point first)

nikomatsakis (Nov 08 2019 at 15:50, on Zulip):

(further caveat, that we'll refine the details of the API in PRs)

pnkfelix (Nov 08 2019 at 15:50, on Zulip):

there is a general consensus that we should do this, subject to experimental results?

yeah, I think we should do this. But I would perhaps start by identifying the most expensive dataflow consumer,a nd porting them first

pnkfelix (Nov 08 2019 at 15:50, on Zulip):

expense here can be execution time or memory usage

pnkfelix (Nov 08 2019 at 15:50, on Zulip):

so... do both ...

nikomatsakis (Nov 08 2019 at 15:50, on Zulip):

I think in particular we are also deciding that we should NOT try to port to some more general framework first

ecstatic-morse (Nov 08 2019 at 15:50, on Zulip):

@pnkfelix have any candidates in mind?

pnkfelix (Nov 08 2019 at 15:50, on Zulip):

I don't know offhand. I'm betting mir-borrowck

nikomatsakis (Nov 08 2019 at 15:51, on Zulip):

(but not that we rule it out or anything of course)

nikomatsakis (Nov 08 2019 at 15:51, on Zulip):

I used to have a lot of stats on this from profiling

nikomatsakis (Nov 08 2019 at 15:51, on Zulip):

which of the borrowck analysis were most expensive

nikomatsakis (Nov 08 2019 at 15:51, on Zulip):

should be easy enough to gather with the self-profile data

nikomatsakis (Nov 08 2019 at 15:52, on Zulip):

ok, should we discuss extensions?

ecstatic-morse (Nov 08 2019 at 15:53, on Zulip):

Is @mw around?

pnkfelix (Nov 08 2019 at 15:53, on Zulip):

For example, we could skip caching block transfer functions for dataflow analyses on acyclic MIR,

Regarding extensions: I thought this (from the hackmd) was an interesting idea

mw (Nov 08 2019 at 15:53, on Zulip):

I am

ecstatic-morse (Nov 08 2019 at 15:54, on Zulip):

Do you remember what problems arose around dataflow when you tried to do extended basic blocks?

ecstatic-morse (Nov 08 2019 at 15:54, on Zulip):

I think this was years ago, sorry. I should have pinged you earlier but I didn't think we'd get this far

pnkfelix (Nov 08 2019 at 15:54, on Zulip):

this #39685 ?

mw (Nov 08 2019 at 15:54, on Zulip):

I'm pretty sure that was someone else

mw (Nov 08 2019 at 15:54, on Zulip):

I never did any major MIR work

ecstatic-morse (Nov 08 2019 at 15:55, on Zulip):

uhh, that's embarassing, sorry

nikomatsakis (Nov 08 2019 at 15:55, on Zulip):

heh so

ecstatic-morse (Nov 08 2019 at 15:55, on Zulip):

yes that

pnkfelix (Nov 08 2019 at 15:55, on Zulip):

it seems like something that would exacerbate the call_return hack situation ...

nikomatsakis (Nov 08 2019 at 15:55, on Zulip):

I think we're not going to do EBB

mw (Nov 08 2019 at 15:55, on Zulip):

no worries :)

nikomatsakis (Nov 08 2019 at 15:55, on Zulip):

I remember hearing that cranelift was backing away from EBB too? (cc @Dan Gohman) but in any case seems far out

ecstatic-morse (Nov 08 2019 at 15:56, on Zulip):

For example, we could skip caching block transfer functions for dataflow analyses on acyclic MIR,

Regarding extensions: I thought this (from the hackmd) was an interesting idea

Yeah, this is quite easy, although it just saves peak memory usage

pnkfelix (Nov 08 2019 at 15:56, on Zulip):

"just" saves

ecstatic-morse (Nov 08 2019 at 15:56, on Zulip):

It's all about that perf.rlo icount XD

nikomatsakis (Nov 08 2019 at 15:57, on Zulip):

For example, we could skip caching block transfer functions for dataflow analyses on acyclic MIR,

I agree this is interesting. There are also more general optimizations one can do -- e.g., recognizing patterns in the source (like loops, if/else-if branches) -- and optimizing around those. That's probably more complex than is worth it.

nikomatsakis (Nov 08 2019 at 15:57, on Zulip):

But I've always wanted to write them.

pnkfelix (Nov 08 2019 at 15:57, on Zulip):

/me is a fan of looking at the perf.rlo max-rss

nikomatsakis (Nov 08 2019 at 15:58, on Zulip):

While results cursors are great for consumers of a dataflow analysis, they make some optimizations more difficult. To operate efficiently, they require that the full dataflow state at entry to each block is stored.

nikomatsakis (Nov 08 2019 at 15:58, on Zulip):

I was just noting that line from the doc

nikomatsakis (Nov 08 2019 at 15:58, on Zulip):

I guess it seems relevant to the acyclic optimization

ecstatic-morse (Nov 08 2019 at 15:59, on Zulip):

Actually we would still have to store state at block entry for acyclic MIR in case there's branching

ecstatic-morse (Nov 08 2019 at 15:59, on Zulip):

That's more for EBB

nikomatsakis (Nov 08 2019 at 15:59, on Zulip):

I was just going to ask where the reduction in peak-rss would come from

pnkfelix (Nov 08 2019 at 16:00, on Zulip):

from not storing the bitsets for basic blocks that you're not going to iterate on

ecstatic-morse (Nov 08 2019 at 16:00, on Zulip):

So normally for gen/kill problems, we build up the transfer functions ahead of time and store them separate from the entry sets

nikomatsakis (Nov 08 2019 at 16:00, on Zulip):

but you still want them to read the results at the end?

nikomatsakis (Nov 08 2019 at 16:00, on Zulip):

but ah yeah ok you don't have to store the gen/kill sets, sure

pnkfelix (Nov 08 2019 at 16:00, on Zulip):

nah you recompute them

nikomatsakis (Nov 08 2019 at 16:00, on Zulip):

that .. doesn't sound right

pnkfelix (Nov 08 2019 at 16:01, on Zulip):

this is all based on an assumption that the fixed-point iteration is the big cost in time

nikomatsakis (Nov 08 2019 at 16:01, on Zulip):

well anyway

ecstatic-morse (Nov 08 2019 at 16:01, on Zulip):

But since you would only have to apply each block effect once for acyclic MIR, why store them?

nikomatsakis (Nov 08 2019 at 16:01, on Zulip):

OK, so, we're at 60 minutes :)

nikomatsakis (Nov 08 2019 at 16:02, on Zulip):

I think it's fine to keep chatting, but I'd like to request two things:

nikomatsakis (Nov 08 2019 at 16:03, on Zulip):
nikomatsakis (Nov 08 2019 at 16:03, on Zulip):
nikomatsakis (Nov 08 2019 at 16:03, on Zulip):

I guess I'd be happy to see an inside rust blog post if you wanted to write one :)

nikomatsakis (Nov 08 2019 at 16:03, on Zulip):

but I don't think it's required

nikomatsakis (Nov 08 2019 at 16:04, on Zulip):

this is interesting stuff though and people might like to hear about it, and you've got the raw material...

ecstatic-morse (Nov 08 2019 at 16:04, on Zulip):

Sounds good. It seems like we've decided to pursue this, so I'll add that to the summary.

nikomatsakis (Nov 08 2019 at 16:04, on Zulip):

OK, thanks all! :heart:

ecstatic-morse (Nov 08 2019 at 16:05, on Zulip):

Oh, and feel free to ask questions here or in another channel, but I'll be unavailable until later today.

eddyb (Nov 08 2019 at 16:45, on Zulip):

@ecstatic-morse EBBs was @simulacrum if I'm not mistaken

simulacrum (Nov 08 2019 at 16:45, on Zulip):

Indeed, yes

eddyb (Nov 08 2019 at 16:46, on Zulip):

and the problem was that several things, including dataflow, have to work on BBs fundamentally

eddyb (Nov 08 2019 at 16:47, on Zulip):

or maybe they could handle EBBs by replacing per-BB data with per-edge data, but there are at least as many edges as there are BBs, so you're likely to lose perf some way or another

eddyb (Nov 08 2019 at 16:48, on Zulip):

and overall it's significant effort to make all of those things work

nagisa (Nov 08 2019 at 20:02, on Zulip):

dataflow can easily work with data that’s as fine as statements, the downside is not performance but memory

nagisa (Nov 08 2019 at 20:02, on Zulip):

BB makes it possible to remember less and recompute more as needed.

nagisa (Nov 08 2019 at 20:02, on Zulip):

so if anything tying dataflow with basic blocks will make things slower.

nagisa (Nov 08 2019 at 20:05, on Zulip):

ecstatic-morse I remember nagisa and maybe someone else tried to get something like that merged a while back but it never landed, might be good to look into what that tried to achieve and the path it took

My original work did not land because I made a critical mistake of trying to land too many things in one go: a framework and a bunch of optimisations. Some of those optimisations ended up depending on stuff that didn’t exist and still does not exist to this day AFAIK (aliasing analysis)

ecstatic-morse (Nov 08 2019 at 23:13, on Zulip):

@eddyb I don't see any fundamental issues with EBBs and dataflow. Like you said, we would keep a cached block transfer function per-edge rather than per-block. I don't think we'll end up using any more memory, since each extra block after a function call gets replaced by an unwind edge.

ecstatic-morse (Nov 08 2019 at 23:15, on Zulip):

@nagisa The prototype we discussed at the meeting does not have that problem. If anything, it's the opposite: it doesn't enable anything new and interesting, just cleans up code a bit. I would like to look into supporting arbitrary lattices soonish. I'll probably want to ask you some questions before I start on that. I still need to really sit down with those PRs.

lqd (Nov 11 2019 at 10:32, on Zulip):

cranelift did indeed move away from EBBs back to BBs, and their rationale was explained in this issue — some of those reasons can apply to our case (and, unfortunately, to (R)VSDGs)

nikomatsakis (Nov 12 2019 at 14:46, on Zulip):

Yeah, I think the main motivation was the "unwind" edge from calls. Doesn't seem worth it to me.

nikomatsakis (Nov 12 2019 at 14:46, on Zulip):

At least the one that appealed to me the most :)

Last update: Nov 22 2019 at 05:00UTC