/* Instruction scheduling pass. Selective scheduler and pipeliner.
- Copyright (C) 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
+ Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011
+ 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);
flist_add (flist_t *lp, insn_t insn, state_t state, deps_t dc, void *tc,
insn_t last_scheduled_insn, VEC(rtx,gc) *executing_insns,
int *ready_ticks, int ready_ticks_size, insn_t sched_next,
- int cycle, int cycle_issued_insns,
+ int cycle, int cycle_issued_insns, int issue_more,
bool starts_cycle_p, bool after_stall_p)
{
fence_t f;
FENCE_TC (f) = tc;
FENCE_LAST_SCHEDULED_INSN (f) = last_scheduled_insn;
+ FENCE_ISSUE_MORE (f) = issue_more;
FENCE_EXECUTING_INSNS (f) = executing_insns;
FENCE_READY_TICKS (f) = ready_ticks;
FENCE_READY_TICKS_SIZE (f) = ready_ticks_size;
}
\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. */
gcc_assert ((s != NULL && dc != NULL && tc != NULL)
|| (s == NULL && dc == NULL && tc == NULL));
- if (s != NULL)
- free (s);
+ free (s);
if (dc != NULL)
delete_deps_context (dc);
ready_ticks_size,
NULL_RTX /* sched_next */,
1 /* cycle */, 0 /* cycle_issued_insns */,
+ issue_rate, /* issue_more */
1 /* starts_cycle_p */, 0 /* after_stall_p */);
}
}
3) all other fields are set to corresponding constant values.
INSN, STATE, DC, TC, LAST_SCHEDULED_INSN, EXECUTING_INSNS,
- READY_TICKS, READY_TICKS_SIZE, SCHED_NEXT, CYCLE and AFTER_STALL_P
- are the corresponding fields of the second fence. */
+ READY_TICKS, READY_TICKS_SIZE, SCHED_NEXT, CYCLE, ISSUE_MORE
+ and AFTER_STALL_P are the corresponding fields of the second fence. */
static void
merge_fences (fence_t f, insn_t insn,
state_t state, deps_t dc, void *tc,
rtx last_scheduled_insn, VEC(rtx, gc) *executing_insns,
int *ready_ticks, int ready_ticks_size,
- rtx sched_next, int cycle, bool after_stall_p)
+ rtx sched_next, int cycle, int issue_more, bool after_stall_p)
{
insn_t last_scheduled_insn_old = FENCE_LAST_SCHEDULED_INSN (f);
FENCE_CYCLE (f) = cycle;
FENCE_LAST_SCHEDULED_INSN (f) = NULL;
+ FENCE_ISSUE_MORE (f) = issue_rate;
VEC_free (rtx, gc, executing_insns);
free (ready_ticks);
if (FENCE_EXECUTING_INSNS (f))
/* 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)
delete_target_context (tc);
FENCE_LAST_SCHEDULED_INSN (f) = NULL;
+ FENCE_ISSUE_MORE (f) = issue_rate;
}
else
if (candidate->src == BLOCK_FOR_INSN (last_scheduled_insn))
FENCE_TC (f) = tc;
FENCE_LAST_SCHEDULED_INSN (f) = last_scheduled_insn;
+ FENCE_ISSUE_MORE (f) = issue_more;
}
else
{
state_t state, deps_t dc, void *tc, rtx last_scheduled_insn,
VEC(rtx, gc) *executing_insns, int *ready_ticks,
int ready_ticks_size, rtx sched_next, int cycle,
- int cycle_issued_insns, bool starts_cycle_p, bool after_stall_p)
+ int cycle_issued_insns, int issue_rate,
+ bool starts_cycle_p, bool after_stall_p)
{
fence_t f = flist_lookup (FLIST_TAIL_HEAD (new_fences), insn);
flist_add (FLIST_TAIL_TAILP (new_fences), insn, state, dc, tc,
last_scheduled_insn, executing_insns, ready_ticks,
ready_ticks_size, sched_next, cycle, cycle_issued_insns,
- starts_cycle_p, after_stall_p);
+ issue_rate, starts_cycle_p, after_stall_p);
FLIST_TAIL_TAILP (new_fences)
= &FLIST_NEXT (*FLIST_TAIL_TAILP (new_fences));
{
merge_fences (f, insn, state, dc, tc, last_scheduled_insn,
executing_insns, ready_ticks, ready_ticks_size,
- sched_next, cycle, after_stall_p);
+ sched_next, cycle, issue_rate, after_stall_p);
}
}
merge_fences (f, old->insn, old->state, old->dc, old->tc,
old->last_scheduled_insn, old->executing_insns,
old->ready_ticks, old->ready_ticks_size,
- old->sched_next, old->cycle,
+ old->sched_next, old->cycle, old->issue_more,
old->after_stall_p);
}
else
NULL_RTX, NULL,
XCNEWVEC (int, ready_ticks_size), ready_ticks_size,
NULL_RTX, FENCE_CYCLE (fence) + 1,
- 0, 1, FENCE_AFTER_STALL_P (fence));
+ 0, issue_rate, 1, FENCE_AFTER_STALL_P (fence));
}
/* Add a new fence to NEW_FENCES list and initialize all of its data
FENCE_SCHED_NEXT (fence),
FENCE_CYCLE (fence),
FENCE_ISSUED_INSNS (fence),
+ FENCE_ISSUE_MORE (fence),
FENCE_STARTS_CYCLE_P (fence),
FENCE_AFTER_STALL_P (fence));
}
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);
}
*pvect = NULL;
}
+/* Merge vector FROM to PVECT. */
+static void
+merge_history_vect (VEC (expr_history_def, heap) **pvect,
+ VEC (expr_history_def, heap) *from)
+{
+ expr_history_def *phist;
+ int i;
+
+ /* We keep this vector sorted. */
+ for (i = 0; VEC_iterate (expr_history_def, from, i, phist); i++)
+ insert_in_history_vect (pvect, phist->uid, phist->type,
+ phist->old_expr_vinsn, phist->new_expr_vinsn,
+ phist->spec_ds);
+}
/* Compare two vinsns as rhses if possible and as vinsns otherwise. */
bool
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)
{
else
EXPR_TARGET_AVAILABLE (to) = -1;
}
+ else if (EXPR_TARGET_AVAILABLE (from) == 0
+ && EXPR_LHS (from)
+ && REG_P (EXPR_LHS (from))
+ && REGNO (EXPR_LHS (to)) != REGNO (EXPR_LHS (from)))
+ EXPR_TARGET_AVAILABLE (to) = -1;
else
EXPR_TARGET_AVAILABLE (to) &= EXPR_TARGET_AVAILABLE (from);
}
void
merge_expr_data (expr_t to, expr_t from, insn_t split_point)
{
- int i;
- expr_history_def *phist;
-
- /* For now, we just set the spec of resulting expr to be minimum of the specs
- of merged exprs. */
- if (EXPR_SPEC (to) > EXPR_SPEC (from))
+ /* Choose the maximum of the specs of merged exprs. This is required
+ for correctness of bookkeeping. */
+ if (EXPR_SPEC (to) < EXPR_SPEC (from))
EXPR_SPEC (to) = EXPR_SPEC (from);
if (split_point)
EXPR_ORIG_SCHED_CYCLE (to) = MIN (EXPR_ORIG_SCHED_CYCLE (to),
EXPR_ORIG_SCHED_CYCLE (from));
- /* We keep this vector sorted. */
- for (i = 0;
- VEC_iterate (expr_history_def, EXPR_HISTORY_OF_CHANGES (from),
- i, phist);
- i++)
- insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (to),
- phist->uid, phist->type,
- phist->old_expr_vinsn, phist->new_expr_vinsn,
- phist->spec_ds);
-
EXPR_WAS_SUBSTITUTED (to) |= EXPR_WAS_SUBSTITUTED (from);
EXPR_WAS_RENAMED (to) |= EXPR_WAS_RENAMED (from);
EXPR_CANT_MOVE (to) |= EXPR_CANT_MOVE (from);
+ merge_history_vect (&EXPR_HISTORY_OF_CHANGES (to),
+ EXPR_HISTORY_OF_CHANGES (from));
update_target_availability (to, from, split_point);
update_speculative_bits (to, from, split_point);
}
if (EXPR_SEPARABLE_P (expr))
{
if (REG_P (EXPR_LHS (expr))
- && bitmap_bit_p (lv_set, REGNO (EXPR_LHS (expr))))
+ && register_unavailable_p (lv_set, EXPR_LHS (expr)))
{
/* If it's an insn like r1 = use (r1, ...), and it exists in
different forms in each of the av_sets being merged, we can't say
miss a unifying code motion along both branches using a renamed
register, but it won't affect a code correctness since upon
an actual code motion a bookkeeping code would be generated. */
- if (bitmap_bit_p (VINSN_REG_USES (EXPR_VINSN (expr)),
- REGNO (EXPR_LHS (expr))))
+ if (register_unavailable_p (VINSN_REG_USES (EXPR_VINSN (expr)),
+ EXPR_LHS (expr)))
EXPR_TARGET_AVAILABLE (expr) = -1;
else
EXPR_TARGET_AVAILABLE (expr) = false;
/* Do not allow clobbering the address register of speculative
insns. */
- if (bitmap_bit_p (VINSN_REG_USES (EXPR_VINSN (expr)),
- expr_dest_regno (expr)))
+ if (register_unavailable_p (VINSN_REG_USES (EXPR_VINSN (expr)),
+ expr_dest_reg (expr)))
{
EXPR_TARGET_AVAILABLE (expr) = false;
return 2;
}
\f
+/* Returns true if REG (at least partially) is present in REGS. */
+bool
+register_unavailable_p (regset regs, rtx reg)
+{
+ unsigned regno, end_regno;
+
+ regno = REGNO (reg);
+ if (bitmap_bit_p (regs, regno))
+ return true;
+
+ end_regno = END_REGNO (reg);
+
+ while (++regno < end_regno)
+ if (bitmap_bit_p (regs, regno))
+ return true;
+
+ return false;
+}
+
/* Av set functions. */
/* Add a new element to av set SETP.
}
/* Leave in AVP only those expressions, which are present in AV,
- and return it. */
+ and return it, merging history expressions. */
void
-av_set_intersect (av_set_t *avp, av_set_t av)
+av_set_code_motion_filter (av_set_t *avp, av_set_t av)
{
av_set_iterator i;
- expr_t expr;
+ expr_t expr, expr2;
FOR_EACH_EXPR_1 (expr, i, avp)
- if (av_set_lookup (av, EXPR_VINSN (expr)) == NULL)
+ if ((expr2 = av_set_lookup (av, EXPR_VINSN (expr))) == NULL)
av_set_iter_remove (&i);
+ else
+ /* When updating av sets in bookkeeping blocks, we can add more insns
+ there which will be transformed but the upper av sets will not
+ reflect those transformations. We then fail to undo those
+ when searching for such insns. So merge the history saved
+ in the av set of the block we are processing. */
+ merge_history_vect (&EXPR_HISTORY_OF_CHANGES (expr),
+ EXPR_HISTORY_OF_CHANGES (expr2));
}
\f
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;
}
\f
+struct sched_scan_info_def
+{
+ /* This hook notifies scheduler frontend to extend its internal per basic
+ block data structures. This hook should be called once before a series of
+ calls to bb_init (). */
+ void (*extend_bb) (void);
+
+ /* This hook makes scheduler frontend to initialize its internal data
+ structures for the passed basic block. */
+ void (*init_bb) (basic_block);
+
+ /* This hook notifies scheduler frontend to extend its internal per insn data
+ structures. This hook should be called once before a series of calls to
+ insn_init (). */
+ void (*extend_insn) (void);
+
+ /* This hook makes scheduler frontend to initialize its internal data
+ structures for the passed insn. */
+ void (*init_insn) (rtx);
+};
+
+/* A driver function to add a set of basic blocks (BBS) to the
+ scheduling region. */
+static void
+sched_scan (const struct sched_scan_info_def *ssi, bb_vec_t bbs)
+{
+ unsigned i;
+ basic_block bb;
+
+ if (ssi->extend_bb)
+ ssi->extend_bb ();
+
+ if (ssi->init_bb)
+ FOR_EACH_VEC_ELT (basic_block, bbs, i, bb)
+ ssi->init_bb (bb);
+
+ if (ssi->extend_insn)
+ ssi->extend_insn ();
+
+ if (ssi->init_insn)
+ FOR_EACH_VEC_ELT (basic_block, bbs, i, bb)
+ {
+ rtx insn;
+
+ FOR_BB_INSNS (bb, insn)
+ ssi->init_insn (insn);
+ }
+}
/* Implement hooks for collecting fundamental insn properties like if insn is
an ASM or is within a SCHED_GROUP. */
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)
+ || CALL_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)
+ || volatile_insn_p (PATTERN (insn))
+ || (targetm.cannot_copy_insn_p
+ && targetm.cannot_copy_insn_p (insn)))
+ force_unique_p = true;
+ else
+ force_unique_p = false;
if (targetm.sched.get_insn_spec_ds)
{
init_global_and_expr_for_insn /* init_insn */
};
- sched_scan (&ssi, bbs, NULL, NULL, NULL);
+ sched_scan (&ssi, bbs);
}
/* Finalize region-scope data structures for basic blocks. */
finish_global_and_expr_insn /* init_insn */
};
- sched_scan (&ssi, bbs, NULL, NULL, NULL);
+ sched_scan (&ssi, bbs);
}
VEC_free (basic_block, heap, bbs);
pro_spec_checked_ds = INSN_SPEC_CHECKED_DS (has_dependence_data.pro);
pro_spec_checked_ds = ds_get_max_dep_weak (pro_spec_checked_ds);
- if (pro_spec_checked_ds != 0)
+ if (pro_spec_checked_ds != 0
+ && bitmap_bit_p (INSN_REG_SETS (has_dependence_data.pro), regno))
/* Merge BE_IN_SPEC bits into *DSP. */
*dsp = ds_full_merge (*dsp, pro_spec_checked_ds,
NULL_RTX, NULL_RTX);
{
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;
/* Keep empty bb only if this block immediately precedes EXIT and
- has incoming non-fallthrough edge. Otherwise remove it. */
+ has incoming non-fallthrough edge, or it has no predecessors or
+ successors. Otherwise remove it. */
if (!sel_bb_empty_p (bb)
|| (single_succ_p (bb)
&& single_succ (bb) == EXIT_BLOCK_PTR
&& (!single_pred_p (bb)
- || !(single_pred_edge (bb)->flags & EDGE_FALLTHRU))))
+ || !(single_pred_edge (bb)->flags & EDGE_FALLTHRU)))
+ || EDGE_COUNT (bb->preds) == 0
+ || EDGE_COUNT (bb->succs) == 0)
return false;
/* Do not attempt to redirect complex edges. */
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);
- move_bb_info (pred_bb, bb);
+ if (in_current_region_p (pred_bb))
+ move_bb_info (pred_bb, 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++;
return -1;
}
-/* Return seqno of the only predecessor of INSN. */
+/* Find the proper seqno for inserting at INSN by successors.
+ Return -1 if no successors with positive seqno exist. */
+static int
+get_seqno_by_succs (rtx insn)
+{
+ basic_block bb = BLOCK_FOR_INSN (insn);
+ rtx tmp = insn, end = BB_END (bb);
+ int seqno;
+ insn_t succ = NULL;
+ succ_iterator si;
+
+ while (tmp != end)
+ {
+ tmp = NEXT_INSN (tmp);
+ if (INSN_P (tmp))
+ return INSN_SEQNO (tmp);
+ }
+
+ seqno = INT_MAX;
+
+ FOR_EACH_SUCC_1 (succ, si, end, SUCCS_NORMAL)
+ if (INSN_SEQNO (succ) > 0)
+ seqno = MIN (seqno, INSN_SEQNO (succ));
+
+ if (seqno == INT_MAX)
+ return -1;
+
+ return seqno;
+}
+
+/* Compute seqno for INSN by its preds or succs. */
static int
-get_seqno_of_a_pred (insn_t insn)
+get_seqno_for_a_jump (insn_t insn)
{
int seqno;
int n;
cfg_preds (BLOCK_FOR_INSN (insn), &preds, &n);
- gcc_assert (n == 1);
- seqno = INSN_SEQNO (preds[0]);
+ gcc_assert (n > 0);
+ /* For one predecessor, use simple method. */
+ if (n == 1)
+ seqno = INSN_SEQNO (preds[0]);
+ else
+ seqno = get_seqno_by_preds (insn);
free (preds);
}
}
+ /* We were unable to find a good seqno among preds. */
+ if (seqno < 0)
+ seqno = get_seqno_by_succs (insn);
+
+ gcc_assert (seqno >= 0);
+
return seqno;
}
int n, i, seqno;
while (tmp != head)
- if (INSN_P (tmp))
- return INSN_SEQNO (tmp);
- else
+ {
tmp = PREV_INSN (tmp);
+ if (INSN_P (tmp))
+ return INSN_SEQNO (tmp);
+ }
cfg_preds (bb, &preds, &n);
for (i = 0, seqno = -1; i < n; i++)
/* Data for each insn in current region. */
VEC (sel_insn_data_def, heap) *s_i_d = NULL;
-/* A vector for the insns we've emitted. */
-static insn_vec_t new_insns = NULL;
-
/* Extend data structures for insns from current region. */
static void
extend_insn_data (void)
init_expr (INSN_EXPR (insn), vinsn_create (insn, false), 0,
REG_BR_PROB_BASE, 0, 0, 0, 0, 0, 0, NULL, true, false, false,
false, true);
- INSN_SEQNO (insn) = get_seqno_of_a_pred (insn);
+ INSN_SEQNO (insn) = get_seqno_for_a_jump (insn);
init_first_time_insn_data (insn);
}
}
if (flags & INSN_INIT_TODO_LUID)
- sched_init_luids (NULL, NULL, NULL, insn);
+ {
+ sched_extend_luids ();
+ sched_init_insn_luid (insn);
+ }
if (flags & INSN_INIT_TODO_SSID)
{
free_lv_set (bb);
}
-/* Initialize an invalid AV_SET for BB.
- This set will be updated next time compute_av () process BB. */
+/* Mark AV_SET for BB as invalid, so this set will be updated the next time
+ compute_av() processes BB. This function is called when creating new basic
+ blocks, as well as for blocks (either new or existing) where new jumps are
+ created when the control flow is being updated. */
static void
invalidate_av_set (basic_block bb)
{
- gcc_assert (BB_AV_LEVEL (bb) <= 0
- && BB_AV_SET (bb) == NULL);
-
BB_AV_LEVEL (bb) = -1;
}
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;
}
void
-sel_init_bbs (bb_vec_t bbs, basic_block bb)
+sel_init_bbs (bb_vec_t bbs)
{
const struct sched_scan_info_def ssi =
{
NULL /* init_insn */
};
- sched_scan (&ssi, bbs, bb, new_insns, NULL);
+ sched_scan (&ssi, bbs);
}
-/* 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;
}
sel_add_bb (basic_block bb)
{
/* Extend luids so that new notes will receive zero luids. */
- sched_init_luids (NULL, NULL, NULL, NULL);
+ sched_extend_luids ();
sched_init_bbs ();
- sel_init_bbs (last_added_blocks, NULL);
+ sel_init_bbs (last_added_blocks);
/* When bb is passed explicitly, the vector should contain
the only element that equals to bb; otherwise, the vector
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;
}
end_sequence ();
- sched_init_luids (NULL, NULL, NULL, NULL);
+ sched_extend_luids ();
sched_extend_target ();
sched_deps_init (false);
NULL, /* add_remove_insn */
NULL, /* begin_schedule_ready */
+ NULL, /* begin_move_insn */
NULL, /* advance_target_bb */
+
+ NULL,
+ NULL,
+
SEL_SCHED | NEW_BBS
};
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);
latch. We can't use header here, because this header could be
just removed preheader and it will give us the wrong region number.
Latch can't be used because it could be in the inner loop too. */
- if (LOOP_MARKED_FOR_PIPELINING_P (loop) && pipelining_p)
+ if (LOOP_MARKED_FOR_PIPELINING_P (loop))
{
int rgn = CONTAINING_RGN (loop->latch->index);
bbs_in_loop_rgns = NULL;
}
-/* Adds the preheader blocks from previous loop to current region taking
- it from LOOP_PREHEADER_BLOCKS (current_loop_nest).
+/* Add the preheader blocks from previous loop to current region taking
+ it from LOOP_PREHEADER_BLOCKS (current_loop_nest) and record them in *BBS.
This function is only used with -fsel-sched-pipelining-outer-loops. */
void
-sel_add_loop_preheaders (void)
+sel_add_loop_preheaders (bb_vec_t *bbs)
{
int i;
basic_block bb;
for (i = 0;
VEC_iterate (basic_block, preheader_blocks, i, bb);
i++)
+ {
+ VEC_safe_push (basic_block, heap, *bbs, bb);
+ VEC_safe_push (basic_block, heap, last_added_blocks, bb);
sel_add_bb (bb);
+ }
VEC_free (basic_block, heap, preheader_blocks);
}
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
