Tracking issue for "Red/Green" Dependency Tracking

[michaelwoerister]

"Red/Green dependency tracking" is what we call the improved tracking algorithm for incremental compilation. The main difference to the algorithm used at the moment is improved accuracy because it can recover from "false positives", that is, it can stop cache invalidation short if a potentially changed value turns out to not have changed after all. A (work-in-progress) description of the system can be found at https://github.com/nikomatsakis/rustc-on-demand-incremental-design-doc/blob/master/0000-rustc-on-demand-and-incremental.md. Implementing this new tracking and caching system will happen in a few phases:

Phase 1 - Red/Green without additional caching

In the first phase the core infrastructure for red/green tracking will be implemented. We do not cache any additional intermediate results but at the end of this phase, we will already have reached peak tracking accuracy.

• Implement direct metadata hashing as a proof of concept for general result hashing (revise metadata hashing to hash the contents of the metadata, not its input dependencies #38114)
• Remove DepTrackingMap::write() (incr.comp.: Remove DepGraph::write() and its callers #42192)
• Refactor DepNode to use a stable hash that does not need "re-tracing" (incr.comp.: Use ICH-based DepNodes in order to make them PODs #42294)
• Clarify how checking for query cycles fits into the red/green algorithm (incr.comp.: Clarify compatibility of red/green evaluation and recovering from cycle errors #42633)
• Remove all occurrences of DepNode re-opening (Remove all occurrences of "DepNode re-opening" #42298)
• Fingerprint all query results (incr.comp.: Compute fingerprint for all query results. #44364)
• Switch to new, append-only dependency graph implementation (incr.comp.: Add new DepGraph implementation. #44772)
• Make Metadata fingerprints available in DepGraph (incr.comp.: Add new DepGraph implementation. #44772)
• Implementing minimal CachingPolicy support for queries and use for CGUs
• Implement red/green marking in ty::queries::{}::try_get()
• Transition the testing framework to work properly again (Tracking Issue for incr. comp. red/green testing #44716)

Phase 2 - Caching ty::TypeckTables

In the second phase, support for caching ty::TypeckTables will be added, which allows the compiler to skip type checking.

• Add infrastructure for caching and loading query results (incr.comp.: Implement query result cache and use it to cache type checking tables. #46004)
• Move all uses of NodeId referenced by ty::TypeckTables over to HirId ([incremental] don't use NodeId in the HIR, but something local to an item #40303)
• Refactor error messages, warnings, and lints to be cacheable (incr.comp.: Lints and other error messages are not included in the ICH #41184)
• Store and load ty::TypeckTables (incr.comp.: Implement query result cache and use it to cache type checking tables. #46004)

Phase 3 - Caching MIR

The third phase will support for caching MIR, which should be straight forward at that point. It remains to be verified though if it actually is a performance gain to do so.

• Use new infrastructure to load and store optimized MIR (incr.comp.: Enable query result caching for many more queries #46556)
• Verify that this even makes sense

cc @nikomatsakis, @eddyb, and @rust-lang/compiler in general

[michaelwoerister]

🎉 🎉 🎉 🎉 🎉

[matklad]

@michaelwoerister could you add a link to https://rust-lang-nursery.github.io/rustc-guide/query.html to the original description? This is what comes up in the search for rust red-green, so it's nice to have links to state-of-the-art docs.