Stream: t-compiler/major changes

Topic: Staged queries compiler-team#391


bjorn3 (Dec 22 2020 at 18:42, on Zulip):

Creating the topic manually as it didn't happen automatically.

bjorn3 (Dec 22 2020 at 18:46, on Zulip):

Nothing to AST,

I don't think it will ever be possible to use queries for macro expansion/name resolution due to it being a fixpoint algorithm. For parsing I don't think it is really beneficial either.

AST to HIR,

Same as for parsing I think.

HIR to MIR,
MIR to LLVM bitcode.

Do you have any estimate about how much queries require HIR and can eagerly be invoked without having to wait till codegen?

cjgillot (Dec 22 2020 at 19:17, on Zulip):

TBH, the stages were indicative. I don't know anything about what happens before lowering.

cjgillot (Dec 22 2020 at 19:19, on Zulip):

I don't have stats, and I am not sure of how we should count. Quite a few queries are eagerly invoked in order to produce metadata. Among them: a lot of typing information + promoted & optimized MIR.

cjgillot (Dec 22 2020 at 19:21, on Zulip):

As a first step, I would like to create the split at MIR creation, so that everything that happens on MIR (borrow check & optimisations) happens without the HIR.

cjgillot (Dec 22 2020 at 19:21, on Zulip):

And thanks for creating the topic :)

cjgillot (Dec 22 2020 at 19:28, on Zulip):

cc @wg-incr-comp

Léo Lanteri Thauvin (Dec 22 2020 at 19:32, on Zulip):

cjgillot said:

TBH, the stages were indicative. I don't know anything about what happens before lowering.

FYI, we tried to write a list of the different steps of compilation in the rustc-dev-guide, but it's still got TODOs in unfortunate places

Tyson Nottingham (Dec 22 2020 at 19:40, on Zulip):

I like the idea in principle, but I'm too big of a noob to comment on specifics. :big_smile:

I've had similar ideas while thinking of ways to reduce memory usage. In general, I think the idea of splitting compilation into a small set of well-defined stages, so that we can prune unnecessary data as we go along, could be profitable.

I kind of assumed that traditional compiler design used a more staged approach in this vein, and wondered if the query system intentionally avoided that approach to enable more flexibility. In any case, I assume there's a flexibility tradeoff here. Ideally, there are some very clear stages where we know we will never need any data that we've pruned at previous stage boundaries. Then flexibility wouldn't really be a concern.

Pruning could also be applicable beyond the query system. E.g. maybe it's possible to prune no-longer-useful interned / arena'd data. It's beyond the scope of the proposal, but it would be worth thinking about in advance, in case any mechanisms can be shared.

Joshua Nelson (Dec 22 2020 at 19:41, on Zulip):

the issue with a staged approach is it breaks incremental, it means you need to recalculate all the data even if you don't use it

Joshua Nelson (Dec 22 2020 at 19:41, on Zulip):

has anyone tried doing drop(queries.hir().steal()); and seeing if that 'just works'?

Joshua Nelson (Dec 22 2020 at 19:44, on Zulip):

I guess you need somewhere to call it from

lcnr (Dec 22 2020 at 20:31, on Zulip):

dropping the hir before codegen would require us to force all needed queries before then :thinking: I think changing tcx.hir to return Steal and then dropping it after mir building/analysis would be quite insightful and not too difficult hopefully

cjgillot (Dec 22 2020 at 21:47, on Zulip):

Joshua Nelson said:

the issue with a staged approach is it breaks incremental, it means you need to recalculate all the data even if you don't use it

I am not so sure of that. By calling ensure on the output queries, we can avoid loading the data from the cache if its not used by later stages. Anyway, a lot of information is already forced for metadata output. I will aim at not forcing more queries manually.

cjgillot (Dec 22 2020 at 21:51, on Zulip):

lcnr said:

dropping the hir before codegen would require us to force all needed queries before then :thinking: I think changing tcx.hir to return Steal and then dropping it after mir building/analysis would be quite insightful and not too difficult hopefully

I tried to. I wanted to drop the HIR after all MIR is built. The trouble is that HIR data is appears in a lot of queries. Furthermore, the 'tcx lifetime is the one of the HIR (more precisely, of the arena which is declared in rustc_interface). Dropping this arena without having dangling pointers everywhere would require to drop a lot of query results.

About the point where the call to steal is done, it should be after having forced all the MIR to be built.

In summary, we get to this proposal.

bjorn3 (Dec 22 2020 at 21:55, on Zulip):

I thinl it should at least be possible to drop (or make empty) the hir::Crate without dropping the arena backing certain parts of the hir that can be borrowed.

nikomatsakis (Feb 11 2021 at 15:15, on Zulip):

I'll have to read the backscroll, but I am mildly dubious of this -- part of our goal with the query system was to allow particular things to be compiled without forcing all things to be compiled

nikomatsakis (Feb 11 2021 at 15:15, on Zulip):

Is there some place where ongoing design discussion is happening? (wg-incr-comp, maybe?)

nikomatsakis (Feb 11 2021 at 15:15, on Zulip):

I mgiht be interested in joining some discussions on this topic

cjgillot (Feb 11 2021 at 17:07, on Zulip):

There is no real discussion place about this. However, I am available in this thread.

cjgillot (Feb 11 2021 at 17:15, on Zulip):

My initial consideration is the following: a few queries are forced for all definitions, to emit metadata. As a consequence, I wonder whether embedding this systematic forcing into the query system would allow "checkpoints" where we can clear the caches.

cjgillot (Feb 11 2021 at 17:16, on Zulip):

For longer-term design, I started an incr-comp roadmap thread here, with an unsorted brain dump
https://rust-lang.zulipchat.com/#narrow/stream/241847-t-compiler.2Fwg-incr-comp/topic/Roadmap.20and.20projects.20for.20incr-comp

apiraino (Feb 11 2021 at 18:00, on Zulip):

nikomatsakis said:

Is there some place where ongoing design discussion is happening? (wg-incr-comp, maybe?)

@nikomatsakis I am currently revising the WG list on the compiler team page and just just noticed that @_wg-incr-comp has no page in that directory but has a Zulip presence under #t-compiler/wg-incr-comp and regular checkins at the compiler team meetings.
So, worth adding some content for @_wg-incr-comp there, too?

Wesley Wiser (Feb 11 2021 at 18:21, on Zulip):

This was probably our (wg-incr-comp) fault. We can add a page there.

nikomatsakis (Feb 12 2021 at 20:29, on Zulip):

Yes

nikomatsakis (Feb 12 2021 at 20:29, on Zulip):

the list needs to be revisited

nikomatsakis (Feb 12 2021 at 20:29, on Zulip):

perhaps the mechanism for maintaining it, too =)

nikomatsakis (Feb 12 2021 at 20:29, on Zulip):

I feel like maybe it'd be better to move that list to the team repo

bjorn3 (Feb 13 2021 at 07:16, on Zulip):

Would it be possible to drop a hir::Body once the corresponding mir::Body is generated?

oli (Feb 13 2021 at 12:06, on Zulip):

if we wrap all hir::Bodys in a Steal, this would work quite easily I would think

simulacrum (Apr 01 2021 at 15:00, on Zulip):

Just a passing thought -- I'm wondering if we could avoid keeping all past queries in memory, e.g., with some kind of speculation/prediction/whatever

pnkfelix (Apr 06 2021 at 12:13, on Zulip):

@simulacrum in other words, determine what a good cache eviction strategy might be, and then impose an optioal limit on the size of the query cache?

simulacrum (Apr 06 2021 at 12:14, on Zulip):

yeah, we'd need to be careful around diagnostics/side-effects, but otherwise yes :)

simulacrum (Apr 06 2021 at 12:14, on Zulip):

in theory you might even always want it, if you have sufficient fast cpu that fitting the query cache, in, say l3 is better for you

pnkfelix (Apr 06 2021 at 12:15, on Zulip):

maybe. Might depend on how much RAM you have, right?

pnkfelix (Apr 06 2021 at 12:16, on Zulip):

(i’m assuming this stuff will always tend to exhaust the L1/L2/L3 cache, at least…)

simulacrum (Apr 06 2021 at 12:19, on Zulip):

yeah, maybe -- well, more so the RAM vs CPU speed; it might be faster in some cases to recompute the query, I guess, though it definitely depends on the query

simulacrum (Apr 06 2021 at 12:20, on Zulip):

I know we had some which were like basically a hash table lookup, caching that in a hash table is 100% pointless and wasteful

pnkfelix (Apr 06 2021 at 12:52, on Zulip):

simulacrum said:

I know we had some which were like basically a hash table lookup, caching that in a hash table is 100% pointless and wasteful

Hmm. My first reaction was :+1:. My second reaction was ”wait, that’s a different problem from cache eviction though, right? I.e., identifying cases that should never be cached at all?” My third reaction is now: “I guess there may be a spectrum here: Things that shoud never be cached, to things that may be useful to evict, and presumably there are things that, once computed, should never be evicted…"

simulacrum (Apr 06 2021 at 13:00, on Zulip):

yeah, there's likely a spectrum. for some things a cache may make sense, but perhaps we do a bunch of queries on one thing and then never again. I don't know if we have hit rate metrics in a more granular (i.e. not overall hit rate, but per-element) way

pnkfelix (Apr 06 2021 at 13:47, on Zulip):

a per-element hit rate sounds like a good thing to capture. The evolution of the hit rate over time might also be useful.

cjgillot (Apr 06 2021 at 17:34, on Zulip):

I guess there are actually two problems this proposal can address: (1) how to release memory for query results we do not need any more, and (2) how to convert between different representations of the crate.

On point 1, there can be many other answers. For instance, having a more systematic use of Steal along with caching just after the query computation (instead of at the end of compilations); having recomputable queries like simulacrum suggests... For now, the query system does not allow to recompute its results. Allowing that should be doable, but certainly very subtle to do efficiently (most notably: how to ensure the results are exactly the same without going through the full query code path?).

Point 2 is only interesting in the perspective of end-to-end queries. The most prominent issue here is iterating all LocalDefIds when queries can create new LocalDefIds. Having a staged query system could allow progress on incremental front-end (macro expansion and incremental parsing, if anybody actually wants make those incremental), while allowing for time to design and join everything cleanly.

Last update: May 07 2021 at 07:15UTC