From 5f0d23589fe634ef3b7986a5dc0e389abfe4c917 Mon Sep 17 00:00:00 2001 From: Richard Kenner Date: Mon, 24 Dec 2001 15:44:45 +0000 Subject: [PATCH] rtl.h (in_expr_list_p): New declaration. * rtl.h (in_expr_list_p): New declaration. * rtlanal.c (in_expr_list_p): New function. * cfgcleanup.c: Reformatting and minor code rearrangement. * cfglayout.c, cfgloop.c, cfgrtl.c: Likewise. From-SVN: r48304 --- gcc/ChangeLog | 7 + gcc/cfgcleanup.c | 141 +++++++++------ gcc/cfglayout.c | 271 +++++++++++++--------------- gcc/cfgloop.c | 204 ++++++++++----------- gcc/cfgrtl.c | 460 ++++++++++++++++++++++++----------------------- gcc/rtl.h | 1 + gcc/rtlanal.c | 18 ++ 7 files changed, 561 insertions(+), 541 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index c526245a109..b6772944d14 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,10 @@ +Mon Dec 24 10:24:59 2001 Richard Kenner + + * rtl.h (in_expr_list_p): New declaration. + * rtlanal.c (in_expr_list_p): New function. + * cfgcleanup.c: Reformatting and minor code rearrangement. + * cfglayout.c, cfgloop.c, cfgrtl.c: Likewise. + 2001-12-23 Richard Henderson PR c/5163: diff --git a/gcc/cfgcleanup.c b/gcc/cfgcleanup.c index abb0217711c..9933defe433 100644 --- a/gcc/cfgcleanup.c +++ b/gcc/cfgcleanup.c @@ -47,21 +47,23 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "obstack.h" /* cleanup_cfg maintains following flags for each basic block. */ -enum bb_flags { + +enum bb_flags +{ /* Set if life info needs to be recomputed for given BB. */ BB_UPDATE_LIFE = 1, /* Set if BB is the forwarder block to avoid too many forwarder_block_p calls. */ BB_FORWARDER_BLOCK = 2 - }; +}; -#define BB_FLAGS(bb) (enum bb_flags)(bb)->aux -#define BB_SET_FLAG(bb,flag) \ - (bb)->aux = (void *) (long) ((enum bb_flags)(bb)->aux | (flag)) -#define BB_CLEAR_FLAG(bb,flag) \ - (bb)->aux = (void *) (long) ((enum bb_flags)(bb)->aux & ~(flag)) +#define BB_FLAGS(BB) (enum bb_flags) (BB)->aux +#define BB_SET_FLAG(BB, FLAG) \ + (BB)->aux = (void *) (long) ((enum bb_flags) (BB)->aux | (FLAG)) +#define BB_CLEAR_FLAG(BB, FLAG) \ + (BB)->aux = (void *) (long) ((enum bb_flags) (BB)->aux & ~(FLAG)) -#define FORWARDER_BLOCK_P(bb) (BB_FLAGS(bb) & BB_FORWARDER_BLOCK) +#define FORWARDER_BLOCK_P(BB) (BB_FLAGS (BB) & BB_FORWARDER_BLOCK) static bool try_crossjump_to_edge PARAMS ((int, edge, edge)); static bool try_crossjump_bb PARAMS ((int, basic_block)); @@ -96,6 +98,7 @@ notice_new_block (bb) { if (!bb) return; + BB_SET_FLAG (bb, BB_UPDATE_LIFE); if (forwarder_block_p (bb)) BB_SET_FLAG (bb, BB_FORWARDER_BLOCK); @@ -183,6 +186,7 @@ try_simplify_condjump (cbranch_block) /* Attempt to prove that operation is NOOP using CSElib or mark the effect on register. Used by jump threading. */ + static bool mark_effect (exp, nonequal) rtx exp; @@ -196,6 +200,7 @@ mark_effect (exp, nonequal) if (REG_P (XEXP (exp, 0))) CLEAR_REGNO_REG_SET (nonequal, REGNO (XEXP (exp, 0))); return false; + case SET: if (rtx_equal_for_cselib_p (SET_DEST (exp), SET_SRC (exp))) return false; @@ -203,6 +208,7 @@ mark_effect (exp, nonequal) return true; SET_REGNO_REG_SET (nonequal, REGNO (SET_SRC (exp))); return false; + default: return false; } @@ -281,10 +287,11 @@ thread_jump (mode, e, b) nonequal = BITMAP_XMALLOC(); CLEAR_REG_SET (nonequal); + /* Now assume that we've continued by the edge E to B and continue processing as if it were same basic block. - Our goal is to prove that whole block is an NOOP. */ + for (insn = NEXT_INSN (b->head); insn != b->end && !failed; insn = NEXT_INSN (insn)) { @@ -300,6 +307,7 @@ thread_jump (mode, e, b) else failed |= mark_effect (pat, nonequal); } + cselib_process_insn (insn); } @@ -340,7 +348,7 @@ try_forward_edges (mode, b) bool changed = false; edge e, next, threaded_edge; - for (e = b->succ; e ; e = next) + for (e = b->succ; e; e = next) { basic_block target, first; int counter; @@ -372,6 +380,7 @@ try_forward_edges (mode, b) counter = n_basic_blocks; new_target = target->succ->dest; } + /* Allow to thread only over one edge at time to simplify updating of probabilities. */ else if ((mode & CLEANUP_THREADING) && !threaded) @@ -383,6 +392,7 @@ try_forward_edges (mode, b) new_target_threaded = true; } } + if (!new_target) break; @@ -400,7 +410,7 @@ try_forward_edges (mode, b) if (GET_CODE (insn) != NOTE) insn = NEXT_INSN (insn); - for (;insn && GET_CODE (insn) != CODE_LABEL && !INSN_P (insn); + for (; insn && GET_CODE (insn) != CODE_LABEL && !INSN_P (insn); insn = NEXT_INSN (insn)) if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG) @@ -409,6 +419,7 @@ try_forward_edges (mode, b) if (GET_CODE (insn) == NOTE) break; } + counter++; target = new_target; threaded |= new_target_threaded; @@ -438,10 +449,12 @@ try_forward_edges (mode, b) else if (!redirect_edge_and_branch (e, target)) { if (rtl_dump_file) - fprintf (rtl_dump_file, "Forwarding edge %i->%i to %i failed.\n", + fprintf (rtl_dump_file, + "Forwarding edge %i->%i to %i failed.\n", b->index, e->dest->index, target->index); continue; } + /* We successfully forwarded the edge. Now update profile data: for each edge we traversed in the chain, remove the original edge's execution count. */ @@ -456,6 +469,7 @@ try_forward_edges (mode, b) do { edge t; + first->count -= edge_count; first->succ->count -= edge_count; first->frequency -= edge_frequency; @@ -463,6 +477,7 @@ try_forward_edges (mode, b) t = threaded_edge; else t = first->succ; + first = t->dest; } while (first != target); @@ -553,10 +568,8 @@ merge_blocks_move_predecessor_nojumps (a, b) BB_SET_FLAG (a, BB_UPDATE_LIFE); if (rtl_dump_file) - { - fprintf (rtl_dump_file, "Moved block %d before %d and merged.\n", - a->index, b->index); - } + fprintf (rtl_dump_file, "Moved block %d before %d and merged.\n", + a->index, b->index); /* Swap the records for the two blocks around. Although we are deleting B, A is now where B was and we want to compact the BB array from where @@ -623,10 +636,8 @@ merge_blocks_move_successor_nojumps (a, b) BB_SET_FLAG (a, BB_UPDATE_LIFE); if (rtl_dump_file) - { - fprintf (rtl_dump_file, "Moved block %d after %d and merged.\n", - b->index, a->index); - } + fprintf (rtl_dump_file, "Moved block %d after %d and merged.\n", + b->index, a->index); } /* Attempt to merge basic blocks that are potentially non-adjacent. @@ -660,13 +671,12 @@ merge_blocks (e, b, c, mode) update_forwarder_flag (b); if (rtl_dump_file) - { - fprintf (rtl_dump_file, "Merged %d and %d without moving.\n", - b->index, c->index); - } + fprintf (rtl_dump_file, "Merged %d and %d without moving.\n", + b->index, c->index); return true; } + /* Otherwise we will need to move code around. Do that only if expensive transformations are allowed. */ else if (mode & CLEANUP_EXPENSIVE) @@ -689,11 +699,13 @@ merge_blocks (e, b, c, mode) for (tmp_edge = c->succ; tmp_edge; tmp_edge = tmp_edge->succ_next) if (tmp_edge->flags & EDGE_FALLTHRU) break; + c_has_outgoing_fallthru = (tmp_edge != NULL); for (tmp_edge = b->pred; tmp_edge; tmp_edge = tmp_edge->pred_next) if (tmp_edge->flags & EDGE_FALLTHRU) break; + b_has_incoming_fallthru = (tmp_edge != NULL); b_fallthru_edge = tmp_edge; @@ -714,6 +726,7 @@ merge_blocks (e, b, c, mode) if (b_has_incoming_fallthru) { basic_block bb; + if (b_fallthru_edge->src == ENTRY_BLOCK_PTR) return false; bb = force_nonfallthru (b_fallthru_edge); @@ -722,9 +735,11 @@ merge_blocks (e, b, c, mode) else BB_SET_FLAG (b_fallthru_edge->src, BB_UPDATE_LIFE); } + merge_blocks_move_predecessor_nojumps (b, c); return true; } + return false; } @@ -825,8 +840,10 @@ insns_match_p (mode, i1, i2) return true; } } + return false; } + return true; } @@ -857,6 +874,7 @@ flow_find_cross_jump (mode, bb1, bb2, f1, f2) last1 = i1; i1 = PREV_INSN (i1); } + i2 = bb2->end; if (onlyjump_p (i2) || (returnjump_p (i2) && !side_effects_p (PATTERN (i2)))) @@ -873,6 +891,7 @@ flow_find_cross_jump (mode, bb1, bb2, f1, f2) /* Ignore notes. */ while (!active_insn_p (i1) && i1 != bb1->head) i1 = PREV_INSN (i1); + while (!active_insn_p (i2) && i2 != bb2->head) i2 = PREV_INSN (i2); @@ -905,18 +924,16 @@ flow_find_cross_jump (mode, bb1, bb2, f1, f2) last1 = i1, last2 = i2; ninsns++; } + i1 = PREV_INSN (i1); i2 = PREV_INSN (i2); } #ifdef HAVE_cc0 - if (ninsns) - { - /* Don't allow the insn after a compare to be shared by - cross-jumping unless the compare is also shared. */ - if (reg_mentioned_p (cc0_rtx, last1) && ! sets_cc0_p (last1)) - last1 = afterlast1, last2 = afterlast2, ninsns--; - } + /* Don't allow the insn after a compare to be shared by + cross-jumping unless the compare is also shared. */ + if (ninsns && reg_mentioned_p (cc0_rtx, last1) && ! sets_cc0_p (last1)) + last1 = afterlast1, last2 = afterlast2, ninsns--; #endif /* Include preceding notes and labels in the cross-jump. One, @@ -926,10 +943,13 @@ flow_find_cross_jump (mode, bb1, bb2, f1, f2) { while (last1 != bb1->head && !active_insn_p (PREV_INSN (last1))) last1 = PREV_INSN (last1); + if (last1 != bb1->head && GET_CODE (PREV_INSN (last1)) == CODE_LABEL) last1 = PREV_INSN (last1); + while (last2 != bb2->head && !active_insn_p (PREV_INSN (last2))) last2 = PREV_INSN (last2); + if (last2 != bb2->head && GET_CODE (PREV_INSN (last2)) == CODE_LABEL) last2 = PREV_INSN (last2); @@ -960,12 +980,8 @@ outgoing_edges_match (mode, bb1, bb2) unconditional jump, or a fake edge to exit. */ if (bb1->succ && !bb1->succ->succ_next && !(bb1->succ->flags & (EDGE_COMPLEX | EDGE_FAKE))) - { - if (! bb2->succ || bb2->succ->succ_next - || (bb2->succ->flags & (EDGE_COMPLEX | EDGE_FAKE))) - return false; - return true; - } + return (bb2->succ && !bb2->succ->succ_next + && (bb2->succ->flags & (EDGE_COMPLEX | EDGE_FAKE)) == 0); /* Match conditional jumps - this may get tricky when fallthru and branch edges are crossed. */ @@ -996,6 +1012,7 @@ outgoing_edges_match (mode, bb1, bb2) should be optimized out already. */ if (FORWARDER_BLOCK_P (f1->dest)) f1 = f1->dest->succ; + if (FORWARDER_BLOCK_P (f2->dest)) f2 = f2->dest->succ; @@ -1028,6 +1045,7 @@ outgoing_edges_match (mode, bb1, bb2) code2 = reversed_comparison_code (cond2, bb2->end); else code2 = GET_CODE (cond2); + if (code2 == UNKNOWN) return false; @@ -1052,6 +1070,7 @@ outgoing_edges_match (mode, bb1, bb2) { rtx note1, note2; int prob1, prob2; + note1 = find_reg_note (bb1->end, REG_BR_PROB, 0); note2 = find_reg_note (bb2->end, REG_BR_PROB, 0); @@ -1067,6 +1086,7 @@ outgoing_edges_match (mode, bb1, bb2) if (abs (prob1 - prob2) > REG_BR_PROB_BASE / 20) return false; } + else if (note1 || note2) return false; } @@ -1096,19 +1116,20 @@ outgoing_edges_match (mode, bb1, bb2) { if (e1->flags & EDGE_EH) nehedges1++; + if (e2->flags & EDGE_EH) nehedges2++; + if (e1->flags & EDGE_FALLTHRU) fallthru1 = e1; if (e2->flags & EDGE_FALLTHRU) fallthru2 = e2; } + /* If number of edges of various types does not match, fail. */ - if (e1 || e2) - return false; - if (nehedges1 != nehedges2) - return false; - if ((fallthru1 != 0) != (fallthru2 != 0)) + if (e1 || e2 + || nehedges1 != nehedges2 + || (fallthru1 != 0) != (fallthru2 != 0)) return false; /* fallthru edges must be forwarded to the same destination. */ @@ -1118,17 +1139,21 @@ outgoing_edges_match (mode, bb1, bb2) ? fallthru1->dest->succ->dest: fallthru1->dest); basic_block d2 = (forwarder_block_p (fallthru2->dest) ? fallthru2->dest->succ->dest: fallthru2->dest); + if (d1 != d2) return false; } + /* In case we do have EH edges, ensure we are in the same region. */ if (nehedges1) { rtx n1 = find_reg_note (bb1->end, REG_EH_REGION, 0); rtx n2 = find_reg_note (bb2->end, REG_EH_REGION, 0); + if (XEXP (n1, 0) != XEXP (n2, 0)) return false; } + /* We don't need to match the rest of edges as above checks should be enought to ensure that they are equivalent. */ return true; @@ -1159,17 +1184,12 @@ try_crossjump_to_edge (mode, e1, e2) if (src1->pred && !src1->pred->pred_next && FORWARDER_BLOCK_P (src1)) - { - e1 = src1->pred; - src1 = e1->src; - } + e1 = src1->pred, src1 = e1->src; + if (src2->pred && !src2->pred->pred_next && FORWARDER_BLOCK_P (src2)) - { - e2 = src2->pred; - src2 = e2->src; - } + e2 = src2->pred, src2 = e2->src; /* Nothing to do if we reach ENTRY, or a common source block. */ if (src1 == ENTRY_BLOCK_PTR || src2 == ENTRY_BLOCK_PTR) @@ -1181,6 +1201,7 @@ try_crossjump_to_edge (mode, e1, e2) if (FORWARDER_BLOCK_P (e1->dest) && FORWARDER_BLOCK_P (e1->dest->succ->dest)) return false; + if (FORWARDER_BLOCK_P (e2->dest) && FORWARDER_BLOCK_P (e2->dest->succ->dest)) return false; @@ -1226,6 +1247,7 @@ try_crossjump_to_edge (mode, e1, e2) if (FORWARDER_BLOCK_P (d)) d = d->succ->dest; + for (s2 = src1->succ; ; s2 = s2->succ_next) { basic_block d2 = s2->dest; @@ -1234,6 +1256,7 @@ try_crossjump_to_edge (mode, e1, e2) if (d == d2) break; } + s->count += s2->count; /* Take care to update possible forwarder blocks. We verified @@ -1245,19 +1268,21 @@ try_crossjump_to_edge (mode, e1, e2) s->dest->count += s2->count; s->dest->frequency += EDGE_FREQUENCY (s); } + if (FORWARDER_BLOCK_P (s2->dest)) { s2->dest->succ->count -= s2->count; s2->dest->count -= s2->count; s2->dest->frequency -= EDGE_FREQUENCY (s); } + if (!redirect_to->frequency && !src1->frequency) s->probability = (s->probability + s2->probability) / 2; else - s->probability = - ((s->probability * redirect_to->frequency + - s2->probability * src1->frequency) - / (redirect_to->frequency + src1->frequency)); + s->probability + = ((s->probability * redirect_to->frequency + + s2->probability * src1->frequency) + / (redirect_to->frequency + src1->frequency)); } note = find_reg_note (redirect_to->end, REG_BR_PROB, 0); @@ -1269,6 +1294,7 @@ try_crossjump_to_edge (mode, e1, e2) /* Skip possible basic block header. */ if (GET_CODE (newpos1) == CODE_LABEL) newpos1 = NEXT_INSN (newpos1); + if (GET_CODE (newpos1) == NOTE) newpos1 = NEXT_INSN (newpos1); last = src1->end; @@ -1409,7 +1435,6 @@ try_optimize_cfg (mode) /* Attempt to merge blocks as made possible by edge removal. If a block has only one successor, and the successor has only one predecessor, they may be combined. */ - do { changed = false; @@ -1431,6 +1456,7 @@ try_optimize_cfg (mode) c = BASIC_BLOCK (b->index - 1); if (rtl_dump_file) fprintf (rtl_dump_file, "Deleting block %i.\n", b->index); + flow_delete_block (b); changed = true; b = c; @@ -1455,6 +1481,7 @@ try_optimize_cfg (mode) || ! label_is_jump_target_p (b->head, b->pred->src->end))) { rtx label = b->head; + b->head = NEXT_INSN (b->head); delete_insn_chain (label, label); if (rtl_dump_file) @@ -1475,6 +1502,7 @@ try_optimize_cfg (mode) if (rtl_dump_file) fprintf (rtl_dump_file, "Deleting fallthru block %i.\n", b->index); + c = BASIC_BLOCK (b->index ? b->index - 1 : 1); redirect_edge_succ_nodup (b->pred, b->succ->dest); flow_delete_block (b); @@ -1554,6 +1582,7 @@ try_optimize_cfg (mode) if ((mode & CLEANUP_UPDATE_LIFE) && changed_overall) { bool found = 0; + blocks = sbitmap_alloc (n_basic_blocks); sbitmap_zero (blocks); for (i = 0; i < n_basic_blocks; i++) @@ -1562,12 +1591,14 @@ try_optimize_cfg (mode) found = 1; SET_BIT (blocks, i); } + if (found) update_life_info (blocks, UPDATE_LIFE_GLOBAL, PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE | PROP_KILL_DEAD_CODE); sbitmap_free (blocks); } + for (i = 0; i < n_basic_blocks; i++) BASIC_BLOCK (i)->aux = NULL; diff --git a/gcc/cfglayout.c b/gcc/cfglayout.c index 1907bafc191..14f08eb39ef 100644 --- a/gcc/cfglayout.c +++ b/gcc/cfglayout.c @@ -1,22 +1,22 @@ /* Basic block reordering routines for the GNU compiler. Copyright (C) 2000, 2001 Free Software Foundation, Inc. - This file is part of GCC. +This file is part of GCC. - GCC is free software; you can redistribute it and/or modify it - under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 2, or (at your option) - any later version. +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 2, or (at your option) any later +version. - GCC is distributed in the hope that it will be useful, but WITHOUT - ANY WARRANTY; without even the implied warranty of MERCHANTABILITY - or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public - License for more details. +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. - You should have received a copy of the GNU General Public License - along with GCC; see the file COPYING. If not, write to the Free - Software Foundation, 59 Temple Place - Suite 330, Boston, MA - 02111-1307, USA. */ +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING. If not, write to the Free +Software Foundation, 59 Temple Place - Suite 330, Boston, MA +02111-1307, USA. */ #include "config.h" #include "system.h" @@ -30,9 +30,7 @@ #include "cfglayout.h" /* The contents of the current function definition are allocated - in this obstack, and all are freed at the end of the function. - For top-level functions, this is temporary_obstack. - Separate obstacks are made for nested functions. */ + in this obstack, and all are freed at the end of the function. */ extern struct obstack flow_obstack; @@ -126,7 +124,7 @@ skip_insns_after_block (bb) if (bb->index + 1 != n_basic_blocks) next_head = BASIC_BLOCK (bb->index + 1)->head; - for (last_insn = insn = bb->end; (insn = NEXT_INSN (insn)); ) + for (last_insn = insn = bb->end; (insn = NEXT_INSN (insn)) != 0; ) { if (insn == next_head) break; @@ -172,30 +170,30 @@ skip_insns_after_block (bb) break; } - /* It is possible to hit contradicting sequence. For instance: + + /* It is possible to hit contradictory sequence. For instance: jump_insn NOTE_INSN_LOOP_BEG barrier - Where barrier belongs to jump_insn, but the note does not. - This can be created by removing the basic block originally - following NOTE_INSN_LOOP_BEG. + Where barrier belongs to jump_insn, but the note does not. This can be + created by removing the basic block originally following + NOTE_INSN_LOOP_BEG. In such case reorder the notes. */ - In such case reorder the notes. */ for (insn = last_insn; insn != bb->end; insn = prev) { - prev = PREV_INSN (insn); - if (GET_CODE (insn) == NOTE) - switch (NOTE_LINE_NUMBER (insn)) - { + prev = PREV_INSN (insn); + if (GET_CODE (insn) == NOTE) + switch (NOTE_LINE_NUMBER (insn)) + { case NOTE_INSN_LOOP_END: case NOTE_INSN_BLOCK_END: case NOTE_INSN_DELETED: case NOTE_INSN_DELETED_LABEL: - continue; + continue; default: - reorder_insns (insn, insn, last_insn); + reorder_insns (insn, insn, last_insn); } } @@ -213,8 +211,7 @@ label_for_bb (bb) if (GET_CODE (label) != CODE_LABEL) { if (rtl_dump_file) - fprintf (rtl_dump_file, "Emitting label for block %d\n", - bb->index); + fprintf (rtl_dump_file, "Emitting label for block %d\n", bb->index); label = block_label (bb); if (bb->head == PREV_INSN (RBI (bb)->eff_head)) @@ -233,7 +230,7 @@ record_effective_endpoints () rtx next_insn = get_insns (); int i; - for (i = 0; i < n_basic_blocks; ++i) + for (i = 0; i < n_basic_blocks; i++) { basic_block bb = BASIC_BLOCK (i); rtx end; @@ -243,32 +240,33 @@ record_effective_endpoints () RBI (bb)->eff_end = end; next_insn = NEXT_INSN (end); } + function_tail_eff_head = next_insn; } +/* Return the next NOTE_INSN_BASIC_BLOCK after X. */ + static rtx get_next_bb_note (x) rtx x; { - while (x) - { - if (NOTE_INSN_BASIC_BLOCK_P (x)) - return x; - x = NEXT_INSN (x); - } + for (; x; x = NEXT_INSN (x)) + if (NOTE_INSN_BASIC_BLOCK_P (x)) + return x; + return NULL; } +/* Return the fist NOTE_INSN_BASIC_BLOCK before X. */ + static rtx get_prev_bb_note (x) rtx x; { - while (x) - { - if (NOTE_INSN_BASIC_BLOCK_P (x)) - return x; - x = PREV_INSN (x); - } + for (; x; x = PREV_INSN (x)) + if (NOTE_INSN_BASIC_BLOCK_P (x)) + return x; + return NULL; } @@ -313,6 +311,7 @@ relate_bbs_with_scopes (s) bbnote = get_next_bb_note (s->note_beg); if (! bbnote) abort (); + if (NOTE_BASIC_BLOCK (bbnote) == s->bb_end) { bbs_spanned = 0; @@ -335,6 +334,7 @@ relate_bbs_with_scopes (s) bbnote = get_prev_bb_note (s->note_end); if (! bbnote) abort (); + if (NOTE_BASIC_BLOCK (bbnote) == s->bb_beg) { bbs_spanned = 0; @@ -357,16 +357,15 @@ relate_bbs_with_scopes (s) bbs_spanned = 0; else { - rtx x1, x2; /* Both notes are outside of any bbs. This implies that all the basic blocks spanned by the pair of notes are contained in this scope. There is a degenerate case to consider. If the notes do not span any basic blocks, then it is an empty scope that can safely be deleted or ignored. Mark these with level = -1. */ + rtx x1 = get_next_bb_note (s->note_beg); + rtx x2 = get_prev_bb_note (s->note_end); - x1 = get_next_bb_note (s->note_beg); - x2 = get_prev_bb_note (s->note_end); if (! (x1 && x2)) { s->level = -1; @@ -418,6 +417,7 @@ make_new_scope (level, note) rtx note; { scope new_scope = xcalloc (1, sizeof (struct scope_def)); + new_scope->level = level; new_scope->note_beg = note; return new_scope; @@ -442,6 +442,7 @@ build_scope_forest (forest) root = NULL; curr_bb = NULL; bbi = 0; + for (x = get_insns (); x; x = NEXT_INSN (x)) { if (bbi < n_basic_blocks && x == BASIC_BLOCK (bbi)->head) @@ -454,8 +455,10 @@ build_scope_forest (forest) if (root) { scope new_scope; + if (! curr_scope) abort(); + level++; new_scope = make_new_scope (level, x); new_scope->outer = curr_scope; @@ -471,10 +474,12 @@ build_scope_forest (forest) curr_scope->inner_last = new_scope; } curr_scope = curr_scope->inner_last; + } else { int ntrees = forest->num_trees; + level++; curr_scope = make_new_scope (level, x); root = curr_scope; @@ -482,6 +487,7 @@ build_scope_forest (forest) sizeof (scope) * (ntrees + 1)); forest->trees[forest->num_trees++] = root; } + curr_scope->bb_beg = curr_bb; } else if (NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_END) @@ -493,22 +499,21 @@ build_scope_forest (forest) if (level == -1) root = NULL; } - } /* if note */ + } if (curr_bb && curr_bb->end == x) { curr_bb = NULL; bbi++; } - - } /* for */ + } for (i = 0; i < forest->num_trees; i++) relate_bbs_with_scopes (forest->trees[i]); } -/* Remove all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes from - the insn chain. */ +/* Remove all NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes from the insn + chain. */ static void remove_scope_notes () @@ -572,7 +577,6 @@ insert_intra_1 (s, ip, bb) } } - /* Insert NOTE_INSN_BLOCK_END notes and NOTE_INSN_BLOCK_BEG notes for scopes that are contained within BB. */ @@ -598,7 +602,6 @@ insert_intra_bb_scope_notes (bb) } } - /* Given two consecutive basic blocks BB1 and BB2 with different scopes, insert NOTE_INSN_BLOCK_END notes after BB1 and NOTE_INSN_BLOCK_BEG notes before BB2 such that the notes are correctly balanced. If BB1 or @@ -619,8 +622,10 @@ insert_inter_bb_scope_notes (bb1, bb2) { scope s1 = RBI (bb1)->scope; scope s2 = RBI (bb2)->scope; + if (! s1 && ! s2) return; + if (! s1) bb1 = NULL; else if (! s2) @@ -632,10 +637,9 @@ insert_inter_bb_scope_notes (bb1, bb2) { scope s1 = RBI (bb1)->scope; scope s2 = RBI (bb2)->scope; + while (s1 != s2) { - if (! (s1 && s2)) - abort (); if (s1->level > s2->level) s1 = s1->outer; else if (s2->level > s1->level) @@ -646,6 +650,7 @@ insert_inter_bb_scope_notes (bb1, bb2) s2 = s2->outer; } } + com = s1; } else @@ -655,18 +660,16 @@ insert_inter_bb_scope_notes (bb1, bb2) if (bb1) { rtx end = bb1->end; + scope s; - scope s = RBI (bb1)->scope; ip = RBI (bb1)->eff_end; - while (s != com) - { - if (NOTE_BLOCK (s->note_beg)) - { - ip = emit_note_after (NOTE_INSN_BLOCK_END, ip); - NOTE_BLOCK (ip) = NOTE_BLOCK (s->note_end); - } - s = s->outer; - } + for (s = RBI (bb1)->scope; s != com; s = s->outer) + if (NOTE_BLOCK (s->note_beg)) + { + ip = emit_note_after (NOTE_INSN_BLOCK_END, ip); + NOTE_BLOCK (ip) = NOTE_BLOCK (s->note_end); + } + /* Emitting note may move the end of basic block to unwanted place. */ bb1->end = end; } @@ -674,17 +677,15 @@ insert_inter_bb_scope_notes (bb1, bb2) /* Open scopes. */ if (bb2) { - scope s = RBI (bb2)->scope; + scope s; + ip = bb2->head; - while (s != com) - { - if (NOTE_BLOCK (s->note_beg)) - { - ip = emit_note_before (NOTE_INSN_BLOCK_BEG, ip); - NOTE_BLOCK (ip) = NOTE_BLOCK (s->note_beg); - } - s = s->outer; - } + for (s = RBI (bb2)->scope; s != com; s = s->outer) + if (NOTE_BLOCK (s->note_beg)) + { + ip = emit_note_before (NOTE_INSN_BLOCK_BEG, ip); + NOTE_BLOCK (ip) = NOTE_BLOCK (s->note_beg); + } } } @@ -709,6 +710,7 @@ rebuild_scope_notes (forest) { basic_block bb1 = BASIC_BLOCK (i); basic_block bb2 = BASIC_BLOCK (i + 1); + if (RBI (bb1)->scope != RBI (bb2)->scope) insert_inter_bb_scope_notes (bb1, bb2); insert_intra_bb_scope_notes (bb1); @@ -745,6 +747,7 @@ free_scope_forest (forest) scope_forest_info *forest; { int i; + for (i = 0; i < forest->num_trees; i++) free_scope_forest_1 (forest->trees[i]); } @@ -755,15 +758,15 @@ void dump_scope_forest (forest) scope_forest_info *forest; { + int i; + if (forest->num_trees == 0) fprintf (stderr, "\n< Empty scope forest >\n"); else - { - int i; - fprintf (stderr, "\n< Scope forest >\n"); - for (i = 0; i < forest->num_trees; i++) - dump_scope_forest_1 (forest->trees[i], 0); - } + fprintf (stderr, "\n< Scope forest >\n"); + + for (i = 0; i < forest->num_trees; i++) + dump_scope_forest_1 (forest->trees[i], 0); } /* Recursive portion of dump_scope_forest. */ @@ -813,33 +816,28 @@ fixup_reorder_chain () /* First do the bulk reordering -- rechain the blocks without regard to the needed changes to jumps and labels. */ - last_bb = BASIC_BLOCK (0); - bb = RBI (last_bb)->next; - index = 1; - while (bb) + for (last_bb = BASIC_BLOCK (0), bb = RBI (last_bb)->next, index = 1; + bb != 0; + last_bb = bb, bb = RBI (bb)->next, index++) { rtx last_e = RBI (last_bb)->eff_end; rtx curr_h = RBI (bb)->eff_head; NEXT_INSN (last_e) = curr_h; PREV_INSN (curr_h) = last_e; - - last_bb = bb; - bb = RBI (bb)->next; - index++; } if (index != n_basic_blocks) abort (); insn = RBI (last_bb)->eff_end; - NEXT_INSN (insn) = function_tail_eff_head; if (function_tail_eff_head) PREV_INSN (function_tail_eff_head) = insn; while (NEXT_INSN (insn)) insn = NEXT_INSN (insn); + set_last_insn (insn); #ifdef ENABLE_CHECKING verify_insn_chain (); @@ -884,6 +882,7 @@ fixup_reorder_chain () if (RBI (bb)->next != e_taken->dest) { rtx note = find_reg_note (bb_end_insn, REG_BR_PROB, 0); + if (note && INTVAL (XEXP (note, 0)) < REG_BR_PROB_BASE / 2 && invert_jump (bb_end_insn, @@ -913,6 +912,7 @@ fixup_reorder_chain () 99% case, there should not have been a fallthru edge. */ if (! e_fall) continue; + #ifdef CASE_DROPS_THROUGH /* Except for VAX. Since we didn't have predication for the tablejump, the fallthru block should not have moved. */ @@ -936,15 +936,13 @@ fixup_reorder_chain () if (RBI (bb)->next == e_fall->dest) continue; - /* An fallthru to exit block. */ + /* A fallthru to exit block. */ if (!RBI (bb)->next && e_fall->dest == EXIT_BLOCK_PTR) continue; } /* We got here if we need to add a new jump insn. */ - nb = force_nonfallthru (e_fall); - if (nb) { alloc_aux_for_block (nb, sizeof (struct reorder_block_def)); @@ -965,18 +963,17 @@ fixup_reorder_chain () if (rtl_dump_file) fprintf (rtl_dump_file, "Reordered sequence:\n"); - while (bb) + + for (; bb; bb = RBI (bb)->next, index++) { if (rtl_dump_file) fprintf (rtl_dump_file, " %i %sbb %i freq %i\n", index, bb->index >= old_n_basic_blocks ? "compensation " : "", bb->index, bb->frequency); + bb->index = index; BASIC_BLOCK (index) = bb; - - bb = RBI (bb)->next; - index++; } } @@ -989,62 +986,31 @@ fixup_reorder_chain () void verify_insn_chain () { - rtx x, - prevx, - nextx; - int insn_cnt1, - insn_cnt2; - - prevx = NULL; - insn_cnt1 = 1; - for (x = get_insns (); x; x = NEXT_INSN (x)) - { - if (PREV_INSN (x) != prevx) - { - fprintf (stderr, "Forward traversal: insn chain corrupt.\n"); - fprintf (stderr, "previous insn:\n"); - debug_rtx (prevx); - fprintf (stderr, "current insn:\n"); - debug_rtx (x); - abort (); - } - ++insn_cnt1; - prevx = x; - } + rtx x, prevx, nextx; + int insn_cnt1, insn_cnt2; - if (prevx != get_last_insn ()) - { - fprintf (stderr, "last_insn corrupt.\n"); + for (prevx = NULL, insn_cnt1 = 1, x = get_insns (); + x != 0; + prevx = x, insn_cnt1++, x = NEXT_INSN (x)) + if (PREV_INSN (x) != prevx) abort (); - } - nextx = NULL; - insn_cnt2 = 1; - for (x = get_last_insn (); x; x = PREV_INSN (x)) - { - if (NEXT_INSN (x) != nextx) - { - fprintf (stderr, "Reverse traversal: insn chain corrupt.\n"); - fprintf (stderr, "current insn:\n"); - debug_rtx (x); - fprintf (stderr, "next insn:\n"); - debug_rtx (nextx); - abort (); - } - ++insn_cnt2; - nextx = x; - } + if (prevx != get_last_insn ()) + abort (); - if (insn_cnt1 != insn_cnt2) - { - fprintf (stderr, "insn_cnt1 (%d) not equal to insn_cnt2 (%d).\n", - insn_cnt1, insn_cnt2); + for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn (); + x != 0; + nextx = x, insn_cnt2++, x = PREV_INSN (x)) + if (NEXT_INSN (x) != nextx) abort (); - } + + if (insn_cnt1 != insn_cnt2) + abort (); } -/* The block falling through to exit must be the last one in the - reordered chain. Ensure that this condition is met. */ +/* The block falling through to exit must be the last one in the reordered + chain. Ensure it is. */ + static void fixup_fallthru_exit_predecessor () { @@ -1054,21 +1020,25 @@ fixup_fallthru_exit_predecessor () for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next) if (e->flags & EDGE_FALLTHRU) bb = e->src; + if (bb && RBI (bb)->next) { basic_block c = BASIC_BLOCK (0); + while (RBI (c)->next != bb) c = RBI (c)->next; + RBI (c)->next = RBI (bb)->next; while (RBI (c)->next) c = RBI (c)->next; + RBI (c)->next = bb; RBI (bb)->next = NULL; } } -/* Main entry point to this module - initialize the datastructures for - CFG layout changes. */ +/* Main entry point to this module: initialize the datastructures for CFG + layout changes. */ void cfg_layout_initialize () @@ -1081,14 +1051,15 @@ cfg_layout_initialize () record_effective_endpoints (); } -/* Finalize the changes - reorder insn list according to the sequence, - enter compensation code, rebuild scope forest. */ +/* Finalize the changes: reorder insn list according to the sequence, enter + compensation code, rebuild scope forest. */ void cfg_layout_finalize () { fixup_fallthru_exit_predecessor (); fixup_reorder_chain (); + #ifdef ENABLE_CHECKING verify_insn_chain (); #endif diff --git a/gcc/cfgloop.c b/gcc/cfgloop.c index a94cbfe79b9..b4b8eb73fbd 100644 --- a/gcc/cfgloop.c +++ b/gcc/cfgloop.c @@ -31,11 +31,13 @@ static int flow_loop_nested_p PARAMS ((struct loop *, static int flow_loop_entry_edges_find PARAMS ((basic_block, const sbitmap, edge **)); static int flow_loop_exit_edges_find PARAMS ((const sbitmap, edge **)); -static int flow_loop_nodes_find PARAMS ((basic_block, basic_block, sbitmap)); -static void flow_loop_pre_header_scan PARAMS ((struct loop *)); +static int flow_loop_nodes_find PARAMS ((basic_block, basic_block, + sbitmap)); +static void flow_loop_pre_header_scan PARAMS ((struct loop *)); static basic_block flow_loop_pre_header_find PARAMS ((basic_block, const sbitmap *)); -static void flow_loop_tree_node_add PARAMS ((struct loop *, struct loop *)); +static void flow_loop_tree_node_add PARAMS ((struct loop *, + struct loop *)); static void flow_loops_tree_build PARAMS ((struct loops *)); static int flow_loop_level_compute PARAMS ((struct loop *, int)); static int flow_loops_level_compute PARAMS ((struct loops *)); @@ -68,14 +70,17 @@ flow_loops_cfg_dump (loops, file) fputs (";; DFS order: ", file); for (i = 0; i < n_basic_blocks; i++) fprintf (file, "%d ", loops->cfg.dfs_order[i]); + fputs ("\n", file); } + /* Dump the reverse completion node order. */ if (loops->cfg.rc_order) { fputs (";; RC order: ", file); for (i = 0; i < n_basic_blocks; i++) fprintf (file, "%d ", loops->cfg.rc_order[i]); + fputs ("\n", file); } } @@ -107,12 +112,10 @@ flow_loop_dump (loop, file, loop_dump_aux, verbose) fprintf (file, ";;\n;; Loop %d (%d to %d):%s%s\n", loop->num, INSN_UID (loop->first->head), INSN_UID (loop->last->end), - loop->shared ? " shared" : "", - loop->invalid ? " invalid" : ""); + loop->shared ? " shared" : "", loop->invalid ? " invalid" : ""); else fprintf (file, ";;\n;; Loop %d:%s%s\n", loop->num, - loop->shared ? " shared" : "", - loop->invalid ? " invalid" : ""); + loop->shared ? " shared" : "", loop->invalid ? " invalid" : ""); fprintf (file, ";; header %d, latch %d, pre-header %d, first %d, last %d\n", loop->header->index, loop->latch->index, @@ -125,14 +128,17 @@ flow_loop_dump (loop, file, loop_dump_aux, verbose) if (loop->pre_header_edges) flow_edge_list_print (";; pre-header edges", loop->pre_header_edges, loop->num_pre_header_edges, file); + flow_edge_list_print (";; entry edges", loop->entry_edges, loop->num_entries, file); fprintf (file, ";; %d", loop->num_nodes); flow_nodes_print (" nodes", loop->nodes, file); flow_edge_list_print (";; exit edges", loop->exit_edges, loop->num_exits, file); + if (loop->exits_doms) flow_nodes_print (";; exit doms", loop->exits_doms, file); + if (loop_dump_aux) loop_dump_aux (loop, file, verbose); } @@ -147,49 +153,42 @@ flow_loops_dump (loops, file, loop_dump_aux, verbose) void (*loop_dump_aux) PARAMS((const struct loop *, FILE *, int)); int verbose; { - int i; + int i, j; int num_loops; num_loops = loops->num; if (! num_loops || ! file) return; - fprintf (file, ";; %d loops found, %d levels\n", - num_loops, loops->levels); - + fprintf (file, ";; %d loops found, %d levels\n", num_loops, loops->levels); for (i = 0; i < num_loops; i++) { struct loop *loop = &loops->array[i]; flow_loop_dump (loop, file, loop_dump_aux, verbose); - if (loop->shared) - { - int j; - - for (j = 0; j < i; j++) - { - struct loop *oloop = &loops->array[j]; - - if (loop->header == oloop->header) - { - int disjoint; - int smaller; - - smaller = loop->num_nodes < oloop->num_nodes; - - /* If the union of LOOP and OLOOP is different than - the larger of LOOP and OLOOP then LOOP and OLOOP - must be disjoint. */ - disjoint = ! flow_loop_nested_p (smaller ? loop : oloop, - smaller ? oloop : loop); - fprintf (file, - ";; loop header %d shared by loops %d, %d %s\n", - loop->header->index, i, j, - disjoint ? "disjoint" : "nested"); - } - } - } + for (j = 0; j < i; j++) + { + struct loop *oloop = &loops->array[j]; + + if (loop->header == oloop->header) + { + int disjoint; + int smaller; + + smaller = loop->num_nodes < oloop->num_nodes; + + /* If the union of LOOP and OLOOP is different than + the larger of LOOP and OLOOP then LOOP and OLOOP + must be disjoint. */ + disjoint = ! flow_loop_nested_p (smaller ? loop : oloop, + smaller ? oloop : loop); + fprintf (file, + ";; loop header %d shared by loops %d, %d %s\n", + loop->header->index, i, j, + disjoint ? "disjoint" : "nested"); + } + } } if (verbose) @@ -225,11 +224,13 @@ flow_loops_free (loops) if (loop->exits_doms) sbitmap_free (loop->exits_doms); } + free (loops->array); loops->array = NULL; if (loops->cfg.dom) sbitmap_vector_free (loops->cfg.dom); + if (loops->cfg.dfs_order) free (loops->cfg.dfs_order); @@ -394,42 +395,33 @@ static void flow_loop_pre_header_scan (loop) struct loop *loop; { - int num = 0; + int num; basic_block ebb; + edge e; loop->num_pre_header_edges = 0; - if (loop->num_entries != 1) - return; + return; ebb = loop->entry_edges[0]->src; + if (ebb == ENTRY_BLOCK_PTR) + return; - if (ebb != ENTRY_BLOCK_PTR) - { - edge e; - - /* Count number of edges along trace from loop header to - root of pre-header extended basic block. Usually this is - only one or two edges. */ - num++; - while (ebb->pred->src != ENTRY_BLOCK_PTR && ! ebb->pred->pred_next) - { - ebb = ebb->pred->src; - num++; - } - - loop->pre_header_edges = (edge *) xmalloc (num * sizeof (edge *)); - loop->num_pre_header_edges = num; - - /* Store edges in order that they are followed. The source - of the first edge is the root node of the pre-header extended - basic block and the destination of the last last edge is - the loop header. */ - for (e = loop->entry_edges[0]; num; e = e->src->pred) - { - loop->pre_header_edges[--num] = e; - } - } + /* Count number of edges along trace from loop header to + root of pre-header extended basic block. Usually this is + only one or two edges. */ + for (num = 1; ebb->pred->src != ENTRY_BLOCK_PTR && ! ebb->pred->pred_next; + num++) + ebb = ebb->pred->src; + + loop->pre_header_edges = (edge *) xmalloc (num * sizeof (edge *)); + loop->num_pre_header_edges = num; + + /* Store edges in order that they are followed. The source of the first edge + is the root node of the pre-header extended basic block and the + destination of the last last edge is the loop header. */ + for (e = loop->entry_edges[0]; num; e = e->src->pred) + loop->pre_header_edges[--num] = e; } /* Return the block for the pre-header of the loop with header @@ -465,6 +457,7 @@ flow_loop_pre_header_find (header, dom) } } } + return pre_header; } @@ -485,16 +478,13 @@ flow_loop_tree_node_add (prevloop, loop) return; } - while (prevloop->outer) - { - if (flow_loop_nested_p (prevloop->outer, loop)) - { - prevloop->next = loop; - loop->outer = prevloop->outer; - return; - } - prevloop = prevloop->outer; - } + for (; prevloop->outer; prevloop = prevloop->outer) + if (flow_loop_nested_p (prevloop->outer, loop)) + { + prevloop->next = loop; + loop->outer = prevloop->outer; + return; + } prevloop->next = loop; loop->outer = NULL; @@ -517,7 +507,8 @@ flow_loops_tree_build (loops) Since we used a depth first search this should be the outermost loop. */ loops->tree_root = &loops->array[0]; - loops->tree_root->outer = loops->tree_root->inner = loops->tree_root->next = NULL; + loops->tree_root->outer = loops->tree_root->inner + = loops->tree_root->next = NULL; /* Add the remaining loops to the tree. */ for (i = 1; i < num_loops; i++) @@ -546,13 +537,11 @@ flow_loop_level_compute (loop, depth) itself). */ for (inner = loop->inner; inner; inner = inner->next) { - int ilevel; - - ilevel = flow_loop_level_compute (inner, depth + 1) + 1; + int ilevel = flow_loop_level_compute (inner, depth + 1) + 1; - if (ilevel > level) - level = ilevel; + level = MAX (ilevel, level); } + loop->level = level; loop->depth = depth; return level; @@ -566,17 +555,17 @@ static int flow_loops_level_compute (loops) struct loops *loops; { + int levels = 0; struct loop *loop; int level; - int levels = 0; /* Traverse all the outer level loops. */ for (loop = loops->tree_root; loop; loop = loop->next) { level = flow_loop_level_compute (loop, 1); - if (level > levels) - levels = level; + levels = MAX (levels, level); } + return levels; } @@ -594,23 +583,15 @@ flow_loop_scan (loops, loop, flags) flags |= LOOP_EXIT_EDGES; if (flags & LOOP_ENTRY_EDGES) - { - /* Find edges which enter the loop header. - Note that the entry edges should only - enter the header of a natural loop. */ - loop->num_entries - = flow_loop_entry_edges_find (loop->header, - loop->nodes, - &loop->entry_edges); - } + /* Find edges which enter the loop header. Note that the entry edges + should only enter the header of a natural loop. */ + loop->num_entries = flow_loop_entry_edges_find (loop->header, loop->nodes, + &loop->entry_edges); if (flags & LOOP_EXIT_EDGES) - { - /* Find edges which exit the loop. */ - loop->num_exits - = flow_loop_exit_edges_find (loop->nodes, - &loop->exit_edges); - } + /* Find edges which exit the loop. */ + loop->num_exits + = flow_loop_exit_edges_find (loop->nodes, &loop->exit_edges); if (flags & LOOP_EXITS_DOMS) { @@ -640,13 +621,14 @@ flow_loop_scan (loops, loop, flags) the loop pre-header. */ flow_loop_pre_header_scan (loop); } + return 1; } -/* Find all the natural loops in the function and save in LOOPS structure - and recalculate loop_depth information in basic block structures. - FLAGS controls which loop information is collected. - Return the number of natural loops found. */ +/* Find all the natural loops in the function and save in LOOPS structure and + recalculate loop_depth information in basic block structures. FLAGS + controls which loop information is collected. Return the number of natural + loops found. */ int flow_loops_find (loops, flags) @@ -668,7 +650,7 @@ flow_loops_find (loops, flags) if (! (flags & LOOP_TREE)) abort (); - memset (loops, 0, sizeof (*loops)); + memset (loops, 0, sizeof *loops); /* Taking care of this degenerate case makes the rest of this code simpler. */ @@ -684,7 +666,6 @@ flow_loops_find (loops, flags) /* Count the number of loop edges (back edges). This should be the same as the number of natural loops. */ - num_loops = 0; for (b = 0; b < n_basic_blocks; b++) { @@ -810,9 +791,7 @@ flow_loops_find (loops, flags) sbitmap_free (headers); } else - { - sbitmap_vector_free (dom); - } + sbitmap_vector_free (dom); loops->num = num_loops; @@ -828,6 +807,7 @@ flow_loops_find (loops, flags) /* Update the information regarding the loops in the CFG specified by LOOPS. */ + int flow_loops_update (loops, flags) struct loops *loops; @@ -850,5 +830,7 @@ flow_loop_outside_edge_p (loop, e) { if (e->dest != loop->header) abort (); - return (e->src == ENTRY_BLOCK_PTR) || ! TEST_BIT (loop->nodes, e->src->index); + + return (e->src == ENTRY_BLOCK_PTR) + || ! TEST_BIT (loop->nodes, e->src->index); } diff --git a/gcc/cfgrtl.c b/gcc/cfgrtl.c index 08912c5d042..92d230eebce 100644 --- a/gcc/cfgrtl.c +++ b/gcc/cfgrtl.c @@ -19,28 +19,28 @@ along with GCC; see the file COPYING. If not, write to the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ -/* This file contains low level functions to manipulate with CFG and analyze it - that are aware of RTL intermediate language. +/* This file contains low level functions to manipulate the CFG and analyze it + that are aware of the RTL intermediate language. Available functionality: - - CFG aware instruction chain manipulation + - CFG-aware instruction chain manipulation delete_insn, delete_insn_chain - Basic block manipulation - create_basic_block, flow_delete_block, split_block, merge_blocks_nomove - - Infrastructure to determine quickly basic block for instruction. + create_basic_block, flow_delete_block, split_block, + merge_blocks_nomove + - Infrastructure to determine quickly basic block for insn compute_bb_for_insn, update_bb_for_insn, set_block_for_insn, - - Edge redirection with updating and optimizing instruction chain - block_label, redirect_edge_and_branch, - redirect_edge_and_branch_force, tidy_fallthru_edge, force_nonfallthru + - Edge redirection with updating and optimizing of insn chain + block_label, redirect_edge_and_branch, + redirect_edge_and_branch_force, tidy_fallthru_edge, force_nonfallthru - Edge splitting and commiting to edges - split_edge, insert_insn_on_edge, commit_edge_insertions + split_edge, insert_insn_on_edge, commit_edge_insertions - Dumping and debugging - print_rtl_with_bb, dump_bb, debug_bb, debug_bb_n + print_rtl_with_bb, dump_bb, debug_bb, debug_bb_n - Consistency checking - verify_flow_info + verify_flow_info - CFG updating after constant propagation - purge_dead_edges, purge_all_dead_edges - */ + purge_dead_edges, purge_all_dead_edges */ #include "config.h" #include "system.h" @@ -57,20 +57,18 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "tm_p.h" #include "obstack.h" -/* Stubs in case we haven't got a return insn. */ +/* Stubs in case we don't have a return insn. */ #ifndef HAVE_return #define HAVE_return 0 #define gen_return() NULL_RTX #endif /* The basic block structure for every insn, indexed by uid. */ - varray_type basic_block_for_insn; /* The labels mentioned in non-jump rtl. Valid during find_basic_blocks. */ /* ??? Should probably be using LABEL_NUSES instead. It would take a bit of surgery to be able to use or co-opt the routines in jump. */ - rtx label_value_list; rtx tail_recursion_label_list; @@ -83,7 +81,7 @@ static bool back_edge_of_syntactic_loop_p PARAMS ((basic_block, basic_block)); static basic_block force_nonfallthru_and_redirect PARAMS ((edge, basic_block)); /* Return true if NOTE is not one of the ones that must be kept paired, - so that we may simply delete them. */ + so that we may simply delete it. */ static int can_delete_note_p (note) @@ -99,26 +97,12 @@ static int can_delete_label_p (label) rtx label; { - rtx x; - - if (LABEL_PRESERVE_P (label)) - return 0; - - for (x = forced_labels; x; x = XEXP (x, 1)) - if (label == XEXP (x, 0)) - return 0; - for (x = label_value_list; x; x = XEXP (x, 1)) - if (label == XEXP (x, 0)) - return 0; - for (x = exception_handler_labels; x; x = XEXP (x, 1)) - if (label == XEXP (x, 0)) - return 0; - - /* User declared labels must be preserved. */ - if (LABEL_NAME (label) != 0) - return 0; - - return 1; + return (!LABEL_PRESERVE_P (label) + /* User declared labels must be preserved. */ + && LABEL_NAME (label) == 0 + && !in_expr_list_p (forced_labels, label) + && !in_expr_list_p (label_value_list, label) + && !in_expr_list_p (exception_handler_labels, label)); } /* Delete INSN by patching it out. Return the next insn. */ @@ -145,6 +129,7 @@ delete_insn (insn) NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED_LABEL; NOTE_SOURCE_FILE (insn) = name; } + remove_node_from_expr_list (insn, &nonlocal_goto_handler_labels); } @@ -189,12 +174,11 @@ void delete_insn_chain (start, finish) rtx start, finish; { - /* Unchain the insns one by one. It would be quicker to delete all - of these with a single unchaining, rather than one at a time, but - we need to keep the NOTE's. */ - rtx next; + /* Unchain the insns one by one. It would be quicker to delete all of these + with a single unchaining, rather than one at a time, but we need to keep + the NOTE's. */ while (1) { next = NEXT_INSN (start); @@ -209,14 +193,12 @@ delete_insn_chain (start, finish) } } -/* Create a new basic block consisting of the instructions between - HEAD and END inclusive. This function is designed to allow fast - BB construction - reuses the note and basic block struct - in BB_NOTE, if any and do not grow BASIC_BLOCK chain and should - be used directly only by CFG construction code. - END can be NULL in to create new empty basic block before HEAD. - Both END and HEAD can be NULL to create basic block at the end of - INSN chain. */ +/* Create a new basic block consisting of the instructions between HEAD and END + inclusive. This function is designed to allow fast BB construction - reuses + the note and basic block struct in BB_NOTE, if any and do not grow + BASIC_BLOCK chain and should be used directly only by CFG construction code. + END can be NULL in to create new empty basic block before HEAD. Both END + and HEAD can be NULL to create basic block at the end of INSN chain. */ basic_block create_basic_block_structure (index, head, end, bb_note) @@ -252,10 +234,8 @@ create_basic_block_structure (index, head, end, bb_note) bb = alloc_block (); if (!head && !end) - { - head = end = bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, - get_last_insn ()); - } + head = end = bb_note + = emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ()); else if (GET_CODE (head) == CODE_LABEL && end) { bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head); @@ -269,6 +249,7 @@ create_basic_block_structure (index, head, end, bb_note) if (!end) end = head; } + NOTE_BASIC_BLOCK (bb_note) = bb; } @@ -290,11 +271,10 @@ create_basic_block_structure (index, head, end, bb_note) return bb; } -/* Create new basic block consisting of instructions in between HEAD and - END and place it to the BB chain at position INDEX. - END can be NULL in to create new empty basic block before HEAD. - Both END and HEAD can be NULL to create basic block at the end of - INSN chain. */ +/* Create new basic block consisting of instructions in between HEAD and END + and place it to the BB chain at position INDEX. END can be NULL in to + create new empty basic block before HEAD. Both END and HEAD can be NULL to + create basic block at the end of INSN chain. */ basic_block create_basic_block (index, head, end) @@ -313,6 +293,7 @@ create_basic_block (index, head, end) for (i = n_basic_blocks - 1; i > index; --i) { basic_block tmp = BASIC_BLOCK (i - 1); + BASIC_BLOCK (i) = tmp; tmp->index = i; } @@ -397,23 +378,22 @@ compute_bb_for_insn (max) if (basic_block_for_insn) VARRAY_FREE (basic_block_for_insn); + VARRAY_BB_INIT (basic_block_for_insn, max, "basic_block_for_insn"); for (i = 0; i < n_basic_blocks; ++i) { basic_block bb = BASIC_BLOCK (i); - rtx insn, end; + rtx end = bb->end; + rtx insn; - end = bb->end; - insn = bb->head; - while (1) + for (insn = bb->head; ; insn = NEXT_INSN (insn)) { - int uid = INSN_UID (insn); - if (uid < max) - VARRAY_BB (basic_block_for_insn, uid) = bb; + if (INSN_UID (insn) < max) + VARRAY_BB (basic_block_for_insn, INSN_UID (insn)) = bb; + if (insn == end) break; - insn = NEXT_INSN (insn); } } } @@ -425,6 +405,7 @@ free_bb_for_insn () { if (basic_block_for_insn) VARRAY_FREE (basic_block_for_insn); + basic_block_for_insn = 0; } @@ -442,7 +423,6 @@ update_bb_for_insn (bb) for (insn = bb->head; ; insn = NEXT_INSN (insn)) { set_block_for_insn (insn, bb); - if (insn == bb->end) break; } @@ -456,15 +436,15 @@ set_block_for_insn (insn, bb) basic_block bb; { size_t uid = INSN_UID (insn); + if (uid >= basic_block_for_insn->num_elements) { - int new_size; - /* Add one-eighth the size so we don't keep calling xrealloc. */ - new_size = uid + (uid + 7) / 8; + size_t new_size = uid + (uid + 7) / 8; VARRAY_GROW (basic_block_for_insn, new_size); } + VARRAY_BB (basic_block_for_insn, uid) = bb; } @@ -528,37 +508,37 @@ void merge_blocks_nomove (a, b) basic_block a, b; { - edge e; - rtx b_head, b_end, a_end; + rtx b_head = b->head, b_end = b->end, a_end = a->end; rtx del_first = NULL_RTX, del_last = NULL_RTX; int b_empty = 0; + edge e; /* If there was a CODE_LABEL beginning B, delete it. */ - b_head = b->head; - b_end = b->end; if (GET_CODE (b_head) == CODE_LABEL) { /* Detect basic blocks with nothing but a label. This can happen in particular at the end of a function. */ if (b_head == b_end) b_empty = 1; + del_first = del_last = b_head; b_head = NEXT_INSN (b_head); } - /* Delete the basic block note. */ + /* Delete the basic block note and handle blocks containing just that + note. */ if (NOTE_INSN_BASIC_BLOCK_P (b_head)) { if (b_head == b_end) b_empty = 1; if (! del_last) del_first = b_head; + del_last = b_head; b_head = NEXT_INSN (b_head); } /* If there was a jump out of A, delete it. */ - a_end = a->end; if (GET_CODE (a_end) == JUMP_INSN) { rtx prev; @@ -577,6 +557,7 @@ merge_blocks_nomove (a, b) if (only_sets_cc0_p (prev)) { rtx tmp = prev; + prev = prev_nonnote_insn (prev); if (!prev) prev = a->head; @@ -614,22 +595,24 @@ merge_blocks_nomove (a, b) /* Reassociate the insns of B with A. */ if (!b_empty) { - rtx x = a_end; if (basic_block_for_insn) { - BLOCK_FOR_INSN (x) = a; - while (x != b_end) - { - x = NEXT_INSN (x); - BLOCK_FOR_INSN (x) = a; - } + rtx x; + + for (x = a_end; x != b_end; x = NEXT_INSN (x)) + BLOCK_FOR_INSN (x) = a; + + BLOCK_FOR_INSN (b_end) = a; } + a_end = b_end; } + a->end = a_end; } -/* Return label in the head of basic block. Create one if it doesn't exist. */ +/* Return the label in the head of basic block BLOCK. Create one if it doesn't + exist. */ rtx block_label (block) @@ -637,21 +620,21 @@ block_label (block) { if (block == EXIT_BLOCK_PTR) return NULL_RTX; + if (GET_CODE (block->head) != CODE_LABEL) { block->head = emit_label_before (gen_label_rtx (), block->head); if (basic_block_for_insn) set_block_for_insn (block->head, block); } + return block->head; } /* Attempt to perform edge redirection by replacing possibly complex jump - instruction by unconditional jump or removing jump completely. - This can apply only if all edges now point to the same block. - - The parameters and return values are equivalent to redirect_edge_and_branch. - */ + instruction by unconditional jump or removing jump completely. This can + apply only if all edges now point to the same block. The parameters and + return values are equivalent to redirect_edge_and_branch. */ static bool try_redirect_by_replacing_jump (e, target) @@ -668,6 +651,7 @@ try_redirect_by_replacing_jump (e, target) for (tmp = src->succ; tmp; tmp = tmp->succ_next) if (tmp->dest != target && tmp != e) break; + if (tmp || !onlyjump_p (insn)) return false; @@ -694,6 +678,7 @@ try_redirect_by_replacing_jump (e, target) /* Selectively unlink whole insn chain. */ delete_insn_chain (kill_from, PREV_INSN (target->head)); } + /* If this already is simplejump, redirect it. */ else if (simplejump_p (insn)) { @@ -704,6 +689,7 @@ try_redirect_by_replacing_jump (e, target) INSN_UID (insn), e->dest->index, target->index); redirect_jump (insn, block_label (target), 0); } + /* Or replace possibly complicated jump insn by simple jump insn. */ else { @@ -732,6 +718,7 @@ try_redirect_by_replacing_jump (e, target) e->flags = EDGE_FALLTHRU; else e->flags = 0; + e->probability = REG_BR_PROB_BASE; e->count = src->count; @@ -743,43 +730,41 @@ try_redirect_by_replacing_jump (e, target) if (e->dest != target) redirect_edge_succ (e, target); + return true; } /* Return last loop_beg note appearing after INSN, before start of next basic block. Return INSN if there are no such notes. - When emitting jump to redirect an fallthru edge, it should always - appear after the LOOP_BEG notes, as loop optimizer expect loop to - either start by fallthru edge or jump following the LOOP_BEG note - jumping to the loop exit test. */ + When emitting jump to redirect an fallthru edge, it should always appear + after the LOOP_BEG notes, as loop optimizer expect loop to either start by + fallthru edge or jump following the LOOP_BEG note jumping to the loop exit + test. */ static rtx last_loop_beg_note (insn) rtx insn; { rtx last = insn; - insn = NEXT_INSN (insn); - while (insn && GET_CODE (insn) == NOTE - && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK) - { - if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG) - last = insn; - insn = NEXT_INSN (insn); - } + + for (insn = NEXT_INSN (insn); insn && GET_CODE (insn) == NOTE + && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK; + insn = NEXT_INSN (insn)) + if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG) + last = insn; + return last; } -/* Attempt to change code to redirect edge E to TARGET. - Don't do that on expense of adding new instructions or reordering - basic blocks. +/* Attempt to change code to redirect edge E to TARGET. Don't do that on + expense of adding new instructions or reordering basic blocks. - Function can be also called with edge destination equivalent to the - TARGET. Then it should try the simplifications and do nothing if - none is possible. + Function can be also called with edge destination equivalent to the TARGET. + Then it should try the simplifications and do nothing if none is possible. - Return true if transformation succeeded. We still return false in case - E already destinated TARGET and we didn't managed to simplify instruction + Return true if transformation succeeded. We still return false in case E + already destinated TARGET and we didn't managed to simplify instruction stream. */ bool @@ -797,6 +782,7 @@ redirect_edge_and_branch (e, target) if (try_redirect_by_replacing_jump (e, target)) return true; + /* Do this fast path late, as we want above code to simplify for cases where called on single edge leaving basic block containing nontrivial jump insn. */ @@ -806,7 +792,7 @@ redirect_edge_and_branch (e, target) /* We can only redirect non-fallthru edges of jump insn. */ if (e->flags & EDGE_FALLTHRU) return false; - if (GET_CODE (insn) != JUMP_INSN) + else if (GET_CODE (insn) != JUMP_INSN) return false; /* Recognize a tablejump and adjust all matching cases. */ @@ -851,27 +837,26 @@ redirect_edge_and_branch (e, target) /* ?? We may play the games with moving the named labels from one basic block to the other in case only one computed_jump is available. */ - if (computed_jump_p (insn)) - return false; - - /* A return instruction can't be redirected. */ - if (returnjump_p (insn)) + if (computed_jump_p (insn) + /* A return instruction can't be redirected. */ + || returnjump_p (insn)) return false; /* If the insn doesn't go where we think, we're confused. */ - if (JUMP_LABEL (insn) != old_label) - abort (); - /* If the substitution doesn't succeed, die. This can happen - if the back end emitted unrecognizable instructions. */ - if (! redirect_jump (insn, block_label (target), 0)) + if (JUMP_LABEL (insn) != old_label + /* If the substitution doesn't succeed, die. This can happen + if the back end emitted unrecognizable instructions. */ + || !redirect_jump (insn, block_label (target), 0)) abort (); } if (rtl_dump_file) fprintf (rtl_dump_file, "Edge %i->%i redirected to %i\n", e->src->index, e->dest->index, target->index); + if (e->dest != target) redirect_edge_succ_nodup (e, target); + return true; } @@ -889,23 +874,24 @@ force_nonfallthru_and_redirect (e, target) if (e->flags & EDGE_ABNORMAL) abort (); - if (!(e->flags & EDGE_FALLTHRU)) + else if (!(e->flags & EDGE_FALLTHRU)) abort (); - if (e->src->succ->succ_next) + else if (e->src->succ->succ_next) { /* Create the new structures. */ note = last_loop_beg_note (e->src->end); - jump_block = create_basic_block (e->src->index + 1, NEXT_INSN (note), NULL); + jump_block + = create_basic_block (e->src->index + 1, NEXT_INSN (note), NULL); jump_block->count = e->count; jump_block->frequency = EDGE_FREQUENCY (e); jump_block->loop_depth = target->loop_depth; if (target->global_live_at_start) { - jump_block->global_live_at_start = - OBSTACK_ALLOC_REG_SET (&flow_obstack); - jump_block->global_live_at_end = - OBSTACK_ALLOC_REG_SET (&flow_obstack); + jump_block->global_live_at_start + = OBSTACK_ALLOC_REG_SET (&flow_obstack); + jump_block->global_live_at_end + = OBSTACK_ALLOC_REG_SET (&flow_obstack); COPY_REG_SET (jump_block->global_live_at_start, target->global_live_at_start); COPY_REG_SET (jump_block->global_live_at_end, @@ -925,6 +911,7 @@ force_nonfallthru_and_redirect (e, target) } else jump_block = e->src; + e->flags &= ~EDGE_FALLTHRU; if (target == EXIT_BLOCK_PTR) { @@ -940,6 +927,7 @@ force_nonfallthru_and_redirect (e, target) JUMP_LABEL (jump_block->end) = label; LABEL_NUSES (label)++; } + emit_barrier_after (jump_block->end); redirect_edge_succ_nodup (e, target); @@ -949,6 +937,7 @@ force_nonfallthru_and_redirect (e, target) /* Edge E is assumed to be fallthru edge. Emit needed jump instruction (and possibly create new basic block) to make edge non-fallthru. Return newly created BB or NULL if none. */ + basic_block force_nonfallthru (e) edge e; @@ -965,17 +954,13 @@ redirect_edge_and_branch_force (e, target) edge e; basic_block target; { - basic_block new_bb; - - if (redirect_edge_and_branch (e, target)) - return NULL; - if (e->dest == target) + if (redirect_edge_and_branch (e, target) + || e->dest == target) return NULL; /* In case the edge redirection failed, try to force it to be non-fallthru and redirect newly created simplejump. */ - new_bb = force_nonfallthru_and_redirect (e, target); - return new_bb; + return force_nonfallthru_and_redirect (e, target); } /* The given edge should potentially be a fallthru edge. If that is in @@ -1042,7 +1027,7 @@ tidy_fallthru_edges () { int i; - for (i = 1; i < n_basic_blocks; ++i) + for (i = 1; i < n_basic_blocks; i++) { basic_block b = BASIC_BLOCK (i - 1); basic_block c = BASIC_BLOCK (i); @@ -1059,6 +1044,7 @@ tidy_fallthru_edges () Furthermore, the edge will be marked as a fallthru because we merge the flags for the duplicate edges. So we do not want to check that the edge is not a FALLTHRU edge. */ + if ((s = b->succ) != NULL && ! (s->flags & EDGE_COMPLEX) && s->succ_next == NULL @@ -1082,8 +1068,7 @@ back_edge_of_syntactic_loop_p (bb1, bb2) if (bb1->index > bb2->index) return false; - - if (bb1->index == bb2->index) + else if (bb1->index == bb2->index) return true; for (insn = bb1->end; insn != bb2->head && count >= 0; @@ -1092,7 +1077,7 @@ back_edge_of_syntactic_loop_p (bb1, bb2) { if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG) count++; - if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END) + else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END) count--; } @@ -1123,6 +1108,7 @@ split_edge (edge_in) if ((edge_in->flags & EDGE_FALLTHRU) == 0) { edge e; + for (e = edge_in->dest->pred; e; e = e->pred_next) if (e->flags & EDGE_FALLTHRU) break; @@ -1152,7 +1138,8 @@ split_edge (edge_in) if (edge_in->dest != EXIT_BLOCK_PTR && PREV_INSN (edge_in->dest->head) && GET_CODE (PREV_INSN (edge_in->dest->head)) == NOTE - && NOTE_LINE_NUMBER (PREV_INSN (edge_in->dest->head)) == NOTE_INSN_LOOP_BEG + && (NOTE_LINE_NUMBER (PREV_INSN (edge_in->dest->head)) + == NOTE_INSN_LOOP_BEG) && !back_edge_of_syntactic_loop_p (edge_in->dest, edge_in->src)) before = PREV_INSN (edge_in->dest->head); else if (edge_in->dest != EXIT_BLOCK_PTR) @@ -1170,8 +1157,10 @@ split_edge (edge_in) { bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack); bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack); - COPY_REG_SET (bb->global_live_at_start, edge_in->dest->global_live_at_start); - COPY_REG_SET (bb->global_live_at_end, edge_in->dest->global_live_at_start); + COPY_REG_SET (bb->global_live_at_start, + edge_in->dest->global_live_at_start); + COPY_REG_SET (bb->global_live_at_end, + edge_in->dest->global_live_at_start); } edge_out = make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU); @@ -1254,6 +1243,7 @@ commit_one_edge_insertion (e) && e->src != ENTRY_BLOCK_PTR) { bb = e->src; + /* It is possible to have a non-simple jump here. Consider a target where some forms of unconditional jumps clobber a register. This happens on the fr30 for example. @@ -1261,12 +1251,11 @@ commit_one_edge_insertion (e) We know this block has a single successor, so we can just emit the queued insns before the jump. */ if (GET_CODE (bb->end) == JUMP_INSN) - { - before = bb->end; - while (GET_CODE (PREV_INSN (before)) == NOTE - && NOTE_LINE_NUMBER (PREV_INSN (before)) == NOTE_INSN_LOOP_BEG) - before = PREV_INSN (before); - } + for (before = bb->end; + GET_CODE (PREV_INSN (before)) == NOTE + && NOTE_LINE_NUMBER (PREV_INSN (before)) == NOTE_INSN_LOOP_BEG; + before = PREV_INSN (before)) + ; else { /* We'd better be fallthru, or we've lost track of what's what. */ @@ -1306,8 +1295,8 @@ commit_one_edge_insertion (e) || e->succ_next != NULL || (e->flags & EDGE_FALLTHRU) == 0) abort (); - e->flags &= ~EDGE_FALLTHRU; + e->flags &= ~EDGE_FALLTHRU; emit_barrier_after (last); if (before) @@ -1315,6 +1304,7 @@ commit_one_edge_insertion (e) } else if (GET_CODE (last) == JUMP_INSN) abort (); + find_sub_basic_blocks (bb); } @@ -1374,8 +1364,7 @@ dump_bb (bb, outf) dump_regset (bb->global_live_at_start, outf); putc ('\n', outf); - for (insn = bb->head, last = NEXT_INSN (bb->end); - insn != last; + for (insn = bb->head, last = NEXT_INSN (bb->end); insn != last; insn = NEXT_INSN (insn)) print_rtl_single (outf, insn); @@ -1420,12 +1409,12 @@ print_rtl_with_bb (outf, rtx_first) int i; enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB }; int max_uid = get_max_uid (); - basic_block *start = (basic_block *) - xcalloc (max_uid, sizeof (basic_block)); - basic_block *end = (basic_block *) - xcalloc (max_uid, sizeof (basic_block)); - enum bb_state *in_bb_p = (enum bb_state *) - xcalloc (max_uid, sizeof (enum bb_state)); + basic_block *start + = (basic_block *) xcalloc (max_uid, sizeof (basic_block)); + basic_block *end + = (basic_block *) xcalloc (max_uid, sizeof (basic_block)); + enum bb_state *in_bb_p + = (enum bb_state *) xcalloc (max_uid, sizeof (enum bb_state)); for (i = n_basic_blocks - 1; i >= 0; i--) { @@ -1437,6 +1426,7 @@ print_rtl_with_bb (outf, rtx_first) for (x = bb->head; x != NULL_RTX; x = NEXT_INSN (x)) { enum bb_state state = IN_MULTIPLE_BB; + if (in_bb_p[INSN_UID (x)] == NOT_IN_BB) state = IN_ONE_BB; in_bb_p[INSN_UID (x)] = state; @@ -1508,7 +1498,7 @@ print_rtl_with_bb (outf, rtx_first) - scans body of the basic block for JUMP_INSN, CODE_LABEL and NOTE_INSN_BASIC_BLOCK - check that all insns are in the basic blocks - (except the switch handling code, barriers and notes) + (except the switch handling code, barriers and notes) - check that all returns are followed by barriers In future it can be extended check a lot of other stuff as well @@ -1540,6 +1530,7 @@ verify_flow_info () for (x = last_head; x != NULL_RTX; x = PREV_INSN (x)) if (x == end) break; + if (!x) { error ("end insn %d for block %d not found in the insn stream", @@ -1560,6 +1551,7 @@ verify_flow_info () INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index); err = 1; } + bb_info[INSN_UID (x)] = bb; if (x == head) @@ -1582,8 +1574,7 @@ verify_flow_info () int has_fallthru = 0; edge e; - e = bb->succ; - while (e) + for (e = bb->succ; e; e = e->succ_next) { if (last_visited [e->dest->index + 2] == bb) { @@ -1591,6 +1582,7 @@ verify_flow_info () e->src->index, e->dest->index); err = 1; } + last_visited [e->dest->index + 2] = bb; if (e->flags & EDGE_FALLTHRU) @@ -1601,21 +1593,24 @@ verify_flow_info () && e->dest != EXIT_BLOCK_PTR) { rtx insn; + if (e->src->index + 1 != e->dest->index) { - error ("verify_flow_info: Incorrect blocks for fallthru %i->%i", - e->src->index, e->dest->index); - err = 1; + error + ("verify_flow_info: Incorrect blocks for fallthru %i->%i", + e->src->index, e->dest->index); + err = 1; } else for (insn = NEXT_INSN (e->src->end); insn != e->dest->head; insn = NEXT_INSN (insn)) if (GET_CODE (insn) == BARRIER #ifndef CASE_DROPS_THROUGH - || INSN_P (insn)) + || INSN_P (insn) #else - || (INSN_P (insn) && ! JUMP_TABLE_DATA_P (insn))) + || (INSN_P (insn) && ! JUMP_TABLE_DATA_P (insn)) #endif + ) { error ("verify_flow_info: Incorrect fallthru %i->%i", e->src->index, e->dest->index); @@ -1623,6 +1618,7 @@ verify_flow_info () err = 1; } } + if (e->src != bb) { error ("verify_flow_info: Basic block %d succ edge is corrupted", @@ -1634,9 +1630,10 @@ verify_flow_info () fprintf (stderr, "\n"); err = 1; } + edge_checksum[e->dest->index + 2] += (size_t) e; - e = e->succ_next; } + if (!has_fallthru) { rtx insn; @@ -1654,8 +1651,7 @@ verify_flow_info () } } - e = bb->pred; - while (e) + for (e = bb->pred; e; e = e->pred_next) { if (e->dest != bb) { @@ -1668,20 +1664,23 @@ verify_flow_info () err = 1; } edge_checksum[e->dest->index + 2] -= (size_t) e; - e = e->pred_next; } - for (x = bb->head; x != NEXT_INSN (bb->end); x = NEXT_INSN (x)) - if (basic_block_for_insn && BLOCK_FOR_INSN (x) != bb) - { - debug_rtx (x); - if (! BLOCK_FOR_INSN (x)) - error ("insn %d is inside basic block %d but block_for_insn is NULL", - INSN_UID (x), bb->index); - else - error ("insn %d is inside basic block %d but block_for_insn is %i", - INSN_UID (x), bb->index, BLOCK_FOR_INSN (x)->index); - err = 1; - } + + for (x = bb->head; x != NEXT_INSN (bb->end); x = NEXT_INSN (x)) + if (basic_block_for_insn && BLOCK_FOR_INSN (x) != bb) + { + debug_rtx (x); + if (! BLOCK_FOR_INSN (x)) + error + ("insn %d inside basic block %d but block_for_insn is NULL", + INSN_UID (x), bb->index); + else + error + ("insn %d inside basic block %d but block_for_insn is %i", + INSN_UID (x), bb->index, BLOCK_FOR_INSN (x)->index); + + err = 1; + } /* OK pointers are correct. Now check the header of basic block. It ought to contain optional CODE_LABEL followed @@ -1695,8 +1694,10 @@ verify_flow_info () bb->index); err = 1; } + x = NEXT_INSN (x); } + if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb) { error ("NOTE_INSN_BASIC_BLOCK is missing for block %d", @@ -1705,42 +1706,38 @@ verify_flow_info () } if (bb->end == x) - { - /* Do checks for empty blocks here */ - } + /* Do checks for empty blocks her. e */ + ; else - { - x = NEXT_INSN (x); - while (x) - { - if (NOTE_INSN_BASIC_BLOCK_P (x)) - { - error ("NOTE_INSN_BASIC_BLOCK %d in the middle of basic block %d", - INSN_UID (x), bb->index); - err = 1; - } - - if (x == bb->end) - break; - - if (GET_CODE (x) == JUMP_INSN - || GET_CODE (x) == CODE_LABEL - || GET_CODE (x) == BARRIER) - { - error ("in basic block %d:", bb->index); - fatal_insn ("flow control insn inside a basic block", x); - } + for (x = NEXT_INSN (x); x; x = NEXT_INSN (x)) + { + if (NOTE_INSN_BASIC_BLOCK_P (x)) + { + error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d", + INSN_UID (x), bb->index); + err = 1; + } + + if (x == bb->end) + break; - x = NEXT_INSN (x); - } - } + if (GET_CODE (x) == JUMP_INSN + || GET_CODE (x) == CODE_LABEL + || GET_CODE (x) == BARRIER) + { + error ("in basic block %d:", bb->index); + fatal_insn ("flow control insn inside a basic block", x); + } + } } /* Complete edge checksumming for ENTRY and EXIT. */ { edge e; + for (e = ENTRY_BLOCK_PTR->succ; e ; e = e->succ_next) edge_checksum[e->dest->index + 2] += (size_t) e; + for (e = EXIT_BLOCK_PTR->pred; e ; e = e->pred_next) edge_checksum[e->dest->index + 2] -= (size_t) e; } @@ -1754,12 +1751,12 @@ verify_flow_info () last_bb_num_seen = -1; num_bb_notes = 0; - x = rtx_first; - while (x) + for (x = rtx_first; x; x = NEXT_INSN (x)) { if (NOTE_INSN_BASIC_BLOCK_P (x)) { basic_block bb = NOTE_BASIC_BLOCK (x); + num_bb_notes++; if (bb->index != last_bb_num_seen + 1) internal_error ("basic blocks not numbered consecutively"); @@ -1781,9 +1778,7 @@ verify_flow_info () && GET_CODE (NEXT_INSN (x)) == JUMP_INSN && (GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_DIFF_VEC || GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_VEC)) - { - x = NEXT_INSN (x); - } + x = NEXT_INSN (x); /* But in any case, non-deletable labels can appear anywhere. */ break; @@ -1798,8 +1793,6 @@ verify_flow_info () && returnjump_p (x) && ! condjump_p (x) && ! (NEXT_INSN (x) && GET_CODE (NEXT_INSN (x)) == BARRIER)) fatal_insn ("return not followed by barrier", x); - - x = NEXT_INSN (x); } if (num_bb_notes != n_basic_blocks) @@ -1828,17 +1821,21 @@ purge_dead_edges (bb) rtx insn = bb->end, note; bool purged = false; + /* ??? This makes no sense since the later test includes more cases. */ if (GET_CODE (insn) == JUMP_INSN && !simplejump_p (insn)) return false; + if (GET_CODE (insn) == JUMP_INSN) { rtx note; edge b,f; + /* We do care only about conditional jumps and simplejumps. */ if (!any_condjump_p (insn) && !returnjump_p (insn) && !simplejump_p (insn)) return false; + for (e = bb->succ; e; e = next) { next = e->succ_next; @@ -1852,19 +1849,23 @@ purge_dead_edges (bb) if ((e->flags & EDGE_FALLTHRU) && any_condjump_p (insn)) continue; - if (e->dest != EXIT_BLOCK_PTR - && e->dest->head == JUMP_LABEL (insn)) + else if (e->dest != EXIT_BLOCK_PTR + && e->dest->head == JUMP_LABEL (insn)) continue; - if (e->dest == EXIT_BLOCK_PTR - && returnjump_p (insn)) + else if (e->dest == EXIT_BLOCK_PTR + && returnjump_p (insn)) continue; + purged = true; remove_edge (e); } + if (!bb->succ || !purged) return false; + if (rtl_dump_file) fprintf (rtl_dump_file, "Purged edges from bb %i\n", bb->index); + if (!optimize) return purged; @@ -1879,6 +1880,7 @@ purge_dead_edges (bb) note = find_reg_note (insn, REG_BR_PROB, NULL); if (!note) return purged; + b = BRANCH_EDGE (bb); f = FALLTHRU_EDGE (bb); b->probability = INTVAL (XEXP (note, 0)); @@ -1886,6 +1888,7 @@ purge_dead_edges (bb) b->count = bb->count * b->probability / REG_BR_PROB_BASE; f->count = bb->count * f->probability / REG_BR_PROB_BASE; } + return purged; } @@ -1894,6 +1897,7 @@ purge_dead_edges (bb) && (note = find_reg_note (insn, REG_EH_REGION, NULL))) { rtx eqnote; + if (! may_trap_p (PATTERN (insn)) || ((eqnote = find_reg_equal_equiv_note (insn)) && ! may_trap_p (XEXP (eqnote, 0)))) @@ -1919,17 +1923,22 @@ purge_dead_edges (bb) edge we know that there used to be a jump here and can then safely remove all non-fallthru edges. */ for (e = bb->succ; e && (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU)); - e = e->succ_next); + e = e->succ_next) + ; + if (!e) return purged; + for (e = bb->succ; e; e = next) { next = e->succ_next; if (!(e->flags & EDGE_FALLTHRU)) remove_edge (e), purged = true; } + if (!bb->succ || bb->succ->succ_next) abort (); + bb->succ->probability = REG_BR_PROB_BASE; bb->succ->count = bb->count; @@ -1939,10 +1948,8 @@ purge_dead_edges (bb) return purged; } -/* Search all basic blocks for potentially dead edges and purge them. - - Return true iff some edge has been eliminated. - */ +/* Search all basic blocks for potentially dead edges and purge them. Return + true if some edge has been eliminated. */ bool purge_all_dead_edges (update_life_p) @@ -1956,18 +1963,21 @@ purge_all_dead_edges (update_life_p) blocks = sbitmap_alloc (n_basic_blocks); sbitmap_zero (blocks); } + for (i = 0; i < n_basic_blocks; i++) { - bool purged_here; - purged_here = purge_dead_edges (BASIC_BLOCK (i)); + bool purged_here = purge_dead_edges (BASIC_BLOCK (i)); + purged |= purged_here; if (purged_here && update_life_p) SET_BIT (blocks, i); } + if (update_life_p && purged) update_life_info (blocks, UPDATE_LIFE_GLOBAL, PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE | PROP_KILL_DEAD_CODE); + if (update_life_p) sbitmap_free (blocks); return purged; diff --git a/gcc/rtl.h b/gcc/rtl.h index e4360d620d2..676d4ace938 100644 --- a/gcc/rtl.h +++ b/gcc/rtl.h @@ -1483,6 +1483,7 @@ typedef int (*rtx_function) PARAMS ((rtx *, void *)); extern int for_each_rtx PARAMS ((rtx *, rtx_function, void *)); extern rtx regno_use_in PARAMS ((unsigned int, rtx)); extern int auto_inc_p PARAMS ((rtx)); +extern int in_expr_list_p PARAMS ((rtx, rtx)); extern void remove_node_from_expr_list PARAMS ((rtx, rtx *)); extern int insns_safe_to_move_p PARAMS ((rtx, rtx, rtx *)); extern int loc_mentioned_in_p PARAMS ((rtx *, rtx)); diff --git a/gcc/rtlanal.c b/gcc/rtlanal.c index b6056de14a1..427e3fbe921 100644 --- a/gcc/rtlanal.c +++ b/gcc/rtlanal.c @@ -1953,6 +1953,24 @@ remove_note (insn, note) abort (); } +/* Search LISTP (an EXPR_LIST) for an entry whose first operand is NODE and + return 1 if it is found. A simple equality test is used to determine if + NODE matches. */ + +int +in_expr_list_p (listp, node) + rtx listp; + rtx node; +{ + rtx x; + + for (x = listp; x; x = XEXP (x, 1)) + if (node == XEXP (x, 0)) + return 1; + + return 0; +} + /* Search LISTP (an EXPR_LIST) for an entry whose first operand is NODE and remove that entry from the list if it is found. -- 2.30.2