diff options
Diffstat (limited to 'gcc')
| -rw-r--r-- | gcc/analyzer/diagnostic-manager.cc | 2 | ||||
| -rw-r--r-- | gcc/digraph.cc | 39 | ||||
| -rw-r--r-- | gcc/shortest-paths.h | 121 |
3 files changed, 125 insertions, 37 deletions
diff --git a/gcc/analyzer/diagnostic-manager.cc b/gcc/analyzer/diagnostic-manager.cc index 7f20841..e84953e 100644 --- a/gcc/analyzer/diagnostic-manager.cc +++ b/gcc/analyzer/diagnostic-manager.cc @@ -73,7 +73,7 @@ class epath_finder public: epath_finder (const exploded_graph &eg) : m_eg (eg), - m_sep (eg, eg.get_origin ()) + m_sep (eg, eg.get_origin (), SPS_FROM_GIVEN_ORIGIN) { } diff --git a/gcc/digraph.cc b/gcc/digraph.cc index 3441a85..e6966b0 100644 --- a/gcc/digraph.cc +++ b/gcc/digraph.cc @@ -147,7 +147,8 @@ test_shortest_paths () /* Use "A" as the origin; all nodes should be reachable. */ { - shortest_paths<test_graph_traits, test_path> sp (g, a); + shortest_paths<test_graph_traits, test_path> sp (g, a, + SPS_FROM_GIVEN_ORIGIN); test_path path_to_a = sp.get_shortest_path (a); ASSERT_EQ (path_to_a.m_edges.length (), 0); /* Trivial path. */ @@ -181,7 +182,8 @@ test_shortest_paths () /* Use "B" as the origin, so only E and F are reachable. */ { - shortest_paths<test_graph_traits, test_path> sp (g, b); + shortest_paths<test_graph_traits, test_path> sp (g, b, + SPS_FROM_GIVEN_ORIGIN); test_path path_to_a = sp.get_shortest_path (a); ASSERT_EQ (path_to_a.m_edges.length (), 0); /* No path. */ @@ -207,7 +209,8 @@ test_shortest_paths () /* Use "C" as the origin, so only D and F are reachable. */ { - shortest_paths<test_graph_traits, test_path> sp (g, c); + shortest_paths<test_graph_traits, test_path> sp (g, c, + SPS_FROM_GIVEN_ORIGIN); test_path path_to_a = sp.get_shortest_path (a); ASSERT_EQ (path_to_a.m_edges.length (), 0); /* No path. */ @@ -229,6 +232,36 @@ test_shortest_paths () ASSERT_EQ (path_to_f.m_edges.length (), 1); ASSERT_EQ (path_to_f.m_edges[0], cf); } + + /* Test of SPS_TO_GIVEN_TARGET. Use "F" as the target. */ + { + shortest_paths<test_graph_traits, test_path> sp (g, f, + SPS_TO_GIVEN_TARGET); + + test_path path_to_a = sp.get_shortest_path (a); + ASSERT_EQ (path_to_a.m_edges.length (), 2); + ASSERT_EQ (path_to_a.m_edges[0], ac); + ASSERT_EQ (path_to_a.m_edges[1], cf); + + test_path path_to_b = sp.get_shortest_path (b); + ASSERT_EQ (path_to_b.m_edges.length (), 2); + ASSERT_EQ (path_to_b.m_edges[0], be); + ASSERT_EQ (path_to_b.m_edges[1], ef); + + test_path path_to_c = sp.get_shortest_path (c); + ASSERT_EQ (path_to_c.m_edges.length (), 1); + ASSERT_EQ (path_to_c.m_edges[0], cf); + + test_path path_to_d = sp.get_shortest_path (d); + ASSERT_EQ (path_to_d.m_edges.length (), 0); /* No path. */ + + test_path path_to_e = sp.get_shortest_path (e); + ASSERT_EQ (path_to_e.m_edges.length (), 1); + ASSERT_EQ (path_to_e.m_edges[0], ef); + + test_path path_to_f = sp.get_shortest_path (f); + ASSERT_EQ (path_to_f.m_edges.length (), 0); + } } /* Run all of the selftests within this file. */ diff --git a/gcc/shortest-paths.h b/gcc/shortest-paths.h index 5648a95..40d2c2a 100644 --- a/gcc/shortest-paths.h +++ b/gcc/shortest-paths.h @@ -23,8 +23,24 @@ along with GCC; see the file COPYING3. If not see #include "timevar.h" -/* A record of the shortest path to each node in an graph - from the origin node. +enum shortest_path_sense +{ + /* Find the shortest path from the given origin node to each + node in the graph. */ + SPS_FROM_GIVEN_ORIGIN, + + /* Find the shortest path from each node in the graph to the + given target node. */ + SPS_TO_GIVEN_TARGET +}; + +/* A record of the shortest path for each node relative to a special + "given node", either: + SPS_FROM_GIVEN_ORIGIN: + from the given origin node to each node in a graph, or + SPS_TO_GIVEN_TARGET: + from each node in a graph to the given target node. + The constructor runs Dijkstra's algorithm, and the results are stored in this class. */ @@ -37,35 +53,46 @@ public: typedef typename GraphTraits::edge_t edge_t; typedef Path_t path_t; - shortest_paths (const graph_t &graph, const node_t *origin); + shortest_paths (const graph_t &graph, const node_t *given_node, + enum shortest_path_sense sense); - path_t get_shortest_path (const node_t *to) const; + path_t get_shortest_path (const node_t *other_node) const; private: const graph_t &m_graph; - /* For each node (by index), the minimal distance to that node from the - origin. */ + enum shortest_path_sense m_sense; + + /* For each node (by index), the minimal distance between that node + and the given node (with direction depending on m_sense). */ 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; + /* For each node (by index): + SPS_FROM_GIVEN_ORIGIN: + the previous edge in the shortest path from the origin, + SPS_TO_GIVEN_TARGET: + the next edge in the shortest path to the target. */ + auto_vec<const edge_t *> m_best_edge; }; /* 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. */ + Use Dijkstra's algorithm relative to GIVEN_NODE to populate m_dist and + m_best_edge with enough information to be able to generate Path_t instances + to give the shortest path... + SPS_FROM_GIVEN_ORIGIN: to each node in a graph from the origin node, or + SPS_TO_GIVEN_TARGET: from each node in a graph to the target node. */ template <typename GraphTraits, typename Path_t> inline -shortest_paths<GraphTraits, Path_t>::shortest_paths (const graph_t &graph, - const node_t *origin) +shortest_paths<GraphTraits, Path_t>:: +shortest_paths (const graph_t &graph, + const node_t *given_node, + enum shortest_path_sense sense) : m_graph (graph), + m_sense (sense), m_dist (graph.m_nodes.length ()), - m_prev (graph.m_nodes.length ()) + m_best_edge (graph.m_nodes.length ()) { auto_timevar tv (TV_ANALYZER_SHORTEST_PATHS); @@ -74,10 +101,10 @@ shortest_paths<GraphTraits, Path_t>::shortest_paths (const graph_t &graph, for (unsigned i = 0; i < graph.m_nodes.length (); i++) { m_dist.quick_push (INT_MAX); - m_prev.quick_push (NULL); + m_best_edge.quick_push (NULL); queue.quick_push (i); } - m_dist[origin->m_index] = 0; + m_dist[given_node->m_index] = 0; while (queue.length () > 0) { @@ -107,39 +134,67 @@ shortest_paths<GraphTraits, Path_t>::shortest_paths (const graph_t &graph, 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) + if (m_sense == SPS_FROM_GIVEN_ORIGIN) { - // 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]) + int i; + edge_t *succ; + FOR_EACH_VEC_ELT (n->m_succs, i, succ) { - m_dist[dest->m_index] = alt; - m_prev[dest->m_index] = 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_best_edge[dest->m_index] = succ; + } + } + } + else + { + int i; + edge_t *pred; + FOR_EACH_VEC_ELT (n->m_preds, i, pred) + { + // TODO: only for dest still in queue + node_t *src = pred->m_src; + int alt = m_dist[n->m_index] + 1; + if (alt < m_dist[src->m_index]) + { + m_dist[src->m_index] = alt; + m_best_edge[src->m_index] = pred; + } } } } } -/* Generate an Path_t instance giving the shortest path to the node - TO from the origin node. +/* Generate an Path_t instance giving the shortest path between OTHER_NODE + and the given node. + + SPS_FROM_GIVEN_ORIGIN: shortest path from given origin node to OTHER_NODE + SPS_TO_GIVEN_TARGET: shortest path from OTHER_NODE to given target node. + If no such path exists, return an empty path. */ template <typename GraphTraits, typename Path_t> inline Path_t -shortest_paths<GraphTraits, Path_t>::get_shortest_path (const node_t *to) const +shortest_paths<GraphTraits, Path_t>:: +get_shortest_path (const node_t *other_node) const { Path_t result; - while (m_prev[to->m_index]) + while (m_best_edge[other_node->m_index]) { - result.m_edges.safe_push (m_prev[to->m_index]); - to = m_prev[to->m_index]->m_src; + result.m_edges.safe_push (m_best_edge[other_node->m_index]); + if (m_sense == SPS_FROM_GIVEN_ORIGIN) + other_node = m_best_edge[other_node->m_index]->m_src; + else + other_node = m_best_edge[other_node->m_index]->m_dest; } - result.m_edges.reverse (); + if (m_sense == SPS_FROM_GIVEN_ORIGIN) + result.m_edges.reverse (); return result; } |