+/* Gets body of a LOOP sorted via provided BB_COMPARATOR. */
+
+basic_block *
+get_loop_body_in_custom_order (const struct loop *loop,
+ int (*bb_comparator) (const void *, const void *))
+{
+ basic_block *bbs = get_loop_body (loop);
+
+ qsort (bbs, loop->num_nodes, sizeof (basic_block), bb_comparator);
+
+ return bbs;
+}
+
+/* Get body of a LOOP in breadth first sort order. */
+
+basic_block *
+get_loop_body_in_bfs_order (const struct loop *loop)
+{
+ basic_block *blocks;
+ basic_block bb;
+ bitmap visited;
+ unsigned int i = 0;
+ unsigned int vc = 1;
+
+ gcc_assert (loop->num_nodes);
+ gcc_assert (loop->latch != EXIT_BLOCK_PTR);
+
+ blocks = XCNEWVEC (basic_block, loop->num_nodes);
+ visited = BITMAP_ALLOC (NULL);
+
+ bb = loop->header;
+ while (i < loop->num_nodes)
+ {
+ edge e;
+ edge_iterator ei;
+
+ if (!bitmap_bit_p (visited, bb->index))
+ {
+ /* This basic block is now visited */
+ bitmap_set_bit (visited, bb->index);
+ blocks[i++] = bb;
+ }
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ if (flow_bb_inside_loop_p (loop, e->dest))
+ {
+ if (!bitmap_bit_p (visited, e->dest->index))
+ {
+ bitmap_set_bit (visited, e->dest->index);
+ blocks[i++] = e->dest;
+ }
+ }
+ }
+
+ gcc_assert (i >= vc);
+
+ bb = blocks[vc++];
+ }
+
+ BITMAP_FREE (visited);
+ return blocks;
+}
+
+/* Hash function for struct loop_exit. */
+
+static hashval_t
+loop_exit_hash (const void *ex)
+{
+ const struct loop_exit *const exit = (const struct loop_exit *) ex;
+
+ return htab_hash_pointer (exit->e);
+}
+
+/* Equality function for struct loop_exit. Compares with edge. */
+
+static int
+loop_exit_eq (const void *ex, const void *e)
+{
+ const struct loop_exit *const exit = (const struct loop_exit *) ex;
+
+ return exit->e == e;
+}
+
+/* Frees the list of loop exit descriptions EX. */
+
+static void
+loop_exit_free (void *ex)
+{
+ struct loop_exit *exit = (struct loop_exit *) ex, *next;
+
+ for (; exit; exit = next)
+ {
+ next = exit->next_e;
+
+ exit->next->prev = exit->prev;
+ exit->prev->next = exit->next;
+
+ ggc_free (exit);
+ }
+}
+
+/* Returns the list of records for E as an exit of a loop. */
+
+static struct loop_exit *
+get_exit_descriptions (edge e)
+{
+ return (struct loop_exit *) htab_find_with_hash (current_loops->exits, e,
+ htab_hash_pointer (e));
+}
+
+/* Updates the lists of loop exits in that E appears.
+ If REMOVED is true, E is being removed, and we
+ just remove it from the lists of exits.
+ If NEW_EDGE is true and E is not a loop exit, we
+ do not try to remove it from loop exit lists. */
+
+void
+rescan_loop_exit (edge e, bool new_edge, bool removed)
+{
+ void **slot;
+ struct loop_exit *exits = NULL, *exit;
+ struct loop *aloop, *cloop;
+
+ if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
+ return;
+
+ if (!removed
+ && e->src->loop_father != NULL
+ && e->dest->loop_father != NULL
+ && !flow_bb_inside_loop_p (e->src->loop_father, e->dest))
+ {
+ cloop = find_common_loop (e->src->loop_father, e->dest->loop_father);
+ for (aloop = e->src->loop_father;
+ aloop != cloop;
+ aloop = loop_outer (aloop))
+ {
+ exit = GGC_NEW (struct loop_exit);
+ exit->e = e;
+
+ exit->next = aloop->exits->next;
+ exit->prev = aloop->exits;
+ exit->next->prev = exit;
+ exit->prev->next = exit;
+
+ exit->next_e = exits;
+ exits = exit;
+ }
+ }
+
+ if (!exits && new_edge)
+ return;
+
+ slot = htab_find_slot_with_hash (current_loops->exits, e,
+ htab_hash_pointer (e),
+ exits ? INSERT : NO_INSERT);
+ if (!slot)
+ return;
+
+ if (exits)
+ {
+ if (*slot)
+ loop_exit_free (*slot);
+ *slot = exits;
+ }
+ else
+ htab_clear_slot (current_loops->exits, slot);
+}
+
+/* For each loop, record list of exit edges, and start maintaining these
+ lists. */
+
+void
+record_loop_exits (void)
+{
+ basic_block bb;
+ edge_iterator ei;
+ edge e;
+
+ if (!current_loops)
+ return;
+
+ if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
+ return;
+ loops_state_set (LOOPS_HAVE_RECORDED_EXITS);
+
+ gcc_assert (current_loops->exits == NULL);
+ current_loops->exits = htab_create_alloc (2 * number_of_loops (),
+ loop_exit_hash,
+ loop_exit_eq,
+ loop_exit_free,
+ ggc_calloc, ggc_free);
+
+ FOR_EACH_BB (bb)
+ {
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ rescan_loop_exit (e, true, false);
+ }
+ }
+}
+
+/* Dumps information about the exit in *SLOT to FILE.
+ Callback for htab_traverse. */
+
+static int
+dump_recorded_exit (void **slot, void *file)
+{
+ struct loop_exit *exit = (struct loop_exit *) *slot;
+ unsigned n = 0;
+ edge e = exit->e;
+
+ for (; exit != NULL; exit = exit->next_e)
+ n++;
+
+ fprintf ((FILE*) file, "Edge %d->%d exits %u loops\n",
+ e->src->index, e->dest->index, n);
+
+ return 1;
+}
+
+/* Dumps the recorded exits of loops to FILE. */
+
+extern void dump_recorded_exits (FILE *);
+void
+dump_recorded_exits (FILE *file)
+{
+ if (!current_loops->exits)
+ return;
+ htab_traverse (current_loops->exits, dump_recorded_exit, file);
+}
+
+/* Releases lists of loop exits. */
+
+void
+release_recorded_exits (void)
+{
+ gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS));
+ htab_delete (current_loops->exits);
+ current_loops->exits = NULL;
+ loops_state_clear (LOOPS_HAVE_RECORDED_EXITS);
+}
+
+/* Returns the list of the exit edges of a LOOP. */
+
+VEC (edge, heap) *
+get_loop_exit_edges (const struct loop *loop)
+{
+ VEC (edge, heap) *edges = NULL;
+ edge e;
+ unsigned i;
+ basic_block *body;
+ edge_iterator ei;
+ struct loop_exit *exit;
+
+ gcc_assert (loop->latch != EXIT_BLOCK_PTR);
+
+ /* If we maintain the lists of exits, use them. Otherwise we must
+ scan the body of the loop. */
+ if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
+ {
+ for (exit = loop->exits->next; exit->e; exit = exit->next)
+ VEC_safe_push (edge, heap, edges, exit->e);
+ }
+ else
+ {
+ body = get_loop_body (loop);
+ for (i = 0; i < loop->num_nodes; i++)
+ FOR_EACH_EDGE (e, ei, body[i]->succs)
+ {
+ if (!flow_bb_inside_loop_p (loop, e->dest))
+ VEC_safe_push (edge, heap, edges, e);
+ }
+ free (body);
+ }
+
+ return edges;
+}
+
+/* Counts the number of conditional branches inside LOOP. */
+
+unsigned
+num_loop_branches (const struct loop *loop)
+{
+ unsigned i, n;
+ basic_block * body;
+
+ gcc_assert (loop->latch != EXIT_BLOCK_PTR);
+
+ body = get_loop_body (loop);
+ n = 0;
+ for (i = 0; i < loop->num_nodes; i++)
+ if (EDGE_COUNT (body[i]->succs) >= 2)
+ n++;
+ free (body);
+
+ return n;
+}
+