--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/gcc/shortest-paths.h	Thu Feb 13 11:34:05 2020 +0900
@@ -0,0 +1,145 @@
+/* Template class for Dijkstra's algorithm on directed graphs.
+   Copyright (C) 2019-2020 Free Software Foundation, Inc.
+   Contributed by David Malcolm <dmalcolm@redhat.com>.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#ifndef GCC_SHORTEST_PATHS_H
+#define GCC_SHORTEST_PATHS_H
+
+#include "timevar.h"
+
+/* A record of the shortest path to each node in an graph
+   from the origin node.
+   The constructor runs Dijkstra's algorithm, and the results are
+   stored in this class.  */
+
+template <typename GraphTraits, typename Path_t>
+class shortest_paths
+{
+public:
+  typedef typename GraphTraits::graph_t graph_t;
+  typedef typename GraphTraits::node_t node_t;
+  typedef typename GraphTraits::edge_t edge_t;
+  typedef Path_t path_t;
+
+  shortest_paths (const graph_t &graph, const node_t *origin);
+
+  path_t get_shortest_path (const node_t *to) const;
+
+private:
+  const graph_t &m_graph;
+
+  /* For each node (by index), the minimal distance to that node from the
+     origin.  */
+  auto_vec<int> m_dist;
+
+  /* For each exploded_node (by index), the previous edge in the shortest
+     path from the origin.  */
+  auto_vec<const edge_t *> m_prev;
+};
+
+/* shortest_paths's constructor.
+
+   Use Dijkstra's algorithm relative to ORIGIN to populate m_dist and
+   m_prev with enough information to be able to generate Path_t instances
+   to give the shortest path to any node in GRAPH from ORIGIN.  */
+
+template <typename GraphTraits, typename Path_t>
+inline
+shortest_paths<GraphTraits, Path_t>::shortest_paths (const graph_t &graph,
+						     const node_t *origin)
+: m_graph (graph),
+  m_dist (graph.m_nodes.length ()),
+  m_prev (graph.m_nodes.length ())
+{
+  auto_timevar tv (TV_ANALYZER_SHORTEST_PATHS);
+
+  auto_vec<int> queue (graph.m_nodes.length ());
+
+  for (unsigned i = 0; i < graph.m_nodes.length (); i++)
+    {
+      m_dist.quick_push (INT_MAX);
+      m_prev.quick_push (NULL);
+      queue.quick_push (i);
+    }
+  m_dist[origin->m_index] = 0;
+
+  while (queue.length () > 0)
+    {
+      /* Get minimal distance in queue.
+	 FIXME: this is O(N^2); replace with a priority queue.  */
+      int idx_with_min_dist = -1;
+      int idx_in_queue_with_min_dist = -1;
+      int min_dist = INT_MAX;
+      for (unsigned i = 0; i < queue.length (); i++)
+	{
+	  int idx = queue[i];
+	  if (m_dist[queue[i]] < min_dist)
+	    {
+	      min_dist = m_dist[idx];
+	      idx_with_min_dist = idx;
+	      idx_in_queue_with_min_dist = i;
+	    }
+	}
+      gcc_assert (idx_with_min_dist != -1);
+      gcc_assert (idx_in_queue_with_min_dist != -1);
+
+      // FIXME: this is confusing: there are two indices here
+
+      queue.unordered_remove (idx_in_queue_with_min_dist);
+
+      node_t *n
+	= static_cast <node_t *> (m_graph.m_nodes[idx_with_min_dist]);
+
+      int i;
+      edge_t *succ;
+      FOR_EACH_VEC_ELT (n->m_succs, i, succ)
+	{
+	  // TODO: only for dest still in queue
+	  node_t *dest = succ->m_dest;
+	  int alt = m_dist[n->m_index] + 1;
+	  if (alt < m_dist[dest->m_index])
+	    {
+	      m_dist[dest->m_index] = alt;
+	      m_prev[dest->m_index] = succ;
+	    }
+	}
+   }
+}
+
+/* Generate an Path_t instance giving the shortest path to the node
+   TO from the origin node.  */
+
+template <typename GraphTraits, typename Path_t>
+inline Path_t
+shortest_paths<GraphTraits, Path_t>::get_shortest_path (const node_t *to) const
+{
+  Path_t result;
+
+  while (m_prev[to->m_index])
+    {
+      result.m_edges.safe_push (m_prev[to->m_index]);
+      to = m_prev[to->m_index]->m_src;
+    }
+
+  result.m_edges.reverse ();
+
+  return result;
+}
+
+#endif /* GCC_SHORTEST_PATHS_H */