/* Instruction scheduling pass. Selective scheduler and pipeliner.
- Copyright (C) 2006, 2007, 2008, 2009, 2010 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);
}
\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);
/* 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);
}
*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;
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++;
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 notes for the whole region. */
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);
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;
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);
}
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);