@@ -1585,65 +1585,6 @@ unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
bitmap_clear_bit (graph->succs[to], to);
}
-/* Information needed to compute the topological ordering of a graph. */
-
-struct topo_info
-{
- /* sbitmap of visited nodes. */
- sbitmap visited;
- /* Array that stores the topological order of the graph, *in
- reverse*. */
- vec<unsigned> topo_order;
-};
-
-
-/* Initialize and return a topological info structure. */
-
-static struct topo_info *
-init_topo_info (void)
-{
- size_t size = graph->size;
- struct topo_info *ti = XNEW (struct topo_info);
- ti->visited = sbitmap_alloc (size);
- bitmap_clear (ti->visited);
- ti->topo_order.create (1);
- return ti;
-}
-
-
-/* Free the topological sort info pointed to by TI. */
-
-static void
-free_topo_info (struct topo_info *ti)
-{
- sbitmap_free (ti->visited);
- ti->topo_order.release ();
- free (ti);
-}
-
-/* Visit the graph in topological order, and store the order in the
- topo_info structure. */
-
-static void
-topo_visit (constraint_graph_t graph, struct topo_info *ti,
- unsigned int n)
-{
- bitmap_iterator bi;
- unsigned int j;
-
- bitmap_set_bit (ti->visited, n);
-
- if (graph->succs[n])
- EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi)
- {
- unsigned k = find (j);
- if (!bitmap_bit_p (ti->visited, k))
- topo_visit (graph, ti, k);
- }
-
- ti->topo_order.safe_push (n);
-}
-
/* Add a copy edge FROM -> TO, optimizing special cases. Returns TRUE
if the solution of TO changed. */
@@ -1925,19 +1866,56 @@ find_indirect_cycles (constraint_graph_t graph)
scc_visit (graph, &si, i);
}
-/* Compute a topological ordering for GRAPH, and store the result in the
- topo_info structure TI. */
+/* Visit the graph in topological order starting at node N, and store the
+ order in TOPO_ORDER using VISITED to indicate visited nodes. */
static void
-compute_topo_order (constraint_graph_t graph,
- struct topo_info *ti)
+topo_visit (constraint_graph_t graph, vec<unsigned> &topo_order,
+ sbitmap visited, unsigned int n)
+{
+ bitmap_iterator bi;
+ unsigned int j;
+
+ bitmap_set_bit (visited, n);
+
+ if (graph->succs[n])
+ EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi)
+ {
+ unsigned k = find (j);
+ if (!bitmap_bit_p (visited, k))
+ topo_visit (graph, topo_order, visited, k);
+ }
+
+ topo_order.quick_push (n);
+}
+
+/* Compute a topological ordering for GRAPH, and return the result. */
+
+static auto_vec<unsigned>
+compute_topo_order (constraint_graph_t graph)
{
unsigned int i;
unsigned int size = graph->size;
+ auto_sbitmap visited (size);
+ bitmap_clear (visited);
+
+ /* For the heuristic in add_graph_edge to work optimally make sure to
+ first visit the connected component of the graph containing
+ ESCAPED. Do this by extracting the connected component
+ with ESCAPED and append that to all other components as solve_graph
+ pops from the order. */
+ auto_vec<unsigned> tail (size);
+ topo_visit (graph, tail, visited, find (escaped_id));
+
+ auto_vec<unsigned> topo_order (size);
+
for (i = 0; i != size; ++i)
- if (!bitmap_bit_p (ti->visited, i) && find (i) == i)
- topo_visit (graph, ti, i);
+ if (!bitmap_bit_p (visited, i) && find (i) == i)
+ topo_visit (graph, topo_order, visited, i);
+
+ topo_order.splice (tail);
+ return topo_order;
}
/* Structure used to for hash value numbering of pointer equivalence
@@ -2765,17 +2743,14 @@ solve_graph (constraint_graph_t graph)
while (!bitmap_empty_p (changed))
{
unsigned int i;
- struct topo_info *ti = init_topo_info ();
stats.iterations++;
bitmap_obstack_initialize (&iteration_obstack);
- compute_topo_order (graph, ti);
-
- while (ti->topo_order.length () != 0)
+ auto_vec<unsigned> topo_order = compute_topo_order (graph);
+ while (topo_order.length () != 0)
{
-
- i = ti->topo_order.pop ();
+ i = topo_order.pop ();
/* If this variable is not a representative, skip it. */
if (find (i) != i)
@@ -2910,7 +2885,6 @@ solve_graph (constraint_graph_t graph)
}
}
}
- free_topo_info (ti);
bitmap_obstack_release (&iteration_obstack);
}