diff options
| -rw-r--r-- | gcc/ChangeLog | 24 | ||||
| -rw-r--r-- | gcc/Makefile.in | 3 | ||||
| -rw-r--r-- | gcc/basic-block.h | 8 | ||||
| -rw-r--r-- | gcc/bb-reorder.c | 34 | ||||
| -rw-r--r-- | gcc/cfganal.c | 79 | ||||
| -rw-r--r-- | gcc/cfgcleanup.c | 6 | ||||
| -rw-r--r-- | gcc/cfglayout.c | 5 | ||||
| -rw-r--r-- | gcc/cfgrtl.c | 8 | ||||
| -rw-r--r-- | gcc/tree-cfg.c | 78 | ||||
| -rw-r--r-- | gcc/tree-flow.h | 1 |
10 files changed, 137 insertions, 109 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 03259005152..706fb616160 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,27 @@ +2004-09-19 Steven Bosscher <stevenb@suse.de> + + * basic-block.h (struct edge_def): Remove crossing_edge. + (EDGE_CROSSING): New define. + (EDGE_ALL_FLAGS): Update. + * bb-reorder.c (find_traces_1_round, better_edge_p, + find_rarely_executed_basic_blocks_and_cr, fix_up_fall_thru_edges, + find_jump_block, fix_crossing_conditional_branches, + fix_crossing_unconditional_branches, add_reg_crossing_jump_notes): + Replace all occurences of crossing_edge with an edge flag check + or set/reset. + * cfgcleanup.c (try_simplify_condjump, try_forward_edges, + try_crossjump_bb): Likewise. + * cfglayout.c (fixup_reorder_chain): Likewise. + * cfgrtl.c (force_nonfallthru_and_redirect, + commit_one_edge_insertion): Likewise. + + * Makefile.in (cfganal.o): Depend on TIMEVAR_H. + * tree-flow.h (compute_dominance_frontiers): Move prototype... + * basic-block.h: ...here. + * tree-cfg.c (compute_dominance_frontiers_1, + compute_dominance_frontiers): Move from here... + * cfganal.c: ...to here. Include timevar.h. + 2004-08-18 James E Wilson <wilson@specifixinc.com> * config/mips/mips.h (ASM_SPEC): In comment, change -meabi= to -mabi=. diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 75999212e27..b7fd64ff2ed 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1974,7 +1974,8 @@ cfgrtl.o : cfgrtl.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) $(FLAGS insn-config.h $(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h toplev.h $(RECOG_H) \ function.h except.h $(GGC_H) $(TM_P_H) insn-config.h $(EXPR_H) cfganal.o : cfganal.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \ - $(BASIC_BLOCK_H) hard-reg-set.h insn-config.h $(RECOG_H) $(GGC_H) $(TM_P_H) + $(BASIC_BLOCK_H) hard-reg-set.h insn-config.h $(RECOG_H) $(GGC_H) $(TM_P_H) \ + $(TIMEVAR_H) cfgbuild.o : cfgbuild.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) $(FLAGS_H) \ insn-config.h $(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h toplev.h $(RECOG_H) \ function.h except.h $(GGC_H) diff --git a/gcc/basic-block.h b/gcc/basic-block.h index 76f13687a52..b5f045ed921 100644 --- a/gcc/basic-block.h +++ b/gcc/basic-block.h @@ -149,8 +149,6 @@ struct edge_def GTY((chain_next ("%h.pred_next"))) int probability; /* biased by REG_BR_PROB_BASE */ gcov_type count; /* Expected number of executions calculated in profile.c */ - bool crossing_edge; /* Crosses between hot and cold sections, when - we do partitioning. */ }; typedef struct edge_def *edge; @@ -174,7 +172,10 @@ typedef struct edge_def *edge; predicate is zero. */ #define EDGE_EXECUTABLE 4096 /* Edge is executable. Only valid during SSA-CCP. */ -#define EDGE_ALL_FLAGS 8191 +#define EDGE_CROSSING 8192 /* Edge crosses between hot + and cold sections, when we + do partitioning. */ +#define EDGE_ALL_FLAGS 16383 #define EDGE_COMPLEX (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_EH) @@ -444,6 +445,7 @@ extern void flow_preorder_transversal_compute (int *); extern int dfs_enumerate_from (basic_block, int, bool (*)(basic_block, void *), basic_block *, int, void *); +extern void compute_dominance_frontiers (bitmap *); extern void dump_edge_info (FILE *, edge, int); extern void brief_dump_cfg (FILE *); extern void clear_edges (void); diff --git a/gcc/bb-reorder.c b/gcc/bb-reorder.c index 32234b103f5..f4c486009a5 100644 --- a/gcc/bb-reorder.c +++ b/gcc/bb-reorder.c @@ -688,7 +688,7 @@ find_traces_1_round (int branch_th, int exec_th, gcov_type count_th, && !(e->flags & EDGE_COMPLEX) && !e->dest->rbi->visited && !e->dest->pred->pred_next - && !e->crossing_edge + && !(e->flags & EDGE_CROSSING) && e->dest->succ && (e->dest->succ->flags & EDGE_CAN_FALLTHRU) && !(e->dest->succ->flags & EDGE_COMPLEX) @@ -880,8 +880,8 @@ better_edge_p (basic_block bb, edge e, int prob, int freq, int best_prob, if (!is_better_edge && flag_reorder_blocks_and_partition && cur_best_edge - && cur_best_edge->crossing_edge - && !e->crossing_edge) + && (cur_best_edge->flags & EDGE_CROSSING) + && !(e->flags & EDGE_CROSSING)) is_better_edge = true; return is_better_edge; @@ -1304,7 +1304,7 @@ find_rarely_executed_basic_blocks_and_crossing_edges (edge *crossing_edges, && e->dest != EXIT_BLOCK_PTR && e->src->partition != e->dest->partition) { - e->crossing_edge = true; + e->flags |= EDGE_CROSSING; if (i == *max_idx) { *max_idx *= 2; @@ -1314,7 +1314,7 @@ find_rarely_executed_basic_blocks_and_crossing_edges (edge *crossing_edges, crossing_edges[i++] = e; } else - e->crossing_edge = false; + e->flags &= ~EDGE_CROSSING; } } *n_crossing_edges = i; @@ -1472,7 +1472,7 @@ fix_up_fall_thru_edges (void) { /* Check to see if the fall-thru edge is a crossing edge. */ - if (fall_thru->crossing_edge) + if (fall_thru->flags & EDGE_CROSSING) { /* The fall_thru edge crosses; now check the cond jump edge, if it exists. */ @@ -1485,7 +1485,7 @@ fix_up_fall_thru_edges (void) if (cond_jump) { - if (!cond_jump->crossing_edge) + if (!(cond_jump->flags & EDGE_CROSSING)) cond_jump_crosses = false; /* We know the fall-thru edge crosses; if the cond @@ -1513,8 +1513,8 @@ fix_up_fall_thru_edges (void) e = fall_thru; fall_thru = cond_jump; cond_jump = e; - cond_jump->crossing_edge = true; - fall_thru->crossing_edge = false; + cond_jump->flags |= EDGE_CROSSING; + fall_thru->flags &= ~EDGE_CROSSING; } } } @@ -1537,7 +1537,7 @@ fix_up_fall_thru_edges (void) partition as bb it's falling through from. */ new_bb->partition = cur_bb->partition; - new_bb->succ->crossing_edge = true; + new_bb->succ->flags |= EDGE_CROSSING; } /* Add barrier after new jump */ @@ -1574,7 +1574,7 @@ find_jump_block (basic_block jump_dest) rtx insn; for (e = jump_dest->pred; e; e = e->pred_next) - if (e->crossing_edge) + if (e->flags & EDGE_CROSSING) { basic_block src = e->src; @@ -1643,9 +1643,9 @@ fix_crossing_conditional_branches (void) /* We already took care of fall-through edges, so only one successor can be a crossing edge. */ - if (succ1 && succ1->crossing_edge) + if (succ1 && (succ1->flags & EDGE_CROSSING)) crossing_edge = succ1; - else if (succ2 && succ2->crossing_edge) + else if (succ2 && (succ2->flags & EDGE_CROSSING)) crossing_edge = succ2; if (crossing_edge) @@ -1758,8 +1758,8 @@ fix_crossing_conditional_branches (void) else new_edge = new_bb->succ; - crossing_edge->crossing_edge = false; - new_edge->crossing_edge = true; + crossing_edge->flags &= ~EDGE_CROSSING; + new_edge->flags |= EDGE_CROSSING; } } } @@ -1790,7 +1790,7 @@ fix_crossing_unconditional_branches (void) this point, no crossing jumps should be conditional. */ if (JUMP_P (last_insn) - && succ->crossing_edge) + && (succ->flags & EDGE_CROSSING)) { rtx label2, table; @@ -1858,7 +1858,7 @@ add_reg_crossing_jump_notes (void) FOR_EACH_BB (bb) for (e = bb->succ; e; e = e->succ_next) - if (e->crossing_edge + if ((e->flags & EDGE_CROSSING) && JUMP_P (BB_END (e->src))) REG_NOTES (BB_END (e->src)) = gen_rtx_EXPR_LIST (REG_CROSSING_JUMP, NULL_RTX, diff --git a/gcc/cfganal.c b/gcc/cfganal.c index db0238c68eb..58745d0ff09 100644 --- a/gcc/cfganal.c +++ b/gcc/cfganal.c @@ -31,6 +31,7 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "recog.h" #include "toplev.h" #include "tm_p.h" +#include "timevar.h" /* Store the data structures necessary for depth-first search. */ struct depth_first_search_dsS { @@ -1041,3 +1042,81 @@ dfs_enumerate_from (basic_block bb, int reverse, rslt[sp]->flags &= ~BB_VISITED; return tv; } + + +/* Computing the Dominance Frontier: + + As described in Morgan, section 3.5, this may be done simply by + walking the dominator tree bottom-up, computing the frontier for + the children before the parent. When considering a block B, + there are two cases: + + (1) A flow graph edge leaving B that does not lead to a child + of B in the dominator tree must be a block that is either equal + to B or not dominated by B. Such blocks belong in the frontier + of B. + + (2) Consider a block X in the frontier of one of the children C + of B. If X is not equal to B and is not dominated by B, it + is in the frontier of B. */ + +static void +compute_dominance_frontiers_1 (bitmap *frontiers, basic_block bb, sbitmap done) +{ + edge e; + basic_block c; + + SET_BIT (done, bb->index); + + /* Do the frontier of the children first. Not all children in the + dominator tree (blocks dominated by this one) are children in the + CFG, so check all blocks. */ + for (c = first_dom_son (CDI_DOMINATORS, bb); + c; + c = next_dom_son (CDI_DOMINATORS, c)) + { + if (! TEST_BIT (done, c->index)) + compute_dominance_frontiers_1 (frontiers, c, done); + } + + /* Find blocks conforming to rule (1) above. */ + for (e = bb->succ; e; e = e->succ_next) + { + if (e->dest == EXIT_BLOCK_PTR) + continue; + if (get_immediate_dominator (CDI_DOMINATORS, e->dest) != bb) + bitmap_set_bit (frontiers[bb->index], e->dest->index); + } + + /* Find blocks conforming to rule (2). */ + for (c = first_dom_son (CDI_DOMINATORS, bb); + c; + c = next_dom_son (CDI_DOMINATORS, c)) + { + int x; + + EXECUTE_IF_SET_IN_BITMAP (frontiers[c->index], 0, x, + { + if (get_immediate_dominator (CDI_DOMINATORS, BASIC_BLOCK (x)) != bb) + bitmap_set_bit (frontiers[bb->index], x); + }); + } +} + + +void +compute_dominance_frontiers (bitmap *frontiers) +{ + sbitmap done = sbitmap_alloc (last_basic_block); + + timevar_push (TV_DOM_FRONTIERS); + + sbitmap_zero (done); + + compute_dominance_frontiers_1 (frontiers, ENTRY_BLOCK_PTR->succ->dest, done); + + sbitmap_free (done); + + timevar_pop (TV_DOM_FRONTIERS); +} + diff --git a/gcc/cfgcleanup.c b/gcc/cfgcleanup.c index d13e6be9bab..8080c663bc7 100644 --- a/gcc/cfgcleanup.c +++ b/gcc/cfgcleanup.c @@ -154,7 +154,7 @@ try_simplify_condjump (basic_block cbranch_block) if (flag_reorder_blocks_and_partition && (jump_block->partition != jump_dest_block->partition - || cbranch_jump_edge->crossing_edge)) + || (cbranch_jump_edge->flags & EDGE_CROSSING))) return false; /* The conditional branch must target the block after the @@ -461,7 +461,7 @@ try_forward_edges (int mode, basic_block b) may_thread |= target->flags & BB_DIRTY; if (FORWARDER_BLOCK_P (target) - && !target->succ->crossing_edge + && !(target->succ->flags & EDGE_CROSSING) && target->succ->dest != EXIT_BLOCK_PTR) { /* Bypass trivial infinite loops. */ @@ -1674,7 +1674,7 @@ try_crossjump_bb (int mode, basic_block bb) if (flag_reorder_blocks_and_partition && (bb->pred->src->partition != bb->pred->pred_next->src->partition - || bb->pred->crossing_edge)) + || (bb->pred->flags & EDGE_CROSSING))) return false; /* It is always cheapest to redirect a block that ends in a branch to diff --git a/gcc/cfglayout.c b/gcc/cfglayout.c index 0cf7d8e5131..e99ed6484da 100644 --- a/gcc/cfglayout.c +++ b/gcc/cfglayout.c @@ -723,7 +723,8 @@ fixup_reorder_chain (void) /* If the "jumping" edge is a crossing edge, and the fall through edge is non-crossing, leave things as they are. */ - else if (e_taken->crossing_edge && !e_fall->crossing_edge) + else if ((e_taken->flags & EDGE_CROSSING) + && !(e_fall->flags & EDGE_CROSSING)) continue; /* Otherwise we can try to invert the jump. This will @@ -814,7 +815,7 @@ fixup_reorder_chain (void) } if (JUMP_P (BB_END (bb)) && !any_condjump_p (BB_END (bb)) - && bb->succ->crossing_edge ) + && (bb->succ->flags & EDGE_CROSSING)) REG_NOTES (BB_END (bb)) = gen_rtx_EXPR_LIST (REG_CROSSING_JUMP, NULL_RTX, REG_NOTES (BB_END (bb))); } diff --git a/gcc/cfgrtl.c b/gcc/cfgrtl.c index f3618f07c97..7295ead57d6 100644 --- a/gcc/cfgrtl.c +++ b/gcc/cfgrtl.c @@ -1114,7 +1114,7 @@ force_nonfallthru_and_redirect (edge e, basic_block target) } if (JUMP_P (BB_END (jump_block)) && !any_condjump_p (BB_END (jump_block)) - && jump_block->succ->crossing_edge ) + && (jump_block->succ->flags & EDGE_CROSSING)) REG_NOTES (BB_END (jump_block)) = gen_rtx_EXPR_LIST (REG_CROSSING_JUMP, NULL_RTX, REG_NOTES (BB_END (jump_block))); @@ -1602,7 +1602,7 @@ commit_one_edge_insertion (edge e, int watch_calls) && targetm.have_named_sections && e->src != ENTRY_BLOCK_PTR && e->src->partition == COLD_PARTITION - && !e->crossing_edge) + && !(e->flags & EDGE_CROSSING)) { rtx bb_note, new_note, cur_insn; @@ -1621,7 +1621,7 @@ commit_one_edge_insertion (edge e, int watch_calls) NOTE_BASIC_BLOCK (new_note) = bb; if (JUMP_P (BB_END (bb)) && !any_condjump_p (BB_END (bb)) - && bb->succ->crossing_edge ) + && (bb->succ->flags & EDGE_CROSSING)) REG_NOTES (BB_END (bb)) = gen_rtx_EXPR_LIST (REG_CROSSING_JUMP, NULL_RTX, REG_NOTES (BB_END (bb))); if (after == bb_note) @@ -1986,7 +1986,7 @@ rtl_verify_flow_info_1 (void) if (e->flags & EDGE_FALLTHRU) { n_fallthru++, fallthru = e; - if (e->crossing_edge + if ((e->flags & EDGE_CROSSING) || (e->src->partition != e->dest->partition && e->src != ENTRY_BLOCK_PTR && e->dest != EXIT_BLOCK_PTR)) diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c index 33c8325041b..621ea576fa7 100644 --- a/gcc/tree-cfg.c +++ b/gcc/tree-cfg.c @@ -2171,84 +2171,6 @@ phi_alternatives_equal (basic_block dest, edge e1, edge e2) } -/* Computing the Dominance Frontier: - - As described in Morgan, section 3.5, this may be done simply by - walking the dominator tree bottom-up, computing the frontier for - the children before the parent. When considering a block B, - there are two cases: - - (1) A flow graph edge leaving B that does not lead to a child - of B in the dominator tree must be a block that is either equal - to B or not dominated by B. Such blocks belong in the frontier - of B. - - (2) Consider a block X in the frontier of one of the children C - of B. If X is not equal to B and is not dominated by B, it - is in the frontier of B. */ - -static void -compute_dominance_frontiers_1 (bitmap *frontiers, basic_block bb, sbitmap done) -{ - edge e; - basic_block c; - - SET_BIT (done, bb->index); - - /* Do the frontier of the children first. Not all children in the - dominator tree (blocks dominated by this one) are children in the - CFG, so check all blocks. */ - for (c = first_dom_son (CDI_DOMINATORS, bb); - c; - c = next_dom_son (CDI_DOMINATORS, c)) - { - if (! TEST_BIT (done, c->index)) - compute_dominance_frontiers_1 (frontiers, c, done); - } - - /* Find blocks conforming to rule (1) above. */ - for (e = bb->succ; e; e = e->succ_next) - { - if (e->dest == EXIT_BLOCK_PTR) - continue; - if (get_immediate_dominator (CDI_DOMINATORS, e->dest) != bb) - bitmap_set_bit (frontiers[bb->index], e->dest->index); - } - - /* Find blocks conforming to rule (2). */ - for (c = first_dom_son (CDI_DOMINATORS, bb); - c; - c = next_dom_son (CDI_DOMINATORS, c)) - { - int x; - - EXECUTE_IF_SET_IN_BITMAP (frontiers[c->index], 0, x, - { - if (get_immediate_dominator (CDI_DOMINATORS, BASIC_BLOCK (x)) != bb) - bitmap_set_bit (frontiers[bb->index], x); - }); - } -} - - -void -compute_dominance_frontiers (bitmap *frontiers) -{ - sbitmap done = sbitmap_alloc (last_basic_block); - - timevar_push (TV_DOM_FRONTIERS); - - sbitmap_zero (done); - - compute_dominance_frontiers_1 (frontiers, ENTRY_BLOCK_PTR->succ->dest, done); - - sbitmap_free (done); - - timevar_pop (TV_DOM_FRONTIERS); -} - - - /*--------------------------------------------------------------------------- Debugging functions ---------------------------------------------------------------------------*/ diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h index ca5897afa49..7d26c5efaa6 100644 --- a/gcc/tree-flow.h +++ b/gcc/tree-flow.h @@ -489,7 +489,6 @@ extern void bsi_insert_on_edge (edge, tree); extern void bsi_commit_edge_inserts (int *); extern void notice_special_calls (tree); extern void clear_special_calls (void); -extern void compute_dominance_frontiers (bitmap *); extern void verify_stmts (void); extern tree tree_block_label (basic_block bb); extern void extract_true_false_edges_from_block (basic_block, edge *, edge *); |