compiler/rustc_query_system/src/dep_graph/serialized.rs

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