-
-
Save michaelwoerister/e278b4ad3eb88d61e19b7ab066c44b25 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
enum DepNodeKind { | |
Hir, | |
Signature, | |
... | |
} | |
// A globally unique ID for a node in a DepGraph. | |
struct DepNode { | |
kind: DepNodeKind, | |
fingerprint: Fingerprint, | |
} | |
impl CurrentDepGraph { | |
fn set_result_fingerprint(&mut self, DepNodeIndex, Fingerprint); | |
fn contains(&mut self, DepNode) -> bool; | |
fn read(&mut self, DepNodeIndex); | |
fn push_as_current_task(&mut self, DepNode); | |
fn pop_current_task(&mut self, DepNode) -> DepNodeIndex; | |
fn push_anonymous_task(&mut self); | |
fn pop_current_task(&mut self) -> DepNodeIndex; | |
} | |
impl PrevDepGraph { | |
fn get_result_fingerprint(DepNode) -> Fingerprint; | |
fn dependencies(DepNode) -> impl Iterator<Item=DepNode>; | |
} | |
// A unique ID for a DepNode in the *current* DepGraph. Allows for fast lookup. | |
struct DepNodeIndex(u32); | |
// An index into tcx.dep_node_cache | |
struct DepNodeCacheIndex(u32); | |
enum DepNodeColor { | |
Red, | |
Green(DepNodeIndex), | |
Grey, | |
} | |
struct TyCtxt { | |
queries, | |
dep_graph: CurrentDepGraph, | |
prev_dep_graph: PrevDepGraph, | |
// Can be used by queries to cache DepNodes | |
dep_node_cache: IndexedVec<DepNodeCacheIndex, DepNodeIndex>, | |
// This is a mapping of DepNode to Color, where DepNode might be something | |
// in the old or the new graph. Hence we have to use the globally valid | |
// DepNode as key instead of a DepNodeIndex, which only exists for already | |
// allocated things in the new graph. | |
dep_graph_colors: HashMap<DepNode, DepNodeColor>, | |
} | |
trait Query { | |
type Key; | |
type Result; | |
// Reads either from tcx.dep_node_cache or constructs the DepNode from the | |
// Key if that is cheaper. | |
fn get_cached_dep_node(tcx, k: &Self::Key, dep_node_cache_index: DepNodeCacheIndex) -> DepNodeIndex; | |
// This can be a no-op, if it's simple to reconstruct a DepNode from the Query::Key. | |
fn cache_dep_node(tcx, dep_node_index: DepNodeIndex) -> DepNodeCacheIndex; | |
fn load_from_disk(&self, tcx, dep_node: DepNode) -> Self::Result; | |
fn store_to_disk(&self, tcx, dep_node: DepNode, Self::Result); | |
// Look something up in the in-memory cache. | |
fn get_cached_result(&self, key: &Self::Key) -> Option<(Self::Result, DepNodeCacheIndex)>; | |
// Caches the given result in-memory. | |
fn cache_result(&mut self, key: Self::Key, dep_node_cache_index: DepNodeCacheIndex, result: Self::Result); | |
// The "provider". | |
fn compute_result(tcx, key: Self::Key) -> Self::Result; | |
fn is_anon_dep_node_query() -> bool; | |
} | |
enum CachingPolicy { | |
InMemoryOnly, | |
FingerprintOnDisk, | |
ResultOnDisk, | |
} | |
struct ForceResult<T> { | |
result: T, | |
color: DepNodeColor, | |
dep_node_index: DepNodeIndex, | |
} | |
fn query<Q: Query>( | |
query: &mut Q, | |
tcx, | |
query_key: Q::Key) | |
-> Q::Result | |
where Q: Query | |
{ | |
// In non-incremental, things are easy | |
if !tcx.incremental { | |
// FX-HASHTABLE LOOKUP | |
return tcx.queries | |
.foo_cache_non_incr | |
.entry(query_key) | |
.or_insert_with(|| Q::compute_result(tcx, query_key)); | |
} | |
// We have something cached, great! | |
// FX-HASHTABLE LOOKUP | |
if let Some(result, dep_node_cache_index) = query.get_cached_result(&query_key) { | |
// FX-HASHTABLE LOOKUP or FREE | |
let dep_node_index = Q::get_cached_dep_node(tcx, &query_key, dep_node_cache_index); | |
// CACHE-FRIENDLY FX-HASHTABLE INSERT + VEC PUSH | |
tcx.new_dep_graph.read(dep_node_index); | |
return result.clone(); | |
} | |
if Q::is_anon_dep_node_query() { | |
tcx.dep_graph.push_anon_task(); | |
let result = Q::compute_result(tcx, &query_key); | |
let dep_node_index = tcx.dep_graph.pop_anon_task(); | |
let dep_node_cache_index = Q::cache_dep_node(dep_node_index); | |
query.cache_result(query_key, dep_node_cache_index, result.clone()); | |
tcx.new_dep_graph.read(dep_node_index); | |
result | |
} else { | |
// Does not cache the node yet! | |
// POSSIBLY EXPENSIVE OPERATION | |
let dep_node = Q::create_dep_node(tcx, &query_key); | |
// Don't have it in memory, but we might have it on disk and already | |
// verified that it is still up-to-date | |
// FX-HASHTABLE LOOKUP | |
if let Green(dep_node_index) = tcx.dep_graph_colors.get(dep_node) { | |
// CACHE-FRIENDLY FX-HASHTABLE INSERT + VEC PUSH | |
tcx.new_dep_graph.read(dep_node_index); | |
return load_from_disk_and_cache_in_memory(query, tcx, query_key, dep_node_index); | |
} | |
// We don't know yet if there is a valid result cached on disk. | |
// We do this by trying to mark the corresponding dependency node as green, | |
// which will only succeed if all its immediate dependencies are green and | |
// might involve actually evaluating and caching transitive dependencies. | |
if let Green(dep_node_index) = try_mark_green(tcx, dep_node) { | |
// CACHE-FRIENDLY FX-HASHTABLE INSERT + VEC PUSH | |
tcx.new_dep_graph.read(dep_node_index); | |
load_from_disk_and_cache_in_memory(query, tcx, query_key, dep_node_index) | |
} else { | |
// One of the dependencies turned up red, we have to re-compute. | |
let ForceResult { | |
result, | |
color: _, | |
dep_node_index | |
} = force(query, tcx, query_key, dep_node); | |
// CACHE-FRIENDLY FX-HASHTABLE INSERT + VEC PUSH | |
tcx.new_dep_graph.read(dep_node_index); | |
result | |
} | |
} | |
} | |
fn load_from_disk_and_cache_in_memory<Q: Query>( | |
query: &mut Q, | |
tcx, | |
query_key: Q::Key, | |
dep_node_index: DepNodeIndex, | |
) | |
-> Q::Result | |
where Q: Query | |
{ | |
let dep_node = tcx.dep_graph.index_to_dep_node(dep_node_index); | |
let result = match query.caching_policy() { | |
InMemoryOnly | | |
FingerprintOnly => { | |
assert!(tcx.dep_graph_colors.get(dep_node) == Green) | |
// If it is already green, the correct edges should already exist | |
tcx.new_dep_graph.ignoring(|| Q::compute_result(tcx, query_key)) | |
} | |
OnDisk => { | |
Q::load_from_disk(dep_node) | |
} | |
}; | |
let dep_node_cache_index = Q::cache_dep_node(tcx, dep_node_index); | |
// FX-HASHTABLE INSERT + maybe cache DepNode (VEC PUSH) | |
query.cache_result(query_key, dep_node_cache_index, result.clone()); | |
result | |
} | |
fn try_mark_green(tcx, dep_node: DepNode) -> DepNodeColor { | |
// We are trying to mark this node as green, so it must still be grey | |
assert!(tcx.dep_graph_colors.get(dep_node) == Grey); | |
// | |
assert!(!tcx.dep_graph.contains(dep_node)); | |
let mut dependencies: Vec<DepNodeIndex> = Vec::new(); | |
// FX-HASHTABLE LOOKUPS (dep-list of dep_node) | |
// N array lookups (dep_node_index to dep_node) | |
for dep_dep_node in tcx.prev_dep_graph.dependencies(dep_node) { | |
// FX-HASHTABLE LOOKUP | |
match tcx.dep_graph_colors.get(dep_dep_node) { | |
Green(dep_dep_node_index) => { | |
// This node checks out, take a look at the next | |
dependencies.push(dep_dep_node_index); | |
} | |
Red => { | |
// This node has changed compared to the last compilation | |
// session, so we did not succeed in marking this node green | |
return Red | |
} | |
Grey => { | |
// We don't know the state of this dependency | |
if let Green(dep_dep_node_index) = try_mark_green(tcx, dep_dep_node) { | |
dependencies.push(dep_dep_node_index); | |
} else { | |
// We could not mark it as green without re-computing it, | |
// so we "force" it. | |
// NOTE: This involves some kind of dynamic dispatch, since | |
// the dependency/query could be of any type. | |
match force_from_dep_node(tcx, dep_dep_node) { | |
Ok((color, dep_dep_node_index)) => { | |
match color { | |
Green(_) => { | |
dependencies.push(dep_dep_node_index); | |
} | |
Red => { | |
assert!(tcx.dep_graph_colors.get(dep_dep_node) == Red); | |
// We were able to re-compute the query result, but it | |
// has changed from the last run. | |
return Red | |
} | |
} | |
} | |
Err(_) => { | |
// We could not recompute the value. This might have one | |
// of two reasons: | |
// | |
// 1. The thing we are trying to recompute does not | |
// exist anymore in the current session | |
// 2. We cannot reconstruct a query-key from the DepNode | |
assert!(tcx.dep_graph_colors.get(dep_dep_node) == Red); | |
return Red | |
} | |
} | |
} | |
} | |
} | |
} | |
// Mirror dep-edges from old graph to new one | |
// Note: We could provide a specialized CurrentDepGraph method, that skips | |
// the hash-table check, because we already know that edges are unique. | |
tcx.dep_graph.push_as_current_task(dep_node); | |
for dep_dep_node_index in dependencies { | |
// CACHE-FRIENDLY FX-HASHTABLE INSERT + VEC PUSH | |
tcx.dep_graph.read(dep_dep_node_index); | |
} | |
// FX-HASHTABLE insert (for dep_node) | |
let dep_node_index = tcx.dep_graph.pop_current_task(dep_node); | |
// FX-HASHTABLE INSERT | |
tcx.dep_graph_colors.set(dep_node, Green(dep_node_index)); | |
Green(dep_node_index) | |
} | |
fn force<Q>(query: &mut Q, tcx, query_key: Q::Key, dep_node: DepNode) -> ForceResult<Q::Result> { | |
assert!(!tcx.dep_graph.contains(dep_node)); | |
assert!(!tcx.dep_graph_colors.contains(dep_node)); | |
// DO CYCLE CHECK HERE | |
tcx.dep_graph.push_as_current_task(dep_node); | |
let result = Q::compute_result(tcx, query_key); | |
let dep_node_index = tcx.dep_graph.pop_current_task(); | |
let dep_node_cache_index = Q::cache_dep_node(dep_node_index); | |
// Cache the result for future queries. | |
query.cache_result(query_key, dep_node_cache_index, result.clone()); | |
if Q::caching_policy() == InMemoryOnly { | |
tcx.dep_graph_colors.set(dep_node, Red); | |
return ForceResult { | |
result, | |
color: red, | |
dep_node_index | |
} | |
} | |
// Now we know the new value. Let's see if it has actually changed. | |
let old_result_fingerprint = tcx.prev_dep_graph.get_result_fingerprint(dep_node); | |
let new_result_fingerprint = result.fingerprint(tcx); | |
let color = if old_result_fingerprint == new_result_fingerprint { | |
// No actual change, which means: | |
// - We can leave the on-disk cache untouched. | |
// - We can mark this node as green. | |
let color = Green(dep_node_index); | |
tcx.dep_graph_colors.set(dep_node, color); | |
color | |
} else { | |
// The value has changed, mark as red an store the new value in | |
// on-disk cache | |
tcx.dep_graph_colors.set(dep_node, Red); | |
match Q::caching_policy() { | |
FingerprintOnDisk => {} | |
OnDisk => { | |
assert!(!Q::is_input()); | |
// This will hopefully happen in a background thread: | |
query.store_to_disk(tcx, dep_node, result.clone()); | |
} | |
} | |
Red | |
}; | |
tcx.dep_graph.set_result_fingerprint(dep_node_index, new_result_fingerprint); | |
ForceResult { | |
result, | |
color, | |
dep_node_index | |
} | |
} | |
// Do dynamic dispatch | |
fn force_from_dep_node(tcx, dep_node: DepNode) -> Result<(DepNodeColor, DepNodeIndex), ()> { | |
// Try to do a reverse-lookup from DepNode fingerprint to DefId. | |
let opt_def_id = dep_node.extract_def_id(tcx); | |
let def_id = if let Some(def_id) = opt_def_id { | |
def_id | |
} else { | |
// Extracting a DefId from the DepNode can have failed for two reasons: | |
// | |
// 1. The fingerprint in the DepNode does not correspond to a single DefPath fingerprint. | |
// 2. The thing the DefId would have identified does not exist anymore | |
// in the current compilation session. | |
// | |
// Both cases prevent us from re-computing the query. | |
tcx.dep_graph_colors.set(dep_dep_node, Red); | |
return Err(()) | |
} | |
match dep_node.kind { | |
Hir => { | |
let result = tcx.queries.hir.force(tcx, def_id, dep_node); | |
return Ok((result.color, result.dep_node_index)); | |
} | |
ItemSig => { | |
let result = tcx.queries.item_sig.force(tcx, def_id, dep_node); | |
return Ok((result.color, result.dep_node_index)); | |
} | |
... | |
_ => bug!("extract_def_id() above should already have returned None.") | |
} | |
} | |
// - Cycle errors | |
// - allocating graph nodes and then failing? | |
// - special "probe_cycle"? |
Oops; I forgot to reply to the earlier question. You asked about your algorithm, with this description:
Yes, this matches my understanding. To me this procedure also sounds totally analogous to "cleaning" in Adapton. Though, seems different in two subtle ways:
- Adapton cleans and re-evaluates in one inter-leaved (possibly-nested) algorithm. Specifically, see this call to loc_produce for the specific step where cleaning switches to nested re-evaluation.
- With names, nominal allocations in Adapton introduce dirtying to be inter-leaved with cleaning and re-evaluation. In some cases, these names play the role of "nominal firewalls", as mentioned above in our earlier comments.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Yes, we do store this view on each edge: Each edge consists of a source node, a target node, an effect (either force or alloc), a dirty bit and a value/content. See
Succ
for details.For get/force edges (that's one kind, with many interchangeable words), the value/content corresponds to the last seen value (the "view", as you call it above). For put/alloc edges, the value corresponds to the allocated value, or thunk closure (a static fn and argument values for its formal parameters).
Cool! Yes, @nikomatsakis and I discussed that connection too: In Adapton we call some nodes "structural" (when they are identified by their value/closure, and their dependencies, usually by a hash of those things), and other nodes are "nominal" --- when they have a name that is distinct from their content. Only nominal allocations induce these "firewalls", in Adapton. It sounds like a very direct connection of related ideas. :)