rename `control_flow_graph` to `graph`

9 files changed, 0 insertions, 1103 deletions

diff --git a/src/librustc_data_structures/control_flow_graph/dominators/mod.rs b/src/librustc_data_structures/control_flow_graph/dominators/mod.rs
deleted file mode 100644
index d134fad2855..00000000000
--- a/src/librustc_data_structures/control_flow_graph/dominators/mod.rs
+++ /dev/null
@@ -1,214 +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.
-
-//! Algorithm citation:
-//! A Simple, Fast Dominance Algorithm.
-//! Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy
-//! Rice Computer Science TS-06-33870
-//! <https://www.cs.rice.edu/~keith/EMBED/dom.pdf>
-
-use super::super::indexed_vec::{Idx, IndexVec};
-use super::iterate::reverse_post_order;
-use super::ControlFlowGraph;
-
-use std::fmt;
-
-#[cfg(test)]
-mod test;
-
-pub fn dominators<G: ControlFlowGraph>(graph: &G) -> Dominators<G::Node> {
-    let start_node = graph.start_node();
-    let rpo = reverse_post_order(graph, start_node);
-    dominators_given_rpo(graph, &rpo)
-}
-
-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());
-    for (index, node) in rpo.iter().rev().cloned().enumerate() {
-        post_order_rank[node] = index;
-    }
-
-    let mut immediate_dominators: IndexVec<G::Node, Option<G::Node>> =
-        IndexVec::from_elem_n(Option::default(), graph.num_nodes());
-    immediate_dominators[start_node] = Some(start_node);
-
-    let mut changed = true;
-    while changed {
-        changed = false;
-
-        for &node in &rpo[1..] {
-            let mut new_idom = None;
-            for pred in graph.predecessors(node) {
-                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),
-                    );
-                }
-            }
-
-            if new_idom != immediate_dominators[node] {
-                immediate_dominators[node] = new_idom;
-                changed = true;
-            }
-        }
-    }
-
-    Dominators {
-        post_order_rank,
-        immediate_dominators,
-    }
-}
-
-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),
-        (Some(n1), Some(n2)) => Some(intersect(post_order_rank, immediate_dominators, n1, n2)),
-    }
-}
-
-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();
-        }
-
-        while post_order_rank[node2] < post_order_rank[node1] {
-            node2 = immediate_dominators[node2].unwrap();
-        }
-    }
-    return node1;
-}
-
-#[derive(Clone, Debug)]
-pub struct Dominators<N: Idx> {
-    post_order_rank: IndexVec<N, usize>,
-    immediate_dominators: IndexVec<N, Option<N>>,
-}
-
-impl<Node: Idx> Dominators<Node> {
-    pub fn is_reachable(&self, node: Node) -> bool {
-        self.immediate_dominators[node].is_some()
-    }
-
-    pub fn immediate_dominator(&self, node: Node) -> Node {
-        assert!(self.is_reachable(node), "node {:?} is not reachable", node);
-        self.immediate_dominators[node].unwrap()
-    }
-
-    pub fn dominators(&self, node: Node) -> Iter<Node> {
-        assert!(self.is_reachable(node), "node {:?} is not reachable", node);
-        Iter {
-            dominators: self,
-            node: Some(node),
-        }
-    }
-
-    pub fn is_dominated_by(&self, node: Node, dom: Node) -> bool {
-        // FIXME -- could be optimized by using post-order-rank
-        self.dominators(node).any(|n| n == dom)
-    }
-
-    #[cfg(test)]
-    fn all_immediate_dominators(&self) -> &IndexVec<Node, Option<Node>> {
-        &self.immediate_dominators
-    }
-}
-
-pub struct Iter<'dom, Node: Idx + 'dom> {
-    dominators: &'dom Dominators<Node>,
-    node: Option<Node>,
-}
-
-impl<'dom, Node: Idx> Iterator for Iter<'dom, Node> {
-    type Item = Node;
-
-    fn next(&mut self) -> Option<Self::Item> {
-        if let Some(node) = self.node {
-            let dom = self.dominators.immediate_dominator(node);
-            if dom == node {
-                self.node = None; // reached the root
-            } else {
-                self.node = Some(dom);
-            }
-            return Some(node);
-        } else {
-            return None;
-        }
-    }
-}
-
-pub struct DominatorTree<N: Idx> {
-    root: N,
-    children: IndexVec<N, Vec<N>>,
-}
-
-impl<Node: Idx> DominatorTree<Node> {
-    pub fn children(&self, node: Node) -> &[Node] {
-        &self.children[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,
-        )
-    }
-}
-
-struct DominatorTreeNode<'tree, Node: Idx> {
-    tree: &'tree DominatorTree<Node>,
-    node: Node,
-}
-
-impl<'tree, Node: Idx> fmt::Debug for DominatorTreeNode<'tree, Node> {
-    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
-        let subtrees: Vec<_> = self.tree
-            .children(self.node)
-            .iter()
-            .map(|&child| DominatorTreeNode {
-                tree: self.tree,
-                node: child,
-            })
-            .collect();
-        fmt.debug_tuple("")
-            .field(&self.node)
-            .field(&subtrees)
-            .finish()
-    }
-}
diff --git a/src/librustc_data_structures/control_flow_graph/dominators/test.rs b/src/librustc_data_structures/control_flow_graph/dominators/test.rs
deleted file mode 100644
index 0af878cac2d..00000000000
--- a/src/librustc_data_structures/control_flow_graph/dominators/test.rs
+++ /dev/null
@@ -1,43 +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::super::test::TestGraph;
-
-use super::*;
-
-#[test]
-fn diamond() {
-    let graph = TestGraph::new(0, &[(0, 1), (0, 2), (1, 3), (2, 3)]);
-
-    let dominators = dominators(&graph);
-    let immediate_dominators = dominators.all_immediate_dominators();
-    assert_eq!(immediate_dominators[0], Some(0));
-    assert_eq!(immediate_dominators[1], Some(0));
-    assert_eq!(immediate_dominators[2], Some(0));
-    assert_eq!(immediate_dominators[3], Some(0));
-}
-
-#[test]
-fn paper() {
-    // example from the paper:
-    let graph = TestGraph::new(6,
-                               &[(6, 5), (6, 4), (5, 1), (4, 2), (4, 3), (1, 2), (2, 3), (3, 2),
-                                 (2, 1)]);
-
-    let dominators = dominators(&graph);
-    let immediate_dominators = dominators.all_immediate_dominators();
-    assert_eq!(immediate_dominators[0], None); // <-- note that 0 is not in graph
-    assert_eq!(immediate_dominators[1], Some(6));
-    assert_eq!(immediate_dominators[2], Some(6));
-    assert_eq!(immediate_dominators[3], Some(6));
-    assert_eq!(immediate_dominators[4], Some(6));
-    assert_eq!(immediate_dominators[5], Some(6));
-    assert_eq!(immediate_dominators[6], Some(6));
-}
diff --git a/src/librustc_data_structures/control_flow_graph/implementation/mod.rs b/src/librustc_data_structures/control_flow_graph/implementation/mod.rs
deleted file mode 100644
index e2b393071ff..00000000000
--- a/src/librustc_data_structures/control_flow_graph/implementation/mod.rs
+++ /dev/null
@@ -1,417 +0,0 @@
-// 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/control_flow_graph/implementation/tests.rs b/src/librustc_data_structures/control_flow_graph/implementation/tests.rs
deleted file mode 100644
index 007704357af..00000000000
--- a/src/librustc_data_structures/control_flow_graph/implementation/tests.rs
+++ /dev/null
@@ -1,139 +0,0 @@
-// Copyright 2015 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 graph::*;
-use std::fmt::Debug;
-
-type TestGraph = Graph<&'static str, &'static str>;
-
-fn create_graph() -> TestGraph {
-    let mut graph = Graph::new();
-
-    // Create a simple graph
-    //
-    //          F
-    //          |
-    //          V
-    //    A --> B --> C
-    //          |     ^
-    //          v     |
-    //          D --> E
-
-    let a = graph.add_node("A");
-    let b = graph.add_node("B");
-    let c = graph.add_node("C");
-    let d = graph.add_node("D");
-    let e = graph.add_node("E");
-    let f = graph.add_node("F");
-
-    graph.add_edge(a, b, "AB");
-    graph.add_edge(b, c, "BC");
-    graph.add_edge(b, d, "BD");
-    graph.add_edge(d, e, "DE");
-    graph.add_edge(e, c, "EC");
-    graph.add_edge(f, b, "FB");
-
-    return graph;
-}
-
-#[test]
-fn each_node() {
-    let graph = create_graph();
-    let expected = ["A", "B", "C", "D", "E", "F"];
-    graph.each_node(|idx, node| {
-        assert_eq!(&expected[idx.0], graph.node_data(idx));
-        assert_eq!(expected[idx.0], node.data);
-        true
-    });
-}
-
-#[test]
-fn each_edge() {
-    let graph = create_graph();
-    let expected = ["AB", "BC", "BD", "DE", "EC", "FB"];
-    graph.each_edge(|idx, edge| {
-        assert_eq!(expected[idx.0], edge.data);
-        true
-    });
-}
-
-fn test_adjacent_edges<N: PartialEq + Debug, E: PartialEq + Debug>(graph: &Graph<N, E>,
-                                                                   start_index: NodeIndex,
-                                                                   start_data: N,
-                                                                   expected_incoming: &[(E, N)],
-                                                                   expected_outgoing: &[(E, N)]) {
-    assert!(graph.node_data(start_index) == &start_data);
-
-    let mut counter = 0;
-    for (edge_index, edge) in graph.incoming_edges(start_index) {
-        assert!(counter < expected_incoming.len());
-        debug!("counter={:?} expected={:?} edge_index={:?} edge={:?}",
-               counter,
-               expected_incoming[counter],
-               edge_index,
-               edge);
-        match expected_incoming[counter] {
-            (ref e, ref n) => {
-                assert!(e == &edge.data);
-                assert!(n == graph.node_data(edge.source()));
-                assert!(start_index == edge.target);
-            }
-        }
-        counter += 1;
-    }
-    assert_eq!(counter, expected_incoming.len());
-
-    let mut counter = 0;
-    for (edge_index, edge) in graph.outgoing_edges(start_index) {
-        assert!(counter < expected_outgoing.len());
-        debug!("counter={:?} expected={:?} edge_index={:?} edge={:?}",
-               counter,
-               expected_outgoing[counter],
-               edge_index,
-               edge);
-        match expected_outgoing[counter] {
-            (ref e, ref n) => {
-                assert!(e == &edge.data);
-                assert!(start_index == edge.source);
-                assert!(n == graph.node_data(edge.target));
-            }
-        }
-        counter += 1;
-    }
-    assert_eq!(counter, expected_outgoing.len());
-}
-
-#[test]
-fn each_adjacent_from_a() {
-    let graph = create_graph();
-    test_adjacent_edges(&graph, NodeIndex(0), "A", &[], &[("AB", "B")]);
-}
-
-#[test]
-fn each_adjacent_from_b() {
-    let graph = create_graph();
-    test_adjacent_edges(&graph,
-                        NodeIndex(1),
-                        "B",
-                        &[("FB", "F"), ("AB", "A")],
-                        &[("BD", "D"), ("BC", "C")]);
-}
-
-#[test]
-fn each_adjacent_from_c() {
-    let graph = create_graph();
-    test_adjacent_edges(&graph, NodeIndex(2), "C", &[("EC", "E"), ("BC", "B")], &[]);
-}
-
-#[test]
-fn each_adjacent_from_d() {
-    let graph = create_graph();
-    test_adjacent_edges(&graph, NodeIndex(3), "D", &[("BD", "B")], &[("DE", "E")]);
-}
diff --git a/src/librustc_data_structures/control_flow_graph/iterate/mod.rs b/src/librustc_data_structures/control_flow_graph/iterate/mod.rs
deleted file mode 100644
index 3afdc88d602..00000000000
--- a/src/librustc_data_structures/control_flow_graph/iterate/mod.rs
+++ /dev/null
@@ -1,63 +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::super::indexed_vec::IndexVec;
-use super::{DirectedGraph, WithSuccessors, WithNumNodes};
-
-#[cfg(test)]
-mod test;
-
-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: 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 {
-        visited[end_node] = true;
-    }
-    post_order_walk(graph, start_node, &mut result, &mut visited);
-    result
-}
-
-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;
-    }
-    visited[node] = true;
-
-    for successor in graph.successors(node) {
-        post_order_walk(graph, successor, result, visited);
-    }
-
-    result.push(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/control_flow_graph/iterate/test.rs
deleted file mode 100644
index 100881ddfdd..00000000000
--- a/src/librustc_data_structures/control_flow_graph/iterate/test.rs
+++ /dev/null
@@ -1,21 +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::super::test::TestGraph;
-
-use super::*;
-
-#[test]
-fn diamond_post_order() {
-    let graph = TestGraph::new(0, &[(0, 1), (0, 2), (1, 3), (2, 3)]);
-
-    let result = post_order_from(&graph, 0);
-    assert_eq!(result, vec![3, 1, 2, 0]);
-}
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 bd933e57b39..00000000000
--- a/src/librustc_data_structures/control_flow_graph/mod.rs
+++ /dev/null
@@ -1,78 +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 implementation;
-pub mod iterate;
-mod reference;
-
-#[cfg(test)]
-mod test;
-
-pub trait DirectedGraph {
-    type Node: Idx;
-}
-
-pub trait WithNumNodes: DirectedGraph {
-    fn num_nodes(&self) -> usize;
-}
-
-pub trait WithSuccessors: DirectedGraph
-where
-    Self: for<'graph> GraphSuccessors<'graph, Item = <Self as DirectedGraph>::Node>,
-{
-    fn successors<'graph>(
-        &'graph self,
-        node: Self::Node,
-    ) -> <Self as GraphSuccessors<'graph>>::Iter;
-}
-
-pub trait GraphSuccessors<'graph> {
-    type Item;
-    type Iter: Iterator<Item = Self::Item>;
-}
-
-pub trait WithPredecessors: DirectedGraph
-where
-    Self: for<'graph> GraphPredecessors<'graph, Item = <Self as DirectedGraph>::Node>,
-{
-    fn predecessors<'graph>(
-        &'graph self,
-        node: Self::Node,
-    ) -> <Self as GraphPredecessors<'graph>>::Iter;
-}
-
-pub trait GraphPredecessors<'graph> {
-    type Item;
-    type Iter: Iterator<Item = Self::Item>;
-}
-
-pub trait WithStartNode: DirectedGraph {
-    fn start_node(&self) -> Self::Node;
-}
-
-pub trait ControlFlowGraph:
-    DirectedGraph + WithStartNode + WithPredecessors + WithStartNode + WithSuccessors + WithNumNodes
-{
-    // convenient trait
-}
-
-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/control_flow_graph/reference.rs
deleted file mode 100644
index a7b763db8da..00000000000
--- a/src/librustc_data_structures/control_flow_graph/reference.rs
+++ /dev/null
@@ -1,51 +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::*;
-
-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)
-    }
-}
-
-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: WithSuccessors> GraphSuccessors<'iter> for &'graph G {
-    type Item = G::Node;
-    type Iter = <G as GraphSuccessors<'iter>>::Iter;
-}
diff --git a/src/librustc_data_structures/control_flow_graph/test.rs b/src/librustc_data_structures/control_flow_graph/test.rs
deleted file mode 100644
index f04b536bc18..00000000000
--- a/src/librustc_data_structures/control_flow_graph/test.rs
+++ /dev/null
@@ -1,77 +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 std::collections::HashMap;
-use std::cmp::max;
-use std::slice;
-use std::iter;
-
-use super::{ControlFlowGraph, GraphPredecessors, GraphSuccessors};
-
-pub struct TestGraph {
-    num_nodes: usize,
-    start_node: usize,
-    successors: HashMap<usize, Vec<usize>>,
-    predecessors: HashMap<usize, Vec<usize>>,
-}
-
-impl TestGraph {
-    pub fn new(start_node: usize, edges: &[(usize, usize)]) -> Self {
-        let mut graph = TestGraph {
-            num_nodes: start_node + 1,
-            start_node,
-            successors: HashMap::new(),
-            predecessors: HashMap::new(),
-        };
-        for &(source, target) in edges {
-            graph.num_nodes = max(graph.num_nodes, source + 1);
-            graph.num_nodes = max(graph.num_nodes, target + 1);
-            graph.successors.entry(source).or_insert(vec![]).push(target);
-            graph.predecessors.entry(target).or_insert(vec![]).push(source);
-        }
-        for node in 0..graph.num_nodes {
-            graph.successors.entry(node).or_insert(vec![]);
-            graph.predecessors.entry(node).or_insert(vec![]);
-        }
-        graph
-    }
-}
-
-impl ControlFlowGraph for TestGraph {
-    type Node = usize;
-
-    fn start_node(&self) -> usize {
-        self.start_node
-    }
-
-    fn num_nodes(&self) -> usize {
-        self.num_nodes
-    }
-
-    fn predecessors<'graph>(&'graph self,
-                            node: usize)
-                            -> <Self as GraphPredecessors<'graph>>::Iter {
-        self.predecessors[&node].iter().cloned()
-    }
-
-    fn successors<'graph>(&'graph self, node: usize) -> <Self as GraphSuccessors<'graph>>::Iter {
-        self.successors[&node].iter().cloned()
-    }
-}
-
-impl<'graph> GraphPredecessors<'graph> for TestGraph {
-    type Item = usize;
-    type Iter = iter::Cloned<slice::Iter<'graph, usize>>;
-}
-
-impl<'graph> GraphSuccessors<'graph> for TestGraph {
-    type Item = usize;
-    type Iter = iter::Cloned<slice::Iter<'graph, usize>>;
-}