rename `control_flow_graph` to `graph`

9 files changed, 1103 insertions, 0 deletions

diff --git a/src/librustc_data_structures/graph/dominators/mod.rs b/src/librustc_data_structures/graph/dominators/mod.rs
new file mode 100644
index 00000000000..d134fad2855
--- /dev/null
+++ b/src/librustc_data_structures/graph/dominators/mod.rs
@@ -0,0 +1,214 @@
+// 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/graph/dominators/test.rs b/src/librustc_data_structures/graph/dominators/test.rs
new file mode 100644
index 00000000000..0af878cac2d
--- /dev/null
+++ b/src/librustc_data_structures/graph/dominators/test.rs
@@ -0,0 +1,43 @@
+// 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/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/implementation/tests.rs b/src/librustc_data_structures/graph/implementation/tests.rs
new file mode 100644
index 00000000000..007704357af
--- /dev/null
+++ b/src/librustc_data_structures/graph/implementation/tests.rs
@@ -0,0 +1,139 @@
+// 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/graph/iterate/mod.rs b/src/librustc_data_structures/graph/iterate/mod.rs
new file mode 100644
index 00000000000..3afdc88d602
--- /dev/null
+++ b/src/librustc_data_structures/graph/iterate/mod.rs
@@ -0,0 +1,63 @@
+// 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/graph/iterate/test.rs b/src/librustc_data_structures/graph/iterate/test.rs
new file mode 100644
index 00000000000..100881ddfdd
--- /dev/null
+++ b/src/librustc_data_structures/graph/iterate/test.rs
@@ -0,0 +1,21 @@
+// 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/graph/mod.rs b/src/librustc_data_structures/graph/mod.rs
new file mode 100644
index 00000000000..bd933e57b39
--- /dev/null
+++ b/src/librustc_data_structures/graph/mod.rs
@@ -0,0 +1,78 @@
+// 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/graph/reference.rs b/src/librustc_data_structures/graph/reference.rs
new file mode 100644
index 00000000000..a7b763db8da
--- /dev/null
+++ b/src/librustc_data_structures/graph/reference.rs
@@ -0,0 +1,51 @@
+// 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/graph/test.rs b/src/librustc_data_structures/graph/test.rs
new file mode 100644
index 00000000000..f04b536bc18
--- /dev/null
+++ b/src/librustc_data_structures/graph/test.rs
@@ -0,0 +1,77 @@
+// 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>>;
+}