diff options
Diffstat (limited to 'gcc-4.2.1-5666.3/gcc/haifa-sched.c')
| -rw-r--r-- | gcc-4.2.1-5666.3/gcc/haifa-sched.c | 4748 |
1 files changed, 0 insertions, 4748 deletions
diff --git a/gcc-4.2.1-5666.3/gcc/haifa-sched.c b/gcc-4.2.1-5666.3/gcc/haifa-sched.c deleted file mode 100644 index 43f0504a6..000000000 --- a/gcc-4.2.1-5666.3/gcc/haifa-sched.c +++ /dev/null @@ -1,4748 +0,0 @@ -/* Instruction scheduling pass. - Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, - 2000, 2001, 2002, 2003, 2004, 2005, 2006 Free Software Foundation, Inc. - Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by, - and currently maintained by, Jim Wilson (wilson@cygnus.com) - -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 -version. - -GCC is distributed in the hope that it will be useful, but WITHOUT ANY -WARRANTY; without even the implied warranty of MERCHANTABILITY or -FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License -for more details. - -You should have received a copy of the GNU General Public License -along with GCC; see the file COPYING. If not, write to the Free -Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA -02110-1301, USA. */ - -/* Instruction scheduling pass. This file, along with sched-deps.c, - contains the generic parts. The actual entry point is found for - the normal instruction scheduling pass is found in sched-rgn.c. - - We compute insn priorities based on data dependencies. Flow - analysis only creates a fraction of the data-dependencies we must - observe: namely, only those dependencies which the combiner can be - expected to use. For this pass, we must therefore create the - remaining dependencies we need to observe: register dependencies, - memory dependencies, dependencies to keep function calls in order, - and the dependence between a conditional branch and the setting of - condition codes are all dealt with here. - - The scheduler first traverses the data flow graph, starting with - the last instruction, and proceeding to the first, assigning values - to insn_priority as it goes. This sorts the instructions - topologically by data dependence. - - Once priorities have been established, we order the insns using - list scheduling. This works as follows: starting with a list of - all the ready insns, and sorted according to priority number, we - schedule the insn from the end of the list by placing its - predecessors in the list according to their priority order. We - consider this insn scheduled by setting the pointer to the "end" of - the list to point to the previous insn. When an insn has no - predecessors, we either queue it until sufficient time has elapsed - or add it to the ready list. As the instructions are scheduled or - when stalls are introduced, the queue advances and dumps insns into - the ready list. When all insns down to the lowest priority have - been scheduled, the critical path of the basic block has been made - as short as possible. The remaining insns are then scheduled in - remaining slots. - - The following list shows the order in which we want to break ties - among insns in the ready list: - - 1. choose insn with the longest path to end of bb, ties - broken by - 2. choose insn with least contribution to register pressure, - ties broken by - 3. prefer in-block upon interblock motion, ties broken by - 4. prefer useful upon speculative motion, ties broken by - 5. choose insn with largest control flow probability, ties - broken by - 6. choose insn with the least dependences upon the previously - scheduled insn, or finally - 7 choose the insn which has the most insns dependent on it. - 8. choose insn with lowest UID. - - Memory references complicate matters. Only if we can be certain - that memory references are not part of the data dependency graph - (via true, anti, or output dependence), can we move operations past - memory references. To first approximation, reads can be done - independently, while writes introduce dependencies. Better - approximations will yield fewer dependencies. - - Before reload, an extended analysis of interblock data dependences - is required for interblock scheduling. This is performed in - 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. - - Having optimized the critical path, we may have also unduly - extended the lifetimes of some registers. If an operation requires - that constants be loaded into registers, it is certainly desirable - to load those constants as early as necessary, but no earlier. - I.e., it will not do to load up a bunch of registers at the - beginning of a basic block only to use them at the end, if they - could be loaded later, since this may result in excessive register - utilization. - - Note that since branches are never in basic blocks, but only end - basic blocks, this pass will not move branches. But that is ok, - since we can use GNU's delayed branch scheduling pass to take care - of this case. - - Also note that no further optimizations based on algebraic - identities are performed, so this pass would be a good one to - perform instruction splitting, such as breaking up a multiply - instruction into shifts and adds where that is profitable. - - Given the memory aliasing analysis that this pass should perform, - it should be possible to remove redundant stores to memory, and to - load values from registers instead of hitting memory. - - Before reload, speculative insns are moved only if a 'proof' exists - that no exception will be caused by this, and if no live registers - exist that inhibit the motion (live registers constraints are not - represented by data dependence edges). - - 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, 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 - exception regions are also carefully retained by this pass. All - other NOTE insns are grouped in their same relative order at the - beginning of basic blocks and regions that have been scheduled. */ - -#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 "regs.h" -#include "function.h" -#include "flags.h" -#include "insn-config.h" -#include "insn-attr.h" -#include "except.h" -#include "toplev.h" -#include "recog.h" -#include "sched-int.h" -#include "target.h" -#include "output.h" -#include "params.h" - -#ifdef INSN_SCHEDULING - -/* issue_rate is the number of insns that can be scheduled in the same - machine cycle. It can be defined in the config/mach/mach.h file, - otherwise we set it to 1. */ - -static int issue_rate; - -/* sched-verbose controls the amount of debugging output the - scheduler prints. It is controlled by -fsched-verbose=N: - N>0 and no -DSR : the output is directed to stderr. - N>=10 will direct the printouts to stderr (regardless of -dSR). - N=1: same as -dSR. - N=2: bb's probabilities, detailed ready list info, unit/insn info. - N=3: rtl at abort point, control-flow, regions info. - N=5: dependences info. */ - -/* APPLE LOCAL begin optimization pragmas 3124235/3420242 */ -/* APPLE LOCAL end optimization pragmas 3124235/3420242 */ -int sched_verbose = 0; - -/* Debugging file. All printouts are sent to dump, which is always set, - either to stderr, or to the dump listing file (-dRS). */ -FILE *sched_dump = 0; - -/* Highest uid before scheduling. */ -static int old_max_uid; - -/* APPLE LOCAL optimization pragmas 3124235/3420242 */ -/* Delete fix_sched_param. */ - -struct haifa_insn_data *h_i_d; - -#define LINE_NOTE(INSN) (h_i_d[INSN_UID (INSN)].line_note) -#define INSN_TICK(INSN) (h_i_d[INSN_UID (INSN)].tick) -#define INTER_TICK(INSN) (h_i_d[INSN_UID (INSN)].inter_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) - -/* Issue points are used to distinguish between instructions in max_issue (). - For now, all instructions are equally good. */ -#define ISSUE_POINTS(INSN) 1 - -/* Vector indexed by basic block number giving the starting line-number - for each basic block. */ -static rtx *line_note_head; - -/* List of important notes we must keep around. This is a pointer to the - last element in the list. */ -static rtx note_list; - -static struct spec_info_def spec_info_var; -/* Description of the speculative part of the scheduling. - If NULL - no speculation. */ -static spec_info_t spec_info; - -/* True, if recovery block was added during scheduling of current block. - Used to determine, if we need to fix INSN_TICKs. */ -static bool added_recovery_block_p; - -/* Counters of different types of speculative instructions. */ -static int nr_begin_data, nr_be_in_data, nr_begin_control, nr_be_in_control; - -/* Pointers to GLAT data. See init_glat for more information. */ -regset *glat_start, *glat_end; - -/* Array used in {unlink, restore}_bb_notes. */ -static rtx *bb_header = 0; - -/* Number of basic_blocks. */ -static int old_last_basic_block; - -/* Basic block after which recovery blocks will be created. */ -static basic_block before_recovery; - -/* Queues, etc. */ - -/* An instruction is ready to be scheduled when all insns preceding it - have already been scheduled. It is important to ensure that all - insns which use its result will not be executed until its result - has been computed. An insn is maintained in one of four structures: - - (P) the "Pending" set of insns which cannot be scheduled until - their dependencies have been satisfied. - (Q) the "Queued" set of insns that can be scheduled when sufficient - time has passed. - (R) the "Ready" list of unscheduled, uncommitted insns. - (S) the "Scheduled" list of insns. - - Initially, all insns are either "Pending" or "Ready" depending on - whether their dependencies are satisfied. - - Insns move from the "Ready" list to the "Scheduled" list as they - are committed to the schedule. As this occurs, the insns in the - "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. - - 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 "Queued" set (Q) is implemented by the variable `insn_queue'. - The "Ready" list (R) is implemented by the variables `ready' and - `n_ready'. - The "Scheduled" list (S) is the new insn chain built by this pass. - - The transition (R->S) is implemented in the scheduling loop in - `schedule_block' when the best insn to schedule is chosen. - 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. 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) & 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) (h_i_d[INSN_UID (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. */ -static size_t dfa_state_size; - -/* The following array is used to find the best insn from ready when - the automaton pipeline interface is used. */ -static char *ready_try; - -/* Describe the ready list of the scheduler. - VEC holds space enough for all insns in the current region. VECLEN - says how many exactly. - FIRST is the index of the element with the highest priority; i.e. the - last one in the ready list, since elements are ordered by ascending - priority. - N_READY determines how many insns are on the ready list. */ - -struct ready_list -{ - rtx *vec; - int veclen; - int first; - int n_ready; -}; - -/* The pointer to the ready list. */ -static struct ready_list *readyp; - -/* Scheduling clock. */ -static int clock_var; - -/* Number of instructions in current scheduling region. */ -static int rgn_n_insns; - -static int may_trap_exp (rtx, int); - -/* 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))))) - -/* Returns a class that insn with GET_DEST(insn)=x may belong to, - as found by analyzing insn's expression. */ - -static int -may_trap_exp (rtx x, int is_store) -{ - enum rtx_code code; - - if (x == 0) - return TRAP_FREE; - code = GET_CODE (x); - if (is_store) - { - 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--) - { - 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; - } - return insn_class; - } -} - -/* Classifies insn for the purpose of verifying that it can be - moved speculatively, by examining it's patterns, 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. */ - -int -haifa_classify_insn (rtx insn) -{ - rtx pat = PATTERN (insn); - int tmp_class = TRAP_FREE; - int insn_class = TRAP_FREE; - enum rtx_code code; - - if (GET_CODE (pat) == PARALLEL) - { - int i, len = XVECLEN (pat, 0); - - for (i = len - 1; i >= 0; i--) - { - code = GET_CODE (XVECEXP (pat, 0, i)); - switch (code) - { - case CLOBBER: - /* Test if it is a 'store'. */ - tmp_class = may_trap_exp (XEXP (XVECEXP (pat, 0, i), 0), 1); - break; - case SET: - /* Test if it is a store. */ - tmp_class = may_trap_exp (SET_DEST (XVECEXP (pat, 0, i)), 1); - if (tmp_class == TRAP_RISKY) - break; - /* Test if it is a load. */ - tmp_class - = WORST_CLASS (tmp_class, - may_trap_exp (SET_SRC (XVECEXP (pat, 0, i)), - 0)); - break; - case COND_EXEC: - case TRAP_IF: - tmp_class = TRAP_RISKY; - break; - default: - ; - } - insn_class = WORST_CLASS (insn_class, tmp_class); - if (insn_class == TRAP_RISKY || insn_class == IRISKY) - break; - } - } - else - { - code = GET_CODE (pat); - switch (code) - { - case CLOBBER: - /* Test if it is a 'store'. */ - tmp_class = may_trap_exp (XEXP (pat, 0), 1); - break; - case SET: - /* Test if it is a store. */ - tmp_class = may_trap_exp (SET_DEST (pat), 1); - if (tmp_class == TRAP_RISKY) - break; - /* Test if it is a load. */ - tmp_class = - WORST_CLASS (tmp_class, - may_trap_exp (SET_SRC (pat), 0)); - break; - case COND_EXEC: - case TRAP_IF: - tmp_class = TRAP_RISKY; - break; - default:; - } - insn_class = tmp_class; - } - - return insn_class; -} - -/* Forward declarations. */ - -HAIFA_INLINE static int insn_cost1 (rtx, enum reg_note, rtx, rtx); -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 (rtx); -static void find_insn_reg_weight (basic_block); -static void find_insn_reg_weight1 (rtx); -static void adjust_priority (rtx); -static void advance_one_cycle (void); - -/* Notes handling mechanism: - ========================= - Generally, NOTES are saved before scheduling and restored after scheduling. - The scheduler distinguishes between three types of notes: - - (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()). - - (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). - - (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()). */ - -static rtx unlink_other_notes (rtx, rtx); -static rtx unlink_line_notes (rtx, rtx); -static void reemit_notes (rtx); - -static rtx *ready_lastpos (struct ready_list *); -static void ready_add (struct ready_list *, rtx, bool); -static void ready_sort (struct ready_list *); -static rtx ready_remove_first (struct ready_list *); - -static void queue_to_ready (struct ready_list *); -static int early_queue_to_ready (state_t, struct ready_list *); - -static void debug_ready_list (struct ready_list *); - -static void move_insn (rtx); - -/* The following functions are used to implement multi-pass scheduling - on the first cycle. */ -static rtx ready_element (struct ready_list *, int); -static rtx ready_remove (struct ready_list *, int); -static void ready_remove_insn (rtx); -static int max_issue (struct ready_list *, int *, int); - -static rtx choose_ready (struct ready_list *); - -static void fix_inter_tick (rtx, rtx); -static int fix_tick_ready (rtx); -static void change_queue_index (rtx, int); -static void resolve_dep (rtx, rtx); - -/* The following functions are used to implement scheduling of data/control - speculative instructions. */ - -static void extend_h_i_d (void); -static void extend_ready (int); -static void extend_global (rtx); -static void extend_all (rtx); -static void init_h_i_d (rtx); -static void generate_recovery_code (rtx); -static void process_insn_depend_be_in_spec (rtx, rtx, ds_t); -static void begin_speculative_block (rtx); -static void add_to_speculative_block (rtx); -static dw_t dep_weak (ds_t); -static edge find_fallthru_edge (basic_block); -static void init_before_recovery (void); -static basic_block create_recovery_block (void); -static void create_check_block_twin (rtx, bool); -static void fix_recovery_deps (basic_block); -static void associate_line_notes_with_blocks (basic_block); -static void change_pattern (rtx, rtx); -static int speculate_insn (rtx, ds_t, rtx *); -static void dump_new_block_header (int, basic_block, rtx, rtx); -static void restore_bb_notes (basic_block); -static void extend_bb (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 init_glat (void); -static void init_glat1 (basic_block); -static void attach_life_info1 (basic_block); -static void free_glat (void); -static void sched_remove_insn (rtx); -static void clear_priorities (rtx); -static void add_jump_dependencies (rtx, rtx); -static void calc_priorities (rtx); -#ifdef ENABLE_CHECKING -static int has_edge_p (VEC(edge,gc) *, int); -static void check_cfg (rtx, rtx); -static void check_sched_flags (void); -#endif - -#endif /* INSN_SCHEDULING */ - -/* Point to state used for the current scheduling pass. */ -struct sched_info *current_sched_info; - -#ifndef INSN_SCHEDULING -void -schedule_insns (void) -{ -} -#else - -/* Working copy of frontend's sched_info variable. */ -static struct sched_info current_sched_info_var; - -/* 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. */ - -static rtx last_scheduled_insn; - -/* Compute cost of executing INSN given the dependence LINK on the insn USED. - This is the number of cycles between instruction issue and - instruction results. */ - -HAIFA_INLINE int -insn_cost (rtx insn, rtx link, rtx used) -{ - return insn_cost1 (insn, used ? REG_NOTE_KIND (link) : REG_NOTE_MAX, - link, used); -} - -/* Compute cost of executing INSN given the dependence on the insn USED. - If LINK is not NULL, then its REG_NOTE_KIND is used as a dependence type. - Otherwise, dependence between INSN and USED is assumed to be of type - DEP_TYPE. This function was introduced as a workaround for - targetm.adjust_cost hook. - This is the number of cycles between instruction issue and - instruction results. */ - -HAIFA_INLINE static int -insn_cost1 (rtx insn, enum reg_note dep_type, rtx link, rtx used) -{ - int cost = INSN_COST (insn); - - if (cost < 0) - { - /* 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) - { - INSN_COST (insn) = 0; - return 0; - } - else - { - cost = insn_default_latency (insn); - if (cost < 0) - cost = 0; - - INSN_COST (insn) = cost; - } - } - - /* In this case estimate cost without caring how insn is used. */ - if (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. */ - if (recog_memoized (used) < 0) - cost = 0; - else - { - gcc_assert (!link || dep_type == REG_NOTE_KIND (link)); - - if (INSN_CODE (insn) >= 0) - { - if (dep_type == REG_DEP_ANTI) - cost = 0; - else if (dep_type == REG_DEP_OUTPUT) - { - cost = (insn_default_latency (insn) - - insn_default_latency (used)); - if (cost <= 0) - cost = 1; - } - else if (bypass_p (insn)) - cost = insn_latency (insn, used); - } - - if (targetm.sched.adjust_cost_2) - cost = targetm.sched.adjust_cost_2 (used, (int) dep_type, insn, cost); - else - { - gcc_assert (link); - if (targetm.sched.adjust_cost) - cost = targetm.sched.adjust_cost (used, link, insn, cost); - } - - if (cost < 0) - cost = 0; - } - - return cost; -} - -/* Compute the priority number for INSN. */ - -static int -priority (rtx insn) -{ - rtx link; - - if (! INSN_P (insn)) - return 0; - - if (! INSN_PRIORITY_KNOWN (insn)) - { - int this_priority = 0; - - if (INSN_DEPEND (insn) == 0) - this_priority = insn_cost (insn, 0, 0); - else - { - 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_DEPEND (check) list, we walk through INSN_DEPEND list - of each instruction in the corresponding recovery block. */ - - rec = RECOVERY_BLOCK (insn); - if (!rec || rec == EXIT_BLOCK_PTR) - { - prev_first = PREV_INSN (insn); - twin = insn; - } - else - { - prev_first = NEXT_INSN (BB_HEAD (rec)); - twin = PREV_INSN (BB_END (rec)); - } - - do - { - for (link = INSN_DEPEND (twin); link; link = XEXP (link, 1)) - { - rtx next; - int next_priority; - - next = XEXP (link, 0); - - if (BLOCK_FOR_INSN (next) != rec) - { - /* Critical path is meaningful in block boundaries - only. */ - if (! (*current_sched_info->contributes_to_priority) - (next, insn) - /* If flag COUNT_SPEC_IN_CRITICAL_PATH is set, - then speculative instructions will less likely be - scheduled. That is because the priority of - their producers will increase, and, thus, the - producers will more likely be scheduled, thus, - resolving the dependence. */ - || ((current_sched_info->flags & DO_SPECULATION) - && (DEP_STATUS (link) & SPECULATIVE) - && !(spec_info->flags - & COUNT_SPEC_IN_CRITICAL_PATH))) - continue; - - next_priority = insn_cost1 (insn, - twin == insn ? - REG_NOTE_KIND (link) : - REG_DEP_ANTI, - twin == insn ? link : 0, - next) + priority (next); - - if (next_priority > this_priority) - this_priority = next_priority; - } - } - - twin = PREV_INSN (twin); - } - while (twin != prev_first); - } - INSN_PRIORITY (insn) = this_priority; - INSN_PRIORITY_KNOWN (insn) = 1; - } - - return INSN_PRIORITY (insn); -} - -/* Macros and functions for keeping the priority queue sorted, and - dealing with queuing and dequeuing of instructions. */ - -#define SCHED_SORT(READY, N_READY) \ -do { if ((N_READY) == 2) \ - swap_sort (READY, N_READY); \ - else if ((N_READY) > 2) \ - qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \ -while (0) - -/* Returns a positive value if x is preferred; returns a negative value if - y is preferred. Should never return 0, since that will make the sort - unstable. */ - -static int -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 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; - - /* 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 = dep_weak (ds1); - else - dw1 = NO_DEP_WEAK; - - ds2 = TODO_SPEC (tmp2) & SPECULATIVE; - if (ds2) - dw2 = dep_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; - - 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 (INSN_P (last_scheduled_insn)) - { - /* 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) - tmp_class = 3; - else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */ - 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) - tmp2_class = 3; - else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */ - tmp2_class = 1; - else - tmp2_class = 2; - - if ((val = tmp2_class - tmp_class)) - return val; - } - - /* 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 = depend_count2 - depend_count1; - if (val) - return val; - - /* If insns are equally good, sort by INSN_LUID (original insn order), - so that we make the sort stable. This minimizes instruction movement, - thus minimizing sched's effect on debugging and cross-jumping. */ - return INSN_LUID (tmp) - INSN_LUID (tmp2); -} - -/* Resort the array A in which only element at index N may be out of order. */ - -HAIFA_INLINE static void -swap_sort (rtx *a, int n) -{ - rtx insn = a[n - 1]; - int i = n - 2; - - while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0) - { - a[i + 1] = a[i]; - i -= 1; - } - a[i + 1] = insn; -} - -/* Add INSN to the insn queue so that it can be executed at least - N_CYCLES after the currently executing insn. Preserve insns - chain for debugging purposes. */ - -HAIFA_INLINE static void -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; - - if (sched_verbose >= 2) - { - fprintf (sched_dump, ";;\t\tReady-->Q: insn %s: ", - (*current_sched_info->print_insn) (insn, 0)); - - fprintf (sched_dump, "queued for %d cycles.\n", n_cycles); - } - - 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 (struct ready_list *ready) -{ - 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/highest priority depending on FIRST_P. */ - -HAIFA_INLINE static void -ready_add (struct ready_list *ready, rtx insn, bool first_p) -{ - 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 - { - 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->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 (struct ready_list *ready) -{ - rtx t; - - 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; -} - -/* 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. */ - -/* 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. */ - -HAIFA_INLINE static 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. */ - -HAIFA_INLINE static void -ready_sort (struct ready_list *ready) -{ - rtx *first = ready_lastpos (ready); - SCHED_SORT (first, ready->n_ready); -} - -/* PREV is an insn that is ready to execute. Adjust its priority if that - will help shorten or lengthen register lifetimes as appropriate. Also - provide a hook for the target to tweek itself. */ - -HAIFA_INLINE static void -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 - notes, which we removed in schedule_region. Nor did it try to - take into account register pressure or anything useful like that. - - Revisit when we have a machine model to work with and not before. */ - - if (targetm.sched.adjust_priority) - INSN_PRIORITY (prev) = - targetm.sched.adjust_priority (prev, INSN_PRIORITY (prev)); -} - -/* Advance time on one cycle. */ -HAIFA_INLINE static void -advance_one_cycle (void) -{ - if (targetm.sched.dfa_pre_cycle_insn) - state_transition (curr_state, - targetm.sched.dfa_pre_cycle_insn ()); - - state_transition (curr_state, NULL); - - if (targetm.sched.dfa_post_cycle_insn) - state_transition (curr_state, - targetm.sched.dfa_post_cycle_insn ()); -} - -/* Clock at which the previous instruction was issued. */ -static int last_clock_var; - -/* INSN is the "currently executing insn". Launch each insn which was - waiting on INSN. READY is the ready list which contains the insns - that are ready to fire. CLOCK is the current cycle. The function - returns necessary cycle advance after issuing the insn (it is not - zero for insns in a schedule group). */ - -static int -schedule_insn (rtx insn) -{ - rtx link; - int advance = 0; - - if (sched_verbose >= 1) - { - char buf[2048]; - - print_insn (buf, insn, 0); - buf[40] = 0; - fprintf (sched_dump, ";;\t%3i--> %-40s:", clock_var, buf); - - if (recog_memoized (insn) < 0) - fprintf (sched_dump, "nothing"); - else - print_reservation (sched_dump, insn); - fputc ('\n', sched_dump); - } - - /* Scheduling instruction should have all its dependencies resolved and - should have been removed from the ready list. */ - gcc_assert (INSN_DEP_COUNT (insn) == 0); - gcc_assert (!LOG_LINKS (insn)); - gcc_assert (QUEUE_INDEX (insn) == QUEUE_NOWHERE); - - QUEUE_INDEX (insn) = QUEUE_SCHEDULED; - - /* Now we can free RESOLVED_DEPS list. */ - if (current_sched_info->flags & USE_DEPS_LIST) - free_DEPS_LIST_list (&RESOLVED_DEPS (insn)); - else - free_INSN_LIST_list (&RESOLVED_DEPS (insn)); - - 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); - - /* ??? Probably, if INSN is scheduled prematurely, we should leave - INSN_TICK untouched. This is a machine-dependent issue, actually. */ - INSN_TICK (insn) = clock_var; - - /* Update dependent instructions. */ - for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1)) - { - rtx next = XEXP (link, 0); - - resolve_dep (next, insn); - - 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 (XEXP (link, 1) == 0); - fix_recovery_deps (RECOVERY_BLOCK (insn)); - } - } - - /* 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 (issue_rate > 1 - && GET_CODE (PATTERN (insn)) != USE - && GET_CODE (PATTERN (insn)) != CLOBBER) - { - 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. */ - -/* Delete notes beginning with INSN and put them in the chain - of notes ended by NOTE_LIST. - Returns the insn following the notes. */ - -static rtx -unlink_other_notes (rtx insn, rtx tail) -{ - rtx prev = PREV_INSN (insn); - - 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_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; - } - - insn = next; - } - 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 (rtx insn, rtx tail) -{ - rtx prev = PREV_INSN (insn); - - while (insn != tail && NOTE_NOT_BB_P (insn)) - { - rtx next = NEXT_INSN (insn); - - if (write_symbols != NO_DEBUG && NOTE_LINE_NUMBER (insn) > 0) - { - 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; - } - - /* Record line-number notes so they can be reused. */ - LINE_NOTE (insn) = insn; - } - else - prev = insn; - - insn = next; - } - return insn; -} - -/* Return the head and tail pointers of ebb starting at BEG and ending - at END. */ - -void -get_ebb_head_tail (basic_block beg, basic_block end, rtx *headp, rtx *tailp) -{ - rtx beg_head = BB_HEAD (beg); - rtx beg_tail = BB_END (beg); - rtx end_head = BB_HEAD (end); - rtx end_tail = BB_END (end); - - /* 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 (LABEL_P (beg_head)) - beg_head = NEXT_INSN (beg_head); - - while (beg_head != beg_tail) - if (NOTE_P (beg_head)) - beg_head = NEXT_INSN (beg_head); - else - break; - - *headp = beg_head; - - 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; - - *tailp = end_tail; -} - -/* Return nonzero if there are no real insns in the range [ HEAD, TAIL ]. */ - -int -no_real_insns_p (rtx head, rtx tail) -{ - while (head != NEXT_INSN (tail)) - { - 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 (rtx head, rtx tail) -{ - rtx next_tail; - rtx insn; - - next_tail = NEXT_INSN (tail); - for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) - { - rtx prev; - - /* Farm out notes, and maybe save them in NOTE_LIST. - This is needed to keep the debugger from - getting completely deranged. */ - if (NOTE_NOT_BB_P (insn)) - { - prev = insn; - insn = unlink_line_notes (insn, next_tail); - - gcc_assert (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. */ - -void -save_line_notes (int b, 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; - - next_tail = NEXT_INSN (tail); - - for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) - if (NOTE_P (insn) && NOTE_LINE_NUMBER (insn) > 0) - line = insn; - else - LINE_NOTE (insn) = line; -} - -/* 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 (rtx head, rtx tail) -{ - rtx line, note, prev, new; - int added_notes = 0; - rtx next_tail, insn; - - head = head; - next_tail = NEXT_INSN (tail); - - /* 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 (NOTE_P (line) && NOTE_LINE_NUMBER (line) > 0) - break; - - /* 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 (NOTE_P (insn) && 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 (!NOTE_P (insn) - && INSN_UID (insn) < old_max_uid - && (note = LINE_NOTE (insn)) != 0 - && note != line - && (line == 0 -#ifdef USE_MAPPED_LOCATION - || NOTE_SOURCE_LOCATION (note) != NOTE_SOURCE_LOCATION (line) -#else - || NOTE_LINE_NUMBER (note) != NOTE_LINE_NUMBER (line) - || NOTE_SOURCE_FILE (note) != NOTE_SOURCE_FILE (line) -#endif - )) - { - 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; - set_block_for_insn (note, BLOCK_FOR_INSN (insn)); - } - else - { - added_notes++; - new = emit_note_after (NOTE_LINE_NUMBER (note), prev); -#ifndef USE_MAPPED_LOCATION - NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note); -#endif - } - } - if (sched_verbose && added_notes) - fprintf (sched_dump, ";; added %d line-number notes\n", added_notes); -} - -/* After scheduling the function, delete redundant line notes from the - insns list. */ - -void -rm_redundant_line_notes (void) -{ - 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 (NOTE_P (insn) && NOTE_LINE_NUMBER (insn) > 0) - { - /* If there are no active insns following, INSN is redundant. */ - if (active_insn == 0) - { - notes++; - SET_INSN_DELETED (insn); - } - /* If the line number is unchanged, LINE is redundant. */ - else if (line -#ifdef USE_MAPPED_LOCATION - && NOTE_SOURCE_LOCATION (line) == NOTE_SOURCE_LOCATION (insn) -#else - && NOTE_LINE_NUMBER (line) == NOTE_LINE_NUMBER (insn) - && NOTE_SOURCE_FILE (line) == NOTE_SOURCE_FILE (insn) -#endif -) - { - notes++; - SET_INSN_DELETED (line); - line = insn; - } - else - line = insn; - active_insn = 0; - } - else if (!((NOTE_P (insn) - && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED) - || (NONJUMP_INSN_P (insn) - && (GET_CODE (PATTERN (insn)) == USE - || GET_CODE (PATTERN (insn)) == CLOBBER)))) - active_insn++; - - if (sched_verbose && notes) - fprintf (sched_dump, ";; deleted %d line-number notes\n", notes); -} - -/* Delete notes between HEAD and TAIL and put them in the chain - of notes ended by NOTE_LIST. */ - -void -rm_other_notes (rtx head, rtx tail) -{ - 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)) - { - rtx prev; - - /* Farm out notes, and maybe save them in NOTE_LIST. - This is needed to keep the debugger from - getting completely deranged. */ - if (NOTE_NOT_BB_P (insn)) - { - prev = insn; - - insn = unlink_other_notes (insn, next_tail); - - gcc_assert (prev != tail && prev != head && insn != next_tail); - } - } -} - -/* Functions for computation of registers live/usage info. */ - -/* 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 (rtx x) -{ - if (GET_CODE (x) == CLOBBER - && register_operand (SET_DEST (x), VOIDmode)) - return 1; - if (GET_CODE (x) == SET - && register_operand (SET_DEST (x), VOIDmode)) - { - if (REG_P (SET_DEST (x))) - { - if (!reg_mentioned_p (SET_DEST (x), SET_SRC (x))) - return 1; - else - return 0; - } - return 1; - } - return 0; -} - -/* Calculate INSN_REG_WEIGHT for all insns of a block. */ - -static void -find_insn_reg_weight (basic_block bb) -{ - rtx insn, next_tail, head, tail; - - get_ebb_head_tail (bb, bb, &head, &tail); - next_tail = NEXT_INSN (tail); - - for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) - find_insn_reg_weight1 (insn); -} - -/* Calculate INSN_REG_WEIGHT for single instruction. - Separated from find_insn_reg_weight because of need - to initialize new instruction in generate_recovery_code. */ -static void -find_insn_reg_weight1 (rtx insn) -{ - int reg_weight = 0; - rtx x; - - /* Handle register life information. */ - if (! INSN_P (insn)) - return; - - /* Increment weight for each register born here. */ - x = PATTERN (insn); - reg_weight += find_set_reg_weight (x); - if (GET_CODE (x) == PARALLEL) - { - int j; - for (j = XVECLEN (x, 0) - 1; j >= 0; j--) - { - x = XVECEXP (PATTERN (insn), 0, j); - reg_weight += find_set_reg_weight (x); - } - } - /* Decrement weight for each register that dies here. */ - for (x = REG_NOTES (insn); x; x = XEXP (x, 1)) - { - if (REG_NOTE_KIND (x) == REG_DEAD - || REG_NOTE_KIND (x) == REG_UNUSED) - reg_weight--; - } - - INSN_REG_WEIGHT (insn) = reg_weight; -} - -/* Move insns that became ready to fire from queue to ready list. */ - -static void -queue_to_ready (struct ready_list *ready) -{ - rtx insn; - rtx link; - - q_ptr = NEXT_Q (q_ptr); - - /* 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)) - { - insn = XEXP (link, 0); - q_size -= 1; - - if (sched_verbose >= 2) - fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ", - (*current_sched_info->print_insn) (insn, 0)); - - /* 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)) - { - 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"); - } - } - 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. */ - if (ready->n_ready == 0) - { - int stalls; - - for (stalls = 1; stalls <= max_insn_queue_index; stalls++) - { - if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)])) - { - for (; link; link = XEXP (link, 1)) - { - insn = XEXP (link, 0); - q_size -= 1; - - if (sched_verbose >= 2) - fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ", - (*current_sched_info->print_insn) (insn, 0)); - - ready_add (ready, insn, false); - if (sched_verbose >= 2) - fprintf (sched_dump, "moving to ready with %d stalls\n", stalls); - } - free_INSN_LIST_list (&insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]); - - advance_one_cycle (); - - break; - } - - advance_one_cycle (); - } - - q_ptr = NEXT_Q_AFTER (q_ptr, stalls); - clock_var += stalls; - } -} - -/* 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) -{ - int n_cycles; - rtx prev_insn = last_scheduled_insn; - - 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)) - { - rtx dep_link = 0; - int dep_cost; - - if (!NOTE_P (prev_insn)) - { - dep_link = find_insn_list (insn, INSN_DEPEND (prev_insn)); - if (dep_link) - { - dep_cost = insn_cost (prev_insn, dep_link, insn) ; - if (targetm.sched.is_costly_dependence (prev_insn, insn, - dep_link, dep_cost, - flag_sched_stalled_insns_dep - n_cycles)) - return false; - } - } - - if (GET_MODE (prev_insn) == TImode) /* end of dispatch group */ - break; - } - - if (!prev_insn) - break; - prev_insn = PREV_INSN (prev_insn); - } - } - - return true; -} - - -/* 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. */ - -static void -reemit_notes (rtx insn) -{ - rtx note, last = insn; - - 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)); - - 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 = last_scheduled_insn; - - 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 - || ((current_sched_info->flags & SCHED_RGN) - && IS_SPECULATION_BRANCHY_CHECK_P (insn)) - || (current_sched_info->flags & SCHED_EBB)); - - 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. */ - { - /* NT is needed for assertion below. */ - rtx nt = current_sched_info->next_tail; - - 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); - } - - set_block_for_insn (insn, bb); - - /* Update BB_END, if needed. */ - if (BB_END (bb) == last) - BB_END (bb) = insn; - } - - reemit_notes (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. */ -static int cycle_issued_insns; - -/* 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. */ -static int -max_issue (struct ready_list *ready, int *index, int max_points) -{ - int n, i, all, n_ready, best, delay, tries_num, points = -1; - struct choice_entry *top; - rtx insn; - - best = 0; - memcpy (choice_stack->state, curr_state, dfa_state_size); - top = choice_stack; - top->rest = cached_first_cycle_multipass_dfa_lookahead; - top->n = 0; - n_ready = ready->n_ready; - for (all = i = 0; i < n_ready; i++) - if (!ready_try [i]) - all++; - i = 0; - tries_num = 0; - for (;;) - { - if (top->rest == 0 || i >= n_ready) - { - if (top == choice_stack) - break; - if (best < top - choice_stack && ready_try [0]) - { - best = top - choice_stack; - *index = choice_stack [1].index; - points = top->n; - if (top->n == max_points || best == all) - break; - } - i = top->index; - ready_try [i] = 0; - top--; - memcpy (curr_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 (curr_state, insn); - if (delay < 0) - { - if (state_dead_lock_p (curr_state)) - top->rest = 0; - else - top->rest--; - n = top->n; - if (memcmp (top->state, curr_state, dfa_state_size) != 0) - n += ISSUE_POINTS (insn); - top++; - top->rest = cached_first_cycle_multipass_dfa_lookahead; - top->index = i; - top->n = n; - memcpy (top->state, curr_state, dfa_state_size); - ready_try [i] = 1; - i = -1; - } - } - i++; - } - while (top != choice_stack) - { - ready_try [top->index] = 0; - top--; - } - memcpy (curr_state, choice_stack->state, dfa_state_size); - - if (sched_verbose >= 4) - fprintf (sched_dump, ";;\t\tChoosed insn : %s; points: %d/%d\n", - (*current_sched_info->print_insn) (ready_element (ready, *index), - 0), - points, max_points); - - return best; -} - -/* The following function chooses insn from READY and modifies - *N_READY and READY. The following function is used only for first - cycle multipass scheduling. */ - -static rtx -choose_ready (struct ready_list *ready) -{ - int lookahead = 0; - - if (targetm.sched.first_cycle_multipass_dfa_lookahead) - lookahead = targetm.sched.first_cycle_multipass_dfa_lookahead (); - if (lookahead <= 0 || SCHED_GROUP_P (ready_element (ready, 0))) - return ready_remove_first (ready); - else - { - /* Try to choose the better insn. */ - int index = 0, i, n; - rtx insn; - int more_issue, max_points, try_data = 1, try_control = 1; - - if (cached_first_cycle_multipass_dfa_lookahead != lookahead) - { - cached_first_cycle_multipass_dfa_lookahead = lookahead; - max_lookahead_tries = 100; - for (i = 0; i < issue_rate; i++) - max_lookahead_tries *= lookahead; - } - insn = ready_element (ready, 0); - if (INSN_CODE (insn) < 0) - return ready_remove_first (ready); - - 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; - } - } - } - - if ((!try_data && (TODO_SPEC (insn) & DATA_SPEC)) - || (!try_control && (TODO_SPEC (insn) & CONTROL_SPEC)) - || (targetm.sched.first_cycle_multipass_dfa_lookahead_guard_spec - && !targetm.sched.first_cycle_multipass_dfa_lookahead_guard_spec - (insn))) - /* Discard speculative instruction that stands first in the ready - list. */ - { - change_queue_index (insn, 1); - return 0; - } - - max_points = ISSUE_POINTS (insn); - more_issue = issue_rate - cycle_issued_insns - 1; - - for (i = 1; i < ready->n_ready; i++) - { - insn = ready_element (ready, i); - ready_try [i] - = (INSN_CODE (insn) < 0 - || (!try_data && (TODO_SPEC (insn) & DATA_SPEC)) - || (!try_control && (TODO_SPEC (insn) & CONTROL_SPEC)) - || (targetm.sched.first_cycle_multipass_dfa_lookahead_guard - && !targetm.sched.first_cycle_multipass_dfa_lookahead_guard - (insn))); - - if (!ready_try [i] && more_issue-- > 0) - max_points += ISSUE_POINTS (insn); - } - - if (max_issue (ready, &index, max_points) == 0) - return ready_remove_first (ready); - else - return ready_remove (ready, index); - } -} - -/* Use forward list scheduling to rearrange insns of block pointed to by - TARGET_BB, possibly bringing insns from subsequent blocks in the same - region. */ - -void -schedule_block (basic_block *target_bb, int rgn_n_insns1) -{ - 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; - rtx next_tail = current_sched_info->next_tail; - rtx head = NEXT_INSN (prev_head); - rtx tail = PREV_INSN (next_tail); - - /* We used to have code to avoid getting parameters moved from hard - argument registers into pseudos. - - However, it was removed when it proved to be of marginal benefit - and caused problems because schedule_block and compute_forward_dependences - had different notions of what the "head" insn was. */ - - gcc_assert (head != tail || INSN_P (head)); - - added_recovery_block_p = false; - - /* Debug info. */ - if (sched_verbose) - dump_new_block_header (0, *target_bb, head, tail); - - state_reset (curr_state); - - /* Allocate the ready list. */ - readyp = &ready; - ready.vec = NULL; - ready_try = NULL; - choice_stack = NULL; - - rgn_n_insns = -1; - extend_ready (rgn_n_insns1 + 1); - - ready.first = ready.veclen - 1; - ready.n_ready = 0; - - /* 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); - - /* 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; - - insn_queue = alloca ((max_insn_queue_index + 1) * sizeof (rtx)); - memset (insn_queue, 0, (max_insn_queue_index + 1) * sizeof (rtx)); - - /* Start just before the beginning of time. */ - clock_var = -1; - - /* We need queue and ready lists and clock_var be initialized - in try_ready () (which is called through init_ready_list ()). */ - (*current_sched_info->init_ready_list) (); - - /* The algorithm is O(n^2) in the number of ready insns at any given - time in the worst case. Before reload we are more likely to have - big lists so truncate them to a reasonable size. */ - if (!reload_completed && ready.n_ready > MAX_SCHED_READY_INSNS) - { - ready_sort (&ready); - - /* 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 on entry: %d insns\n", ready.n_ready); - fprintf (sched_dump, - ";;\t\t before reload => truncated to %d insns\n", i); - } - - /* Delay all insns past it for 1 cycle. */ - while (i < ready.n_ready) - queue_insn (ready_remove (&ready, i), 1); - } - - /* Now we can restore basic block notes and maintain precise cfg. */ - restore_bb_notes (*target_bb); - - 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 - { - 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); - - if (sort_p) - { - /* Sort the ready list based on priority. */ - ready_sort (&ready); - - if (sched_verbose >= 2) - { - fprintf (sched_dump, ";;\t\tReady list after ready_sort: "); - debug_ready_list (&ready); - } - } - - /* 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; - - first_cycle_insn_p = 1; - cycle_issued_insns = 0; - for (;;) - { - rtx insn; - int cost; - bool asm_p = false; - - if (sched_verbose >= 2) - { - fprintf (sched_dump, ";;\tReady list (t = %3d): ", - clock_var); - debug_ready_list (&ready); - } - - if (ready.n_ready == 0 - && can_issue_more - && reload_completed) - { - /* Allow scheduling insns directly from the queue in case - there's nothing better to do (ready list is empty) but - 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); - } - - if (ready.n_ready == 0 || !can_issue_more - || state_dead_lock_p (curr_state) - || !(*current_sched_info->schedule_more_p) ()) - break; - - /* Select and remove the insn from the ready list. */ - if (sort_p) - { - insn = choose_ready (&ready); - if (!insn) - continue; - } - 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 tryed 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 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 = 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) - { - fprintf (sched_dump, ";;\tReady list (final): "); - debug_ready_list (&ready); - } - - 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--) - { - rtx x; - - x = ready_element (&ready, i); - QUEUE_INDEX (x) = QUEUE_NOWHERE; - TODO_SPEC (x) = (TODO_SPEC (x) & ~SPECULATIVE) | HARD_DEP; - } - - 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]); - } - } - - if (!current_sched_info->queue_must_finish_empty - || added_recovery_block_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) - targetm.sched.md_finish (sched_dump, sched_verbose); - - /* Update head/tail boundaries. */ - head = NEXT_INSN (prev_head); - tail = last_scheduled_insn; - - /* Restore-other-notes: NOTE_LIST is the end of a chain of notes - previously found among the insns. Insert them at the beginning - of the insns. */ - if (note_list != 0) - { - basic_block head_bb = BLOCK_FOR_INSN (head); - rtx note_head = note_list; - - while (PREV_INSN (note_head)) - { - set_block_for_insn (note_head, head_bb); - note_head = PREV_INSN (note_head); - } - /* In the above cycle we've missed this note: */ - set_block_for_insn (note_head, head_bb); - - PREV_INSN (note_head) = PREV_INSN (head); - NEXT_INSN (PREV_INSN (head)) = note_head; - PREV_INSN (head) = note_list; - NEXT_INSN (note_list) = head; - head = note_head; - } - - /* Debugging. */ - if (sched_verbose) - { - fprintf (sched_dump, ";; total time = %d\n;; new head = %d\n", - clock_var, INSN_UID (head)); - fprintf (sched_dump, ";; new tail = %d\n\n", - INSN_UID (tail)); - } - - current_sched_info->head = head; - current_sched_info->tail = tail; - - free (ready.vec); - - free (ready_try); - for (i = 0; i <= rgn_n_insns; i++) - free (choice_stack [i].state); - free (choice_stack); -} - -/* Set_priorities: compute priority of each insn in the block. */ - -int -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; - - 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 (!INSN_P (insn)) - continue; - - n_insn++; - (void) priority (insn); - - if (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; -} - -/* Next LUID to assign to an instruction. */ -static int luid; - -/* Initialize some global state for the scheduler. */ - -void -sched_init (void) -{ - basic_block b; - rtx insn; - int i; - - /* Switch to working copy of sched_info. */ - memcpy (¤t_sched_info_var, current_sched_info, - sizeof (current_sched_info_var)); - current_sched_info = ¤t_sched_info_var; - - /* Disable speculative loads in their presence if cc0 defined. */ -#ifdef HAVE_cc0 - flag_schedule_speculative_load = 0; -#endif - - /* Set dump and sched_verbose for the desired debugging output. If no - dump-file was specified, but -fsched-verbose=N (any N), print to stderr. - For -fsched-verbose=N, N>=10, print everything to stderr. */ - sched_verbose = sched_verbose_param; - if (sched_verbose_param == 0 && dump_file) - sched_verbose = 1; - sched_dump = ((sched_verbose_param >= 10 || !dump_file) - ? stderr : dump_file); - - /* Initialize SPEC_INFO. */ - if (targetm.sched.set_sched_flags) - { - spec_info = &spec_info_var; - targetm.sched.set_sched_flags (spec_info); - if (current_sched_info->flags & DO_SPECULATION) - spec_info->weakness_cutoff = - (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF) * MAX_DEP_WEAK) / 100; - else - /* So we won't read anything accidentally. */ - spec_info = 0; -#ifdef ENABLE_CHECKING - check_sched_flags (); -#endif - } - 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 (); - else - issue_rate = 1; - - if (cached_issue_rate != issue_rate) - { - cached_issue_rate = issue_rate; - /* To invalidate max_lookahead_tries: */ - cached_first_cycle_multipass_dfa_lookahead = 0; - } - - old_max_uid = 0; - h_i_d = 0; - extend_h_i_d (); - - for (i = 0; i < old_max_uid; i++) - { - h_i_d[i].cost = -1; - h_i_d[i].todo_spec = HARD_DEP; - h_i_d[i].queue_index = QUEUE_NOWHERE; - h_i_d[i].tick = INVALID_TICK; - h_i_d[i].inter_tick = INVALID_TICK; - } - - if (targetm.sched.init_dfa_pre_cycle_insn) - targetm.sched.init_dfa_pre_cycle_insn (); - - if (targetm.sched.init_dfa_post_cycle_insn) - targetm.sched.init_dfa_post_cycle_insn (); - - dfa_start (); - dfa_state_size = state_size (); - curr_state = xmalloc (dfa_state_size); - - h_i_d[0].luid = 0; - luid = 1; - FOR_EACH_BB (b) - for (insn = BB_HEAD (b); ; insn = NEXT_INSN (insn)) - { - INSN_LUID (insn) = luid; - - /* Increment the next luid, unless this is a note. We don't - really need separate IDs for notes and we don't want to - schedule differently depending on whether or not there are - line-number notes, i.e., depending on whether or not we're - generating debugging information. */ - if (!NOTE_P (insn)) - ++luid; - - if (insn == BB_END (b)) - break; - } - - init_dependency_caches (luid); - - init_alias_analysis (); - - line_note_head = 0; - old_last_basic_block = 0; - glat_start = 0; - glat_end = 0; - extend_bb (0); - - if (current_sched_info->flags & USE_GLAT) - init_glat (); - - /* Compute INSN_REG_WEIGHT for all blocks. We must do this before - removing death notes. */ - FOR_EACH_BB_REVERSE (b) - find_insn_reg_weight (b); - - if (targetm.sched.md_init_global) - targetm.sched.md_init_global (sched_dump, sched_verbose, old_max_uid); - - nr_begin_data = nr_begin_control = nr_be_in_data = nr_be_in_control = 0; - before_recovery = 0; - -#ifdef ENABLE_CHECKING - /* This is used preferably for finding bugs in check_cfg () itself. */ - check_cfg (0, 0); -#endif -} - -/* Free global data used during insn scheduling. */ - -void -sched_finish (void) -{ - free (h_i_d); - free (curr_state); - dfa_finish (); - free_dependency_caches (); - end_alias_analysis (); - free (line_note_head); - free_glat (); - - if (targetm.sched.md_finish_global) - targetm.sched.md_finish_global (sched_dump, sched_verbose); - - if (spec_info && spec_info->dump) - { - char c = reload_completed ? 'a' : 'b'; - - 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); - } - -#ifdef ENABLE_CHECKING - /* After reload ia64 backend clobbers CFG, so can't check anything. */ - if (!reload_completed) - check_cfg (0, 0); -#endif - - current_sched_info = NULL; -} - -/* Fix INSN_TICKs of the instructions in the current block as well as - 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; - 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)) - { - int tick; - rtx link; - - tick = INSN_TICK (head); - gcc_assert (tick >= MIN_TICK); - - /* Fix INSN_TICK of instruction from just scheduled block. */ - if (!bitmap_bit_p (&processed, INSN_LUID (head))) - { - bitmap_set_bit (&processed, INSN_LUID (head)); - tick -= next_clock; - - if (tick < MIN_TICK) - tick = MIN_TICK; - - INSN_TICK (head) = tick; - } - - for (link = INSN_DEPEND (head); link; link = XEXP (link, 1)) - { - rtx next; - - next = XEXP (link, 0); - 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); -} - -/* 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; - rtx link; - - ts = &TODO_SPEC (next); - old_ts = *ts; - - gcc_assert (!(old_ts & ~(SPECULATIVE | HARD_DEP)) - && ((old_ts & HARD_DEP) - || (old_ts & SPECULATIVE))); - - if (!(current_sched_info->flags & DO_SPECULATION)) - { - if (!LOG_LINKS (next)) - *ts &= ~HARD_DEP; - } - else - { - *ts &= ~SPECULATIVE & ~HARD_DEP; - - link = LOG_LINKS (next); - if (link) - { - /* LOG_LINKS are maintained sorted. - So if DEP_STATUS of the first dep is SPECULATIVE, - than all other deps are speculative too. */ - if (DEP_STATUS (link) & SPECULATIVE) - { - /* Now we've got NEXT with speculative deps only. - 1. Look at the deps to see what we have to do. - 2. Check if we can do 'todo'. */ - *ts = DEP_STATUS (link) & SPECULATIVE; - while ((link = XEXP (link, 1))) - *ts = ds_merge (*ts, DEP_STATUS (link) & SPECULATIVE); - - if (dep_weak (*ts) < spec_info->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 = 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); - - 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. */ - { - 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) -{ - rtx link; - int tick, delay; - - link = RESOLVED_DEPS (next); - - if (link) - { - int full_p; - - 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; - do - { - rtx pro; - int tick1; - - pro = XEXP (link, 0); - gcc_assert (INSN_TICK (pro) >= MIN_TICK); - - tick1 = INSN_TICK (pro) + insn_cost (pro, link, next); - if (tick1 > tick) - tick = tick1; - } - while ((link = XEXP (link, 1)) && full_p); - } - 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; - - /* 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"); - } -} - -/* INSN is being scheduled. Resolve the dependence between INSN and NEXT. */ -static void -resolve_dep (rtx next, rtx insn) -{ - rtx dep; - - INSN_DEP_COUNT (next)--; - - dep = remove_list_elem (insn, &LOG_LINKS (next)); - XEXP (dep, 1) = RESOLVED_DEPS (next); - RESOLVED_DEPS (next) = dep; - - gcc_assert ((INSN_DEP_COUNT (next) != 0 || !LOG_LINKS (next)) - && (LOG_LINKS (next) || INSN_DEP_COUNT (next) == 0)); -} - -/* Extend H_I_D data. */ -static void -extend_h_i_d (void) -{ - /* We use LUID 0 for the fake insn (UID 0) which holds dependencies for - pseudos which do not cross calls. */ - int new_max_uid = get_max_uid() + 1; - - h_i_d = xrecalloc (h_i_d, new_max_uid, old_max_uid, sizeof (*h_i_d)); - old_max_uid = new_max_uid; - - if (targetm.sched.h_i_d_extended) - targetm.sched.h_i_d_extended (); -} - -/* Extend READY, READY_TRY and CHOICE_STACK arrays. - N_NEW_INSNS is the number of additional elements to allocate. */ -static void -extend_ready (int n_new_insns) -{ - int i; - - readyp->veclen = rgn_n_insns + n_new_insns + 1 + issue_rate; - readyp->vec = XRESIZEVEC (rtx, readyp->vec, readyp->veclen); - - ready_try = xrecalloc (ready_try, rgn_n_insns + n_new_insns + 1, - rgn_n_insns + 1, sizeof (char)); - - rgn_n_insns += n_new_insns; - - choice_stack = XRESIZEVEC (struct choice_entry, choice_stack, - rgn_n_insns + 1); - - for (i = rgn_n_insns; n_new_insns--; i--) - choice_stack[i].state = xmalloc (dfa_state_size); -} - -/* Extend global scheduler structures (those, that live across calls to - schedule_block) to include information about just emitted INSN. */ -static void -extend_global (rtx insn) -{ - gcc_assert (INSN_P (insn)); - /* These structures have scheduler scope. */ - extend_h_i_d (); - init_h_i_d (insn); - - extend_dependency_caches (1, 0); -} - -/* Extends global and local scheduler structures to include information - about just emitted INSN. */ -static void -extend_all (rtx insn) -{ - extend_global (insn); - - /* These structures have block scope. */ - extend_ready (1); - - (*current_sched_info->add_remove_insn) (insn, 0); -} - -/* Initialize h_i_d entry of the new INSN with default values. - Values, that are not explicitly initialized here, hold zero. */ -static void -init_h_i_d (rtx insn) -{ - INSN_LUID (insn) = luid++; - INSN_COST (insn) = -1; - TODO_SPEC (insn) = HARD_DEP; - QUEUE_INDEX (insn) = QUEUE_NOWHERE; - INSN_TICK (insn) = INVALID_TICK; - INTER_TICK (insn) = INVALID_TICK; - find_insn_reg_weight1 (insn); -} - -/* 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 LINK list and TWIN. */ -static void -process_insn_depend_be_in_spec (rtx link, rtx twin, ds_t fs) -{ - for (; link; link = XEXP (link, 1)) - { - ds_t ds; - rtx consumer; - - consumer = XEXP (link, 0); - - ds = DEP_STATUS (link); - - 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. */ - dep_weak (ds) <= dep_weak (fs)) - /* Transform it to be in speculative. */ - ds = (ds & ~BEGIN_SPEC) | fs; - } - else - /* Mark the dep as 'be in speculative'. */ - ds |= fs; - } - - add_back_forw_dep (consumer, twin, REG_NOTE_KIND (link), ds); - } -} - -/* 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; -} - -/* Generates recovery code for BE_IN speculative INSN. */ -static void -add_to_speculative_block (rtx insn) -{ - ds_t ts; - rtx link, twins = NULL; - - 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 (link = LOG_LINKS (insn); link;) - { - rtx check; - - check = XEXP (link, 0); - - if (IS_SPECULATION_SIMPLE_CHECK_P (check)) - { - create_check_block_twin (check, true); - link = LOG_LINKS (insn); - } - else - link = XEXP (link, 1); - } - - clear_priorities (insn); - - do - { - rtx link, check, twin; - basic_block rec; - - link = LOG_LINKS (insn); - gcc_assert (!(DEP_STATUS (link) & BEGIN_SPEC) - && (DEP_STATUS (link) & BE_IN_SPEC) - && (DEP_STATUS (link) & DEP_TYPES) == DEP_TRUE); - - check = XEXP (link, 0); - - gcc_assert (!IS_SPECULATION_CHECK_P (check) && !ORIG_PAT (check) - && QUEUE_INDEX (check) == QUEUE_NOWHERE); - - rec = BLOCK_FOR_INSN (check); - - twin = emit_insn_before (copy_rtx (PATTERN (insn)), BB_END (rec)); - extend_global (twin); - - RESOLVED_DEPS (twin) = copy_DEPS_LIST_list (RESOLVED_DEPS (insn)); - - 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. */ - do - { - add_back_forw_dep (twin, check, REG_DEP_TRUE, DEP_TRUE); - - do - { - link = XEXP (link, 1); - if (link) - { - check = XEXP (link, 0); - if (BLOCK_FOR_INSN (check) == rec) - break; - } - else - break; - } - while (1); - } - while (link); - - process_insn_depend_be_in_spec (INSN_DEPEND (insn), twin, ts); - - for (link = LOG_LINKS (insn); link;) - { - check = XEXP (link, 0); - - if (BLOCK_FOR_INSN (check) == rec) - { - delete_back_forw_dep (insn, check); - link = LOG_LINKS (insn); - } - else - link = XEXP (link, 1); - } - } - while (LOG_LINKS (insn)); - - /* We can't add the dependence between insn and twin earlier because - that would make twin appear in the INSN_DEPEND (insn). */ - while (twins) - { - rtx twin; - - twin = XEXP (twins, 0); - calc_priorities (twin); - add_back_forw_dep (twin, insn, REG_DEP_OUTPUT, DEP_OUTPUT); - - twin = XEXP (twins, 1); - free_INSN_LIST_node (twins); - twins = twin; - } -} - -/* 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; -} - -/* Return the probability of speculation success for the speculation - status DS. */ -static dw_t -dep_weak (ds_t ds) -{ - ds_t res = 1, dt; - int n = 0; - - dt = FIRST_SPEC_TYPE; - do - { - if (ds & dt) - { - res *= (ds_t) get_dep_weak (ds, dt); - n++; - } - - if (dt == LAST_SPEC_TYPE) - break; - dt <<= SPEC_TYPE_SHIFT; - } - while (1); - - gcc_assert (n); - while (--n) - res /= MAX_DEP_WEAK; - - if (res < MIN_DEP_WEAK) - res = MIN_DEP_WEAK; - - gcc_assert (res <= MAX_DEP_WEAK); - - return (dw_t) res; -} - -/* Helper function. - Find fallthru edge from PRED. */ -static edge -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; -} - -/* Initialize BEFORE_RECOVERY variable. */ -static void -init_before_recovery (void) -{ - 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; - - single = create_empty_bb (last); - empty = create_empty_bb (single); - - 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)++; - extend_global (x); - - emit_barrier_after (x); - - add_block (empty, 0); - add_block (single, 0); - - before_recovery = single; - - 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. */ -static basic_block -create_recovery_block (void) -{ - rtx label; - rtx barrier; - basic_block rec; - - added_recovery_block_p = true; - - if (!before_recovery) - init_before_recovery (); - - 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); - - /* Recovery block always end 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); - - before_recovery = rec; - - return rec; -} - -/* 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, link; - ds_t fs; - - gcc_assert (ORIG_PAT (insn) - && (!mutate_p - || (IS_SPECULATION_SIMPLE_CHECK_P (insn) - && !(TODO_SPEC (insn) & SPECULATIVE)))); - - /* Create recovery block. */ - if (mutate_p || targetm.sched.needs_block_p (insn)) - { - rec = create_recovery_block (); - label = BB_HEAD (rec); - } - else - { - rec = EXIT_BLOCK_PTR; - label = 0; - } - - /* Emit CHECK. */ - check = targetm.sched.gen_check (insn, label, mutate_p); - - 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. */ - extend_all (check); - 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) - { - rtx link; - - for (link = RESOLVED_DEPS (insn); link; link = XEXP (link, 1)) - if (DEP_STATUS (link) & DEP_OUTPUT) - { - RESOLVED_DEPS (check) = - alloc_DEPS_LIST (XEXP (link, 0), RESOLVED_DEPS (check), DEP_TRUE); - PUT_REG_NOTE_KIND (RESOLVED_DEPS (check), REG_DEP_TRUE); - } - - twin = emit_insn_after (ORIG_PAT (insn), BB_END (rec)); - extend_global (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). */ - } - - RESOLVED_DEPS (twin) = copy_DEPS_LIST_list (RESOLVED_DEPS (insn)); - - if (rec != EXIT_BLOCK_PTR) - /* In case of branchy check, fix CFG. */ - { - basic_block first_bb, second_bb; - rtx jump; - edge e; - int edge_flags; - - first_bb = BLOCK_FOR_INSN (check); - e = split_block (first_bb, check); - /* split_block emits note if *check == BB_END. Probably it - is better to rip that note off. */ - gcc_assert (e->src == first_bb); - second_bb = e->dest; - - /* This is fixing of incoming edge. */ - /* ??? Which other flags should be specified? */ - if (BB_PARTITION (first_bb) != BB_PARTITION (rec)) - /* Partition type is the same, if it is "unpartitioned". */ - edge_flags = EDGE_CROSSING; - else - edge_flags = 0; - - e = make_edge (first_bb, rec, edge_flags); - - add_block (second_bb, first_bb); - - gcc_assert (NOTE_INSN_BASIC_BLOCK_P (BB_HEAD (second_bb))); - label = block_label (second_bb); - jump = emit_jump_insn_after (gen_jump (label), BB_END (rec)); - JUMP_LABEL (jump) = label; - LABEL_NUSES (label)++; - extend_global (jump); - - if (BB_PARTITION (second_bb) != BB_PARTITION (rec)) - /* Partition type is the same, if it is "unpartitioned". */ - { - /* Rewritten from cfgrtl.c. */ - if (flag_reorder_blocks_and_partition - && targetm.have_named_sections - /*&& !any_condjump_p (jump)*/) - /* any_condjump_p (jump) == false. - We don't need the same note for the check because - any_condjump_p (check) == true. */ - { - REG_NOTES (jump) = gen_rtx_EXPR_LIST (REG_CROSSING_JUMP, - NULL_RTX, - REG_NOTES (jump)); - } - edge_flags = EDGE_CROSSING; - } - else - edge_flags = 0; - - make_single_succ_edge (rec, second_bb, edge_flags); - - add_block (rec, EXIT_BLOCK_PTR); - } - - /* Move backward dependences from INSN to CHECK and - move forward dependences from INSN to TWIN. */ - for (link = LOG_LINKS (insn); link; link = XEXP (link, 1)) - { - 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 (link); - - if (ds & BEGIN_SPEC) - { - gcc_assert (!mutate_p); - ds &= ~BEGIN_SPEC; - } - - if (rec != EXIT_BLOCK_PTR) - { - add_back_forw_dep (check, XEXP (link, 0), REG_NOTE_KIND (link), ds); - add_back_forw_dep (twin, XEXP (link, 0), REG_NOTE_KIND (link), ds); - } - else - add_back_forw_dep (check, XEXP (link, 0), REG_NOTE_KIND (link), ds); - } - - for (link = LOG_LINKS (insn); link;) - if ((DEP_STATUS (link) & BEGIN_SPEC) - || mutate_p) - /* We can delete this dep only if we totally overcome it with - BEGIN_SPECULATION. */ - { - delete_back_forw_dep (insn, XEXP (link, 0)); - link = LOG_LINKS (insn); - } - else - link = XEXP (link, 1); - - 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; - - 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_depend_be_in_spec (INSN_DEPEND (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) - { - add_back_forw_dep (check, insn, REG_DEP_TRUE, DEP_TRUE); - add_back_forw_dep (twin, insn, REG_DEP_OUTPUT, DEP_OUTPUT); - } - else - { - if (spec_info->dump) - fprintf (spec_info->dump, ";;\t\tRemoved simple check : %s\n", - (*current_sched_info->print_insn) (insn, 0)); - - for (link = INSN_DEPEND (insn); link; link = INSN_DEPEND (insn)) - delete_back_forw_dep (XEXP (link, 0), insn); - - if (QUEUE_INDEX (insn) != QUEUE_NOWHERE) - try_ready (check); - - sched_remove_insn (insn); - } - - add_back_forw_dep (twin, check, REG_DEP_ANTI, DEP_ANTI); - } - else - add_back_forw_dep (check, insn, REG_DEP_TRUE, DEP_TRUE | DEP_OUTPUT); - - if (!mutate_p) - /* Fix priorities. If MUTATE_P is nonzero, this is not necessary, - because it'll be done later in add_to_speculative_block. */ - { - clear_priorities (twin); - calc_priorities (twin); - } -} - -/* 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, link, jump, ready_list = 0; - bitmap_head in_ready; - - 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 - { - for (link = INSN_DEPEND (insn); link;) - { - rtx consumer; - - consumer = XEXP (link, 0); - - if (BLOCK_FOR_INSN (consumer) != rec) - { - delete_back_forw_dep (consumer, insn); - - 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)); - } - - link = INSN_DEPEND (insn); - } - else - { - gcc_assert ((DEP_STATUS (link) & DEP_TYPES) == DEP_TRUE); - - link = XEXP (link, 1); - } - } - - 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); -} - -/* The function saves line notes at the beginning of block B. */ -static void -associate_line_notes_with_blocks (basic_block b) -{ - rtx line; - - for (line = BB_HEAD (b); line; line = PREV_INSN (line)) - if (NOTE_P (line) && NOTE_LINE_NUMBER (line) > 0) - { - line_note_head[b->index] = line; - break; - } - /* Do a forward search as well, since we won't get to see the first - notes in a basic block. */ - for (line = BB_HEAD (b); line; line = NEXT_INSN (line)) - { - if (INSN_P (line)) - break; - if (NOTE_P (line) && NOTE_LINE_NUMBER (line) > 0) - line_note_head[b->index] = line; - } -} - -/* Changes pattern of the INSN to NEW_PAT. */ -static void -change_pattern (rtx insn, rtx new_pat) -{ - int t; - - t = validate_change (insn, &PATTERN (insn), new_pat, 0); - gcc_assert (t); - /* Invalidate INSN_COST, so it'll be recalculated. */ - INSN_COST (insn) = -1; - /* Invalidate INSN_TICK, so it'll be recalculated. */ - INSN_TICK (insn) = INVALID_TICK; - dfa_clear_single_insn_cache (insn); -} - - -/* -1 - can't speculate, - 0 - for speculation with REQUEST mode it is OK to use - current instruction pattern, - 1 - need to change pattern for *NEW_PAT to be speculative. */ -static int -speculate_insn (rtx insn, ds_t request, rtx *new_pat) -{ - gcc_assert (current_sched_info->flags & DO_SPECULATION - && (request & SPECULATIVE)); - - if (!NONJUMP_INSN_P (insn) - || HAS_INTERNAL_DEP (insn) - || SCHED_GROUP_P (insn) - || side_effects_p (PATTERN (insn)) - || (request & spec_info->mask) != request) - return -1; - - gcc_assert (!IS_SPECULATION_CHECK_P (insn)); - - if (request & BE_IN_SPEC) - { - if (may_trap_p (PATTERN (insn))) - return -1; - - if (!(request & BEGIN_SPEC)) - return 0; - } - - return targetm.sched.speculate_insn (insn, request & BEGIN_SPEC, new_pat); -} - -/* 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 = xmalloc (last_basic_block * sizeof (*bb_header)); - - /* 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; -} - -/* Extend per basic block data structures of the scheduler. - If BB is NULL, initialize structures for the whole CFG. - Otherwise, initialize them for the just created BB. */ -static void -extend_bb (basic_block bb) -{ - rtx insn; - - if (write_symbols != NO_DEBUG) - { - /* 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. */ - line_note_head = xrecalloc (line_note_head, last_basic_block, - old_last_basic_block, - sizeof (*line_note_head)); - - if (bb) - associate_line_notes_with_blocks (bb); - else - FOR_EACH_BB (bb) - associate_line_notes_with_blocks (bb); - } - - old_last_basic_block = last_basic_block; - - if (current_sched_info->flags & USE_GLAT) - { - glat_start = xrealloc (glat_start, - last_basic_block * sizeof (*glat_start)); - glat_end = xrealloc (glat_end, last_basic_block * sizeof (*glat_end)); - } - - /* The following is done to keep current_sched_info->next_tail non null. */ - - insn = BB_END (EXIT_BLOCK_PTR->prev_bb); - if (NEXT_INSN (insn) == 0 - || (!NOTE_P (insn) - && !LABEL_P (insn) - /* Don't emit a NOTE if it would end up before a BARRIER. */ - && !BARRIER_P (NEXT_INSN (insn)))) - { - emit_note_after (NOTE_INSN_DELETED, insn); - /* Make insn to appear outside BB. */ - BB_END (EXIT_BLOCK_PTR->prev_bb) = insn; - } -} - -/* Add a basic block BB to extended basic block EBB. - If EBB is EXIT_BLOCK_PTR, then BB is recovery block. - If EBB is NULL, then BB should be a new region. */ -void -add_block (basic_block bb, basic_block ebb) -{ - gcc_assert (current_sched_info->flags & DETACH_LIFE_INFO - && bb->il.rtl->global_live_at_start == 0 - && bb->il.rtl->global_live_at_end == 0); - - extend_bb (bb); - - glat_start[bb->index] = 0; - glat_end[bb->index] = 0; - - if (current_sched_info->add_block) - /* This changes only data structures of the front-end. */ - current_sched_info->add_block (bb, ebb); -} - -/* Helper function. - Fix CFG after both in- and inter-block movement of - control_flow_insn_p JUMP. */ -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 (current_sched_info->flags & SCHED_EBB - || 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); - - if (current_sched_info->fix_recovery_cfg) - current_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; -} - -/* Initialize GLAT (global_live_at_{start, end}) structures. - GLAT structures are used to substitute global_live_{start, end} - regsets during scheduling. This is necessary to use such functions as - split_block (), as they assume consistency of register live information. */ -static void -init_glat (void) -{ - basic_block bb; - - FOR_ALL_BB (bb) - init_glat1 (bb); -} - -/* Helper function for init_glat. */ -static void -init_glat1 (basic_block bb) -{ - gcc_assert (bb->il.rtl->global_live_at_start != 0 - && bb->il.rtl->global_live_at_end != 0); - - glat_start[bb->index] = bb->il.rtl->global_live_at_start; - glat_end[bb->index] = bb->il.rtl->global_live_at_end; - - if (current_sched_info->flags & DETACH_LIFE_INFO) - { - bb->il.rtl->global_live_at_start = 0; - bb->il.rtl->global_live_at_end = 0; - } -} - -/* Attach reg_live_info back to basic blocks. - Also save regsets, that should not have been changed during scheduling, - for checking purposes (see check_reg_live). */ -void -attach_life_info (void) -{ - basic_block bb; - - FOR_ALL_BB (bb) - attach_life_info1 (bb); -} - -/* Helper function for attach_life_info. */ -static void -attach_life_info1 (basic_block bb) -{ - gcc_assert (bb->il.rtl->global_live_at_start == 0 - && bb->il.rtl->global_live_at_end == 0); - - if (glat_start[bb->index]) - { - gcc_assert (glat_end[bb->index]); - - bb->il.rtl->global_live_at_start = glat_start[bb->index]; - bb->il.rtl->global_live_at_end = glat_end[bb->index]; - - /* Make them NULL, so they won't be freed in free_glat. */ - glat_start[bb->index] = 0; - glat_end[bb->index] = 0; - -#ifdef ENABLE_CHECKING - if (bb->index < NUM_FIXED_BLOCKS - || current_sched_info->region_head_or_leaf_p (bb, 0)) - { - glat_start[bb->index] = ALLOC_REG_SET (®_obstack); - COPY_REG_SET (glat_start[bb->index], - bb->il.rtl->global_live_at_start); - } - - if (bb->index < NUM_FIXED_BLOCKS - || current_sched_info->region_head_or_leaf_p (bb, 1)) - { - glat_end[bb->index] = ALLOC_REG_SET (®_obstack); - COPY_REG_SET (glat_end[bb->index], bb->il.rtl->global_live_at_end); - } -#endif - } - else - { - gcc_assert (!glat_end[bb->index]); - - bb->il.rtl->global_live_at_start = ALLOC_REG_SET (®_obstack); - bb->il.rtl->global_live_at_end = ALLOC_REG_SET (®_obstack); - } -} - -/* Free GLAT information. */ -static void -free_glat (void) -{ -#ifdef ENABLE_CHECKING - if (current_sched_info->flags & DETACH_LIFE_INFO) - { - basic_block bb; - - FOR_ALL_BB (bb) - { - if (glat_start[bb->index]) - FREE_REG_SET (glat_start[bb->index]); - if (glat_end[bb->index]) - FREE_REG_SET (glat_end[bb->index]); - } - } -#endif - - free (glat_start); - free (glat_end); -} - -/* Remove INSN from the instruction stream. - INSN should have any dependencies. */ -static void -sched_remove_insn (rtx insn) -{ - 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. */ -static void -clear_priorities (rtx insn) -{ - rtx link; - - for (link = LOG_LINKS (insn); link; link = XEXP (link, 1)) - { - rtx pro; - - pro = XEXP (link, 0); - if (INSN_PRIORITY_KNOWN (pro)) - { - INSN_PRIORITY_KNOWN (pro) = 0; - clear_priorities (pro); - } - } -} - -/* Recompute priorities of instructions, whose priorities might have been - changed due to changes in INSN. */ -static void -calc_priorities (rtx insn) -{ - rtx link; - - for (link = LOG_LINKS (insn); link; link = XEXP (link, 1)) - { - rtx pro; - - pro = XEXP (link, 0); - if (!INSN_PRIORITY_KNOWN (pro)) - { - priority (pro); - calc_priorities (pro); - } - } -} - - -/* 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 (!INSN_DEPEND (insn)) - add_back_forw_dep (jump, insn, REG_DEP_ANTI, DEP_ANTI); - } - while (1); - gcc_assert (LOG_LINKS (jump)); -} - -/* 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 -extern void debug_spec_status (ds_t); - -/* Dump information about the dependence status S. */ -void -debug_spec_status (ds_t s) -{ - FILE *f = stderr; - - if (s & BEGIN_DATA) - fprintf (f, "BEGIN_DATA: %d; ", get_dep_weak (s, BEGIN_DATA)); - if (s & BE_IN_DATA) - fprintf (f, "BE_IN_DATA: %d; ", get_dep_weak (s, BE_IN_DATA)); - if (s & BEGIN_CONTROL) - fprintf (f, "BEGIN_CONTROL: %d; ", get_dep_weak (s, BEGIN_CONTROL)); - if (s & BE_IN_CONTROL) - fprintf (f, "BE_IN_CONTROL: %d; ", get_dep_weak (s, BE_IN_CONTROL)); - - if (s & HARD_DEP) - fprintf (f, "HARD_DEP; "); - - if (s & DEP_TRUE) - fprintf (f, "DEP_TRUE; "); - if (s & DEP_ANTI) - fprintf (f, "DEP_ANTI; "); - if (s & DEP_OUTPUT) - fprintf (f, "DEP_OUTPUT; "); - - fprintf (f, "\n"); -} - -/* Helper function for check_cfg. - Return nonzero, if edge vector pointed to by EL has edge with TYPE in - its flags. */ -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); -} - -/* Perform a few consistency checks of flags in different data structures. */ -static void -check_sched_flags (void) -{ - unsigned int f = current_sched_info->flags; - - if (flag_sched_stalled_insns) - gcc_assert (!(f & DO_SPECULATION)); - if (f & DO_SPECULATION) - gcc_assert (!flag_sched_stalled_insns - && (f & DETACH_LIFE_INFO) - && spec_info - && spec_info->mask); - if (f & DETACH_LIFE_INFO) - gcc_assert (f & USE_GLAT); -} - -/* Check global_live_at_{start, end} regsets. - If FATAL_P is TRUE, then abort execution at the first failure. - Otherwise, print diagnostics to STDERR (this mode is for calling - from debugger). */ -void -check_reg_live (bool fatal_p) -{ - basic_block bb; - - FOR_ALL_BB (bb) - { - int i; - - i = bb->index; - - if (glat_start[i]) - { - bool b = bitmap_equal_p (bb->il.rtl->global_live_at_start, - glat_start[i]); - - if (!b) - { - gcc_assert (!fatal_p); - - fprintf (stderr, ";; check_reg_live_at_start (%d) failed.\n", i); - } - } - - if (glat_end[i]) - { - bool b = bitmap_equal_p (bb->il.rtl->global_live_at_end, - glat_end[i]); - - if (!b) - { - gcc_assert (!fatal_p); - - fprintf (stderr, ";; check_reg_live_at_end (%d) failed.\n", i); - } - } - } -} -#endif /* ENABLE_CHECKING */ - -#endif /* INSN_SCHEDULING */ |