/* Instruction scheduling pass.
Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
- 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
+ 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
Free Software Foundation, Inc.
Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
and currently maintained by, Jim Wilson (wilson@cygnus.com)
#include "vecprim.h"
#include "dbgcnt.h"
#include "cfgloop.h"
+#include "ira.h"
#ifdef INSN_SCHEDULING
char *ready_try = NULL;
/* The ready list. */
-struct ready_list ready = {NULL, 0, 0, 0};
+struct ready_list ready = {NULL, 0, 0, 0, 0};
/* The pointer to the ready list (to be removed). */
static struct ready_list *readyp = &ready;
static void swap_sort (rtx *, int);
static void queue_insn (rtx, int);
static int schedule_insn (rtx);
-static int find_set_reg_weight (const_rtx);
-static void find_insn_reg_weight (const_rtx);
static void adjust_priority (rtx);
static void advance_one_cycle (void);
static void extend_h_i_d (void);
}
#else
+/* Do register pressure sensitive insn scheduling if the flag is set
+ up. */
+bool sched_pressure_p;
+
+/* Map regno -> its cover class. The map defined only when
+ SCHED_PRESSURE_P is true. */
+enum reg_class *sched_regno_cover_class;
+
+/* The current register pressure. Only elements corresponding cover
+ classes are defined. */
+static int curr_reg_pressure[N_REG_CLASSES];
+
+/* Saved value of the previous array. */
+static int saved_reg_pressure[N_REG_CLASSES];
+
+/* Register living at given scheduling point. */
+static bitmap curr_reg_live;
+
+/* Saved value of the previous array. */
+static bitmap saved_reg_live;
+
+/* Registers mentioned in the current region. */
+static bitmap region_ref_regs;
+
+/* Initiate register pressure relative info for scheduling the current
+ region. Currently it is only clearing register mentioned in the
+ current region. */
+void
+sched_init_region_reg_pressure_info (void)
+{
+ bitmap_clear (region_ref_regs);
+}
+
+/* Update current register pressure related info after birth (if
+ BIRTH_P) or death of register REGNO. */
+static void
+mark_regno_birth_or_death (int regno, bool birth_p)
+{
+ enum reg_class cover_class;
+
+ cover_class = sched_regno_cover_class[regno];
+ if (regno >= FIRST_PSEUDO_REGISTER)
+ {
+ if (cover_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)];
+ }
+ else
+ {
+ bitmap_clear_bit (curr_reg_live, regno);
+ curr_reg_pressure[cover_class]
+ -= ira_reg_class_nregs[cover_class][PSEUDO_REGNO_MODE (regno)];
+ }
+ }
+ }
+ else if (cover_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]++;
+ }
+ else
+ {
+ bitmap_clear_bit (curr_reg_live, regno);
+ curr_reg_pressure[cover_class]--;
+ }
+ }
+}
+
+/* Initiate current register pressure related info from living
+ registers given by LIVE. */
+static void
+initiate_reg_pressure_info (bitmap live)
+{
+ int i;
+ 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;
+ 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))
+ mark_regno_birth_or_death (j, true);
+}
+
+/* Mark registers in X as mentioned in the current region. */
+static void
+setup_ref_regs (rtx x)
+{
+ int i, j, regno;
+ const RTX_CODE code = GET_CODE (x);
+ const char *fmt;
+
+ if (REG_P (x))
+ {
+ regno = REGNO (x);
+ if (regno >= FIRST_PSEUDO_REGISTER)
+ bitmap_set_bit (region_ref_regs, REGNO (x));
+ else
+ for (i = hard_regno_nregs[regno][GET_MODE (x)] - 1; i >= 0; i--)
+ bitmap_set_bit (region_ref_regs, regno + i);
+ return;
+ }
+ fmt = GET_RTX_FORMAT (code);
+ for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+ if (fmt[i] == 'e')
+ setup_ref_regs (XEXP (x, i));
+ else if (fmt[i] == 'E')
+ {
+ for (j = 0; j < XVECLEN (x, i); j++)
+ setup_ref_regs (XVECEXP (x, i, j));
+ }
+}
+
+/* Initiate current register pressure related info at the start of
+ basic block BB. */
+static void
+initiate_bb_reg_pressure_info (basic_block bb)
+{
+ unsigned int i;
+ rtx insn;
+
+ if (current_nr_blocks > 1)
+ FOR_BB_INSNS (bb, insn)
+ if (INSN_P (insn))
+ setup_ref_regs (PATTERN (insn));
+ initiate_reg_pressure_info (df_get_live_in (bb));
+#ifdef EH_RETURN_DATA_REGNO
+ if (bb_has_eh_pred (bb))
+ for (i = 0; ; ++i)
+ {
+ unsigned int regno = EH_RETURN_DATA_REGNO (i);
+
+ if (regno == INVALID_REGNUM)
+ break;
+ if (! bitmap_bit_p (df_get_live_in (bb), regno))
+ mark_regno_birth_or_death (regno, true);
+ }
+#endif
+}
+
+/* Save current register pressure related info. */
+static void
+save_reg_pressure (void)
+{
+ 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]];
+ bitmap_copy (saved_reg_live, curr_reg_live);
+}
+
+/* Restore saved register pressure related info. */
+static void
+restore_reg_pressure (void)
+{
+ 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]];
+ bitmap_copy (curr_reg_live, saved_reg_live);
+}
+
+/* Return TRUE if the register is dying after its USE. */
+static bool
+dying_use_p (struct reg_use_data *use)
+{
+ struct reg_use_data *next;
+
+ for (next = use->next_regno_use; next != use; next = next->next_regno_use)
+ if (QUEUE_INDEX (next->insn) != QUEUE_SCHEDULED)
+ return false;
+ return true;
+}
+
+/* Print info about the current register pressure and its excess for
+ each cover class. */
+static void
+print_curr_reg_pressure (void)
+{
+ int i;
+ enum reg_class cl;
+
+ fprintf (sched_dump, ";;\t");
+ for (i = 0; i < ira_reg_class_cover_size; i++)
+ {
+ cl = ira_reg_class_cover[i];
+ gcc_assert (curr_reg_pressure[cl] >= 0);
+ fprintf (sched_dump, " %s:%d(%d)", reg_class_names[cl],
+ curr_reg_pressure[cl],
+ curr_reg_pressure[cl] - ira_available_class_regs[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. */
/* Compute cost of executing INSN.
This is the number of cycles between instruction issue and
instruction results. */
-HAIFA_INLINE int
+int
insn_cost (rtx insn)
{
int cost;
/* Compute cost of dependence LINK.
This is the number of cycles between instruction issue and
- instruction results. */
+ instruction results.
+ ??? We also use this function to call recog_memoized on all insns. */
int
dep_cost_1 (dep_t link, dw_t dw)
{
+ rtx insn = DEP_PRO (link);
rtx used = DEP_CON (link);
int 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. */
+ values to overlap the return and call. We don't care about the
+ the dependence cost when only decreasing register pressure. */
if (recog_memoized (used) < 0)
- cost = 0;
+ {
+ cost = 0;
+ recog_memoized (insn);
+ }
else
{
- rtx insn = DEP_PRO (link);
enum reg_note dep_type = DEP_TYPE (link);
cost = insn_cost (insn);
if (targetm.sched.adjust_cost_2)
- {
- cost = targetm.sched.adjust_cost_2 (used, (int) dep_type, insn, cost,
- dw);
- }
+ cost = targetm.sched.adjust_cost_2 (used, (int) dep_type, insn, cost,
+ dw);
else if (targetm.sched.adjust_cost != NULL)
{
/* This variable is used for backward compatibility with the
static bool
contributes_to_priority_p (dep_t dep)
{
+ if (DEBUG_INSN_P (DEP_CON (dep))
+ || DEBUG_INSN_P (DEP_PRO (dep)))
+ return false;
+
/* Critical path is meaningful in block boundaries only. */
if (!current_sched_info->contributes_to_priority (DEP_CON (dep),
DEP_PRO (dep)))
return true;
}
+/* Compute the number of nondebug forward deps of an insn. */
+
+static int
+dep_list_size (rtx insn)
+{
+ sd_iterator_def sd_it;
+ dep_t dep;
+ int dbgcount = 0, nodbgcount = 0;
+
+ if (!MAY_HAVE_DEBUG_INSNS)
+ return sd_lists_size (insn, SD_LIST_FORW);
+
+ FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
+ {
+ if (DEBUG_INSN_P (DEP_CON (dep)))
+ dbgcount++;
+ else
+ nodbgcount++;
+ }
+
+ gcc_assert (dbgcount + nodbgcount == sd_lists_size (insn, SD_LIST_FORW));
+
+ return nodbgcount;
+}
+
/* Compute the priority number for INSN. */
static int
priority (rtx insn)
{
int this_priority = -1;
- if (sd_lists_empty_p (insn, SD_LIST_FORW))
+ if (dep_list_size (insn) == 0)
/* ??? We should set INSN_PRIORITY to insn_cost when and insn has
some forward deps but all of them are ignored by
contributes_to_priority hook. At the moment we set priority of
qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
while (0)
+/* Setup info about the current register pressure impact of scheduling
+ INSN at the current scheduling point. */
+static void
+setup_insn_reg_pressure_info (rtx insn)
+{
+ int i, change, before, after, hard_regno;
+ int excess_cost_change;
+ enum machine_mode mode;
+ enum reg_class cl;
+ struct reg_pressure_data *pressure_info;
+ int *max_reg_pressure;
+ struct reg_use_data *use;
+ static int death[N_REG_CLASSES];
+
+ excess_cost_change = 0;
+ for (i = 0; i < ira_reg_class_cover_size; i++)
+ death[ira_reg_class_cover[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];
+ if (use->regno < FIRST_PSEUDO_REGISTER)
+ death[cl]++;
+ else
+ death[cl] += ira_reg_class_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++)
+ {
+ cl = ira_reg_class_cover[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]);
+ after = MAX (0, max_reg_pressure[i] + change
+ - ira_available_class_regs[cl]);
+ hard_regno = ira_class_hard_regs[cl][0];
+ gcc_assert (hard_regno >= 0);
+ mode = reg_raw_mode[hard_regno];
+ excess_cost_change += ((after - before)
+ * (ira_memory_move_cost[mode][cl][0]
+ + ira_memory_move_cost[mode][cl][1]));
+ }
+ INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insn) = excess_cost_change;
+}
+
/* Returns a positive value if x is preferred; returns a negative value if
y is preferred. Should never return 0, since that will make the sort
unstable. */
{
rtx tmp = *(const rtx *) y;
rtx tmp2 = *(const rtx *) x;
+ rtx last;
int tmp_class, tmp2_class;
- int val, priority_val, weight_val, info_val;
+ int val, priority_val, info_val;
+
+ if (MAY_HAVE_DEBUG_INSNS)
+ {
+ /* Schedule debug insns as early as possible. */
+ if (DEBUG_INSN_P (tmp) && !DEBUG_INSN_P (tmp2))
+ return -1;
+ else if (DEBUG_INSN_P (tmp2))
+ return 1;
+ }
/* The insn in a schedule group should be issued the first. */
- if (SCHED_GROUP_P (tmp) != SCHED_GROUP_P (tmp2))
+ if (flag_sched_group_heuristic &&
+ SCHED_GROUP_P (tmp) != SCHED_GROUP_P (tmp2))
return SCHED_GROUP_P (tmp2) ? 1 : -1;
/* Make sure that priority of TMP and TMP2 are initialized. */
gcc_assert (INSN_PRIORITY_KNOWN (tmp) && INSN_PRIORITY_KNOWN (tmp2));
+ if (sched_pressure_p)
+ {
+ int diff;
+
+ /* Prefer insn whose scheduling results in the smallest register
+ pressure excess. */
+ if ((diff = (INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp)
+ + (INSN_TICK (tmp) > clock_var
+ ? INSN_TICK (tmp) - clock_var : 0)
+ - INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp2)
+ - (INSN_TICK (tmp2) > clock_var
+ ? INSN_TICK (tmp2) - clock_var : 0))) != 0)
+ return diff;
+ }
+
+
+ if (sched_pressure_p
+ && (INSN_TICK (tmp2) > clock_var || INSN_TICK (tmp) > clock_var))
+ {
+ if (INSN_TICK (tmp) <= clock_var)
+ return -1;
+ else if (INSN_TICK (tmp2) <= clock_var)
+ return 1;
+ else
+ return INSN_TICK (tmp) - INSN_TICK (tmp2);
+ }
/* Prefer insn with higher priority. */
priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
- if (priority_val)
+ if (flag_sched_critical_path_heuristic && priority_val)
return priority_val;
-
+
/* Prefer speculative insn with greater dependencies weakness. */
- if (spec_info)
+ if (flag_sched_spec_insn_heuristic && spec_info)
{
ds_t ds1, ds2;
dw_t dw1, dw2;
return dw;
}
- /* Prefer an insn with smaller contribution to registers-pressure. */
- if (!reload_completed &&
- (weight_val = INSN_REG_WEIGHT (tmp) - INSN_REG_WEIGHT (tmp2)))
- return weight_val;
-
info_val = (*current_sched_info->rank) (tmp, tmp2);
- if (info_val)
+ if(flag_sched_rank_heuristic && info_val)
return info_val;
- /* Compare insns based on their relation to the last-scheduled-insn. */
- if (INSN_P (last_scheduled_insn))
+ 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);
+ }
+
+ /* Compare insns based on their relation to the last scheduled
+ non-debug insn. */
+ if (flag_sched_last_insn_heuristic && NONDEBUG_INSN_P (last))
{
dep_t dep1;
dep_t dep2;
2) Anti/Output dependent on last scheduled insn.
3) Independent of last scheduled insn, or has latency of one.
Choose the insn from the highest numbered class if different. */
- dep1 = sd_find_dep_between (last_scheduled_insn, tmp, true);
+ dep1 = sd_find_dep_between (last, tmp, true);
if (dep1 == NULL || dep_cost (dep1) == 1)
tmp_class = 3;
else
tmp_class = 2;
- dep2 = sd_find_dep_between (last_scheduled_insn, tmp2, true);
+ dep2 = sd_find_dep_between (last, tmp2, true);
if (dep2 == NULL || dep_cost (dep2) == 1)
tmp2_class = 3;
This gives the scheduler more freedom when scheduling later
instructions at the expense of added register pressure. */
- val = (sd_lists_size (tmp2, SD_LIST_FORW)
- - sd_lists_size (tmp, SD_LIST_FORW));
+ val = (dep_list_size (tmp2) - dep_list_size (tmp));
- if (val != 0)
+ if (flag_sched_dep_count_heuristic && val != 0)
return val;
/* If insns are equally good, sort by INSN_LUID (original insn order),
rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]);
gcc_assert (n_cycles <= max_insn_queue_index);
+ gcc_assert (!DEBUG_INSN_P (insn));
insn_queue[next_q] = link;
q_size += 1;
}
ready->n_ready++;
+ if (DEBUG_INSN_P (insn))
+ ready->n_debug++;
gcc_assert (QUEUE_INDEX (insn) != QUEUE_READY);
QUEUE_INDEX (insn) = QUEUE_READY;
gcc_assert (ready->n_ready);
t = ready->vec[ready->first--];
ready->n_ready--;
+ if (DEBUG_INSN_P (t))
+ ready->n_debug--;
/* If the queue becomes empty, reset it. */
if (ready->n_ready == 0)
ready->first = ready->veclen - 1;
gcc_assert (ready->n_ready && index < ready->n_ready);
t = ready->vec[ready->first - index];
ready->n_ready--;
+ if (DEBUG_INSN_P (t))
+ ready->n_debug--;
for (i = index; i < ready->n_ready; i++)
ready->vec[ready->first - i] = ready->vec[ready->first - i - 1];
QUEUE_INDEX (t) = QUEUE_NOWHERE;
void
ready_sort (struct ready_list *ready)
{
+ int i;
rtx *first = ready_lastpos (ready);
+
+ if (sched_pressure_p)
+ {
+ for (i = 0; i < ready->n_ready; i++)
+ setup_insn_reg_pressure_info (first[i]);
+ }
SCHED_SORT (first, ready->n_ready);
}
{
advance_state (curr_state);
if (sched_verbose >= 6)
- fprintf (sched_dump, "\n;;\tAdvanced a state.\n");
+ fprintf (sched_dump, ";;\tAdvanced a state.\n");
}
/* Clock at which the previous instruction was issued. */
static int last_clock_var;
+/* Update register pressure after scheduling INSN. */
+static void
+update_register_pressure (rtx insn)
+{
+ struct reg_use_data *use;
+ struct reg_set_data *set;
+
+ for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
+ if (dying_use_p (use) && bitmap_bit_p (curr_reg_live, use->regno))
+ mark_regno_birth_or_death (use->regno, false);
+ for (set = INSN_REG_SET_LIST (insn); set != NULL; set = set->next_insn_set)
+ mark_regno_birth_or_death (set->regno, true);
+}
+
+/* Set up or update (if UPDATE_P) max register pressure (see its
+ meaning in sched-int.h::_haifa_insn_data) for all current BB insns
+ after insn AFTER. */
+static void
+setup_insn_max_reg_pressure (rtx after, bool update_p)
+{
+ int i, p;
+ bool eq_p;
+ rtx insn;
+ 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 (insn = NEXT_INSN (after);
+ insn != NULL_RTX && BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (after);
+ insn = NEXT_INSN (insn))
+ if (NONDEBUG_INSN_P (insn))
+ {
+ eq_p = true;
+ for (i = 0; i < ira_reg_class_cover_size; i++)
+ {
+ p = max_reg_pressure[ira_reg_class_cover[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]];
+ }
+ }
+ 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]];
+ }
+ restore_reg_pressure ();
+}
+
+/* Update the current register pressure after scheduling INSN. Update
+ also max register pressure for unscheduled insns of the current
+ BB. */
+static void
+update_reg_and_insn_max_reg_pressure (rtx insn)
+{
+ 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]];
+ 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])
+ break;
+ if (i < ira_reg_class_cover_size)
+ setup_insn_max_reg_pressure (insn, true);
+}
+
+/* Set up register pressure at the beginning of basic block BB whose
+ insns starting after insn AFTER. Set up also max register pressure
+ for all insns of the basic block. */
+void
+sched_setup_bb_reg_pressure_info (basic_block bb, rtx after)
+{
+ gcc_assert (sched_pressure_p);
+ initiate_bb_reg_pressure_info (bb);
+ setup_insn_max_reg_pressure (after, false);
+}
+
/* INSN is the "currently executing insn". Launch each insn which was
waiting on INSN. READY is the ready list which contains the insns
that are ready to fire. CLOCK is the current cycle. The function
{
sd_iterator_def sd_it;
dep_t dep;
+ int i;
int advance = 0;
if (sched_verbose >= 1)
{
+ struct reg_pressure_data *pressure_info;
char buf[2048];
print_insn (buf, insn, 0);
fprintf (sched_dump, "nothing");
else
print_reservation (sched_dump, insn);
+ pressure_info = INSN_REG_PRESSURE (insn);
+ if (pressure_info != NULL)
+ {
+ fputc (':', sched_dump);
+ for (i = 0; i < ira_reg_class_cover_size; i++)
+ fprintf (sched_dump, "%s%+d(%d)",
+ reg_class_names[ira_reg_class_cover[i]],
+ pressure_info[i].set_increase, pressure_info[i].change);
+ }
fputc ('\n', sched_dump);
}
+ if (sched_pressure_p)
+ update_reg_and_insn_max_reg_pressure (insn);
+
/* Scheduling instruction should have all its dependencies resolved and
should have been removed from the ready list. */
gcc_assert (sd_lists_empty_p (insn, SD_LIST_BACK));
be aligned. */
if (issue_rate > 1
&& GET_CODE (PATTERN (insn)) != USE
- && GET_CODE (PATTERN (insn)) != CLOBBER)
+ && GET_CODE (PATTERN (insn)) != CLOBBER
+ && !DEBUG_INSN_P (insn))
{
if (reload_completed)
PUT_MODE (insn, clock_var > last_clock_var ? TImode : VOIDmode);
beg_head = NEXT_INSN (beg_head);
while (beg_head != beg_tail)
- if (NOTE_P (beg_head))
+ if (NOTE_P (beg_head) || BOUNDARY_DEBUG_INSN_P (beg_head))
beg_head = NEXT_INSN (beg_head);
else
break;
end_head = NEXT_INSN (end_head);
while (end_head != end_tail)
- if (NOTE_P (end_tail))
+ if (NOTE_P (end_tail) || BOUNDARY_DEBUG_INSN_P (end_tail))
end_tail = PREV_INSN (end_tail);
else
break;
{
while (head != NEXT_INSN (tail))
{
- if (!NOTE_P (head) && !LABEL_P (head))
+ if (!NOTE_P (head) && !LABEL_P (head)
+ && !BOUNDARY_DEBUG_INSN_P (head))
return 0;
head = NEXT_INSN (head);
}
return head;
}
-/* Functions for computation of registers live/usage info. */
-
-/* This function looks for a new register being defined.
- If the destination register is already used by the source,
- a new register is not needed. */
-static int
-find_set_reg_weight (const_rtx x)
-{
- if (GET_CODE (x) == CLOBBER
- && register_operand (SET_DEST (x), VOIDmode))
- return 1;
- if (GET_CODE (x) == SET
- && register_operand (SET_DEST (x), VOIDmode))
- {
- if (REG_P (SET_DEST (x)))
- {
- if (!reg_mentioned_p (SET_DEST (x), SET_SRC (x)))
- return 1;
- else
- return 0;
- }
- return 1;
- }
- return 0;
-}
-
-/* Calculate INSN_REG_WEIGHT for INSN. */
-static void
-find_insn_reg_weight (const_rtx insn)
-{
- int reg_weight = 0;
- rtx x;
-
- /* Handle register life information. */
- if (! INSN_P (insn))
- return;
-
- /* Increment weight for each register born here. */
- x = PATTERN (insn);
- reg_weight += find_set_reg_weight (x);
- if (GET_CODE (x) == PARALLEL)
- {
- int j;
- for (j = XVECLEN (x, 0) - 1; j >= 0; j--)
- {
- x = XVECEXP (PATTERN (insn), 0, j);
- reg_weight += find_set_reg_weight (x);
- }
- }
- /* Decrement weight for each register that dies here. */
- for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
- {
- if (REG_NOTE_KIND (x) == REG_DEAD
- || REG_NOTE_KIND (x) == REG_UNUSED)
- reg_weight--;
- }
-
- INSN_REG_WEIGHT (insn) = reg_weight;
-}
-
/* Move insns that became ready to fire from queue to ready list. */
static void
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_insn (last_scheduled_insn);
+ {
+ /* 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);
+ }
else
skip_insn = NULL_RTX;
/* If the ready list is full, delay the insn for 1 cycle.
See the comment in schedule_block for the rationale. */
if (!reload_completed
- && ready->n_ready > MAX_SCHED_READY_INSNS
+ && ready->n_ready - ready->n_debug > MAX_SCHED_READY_INSNS
&& !SCHED_GROUP_P (insn)
&& insn != skip_insn)
{
p = ready_lastpos (ready);
for (i = 0; i < ready->n_ready; i++)
- fprintf (sched_dump, " %s", (*current_sched_info->print_insn) (p[i], 0));
+ {
+ fprintf (sched_dump, " %s:%d",
+ (*current_sched_info->print_insn) (p[i], 0),
+ INSN_LUID (p[i]));
+ if (sched_pressure_p)
+ fprintf (sched_dump, "(cost=%d",
+ INSN_REG_PRESSURE_EXCESS_COST_CHANGE (p[i]));
+ if (INSN_TICK (p[i]) > clock_var)
+ fprintf (sched_dump, ":delay=%d", INSN_TICK (p[i]) - clock_var);
+ if (sched_pressure_p)
+ fprintf (sched_dump, ")");
+ }
fprintf (sched_dump, "\n");
}
{
if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
{
- enum insn_note note_type = INTVAL (XEXP (note, 0));
+ enum insn_note note_type = (enum insn_note) INTVAL (XEXP (note, 0));
last = emit_note_before (note_type, last);
remove_note (insn, note);
SCHED_GROUP_P (insn) = 0;
}
+/* Return true if scheduling INSN will finish current clock cycle. */
+static bool
+insn_finishes_cycle_p (rtx insn)
+{
+ if (SCHED_GROUP_P (insn))
+ /* After issuing INSN, rest of the sched_group will be forced to issue
+ in order. Don't make any plans for the rest of cycle. */
+ return true;
+
+ /* Finishing the block will, apparently, finish the cycle. */
+ if (current_sched_info->insn_finishes_block_p
+ && current_sched_info->insn_finishes_block_p (insn))
+ return true;
+
+ return false;
+}
+
/* The following structure describe an entry of the stack of choices. */
struct choice_entry
{
/* Init max_points. */
max_points = 0;
more_issue = issue_rate - cycle_issued_insns;
- gcc_assert (more_issue >= 0);
+
+ /* ??? 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])
delay = state_transition (state, insn);
if (delay < 0)
{
- if (state_dead_lock_p (state))
+ if (state_dead_lock_p (state)
+ || insn_finishes_cycle_p (insn))
+ /* We won't issue any more instructions in the next
+ choice_state. */
top->rest = 0;
else
top->rest--;
if (targetm.sched.first_cycle_multipass_dfa_lookahead)
lookahead = targetm.sched.first_cycle_multipass_dfa_lookahead ();
- if (lookahead <= 0 || SCHED_GROUP_P (ready_element (ready, 0)))
+ if (lookahead <= 0 || SCHED_GROUP_P (ready_element (ready, 0))
+ || DEBUG_INSN_P (ready_element (ready, 0)))
{
*insn_ptr = ready_remove_first (ready);
return 0;
{
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
ready_try [i]
= (/* INSN_CODE check can be omitted here as it is also done later
if (max_issue (ready, 1, curr_state, &index) == 0)
{
- if (sched_verbose >= 4)
- fprintf (sched_dump, ";;\t\tChosen none\n");
*insn_ptr = ready_remove_first (ready);
+ if (sched_verbose >= 4)
+ fprintf (sched_dump, ";;\t\tChosen insn (but can't issue) : %s \n",
+ (*current_sched_info->print_insn) (*insn_ptr, 0));
return 0;
}
else
/* Clear the ready list. */
ready.first = ready.veclen - 1;
ready.n_ready = 0;
+ ready.n_debug = 0;
/* It is used for first cycle multipass scheduling. */
temp_state = alloca (dfa_state_size);
/* We start inserting insns after PREV_HEAD. */
last_scheduled_insn = prev_head;
- gcc_assert (NOTE_P (last_scheduled_insn)
+ gcc_assert ((NOTE_P (last_scheduled_insn)
+ || BOUNDARY_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
/* The algorithm is O(n^2) in the number of ready insns at any given
time in the worst case. Before reload we are more likely to have
big lists so truncate them to a reasonable size. */
- if (!reload_completed && ready.n_ready > MAX_SCHED_READY_INSNS)
+ if (!reload_completed
+ && ready.n_ready - ready.n_debug > MAX_SCHED_READY_INSNS)
{
ready_sort (&ready);
- /* Find first free-standing insn past MAX_SCHED_READY_INSNS. */
- for (i = MAX_SCHED_READY_INSNS; i < ready.n_ready; i++)
+ /* Find first free-standing insn past MAX_SCHED_READY_INSNS.
+ If there are debug insns, we know they're first. */
+ for (i = MAX_SCHED_READY_INSNS + ready.n_debug; i < ready.n_ready; i++)
if (!SCHED_GROUP_P (ready_element (&ready, i)))
break;
}
}
+ /* We don't want md sched reorder to even see debug isns, so put
+ 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);
+ last_scheduled_insn = insn;
+ advance = schedule_insn (insn);
+ gcc_assert (advance == 0);
+ if (ready.n_ready > 0)
+ ready_sort (&ready);
+ }
+
+ if (!ready.n_ready)
+ continue;
+ }
+
/* Allow the target to reorder the list, typically for
better instruction bundling. */
if (sort_p && targetm.sched.reorder
fprintf (sched_dump, ";;\tReady list (t = %3d): ",
clock_var);
debug_ready_list (&ready);
+ if (sched_pressure_p)
+ print_curr_reg_pressure ();
}
if (ready.n_ready == 0
ready_sort (&ready);
}
- if (ready.n_ready == 0 || !can_issue_more
+ if (ready.n_ready == 0
+ || !can_issue_more
|| state_dead_lock_p (curr_state)
|| !(*current_sched_info->schedule_more_p) ())
break;
else
insn = ready_remove_first (&ready);
+ if (sched_pressure_p && INSN_TICK (insn) > clock_var)
+ {
+ ready_add (&ready, insn, true);
+ advance = 1;
+ break;
+ }
+
if (targetm.sched.dfa_new_cycle
&& targetm.sched.dfa_new_cycle (sched_dump, sched_verbose,
insn, last_clock_var,
fatal error for unrecognizable insns. */
cost = 0;
}
+ else if (sched_pressure_p)
+ cost = 0;
else
{
cost = state_transition (temp_state, insn);
if (targetm.sched.variable_issue)
can_issue_more =
targetm.sched.variable_issue (sched_dump, sched_verbose,
- insn, can_issue_more);
+ insn, can_issue_more);
/* A naked CLOBBER or USE generates no instruction, so do
not count them against the issue rate. */
else if (GET_CODE (PATTERN (insn)) != USE
&& GET_CODE (PATTERN (insn)) != CLOBBER)
can_issue_more--;
-
advance = schedule_insn (insn);
/* After issuing an asm insn we should start a new cycle. */
if (ready.n_ready > 0)
ready_sort (&ready);
+ /* Quickly go through debug insns such that md sched
+ reorder2 doesn't have to deal with debug insns. */
+ 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)))
+ {
+ 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);
+ advance = schedule_insn (insn);
+ last_scheduled_insn = insn;
+ gcc_assert (advance == 0);
+ if (ready.n_ready > 0)
+ ready_sort (&ready);
+ }
+ }
+
if (targetm.sched.reorder2
&& (ready.n_ready == 0
|| !SCHED_GROUP_P (ready_element (&ready, 0))))
if (current_sched_info->queue_must_finish_empty)
/* Sanity check -- queue must be empty now. Meaningless if region has
multiple bbs. */
- gcc_assert (!q_size && !ready.n_ready);
+ gcc_assert (!q_size && !ready.n_ready && !ready.n_debug);
else
{
/* We must maintain QUEUE_INDEX between blocks in region. */
current_sched_info->sched_max_insns_priority;
rtx prev_head;
- if (head == tail && (! INSN_P (head)))
- return 0;
+ if (head == tail && (! INSN_P (head) || BOUNDARY_DEBUG_INSN_P (head)))
+ gcc_unreachable ();
n_insn = 0;
flag_schedule_speculative_load = 0;
#endif
+ 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 ();
+
/* Initialize SPEC_INFO. */
if (targetm.sched.set_sched_flags)
{
targetm.sched.md_init_global (sched_dump, sched_verbose,
get_max_uid () + 1);
+ if (sched_pressure_p)
+ {
+ int i, max_regno = max_reg_num ();
+
+ ira_set_pseudo_classes (sched_verbose ? sched_dump : NULL);
+ sched_regno_cover_class
+ = (enum reg_class *) xmalloc (max_regno * sizeof (enum reg_class));
+ for (i = 0; i < max_regno; i++)
+ sched_regno_cover_class[i]
+ = (i < FIRST_PSEUDO_REGISTER
+ ? ira_class_translate[REGNO_REG_CLASS (i)]
+ : reg_cover_class (i));
+ curr_reg_live = BITMAP_ALLOC (NULL);
+ saved_reg_live = BITMAP_ALLOC (NULL);
+ region_ref_regs = BITMAP_ALLOC (NULL);
+ }
+
curr_state = xmalloc (dfa_state_size);
}
sched_finish (void)
{
haifa_finish_h_i_d ();
+ if (sched_pressure_p)
+ {
+ free (sched_regno_cover_class);
+ BITMAP_FREE (region_ref_regs);
+ BITMAP_FREE (saved_reg_live);
+ BITMAP_FREE (curr_reg_live);
+ }
free (curr_state);
if (targetm.sched.md_finish_global)
INSN_TICK (next) = tick;
delay = tick - clock_var;
- if (delay <= 0)
+ if (delay <= 0 || sched_pressure_p)
delay = QUEUE_READY;
change_queue_index (next, delay);
/* Rewritten from cfgrtl.c. */
if (flag_reorder_blocks_and_partition
&& targetm.have_named_sections)
- /* We don't need the same note for the check because
- any_condjump_p (check) == true. */
{
- REG_NOTES (jump) = gen_rtx_EXPR_LIST (REG_CROSSING_JUMP,
- NULL_RTX,
- REG_NOTES (jump));
+ /* We don't need the same note for the check because
+ any_condjump_p (check) == true. */
+ add_reg_note (jump, REG_CROSSING_JUMP, NULL_RTX);
}
edge_flags = EDGE_CROSSING;
}
todo_spec &= SPECULATIVE;
/* Create recovery block. */
- if (mutate_p || targetm.sched.needs_block_p (insn))
+ if (mutate_p || targetm.sched.needs_block_p (todo_spec))
{
rec = sched_create_recovery_block (NULL);
label = BB_HEAD (rec);
}
/* Emit CHECK. */
- check = targetm.sched.gen_spec_check (insn, label, mutate_p);
+ check = targetm.sched.gen_spec_check (insn, label, todo_spec);
if (rec != EXIT_BLOCK_PTR)
{
if (insn == jump)
break;
- if (sd_lists_empty_p (insn, SD_LIST_FORW))
+ if (dep_list_size (insn) == 0)
{
dep_def _new_dep, *new_dep = &_new_dep;
return 0;
}
+/* Search back, starting at INSN, for an insn that is not a
+ NOTE_INSN_VAR_LOCATION. Don't search beyond HEAD, and return it if
+ no such insn can be found. */
+static inline rtx
+prev_non_location_insn (rtx insn, rtx head)
+{
+ while (insn != head && NOTE_P (insn)
+ && NOTE_KIND (insn) == NOTE_INSN_VAR_LOCATION)
+ insn = PREV_INSN (insn);
+
+ return insn;
+}
+
/* Check few properties of CFG between HEAD and TAIL.
If HEAD (TAIL) is NULL check from the beginning (till the end) of the
instruction stream. */
{
if (control_flow_insn_p (head))
{
- gcc_assert (BB_END (bb) == head);
-
+ gcc_assert (prev_non_location_insn (BB_END (bb), head)
+ == head);
+
if (any_uncondjump_p (head))
gcc_assert (EDGE_COUNT (bb->succs) == 1
&& BARRIER_P (NEXT_INSN (head)));
if (BB_END (bb) == head)
{
if (EDGE_COUNT (bb->succs) > 1)
- gcc_assert (control_flow_insn_p (head)
+ gcc_assert (control_flow_insn_p (prev_non_location_insn
+ (head, BB_HEAD (bb)))
|| has_edge_p (bb->succs, EDGE_COMPLEX));
bb = 0;
}
-
+
head = NEXT_INSN (head);
}
}
#endif /* ENABLE_CHECKING */
-const struct sched_scan_info_def *sched_scan_info;
-
/* Extend per basic block data structures. */
static void
extend_bb (void)
if (INSN_LUID (insn) > 0)
{
INSN_COST (insn) = -1;
- find_insn_reg_weight (insn);
QUEUE_INDEX (insn) = QUEUE_NOWHERE;
INSN_TICK (insn) = INVALID_TICK;
INTER_TICK (insn) = INVALID_TICK;
void
haifa_finish_h_i_d (void)
{
+ int i;
+ 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++)
+ {
+ if (data->reg_pressure != NULL)
+ free (data->reg_pressure);
+ for (use = data->reg_use_list; use != NULL; use = next)
+ {
+ next = use->next_insn_use;
+ free (use);
+ }
+ }
VEC_free (haifa_insn_data_def, heap, h_i_d);
}
return create_empty_bb (after);
}
+/* Insert PAT as an INSN into the schedule and update the necessary data
+ structures to account for it. */
+rtx
+sched_emit_insn (rtx pat)
+{
+ rtx insn = emit_insn_after (pat, last_scheduled_insn);
+ last_scheduled_insn = insn;
+ haifa_init_insn (insn);
+ return insn;
+}
+
#endif /* INSN_SCHEDULING */
OSDN Git Service
