From a5414ff59071320dd80a6541af5befab853ca6ff Mon Sep 17 00:00:00 2001 From: rakdver Date: Wed, 5 Mar 2003 22:05:18 +0000 Subject: [PATCH] * basic-block.h (EDGE_IRREDUCIBLE_LOOP, EDGE_ALL_FLAGS): New. * cfg.c (dump_edge_info): Add EDGE_IRREDUCIBLE_LOOP flag dump. * cfgloop.c (flow_loop_free): Made global. (establish_preds): New static function. (flow_loop_tree_node_add): Handle subloops of added loop correctly. (get_loop_exit_edges): New. (verify_loop_structure): Verify EDGE_IRREDUCIBLE_LOOP flags. * cfgloop.h (flow_loop_free, get_loop_exit_edges, unloop): Declare. * cfgloopanal.c (mark_irreducible_loops): Mark edges in irreducible loops. * cfgloopmanip.c (loop_delete_branch_edge): Allow to test for removability of an edge. (fix_irreducible_loops): New static function. (find_path, remove_path): Add ability to remove enclosing loops. (unloop): New. (copy_bbs, duplicate_loop_to_header_edge): Use EDGE_IRREDUCIBLE_LOOP flags. * cfgrtl.c (verify_flow_info): Handle EDGE_IRREDUCIBLE_LOOP flag. * loop-unroll.c (peel_loops_completely): Do not duplicate loop if not neccessary. (decide_peel_completely, peel_loops_completely): Allow complete peeling of non-duplicable once rolling loops. * loop-unswitch.c (unswitch_loop): Update EDGE_IRREDUCIBLE_LOOP flags. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@63864 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/ChangeLog | 26 ++++++ gcc/basic-block.h | 4 +- gcc/cfg.c | 2 +- gcc/cfgloop.c | 98 +++++++++++++++++--- gcc/cfgloop.h | 3 + gcc/cfgloopanal.c | 51 ++++++++--- gcc/cfgloopmanip.c | 257 +++++++++++++++++++++++++++++++++++++++++----------- gcc/cfgrtl.c | 8 +- gcc/loop-unroll.c | 87 ++++++++---------- gcc/loop-unswitch.c | 26 ++++-- 10 files changed, 426 insertions(+), 136 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index e6cfe6f..6b90313 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,29 @@ +2003-03-05 Zdenek Dvorak + + * basic-block.h (EDGE_IRREDUCIBLE_LOOP, EDGE_ALL_FLAGS): New. + * cfg.c (dump_edge_info): Add EDGE_IRREDUCIBLE_LOOP flag dump. + * cfgloop.c (flow_loop_free): Made global. + (establish_preds): New static function. + (flow_loop_tree_node_add): Handle subloops of added loop correctly. + (get_loop_exit_edges): New. + (verify_loop_structure): Verify EDGE_IRREDUCIBLE_LOOP flags. + * cfgloop.h (flow_loop_free, get_loop_exit_edges, unloop): Declare. + * cfgloopanal.c (mark_irreducible_loops): Mark edges in irreducible + loops. + * cfgloopmanip.c (loop_delete_branch_edge): Allow to test for + removability of an edge. + (fix_irreducible_loops): New static function. + (find_path, remove_path): Add ability to remove enclosing loops. + (unloop): New. + (copy_bbs, duplicate_loop_to_header_edge): Use EDGE_IRREDUCIBLE_LOOP + flags. + * cfgrtl.c (verify_flow_info): Handle EDGE_IRREDUCIBLE_LOOP flag. + * loop-unroll.c (peel_loops_completely): Do not duplicate loop if + not neccessary. + (decide_peel_completely, peel_loops_completely): Allow complete peeling + of non-duplicable once rolling loops. + * loop-unswitch.c (unswitch_loop): Update EDGE_IRREDUCIBLE_LOOP flags. + Wed Mar 5 21:40:57 2003 J"orn Rennecke * sh.h (OVERRIDE_OPTIONS): For TARGET_SHMEDIA, the minimum value diff --git a/gcc/basic-block.h b/gcc/basic-block.h index 680bba5..e62419f 100644 --- a/gcc/basic-block.h +++ b/gcc/basic-block.h @@ -150,6 +150,8 @@ typedef struct edge_def { #define EDGE_DFS_BACK 32 /* A backwards edge */ #define EDGE_CAN_FALLTHRU 64 /* Candidate for straight line flow. */ +#define EDGE_IRREDUCIBLE_LOOP 128 /* Part of irreducible loop. */ +#define EDGE_ALL_FLAGS 255 #define EDGE_COMPLEX (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_EH) @@ -540,7 +542,7 @@ extern void init_flow PARAMS ((void)); extern void reorder_basic_blocks PARAMS ((void)); extern void dump_bb PARAMS ((basic_block, FILE *)); extern void debug_bb PARAMS ((basic_block)); -extern void debug_bb_n PARAMS ((int)); +extern basic_block debug_bb_n PARAMS ((int)); extern void dump_regset PARAMS ((regset, FILE *)); extern void debug_regset PARAMS ((regset)); extern void allocate_reg_life_data PARAMS ((void)); diff --git a/gcc/cfg.c b/gcc/cfg.c index 29879a8..de7a212 100644 --- a/gcc/cfg.c +++ b/gcc/cfg.c @@ -639,7 +639,7 @@ dump_edge_info (file, e, do_succ) if (e->flags) { static const char * const bitnames[] - = {"fallthru", "ab", "abcall", "eh", "fake", "dfs_back", "can_fallthru"}; + = {"fallthru", "ab", "abcall", "eh", "fake", "dfs_back", "can_fallthru","irreducible"}; int comma = 0; int i, flags = e->flags; diff --git a/gcc/cfgloop.c b/gcc/cfgloop.c index 9f8c305..92d9055 100644 --- a/gcc/cfgloop.c +++ b/gcc/cfgloop.c @@ -43,12 +43,12 @@ static basic_block flow_loop_pre_header_find PARAMS ((basic_block, dominance_info)); static int flow_loop_level_compute PARAMS ((struct loop *)); static int flow_loops_level_compute PARAMS ((struct loops *)); +static void establish_preds PARAMS ((struct loop *)); static basic_block make_forwarder_block PARAMS ((basic_block, int, int, edge, int)); static void canonicalize_loop_headers PARAMS ((void)); static bool glb_enum_p PARAMS ((basic_block, void *)); static void redirect_edge_with_latch_update PARAMS ((edge, basic_block)); -static void flow_loop_free PARAMS ((struct loop *)); /* Dump loop related CFG information. */ @@ -185,7 +185,7 @@ flow_loops_dump (loops, file, loop_dump_aux, verbose) } /* Free data allocated for LOOP. */ -static void +void flow_loop_free (loop) struct loop *loop; { @@ -447,8 +447,26 @@ flow_loop_pre_header_find (header, dom) return pre_header; } +static void +establish_preds (loop) + struct loop *loop; +{ + struct loop *ploop, *father = loop->outer; + + loop->depth = father->depth + 1; + if (loop->pred) + free (loop->pred); + loop->pred = xmalloc (sizeof (struct loop *) * loop->depth); + memcpy (loop->pred, father->pred, sizeof (struct loop *) * father->depth); + loop->pred[father->depth] = father; + + for (ploop = loop->inner; ploop; ploop = ploop->next) + establish_preds (ploop); +} + /* Add LOOP to the loop hierarchy tree where FATHER is father of the - added loop. */ + added loop. If LOOP has some children, take care of that their + pred field will be initialized correctly. */ void flow_loop_tree_node_add (father, loop) @@ -459,10 +477,7 @@ flow_loop_tree_node_add (father, loop) father->inner = loop; loop->outer = father; - loop->depth = father->depth + 1; - loop->pred = xmalloc (sizeof (struct loop *) * loop->depth); - memcpy (loop->pred, father->pred, sizeof (struct loop *) * father->depth); - loop->pred[father->depth] = father; + establish_preds (loop); } /* Remove LOOP from the loop hierarchy tree. */ @@ -1029,6 +1044,37 @@ get_loop_body (loop) return tovisit; } +/* Gets exit edges of a LOOP, returning their number in N_EDGES. */ +edge * +get_loop_exit_edges (loop, n_edges) + const struct loop *loop; + unsigned *n_edges; +{ + edge *edges, e; + unsigned i, n; + basic_block * body; + + if (loop->latch == EXIT_BLOCK_PTR) + abort (); + + body = get_loop_body (loop); + n = 0; + for (i = 0; i < loop->num_nodes; i++) + for (e = body[i]->succ; e; e = e->succ_next) + if (!flow_bb_inside_loop_p (loop, e->dest)) + n++; + edges = xmalloc (n * sizeof (edge)); + *n_edges = n; + n = 0; + for (i = 0; i < loop->num_nodes; i++) + for (e = body[i]->succ; e; e = e->succ_next) + if (!flow_bb_inside_loop_p (loop, e->dest)) + edges[n++] = e; + free (body); + + return edges; +} + /* Adds basic block BB to LOOP. */ void add_bb_to_loop (bb, loop) @@ -1135,6 +1181,7 @@ verify_loop_structure (loops) basic_block *bbs, bb; struct loop *loop; int err = 0; + edge e; /* Check sizes. */ sizes = xcalloc (loops->num, sizeof (int)); @@ -1215,6 +1262,12 @@ verify_loop_structure (loops) error ("Loop %d's header does not belong directly to it.", i); err = 1; } + if ((loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) + && (loop_latch_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)) + { + error ("Loop %d's latch is marked as part of irreducible region.", i); + err = 1; + } } /* Check irreducible loops. */ @@ -1223,10 +1276,15 @@ verify_loop_structure (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); + { + if (bb->flags & BB_IRREDUCIBLE_LOOP) + SET_BIT (irreds, bb->index); + else + RESET_BIT (irreds, bb->index); + for (e = bb->succ; e; e = e->succ_next) + if (e->flags & EDGE_IRREDUCIBLE_LOOP) + e->flags |= EDGE_ALL_FLAGS + 1; + } /* Recount it. */ mark_irreducible_loops (loops); @@ -1246,6 +1304,24 @@ verify_loop_structure (loops) error ("Basic block %d should not be marked irreducible.", bb->index); err = 1; } + for (e = bb->succ; e; e = e->succ_next) + { + if ((e->flags & EDGE_IRREDUCIBLE_LOOP) + && !(e->flags & (EDGE_ALL_FLAGS + 1))) + { + error ("Edge from %d to %d should be marked irreducible.", + e->src->index, e->dest->index); + err = 1; + } + else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP) + && (e->flags & (EDGE_ALL_FLAGS + 1))) + { + error ("Edge from %d to %d should not be marked irreducible.", + e->src->index, e->dest->index); + err = 1; + } + e->flags &= ~(EDGE_ALL_FLAGS + 1); + } } free (irreds); } diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h index ae1e529..c5db914 100644 --- a/gcc/cfgloop.h +++ b/gcc/cfgloop.h @@ -266,6 +266,7 @@ extern void flow_loop_dump PARAMS ((const struct loop *, FILE *, FILE *, int), int)); extern int flow_loop_scan PARAMS ((struct loops *, struct loop *, int)); +extern void flow_loop_free PARAMS ((struct loop *)); void mark_irreducible_loops PARAMS ((struct loops *)); /* Loop datastructure manipulation/querying. */ @@ -282,6 +283,7 @@ extern int average_num_loop_insns PARAMS ((struct loop *)); /* Loops & cfg manipulation. */ extern basic_block *get_loop_body PARAMS ((const struct loop *)); +extern edge *get_loop_exit_edges PARAMS ((const struct loop *, unsigned *)); extern edge loop_preheader_edge PARAMS ((const struct loop *)); extern edge loop_latch_edge PARAMS ((const struct loop *)); @@ -326,6 +328,7 @@ extern int duplicate_loop_to_header_edge PARAMS ((struct loop *, edge, unsigned *, int)); extern struct loop *loopify PARAMS ((struct loops *, edge, edge, basic_block)); +extern void unloop PARAMS ((struct loops *, struct loop *)); extern bool remove_path PARAMS ((struct loops *, edge)); extern edge split_loop_bb PARAMS ((struct loops *, basic_block, rtx)); diff --git a/gcc/cfgloopanal.c b/gcc/cfgloopanal.c index 1c2a57d..5e00d43 100644 --- a/gcc/cfgloopanal.c +++ b/gcc/cfgloopanal.c @@ -819,12 +819,12 @@ simple_loop_p (loops, loop, desc) return any; } -/* Marks blocks 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. */ +/* 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. */ void mark_irreducible_loops (loops) struct loops *loops; @@ -832,10 +832,19 @@ mark_irreducible_loops (loops) int *dfs_in, *closed, *mr, *mri, *n_edges, *stack; unsigned i; edge **edges, e; + edge *estack; basic_block act; int stack_top, tick, 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; + } + /* 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). */ @@ -846,6 +855,7 @@ mark_irreducible_loops (loops) 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)); + estack = xmalloc ((n_basic_blocks + loops->num) * sizeof (edge)); /* Create the edge lists. */ for (i = 0; i < last_basic_block + loops->num; i++) @@ -923,7 +933,11 @@ mark_irreducible_loops (loops) stack_top = 0; for (i = 0; i < loops->num; i++) if (loops->parray[i]) - stack[stack_top++] = loops->parray[i]->header->index + 1; + { + stack[stack_top] = loops->parray[i]->header->index + 1; + estack[stack_top] = NULL; + stack_top++; + } while (stack_top) { @@ -941,16 +955,24 @@ mark_irreducible_loops (loops) : e->dest->index + 1; if (closed[sidx]) { - if (mr[sidx] < mr[idx] && !closed[mri[sidx]]) + if (!closed[mri[sidx]]) { - mr[idx] = mr[sidx]; - mri[idx] = mri[sidx]; + if (mr[sidx] < mr[idx]) + { + mr[idx] = mr[sidx]; + mri[idx] = mri[sidx]; + } + + if (mr[sidx] <= dfs_in[idx]) + e->flags |= EDGE_IRREDUCIBLE_LOOP; } continue; } if (dfs_in[sidx] < 0) { - stack[stack_top++] = sidx; + stack[stack_top] = sidx; + estack[stack_top] = e; + stack_top++; goto next; } if (dfs_in[sidx] < mr[idx]) @@ -958,12 +980,14 @@ mark_irreducible_loops (loops) mr[idx] = dfs_in[sidx]; mri[idx] = sidx; } + e->flags |= EDGE_IRREDUCIBLE_LOOP; } /* Return back. */ closed[idx] = 1; + e = estack[stack_top - 1]; stack_top--; - if (stack_top && dfs_in[stack[stack_top - 1]] >= 0) + if (e) { /* Propagate information back. */ sidx = stack[stack_top - 1]; @@ -972,6 +996,8 @@ mark_irreducible_loops (loops) mr[sidx] = mr[idx]; mri[sidx] = mri[idx]; } + if (mr[idx] <= dfs_in[sidx]) + e->flags |= EDGE_IRREDUCIBLE_LOOP; } /* Mark the block if relevant. */ if (idx && idx <= last_basic_block && mr[idx] <= dfs_in[idx]) @@ -980,6 +1006,7 @@ next:; } free (stack); + free (estack); free (dfs_in); free (closed); free (mr); diff --git a/gcc/cfgloopmanip.c b/gcc/cfgloopmanip.c index 69cb63b..e2e039b 100644 --- a/gcc/cfgloopmanip.c +++ b/gcc/cfgloopmanip.c @@ -36,7 +36,7 @@ static void duplicate_subloops PARAMS ((struct loops *, struct loop *, 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 bool loop_delete_branch_edge PARAMS ((edge, int)); static void copy_bbs PARAMS ((basic_block *, int, edge, edge, basic_block **, struct loops *, edge *, @@ -58,6 +58,7 @@ static void record_exit_edges PARAMS ((edge, basic_block *, int, edge *, unsigned *, int)); static basic_block create_preheader PARAMS ((struct loop *, dominance_info, int)); +static void fix_irreducible_loops PARAMS ((basic_block)); /* Splits basic block BB after INSN, returns created edge. Updates loops and dominators. */ @@ -128,28 +129,20 @@ remove_bbs (dom, bbs, nbbs) /* Find path -- i.e. the basic blocks dominated by edge E and put them into array BBS, that will be allocated large enough to contain them. - The number of basic blocks in the path is returned. */ + E->dest must have exactly one predecessor for this to work (it is + easy to achieve and we do not put it here because we do not want to + alter anything by this function). The number of basic blocks in the + path is returned. */ static int find_path (e, doms, bbs) edge e; dominance_info doms; basic_block **bbs; { - edge ae = NULL; struct rpe_data rpe; if (e->dest->pred->pred_next) - { - for (ae = e->dest->pred; ae; ae = ae->pred_next) - if (ae != e && !dominated_by_p (doms, ae->src, e->dest)) - break; - } - if (ae) - { - /* The path is formed just by the edge. */ - *bbs = NULL; - return 0; - } + abort (); /* Find bbs in the path. */ rpe.dom = e->dest; @@ -231,7 +224,7 @@ fix_bb_placements (loops, from) /* Prevent us from going out of the base_loop. */ SET_BIT (in_queue, base_loop->header->index); - queue = xcalloc (base_loop->num_nodes + 1, sizeof (basic_block)); + queue = xmalloc ((base_loop->num_nodes + 1) * sizeof (basic_block)); qtop = queue + base_loop->num_nodes + 1; qbeg = queue; qend = queue + 1; @@ -296,6 +289,75 @@ fix_bb_placements (loops, from) free (queue); } +/* Basic block from has lost one or more of its predecessors, so it might + mo longer be part irreducible loop. Fix it and proceed recursively + for its successors if needed. */ +static void +fix_irreducible_loops (from) + basic_block from; +{ + basic_block bb; + basic_block *stack; + int stack_top; + sbitmap on_stack; + edge *edges, e; + unsigned n_edges, i; + + if (!(from->flags & BB_IRREDUCIBLE_LOOP)) + return; + + on_stack = sbitmap_alloc (last_basic_block); + sbitmap_zero (on_stack); + SET_BIT (on_stack, from->index); + stack = xmalloc (from->loop_father->num_nodes * sizeof (basic_block)); + stack[0] = from; + stack_top = 1; + + while (stack_top) + { + bb = stack[--stack_top]; + RESET_BIT (on_stack, bb->index); + + for (e = bb->pred; e; e = e->pred_next) + if (e->flags & EDGE_IRREDUCIBLE_LOOP) + break; + if (e) + continue; + + bb->flags &= ~BB_IRREDUCIBLE_LOOP; + if (bb->loop_father->header == bb) + edges = get_loop_exit_edges (bb->loop_father, &n_edges); + else + { + n_edges = 0; + for (e = bb->succ; e; e = e->succ_next) + n_edges++; + edges = xmalloc (n_edges * sizeof (edge)); + n_edges = 0; + for (e = bb->succ; e; e = e->succ_next) + edges[n_edges++] = e; + } + + for (i = 0; i < n_edges; i++) + if (e->flags & EDGE_IRREDUCIBLE_LOOP) + { + if (!flow_bb_inside_loop_p (from->loop_father, e->dest)) + continue; + + e->flags &= ~EDGE_IRREDUCIBLE_LOOP; + if (TEST_BIT (on_stack, e->dest->index)) + continue; + + SET_BIT (on_stack, e->dest->index); + stack[stack_top++] = e->dest; + } + free (edges); + } + + free (on_stack); + free (stack); +} + /* Removes path beginning at edge E, i.e. remove basic blocks dominated by E and update loop structure stored in LOOPS and dominators. Return true if we were able to remove the path, false otherwise (and nothing is affected @@ -310,7 +372,26 @@ remove_path (loops, e) int i, nrem, n_bord_bbs, n_dom_bbs; sbitmap seen; - /* First identify the path. */ + if (!loop_delete_branch_edge (e, 0)) + return false; + + /* We need to check whether basic blocks are dominated by the edge + e, but we only have basic block dominators. This is easy to + fix -- when e->dest has exactly one predecessor, this corresponds + to blocks dominated by e->dest, if not, split the edge. */ + if (e->dest->pred->pred_next) + e = loop_split_edge_with (e, NULL_RTX, loops)->pred; + + /* It may happen that by removing path we remove one or more loops + we belong to. In this case first unloop the loops, then proceed + normally. We may assume that e->dest is not a header of any loop, + as it now has exactly one predecessor. */ + while (e->src->loop_father->outer + && dominated_by_p (loops->cfg.dom, + e->src->loop_father->latch, e->dest)) + unloop (loops, e->src->loop_father); + + /* Identify the path. */ nrem = find_path (e, loops->cfg.dom, &rem_bbs); n_bord_bbs = 0; @@ -321,31 +402,21 @@ remove_path (loops, e) /* Find "border" hexes -- i.e. those with predecessor in removed path. */ for (i = 0; i < nrem; i++) SET_BIT (seen, rem_bbs[i]->index); - if (nrem) + for (i = 0; i < nrem; i++) { - for (i = 0; i < nrem; i++) - { - bb = rem_bbs[i]; - for (ae = rem_bbs[i]->succ; ae; ae = ae->succ_next) - if (ae->dest != EXIT_BLOCK_PTR && !TEST_BIT (seen, ae->dest->index)) - { - SET_BIT (seen, ae->dest->index); - bord_bbs[n_bord_bbs++] = ae->dest; - } - } + bb = rem_bbs[i]; + for (ae = rem_bbs[i]->succ; ae; ae = ae->succ_next) + if (ae->dest != EXIT_BLOCK_PTR && !TEST_BIT (seen, ae->dest->index)) + { + SET_BIT (seen, ae->dest->index); + bord_bbs[n_bord_bbs++] = ae->dest; + } } - else if (e->dest != EXIT_BLOCK_PTR) - bord_bbs[n_bord_bbs++] = e->dest; /* Remove the path. */ from = e->src; - if (!loop_delete_branch_edge (e)) - { - free (rem_bbs); - free (bord_bbs); - free (seen); - return false; - } + if (!loop_delete_branch_edge (e, 1)) + abort (); dom_bbs = xcalloc (n_basic_blocks, sizeof (basic_block)); /* Cancel loops contained in the path. */ @@ -356,7 +427,7 @@ remove_path (loops, e) remove_bbs (loops->cfg.dom, rem_bbs, nrem); free (rem_bbs); - /* Find blocks with whose dominators may be affected. */ + /* Find blocks whose dominators may be affected. */ n_dom_bbs = 0; sbitmap_zero (seen); for (i = 0; i < n_bord_bbs; i++) @@ -376,13 +447,18 @@ remove_path (loops, e) free(ldom); } - free (bord_bbs); free (seen); /* Recount dominators. */ iterate_fix_dominators (loops->cfg.dom, dom_bbs, n_dom_bbs); free (dom_bbs); + /* These blocks have lost some predecessor(s), thus their irreducible + status could be changed. */ + for (i = 0; i < n_bord_bbs; i++) + fix_irreducible_loops (bord_bbs[i]); + free (bord_bbs); + /* Fix placements of basic blocks inside loops and the placement of loops in the loop tree. */ fix_bb_placements (loops, from); @@ -557,6 +633,65 @@ loopify (loops, latch_edge, header_edge, switch_bb) return loop; } +/* Remove the latch edge of a LOOP and update LOOPS tree to indicate that + the LOOP was removed. After this function, original loop latch will + have no successor, which caller is expected to fix somehow. */ +void +unloop (loops, loop) + struct loops *loops; + struct loop *loop; +{ + basic_block *body; + struct loop *ploop; + unsigned i, n; + basic_block latch = loop->latch; + edge *edges; + unsigned n_edges; + + /* This is relatively straigtforward. The dominators are unchanged, as + loop header dominates loop latch, so the only thing we have to care of + is the placement of loops and basic blocks inside the loop tree. We + move them all to the loop->outer, and then let fix_bb_placements do + its work. */ + + body = get_loop_body (loop); + edges = get_loop_exit_edges (loop, &n_edges); + n = loop->num_nodes; + for (i = 0; i < n; i++) + if (body[i]->loop_father == loop) + { + remove_bb_from_loops (body[i]); + add_bb_to_loop (body[i], loop->outer); + } + free(body); + + while (loop->inner) + { + ploop = loop->inner; + flow_loop_tree_node_remove (ploop); + flow_loop_tree_node_add (loop->outer, ploop); + } + + /* Remove the loop and free its data. */ + flow_loop_tree_node_remove (loop); + loops->parray[loop->num] = NULL; + flow_loop_free (loop); + + remove_edge (latch->succ); + fix_bb_placements (loops, latch); + + /* If the loop was inside an irreducible region, we would have to somehow + update the irreducible marks inside its body. While it is certainly + possible to do, it is a bit complicated and this situation should be + very rare, so we just remark all loops in this case. */ + for (i = 0; i < n_edges; i++) + if (edges[i]->flags & EDGE_IRREDUCIBLE_LOOP) + break; + if (i != n_edges) + mark_irreducible_loops (loops); + free (edges); +} + /* Fix placement of LOOP inside loop tree, i.e. find the innermost superloop FATHER of LOOP such that all of the edges comming out of LOOP belong to FATHER, and set it as outer loop of LOOP. Return 1 if placement of @@ -696,16 +831,21 @@ loop_redirect_edge (e, dest) cfg_layout_redirect_edge (e, dest); } -/* Deletes edge E from a branch if possible. */ +/* Deletes edge E from a branch if possible. Unless REALLY_DELETE is set, + just test whether it is possible to remove the edge. */ static bool -loop_delete_branch_edge (e) +loop_delete_branch_edge (e, really_delete) edge e; + int really_delete; { basic_block src = e->src; + int irr; + edge snd; if (src->succ->succ_next) { basic_block newdest; + /* Cannot handle more than two exit edges. */ if (src->succ->succ_next->succ_next) return false; @@ -713,12 +853,24 @@ loop_delete_branch_edge (e) if (!any_condjump_p (src->end)) return false; - newdest = (e == src->succ - ? src->succ->succ_next->dest : src->succ->dest); + snd = e == src->succ ? src->succ->succ_next : src->succ; + newdest = snd->dest; if (newdest == EXIT_BLOCK_PTR) return false; - return cfg_layout_redirect_edge (e, newdest); + /* Hopefully the above conditions should suffice. */ + if (!really_delete) + return true; + + /* Redirecting behaves wrongly wrto this flag. */ + irr = snd->flags & EDGE_IRREDUCIBLE_LOOP; + + if (!cfg_layout_redirect_edge (e, newdest)) + return false; + src->succ->flags &= ~EDGE_IRREDUCIBLE_LOOP; + src->succ->flags |= irr; + + return true; } else { @@ -833,6 +985,11 @@ copy_bbs (bbs, n, entry, latch_edge, new_bbs, loops, header_edge, copy_header_ed /* Leads to copied loop and it is not latch edge, redirect it. */ if (bb != header) loop_redirect_edge (e, new_bb); + + if (add_irreducible_flag + && (bb->loop_father == header->loop_father + || RBI (src)->original->loop_father == header->loop_father)) + e->flags |= EDGE_IRREDUCIBLE_LOOP; } } @@ -1005,7 +1162,7 @@ duplicate_loop_to_header_edge (loop, e, loops, ndupl, wont_exit, orig, } } - add_irreducible_flag = !is_latch && (e->src->flags & BB_IRREDUCIBLE_LOOP); + add_irreducible_flag = !is_latch && (e->flags & EDGE_IRREDUCIBLE_LOOP); /* Find edge from latch. */ latch_edge = loop_latch_edge (loop); @@ -1355,17 +1512,15 @@ loop_split_edge_with (e, insns, loops) 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; new_e->count = e->count; + if (e->flags & EDGE_IRREDUCIBLE_LOOP) + { + new_bb->flags |= BB_IRREDUCIBLE_LOOP; + new_e->flags |= EDGE_IRREDUCIBLE_LOOP; + } new_bb->count = e->count; new_bb->frequency = EDGE_FREQUENCY (e); diff --git a/gcc/cfgrtl.c b/gcc/cfgrtl.c index 77290a9..31f7110 100644 --- a/gcc/cfgrtl.c +++ b/gcc/cfgrtl.c @@ -1594,11 +1594,13 @@ debug_bb (bb) dump_bb (bb, stderr); } -void +basic_block debug_bb_n (n) int n; { - dump_bb (BASIC_BLOCK (n), stderr); + basic_block bb = BASIC_BLOCK (n); + dump_bb (bb, stderr); + return bb; } /* Like print_rtl, but also print out live information for the start of each @@ -1866,7 +1868,7 @@ verify_flow_info () if (e->flags & EDGE_FALLTHRU) n_fallthru++; - if ((e->flags & ~(EDGE_DFS_BACK | EDGE_CAN_FALLTHRU)) == 0) + if ((e->flags & ~(EDGE_DFS_BACK | EDGE_CAN_FALLTHRU | EDGE_IRREDUCIBLE_LOOP)) == 0) n_branch++; if (e->flags & EDGE_ABNORMAL_CALL) diff --git a/gcc/loop-unroll.c b/gcc/loop-unroll.c index 67eb8da..6f945a2 100644 --- a/gcc/loop-unroll.c +++ b/gcc/loop-unroll.c @@ -180,25 +180,6 @@ peel_loops_completely (loops, flags) fprintf (rtl_dump_file, ";; Considering loop %d for complete peeling\n", loop->num); - /* Do not peel cold areas. */ - if (!maybe_hot_bb_p (loop->header)) - { - if (rtl_dump_file) - fprintf (rtl_dump_file, ";; Not considering loop, cold area\n"); - loop = next; - continue; - } - - /* Can the loop be manipulated? */ - if (!can_duplicate_loop_p (loop)) - { - if (rtl_dump_file) - fprintf (rtl_dump_file, - ";; Not considering loop, cannot duplicate\n"); - loop = next; - continue; - } - loop->ninsns = num_loop_insns (loop); decide_peel_once_rolling (loops, loop, flags); @@ -348,6 +329,23 @@ decide_peel_completely (loops, loop, flags) return; } + /* Do not peel cold areas. */ + if (!maybe_hot_bb_p (loop->header)) + { + if (rtl_dump_file) + fprintf (rtl_dump_file, ";; Not considering loop, cold area\n"); + return; + } + + /* Can the loop be manipulated? */ + if (!can_duplicate_loop_p (loop)) + { + if (rtl_dump_file) + fprintf (rtl_dump_file, + ";; Not considering loop, cannot duplicate\n"); + return; + } + /* npeel = number of iterations to peel. */ npeel = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS) / loop->ninsns; if (npeel > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES)) @@ -411,45 +409,40 @@ peel_loop_completely (loops, loop) { sbitmap wont_exit; unsigned HOST_WIDE_INT npeel; - edge e; unsigned n_remove_edges, i; edge *remove_edges; struct loop_desc *desc = &loop->desc; npeel = desc->niter; - wont_exit = sbitmap_alloc (npeel + 2); - sbitmap_ones (wont_exit); - RESET_BIT (wont_exit, 0); - RESET_BIT (wont_exit, npeel + 1); - if (desc->may_be_zero) - RESET_BIT (wont_exit, 1); - - remove_edges = xcalloc (npeel, sizeof (edge)); - n_remove_edges = 0; - - if (!duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop), - loops, npeel + 1, - wont_exit, desc->out_edge, remove_edges, &n_remove_edges, - DLTHE_FLAG_UPDATE_FREQ)) - abort (); + if (npeel) + { + wont_exit = sbitmap_alloc (npeel + 1); + sbitmap_ones (wont_exit); + RESET_BIT (wont_exit, 0); + if (desc->may_be_zero) + RESET_BIT (wont_exit, 1); - free (wont_exit); + remove_edges = xcalloc (npeel, sizeof (edge)); + n_remove_edges = 0; - /* Remove the exit edges. */ - for (i = 0; i < n_remove_edges; i++) - remove_path (loops, remove_edges[i]); - free (remove_edges); + if (!duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop), + loops, npeel, + wont_exit, desc->out_edge, remove_edges, &n_remove_edges, + DLTHE_FLAG_UPDATE_FREQ)) + abort (); - /* Now remove the loop. */ - for (e = RBI (desc->in_edge->src)->copy->succ; - e && e->dest != RBI (desc->in_edge->dest)->copy; - e = e->succ_next); + free (wont_exit); - if (!e) - abort (); + /* Remove the exit edges. */ + for (i = 0; i < n_remove_edges; i++) + remove_path (loops, remove_edges[i]); + free (remove_edges); + } - remove_path (loops, e); + /* Now remove the unreachable part of the last iteration and cancel + the loop. */ + remove_path (loops, desc->in_edge); if (rtl_dump_file) fprintf (rtl_dump_file, ";; Peeled loop completely, %d times\n", (int) npeel); diff --git a/gcc/loop-unswitch.c b/gcc/loop-unswitch.c index 8d6654c..fdce1eb 100644 --- a/gcc/loop-unswitch.c +++ b/gcc/loop-unswitch.c @@ -335,7 +335,7 @@ unswitch_loop (loops, loop, unswitch_on) struct loop *loop; basic_block unswitch_on; { - edge entry, e, latch_edge; + edge entry, latch_edge; basic_block switch_bb, unswitch_on_alt, src; struct loop *nloop; sbitmap zero_bitmap; @@ -366,15 +366,15 @@ unswitch_loop (loops, loop, unswitch_on) /* Make a copy. */ src = entry->src; - irred_flag = src->flags & BB_IRREDUCIBLE_LOOP; - src->flags &= ~BB_IRREDUCIBLE_LOOP; + irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP; + entry->flags &= ~EDGE_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; + entry->flags |= irred_flag; /* Record the block with condition we unswitch on. */ unswitch_on_alt = RBI (unswitch_on)->copy; @@ -382,8 +382,18 @@ unswitch_loop (loops, loop, unswitch_on) /* Make a copy of the block containing the condition; we will use it as switch to decide which loop we want to use. */ switch_bb = cfg_layout_duplicate_bb (unswitch_on, NULL); - switch_bb->flags &= ~BB_IRREDUCIBLE_LOOP; - switch_bb->flags |= irred_flag; + if (irred_flag) + { + switch_bb->flags |= BB_IRREDUCIBLE_LOOP; + switch_bb->succ->flags |= EDGE_IRREDUCIBLE_LOOP; + switch_bb->succ->succ_next->flags |= EDGE_IRREDUCIBLE_LOOP; + } + else + { + switch_bb->flags &= ~BB_IRREDUCIBLE_LOOP; + switch_bb->succ->flags &= ~EDGE_IRREDUCIBLE_LOOP; + switch_bb->succ->succ_next->flags &= ~EDGE_IRREDUCIBLE_LOOP; + } add_to_dominance_info (loops->cfg.dom, switch_bb); RBI (unswitch_on)->copy = unswitch_on_alt; @@ -396,10 +406,6 @@ unswitch_loop (loops, loop, unswitch_on) /* Remove branches that are now unreachable in new loops. We rely on the fact that cfg_layout_duplicate_bb reverses list of edges. */ - for (e = unswitch_on->succ->succ_next->dest->pred; e; e = e->pred_next) - if (e->src != unswitch_on && - !dominated_by_p (loops->cfg.dom, e->src, e->dest)) - break; remove_path (loops, unswitch_on->succ); remove_path (loops, unswitch_on_alt->succ); -- 2.7.4