/* Scheduling clock. */
static int clock_var;
+/* This records the actual schedule. It is built up during the main phase
+ of schedule_block, and afterwards used to reorder the insns in the RTL. */
+static VEC(rtx, heap) *scheduled_insns;
+
static int may_trap_exp (const_rtx, int);
/* Nonzero iff the address is comprised from at most 1 register. */
static int priority (rtx);
static int rank_for_schedule (const void *, const void *);
static void swap_sort (rtx *, int);
-static void queue_insn (rtx, int);
+static void queue_insn (rtx, int, const char *);
static int schedule_insn (rtx);
static void adjust_priority (rtx);
static void advance_one_cycle (void);
fprintf (sched_dump, "\n");
}
-/* Pointer to the last instruction scheduled. Used by rank_for_schedule,
- so that insns independent of the last scheduled insn will be preferred
- over dependent instructions. */
-
+/* Pointer to the last instruction scheduled. */
static rtx last_scheduled_insn;
+/* Pointer that iterates through the list of unscheduled insns if we
+ have a dbg_cnt enabled. It always points at an insn prior to the
+ first unscheduled one. */
+static rtx nonscheduled_insns_begin;
+
/* Cached cost of the instruction. Use below function to get cost of the
insn. -1 here means that the field is not initialized. */
#define INSN_COST(INSN) (HID (INSN)->cost)
/* A USE insn should never require the value used to be computed.
This allows the computation of a function's result and parameter
values to overlap the return and call. We don't care about the
- the dependence cost when only decreasing register pressure. */
+ dependence cost when only decreasing register pressure. */
if (recog_memoized (used) < 0)
{
cost = 0;
if (flag_sched_last_insn_heuristic)
{
- last = last_scheduled_insn;
-
- if (DEBUG_INSN_P (last) && last != current_sched_info->prev_head)
- do
- last = PREV_INSN (last);
- while (!NONDEBUG_INSN_P (last)
- && last != current_sched_info->prev_head);
+ int i = VEC_length (rtx, scheduled_insns);
+ last = NULL_RTX;
+ while (i-- > 0)
+ {
+ last = VEC_index (rtx, scheduled_insns, i);
+ if (NONDEBUG_INSN_P (last))
+ break;
+ }
}
/* Compare insns based on their relation to the last scheduled
non-debug insn. */
- if (flag_sched_last_insn_heuristic && NONDEBUG_INSN_P (last))
+ if (flag_sched_last_insn_heuristic && last && NONDEBUG_INSN_P (last))
{
dep_t dep1;
dep_t dep2;
/* Add INSN to the insn queue so that it can be executed at least
N_CYCLES after the currently executing insn. Preserve insns
- chain for debugging purposes. */
+ chain for debugging purposes. REASON will be printed in debugging
+ output. */
HAIFA_INLINE static void
-queue_insn (rtx insn, int n_cycles)
+queue_insn (rtx insn, int n_cycles, const char *reason)
{
int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]);
fprintf (sched_dump, ";;\t\tReady-->Q: insn %s: ",
(*current_sched_info->print_insn) (insn, 0));
- fprintf (sched_dump, "queued for %d cycles.\n", n_cycles);
+ fprintf (sched_dump, "queued for %d cycles (%s).\n", n_cycles, reason);
}
QUEUE_INDEX (insn) = next_q;
q_ptr = NEXT_Q (q_ptr);
if (dbg_cnt (sched_insn) == false)
- /* If debug counter is activated do not requeue insn next after
- last_scheduled_insn. */
- skip_insn = next_nonnote_nondebug_insn (last_scheduled_insn);
+ {
+ /* If debug counter is activated do not requeue the first
+ nonscheduled insn. */
+ skip_insn = nonscheduled_insns_begin;
+ do
+ {
+ skip_insn = next_nonnote_nondebug_insn (skip_insn);
+ }
+ while (QUEUE_INDEX (skip_insn) == QUEUE_SCHEDULED);
+ }
else
skip_insn = NULL_RTX;
&& ready->n_ready - ready->n_debug > MAX_SCHED_READY_INSNS
&& !SCHED_GROUP_P (insn)
&& insn != skip_insn)
- {
- if (sched_verbose >= 2)
- fprintf (sched_dump, "requeued because ready full\n");
- queue_insn (insn, 1);
- }
+ queue_insn (insn, 1, "ready full");
else
{
ready_add (ready, insn, false);
static bool
ok_for_early_queue_removal (rtx insn)
{
- int n_cycles;
- rtx prev_insn = last_scheduled_insn;
-
if (targetm.sched.is_costly_dependence)
{
+ rtx prev_insn;
+ int n_cycles;
+ int i = VEC_length (rtx, scheduled_insns);
for (n_cycles = flag_sched_stalled_insns_dep; n_cycles; n_cycles--)
{
- for ( ; prev_insn; prev_insn = PREV_INSN (prev_insn))
+ while (i-- > 0)
{
int cost;
- if (prev_insn == current_sched_info->prev_head)
- {
- prev_insn = NULL;
- break;
- }
+ prev_insn = VEC_index (rtx, scheduled_insns, i);
if (!NOTE_P (prev_insn))
{
break;
}
- if (!prev_insn)
+ if (i == 0)
break;
- prev_insn = PREV_INSN (prev_insn);
}
}
{
if (state_dead_lock_p (state)
|| insn_finishes_cycle_p (insn))
- /* We won't issue any more instructions in the next
- choice_state. */
+ /* We won't issue any more instructions in the next
+ choice_state. */
top->rest = 0;
else
top->rest--;
if (dbg_cnt (sched_insn) == false)
{
- rtx insn;
-
- insn = next_nonnote_insn (last_scheduled_insn);
+ rtx insn = nonscheduled_insns_begin;
+ do
+ {
+ insn = next_nonnote_insn (insn);
+ }
+ while (QUEUE_INDEX (insn) == QUEUE_SCHEDULED);
if (QUEUE_INDEX (insn) == QUEUE_READY)
/* INSN is in the ready_list. */
{
+ nonscheduled_insns_begin = insn;
ready_remove_insn (insn);
*insn_ptr = insn;
return 0;
}
}
+/* This function is called when we have successfully scheduled a
+ block. It uses the schedule stored in the scheduled_insns vector
+ to rearrange the RTL. PREV_HEAD is used as the anchor to which we
+ append the scheduled insns; TAIL is the insn after the scheduled
+ block. TARGET_BB is the argument passed to schedule_block. */
+
+static void
+commit_schedule (rtx prev_head, rtx tail, basic_block *target_bb)
+{
+ unsigned int i;
+ rtx insn;
+
+ last_scheduled_insn = prev_head;
+ for (i = 0;
+ VEC_iterate (rtx, scheduled_insns, i, insn);
+ i++)
+ {
+ if (control_flow_insn_p (last_scheduled_insn)
+ || current_sched_info->advance_target_bb (*target_bb, insn))
+ {
+ *target_bb = current_sched_info->advance_target_bb (*target_bb, 0);
+
+ if (sched_verbose)
+ {
+ rtx x;
+
+ x = next_real_insn (last_scheduled_insn);
+ gcc_assert (x);
+ dump_new_block_header (1, *target_bb, x, tail);
+ }
+
+ last_scheduled_insn = bb_note (*target_bb);
+ }
+
+ if (current_sched_info->begin_move_insn)
+ (*current_sched_info->begin_move_insn) (insn, last_scheduled_insn);
+ move_insn (insn, last_scheduled_insn,
+ current_sched_info->next_tail);
+ if (!DEBUG_INSN_P (insn))
+ reemit_notes (insn);
+ last_scheduled_insn = insn;
+ }
+
+ VEC_truncate (rtx, scheduled_insns, 0);
+}
+
+/* Examine all insns on the ready list and queue those which can't be
+ issued in this cycle. TEMP_STATE is temporary scheduler state we
+ can use as scratch space. If FIRST_CYCLE_INSN_P is true, no insns
+ have been issued for the current cycle, which means it is valid to
+ issue an asm statement. */
+
+static void
+prune_ready_list (state_t temp_state, bool first_cycle_insn_p)
+{
+ int i;
+
+ restart:
+ for (i = 0; i < ready.n_ready; i++)
+ {
+ rtx insn = ready_element (&ready, i);
+ int cost = 0;
+ const char *reason = "resource conflict";
+
+ if (recog_memoized (insn) < 0)
+ {
+ if (!first_cycle_insn_p
+ && (GET_CODE (PATTERN (insn)) == ASM_INPUT
+ || asm_noperands (PATTERN (insn)) >= 0))
+ cost = 1;
+ reason = "asm";
+ }
+ else if (sched_pressure_p)
+ cost = 0;
+ else
+ {
+ memcpy (temp_state, curr_state, dfa_state_size);
+ cost = state_transition (temp_state, insn);
+ if (cost < 0)
+ cost = 0;
+ else if (cost == 0)
+ cost = 1;
+ }
+ if (cost >= 1)
+ {
+ ready_remove (&ready, i);
+ queue_insn (insn, cost, reason);
+ goto restart;
+ }
+ }
+}
+
/* Use forward list scheduling to rearrange insns of block pointed to by
TARGET_BB, possibly bringing insns from subsequent blocks in the same
region. */
targetm.sched.init (sched_dump, sched_verbose, ready.veclen);
/* We start inserting insns after PREV_HEAD. */
- last_scheduled_insn = prev_head;
+ last_scheduled_insn = nonscheduled_insns_begin = prev_head;
gcc_assert ((NOTE_P (last_scheduled_insn)
|| DEBUG_INSN_P (last_scheduled_insn))
/* Delay all insns past it for 1 cycle. If debug counter is
activated make an exception for the insn right after
- last_scheduled_insn. */
+ nonscheduled_insns_begin. */
{
rtx skip_insn;
if (dbg_cnt (sched_insn) == false)
- skip_insn = next_nonnote_insn (last_scheduled_insn);
+ skip_insn = next_nonnote_insn (nonscheduled_insns_begin);
else
skip_insn = NULL_RTX;
insn = ready_remove (&ready, i);
if (insn != skip_insn)
- queue_insn (insn, 1);
+ queue_insn (insn, 1, "list truncated");
}
+ if (skip_insn)
+ ready_add (&ready, skip_insn, true);
}
}
advance = 0;
+ gcc_assert (VEC_length (rtx, scheduled_insns) == 0);
sort_p = TRUE;
/* Loop until all the insns in BB are scheduled. */
while ((*current_sched_info->schedule_more_p) ())
}
while (advance > 0);
+ prune_ready_list (temp_state, true);
+ if (ready.n_ready == 0)
+ continue;
+
if (sort_p)
{
/* Sort the ready list based on priority. */
them out right away. */
if (ready.n_ready && DEBUG_INSN_P (ready_element (&ready, 0)))
{
- if (control_flow_insn_p (last_scheduled_insn))
- {
- *target_bb = current_sched_info->advance_target_bb
- (*target_bb, 0);
-
- if (sched_verbose)
- {
- rtx x;
-
- x = next_real_insn (last_scheduled_insn);
- gcc_assert (x);
- dump_new_block_header (1, *target_bb, x, tail);
- }
-
- last_scheduled_insn = bb_note (*target_bb);
- }
-
while (ready.n_ready && DEBUG_INSN_P (ready_element (&ready, 0)))
{
rtx insn = ready_remove_first (&ready);
gcc_assert (DEBUG_INSN_P (insn));
- (*current_sched_info->begin_schedule_ready) (insn,
- last_scheduled_insn);
- move_insn (insn, last_scheduled_insn,
- current_sched_info->next_tail);
+ (*current_sched_info->begin_schedule_ready) (insn);
+ VEC_safe_push (rtx, heap, scheduled_insns, insn);
last_scheduled_insn = insn;
advance = schedule_insn (insn);
gcc_assert (advance == 0);
}
sort_p = TRUE;
- memcpy (temp_state, curr_state, dfa_state_size);
- if (recog_memoized (insn) < 0)
- {
- asm_p = (GET_CODE (PATTERN (insn)) == ASM_INPUT
- || asm_noperands (PATTERN (insn)) >= 0);
- if (!first_cycle_insn_p && asm_p)
- /* This is asm insn which is tried to be issued on the
- cycle not first. Issue it on the next cycle. */
- cost = 1;
- else
- /* A USE insn, or something else we don't need to
- understand. We can't pass these directly to
- state_transition because it will trigger a
- fatal error for unrecognizable insns. */
- cost = 0;
- }
- else if (sched_pressure_p)
- cost = 0;
- else
- {
- cost = state_transition (temp_state, insn);
- if (cost < 0)
- cost = 0;
- else if (cost == 0)
- cost = 1;
- }
-
- if (cost >= 1)
- {
- queue_insn (insn, cost);
- if (SCHED_GROUP_P (insn))
- {
- advance = cost;
- break;
- }
-
- continue;
- }
if (current_sched_info->can_schedule_ready_p
&& ! (*current_sched_info->can_schedule_ready_p) (insn))
if (TODO_SPEC (insn) & SPECULATIVE)
generate_recovery_code (insn);
- if (control_flow_insn_p (last_scheduled_insn)
- /* This is used to switch basic blocks by request
- from scheduler front-end (actually, sched-ebb.c only).
- This is used to process blocks with single fallthru
- edge. If succeeding block has jump, it [jump] will try
- move at the end of current bb, thus corrupting CFG. */
- || current_sched_info->advance_target_bb (*target_bb, insn))
- {
- *target_bb = current_sched_info->advance_target_bb
- (*target_bb, 0);
-
- if (sched_verbose)
- {
- rtx x;
-
- x = next_real_insn (last_scheduled_insn);
- gcc_assert (x);
- dump_new_block_header (1, *target_bb, x, tail);
- }
-
- last_scheduled_insn = bb_note (*target_bb);
- }
-
- /* Update counters, etc in the scheduler's front end. */
- (*current_sched_info->begin_schedule_ready) (insn,
- last_scheduled_insn);
-
- move_insn (insn, last_scheduled_insn, current_sched_info->next_tail);
-
if (targetm.sched.dispatch (NULL_RTX, IS_DISPATCH_ON))
targetm.sched.dispatch_do (insn, ADD_TO_DISPATCH_WINDOW);
- reemit_notes (insn);
+ /* Update counters, etc in the scheduler's front end. */
+ (*current_sched_info->begin_schedule_ready) (insn);
+ VEC_safe_push (rtx, heap, scheduled_insns, insn);
last_scheduled_insn = insn;
- if (memcmp (curr_state, temp_state, dfa_state_size) != 0)
- {
- cycle_issued_insns++;
- memcpy (curr_state, temp_state, dfa_state_size);
- }
+ if (recog_memoized (insn) >= 0)
+ {
+ memcpy (temp_state, curr_state, dfa_state_size);
+ cost = state_transition (curr_state, insn);
+ if (!sched_pressure_p)
+ gcc_assert (cost < 0);
+ if (memcmp (temp_state, curr_state, dfa_state_size) != 0)
+ cycle_issued_insns++;
+ asm_p = false;
+ }
+ else
+ asm_p = (GET_CODE (PATTERN (insn)) == ASM_INPUT
+ || asm_noperands (PATTERN (insn)) >= 0);
if (targetm.sched.variable_issue)
can_issue_more =
first_cycle_insn_p = false;
+ if (ready.n_ready > 0)
+ prune_ready_list (temp_state, false);
+
/* Sort the ready list based on priority. This must be
redone here, as schedule_insn may have readied additional
insns that will not be sorted correctly. */
if (ready.n_ready && DEBUG_INSN_P (ready_element (&ready, 0))
&& (*current_sched_info->schedule_more_p) ())
{
- if (control_flow_insn_p (last_scheduled_insn))
- {
- *target_bb = current_sched_info->advance_target_bb
- (*target_bb, 0);
-
- if (sched_verbose)
- {
- rtx x;
-
- x = next_real_insn (last_scheduled_insn);
- gcc_assert (x);
- dump_new_block_header (1, *target_bb, x, tail);
- }
-
- last_scheduled_insn = bb_note (*target_bb);
- }
-
- while (ready.n_ready && DEBUG_INSN_P (ready_element (&ready, 0)))
+ while (ready.n_ready && DEBUG_INSN_P (ready_element (&ready, 0)))
{
insn = ready_remove_first (&ready);
gcc_assert (DEBUG_INSN_P (insn));
- (*current_sched_info->begin_schedule_ready)
- (insn, last_scheduled_insn);
- move_insn (insn, last_scheduled_insn,
- current_sched_info->next_tail);
+ (*current_sched_info->begin_schedule_ready) (insn);
+ VEC_safe_push (rtx, heap, scheduled_insns, insn);
advance = schedule_insn (insn);
last_scheduled_insn = insn;
gcc_assert (advance == 0);
}
}
+ commit_schedule (prev_head, tail, target_bb);
if (sched_verbose)
fprintf (sched_dump, ";; total time = %d\n", clock_var);
setup_sched_dump ();
sched_init ();
+ scheduled_insns = VEC_alloc (rtx, heap, 0);
+
if (spec_info != NULL)
{
sched_deps_info->use_deps_list = 1;
c, nr_be_in_control);
}
+ VEC_free (rtx, heap, scheduled_insns);
+
/* Finalize h_i_d, dependency caches, and luids for the whole
function. Target will be finalized in md_global_finish (). */
sched_deps_finish ();
if (delay == QUEUE_READY)
ready_add (readyp, next, false);
else if (delay >= 1)
- queue_insn (next, delay);
+ queue_insn (next, delay, "change queue index");
if (sched_verbose >= 2)
{
{
i = 0;
sched_ready_n_insns = 0;
+ VEC_reserve (rtx, heap, scheduled_insns, new_sched_ready_n_insns);
}
else
i = sched_ready_n_insns + 1;
FOR_EACH_VEC_ELT (haifa_insn_data_def, h_i_d, i, data)
{
- if (data->reg_pressure != NULL)
- free (data->reg_pressure);
+ free (data->reg_pressure);
for (use = data->reg_use_list; use != NULL; use = next)
{
next = use->next_insn_use;
/* Extend dependency caches by one element. */
extend_dependency_caches (1, false);
}
+ if (sched_pressure_p)
+ init_insn_reg_pressure_info (insn);
}
/* Init data for the new basic block BB which comes after AFTER. */