/* Instruction scheduling pass.
Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
- 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
+ 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
Free Software Foundation, Inc.
Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
and currently maintained by, Jim Wilson (wilson@cygnus.com)
#include "coretypes.h"
#include "tm.h"
#include "diagnostic-core.h"
-#include "toplev.h"
#include "rtl.h"
#include "tm_p.h"
#include "hard-reg-set.h"
N=3: rtl at abort point, control-flow, regions info.
N=5: dependences info. */
-static int sched_verbose_param = 0;
int sched_verbose = 0;
/* Debugging file. All printouts are sent to dump, which is always set,
either to stderr, or to the dump listing file (-dRS). */
FILE *sched_dump = 0;
-/* fix_sched_param() is called from toplev.c upon detection
- of the -fsched-verbose=N option. */
-
-void
-fix_sched_param (const char *param, const char *val)
-{
- if (!strcmp (param, "verbose"))
- sched_verbose_param = atoi (val);
- else
- warning (0, "fix_sched_param: unknown param: %s", param);
-}
-
/* This is a placeholder for the scheduler parameters common
to all schedulers. */
struct common_sched_info_def *common_sched_info;
/* The minimal value of the INSN_TICK of an instruction. */
#define MIN_TICK (-max_insn_queue_index)
-/* Issue points are used to distinguish between instructions in max_issue ().
- For now, all instructions are equally good. */
-#define ISSUE_POINTS(INSN) 1
-
/* List of important notes we must keep around. This is a pointer to the
last element in the list. */
rtx note_list;
/* 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);
static void ready_add (struct ready_list *, rtx, bool);
static rtx ready_remove_first (struct ready_list *);
+static rtx ready_remove_first_dispatch (struct ready_list *ready);
static void queue_to_ready (struct ready_list *);
static int early_queue_to_ready (state_t, struct ready_list *);
static rtx ready_remove (struct ready_list *, int);
static void ready_remove_insn (rtx);
-static int choose_ready (struct ready_list *, rtx *);
-
static void fix_inter_tick (rtx, rtx);
static int fix_tick_ready (rtx);
static void change_queue_index (rtx, int);
up. */
bool sched_pressure_p;
-/* Map regno -> its cover class. The map defined only when
+/* Map regno -> its pressure class. The map defined only when
SCHED_PRESSURE_P is true. */
-enum reg_class *sched_regno_cover_class;
+enum reg_class *sched_regno_pressure_class;
-/* The current register pressure. Only elements corresponding cover
+/* The current register pressure. Only elements corresponding pressure
classes are defined. */
static int curr_reg_pressure[N_REG_CLASSES];
static void
mark_regno_birth_or_death (int regno, bool birth_p)
{
- enum reg_class cover_class;
+ enum reg_class pressure_class;
- cover_class = sched_regno_cover_class[regno];
+ pressure_class = sched_regno_pressure_class[regno];
if (regno >= FIRST_PSEUDO_REGISTER)
{
- if (cover_class != NO_REGS)
+ if (pressure_class != NO_REGS)
{
if (birth_p)
{
bitmap_set_bit (curr_reg_live, regno);
- curr_reg_pressure[cover_class]
- += ira_reg_class_nregs[cover_class][PSEUDO_REGNO_MODE (regno)];
+ curr_reg_pressure[pressure_class]
+ += (ira_reg_class_max_nregs
+ [pressure_class][PSEUDO_REGNO_MODE (regno)]);
}
else
{
bitmap_clear_bit (curr_reg_live, regno);
- curr_reg_pressure[cover_class]
- -= ira_reg_class_nregs[cover_class][PSEUDO_REGNO_MODE (regno)];
+ curr_reg_pressure[pressure_class]
+ -= (ira_reg_class_max_nregs
+ [pressure_class][PSEUDO_REGNO_MODE (regno)]);
}
}
}
- else if (cover_class != NO_REGS
+ else if (pressure_class != NO_REGS
&& ! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
{
if (birth_p)
{
bitmap_set_bit (curr_reg_live, regno);
- curr_reg_pressure[cover_class]++;
+ curr_reg_pressure[pressure_class]++;
}
else
{
bitmap_clear_bit (curr_reg_live, regno);
- curr_reg_pressure[cover_class]--;
+ curr_reg_pressure[pressure_class]--;
}
}
}
unsigned int j;
bitmap_iterator bi;
- for (i = 0; i < ira_reg_class_cover_size; i++)
- curr_reg_pressure[ira_reg_class_cover[i]] = 0;
+ for (i = 0; i < ira_pressure_classes_num; i++)
+ curr_reg_pressure[ira_pressure_classes[i]] = 0;
bitmap_clear (curr_reg_live);
EXECUTE_IF_SET_IN_BITMAP (live, 0, j, bi)
if (current_nr_blocks == 1 || bitmap_bit_p (region_ref_regs, j))
if (REG_P (x))
{
regno = REGNO (x);
- if (regno >= FIRST_PSEUDO_REGISTER)
- bitmap_set_bit (region_ref_regs, REGNO (x));
+ if (HARD_REGISTER_NUM_P (regno))
+ bitmap_set_range (region_ref_regs, regno,
+ hard_regno_nregs[regno][GET_MODE (x)]);
else
- for (i = hard_regno_nregs[regno][GET_MODE (x)] - 1; i >= 0; i--)
- bitmap_set_bit (region_ref_regs, regno + i);
+ bitmap_set_bit (region_ref_regs, REGNO (x));
return;
}
fmt = GET_RTX_FORMAT (code);
static void
initiate_bb_reg_pressure_info (basic_block bb)
{
- unsigned int i;
+ unsigned int i ATTRIBUTE_UNUSED;
rtx insn;
if (current_nr_blocks > 1)
{
int i;
- for (i = 0; i < ira_reg_class_cover_size; i++)
- saved_reg_pressure[ira_reg_class_cover[i]]
- = curr_reg_pressure[ira_reg_class_cover[i]];
+ for (i = 0; i < ira_pressure_classes_num; i++)
+ saved_reg_pressure[ira_pressure_classes[i]]
+ = curr_reg_pressure[ira_pressure_classes[i]];
bitmap_copy (saved_reg_live, curr_reg_live);
}
{
int i;
- for (i = 0; i < ira_reg_class_cover_size; i++)
- curr_reg_pressure[ira_reg_class_cover[i]]
- = saved_reg_pressure[ira_reg_class_cover[i]];
+ for (i = 0; i < ira_pressure_classes_num; i++)
+ curr_reg_pressure[ira_pressure_classes[i]]
+ = saved_reg_pressure[ira_pressure_classes[i]];
bitmap_copy (curr_reg_live, saved_reg_live);
}
}
/* Print info about the current register pressure and its excess for
- each cover class. */
+ each pressure class. */
static void
print_curr_reg_pressure (void)
{
enum reg_class cl;
fprintf (sched_dump, ";;\t");
- for (i = 0; i < ira_reg_class_cover_size; i++)
+ for (i = 0; i < ira_pressure_classes_num; i++)
{
- cl = ira_reg_class_cover[i];
+ cl = ira_pressure_classes[i];
gcc_assert (curr_reg_pressure[cl] >= 0);
fprintf (sched_dump, " %s:%d(%d)", reg_class_names[cl],
curr_reg_pressure[cl],
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;
gcc_checking_assert (!DEBUG_INSN_P (insn));
excess_cost_change = 0;
- for (i = 0; i < ira_reg_class_cover_size; i++)
- death[ira_reg_class_cover[i]] = 0;
+ for (i = 0; i < ira_pressure_classes_num; i++)
+ death[ira_pressure_classes[i]] = 0;
for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
if (dying_use_p (use))
{
- cl = sched_regno_cover_class[use->regno];
+ cl = sched_regno_pressure_class[use->regno];
if (use->regno < FIRST_PSEUDO_REGISTER)
death[cl]++;
else
- death[cl] += ira_reg_class_nregs[cl][PSEUDO_REGNO_MODE (use->regno)];
+ death[cl]
+ += ira_reg_class_max_nregs[cl][PSEUDO_REGNO_MODE (use->regno)];
}
pressure_info = INSN_REG_PRESSURE (insn);
max_reg_pressure = INSN_MAX_REG_PRESSURE (insn);
gcc_assert (pressure_info != NULL && max_reg_pressure != NULL);
- for (i = 0; i < ira_reg_class_cover_size; i++)
+ for (i = 0; i < ira_pressure_classes_num; i++)
{
- cl = ira_reg_class_cover[i];
+ cl = ira_pressure_classes[i];
gcc_assert (curr_reg_pressure[cl] >= 0);
change = (int) pressure_info[i].set_increase - death[cl];
before = MAX (0, max_reg_pressure[i] - ira_available_class_regs[cl]);
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;
static int max_reg_pressure[N_REG_CLASSES];
save_reg_pressure ();
- for (i = 0; i < ira_reg_class_cover_size; i++)
- max_reg_pressure[ira_reg_class_cover[i]]
- = curr_reg_pressure[ira_reg_class_cover[i]];
+ for (i = 0; i < ira_pressure_classes_num; i++)
+ max_reg_pressure[ira_pressure_classes[i]]
+ = curr_reg_pressure[ira_pressure_classes[i]];
for (insn = NEXT_INSN (after);
insn != NULL_RTX && ! BARRIER_P (insn)
&& BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (after);
if (NONDEBUG_INSN_P (insn))
{
eq_p = true;
- for (i = 0; i < ira_reg_class_cover_size; i++)
+ for (i = 0; i < ira_pressure_classes_num; i++)
{
- p = max_reg_pressure[ira_reg_class_cover[i]];
+ p = max_reg_pressure[ira_pressure_classes[i]];
if (INSN_MAX_REG_PRESSURE (insn)[i] != p)
{
eq_p = false;
INSN_MAX_REG_PRESSURE (insn)[i]
- = max_reg_pressure[ira_reg_class_cover[i]];
+ = max_reg_pressure[ira_pressure_classes[i]];
}
}
if (update_p && eq_p)
break;
update_register_pressure (insn);
- for (i = 0; i < ira_reg_class_cover_size; i++)
- if (max_reg_pressure[ira_reg_class_cover[i]]
- < curr_reg_pressure[ira_reg_class_cover[i]])
- max_reg_pressure[ira_reg_class_cover[i]]
- = curr_reg_pressure[ira_reg_class_cover[i]];
+ for (i = 0; i < ira_pressure_classes_num; i++)
+ if (max_reg_pressure[ira_pressure_classes[i]]
+ < curr_reg_pressure[ira_pressure_classes[i]])
+ max_reg_pressure[ira_pressure_classes[i]]
+ = curr_reg_pressure[ira_pressure_classes[i]];
}
restore_reg_pressure ();
}
int i;
int before[N_REG_CLASSES];
- for (i = 0; i < ira_reg_class_cover_size; i++)
- before[i] = curr_reg_pressure[ira_reg_class_cover[i]];
+ for (i = 0; i < ira_pressure_classes_num; i++)
+ before[i] = curr_reg_pressure[ira_pressure_classes[i]];
update_register_pressure (insn);
- for (i = 0; i < ira_reg_class_cover_size; i++)
- if (curr_reg_pressure[ira_reg_class_cover[i]] != before[i])
+ for (i = 0; i < ira_pressure_classes_num; i++)
+ if (curr_reg_pressure[ira_pressure_classes[i]] != before[i])
break;
- if (i < ira_reg_class_cover_size)
+ if (i < ira_pressure_classes_num)
setup_insn_max_reg_pressure (insn, true);
}
if (pressure_info != NULL)
{
fputc (':', sched_dump);
- for (i = 0; i < ira_reg_class_cover_size; i++)
+ for (i = 0; i < ira_pressure_classes_num; i++)
fprintf (sched_dump, "%s%+d(%d)",
- reg_class_names[ira_reg_class_cover[i]],
+ reg_class_names[ira_pressure_classes[i]],
pressure_info[i].set_increase, pressure_info[i].change);
}
fputc ('\n', sched_dump);
beg_head = NEXT_INSN (beg_head);
while (beg_head != beg_tail)
- if (NOTE_P (beg_head) || BOUNDARY_DEBUG_INSN_P (beg_head))
+ if (NOTE_P (beg_head))
beg_head = NEXT_INSN (beg_head);
+ else if (DEBUG_INSN_P (beg_head))
+ {
+ rtx note, next;
+
+ for (note = NEXT_INSN (beg_head);
+ note != beg_tail;
+ note = next)
+ {
+ next = NEXT_INSN (note);
+ if (NOTE_P (note))
+ {
+ if (sched_verbose >= 9)
+ fprintf (sched_dump, "reorder %i\n", INSN_UID (note));
+
+ reorder_insns_nobb (note, note, PREV_INSN (beg_head));
+
+ if (BLOCK_FOR_INSN (note) != beg)
+ df_insn_change_bb (note, beg);
+ }
+ else if (!DEBUG_INSN_P (note))
+ break;
+ }
+
+ break;
+ }
else
break;
end_head = NEXT_INSN (end_head);
while (end_head != end_tail)
- if (NOTE_P (end_tail) || BOUNDARY_DEBUG_INSN_P (end_tail))
+ if (NOTE_P (end_tail))
end_tail = PREV_INSN (end_tail);
+ else if (DEBUG_INSN_P (end_tail))
+ {
+ rtx note, prev;
+
+ for (note = PREV_INSN (end_tail);
+ note != end_head;
+ note = prev)
+ {
+ prev = PREV_INSN (note);
+ if (NOTE_P (note))
+ {
+ if (sched_verbose >= 9)
+ fprintf (sched_dump, "reorder %i\n", INSN_UID (note));
+
+ reorder_insns_nobb (note, note, end_tail);
+
+ if (end_tail == BB_END (end))
+ BB_END (end) = note;
+
+ if (BLOCK_FOR_INSN (note) != end)
+ df_insn_change_bb (note, end);
+ }
+ else if (!DEBUG_INSN_P (note))
+ break;
+ }
+
+ break;
+ }
else
break;
{
while (head != NEXT_INSN (tail))
{
- if (!NOTE_P (head) && !LABEL_P (head)
- && !BOUNDARY_DEBUG_INSN_P (head))
+ if (!NOTE_P (head) && !LABEL_P (head))
return 0;
head = NEXT_INSN (head);
}
if (dbg_cnt (sched_insn) == false)
{
- /* If debug counter is activated do not requeue insn next after
- last_scheduled_insn. */
- skip_insn = next_nonnote_insn (last_scheduled_insn);
- while (skip_insn && DEBUG_INSN_P (skip_insn))
- skip_insn = next_nonnote_insn (skip_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);
}
}
return false;
}
+/* Define type for target data used in multipass scheduling. */
+#ifndef TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T
+# define TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T int
+#endif
+typedef TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T first_cycle_multipass_data_t;
+
/* The following structure describe an entry of the stack of choices. */
struct choice_entry
{
int n;
/* State after issuing the insn. */
state_t state;
+ /* Target-specific data. */
+ first_cycle_multipass_data_t target_data;
};
/* The following array is used to implement a stack of choices used in
insns is insns with the best rank (the first insn in READY). To
make this function tries different samples of ready insns. READY
is current queue `ready'. Global array READY_TRY reflects what
- insns are already issued in this try. MAX_POINTS is the sum of points
- of all instructions in READY. The function stops immediately,
+ insns are already issued in this try. The function stops immediately,
if it reached the such a solution, that all instruction can be issued.
INDEX will contain index of the best insn in READY. The following
function is used only for first cycle multipass scheduling.
CLOBBERs, etc must be filtered elsewhere. */
int
max_issue (struct ready_list *ready, int privileged_n, state_t state,
- int *index)
+ bool first_cycle_insn_p, int *index)
{
- int n, i, all, n_ready, best, delay, tries_num, max_points;
+ int n, i, all, n_ready, best, delay, tries_num;
int more_issue;
struct choice_entry *top;
rtx insn;
}
/* Init max_points. */
- max_points = 0;
more_issue = issue_rate - cycle_issued_insns;
-
- /* ??? We used to assert here that we never issue more insns than issue_rate.
- However, some targets (e.g. MIPS/SB1) claim lower issue rate than can be
- achieved to get better performance. Until these targets are fixed to use
- scheduler hooks to manipulate insns priority instead, the assert should
- be disabled.
-
- gcc_assert (more_issue >= 0); */
-
- for (i = 0; i < n_ready; i++)
- if (!ready_try [i])
- {
- if (more_issue-- > 0)
- max_points += ISSUE_POINTS (ready_element (ready, i));
- else
- break;
- }
+ gcc_assert (more_issue >= 0);
/* The number of the issued insns in the best solution. */
best = 0;
memcpy (top->state, state, dfa_state_size);
top->rest = dfa_lookahead;
top->n = 0;
+ if (targetm.sched.first_cycle_multipass_begin)
+ targetm.sched.first_cycle_multipass_begin (&top->target_data,
+ ready_try, n_ready,
+ first_cycle_insn_p);
/* Count the number of the insns to search among. */
for (all = i = 0; i < n_ready; i++)
if (/* If we've reached a dead end or searched enough of what we have
been asked... */
top->rest == 0
- /* Or have nothing else to try. */
- || i >= n_ready)
+ /* or have nothing else to try... */
+ || i >= n_ready
+ /* or should not issue more. */
+ || top->n >= more_issue)
{
/* ??? (... || i == n_ready). */
gcc_assert (i <= n_ready);
+ /* We should not issue more than issue_rate instructions. */
+ gcc_assert (top->n <= more_issue);
+
if (top == choice_stack)
break;
/* This is the index of the insn issued first in this
solution. */
*index = choice_stack [1].index;
- if (top->n == max_points || best == all)
+ if (top->n == more_issue || best == all)
break;
}
}
/* Backtrack. */
ready_try [i] = 0;
+
+ if (targetm.sched.first_cycle_multipass_backtrack)
+ targetm.sched.first_cycle_multipass_backtrack (&top->target_data,
+ ready_try, n_ready);
+
top--;
memcpy (state, top->state, dfa_state_size);
}
{
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--;
n = top->n;
if (memcmp (top->state, state, dfa_state_size) != 0)
- n += ISSUE_POINTS (insn);
+ n++;
/* Advance to the next choice_entry. */
top++;
top->index = i;
top->n = n;
memcpy (top->state, state, dfa_state_size);
-
ready_try [i] = 1;
+
+ if (targetm.sched.first_cycle_multipass_issue)
+ targetm.sched.first_cycle_multipass_issue (&top->target_data,
+ ready_try, n_ready,
+ insn,
+ &((top - 1)
+ ->target_data));
+
i = -1;
}
}
i++;
}
+ if (targetm.sched.first_cycle_multipass_end)
+ targetm.sched.first_cycle_multipass_end (best != 0
+ ? &choice_stack[1].target_data
+ : NULL);
+
/* Restore the original state of the DFA. */
memcpy (state, choice_stack->state, dfa_state_size);
0 if INSN_PTR is set to point to the desirable insn,
1 if choose_ready () should be restarted without advancing the cycle. */
static int
-choose_ready (struct ready_list *ready, rtx *insn_ptr)
+choose_ready (struct ready_list *ready, bool first_cycle_insn_p,
+ rtx *insn_ptr)
{
int lookahead;
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;
if (lookahead <= 0 || SCHED_GROUP_P (ready_element (ready, 0))
|| DEBUG_INSN_P (ready_element (ready, 0)))
{
- *insn_ptr = ready_remove_first (ready);
+ if (targetm.sched.dispatch (NULL_RTX, IS_DISPATCH_ON))
+ *insn_ptr = ready_remove_first_dispatch (ready);
+ else
+ *insn_ptr = ready_remove_first (ready);
+
return 0;
}
else
{
insn = ready_element (ready, i);
-#ifdef ENABLE_CHECKING
/* If this insn is recognizable we should have already
recognized it earlier.
??? Not very clear where this is supposed to be done.
See dep_cost_1. */
- gcc_assert (INSN_CODE (insn) >= 0
- || recog_memoized (insn) < 0);
-#endif
+ gcc_checking_assert (INSN_CODE (insn) >= 0
+ || recog_memoized (insn) < 0);
ready_try [i]
= (/* INSN_CODE check can be omitted here as it is also done later
(insn)));
}
- if (max_issue (ready, 1, curr_state, &index) == 0)
+ if (max_issue (ready, 1, curr_state, first_cycle_insn_p, &index) == 0)
{
*insn_ptr = ready_remove_first (ready);
if (sched_verbose >= 4)
}
}
+/* 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. */
void
schedule_block (basic_block *target_bb)
{
- int i, first_cycle_insn_p;
+ int i;
+ bool first_cycle_insn_p;
int can_issue_more;
state_t temp_state = NULL; /* It is used for multipass scheduling. */
int sort_p, advance, start_clock_var;
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)
- || BOUNDARY_DEBUG_INSN_P (last_scheduled_insn))
+ || DEBUG_INSN_P (last_scheduled_insn))
&& BLOCK_FOR_INSN (last_scheduled_insn) == *target_bb);
/* Initialize INSN_QUEUE. Q_SIZE is the total number of insns in the
/* 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);
else
can_issue_more = issue_rate;
- first_cycle_insn_p = 1;
+ first_cycle_insn_p = true;
cycle_issued_insns = 0;
for (;;)
{
int res;
insn = NULL_RTX;
- res = choose_ready (&ready, &insn);
+ res = choose_ready (&ready, first_cycle_insn_p, &insn);
if (res < 0)
/* Finish cycle. */
}
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);
- }
+ if (targetm.sched.dispatch (NULL_RTX, IS_DISPATCH_ON))
+ targetm.sched.dispatch_do (insn, ADD_TO_DISPATCH_WINDOW);
/* 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);
- reemit_notes (insn);
+ (*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 =
if (advance != 0)
break;
- first_cycle_insn_p = 0;
+ 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
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);
current_sched_info->sched_max_insns_priority;
rtx prev_head;
- if (head == tail && (! INSN_P (head) || BOUNDARY_DEBUG_INSN_P (head)))
+ if (head == tail && ! INSN_P (head))
gcc_unreachable ();
n_insn = 0;
flag_schedule_speculative_load = 0;
#endif
+ if (targetm.sched.dispatch (NULL_RTX, IS_DISPATCH_ON))
+ targetm.sched.dispatch_do (NULL_RTX, DISPATCH_INIT);
+
sched_pressure_p = (flag_sched_pressure && ! reload_completed
&& common_sched_info->sched_pass_id == SCHED_RGN_PASS);
+
if (sched_pressure_p)
ira_setup_eliminable_regset ();
int i, max_regno = max_reg_num ();
ira_set_pseudo_classes (sched_verbose ? sched_dump : NULL);
- sched_regno_cover_class
+ sched_regno_pressure_class
= (enum reg_class *) xmalloc (max_regno * sizeof (enum reg_class));
for (i = 0; i < max_regno; i++)
- sched_regno_cover_class[i]
+ sched_regno_pressure_class[i]
= (i < FIRST_PSEUDO_REGISTER
- ? ira_class_translate[REGNO_REG_CLASS (i)]
- : reg_cover_class (i));
+ ? ira_pressure_class_translate[REGNO_REG_CLASS (i)]
+ : ira_pressure_class_translate[reg_allocno_class (i)]);
curr_reg_live = BITMAP_ALLOC (NULL);
saved_reg_live = BITMAP_ALLOC (NULL);
region_ref_regs = BITMAP_ALLOC (NULL);
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 ();
haifa_finish_h_i_d ();
if (sched_pressure_p)
{
- free (sched_regno_cover_class);
+ free (sched_regno_pressure_class);
BITMAP_FREE (region_ref_regs);
BITMAP_FREE (saved_reg_live);
BITMAP_FREE (curr_reg_live);
gcc_assert (tick >= MIN_TICK);
/* Fix INSN_TICK of instruction from just scheduled block. */
- if (!bitmap_bit_p (&processed, INSN_LUID (head)))
+ if (bitmap_set_bit (&processed, INSN_LUID (head)))
{
- bitmap_set_bit (&processed, INSN_LUID (head));
tick -= next_clock;
if (tick < MIN_TICK)
/* If NEXT has its INSN_TICK calculated, fix it.
If not - it will be properly calculated from
scratch later in fix_tick_ready. */
- && !bitmap_bit_p (&processed, INSN_LUID (next)))
+ && bitmap_set_bit (&processed, INSN_LUID (next)))
{
- bitmap_set_bit (&processed, INSN_LUID (next));
tick -= next_clock;
if (tick < MIN_TICK)
{
int tick, delay;
- if (!sd_lists_empty_p (next, SD_LIST_RES_BACK))
+ if (!DEBUG_INSN_P (next) && !sd_lists_empty_p (next, SD_LIST_RES_BACK))
{
int full_p;
sd_iterator_def sd_it;
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;
new_sched_ready_n_insns + 1);
for (; i <= new_sched_ready_n_insns; i++)
- choice_stack[i].state = xmalloc (dfa_state_size);
+ {
+ choice_stack[i].state = xmalloc (dfa_state_size);
+
+ if (targetm.sched.first_cycle_multipass_init)
+ targetm.sched.first_cycle_multipass_init (&(choice_stack[i]
+ .target_data));
+ }
sched_ready_n_insns = new_sched_ready_n_insns;
}
ready_try = NULL;
for (i = 0; i <= sched_ready_n_insns; i++)
- free (choice_stack [i].state);
+ {
+ if (targetm.sched.first_cycle_multipass_fini)
+ targetm.sched.first_cycle_multipass_fini (&(choice_stack[i]
+ .target_data));
+
+ free (choice_stack [i].state);
+ }
free (choice_stack);
choice_stack = NULL;
/* Helper function.
Find fallthru edge from PRED. */
edge
-find_fallthru_edge (basic_block pred)
+find_fallthru_edge_from (basic_block pred)
{
edge e;
- edge_iterator ei;
basic_block succ;
succ = pred->next_bb;
if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds))
{
- FOR_EACH_EDGE (e, ei, pred->succs)
- if (e->flags & EDGE_FALLTHRU)
- {
- gcc_assert (e->dest == succ);
- return e;
- }
+ e = find_fallthru_edge (pred->succs);
+
+ if (e)
+ {
+ gcc_assert (e->dest == succ);
+ return e;
+ }
}
else
{
- FOR_EACH_EDGE (e, ei, succ->preds)
- if (e->flags & EDGE_FALLTHRU)
- {
- gcc_assert (e->src == pred);
- return e;
- }
+ e = find_fallthru_edge (succ->preds);
+
+ if (e)
+ {
+ gcc_assert (e->src == pred);
+ return e;
+ }
}
return NULL;
edge e;
last = EXIT_BLOCK_PTR->prev_bb;
- e = find_fallthru_edge (last);
+ e = find_fallthru_edge_from (last);
if (e)
{
edge_flags = 0;
make_single_succ_edge (rec, second_bb, edge_flags);
+ if (dom_info_available_p (CDI_DOMINATORS))
+ set_immediate_dominator (CDI_DOMINATORS, rec, first_bb);
}
/* This function creates recovery code for INSN. If MUTATE_P is nonzero,
{
sd_delete_dep (sd_it);
- if (!bitmap_bit_p (&in_ready, INSN_LUID (consumer)))
- {
- ready_list = alloc_INSN_LIST (consumer, ready_list);
- bitmap_set_bit (&in_ready, INSN_LUID (consumer));
- }
+ if (bitmap_set_bit (&in_ready, INSN_LUID (consumer)))
+ ready_list = alloc_INSN_LIST (consumer, ready_list);
}
else
{
int i;
rtx insn;
- for (i = 0; VEC_iterate (rtx, roots, i, insn); i++)
+ FOR_EACH_VEC_ELT (rtx, roots, i, insn)
priority (insn);
}
unsigned i;
basic_block x;
- for (i = 0; VEC_iterate (basic_block, bbs, i, x); i++)
+ FOR_EACH_VEC_ELT (basic_block, bbs, i, x)
init_bb (x);
}
unsigned i;
basic_block x;
- for (i = 0; VEC_iterate (basic_block, bbs, i, x); i++)
+ FOR_EACH_VEC_ELT (basic_block, bbs, i, x)
init_insns_in_bb (x);
}
unsigned i;
rtx x;
- for (i = 0; VEC_iterate (rtx, insns, i, x); i++)
+ FOR_EACH_VEC_ELT (rtx, insns, i, x)
init_insn (x);
}
haifa_insn_data_t data;
struct reg_use_data *use, *next;
- for (i = 0; VEC_iterate (haifa_insn_data_def, h_i_d, i, data); i++)
+ 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. */
return insn;
}
+/* This function returns a candidate satisfying dispatch constraints from
+ the ready list. */
+
+static rtx
+ready_remove_first_dispatch (struct ready_list *ready)
+{
+ int i;
+ rtx insn = ready_element (ready, 0);
+
+ if (ready->n_ready == 1
+ || INSN_CODE (insn) < 0
+ || !INSN_P (insn)
+ || !active_insn_p (insn)
+ || targetm.sched.dispatch (insn, FITS_DISPATCH_WINDOW))
+ return ready_remove_first (ready);
+
+ for (i = 1; i < ready->n_ready; i++)
+ {
+ insn = ready_element (ready, i);
+
+ if (INSN_CODE (insn) < 0
+ || !INSN_P (insn)
+ || !active_insn_p (insn))
+ continue;
+
+ if (targetm.sched.dispatch (insn, FITS_DISPATCH_WINDOW))
+ {
+ /* Return ith element of ready. */
+ insn = ready_remove (ready, i);
+ return insn;
+ }
+ }
+
+ if (targetm.sched.dispatch (NULL_RTX, DISPATCH_VIOLATION))
+ return ready_remove_first (ready);
+
+ for (i = 1; i < ready->n_ready; i++)
+ {
+ insn = ready_element (ready, i);
+
+ if (INSN_CODE (insn) < 0
+ || !INSN_P (insn)
+ || !active_insn_p (insn))
+ continue;
+
+ /* Return i-th element of ready. */
+ if (targetm.sched.dispatch (insn, IS_CMP))
+ return ready_remove (ready, i);
+ }
+
+ return ready_remove_first (ready);
+}
+
+/* Get number of ready insn in the ready list. */
+
+int
+number_in_ready (void)
+{
+ return ready.n_ready;
+}
+
+/* Get number of ready's in the ready list. */
+
+rtx
+get_ready_element (int i)
+{
+ return ready_element (&ready, i);
+}
+
#endif /* INSN_SCHEDULING */
OSDN Git Service
