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 deserialization 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::{FileEncodeResult, FileEncoder, IntEncodedWithFixedSize, MemDecoder};
  23 use rustc_serialize::{Decodable, Decoder, Encodable};
  24 use smallvec::SmallVec;
  25
  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.
  29 rustc_index::newtype_index! {
  30     #[max = 0x7FFF_FFFF]
  31     pub struct SerializedDepNodeIndex {}
  32 }
  33
  34 /// Data for use when recompiling the **current crate**.
  35 #[derive(Debug)]
  36 pub struct SerializedDepGraph<K: DepKind> {
  37     /// The set of all DepNodes in the graph
  38     nodes: IndexVec<SerializedDepNodeIndex, DepNode<K>>,
  39     /// The set of all Fingerprints in the graph. Each Fingerprint corresponds to
  40     /// the DepNode at the same index in the nodes vector.
  41     fingerprints: IndexVec<SerializedDepNodeIndex, Fingerprint>,
  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.
  45     edge_list_indices: IndexVec<SerializedDepNodeIndex, (u32, u32)>,
  46     /// A flattened list of all edge targets in the graph. Edge sources are
  47     /// implicit in edge_list_indices.
  48     edge_list_data: Vec<SerializedDepNodeIndex>,
  49     /// Reciprocal map to `nodes`.
  50     index: FxHashMap<DepNode<K>, SerializedDepNodeIndex>,
  51 }
  52
  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(),
  60             index: Default::default(),
  61         }
  62     }
  63 }
  64
  65 impl<K: DepKind> SerializedDepGraph<K> {
  66     #[inline]
  67     pub fn edge_targets_from(&self, source: SerializedDepNodeIndex) -> &[SerializedDepNodeIndex] {
  68         let targets = self.edge_list_indices[source];
  69         &self.edge_list_data[targets.0 as usize..targets.1 as usize]
  70     }
  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     }
  95 }
  96
  97 impl<'a, K: DepKind + Decodable<MemDecoder<'a>>> Decodable<MemDecoder<'a>>
  98     for SerializedDepGraph<K>
  99 {
 100     #[instrument(level = "debug", skip(d))]
 101     fn decode(d: &mut MemDecoder<'a>) -> SerializedDepGraph<K> {
 102         let start_position = d.position();
 103
 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());
 108
 109         let node_count = IntEncodedWithFixedSize::decode(d).0 as usize;
 110         let edge_count = IntEncodedWithFixedSize::decode(d).0 as usize;
 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 {
 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);
 141         }
 142
 143         let index: FxHashMap<_, _> =
 144             nodes.iter_enumerated().map(|(idx, &dep_node)| (dep_node, idx)).collect();
 145
 146         SerializedDepGraph { nodes, fingerprints, edge_list_indices, edge_list_data, index }
 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,
 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,
 176             stats: record_stats.then(FxHashMap::default),
 177         }
 178     }
 179
 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
 206         let encoder = &mut self.encoder;
 207         node.encode(encoder);
 208         index
 209     }
 210
 211     fn finish(self, profiler: &SelfProfilerRef) -> FileEncodeResult {
 212         let Self { mut encoder, total_node_count, total_edge_count, stats: _ } = self;
 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());
 219         IntEncodedWithFixedSize(node_count).encode(&mut encoder);
 220         IntEncodedWithFixedSize(edge_count).encode(&mut encoder);
 221         debug!("position: {:?}", encoder.position());
 222         // Drop the encoder so that nothing is written after the counts.
 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         }
 229         result
 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");
 273             eprintln!("{}", SEPARATOR);
 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) {
 279                 eprintln!("[incremental] Total Edge Reads: {}", total_read_count);
 280                 eprintln!(
 281                     "[incremental] Total Duplicate Edge Reads: {}",
 282                     total_duplicate_read_count
 283                 );
 284             }
 285
 286             eprintln!("[incremental]");
 287             eprintln!(
 288                 "[incremental]  {:<36}| {:<17}| {:<12}| {:<17}|",
 289                 "Node Kind", "Node Frequency", "Node Count", "Avg. Edge Count"
 290             );
 291             eprintln!("{}", SEPARATOR);
 292
 293             for stat in stats {
 294                 let node_kind_ratio =
 295                     (100.0 * (stat.node_counter as f64)) / (status.total_node_count as f64);
 296                 let node_kind_avg_edges = (stat.edge_counter as f64) / (stat.node_counter as f64);
 297
 298                 eprintln!(
 299                     "[incremental]  {:<36}|{:>16.1}% |{:>12} |{:>17.1} |",
 300                     format!("{:?}", stat.kind),
 301                     node_kind_ratio,
 302                     stat.node_counter,
 303                     node_kind_avg_edges,
 304                 );
 305             }
 306
 307             eprintln!("{}", SEPARATOR);
 308             eprintln!("[incremental]");
 309         }
 310     }
 311
 312     pub(crate) fn send(
 313         &self,
 314         profiler: &SelfProfilerRef,
 315         node: DepNode<K>,
 316         fingerprint: Fingerprint,
 317         edges: SmallVec<[DepNodeIndex; 8]>,
 318     ) -> DepNodeIndex {
 319         let _prof_timer = profiler.generic_activity("incr_comp_encode_dep_graph");
 320         let node = NodeInfo { node, fingerprint, edges };
 321         self.status.lock().encode_node(&node, &self.record_graph)
 322     }
 323
 324     pub fn finish(self, profiler: &SelfProfilerRef) -> FileEncodeResult {
 325         let _prof_timer = profiler.generic_activity("incr_comp_encode_dep_graph");
 326         self.status.into_inner().finish(profiler)
 327     }
 328 }