-/* Releases the memory occupied by G. */
-
-static void
-free_graph (struct graph *g)
-{
- struct edge *e, *n;
- int i;
-
- for (i = 0; i < g->n_vertices; i++)
- for (e = g->vertices[i].succ; e; e = n)
- {
- n = e->succ_next;
- free (e);
- }
- free (g->vertices);
- free (g);
-}
-
-/* Marks blocks and edges that are part of non-recognized loops; i.e. we
- throw away all latch edges and mark blocks inside any remaining cycle.
- Everything is a bit complicated due to fact we do not want to do this
- for parts of cycles that only "pass" through some loop -- i.e. for
- each cycle, we want to mark blocks that belong directly to innermost
- loop containing the whole cycle.
-
- LOOPS is the loop tree. */
-
-#define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block)
-#define BB_REPR(BB) ((BB)->index + 1)
-
-void
-mark_irreducible_loops (struct loops *loops)
-{
- basic_block act;
- edge e;
- int i, src, dest;
- struct graph *g;
- int *queue1 = xmalloc ((last_basic_block + loops->num) * sizeof (int));
- int *queue2 = xmalloc ((last_basic_block + loops->num) * sizeof (int));
- int nq, depth;
- struct loop *cloop;
-
- /* Reset the flags. */
- FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
- {
- act->flags &= ~BB_IRREDUCIBLE_LOOP;
- for (e = act->succ; e; e = e->succ_next)
- e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
- }
-
- /* Create the edge lists. */
- g = new_graph (last_basic_block + loops->num);
-
- FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
- for (e = act->succ; e; e = e->succ_next)
- {
- /* Ignore edges to exit. */
- if (e->dest == EXIT_BLOCK_PTR)
- continue;
-
- /* And latch edges. */
- if (e->dest->loop_father->header == e->dest
- && e->dest->loop_father->latch == act)
- continue;
-
- /* Edges inside a single loop should be left where they are. Edges
- to subloop headers should lead to representative of the subloop,
- but from the same place.
-
- Edges exiting loops should lead from representative
- of the son of nearest common ancestor of the loops in that
- act lays. */
-
- src = BB_REPR (act);
- dest = BB_REPR (e->dest);
-
- if (e->dest->loop_father->header == e->dest)
- dest = LOOP_REPR (e->dest->loop_father);
-
- if (!flow_bb_inside_loop_p (act->loop_father, e->dest))
- {
- depth = find_common_loop (act->loop_father,
- e->dest->loop_father)->depth + 1;
- if (depth == act->loop_father->depth)
- cloop = act->loop_father;
- else
- cloop = act->loop_father->pred[depth];
-
- src = LOOP_REPR (cloop);
- }
-
- add_edge (g, src, dest, e);
- }
-
- /* Find the strongly connected components. Use the algorithm of Tarjan --
- first determine the postorder dfs numbering in reversed graph, then
- run the dfs on the original graph in the order given by decreasing
- numbers assigned by the previous pass. */
- nq = 0;
- FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
- {
- queue1[nq++] = BB_REPR (act);
- }
- for (i = 1; i < (int) loops->num; i++)
- if (loops->parray[i])
- queue1[nq++] = LOOP_REPR (loops->parray[i]);
- dfs (g, queue1, nq, queue2, false);
- for (i = 0; i < nq; i++)
- queue1[i] = queue2[nq - i - 1];
- dfs (g, queue1, nq, NULL, true);
-
- /* Mark the irreducible loops. */
- for_each_edge (g, check_irred);
-
- free_graph (g);
- free (queue1);
- free (queue2);
-
- loops->state |= LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS;
-}
projects / gcc.git / blobdiff