1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
3 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
4 Free Software Foundation, Inc.
5 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
6 and currently maintained by, Jim Wilson (wilson@cygnus.com)
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
24 /* Instruction scheduling pass. This file, along with sched-deps.c,
25 contains the generic parts. The actual entry point is found for
26 the normal instruction scheduling pass is found in sched-rgn.c.
28 We compute insn priorities based on data dependencies. Flow
29 analysis only creates a fraction of the data-dependencies we must
30 observe: namely, only those dependencies which the combiner can be
31 expected to use. For this pass, we must therefore create the
32 remaining dependencies we need to observe: register dependencies,
33 memory dependencies, dependencies to keep function calls in order,
34 and the dependence between a conditional branch and the setting of
35 condition codes are all dealt with here.
37 The scheduler first traverses the data flow graph, starting with
38 the last instruction, and proceeding to the first, assigning values
39 to insn_priority as it goes. This sorts the instructions
40 topologically by data dependence.
42 Once priorities have been established, we order the insns using
43 list scheduling. This works as follows: starting with a list of
44 all the ready insns, and sorted according to priority number, we
45 schedule the insn from the end of the list by placing its
46 predecessors in the list according to their priority order. We
47 consider this insn scheduled by setting the pointer to the "end" of
48 the list to point to the previous insn. When an insn has no
49 predecessors, we either queue it until sufficient time has elapsed
50 or add it to the ready list. As the instructions are scheduled or
51 when stalls are introduced, the queue advances and dumps insns into
52 the ready list. When all insns down to the lowest priority have
53 been scheduled, the critical path of the basic block has been made
54 as short as possible. The remaining insns are then scheduled in
57 The following list shows the order in which we want to break ties
58 among insns in the ready list:
60 1. choose insn with the longest path to end of bb, ties
62 2. choose insn with least contribution to register pressure,
64 3. prefer in-block upon interblock motion, ties broken by
65 4. prefer useful upon speculative motion, ties broken by
66 5. choose insn with largest control flow probability, ties
68 6. choose insn with the least dependences upon the previously
69 scheduled insn, or finally
70 7 choose the insn which has the most insns dependent on it.
71 8. choose insn with lowest UID.
73 Memory references complicate matters. Only if we can be certain
74 that memory references are not part of the data dependency graph
75 (via true, anti, or output dependence), can we move operations past
76 memory references. To first approximation, reads can be done
77 independently, while writes introduce dependencies. Better
78 approximations will yield fewer dependencies.
80 Before reload, an extended analysis of interblock data dependences
81 is required for interblock scheduling. This is performed in
82 compute_block_backward_dependences ().
84 Dependencies set up by memory references are treated in exactly the
85 same way as other dependencies, by using insn backward dependences
86 INSN_BACK_DEPS. INSN_BACK_DEPS are translated into forward dependences
87 INSN_FORW_DEPS the purpose of forward list scheduling.
89 Having optimized the critical path, we may have also unduly
90 extended the lifetimes of some registers. If an operation requires
91 that constants be loaded into registers, it is certainly desirable
92 to load those constants as early as necessary, but no earlier.
93 I.e., it will not do to load up a bunch of registers at the
94 beginning of a basic block only to use them at the end, if they
95 could be loaded later, since this may result in excessive register
98 Note that since branches are never in basic blocks, but only end
99 basic blocks, this pass will not move branches. But that is ok,
100 since we can use GNU's delayed branch scheduling pass to take care
103 Also note that no further optimizations based on algebraic
104 identities are performed, so this pass would be a good one to
105 perform instruction splitting, such as breaking up a multiply
106 instruction into shifts and adds where that is profitable.
108 Given the memory aliasing analysis that this pass should perform,
109 it should be possible to remove redundant stores to memory, and to
110 load values from registers instead of hitting memory.
112 Before reload, speculative insns are moved only if a 'proof' exists
113 that no exception will be caused by this, and if no live registers
114 exist that inhibit the motion (live registers constraints are not
115 represented by data dependence edges).
117 This pass must update information that subsequent passes expect to
118 be correct. Namely: reg_n_refs, reg_n_sets, reg_n_deaths,
119 reg_n_calls_crossed, and reg_live_length. Also, BB_HEAD, BB_END.
121 The information in the line number notes is carefully retained by
122 this pass. Notes that refer to the starting and ending of
123 exception regions are also carefully retained by this pass. All
124 other NOTE insns are grouped in their same relative order at the
125 beginning of basic blocks and regions that have been scheduled. */
129 #include "coretypes.h"
131 #include "diagnostic-core.h"
134 #include "hard-reg-set.h"
136 #include "function.h"
138 #include "insn-config.h"
139 #include "insn-attr.h"
142 #include "sched-int.h"
150 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
152 #ifdef INSN_SCHEDULING
154 /* issue_rate is the number of insns that can be scheduled in the same
155 machine cycle. It can be defined in the config/mach/mach.h file,
156 otherwise we set it to 1. */
160 /* sched-verbose controls the amount of debugging output the
161 scheduler prints. It is controlled by -fsched-verbose=N:
162 N>0 and no -DSR : the output is directed to stderr.
163 N>=10 will direct the printouts to stderr (regardless of -dSR).
165 N=2: bb's probabilities, detailed ready list info, unit/insn info.
166 N=3: rtl at abort point, control-flow, regions info.
167 N=5: dependences info. */
169 int sched_verbose = 0;
171 /* Debugging file. All printouts are sent to dump, which is always set,
172 either to stderr, or to the dump listing file (-dRS). */
173 FILE *sched_dump = 0;
175 /* This is a placeholder for the scheduler parameters common
176 to all schedulers. */
177 struct common_sched_info_def *common_sched_info;
179 #define INSN_TICK(INSN) (HID (INSN)->tick)
180 #define INTER_TICK(INSN) (HID (INSN)->inter_tick)
182 /* If INSN_TICK of an instruction is equal to INVALID_TICK,
183 then it should be recalculated from scratch. */
184 #define INVALID_TICK (-(max_insn_queue_index + 1))
185 /* The minimal value of the INSN_TICK of an instruction. */
186 #define MIN_TICK (-max_insn_queue_index)
188 /* List of important notes we must keep around. This is a pointer to the
189 last element in the list. */
192 static struct spec_info_def spec_info_var;
193 /* Description of the speculative part of the scheduling.
194 If NULL - no speculation. */
195 spec_info_t spec_info = NULL;
197 /* True, if recovery block was added during scheduling of current block.
198 Used to determine, if we need to fix INSN_TICKs. */
199 static bool haifa_recovery_bb_recently_added_p;
201 /* True, if recovery block was added during this scheduling pass.
202 Used to determine if we should have empty memory pools of dependencies
203 after finishing current region. */
204 bool haifa_recovery_bb_ever_added_p;
206 /* Counters of different types of speculative instructions. */
207 static int nr_begin_data, nr_be_in_data, nr_begin_control, nr_be_in_control;
209 /* Array used in {unlink, restore}_bb_notes. */
210 static rtx *bb_header = 0;
212 /* Basic block after which recovery blocks will be created. */
213 static basic_block before_recovery;
215 /* Basic block just before the EXIT_BLOCK and after recovery, if we have
217 basic_block after_recovery;
219 /* FALSE if we add bb to another region, so we don't need to initialize it. */
220 bool adding_bb_to_current_region_p = true;
224 /* An instruction is ready to be scheduled when all insns preceding it
225 have already been scheduled. It is important to ensure that all
226 insns which use its result will not be executed until its result
227 has been computed. An insn is maintained in one of four structures:
229 (P) the "Pending" set of insns which cannot be scheduled until
230 their dependencies have been satisfied.
231 (Q) the "Queued" set of insns that can be scheduled when sufficient
233 (R) the "Ready" list of unscheduled, uncommitted insns.
234 (S) the "Scheduled" list of insns.
236 Initially, all insns are either "Pending" or "Ready" depending on
237 whether their dependencies are satisfied.
239 Insns move from the "Ready" list to the "Scheduled" list as they
240 are committed to the schedule. As this occurs, the insns in the
241 "Pending" list have their dependencies satisfied and move to either
242 the "Ready" list or the "Queued" set depending on whether
243 sufficient time has passed to make them ready. As time passes,
244 insns move from the "Queued" set to the "Ready" list.
246 The "Pending" list (P) are the insns in the INSN_FORW_DEPS of the
247 unscheduled insns, i.e., those that are ready, queued, and pending.
248 The "Queued" set (Q) is implemented by the variable `insn_queue'.
249 The "Ready" list (R) is implemented by the variables `ready' and
251 The "Scheduled" list (S) is the new insn chain built by this pass.
253 The transition (R->S) is implemented in the scheduling loop in
254 `schedule_block' when the best insn to schedule is chosen.
255 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
256 insns move from the ready list to the scheduled list.
257 The transition (Q->R) is implemented in 'queue_to_insn' as time
258 passes or stalls are introduced. */
260 /* Implement a circular buffer to delay instructions until sufficient
261 time has passed. For the new pipeline description interface,
262 MAX_INSN_QUEUE_INDEX is a power of two minus one which is not less
263 than maximal time of instruction execution computed by genattr.c on
264 the base maximal time of functional unit reservations and getting a
265 result. This is the longest time an insn may be queued. */
267 static rtx *insn_queue;
268 static int q_ptr = 0;
269 static int q_size = 0;
270 #define NEXT_Q(X) (((X)+1) & max_insn_queue_index)
271 #define NEXT_Q_AFTER(X, C) (((X)+C) & max_insn_queue_index)
273 #define QUEUE_SCHEDULED (-3)
274 #define QUEUE_NOWHERE (-2)
275 #define QUEUE_READY (-1)
276 /* QUEUE_SCHEDULED - INSN is scheduled.
277 QUEUE_NOWHERE - INSN isn't scheduled yet and is neither in
279 QUEUE_READY - INSN is in ready list.
280 N >= 0 - INSN queued for X [where NEXT_Q_AFTER (q_ptr, X) == N] cycles. */
282 #define QUEUE_INDEX(INSN) (HID (INSN)->queue_index)
284 /* The following variable value refers for all current and future
285 reservations of the processor units. */
288 /* The following variable value is size of memory representing all
289 current and future reservations of the processor units. */
290 size_t dfa_state_size;
292 /* The following array is used to find the best insn from ready when
293 the automaton pipeline interface is used. */
294 char *ready_try = NULL;
296 /* The ready list. */
297 struct ready_list ready = {NULL, 0, 0, 0, 0};
299 /* The pointer to the ready list (to be removed). */
300 static struct ready_list *readyp = &ready;
302 /* Scheduling clock. */
303 static int clock_var;
305 /* This records the actual schedule. It is built up during the main phase
306 of schedule_block, and afterwards used to reorder the insns in the RTL. */
307 static VEC(rtx, heap) *scheduled_insns;
309 static int may_trap_exp (const_rtx, int);
311 /* Nonzero iff the address is comprised from at most 1 register. */
312 #define CONST_BASED_ADDRESS_P(x) \
314 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
315 || (GET_CODE (x) == LO_SUM)) \
316 && (CONSTANT_P (XEXP (x, 0)) \
317 || CONSTANT_P (XEXP (x, 1)))))
319 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
320 as found by analyzing insn's expression. */
323 static int haifa_luid_for_non_insn (rtx x);
325 /* Haifa version of sched_info hooks common to all headers. */
326 const struct common_sched_info_def haifa_common_sched_info =
328 NULL, /* fix_recovery_cfg */
329 NULL, /* add_block */
330 NULL, /* estimate_number_of_insns */
331 haifa_luid_for_non_insn, /* luid_for_non_insn */
332 SCHED_PASS_UNKNOWN /* sched_pass_id */
335 const struct sched_scan_info_def *sched_scan_info;
337 /* Mapping from instruction UID to its Logical UID. */
338 VEC (int, heap) *sched_luids = NULL;
340 /* Next LUID to assign to an instruction. */
341 int sched_max_luid = 1;
343 /* Haifa Instruction Data. */
344 VEC (haifa_insn_data_def, heap) *h_i_d = NULL;
346 void (* sched_init_only_bb) (basic_block, basic_block);
348 /* Split block function. Different schedulers might use different functions
349 to handle their internal data consistent. */
350 basic_block (* sched_split_block) (basic_block, rtx);
352 /* Create empty basic block after the specified block. */
353 basic_block (* sched_create_empty_bb) (basic_block);
356 may_trap_exp (const_rtx x, int is_store)
365 if (code == MEM && may_trap_p (x))
372 /* The insn uses memory: a volatile load. */
373 if (MEM_VOLATILE_P (x))
375 /* An exception-free load. */
378 /* A load with 1 base register, to be further checked. */
379 if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))
380 return PFREE_CANDIDATE;
381 /* No info on the load, to be further checked. */
382 return PRISKY_CANDIDATE;
387 int i, insn_class = TRAP_FREE;
389 /* Neither store nor load, check if it may cause a trap. */
392 /* Recursive step: walk the insn... */
393 fmt = GET_RTX_FORMAT (code);
394 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
398 int tmp_class = may_trap_exp (XEXP (x, i), is_store);
399 insn_class = WORST_CLASS (insn_class, tmp_class);
401 else if (fmt[i] == 'E')
404 for (j = 0; j < XVECLEN (x, i); j++)
406 int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);
407 insn_class = WORST_CLASS (insn_class, tmp_class);
408 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
412 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
419 /* Classifies rtx X of an insn for the purpose of verifying that X can be
420 executed speculatively (and consequently the insn can be moved
421 speculatively), by examining X, returning:
422 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
423 TRAP_FREE: non-load insn.
424 IFREE: load from a globally safe location.
425 IRISKY: volatile load.
426 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
427 being either PFREE or PRISKY. */
430 haifa_classify_rtx (const_rtx x)
432 int tmp_class = TRAP_FREE;
433 int insn_class = TRAP_FREE;
436 if (GET_CODE (x) == PARALLEL)
438 int i, len = XVECLEN (x, 0);
440 for (i = len - 1; i >= 0; i--)
442 tmp_class = haifa_classify_rtx (XVECEXP (x, 0, i));
443 insn_class = WORST_CLASS (insn_class, tmp_class);
444 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
454 /* Test if it is a 'store'. */
455 tmp_class = may_trap_exp (XEXP (x, 0), 1);
458 /* Test if it is a store. */
459 tmp_class = may_trap_exp (SET_DEST (x), 1);
460 if (tmp_class == TRAP_RISKY)
462 /* Test if it is a load. */
464 WORST_CLASS (tmp_class,
465 may_trap_exp (SET_SRC (x), 0));
468 tmp_class = haifa_classify_rtx (COND_EXEC_CODE (x));
469 if (tmp_class == TRAP_RISKY)
471 tmp_class = WORST_CLASS (tmp_class,
472 may_trap_exp (COND_EXEC_TEST (x), 0));
475 tmp_class = TRAP_RISKY;
479 insn_class = tmp_class;
486 haifa_classify_insn (const_rtx insn)
488 return haifa_classify_rtx (PATTERN (insn));
491 /* Forward declarations. */
493 static int priority (rtx);
494 static int rank_for_schedule (const void *, const void *);
495 static void swap_sort (rtx *, int);
496 static void queue_insn (rtx, int, const char *);
497 static int schedule_insn (rtx);
498 static void adjust_priority (rtx);
499 static void advance_one_cycle (void);
500 static void extend_h_i_d (void);
503 /* Notes handling mechanism:
504 =========================
505 Generally, NOTES are saved before scheduling and restored after scheduling.
506 The scheduler distinguishes between two types of notes:
508 (1) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
509 Before scheduling a region, a pointer to the note is added to the insn
510 that follows or precedes it. (This happens as part of the data dependence
511 computation). After scheduling an insn, the pointer contained in it is
512 used for regenerating the corresponding note (in reemit_notes).
514 (2) All other notes (e.g. INSN_DELETED): Before scheduling a block,
515 these notes are put in a list (in rm_other_notes() and
516 unlink_other_notes ()). After scheduling the block, these notes are
517 inserted at the beginning of the block (in schedule_block()). */
519 static void ready_add (struct ready_list *, rtx, bool);
520 static rtx ready_remove_first (struct ready_list *);
521 static rtx ready_remove_first_dispatch (struct ready_list *ready);
523 static void queue_to_ready (struct ready_list *);
524 static int early_queue_to_ready (state_t, struct ready_list *);
526 static void debug_ready_list (struct ready_list *);
528 /* The following functions are used to implement multi-pass scheduling
529 on the first cycle. */
530 static rtx ready_remove (struct ready_list *, int);
531 static void ready_remove_insn (rtx);
533 static void fix_inter_tick (rtx, rtx);
534 static int fix_tick_ready (rtx);
535 static void change_queue_index (rtx, int);
537 /* The following functions are used to implement scheduling of data/control
538 speculative instructions. */
540 static void extend_h_i_d (void);
541 static void init_h_i_d (rtx);
542 static void generate_recovery_code (rtx);
543 static void process_insn_forw_deps_be_in_spec (rtx, rtx, ds_t);
544 static void begin_speculative_block (rtx);
545 static void add_to_speculative_block (rtx);
546 static void init_before_recovery (basic_block *);
547 static void create_check_block_twin (rtx, bool);
548 static void fix_recovery_deps (basic_block);
549 static void haifa_change_pattern (rtx, rtx);
550 static void dump_new_block_header (int, basic_block, rtx, rtx);
551 static void restore_bb_notes (basic_block);
552 static void fix_jump_move (rtx);
553 static void move_block_after_check (rtx);
554 static void move_succs (VEC(edge,gc) **, basic_block);
555 static void sched_remove_insn (rtx);
556 static void clear_priorities (rtx, rtx_vec_t *);
557 static void calc_priorities (rtx_vec_t);
558 static void add_jump_dependencies (rtx, rtx);
559 #ifdef ENABLE_CHECKING
560 static int has_edge_p (VEC(edge,gc) *, int);
561 static void check_cfg (rtx, rtx);
564 #endif /* INSN_SCHEDULING */
566 /* Point to state used for the current scheduling pass. */
567 struct haifa_sched_info *current_sched_info;
569 #ifndef INSN_SCHEDULING
571 schedule_insns (void)
576 /* Do register pressure sensitive insn scheduling if the flag is set
578 bool sched_pressure_p;
580 /* Map regno -> its pressure class. The map defined only when
581 SCHED_PRESSURE_P is true. */
582 enum reg_class *sched_regno_pressure_class;
584 /* The current register pressure. Only elements corresponding pressure
585 classes are defined. */
586 static int curr_reg_pressure[N_REG_CLASSES];
588 /* Saved value of the previous array. */
589 static int saved_reg_pressure[N_REG_CLASSES];
591 /* Register living at given scheduling point. */
592 static bitmap curr_reg_live;
594 /* Saved value of the previous array. */
595 static bitmap saved_reg_live;
597 /* Registers mentioned in the current region. */
598 static bitmap region_ref_regs;
600 /* Initiate register pressure relative info for scheduling the current
601 region. Currently it is only clearing register mentioned in the
604 sched_init_region_reg_pressure_info (void)
606 bitmap_clear (region_ref_regs);
609 /* Update current register pressure related info after birth (if
610 BIRTH_P) or death of register REGNO. */
612 mark_regno_birth_or_death (int regno, bool birth_p)
614 enum reg_class pressure_class;
616 pressure_class = sched_regno_pressure_class[regno];
617 if (regno >= FIRST_PSEUDO_REGISTER)
619 if (pressure_class != NO_REGS)
623 bitmap_set_bit (curr_reg_live, regno);
624 curr_reg_pressure[pressure_class]
625 += (ira_reg_class_max_nregs
626 [pressure_class][PSEUDO_REGNO_MODE (regno)]);
630 bitmap_clear_bit (curr_reg_live, regno);
631 curr_reg_pressure[pressure_class]
632 -= (ira_reg_class_max_nregs
633 [pressure_class][PSEUDO_REGNO_MODE (regno)]);
637 else if (pressure_class != NO_REGS
638 && ! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
642 bitmap_set_bit (curr_reg_live, regno);
643 curr_reg_pressure[pressure_class]++;
647 bitmap_clear_bit (curr_reg_live, regno);
648 curr_reg_pressure[pressure_class]--;
653 /* Initiate current register pressure related info from living
654 registers given by LIVE. */
656 initiate_reg_pressure_info (bitmap live)
662 for (i = 0; i < ira_pressure_classes_num; i++)
663 curr_reg_pressure[ira_pressure_classes[i]] = 0;
664 bitmap_clear (curr_reg_live);
665 EXECUTE_IF_SET_IN_BITMAP (live, 0, j, bi)
666 if (current_nr_blocks == 1 || bitmap_bit_p (region_ref_regs, j))
667 mark_regno_birth_or_death (j, true);
670 /* Mark registers in X as mentioned in the current region. */
672 setup_ref_regs (rtx x)
675 const RTX_CODE code = GET_CODE (x);
681 if (HARD_REGISTER_NUM_P (regno))
682 bitmap_set_range (region_ref_regs, regno,
683 hard_regno_nregs[regno][GET_MODE (x)]);
685 bitmap_set_bit (region_ref_regs, REGNO (x));
688 fmt = GET_RTX_FORMAT (code);
689 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
691 setup_ref_regs (XEXP (x, i));
692 else if (fmt[i] == 'E')
694 for (j = 0; j < XVECLEN (x, i); j++)
695 setup_ref_regs (XVECEXP (x, i, j));
699 /* Initiate current register pressure related info at the start of
702 initiate_bb_reg_pressure_info (basic_block bb)
704 unsigned int i ATTRIBUTE_UNUSED;
707 if (current_nr_blocks > 1)
708 FOR_BB_INSNS (bb, insn)
709 if (NONDEBUG_INSN_P (insn))
710 setup_ref_regs (PATTERN (insn));
711 initiate_reg_pressure_info (df_get_live_in (bb));
712 #ifdef EH_RETURN_DATA_REGNO
713 if (bb_has_eh_pred (bb))
716 unsigned int regno = EH_RETURN_DATA_REGNO (i);
718 if (regno == INVALID_REGNUM)
720 if (! bitmap_bit_p (df_get_live_in (bb), regno))
721 mark_regno_birth_or_death (regno, true);
726 /* Save current register pressure related info. */
728 save_reg_pressure (void)
732 for (i = 0; i < ira_pressure_classes_num; i++)
733 saved_reg_pressure[ira_pressure_classes[i]]
734 = curr_reg_pressure[ira_pressure_classes[i]];
735 bitmap_copy (saved_reg_live, curr_reg_live);
738 /* Restore saved register pressure related info. */
740 restore_reg_pressure (void)
744 for (i = 0; i < ira_pressure_classes_num; i++)
745 curr_reg_pressure[ira_pressure_classes[i]]
746 = saved_reg_pressure[ira_pressure_classes[i]];
747 bitmap_copy (curr_reg_live, saved_reg_live);
750 /* Return TRUE if the register is dying after its USE. */
752 dying_use_p (struct reg_use_data *use)
754 struct reg_use_data *next;
756 for (next = use->next_regno_use; next != use; next = next->next_regno_use)
757 if (NONDEBUG_INSN_P (next->insn)
758 && QUEUE_INDEX (next->insn) != QUEUE_SCHEDULED)
763 /* Print info about the current register pressure and its excess for
764 each pressure class. */
766 print_curr_reg_pressure (void)
771 fprintf (sched_dump, ";;\t");
772 for (i = 0; i < ira_pressure_classes_num; i++)
774 cl = ira_pressure_classes[i];
775 gcc_assert (curr_reg_pressure[cl] >= 0);
776 fprintf (sched_dump, " %s:%d(%d)", reg_class_names[cl],
777 curr_reg_pressure[cl],
778 curr_reg_pressure[cl] - ira_available_class_regs[cl]);
780 fprintf (sched_dump, "\n");
783 /* Pointer to the last instruction scheduled. */
784 static rtx last_scheduled_insn;
786 /* Pointer to the last nondebug instruction scheduled within the
787 block, or the prev_head of the scheduling block. Used by
788 rank_for_schedule, so that insns independent of the last scheduled
789 insn will be preferred over dependent instructions. */
790 static rtx last_nondebug_scheduled_insn;
792 /* Pointer that iterates through the list of unscheduled insns if we
793 have a dbg_cnt enabled. It always points at an insn prior to the
794 first unscheduled one. */
795 static rtx nonscheduled_insns_begin;
797 /* Cached cost of the instruction. Use below function to get cost of the
798 insn. -1 here means that the field is not initialized. */
799 #define INSN_COST(INSN) (HID (INSN)->cost)
801 /* Compute cost of executing INSN.
802 This is the number of cycles between instruction issue and
803 instruction results. */
811 if (recog_memoized (insn) < 0)
814 cost = insn_default_latency (insn);
821 cost = INSN_COST (insn);
825 /* A USE insn, or something else we don't need to
826 understand. We can't pass these directly to
827 result_ready_cost or insn_default_latency because it will
828 trigger a fatal error for unrecognizable insns. */
829 if (recog_memoized (insn) < 0)
831 INSN_COST (insn) = 0;
836 cost = insn_default_latency (insn);
840 INSN_COST (insn) = cost;
847 /* Compute cost of dependence LINK.
848 This is the number of cycles between instruction issue and
850 ??? We also use this function to call recog_memoized on all insns. */
852 dep_cost_1 (dep_t link, dw_t dw)
854 rtx insn = DEP_PRO (link);
855 rtx used = DEP_CON (link);
858 /* A USE insn should never require the value used to be computed.
859 This allows the computation of a function's result and parameter
860 values to overlap the return and call. We don't care about the
861 dependence cost when only decreasing register pressure. */
862 if (recog_memoized (used) < 0)
865 recog_memoized (insn);
869 enum reg_note dep_type = DEP_TYPE (link);
871 cost = insn_cost (insn);
873 if (INSN_CODE (insn) >= 0)
875 if (dep_type == REG_DEP_ANTI)
877 else if (dep_type == REG_DEP_OUTPUT)
879 cost = (insn_default_latency (insn)
880 - insn_default_latency (used));
884 else if (bypass_p (insn))
885 cost = insn_latency (insn, used);
889 if (targetm.sched.adjust_cost_2)
890 cost = targetm.sched.adjust_cost_2 (used, (int) dep_type, insn, cost,
892 else if (targetm.sched.adjust_cost != NULL)
894 /* This variable is used for backward compatibility with the
896 rtx dep_cost_rtx_link = alloc_INSN_LIST (NULL_RTX, NULL_RTX);
898 /* Make it self-cycled, so that if some tries to walk over this
899 incomplete list he/she will be caught in an endless loop. */
900 XEXP (dep_cost_rtx_link, 1) = dep_cost_rtx_link;
902 /* Targets use only REG_NOTE_KIND of the link. */
903 PUT_REG_NOTE_KIND (dep_cost_rtx_link, DEP_TYPE (link));
905 cost = targetm.sched.adjust_cost (used, dep_cost_rtx_link,
908 free_INSN_LIST_node (dep_cost_rtx_link);
918 /* Compute cost of dependence LINK.
919 This is the number of cycles between instruction issue and
920 instruction results. */
922 dep_cost (dep_t link)
924 return dep_cost_1 (link, 0);
927 /* Use this sel-sched.c friendly function in reorder2 instead of increasing
928 INSN_PRIORITY explicitly. */
930 increase_insn_priority (rtx insn, int amount)
934 /* We're dealing with haifa-sched.c INSN_PRIORITY. */
935 if (INSN_PRIORITY_KNOWN (insn))
936 INSN_PRIORITY (insn) += amount;
940 /* In sel-sched.c INSN_PRIORITY is not kept up to date.
941 Use EXPR_PRIORITY instead. */
942 sel_add_to_insn_priority (insn, amount);
946 /* Return 'true' if DEP should be included in priority calculations. */
948 contributes_to_priority_p (dep_t dep)
950 if (DEBUG_INSN_P (DEP_CON (dep))
951 || DEBUG_INSN_P (DEP_PRO (dep)))
954 /* Critical path is meaningful in block boundaries only. */
955 if (!current_sched_info->contributes_to_priority (DEP_CON (dep),
959 /* If flag COUNT_SPEC_IN_CRITICAL_PATH is set,
960 then speculative instructions will less likely be
961 scheduled. That is because the priority of
962 their producers will increase, and, thus, the
963 producers will more likely be scheduled, thus,
964 resolving the dependence. */
965 if (sched_deps_info->generate_spec_deps
966 && !(spec_info->flags & COUNT_SPEC_IN_CRITICAL_PATH)
967 && (DEP_STATUS (dep) & SPECULATIVE))
973 /* Compute the number of nondebug forward deps of an insn. */
976 dep_list_size (rtx insn)
978 sd_iterator_def sd_it;
980 int dbgcount = 0, nodbgcount = 0;
982 if (!MAY_HAVE_DEBUG_INSNS)
983 return sd_lists_size (insn, SD_LIST_FORW);
985 FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
987 if (DEBUG_INSN_P (DEP_CON (dep)))
989 else if (!DEBUG_INSN_P (DEP_PRO (dep)))
993 gcc_assert (dbgcount + nodbgcount == sd_lists_size (insn, SD_LIST_FORW));
998 /* Compute the priority number for INSN. */
1002 if (! INSN_P (insn))
1005 /* We should not be interested in priority of an already scheduled insn. */
1006 gcc_assert (QUEUE_INDEX (insn) != QUEUE_SCHEDULED);
1008 if (!INSN_PRIORITY_KNOWN (insn))
1010 int this_priority = -1;
1012 if (dep_list_size (insn) == 0)
1013 /* ??? We should set INSN_PRIORITY to insn_cost when and insn has
1014 some forward deps but all of them are ignored by
1015 contributes_to_priority hook. At the moment we set priority of
1017 this_priority = insn_cost (insn);
1020 rtx prev_first, twin;
1023 /* For recovery check instructions we calculate priority slightly
1024 different than that of normal instructions. Instead of walking
1025 through INSN_FORW_DEPS (check) list, we walk through
1026 INSN_FORW_DEPS list of each instruction in the corresponding
1029 /* Selective scheduling does not define RECOVERY_BLOCK macro. */
1030 rec = sel_sched_p () ? NULL : RECOVERY_BLOCK (insn);
1031 if (!rec || rec == EXIT_BLOCK_PTR)
1033 prev_first = PREV_INSN (insn);
1038 prev_first = NEXT_INSN (BB_HEAD (rec));
1039 twin = PREV_INSN (BB_END (rec));
1044 sd_iterator_def sd_it;
1047 FOR_EACH_DEP (twin, SD_LIST_FORW, sd_it, dep)
1052 next = DEP_CON (dep);
1054 if (BLOCK_FOR_INSN (next) != rec)
1058 if (!contributes_to_priority_p (dep))
1062 cost = dep_cost (dep);
1065 struct _dep _dep1, *dep1 = &_dep1;
1067 init_dep (dep1, insn, next, REG_DEP_ANTI);
1069 cost = dep_cost (dep1);
1072 next_priority = cost + priority (next);
1074 if (next_priority > this_priority)
1075 this_priority = next_priority;
1079 twin = PREV_INSN (twin);
1081 while (twin != prev_first);
1084 if (this_priority < 0)
1086 gcc_assert (this_priority == -1);
1088 this_priority = insn_cost (insn);
1091 INSN_PRIORITY (insn) = this_priority;
1092 INSN_PRIORITY_STATUS (insn) = 1;
1095 return INSN_PRIORITY (insn);
1098 /* Macros and functions for keeping the priority queue sorted, and
1099 dealing with queuing and dequeuing of instructions. */
1101 #define SCHED_SORT(READY, N_READY) \
1102 do { if ((N_READY) == 2) \
1103 swap_sort (READY, N_READY); \
1104 else if ((N_READY) > 2) \
1105 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
1108 /* Setup info about the current register pressure impact of scheduling
1109 INSN at the current scheduling point. */
1111 setup_insn_reg_pressure_info (rtx insn)
1113 int i, change, before, after, hard_regno;
1114 int excess_cost_change;
1115 enum machine_mode mode;
1117 struct reg_pressure_data *pressure_info;
1118 int *max_reg_pressure;
1119 struct reg_use_data *use;
1120 static int death[N_REG_CLASSES];
1122 gcc_checking_assert (!DEBUG_INSN_P (insn));
1124 excess_cost_change = 0;
1125 for (i = 0; i < ira_pressure_classes_num; i++)
1126 death[ira_pressure_classes[i]] = 0;
1127 for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
1128 if (dying_use_p (use))
1130 cl = sched_regno_pressure_class[use->regno];
1131 if (use->regno < FIRST_PSEUDO_REGISTER)
1135 += ira_reg_class_max_nregs[cl][PSEUDO_REGNO_MODE (use->regno)];
1137 pressure_info = INSN_REG_PRESSURE (insn);
1138 max_reg_pressure = INSN_MAX_REG_PRESSURE (insn);
1139 gcc_assert (pressure_info != NULL && max_reg_pressure != NULL);
1140 for (i = 0; i < ira_pressure_classes_num; i++)
1142 cl = ira_pressure_classes[i];
1143 gcc_assert (curr_reg_pressure[cl] >= 0);
1144 change = (int) pressure_info[i].set_increase - death[cl];
1145 before = MAX (0, max_reg_pressure[i] - ira_available_class_regs[cl]);
1146 after = MAX (0, max_reg_pressure[i] + change
1147 - ira_available_class_regs[cl]);
1148 hard_regno = ira_class_hard_regs[cl][0];
1149 gcc_assert (hard_regno >= 0);
1150 mode = reg_raw_mode[hard_regno];
1151 excess_cost_change += ((after - before)
1152 * (ira_memory_move_cost[mode][cl][0]
1153 + ira_memory_move_cost[mode][cl][1]));
1155 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insn) = excess_cost_change;
1158 /* Returns a positive value if x is preferred; returns a negative value if
1159 y is preferred. Should never return 0, since that will make the sort
1163 rank_for_schedule (const void *x, const void *y)
1165 rtx tmp = *(const rtx *) y;
1166 rtx tmp2 = *(const rtx *) x;
1167 int tmp_class, tmp2_class;
1168 int val, priority_val, info_val;
1170 if (MAY_HAVE_DEBUG_INSNS)
1172 /* Schedule debug insns as early as possible. */
1173 if (DEBUG_INSN_P (tmp) && !DEBUG_INSN_P (tmp2))
1175 else if (DEBUG_INSN_P (tmp2))
1179 /* The insn in a schedule group should be issued the first. */
1180 if (flag_sched_group_heuristic &&
1181 SCHED_GROUP_P (tmp) != SCHED_GROUP_P (tmp2))
1182 return SCHED_GROUP_P (tmp2) ? 1 : -1;
1184 /* Make sure that priority of TMP and TMP2 are initialized. */
1185 gcc_assert (INSN_PRIORITY_KNOWN (tmp) && INSN_PRIORITY_KNOWN (tmp2));
1187 if (sched_pressure_p)
1191 /* Prefer insn whose scheduling results in the smallest register
1193 if ((diff = (INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp)
1194 + (INSN_TICK (tmp) > clock_var
1195 ? INSN_TICK (tmp) - clock_var : 0)
1196 - INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp2)
1197 - (INSN_TICK (tmp2) > clock_var
1198 ? INSN_TICK (tmp2) - clock_var : 0))) != 0)
1203 if (sched_pressure_p
1204 && (INSN_TICK (tmp2) > clock_var || INSN_TICK (tmp) > clock_var))
1206 if (INSN_TICK (tmp) <= clock_var)
1208 else if (INSN_TICK (tmp2) <= clock_var)
1211 return INSN_TICK (tmp) - INSN_TICK (tmp2);
1213 /* Prefer insn with higher priority. */
1214 priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
1216 if (flag_sched_critical_path_heuristic && priority_val)
1217 return priority_val;
1219 /* Prefer speculative insn with greater dependencies weakness. */
1220 if (flag_sched_spec_insn_heuristic && spec_info)
1226 ds1 = TODO_SPEC (tmp) & SPECULATIVE;
1228 dw1 = ds_weak (ds1);
1232 ds2 = TODO_SPEC (tmp2) & SPECULATIVE;
1234 dw2 = ds_weak (ds2);
1239 if (dw > (NO_DEP_WEAK / 8) || dw < -(NO_DEP_WEAK / 8))
1243 info_val = (*current_sched_info->rank) (tmp, tmp2);
1244 if(flag_sched_rank_heuristic && info_val)
1247 /* Compare insns based on their relation to the last scheduled
1249 if (flag_sched_last_insn_heuristic && last_nondebug_scheduled_insn)
1253 rtx last = last_nondebug_scheduled_insn;
1255 /* Classify the instructions into three classes:
1256 1) Data dependent on last schedule insn.
1257 2) Anti/Output dependent on last scheduled insn.
1258 3) Independent of last scheduled insn, or has latency of one.
1259 Choose the insn from the highest numbered class if different. */
1260 dep1 = sd_find_dep_between (last, tmp, true);
1262 if (dep1 == NULL || dep_cost (dep1) == 1)
1264 else if (/* Data dependence. */
1265 DEP_TYPE (dep1) == REG_DEP_TRUE)
1270 dep2 = sd_find_dep_between (last, tmp2, true);
1272 if (dep2 == NULL || dep_cost (dep2) == 1)
1274 else if (/* Data dependence. */
1275 DEP_TYPE (dep2) == REG_DEP_TRUE)
1280 if ((val = tmp2_class - tmp_class))
1284 /* Prefer the insn which has more later insns that depend on it.
1285 This gives the scheduler more freedom when scheduling later
1286 instructions at the expense of added register pressure. */
1288 val = (dep_list_size (tmp2) - dep_list_size (tmp));
1290 if (flag_sched_dep_count_heuristic && val != 0)
1293 /* If insns are equally good, sort by INSN_LUID (original insn order),
1294 so that we make the sort stable. This minimizes instruction movement,
1295 thus minimizing sched's effect on debugging and cross-jumping. */
1296 return INSN_LUID (tmp) - INSN_LUID (tmp2);
1299 /* Resort the array A in which only element at index N may be out of order. */
1301 HAIFA_INLINE static void
1302 swap_sort (rtx *a, int n)
1304 rtx insn = a[n - 1];
1307 while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0)
1315 /* Add INSN to the insn queue so that it can be executed at least
1316 N_CYCLES after the currently executing insn. Preserve insns
1317 chain for debugging purposes. REASON will be printed in debugging
1320 HAIFA_INLINE static void
1321 queue_insn (rtx insn, int n_cycles, const char *reason)
1323 int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
1324 rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]);
1326 gcc_assert (n_cycles <= max_insn_queue_index);
1327 gcc_assert (!DEBUG_INSN_P (insn));
1329 insn_queue[next_q] = link;
1332 if (sched_verbose >= 2)
1334 fprintf (sched_dump, ";;\t\tReady-->Q: insn %s: ",
1335 (*current_sched_info->print_insn) (insn, 0));
1337 fprintf (sched_dump, "queued for %d cycles (%s).\n", n_cycles, reason);
1340 QUEUE_INDEX (insn) = next_q;
1343 /* Remove INSN from queue. */
1345 queue_remove (rtx insn)
1347 gcc_assert (QUEUE_INDEX (insn) >= 0);
1348 remove_free_INSN_LIST_elem (insn, &insn_queue[QUEUE_INDEX (insn)]);
1350 QUEUE_INDEX (insn) = QUEUE_NOWHERE;
1353 /* Return a pointer to the bottom of the ready list, i.e. the insn
1354 with the lowest priority. */
1357 ready_lastpos (struct ready_list *ready)
1359 gcc_assert (ready->n_ready >= 1);
1360 return ready->vec + ready->first - ready->n_ready + 1;
1363 /* Add an element INSN to the ready list so that it ends up with the
1364 lowest/highest priority depending on FIRST_P. */
1366 HAIFA_INLINE static void
1367 ready_add (struct ready_list *ready, rtx insn, bool first_p)
1371 if (ready->first == ready->n_ready)
1373 memmove (ready->vec + ready->veclen - ready->n_ready,
1374 ready_lastpos (ready),
1375 ready->n_ready * sizeof (rtx));
1376 ready->first = ready->veclen - 1;
1378 ready->vec[ready->first - ready->n_ready] = insn;
1382 if (ready->first == ready->veclen - 1)
1385 /* ready_lastpos() fails when called with (ready->n_ready == 0). */
1386 memmove (ready->vec + ready->veclen - ready->n_ready - 1,
1387 ready_lastpos (ready),
1388 ready->n_ready * sizeof (rtx));
1389 ready->first = ready->veclen - 2;
1391 ready->vec[++(ready->first)] = insn;
1395 if (DEBUG_INSN_P (insn))
1398 gcc_assert (QUEUE_INDEX (insn) != QUEUE_READY);
1399 QUEUE_INDEX (insn) = QUEUE_READY;
1402 /* Remove the element with the highest priority from the ready list and
1405 HAIFA_INLINE static rtx
1406 ready_remove_first (struct ready_list *ready)
1410 gcc_assert (ready->n_ready);
1411 t = ready->vec[ready->first--];
1413 if (DEBUG_INSN_P (t))
1415 /* If the queue becomes empty, reset it. */
1416 if (ready->n_ready == 0)
1417 ready->first = ready->veclen - 1;
1419 gcc_assert (QUEUE_INDEX (t) == QUEUE_READY);
1420 QUEUE_INDEX (t) = QUEUE_NOWHERE;
1425 /* The following code implements multi-pass scheduling for the first
1426 cycle. In other words, we will try to choose ready insn which
1427 permits to start maximum number of insns on the same cycle. */
1429 /* Return a pointer to the element INDEX from the ready. INDEX for
1430 insn with the highest priority is 0, and the lowest priority has
1434 ready_element (struct ready_list *ready, int index)
1436 gcc_assert (ready->n_ready && index < ready->n_ready);
1438 return ready->vec[ready->first - index];
1441 /* Remove the element INDEX from the ready list and return it. INDEX
1442 for insn with the highest priority is 0, and the lowest priority
1445 HAIFA_INLINE static rtx
1446 ready_remove (struct ready_list *ready, int index)
1452 return ready_remove_first (ready);
1453 gcc_assert (ready->n_ready && index < ready->n_ready);
1454 t = ready->vec[ready->first - index];
1456 if (DEBUG_INSN_P (t))
1458 for (i = index; i < ready->n_ready; i++)
1459 ready->vec[ready->first - i] = ready->vec[ready->first - i - 1];
1460 QUEUE_INDEX (t) = QUEUE_NOWHERE;
1464 /* Remove INSN from the ready list. */
1466 ready_remove_insn (rtx insn)
1470 for (i = 0; i < readyp->n_ready; i++)
1471 if (ready_element (readyp, i) == insn)
1473 ready_remove (readyp, i);
1479 /* Sort the ready list READY by ascending priority, using the SCHED_SORT
1483 ready_sort (struct ready_list *ready)
1486 rtx *first = ready_lastpos (ready);
1488 if (sched_pressure_p)
1490 for (i = 0; i < ready->n_ready; i++)
1491 if (!DEBUG_INSN_P (first[i]))
1492 setup_insn_reg_pressure_info (first[i]);
1494 SCHED_SORT (first, ready->n_ready);
1497 /* PREV is an insn that is ready to execute. Adjust its priority if that
1498 will help shorten or lengthen register lifetimes as appropriate. Also
1499 provide a hook for the target to tweak itself. */
1501 HAIFA_INLINE static void
1502 adjust_priority (rtx prev)
1504 /* ??? There used to be code here to try and estimate how an insn
1505 affected register lifetimes, but it did it by looking at REG_DEAD
1506 notes, which we removed in schedule_region. Nor did it try to
1507 take into account register pressure or anything useful like that.
1509 Revisit when we have a machine model to work with and not before. */
1511 if (targetm.sched.adjust_priority)
1512 INSN_PRIORITY (prev) =
1513 targetm.sched.adjust_priority (prev, INSN_PRIORITY (prev));
1516 /* Advance DFA state STATE on one cycle. */
1518 advance_state (state_t state)
1520 if (targetm.sched.dfa_pre_advance_cycle)
1521 targetm.sched.dfa_pre_advance_cycle ();
1523 if (targetm.sched.dfa_pre_cycle_insn)
1524 state_transition (state,
1525 targetm.sched.dfa_pre_cycle_insn ());
1527 state_transition (state, NULL);
1529 if (targetm.sched.dfa_post_cycle_insn)
1530 state_transition (state,
1531 targetm.sched.dfa_post_cycle_insn ());
1533 if (targetm.sched.dfa_post_advance_cycle)
1534 targetm.sched.dfa_post_advance_cycle ();
1537 /* Advance time on one cycle. */
1538 HAIFA_INLINE static void
1539 advance_one_cycle (void)
1541 advance_state (curr_state);
1542 if (sched_verbose >= 6)
1543 fprintf (sched_dump, ";;\tAdvanced a state.\n");
1546 /* Clock at which the previous instruction was issued. */
1547 static int last_clock_var;
1549 /* Update register pressure after scheduling INSN. */
1551 update_register_pressure (rtx insn)
1553 struct reg_use_data *use;
1554 struct reg_set_data *set;
1556 gcc_checking_assert (!DEBUG_INSN_P (insn));
1558 for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
1559 if (dying_use_p (use) && bitmap_bit_p (curr_reg_live, use->regno))
1560 mark_regno_birth_or_death (use->regno, false);
1561 for (set = INSN_REG_SET_LIST (insn); set != NULL; set = set->next_insn_set)
1562 mark_regno_birth_or_death (set->regno, true);
1565 /* Set up or update (if UPDATE_P) max register pressure (see its
1566 meaning in sched-int.h::_haifa_insn_data) for all current BB insns
1567 after insn AFTER. */
1569 setup_insn_max_reg_pressure (rtx after, bool update_p)
1574 static int max_reg_pressure[N_REG_CLASSES];
1576 save_reg_pressure ();
1577 for (i = 0; i < ira_pressure_classes_num; i++)
1578 max_reg_pressure[ira_pressure_classes[i]]
1579 = curr_reg_pressure[ira_pressure_classes[i]];
1580 for (insn = NEXT_INSN (after);
1581 insn != NULL_RTX && ! BARRIER_P (insn)
1582 && BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (after);
1583 insn = NEXT_INSN (insn))
1584 if (NONDEBUG_INSN_P (insn))
1587 for (i = 0; i < ira_pressure_classes_num; i++)
1589 p = max_reg_pressure[ira_pressure_classes[i]];
1590 if (INSN_MAX_REG_PRESSURE (insn)[i] != p)
1593 INSN_MAX_REG_PRESSURE (insn)[i]
1594 = max_reg_pressure[ira_pressure_classes[i]];
1597 if (update_p && eq_p)
1599 update_register_pressure (insn);
1600 for (i = 0; i < ira_pressure_classes_num; i++)
1601 if (max_reg_pressure[ira_pressure_classes[i]]
1602 < curr_reg_pressure[ira_pressure_classes[i]])
1603 max_reg_pressure[ira_pressure_classes[i]]
1604 = curr_reg_pressure[ira_pressure_classes[i]];
1606 restore_reg_pressure ();
1609 /* Update the current register pressure after scheduling INSN. Update
1610 also max register pressure for unscheduled insns of the current
1613 update_reg_and_insn_max_reg_pressure (rtx insn)
1616 int before[N_REG_CLASSES];
1618 for (i = 0; i < ira_pressure_classes_num; i++)
1619 before[i] = curr_reg_pressure[ira_pressure_classes[i]];
1620 update_register_pressure (insn);
1621 for (i = 0; i < ira_pressure_classes_num; i++)
1622 if (curr_reg_pressure[ira_pressure_classes[i]] != before[i])
1624 if (i < ira_pressure_classes_num)
1625 setup_insn_max_reg_pressure (insn, true);
1628 /* Set up register pressure at the beginning of basic block BB whose
1629 insns starting after insn AFTER. Set up also max register pressure
1630 for all insns of the basic block. */
1632 sched_setup_bb_reg_pressure_info (basic_block bb, rtx after)
1634 gcc_assert (sched_pressure_p);
1635 initiate_bb_reg_pressure_info (bb);
1636 setup_insn_max_reg_pressure (after, false);
1639 /* INSN is the "currently executing insn". Launch each insn which was
1640 waiting on INSN. READY is the ready list which contains the insns
1641 that are ready to fire. CLOCK is the current cycle. The function
1642 returns necessary cycle advance after issuing the insn (it is not
1643 zero for insns in a schedule group). */
1646 schedule_insn (rtx insn)
1648 sd_iterator_def sd_it;
1653 if (sched_verbose >= 1)
1655 struct reg_pressure_data *pressure_info;
1658 print_insn (buf, insn, 0);
1660 fprintf (sched_dump, ";;\t%3i--> %-40s:", clock_var, buf);
1662 if (recog_memoized (insn) < 0)
1663 fprintf (sched_dump, "nothing");
1665 print_reservation (sched_dump, insn);
1666 pressure_info = INSN_REG_PRESSURE (insn);
1667 if (pressure_info != NULL)
1669 fputc (':', sched_dump);
1670 for (i = 0; i < ira_pressure_classes_num; i++)
1671 fprintf (sched_dump, "%s%+d(%d)",
1672 reg_class_names[ira_pressure_classes[i]],
1673 pressure_info[i].set_increase, pressure_info[i].change);
1675 fputc ('\n', sched_dump);
1678 if (sched_pressure_p && !DEBUG_INSN_P (insn))
1679 update_reg_and_insn_max_reg_pressure (insn);
1681 /* Scheduling instruction should have all its dependencies resolved and
1682 should have been removed from the ready list. */
1683 gcc_assert (sd_lists_empty_p (insn, SD_LIST_BACK));
1685 /* Reset debug insns invalidated by moving this insn. */
1686 if (MAY_HAVE_DEBUG_INSNS && !DEBUG_INSN_P (insn))
1687 for (sd_it = sd_iterator_start (insn, SD_LIST_BACK);
1688 sd_iterator_cond (&sd_it, &dep);)
1690 rtx dbg = DEP_PRO (dep);
1691 struct reg_use_data *use, *next;
1693 gcc_assert (DEBUG_INSN_P (dbg));
1695 if (sched_verbose >= 6)
1696 fprintf (sched_dump, ";;\t\tresetting: debug insn %d\n",
1699 /* ??? Rather than resetting the debug insn, we might be able
1700 to emit a debug temp before the just-scheduled insn, but
1701 this would involve checking that the expression at the
1702 point of the debug insn is equivalent to the expression
1703 before the just-scheduled insn. They might not be: the
1704 expression in the debug insn may depend on other insns not
1705 yet scheduled that set MEMs, REGs or even other debug
1706 insns. It's not clear that attempting to preserve debug
1707 information in these cases is worth the effort, given how
1708 uncommon these resets are and the likelihood that the debug
1709 temps introduced won't survive the schedule change. */
1710 INSN_VAR_LOCATION_LOC (dbg) = gen_rtx_UNKNOWN_VAR_LOC ();
1711 df_insn_rescan (dbg);
1713 /* Unknown location doesn't use any registers. */
1714 for (use = INSN_REG_USE_LIST (dbg); use != NULL; use = next)
1716 struct reg_use_data *prev = use;
1718 /* Remove use from the cyclic next_regno_use chain first. */
1719 while (prev->next_regno_use != use)
1720 prev = prev->next_regno_use;
1721 prev->next_regno_use = use->next_regno_use;
1722 next = use->next_insn_use;
1725 INSN_REG_USE_LIST (dbg) = NULL;
1727 /* We delete rather than resolve these deps, otherwise we
1728 crash in sched_free_deps(), because forward deps are
1729 expected to be released before backward deps. */
1730 sd_delete_dep (sd_it);
1733 gcc_assert (QUEUE_INDEX (insn) == QUEUE_NOWHERE);
1734 QUEUE_INDEX (insn) = QUEUE_SCHEDULED;
1736 gcc_assert (INSN_TICK (insn) >= MIN_TICK);
1737 if (INSN_TICK (insn) > clock_var)
1738 /* INSN has been prematurely moved from the queue to the ready list.
1739 This is possible only if following flag is set. */
1740 gcc_assert (flag_sched_stalled_insns);
1742 /* ??? Probably, if INSN is scheduled prematurely, we should leave
1743 INSN_TICK untouched. This is a machine-dependent issue, actually. */
1744 INSN_TICK (insn) = clock_var;
1746 /* Update dependent instructions. */
1747 for (sd_it = sd_iterator_start (insn, SD_LIST_FORW);
1748 sd_iterator_cond (&sd_it, &dep);)
1750 rtx next = DEP_CON (dep);
1752 /* Resolve the dependence between INSN and NEXT.
1753 sd_resolve_dep () moves current dep to another list thus
1754 advancing the iterator. */
1755 sd_resolve_dep (sd_it);
1757 /* Don't bother trying to mark next as ready if insn is a debug
1758 insn. If insn is the last hard dependency, it will have
1759 already been discounted. */
1760 if (DEBUG_INSN_P (insn) && !DEBUG_INSN_P (next))
1763 if (!IS_SPECULATION_BRANCHY_CHECK_P (insn))
1767 effective_cost = try_ready (next);
1769 if (effective_cost >= 0
1770 && SCHED_GROUP_P (next)
1771 && advance < effective_cost)
1772 advance = effective_cost;
1775 /* Check always has only one forward dependence (to the first insn in
1776 the recovery block), therefore, this will be executed only once. */
1778 gcc_assert (sd_lists_empty_p (insn, SD_LIST_FORW));
1779 fix_recovery_deps (RECOVERY_BLOCK (insn));
1783 /* This is the place where scheduler doesn't *basically* need backward and
1784 forward dependencies for INSN anymore. Nevertheless they are used in
1785 heuristics in rank_for_schedule (), early_queue_to_ready () and in
1786 some targets (e.g. rs6000). Thus the earliest place where we *can*
1787 remove dependencies is after targetm.sched.finish () call in
1788 schedule_block (). But, on the other side, the safest place to remove
1789 dependencies is when we are finishing scheduling entire region. As we
1790 don't generate [many] dependencies during scheduling itself, we won't
1791 need memory until beginning of next region.
1792 Bottom line: Dependencies are removed for all insns in the end of
1793 scheduling the region. */
1795 /* Annotate the instruction with issue information -- TImode
1796 indicates that the instruction is expected not to be able
1797 to issue on the same cycle as the previous insn. A machine
1798 may use this information to decide how the instruction should
1801 && GET_CODE (PATTERN (insn)) != USE
1802 && GET_CODE (PATTERN (insn)) != CLOBBER
1803 && !DEBUG_INSN_P (insn))
1805 if (reload_completed)
1806 PUT_MODE (insn, clock_var > last_clock_var ? TImode : VOIDmode);
1807 last_clock_var = clock_var;
1813 /* Functions for handling of notes. */
1815 /* Add note list that ends on FROM_END to the end of TO_ENDP. */
1817 concat_note_lists (rtx from_end, rtx *to_endp)
1821 /* It's easy when have nothing to concat. */
1822 if (from_end == NULL)
1825 /* It's also easy when destination is empty. */
1826 if (*to_endp == NULL)
1828 *to_endp = from_end;
1832 from_start = from_end;
1833 while (PREV_INSN (from_start) != NULL)
1834 from_start = PREV_INSN (from_start);
1836 PREV_INSN (from_start) = *to_endp;
1837 NEXT_INSN (*to_endp) = from_start;
1838 *to_endp = from_end;
1841 /* Delete notes between HEAD and TAIL and put them in the chain
1842 of notes ended by NOTE_LIST. */
1844 remove_notes (rtx head, rtx tail)
1846 rtx next_tail, insn, next;
1849 if (head == tail && !INSN_P (head))
1852 next_tail = NEXT_INSN (tail);
1853 for (insn = head; insn != next_tail; insn = next)
1855 next = NEXT_INSN (insn);
1859 switch (NOTE_KIND (insn))
1861 case NOTE_INSN_BASIC_BLOCK:
1864 case NOTE_INSN_EPILOGUE_BEG:
1868 add_reg_note (next, REG_SAVE_NOTE,
1869 GEN_INT (NOTE_INSN_EPILOGUE_BEG));
1877 /* Add the note to list that ends at NOTE_LIST. */
1878 PREV_INSN (insn) = note_list;
1879 NEXT_INSN (insn) = NULL_RTX;
1881 NEXT_INSN (note_list) = insn;
1886 gcc_assert ((sel_sched_p () || insn != tail) && insn != head);
1891 /* Return the head and tail pointers of ebb starting at BEG and ending
1894 get_ebb_head_tail (basic_block beg, basic_block end, rtx *headp, rtx *tailp)
1896 rtx beg_head = BB_HEAD (beg);
1897 rtx beg_tail = BB_END (beg);
1898 rtx end_head = BB_HEAD (end);
1899 rtx end_tail = BB_END (end);
1901 /* Don't include any notes or labels at the beginning of the BEG
1902 basic block, or notes at the end of the END basic blocks. */
1904 if (LABEL_P (beg_head))
1905 beg_head = NEXT_INSN (beg_head);
1907 while (beg_head != beg_tail)
1908 if (NOTE_P (beg_head))
1909 beg_head = NEXT_INSN (beg_head);
1910 else if (DEBUG_INSN_P (beg_head))
1914 for (note = NEXT_INSN (beg_head);
1918 next = NEXT_INSN (note);
1921 if (sched_verbose >= 9)
1922 fprintf (sched_dump, "reorder %i\n", INSN_UID (note));
1924 reorder_insns_nobb (note, note, PREV_INSN (beg_head));
1926 if (BLOCK_FOR_INSN (note) != beg)
1927 df_insn_change_bb (note, beg);
1929 else if (!DEBUG_INSN_P (note))
1941 end_head = beg_head;
1942 else if (LABEL_P (end_head))
1943 end_head = NEXT_INSN (end_head);
1945 while (end_head != end_tail)
1946 if (NOTE_P (end_tail))
1947 end_tail = PREV_INSN (end_tail);
1948 else if (DEBUG_INSN_P (end_tail))
1952 for (note = PREV_INSN (end_tail);
1956 prev = PREV_INSN (note);
1959 if (sched_verbose >= 9)
1960 fprintf (sched_dump, "reorder %i\n", INSN_UID (note));
1962 reorder_insns_nobb (note, note, end_tail);
1964 if (end_tail == BB_END (end))
1965 BB_END (end) = note;
1967 if (BLOCK_FOR_INSN (note) != end)
1968 df_insn_change_bb (note, end);
1970 else if (!DEBUG_INSN_P (note))
1982 /* Return nonzero if there are no real insns in the range [ HEAD, TAIL ]. */
1985 no_real_insns_p (const_rtx head, const_rtx tail)
1987 while (head != NEXT_INSN (tail))
1989 if (!NOTE_P (head) && !LABEL_P (head))
1991 head = NEXT_INSN (head);
1996 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
1997 previously found among the insns. Insert them just before HEAD. */
1999 restore_other_notes (rtx head, basic_block head_bb)
2003 rtx note_head = note_list;
2006 head_bb = BLOCK_FOR_INSN (head);
2008 head = NEXT_INSN (bb_note (head_bb));
2010 while (PREV_INSN (note_head))
2012 set_block_for_insn (note_head, head_bb);
2013 note_head = PREV_INSN (note_head);
2015 /* In the above cycle we've missed this note. */
2016 set_block_for_insn (note_head, head_bb);
2018 PREV_INSN (note_head) = PREV_INSN (head);
2019 NEXT_INSN (PREV_INSN (head)) = note_head;
2020 PREV_INSN (head) = note_list;
2021 NEXT_INSN (note_list) = head;
2023 if (BLOCK_FOR_INSN (head) != head_bb)
2024 BB_END (head_bb) = note_list;
2032 /* Move insns that became ready to fire from queue to ready list. */
2035 queue_to_ready (struct ready_list *ready)
2041 q_ptr = NEXT_Q (q_ptr);
2043 if (dbg_cnt (sched_insn) == false)
2045 /* If debug counter is activated do not requeue the first
2046 nonscheduled insn. */
2047 skip_insn = nonscheduled_insns_begin;
2050 skip_insn = next_nonnote_nondebug_insn (skip_insn);
2052 while (QUEUE_INDEX (skip_insn) == QUEUE_SCHEDULED);
2055 skip_insn = NULL_RTX;
2057 /* Add all pending insns that can be scheduled without stalls to the
2059 for (link = insn_queue[q_ptr]; link; link = XEXP (link, 1))
2061 insn = XEXP (link, 0);
2064 if (sched_verbose >= 2)
2065 fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
2066 (*current_sched_info->print_insn) (insn, 0));
2068 /* If the ready list is full, delay the insn for 1 cycle.
2069 See the comment in schedule_block for the rationale. */
2070 if (!reload_completed
2071 && ready->n_ready - ready->n_debug > MAX_SCHED_READY_INSNS
2072 && !SCHED_GROUP_P (insn)
2073 && insn != skip_insn)
2074 queue_insn (insn, 1, "ready full");
2077 ready_add (ready, insn, false);
2078 if (sched_verbose >= 2)
2079 fprintf (sched_dump, "moving to ready without stalls\n");
2082 free_INSN_LIST_list (&insn_queue[q_ptr]);
2084 /* If there are no ready insns, stall until one is ready and add all
2085 of the pending insns at that point to the ready list. */
2086 if (ready->n_ready == 0)
2090 for (stalls = 1; stalls <= max_insn_queue_index; stalls++)
2092 if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
2094 for (; link; link = XEXP (link, 1))
2096 insn = XEXP (link, 0);
2099 if (sched_verbose >= 2)
2100 fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
2101 (*current_sched_info->print_insn) (insn, 0));
2103 ready_add (ready, insn, false);
2104 if (sched_verbose >= 2)
2105 fprintf (sched_dump, "moving to ready with %d stalls\n", stalls);
2107 free_INSN_LIST_list (&insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]);
2109 advance_one_cycle ();
2114 advance_one_cycle ();
2117 q_ptr = NEXT_Q_AFTER (q_ptr, stalls);
2118 clock_var += stalls;
2122 /* Used by early_queue_to_ready. Determines whether it is "ok" to
2123 prematurely move INSN from the queue to the ready list. Currently,
2124 if a target defines the hook 'is_costly_dependence', this function
2125 uses the hook to check whether there exist any dependences which are
2126 considered costly by the target, between INSN and other insns that
2127 have already been scheduled. Dependences are checked up to Y cycles
2128 back, with default Y=1; The flag -fsched-stalled-insns-dep=Y allows
2129 controlling this value.
2130 (Other considerations could be taken into account instead (or in
2131 addition) depending on user flags and target hooks. */
2134 ok_for_early_queue_removal (rtx insn)
2136 if (targetm.sched.is_costly_dependence)
2140 int i = VEC_length (rtx, scheduled_insns);
2141 for (n_cycles = flag_sched_stalled_insns_dep; n_cycles; n_cycles--)
2147 prev_insn = VEC_index (rtx, scheduled_insns, i);
2149 if (!NOTE_P (prev_insn))
2153 dep = sd_find_dep_between (prev_insn, insn, true);
2157 cost = dep_cost (dep);
2159 if (targetm.sched.is_costly_dependence (dep, cost,
2160 flag_sched_stalled_insns_dep - n_cycles))
2165 if (GET_MODE (prev_insn) == TImode) /* end of dispatch group */
2178 /* Remove insns from the queue, before they become "ready" with respect
2179 to FU latency considerations. */
2182 early_queue_to_ready (state_t state, struct ready_list *ready)
2190 state_t temp_state = alloca (dfa_state_size);
2192 int insns_removed = 0;
2195 Flag '-fsched-stalled-insns=X' determines the aggressiveness of this
2198 X == 0: There is no limit on how many queued insns can be removed
2199 prematurely. (flag_sched_stalled_insns = -1).
2201 X >= 1: Only X queued insns can be removed prematurely in each
2202 invocation. (flag_sched_stalled_insns = X).
2204 Otherwise: Early queue removal is disabled.
2205 (flag_sched_stalled_insns = 0)
2208 if (! flag_sched_stalled_insns)
2211 for (stalls = 0; stalls <= max_insn_queue_index; stalls++)
2213 if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
2215 if (sched_verbose > 6)
2216 fprintf (sched_dump, ";; look at index %d + %d\n", q_ptr, stalls);
2221 next_link = XEXP (link, 1);
2222 insn = XEXP (link, 0);
2223 if (insn && sched_verbose > 6)
2224 print_rtl_single (sched_dump, insn);
2226 memcpy (temp_state, state, dfa_state_size);
2227 if (recog_memoized (insn) < 0)
2228 /* non-negative to indicate that it's not ready
2229 to avoid infinite Q->R->Q->R... */
2232 cost = state_transition (temp_state, insn);
2234 if (sched_verbose >= 6)
2235 fprintf (sched_dump, "transition cost = %d\n", cost);
2237 move_to_ready = false;
2240 move_to_ready = ok_for_early_queue_removal (insn);
2241 if (move_to_ready == true)
2243 /* move from Q to R */
2245 ready_add (ready, insn, false);
2248 XEXP (prev_link, 1) = next_link;
2250 insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = next_link;
2252 free_INSN_LIST_node (link);
2254 if (sched_verbose >= 2)
2255 fprintf (sched_dump, ";;\t\tEarly Q-->Ready: insn %s\n",
2256 (*current_sched_info->print_insn) (insn, 0));
2259 if (insns_removed == flag_sched_stalled_insns)
2260 /* Remove no more than flag_sched_stalled_insns insns
2261 from Q at a time. */
2262 return insns_removed;
2266 if (move_to_ready == false)
2273 } /* for stalls.. */
2275 return insns_removed;
2279 /* Print the ready list for debugging purposes. Callable from debugger. */
2282 debug_ready_list (struct ready_list *ready)
2287 if (ready->n_ready == 0)
2289 fprintf (sched_dump, "\n");
2293 p = ready_lastpos (ready);
2294 for (i = 0; i < ready->n_ready; i++)
2296 fprintf (sched_dump, " %s:%d",
2297 (*current_sched_info->print_insn) (p[i], 0),
2299 if (sched_pressure_p)
2300 fprintf (sched_dump, "(cost=%d",
2301 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (p[i]));
2302 if (INSN_TICK (p[i]) > clock_var)
2303 fprintf (sched_dump, ":delay=%d", INSN_TICK (p[i]) - clock_var);
2304 if (sched_pressure_p)
2305 fprintf (sched_dump, ")");
2307 fprintf (sched_dump, "\n");
2310 /* Search INSN for REG_SAVE_NOTE notes and convert them back into insn
2311 NOTEs. This is used for NOTE_INSN_EPILOGUE_BEG, so that sched-ebb
2312 replaces the epilogue note in the correct basic block. */
2314 reemit_notes (rtx insn)
2316 rtx note, last = insn;
2318 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
2320 if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
2322 enum insn_note note_type = (enum insn_note) INTVAL (XEXP (note, 0));
2324 last = emit_note_before (note_type, last);
2325 remove_note (insn, note);
2330 /* Move INSN. Reemit notes if needed. Update CFG, if needed. */
2332 move_insn (rtx insn, rtx last, rtx nt)
2334 if (PREV_INSN (insn) != last)
2340 bb = BLOCK_FOR_INSN (insn);
2342 /* BB_HEAD is either LABEL or NOTE. */
2343 gcc_assert (BB_HEAD (bb) != insn);
2345 if (BB_END (bb) == insn)
2346 /* If this is last instruction in BB, move end marker one
2349 /* Jumps are always placed at the end of basic block. */
2350 jump_p = control_flow_insn_p (insn);
2353 || ((common_sched_info->sched_pass_id == SCHED_RGN_PASS)
2354 && IS_SPECULATION_BRANCHY_CHECK_P (insn))
2355 || (common_sched_info->sched_pass_id
2356 == SCHED_EBB_PASS));
2358 gcc_assert (BLOCK_FOR_INSN (PREV_INSN (insn)) == bb);
2360 BB_END (bb) = PREV_INSN (insn);
2363 gcc_assert (BB_END (bb) != last);
2366 /* We move the block note along with jump. */
2370 note = NEXT_INSN (insn);
2371 while (NOTE_NOT_BB_P (note) && note != nt)
2372 note = NEXT_INSN (note);
2376 || BARRIER_P (note)))
2377 note = NEXT_INSN (note);
2379 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
2384 NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (note);
2385 PREV_INSN (NEXT_INSN (note)) = PREV_INSN (insn);
2387 NEXT_INSN (note) = NEXT_INSN (last);
2388 PREV_INSN (NEXT_INSN (last)) = note;
2390 NEXT_INSN (last) = insn;
2391 PREV_INSN (insn) = last;
2393 bb = BLOCK_FOR_INSN (last);
2397 fix_jump_move (insn);
2399 if (BLOCK_FOR_INSN (insn) != bb)
2400 move_block_after_check (insn);
2402 gcc_assert (BB_END (bb) == last);
2405 df_insn_change_bb (insn, bb);
2407 /* Update BB_END, if needed. */
2408 if (BB_END (bb) == last)
2412 SCHED_GROUP_P (insn) = 0;
2415 /* Return true if scheduling INSN will finish current clock cycle. */
2417 insn_finishes_cycle_p (rtx insn)
2419 if (SCHED_GROUP_P (insn))
2420 /* After issuing INSN, rest of the sched_group will be forced to issue
2421 in order. Don't make any plans for the rest of cycle. */
2424 /* Finishing the block will, apparently, finish the cycle. */
2425 if (current_sched_info->insn_finishes_block_p
2426 && current_sched_info->insn_finishes_block_p (insn))
2432 /* Define type for target data used in multipass scheduling. */
2433 #ifndef TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T
2434 # define TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T int
2436 typedef TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T first_cycle_multipass_data_t;
2438 /* The following structure describe an entry of the stack of choices. */
2441 /* Ordinal number of the issued insn in the ready queue. */
2443 /* The number of the rest insns whose issues we should try. */
2445 /* The number of issued essential insns. */
2447 /* State after issuing the insn. */
2449 /* Target-specific data. */
2450 first_cycle_multipass_data_t target_data;
2453 /* The following array is used to implement a stack of choices used in
2454 function max_issue. */
2455 static struct choice_entry *choice_stack;
2457 /* The following variable value is number of essential insns issued on
2458 the current cycle. An insn is essential one if it changes the
2459 processors state. */
2460 int cycle_issued_insns;
2462 /* This holds the value of the target dfa_lookahead hook. */
2465 /* The following variable value is maximal number of tries of issuing
2466 insns for the first cycle multipass insn scheduling. We define
2467 this value as constant*(DFA_LOOKAHEAD**ISSUE_RATE). We would not
2468 need this constraint if all real insns (with non-negative codes)
2469 had reservations because in this case the algorithm complexity is
2470 O(DFA_LOOKAHEAD**ISSUE_RATE). Unfortunately, the dfa descriptions
2471 might be incomplete and such insn might occur. For such
2472 descriptions, the complexity of algorithm (without the constraint)
2473 could achieve DFA_LOOKAHEAD ** N , where N is the queue length. */
2474 static int max_lookahead_tries;
2476 /* The following value is value of hook
2477 `first_cycle_multipass_dfa_lookahead' at the last call of
2479 static int cached_first_cycle_multipass_dfa_lookahead = 0;
2481 /* The following value is value of `issue_rate' at the last call of
2483 static int cached_issue_rate = 0;
2485 /* The following function returns maximal (or close to maximal) number
2486 of insns which can be issued on the same cycle and one of which
2487 insns is insns with the best rank (the first insn in READY). To
2488 make this function tries different samples of ready insns. READY
2489 is current queue `ready'. Global array READY_TRY reflects what
2490 insns are already issued in this try. The function stops immediately,
2491 if it reached the such a solution, that all instruction can be issued.
2492 INDEX will contain index of the best insn in READY. The following
2493 function is used only for first cycle multipass scheduling.
2497 This function expects recognized insns only. All USEs,
2498 CLOBBERs, etc must be filtered elsewhere. */
2500 max_issue (struct ready_list *ready, int privileged_n, state_t state,
2501 bool first_cycle_insn_p, int *index)
2503 int n, i, all, n_ready, best, delay, tries_num;
2505 struct choice_entry *top;
2508 n_ready = ready->n_ready;
2509 gcc_assert (dfa_lookahead >= 1 && privileged_n >= 0
2510 && privileged_n <= n_ready);
2512 /* Init MAX_LOOKAHEAD_TRIES. */
2513 if (cached_first_cycle_multipass_dfa_lookahead != dfa_lookahead)
2515 cached_first_cycle_multipass_dfa_lookahead = dfa_lookahead;
2516 max_lookahead_tries = 100;
2517 for (i = 0; i < issue_rate; i++)
2518 max_lookahead_tries *= dfa_lookahead;
2521 /* Init max_points. */
2522 more_issue = issue_rate - cycle_issued_insns;
2523 gcc_assert (more_issue >= 0);
2525 /* The number of the issued insns in the best solution. */
2530 /* Set initial state of the search. */
2531 memcpy (top->state, state, dfa_state_size);
2532 top->rest = dfa_lookahead;
2534 if (targetm.sched.first_cycle_multipass_begin)
2535 targetm.sched.first_cycle_multipass_begin (&top->target_data,
2537 first_cycle_insn_p);
2539 /* Count the number of the insns to search among. */
2540 for (all = i = 0; i < n_ready; i++)
2544 /* I is the index of the insn to try next. */
2549 if (/* If we've reached a dead end or searched enough of what we have
2552 /* or have nothing else to try... */
2554 /* or should not issue more. */
2555 || top->n >= more_issue)
2557 /* ??? (... || i == n_ready). */
2558 gcc_assert (i <= n_ready);
2560 /* We should not issue more than issue_rate instructions. */
2561 gcc_assert (top->n <= more_issue);
2563 if (top == choice_stack)
2566 if (best < top - choice_stack)
2571 /* Try to find issued privileged insn. */
2572 while (n && !ready_try[--n]);
2575 if (/* If all insns are equally good... */
2577 /* Or a privileged insn will be issued. */
2579 /* Then we have a solution. */
2581 best = top - choice_stack;
2582 /* This is the index of the insn issued first in this
2584 *index = choice_stack [1].index;
2585 if (top->n == more_issue || best == all)
2590 /* Set ready-list index to point to the last insn
2591 ('i++' below will advance it to the next insn). */
2597 if (targetm.sched.first_cycle_multipass_backtrack)
2598 targetm.sched.first_cycle_multipass_backtrack (&top->target_data,
2599 ready_try, n_ready);
2602 memcpy (state, top->state, dfa_state_size);
2604 else if (!ready_try [i])
2607 if (tries_num > max_lookahead_tries)
2609 insn = ready_element (ready, i);
2610 delay = state_transition (state, insn);
2613 if (state_dead_lock_p (state)
2614 || insn_finishes_cycle_p (insn))
2615 /* We won't issue any more instructions in the next
2622 if (memcmp (top->state, state, dfa_state_size) != 0)
2625 /* Advance to the next choice_entry. */
2627 /* Initialize it. */
2628 top->rest = dfa_lookahead;
2631 memcpy (top->state, state, dfa_state_size);
2634 if (targetm.sched.first_cycle_multipass_issue)
2635 targetm.sched.first_cycle_multipass_issue (&top->target_data,
2645 /* Increase ready-list index. */
2649 if (targetm.sched.first_cycle_multipass_end)
2650 targetm.sched.first_cycle_multipass_end (best != 0
2651 ? &choice_stack[1].target_data
2654 /* Restore the original state of the DFA. */
2655 memcpy (state, choice_stack->state, dfa_state_size);
2660 /* The following function chooses insn from READY and modifies
2661 READY. The following function is used only for first
2662 cycle multipass scheduling.
2664 -1 if cycle should be advanced,
2665 0 if INSN_PTR is set to point to the desirable insn,
2666 1 if choose_ready () should be restarted without advancing the cycle. */
2668 choose_ready (struct ready_list *ready, bool first_cycle_insn_p,
2673 if (dbg_cnt (sched_insn) == false)
2675 rtx insn = nonscheduled_insns_begin;
2678 insn = next_nonnote_insn (insn);
2680 while (QUEUE_INDEX (insn) == QUEUE_SCHEDULED);
2682 if (QUEUE_INDEX (insn) == QUEUE_READY)
2683 /* INSN is in the ready_list. */
2685 nonscheduled_insns_begin = insn;
2686 ready_remove_insn (insn);
2691 /* INSN is in the queue. Advance cycle to move it to the ready list. */
2697 if (targetm.sched.first_cycle_multipass_dfa_lookahead)
2698 lookahead = targetm.sched.first_cycle_multipass_dfa_lookahead ();
2699 if (lookahead <= 0 || SCHED_GROUP_P (ready_element (ready, 0))
2700 || DEBUG_INSN_P (ready_element (ready, 0)))
2702 if (targetm.sched.dispatch (NULL_RTX, IS_DISPATCH_ON))
2703 *insn_ptr = ready_remove_first_dispatch (ready);
2705 *insn_ptr = ready_remove_first (ready);
2711 /* Try to choose the better insn. */
2712 int index = 0, i, n;
2714 int try_data = 1, try_control = 1;
2717 insn = ready_element (ready, 0);
2718 if (INSN_CODE (insn) < 0)
2720 *insn_ptr = ready_remove_first (ready);
2725 && spec_info->flags & (PREFER_NON_DATA_SPEC
2726 | PREFER_NON_CONTROL_SPEC))
2728 for (i = 0, n = ready->n_ready; i < n; i++)
2733 x = ready_element (ready, i);
2736 if (spec_info->flags & PREFER_NON_DATA_SPEC
2737 && !(s & DATA_SPEC))
2740 if (!(spec_info->flags & PREFER_NON_CONTROL_SPEC)
2745 if (spec_info->flags & PREFER_NON_CONTROL_SPEC
2746 && !(s & CONTROL_SPEC))
2749 if (!(spec_info->flags & PREFER_NON_DATA_SPEC) || !try_data)
2755 ts = TODO_SPEC (insn);
2756 if ((ts & SPECULATIVE)
2757 && (((!try_data && (ts & DATA_SPEC))
2758 || (!try_control && (ts & CONTROL_SPEC)))
2759 || (targetm.sched.first_cycle_multipass_dfa_lookahead_guard_spec
2761 .first_cycle_multipass_dfa_lookahead_guard_spec (insn))))
2762 /* Discard speculative instruction that stands first in the ready
2765 change_queue_index (insn, 1);
2771 for (i = 1; i < ready->n_ready; i++)
2773 insn = ready_element (ready, i);
2776 = ((!try_data && (TODO_SPEC (insn) & DATA_SPEC))
2777 || (!try_control && (TODO_SPEC (insn) & CONTROL_SPEC)));
2780 /* Let the target filter the search space. */
2781 for (i = 1; i < ready->n_ready; i++)
2784 insn = ready_element (ready, i);
2786 /* If this insn is recognizable we should have already
2787 recognized it earlier.
2788 ??? Not very clear where this is supposed to be done.
2790 gcc_checking_assert (INSN_CODE (insn) >= 0
2791 || recog_memoized (insn) < 0);
2794 = (/* INSN_CODE check can be omitted here as it is also done later
2796 INSN_CODE (insn) < 0
2797 || (targetm.sched.first_cycle_multipass_dfa_lookahead_guard
2798 && !targetm.sched.first_cycle_multipass_dfa_lookahead_guard
2802 if (max_issue (ready, 1, curr_state, first_cycle_insn_p, &index) == 0)
2804 *insn_ptr = ready_remove_first (ready);
2805 if (sched_verbose >= 4)
2806 fprintf (sched_dump, ";;\t\tChosen insn (but can't issue) : %s \n",
2807 (*current_sched_info->print_insn) (*insn_ptr, 0));
2812 if (sched_verbose >= 4)
2813 fprintf (sched_dump, ";;\t\tChosen insn : %s\n",
2814 (*current_sched_info->print_insn)
2815 (ready_element (ready, index), 0));
2817 *insn_ptr = ready_remove (ready, index);
2823 /* This function is called when we have successfully scheduled a
2824 block. It uses the schedule stored in the scheduled_insns vector
2825 to rearrange the RTL. PREV_HEAD is used as the anchor to which we
2826 append the scheduled insns; TAIL is the insn after the scheduled
2827 block. TARGET_BB is the argument passed to schedule_block. */
2830 commit_schedule (rtx prev_head, rtx tail, basic_block *target_bb)
2835 last_scheduled_insn = prev_head;
2837 VEC_iterate (rtx, scheduled_insns, i, insn);
2840 if (control_flow_insn_p (last_scheduled_insn)
2841 || current_sched_info->advance_target_bb (*target_bb, insn))
2843 *target_bb = current_sched_info->advance_target_bb (*target_bb, 0);
2849 x = next_real_insn (last_scheduled_insn);
2851 dump_new_block_header (1, *target_bb, x, tail);
2854 last_scheduled_insn = bb_note (*target_bb);
2857 if (current_sched_info->begin_move_insn)
2858 (*current_sched_info->begin_move_insn) (insn, last_scheduled_insn);
2859 move_insn (insn, last_scheduled_insn,
2860 current_sched_info->next_tail);
2861 if (!DEBUG_INSN_P (insn))
2862 reemit_notes (insn);
2863 last_scheduled_insn = insn;
2866 VEC_truncate (rtx, scheduled_insns, 0);
2869 /* Examine all insns on the ready list and queue those which can't be
2870 issued in this cycle. TEMP_STATE is temporary scheduler state we
2871 can use as scratch space. If FIRST_CYCLE_INSN_P is true, no insns
2872 have been issued for the current cycle, which means it is valid to
2873 issue an asm statement. */
2876 prune_ready_list (state_t temp_state, bool first_cycle_insn_p)
2881 for (i = 0; i < ready.n_ready; i++)
2883 rtx insn = ready_element (&ready, i);
2885 const char *reason = "resource conflict";
2887 if (recog_memoized (insn) < 0)
2889 if (!first_cycle_insn_p
2890 && (GET_CODE (PATTERN (insn)) == ASM_INPUT
2891 || asm_noperands (PATTERN (insn)) >= 0))
2895 else if (sched_pressure_p)
2899 memcpy (temp_state, curr_state, dfa_state_size);
2900 cost = state_transition (temp_state, insn);
2908 ready_remove (&ready, i);
2909 queue_insn (insn, cost, reason);
2915 /* Use forward list scheduling to rearrange insns of block pointed to by
2916 TARGET_BB, possibly bringing insns from subsequent blocks in the same
2920 schedule_block (basic_block *target_bb)
2923 bool first_cycle_insn_p;
2925 state_t temp_state = NULL; /* It is used for multipass scheduling. */
2926 int sort_p, advance, start_clock_var;
2928 /* Head/tail info for this block. */
2929 rtx prev_head = current_sched_info->prev_head;
2930 rtx next_tail = current_sched_info->next_tail;
2931 rtx head = NEXT_INSN (prev_head);
2932 rtx tail = PREV_INSN (next_tail);
2934 /* We used to have code to avoid getting parameters moved from hard
2935 argument registers into pseudos.
2937 However, it was removed when it proved to be of marginal benefit
2938 and caused problems because schedule_block and compute_forward_dependences
2939 had different notions of what the "head" insn was. */
2941 gcc_assert (head != tail || INSN_P (head));
2943 haifa_recovery_bb_recently_added_p = false;
2947 dump_new_block_header (0, *target_bb, head, tail);
2949 state_reset (curr_state);
2951 /* Clear the ready list. */
2952 ready.first = ready.veclen - 1;
2956 /* It is used for first cycle multipass scheduling. */
2957 temp_state = alloca (dfa_state_size);
2959 if (targetm.sched.init)
2960 targetm.sched.init (sched_dump, sched_verbose, ready.veclen);
2962 /* We start inserting insns after PREV_HEAD. */
2963 last_scheduled_insn = nonscheduled_insns_begin = prev_head;
2964 last_nondebug_scheduled_insn = NULL_RTX;
2966 gcc_assert ((NOTE_P (last_scheduled_insn)
2967 || DEBUG_INSN_P (last_scheduled_insn))
2968 && BLOCK_FOR_INSN (last_scheduled_insn) == *target_bb);
2970 /* Initialize INSN_QUEUE. Q_SIZE is the total number of insns in the
2975 insn_queue = XALLOCAVEC (rtx, max_insn_queue_index + 1);
2976 memset (insn_queue, 0, (max_insn_queue_index + 1) * sizeof (rtx));
2978 /* Start just before the beginning of time. */
2981 /* We need queue and ready lists and clock_var be initialized
2982 in try_ready () (which is called through init_ready_list ()). */
2983 (*current_sched_info->init_ready_list) ();
2985 /* The algorithm is O(n^2) in the number of ready insns at any given
2986 time in the worst case. Before reload we are more likely to have
2987 big lists so truncate them to a reasonable size. */
2988 if (!reload_completed
2989 && ready.n_ready - ready.n_debug > MAX_SCHED_READY_INSNS)
2991 ready_sort (&ready);
2993 /* Find first free-standing insn past MAX_SCHED_READY_INSNS.
2994 If there are debug insns, we know they're first. */
2995 for (i = MAX_SCHED_READY_INSNS + ready.n_debug; i < ready.n_ready; i++)
2996 if (!SCHED_GROUP_P (ready_element (&ready, i)))
2999 if (sched_verbose >= 2)
3001 fprintf (sched_dump,
3002 ";;\t\tReady list on entry: %d insns\n", ready.n_ready);
3003 fprintf (sched_dump,
3004 ";;\t\t before reload => truncated to %d insns\n", i);
3007 /* Delay all insns past it for 1 cycle. If debug counter is
3008 activated make an exception for the insn right after
3009 nonscheduled_insns_begin. */
3013 if (dbg_cnt (sched_insn) == false)
3014 skip_insn = next_nonnote_insn (nonscheduled_insns_begin);
3016 skip_insn = NULL_RTX;
3018 while (i < ready.n_ready)
3022 insn = ready_remove (&ready, i);
3024 if (insn != skip_insn)
3025 queue_insn (insn, 1, "list truncated");
3028 ready_add (&ready, skip_insn, true);
3032 /* Now we can restore basic block notes and maintain precise cfg. */
3033 restore_bb_notes (*target_bb);
3035 last_clock_var = -1;
3039 gcc_assert (VEC_length (rtx, scheduled_insns) == 0);
3041 /* Loop until all the insns in BB are scheduled. */
3042 while ((*current_sched_info->schedule_more_p) ())
3046 start_clock_var = clock_var;
3050 advance_one_cycle ();
3052 /* Add to the ready list all pending insns that can be issued now.
3053 If there are no ready insns, increment clock until one
3054 is ready and add all pending insns at that point to the ready
3056 queue_to_ready (&ready);
3058 gcc_assert (ready.n_ready);
3060 if (sched_verbose >= 2)
3062 fprintf (sched_dump, ";;\t\tReady list after queue_to_ready: ");
3063 debug_ready_list (&ready);
3065 advance -= clock_var - start_clock_var;
3067 while (advance > 0);
3069 if (ready.n_ready > 0)
3070 prune_ready_list (temp_state, true);
3071 if (ready.n_ready == 0)
3074 first_cycle_insn_p = true;
3075 cycle_issued_insns = 0;
3076 can_issue_more = issue_rate;
3083 if (sort_p && ready.n_ready > 0)
3085 /* Sort the ready list based on priority. This must be
3086 done every iteration through the loop, as schedule_insn
3087 may have readied additional insns that will not be
3088 sorted correctly. */
3089 ready_sort (&ready);
3091 if (sched_verbose >= 2)
3093 fprintf (sched_dump, ";;\t\tReady list after ready_sort: ");
3094 debug_ready_list (&ready);
3098 /* We don't want md sched reorder to even see debug isns, so put
3099 them out right away. */
3100 if (ready.n_ready && DEBUG_INSN_P (ready_element (&ready, 0))
3101 && (*current_sched_info->schedule_more_p) ())
3103 while (ready.n_ready && DEBUG_INSN_P (ready_element (&ready, 0)))
3105 rtx insn = ready_remove_first (&ready);
3106 gcc_assert (DEBUG_INSN_P (insn));
3107 (*current_sched_info->begin_schedule_ready) (insn);
3108 VEC_safe_push (rtx, heap, scheduled_insns, insn);
3109 last_scheduled_insn = insn;
3110 advance = schedule_insn (insn);
3111 gcc_assert (advance == 0);
3112 if (ready.n_ready > 0)
3113 ready_sort (&ready);
3117 if (first_cycle_insn_p && !ready.n_ready)
3120 /* Allow the target to reorder the list, typically for
3121 better instruction bundling. */
3123 && (ready.n_ready == 0
3124 || !SCHED_GROUP_P (ready_element (&ready, 0))))
3126 if (first_cycle_insn_p && targetm.sched.reorder)
3128 = targetm.sched.reorder (sched_dump, sched_verbose,
3129 ready_lastpos (&ready),
3130 &ready.n_ready, clock_var);
3131 else if (!first_cycle_insn_p && targetm.sched.reorder2)
3133 = targetm.sched.reorder2 (sched_dump, sched_verbose,
3135 ? ready_lastpos (&ready) : NULL,
3136 &ready.n_ready, clock_var);
3139 restart_choose_ready:
3140 if (sched_verbose >= 2)
3142 fprintf (sched_dump, ";;\tReady list (t = %3d): ",
3144 debug_ready_list (&ready);
3145 if (sched_pressure_p)
3146 print_curr_reg_pressure ();
3149 if (ready.n_ready == 0
3151 && reload_completed)
3153 /* Allow scheduling insns directly from the queue in case
3154 there's nothing better to do (ready list is empty) but
3155 there are still vacant dispatch slots in the current cycle. */
3156 if (sched_verbose >= 6)
3157 fprintf (sched_dump,";;\t\tSecond chance\n");
3158 memcpy (temp_state, curr_state, dfa_state_size);
3159 if (early_queue_to_ready (temp_state, &ready))
3160 ready_sort (&ready);
3163 if (ready.n_ready == 0
3165 || state_dead_lock_p (curr_state)
3166 || !(*current_sched_info->schedule_more_p) ())
3169 /* Select and remove the insn from the ready list. */
3175 res = choose_ready (&ready, first_cycle_insn_p, &insn);
3181 goto restart_choose_ready;
3183 gcc_assert (insn != NULL_RTX);
3186 insn = ready_remove_first (&ready);
3188 if (sched_pressure_p && INSN_TICK (insn) > clock_var)
3190 ready_add (&ready, insn, true);
3195 if (targetm.sched.dfa_new_cycle
3196 && targetm.sched.dfa_new_cycle (sched_dump, sched_verbose,
3197 insn, last_clock_var,
3198 clock_var, &sort_p))
3199 /* SORT_P is used by the target to override sorting
3200 of the ready list. This is needed when the target
3201 has modified its internal structures expecting that
3202 the insn will be issued next. As we need the insn
3203 to have the highest priority (so it will be returned by
3204 the ready_remove_first call above), we invoke
3205 ready_add (&ready, insn, true).
3206 But, still, there is one issue: INSN can be later
3207 discarded by scheduler's front end through
3208 current_sched_info->can_schedule_ready_p, hence, won't
3211 ready_add (&ready, insn, true);
3217 if (current_sched_info->can_schedule_ready_p
3218 && ! (*current_sched_info->can_schedule_ready_p) (insn))
3219 /* We normally get here only if we don't want to move
3220 insn from the split block. */
3222 TODO_SPEC (insn) = (TODO_SPEC (insn) & ~SPECULATIVE) | HARD_DEP;
3223 goto restart_choose_ready;
3226 /* DECISION is made. */
3228 if (TODO_SPEC (insn) & SPECULATIVE)
3229 generate_recovery_code (insn);
3231 if (targetm.sched.dispatch (NULL_RTX, IS_DISPATCH_ON))
3232 targetm.sched.dispatch_do (insn, ADD_TO_DISPATCH_WINDOW);
3234 /* Update counters, etc in the scheduler's front end. */
3235 (*current_sched_info->begin_schedule_ready) (insn);
3236 VEC_safe_push (rtx, heap, scheduled_insns, insn);
3237 gcc_assert (NONDEBUG_INSN_P (insn));
3238 last_nondebug_scheduled_insn = last_scheduled_insn = insn;
3240 if (recog_memoized (insn) >= 0)
3242 memcpy (temp_state, curr_state, dfa_state_size);
3243 cost = state_transition (curr_state, insn);
3244 if (!sched_pressure_p)
3245 gcc_assert (cost < 0);
3246 if (memcmp (temp_state, curr_state, dfa_state_size) != 0)
3247 cycle_issued_insns++;
3251 asm_p = (GET_CODE (PATTERN (insn)) == ASM_INPUT
3252 || asm_noperands (PATTERN (insn)) >= 0);
3254 if (targetm.sched.variable_issue)
3256 targetm.sched.variable_issue (sched_dump, sched_verbose,
3257 insn, can_issue_more);
3258 /* A naked CLOBBER or USE generates no instruction, so do
3259 not count them against the issue rate. */
3260 else if (GET_CODE (PATTERN (insn)) != USE
3261 && GET_CODE (PATTERN (insn)) != CLOBBER)
3263 advance = schedule_insn (insn);
3265 /* After issuing an asm insn we should start a new cycle. */
3266 if (advance == 0 && asm_p)
3271 first_cycle_insn_p = false;
3272 if (ready.n_ready > 0)
3273 prune_ready_list (temp_state, false);
3280 fprintf (sched_dump, ";;\tReady list (final): ");
3281 debug_ready_list (&ready);
3284 if (current_sched_info->queue_must_finish_empty)
3285 /* Sanity check -- queue must be empty now. Meaningless if region has
3287 gcc_assert (!q_size && !ready.n_ready && !ready.n_debug);
3290 /* We must maintain QUEUE_INDEX between blocks in region. */
3291 for (i = ready.n_ready - 1; i >= 0; i--)
3295 x = ready_element (&ready, i);
3296 QUEUE_INDEX (x) = QUEUE_NOWHERE;
3297 TODO_SPEC (x) = (TODO_SPEC (x) & ~SPECULATIVE) | HARD_DEP;
3301 for (i = 0; i <= max_insn_queue_index; i++)
3304 for (link = insn_queue[i]; link; link = XEXP (link, 1))
3309 QUEUE_INDEX (x) = QUEUE_NOWHERE;
3310 TODO_SPEC (x) = (TODO_SPEC (x) & ~SPECULATIVE) | HARD_DEP;
3312 free_INSN_LIST_list (&insn_queue[i]);
3316 commit_schedule (prev_head, tail, target_bb);
3318 fprintf (sched_dump, ";; total time = %d\n", clock_var);
3320 if (!current_sched_info->queue_must_finish_empty
3321 || haifa_recovery_bb_recently_added_p)
3323 /* INSN_TICK (minimum clock tick at which the insn becomes
3324 ready) may be not correct for the insn in the subsequent
3325 blocks of the region. We should use a correct value of
3326 `clock_var' or modify INSN_TICK. It is better to keep
3327 clock_var value equal to 0 at the start of a basic block.
3328 Therefore we modify INSN_TICK here. */
3329 fix_inter_tick (NEXT_INSN (prev_head), last_scheduled_insn);
3332 if (targetm.sched.finish)
3334 targetm.sched.finish (sched_dump, sched_verbose);
3335 /* Target might have added some instructions to the scheduled block
3336 in its md_finish () hook. These new insns don't have any data
3337 initialized and to identify them we extend h_i_d so that they'll
3339 sched_init_luids (NULL, NULL, NULL, NULL);
3343 fprintf (sched_dump, ";; new head = %d\n;; new tail = %d\n\n",
3344 INSN_UID (head), INSN_UID (tail));
3346 /* Update head/tail boundaries. */
3347 head = NEXT_INSN (prev_head);
3348 tail = last_scheduled_insn;
3350 head = restore_other_notes (head, NULL);
3352 current_sched_info->head = head;
3353 current_sched_info->tail = tail;
3356 /* Set_priorities: compute priority of each insn in the block. */
3359 set_priorities (rtx head, rtx tail)
3363 int sched_max_insns_priority =
3364 current_sched_info->sched_max_insns_priority;
3367 if (head == tail && ! INSN_P (head))
3372 prev_head = PREV_INSN (head);
3373 for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
3379 (void) priority (insn);
3381 gcc_assert (INSN_PRIORITY_KNOWN (insn));
3383 sched_max_insns_priority = MAX (sched_max_insns_priority,
3384 INSN_PRIORITY (insn));
3387 current_sched_info->sched_max_insns_priority = sched_max_insns_priority;
3392 /* Set dump and sched_verbose for the desired debugging output. If no
3393 dump-file was specified, but -fsched-verbose=N (any N), print to stderr.
3394 For -fsched-verbose=N, N>=10, print everything to stderr. */
3396 setup_sched_dump (void)
3398 sched_verbose = sched_verbose_param;
3399 if (sched_verbose_param == 0 && dump_file)
3401 sched_dump = ((sched_verbose_param >= 10 || !dump_file)
3402 ? stderr : dump_file);
3405 /* Initialize some global state for the scheduler. This function works
3406 with the common data shared between all the schedulers. It is called
3407 from the scheduler specific initialization routine. */
3412 /* Disable speculative loads in their presence if cc0 defined. */
3414 flag_schedule_speculative_load = 0;
3417 if (targetm.sched.dispatch (NULL_RTX, IS_DISPATCH_ON))
3418 targetm.sched.dispatch_do (NULL_RTX, DISPATCH_INIT);
3420 sched_pressure_p = (flag_sched_pressure && ! reload_completed
3421 && common_sched_info->sched_pass_id == SCHED_RGN_PASS);
3423 if (sched_pressure_p)
3424 ira_setup_eliminable_regset ();
3426 /* Initialize SPEC_INFO. */
3427 if (targetm.sched.set_sched_flags)
3429 spec_info = &spec_info_var;
3430 targetm.sched.set_sched_flags (spec_info);
3432 if (spec_info->mask != 0)
3434 spec_info->data_weakness_cutoff =
3435 (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF) * MAX_DEP_WEAK) / 100;
3436 spec_info->control_weakness_cutoff =
3437 (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF)
3438 * REG_BR_PROB_BASE) / 100;
3441 /* So we won't read anything accidentally. */
3446 /* So we won't read anything accidentally. */
3449 /* Initialize issue_rate. */
3450 if (targetm.sched.issue_rate)
3451 issue_rate = targetm.sched.issue_rate ();
3455 if (cached_issue_rate != issue_rate)
3457 cached_issue_rate = issue_rate;
3458 /* To invalidate max_lookahead_tries: */
3459 cached_first_cycle_multipass_dfa_lookahead = 0;
3462 if (targetm.sched.first_cycle_multipass_dfa_lookahead)
3463 dfa_lookahead = targetm.sched.first_cycle_multipass_dfa_lookahead ();
3467 if (targetm.sched.init_dfa_pre_cycle_insn)
3468 targetm.sched.init_dfa_pre_cycle_insn ();
3470 if (targetm.sched.init_dfa_post_cycle_insn)
3471 targetm.sched.init_dfa_post_cycle_insn ();
3474 dfa_state_size = state_size ();
3476 init_alias_analysis ();
3478 df_set_flags (DF_LR_RUN_DCE);
3479 df_note_add_problem ();
3481 /* More problems needed for interloop dep calculation in SMS. */
3482 if (common_sched_info->sched_pass_id == SCHED_SMS_PASS)
3484 df_rd_add_problem ();
3485 df_chain_add_problem (DF_DU_CHAIN + DF_UD_CHAIN);
3490 /* Do not run DCE after reload, as this can kill nops inserted
3492 if (reload_completed)
3493 df_clear_flags (DF_LR_RUN_DCE);
3495 regstat_compute_calls_crossed ();
3497 if (targetm.sched.init_global)
3498 targetm.sched.init_global (sched_dump, sched_verbose, get_max_uid () + 1);
3500 if (sched_pressure_p)
3502 int i, max_regno = max_reg_num ();
3504 ira_set_pseudo_classes (sched_verbose ? sched_dump : NULL);
3505 sched_regno_pressure_class
3506 = (enum reg_class *) xmalloc (max_regno * sizeof (enum reg_class));
3507 for (i = 0; i < max_regno; i++)
3508 sched_regno_pressure_class[i]
3509 = (i < FIRST_PSEUDO_REGISTER
3510 ? ira_pressure_class_translate[REGNO_REG_CLASS (i)]
3511 : ira_pressure_class_translate[reg_allocno_class (i)]);
3512 curr_reg_live = BITMAP_ALLOC (NULL);
3513 saved_reg_live = BITMAP_ALLOC (NULL);
3514 region_ref_regs = BITMAP_ALLOC (NULL);
3517 curr_state = xmalloc (dfa_state_size);
3520 static void haifa_init_only_bb (basic_block, basic_block);
3522 /* Initialize data structures specific to the Haifa scheduler. */
3524 haifa_sched_init (void)
3526 setup_sched_dump ();
3529 scheduled_insns = VEC_alloc (rtx, heap, 0);
3531 if (spec_info != NULL)
3533 sched_deps_info->use_deps_list = 1;
3534 sched_deps_info->generate_spec_deps = 1;
3537 /* Initialize luids, dependency caches, target and h_i_d for the
3540 bb_vec_t bbs = VEC_alloc (basic_block, heap, n_basic_blocks);
3546 VEC_quick_push (basic_block, bbs, bb);
3547 sched_init_luids (bbs, NULL, NULL, NULL);
3548 sched_deps_init (true);
3549 sched_extend_target ();
3550 haifa_init_h_i_d (bbs, NULL, NULL, NULL);
3552 VEC_free (basic_block, heap, bbs);
3555 sched_init_only_bb = haifa_init_only_bb;
3556 sched_split_block = sched_split_block_1;
3557 sched_create_empty_bb = sched_create_empty_bb_1;
3558 haifa_recovery_bb_ever_added_p = false;
3560 #ifdef ENABLE_CHECKING
3561 /* This is used preferably for finding bugs in check_cfg () itself.
3562 We must call sched_bbs_init () before check_cfg () because check_cfg ()
3563 assumes that the last insn in the last bb has a non-null successor. */
3567 nr_begin_data = nr_begin_control = nr_be_in_data = nr_be_in_control = 0;
3568 before_recovery = 0;
3572 /* Finish work with the data specific to the Haifa scheduler. */
3574 haifa_sched_finish (void)
3576 sched_create_empty_bb = NULL;
3577 sched_split_block = NULL;
3578 sched_init_only_bb = NULL;
3580 if (spec_info && spec_info->dump)
3582 char c = reload_completed ? 'a' : 'b';
3584 fprintf (spec_info->dump,
3585 ";; %s:\n", current_function_name ());
3587 fprintf (spec_info->dump,
3588 ";; Procedure %cr-begin-data-spec motions == %d\n",
3590 fprintf (spec_info->dump,
3591 ";; Procedure %cr-be-in-data-spec motions == %d\n",
3593 fprintf (spec_info->dump,
3594 ";; Procedure %cr-begin-control-spec motions == %d\n",
3595 c, nr_begin_control);
3596 fprintf (spec_info->dump,
3597 ";; Procedure %cr-be-in-control-spec motions == %d\n",
3598 c, nr_be_in_control);
3601 VEC_free (rtx, heap, scheduled_insns);
3603 /* Finalize h_i_d, dependency caches, and luids for the whole
3604 function. Target will be finalized in md_global_finish (). */
3605 sched_deps_finish ();
3606 sched_finish_luids ();
3607 current_sched_info = NULL;
3611 /* Free global data used during insn scheduling. This function works with
3612 the common data shared between the schedulers. */
3617 haifa_finish_h_i_d ();
3618 if (sched_pressure_p)
3620 free (sched_regno_pressure_class);
3621 BITMAP_FREE (region_ref_regs);
3622 BITMAP_FREE (saved_reg_live);
3623 BITMAP_FREE (curr_reg_live);
3627 if (targetm.sched.finish_global)
3628 targetm.sched.finish_global (sched_dump, sched_verbose);
3630 end_alias_analysis ();
3632 regstat_free_calls_crossed ();
3636 #ifdef ENABLE_CHECKING
3637 /* After reload ia64 backend clobbers CFG, so can't check anything. */
3638 if (!reload_completed)
3643 /* Fix INSN_TICKs of the instructions in the current block as well as
3644 INSN_TICKs of their dependents.
3645 HEAD and TAIL are the begin and the end of the current scheduled block. */
3647 fix_inter_tick (rtx head, rtx tail)
3649 /* Set of instructions with corrected INSN_TICK. */
3650 bitmap_head processed;
3651 /* ??? It is doubtful if we should assume that cycle advance happens on
3652 basic block boundaries. Basically insns that are unconditionally ready
3653 on the start of the block are more preferable then those which have
3654 a one cycle dependency over insn from the previous block. */
3655 int next_clock = clock_var + 1;
3657 bitmap_initialize (&processed, 0);
3659 /* Iterates over scheduled instructions and fix their INSN_TICKs and
3660 INSN_TICKs of dependent instructions, so that INSN_TICKs are consistent
3661 across different blocks. */
3662 for (tail = NEXT_INSN (tail); head != tail; head = NEXT_INSN (head))
3667 sd_iterator_def sd_it;
3670 tick = INSN_TICK (head);
3671 gcc_assert (tick >= MIN_TICK);
3673 /* Fix INSN_TICK of instruction from just scheduled block. */
3674 if (bitmap_set_bit (&processed, INSN_LUID (head)))
3678 if (tick < MIN_TICK)
3681 INSN_TICK (head) = tick;
3684 FOR_EACH_DEP (head, SD_LIST_RES_FORW, sd_it, dep)
3688 next = DEP_CON (dep);
3689 tick = INSN_TICK (next);
3691 if (tick != INVALID_TICK
3692 /* If NEXT has its INSN_TICK calculated, fix it.
3693 If not - it will be properly calculated from
3694 scratch later in fix_tick_ready. */
3695 && bitmap_set_bit (&processed, INSN_LUID (next)))
3699 if (tick < MIN_TICK)
3702 if (tick > INTER_TICK (next))
3703 INTER_TICK (next) = tick;
3705 tick = INTER_TICK (next);
3707 INSN_TICK (next) = tick;
3712 bitmap_clear (&processed);
3715 static int haifa_speculate_insn (rtx, ds_t, rtx *);
3717 /* Check if NEXT is ready to be added to the ready or queue list.
3718 If "yes", add it to the proper list.
3720 -1 - is not ready yet,
3721 0 - added to the ready list,
3722 0 < N - queued for N cycles. */
3724 try_ready (rtx next)
3728 ts = &TODO_SPEC (next);
3731 gcc_assert (!(old_ts & ~(SPECULATIVE | HARD_DEP))
3732 && ((old_ts & HARD_DEP)
3733 || (old_ts & SPECULATIVE)));
3735 if (sd_lists_empty_p (next, SD_LIST_BACK))
3736 /* NEXT has all its dependencies resolved. */
3738 /* Remove HARD_DEP bit from NEXT's status. */
3741 if (current_sched_info->flags & DO_SPECULATION)
3742 /* Remove all speculative bits from NEXT's status. */
3743 *ts &= ~SPECULATIVE;
3747 /* One of the NEXT's dependencies has been resolved.
3748 Recalculate NEXT's status. */
3750 *ts &= ~SPECULATIVE & ~HARD_DEP;
3752 if (sd_lists_empty_p (next, SD_LIST_HARD_BACK))
3753 /* Now we've got NEXT with speculative deps only.
3754 1. Look at the deps to see what we have to do.
3755 2. Check if we can do 'todo'. */
3757 sd_iterator_def sd_it;
3759 bool first_p = true;
3761 FOR_EACH_DEP (next, SD_LIST_BACK, sd_it, dep)
3763 ds_t ds = DEP_STATUS (dep) & SPECULATIVE;
3765 if (DEBUG_INSN_P (DEP_PRO (dep))
3766 && !DEBUG_INSN_P (next))
3776 *ts = ds_merge (*ts, ds);
3779 if (ds_weak (*ts) < spec_info->data_weakness_cutoff)
3780 /* Too few points. */
3781 *ts = (*ts & ~SPECULATIVE) | HARD_DEP;
3788 gcc_assert (*ts == old_ts
3789 && QUEUE_INDEX (next) == QUEUE_NOWHERE);
3790 else if (current_sched_info->new_ready)
3791 *ts = current_sched_info->new_ready (next, *ts);
3793 /* * if !(old_ts & SPECULATIVE) (e.g. HARD_DEP or 0), then insn might
3794 have its original pattern or changed (speculative) one. This is due
3795 to changing ebb in region scheduling.
3796 * But if (old_ts & SPECULATIVE), then we are pretty sure that insn
3797 has speculative pattern.
3799 We can't assert (!(*ts & HARD_DEP) || *ts == old_ts) here because
3800 control-speculative NEXT could have been discarded by sched-rgn.c
3801 (the same case as when discarded by can_schedule_ready_p ()). */
3803 if ((*ts & SPECULATIVE)
3804 /* If (old_ts == *ts), then (old_ts & SPECULATIVE) and we don't
3805 need to change anything. */
3811 gcc_assert ((*ts & SPECULATIVE) && !(*ts & ~SPECULATIVE));
3813 res = haifa_speculate_insn (next, *ts, &new_pat);
3818 /* It would be nice to change DEP_STATUS of all dependences,
3819 which have ((DEP_STATUS & SPECULATIVE) == *ts) to HARD_DEP,
3820 so we won't reanalyze anything. */
3821 *ts = (*ts & ~SPECULATIVE) | HARD_DEP;
3825 /* We follow the rule, that every speculative insn
3826 has non-null ORIG_PAT. */
3827 if (!ORIG_PAT (next))
3828 ORIG_PAT (next) = PATTERN (next);
3832 if (!ORIG_PAT (next))
3833 /* If we gonna to overwrite the original pattern of insn,
3835 ORIG_PAT (next) = PATTERN (next);
3837 haifa_change_pattern (next, new_pat);
3845 /* We need to restore pattern only if (*ts == 0), because otherwise it is
3846 either correct (*ts & SPECULATIVE),
3847 or we simply don't care (*ts & HARD_DEP). */
3849 gcc_assert (!ORIG_PAT (next)
3850 || !IS_SPECULATION_BRANCHY_CHECK_P (next));
3854 /* We can't assert (QUEUE_INDEX (next) == QUEUE_NOWHERE) here because
3855 control-speculative NEXT could have been discarded by sched-rgn.c
3856 (the same case as when discarded by can_schedule_ready_p ()). */
3857 /*gcc_assert (QUEUE_INDEX (next) == QUEUE_NOWHERE);*/
3859 change_queue_index (next, QUEUE_NOWHERE);
3862 else if (!(*ts & BEGIN_SPEC) && ORIG_PAT (next) && !IS_SPECULATION_CHECK_P (next))
3863 /* We should change pattern of every previously speculative
3864 instruction - and we determine if NEXT was speculative by using
3865 ORIG_PAT field. Except one case - speculation checks have ORIG_PAT
3866 pat too, so skip them. */
3868 haifa_change_pattern (next, ORIG_PAT (next));
3869 ORIG_PAT (next) = 0;
3872 if (sched_verbose >= 2)
3874 int s = TODO_SPEC (next);
3876 fprintf (sched_dump, ";;\t\tdependencies resolved: insn %s",
3877 (*current_sched_info->print_insn) (next, 0));
3879 if (spec_info && spec_info->dump)
3882 fprintf (spec_info->dump, "; data-spec;");
3883 if (s & BEGIN_CONTROL)
3884 fprintf (spec_info->dump, "; control-spec;");
3885 if (s & BE_IN_CONTROL)
3886 fprintf (spec_info->dump, "; in-control-spec;");
3889 fprintf (sched_dump, "\n");
3892 adjust_priority (next);
3894 return fix_tick_ready (next);
3897 /* Calculate INSN_TICK of NEXT and add it to either ready or queue list. */
3899 fix_tick_ready (rtx next)
3903 if (!DEBUG_INSN_P (next) && !sd_lists_empty_p (next, SD_LIST_RES_BACK))
3906 sd_iterator_def sd_it;
3909 tick = INSN_TICK (next);
3910 /* if tick is not equal to INVALID_TICK, then update
3911 INSN_TICK of NEXT with the most recent resolved dependence
3912 cost. Otherwise, recalculate from scratch. */
3913 full_p = (tick == INVALID_TICK);
3915 FOR_EACH_DEP (next, SD_LIST_RES_BACK, sd_it, dep)
3917 rtx pro = DEP_PRO (dep);
3920 gcc_assert (INSN_TICK (pro) >= MIN_TICK);
3922 tick1 = INSN_TICK (pro) + dep_cost (dep);
3933 INSN_TICK (next) = tick;
3935 delay = tick - clock_var;
3936 if (delay <= 0 || sched_pressure_p)
3937 delay = QUEUE_READY;
3939 change_queue_index (next, delay);
3944 /* Move NEXT to the proper queue list with (DELAY >= 1),
3945 or add it to the ready list (DELAY == QUEUE_READY),
3946 or remove it from ready and queue lists at all (DELAY == QUEUE_NOWHERE). */
3948 change_queue_index (rtx next, int delay)
3950 int i = QUEUE_INDEX (next);
3952 gcc_assert (QUEUE_NOWHERE <= delay && delay <= max_insn_queue_index
3954 gcc_assert (i != QUEUE_SCHEDULED);
3956 if ((delay > 0 && NEXT_Q_AFTER (q_ptr, delay) == i)
3957 || (delay < 0 && delay == i))
3958 /* We have nothing to do. */
3961 /* Remove NEXT from wherever it is now. */
3962 if (i == QUEUE_READY)
3963 ready_remove_insn (next);
3965 queue_remove (next);
3967 /* Add it to the proper place. */
3968 if (delay == QUEUE_READY)
3969 ready_add (readyp, next, false);
3970 else if (delay >= 1)
3971 queue_insn (next, delay, "change queue index");
3973 if (sched_verbose >= 2)
3975 fprintf (sched_dump, ";;\t\ttick updated: insn %s",
3976 (*current_sched_info->print_insn) (next, 0));
3978 if (delay == QUEUE_READY)
3979 fprintf (sched_dump, " into ready\n");
3980 else if (delay >= 1)
3981 fprintf (sched_dump, " into queue with cost=%d\n", delay);
3983 fprintf (sched_dump, " removed from ready or queue lists\n");
3987 static int sched_ready_n_insns = -1;
3989 /* Initialize per region data structures. */
3991 sched_extend_ready_list (int new_sched_ready_n_insns)
3995 if (sched_ready_n_insns == -1)
3996 /* At the first call we need to initialize one more choice_stack
4000 sched_ready_n_insns = 0;
4001 VEC_reserve (rtx, heap, scheduled_insns, new_sched_ready_n_insns);
4004 i = sched_ready_n_insns + 1;
4006 ready.veclen = new_sched_ready_n_insns + issue_rate;
4007 ready.vec = XRESIZEVEC (rtx, ready.vec, ready.veclen);
4009 gcc_assert (new_sched_ready_n_insns >= sched_ready_n_insns);
4011 ready_try = (char *) xrecalloc (ready_try, new_sched_ready_n_insns,
4012 sched_ready_n_insns, sizeof (*ready_try));
4014 /* We allocate +1 element to save initial state in the choice_stack[0]
4016 choice_stack = XRESIZEVEC (struct choice_entry, choice_stack,
4017 new_sched_ready_n_insns + 1);
4019 for (; i <= new_sched_ready_n_insns; i++)
4021 choice_stack[i].state = xmalloc (dfa_state_size);
4023 if (targetm.sched.first_cycle_multipass_init)
4024 targetm.sched.first_cycle_multipass_init (&(choice_stack[i]
4028 sched_ready_n_insns = new_sched_ready_n_insns;
4031 /* Free per region data structures. */
4033 sched_finish_ready_list (void)
4044 for (i = 0; i <= sched_ready_n_insns; i++)
4046 if (targetm.sched.first_cycle_multipass_fini)
4047 targetm.sched.first_cycle_multipass_fini (&(choice_stack[i]
4050 free (choice_stack [i].state);
4052 free (choice_stack);
4053 choice_stack = NULL;
4055 sched_ready_n_insns = -1;
4059 haifa_luid_for_non_insn (rtx x)
4061 gcc_assert (NOTE_P (x) || LABEL_P (x));
4066 /* Generates recovery code for INSN. */
4068 generate_recovery_code (rtx insn)
4070 if (TODO_SPEC (insn) & BEGIN_SPEC)
4071 begin_speculative_block (insn);
4073 /* Here we have insn with no dependencies to
4074 instructions other then CHECK_SPEC ones. */
4076 if (TODO_SPEC (insn) & BE_IN_SPEC)
4077 add_to_speculative_block (insn);
4081 Tries to add speculative dependencies of type FS between instructions
4082 in deps_list L and TWIN. */
4084 process_insn_forw_deps_be_in_spec (rtx insn, rtx twin, ds_t fs)
4086 sd_iterator_def sd_it;
4089 FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
4094 consumer = DEP_CON (dep);
4096 ds = DEP_STATUS (dep);
4098 if (/* If we want to create speculative dep. */
4100 /* And we can do that because this is a true dep. */
4101 && (ds & DEP_TYPES) == DEP_TRUE)
4103 gcc_assert (!(ds & BE_IN_SPEC));
4105 if (/* If this dep can be overcome with 'begin speculation'. */
4107 /* Then we have a choice: keep the dep 'begin speculative'
4108 or transform it into 'be in speculative'. */
4110 if (/* In try_ready we assert that if insn once became ready
4111 it can be removed from the ready (or queue) list only
4112 due to backend decision. Hence we can't let the
4113 probability of the speculative dep to decrease. */
4114 ds_weak (ds) <= ds_weak (fs))
4118 new_ds = (ds & ~BEGIN_SPEC) | fs;
4120 if (/* consumer can 'be in speculative'. */
4121 sched_insn_is_legitimate_for_speculation_p (consumer,
4123 /* Transform it to be in speculative. */
4128 /* Mark the dep as 'be in speculative'. */
4133 dep_def _new_dep, *new_dep = &_new_dep;
4135 init_dep_1 (new_dep, twin, consumer, DEP_TYPE (dep), ds);
4136 sd_add_dep (new_dep, false);
4141 /* Generates recovery code for BEGIN speculative INSN. */
4143 begin_speculative_block (rtx insn)
4145 if (TODO_SPEC (insn) & BEGIN_DATA)
4147 if (TODO_SPEC (insn) & BEGIN_CONTROL)
4150 create_check_block_twin (insn, false);
4152 TODO_SPEC (insn) &= ~BEGIN_SPEC;
4155 static void haifa_init_insn (rtx);
4157 /* Generates recovery code for BE_IN speculative INSN. */
4159 add_to_speculative_block (rtx insn)
4162 sd_iterator_def sd_it;
4165 rtx_vec_t priorities_roots;
4167 ts = TODO_SPEC (insn);
4168 gcc_assert (!(ts & ~BE_IN_SPEC));
4170 if (ts & BE_IN_DATA)
4172 if (ts & BE_IN_CONTROL)
4175 TODO_SPEC (insn) &= ~BE_IN_SPEC;
4176 gcc_assert (!TODO_SPEC (insn));
4178 DONE_SPEC (insn) |= ts;
4180 /* First we convert all simple checks to branchy. */
4181 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
4182 sd_iterator_cond (&sd_it, &dep);)
4184 rtx check = DEP_PRO (dep);
4186 if (IS_SPECULATION_SIMPLE_CHECK_P (check))
4188 create_check_block_twin (check, true);
4190 /* Restart search. */
4191 sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
4194 /* Continue search. */
4195 sd_iterator_next (&sd_it);
4198 priorities_roots = NULL;
4199 clear_priorities (insn, &priorities_roots);
4206 /* Get the first backward dependency of INSN. */
4207 sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
4208 if (!sd_iterator_cond (&sd_it, &dep))
4209 /* INSN has no backward dependencies left. */
4212 gcc_assert ((DEP_STATUS (dep) & BEGIN_SPEC) == 0
4213 && (DEP_STATUS (dep) & BE_IN_SPEC) != 0
4214 && (DEP_STATUS (dep) & DEP_TYPES) == DEP_TRUE);
4216 check = DEP_PRO (dep);
4218 gcc_assert (!IS_SPECULATION_CHECK_P (check) && !ORIG_PAT (check)
4219 && QUEUE_INDEX (check) == QUEUE_NOWHERE);
4221 rec = BLOCK_FOR_INSN (check);
4223 twin = emit_insn_before (copy_insn (PATTERN (insn)), BB_END (rec));
4224 haifa_init_insn (twin);
4226 sd_copy_back_deps (twin, insn, true);
4228 if (sched_verbose && spec_info->dump)
4229 /* INSN_BB (insn) isn't determined for twin insns yet.
4230 So we can't use current_sched_info->print_insn. */
4231 fprintf (spec_info->dump, ";;\t\tGenerated twin insn : %d/rec%d\n",
4232 INSN_UID (twin), rec->index);
4234 twins = alloc_INSN_LIST (twin, twins);
4236 /* Add dependences between TWIN and all appropriate
4237 instructions from REC. */
4238 FOR_EACH_DEP (insn, SD_LIST_SPEC_BACK, sd_it, dep)
4240 rtx pro = DEP_PRO (dep);
4242 gcc_assert (DEP_TYPE (dep) == REG_DEP_TRUE);
4244 /* INSN might have dependencies from the instructions from
4245 several recovery blocks. At this iteration we process those
4246 producers that reside in REC. */
4247 if (BLOCK_FOR_INSN (pro) == rec)
4249 dep_def _new_dep, *new_dep = &_new_dep;
4251 init_dep (new_dep, pro, twin, REG_DEP_TRUE);
4252 sd_add_dep (new_dep, false);
4256 process_insn_forw_deps_be_in_spec (insn, twin, ts);
4258 /* Remove all dependencies between INSN and insns in REC. */
4259 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
4260 sd_iterator_cond (&sd_it, &dep);)
4262 rtx pro = DEP_PRO (dep);
4264 if (BLOCK_FOR_INSN (pro) == rec)
4265 sd_delete_dep (sd_it);
4267 sd_iterator_next (&sd_it);
4271 /* We couldn't have added the dependencies between INSN and TWINS earlier
4272 because that would make TWINS appear in the INSN_BACK_DEPS (INSN). */
4277 twin = XEXP (twins, 0);
4280 dep_def _new_dep, *new_dep = &_new_dep;
4282 init_dep (new_dep, insn, twin, REG_DEP_OUTPUT);
4283 sd_add_dep (new_dep, false);
4286 twin = XEXP (twins, 1);
4287 free_INSN_LIST_node (twins);
4291 calc_priorities (priorities_roots);
4292 VEC_free (rtx, heap, priorities_roots);
4295 /* Extends and fills with zeros (only the new part) array pointed to by P. */
4297 xrecalloc (void *p, size_t new_nmemb, size_t old_nmemb, size_t size)
4299 gcc_assert (new_nmemb >= old_nmemb);
4300 p = XRESIZEVAR (void, p, new_nmemb * size);
4301 memset (((char *) p) + old_nmemb * size, 0, (new_nmemb - old_nmemb) * size);
4306 Find fallthru edge from PRED. */
4308 find_fallthru_edge_from (basic_block pred)
4313 succ = pred->next_bb;
4314 gcc_assert (succ->prev_bb == pred);
4316 if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds))
4318 e = find_fallthru_edge (pred->succs);
4322 gcc_assert (e->dest == succ);
4328 e = find_fallthru_edge (succ->preds);
4332 gcc_assert (e->src == pred);
4340 /* Extend per basic block data structures. */
4342 sched_extend_bb (void)
4346 /* The following is done to keep current_sched_info->next_tail non null. */
4347 insn = BB_END (EXIT_BLOCK_PTR->prev_bb);
4348 if (NEXT_INSN (insn) == 0
4351 /* Don't emit a NOTE if it would end up before a BARRIER. */
4352 && !BARRIER_P (NEXT_INSN (insn))))
4354 rtx note = emit_note_after (NOTE_INSN_DELETED, insn);
4355 /* Make insn appear outside BB. */
4356 set_block_for_insn (note, NULL);
4357 BB_END (EXIT_BLOCK_PTR->prev_bb) = insn;
4361 /* Init per basic block data structures. */
4363 sched_init_bbs (void)
4368 /* Initialize BEFORE_RECOVERY variable. */
4370 init_before_recovery (basic_block *before_recovery_ptr)
4375 last = EXIT_BLOCK_PTR->prev_bb;
4376 e = find_fallthru_edge_from (last);
4380 /* We create two basic blocks:
4381 1. Single instruction block is inserted right after E->SRC
4383 2. Empty block right before EXIT_BLOCK.
4384 Between these two blocks recovery blocks will be emitted. */
4386 basic_block single, empty;
4389 /* If the fallthrough edge to exit we've found is from the block we've
4390 created before, don't do anything more. */
4391 if (last == after_recovery)
4394 adding_bb_to_current_region_p = false;
4396 single = sched_create_empty_bb (last);
4397 empty = sched_create_empty_bb (single);
4399 /* Add new blocks to the root loop. */
4400 if (current_loops != NULL)
4402 add_bb_to_loop (single, VEC_index (loop_p, current_loops->larray, 0));
4403 add_bb_to_loop (empty, VEC_index (loop_p, current_loops->larray, 0));
4406 single->count = last->count;
4407 empty->count = last->count;
4408 single->frequency = last->frequency;
4409 empty->frequency = last->frequency;
4410 BB_COPY_PARTITION (single, last);
4411 BB_COPY_PARTITION (empty, last);
4413 redirect_edge_succ (e, single);
4414 make_single_succ_edge (single, empty, 0);
4415 make_single_succ_edge (empty, EXIT_BLOCK_PTR,
4416 EDGE_FALLTHRU | EDGE_CAN_FALLTHRU);
4418 label = block_label (empty);
4419 x = emit_jump_insn_after (gen_jump (label), BB_END (single));
4420 JUMP_LABEL (x) = label;
4421 LABEL_NUSES (label)++;
4422 haifa_init_insn (x);
4424 emit_barrier_after (x);
4426 sched_init_only_bb (empty, NULL);
4427 sched_init_only_bb (single, NULL);
4430 adding_bb_to_current_region_p = true;
4431 before_recovery = single;
4432 after_recovery = empty;
4434 if (before_recovery_ptr)
4435 *before_recovery_ptr = before_recovery;
4437 if (sched_verbose >= 2 && spec_info->dump)
4438 fprintf (spec_info->dump,
4439 ";;\t\tFixed fallthru to EXIT : %d->>%d->%d->>EXIT\n",
4440 last->index, single->index, empty->index);
4443 before_recovery = last;
4446 /* Returns new recovery block. */
4448 sched_create_recovery_block (basic_block *before_recovery_ptr)
4454 haifa_recovery_bb_recently_added_p = true;
4455 haifa_recovery_bb_ever_added_p = true;
4457 init_before_recovery (before_recovery_ptr);
4459 barrier = get_last_bb_insn (before_recovery);
4460 gcc_assert (BARRIER_P (barrier));
4462 label = emit_label_after (gen_label_rtx (), barrier);
4464 rec = create_basic_block (label, label, before_recovery);
4466 /* A recovery block always ends with an unconditional jump. */
4467 emit_barrier_after (BB_END (rec));
4469 if (BB_PARTITION (before_recovery) != BB_UNPARTITIONED)
4470 BB_SET_PARTITION (rec, BB_COLD_PARTITION);
4472 if (sched_verbose && spec_info->dump)
4473 fprintf (spec_info->dump, ";;\t\tGenerated recovery block rec%d\n",
4479 /* Create edges: FIRST_BB -> REC; FIRST_BB -> SECOND_BB; REC -> SECOND_BB
4480 and emit necessary jumps. */
4482 sched_create_recovery_edges (basic_block first_bb, basic_block rec,
4483 basic_block second_bb)
4489 /* This is fixing of incoming edge. */
4490 /* ??? Which other flags should be specified? */
4491 if (BB_PARTITION (first_bb) != BB_PARTITION (rec))
4492 /* Partition type is the same, if it is "unpartitioned". */
4493 edge_flags = EDGE_CROSSING;
4497 make_edge (first_bb, rec, edge_flags);
4498 label = block_label (second_bb);
4499 jump = emit_jump_insn_after (gen_jump (label), BB_END (rec));
4500 JUMP_LABEL (jump) = label;
4501 LABEL_NUSES (label)++;
4503 if (BB_PARTITION (second_bb) != BB_PARTITION (rec))
4504 /* Partition type is the same, if it is "unpartitioned". */
4506 /* Rewritten from cfgrtl.c. */
4507 if (flag_reorder_blocks_and_partition
4508 && targetm.have_named_sections)
4510 /* We don't need the same note for the check because
4511 any_condjump_p (check) == true. */
4512 add_reg_note (jump, REG_CROSSING_JUMP, NULL_RTX);
4514 edge_flags = EDGE_CROSSING;
4519 make_single_succ_edge (rec, second_bb, edge_flags);
4520 if (dom_info_available_p (CDI_DOMINATORS))
4521 set_immediate_dominator (CDI_DOMINATORS, rec, first_bb);
4524 /* This function creates recovery code for INSN. If MUTATE_P is nonzero,
4525 INSN is a simple check, that should be converted to branchy one. */
4527 create_check_block_twin (rtx insn, bool mutate_p)
4530 rtx label, check, twin;
4532 sd_iterator_def sd_it;
4534 dep_def _new_dep, *new_dep = &_new_dep;
4537 gcc_assert (ORIG_PAT (insn) != NULL_RTX);
4540 todo_spec = TODO_SPEC (insn);
4543 gcc_assert (IS_SPECULATION_SIMPLE_CHECK_P (insn)
4544 && (TODO_SPEC (insn) & SPECULATIVE) == 0);
4546 todo_spec = CHECK_SPEC (insn);
4549 todo_spec &= SPECULATIVE;
4551 /* Create recovery block. */
4552 if (mutate_p || targetm.sched.needs_block_p (todo_spec))
4554 rec = sched_create_recovery_block (NULL);
4555 label = BB_HEAD (rec);
4559 rec = EXIT_BLOCK_PTR;
4564 check = targetm.sched.gen_spec_check (insn, label, todo_spec);
4566 if (rec != EXIT_BLOCK_PTR)
4568 /* To have mem_reg alive at the beginning of second_bb,
4569 we emit check BEFORE insn, so insn after splitting
4570 insn will be at the beginning of second_bb, which will
4571 provide us with the correct life information. */
4572 check = emit_jump_insn_before (check, insn);
4573 JUMP_LABEL (check) = label;
4574 LABEL_NUSES (label)++;
4577 check = emit_insn_before (check, insn);
4579 /* Extend data structures. */
4580 haifa_init_insn (check);
4582 /* CHECK is being added to current region. Extend ready list. */
4583 gcc_assert (sched_ready_n_insns != -1);
4584 sched_extend_ready_list (sched_ready_n_insns + 1);
4586 if (current_sched_info->add_remove_insn)
4587 current_sched_info->add_remove_insn (insn, 0);
4589 RECOVERY_BLOCK (check) = rec;
4591 if (sched_verbose && spec_info->dump)
4592 fprintf (spec_info->dump, ";;\t\tGenerated check insn : %s\n",
4593 (*current_sched_info->print_insn) (check, 0));
4595 gcc_assert (ORIG_PAT (insn));
4597 /* Initialize TWIN (twin is a duplicate of original instruction
4598 in the recovery block). */
4599 if (rec != EXIT_BLOCK_PTR)
4601 sd_iterator_def sd_it;
4604 FOR_EACH_DEP (insn, SD_LIST_RES_BACK, sd_it, dep)
4605 if ((DEP_STATUS (dep) & DEP_OUTPUT) != 0)
4607 struct _dep _dep2, *dep2 = &_dep2;
4609 init_dep (dep2, DEP_PRO (dep), check, REG_DEP_TRUE);
4611 sd_add_dep (dep2, true);
4614 twin = emit_insn_after (ORIG_PAT (insn), BB_END (rec));
4615 haifa_init_insn (twin);
4617 if (sched_verbose && spec_info->dump)
4618 /* INSN_BB (insn) isn't determined for twin insns yet.
4619 So we can't use current_sched_info->print_insn. */
4620 fprintf (spec_info->dump, ";;\t\tGenerated twin insn : %d/rec%d\n",
4621 INSN_UID (twin), rec->index);
4625 ORIG_PAT (check) = ORIG_PAT (insn);
4626 HAS_INTERNAL_DEP (check) = 1;
4628 /* ??? We probably should change all OUTPUT dependencies to
4632 /* Copy all resolved back dependencies of INSN to TWIN. This will
4633 provide correct value for INSN_TICK (TWIN). */
4634 sd_copy_back_deps (twin, insn, true);
4636 if (rec != EXIT_BLOCK_PTR)
4637 /* In case of branchy check, fix CFG. */
4639 basic_block first_bb, second_bb;
4642 first_bb = BLOCK_FOR_INSN (check);
4643 second_bb = sched_split_block (first_bb, check);
4645 sched_create_recovery_edges (first_bb, rec, second_bb);
4647 sched_init_only_bb (second_bb, first_bb);
4648 sched_init_only_bb (rec, EXIT_BLOCK_PTR);
4650 jump = BB_END (rec);
4651 haifa_init_insn (jump);
4654 /* Move backward dependences from INSN to CHECK and
4655 move forward dependences from INSN to TWIN. */
4657 /* First, create dependencies between INSN's producers and CHECK & TWIN. */
4658 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
4660 rtx pro = DEP_PRO (dep);
4663 /* If BEGIN_DATA: [insn ~~TRUE~~> producer]:
4664 check --TRUE--> producer ??? or ANTI ???
4665 twin --TRUE--> producer
4666 twin --ANTI--> check
4668 If BEGIN_CONTROL: [insn ~~ANTI~~> producer]:
4669 check --ANTI--> producer
4670 twin --ANTI--> producer
4671 twin --ANTI--> check
4673 If BE_IN_SPEC: [insn ~~TRUE~~> producer]:
4674 check ~~TRUE~~> producer
4675 twin ~~TRUE~~> producer
4676 twin --ANTI--> check */
4678 ds = DEP_STATUS (dep);
4680 if (ds & BEGIN_SPEC)
4682 gcc_assert (!mutate_p);
4686 init_dep_1 (new_dep, pro, check, DEP_TYPE (dep), ds);
4687 sd_add_dep (new_dep, false);
4689 if (rec != EXIT_BLOCK_PTR)
4691 DEP_CON (new_dep) = twin;
4692 sd_add_dep (new_dep, false);
4696 /* Second, remove backward dependencies of INSN. */
4697 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
4698 sd_iterator_cond (&sd_it, &dep);)
4700 if ((DEP_STATUS (dep) & BEGIN_SPEC)
4702 /* We can delete this dep because we overcome it with
4703 BEGIN_SPECULATION. */
4704 sd_delete_dep (sd_it);
4706 sd_iterator_next (&sd_it);
4709 /* Future Speculations. Determine what BE_IN speculations will be like. */
4712 /* Fields (DONE_SPEC (x) & BEGIN_SPEC) and CHECK_SPEC (x) are set only
4715 gcc_assert (!DONE_SPEC (insn));
4719 ds_t ts = TODO_SPEC (insn);
4721 DONE_SPEC (insn) = ts & BEGIN_SPEC;
4722 CHECK_SPEC (check) = ts & BEGIN_SPEC;
4724 /* Luckiness of future speculations solely depends upon initial
4725 BEGIN speculation. */
4726 if (ts & BEGIN_DATA)
4727 fs = set_dep_weak (fs, BE_IN_DATA, get_dep_weak (ts, BEGIN_DATA));
4728 if (ts & BEGIN_CONTROL)
4729 fs = set_dep_weak (fs, BE_IN_CONTROL,
4730 get_dep_weak (ts, BEGIN_CONTROL));
4733 CHECK_SPEC (check) = CHECK_SPEC (insn);
4735 /* Future speculations: call the helper. */
4736 process_insn_forw_deps_be_in_spec (insn, twin, fs);
4738 if (rec != EXIT_BLOCK_PTR)
4740 /* Which types of dependencies should we use here is,
4741 generally, machine-dependent question... But, for now,
4746 init_dep (new_dep, insn, check, REG_DEP_TRUE);
4747 sd_add_dep (new_dep, false);
4749 init_dep (new_dep, insn, twin, REG_DEP_OUTPUT);
4750 sd_add_dep (new_dep, false);
4754 if (spec_info->dump)
4755 fprintf (spec_info->dump, ";;\t\tRemoved simple check : %s\n",
4756 (*current_sched_info->print_insn) (insn, 0));
4758 /* Remove all dependencies of the INSN. */
4760 sd_it = sd_iterator_start (insn, (SD_LIST_FORW
4762 | SD_LIST_RES_BACK));
4763 while (sd_iterator_cond (&sd_it, &dep))
4764 sd_delete_dep (sd_it);
4767 /* If former check (INSN) already was moved to the ready (or queue)
4768 list, add new check (CHECK) there too. */
4769 if (QUEUE_INDEX (insn) != QUEUE_NOWHERE)
4772 /* Remove old check from instruction stream and free its
4774 sched_remove_insn (insn);
4777 init_dep (new_dep, check, twin, REG_DEP_ANTI);
4778 sd_add_dep (new_dep, false);
4782 init_dep_1 (new_dep, insn, check, REG_DEP_TRUE, DEP_TRUE | DEP_OUTPUT);
4783 sd_add_dep (new_dep, false);
4787 /* Fix priorities. If MUTATE_P is nonzero, this is not necessary,
4788 because it'll be done later in add_to_speculative_block. */
4790 rtx_vec_t priorities_roots = NULL;
4792 clear_priorities (twin, &priorities_roots);
4793 calc_priorities (priorities_roots);
4794 VEC_free (rtx, heap, priorities_roots);
4798 /* Removes dependency between instructions in the recovery block REC
4799 and usual region instructions. It keeps inner dependences so it
4800 won't be necessary to recompute them. */
4802 fix_recovery_deps (basic_block rec)
4804 rtx note, insn, jump, ready_list = 0;
4805 bitmap_head in_ready;
4808 bitmap_initialize (&in_ready, 0);
4810 /* NOTE - a basic block note. */
4811 note = NEXT_INSN (BB_HEAD (rec));
4812 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
4813 insn = BB_END (rec);
4814 gcc_assert (JUMP_P (insn));
4815 insn = PREV_INSN (insn);
4819 sd_iterator_def sd_it;
4822 for (sd_it = sd_iterator_start (insn, SD_LIST_FORW);
4823 sd_iterator_cond (&sd_it, &dep);)
4825 rtx consumer = DEP_CON (dep);
4827 if (BLOCK_FOR_INSN (consumer) != rec)
4829 sd_delete_dep (sd_it);
4831 if (bitmap_set_bit (&in_ready, INSN_LUID (consumer)))
4832 ready_list = alloc_INSN_LIST (consumer, ready_list);
4836 gcc_assert ((DEP_STATUS (dep) & DEP_TYPES) == DEP_TRUE);
4838 sd_iterator_next (&sd_it);
4842 insn = PREV_INSN (insn);
4844 while (insn != note);
4846 bitmap_clear (&in_ready);
4848 /* Try to add instructions to the ready or queue list. */
4849 for (link = ready_list; link; link = XEXP (link, 1))
4850 try_ready (XEXP (link, 0));
4851 free_INSN_LIST_list (&ready_list);
4853 /* Fixing jump's dependences. */
4854 insn = BB_HEAD (rec);
4855 jump = BB_END (rec);
4857 gcc_assert (LABEL_P (insn));
4858 insn = NEXT_INSN (insn);
4860 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
4861 add_jump_dependencies (insn, jump);
4864 /* Change pattern of INSN to NEW_PAT. */
4866 sched_change_pattern (rtx insn, rtx new_pat)
4870 t = validate_change (insn, &PATTERN (insn), new_pat, 0);
4872 dfa_clear_single_insn_cache (insn);
4875 /* Change pattern of INSN to NEW_PAT. Invalidate cached haifa
4876 instruction data. */
4878 haifa_change_pattern (rtx insn, rtx new_pat)
4880 sched_change_pattern (insn, new_pat);
4882 /* Invalidate INSN_COST, so it'll be recalculated. */
4883 INSN_COST (insn) = -1;
4884 /* Invalidate INSN_TICK, so it'll be recalculated. */
4885 INSN_TICK (insn) = INVALID_TICK;
4888 /* -1 - can't speculate,
4889 0 - for speculation with REQUEST mode it is OK to use
4890 current instruction pattern,
4891 1 - need to change pattern for *NEW_PAT to be speculative. */
4893 sched_speculate_insn (rtx insn, ds_t request, rtx *new_pat)
4895 gcc_assert (current_sched_info->flags & DO_SPECULATION
4896 && (request & SPECULATIVE)
4897 && sched_insn_is_legitimate_for_speculation_p (insn, request));
4899 if ((request & spec_info->mask) != request)
4902 if (request & BE_IN_SPEC
4903 && !(request & BEGIN_SPEC))
4906 return targetm.sched.speculate_insn (insn, request, new_pat);
4910 haifa_speculate_insn (rtx insn, ds_t request, rtx *new_pat)
4912 gcc_assert (sched_deps_info->generate_spec_deps
4913 && !IS_SPECULATION_CHECK_P (insn));
4915 if (HAS_INTERNAL_DEP (insn)
4916 || SCHED_GROUP_P (insn))
4919 return sched_speculate_insn (insn, request, new_pat);
4922 /* Print some information about block BB, which starts with HEAD and
4923 ends with TAIL, before scheduling it.
4924 I is zero, if scheduler is about to start with the fresh ebb. */
4926 dump_new_block_header (int i, basic_block bb, rtx head, rtx tail)
4929 fprintf (sched_dump,
4930 ";; ======================================================\n");
4932 fprintf (sched_dump,
4933 ";; =====================ADVANCING TO=====================\n");
4934 fprintf (sched_dump,
4935 ";; -- basic block %d from %d to %d -- %s reload\n",
4936 bb->index, INSN_UID (head), INSN_UID (tail),
4937 (reload_completed ? "after" : "before"));
4938 fprintf (sched_dump,
4939 ";; ======================================================\n");
4940 fprintf (sched_dump, "\n");
4943 /* Unlink basic block notes and labels and saves them, so they
4944 can be easily restored. We unlink basic block notes in EBB to
4945 provide back-compatibility with the previous code, as target backends
4946 assume, that there'll be only instructions between
4947 current_sched_info->{head and tail}. We restore these notes as soon
4949 FIRST (LAST) is the first (last) basic block in the ebb.
4950 NB: In usual case (FIRST == LAST) nothing is really done. */
4952 unlink_bb_notes (basic_block first, basic_block last)
4954 /* We DON'T unlink basic block notes of the first block in the ebb. */
4958 bb_header = XNEWVEC (rtx, last_basic_block);
4960 /* Make a sentinel. */
4961 if (last->next_bb != EXIT_BLOCK_PTR)
4962 bb_header[last->next_bb->index] = 0;
4964 first = first->next_bb;
4967 rtx prev, label, note, next;
4969 label = BB_HEAD (last);
4970 if (LABEL_P (label))
4971 note = NEXT_INSN (label);
4974 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
4976 prev = PREV_INSN (label);
4977 next = NEXT_INSN (note);
4978 gcc_assert (prev && next);
4980 NEXT_INSN (prev) = next;
4981 PREV_INSN (next) = prev;
4983 bb_header[last->index] = label;
4988 last = last->prev_bb;
4993 /* Restore basic block notes.
4994 FIRST is the first basic block in the ebb. */
4996 restore_bb_notes (basic_block first)
5001 /* We DON'T unlink basic block notes of the first block in the ebb. */
5002 first = first->next_bb;
5003 /* Remember: FIRST is actually a second basic block in the ebb. */
5005 while (first != EXIT_BLOCK_PTR
5006 && bb_header[first->index])
5008 rtx prev, label, note, next;
5010 label = bb_header[first->index];
5011 prev = PREV_INSN (label);
5012 next = NEXT_INSN (prev);
5014 if (LABEL_P (label))
5015 note = NEXT_INSN (label);
5018 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
5020 bb_header[first->index] = 0;
5022 NEXT_INSN (prev) = label;
5023 NEXT_INSN (note) = next;
5024 PREV_INSN (next) = note;
5026 first = first->next_bb;
5034 Fix CFG after both in- and inter-block movement of
5035 control_flow_insn_p JUMP. */
5037 fix_jump_move (rtx jump)
5039 basic_block bb, jump_bb, jump_bb_next;
5041 bb = BLOCK_FOR_INSN (PREV_INSN (jump));
5042 jump_bb = BLOCK_FOR_INSN (jump);
5043 jump_bb_next = jump_bb->next_bb;
5045 gcc_assert (common_sched_info->sched_pass_id == SCHED_EBB_PASS
5046 || IS_SPECULATION_BRANCHY_CHECK_P (jump));
5048 if (!NOTE_INSN_BASIC_BLOCK_P (BB_END (jump_bb_next)))
5049 /* if jump_bb_next is not empty. */
5050 BB_END (jump_bb) = BB_END (jump_bb_next);
5052 if (BB_END (bb) != PREV_INSN (jump))
5053 /* Then there are instruction after jump that should be placed
5055 BB_END (jump_bb_next) = BB_END (bb);
5057 /* Otherwise jump_bb_next is empty. */
5058 BB_END (jump_bb_next) = NEXT_INSN (BB_HEAD (jump_bb_next));
5060 /* To make assertion in move_insn happy. */
5061 BB_END (bb) = PREV_INSN (jump);
5063 update_bb_for_insn (jump_bb_next);
5066 /* Fix CFG after interblock movement of control_flow_insn_p JUMP. */
5068 move_block_after_check (rtx jump)
5070 basic_block bb, jump_bb, jump_bb_next;
5073 bb = BLOCK_FOR_INSN (PREV_INSN (jump));
5074 jump_bb = BLOCK_FOR_INSN (jump);
5075 jump_bb_next = jump_bb->next_bb;
5077 update_bb_for_insn (jump_bb);
5079 gcc_assert (IS_SPECULATION_CHECK_P (jump)
5080 || IS_SPECULATION_CHECK_P (BB_END (jump_bb_next)));
5082 unlink_block (jump_bb_next);
5083 link_block (jump_bb_next, bb);
5087 move_succs (&(jump_bb->succs), bb);
5088 move_succs (&(jump_bb_next->succs), jump_bb);
5089 move_succs (&t, jump_bb_next);
5091 df_mark_solutions_dirty ();
5093 common_sched_info->fix_recovery_cfg
5094 (bb->index, jump_bb->index, jump_bb_next->index);
5097 /* Helper function for move_block_after_check.
5098 This functions attaches edge vector pointed to by SUCCSP to
5101 move_succs (VEC(edge,gc) **succsp, basic_block to)
5106 gcc_assert (to->succs == 0);
5108 to->succs = *succsp;
5110 FOR_EACH_EDGE (e, ei, to->succs)
5116 /* Remove INSN from the instruction stream.
5117 INSN should have any dependencies. */
5119 sched_remove_insn (rtx insn)
5121 sd_finish_insn (insn);
5123 change_queue_index (insn, QUEUE_NOWHERE);
5124 current_sched_info->add_remove_insn (insn, 1);
5128 /* Clear priorities of all instructions, that are forward dependent on INSN.
5129 Store in vector pointed to by ROOTS_PTR insns on which priority () should
5130 be invoked to initialize all cleared priorities. */
5132 clear_priorities (rtx insn, rtx_vec_t *roots_ptr)
5134 sd_iterator_def sd_it;
5136 bool insn_is_root_p = true;
5138 gcc_assert (QUEUE_INDEX (insn) != QUEUE_SCHEDULED);
5140 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
5142 rtx pro = DEP_PRO (dep);
5144 if (INSN_PRIORITY_STATUS (pro) >= 0
5145 && QUEUE_INDEX (insn) != QUEUE_SCHEDULED)
5147 /* If DEP doesn't contribute to priority then INSN itself should
5148 be added to priority roots. */
5149 if (contributes_to_priority_p (dep))
5150 insn_is_root_p = false;
5152 INSN_PRIORITY_STATUS (pro) = -1;
5153 clear_priorities (pro, roots_ptr);
5158 VEC_safe_push (rtx, heap, *roots_ptr, insn);
5161 /* Recompute priorities of instructions, whose priorities might have been
5162 changed. ROOTS is a vector of instructions whose priority computation will
5163 trigger initialization of all cleared priorities. */
5165 calc_priorities (rtx_vec_t roots)
5170 FOR_EACH_VEC_ELT (rtx, roots, i, insn)
5175 /* Add dependences between JUMP and other instructions in the recovery
5176 block. INSN is the first insn the recovery block. */
5178 add_jump_dependencies (rtx insn, rtx jump)
5182 insn = NEXT_INSN (insn);
5186 if (dep_list_size (insn) == 0)
5188 dep_def _new_dep, *new_dep = &_new_dep;
5190 init_dep (new_dep, insn, jump, REG_DEP_ANTI);
5191 sd_add_dep (new_dep, false);
5196 gcc_assert (!sd_lists_empty_p (jump, SD_LIST_BACK));
5199 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
5201 bb_note (basic_block bb)
5205 note = BB_HEAD (bb);
5207 note = NEXT_INSN (note);
5209 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
5213 #ifdef ENABLE_CHECKING
5214 /* Helper function for check_cfg.
5215 Return nonzero, if edge vector pointed to by EL has edge with TYPE in
5218 has_edge_p (VEC(edge,gc) *el, int type)
5223 FOR_EACH_EDGE (e, ei, el)
5224 if (e->flags & type)
5229 /* Search back, starting at INSN, for an insn that is not a
5230 NOTE_INSN_VAR_LOCATION. Don't search beyond HEAD, and return it if
5231 no such insn can be found. */
5233 prev_non_location_insn (rtx insn, rtx head)
5235 while (insn != head && NOTE_P (insn)
5236 && NOTE_KIND (insn) == NOTE_INSN_VAR_LOCATION)
5237 insn = PREV_INSN (insn);
5242 /* Check few properties of CFG between HEAD and TAIL.
5243 If HEAD (TAIL) is NULL check from the beginning (till the end) of the
5244 instruction stream. */
5246 check_cfg (rtx head, rtx tail)
5250 int not_first = 0, not_last;
5253 head = get_insns ();
5255 tail = get_last_insn ();
5256 next_tail = NEXT_INSN (tail);
5260 not_last = head != tail;
5263 gcc_assert (NEXT_INSN (PREV_INSN (head)) == head);
5265 gcc_assert (PREV_INSN (NEXT_INSN (head)) == head);
5268 || (NOTE_INSN_BASIC_BLOCK_P (head)
5270 || (not_first && !LABEL_P (PREV_INSN (head))))))
5272 gcc_assert (bb == 0);
5273 bb = BLOCK_FOR_INSN (head);
5275 gcc_assert (BB_HEAD (bb) == head);
5277 /* This is the case of jump table. See inside_basic_block_p (). */
5278 gcc_assert (LABEL_P (head) && !inside_basic_block_p (head));
5283 gcc_assert (!inside_basic_block_p (head));
5284 head = NEXT_INSN (head);
5288 gcc_assert (inside_basic_block_p (head)
5290 gcc_assert (BLOCK_FOR_INSN (head) == bb);
5294 head = NEXT_INSN (head);
5295 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (head));
5299 if (control_flow_insn_p (head))
5301 gcc_assert (prev_non_location_insn (BB_END (bb), head)
5304 if (any_uncondjump_p (head))
5305 gcc_assert (EDGE_COUNT (bb->succs) == 1
5306 && BARRIER_P (NEXT_INSN (head)));
5307 else if (any_condjump_p (head))
5308 gcc_assert (/* Usual case. */
5309 (EDGE_COUNT (bb->succs) > 1
5310 && !BARRIER_P (NEXT_INSN (head)))
5311 /* Or jump to the next instruction. */
5312 || (EDGE_COUNT (bb->succs) == 1
5313 && (BB_HEAD (EDGE_I (bb->succs, 0)->dest)
5314 == JUMP_LABEL (head))));
5316 if (BB_END (bb) == head)
5318 if (EDGE_COUNT (bb->succs) > 1)
5319 gcc_assert (control_flow_insn_p (prev_non_location_insn
5320 (head, BB_HEAD (bb)))
5321 || has_edge_p (bb->succs, EDGE_COMPLEX));
5325 head = NEXT_INSN (head);
5331 while (head != next_tail);
5333 gcc_assert (bb == 0);
5336 #endif /* ENABLE_CHECKING */
5338 /* Extend per basic block data structures. */
5342 if (sched_scan_info->extend_bb)
5343 sched_scan_info->extend_bb ();
5346 /* Init data for BB. */
5348 init_bb (basic_block bb)
5350 if (sched_scan_info->init_bb)
5351 sched_scan_info->init_bb (bb);
5354 /* Extend per insn data structures. */
5358 if (sched_scan_info->extend_insn)
5359 sched_scan_info->extend_insn ();
5362 /* Init data structures for INSN. */
5364 init_insn (rtx insn)
5366 if (sched_scan_info->init_insn)
5367 sched_scan_info->init_insn (insn);
5370 /* Init all insns in BB. */
5372 init_insns_in_bb (basic_block bb)
5376 FOR_BB_INSNS (bb, insn)
5380 /* A driver function to add a set of basic blocks (BBS),
5381 a single basic block (BB), a set of insns (INSNS) or a single insn (INSN)
5382 to the scheduling region. */
5384 sched_scan (const struct sched_scan_info_def *ssi,
5385 bb_vec_t bbs, basic_block bb, insn_vec_t insns, rtx insn)
5387 sched_scan_info = ssi;
5389 if (bbs != NULL || bb != NULL)
5398 FOR_EACH_VEC_ELT (basic_block, bbs, i, x)
5413 FOR_EACH_VEC_ELT (basic_block, bbs, i, x)
5414 init_insns_in_bb (x);
5418 init_insns_in_bb (bb);
5425 FOR_EACH_VEC_ELT (rtx, insns, i, x)
5434 /* Extend data structures for logical insn UID. */
5436 luids_extend_insn (void)
5438 int new_luids_max_uid = get_max_uid () + 1;
5440 VEC_safe_grow_cleared (int, heap, sched_luids, new_luids_max_uid);
5443 /* Initialize LUID for INSN. */
5445 luids_init_insn (rtx insn)
5447 int i = INSN_P (insn) ? 1 : common_sched_info->luid_for_non_insn (insn);
5452 luid = sched_max_luid;
5453 sched_max_luid += i;
5458 SET_INSN_LUID (insn, luid);
5461 /* Initialize luids for BBS, BB, INSNS and INSN.
5462 The hook common_sched_info->luid_for_non_insn () is used to determine
5463 if notes, labels, etc. need luids. */
5465 sched_init_luids (bb_vec_t bbs, basic_block bb, insn_vec_t insns, rtx insn)
5467 const struct sched_scan_info_def ssi =
5469 NULL, /* extend_bb */
5471 luids_extend_insn, /* extend_insn */
5472 luids_init_insn /* init_insn */
5475 sched_scan (&ssi, bbs, bb, insns, insn);
5480 sched_finish_luids (void)
5482 VEC_free (int, heap, sched_luids);
5486 /* Return logical uid of INSN. Helpful while debugging. */
5488 insn_luid (rtx insn)
5490 return INSN_LUID (insn);
5493 /* Extend per insn data in the target. */
5495 sched_extend_target (void)
5497 if (targetm.sched.h_i_d_extended)
5498 targetm.sched.h_i_d_extended ();
5501 /* Extend global scheduler structures (those, that live across calls to
5502 schedule_block) to include information about just emitted INSN. */
5506 int reserve = (get_max_uid () + 1
5507 - VEC_length (haifa_insn_data_def, h_i_d));
5509 && ! VEC_space (haifa_insn_data_def, h_i_d, reserve))
5511 VEC_safe_grow_cleared (haifa_insn_data_def, heap, h_i_d,
5512 3 * get_max_uid () / 2);
5513 sched_extend_target ();
5517 /* Initialize h_i_d entry of the INSN with default values.
5518 Values, that are not explicitly initialized here, hold zero. */
5520 init_h_i_d (rtx insn)
5522 if (INSN_LUID (insn) > 0)
5524 INSN_COST (insn) = -1;
5525 QUEUE_INDEX (insn) = QUEUE_NOWHERE;
5526 INSN_TICK (insn) = INVALID_TICK;
5527 INTER_TICK (insn) = INVALID_TICK;
5528 TODO_SPEC (insn) = HARD_DEP;
5532 /* Initialize haifa_insn_data for BBS, BB, INSNS and INSN. */
5534 haifa_init_h_i_d (bb_vec_t bbs, basic_block bb, insn_vec_t insns, rtx insn)
5536 const struct sched_scan_info_def ssi =
5538 NULL, /* extend_bb */
5540 extend_h_i_d, /* extend_insn */
5541 init_h_i_d /* init_insn */
5544 sched_scan (&ssi, bbs, bb, insns, insn);
5547 /* Finalize haifa_insn_data. */
5549 haifa_finish_h_i_d (void)
5552 haifa_insn_data_t data;
5553 struct reg_use_data *use, *next;
5555 FOR_EACH_VEC_ELT (haifa_insn_data_def, h_i_d, i, data)
5557 free (data->reg_pressure);
5558 for (use = data->reg_use_list; use != NULL; use = next)
5560 next = use->next_insn_use;
5564 VEC_free (haifa_insn_data_def, heap, h_i_d);
5567 /* Init data for the new insn INSN. */
5569 haifa_init_insn (rtx insn)
5571 gcc_assert (insn != NULL);
5573 sched_init_luids (NULL, NULL, NULL, insn);
5574 sched_extend_target ();
5575 sched_deps_init (false);
5576 haifa_init_h_i_d (NULL, NULL, NULL, insn);
5578 if (adding_bb_to_current_region_p)
5580 sd_init_insn (insn);
5582 /* Extend dependency caches by one element. */
5583 extend_dependency_caches (1, false);
5585 if (sched_pressure_p)
5586 init_insn_reg_pressure_info (insn);
5589 /* Init data for the new basic block BB which comes after AFTER. */
5591 haifa_init_only_bb (basic_block bb, basic_block after)
5593 gcc_assert (bb != NULL);
5597 if (common_sched_info->add_block)
5598 /* This changes only data structures of the front-end. */
5599 common_sched_info->add_block (bb, after);
5602 /* A generic version of sched_split_block (). */
5604 sched_split_block_1 (basic_block first_bb, rtx after)
5608 e = split_block (first_bb, after);
5609 gcc_assert (e->src == first_bb);
5611 /* sched_split_block emits note if *check == BB_END. Probably it
5612 is better to rip that note off. */
5617 /* A generic version of sched_create_empty_bb (). */
5619 sched_create_empty_bb_1 (basic_block after)
5621 return create_empty_bb (after);
5624 /* Insert PAT as an INSN into the schedule and update the necessary data
5625 structures to account for it. */
5627 sched_emit_insn (rtx pat)
5629 rtx insn = emit_insn_before (pat, nonscheduled_insns_begin);
5630 haifa_init_insn (insn);
5632 if (current_sched_info->add_remove_insn)
5633 current_sched_info->add_remove_insn (insn, 0);
5635 (*current_sched_info->begin_schedule_ready) (insn);
5636 VEC_safe_push (rtx, heap, scheduled_insns, insn);
5638 last_scheduled_insn = insn;
5642 /* This function returns a candidate satisfying dispatch constraints from
5646 ready_remove_first_dispatch (struct ready_list *ready)
5649 rtx insn = ready_element (ready, 0);
5651 if (ready->n_ready == 1
5652 || INSN_CODE (insn) < 0
5654 || !active_insn_p (insn)
5655 || targetm.sched.dispatch (insn, FITS_DISPATCH_WINDOW))
5656 return ready_remove_first (ready);
5658 for (i = 1; i < ready->n_ready; i++)
5660 insn = ready_element (ready, i);
5662 if (INSN_CODE (insn) < 0
5664 || !active_insn_p (insn))
5667 if (targetm.sched.dispatch (insn, FITS_DISPATCH_WINDOW))
5669 /* Return ith element of ready. */
5670 insn = ready_remove (ready, i);
5675 if (targetm.sched.dispatch (NULL_RTX, DISPATCH_VIOLATION))
5676 return ready_remove_first (ready);
5678 for (i = 1; i < ready->n_ready; i++)
5680 insn = ready_element (ready, i);
5682 if (INSN_CODE (insn) < 0
5684 || !active_insn_p (insn))
5687 /* Return i-th element of ready. */
5688 if (targetm.sched.dispatch (insn, IS_CMP))
5689 return ready_remove (ready, i);
5692 return ready_remove_first (ready);
5695 /* Get number of ready insn in the ready list. */
5698 number_in_ready (void)
5700 return ready.n_ready;
5703 /* Get number of ready's in the ready list. */
5706 get_ready_element (int i)
5708 return ready_element (&ready, i);
5711 #endif /* INSN_SCHEDULING */