Query Parallelization Tracking Issue

[nikomatsakis]

This issue is a sub-issue of #48547: it tracks the in-progress effort to parallelize rustc across queries. This work is being spearheaded by @Zoxc.

Goals

Allow rustc to execute queries in parallel with one another. Enable the use of rayon or other tools for intra-query parallelization as well. See this internals thread for more information.

Overview of the plan

• Make all types in the compiler send and sync by landing @Zoxc's existing work
  • The existing work largely replaces RefCell usage with Mutex
  • In many cases, the interior mutability itself can be refactored away. The plan is do this as a second step.
• Set up CI so this gets some testing (CI: Make sure that we can bootstrap with cfg(parallel_queries). #48607)
• Implement a thread pool that is integrated with Cargo's jobserver (Add support for using a jobserver with Rayon #56946)
• Build list of all sources of shared state in the compiler by auditing PR history Audit sources of shared state across rustc #63643
• Audit each source of shared state, leading to either refactoring to reduce use of shared state, or persistent documentation covering invariants, atomicity, and lock orderings

Pending refactorings

• ParseSess.included_mod_stack might be problematic
• Ensure that the err_count() API is not used to discover if errors happen in parallel code (cc [parallel-queries] Refactor error message handling to better integrate with parallel queries #49737)
• Find a way to order error messages deterministically so that if a query depends on another query, its error messages appear after the other query (cc [parallel-queries] Refactor error message handling to better integrate with parallel queries #49737)
• Make mk_attr_id use a scoped thread local or make it part of ParseSess
• See if GlobalCtxt.rcache, OnDiskCache.file_index_to_file and OnDiskCache.synthetic_expansion_infos are faster as thread-locals
• Review usages of Session.lint_store and Session.buffered_lints
• Fix EvaluationCache overwrites its entries #50507, as it may cause issues with parallel rustc
• Find a way to deal with marking attributes as used
• Ensure Rayon executes all remaining work when we panic inside the thread pool

Completed refactorings

• Remove HIR inlining (Remove HIR inlining (now that we don't need it for constant evaluation anymore) #49690)
• Make GlobalCtxt implement Sync
• Use scoped thread locals instead of globals, WIP: Less globals #46193
• Misc fixes required to use a rayon thread pool, WIP: Parallelize passes using rayon #46564
• Ensure metadata loaded by LlvmMetadataLoader does not get freed on the wrong thread
• CurrentDepGraph.task_stack has to be made a QueryJob field. (implemented in Make incremental compilation thread-safe #49732)
• Check that optimization fuel is not used with parallel queries
• Review libproc_macro for issues, Find out which types should be Send, Sync. Deal with Deref impls for Symbol. (Decouple proc_macro from the rest of the compiler. #49219)
• Run CI with cfg(parallel_queries)
• Refactor away CStore::next_crate_num
• Make FileMap.lines, FileMap.multibyte_chars, and FileMap.non_narrow_chars immutable (implemented in Make FileMap::{lines, multibyte_chars, non_narrow_chars} non-mutable.  #50997)
• When executing queries, instead of keeping around a lock to the query map, create a job object immediately instead (Move query code outside macros and store query jobs separately from query results #50102)
• Ensure all diagnostics are emitted before returning from DepGraph.try_mark_green
• Refactor DepGraphData.previous_work_products so it becomes immutable ([parallel-queries] DepGraph::previous_work_products could be made immutable to avoid shared mutable state #50501) (implemented in Make DepGraph::previous_work_products immutable #50524)
• Remove DepGraphData.work_products by threaded the value through save_trans_partition() -> copy_module_artifacts_into_incr_comp_cache() -> OngoingCrateTranslation::join() ([parallel-queries] Refactor away DepGraph::work_products to avoid shared mutable state #50500) (implemented in Encountered errors [...] resolving bounds after type-checking [rustc 1.28.0-nightly (952f344cd 2018-05-18)] #50885)
• The TransitiveRelation doesn't really need to use a RefCell. In the future, it won't even be shared, but regardless the caching scheme could be reworked to avoid RefCell (implemented in get rid of RefCell in TransitiveRelation #99702).
• Refactor GlobalCtxt::layout_depth so it does not need global mutable state ([parallel-queries] Refactor layout-depth tracking so it does not need mutable state in the GlobalCtxt #49735) (implemented in add depth_limit in QueryVTable to avoid entering a new tcx in layout_of #100748)

[nikomatsakis]

cc @michaelwoerister

[michaelwoerister]

I'm trying to identify the blocking issues for a minimal but correct version of parallel queries. Ideally we would solve all of them over the next few weeks :)

So far I've found:

• MIRI const evaluation is not really thread-safe yet and needs at least a proper review for possible race conditions.
• SelectionCache and EvaluationCache are not thread-safe yet. A PR is open (Make SelectionCache and EvaluationCache thread-safe #49834) but needs review by @nikomatsakis.
• Rayon needs some enhancements (Add a Rayon thread pool #50235 (comment)) that have not been reviewed yet (@nikomatsakis or @cuviper).
• Incremental compilation's OnDiskCache could use another review for race conditions.
• GlobalCtxt is not Sync yet, which is blocked on a few of the above.
• We actually need to use the parallel abstractions that @Zoxc introduced.

There are a few things that also need to be solved medium term, but they are not blocking yet:

• Error message handling must be deterministic enough for tests to work (or tests need to handle indeterminism)
• Various things could be made thread-local or immutable instead of globally shared.
• Various corner cases (such as optimization fuel) may not work correctly yet.

@Zoxc, @nikomatsakis, @oli-obk, @eddyb: I'm sure this list does not cover all blockers. Let me know what I forgot :)

[Zoxc]

@michaelwoerister We also have to make queries work on a Rayon thread-pool

[michaelwoerister]

We also have to make queries work on a Rayon thread-pool

What exactly does this involve?

[Zoxc]

@michaelwoerister We have to make waiting on already executing queries block and also detect and recover from query cycles

[michaelwoerister]

Ah, right. The blocking should be easy enough. I have not thought in detail about cycle detection and recovery though.