[CFG] Irreducible loop tracking
Zdenek Dvorak
rakdver@atrey.karlin.mff.cuni.cz
Thu Jun 13 11:17:00 GMT 2002
Hello.
This patch makes us to keep track of basic blocks that are part of some
irreducible loop; this improves performance of
just_once_each_iteration_p while the cost to update this information is
low (because we don't change structure of such loops in loop optimizer).
It also makes several minor changes to simple loop discovery code.
I'm commiting the change to cfg branch.
Zdenek
Changelog:
* basic-block.h (BB_IRREDUCIBLE_LOOP): New flag.
(VLS_EXPECT_MARKED_IRREDUCIBLE_LOOPS): New flag for
verify_loop_structure.
(mark_irreducible_loops): Declare.
* cfgloop.c (flow_loop_dump): Dump BB_IRREDUCIBLE_LOOP flag.
(verify_loop_structure): Check correctness of BB_IRREDUCIBLE_LOOP flags.
* cfgloopanal.c (cbp_enum_p): Removed.
(create_preheader): Fix updating loopstructure.
(just_once_each_iteration_p): Use BB_IRREDUCIBLE_LOOP flag.
(constant_iterations): Only check desc->lim_alts and desc->var_alts
lists against their heads to avoid quadratic worst case.
(simple_loop_exit_p): Use just dominated_by_p instead of
just_once_each_iteration_p on one place.
(loop_split_edge_with): Update BB_IRREDUCIBLE_LOOP flag.
(mark_irreducible_loops): New function.
* loop-new.c (copy_bbs, duplicate_loop_to_header_edge,
may_unswitch_on_p, unswitch_loop): Update BB_IRREDUCIBLE_LOOP flag.
(loop_optimizer_init): Use mark_irreducible_loops.
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.127.2.34
diff -c -3 -p -r1.127.2.34 basic-block.h
*** basic-block.h 12 Jun 2002 16:26:34 -0000 1.127.2.34
--- basic-block.h 13 Jun 2002 14:41:53 -0000
*************** typedef struct basic_block_def {
*** 234,239 ****
--- 234,240 ----
/* Used by dfs_enumerate_from; keep this one zero! */
#define BB_VISITED 8
#define BB_SUPERBLOCK 16
+ #define BB_IRREDUCIBLE_LOOP 32
/* Number of basic blocks in the current function. */
*************** extern void cancel_loop PARAMS ((struct
*** 738,746 ****
extern void cancel_loop_tree PARAMS ((struct loops *, struct loop *));
extern void verify_loop_structure PARAMS ((struct loops *, int));
! #define VLS_EXPECT_PREHEADERS 1
! #define VLS_EXPECT_SIMPLE_LATCHES 2
! #define VLS_FOR_LOOP_NEW (VLS_EXPECT_PREHEADERS | VLS_EXPECT_SIMPLE_LATCHES)
extern int expected_loop_iterations PARAMS ((const struct loop *));
typedef struct conflict_graph_def *conflict_graph;
--- 739,752 ----
extern void cancel_loop_tree PARAMS ((struct loops *, struct loop *));
extern void verify_loop_structure PARAMS ((struct loops *, int));
! enum
! {
! VLS_EXPECT_PREHEADERS=1,
! VLS_EXPECT_SIMPLE_LATCHES=2,
! VLS_EXPECT_MARKED_IRREDUCIBLE_LOOPS=4,
! VLS_FOR_LOOP_NEW = VLS_EXPECT_PREHEADERS | VLS_EXPECT_SIMPLE_LATCHES
! | VLS_EXPECT_MARKED_IRREDUCIBLE_LOOPS
! };
extern int expected_loop_iterations PARAMS ((const struct loop *));
typedef struct conflict_graph_def *conflict_graph;
*************** void test_invariants PARAMS ((struct l
*** 813,818 ****
--- 819,825 ----
bool loop_invariant_rtx_p PARAMS ((struct loop_invariants *, rtx, rtx));
basic_block loop_split_edge_with PARAMS ((edge, rtx, struct loops *));
void force_single_succ_latches PARAMS ((struct loops *));
+ void mark_irreducible_loops PARAMS ((struct loops *));
bool just_once_each_iteration_p PARAMS ((struct loops *,struct loop *, basic_block));
int num_loop_insns PARAMS ((struct loop *));
bool inside_basic_block_p PARAMS ((rtx));
Index: cfgloop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloop.c,v
retrieving revision 1.2.2.22
diff -c -3 -p -r1.2.2.22 cfgloop.c
*** cfgloop.c 6 Jun 2002 21:16:30 -0000 1.2.2.22
--- cfgloop.c 13 Jun 2002 14:41:53 -0000
*************** flow_loop_dump (loop, file, loop_dump_au
*** 139,145 ****
fprintf (file, ";; nodes:");
bbs = get_loop_body (loop);
for (i = 0; i < loop->num_nodes; i++)
! fprintf (file, " %d", bbs[i]->index);
free (bbs);
fprintf (file, "\n");
flow_edge_list_print (";; exit edges", loop->exit_edges,
--- 139,146 ----
fprintf (file, ";; nodes:");
bbs = get_loop_body (loop);
for (i = 0; i < loop->num_nodes; i++)
! fprintf (file, " %d%s", bbs[i]->index,
! (bbs[i]->flags & BB_IRREDUCIBLE_LOOP) ? "i" : "");
free (bbs);
fprintf (file, "\n");
flow_edge_list_print (";; exit edges", loop->exit_edges,
*************** find_common_loop (loop_s, loop_d)
*** 1118,1123 ****
--- 1119,1125 ----
-- results of get_loop_body really belong to the loop
-- loop header have just single entry edge and single latch edge
-- loop latches have only single successor that is header of their loop
+ -- irreducible loops are correctly marked
*/
void
verify_loop_structure (loops, flags)
*************** verify_loop_structure (loops, flags)
*** 1125,1130 ****
--- 1127,1133 ----
int flags;
{
int *sizes, i, j;
+ sbitmap irreds;
basic_block *bbs, bb;
struct loop *loop;
int err = 0;
*************** verify_loop_structure (loops, flags)
*** 1208,1213 ****
--- 1211,1249 ----
error ("Loop %d's header does not belong directly to it.", i);
err = 1;
}
+ }
+
+ /* Check irreducible loops. */
+ if (flags & VLS_EXPECT_MARKED_IRREDUCIBLE_LOOPS)
+ {
+ /* Record old info. */
+ irreds = sbitmap_alloc (last_basic_block);
+ FOR_EACH_BB (bb)
+ if (bb->flags & BB_IRREDUCIBLE_LOOP)
+ SET_BIT (irreds, bb->index);
+ else
+ RESET_BIT (irreds, bb->index);
+
+ /* Recount it. */
+ mark_irreducible_loops (loops);
+
+ /* Compare. */
+ FOR_EACH_BB (bb)
+ {
+ if ((bb->flags & BB_IRREDUCIBLE_LOOP)
+ && !TEST_BIT (irreds, bb->index))
+ {
+ error ("Basic block %d should be marked irreducible.", bb->index);
+ err = 1;
+ }
+ else if (!(bb->flags & BB_IRREDUCIBLE_LOOP)
+ && TEST_BIT (irreds, bb->index))
+ {
+ error ("Basic block %d should not be marked irreducible.", bb->index);
+ err = 1;
+ }
+ }
+ free (irreds);
}
/* Check frequencies. */
Index: cfgloopanal.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/cfgloopanal.c,v
retrieving revision 1.1.2.14
diff -c -3 -p -r1.1.2.14 cfgloopanal.c
*** cfgloopanal.c 12 Jun 2002 16:26:37 -0000 1.1.2.14
--- cfgloopanal.c 13 Jun 2002 14:41:53 -0000
*************** static void note_mem_store PARAMS ((rtx
*** 18,24 ****
static int discover_invariant PARAMS ((rtx insn, void *data));
static int not_invariant_rtx PARAMS ((rtx *rtxp, void *data));
static bool mark_maybe_invariant_set PARAMS ((rtx, rtx, rtx, struct loop_invariants *));
- static bool cbp_enum_p PARAMS ((basic_block, void *));
static bool invariant_in_blocks_p PARAMS ((rtx, basic_block *, int));
static rtx test_for_iteration PARAMS ((struct loop_desc *desc,
unsigned HOST_WIDE_INT));
--- 18,23 ----
*************** create_preheader (loop, dom, flags)
*** 446,452 ****
edge e, fallthru;
basic_block dummy;
basic_block jump, src;
! struct loop *cloop = NULL;
int nentry = 0;
rtx insn;
--- 445,451 ----
edge e, fallthru;
basic_block dummy;
basic_block jump, src;
! struct loop *cloop, *ploop;
int nentry = 0;
rtx insn;
*************** create_preheader (loop, dom, flags)
*** 475,484 ****
insn = get_last_insn ();
fallthru = split_block (loop->header, insn);
dummy = fallthru->src;
- if (loop->latch == loop->header)
- loop->latch = fallthru->dest;
loop->header = fallthru->dest;
if (flags & CP_INSIDE_CFGLAYOUT)
alloc_aux_for_block (fallthru->dest, sizeof (struct reorder_block_def));
add_to_dominance_info (dom, fallthru->dest);
--- 474,487 ----
insn = get_last_insn ();
fallthru = split_block (loop->header, insn);
dummy = fallthru->src;
loop->header = fallthru->dest;
+ /* The header could be a latch of some superloop(s); due to design of
+ split_block, it would now move to fallthru->dest. */
+ for (ploop = loop; ploop; ploop = ploop->outer)
+ if (ploop->latch == dummy)
+ ploop->latch = fallthru->dest;
+
if (flags & CP_INSIDE_CFGLAYOUT)
alloc_aux_for_block (fallthru->dest, sizeof (struct reorder_block_def));
add_to_dominance_info (dom, fallthru->dest);
*************** create_preheaders (loops, flags)
*** 532,548 ****
create_preheader (loops->parray[i], loops->cfg.dom, flags);
}
- /* Enumeration predicate for just_once_each_iteration_p. */
- static bool
- cbp_enum_p (bb, data)
- basic_block bb;
- void *data;
- {
- struct loop *loop = data;
- return bb != loop->header
- && flow_bb_inside_loop_p (loop, bb);
- }
-
/* Checks whether BB is executed exactly once in each LOOP iteration. */
bool
just_once_each_iteration_p (loops, loop, bb)
--- 535,540 ----
*************** just_once_each_iteration_p (loops, loop,
*** 550,559 ****
struct loop *loop;
basic_block bb;
{
- basic_block *bbs;
- int i, n;
- edge e;
-
/* It must be executed at least once each iteration. */
if (!dominated_by_p (loops->cfg.dom, loop->latch, bb))
return false;
--- 542,547 ----
*************** just_once_each_iteration_p (loops, loop,
*** 563,583 ****
return false;
/* But this was not enough. We might have some irreducible loop here. */
! if (bb == loop->header)
! return true;
!
! bbs = xcalloc (loop->num_nodes, sizeof (basic_block));
! n = dfs_enumerate_from (bb, 0, cbp_enum_p, bbs, loop->num_nodes,
! (void *) loop);
! for (i = 0; i < n; i++)
! for (e = bbs[i]->succ; e; e = e->succ_next)
! if (e->dest == bb)
! {
! free (bbs);
! return false;
! }
- free (bbs);
return true;
}
--- 551,559 ----
return false;
/* But this was not enough. We might have some irreducible loop here. */
! if (bb->flags & BB_IRREDUCIBLE_LOOP)
! return false;
return true;
}
*************** constant_iterations (desc, niter, may_be
*** 858,874 ****
*may_be_zero = (test != const_true_rtx);
for (ainit = desc->var_alts; ainit; ainit = XEXP (ainit, 1))
! for (alim = desc->lim_alts; alim; alim = XEXP (alim, 1))
! {
! if (!(expr = count_loop_iterations (desc, XEXP (ainit, 0), XEXP (alim, 0))))
! abort ();
! if (GET_CODE (expr) == CONST_INT)
! {
! *niter = INTVAL (expr);
! return true;
! }
! }
return false;
}
--- 834,863 ----
*may_be_zero = (test != const_true_rtx);
+ /* It would make a little sense to check every with every when we
+ know that all but the first alternative are simply registers. */
for (ainit = desc->var_alts; ainit; ainit = XEXP (ainit, 1))
! {
! alim = XEXP (desc->lim_alts, 0);
! if (!(expr = count_loop_iterations (desc, XEXP (ainit, 0), alim)))
! abort ();
! if (GET_CODE (expr) == CONST_INT)
! {
! *niter = INTVAL (expr);
! return true;
! }
! }
! for (alim = XEXP (desc->lim_alts, 1); alim; alim = XEXP (alim, 1))
! {
! ainit = XEXP (desc->var_alts, 0);
! if (!(expr = count_loop_iterations (desc, ainit, XEXP (alim, 0))))
! abort ();
! if (GET_CODE (expr) == CONST_INT)
! {
! *niter = INTVAL (expr);
! return true;
! }
! }
return false;
}
*************** simple_loop_exit_p (loops, loop, exit_ed
*** 1069,1076 ****
if (!exit_bb)
return false;
! /* It must be tested once during any iteration. */
! if (!just_once_each_iteration_p (loops, loop, exit_bb))
return false;
/* It must end in a simple conditional jump. */
--- 1058,1065 ----
if (!exit_bb)
return false;
! /* It must be tested (at least) once during any iteration. */
! if (!dominated_by_p (loops->cfg.dom, loop->latch, exit_bb))
return false;
/* It must end in a simple conditional jump. */
*************** loop_split_edge_with (e, insns, loops)
*** 1209,1215 ****
new_bb = create_basic_block (NULL_RTX, NULL_RTX, EXIT_BLOCK_PTR->prev_bb);
add_to_dominance_info (loops->cfg.dom, new_bb);
add_bb_to_loop (new_bb, loop_c);
! new_bb->flags = BB_SUPERBLOCK;
new_e = make_edge (new_bb, dest, EDGE_FALLTHRU);
new_e->probability = REG_BR_PROB_BASE;
--- 1198,1211 ----
new_bb = create_basic_block (NULL_RTX, NULL_RTX, EXIT_BLOCK_PTR->prev_bb);
add_to_dominance_info (loops->cfg.dom, new_bb);
add_bb_to_loop (new_bb, loop_c);
! new_bb->flags = insns ? BB_SUPERBLOCK : 0;
! if (src->flags & BB_IRREDUCIBLE_LOOP)
! {
! /* We expect simple preheaders here. */
! if ((dest->flags & BB_IRREDUCIBLE_LOOP)
! || dest->loop_father->header == dest)
! new_bb->flags |= BB_IRREDUCIBLE_LOOP;
! }
new_e = make_edge (new_bb, dest, EDGE_FALLTHRU);
new_e->probability = REG_BR_PROB_BASE;
*************** force_single_succ_latches (loops)
*** 1258,1261 ****
--- 1254,1411 ----
for (e = loop->header->pred; e->src != loop->latch; e = e->pred_next);
loop_split_edge_with (e, NULL_RTX, loops);
}
+ }
+
+ /* Marks blocks that are part of non-reckognized 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. */
+ void
+ mark_irreducible_loops (loops)
+ struct loops *loops;
+ {
+ int *dfs_in, *closed, *mr, *n_edges, *stack, i;
+ edge **edges, e;
+ basic_block act;
+ int stack_top, tick, depth;
+ struct loop *cloop;
+
+ /* The first last_basic_block + 1 entries are for real blocks (including
+ entry); then we have loops->num - 1 fake blocks for loops to that we
+ assign edges leading from loops (fake loop 0 is not interesting). */
+ dfs_in = xmalloc ((last_basic_block + loops->num) * sizeof (int));
+ closed = xmalloc ((last_basic_block + loops->num) * sizeof (int));
+ mr = xmalloc ((last_basic_block + loops->num) * sizeof (int));
+ n_edges = xmalloc ((last_basic_block + loops->num) * sizeof (int));
+ edges = xmalloc ((last_basic_block + loops->num) * sizeof (edge *));
+ stack = xmalloc ((n_basic_blocks + loops->num) * sizeof (int));
+
+ /* Create the edge lists. */
+ for (i = 0; i < last_basic_block + loops->num; i++)
+ n_edges[i] = 0;
+ 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. */
+ if (act->loop_father == e->dest->loop_father
+ || act->loop_father == e->dest->loop_father->outer)
+ {
+ n_edges[act->index + 1]++;
+ continue;
+ }
+ /* Edges exiting loops remain. They should lead from representative
+ of the son of nearest common ancestor of the loops in that
+ act lays. */
+ 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];
+ n_edges[cloop->num + last_basic_block]++;
+ }
+
+ for (i = 0; i < last_basic_block + loops->num; i++)
+ {
+ edges[i] = xmalloc (n_edges[i] * sizeof (edge));
+ n_edges[i] = 0;
+ }
+
+ FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
+ for (e = act->succ; e; e = e->succ_next)
+ {
+ if (e->dest == EXIT_BLOCK_PTR)
+ continue;
+ if (e->dest->loop_father->header == e->dest
+ && e->dest->loop_father->latch == act)
+ continue;
+ if (act->loop_father == e->dest->loop_father
+ || act->loop_father == e->dest->loop_father->outer)
+ {
+ edges[act->index + 1][n_edges[act->index + 1]++] = e;
+ continue;
+ }
+ 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];
+ i = cloop->num + last_basic_block;
+ edges[i][n_edges[i]++] = e;
+ }
+
+ /* Compute dfs numbering, starting from loop headers, and mark found
+ loops.*/
+ tick = 0;
+ for (i = 0; i < last_basic_block + loops->num; i++)
+ {
+ dfs_in[i] = -1;
+ closed[i] = 0;
+ mr[i] = last_basic_block + loops->num;
+ }
+
+ stack_top = 0;
+ for (i = 0; i < loops->num; i++)
+ if (loops->parray[i])
+ stack[stack_top++] = loops->parray[i]->header->index + 1;
+
+ while (stack_top)
+ {
+ int idx, sidx;
+
+ idx = stack[stack_top - 1];
+ if (dfs_in[idx] < 0)
+ dfs_in[idx] = tick++;
+
+ while (n_edges[idx])
+ {
+ e = edges[idx][--n_edges[idx]];
+ sidx = e->dest->loop_father->header == e->dest
+ ? e->dest->loop_father->num + last_basic_block
+ : e->dest->index + 1;
+ if (closed[sidx])
+ continue;
+ if (dfs_in[sidx] < 0)
+ {
+ stack[stack_top++] = sidx;
+ goto next;
+ }
+ if (dfs_in[sidx] < mr[idx])
+ mr[idx] = dfs_in[sidx];
+ }
+
+ /* Return back. */
+ closed[idx] = 1;
+ stack_top--;
+ if (stack_top && dfs_in[stack[stack_top - 1]] >= 0)
+ {
+ /* Propagate information back. */
+ sidx = stack[stack_top - 1];
+ if (mr[sidx] > mr[idx])
+ mr[sidx] = mr[idx];
+ }
+ /* Mark the block if relevant. */
+ if (idx && idx <= last_basic_block && mr[idx] <= dfs_in[idx])
+ BASIC_BLOCK (idx - 1)->flags |= BB_IRREDUCIBLE_LOOP;
+ next:;
+ }
+
+ free (stack);
+ free (dfs_in);
+ free (closed);
+ free (mr);
+ for (i = 0; i < last_basic_block + loops->num; i++)
+ free (edges[i]);
+ free (edges);
+ free (n_edges);
}
Index: loop-new.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/loop-new.c,v
retrieving revision 1.1.2.25
diff -c -3 -p -r1.1.2.25 loop-new.c
*** loop-new.c 6 Jun 2002 21:16:31 -0000 1.1.2.25
--- loop-new.c 13 Jun 2002 14:41:53 -0000
*************** static void duplicate_subloops PARAMS ((
*** 47,53 ****
static void copy_loops_to PARAMS ((struct loops *, struct loop **, int, struct loop *));
static void loop_redirect_edge PARAMS ((edge, basic_block));
static bool loop_delete_branch_edge PARAMS ((edge));
! static void copy_bbs PARAMS ((basic_block *, int, edge, edge, basic_block **, struct loops *, edge *, edge *));
static struct loop *unswitch_loop PARAMS ((struct loops *, struct loop *, basic_block));
static void remove_bbs PARAMS ((dominance_info, basic_block *, int));
static bool rpe_enum_p PARAMS ((basic_block, void *));
--- 47,53 ----
static void copy_loops_to PARAMS ((struct loops *, struct loop **, int, struct loop *));
static void loop_redirect_edge PARAMS ((edge, basic_block));
static bool loop_delete_branch_edge PARAMS ((edge));
! static void copy_bbs PARAMS ((basic_block *, int, edge, edge, basic_block **, struct loops *, edge *, edge *, int));
static struct loop *unswitch_loop PARAMS ((struct loops *, struct loop *, basic_block));
static void remove_bbs PARAMS ((dominance_info, basic_block *, int));
static bool rpe_enum_p PARAMS ((basic_block, void *));
*************** loop_optimizer_init (dumpfile)
*** 100,105 ****
--- 100,108 ----
/* Force all latches to have only single successor. */
force_single_succ_latches (loops);
+ /* Mark irreducible loops. */
+ mark_irreducible_loops (loops);
+
/* Dump loops. */
flow_loops_dump (loops, dumpfile, NULL, 1);
*************** may_unswitch_on_p (loops, bb, loop, body
*** 229,237 ****
|| !flow_bb_inside_loop_p (loop, bb->succ->succ_next->dest))
return false;
! /* Latch must be dominated by it (ugly technical restriction,
! we should remove this later). */
! if (!dominated_by_p (loops->cfg.dom, loop->latch, bb))
return false;
/* Condition must be invariant. */
--- 232,240 ----
|| !flow_bb_inside_loop_p (loop, bb->succ->succ_next->dest))
return false;
! /* It must be executed just once each iteration (because otherwise we
! are unable to update dominator/irreducible loop information correctly). */
! if (!just_once_each_iteration_p (loops, loop, bb))
return false;
/* Condition must be invariant. */
*************** unswitch_loop (loops, loop, unswitch_on)
*** 804,812 ****
basic_block unswitch_on;
{
edge entry, e, latch_edge;
! basic_block switch_bb, unswitch_on_alt;
struct loop *nloop;
sbitmap zero_bitmap;
/* Some sanity checking. */
if (!flow_bb_inside_loop_p (loop, unswitch_on))
--- 807,816 ----
basic_block unswitch_on;
{
edge entry, e, latch_edge;
! basic_block switch_bb, unswitch_on_alt, src;
struct loop *nloop;
sbitmap zero_bitmap;
+ int irred_flag;
/* Some sanity checking. */
if (!flow_bb_inside_loop_p (loop, unswitch_on))
*************** unswitch_loop (loops, loop, unswitch_on)
*** 814,820 ****
if (!unswitch_on->succ || !unswitch_on->succ->succ_next ||
unswitch_on->succ->succ_next->succ_next)
abort ();
! if (!dominated_by_p (loops->cfg.dom, loop->latch, unswitch_on))
abort ();
if (loop->inner)
abort ();
--- 818,824 ----
if (!unswitch_on->succ || !unswitch_on->succ->succ_next ||
unswitch_on->succ->succ_next->succ_next)
abort ();
! if (!just_once_each_iteration_p (loops, loop, unswitch_on))
abort ();
if (loop->inner)
abort ();
*************** unswitch_loop (loops, loop, unswitch_on)
*** 828,851 ****
return NULL;
if (!cfg_layout_can_duplicate_bb_p (unswitch_on))
return NULL;
!
! for (entry = loop->header->pred;
! entry->src == loop->latch;
! entry = entry->pred_next);
/* Make a copy. */
zero_bitmap = sbitmap_alloc (2);
sbitmap_zero (zero_bitmap);
if (!duplicate_loop_to_header_edge (loop, entry, loops, 1,
zero_bitmap, NULL, NULL, NULL, 0))
return NULL;
free (zero_bitmap);
/* Record switch block. */
unswitch_on_alt = RBI (unswitch_on)->copy;
/* Make a copy of unswitched block. */
switch_bb = cfg_layout_duplicate_bb (unswitch_on, NULL);
add_to_dominance_info (loops->cfg.dom, switch_bb);
RBI (unswitch_on)->copy = unswitch_on_alt;
--- 832,859 ----
return NULL;
if (!cfg_layout_can_duplicate_bb_p (unswitch_on))
return NULL;
!
! entry = loop_preheader_edge (loop);
/* Make a copy. */
+ src = entry->src;
+ irred_flag = src->flags & BB_IRREDUCIBLE_LOOP;
+ src->flags &= ~BB_IRREDUCIBLE_LOOP;
zero_bitmap = sbitmap_alloc (2);
sbitmap_zero (zero_bitmap);
if (!duplicate_loop_to_header_edge (loop, entry, loops, 1,
zero_bitmap, NULL, NULL, NULL, 0))
return NULL;
free (zero_bitmap);
+ src->flags |= irred_flag;
/* Record switch block. */
unswitch_on_alt = RBI (unswitch_on)->copy;
/* Make a copy of unswitched block. */
switch_bb = cfg_layout_duplicate_bb (unswitch_on, NULL);
+ switch_bb->flags &= ~BB_IRREDUCIBLE_LOOP;
+ switch_bb->flags |= irred_flag;
add_to_dominance_info (loops->cfg.dom, switch_bb);
RBI (unswitch_on)->copy = unswitch_on_alt;
*************** loop_delete_branch_edge (e)
*** 990,998 ****
/* Duplicates BBS. Newly created bbs are placed into NEW_BBS, edges to
header (target of ENTRY) and copy of header are returned, edge ENTRY
is redirected to header copy. Assigns bbs into loops, updates
! dominators. */
static void
! copy_bbs (bbs, n, entry, latch_edge, new_bbs, loops, header_edge, copy_header_edge)
basic_block *bbs;
int n;
edge entry;
--- 998,1007 ----
/* Duplicates BBS. Newly created bbs are placed into NEW_BBS, edges to
header (target of ENTRY) and copy of header are returned, edge ENTRY
is redirected to header copy. Assigns bbs into loops, updates
! dominators. If ADD_IRREDUCIBLE_FLAG, basic blocks that are not
! member of any inner loop are marked irreducible. */
static void
! copy_bbs (bbs, n, entry, latch_edge, new_bbs, loops, header_edge, copy_header_edge, add_irreducible_flag)
basic_block *bbs;
int n;
edge entry;
*************** copy_bbs (bbs, n, entry, latch_edge, new
*** 1001,1006 ****
--- 1010,1016 ----
struct loops *loops;
edge *header_edge;
edge *copy_header_edge;
+ int add_irreducible_flag;
{
int i;
basic_block bb, new_bb, header = entry->dest, dom_bb;
*************** copy_bbs (bbs, n, entry, latch_edge, new
*** 1024,1029 ****
--- 1034,1043 ----
if (bb->loop_father->latch == bb &&
bb->loop_father != header->loop_father)
new_bb->loop_father->latch = new_bb;
+ /* Take care of irreducible loops. */
+ if (add_irreducible_flag
+ && bb->loop_father == header->loop_father)
+ new_bb->flags |= BB_IRREDUCIBLE_LOOP;
}
/* Set dominators. */
*************** copy_bbs (bbs, n, entry, latch_edge, new
*** 1033,1039 ****
new_bb = (*new_bbs)[i];
if (bb != header)
{
! /* For anything than loop header, just copy it. */
dom_bb = get_immediate_dominator (loops->cfg.dom, bb);
dom_bb = RBI (dom_bb)->copy;
}
--- 1047,1053 ----
new_bb = (*new_bbs)[i];
if (bb != header)
{
! /* For anything else than loop header, just copy it. */
dom_bb = get_immediate_dominator (loops->cfg.dom, bb);
dom_bb = RBI (dom_bb)->copy;
}
*************** duplicate_loop_to_header_edge (loop, e,
*** 1197,1202 ****
--- 1211,1217 ----
int i, j, n;
int is_latch = (latch == e->src);
int k0, k, kk, freq_in, freq_e, freq_le;
+ int add_irreducible_flag;
if (e->dest != loop->header)
abort ();
*************** duplicate_loop_to_header_edge (loop, e,
*** 1225,1230 ****
--- 1240,1247 ----
}
}
+ add_irreducible_flag = !is_latch && (e->src->flags & BB_IRREDUCIBLE_LOOP);
+
/* Find edge from latch. */
latch_edge = loop_latch_edge (loop);
*************** duplicate_loop_to_header_edge (loop, e,
*** 1319,1325 ****
copy_loops_to (loops, orig_loops, n_orig_loops, target);
/* Copy bbs. */
! copy_bbs (bbs, n, e, latch_edge, &new_bbs, loops, &e, &he);
if (is_latch)
loop->latch = RBI (latch)->copy;
--- 1336,1342 ----
copy_loops_to (loops, orig_loops, n_orig_loops, target);
/* Copy bbs. */
! copy_bbs (bbs, n, e, latch_edge, &new_bbs, loops, &e, &he, add_irreducible_flag);
if (is_latch)
loop->latch = RBI (latch)->copy;
More information about the Gcc-patches
mailing list