]>
Commit | Line | Data |
---|---|---|
ea8adc8c | 1 | //! The data that we will serialize and deserialize. |
cdc7bbd5 XL |
2 | //! |
3 | //! The dep-graph is serialized as a sequence of NodeInfo, with the dependencies | |
9c376795 | 4 | //! specified inline. The total number of nodes and edges are stored as the last |
cdc7bbd5 XL |
5 | //! 16 bytes of the file, so we can find them easily at decoding time. |
6 | //! | |
7 | //! The serialisation is performed on-demand when each node is emitted. Using this | |
8 | //! scheme, we do not need to keep the current graph in memory. | |
9 | //! | |
5e7ed085 | 10 | //! The deserialization is performed manually, in order to convert from the stored |
9c376795 | 11 | //! sequence of NodeInfos to the different arrays in SerializedDepGraph. Since the |
cdc7bbd5 XL |
12 | //! node and edge count are stored at the end of the file, all the arrays can be |
13 | //! pre-allocated with the right length. | |
ea8adc8c | 14 | |
cdc7bbd5 XL |
15 | use super::query::DepGraphQuery; |
16 | use super::{DepKind, DepNode, DepNodeIndex}; | |
ba9703b0 | 17 | use rustc_data_structures::fingerprint::Fingerprint; |
cdc7bbd5 XL |
18 | use rustc_data_structures::fx::FxHashMap; |
19 | use rustc_data_structures::profiling::SelfProfilerRef; | |
20 | use rustc_data_structures::sync::Lock; | |
21 | use rustc_index::vec::{Idx, IndexVec}; | |
923072b8 | 22 | use rustc_serialize::opaque::{FileEncodeResult, FileEncoder, IntEncodedWithFixedSize, MemDecoder}; |
cdc7bbd5 XL |
23 | use rustc_serialize::{Decodable, Decoder, Encodable}; |
24 | use smallvec::SmallVec; | |
ea8adc8c | 25 | |
fc512014 XL |
26 | // The maximum value of `SerializedDepNodeIndex` leaves the upper two bits |
27 | // unused so that we can store multiple index types in `CompressedHybridIndex`, | |
28 | // and use those bits to encode which index type it contains. | |
e74abb32 | 29 | rustc_index::newtype_index! { |
9c376795 FG |
30 | #[max = 0x7FFF_FFFF] |
31 | pub struct SerializedDepNodeIndex {} | |
b7449926 | 32 | } |
ea8adc8c XL |
33 | |
34 | /// Data for use when recompiling the **current crate**. | |
5869c6ff | 35 | #[derive(Debug)] |
ba9703b0 | 36 | pub struct SerializedDepGraph<K: DepKind> { |
ea8adc8c | 37 | /// The set of all DepNodes in the graph |
17df50a5 | 38 | nodes: IndexVec<SerializedDepNodeIndex, DepNode<K>>, |
0531ce1d XL |
39 | /// The set of all Fingerprints in the graph. Each Fingerprint corresponds to |
40 | /// the DepNode at the same index in the nodes vector. | |
17df50a5 | 41 | fingerprints: IndexVec<SerializedDepNodeIndex, Fingerprint>, |
ea8adc8c XL |
42 | /// For each DepNode, stores the list of edges originating from that |
43 | /// DepNode. Encoded as a [start, end) pair indexing into edge_list_data, | |
44 | /// which holds the actual DepNodeIndices of the target nodes. | |
17df50a5 | 45 | edge_list_indices: IndexVec<SerializedDepNodeIndex, (u32, u32)>, |
ea8adc8c XL |
46 | /// A flattened list of all edge targets in the graph. Edge sources are |
47 | /// implicit in edge_list_indices. | |
17df50a5 XL |
48 | edge_list_data: Vec<SerializedDepNodeIndex>, |
49 | /// Reciprocal map to `nodes`. | |
50 | index: FxHashMap<DepNode<K>, SerializedDepNodeIndex>, | |
ea8adc8c XL |
51 | } |
52 | ||
ba9703b0 XL |
53 | impl<K: DepKind> Default for SerializedDepGraph<K> { |
54 | fn default() -> Self { | |
55 | SerializedDepGraph { | |
56 | nodes: Default::default(), | |
57 | fingerprints: Default::default(), | |
58 | edge_list_indices: Default::default(), | |
59 | edge_list_data: Default::default(), | |
17df50a5 | 60 | index: Default::default(), |
ba9703b0 XL |
61 | } |
62 | } | |
63 | } | |
64 | ||
65 | impl<K: DepKind> SerializedDepGraph<K> { | |
ea8adc8c | 66 | #[inline] |
dfeec247 | 67 | pub fn edge_targets_from(&self, source: SerializedDepNodeIndex) -> &[SerializedDepNodeIndex] { |
ea8adc8c XL |
68 | let targets = self.edge_list_indices[source]; |
69 | &self.edge_list_data[targets.0 as usize..targets.1 as usize] | |
70 | } | |
17df50a5 XL |
71 | |
72 | #[inline] | |
73 | pub fn index_to_node(&self, dep_node_index: SerializedDepNodeIndex) -> DepNode<K> { | |
74 | self.nodes[dep_node_index] | |
75 | } | |
76 | ||
77 | #[inline] | |
78 | pub fn node_to_index_opt(&self, dep_node: &DepNode<K>) -> Option<SerializedDepNodeIndex> { | |
79 | self.index.get(dep_node).cloned() | |
80 | } | |
81 | ||
82 | #[inline] | |
83 | pub fn fingerprint_of(&self, dep_node: &DepNode<K>) -> Option<Fingerprint> { | |
84 | self.index.get(dep_node).map(|&node_index| self.fingerprints[node_index]) | |
85 | } | |
86 | ||
87 | #[inline] | |
88 | pub fn fingerprint_by_index(&self, dep_node_index: SerializedDepNodeIndex) -> Fingerprint { | |
89 | self.fingerprints[dep_node_index] | |
90 | } | |
91 | ||
92 | pub fn node_count(&self) -> usize { | |
93 | self.index.len() | |
94 | } | |
ea8adc8c | 95 | } |
5869c6ff | 96 | |
923072b8 | 97 | impl<'a, K: DepKind + Decodable<MemDecoder<'a>>> Decodable<MemDecoder<'a>> |
cdc7bbd5 XL |
98 | for SerializedDepGraph<K> |
99 | { | |
c295e0f8 | 100 | #[instrument(level = "debug", skip(d))] |
923072b8 | 101 | fn decode(d: &mut MemDecoder<'a>) -> SerializedDepGraph<K> { |
cdc7bbd5 | 102 | let start_position = d.position(); |
5869c6ff | 103 | |
cdc7bbd5 XL |
104 | // The last 16 bytes are the node count and edge count. |
105 | debug!("position: {:?}", d.position()); | |
106 | d.set_position(d.data.len() - 2 * IntEncodedWithFixedSize::ENCODED_SIZE); | |
107 | debug!("position: {:?}", d.position()); | |
5869c6ff | 108 | |
5099ac24 FG |
109 | let node_count = IntEncodedWithFixedSize::decode(d).0 as usize; |
110 | let edge_count = IntEncodedWithFixedSize::decode(d).0 as usize; | |
cdc7bbd5 XL |
111 | debug!(?node_count, ?edge_count); |
112 | ||
113 | debug!("position: {:?}", d.position()); | |
114 | d.set_position(start_position); | |
115 | debug!("position: {:?}", d.position()); | |
116 | ||
117 | let mut nodes = IndexVec::with_capacity(node_count); | |
118 | let mut fingerprints = IndexVec::with_capacity(node_count); | |
119 | let mut edge_list_indices = IndexVec::with_capacity(node_count); | |
120 | let mut edge_list_data = Vec::with_capacity(edge_count); | |
121 | ||
122 | for _index in 0..node_count { | |
5e7ed085 FG |
123 | let dep_node: DepNode<K> = Decodable::decode(d); |
124 | let _i: SerializedDepNodeIndex = nodes.push(dep_node); | |
125 | debug_assert_eq!(_i.index(), _index); | |
126 | ||
127 | let fingerprint: Fingerprint = Decodable::decode(d); | |
128 | let _i: SerializedDepNodeIndex = fingerprints.push(fingerprint); | |
129 | debug_assert_eq!(_i.index(), _index); | |
130 | ||
131 | // Deserialize edges -- sequence of DepNodeIndex | |
132 | let len = d.read_usize(); | |
133 | let start = edge_list_data.len().try_into().unwrap(); | |
134 | for _ in 0..len { | |
135 | let edge = Decodable::decode(d); | |
136 | edge_list_data.push(edge); | |
137 | } | |
138 | let end = edge_list_data.len().try_into().unwrap(); | |
139 | let _i: SerializedDepNodeIndex = edge_list_indices.push((start, end)); | |
140 | debug_assert_eq!(_i.index(), _index); | |
cdc7bbd5 XL |
141 | } |
142 | ||
17df50a5 XL |
143 | let index: FxHashMap<_, _> = |
144 | nodes.iter_enumerated().map(|(idx, &dep_node)| (dep_node, idx)).collect(); | |
145 | ||
5099ac24 | 146 | SerializedDepGraph { nodes, fingerprints, edge_list_indices, edge_list_data, index } |
cdc7bbd5 XL |
147 | } |
148 | } | |
149 | ||
150 | #[derive(Debug, Encodable, Decodable)] | |
151 | pub struct NodeInfo<K: DepKind> { | |
152 | node: DepNode<K>, | |
153 | fingerprint: Fingerprint, | |
154 | edges: SmallVec<[DepNodeIndex; 8]>, | |
155 | } | |
156 | ||
157 | struct Stat<K: DepKind> { | |
158 | kind: K, | |
159 | node_counter: u64, | |
160 | edge_counter: u64, | |
161 | } | |
162 | ||
163 | struct EncoderState<K: DepKind> { | |
164 | encoder: FileEncoder, | |
165 | total_node_count: usize, | |
166 | total_edge_count: usize, | |
cdc7bbd5 XL |
167 | stats: Option<FxHashMap<K, Stat<K>>>, |
168 | } | |
169 | ||
170 | impl<K: DepKind> EncoderState<K> { | |
171 | fn new(encoder: FileEncoder, record_stats: bool) -> Self { | |
172 | Self { | |
173 | encoder, | |
174 | total_edge_count: 0, | |
175 | total_node_count: 0, | |
5099ac24 | 176 | stats: record_stats.then(FxHashMap::default), |
cdc7bbd5 XL |
177 | } |
178 | } | |
179 | ||
cdc7bbd5 XL |
180 | fn encode_node( |
181 | &mut self, | |
182 | node: &NodeInfo<K>, | |
183 | record_graph: &Option<Lock<DepGraphQuery<K>>>, | |
184 | ) -> DepNodeIndex { | |
185 | let index = DepNodeIndex::new(self.total_node_count); | |
186 | self.total_node_count += 1; | |
187 | ||
188 | let edge_count = node.edges.len(); | |
189 | self.total_edge_count += edge_count; | |
190 | ||
191 | if let Some(record_graph) = &record_graph { | |
192 | // Do not ICE when a query is called from within `with_query`. | |
193 | if let Some(record_graph) = &mut record_graph.try_lock() { | |
194 | record_graph.push(index, node.node, &node.edges); | |
195 | } | |
196 | } | |
197 | ||
198 | if let Some(stats) = &mut self.stats { | |
199 | let kind = node.node.kind; | |
200 | ||
201 | let stat = stats.entry(kind).or_insert(Stat { kind, node_counter: 0, edge_counter: 0 }); | |
202 | stat.node_counter += 1; | |
203 | stat.edge_counter += edge_count as u64; | |
204 | } | |
205 | ||
cdc7bbd5 | 206 | let encoder = &mut self.encoder; |
923072b8 | 207 | node.encode(encoder); |
cdc7bbd5 XL |
208 | index |
209 | } | |
210 | ||
3c0e092e | 211 | fn finish(self, profiler: &SelfProfilerRef) -> FileEncodeResult { |
923072b8 | 212 | let Self { mut encoder, total_node_count, total_edge_count, stats: _ } = self; |
cdc7bbd5 XL |
213 | |
214 | let node_count = total_node_count.try_into().unwrap(); | |
215 | let edge_count = total_edge_count.try_into().unwrap(); | |
216 | ||
217 | debug!(?node_count, ?edge_count); | |
218 | debug!("position: {:?}", encoder.position()); | |
923072b8 FG |
219 | IntEncodedWithFixedSize(node_count).encode(&mut encoder); |
220 | IntEncodedWithFixedSize(edge_count).encode(&mut encoder); | |
cdc7bbd5 XL |
221 | debug!("position: {:?}", encoder.position()); |
222 | // Drop the encoder so that nothing is written after the counts. | |
923072b8 FG |
223 | let result = encoder.finish(); |
224 | if let Ok(position) = result { | |
225 | // FIXME(rylev): we hardcode the dep graph file name so we | |
226 | // don't need a dependency on rustc_incremental just for that. | |
227 | profiler.artifact_size("dep_graph", "dep-graph.bin", position as u64); | |
228 | } | |
3c0e092e | 229 | result |
cdc7bbd5 XL |
230 | } |
231 | } | |
232 | ||
233 | pub struct GraphEncoder<K: DepKind> { | |
234 | status: Lock<EncoderState<K>>, | |
235 | record_graph: Option<Lock<DepGraphQuery<K>>>, | |
236 | } | |
237 | ||
238 | impl<K: DepKind + Encodable<FileEncoder>> GraphEncoder<K> { | |
239 | pub fn new( | |
240 | encoder: FileEncoder, | |
241 | prev_node_count: usize, | |
242 | record_graph: bool, | |
243 | record_stats: bool, | |
244 | ) -> Self { | |
245 | let record_graph = | |
246 | if record_graph { Some(Lock::new(DepGraphQuery::new(prev_node_count))) } else { None }; | |
247 | let status = Lock::new(EncoderState::new(encoder, record_stats)); | |
248 | GraphEncoder { status, record_graph } | |
249 | } | |
250 | ||
251 | pub(crate) fn with_query(&self, f: impl Fn(&DepGraphQuery<K>)) { | |
252 | if let Some(record_graph) = &self.record_graph { | |
253 | f(&record_graph.lock()) | |
254 | } | |
255 | } | |
256 | ||
257 | pub(crate) fn print_incremental_info( | |
258 | &self, | |
259 | total_read_count: u64, | |
260 | total_duplicate_read_count: u64, | |
261 | ) { | |
262 | let status = self.status.lock(); | |
263 | if let Some(record_stats) = &status.stats { | |
264 | let mut stats: Vec<_> = record_stats.values().collect(); | |
265 | stats.sort_by_key(|s| -(s.node_counter as i64)); | |
266 | ||
267 | const SEPARATOR: &str = "[incremental] --------------------------------\ | |
268 | ----------------------------------------------\ | |
269 | ------------"; | |
270 | ||
271 | eprintln!("[incremental]"); | |
272 | eprintln!("[incremental] DepGraph Statistics"); | |
9c376795 | 273 | eprintln!("{SEPARATOR}"); |
cdc7bbd5 XL |
274 | eprintln!("[incremental]"); |
275 | eprintln!("[incremental] Total Node Count: {}", status.total_node_count); | |
276 | eprintln!("[incremental] Total Edge Count: {}", status.total_edge_count); | |
277 | ||
278 | if cfg!(debug_assertions) { | |
9c376795 FG |
279 | eprintln!("[incremental] Total Edge Reads: {total_read_count}"); |
280 | eprintln!("[incremental] Total Duplicate Edge Reads: {total_duplicate_read_count}"); | |
cdc7bbd5 XL |
281 | } |
282 | ||
283 | eprintln!("[incremental]"); | |
284 | eprintln!( | |
285 | "[incremental] {:<36}| {:<17}| {:<12}| {:<17}|", | |
286 | "Node Kind", "Node Frequency", "Node Count", "Avg. Edge Count" | |
287 | ); | |
9c376795 | 288 | eprintln!("{SEPARATOR}"); |
cdc7bbd5 XL |
289 | |
290 | for stat in stats { | |
291 | let node_kind_ratio = | |
292 | (100.0 * (stat.node_counter as f64)) / (status.total_node_count as f64); | |
293 | let node_kind_avg_edges = (stat.edge_counter as f64) / (stat.node_counter as f64); | |
294 | ||
295 | eprintln!( | |
296 | "[incremental] {:<36}|{:>16.1}% |{:>12} |{:>17.1} |", | |
297 | format!("{:?}", stat.kind), | |
298 | node_kind_ratio, | |
299 | stat.node_counter, | |
300 | node_kind_avg_edges, | |
301 | ); | |
302 | } | |
303 | ||
9c376795 | 304 | eprintln!("{SEPARATOR}"); |
cdc7bbd5 XL |
305 | eprintln!("[incremental]"); |
306 | } | |
307 | } | |
308 | ||
309 | pub(crate) fn send( | |
310 | &self, | |
311 | profiler: &SelfProfilerRef, | |
312 | node: DepNode<K>, | |
313 | fingerprint: Fingerprint, | |
314 | edges: SmallVec<[DepNodeIndex; 8]>, | |
315 | ) -> DepNodeIndex { | |
316 | let _prof_timer = profiler.generic_activity("incr_comp_encode_dep_graph"); | |
317 | let node = NodeInfo { node, fingerprint, edges }; | |
318 | self.status.lock().encode_node(&node, &self.record_graph) | |
319 | } | |
5869c6ff | 320 | |
cdc7bbd5 XL |
321 | pub fn finish(self, profiler: &SelfProfilerRef) -> FileEncodeResult { |
322 | let _prof_timer = profiler.generic_activity("incr_comp_encode_dep_graph"); | |
3c0e092e | 323 | self.status.into_inner().finish(profiler) |
5869c6ff XL |
324 | } |
325 | } |