/* Instruction scheduling pass. Selective scheduler and pipeliner.
- Copyright (C) 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
+ Copyright (C) 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
This file is part of GCC.
#include "system.h"
#include "coretypes.h"
#include "tm.h"
-#include "toplev.h"
+#include "diagnostic-core.h"
#include "rtl.h"
#include "tm_p.h"
#include "hard-reg-set.h"
#include "insn-config.h"
#include "insn-attr.h"
#include "except.h"
-#include "toplev.h"
#include "recog.h"
#include "params.h"
#include "target.h"
#include "vec.h"
#include "langhooks.h"
#include "rtlhooks-def.h"
+#include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
#ifdef INSN_SCHEDULING
#include "sel-sched-ir.h"
static void move_bb_info (basic_block, basic_block);
static void remove_empty_bb (basic_block, bool);
+static void sel_merge_blocks (basic_block, basic_block);
static void sel_remove_loop_preheader (void);
+static bool bb_has_removable_jump_to_p (basic_block, basic_block);
static bool insn_is_the_only_one_in_bb_p (insn_t);
static void create_initial_data_sets (basic_block);
}
\f
/* Functions to work with dependence contexts.
- Dc (aka deps context, aka deps_t, aka struct deps *) is short for dependence
+ Dc (aka deps context, aka deps_t, aka struct deps_desc *) is short for dependence
context. It accumulates information about processed insns to decide if
current insn is dependent on the processed ones. */
static deps_t
alloc_deps_context (void)
{
- return XNEW (struct deps);
+ return XNEW (struct deps_desc);
}
/* Allocate and initialize dep context. */
/* Find fallthrough edge. */
gcc_assert (BLOCK_FOR_INSN (insn)->prev_bb);
- candidate = find_fallthru_edge (BLOCK_FOR_INSN (insn)->prev_bb);
+ candidate = find_fallthru_edge_from (BLOCK_FOR_INSN (insn)->prev_bb);
if (!candidate
|| (candidate->src != BLOCK_FOR_INSN (last_scheduled_insn)
void
return_regset_to_pool (regset rs)
{
+ gcc_assert (rs);
regset_pool.diff--;
if (regset_pool.n == regset_pool.s)
VINSN_COUNT (vi) = 0;
vi->cost = -1;
+ if (INSN_NOP_P (insn))
+ return;
+
if (DF_INSN_UID_SAFE_GET (INSN_UID (insn)) != NULL)
init_id_from_df (VINSN_ID (vi), insn, force_unique_p);
else
{
gcc_assert (VINSN_COUNT (vi) == 0);
- return_regset_to_pool (VINSN_REG_SETS (vi));
- return_regset_to_pool (VINSN_REG_USES (vi));
- return_regset_to_pool (VINSN_REG_CLOBBERS (vi));
+ if (!INSN_NOP_P (VINSN_INSN_RTX (vi)))
+ {
+ return_regset_to_pool (VINSN_REG_SETS (vi));
+ return_regset_to_pool (VINSN_REG_USES (vi));
+ return_regset_to_pool (VINSN_REG_CLOBBERS (vi));
+ }
free (vi);
}
init_expr (expr_t expr, vinsn_t vi, int spec, int use, int priority,
int sched_times, int orig_bb_index, ds_t spec_done_ds,
ds_t spec_to_check_ds, int orig_sched_cycle,
- VEC(expr_history_def, heap) *history, bool target_available,
+ VEC(expr_history_def, heap) *history, signed char target_available,
bool was_substituted, bool was_renamed, bool needs_spec_check_p,
bool cant_move)
{
static void
deps_init_id (idata_t id, insn_t insn, bool force_unique_p)
{
- struct deps _dc, *dc = &_dc;
+ struct deps_desc _dc, *dc = &_dc;
deps_init_id_data.where = DEPS_IN_NOWHERE;
deps_init_id_data.id = id;
bool force_unique_p;
ds_t spec_done_ds;
- /* Certain instructions cannot be cloned. */
- if (CANT_MOVE (insn)
- || INSN_ASM_P (insn)
- || SCHED_GROUP_P (insn)
- || prologue_epilogue_contains (insn)
- /* Exception handling insns are always unique. */
- || (flag_non_call_exceptions && can_throw_internal (insn))
- /* TRAP_IF though have an INSN code is control_flow_insn_p (). */
- || control_flow_insn_p (insn))
- force_unique_p = true;
+ /* Certain instructions cannot be cloned, and frame related insns and
+ the insn adjacent to NOTE_INSN_EPILOGUE_BEG cannot be moved out of
+ their block. */
+ if (prologue_epilogue_contains (insn))
+ {
+ if (RTX_FRAME_RELATED_P (insn))
+ CANT_MOVE (insn) = 1;
+ else
+ {
+ rtx note;
+ for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
+ if (REG_NOTE_KIND (note) == REG_SAVE_NOTE
+ && ((enum insn_note) INTVAL (XEXP (note, 0))
+ == NOTE_INSN_EPILOGUE_BEG))
+ {
+ CANT_MOVE (insn) = 1;
+ break;
+ }
+ }
+ force_unique_p = true;
+ }
else
- force_unique_p = false;
+ if (CANT_MOVE (insn)
+ || INSN_ASM_P (insn)
+ || SCHED_GROUP_P (insn)
+ /* Exception handling insns are always unique. */
+ || (cfun->can_throw_non_call_exceptions && can_throw_internal (insn))
+ /* TRAP_IF though have an INSN code is control_flow_insn_p (). */
+ || control_flow_insn_p (insn))
+ force_unique_p = true;
+ else
+ force_unique_p = false;
if (targetm.sched.get_insn_spec_ds)
{
{
int i;
ds_t ds;
- struct deps *dc;
+ struct deps_desc *dc;
if (INSN_SIMPLEJUMP_P (pred))
/* Unconditional jump is just a transfer of control flow.
/* Tidy the possibly empty block BB. */
static bool
-maybe_tidy_empty_bb (basic_block bb, bool recompute_toporder_p)
+maybe_tidy_empty_bb (basic_block bb)
{
basic_block succ_bb, pred_bb;
+ VEC (basic_block, heap) *dom_bbs;
edge e;
edge_iterator ei;
bool rescan_p;
succ_bb = single_succ (bb);
rescan_p = true;
pred_bb = NULL;
+ dom_bbs = NULL;
/* Redirect all non-fallthru edges to the next bb. */
while (rescan_p)
if (!(e->flags & EDGE_FALLTHRU))
{
- recompute_toporder_p |= sel_redirect_edge_and_branch (e, succ_bb);
+ /* We can not invalidate computed topological order by moving
+ the edge destination block (E->SUCC) along a fallthru edge.
+
+ We will update dominators here only when we'll get
+ an unreachable block when redirecting, otherwise
+ sel_redirect_edge_and_branch will take care of it. */
+ if (e->dest != bb
+ && single_pred_p (e->dest))
+ VEC_safe_push (basic_block, heap, dom_bbs, e->dest);
+ sel_redirect_edge_and_branch (e, succ_bb);
rescan_p = true;
break;
}
+ /* If the edge is fallthru, but PRED_BB ends in a conditional jump
+ to BB (so there is no non-fallthru edge from PRED_BB to BB), we
+ still have to adjust it. */
+ else if (single_succ_p (pred_bb) && any_condjump_p (BB_END (pred_bb)))
+ {
+ /* If possible, try to remove the unneeded conditional jump. */
+ if (INSN_SCHED_TIMES (BB_END (pred_bb)) == 0
+ && !IN_CURRENT_FENCE_P (BB_END (pred_bb)))
+ {
+ if (!sel_remove_insn (BB_END (pred_bb), false, false))
+ tidy_fallthru_edge (e);
+ }
+ else
+ sel_redirect_edge_and_branch (e, succ_bb);
+ rescan_p = true;
+ break;
+ }
}
}
- /* If it is possible - merge BB with its predecessor. */
if (can_merge_blocks_p (bb->prev_bb, bb))
sel_merge_blocks (bb->prev_bb, bb);
else
- /* Otherwise this is a block without fallthru predecessor.
- Just delete it. */
{
+ /* This is a block without fallthru predecessor. Just delete it. */
gcc_assert (pred_bb != NULL);
if (in_current_region_p (pred_bb))
remove_empty_bb (bb, true);
}
- if (recompute_toporder_p)
- sel_recompute_toporder ();
-
-#ifdef ENABLE_CHECKING
- verify_backedges ();
-#endif
+ if (!VEC_empty (basic_block, dom_bbs))
+ {
+ VEC_safe_push (basic_block, heap, dom_bbs, succ_bb);
+ iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, false);
+ VEC_free (basic_block, heap, dom_bbs);
+ }
return true;
}
insn_t first, last;
/* First check whether XBB is empty. */
- changed = maybe_tidy_empty_bb (xbb, false);
+ changed = maybe_tidy_empty_bb (xbb);
if (changed || !full_tidying)
return changed;
/* Check if there is a unnecessary jump after insn left. */
- if (jump_leads_only_to_bb_p (BB_END (xbb), xbb->next_bb)
+ if (bb_has_removable_jump_to_p (xbb, xbb->next_bb)
&& INSN_SCHED_TIMES (BB_END (xbb)) == 0
&& !IN_CURRENT_FENCE_P (BB_END (xbb)))
{
/* And unconditional jump in previous basic block leads to
next basic block of XBB and this jump can be safely removed. */
&& in_current_region_p (xbb->prev_bb)
- && jump_leads_only_to_bb_p (BB_END (xbb->prev_bb), xbb->next_bb)
+ && bb_has_removable_jump_to_p (xbb->prev_bb, xbb->next_bb)
&& INSN_SCHED_TIMES (BB_END (xbb->prev_bb)) == 0
/* Also this jump is not at the scheduling boundary. */
&& !IN_CURRENT_FENCE_P (BB_END (xbb->prev_bb)))
that contained that jump, becomes empty too. In such case
remove it too. */
if (sel_bb_empty_p (xbb->prev_bb))
- changed = maybe_tidy_empty_bb (xbb->prev_bb, recompute_toporder_p);
- else if (recompute_toporder_p)
+ changed = maybe_tidy_empty_bb (xbb->prev_bb);
+ if (recompute_toporder_p)
sel_recompute_toporder ();
}
+#ifdef ENABLE_CHECKING
+ verify_backedges ();
+ verify_dominators (CDI_DOMINATORS);
+#endif
+
return changed;
}
void
purge_empty_blocks (void)
{
- /* Do not attempt to delete preheader. */
- int i = sel_is_loop_preheader_p (BASIC_BLOCK (BB_TO_BLOCK (0))) ? 1 : 0;
+ int i;
- while (i < current_nr_blocks)
+ /* Do not attempt to delete the first basic block in the region. */
+ for (i = 1; i < current_nr_blocks; )
{
basic_block b = BASIC_BLOCK (BB_TO_BLOCK (i));
- if (maybe_tidy_empty_bb (b, false))
+ if (maybe_tidy_empty_bb (b))
continue;
i++;
note = bb_note (bb);
head = next_nonnote_insn (note);
- if (head && BLOCK_FOR_INSN (head) != bb)
+ if (head && (BARRIER_P (head) || BLOCK_FOR_INSN (head) != bb))
head = NULL_RTX;
}
if (!JUMP_P (jump))
return NULL;
- if (any_uncondjump_p (jump))
- return single_succ (BLOCK_FOR_INSN (jump));
-
if (!any_condjump_p (jump))
return NULL;
sched_scan (&ssi, bbs, bb, new_insns, NULL);
}
-/* Restore other notes for the whole region. */
+/* Restore notes for the whole region. */
static void
-sel_restore_other_notes (void)
+sel_restore_notes (void)
{
int bb;
+ insn_t insn;
for (bb = 0; bb < current_nr_blocks; bb++)
{
restore_other_notes (NULL, first);
BB_NOTE_LIST (first) = NULL_RTX;
+ FOR_BB_INSNS (first, insn)
+ if (NONDEBUG_INSN_P (insn))
+ reemit_notes (insn);
+
first = first->next_bb;
}
while (first != last);
void
sel_finish_bbs (void)
{
- sel_restore_other_notes ();
+ sel_restore_notes ();
/* Remove current loop preheader from this loop. */
if (current_loop_nest)
basic_block pred_bb = e->src;
insn_t bb_end = BB_END (pred_bb);
- /* ??? This code is not supposed to walk out of a region. */
- gcc_assert (in_current_region_p (pred_bb));
+ if (!in_current_region_p (pred_bb))
+ {
+ gcc_assert (flag_sel_sched_pipelining_outer_loops
+ && current_loop_nest);
+ continue;
+ }
if (sel_bb_empty_p (pred_bb))
cfg_preds_1 (pred_bb, preds, n, size);
}
}
- gcc_assert (*n != 0);
+ gcc_assert (*n != 0
+ || (flag_sel_sched_pipelining_outer_loops
+ && current_loop_nest));
}
/* Find all predecessors of BB and record them in PREDS and their number
{
basic_block next_bb = bb_next_bb (bb);
edge e;
- edge_iterator ei;
if (next_bb == EXIT_BLOCK_PTR
|| bitmap_bit_p (forced_ebb_heads, next_bb->index)
if (!in_current_region_p (next_bb))
return true;
- FOR_EACH_EDGE (e, ei, bb->succs)
- if ((e->flags & EDGE_FALLTHRU) != 0)
- {
- gcc_assert (e->dest == next_bb);
-
- return false;
- }
+ e = find_fallthru_edge (bb->succs);
+ if (e)
+ {
+ gcc_assert (e->dest == next_bb);
+
+ return false;
+ }
return true;
}
static void
sel_remove_bb (basic_block bb, bool remove_from_cfg_p)
{
+ unsigned idx = bb->index;
+
gcc_assert (bb != NULL && BB_NOTE_LIST (bb) == NULL_RTX);
remove_bb_from_region (bb);
return_bb_to_pool (bb);
- bitmap_clear_bit (blocks_to_reschedule, bb->index);
+ bitmap_clear_bit (blocks_to_reschedule, idx);
if (remove_from_cfg_p)
- delete_and_free_basic_block (bb);
+ {
+ basic_block succ = single_succ (bb);
+ delete_and_free_basic_block (bb);
+ set_immediate_dominator (CDI_DOMINATORS, succ,
+ recompute_dominator (CDI_DOMINATORS, succ));
+ }
- rgn_setup_region (CONTAINING_RGN (bb->index));
+ rgn_setup_region (CONTAINING_RGN (idx));
}
/* Concatenate info of EMPTY_BB to info of MERGE_BB. */
}
-/* Remove an empty basic block EMPTY_BB. When MERGE_UP_P is true, we put
- EMPTY_BB's note lists into its predecessor instead of putting them
- into the successor. When REMOVE_FROM_CFG_P is true, also remove
- the empty block. */
-void
-sel_remove_empty_bb (basic_block empty_bb, bool merge_up_p,
- bool remove_from_cfg_p)
-{
- basic_block merge_bb;
-
- gcc_assert (sel_bb_empty_p (empty_bb));
-
- if (merge_up_p)
- {
- merge_bb = empty_bb->prev_bb;
- gcc_assert (EDGE_COUNT (empty_bb->preds) == 1
- && EDGE_PRED (empty_bb, 0)->src == merge_bb);
- }
- else
- {
- edge e;
- edge_iterator ei;
-
- merge_bb = bb_next_bb (empty_bb);
-
- /* Redirect incoming edges (except fallthrough one) of EMPTY_BB to its
- successor block. */
- for (ei = ei_start (empty_bb->preds);
- (e = ei_safe_edge (ei)); )
- {
- if (! (e->flags & EDGE_FALLTHRU))
- sel_redirect_edge_and_branch (e, merge_bb);
- else
- ei_next (&ei);
- }
-
- gcc_assert (EDGE_COUNT (empty_bb->succs) == 1
- && EDGE_SUCC (empty_bb, 0)->dest == merge_bb);
- }
-
- move_bb_info (merge_bb, empty_bb);
- remove_empty_bb (empty_bb, remove_from_cfg_p);
-}
-
/* Remove EMPTY_BB. If REMOVE_FROM_CFG_P is false, remove EMPTY_BB from
region, but keep it in CFG. */
static void
}
/* Merge basic block B into basic block A. */
-void
+static void
sel_merge_blocks (basic_block a, basic_block b)
{
- sel_remove_empty_bb (b, true, false);
- merge_blocks (a, b);
+ gcc_assert (sel_bb_empty_p (b)
+ && EDGE_COUNT (b->preds) == 1
+ && EDGE_PRED (b, 0)->src == b->prev_bb);
+ move_bb_info (b->prev_bb, b);
+ remove_empty_bb (b, false);
+ merge_blocks (a, b);
change_loops_latches (b, a);
}
void
sel_redirect_edge_and_branch_force (edge e, basic_block to)
{
- basic_block jump_bb, src;
+ basic_block jump_bb, src, orig_dest = e->dest;
int prev_max_uid;
rtx jump;
- gcc_assert (!sel_bb_empty_p (e->src));
-
+ /* This function is now used only for bookkeeping code creation, where
+ we'll never get the single pred of orig_dest block and thus will not
+ hit unreachable blocks when updating dominator info. */
+ gcc_assert (!sel_bb_empty_p (e->src)
+ && !single_pred_p (orig_dest));
src = e->src;
prev_max_uid = get_max_uid ();
jump_bb = redirect_edge_and_branch_force (e, to);
jump = find_new_jump (src, jump_bb, prev_max_uid);
if (jump)
sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
+ set_immediate_dominator (CDI_DOMINATORS, to,
+ recompute_dominator (CDI_DOMINATORS, to));
+ set_immediate_dominator (CDI_DOMINATORS, orig_dest,
+ recompute_dominator (CDI_DOMINATORS, orig_dest));
}
/* A wrapper for redirect_edge_and_branch. Return TRUE if blocks connected by
sel_redirect_edge_and_branch (edge e, basic_block to)
{
bool latch_edge_p;
- basic_block src;
+ basic_block src, orig_dest = e->dest;
int prev_max_uid;
rtx jump;
edge redirected;
bool recompute_toporder_p = false;
+ bool maybe_unreachable = single_pred_p (orig_dest);
latch_edge_p = (pipelining_p
&& current_loop_nest
if (jump)
sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
+ /* Only update dominator info when we don't have unreachable blocks.
+ Otherwise we'll update in maybe_tidy_empty_bb. */
+ if (!maybe_unreachable)
+ {
+ set_immediate_dominator (CDI_DOMINATORS, to,
+ recompute_dominator (CDI_DOMINATORS, to));
+ set_immediate_dominator (CDI_DOMINATORS, orig_dest,
+ recompute_dominator (CDI_DOMINATORS, orig_dest));
+ }
return recompute_toporder_p;
}
gcc_assert (nop_pattern == NULL_RTX
&& exit_insn == NULL_RTX);
- nop_pattern = gen_nop ();
+ nop_pattern = constm1_rtx;
start_sequence ();
emit_insn (nop_pattern);
new_rgn_number = sel_create_new_region ();
- for (i = 0; VEC_iterate (basic_block, *loop_blocks, i, bb); i++)
+ FOR_EACH_VEC_ELT (basic_block, *loop_blocks, i, bb)
{
gcc_assert (new_rgn_number >= 0);
return false;
}
-/* Checks whether JUMP leads to basic block DEST_BB and no other blocks. */
-bool
-jump_leads_only_to_bb_p (insn_t jump, basic_block dest_bb)
+/* Check whether JUMP_BB ends with a jump insn that leads only to DEST_BB and
+ can be removed, making the corresponding edge fallthrough (assuming that
+ all basic blocks between JUMP_BB and DEST_BB are empty). */
+static bool
+bb_has_removable_jump_to_p (basic_block jump_bb, basic_block dest_bb)
{
- basic_block jump_bb = BLOCK_FOR_INSN (jump);
-
- /* It is not jump, jump with side-effects or jump can lead to several
- basic blocks. */
- if (!onlyjump_p (jump)
- || !any_uncondjump_p (jump))
+ if (!onlyjump_p (BB_END (jump_bb))
+ || tablejump_p (BB_END (jump_bb), NULL, NULL))
return false;
/* Several outgoing edges, abnormal edge or destination of jump is
not DEST_BB. */
if (EDGE_COUNT (jump_bb->succs) != 1
- || EDGE_SUCC (jump_bb, 0)->flags & EDGE_ABNORMAL
+ || EDGE_SUCC (jump_bb, 0)->flags & (EDGE_ABNORMAL | EDGE_CROSSING)
|| EDGE_SUCC (jump_bb, 0)->dest != dest_bb)
return false;
{
/* If all preheader blocks are empty - dont create new empty region.
Instead, remove them completely. */
- for (i = 0; VEC_iterate (basic_block, preheader_blocks, i, bb); i++)
+ FOR_EACH_VEC_ELT (basic_block, preheader_blocks, i, bb)
{
edge e;
edge_iterator ei;
basic block if it becomes empty. */
if (next_bb->prev_bb == prev_bb
&& prev_bb != ENTRY_BLOCK_PTR
- && jump_leads_only_to_bb_p (BB_END (prev_bb), next_bb))
+ && bb_has_removable_jump_to_p (prev_bb, next_bb))
{
redirect_edge_and_branch (EDGE_SUCC (prev_bb, 0), next_bb);
if (BB_END (prev_bb) == bb_note (prev_bb))
free_data_sets (prev_bb);
}
+
+ set_immediate_dominator (CDI_DOMINATORS, next_bb,
+ recompute_dominator (CDI_DOMINATORS,
+ next_bb));
}
}
VEC_free (basic_block, heap, preheader_blocks);
OSDN Git Service
