diff options
author | obrien <obrien@FreeBSD.org> | 2002-02-01 18:16:02 +0000 |
---|---|---|
committer | obrien <obrien@FreeBSD.org> | 2002-02-01 18:16:02 +0000 |
commit | c9ab9ae440a8066b2c2b85b157b1fdadcf09916a (patch) | |
tree | 086d9d6c8fbd4fc8fe4495059332f66bc0f8d12b /contrib/gcc/cfglayout.c | |
parent | 2ecfd8bd04b63f335c1ec6295740a4bfd97a4fa6 (diff) | |
download | FreeBSD-src-c9ab9ae440a8066b2c2b85b157b1fdadcf09916a.zip FreeBSD-src-c9ab9ae440a8066b2c2b85b157b1fdadcf09916a.tar.gz |
Enlist the FreeBSD-CURRENT users as testers of what is to become Gcc 3.1.0.
These bits are taken from the FSF anoncvs repo on 1-Feb-2002 08:20 PST.
Diffstat (limited to 'contrib/gcc/cfglayout.c')
-rw-r--r-- | contrib/gcc/cfglayout.c | 596 |
1 files changed, 596 insertions, 0 deletions
diff --git a/contrib/gcc/cfglayout.c b/contrib/gcc/cfglayout.c new file mode 100644 index 0000000..329e9f8 --- /dev/null +++ b/contrib/gcc/cfglayout.c @@ -0,0 +1,596 @@ +/* Basic block reordering routines for the GNU compiler. + Copyright (C) 2000, 2001 Free Software Foundation, Inc. + +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 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. */ + +#include "config.h" +#include "system.h" +#include "tree.h" +#include "rtl.h" +#include "hard-reg-set.h" +#include "basic-block.h" +#include "insn-config.h" +#include "output.h" +#include "function.h" +#include "obstack.h" +#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. */ +extern struct obstack flow_obstack; + +/* Holds the interesting trailing notes for the function. */ +static rtx function_tail_eff_head; + +static rtx skip_insns_after_block PARAMS ((basic_block)); +static void record_effective_endpoints PARAMS ((void)); +static rtx label_for_bb PARAMS ((basic_block)); +static void fixup_reorder_chain PARAMS ((void)); + +static void set_block_levels PARAMS ((tree, int)); +static void change_scope PARAMS ((rtx, tree, tree)); + +void verify_insn_chain PARAMS ((void)); +static void fixup_fallthru_exit_predecessor PARAMS ((void)); + +/* Map insn uid to lexical block. */ +static varray_type insn_scopes; + +/* Skip over inter-block insns occurring after BB which are typically + associated with BB (e.g., barriers). If there are any such insns, + we return the last one. Otherwise, we return the end of BB. */ + +static rtx +skip_insns_after_block (bb) + basic_block bb; +{ + rtx insn, last_insn, next_head, prev; + + next_head = NULL_RTX; + 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)) != 0; ) + { + if (insn == next_head) + break; + + switch (GET_CODE (insn)) + { + case BARRIER: + last_insn = insn; + continue; + + case NOTE: + switch (NOTE_LINE_NUMBER (insn)) + { + case NOTE_INSN_LOOP_END: + case NOTE_INSN_BLOCK_END: + last_insn = insn; + continue; + case NOTE_INSN_DELETED: + case NOTE_INSN_DELETED_LABEL: + continue; + + default: + continue; + break; + } + break; + + case CODE_LABEL: + if (NEXT_INSN (insn) + && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN + && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC + || GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_DIFF_VEC)) + { + insn = NEXT_INSN (insn); + last_insn = insn; + continue; + } + break; + + default: + break; + } + + break; + } + + /* 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. 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)) + { + case NOTE_INSN_LOOP_END: + case NOTE_INSN_BLOCK_END: + case NOTE_INSN_DELETED: + case NOTE_INSN_DELETED_LABEL: + continue; + default: + reorder_insns (insn, insn, last_insn); + } + } + + return last_insn; +} + +/* Locate or create a label for a given basic block. */ + +static rtx +label_for_bb (bb) + basic_block bb; +{ + rtx label = bb->head; + + if (GET_CODE (label) != CODE_LABEL) + { + if (rtl_dump_file) + 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)) + RBI (bb)->eff_head = label; + } + + return label; +} + +/* Locate the effective beginning and end of the insn chain for each + block, as defined by skip_insns_after_block above. */ + +static void +record_effective_endpoints () +{ + rtx next_insn = get_insns (); + int i; + + for (i = 0; i < n_basic_blocks; i++) + { + basic_block bb = BASIC_BLOCK (i); + rtx end; + + RBI (bb)->eff_head = next_insn; + end = skip_insns_after_block (bb); + RBI (bb)->eff_end = end; + next_insn = NEXT_INSN (end); + } + + function_tail_eff_head = next_insn; +} + +/* Build a varray mapping INSN_UID to lexical block. Return it. */ + +void +scope_to_insns_initialize () +{ + tree block = NULL; + rtx insn, next; + + VARRAY_TREE_INIT (insn_scopes, get_max_uid (), "insn scopes"); + + for (insn = get_insns (); insn; insn = next) + { + next = NEXT_INSN (insn); + + if (active_insn_p (insn) + && GET_CODE (PATTERN (insn)) != ADDR_VEC + && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC) + VARRAY_TREE (insn_scopes, INSN_UID (insn)) = block; + else if (GET_CODE (insn) == NOTE) + { + switch (NOTE_LINE_NUMBER (insn)) + { + case NOTE_INSN_BLOCK_BEG: + block = NOTE_BLOCK (insn); + delete_insn (insn); + break; + case NOTE_INSN_BLOCK_END: + block = BLOCK_SUPERCONTEXT (block); + delete_insn (insn); + break; + default: + break; + } + } + } +} + +/* For each lexical block, set BLOCK_NUMBER to the depth at which it is + found in the block tree. */ + +static void +set_block_levels (block, level) + tree block; + int level; +{ + while (block) + { + BLOCK_NUMBER (block) = level; + set_block_levels (BLOCK_SUBBLOCKS (block), level + 1); + block = BLOCK_CHAIN (block); + } +} + +/* Emit lexical block notes needed to change scope from S1 to S2. */ + +static void +change_scope (orig_insn, s1, s2) + rtx orig_insn; + tree s1, s2; +{ + rtx insn = orig_insn; + tree com = NULL_TREE; + tree ts1 = s1, ts2 = s2; + tree s; + + while (ts1 != ts2) + { + if (ts1 == NULL || ts2 == NULL) + abort (); + if (BLOCK_NUMBER (ts1) > BLOCK_NUMBER (ts2)) + ts1 = BLOCK_SUPERCONTEXT (ts1); + else if (BLOCK_NUMBER (ts1) < BLOCK_NUMBER (ts2)) + ts2 = BLOCK_SUPERCONTEXT (ts2); + else + { + ts1 = BLOCK_SUPERCONTEXT (ts1); + ts2 = BLOCK_SUPERCONTEXT (ts2); + } + } + com = ts1; + + /* Close scopes. */ + s = s1; + while (s != com) + { + rtx note = emit_note_before (NOTE_INSN_BLOCK_END, insn); + NOTE_BLOCK (note) = s; + s = BLOCK_SUPERCONTEXT (s); + } + + /* Open scopes. */ + s = s2; + while (s != com) + { + insn = emit_note_before (NOTE_INSN_BLOCK_BEG, insn); + NOTE_BLOCK (insn) = s; + s = BLOCK_SUPERCONTEXT (s); + } +} + +/* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based + on the scope tree and the newly reordered instructions. */ + +void +scope_to_insns_finalize () +{ + tree cur_block = DECL_INITIAL (cfun->decl); + rtx insn, note; + + /* Tag the blocks with a depth number so that change_scope can find + the common parent easily. */ + set_block_levels (cur_block, 0); + + for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) + { + tree this_block; + + if ((size_t) INSN_UID (insn) >= insn_scopes->num_elements) + continue; + this_block = VARRAY_TREE (insn_scopes, INSN_UID (insn)); + if (! this_block) + continue; + + if (this_block != cur_block) + { + change_scope (insn, cur_block, this_block); + cur_block = this_block; + } + } + + VARRAY_FREE (insn_scopes); + + /* change_scope emits before the insn, not after. */ + note = emit_note (NULL, NOTE_INSN_DELETED); + change_scope (note, cur_block, DECL_INITIAL (cfun->decl)); + delete_insn (note); + + reorder_blocks (); +} + +/* Given a reorder chain, rearrange the code to match. */ + +static void +fixup_reorder_chain () +{ + basic_block bb, last_bb; + int index; + rtx insn; + int old_n_basic_blocks = n_basic_blocks; + + /* First do the bulk reordering -- rechain the blocks without regard to + the needed changes to jumps and labels. */ + + 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; + } + + 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 (); +#endif + + /* Now add jumps and labels as needed to match the blocks new + outgoing edges. */ + + for (bb = BASIC_BLOCK (0); bb ; bb = RBI (bb)->next) + { + edge e_fall, e_taken, e; + rtx bb_end_insn; + basic_block nb; + + if (bb->succ == NULL) + continue; + + /* Find the old fallthru edge, and another non-EH edge for + a taken jump. */ + e_taken = e_fall = NULL; + for (e = bb->succ; e ; e = e->succ_next) + if (e->flags & EDGE_FALLTHRU) + e_fall = e; + else if (! (e->flags & EDGE_EH)) + e_taken = e; + + bb_end_insn = bb->end; + if (GET_CODE (bb_end_insn) == JUMP_INSN) + { + if (any_condjump_p (bb_end_insn)) + { + /* If the old fallthru is still next, nothing to do. */ + if (RBI (bb)->next == e_fall->dest + || (!RBI (bb)->next + && e_fall->dest == EXIT_BLOCK_PTR)) + continue; + + /* There is one special case: if *neither* block is next, + such as happens at the very end of a function, then we'll + need to add a new unconditional jump. Choose the taken + edge based on known or assumed probability. */ + 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, + label_for_bb (e_fall->dest), 0)) + { + e_fall->flags &= ~EDGE_FALLTHRU; + e_taken->flags |= EDGE_FALLTHRU; + update_br_prob_note (bb); + e = e_fall, e_fall = e_taken, e_taken = e; + } + } + + /* Otherwise we can try to invert the jump. This will + basically never fail, however, keep up the pretense. */ + else if (invert_jump (bb_end_insn, + label_for_bb (e_fall->dest), 0)) + { + e_fall->flags &= ~EDGE_FALLTHRU; + e_taken->flags |= EDGE_FALLTHRU; + update_br_prob_note (bb); + continue; + } + } + else if (returnjump_p (bb_end_insn)) + continue; + else + { + /* Otherwise we have some switch or computed jump. In the + 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. */ + if (RBI (bb)->next == e_fall->dest) + continue; + bb_end_insn = skip_insns_after_block (bb); +#else + abort (); +#endif + } + } + else + { + /* No fallthru implies a noreturn function with EH edges, or + something similarly bizarre. In any case, we don't need to + do anything. */ + if (! e_fall) + continue; + + /* If the fallthru block is still next, nothing to do. */ + if (RBI (bb)->next == e_fall->dest) + continue; + + /* 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)); + RBI (nb)->eff_head = nb->head; + RBI (nb)->eff_end = NEXT_INSN (nb->end); + RBI (nb)->visited = 1; + RBI (nb)->next = RBI (bb)->next; + RBI (bb)->next = nb; + /* Don't process this new block. */ + bb = nb; + } + } + + /* Put basic_block_info in the new order. */ + bb = BASIC_BLOCK (0); + index = 0; + + if (rtl_dump_file) + fprintf (rtl_dump_file, "Reordered sequence:\n"); + + 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; + } +} + +/* Perform sanity checks on the insn chain. + 1. Check that next/prev pointers are consistent in both the forward and + reverse direction. + 2. Count insns in chain, going both directions, and check if equal. + 3. Check that get_last_insn () returns the actual end of chain. */ + +void +verify_insn_chain () +{ + rtx x, prevx, nextx; + int insn_cnt1, insn_cnt2; + + 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 (); + + if (prevx != get_last_insn ()) + abort (); + + 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 it is. */ + +static void +fixup_fallthru_exit_predecessor () +{ + edge e; + basic_block bb = NULL; + + 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. */ + +void +cfg_layout_initialize () +{ + alloc_aux_for_blocks (sizeof (struct reorder_block_def)); + + scope_to_insns_initialize (); + + record_effective_endpoints (); +} + +/* 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 + + scope_to_insns_finalize (); + + free_aux_for_blocks (); + +#ifdef ENABLE_CHECKING + verify_flow_info (); +#endif +} |