/* Basic block reordering routines for the GNU compiler.
- Copyright (C) 2000 Free Software Foundation, Inc.
+ 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"
+#include "coretypes.h"
+#include "tm.h"
+#include "tree.h"
#include "rtl.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "function.h"
#include "obstack.h"
#include "cfglayout.h"
+#include "cfgloop.h"
+#include "target.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;
-/* Structure to hold information about lexical scopes. */
-struct scope_def
-{
- int level;
-
- /* The NOTE_INSN_BLOCK_BEG that started this scope. */
- rtx note_beg;
-
- /* The NOTE_INSN_BLOCK_END that ended this scope. */
- rtx note_end;
-
- /* The bb containing note_beg (if any). */
- basic_block bb_beg;
-
- /* The bb containing note_end (if any). */
- basic_block bb_end;
-
- /* List of basic blocks contained within this scope. */
- basic_block *bbs;
-
- /* Number of blocks contained within this scope. */
- int num_bbs;
-
- /* The outer scope or NULL if outermost scope. */
- struct scope_def *outer;
-
- /* The first inner scope or NULL if innermost scope. */
- struct scope_def *inner;
-
- /* The last inner scope or NULL if innermost scope. */
- struct scope_def *inner_last;
-
- /* Link to the next (sibling) scope. */
- struct scope_def *next;
-};
-
-/* Structure to hold information about the scope forest. */
-typedef struct
-{
- /* Number of trees in forest. */
- int num_trees;
-
- /* List of tree roots. */
- scope *trees;
-} scope_forest_info;
-
/* Holds the interesting trailing notes for the function. */
-static rtx function_tail_eff_head;
-
-/* The scope forest of current function. */
-static scope_forest_info forest;
+static rtx function_footer;
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 relate_bbs_with_scopes PARAMS ((scope));
-static scope make_new_scope PARAMS ((int, rtx));
-static void build_scope_forest PARAMS ((scope_forest_info *));
-static void remove_scope_notes PARAMS ((void));
-static void insert_intra_1 PARAMS ((scope, rtx *, basic_block));
-static void insert_intra_bb_scope_notes PARAMS ((basic_block));
-static void insert_inter_bb_scope_notes PARAMS ((basic_block, basic_block));
-static void rebuild_scope_notes PARAMS ((scope_forest_info *));
-static void free_scope_forest_1 PARAMS ((scope));
-static void free_scope_forest PARAMS ((scope_forest_info *));
-void dump_scope_forest PARAMS ((scope_forest_info *));
-static void dump_scope_forest_1 PARAMS ((scope, int));
-
-static rtx get_next_bb_note PARAMS ((rtx));
-static rtx get_prev_bb_note PARAMS ((rtx));
+static void set_block_levels PARAMS ((tree, int));
+static void change_scope PARAMS ((rtx, tree, tree));
void verify_insn_chain PARAMS ((void));
-static basic_block fixup_fallthru_exit_predecesor PARAMS ((void));
+static void cleanup_unconditional_jumps PARAMS ((struct loops *));
+static void fixup_fallthru_exit_predecessor PARAMS ((void));
+static rtx unlink_insn_chain PARAMS ((rtx, rtx));
+static rtx duplicate_insn_chain PARAMS ((rtx, rtx));
+static void break_superblocks PARAMS ((void));
+\f
+static rtx
+unlink_insn_chain (first, last)
+ rtx first;
+ rtx last;
+{
+ rtx prevfirst = PREV_INSN (first);
+ rtx nextlast = NEXT_INSN (last);
+
+ PREV_INSN (first) = NULL;
+ NEXT_INSN (last) = NULL;
+ if (prevfirst)
+ NEXT_INSN (prevfirst) = nextlast;
+ if (nextlast)
+ PREV_INSN (nextlast) = prevfirst;
+ else
+ set_last_insn (prevfirst);
+ if (!prevfirst)
+ set_first_insn (nextlast);
+ return first;
+}
\f
/* Skip over inter-block insns occurring after BB which are typically
associated with BB (e.g., barriers). If there are any such insns,
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;
+ if (bb->next_bb != EXIT_BLOCK_PTR)
+ next_head = bb->next_bb->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;
last_insn = insn;
continue;
}
- break;
+ break;
default:
break;
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))
- {
- 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);
- }
+ 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;
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))
- RBI (bb)->eff_head = label;
}
return label;
record_effective_endpoints ()
{
rtx next_insn = get_insns ();
- int i;
-
- for (i = 0; i < n_basic_blocks; ++i)
+ basic_block bb;
+
+ FOR_EACH_BB (bb)
{
- basic_block bb = BASIC_BLOCK (i);
rtx end;
- RBI (bb)->eff_head = next_insn;
+ if (PREV_INSN (bb->head) && next_insn != bb->head)
+ RBI (bb)->header = unlink_insn_chain (next_insn,
+ PREV_INSN (bb->head));
end = skip_insns_after_block (bb);
- RBI (bb)->eff_end = end;
- next_insn = NEXT_INSN (end);
- }
- function_tail_eff_head = next_insn;
-}
-\f
-static rtx
-get_next_bb_note (x)
- rtx x;
-{
- while (x)
- {
- if (NOTE_INSN_BASIC_BLOCK_P (x))
- return x;
- x = NEXT_INSN (x);
+ if (NEXT_INSN (bb->end) && bb->end != end)
+ RBI (bb)->footer = unlink_insn_chain (NEXT_INSN (bb->end), end);
+ next_insn = NEXT_INSN (bb->end);
}
- return NULL;
-}
-static rtx
-get_prev_bb_note (x)
- rtx x;
-{
- while (x)
- {
- if (NOTE_INSN_BASIC_BLOCK_P (x))
- return x;
- x = PREV_INSN (x);
- }
- return NULL;
+ function_footer = next_insn;
+ if (function_footer)
+ function_footer = unlink_insn_chain (function_footer, get_last_insn ());
}
+\f
+/* Build a varray mapping INSN_UID to lexical block. Return it. */
-/* Determine and record the relationships between basic blocks and
- scopes in scope tree S. */
-
-static void
-relate_bbs_with_scopes (s)
- scope s;
+void
+scope_to_insns_initialize ()
{
- scope p;
- int i, bbi1, bbi2, bbs_spanned;
- rtx bbnote;
-
- for (p = s->inner; p; p = p->next)
- relate_bbs_with_scopes (p);
+ tree block = NULL;
+ rtx insn, next;
- bbi1 = bbi2 = -1;
- bbs_spanned = 0;
-
- /* If the begin and end notes are both inside the same basic block,
- or if they are both outside of basic blocks, then we know immediately
- how they are related. Otherwise, we need to poke around to make the
- determination. */
- if (s->bb_beg != s->bb_end)
+ for (insn = get_insns (); insn; insn = next)
{
- if (s->bb_beg && s->bb_end)
- {
- /* Both notes are in different bbs. This implies that all the
- basic blocks spanned by the pair of notes are contained in
- this scope. */
- bbi1 = s->bb_beg->index;
- bbi2 = s->bb_end->index;
- bbs_spanned = 1;
- }
- else if (! s->bb_beg)
- {
- /* First note is outside of a bb. If the scope spans more than
- one basic block, then they all are contained within this
- scope. Otherwise, this scope is contained within the basic
- block. */
- bbnote = get_next_bb_note (s->note_beg);
- if (! bbnote)
- abort ();
- if (NOTE_BASIC_BLOCK (bbnote) == s->bb_end)
- {
- bbs_spanned = 0;
- s->bb_beg = NOTE_BASIC_BLOCK (bbnote);
- }
- else
- {
- bbi1 = NOTE_BASIC_BLOCK (bbnote)->index;
- bbi2 = s->bb_end->index;
- s->bb_end = NULL;
- bbs_spanned = 1;
- }
- }
- else /* ! s->bb_end */
- {
- /* Second note is outside of a bb. If the scope spans more than
- one basic block, then they all are contained within this
- scope. Otherwise, this scope is contained within the basic
- block. */
- bbnote = get_prev_bb_note (s->note_end);
- if (! bbnote)
- abort ();
- if (NOTE_BASIC_BLOCK (bbnote) == s->bb_beg)
- {
- bbs_spanned = 0;
- s->bb_end = NOTE_BASIC_BLOCK (bbnote);
- }
- else
- {
- bbi1 = s->bb_beg->index;
- bbi2 = NOTE_BASIC_BLOCK (bbnote)->index;
- s->bb_beg = NULL;
- bbs_spanned = 1;
- }
- }
- }
- else
- {
- if (s->bb_beg)
- /* Both notes are in the same bb, which implies the block
- contains this scope. */
- 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. */
-
- x1 = get_next_bb_note (s->note_beg);
- x2 = get_prev_bb_note (s->note_end);
- if (! (x1 && x2))
- {
- s->level = -1;
- bbs_spanned = 0;
- }
- else
- {
- bbi1 = NOTE_BASIC_BLOCK (x1)->index;
- bbi2 = NOTE_BASIC_BLOCK (x2)->index;
- bbs_spanned = 1;
- }
- }
- }
+ next = NEXT_INSN (insn);
- /* If the scope spans one or more basic blocks, we record them. We
- only record the bbs that are immediately contained within this
- scope. Note that if a scope is contained within a bb, we can tell
- by checking that bb_beg = bb_end and that they are non-null. */
- if (bbs_spanned)
- {
- int j = 0;
-
- s->num_bbs = 0;
- for (i = bbi1; i <= bbi2; i++)
- if (! RBI (BASIC_BLOCK (i))->scope)
- s->num_bbs++;
-
- s->bbs = xmalloc (s->num_bbs * sizeof (basic_block));
- for (i = bbi1; i <= bbi2; i++)
+ if (active_insn_p (insn)
+ && GET_CODE (PATTERN (insn)) != ADDR_VEC
+ && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC)
+ INSN_SCOPE (insn) = block;
+ else if (GET_CODE (insn) == NOTE)
{
- basic_block curr_bb = BASIC_BLOCK (i);
- if (! RBI (curr_bb)->scope)
+ switch (NOTE_LINE_NUMBER (insn))
{
- s->bbs[j++] = curr_bb;
- RBI (curr_bb)->scope = s;
+ case NOTE_INSN_BLOCK_BEG:
+ block = NOTE_BLOCK (insn);
+ delete_insn (insn);
+ break;
+ case NOTE_INSN_BLOCK_END:
+ block = BLOCK_SUPERCONTEXT (block);
+ if (block && TREE_CODE (block) == FUNCTION_DECL)
+ block = 0;
+ delete_insn (insn);
+ break;
+ default:
+ break;
}
}
}
- else
- s->num_bbs = 0;
-}
-/* Allocate and initialize a new scope structure with scope level LEVEL,
- and record the NOTE beginning the scope. */
-
-static scope
-make_new_scope (level, note)
- int level;
- rtx note;
-{
- scope new_scope = xcalloc (1, sizeof (struct scope_def));
- new_scope->level = level;
- new_scope->note_beg = note;
- return new_scope;
+ /* Tag the blocks with a depth number so that change_scope can find
+ the common parent easily. */
+ set_block_levels (DECL_INITIAL (cfun->decl), 0);
}
-
-/* Build a forest representing the scope structure of the function.
- Return a pointer to a structure describing the forest. */
+/* For each lexical block, set BLOCK_NUMBER to the depth at which it is
+ found in the block tree. */
static void
-build_scope_forest (forest)
- scope_forest_info *forest;
-{
- rtx x;
- int level, bbi, i;
- basic_block curr_bb;
- scope root, curr_scope = 0;
-
- forest->num_trees = 0;
- forest->trees = NULL;
- level = -1;
- 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)
- curr_bb = BASIC_BLOCK (bbi);
-
- if (GET_CODE (x) == NOTE)
- {
- if (NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_BEG)
- {
- if (root)
- {
- scope new_scope;
- if (! curr_scope)
- abort();
- level++;
- new_scope = make_new_scope (level, x);
- new_scope->outer = curr_scope;
- new_scope->next = NULL;
- if (! curr_scope->inner)
- {
- curr_scope->inner = new_scope;
- curr_scope->inner_last = new_scope;
- }
- else
- {
- curr_scope->inner_last->next = new_scope;
- 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;
- forest->trees = xrealloc (forest->trees,
- 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)
- {
- curr_scope->bb_end = curr_bb;
- curr_scope->note_end = x;
- level--;
- curr_scope = curr_scope->outer;
- 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]);
-}
-\f
-/* Remove all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes from
- the insn chain. */
-
-static void
-remove_scope_notes ()
+set_block_levels (block, level)
+ tree block;
+ int level;
{
- rtx x, next;
- basic_block currbb = NULL;
-
- for (x = get_insns (); x; x = next)
+ while (block)
{
- next = NEXT_INSN (x);
- if (NOTE_INSN_BASIC_BLOCK_P (x))
- currbb = NOTE_BASIC_BLOCK (x);
-
- if (GET_CODE (x) == NOTE
- && (NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_BEG
- || NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_END))
- {
- /* Check if the scope note happens to be the end of a bb. */
- if (currbb && x == currbb->end)
- currbb->end = PREV_INSN (x);
- if (currbb && x == currbb->head)
- abort ();
-
- if (PREV_INSN (x))
- {
- NEXT_INSN (PREV_INSN (x)) = next;
- PREV_INSN (next) = PREV_INSN (x);
-
- NEXT_INSN (x) = NULL;
- PREV_INSN (x) = NULL;
- }
- else
- abort ();
- }
+ BLOCK_NUMBER (block) = level;
+ set_block_levels (BLOCK_SUBBLOCKS (block), level + 1);
+ block = BLOCK_CHAIN (block);
}
}
\f
-/* Insert scope note pairs for a contained scope tree S after insn IP. */
-
-static void
-insert_intra_1 (s, ip, bb)
- scope s;
- rtx *ip;
- basic_block bb;
+/* Return sope resulting from combination of S1 and S2. */
+tree
+choose_inner_scope (s1, s2)
+ tree s1, s2;
{
- scope p;
-
- if (NOTE_BLOCK (s->note_beg))
- {
- *ip = emit_note_after (NOTE_INSN_BLOCK_BEG, *ip);
- NOTE_BLOCK (*ip) = NOTE_BLOCK (s->note_beg);
- }
-
- for (p = s->inner; p; p = p->next)
- insert_intra_1 (p, ip, bb);
-
- if (NOTE_BLOCK (s->note_beg))
- {
- *ip = emit_note_after (NOTE_INSN_BLOCK_END, *ip);
- NOTE_BLOCK (*ip) = NOTE_BLOCK (s->note_end);
- }
-}
-
-
-/* Insert NOTE_INSN_BLOCK_END notes and NOTE_INSN_BLOCK_BEG notes for
- scopes that are contained within BB. */
-
-static void
-insert_intra_bb_scope_notes (bb)
- basic_block bb;
-{
- scope s = RBI (bb)->scope;
- scope p;
- rtx ip;
-
- if (! s)
- return;
-
- ip = bb->head;
- if (GET_CODE (ip) == CODE_LABEL)
- ip = NEXT_INSN (ip);
-
- for (p = s->inner; p; p = p->next)
- {
- if (p->bb_beg != NULL && p->bb_beg == p->bb_end && p->bb_beg == bb)
- insert_intra_1 (p, &ip, bb);
- }
+ if (!s1)
+ return s2;
+ if (!s2)
+ return s1;
+ if (BLOCK_NUMBER (s1) > BLOCK_NUMBER (s2))
+ return s1;
+ return s2;
}
-
-
-/* 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
- BB2 is NULL, we are inserting scope notes for the first and last basic
- blocks, respectively. */
+\f
+/* Emit lexical block notes needed to change scope from S1 to S2. */
static void
-insert_inter_bb_scope_notes (bb1, bb2)
- basic_block bb1;
- basic_block bb2;
+change_scope (orig_insn, s1, s2)
+ rtx orig_insn;
+ tree s1, s2;
{
- rtx ip;
- scope com;
-
- /* It is possible that a basic block is not contained in any scope.
- In that case, we either open or close a scope but not both. */
- if (bb1 && bb2)
- {
- scope s1 = RBI (bb1)->scope;
- scope s2 = RBI (bb2)->scope;
- if (! s1 && ! s2)
- return;
- if (! s1)
- bb1 = NULL;
- else if (! s2)
- bb2 = NULL;
- }
+ rtx insn = orig_insn;
+ tree com = NULL_TREE;
+ tree ts1 = s1, ts2 = s2;
+ tree s;
- /* Find common ancestor scope. */
- if (bb1 && bb2)
+ while (ts1 != ts2)
{
- scope s1 = RBI (bb1)->scope;
- scope s2 = RBI (bb2)->scope;
- while (s1 != s2)
+ 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
{
- if (! (s1 && s2))
- abort ();
- if (s1->level > s2->level)
- s1 = s1->outer;
- else if (s2->level > s1->level)
- s2 = s2->outer;
- else
- {
- s1 = s1->outer;
- s2 = s2->outer;
- }
+ ts1 = BLOCK_SUPERCONTEXT (ts1);
+ ts2 = BLOCK_SUPERCONTEXT (ts2);
}
- com = s1;
}
- else
- com = NULL;
+ com = ts1;
/* Close scopes. */
- if (bb1)
+ s = s1;
+ while (s != com)
{
- rtx end = bb1->end;
-
- 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;
- }
- /* Emitting note may move the end of basic block to unwanted place. */
- bb1->end = end;
+ rtx note = emit_note_before (NOTE_INSN_BLOCK_END, insn);
+ NOTE_BLOCK (note) = s;
+ s = BLOCK_SUPERCONTEXT (s);
}
/* Open scopes. */
- if (bb2)
+ s = s2;
+ while (s != com)
{
- scope s = RBI (bb2)->scope;
- 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;
- }
+ 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 forest and the newly reordered basic blocks. */
-
-static void
-rebuild_scope_notes (forest)
- scope_forest_info *forest;
-{
- int i;
-
- if (forest->num_trees == 0)
- return;
-
- /* Start by opening the scopes before the first basic block. */
- insert_inter_bb_scope_notes (NULL, BASIC_BLOCK (0));
-
- /* Then, open and close scopes as needed between blocks. */
- for (i = 0; i < n_basic_blocks - 1; i++)
- {
- 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);
- }
-
- /* Finally, close the scopes after the last basic block. */
- insert_inter_bb_scope_notes (BASIC_BLOCK (n_basic_blocks - 1), NULL);
- insert_intra_bb_scope_notes (BASIC_BLOCK (n_basic_blocks - 1));
-}
-\f
-/* Free the storage associated with the scope tree at S. */
-
-static void
-free_scope_forest_1 (s)
- scope s;
-{
- scope p, next;
-
- for (p = s->inner; p; p = next)
- {
- next = p->next;
- free_scope_forest_1 (p);
- }
-
- if (s->bbs)
- free (s->bbs);
- free (s);
-}
-
-/* Free the storage associated with the scope forest. */
-
-static void
-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]);
-}
-\f
-/* Visualize the scope forest. */
+ on the scope tree and the newly reordered instructions. */
void
-dump_scope_forest (forest)
- scope_forest_info *forest;
+scope_to_insns_finalize ()
{
- if (forest->num_trees == 0)
- fprintf (stderr, "\n< Empty scope forest >\n");
- else
+ tree cur_block = DECL_INITIAL (cfun->decl);
+ rtx insn, note;
+
+ insn = get_insns ();
+ if (!active_insn_p (insn))
+ insn = next_active_insn (insn);
+ for (; insn; insn = next_active_insn (insn))
{
- int i;
- fprintf (stderr, "\n< Scope forest >\n");
- for (i = 0; i < forest->num_trees; i++)
- dump_scope_forest_1 (forest->trees[i], 0);
- }
-}
+ tree this_block;
-/* Recursive portion of dump_scope_forest. */
+ this_block = INSN_SCOPE (insn);
+ /* For sequences compute scope resulting from merging all scopes
+ of instructions nested inside. */
+ if (GET_CODE (PATTERN (insn)) == SEQUENCE)
+ {
+ int i;
+ rtx body = PATTERN (insn);
-static void
-dump_scope_forest_1 (s, indent)
- scope s;
- int indent;
-{
- scope p;
- int i;
+ this_block = NULL;
+ for (i = 0; i < XVECLEN (body, 0); i++)
+ this_block = choose_inner_scope (this_block,
+ INSN_SCOPE (XVECEXP (body, 0, i)));
+ }
+ if (! this_block)
+ continue;
- if (s->bb_beg != NULL && s->bb_beg == s->bb_end
- && RBI (s->bb_beg)->scope
- && RBI (s->bb_beg)->scope->level + 1 == s->level)
- {
- fprintf (stderr, "%*s", indent, "");
- fprintf (stderr, "BB%d:\n", s->bb_beg->index);
+ if (this_block != cur_block)
+ {
+ change_scope (insn, cur_block, this_block);
+ cur_block = this_block;
+ }
}
- fprintf (stderr, "%*s", indent, "");
- fprintf (stderr, "{ level %d (block %p)\n", s->level,
- (PTR) NOTE_BLOCK (s->note_beg));
+ /* 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);
- fprintf (stderr, "%*s%s", indent, "", "bbs:");
- for (i = 0; i < s->num_bbs; i++)
- fprintf (stderr, " %d", s->bbs[i]->index);
- fprintf (stderr, "\n");
-
- for (p = s->inner; p; p = p->next)
- dump_scope_forest_1 (p, indent + 2);
-
- fprintf (stderr, "%*s", indent, "");
- fprintf (stderr, "}\n");
+ reorder_blocks ();
}
\f
/* Given a reorder chain, rearrange the code to match. */
static void
fixup_reorder_chain ()
{
- basic_block bb, last_bb;
+ basic_block bb, prev_bb;
int index;
- rtx insn;
- int old_n_basic_blocks = n_basic_blocks;
+ rtx insn = NULL;
/* 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 (bb = ENTRY_BLOCK_PTR->next_bb, index = 0;
+ bb != 0;
+ 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 (RBI (bb)->header)
+ {
+ if (insn)
+ NEXT_INSN (insn) = RBI (bb)->header;
+ else
+ set_first_insn (RBI (bb)->header);
+ PREV_INSN (RBI (bb)->header) = insn;
+ insn = RBI (bb)->header;
+ while (NEXT_INSN (insn))
+ insn = NEXT_INSN (insn);
+ }
+ if (insn)
+ NEXT_INSN (insn) = bb->head;
+ else
+ set_first_insn (bb->head);
+ PREV_INSN (bb->head) = insn;
+ insn = bb->end;
+ if (RBI (bb)->footer)
+ {
+ NEXT_INSN (insn) = RBI (bb)->footer;
+ PREV_INSN (RBI (bb)->footer) = insn;
+ while (NEXT_INSN (insn))
+ insn = NEXT_INSN (insn);
+ }
}
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;
+ NEXT_INSN (insn) = function_footer;
+ if (function_footer)
+ PREV_INSN (function_footer) = insn;
while (NEXT_INSN (insn))
insn = NEXT_INSN (insn);
+
set_last_insn (insn);
#ifdef ENABLE_CHECKING
verify_insn_chain ();
/* Now add jumps and labels as needed to match the blocks new
outgoing edges. */
- for (bb = BASIC_BLOCK (0); bb ; bb = RBI (bb)->next)
+ for (bb = ENTRY_BLOCK_PTR->next_bb; bb ; bb = RBI (bb)->next)
{
edge e_fall, e_taken, e;
rtx bb_end_insn;
&& e_fall->dest == EXIT_BLOCK_PTR))
continue;
+ /* The degenerated case of conditional jump jumping to the next
+ instruction can happen on target having jumps with side
+ effects.
+
+ Create temporarily the duplicated edge representing branch.
+ It will get unidentified by force_nonfallthru_and_redirect
+ that would otherwise get confused by fallthru edge not pointing
+ to the next basic block. */
+ if (!e_taken)
+ {
+ rtx note;
+ edge e_fake;
+
+ e_fake = unchecked_make_edge (bb, e_fall->dest, 0);
+
+ if (!redirect_jump (bb->end, block_label (bb), 0))
+ abort ();
+ note = find_reg_note (bb->end, REG_BR_PROB, NULL_RTX);
+ if (note)
+ {
+ int prob = INTVAL (XEXP (note, 0));
+
+ e_fake->probability = prob;
+ e_fake->count = e_fall->count * prob / REG_BR_PROB_BASE;
+ e_fall->probability -= e_fall->probability;
+ e_fall->count -= e_fake->count;
+ if (e_fall->probability < 0)
+ e_fall->probability = 0;
+ if (e_fall->count < 0)
+ e_fall->count = 0;
+ }
+ }
/* 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)
+ else 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,
{
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
+ /* 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;
}
}
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;
- /* 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));
- RBI (nb)->eff_head = nb->head;
- RBI (nb)->eff_end = NEXT_INSN (nb->end);
- RBI (nb)->scope = RBI (bb)->scope;
RBI (nb)->visited = 1;
RBI (nb)->next = RBI (bb)->next;
RBI (bb)->next = 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");
- while (bb)
{
- 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);
+ fprintf (rtl_dump_file, "Reordered sequence:\n");
+ for (bb = ENTRY_BLOCK_PTR->next_bb, index = 0; bb; bb = RBI (bb)->next, index ++)
+ {
+ fprintf (rtl_dump_file, " %i ", index);
+ if (RBI (bb)->original)
+ fprintf (rtl_dump_file, "duplicate of %i ",
+ RBI (bb)->original->index);
+ else if (forwarder_block_p (bb) && GET_CODE (bb->head) != CODE_LABEL)
+ fprintf (rtl_dump_file, "compensation ");
+ else
+ fprintf (rtl_dump_file, "bb %i ", bb->index);
+ fprintf (rtl_dump_file, " [%i]\n", bb->frequency);
+ }
+ }
+
+ prev_bb = ENTRY_BLOCK_PTR;
+ bb = ENTRY_BLOCK_PTR->next_bb;
+ index = 0;
+
+ for (; bb; prev_bb = bb, bb = RBI (bb)->next, index ++)
+ {
bb->index = index;
BASIC_BLOCK (index) = bb;
- bb = RBI (bb)->next;
- index++;
+ bb->prev_bb = prev_bb;
+ prev_bb->next_bb = bb;
}
+ prev_bb->next_bb = EXIT_BLOCK_PTR;
+ EXIT_BLOCK_PTR->prev_bb = prev_bb;
}
\f
/* Perform sanity checks on the insn 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;
+
+ 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 ())
- {
- fprintf (stderr, "last_insn corrupt.\n");
+ 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 ();
- }
- nextx = NULL;
- insn_cnt2 = 1;
- for (x = get_last_insn (); x; x = PREV_INSN (x))
+ if (insn_cnt1 != insn_cnt2)
+ abort ();
+}
+\f
+/* Remove any unconditional jumps and forwarder block creating fallthru
+ edges instead. During BB reordering, fallthru edges are not required
+ to target next basic block in the linear CFG layout, so the unconditional
+ jumps are not needed. If LOOPS is not null, also update loop structure &
+ dominators. */
+
+static void
+cleanup_unconditional_jumps (loops)
+ struct loops *loops;
+{
+ basic_block bb;
+
+ FOR_EACH_BB (bb)
{
- if (NEXT_INSN (x) != nextx)
+ if (!bb->succ)
+ continue;
+ if (bb->succ->flags & EDGE_FALLTHRU)
+ continue;
+ if (!bb->succ->succ_next)
{
- 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;
- }
+ rtx insn;
+ if (GET_CODE (bb->head) != CODE_LABEL && forwarder_block_p (bb)
+ && bb->prev_bb != ENTRY_BLOCK_PTR)
+ {
+ basic_block prev = bb->prev_bb;
- if (insn_cnt1 != insn_cnt2)
- {
- fprintf (stderr, "insn_cnt1 (%d) not equal to insn_cnt2 (%d).\n",
- insn_cnt1, insn_cnt2);
- abort ();
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file, "Removing forwarder BB %i\n",
+ bb->index);
+
+ if (loops)
+ {
+ /* bb cannot be loop header, as it only has one entry
+ edge. It could be a loop latch. */
+ if (bb->loop_father->header == bb)
+ abort ();
+
+ if (bb->loop_father->latch == bb)
+ bb->loop_father->latch = bb->pred->src;
+
+ if (get_immediate_dominator
+ (loops->cfg.dom, bb->succ->dest) == bb)
+ set_immediate_dominator
+ (loops->cfg.dom, bb->succ->dest, bb->pred->src);
+
+ remove_bb_from_loops (bb);
+ delete_from_dominance_info (loops->cfg.dom, bb);
+ }
+
+ redirect_edge_succ_nodup (bb->pred, bb->succ->dest);
+ flow_delete_block (bb);
+ bb = prev;
+ }
+ else if (simplejump_p (bb->end))
+ {
+ rtx jump = bb->end;
+
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file, "Removing jump %i in BB %i\n",
+ INSN_UID (jump), bb->index);
+ delete_insn (jump);
+ bb->succ->flags |= EDGE_FALLTHRU;
+ }
+ else
+ continue;
+
+ insn = NEXT_INSN (bb->end);
+ while (insn
+ && (GET_CODE (insn) != NOTE
+ || NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK))
+ {
+ rtx next = NEXT_INSN (insn);
+
+ if (GET_CODE (insn) == BARRIER)
+ delete_barrier (insn);
+
+ insn = next;
+ }
+ }
}
}
-
-/* The block falling trought to exit must be last in the reordered
- chain. Make it happen so. */
-static basic_block
-fixup_fallthru_exit_predecesor ()
+\f
+/* The block falling through to exit must be the last one in the
+ reordered chain. Ensure that this condition is met. */
+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);
+ basic_block c = ENTRY_BLOCK_PTR->next_bb;
+
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;
}
}
\f
+/* Return true in case it is possible to duplicate the basic block BB. */
+
+bool
+cfg_layout_can_duplicate_bb_p (bb)
+ basic_block bb;
+{
+ edge s;
+
+ if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR)
+ return false;
+
+ /* Duplicating fallthru block to exit would require adding a jump
+ and splitting the real last BB. */
+ for (s = bb->succ; s; s = s->succ_next)
+ if (s->dest == EXIT_BLOCK_PTR && s->flags & EDGE_FALLTHRU)
+ return false;
+
+ /* Do not attempt to duplicate tablejumps, as we need to unshare
+ the dispatch table. This is difficult to do, as the instructions
+ computing jump destination may be hoisted outside the basic block. */
+ if (tablejump_p (bb->end, NULL, NULL))
+ return false;
+
+ /* Do not duplicate blocks containing insns that can't be copied. */
+ if (targetm.cannot_copy_insn_p)
+ {
+ rtx insn = bb->head;
+ while (1)
+ {
+ if (INSN_P (insn) && (*targetm.cannot_copy_insn_p) (insn))
+ return false;
+ if (insn == bb->end)
+ break;
+ insn = NEXT_INSN (insn);
+ }
+ }
+
+ return true;
+}
+
+static rtx
+duplicate_insn_chain (from, to)
+ rtx from, to;
+{
+ rtx insn, last;
+
+ /* Avoid updating of boundaries of previous basic block. The
+ note will get removed from insn stream in fixup. */
+ last = emit_note (NULL, NOTE_INSN_DELETED);
+
+ /* Create copy at the end of INSN chain. The chain will
+ be reordered later. */
+ for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn))
+ {
+ switch (GET_CODE (insn))
+ {
+ case INSN:
+ case CALL_INSN:
+ case JUMP_INSN:
+ /* Avoid copying of dispatch tables. We never duplicate
+ tablejumps, so this can hit only in case the table got
+ moved far from original jump. */
+ if (GET_CODE (PATTERN (insn)) == ADDR_VEC
+ || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
+ break;
+ emit_copy_of_insn_after (insn, get_last_insn ());
+ break;
+
+ case CODE_LABEL:
+ break;
+
+ case BARRIER:
+ emit_barrier ();
+ break;
+
+ case NOTE:
+ switch (NOTE_LINE_NUMBER (insn))
+ {
+ /* In case prologue is empty and function contain label
+ in first BB, we may want to copy the block. */
+ case NOTE_INSN_PROLOGUE_END:
+
+ case NOTE_INSN_LOOP_VTOP:
+ case NOTE_INSN_LOOP_CONT:
+ case NOTE_INSN_LOOP_BEG:
+ case NOTE_INSN_LOOP_END:
+ /* Strip down the loop notes - we don't really want to keep
+ them consistent in loop copies. */
+ case NOTE_INSN_DELETED:
+ case NOTE_INSN_DELETED_LABEL:
+ /* No problem to strip these. */
+ case NOTE_INSN_EPILOGUE_BEG:
+ case NOTE_INSN_FUNCTION_END:
+ /* Debug code expect these notes to exist just once.
+ Keep them in the master copy.
+ ??? It probably makes more sense to duplicate them for each
+ epilogue copy. */
+ case NOTE_INSN_FUNCTION_BEG:
+ /* There is always just single entry to function. */
+ case NOTE_INSN_BASIC_BLOCK:
+ break;
+
+ /* There is no purpose to duplicate prologue. */
+ case NOTE_INSN_BLOCK_BEG:
+ case NOTE_INSN_BLOCK_END:
+ /* The BLOCK_BEG/BLOCK_END notes should be eliminated when BB
+ reordering is in the progress. */
+ case NOTE_INSN_EH_REGION_BEG:
+ case NOTE_INSN_EH_REGION_END:
+ /* Should never exist at BB duplication time. */
+ abort ();
+ break;
+ case NOTE_INSN_REPEATED_LINE_NUMBER:
+ emit_note (NOTE_SOURCE_FILE (insn), NOTE_LINE_NUMBER (insn));
+ break;
+
+ default:
+ if (NOTE_LINE_NUMBER (insn) < 0)
+ abort ();
+ /* It is possible that no_line_number is set and the note
+ won't be emitted. */
+ emit_note (NOTE_SOURCE_FILE (insn), NOTE_LINE_NUMBER (insn));
+ }
+ break;
+ default:
+ abort ();
+ }
+ }
+ insn = NEXT_INSN (last);
+ delete_insn (last);
+ return insn;
+}
+
+/* Redirect Edge to DEST. */
+bool
+cfg_layout_redirect_edge (e, dest)
+ edge e;
+ basic_block dest;
+{
+ basic_block src = e->src;
+ basic_block old_next_bb = src->next_bb;
+ bool ret;
+
+ /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
+ in the case the basic block appears to be in sequence. Avoid this
+ transformation. */
+
+ src->next_bb = NULL;
+ if (e->flags & EDGE_FALLTHRU)
+ {
+ /* Redirect any branch edges unified with the fallthru one. */
+ if (GET_CODE (src->end) == JUMP_INSN
+ && JUMP_LABEL (src->end) == e->dest->head)
+ {
+ if (!redirect_jump (src->end, block_label (dest), 0))
+ abort ();
+ }
+ /* In case we are redirecting fallthru edge to the branch edge
+ of conditional jump, remove it. */
+ if (src->succ->succ_next
+ && !src->succ->succ_next->succ_next)
+ {
+ edge s = e->succ_next ? e->succ_next : src->succ;
+ if (s->dest == dest
+ && any_condjump_p (src->end)
+ && onlyjump_p (src->end))
+ delete_insn (src->end);
+ }
+ redirect_edge_succ_nodup (e, dest);
+
+ ret = true;
+ }
+ else
+ ret = redirect_edge_and_branch (e, dest);
+
+ /* We don't want simplejumps in the insn stream during cfglayout. */
+ if (simplejump_p (src->end))
+ {
+ delete_insn (src->end);
+ delete_barrier (NEXT_INSN (src->end));
+ src->succ->flags |= EDGE_FALLTHRU;
+ }
+ src->next_bb = old_next_bb;
+
+ return ret;
+}
+
+/* Same as split_block but update cfg_layout structures. */
+edge
+cfg_layout_split_block (bb, insn)
+ basic_block bb;
+ rtx insn;
+{
+ edge fallthru = split_block (bb, insn);
+
+ alloc_aux_for_block (fallthru->dest, sizeof (struct reorder_block_def));
+ RBI (fallthru->dest)->footer = RBI (fallthru->src)->footer;
+ RBI (fallthru->src)->footer = NULL;
+ return fallthru;
+}
+
+/* Create a duplicate of the basic block BB and redirect edge E into it. */
+
+basic_block
+cfg_layout_duplicate_bb (bb, e)
+ basic_block bb;
+ edge e;
+{
+ rtx insn;
+ edge s, n;
+ basic_block new_bb;
+ gcov_type new_count = e ? e->count : 0;
+
+ if (bb->count < new_count)
+ new_count = bb->count;
+ if (!bb->pred)
+ abort ();
+#ifdef ENABLE_CHECKING
+ if (!cfg_layout_can_duplicate_bb_p (bb))
+ abort ();
+#endif
+
+ insn = duplicate_insn_chain (bb->head, bb->end);
+ new_bb = create_basic_block (insn,
+ insn ? get_last_insn () : NULL,
+ EXIT_BLOCK_PTR->prev_bb);
+ alloc_aux_for_block (new_bb, sizeof (struct reorder_block_def));
+
+ if (RBI (bb)->header)
+ {
+ insn = RBI (bb)->header;
+ while (NEXT_INSN (insn))
+ insn = NEXT_INSN (insn);
+ insn = duplicate_insn_chain (RBI (bb)->header, insn);
+ if (insn)
+ RBI (new_bb)->header = unlink_insn_chain (insn, get_last_insn ());
+ }
+
+ if (RBI (bb)->footer)
+ {
+ insn = RBI (bb)->footer;
+ while (NEXT_INSN (insn))
+ insn = NEXT_INSN (insn);
+ insn = duplicate_insn_chain (RBI (bb)->footer, insn);
+ if (insn)
+ RBI (new_bb)->footer = unlink_insn_chain (insn, get_last_insn ());
+ }
+
+ if (bb->global_live_at_start)
+ {
+ new_bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
+ new_bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
+ COPY_REG_SET (new_bb->global_live_at_start, bb->global_live_at_start);
+ COPY_REG_SET (new_bb->global_live_at_end, bb->global_live_at_end);
+ }
+
+ new_bb->loop_depth = bb->loop_depth;
+ new_bb->flags = bb->flags;
+ for (s = bb->succ; s; s = s->succ_next)
+ {
+ /* Since we are creating edges from a new block to successors
+ of another block (which therefore are known to be disjoint), there
+ is no need to actually check for duplicated edges. */
+ n = unchecked_make_edge (new_bb, s->dest, s->flags);
+ n->probability = s->probability;
+ if (new_count)
+ /* Take care for overflows! */
+ n->count = s->count * (new_count * 10000 / bb->count) / 10000;
+ else
+ n->count = 0;
+ s->count -= n->count;
+ }
+
+ new_bb->count = new_count;
+ bb->count -= new_count;
+
+ if (e)
+ {
+ new_bb->frequency = EDGE_FREQUENCY (e);
+ bb->frequency -= EDGE_FREQUENCY (e);
+
+ cfg_layout_redirect_edge (e, new_bb);
+ }
+
+ if (bb->count < 0)
+ bb->count = 0;
+ if (bb->frequency < 0)
+ bb->frequency = 0;
+
+ RBI (new_bb)->original = bb;
+ RBI (bb)->copy = new_bb;
+ return new_bb;
+}
+\f
/* Main entry point to this module - initialize the datastructures for
- CFG layout changes. */
+ CFG layout changes. It keeps LOOPS up-to-date if not null. */
void
-cfg_layout_initialize ()
+cfg_layout_initialize (loops)
+ struct loops *loops;
{
+ /* Our algorithm depends on fact that there are now dead jumptables
+ around the code. */
alloc_aux_for_blocks (sizeof (struct reorder_block_def));
- build_scope_forest (&forest);
- remove_scope_notes ();
+ cleanup_unconditional_jumps (loops);
record_effective_endpoints ();
}
-/* Finalize the changes - reorder insn list according to the sequence,
- enter compensation code, rebuild scope forest. */
+/* Splits superblocks. */
+static void
+break_superblocks ()
+{
+ sbitmap superblocks;
+ int i, need;
+
+ superblocks = sbitmap_alloc (n_basic_blocks);
+ sbitmap_zero (superblocks);
+
+ need = 0;
+
+ for (i = 0; i < n_basic_blocks; i++)
+ if (BASIC_BLOCK(i)->flags & BB_SUPERBLOCK)
+ {
+ BASIC_BLOCK(i)->flags &= ~BB_SUPERBLOCK;
+ SET_BIT (superblocks, i);
+ need = 1;
+ }
+
+ if (need)
+ {
+ rebuild_jump_labels (get_insns ());
+ find_many_sub_basic_blocks (superblocks);
+ }
+
+ free (superblocks);
+}
+
+/* Finalize the changes: reorder insn list according to the sequence, enter
+ compensation code, rebuild scope forest. */
void
cfg_layout_finalize ()
{
- fixup_fallthru_exit_predecesor ();
+ fixup_fallthru_exit_predecessor ();
fixup_reorder_chain ();
+
#ifdef ENABLE_CHECKING
verify_insn_chain ();
#endif
- rebuild_scope_notes (&forest);
- free_scope_forest (&forest);
- reorder_blocks ();
-
free_aux_for_blocks ();
+ break_superblocks ();
+
#ifdef ENABLE_CHECKING
verify_flow_info ();
#endif
OSDN Git Service
