1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223
// Copyright 2014 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. //! Second phase. Construct new graph. The previous phase has //! converted the input graph into a DAG by detecting and unifying //! cycles. It provides us with the following (which is a //! representation of the DAG): //! //! - SCCs, in the form of a union-find repr that can convert each node to //! its *cycle head* (an arbitrarly chosen representative from the cycle) //! - a vector of *leaf nodes*, just a convenience //! - a vector of *parents* for each node (in some cases, nodes have no parents, //! or their parent is another member of same cycle; in that case, the vector //! will be stored `v[i] == i`, after canonicalization) //! - a vector of *cross edges*, meaning add'l edges between graphs nodes beyond //! the parents. use rustc_data_structures::fx::FxHashMap; use super::*; pub(super) fn construct_graph<'g, N, I, O>(r: &mut GraphReduce<'g, N, I, O>, dag: Dag) -> Reduction<'g, N> where N: Debug + Clone, I: Fn(&N) -> bool, O: Fn(&N) -> bool, { let Dag { parents: old_parents, input_nodes, output_nodes, cross_edges } = dag; let in_graph = r.in_graph; debug!("construct_graph"); // Create a canonical list of edges; this includes both parent and // cross-edges. We store this in `(target -> Vec<source>)` form. // We call the first edge to any given target its "parent". let mut edges = FxHashMap(); let old_parent_edges = old_parents.iter().cloned().zip((0..).map(NodeIndex)); for (source, target) in old_parent_edges.chain(cross_edges) { debug!("original edge `{:?} -rf-> {:?}`", in_graph.node_data(source), in_graph.node_data(target)); let source = r.cycle_head(source); let target = r.cycle_head(target); if source != target { let v = edges.entry(target).or_insert(vec![]); if !v.contains(&source) { debug!("edge `{:?} -rf-> {:?}` is edge #{} with that target", in_graph.node_data(source), in_graph.node_data(target), v.len()); v.push(source); } } } let parent = |ni: NodeIndex| -> NodeIndex { edges[&ni][0] }; // `retain_map`: a map of those nodes that we will want to // *retain* in the ultimate graph; the key is the node index in // the old graph, the value is the node index in the new // graph. These are nodes in the following categories: // // - inputs // - work-products // - targets of a cross-edge // // The first two categories hopefully make sense. We want the // inputs so we can compare hashes later. We want the // work-products so we can tell precisely when a given // work-product is invalidated. But the last one isn't strictly // needed; we keep cross-target edges so as to minimize the total // graph size. // // Consider a graph like: // // WP0 -rf-> Y // WP1 -rf-> Y // Y -rf-> INPUT0 // Y -rf-> INPUT1 // Y -rf-> INPUT2 // Y -rf-> INPUT3 // // Now if we were to remove Y, we would have a total of 8 edges: both WP0 and WP1 // depend on INPUT0...INPUT3. As it is, we have 6 edges. // // NB: The current rules are not optimal. For example, given this // input graph: // // OUT0 -rf-> X // OUT1 -rf-> X // X -rf -> INPUT0 // // we will preserve X because it has two "consumers" (OUT0 and // OUT1). We could as easily skip it, but we'd have to tally up // the number of input nodes that it (transitively) reaches, and I // was too lazy to do so. This is the unit test `suboptimal`. let mut retain_map = FxHashMap(); let mut new_graph = Graph::new(); { // Start by adding start-nodes and inputs. let retained_nodes = output_nodes.iter().chain(&input_nodes).map(|&n| r.cycle_head(n)); // Next add in targets of cross-edges. Due to the canonicalization, // some of these may be self-edges or may may duplicate the parent // edges, so ignore those. let retained_nodes = retained_nodes.chain( edges.iter() .filter(|&(_, ref sources)| sources.len() > 1) .map(|(&target, _)| target)); // Now create the new graph, adding in the entries from the map. for n in retained_nodes { retain_map.entry(n) .or_insert_with(|| { let data = in_graph.node_data(n); debug!("retaining node `{:?}`", data); new_graph.add_node(data) }); } } // Given a cycle-head `ni`, converts it to the closest parent that has // been retained in the output graph. let retained_parent = |mut ni: NodeIndex| -> NodeIndex { loop { debug!("retained_parent({:?})", in_graph.node_data(ni)); match retain_map.get(&ni) { Some(&v) => return v, None => ni = parent(ni), } } }; // Now add in the edges into the graph. for (&target, sources) in &edges { if let Some(&r_target) = retain_map.get(&target) { debug!("adding edges that target `{:?}`", in_graph.node_data(target)); for &source in sources { debug!("new edge `{:?} -rf-> {:?}`", in_graph.node_data(source), in_graph.node_data(target)); let r_source = retained_parent(source); // NB. In the input graph, we have `a -> b` if b // **reads from** a. But in the terminology of this // code, we would describe that edge as `b -> a`, // because we have edges *from* outputs *to* inputs. // Therefore, when we create our new graph, we have to // reverse the edge. new_graph.add_edge(r_target, r_source, ()); } } else { assert_eq!(sources.len(), 1); } } // One complication. In some cases, output nodes *may* participate in // cycles. An example: // // [HIR0] [HIR1] // | | // v v // TypeckClosureBody(X) -> ItemSignature(X::SomeClosureInX) // | ^ | | // | +-------------------------+ | // | | // v v // Foo Bar // // In these cases, the output node may not wind up as the head // of the cycle, in which case it would be absent from the // final graph. We don't wish this to happen, therefore we go // over the list of output nodes again and check for any that // are not their own cycle-head. If we find such a node, we // add it to the graph now with an edge from the cycle head. // So the graph above could get transformed into this: // // [HIR0, HIR1] // | // v // TypeckClosureBody(X) ItemSignature(X::SomeClosureInX) // ^ | | // +-------------------------+ | // v // [Foo, Bar] // // (Note that all the edges here are "read-by" edges, not // "reads-from" edges.) for &output_node in &output_nodes { let head = r.cycle_head(output_node); if output_node == head { assert!(retain_map.contains_key(&output_node)); } else { assert!(!retain_map.contains_key(&output_node)); let output_data = in_graph.node_data(output_node); let new_node = new_graph.add_node(output_data); let new_head_node = retain_map[&head]; new_graph.add_edge(new_head_node, new_node, ()); } } // Finally, prepare a list of the input node indices as found in // the new graph. Note that since all input nodes are leaves in // the graph, they should never participate in a cycle. let input_nodes = input_nodes.iter() .map(|&n| { assert_eq!(r.cycle_head(n), n, "input node participating in a cycle"); retain_map[&n] }) .collect(); Reduction { graph: new_graph, input_nodes: input_nodes } }