X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fhaifa-sched.c;h=b7f0cfce359ced98e1cfb5c4b4978f84cacabe8d;hb=41ad616dd2b78a0c53a488448d00ad7a20c35153;hp=87d7bd11910f623fecf1badbba4407214c827fc5;hpb=9997bd271736dc80d321fb8146633ccda9ae184e;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/haifa-sched.c b/gcc/haifa-sched.c index 87d7bd11910..b7f0cfce359 100644 --- a/gcc/haifa-sched.c +++ b/gcc/haifa-sched.c @@ -1,6 +1,7 @@ /* Instruction scheduling pass. Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000, - 2001, 2002, 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc. + 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 + Free Software Foundation, Inc. Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by, and currently maintained by, Jim Wilson (wilson@cygnus.com) @@ -8,7 +9,7 @@ This file is part of GCC. GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free -Software Foundation; either version 2, or (at your option) any later +Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, but WITHOUT ANY @@ -17,9 +18,8 @@ FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License -along with GCC; see the file COPYING. If not, write to the Free -Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA -02110-1301, USA. */ +along with GCC; see the file COPYING3. If not see +. */ /* Instruction scheduling pass. This file, along with sched-deps.c, contains the generic parts. The actual entry point is found for @@ -144,6 +144,10 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA #include "target.h" #include "output.h" #include "params.h" +#include "vecprim.h" +#include "dbgcnt.h" +#include "cfgloop.h" +#include "ira.h" #ifdef INSN_SCHEDULING @@ -151,7 +155,7 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA machine cycle. It can be defined in the config/mach/mach.h file, otherwise we set it to 1. */ -static int issue_rate; +int issue_rate; /* sched-verbose controls the amount of debugging output the scheduler prints. It is controlled by -fsched-verbose=N: @@ -169,9 +173,6 @@ int sched_verbose = 0; either to stderr, or to the dump listing file (-dRS). */ FILE *sched_dump = 0; -/* Highest uid before scheduling. */ -static int old_max_uid; - /* fix_sched_param() is called from toplev.c upon detection of the -fsched-verbose=N option. */ @@ -184,10 +185,12 @@ fix_sched_param (const char *param, const char *val) warning (0, "fix_sched_param: unknown param: %s", param); } -struct haifa_insn_data *h_i_d; +/* This is a placeholder for the scheduler parameters common + to all schedulers. */ +struct common_sched_info_def *common_sched_info; -#define INSN_TICK(INSN) (h_i_d[INSN_UID (INSN)].tick) -#define INTER_TICK(INSN) (h_i_d[INSN_UID (INSN)].inter_tick) +#define INSN_TICK(INSN) (HID (INSN)->tick) +#define INTER_TICK(INSN) (HID (INSN)->inter_tick) /* If INSN_TICK of an instruction is equal to INVALID_TICK, then it should be recalculated from scratch. */ @@ -201,32 +204,38 @@ struct haifa_insn_data *h_i_d; /* List of important notes we must keep around. This is a pointer to the last element in the list. */ -static rtx note_list; +rtx note_list; static struct spec_info_def spec_info_var; /* Description of the speculative part of the scheduling. If NULL - no speculation. */ -static spec_info_t spec_info; +spec_info_t spec_info = NULL; /* True, if recovery block was added during scheduling of current block. Used to determine, if we need to fix INSN_TICKs. */ -static bool added_recovery_block_p; +static bool haifa_recovery_bb_recently_added_p; + +/* True, if recovery block was added during this scheduling pass. + Used to determine if we should have empty memory pools of dependencies + after finishing current region. */ +bool haifa_recovery_bb_ever_added_p; /* Counters of different types of speculative instructions. */ static int nr_begin_data, nr_be_in_data, nr_begin_control, nr_be_in_control; -/* Pointers to GLAT data. See init_glat for more information. */ -regset *glat_start, *glat_end; - /* Array used in {unlink, restore}_bb_notes. */ static rtx *bb_header = 0; -/* Number of basic_blocks. */ -static int old_last_basic_block; - /* Basic block after which recovery blocks will be created. */ static basic_block before_recovery; +/* Basic block just before the EXIT_BLOCK and after recovery, if we have + created it. */ +basic_block after_recovery; + +/* FALSE if we add bb to another region, so we don't need to initialize it. */ +bool adding_bb_to_current_region_p = true; + /* Queues, etc. */ /* An instruction is ready to be scheduled when all insns preceding it @@ -286,8 +295,8 @@ static int q_size = 0; queue or ready list. QUEUE_READY - INSN is in ready list. N >= 0 - INSN queued for X [where NEXT_Q_AFTER (q_ptr, X) == N] cycles. */ - -#define QUEUE_INDEX(INSN) (h_i_d[INSN_UID (INSN)].queue_index) + +#define QUEUE_INDEX(INSN) (HID (INSN)->queue_index) /* The following variable value refers for all current and future reservations of the processor units. */ @@ -295,38 +304,22 @@ state_t curr_state; /* The following variable value is size of memory representing all current and future reservations of the processor units. */ -static size_t dfa_state_size; +size_t dfa_state_size; /* The following array is used to find the best insn from ready when the automaton pipeline interface is used. */ -static char *ready_try; - -/* Describe the ready list of the scheduler. - VEC holds space enough for all insns in the current region. VECLEN - says how many exactly. - FIRST is the index of the element with the highest priority; i.e. the - last one in the ready list, since elements are ordered by ascending - priority. - N_READY determines how many insns are on the ready list. */ +char *ready_try = NULL; -struct ready_list -{ - rtx *vec; - int veclen; - int first; - int n_ready; -}; +/* The ready list. */ +struct ready_list ready = {NULL, 0, 0, 0, 0}; -/* The pointer to the ready list. */ -static struct ready_list *readyp; +/* The pointer to the ready list (to be removed). */ +static struct ready_list *readyp = &ready; /* Scheduling clock. */ static int clock_var; -/* Number of instructions in current scheduling region. */ -static int rgn_n_insns; - -static int may_trap_exp (rtx, int); +static int may_trap_exp (const_rtx, int); /* Nonzero iff the address is comprised from at most 1 register. */ #define CONST_BASED_ADDRESS_P(x) \ @@ -339,8 +332,41 @@ static int may_trap_exp (rtx, int); /* Returns a class that insn with GET_DEST(insn)=x may belong to, as found by analyzing insn's expression. */ + +static int haifa_luid_for_non_insn (rtx x); + +/* Haifa version of sched_info hooks common to all headers. */ +const struct common_sched_info_def haifa_common_sched_info = + { + NULL, /* fix_recovery_cfg */ + NULL, /* add_block */ + NULL, /* estimate_number_of_insns */ + haifa_luid_for_non_insn, /* luid_for_non_insn */ + 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; + +/* Next LUID to assign to an instruction. */ +int sched_max_luid = 1; + +/* Haifa Instruction Data. */ +VEC (haifa_insn_data_def, heap) *h_i_d = NULL; + +void (* sched_init_only_bb) (basic_block, basic_block); + +/* Split block function. Different schedulers might use different functions + to handle their internal data consistent. */ +basic_block (* sched_split_block) (basic_block, rtx); + +/* Create empty basic block after the specified block. */ +basic_block (* sched_create_empty_bb) (basic_block); + static int -may_trap_exp (rtx x, int is_store) +may_trap_exp (const_rtx x, int is_store) { enum rtx_code code; @@ -403,8 +429,9 @@ may_trap_exp (rtx x, int is_store) } } -/* Classifies insn for the purpose of verifying that it can be - moved speculatively, by examining it's patterns, returning: +/* Classifies rtx X of an insn for the purpose of verifying that X can be + executed speculatively (and consequently the insn can be moved + speculatively), by examining X, returning: TRAP_RISKY: store, or risky non-load insn (e.g. division by variable). TRAP_FREE: non-load insn. IFREE: load from a globally safe location. @@ -412,45 +439,20 @@ may_trap_exp (rtx x, int is_store) PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for being either PFREE or PRISKY. */ -int -haifa_classify_insn (rtx insn) +static int +haifa_classify_rtx (const_rtx x) { - rtx pat = PATTERN (insn); int tmp_class = TRAP_FREE; int insn_class = TRAP_FREE; enum rtx_code code; - if (GET_CODE (pat) == PARALLEL) + if (GET_CODE (x) == PARALLEL) { - int i, len = XVECLEN (pat, 0); + int i, len = XVECLEN (x, 0); for (i = len - 1; i >= 0; i--) { - code = GET_CODE (XVECEXP (pat, 0, i)); - switch (code) - { - case CLOBBER: - /* Test if it is a 'store'. */ - tmp_class = may_trap_exp (XEXP (XVECEXP (pat, 0, i), 0), 1); - break; - case SET: - /* Test if it is a store. */ - tmp_class = may_trap_exp (SET_DEST (XVECEXP (pat, 0, i)), 1); - if (tmp_class == TRAP_RISKY) - break; - /* Test if it is a load. */ - tmp_class - = WORST_CLASS (tmp_class, - may_trap_exp (SET_SRC (XVECEXP (pat, 0, i)), - 0)); - break; - case COND_EXEC: - case TRAP_IF: - tmp_class = TRAP_RISKY; - break; - default: - ; - } + tmp_class = haifa_classify_rtx (XVECEXP (x, 0, i)); insn_class = WORST_CLASS (insn_class, tmp_class); if (insn_class == TRAP_RISKY || insn_class == IRISKY) break; @@ -458,24 +460,30 @@ haifa_classify_insn (rtx insn) } else { - code = GET_CODE (pat); + code = GET_CODE (x); switch (code) { case CLOBBER: /* Test if it is a 'store'. */ - tmp_class = may_trap_exp (XEXP (pat, 0), 1); + tmp_class = may_trap_exp (XEXP (x, 0), 1); break; case SET: /* Test if it is a store. */ - tmp_class = may_trap_exp (SET_DEST (pat), 1); + tmp_class = may_trap_exp (SET_DEST (x), 1); if (tmp_class == TRAP_RISKY) break; /* Test if it is a load. */ tmp_class = WORST_CLASS (tmp_class, - may_trap_exp (SET_SRC (pat), 0)); + may_trap_exp (SET_SRC (x), 0)); break; case COND_EXEC: + tmp_class = haifa_classify_rtx (COND_EXEC_CODE (x)); + if (tmp_class == TRAP_RISKY) + break; + tmp_class = WORST_CLASS (tmp_class, + may_trap_exp (COND_EXEC_TEST (x), 0)); + break; case TRAP_IF: tmp_class = TRAP_RISKY; break; @@ -487,6 +495,12 @@ haifa_classify_insn (rtx insn) return insn_class; } +int +haifa_classify_insn (const_rtx insn) +{ + return haifa_classify_rtx (PATTERN (insn)); +} + /* Forward declarations. */ static int priority (rtx); @@ -494,11 +508,10 @@ static int rank_for_schedule (const void *, const void *); static void swap_sort (rtx *, int); static void queue_insn (rtx, int); static int schedule_insn (rtx); -static int find_set_reg_weight (rtx); -static void find_insn_reg_weight (basic_block); -static void find_insn_reg_weight1 (rtx); static void adjust_priority (rtx); static void advance_one_cycle (void); +static void extend_h_i_d (void); + /* Notes handling mechanism: ========================= @@ -516,12 +529,7 @@ static void advance_one_cycle (void); unlink_other_notes ()). After scheduling the block, these notes are inserted at the beginning of the block (in schedule_block()). */ -static rtx unlink_other_notes (rtx, rtx); -static void reemit_notes (rtx); - -static rtx *ready_lastpos (struct ready_list *); static void ready_add (struct ready_list *, rtx, bool); -static void ready_sort (struct ready_list *); static rtx ready_remove_first (struct ready_list *); static void queue_to_ready (struct ready_list *); @@ -529,16 +537,12 @@ static int early_queue_to_ready (state_t, struct ready_list *); static void debug_ready_list (struct ready_list *); -static void move_insn (rtx); - /* The following functions are used to implement multi-pass scheduling on the first cycle. */ -static rtx ready_element (struct ready_list *, int); static rtx ready_remove (struct ready_list *, int); static void ready_remove_insn (rtx); -static int max_issue (struct ready_list *, int *, int); -static rtx choose_ready (struct ready_list *); +static int choose_ready (struct ready_list *, rtx *); static void fix_inter_tick (rtx, rtx); static int fix_tick_ready (rtx); @@ -548,46 +552,33 @@ static void change_queue_index (rtx, int); speculative instructions. */ static void extend_h_i_d (void); -static void extend_ready (int); -static void extend_global (rtx); -static void extend_all (rtx); static void init_h_i_d (rtx); static void generate_recovery_code (rtx); -static void process_insn_forw_deps_be_in_spec (deps_list_t, rtx, ds_t); +static void process_insn_forw_deps_be_in_spec (rtx, rtx, ds_t); static void begin_speculative_block (rtx); static void add_to_speculative_block (rtx); -static dw_t dep_weak (ds_t); -static edge find_fallthru_edge (basic_block); -static void init_before_recovery (void); -static basic_block create_recovery_block (void); +static void init_before_recovery (basic_block *); static void create_check_block_twin (rtx, bool); static void fix_recovery_deps (basic_block); -static void change_pattern (rtx, rtx); -static int speculate_insn (rtx, ds_t, rtx *); +static void haifa_change_pattern (rtx, rtx); static void dump_new_block_header (int, basic_block, rtx, rtx); static void restore_bb_notes (basic_block); -static void extend_bb (void); static void fix_jump_move (rtx); static void move_block_after_check (rtx); static void move_succs (VEC(edge,gc) **, basic_block); -static void init_glat (void); -static void init_glat1 (basic_block); -static void attach_life_info1 (basic_block); -static void free_glat (void); static void sched_remove_insn (rtx); -static void clear_priorities (rtx); +static void clear_priorities (rtx, rtx_vec_t *); +static void calc_priorities (rtx_vec_t); static void add_jump_dependencies (rtx, rtx); -static void calc_priorities (rtx); #ifdef ENABLE_CHECKING static int has_edge_p (VEC(edge,gc) *, int); static void check_cfg (rtx, rtx); -static void check_sched_flags (void); #endif #endif /* INSN_SCHEDULING */ /* Point to state used for the current scheduling pass. */ -struct sched_info *current_sched_info; +struct haifa_sched_info *current_sched_info; #ifndef INSN_SCHEDULING void @@ -596,8 +587,210 @@ schedule_insns (void) } #else -/* Working copy of frontend's sched_info variable. */ -static struct sched_info current_sched_info_var; +/* 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 (NONDEBUG_INSN_P (next->insn) + && 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 @@ -607,15 +800,29 @@ static rtx last_scheduled_insn; /* 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) (h_i_d[INSN_UID (INSN)].cost) +#define INSN_COST(INSN) (HID (INSN)->cost) /* 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 = INSN_COST (insn); + int cost; + + if (sel_sched_p ()) + { + if (recog_memoized (insn) < 0) + return 0; + + cost = insn_default_latency (insn); + if (cost < 0) + cost = 0; + + return cost; + } + + cost = INSN_COST (insn); if (cost < 0) { @@ -643,22 +850,27 @@ insn_cost (rtx insn) /* 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 (dep_t link) +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_KIND (link); + enum reg_note dep_type = DEP_TYPE (link); cost = insn_cost (insn); @@ -677,18 +889,22 @@ dep_cost (dep_t link) cost = insn_latency (insn, used); } - if (targetm.sched.adjust_cost != NULL) + + if (targetm.sched.adjust_cost_2) + 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 targets. */ rtx dep_cost_rtx_link = alloc_INSN_LIST (NULL_RTX, NULL_RTX); /* Make it self-cycled, so that if some tries to walk over this - incomplete list he/she will be cought in an endless loop. */ + incomplete list he/she will be caught in an endless loop. */ XEXP (dep_cost_rtx_link, 1) = dep_cost_rtx_link; /* Targets use only REG_NOTE_KIND of the link. */ - PUT_REG_NOTE_KIND (dep_cost_rtx_link, DEP_KIND (link)); + PUT_REG_NOTE_KIND (dep_cost_rtx_link, DEP_TYPE (link)); cost = targetm.sched.adjust_cost (used, dep_cost_rtx_link, insn, cost); @@ -703,21 +919,101 @@ dep_cost (dep_t link) return cost; } -/* Compute the priority number for INSN. */ +/* Compute cost of dependence LINK. + This is the number of cycles between instruction issue and + instruction results. */ +int +dep_cost (dep_t link) +{ + return dep_cost_1 (link, 0); +} + +/* Use this sel-sched.c friendly function in reorder2 instead of increasing + INSN_PRIORITY explicitly. */ +void +increase_insn_priority (rtx insn, int amount) +{ + if (!sel_sched_p ()) + { + /* We're dealing with haifa-sched.c INSN_PRIORITY. */ + if (INSN_PRIORITY_KNOWN (insn)) + INSN_PRIORITY (insn) += amount; + } + else + { + /* In sel-sched.c INSN_PRIORITY is not kept up to date. + Use EXPR_PRIORITY instead. */ + sel_add_to_insn_priority (insn, amount); + } +} + +/* Return 'true' if DEP should be included in priority calculations. */ +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 false; + + /* If flag COUNT_SPEC_IN_CRITICAL_PATH is set, + then speculative instructions will less likely be + scheduled. That is because the priority of + their producers will increase, and, thus, the + producers will more likely be scheduled, thus, + resolving the dependence. */ + if (sched_deps_info->generate_spec_deps + && !(spec_info->flags & COUNT_SPEC_IN_CRITICAL_PATH) + && (DEP_STATUS (dep) & SPECULATIVE)) + return false; + + return true; +} + +/* Compute the number of nondebug forward deps of an insn. */ static int -priority (rtx insn) +dep_list_size (rtx insn) { - dep_link_t link; + 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 if (!DEBUG_INSN_P (DEP_PRO (dep))) + 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) +{ if (! INSN_P (insn)) return 0; - if (! INSN_PRIORITY_KNOWN (insn)) + /* We should not be interested in priority of an already scheduled insn. */ + gcc_assert (QUEUE_INDEX (insn) != QUEUE_SCHEDULED); + + if (!INSN_PRIORITY_KNOWN (insn)) { - int this_priority = 0; + int this_priority = -1; - if (deps_list_empty_p (INSN_FORW_DEPS (insn))) + 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 @@ -732,9 +1028,10 @@ priority (rtx insn) different than that of normal instructions. Instead of walking through INSN_FORW_DEPS (check) list, we walk through INSN_FORW_DEPS list of each instruction in the corresponding - recovery block. */ + recovery block. */ - rec = RECOVERY_BLOCK (insn); + /* Selective scheduling does not define RECOVERY_BLOCK macro. */ + rec = sel_sched_p () ? NULL : RECOVERY_BLOCK (insn); if (!rec || rec == EXIT_BLOCK_PTR) { prev_first = PREV_INSN (insn); @@ -748,11 +1045,13 @@ priority (rtx insn) do { - FOR_EACH_DEP_LINK (link, INSN_FORW_DEPS (twin)) + sd_iterator_def sd_it; + dep_t dep; + + FOR_EACH_DEP (twin, SD_LIST_FORW, sd_it, dep) { rtx next; int next_priority; - dep_t dep = DEP_LINK_DEP (link); next = DEP_CON (dep); @@ -760,20 +1059,7 @@ priority (rtx insn) { int cost; - /* Critical path is meaningful in block boundaries - only. */ - if (! (*current_sched_info->contributes_to_priority) - (next, insn) - /* If flag COUNT_SPEC_IN_CRITICAL_PATH is set, - then speculative instructions will less likely be - scheduled. That is because the priority of - their producers will increase, and, thus, the - producers will more likely be scheduled, thus, - resolving the dependence. */ - || ((current_sched_info->flags & DO_SPECULATION) - && (DEP_STATUS (dep) & SPECULATIVE) - && !(spec_info->flags - & COUNT_SPEC_IN_CRITICAL_PATH))) + if (!contributes_to_priority_p (dep)) continue; if (twin == insn) @@ -793,13 +1079,21 @@ priority (rtx insn) this_priority = next_priority; } } - + twin = PREV_INSN (twin); } while (twin != prev_first); } + + if (this_priority < 0) + { + gcc_assert (this_priority == -1); + + this_priority = insn_cost (insn); + } + INSN_PRIORITY (insn) = this_priority; - INSN_PRIORITY_KNOWN (insn) = 1; + INSN_PRIORITY_STATUS (insn) = 1; } return INSN_PRIORITY (insn); @@ -815,6 +1109,53 @@ do { if ((N_READY) == 2) \ 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. */ @@ -824,22 +1165,61 @@ rank_for_schedule (const void *x, const void *y) { rtx tmp = *(const rtx *) y; rtx tmp2 = *(const rtx *) x; - dep_link_t link1, link2; + 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; @@ -847,13 +1227,13 @@ rank_for_schedule (const void *x, const void *y) ds1 = TODO_SPEC (tmp) & SPECULATIVE; if (ds1) - dw1 = dep_weak (ds1); + dw1 = ds_weak (ds1); else dw1 = NO_DEP_WEAK; - + ds2 = TODO_SPEC (tmp2) & SPECULATIVE; if (ds2) - dw2 = dep_weak (ds2); + dw2 = ds_weak (ds2); else dw2 = NO_DEP_WEAK; @@ -862,43 +1242,49 @@ rank_for_schedule (const void *x, const void *y) 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; + /* Classify the instructions into three classes: 1) Data dependent on last schedule insn. 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. */ - link1 - = find_link_by_con_in_deps_list (INSN_FORW_DEPS (last_scheduled_insn), - tmp); + dep1 = sd_find_dep_between (last, tmp, true); - if (link1 == NULL || dep_cost (DEP_LINK_DEP (link1)) == 1) + if (dep1 == NULL || dep_cost (dep1) == 1) tmp_class = 3; else if (/* Data dependence. */ - DEP_LINK_KIND (link1) == REG_DEP_TRUE) + DEP_TYPE (dep1) == REG_DEP_TRUE) tmp_class = 1; else tmp_class = 2; - link2 - = find_link_by_con_in_deps_list (INSN_FORW_DEPS (last_scheduled_insn), - tmp2); + dep2 = sd_find_dep_between (last, tmp2, true); - if (link2 == NULL || dep_cost (DEP_LINK_DEP (link2)) == 1) + if (dep2 == NULL || dep_cost (dep2) == 1) tmp2_class = 3; else if (/* Data dependence. */ - DEP_LINK_KIND (link2) == REG_DEP_TRUE) + DEP_TYPE (dep2) == REG_DEP_TRUE) tmp2_class = 1; else tmp2_class = 2; @@ -911,21 +1297,10 @@ rank_for_schedule (const void *x, const void *y) This gives the scheduler more freedom when scheduling later instructions at the expense of added register pressure. */ - link1 = DEPS_LIST_FIRST (INSN_FORW_DEPS (tmp)); - link2 = DEPS_LIST_FIRST (INSN_FORW_DEPS (tmp2)); - - while (link1 != NULL && link2 != NULL) - { - link1 = DEP_LINK_NEXT (link1); - link2 = DEP_LINK_NEXT (link2); - } + val = (dep_list_size (tmp2) - dep_list_size (tmp)); - if (link1 != NULL && link2 == NULL) - /* TMP (Y) has more insns that depend on it. */ - return -1; - if (link1 == NULL && link2 != NULL) - /* TMP2 (X) has more insns that depend on it. */ - return 1; + if (flag_sched_dep_count_heuristic && val != 0) + return val; /* If insns are equally good, sort by INSN_LUID (original insn order), so that we make the sort stable. This minimizes instruction movement, @@ -960,6 +1335,7 @@ queue_insn (rtx insn, int n_cycles) 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; @@ -971,7 +1347,7 @@ queue_insn (rtx insn, int n_cycles) fprintf (sched_dump, "queued for %d cycles.\n", n_cycles); } - + QUEUE_INDEX (insn) = next_q; } @@ -988,7 +1364,7 @@ queue_remove (rtx insn) /* Return a pointer to the bottom of the ready list, i.e. the insn with the lowest priority. */ -HAIFA_INLINE static rtx * +rtx * ready_lastpos (struct ready_list *ready) { gcc_assert (ready->n_ready >= 1); @@ -1027,6 +1403,8 @@ ready_add (struct ready_list *ready, rtx insn, bool first_p) } ready->n_ready++; + if (DEBUG_INSN_P (insn)) + ready->n_debug++; gcc_assert (QUEUE_INDEX (insn) != QUEUE_READY); QUEUE_INDEX (insn) = QUEUE_READY; @@ -1039,10 +1417,12 @@ HAIFA_INLINE static rtx ready_remove_first (struct ready_list *ready) { rtx t; - + 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; @@ -1061,11 +1441,11 @@ ready_remove_first (struct ready_list *ready) insn with the highest priority is 0, and the lowest priority has N_READY - 1. */ -HAIFA_INLINE static rtx +rtx ready_element (struct ready_list *ready, int index) { gcc_assert (ready->n_ready && index < ready->n_ready); - + return ready->vec[ready->first - index]; } @@ -1084,6 +1464,8 @@ ready_remove (struct ready_list *ready, int index) 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; @@ -1108,16 +1490,23 @@ ready_remove_insn (rtx insn) /* Sort the ready list READY by ascending priority, using the SCHED_SORT macro. */ -HAIFA_INLINE static void +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); } /* PREV is an insn that is ready to execute. Adjust its priority if that will help shorten or lengthen register lifetimes as appropriate. Also - provide a hook for the target to tweek itself. */ + provide a hook for the target to tweak itself. */ HAIFA_INLINE static void adjust_priority (rtx prev) @@ -1134,39 +1523,144 @@ adjust_priority (rtx prev) targetm.sched.adjust_priority (prev, INSN_PRIORITY (prev)); } -/* Advance time on one cycle. */ -HAIFA_INLINE static void -advance_one_cycle (void) +/* Advance DFA state STATE on one cycle. */ +void +advance_state (state_t state) { + if (targetm.sched.dfa_pre_advance_cycle) + targetm.sched.dfa_pre_advance_cycle (); + if (targetm.sched.dfa_pre_cycle_insn) - state_transition (curr_state, + state_transition (state, targetm.sched.dfa_pre_cycle_insn ()); - state_transition (curr_state, NULL); - + state_transition (state, NULL); + if (targetm.sched.dfa_post_cycle_insn) - state_transition (curr_state, + state_transition (state, targetm.sched.dfa_post_cycle_insn ()); + + if (targetm.sched.dfa_post_advance_cycle) + targetm.sched.dfa_post_advance_cycle (); +} + +/* Advance time on one cycle. */ +HAIFA_INLINE static void +advance_one_cycle (void) +{ + advance_state (curr_state); + if (sched_verbose >= 6) + fprintf (sched_dump, ";;\tAdvanced a state.\n"); } /* Clock at which the previous instruction was issued. */ static int last_clock_var; -/* 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 - returns necessary cycle advance after issuing the insn (it is not - zero for insns in a schedule group). */ - -static int -schedule_insn (rtx insn) +/* Update register pressure after scheduling INSN. */ +static void +update_register_pressure (rtx insn) { - dep_link_t link; - int advance = 0; - - if (sched_verbose >= 1) - { - char buf[2048]; + 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 + returns necessary cycle advance after issuing the insn (it is not + zero for insns in a schedule group). */ + +static int +schedule_insn (rtx insn) +{ + 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); buf[40] = 0; @@ -1176,17 +1670,57 @@ schedule_insn (rtx insn) 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 (INSN_DEP_COUNT (insn) == 0 - && deps_list_empty_p (INSN_BACK_DEPS (insn))); - free_deps_list (INSN_BACK_DEPS (insn)); + gcc_assert (sd_lists_empty_p (insn, SD_LIST_BACK)); - /* Now we can free INSN_RESOLVED_BACK_DEPS list. */ - delete_deps_list (INSN_RESOLVED_BACK_DEPS (insn)); + /* Reset debug insns invalidated by moving this insn. */ + if (MAY_HAVE_DEBUG_INSNS && !DEBUG_INSN_P (insn)) + for (sd_it = sd_iterator_start (insn, SD_LIST_BACK); + sd_iterator_cond (&sd_it, &dep);) + { + rtx dbg = DEP_PRO (dep); + + gcc_assert (DEBUG_INSN_P (dbg)); + + if (sched_verbose >= 6) + fprintf (sched_dump, ";;\t\tresetting: debug insn %d\n", + INSN_UID (dbg)); + + /* ??? Rather than resetting the debug insn, we might be able + to emit a debug temp before the just-scheduled insn, but + this would involve checking that the expression at the + point of the debug insn is equivalent to the expression + before the just-scheduled insn. They might not be: the + expression in the debug insn may depend on other insns not + yet scheduled that set MEMs, REGs or even other debug + insns. It's not clear that attempting to preserve debug + information in these cases is worth the effort, given how + uncommon these resets are and the likelihood that the debug + temps introduced won't survive the schedule change. */ + INSN_VAR_LOCATION_LOC (dbg) = gen_rtx_UNKNOWN_VAR_LOC (); + df_insn_rescan (dbg); + + /* We delete rather than resolve these deps, otherwise we + crash in sched_free_deps(), because forward deps are + expected to be released before backward deps. */ + sd_delete_dep (sd_it); + } gcc_assert (QUEUE_INDEX (insn) == QUEUE_NOWHERE); QUEUE_INDEX (insn) = QUEUE_SCHEDULED; @@ -1195,33 +1729,35 @@ schedule_insn (rtx insn) if (INSN_TICK (insn) > clock_var) /* INSN has been prematurely moved from the queue to the ready list. This is possible only if following flag is set. */ - gcc_assert (flag_sched_stalled_insns); + gcc_assert (flag_sched_stalled_insns); /* ??? Probably, if INSN is scheduled prematurely, we should leave INSN_TICK untouched. This is a machine-dependent issue, actually. */ INSN_TICK (insn) = clock_var; /* Update dependent instructions. */ - FOR_EACH_DEP_LINK (link, INSN_FORW_DEPS (insn)) + for (sd_it = sd_iterator_start (insn, SD_LIST_FORW); + sd_iterator_cond (&sd_it, &dep);) { - rtx next = DEP_LINK_CON (link); + rtx next = DEP_CON (dep); - /* Resolve the dependence between INSN and NEXT. */ + /* Resolve the dependence between INSN and NEXT. + sd_resolve_dep () moves current dep to another list thus + advancing the iterator. */ + sd_resolve_dep (sd_it); - INSN_DEP_COUNT (next)--; - - move_dep_link (DEP_NODE_BACK (DEP_LINK_NODE (link)), - INSN_RESOLVED_BACK_DEPS (next)); - - gcc_assert ((INSN_DEP_COUNT (next) == 0) - == deps_list_empty_p (INSN_BACK_DEPS (next))); + /* Don't bother trying to mark next as ready if insn is a debug + insn. If insn is the last hard dependency, it will have + already been discounted. */ + if (DEBUG_INSN_P (insn) && !DEBUG_INSN_P (next)) + continue; if (!IS_SPECULATION_BRANCHY_CHECK_P (insn)) { - int effective_cost; - + int effective_cost; + effective_cost = try_ready (next); - + if (effective_cost >= 0 && SCHED_GROUP_P (next) && advance < effective_cost) @@ -1231,11 +1767,23 @@ schedule_insn (rtx insn) /* Check always has only one forward dependence (to the first insn in the recovery block), therefore, this will be executed only once. */ { - gcc_assert (DEP_LINK_NEXT (link) == NULL); + gcc_assert (sd_lists_empty_p (insn, SD_LIST_FORW)); fix_recovery_deps (RECOVERY_BLOCK (insn)); } } + /* This is the place where scheduler doesn't *basically* need backward and + 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 + 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 + need memory until beginning of next region. + Bottom line: Dependencies are removed for all insns in the end of + scheduling the region. */ + /* Annotate the instruction with issue information -- TImode indicates that the instruction is expected not to be able to issue on the same cycle as the previous insn. A machine @@ -1243,7 +1791,8 @@ schedule_insn (rtx insn) 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); @@ -1255,56 +1804,84 @@ schedule_insn (rtx insn) /* Functions for handling of notes. */ -/* Delete notes beginning with INSN and put them in the chain - of notes ended by NOTE_LIST. - Returns the insn following the notes. */ - -static rtx -unlink_other_notes (rtx insn, rtx tail) +/* Add note list that ends on FROM_END to the end of TO_ENDP. */ +void +concat_note_lists (rtx from_end, rtx *to_endp) { - rtx prev = PREV_INSN (insn); + rtx from_start; - while (insn != tail && NOTE_NOT_BB_P (insn)) + /* It's easy when have nothing to concat. */ + if (from_end == NULL) + return; + + /* It's also easy when destination is empty. */ + if (*to_endp == NULL) { - rtx next = NEXT_INSN (insn); - basic_block bb = BLOCK_FOR_INSN (insn); + *to_endp = from_end; + return; + } - /* Delete the note from its current position. */ - if (prev) - NEXT_INSN (prev) = next; - if (next) - PREV_INSN (next) = prev; + from_start = from_end; + while (PREV_INSN (from_start) != NULL) + from_start = PREV_INSN (from_start); - if (bb) - { - /* Basic block can begin with either LABEL or - NOTE_INSN_BASIC_BLOCK. */ - gcc_assert (BB_HEAD (bb) != insn); + PREV_INSN (from_start) = *to_endp; + NEXT_INSN (*to_endp) = from_start; + *to_endp = from_end; +} - /* Check if we are removing last insn in the BB. */ - if (BB_END (bb) == insn) - BB_END (bb) = prev; - } +/* Delete notes between HEAD and TAIL and put them in the chain + of notes ended by NOTE_LIST. */ +void +remove_notes (rtx head, rtx tail) +{ + rtx next_tail, insn, next; + + note_list = 0; + if (head == tail && !INSN_P (head)) + return; + + next_tail = NEXT_INSN (tail); + for (insn = head; insn != next_tail; insn = next) + { + next = NEXT_INSN (insn); + if (!NOTE_P (insn)) + continue; - /* See sched_analyze to see how these are handled. */ - if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG - && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END) + switch (NOTE_KIND (insn)) { - /* Insert the note at the end of the notes list. */ + case NOTE_INSN_BASIC_BLOCK: + continue; + + case NOTE_INSN_EPILOGUE_BEG: + if (insn != tail) + { + remove_insn (insn); + add_reg_note (next, REG_SAVE_NOTE, + GEN_INT (NOTE_INSN_EPILOGUE_BEG)); + break; + } + /* FALLTHRU */ + + default: + remove_insn (insn); + + /* Add the note to list that ends at NOTE_LIST. */ PREV_INSN (insn) = note_list; + NEXT_INSN (insn) = NULL_RTX; if (note_list) NEXT_INSN (note_list) = insn; note_list = insn; + break; } - insn = next; + gcc_assert ((sel_sched_p () || insn != tail) && insn != head); } - return insn; } + /* Return the head and tail pointers of ebb starting at BEG and ending at END. */ - void get_ebb_head_tail (basic_block beg, basic_block end, rtx *headp, rtx *tailp) { @@ -1320,7 +1897,7 @@ 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)) + if (NOTE_P (beg_head) || BOUNDARY_DEBUG_INSN_P (beg_head)) beg_head = NEXT_INSN (beg_head); else break; @@ -1333,7 +1910,7 @@ 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)) + if (NOTE_P (end_tail) || BOUNDARY_DEBUG_INSN_P (end_tail)) end_tail = PREV_INSN (end_tail); else break; @@ -1344,124 +1921,52 @@ get_ebb_head_tail (basic_block beg, basic_block end, rtx *headp, rtx *tailp) /* Return nonzero if there are no real insns in the range [ HEAD, TAIL ]. */ int -no_real_insns_p (rtx head, rtx tail) +no_real_insns_p (const_rtx head, const_rtx tail) { 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 1; } -/* Delete notes between HEAD and TAIL and put them in the chain - of notes ended by NOTE_LIST. */ - -void -rm_other_notes (rtx head, rtx tail) +/* Restore-other-notes: NOTE_LIST is the end of a chain of notes + previously found among the insns. Insert them just before HEAD. */ +rtx +restore_other_notes (rtx head, basic_block head_bb) { - rtx next_tail; - rtx insn; - - note_list = 0; - if (head == tail && (! INSN_P (head))) - return; - - next_tail = NEXT_INSN (tail); - for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) + if (note_list != 0) { - rtx prev; - - /* Farm out notes, and maybe save them in NOTE_LIST. - This is needed to keep the debugger from - getting completely deranged. */ - if (NOTE_NOT_BB_P (insn)) - { - prev = insn; - - insn = unlink_other_notes (insn, next_tail); - - gcc_assert (prev != tail && prev != head && insn != next_tail); - } - } -} - -/* Functions for computation of registers live/usage info. */ + rtx note_head = note_list; -/* 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. */ + if (head) + head_bb = BLOCK_FOR_INSN (head); + else + head = NEXT_INSN (bb_note (head_bb)); -static int -find_set_reg_weight (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))) + while (PREV_INSN (note_head)) { - if (!reg_mentioned_p (SET_DEST (x), SET_SRC (x))) - return 1; - else - return 0; + set_block_for_insn (note_head, head_bb); + note_head = PREV_INSN (note_head); } - return 1; - } - return 0; -} - -/* Calculate INSN_REG_WEIGHT for all insns of a block. */ - -static void -find_insn_reg_weight (basic_block bb) -{ - rtx insn, next_tail, head, tail; + /* In the above cycle we've missed this note. */ + set_block_for_insn (note_head, head_bb); - get_ebb_head_tail (bb, bb, &head, &tail); - next_tail = NEXT_INSN (tail); + PREV_INSN (note_head) = PREV_INSN (head); + NEXT_INSN (PREV_INSN (head)) = note_head; + PREV_INSN (head) = note_list; + NEXT_INSN (note_list) = head; - for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) - find_insn_reg_weight1 (insn); -} + if (BLOCK_FOR_INSN (head) != head_bb) + BB_END (head_bb) = note_list; -/* Calculate INSN_REG_WEIGHT for single instruction. - Separated from find_insn_reg_weight because of need - to initialize new instruction in generate_recovery_code. */ -static void -find_insn_reg_weight1 (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--; + head = note_head; } - - INSN_REG_WEIGHT (insn) = reg_weight; + + return head; } /* Move insns that became ready to fire from queue to ready list. */ @@ -1471,9 +1976,21 @@ queue_to_ready (struct ready_list *ready) { rtx insn; rtx link; + rtx skip_insn; 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); + while (skip_insn && DEBUG_INSN_P (skip_insn)) + skip_insn = next_nonnote_insn (skip_insn); + } + else + skip_insn = NULL_RTX; + /* Add all pending insns that can be scheduled without stalls to the ready list. */ for (link = insn_queue[q_ptr]; link; link = XEXP (link, 1)) @@ -1488,8 +2005,9 @@ queue_to_ready (struct ready_list *ready) /* 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 - && !SCHED_GROUP_P (insn)) + && 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"); @@ -1543,17 +2061,17 @@ queue_to_ready (struct ready_list *ready) } /* Used by early_queue_to_ready. Determines whether it is "ok" to - prematurely move INSN from the queue to the ready list. Currently, - if a target defines the hook 'is_costly_dependence', this function + prematurely move INSN from the queue to the ready list. Currently, + if a target defines the hook 'is_costly_dependence', this function uses the hook to check whether there exist any dependences which are - considered costly by the target, between INSN and other insns that + considered costly by the target, between INSN and other insns that have already been scheduled. Dependences are checked up to Y cycles back, with default Y=1; The flag -fsched-stalled-insns-dep=Y allows - controlling this value. - (Other considerations could be taken into account instead (or in + controlling this value. + (Other considerations could be taken into account instead (or in addition) depending on user flags and target hooks. */ -static bool +static bool ok_for_early_queue_removal (rtx insn) { int n_cycles; @@ -1567,17 +2085,20 @@ ok_for_early_queue_removal (rtx insn) { int cost; + if (prev_insn == current_sched_info->prev_head) + { + prev_insn = NULL; + break; + } + if (!NOTE_P (prev_insn)) { - dep_link_t dep_link; + dep_t dep; - dep_link = (find_link_by_con_in_deps_list - (INSN_FORW_DEPS (prev_insn), insn)); + dep = sd_find_dep_between (prev_insn, insn, true); - if (dep_link) + if (dep != NULL) { - dep_t dep = DEP_LINK_DEP (dep_link); - cost = dep_cost (dep); if (targetm.sched.is_costly_dependence (dep, cost, @@ -1590,9 +2111,9 @@ ok_for_early_queue_removal (rtx insn) break; } - if (!prev_insn) + if (!prev_insn) break; - prev_insn = PREV_INSN (prev_insn); + prev_insn = PREV_INSN (prev_insn); } } @@ -1603,7 +2124,7 @@ ok_for_early_queue_removal (rtx insn) /* Remove insns from the queue, before they become "ready" with respect to FU latency considerations. */ -static int +static int early_queue_to_ready (state_t state, struct ready_list *ready) { rtx insn; @@ -1617,20 +2138,20 @@ early_queue_to_ready (state_t state, struct ready_list *ready) int insns_removed = 0; /* - Flag '-fsched-stalled-insns=X' determines the aggressiveness of this - function: + Flag '-fsched-stalled-insns=X' determines the aggressiveness of this + function: - X == 0: There is no limit on how many queued insns can be removed + X == 0: There is no limit on how many queued insns can be removed prematurely. (flag_sched_stalled_insns = -1). - X >= 1: Only X queued insns can be removed prematurely in each + X >= 1: Only X queued insns can be removed prematurely in each invocation. (flag_sched_stalled_insns = X). Otherwise: Early queue removal is disabled. (flag_sched_stalled_insns = 0) */ - if (! flag_sched_stalled_insns) + if (! flag_sched_stalled_insns) return 0; for (stalls = 0; stalls <= max_insn_queue_index; stalls++) @@ -1649,7 +2170,7 @@ early_queue_to_ready (state_t state, struct ready_list *ready) print_rtl_single (sched_dump, insn); memcpy (temp_state, state, dfa_state_size); - if (recog_memoized (insn) < 0) + if (recog_memoized (insn) < 0) /* non-negative to indicate that it's not ready to avoid infinite Q->R->Q->R... */ cost = 0; @@ -1660,7 +2181,7 @@ early_queue_to_ready (state_t state, struct ready_list *ready) fprintf (sched_dump, "transition cost = %d\n", cost); move_to_ready = false; - if (cost < 0) + if (cost < 0) { move_to_ready = ok_for_early_queue_removal (insn); if (move_to_ready == true) @@ -1669,7 +2190,7 @@ early_queue_to_ready (state_t state, struct ready_list *ready) q_size -= 1; ready_add (ready, insn, false); - if (prev_link) + if (prev_link) XEXP (prev_link, 1) = next_link; else insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = next_link; @@ -1693,11 +2214,11 @@ early_queue_to_ready (state_t state, struct ready_list *ready) link = next_link; } /* while link */ - } /* if link */ + } /* if link */ } /* for stalls.. */ - return insns_removed; + return insns_removed; } @@ -1717,17 +2238,25 @@ debug_ready_list (struct ready_list *ready) 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"); } -/* Search INSN for REG_SAVE_NOTE note pairs for - NOTE_INSN_EHREGION_{BEG,END}; and convert them back into - NOTEs. The REG_SAVE_NOTE note following first one is contains the - saved value for NOTE_BLOCK_NUMBER which is useful for - NOTE_INSN_EH_REGION_{BEG,END} NOTEs. */ - -static void +/* Search INSN for REG_SAVE_NOTE notes and convert them back into insn + NOTEs. This is used for NOTE_INSN_EPILOGUE_BEG, so that sched-ebb + replaces the epilogue note in the correct basic block. */ +void reemit_notes (rtx insn) { rtx note, last = insn; @@ -1736,7 +2265,7 @@ reemit_notes (rtx insn) { 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); @@ -1746,10 +2275,8 @@ reemit_notes (rtx insn) /* Move INSN. Reemit notes if needed. Update CFG, if needed. */ static void -move_insn (rtx insn) +move_insn (rtx insn, rtx last, rtx nt) { - rtx last = last_scheduled_insn; - if (PREV_INSN (insn) != last) { basic_block bb; @@ -1757,9 +2284,9 @@ move_insn (rtx insn) int jump_p = 0; bb = BLOCK_FOR_INSN (insn); - + /* BB_HEAD is either LABEL or NOTE. */ - gcc_assert (BB_HEAD (bb) != insn); + gcc_assert (BB_HEAD (bb) != insn); if (BB_END (bb) == insn) /* If this is last instruction in BB, move end marker one @@ -1769,10 +2296,11 @@ move_insn (rtx insn) jump_p = control_flow_insn_p (insn); gcc_assert (!jump_p - || ((current_sched_info->flags & SCHED_RGN) + || ((common_sched_info->sched_pass_id == SCHED_RGN_PASS) && IS_SPECULATION_BRANCHY_CHECK_P (insn)) - || (current_sched_info->flags & SCHED_EBB)); - + || (common_sched_info->sched_pass_id + == SCHED_EBB_PASS)); + gcc_assert (BLOCK_FOR_INSN (PREV_INSN (insn)) == bb); BB_END (bb) = PREV_INSN (insn); @@ -1783,8 +2311,7 @@ move_insn (rtx insn) if (jump_p) /* We move the block note along with jump. */ { - /* NT is needed for assertion below. */ - rtx nt = current_sched_info->next_tail; + gcc_assert (nt); note = NEXT_INSN (insn); while (NOTE_NOT_BB_P (note) && note != nt) @@ -1794,7 +2321,7 @@ move_insn (rtx insn) && (LABEL_P (note) || BARRIER_P (note))) note = NEXT_INSN (note); - + gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note)); } else @@ -1821,16 +2348,31 @@ move_insn (rtx insn) gcc_assert (BB_END (bb) == last); } - set_block_for_insn (insn, bb); - + df_insn_change_bb (insn, bb); + /* Update BB_END, if needed. */ if (BB_END (bb) == last) - BB_END (bb) = insn; + BB_END (bb) = insn; } - - reemit_notes (insn); - SCHED_GROUP_P (insn) = 0; + 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. */ @@ -1853,7 +2395,10 @@ static struct choice_entry *choice_stack; /* The following variable value is number of essential insns issued on the current cycle. An insn is essential one if it changes the processors state. */ -static int cycle_issued_insns; +int cycle_issued_insns; + +/* This holds the value of the target dfa_lookahead hook. */ +int dfa_lookahead; /* The following variable value is maximal number of tries of issuing insns for the first cycle multipass insn scheduling. We define @@ -1884,43 +2429,119 @@ static int cached_issue_rate = 0; of all instructions in READY. 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. */ -static int -max_issue (struct ready_list *ready, int *index, int max_points) + function is used only for first cycle multipass scheduling. + + PRIVILEGED_N >= 0 + + This function expects recognized insns only. All USEs, + CLOBBERs, etc must be filtered elsewhere. */ +int +max_issue (struct ready_list *ready, int privileged_n, state_t state, + int *index) { - int n, i, all, n_ready, best, delay, tries_num, points = -1; + int n, i, all, n_ready, best, delay, tries_num, max_points; + int more_issue; struct choice_entry *top; rtx insn; + n_ready = ready->n_ready; + gcc_assert (dfa_lookahead >= 1 && privileged_n >= 0 + && privileged_n <= n_ready); + + /* Init MAX_LOOKAHEAD_TRIES. */ + if (cached_first_cycle_multipass_dfa_lookahead != dfa_lookahead) + { + cached_first_cycle_multipass_dfa_lookahead = dfa_lookahead; + max_lookahead_tries = 100; + for (i = 0; i < issue_rate; i++) + max_lookahead_tries *= dfa_lookahead; + } + + /* 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; + } + + /* The number of the issued insns in the best solution. */ best = 0; - memcpy (choice_stack->state, curr_state, dfa_state_size); + top = choice_stack; - top->rest = cached_first_cycle_multipass_dfa_lookahead; + + /* Set initial state of the search. */ + memcpy (top->state, state, dfa_state_size); + top->rest = dfa_lookahead; top->n = 0; - n_ready = ready->n_ready; + + /* Count the number of the insns to search among. */ for (all = i = 0; i < n_ready; i++) if (!ready_try [i]) all++; + + /* I is the index of the insn to try next. */ i = 0; tries_num = 0; for (;;) { - if (top->rest == 0 || i >= n_ready) + 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) { + /* ??? (... || i == n_ready). */ + gcc_assert (i <= n_ready); + if (top == choice_stack) break; - if (best < top - choice_stack && ready_try [0]) + + if (best < top - choice_stack) { - best = top - choice_stack; - *index = choice_stack [1].index; - points = top->n; - if (top->n == max_points || best == all) - break; + if (privileged_n) + { + n = privileged_n; + /* Try to find issued privileged insn. */ + while (n && !ready_try[--n]); + } + + if (/* If all insns are equally good... */ + privileged_n == 0 + /* Or a privileged insn will be issued. */ + || ready_try[n]) + /* Then we have a solution. */ + { + best = top - choice_stack; + /* This is the index of the insn issued first in this + solution. */ + *index = choice_stack [1].index; + if (top->n == max_points || best == all) + break; + } } + + /* Set ready-list index to point to the last insn + ('i++' below will advance it to the next insn). */ i = top->index; + + /* Backtrack. */ ready_try [i] = 0; top--; - memcpy (curr_state, top->state, dfa_state_size); + memcpy (state, top->state, dfa_state_size); } else if (!ready_try [i]) { @@ -1928,73 +2549,98 @@ max_issue (struct ready_list *ready, int *index, int max_points) if (tries_num > max_lookahead_tries) break; insn = ready_element (ready, i); - delay = state_transition (curr_state, insn); + delay = state_transition (state, insn); if (delay < 0) { - if (state_dead_lock_p (curr_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--; + n = top->n; - if (memcmp (top->state, curr_state, dfa_state_size) != 0) + if (memcmp (top->state, state, dfa_state_size) != 0) n += ISSUE_POINTS (insn); + + /* Advance to the next choice_entry. */ top++; - top->rest = cached_first_cycle_multipass_dfa_lookahead; + /* Initialize it. */ + top->rest = dfa_lookahead; top->index = i; top->n = n; - memcpy (top->state, curr_state, dfa_state_size); + memcpy (top->state, state, dfa_state_size); + ready_try [i] = 1; i = -1; } } + + /* Increase ready-list index. */ i++; } - while (top != choice_stack) - { - ready_try [top->index] = 0; - top--; - } - memcpy (curr_state, choice_stack->state, dfa_state_size); - - if (sched_verbose >= 4) - fprintf (sched_dump, ";;\t\tChoosed insn : %s; points: %d/%d\n", - (*current_sched_info->print_insn) (ready_element (ready, *index), - 0), - points, max_points); - + + /* Restore the original state of the DFA. */ + memcpy (state, choice_stack->state, dfa_state_size); + return best; } /* The following function chooses insn from READY and modifies - *N_READY and READY. The following function is used only for first - cycle multipass scheduling. */ - -static rtx -choose_ready (struct ready_list *ready) + READY. The following function is used only for first + cycle multipass scheduling. + Return: + -1 if cycle should be advanced, + 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) { - int lookahead = 0; + int lookahead; + + if (dbg_cnt (sched_insn) == false) + { + rtx insn; + + insn = next_nonnote_insn (last_scheduled_insn); + + if (QUEUE_INDEX (insn) == QUEUE_READY) + /* INSN is in the ready_list. */ + { + ready_remove_insn (insn); + *insn_ptr = insn; + return 0; + } + + /* INSN is in the queue. Advance cycle to move it to the ready list. */ + return -1; + } + + lookahead = 0; 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))) - return ready_remove_first (ready); + 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; + } else { /* Try to choose the better insn. */ int index = 0, i, n; rtx insn; - int more_issue, max_points, try_data = 1, try_control = 1; - - if (cached_first_cycle_multipass_dfa_lookahead != lookahead) - { - cached_first_cycle_multipass_dfa_lookahead = lookahead; - max_lookahead_tries = 100; - for (i = 0; i < issue_rate; i++) - max_lookahead_tries *= lookahead; - } + int try_data = 1, try_control = 1; + ds_t ts; + insn = ready_element (ready, 0); if (INSN_CODE (insn) < 0) - return ready_remove_first (ready); + { + *insn_ptr = ready_remove_first (ready); + return 0; + } if (spec_info && spec_info->flags & (PREFER_NON_DATA_SPEC @@ -2007,16 +2653,16 @@ choose_ready (struct ready_list *ready) x = ready_element (ready, i); s = TODO_SPEC (x); - + if (spec_info->flags & PREFER_NON_DATA_SPEC && !(s & DATA_SPEC)) - { + { try_data = 0; if (!(spec_info->flags & PREFER_NON_CONTROL_SPEC) || !try_control) break; } - + if (spec_info->flags & PREFER_NON_CONTROL_SPEC && !(s & CONTROL_SPEC)) { @@ -2027,40 +2673,73 @@ choose_ready (struct ready_list *ready) } } - if ((!try_data && (TODO_SPEC (insn) & DATA_SPEC)) - || (!try_control && (TODO_SPEC (insn) & CONTROL_SPEC)) - || (targetm.sched.first_cycle_multipass_dfa_lookahead_guard_spec - && !targetm.sched.first_cycle_multipass_dfa_lookahead_guard_spec - (insn))) + ts = TODO_SPEC (insn); + if ((ts & SPECULATIVE) + && (((!try_data && (ts & DATA_SPEC)) + || (!try_control && (ts & CONTROL_SPEC))) + || (targetm.sched.first_cycle_multipass_dfa_lookahead_guard_spec + && !targetm.sched + .first_cycle_multipass_dfa_lookahead_guard_spec (insn)))) /* Discard speculative instruction that stands first in the ready list. */ { change_queue_index (insn, 1); - return 0; + return 1; } - max_points = ISSUE_POINTS (insn); - more_issue = issue_rate - cycle_issued_insns - 1; + ready_try[0] = 0; for (i = 1; i < ready->n_ready; i++) { insn = ready_element (ready, i); + ready_try [i] - = (INSN_CODE (insn) < 0 - || (!try_data && (TODO_SPEC (insn) & DATA_SPEC)) - || (!try_control && (TODO_SPEC (insn) & CONTROL_SPEC)) - || (targetm.sched.first_cycle_multipass_dfa_lookahead_guard - && !targetm.sched.first_cycle_multipass_dfa_lookahead_guard - (insn))); - - if (!ready_try [i] && more_issue-- > 0) - max_points += ISSUE_POINTS (insn); + = ((!try_data && (TODO_SPEC (insn) & DATA_SPEC)) + || (!try_control && (TODO_SPEC (insn) & CONTROL_SPEC))); } - if (max_issue (ready, &index, max_points) == 0) - return ready_remove_first (ready); + /* Let the target filter the search space. */ + for (i = 1; i < ready->n_ready; i++) + if (!ready_try[i]) + { + 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 + in max_issue (). */ + INSN_CODE (insn) < 0 + || (targetm.sched.first_cycle_multipass_dfa_lookahead_guard + && !targetm.sched.first_cycle_multipass_dfa_lookahead_guard + (insn))); + } + + if (max_issue (ready, 1, curr_state, &index) == 0) + { + *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 - return ready_remove (ready, index); + { + if (sched_verbose >= 4) + fprintf (sched_dump, ";;\t\tChosen insn : %s\n", + (*current_sched_info->print_insn) + (ready_element (ready, index), 0)); + + *insn_ptr = ready_remove (ready, index); + return 0; + } } } @@ -2069,9 +2748,8 @@ choose_ready (struct ready_list *ready) region. */ void -schedule_block (basic_block *target_bb, int rgn_n_insns1) +schedule_block (basic_block *target_bb) { - struct ready_list ready; int i, first_cycle_insn_p; int can_issue_more; state_t temp_state = NULL; /* It is used for multipass scheduling. */ @@ -2092,7 +2770,7 @@ schedule_block (basic_block *target_bb, int rgn_n_insns1) gcc_assert (head != tail || INSN_P (head)); - added_recovery_block_p = false; + haifa_recovery_bb_recently_added_p = false; /* Debug info. */ if (sched_verbose) @@ -2100,17 +2778,10 @@ schedule_block (basic_block *target_bb, int rgn_n_insns1) state_reset (curr_state); - /* Allocate the ready list. */ - readyp = &ready; - ready.vec = NULL; - ready_try = NULL; - choice_stack = NULL; - - rgn_n_insns = -1; - extend_ready (rgn_n_insns1 + 1); - + /* 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); @@ -2121,7 +2792,8 @@ schedule_block (basic_block *target_bb, int rgn_n_insns1) /* 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 @@ -2129,25 +2801,27 @@ schedule_block (basic_block *target_bb, int rgn_n_insns1) q_ptr = 0; q_size = 0; - insn_queue = alloca ((max_insn_queue_index + 1) * sizeof (rtx)); + insn_queue = XALLOCAVEC (rtx, max_insn_queue_index + 1); memset (insn_queue, 0, (max_insn_queue_index + 1) * sizeof (rtx)); /* Start just before the beginning of time. */ clock_var = -1; - /* We need queue and ready lists and clock_var be initialized + /* We need queue and ready lists and clock_var be initialized in try_ready () (which is called through init_ready_list ()). */ (*current_sched_info->init_ready_list) (); /* 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; @@ -2159,12 +2833,30 @@ schedule_block (basic_block *target_bb, int rgn_n_insns1) ";;\t\t before reload => truncated to %d insns\n", i); } - /* Delay all insns past it for 1 cycle. */ - while (i < ready.n_ready) - queue_insn (ready_remove (&ready, i), 1); - } + /* Delay all insns past it for 1 cycle. If debug counter is + activated make an exception for the insn right after + last_scheduled_insn. */ + { + rtx skip_insn; - /* Now we can restore basic block notes and maintain precise cfg. */ + if (dbg_cnt (sched_insn) == false) + skip_insn = next_nonnote_insn (last_scheduled_insn); + else + skip_insn = NULL_RTX; + + while (i < ready.n_ready) + { + rtx insn; + + insn = ready_remove (&ready, i); + + if (insn != skip_insn) + queue_insn (insn, 1); + } + } + } + + /* Now we can restore basic block notes and maintain precise cfg. */ restore_bb_notes (*target_bb); last_clock_var = -1; @@ -2212,6 +2904,46 @@ schedule_block (basic_block *target_bb, int rgn_n_insns1) } } + /* 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 @@ -2237,11 +2969,13 @@ schedule_block (basic_block *target_bb, int rgn_n_insns1) 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 - && can_issue_more - && reload_completed) + if (ready.n_ready == 0 + && can_issue_more + && reload_completed) { /* Allow scheduling insns directly from the queue in case there's nothing better to do (ready list is empty) but @@ -2253,7 +2987,8 @@ schedule_block (basic_block *target_bb, int rgn_n_insns1) 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; @@ -2261,13 +2996,30 @@ schedule_block (basic_block *target_bb, int rgn_n_insns1) /* Select and remove the insn from the ready list. */ if (sort_p) { - insn = choose_ready (&ready); - if (!insn) + int res; + + insn = NULL_RTX; + res = choose_ready (&ready, &insn); + + if (res < 0) + /* Finish cycle. */ + break; + if (res > 0) + /* Restart choose_ready (). */ continue; + + gcc_assert (insn != NULL_RTX); } 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, @@ -2279,10 +3031,10 @@ schedule_block (basic_block *target_bb, int rgn_n_insns1) to have the highest priority (so it will be returned by the ready_remove_first call above), we invoke ready_add (&ready, insn, true). - But, still, there is one issue: INSN can be later - discarded by scheduler's front end through + But, still, there is one issue: INSN can be later + discarded by scheduler's front end through current_sched_info->can_schedule_ready_p, hence, won't - be issued next. */ + be issued next. */ { ready_add (&ready, insn, true); break; @@ -2295,7 +3047,7 @@ schedule_block (basic_block *target_bb, int rgn_n_insns1) 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 tryed to be issued on the + /* This is asm insn which is tried to be issued on the cycle not first. Issue it on the next cycle. */ cost = 1; else @@ -2305,6 +3057,8 @@ schedule_block (basic_block *target_bb, int rgn_n_insns1) fatal error for unrecognizable insns. */ cost = 0; } + else if (sched_pressure_p) + cost = 0; else { cost = state_transition (temp_state, insn); @@ -2322,7 +3076,7 @@ schedule_block (basic_block *target_bb, int rgn_n_insns1) advance = cost; break; } - + continue; } @@ -2335,13 +3089,13 @@ schedule_block (basic_block *target_bb, int rgn_n_insns1) continue; } - /* DECISION is made. */ - + /* DECISION is made. */ + if (TODO_SPEC (insn) & SPECULATIVE) generate_recovery_code (insn); - if (control_flow_insn_p (last_scheduled_insn) - /* This is used to to switch basic blocks by request + 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 @@ -2350,7 +3104,7 @@ schedule_block (basic_block *target_bb, int rgn_n_insns1) { *target_bb = current_sched_info->advance_target_bb (*target_bb, 0); - + if (sched_verbose) { rtx x; @@ -2362,14 +3116,15 @@ schedule_block (basic_block *target_bb, int rgn_n_insns1) last_scheduled_insn = bb_note (*target_bb); } - + /* Update counters, etc in the scheduler's front end. */ (*current_sched_info->begin_schedule_ready) (insn, last_scheduled_insn); - - move_insn (insn); + + move_insn (insn, last_scheduled_insn, current_sched_info->next_tail); + reemit_notes (insn); last_scheduled_insn = insn; - + if (memcmp (curr_state, temp_state, dfa_state_size) != 0) { cycle_issued_insns++; @@ -2379,13 +3134,12 @@ schedule_block (basic_block *target_bb, int rgn_n_insns1) 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. */ @@ -2402,6 +3156,44 @@ schedule_block (basic_block *target_bb, int rgn_n_insns1) 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)))) @@ -2425,20 +3217,20 @@ schedule_block (basic_block *target_bb, int rgn_n_insns1) 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); - else + gcc_assert (!q_size && !ready.n_ready && !ready.n_debug); + else { /* We must maintain QUEUE_INDEX between blocks in region. */ for (i = ready.n_ready - 1; i >= 0; i--) { rtx x; - + x = ready_element (&ready, i); QUEUE_INDEX (x) = QUEUE_NOWHERE; TODO_SPEC (x) = (TODO_SPEC (x) & ~SPECULATIVE) | HARD_DEP; } - if (q_size) + if (q_size) for (i = 0; i <= max_insn_queue_index; i++) { rtx link; @@ -2454,8 +3246,11 @@ schedule_block (basic_block *target_bb, int rgn_n_insns1) } } + if (sched_verbose) + fprintf (sched_dump, ";; total time = %d\n", clock_var); + if (!current_sched_info->queue_must_finish_empty - || added_recovery_block_p) + || haifa_recovery_bb_recently_added_p) { /* INSN_TICK (minimum clock tick at which the insn becomes ready) may be not correct for the insn in the subsequent @@ -2467,53 +3262,27 @@ schedule_block (basic_block *target_bb, int rgn_n_insns1) } if (targetm.sched.md_finish) - targetm.sched.md_finish (sched_dump, sched_verbose); + { + targetm.sched.md_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); + } + + if (sched_verbose) + fprintf (sched_dump, ";; new head = %d\n;; new tail = %d\n\n", + INSN_UID (head), INSN_UID (tail)); /* Update head/tail boundaries. */ head = NEXT_INSN (prev_head); tail = last_scheduled_insn; - /* Restore-other-notes: NOTE_LIST is the end of a chain of notes - previously found among the insns. Insert them at the beginning - of the insns. */ - if (note_list != 0) - { - basic_block head_bb = BLOCK_FOR_INSN (head); - rtx note_head = note_list; - - while (PREV_INSN (note_head)) - { - set_block_for_insn (note_head, head_bb); - note_head = PREV_INSN (note_head); - } - /* In the above cycle we've missed this note: */ - set_block_for_insn (note_head, head_bb); - - PREV_INSN (note_head) = PREV_INSN (head); - NEXT_INSN (PREV_INSN (head)) = note_head; - PREV_INSN (head) = note_list; - NEXT_INSN (note_list) = head; - head = note_head; - } - - /* Debugging. */ - if (sched_verbose) - { - fprintf (sched_dump, ";; total time = %d\n;; new head = %d\n", - clock_var, INSN_UID (head)); - fprintf (sched_dump, ";; new tail = %d\n\n", - INSN_UID (tail)); - } + head = restore_other_notes (head, NULL); current_sched_info->head = head; current_sched_info->tail = tail; - - free (ready.vec); - - free (ready_try); - for (i = 0; i <= rgn_n_insns; i++) - free (choice_stack [i].state); - free (choice_stack); } /* Set_priorities: compute priority of each insn in the block. */ @@ -2523,12 +3292,12 @@ set_priorities (rtx head, rtx tail) { rtx insn; int n_insn; - int sched_max_insns_priority = + int sched_max_insns_priority = 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; @@ -2541,9 +3310,10 @@ set_priorities (rtx head, rtx tail) n_insn++; (void) priority (insn); - if (INSN_PRIORITY_KNOWN (insn)) - sched_max_insns_priority = - MAX (sched_max_insns_priority, INSN_PRIORITY (insn)); + gcc_assert (INSN_PRIORITY_KNOWN (insn)); + + sched_max_insns_priority = MAX (sched_max_insns_priority, + INSN_PRIORITY (insn)); } current_sched_info->sched_max_insns_priority = sched_max_insns_priority; @@ -2551,51 +3321,54 @@ set_priorities (rtx head, rtx tail) return n_insn; } -/* Next LUID to assign to an instruction. */ -static int luid; +/* Set dump and sched_verbose for the desired debugging output. If no + dump-file was specified, but -fsched-verbose=N (any N), print to stderr. + For -fsched-verbose=N, N>=10, print everything to stderr. */ +void +setup_sched_dump (void) +{ + sched_verbose = sched_verbose_param; + if (sched_verbose_param == 0 && dump_file) + sched_verbose = 1; + sched_dump = ((sched_verbose_param >= 10 || !dump_file) + ? stderr : dump_file); +} -/* Initialize some global state for the scheduler. */ +/* Initialize some global state for the scheduler. This function works + with the common data shared between all the schedulers. It is called + from the scheduler specific initialization routine. */ void sched_init (void) { - basic_block b; - rtx insn; - int i; - - /* Switch to working copy of sched_info. */ - memcpy (¤t_sched_info_var, current_sched_info, - sizeof (current_sched_info_var)); - current_sched_info = ¤t_sched_info_var; - /* Disable speculative loads in their presence if cc0 defined. */ #ifdef HAVE_cc0 flag_schedule_speculative_load = 0; #endif - /* Set dump and sched_verbose for the desired debugging output. If no - dump-file was specified, but -fsched-verbose=N (any N), print to stderr. - For -fsched-verbose=N, N>=10, print everything to stderr. */ - sched_verbose = sched_verbose_param; - if (sched_verbose_param == 0 && dump_file) - sched_verbose = 1; - sched_dump = ((sched_verbose_param >= 10 || !dump_file) - ? stderr : dump_file); + 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) { spec_info = &spec_info_var; targetm.sched.set_sched_flags (spec_info); - if (current_sched_info->flags & DO_SPECULATION) - spec_info->weakness_cutoff = - (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF) * MAX_DEP_WEAK) / 100; + + if (spec_info->mask != 0) + { + spec_info->data_weakness_cutoff = + (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF) * MAX_DEP_WEAK) / 100; + spec_info->control_weakness_cutoff = + (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF) + * REG_BR_PROB_BASE) / 100; + } else /* So we won't read anything accidentally. */ - spec_info = 0; -#ifdef ENABLE_CHECKING - check_sched_flags (); -#endif + spec_info = NULL; + } else /* So we won't read anything accidentally. */ @@ -2614,18 +3387,10 @@ sched_init (void) cached_first_cycle_multipass_dfa_lookahead = 0; } - old_max_uid = 0; - h_i_d = 0; - extend_h_i_d (); - - for (i = 0; i < old_max_uid; i++) - { - h_i_d[i].cost = -1; - h_i_d[i].todo_spec = HARD_DEP; - h_i_d[i].queue_index = QUEUE_NOWHERE; - h_i_d[i].tick = INVALID_TICK; - h_i_d[i].inter_tick = INVALID_TICK; - } + if (targetm.sched.first_cycle_multipass_dfa_lookahead) + dfa_lookahead = targetm.sched.first_cycle_multipass_dfa_lookahead (); + else + dfa_lookahead = 0; if (targetm.sched.init_dfa_pre_cycle_insn) targetm.sched.init_dfa_pre_cycle_insn (); @@ -2635,71 +3400,110 @@ sched_init (void) dfa_start (); dfa_state_size = state_size (); - curr_state = xmalloc (dfa_state_size); - h_i_d[0].luid = 0; - luid = 1; - FOR_EACH_BB (b) - for (insn = BB_HEAD (b); ; insn = NEXT_INSN (insn)) - { - INSN_LUID (insn) = luid; + init_alias_analysis (); - /* Increment the next luid, unless this is a note. We don't - really need separate IDs for notes and we don't want to - schedule differently depending on whether or not there are - line-number notes, i.e., depending on whether or not we're - generating debugging information. */ - if (!NOTE_P (insn)) - ++luid; + df_set_flags (DF_LR_RUN_DCE); + df_note_add_problem (); - if (insn == BB_END (b)) - break; - } + /* More problems needed for interloop dep calculation in SMS. */ + if (common_sched_info->sched_pass_id == SCHED_SMS_PASS) + { + df_rd_add_problem (); + df_chain_add_problem (DF_DU_CHAIN + DF_UD_CHAIN); + } - init_dependency_caches (luid); + df_analyze (); - init_alias_analysis (); + /* Do not run DCE after reload, as this can kill nops inserted + by bundling. */ + if (reload_completed) + df_clear_flags (DF_LR_RUN_DCE); - old_last_basic_block = 0; - glat_start = 0; - glat_end = 0; - extend_bb (); + regstat_compute_calls_crossed (); - if (current_sched_info->flags & USE_GLAT) - init_glat (); + if (targetm.sched.md_init_global) + targetm.sched.md_init_global (sched_dump, sched_verbose, + get_max_uid () + 1); - /* Compute INSN_REG_WEIGHT for all blocks. We must do this before - removing death notes. */ - FOR_EACH_BB_REVERSE (b) - find_insn_reg_weight (b); + 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); + } - if (targetm.sched.md_init_global) - targetm.sched.md_init_global (sched_dump, sched_verbose, old_max_uid); + curr_state = xmalloc (dfa_state_size); +} - nr_begin_data = nr_begin_control = nr_be_in_data = nr_be_in_control = 0; - before_recovery = 0; +static void haifa_init_only_bb (basic_block, basic_block); + +/* Initialize data structures specific to the Haifa scheduler. */ +void +haifa_sched_init (void) +{ + setup_sched_dump (); + sched_init (); + + if (spec_info != NULL) + { + sched_deps_info->use_deps_list = 1; + sched_deps_info->generate_spec_deps = 1; + } + + /* Initialize luids, dependency caches, target and h_i_d for the + whole function. */ + { + bb_vec_t bbs = VEC_alloc (basic_block, heap, n_basic_blocks); + basic_block bb; + + sched_init_bbs (); + + FOR_EACH_BB (bb) + VEC_quick_push (basic_block, bbs, bb); + sched_init_luids (bbs, NULL, NULL, NULL); + sched_deps_init (true); + sched_extend_target (); + haifa_init_h_i_d (bbs, NULL, NULL, NULL); + + VEC_free (basic_block, heap, bbs); + } + + sched_init_only_bb = haifa_init_only_bb; + sched_split_block = sched_split_block_1; + sched_create_empty_bb = sched_create_empty_bb_1; + haifa_recovery_bb_ever_added_p = false; #ifdef ENABLE_CHECKING - /* This is used preferably for finding bugs in check_cfg () itself. */ + /* This is used preferably for finding bugs in check_cfg () itself. + We must call sched_bbs_init () before check_cfg () because check_cfg () + assumes that the last insn in the last bb has a non-null successor. */ check_cfg (0, 0); #endif -} -/* Free global data used during insn scheduling. */ + nr_begin_data = nr_begin_control = nr_be_in_data = nr_be_in_control = 0; + before_recovery = 0; + after_recovery = 0; +} +/* Finish work with the data specific to the Haifa scheduler. */ void -sched_finish (void) +haifa_sched_finish (void) { - free (h_i_d); - free (curr_state); - dfa_finish (); - free_dependency_caches (); - end_alias_analysis (); - free_glat (); + sched_create_empty_bb = NULL; + sched_split_block = NULL; + sched_init_only_bb = NULL; - if (targetm.sched.md_finish_global) - targetm.sched.md_finish_global (sched_dump, sched_verbose); - if (spec_info && spec_info->dump) { char c = reload_completed ? 'a' : 'b'; @@ -2721,13 +3525,44 @@ sched_finish (void) c, nr_be_in_control); } + /* Finalize h_i_d, dependency caches, and luids for the whole + function. Target will be finalized in md_global_finish (). */ + sched_deps_finish (); + sched_finish_luids (); + current_sched_info = NULL; + sched_finish (); +} + +/* Free global data used during insn scheduling. This function works with + the common data shared between the schedulers. */ + +void +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) + targetm.sched.md_finish_global (sched_dump, sched_verbose); + + end_alias_analysis (); + + regstat_free_calls_crossed (); + + dfa_finish (); + #ifdef ENABLE_CHECKING /* After reload ia64 backend clobbers CFG, so can't check anything. */ if (!reload_completed) check_cfg (0, 0); #endif - - current_sched_info = NULL; } /* Fix INSN_TICKs of the instructions in the current block as well as @@ -2738,10 +3573,14 @@ fix_inter_tick (rtx head, rtx tail) { /* Set of instructions with corrected INSN_TICK. */ bitmap_head processed; + /* ??? It is doubtful if we should assume that cycle advance happens on + basic block boundaries. Basically insns that are unconditionally ready + on the start of the block are more preferable then those which have + a one cycle dependency over insn from the previous block. */ int next_clock = clock_var + 1; bitmap_initialize (&processed, 0); - + /* Iterates over scheduled instructions and fix their INSN_TICKs and INSN_TICKs of dependent instructions, so that INSN_TICKs are consistent across different blocks. */ @@ -2750,28 +3589,29 @@ fix_inter_tick (rtx head, rtx tail) if (INSN_P (head)) { int tick; - dep_link_t link; - + sd_iterator_def sd_it; + dep_t dep; + tick = INSN_TICK (head); gcc_assert (tick >= MIN_TICK); - + /* Fix INSN_TICK of instruction from just scheduled block. */ if (!bitmap_bit_p (&processed, INSN_LUID (head))) { bitmap_set_bit (&processed, INSN_LUID (head)); tick -= next_clock; - + if (tick < MIN_TICK) tick = MIN_TICK; - - INSN_TICK (head) = tick; + + INSN_TICK (head) = tick; } - - FOR_EACH_DEP_LINK (link, INSN_FORW_DEPS (head)) + + FOR_EACH_DEP (head, SD_LIST_RES_FORW, sd_it, dep) { rtx next; - - next = DEP_LINK_CON (link); + + next = DEP_CON (dep); tick = INSN_TICK (next); if (tick != INVALID_TICK @@ -2782,15 +3622,15 @@ fix_inter_tick (rtx head, rtx tail) { bitmap_set_bit (&processed, INSN_LUID (next)); tick -= next_clock; - + if (tick < MIN_TICK) tick = MIN_TICK; - + if (tick > INTER_TICK (next)) INTER_TICK (next) = tick; else tick = INTER_TICK (next); - + INSN_TICK (next) = tick; } } @@ -2798,7 +3638,9 @@ fix_inter_tick (rtx head, rtx tail) } bitmap_clear (&processed); } - + +static int haifa_speculate_insn (rtx, ds_t, rtx *); + /* Check if NEXT is ready to be added to the ready or queue list. If "yes", add it to the proper list. Returns: @@ -2807,9 +3649,8 @@ fix_inter_tick (rtx head, rtx tail) 0 < N - queued for N cycles. */ int try_ready (rtx next) -{ +{ ds_t old_ts, *ts; - dep_link_t link; ts = &TODO_SPEC (next); old_ts = *ts; @@ -2817,45 +3658,57 @@ try_ready (rtx next) gcc_assert (!(old_ts & ~(SPECULATIVE | HARD_DEP)) && ((old_ts & HARD_DEP) || (old_ts & SPECULATIVE))); - - if (!(current_sched_info->flags & DO_SPECULATION)) + + if (sd_lists_empty_p (next, SD_LIST_BACK)) + /* NEXT has all its dependencies resolved. */ { - if (deps_list_empty_p (INSN_BACK_DEPS (next))) - *ts &= ~HARD_DEP; + /* Remove HARD_DEP bit from NEXT's status. */ + *ts &= ~HARD_DEP; + + if (current_sched_info->flags & DO_SPECULATION) + /* Remove all speculative bits from NEXT's status. */ + *ts &= ~SPECULATIVE; } else { + /* One of the NEXT's dependencies has been resolved. + Recalculate NEXT's status. */ + *ts &= ~SPECULATIVE & ~HARD_DEP; - link = DEPS_LIST_FIRST (INSN_BACK_DEPS (next)); + if (sd_lists_empty_p (next, SD_LIST_HARD_BACK)) + /* Now we've got NEXT with speculative deps only. + 1. Look at the deps to see what we have to do. + 2. Check if we can do 'todo'. */ + { + sd_iterator_def sd_it; + dep_t dep; + bool first_p = true; - if (link != NULL) - { - ds_t ds = DEP_LINK_STATUS (link) & SPECULATIVE; - - /* Backward dependencies of the insn are maintained sorted. - So if DEP_STATUS of the first dep is SPECULATIVE, - than all other deps are speculative too. */ - if (ds != 0) - { - /* Now we've got NEXT with speculative deps only. - 1. Look at the deps to see what we have to do. - 2. Check if we can do 'todo'. */ - *ts = ds; - - while ((link = DEP_LINK_NEXT (link)) != NULL) + FOR_EACH_DEP (next, SD_LIST_BACK, sd_it, dep) + { + ds_t ds = DEP_STATUS (dep) & SPECULATIVE; + + if (DEBUG_INSN_P (DEP_PRO (dep)) + && !DEBUG_INSN_P (next)) + continue; + + if (first_p) { - ds = DEP_LINK_STATUS (link) & SPECULATIVE; - *ts = ds_merge (*ts, ds); - } + first_p = false; - if (dep_weak (*ts) < spec_info->weakness_cutoff) - /* Too few points. */ - *ts = (*ts & ~SPECULATIVE) | HARD_DEP; + *ts = ds; + } + else + *ts = ds_merge (*ts, ds); } - else - *ts |= HARD_DEP; - } + + if (ds_weak (*ts) < spec_info->data_weakness_cutoff) + /* Too few points. */ + *ts = (*ts & ~SPECULATIVE) | HARD_DEP; + } + else + *ts |= HARD_DEP; } if (*ts & HARD_DEP) @@ -2881,11 +3734,11 @@ try_ready (rtx next) { int res; rtx new_pat; - + gcc_assert ((*ts & SPECULATIVE) && !(*ts & ~SPECULATIVE)); - - res = speculate_insn (next, *ts, &new_pat); - + + res = haifa_speculate_insn (next, *ts, &new_pat); + switch (res) { case -1: @@ -2894,62 +3747,62 @@ try_ready (rtx next) so we won't reanalyze anything. */ *ts = (*ts & ~SPECULATIVE) | HARD_DEP; break; - + case 0: /* We follow the rule, that every speculative insn has non-null ORIG_PAT. */ if (!ORIG_PAT (next)) ORIG_PAT (next) = PATTERN (next); break; - - case 1: + + case 1: if (!ORIG_PAT (next)) /* If we gonna to overwrite the original pattern of insn, save it. */ ORIG_PAT (next) = PATTERN (next); - - change_pattern (next, new_pat); + + haifa_change_pattern (next, new_pat); break; - + default: gcc_unreachable (); } } - + /* We need to restore pattern only if (*ts == 0), because otherwise it is either correct (*ts & SPECULATIVE), or we simply don't care (*ts & HARD_DEP). */ - + gcc_assert (!ORIG_PAT (next) || !IS_SPECULATION_BRANCHY_CHECK_P (next)); - + if (*ts & HARD_DEP) { /* We can't assert (QUEUE_INDEX (next) == QUEUE_NOWHERE) here because control-speculative NEXT could have been discarded by sched-rgn.c (the same case as when discarded by can_schedule_ready_p ()). */ /*gcc_assert (QUEUE_INDEX (next) == QUEUE_NOWHERE);*/ - + change_queue_index (next, QUEUE_NOWHERE); return -1; } else if (!(*ts & BEGIN_SPEC) && ORIG_PAT (next) && !IS_SPECULATION_CHECK_P (next)) - /* We should change pattern of every previously speculative + /* We should change pattern of every previously speculative instruction - and we determine if NEXT was speculative by using ORIG_PAT field. Except one case - speculation checks have ORIG_PAT pat too, so skip them. */ { - change_pattern (next, ORIG_PAT (next)); + haifa_change_pattern (next, ORIG_PAT (next)); ORIG_PAT (next) = 0; } if (sched_verbose >= 2) - { + { int s = TODO_SPEC (next); - + fprintf (sched_dump, ";;\t\tdependencies resolved: insn %s", (*current_sched_info->print_insn) (next, 0)); - + if (spec_info && spec_info->dump) { if (s & BEGIN_DATA) @@ -2961,10 +3814,10 @@ try_ready (rtx next) } fprintf (sched_dump, "\n"); - } - + } + adjust_priority (next); - + return fix_tick_ready (next); } @@ -2974,10 +3827,11 @@ fix_tick_ready (rtx next) { int tick, delay; - if (!deps_list_empty_p (INSN_RESOLVED_BACK_DEPS (next))) + if (!sd_lists_empty_p (next, SD_LIST_RES_BACK)) { int full_p; - dep_link_t link; + sd_iterator_def sd_it; + dep_t dep; tick = INSN_TICK (next); /* if tick is not equal to INVALID_TICK, then update @@ -2985,12 +3839,11 @@ fix_tick_ready (rtx next) cost. Otherwise, recalculate from scratch. */ full_p = (tick == INVALID_TICK); - FOR_EACH_DEP_LINK (link, INSN_RESOLVED_BACK_DEPS (next)) - { - dep_t dep = DEP_LINK_DEP (link); + FOR_EACH_DEP (next, SD_LIST_RES_BACK, sd_it, dep) + { rtx pro = DEP_PRO (dep); int tick1; - + gcc_assert (INSN_TICK (pro) >= MIN_TICK); tick1 = INSN_TICK (pro) + dep_cost (dep); @@ -3007,7 +3860,7 @@ fix_tick_ready (rtx next) 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); @@ -3023,10 +3876,10 @@ change_queue_index (rtx next, int delay) { int i = QUEUE_INDEX (next); - gcc_assert (QUEUE_NOWHERE <= delay && delay <= max_insn_queue_index + gcc_assert (QUEUE_NOWHERE <= delay && delay <= max_insn_queue_index && delay != 0); gcc_assert (i != QUEUE_SCHEDULED); - + if ((delay > 0 && NEXT_Q_AFTER (q_ptr, delay) == i) || (delay < 0 && delay == i)) /* We have nothing to do. */ @@ -3037,18 +3890,18 @@ change_queue_index (rtx next, int delay) ready_remove_insn (next); else if (i >= 0) queue_remove (next); - + /* Add it to the proper place. */ if (delay == QUEUE_READY) ready_add (readyp, next, false); else if (delay >= 1) queue_insn (next, delay); - + if (sched_verbose >= 2) - { + { fprintf (sched_dump, ";;\t\ttick updated: insn %s", (*current_sched_info->print_insn) (next, 0)); - + if (delay == QUEUE_READY) fprintf (sched_dump, " into ready\n"); else if (delay >= 1) @@ -3058,89 +3911,70 @@ change_queue_index (rtx next, int delay) } } -/* Extend H_I_D data. */ -static void -extend_h_i_d (void) -{ - /* We use LUID 0 for the fake insn (UID 0) which holds dependencies for - pseudos which do not cross calls. */ - int new_max_uid = get_max_uid () + 1; - - h_i_d = xrecalloc (h_i_d, new_max_uid, old_max_uid, sizeof (*h_i_d)); - old_max_uid = new_max_uid; - - if (targetm.sched.h_i_d_extended) - targetm.sched.h_i_d_extended (); -} +static int sched_ready_n_insns = -1; -/* Extend READY, READY_TRY and CHOICE_STACK arrays. - N_NEW_INSNS is the number of additional elements to allocate. */ -static void -extend_ready (int n_new_insns) +/* Initialize per region data structures. */ +void +sched_extend_ready_list (int new_sched_ready_n_insns) { int i; - readyp->veclen = rgn_n_insns + n_new_insns + 1 + issue_rate; - readyp->vec = XRESIZEVEC (rtx, readyp->vec, readyp->veclen); - - ready_try = xrecalloc (ready_try, rgn_n_insns + n_new_insns + 1, - rgn_n_insns + 1, sizeof (char)); + if (sched_ready_n_insns == -1) + /* At the first call we need to initialize one more choice_stack + entry. */ + { + i = 0; + sched_ready_n_insns = 0; + } + else + i = sched_ready_n_insns + 1; + + ready.veclen = new_sched_ready_n_insns + issue_rate; + ready.vec = XRESIZEVEC (rtx, ready.vec, ready.veclen); + + gcc_assert (new_sched_ready_n_insns >= sched_ready_n_insns); - rgn_n_insns += n_new_insns; + ready_try = (char *) xrecalloc (ready_try, new_sched_ready_n_insns, + sched_ready_n_insns, sizeof (*ready_try)); + /* We allocate +1 element to save initial state in the choice_stack[0] + entry. */ choice_stack = XRESIZEVEC (struct choice_entry, choice_stack, - rgn_n_insns + 1); + new_sched_ready_n_insns + 1); - for (i = rgn_n_insns; n_new_insns--; i--) + for (; i <= new_sched_ready_n_insns; i++) choice_stack[i].state = xmalloc (dfa_state_size); + + sched_ready_n_insns = new_sched_ready_n_insns; } -/* Extend global scheduler structures (those, that live across calls to - schedule_block) to include information about just emitted INSN. */ -static void -extend_global (rtx insn) +/* Free per region data structures. */ +void +sched_finish_ready_list (void) { - gcc_assert (INSN_P (insn)); - /* These structures have scheduler scope. */ - extend_h_i_d (); - init_h_i_d (insn); + int i; - extend_dependency_caches (1, 0); -} + free (ready.vec); + ready.vec = NULL; + ready.veclen = 0; -/* Extends global and local scheduler structures to include information - about just emitted INSN. */ -static void -extend_all (rtx insn) -{ - extend_global (insn); - - /* These structures have block scope. */ - extend_ready (1); - - (*current_sched_info->add_remove_insn) (insn, 0); + free (ready_try); + ready_try = NULL; + + for (i = 0; i <= sched_ready_n_insns; i++) + free (choice_stack [i].state); + free (choice_stack); + choice_stack = NULL; + + sched_ready_n_insns = -1; } -/* Initialize h_i_d entry of the new INSN with default values. - Values, that are not explicitly initialized here, hold zero. */ -static void -init_h_i_d (rtx insn) +static int +haifa_luid_for_non_insn (rtx x) { - INSN_LUID (insn) = luid++; - INSN_COST (insn) = -1; - TODO_SPEC (insn) = HARD_DEP; - QUEUE_INDEX (insn) = QUEUE_NOWHERE; - INSN_TICK (insn) = INVALID_TICK; - INTER_TICK (insn) = INVALID_TICK; - find_insn_reg_weight1 (insn); + gcc_assert (NOTE_P (x) || LABEL_P (x)); - /* These two lists will be freed in schedule_insn (). */ - INSN_BACK_DEPS (insn) = create_deps_list (false); - INSN_RESOLVED_BACK_DEPS (insn) = create_deps_list (false); - - /* This one should be allocated on the obstack because it should live till - the scheduling ends. */ - INSN_FORW_DEPS (insn) = create_deps_list (true); + return 0; } /* Generates recovery code for INSN. */ @@ -3149,10 +3983,10 @@ generate_recovery_code (rtx insn) { if (TODO_SPEC (insn) & BEGIN_SPEC) begin_speculative_block (insn); - + /* Here we have insn with no dependencies to instructions other then CHECK_SPEC ones. */ - + if (TODO_SPEC (insn) & BE_IN_SPEC) add_to_speculative_block (insn); } @@ -3161,18 +3995,19 @@ generate_recovery_code (rtx insn) Tries to add speculative dependencies of type FS between instructions in deps_list L and TWIN. */ static void -process_insn_forw_deps_be_in_spec (deps_list_t l, rtx twin, ds_t fs) +process_insn_forw_deps_be_in_spec (rtx insn, rtx twin, ds_t fs) { - dep_link_t link; + sd_iterator_def sd_it; + dep_t dep; - FOR_EACH_DEP_LINK (link, l) + FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep) { ds_t ds; rtx consumer; - consumer = DEP_LINK_CON (link); + consumer = DEP_CON (dep); - ds = DEP_LINK_STATUS (link); + ds = DEP_STATUS (dep); if (/* If we want to create speculative dep. */ fs @@ -3190,16 +4025,30 @@ process_insn_forw_deps_be_in_spec (deps_list_t l, rtx twin, ds_t fs) it can be removed from the ready (or queue) list only due to backend decision. Hence we can't let the probability of the speculative dep to decrease. */ - dep_weak (ds) <= dep_weak (fs)) - /* Transform it to be in speculative. */ - ds = (ds & ~BEGIN_SPEC) | fs; + ds_weak (ds) <= ds_weak (fs)) + { + ds_t new_ds; + + new_ds = (ds & ~BEGIN_SPEC) | fs; + + if (/* consumer can 'be in speculative'. */ + sched_insn_is_legitimate_for_speculation_p (consumer, + new_ds)) + /* Transform it to be in speculative. */ + ds = new_ds; + } } else /* Mark the dep as 'be in speculative'. */ ds |= fs; } - add_back_forw_dep (consumer, twin, DEP_LINK_KIND (link), ds); + { + dep_def _new_dep, *new_dep = &_new_dep; + + init_dep_1 (new_dep, twin, consumer, DEP_TYPE (dep), ds); + sd_add_dep (new_dep, false); + } } } @@ -3208,7 +4057,7 @@ static void begin_speculative_block (rtx insn) { if (TODO_SPEC (insn) & BEGIN_DATA) - nr_begin_data++; + nr_begin_data++; if (TODO_SPEC (insn) & BEGIN_CONTROL) nr_begin_control++; @@ -3217,13 +4066,17 @@ begin_speculative_block (rtx insn) TODO_SPEC (insn) &= ~BEGIN_SPEC; } +static void haifa_init_insn (rtx); + /* Generates recovery code for BE_IN speculative INSN. */ static void add_to_speculative_block (rtx insn) { ds_t ts; - dep_link_t link; + sd_iterator_def sd_it; + dep_t dep; rtx twins = NULL; + rtx_vec_t priorities_roots; ts = TODO_SPEC (insn); gcc_assert (!(ts & ~BE_IN_SPEC)); @@ -3235,53 +4088,56 @@ add_to_speculative_block (rtx insn) TODO_SPEC (insn) &= ~BE_IN_SPEC; gcc_assert (!TODO_SPEC (insn)); - + DONE_SPEC (insn) |= ts; /* First we convert all simple checks to branchy. */ - for (link = DEPS_LIST_FIRST (INSN_BACK_DEPS (insn)); link != NULL;) + for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK); + sd_iterator_cond (&sd_it, &dep);) { - rtx check = DEP_LINK_PRO (link); + rtx check = DEP_PRO (dep); if (IS_SPECULATION_SIMPLE_CHECK_P (check)) { create_check_block_twin (check, true); /* Restart search. */ - link = DEPS_LIST_FIRST (INSN_BACK_DEPS (insn)); + sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK); } else /* Continue search. */ - link = DEP_LINK_NEXT (link); + sd_iterator_next (&sd_it); } - clear_priorities (insn); - - do + priorities_roots = NULL; + clear_priorities (insn, &priorities_roots); + + while (1) { - dep_link_t link; rtx check, twin; basic_block rec; - link = DEPS_LIST_FIRST (INSN_BACK_DEPS (insn)); + /* Get the first backward dependency of INSN. */ + sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK); + if (!sd_iterator_cond (&sd_it, &dep)) + /* INSN has no backward dependencies left. */ + break; - gcc_assert ((DEP_LINK_STATUS (link) & BEGIN_SPEC) == 0 - && (DEP_LINK_STATUS (link) & BE_IN_SPEC) != 0 - && (DEP_LINK_STATUS (link) & DEP_TYPES) == DEP_TRUE); + gcc_assert ((DEP_STATUS (dep) & BEGIN_SPEC) == 0 + && (DEP_STATUS (dep) & BE_IN_SPEC) != 0 + && (DEP_STATUS (dep) & DEP_TYPES) == DEP_TRUE); - check = DEP_LINK_PRO (link); + check = DEP_PRO (dep); gcc_assert (!IS_SPECULATION_CHECK_P (check) && !ORIG_PAT (check) && QUEUE_INDEX (check) == QUEUE_NOWHERE); - + rec = BLOCK_FOR_INSN (check); - - twin = emit_insn_before (copy_rtx (PATTERN (insn)), BB_END (rec)); - extend_global (twin); - copy_deps_list_change_con (INSN_RESOLVED_BACK_DEPS (twin), - INSN_RESOLVED_BACK_DEPS (insn), - twin); + twin = emit_insn_before (copy_insn (PATTERN (insn)), BB_END (rec)); + haifa_init_insn (twin); + + sd_copy_back_deps (twin, insn, true); if (sched_verbose && spec_info->dump) /* INSN_BB (insn) isn't determined for twin insns yet. @@ -3293,47 +4149,38 @@ add_to_speculative_block (rtx insn) /* Add dependences between TWIN and all appropriate instructions from REC. */ - do - { - add_back_forw_dep (twin, check, REG_DEP_TRUE, DEP_TRUE); - - do - { - link = DEP_LINK_NEXT (link); - - if (link != NULL) - { - check = DEP_LINK_PRO (link); - if (BLOCK_FOR_INSN (check) == rec) - break; - } - else - break; + FOR_EACH_DEP (insn, SD_LIST_SPEC_BACK, sd_it, dep) + { + rtx pro = DEP_PRO (dep); + + gcc_assert (DEP_TYPE (dep) == REG_DEP_TRUE); + + /* INSN might have dependencies from the instructions from + several recovery blocks. At this iteration we process those + producers that reside in REC. */ + if (BLOCK_FOR_INSN (pro) == rec) + { + dep_def _new_dep, *new_dep = &_new_dep; + + init_dep (new_dep, pro, twin, REG_DEP_TRUE); + sd_add_dep (new_dep, false); } - while (1); } - while (link != NULL); - process_insn_forw_deps_be_in_spec (INSN_FORW_DEPS (insn), twin, ts); + process_insn_forw_deps_be_in_spec (insn, twin, ts); /* Remove all dependencies between INSN and insns in REC. */ - for (link = DEPS_LIST_FIRST (INSN_BACK_DEPS (insn)); link != NULL;) + for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK); + sd_iterator_cond (&sd_it, &dep);) { - check = DEP_LINK_PRO (link); + rtx pro = DEP_PRO (dep); - if (BLOCK_FOR_INSN (check) == rec) - { - delete_back_forw_dep (link); - - /* Restart search. */ - link = DEPS_LIST_FIRST (INSN_BACK_DEPS (insn)); - } + if (BLOCK_FOR_INSN (pro) == rec) + sd_delete_dep (sd_it); else - /* Continue search. */ - link = DEP_LINK_NEXT (link); + sd_iterator_next (&sd_it); } } - while (!deps_list_empty_p (INSN_BACK_DEPS (insn))); /* We couldn't have added the dependencies between INSN and TWINS earlier because that would make TWINS appear in the INSN_BACK_DEPS (INSN). */ @@ -3342,13 +4189,21 @@ add_to_speculative_block (rtx insn) rtx twin; twin = XEXP (twins, 0); - calc_priorities (twin); - add_back_forw_dep (twin, insn, REG_DEP_OUTPUT, DEP_OUTPUT); + + { + dep_def _new_dep, *new_dep = &_new_dep; + + init_dep (new_dep, insn, twin, REG_DEP_OUTPUT); + sd_add_dep (new_dep, false); + } twin = XEXP (twins, 1); free_INSN_LIST_node (twins); - twins = twin; + twins = twin; } + + calc_priorities (priorities_roots); + VEC_free (rtx, heap, priorities_roots); } /* Extends and fills with zeros (only the new part) array pointed to by P. */ @@ -3361,44 +4216,9 @@ xrecalloc (void *p, size_t new_nmemb, size_t old_nmemb, size_t size) return p; } -/* Return the probability of speculation success for the speculation - status DS. */ -static dw_t -dep_weak (ds_t ds) -{ - ds_t res = 1, dt; - int n = 0; - - dt = FIRST_SPEC_TYPE; - do - { - if (ds & dt) - { - res *= (ds_t) get_dep_weak (ds, dt); - n++; - } - - if (dt == LAST_SPEC_TYPE) - break; - dt <<= SPEC_TYPE_SHIFT; - } - while (1); - - gcc_assert (n); - while (--n) - res /= MAX_DEP_WEAK; - - if (res < MIN_DEP_WEAK) - res = MIN_DEP_WEAK; - - gcc_assert (res <= MAX_DEP_WEAK); - - return (dw_t) res; -} - /* Helper function. Find fallthru edge from PRED. */ -static edge +edge find_fallthru_edge (basic_block pred) { edge e; @@ -3430,9 +4250,37 @@ find_fallthru_edge (basic_block pred) return NULL; } +/* Extend per basic block data structures. */ +static void +sched_extend_bb (void) +{ + rtx insn; + + /* The following is done to keep current_sched_info->next_tail non null. */ + insn = BB_END (EXIT_BLOCK_PTR->prev_bb); + if (NEXT_INSN (insn) == 0 + || (!NOTE_P (insn) + && !LABEL_P (insn) + /* Don't emit a NOTE if it would end up before a BARRIER. */ + && !BARRIER_P (NEXT_INSN (insn)))) + { + rtx note = emit_note_after (NOTE_INSN_DELETED, insn); + /* Make insn appear outside BB. */ + set_block_for_insn (note, NULL); + BB_END (EXIT_BLOCK_PTR->prev_bb) = insn; + } +} + +/* Init per basic block data structures. */ +void +sched_init_bbs (void) +{ + sched_extend_bb (); +} + /* Initialize BEFORE_RECOVERY variable. */ static void -init_before_recovery (void) +init_before_recovery (basic_block *before_recovery_ptr) { basic_block last; edge e; @@ -3442,19 +4290,33 @@ init_before_recovery (void) if (e) { - /* We create two basic blocks: + /* We create two basic blocks: 1. Single instruction block is inserted right after E->SRC - and has jump to + and has jump to 2. Empty block right before EXIT_BLOCK. Between these two blocks recovery blocks will be emitted. */ basic_block single, empty; rtx x, label; - single = create_empty_bb (last); - empty = create_empty_bb (single); + /* If the fallthrough edge to exit we've found is from the block we've + created before, don't do anything more. */ + if (last == after_recovery) + return; + + adding_bb_to_current_region_p = false; + + single = sched_create_empty_bb (last); + empty = sched_create_empty_bb (single); - single->count = last->count; + /* Add new blocks to the root loop. */ + if (current_loops != NULL) + { + add_bb_to_loop (single, VEC_index (loop_p, current_loops->larray, 0)); + add_bb_to_loop (empty, VEC_index (loop_p, current_loops->larray, 0)); + } + + single->count = last->count; empty->count = last->count; single->frequency = last->frequency; empty->frequency = last->frequency; @@ -3470,36 +4332,42 @@ init_before_recovery (void) x = emit_jump_insn_after (gen_jump (label), BB_END (single)); JUMP_LABEL (x) = label; LABEL_NUSES (label)++; - extend_global (x); - + haifa_init_insn (x); + emit_barrier_after (x); - add_block (empty, 0); - add_block (single, 0); + sched_init_only_bb (empty, NULL); + sched_init_only_bb (single, NULL); + sched_extend_bb (); + adding_bb_to_current_region_p = true; before_recovery = single; + after_recovery = empty; + + if (before_recovery_ptr) + *before_recovery_ptr = before_recovery; if (sched_verbose >= 2 && spec_info->dump) fprintf (spec_info->dump, - ";;\t\tFixed fallthru to EXIT : %d->>%d->%d->>EXIT\n", - last->index, single->index, empty->index); + ";;\t\tFixed fallthru to EXIT : %d->>%d->%d->>EXIT\n", + last->index, single->index, empty->index); } else before_recovery = last; } /* Returns new recovery block. */ -static basic_block -create_recovery_block (void) +basic_block +sched_create_recovery_block (basic_block *before_recovery_ptr) { rtx label; rtx barrier; basic_block rec; - - added_recovery_block_p = true; - if (!before_recovery) - init_before_recovery (); + haifa_recovery_bb_recently_added_p = true; + haifa_recovery_bb_ever_added_p = true; + + init_before_recovery (before_recovery_ptr); barrier = get_last_bb_insn (before_recovery); gcc_assert (BARRIER_P (barrier)); @@ -3508,21 +4376,62 @@ create_recovery_block (void) rec = create_basic_block (label, label, before_recovery); - /* Recovery block always end with an unconditional jump. */ + /* A recovery block always ends with an unconditional jump. */ emit_barrier_after (BB_END (rec)); if (BB_PARTITION (before_recovery) != BB_UNPARTITIONED) BB_SET_PARTITION (rec, BB_COLD_PARTITION); - - if (sched_verbose && spec_info->dump) + + if (sched_verbose && spec_info->dump) fprintf (spec_info->dump, ";;\t\tGenerated recovery block rec%d\n", rec->index); - before_recovery = rec; - return rec; } +/* Create edges: FIRST_BB -> REC; FIRST_BB -> SECOND_BB; REC -> SECOND_BB + and emit necessary jumps. */ +void +sched_create_recovery_edges (basic_block first_bb, basic_block rec, + basic_block second_bb) +{ + rtx label; + rtx jump; + int edge_flags; + + /* This is fixing of incoming edge. */ + /* ??? Which other flags should be specified? */ + if (BB_PARTITION (first_bb) != BB_PARTITION (rec)) + /* Partition type is the same, if it is "unpartitioned". */ + edge_flags = EDGE_CROSSING; + else + edge_flags = 0; + + make_edge (first_bb, rec, edge_flags); + label = block_label (second_bb); + jump = emit_jump_insn_after (gen_jump (label), BB_END (rec)); + JUMP_LABEL (jump) = label; + LABEL_NUSES (label)++; + + if (BB_PARTITION (second_bb) != BB_PARTITION (rec)) + /* Partition type is the same, if it is "unpartitioned". */ + { + /* 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. */ + add_reg_note (jump, REG_CROSSING_JUMP, NULL_RTX); + } + edge_flags = EDGE_CROSSING; + } + else + edge_flags = 0; + + make_single_succ_edge (rec, second_bb, edge_flags); +} + /* This function creates recovery code for INSN. If MUTATE_P is nonzero, INSN is a simple check, that should be converted to branchy one. */ static void @@ -3530,33 +4439,45 @@ create_check_block_twin (rtx insn, bool mutate_p) { basic_block rec; rtx label, check, twin; - dep_link_t link; ds_t fs; + sd_iterator_def sd_it; + dep_t dep; + dep_def _new_dep, *new_dep = &_new_dep; + ds_t todo_spec; + + gcc_assert (ORIG_PAT (insn) != NULL_RTX); - gcc_assert (ORIG_PAT (insn) - && (!mutate_p - || (IS_SPECULATION_SIMPLE_CHECK_P (insn) - && !(TODO_SPEC (insn) & SPECULATIVE)))); + if (!mutate_p) + todo_spec = TODO_SPEC (insn); + else + { + gcc_assert (IS_SPECULATION_SIMPLE_CHECK_P (insn) + && (TODO_SPEC (insn) & SPECULATIVE) == 0); + + todo_spec = CHECK_SPEC (insn); + } + + 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 = create_recovery_block (); + rec = sched_create_recovery_block (NULL); label = BB_HEAD (rec); } else { rec = EXIT_BLOCK_PTR; - label = 0; + label = NULL_RTX; } /* Emit CHECK. */ - check = targetm.sched.gen_check (insn, label, mutate_p); + check = targetm.sched.gen_spec_check (insn, label, todo_spec); if (rec != EXIT_BLOCK_PTR) { /* To have mem_reg alive at the beginning of second_bb, - we emit check BEFORE insn, so insn after splitting + we emit check BEFORE insn, so insn after splitting insn will be at the beginning of second_bb, which will provide us with the correct life information. */ check = emit_jump_insn_before (check, insn); @@ -3567,7 +4488,15 @@ create_check_block_twin (rtx insn, bool mutate_p) check = emit_insn_before (check, insn); /* Extend data structures. */ - extend_all (check); + haifa_init_insn (check); + + /* CHECK is being added to current region. Extend ready list. */ + gcc_assert (sched_ready_n_insns != -1); + sched_extend_ready_list (sched_ready_n_insns + 1); + + if (current_sched_info->add_remove_insn) + current_sched_info->add_remove_insn (insn, 0); + RECOVERY_BLOCK (check) = rec; if (sched_verbose && spec_info->dump) @@ -3580,18 +4509,21 @@ create_check_block_twin (rtx insn, bool mutate_p) in the recovery block). */ if (rec != EXIT_BLOCK_PTR) { - FOR_EACH_DEP_LINK (link, INSN_RESOLVED_BACK_DEPS (insn)) - if ((DEP_LINK_STATUS (link) & DEP_OUTPUT) != 0) + sd_iterator_def sd_it; + dep_t dep; + + FOR_EACH_DEP (insn, SD_LIST_RES_BACK, sd_it, dep) + if ((DEP_STATUS (dep) & DEP_OUTPUT) != 0) { - struct _dep _dep, *dep = &_dep; + struct _dep _dep2, *dep2 = &_dep2; - init_dep (dep, DEP_LINK_PRO (link), check, REG_DEP_TRUE); + init_dep (dep2, DEP_PRO (dep), check, REG_DEP_TRUE); - add_back_dep_to_deps_list (INSN_RESOLVED_BACK_DEPS (check), dep); + sd_add_dep (dep2, true); } twin = emit_insn_after (ORIG_PAT (insn), BB_END (rec)); - extend_global (twin); + haifa_init_insn (twin); if (sched_verbose && spec_info->dump) /* INSN_BB (insn) isn't determined for twin insns yet. @@ -3608,82 +4540,42 @@ create_check_block_twin (rtx insn, bool mutate_p) (TRUE | OUTPUT). */ } - copy_deps_list_change_con (INSN_RESOLVED_BACK_DEPS (twin), - INSN_RESOLVED_BACK_DEPS (insn), - twin); + /* Copy all resolved back dependencies of INSN to TWIN. This will + provide correct value for INSN_TICK (TWIN). */ + sd_copy_back_deps (twin, insn, true); if (rec != EXIT_BLOCK_PTR) /* In case of branchy check, fix CFG. */ { basic_block first_bb, second_bb; rtx jump; - edge e; - int edge_flags; first_bb = BLOCK_FOR_INSN (check); - e = split_block (first_bb, check); - /* split_block emits note if *check == BB_END. Probably it - is better to rip that note off. */ - gcc_assert (e->src == first_bb); - second_bb = e->dest; - - /* This is fixing of incoming edge. */ - /* ??? Which other flags should be specified? */ - if (BB_PARTITION (first_bb) != BB_PARTITION (rec)) - /* Partition type is the same, if it is "unpartitioned". */ - edge_flags = EDGE_CROSSING; - else - edge_flags = 0; - - e = make_edge (first_bb, rec, edge_flags); - - add_block (second_bb, first_bb); - - gcc_assert (NOTE_INSN_BASIC_BLOCK_P (BB_HEAD (second_bb))); - label = block_label (second_bb); - jump = emit_jump_insn_after (gen_jump (label), BB_END (rec)); - JUMP_LABEL (jump) = label; - LABEL_NUSES (label)++; - extend_global (jump); + second_bb = sched_split_block (first_bb, check); - if (BB_PARTITION (second_bb) != BB_PARTITION (rec)) - /* Partition type is the same, if it is "unpartitioned". */ - { - /* Rewritten from cfgrtl.c. */ - if (flag_reorder_blocks_and_partition - && targetm.have_named_sections - /*&& !any_condjump_p (jump)*/) - /* any_condjump_p (jump) == false. - 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)); - } - edge_flags = EDGE_CROSSING; - } - else - edge_flags = 0; - - make_single_succ_edge (rec, second_bb, edge_flags); - - add_block (rec, EXIT_BLOCK_PTR); + sched_create_recovery_edges (first_bb, rec, second_bb); + + sched_init_only_bb (second_bb, first_bb); + sched_init_only_bb (rec, EXIT_BLOCK_PTR); + + jump = BB_END (rec); + haifa_init_insn (jump); } - /* Move backward dependences from INSN to CHECK and + /* Move backward dependences from INSN to CHECK and move forward dependences from INSN to TWIN. */ - FOR_EACH_DEP_LINK (link, INSN_BACK_DEPS (insn)) + + /* First, create dependencies between INSN's producers and CHECK & TWIN. */ + FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep) { - rtx pro = DEP_LINK_PRO (link); - enum reg_note dk = DEP_LINK_KIND (link); + rtx pro = DEP_PRO (dep); ds_t ds; /* If BEGIN_DATA: [insn ~~TRUE~~> producer]: check --TRUE--> producer ??? or ANTI ??? twin --TRUE--> producer twin --ANTI--> check - + If BEGIN_CONTROL: [insn ~~ANTI~~> producer]: check --ANTI--> producer twin --ANTI--> producer @@ -3692,9 +4584,9 @@ create_check_block_twin (rtx insn, bool mutate_p) If BE_IN_SPEC: [insn ~~TRUE~~> producer]: check ~~TRUE~~> producer twin ~~TRUE~~> producer - twin --ANTI--> check */ + twin --ANTI--> check */ - ds = DEP_LINK_STATUS (link); + ds = DEP_STATUS (dep); if (ds & BEGIN_SPEC) { @@ -3702,54 +4594,57 @@ create_check_block_twin (rtx insn, bool mutate_p) ds &= ~BEGIN_SPEC; } + init_dep_1 (new_dep, pro, check, DEP_TYPE (dep), ds); + sd_add_dep (new_dep, false); + if (rec != EXIT_BLOCK_PTR) { - add_back_forw_dep (check, pro, dk, ds); - add_back_forw_dep (twin, pro, dk, ds); - } - else - add_back_forw_dep (check, pro, dk, ds); + DEP_CON (new_dep) = twin; + sd_add_dep (new_dep, false); + } } - for (link = DEPS_LIST_FIRST (INSN_BACK_DEPS (insn)); link != NULL;) - if ((DEP_LINK_STATUS (link) & BEGIN_SPEC) - || mutate_p) - /* We can delete this dep only if we totally overcome it with - BEGIN_SPECULATION. */ - { - delete_back_forw_dep (link); - - /* Restart search. */ - link = DEPS_LIST_FIRST (INSN_BACK_DEPS (insn)); - } - else - /* Continue search. */ - link = DEP_LINK_NEXT (link); + /* Second, remove backward dependencies of INSN. */ + for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK); + sd_iterator_cond (&sd_it, &dep);) + { + if ((DEP_STATUS (dep) & BEGIN_SPEC) + || mutate_p) + /* We can delete this dep because we overcome it with + BEGIN_SPECULATION. */ + sd_delete_dep (sd_it); + else + sd_iterator_next (&sd_it); + } + /* Future Speculations. Determine what BE_IN speculations will be like. */ fs = 0; /* Fields (DONE_SPEC (x) & BEGIN_SPEC) and CHECK_SPEC (x) are set only here. */ - + gcc_assert (!DONE_SPEC (insn)); - + if (!mutate_p) - { + { ds_t ts = TODO_SPEC (insn); DONE_SPEC (insn) = ts & BEGIN_SPEC; CHECK_SPEC (check) = ts & BEGIN_SPEC; + /* Luckiness of future speculations solely depends upon initial + BEGIN speculation. */ if (ts & BEGIN_DATA) fs = set_dep_weak (fs, BE_IN_DATA, get_dep_weak (ts, BEGIN_DATA)); if (ts & BEGIN_CONTROL) - fs = set_dep_weak (fs, BE_IN_CONTROL, get_dep_weak (ts, BEGIN_CONTROL)); + fs = set_dep_weak (fs, BE_IN_CONTROL, + get_dep_weak (ts, BEGIN_CONTROL)); } else CHECK_SPEC (check) = CHECK_SPEC (insn); /* Future speculations: call the helper. */ - process_insn_forw_deps_be_in_spec (INSN_FORW_DEPS (insn), twin, fs); + process_insn_forw_deps_be_in_spec (insn, twin, fs); if (rec != EXIT_BLOCK_PTR) { @@ -3759,42 +4654,55 @@ create_check_block_twin (rtx insn, bool mutate_p) if (!mutate_p) { - add_back_forw_dep (check, insn, REG_DEP_TRUE, DEP_TRUE); - add_back_forw_dep (twin, insn, REG_DEP_OUTPUT, DEP_OUTPUT); + init_dep (new_dep, insn, check, REG_DEP_TRUE); + sd_add_dep (new_dep, false); + + init_dep (new_dep, insn, twin, REG_DEP_OUTPUT); + sd_add_dep (new_dep, false); } else { - dep_link_t link; - - if (spec_info->dump) + if (spec_info->dump) fprintf (spec_info->dump, ";;\t\tRemoved simple check : %s\n", (*current_sched_info->print_insn) (insn, 0)); - /* Remove all forward dependencies of the INSN. */ - link = DEPS_LIST_FIRST (INSN_FORW_DEPS (insn)); - while (link != NULL) - { - delete_back_forw_dep (link); - link = DEPS_LIST_FIRST (INSN_FORW_DEPS (insn)); - } + /* Remove all dependencies of the INSN. */ + { + sd_it = sd_iterator_start (insn, (SD_LIST_FORW + | SD_LIST_BACK + | SD_LIST_RES_BACK)); + while (sd_iterator_cond (&sd_it, &dep)) + sd_delete_dep (sd_it); + } + /* If former check (INSN) already was moved to the ready (or queue) + list, add new check (CHECK) there too. */ if (QUEUE_INDEX (insn) != QUEUE_NOWHERE) try_ready (check); + /* Remove old check from instruction stream and free its + data. */ sched_remove_insn (insn); } - add_back_forw_dep (twin, check, REG_DEP_ANTI, DEP_ANTI); + init_dep (new_dep, check, twin, REG_DEP_ANTI); + sd_add_dep (new_dep, false); } else - add_back_forw_dep (check, insn, REG_DEP_TRUE, DEP_TRUE | DEP_OUTPUT); + { + init_dep_1 (new_dep, insn, check, REG_DEP_TRUE, DEP_TRUE | DEP_OUTPUT); + sd_add_dep (new_dep, false); + } if (!mutate_p) /* Fix priorities. If MUTATE_P is nonzero, this is not necessary, because it'll be done later in add_to_speculative_block. */ { - clear_priorities (twin); - calc_priorities (twin); + rtx_vec_t priorities_roots = NULL; + + clear_priorities (twin, &priorities_roots); + calc_priorities (priorities_roots); + VEC_free (rtx, heap, priorities_roots); } } @@ -3804,13 +4712,12 @@ create_check_block_twin (rtx insn, bool mutate_p) static void fix_recovery_deps (basic_block rec) { - dep_link_t link; rtx note, insn, jump, ready_list = 0; bitmap_head in_ready; - rtx link1; + rtx link; bitmap_initialize (&in_ready, 0); - + /* NOTE - a basic block note. */ note = NEXT_INSN (BB_HEAD (rec)); gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note)); @@ -3819,35 +4726,33 @@ fix_recovery_deps (basic_block rec) insn = PREV_INSN (insn); do - { - for (link = DEPS_LIST_FIRST (INSN_FORW_DEPS (insn)); link != NULL;) - { - rtx consumer; + { + sd_iterator_def sd_it; + dep_t dep; - consumer = DEP_LINK_CON (link); + for (sd_it = sd_iterator_start (insn, SD_LIST_FORW); + sd_iterator_cond (&sd_it, &dep);) + { + rtx consumer = DEP_CON (dep); if (BLOCK_FOR_INSN (consumer) != rec) { - delete_back_forw_dep (link); + 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)); } - - /* Restart search. */ - link = DEPS_LIST_FIRST (INSN_FORW_DEPS (insn)); } else { - gcc_assert ((DEP_LINK_STATUS (link) & DEP_TYPES) == DEP_TRUE); + gcc_assert ((DEP_STATUS (dep) & DEP_TYPES) == DEP_TRUE); - /* Continue search. */ - link = DEP_LINK_NEXT (link); + sd_iterator_next (&sd_it); } } - + insn = PREV_INSN (insn); } while (insn != note); @@ -3855,66 +4760,77 @@ fix_recovery_deps (basic_block rec) bitmap_clear (&in_ready); /* Try to add instructions to the ready or queue list. */ - for (link1 = ready_list; link1; link1 = XEXP (link1, 1)) - try_ready (XEXP (link1, 0)); + for (link = ready_list; link; link = XEXP (link, 1)) + try_ready (XEXP (link, 0)); free_INSN_LIST_list (&ready_list); /* Fixing jump's dependences. */ insn = BB_HEAD (rec); jump = BB_END (rec); - + gcc_assert (LABEL_P (insn)); insn = NEXT_INSN (insn); - + gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn)); add_jump_dependencies (insn, jump); } -/* Changes pattern of the INSN to NEW_PAT. */ -static void -change_pattern (rtx insn, rtx new_pat) +/* Change pattern of INSN to NEW_PAT. */ +void +sched_change_pattern (rtx insn, rtx new_pat) { int t; t = validate_change (insn, &PATTERN (insn), new_pat, 0); gcc_assert (t); + dfa_clear_single_insn_cache (insn); +} + +/* Change pattern of INSN to NEW_PAT. Invalidate cached haifa + instruction data. */ +static void +haifa_change_pattern (rtx insn, rtx new_pat) +{ + sched_change_pattern (insn, new_pat); + /* Invalidate INSN_COST, so it'll be recalculated. */ INSN_COST (insn) = -1; /* Invalidate INSN_TICK, so it'll be recalculated. */ INSN_TICK (insn) = INVALID_TICK; - dfa_clear_single_insn_cache (insn); } - /* -1 - can't speculate, 0 - for speculation with REQUEST mode it is OK to use current instruction pattern, 1 - need to change pattern for *NEW_PAT to be speculative. */ -static int -speculate_insn (rtx insn, ds_t request, rtx *new_pat) +int +sched_speculate_insn (rtx insn, ds_t request, rtx *new_pat) { gcc_assert (current_sched_info->flags & DO_SPECULATION - && (request & SPECULATIVE)); + && (request & SPECULATIVE) + && sched_insn_is_legitimate_for_speculation_p (insn, request)); - if (!NONJUMP_INSN_P (insn) - || HAS_INTERNAL_DEP (insn) - || SCHED_GROUP_P (insn) - || side_effects_p (PATTERN (insn)) - || (request & spec_info->mask) != request) + if ((request & spec_info->mask) != request) return -1; - - gcc_assert (!IS_SPECULATION_CHECK_P (insn)); - - if (request & BE_IN_SPEC) - { - if (may_trap_p (PATTERN (insn))) - return -1; - - if (!(request & BEGIN_SPEC)) - return 0; - } - return targetm.sched.speculate_insn (insn, request & BEGIN_SPEC, new_pat); + if (request & BE_IN_SPEC + && !(request & BEGIN_SPEC)) + return 0; + + return targetm.sched.speculate_insn (insn, request, new_pat); +} + +static int +haifa_speculate_insn (rtx insn, ds_t request, rtx *new_pat) +{ + gcc_assert (sched_deps_info->generate_spec_deps + && !IS_SPECULATION_CHECK_P (insn)); + + if (HAS_INTERNAL_DEP (insn) + || SCHED_GROUP_P (insn)) + return -1; + + return sched_speculate_insn (insn, request, new_pat); } /* Print some information about block BB, which starts with HEAD and @@ -3953,7 +4869,7 @@ unlink_bb_notes (basic_block first, basic_block last) if (first == last) return; - bb_header = xmalloc (last_basic_block * sizeof (*bb_header)); + bb_header = XNEWVEC (rtx, last_basic_block); /* Make a sentinel. */ if (last->next_bb != EXIT_BLOCK_PTR) @@ -3968,7 +4884,7 @@ unlink_bb_notes (basic_block first, basic_block last) if (LABEL_P (label)) note = NEXT_INSN (label); else - note = label; + note = label; gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note)); prev = PREV_INSN (label); @@ -3982,7 +4898,7 @@ unlink_bb_notes (basic_block first, basic_block last) if (last == first) break; - + last = last->prev_bb; } while (1); @@ -3997,14 +4913,14 @@ restore_bb_notes (basic_block first) return; /* We DON'T unlink basic block notes of the first block in the ebb. */ - first = first->next_bb; + first = first->next_bb; /* Remember: FIRST is actually a second basic block in the ebb. */ while (first != EXIT_BLOCK_PTR && bb_header[first->index]) { rtx prev, label, note, next; - + label = bb_header[first->index]; prev = PREV_INSN (label); next = NEXT_INSN (prev); @@ -4012,7 +4928,7 @@ restore_bb_notes (basic_block first) if (LABEL_P (label)) note = NEXT_INSN (label); else - note = label; + note = label; gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note)); bb_header[first->index] = 0; @@ -4020,7 +4936,7 @@ restore_bb_notes (basic_block first) NEXT_INSN (prev) = label; NEXT_INSN (note) = next; PREV_INSN (next) = note; - + first = first->next_bb; } @@ -4028,58 +4944,6 @@ restore_bb_notes (basic_block first) bb_header = 0; } -/* Extend per basic block data structures of the scheduler. - If BB is NULL, initialize structures for the whole CFG. - Otherwise, initialize them for the just created BB. */ -static void -extend_bb (void) -{ - rtx insn; - - old_last_basic_block = last_basic_block; - - if (current_sched_info->flags & USE_GLAT) - { - glat_start = xrealloc (glat_start, - last_basic_block * sizeof (*glat_start)); - glat_end = xrealloc (glat_end, last_basic_block * sizeof (*glat_end)); - } - - /* The following is done to keep current_sched_info->next_tail non null. */ - - insn = BB_END (EXIT_BLOCK_PTR->prev_bb); - if (NEXT_INSN (insn) == 0 - || (!NOTE_P (insn) - && !LABEL_P (insn) - /* Don't emit a NOTE if it would end up before a BARRIER. */ - && !BARRIER_P (NEXT_INSN (insn)))) - { - emit_note_after (NOTE_INSN_DELETED, insn); - /* Make insn to appear outside BB. */ - BB_END (EXIT_BLOCK_PTR->prev_bb) = insn; - } -} - -/* Add a basic block BB to extended basic block EBB. - If EBB is EXIT_BLOCK_PTR, then BB is recovery block. - If EBB is NULL, then BB should be a new region. */ -void -add_block (basic_block bb, basic_block ebb) -{ - gcc_assert (current_sched_info->flags & DETACH_LIFE_INFO - && bb->il.rtl->global_live_at_start == 0 - && bb->il.rtl->global_live_at_end == 0); - - extend_bb (); - - glat_start[bb->index] = 0; - glat_end[bb->index] = 0; - - if (current_sched_info->add_block) - /* This changes only data structures of the front-end. */ - current_sched_info->add_block (bb, ebb); -} - /* Helper function. Fix CFG after both in- and inter-block movement of control_flow_insn_p JUMP. */ @@ -4092,9 +4956,9 @@ fix_jump_move (rtx jump) jump_bb = BLOCK_FOR_INSN (jump); jump_bb_next = jump_bb->next_bb; - gcc_assert (current_sched_info->flags & SCHED_EBB + gcc_assert (common_sched_info->sched_pass_id == SCHED_EBB_PASS || IS_SPECULATION_BRANCHY_CHECK_P (jump)); - + if (!NOTE_INSN_BASIC_BLOCK_P (BB_END (jump_bb_next))) /* if jump_bb_next is not empty. */ BB_END (jump_bb) = BB_END (jump_bb_next); @@ -4123,9 +4987,9 @@ move_block_after_check (rtx jump) bb = BLOCK_FOR_INSN (PREV_INSN (jump)); jump_bb = BLOCK_FOR_INSN (jump); jump_bb_next = jump_bb->next_bb; - + update_bb_for_insn (jump_bb); - + gcc_assert (IS_SPECULATION_CHECK_P (jump) || IS_SPECULATION_CHECK_P (BB_END (jump_bb_next))); @@ -4137,10 +5001,11 @@ move_block_after_check (rtx jump) move_succs (&(jump_bb->succs), bb); move_succs (&(jump_bb_next->succs), jump_bb); move_succs (&t, jump_bb_next); - - if (current_sched_info->fix_recovery_cfg) - current_sched_info->fix_recovery_cfg - (bb->index, jump_bb->index, jump_bb_next->index); + + df_mark_solutions_dirty (); + + common_sched_info->fix_recovery_cfg + (bb->index, jump_bb->index, jump_bb_next->index); } /* Helper function for move_block_after_check. @@ -4162,161 +5027,62 @@ move_succs (VEC(edge,gc) **succsp, basic_block to) *succsp = 0; } -/* Initialize GLAT (global_live_at_{start, end}) structures. - GLAT structures are used to substitute global_live_{start, end} - regsets during scheduling. This is necessary to use such functions as - split_block (), as they assume consistency of register live information. */ -static void -init_glat (void) -{ - basic_block bb; - - FOR_ALL_BB (bb) - init_glat1 (bb); -} - -/* Helper function for init_glat. */ -static void -init_glat1 (basic_block bb) -{ - gcc_assert (bb->il.rtl->global_live_at_start != 0 - && bb->il.rtl->global_live_at_end != 0); - - glat_start[bb->index] = bb->il.rtl->global_live_at_start; - glat_end[bb->index] = bb->il.rtl->global_live_at_end; - - if (current_sched_info->flags & DETACH_LIFE_INFO) - { - bb->il.rtl->global_live_at_start = 0; - bb->il.rtl->global_live_at_end = 0; - } -} - -/* Attach reg_live_info back to basic blocks. - Also save regsets, that should not have been changed during scheduling, - for checking purposes (see check_reg_live). */ -void -attach_life_info (void) -{ - basic_block bb; - - FOR_ALL_BB (bb) - attach_life_info1 (bb); -} - -/* Helper function for attach_life_info. */ -static void -attach_life_info1 (basic_block bb) -{ - gcc_assert (bb->il.rtl->global_live_at_start == 0 - && bb->il.rtl->global_live_at_end == 0); - - if (glat_start[bb->index]) - { - gcc_assert (glat_end[bb->index]); - - bb->il.rtl->global_live_at_start = glat_start[bb->index]; - bb->il.rtl->global_live_at_end = glat_end[bb->index]; - - /* Make them NULL, so they won't be freed in free_glat. */ - glat_start[bb->index] = 0; - glat_end[bb->index] = 0; - -#ifdef ENABLE_CHECKING - if (bb->index < NUM_FIXED_BLOCKS - || current_sched_info->region_head_or_leaf_p (bb, 0)) - { - glat_start[bb->index] = ALLOC_REG_SET (®_obstack); - COPY_REG_SET (glat_start[bb->index], - bb->il.rtl->global_live_at_start); - } - - if (bb->index < NUM_FIXED_BLOCKS - || current_sched_info->region_head_or_leaf_p (bb, 1)) - { - glat_end[bb->index] = ALLOC_REG_SET (®_obstack); - COPY_REG_SET (glat_end[bb->index], bb->il.rtl->global_live_at_end); - } -#endif - } - else - { - gcc_assert (!glat_end[bb->index]); - - bb->il.rtl->global_live_at_start = ALLOC_REG_SET (®_obstack); - bb->il.rtl->global_live_at_end = ALLOC_REG_SET (®_obstack); - } -} - -/* Free GLAT information. */ -static void -free_glat (void) -{ -#ifdef ENABLE_CHECKING - if (current_sched_info->flags & DETACH_LIFE_INFO) - { - basic_block bb; - - FOR_ALL_BB (bb) - { - if (glat_start[bb->index]) - FREE_REG_SET (glat_start[bb->index]); - if (glat_end[bb->index]) - FREE_REG_SET (glat_end[bb->index]); - } - } -#endif - - free (glat_start); - free (glat_end); -} - /* Remove INSN from the instruction stream. INSN should have any dependencies. */ static void sched_remove_insn (rtx insn) { + sd_finish_insn (insn); + change_queue_index (insn, QUEUE_NOWHERE); current_sched_info->add_remove_insn (insn, 1); remove_insn (insn); } -/* Clear priorities of all instructions, that are - forward dependent on INSN. */ +/* Clear priorities of all instructions, that are forward dependent on INSN. + Store in vector pointed to by ROOTS_PTR insns on which priority () should + be invoked to initialize all cleared priorities. */ static void -clear_priorities (rtx insn) +clear_priorities (rtx insn, rtx_vec_t *roots_ptr) { - dep_link_t link; + sd_iterator_def sd_it; + dep_t dep; + bool insn_is_root_p = true; - FOR_EACH_DEP_LINK (link, INSN_BACK_DEPS (insn)) + gcc_assert (QUEUE_INDEX (insn) != QUEUE_SCHEDULED); + + FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep) { - rtx pro = DEP_LINK_PRO (link); + rtx pro = DEP_PRO (dep); - if (INSN_PRIORITY_KNOWN (pro)) + if (INSN_PRIORITY_STATUS (pro) >= 0 + && QUEUE_INDEX (insn) != QUEUE_SCHEDULED) { - INSN_PRIORITY_KNOWN (pro) = 0; - clear_priorities (pro); + /* If DEP doesn't contribute to priority then INSN itself should + be added to priority roots. */ + if (contributes_to_priority_p (dep)) + insn_is_root_p = false; + + INSN_PRIORITY_STATUS (pro) = -1; + clear_priorities (pro, roots_ptr); } } + + if (insn_is_root_p) + VEC_safe_push (rtx, heap, *roots_ptr, insn); } /* Recompute priorities of instructions, whose priorities might have been - changed due to changes in INSN. */ + changed. ROOTS is a vector of instructions whose priority computation will + trigger initialization of all cleared priorities. */ static void -calc_priorities (rtx insn) +calc_priorities (rtx_vec_t roots) { - dep_link_t link; - - FOR_EACH_DEP_LINK (link, INSN_BACK_DEPS (insn)) - { - rtx pro = DEP_LINK_PRO (link); + int i; + rtx insn; - if (!INSN_PRIORITY_KNOWN (pro)) - { - priority (pro); - calc_priorities (pro); - } - } + for (i = 0; VEC_iterate (rtx, roots, i, insn); i++) + priority (insn); } @@ -4330,13 +5096,18 @@ add_jump_dependencies (rtx insn, rtx jump) insn = NEXT_INSN (insn); if (insn == jump) break; - - if (deps_list_empty_p (INSN_FORW_DEPS (insn))) - add_back_forw_dep (jump, insn, REG_DEP_ANTI, DEP_ANTI); + + if (dep_list_size (insn) == 0) + { + dep_def _new_dep, *new_dep = &_new_dep; + + init_dep (new_dep, insn, jump, REG_DEP_ANTI); + sd_add_dep (new_dep, false); + } } while (1); - gcc_assert (!deps_list_empty_p (INSN_BACK_DEPS (jump))); + gcc_assert (!sd_lists_empty_p (jump, SD_LIST_BACK)); } /* Return the NOTE_INSN_BASIC_BLOCK of BB. */ @@ -4354,36 +5125,6 @@ bb_note (basic_block bb) } #ifdef ENABLE_CHECKING -extern void debug_spec_status (ds_t); - -/* Dump information about the dependence status S. */ -void -debug_spec_status (ds_t s) -{ - FILE *f = stderr; - - if (s & BEGIN_DATA) - fprintf (f, "BEGIN_DATA: %d; ", get_dep_weak (s, BEGIN_DATA)); - if (s & BE_IN_DATA) - fprintf (f, "BE_IN_DATA: %d; ", get_dep_weak (s, BE_IN_DATA)); - if (s & BEGIN_CONTROL) - fprintf (f, "BEGIN_CONTROL: %d; ", get_dep_weak (s, BEGIN_CONTROL)); - if (s & BE_IN_CONTROL) - fprintf (f, "BE_IN_CONTROL: %d; ", get_dep_weak (s, BE_IN_CONTROL)); - - if (s & HARD_DEP) - fprintf (f, "HARD_DEP; "); - - if (s & DEP_TRUE) - fprintf (f, "DEP_TRUE; "); - if (s & DEP_ANTI) - fprintf (f, "DEP_ANTI; "); - if (s & DEP_OUTPUT) - fprintf (f, "DEP_OUTPUT; "); - - fprintf (f, "\n"); -} - /* Helper function for check_cfg. Return nonzero, if edge vector pointed to by EL has edge with TYPE in its flags. */ @@ -4399,6 +5140,19 @@ has_edge_p (VEC(edge,gc) *el, int type) 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. */ @@ -4416,23 +5170,23 @@ check_cfg (rtx head, rtx tail) next_tail = NEXT_INSN (tail); do - { - not_last = head != tail; + { + not_last = head != tail; if (not_first) gcc_assert (NEXT_INSN (PREV_INSN (head)) == head); if (not_last) gcc_assert (PREV_INSN (NEXT_INSN (head)) == head); - if (LABEL_P (head) + if (LABEL_P (head) || (NOTE_INSN_BASIC_BLOCK_P (head) && (!not_first || (not_first && !LABEL_P (PREV_INSN (head)))))) { - gcc_assert (bb == 0); + gcc_assert (bb == 0); bb = BLOCK_FOR_INSN (head); if (bb != 0) - gcc_assert (BB_HEAD (bb) == head); + gcc_assert (BB_HEAD (bb) == head); else /* This is the case of jump table. See inside_basic_block_p (). */ gcc_assert (LABEL_P (head) && !inside_basic_block_p (head)); @@ -4448,7 +5202,7 @@ check_cfg (rtx head, rtx tail) gcc_assert (inside_basic_block_p (head) || NOTE_P (head)); gcc_assert (BLOCK_FOR_INSN (head) == bb); - + if (LABEL_P (head)) { head = NEXT_INSN (head); @@ -4458,8 +5212,9 @@ check_cfg (rtx head, rtx tail) { 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))); @@ -4475,11 +5230,12 @@ check_cfg (rtx head, rtx tail) 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); } } @@ -4491,65 +5247,302 @@ check_cfg (rtx head, rtx tail) gcc_assert (bb == 0); } -/* Perform a few consistency checks of flags in different data structures. */ +#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 -check_sched_flags (void) +init_insns_in_bb (basic_block bb) { - unsigned int f = current_sched_info->flags; - - if (flag_sched_stalled_insns) - gcc_assert (!(f & DO_SPECULATION)); - if (f & DO_SPECULATION) - gcc_assert (!flag_sched_stalled_insns - && (f & DETACH_LIFE_INFO) - && spec_info - && spec_info->mask); - if (f & DETACH_LIFE_INFO) - gcc_assert (f & USE_GLAT); + rtx insn; + + FOR_BB_INSNS (bb, insn) + init_insn (insn); } -/* Check global_live_at_{start, end} regsets. - If FATAL_P is TRUE, then abort execution at the first failure. - Otherwise, print diagnostics to STDERR (this mode is for calling - from debugger). */ +/* 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 -check_reg_live (bool fatal_p) +sched_scan (const struct sched_scan_info_def *ssi, + bb_vec_t bbs, basic_block bb, insn_vec_t insns, rtx insn) { - basic_block bb; + sched_scan_info = ssi; - FOR_ALL_BB (bb) + if (bbs != NULL || bb != NULL) { - int i; + extend_bb (); - i = bb->index; - - if (glat_start[i]) + if (bbs != NULL) { - bool b = bitmap_equal_p (bb->il.rtl->global_live_at_start, - glat_start[i]); - - if (!b) - { - gcc_assert (!fatal_p); + unsigned i; + basic_block x; - fprintf (stderr, ";; check_reg_live_at_start (%d) failed.\n", i); - } + for (i = 0; VEC_iterate (basic_block, bbs, i, x); i++) + init_bb (x); } - if (glat_end[i]) - { - bool b = bitmap_equal_p (bb->il.rtl->global_live_at_end, - glat_end[i]); + if (bb != NULL) + init_bb (bb); + } - if (!b) - { - gcc_assert (!fatal_p); + extend_insn (); - fprintf (stderr, ";; check_reg_live_at_end (%d) failed.\n", i); - } + 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) +{ + int new_luids_max_uid = get_max_uid () + 1; + + VEC_safe_grow_cleared (int, heap, sched_luids, new_luids_max_uid); +} + +/* Initialize LUID for INSN. */ +static void +luids_init_insn (rtx insn) +{ + int i = INSN_P (insn) ? 1 : common_sched_info->luid_for_non_insn (insn); + int luid; + + if (i >= 0) + { + luid = sched_max_luid; + sched_max_luid += i; + } + else + luid = -1; + + SET_INSN_LUID (insn, luid); +} + +/* Initialize luids for BBS, BB, INSNS and INSN. + 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) +{ + const struct sched_scan_info_def ssi = + { + NULL, /* extend_bb */ + NULL, /* init_bb */ + luids_extend_insn, /* extend_insn */ + luids_init_insn /* init_insn */ + }; + + sched_scan (&ssi, bbs, bb, insns, insn); +} + +/* Free LUIDs. */ +void +sched_finish_luids (void) +{ + VEC_free (int, heap, sched_luids); + sched_max_luid = 1; +} + +/* Return logical uid of INSN. Helpful while debugging. */ +int +insn_luid (rtx insn) +{ + return INSN_LUID (insn); +} + +/* Extend per insn data in the target. */ +void +sched_extend_target (void) +{ + if (targetm.sched.h_i_d_extended) + targetm.sched.h_i_d_extended (); +} + +/* Extend global scheduler structures (those, that live across calls to + schedule_block) to include information about just emitted INSN. */ +static void +extend_h_i_d (void) +{ + int reserve = (get_max_uid () + 1 + - VEC_length (haifa_insn_data_def, h_i_d)); + if (reserve > 0 + && ! VEC_space (haifa_insn_data_def, h_i_d, reserve)) + { + VEC_safe_grow_cleared (haifa_insn_data_def, heap, h_i_d, + 3 * get_max_uid () / 2); + sched_extend_target (); + } +} + +/* Initialize h_i_d entry of the INSN with default values. + Values, that are not explicitly initialized here, hold zero. */ +static void +init_h_i_d (rtx insn) +{ + if (INSN_LUID (insn) > 0) + { + INSN_COST (insn) = -1; + QUEUE_INDEX (insn) = QUEUE_NOWHERE; + INSN_TICK (insn) = INVALID_TICK; + INTER_TICK (insn) = INVALID_TICK; + TODO_SPEC (insn) = HARD_DEP; + } +} + +/* Initialize haifa_insn_data for BBS, BB, INSNS and INSN. */ +void +haifa_init_h_i_d (bb_vec_t bbs, basic_block bb, insn_vec_t insns, rtx insn) +{ + const struct sched_scan_info_def ssi = + { + NULL, /* extend_bb */ + NULL, /* init_bb */ + extend_h_i_d, /* extend_insn */ + init_h_i_d /* init_insn */ + }; + + sched_scan (&ssi, bbs, bb, insns, insn); +} + +/* Finalize haifa_insn_data. */ +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); +} + +/* Init data for the new insn INSN. */ +static void +haifa_init_insn (rtx insn) +{ + gcc_assert (insn != NULL); + + sched_init_luids (NULL, NULL, NULL, insn); + sched_extend_target (); + sched_deps_init (false); + haifa_init_h_i_d (NULL, NULL, NULL, insn); + + if (adding_bb_to_current_region_p) + { + sd_init_insn (insn); + + /* Extend dependency caches by one element. */ + extend_dependency_caches (1, false); + } +} + +/* Init data for the new basic block BB which comes after AFTER. */ +static void +haifa_init_only_bb (basic_block bb, basic_block after) +{ + gcc_assert (bb != NULL); + + sched_init_bbs (); + + if (common_sched_info->add_block) + /* This changes only data structures of the front-end. */ + common_sched_info->add_block (bb, after); +} + +/* A generic version of sched_split_block (). */ +basic_block +sched_split_block_1 (basic_block first_bb, rtx after) +{ + edge e; + + e = split_block (first_bb, after); + gcc_assert (e->src == first_bb); + + /* sched_split_block emits note if *check == BB_END. Probably it + is better to rip that note off. */ + + return e->dest; +} + +/* A generic version of sched_create_empty_bb (). */ +basic_block +sched_create_empty_bb_1 (basic_block after) +{ + 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 /* ENABLE_CHECKING */ #endif /* INSN_SCHEDULING */