Stream: wg-async-foundations

Topic: shrinking generators #52924


nikomatsakis (Mar 05 2019 at 18:13, on Zulip):

So the other issue is Reuse generator slots after StorageDead #52924

nikomatsakis (Mar 05 2019 at 18:13, on Zulip):

we had some discussion in the youtube video about the overall strategy

nikomatsakis (Mar 05 2019 at 18:13, on Zulip):

however, I've not really looked into the code in question to see what is blocking that strategy from being implemented

nikomatsakis (Mar 05 2019 at 18:13, on Zulip):

@eddyb -- do you happen to be around?

nikomatsakis (Mar 05 2019 at 18:17, on Zulip):

(OK, I'm going to guess they're not right now)

tmandry (Mar 05 2019 at 18:17, on Zulip):

this sounds to me like a fun/interesting issue to tackle, but I'm not sure when I would be able to dig in (next week possibly?)

nikomatsakis (Mar 05 2019 at 18:17, on Zulip):

Actually, @Zoxc would likely know too, in case they are around

eddyb (Mar 05 2019 at 18:17, on Zulip):

Zulip won't notify me

nikomatsakis (Mar 05 2019 at 18:17, on Zulip):

Hey @eddyb =)

nikomatsakis (Mar 05 2019 at 18:17, on Zulip):

We were discussing how to alter the layout of generators

tmandry (Mar 05 2019 at 18:17, on Zulip):

(if someone else wants to tackle it, feel free)

nikomatsakis (Mar 05 2019 at 18:17, on Zulip):

so that they reuse slots

eddyb (Mar 05 2019 at 18:18, on Zulip):

I've discussed this with @Taylor Cramer before

nikomatsakis (Mar 05 2019 at 18:18, on Zulip):

@Taylor Cramer had mentioned the idea that you two discussed of using a simple heuristic to achieve better re-use

nikomatsakis (Mar 05 2019 at 18:18, on Zulip):

Yes, but I was wondering -- what parts of the code would have to be modified?

eddyb (Mar 05 2019 at 18:18, on Zulip):

the general case is painful to implement, but the simple case should be relatively easy

eddyb (Mar 05 2019 at 18:18, on Zulip):

if @Zoxc is around, you should ask them

nikomatsakis (Mar 05 2019 at 18:18, on Zulip):

Basically, is this relatively straightforward, or will it require some bigger refactorings?

nikomatsakis (Mar 05 2019 at 18:18, on Zulip):

(I was particularly concerned about whether it was ok for layout of a generator to depend on MIR.. I guess maybe it already does?)

eddyb (Mar 05 2019 at 18:19, on Zulip):

the simple case is "this is live only across one yield" I think?

eddyb (Mar 05 2019 at 18:19, on Zulip):

it already does

nikomatsakis (Mar 05 2019 at 18:19, on Zulip):

right, this is what @Taylor Cramer described

nikomatsakis (Mar 05 2019 at 18:19, on Zulip):

OK, then it seems like it shouldn't be too hard to do

eddyb (Mar 05 2019 at 18:20, on Zulip):

so, you end up with a map from state to a list of locals only needed for that state (i.e. those lists are all disjoint)

nikomatsakis (Mar 05 2019 at 18:20, on Zulip):

So, to fill in those of you who didn't follow the video the other day, the idea would be to identify data that is only live across a single yield, and then sort those bits of data by which yield they are live across. Things from yield X and yield Y can re-use the same storage slots

nikomatsakis (Mar 05 2019 at 18:20, on Zulip):

But for things live across multiple yield, we can just put them each into their own storage slot

nikomatsakis (Mar 05 2019 at 18:20, on Zulip):

this isn't optimal but would help a lot

nikomatsakis (Mar 05 2019 at 18:20, on Zulip):

and would be efficient to compute

nikomatsakis (Mar 05 2019 at 18:20, on Zulip):

(Sound about right, @eddyb?)

eddyb (Mar 05 2019 at 18:20, on Zulip):

you would then use that to have an enum-like thing after the existing layout (which wouldn't contain any of those locals)

nikomatsakis (Mar 05 2019 at 18:20, on Zulip):

Right ok

nikomatsakis (Mar 05 2019 at 18:21, on Zulip):

so I guess somebody needs to dig into the existing layout code a bit to suggest how to alter

nikomatsakis (Mar 05 2019 at 18:21, on Zulip):

my sense is that it seems of "medium" complexity

eddyb (Mar 05 2019 at 18:21, on Zulip):

well, what I described is how I think this would be sanely implemented, i.e. without trying to pair up locals

nikomatsakis (Mar 05 2019 at 18:21, on Zulip):

not a trivial patch but not an epic quest either

eddyb (Mar 05 2019 at 18:21, on Zulip):

the layout code shouldn't be too hard, you kinda have to treat it like an enum

eddyb (Mar 05 2019 at 18:22, on Zulip):

I guess we don't have enums with "common fields" today, heh

nikomatsakis (Mar 05 2019 at 18:22, on Zulip):

I mean right now we handle generators somehow

eddyb (Mar 05 2019 at 18:22, on Zulip):

right now we just make a struct

eddyb (Mar 05 2019 at 18:22, on Zulip):

with the state and all the locals ever saved

nikomatsakis (Mar 05 2019 at 18:22, on Zulip):

ok, I see

nikomatsakis (Mar 05 2019 at 18:23, on Zulip):

all right, we should break out these details into a separate topic

eddyb (Mar 05 2019 at 18:23, on Zulip):

there's no concept in the layout for "a struct with potentially-overlapping fields", sadly, that would be ideal here

nikomatsakis (Mar 05 2019 at 18:23, on Zulip):

I guess the question is: does anybody who is present here today feel interested in trying to tackle this challenge

eddyb (Mar 05 2019 at 18:23, on Zulip):

yeah, split this entire conversation out, since you pinged me

eddyb (Mar 05 2019 at 18:24, on Zulip):

(PM me somewhere, ideally Discord, if you need help with the layout stuff. for the analysis on the MIR side, you'll likely need @Zoxc)

tmandry (Mar 05 2019 at 18:24, on Zulip):

I'm interested as I mentioned

eddyb (Mar 05 2019 at 18:24, on Zulip):

I could also work on it as part of my upcoming contract but it might take a while to get to it

nikomatsakis (Mar 05 2019 at 18:24, on Zulip):

(ok, separated)

tmandry (Mar 05 2019 at 18:24, on Zulip):

but not sure whether I will have bandwidth for it.. that should become clear later today :)

Taylor Cramer (Mar 05 2019 at 18:35, on Zulip):

Yeah @tmandry we should chat about this later today :)

Taylor Cramer (Mar 05 2019 at 18:36, on Zulip):

As far as the "enum with shared fields" thing goes, I'd imagined there'd be some way to hide the actual types from MIR and keep the generator memory as roughly a "stack" of bytes

Taylor Cramer (Mar 05 2019 at 18:37, on Zulip):

We lose out on some optimization opportunities but it seems like a reasonable place to start

Taylor Cramer (Mar 05 2019 at 18:37, on Zulip):

I think @RalfJ had opinions here

Taylor Cramer (Mar 05 2019 at 22:53, on Zulip):

trying again after adding them to the stream... @RalfJ

RalfJ (Mar 06 2019 at 09:22, on Zulip):

I am mostly concerned about having a definition of a "valid" generator state (as in, the invariant that layout optimizations rely on) that can be reasonably checked by a UB sanitizer. Currently generators are treated as opaque by Miri because their fields dont actually all get properly initialized upon creation -- basically, the type information stored in the layout is lying when it claims that these fields always have these types. I think this is also why the layout code needs a special case to not find niches in generators.

nikomatsakis (Mar 06 2019 at 16:11, on Zulip):

I imagine that if we take the 'enum-like' approach that @eddyb was describing -- probably "union-like" is a better description -- this problem will go away

nikomatsakis (Mar 06 2019 at 16:11, on Zulip):

but it's a good thing for us to try to fix at the same time

nikomatsakis (Mar 06 2019 at 16:13, on Zulip):

that said, it seems like we might want a kind of separation -- what the MIR calls "field 0", for example, might want to map to a richer internal structure, I would think... i.e., internally the generator would have a kind of "union" of possibilities...

nikomatsakis (Mar 06 2019 at 16:13, on Zulip):

...I have to look a bit at the code to try and make what I'm saying more precise.

Taylor Cramer (Mar 06 2019 at 17:12, on Zulip):

it certainly would be helpful to have a bit of information left over for debuginfo as well

nikomatsakis (Mar 06 2019 at 17:44, on Zulip):

Yes, a good point

tmandry (Mar 12 2019 at 01:54, on Zulip):

Okay, I've begun digging into this and taking notes on what the implementation would require. I'm very new to all of this code, so anyone that has familiarity with it is welcome to add to my notes / leave comments :)

tmandry (Mar 12 2019 at 01:54, on Zulip):

so far it's all pretty basic stuff, just finding out what code is involved etc

tmandry (Mar 20 2019 at 01:50, on Zulip):

Okay, so my current thinking is I have two possible approaches to making this work:

1) Actually create an enum type during the mir transform stage, with one variant for each yield point, and put it inside the GeneratorLayout
- not entirely clear on how to propagate local def information through to debug info, this would probably require significant refactoring of that code
2) Store all the information about fields only live across one yield point inside GeneratorLayout, and then eventually turn this into a custom layout with FieldPlacement::Arbitrary, essentially handling it the same as an enum.
3) Maybe something else?

I haven't dug into how feasible each of these options is yet, thoughts/suggestions welcome!

Giles Cope (Mar 20 2019 at 08:32, on Zulip):

Debug - that's a good point. Which approach is likely to be kinder to debuggers trying to fathom what's going on with a generator?

Nemo157 (Mar 20 2019 at 10:00, on Zulip):

Debug is handled similar to function locals when the generator is running, currently all locals are declared as soon as the generator resumes, but I think this change will make it more needed to actually declare the correct locals based on current state

Nemo157 (Mar 20 2019 at 10:00, on Zulip):

There’s also the question of what to display when printing the generator value itself, I’m not sure what’s done currently

tmandry (Mar 20 2019 at 16:34, on Zulip):

(deleted)

tmandry (Mar 20 2019 at 16:34, on Zulip):

cc @eddyb

nikomatsakis (Mar 20 2019 at 19:50, on Zulip):

btw @eddyb has troubles with Zulip, you may get more mileage by pinging them on discord with a link to the comment

eddyb (Mar 20 2019 at 19:51, on Zulip):

oh it's this hard stuff

eddyb (Mar 20 2019 at 19:51, on Zulip):

I'm in a wg-grammar meeting (the first one I attended in several months...), but I'll try to multitask

eddyb (Mar 20 2019 at 20:08, on Zulip):

1) Actually create an enum type during the mir transform stage

there's no way to synthesize actual enum types during compilation, btw

eddyb (Mar 20 2019 at 20:13, on Zulip):

@tmandry only 2) is workable AFAICT. as for debuginfo, there shouldn't be any issues - I also need to get back to https://github.com/rust-lang/rust/pull/56278 soon, the follow-up to that should clean up the debuginfo generation logic and let us do more things with generators

eddyb (Mar 20 2019 at 20:16, on Zulip):

@Nemo157 btw for debuggers printing the generator itself, we can piggyback on the new support for debugging enums, which tells DWARF about variant types quite directly

eddyb (Mar 20 2019 at 20:17, on Zulip):

and because DWARF has little to no limitations to how weird layouts can be, pretty much anything should work!

tmandry (Mar 20 2019 at 20:55, on Zulip):

okay, thanks!

tmandry (Mar 20 2019 at 20:55, on Zulip):

I think I'll try to implement proper debuginfo in this PR, but if I hit issues, I can open a new blocking issue and wait on #56278

tmandry (Mar 26 2019 at 05:08, on Zulip):

Status update: I'm nearly done with an initial implementation. The analysis is done and now I'm working on the layout code. Most of the time has been spent understanding what's going on currently, the implementation itself doesn't seem that hard.

tmandry (Mar 26 2019 at 05:08, on Zulip):

cc @nikomatsakis since I won't be able to make the wg meeting tomorrow

tmandry (Mar 26 2019 at 23:16, on Zulip):

(okay, so implementing the layout is definitely the harder part)

tmandry (Mar 28 2019 at 02:19, on Zulip):

@eddyb Right now FieldPlacement::Arbitrary lowers directly to an LLVM struct which iiuc doesn't support overlapping fields. Is it possible to use FieldPlacement::Variant and generate MIR that accesses the fields under a variant?

tmandry (Mar 28 2019 at 18:47, on Zulip):

(cc other people who might know... @Zoxc @varkor @Vadim Petrochenkov)

tmandry (Mar 28 2019 at 18:54, on Zulip):

I'm just looking for a quick thumbs up/down on whether this approach is worth pursuing.. tackling it now unless I hear otherwise :)

tmandry (Mar 28 2019 at 18:57, on Zulip):

one problem I see is that I'd have to move the variant tag to field 0, in front of the generator upvars, which might break things elsewhere

tmandry (Mar 28 2019 at 19:05, on Zulip):

more specifically, I'm sure there is both code that assumes variant tags are at field index 0, and code that assumes that upvars start at index 0

tmandry (Mar 28 2019 at 19:10, on Zulip):

actually, it may not matter for codegen purposes. the MIR generation will always generate a direct field access to get the variant, as well as to the fields that should be valid across a particular suspension point.

tmandry (Mar 28 2019 at 19:11, on Zulip):

okay, this might work

Nemo157 (Mar 28 2019 at 20:29, on Zulip):

@tmandry I know that debuginfo definitely assumes upvars start at field index 0

Nemo157 (Mar 28 2019 at 20:30, on Zulip):

But that shouldn’t be hard to fixup

tmandry (Mar 28 2019 at 21:15, on Zulip):

@Nemo157 thanks

tmandry (Mar 28 2019 at 21:15, on Zulip):

I'm going to try keeping them there first

eddyb (Mar 28 2019 at 21:24, on Zulip):

the tag is not before everything else? huh

eddyb (Mar 28 2019 at 21:25, on Zulip):

the field stuff is tricky... I don't think FIeldPlacement::Variant is a thing?

eddyb (Mar 28 2019 at 21:25, on Zulip):

maybe rename Arbitrary to Disjoint and add another variant... or maybe just a disjoint field to Arbitrary

eddyb (Mar 28 2019 at 21:25, on Zulip):

so the "struct-like" situation only holds for disjoint: true

eddyb (Mar 28 2019 at 21:27, on Zulip):

rustc_codegen_llvm already has logic for accessing arbitrary offsets in non-struct-likes... unless that became unnecessary and got removed, heh

eddyb (Mar 28 2019 at 21:28, on Zulip):

you could try doing variants but idk if you can encode that in MIR nicely, MIR variant "downcasting" requires an AdtDef (that the variant index indexes into)

eddyb (Mar 28 2019 at 21:29, on Zulip):

so I think "non-disjoint arbitrary offsets" that the LLVM backend has to work harder for, but doesn't introduce complexity anywhere else, is good. OTOH, using the variants stuff means miri can actually validity-check generators because there is a mapping from discriminant values to which fields should be initialized

tmandry (Mar 28 2019 at 21:35, on Zulip):

erm yeah, I meant to use Variants::Tagged instead of Variants::Single

tmandry (Mar 28 2019 at 21:36, on Zulip):

basically treat it as an enum with a long, multi-field prefix

tmandry (Mar 28 2019 at 21:37, on Zulip):

ah I see about the AdtDef, I was a bit worried about something like that

tmandry (Mar 28 2019 at 21:38, on Zulip):

I would like to get miri able to do validity checking, but if it's a big refactor then it can wait..

tmandry (Apr 05 2019 at 18:50, on Zulip):

So, the way generators work now

tmandry (Apr 05 2019 at 18:51, on Zulip):

is that locals who are live across yields are remapped to fields of our generator struct

tmandry (Apr 05 2019 at 18:52, on Zulip):

this is fairly easily done, and means the MIR doesn't need to change much

tmandry (Apr 05 2019 at 18:53, on Zulip):

However, one interesting consequence of putting these locals in a tagged union, with one variant for each yield

tmandry (Apr 05 2019 at 18:54, on Zulip):

is that accesses of some locals, who (let's say) are only live across one yield point,
may interleave with the accesses of locals who are only live across the next yield point

tmandry (Apr 05 2019 at 18:55, on Zulip):

If we were to follow the way the MIR transform is done today, this would lead to invalid codegen, because those locals might actually overlap in memory

tmandry (Apr 05 2019 at 19:01, on Zulip):

for example, let's pretend our generator looks like this

fn my_generator() {
  let x = foo();
  yield 1;
  let y = bar();
  take(x);
  yield 2;
  take(y);
}

then our generator type would look like this...

enum MyGenerator {
  Unresumed,
  Complete,
  Poisoned,
  YieldedOnce { x },
  YieldedTwice { y },
}

when the generator is resumed after the first yield, the generated code would write to y, then read from x, which is bad because they share the same bytes in memory

tmandry (Apr 05 2019 at 19:02, on Zulip):

So, the solution to this is to move all the "locals" like this _out_ of the generator type and into real locals at the beginning of each resume

tmandry (Apr 05 2019 at 19:03, on Zulip):

But of course, for any locals which are borrowed, this could break things

tmandry (Apr 05 2019 at 19:03, on Zulip):

So the initial plan is for this optimization not to include any locals which are ever borrowed

tmandry (Apr 05 2019 at 19:05, on Zulip):

We have the information we need to make the optimization smarter than this, of course

tmandry (Apr 05 2019 at 19:05, on Zulip):

@eddyb and I were talking about this, and doing the "full" optimization is a lot like the NRVO optimization, which was quite expensive the last time they tried it

tmandry (Apr 05 2019 at 19:05, on Zulip):

cc @Taylor Cramer

tmandry (Apr 05 2019 at 19:11, on Zulip):

I think this also relates to some of the other issues around optimizations involving borrowed locals

tmandry (Apr 05 2019 at 19:11, on Zulip):

so maybe we can solve many of them with the same analysis

tmandry (Apr 05 2019 at 19:12, on Zulip):

assuming we can find one that performs well.. :)

tmandry (Apr 06 2019 at 00:54, on Zulip):

Okay, so latest update is, we need to support some borrowed locals in order to optimize await

tmandry (Apr 06 2019 at 00:57, on Zulip):

In the await case it is easier, because the borrowed future goes out of scope by the time we are done await'ing it

tmandry (Apr 06 2019 at 00:58, on Zulip):

So we decided to use storage liveness for this

tmandry (Apr 06 2019 at 00:58, on Zulip):

if we have two vars x and y, and every occurrence of StorageLive(y) is dominated by an occurrence of StorageDead(x), then x and y can overlap in the generator type

tmandry (Apr 06 2019 at 01:00, on Zulip):

I'll look more into how to run this on monday

tmandry (Apr 06 2019 at 01:16, on Zulip):

but this would mean that we won't be moving things in and out of the generator struct, and will continue using the fields directly

tmandry (Apr 12 2019 at 23:50, on Zulip):

Nemo157 btw for debuggers printing the generator itself, we can piggyback on the new support for debugging enums, which tells DWARF about variant types quite directly

tmandry (Apr 12 2019 at 23:51, on Zulip):

I'm having trouble observing this behavior even for enums

tmandry (Apr 12 2019 at 23:52, on Zulip):

@Nemo157 should I be able to print an enum in gdb or lldb and see the fields inside it?

tmandry (Apr 12 2019 at 23:53, on Zulip):

(or anyone who knows)

tmandry (Apr 13 2019 at 21:14, on Zulip):

ah, gdb 8 seems to support this. newer lldb still doesn't seem to though

tmandry (Apr 16 2019 at 19:10, on Zulip):

Okay, so here's the current logic of the optimization:

tmandry (Apr 16 2019 at 19:10, on Zulip):

@nikomatsakis ^

tmandry (Apr 16 2019 at 19:12, on Zulip):

sorry for weird formatting, zulip doesn't seem to handle numbered lists well

nikomatsakis (Apr 16 2019 at 19:13, on Zulip):

Can you say a bit more about step 3?

(3) Run MaybeStorageLive dataflow analysis on MIR

What is this analysis more precisely?

tmandry (Apr 16 2019 at 19:16, on Zulip):

here's the code

tmandry (Apr 16 2019 at 19:16, on Zulip):

it's a very simple analysis, only looking at StorageLive and StorageDead statements

tmandry (Apr 16 2019 at 19:17, on Zulip):

so one possibility is to make this smarter, and look to see if there are actual reads and writes past a certain point

tmandry (Apr 16 2019 at 19:19, on Zulip):

I may be wrong since I'm new to this, but dataflow analysis seems to propagate in the "forward" direction (perhaps it's a fixed point algorithm?), while this would need to propagate information "backwards"

tmandry (Apr 16 2019 at 19:21, on Zulip):

of course rustc_mir::util::liveness must be doing this somehow

tmandry (Apr 16 2019 at 19:21, on Zulip):

(I haven't looked at the code)

tmandry (Apr 16 2019 at 19:23, on Zulip):

however, "regular" liveness analysis doesn't work here, because it only cares about whether particular assignments are actually used, while we care about storage liveness (i.e., whether physical bytes should be reserved for future assignments)

tmandry (Apr 16 2019 at 19:23, on Zulip):

so all that to say, we could maybe come up with a way of combining these two approaches into something smarter than MaybeStorageLive, as you alluded to earlier in the meeting

tmandry (Apr 16 2019 at 19:24, on Zulip):

not sure if I'm being clear

tmandry (Apr 16 2019 at 19:27, on Zulip):

I think this can be done, but I haven't though through all of the details yet

tmandry (Apr 16 2019 at 19:34, on Zulip):

The other possible approach I see is one you also mentioned:
Emitting StorageDead on the drop and unwind paths, at least for generators

tmandry (Apr 16 2019 at 19:35, on Zulip):

(ping @nikomatsakis again :) )

nikomatsakis (Apr 16 2019 at 19:39, on Zulip):

@tmandry thanks -- hmm,

nikomatsakis (Apr 16 2019 at 19:39, on Zulip):

what I was proposing was indeed something more like a "liveness" analysis

nikomatsakis (Apr 16 2019 at 19:40, on Zulip):

whether it's different from a normal liveness analysis depends a bit on your perspetive

nikomatsakis (Apr 16 2019 at 19:41, on Zulip):

that is, x = 5 -- while traditionally considered a "def" of x -- could in rust be considered a use, since it has to drop the previous value of x (though I guess this doesn't apply to integers)

nikomatsakis (Apr 16 2019 at 19:41, on Zulip):

anyway the point would be that basically everything would be considered a use of the variable except StorageLive

nikomatsakis (Apr 16 2019 at 19:41, on Zulip):

which would be considered a def

nikomatsakis (Apr 16 2019 at 19:42, on Zulip):

(though the semantics of StorageLive are a bit..odd -- it's not clear to me, for example, what happens if you have two StorageLive statements, one after the other -- is the second one a no-op?)

tmandry (Apr 16 2019 at 19:42, on Zulip):

anyway the point would be that basically everything would be considered a use of the variable except StorageLive

yes, that sounds right

nikomatsakis (Apr 16 2019 at 19:42, on Zulip):

but let's assume (which I presume is true) that this doesn't happen for us, and that there is only a single StorageLive for any given slot (or possibly zero)

tmandry (Apr 16 2019 at 19:43, on Zulip):

(though the semantics of StorageLive are a bit..odd -- it's not clear to me, for example, what happens if you have two StorageLive statements, one after the other -- is the second one a no-op?)

(I have found them odd too, including the lack of StorageDead along some paths, and wish there were a more formal definition somewhere)

nikomatsakis (Apr 16 2019 at 19:43, on Zulip):

yes, that sounds right

well, hmm, so are we running this before or after drop elaboration?

tmandry (Apr 16 2019 at 19:43, on Zulip):

before

nikomatsakis (Apr 16 2019 at 19:44, on Zulip):

so really what you want is something like x = 5 is a use iff x is "maybe initialized"

tmandry (Apr 16 2019 at 19:44, on Zulip):

or wait, no

tmandry (Apr 16 2019 at 19:44, on Zulip):

sorry, I'm confused, as there's a drop elaboration step within the generator transform

tmandry (Apr 16 2019 at 19:45, on Zulip):

but the "regular" drop elaboration stage happens before us

tmandry (Apr 16 2019 at 19:46, on Zulip):

I think we can consider all locals like a "normal" function at this point

nikomatsakis (Apr 16 2019 at 19:47, on Zulip):

are you sure?

nikomatsakis (Apr 16 2019 at 19:47, on Zulip):

seems a bit odd

nikomatsakis (Apr 16 2019 at 19:47, on Zulip):

but ok

tmandry (Apr 16 2019 at 19:47, on Zulip):

well, the analysis is running before we remap any locals to generator fields

nikomatsakis (Apr 16 2019 at 19:47, on Zulip):

in that event, though, when you do x = 5 that will get compiled into a regular assignment but also a kind of drop of the previous value

nikomatsakis (Apr 16 2019 at 19:48, on Zulip):

but the real question is whether we create StorageLive for all things

nikomatsakis (Apr 16 2019 at 19:48, on Zulip):

(e.g., even for temporaries etc?)

tmandry (Apr 16 2019 at 19:48, on Zulip):

there are some locals that never have StorageLive or StorageDead statements at all; these are not considered candidates for overlapping

nikomatsakis (Apr 16 2019 at 19:49, on Zulip):

ok, I feel like they could be, but let's ignore them for now

tmandry (Apr 16 2019 at 19:49, on Zulip):

(they also have to be handled specially in the existing layout computation)

nikomatsakis (Apr 16 2019 at 19:49, on Zulip):

if we do, and there's exactly one, it's not really important. I suspect we could do the analysis I talked about (indeed, a backwards analysis, and indeed it cannot use the generic dataflow framework then). We could implement it with datafrog, also.

nikomatsakis (Apr 16 2019 at 19:49, on Zulip):

(liveness has custom code for this reason)

nikomatsakis (Apr 16 2019 at 19:50, on Zulip):

the idea would roughly be "who cares if its storage is still live if we never look at it"

nikomatsakis (Apr 16 2019 at 19:50, on Zulip):

but maybe I don't know what I'm talking about :)

nikomatsakis (Apr 16 2019 at 19:50, on Zulip):

I'm a bit reluctant to modify the MIR generation though

nikomatsakis (Apr 16 2019 at 19:50, on Zulip):

but I do also worry that we're being hand-wavy with our semantics

nikomatsakis (Apr 16 2019 at 19:51, on Zulip):

and it'd be nice to try and write-out and document somewhat clearly what's going on here

tmandry (Apr 16 2019 at 19:51, on Zulip):

the idea would roughly be "who cares if its storage is still live if we never look at it"

it makes sense to me and I've been iterating on this for awhile (but the earlier iterations also made sense to me at first... ;) )

tmandry (Apr 16 2019 at 19:53, on Zulip):

I'm a bit reluctant to modify the MIR generation though

which part, the generation on drops and unwind paths?

tmandry (Apr 16 2019 at 19:53, on Zulip):

we wouldn't need that if we do the liveness approach, and if indeed that works, I'm inclined to do it that way

nikomatsakis (Apr 16 2019 at 19:54, on Zulip):

which part, the generation on drops and unwind paths?

right

nikomatsakis (Apr 16 2019 at 19:54, on Zulip):

because it could be a lot more IR, for one thing, and because I think it might be annoying

nikomatsakis (Apr 16 2019 at 19:54, on Zulip):

and because it doesn't quite feel necessary

tmandry (Apr 16 2019 at 19:56, on Zulip):

okay, I'll try implementing the "storage liveness analysis"

tmandry (Apr 16 2019 at 19:56, on Zulip):

I feel like the terminology is getting confusing

nikomatsakis (Apr 16 2019 at 19:56, on Zulip):

yeah that is probably a bad name :)

tmandry (Apr 16 2019 at 19:57, on Zulip):

sounds good, thanks :)

tmandry (Apr 16 2019 at 19:57, on Zulip):

has to run

nikomatsakis (Apr 16 2019 at 20:10, on Zulip):

great

tmandry (Apr 16 2019 at 22:16, on Zulip):

@nikomatsakis ah I remember now why we cared about StorageDead, it's because of borrows

nikomatsakis (Apr 16 2019 at 22:16, on Zulip):

oh, yes, ok

nikomatsakis (Apr 16 2019 at 22:16, on Zulip):

unsafe code

tmandry (Apr 16 2019 at 22:17, on Zulip):

that, and right now the liveness analysis doesn't consider the uses of borrows in general

nikomatsakis (Apr 16 2019 at 22:17, on Zulip):

well I guess any borrow

nikomatsakis (Apr 16 2019 at 22:17, on Zulip):

yeah

tmandry (Apr 16 2019 at 22:17, on Zulip):

and we borrow the future in await!() which is specifically the case that I care about optimizing right now :)

tmandry (Apr 16 2019 at 22:20, on Zulip):

so, we may need a different approach

tmandry (Apr 16 2019 at 22:22, on Zulip):

one thing I realized with changing the drop/unwind MIR is, maybe we can stick with the blocks we have, but sprinkle extra StorageDead statements around (i.e., you might encounter a StorageDead without ever seeing a StorageLive)

tmandry (Apr 16 2019 at 22:23, on Zulip):

..then, when considering whether a local may be storage live in a block, if there are StorageDead statements at the beginning of the block, process all of those as part of the start of the block

tmandry (Apr 16 2019 at 22:23, on Zulip):

..this feels hacky, so maybe it's wrong :)

tmandry (Apr 16 2019 at 23:21, on Zulip):

^ the intuition above being "if two vars might both be StorageLive at the beginning of the block, but then one or both of them are immediately StorageDead before anything else happens, then it doesn't count"

tmandry (Apr 16 2019 at 23:22, on Zulip):

this still depends on adding StorageDead statements in certain places, though

tmandry (Apr 17 2019 at 01:05, on Zulip):

Okay, I think I'm going to try to prove out the optimization while generating full StorageDead statements everywhere

tmandry (Apr 17 2019 at 01:07, on Zulip):

then we can talk about ways to simplify the generated MIR (I think there are some, since unlike drop, StorageDead can happen multiple times, or even without having a StorageLive)

tmandry (Apr 17 2019 at 01:07, on Zulip):

Ironically, what I'm really trying to preserve is information about scopes here

tmandry (Apr 17 2019 at 01:08, on Zulip):

maybe we can use scope information directly...?

tmandry (Apr 17 2019 at 04:00, on Zulip):

i.e. if we know two vars are in scopes that are disjoint, then they're okay to overlap in storage

tmandry (Apr 17 2019 at 04:01, on Zulip):

although this precludes optimizations we might want to do later

tmandry (Apr 17 2019 at 04:42, on Zulip):

(ah nevermind, there's a reason scopes aren't preserved in MIR. sounds like StorageDead is the way.)

tmandry (Apr 17 2019 at 18:13, on Zulip):

@nikomatsakis any objection to the above?

tmandry (Apr 18 2019 at 20:35, on Zulip):

@nikomatsakis ping :)

nikomatsakis (Apr 19 2019 at 17:53, on Zulip):

Hey @tmandry

nikomatsakis (Apr 19 2019 at 17:53, on Zulip):

Sorry, yesterday I was basically tied up all day

nikomatsakis (Apr 19 2019 at 17:54, on Zulip):

any objection to the above?

I'm not 100% sure what the proposal is, I guess

nikomatsakis (Apr 19 2019 at 17:55, on Zulip):

@RalfJ -- apologies for subscribing you to this stream, but I have a quick question -- you were at some point writing up some kind of semantics for StorageLive and StorageDead, right?

nikomatsakis (Apr 19 2019 at 17:55, on Zulip):

@RalfJ :point_up:

tmandry (Apr 19 2019 at 18:14, on Zulip):

I'm not 100% sure what the proposal is, I guess

@nikomatsakis it's to go ahead and emit StorageDead for everything along drop and unwind paths, so we're preserving the information that the optimization needs

tmandry (Apr 19 2019 at 18:15, on Zulip):

we could consider only doing it for generators

RalfJ (Apr 19 2019 at 18:16, on Zulip):

RalfJ -- apologies for subscribing you to this stream, but I have a quick question -- you were at some point writing up some kind of semantics for StorageLive and StorageDead, right?

"writing up" is an overstatement^^

RalfJ (Apr 19 2019 at 18:16, on Zulip):

I have a blog post at https://www.ralfj.de/blog/2017/06/06/MIR-semantics.html

RalfJ (Apr 19 2019 at 18:16, on Zulip):

but mostly there is an implementation in Miri

tmandry (Apr 19 2019 at 18:19, on Zulip):

(I was also saying that, as an optimization, there might be ways to avoid creating new blocks of just StorageDeads by propagating those statements to other blocks, roughly speaking)

tmandry (Apr 19 2019 at 18:20, on Zulip):

but I'm not sure about this

tmandry (Apr 19 2019 at 18:37, on Zulip):

the reason we need to see StorageDead is because our local could have been borrowed

tmandry (Apr 19 2019 at 18:37, on Zulip):

and we can't ignore borrowed locals if we want to optimize await

nikomatsakis (Apr 19 2019 at 19:19, on Zulip):

Thanks @RalfJ =)

nikomatsakis (Apr 19 2019 at 19:20, on Zulip):

@tmandry have you seen that post? :) I'm skimming it now and then I'll re-read your comments...

nikomatsakis (Apr 19 2019 at 19:22, on Zulip):

Though I guess it doesn't discuss StorageDead :)

nikomatsakis (Apr 19 2019 at 19:22, on Zulip):

just the effects of redundant StorageLive

tmandry (Apr 19 2019 at 19:22, on Zulip):

^ yes

tmandry (Apr 19 2019 at 19:22, on Zulip):

I found it informative, just not for this particular question :)

nikomatsakis (Apr 19 2019 at 19:22, on Zulip):

well, @tmandry, I have no objection to trying to emit StorageDead, we should check the effects on perf though

tmandry (Apr 19 2019 at 19:22, on Zulip):

:thumbs_up:

nikomatsakis (Apr 19 2019 at 19:23, on Zulip):

I agree that we are somehow encoding scope information

nikomatsakis (Apr 19 2019 at 19:23, on Zulip):

But I also agree we probably want to go with using flow-control

tmandry (Apr 19 2019 at 19:26, on Zulip):

I'm thinking maybe eventually we can have an optimization pass that bubbles StorageDead up, based on liveness and other factors

tmandry (Apr 19 2019 at 19:27, on Zulip):

but I don't really have an idea of what that looks like :)

RalfJ (Apr 19 2019 at 20:22, on Zulip):

Though I guess it doesn't discuss StorageDead :)

if you have questions about what Miri does for StorageDead, ask and you shall receive an answer. ;)

tmandry (Apr 19 2019 at 21:19, on Zulip):

@RalfJ the question I had is, is it okay to encounter StorageDead twice in a row (or more) for the same var, or StorageDead without StorageLive?

Matthew Jasper (Apr 19 2019 at 21:29, on Zulip):

Double StorageDead already happens at the moment, and is handled properly.

RalfJ (Apr 19 2019 at 21:47, on Zulip):

Miri says yes that is okay

RalfJ (Apr 19 2019 at 21:47, on Zulip):

for whatever that is worth^^

tmandry (Apr 19 2019 at 22:23, on Zulip):

okay, thanks :)

tmandry (Apr 20 2019 at 00:31, on Zulip):

strangely, emitting these StorageDead statements causes NLL borrow check to emit fewer errors than it did before in a few tests

Taylor Cramer (Apr 20 2019 at 00:31, on Zulip):

I'd believe it

tmandry (Apr 20 2019 at 00:31, on Zulip):

like, it stops after the first error

Taylor Cramer (Apr 20 2019 at 00:31, on Zulip):

oh

Taylor Cramer (Apr 20 2019 at 00:31, on Zulip):

that... is not what I'd expect

tmandry (Apr 20 2019 at 00:31, on Zulip):

and when I comment that line out, then it emits the error for the next line :)

tmandry (Apr 20 2019 at 00:32, on Zulip):

this is only 3 tests, not everywhere

tmandry (Apr 20 2019 at 00:32, on Zulip):

all in ui/nll/user-annotations/

tmandry (Apr 20 2019 at 00:33, on Zulip):

maybe there is some heuristic to remove redundant errors somewhere in NLL?

tmandry (Apr 20 2019 at 00:35, on Zulip):

@nikomatsakis any idea?

tmandry (Apr 20 2019 at 00:38, on Zulip):

here are the failures... https://gist.github.com/tmandry/8f2ed1438391b80a0b91a2452b36826f

nikomatsakis (Apr 22 2019 at 18:43, on Zulip):

maybe there is some heuristic to remove redundant errors somewhere in NLL?

hmm I'm not sure

nikomatsakis (Apr 22 2019 at 18:44, on Zulip):

ah, actually, yeah I think there is some kind of duplicate suppression logic

nikomatsakis (Apr 22 2019 at 18:44, on Zulip):

@davidtwco or @Matthew Jasper may remember more precisely

nikomatsakis (Apr 22 2019 at 18:44, on Zulip):

but I remember StorageDead being relevant to errors somehow

nikomatsakis (Apr 22 2019 at 18:44, on Zulip):

I don't have time to dig in just now

Matthew Jasper (Apr 22 2019 at 18:45, on Zulip):

There is definitely some deduplication for storage dead errors.

Matthew Jasper (Apr 22 2019 at 18:50, on Zulip):

https://github.com/rust-lang/rust/blob/c21fbfe7e310b9055ed6b7c46b7d37b831a516e3/src/librustc_mir/borrow_check/error_reporting.rs#L701-L709

Matthew Jasper (Apr 22 2019 at 18:52, on Zulip):

That doesn't appear to be what's happening here though, as the borrow spans should be different

Matthew Jasper (Apr 22 2019 at 18:57, on Zulip):

Maybe here: https://github.com/rust-lang/rust/blob/c21fbfe7e310b9055ed6b7c46b7d37b831a516e3/src/librustc_mir/borrow_check/mod.rs#L930-L940

tmandry (Apr 23 2019 at 00:37, on Zulip):

@Matthew Jasper this definitely looks promising, thanks for pointing me to that!

tmandry (Apr 23 2019 at 00:39, on Zulip):

it seems like check_for_invalidation_at_exit does not do this suppression, and this function was handling checking those locals before I began emitting StorageDeads everywhere

tmandry (Apr 23 2019 at 00:40, on Zulip):

now access_place handles them which does suppression

tmandry (Apr 23 2019 at 00:40, on Zulip):

so the question is... what is the "correct" behavior?

tmandry (Apr 23 2019 at 00:41, on Zulip):

I'll push the updated tests to my upcoming PR and we can discuss there...

tmandry (Apr 23 2019 at 01:40, on Zulip):

can @nikomatsakis or someone who can start a try run on my PR #60187?

tmandry (Apr 23 2019 at 01:40, on Zulip):

we need to check the impact on perf of generating these StorageDead statements

tmandry (Apr 23 2019 at 01:46, on Zulip):

@Zoxc thanks :)

tmandry (Apr 23 2019 at 01:46, on Zulip):

@Zoxc also you'd be a great person to take a look at the PR :)

tmandry (Apr 24 2019 at 23:50, on Zulip):

@Zoxc hey.. I am trying to implement "only emit StorageDeads for generators", but I'm not sure how to get the information of _whether_ the code being lowered is in a generator

tmandry (Apr 24 2019 at 23:51, on Zulip):

today the generator-specific code just gets triggered if we hit a yield statement

tmandry (Apr 24 2019 at 23:51, on Zulip):

but I need to know for all the code when building the MIR

Zoxc (Apr 24 2019 at 23:54, on Zulip):

You can look up the body and see if it is a generator, https://github.com/rust-lang/rust/blob/master/src/librustc_mir/build/mod.rs#L134

tmandry (Apr 24 2019 at 23:55, on Zulip):

Perfect, thanks!

Taylor Cramer (Apr 29 2019 at 17:46, on Zulip):

@eddyb @Zoxc are either of you around and able to review https://github.com/rust-lang/rust/pull/59897 ? it has been blocked on review for a while now

Taylor Cramer (Apr 29 2019 at 17:47, on Zulip):

It's also blocking further work on an issue that is tagged as blocking the release of async/await

eddyb (Apr 30 2019 at 04:57, on Zulip):

ahh, my bad, it's been slipping through

eddyb (Apr 30 2019 at 04:58, on Zulip):

I'm opening it now

eddyb (Apr 30 2019 at 05:18, on Zulip):

done. I did request some feedback from @nikomatsakis and @mw but I don't think it's blocking

nikomatsakis (Apr 30 2019 at 17:01, on Zulip):

I'll take a look

tmandry (May 02 2019 at 20:41, on Zulip):

@Zoxc I replied to your comment about the approach of using variants for generators

tmandry (May 02 2019 at 20:41, on Zulip):

can you let me know if this makes sense?

tmandry (May 16 2019 at 18:49, on Zulip):

@Zoxc I think #60840 is ready to merge

Taylor Cramer (May 22 2019 at 15:29, on Zulip):

ping @eddyb can you take a look at https://github.com/rust-lang/rust/pull/60187 ? @Zoxc wanted you to review the layout code changes

eddyb (May 22 2019 at 15:46, on Zulip):

I guess. I likely can't get to the review today, but I'll try to look tomorrow

eddyb (May 22 2019 at 15:47, on Zulip):

I am vaguely worried about the optimization itself, and its correctness

Taylor Cramer (May 22 2019 at 15:54, on Zulip):

@eddyb if you have concerns, it would be especially helpful to let @tmandry know so we can resolve them as quickly as possible, since this is blocking async/await stabilization

eddyb (May 22 2019 at 15:54, on Zulip):

wait what

eddyb (May 22 2019 at 15:54, on Zulip):

how is this blocking?

eddyb (May 22 2019 at 15:54, on Zulip):

this is the first I hear of this

Taylor Cramer (May 22 2019 at 15:55, on Zulip):

The lang time decided to label the issue as blocking since it's causing stack overflows in a significant number of real usecases

Taylor Cramer (May 22 2019 at 15:55, on Zulip):

due to excessively large future types

eddyb (May 22 2019 at 15:55, on Zulip):

oh jfc

eddyb (May 22 2019 at 16:51, on Zulip):

okay I've looked and while I left a lot of comments, I'm happier now

eddyb (May 22 2019 at 16:52, on Zulip):

looks like @tmandry picked a more straight-forward solution than what my last long discussion with them contained

Taylor Cramer (May 22 2019 at 17:07, on Zulip):

@eddyb thanks for taking a look! :)

tmandry (May 31 2019 at 17:55, on Zulip):

@centril did you want a timer run for #61373?

centril (May 31 2019 at 18:02, on Zulip):

@tmandry I assumed you/the reviewer did and wanted to be helpful :slight_smile:

tmandry (May 31 2019 at 20:26, on Zulip):

ah ok. can't hurt :)

tmandry (Jun 07 2019 at 18:55, on Zulip):

@Zoxc and also @eddyb, would you mind taking a look at #60187? All the changes since last review are in new commits, starting with "Small review fixes"

tmandry (Jun 17 2019 at 21:57, on Zulip):

@Zoxc How would you feel about enabling the HaveBeenBorrowedLocals dataflow computation in all generators, not just immovable ones?

tmandry (Jun 17 2019 at 21:58, on Zulip):

I need the output of it in the new dataflow stage I'm doing (so that we don't allocate two storage slots in our generator for locals that get moved from)

tmandry (Jun 17 2019 at 21:59, on Zulip):

And while, technically, we could get away with not doing the HaveBeenBorrowedLocals stage, it leads to some highly coupled code with messy types

Zoxc (Jun 17 2019 at 22:01, on Zulip):

It's just for immovable generators

tmandry (Jun 17 2019 at 22:02, on Zulip):

er, immovable generators, sorry

tmandry (Jun 17 2019 at 22:02, on Zulip):

Considering that I'm adding a new dataflow pass that's going to be used in all generators, I wonder if it really makes sense anymore to skip this pass on movable generators

tmandry (Jun 17 2019 at 22:04, on Zulip):

(I guess you could make the argument that my pass is only for optimization, and maybe shouldn't run when optimizations are turned off..)

Zoxc (Jun 17 2019 at 22:04, on Zulip):

You shouldn't rely on it's output for movable generators though. It might be a sign that what you're doing is questionable =P

tmandry (Jun 17 2019 at 22:05, on Zulip):

Well, I'm not directly relying on it

tmandry (Jun 17 2019 at 22:05, on Zulip):

The problem is, my new dataflow pass depends on the output of that HaveBeenBorrowedLocals pass

tmandry (Jun 17 2019 at 22:06, on Zulip):

It's technically correct to ignore borrows, if the generator is movable and we only look at the results over yield points

tmandry (Jun 17 2019 at 22:06, on Zulip):

But.. that knowledge gets spread around the code right now :/

tmandry (Jun 17 2019 at 22:07, on Zulip):

Hmm, if we do gate my new pass on optimizations being enabled

tmandry (Jun 17 2019 at 22:08, on Zulip):

..we can run HaveBeenBorrowedLocals only for immovable generators OR if optimizations are enabled (so my pass can consume it)

Zoxc (Jun 17 2019 at 22:13, on Zulip):

What does your pass do?

tmandry (Jun 17 2019 at 22:22, on Zulip):

@Zoxc It's described in this comment

tmandry (Jun 17 2019 at 22:23, on Zulip):

It can be considered a refinement of MaybeStorageLive for the purpose of deciding whether a local needs to be saved or not

tmandry (Jun 17 2019 at 22:24, on Zulip):

(we can decide not to save a local if it is StorageLive in some cases, so it becomes two independent passes)

tmandry (Jun 17 2019 at 22:24, on Zulip):

for non-optimized builds, it's possible I can fall back to using MaybeStorageLive

tmandry (Jun 17 2019 at 22:25, on Zulip):

...but that can increase Future sizes 2x in most cases and 3x in some

tmandry (Jun 21 2019 at 02:19, on Zulip):

Okay, I think with #61922 the biggest wins for generator optimization are merged

tmandry (Jun 24 2019 at 19:09, on Zulip):

well, I mean written.. it's not merged yet :)

nikomatsakis (Jun 25 2019 at 17:00, on Zulip):

=)

tmandry (Jul 03 2019 at 01:12, on Zulip):

Okay, now it's merged!

Last update: Nov 18 2019 at 00:40UTC