/* Basic block reordering routines for the GNU compiler.
- Copyright (C) 2000 Free Software Foundation, Inc.
+ Copyright (C) 2000, 2001, 2003, 2004 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"
+#include "ggc.h"
+#include "alloc-pool.h"
+#include "flags.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;
+/* Holds the interesting trailing notes for the function. */
+rtx cfg_layout_function_footer, cfg_layout_function_header;
- /* The last inner scope or NULL if innermost scope. */
- struct scope_def *inner_last;
+static rtx skip_insns_after_block (basic_block);
+static void record_effective_endpoints (void);
+static rtx label_for_bb (basic_block);
+static void fixup_reorder_chain (void);
- /* Link to the next (sibling) scope. */
- struct scope_def *next;
-};
+static void set_block_levels (tree, int);
+static void change_scope (rtx, tree, tree);
-/* Structure to hold information about the scope forest. */
-typedef struct
+void verify_insn_chain (void);
+static void fixup_fallthru_exit_predecessor (void);
+static tree insn_scope (rtx);
+static void update_unlikely_executed_notes (basic_block);
+\f
+rtx
+unlink_insn_chain (rtx first, rtx last)
{
- /* 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 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));
-
-void verify_insn_chain PARAMS ((void));
-static basic_block fixup_fallthru_exit_predecesor PARAMS ((void));
+ 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,
we return the last one. Otherwise, we return the end of BB. */
static rtx
-skip_insns_after_block (bb)
- basic_block bb;
+skip_insns_after_block (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;
+ if (bb->next_bb != EXIT_BLOCK_PTR)
+ next_head = BB_HEAD (bb->next_bb);
- for (last_insn = insn = bb->end; (insn = NEXT_INSN (insn)); )
+ for (last_insn = insn = BB_END (bb); (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)
+ for (insn = last_insn; insn != BB_END (bb); 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;
/* Locate or create a label for a given basic block. */
static rtx
-label_for_bb (bb)
- basic_block bb;
+label_for_bb (basic_block bb)
{
- rtx label = bb->head;
+ rtx label = BB_HEAD (bb);
if (GET_CODE (label) != CODE_LABEL)
{
- if (rtl_dump_file)
- fprintf (rtl_dump_file, "Emitting label for block %d\n",
- bb->index);
+ if (dump_file)
+ fprintf (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;
block, as defined by skip_insns_after_block above. */
static void
-record_effective_endpoints ()
+record_effective_endpoints (void)
{
- rtx next_insn = get_insns ();
- int i;
-
- for (i = 0; i < n_basic_blocks; ++i)
+ rtx next_insn;
+ basic_block bb;
+ rtx insn;
+
+ for (insn = get_insns ();
+ insn
+ && GET_CODE (insn) == NOTE
+ && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK;
+ insn = NEXT_INSN (insn))
+ continue;
+ if (!insn)
+ abort (); /* No basic blocks at all? */
+ if (PREV_INSN (insn))
+ cfg_layout_function_header =
+ unlink_insn_chain (get_insns (), PREV_INSN (insn));
+ else
+ cfg_layout_function_header = NULL_RTX;
+
+ next_insn = get_insns ();
+ FOR_EACH_BB (bb)
{
- basic_block bb = BASIC_BLOCK (i);
rtx end;
- RBI (bb)->eff_head = next_insn;
+ if (PREV_INSN (BB_HEAD (bb)) && next_insn != BB_HEAD (bb))
+ bb->rbi->header = unlink_insn_chain (next_insn,
+ PREV_INSN (BB_HEAD (bb)));
end = skip_insns_after_block (bb);
- RBI (bb)->eff_end = end;
- next_insn = NEXT_INSN (end);
+ if (NEXT_INSN (BB_END (bb)) && BB_END (bb) != end)
+ bb->rbi->footer = unlink_insn_chain (NEXT_INSN (BB_END (bb)), end);
+ next_insn = NEXT_INSN (BB_END (bb));
}
- function_tail_eff_head = next_insn;
+
+ cfg_layout_function_footer = next_insn;
+ if (cfg_layout_function_footer)
+ cfg_layout_function_footer = unlink_insn_chain (cfg_layout_function_footer, get_last_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);
- }
- return NULL;
-}
+/* Data structures representing mapping of INSN_LOCATOR into scope blocks, line
+ numbers and files. In order to be GGC friendly we need to use separate
+ varrays. This also slightly improve the memory locality in binary search.
+ The _locs array contains locators where the given property change. The
+ block_locators_blocks contains the scope block that is used for all insn
+ locator greater than corresponding block_locators_locs value and smaller
+ than the following one. Similarly for the other properties. */
+static GTY(()) varray_type block_locators_locs;
+static GTY(()) varray_type block_locators_blocks;
+static GTY(()) varray_type line_locators_locs;
+static GTY(()) varray_type line_locators_lines;
+static GTY(()) varray_type file_locators_locs;
+static GTY(()) varray_type file_locators_files;
+int prologue_locator;
+int epilogue_locator;
+
+/* During the RTL expansion the lexical blocks and line numbers are
+ represented via INSN_NOTEs. Replace them by representation using
+ INSN_LOCATORs. */
-static rtx
-get_prev_bb_note (x)
- rtx x;
+void
+insn_locators_initialize (void)
{
- while (x)
+ tree block = NULL;
+ tree last_block = NULL;
+ rtx insn, next;
+ int loc = 0;
+ int line_number = 0, last_line_number = 0;
+ char *file_name = NULL, *last_file_name = NULL;
+
+ prologue_locator = epilogue_locator = 0;
+
+ VARRAY_INT_INIT (block_locators_locs, 32, "block_locators_locs");
+ VARRAY_TREE_INIT (block_locators_blocks, 32, "block_locators_blocks");
+ VARRAY_INT_INIT (line_locators_locs, 32, "line_locators_locs");
+ VARRAY_INT_INIT (line_locators_lines, 32, "line_locators_lines");
+ VARRAY_INT_INIT (file_locators_locs, 32, "file_locators_locs");
+ VARRAY_CHAR_PTR_INIT (file_locators_files, 32, "file_locators_files");
+
+ for (insn = get_insns (); insn; insn = next)
{
- if (NOTE_INSN_BASIC_BLOCK_P (x))
- return x;
- x = PREV_INSN (x);
- }
- return NULL;
-}
-
-/* Determine and record the relationships between basic blocks and
- scopes in scope tree S. */
+ next = NEXT_INSN (insn);
-static void
-relate_bbs_with_scopes (s)
- scope s;
-{
- scope p;
- int i, bbi1, bbi2, bbs_spanned;
- rtx bbnote;
-
- for (p = s->inner; p; p = p->next)
- relate_bbs_with_scopes (p);
-
- 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)
- {
- 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
+ if ((active_insn_p (insn)
+ && GET_CODE (PATTERN (insn)) != ADDR_VEC
+ && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC)
+ || !NEXT_INSN (insn)
+ || (!prologue_locator && file_name))
+ {
+ if (last_block != block)
{
- bbi1 = NOTE_BASIC_BLOCK (bbnote)->index;
- bbi2 = s->bb_end->index;
- s->bb_end = NULL;
- bbs_spanned = 1;
+ loc++;
+ VARRAY_PUSH_INT (block_locators_locs, loc);
+ VARRAY_PUSH_TREE (block_locators_blocks, block);
+ last_block = block;
}
- }
- 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)
+ if (last_line_number != line_number)
{
- bbs_spanned = 0;
- s->bb_end = NOTE_BASIC_BLOCK (bbnote);
+ loc++;
+ VARRAY_PUSH_INT (line_locators_locs, loc);
+ VARRAY_PUSH_INT (line_locators_lines, line_number);
+ last_line_number = line_number;
}
- else
+ if (last_file_name != file_name)
{
- bbi1 = s->bb_beg->index;
- bbi2 = NOTE_BASIC_BLOCK (bbnote)->index;
- s->bb_beg = NULL;
- bbs_spanned = 1;
+ loc++;
+ VARRAY_PUSH_INT (file_locators_locs, loc);
+ VARRAY_PUSH_CHAR_PTR (file_locators_files, file_name);
+ last_file_name = file_name;
}
}
- }
- else
- {
- if (s->bb_beg)
- /* Both notes are in the same bb, which implies the block
- contains this scope. */
- bbs_spanned = 0;
- else
+ if (!prologue_locator && file_name)
+ prologue_locator = loc;
+ if (!NEXT_INSN (insn))
+ epilogue_locator = loc;
+ if (active_insn_p (insn))
+ INSN_LOCATOR (insn) = loc;
+ else if (GET_CODE (insn) == NOTE)
{
- 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
+ switch (NOTE_LINE_NUMBER (insn))
{
- bbi1 = NOTE_BASIC_BLOCK (x1)->index;
- bbi2 = NOTE_BASIC_BLOCK (x2)->index;
- bbs_spanned = 1;
+ case NOTE_INSN_BLOCK_BEG:
+ if (cfun->dont_emit_block_notes)
+ abort ();
+ block = NOTE_BLOCK (insn);
+ delete_insn (insn);
+ break;
+ case NOTE_INSN_BLOCK_END:
+ if (cfun->dont_emit_block_notes)
+ abort ();
+ block = BLOCK_SUPERCONTEXT (block);
+ if (block && TREE_CODE (block) == FUNCTION_DECL)
+ block = 0;
+ delete_insn (insn);
+ break;
+ default:
+ if (NOTE_LINE_NUMBER (insn) > 0)
+ {
+ line_number = NOTE_LINE_NUMBER (insn);
+ file_name = (char *)NOTE_SOURCE_FILE (insn);
+ }
+ break;
}
}
- }
-
- /* 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++)
- {
- basic_block curr_bb = BASIC_BLOCK (i);
- if (! RBI (curr_bb)->scope)
- {
- s->bbs[j++] = curr_bb;
- RBI (curr_bb)->scope = s;
- }
- }
+ if (cfun->dont_emit_block_notes)
+ check_block_change (insn, &block);
}
- else
- s->num_bbs = 0;
-}
-/* Allocate and initialize a new scope structure with scope level LEVEL,
- and record the NOTE beginning the 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);
-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;
+ if (cfun->dont_emit_block_notes)
+ free_block_changes ();
}
-
-/* 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;
+set_block_levels (tree block, int level)
{
- 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))
+ while (block)
{
- 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]);
+ BLOCK_NUMBER (block) = level;
+ set_block_levels (BLOCK_SUBBLOCKS (block), level + 1);
+ block = BLOCK_CHAIN (block);
+ }
}
\f
-/* Remove all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes from
- the insn chain. */
+/* Return sope resulting from combination of S1 and S2. */
+tree
+choose_inner_scope (tree s1, tree s2)
+{
+ if (!s1)
+ return s2;
+ if (!s2)
+ return s1;
+ if (BLOCK_NUMBER (s1) > BLOCK_NUMBER (s2))
+ return s1;
+ return s2;
+}
+\f
+/* Emit lexical block notes needed to change scope from S1 to S2. */
static void
-remove_scope_notes ()
+change_scope (rtx orig_insn, tree s1, tree s2)
{
- rtx x, next;
- basic_block currbb = NULL;
+ rtx insn = orig_insn;
+ tree com = NULL_TREE;
+ tree ts1 = s1, ts2 = s2;
+ tree s;
- for (x = get_insns (); x; x = next)
+ while (ts1 != ts2)
{
- 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))
+ 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
{
- /* 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 ();
+ ts1 = BLOCK_SUPERCONTEXT (ts1);
+ ts2 = BLOCK_SUPERCONTEXT (ts2);
}
}
-}
-\f
-/* Insert scope note pairs for a contained scope tree S after insn IP. */
+ com = ts1;
-static void
-insert_intra_1 (s, ip, bb)
- scope s;
- rtx *ip;
- basic_block bb;
-{
- 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);
+ /* 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);
}
-}
-
-
-/* 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)
+ /* Open scopes. */
+ s = s2;
+ while (s != com)
{
- if (p->bb_beg != NULL && p->bb_beg == p->bb_end && p->bb_beg == bb)
- insert_intra_1 (p, &ip, bb);
+ insn = emit_note_before (NOTE_INSN_BLOCK_BEG, insn);
+ NOTE_BLOCK (insn) = s;
+ s = BLOCK_SUPERCONTEXT (s);
}
}
-
-/* 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. */
-
-static void
-insert_inter_bb_scope_notes (bb1, bb2)
- basic_block bb1;
- basic_block bb2;
+/* Return lexical scope block insn belong to. */
+static tree
+insn_scope (rtx insn)
{
- 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)
+ int max = VARRAY_ACTIVE_SIZE (block_locators_locs);
+ int min = 0;
+ int loc = INSN_LOCATOR (insn);
+
+ /* When block_locators_locs was initialized, the pro- and epilogue
+ insns didn't exist yet and can therefore not be found this way.
+ But we know that they belong to the outer most block of the
+ current function.
+ Without this test, the prologue would be put inside the block of
+ the first valid instruction in the function and when that first
+ insn is part of an inlined function then the low_pc of that
+ inlined function is messed up. Likewise for the epilogue and
+ the last valid instruction. */
+ if (loc == prologue_locator || loc == epilogue_locator)
+ return DECL_INITIAL (cfun->decl);
+
+ if (!max || !loc)
+ return NULL;
+ while (1)
{
- scope s1 = RBI (bb1)->scope;
- scope s2 = RBI (bb2)->scope;
- if (! s1 && ! s2)
- return;
- if (! s1)
- bb1 = NULL;
- else if (! s2)
- bb2 = NULL;
- }
+ int pos = (min + max) / 2;
+ int tmp = VARRAY_INT (block_locators_locs, pos);
- /* Find common ancestor scope. */
- if (bb1 && bb2)
- {
- scope s1 = RBI (bb1)->scope;
- scope s2 = RBI (bb2)->scope;
- while (s1 != s2)
+ if (tmp <= loc && min != pos)
+ min = pos;
+ else if (tmp > loc && max != pos)
+ max = pos;
+ 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;
- }
+ min = pos;
+ break;
}
- com = s1;
}
- else
- com = NULL;
-
- /* Close scopes. */
- if (bb1)
- {
- rtx end = bb1->end;
+ return VARRAY_TREE (block_locators_blocks, min);
+}
- 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;
- }
+/* Return line number of the statement specified by the locator. */
+int
+locator_line (int loc)
+{
+ int max = VARRAY_ACTIVE_SIZE (line_locators_locs);
+ int min = 0;
- /* Open scopes. */
- if (bb2)
+ if (!max || !loc)
+ return 0;
+ while (1)
{
- scope s = RBI (bb2)->scope;
- ip = bb2->head;
- while (s != com)
+ int pos = (min + max) / 2;
+ int tmp = VARRAY_INT (line_locators_locs, pos);
+
+ if (tmp <= loc && min != pos)
+ min = pos;
+ else if (tmp > loc && max != pos)
+ max = pos;
+ else
{
- 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;
+ min = pos;
+ break;
}
}
+ return VARRAY_INT (line_locators_lines, min);
}
-
-/* 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;
+/* Return line number of the statement that produced this insn. */
+int
+insn_line (rtx insn)
{
- 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));
+ return locator_line (INSN_LOCATOR (insn));
}
-\f
-/* Free the storage associated with the scope tree at S. */
-static void
-free_scope_forest_1 (s)
- scope s;
+/* Return source file of the statement specified by LOC. */
+const char *
+locator_file (int loc)
{
- scope p, next;
+ int max = VARRAY_ACTIVE_SIZE (file_locators_locs);
+ int min = 0;
- for (p = s->inner; p; p = next)
+ if (!max || !loc)
+ return NULL;
+ while (1)
{
- next = p->next;
- free_scope_forest_1 (p);
- }
+ int pos = (min + max) / 2;
+ int tmp = VARRAY_INT (file_locators_locs, pos);
- if (s->bbs)
- free (s->bbs);
- free (s);
+ if (tmp <= loc && min != pos)
+ min = pos;
+ else if (tmp > loc && max != pos)
+ max = pos;
+ else
+ {
+ min = pos;
+ break;
+ }
+ }
+ return VARRAY_CHAR_PTR (file_locators_files, min);
}
-/* Free the storage associated with the scope forest. */
-
-static void
-free_scope_forest (forest)
- scope_forest_info *forest;
+/* Return source file of the statement that produced this insn. */
+const char *
+insn_file (rtx insn)
{
- int i;
- for (i = 0; i < forest->num_trees; i++)
- free_scope_forest_1 (forest->trees[i]);
+ return locator_file (INSN_LOCATOR (insn));
}
-\f
-/* Visualize the scope forest. */
+
+/* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based
+ on the scope tree and the newly reordered instructions. */
void
-dump_scope_forest (forest)
- scope_forest_info *forest;
+reemit_insn_block_notes (void)
{
- 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));
-
- 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);
+ /* change_scope emits before the insn, not after. */
+ note = emit_note (NOTE_INSN_DELETED);
+ change_scope (note, cur_block, DECL_INITIAL (cfun->decl));
+ delete_insn (note);
- fprintf (stderr, "%*s", indent, "");
- fprintf (stderr, "}\n");
+ reorder_blocks ();
}
\f
/* Given a reorder chain, rearrange the code to match. */
static void
-fixup_reorder_chain ()
+fixup_reorder_chain (void)
{
- 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;
+
+ if (cfg_layout_function_header)
+ {
+ set_first_insn (cfg_layout_function_header);
+ insn = cfg_layout_function_header;
+ while (NEXT_INSN (insn))
+ insn = NEXT_INSN (insn);
+ }
/* 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 = bb->rbi->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 (bb->rbi->header)
+ {
+ if (insn)
+ NEXT_INSN (insn) = bb->rbi->header;
+ else
+ set_first_insn (bb->rbi->header);
+ PREV_INSN (bb->rbi->header) = insn;
+ insn = bb->rbi->header;
+ while (NEXT_INSN (insn))
+ insn = NEXT_INSN (insn);
+ }
+ if (insn)
+ NEXT_INSN (insn) = BB_HEAD (bb);
+ else
+ set_first_insn (BB_HEAD (bb));
+ PREV_INSN (BB_HEAD (bb)) = insn;
+ insn = BB_END (bb);
+ if (bb->rbi->footer)
+ {
+ NEXT_INSN (insn) = bb->rbi->footer;
+ PREV_INSN (bb->rbi->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) = cfg_layout_function_footer;
+ if (cfg_layout_function_footer)
+ PREV_INSN (cfg_layout_function_footer) = insn;
while (NEXT_INSN (insn))
insn = NEXT_INSN (insn);
+
set_last_insn (insn);
#ifdef ENABLE_CHECKING
verify_insn_chain ();
#endif
+ delete_dead_jumptables ();
/* 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 = bb->rbi->next)
{
edge e_fall, e_taken, e;
rtx bb_end_insn;
basic_block nb;
+ basic_block old_bb;
if (bb->succ == NULL)
continue;
else if (! (e->flags & EDGE_EH))
e_taken = e;
- bb_end_insn = bb->end;
+ bb_end_insn = BB_END (bb);
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))
+ if (bb->rbi->next == e_fall->dest
+ || 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 (bb), block_label (bb), 0))
+ abort ();
+ note = find_reg_note (BB_END (bb), 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 (bb->rbi->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->dest == EXIT_BLOCK_PTR
+ ? NULL_RTX
+ : label_for_bb (e_fall->dest)), 0))
{
e_fall->flags &= ~EDGE_FALLTHRU;
+#ifdef ENABLE_CHECKING
+ if (!could_fall_through (e_taken->src, e_taken->dest))
+ abort ();
+#endif
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
+ /* If the "jumping" edge is a crossing edge, and the fall
+ through edge is non-crossing, leave things as they are. */
+ else if (e_taken->crossing_edge && !e_fall->crossing_edge)
+ continue;
+
+ /* 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->dest == EXIT_BLOCK_PTR
+ ? NULL_RTX
+ : label_for_bb (e_fall->dest)), 0))
{
e_fall->flags &= ~EDGE_FALLTHRU;
+#ifdef ENABLE_CHECKING
+ if (!could_fall_through (e_taken->src, e_taken->dest))
+ abort ();
+#endif
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)
+ if (bb->rbi->next == e_fall->dest)
continue;
bb_end_insn = skip_insns_after_block (bb);
#else
continue;
/* If the fallthru block is still next, nothing to do. */
- if (RBI (bb)->next == e_fall->dest)
+ if (bb->rbi->next == e_fall->dest)
continue;
- /* An fallthru to exit block. */
- if (!RBI (bb)->next && e_fall->dest == EXIT_BLOCK_PTR)
+ /* A fallthru to exit block. */
+ if (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;
+ initialize_bb_rbi (nb);
+ nb->rbi->visited = 1;
+ nb->rbi->next = bb->rbi->next;
+ bb->rbi->next = nb;
/* Don't process this new block. */
+ old_bb = bb;
bb = nb;
+
+ /* Make sure new bb is tagged for correct section (same as
+ fall-thru source). */
+ e_fall->src->partition = bb->pred->src->partition;
+ if (flag_reorder_blocks_and_partition)
+ {
+ if (bb->pred->src->partition == COLD_PARTITION)
+ {
+ rtx new_note;
+ rtx note = BB_HEAD (e_fall->src);
+
+ while (!INSN_P (note)
+ && note != BB_END (e_fall->src))
+ note = NEXT_INSN (note);
+
+ new_note = emit_note_before
+ (NOTE_INSN_UNLIKELY_EXECUTED_CODE,
+ note);
+ NOTE_BASIC_BLOCK (new_note) = bb;
+ }
+ if (GET_CODE (BB_END (bb)) == JUMP_INSN
+ && !any_condjump_p (BB_END (bb))
+ && bb->succ->crossing_edge )
+ REG_NOTES (BB_END (bb)) = gen_rtx_EXPR_LIST
+ (REG_CROSSING_JUMP, NULL_RTX, REG_NOTES (BB_END (bb)));
+ }
}
}
/* Put basic_block_info in the new order. */
- bb = BASIC_BLOCK (0);
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "Reordered sequence:\n");
+ for (bb = ENTRY_BLOCK_PTR->next_bb, index = 0;
+ bb;
+ bb = bb->rbi->next, index++)
+ {
+ fprintf (dump_file, " %i ", index);
+ if (bb->rbi->original)
+ fprintf (dump_file, "duplicate of %i ",
+ bb->rbi->original->index);
+ else if (forwarder_block_p (bb)
+ && GET_CODE (BB_HEAD (bb)) != CODE_LABEL)
+ fprintf (dump_file, "compensation ");
+ else
+ fprintf (dump_file, "bb %i ", bb->index);
+ fprintf (dump_file, " [%i]\n", bb->frequency);
+ }
+ }
+
+ prev_bb = ENTRY_BLOCK_PTR;
+ bb = ENTRY_BLOCK_PTR->next_bb;
index = 0;
- if (rtl_dump_file)
- fprintf (rtl_dump_file, "Reordered sequence:\n");
- while (bb)
+ for (; bb; prev_bb = bb, bb = bb->rbi->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++;
+ update_unlikely_executed_notes (bb);
+
+ bb->prev_bb = prev_bb;
+ prev_bb->next_bb = bb;
+ }
+ prev_bb->next_bb = EXIT_BLOCK_PTR;
+ EXIT_BLOCK_PTR->prev_bb = prev_bb;
+
+ /* Annoying special case - jump around dead jumptables left in the code. */
+ FOR_EACH_BB (bb)
+ {
+ edge e;
+ for (e = bb->succ; e && !(e->flags & EDGE_FALLTHRU); e = e->succ_next)
+ continue;
+ if (e && !can_fallthru (e->src, e->dest))
+ force_nonfallthru (e);
}
}
\f
+/* Update the basic block number information in any
+ NOTE_INSN_UNLIKELY_EXECUTED_CODE notes within the basic block. */
+
+static void
+update_unlikely_executed_notes (basic_block bb)
+{
+ rtx cur_insn;
+
+ for (cur_insn = BB_HEAD (bb); cur_insn != BB_END (bb);
+ cur_insn = NEXT_INSN (cur_insn))
+ if (GET_CODE (cur_insn) == NOTE
+ && NOTE_LINE_NUMBER (cur_insn) == NOTE_INSN_UNLIKELY_EXECUTED_CODE)
+ NOTE_BASIC_BLOCK (cur_insn) = bb;
+}
+\f
/* Perform sanity checks on the insn chain.
1. Check that next/prev pointers are consistent in both the forward and
reverse direction.
3. Check that get_last_insn () returns the actual end of chain. */
void
-verify_insn_chain ()
+verify_insn_chain (void)
{
- rtx x,
- prevx,
- nextx;
- int insn_cnt1,
- insn_cnt2;
-
- prevx = NULL;
- insn_cnt1 = 1;
- for (x = get_insns (); x; x = NEXT_INSN (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 ())
+ 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 ();
+}
+\f
+/* If we have assembler epilogues, the block falling through to exit must
+ be the last one in the reordered chain when we reach final. Ensure
+ that this condition is met. */
+static void
+fixup_fallthru_exit_predecessor (void)
+{
+ edge e;
+ basic_block bb = NULL;
+
+ /* This transformation is not valid before reload, because we might separate
+ a call from the instruction that copies the return value. */
+ if (! reload_completed)
+ abort ();
+
+ for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
+ if (e->flags & EDGE_FALLTHRU)
+ bb = e->src;
+
+ if (bb && bb->rbi->next)
{
- if (PREV_INSN (x) != prevx)
+ basic_block c = ENTRY_BLOCK_PTR->next_bb;
+
+ /* If the very first block is the one with the fall-through exit
+ edge, we have to split that block. */
+ if (c == bb)
{
- 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 ();
+ bb = split_block (bb, NULL)->dest;
+ initialize_bb_rbi (bb);
+ bb->rbi->next = c->rbi->next;
+ c->rbi->next = bb;
+ bb->rbi->footer = c->rbi->footer;
+ c->rbi->footer = NULL;
}
- ++insn_cnt1;
- prevx = x;
+
+ while (c->rbi->next != bb)
+ c = c->rbi->next;
+
+ c->rbi->next = bb->rbi->next;
+ while (c->rbi->next)
+ c = c->rbi->next;
+
+ c->rbi->next = bb;
+ bb->rbi->next = NULL;
}
+}
+\f
+/* Return true in case it is possible to duplicate the basic block BB. */
- if (prevx != get_last_insn ())
+/* We do not want to declare the function in a header file, since it should
+ only be used through the cfghooks interface, and we do not want to move
+ it to cfgrtl.c since it would require also moving quite a lot of related
+ code. */
+extern bool cfg_layout_can_duplicate_bb_p (basic_block);
+
+bool
+cfg_layout_can_duplicate_bb_p (basic_block bb)
+{
+ /* 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 (bb), NULL, NULL))
+ return false;
+
+ /* Do not duplicate blocks containing insns that can't be copied. */
+ if (targetm.cannot_copy_insn_p)
{
- fprintf (stderr, "last_insn corrupt.\n");
- abort ();
+ rtx insn = BB_HEAD (bb);
+ while (1)
+ {
+ if (INSN_P (insn) && targetm.cannot_copy_insn_p (insn))
+ return false;
+ if (insn == BB_END (bb))
+ break;
+ insn = NEXT_INSN (insn);
+ }
}
- nextx = NULL;
- insn_cnt2 = 1;
- for (x = get_last_insn (); x; x = PREV_INSN (x))
+ return true;
+}
+
+rtx
+duplicate_insn_chain (rtx from, rtx 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 (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))
{
- if (NEXT_INSN (x) != nextx)
+ switch (GET_CODE (insn))
{
- fprintf (stderr, "Reverse traversal: insn chain corrupt.\n");
- fprintf (stderr, "current insn:\n");
- debug_rtx (x);
- fprintf (stderr, "next insn:\n");
- debug_rtx (nextx);
+ 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:
+ case NOTE_INSN_UNLIKELY_EXECUTED_CODE:
+ emit_note_copy (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_copy (insn);
+ }
+ break;
+ default:
abort ();
}
- ++insn_cnt2;
- nextx = x;
}
+ insn = NEXT_INSN (last);
+ delete_insn (last);
+ return insn;
+}
+/* Create a duplicate of the basic block BB. */
- if (insn_cnt1 != insn_cnt2)
+/* We do not want to declare the function in a header file, since it should
+ only be used through the cfghooks interface, and we do not want to move
+ it to cfgrtl.c since it would require also moving quite a lot of related
+ code. */
+extern basic_block cfg_layout_duplicate_bb (basic_block);
+
+basic_block
+cfg_layout_duplicate_bb (basic_block bb)
+{
+ rtx insn;
+ basic_block new_bb;
+
+ insn = duplicate_insn_chain (BB_HEAD (bb), BB_END (bb));
+ new_bb = create_basic_block (insn,
+ insn ? get_last_insn () : NULL,
+ EXIT_BLOCK_PTR->prev_bb);
+
+ if (bb->rbi->header)
{
- fprintf (stderr, "insn_cnt1 (%d) not equal to insn_cnt2 (%d).\n",
- insn_cnt1, insn_cnt2);
- abort ();
+ insn = bb->rbi->header;
+ while (NEXT_INSN (insn))
+ insn = NEXT_INSN (insn);
+ insn = duplicate_insn_chain (bb->rbi->header, insn);
+ if (insn)
+ new_bb->rbi->header = unlink_insn_chain (insn, get_last_insn ());
}
-}
-/* The block falling trought to exit must be last in the reordered
- chain. Make it happen so. */
-static basic_block
-fixup_fallthru_exit_predecesor ()
-{
- edge e;
- basic_block bb = NULL;
+ if (bb->rbi->footer)
+ {
+ insn = bb->rbi->footer;
+ while (NEXT_INSN (insn))
+ insn = NEXT_INSN (insn);
+ insn = duplicate_insn_chain (bb->rbi->footer, insn);
+ if (insn)
+ new_bb->rbi->footer = unlink_insn_chain (insn, get_last_insn ());
+ }
- for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
- if (e->flags & EDGE_FALLTHRU)
- bb = e->src;
- if (bb && RBI (bb)->next)
+ if (bb->global_live_at_start)
{
- 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;
+ 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);
}
+
+ return new_bb;
}
\f
-/* Main entry point to this module - initialize the datastructures for
- CFG layout changes. */
+/* Main entry point to this module - initialize the data structures for
+ CFG layout changes. It keeps LOOPS up-to-date if not null. */
void
-cfg_layout_initialize ()
+cfg_layout_initialize (void)
{
- alloc_aux_for_blocks (sizeof (struct reorder_block_def));
+ basic_block bb;
+
+ /* Our algorithm depends on fact that there are no dead jumptables
+ around the code. */
+ alloc_rbi_pool ();
- build_scope_forest (&forest);
- remove_scope_notes ();
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
+ initialize_bb_rbi (bb);
+
+ cfg_layout_rtl_register_cfg_hooks ();
record_effective_endpoints ();
+
+ cleanup_cfg (CLEANUP_CFGLAYOUT);
+}
+
+/* Splits superblocks. */
+void
+break_superblocks (void)
+{
+ sbitmap superblocks;
+ bool need = false;
+ basic_block bb;
+
+ superblocks = sbitmap_alloc (last_basic_block);
+ sbitmap_zero (superblocks);
+
+ FOR_EACH_BB (bb)
+ if (bb->flags & BB_SUPERBLOCK)
+ {
+ bb->flags &= ~BB_SUPERBLOCK;
+ SET_BIT (superblocks, bb->index);
+ need = true;
+ }
+
+ 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. */
+/* Finalize the changes: reorder insn list according to the sequence, enter
+ compensation code, rebuild scope forest. */
void
-cfg_layout_finalize ()
+cfg_layout_finalize (void)
{
- fixup_fallthru_exit_predecesor ();
+ basic_block bb;
+
+#ifdef ENABLE_CHECKING
+ verify_flow_info ();
+#endif
+ rtl_register_cfg_hooks ();
+ if (reload_completed
+#ifdef HAVE_epilogue
+ && !HAVE_epilogue
+#endif
+ )
+ 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_rbi_pool ();
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
+ bb->rbi = NULL;
- free_aux_for_blocks ();
+ break_superblocks ();
#ifdef ENABLE_CHECKING
verify_flow_info ();
#endif
}
+
+/* Checks whether all N blocks in BBS array can be copied. */
+bool
+can_copy_bbs_p (basic_block *bbs, unsigned n)
+{
+ unsigned i;
+ edge e;
+ int ret = true;
+
+ for (i = 0; i < n; i++)
+ bbs[i]->rbi->duplicated = 1;
+
+ for (i = 0; i < n; i++)
+ {
+ /* In case we should redirect abnormal edge during duplication, fail. */
+ for (e = bbs[i]->succ; e; e = e->succ_next)
+ if ((e->flags & EDGE_ABNORMAL)
+ && e->dest->rbi->duplicated)
+ {
+ ret = false;
+ goto end;
+ }
+
+ if (!can_duplicate_block_p (bbs[i]))
+ {
+ ret = false;
+ break;
+ }
+ }
+
+end:
+ for (i = 0; i < n; i++)
+ bbs[i]->rbi->duplicated = 0;
+
+ return ret;
+}
+
+/* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
+ are placed into array NEW_BBS in the same order. Edges from basic blocks
+ in BBS are also duplicated and copies of those of them
+ that lead into BBS are redirected to appropriate newly created block. The
+ function assigns bbs into loops (copy of basic block bb is assigned to
+ bb->loop_father->copy loop, so this must be set up correctly in advance)
+ and updates dominators locally (LOOPS structure that contains the information
+ about dominators is passed to enable this).
+
+ BASE is the superloop to that basic block belongs; if its header or latch
+ is copied, we do not set the new blocks as header or latch.
+
+ Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
+ also in the same order. */
+
+void
+copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs,
+ edge *edges, unsigned n_edges, edge *new_edges,
+ struct loop *base)
+{
+ unsigned i, j;
+ basic_block bb, new_bb, dom_bb;
+ edge e;
+
+ /* Duplicate bbs, update dominators, assign bbs to loops. */
+ for (i = 0; i < n; i++)
+ {
+ /* Duplicate. */
+ bb = bbs[i];
+ new_bb = new_bbs[i] = duplicate_block (bb, NULL);
+ bb->rbi->duplicated = 1;
+ /* Add to loop. */
+ add_bb_to_loop (new_bb, bb->loop_father->copy);
+ /* Possibly set header. */
+ if (bb->loop_father->header == bb && bb->loop_father != base)
+ new_bb->loop_father->header = new_bb;
+ /* Or latch. */
+ if (bb->loop_father->latch == bb && bb->loop_father != base)
+ new_bb->loop_father->latch = new_bb;
+ }
+
+ /* Set dominators. */
+ for (i = 0; i < n; i++)
+ {
+ bb = bbs[i];
+ new_bb = new_bbs[i];
+
+ dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
+ if (dom_bb->rbi->duplicated)
+ {
+ dom_bb = dom_bb->rbi->copy;
+ set_immediate_dominator (CDI_DOMINATORS, new_bb, dom_bb);
+ }
+ }
+
+ /* Redirect edges. */
+ for (j = 0; j < n_edges; j++)
+ new_edges[j] = NULL;
+ for (i = 0; i < n; i++)
+ {
+ new_bb = new_bbs[i];
+ bb = bbs[i];
+
+ for (e = new_bb->succ; e; e = e->succ_next)
+ {
+ for (j = 0; j < n_edges; j++)
+ if (edges[j] && edges[j]->src == bb && edges[j]->dest == e->dest)
+ new_edges[j] = e;
+
+ if (!e->dest->rbi->duplicated)
+ continue;
+ redirect_edge_and_branch_force (e, e->dest->rbi->copy);
+ }
+ }
+
+ /* Clear information about duplicates. */
+ for (i = 0; i < n; i++)
+ bbs[i]->rbi->duplicated = 0;
+}
+
+#include "gt-cfglayout.h"
OSDN Git Service
