X-Git-Url: https://oss.titaniummirror.com/gitweb?a=blobdiff_plain;f=gcc%2Fhaifa-sched.c;h=09dc233c2537536cee00d0da41e442ac2c20e02b;hb=6fed43773c9b0ce596dca5686f37ac3fc0fa11c0;hp=1d67afb41563031e239c15523379ded9f2264356;hpb=27b11d56b743098deb193d510b337ba22dc52e5c;p=msp430-gcc.git diff --git a/gcc/haifa-sched.c b/gcc/haifa-sched.c index 1d67afb4..09dc233c 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 Free Software Foundation, Inc. + Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000, + 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008 + 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, 59 Temple Place - Suite 330, Boston, MA -02111-1307, 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 @@ -54,13 +54,6 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA as short as possible. The remaining insns are then scheduled in remaining slots. - Function unit conflicts are resolved during forward list scheduling - by tracking the time when each insn is committed to the schedule - and from that, the time the function units it uses must be free. - As insns on the ready list are considered for scheduling, those - that would result in a blockage of the already committed insns are - queued until no blockage will result. - The following list shows the order in which we want to break ties among insns in the ready list: @@ -89,9 +82,9 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA compute_block_backward_dependences (). Dependencies set up by memory references are treated in exactly the - same way as other dependencies, by using LOG_LINKS backward - dependences. LOG_LINKS are translated into INSN_DEPEND forward - dependences for the purpose of forward list scheduling. + same way as other dependencies, by using insn backward dependences + INSN_BACK_DEPS. INSN_BACK_DEPS are translated into forward dependences + INSN_FORW_DEPS the purpose of forward list scheduling. Having optimized the critical path, we may have also unduly extended the lifetimes of some registers. If an operation requires @@ -123,8 +116,7 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA This pass must update information that subsequent passes expect to be correct. Namely: reg_n_refs, reg_n_sets, reg_n_deaths, - reg_n_calls_crossed, and reg_live_length. Also, BLOCK_HEAD, - BLOCK_END. + reg_n_calls_crossed, and reg_live_length. Also, BB_HEAD, BB_END. The information in the line number notes is carefully retained by this pass. Notes that refer to the starting and ending of @@ -134,11 +126,12 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "config.h" #include "system.h" +#include "coretypes.h" +#include "tm.h" #include "toplev.h" #include "rtl.h" #include "tm_p.h" #include "hard-reg-set.h" -#include "basic-block.h" #include "regs.h" #include "function.h" #include "flags.h" @@ -149,6 +142,11 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "recog.h" #include "sched-int.h" #include "target.h" +#include "output.h" +#include "params.h" +#include "vecprim.h" +#include "dbgcnt.h" +#include "cfgloop.h" #ifdef INSN_SCHEDULING @@ -156,7 +154,7 @@ Software Foundation, 59 Temple Place - Suite 330, 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: @@ -174,41 +172,68 @@ 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. */ void -fix_sched_param (param, val) - const char *param, *val; +fix_sched_param (const char *param, const char *val) { if (!strcmp (param, "verbose")) sched_verbose_param = atoi (val); else - warning ("fix_sched_param: unknown param: %s", param); + 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 DONE_PRIORITY -1 -#define MAX_PRIORITY 0x7fffffff -#define TAIL_PRIORITY 0x7ffffffe -#define LAUNCH_PRIORITY 0x7f000001 -#define DONE_PRIORITY_P(INSN) (INSN_PRIORITY (INSN) < 0) -#define LOW_PRIORITY_P(INSN) ((INSN_PRIORITY (INSN) & 0x7f000000) == 0) +#define INSN_TICK(INSN) (HID (INSN)->tick) +#define INTER_TICK(INSN) (HID (INSN)->inter_tick) -#define LINE_NOTE(INSN) (h_i_d[INSN_UID (INSN)].line_note) -#define INSN_TICK(INSN) (h_i_d[INSN_UID (INSN)].tick) +/* If INSN_TICK of an instruction is equal to INVALID_TICK, + then it should be recalculated from scratch. */ +#define INVALID_TICK (-(max_insn_queue_index + 1)) +/* The minimal value of the INSN_TICK of an instruction. */ +#define MIN_TICK (-max_insn_queue_index) -/* Vector indexed by basic block number giving the starting line-number - for each basic block. */ -static rtx *line_note_head; +/* Issue points are used to distinguish between instructions in max_issue (). + For now, all instructions are equally good. */ +#define ISSUE_POINTS(INSN) 1 /* List of important notes we must keep around. This is a pointer to the last element in the list. */ -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. */ +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 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; + +/* Array used in {unlink, restore}_bb_notes. */ +static rtx *bb_header = 0; + +/* 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. */ @@ -232,12 +257,10 @@ static rtx note_list; "Pending" list have their dependencies satisfied and move to either the "Ready" list or the "Queued" set depending on whether sufficient time has passed to make them ready. As time passes, - insns move from the "Queued" set to the "Ready" list. Insns may - move from the "Ready" list to the "Queued" set if they are blocked - due to a function unit conflict. + insns move from the "Queued" set to the "Ready" list. - The "Pending" list (P) are the insns in the INSN_DEPEND of the unscheduled - insns, i.e., those that are ready, queued, and pending. + The "Pending" list (P) are the insns in the INSN_FORW_DEPS of the + unscheduled insns, i.e., those that are ready, queued, and pending. The "Queued" set (Q) is implemented by the variable `insn_queue'. The "Ready" list (R) is implemented by the variables `ready' and `n_ready'. @@ -245,515 +268,607 @@ static rtx note_list; The transition (R->S) is implemented in the scheduling loop in `schedule_block' when the best insn to schedule is chosen. - The transition (R->Q) is implemented in `queue_insn' when an - insn is found to have a function unit conflict with the already - committed insns. The transitions (P->R and P->Q) are implemented in `schedule_insn' as insns move from the ready list to the scheduled list. The transition (Q->R) is implemented in 'queue_to_insn' as time passes or stalls are introduced. */ /* Implement a circular buffer to delay instructions until sufficient - time has passed. INSN_QUEUE_SIZE is a power of two larger than - MAX_BLOCKAGE and MAX_READY_COST computed by genattr.c. This is the - longest time an isnsn may be queued. */ -static rtx insn_queue[INSN_QUEUE_SIZE]; + time has passed. For the new pipeline description interface, + MAX_INSN_QUEUE_INDEX is a power of two minus one which is not less + than maximal time of instruction execution computed by genattr.c on + the base maximal time of functional unit reservations and getting a + result. This is the longest time an insn may be queued. */ + +static rtx *insn_queue; static int q_ptr = 0; static int q_size = 0; -#define NEXT_Q(X) (((X)+1) & (INSN_QUEUE_SIZE-1)) -#define NEXT_Q_AFTER(X, C) (((X)+C) & (INSN_QUEUE_SIZE-1)) - -/* 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. */ - -struct ready_list -{ - rtx *vec; - int veclen; - int first; - int n_ready; -}; - -/* Forward declarations. */ -static unsigned int blockage_range PARAMS ((int, rtx)); -static void clear_units PARAMS ((void)); -static void schedule_unit PARAMS ((int, rtx, int)); -static int actual_hazard PARAMS ((int, rtx, int, int)); -static int potential_hazard PARAMS ((int, rtx, int)); -static int priority PARAMS ((rtx)); -static int rank_for_schedule PARAMS ((const PTR, const PTR)); -static void swap_sort PARAMS ((rtx *, int)); -static void queue_insn PARAMS ((rtx, int)); -static void schedule_insn PARAMS ((rtx, struct ready_list *, int)); -static void find_insn_reg_weight PARAMS ((int)); -static void adjust_priority PARAMS ((rtx)); - -/* Notes handling mechanism: - ========================= - Generally, NOTES are saved before scheduling and restored after scheduling. - The scheduler distinguishes between three types of notes: +#define NEXT_Q(X) (((X)+1) & max_insn_queue_index) +#define NEXT_Q_AFTER(X, C) (((X)+C) & max_insn_queue_index) + +#define QUEUE_SCHEDULED (-3) +#define QUEUE_NOWHERE (-2) +#define QUEUE_READY (-1) +/* QUEUE_SCHEDULED - INSN is scheduled. + QUEUE_NOWHERE - INSN isn't scheduled yet and is neither in + 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) (HID (INSN)->queue_index) + +/* The following variable value refers for all current and future + reservations of the processor units. */ +state_t curr_state; + +/* The following variable value is size of memory representing all + current and future reservations of the processor units. */ +size_t dfa_state_size; + +/* The following array is used to find the best insn from ready when + the automaton pipeline interface is used. */ +char *ready_try = NULL; + +/* The ready list. */ +struct ready_list ready = {NULL, 0, 0, 0}; + +/* The pointer to the ready list (to be removed). */ +static struct ready_list *readyp = &ready; + +/* Scheduling clock. */ +static int clock_var; - (1) LINE_NUMBER notes, generated and used for debugging. Here, - before scheduling a region, a pointer to the LINE_NUMBER note is - added to the insn following it (in save_line_notes()), and the note - is removed (in rm_line_notes() and unlink_line_notes()). After - scheduling the region, this pointer is used for regeneration of - the LINE_NUMBER note (in restore_line_notes()). +static int may_trap_exp (const_rtx, int); - (2) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes: - Before scheduling a region, a pointer to the note is added to the insn - that follows or precedes it. (This happens as part of the data dependence - computation). After scheduling an insn, the pointer contained in it is - used for regenerating the corresponding note (in reemit_notes). +/* Nonzero iff the address is comprised from at most 1 register. */ +#define CONST_BASED_ADDRESS_P(x) \ + (REG_P (x) \ + || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \ + || (GET_CODE (x) == LO_SUM)) \ + && (CONSTANT_P (XEXP (x, 0)) \ + || CONSTANT_P (XEXP (x, 1))))) - (3) All other notes (e.g. INSN_DELETED): Before scheduling a block, - these notes are put in a list (in rm_other_notes() and - unlink_other_notes ()). After scheduling the block, these notes are - inserted at the beginning of the block (in schedule_block()). */ +/* Returns a class that insn with GET_DEST(insn)=x may belong to, + as found by analyzing insn's expression. */ -static rtx unlink_other_notes PARAMS ((rtx, rtx)); -static rtx unlink_line_notes PARAMS ((rtx, rtx)); -static rtx reemit_notes PARAMS ((rtx, rtx)); + +static int haifa_luid_for_non_insn (rtx x); -static rtx *ready_lastpos PARAMS ((struct ready_list *)); -static void ready_sort PARAMS ((struct ready_list *)); -static rtx ready_remove_first PARAMS ((struct ready_list *)); +/* 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 */ + }; -static void queue_to_ready PARAMS ((struct ready_list *)); +const struct sched_scan_info_def *sched_scan_info; -static void debug_ready_list PARAMS ((struct ready_list *)); +/* Mapping from instruction UID to its Logical UID. */ +VEC (int, heap) *sched_luids = NULL; -static rtx move_insn1 PARAMS ((rtx, rtx)); -static rtx move_insn PARAMS ((rtx, rtx)); +/* Next LUID to assign to an instruction. */ +int sched_max_luid = 1; -#endif /* INSN_SCHEDULING */ - -/* Point to state used for the current scheduling pass. */ -struct sched_info *current_sched_info; - -#ifndef INSN_SCHEDULING -void -schedule_insns (dump_file) - FILE *dump_file ATTRIBUTE_UNUSED; -{ -} -#else +/* Haifa Instruction Data. */ +VEC (haifa_insn_data_def, heap) *h_i_d = NULL; -/* Pointer to the last instruction scheduled. Used by rank_for_schedule, - so that insns independent of the last scheduled insn will be preferred - over dependent instructions. */ +void (* sched_init_only_bb) (basic_block, basic_block); -static rtx last_scheduled_insn; +/* Split block function. Different schedulers might use different functions + to handle their internal data consistent. */ +basic_block (* sched_split_block) (basic_block, rtx); -/* Compute the function units used by INSN. This caches the value - returned by function_units_used. A function unit is encoded as the - unit number if the value is non-negative and the compliment of a - mask if the value is negative. A function unit index is the - non-negative encoding. */ +/* Create empty basic block after the specified block. */ +basic_block (* sched_create_empty_bb) (basic_block); -HAIFA_INLINE int -insn_unit (insn) - rtx insn; +static int +may_trap_exp (const_rtx x, int is_store) { - int unit = INSN_UNIT (insn); + enum rtx_code code; - if (unit == 0) + if (x == 0) + return TRAP_FREE; + code = GET_CODE (x); + if (is_store) { - recog_memoized (insn); - - /* A USE insn, or something else we don't need to understand. - We can't pass these directly to function_units_used because it will - trigger a fatal error for unrecognizable insns. */ - if (INSN_CODE (insn) < 0) - unit = -1; + if (code == MEM && may_trap_p (x)) + return TRAP_RISKY; else + return TRAP_FREE; + } + if (code == MEM) + { + /* The insn uses memory: a volatile load. */ + if (MEM_VOLATILE_P (x)) + return IRISKY; + /* An exception-free load. */ + if (!may_trap_p (x)) + return IFREE; + /* A load with 1 base register, to be further checked. */ + if (CONST_BASED_ADDRESS_P (XEXP (x, 0))) + return PFREE_CANDIDATE; + /* No info on the load, to be further checked. */ + return PRISKY_CANDIDATE; + } + else + { + const char *fmt; + int i, insn_class = TRAP_FREE; + + /* Neither store nor load, check if it may cause a trap. */ + if (may_trap_p (x)) + return TRAP_RISKY; + /* Recursive step: walk the insn... */ + fmt = GET_RTX_FORMAT (code); + for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) { - unit = function_units_used (insn); - /* Increment non-negative values so we can cache zero. */ - if (unit >= 0) - unit++; + if (fmt[i] == 'e') + { + int tmp_class = may_trap_exp (XEXP (x, i), is_store); + insn_class = WORST_CLASS (insn_class, tmp_class); + } + else if (fmt[i] == 'E') + { + int j; + for (j = 0; j < XVECLEN (x, i); j++) + { + int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store); + insn_class = WORST_CLASS (insn_class, tmp_class); + if (insn_class == TRAP_RISKY || insn_class == IRISKY) + break; + } + } + if (insn_class == TRAP_RISKY || insn_class == IRISKY) + break; } - /* We only cache 16 bits of the result, so if the value is out of - range, don't cache it. */ - if (FUNCTION_UNITS_SIZE < HOST_BITS_PER_SHORT - || unit >= 0 - || (unit & ~((1 << (HOST_BITS_PER_SHORT - 1)) - 1)) == 0) - INSN_UNIT (insn) = unit; + return insn_class; } - return (unit > 0 ? unit - 1 : unit); } -/* Compute the blockage range for executing INSN on UNIT. This caches - the value returned by the blockage_range_function for the unit. - These values are encoded in an int where the upper half gives the - minimum value and the lower half gives the maximum value. */ +/* 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. + IRISKY: volatile load. + PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for + being either PFREE or PRISKY. */ -HAIFA_INLINE static unsigned int -blockage_range (unit, insn) - int unit; - rtx insn; +static int +haifa_classify_rtx (const_rtx x) { - unsigned int blockage = INSN_BLOCKAGE (insn); - unsigned int range; + int tmp_class = TRAP_FREE; + int insn_class = TRAP_FREE; + enum rtx_code code; - if ((int) UNIT_BLOCKED (blockage) != unit + 1) + if (GET_CODE (x) == PARALLEL) { - range = function_units[unit].blockage_range_function (insn); - /* We only cache the blockage range for one unit and then only if - the values fit. */ - if (HOST_BITS_PER_INT >= UNIT_BITS + 2 * BLOCKAGE_BITS) - INSN_BLOCKAGE (insn) = ENCODE_BLOCKAGE (unit + 1, range); + int i, len = XVECLEN (x, 0); + + for (i = len - 1; i >= 0; i--) + { + 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; + } } else - range = BLOCKAGE_RANGE (blockage); + { + code = GET_CODE (x); + switch (code) + { + case CLOBBER: + /* Test if it is a 'store'. */ + 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 (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 (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; + default:; + } + insn_class = tmp_class; + } - return range; + return insn_class; } -/* A vector indexed by function unit instance giving the last insn to use - the unit. The value of the function unit instance index for unit U - instance I is (U + I * FUNCTION_UNITS_SIZE). */ -static rtx unit_last_insn[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY]; +int +haifa_classify_insn (const_rtx insn) +{ + return haifa_classify_rtx (PATTERN (insn)); +} -/* A vector indexed by function unit instance giving the minimum time when - the unit will unblock based on the maximum blockage cost. */ -static int unit_tick[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY]; +/* Forward declarations. */ -/* A vector indexed by function unit number giving the number of insns - that remain to use the unit. */ -static int unit_n_insns[FUNCTION_UNITS_SIZE]; +static int priority (rtx); +static int rank_for_schedule (const void *, const void *); +static void swap_sort (rtx *, int); +static void queue_insn (rtx, int); +static int schedule_insn (rtx); +static int find_set_reg_weight (const_rtx); +static void find_insn_reg_weight (const_rtx); +static void adjust_priority (rtx); +static void advance_one_cycle (void); +static void extend_h_i_d (void); -/* Access the unit_last_insn array. Used by the visualization code. */ -rtx -get_unit_last_insn (instance) - int instance; -{ - return unit_last_insn[instance]; -} +/* Notes handling mechanism: + ========================= + Generally, NOTES are saved before scheduling and restored after scheduling. + The scheduler distinguishes between two types of notes: -/* Reset the function unit state to the null state. */ + (1) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes: + Before scheduling a region, a pointer to the note is added to the insn + that follows or precedes it. (This happens as part of the data dependence + computation). After scheduling an insn, the pointer contained in it is + used for regenerating the corresponding note (in reemit_notes). -static void -clear_units () -{ - memset ((char *) unit_last_insn, 0, sizeof (unit_last_insn)); - memset ((char *) unit_tick, 0, sizeof (unit_tick)); - memset ((char *) unit_n_insns, 0, sizeof (unit_n_insns)); -} + (2) All other notes (e.g. INSN_DELETED): Before scheduling a block, + these notes are put in a list (in rm_other_notes() and + unlink_other_notes ()). After scheduling the block, these notes are + inserted at the beginning of the block (in schedule_block()). */ -/* Return the issue-delay of an insn. */ +static void ready_add (struct ready_list *, rtx, bool); +static rtx ready_remove_first (struct ready_list *); + +static void queue_to_ready (struct ready_list *); +static int early_queue_to_ready (state_t, struct ready_list *); + +static void debug_ready_list (struct ready_list *); + +/* The following functions are used to implement multi-pass scheduling + on the first cycle. */ +static rtx ready_remove (struct ready_list *, int); +static void ready_remove_insn (rtx); + +static int choose_ready (struct ready_list *, rtx *); + +static void fix_inter_tick (rtx, rtx); +static int fix_tick_ready (rtx); +static void change_queue_index (rtx, int); + +/* The following functions are used to implement scheduling of data/control + speculative instructions. */ + +static void extend_h_i_d (void); +static void init_h_i_d (rtx); +static void generate_recovery_code (rtx); +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 void init_before_recovery (basic_block *); +static void create_check_block_twin (rtx, bool); +static void fix_recovery_deps (basic_block); +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 fix_jump_move (rtx); +static void move_block_after_check (rtx); +static void move_succs (VEC(edge,gc) **, basic_block); +static void sched_remove_insn (rtx); +static void clear_priorities (rtx, rtx_vec_t *); +static void calc_priorities (rtx_vec_t); +static void add_jump_dependencies (rtx, rtx); +#ifdef ENABLE_CHECKING +static int has_edge_p (VEC(edge,gc) *, int); +static void check_cfg (rtx, rtx); +#endif -HAIFA_INLINE int -insn_issue_delay (insn) - rtx insn; +#endif /* INSN_SCHEDULING */ + +/* Point to state used for the current scheduling pass. */ +struct haifa_sched_info *current_sched_info; + +#ifndef INSN_SCHEDULING +void +schedule_insns (void) { - int i, delay = 0; - int unit = insn_unit (insn); +} +#else - /* Efficiency note: in fact, we are working 'hard' to compute a - value that was available in md file, and is not available in - function_units[] structure. It would be nice to have this - value there, too. */ - if (unit >= 0) - { - if (function_units[unit].blockage_range_function && - function_units[unit].blockage_function) - delay = function_units[unit].blockage_function (insn, insn); - } - else - for (i = 0, unit = ~unit; unit; i++, unit >>= 1) - if ((unit & 1) != 0 && function_units[i].blockage_range_function - && function_units[i].blockage_function) - delay = MAX (delay, function_units[i].blockage_function (insn, insn)); +/* Pointer to the last instruction scheduled. Used by rank_for_schedule, + so that insns independent of the last scheduled insn will be preferred + over dependent instructions. */ - return delay; -} +static rtx last_scheduled_insn; -/* Return the actual hazard cost of executing INSN on the unit UNIT, - instance INSTANCE at time CLOCK if the previous actual hazard cost - was COST. */ +/* Cached cost of the instruction. Use below function to get cost of the + insn. -1 here means that the field is not initialized. */ +#define INSN_COST(INSN) (HID (INSN)->cost) +/* Compute cost of executing INSN. + This is the number of cycles between instruction issue and + instruction results. */ HAIFA_INLINE int -actual_hazard_this_instance (unit, instance, insn, clock, cost) - int unit, instance, clock, cost; - rtx insn; +insn_cost (rtx insn) { - int tick = unit_tick[instance]; /* Issue time of the last issued insn. */ + int cost; - if (tick - clock > cost) + if (sel_sched_p ()) { - /* The scheduler is operating forward, so unit's last insn is the - executing insn and INSN is the candidate insn. We want a - more exact measure of the blockage if we execute INSN at CLOCK - given when we committed the execution of the unit's last insn. + if (recog_memoized (insn) < 0) + return 0; - The blockage value is given by either the unit's max blockage - constant, blockage range function, or blockage function. Use - the most exact form for the given unit. */ + cost = insn_default_latency (insn); + if (cost < 0) + cost = 0; - if (function_units[unit].blockage_range_function) - { - if (function_units[unit].blockage_function) - tick += (function_units[unit].blockage_function - (unit_last_insn[instance], insn) - - function_units[unit].max_blockage); - else - tick += ((int) MAX_BLOCKAGE_COST (blockage_range (unit, insn)) - - function_units[unit].max_blockage); - } - if (tick - clock > cost) - cost = tick - clock; + return cost; } - return cost; -} -/* Record INSN as having begun execution on the units encoded by UNIT at - time CLOCK. */ + cost = INSN_COST (insn); -HAIFA_INLINE static void -schedule_unit (unit, insn, clock) - int unit, clock; - rtx insn; -{ - int i; - - if (unit >= 0) + if (cost < 0) { - int instance = unit; -#if MAX_MULTIPLICITY > 1 - /* Find the first free instance of the function unit and use that - one. We assume that one is free. */ - for (i = function_units[unit].multiplicity - 1; i > 0; i--) + /* A USE insn, or something else we don't need to + understand. We can't pass these directly to + result_ready_cost or insn_default_latency because it will + trigger a fatal error for unrecognizable insns. */ + if (recog_memoized (insn) < 0) { - if (!actual_hazard_this_instance (unit, instance, insn, clock, 0)) - break; - instance += FUNCTION_UNITS_SIZE; + INSN_COST (insn) = 0; + return 0; + } + else + { + cost = insn_default_latency (insn); + if (cost < 0) + cost = 0; + + INSN_COST (insn) = cost; } -#endif - unit_last_insn[instance] = insn; - unit_tick[instance] = (clock + function_units[unit].max_blockage); } - else - for (i = 0, unit = ~unit; unit; i++, unit >>= 1) - if ((unit & 1) != 0) - schedule_unit (i, insn, clock); -} -/* Return the actual hazard cost of executing INSN on the units encoded by - UNIT at time CLOCK if the previous actual hazard cost was COST. */ + return cost; +} -HAIFA_INLINE static int -actual_hazard (unit, insn, clock, cost) - int unit, clock, cost; - rtx insn; +/* Compute cost of dependence LINK. + This is the number of cycles between instruction issue and + instruction results. + ??? We also use this function to call recog_memoized on all insns. */ +int +dep_cost_1 (dep_t link, dw_t dw) { - int i; - - if (unit >= 0) + 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. */ + if (recog_memoized (used) < 0) + { + cost = 0; + recog_memoized (insn); + } + else { - /* Find the instance of the function unit with the minimum hazard. */ - int instance = unit; - int best_cost = actual_hazard_this_instance (unit, instance, insn, - clock, cost); -#if MAX_MULTIPLICITY > 1 - int this_cost; + enum reg_note dep_type = DEP_TYPE (link); + + cost = insn_cost (insn); - if (best_cost > cost) + if (INSN_CODE (insn) >= 0) { - for (i = function_units[unit].multiplicity - 1; i > 0; i--) + if (dep_type == REG_DEP_ANTI) + cost = 0; + else if (dep_type == REG_DEP_OUTPUT) { - instance += FUNCTION_UNITS_SIZE; - this_cost = actual_hazard_this_instance (unit, instance, insn, - clock, cost); - if (this_cost < best_cost) - { - best_cost = this_cost; - if (this_cost <= cost) - break; - } + cost = (insn_default_latency (insn) + - insn_default_latency (used)); + if (cost <= 0) + cost = 1; } + else if (bypass_p (insn)) + cost = insn_latency (insn, used); } -#endif - cost = MAX (cost, best_cost); - } - else - for (i = 0, unit = ~unit; unit; i++, unit >>= 1) - if ((unit & 1) != 0) - cost = actual_hazard (i, insn, clock, cost); + - return cost; -} + 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); -/* Return the potential hazard cost of executing an instruction on the - units encoded by UNIT if the previous potential hazard cost was COST. - An insn with a large blockage time is chosen in preference to one - with a smaller time; an insn that uses a unit that is more likely - to be used is chosen in preference to one with a unit that is less - used. We are trying to minimize a subsequent actual hazard. */ + /* Make it self-cycled, so that if some tries to walk over this + incomplete list he/she will be caught in an endless loop. */ + XEXP (dep_cost_rtx_link, 1) = dep_cost_rtx_link; -HAIFA_INLINE static int -potential_hazard (unit, insn, cost) - int unit, cost; - rtx insn; -{ - int i, ncost; - unsigned int minb, maxb; + /* Targets use only REG_NOTE_KIND of the link. */ + PUT_REG_NOTE_KIND (dep_cost_rtx_link, DEP_TYPE (link)); - if (unit >= 0) - { - minb = maxb = function_units[unit].max_blockage; - if (maxb > 1) - { - if (function_units[unit].blockage_range_function) - { - maxb = minb = blockage_range (unit, insn); - maxb = MAX_BLOCKAGE_COST (maxb); - minb = MIN_BLOCKAGE_COST (minb); - } + cost = targetm.sched.adjust_cost (used, dep_cost_rtx_link, + insn, cost); - if (maxb > 1) - { - /* Make the number of instructions left dominate. Make the - minimum delay dominate the maximum delay. If all these - are the same, use the unit number to add an arbitrary - ordering. Other terms can be added. */ - ncost = minb * 0x40 + maxb; - ncost *= (unit_n_insns[unit] - 1) * 0x1000 + unit; - if (ncost > cost) - cost = ncost; - } + free_INSN_LIST_node (dep_cost_rtx_link); } + + if (cost < 0) + cost = 0; } - else - for (i = 0, unit = ~unit; unit; i++, unit >>= 1) - if ((unit & 1) != 0) - cost = potential_hazard (i, insn, cost); return cost; } -/* Compute cost of executing INSN given the dependence LINK on the insn USED. +/* Compute cost of dependence LINK. This is the number of cycles between instruction issue and instruction results. */ - -HAIFA_INLINE int -insn_cost (insn, link, used) - rtx insn, link, used; +int +dep_cost (dep_t link) { - int cost = INSN_COST (insn); + return dep_cost_1 (link, 0); +} - if (cost == 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 ()) { - recog_memoized (insn); - - /* A USE insn, or something else we don't need to understand. - We can't pass these directly to result_ready_cost because it will - trigger a fatal error for unrecognizable insns. */ - if (INSN_CODE (insn) < 0) - { - INSN_COST (insn) = 1; - return 1; - } - else - { - cost = result_ready_cost (insn); - - if (cost < 1) - cost = 1; - - INSN_COST (insn) = cost; - } + /* We're dealing with haifa-sched.c INSN_PRIORITY. */ + if (INSN_PRIORITY_KNOWN (insn)) + INSN_PRIORITY (insn) += amount; } - - /* In this case estimate cost without caring how insn is used. */ - if (link == 0 && used == 0) - return 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. */ - recog_memoized (used); - if (INSN_CODE (used) < 0) - LINK_COST_FREE (link) = 1; - - /* If some dependencies vary the cost, compute the adjustment. Most - commonly, the adjustment is complete: either the cost is ignored - (in the case of an output- or anti-dependence), or the cost is - unchanged. These values are cached in the link as LINK_COST_FREE - and LINK_COST_ZERO. */ - - if (LINK_COST_FREE (link)) - cost = 0; - else if (!LINK_COST_ZERO (link) && targetm.sched.adjust_cost) + else { - int ncost = (*targetm.sched.adjust_cost) (used, link, insn, cost); - - if (ncost < 1) - { - LINK_COST_FREE (link) = 1; - ncost = 0; - } - if (cost == ncost) - LINK_COST_ZERO (link) = 1; - cost = ncost; + /* In sel-sched.c INSN_PRIORITY is not kept up to date. + Use EXPR_PRIORITY instead. */ + sel_add_to_insn_priority (insn, amount); } +} - return cost; +/* Return 'true' if DEP should be included in priority calculations. */ +static bool +contributes_to_priority_p (dep_t dep) +{ + /* 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 priority number for INSN. */ - static int -priority (insn) - rtx insn; +priority (rtx insn) { - rtx link; - if (! INSN_P (insn)) return 0; - if (! INSN_PRIORITY_KNOWN (insn)) - { - int this_priority = 0; + /* We should not be interested in priority of an already scheduled insn. */ + gcc_assert (QUEUE_INDEX (insn) != QUEUE_SCHEDULED); - if (INSN_DEPEND (insn) == 0) - this_priority = insn_cost (insn, 0, 0); + if (!INSN_PRIORITY_KNOWN (insn)) + { + int this_priority = -1; + + if (sd_lists_empty_p (insn, SD_LIST_FORW)) + /* ??? 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 + such insn to 0. */ + this_priority = insn_cost (insn); else { - for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1)) + rtx prev_first, twin; + basic_block rec; + + /* For recovery check instructions we calculate priority slightly + 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. */ + + /* Selective scheduling does not define RECOVERY_BLOCK macro. */ + rec = sel_sched_p () ? NULL : RECOVERY_BLOCK (insn); + if (!rec || rec == EXIT_BLOCK_PTR) { - rtx next; - int next_priority; + prev_first = PREV_INSN (insn); + twin = insn; + } + else + { + prev_first = NEXT_INSN (BB_HEAD (rec)); + twin = PREV_INSN (BB_END (rec)); + } - if (RTX_INTEGRATED_P (link)) - continue; + do + { + sd_iterator_def sd_it; + dep_t dep; + + FOR_EACH_DEP (twin, SD_LIST_FORW, sd_it, dep) + { + rtx next; + int next_priority; - next = XEXP (link, 0); + next = DEP_CON (dep); - /* Critical path is meaningful in block boundaries only. */ - if (! (*current_sched_info->contributes_to_priority) (next, insn)) - continue; + if (BLOCK_FOR_INSN (next) != rec) + { + int cost; - next_priority = insn_cost (insn, link, next) + priority (next); - if (next_priority > this_priority) - this_priority = next_priority; + if (!contributes_to_priority_p (dep)) + continue; + + if (twin == insn) + cost = dep_cost (dep); + else + { + struct _dep _dep1, *dep1 = &_dep1; + + init_dep (dep1, insn, next, REG_DEP_ANTI); + + cost = dep_cost (dep1); + } + + next_priority = cost + priority (next); + + if (next_priority > this_priority) + 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); } /* Macros and functions for keeping the priority queue sorted, and - dealing with queueing and dequeueing of instructions. */ + dealing with queuing and dequeuing of instructions. */ #define SCHED_SORT(READY, N_READY) \ do { if ((N_READY) == 2) \ @@ -767,50 +882,86 @@ while (0) unstable. */ static int -rank_for_schedule (x, y) - const PTR x; - const PTR y; +rank_for_schedule (const void *x, const void *y) { rtx tmp = *(const rtx *) y; rtx tmp2 = *(const rtx *) x; - rtx link; - int tmp_class, tmp2_class, depend_count1, depend_count2; + int tmp_class, tmp2_class; int val, priority_val, weight_val, info_val; + /* The insn in a schedule group should be issued the first. */ + if (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)); + /* Prefer insn with higher priority. */ priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp); + if (priority_val) return priority_val; + /* Prefer speculative insn with greater dependencies weakness. */ + if (spec_info) + { + ds_t ds1, ds2; + dw_t dw1, dw2; + int dw; + + ds1 = TODO_SPEC (tmp) & SPECULATIVE; + if (ds1) + dw1 = ds_weak (ds1); + else + dw1 = NO_DEP_WEAK; + + ds2 = TODO_SPEC (tmp2) & SPECULATIVE; + if (ds2) + dw2 = ds_weak (ds2); + else + dw2 = NO_DEP_WEAK; + + dw = dw2 - dw1; + if (dw > (NO_DEP_WEAK / 8) || dw < -(NO_DEP_WEAK / 8)) + 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); + return weight_val; info_val = (*current_sched_info->rank) (tmp, tmp2); if (info_val) return info_val; /* Compare insns based on their relation to the last-scheduled-insn. */ - if (last_scheduled_insn) + if (INSN_P (last_scheduled_insn)) { + 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. */ - link = find_insn_list (tmp, INSN_DEPEND (last_scheduled_insn)); - if (link == 0 || insn_cost (last_scheduled_insn, link, tmp) == 1) + dep1 = sd_find_dep_between (last_scheduled_insn, tmp, true); + + if (dep1 == NULL || dep_cost (dep1) == 1) tmp_class = 3; - else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */ + else if (/* Data dependence. */ + DEP_TYPE (dep1) == REG_DEP_TRUE) tmp_class = 1; else tmp_class = 2; - link = find_insn_list (tmp2, INSN_DEPEND (last_scheduled_insn)); - if (link == 0 || insn_cost (last_scheduled_insn, link, tmp2) == 1) + dep2 = sd_find_dep_between (last_scheduled_insn, tmp2, true); + + if (dep2 == NULL || dep_cost (dep2) == 1) tmp2_class = 3; - else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */ + else if (/* Data dependence. */ + DEP_TYPE (dep2) == REG_DEP_TRUE) tmp2_class = 1; else tmp2_class = 2; @@ -822,16 +973,11 @@ rank_for_schedule (x, y) /* Prefer the insn which has more later insns that depend on it. This gives the scheduler more freedom when scheduling later instructions at the expense of added register pressure. */ - depend_count1 = 0; - for (link = INSN_DEPEND (tmp); link; link = XEXP (link, 1)) - depend_count1++; - depend_count2 = 0; - for (link = INSN_DEPEND (tmp2); link; link = XEXP (link, 1)) - depend_count2++; + val = (sd_lists_size (tmp2, SD_LIST_FORW) + - sd_lists_size (tmp, SD_LIST_FORW)); - val = depend_count2 - depend_count1; - if (val) + if (val != 0) return val; /* If insns are equally good, sort by INSN_LUID (original insn order), @@ -843,9 +989,7 @@ rank_for_schedule (x, y) /* Resort the array A in which only element at index N may be out of order. */ HAIFA_INLINE static void -swap_sort (a, n) - rtx *a; - int n; +swap_sort (rtx *a, int n) { rtx insn = a[n - 1]; int i = n - 2; @@ -863,12 +1007,13 @@ swap_sort (a, n) chain for debugging purposes. */ HAIFA_INLINE static void -queue_insn (insn, n_cycles) - rtx insn; - int n_cycles; +queue_insn (rtx insn, int n_cycles) { int next_q = NEXT_Q_AFTER (q_ptr, n_cycles); rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]); + + gcc_assert (n_cycles <= max_insn_queue_index); + insn_queue[next_q] = link; q_size += 1; @@ -879,63 +1024,145 @@ queue_insn (insn, n_cycles) fprintf (sched_dump, "queued for %d cycles.\n", n_cycles); } + + QUEUE_INDEX (insn) = next_q; +} + +/* Remove INSN from queue. */ +static void +queue_remove (rtx insn) +{ + gcc_assert (QUEUE_INDEX (insn) >= 0); + remove_free_INSN_LIST_elem (insn, &insn_queue[QUEUE_INDEX (insn)]); + q_size--; + QUEUE_INDEX (insn) = QUEUE_NOWHERE; } /* Return a pointer to the bottom of the ready list, i.e. the insn with the lowest priority. */ -HAIFA_INLINE static rtx * -ready_lastpos (ready) - struct ready_list *ready; +rtx * +ready_lastpos (struct ready_list *ready) { - if (ready->n_ready == 0) - abort (); + gcc_assert (ready->n_ready >= 1); return ready->vec + ready->first - ready->n_ready + 1; } -/* Add an element INSN to the ready list so that it ends up with the lowest - priority. */ +/* Add an element INSN to the ready list so that it ends up with the + lowest/highest priority depending on FIRST_P. */ -HAIFA_INLINE void -ready_add (ready, insn) - struct ready_list *ready; - rtx insn; +HAIFA_INLINE static void +ready_add (struct ready_list *ready, rtx insn, bool first_p) { - if (ready->first == ready->n_ready) + if (!first_p) + { + if (ready->first == ready->n_ready) + { + memmove (ready->vec + ready->veclen - ready->n_ready, + ready_lastpos (ready), + ready->n_ready * sizeof (rtx)); + ready->first = ready->veclen - 1; + } + ready->vec[ready->first - ready->n_ready] = insn; + } + else { - memmove (ready->vec + ready->veclen - ready->n_ready, - ready_lastpos (ready), - ready->n_ready * sizeof (rtx)); - ready->first = ready->veclen - 1; + if (ready->first == ready->veclen - 1) + { + if (ready->n_ready) + /* ready_lastpos() fails when called with (ready->n_ready == 0). */ + memmove (ready->vec + ready->veclen - ready->n_ready - 1, + ready_lastpos (ready), + ready->n_ready * sizeof (rtx)); + ready->first = ready->veclen - 2; + } + ready->vec[++(ready->first)] = insn; } - ready->vec[ready->first - ready->n_ready] = insn; + ready->n_ready++; + + gcc_assert (QUEUE_INDEX (insn) != QUEUE_READY); + QUEUE_INDEX (insn) = QUEUE_READY; } /* Remove the element with the highest priority from the ready list and return it. */ HAIFA_INLINE static rtx -ready_remove_first (ready) - struct ready_list *ready; +ready_remove_first (struct ready_list *ready) { rtx t; - if (ready->n_ready == 0) - abort (); + + gcc_assert (ready->n_ready); t = ready->vec[ready->first--]; ready->n_ready--; /* If the queue becomes empty, reset it. */ if (ready->n_ready == 0) ready->first = ready->veclen - 1; + + gcc_assert (QUEUE_INDEX (t) == QUEUE_READY); + QUEUE_INDEX (t) = QUEUE_NOWHERE; + return t; } -/* Sort the ready list READY by ascending priority, using the SCHED_SORT - macro. */ +/* The following code implements multi-pass scheduling for the first + cycle. In other words, we will try to choose ready insn which + permits to start maximum number of insns on the same cycle. */ -HAIFA_INLINE static void -ready_sort (ready) - struct ready_list *ready; +/* Return a pointer to the element INDEX from the ready. INDEX for + insn with the highest priority is 0, and the lowest priority has + N_READY - 1. */ + +rtx +ready_element (struct ready_list *ready, int index) +{ + gcc_assert (ready->n_ready && index < ready->n_ready); + + return ready->vec[ready->first - index]; +} + +/* Remove the element INDEX from the ready list and return it. INDEX + for insn with the highest priority is 0, and the lowest priority + has N_READY - 1. */ + +HAIFA_INLINE static rtx +ready_remove (struct ready_list *ready, int index) +{ + rtx t; + int i; + + if (index == 0) + return ready_remove_first (ready); + gcc_assert (ready->n_ready && index < ready->n_ready); + t = ready->vec[ready->first - index]; + ready->n_ready--; + for (i = index; i < ready->n_ready; i++) + ready->vec[ready->first - i] = ready->vec[ready->first - i - 1]; + QUEUE_INDEX (t) = QUEUE_NOWHERE; + return t; +} + +/* Remove INSN from the ready list. */ +static void +ready_remove_insn (rtx insn) +{ + int i; + + for (i = 0; i < readyp->n_ready; i++) + if (ready_element (readyp, i) == insn) + { + ready_remove (readyp, i); + return; + } + gcc_unreachable (); +} + +/* Sort the ready list READY by ascending priority, using the SCHED_SORT + macro. */ + +void +ready_sort (struct ready_list *ready) { rtx *first = ready_lastpos (ready); SCHED_SORT (first, ready->n_ready); @@ -943,11 +1170,10 @@ ready_sort (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 (prev) - rtx prev; +adjust_priority (rtx prev) { /* ??? There used to be code here to try and estimate how an insn affected register lifetimes, but it did it by looking at REG_DEAD @@ -958,7 +1184,37 @@ adjust_priority (prev) if (targetm.sched.adjust_priority) INSN_PRIORITY (prev) = - (*targetm.sched.adjust_priority) (prev, INSN_PRIORITY (prev)); + targetm.sched.adjust_priority (prev, INSN_PRIORITY (prev)); +} + +/* 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 (state, + targetm.sched.dfa_pre_cycle_insn ()); + + state_transition (state, NULL); + + if (targetm.sched.dfa_post_cycle_insn) + 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. */ @@ -966,213 +1222,258 @@ 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. - */ + 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 void -schedule_insn (insn, ready, clock) - rtx insn; - struct ready_list *ready; - int clock; +static int +schedule_insn (rtx insn) { - rtx link; - int unit; + sd_iterator_def sd_it; + dep_t dep; + int advance = 0; - unit = insn_unit (insn); - - if (sched_verbose >= 2) + if (sched_verbose >= 1) { - fprintf (sched_dump, ";;\t\t--> scheduling insn <<<%d>>> on unit ", - INSN_UID (insn)); - insn_print_units (insn); - fprintf (sched_dump, "\n"); - } + char buf[2048]; - if (sched_verbose && unit == -1) - visualize_no_unit (insn); + print_insn (buf, insn, 0); + buf[40] = 0; + fprintf (sched_dump, ";;\t%3i--> %-40s:", clock_var, buf); - if (MAX_BLOCKAGE > 1 || issue_rate > 1 || sched_verbose) - schedule_unit (unit, insn, clock); - - if (INSN_DEPEND (insn) == 0) - return; + if (recog_memoized (insn) < 0) + fprintf (sched_dump, "nothing"); + else + print_reservation (sched_dump, insn); + fputc ('\n', sched_dump); + } - for (link = INSN_DEPEND (insn); link != 0; link = XEXP (link, 1)) - { - rtx next = XEXP (link, 0); - int cost = insn_cost (insn, link, next); + /* Scheduling instruction should have all its dependencies resolved and + should have been removed from the ready list. */ + gcc_assert (sd_lists_empty_p (insn, SD_LIST_BACK)); - INSN_TICK (next) = MAX (INSN_TICK (next), clock + cost); + gcc_assert (QUEUE_INDEX (insn) == QUEUE_NOWHERE); + QUEUE_INDEX (insn) = QUEUE_SCHEDULED; - if ((INSN_DEP_COUNT (next) -= 1) == 0) - { - int effective_cost = INSN_TICK (next) - clock; + gcc_assert (INSN_TICK (insn) >= MIN_TICK); + 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); - if (! (*current_sched_info->new_ready) (next)) - continue; + /* ??? Probably, if INSN is scheduled prematurely, we should leave + INSN_TICK untouched. This is a machine-dependent issue, actually. */ + INSN_TICK (insn) = clock_var; - if (sched_verbose >= 2) - { - fprintf (sched_dump, ";;\t\tdependences resolved: insn %s ", - (*current_sched_info->print_insn) (next, 0)); + /* Update dependent instructions. */ + for (sd_it = sd_iterator_start (insn, SD_LIST_FORW); + sd_iterator_cond (&sd_it, &dep);) + { + rtx next = DEP_CON (dep); - if (effective_cost < 1) - fprintf (sched_dump, "into ready\n"); - else - fprintf (sched_dump, "into queue with cost=%d\n", effective_cost); - } + /* 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); - /* Adjust the priority of NEXT and either put it on the ready - list or queue it. */ - adjust_priority (next); - if (effective_cost < 1) - ready_add (ready, next); - else - queue_insn (next, effective_cost); + if (!IS_SPECULATION_BRANCHY_CHECK_P (insn)) + { + int effective_cost; + + effective_cost = try_ready (next); + + if (effective_cost >= 0 + && SCHED_GROUP_P (next) + && advance < effective_cost) + advance = effective_cost; + } + else + /* Check always has only one forward dependence (to the first insn in + the recovery block), therefore, this will be executed only once. */ + { + 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 may use this information to decide how the instruction should be aligned. */ - if (reload_completed && issue_rate > 1) + if (issue_rate > 1 + && GET_CODE (PATTERN (insn)) != USE + && GET_CODE (PATTERN (insn)) != CLOBBER) { - PUT_MODE (insn, clock > last_clock_var ? TImode : VOIDmode); - last_clock_var = clock; + if (reload_completed) + PUT_MODE (insn, clock_var > last_clock_var ? TImode : VOIDmode); + last_clock_var = clock_var; } + + return advance; } /* Functions for handling of notes. */ +/* Insert the INSN note at the end of the notes list. */ +static void +add_to_note_list (rtx insn, rtx *note_list_end_p) +{ + PREV_INSN (insn) = *note_list_end_p; + if (*note_list_end_p) + NEXT_INSN (*note_list_end_p) = insn; + *note_list_end_p = insn; +} + +/* 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 from_start; + + if (from_end == NULL) + /* It's easy when have nothing to concat. */ + return; + + if (*to_endp == NULL) + /* It's also easy when destination is empty. */ + { + *to_endp = from_end; + return; + } + + from_start = from_end; + /* A note list should be traversed via PREV_INSN. */ + while (PREV_INSN (from_start) != NULL) + from_start = PREV_INSN (from_start); + + add_to_note_list (from_start, to_endp); + *to_endp = from_end; +} + /* 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 (insn, tail) - rtx insn, tail; +unlink_other_notes (rtx insn, rtx tail) { rtx prev = PREV_INSN (insn); - while (insn != tail && GET_CODE (insn) == NOTE) + while (insn != tail && NOTE_NOT_BB_P (insn)) { rtx next = NEXT_INSN (insn); + basic_block bb = BLOCK_FOR_INSN (insn); + /* Delete the note from its current position. */ if (prev) NEXT_INSN (prev) = next; if (next) PREV_INSN (next) = prev; + if (bb) + { + /* Basic block can begin with either LABEL or + NOTE_INSN_BASIC_BLOCK. */ + gcc_assert (BB_HEAD (bb) != insn); + + /* Check if we are removing last insn in the BB. */ + if (BB_END (bb) == insn) + BB_END (bb) = prev; + } + /* See sched_analyze to see how these are handled. */ - if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG - && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_END - && NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_BEG - && NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_END - && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG - && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END) - { - /* Insert the note at the end of the notes list. */ - PREV_INSN (insn) = note_list; - if (note_list) - NEXT_INSN (note_list) = insn; - note_list = insn; - } + if (NOTE_KIND (insn) != NOTE_INSN_EH_REGION_BEG + && NOTE_KIND (insn) != NOTE_INSN_EH_REGION_END) + add_to_note_list (insn, ¬e_list); insn = next; } + + if (insn == tail) + { + gcc_assert (sel_sched_p ()); + return prev; + } + return insn; } -/* Delete line notes beginning with INSN. Record line-number notes so - they can be reused. Returns the insn following the notes. */ - -static rtx -unlink_line_notes (insn, tail) - rtx insn, tail; +/* 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) { - rtx prev = PREV_INSN (insn); + rtx beg_head = BB_HEAD (beg); + rtx beg_tail = BB_END (beg); + rtx end_head = BB_HEAD (end); + rtx end_tail = BB_END (end); - while (insn != tail && GET_CODE (insn) == NOTE) - { - rtx next = NEXT_INSN (insn); + /* Don't include any notes or labels at the beginning of the BEG + basic block, or notes at the end of the END basic blocks. */ - if (write_symbols != NO_DEBUG && NOTE_LINE_NUMBER (insn) > 0) - { - /* Delete the note from its current position. */ - if (prev) - NEXT_INSN (prev) = next; - if (next) - PREV_INSN (next) = prev; - - /* Record line-number notes so they can be reused. */ - LINE_NOTE (insn) = insn; - } - else - prev = insn; + if (LABEL_P (beg_head)) + beg_head = NEXT_INSN (beg_head); - insn = next; - } - return insn; -} + while (beg_head != beg_tail) + if (NOTE_P (beg_head)) + beg_head = NEXT_INSN (beg_head); + else + break; -/* Return the head and tail pointers of BB. */ + *headp = beg_head; -void -get_block_head_tail (b, headp, tailp) - int b; - rtx *headp; - rtx *tailp; -{ - /* HEAD and TAIL delimit the basic block being scheduled. */ - rtx head = BLOCK_HEAD (b); - rtx tail = BLOCK_END (b); - - /* Don't include any notes or labels at the beginning of the - basic block, or notes at the ends of basic blocks. */ - while (head != tail) - { - if (GET_CODE (head) == NOTE) - head = NEXT_INSN (head); - else if (GET_CODE (tail) == NOTE) - tail = PREV_INSN (tail); - else if (GET_CODE (head) == CODE_LABEL) - head = NEXT_INSN (head); - else - break; - } + if (beg == end) + end_head = beg_head; + else if (LABEL_P (end_head)) + end_head = NEXT_INSN (end_head); + + while (end_head != end_tail) + if (NOTE_P (end_tail)) + end_tail = PREV_INSN (end_tail); + else + break; - *headp = head; - *tailp = tail; + *tailp = end_tail; } /* Return nonzero if there are no real insns in the range [ HEAD, TAIL ]. */ int -no_real_insns_p (head, tail) - rtx head, tail; +no_real_insns_p (const_rtx head, const_rtx tail) { while (head != NEXT_INSN (tail)) { - if (GET_CODE (head) != NOTE && GET_CODE (head) != CODE_LABEL) + if (!NOTE_P (head) && !LABEL_P (head)) return 0; head = NEXT_INSN (head); } return 1; } -/* Delete line notes from one block. Save them so they can be later restored - (in restore_line_notes). HEAD and TAIL are the boundaries of the - block in which notes should be processed. */ - -void -rm_line_notes (head, tail) - rtx head, tail; +/* Delete notes between HEAD and TAIL and put them in the chain + of notes ended by NOTE_LIST. */ +static void +rm_other_notes (rtx head, rtx tail) { 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)) { @@ -1181,266 +1482,156 @@ rm_line_notes (head, tail) /* Farm out notes, and maybe save them in NOTE_LIST. This is needed to keep the debugger from getting completely deranged. */ - if (GET_CODE (insn) == NOTE) + if (NOTE_NOT_BB_P (insn)) { prev = insn; - insn = unlink_line_notes (insn, next_tail); - - if (prev == tail) - abort (); - if (prev == head) - abort (); - if (insn == next_tail) - abort (); + insn = unlink_other_notes (insn, next_tail); + + gcc_assert ((sel_sched_p () + || prev != tail) && prev != head && insn != next_tail); } } } -/* Save line number notes for each insn in block B. HEAD and TAIL are - the boundaries of the block in which notes should be processed. */ - +/* Same as above, but also process REG_SAVE_NOTEs of HEAD. */ void -save_line_notes (b, head, tail) - int b; - rtx head, tail; +remove_notes (rtx head, rtx tail) { - rtx next_tail; - - /* We must use the true line number for the first insn in the block - that was computed and saved at the start of this pass. We can't - use the current line number, because scheduling of the previous - block may have changed the current line number. */ - - rtx line = line_note_head[b]; - rtx insn; + /* rm_other_notes only removes notes which are _inside_ the + block---that is, it won't remove notes before the first real insn + or after the last real insn of the block. So if the first insn + has a REG_SAVE_NOTE which would otherwise be emitted before the + insn, it is redundant with the note before the start of the + block, and so we have to take it out. */ + if (INSN_P (head)) + { + rtx note; - next_tail = NEXT_INSN (tail); + for (note = REG_NOTES (head); note; note = XEXP (note, 1)) + if (REG_NOTE_KIND (note) == REG_SAVE_NOTE) + remove_note (head, note); + } - for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) - if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0) - line = insn; - else - LINE_NOTE (insn) = line; + /* Remove remaining note insns from the block, save them in + note_list. These notes are restored at the end of + schedule_block (). */ + rm_other_notes (head, tail); } -/* After a block was scheduled, insert line notes into the insns list. - HEAD and TAIL are the boundaries of the block in which notes should - be processed. */ - -void -restore_line_notes (head, tail) - rtx head, 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 line, note, prev, new; - int added_notes = 0; - rtx next_tail, insn; + if (note_list != 0) + { + rtx note_head = note_list; - head = head; - next_tail = NEXT_INSN (tail); + if (head) + head_bb = BLOCK_FOR_INSN (head); + else + head = NEXT_INSN (bb_note (head_bb)); - /* Determine the current line-number. We want to know the current - line number of the first insn of the block here, in case it is - different from the true line number that was saved earlier. If - different, then we need a line number note before the first insn - of this block. If it happens to be the same, then we don't want to - emit another line number note here. */ - for (line = head; line; line = PREV_INSN (line)) - if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0) - break; + 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); - /* Walk the insns keeping track of the current line-number and inserting - the line-number notes as needed. */ - for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) - if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0) - line = insn; - /* This used to emit line number notes before every non-deleted note. - However, this confuses a debugger, because line notes not separated - by real instructions all end up at the same address. I can find no - use for line number notes before other notes, so none are emitted. */ - else if (GET_CODE (insn) != NOTE - && INSN_UID (insn) < old_max_uid - && (note = LINE_NOTE (insn)) != 0 - && note != line - && (line == 0 - || NOTE_LINE_NUMBER (note) != NOTE_LINE_NUMBER (line) - || NOTE_SOURCE_FILE (note) != NOTE_SOURCE_FILE (line))) - { - line = note; - prev = PREV_INSN (insn); - if (LINE_NOTE (note)) - { - /* Re-use the original line-number note. */ - LINE_NOTE (note) = 0; - PREV_INSN (note) = prev; - NEXT_INSN (prev) = note; - PREV_INSN (insn) = note; - NEXT_INSN (note) = insn; - } - else - { - added_notes++; - new = emit_note_after (NOTE_LINE_NUMBER (note), prev); - NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note); - RTX_INTEGRATED_P (new) = RTX_INTEGRATED_P (note); - } - } - if (sched_verbose && added_notes) - fprintf (sched_dump, ";; added %d line-number notes\n", added_notes); -} + PREV_INSN (note_head) = PREV_INSN (head); + NEXT_INSN (PREV_INSN (head)) = note_head; + PREV_INSN (head) = note_list; + NEXT_INSN (note_list) = head; -/* After scheduling the function, delete redundant line notes from the - insns list. */ + if (BLOCK_FOR_INSN (head) != head_bb) + BB_END (head_bb) = note_list; -void -rm_redundant_line_notes () -{ - rtx line = 0; - rtx insn = get_insns (); - int active_insn = 0; - int notes = 0; - - /* Walk the insns deleting redundant line-number notes. Many of these - are already present. The remainder tend to occur at basic - block boundaries. */ - for (insn = get_last_insn (); insn; insn = PREV_INSN (insn)) - if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0) - { - /* If there are no active insns following, INSN is redundant. */ - if (active_insn == 0) - { - notes++; - NOTE_SOURCE_FILE (insn) = 0; - NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED; - } - /* If the line number is unchanged, LINE is redundant. */ - else if (line - && NOTE_LINE_NUMBER (line) == NOTE_LINE_NUMBER (insn) - && NOTE_SOURCE_FILE (line) == NOTE_SOURCE_FILE (insn)) - { - notes++; - NOTE_SOURCE_FILE (line) = 0; - NOTE_LINE_NUMBER (line) = NOTE_INSN_DELETED; - line = insn; - } - else - line = insn; - active_insn = 0; - } - else if (!((GET_CODE (insn) == NOTE - && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED) - || (GET_CODE (insn) == INSN - && (GET_CODE (PATTERN (insn)) == USE - || GET_CODE (PATTERN (insn)) == CLOBBER)))) - active_insn++; + head = note_head; + } - if (sched_verbose && notes) - fprintf (sched_dump, ";; deleted %d line-number notes\n", notes); + return head; } -/* Delete notes between HEAD and TAIL and put them in the chain - of notes ended by NOTE_LIST. */ +/* Functions for computation of registers live/usage info. */ -void -rm_other_notes (head, tail) - rtx head; - rtx tail; +/* This function looks for a new register being defined. + If the destination register is already used by the source, + a new register is not needed. */ +static int +find_set_reg_weight (const_rtx x) { - 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 (GET_CODE (x) == CLOBBER + && register_operand (SET_DEST (x), VOIDmode)) + return 1; + if (GET_CODE (x) == SET + && register_operand (SET_DEST (x), VOIDmode)) { - rtx prev; - - /* Farm out notes, and maybe save them in NOTE_LIST. - This is needed to keep the debugger from - getting completely deranged. */ - if (GET_CODE (insn) == NOTE) + if (REG_P (SET_DEST (x))) { - prev = insn; - - insn = unlink_other_notes (insn, next_tail); - - if (prev == tail) - abort (); - if (prev == head) - abort (); - if (insn == next_tail) - abort (); + if (!reg_mentioned_p (SET_DEST (x), SET_SRC (x))) + return 1; + else + return 0; } + return 1; } + return 0; } -/* Functions for computation of registers live/usage info. */ - -/* Calculate INSN_REG_WEIGHT for all insns of a block. */ - +/* Calculate INSN_REG_WEIGHT for INSN. */ static void -find_insn_reg_weight (b) - int b; +find_insn_reg_weight (const_rtx insn) { - rtx insn, next_tail, head, tail; - - get_block_head_tail (b, &head, &tail); - next_tail = NEXT_INSN (tail); - - for (insn = head; insn != next_tail; insn = NEXT_INSN (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 reg_weight = 0; - rtx x; - - /* Handle register life information. */ - if (! INSN_P (insn)) - continue; - - /* Increment weight for each register born here. */ - x = PATTERN (insn); - if ((GET_CODE (x) == SET || GET_CODE (x) == CLOBBER) - && register_operand (SET_DEST (x), VOIDmode)) - reg_weight++; - else if (GET_CODE (x) == PARALLEL) - { - int j; - for (j = XVECLEN (x, 0) - 1; j >= 0; j--) - { - x = XVECEXP (PATTERN (insn), 0, j); - if ((GET_CODE (x) == SET || GET_CODE (x) == CLOBBER) - && register_operand (SET_DEST (x), VOIDmode)) - reg_weight++; - } - } - - /* Decrement weight for each register that dies here. */ - for (x = REG_NOTES (insn); x; x = XEXP (x, 1)) + int j; + for (j = XVECLEN (x, 0) - 1; j >= 0; j--) { - if (REG_NOTE_KIND (x) == REG_DEAD - || REG_NOTE_KIND (x) == REG_UNUSED) - reg_weight--; + x = XVECEXP (PATTERN (insn), 0, j); + reg_weight += find_set_reg_weight (x); } - - INSN_REG_WEIGHT (insn) = reg_weight; } + /* Decrement weight for each register that dies here. */ + for (x = REG_NOTES (insn); x; x = XEXP (x, 1)) + { + if (REG_NOTE_KIND (x) == REG_DEAD + || REG_NOTE_KIND (x) == REG_UNUSED) + reg_weight--; + } + + INSN_REG_WEIGHT (insn) = reg_weight; } -/* Scheduling clock, modified in schedule_block() and queue_to_ready (). */ -static int clock_var; - /* Move insns that became ready to fire from queue to ready list. */ static void -queue_to_ready (ready) - struct ready_list *ready; +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); + 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)) @@ -1452,11 +1643,25 @@ queue_to_ready (ready) fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ", (*current_sched_info->print_insn) (insn, 0)); - ready_add (ready, insn); - if (sched_verbose >= 2) - fprintf (sched_dump, "moving to ready without stalls\n"); + /* 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) + && insn != skip_insn) + { + if (sched_verbose >= 2) + fprintf (sched_dump, "requeued because ready full\n"); + queue_insn (insn, 1); + } + else + { + ready_add (ready, insn, false); + if (sched_verbose >= 2) + fprintf (sched_dump, "moving to ready without stalls\n"); + } } - insn_queue[q_ptr] = 0; + free_INSN_LIST_list (&insn_queue[q_ptr]); /* If there are no ready insns, stall until one is ready and add all of the pending insns at that point to the ready list. */ @@ -1464,7 +1669,7 @@ queue_to_ready (ready) { int stalls; - for (stalls = 1; stalls < INSN_QUEUE_SIZE; stalls++) + for (stalls = 1; stalls <= max_insn_queue_index; stalls++) { if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)])) { @@ -1477,170 +1682,690 @@ queue_to_ready (ready) fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ", (*current_sched_info->print_insn) (insn, 0)); - ready_add (ready, insn); + ready_add (ready, insn, false); if (sched_verbose >= 2) fprintf (sched_dump, "moving to ready with %d stalls\n", stalls); } - insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = 0; + free_INSN_LIST_list (&insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]); - if (ready->n_ready) - break; + advance_one_cycle (); + + break; } + + advance_one_cycle (); } - if (sched_verbose && stalls) - visualize_stall_cycles (stalls); q_ptr = NEXT_Q_AFTER (q_ptr, stalls); clock_var += stalls; } } -/* Print the ready list for debugging purposes. Callable from debugger. */ - -static void -debug_ready_list (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 + uses the hook to check whether there exist any dependences which are + 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 + addition) depending on user flags and target hooks. */ + +static bool +ok_for_early_queue_removal (rtx insn) { - rtx *p; - int i; + int n_cycles; + rtx prev_insn = last_scheduled_insn; - if (ready->n_ready == 0) - return; + if (targetm.sched.is_costly_dependence) + { + for (n_cycles = flag_sched_stalled_insns_dep; n_cycles; n_cycles--) + { + for ( ; prev_insn; prev_insn = PREV_INSN (prev_insn)) + { + int cost; - 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, "\n"); -} + if (prev_insn == current_sched_info->prev_head) + { + prev_insn = NULL; + break; + } -/* move_insn1: Remove INSN from insn chain, and link it after LAST insn. */ + if (!NOTE_P (prev_insn)) + { + dep_t dep; -static rtx -move_insn1 (insn, last) - rtx insn, last; -{ - NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn); - PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn); + dep = sd_find_dep_between (prev_insn, insn, true); - NEXT_INSN (insn) = NEXT_INSN (last); - PREV_INSN (NEXT_INSN (last)) = insn; + if (dep != NULL) + { + cost = dep_cost (dep); - NEXT_INSN (last) = insn; - PREV_INSN (insn) = last; + if (targetm.sched.is_costly_dependence (dep, cost, + flag_sched_stalled_insns_dep - n_cycles)) + return false; + } + } - return insn; + if (GET_MODE (prev_insn) == TImode) /* end of dispatch group */ + break; + } + + if (!prev_insn) + break; + prev_insn = PREV_INSN (prev_insn); + } + } + + return true; } -/* Search INSN for REG_SAVE_NOTE note pairs for - NOTE_INSN_{LOOP,EHREGION}_{BEG,END}; and convert them back into + +/* Remove insns from the queue, before they become "ready" with respect + to FU latency considerations. */ + +static int +early_queue_to_ready (state_t state, struct ready_list *ready) +{ + rtx insn; + rtx link; + rtx next_link; + rtx prev_link; + bool move_to_ready; + int cost; + state_t temp_state = alloca (dfa_state_size); + int stalls; + int insns_removed = 0; + + /* + 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 + prematurely. (flag_sched_stalled_insns = -1). + + 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) + return 0; + + for (stalls = 0; stalls <= max_insn_queue_index; stalls++) + { + if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)])) + { + if (sched_verbose > 6) + fprintf (sched_dump, ";; look at index %d + %d\n", q_ptr, stalls); + + prev_link = 0; + while (link) + { + next_link = XEXP (link, 1); + insn = XEXP (link, 0); + if (insn && sched_verbose > 6) + print_rtl_single (sched_dump, insn); + + memcpy (temp_state, state, dfa_state_size); + if (recog_memoized (insn) < 0) + /* non-negative to indicate that it's not ready + to avoid infinite Q->R->Q->R... */ + cost = 0; + else + cost = state_transition (temp_state, insn); + + if (sched_verbose >= 6) + fprintf (sched_dump, "transition cost = %d\n", cost); + + move_to_ready = false; + if (cost < 0) + { + move_to_ready = ok_for_early_queue_removal (insn); + if (move_to_ready == true) + { + /* move from Q to R */ + q_size -= 1; + ready_add (ready, insn, false); + + if (prev_link) + XEXP (prev_link, 1) = next_link; + else + insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = next_link; + + free_INSN_LIST_node (link); + + if (sched_verbose >= 2) + fprintf (sched_dump, ";;\t\tEarly Q-->Ready: insn %s\n", + (*current_sched_info->print_insn) (insn, 0)); + + insns_removed++; + if (insns_removed == flag_sched_stalled_insns) + /* Remove no more than flag_sched_stalled_insns insns + from Q at a time. */ + return insns_removed; + } + } + + if (move_to_ready == false) + prev_link = link; + + link = next_link; + } /* while link */ + } /* if link */ + + } /* for stalls.. */ + + return insns_removed; +} + + +/* Print the ready list for debugging purposes. Callable from debugger. */ + +static void +debug_ready_list (struct ready_list *ready) +{ + rtx *p; + int i; + + if (ready->n_ready == 0) + { + fprintf (sched_dump, "\n"); + return; + } + + 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, "\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. LAST is the last instruction - output by the instruction scheduler. Return the new value of LAST. */ - -static rtx -reemit_notes (insn, last) - rtx insn; - rtx last; + NOTE_INSN_EH_REGION_{BEG,END} NOTEs. */ +void +reemit_notes (rtx insn) { - rtx note, retval; + rtx note, last = insn; - retval = last; for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) { if (REG_NOTE_KIND (note) == REG_SAVE_NOTE) { enum insn_note note_type = INTVAL (XEXP (note, 0)); - if (note_type == NOTE_INSN_RANGE_BEG - || note_type == NOTE_INSN_RANGE_END) + last = emit_note_before (note_type, last); + remove_note (insn, note); + } + } +} + +/* Move INSN. Reemit notes if needed. Update CFG, if needed. */ +static void +move_insn (rtx insn, rtx last, rtx nt) +{ + if (PREV_INSN (insn) != last) + { + basic_block bb; + rtx note; + int jump_p = 0; + + bb = BLOCK_FOR_INSN (insn); + + /* BB_HEAD is either LABEL or NOTE. */ + gcc_assert (BB_HEAD (bb) != insn); + + if (BB_END (bb) == insn) + /* If this is last instruction in BB, move end marker one + instruction up. */ + { + /* Jumps are always placed at the end of basic block. */ + jump_p = control_flow_insn_p (insn); + + gcc_assert (!jump_p + || ((common_sched_info->sched_pass_id == SCHED_RGN_PASS) + && IS_SPECULATION_BRANCHY_CHECK_P (insn)) + || (common_sched_info->sched_pass_id + == SCHED_EBB_PASS)); + + gcc_assert (BLOCK_FOR_INSN (PREV_INSN (insn)) == bb); + + BB_END (bb) = PREV_INSN (insn); + } + + gcc_assert (BB_END (bb) != last); + + if (jump_p) + /* We move the block note along with jump. */ + { + gcc_assert (nt); + + note = NEXT_INSN (insn); + while (NOTE_NOT_BB_P (note) && note != nt) + note = NEXT_INSN (note); + + if (note != nt + && (LABEL_P (note) + || BARRIER_P (note))) + note = NEXT_INSN (note); + + gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note)); + } + else + note = insn; + + NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (note); + PREV_INSN (NEXT_INSN (note)) = PREV_INSN (insn); + + NEXT_INSN (note) = NEXT_INSN (last); + PREV_INSN (NEXT_INSN (last)) = note; + + NEXT_INSN (last) = insn; + PREV_INSN (insn) = last; + + bb = BLOCK_FOR_INSN (last); + + if (jump_p) + { + fix_jump_move (insn); + + if (BLOCK_FOR_INSN (insn) != bb) + move_block_after_check (insn); + + gcc_assert (BB_END (bb) == last); + } + + df_insn_change_bb (insn, bb); + + /* Update BB_END, if needed. */ + if (BB_END (bb) == last) + BB_END (bb) = insn; + } + + SCHED_GROUP_P (insn) = 0; +} + +/* The following structure describe an entry of the stack of choices. */ +struct choice_entry +{ + /* Ordinal number of the issued insn in the ready queue. */ + int index; + /* The number of the rest insns whose issues we should try. */ + int rest; + /* The number of issued essential insns. */ + int n; + /* State after issuing the insn. */ + state_t state; +}; + +/* The following array is used to implement a stack of choices used in + function max_issue. */ +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. */ +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 + this value as constant*(DFA_LOOKAHEAD**ISSUE_RATE). We would not + need this constraint if all real insns (with non-negative codes) + had reservations because in this case the algorithm complexity is + O(DFA_LOOKAHEAD**ISSUE_RATE). Unfortunately, the dfa descriptions + might be incomplete and such insn might occur. For such + descriptions, the complexity of algorithm (without the constraint) + could achieve DFA_LOOKAHEAD ** N , where N is the queue length. */ +static int max_lookahead_tries; + +/* The following value is value of hook + `first_cycle_multipass_dfa_lookahead' at the last call of + `max_issue'. */ +static int cached_first_cycle_multipass_dfa_lookahead = 0; + +/* The following value is value of `issue_rate' at the last call of + `sched_init'. */ +static int cached_issue_rate = 0; + +/* The following function returns maximal (or close to maximal) number + of insns which can be issued on the same cycle and one of which + insns is insns with the best rank (the first insn in READY). To + make this function tries different samples of ready insns. READY + is current queue `ready'. Global array READY_TRY reflects what + insns are already issued in this try. MAX_POINTS is the sum of points + of all instructions in READY. The function stops immediately, + 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. + + 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, 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; + + top = choice_stack; + + /* Set initial state of the search. */ + memcpy (top->state, state, dfa_state_size); + top->rest = dfa_lookahead; + top->n = 0; + + /* 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 (/* 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) { - last = emit_note_before (note_type, last); - remove_note (insn, note); - note = XEXP (note, 1); - NOTE_RANGE_INFO (last) = XEXP (note, 0); + 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; + points = top->n; + if (top->n == max_points || best == all) + break; + } } - else + + /* 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 (state, top->state, dfa_state_size); + } + else if (!ready_try [i]) + { + tries_num++; + if (tries_num > max_lookahead_tries) + break; + insn = ready_element (ready, i); + delay = state_transition (state, insn); + if (delay < 0) { - last = emit_note_before (note_type, last); - remove_note (insn, note); - note = XEXP (note, 1); - if (note_type == NOTE_INSN_EH_REGION_BEG - || note_type == NOTE_INSN_EH_REGION_END) - NOTE_EH_HANDLER (last) = INTVAL (XEXP (note, 0)); + if (state_dead_lock_p (state)) + top->rest = 0; + else + top->rest--; + + n = top->n; + if (memcmp (top->state, state, dfa_state_size) != 0) + n += ISSUE_POINTS (insn); + + /* Advance to the next choice_entry. */ + top++; + /* Initialize it. */ + top->rest = dfa_lookahead; + top->index = i; + top->n = n; + memcpy (top->state, state, dfa_state_size); + + ready_try [i] = 1; + i = -1; } - remove_note (insn, note); } + + /* Increase ready-list index. */ + i++; } - return retval; -} -/* Move INSN, and all insns which should be issued before it, - due to SCHED_GROUP_P flag. Reemit notes if needed. + /* Restore the original state of the DFA. */ + memcpy (state, choice_stack->state, dfa_state_size); - Return the last insn emitted by the scheduler, which is the - return value from the first call to reemit_notes. */ + return best; +} -static rtx -move_insn (insn, last) - rtx insn, last; +/* The following function chooses insn from READY and modifies + 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) { - rtx retval = NULL; + int lookahead; - /* If INSN has SCHED_GROUP_P set, then issue it and any other - insns with SCHED_GROUP_P set first. */ - while (SCHED_GROUP_P (insn)) + if (dbg_cnt (sched_insn) == false) { - rtx prev = PREV_INSN (insn); + rtx insn; - /* Move a SCHED_GROUP_P insn. */ - move_insn1 (insn, last); - /* If this is the first call to reemit_notes, then record - its return value. */ - if (retval == NULL_RTX) - retval = reemit_notes (insn, insn); - else - reemit_notes (insn, insn); - /* Consume SCHED_GROUP_P flag. */ - SCHED_GROUP_P (insn) = 0; - insn = prev; + 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; } - /* Now move the first non SCHED_GROUP_P insn. */ - move_insn1 (insn, last); + lookahead = 0; - /* If this is the first call to reemit_notes, then record - its return value. */ - if (retval == NULL_RTX) - retval = reemit_notes (insn, insn); + 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))) + { + *insn_ptr = ready_remove_first (ready); + return 0; + } else - reemit_notes (insn, insn); + { + /* Try to choose the better insn. */ + int index = 0, i, n; + rtx insn; + int try_data = 1, try_control = 1; + ds_t ts; + + insn = ready_element (ready, 0); + if (INSN_CODE (insn) < 0) + { + *insn_ptr = ready_remove_first (ready); + return 0; + } - return retval; -} + if (spec_info + && spec_info->flags & (PREFER_NON_DATA_SPEC + | PREFER_NON_CONTROL_SPEC)) + { + for (i = 0, n = ready->n_ready; i < n; i++) + { + rtx x; + ds_t s; + + 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)) + { + try_control = 0; + if (!(spec_info->flags & PREFER_NON_DATA_SPEC) || !try_data) + break; + } + } + } -/* Called from backends from targetm.sched.reorder to emit stuff into - the instruction stream. */ + 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 1; + } -rtx -sched_emit_insn (pat) - rtx pat; -{ - rtx insn = emit_insn_after (pat, last_scheduled_insn); - last_scheduled_insn = insn; - return insn; + ready_try[0] = 0; + + for (i = 1; i < ready->n_ready; i++) + { + insn = ready_element (ready, i); + + ready_try [i] + = ((!try_data && (TODO_SPEC (insn) & DATA_SPEC)) + || (!try_control && (TODO_SPEC (insn) & CONTROL_SPEC))); + } + + /* 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 + { + 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; + } + } } -/* Use forward list scheduling to rearrange insns of block B in region RGN, - possibly bringing insns from subsequent blocks in the same region. */ +/* Use forward list scheduling to rearrange insns of block pointed to by + TARGET_BB, possibly bringing insns from subsequent blocks in the same + region. */ void -schedule_block (b, rgn_n_insns) - int b; - int rgn_n_insns; +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. */ + int sort_p, advance, start_clock_var; /* Head/tail info for this block. */ rtx prev_head = current_sched_info->prev_head; @@ -1655,356 +2380,2632 @@ schedule_block (b, rgn_n_insns) and caused problems because schedule_block and compute_forward_dependences had different notions of what the "head" insn was. */ - if (head == tail && (! INSN_P (head))) - abort (); + gcc_assert (head != tail || INSN_P (head)); + + haifa_recovery_bb_recently_added_p = false; /* Debug info. */ if (sched_verbose) - { - fprintf (sched_dump, ";; ======================================================\n"); - fprintf (sched_dump, - ";; -- basic block %d from %d to %d -- %s reload\n", - b, INSN_UID (head), INSN_UID (tail), - (reload_completed ? "after" : "before")); - fprintf (sched_dump, ";; ======================================================\n"); - fprintf (sched_dump, "\n"); - - visualize_alloc (); - init_block_visualization (); - } + dump_new_block_header (0, *target_bb, head, tail); - clear_units (); + state_reset (curr_state); - /* Allocate the ready list. */ - ready.veclen = rgn_n_insns + 1 + issue_rate; + /* Clear the ready list. */ ready.first = ready.veclen - 1; - ready.vec = (rtx *) xmalloc (ready.veclen * sizeof (rtx)); ready.n_ready = 0; - (*current_sched_info->init_ready_list) (&ready); + /* It is used for first cycle multipass scheduling. */ + temp_state = alloca (dfa_state_size); if (targetm.sched.md_init) - (*targetm.sched.md_init) (sched_dump, sched_verbose, ready.veclen); + targetm.sched.md_init (sched_dump, sched_verbose, ready.veclen); /* We start inserting insns after PREV_HEAD. */ last_scheduled_insn = prev_head; + gcc_assert (NOTE_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 queue. */ q_ptr = 0; q_size = 0; - last_clock_var = 0; - memset ((char *) insn_queue, 0, sizeof (insn_queue)); + + 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; - /* Loop until all the insns in BB are scheduled. */ - while ((*current_sched_info->schedule_more_p) ()) - { - clock_var++; + /* 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) (); - /* Add to the ready list all pending insns that can be issued now. - If there are no ready insns, increment clock until one - is ready and add all pending insns at that point to the ready - list. */ - queue_to_ready (&ready); + /* 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) + { + ready_sort (&ready); - if (ready.n_ready == 0) - abort (); + /* Find first free-standing insn past MAX_SCHED_READY_INSNS. */ + for (i = MAX_SCHED_READY_INSNS; i < ready.n_ready; i++) + if (!SCHED_GROUP_P (ready_element (&ready, i))) + break; if (sched_verbose >= 2) { - fprintf (sched_dump, ";;\t\tReady list after queue_to_ready: "); - debug_ready_list (&ready); + fprintf (sched_dump, + ";;\t\tReady list on entry: %d insns\n", ready.n_ready); + fprintf (sched_dump, + ";;\t\t before reload => truncated to %d insns\n", i); } - /* Sort the ready list based on priority. */ - ready_sort (&ready); + /* 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; - /* Allow the target to reorder the list, typically for - better instruction bundling. */ - if (targetm.sched.reorder) - can_issue_more = - (*targetm.sched.reorder) (sched_dump, sched_verbose, - ready_lastpos (&ready), - &ready.n_ready, clock_var); - else - can_issue_more = issue_rate; + if (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); + } + } + } - if (sched_verbose && targetm.sched.cycle_display) - last_scheduled_insn - = (*targetm.sched.cycle_display) (clock_var, last_scheduled_insn); + /* Now we can restore basic block notes and maintain precise cfg. */ + restore_bb_notes (*target_bb); - if (sched_verbose) + last_clock_var = -1; + + advance = 0; + + sort_p = TRUE; + /* Loop until all the insns in BB are scheduled. */ + while ((*current_sched_info->schedule_more_p) ()) + { + do { - fprintf (sched_dump, "\n;;\tReady list (t =%3d): ", clock_var); - debug_ready_list (&ready); + start_clock_var = clock_var; + + clock_var++; + + advance_one_cycle (); + + /* Add to the ready list all pending insns that can be issued now. + If there are no ready insns, increment clock until one + is ready and add all pending insns at that point to the ready + list. */ + queue_to_ready (&ready); + + gcc_assert (ready.n_ready); + + if (sched_verbose >= 2) + { + fprintf (sched_dump, ";;\t\tReady list after queue_to_ready: "); + debug_ready_list (&ready); + } + advance -= clock_var - start_clock_var; } + while (advance > 0); - /* Issue insns from ready list. */ - while (ready.n_ready != 0 - && can_issue_more - && (*current_sched_info->schedule_more_p) ()) + if (sort_p) { - /* Select and remove the insn from the ready list. */ - rtx insn = ready_remove_first (&ready); - int cost = actual_hazard (insn_unit (insn), insn, clock_var, 0); + /* Sort the ready list based on priority. */ + ready_sort (&ready); - if (cost >= 1) + if (sched_verbose >= 2) { - queue_insn (insn, cost); - continue; + fprintf (sched_dump, ";;\t\tReady list after ready_sort: "); + debug_ready_list (&ready); } + } - if (! (*current_sched_info->can_schedule_ready_p) (insn)) - goto next; - - last_scheduled_insn = move_insn (insn, last_scheduled_insn); + /* Allow the target to reorder the list, typically for + better instruction bundling. */ + if (sort_p && targetm.sched.reorder + && (ready.n_ready == 0 + || !SCHED_GROUP_P (ready_element (&ready, 0)))) + can_issue_more = + targetm.sched.reorder (sched_dump, sched_verbose, + ready_lastpos (&ready), + &ready.n_ready, clock_var); + else + can_issue_more = issue_rate; - if (targetm.sched.variable_issue) - can_issue_more = - (*targetm.sched.variable_issue) (sched_dump, sched_verbose, - 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--; + first_cycle_insn_p = 1; + cycle_issued_insns = 0; + for (;;) + { + rtx insn; + int cost; + bool asm_p = false; - schedule_insn (insn, &ready, clock_var); + if (sched_verbose >= 2) + { + fprintf (sched_dump, ";;\tReady list (t = %3d): ", + clock_var); + debug_ready_list (&ready); + } - next: - if (targetm.sched.reorder2) + if (ready.n_ready == 0 + && can_issue_more + && reload_completed) { - /* Sort the ready list based on priority. */ - if (ready.n_ready > 0) + /* Allow scheduling insns directly from the queue in case + there's nothing better to do (ready list is empty) but + there are still vacant dispatch slots in the current cycle. */ + if (sched_verbose >= 6) + fprintf (sched_dump,";;\t\tSecond chance\n"); + memcpy (temp_state, curr_state, dfa_state_size); + if (early_queue_to_ready (temp_state, &ready)) ready_sort (&ready); - can_issue_more = - (*targetm.sched.reorder2) (sched_dump,sched_verbose, - ready.n_ready - ? ready_lastpos (&ready) : NULL, - &ready.n_ready, clock_var); } - } - - /* Debug info. */ - if (sched_verbose) - visualize_scheduled_insns (clock_var); - } - if (targetm.sched.md_finish) - (*targetm.sched.md_finish) (sched_dump, sched_verbose); + if (ready.n_ready == 0 || !can_issue_more + || state_dead_lock_p (curr_state) + || !(*current_sched_info->schedule_more_p) ()) + break; - /* Debug info. */ - if (sched_verbose) - { - fprintf (sched_dump, ";;\tReady list (final): "); - debug_ready_list (&ready); - print_block_visualization (""); - } + /* Select and remove the insn from the ready list. */ + if (sort_p) + { + int res; - /* Sanity check -- queue must be empty now. Meaningless if region has - multiple bbs. */ - if (current_sched_info->queue_must_finish_empty && q_size != 0) - abort (); + insn = NULL_RTX; + res = choose_ready (&ready, &insn); - /* Update head/tail boundaries. */ - head = NEXT_INSN (prev_head); - tail = last_scheduled_insn; + if (res < 0) + /* Finish cycle. */ + break; + if (res > 0) + /* Restart choose_ready (). */ + continue; - /* 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) + gcc_assert (insn != NULL_RTX); + } + else + insn = ready_remove_first (&ready); + + if (targetm.sched.dfa_new_cycle + && targetm.sched.dfa_new_cycle (sched_dump, sched_verbose, + insn, last_clock_var, + clock_var, &sort_p)) + /* SORT_P is used by the target to override sorting + of the ready list. This is needed when the target + has modified its internal structures expecting that + the insn will be issued next. As we need the insn + 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 + current_sched_info->can_schedule_ready_p, hence, won't + be issued next. */ + { + ready_add (&ready, insn, true); + break; + } + + sort_p = TRUE; + memcpy (temp_state, curr_state, dfa_state_size); + if (recog_memoized (insn) < 0) + { + asm_p = (GET_CODE (PATTERN (insn)) == ASM_INPUT + || asm_noperands (PATTERN (insn)) >= 0); + if (!first_cycle_insn_p && asm_p) + /* This is asm insn which is tried to be issued on the + cycle not first. Issue it on the next cycle. */ + cost = 1; + else + /* A USE insn, or something else we don't need to + understand. We can't pass these directly to + state_transition because it will trigger a + fatal error for unrecognizable insns. */ + cost = 0; + } + else + { + cost = state_transition (temp_state, insn); + if (cost < 0) + cost = 0; + else if (cost == 0) + cost = 1; + } + + if (cost >= 1) + { + queue_insn (insn, cost); + if (SCHED_GROUP_P (insn)) + { + advance = cost; + break; + } + + continue; + } + + if (current_sched_info->can_schedule_ready_p + && ! (*current_sched_info->can_schedule_ready_p) (insn)) + /* We normally get here only if we don't want to move + insn from the split block. */ + { + TODO_SPEC (insn) = (TODO_SPEC (insn) & ~SPECULATIVE) | HARD_DEP; + continue; + } + + /* DECISION is made. */ + + if (TODO_SPEC (insn) & SPECULATIVE) + generate_recovery_code (insn); + + if (control_flow_insn_p (last_scheduled_insn) + /* This is used to switch basic blocks by request + from scheduler front-end (actually, sched-ebb.c only). + This is used to process blocks with single fallthru + edge. If succeeding block has jump, it [jump] will try + move at the end of current bb, thus corrupting CFG. */ + || current_sched_info->advance_target_bb (*target_bb, insn)) + { + *target_bb = current_sched_info->advance_target_bb + (*target_bb, 0); + + if (sched_verbose) + { + rtx x; + + x = next_real_insn (last_scheduled_insn); + gcc_assert (x); + dump_new_block_header (1, *target_bb, x, tail); + } + + last_scheduled_insn = bb_note (*target_bb); + } + + /* Update counters, etc in the scheduler's front end. */ + (*current_sched_info->begin_schedule_ready) (insn, + last_scheduled_insn); + + move_insn (insn, last_scheduled_insn, current_sched_info->next_tail); + reemit_notes (insn); + last_scheduled_insn = insn; + + if (memcmp (curr_state, temp_state, dfa_state_size) != 0) + { + cycle_issued_insns++; + memcpy (curr_state, temp_state, dfa_state_size); + } + + if (targetm.sched.variable_issue) + can_issue_more = + targetm.sched.variable_issue (sched_dump, sched_verbose, + insn, can_issue_more); + /* A naked CLOBBER or USE generates no instruction, so do + not count them against the issue rate. */ + else if (GET_CODE (PATTERN (insn)) != USE + && GET_CODE (PATTERN (insn)) != CLOBBER) + can_issue_more--; + + advance = schedule_insn (insn); + + /* After issuing an asm insn we should start a new cycle. */ + if (advance == 0 && asm_p) + advance = 1; + if (advance != 0) + break; + + first_cycle_insn_p = 0; + + /* Sort the ready list based on priority. This must be + redone here, as schedule_insn may have readied additional + insns that will not be sorted correctly. */ + if (ready.n_ready > 0) + ready_sort (&ready); + + if (targetm.sched.reorder2 + && (ready.n_ready == 0 + || !SCHED_GROUP_P (ready_element (&ready, 0)))) + { + can_issue_more = + targetm.sched.reorder2 (sched_dump, sched_verbose, + ready.n_ready + ? ready_lastpos (&ready) : NULL, + &ready.n_ready, clock_var); + } + } + } + + /* Debug info. */ + if (sched_verbose) { - rtx note_head = note_list; + fprintf (sched_dump, ";;\tReady list (final): "); + debug_ready_list (&ready); + } - while (PREV_INSN (note_head)) + 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 + { + /* We must maintain QUEUE_INDEX between blocks in region. */ + for (i = ready.n_ready - 1; i >= 0; i--) { - note_head = PREV_INSN (note_head); + rtx x; + + x = ready_element (&ready, i); + QUEUE_INDEX (x) = QUEUE_NOWHERE; + TODO_SPEC (x) = (TODO_SPEC (x) & ~SPECULATIVE) | HARD_DEP; } - 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; + if (q_size) + for (i = 0; i <= max_insn_queue_index; i++) + { + rtx link; + for (link = insn_queue[i]; link; link = XEXP (link, 1)) + { + rtx x; + + x = XEXP (link, 0); + QUEUE_INDEX (x) = QUEUE_NOWHERE; + TODO_SPEC (x) = (TODO_SPEC (x) & ~SPECULATIVE) | HARD_DEP; + } + free_INSN_LIST_list (&insn_queue[i]); + } } - /* Debugging. */ if (sched_verbose) + fprintf (sched_dump, ";; total time = %d\n", clock_var); + + if (!current_sched_info->queue_must_finish_empty + || 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 + blocks of the region. We should use a correct value of + `clock_var' or modify INSN_TICK. It is better to keep + clock_var value equal to 0 at the start of a basic block. + Therefore we modify INSN_TICK here. */ + fix_inter_tick (NEXT_INSN (prev_head), last_scheduled_insn); + } + + if (targetm.sched.md_finish) { - 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)); - visualize_free (); + 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; + + head = restore_other_notes (head, NULL); + current_sched_info->head = head; current_sched_info->tail = tail; - - free (ready.vec); } /* Set_priorities: compute priority of each insn in the block. */ int -set_priorities (head, tail) - rtx head, tail; +set_priorities (rtx head, rtx tail) { rtx insn; int n_insn; - + int sched_max_insns_priority = + current_sched_info->sched_max_insns_priority; rtx prev_head; - prev_head = PREV_INSN (head); - if (head == tail && (! INSN_P (head))) return 0; n_insn = 0; + + prev_head = PREV_INSN (head); for (insn = tail; insn != prev_head; insn = PREV_INSN (insn)) { - if (GET_CODE (insn) == NOTE) + if (!INSN_P (insn)) continue; - if (!(SCHED_GROUP_P (insn))) - n_insn++; + n_insn++; (void) 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; + return n_insn; } -/* Initialize some global state for the scheduler. DUMP_FILE is to be used - for debugging output. */ - +/* 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 -sched_init (dump_file) - FILE *dump_file; +setup_sched_dump (void) { - int luid, b; - rtx insn; + 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. 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) +{ /* 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); + /* Initialize SPEC_INFO. */ + if (targetm.sched.set_sched_flags) + { + spec_info = &spec_info_var; + targetm.sched.set_sched_flags (spec_info); + + 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 = NULL; + + } + else + /* So we won't read anything accidentally. */ + spec_info = 0; /* Initialize issue_rate. */ if (targetm.sched.issue_rate) - issue_rate = (*targetm.sched.issue_rate) (); + issue_rate = targetm.sched.issue_rate (); else issue_rate = 1; - /* We use LUID 0 for the fake insn (UID 0) which holds dependencies for - pseudos which do not cross calls. */ - old_max_uid = get_max_uid () + 1; + if (cached_issue_rate != issue_rate) + { + cached_issue_rate = issue_rate; + /* To invalidate max_lookahead_tries: */ + cached_first_cycle_multipass_dfa_lookahead = 0; + } - h_i_d = (struct haifa_insn_data *) xcalloc (old_max_uid, sizeof (*h_i_d)); + if (targetm.sched.first_cycle_multipass_dfa_lookahead) + dfa_lookahead = targetm.sched.first_cycle_multipass_dfa_lookahead (); + else + dfa_lookahead = 0; - h_i_d[0].luid = 0; - luid = 1; - for (b = 0; b < n_basic_blocks; b++) - for (insn = BLOCK_HEAD (b);; insn = NEXT_INSN (insn)) - { - INSN_LUID (insn) = luid; + if (targetm.sched.init_dfa_pre_cycle_insn) + targetm.sched.init_dfa_pre_cycle_insn (); - /* 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 (GET_CODE (insn) != NOTE) - ++luid; + if (targetm.sched.init_dfa_post_cycle_insn) + targetm.sched.init_dfa_post_cycle_insn (); - if (insn == BLOCK_END (b)) - break; - } + dfa_start (); + dfa_state_size = state_size (); - init_dependency_caches (luid); + init_alias_analysis (); - compute_bb_for_insn (old_max_uid); + df_set_flags (DF_LR_RUN_DCE); + df_note_add_problem (); - init_alias_analysis (); + /* 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); + } + + df_analyze (); + + /* Do not run DCE after reload, as this can kill nops inserted + by bundling. */ + if (reload_completed) + df_clear_flags (DF_LR_RUN_DCE); + + regstat_compute_calls_crossed (); + + if (targetm.sched.md_init_global) + targetm.sched.md_init_global (sched_dump, sched_verbose, + get_max_uid () + 1); + + curr_state = xmalloc (dfa_state_size); +} + +static void haifa_init_only_bb (basic_block, basic_block); - if (write_symbols != NO_DEBUG) +/* 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. + 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 + + 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 +haifa_sched_finish (void) +{ + sched_create_empty_bb = NULL; + sched_split_block = NULL; + sched_init_only_bb = NULL; + + if (spec_info && spec_info->dump) { - rtx line; + char c = reload_completed ? 'a' : 'b'; + + fprintf (spec_info->dump, + ";; %s:\n", current_function_name ()); + + fprintf (spec_info->dump, + ";; Procedure %cr-begin-data-spec motions == %d\n", + c, nr_begin_data); + fprintf (spec_info->dump, + ";; Procedure %cr-be-in-data-spec motions == %d\n", + c, nr_be_in_data); + fprintf (spec_info->dump, + ";; Procedure %cr-begin-control-spec motions == %d\n", + c, nr_begin_control); + fprintf (spec_info->dump, + ";; Procedure %cr-be-in-control-spec motions == %d\n", + 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 (); +} - line_note_head = (rtx *) xcalloc (n_basic_blocks, sizeof (rtx)); +/* Free global data used during insn scheduling. This function works with + the common data shared between the schedulers. */ - /* Save-line-note-head: - Determine the line-number at the start of each basic block. - This must be computed and saved now, because after a basic block's - predecessor has been scheduled, it is impossible to accurately - determine the correct line number for the first insn of the block. */ +void +sched_finish (void) +{ + haifa_finish_h_i_d (); + 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 +} - for (b = 0; b < n_basic_blocks; b++) +/* Fix INSN_TICKs of the instructions in the current block as well as + INSN_TICKs of their dependents. + HEAD and TAIL are the begin and the end of the current scheduled block. */ +static void +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. */ + for (tail = NEXT_INSN (tail); head != tail; head = NEXT_INSN (head)) + { + if (INSN_P (head)) { - for (line = BLOCK_HEAD (b); line; line = PREV_INSN (line)) - if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0) - { - line_note_head[b] = line; - break; - } - /* Do a forward search as well, since we won't get to see the first - notes in a basic block. */ - for (line = BLOCK_HEAD (b); line; line = NEXT_INSN (line)) + int tick; + 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))) { - if (INSN_P (line)) - break; - if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0) - line_note_head[b] = line; + bitmap_set_bit (&processed, INSN_LUID (head)); + tick -= next_clock; + + if (tick < MIN_TICK) + tick = MIN_TICK; + + INSN_TICK (head) = tick; + } + + FOR_EACH_DEP (head, SD_LIST_RES_FORW, sd_it, dep) + { + rtx next; + + next = DEP_CON (dep); + tick = INSN_TICK (next); + + if (tick != INVALID_TICK + /* If NEXT has its INSN_TICK calculated, fix it. + If not - it will be properly calculated from + scratch later in fix_tick_ready. */ + && !bitmap_bit_p (&processed, INSN_LUID (next))) + { + bitmap_set_bit (&processed, INSN_LUID (next)); + 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; + } } } } + bitmap_clear (&processed); +} - /* Find units used in this function, for visualization. */ - if (sched_verbose) - init_target_units (); +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: + -1 - is not ready yet, + 0 - added to the ready list, + 0 < N - queued for N cycles. */ +int +try_ready (rtx next) +{ + ds_t old_ts, *ts; + + ts = &TODO_SPEC (next); + old_ts = *ts; + + gcc_assert (!(old_ts & ~(SPECULATIVE | HARD_DEP)) + && ((old_ts & HARD_DEP) + || (old_ts & SPECULATIVE))); + + if (sd_lists_empty_p (next, SD_LIST_BACK)) + /* NEXT has all its dependencies resolved. */ + { + /* 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. */ - /* ??? Add a NOTE after the last insn of the last basic block. It is not - known why this is done. */ + *ts &= ~SPECULATIVE & ~HARD_DEP; - insn = BLOCK_END (n_basic_blocks - 1); - if (NEXT_INSN (insn) == 0 - || (GET_CODE (insn) != NOTE - && GET_CODE (insn) != CODE_LABEL - /* Don't emit a NOTE if it would end up before a BARRIER. */ - && GET_CODE (NEXT_INSN (insn)) != BARRIER)) + 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; + + FOR_EACH_DEP (next, SD_LIST_BACK, sd_it, dep) + { + ds_t ds = DEP_STATUS (dep) & SPECULATIVE; + + if (first_p) + { + first_p = false; + + *ts = ds; + } + else + *ts = ds_merge (*ts, ds); + } + + 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) + gcc_assert (*ts == old_ts + && QUEUE_INDEX (next) == QUEUE_NOWHERE); + else if (current_sched_info->new_ready) + *ts = current_sched_info->new_ready (next, *ts); + + /* * if !(old_ts & SPECULATIVE) (e.g. HARD_DEP or 0), then insn might + have its original pattern or changed (speculative) one. This is due + to changing ebb in region scheduling. + * But if (old_ts & SPECULATIVE), then we are pretty sure that insn + has speculative pattern. + + We can't assert (!(*ts & HARD_DEP) || *ts == old_ts) here because + control-speculative NEXT could have been discarded by sched-rgn.c + (the same case as when discarded by can_schedule_ready_p ()). */ + + if ((*ts & SPECULATIVE) + /* If (old_ts == *ts), then (old_ts & SPECULATIVE) and we don't + need to change anything. */ + && *ts != old_ts) + { + int res; + rtx new_pat; + + gcc_assert ((*ts & SPECULATIVE) && !(*ts & ~SPECULATIVE)); + + res = haifa_speculate_insn (next, *ts, &new_pat); + + switch (res) + { + case -1: + /* It would be nice to change DEP_STATUS of all dependences, + which have ((DEP_STATUS & SPECULATIVE) == *ts) to HARD_DEP, + 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: + if (!ORIG_PAT (next)) + /* If we gonna to overwrite the original pattern of insn, + save it. */ + ORIG_PAT (next) = PATTERN (next); + + 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 + 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. */ + { + 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) + fprintf (spec_info->dump, "; data-spec;"); + if (s & BEGIN_CONTROL) + fprintf (spec_info->dump, "; control-spec;"); + if (s & BE_IN_CONTROL) + fprintf (spec_info->dump, "; in-control-spec;"); + } + + fprintf (sched_dump, "\n"); + } + + adjust_priority (next); + + return fix_tick_ready (next); +} + +/* Calculate INSN_TICK of NEXT and add it to either ready or queue list. */ +static int +fix_tick_ready (rtx next) +{ + int tick, delay; + + if (!sd_lists_empty_p (next, SD_LIST_RES_BACK)) { - emit_note_after (NOTE_INSN_DELETED, BLOCK_END (n_basic_blocks - 1)); - /* Make insn to appear outside BB. */ - BLOCK_END (n_basic_blocks - 1) = PREV_INSN (BLOCK_END (n_basic_blocks - 1)); + int full_p; + sd_iterator_def sd_it; + dep_t dep; + + tick = INSN_TICK (next); + /* if tick is not equal to INVALID_TICK, then update + INSN_TICK of NEXT with the most recent resolved dependence + cost. Otherwise, recalculate from scratch. */ + full_p = (tick == INVALID_TICK); + + 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); + if (tick1 > tick) + tick = tick1; + + if (!full_p) + break; + } } + else + tick = -1; + + INSN_TICK (next) = tick; + + delay = tick - clock_var; + if (delay <= 0) + delay = QUEUE_READY; + + change_queue_index (next, delay); + + return delay; +} + +/* Move NEXT to the proper queue list with (DELAY >= 1), + or add it to the ready list (DELAY == QUEUE_READY), + or remove it from ready and queue lists at all (DELAY == QUEUE_NOWHERE). */ +static void +change_queue_index (rtx next, int delay) +{ + int i = QUEUE_INDEX (next); + + 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. */ + return; - /* Compute INSN_REG_WEIGHT for all blocks. We must do this before - removing death notes. */ - for (b = n_basic_blocks - 1; b >= 0; b--) - find_insn_reg_weight (b); + /* Remove NEXT from wherever it is now. */ + if (i == QUEUE_READY) + 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) + fprintf (sched_dump, " into queue with cost=%d\n", delay); + else + fprintf (sched_dump, " removed from ready or queue lists\n"); + } } -/* Free global data used during insn scheduling. */ +static int sched_ready_n_insns = -1; +/* Initialize per region data structures. */ void -sched_finish () +sched_extend_ready_list (int new_sched_ready_n_insns) { - free (h_i_d); - free_dependency_caches (); - end_alias_analysis (); - if (write_symbols != NO_DEBUG) - free (line_note_head); + int i; + + 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); + + 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, + new_sched_ready_n_insns + 1); + + 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; +} + +/* Free per region data structures. */ +void +sched_finish_ready_list (void) +{ + int i; + + free (ready.vec); + ready.vec = NULL; + ready.veclen = 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; +} + +static int +haifa_luid_for_non_insn (rtx x) +{ + gcc_assert (NOTE_P (x) || LABEL_P (x)); + + return 0; +} + +/* Generates recovery code for INSN. */ +static void +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); } + +/* Helper function. + 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 (rtx insn, rtx twin, ds_t fs) +{ + sd_iterator_def sd_it; + dep_t dep; + + FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep) + { + ds_t ds; + rtx consumer; + + consumer = DEP_CON (dep); + + ds = DEP_STATUS (dep); + + if (/* If we want to create speculative dep. */ + fs + /* And we can do that because this is a true dep. */ + && (ds & DEP_TYPES) == DEP_TRUE) + { + gcc_assert (!(ds & BE_IN_SPEC)); + + if (/* If this dep can be overcome with 'begin speculation'. */ + ds & BEGIN_SPEC) + /* Then we have a choice: keep the dep 'begin speculative' + or transform it into 'be in speculative'. */ + { + if (/* In try_ready we assert that if insn once became ready + 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. */ + 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; + } + + { + 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); + } + } +} + +/* Generates recovery code for BEGIN speculative INSN. */ +static void +begin_speculative_block (rtx insn) +{ + if (TODO_SPEC (insn) & BEGIN_DATA) + nr_begin_data++; + if (TODO_SPEC (insn) & BEGIN_CONTROL) + nr_begin_control++; + + create_check_block_twin (insn, false); + + 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; + 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)); + + if (ts & BE_IN_DATA) + nr_be_in_data++; + if (ts & BE_IN_CONTROL) + nr_be_in_control++; + + TODO_SPEC (insn) &= ~BE_IN_SPEC; + gcc_assert (!TODO_SPEC (insn)); + + DONE_SPEC (insn) |= ts; + + /* First we convert all simple checks to branchy. */ + for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK); + sd_iterator_cond (&sd_it, &dep);) + { + rtx check = DEP_PRO (dep); + + if (IS_SPECULATION_SIMPLE_CHECK_P (check)) + { + create_check_block_twin (check, true); + + /* Restart search. */ + sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK); + } + else + /* Continue search. */ + sd_iterator_next (&sd_it); + } + + priorities_roots = NULL; + clear_priorities (insn, &priorities_roots); + + while (1) + { + rtx check, twin; + basic_block rec; + + /* 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_STATUS (dep) & BEGIN_SPEC) == 0 + && (DEP_STATUS (dep) & BE_IN_SPEC) != 0 + && (DEP_STATUS (dep) & DEP_TYPES) == DEP_TRUE); + + 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_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. + So we can't use current_sched_info->print_insn. */ + fprintf (spec_info->dump, ";;\t\tGenerated twin insn : %d/rec%d\n", + INSN_UID (twin), rec->index); + + twins = alloc_INSN_LIST (twin, twins); + + /* Add dependences between TWIN and all appropriate + instructions from REC. */ + 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); + } + } + + process_insn_forw_deps_be_in_spec (insn, twin, ts); + + /* Remove all dependencies between INSN and insns in REC. */ + for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK); + sd_iterator_cond (&sd_it, &dep);) + { + rtx pro = DEP_PRO (dep); + + if (BLOCK_FOR_INSN (pro) == rec) + sd_delete_dep (sd_it); + else + sd_iterator_next (&sd_it); + } + } + + /* We couldn't have added the dependencies between INSN and TWINS earlier + because that would make TWINS appear in the INSN_BACK_DEPS (INSN). */ + while (twins) + { + rtx twin; + + twin = XEXP (twins, 0); + + { + 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; + } + + calc_priorities (priorities_roots); + VEC_free (rtx, heap, priorities_roots); +} + +/* Extends and fills with zeros (only the new part) array pointed to by P. */ +void * +xrecalloc (void *p, size_t new_nmemb, size_t old_nmemb, size_t size) +{ + gcc_assert (new_nmemb >= old_nmemb); + p = XRESIZEVAR (void, p, new_nmemb * size); + memset (((char *) p) + old_nmemb * size, 0, (new_nmemb - old_nmemb) * size); + return p; +} + +/* Helper function. + Find fallthru edge from PRED. */ +edge +find_fallthru_edge (basic_block pred) +{ + edge e; + edge_iterator ei; + basic_block succ; + + succ = pred->next_bb; + gcc_assert (succ->prev_bb == pred); + + if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds)) + { + FOR_EACH_EDGE (e, ei, pred->succs) + if (e->flags & EDGE_FALLTHRU) + { + gcc_assert (e->dest == succ); + return e; + } + } + else + { + FOR_EACH_EDGE (e, ei, succ->preds) + if (e->flags & EDGE_FALLTHRU) + { + gcc_assert (e->src == pred); + return e; + } + } + + 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 (basic_block *before_recovery_ptr) +{ + basic_block last; + edge e; + + last = EXIT_BLOCK_PTR->prev_bb; + e = find_fallthru_edge (last); + + if (e) + { + /* We create two basic blocks: + 1. Single instruction block is inserted right after E->SRC + 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; + + /* 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); + + /* 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; + BB_COPY_PARTITION (single, last); + BB_COPY_PARTITION (empty, last); + + redirect_edge_succ (e, single); + make_single_succ_edge (single, empty, 0); + make_single_succ_edge (empty, EXIT_BLOCK_PTR, + EDGE_FALLTHRU | EDGE_CAN_FALLTHRU); + + label = block_label (empty); + x = emit_jump_insn_after (gen_jump (label), BB_END (single)); + JUMP_LABEL (x) = label; + LABEL_NUSES (label)++; + haifa_init_insn (x); + + emit_barrier_after (x); + + 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); + } + else + before_recovery = last; +} + +/* Returns new recovery block. */ +basic_block +sched_create_recovery_block (basic_block *before_recovery_ptr) +{ + rtx label; + rtx barrier; + basic_block rec; + + 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)); + + label = emit_label_after (gen_label_rtx (), barrier); + + rec = create_basic_block (label, label, before_recovery); + + /* 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) + fprintf (spec_info->dump, ";;\t\tGenerated recovery block rec%d\n", + rec->index); + + 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; + edge e; + 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; + + e = 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. */ + { + 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); +} + +/* 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 +create_check_block_twin (rtx insn, bool mutate_p) +{ + basic_block rec; + rtx label, check, twin; + 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); + + 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 (todo_spec)) + { + rec = sched_create_recovery_block (NULL); + label = BB_HEAD (rec); + } + else + { + rec = EXIT_BLOCK_PTR; + label = NULL_RTX; + } + + /* Emit CHECK. */ + 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 + 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); + JUMP_LABEL (check) = label; + LABEL_NUSES (label)++; + } + else + check = emit_insn_before (check, insn); + + /* Extend data structures. */ + 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) + fprintf (spec_info->dump, ";;\t\tGenerated check insn : %s\n", + (*current_sched_info->print_insn) (check, 0)); + + gcc_assert (ORIG_PAT (insn)); + + /* Initialize TWIN (twin is a duplicate of original instruction + in the recovery block). */ + if (rec != EXIT_BLOCK_PTR) + { + 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 _dep2, *dep2 = &_dep2; + + init_dep (dep2, DEP_PRO (dep), check, REG_DEP_TRUE); + + sd_add_dep (dep2, true); + } + + twin = emit_insn_after (ORIG_PAT (insn), BB_END (rec)); + haifa_init_insn (twin); + + if (sched_verbose && spec_info->dump) + /* INSN_BB (insn) isn't determined for twin insns yet. + So we can't use current_sched_info->print_insn. */ + fprintf (spec_info->dump, ";;\t\tGenerated twin insn : %d/rec%d\n", + INSN_UID (twin), rec->index); + } + else + { + ORIG_PAT (check) = ORIG_PAT (insn); + HAS_INTERNAL_DEP (check) = 1; + twin = check; + /* ??? We probably should change all OUTPUT dependencies to + (TRUE | OUTPUT). */ + } + + /* 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; + + first_bb = BLOCK_FOR_INSN (check); + second_bb = sched_split_block (first_bb, check); + + 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 forward dependences from INSN to TWIN. */ + + /* First, create dependencies between INSN's producers and CHECK & TWIN. */ + FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep) + { + 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 + twin --ANTI--> check + + If BE_IN_SPEC: [insn ~~TRUE~~> producer]: + check ~~TRUE~~> producer + twin ~~TRUE~~> producer + twin --ANTI--> check */ + + ds = DEP_STATUS (dep); + + if (ds & BEGIN_SPEC) + { + gcc_assert (!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) + { + DEP_CON (new_dep) = twin; + sd_add_dep (new_dep, false); + } + } + + /* 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)); + } + else + CHECK_SPEC (check) = CHECK_SPEC (insn); + + /* Future speculations: call the helper. */ + process_insn_forw_deps_be_in_spec (insn, twin, fs); + + if (rec != EXIT_BLOCK_PTR) + { + /* Which types of dependencies should we use here is, + generally, machine-dependent question... But, for now, + it is not. */ + + if (!mutate_p) + { + 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 + { + if (spec_info->dump) + fprintf (spec_info->dump, ";;\t\tRemoved simple check : %s\n", + (*current_sched_info->print_insn) (insn, 0)); + + /* 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); + } + + init_dep (new_dep, check, twin, REG_DEP_ANTI); + sd_add_dep (new_dep, false); + } + else + { + 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. */ + { + rtx_vec_t priorities_roots = NULL; + + clear_priorities (twin, &priorities_roots); + calc_priorities (priorities_roots); + VEC_free (rtx, heap, priorities_roots); + } +} + +/* Removes dependency between instructions in the recovery block REC + and usual region instructions. It keeps inner dependences so it + won't be necessary to recompute them. */ +static void +fix_recovery_deps (basic_block rec) +{ + rtx note, insn, jump, ready_list = 0; + bitmap_head in_ready; + 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)); + insn = BB_END (rec); + gcc_assert (JUMP_P (insn)); + insn = PREV_INSN (insn); + + do + { + sd_iterator_def sd_it; + dep_t dep; + + 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) + { + 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)); + } + } + else + { + gcc_assert ((DEP_STATUS (dep) & DEP_TYPES) == DEP_TRUE); + + sd_iterator_next (&sd_it); + } + } + + insn = PREV_INSN (insn); + } + while (insn != note); + + bitmap_clear (&in_ready); + + /* Try to add instructions to the ready or queue list. */ + 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); +} + +/* 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; +} + +/* -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. */ +int +sched_speculate_insn (rtx insn, ds_t request, rtx *new_pat) +{ + gcc_assert (current_sched_info->flags & DO_SPECULATION + && (request & SPECULATIVE) + && sched_insn_is_legitimate_for_speculation_p (insn, request)); + + if ((request & spec_info->mask) != request) + return -1; + + 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 + ends with TAIL, before scheduling it. + I is zero, if scheduler is about to start with the fresh ebb. */ +static void +dump_new_block_header (int i, basic_block bb, rtx head, rtx tail) +{ + if (!i) + fprintf (sched_dump, + ";; ======================================================\n"); + else + fprintf (sched_dump, + ";; =====================ADVANCING TO=====================\n"); + fprintf (sched_dump, + ";; -- basic block %d from %d to %d -- %s reload\n", + bb->index, INSN_UID (head), INSN_UID (tail), + (reload_completed ? "after" : "before")); + fprintf (sched_dump, + ";; ======================================================\n"); + fprintf (sched_dump, "\n"); +} + +/* Unlink basic block notes and labels and saves them, so they + can be easily restored. We unlink basic block notes in EBB to + provide back-compatibility with the previous code, as target backends + assume, that there'll be only instructions between + current_sched_info->{head and tail}. We restore these notes as soon + as we can. + FIRST (LAST) is the first (last) basic block in the ebb. + NB: In usual case (FIRST == LAST) nothing is really done. */ +void +unlink_bb_notes (basic_block first, basic_block last) +{ + /* We DON'T unlink basic block notes of the first block in the ebb. */ + if (first == last) + return; + + bb_header = XNEWVEC (rtx, last_basic_block); + + /* Make a sentinel. */ + if (last->next_bb != EXIT_BLOCK_PTR) + bb_header[last->next_bb->index] = 0; + + first = first->next_bb; + do + { + rtx prev, label, note, next; + + label = BB_HEAD (last); + if (LABEL_P (label)) + note = NEXT_INSN (label); + else + note = label; + gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note)); + + prev = PREV_INSN (label); + next = NEXT_INSN (note); + gcc_assert (prev && next); + + NEXT_INSN (prev) = next; + PREV_INSN (next) = prev; + + bb_header[last->index] = label; + + if (last == first) + break; + + last = last->prev_bb; + } + while (1); +} + +/* Restore basic block notes. + FIRST is the first basic block in the ebb. */ +static void +restore_bb_notes (basic_block first) +{ + if (!bb_header) + return; + + /* We DON'T unlink basic block notes of the first block in the ebb. */ + 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); + + if (LABEL_P (label)) + note = NEXT_INSN (label); + else + note = label; + gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note)); + + bb_header[first->index] = 0; + + NEXT_INSN (prev) = label; + NEXT_INSN (note) = next; + PREV_INSN (next) = note; + + first = first->next_bb; + } + + free (bb_header); + bb_header = 0; +} + +/* Helper function. + Fix CFG after both in- and inter-block movement of + control_flow_insn_p JUMP. */ +static void +fix_jump_move (rtx jump) +{ + basic_block bb, jump_bb, jump_bb_next; + + bb = BLOCK_FOR_INSN (PREV_INSN (jump)); + jump_bb = BLOCK_FOR_INSN (jump); + jump_bb_next = jump_bb->next_bb; + + 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); + + if (BB_END (bb) != PREV_INSN (jump)) + /* Then there are instruction after jump that should be placed + to jump_bb_next. */ + BB_END (jump_bb_next) = BB_END (bb); + else + /* Otherwise jump_bb_next is empty. */ + BB_END (jump_bb_next) = NEXT_INSN (BB_HEAD (jump_bb_next)); + + /* To make assertion in move_insn happy. */ + BB_END (bb) = PREV_INSN (jump); + + update_bb_for_insn (jump_bb_next); +} + +/* Fix CFG after interblock movement of control_flow_insn_p JUMP. */ +static void +move_block_after_check (rtx jump) +{ + basic_block bb, jump_bb, jump_bb_next; + VEC(edge,gc) *t; + + 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))); + + unlink_block (jump_bb_next); + link_block (jump_bb_next, bb); + + t = bb->succs; + bb->succs = 0; + move_succs (&(jump_bb->succs), bb); + move_succs (&(jump_bb_next->succs), jump_bb); + move_succs (&t, jump_bb_next); + + 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. + This functions attaches edge vector pointed to by SUCCSP to + block TO. */ +static void +move_succs (VEC(edge,gc) **succsp, basic_block to) +{ + edge e; + edge_iterator ei; + + gcc_assert (to->succs == 0); + + to->succs = *succsp; + + FOR_EACH_EDGE (e, ei, to->succs) + e->src = to; + + *succsp = 0; +} + +/* 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. + 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, rtx_vec_t *roots_ptr) +{ + sd_iterator_def sd_it; + dep_t dep; + bool insn_is_root_p = true; + + gcc_assert (QUEUE_INDEX (insn) != QUEUE_SCHEDULED); + + FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep) + { + rtx pro = DEP_PRO (dep); + + if (INSN_PRIORITY_STATUS (pro) >= 0 + && QUEUE_INDEX (insn) != QUEUE_SCHEDULED) + { + /* 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. ROOTS is a vector of instructions whose priority computation will + trigger initialization of all cleared priorities. */ +static void +calc_priorities (rtx_vec_t roots) +{ + int i; + rtx insn; + + for (i = 0; VEC_iterate (rtx, roots, i, insn); i++) + priority (insn); +} + + +/* Add dependences between JUMP and other instructions in the recovery + block. INSN is the first insn the recovery block. */ +static void +add_jump_dependencies (rtx insn, rtx jump) +{ + do + { + insn = NEXT_INSN (insn); + if (insn == jump) + break; + + if (sd_lists_empty_p (insn, SD_LIST_FORW)) + { + 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 (!sd_lists_empty_p (jump, SD_LIST_BACK)); +} + +/* Return the NOTE_INSN_BASIC_BLOCK of BB. */ +rtx +bb_note (basic_block bb) +{ + rtx note; + + note = BB_HEAD (bb); + if (LABEL_P (note)) + note = NEXT_INSN (note); + + gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note)); + return note; +} + +#ifdef ENABLE_CHECKING +/* Helper function for check_cfg. + Return nonzero, if edge vector pointed to by EL has edge with TYPE in + its flags. */ +static int +has_edge_p (VEC(edge,gc) *el, int type) +{ + edge e; + edge_iterator ei; + + FOR_EACH_EDGE (e, ei, el) + if (e->flags & type) + return 1; + return 0; +} + +/* 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. */ +static void +check_cfg (rtx head, rtx tail) +{ + rtx next_tail; + basic_block bb = 0; + int not_first = 0, not_last; + + if (head == NULL) + head = get_insns (); + if (tail == NULL) + tail = get_last_insn (); + next_tail = NEXT_INSN (tail); + + do + { + 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) + || (NOTE_INSN_BASIC_BLOCK_P (head) + && (!not_first + || (not_first && !LABEL_P (PREV_INSN (head)))))) + { + gcc_assert (bb == 0); + bb = BLOCK_FOR_INSN (head); + if (bb != 0) + 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)); + } + + if (bb == 0) + { + gcc_assert (!inside_basic_block_p (head)); + head = NEXT_INSN (head); + } + else + { + 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); + gcc_assert (NOTE_INSN_BASIC_BLOCK_P (head)); + } + else + { + if (control_flow_insn_p (head)) + { + gcc_assert (BB_END (bb) == head); + + if (any_uncondjump_p (head)) + gcc_assert (EDGE_COUNT (bb->succs) == 1 + && BARRIER_P (NEXT_INSN (head))); + else if (any_condjump_p (head)) + gcc_assert (/* Usual case. */ + (EDGE_COUNT (bb->succs) > 1 + && !BARRIER_P (NEXT_INSN (head))) + /* Or jump to the next instruction. */ + || (EDGE_COUNT (bb->succs) == 1 + && (BB_HEAD (EDGE_I (bb->succs, 0)->dest) + == JUMP_LABEL (head)))); + } + if (BB_END (bb) == head) + { + if (EDGE_COUNT (bb->succs) > 1) + gcc_assert (control_flow_insn_p (head) + || has_edge_p (bb->succs, EDGE_COMPLEX)); + bb = 0; + } + + head = NEXT_INSN (head); + } + } + + not_first = 1; + } + while (head != next_tail); + + gcc_assert (bb == 0); +} + +#endif /* ENABLE_CHECKING */ + +const struct sched_scan_info_def *sched_scan_info; + +/* Extend per basic block data structures. */ +static void +extend_bb (void) +{ + if (sched_scan_info->extend_bb) + sched_scan_info->extend_bb (); +} + +/* Init data for BB. */ +static void +init_bb (basic_block bb) +{ + if (sched_scan_info->init_bb) + sched_scan_info->init_bb (bb); +} + +/* Extend per insn data structures. */ +static void +extend_insn (void) +{ + if (sched_scan_info->extend_insn) + sched_scan_info->extend_insn (); +} + +/* Init data structures for INSN. */ +static void +init_insn (rtx insn) +{ + if (sched_scan_info->init_insn) + sched_scan_info->init_insn (insn); +} + +/* Init all insns in BB. */ +static void +init_insns_in_bb (basic_block bb) +{ + rtx insn; + + FOR_BB_INSNS (bb, insn) + init_insn (insn); +} + +/* A driver function to add a set of basic blocks (BBS), + a single basic block (BB), a set of insns (INSNS) or a single insn (INSN) + to the scheduling region. */ +void +sched_scan (const struct sched_scan_info_def *ssi, + bb_vec_t bbs, basic_block bb, insn_vec_t insns, rtx insn) +{ + sched_scan_info = ssi; + + if (bbs != NULL || bb != NULL) + { + extend_bb (); + + if (bbs != NULL) + { + unsigned i; + basic_block x; + + for (i = 0; VEC_iterate (basic_block, bbs, i, x); i++) + init_bb (x); + } + + if (bb != NULL) + init_bb (bb); + } + + extend_insn (); + + if (bbs != NULL) + { + unsigned i; + basic_block x; + + for (i = 0; VEC_iterate (basic_block, bbs, i, x); i++) + init_insns_in_bb (x); + } + + if (bb != NULL) + init_insns_in_bb (bb); + + if (insns != NULL) + { + unsigned i; + rtx x; + + for (i = 0; VEC_iterate (rtx, insns, i, x); i++) + init_insn (x); + } + + if (insn != NULL) + init_insn (insn); +} + + +/* Extend data structures for logical insn UID. */ +static void +luids_extend_insn (void) +{ + 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; + find_insn_reg_weight (insn); + 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) +{ + 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 /* INSN_SCHEDULING */