Stream: t-compiler/wg-nll

Topic: #53178 optimize SCC computation


nikomatsakis (Aug 08 2018 at 16:58, on Zulip):

@Wesley Wiser is going to check this out

Wesley Wiser (Aug 09 2018 at 17:44, on Zulip):

@nikomatsakis I think I understand the task now. So outgoing_edges() takes a region and returns an iterator over all of the regions it outlives. If the region is 'static then of course it must outlive all regions by definition. So in this case, the iterator should loop over every region and return all of them. (Of course this only applies when D=Normal, D=Reverse is different.) I think the way to do this is something like (pseudocode)

for region in self.first_constraints {
  let mut next = self.next_constraints[region];
  while let Some(outlived) = next {
    next = self.next_constraints(outlived);
    yield outlived;
  }
}

Does that seem right?

Wesley Wiser (Aug 09 2018 at 17:44, on Zulip):

Easy link to graph.rs as of your PR

nikomatsakis (Aug 09 2018 at 17:45, on Zulip):

the first part is right, but I don't understand the code example

nikomatsakis (Aug 09 2018 at 17:46, on Zulip):

it seems to be iterating over the constraint linked list?

nikomatsakis (Aug 09 2018 at 17:46, on Zulip):

there are various ways you could do this of course

nikomatsakis (Aug 09 2018 at 17:47, on Zulip):

but I suppose

for region in self.first_constraints.indices() {
  yield region;
}
nikomatsakis (Aug 09 2018 at 17:47, on Zulip):

might do it

Wesley Wiser (Aug 09 2018 at 17:48, on Zulip):

Hmm. Perhaps I've misunderstood the Edges iterator

Wesley Wiser (Aug 09 2018 at 17:49, on Zulip):

I thought it was necessary to iterator over the the next_constraints because for a constraint like R1: R2 + R3, that's where the R2 and R3 regions will come from

nikomatsakis (Aug 09 2018 at 17:49, on Zulip):

no I mean

nikomatsakis (Aug 09 2018 at 17:49, on Zulip):

that is how the edges iterator works

nikomatsakis (Aug 09 2018 at 17:50, on Zulip):

I'm not really sure what pseudocode you are showing me :)

nikomatsakis (Aug 09 2018 at 17:50, on Zulip):

I thought you were talking about the additional iteration that would be needed

Wesley Wiser (Aug 09 2018 at 17:51, on Zulip):

Oh sorry

I mean that the complete output of the iterator when given a 'static region should be next_constraints + first_constraints.

Wesley Wiser (Aug 09 2018 at 17:51, on Zulip):

It basically needs to return all of the constraints right?

nikomatsakis (Aug 09 2018 at 17:51, on Zulip):

well

nikomatsakis (Aug 09 2018 at 17:51, on Zulip):

we are talking about augmenting the thing that iterates over regions, right?

Wesley Wiser (Aug 09 2018 at 17:52, on Zulip):

Edges yes

nikomatsakis (Aug 09 2018 at 17:52, on Zulip):

in that case, it's enough for 'static to yield all the regions just once

nikomatsakis (Aug 09 2018 at 17:52, on Zulip):

but for every other region, it would want to walk over the constraints and map to the sub endpoint

nikomatsakis (Aug 09 2018 at 17:52, on Zulip):

otherwise, you'll just wind up with duplicate edges I guess

nikomatsakis (Aug 09 2018 at 17:52, on Zulip):

doesn't hurt

nikomatsakis (Aug 09 2018 at 17:52, on Zulip):

also not needed

nikomatsakis (Aug 09 2018 at 17:53, on Zulip):

so I guess I would say

nikomatsakis (Aug 09 2018 at 17:53, on Zulip):

er, sorry

nikomatsakis (Aug 09 2018 at 17:53, on Zulip):

not Edges

nikomatsakis (Aug 09 2018 at 17:53, on Zulip):

note that the SCC is not built from Edges, that's just a building block

nikomatsakis (Aug 09 2018 at 17:54, on Zulip):

Successors is the one we use for the SCC

nikomatsakis (Aug 09 2018 at 17:54, on Zulip):

and it yields up not constraints but regions

nikomatsakis (Aug 09 2018 at 17:54, on Zulip):

well really the point is RegionGraph

Wesley Wiser (Aug 09 2018 at 17:55, on Zulip):

Ok got it.

My brain skipped right past Successors and I was just looking at Edges

Wesley Wiser (Aug 09 2018 at 17:56, on Zulip):

:face_palm:

nikomatsakis (Aug 09 2018 at 17:56, on Zulip):

honestly I think the easiest thing to do might be to make Yet Another Layer :P

nikomatsakis (Aug 09 2018 at 17:56, on Zulip):

in particular, there are these "wrapper traits" here:

nikomatsakis (Aug 09 2018 at 17:56, on Zulip):

https://github.com/rust-lang/rust/blob/31fe3df6543566f5671da4d78b381b9d59f2d096/src/librustc_mir/borrow_check/nll/constraints/graph.rs#L176-L198

nikomatsakis (Aug 09 2018 at 17:56, on Zulip):

those are the things that define the graph the SCC computation is based on

nikomatsakis (Aug 09 2018 at 17:57, on Zulip):

I wonder if we want another struct, let's call it AugmentedRegionGraph, sort of like

struct AugmentedRegionGraph {
    graph: NormalRegionGraph, // no need to support other directions
}
nikomatsakis (Aug 09 2018 at 17:57, on Zulip):

and then implement the graph traits for that

nikomatsakis (Aug 09 2018 at 17:57, on Zulip):

the "successors" relation would then return something like

nikomatsakis (Aug 09 2018 at 17:58, on Zulip):
let static_successors = if node == STATIC {
    Some(STATIC .. NUM_REGIONS)
} else {
    None
};

let normal_successors = self.graph.outgoing_regions(node);

static_successors
  .into_iter()
  .flat_map(|range| range)
  .chain(normal_successors)
nikomatsakis (Aug 09 2018 at 17:59, on Zulip):

Ok got it.

My brain skipped right past Successors and I was just looking at Edges

Successors is really just a "mapped" version of Edges anyhow

Wesley Wiser (Aug 09 2018 at 17:59, on Zulip):

And NormalRegionGraph is just a RegionGraph<'s, Normal>?

nikomatsakis (Aug 09 2018 at 17:59, on Zulip):

yeah

nikomatsakis (Aug 09 2018 at 17:59, on Zulip):

that's an existing alias I think

nikomatsakis (Aug 09 2018 at 17:59, on Zulip):

er, I guess it's not

nikomatsakis (Aug 09 2018 at 17:59, on Zulip):

well I meant that :)

Wesley Wiser (Aug 09 2018 at 18:00, on Zulip):

I think there's just {Normal|Reverse}ConstraintGraph

nikomatsakis (Aug 09 2018 at 18:00, on Zulip):

yes, you are correct

Wesley Wiser (Aug 09 2018 at 18:00, on Zulip):

Gotcha

Wesley Wiser (Aug 09 2018 at 18:01, on Zulip):

Is STATIC defined somewhere? RegionVid doesn't seem to define it https://doc.rust-lang.org/nightly/nightly-rustc/rustc/ty/struct.RegionVid.html

nikomatsakis (Aug 09 2018 at 18:02, on Zulip):

no, it's universal_regions.fr_static I think

nikomatsakis (Aug 09 2018 at 18:02, on Zulip):

it is -- in practice -- always zero

nikomatsakis (Aug 09 2018 at 18:02, on Zulip):

really the range I defined is actually self.first_contraints.indices() or whatever

Wesley Wiser (Aug 09 2018 at 18:02, on Zulip):

That looks correct

nikomatsakis (Aug 09 2018 at 18:02, on Zulip):

we have a universal_regions in this code? I forget

nikomatsakis (Aug 09 2018 at 18:02, on Zulip):

we could make it a true constant

nikomatsakis (Aug 09 2018 at 18:03, on Zulip):

seems like we don't have it here

nikomatsakis (Aug 09 2018 at 18:03, on Zulip):

we could pass it down though when constructing the graph

nikomatsakis (Aug 09 2018 at 18:03, on Zulip):

i.e., we could add an argument to compute_sccs

Wesley Wiser (Aug 09 2018 at 18:03, on Zulip):

Ok. That should be easy enough

nikomatsakis (Aug 09 2018 at 18:04, on Zulip):

I'd probably just pass down static_vid: RegionVid

nikomatsakis (Aug 09 2018 at 18:04, on Zulip):

and not the whole struct thing

Wesley Wiser (Aug 09 2018 at 18:04, on Zulip):

right

Wesley Wiser (Aug 09 2018 at 18:05, on Zulip):

Ok. Thanks for your time!! I'm going to work on this tonight and see how far I get.

nikomatsakis (Aug 09 2018 at 18:05, on Zulip):

:guitar:

nikomatsakis (Aug 09 2018 at 18:05, on Zulip):

let me know if you hit any roadblocks :)

Wesley Wiser (Aug 09 2018 at 18:06, on Zulip):

Will do! :)

Jake Goulding (Aug 09 2018 at 18:54, on Zulip):
for region in self.first_constraints.indices() {
  yield region;
}

@nikomatsakis I assume you were using pseudocode, but does the compiler yet use generators for things?

nikomatsakis (Aug 09 2018 at 18:54, on Zulip):

we do not

nikomatsakis (Aug 09 2018 at 18:55, on Zulip):

I've thought about it...

Jake Goulding (Aug 09 2018 at 18:56, on Zulip):

Any particular reason to avoid it? Since async/await uses it so much, seems like getting more usages would be a good thing.

nikomatsakis (Aug 09 2018 at 18:56, on Zulip):

not really

nikomatsakis (Aug 09 2018 at 18:57, on Zulip):

I don't think there is a convenient way to make an iterator yet

nikomatsakis (Aug 09 2018 at 18:57, on Zulip):

but we could add one

nikomatsakis (Aug 09 2018 at 18:57, on Zulip):

I think when I was last going to try it, though, the "borrowck-enabled" variant didn't yet exist

nikomatsakis (Aug 09 2018 at 18:57, on Zulip):

now it would be more ergonomic

Jake Goulding (Aug 09 2018 at 18:58, on Zulip):

Heh, I wrote the generator->iterator adapter months (years?) ago for a SO question, I've always been surprised that wasn't in the stdlib

nikomatsakis (Aug 10 2018 at 10:10, on Zulip):

@Wesley Wiser how'd it go?

Wesley Wiser (Aug 10 2018 at 13:33, on Zulip):

@nikomatsakis Ok, I guess. I've added the code we talked about yesterday and wired it up to compute_sccs(). The code builds and the compiler bootstraps but there's some NLL ui-tests that are failing. I didn't have time to investigate them very much.

nikomatsakis (Aug 10 2018 at 13:35, on Zulip):

ok

nikomatsakis (Aug 10 2018 at 13:35, on Zulip):

feel free to open a WIP PR

Wesley Wiser (Aug 10 2018 at 13:37, on Zulip):

I'll probably do that this evening. The tests finished running right as I was about to go to bed so I didn't have time to investigate further.

Wesley Wiser (Aug 10 2018 at 13:38, on Zulip):

A quick glance at the errors looked like there were changes in some of the errors referencing the 'static lifetime. It didn't look correct to me at first glance but I find the test output hard to read anyway.

Wesley Wiser (Aug 10 2018 at 13:38, on Zulip):

I'll dig in more tonight

nikomatsakis (Aug 10 2018 at 13:42, on Zulip):

A quick glance at the errors looked like there were changes in some of the errors referencing the 'static lifetime. It didn't look correct to me at first glance but I find the test output hard to read anyway.

ah, well, it might be that this change legitimately changes the heuristics for printing region errors

Wesley Wiser (Aug 10 2018 at 13:43, on Zulip):

Gotcha. I'll run the failing tests manually tonight so I can compare the complete output side-by-side and see if it's actually an issue or not.

Wesley Wiser (Aug 10 2018 at 13:44, on Zulip):

Since this is a perf optimization, I guess the best test that it's "working" is to compile html5ever and look at the compile times right?

nikomatsakis (Aug 10 2018 at 13:46, on Zulip):

locally? yeah, that would be possible

nikomatsakis (Aug 10 2018 at 13:46, on Zulip):

we can also have the official perf server test it

nikomatsakis (Aug 10 2018 at 13:47, on Zulip):

once we are satisfied it's correct :)

nikomatsakis (Aug 10 2018 at 13:47, on Zulip):

you probably want to build on https://github.com/rust-lang/rust/pull/53177 in terms of testing perf

nikomatsakis (Aug 10 2018 at 13:47, on Zulip):

which will..hopefully...land soon?

Wesley Wiser (Aug 10 2018 at 13:48, on Zulip):

Yeah, I'm working on top of your branch :)

nikomatsakis (Aug 10 2018 at 13:49, on Zulip):

k

Wesley Wiser (Aug 16 2018 at 14:18, on Zulip):

I think you're right about the heuristics in error reporting changing. It looks to me like the error is still being reported correctly, but it's using the wrong wording. I tried tracking it down last night and couldn't quite get it but I have a lead so maybe I can fix it tonight.

Wesley Wiser (Aug 16 2018 at 14:18, on Zulip):

Would it be possible to go ahead and get a perf run for the changes? I'm interested in seeing if the speedup you were expecting to see happens.

Wesley Wiser (Aug 16 2018 at 14:19, on Zulip):

I also left a question on the PR for you.

Wesley Wiser (Aug 16 2018 at 14:19, on Zulip):

@nikomatsakis ^^

nikomatsakis (Aug 16 2018 at 14:25, on Zulip):

yes, we can do a perf run

nikomatsakis (Aug 16 2018 at 14:25, on Zulip):

sorry, this week has been crazy busy

Wesley Wiser (Aug 16 2018 at 14:25, on Zulip):

No problem! :)

Wesley Wiser (Aug 16 2018 at 14:26, on Zulip):

Do the tests need to pass to get a try build out? They're currently failing because of the changed error messages.

nikomatsakis (Aug 16 2018 at 14:26, on Zulip):

yeah, I'm not sure

nikomatsakis (Aug 16 2018 at 14:26, on Zulip):

I always forget

nikomatsakis (Aug 16 2018 at 14:27, on Zulip):

probably best to just fix the tests

Wesley Wiser (Aug 16 2018 at 14:27, on Zulip):

Ah, ok.

nikomatsakis (Aug 16 2018 at 14:27, on Zulip):

if it's just UI changes, you can run ./x.py test src/test/ui --bless

nikomatsakis (Aug 16 2018 at 14:27, on Zulip):

sorry, by "fix the tests" I mean "modify them to reflect the changes"

Wesley Wiser (Aug 16 2018 at 14:27, on Zulip):

Gotcha

Wesley Wiser (Aug 16 2018 at 14:28, on Zulip):

I'll do that tonight so maybe we can get a perf run in tomorrow.

nikomatsakis (Aug 16 2018 at 14:28, on Zulip):

@simulacrum does bors try require tests to pass?

nikomatsakis (Aug 16 2018 at 14:28, on Zulip):

in particular, in order to produce an artifact usable by perf...?

nikomatsakis (Aug 16 2018 at 14:28, on Zulip):

now that I think about it, I think maybe it doesn't

Wesley Wiser (Aug 16 2018 at 14:29, on Zulip):

I don't know what kind of speedup you were hoping to see from that change. On my pc, there is a speed up to html5ever but it doesn't seem that big.

Wesley Wiser (Aug 16 2018 at 14:29, on Zulip):

I couldn't figure out how to build just html5ever without its dependencies so the total build time is definitely skewed by them.

lqd (Aug 16 2018 at 14:32, on Zulip):

after a non-incremental check, something like touch src/lib.rs && CARGO_INCREMENTAL=0 cargo rustc --profile check --lib -- -Zborrowck=mir -Ztwo-phase-borrows should do the trick

Wesley Wiser (Aug 16 2018 at 14:33, on Zulip):

@lqd Ah, perfect. Thanks!

lqd (Aug 16 2018 at 15:30, on Zulip):

does bors try require tests to pass?

since I had the same question minutes earlier and mine just succeeded, it appears that try builds don't need to have all the tests pass indeed :) I think perf could be ran on #53327 as-is

Wesley Wiser (Aug 17 2018 at 02:07, on Zulip):

Ok. With #53327 html5ever drops from 4.2 seconds to compile on my pc to 4.0 seconds in -Zborrowck=mir -Ztwo-phase-borrows mode.

lqd (Aug 17 2018 at 07:07, on Zulip):

so it only needs a rust-timer command :) cc @simulacrum @kennytm

kennytm (Aug 17 2018 at 07:45, on Zulip):

done @lqd

lqd (Aug 17 2018 at 08:08, on Zulip):

@kennytm thanks a lot :)

nikomatsakis (Aug 22 2018 at 17:59, on Zulip):

@Wesley Wiser so I made a few edits to your PR...

nikomatsakis (Aug 22 2018 at 17:59, on Zulip):

converting it to avoid Box and fix the lifetime issues

nikomatsakis (Aug 22 2018 at 17:59, on Zulip):

I guess I'll just push them

nikomatsakis (Aug 22 2018 at 18:00, on Zulip):

I was getting "nerd swiped" by improvements to IndexVec to make it read nicer but I think I will stop here ;)

Wesley Wiser (Aug 22 2018 at 18:23, on Zulip):

@nikomatsakis Thanks! I'll take a look. I've been trying to track down the error reporting regressions that are failing the ui tests.

nikomatsakis (Aug 22 2018 at 18:27, on Zulip):

@Wesley Wiser ok -- can you push the updated UI tests to the PR? I'd like to see the full diffs, and that's the easiest way.

nikomatsakis (Aug 22 2018 at 18:27, on Zulip):

I guess I can build and run locally too...

Wesley Wiser (Aug 22 2018 at 18:30, on Zulip):

The issue is here. Before my change, best_choice would be Some(_) but now it's None because this removes constraints in the same SCC. With my changes, they're in the same SCC and so this code runs when it normally wouldn't.

Wesley Wiser (Aug 22 2018 at 18:31, on Zulip):

@nikomatsakis I'll do that first thing tonight when I get back to my pc

nikomatsakis (Aug 22 2018 at 18:32, on Zulip):

ok

nikomatsakis (Aug 22 2018 at 18:32, on Zulip):

I can certainly imagine that this would influence those results

nikomatsakis (Aug 23 2018 at 18:42, on Zulip):

ok @Wesley Wiser so I see the delta now. It makes sense to me how this is arising: it's fundamentally just kind of tricky to figure out which points are "user visible" conversions and which are not. The SCC is clearly an imperfect heuristic here... but I'm not sure whether to hold up the PR on that basis or not.

nikomatsakis (Aug 23 2018 at 18:44, on Zulip):

do you want to rebase, in any case?

Wesley Wiser (Aug 23 2018 at 18:50, on Zulip):

I certainly can yeah. Do you want me to keep your commits separate or squash it all together?

Wesley Wiser (Aug 23 2018 at 18:51, on Zulip):

I'm personally pretty bummed by the regression in error messages. I think they used to be really good and now they're pretty meh. It's certainly your call though if you want to merge as-is or not. :)

Wesley Wiser (Aug 23 2018 at 18:52, on Zulip):

I spent last night trying to come up with a better heuristic but I haven't thought of anything yet.

nikomatsakis (Aug 23 2018 at 18:57, on Zulip):

I certainly can yeah. Do you want me to keep your commits separate or squash it all together?

squash is fine

nikomatsakis (Aug 23 2018 at 18:57, on Zulip):

I spent last night trying to come up with a better heuristic but I haven't thought of anything yet.

well, certainly we could compute the SCC without the augmentation and use that

nikomatsakis (Aug 23 2018 at 18:57, on Zulip):

it doesn't .. feel "theoretically" better

nikomatsakis (Aug 23 2018 at 18:57, on Zulip):

it just sort of "happens to be"

nikomatsakis (Aug 23 2018 at 18:58, on Zulip):

but this is all a heuristic, so...

nikomatsakis (Aug 23 2018 at 18:58, on Zulip):

(that is, we could compute this lazilly when we have to report errors, I mean)

nikomatsakis (Aug 23 2018 at 18:58, on Zulip):

the other option I can see -- well, I have to review the code -- but it would basically be that we don't just consider whether the sub/sup are in the same SCC, but we also look at the kind of edge

nikomatsakis (Aug 23 2018 at 18:58, on Zulip):

do you have plots of the region graphs in those examples?

Wesley Wiser (Aug 23 2018 at 19:08, on Zulip):

@nikomatsakis Is there a tool to dump that info?

nikomatsakis (Aug 23 2018 at 20:05, on Zulip):

-Zdump-mir=nll I think gives dot files

nikomatsakis (Aug 23 2018 at 20:05, on Zulip):

in the mir_dump directory

nikomatsakis (Aug 23 2018 at 20:05, on Zulip):

IIRC

nikomatsakis (Aug 24 2018 at 17:53, on Zulip):

ok @Wesley Wiser consensus seems to be merging the PR as is — I hadn't realized there were ICEs etc though

nikomatsakis (Aug 24 2018 at 17:54, on Zulip):

I guess you rebased, though?

Wesley Wiser (Aug 24 2018 at 18:12, on Zulip):

Yeah, I rebased on master last night

Wesley Wiser (Aug 24 2018 at 18:12, on Zulip):

I didn't realize either since they were mixed into the other failing tests

Wesley Wiser (Aug 24 2018 at 18:13, on Zulip):

I spent about an hour last night looking into the ICEs but it's slow going. I'm completely unfamiliar with this code.

nikomatsakis (Aug 24 2018 at 18:13, on Zulip):

ok, I can take a look in a bit

Wesley Wiser (Aug 24 2018 at 18:13, on Zulip):

Much appreciated! :)

Wesley Wiser (Aug 24 2018 at 18:17, on Zulip):

The stack trace showed that find_constraint_paths_between_regions() (here) was failing to find the path and thus returning None which was getting unwrapped in best_blame_constraint() (here) when called from find_outlives_blame_span() (here)

nikomatsakis (Aug 24 2018 at 19:07, on Zulip):

ok, I see how that could happen.

nikomatsakis (Aug 24 2018 at 19:07, on Zulip):

the problem here is that we are walking the "unaugmented" graph, essentially

nikomatsakis (Aug 24 2018 at 19:07, on Zulip):

let me look at the code just a bit more closely

nikomatsakis (Aug 24 2018 at 19:09, on Zulip):

I guess if you have R1: R2: 'static then we would have a "synthetic" edge like 'static: R3

nikomatsakis (Aug 24 2018 at 19:10, on Zulip):

so if we are then searching for a path from R1 to R3, we won't find it

nikomatsakis (Aug 24 2018 at 19:10, on Zulip):

one option is just to search the augmented graph

nikomatsakis (Aug 24 2018 at 19:11, on Zulip):

that may have other effects on error msgs

nikomatsakis (Aug 24 2018 at 19:11, on Zulip):

another option would be to look for "r3 or 'static"

nikomatsakis (Aug 24 2018 at 19:12, on Zulip):

that would fix the ICE but it feels...like the concern is "leaking" a bit more than I might like

nikomatsakis (Aug 24 2018 at 19:12, on Zulip):

I am wondering

nikomatsakis (Aug 24 2018 at 19:12, on Zulip):

another option might be to tweak our approach

nikomatsakis (Aug 24 2018 at 19:13, on Zulip):

and just add the extra constraints

nikomatsakis (Aug 24 2018 at 19:13, on Zulip):

into the list of constraints

nikomatsakis (Aug 24 2018 at 19:13, on Zulip):

but that also feels meh

nikomatsakis (Aug 24 2018 at 19:30, on Zulip):

(e.g., there are a lot of variables, seem silly to materialize all those constraints)

nikomatsakis (Aug 24 2018 at 19:31, on Zulip):

hmm maybe this setup is a bit silly altogether

Jake Goulding (Aug 24 2018 at 19:32, on Zulip):
nikomatsakis (Aug 24 2018 at 19:35, on Zulip):

ok @Wesley Wiser so... right now we have these various layers. There is the "constraint graph", which yields up constraint indices. Then you can combine that with the constraint set to get the region graph.

One annoying thing here is that, because we yield up constraint indices, if we want to make fake constraints, say, that connect 'static to other lifetimes, then we have to add them into the vector.

Maybe instead the constraint graph iterator should take a &'iter ConstraintSet. Then the iterator can yield up OutlivesConstraint structs by value. This way, we can generate OutlivesConstraint { sup: static, sub: other_region, locations: Locations::All } for those implied 'static constraints.

We can then do that always, in the base layer of the graph.

Then we can remove the "augmented-region-graph" concept.

Moreover, this might help with the other regressions we were seeing, since maybe we can tweak the locations value and help our "graph walker" to identify interesting points again (maybe -- I might rather take a different approach).

nikomatsakis (Aug 24 2018 at 19:36, on Zulip):

I think I'll copy this into the PR so you don't have to read all my chatter

Wesley Wiser (Aug 24 2018 at 19:40, on Zulip):

(reading through it now)

Wesley Wiser (Aug 24 2018 at 20:15, on Zulip):

@nikomatsakis So, I think I get the general idea. A few questions:

You said "constraint graph iterator" is that the Edges struct which impls Iterator<Type = ConstraintIndex>? Are you saying I should change it to impl Iterator<Type = OutlivesConstraint>? Or is this a new iterator that should be created?

We can do that always, in the base layer of the graph

Are you saying we'd add the outlives constraints in ConstraintGraph? Or that the constraint graph iterator is responsible for creating them when iterated?

nikomatsakis (Aug 24 2018 at 20:17, on Zulip):

@Wesley Wiser

Are you saying I should change it to impl Iterator<Type = OutlivesConstraint>?

Yes

Or that the constraint graph iterator is responsible for creating them when iterated?

This, I think

Wesley Wiser (Aug 24 2018 at 20:19, on Zulip):

Ok :thumbs_up:

Wesley Wiser (Aug 24 2018 at 20:22, on Zulip):

I think that's enough for me to get started working on that tonight. I'm sure I'll probably have questions for you on Monday :laughing:

nikomatsakis (Aug 24 2018 at 20:24, on Zulip):

sounds good! =)

Wesley Wiser (Aug 24 2018 at 20:24, on Zulip):

Thanks for all your help!

Wesley Wiser (Aug 27 2018 at 03:40, on Zulip):

@nikomatsakis That was a really good idea! I tried the other strategy as you said and it works much better. After the changes, there were only two failing ui tests and they don't seem like significant regressions either. I'm unsure of the perf so we'll definitely need to rerun that.

nikomatsakis (Aug 27 2018 at 11:12, on Zulip):

@Wesley Wiser left some comments; there may be a bug lurking there too though, given that the perf results are "different" than before

Wesley Wiser (Aug 28 2018 at 14:57, on Zulip):

@nikomatsakis I implemented your feedback. The perf results look much better now.

nikomatsakis (Aug 28 2018 at 15:03, on Zulip):

great!

nikomatsakis (Aug 28 2018 at 15:04, on Zulip):

of course now the question is what's up with ucd-check :P

nikomatsakis (Aug 28 2018 at 15:06, on Zulip):

I guess I was wrong about the "extra errors"

nikomatsakis (Aug 28 2018 at 15:08, on Zulip):

oh the max-rss wins are huge though

Wesley Wiser (Aug 28 2018 at 15:09, on Zulip):

Yeah, I can try profiling it tonight and see if anything jumps out to me.

Wesley Wiser (Aug 28 2018 at 15:10, on Zulip):

ucd-check that is

nikomatsakis (Aug 28 2018 at 15:10, on Zulip):

it's curious but probably not that big a deal

nikomatsakis (Aug 28 2018 at 15:10, on Zulip):

I left a few comments

nikomatsakis (Aug 28 2018 at 15:10, on Zulip):

to that effect:)

nikomatsakis (Aug 28 2018 at 15:11, on Zulip):

nice that, after this, html5ever gets to 115% or so

Wesley Wiser (Aug 28 2018 at 15:13, on Zulip):

Yeah, the html5ever results are exciting

Wesley Wiser (Aug 28 2018 at 15:14, on Zulip):

I don't know if you noticed but the "extra errors" issue seems to have gotten worse :face_palm:

nikomatsakis (Aug 28 2018 at 15:16, on Zulip):

hmm curious

Jake Goulding (Aug 28 2018 at 15:22, on Zulip):

perf wins link please?

Jake Goulding (Aug 28 2018 at 15:27, on Zulip):

Ah - https://perf.rust-lang.org/compare.html?start=f33921ba58754d1bfbaf483ddc6dc9dffdcd4de7&end=3bf463eacebe287b54bbfa28fd64168e41c4446c

nikomatsakis (Aug 28 2018 at 15:29, on Zulip):

Er, sorry, . Yes comparison URL

lqd (Aug 28 2018 at 16:02, on Zulip):

ucd-check is only 1 run, so more sensitive to weirdness imo :)

nikomatsakis (Aug 28 2018 at 16:15, on Zulip):

ah makes sense

Wesley Wiser (Aug 28 2018 at 16:33, on Zulip):

Oh interesting

Wesley Wiser (Aug 28 2018 at 16:34, on Zulip):

I'll still take a look tonight and see if there's any low hanging fruit but that makes me feel better

Wesley Wiser (Aug 29 2018 at 00:51, on Zulip):

I'm not seeing anything pop out to me in perf.

nikomatsakis (Aug 29 2018 at 00:53, on Zulip):

the real question is if we can suppress the duplicate errors somehow

nikomatsakis (Aug 29 2018 at 00:53, on Zulip):

seems like it should be true

Wesley Wiser (Aug 31 2018 at 04:00, on Zulip):

So I've tried comparing a log of rustc with and without my changes. One thing that stands out to me is this:

Before:

rustc_mir::borrow_check::nll::region_infer::error_reporting: report_error: fr_is_local=true outlived_fr_is_local=false category=Assignment
rustc_mir::borrow_check::nll::region_infer::error_reporting::var_name: get_var_name_and_span_for_region(fr='_#1r)
rustc_mir::borrow_check::nll::region_infer::error_reporting::var_name: get_var_name_and_span_for_region: attempting upvar
rustc_mir::borrow_check::nll::region_infer::error_reporting::var_name: get_var_name_and_span_for_region: attempting argument
rustc_mir::borrow_check::nll::region_infer::error_reporting::var_name: get_argument_index_for_region: arg_ty = std::boxed::Box<<&T as A>::X>
rustc_mir::borrow_check::nll::region_infer::error_reporting::var_name: get_argument_index_for_region: found '_#1r in argument 0 which has type std::boxed::Box<<&T as A>::X>
rustc_mir::borrow_check::nll::region_infer::error_reporting::var_name: get_argument_name_and_span_for_region: argument_local=_1
rustc_mir::borrow_check::nll::region_infer::error_reporting::var_name: get_argument_name_and_span_for_region: argument_name=Some(s) argument_span=issue-50716.rs:20:24: 20:25
rustc_mir::borrow_check::nll::region_infer::error_reporting::var_name: get_var_name_and_span_for_region(fr='_#0r)
rustc_mir::borrow_check::nll::region_infer::error_reporting::var_name: get_var_name_and_span_for_region: attempting upvar
rustc_mir::borrow_check::nll::region_infer::error_reporting::var_name: get_var_name_and_span_for_region: attempting argument
rustc_mir::borrow_check::nll::region_infer::error_reporting::var_name: get_argument_index_for_region: arg_ty = std::boxed::Box<<&T as A>::X>
rustc_mir::borrow_check::nll::region_infer: check_universal_region(fr='_#2r)
rustc_mir::borrow_check::nll::region_infer: check_universal_region(fr='_#3r)

After:

rustc_mir::borrow_check::nll::region_infer::error_reporting: report_error: fr_is_local=true outlived_fr_is_local=false category=Assignment
rustc_mir::borrow_check::nll::region_infer::error_reporting::var_name: get_var_name_and_span_for_region(fr='_#1r)
rustc_mir::borrow_check::nll::region_infer::error_reporting::var_name: get_var_name_and_span_for_region: attempting upvar
rustc_mir::borrow_check::nll::region_infer::error_reporting::var_name: get_var_name_and_span_for_region: attempting argument
rustc_mir::borrow_check::nll::region_infer::error_reporting::var_name: get_argument_index_for_region: arg_ty = std::boxed::Box<<&T as A>::X>
rustc_mir::borrow_check::nll::region_infer::error_reporting::var_name: get_argument_index_for_region: found '_#1r in argument 0 which has type std::boxed::Box<<&T as A>::X>
rustc_mir::borrow_check::nll::region_infer::error_reporting::var_name: get_argument_name_and_span_for_region: argument_local=_1
rustc_mir::borrow_check::nll::region_infer::error_reporting::var_name: get_argument_name_and_span_for_region: argument_name=Some(s) argument_span=issue-50716.rs:20:24: 20:25
rustc_mir::borrow_check::nll::region_infer::error_reporting::var_name: get_var_name_and_span_for_region(fr='_#0r)
rustc_mir::borrow_check::nll::region_infer::error_reporting::var_name: get_var_name_and_span_for_region: attempting upvar
rustc_mir::borrow_check::nll::region_infer::error_reporting::var_name: get_var_name_and_span_for_region: attempting argument
rustc_mir::borrow_check::nll::region_infer::error_reporting::var_name: get_argument_index_for_region: arg_ty = std::boxed::Box<<&T as A>::X>
rustc_mir::borrow_check::nll::region_infer: check_universal_region: fr='_#1r does not outlive shorter_fr='_#2r

The last message comes from here.

I'm not sure what to investigate next.

Wesley Wiser (Aug 31 2018 at 14:16, on Zulip):

@nikomatsakis Does the above info mean anything to you? I'm still working on figuring it out but I thought I'd ask in case it was obvious to you

nikomatsakis (Aug 31 2018 at 14:17, on Zulip):

it's not obvious to me, no

nikomatsakis (Aug 31 2018 at 14:18, on Zulip):

I was hoping to look at it today, presuming you don't find it first :)

Wesley Wiser (Aug 31 2018 at 14:20, on Zulip):

I'm at work right now so I won't be able to look at it until tonight :)

Wesley Wiser (Aug 31 2018 at 14:20, on Zulip):

That was just how far I got last night

Wesley Wiser (Aug 31 2018 at 14:21, on Zulip):

I'm kind of wondering if this comment you made is more significant than we thought:

I mean, to be strictly consistent, we would basically add an "extra" static constraint to every region in a reverse graph, but it wouldn't actually matter to any of the consumers.

Maybe it does matter and we need to be doing that?

Wesley Wiser (Aug 31 2018 at 14:21, on Zulip):

That's just a guess though

nikomatsakis (Aug 31 2018 at 14:22, on Zulip):

I can't see how

nikomatsakis (Aug 31 2018 at 14:22, on Zulip):

the reverse graph is used in just one place

nikomatsakis (Aug 31 2018 at 14:22, on Zulip):

which is to avoid computing liveness

nikomatsakis (Aug 31 2018 at 14:22, on Zulip):

I don't think it is used in the error reporting code at all

nikomatsakis (Aug 31 2018 at 14:22, on Zulip):

but .. I may be overlooking something :)

Wesley Wiser (Aug 31 2018 at 14:23, on Zulip):

It's not used by universal_regions_outlived_by() or universal_region_relations .outlives()?

Wesley Wiser (Aug 31 2018 at 14:24, on Zulip):

(I don't know, just wondering)

nikomatsakis (Aug 31 2018 at 14:25, on Zulip):

it is not

Wesley Wiser (Aug 31 2018 at 14:25, on Zulip):

On a side note, is there documentation for the NLL borrow checker somewhere? I tried looking in the rustc-guide when I started working on this but I didn't see anything there.

Wesley Wiser (Aug 31 2018 at 14:25, on Zulip):

gotcha

nikomatsakis (Aug 31 2018 at 14:25, on Zulip):

not really. I'm working actually literally this second on writing more docs...

Wesley Wiser (Aug 31 2018 at 14:25, on Zulip):

I can read the code and see what it's doing but I have no idea why...

nikomatsakis (Aug 31 2018 at 14:25, on Zulip):

...but there is a lot to document :)

Wesley Wiser (Aug 31 2018 at 14:25, on Zulip):

Ah :thumbs_up: :thumbs_up:

nikomatsakis (Aug 31 2018 at 14:25, on Zulip):

there are docs scattered throughout the code

nikomatsakis (Aug 31 2018 at 14:27, on Zulip):

of course writing docs just makes me want to refactor everything :P

Wesley Wiser (Aug 31 2018 at 14:28, on Zulip):

The eternal struggle

Wesley Wiser (Aug 31 2018 at 14:30, on Zulip):

If you jot down what you want refactored, I'd be happy to work on that after we get this issue resolved :)
I love refactoring :ferris:

nikomatsakis (Aug 31 2018 at 15:06, on Zulip):

woohoo :)

nikomatsakis (Aug 31 2018 at 15:06, on Zulip):

the challenge here is not knowing precisely what I want

nikomatsakis (Aug 31 2018 at 15:06, on Zulip):

just knowing we ain't got it ;)

nikomatsakis (Aug 31 2018 at 15:06, on Zulip):

but I am starting to get some ideas

Wesley Wiser (Aug 31 2018 at 15:12, on Zulip):

Sounds good!

Wesley Wiser (Sep 04 2018 at 19:19, on Zulip):

Hey @nikomatsakis did you happen to get a chance to look at this? I'm stuck and could use a nudge in the right direction :)

nikomatsakis (Sep 04 2018 at 19:55, on Zulip):

not yet sorry

nikomatsakis (Sep 04 2018 at 19:56, on Zulip):

will do

Wesley Wiser (Sep 04 2018 at 19:56, on Zulip):

No worries :)

Wesley Wiser (Sep 06 2018 at 13:35, on Zulip):

@nikomatsakis I left a comment on the pr here with a thought I had about the failing tests.

nikomatsakis (Sep 06 2018 at 14:39, on Zulip):

replied

Wesley Wiser (Sep 06 2018 at 15:34, on Zulip):

@nikomatsakis Did you reply on GH? I'm not seeing it :grimacing:

nikomatsakis (Sep 06 2018 at 15:44, on Zulip):

I thought I did

nikomatsakis (Sep 06 2018 at 15:44, on Zulip):

tl;dr I thought that code is correct

nikomatsakis (Sep 06 2018 at 15:44, on Zulip):

let me investigate a bit the problem...

nikomatsakis (Sep 06 2018 at 16:40, on Zulip):

@Wesley Wiser ok I found the problem. It was indeed obscure. =)

nikomatsakis (Sep 06 2018 at 16:40, on Zulip):

will push a fix shortly

nikomatsakis (Sep 06 2018 at 16:40, on Zulip):

running --bless right now

Wesley Wiser (Sep 06 2018 at 16:40, on Zulip):

Woohoo!

Wesley Wiser (Sep 06 2018 at 16:40, on Zulip):

I'm reading through your comments now

Wesley Wiser (Sep 06 2018 at 16:41, on Zulip):

Very interested to see how this plays out...

nikomatsakis (Sep 06 2018 at 16:45, on Zulip):

it's one of those bugs that is at once exciting and yet dull as can be :P

nikomatsakis (Sep 06 2018 at 16:49, on Zulip):

pushed

nikomatsakis (Sep 06 2018 at 16:49, on Zulip):

final commit is the actual fix

Wesley Wiser (Sep 06 2018 at 16:50, on Zulip):

/me reads

Wesley Wiser (Sep 06 2018 at 16:54, on Zulip):

I think that makes sense...
"Late bound regions" is unfamiliar terminology to me.
I guess I need to spend more time meditating on the rustc-doc texts.

Wesley Wiser (Sep 06 2018 at 16:57, on Zulip):

Well that certainly fixes those bad error messages!

Wesley Wiser (Sep 06 2018 at 16:58, on Zulip):

And there's a few new error messages that are actually really helpful like this one

nikomatsakis (Sep 06 2018 at 17:14, on Zulip):

late-bound regions are one of the more obscure concepts in rustc

nikomatsakis (Sep 06 2018 at 17:14, on Zulip):

I should write a rustc-guide chapter about them

nikomatsakis (Sep 06 2018 at 17:14, on Zulip):

I hope someday to make them go away

Wesley Wiser (Sep 06 2018 at 17:20, on Zulip):

Thanks for your help on this!

Wesley Wiser (Sep 06 2018 at 17:20, on Zulip):

Out of curiosity, how did you go about debugging this? I tried a bunch of different things but nothing felt very effective to me.

nikomatsakis (Sep 06 2018 at 17:22, on Zulip):

Out of curiosity, how did you go about debugging this? I tried a bunch of different things but nothing felt very effective to me.

well, first I tracked back why give_region_a_name was returning the value it did

nikomatsakis (Sep 06 2018 at 17:22, on Zulip):

then I added various debug! statements (some of which I committed) to possible places that the BrNamed might have been generated

nikomatsakis (Sep 06 2018 at 17:23, on Zulip):

and ran RUST_LOG=rustc_typeck,rustc_mir rustc foo.rs >& killme basically

nikomatsakis (Sep 06 2018 at 17:23, on Zulip):

then I did a grep through that log for the troublesome BrNamed (actually M-x occur in emacs, but same diff)

nikomatsakis (Sep 06 2018 at 17:23, on Zulip):

once I found where it started to appear, I could add more targeted debugging around that fn

nikomatsakis (Sep 06 2018 at 17:23, on Zulip):

this technique -- dumping tons of data then grepping through the logs -- is something I do a lot

nikomatsakis (Sep 06 2018 at 17:24, on Zulip):

works best if you have a small test case though :)

Wesley Wiser (Sep 07 2018 at 13:27, on Zulip):

FYI, I rebased and fixed the tests

nikomatsakis (Sep 07 2018 at 15:43, on Zulip):

ok, r+'d — we should think about how to fix the error messages maybe?

nikomatsakis (Sep 07 2018 at 15:43, on Zulip):

(in separate PR)

Wesley Wiser (Sep 07 2018 at 15:49, on Zulip):

You mean the extra errors?

Yeah, that's a good idea.

lqd (Sep 07 2018 at 20:30, on Zulip):

@Wesley Wiser yay it landed, awesome job :)

Wesley Wiser (Sep 07 2018 at 20:46, on Zulip):

@lqd Thanks!

Last update: Nov 22 2019 at 00:05UTC