Auto merge of #51987 - nikomatsakis:nll-region-infer-scc, r=pnkfelix

nll experiment: compute SCCs instead of iterative region solving

This is an attempt to speed up region solving by replacing the current iterative dataflow with a SCC computation. The idea is to detect cycles (SCCs) amongst region constraints and then compute just one value per cycle. The graph with all cycles removed is of course a DAG, so we can then solve constraints "bottom up" once the liveness values are known.

I kinda ran out of time this morning so the last commit is a bit sloppy but I wanted to get this posted, let travis run on it, and maybe do a perf run, before I clean it up.

14 files changed, 1089 insertions, 481 deletions

diff --git a/src/librustc_data_structures/control_flow_graph/mod.rs b/src/librustc_data_structures/control_flow_graph/mod.rs
deleted file mode 100644
index 7bf776675c6..00000000000
--- a/src/librustc_data_structures/control_flow_graph/mod.rs
+++ /dev/null
@@ -1,42 +0,0 @@
-// Copyright 2016 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::indexed_vec::Idx;
-
-pub mod dominators;
-pub mod iterate;
-mod reference;
-
-#[cfg(test)]
-mod test;
-
-pub trait ControlFlowGraph
-    where Self: for<'graph> GraphPredecessors<'graph, Item=<Self as ControlFlowGraph>::Node>,
-          Self: for<'graph> GraphSuccessors<'graph, Item=<Self as ControlFlowGraph>::Node>
-{
-    type Node: Idx;
-
-    fn num_nodes(&self) -> usize;
-    fn start_node(&self) -> Self::Node;
-    fn predecessors<'graph>(&'graph self, node: Self::Node)
-                            -> <Self as GraphPredecessors<'graph>>::Iter;
-    fn successors<'graph>(&'graph self, node: Self::Node)
-                            -> <Self as GraphSuccessors<'graph>>::Iter;
-}
-
-pub trait GraphPredecessors<'graph> {
-    type Item;
-    type Iter: Iterator<Item = Self::Item>;
-}
-
-pub trait GraphSuccessors<'graph> {
-    type Item;
-    type Iter: Iterator<Item = Self::Item>;
-}
diff --git a/src/librustc_data_structures/control_flow_graph/dominators/mod.rs b/src/librustc_data_structures/graph/dominators/mod.rs
index 54407658e6c..d134fad2855 100644
--- a/src/librustc_data_structures/control_flow_graph/dominators/mod.rs
+++ b/src/librustc_data_structures/graph/dominators/mod.rs
@@ -14,9 +14,9 @@
 //! Rice Computer Science TS-06-33870
 //! <https://www.cs.rice.edu/~keith/EMBED/dom.pdf>
 
-use super::ControlFlowGraph;
+use super::super::indexed_vec::{Idx, IndexVec};
 use super::iterate::reverse_post_order;
-use super::super::indexed_vec::{IndexVec, Idx};
+use super::ControlFlowGraph;
 
 use std::fmt;
 
@@ -29,15 +29,16 @@ pub fn dominators<G: ControlFlowGraph>(graph: &G) -> Dominators<G::Node> {
     dominators_given_rpo(graph, &rpo)
 }
 
-pub fn dominators_given_rpo<G: ControlFlowGraph>(graph: &G,
-                                                 rpo: &[G::Node])
-                                                 -> Dominators<G::Node> {
+pub fn dominators_given_rpo<G: ControlFlowGraph>(
+    graph: &G,
+    rpo: &[G::Node],
+) -> Dominators<G::Node> {
     let start_node = graph.start_node();
     assert_eq!(rpo[0], start_node);
 
     // compute the post order index (rank) for each node
-    let mut post_order_rank: IndexVec<G::Node, usize> = IndexVec::from_elem_n(usize::default(),
-                                                                              graph.num_nodes());
+    let mut post_order_rank: IndexVec<G::Node, usize> =
+        IndexVec::from_elem_n(usize::default(), graph.num_nodes());
     for (index, node) in rpo.iter().rev().cloned().enumerate() {
         post_order_rank[node] = index;
     }
@@ -56,10 +57,12 @@ pub fn dominators_given_rpo<G: ControlFlowGraph>(graph: &G,
                 if immediate_dominators[pred].is_some() {
                     // (*)
                     // (*) dominators for `pred` have been calculated
-                    new_idom = intersect_opt(&post_order_rank,
-                                             &immediate_dominators,
-                                             new_idom,
-                                             Some(pred));
+                    new_idom = intersect_opt(
+                        &post_order_rank,
+                        &immediate_dominators,
+                        new_idom,
+                        Some(pred),
+                    );
                 }
             }
 
@@ -76,11 +79,12 @@ pub fn dominators_given_rpo<G: ControlFlowGraph>(graph: &G,
     }
 }
 
-fn intersect_opt<Node: Idx>(post_order_rank: &IndexVec<Node, usize>,
-                            immediate_dominators: &IndexVec<Node, Option<Node>>,
-                            node1: Option<Node>,
-                            node2: Option<Node>)
-                            -> Option<Node> {
+fn intersect_opt<Node: Idx>(
+    post_order_rank: &IndexVec<Node, usize>,
+    immediate_dominators: &IndexVec<Node, Option<Node>>,
+    node1: Option<Node>,
+    node2: Option<Node>,
+) -> Option<Node> {
     match (node1, node2) {
         (None, None) => None,
         (Some(n), None) | (None, Some(n)) => Some(n),
@@ -88,11 +92,12 @@ fn intersect_opt<Node: Idx>(post_order_rank: &IndexVec<Node, usize>,
     }
 }
 
-fn intersect<Node: Idx>(post_order_rank: &IndexVec<Node, usize>,
-                        immediate_dominators: &IndexVec<Node, Option<Node>>,
-                        mut node1: Node,
-                        mut node2: Node)
-                        -> Node {
+fn intersect<Node: Idx>(
+    post_order_rank: &IndexVec<Node, usize>,
+    immediate_dominators: &IndexVec<Node, Option<Node>>,
+    mut node1: Node,
+    mut node2: Node,
+) -> Node {
     while node1 != node2 {
         while post_order_rank[node1] < post_order_rank[node2] {
             node1 = immediate_dominators[node1].unwrap();
@@ -176,11 +181,13 @@ impl<Node: Idx> DominatorTree<Node> {
 
 impl<Node: Idx> fmt::Debug for DominatorTree<Node> {
     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
-        fmt::Debug::fmt(&DominatorTreeNode {
-                            tree: self,
-                            node: self.root,
-                        },
-                        fmt)
+        fmt::Debug::fmt(
+            &DominatorTreeNode {
+                tree: self,
+                node: self.root,
+            },
+            fmt,
+        )
     }
 }
 
@@ -194,11 +201,9 @@ impl<'tree, Node: Idx> fmt::Debug for DominatorTreeNode<'tree, Node> {
         let subtrees: Vec<_> = self.tree
             .children(self.node)
             .iter()
-            .map(|&child| {
-                DominatorTreeNode {
-                    tree: self.tree,
-                    node: child,
-                }
+            .map(|&child| DominatorTreeNode {
+                tree: self.tree,
+                node: child,
             })
             .collect();
         fmt.debug_tuple("")
diff --git a/src/librustc_data_structures/control_flow_graph/dominators/test.rs b/src/librustc_data_structures/graph/dominators/test.rs
index 0af878cac2d..0af878cac2d 100644
--- a/src/librustc_data_structures/control_flow_graph/dominators/test.rs
+++ b/src/librustc_data_structures/graph/dominators/test.rs
diff --git a/src/librustc_data_structures/graph/implementation/mod.rs b/src/librustc_data_structures/graph/implementation/mod.rs
new file mode 100644
index 00000000000..e2b393071ff
--- /dev/null
+++ b/src/librustc_data_structures/graph/implementation/mod.rs
@@ -0,0 +1,417 @@
+// Copyright 2012-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.
+
+//! A graph module for use in dataflow, region resolution, and elsewhere.
+//!
+//! # Interface details
+//!
+//! You customize the graph by specifying a "node data" type `N` and an
+//! "edge data" type `E`. You can then later gain access (mutable or
+//! immutable) to these "user-data" bits. Currently, you can only add
+//! nodes or edges to the graph. You cannot remove or modify them once
+//! added. This could be changed if we have a need.
+//!
+//! # Implementation details
+//!
+//! The main tricky thing about this code is the way that edges are
+//! stored. The edges are stored in a central array, but they are also
+//! threaded onto two linked lists for each node, one for incoming edges
+//! and one for outgoing edges. Note that every edge is a member of some
+//! incoming list and some outgoing list.  Basically you can load the
+//! first index of the linked list from the node data structures (the
+//! field `first_edge`) and then, for each edge, load the next index from
+//! the field `next_edge`). Each of those fields is an array that should
+//! be indexed by the direction (see the type `Direction`).
+
+use bitvec::BitVector;
+use std::fmt::Debug;
+use std::usize;
+use snapshot_vec::{SnapshotVec, SnapshotVecDelegate};
+
+#[cfg(test)]
+mod tests;
+
+pub struct Graph<N, E> {
+    nodes: SnapshotVec<Node<N>>,
+    edges: SnapshotVec<Edge<E>>,
+}
+
+pub struct Node<N> {
+    first_edge: [EdgeIndex; 2], // see module comment
+    pub data: N,
+}
+
+#[derive(Debug)]
+pub struct Edge<E> {
+    next_edge: [EdgeIndex; 2], // see module comment
+    source: NodeIndex,
+    target: NodeIndex,
+    pub data: E,
+}
+
+impl<N> SnapshotVecDelegate for Node<N> {
+    type Value = Node<N>;
+    type Undo = ();
+
+    fn reverse(_: &mut Vec<Node<N>>, _: ()) {}
+}
+
+impl<N> SnapshotVecDelegate for Edge<N> {
+    type Value = Edge<N>;
+    type Undo = ();
+
+    fn reverse(_: &mut Vec<Edge<N>>, _: ()) {}
+}
+
+#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
+pub struct NodeIndex(pub usize);
+
+#[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, PartialEq)]
+pub struct Direction {
+    repr: usize,
+}
+
+pub const OUTGOING: Direction = Direction { repr: 0 };
+
+pub const INCOMING: Direction = Direction { repr: 1 };
+
+impl NodeIndex {
+    /// Returns unique id (unique with respect to the graph holding associated node).
+    pub fn node_id(&self) -> usize {
+        self.0
+    }
+}
+
+impl<N: Debug, E: Debug> Graph<N, E> {
+    pub fn new() -> Graph<N, E> {
+        Graph {
+            nodes: SnapshotVec::new(),
+            edges: SnapshotVec::new(),
+        }
+    }
+
+    pub fn with_capacity(nodes: usize, edges: usize) -> Graph<N, E> {
+        Graph {
+            nodes: SnapshotVec::with_capacity(nodes),
+            edges: SnapshotVec::with_capacity(edges),
+        }
+    }
+
+    // # Simple accessors
+
+    #[inline]
+    pub fn all_nodes(&self) -> &[Node<N>] {
+        &self.nodes
+    }
+
+    #[inline]
+    pub fn len_nodes(&self) -> usize {
+        self.nodes.len()
+    }
+
+    #[inline]
+    pub fn all_edges(&self) -> &[Edge<E>] {
+        &self.edges
+    }
+
+    #[inline]
+    pub fn len_edges(&self) -> usize {
+        self.edges.len()
+    }
+
+    // # Node construction
+
+    pub fn next_node_index(&self) -> NodeIndex {
+        NodeIndex(self.nodes.len())
+    }
+
+    pub fn add_node(&mut self, data: N) -> NodeIndex {
+        let idx = self.next_node_index();
+        self.nodes.push(Node {
+            first_edge: [INVALID_EDGE_INDEX, INVALID_EDGE_INDEX],
+            data,
+        });
+        idx
+    }
+
+    pub fn mut_node_data(&mut self, idx: NodeIndex) -> &mut N {
+        &mut self.nodes[idx.0].data
+    }
+
+    pub fn node_data(&self, idx: NodeIndex) -> &N {
+        &self.nodes[idx.0].data
+    }
+
+    pub fn node(&self, idx: NodeIndex) -> &Node<N> {
+        &self.nodes[idx.0]
+    }
+
+    // # Edge construction and queries
+
+    pub fn next_edge_index(&self) -> EdgeIndex {
+        EdgeIndex(self.edges.len())
+    }
+
+    pub fn add_edge(&mut self, source: NodeIndex, target: NodeIndex, data: E) -> EdgeIndex {
+        debug!("graph: add_edge({:?}, {:?}, {:?})", source, target, data);
+
+        let idx = self.next_edge_index();
+
+        // read current first of the list of edges from each node
+        let source_first = self.nodes[source.0].first_edge[OUTGOING.repr];
+        let target_first = self.nodes[target.0].first_edge[INCOMING.repr];
+
+        // create the new edge, with the previous firsts from each node
+        // as the next pointers
+        self.edges.push(Edge {
+            next_edge: [source_first, target_first],
+            source,
+            target,
+            data,
+        });
+
+        // adjust the firsts for each node target be the next object.
+        self.nodes[source.0].first_edge[OUTGOING.repr] = idx;
+        self.nodes[target.0].first_edge[INCOMING.repr] = idx;
+
+        return idx;
+    }
+
+    pub fn edge(&self, idx: EdgeIndex) -> &Edge<E> {
+        &self.edges[idx.0]
+    }
+
+    // # Iterating over nodes, edges
+
+    pub fn enumerated_nodes(&self) -> impl Iterator<Item = (NodeIndex, &Node<N>)> {
+        self.nodes
+            .iter()
+            .enumerate()
+            .map(|(idx, n)| (NodeIndex(idx), n))
+    }
+
+    pub fn enumerated_edges(&self) -> impl Iterator<Item = (EdgeIndex, &Edge<E>)> {
+        self.edges
+            .iter()
+            .enumerate()
+            .map(|(idx, e)| (EdgeIndex(idx), e))
+    }
+
+    pub fn each_node<'a>(&'a self, mut f: impl FnMut(NodeIndex, &'a Node<N>) -> bool) -> bool {
+        //! Iterates over all edges defined in the graph.
+        self.enumerated_nodes()
+            .all(|(node_idx, node)| f(node_idx, node))
+    }
+
+    pub fn each_edge<'a>(&'a self, mut f: impl FnMut(EdgeIndex, &'a Edge<E>) -> bool) -> bool {
+        //! Iterates over all edges defined in the graph
+        self.enumerated_edges()
+            .all(|(edge_idx, edge)| f(edge_idx, edge))
+    }
+
+    pub fn outgoing_edges(&self, source: NodeIndex) -> AdjacentEdges<N, E> {
+        self.adjacent_edges(source, OUTGOING)
+    }
+
+    pub fn incoming_edges(&self, source: NodeIndex) -> AdjacentEdges<N, E> {
+        self.adjacent_edges(source, INCOMING)
+    }
+
+    pub fn adjacent_edges(&self, source: NodeIndex, direction: Direction) -> AdjacentEdges<N, E> {
+        let first_edge = self.node(source).first_edge[direction.repr];
+        AdjacentEdges {
+            graph: self,
+            direction,
+            next: first_edge,
+        }
+    }
+
+    pub fn successor_nodes<'a>(
+        &'a self,
+        source: NodeIndex,
+    ) -> impl Iterator<Item = NodeIndex> + 'a {
+        self.outgoing_edges(source).targets()
+    }
+
+    pub fn predecessor_nodes<'a>(
+        &'a self,
+        target: NodeIndex,
+    ) -> impl Iterator<Item = NodeIndex> + 'a {
+        self.incoming_edges(target).sources()
+    }
+
+    pub fn depth_traverse<'a>(
+        &'a self,
+        start: NodeIndex,
+        direction: Direction,
+    ) -> DepthFirstTraversal<'a, N, E> {
+        DepthFirstTraversal::with_start_node(self, start, direction)
+    }
+
+    pub fn nodes_in_postorder<'a>(
+        &'a self,
+        direction: Direction,
+        entry_node: NodeIndex,
+    ) -> Vec<NodeIndex> {
+        let mut visited = BitVector::new(self.len_nodes());
+        let mut stack = vec![];
+        let mut result = Vec::with_capacity(self.len_nodes());
+        let mut push_node = |stack: &mut Vec<_>, node: NodeIndex| {
+            if visited.insert(node.0) {
+                stack.push((node, self.adjacent_edges(node, direction)));
+            }
+        };
+
+        for node in Some(entry_node)
+            .into_iter()
+            .chain(self.enumerated_nodes().map(|(node, _)| node))
+        {
+            push_node(&mut stack, node);
+            while let Some((node, mut iter)) = stack.pop() {
+                if let Some((_, child)) = iter.next() {
+                    let target = child.source_or_target(direction);
+                    // the current node needs more processing, so
+                    // add it back to the stack
+                    stack.push((node, iter));
+                    // and then push the new node
+                    push_node(&mut stack, target);
+                } else {
+                    result.push(node);
+                }
+            }
+        }
+
+        assert_eq!(result.len(), self.len_nodes());
+        result
+    }
+}
+
+// # Iterators
+
+pub struct AdjacentEdges<'g, N, E>
+where
+    N: 'g,
+    E: 'g,
+{
+    graph: &'g Graph<N, E>,
+    direction: Direction,
+    next: EdgeIndex,
+}
+
+impl<'g, N: Debug, E: Debug> AdjacentEdges<'g, N, E> {
+    fn targets(self) -> impl Iterator<Item = NodeIndex> + 'g {
+        self.into_iter().map(|(_, edge)| edge.target)
+    }
+
+    fn sources(self) -> impl Iterator<Item = NodeIndex> + 'g {
+        self.into_iter().map(|(_, edge)| edge.source)
+    }
+}
+
+impl<'g, N: Debug, E: Debug> Iterator for AdjacentEdges<'g, N, E> {
+    type Item = (EdgeIndex, &'g Edge<E>);
+
+    fn next(&mut self) -> Option<(EdgeIndex, &'g Edge<E>)> {
+        let edge_index = self.next;
+        if edge_index == INVALID_EDGE_INDEX {
+            return None;
+        }
+
+        let edge = self.graph.edge(edge_index);
+        self.next = edge.next_edge[self.direction.repr];
+        Some((edge_index, edge))
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        // At most, all the edges in the graph.
+        (0, Some(self.graph.len_edges()))
+    }
+}
+
+pub struct DepthFirstTraversal<'g, N, E>
+where
+    N: 'g,
+    E: 'g,
+{
+    graph: &'g Graph<N, E>,
+    stack: Vec<NodeIndex>,
+    visited: BitVector,
+    direction: Direction,
+}
+
+impl<'g, N: Debug, E: Debug> DepthFirstTraversal<'g, N, E> {
+    pub fn with_start_node(
+        graph: &'g Graph<N, E>,
+        start_node: NodeIndex,
+        direction: Direction,
+    ) -> Self {
+        let mut visited = BitVector::new(graph.len_nodes());
+        visited.insert(start_node.node_id());
+        DepthFirstTraversal {
+            graph,
+            stack: vec![start_node],
+            visited,
+            direction,
+        }
+    }
+
+    fn visit(&mut self, node: NodeIndex) {
+        if self.visited.insert(node.node_id()) {
+            self.stack.push(node);
+        }
+    }
+}
+
+impl<'g, N: Debug, E: Debug> Iterator for DepthFirstTraversal<'g, N, E> {
+    type Item = NodeIndex;
+
+    fn next(&mut self) -> Option<NodeIndex> {
+        let next = self.stack.pop();
+        if let Some(idx) = next {
+            for (_, edge) in self.graph.adjacent_edges(idx, self.direction) {
+                let target = edge.source_or_target(self.direction);
+                self.visit(target);
+            }
+        }
+        next
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        // We will visit every node in the graph exactly once.
+        let remaining = self.graph.len_nodes() - self.visited.count();
+        (remaining, Some(remaining))
+    }
+}
+
+impl<'g, N: Debug, E: Debug> ExactSizeIterator for DepthFirstTraversal<'g, N, E> {}
+
+impl<E> Edge<E> {
+    pub fn source(&self) -> NodeIndex {
+        self.source
+    }
+
+    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/graph/tests.rs b/src/librustc_data_structures/graph/implementation/tests.rs
index 007704357af..3814827b5df 100644
--- a/src/librustc_data_structures/graph/tests.rs
+++ b/src/librustc_data_structures/graph/implementation/tests.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use graph::*;
+use graph::implementation::*;
 use std::fmt::Debug;
 
 type TestGraph = Graph<&'static str, &'static str>;
diff --git a/src/librustc_data_structures/control_flow_graph/iterate/mod.rs b/src/librustc_data_structures/graph/iterate/mod.rs
index 2d70b406342..3afdc88d602 100644
--- a/src/librustc_data_structures/control_flow_graph/iterate/mod.rs
+++ b/src/librustc_data_structures/graph/iterate/mod.rs
@@ -8,20 +8,24 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use super::ControlFlowGraph;
 use super::super::indexed_vec::IndexVec;
+use super::{DirectedGraph, WithSuccessors, WithNumNodes};
 
 #[cfg(test)]
 mod test;
 
-pub fn post_order_from<G: ControlFlowGraph>(graph: &G, start_node: G::Node) -> Vec<G::Node> {
+pub fn post_order_from<G: DirectedGraph + WithSuccessors + WithNumNodes>(
+    graph: &G,
+    start_node: G::Node,
+) -> Vec<G::Node> {
     post_order_from_to(graph, start_node, None)
 }
 
-pub fn post_order_from_to<G: ControlFlowGraph>(graph: &G,
-                                               start_node: G::Node,
-                                               end_node: Option<G::Node>)
-                                               -> Vec<G::Node> {
+pub fn post_order_from_to<G: DirectedGraph + WithSuccessors + WithNumNodes>(
+    graph: &G,
+    start_node: G::Node,
+    end_node: Option<G::Node>,
+) -> Vec<G::Node> {
     let mut visited: IndexVec<G::Node, bool> = IndexVec::from_elem_n(false, graph.num_nodes());
     let mut result: Vec<G::Node> = Vec::with_capacity(graph.num_nodes());
     if let Some(end_node) = end_node {
@@ -31,10 +35,12 @@ pub fn post_order_from_to<G: ControlFlowGraph>(graph: &G,
     result
 }
 
-fn post_order_walk<G: ControlFlowGraph>(graph: &G,
-                                        node: G::Node,
-                                        result: &mut Vec<G::Node>,
-                                        visited: &mut IndexVec<G::Node, bool>) {
+fn post_order_walk<G: DirectedGraph + WithSuccessors + WithNumNodes>(
+    graph: &G,
+    node: G::Node,
+    result: &mut Vec<G::Node>,
+    visited: &mut IndexVec<G::Node, bool>,
+) {
     if visited[node] {
         return;
     }
@@ -47,7 +53,10 @@ fn post_order_walk<G: ControlFlowGraph>(graph: &G,
     result.push(node);
 }
 
-pub fn reverse_post_order<G: ControlFlowGraph>(graph: &G, start_node: G::Node) -> Vec<G::Node> {
+pub fn reverse_post_order<G: DirectedGraph + WithSuccessors + WithNumNodes>(
+    graph: &G,
+    start_node: G::Node,
+) -> Vec<G::Node> {
     let mut vec = post_order_from(graph, start_node);
     vec.reverse();
     vec
diff --git a/src/librustc_data_structures/control_flow_graph/iterate/test.rs b/src/librustc_data_structures/graph/iterate/test.rs
index 100881ddfdd..100881ddfdd 100644
--- a/src/librustc_data_structures/control_flow_graph/iterate/test.rs
+++ b/src/librustc_data_structures/graph/iterate/test.rs
diff --git a/src/librustc_data_structures/graph/mod.rs b/src/librustc_data_structures/graph/mod.rs
index e2b393071ff..7265e4e8c7c 100644
--- a/src/librustc_data_structures/graph/mod.rs
+++ b/src/librustc_data_structures/graph/mod.rs
@@ -1,4 +1,4 @@
-// Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
+// Copyright 2016 The Rust Project Developers. See the COPYRIGHT
 // file at the top-level directory of this distribution and at
 // http://rust-lang.org/COPYRIGHT.
 //
@@ -8,410 +8,72 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-//! A graph module for use in dataflow, region resolution, and elsewhere.
-//!
-//! # Interface details
-//!
-//! You customize the graph by specifying a "node data" type `N` and an
-//! "edge data" type `E`. You can then later gain access (mutable or
-//! immutable) to these "user-data" bits. Currently, you can only add
-//! nodes or edges to the graph. You cannot remove or modify them once
-//! added. This could be changed if we have a need.
-//!
-//! # Implementation details
-//!
-//! The main tricky thing about this code is the way that edges are
-//! stored. The edges are stored in a central array, but they are also
-//! threaded onto two linked lists for each node, one for incoming edges
-//! and one for outgoing edges. Note that every edge is a member of some
-//! incoming list and some outgoing list.  Basically you can load the
-//! first index of the linked list from the node data structures (the
-//! field `first_edge`) and then, for each edge, load the next index from
-//! the field `next_edge`). Each of those fields is an array that should
-//! be indexed by the direction (see the type `Direction`).
+use super::indexed_vec::Idx;
 
-use bitvec::BitVector;
-use std::fmt::Debug;
-use std::usize;
-use snapshot_vec::{SnapshotVec, SnapshotVecDelegate};
+pub mod dominators;
+pub mod implementation;
+pub mod iterate;
+mod reference;
+pub mod scc;
 
 #[cfg(test)]
-mod tests;
+mod test;
 
-pub struct Graph<N, E> {
-    nodes: SnapshotVec<Node<N>>,
-    edges: SnapshotVec<Edge<E>>,
+pub trait DirectedGraph {
+    type Node: Idx;
 }
 
-pub struct Node<N> {
-    first_edge: [EdgeIndex; 2], // see module comment
-    pub data: N,
+pub trait WithNumNodes: DirectedGraph {
+    fn num_nodes(&self) -> usize;
 }
 
-#[derive(Debug)]
-pub struct Edge<E> {
-    next_edge: [EdgeIndex; 2], // see module comment
-    source: NodeIndex,
-    target: NodeIndex,
-    pub data: E,
-}
-
-impl<N> SnapshotVecDelegate for Node<N> {
-    type Value = Node<N>;
-    type Undo = ();
-
-    fn reverse(_: &mut Vec<Node<N>>, _: ()) {}
-}
-
-impl<N> SnapshotVecDelegate for Edge<N> {
-    type Value = Edge<N>;
-    type Undo = ();
-
-    fn reverse(_: &mut Vec<Edge<N>>, _: ()) {}
-}
-
-#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
-pub struct NodeIndex(pub usize);
-
-#[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, PartialEq)]
-pub struct Direction {
-    repr: usize,
-}
-
-pub const OUTGOING: Direction = Direction { repr: 0 };
-
-pub const INCOMING: Direction = Direction { repr: 1 };
-
-impl NodeIndex {
-    /// Returns unique id (unique with respect to the graph holding associated node).
-    pub fn node_id(&self) -> usize {
-        self.0
-    }
-}
-
-impl<N: Debug, E: Debug> Graph<N, E> {
-    pub fn new() -> Graph<N, E> {
-        Graph {
-            nodes: SnapshotVec::new(),
-            edges: SnapshotVec::new(),
-        }
-    }
-
-    pub fn with_capacity(nodes: usize, edges: usize) -> Graph<N, E> {
-        Graph {
-            nodes: SnapshotVec::with_capacity(nodes),
-            edges: SnapshotVec::with_capacity(edges),
-        }
-    }
-
-    // # Simple accessors
-
-    #[inline]
-    pub fn all_nodes(&self) -> &[Node<N>] {
-        &self.nodes
-    }
-
-    #[inline]
-    pub fn len_nodes(&self) -> usize {
-        self.nodes.len()
-    }
-
-    #[inline]
-    pub fn all_edges(&self) -> &[Edge<E>] {
-        &self.edges
-    }
-
-    #[inline]
-    pub fn len_edges(&self) -> usize {
-        self.edges.len()
-    }
-
-    // # Node construction
-
-    pub fn next_node_index(&self) -> NodeIndex {
-        NodeIndex(self.nodes.len())
-    }
-
-    pub fn add_node(&mut self, data: N) -> NodeIndex {
-        let idx = self.next_node_index();
-        self.nodes.push(Node {
-            first_edge: [INVALID_EDGE_INDEX, INVALID_EDGE_INDEX],
-            data,
-        });
-        idx
-    }
-
-    pub fn mut_node_data(&mut self, idx: NodeIndex) -> &mut N {
-        &mut self.nodes[idx.0].data
-    }
-
-    pub fn node_data(&self, idx: NodeIndex) -> &N {
-        &self.nodes[idx.0].data
-    }
-
-    pub fn node(&self, idx: NodeIndex) -> &Node<N> {
-        &self.nodes[idx.0]
-    }
-
-    // # Edge construction and queries
-
-    pub fn next_edge_index(&self) -> EdgeIndex {
-        EdgeIndex(self.edges.len())
-    }
-
-    pub fn add_edge(&mut self, source: NodeIndex, target: NodeIndex, data: E) -> EdgeIndex {
-        debug!("graph: add_edge({:?}, {:?}, {:?})", source, target, data);
-
-        let idx = self.next_edge_index();
-
-        // read current first of the list of edges from each node
-        let source_first = self.nodes[source.0].first_edge[OUTGOING.repr];
-        let target_first = self.nodes[target.0].first_edge[INCOMING.repr];
-
-        // create the new edge, with the previous firsts from each node
-        // as the next pointers
-        self.edges.push(Edge {
-            next_edge: [source_first, target_first],
-            source,
-            target,
-            data,
-        });
-
-        // adjust the firsts for each node target be the next object.
-        self.nodes[source.0].first_edge[OUTGOING.repr] = idx;
-        self.nodes[target.0].first_edge[INCOMING.repr] = idx;
-
-        return idx;
-    }
-
-    pub fn edge(&self, idx: EdgeIndex) -> &Edge<E> {
-        &self.edges[idx.0]
-    }
-
-    // # Iterating over nodes, edges
-
-    pub fn enumerated_nodes(&self) -> impl Iterator<Item = (NodeIndex, &Node<N>)> {
-        self.nodes
-            .iter()
-            .enumerate()
-            .map(|(idx, n)| (NodeIndex(idx), n))
-    }
-
-    pub fn enumerated_edges(&self) -> impl Iterator<Item = (EdgeIndex, &Edge<E>)> {
-        self.edges
-            .iter()
-            .enumerate()
-            .map(|(idx, e)| (EdgeIndex(idx), e))
-    }
-
-    pub fn each_node<'a>(&'a self, mut f: impl FnMut(NodeIndex, &'a Node<N>) -> bool) -> bool {
-        //! Iterates over all edges defined in the graph.
-        self.enumerated_nodes()
-            .all(|(node_idx, node)| f(node_idx, node))
-    }
-
-    pub fn each_edge<'a>(&'a self, mut f: impl FnMut(EdgeIndex, &'a Edge<E>) -> bool) -> bool {
-        //! Iterates over all edges defined in the graph
-        self.enumerated_edges()
-            .all(|(edge_idx, edge)| f(edge_idx, edge))
-    }
-
-    pub fn outgoing_edges(&self, source: NodeIndex) -> AdjacentEdges<N, E> {
-        self.adjacent_edges(source, OUTGOING)
-    }
-
-    pub fn incoming_edges(&self, source: NodeIndex) -> AdjacentEdges<N, E> {
-        self.adjacent_edges(source, INCOMING)
-    }
-
-    pub fn adjacent_edges(&self, source: NodeIndex, direction: Direction) -> AdjacentEdges<N, E> {
-        let first_edge = self.node(source).first_edge[direction.repr];
-        AdjacentEdges {
-            graph: self,
-            direction,
-            next: first_edge,
-        }
-    }
-
-    pub fn successor_nodes<'a>(
-        &'a self,
-        source: NodeIndex,
-    ) -> impl Iterator<Item = NodeIndex> + 'a {
-        self.outgoing_edges(source).targets()
-    }
-
-    pub fn predecessor_nodes<'a>(
-        &'a self,
-        target: NodeIndex,
-    ) -> impl Iterator<Item = NodeIndex> + 'a {
-        self.incoming_edges(target).sources()
-    }
-
-    pub fn depth_traverse<'a>(
-        &'a self,
-        start: NodeIndex,
-        direction: Direction,
-    ) -> DepthFirstTraversal<'a, N, E> {
-        DepthFirstTraversal::with_start_node(self, start, direction)
-    }
-
-    pub fn nodes_in_postorder<'a>(
-        &'a self,
-        direction: Direction,
-        entry_node: NodeIndex,
-    ) -> Vec<NodeIndex> {
-        let mut visited = BitVector::new(self.len_nodes());
-        let mut stack = vec![];
-        let mut result = Vec::with_capacity(self.len_nodes());
-        let mut push_node = |stack: &mut Vec<_>, node: NodeIndex| {
-            if visited.insert(node.0) {
-                stack.push((node, self.adjacent_edges(node, direction)));
-            }
-        };
-
-        for node in Some(entry_node)
-            .into_iter()
-            .chain(self.enumerated_nodes().map(|(node, _)| node))
-        {
-            push_node(&mut stack, node);
-            while let Some((node, mut iter)) = stack.pop() {
-                if let Some((_, child)) = iter.next() {
-                    let target = child.source_or_target(direction);
-                    // the current node needs more processing, so
-                    // add it back to the stack
-                    stack.push((node, iter));
-                    // and then push the new node
-                    push_node(&mut stack, target);
-                } else {
-                    result.push(node);
-                }
-            }
-        }
-
-        assert_eq!(result.len(), self.len_nodes());
-        result
-    }
-}
-
-// # Iterators
-
-pub struct AdjacentEdges<'g, N, E>
+pub trait WithSuccessors: DirectedGraph
 where
-    N: 'g,
-    E: 'g,
+    Self: for<'graph> GraphSuccessors<'graph, Item = <Self as DirectedGraph>::Node>,
 {
-    graph: &'g Graph<N, E>,
-    direction: Direction,
-    next: EdgeIndex,
+    fn successors<'graph>(
+        &'graph self,
+        node: Self::Node,
+    ) -> <Self as GraphSuccessors<'graph>>::Iter;
 }
 
-impl<'g, N: Debug, E: Debug> AdjacentEdges<'g, N, E> {
-    fn targets(self) -> impl Iterator<Item = NodeIndex> + 'g {
-        self.into_iter().map(|(_, edge)| edge.target)
-    }
-
-    fn sources(self) -> impl Iterator<Item = NodeIndex> + 'g {
-        self.into_iter().map(|(_, edge)| edge.source)
-    }
+pub trait GraphSuccessors<'graph> {
+    type Item;
+    type Iter: Iterator<Item = Self::Item>;
 }
 
-impl<'g, N: Debug, E: Debug> Iterator for AdjacentEdges<'g, N, E> {
-    type Item = (EdgeIndex, &'g Edge<E>);
-
-    fn next(&mut self) -> Option<(EdgeIndex, &'g Edge<E>)> {
-        let edge_index = self.next;
-        if edge_index == INVALID_EDGE_INDEX {
-            return None;
-        }
-
-        let edge = self.graph.edge(edge_index);
-        self.next = edge.next_edge[self.direction.repr];
-        Some((edge_index, edge))
-    }
-
-    fn size_hint(&self) -> (usize, Option<usize>) {
-        // At most, all the edges in the graph.
-        (0, Some(self.graph.len_edges()))
-    }
-}
-
-pub struct DepthFirstTraversal<'g, N, E>
+pub trait WithPredecessors: DirectedGraph
 where
-    N: 'g,
-    E: 'g,
+    Self: for<'graph> GraphPredecessors<'graph, Item = <Self as DirectedGraph>::Node>,
 {
-    graph: &'g Graph<N, E>,
-    stack: Vec<NodeIndex>,
-    visited: BitVector,
-    direction: Direction,
+    fn predecessors<'graph>(
+        &'graph self,
+        node: Self::Node,
+    ) -> <Self as GraphPredecessors<'graph>>::Iter;
 }
 
-impl<'g, N: Debug, E: Debug> DepthFirstTraversal<'g, N, E> {
-    pub fn with_start_node(
-        graph: &'g Graph<N, E>,
-        start_node: NodeIndex,
-        direction: Direction,
-    ) -> Self {
-        let mut visited = BitVector::new(graph.len_nodes());
-        visited.insert(start_node.node_id());
-        DepthFirstTraversal {
-            graph,
-            stack: vec![start_node],
-            visited,
-            direction,
-        }
-    }
-
-    fn visit(&mut self, node: NodeIndex) {
-        if self.visited.insert(node.node_id()) {
-            self.stack.push(node);
-        }
-    }
+pub trait GraphPredecessors<'graph> {
+    type Item;
+    type Iter: Iterator<Item = Self::Item>;
 }
 
-impl<'g, N: Debug, E: Debug> Iterator for DepthFirstTraversal<'g, N, E> {
-    type Item = NodeIndex;
-
-    fn next(&mut self) -> Option<NodeIndex> {
-        let next = self.stack.pop();
-        if let Some(idx) = next {
-            for (_, edge) in self.graph.adjacent_edges(idx, self.direction) {
-                let target = edge.source_or_target(self.direction);
-                self.visit(target);
-            }
-        }
-        next
-    }
-
-    fn size_hint(&self) -> (usize, Option<usize>) {
-        // We will visit every node in the graph exactly once.
-        let remaining = self.graph.len_nodes() - self.visited.count();
-        (remaining, Some(remaining))
-    }
+pub trait WithStartNode: DirectedGraph {
+    fn start_node(&self) -> Self::Node;
 }
 
-impl<'g, N: Debug, E: Debug> ExactSizeIterator for DepthFirstTraversal<'g, N, E> {}
-
-impl<E> Edge<E> {
-    pub fn source(&self) -> NodeIndex {
-        self.source
-    }
-
-    pub fn target(&self) -> NodeIndex {
-        self.target
-    }
+pub trait ControlFlowGraph:
+    DirectedGraph + WithStartNode + WithPredecessors + WithStartNode + WithSuccessors + WithNumNodes
+{
+    // convenient trait
+}
 
-    pub fn source_or_target(&self, direction: Direction) -> NodeIndex {
-        if direction == OUTGOING {
-            self.target
-        } else {
-            self.source
-        }
-    }
+impl<T> ControlFlowGraph for T
+where
+    T: DirectedGraph
+        + WithStartNode
+        + WithPredecessors
+        + WithStartNode
+        + WithSuccessors
+        + WithNumNodes,
+{
 }
diff --git a/src/librustc_data_structures/control_flow_graph/reference.rs b/src/librustc_data_structures/graph/reference.rs
index 3b8b01f2ff4..a7b763db8da 100644
--- a/src/librustc_data_structures/control_flow_graph/reference.rs
+++ b/src/librustc_data_structures/graph/reference.rs
@@ -10,34 +10,42 @@
 
 use super::*;
 
-impl<'graph, G: ControlFlowGraph> ControlFlowGraph for &'graph G {
+impl<'graph, G: DirectedGraph> DirectedGraph for &'graph G {
     type Node = G::Node;
+}
 
+impl<'graph, G: WithNumNodes> WithNumNodes for &'graph G {
     fn num_nodes(&self) -> usize {
         (**self).num_nodes()
     }
+}
 
+impl<'graph, G: WithStartNode> WithStartNode for &'graph G {
     fn start_node(&self) -> Self::Node {
         (**self).start_node()
     }
+}
+
+impl<'graph, G: WithSuccessors> WithSuccessors for &'graph G {
+    fn successors<'iter>(&'iter self, node: Self::Node) -> <Self as GraphSuccessors<'iter>>::Iter {
+        (**self).successors(node)
+    }
+}
 
+impl<'graph, G: WithPredecessors> WithPredecessors for &'graph G {
     fn predecessors<'iter>(&'iter self,
                            node: Self::Node)
                            -> <Self as GraphPredecessors<'iter>>::Iter {
         (**self).predecessors(node)
     }
-
-    fn successors<'iter>(&'iter self, node: Self::Node) -> <Self as GraphSuccessors<'iter>>::Iter {
-        (**self).successors(node)
-    }
 }
 
-impl<'iter, 'graph, G: ControlFlowGraph> GraphPredecessors<'iter> for &'graph G {
+impl<'iter, 'graph, G: WithPredecessors> GraphPredecessors<'iter> for &'graph G {
     type Item = G::Node;
     type Iter = <G as GraphPredecessors<'iter>>::Iter;
 }
 
-impl<'iter, 'graph, G: ControlFlowGraph> GraphSuccessors<'iter> for &'graph G {
+impl<'iter, 'graph, G: WithSuccessors> GraphSuccessors<'iter> for &'graph G {
     type Item = G::Node;
     type Iter = <G as GraphSuccessors<'iter>>::Iter;
 }
diff --git a/src/librustc_data_structures/graph/scc/mod.rs b/src/librustc_data_structures/graph/scc/mod.rs
new file mode 100644
index 00000000000..a989a540102
--- /dev/null
+++ b/src/librustc_data_structures/graph/scc/mod.rs
@@ -0,0 +1,361 @@
+// Copyright 2017 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.
+
+//! Routine to compute the strongly connected components (SCCs) of a
+//! graph, as well as the resulting DAG if each SCC is replaced with a
+//! node in the graph. This uses Tarjan's algorithm that completes in
+//! O(n) time.
+
+use fx::FxHashSet;
+use graph::{DirectedGraph, WithNumNodes, WithSuccessors};
+use indexed_vec::{Idx, IndexVec};
+use std::ops::Range;
+
+mod test;
+
+/// Strongly connected components (SCC) of a graph. The type `N` is
+/// the index type for the graph nodes and `S` is the index type for
+/// the SCCs. We can map from each node to the SCC that it
+/// participates in, and we also have the successors of each SCC.
+pub struct Sccs<N: Idx, S: Idx> {
+    /// For each node, what is the SCC index of the SCC to which it
+    /// belongs.
+    scc_indices: IndexVec<N, S>,
+
+    /// Data about each SCC.
+    scc_data: SccData<S>,
+}
+
+struct SccData<S: Idx> {
+    /// For each SCC, the range of `all_successors` where its
+    /// successors can be found.
+    ranges: IndexVec<S, Range<usize>>,
+
+    /// Contains the succcessors for all the Sccs, concatenated. The
+    /// range of indices corresponding to a given SCC is found in its
+    /// SccData.
+    all_successors: Vec<S>,
+}
+
+impl<N: Idx, S: Idx> Sccs<N, S> {
+    pub fn new(graph: &(impl DirectedGraph<Node = N> + WithNumNodes + WithSuccessors)) -> Self {
+        SccsConstruction::construct(graph)
+    }
+
+    /// Returns the number of SCCs in the graph.
+    pub fn num_sccs(&self) -> usize {
+        self.scc_data.len()
+    }
+
+    /// Returns an iterator over the SCCs in the graph.
+    pub fn all_sccs(&self) -> impl Iterator<Item = S> {
+        (0 .. self.scc_data.len()).map(S::new)
+    }
+
+    /// Returns the SCC to which a node `r` belongs.
+    pub fn scc(&self, r: N) -> S {
+        self.scc_indices[r]
+    }
+
+    /// Returns the successors of the given SCC.
+    pub fn successors(&self, scc: S) -> &[S] {
+        self.scc_data.successors(scc)
+    }
+}
+
+impl<S: Idx> SccData<S> {
+    /// Number of SCCs,
+    fn len(&self) -> usize {
+        self.ranges.len()
+    }
+
+    /// Returns the successors of the given SCC.
+    fn successors(&self, scc: S) -> &[S] {
+        // Annoyingly, `range` does not implement `Copy`, so we have
+        // to do `range.start..range.end`:
+        let range = &self.ranges[scc];
+        &self.all_successors[range.start..range.end]
+    }
+
+    /// Creates a new SCC with `successors` as its successors and
+    /// returns the resulting index.
+    fn create_scc(&mut self, successors: impl IntoIterator<Item = S>) -> S {
+        // Store the successors on `scc_successors_vec`, remembering
+        // the range of indices.
+        let all_successors_start = self.all_successors.len();
+        self.all_successors.extend(successors);
+        let all_successors_end = self.all_successors.len();
+
+        debug!(
+            "create_scc({:?}) successors={:?}",
+            self.ranges.len(),
+            &self.all_successors[all_successors_start..all_successors_end],
+        );
+
+        self.ranges.push(all_successors_start..all_successors_end)
+    }
+}
+
+struct SccsConstruction<'c, G: DirectedGraph + WithNumNodes + WithSuccessors + 'c, S: Idx> {
+    graph: &'c G,
+
+    /// The state of each node; used during walk to record the stack
+    /// and after walk to record what cycle each node ended up being
+    /// in.
+    node_states: IndexVec<G::Node, NodeState<G::Node, S>>,
+
+    /// The stack of nodes that we are visiting as part of the DFS.
+    node_stack: Vec<G::Node>,
+
+    /// The stack of successors: as we visit a node, we mark our
+    /// position in this stack, and when we encounter a successor SCC,
+    /// we push it on the stack. When we complete an SCC, we can pop
+    /// everything off the stack that was found along the way.
+    successors_stack: Vec<S>,
+
+    /// A set used to strip duplicates. As we accumulate successors
+    /// into the successors_stack, we sometimes get duplicate entries.
+    /// We use this set to remove those -- we also keep its storage
+    /// around between successors to amortize memory allocation costs.
+    duplicate_set: FxHashSet<S>,
+
+    scc_data: SccData<S>,
+}
+
+#[derive(Copy, Clone, Debug)]
+enum NodeState<N, S> {
+    /// This node has not yet been visited as part of the DFS.
+    ///
+    /// After SCC construction is complete, this state ought to be
+    /// impossible.
+    NotVisited,
+
+    /// This node is currently being walk as part of our DFS. It is on
+    /// the stack at the depth `depth`.
+    ///
+    /// After SCC construction is complete, this state ought to be
+    /// impossible.
+    BeingVisited { depth: usize },
+
+    /// Indicates that this node is a member of the given cycle.
+    InCycle { scc_index: S },
+
+    /// Indicates that this node is a member of whatever cycle
+    /// `parent` is a member of. This state is transient: whenever we
+    /// see it, we try to overwrite it with the current state of
+    /// `parent` (this is the "path compression" step of a union-find
+    /// algorithm).
+    InCycleWith { parent: N },
+}
+
+#[derive(Copy, Clone, Debug)]
+enum WalkReturn<S> {
+    Cycle { min_depth: usize },
+    Complete { scc_index: S },
+}
+
+impl<'c, G, S> SccsConstruction<'c, G, S>
+where
+    G: DirectedGraph + WithNumNodes + WithSuccessors,
+    S: Idx,
+{
+    /// Identifies SCCs in the graph `G` and computes the resulting
+    /// DAG. This uses a variant of [Tarjan's
+    /// algorithm][wikipedia]. The high-level summary of the algorithm
+    /// is that we do a depth-first search. Along the way, we keep a
+    /// stack of each node whose successors are being visited. We
+    /// track the depth of each node on this stack (there is no depth
+    /// if the node is not on the stack). When we find that some node
+    /// N with depth D can reach some other node N' with lower depth
+    /// D' (i.e., D' < D), we know that N, N', and all nodes in
+    /// between them on the stack are part of an SCC.
+    ///
+    /// [wikipedia]: https://bit.ly/2EZIx84
+    fn construct(graph: &'c G) -> Sccs<G::Node, S> {
+        let num_nodes = graph.num_nodes();
+
+        let mut this = Self {
+            graph,
+            node_states: IndexVec::from_elem_n(NodeState::NotVisited, num_nodes),
+            node_stack: Vec::with_capacity(num_nodes),
+            successors_stack: Vec::new(),
+            scc_data: SccData {
+                ranges: IndexVec::new(),
+                all_successors: Vec::new(),
+            },
+            duplicate_set: FxHashSet::default(),
+        };
+
+        let scc_indices = (0..num_nodes)
+            .map(G::Node::new)
+            .map(|node| match this.walk_node(0, node) {
+                WalkReturn::Complete { scc_index } => scc_index,
+                WalkReturn::Cycle { min_depth } => panic!(
+                    "`walk_node(0, {:?})` returned cycle with depth {:?}",
+                    node, min_depth
+                ),
+            })
+            .collect();
+
+        Sccs {
+            scc_indices,
+            scc_data: this.scc_data,
+        }
+    }
+
+    /// Visit a node during the DFS. We first examine its current
+    /// state -- if it is not yet visited (`NotVisited`), we can push
+    /// it onto the stack and start walking its successors.
+    ///
+    /// If it is already on the DFS stack it will be in the state
+    /// `BeingVisited`. In that case, we have found a cycle and we
+    /// return the depth from the stack.
+    ///
+    /// Otherwise, we are looking at a node that has already been
+    /// completely visited. We therefore return `WalkReturn::Complete`
+    /// with its associated SCC index.
+    fn walk_node(&mut self, depth: usize, node: G::Node) -> WalkReturn<S> {
+        debug!("walk_node(depth = {:?}, node = {:?})", depth, node);
+        match self.find_state(node) {
+            NodeState::InCycle { scc_index } => WalkReturn::Complete { scc_index },
+
+            NodeState::BeingVisited { depth: min_depth } => WalkReturn::Cycle { min_depth },
+
+            NodeState::NotVisited => self.walk_unvisited_node(depth, node),
+
+            NodeState::InCycleWith { parent } => panic!(
+                "`find_state` returned `InCycleWith({:?})`, which ought to be impossible",
+                parent
+            ),
+        }
+    }
+
+    /// Fetches the state of the node `r`. If `r` is recorded as being
+    /// in a cycle with some other node `r2`, then fetches the state
+    /// of `r2` (and updates `r` to reflect current result). This is
+    /// basically the "find" part of a standard union-find algorithm
+    /// (with path compression).
+    fn find_state(&mut self, r: G::Node) -> NodeState<G::Node, S> {
+        debug!("find_state(r = {:?} in state {:?})", r, self.node_states[r]);
+        match self.node_states[r] {
+            NodeState::InCycle { scc_index } => NodeState::InCycle { scc_index },
+            NodeState::BeingVisited { depth } => NodeState::BeingVisited { depth },
+            NodeState::NotVisited => NodeState::NotVisited,
+            NodeState::InCycleWith { parent } => {
+                let parent_state = self.find_state(parent);
+                debug!("find_state: parent_state = {:?}", parent_state);
+                match parent_state {
+                    NodeState::InCycle { .. } => {
+                        self.node_states[r] = parent_state;
+                        parent_state
+                    }
+
+                    NodeState::BeingVisited { depth } => {
+                        self.node_states[r] = NodeState::InCycleWith {
+                            parent: self.node_stack[depth],
+                        };
+                        parent_state
+                    }
+
+                    NodeState::NotVisited | NodeState::InCycleWith { .. } => {
+                        panic!("invalid parent state: {:?}", parent_state)
+                    }
+                }
+            }
+        }
+    }
+
+    /// Walks a node that has never been visited before.
+    fn walk_unvisited_node(&mut self, depth: usize, node: G::Node) -> WalkReturn<S> {
+        debug!(
+            "walk_unvisited_node(depth = {:?}, node = {:?})",
+            depth, node
+        );
+
+        debug_assert!(match self.node_states[node] {
+            NodeState::NotVisited => true,
+            _ => false,
+        });
+
+        // Push `node` onto the stack.
+        self.node_states[node] = NodeState::BeingVisited { depth };
+        self.node_stack.push(node);
+
+        // Walk each successor of the node, looking to see if any of
+        // them can reach a node that is presently on the stack. If
+        // so, that means they can also reach us.
+        let mut min_depth = depth;
+        let mut min_cycle_root = node;
+        let successors_len = self.successors_stack.len();
+        for successor_node in self.graph.successors(node) {
+            debug!(
+                "walk_unvisited_node: node = {:?} successor_ode = {:?}",
+                node, successor_node
+            );
+            match self.walk_node(depth + 1, successor_node) {
+                WalkReturn::Cycle {
+                    min_depth: successor_min_depth,
+                } => {
+                    // Track the minimum depth we can reach.
+                    assert!(successor_min_depth <= depth);
+                    if successor_min_depth < min_depth {
+                        debug!(
+                            "walk_unvisited_node: node = {:?} successor_min_depth = {:?}",
+                            node, successor_min_depth
+                        );
+                        min_depth = successor_min_depth;
+                        min_cycle_root = successor_node;
+                    }
+                }
+
+                WalkReturn::Complete {
+                    scc_index: successor_scc_index,
+                } => {
+                    // Push the completed SCC indices onto
+                    // the `successors_stack` for later.
+                    debug!(
+                        "walk_unvisited_node: node = {:?} successor_scc_index = {:?}",
+                        node, successor_scc_index
+                    );
+                    self.successors_stack.push(successor_scc_index);
+                }
+            }
+        }
+
+        // Completed walk, remove `node` from the stack.
+        let r = self.node_stack.pop();
+        debug_assert_eq!(r, Some(node));
+
+        // If `min_depth == depth`, then we are the root of the
+        // cycle: we can't reach anyone further down the stack.
+        if min_depth == depth {
+            // Note that successor stack may have duplicates, so we
+            // want to remove those:
+            let deduplicated_successors = {
+                let duplicate_set = &mut self.duplicate_set;
+                duplicate_set.clear();
+                self.successors_stack
+                    .drain(successors_len..)
+                    .filter(move |&i| duplicate_set.insert(i))
+            };
+            let scc_index = self.scc_data.create_scc(deduplicated_successors);
+            self.node_states[node] = NodeState::InCycle { scc_index };
+            WalkReturn::Complete { scc_index }
+        } else {
+            // We are not the head of the cycle. Return back to our
+            // caller. They will take ownership of the
+            // `self.successors` data that we pushed.
+            self.node_states[node] = NodeState::InCycleWith {
+                parent: min_cycle_root,
+            };
+            WalkReturn::Cycle { min_depth }
+        }
+    }
+}
diff --git a/src/librustc_data_structures/graph/scc/test.rs b/src/librustc_data_structures/graph/scc/test.rs
new file mode 100644
index 00000000000..405e1b3a617
--- /dev/null
+++ b/src/librustc_data_structures/graph/scc/test.rs
@@ -0,0 +1,180 @@
+// Copyright 2016 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.
+
+#![cfg(test)]
+
+use graph::test::TestGraph;
+use super::*;
+
+#[test]
+fn diamond() {
+    let graph = TestGraph::new(0, &[(0, 1), (0, 2), (1, 3), (2, 3)]);
+    let sccs: Sccs<_, usize> = Sccs::new(&graph);
+    assert_eq!(sccs.num_sccs(), 4);
+    assert_eq!(sccs.num_sccs(), 4);
+}
+
+#[test]
+fn test_big_scc() {
+    // The order in which things will be visited is important to this
+    // test.
+    //
+    // We will visit:
+    //
+    // 0 -> 1 -> 2 -> 0
+    //
+    // and at this point detect a cycle. 2 will return back to 1 which
+    // will visit 3. 3 will visit 2 before the cycle is complete, and
+    // hence it too will return a cycle.
+
+    /*
++-> 0
+|   |
+|   v
+|   1 -> 3
+|   |    |
+|   v    |
++-- 2 <--+
+     */
+    let graph = TestGraph::new(0, &[
+        (0, 1),
+        (1, 2),
+        (1, 3),
+        (2, 0),
+        (3, 2),
+    ]);
+    let sccs: Sccs<_, usize> = Sccs::new(&graph);
+    assert_eq!(sccs.num_sccs(), 1);
+}
+
+#[test]
+fn test_three_sccs() {
+    /*
+    0
+    |
+    v
++-> 1    3
+|   |    |
+|   v    |
++-- 2 <--+
+     */
+    let graph = TestGraph::new(0, &[
+        (0, 1),
+        (1, 2),
+        (2, 1),
+        (3, 2),
+    ]);
+    let sccs: Sccs<_, usize> = Sccs::new(&graph);
+    assert_eq!(sccs.num_sccs(), 3);
+    assert_eq!(sccs.scc(0), 1);
+    assert_eq!(sccs.scc(1), 0);
+    assert_eq!(sccs.scc(2), 0);
+    assert_eq!(sccs.scc(3), 2);
+    assert_eq!(sccs.successors(0), &[]);
+    assert_eq!(sccs.successors(1), &[0]);
+    assert_eq!(sccs.successors(2), &[0]);
+}
+
+#[test]
+fn test_find_state_2() {
+    // The order in which things will be visited is important to this
+    // test. It tests part of the `find_state` behavior. Here is the
+    // graph:
+    //
+    //
+    //       /----+
+    //     0 <--+ |
+    //     |    | |
+    //     v    | |
+    // +-> 1 -> 3 4
+    // |   |      |
+    // |   v      |
+    // +-- 2 <----+
+
+    let graph = TestGraph::new(0, &[
+        (0, 1),
+        (0, 4),
+        (1, 2),
+        (1, 3),
+        (2, 1),
+        (3, 0),
+        (4, 2),
+    ]);
+
+    // For this graph, we will start in our DFS by visiting:
+    //
+    // 0 -> 1 -> 2 -> 1
+    //
+    // and at this point detect a cycle. The state of 2 will thus be
+    // `InCycleWith { 1 }`.  We will then visit the 1 -> 3 edge, which
+    // will attempt to visit 0 as well, thus going to the state
+    // `InCycleWith { 0 }`. Finally, node 1 will complete; the lowest
+    // depth of any successor was 3 which had depth 0, and thus it
+    // will be in the state `InCycleWith { 3 }`.
+    //
+    // When we finally traverse the `0 -> 4` edge and then visit node 2,
+    // the states of the nodes are:
+    //
+    // 0 BeingVisited { 0 }
+    // 1 InCycleWith { 3 }
+    // 2 InCycleWith { 1 }
+    // 3 InCycleWith { 0 }
+    //
+    // and hence 4 will traverse the links, finding an ultimate depth of 0.
+    // If will also collapse the states to the following:
+    //
+    // 0 BeingVisited { 0 }
+    // 1 InCycleWith { 3 }
+    // 2 InCycleWith { 1 }
+    // 3 InCycleWith { 0 }
+
+    let sccs: Sccs<_, usize> = Sccs::new(&graph);
+    assert_eq!(sccs.num_sccs(), 1);
+    assert_eq!(sccs.scc(0), 0);
+    assert_eq!(sccs.scc(1), 0);
+    assert_eq!(sccs.scc(2), 0);
+    assert_eq!(sccs.scc(3), 0);
+    assert_eq!(sccs.scc(4), 0);
+    assert_eq!(sccs.successors(0), &[]);
+}
+
+#[test]
+fn test_find_state_3() {
+    /*
+      /----+
+    0 <--+ |
+    |    | |
+    v    | |
++-> 1 -> 3 4 5
+|   |      | |
+|   v      | |
++-- 2 <----+-+
+     */
+    let graph = TestGraph::new(0, &[
+        (0, 1),
+        (0, 4),
+        (1, 2),
+        (1, 3),
+        (2, 1),
+        (3, 0),
+        (4, 2),
+        (5, 2),
+    ]);
+    let sccs: Sccs<_, usize> = Sccs::new(&graph);
+    assert_eq!(sccs.num_sccs(), 2);
+    assert_eq!(sccs.scc(0), 0);
+    assert_eq!(sccs.scc(1), 0);
+    assert_eq!(sccs.scc(2), 0);
+    assert_eq!(sccs.scc(3), 0);
+    assert_eq!(sccs.scc(4), 0);
+    assert_eq!(sccs.scc(5), 1);
+    assert_eq!(sccs.successors(0), &[]);
+    assert_eq!(sccs.successors(1), &[0]);
+}
diff --git a/src/librustc_data_structures/control_flow_graph/test.rs b/src/librustc_data_structures/graph/test.rs
index f04b536bc18..48b654726b8 100644
--- a/src/librustc_data_structures/control_flow_graph/test.rs
+++ b/src/librustc_data_structures/graph/test.rs
@@ -13,7 +13,7 @@ use std::cmp::max;
 use std::slice;
 use std::iter;
 
-use super::{ControlFlowGraph, GraphPredecessors, GraphSuccessors};
+use super::*;
 
 pub struct TestGraph {
     num_nodes: usize,
@@ -44,23 +44,31 @@ impl TestGraph {
     }
 }
 
-impl ControlFlowGraph for TestGraph {
+impl DirectedGraph for TestGraph {
     type Node = usize;
+}
 
+impl WithStartNode for TestGraph {
     fn start_node(&self) -> usize {
         self.start_node
     }
+}
 
+impl WithNumNodes for TestGraph {
     fn num_nodes(&self) -> usize {
         self.num_nodes
     }
+}
 
+impl WithPredecessors for TestGraph {
     fn predecessors<'graph>(&'graph self,
                             node: usize)
                             -> <Self as GraphPredecessors<'graph>>::Iter {
         self.predecessors[&node].iter().cloned()
     }
+}
 
+impl WithSuccessors for TestGraph {
     fn successors<'graph>(&'graph self, node: usize) -> <Self as GraphSuccessors<'graph>>::Iter {
         self.successors[&node].iter().cloned()
     }
diff --git a/src/librustc_data_structures/indexed_vec.rs b/src/librustc_data_structures/indexed_vec.rs
index ad3710e9536..26de2191090 100644
--- a/src/librustc_data_structures/indexed_vec.rs
+++ b/src/librustc_data_structures/indexed_vec.rs
@@ -14,6 +14,7 @@ use std::slice;
 use std::marker::PhantomData;
 use std::ops::{Index, IndexMut, Range, RangeBounds};
 use std::fmt;
+use std::hash::Hash;
 use std::vec;
 use std::u32;
 
@@ -22,7 +23,7 @@ use rustc_serialize as serialize;
 /// Represents some newtyped `usize` wrapper.
 ///
 /// (purpose: avoid mixing indexes for different bitvector domains.)
-pub trait Idx: Copy + 'static + Eq + Debug {
+pub trait Idx: Copy + 'static + Ord + Debug + Hash {
     fn new(idx: usize) -> Self;
     fn index(self) -> usize;
 }
diff --git a/src/librustc_data_structures/lib.rs b/src/librustc_data_structures/lib.rs
index 2cca31f70a0..508dc567fa0 100644
--- a/src/librustc_data_structures/lib.rs
+++ b/src/librustc_data_structures/lib.rs
@@ -61,7 +61,6 @@ pub mod small_vec;
 pub mod base_n;
 pub mod bitslice;
 pub mod bitvec;
-pub mod graph;
 pub mod indexed_set;
 pub mod indexed_vec;
 pub mod obligation_forest;
@@ -73,7 +72,7 @@ pub mod transitive_relation;
 pub use ena::unify;
 pub mod fx;
 pub mod tuple_slice;
-pub mod control_flow_graph;
+pub mod graph;
 pub mod flock;
 pub mod sync;
 pub mod owning_ref;