Remove all occurrences of "DepNode re-opening"

[michaelwoerister]

In order for the new red/green dependency tracking to work and for our compiler developers' sanity, we need incremental compilation's dependency graph to not contain any cycles. Since DepGraph::write() has been removed in #42192, we are close to guaranteeing this "by construction". The only other way of introducing cycles into the dependency graph is by "re-opening" a node:

// Allocate DepNode::A
dep_graph.with_task(DepNode::A, tcx, (), || {
   // ...
});

// Allocate DepNode::B and add edge B -> A
dep_graph.with_task(DepNode::B, tcx, (), || {
    dep_graph.read(DepNode::A);
});

// Re-open DepNode::A and add edge A -> B
dep_graph.with_task(DepNode::A, tcx, (), || {
    dep_graph.read(DepNode::B);
});

Currently, re-opening is needed for supporting DepNode merging: Many tasks share the same DepNode. For example, DepNode::ItemSignature is used for many things that conceptually are part of an item's signature. Another example is trait selection where we don't want to track at full accuracy since that would cause too much overhead.

There are three basic ways of avoiding node re-opening:

1. Make the DepNode fully accurate so that two distinct tasks use two distinct DepNodes instead of using the same one. This increases tracking overhead.
2. Merge tasks so that there's just one task that computes all results corresponding to a given DepNode. This decreases laziness since not all parts of a result might be needed. It might also lead to result with many Option fields in them because some parts of it are only valid for a subset of query keys (e.g. impl_trait_ref is only valid for trait impls but if it was part of a larger item_signature query, we would have to provide it for any kind of item that has a signature).
3. Use the yet-to-be-implemented "anonymous" DepNodes which allows node merging in a safe way that keeps the graph free of cycles. Anonymous nodes can only be used for things the result of which we do not cache and using them is slightly more expensive than using a regular node.

DepNode kinds that will need un-merging are the following (in addition to others probably):

// All of these queries use DepNode::ItemSignature
type_of: ItemSignature(DefId) -> Ty<'tcx>,
generics_of: ItemSignature(DefId) -> &'tcx ty::Generics,
predicates_of: ItemSignature(DefId) -> ty::GenericPredicates<'tcx>,
super_predicates_of: ItemSignature(DefId) -> ty::GenericPredicates<'tcx>,
trait_def: ItemSignature(DefId) -> &'tcx ty::TraitDef,
adt_def: ItemSignature(DefId) -> &'tcx ty::AdtDef,
impl_trait_ref: ItemSignature(DefId) -> Option<ty::TraitRef<'tcx>>,
impl_polarity: ItemSignature(DefId) -> hir::ImplPolarity,
closure_kind: ItemSignature(DefId) -> ty::ClosureKind,
closure_type: ItemSignature(DefId) -> ty::PolyFnSig<'tcx>,
coerce_unsized_info: ItemSignature(DefId) -> ty::adjustment::CoerceUnsizedInfo,

// All of these queries use DepNode::Mir(DefId)
mir_const_qualif: Mir(DefId) -> u8,
mir_const: Mir(DefId) -> &'tcx Steal<mir::Mir<'tcx>>,
mir_validated: Mir(DefId) -> &'tcx Steal<mir::Mir<'tcx>>,
optimized_mir: Mir(DefId) -> &'tcx mir::Mir<'tcx>,

// These queries use DepNode::TypeckTables(DefId)
typeck_tables_of: TypeckTables(DefId) -> &'tcx ty::TypeckTables<'tcx>,
has_typeck_tables: TypeckTables(DefId) -> bool,

// These both use DepNode::Coherence
crate_inherent_impls: crate_inherent_impls_dep_node(CrateNum) -> CrateInherentImpls,
crate_inherent_impls_overlap_check: crate_inherent_impls_dep_node(CrateNum) -> (),

// const_eval uses one DepNode::ConstEval for all consts with the same DefId
const_eval: const_eval_dep_node((DefId, &'tcx Substs<'tcx>)) -> const_val::EvalResult<'tcx>,

// There's only one DepNode::SymbolName although there are can be 
// many different symbol names because of monomorphization
def_symbol_name: SymbolName(DefId) -> ty::SymbolName,
symbol_name: symbol_name_dep_node(ty::Instance<'tcx>) -> ty::SymbolName,

// DepNode::TraitImpls(DefId)
trait_impls_of: TraitImpls(DefId) -> ty::trait_def::TraitImpls,
relevant_trait_impls_for: relevant_trait_impls_for((DefId, SimplifiedType)) -> ty::trait_def::TraitImpls,

There's also TransTraitCaches which still uses DepTrackingMap directly.

It remains to be clarified which strategy to use exactly in which case.

cc @nikomatsakis and @eddyb

[michaelwoerister]

It might also turn out that we do want to support re-opening nodes and just ensure cycle freedom via a runtime check. For things like symbol names that we don't want to cache on-disk, it seems a bit excessive to have one node per monomorphic instance (strategy 1), it's a bit complicated to have one node for all instances (strategy 2), and the anonymous node strategy might end up with the same number of nodes as strategy 1.

We could also have simplified cycle-check for cases like this: Every kind of DepNode is assigned to a compiler phase (or something like that) and we just disallow adding edges from phase n to anything greater than n-1. E.g. the SymbolName dep-node gets phase trans while everything it needs to access is in phase type-check or smaller.

[nikomatsakis]

I think I had planned to handle this by moving to anonymous nodes. I think we should be able to add that as a concept into the existing dep-graph without any particular problem, right?

[nikomatsakis]

It is (potentially) true that we might still want to be able to "re-open" nodes, but I'm not sure. I'd rather pursue using anonymous nodes and see how far that takes us.

[michaelwoerister]

I think I had planned to handle this by moving to anonymous nodes. I think we should be able to add that as a concept into the existing dep-graph without any particular problem, right?

I think so. Not sure about the implementation details.

It is (potentially) true that we might still want to be able to "re-open" nodes, but I'm not sure. I'd rather pursue using anonymous nodes and see how far that takes us.

Sure. However, as in the example above, there might be cases where anonymous nodes would not improve performance compared to maximal granularity. It's something we should keep an eye on.