X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fhaifa-sched.c;h=0cb329077bb3219246aa62c573a3ccf67d9158eb;hb=8ce5985492e01af26fb8cabcc38118f8ae0a91e2;hp=0dd220d7302a507355c7408209e78b0bbb0141f9;hpb=f145fac4afd9586470a3337fe49279ad4a289b33;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/haifa-sched.c b/gcc/haifa-sched.c index 0dd220d7302..0cb329077bb 100644 --- a/gcc/haifa-sched.c +++ b/gcc/haifa-sched.c @@ -1,6 +1,6 @@ /* 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) @@ -128,7 +128,7 @@ along with GCC; see the file COPYING3. If not see #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" @@ -138,7 +138,6 @@ along with GCC; see the file COPYING3. If not see #include "insn-config.h" #include "insn-attr.h" #include "except.h" -#include "toplev.h" #include "recog.h" #include "sched-int.h" #include "target.h" @@ -148,6 +147,7 @@ along with GCC; see the file COPYING3. If not see #include "dbgcnt.h" #include "cfgloop.h" #include "ira.h" +#include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */ #ifdef INSN_SCHEDULING @@ -166,25 +166,12 @@ int issue_rate; 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; @@ -198,10 +185,6 @@ 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; @@ -319,6 +302,10 @@ static struct ready_list *readyp = &ready; /* 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. */ @@ -345,8 +332,6 @@ const struct common_sched_info_def haifa_common_sched_info = SCHED_PASS_UNKNOWN /* sched_pass_id */ }; -const struct sched_scan_info_def *sched_scan_info; - /* Mapping from instruction UID to its Logical UID. */ VEC (int, heap) *sched_luids = NULL; @@ -506,7 +491,7 @@ haifa_classify_insn (const_rtx insn) 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); @@ -531,6 +516,7 @@ static void extend_h_i_d (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 *); @@ -542,8 +528,6 @@ static void debug_ready_list (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); @@ -591,11 +575,11 @@ schedule_insns (void) 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]; @@ -625,39 +609,41 @@ sched_init_region_reg_pressure_info (void) 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]--; } } } @@ -671,8 +657,8 @@ initiate_reg_pressure_info (bitmap live) 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)) @@ -690,11 +676,11 @@ setup_ref_regs (rtx x) 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); @@ -713,12 +699,12 @@ setup_ref_regs (rtx x) 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) FOR_BB_INSNS (bb, insn) - if (INSN_P (insn)) + if (NONDEBUG_INSN_P (insn)) setup_ref_regs (PATTERN (insn)); initiate_reg_pressure_info (df_get_live_in (bb)); #ifdef EH_RETURN_DATA_REGNO @@ -741,9 +727,9 @@ 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]]; + 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); } @@ -753,9 +739,9 @@ 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]]; + 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); } @@ -773,7 +759,7 @@ dying_use_p (struct reg_use_data *use) } /* Print info about the current register pressure and its excess for - each cover class. */ + each pressure class. */ static void print_curr_reg_pressure (void) { @@ -781,9 +767,9 @@ 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], @@ -792,12 +778,20 @@ print_curr_reg_pressure (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 to the last nondebug instruction scheduled within the + block, or the prev_head of the scheduling block. Used by + rank_for_schedule, so that insns independent of the last scheduled + insn will be preferred over dependent instructions. */ +static rtx last_nondebug_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) @@ -862,7 +856,7 @@ dep_cost_1 (dep_t link, dw_t dw) /* 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; @@ -1123,24 +1117,27 @@ setup_insn_reg_pressure_info (rtx insn) struct reg_use_data *use; static int death[N_REG_CLASSES]; + 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]); @@ -1165,7 +1162,6 @@ rank_for_schedule (const void *x, const void *y) { rtx tmp = *(const rtx *) y; rtx tmp2 = *(const rtx *) x; - rtx last; int tmp_class, tmp2_class; int val, priority_val, info_val; @@ -1246,23 +1242,13 @@ rank_for_schedule (const void *x, const void *y) if(flag_sched_rank_heuristic && info_val) return info_val; - 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)) + if (flag_sched_last_insn_heuristic && last_nondebug_scheduled_insn) { dep_t dep1; dep_t dep2; + rtx last = last_nondebug_scheduled_insn; /* Classify the instructions into three classes: 1) Data dependent on last schedule insn. @@ -1326,10 +1312,11 @@ swap_sort (rtx *a, int n) /* 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]); @@ -1345,7 +1332,7 @@ queue_insn (rtx insn, int n_cycles) 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; @@ -1499,7 +1486,8 @@ ready_sort (struct ready_list *ready) if (sched_pressure_p) { for (i = 0; i < ready->n_ready; i++) - setup_insn_reg_pressure_info (first[i]); + if (!DEBUG_INSN_P (first[i])) + setup_insn_reg_pressure_info (first[i]); } SCHED_SORT (first, ready->n_ready); } @@ -1563,6 +1551,8 @@ update_register_pressure (rtx insn) struct reg_use_data *use; struct reg_set_data *set; + gcc_checking_assert (!DEBUG_INSN_P (insn)); + 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); @@ -1582,33 +1572,34 @@ setup_insn_max_reg_pressure (rtx after, bool update_p) 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 && BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (after); + insn != NULL_RTX && ! BARRIER_P (insn) + && 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++) + 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 (); } @@ -1622,13 +1613,13 @@ 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]]; + 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); } @@ -1674,15 +1665,15 @@ schedule_insn (rtx insn) 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); } - if (sched_pressure_p) + if (sched_pressure_p && !DEBUG_INSN_P (insn)) update_reg_and_insn_max_reg_pressure (insn); /* Scheduling instruction should have all its dependencies resolved and @@ -1720,6 +1711,12 @@ schedule_insn (rtx insn) /* Unknown location doesn't use any registers. */ for (use = INSN_REG_USE_LIST (dbg); use != NULL; use = next) { + struct reg_use_data *prev = use; + + /* Remove use from the cyclic next_regno_use chain first. */ + while (prev->next_regno_use != use) + prev = prev->next_regno_use; + prev->next_regno_use = use->next_regno_use; next = use->next_insn_use; free (use); } @@ -1785,7 +1782,7 @@ schedule_insn (rtx insn) forward dependencies for INSN anymore. Nevertheless they are used in heuristics in rank_for_schedule (), early_queue_to_ready () and in some targets (e.g. rs6000). Thus the earliest place where we *can* - remove dependencies is after targetm.sched.md_finish () call in + remove dependencies is after targetm.sched.finish () call in schedule_block (). But, on the other side, the safest place to remove dependencies is when we are finishing scheduling entire region. As we don't generate [many] dependencies during scheduling itself, we won't @@ -1906,8 +1903,33 @@ get_ebb_head_tail (basic_block beg, basic_block end, rtx *headp, rtx *tailp) 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; @@ -1919,8 +1941,36 @@ get_ebb_head_tail (basic_block beg, basic_block end, rtx *headp, rtx *tailp) 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; @@ -1934,8 +1984,7 @@ no_real_insns_p (const_rtx head, const_rtx tail) { 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); } @@ -1991,11 +2040,14 @@ queue_to_ready (struct ready_list *ready) 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; @@ -2017,11 +2069,7 @@ queue_to_ready (struct ready_list *ready) && 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); @@ -2083,22 +2131,18 @@ queue_to_ready (struct ready_list *ready) 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)) { @@ -2120,9 +2164,8 @@ ok_for_early_queue_removal (rtx insn) break; } - if (!prev_insn) + if (i == 0) break; - prev_insn = PREV_INSN (prev_insn); } } @@ -2384,6 +2427,12 @@ insn_finishes_cycle_p (rtx 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 { @@ -2395,6 +2444,8 @@ 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 @@ -2434,8 +2485,7 @@ static int cached_issue_rate = 0; 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. @@ -2446,9 +2496,9 @@ static int cached_issue_rate = 0; 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; @@ -2467,25 +2517,8 @@ max_issue (struct ready_list *ready, int privileged_n, state_t state, } /* 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; @@ -2496,6 +2529,10 @@ max_issue (struct ready_list *ready, int privileged_n, state_t state, 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++) @@ -2510,12 +2547,17 @@ max_issue (struct ready_list *ready, int privileged_n, state_t state, 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; @@ -2538,7 +2580,7 @@ max_issue (struct ready_list *ready, int privileged_n, state_t state, /* 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; } } @@ -2549,6 +2591,11 @@ max_issue (struct ready_list *ready, int privileged_n, state_t state, /* 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); } @@ -2563,15 +2610,15 @@ max_issue (struct ready_list *ready, int privileged_n, state_t state, { 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++; @@ -2580,8 +2627,15 @@ max_issue (struct ready_list *ready, int privileged_n, state_t state, 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; } } @@ -2590,6 +2644,11 @@ max_issue (struct ready_list *ready, int privileged_n, state_t state, 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); @@ -2604,19 +2663,24 @@ max_issue (struct ready_list *ready, int privileged_n, state_t state, 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; @@ -2633,7 +2697,11 @@ choose_ready (struct ready_list *ready, rtx *insn_ptr) 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 @@ -2713,14 +2781,12 @@ choose_ready (struct ready_list *ready, rtx *insn_ptr) { 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 @@ -2731,7 +2797,7 @@ choose_ready (struct ready_list *ready, rtx *insn_ptr) (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) @@ -2752,6 +2818,98 @@ choose_ready (struct ready_list *ready, rtx *insn_ptr) } } +/* 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. */ @@ -2759,7 +2917,8 @@ choose_ready (struct ready_list *ready, rtx *insn_ptr) 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; @@ -2795,14 +2954,15 @@ schedule_block (basic_block *target_bb) /* It is used for first cycle multipass scheduling. */ temp_state = alloca (dfa_state_size); - if (targetm.sched.md_init) - targetm.sched.md_init (sched_dump, sched_verbose, ready.veclen); + if (targetm.sched.init) + 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; + last_nondebug_scheduled_insn = NULL_RTX; 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 @@ -2844,12 +3004,12 @@ schedule_block (basic_block *target_bb) /* 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; @@ -2860,8 +3020,10 @@ schedule_block (basic_block *target_bb) 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); } } @@ -2872,6 +3034,7 @@ schedule_block (basic_block *target_bb) 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) ()) @@ -2901,78 +3064,77 @@ schedule_block (basic_block *target_bb) } while (advance > 0); - if (sort_p) - { - /* Sort the ready list based on priority. */ - ready_sort (&ready); - - if (sched_verbose >= 2) - { - fprintf (sched_dump, ";;\t\tReady list after ready_sort: "); - debug_ready_list (&ready); - } - } + if (ready.n_ready > 0) + prune_ready_list (temp_state, true); + if (ready.n_ready == 0) + continue; - /* 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))) + first_cycle_insn_p = true; + cycle_issued_insns = 0; + can_issue_more = issue_rate; + for (;;) { - if (control_flow_insn_p (last_scheduled_insn)) + rtx insn; + int cost; + bool asm_p = false; + + if (sort_p && ready.n_ready > 0) { - *target_bb = current_sched_info->advance_target_bb - (*target_bb, 0); + /* Sort the ready list based on priority. This must be + done every iteration through the loop, as schedule_insn + may have readied additional insns that will not be + sorted correctly. */ + ready_sort (&ready); - if (sched_verbose) + if (sched_verbose >= 2) { - rtx x; - - x = next_real_insn (last_scheduled_insn); - gcc_assert (x); - dump_new_block_header (1, *target_bb, x, tail); + fprintf (sched_dump, ";;\t\tReady list after ready_sort: "); + debug_ready_list (&ready); } - - last_scheduled_insn = bb_note (*target_bb); } - while (ready.n_ready && DEBUG_INSN_P (ready_element (&ready, 0))) + /* 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)) + && (*current_sched_info->schedule_more_p) ()) { - 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); + 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); + VEC_safe_push (rtx, heap, scheduled_insns, insn); + 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 - && (ready.n_ready == 0 - || !SCHED_GROUP_P (ready_element (&ready, 0)))) - can_issue_more = - targetm.sched.reorder (sched_dump, sched_verbose, - ready_lastpos (&ready), - &ready.n_ready, clock_var); - else - can_issue_more = issue_rate; + if (first_cycle_insn_p && !ready.n_ready) + break; - first_cycle_insn_p = 1; - cycle_issued_insns = 0; - for (;;) - { - rtx insn; - int cost; - bool asm_p = false; + /* Allow the target to reorder the list, typically for + better instruction bundling. */ + if (sort_p + && (ready.n_ready == 0 + || !SCHED_GROUP_P (ready_element (&ready, 0)))) + { + if (first_cycle_insn_p && targetm.sched.reorder) + can_issue_more + = targetm.sched.reorder (sched_dump, sched_verbose, + ready_lastpos (&ready), + &ready.n_ready, clock_var); + else if (!first_cycle_insn_p && targetm.sched.reorder2) + can_issue_more + = targetm.sched.reorder2 (sched_dump, sched_verbose, + ready.n_ready + ? ready_lastpos (&ready) : NULL, + &ready.n_ready, clock_var); + } + restart_choose_ready: if (sched_verbose >= 2) { fprintf (sched_dump, ";;\tReady list (t = %3d): ", @@ -3008,14 +3170,13 @@ schedule_block (basic_block *target_bb) int res; insn = NULL_RTX; - res = choose_ready (&ready, &insn); + res = choose_ready (&ready, first_cycle_insn_p, &insn); if (res < 0) /* Finish cycle. */ break; if (res > 0) - /* Restart choose_ready (). */ - continue; + goto restart_choose_ready; gcc_assert (insn != NULL_RTX); } @@ -3050,44 +3211,6 @@ schedule_block (basic_block *target_bb) } 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)) @@ -3095,7 +3218,7 @@ schedule_block (basic_block *target_bb) insn from the split block. */ { TODO_SPEC (insn) = (TODO_SPEC (insn) & ~SPECULATIVE) | HARD_DEP; - continue; + goto restart_choose_ready; } /* DECISION is made. */ @@ -3103,42 +3226,28 @@ schedule_block (basic_block *target_bb) 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); - last_scheduled_insn = insn; + (*current_sched_info->begin_schedule_ready) (insn); + VEC_safe_push (rtx, heap, scheduled_insns, insn); + gcc_assert (NONDEBUG_INSN_P (insn)); + last_nondebug_scheduled_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 = @@ -3157,62 +3266,9 @@ schedule_block (basic_block *target_bb) if (advance != 0) break; - first_cycle_insn_p = 0; - - /* 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. */ + first_cycle_insn_p = false; 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)))) - { - can_issue_more = - targetm.sched.reorder2 (sched_dump, sched_verbose, - ready.n_ready - ? ready_lastpos (&ready) : NULL, - &ready.n_ready, clock_var); - } + prune_ready_list (temp_state, false); } } @@ -3255,6 +3311,7 @@ schedule_block (basic_block *target_bb) } } + commit_schedule (prev_head, tail, target_bb); if (sched_verbose) fprintf (sched_dump, ";; total time = %d\n", clock_var); @@ -3270,14 +3327,14 @@ schedule_block (basic_block *target_bb) fix_inter_tick (NEXT_INSN (prev_head), last_scheduled_insn); } - if (targetm.sched.md_finish) + if (targetm.sched.finish) { - targetm.sched.md_finish (sched_dump, sched_verbose); + targetm.sched.finish (sched_dump, sched_verbose); /* Target might have added some instructions to the scheduled block in its md_finish () hook. These new insns don't have any data initialized and to identify them we extend h_i_d so that they'll get zero luids. */ - sched_init_luids (NULL, NULL, NULL, NULL); + sched_extend_luids (); } if (sched_verbose) @@ -3305,7 +3362,7 @@ set_priorities (rtx head, rtx tail) 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; @@ -3355,8 +3412,12 @@ sched_init (void) 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 (); @@ -3431,22 +3492,21 @@ sched_init (void) regstat_compute_calls_crossed (); - if (targetm.sched.md_init_global) - targetm.sched.md_init_global (sched_dump, sched_verbose, - get_max_uid () + 1); + if (targetm.sched.init_global) + targetm.sched.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 + 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); @@ -3464,6 +3524,8 @@ haifa_sched_init (void) setup_sched_dump (); sched_init (); + scheduled_insns = VEC_alloc (rtx, heap, 0); + if (spec_info != NULL) { sched_deps_info->use_deps_list = 1; @@ -3480,10 +3542,10 @@ haifa_sched_init (void) FOR_EACH_BB (bb) VEC_quick_push (basic_block, bbs, bb); - sched_init_luids (bbs, NULL, NULL, NULL); + sched_init_luids (bbs); sched_deps_init (true); sched_extend_target (); - haifa_init_h_i_d (bbs, NULL, NULL, NULL); + haifa_init_h_i_d (bbs); VEC_free (basic_block, heap, bbs); } @@ -3534,6 +3596,8 @@ haifa_sched_finish (void) 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 (); @@ -3551,15 +3615,15 @@ sched_finish (void) 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); } free (curr_state); - if (targetm.sched.md_finish_global) - targetm.sched.md_finish_global (sched_dump, sched_verbose); + if (targetm.sched.finish_global) + targetm.sched.finish_global (sched_dump, sched_verbose); end_alias_analysis (); @@ -3605,9 +3669,8 @@ fix_inter_tick (rtx head, rtx tail) 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) @@ -3627,9 +3690,8 @@ fix_inter_tick (rtx head, rtx tail) /* 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) @@ -3836,7 +3898,7 @@ fix_tick_ready (rtx next) { 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; @@ -3904,7 +3966,7 @@ change_queue_index (rtx next, int delay) 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) { @@ -3934,6 +3996,7 @@ sched_extend_ready_list (int new_sched_ready_n_insns) { 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; @@ -3952,7 +4015,13 @@ sched_extend_ready_list (int new_sched_ready_n_insns) 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; } @@ -3971,7 +4040,13 @@ sched_finish_ready_list (void) 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; @@ -4228,10 +4303,9 @@ xrecalloc (void *p, size_t new_nmemb, size_t old_nmemb, size_t size) /* 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; @@ -4239,21 +4313,23 @@ find_fallthru_edge (basic_block pred) 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; @@ -4295,7 +4371,7 @@ init_before_recovery (basic_block *before_recovery_ptr) edge e; last = EXIT_BLOCK_PTR->prev_bb; - e = find_fallthru_edge (last); + e = find_fallthru_edge_from (last); if (e) { @@ -4439,6 +4515,8 @@ sched_create_recovery_edges (basic_block first_bb, basic_block rec, 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, @@ -4748,11 +4826,8 @@ fix_recovery_deps (basic_block rec) { 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 { @@ -5090,7 +5165,7 @@ calc_priorities (rtx_vec_t roots) int i; rtx insn; - for (i = 0; VEC_iterate (rtx, roots, i, insn); i++) + FOR_EACH_VEC_ELT (rtx, roots, i, insn) priority (insn); } @@ -5258,105 +5333,9 @@ check_cfg (rtx head, rtx tail) #endif /* ENABLE_CHECKING */ -/* Extend per basic block data structures. */ -static void -extend_bb (void) -{ - if (sched_scan_info->extend_bb) - sched_scan_info->extend_bb (); -} - -/* Init data for BB. */ -static void -init_bb (basic_block bb) -{ - if (sched_scan_info->init_bb) - sched_scan_info->init_bb (bb); -} - -/* Extend per insn data structures. */ -static void -extend_insn (void) -{ - if (sched_scan_info->extend_insn) - sched_scan_info->extend_insn (); -} - -/* Init data structures for INSN. */ -static void -init_insn (rtx insn) -{ - if (sched_scan_info->init_insn) - sched_scan_info->init_insn (insn); -} - -/* Init all insns in BB. */ -static void -init_insns_in_bb (basic_block bb) -{ - rtx insn; - - FOR_BB_INSNS (bb, insn) - init_insn (insn); -} - -/* A driver function to add a set of basic blocks (BBS), - a single basic block (BB), a set of insns (INSNS) or a single insn (INSN) - to the scheduling region. */ -void -sched_scan (const struct sched_scan_info_def *ssi, - bb_vec_t bbs, basic_block bb, insn_vec_t insns, rtx insn) -{ - sched_scan_info = ssi; - - if (bbs != NULL || bb != NULL) - { - extend_bb (); - - if (bbs != NULL) - { - unsigned i; - basic_block x; - - for (i = 0; VEC_iterate (basic_block, bbs, i, x); i++) - init_bb (x); - } - - if (bb != NULL) - init_bb (bb); - } - - extend_insn (); - - if (bbs != NULL) - { - unsigned i; - basic_block x; - - for (i = 0; VEC_iterate (basic_block, bbs, i, x); i++) - init_insns_in_bb (x); - } - - if (bb != NULL) - init_insns_in_bb (bb); - - if (insns != NULL) - { - unsigned i; - rtx x; - - for (i = 0; VEC_iterate (rtx, insns, i, x); i++) - init_insn (x); - } - - if (insn != NULL) - init_insn (insn); -} - - /* Extend data structures for logical insn UID. */ -static void -luids_extend_insn (void) +void +sched_extend_luids (void) { int new_luids_max_uid = get_max_uid () + 1; @@ -5364,8 +5343,8 @@ luids_extend_insn (void) } /* Initialize LUID for INSN. */ -static void -luids_init_insn (rtx insn) +void +sched_init_insn_luid (rtx insn) { int i = INSN_P (insn) ? 1 : common_sched_info->luid_for_non_insn (insn); int luid; @@ -5381,21 +5360,23 @@ luids_init_insn (rtx insn) SET_INSN_LUID (insn, luid); } -/* Initialize luids for BBS, BB, INSNS and INSN. +/* Initialize luids for BBS. The hook common_sched_info->luid_for_non_insn () is used to determine if notes, labels, etc. need luids. */ void -sched_init_luids (bb_vec_t bbs, basic_block bb, insn_vec_t insns, rtx insn) +sched_init_luids (bb_vec_t bbs) { - const struct sched_scan_info_def ssi = + int i; + basic_block bb; + + sched_extend_luids (); + FOR_EACH_VEC_ELT (basic_block, bbs, i, bb) { - NULL, /* extend_bb */ - NULL, /* init_bb */ - luids_extend_insn, /* extend_insn */ - luids_init_insn /* init_insn */ - }; + rtx insn; - sched_scan (&ssi, bbs, bb, insns, insn); + FOR_BB_INSNS (bb, insn) + sched_init_insn_luid (insn); + } } /* Free LUIDs. */ @@ -5452,19 +5433,21 @@ init_h_i_d (rtx insn) } } -/* Initialize haifa_insn_data for BBS, BB, INSNS and INSN. */ +/* Initialize haifa_insn_data for BBS. */ void -haifa_init_h_i_d (bb_vec_t bbs, basic_block bb, insn_vec_t insns, rtx insn) +haifa_init_h_i_d (bb_vec_t bbs) { - const struct sched_scan_info_def ssi = + int i; + basic_block bb; + + extend_h_i_d (); + FOR_EACH_VEC_ELT (basic_block, bbs, i, bb) { - NULL, /* extend_bb */ - NULL, /* init_bb */ - extend_h_i_d, /* extend_insn */ - init_h_i_d /* init_insn */ - }; + rtx insn; - sched_scan (&ssi, bbs, bb, insns, insn); + FOR_BB_INSNS (bb, insn) + init_h_i_d (insn); + } } /* Finalize haifa_insn_data. */ @@ -5475,10 +5458,9 @@ haifa_finish_h_i_d (void) 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; @@ -5494,10 +5476,12 @@ haifa_init_insn (rtx insn) { gcc_assert (insn != NULL); - sched_init_luids (NULL, NULL, NULL, insn); + sched_extend_luids (); + sched_init_insn_luid (insn); sched_extend_target (); sched_deps_init (false); - haifa_init_h_i_d (NULL, NULL, NULL, insn); + extend_h_i_d (); + init_h_i_d (insn); if (adding_bb_to_current_region_p) { @@ -5506,6 +5490,8 @@ haifa_init_insn (rtx insn) /* 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. */ @@ -5548,10 +5534,86 @@ sched_create_empty_bb_1 (basic_block after) rtx sched_emit_insn (rtx pat) { - rtx insn = emit_insn_after (pat, last_scheduled_insn); - last_scheduled_insn = insn; + rtx insn = emit_insn_before (pat, nonscheduled_insns_begin); haifa_init_insn (insn); + + if (current_sched_info->add_remove_insn) + current_sched_info->add_remove_insn (insn, 0); + + (*current_sched_info->begin_schedule_ready) (insn); + VEC_safe_push (rtx, heap, scheduled_insns, insn); + + last_scheduled_insn = insn; 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 */