diff options
| -rw-r--r-- | src/librustc/dep_graph/README.md | 384 | ||||
| -rw-r--r-- | src/librustc/dep_graph/dep_tracking_map.rs | 81 | ||||
| -rw-r--r-- | src/librustc/dep_graph/edges.rs | 162 | ||||
| -rw-r--r-- | src/librustc/dep_graph/mod.rs | 196 | ||||
| -rw-r--r-- | src/librustc/dep_graph/query.rs | 68 | ||||
| -rw-r--r-- | src/librustc/dep_graph/raii.rs | 47 | ||||
| -rw-r--r-- | src/librustc/dep_graph/thread.rs | 137 | ||||
| -rw-r--r-- | src/librustc/lib.rs | 2 | ||||
| -rw-r--r-- | src/librustc/middle/ty/fast_reject.rs | 2 | ||||
| -rw-r--r-- | src/librustc_data_structures/graph/mod.rs | 14 | ||||
| -rw-r--r-- | src/librustc_data_structures/lib.rs | 1 | ||||
| -rw-r--r-- | src/librustc_data_structures/veccell/mod.rs | 37 |
12 files changed, 1127 insertions, 4 deletions
diff --git a/src/librustc/dep_graph/README.md b/src/librustc/dep_graph/README.md new file mode 100644 index 00000000000..c607894c5e3 --- /dev/null +++ b/src/librustc/dep_graph/README.md @@ -0,0 +1,384 @@ +# Dependency graph for incremental compilation + +This module contains the infrastructure for managing the incremental +compilation dependency graph. This README aims to explain how it ought +to be used. In this document, we'll first explain the overall +strategy, and then share some tips for handling specific scenarios. + +The high-level idea is that we want to instrument the compiler to +track which parts of the AST and other IR are read/written by what. +This way, when we come back later, we can look at this graph and +determine what work needs to be redone. + +### The dependency graph + +The nodes of the graph are defined by the enum `DepNode`. They represent +one of three things: + +1. HIR nodes (like `Hir(DefId)`) represent the HIR input itself. +2. Data nodes (like `ItemSignature(DefId)`) represent some computed + information about a particular item. +3. Procedure notes (like `CoherenceCheckImpl(DefId)`) represent some + procedure that is executing. Usually this procedure is + performing some kind of check for errors. You can think of them as + computed values where the value being computed is `()` (and the + value may fail to be computed, if an error results). + +An edge `N1 -> N2` is added between two nodes if either: + +- the value of `N1` is used to compute `N2`; +- `N1` is read by the procedure `N2`; +- the procedure `N1` writes the value `N2`. + +The latter two conditions are equivalent to the first one if you think +of procedures as values. + +### Basic tracking + +There is a very general strategy to ensure that you have a correct, if +sometimes overconservative, dependency graph. The two main things you have +to do are (a) identify shared state and (b) identify the current tasks. + +### Identifying shared state + +Identify "shared state" that will be written by one pass and read by +another. In particular, we need to identify shared state that will be +read "across items" -- that is, anything where changes in one item +could invalidate work done for other items. So, for example: + +1. The signature for a function is "shared state". +2. The computed type of some expression in the body of a function is + not shared state, because if it changes it does not itself + invalidate other functions (though it may be that it causes new + monomorphizations to occur, but that's handled independently). + +Put another way: if the HIR for an item changes, we are going to +recompile that item for sure. But we need the dep tracking map to tell +us what *else* we have to recompile. Shared state is anything that is +used to communicate results from one item to another. + +### Identifying the current task + +The dep graph always tracks a current task: this is basically the +`DepNode` that the compiler is computing right now. Typically it would +be a procedure node, but it can also be a data node (as noted above, +the two are kind of equivalent). + +You set the current task by calling `dep_graph.in_task(node)`. For example: + +```rust +let _task = tcx.dep_graph.in_task(DepNode::Privacy); +``` + +Now all the code until `_task` goes out of scope will be considered +part of the "privacy task". + +The tasks are maintained in a stack, so it is perfectly fine to nest +one task within another. Because pushing a task is considered to be +computing a value, when you nest a task `N2` inside of a task `N1`, we +automatically add an edge `N2 -> N1` (since `N1` presumably needed the +result of `N2` to complete): + +```rust +let _n1 = tcx.dep_graph.in_task(DepNode::N1); +let _n2 = tcx.dep_graph.in_task(DepNode::N2); +// this will result in an edge N1 -> n2 +``` + +### Ignore tasks + +Although it is rarely needed, you can also push a special "ignore" +task: + +```rust +let _ignore = tc.dep_graph.in_ignore(); +``` + +This will cause all read/write edges to be ignored until it goes out +of scope or until something else is pushed. For example, we could +suppress the edge between nested tasks like so: + +```rust +let _n1 = tcx.dep_graph.in_task(DepNode::N1); +let _ignore = tcx.dep_graph.in_ignore(); +let _n2 = tcx.dep_graph.in_task(DepNode::N2); +// now no edge is added +``` + +### Tracking reads and writes + +We need to identify what shared state is read/written by the current +task as it executes. The most fundamental way of doing that is to invoke +the `read` and `write` methods on `DepGraph`: + +```rust +// Adds an edge from DepNode::Hir(some_def_id) to the current task +tcx.dep_graph.read(DepNode::Hir(some_def_id)) + +// Adds an edge from the current task to DepNode::ItemSignature(some_def_id) +tcx.dep_graph.write(DepNode::ItemSignature(some_def_id)) +``` + +However, you should rarely need to invoke those methods directly. +Instead, the idea is to *encapsulate* shared state into some API that +will invoke `read` and `write` automatically. The most common way to +do this is to use a `DepTrackingMap`, described in the next section, +but any sort of abstraction brarier will do. In general, the strategy +is that getting access to information implicitly adds an appropriate +`read`. So, for example, when you use the +`dep_graph::visit_all_items_in_krate` helper method, it will visit +each item `X`, start a task `Foo(X)` for that item, and automatically +add an edge `Hir(X) -> Foo(X)`. This edge is added because the code is +being given access to the HIR node for `X`, and hence it is expected +to read from it. Similarly, reading from the `tcache` map for item `X` +(which is a `DepTrackingMap`, described below) automatically invokes +`dep_graph.read(ItemSignature(X))`. + +To make this strategy work, a certain amount of indirection is +required. For example, modules in the HIR do not have direct pointers +to the items that they contain. Rather, they contain node-ids -- one +can then ask the HIR map for the item with a given node-id. This gives +us an opportunity to add an appropriate read edge. + +#### Explicit calls to read and write when starting a new subtask + +One time when you *may* need to call `read` and `write` directly is +when you push a new task onto the stack, either by calling `in_task` +as shown above or indirectly, such as with the `memoize` pattern +described below. In that case, any data that the task has access to +from the surrounding environment must be explicitly "read". For +example, in `librustc_typeck`, the collection code visits all items +and, among other things, starts a subtask producing its signature +(what follows is simplified pseudocode, of course): + +```rust +fn visit_item(item: &hir::Item) { + // Here, current subtask is "Collect(X)", and an edge Hir(X) -> Collect(X) + // has automatically been added by `visit_all_items_in_krate`. + let sig = signature_of_item(item); +} + +fn signature_of_item(item: &hir::Item) { + let def_id = tcx.map.local_def_id(item.id); + let task = tcx.dep_graph.in_task(DepNode::ItemSignature(def_id)); + tcx.dep_graph.read(DepNode::Hir(def_id)); // <-- the interesting line + ... +} +``` + +Here you can see that, in `signature_of_item`, we started a subtask +corresponding to producing the `ItemSignature`. This subtask will read from +`item` -- but it gained access to `item` implicitly. This means that if it just +reads from `item`, there would be missing edges in the graph: + + Hir(X) --+ // added by the explicit call to `read` + | | + | +---> ItemSignature(X) -> Collect(X) + | ^ + | | + +---------------------------------+ // added by `visit_all_items_in_krate` + +In particular, the edge from `Hir(X)` to `ItemSignature(X)` is only +present because we called `read` ourselves when entering the `ItemSignature(X)` +task. + +So, the rule of thumb: when entering a new task yourself, register +reads on any shared state that you inherit. (This actually comes up +fairly infrequently though: the main place you need caution is around +memoization.) + +#### Dependency tracking map + +`DepTrackingMap` is a particularly convenient way to correctly store +shared state. A `DepTrackingMap` is a special hashmap that will add +edges automatically when `get` and `insert` are called. The idea is +that, when you get/insert a value for the key `K`, we will add an edge +from/to the node `DepNode::Variant(K)` (for some variant specific to +the map). + +Each `DepTrackingMap` is parameterized by a special type `M` that +implements `DepTrackingMapId`; this trait defines the key and value +types of the map, and also defines a fn for converting from the key to +a `DepNode` label. You don't usually have to muck about with this by +hand, there is a macro for creating it. You can see the complete set +of `DepTrackingMap` definitions in `librustc/middle/ty/maps.rs`. + +As an example, let's look at the `adt_defs` map. The `adt_defs` map +maps from the def-id of a struct/enum to its `AdtDef`. It is defined +using this macro: + +```rust +dep_map_ty! { AdtDefs: ItemSignature(DefId) -> ty::AdtDefMaster<'tcx> } +// ~~~~~~~ ~~~~~~~~~~~~~ ~~~~~ ~~~~~~~~~~~~~~~~~~~~~~ +// | | Key type Value type +// | DepNode variant +// Name of map id type +``` + +this indicates that a map id type `AdtDefs` will be created. The key +of the map will be a `DefId` and value will be +`ty::AdtDefMaster<'tcx>`. The `DepNode` will be created by +`DepNode::ItemSignature(K)` for a given key. + +Once that is done, you can just use the `DepTrackingMap` like any +other map. + +#### Memoization + +One particularly interesting case is memoization. If you have some +shared state that you compute in a memoized fashion, the correct thing +to do is to define a `RefCell<DepTrackingMap>` for it and use the +`memoize` helper: + +```rust +map.memoize(key, || /* compute value */) +``` + +This will create a graph that looks like + + ... -> MapVariant(key) -> CurrentTask + +where `MapVariant` is the `DepNode` variant that the map is associated with, +and `...` are whatever edges the `/* compute value */` closure creates. + +In particular, using the memoize helper is much better than writing +the obvious code yourself: + +``` +if let Some(result) = map.get(key) { + return result; +} +let value = /* compute value */; +map.insert(key, value); +``` + +If you write that code manually, the dependency graph you get will +include artificial edges that are not necessary. For example, imagine that +two tasks, A and B, both invoke the manual memoization code, but A happens +to go first. The resulting graph will be: + + ... -> A -> MapVariant(key) -> B + ~~~~~~~~~~~~~~~~~~~~~~~~~~~ // caused by A writing to MapVariant(key) + ~~~~~~~~~~~~~~~~~~~~ // caused by B reading from MapVariant(key) + +This graph is not *wrong*, but it encodes a path from A to B that +should not exist. In contrast, using the memoized helper, you get: + + ... -> MapVariant(key) -> A + | + +----------> B + +which is much cleaner. + +**Be aware though that the closure is executed with `MapVariant(key)` +pushed onto the stack as the current task!** That means that you must +add explicit `read` calls for any shared state that it accesses +implicitly from its environment. See the section on "explicit calls to +read and write when starting a new subtask" above for more details. + +### How to decide where to introduce a new task + +Certainly, you need at least one task on the stack: any attempt to +`read` or `write` shared state will panic if there is no current +task. But where does it make sense to introduce subtasks? The basic +rule is that a subtask makes sense for any discrete unit of work you +may want to skip in the future. Adding a subtask separates out the +reads/writes from *that particular subtask* versus the larger +context. An example: you might have a 'meta' task for all of borrow +checking, and then subtasks for borrow checking individual fns. (Seen +in this light, memoized computations are just a special case where we +may want to avoid redoing the work even within the context of one +compilation.) + +The other case where you might want a subtask is to help with refining +the reads/writes for some later bit of work that needs to be memoized. +For example, we create a subtask for type-checking the body of each +fn. However, in the initial version of incr. comp. at least, we do +not expect to actually *SKIP* type-checking -- we only expect to skip +trans. However, it's still useful to create subtasks for type-checking +individual items, because, otherwise, if a fn sig changes, we won't +know which callers are affected -- in fact, because the graph would be +so coarse, we'd just have to retrans everything, since we can't +distinguish which fns used which fn sigs. + +### Testing the dependency graph + +There are various ways to write tests against the dependency graph. +The simplest mechanism are the +`#[rustc_if_this_changed` and `#[rustc_then_this_would_need]` +annotations. These are used in compile-fail tests to test whether the +expected set of paths exist in the dependency graph. As an example, +see `src/test/compile-fail/dep-graph-caller-callee.rs`. + +The idea is that you can annotate a test like: + +```rust +#[rustc_if_this_changed] +fn foo() { } + +#[rustc_then_this_would_need(TypeckItemBody)] //~ ERROR OK +fn bar() { foo(); } + +#[rustc_then_this_would_need(TypeckItemBody)] //~ ERROR no path +fn baz() { } +``` + +This will check whether there is a path in the dependency graph from +`Hir(foo)` to `TypeckItemBody(bar)`. An error is reported for each +`#[rustc_then_this_would_need]` annotation that indicates whether a +path exists. `//~ ERROR` annotations can then be used to test if a +path is found (as demonstrated above). + +### Debugging the dependency graph + +The compiler is also capable of dumping the dependency graph for your +debugging pleasure. To do so, pass the `-Z dump-dep-graph` flag. The +graph will be dumped to `dep_graph.{txt,dot}` in the current +directory. You can override the filename with the `RUST_DEP_GRAPH` +environment variable. + +Frequently, though, the full dep graph is quite overwhelming and not +particularly helpful. Therefore, the compiler also allows you to filter +the graph. You can filter in three ways: + +1. All edges originating in a particular set of nodes (usually a single node). +2. All edges reaching a particular set of nodes. +3. All edges that lie between given start and end nodes. + +To filter, use the `RUST_DEP_GRAPH_FILTER` environment variable, which should +look like one of the following: + +``` +source_filter // nodes originating from source_filter +-> target_filter // nodes that can reach target_filter +source_filter -> target_filter // nodes in between source_filter and target_filter +``` + +`source_filter` and `target_filter` are a comma-separated list of strings. +A node is considered to match a filter if all of those strings appear in its +label. So, for example: + +``` +RUST_DEP_GRAPH_FILTER='-> TypeckItemBody' +``` + +would select the predecessors of all `TypeckItemBody` nodes. Usually though you +want the `TypeckItemBody` nod for some particular fn, so you might write: + +``` +RUST_DEP_GRAPH_FILTER='-> TypeckItemBody,bar' +``` + +This will select only the `TypeckItemBody` nodes for fns with `bar` in their name. + +Perhaps you are finding that when you change `foo` you need to re-type-check `bar`, +but you don't think you should have to. In that case, you might do: + +``` +RUST_DEP_GRAPH_FILTER='Hir,foo -> TypeckItemBody,bar' +``` + +This will dump out all the nodes that lead from `Hir(foo)` to +`TypeckItemBody(bar)`, from which you can (hopefully) see the source +of the erroneous edge. + diff --git a/src/librustc/dep_graph/dep_tracking_map.rs b/src/librustc/dep_graph/dep_tracking_map.rs new file mode 100644 index 00000000000..4f1063eae50 --- /dev/null +++ b/src/librustc/dep_graph/dep_tracking_map.rs @@ -0,0 +1,81 @@ +// Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use rustc_data_structures::fnv::FnvHashMap; +use std::cell::RefCell; +use std::ops::Index; +use std::hash::Hash; +use std::marker::PhantomData; + +use super::{DepNode, DepGraph}; + +/// A DepTrackingMap offers a subset of the `Map` API and ensures that +/// we make calls to `read` and `write` as appropriate. We key the +/// maps with a unique type for brevity. +pub struct DepTrackingMap<M: DepTrackingMapId> { + phantom: PhantomData<M>, + graph: DepGraph, + map: FnvHashMap<M::Key, M::Value>, +} + +pub trait DepTrackingMapId { + type Key: Eq + Hash + Clone; + type Value: Clone; + fn to_dep_node(key: &Self::Key) -> DepNode; +} + +impl<M: DepTrackingMapId> DepTrackingMap<M> { + pub fn new(graph: DepGraph) -> DepTrackingMap<M> { + DepTrackingMap { + phantom: PhantomData, + graph: graph, + map: FnvHashMap() + } + } + + /// Registers a (synthetic) read from the key `k`. Usually this + /// is invoked automatically by `get`. + fn read(&self, k: &M::Key) { + let dep_node = M::to_dep_node(k); + self.graph.read(dep_node); + } + + /// Registers a (synthetic) write to the key `k`. Usually this is + /// invoked automatically by `insert`. + fn write(&self, k: &M::Key) { + let dep_node = M::to_dep_node(k); + self.graph.write(dep_node); + } + + pub fn get(&self, k: &M::Key) -> Option<&M::Value> { + self.read(k); + self.map.get(k) + } + + pub fn insert(&mut self, k: M::Key, v: M::Value) -> Option<M::Value> { + self.write(&k); + self.map.insert(k, v) + } + + pub fn contains_key(&self, k: &M::Key) -> bool { + self.read(k); + self.map.contains_key(k) + } +} + +impl<'k, M: DepTrackingMapId> Index<&'k M::Key> for DepTrackingMap<M> { + type Output = M::Value; + + #[inline] + fn index(&self, k: &'k M::Key) -> &M::Value { + self.get(k).unwrap() + } +} + diff --git a/src/librustc/dep_graph/edges.rs b/src/librustc/dep_graph/edges.rs new file mode 100644 index 00000000000..07b18944aa1 --- /dev/null +++ b/src/librustc/dep_graph/edges.rs @@ -0,0 +1,162 @@ +// Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use rustc_data_structures::fnv::{FnvHashMap, FnvHashSet}; +use super::{DepGraphQuery, DepNode}; + +pub struct DepGraphEdges { + ids: Vec<DepNode>, + indices: FnvHashMap<DepNode, IdIndex>, + edges: FnvHashSet<(IdIndex, IdIndex)>, + open_nodes: Vec<OpenNode>, +} + +#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)] +struct IdIndex { + index: u32 +} + +impl IdIndex { + fn new(v: usize) -> IdIndex { + assert!((v & 0xFFFF_FFFF) == v); + IdIndex { index: v as u32 } + } + + fn index(self) -> usize { + self.index as usize + } +} + +#[derive(Clone, Debug, PartialEq)] +enum OpenNode { + Node(IdIndex), + Ignore, +} + +impl DepGraphEdges { + pub fn new() -> DepGraphEdges { + DepGraphEdges { + ids: vec![], + indices: FnvHashMap(), + edges: FnvHashSet(), + open_nodes: Vec::new() + } + } + + fn id(&self, index: IdIndex) -> &DepNode { + &self.ids[index.index()] + } + + /// Creates a node for `id` in the graph. + fn make_node(&mut self, id: DepNode) -> IdIndex { + if let Some(&i) = self.indices.get(&id) { + return i; + } + + let index = IdIndex::new(self.ids.len()); + self.ids.push(id.clone()); + self.indices.insert(id, index); + index + } + + /// Top of the stack of open nodes. + fn current_node(&self) -> Option<OpenNode> { + self.open_nodes.last().cloned() + } + + pub fn push_ignore(&mut self) { + self.open_nodes.push(OpenNode::Ignore); + } + + pub fn pop_ignore(&mut self) { + let popped_node = self.open_nodes.pop().unwrap(); + assert_eq!(popped_node, OpenNode::Ignore); + } + + pub fn push_task(&mut self, key: DepNode) { + let top_node = self.current_node(); + + let new_node = self.make_node(key.clone()); + self.open_nodes.push(OpenNode::Node(new_node)); + + // if we are in the midst of doing task T, then this new task + // N is a subtask of T, so add an edge N -> T. + if let Some(top_node) = top_node { + self.add_edge_from_open_node(top_node, |t| (new_node, t)); + } + } + + pub fn pop_task(&mut self, key: DepNode) { + let popped_node = self.open_nodes.pop().unwrap(); + assert_eq!(OpenNode::Node(self.indices[&key]), popped_node); + } + + /// Indicates that the current task `C` reads `v` by adding an + /// edge from `v` to `C`. If there is no current task, panics. If + /// you want to suppress this edge, use `ignore`. + pub fn read(&mut self, v: DepNode) { + let source = self.make_node(v); + self.add_edge_from_current_node(|current| (source, current)) + } + + /// Indicates that the current task `C` writes `v` by adding an + /// edge from `C` to `v`. If there is no current task, panics. If + /// you want to suppress this edge, use `ignore`. + pub fn write(&mut self, v: DepNode) { + let target = self.make_node(v); + self.add_edge_from_current_node(|current| (current, target)) + } + + /// Invoke `add_edge_from_open_node` with the top of the stack, or + /// panic if stack is empty. + fn add_edge_from_current_node<OP>(&mut self, + op: OP) + where OP: FnOnce(IdIndex) -> (IdIndex, IdIndex) + { + match self.current_node() { + Some(open_node) => self.add_edge_from_open_node(open_node, op), + None => panic!("no current node, cannot add edge into dependency graph") + } + } + + /// Adds an edge to or from the `open_node`, assuming `open_node` + /// is not `Ignore`. The direction of the edge is determined by + /// the closure `op` --- we pass as argument the open node `n`, + /// and the closure returns a (source, target) tuple, which should + /// include `n` in one spot or another. + fn add_edge_from_open_node<OP>(&mut self, + open_node: OpenNode, + op: OP) + where OP: FnOnce(IdIndex) -> (IdIndex, IdIndex) + { + let (source, target) = match open_node { + OpenNode::Node(n) => op(n), + OpenNode::Ignore => { return; } + }; + + // ignore trivial self edges, which are not very interesting + if source == target { + return; + } + + if self.edges.insert((source, target)) { + debug!("adding edge from {:?} to {:?}", + self.id(source), + self.id(target)); + } + } + + pub fn query(&self) -> DepGraphQuery { + let edges: Vec<_> = self.edges.iter() + .map(|&(i, j)| (self.id(i).clone(), self.id(j).clone())) + .collect(); + DepGraphQuery::new(&self.ids, &edges) + } +} diff --git a/src/librustc/dep_graph/mod.rs b/src/librustc/dep_graph/mod.rs new file mode 100644 index 00000000000..c3d195811f2 --- /dev/null +++ b/src/librustc/dep_graph/mod.rs @@ -0,0 +1,196 @@ +// Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use self::thread::{DepGraphThreadData, DepMessage}; +use middle::def_id::DefId; +use middle::ty; +use middle::ty::fast_reject::SimplifiedType; +use rustc_front::hir; +use rustc_front::intravisit::Visitor; +use std::rc::Rc; + +mod dep_tracking_map; +mod edges; +mod query; +mod raii; +mod thread; + +#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)] +pub enum DepNode { + // Represents the `Krate` as a whole (the `hir::Krate` value) (as + // distinct from the krate module). This is basically a hash of + // the entire krate, so if you read from `Krate` (e.g., by calling + // `tcx.map.krate()`), we will have to assume that any change + // means that you need to be recompiled. This is because the + // `Krate` value gives you access to all other items. To avoid + // this fate, do not call `tcx.map.krate()`; instead, prefer + // wrappers like `tcx.visit_all_items_in_krate()`. If there is no + // suitable wrapper, you can use `tcx.dep_graph.ignore()` to gain + // access to the krate, but you must remember to add suitable + // edges yourself for the individual items that you read. + Krate, + + // Represents the HIR node with the given node-id + Hir(DefId), + + // Represents different phases in the compiler. + CollectItem(DefId), + Coherence, + CoherenceCheckImpl(DefId), + CoherenceOverlapCheck(DefId), + CoherenceOverlapCheckSpecial(DefId), + CoherenceOrphanCheck(DefId), + Variance, + WfCheck(DefId), + TypeckItemType(DefId), + TypeckItemBody(DefId), + Dropck, + DropckImpl(DefId), + CheckConst(DefId), + Privacy, + IntrinsicCheck(DefId), + MatchCheck(DefId), + MirMapConstruction(DefId), + BorrowCheck(DefId), + RvalueCheck(DefId), + Reachability, + DeadCheck, + StabilityCheck, + LateLintCheck, + IntrinsicUseCheck, + TransCrate, + TransCrateItem(DefId), + TransInlinedItem(DefId), + TransWriteMetadata, + + // Nodes representing bits of computed IR in the tcx. Each shared + // table in the tcx (or elsewhere) maps to one of these + // nodes. Often we map multiple tables to the same node if there + // is no point in distinguishing them (e.g., both the type and + // predicates for an item wind up in `ItemSignature`). Other + // times, such as `ImplItems` vs `TraitItemDefIds`, tables which + // might be mergable are kept distinct because the sets of def-ids + // to which they apply are disjoint, and hence we might as well + // have distinct labels for easier debugging. + ImplOrTraitItems(DefId), + ItemSignature(DefId), + FieldTy(DefId), + TraitItemDefIds(DefId), + InherentImpls(DefId), + ImplItems(DefId), + + // The set of impls for a given trait. Ultimately, it would be + // nice to get more fine-grained here (e.g., to include a + // simplified type), but we can't do that until we restructure the + // HIR to distinguish the *header* of an impl from its body. This + // is because changes to the header may change the self-type of + // the impl and hence would require us to be more conservative + // than changes in the impl body. + TraitImpls(DefId), + + // Nodes representing caches. To properly handle a true cache, we + // don't use a DepTrackingMap, but rather we push a task node. + // Otherwise the write into the map would be incorrectly + // attributed to the first task that happened to fill the cache, + // which would yield an overly conservative dep-graph. + TraitItems(DefId), + ReprHints(DefId), + TraitSelect(DefId, Option<SimplifiedType>), +} + +#[derive(Clone)] +pub struct DepGraph { + data: Rc<DepGraphThreadData> +} + +impl DepGraph { + pub fn new(enabled: bool) -> DepGraph { + DepGraph { + data: Rc::new(DepGraphThreadData::new(enabled)) + } + } + + pub fn query(&self) -> DepGraphQuery { + self.data.query() + } + + pub fn in_ignore<'graph>(&'graph self) -> raii::IgnoreTask<'graph> { + raii::IgnoreTask::new(&self.data) + } + + pub fn in_task<'graph>(&'graph self, key: DepNode) -> raii::DepTask<'graph> { + raii::DepTask::new(&self.data, key) + } + + pub fn with_ignore<OP,R>(&self, op: OP) -> R + where OP: FnOnce() -> R + { + let _task = self.in_ignore(); + op() + } + + pub fn with_task<OP,R>(&self, key: DepNode, op: OP) -> R + where OP: FnOnce() -> R + { + let _task = self.in_task(key); + op() + } + + pub fn read(&self, v: DepNode) { + self.data.enqueue(DepMessage::Read(v)); + } + + pub fn write(&self, v: DepNode) { + self.data.enqueue(DepMessage::Write(v)); + } +} + +pub use self::dep_tracking_map::{DepTrackingMap, DepTrackingMapId}; + +pub use self::query::DepGraphQuery; + +/// Visit all the items in the krate in some order. When visiting a +/// particular item, first create a dep-node by calling `dep_node_fn` +/// and push that onto the dep-graph stack of tasks, and also create a +/// read edge from the corresponding AST node. This is used in +/// compiler passes to automatically record the item that they are +/// working on. +pub fn visit_all_items_in_krate<'tcx,V,F>(tcx: &ty::ctxt<'tcx>, + mut dep_node_fn: F, + visitor: &mut V) + where F: FnMut(DefId) -> DepNode, V: Visitor<'tcx> +{ + struct TrackingVisitor<'visit, 'tcx: 'visit, F: 'visit, V: 'visit> { + tcx: &'visit ty::ctxt<'tcx>, + dep_node_fn: &'visit mut F, + visitor: &'visit mut V + } + + impl<'visit, 'tcx, F, V> Visitor<'tcx> for TrackingVisitor<'visit, 'tcx, F, V> + where F: FnMut(DefId) -> DepNode, V: Visitor<'tcx> + { + fn visit_item(&mut self, i: &'tcx hir::Item) { + let item_def_id = self.tcx.map.local_def_id(i.id); + let task_id = (self.dep_node_fn)(item_def_id); + debug!("About to start task {:?}", task_id); + let _task = self.tcx.dep_graph.in_task(task_id); + self.tcx.dep_graph.read(DepNode::Hir(item_def_id)); + self.visitor.visit_item(i) + } + } + + let krate = tcx.dep_graph.with_ignore(|| tcx.map.krate()); + let mut tracking_visitor = TrackingVisitor { + tcx: tcx, + dep_node_fn: &mut dep_node_fn, + visitor: visitor + }; + krate.visit_all_items(&mut tracking_visitor) +} diff --git a/src/librustc/dep_graph/query.rs b/src/librustc/dep_graph/query.rs new file mode 100644 index 00000000000..74a054acb4f --- /dev/null +++ b/src/librustc/dep_graph/query.rs @@ -0,0 +1,68 @@ +// Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use rustc_data_structures::fnv::FnvHashMap; +use rustc_data_structures::graph::{Graph, NodeIndex}; + +use super::DepNode; + +pub struct DepGraphQuery { + pub graph: Graph<DepNode, ()>, + pub indices: FnvHashMap<DepNode, NodeIndex>, +} + +impl DepGraphQuery { + pub fn new(nodes: &[DepNode], edges: &[(DepNode, DepNode)]) -> DepGraphQuery { + let mut graph = Graph::new(); + let mut indices = FnvHashMap(); + for node in nodes { + indices.insert(node.clone(), graph.next_node_index()); + graph.add_node(node.clone()); + } + + for &(ref source, ref target) in edges { + let source = indices[source]; + let target = indices[target]; + graph.add_edge(source, target, ()); + } + + DepGraphQuery { + graph: graph, + indices: indices + } + } + + pub fn nodes(&self) -> Vec<DepNode> { + self.graph.all_nodes() + .iter() + .map(|n| n.data.clone()) + .collect() + } + + pub fn edges(&self) -> Vec<(DepNode,DepNode)> { + self.graph.all_edges() + .iter() + .map(|edge| (edge.source(), edge.target())) + .map(|(s, t)| (self.graph.node_data(s).clone(), self.graph.node_data(t).clone())) + .collect() + } + + /// All nodes reachable from `node`. In other words, things that + /// will have to be recomputed if `node` changes. + pub fn dependents(&self, node: DepNode) -> Vec<DepNode> { + if let Some(&index) = self.indices.get(&node) { + self.graph.depth_traverse(index) + .map(|dependent_node| self.graph.node_data(dependent_node).clone()) + .collect() + } else { + vec![] + } + } +} diff --git a/src/librustc/dep_graph/raii.rs b/src/librustc/dep_graph/raii.rs new file mode 100644 index 00000000000..dd7ff92f9c3 --- /dev/null +++ b/src/librustc/dep_graph/raii.rs @@ -0,0 +1,47 @@ +// Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use super::DepNode; +use super::thread::{DepGraphThreadData, DepMessage}; + +pub struct DepTask<'graph> { + data: &'graph DepGraphThreadData, + key: DepNode, +} + +impl<'graph> DepTask<'graph> { + pub fn new(data: &'graph DepGraphThreadData, key: DepNode) -> DepTask<'graph> { + data.enqueue(DepMessage::PushTask(key)); + DepTask { data: data, key: key } + } +} + +impl<'graph> Drop for DepTask<'graph> { + fn drop(&mut self) { + self.data.enqueue(DepMessage::PopTask(self.key)); + } +} + +pub struct IgnoreTask<'graph> { + data: &'graph DepGraphThreadData +} + +impl<'graph> IgnoreTask<'graph> { + pub fn new(data: &'graph DepGraphThreadData) -> IgnoreTask<'graph> { + data.enqueue(DepMessage::PushIgnore); + IgnoreTask { data: data } + } +} + +impl<'graph> Drop for IgnoreTask<'graph> { + fn drop(&mut self) { + self.data.enqueue(DepMessage::PopIgnore); + } +} diff --git a/src/librustc/dep_graph/thread.rs b/src/librustc/dep_graph/thread.rs new file mode 100644 index 00000000000..f2a5b1c9ef9 --- /dev/null +++ b/src/librustc/dep_graph/thread.rs @@ -0,0 +1,137 @@ +// Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! Manages the communication between the compiler's main thread and +//! the thread that constructs the dependency graph. The basic idea is +//! to use double buffering to lower the cost of producing a message. +//! In the compiler thread, we accumulate messages in a vector until +//! the vector is full, or until we want to query the graph, and then +//! we send that vector over to the depgraph thread. At the same time, +//! we receive an empty vector from the depgraph thread that we can use +//! to accumulate more messages. This way we only ever have two vectors +//! allocated (and both have a fairly large capacity). + +use rustc_data_structures::veccell::VecCell; +use std::sync::mpsc::{self, Sender, Receiver}; +use std::thread; + +use super::DepGraphQuery; +use super::DepNode; +use super::edges::DepGraphEdges; + +pub enum DepMessage { + Read(DepNode), + Write(DepNode), + PushTask(DepNode), + PopTask(DepNode), + PushIgnore, + PopIgnore, + Query, +} + +pub struct DepGraphThreadData { + enabled: bool, + + // current buffer, where we accumulate messages + messages: VecCell<DepMessage>, + + // whence to receive new buffer when full + swap_in: Receiver<Vec<DepMessage>>, + + // where to send buffer when full + swap_out: Sender<Vec<DepMessage>>, + + // where to receiver query results + query_in: Receiver<DepGraphQuery>, +} + +const INITIAL_CAPACITY: usize = 2048; + +impl DepGraphThreadData { + pub fn new(enabled: bool) -> DepGraphThreadData { + let (tx1, rx1) = mpsc::channel(); + let (tx2, rx2) = mpsc::channel(); + let (txq, rxq) = mpsc::channel(); + if enabled { + thread::spawn(move || main(rx1, tx2, txq)); + } + DepGraphThreadData { + enabled: enabled, + messages: VecCell::with_capacity(INITIAL_CAPACITY), + swap_in: rx2, + swap_out: tx1, + query_in: rxq, + } + } + + /// Sends the current batch of messages to the thread. Installs a + /// new vector of messages. + fn swap(&self) { + assert!(self.enabled, "should never swap if not enabled"); + + // should be a buffer waiting for us (though of course we may + // have to wait for depgraph thread to finish processing the + // old messages) + let new_messages = self.swap_in.recv().unwrap(); + assert!(new_messages.is_empty()); + + // swap in the empty buffer and extract the full one + let old_messages = self.messages.swap(new_messages); + + // send full buffer to depgraph thread to be processed + self.swap_out.send(old_messages).unwrap(); + } + + pub fn query(&self) -> DepGraphQuery { + assert!(self.enabled, "cannot query if dep graph construction not enabled"); + self.enqueue(DepMessage::Query); + self.swap(); + self.query_in.recv().unwrap() + } + + /// Enqueue a message to be sent when things are next swapped. (If + /// the buffer is full, this may swap.) + #[inline] + pub fn enqueue(&self, message: DepMessage) { + if self.enabled { + let len = self.messages.push(message); + if len == INITIAL_CAPACITY { + self.swap(); + } + } + } +} + +/// Definition of the depgraph thread. +pub fn main(swap_in: Receiver<Vec<DepMessage>>, + swap_out: Sender<Vec<DepMessage>>, + query_out: Sender<DepGraphQuery>) { + let mut edges = DepGraphEdges::new(); + + // the compiler thread always expects a fresh buffer to be + // waiting, so queue one up + swap_out.send(Vec::with_capacity(INITIAL_CAPACITY)).unwrap(); + + // process the buffers from compiler thread as we receive them + for mut messages in swap_in { + for msg in messages.drain(..) { + match msg { + DepMessage::Read(node) => edges.read(node), + DepMessage::Write(node) => edges.write(node), + DepMessage::PushTask(node) => edges.push_task(node), + DepMessage::PopTask(node) => edges.pop_task(node), + DepMessage::PushIgnore => edges.push_ignore(), + DepMessage::PopIgnore => edges.pop_ignore(), + DepMessage::Query => query_out.send(edges.query()).unwrap(), + } + } + swap_out.send(messages).unwrap(); + } +} diff --git a/src/librustc/lib.rs b/src/librustc/lib.rs index 00d6237b855..f84d5fbaf81 100644 --- a/src/librustc/lib.rs +++ b/src/librustc/lib.rs @@ -87,6 +87,8 @@ pub mod back { pub use rustc_back::svh; } +pub mod dep_graph; + pub mod front { pub mod check_attr; pub mod map; diff --git a/src/librustc/middle/ty/fast_reject.rs b/src/librustc/middle/ty/fast_reject.rs index 77608f40128..a06e8a72c44 100644 --- a/src/librustc/middle/ty/fast_reject.rs +++ b/src/librustc/middle/ty/fast_reject.rs @@ -15,7 +15,7 @@ use syntax::ast; use self::SimplifiedType::*; /// See `simplify_type -#[derive(Clone, Copy, PartialEq, Eq, Hash)] +#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)] pub enum SimplifiedType { BoolSimplifiedType, CharSimplifiedType, diff --git a/src/librustc_data_structures/graph/mod.rs b/src/librustc_data_structures/graph/mod.rs index 4a3810c822b..1ea09490aed 100644 --- a/src/librustc_data_structures/graph/mod.rs +++ b/src/librustc_data_structures/graph/mod.rs @@ -77,16 +77,16 @@ impl<E: Debug> Debug for Edge<E> { } } -#[derive(Copy, Clone, PartialEq, Debug)] +#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)] pub struct NodeIndex(pub usize); -#[derive(Copy, Clone, PartialEq, Debug)] +#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)] pub struct EdgeIndex(pub usize); pub const INVALID_EDGE_INDEX: EdgeIndex = EdgeIndex(usize::MAX); // Use a private field here to guarantee no more instances are created: -#[derive(Copy, Clone, Debug)] +#[derive(Copy, Clone, Debug, PartialEq)] pub struct Direction { repr: usize } pub const OUTGOING: Direction = Direction { repr: 0 }; @@ -410,4 +410,12 @@ impl<E> Edge<E> { pub fn target(&self) -> NodeIndex { self.target } + + pub fn source_or_target(&self, direction: Direction) -> NodeIndex { + if direction == OUTGOING { + self.target + } else { + self.source + } + } } diff --git a/src/librustc_data_structures/lib.rs b/src/librustc_data_structures/lib.rs index 3bba7d651ad..ef64d7dde09 100644 --- a/src/librustc_data_structures/lib.rs +++ b/src/librustc_data_structures/lib.rs @@ -40,6 +40,7 @@ pub mod transitive_relation; pub mod unify; pub mod fnv; pub mod tuple_slice; +pub mod veccell; // See comments in src/librustc/lib.rs #[doc(hidden)] diff --git a/src/librustc_data_structures/veccell/mod.rs b/src/librustc_data_structures/veccell/mod.rs new file mode 100644 index 00000000000..1842d0a4958 --- /dev/null +++ b/src/librustc_data_structures/veccell/mod.rs @@ -0,0 +1,37 @@ +use std::cell::UnsafeCell; +use std::mem; + +pub struct VecCell<T> { + data: UnsafeCell<Vec<T>> +} + +impl<T> VecCell<T> { + pub fn with_capacity(capacity: usize) -> VecCell<T>{ + VecCell { data: UnsafeCell::new(Vec::with_capacity(capacity)) } + } + + #[inline] + pub fn push(&self, data: T) -> usize { + // The logic here, and in `swap` below, is that the `push` + // method on the vector will not recursively access this + // `VecCell`. Therefore, we can temporarily obtain mutable + // access, secure in the knowledge that even if aliases exist + // -- indeed, even if aliases are reachable from within the + // vector -- they will not be used for the duration of this + // particular fn call. (Note that we also are relying on the + // fact that `VecCell` is not `Sync`.) + unsafe { + let v = self.data.get(); + (*v).push(data); + (*v).len() + } + } + + pub fn swap(&self, mut data: Vec<T>) -> Vec<T> { + unsafe { + let v = self.data.get(); + mem::swap(&mut *v, &mut data); + } + data + } +} |