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
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"
134 #include "hard-reg-set.h"
136 #include "function.h"
138 #include "insn-config.h"
139 #include "insn-attr.h"
143 #include "sched-int.h"
151 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
153 #ifdef INSN_SCHEDULING
155 /* issue_rate is the number of insns that can be scheduled in the same
156 machine cycle. It can be defined in the config/mach/mach.h file,
157 otherwise we set it to 1. */
161 /* sched-verbose controls the amount of debugging output the
162 scheduler prints. It is controlled by -fsched-verbose=N:
163 N>0 and no -DSR : the output is directed to stderr.
164 N>=10 will direct the printouts to stderr (regardless of -dSR).
166 N=2: bb's probabilities, detailed ready list info, unit/insn info.
167 N=3: rtl at abort point, control-flow, regions info.
168 N=5: dependences info. */
170 static int sched_verbose_param = 0;
171 int sched_verbose = 0;
173 /* Debugging file. All printouts are sent to dump, which is always set,
174 either to stderr, or to the dump listing file (-dRS). */
175 FILE *sched_dump = 0;
177 /* fix_sched_param() is called from toplev.c upon detection
178 of the -fsched-verbose=N option. */
181 fix_sched_param (const char *param, const char *val)
183 if (!strcmp (param, "verbose"))
184 sched_verbose_param = atoi (val);
186 warning (0, "fix_sched_param: unknown param: %s", param);
189 /* This is a placeholder for the scheduler parameters common
190 to all schedulers. */
191 struct common_sched_info_def *common_sched_info;
193 #define INSN_TICK(INSN) (HID (INSN)->tick)
194 #define INTER_TICK(INSN) (HID (INSN)->inter_tick)
196 /* If INSN_TICK of an instruction is equal to INVALID_TICK,
197 then it should be recalculated from scratch. */
198 #define INVALID_TICK (-(max_insn_queue_index + 1))
199 /* The minimal value of the INSN_TICK of an instruction. */
200 #define MIN_TICK (-max_insn_queue_index)
202 /* Issue points are used to distinguish between instructions in max_issue ().
203 For now, all instructions are equally good. */
204 #define ISSUE_POINTS(INSN) 1
206 /* List of important notes we must keep around. This is a pointer to the
207 last element in the list. */
210 static struct spec_info_def spec_info_var;
211 /* Description of the speculative part of the scheduling.
212 If NULL - no speculation. */
213 spec_info_t spec_info = NULL;
215 /* True, if recovery block was added during scheduling of current block.
216 Used to determine, if we need to fix INSN_TICKs. */
217 static bool haifa_recovery_bb_recently_added_p;
219 /* True, if recovery block was added during this scheduling pass.
220 Used to determine if we should have empty memory pools of dependencies
221 after finishing current region. */
222 bool haifa_recovery_bb_ever_added_p;
224 /* Counters of different types of speculative instructions. */
225 static int nr_begin_data, nr_be_in_data, nr_begin_control, nr_be_in_control;
227 /* Array used in {unlink, restore}_bb_notes. */
228 static rtx *bb_header = 0;
230 /* Basic block after which recovery blocks will be created. */
231 static basic_block before_recovery;
233 /* Basic block just before the EXIT_BLOCK and after recovery, if we have
235 basic_block after_recovery;
237 /* FALSE if we add bb to another region, so we don't need to initialize it. */
238 bool adding_bb_to_current_region_p = true;
242 /* An instruction is ready to be scheduled when all insns preceding it
243 have already been scheduled. It is important to ensure that all
244 insns which use its result will not be executed until its result
245 has been computed. An insn is maintained in one of four structures:
247 (P) the "Pending" set of insns which cannot be scheduled until
248 their dependencies have been satisfied.
249 (Q) the "Queued" set of insns that can be scheduled when sufficient
251 (R) the "Ready" list of unscheduled, uncommitted insns.
252 (S) the "Scheduled" list of insns.
254 Initially, all insns are either "Pending" or "Ready" depending on
255 whether their dependencies are satisfied.
257 Insns move from the "Ready" list to the "Scheduled" list as they
258 are committed to the schedule. As this occurs, the insns in the
259 "Pending" list have their dependencies satisfied and move to either
260 the "Ready" list or the "Queued" set depending on whether
261 sufficient time has passed to make them ready. As time passes,
262 insns move from the "Queued" set to the "Ready" list.
264 The "Pending" list (P) are the insns in the INSN_FORW_DEPS of the
265 unscheduled insns, i.e., those that are ready, queued, and pending.
266 The "Queued" set (Q) is implemented by the variable `insn_queue'.
267 The "Ready" list (R) is implemented by the variables `ready' and
269 The "Scheduled" list (S) is the new insn chain built by this pass.
271 The transition (R->S) is implemented in the scheduling loop in
272 `schedule_block' when the best insn to schedule is chosen.
273 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
274 insns move from the ready list to the scheduled list.
275 The transition (Q->R) is implemented in 'queue_to_insn' as time
276 passes or stalls are introduced. */
278 /* Implement a circular buffer to delay instructions until sufficient
279 time has passed. For the new pipeline description interface,
280 MAX_INSN_QUEUE_INDEX is a power of two minus one which is not less
281 than maximal time of instruction execution computed by genattr.c on
282 the base maximal time of functional unit reservations and getting a
283 result. This is the longest time an insn may be queued. */
285 static rtx *insn_queue;
286 static int q_ptr = 0;
287 static int q_size = 0;
288 #define NEXT_Q(X) (((X)+1) & max_insn_queue_index)
289 #define NEXT_Q_AFTER(X, C) (((X)+C) & max_insn_queue_index)
291 #define QUEUE_SCHEDULED (-3)
292 #define QUEUE_NOWHERE (-2)
293 #define QUEUE_READY (-1)
294 /* QUEUE_SCHEDULED - INSN is scheduled.
295 QUEUE_NOWHERE - INSN isn't scheduled yet and is neither in
297 QUEUE_READY - INSN is in ready list.
298 N >= 0 - INSN queued for X [where NEXT_Q_AFTER (q_ptr, X) == N] cycles. */
300 #define QUEUE_INDEX(INSN) (HID (INSN)->queue_index)
302 /* The following variable value refers for all current and future
303 reservations of the processor units. */
306 /* The following variable value is size of memory representing all
307 current and future reservations of the processor units. */
308 size_t dfa_state_size;
310 /* The following array is used to find the best insn from ready when
311 the automaton pipeline interface is used. */
312 char *ready_try = NULL;
314 /* The ready list. */
315 struct ready_list ready = {NULL, 0, 0, 0, 0};
317 /* The pointer to the ready list (to be removed). */
318 static struct ready_list *readyp = &ready;
320 /* Scheduling clock. */
321 static int clock_var;
323 static int may_trap_exp (const_rtx, int);
325 /* Nonzero iff the address is comprised from at most 1 register. */
326 #define CONST_BASED_ADDRESS_P(x) \
328 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
329 || (GET_CODE (x) == LO_SUM)) \
330 && (CONSTANT_P (XEXP (x, 0)) \
331 || CONSTANT_P (XEXP (x, 1)))))
333 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
334 as found by analyzing insn's expression. */
337 static int haifa_luid_for_non_insn (rtx x);
339 /* Haifa version of sched_info hooks common to all headers. */
340 const struct common_sched_info_def haifa_common_sched_info =
342 NULL, /* fix_recovery_cfg */
343 NULL, /* add_block */
344 NULL, /* estimate_number_of_insns */
345 haifa_luid_for_non_insn, /* luid_for_non_insn */
346 SCHED_PASS_UNKNOWN /* sched_pass_id */
349 const struct sched_scan_info_def *sched_scan_info;
351 /* Mapping from instruction UID to its Logical UID. */
352 VEC (int, heap) *sched_luids = NULL;
354 /* Next LUID to assign to an instruction. */
355 int sched_max_luid = 1;
357 /* Haifa Instruction Data. */
358 VEC (haifa_insn_data_def, heap) *h_i_d = NULL;
360 void (* sched_init_only_bb) (basic_block, basic_block);
362 /* Split block function. Different schedulers might use different functions
363 to handle their internal data consistent. */
364 basic_block (* sched_split_block) (basic_block, rtx);
366 /* Create empty basic block after the specified block. */
367 basic_block (* sched_create_empty_bb) (basic_block);
370 may_trap_exp (const_rtx x, int is_store)
379 if (code == MEM && may_trap_p (x))
386 /* The insn uses memory: a volatile load. */
387 if (MEM_VOLATILE_P (x))
389 /* An exception-free load. */
392 /* A load with 1 base register, to be further checked. */
393 if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))
394 return PFREE_CANDIDATE;
395 /* No info on the load, to be further checked. */
396 return PRISKY_CANDIDATE;
401 int i, insn_class = TRAP_FREE;
403 /* Neither store nor load, check if it may cause a trap. */
406 /* Recursive step: walk the insn... */
407 fmt = GET_RTX_FORMAT (code);
408 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
412 int tmp_class = may_trap_exp (XEXP (x, i), is_store);
413 insn_class = WORST_CLASS (insn_class, tmp_class);
415 else if (fmt[i] == 'E')
418 for (j = 0; j < XVECLEN (x, i); j++)
420 int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);
421 insn_class = WORST_CLASS (insn_class, tmp_class);
422 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
426 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
433 /* Classifies rtx X of an insn for the purpose of verifying that X can be
434 executed speculatively (and consequently the insn can be moved
435 speculatively), by examining X, returning:
436 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
437 TRAP_FREE: non-load insn.
438 IFREE: load from a globally safe location.
439 IRISKY: volatile load.
440 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
441 being either PFREE or PRISKY. */
444 haifa_classify_rtx (const_rtx x)
446 int tmp_class = TRAP_FREE;
447 int insn_class = TRAP_FREE;
450 if (GET_CODE (x) == PARALLEL)
452 int i, len = XVECLEN (x, 0);
454 for (i = len - 1; i >= 0; i--)
456 tmp_class = haifa_classify_rtx (XVECEXP (x, 0, i));
457 insn_class = WORST_CLASS (insn_class, tmp_class);
458 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
468 /* Test if it is a 'store'. */
469 tmp_class = may_trap_exp (XEXP (x, 0), 1);
472 /* Test if it is a store. */
473 tmp_class = may_trap_exp (SET_DEST (x), 1);
474 if (tmp_class == TRAP_RISKY)
476 /* Test if it is a load. */
478 WORST_CLASS (tmp_class,
479 may_trap_exp (SET_SRC (x), 0));
482 tmp_class = haifa_classify_rtx (COND_EXEC_CODE (x));
483 if (tmp_class == TRAP_RISKY)
485 tmp_class = WORST_CLASS (tmp_class,
486 may_trap_exp (COND_EXEC_TEST (x), 0));
489 tmp_class = TRAP_RISKY;
493 insn_class = tmp_class;
500 haifa_classify_insn (const_rtx insn)
502 return haifa_classify_rtx (PATTERN (insn));
505 /* Forward declarations. */
507 static int priority (rtx);
508 static int rank_for_schedule (const void *, const void *);
509 static void swap_sort (rtx *, int);
510 static void queue_insn (rtx, int);
511 static int schedule_insn (rtx);
512 static void adjust_priority (rtx);
513 static void advance_one_cycle (void);
514 static void extend_h_i_d (void);
517 /* Notes handling mechanism:
518 =========================
519 Generally, NOTES are saved before scheduling and restored after scheduling.
520 The scheduler distinguishes between two types of notes:
522 (1) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
523 Before scheduling a region, a pointer to the note is added to the insn
524 that follows or precedes it. (This happens as part of the data dependence
525 computation). After scheduling an insn, the pointer contained in it is
526 used for regenerating the corresponding note (in reemit_notes).
528 (2) All other notes (e.g. INSN_DELETED): Before scheduling a block,
529 these notes are put in a list (in rm_other_notes() and
530 unlink_other_notes ()). After scheduling the block, these notes are
531 inserted at the beginning of the block (in schedule_block()). */
533 static void ready_add (struct ready_list *, rtx, bool);
534 static rtx ready_remove_first (struct ready_list *);
536 static void queue_to_ready (struct ready_list *);
537 static int early_queue_to_ready (state_t, struct ready_list *);
539 static void debug_ready_list (struct ready_list *);
541 /* The following functions are used to implement multi-pass scheduling
542 on the first cycle. */
543 static rtx ready_remove (struct ready_list *, int);
544 static void ready_remove_insn (rtx);
546 static int choose_ready (struct ready_list *, rtx *);
548 static void fix_inter_tick (rtx, rtx);
549 static int fix_tick_ready (rtx);
550 static void change_queue_index (rtx, int);
552 /* The following functions are used to implement scheduling of data/control
553 speculative instructions. */
555 static void extend_h_i_d (void);
556 static void init_h_i_d (rtx);
557 static void generate_recovery_code (rtx);
558 static void process_insn_forw_deps_be_in_spec (rtx, rtx, ds_t);
559 static void begin_speculative_block (rtx);
560 static void add_to_speculative_block (rtx);
561 static void init_before_recovery (basic_block *);
562 static void create_check_block_twin (rtx, bool);
563 static void fix_recovery_deps (basic_block);
564 static void haifa_change_pattern (rtx, rtx);
565 static void dump_new_block_header (int, basic_block, rtx, rtx);
566 static void restore_bb_notes (basic_block);
567 static void fix_jump_move (rtx);
568 static void move_block_after_check (rtx);
569 static void move_succs (VEC(edge,gc) **, basic_block);
570 static void sched_remove_insn (rtx);
571 static void clear_priorities (rtx, rtx_vec_t *);
572 static void calc_priorities (rtx_vec_t);
573 static void add_jump_dependencies (rtx, rtx);
574 #ifdef ENABLE_CHECKING
575 static int has_edge_p (VEC(edge,gc) *, int);
576 static void check_cfg (rtx, rtx);
579 #endif /* INSN_SCHEDULING */
581 /* Point to state used for the current scheduling pass. */
582 struct haifa_sched_info *current_sched_info;
584 #ifndef INSN_SCHEDULING
586 schedule_insns (void)
591 /* Do register pressure sensitive insn scheduling if the flag is set
593 bool sched_pressure_p;
595 /* Map regno -> its cover class. The map defined only when
596 SCHED_PRESSURE_P is true. */
597 enum reg_class *sched_regno_cover_class;
599 /* The current register pressure. Only elements corresponding cover
600 classes are defined. */
601 static int curr_reg_pressure[N_REG_CLASSES];
603 /* Saved value of the previous array. */
604 static int saved_reg_pressure[N_REG_CLASSES];
606 /* Register living at given scheduling point. */
607 static bitmap curr_reg_live;
609 /* Saved value of the previous array. */
610 static bitmap saved_reg_live;
612 /* Registers mentioned in the current region. */
613 static bitmap region_ref_regs;
615 /* Initiate register pressure relative info for scheduling the current
616 region. Currently it is only clearing register mentioned in the
619 sched_init_region_reg_pressure_info (void)
621 bitmap_clear (region_ref_regs);
624 /* Update current register pressure related info after birth (if
625 BIRTH_P) or death of register REGNO. */
627 mark_regno_birth_or_death (int regno, bool birth_p)
629 enum reg_class cover_class;
631 cover_class = sched_regno_cover_class[regno];
632 if (regno >= FIRST_PSEUDO_REGISTER)
634 if (cover_class != NO_REGS)
638 bitmap_set_bit (curr_reg_live, regno);
639 curr_reg_pressure[cover_class]
640 += ira_reg_class_nregs[cover_class][PSEUDO_REGNO_MODE (regno)];
644 bitmap_clear_bit (curr_reg_live, regno);
645 curr_reg_pressure[cover_class]
646 -= ira_reg_class_nregs[cover_class][PSEUDO_REGNO_MODE (regno)];
650 else if (cover_class != NO_REGS
651 && ! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
655 bitmap_set_bit (curr_reg_live, regno);
656 curr_reg_pressure[cover_class]++;
660 bitmap_clear_bit (curr_reg_live, regno);
661 curr_reg_pressure[cover_class]--;
666 /* Initiate current register pressure related info from living
667 registers given by LIVE. */
669 initiate_reg_pressure_info (bitmap live)
675 for (i = 0; i < ira_reg_class_cover_size; i++)
676 curr_reg_pressure[ira_reg_class_cover[i]] = 0;
677 bitmap_clear (curr_reg_live);
678 EXECUTE_IF_SET_IN_BITMAP (live, 0, j, bi)
679 if (current_nr_blocks == 1 || bitmap_bit_p (region_ref_regs, j))
680 mark_regno_birth_or_death (j, true);
683 /* Mark registers in X as mentioned in the current region. */
685 setup_ref_regs (rtx x)
688 const RTX_CODE code = GET_CODE (x);
694 if (regno >= FIRST_PSEUDO_REGISTER)
695 bitmap_set_bit (region_ref_regs, REGNO (x));
697 for (i = hard_regno_nregs[regno][GET_MODE (x)] - 1; i >= 0; i--)
698 bitmap_set_bit (region_ref_regs, regno + i);
701 fmt = GET_RTX_FORMAT (code);
702 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
704 setup_ref_regs (XEXP (x, i));
705 else if (fmt[i] == 'E')
707 for (j = 0; j < XVECLEN (x, i); j++)
708 setup_ref_regs (XVECEXP (x, i, j));
712 /* Initiate current register pressure related info at the start of
715 initiate_bb_reg_pressure_info (basic_block bb)
720 if (current_nr_blocks > 1)
721 FOR_BB_INSNS (bb, insn)
722 if (NONDEBUG_INSN_P (insn))
723 setup_ref_regs (PATTERN (insn));
724 initiate_reg_pressure_info (df_get_live_in (bb));
725 #ifdef EH_RETURN_DATA_REGNO
726 if (bb_has_eh_pred (bb))
729 unsigned int regno = EH_RETURN_DATA_REGNO (i);
731 if (regno == INVALID_REGNUM)
733 if (! bitmap_bit_p (df_get_live_in (bb), regno))
734 mark_regno_birth_or_death (regno, true);
739 /* Save current register pressure related info. */
741 save_reg_pressure (void)
745 for (i = 0; i < ira_reg_class_cover_size; i++)
746 saved_reg_pressure[ira_reg_class_cover[i]]
747 = curr_reg_pressure[ira_reg_class_cover[i]];
748 bitmap_copy (saved_reg_live, curr_reg_live);
751 /* Restore saved register pressure related info. */
753 restore_reg_pressure (void)
757 for (i = 0; i < ira_reg_class_cover_size; i++)
758 curr_reg_pressure[ira_reg_class_cover[i]]
759 = saved_reg_pressure[ira_reg_class_cover[i]];
760 bitmap_copy (curr_reg_live, saved_reg_live);
763 /* Return TRUE if the register is dying after its USE. */
765 dying_use_p (struct reg_use_data *use)
767 struct reg_use_data *next;
769 for (next = use->next_regno_use; next != use; next = next->next_regno_use)
770 if (NONDEBUG_INSN_P (next->insn)
771 && QUEUE_INDEX (next->insn) != QUEUE_SCHEDULED)
776 /* Print info about the current register pressure and its excess for
779 print_curr_reg_pressure (void)
784 fprintf (sched_dump, ";;\t");
785 for (i = 0; i < ira_reg_class_cover_size; i++)
787 cl = ira_reg_class_cover[i];
788 gcc_assert (curr_reg_pressure[cl] >= 0);
789 fprintf (sched_dump, " %s:%d(%d)", reg_class_names[cl],
790 curr_reg_pressure[cl],
791 curr_reg_pressure[cl] - ira_available_class_regs[cl]);
793 fprintf (sched_dump, "\n");
796 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
797 so that insns independent of the last scheduled insn will be preferred
798 over dependent instructions. */
800 static rtx last_scheduled_insn;
802 /* Cached cost of the instruction. Use below function to get cost of the
803 insn. -1 here means that the field is not initialized. */
804 #define INSN_COST(INSN) (HID (INSN)->cost)
806 /* Compute cost of executing INSN.
807 This is the number of cycles between instruction issue and
808 instruction results. */
816 if (recog_memoized (insn) < 0)
819 cost = insn_default_latency (insn);
826 cost = INSN_COST (insn);
830 /* A USE insn, or something else we don't need to
831 understand. We can't pass these directly to
832 result_ready_cost or insn_default_latency because it will
833 trigger a fatal error for unrecognizable insns. */
834 if (recog_memoized (insn) < 0)
836 INSN_COST (insn) = 0;
841 cost = insn_default_latency (insn);
845 INSN_COST (insn) = cost;
852 /* Compute cost of dependence LINK.
853 This is the number of cycles between instruction issue and
855 ??? We also use this function to call recog_memoized on all insns. */
857 dep_cost_1 (dep_t link, dw_t dw)
859 rtx insn = DEP_PRO (link);
860 rtx used = DEP_CON (link);
863 /* A USE insn should never require the value used to be computed.
864 This allows the computation of a function's result and parameter
865 values to overlap the return and call. We don't care about the
866 the dependence cost when only decreasing register pressure. */
867 if (recog_memoized (used) < 0)
870 recog_memoized (insn);
874 enum reg_note dep_type = DEP_TYPE (link);
876 cost = insn_cost (insn);
878 if (INSN_CODE (insn) >= 0)
880 if (dep_type == REG_DEP_ANTI)
882 else if (dep_type == REG_DEP_OUTPUT)
884 cost = (insn_default_latency (insn)
885 - insn_default_latency (used));
889 else if (bypass_p (insn))
890 cost = insn_latency (insn, used);
894 if (targetm.sched.adjust_cost_2)
895 cost = targetm.sched.adjust_cost_2 (used, (int) dep_type, insn, cost,
897 else if (targetm.sched.adjust_cost != NULL)
899 /* This variable is used for backward compatibility with the
901 rtx dep_cost_rtx_link = alloc_INSN_LIST (NULL_RTX, NULL_RTX);
903 /* Make it self-cycled, so that if some tries to walk over this
904 incomplete list he/she will be caught in an endless loop. */
905 XEXP (dep_cost_rtx_link, 1) = dep_cost_rtx_link;
907 /* Targets use only REG_NOTE_KIND of the link. */
908 PUT_REG_NOTE_KIND (dep_cost_rtx_link, DEP_TYPE (link));
910 cost = targetm.sched.adjust_cost (used, dep_cost_rtx_link,
913 free_INSN_LIST_node (dep_cost_rtx_link);
923 /* Compute cost of dependence LINK.
924 This is the number of cycles between instruction issue and
925 instruction results. */
927 dep_cost (dep_t link)
929 return dep_cost_1 (link, 0);
932 /* Use this sel-sched.c friendly function in reorder2 instead of increasing
933 INSN_PRIORITY explicitly. */
935 increase_insn_priority (rtx insn, int amount)
939 /* We're dealing with haifa-sched.c INSN_PRIORITY. */
940 if (INSN_PRIORITY_KNOWN (insn))
941 INSN_PRIORITY (insn) += amount;
945 /* In sel-sched.c INSN_PRIORITY is not kept up to date.
946 Use EXPR_PRIORITY instead. */
947 sel_add_to_insn_priority (insn, amount);
951 /* Return 'true' if DEP should be included in priority calculations. */
953 contributes_to_priority_p (dep_t dep)
955 if (DEBUG_INSN_P (DEP_CON (dep))
956 || DEBUG_INSN_P (DEP_PRO (dep)))
959 /* Critical path is meaningful in block boundaries only. */
960 if (!current_sched_info->contributes_to_priority (DEP_CON (dep),
964 /* If flag COUNT_SPEC_IN_CRITICAL_PATH is set,
965 then speculative instructions will less likely be
966 scheduled. That is because the priority of
967 their producers will increase, and, thus, the
968 producers will more likely be scheduled, thus,
969 resolving the dependence. */
970 if (sched_deps_info->generate_spec_deps
971 && !(spec_info->flags & COUNT_SPEC_IN_CRITICAL_PATH)
972 && (DEP_STATUS (dep) & SPECULATIVE))
978 /* Compute the number of nondebug forward deps of an insn. */
981 dep_list_size (rtx insn)
983 sd_iterator_def sd_it;
985 int dbgcount = 0, nodbgcount = 0;
987 if (!MAY_HAVE_DEBUG_INSNS)
988 return sd_lists_size (insn, SD_LIST_FORW);
990 FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
992 if (DEBUG_INSN_P (DEP_CON (dep)))
994 else if (!DEBUG_INSN_P (DEP_PRO (dep)))
998 gcc_assert (dbgcount + nodbgcount == sd_lists_size (insn, SD_LIST_FORW));
1003 /* Compute the priority number for INSN. */
1007 if (! INSN_P (insn))
1010 /* We should not be interested in priority of an already scheduled insn. */
1011 gcc_assert (QUEUE_INDEX (insn) != QUEUE_SCHEDULED);
1013 if (!INSN_PRIORITY_KNOWN (insn))
1015 int this_priority = -1;
1017 if (dep_list_size (insn) == 0)
1018 /* ??? We should set INSN_PRIORITY to insn_cost when and insn has
1019 some forward deps but all of them are ignored by
1020 contributes_to_priority hook. At the moment we set priority of
1022 this_priority = insn_cost (insn);
1025 rtx prev_first, twin;
1028 /* For recovery check instructions we calculate priority slightly
1029 different than that of normal instructions. Instead of walking
1030 through INSN_FORW_DEPS (check) list, we walk through
1031 INSN_FORW_DEPS list of each instruction in the corresponding
1034 /* Selective scheduling does not define RECOVERY_BLOCK macro. */
1035 rec = sel_sched_p () ? NULL : RECOVERY_BLOCK (insn);
1036 if (!rec || rec == EXIT_BLOCK_PTR)
1038 prev_first = PREV_INSN (insn);
1043 prev_first = NEXT_INSN (BB_HEAD (rec));
1044 twin = PREV_INSN (BB_END (rec));
1049 sd_iterator_def sd_it;
1052 FOR_EACH_DEP (twin, SD_LIST_FORW, sd_it, dep)
1057 next = DEP_CON (dep);
1059 if (BLOCK_FOR_INSN (next) != rec)
1063 if (!contributes_to_priority_p (dep))
1067 cost = dep_cost (dep);
1070 struct _dep _dep1, *dep1 = &_dep1;
1072 init_dep (dep1, insn, next, REG_DEP_ANTI);
1074 cost = dep_cost (dep1);
1077 next_priority = cost + priority (next);
1079 if (next_priority > this_priority)
1080 this_priority = next_priority;
1084 twin = PREV_INSN (twin);
1086 while (twin != prev_first);
1089 if (this_priority < 0)
1091 gcc_assert (this_priority == -1);
1093 this_priority = insn_cost (insn);
1096 INSN_PRIORITY (insn) = this_priority;
1097 INSN_PRIORITY_STATUS (insn) = 1;
1100 return INSN_PRIORITY (insn);
1103 /* Macros and functions for keeping the priority queue sorted, and
1104 dealing with queuing and dequeuing of instructions. */
1106 #define SCHED_SORT(READY, N_READY) \
1107 do { if ((N_READY) == 2) \
1108 swap_sort (READY, N_READY); \
1109 else if ((N_READY) > 2) \
1110 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
1113 /* Setup info about the current register pressure impact of scheduling
1114 INSN at the current scheduling point. */
1116 setup_insn_reg_pressure_info (rtx insn)
1118 int i, change, before, after, hard_regno;
1119 int excess_cost_change;
1120 enum machine_mode mode;
1122 struct reg_pressure_data *pressure_info;
1123 int *max_reg_pressure;
1124 struct reg_use_data *use;
1125 static int death[N_REG_CLASSES];
1127 excess_cost_change = 0;
1128 for (i = 0; i < ira_reg_class_cover_size; i++)
1129 death[ira_reg_class_cover[i]] = 0;
1130 for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
1131 if (dying_use_p (use))
1133 cl = sched_regno_cover_class[use->regno];
1134 if (use->regno < FIRST_PSEUDO_REGISTER)
1137 death[cl] += ira_reg_class_nregs[cl][PSEUDO_REGNO_MODE (use->regno)];
1139 pressure_info = INSN_REG_PRESSURE (insn);
1140 max_reg_pressure = INSN_MAX_REG_PRESSURE (insn);
1141 gcc_assert (pressure_info != NULL && max_reg_pressure != NULL);
1142 for (i = 0; i < ira_reg_class_cover_size; i++)
1144 cl = ira_reg_class_cover[i];
1145 gcc_assert (curr_reg_pressure[cl] >= 0);
1146 change = (int) pressure_info[i].set_increase - death[cl];
1147 before = MAX (0, max_reg_pressure[i] - ira_available_class_regs[cl]);
1148 after = MAX (0, max_reg_pressure[i] + change
1149 - ira_available_class_regs[cl]);
1150 hard_regno = ira_class_hard_regs[cl][0];
1151 gcc_assert (hard_regno >= 0);
1152 mode = reg_raw_mode[hard_regno];
1153 excess_cost_change += ((after - before)
1154 * (ira_memory_move_cost[mode][cl][0]
1155 + ira_memory_move_cost[mode][cl][1]));
1157 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insn) = excess_cost_change;
1160 /* Returns a positive value if x is preferred; returns a negative value if
1161 y is preferred. Should never return 0, since that will make the sort
1165 rank_for_schedule (const void *x, const void *y)
1167 rtx tmp = *(const rtx *) y;
1168 rtx tmp2 = *(const rtx *) x;
1170 int tmp_class, tmp2_class;
1171 int val, priority_val, info_val;
1173 if (MAY_HAVE_DEBUG_INSNS)
1175 /* Schedule debug insns as early as possible. */
1176 if (DEBUG_INSN_P (tmp) && !DEBUG_INSN_P (tmp2))
1178 else if (DEBUG_INSN_P (tmp2))
1182 /* The insn in a schedule group should be issued the first. */
1183 if (flag_sched_group_heuristic &&
1184 SCHED_GROUP_P (tmp) != SCHED_GROUP_P (tmp2))
1185 return SCHED_GROUP_P (tmp2) ? 1 : -1;
1187 /* Make sure that priority of TMP and TMP2 are initialized. */
1188 gcc_assert (INSN_PRIORITY_KNOWN (tmp) && INSN_PRIORITY_KNOWN (tmp2));
1190 if (sched_pressure_p)
1194 /* Prefer insn whose scheduling results in the smallest register
1196 if ((diff = (INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp)
1197 + (INSN_TICK (tmp) > clock_var
1198 ? INSN_TICK (tmp) - clock_var : 0)
1199 - INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp2)
1200 - (INSN_TICK (tmp2) > clock_var
1201 ? INSN_TICK (tmp2) - clock_var : 0))) != 0)
1206 if (sched_pressure_p
1207 && (INSN_TICK (tmp2) > clock_var || INSN_TICK (tmp) > clock_var))
1209 if (INSN_TICK (tmp) <= clock_var)
1211 else if (INSN_TICK (tmp2) <= clock_var)
1214 return INSN_TICK (tmp) - INSN_TICK (tmp2);
1216 /* Prefer insn with higher priority. */
1217 priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
1219 if (flag_sched_critical_path_heuristic && priority_val)
1220 return priority_val;
1222 /* Prefer speculative insn with greater dependencies weakness. */
1223 if (flag_sched_spec_insn_heuristic && spec_info)
1229 ds1 = TODO_SPEC (tmp) & SPECULATIVE;
1231 dw1 = ds_weak (ds1);
1235 ds2 = TODO_SPEC (tmp2) & SPECULATIVE;
1237 dw2 = ds_weak (ds2);
1242 if (dw > (NO_DEP_WEAK / 8) || dw < -(NO_DEP_WEAK / 8))
1246 info_val = (*current_sched_info->rank) (tmp, tmp2);
1247 if(flag_sched_rank_heuristic && info_val)
1250 if (flag_sched_last_insn_heuristic)
1252 last = last_scheduled_insn;
1254 if (DEBUG_INSN_P (last) && last != current_sched_info->prev_head)
1256 last = PREV_INSN (last);
1257 while (!NONDEBUG_INSN_P (last)
1258 && last != current_sched_info->prev_head);
1261 /* Compare insns based on their relation to the last scheduled
1263 if (flag_sched_last_insn_heuristic && NONDEBUG_INSN_P (last))
1268 /* Classify the instructions into three classes:
1269 1) Data dependent on last schedule insn.
1270 2) Anti/Output dependent on last scheduled insn.
1271 3) Independent of last scheduled insn, or has latency of one.
1272 Choose the insn from the highest numbered class if different. */
1273 dep1 = sd_find_dep_between (last, tmp, true);
1275 if (dep1 == NULL || dep_cost (dep1) == 1)
1277 else if (/* Data dependence. */
1278 DEP_TYPE (dep1) == REG_DEP_TRUE)
1283 dep2 = sd_find_dep_between (last, tmp2, true);
1285 if (dep2 == NULL || dep_cost (dep2) == 1)
1287 else if (/* Data dependence. */
1288 DEP_TYPE (dep2) == REG_DEP_TRUE)
1293 if ((val = tmp2_class - tmp_class))
1297 /* Prefer the insn which has more later insns that depend on it.
1298 This gives the scheduler more freedom when scheduling later
1299 instructions at the expense of added register pressure. */
1301 val = (dep_list_size (tmp2) - dep_list_size (tmp));
1303 if (flag_sched_dep_count_heuristic && val != 0)
1306 /* If insns are equally good, sort by INSN_LUID (original insn order),
1307 so that we make the sort stable. This minimizes instruction movement,
1308 thus minimizing sched's effect on debugging and cross-jumping. */
1309 return INSN_LUID (tmp) - INSN_LUID (tmp2);
1312 /* Resort the array A in which only element at index N may be out of order. */
1314 HAIFA_INLINE static void
1315 swap_sort (rtx *a, int n)
1317 rtx insn = a[n - 1];
1320 while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0)
1328 /* Add INSN to the insn queue so that it can be executed at least
1329 N_CYCLES after the currently executing insn. Preserve insns
1330 chain for debugging purposes. */
1332 HAIFA_INLINE static void
1333 queue_insn (rtx insn, int n_cycles)
1335 int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
1336 rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]);
1338 gcc_assert (n_cycles <= max_insn_queue_index);
1339 gcc_assert (!DEBUG_INSN_P (insn));
1341 insn_queue[next_q] = link;
1344 if (sched_verbose >= 2)
1346 fprintf (sched_dump, ";;\t\tReady-->Q: insn %s: ",
1347 (*current_sched_info->print_insn) (insn, 0));
1349 fprintf (sched_dump, "queued for %d cycles.\n", n_cycles);
1352 QUEUE_INDEX (insn) = next_q;
1355 /* Remove INSN from queue. */
1357 queue_remove (rtx insn)
1359 gcc_assert (QUEUE_INDEX (insn) >= 0);
1360 remove_free_INSN_LIST_elem (insn, &insn_queue[QUEUE_INDEX (insn)]);
1362 QUEUE_INDEX (insn) = QUEUE_NOWHERE;
1365 /* Return a pointer to the bottom of the ready list, i.e. the insn
1366 with the lowest priority. */
1369 ready_lastpos (struct ready_list *ready)
1371 gcc_assert (ready->n_ready >= 1);
1372 return ready->vec + ready->first - ready->n_ready + 1;
1375 /* Add an element INSN to the ready list so that it ends up with the
1376 lowest/highest priority depending on FIRST_P. */
1378 HAIFA_INLINE static void
1379 ready_add (struct ready_list *ready, rtx insn, bool first_p)
1383 if (ready->first == ready->n_ready)
1385 memmove (ready->vec + ready->veclen - ready->n_ready,
1386 ready_lastpos (ready),
1387 ready->n_ready * sizeof (rtx));
1388 ready->first = ready->veclen - 1;
1390 ready->vec[ready->first - ready->n_ready] = insn;
1394 if (ready->first == ready->veclen - 1)
1397 /* ready_lastpos() fails when called with (ready->n_ready == 0). */
1398 memmove (ready->vec + ready->veclen - ready->n_ready - 1,
1399 ready_lastpos (ready),
1400 ready->n_ready * sizeof (rtx));
1401 ready->first = ready->veclen - 2;
1403 ready->vec[++(ready->first)] = insn;
1407 if (DEBUG_INSN_P (insn))
1410 gcc_assert (QUEUE_INDEX (insn) != QUEUE_READY);
1411 QUEUE_INDEX (insn) = QUEUE_READY;
1414 /* Remove the element with the highest priority from the ready list and
1417 HAIFA_INLINE static rtx
1418 ready_remove_first (struct ready_list *ready)
1422 gcc_assert (ready->n_ready);
1423 t = ready->vec[ready->first--];
1425 if (DEBUG_INSN_P (t))
1427 /* If the queue becomes empty, reset it. */
1428 if (ready->n_ready == 0)
1429 ready->first = ready->veclen - 1;
1431 gcc_assert (QUEUE_INDEX (t) == QUEUE_READY);
1432 QUEUE_INDEX (t) = QUEUE_NOWHERE;
1437 /* The following code implements multi-pass scheduling for the first
1438 cycle. In other words, we will try to choose ready insn which
1439 permits to start maximum number of insns on the same cycle. */
1441 /* Return a pointer to the element INDEX from the ready. INDEX for
1442 insn with the highest priority is 0, and the lowest priority has
1446 ready_element (struct ready_list *ready, int index)
1448 gcc_assert (ready->n_ready && index < ready->n_ready);
1450 return ready->vec[ready->first - index];
1453 /* Remove the element INDEX from the ready list and return it. INDEX
1454 for insn with the highest priority is 0, and the lowest priority
1457 HAIFA_INLINE static rtx
1458 ready_remove (struct ready_list *ready, int index)
1464 return ready_remove_first (ready);
1465 gcc_assert (ready->n_ready && index < ready->n_ready);
1466 t = ready->vec[ready->first - index];
1468 if (DEBUG_INSN_P (t))
1470 for (i = index; i < ready->n_ready; i++)
1471 ready->vec[ready->first - i] = ready->vec[ready->first - i - 1];
1472 QUEUE_INDEX (t) = QUEUE_NOWHERE;
1476 /* Remove INSN from the ready list. */
1478 ready_remove_insn (rtx insn)
1482 for (i = 0; i < readyp->n_ready; i++)
1483 if (ready_element (readyp, i) == insn)
1485 ready_remove (readyp, i);
1491 /* Sort the ready list READY by ascending priority, using the SCHED_SORT
1495 ready_sort (struct ready_list *ready)
1498 rtx *first = ready_lastpos (ready);
1500 if (sched_pressure_p)
1502 for (i = 0; i < ready->n_ready; i++)
1503 setup_insn_reg_pressure_info (first[i]);
1505 SCHED_SORT (first, ready->n_ready);
1508 /* PREV is an insn that is ready to execute. Adjust its priority if that
1509 will help shorten or lengthen register lifetimes as appropriate. Also
1510 provide a hook for the target to tweak itself. */
1512 HAIFA_INLINE static void
1513 adjust_priority (rtx prev)
1515 /* ??? There used to be code here to try and estimate how an insn
1516 affected register lifetimes, but it did it by looking at REG_DEAD
1517 notes, which we removed in schedule_region. Nor did it try to
1518 take into account register pressure or anything useful like that.
1520 Revisit when we have a machine model to work with and not before. */
1522 if (targetm.sched.adjust_priority)
1523 INSN_PRIORITY (prev) =
1524 targetm.sched.adjust_priority (prev, INSN_PRIORITY (prev));
1527 /* Advance DFA state STATE on one cycle. */
1529 advance_state (state_t state)
1531 if (targetm.sched.dfa_pre_advance_cycle)
1532 targetm.sched.dfa_pre_advance_cycle ();
1534 if (targetm.sched.dfa_pre_cycle_insn)
1535 state_transition (state,
1536 targetm.sched.dfa_pre_cycle_insn ());
1538 state_transition (state, NULL);
1540 if (targetm.sched.dfa_post_cycle_insn)
1541 state_transition (state,
1542 targetm.sched.dfa_post_cycle_insn ());
1544 if (targetm.sched.dfa_post_advance_cycle)
1545 targetm.sched.dfa_post_advance_cycle ();
1548 /* Advance time on one cycle. */
1549 HAIFA_INLINE static void
1550 advance_one_cycle (void)
1552 advance_state (curr_state);
1553 if (sched_verbose >= 6)
1554 fprintf (sched_dump, ";;\tAdvanced a state.\n");
1557 /* Clock at which the previous instruction was issued. */
1558 static int last_clock_var;
1560 /* Update register pressure after scheduling INSN. */
1562 update_register_pressure (rtx insn)
1564 struct reg_use_data *use;
1565 struct reg_set_data *set;
1567 for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
1568 if (dying_use_p (use) && bitmap_bit_p (curr_reg_live, use->regno))
1569 mark_regno_birth_or_death (use->regno, false);
1570 for (set = INSN_REG_SET_LIST (insn); set != NULL; set = set->next_insn_set)
1571 mark_regno_birth_or_death (set->regno, true);
1574 /* Set up or update (if UPDATE_P) max register pressure (see its
1575 meaning in sched-int.h::_haifa_insn_data) for all current BB insns
1576 after insn AFTER. */
1578 setup_insn_max_reg_pressure (rtx after, bool update_p)
1583 static int max_reg_pressure[N_REG_CLASSES];
1585 save_reg_pressure ();
1586 for (i = 0; i < ira_reg_class_cover_size; i++)
1587 max_reg_pressure[ira_reg_class_cover[i]]
1588 = curr_reg_pressure[ira_reg_class_cover[i]];
1589 for (insn = NEXT_INSN (after);
1590 insn != NULL_RTX && ! BARRIER_P (insn)
1591 && BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (after);
1592 insn = NEXT_INSN (insn))
1593 if (NONDEBUG_INSN_P (insn))
1596 for (i = 0; i < ira_reg_class_cover_size; i++)
1598 p = max_reg_pressure[ira_reg_class_cover[i]];
1599 if (INSN_MAX_REG_PRESSURE (insn)[i] != p)
1602 INSN_MAX_REG_PRESSURE (insn)[i]
1603 = max_reg_pressure[ira_reg_class_cover[i]];
1606 if (update_p && eq_p)
1608 update_register_pressure (insn);
1609 for (i = 0; i < ira_reg_class_cover_size; i++)
1610 if (max_reg_pressure[ira_reg_class_cover[i]]
1611 < curr_reg_pressure[ira_reg_class_cover[i]])
1612 max_reg_pressure[ira_reg_class_cover[i]]
1613 = curr_reg_pressure[ira_reg_class_cover[i]];
1615 restore_reg_pressure ();
1618 /* Update the current register pressure after scheduling INSN. Update
1619 also max register pressure for unscheduled insns of the current
1622 update_reg_and_insn_max_reg_pressure (rtx insn)
1625 int before[N_REG_CLASSES];
1627 for (i = 0; i < ira_reg_class_cover_size; i++)
1628 before[i] = curr_reg_pressure[ira_reg_class_cover[i]];
1629 update_register_pressure (insn);
1630 for (i = 0; i < ira_reg_class_cover_size; i++)
1631 if (curr_reg_pressure[ira_reg_class_cover[i]] != before[i])
1633 if (i < ira_reg_class_cover_size)
1634 setup_insn_max_reg_pressure (insn, true);
1637 /* Set up register pressure at the beginning of basic block BB whose
1638 insns starting after insn AFTER. Set up also max register pressure
1639 for all insns of the basic block. */
1641 sched_setup_bb_reg_pressure_info (basic_block bb, rtx after)
1643 gcc_assert (sched_pressure_p);
1644 initiate_bb_reg_pressure_info (bb);
1645 setup_insn_max_reg_pressure (after, false);
1648 /* INSN is the "currently executing insn". Launch each insn which was
1649 waiting on INSN. READY is the ready list which contains the insns
1650 that are ready to fire. CLOCK is the current cycle. The function
1651 returns necessary cycle advance after issuing the insn (it is not
1652 zero for insns in a schedule group). */
1655 schedule_insn (rtx insn)
1657 sd_iterator_def sd_it;
1662 if (sched_verbose >= 1)
1664 struct reg_pressure_data *pressure_info;
1667 print_insn (buf, insn, 0);
1669 fprintf (sched_dump, ";;\t%3i--> %-40s:", clock_var, buf);
1671 if (recog_memoized (insn) < 0)
1672 fprintf (sched_dump, "nothing");
1674 print_reservation (sched_dump, insn);
1675 pressure_info = INSN_REG_PRESSURE (insn);
1676 if (pressure_info != NULL)
1678 fputc (':', sched_dump);
1679 for (i = 0; i < ira_reg_class_cover_size; i++)
1680 fprintf (sched_dump, "%s%+d(%d)",
1681 reg_class_names[ira_reg_class_cover[i]],
1682 pressure_info[i].set_increase, pressure_info[i].change);
1684 fputc ('\n', sched_dump);
1687 if (sched_pressure_p)
1688 update_reg_and_insn_max_reg_pressure (insn);
1690 /* Scheduling instruction should have all its dependencies resolved and
1691 should have been removed from the ready list. */
1692 gcc_assert (sd_lists_empty_p (insn, SD_LIST_BACK));
1694 /* Reset debug insns invalidated by moving this insn. */
1695 if (MAY_HAVE_DEBUG_INSNS && !DEBUG_INSN_P (insn))
1696 for (sd_it = sd_iterator_start (insn, SD_LIST_BACK);
1697 sd_iterator_cond (&sd_it, &dep);)
1699 rtx dbg = DEP_PRO (dep);
1700 struct reg_use_data *use, *next;
1702 gcc_assert (DEBUG_INSN_P (dbg));
1704 if (sched_verbose >= 6)
1705 fprintf (sched_dump, ";;\t\tresetting: debug insn %d\n",
1708 /* ??? Rather than resetting the debug insn, we might be able
1709 to emit a debug temp before the just-scheduled insn, but
1710 this would involve checking that the expression at the
1711 point of the debug insn is equivalent to the expression
1712 before the just-scheduled insn. They might not be: the
1713 expression in the debug insn may depend on other insns not
1714 yet scheduled that set MEMs, REGs or even other debug
1715 insns. It's not clear that attempting to preserve debug
1716 information in these cases is worth the effort, given how
1717 uncommon these resets are and the likelihood that the debug
1718 temps introduced won't survive the schedule change. */
1719 INSN_VAR_LOCATION_LOC (dbg) = gen_rtx_UNKNOWN_VAR_LOC ();
1720 df_insn_rescan (dbg);
1722 /* Unknown location doesn't use any registers. */
1723 for (use = INSN_REG_USE_LIST (dbg); use != NULL; use = next)
1725 struct reg_use_data *prev = use;
1727 /* Remove use from the cyclic next_regno_use chain first. */
1728 while (prev->next_regno_use != use)
1729 prev = prev->next_regno_use;
1730 prev->next_regno_use = use->next_regno_use;
1731 next = use->next_insn_use;
1734 INSN_REG_USE_LIST (dbg) = NULL;
1736 /* We delete rather than resolve these deps, otherwise we
1737 crash in sched_free_deps(), because forward deps are
1738 expected to be released before backward deps. */
1739 sd_delete_dep (sd_it);
1742 gcc_assert (QUEUE_INDEX (insn) == QUEUE_NOWHERE);
1743 QUEUE_INDEX (insn) = QUEUE_SCHEDULED;
1745 gcc_assert (INSN_TICK (insn) >= MIN_TICK);
1746 if (INSN_TICK (insn) > clock_var)
1747 /* INSN has been prematurely moved from the queue to the ready list.
1748 This is possible only if following flag is set. */
1749 gcc_assert (flag_sched_stalled_insns);
1751 /* ??? Probably, if INSN is scheduled prematurely, we should leave
1752 INSN_TICK untouched. This is a machine-dependent issue, actually. */
1753 INSN_TICK (insn) = clock_var;
1755 /* Update dependent instructions. */
1756 for (sd_it = sd_iterator_start (insn, SD_LIST_FORW);
1757 sd_iterator_cond (&sd_it, &dep);)
1759 rtx next = DEP_CON (dep);
1761 /* Resolve the dependence between INSN and NEXT.
1762 sd_resolve_dep () moves current dep to another list thus
1763 advancing the iterator. */
1764 sd_resolve_dep (sd_it);
1766 /* Don't bother trying to mark next as ready if insn is a debug
1767 insn. If insn is the last hard dependency, it will have
1768 already been discounted. */
1769 if (DEBUG_INSN_P (insn) && !DEBUG_INSN_P (next))
1772 if (!IS_SPECULATION_BRANCHY_CHECK_P (insn))
1776 effective_cost = try_ready (next);
1778 if (effective_cost >= 0
1779 && SCHED_GROUP_P (next)
1780 && advance < effective_cost)
1781 advance = effective_cost;
1784 /* Check always has only one forward dependence (to the first insn in
1785 the recovery block), therefore, this will be executed only once. */
1787 gcc_assert (sd_lists_empty_p (insn, SD_LIST_FORW));
1788 fix_recovery_deps (RECOVERY_BLOCK (insn));
1792 /* This is the place where scheduler doesn't *basically* need backward and
1793 forward dependencies for INSN anymore. Nevertheless they are used in
1794 heuristics in rank_for_schedule (), early_queue_to_ready () and in
1795 some targets (e.g. rs6000). Thus the earliest place where we *can*
1796 remove dependencies is after targetm.sched.md_finish () call in
1797 schedule_block (). But, on the other side, the safest place to remove
1798 dependencies is when we are finishing scheduling entire region. As we
1799 don't generate [many] dependencies during scheduling itself, we won't
1800 need memory until beginning of next region.
1801 Bottom line: Dependencies are removed for all insns in the end of
1802 scheduling the region. */
1804 /* Annotate the instruction with issue information -- TImode
1805 indicates that the instruction is expected not to be able
1806 to issue on the same cycle as the previous insn. A machine
1807 may use this information to decide how the instruction should
1810 && GET_CODE (PATTERN (insn)) != USE
1811 && GET_CODE (PATTERN (insn)) != CLOBBER
1812 && !DEBUG_INSN_P (insn))
1814 if (reload_completed)
1815 PUT_MODE (insn, clock_var > last_clock_var ? TImode : VOIDmode);
1816 last_clock_var = clock_var;
1822 /* Functions for handling of notes. */
1824 /* Add note list that ends on FROM_END to the end of TO_ENDP. */
1826 concat_note_lists (rtx from_end, rtx *to_endp)
1830 /* It's easy when have nothing to concat. */
1831 if (from_end == NULL)
1834 /* It's also easy when destination is empty. */
1835 if (*to_endp == NULL)
1837 *to_endp = from_end;
1841 from_start = from_end;
1842 while (PREV_INSN (from_start) != NULL)
1843 from_start = PREV_INSN (from_start);
1845 PREV_INSN (from_start) = *to_endp;
1846 NEXT_INSN (*to_endp) = from_start;
1847 *to_endp = from_end;
1850 /* Delete notes between HEAD and TAIL and put them in the chain
1851 of notes ended by NOTE_LIST. */
1853 remove_notes (rtx head, rtx tail)
1855 rtx next_tail, insn, next;
1858 if (head == tail && !INSN_P (head))
1861 next_tail = NEXT_INSN (tail);
1862 for (insn = head; insn != next_tail; insn = next)
1864 next = NEXT_INSN (insn);
1868 switch (NOTE_KIND (insn))
1870 case NOTE_INSN_BASIC_BLOCK:
1873 case NOTE_INSN_EPILOGUE_BEG:
1877 add_reg_note (next, REG_SAVE_NOTE,
1878 GEN_INT (NOTE_INSN_EPILOGUE_BEG));
1886 /* Add the note to list that ends at NOTE_LIST. */
1887 PREV_INSN (insn) = note_list;
1888 NEXT_INSN (insn) = NULL_RTX;
1890 NEXT_INSN (note_list) = insn;
1895 gcc_assert ((sel_sched_p () || insn != tail) && insn != head);
1900 /* Return the head and tail pointers of ebb starting at BEG and ending
1903 get_ebb_head_tail (basic_block beg, basic_block end, rtx *headp, rtx *tailp)
1905 rtx beg_head = BB_HEAD (beg);
1906 rtx beg_tail = BB_END (beg);
1907 rtx end_head = BB_HEAD (end);
1908 rtx end_tail = BB_END (end);
1910 /* Don't include any notes or labels at the beginning of the BEG
1911 basic block, or notes at the end of the END basic blocks. */
1913 if (LABEL_P (beg_head))
1914 beg_head = NEXT_INSN (beg_head);
1916 while (beg_head != beg_tail)
1917 if (NOTE_P (beg_head) || BOUNDARY_DEBUG_INSN_P (beg_head))
1918 beg_head = NEXT_INSN (beg_head);
1925 end_head = beg_head;
1926 else if (LABEL_P (end_head))
1927 end_head = NEXT_INSN (end_head);
1929 while (end_head != end_tail)
1930 if (NOTE_P (end_tail) || BOUNDARY_DEBUG_INSN_P (end_tail))
1931 end_tail = PREV_INSN (end_tail);
1938 /* Return nonzero if there are no real insns in the range [ HEAD, TAIL ]. */
1941 no_real_insns_p (const_rtx head, const_rtx tail)
1943 while (head != NEXT_INSN (tail))
1945 if (!NOTE_P (head) && !LABEL_P (head)
1946 && !BOUNDARY_DEBUG_INSN_P (head))
1948 head = NEXT_INSN (head);
1953 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
1954 previously found among the insns. Insert them just before HEAD. */
1956 restore_other_notes (rtx head, basic_block head_bb)
1960 rtx note_head = note_list;
1963 head_bb = BLOCK_FOR_INSN (head);
1965 head = NEXT_INSN (bb_note (head_bb));
1967 while (PREV_INSN (note_head))
1969 set_block_for_insn (note_head, head_bb);
1970 note_head = PREV_INSN (note_head);
1972 /* In the above cycle we've missed this note. */
1973 set_block_for_insn (note_head, head_bb);
1975 PREV_INSN (note_head) = PREV_INSN (head);
1976 NEXT_INSN (PREV_INSN (head)) = note_head;
1977 PREV_INSN (head) = note_list;
1978 NEXT_INSN (note_list) = head;
1980 if (BLOCK_FOR_INSN (head) != head_bb)
1981 BB_END (head_bb) = note_list;
1989 /* Move insns that became ready to fire from queue to ready list. */
1992 queue_to_ready (struct ready_list *ready)
1998 q_ptr = NEXT_Q (q_ptr);
2000 if (dbg_cnt (sched_insn) == false)
2002 /* If debug counter is activated do not requeue insn next after
2003 last_scheduled_insn. */
2004 skip_insn = next_nonnote_insn (last_scheduled_insn);
2005 while (skip_insn && DEBUG_INSN_P (skip_insn))
2006 skip_insn = next_nonnote_insn (skip_insn);
2009 skip_insn = NULL_RTX;
2011 /* Add all pending insns that can be scheduled without stalls to the
2013 for (link = insn_queue[q_ptr]; link; link = XEXP (link, 1))
2015 insn = XEXP (link, 0);
2018 if (sched_verbose >= 2)
2019 fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
2020 (*current_sched_info->print_insn) (insn, 0));
2022 /* If the ready list is full, delay the insn for 1 cycle.
2023 See the comment in schedule_block for the rationale. */
2024 if (!reload_completed
2025 && ready->n_ready - ready->n_debug > MAX_SCHED_READY_INSNS
2026 && !SCHED_GROUP_P (insn)
2027 && insn != skip_insn)
2029 if (sched_verbose >= 2)
2030 fprintf (sched_dump, "requeued because ready full\n");
2031 queue_insn (insn, 1);
2035 ready_add (ready, insn, false);
2036 if (sched_verbose >= 2)
2037 fprintf (sched_dump, "moving to ready without stalls\n");
2040 free_INSN_LIST_list (&insn_queue[q_ptr]);
2042 /* If there are no ready insns, stall until one is ready and add all
2043 of the pending insns at that point to the ready list. */
2044 if (ready->n_ready == 0)
2048 for (stalls = 1; stalls <= max_insn_queue_index; stalls++)
2050 if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
2052 for (; link; link = XEXP (link, 1))
2054 insn = XEXP (link, 0);
2057 if (sched_verbose >= 2)
2058 fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
2059 (*current_sched_info->print_insn) (insn, 0));
2061 ready_add (ready, insn, false);
2062 if (sched_verbose >= 2)
2063 fprintf (sched_dump, "moving to ready with %d stalls\n", stalls);
2065 free_INSN_LIST_list (&insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]);
2067 advance_one_cycle ();
2072 advance_one_cycle ();
2075 q_ptr = NEXT_Q_AFTER (q_ptr, stalls);
2076 clock_var += stalls;
2080 /* Used by early_queue_to_ready. Determines whether it is "ok" to
2081 prematurely move INSN from the queue to the ready list. Currently,
2082 if a target defines the hook 'is_costly_dependence', this function
2083 uses the hook to check whether there exist any dependences which are
2084 considered costly by the target, between INSN and other insns that
2085 have already been scheduled. Dependences are checked up to Y cycles
2086 back, with default Y=1; The flag -fsched-stalled-insns-dep=Y allows
2087 controlling this value.
2088 (Other considerations could be taken into account instead (or in
2089 addition) depending on user flags and target hooks. */
2092 ok_for_early_queue_removal (rtx insn)
2095 rtx prev_insn = last_scheduled_insn;
2097 if (targetm.sched.is_costly_dependence)
2099 for (n_cycles = flag_sched_stalled_insns_dep; n_cycles; n_cycles--)
2101 for ( ; prev_insn; prev_insn = PREV_INSN (prev_insn))
2105 if (prev_insn == current_sched_info->prev_head)
2111 if (!NOTE_P (prev_insn))
2115 dep = sd_find_dep_between (prev_insn, insn, true);
2119 cost = dep_cost (dep);
2121 if (targetm.sched.is_costly_dependence (dep, cost,
2122 flag_sched_stalled_insns_dep - n_cycles))
2127 if (GET_MODE (prev_insn) == TImode) /* end of dispatch group */
2133 prev_insn = PREV_INSN (prev_insn);
2141 /* Remove insns from the queue, before they become "ready" with respect
2142 to FU latency considerations. */
2145 early_queue_to_ready (state_t state, struct ready_list *ready)
2153 state_t temp_state = alloca (dfa_state_size);
2155 int insns_removed = 0;
2158 Flag '-fsched-stalled-insns=X' determines the aggressiveness of this
2161 X == 0: There is no limit on how many queued insns can be removed
2162 prematurely. (flag_sched_stalled_insns = -1).
2164 X >= 1: Only X queued insns can be removed prematurely in each
2165 invocation. (flag_sched_stalled_insns = X).
2167 Otherwise: Early queue removal is disabled.
2168 (flag_sched_stalled_insns = 0)
2171 if (! flag_sched_stalled_insns)
2174 for (stalls = 0; stalls <= max_insn_queue_index; stalls++)
2176 if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
2178 if (sched_verbose > 6)
2179 fprintf (sched_dump, ";; look at index %d + %d\n", q_ptr, stalls);
2184 next_link = XEXP (link, 1);
2185 insn = XEXP (link, 0);
2186 if (insn && sched_verbose > 6)
2187 print_rtl_single (sched_dump, insn);
2189 memcpy (temp_state, state, dfa_state_size);
2190 if (recog_memoized (insn) < 0)
2191 /* non-negative to indicate that it's not ready
2192 to avoid infinite Q->R->Q->R... */
2195 cost = state_transition (temp_state, insn);
2197 if (sched_verbose >= 6)
2198 fprintf (sched_dump, "transition cost = %d\n", cost);
2200 move_to_ready = false;
2203 move_to_ready = ok_for_early_queue_removal (insn);
2204 if (move_to_ready == true)
2206 /* move from Q to R */
2208 ready_add (ready, insn, false);
2211 XEXP (prev_link, 1) = next_link;
2213 insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = next_link;
2215 free_INSN_LIST_node (link);
2217 if (sched_verbose >= 2)
2218 fprintf (sched_dump, ";;\t\tEarly Q-->Ready: insn %s\n",
2219 (*current_sched_info->print_insn) (insn, 0));
2222 if (insns_removed == flag_sched_stalled_insns)
2223 /* Remove no more than flag_sched_stalled_insns insns
2224 from Q at a time. */
2225 return insns_removed;
2229 if (move_to_ready == false)
2236 } /* for stalls.. */
2238 return insns_removed;
2242 /* Print the ready list for debugging purposes. Callable from debugger. */
2245 debug_ready_list (struct ready_list *ready)
2250 if (ready->n_ready == 0)
2252 fprintf (sched_dump, "\n");
2256 p = ready_lastpos (ready);
2257 for (i = 0; i < ready->n_ready; i++)
2259 fprintf (sched_dump, " %s:%d",
2260 (*current_sched_info->print_insn) (p[i], 0),
2262 if (sched_pressure_p)
2263 fprintf (sched_dump, "(cost=%d",
2264 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (p[i]));
2265 if (INSN_TICK (p[i]) > clock_var)
2266 fprintf (sched_dump, ":delay=%d", INSN_TICK (p[i]) - clock_var);
2267 if (sched_pressure_p)
2268 fprintf (sched_dump, ")");
2270 fprintf (sched_dump, "\n");
2273 /* Search INSN for REG_SAVE_NOTE notes and convert them back into insn
2274 NOTEs. This is used for NOTE_INSN_EPILOGUE_BEG, so that sched-ebb
2275 replaces the epilogue note in the correct basic block. */
2277 reemit_notes (rtx insn)
2279 rtx note, last = insn;
2281 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
2283 if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
2285 enum insn_note note_type = (enum insn_note) INTVAL (XEXP (note, 0));
2287 last = emit_note_before (note_type, last);
2288 remove_note (insn, note);
2293 /* Move INSN. Reemit notes if needed. Update CFG, if needed. */
2295 move_insn (rtx insn, rtx last, rtx nt)
2297 if (PREV_INSN (insn) != last)
2303 bb = BLOCK_FOR_INSN (insn);
2305 /* BB_HEAD is either LABEL or NOTE. */
2306 gcc_assert (BB_HEAD (bb) != insn);
2308 if (BB_END (bb) == insn)
2309 /* If this is last instruction in BB, move end marker one
2312 /* Jumps are always placed at the end of basic block. */
2313 jump_p = control_flow_insn_p (insn);
2316 || ((common_sched_info->sched_pass_id == SCHED_RGN_PASS)
2317 && IS_SPECULATION_BRANCHY_CHECK_P (insn))
2318 || (common_sched_info->sched_pass_id
2319 == SCHED_EBB_PASS));
2321 gcc_assert (BLOCK_FOR_INSN (PREV_INSN (insn)) == bb);
2323 BB_END (bb) = PREV_INSN (insn);
2326 gcc_assert (BB_END (bb) != last);
2329 /* We move the block note along with jump. */
2333 note = NEXT_INSN (insn);
2334 while (NOTE_NOT_BB_P (note) && note != nt)
2335 note = NEXT_INSN (note);
2339 || BARRIER_P (note)))
2340 note = NEXT_INSN (note);
2342 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
2347 NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (note);
2348 PREV_INSN (NEXT_INSN (note)) = PREV_INSN (insn);
2350 NEXT_INSN (note) = NEXT_INSN (last);
2351 PREV_INSN (NEXT_INSN (last)) = note;
2353 NEXT_INSN (last) = insn;
2354 PREV_INSN (insn) = last;
2356 bb = BLOCK_FOR_INSN (last);
2360 fix_jump_move (insn);
2362 if (BLOCK_FOR_INSN (insn) != bb)
2363 move_block_after_check (insn);
2365 gcc_assert (BB_END (bb) == last);
2368 df_insn_change_bb (insn, bb);
2370 /* Update BB_END, if needed. */
2371 if (BB_END (bb) == last)
2375 SCHED_GROUP_P (insn) = 0;
2378 /* Return true if scheduling INSN will finish current clock cycle. */
2380 insn_finishes_cycle_p (rtx insn)
2382 if (SCHED_GROUP_P (insn))
2383 /* After issuing INSN, rest of the sched_group will be forced to issue
2384 in order. Don't make any plans for the rest of cycle. */
2387 /* Finishing the block will, apparently, finish the cycle. */
2388 if (current_sched_info->insn_finishes_block_p
2389 && current_sched_info->insn_finishes_block_p (insn))
2395 /* The following structure describe an entry of the stack of choices. */
2398 /* Ordinal number of the issued insn in the ready queue. */
2400 /* The number of the rest insns whose issues we should try. */
2402 /* The number of issued essential insns. */
2404 /* State after issuing the insn. */
2408 /* The following array is used to implement a stack of choices used in
2409 function max_issue. */
2410 static struct choice_entry *choice_stack;
2412 /* The following variable value is number of essential insns issued on
2413 the current cycle. An insn is essential one if it changes the
2414 processors state. */
2415 int cycle_issued_insns;
2417 /* This holds the value of the target dfa_lookahead hook. */
2420 /* The following variable value is maximal number of tries of issuing
2421 insns for the first cycle multipass insn scheduling. We define
2422 this value as constant*(DFA_LOOKAHEAD**ISSUE_RATE). We would not
2423 need this constraint if all real insns (with non-negative codes)
2424 had reservations because in this case the algorithm complexity is
2425 O(DFA_LOOKAHEAD**ISSUE_RATE). Unfortunately, the dfa descriptions
2426 might be incomplete and such insn might occur. For such
2427 descriptions, the complexity of algorithm (without the constraint)
2428 could achieve DFA_LOOKAHEAD ** N , where N is the queue length. */
2429 static int max_lookahead_tries;
2431 /* The following value is value of hook
2432 `first_cycle_multipass_dfa_lookahead' at the last call of
2434 static int cached_first_cycle_multipass_dfa_lookahead = 0;
2436 /* The following value is value of `issue_rate' at the last call of
2438 static int cached_issue_rate = 0;
2440 /* The following function returns maximal (or close to maximal) number
2441 of insns which can be issued on the same cycle and one of which
2442 insns is insns with the best rank (the first insn in READY). To
2443 make this function tries different samples of ready insns. READY
2444 is current queue `ready'. Global array READY_TRY reflects what
2445 insns are already issued in this try. MAX_POINTS is the sum of points
2446 of all instructions in READY. The function stops immediately,
2447 if it reached the such a solution, that all instruction can be issued.
2448 INDEX will contain index of the best insn in READY. The following
2449 function is used only for first cycle multipass scheduling.
2453 This function expects recognized insns only. All USEs,
2454 CLOBBERs, etc must be filtered elsewhere. */
2456 max_issue (struct ready_list *ready, int privileged_n, state_t state,
2459 int n, i, all, n_ready, best, delay, tries_num, max_points;
2461 struct choice_entry *top;
2464 n_ready = ready->n_ready;
2465 gcc_assert (dfa_lookahead >= 1 && privileged_n >= 0
2466 && privileged_n <= n_ready);
2468 /* Init MAX_LOOKAHEAD_TRIES. */
2469 if (cached_first_cycle_multipass_dfa_lookahead != dfa_lookahead)
2471 cached_first_cycle_multipass_dfa_lookahead = dfa_lookahead;
2472 max_lookahead_tries = 100;
2473 for (i = 0; i < issue_rate; i++)
2474 max_lookahead_tries *= dfa_lookahead;
2477 /* Init max_points. */
2479 more_issue = issue_rate - cycle_issued_insns;
2481 /* ??? We used to assert here that we never issue more insns than issue_rate.
2482 However, some targets (e.g. MIPS/SB1) claim lower issue rate than can be
2483 achieved to get better performance. Until these targets are fixed to use
2484 scheduler hooks to manipulate insns priority instead, the assert should
2487 gcc_assert (more_issue >= 0); */
2489 for (i = 0; i < n_ready; i++)
2492 if (more_issue-- > 0)
2493 max_points += ISSUE_POINTS (ready_element (ready, i));
2498 /* The number of the issued insns in the best solution. */
2503 /* Set initial state of the search. */
2504 memcpy (top->state, state, dfa_state_size);
2505 top->rest = dfa_lookahead;
2508 /* Count the number of the insns to search among. */
2509 for (all = i = 0; i < n_ready; i++)
2513 /* I is the index of the insn to try next. */
2518 if (/* If we've reached a dead end or searched enough of what we have
2521 /* Or have nothing else to try. */
2524 /* ??? (... || i == n_ready). */
2525 gcc_assert (i <= n_ready);
2527 if (top == choice_stack)
2530 if (best < top - choice_stack)
2535 /* Try to find issued privileged insn. */
2536 while (n && !ready_try[--n]);
2539 if (/* If all insns are equally good... */
2541 /* Or a privileged insn will be issued. */
2543 /* Then we have a solution. */
2545 best = top - choice_stack;
2546 /* This is the index of the insn issued first in this
2548 *index = choice_stack [1].index;
2549 if (top->n == max_points || best == all)
2554 /* Set ready-list index to point to the last insn
2555 ('i++' below will advance it to the next insn). */
2561 memcpy (state, top->state, dfa_state_size);
2563 else if (!ready_try [i])
2566 if (tries_num > max_lookahead_tries)
2568 insn = ready_element (ready, i);
2569 delay = state_transition (state, insn);
2572 if (state_dead_lock_p (state)
2573 || insn_finishes_cycle_p (insn))
2574 /* We won't issue any more instructions in the next
2581 if (memcmp (top->state, state, dfa_state_size) != 0)
2582 n += ISSUE_POINTS (insn);
2584 /* Advance to the next choice_entry. */
2586 /* Initialize it. */
2587 top->rest = dfa_lookahead;
2590 memcpy (top->state, state, dfa_state_size);
2597 /* Increase ready-list index. */
2601 /* Restore the original state of the DFA. */
2602 memcpy (state, choice_stack->state, dfa_state_size);
2607 /* The following function chooses insn from READY and modifies
2608 READY. The following function is used only for first
2609 cycle multipass scheduling.
2611 -1 if cycle should be advanced,
2612 0 if INSN_PTR is set to point to the desirable insn,
2613 1 if choose_ready () should be restarted without advancing the cycle. */
2615 choose_ready (struct ready_list *ready, rtx *insn_ptr)
2619 if (dbg_cnt (sched_insn) == false)
2623 insn = next_nonnote_insn (last_scheduled_insn);
2625 if (QUEUE_INDEX (insn) == QUEUE_READY)
2626 /* INSN is in the ready_list. */
2628 ready_remove_insn (insn);
2633 /* INSN is in the queue. Advance cycle to move it to the ready list. */
2639 if (targetm.sched.first_cycle_multipass_dfa_lookahead)
2640 lookahead = targetm.sched.first_cycle_multipass_dfa_lookahead ();
2641 if (lookahead <= 0 || SCHED_GROUP_P (ready_element (ready, 0))
2642 || DEBUG_INSN_P (ready_element (ready, 0)))
2644 *insn_ptr = ready_remove_first (ready);
2649 /* Try to choose the better insn. */
2650 int index = 0, i, n;
2652 int try_data = 1, try_control = 1;
2655 insn = ready_element (ready, 0);
2656 if (INSN_CODE (insn) < 0)
2658 *insn_ptr = ready_remove_first (ready);
2663 && spec_info->flags & (PREFER_NON_DATA_SPEC
2664 | PREFER_NON_CONTROL_SPEC))
2666 for (i = 0, n = ready->n_ready; i < n; i++)
2671 x = ready_element (ready, i);
2674 if (spec_info->flags & PREFER_NON_DATA_SPEC
2675 && !(s & DATA_SPEC))
2678 if (!(spec_info->flags & PREFER_NON_CONTROL_SPEC)
2683 if (spec_info->flags & PREFER_NON_CONTROL_SPEC
2684 && !(s & CONTROL_SPEC))
2687 if (!(spec_info->flags & PREFER_NON_DATA_SPEC) || !try_data)
2693 ts = TODO_SPEC (insn);
2694 if ((ts & SPECULATIVE)
2695 && (((!try_data && (ts & DATA_SPEC))
2696 || (!try_control && (ts & CONTROL_SPEC)))
2697 || (targetm.sched.first_cycle_multipass_dfa_lookahead_guard_spec
2699 .first_cycle_multipass_dfa_lookahead_guard_spec (insn))))
2700 /* Discard speculative instruction that stands first in the ready
2703 change_queue_index (insn, 1);
2709 for (i = 1; i < ready->n_ready; i++)
2711 insn = ready_element (ready, i);
2714 = ((!try_data && (TODO_SPEC (insn) & DATA_SPEC))
2715 || (!try_control && (TODO_SPEC (insn) & CONTROL_SPEC)));
2718 /* Let the target filter the search space. */
2719 for (i = 1; i < ready->n_ready; i++)
2722 insn = ready_element (ready, i);
2724 #ifdef ENABLE_CHECKING
2725 /* If this insn is recognizable we should have already
2726 recognized it earlier.
2727 ??? Not very clear where this is supposed to be done.
2729 gcc_assert (INSN_CODE (insn) >= 0
2730 || recog_memoized (insn) < 0);
2734 = (/* INSN_CODE check can be omitted here as it is also done later
2736 INSN_CODE (insn) < 0
2737 || (targetm.sched.first_cycle_multipass_dfa_lookahead_guard
2738 && !targetm.sched.first_cycle_multipass_dfa_lookahead_guard
2742 if (max_issue (ready, 1, curr_state, &index) == 0)
2744 *insn_ptr = ready_remove_first (ready);
2745 if (sched_verbose >= 4)
2746 fprintf (sched_dump, ";;\t\tChosen insn (but can't issue) : %s \n",
2747 (*current_sched_info->print_insn) (*insn_ptr, 0));
2752 if (sched_verbose >= 4)
2753 fprintf (sched_dump, ";;\t\tChosen insn : %s\n",
2754 (*current_sched_info->print_insn)
2755 (ready_element (ready, index), 0));
2757 *insn_ptr = ready_remove (ready, index);
2763 /* Use forward list scheduling to rearrange insns of block pointed to by
2764 TARGET_BB, possibly bringing insns from subsequent blocks in the same
2768 schedule_block (basic_block *target_bb)
2770 int i, first_cycle_insn_p;
2772 state_t temp_state = NULL; /* It is used for multipass scheduling. */
2773 int sort_p, advance, start_clock_var;
2775 /* Head/tail info for this block. */
2776 rtx prev_head = current_sched_info->prev_head;
2777 rtx next_tail = current_sched_info->next_tail;
2778 rtx head = NEXT_INSN (prev_head);
2779 rtx tail = PREV_INSN (next_tail);
2781 /* We used to have code to avoid getting parameters moved from hard
2782 argument registers into pseudos.
2784 However, it was removed when it proved to be of marginal benefit
2785 and caused problems because schedule_block and compute_forward_dependences
2786 had different notions of what the "head" insn was. */
2788 gcc_assert (head != tail || INSN_P (head));
2790 haifa_recovery_bb_recently_added_p = false;
2794 dump_new_block_header (0, *target_bb, head, tail);
2796 state_reset (curr_state);
2798 /* Clear the ready list. */
2799 ready.first = ready.veclen - 1;
2803 /* It is used for first cycle multipass scheduling. */
2804 temp_state = alloca (dfa_state_size);
2806 if (targetm.sched.md_init)
2807 targetm.sched.md_init (sched_dump, sched_verbose, ready.veclen);
2809 /* We start inserting insns after PREV_HEAD. */
2810 last_scheduled_insn = prev_head;
2812 gcc_assert ((NOTE_P (last_scheduled_insn)
2813 || BOUNDARY_DEBUG_INSN_P (last_scheduled_insn))
2814 && BLOCK_FOR_INSN (last_scheduled_insn) == *target_bb);
2816 /* Initialize INSN_QUEUE. Q_SIZE is the total number of insns in the
2821 insn_queue = XALLOCAVEC (rtx, max_insn_queue_index + 1);
2822 memset (insn_queue, 0, (max_insn_queue_index + 1) * sizeof (rtx));
2824 /* Start just before the beginning of time. */
2827 /* We need queue and ready lists and clock_var be initialized
2828 in try_ready () (which is called through init_ready_list ()). */
2829 (*current_sched_info->init_ready_list) ();
2831 /* The algorithm is O(n^2) in the number of ready insns at any given
2832 time in the worst case. Before reload we are more likely to have
2833 big lists so truncate them to a reasonable size. */
2834 if (!reload_completed
2835 && ready.n_ready - ready.n_debug > MAX_SCHED_READY_INSNS)
2837 ready_sort (&ready);
2839 /* Find first free-standing insn past MAX_SCHED_READY_INSNS.
2840 If there are debug insns, we know they're first. */
2841 for (i = MAX_SCHED_READY_INSNS + ready.n_debug; i < ready.n_ready; i++)
2842 if (!SCHED_GROUP_P (ready_element (&ready, i)))
2845 if (sched_verbose >= 2)
2847 fprintf (sched_dump,
2848 ";;\t\tReady list on entry: %d insns\n", ready.n_ready);
2849 fprintf (sched_dump,
2850 ";;\t\t before reload => truncated to %d insns\n", i);
2853 /* Delay all insns past it for 1 cycle. If debug counter is
2854 activated make an exception for the insn right after
2855 last_scheduled_insn. */
2859 if (dbg_cnt (sched_insn) == false)
2860 skip_insn = next_nonnote_insn (last_scheduled_insn);
2862 skip_insn = NULL_RTX;
2864 while (i < ready.n_ready)
2868 insn = ready_remove (&ready, i);
2870 if (insn != skip_insn)
2871 queue_insn (insn, 1);
2876 /* Now we can restore basic block notes and maintain precise cfg. */
2877 restore_bb_notes (*target_bb);
2879 last_clock_var = -1;
2884 /* Loop until all the insns in BB are scheduled. */
2885 while ((*current_sched_info->schedule_more_p) ())
2889 start_clock_var = clock_var;
2893 advance_one_cycle ();
2895 /* Add to the ready list all pending insns that can be issued now.
2896 If there are no ready insns, increment clock until one
2897 is ready and add all pending insns at that point to the ready
2899 queue_to_ready (&ready);
2901 gcc_assert (ready.n_ready);
2903 if (sched_verbose >= 2)
2905 fprintf (sched_dump, ";;\t\tReady list after queue_to_ready: ");
2906 debug_ready_list (&ready);
2908 advance -= clock_var - start_clock_var;
2910 while (advance > 0);
2914 /* Sort the ready list based on priority. */
2915 ready_sort (&ready);
2917 if (sched_verbose >= 2)
2919 fprintf (sched_dump, ";;\t\tReady list after ready_sort: ");
2920 debug_ready_list (&ready);
2924 /* We don't want md sched reorder to even see debug isns, so put
2925 them out right away. */
2926 if (ready.n_ready && DEBUG_INSN_P (ready_element (&ready, 0)))
2928 if (control_flow_insn_p (last_scheduled_insn))
2930 *target_bb = current_sched_info->advance_target_bb
2937 x = next_real_insn (last_scheduled_insn);
2939 dump_new_block_header (1, *target_bb, x, tail);
2942 last_scheduled_insn = bb_note (*target_bb);
2945 while (ready.n_ready && DEBUG_INSN_P (ready_element (&ready, 0)))
2947 rtx insn = ready_remove_first (&ready);
2948 gcc_assert (DEBUG_INSN_P (insn));
2949 (*current_sched_info->begin_schedule_ready) (insn,
2950 last_scheduled_insn);
2951 move_insn (insn, last_scheduled_insn,
2952 current_sched_info->next_tail);
2953 last_scheduled_insn = insn;
2954 advance = schedule_insn (insn);
2955 gcc_assert (advance == 0);
2956 if (ready.n_ready > 0)
2957 ready_sort (&ready);
2964 /* Allow the target to reorder the list, typically for
2965 better instruction bundling. */
2966 if (sort_p && targetm.sched.reorder
2967 && (ready.n_ready == 0
2968 || !SCHED_GROUP_P (ready_element (&ready, 0))))
2970 targetm.sched.reorder (sched_dump, sched_verbose,
2971 ready_lastpos (&ready),
2972 &ready.n_ready, clock_var);
2974 can_issue_more = issue_rate;
2976 first_cycle_insn_p = 1;
2977 cycle_issued_insns = 0;
2984 if (sched_verbose >= 2)
2986 fprintf (sched_dump, ";;\tReady list (t = %3d): ",
2988 debug_ready_list (&ready);
2989 if (sched_pressure_p)
2990 print_curr_reg_pressure ();
2993 if (ready.n_ready == 0
2995 && reload_completed)
2997 /* Allow scheduling insns directly from the queue in case
2998 there's nothing better to do (ready list is empty) but
2999 there are still vacant dispatch slots in the current cycle. */
3000 if (sched_verbose >= 6)
3001 fprintf (sched_dump,";;\t\tSecond chance\n");
3002 memcpy (temp_state, curr_state, dfa_state_size);
3003 if (early_queue_to_ready (temp_state, &ready))
3004 ready_sort (&ready);
3007 if (ready.n_ready == 0
3009 || state_dead_lock_p (curr_state)
3010 || !(*current_sched_info->schedule_more_p) ())
3013 /* Select and remove the insn from the ready list. */
3019 res = choose_ready (&ready, &insn);
3025 /* Restart choose_ready (). */
3028 gcc_assert (insn != NULL_RTX);
3031 insn = ready_remove_first (&ready);
3033 if (sched_pressure_p && INSN_TICK (insn) > clock_var)
3035 ready_add (&ready, insn, true);
3040 if (targetm.sched.dfa_new_cycle
3041 && targetm.sched.dfa_new_cycle (sched_dump, sched_verbose,
3042 insn, last_clock_var,
3043 clock_var, &sort_p))
3044 /* SORT_P is used by the target to override sorting
3045 of the ready list. This is needed when the target
3046 has modified its internal structures expecting that
3047 the insn will be issued next. As we need the insn
3048 to have the highest priority (so it will be returned by
3049 the ready_remove_first call above), we invoke
3050 ready_add (&ready, insn, true).
3051 But, still, there is one issue: INSN can be later
3052 discarded by scheduler's front end through
3053 current_sched_info->can_schedule_ready_p, hence, won't
3056 ready_add (&ready, insn, true);
3061 memcpy (temp_state, curr_state, dfa_state_size);
3062 if (recog_memoized (insn) < 0)
3064 asm_p = (GET_CODE (PATTERN (insn)) == ASM_INPUT
3065 || asm_noperands (PATTERN (insn)) >= 0);
3066 if (!first_cycle_insn_p && asm_p)
3067 /* This is asm insn which is tried to be issued on the
3068 cycle not first. Issue it on the next cycle. */
3071 /* A USE insn, or something else we don't need to
3072 understand. We can't pass these directly to
3073 state_transition because it will trigger a
3074 fatal error for unrecognizable insns. */
3077 else if (sched_pressure_p)
3081 cost = state_transition (temp_state, insn);
3090 queue_insn (insn, cost);
3091 if (SCHED_GROUP_P (insn))
3100 if (current_sched_info->can_schedule_ready_p
3101 && ! (*current_sched_info->can_schedule_ready_p) (insn))
3102 /* We normally get here only if we don't want to move
3103 insn from the split block. */
3105 TODO_SPEC (insn) = (TODO_SPEC (insn) & ~SPECULATIVE) | HARD_DEP;
3109 /* DECISION is made. */
3111 if (TODO_SPEC (insn) & SPECULATIVE)
3112 generate_recovery_code (insn);
3114 if (control_flow_insn_p (last_scheduled_insn)
3115 /* This is used to switch basic blocks by request
3116 from scheduler front-end (actually, sched-ebb.c only).
3117 This is used to process blocks with single fallthru
3118 edge. If succeeding block has jump, it [jump] will try
3119 move at the end of current bb, thus corrupting CFG. */
3120 || current_sched_info->advance_target_bb (*target_bb, insn))
3122 *target_bb = current_sched_info->advance_target_bb
3129 x = next_real_insn (last_scheduled_insn);
3131 dump_new_block_header (1, *target_bb, x, tail);
3134 last_scheduled_insn = bb_note (*target_bb);
3137 /* Update counters, etc in the scheduler's front end. */
3138 (*current_sched_info->begin_schedule_ready) (insn,
3139 last_scheduled_insn);
3141 move_insn (insn, last_scheduled_insn, current_sched_info->next_tail);
3142 reemit_notes (insn);
3143 last_scheduled_insn = insn;
3145 if (memcmp (curr_state, temp_state, dfa_state_size) != 0)
3147 cycle_issued_insns++;
3148 memcpy (curr_state, temp_state, dfa_state_size);
3151 if (targetm.sched.variable_issue)
3153 targetm.sched.variable_issue (sched_dump, sched_verbose,
3154 insn, can_issue_more);
3155 /* A naked CLOBBER or USE generates no instruction, so do
3156 not count them against the issue rate. */
3157 else if (GET_CODE (PATTERN (insn)) != USE
3158 && GET_CODE (PATTERN (insn)) != CLOBBER)
3160 advance = schedule_insn (insn);
3162 /* After issuing an asm insn we should start a new cycle. */
3163 if (advance == 0 && asm_p)
3168 first_cycle_insn_p = 0;
3170 /* Sort the ready list based on priority. This must be
3171 redone here, as schedule_insn may have readied additional
3172 insns that will not be sorted correctly. */
3173 if (ready.n_ready > 0)
3174 ready_sort (&ready);
3176 /* Quickly go through debug insns such that md sched
3177 reorder2 doesn't have to deal with debug insns. */
3178 if (ready.n_ready && DEBUG_INSN_P (ready_element (&ready, 0))
3179 && (*current_sched_info->schedule_more_p) ())
3181 if (control_flow_insn_p (last_scheduled_insn))
3183 *target_bb = current_sched_info->advance_target_bb
3190 x = next_real_insn (last_scheduled_insn);
3192 dump_new_block_header (1, *target_bb, x, tail);
3195 last_scheduled_insn = bb_note (*target_bb);
3198 while (ready.n_ready && DEBUG_INSN_P (ready_element (&ready, 0)))
3200 insn = ready_remove_first (&ready);
3201 gcc_assert (DEBUG_INSN_P (insn));
3202 (*current_sched_info->begin_schedule_ready)
3203 (insn, last_scheduled_insn);
3204 move_insn (insn, last_scheduled_insn,
3205 current_sched_info->next_tail);
3206 advance = schedule_insn (insn);
3207 last_scheduled_insn = insn;
3208 gcc_assert (advance == 0);
3209 if (ready.n_ready > 0)
3210 ready_sort (&ready);
3214 if (targetm.sched.reorder2
3215 && (ready.n_ready == 0
3216 || !SCHED_GROUP_P (ready_element (&ready, 0))))
3219 targetm.sched.reorder2 (sched_dump, sched_verbose,
3221 ? ready_lastpos (&ready) : NULL,
3222 &ready.n_ready, clock_var);
3230 fprintf (sched_dump, ";;\tReady list (final): ");
3231 debug_ready_list (&ready);
3234 if (current_sched_info->queue_must_finish_empty)
3235 /* Sanity check -- queue must be empty now. Meaningless if region has
3237 gcc_assert (!q_size && !ready.n_ready && !ready.n_debug);
3240 /* We must maintain QUEUE_INDEX between blocks in region. */
3241 for (i = ready.n_ready - 1; i >= 0; i--)
3245 x = ready_element (&ready, i);
3246 QUEUE_INDEX (x) = QUEUE_NOWHERE;
3247 TODO_SPEC (x) = (TODO_SPEC (x) & ~SPECULATIVE) | HARD_DEP;
3251 for (i = 0; i <= max_insn_queue_index; i++)
3254 for (link = insn_queue[i]; link; link = XEXP (link, 1))
3259 QUEUE_INDEX (x) = QUEUE_NOWHERE;
3260 TODO_SPEC (x) = (TODO_SPEC (x) & ~SPECULATIVE) | HARD_DEP;
3262 free_INSN_LIST_list (&insn_queue[i]);
3267 fprintf (sched_dump, ";; total time = %d\n", clock_var);
3269 if (!current_sched_info->queue_must_finish_empty
3270 || haifa_recovery_bb_recently_added_p)
3272 /* INSN_TICK (minimum clock tick at which the insn becomes
3273 ready) may be not correct for the insn in the subsequent
3274 blocks of the region. We should use a correct value of
3275 `clock_var' or modify INSN_TICK. It is better to keep
3276 clock_var value equal to 0 at the start of a basic block.
3277 Therefore we modify INSN_TICK here. */
3278 fix_inter_tick (NEXT_INSN (prev_head), last_scheduled_insn);
3281 if (targetm.sched.md_finish)
3283 targetm.sched.md_finish (sched_dump, sched_verbose);
3284 /* Target might have added some instructions to the scheduled block
3285 in its md_finish () hook. These new insns don't have any data
3286 initialized and to identify them we extend h_i_d so that they'll
3288 sched_init_luids (NULL, NULL, NULL, NULL);
3292 fprintf (sched_dump, ";; new head = %d\n;; new tail = %d\n\n",
3293 INSN_UID (head), INSN_UID (tail));
3295 /* Update head/tail boundaries. */
3296 head = NEXT_INSN (prev_head);
3297 tail = last_scheduled_insn;
3299 head = restore_other_notes (head, NULL);
3301 current_sched_info->head = head;
3302 current_sched_info->tail = tail;
3305 /* Set_priorities: compute priority of each insn in the block. */
3308 set_priorities (rtx head, rtx tail)
3312 int sched_max_insns_priority =
3313 current_sched_info->sched_max_insns_priority;
3316 if (head == tail && (! INSN_P (head) || BOUNDARY_DEBUG_INSN_P (head)))
3321 prev_head = PREV_INSN (head);
3322 for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
3328 (void) priority (insn);
3330 gcc_assert (INSN_PRIORITY_KNOWN (insn));
3332 sched_max_insns_priority = MAX (sched_max_insns_priority,
3333 INSN_PRIORITY (insn));
3336 current_sched_info->sched_max_insns_priority = sched_max_insns_priority;
3341 /* Set dump and sched_verbose for the desired debugging output. If no
3342 dump-file was specified, but -fsched-verbose=N (any N), print to stderr.
3343 For -fsched-verbose=N, N>=10, print everything to stderr. */
3345 setup_sched_dump (void)
3347 sched_verbose = sched_verbose_param;
3348 if (sched_verbose_param == 0 && dump_file)
3350 sched_dump = ((sched_verbose_param >= 10 || !dump_file)
3351 ? stderr : dump_file);
3354 /* Initialize some global state for the scheduler. This function works
3355 with the common data shared between all the schedulers. It is called
3356 from the scheduler specific initialization routine. */
3361 /* Disable speculative loads in their presence if cc0 defined. */
3363 flag_schedule_speculative_load = 0;
3366 sched_pressure_p = (flag_sched_pressure && ! reload_completed
3367 && common_sched_info->sched_pass_id == SCHED_RGN_PASS);
3368 if (sched_pressure_p)
3369 ira_setup_eliminable_regset ();
3371 /* Initialize SPEC_INFO. */
3372 if (targetm.sched.set_sched_flags)
3374 spec_info = &spec_info_var;
3375 targetm.sched.set_sched_flags (spec_info);
3377 if (spec_info->mask != 0)
3379 spec_info->data_weakness_cutoff =
3380 (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF) * MAX_DEP_WEAK) / 100;
3381 spec_info->control_weakness_cutoff =
3382 (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF)
3383 * REG_BR_PROB_BASE) / 100;
3386 /* So we won't read anything accidentally. */
3391 /* So we won't read anything accidentally. */
3394 /* Initialize issue_rate. */
3395 if (targetm.sched.issue_rate)
3396 issue_rate = targetm.sched.issue_rate ();
3400 if (cached_issue_rate != issue_rate)
3402 cached_issue_rate = issue_rate;
3403 /* To invalidate max_lookahead_tries: */
3404 cached_first_cycle_multipass_dfa_lookahead = 0;
3407 if (targetm.sched.first_cycle_multipass_dfa_lookahead)
3408 dfa_lookahead = targetm.sched.first_cycle_multipass_dfa_lookahead ();
3412 if (targetm.sched.init_dfa_pre_cycle_insn)
3413 targetm.sched.init_dfa_pre_cycle_insn ();
3415 if (targetm.sched.init_dfa_post_cycle_insn)
3416 targetm.sched.init_dfa_post_cycle_insn ();
3419 dfa_state_size = state_size ();
3421 init_alias_analysis ();
3423 df_set_flags (DF_LR_RUN_DCE);
3424 df_note_add_problem ();
3426 /* More problems needed for interloop dep calculation in SMS. */
3427 if (common_sched_info->sched_pass_id == SCHED_SMS_PASS)
3429 df_rd_add_problem ();
3430 df_chain_add_problem (DF_DU_CHAIN + DF_UD_CHAIN);
3435 /* Do not run DCE after reload, as this can kill nops inserted
3437 if (reload_completed)
3438 df_clear_flags (DF_LR_RUN_DCE);
3440 regstat_compute_calls_crossed ();
3442 if (targetm.sched.md_init_global)
3443 targetm.sched.md_init_global (sched_dump, sched_verbose,
3444 get_max_uid () + 1);
3446 if (sched_pressure_p)
3448 int i, max_regno = max_reg_num ();
3450 ira_set_pseudo_classes (sched_verbose ? sched_dump : NULL);
3451 sched_regno_cover_class
3452 = (enum reg_class *) xmalloc (max_regno * sizeof (enum reg_class));
3453 for (i = 0; i < max_regno; i++)
3454 sched_regno_cover_class[i]
3455 = (i < FIRST_PSEUDO_REGISTER
3456 ? ira_class_translate[REGNO_REG_CLASS (i)]
3457 : reg_cover_class (i));
3458 curr_reg_live = BITMAP_ALLOC (NULL);
3459 saved_reg_live = BITMAP_ALLOC (NULL);
3460 region_ref_regs = BITMAP_ALLOC (NULL);
3463 curr_state = xmalloc (dfa_state_size);
3466 static void haifa_init_only_bb (basic_block, basic_block);
3468 /* Initialize data structures specific to the Haifa scheduler. */
3470 haifa_sched_init (void)
3472 setup_sched_dump ();
3475 if (spec_info != NULL)
3477 sched_deps_info->use_deps_list = 1;
3478 sched_deps_info->generate_spec_deps = 1;
3481 /* Initialize luids, dependency caches, target and h_i_d for the
3484 bb_vec_t bbs = VEC_alloc (basic_block, heap, n_basic_blocks);
3490 VEC_quick_push (basic_block, bbs, bb);
3491 sched_init_luids (bbs, NULL, NULL, NULL);
3492 sched_deps_init (true);
3493 sched_extend_target ();
3494 haifa_init_h_i_d (bbs, NULL, NULL, NULL);
3496 VEC_free (basic_block, heap, bbs);
3499 sched_init_only_bb = haifa_init_only_bb;
3500 sched_split_block = sched_split_block_1;
3501 sched_create_empty_bb = sched_create_empty_bb_1;
3502 haifa_recovery_bb_ever_added_p = false;
3504 #ifdef ENABLE_CHECKING
3505 /* This is used preferably for finding bugs in check_cfg () itself.
3506 We must call sched_bbs_init () before check_cfg () because check_cfg ()
3507 assumes that the last insn in the last bb has a non-null successor. */
3511 nr_begin_data = nr_begin_control = nr_be_in_data = nr_be_in_control = 0;
3512 before_recovery = 0;
3516 /* Finish work with the data specific to the Haifa scheduler. */
3518 haifa_sched_finish (void)
3520 sched_create_empty_bb = NULL;
3521 sched_split_block = NULL;
3522 sched_init_only_bb = NULL;
3524 if (spec_info && spec_info->dump)
3526 char c = reload_completed ? 'a' : 'b';
3528 fprintf (spec_info->dump,
3529 ";; %s:\n", current_function_name ());
3531 fprintf (spec_info->dump,
3532 ";; Procedure %cr-begin-data-spec motions == %d\n",
3534 fprintf (spec_info->dump,
3535 ";; Procedure %cr-be-in-data-spec motions == %d\n",
3537 fprintf (spec_info->dump,
3538 ";; Procedure %cr-begin-control-spec motions == %d\n",
3539 c, nr_begin_control);
3540 fprintf (spec_info->dump,
3541 ";; Procedure %cr-be-in-control-spec motions == %d\n",
3542 c, nr_be_in_control);
3545 /* Finalize h_i_d, dependency caches, and luids for the whole
3546 function. Target will be finalized in md_global_finish (). */
3547 sched_deps_finish ();
3548 sched_finish_luids ();
3549 current_sched_info = NULL;
3553 /* Free global data used during insn scheduling. This function works with
3554 the common data shared between the schedulers. */
3559 haifa_finish_h_i_d ();
3560 if (sched_pressure_p)
3562 free (sched_regno_cover_class);
3563 BITMAP_FREE (region_ref_regs);
3564 BITMAP_FREE (saved_reg_live);
3565 BITMAP_FREE (curr_reg_live);
3569 if (targetm.sched.md_finish_global)
3570 targetm.sched.md_finish_global (sched_dump, sched_verbose);
3572 end_alias_analysis ();
3574 regstat_free_calls_crossed ();
3578 #ifdef ENABLE_CHECKING
3579 /* After reload ia64 backend clobbers CFG, so can't check anything. */
3580 if (!reload_completed)
3585 /* Fix INSN_TICKs of the instructions in the current block as well as
3586 INSN_TICKs of their dependents.
3587 HEAD and TAIL are the begin and the end of the current scheduled block. */
3589 fix_inter_tick (rtx head, rtx tail)
3591 /* Set of instructions with corrected INSN_TICK. */
3592 bitmap_head processed;
3593 /* ??? It is doubtful if we should assume that cycle advance happens on
3594 basic block boundaries. Basically insns that are unconditionally ready
3595 on the start of the block are more preferable then those which have
3596 a one cycle dependency over insn from the previous block. */
3597 int next_clock = clock_var + 1;
3599 bitmap_initialize (&processed, 0);
3601 /* Iterates over scheduled instructions and fix their INSN_TICKs and
3602 INSN_TICKs of dependent instructions, so that INSN_TICKs are consistent
3603 across different blocks. */
3604 for (tail = NEXT_INSN (tail); head != tail; head = NEXT_INSN (head))
3609 sd_iterator_def sd_it;
3612 tick = INSN_TICK (head);
3613 gcc_assert (tick >= MIN_TICK);
3615 /* Fix INSN_TICK of instruction from just scheduled block. */
3616 if (!bitmap_bit_p (&processed, INSN_LUID (head)))
3618 bitmap_set_bit (&processed, INSN_LUID (head));
3621 if (tick < MIN_TICK)
3624 INSN_TICK (head) = tick;
3627 FOR_EACH_DEP (head, SD_LIST_RES_FORW, sd_it, dep)
3631 next = DEP_CON (dep);
3632 tick = INSN_TICK (next);
3634 if (tick != INVALID_TICK
3635 /* If NEXT has its INSN_TICK calculated, fix it.
3636 If not - it will be properly calculated from
3637 scratch later in fix_tick_ready. */
3638 && !bitmap_bit_p (&processed, INSN_LUID (next)))
3640 bitmap_set_bit (&processed, INSN_LUID (next));
3643 if (tick < MIN_TICK)
3646 if (tick > INTER_TICK (next))
3647 INTER_TICK (next) = tick;
3649 tick = INTER_TICK (next);
3651 INSN_TICK (next) = tick;
3656 bitmap_clear (&processed);
3659 static int haifa_speculate_insn (rtx, ds_t, rtx *);
3661 /* Check if NEXT is ready to be added to the ready or queue list.
3662 If "yes", add it to the proper list.
3664 -1 - is not ready yet,
3665 0 - added to the ready list,
3666 0 < N - queued for N cycles. */
3668 try_ready (rtx next)
3672 ts = &TODO_SPEC (next);
3675 gcc_assert (!(old_ts & ~(SPECULATIVE | HARD_DEP))
3676 && ((old_ts & HARD_DEP)
3677 || (old_ts & SPECULATIVE)));
3679 if (sd_lists_empty_p (next, SD_LIST_BACK))
3680 /* NEXT has all its dependencies resolved. */
3682 /* Remove HARD_DEP bit from NEXT's status. */
3685 if (current_sched_info->flags & DO_SPECULATION)
3686 /* Remove all speculative bits from NEXT's status. */
3687 *ts &= ~SPECULATIVE;
3691 /* One of the NEXT's dependencies has been resolved.
3692 Recalculate NEXT's status. */
3694 *ts &= ~SPECULATIVE & ~HARD_DEP;
3696 if (sd_lists_empty_p (next, SD_LIST_HARD_BACK))
3697 /* Now we've got NEXT with speculative deps only.
3698 1. Look at the deps to see what we have to do.
3699 2. Check if we can do 'todo'. */
3701 sd_iterator_def sd_it;
3703 bool first_p = true;
3705 FOR_EACH_DEP (next, SD_LIST_BACK, sd_it, dep)
3707 ds_t ds = DEP_STATUS (dep) & SPECULATIVE;
3709 if (DEBUG_INSN_P (DEP_PRO (dep))
3710 && !DEBUG_INSN_P (next))
3720 *ts = ds_merge (*ts, ds);
3723 if (ds_weak (*ts) < spec_info->data_weakness_cutoff)
3724 /* Too few points. */
3725 *ts = (*ts & ~SPECULATIVE) | HARD_DEP;
3732 gcc_assert (*ts == old_ts
3733 && QUEUE_INDEX (next) == QUEUE_NOWHERE);
3734 else if (current_sched_info->new_ready)
3735 *ts = current_sched_info->new_ready (next, *ts);
3737 /* * if !(old_ts & SPECULATIVE) (e.g. HARD_DEP or 0), then insn might
3738 have its original pattern or changed (speculative) one. This is due
3739 to changing ebb in region scheduling.
3740 * But if (old_ts & SPECULATIVE), then we are pretty sure that insn
3741 has speculative pattern.
3743 We can't assert (!(*ts & HARD_DEP) || *ts == old_ts) here because
3744 control-speculative NEXT could have been discarded by sched-rgn.c
3745 (the same case as when discarded by can_schedule_ready_p ()). */
3747 if ((*ts & SPECULATIVE)
3748 /* If (old_ts == *ts), then (old_ts & SPECULATIVE) and we don't
3749 need to change anything. */
3755 gcc_assert ((*ts & SPECULATIVE) && !(*ts & ~SPECULATIVE));
3757 res = haifa_speculate_insn (next, *ts, &new_pat);
3762 /* It would be nice to change DEP_STATUS of all dependences,
3763 which have ((DEP_STATUS & SPECULATIVE) == *ts) to HARD_DEP,
3764 so we won't reanalyze anything. */
3765 *ts = (*ts & ~SPECULATIVE) | HARD_DEP;
3769 /* We follow the rule, that every speculative insn
3770 has non-null ORIG_PAT. */
3771 if (!ORIG_PAT (next))
3772 ORIG_PAT (next) = PATTERN (next);
3776 if (!ORIG_PAT (next))
3777 /* If we gonna to overwrite the original pattern of insn,
3779 ORIG_PAT (next) = PATTERN (next);
3781 haifa_change_pattern (next, new_pat);
3789 /* We need to restore pattern only if (*ts == 0), because otherwise it is
3790 either correct (*ts & SPECULATIVE),
3791 or we simply don't care (*ts & HARD_DEP). */
3793 gcc_assert (!ORIG_PAT (next)
3794 || !IS_SPECULATION_BRANCHY_CHECK_P (next));
3798 /* We can't assert (QUEUE_INDEX (next) == QUEUE_NOWHERE) here because
3799 control-speculative NEXT could have been discarded by sched-rgn.c
3800 (the same case as when discarded by can_schedule_ready_p ()). */
3801 /*gcc_assert (QUEUE_INDEX (next) == QUEUE_NOWHERE);*/
3803 change_queue_index (next, QUEUE_NOWHERE);
3806 else if (!(*ts & BEGIN_SPEC) && ORIG_PAT (next) && !IS_SPECULATION_CHECK_P (next))
3807 /* We should change pattern of every previously speculative
3808 instruction - and we determine if NEXT was speculative by using
3809 ORIG_PAT field. Except one case - speculation checks have ORIG_PAT
3810 pat too, so skip them. */
3812 haifa_change_pattern (next, ORIG_PAT (next));
3813 ORIG_PAT (next) = 0;
3816 if (sched_verbose >= 2)
3818 int s = TODO_SPEC (next);
3820 fprintf (sched_dump, ";;\t\tdependencies resolved: insn %s",
3821 (*current_sched_info->print_insn) (next, 0));
3823 if (spec_info && spec_info->dump)
3826 fprintf (spec_info->dump, "; data-spec;");
3827 if (s & BEGIN_CONTROL)
3828 fprintf (spec_info->dump, "; control-spec;");
3829 if (s & BE_IN_CONTROL)
3830 fprintf (spec_info->dump, "; in-control-spec;");
3833 fprintf (sched_dump, "\n");
3836 adjust_priority (next);
3838 return fix_tick_ready (next);
3841 /* Calculate INSN_TICK of NEXT and add it to either ready or queue list. */
3843 fix_tick_ready (rtx next)
3847 if (!sd_lists_empty_p (next, SD_LIST_RES_BACK))
3850 sd_iterator_def sd_it;
3853 tick = INSN_TICK (next);
3854 /* if tick is not equal to INVALID_TICK, then update
3855 INSN_TICK of NEXT with the most recent resolved dependence
3856 cost. Otherwise, recalculate from scratch. */
3857 full_p = (tick == INVALID_TICK);
3859 FOR_EACH_DEP (next, SD_LIST_RES_BACK, sd_it, dep)
3861 rtx pro = DEP_PRO (dep);
3864 gcc_assert (INSN_TICK (pro) >= MIN_TICK);
3866 tick1 = INSN_TICK (pro) + dep_cost (dep);
3877 INSN_TICK (next) = tick;
3879 delay = tick - clock_var;
3880 if (delay <= 0 || sched_pressure_p)
3881 delay = QUEUE_READY;
3883 change_queue_index (next, delay);
3888 /* Move NEXT to the proper queue list with (DELAY >= 1),
3889 or add it to the ready list (DELAY == QUEUE_READY),
3890 or remove it from ready and queue lists at all (DELAY == QUEUE_NOWHERE). */
3892 change_queue_index (rtx next, int delay)
3894 int i = QUEUE_INDEX (next);
3896 gcc_assert (QUEUE_NOWHERE <= delay && delay <= max_insn_queue_index
3898 gcc_assert (i != QUEUE_SCHEDULED);
3900 if ((delay > 0 && NEXT_Q_AFTER (q_ptr, delay) == i)
3901 || (delay < 0 && delay == i))
3902 /* We have nothing to do. */
3905 /* Remove NEXT from wherever it is now. */
3906 if (i == QUEUE_READY)
3907 ready_remove_insn (next);
3909 queue_remove (next);
3911 /* Add it to the proper place. */
3912 if (delay == QUEUE_READY)
3913 ready_add (readyp, next, false);
3914 else if (delay >= 1)
3915 queue_insn (next, delay);
3917 if (sched_verbose >= 2)
3919 fprintf (sched_dump, ";;\t\ttick updated: insn %s",
3920 (*current_sched_info->print_insn) (next, 0));
3922 if (delay == QUEUE_READY)
3923 fprintf (sched_dump, " into ready\n");
3924 else if (delay >= 1)
3925 fprintf (sched_dump, " into queue with cost=%d\n", delay);
3927 fprintf (sched_dump, " removed from ready or queue lists\n");
3931 static int sched_ready_n_insns = -1;
3933 /* Initialize per region data structures. */
3935 sched_extend_ready_list (int new_sched_ready_n_insns)
3939 if (sched_ready_n_insns == -1)
3940 /* At the first call we need to initialize one more choice_stack
3944 sched_ready_n_insns = 0;
3947 i = sched_ready_n_insns + 1;
3949 ready.veclen = new_sched_ready_n_insns + issue_rate;
3950 ready.vec = XRESIZEVEC (rtx, ready.vec, ready.veclen);
3952 gcc_assert (new_sched_ready_n_insns >= sched_ready_n_insns);
3954 ready_try = (char *) xrecalloc (ready_try, new_sched_ready_n_insns,
3955 sched_ready_n_insns, sizeof (*ready_try));
3957 /* We allocate +1 element to save initial state in the choice_stack[0]
3959 choice_stack = XRESIZEVEC (struct choice_entry, choice_stack,
3960 new_sched_ready_n_insns + 1);
3962 for (; i <= new_sched_ready_n_insns; i++)
3963 choice_stack[i].state = xmalloc (dfa_state_size);
3965 sched_ready_n_insns = new_sched_ready_n_insns;
3968 /* Free per region data structures. */
3970 sched_finish_ready_list (void)
3981 for (i = 0; i <= sched_ready_n_insns; i++)
3982 free (choice_stack [i].state);
3983 free (choice_stack);
3984 choice_stack = NULL;
3986 sched_ready_n_insns = -1;
3990 haifa_luid_for_non_insn (rtx x)
3992 gcc_assert (NOTE_P (x) || LABEL_P (x));
3997 /* Generates recovery code for INSN. */
3999 generate_recovery_code (rtx insn)
4001 if (TODO_SPEC (insn) & BEGIN_SPEC)
4002 begin_speculative_block (insn);
4004 /* Here we have insn with no dependencies to
4005 instructions other then CHECK_SPEC ones. */
4007 if (TODO_SPEC (insn) & BE_IN_SPEC)
4008 add_to_speculative_block (insn);
4012 Tries to add speculative dependencies of type FS between instructions
4013 in deps_list L and TWIN. */
4015 process_insn_forw_deps_be_in_spec (rtx insn, rtx twin, ds_t fs)
4017 sd_iterator_def sd_it;
4020 FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
4025 consumer = DEP_CON (dep);
4027 ds = DEP_STATUS (dep);
4029 if (/* If we want to create speculative dep. */
4031 /* And we can do that because this is a true dep. */
4032 && (ds & DEP_TYPES) == DEP_TRUE)
4034 gcc_assert (!(ds & BE_IN_SPEC));
4036 if (/* If this dep can be overcome with 'begin speculation'. */
4038 /* Then we have a choice: keep the dep 'begin speculative'
4039 or transform it into 'be in speculative'. */
4041 if (/* In try_ready we assert that if insn once became ready
4042 it can be removed from the ready (or queue) list only
4043 due to backend decision. Hence we can't let the
4044 probability of the speculative dep to decrease. */
4045 ds_weak (ds) <= ds_weak (fs))
4049 new_ds = (ds & ~BEGIN_SPEC) | fs;
4051 if (/* consumer can 'be in speculative'. */
4052 sched_insn_is_legitimate_for_speculation_p (consumer,
4054 /* Transform it to be in speculative. */
4059 /* Mark the dep as 'be in speculative'. */
4064 dep_def _new_dep, *new_dep = &_new_dep;
4066 init_dep_1 (new_dep, twin, consumer, DEP_TYPE (dep), ds);
4067 sd_add_dep (new_dep, false);
4072 /* Generates recovery code for BEGIN speculative INSN. */
4074 begin_speculative_block (rtx insn)
4076 if (TODO_SPEC (insn) & BEGIN_DATA)
4078 if (TODO_SPEC (insn) & BEGIN_CONTROL)
4081 create_check_block_twin (insn, false);
4083 TODO_SPEC (insn) &= ~BEGIN_SPEC;
4086 static void haifa_init_insn (rtx);
4088 /* Generates recovery code for BE_IN speculative INSN. */
4090 add_to_speculative_block (rtx insn)
4093 sd_iterator_def sd_it;
4096 rtx_vec_t priorities_roots;
4098 ts = TODO_SPEC (insn);
4099 gcc_assert (!(ts & ~BE_IN_SPEC));
4101 if (ts & BE_IN_DATA)
4103 if (ts & BE_IN_CONTROL)
4106 TODO_SPEC (insn) &= ~BE_IN_SPEC;
4107 gcc_assert (!TODO_SPEC (insn));
4109 DONE_SPEC (insn) |= ts;
4111 /* First we convert all simple checks to branchy. */
4112 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
4113 sd_iterator_cond (&sd_it, &dep);)
4115 rtx check = DEP_PRO (dep);
4117 if (IS_SPECULATION_SIMPLE_CHECK_P (check))
4119 create_check_block_twin (check, true);
4121 /* Restart search. */
4122 sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
4125 /* Continue search. */
4126 sd_iterator_next (&sd_it);
4129 priorities_roots = NULL;
4130 clear_priorities (insn, &priorities_roots);
4137 /* Get the first backward dependency of INSN. */
4138 sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
4139 if (!sd_iterator_cond (&sd_it, &dep))
4140 /* INSN has no backward dependencies left. */
4143 gcc_assert ((DEP_STATUS (dep) & BEGIN_SPEC) == 0
4144 && (DEP_STATUS (dep) & BE_IN_SPEC) != 0
4145 && (DEP_STATUS (dep) & DEP_TYPES) == DEP_TRUE);
4147 check = DEP_PRO (dep);
4149 gcc_assert (!IS_SPECULATION_CHECK_P (check) && !ORIG_PAT (check)
4150 && QUEUE_INDEX (check) == QUEUE_NOWHERE);
4152 rec = BLOCK_FOR_INSN (check);
4154 twin = emit_insn_before (copy_insn (PATTERN (insn)), BB_END (rec));
4155 haifa_init_insn (twin);
4157 sd_copy_back_deps (twin, insn, true);
4159 if (sched_verbose && spec_info->dump)
4160 /* INSN_BB (insn) isn't determined for twin insns yet.
4161 So we can't use current_sched_info->print_insn. */
4162 fprintf (spec_info->dump, ";;\t\tGenerated twin insn : %d/rec%d\n",
4163 INSN_UID (twin), rec->index);
4165 twins = alloc_INSN_LIST (twin, twins);
4167 /* Add dependences between TWIN and all appropriate
4168 instructions from REC. */
4169 FOR_EACH_DEP (insn, SD_LIST_SPEC_BACK, sd_it, dep)
4171 rtx pro = DEP_PRO (dep);
4173 gcc_assert (DEP_TYPE (dep) == REG_DEP_TRUE);
4175 /* INSN might have dependencies from the instructions from
4176 several recovery blocks. At this iteration we process those
4177 producers that reside in REC. */
4178 if (BLOCK_FOR_INSN (pro) == rec)
4180 dep_def _new_dep, *new_dep = &_new_dep;
4182 init_dep (new_dep, pro, twin, REG_DEP_TRUE);
4183 sd_add_dep (new_dep, false);
4187 process_insn_forw_deps_be_in_spec (insn, twin, ts);
4189 /* Remove all dependencies between INSN and insns in REC. */
4190 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
4191 sd_iterator_cond (&sd_it, &dep);)
4193 rtx pro = DEP_PRO (dep);
4195 if (BLOCK_FOR_INSN (pro) == rec)
4196 sd_delete_dep (sd_it);
4198 sd_iterator_next (&sd_it);
4202 /* We couldn't have added the dependencies between INSN and TWINS earlier
4203 because that would make TWINS appear in the INSN_BACK_DEPS (INSN). */
4208 twin = XEXP (twins, 0);
4211 dep_def _new_dep, *new_dep = &_new_dep;
4213 init_dep (new_dep, insn, twin, REG_DEP_OUTPUT);
4214 sd_add_dep (new_dep, false);
4217 twin = XEXP (twins, 1);
4218 free_INSN_LIST_node (twins);
4222 calc_priorities (priorities_roots);
4223 VEC_free (rtx, heap, priorities_roots);
4226 /* Extends and fills with zeros (only the new part) array pointed to by P. */
4228 xrecalloc (void *p, size_t new_nmemb, size_t old_nmemb, size_t size)
4230 gcc_assert (new_nmemb >= old_nmemb);
4231 p = XRESIZEVAR (void, p, new_nmemb * size);
4232 memset (((char *) p) + old_nmemb * size, 0, (new_nmemb - old_nmemb) * size);
4237 Find fallthru edge from PRED. */
4239 find_fallthru_edge (basic_block pred)
4245 succ = pred->next_bb;
4246 gcc_assert (succ->prev_bb == pred);
4248 if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds))
4250 FOR_EACH_EDGE (e, ei, pred->succs)
4251 if (e->flags & EDGE_FALLTHRU)
4253 gcc_assert (e->dest == succ);
4259 FOR_EACH_EDGE (e, ei, succ->preds)
4260 if (e->flags & EDGE_FALLTHRU)
4262 gcc_assert (e->src == pred);
4270 /* Extend per basic block data structures. */
4272 sched_extend_bb (void)
4276 /* The following is done to keep current_sched_info->next_tail non null. */
4277 insn = BB_END (EXIT_BLOCK_PTR->prev_bb);
4278 if (NEXT_INSN (insn) == 0
4281 /* Don't emit a NOTE if it would end up before a BARRIER. */
4282 && !BARRIER_P (NEXT_INSN (insn))))
4284 rtx note = emit_note_after (NOTE_INSN_DELETED, insn);
4285 /* Make insn appear outside BB. */
4286 set_block_for_insn (note, NULL);
4287 BB_END (EXIT_BLOCK_PTR->prev_bb) = insn;
4291 /* Init per basic block data structures. */
4293 sched_init_bbs (void)
4298 /* Initialize BEFORE_RECOVERY variable. */
4300 init_before_recovery (basic_block *before_recovery_ptr)
4305 last = EXIT_BLOCK_PTR->prev_bb;
4306 e = find_fallthru_edge (last);
4310 /* We create two basic blocks:
4311 1. Single instruction block is inserted right after E->SRC
4313 2. Empty block right before EXIT_BLOCK.
4314 Between these two blocks recovery blocks will be emitted. */
4316 basic_block single, empty;
4319 /* If the fallthrough edge to exit we've found is from the block we've
4320 created before, don't do anything more. */
4321 if (last == after_recovery)
4324 adding_bb_to_current_region_p = false;
4326 single = sched_create_empty_bb (last);
4327 empty = sched_create_empty_bb (single);
4329 /* Add new blocks to the root loop. */
4330 if (current_loops != NULL)
4332 add_bb_to_loop (single, VEC_index (loop_p, current_loops->larray, 0));
4333 add_bb_to_loop (empty, VEC_index (loop_p, current_loops->larray, 0));
4336 single->count = last->count;
4337 empty->count = last->count;
4338 single->frequency = last->frequency;
4339 empty->frequency = last->frequency;
4340 BB_COPY_PARTITION (single, last);
4341 BB_COPY_PARTITION (empty, last);
4343 redirect_edge_succ (e, single);
4344 make_single_succ_edge (single, empty, 0);
4345 make_single_succ_edge (empty, EXIT_BLOCK_PTR,
4346 EDGE_FALLTHRU | EDGE_CAN_FALLTHRU);
4348 label = block_label (empty);
4349 x = emit_jump_insn_after (gen_jump (label), BB_END (single));
4350 JUMP_LABEL (x) = label;
4351 LABEL_NUSES (label)++;
4352 haifa_init_insn (x);
4354 emit_barrier_after (x);
4356 sched_init_only_bb (empty, NULL);
4357 sched_init_only_bb (single, NULL);
4360 adding_bb_to_current_region_p = true;
4361 before_recovery = single;
4362 after_recovery = empty;
4364 if (before_recovery_ptr)
4365 *before_recovery_ptr = before_recovery;
4367 if (sched_verbose >= 2 && spec_info->dump)
4368 fprintf (spec_info->dump,
4369 ";;\t\tFixed fallthru to EXIT : %d->>%d->%d->>EXIT\n",
4370 last->index, single->index, empty->index);
4373 before_recovery = last;
4376 /* Returns new recovery block. */
4378 sched_create_recovery_block (basic_block *before_recovery_ptr)
4384 haifa_recovery_bb_recently_added_p = true;
4385 haifa_recovery_bb_ever_added_p = true;
4387 init_before_recovery (before_recovery_ptr);
4389 barrier = get_last_bb_insn (before_recovery);
4390 gcc_assert (BARRIER_P (barrier));
4392 label = emit_label_after (gen_label_rtx (), barrier);
4394 rec = create_basic_block (label, label, before_recovery);
4396 /* A recovery block always ends with an unconditional jump. */
4397 emit_barrier_after (BB_END (rec));
4399 if (BB_PARTITION (before_recovery) != BB_UNPARTITIONED)
4400 BB_SET_PARTITION (rec, BB_COLD_PARTITION);
4402 if (sched_verbose && spec_info->dump)
4403 fprintf (spec_info->dump, ";;\t\tGenerated recovery block rec%d\n",
4409 /* Create edges: FIRST_BB -> REC; FIRST_BB -> SECOND_BB; REC -> SECOND_BB
4410 and emit necessary jumps. */
4412 sched_create_recovery_edges (basic_block first_bb, basic_block rec,
4413 basic_block second_bb)
4419 /* This is fixing of incoming edge. */
4420 /* ??? Which other flags should be specified? */
4421 if (BB_PARTITION (first_bb) != BB_PARTITION (rec))
4422 /* Partition type is the same, if it is "unpartitioned". */
4423 edge_flags = EDGE_CROSSING;
4427 make_edge (first_bb, rec, edge_flags);
4428 label = block_label (second_bb);
4429 jump = emit_jump_insn_after (gen_jump (label), BB_END (rec));
4430 JUMP_LABEL (jump) = label;
4431 LABEL_NUSES (label)++;
4433 if (BB_PARTITION (second_bb) != BB_PARTITION (rec))
4434 /* Partition type is the same, if it is "unpartitioned". */
4436 /* Rewritten from cfgrtl.c. */
4437 if (flag_reorder_blocks_and_partition
4438 && targetm.have_named_sections)
4440 /* We don't need the same note for the check because
4441 any_condjump_p (check) == true. */
4442 add_reg_note (jump, REG_CROSSING_JUMP, NULL_RTX);
4444 edge_flags = EDGE_CROSSING;
4449 make_single_succ_edge (rec, second_bb, edge_flags);
4452 /* This function creates recovery code for INSN. If MUTATE_P is nonzero,
4453 INSN is a simple check, that should be converted to branchy one. */
4455 create_check_block_twin (rtx insn, bool mutate_p)
4458 rtx label, check, twin;
4460 sd_iterator_def sd_it;
4462 dep_def _new_dep, *new_dep = &_new_dep;
4465 gcc_assert (ORIG_PAT (insn) != NULL_RTX);
4468 todo_spec = TODO_SPEC (insn);
4471 gcc_assert (IS_SPECULATION_SIMPLE_CHECK_P (insn)
4472 && (TODO_SPEC (insn) & SPECULATIVE) == 0);
4474 todo_spec = CHECK_SPEC (insn);
4477 todo_spec &= SPECULATIVE;
4479 /* Create recovery block. */
4480 if (mutate_p || targetm.sched.needs_block_p (todo_spec))
4482 rec = sched_create_recovery_block (NULL);
4483 label = BB_HEAD (rec);
4487 rec = EXIT_BLOCK_PTR;
4492 check = targetm.sched.gen_spec_check (insn, label, todo_spec);
4494 if (rec != EXIT_BLOCK_PTR)
4496 /* To have mem_reg alive at the beginning of second_bb,
4497 we emit check BEFORE insn, so insn after splitting
4498 insn will be at the beginning of second_bb, which will
4499 provide us with the correct life information. */
4500 check = emit_jump_insn_before (check, insn);
4501 JUMP_LABEL (check) = label;
4502 LABEL_NUSES (label)++;
4505 check = emit_insn_before (check, insn);
4507 /* Extend data structures. */
4508 haifa_init_insn (check);
4510 /* CHECK is being added to current region. Extend ready list. */
4511 gcc_assert (sched_ready_n_insns != -1);
4512 sched_extend_ready_list (sched_ready_n_insns + 1);
4514 if (current_sched_info->add_remove_insn)
4515 current_sched_info->add_remove_insn (insn, 0);
4517 RECOVERY_BLOCK (check) = rec;
4519 if (sched_verbose && spec_info->dump)
4520 fprintf (spec_info->dump, ";;\t\tGenerated check insn : %s\n",
4521 (*current_sched_info->print_insn) (check, 0));
4523 gcc_assert (ORIG_PAT (insn));
4525 /* Initialize TWIN (twin is a duplicate of original instruction
4526 in the recovery block). */
4527 if (rec != EXIT_BLOCK_PTR)
4529 sd_iterator_def sd_it;
4532 FOR_EACH_DEP (insn, SD_LIST_RES_BACK, sd_it, dep)
4533 if ((DEP_STATUS (dep) & DEP_OUTPUT) != 0)
4535 struct _dep _dep2, *dep2 = &_dep2;
4537 init_dep (dep2, DEP_PRO (dep), check, REG_DEP_TRUE);
4539 sd_add_dep (dep2, true);
4542 twin = emit_insn_after (ORIG_PAT (insn), BB_END (rec));
4543 haifa_init_insn (twin);
4545 if (sched_verbose && spec_info->dump)
4546 /* INSN_BB (insn) isn't determined for twin insns yet.
4547 So we can't use current_sched_info->print_insn. */
4548 fprintf (spec_info->dump, ";;\t\tGenerated twin insn : %d/rec%d\n",
4549 INSN_UID (twin), rec->index);
4553 ORIG_PAT (check) = ORIG_PAT (insn);
4554 HAS_INTERNAL_DEP (check) = 1;
4556 /* ??? We probably should change all OUTPUT dependencies to
4560 /* Copy all resolved back dependencies of INSN to TWIN. This will
4561 provide correct value for INSN_TICK (TWIN). */
4562 sd_copy_back_deps (twin, insn, true);
4564 if (rec != EXIT_BLOCK_PTR)
4565 /* In case of branchy check, fix CFG. */
4567 basic_block first_bb, second_bb;
4570 first_bb = BLOCK_FOR_INSN (check);
4571 second_bb = sched_split_block (first_bb, check);
4573 sched_create_recovery_edges (first_bb, rec, second_bb);
4575 sched_init_only_bb (second_bb, first_bb);
4576 sched_init_only_bb (rec, EXIT_BLOCK_PTR);
4578 jump = BB_END (rec);
4579 haifa_init_insn (jump);
4582 /* Move backward dependences from INSN to CHECK and
4583 move forward dependences from INSN to TWIN. */
4585 /* First, create dependencies between INSN's producers and CHECK & TWIN. */
4586 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
4588 rtx pro = DEP_PRO (dep);
4591 /* If BEGIN_DATA: [insn ~~TRUE~~> producer]:
4592 check --TRUE--> producer ??? or ANTI ???
4593 twin --TRUE--> producer
4594 twin --ANTI--> check
4596 If BEGIN_CONTROL: [insn ~~ANTI~~> producer]:
4597 check --ANTI--> producer
4598 twin --ANTI--> producer
4599 twin --ANTI--> check
4601 If BE_IN_SPEC: [insn ~~TRUE~~> producer]:
4602 check ~~TRUE~~> producer
4603 twin ~~TRUE~~> producer
4604 twin --ANTI--> check */
4606 ds = DEP_STATUS (dep);
4608 if (ds & BEGIN_SPEC)
4610 gcc_assert (!mutate_p);
4614 init_dep_1 (new_dep, pro, check, DEP_TYPE (dep), ds);
4615 sd_add_dep (new_dep, false);
4617 if (rec != EXIT_BLOCK_PTR)
4619 DEP_CON (new_dep) = twin;
4620 sd_add_dep (new_dep, false);
4624 /* Second, remove backward dependencies of INSN. */
4625 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
4626 sd_iterator_cond (&sd_it, &dep);)
4628 if ((DEP_STATUS (dep) & BEGIN_SPEC)
4630 /* We can delete this dep because we overcome it with
4631 BEGIN_SPECULATION. */
4632 sd_delete_dep (sd_it);
4634 sd_iterator_next (&sd_it);
4637 /* Future Speculations. Determine what BE_IN speculations will be like. */
4640 /* Fields (DONE_SPEC (x) & BEGIN_SPEC) and CHECK_SPEC (x) are set only
4643 gcc_assert (!DONE_SPEC (insn));
4647 ds_t ts = TODO_SPEC (insn);
4649 DONE_SPEC (insn) = ts & BEGIN_SPEC;
4650 CHECK_SPEC (check) = ts & BEGIN_SPEC;
4652 /* Luckiness of future speculations solely depends upon initial
4653 BEGIN speculation. */
4654 if (ts & BEGIN_DATA)
4655 fs = set_dep_weak (fs, BE_IN_DATA, get_dep_weak (ts, BEGIN_DATA));
4656 if (ts & BEGIN_CONTROL)
4657 fs = set_dep_weak (fs, BE_IN_CONTROL,
4658 get_dep_weak (ts, BEGIN_CONTROL));
4661 CHECK_SPEC (check) = CHECK_SPEC (insn);
4663 /* Future speculations: call the helper. */
4664 process_insn_forw_deps_be_in_spec (insn, twin, fs);
4666 if (rec != EXIT_BLOCK_PTR)
4668 /* Which types of dependencies should we use here is,
4669 generally, machine-dependent question... But, for now,
4674 init_dep (new_dep, insn, check, REG_DEP_TRUE);
4675 sd_add_dep (new_dep, false);
4677 init_dep (new_dep, insn, twin, REG_DEP_OUTPUT);
4678 sd_add_dep (new_dep, false);
4682 if (spec_info->dump)
4683 fprintf (spec_info->dump, ";;\t\tRemoved simple check : %s\n",
4684 (*current_sched_info->print_insn) (insn, 0));
4686 /* Remove all dependencies of the INSN. */
4688 sd_it = sd_iterator_start (insn, (SD_LIST_FORW
4690 | SD_LIST_RES_BACK));
4691 while (sd_iterator_cond (&sd_it, &dep))
4692 sd_delete_dep (sd_it);
4695 /* If former check (INSN) already was moved to the ready (or queue)
4696 list, add new check (CHECK) there too. */
4697 if (QUEUE_INDEX (insn) != QUEUE_NOWHERE)
4700 /* Remove old check from instruction stream and free its
4702 sched_remove_insn (insn);
4705 init_dep (new_dep, check, twin, REG_DEP_ANTI);
4706 sd_add_dep (new_dep, false);
4710 init_dep_1 (new_dep, insn, check, REG_DEP_TRUE, DEP_TRUE | DEP_OUTPUT);
4711 sd_add_dep (new_dep, false);
4715 /* Fix priorities. If MUTATE_P is nonzero, this is not necessary,
4716 because it'll be done later in add_to_speculative_block. */
4718 rtx_vec_t priorities_roots = NULL;
4720 clear_priorities (twin, &priorities_roots);
4721 calc_priorities (priorities_roots);
4722 VEC_free (rtx, heap, priorities_roots);
4726 /* Removes dependency between instructions in the recovery block REC
4727 and usual region instructions. It keeps inner dependences so it
4728 won't be necessary to recompute them. */
4730 fix_recovery_deps (basic_block rec)
4732 rtx note, insn, jump, ready_list = 0;
4733 bitmap_head in_ready;
4736 bitmap_initialize (&in_ready, 0);
4738 /* NOTE - a basic block note. */
4739 note = NEXT_INSN (BB_HEAD (rec));
4740 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
4741 insn = BB_END (rec);
4742 gcc_assert (JUMP_P (insn));
4743 insn = PREV_INSN (insn);
4747 sd_iterator_def sd_it;
4750 for (sd_it = sd_iterator_start (insn, SD_LIST_FORW);
4751 sd_iterator_cond (&sd_it, &dep);)
4753 rtx consumer = DEP_CON (dep);
4755 if (BLOCK_FOR_INSN (consumer) != rec)
4757 sd_delete_dep (sd_it);
4759 if (!bitmap_bit_p (&in_ready, INSN_LUID (consumer)))
4761 ready_list = alloc_INSN_LIST (consumer, ready_list);
4762 bitmap_set_bit (&in_ready, INSN_LUID (consumer));
4767 gcc_assert ((DEP_STATUS (dep) & DEP_TYPES) == DEP_TRUE);
4769 sd_iterator_next (&sd_it);
4773 insn = PREV_INSN (insn);
4775 while (insn != note);
4777 bitmap_clear (&in_ready);
4779 /* Try to add instructions to the ready or queue list. */
4780 for (link = ready_list; link; link = XEXP (link, 1))
4781 try_ready (XEXP (link, 0));
4782 free_INSN_LIST_list (&ready_list);
4784 /* Fixing jump's dependences. */
4785 insn = BB_HEAD (rec);
4786 jump = BB_END (rec);
4788 gcc_assert (LABEL_P (insn));
4789 insn = NEXT_INSN (insn);
4791 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
4792 add_jump_dependencies (insn, jump);
4795 /* Change pattern of INSN to NEW_PAT. */
4797 sched_change_pattern (rtx insn, rtx new_pat)
4801 t = validate_change (insn, &PATTERN (insn), new_pat, 0);
4803 dfa_clear_single_insn_cache (insn);
4806 /* Change pattern of INSN to NEW_PAT. Invalidate cached haifa
4807 instruction data. */
4809 haifa_change_pattern (rtx insn, rtx new_pat)
4811 sched_change_pattern (insn, new_pat);
4813 /* Invalidate INSN_COST, so it'll be recalculated. */
4814 INSN_COST (insn) = -1;
4815 /* Invalidate INSN_TICK, so it'll be recalculated. */
4816 INSN_TICK (insn) = INVALID_TICK;
4819 /* -1 - can't speculate,
4820 0 - for speculation with REQUEST mode it is OK to use
4821 current instruction pattern,
4822 1 - need to change pattern for *NEW_PAT to be speculative. */
4824 sched_speculate_insn (rtx insn, ds_t request, rtx *new_pat)
4826 gcc_assert (current_sched_info->flags & DO_SPECULATION
4827 && (request & SPECULATIVE)
4828 && sched_insn_is_legitimate_for_speculation_p (insn, request));
4830 if ((request & spec_info->mask) != request)
4833 if (request & BE_IN_SPEC
4834 && !(request & BEGIN_SPEC))
4837 return targetm.sched.speculate_insn (insn, request, new_pat);
4841 haifa_speculate_insn (rtx insn, ds_t request, rtx *new_pat)
4843 gcc_assert (sched_deps_info->generate_spec_deps
4844 && !IS_SPECULATION_CHECK_P (insn));
4846 if (HAS_INTERNAL_DEP (insn)
4847 || SCHED_GROUP_P (insn))
4850 return sched_speculate_insn (insn, request, new_pat);
4853 /* Print some information about block BB, which starts with HEAD and
4854 ends with TAIL, before scheduling it.
4855 I is zero, if scheduler is about to start with the fresh ebb. */
4857 dump_new_block_header (int i, basic_block bb, rtx head, rtx tail)
4860 fprintf (sched_dump,
4861 ";; ======================================================\n");
4863 fprintf (sched_dump,
4864 ";; =====================ADVANCING TO=====================\n");
4865 fprintf (sched_dump,
4866 ";; -- basic block %d from %d to %d -- %s reload\n",
4867 bb->index, INSN_UID (head), INSN_UID (tail),
4868 (reload_completed ? "after" : "before"));
4869 fprintf (sched_dump,
4870 ";; ======================================================\n");
4871 fprintf (sched_dump, "\n");
4874 /* Unlink basic block notes and labels and saves them, so they
4875 can be easily restored. We unlink basic block notes in EBB to
4876 provide back-compatibility with the previous code, as target backends
4877 assume, that there'll be only instructions between
4878 current_sched_info->{head and tail}. We restore these notes as soon
4880 FIRST (LAST) is the first (last) basic block in the ebb.
4881 NB: In usual case (FIRST == LAST) nothing is really done. */
4883 unlink_bb_notes (basic_block first, basic_block last)
4885 /* We DON'T unlink basic block notes of the first block in the ebb. */
4889 bb_header = XNEWVEC (rtx, last_basic_block);
4891 /* Make a sentinel. */
4892 if (last->next_bb != EXIT_BLOCK_PTR)
4893 bb_header[last->next_bb->index] = 0;
4895 first = first->next_bb;
4898 rtx prev, label, note, next;
4900 label = BB_HEAD (last);
4901 if (LABEL_P (label))
4902 note = NEXT_INSN (label);
4905 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
4907 prev = PREV_INSN (label);
4908 next = NEXT_INSN (note);
4909 gcc_assert (prev && next);
4911 NEXT_INSN (prev) = next;
4912 PREV_INSN (next) = prev;
4914 bb_header[last->index] = label;
4919 last = last->prev_bb;
4924 /* Restore basic block notes.
4925 FIRST is the first basic block in the ebb. */
4927 restore_bb_notes (basic_block first)
4932 /* We DON'T unlink basic block notes of the first block in the ebb. */
4933 first = first->next_bb;
4934 /* Remember: FIRST is actually a second basic block in the ebb. */
4936 while (first != EXIT_BLOCK_PTR
4937 && bb_header[first->index])
4939 rtx prev, label, note, next;
4941 label = bb_header[first->index];
4942 prev = PREV_INSN (label);
4943 next = NEXT_INSN (prev);
4945 if (LABEL_P (label))
4946 note = NEXT_INSN (label);
4949 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
4951 bb_header[first->index] = 0;
4953 NEXT_INSN (prev) = label;
4954 NEXT_INSN (note) = next;
4955 PREV_INSN (next) = note;
4957 first = first->next_bb;
4965 Fix CFG after both in- and inter-block movement of
4966 control_flow_insn_p JUMP. */
4968 fix_jump_move (rtx jump)
4970 basic_block bb, jump_bb, jump_bb_next;
4972 bb = BLOCK_FOR_INSN (PREV_INSN (jump));
4973 jump_bb = BLOCK_FOR_INSN (jump);
4974 jump_bb_next = jump_bb->next_bb;
4976 gcc_assert (common_sched_info->sched_pass_id == SCHED_EBB_PASS
4977 || IS_SPECULATION_BRANCHY_CHECK_P (jump));
4979 if (!NOTE_INSN_BASIC_BLOCK_P (BB_END (jump_bb_next)))
4980 /* if jump_bb_next is not empty. */
4981 BB_END (jump_bb) = BB_END (jump_bb_next);
4983 if (BB_END (bb) != PREV_INSN (jump))
4984 /* Then there are instruction after jump that should be placed
4986 BB_END (jump_bb_next) = BB_END (bb);
4988 /* Otherwise jump_bb_next is empty. */
4989 BB_END (jump_bb_next) = NEXT_INSN (BB_HEAD (jump_bb_next));
4991 /* To make assertion in move_insn happy. */
4992 BB_END (bb) = PREV_INSN (jump);
4994 update_bb_for_insn (jump_bb_next);
4997 /* Fix CFG after interblock movement of control_flow_insn_p JUMP. */
4999 move_block_after_check (rtx jump)
5001 basic_block bb, jump_bb, jump_bb_next;
5004 bb = BLOCK_FOR_INSN (PREV_INSN (jump));
5005 jump_bb = BLOCK_FOR_INSN (jump);
5006 jump_bb_next = jump_bb->next_bb;
5008 update_bb_for_insn (jump_bb);
5010 gcc_assert (IS_SPECULATION_CHECK_P (jump)
5011 || IS_SPECULATION_CHECK_P (BB_END (jump_bb_next)));
5013 unlink_block (jump_bb_next);
5014 link_block (jump_bb_next, bb);
5018 move_succs (&(jump_bb->succs), bb);
5019 move_succs (&(jump_bb_next->succs), jump_bb);
5020 move_succs (&t, jump_bb_next);
5022 df_mark_solutions_dirty ();
5024 common_sched_info->fix_recovery_cfg
5025 (bb->index, jump_bb->index, jump_bb_next->index);
5028 /* Helper function for move_block_after_check.
5029 This functions attaches edge vector pointed to by SUCCSP to
5032 move_succs (VEC(edge,gc) **succsp, basic_block to)
5037 gcc_assert (to->succs == 0);
5039 to->succs = *succsp;
5041 FOR_EACH_EDGE (e, ei, to->succs)
5047 /* Remove INSN from the instruction stream.
5048 INSN should have any dependencies. */
5050 sched_remove_insn (rtx insn)
5052 sd_finish_insn (insn);
5054 change_queue_index (insn, QUEUE_NOWHERE);
5055 current_sched_info->add_remove_insn (insn, 1);
5059 /* Clear priorities of all instructions, that are forward dependent on INSN.
5060 Store in vector pointed to by ROOTS_PTR insns on which priority () should
5061 be invoked to initialize all cleared priorities. */
5063 clear_priorities (rtx insn, rtx_vec_t *roots_ptr)
5065 sd_iterator_def sd_it;
5067 bool insn_is_root_p = true;
5069 gcc_assert (QUEUE_INDEX (insn) != QUEUE_SCHEDULED);
5071 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
5073 rtx pro = DEP_PRO (dep);
5075 if (INSN_PRIORITY_STATUS (pro) >= 0
5076 && QUEUE_INDEX (insn) != QUEUE_SCHEDULED)
5078 /* If DEP doesn't contribute to priority then INSN itself should
5079 be added to priority roots. */
5080 if (contributes_to_priority_p (dep))
5081 insn_is_root_p = false;
5083 INSN_PRIORITY_STATUS (pro) = -1;
5084 clear_priorities (pro, roots_ptr);
5089 VEC_safe_push (rtx, heap, *roots_ptr, insn);
5092 /* Recompute priorities of instructions, whose priorities might have been
5093 changed. ROOTS is a vector of instructions whose priority computation will
5094 trigger initialization of all cleared priorities. */
5096 calc_priorities (rtx_vec_t roots)
5101 for (i = 0; VEC_iterate (rtx, roots, i, insn); i++)
5106 /* Add dependences between JUMP and other instructions in the recovery
5107 block. INSN is the first insn the recovery block. */
5109 add_jump_dependencies (rtx insn, rtx jump)
5113 insn = NEXT_INSN (insn);
5117 if (dep_list_size (insn) == 0)
5119 dep_def _new_dep, *new_dep = &_new_dep;
5121 init_dep (new_dep, insn, jump, REG_DEP_ANTI);
5122 sd_add_dep (new_dep, false);
5127 gcc_assert (!sd_lists_empty_p (jump, SD_LIST_BACK));
5130 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
5132 bb_note (basic_block bb)
5136 note = BB_HEAD (bb);
5138 note = NEXT_INSN (note);
5140 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
5144 #ifdef ENABLE_CHECKING
5145 /* Helper function for check_cfg.
5146 Return nonzero, if edge vector pointed to by EL has edge with TYPE in
5149 has_edge_p (VEC(edge,gc) *el, int type)
5154 FOR_EACH_EDGE (e, ei, el)
5155 if (e->flags & type)
5160 /* Search back, starting at INSN, for an insn that is not a
5161 NOTE_INSN_VAR_LOCATION. Don't search beyond HEAD, and return it if
5162 no such insn can be found. */
5164 prev_non_location_insn (rtx insn, rtx head)
5166 while (insn != head && NOTE_P (insn)
5167 && NOTE_KIND (insn) == NOTE_INSN_VAR_LOCATION)
5168 insn = PREV_INSN (insn);
5173 /* Check few properties of CFG between HEAD and TAIL.
5174 If HEAD (TAIL) is NULL check from the beginning (till the end) of the
5175 instruction stream. */
5177 check_cfg (rtx head, rtx tail)
5181 int not_first = 0, not_last;
5184 head = get_insns ();
5186 tail = get_last_insn ();
5187 next_tail = NEXT_INSN (tail);
5191 not_last = head != tail;
5194 gcc_assert (NEXT_INSN (PREV_INSN (head)) == head);
5196 gcc_assert (PREV_INSN (NEXT_INSN (head)) == head);
5199 || (NOTE_INSN_BASIC_BLOCK_P (head)
5201 || (not_first && !LABEL_P (PREV_INSN (head))))))
5203 gcc_assert (bb == 0);
5204 bb = BLOCK_FOR_INSN (head);
5206 gcc_assert (BB_HEAD (bb) == head);
5208 /* This is the case of jump table. See inside_basic_block_p (). */
5209 gcc_assert (LABEL_P (head) && !inside_basic_block_p (head));
5214 gcc_assert (!inside_basic_block_p (head));
5215 head = NEXT_INSN (head);
5219 gcc_assert (inside_basic_block_p (head)
5221 gcc_assert (BLOCK_FOR_INSN (head) == bb);
5225 head = NEXT_INSN (head);
5226 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (head));
5230 if (control_flow_insn_p (head))
5232 gcc_assert (prev_non_location_insn (BB_END (bb), head)
5235 if (any_uncondjump_p (head))
5236 gcc_assert (EDGE_COUNT (bb->succs) == 1
5237 && BARRIER_P (NEXT_INSN (head)));
5238 else if (any_condjump_p (head))
5239 gcc_assert (/* Usual case. */
5240 (EDGE_COUNT (bb->succs) > 1
5241 && !BARRIER_P (NEXT_INSN (head)))
5242 /* Or jump to the next instruction. */
5243 || (EDGE_COUNT (bb->succs) == 1
5244 && (BB_HEAD (EDGE_I (bb->succs, 0)->dest)
5245 == JUMP_LABEL (head))));
5247 if (BB_END (bb) == head)
5249 if (EDGE_COUNT (bb->succs) > 1)
5250 gcc_assert (control_flow_insn_p (prev_non_location_insn
5251 (head, BB_HEAD (bb)))
5252 || has_edge_p (bb->succs, EDGE_COMPLEX));
5256 head = NEXT_INSN (head);
5262 while (head != next_tail);
5264 gcc_assert (bb == 0);
5267 #endif /* ENABLE_CHECKING */
5269 /* Extend per basic block data structures. */
5273 if (sched_scan_info->extend_bb)
5274 sched_scan_info->extend_bb ();
5277 /* Init data for BB. */
5279 init_bb (basic_block bb)
5281 if (sched_scan_info->init_bb)
5282 sched_scan_info->init_bb (bb);
5285 /* Extend per insn data structures. */
5289 if (sched_scan_info->extend_insn)
5290 sched_scan_info->extend_insn ();
5293 /* Init data structures for INSN. */
5295 init_insn (rtx insn)
5297 if (sched_scan_info->init_insn)
5298 sched_scan_info->init_insn (insn);
5301 /* Init all insns in BB. */
5303 init_insns_in_bb (basic_block bb)
5307 FOR_BB_INSNS (bb, insn)
5311 /* A driver function to add a set of basic blocks (BBS),
5312 a single basic block (BB), a set of insns (INSNS) or a single insn (INSN)
5313 to the scheduling region. */
5315 sched_scan (const struct sched_scan_info_def *ssi,
5316 bb_vec_t bbs, basic_block bb, insn_vec_t insns, rtx insn)
5318 sched_scan_info = ssi;
5320 if (bbs != NULL || bb != NULL)
5329 for (i = 0; VEC_iterate (basic_block, bbs, i, x); i++)
5344 for (i = 0; VEC_iterate (basic_block, bbs, i, x); i++)
5345 init_insns_in_bb (x);
5349 init_insns_in_bb (bb);
5356 for (i = 0; VEC_iterate (rtx, insns, i, x); i++)
5365 /* Extend data structures for logical insn UID. */
5367 luids_extend_insn (void)
5369 int new_luids_max_uid = get_max_uid () + 1;
5371 VEC_safe_grow_cleared (int, heap, sched_luids, new_luids_max_uid);
5374 /* Initialize LUID for INSN. */
5376 luids_init_insn (rtx insn)
5378 int i = INSN_P (insn) ? 1 : common_sched_info->luid_for_non_insn (insn);
5383 luid = sched_max_luid;
5384 sched_max_luid += i;
5389 SET_INSN_LUID (insn, luid);
5392 /* Initialize luids for BBS, BB, INSNS and INSN.
5393 The hook common_sched_info->luid_for_non_insn () is used to determine
5394 if notes, labels, etc. need luids. */
5396 sched_init_luids (bb_vec_t bbs, basic_block bb, insn_vec_t insns, rtx insn)
5398 const struct sched_scan_info_def ssi =
5400 NULL, /* extend_bb */
5402 luids_extend_insn, /* extend_insn */
5403 luids_init_insn /* init_insn */
5406 sched_scan (&ssi, bbs, bb, insns, insn);
5411 sched_finish_luids (void)
5413 VEC_free (int, heap, sched_luids);
5417 /* Return logical uid of INSN. Helpful while debugging. */
5419 insn_luid (rtx insn)
5421 return INSN_LUID (insn);
5424 /* Extend per insn data in the target. */
5426 sched_extend_target (void)
5428 if (targetm.sched.h_i_d_extended)
5429 targetm.sched.h_i_d_extended ();
5432 /* Extend global scheduler structures (those, that live across calls to
5433 schedule_block) to include information about just emitted INSN. */
5437 int reserve = (get_max_uid () + 1
5438 - VEC_length (haifa_insn_data_def, h_i_d));
5440 && ! VEC_space (haifa_insn_data_def, h_i_d, reserve))
5442 VEC_safe_grow_cleared (haifa_insn_data_def, heap, h_i_d,
5443 3 * get_max_uid () / 2);
5444 sched_extend_target ();
5448 /* Initialize h_i_d entry of the INSN with default values.
5449 Values, that are not explicitly initialized here, hold zero. */
5451 init_h_i_d (rtx insn)
5453 if (INSN_LUID (insn) > 0)
5455 INSN_COST (insn) = -1;
5456 QUEUE_INDEX (insn) = QUEUE_NOWHERE;
5457 INSN_TICK (insn) = INVALID_TICK;
5458 INTER_TICK (insn) = INVALID_TICK;
5459 TODO_SPEC (insn) = HARD_DEP;
5463 /* Initialize haifa_insn_data for BBS, BB, INSNS and INSN. */
5465 haifa_init_h_i_d (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 extend_h_i_d, /* extend_insn */
5472 init_h_i_d /* init_insn */
5475 sched_scan (&ssi, bbs, bb, insns, insn);
5478 /* Finalize haifa_insn_data. */
5480 haifa_finish_h_i_d (void)
5483 haifa_insn_data_t data;
5484 struct reg_use_data *use, *next;
5486 for (i = 0; VEC_iterate (haifa_insn_data_def, h_i_d, i, data); i++)
5488 if (data->reg_pressure != NULL)
5489 free (data->reg_pressure);
5490 for (use = data->reg_use_list; use != NULL; use = next)
5492 next = use->next_insn_use;
5496 VEC_free (haifa_insn_data_def, heap, h_i_d);
5499 /* Init data for the new insn INSN. */
5501 haifa_init_insn (rtx insn)
5503 gcc_assert (insn != NULL);
5505 sched_init_luids (NULL, NULL, NULL, insn);
5506 sched_extend_target ();
5507 sched_deps_init (false);
5508 haifa_init_h_i_d (NULL, NULL, NULL, insn);
5510 if (adding_bb_to_current_region_p)
5512 sd_init_insn (insn);
5514 /* Extend dependency caches by one element. */
5515 extend_dependency_caches (1, false);
5519 /* Init data for the new basic block BB which comes after AFTER. */
5521 haifa_init_only_bb (basic_block bb, basic_block after)
5523 gcc_assert (bb != NULL);
5527 if (common_sched_info->add_block)
5528 /* This changes only data structures of the front-end. */
5529 common_sched_info->add_block (bb, after);
5532 /* A generic version of sched_split_block (). */
5534 sched_split_block_1 (basic_block first_bb, rtx after)
5538 e = split_block (first_bb, after);
5539 gcc_assert (e->src == first_bb);
5541 /* sched_split_block emits note if *check == BB_END. Probably it
5542 is better to rip that note off. */
5547 /* A generic version of sched_create_empty_bb (). */
5549 sched_create_empty_bb_1 (basic_block after)
5551 return create_empty_bb (after);
5554 /* Insert PAT as an INSN into the schedule and update the necessary data
5555 structures to account for it. */
5557 sched_emit_insn (rtx pat)
5559 rtx insn = emit_insn_after (pat, last_scheduled_insn);
5560 last_scheduled_insn = insn;
5561 haifa_init_insn (insn);
5565 #endif /* INSN_SCHEDULING */