1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
3 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
4 Free Software Foundation, Inc.
5 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
6 and currently maintained by, Jim Wilson (wilson@cygnus.com)
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
24 /* Instruction scheduling pass. This file, along with sched-deps.c,
25 contains the generic parts. The actual entry point is found for
26 the normal instruction scheduling pass is found in sched-rgn.c.
28 We compute insn priorities based on data dependencies. Flow
29 analysis only creates a fraction of the data-dependencies we must
30 observe: namely, only those dependencies which the combiner can be
31 expected to use. For this pass, we must therefore create the
32 remaining dependencies we need to observe: register dependencies,
33 memory dependencies, dependencies to keep function calls in order,
34 and the dependence between a conditional branch and the setting of
35 condition codes are all dealt with here.
37 The scheduler first traverses the data flow graph, starting with
38 the last instruction, and proceeding to the first, assigning values
39 to insn_priority as it goes. This sorts the instructions
40 topologically by data dependence.
42 Once priorities have been established, we order the insns using
43 list scheduling. This works as follows: starting with a list of
44 all the ready insns, and sorted according to priority number, we
45 schedule the insn from the end of the list by placing its
46 predecessors in the list according to their priority order. We
47 consider this insn scheduled by setting the pointer to the "end" of
48 the list to point to the previous insn. When an insn has no
49 predecessors, we either queue it until sufficient time has elapsed
50 or add it to the ready list. As the instructions are scheduled or
51 when stalls are introduced, the queue advances and dumps insns into
52 the ready list. When all insns down to the lowest priority have
53 been scheduled, the critical path of the basic block has been made
54 as short as possible. The remaining insns are then scheduled in
57 The following list shows the order in which we want to break ties
58 among insns in the ready list:
60 1. choose insn with the longest path to end of bb, ties
62 2. choose insn with least contribution to register pressure,
64 3. prefer in-block upon interblock motion, ties broken by
65 4. prefer useful upon speculative motion, ties broken by
66 5. choose insn with largest control flow probability, ties
68 6. choose insn with the least dependences upon the previously
69 scheduled insn, or finally
70 7 choose the insn which has the most insns dependent on it.
71 8. choose insn with lowest UID.
73 Memory references complicate matters. Only if we can be certain
74 that memory references are not part of the data dependency graph
75 (via true, anti, or output dependence), can we move operations past
76 memory references. To first approximation, reads can be done
77 independently, while writes introduce dependencies. Better
78 approximations will yield fewer dependencies.
80 Before reload, an extended analysis of interblock data dependences
81 is required for interblock scheduling. This is performed in
82 compute_block_backward_dependences ().
84 Dependencies set up by memory references are treated in exactly the
85 same way as other dependencies, by using insn backward dependences
86 INSN_BACK_DEPS. INSN_BACK_DEPS are translated into forward dependences
87 INSN_FORW_DEPS the purpose of forward list scheduling.
89 Having optimized the critical path, we may have also unduly
90 extended the lifetimes of some registers. If an operation requires
91 that constants be loaded into registers, it is certainly desirable
92 to load those constants as early as necessary, but no earlier.
93 I.e., it will not do to load up a bunch of registers at the
94 beginning of a basic block only to use them at the end, if they
95 could be loaded later, since this may result in excessive register
98 Note that since branches are never in basic blocks, but only end
99 basic blocks, this pass will not move branches. But that is ok,
100 since we can use GNU's delayed branch scheduling pass to take care
103 Also note that no further optimizations based on algebraic
104 identities are performed, so this pass would be a good one to
105 perform instruction splitting, such as breaking up a multiply
106 instruction into shifts and adds where that is profitable.
108 Given the memory aliasing analysis that this pass should perform,
109 it should be possible to remove redundant stores to memory, and to
110 load values from registers instead of hitting memory.
112 Before reload, speculative insns are moved only if a 'proof' exists
113 that no exception will be caused by this, and if no live registers
114 exist that inhibit the motion (live registers constraints are not
115 represented by data dependence edges).
117 This pass must update information that subsequent passes expect to
118 be correct. Namely: reg_n_refs, reg_n_sets, reg_n_deaths,
119 reg_n_calls_crossed, and reg_live_length. Also, BB_HEAD, BB_END.
121 The information in the line number notes is carefully retained by
122 this pass. Notes that refer to the starting and ending of
123 exception regions are also carefully retained by this pass. All
124 other NOTE insns are grouped in their same relative order at the
125 beginning of basic blocks and regions that have been scheduled. */
129 #include "coretypes.h"
131 #include "diagnostic-core.h"
134 #include "hard-reg-set.h"
136 #include "function.h"
138 #include "insn-config.h"
139 #include "insn-attr.h"
142 #include "sched-int.h"
144 #include "common/common-target.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 int sched_verbose = 0;
172 /* Debugging file. All printouts are sent to dump, which is always set,
173 either to stderr, or to the dump listing file (-dRS). */
174 FILE *sched_dump = 0;
176 /* This is a placeholder for the scheduler parameters common
177 to all schedulers. */
178 struct common_sched_info_def *common_sched_info;
180 #define INSN_TICK(INSN) (HID (INSN)->tick)
181 #define INTER_TICK(INSN) (HID (INSN)->inter_tick)
183 /* If INSN_TICK of an instruction is equal to INVALID_TICK,
184 then it should be recalculated from scratch. */
185 #define INVALID_TICK (-(max_insn_queue_index + 1))
186 /* The minimal value of the INSN_TICK of an instruction. */
187 #define MIN_TICK (-max_insn_queue_index)
189 /* List of important notes we must keep around. This is a pointer to the
190 last element in the list. */
193 static struct spec_info_def spec_info_var;
194 /* Description of the speculative part of the scheduling.
195 If NULL - no speculation. */
196 spec_info_t spec_info = NULL;
198 /* True, if recovery block was added during scheduling of current block.
199 Used to determine, if we need to fix INSN_TICKs. */
200 static bool haifa_recovery_bb_recently_added_p;
202 /* True, if recovery block was added during this scheduling pass.
203 Used to determine if we should have empty memory pools of dependencies
204 after finishing current region. */
205 bool haifa_recovery_bb_ever_added_p;
207 /* Counters of different types of speculative instructions. */
208 static int nr_begin_data, nr_be_in_data, nr_begin_control, nr_be_in_control;
210 /* Array used in {unlink, restore}_bb_notes. */
211 static rtx *bb_header = 0;
213 /* Basic block after which recovery blocks will be created. */
214 static basic_block before_recovery;
216 /* Basic block just before the EXIT_BLOCK and after recovery, if we have
218 basic_block after_recovery;
220 /* FALSE if we add bb to another region, so we don't need to initialize it. */
221 bool adding_bb_to_current_region_p = true;
225 /* An instruction is ready to be scheduled when all insns preceding it
226 have already been scheduled. It is important to ensure that all
227 insns which use its result will not be executed until its result
228 has been computed. An insn is maintained in one of four structures:
230 (P) the "Pending" set of insns which cannot be scheduled until
231 their dependencies have been satisfied.
232 (Q) the "Queued" set of insns that can be scheduled when sufficient
234 (R) the "Ready" list of unscheduled, uncommitted insns.
235 (S) the "Scheduled" list of insns.
237 Initially, all insns are either "Pending" or "Ready" depending on
238 whether their dependencies are satisfied.
240 Insns move from the "Ready" list to the "Scheduled" list as they
241 are committed to the schedule. As this occurs, the insns in the
242 "Pending" list have their dependencies satisfied and move to either
243 the "Ready" list or the "Queued" set depending on whether
244 sufficient time has passed to make them ready. As time passes,
245 insns move from the "Queued" set to the "Ready" list.
247 The "Pending" list (P) are the insns in the INSN_FORW_DEPS of the
248 unscheduled insns, i.e., those that are ready, queued, and pending.
249 The "Queued" set (Q) is implemented by the variable `insn_queue'.
250 The "Ready" list (R) is implemented by the variables `ready' and
252 The "Scheduled" list (S) is the new insn chain built by this pass.
254 The transition (R->S) is implemented in the scheduling loop in
255 `schedule_block' when the best insn to schedule is chosen.
256 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
257 insns move from the ready list to the scheduled list.
258 The transition (Q->R) is implemented in 'queue_to_insn' as time
259 passes or stalls are introduced. */
261 /* Implement a circular buffer to delay instructions until sufficient
262 time has passed. For the new pipeline description interface,
263 MAX_INSN_QUEUE_INDEX is a power of two minus one which is not less
264 than maximal time of instruction execution computed by genattr.c on
265 the base maximal time of functional unit reservations and getting a
266 result. This is the longest time an insn may be queued. */
268 static rtx *insn_queue;
269 static int q_ptr = 0;
270 static int q_size = 0;
271 #define NEXT_Q(X) (((X)+1) & max_insn_queue_index)
272 #define NEXT_Q_AFTER(X, C) (((X)+C) & max_insn_queue_index)
274 #define QUEUE_SCHEDULED (-3)
275 #define QUEUE_NOWHERE (-2)
276 #define QUEUE_READY (-1)
277 /* QUEUE_SCHEDULED - INSN is scheduled.
278 QUEUE_NOWHERE - INSN isn't scheduled yet and is neither in
280 QUEUE_READY - INSN is in ready list.
281 N >= 0 - INSN queued for X [where NEXT_Q_AFTER (q_ptr, X) == N] cycles. */
283 #define QUEUE_INDEX(INSN) (HID (INSN)->queue_index)
285 /* The following variable value refers for all current and future
286 reservations of the processor units. */
289 /* The following variable value is size of memory representing all
290 current and future reservations of the processor units. */
291 size_t dfa_state_size;
293 /* The following array is used to find the best insn from ready when
294 the automaton pipeline interface is used. */
295 char *ready_try = NULL;
297 /* The ready list. */
298 struct ready_list ready = {NULL, 0, 0, 0, 0};
300 /* The pointer to the ready list (to be removed). */
301 static struct ready_list *readyp = &ready;
303 /* Scheduling clock. */
304 static int clock_var;
306 /* This records the actual schedule. It is built up during the main phase
307 of schedule_block, and afterwards used to reorder the insns in the RTL. */
308 static VEC(rtx, heap) *scheduled_insns;
310 static int may_trap_exp (const_rtx, int);
312 /* Nonzero iff the address is comprised from at most 1 register. */
313 #define CONST_BASED_ADDRESS_P(x) \
315 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
316 || (GET_CODE (x) == LO_SUM)) \
317 && (CONSTANT_P (XEXP (x, 0)) \
318 || CONSTANT_P (XEXP (x, 1)))))
320 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
321 as found by analyzing insn's expression. */
324 static int haifa_luid_for_non_insn (rtx x);
326 /* Haifa version of sched_info hooks common to all headers. */
327 const struct common_sched_info_def haifa_common_sched_info =
329 NULL, /* fix_recovery_cfg */
330 NULL, /* add_block */
331 NULL, /* estimate_number_of_insns */
332 haifa_luid_for_non_insn, /* luid_for_non_insn */
333 SCHED_PASS_UNKNOWN /* sched_pass_id */
336 /* Mapping from instruction UID to its Logical UID. */
337 VEC (int, heap) *sched_luids = NULL;
339 /* Next LUID to assign to an instruction. */
340 int sched_max_luid = 1;
342 /* Haifa Instruction Data. */
343 VEC (haifa_insn_data_def, heap) *h_i_d = NULL;
345 void (* sched_init_only_bb) (basic_block, basic_block);
347 /* Split block function. Different schedulers might use different functions
348 to handle their internal data consistent. */
349 basic_block (* sched_split_block) (basic_block, rtx);
351 /* Create empty basic block after the specified block. */
352 basic_block (* sched_create_empty_bb) (basic_block);
355 may_trap_exp (const_rtx x, int is_store)
364 if (code == MEM && may_trap_p (x))
371 /* The insn uses memory: a volatile load. */
372 if (MEM_VOLATILE_P (x))
374 /* An exception-free load. */
377 /* A load with 1 base register, to be further checked. */
378 if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))
379 return PFREE_CANDIDATE;
380 /* No info on the load, to be further checked. */
381 return PRISKY_CANDIDATE;
386 int i, insn_class = TRAP_FREE;
388 /* Neither store nor load, check if it may cause a trap. */
391 /* Recursive step: walk the insn... */
392 fmt = GET_RTX_FORMAT (code);
393 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
397 int tmp_class = may_trap_exp (XEXP (x, i), is_store);
398 insn_class = WORST_CLASS (insn_class, tmp_class);
400 else if (fmt[i] == 'E')
403 for (j = 0; j < XVECLEN (x, i); j++)
405 int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);
406 insn_class = WORST_CLASS (insn_class, tmp_class);
407 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
411 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
418 /* Classifies rtx X of an insn for the purpose of verifying that X can be
419 executed speculatively (and consequently the insn can be moved
420 speculatively), by examining X, returning:
421 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
422 TRAP_FREE: non-load insn.
423 IFREE: load from a globally safe location.
424 IRISKY: volatile load.
425 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
426 being either PFREE or PRISKY. */
429 haifa_classify_rtx (const_rtx x)
431 int tmp_class = TRAP_FREE;
432 int insn_class = TRAP_FREE;
435 if (GET_CODE (x) == PARALLEL)
437 int i, len = XVECLEN (x, 0);
439 for (i = len - 1; i >= 0; i--)
441 tmp_class = haifa_classify_rtx (XVECEXP (x, 0, i));
442 insn_class = WORST_CLASS (insn_class, tmp_class);
443 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
453 /* Test if it is a 'store'. */
454 tmp_class = may_trap_exp (XEXP (x, 0), 1);
457 /* Test if it is a store. */
458 tmp_class = may_trap_exp (SET_DEST (x), 1);
459 if (tmp_class == TRAP_RISKY)
461 /* Test if it is a load. */
463 WORST_CLASS (tmp_class,
464 may_trap_exp (SET_SRC (x), 0));
467 tmp_class = haifa_classify_rtx (COND_EXEC_CODE (x));
468 if (tmp_class == TRAP_RISKY)
470 tmp_class = WORST_CLASS (tmp_class,
471 may_trap_exp (COND_EXEC_TEST (x), 0));
474 tmp_class = TRAP_RISKY;
478 insn_class = tmp_class;
485 haifa_classify_insn (const_rtx insn)
487 return haifa_classify_rtx (PATTERN (insn));
490 /* Forward declarations. */
492 static int priority (rtx);
493 static int rank_for_schedule (const void *, const void *);
494 static void swap_sort (rtx *, int);
495 static void queue_insn (rtx, int, const char *);
496 static int schedule_insn (rtx);
497 static void adjust_priority (rtx);
498 static void advance_one_cycle (void);
499 static void extend_h_i_d (void);
502 /* Notes handling mechanism:
503 =========================
504 Generally, NOTES are saved before scheduling and restored after scheduling.
505 The scheduler distinguishes between two types of notes:
507 (1) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
508 Before scheduling a region, a pointer to the note is added to the insn
509 that follows or precedes it. (This happens as part of the data dependence
510 computation). After scheduling an insn, the pointer contained in it is
511 used for regenerating the corresponding note (in reemit_notes).
513 (2) All other notes (e.g. INSN_DELETED): Before scheduling a block,
514 these notes are put in a list (in rm_other_notes() and
515 unlink_other_notes ()). After scheduling the block, these notes are
516 inserted at the beginning of the block (in schedule_block()). */
518 static void ready_add (struct ready_list *, rtx, bool);
519 static rtx ready_remove_first (struct ready_list *);
520 static rtx ready_remove_first_dispatch (struct ready_list *ready);
522 static void queue_to_ready (struct ready_list *);
523 static int early_queue_to_ready (state_t, struct ready_list *);
525 static void debug_ready_list (struct ready_list *);
527 /* The following functions are used to implement multi-pass scheduling
528 on the first cycle. */
529 static rtx ready_remove (struct ready_list *, int);
530 static void ready_remove_insn (rtx);
532 static void fix_inter_tick (rtx, rtx);
533 static int fix_tick_ready (rtx);
534 static void change_queue_index (rtx, int);
536 /* The following functions are used to implement scheduling of data/control
537 speculative instructions. */
539 static void extend_h_i_d (void);
540 static void init_h_i_d (rtx);
541 static void generate_recovery_code (rtx);
542 static void process_insn_forw_deps_be_in_spec (rtx, rtx, ds_t);
543 static void begin_speculative_block (rtx);
544 static void add_to_speculative_block (rtx);
545 static void init_before_recovery (basic_block *);
546 static void create_check_block_twin (rtx, bool);
547 static void fix_recovery_deps (basic_block);
548 static void haifa_change_pattern (rtx, rtx);
549 static void dump_new_block_header (int, basic_block, rtx, rtx);
550 static void restore_bb_notes (basic_block);
551 static void fix_jump_move (rtx);
552 static void move_block_after_check (rtx);
553 static void move_succs (VEC(edge,gc) **, basic_block);
554 static void sched_remove_insn (rtx);
555 static void clear_priorities (rtx, rtx_vec_t *);
556 static void calc_priorities (rtx_vec_t);
557 static void add_jump_dependencies (rtx, rtx);
558 #ifdef ENABLE_CHECKING
559 static int has_edge_p (VEC(edge,gc) *, int);
560 static void check_cfg (rtx, rtx);
563 #endif /* INSN_SCHEDULING */
565 /* Point to state used for the current scheduling pass. */
566 struct haifa_sched_info *current_sched_info;
568 #ifndef INSN_SCHEDULING
570 schedule_insns (void)
575 /* Do register pressure sensitive insn scheduling if the flag is set
577 bool sched_pressure_p;
579 /* Map regno -> its pressure class. The map defined only when
580 SCHED_PRESSURE_P is true. */
581 enum reg_class *sched_regno_pressure_class;
583 /* The current register pressure. Only elements corresponding pressure
584 classes are defined. */
585 static int curr_reg_pressure[N_REG_CLASSES];
587 /* Saved value of the previous array. */
588 static int saved_reg_pressure[N_REG_CLASSES];
590 /* Register living at given scheduling point. */
591 static bitmap curr_reg_live;
593 /* Saved value of the previous array. */
594 static bitmap saved_reg_live;
596 /* Registers mentioned in the current region. */
597 static bitmap region_ref_regs;
599 /* Initiate register pressure relative info for scheduling the current
600 region. Currently it is only clearing register mentioned in the
603 sched_init_region_reg_pressure_info (void)
605 bitmap_clear (region_ref_regs);
608 /* Update current register pressure related info after birth (if
609 BIRTH_P) or death of register REGNO. */
611 mark_regno_birth_or_death (int regno, bool birth_p)
613 enum reg_class pressure_class;
615 pressure_class = sched_regno_pressure_class[regno];
616 if (regno >= FIRST_PSEUDO_REGISTER)
618 if (pressure_class != NO_REGS)
622 bitmap_set_bit (curr_reg_live, regno);
623 curr_reg_pressure[pressure_class]
624 += (ira_reg_class_max_nregs
625 [pressure_class][PSEUDO_REGNO_MODE (regno)]);
629 bitmap_clear_bit (curr_reg_live, regno);
630 curr_reg_pressure[pressure_class]
631 -= (ira_reg_class_max_nregs
632 [pressure_class][PSEUDO_REGNO_MODE (regno)]);
636 else if (pressure_class != NO_REGS
637 && ! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
641 bitmap_set_bit (curr_reg_live, regno);
642 curr_reg_pressure[pressure_class]++;
646 bitmap_clear_bit (curr_reg_live, regno);
647 curr_reg_pressure[pressure_class]--;
652 /* Initiate current register pressure related info from living
653 registers given by LIVE. */
655 initiate_reg_pressure_info (bitmap live)
661 for (i = 0; i < ira_pressure_classes_num; i++)
662 curr_reg_pressure[ira_pressure_classes[i]] = 0;
663 bitmap_clear (curr_reg_live);
664 EXECUTE_IF_SET_IN_BITMAP (live, 0, j, bi)
665 if (current_nr_blocks == 1 || bitmap_bit_p (region_ref_regs, j))
666 mark_regno_birth_or_death (j, true);
669 /* Mark registers in X as mentioned in the current region. */
671 setup_ref_regs (rtx x)
674 const RTX_CODE code = GET_CODE (x);
680 if (HARD_REGISTER_NUM_P (regno))
681 bitmap_set_range (region_ref_regs, regno,
682 hard_regno_nregs[regno][GET_MODE (x)]);
684 bitmap_set_bit (region_ref_regs, REGNO (x));
687 fmt = GET_RTX_FORMAT (code);
688 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
690 setup_ref_regs (XEXP (x, i));
691 else if (fmt[i] == 'E')
693 for (j = 0; j < XVECLEN (x, i); j++)
694 setup_ref_regs (XVECEXP (x, i, j));
698 /* Initiate current register pressure related info at the start of
701 initiate_bb_reg_pressure_info (basic_block bb)
703 unsigned int i ATTRIBUTE_UNUSED;
706 if (current_nr_blocks > 1)
707 FOR_BB_INSNS (bb, insn)
708 if (NONDEBUG_INSN_P (insn))
709 setup_ref_regs (PATTERN (insn));
710 initiate_reg_pressure_info (df_get_live_in (bb));
711 #ifdef EH_RETURN_DATA_REGNO
712 if (bb_has_eh_pred (bb))
715 unsigned int regno = EH_RETURN_DATA_REGNO (i);
717 if (regno == INVALID_REGNUM)
719 if (! bitmap_bit_p (df_get_live_in (bb), regno))
720 mark_regno_birth_or_death (regno, true);
725 /* Save current register pressure related info. */
727 save_reg_pressure (void)
731 for (i = 0; i < ira_pressure_classes_num; i++)
732 saved_reg_pressure[ira_pressure_classes[i]]
733 = curr_reg_pressure[ira_pressure_classes[i]];
734 bitmap_copy (saved_reg_live, curr_reg_live);
737 /* Restore saved register pressure related info. */
739 restore_reg_pressure (void)
743 for (i = 0; i < ira_pressure_classes_num; i++)
744 curr_reg_pressure[ira_pressure_classes[i]]
745 = saved_reg_pressure[ira_pressure_classes[i]];
746 bitmap_copy (curr_reg_live, saved_reg_live);
749 /* Return TRUE if the register is dying after its USE. */
751 dying_use_p (struct reg_use_data *use)
753 struct reg_use_data *next;
755 for (next = use->next_regno_use; next != use; next = next->next_regno_use)
756 if (NONDEBUG_INSN_P (next->insn)
757 && QUEUE_INDEX (next->insn) != QUEUE_SCHEDULED)
762 /* Print info about the current register pressure and its excess for
763 each pressure class. */
765 print_curr_reg_pressure (void)
770 fprintf (sched_dump, ";;\t");
771 for (i = 0; i < ira_pressure_classes_num; i++)
773 cl = ira_pressure_classes[i];
774 gcc_assert (curr_reg_pressure[cl] >= 0);
775 fprintf (sched_dump, " %s:%d(%d)", reg_class_names[cl],
776 curr_reg_pressure[cl],
777 curr_reg_pressure[cl] - ira_available_class_regs[cl]);
779 fprintf (sched_dump, "\n");
782 /* Pointer to the last instruction scheduled. */
783 static rtx last_scheduled_insn;
785 /* Pointer to the last nondebug instruction scheduled within the
786 block, or the prev_head of the scheduling block. Used by
787 rank_for_schedule, so that insns independent of the last scheduled
788 insn will be preferred over dependent instructions. */
789 static rtx last_nondebug_scheduled_insn;
791 /* Pointer that iterates through the list of unscheduled insns if we
792 have a dbg_cnt enabled. It always points at an insn prior to the
793 first unscheduled one. */
794 static rtx nonscheduled_insns_begin;
796 /* Cached cost of the instruction. Use below function to get cost of the
797 insn. -1 here means that the field is not initialized. */
798 #define INSN_COST(INSN) (HID (INSN)->cost)
800 /* Compute cost of executing INSN.
801 This is the number of cycles between instruction issue and
802 instruction results. */
810 if (recog_memoized (insn) < 0)
813 cost = insn_default_latency (insn);
820 cost = INSN_COST (insn);
824 /* A USE insn, or something else we don't need to
825 understand. We can't pass these directly to
826 result_ready_cost or insn_default_latency because it will
827 trigger a fatal error for unrecognizable insns. */
828 if (recog_memoized (insn) < 0)
830 INSN_COST (insn) = 0;
835 cost = insn_default_latency (insn);
839 INSN_COST (insn) = cost;
846 /* Compute cost of dependence LINK.
847 This is the number of cycles between instruction issue and
849 ??? We also use this function to call recog_memoized on all insns. */
851 dep_cost_1 (dep_t link, dw_t dw)
853 rtx insn = DEP_PRO (link);
854 rtx used = DEP_CON (link);
857 /* A USE insn should never require the value used to be computed.
858 This allows the computation of a function's result and parameter
859 values to overlap the return and call. We don't care about the
860 dependence cost when only decreasing register pressure. */
861 if (recog_memoized (used) < 0)
864 recog_memoized (insn);
868 enum reg_note dep_type = DEP_TYPE (link);
870 cost = insn_cost (insn);
872 if (INSN_CODE (insn) >= 0)
874 if (dep_type == REG_DEP_ANTI)
876 else if (dep_type == REG_DEP_OUTPUT)
878 cost = (insn_default_latency (insn)
879 - insn_default_latency (used));
883 else if (bypass_p (insn))
884 cost = insn_latency (insn, used);
888 if (targetm.sched.adjust_cost_2)
889 cost = targetm.sched.adjust_cost_2 (used, (int) dep_type, insn, cost,
891 else if (targetm.sched.adjust_cost != NULL)
893 /* This variable is used for backward compatibility with the
895 rtx dep_cost_rtx_link = alloc_INSN_LIST (NULL_RTX, NULL_RTX);
897 /* Make it self-cycled, so that if some tries to walk over this
898 incomplete list he/she will be caught in an endless loop. */
899 XEXP (dep_cost_rtx_link, 1) = dep_cost_rtx_link;
901 /* Targets use only REG_NOTE_KIND of the link. */
902 PUT_REG_NOTE_KIND (dep_cost_rtx_link, DEP_TYPE (link));
904 cost = targetm.sched.adjust_cost (used, dep_cost_rtx_link,
907 free_INSN_LIST_node (dep_cost_rtx_link);
917 /* Compute cost of dependence LINK.
918 This is the number of cycles between instruction issue and
919 instruction results. */
921 dep_cost (dep_t link)
923 return dep_cost_1 (link, 0);
926 /* Use this sel-sched.c friendly function in reorder2 instead of increasing
927 INSN_PRIORITY explicitly. */
929 increase_insn_priority (rtx insn, int amount)
933 /* We're dealing with haifa-sched.c INSN_PRIORITY. */
934 if (INSN_PRIORITY_KNOWN (insn))
935 INSN_PRIORITY (insn) += amount;
939 /* In sel-sched.c INSN_PRIORITY is not kept up to date.
940 Use EXPR_PRIORITY instead. */
941 sel_add_to_insn_priority (insn, amount);
945 /* Return 'true' if DEP should be included in priority calculations. */
947 contributes_to_priority_p (dep_t dep)
949 if (DEBUG_INSN_P (DEP_CON (dep))
950 || DEBUG_INSN_P (DEP_PRO (dep)))
953 /* Critical path is meaningful in block boundaries only. */
954 if (!current_sched_info->contributes_to_priority (DEP_CON (dep),
958 /* If flag COUNT_SPEC_IN_CRITICAL_PATH is set,
959 then speculative instructions will less likely be
960 scheduled. That is because the priority of
961 their producers will increase, and, thus, the
962 producers will more likely be scheduled, thus,
963 resolving the dependence. */
964 if (sched_deps_info->generate_spec_deps
965 && !(spec_info->flags & COUNT_SPEC_IN_CRITICAL_PATH)
966 && (DEP_STATUS (dep) & SPECULATIVE))
972 /* Compute the number of nondebug forward deps of an insn. */
975 dep_list_size (rtx insn)
977 sd_iterator_def sd_it;
979 int dbgcount = 0, nodbgcount = 0;
981 if (!MAY_HAVE_DEBUG_INSNS)
982 return sd_lists_size (insn, SD_LIST_FORW);
984 FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
986 if (DEBUG_INSN_P (DEP_CON (dep)))
988 else if (!DEBUG_INSN_P (DEP_PRO (dep)))
992 gcc_assert (dbgcount + nodbgcount == sd_lists_size (insn, SD_LIST_FORW));
997 /* Compute the priority number for INSN. */
1001 if (! INSN_P (insn))
1004 /* We should not be interested in priority of an already scheduled insn. */
1005 gcc_assert (QUEUE_INDEX (insn) != QUEUE_SCHEDULED);
1007 if (!INSN_PRIORITY_KNOWN (insn))
1009 int this_priority = -1;
1011 if (dep_list_size (insn) == 0)
1012 /* ??? We should set INSN_PRIORITY to insn_cost when and insn has
1013 some forward deps but all of them are ignored by
1014 contributes_to_priority hook. At the moment we set priority of
1016 this_priority = insn_cost (insn);
1019 rtx prev_first, twin;
1022 /* For recovery check instructions we calculate priority slightly
1023 different than that of normal instructions. Instead of walking
1024 through INSN_FORW_DEPS (check) list, we walk through
1025 INSN_FORW_DEPS list of each instruction in the corresponding
1028 /* Selective scheduling does not define RECOVERY_BLOCK macro. */
1029 rec = sel_sched_p () ? NULL : RECOVERY_BLOCK (insn);
1030 if (!rec || rec == EXIT_BLOCK_PTR)
1032 prev_first = PREV_INSN (insn);
1037 prev_first = NEXT_INSN (BB_HEAD (rec));
1038 twin = PREV_INSN (BB_END (rec));
1043 sd_iterator_def sd_it;
1046 FOR_EACH_DEP (twin, SD_LIST_FORW, sd_it, dep)
1051 next = DEP_CON (dep);
1053 if (BLOCK_FOR_INSN (next) != rec)
1057 if (!contributes_to_priority_p (dep))
1061 cost = dep_cost (dep);
1064 struct _dep _dep1, *dep1 = &_dep1;
1066 init_dep (dep1, insn, next, REG_DEP_ANTI);
1068 cost = dep_cost (dep1);
1071 next_priority = cost + priority (next);
1073 if (next_priority > this_priority)
1074 this_priority = next_priority;
1078 twin = PREV_INSN (twin);
1080 while (twin != prev_first);
1083 if (this_priority < 0)
1085 gcc_assert (this_priority == -1);
1087 this_priority = insn_cost (insn);
1090 INSN_PRIORITY (insn) = this_priority;
1091 INSN_PRIORITY_STATUS (insn) = 1;
1094 return INSN_PRIORITY (insn);
1097 /* Macros and functions for keeping the priority queue sorted, and
1098 dealing with queuing and dequeuing of instructions. */
1100 #define SCHED_SORT(READY, N_READY) \
1101 do { if ((N_READY) == 2) \
1102 swap_sort (READY, N_READY); \
1103 else if ((N_READY) > 2) \
1104 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
1107 /* Setup info about the current register pressure impact of scheduling
1108 INSN at the current scheduling point. */
1110 setup_insn_reg_pressure_info (rtx insn)
1112 int i, change, before, after, hard_regno;
1113 int excess_cost_change;
1114 enum machine_mode mode;
1116 struct reg_pressure_data *pressure_info;
1117 int *max_reg_pressure;
1118 struct reg_use_data *use;
1119 static int death[N_REG_CLASSES];
1121 gcc_checking_assert (!DEBUG_INSN_P (insn));
1123 excess_cost_change = 0;
1124 for (i = 0; i < ira_pressure_classes_num; i++)
1125 death[ira_pressure_classes[i]] = 0;
1126 for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
1127 if (dying_use_p (use))
1129 cl = sched_regno_pressure_class[use->regno];
1130 if (use->regno < FIRST_PSEUDO_REGISTER)
1134 += ira_reg_class_max_nregs[cl][PSEUDO_REGNO_MODE (use->regno)];
1136 pressure_info = INSN_REG_PRESSURE (insn);
1137 max_reg_pressure = INSN_MAX_REG_PRESSURE (insn);
1138 gcc_assert (pressure_info != NULL && max_reg_pressure != NULL);
1139 for (i = 0; i < ira_pressure_classes_num; i++)
1141 cl = ira_pressure_classes[i];
1142 gcc_assert (curr_reg_pressure[cl] >= 0);
1143 change = (int) pressure_info[i].set_increase - death[cl];
1144 before = MAX (0, max_reg_pressure[i] - ira_available_class_regs[cl]);
1145 after = MAX (0, max_reg_pressure[i] + change
1146 - ira_available_class_regs[cl]);
1147 hard_regno = ira_class_hard_regs[cl][0];
1148 gcc_assert (hard_regno >= 0);
1149 mode = reg_raw_mode[hard_regno];
1150 excess_cost_change += ((after - before)
1151 * (ira_memory_move_cost[mode][cl][0]
1152 + ira_memory_move_cost[mode][cl][1]));
1154 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insn) = excess_cost_change;
1157 /* Returns a positive value if x is preferred; returns a negative value if
1158 y is preferred. Should never return 0, since that will make the sort
1162 rank_for_schedule (const void *x, const void *y)
1164 rtx tmp = *(const rtx *) y;
1165 rtx tmp2 = *(const rtx *) x;
1166 int tmp_class, tmp2_class;
1167 int val, priority_val, info_val;
1169 if (MAY_HAVE_DEBUG_INSNS)
1171 /* Schedule debug insns as early as possible. */
1172 if (DEBUG_INSN_P (tmp) && !DEBUG_INSN_P (tmp2))
1174 else if (DEBUG_INSN_P (tmp2))
1178 /* The insn in a schedule group should be issued the first. */
1179 if (flag_sched_group_heuristic &&
1180 SCHED_GROUP_P (tmp) != SCHED_GROUP_P (tmp2))
1181 return SCHED_GROUP_P (tmp2) ? 1 : -1;
1183 /* Make sure that priority of TMP and TMP2 are initialized. */
1184 gcc_assert (INSN_PRIORITY_KNOWN (tmp) && INSN_PRIORITY_KNOWN (tmp2));
1186 if (sched_pressure_p)
1190 /* Prefer insn whose scheduling results in the smallest register
1192 if ((diff = (INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp)
1193 + (INSN_TICK (tmp) > clock_var
1194 ? INSN_TICK (tmp) - clock_var : 0)
1195 - INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp2)
1196 - (INSN_TICK (tmp2) > clock_var
1197 ? INSN_TICK (tmp2) - clock_var : 0))) != 0)
1202 if (sched_pressure_p
1203 && (INSN_TICK (tmp2) > clock_var || INSN_TICK (tmp) > clock_var))
1205 if (INSN_TICK (tmp) <= clock_var)
1207 else if (INSN_TICK (tmp2) <= clock_var)
1210 return INSN_TICK (tmp) - INSN_TICK (tmp2);
1212 /* Prefer insn with higher priority. */
1213 priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
1215 if (flag_sched_critical_path_heuristic && priority_val)
1216 return priority_val;
1218 /* Prefer speculative insn with greater dependencies weakness. */
1219 if (flag_sched_spec_insn_heuristic && spec_info)
1225 ds1 = TODO_SPEC (tmp) & SPECULATIVE;
1227 dw1 = ds_weak (ds1);
1231 ds2 = TODO_SPEC (tmp2) & SPECULATIVE;
1233 dw2 = ds_weak (ds2);
1238 if (dw > (NO_DEP_WEAK / 8) || dw < -(NO_DEP_WEAK / 8))
1242 info_val = (*current_sched_info->rank) (tmp, tmp2);
1243 if(flag_sched_rank_heuristic && info_val)
1246 /* Compare insns based on their relation to the last scheduled
1248 if (flag_sched_last_insn_heuristic && last_nondebug_scheduled_insn)
1252 rtx last = last_nondebug_scheduled_insn;
1254 /* Classify the instructions into three classes:
1255 1) Data dependent on last schedule insn.
1256 2) Anti/Output dependent on last scheduled insn.
1257 3) Independent of last scheduled insn, or has latency of one.
1258 Choose the insn from the highest numbered class if different. */
1259 dep1 = sd_find_dep_between (last, tmp, true);
1261 if (dep1 == NULL || dep_cost (dep1) == 1)
1263 else if (/* Data dependence. */
1264 DEP_TYPE (dep1) == REG_DEP_TRUE)
1269 dep2 = sd_find_dep_between (last, tmp2, true);
1271 if (dep2 == NULL || dep_cost (dep2) == 1)
1273 else if (/* Data dependence. */
1274 DEP_TYPE (dep2) == REG_DEP_TRUE)
1279 if ((val = tmp2_class - tmp_class))
1283 /* Prefer the insn which has more later insns that depend on it.
1284 This gives the scheduler more freedom when scheduling later
1285 instructions at the expense of added register pressure. */
1287 val = (dep_list_size (tmp2) - dep_list_size (tmp));
1289 if (flag_sched_dep_count_heuristic && val != 0)
1292 /* If insns are equally good, sort by INSN_LUID (original insn order),
1293 so that we make the sort stable. This minimizes instruction movement,
1294 thus minimizing sched's effect on debugging and cross-jumping. */
1295 return INSN_LUID (tmp) - INSN_LUID (tmp2);
1298 /* Resort the array A in which only element at index N may be out of order. */
1300 HAIFA_INLINE static void
1301 swap_sort (rtx *a, int n)
1303 rtx insn = a[n - 1];
1306 while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0)
1314 /* Add INSN to the insn queue so that it can be executed at least
1315 N_CYCLES after the currently executing insn. Preserve insns
1316 chain for debugging purposes. REASON will be printed in debugging
1319 HAIFA_INLINE static void
1320 queue_insn (rtx insn, int n_cycles, const char *reason)
1322 int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
1323 rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]);
1325 gcc_assert (n_cycles <= max_insn_queue_index);
1326 gcc_assert (!DEBUG_INSN_P (insn));
1328 insn_queue[next_q] = link;
1331 if (sched_verbose >= 2)
1333 fprintf (sched_dump, ";;\t\tReady-->Q: insn %s: ",
1334 (*current_sched_info->print_insn) (insn, 0));
1336 fprintf (sched_dump, "queued for %d cycles (%s).\n", n_cycles, reason);
1339 QUEUE_INDEX (insn) = next_q;
1342 /* Remove INSN from queue. */
1344 queue_remove (rtx insn)
1346 gcc_assert (QUEUE_INDEX (insn) >= 0);
1347 remove_free_INSN_LIST_elem (insn, &insn_queue[QUEUE_INDEX (insn)]);
1349 QUEUE_INDEX (insn) = QUEUE_NOWHERE;
1352 /* Return a pointer to the bottom of the ready list, i.e. the insn
1353 with the lowest priority. */
1356 ready_lastpos (struct ready_list *ready)
1358 gcc_assert (ready->n_ready >= 1);
1359 return ready->vec + ready->first - ready->n_ready + 1;
1362 /* Add an element INSN to the ready list so that it ends up with the
1363 lowest/highest priority depending on FIRST_P. */
1365 HAIFA_INLINE static void
1366 ready_add (struct ready_list *ready, rtx insn, bool first_p)
1370 if (ready->first == ready->n_ready)
1372 memmove (ready->vec + ready->veclen - ready->n_ready,
1373 ready_lastpos (ready),
1374 ready->n_ready * sizeof (rtx));
1375 ready->first = ready->veclen - 1;
1377 ready->vec[ready->first - ready->n_ready] = insn;
1381 if (ready->first == ready->veclen - 1)
1384 /* ready_lastpos() fails when called with (ready->n_ready == 0). */
1385 memmove (ready->vec + ready->veclen - ready->n_ready - 1,
1386 ready_lastpos (ready),
1387 ready->n_ready * sizeof (rtx));
1388 ready->first = ready->veclen - 2;
1390 ready->vec[++(ready->first)] = insn;
1394 if (DEBUG_INSN_P (insn))
1397 gcc_assert (QUEUE_INDEX (insn) != QUEUE_READY);
1398 QUEUE_INDEX (insn) = QUEUE_READY;
1401 /* Remove the element with the highest priority from the ready list and
1404 HAIFA_INLINE static rtx
1405 ready_remove_first (struct ready_list *ready)
1409 gcc_assert (ready->n_ready);
1410 t = ready->vec[ready->first--];
1412 if (DEBUG_INSN_P (t))
1414 /* If the queue becomes empty, reset it. */
1415 if (ready->n_ready == 0)
1416 ready->first = ready->veclen - 1;
1418 gcc_assert (QUEUE_INDEX (t) == QUEUE_READY);
1419 QUEUE_INDEX (t) = QUEUE_NOWHERE;
1424 /* The following code implements multi-pass scheduling for the first
1425 cycle. In other words, we will try to choose ready insn which
1426 permits to start maximum number of insns on the same cycle. */
1428 /* Return a pointer to the element INDEX from the ready. INDEX for
1429 insn with the highest priority is 0, and the lowest priority has
1433 ready_element (struct ready_list *ready, int index)
1435 gcc_assert (ready->n_ready && index < ready->n_ready);
1437 return ready->vec[ready->first - index];
1440 /* Remove the element INDEX from the ready list and return it. INDEX
1441 for insn with the highest priority is 0, and the lowest priority
1444 HAIFA_INLINE static rtx
1445 ready_remove (struct ready_list *ready, int index)
1451 return ready_remove_first (ready);
1452 gcc_assert (ready->n_ready && index < ready->n_ready);
1453 t = ready->vec[ready->first - index];
1455 if (DEBUG_INSN_P (t))
1457 for (i = index; i < ready->n_ready; i++)
1458 ready->vec[ready->first - i] = ready->vec[ready->first - i - 1];
1459 QUEUE_INDEX (t) = QUEUE_NOWHERE;
1463 /* Remove INSN from the ready list. */
1465 ready_remove_insn (rtx insn)
1469 for (i = 0; i < readyp->n_ready; i++)
1470 if (ready_element (readyp, i) == insn)
1472 ready_remove (readyp, i);
1478 /* Sort the ready list READY by ascending priority, using the SCHED_SORT
1482 ready_sort (struct ready_list *ready)
1485 rtx *first = ready_lastpos (ready);
1487 if (sched_pressure_p)
1489 for (i = 0; i < ready->n_ready; i++)
1490 if (!DEBUG_INSN_P (first[i]))
1491 setup_insn_reg_pressure_info (first[i]);
1493 SCHED_SORT (first, ready->n_ready);
1496 /* PREV is an insn that is ready to execute. Adjust its priority if that
1497 will help shorten or lengthen register lifetimes as appropriate. Also
1498 provide a hook for the target to tweak itself. */
1500 HAIFA_INLINE static void
1501 adjust_priority (rtx prev)
1503 /* ??? There used to be code here to try and estimate how an insn
1504 affected register lifetimes, but it did it by looking at REG_DEAD
1505 notes, which we removed in schedule_region. Nor did it try to
1506 take into account register pressure or anything useful like that.
1508 Revisit when we have a machine model to work with and not before. */
1510 if (targetm.sched.adjust_priority)
1511 INSN_PRIORITY (prev) =
1512 targetm.sched.adjust_priority (prev, INSN_PRIORITY (prev));
1515 /* Advance DFA state STATE on one cycle. */
1517 advance_state (state_t state)
1519 if (targetm.sched.dfa_pre_advance_cycle)
1520 targetm.sched.dfa_pre_advance_cycle ();
1522 if (targetm.sched.dfa_pre_cycle_insn)
1523 state_transition (state,
1524 targetm.sched.dfa_pre_cycle_insn ());
1526 state_transition (state, NULL);
1528 if (targetm.sched.dfa_post_cycle_insn)
1529 state_transition (state,
1530 targetm.sched.dfa_post_cycle_insn ());
1532 if (targetm.sched.dfa_post_advance_cycle)
1533 targetm.sched.dfa_post_advance_cycle ();
1536 /* Advance time on one cycle. */
1537 HAIFA_INLINE static void
1538 advance_one_cycle (void)
1540 advance_state (curr_state);
1541 if (sched_verbose >= 6)
1542 fprintf (sched_dump, ";;\tAdvanced a state.\n");
1545 /* Clock at which the previous instruction was issued. */
1546 static int last_clock_var;
1548 /* Update register pressure after scheduling INSN. */
1550 update_register_pressure (rtx insn)
1552 struct reg_use_data *use;
1553 struct reg_set_data *set;
1555 gcc_checking_assert (!DEBUG_INSN_P (insn));
1557 for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
1558 if (dying_use_p (use) && bitmap_bit_p (curr_reg_live, use->regno))
1559 mark_regno_birth_or_death (use->regno, false);
1560 for (set = INSN_REG_SET_LIST (insn); set != NULL; set = set->next_insn_set)
1561 mark_regno_birth_or_death (set->regno, true);
1564 /* Set up or update (if UPDATE_P) max register pressure (see its
1565 meaning in sched-int.h::_haifa_insn_data) for all current BB insns
1566 after insn AFTER. */
1568 setup_insn_max_reg_pressure (rtx after, bool update_p)
1573 static int max_reg_pressure[N_REG_CLASSES];
1575 save_reg_pressure ();
1576 for (i = 0; i < ira_pressure_classes_num; i++)
1577 max_reg_pressure[ira_pressure_classes[i]]
1578 = curr_reg_pressure[ira_pressure_classes[i]];
1579 for (insn = NEXT_INSN (after);
1580 insn != NULL_RTX && ! BARRIER_P (insn)
1581 && BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (after);
1582 insn = NEXT_INSN (insn))
1583 if (NONDEBUG_INSN_P (insn))
1586 for (i = 0; i < ira_pressure_classes_num; i++)
1588 p = max_reg_pressure[ira_pressure_classes[i]];
1589 if (INSN_MAX_REG_PRESSURE (insn)[i] != p)
1592 INSN_MAX_REG_PRESSURE (insn)[i]
1593 = max_reg_pressure[ira_pressure_classes[i]];
1596 if (update_p && eq_p)
1598 update_register_pressure (insn);
1599 for (i = 0; i < ira_pressure_classes_num; i++)
1600 if (max_reg_pressure[ira_pressure_classes[i]]
1601 < curr_reg_pressure[ira_pressure_classes[i]])
1602 max_reg_pressure[ira_pressure_classes[i]]
1603 = curr_reg_pressure[ira_pressure_classes[i]];
1605 restore_reg_pressure ();
1608 /* Update the current register pressure after scheduling INSN. Update
1609 also max register pressure for unscheduled insns of the current
1612 update_reg_and_insn_max_reg_pressure (rtx insn)
1615 int before[N_REG_CLASSES];
1617 for (i = 0; i < ira_pressure_classes_num; i++)
1618 before[i] = curr_reg_pressure[ira_pressure_classes[i]];
1619 update_register_pressure (insn);
1620 for (i = 0; i < ira_pressure_classes_num; i++)
1621 if (curr_reg_pressure[ira_pressure_classes[i]] != before[i])
1623 if (i < ira_pressure_classes_num)
1624 setup_insn_max_reg_pressure (insn, true);
1627 /* Set up register pressure at the beginning of basic block BB whose
1628 insns starting after insn AFTER. Set up also max register pressure
1629 for all insns of the basic block. */
1631 sched_setup_bb_reg_pressure_info (basic_block bb, rtx after)
1633 gcc_assert (sched_pressure_p);
1634 initiate_bb_reg_pressure_info (bb);
1635 setup_insn_max_reg_pressure (after, false);
1638 /* INSN is the "currently executing insn". Launch each insn which was
1639 waiting on INSN. READY is the ready list which contains the insns
1640 that are ready to fire. CLOCK is the current cycle. The function
1641 returns necessary cycle advance after issuing the insn (it is not
1642 zero for insns in a schedule group). */
1645 schedule_insn (rtx insn)
1647 sd_iterator_def sd_it;
1652 if (sched_verbose >= 1)
1654 struct reg_pressure_data *pressure_info;
1657 print_insn (buf, insn, 0);
1659 fprintf (sched_dump, ";;\t%3i--> %-40s:", clock_var, buf);
1661 if (recog_memoized (insn) < 0)
1662 fprintf (sched_dump, "nothing");
1664 print_reservation (sched_dump, insn);
1665 pressure_info = INSN_REG_PRESSURE (insn);
1666 if (pressure_info != NULL)
1668 fputc (':', sched_dump);
1669 for (i = 0; i < ira_pressure_classes_num; i++)
1670 fprintf (sched_dump, "%s%+d(%d)",
1671 reg_class_names[ira_pressure_classes[i]],
1672 pressure_info[i].set_increase, pressure_info[i].change);
1674 fputc ('\n', sched_dump);
1677 if (sched_pressure_p && !DEBUG_INSN_P (insn))
1678 update_reg_and_insn_max_reg_pressure (insn);
1680 /* Scheduling instruction should have all its dependencies resolved and
1681 should have been removed from the ready list. */
1682 gcc_assert (sd_lists_empty_p (insn, SD_LIST_BACK));
1684 /* Reset debug insns invalidated by moving this insn. */
1685 if (MAY_HAVE_DEBUG_INSNS && !DEBUG_INSN_P (insn))
1686 for (sd_it = sd_iterator_start (insn, SD_LIST_BACK);
1687 sd_iterator_cond (&sd_it, &dep);)
1689 rtx dbg = DEP_PRO (dep);
1690 struct reg_use_data *use, *next;
1692 gcc_assert (DEBUG_INSN_P (dbg));
1694 if (sched_verbose >= 6)
1695 fprintf (sched_dump, ";;\t\tresetting: debug insn %d\n",
1698 /* ??? Rather than resetting the debug insn, we might be able
1699 to emit a debug temp before the just-scheduled insn, but
1700 this would involve checking that the expression at the
1701 point of the debug insn is equivalent to the expression
1702 before the just-scheduled insn. They might not be: the
1703 expression in the debug insn may depend on other insns not
1704 yet scheduled that set MEMs, REGs or even other debug
1705 insns. It's not clear that attempting to preserve debug
1706 information in these cases is worth the effort, given how
1707 uncommon these resets are and the likelihood that the debug
1708 temps introduced won't survive the schedule change. */
1709 INSN_VAR_LOCATION_LOC (dbg) = gen_rtx_UNKNOWN_VAR_LOC ();
1710 df_insn_rescan (dbg);
1712 /* Unknown location doesn't use any registers. */
1713 for (use = INSN_REG_USE_LIST (dbg); use != NULL; use = next)
1715 struct reg_use_data *prev = use;
1717 /* Remove use from the cyclic next_regno_use chain first. */
1718 while (prev->next_regno_use != use)
1719 prev = prev->next_regno_use;
1720 prev->next_regno_use = use->next_regno_use;
1721 next = use->next_insn_use;
1724 INSN_REG_USE_LIST (dbg) = NULL;
1726 /* We delete rather than resolve these deps, otherwise we
1727 crash in sched_free_deps(), because forward deps are
1728 expected to be released before backward deps. */
1729 sd_delete_dep (sd_it);
1732 gcc_assert (QUEUE_INDEX (insn) == QUEUE_NOWHERE);
1733 QUEUE_INDEX (insn) = QUEUE_SCHEDULED;
1735 gcc_assert (INSN_TICK (insn) >= MIN_TICK);
1736 if (INSN_TICK (insn) > clock_var)
1737 /* INSN has been prematurely moved from the queue to the ready list.
1738 This is possible only if following flag is set. */
1739 gcc_assert (flag_sched_stalled_insns);
1741 /* ??? Probably, if INSN is scheduled prematurely, we should leave
1742 INSN_TICK untouched. This is a machine-dependent issue, actually. */
1743 INSN_TICK (insn) = clock_var;
1745 /* Update dependent instructions. */
1746 for (sd_it = sd_iterator_start (insn, SD_LIST_FORW);
1747 sd_iterator_cond (&sd_it, &dep);)
1749 rtx next = DEP_CON (dep);
1751 /* Resolve the dependence between INSN and NEXT.
1752 sd_resolve_dep () moves current dep to another list thus
1753 advancing the iterator. */
1754 sd_resolve_dep (sd_it);
1756 /* Don't bother trying to mark next as ready if insn is a debug
1757 insn. If insn is the last hard dependency, it will have
1758 already been discounted. */
1759 if (DEBUG_INSN_P (insn) && !DEBUG_INSN_P (next))
1762 if (!IS_SPECULATION_BRANCHY_CHECK_P (insn))
1766 effective_cost = try_ready (next);
1768 if (effective_cost >= 0
1769 && SCHED_GROUP_P (next)
1770 && advance < effective_cost)
1771 advance = effective_cost;
1774 /* Check always has only one forward dependence (to the first insn in
1775 the recovery block), therefore, this will be executed only once. */
1777 gcc_assert (sd_lists_empty_p (insn, SD_LIST_FORW));
1778 fix_recovery_deps (RECOVERY_BLOCK (insn));
1782 /* This is the place where scheduler doesn't *basically* need backward and
1783 forward dependencies for INSN anymore. Nevertheless they are used in
1784 heuristics in rank_for_schedule (), early_queue_to_ready () and in
1785 some targets (e.g. rs6000). Thus the earliest place where we *can*
1786 remove dependencies is after targetm.sched.finish () call in
1787 schedule_block (). But, on the other side, the safest place to remove
1788 dependencies is when we are finishing scheduling entire region. As we
1789 don't generate [many] dependencies during scheduling itself, we won't
1790 need memory until beginning of next region.
1791 Bottom line: Dependencies are removed for all insns in the end of
1792 scheduling the region. */
1794 /* Annotate the instruction with issue information -- TImode
1795 indicates that the instruction is expected not to be able
1796 to issue on the same cycle as the previous insn. A machine
1797 may use this information to decide how the instruction should
1800 && GET_CODE (PATTERN (insn)) != USE
1801 && GET_CODE (PATTERN (insn)) != CLOBBER
1802 && !DEBUG_INSN_P (insn))
1804 if (reload_completed)
1805 PUT_MODE (insn, clock_var > last_clock_var ? TImode : VOIDmode);
1806 last_clock_var = clock_var;
1812 /* Functions for handling of notes. */
1814 /* Add note list that ends on FROM_END to the end of TO_ENDP. */
1816 concat_note_lists (rtx from_end, rtx *to_endp)
1820 /* It's easy when have nothing to concat. */
1821 if (from_end == NULL)
1824 /* It's also easy when destination is empty. */
1825 if (*to_endp == NULL)
1827 *to_endp = from_end;
1831 from_start = from_end;
1832 while (PREV_INSN (from_start) != NULL)
1833 from_start = PREV_INSN (from_start);
1835 PREV_INSN (from_start) = *to_endp;
1836 NEXT_INSN (*to_endp) = from_start;
1837 *to_endp = from_end;
1840 /* Delete notes between HEAD and TAIL and put them in the chain
1841 of notes ended by NOTE_LIST. */
1843 remove_notes (rtx head, rtx tail)
1845 rtx next_tail, insn, next;
1848 if (head == tail && !INSN_P (head))
1851 next_tail = NEXT_INSN (tail);
1852 for (insn = head; insn != next_tail; insn = next)
1854 next = NEXT_INSN (insn);
1858 switch (NOTE_KIND (insn))
1860 case NOTE_INSN_BASIC_BLOCK:
1863 case NOTE_INSN_EPILOGUE_BEG:
1867 add_reg_note (next, REG_SAVE_NOTE,
1868 GEN_INT (NOTE_INSN_EPILOGUE_BEG));
1876 /* Add the note to list that ends at NOTE_LIST. */
1877 PREV_INSN (insn) = note_list;
1878 NEXT_INSN (insn) = NULL_RTX;
1880 NEXT_INSN (note_list) = insn;
1885 gcc_assert ((sel_sched_p () || insn != tail) && insn != head);
1890 /* Return the head and tail pointers of ebb starting at BEG and ending
1893 get_ebb_head_tail (basic_block beg, basic_block end, rtx *headp, rtx *tailp)
1895 rtx beg_head = BB_HEAD (beg);
1896 rtx beg_tail = BB_END (beg);
1897 rtx end_head = BB_HEAD (end);
1898 rtx end_tail = BB_END (end);
1900 /* Don't include any notes or labels at the beginning of the BEG
1901 basic block, or notes at the end of the END basic blocks. */
1903 if (LABEL_P (beg_head))
1904 beg_head = NEXT_INSN (beg_head);
1906 while (beg_head != beg_tail)
1907 if (NOTE_P (beg_head))
1908 beg_head = NEXT_INSN (beg_head);
1909 else if (DEBUG_INSN_P (beg_head))
1913 for (note = NEXT_INSN (beg_head);
1917 next = NEXT_INSN (note);
1920 if (sched_verbose >= 9)
1921 fprintf (sched_dump, "reorder %i\n", INSN_UID (note));
1923 reorder_insns_nobb (note, note, PREV_INSN (beg_head));
1925 if (BLOCK_FOR_INSN (note) != beg)
1926 df_insn_change_bb (note, beg);
1928 else if (!DEBUG_INSN_P (note))
1940 end_head = beg_head;
1941 else if (LABEL_P (end_head))
1942 end_head = NEXT_INSN (end_head);
1944 while (end_head != end_tail)
1945 if (NOTE_P (end_tail))
1946 end_tail = PREV_INSN (end_tail);
1947 else if (DEBUG_INSN_P (end_tail))
1951 for (note = PREV_INSN (end_tail);
1955 prev = PREV_INSN (note);
1958 if (sched_verbose >= 9)
1959 fprintf (sched_dump, "reorder %i\n", INSN_UID (note));
1961 reorder_insns_nobb (note, note, end_tail);
1963 if (end_tail == BB_END (end))
1964 BB_END (end) = note;
1966 if (BLOCK_FOR_INSN (note) != end)
1967 df_insn_change_bb (note, end);
1969 else if (!DEBUG_INSN_P (note))
1981 /* Return nonzero if there are no real insns in the range [ HEAD, TAIL ]. */
1984 no_real_insns_p (const_rtx head, const_rtx tail)
1986 while (head != NEXT_INSN (tail))
1988 if (!NOTE_P (head) && !LABEL_P (head))
1990 head = NEXT_INSN (head);
1995 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
1996 previously found among the insns. Insert them just before HEAD. */
1998 restore_other_notes (rtx head, basic_block head_bb)
2002 rtx note_head = note_list;
2005 head_bb = BLOCK_FOR_INSN (head);
2007 head = NEXT_INSN (bb_note (head_bb));
2009 while (PREV_INSN (note_head))
2011 set_block_for_insn (note_head, head_bb);
2012 note_head = PREV_INSN (note_head);
2014 /* In the above cycle we've missed this note. */
2015 set_block_for_insn (note_head, head_bb);
2017 PREV_INSN (note_head) = PREV_INSN (head);
2018 NEXT_INSN (PREV_INSN (head)) = note_head;
2019 PREV_INSN (head) = note_list;
2020 NEXT_INSN (note_list) = head;
2022 if (BLOCK_FOR_INSN (head) != head_bb)
2023 BB_END (head_bb) = note_list;
2031 /* Move insns that became ready to fire from queue to ready list. */
2034 queue_to_ready (struct ready_list *ready)
2040 q_ptr = NEXT_Q (q_ptr);
2042 if (dbg_cnt (sched_insn) == false)
2044 /* If debug counter is activated do not requeue the first
2045 nonscheduled insn. */
2046 skip_insn = nonscheduled_insns_begin;
2049 skip_insn = next_nonnote_nondebug_insn (skip_insn);
2051 while (QUEUE_INDEX (skip_insn) == QUEUE_SCHEDULED);
2054 skip_insn = NULL_RTX;
2056 /* Add all pending insns that can be scheduled without stalls to the
2058 for (link = insn_queue[q_ptr]; link; link = XEXP (link, 1))
2060 insn = XEXP (link, 0);
2063 if (sched_verbose >= 2)
2064 fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
2065 (*current_sched_info->print_insn) (insn, 0));
2067 /* If the ready list is full, delay the insn for 1 cycle.
2068 See the comment in schedule_block for the rationale. */
2069 if (!reload_completed
2070 && ready->n_ready - ready->n_debug > MAX_SCHED_READY_INSNS
2071 && !SCHED_GROUP_P (insn)
2072 && insn != skip_insn)
2073 queue_insn (insn, 1, "ready full");
2076 ready_add (ready, insn, false);
2077 if (sched_verbose >= 2)
2078 fprintf (sched_dump, "moving to ready without stalls\n");
2081 free_INSN_LIST_list (&insn_queue[q_ptr]);
2083 /* If there are no ready insns, stall until one is ready and add all
2084 of the pending insns at that point to the ready list. */
2085 if (ready->n_ready == 0)
2089 for (stalls = 1; stalls <= max_insn_queue_index; stalls++)
2091 if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
2093 for (; link; link = XEXP (link, 1))
2095 insn = XEXP (link, 0);
2098 if (sched_verbose >= 2)
2099 fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
2100 (*current_sched_info->print_insn) (insn, 0));
2102 ready_add (ready, insn, false);
2103 if (sched_verbose >= 2)
2104 fprintf (sched_dump, "moving to ready with %d stalls\n", stalls);
2106 free_INSN_LIST_list (&insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]);
2108 advance_one_cycle ();
2113 advance_one_cycle ();
2116 q_ptr = NEXT_Q_AFTER (q_ptr, stalls);
2117 clock_var += stalls;
2121 /* Used by early_queue_to_ready. Determines whether it is "ok" to
2122 prematurely move INSN from the queue to the ready list. Currently,
2123 if a target defines the hook 'is_costly_dependence', this function
2124 uses the hook to check whether there exist any dependences which are
2125 considered costly by the target, between INSN and other insns that
2126 have already been scheduled. Dependences are checked up to Y cycles
2127 back, with default Y=1; The flag -fsched-stalled-insns-dep=Y allows
2128 controlling this value.
2129 (Other considerations could be taken into account instead (or in
2130 addition) depending on user flags and target hooks. */
2133 ok_for_early_queue_removal (rtx insn)
2135 if (targetm.sched.is_costly_dependence)
2139 int i = VEC_length (rtx, scheduled_insns);
2140 for (n_cycles = flag_sched_stalled_insns_dep; n_cycles; n_cycles--)
2146 prev_insn = VEC_index (rtx, scheduled_insns, i);
2148 if (!NOTE_P (prev_insn))
2152 dep = sd_find_dep_between (prev_insn, insn, true);
2156 cost = dep_cost (dep);
2158 if (targetm.sched.is_costly_dependence (dep, cost,
2159 flag_sched_stalled_insns_dep - n_cycles))
2164 if (GET_MODE (prev_insn) == TImode) /* end of dispatch group */
2177 /* Remove insns from the queue, before they become "ready" with respect
2178 to FU latency considerations. */
2181 early_queue_to_ready (state_t state, struct ready_list *ready)
2189 state_t temp_state = alloca (dfa_state_size);
2191 int insns_removed = 0;
2194 Flag '-fsched-stalled-insns=X' determines the aggressiveness of this
2197 X == 0: There is no limit on how many queued insns can be removed
2198 prematurely. (flag_sched_stalled_insns = -1).
2200 X >= 1: Only X queued insns can be removed prematurely in each
2201 invocation. (flag_sched_stalled_insns = X).
2203 Otherwise: Early queue removal is disabled.
2204 (flag_sched_stalled_insns = 0)
2207 if (! flag_sched_stalled_insns)
2210 for (stalls = 0; stalls <= max_insn_queue_index; stalls++)
2212 if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
2214 if (sched_verbose > 6)
2215 fprintf (sched_dump, ";; look at index %d + %d\n", q_ptr, stalls);
2220 next_link = XEXP (link, 1);
2221 insn = XEXP (link, 0);
2222 if (insn && sched_verbose > 6)
2223 print_rtl_single (sched_dump, insn);
2225 memcpy (temp_state, state, dfa_state_size);
2226 if (recog_memoized (insn) < 0)
2227 /* non-negative to indicate that it's not ready
2228 to avoid infinite Q->R->Q->R... */
2231 cost = state_transition (temp_state, insn);
2233 if (sched_verbose >= 6)
2234 fprintf (sched_dump, "transition cost = %d\n", cost);
2236 move_to_ready = false;
2239 move_to_ready = ok_for_early_queue_removal (insn);
2240 if (move_to_ready == true)
2242 /* move from Q to R */
2244 ready_add (ready, insn, false);
2247 XEXP (prev_link, 1) = next_link;
2249 insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = next_link;
2251 free_INSN_LIST_node (link);
2253 if (sched_verbose >= 2)
2254 fprintf (sched_dump, ";;\t\tEarly Q-->Ready: insn %s\n",
2255 (*current_sched_info->print_insn) (insn, 0));
2258 if (insns_removed == flag_sched_stalled_insns)
2259 /* Remove no more than flag_sched_stalled_insns insns
2260 from Q at a time. */
2261 return insns_removed;
2265 if (move_to_ready == false)
2272 } /* for stalls.. */
2274 return insns_removed;
2278 /* Print the ready list for debugging purposes. Callable from debugger. */
2281 debug_ready_list (struct ready_list *ready)
2286 if (ready->n_ready == 0)
2288 fprintf (sched_dump, "\n");
2292 p = ready_lastpos (ready);
2293 for (i = 0; i < ready->n_ready; i++)
2295 fprintf (sched_dump, " %s:%d",
2296 (*current_sched_info->print_insn) (p[i], 0),
2298 if (sched_pressure_p)
2299 fprintf (sched_dump, "(cost=%d",
2300 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (p[i]));
2301 if (INSN_TICK (p[i]) > clock_var)
2302 fprintf (sched_dump, ":delay=%d", INSN_TICK (p[i]) - clock_var);
2303 if (sched_pressure_p)
2304 fprintf (sched_dump, ")");
2306 fprintf (sched_dump, "\n");
2309 /* Search INSN for REG_SAVE_NOTE notes and convert them back into insn
2310 NOTEs. This is used for NOTE_INSN_EPILOGUE_BEG, so that sched-ebb
2311 replaces the epilogue note in the correct basic block. */
2313 reemit_notes (rtx insn)
2315 rtx note, last = insn;
2317 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
2319 if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
2321 enum insn_note note_type = (enum insn_note) INTVAL (XEXP (note, 0));
2323 last = emit_note_before (note_type, last);
2324 remove_note (insn, note);
2329 /* Move INSN. Reemit notes if needed. Update CFG, if needed. */
2331 move_insn (rtx insn, rtx last, rtx nt)
2333 if (PREV_INSN (insn) != last)
2339 bb = BLOCK_FOR_INSN (insn);
2341 /* BB_HEAD is either LABEL or NOTE. */
2342 gcc_assert (BB_HEAD (bb) != insn);
2344 if (BB_END (bb) == insn)
2345 /* If this is last instruction in BB, move end marker one
2348 /* Jumps are always placed at the end of basic block. */
2349 jump_p = control_flow_insn_p (insn);
2352 || ((common_sched_info->sched_pass_id == SCHED_RGN_PASS)
2353 && IS_SPECULATION_BRANCHY_CHECK_P (insn))
2354 || (common_sched_info->sched_pass_id
2355 == SCHED_EBB_PASS));
2357 gcc_assert (BLOCK_FOR_INSN (PREV_INSN (insn)) == bb);
2359 BB_END (bb) = PREV_INSN (insn);
2362 gcc_assert (BB_END (bb) != last);
2365 /* We move the block note along with jump. */
2369 note = NEXT_INSN (insn);
2370 while (NOTE_NOT_BB_P (note) && note != nt)
2371 note = NEXT_INSN (note);
2375 || BARRIER_P (note)))
2376 note = NEXT_INSN (note);
2378 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
2383 NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (note);
2384 PREV_INSN (NEXT_INSN (note)) = PREV_INSN (insn);
2386 NEXT_INSN (note) = NEXT_INSN (last);
2387 PREV_INSN (NEXT_INSN (last)) = note;
2389 NEXT_INSN (last) = insn;
2390 PREV_INSN (insn) = last;
2392 bb = BLOCK_FOR_INSN (last);
2396 fix_jump_move (insn);
2398 if (BLOCK_FOR_INSN (insn) != bb)
2399 move_block_after_check (insn);
2401 gcc_assert (BB_END (bb) == last);
2404 df_insn_change_bb (insn, bb);
2406 /* Update BB_END, if needed. */
2407 if (BB_END (bb) == last)
2411 SCHED_GROUP_P (insn) = 0;
2414 /* Return true if scheduling INSN will finish current clock cycle. */
2416 insn_finishes_cycle_p (rtx insn)
2418 if (SCHED_GROUP_P (insn))
2419 /* After issuing INSN, rest of the sched_group will be forced to issue
2420 in order. Don't make any plans for the rest of cycle. */
2423 /* Finishing the block will, apparently, finish the cycle. */
2424 if (current_sched_info->insn_finishes_block_p
2425 && current_sched_info->insn_finishes_block_p (insn))
2431 /* Define type for target data used in multipass scheduling. */
2432 #ifndef TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T
2433 # define TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T int
2435 typedef TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T first_cycle_multipass_data_t;
2437 /* The following structure describe an entry of the stack of choices. */
2440 /* Ordinal number of the issued insn in the ready queue. */
2442 /* The number of the rest insns whose issues we should try. */
2444 /* The number of issued essential insns. */
2446 /* State after issuing the insn. */
2448 /* Target-specific data. */
2449 first_cycle_multipass_data_t target_data;
2452 /* The following array is used to implement a stack of choices used in
2453 function max_issue. */
2454 static struct choice_entry *choice_stack;
2456 /* The following variable value is number of essential insns issued on
2457 the current cycle. An insn is essential one if it changes the
2458 processors state. */
2459 int cycle_issued_insns;
2461 /* This holds the value of the target dfa_lookahead hook. */
2464 /* The following variable value is maximal number of tries of issuing
2465 insns for the first cycle multipass insn scheduling. We define
2466 this value as constant*(DFA_LOOKAHEAD**ISSUE_RATE). We would not
2467 need this constraint if all real insns (with non-negative codes)
2468 had reservations because in this case the algorithm complexity is
2469 O(DFA_LOOKAHEAD**ISSUE_RATE). Unfortunately, the dfa descriptions
2470 might be incomplete and such insn might occur. For such
2471 descriptions, the complexity of algorithm (without the constraint)
2472 could achieve DFA_LOOKAHEAD ** N , where N is the queue length. */
2473 static int max_lookahead_tries;
2475 /* The following value is value of hook
2476 `first_cycle_multipass_dfa_lookahead' at the last call of
2478 static int cached_first_cycle_multipass_dfa_lookahead = 0;
2480 /* The following value is value of `issue_rate' at the last call of
2482 static int cached_issue_rate = 0;
2484 /* The following function returns maximal (or close to maximal) number
2485 of insns which can be issued on the same cycle and one of which
2486 insns is insns with the best rank (the first insn in READY). To
2487 make this function tries different samples of ready insns. READY
2488 is current queue `ready'. Global array READY_TRY reflects what
2489 insns are already issued in this try. The function stops immediately,
2490 if it reached the such a solution, that all instruction can be issued.
2491 INDEX will contain index of the best insn in READY. The following
2492 function is used only for first cycle multipass scheduling.
2496 This function expects recognized insns only. All USEs,
2497 CLOBBERs, etc must be filtered elsewhere. */
2499 max_issue (struct ready_list *ready, int privileged_n, state_t state,
2500 bool first_cycle_insn_p, int *index)
2502 int n, i, all, n_ready, best, delay, tries_num;
2504 struct choice_entry *top;
2507 n_ready = ready->n_ready;
2508 gcc_assert (dfa_lookahead >= 1 && privileged_n >= 0
2509 && privileged_n <= n_ready);
2511 /* Init MAX_LOOKAHEAD_TRIES. */
2512 if (cached_first_cycle_multipass_dfa_lookahead != dfa_lookahead)
2514 cached_first_cycle_multipass_dfa_lookahead = dfa_lookahead;
2515 max_lookahead_tries = 100;
2516 for (i = 0; i < issue_rate; i++)
2517 max_lookahead_tries *= dfa_lookahead;
2520 /* Init max_points. */
2521 more_issue = issue_rate - cycle_issued_insns;
2522 gcc_assert (more_issue >= 0);
2524 /* The number of the issued insns in the best solution. */
2529 /* Set initial state of the search. */
2530 memcpy (top->state, state, dfa_state_size);
2531 top->rest = dfa_lookahead;
2533 if (targetm.sched.first_cycle_multipass_begin)
2534 targetm.sched.first_cycle_multipass_begin (&top->target_data,
2536 first_cycle_insn_p);
2538 /* Count the number of the insns to search among. */
2539 for (all = i = 0; i < n_ready; i++)
2543 /* I is the index of the insn to try next. */
2548 if (/* If we've reached a dead end or searched enough of what we have
2551 /* or have nothing else to try... */
2553 /* or should not issue more. */
2554 || top->n >= more_issue)
2556 /* ??? (... || i == n_ready). */
2557 gcc_assert (i <= n_ready);
2559 /* We should not issue more than issue_rate instructions. */
2560 gcc_assert (top->n <= more_issue);
2562 if (top == choice_stack)
2565 if (best < top - choice_stack)
2570 /* Try to find issued privileged insn. */
2571 while (n && !ready_try[--n]);
2574 if (/* If all insns are equally good... */
2576 /* Or a privileged insn will be issued. */
2578 /* Then we have a solution. */
2580 best = top - choice_stack;
2581 /* This is the index of the insn issued first in this
2583 *index = choice_stack [1].index;
2584 if (top->n == more_issue || best == all)
2589 /* Set ready-list index to point to the last insn
2590 ('i++' below will advance it to the next insn). */
2596 if (targetm.sched.first_cycle_multipass_backtrack)
2597 targetm.sched.first_cycle_multipass_backtrack (&top->target_data,
2598 ready_try, n_ready);
2601 memcpy (state, top->state, dfa_state_size);
2603 else if (!ready_try [i])
2606 if (tries_num > max_lookahead_tries)
2608 insn = ready_element (ready, i);
2609 delay = state_transition (state, insn);
2612 if (state_dead_lock_p (state)
2613 || insn_finishes_cycle_p (insn))
2614 /* We won't issue any more instructions in the next
2621 if (memcmp (top->state, state, dfa_state_size) != 0)
2624 /* Advance to the next choice_entry. */
2626 /* Initialize it. */
2627 top->rest = dfa_lookahead;
2630 memcpy (top->state, state, dfa_state_size);
2633 if (targetm.sched.first_cycle_multipass_issue)
2634 targetm.sched.first_cycle_multipass_issue (&top->target_data,
2644 /* Increase ready-list index. */
2648 if (targetm.sched.first_cycle_multipass_end)
2649 targetm.sched.first_cycle_multipass_end (best != 0
2650 ? &choice_stack[1].target_data
2653 /* Restore the original state of the DFA. */
2654 memcpy (state, choice_stack->state, dfa_state_size);
2659 /* The following function chooses insn from READY and modifies
2660 READY. The following function is used only for first
2661 cycle multipass scheduling.
2663 -1 if cycle should be advanced,
2664 0 if INSN_PTR is set to point to the desirable insn,
2665 1 if choose_ready () should be restarted without advancing the cycle. */
2667 choose_ready (struct ready_list *ready, bool first_cycle_insn_p,
2672 if (dbg_cnt (sched_insn) == false)
2674 rtx insn = nonscheduled_insns_begin;
2677 insn = next_nonnote_insn (insn);
2679 while (QUEUE_INDEX (insn) == QUEUE_SCHEDULED);
2681 if (QUEUE_INDEX (insn) == QUEUE_READY)
2682 /* INSN is in the ready_list. */
2684 nonscheduled_insns_begin = insn;
2685 ready_remove_insn (insn);
2690 /* INSN is in the queue. Advance cycle to move it to the ready list. */
2696 if (targetm.sched.first_cycle_multipass_dfa_lookahead)
2697 lookahead = targetm.sched.first_cycle_multipass_dfa_lookahead ();
2698 if (lookahead <= 0 || SCHED_GROUP_P (ready_element (ready, 0))
2699 || DEBUG_INSN_P (ready_element (ready, 0)))
2701 if (targetm.sched.dispatch (NULL_RTX, IS_DISPATCH_ON))
2702 *insn_ptr = ready_remove_first_dispatch (ready);
2704 *insn_ptr = ready_remove_first (ready);
2710 /* Try to choose the better insn. */
2711 int index = 0, i, n;
2713 int try_data = 1, try_control = 1;
2716 insn = ready_element (ready, 0);
2717 if (INSN_CODE (insn) < 0)
2719 *insn_ptr = ready_remove_first (ready);
2724 && spec_info->flags & (PREFER_NON_DATA_SPEC
2725 | PREFER_NON_CONTROL_SPEC))
2727 for (i = 0, n = ready->n_ready; i < n; i++)
2732 x = ready_element (ready, i);
2735 if (spec_info->flags & PREFER_NON_DATA_SPEC
2736 && !(s & DATA_SPEC))
2739 if (!(spec_info->flags & PREFER_NON_CONTROL_SPEC)
2744 if (spec_info->flags & PREFER_NON_CONTROL_SPEC
2745 && !(s & CONTROL_SPEC))
2748 if (!(spec_info->flags & PREFER_NON_DATA_SPEC) || !try_data)
2754 ts = TODO_SPEC (insn);
2755 if ((ts & SPECULATIVE)
2756 && (((!try_data && (ts & DATA_SPEC))
2757 || (!try_control && (ts & CONTROL_SPEC)))
2758 || (targetm.sched.first_cycle_multipass_dfa_lookahead_guard_spec
2760 .first_cycle_multipass_dfa_lookahead_guard_spec (insn))))
2761 /* Discard speculative instruction that stands first in the ready
2764 change_queue_index (insn, 1);
2770 for (i = 1; i < ready->n_ready; i++)
2772 insn = ready_element (ready, i);
2775 = ((!try_data && (TODO_SPEC (insn) & DATA_SPEC))
2776 || (!try_control && (TODO_SPEC (insn) & CONTROL_SPEC)));
2779 /* Let the target filter the search space. */
2780 for (i = 1; i < ready->n_ready; i++)
2783 insn = ready_element (ready, i);
2785 /* If this insn is recognizable we should have already
2786 recognized it earlier.
2787 ??? Not very clear where this is supposed to be done.
2789 gcc_checking_assert (INSN_CODE (insn) >= 0
2790 || recog_memoized (insn) < 0);
2793 = (/* INSN_CODE check can be omitted here as it is also done later
2795 INSN_CODE (insn) < 0
2796 || (targetm.sched.first_cycle_multipass_dfa_lookahead_guard
2797 && !targetm.sched.first_cycle_multipass_dfa_lookahead_guard
2801 if (max_issue (ready, 1, curr_state, first_cycle_insn_p, &index) == 0)
2803 *insn_ptr = ready_remove_first (ready);
2804 if (sched_verbose >= 4)
2805 fprintf (sched_dump, ";;\t\tChosen insn (but can't issue) : %s \n",
2806 (*current_sched_info->print_insn) (*insn_ptr, 0));
2811 if (sched_verbose >= 4)
2812 fprintf (sched_dump, ";;\t\tChosen insn : %s\n",
2813 (*current_sched_info->print_insn)
2814 (ready_element (ready, index), 0));
2816 *insn_ptr = ready_remove (ready, index);
2822 /* This function is called when we have successfully scheduled a
2823 block. It uses the schedule stored in the scheduled_insns vector
2824 to rearrange the RTL. PREV_HEAD is used as the anchor to which we
2825 append the scheduled insns; TAIL is the insn after the scheduled
2826 block. TARGET_BB is the argument passed to schedule_block. */
2829 commit_schedule (rtx prev_head, rtx tail, basic_block *target_bb)
2834 last_scheduled_insn = prev_head;
2836 VEC_iterate (rtx, scheduled_insns, i, insn);
2839 if (control_flow_insn_p (last_scheduled_insn)
2840 || current_sched_info->advance_target_bb (*target_bb, insn))
2842 *target_bb = current_sched_info->advance_target_bb (*target_bb, 0);
2848 x = next_real_insn (last_scheduled_insn);
2850 dump_new_block_header (1, *target_bb, x, tail);
2853 last_scheduled_insn = bb_note (*target_bb);
2856 if (current_sched_info->begin_move_insn)
2857 (*current_sched_info->begin_move_insn) (insn, last_scheduled_insn);
2858 move_insn (insn, last_scheduled_insn,
2859 current_sched_info->next_tail);
2860 if (!DEBUG_INSN_P (insn))
2861 reemit_notes (insn);
2862 last_scheduled_insn = insn;
2865 VEC_truncate (rtx, scheduled_insns, 0);
2868 /* Examine all insns on the ready list and queue those which can't be
2869 issued in this cycle. TEMP_STATE is temporary scheduler state we
2870 can use as scratch space. If FIRST_CYCLE_INSN_P is true, no insns
2871 have been issued for the current cycle, which means it is valid to
2872 issue an asm statement. */
2875 prune_ready_list (state_t temp_state, bool first_cycle_insn_p)
2880 for (i = 0; i < ready.n_ready; i++)
2882 rtx insn = ready_element (&ready, i);
2884 const char *reason = "resource conflict";
2886 if (recog_memoized (insn) < 0)
2888 if (!first_cycle_insn_p
2889 && (GET_CODE (PATTERN (insn)) == ASM_INPUT
2890 || asm_noperands (PATTERN (insn)) >= 0))
2894 else if (sched_pressure_p)
2898 memcpy (temp_state, curr_state, dfa_state_size);
2899 cost = state_transition (temp_state, insn);
2907 ready_remove (&ready, i);
2908 queue_insn (insn, cost, reason);
2914 /* Use forward list scheduling to rearrange insns of block pointed to by
2915 TARGET_BB, possibly bringing insns from subsequent blocks in the same
2919 schedule_block (basic_block *target_bb)
2922 bool first_cycle_insn_p;
2924 state_t temp_state = NULL; /* It is used for multipass scheduling. */
2925 int sort_p, advance, start_clock_var;
2927 /* Head/tail info for this block. */
2928 rtx prev_head = current_sched_info->prev_head;
2929 rtx next_tail = current_sched_info->next_tail;
2930 rtx head = NEXT_INSN (prev_head);
2931 rtx tail = PREV_INSN (next_tail);
2933 /* We used to have code to avoid getting parameters moved from hard
2934 argument registers into pseudos.
2936 However, it was removed when it proved to be of marginal benefit
2937 and caused problems because schedule_block and compute_forward_dependences
2938 had different notions of what the "head" insn was. */
2940 gcc_assert (head != tail || INSN_P (head));
2942 haifa_recovery_bb_recently_added_p = false;
2946 dump_new_block_header (0, *target_bb, head, tail);
2948 state_reset (curr_state);
2950 /* Clear the ready list. */
2951 ready.first = ready.veclen - 1;
2955 /* It is used for first cycle multipass scheduling. */
2956 temp_state = alloca (dfa_state_size);
2958 if (targetm.sched.init)
2959 targetm.sched.init (sched_dump, sched_verbose, ready.veclen);
2961 /* We start inserting insns after PREV_HEAD. */
2962 last_scheduled_insn = nonscheduled_insns_begin = prev_head;
2963 last_nondebug_scheduled_insn = NULL_RTX;
2965 gcc_assert ((NOTE_P (last_scheduled_insn)
2966 || DEBUG_INSN_P (last_scheduled_insn))
2967 && BLOCK_FOR_INSN (last_scheduled_insn) == *target_bb);
2969 /* Initialize INSN_QUEUE. Q_SIZE is the total number of insns in the
2974 insn_queue = XALLOCAVEC (rtx, max_insn_queue_index + 1);
2975 memset (insn_queue, 0, (max_insn_queue_index + 1) * sizeof (rtx));
2977 /* Start just before the beginning of time. */
2980 /* We need queue and ready lists and clock_var be initialized
2981 in try_ready () (which is called through init_ready_list ()). */
2982 (*current_sched_info->init_ready_list) ();
2984 /* The algorithm is O(n^2) in the number of ready insns at any given
2985 time in the worst case. Before reload we are more likely to have
2986 big lists so truncate them to a reasonable size. */
2987 if (!reload_completed
2988 && ready.n_ready - ready.n_debug > MAX_SCHED_READY_INSNS)
2990 ready_sort (&ready);
2992 /* Find first free-standing insn past MAX_SCHED_READY_INSNS.
2993 If there are debug insns, we know they're first. */
2994 for (i = MAX_SCHED_READY_INSNS + ready.n_debug; i < ready.n_ready; i++)
2995 if (!SCHED_GROUP_P (ready_element (&ready, i)))
2998 if (sched_verbose >= 2)
3000 fprintf (sched_dump,
3001 ";;\t\tReady list on entry: %d insns\n", ready.n_ready);
3002 fprintf (sched_dump,
3003 ";;\t\t before reload => truncated to %d insns\n", i);
3006 /* Delay all insns past it for 1 cycle. If debug counter is
3007 activated make an exception for the insn right after
3008 nonscheduled_insns_begin. */
3012 if (dbg_cnt (sched_insn) == false)
3013 skip_insn = next_nonnote_insn (nonscheduled_insns_begin);
3015 skip_insn = NULL_RTX;
3017 while (i < ready.n_ready)
3021 insn = ready_remove (&ready, i);
3023 if (insn != skip_insn)
3024 queue_insn (insn, 1, "list truncated");
3027 ready_add (&ready, skip_insn, true);
3031 /* Now we can restore basic block notes and maintain precise cfg. */
3032 restore_bb_notes (*target_bb);
3034 last_clock_var = -1;
3038 gcc_assert (VEC_length (rtx, scheduled_insns) == 0);
3040 /* Loop until all the insns in BB are scheduled. */
3041 while ((*current_sched_info->schedule_more_p) ())
3045 start_clock_var = clock_var;
3049 advance_one_cycle ();
3051 /* Add to the ready list all pending insns that can be issued now.
3052 If there are no ready insns, increment clock until one
3053 is ready and add all pending insns at that point to the ready
3055 queue_to_ready (&ready);
3057 gcc_assert (ready.n_ready);
3059 if (sched_verbose >= 2)
3061 fprintf (sched_dump, ";;\t\tReady list after queue_to_ready: ");
3062 debug_ready_list (&ready);
3064 advance -= clock_var - start_clock_var;
3066 while (advance > 0);
3068 if (ready.n_ready > 0)
3069 prune_ready_list (temp_state, true);
3070 if (ready.n_ready == 0)
3073 first_cycle_insn_p = true;
3074 cycle_issued_insns = 0;
3075 can_issue_more = issue_rate;
3082 if (sort_p && ready.n_ready > 0)
3084 /* Sort the ready list based on priority. This must be
3085 done every iteration through the loop, as schedule_insn
3086 may have readied additional insns that will not be
3087 sorted correctly. */
3088 ready_sort (&ready);
3090 if (sched_verbose >= 2)
3092 fprintf (sched_dump, ";;\t\tReady list after ready_sort: ");
3093 debug_ready_list (&ready);
3097 /* We don't want md sched reorder to even see debug isns, so put
3098 them out right away. */
3099 if (ready.n_ready && DEBUG_INSN_P (ready_element (&ready, 0))
3100 && (*current_sched_info->schedule_more_p) ())
3102 while (ready.n_ready && DEBUG_INSN_P (ready_element (&ready, 0)))
3104 rtx insn = ready_remove_first (&ready);
3105 gcc_assert (DEBUG_INSN_P (insn));
3106 (*current_sched_info->begin_schedule_ready) (insn);
3107 VEC_safe_push (rtx, heap, scheduled_insns, insn);
3108 last_scheduled_insn = insn;
3109 advance = schedule_insn (insn);
3110 gcc_assert (advance == 0);
3111 if (ready.n_ready > 0)
3112 ready_sort (&ready);
3116 if (first_cycle_insn_p && !ready.n_ready)
3119 /* Allow the target to reorder the list, typically for
3120 better instruction bundling. */
3122 && (ready.n_ready == 0
3123 || !SCHED_GROUP_P (ready_element (&ready, 0))))
3125 if (first_cycle_insn_p && targetm.sched.reorder)
3127 = targetm.sched.reorder (sched_dump, sched_verbose,
3128 ready_lastpos (&ready),
3129 &ready.n_ready, clock_var);
3130 else if (!first_cycle_insn_p && targetm.sched.reorder2)
3132 = targetm.sched.reorder2 (sched_dump, sched_verbose,
3134 ? ready_lastpos (&ready) : NULL,
3135 &ready.n_ready, clock_var);
3138 restart_choose_ready:
3139 if (sched_verbose >= 2)
3141 fprintf (sched_dump, ";;\tReady list (t = %3d): ",
3143 debug_ready_list (&ready);
3144 if (sched_pressure_p)
3145 print_curr_reg_pressure ();
3148 if (ready.n_ready == 0
3150 && reload_completed)
3152 /* Allow scheduling insns directly from the queue in case
3153 there's nothing better to do (ready list is empty) but
3154 there are still vacant dispatch slots in the current cycle. */
3155 if (sched_verbose >= 6)
3156 fprintf (sched_dump,";;\t\tSecond chance\n");
3157 memcpy (temp_state, curr_state, dfa_state_size);
3158 if (early_queue_to_ready (temp_state, &ready))
3159 ready_sort (&ready);
3162 if (ready.n_ready == 0
3164 || state_dead_lock_p (curr_state)
3165 || !(*current_sched_info->schedule_more_p) ())
3168 /* Select and remove the insn from the ready list. */
3174 res = choose_ready (&ready, first_cycle_insn_p, &insn);
3180 goto restart_choose_ready;
3182 gcc_assert (insn != NULL_RTX);
3185 insn = ready_remove_first (&ready);
3187 if (sched_pressure_p && INSN_TICK (insn) > clock_var)
3189 ready_add (&ready, insn, true);
3194 if (targetm.sched.dfa_new_cycle
3195 && targetm.sched.dfa_new_cycle (sched_dump, sched_verbose,
3196 insn, last_clock_var,
3197 clock_var, &sort_p))
3198 /* SORT_P is used by the target to override sorting
3199 of the ready list. This is needed when the target
3200 has modified its internal structures expecting that
3201 the insn will be issued next. As we need the insn
3202 to have the highest priority (so it will be returned by
3203 the ready_remove_first call above), we invoke
3204 ready_add (&ready, insn, true).
3205 But, still, there is one issue: INSN can be later
3206 discarded by scheduler's front end through
3207 current_sched_info->can_schedule_ready_p, hence, won't
3210 ready_add (&ready, insn, true);
3216 if (current_sched_info->can_schedule_ready_p
3217 && ! (*current_sched_info->can_schedule_ready_p) (insn))
3218 /* We normally get here only if we don't want to move
3219 insn from the split block. */
3221 TODO_SPEC (insn) = (TODO_SPEC (insn) & ~SPECULATIVE) | HARD_DEP;
3222 goto restart_choose_ready;
3225 /* DECISION is made. */
3227 if (TODO_SPEC (insn) & SPECULATIVE)
3228 generate_recovery_code (insn);
3230 if (targetm.sched.dispatch (NULL_RTX, IS_DISPATCH_ON))
3231 targetm.sched.dispatch_do (insn, ADD_TO_DISPATCH_WINDOW);
3233 /* Update counters, etc in the scheduler's front end. */
3234 (*current_sched_info->begin_schedule_ready) (insn);
3235 VEC_safe_push (rtx, heap, scheduled_insns, insn);
3236 gcc_assert (NONDEBUG_INSN_P (insn));
3237 last_nondebug_scheduled_insn = last_scheduled_insn = insn;
3239 if (recog_memoized (insn) >= 0)
3241 memcpy (temp_state, curr_state, dfa_state_size);
3242 cost = state_transition (curr_state, insn);
3243 if (!sched_pressure_p)
3244 gcc_assert (cost < 0);
3245 if (memcmp (temp_state, curr_state, dfa_state_size) != 0)
3246 cycle_issued_insns++;
3250 asm_p = (GET_CODE (PATTERN (insn)) == ASM_INPUT
3251 || asm_noperands (PATTERN (insn)) >= 0);
3253 if (targetm.sched.variable_issue)
3255 targetm.sched.variable_issue (sched_dump, sched_verbose,
3256 insn, can_issue_more);
3257 /* A naked CLOBBER or USE generates no instruction, so do
3258 not count them against the issue rate. */
3259 else if (GET_CODE (PATTERN (insn)) != USE
3260 && GET_CODE (PATTERN (insn)) != CLOBBER)
3262 advance = schedule_insn (insn);
3264 /* After issuing an asm insn we should start a new cycle. */
3265 if (advance == 0 && asm_p)
3270 first_cycle_insn_p = false;
3271 if (ready.n_ready > 0)
3272 prune_ready_list (temp_state, false);
3279 fprintf (sched_dump, ";;\tReady list (final): ");
3280 debug_ready_list (&ready);
3283 if (current_sched_info->queue_must_finish_empty)
3284 /* Sanity check -- queue must be empty now. Meaningless if region has
3286 gcc_assert (!q_size && !ready.n_ready && !ready.n_debug);
3289 /* We must maintain QUEUE_INDEX between blocks in region. */
3290 for (i = ready.n_ready - 1; i >= 0; i--)
3294 x = ready_element (&ready, i);
3295 QUEUE_INDEX (x) = QUEUE_NOWHERE;
3296 TODO_SPEC (x) = (TODO_SPEC (x) & ~SPECULATIVE) | HARD_DEP;
3300 for (i = 0; i <= max_insn_queue_index; i++)
3303 for (link = insn_queue[i]; link; link = XEXP (link, 1))
3308 QUEUE_INDEX (x) = QUEUE_NOWHERE;
3309 TODO_SPEC (x) = (TODO_SPEC (x) & ~SPECULATIVE) | HARD_DEP;
3311 free_INSN_LIST_list (&insn_queue[i]);
3315 commit_schedule (prev_head, tail, target_bb);
3317 fprintf (sched_dump, ";; total time = %d\n", clock_var);
3319 if (!current_sched_info->queue_must_finish_empty
3320 || haifa_recovery_bb_recently_added_p)
3322 /* INSN_TICK (minimum clock tick at which the insn becomes
3323 ready) may be not correct for the insn in the subsequent
3324 blocks of the region. We should use a correct value of
3325 `clock_var' or modify INSN_TICK. It is better to keep
3326 clock_var value equal to 0 at the start of a basic block.
3327 Therefore we modify INSN_TICK here. */
3328 fix_inter_tick (NEXT_INSN (prev_head), last_scheduled_insn);
3331 if (targetm.sched.finish)
3333 targetm.sched.finish (sched_dump, sched_verbose);
3334 /* Target might have added some instructions to the scheduled block
3335 in its md_finish () hook. These new insns don't have any data
3336 initialized and to identify them we extend h_i_d so that they'll
3338 sched_extend_luids ();
3342 fprintf (sched_dump, ";; new head = %d\n;; new tail = %d\n\n",
3343 INSN_UID (head), INSN_UID (tail));
3345 /* Update head/tail boundaries. */
3346 head = NEXT_INSN (prev_head);
3347 tail = last_scheduled_insn;
3349 head = restore_other_notes (head, NULL);
3351 current_sched_info->head = head;
3352 current_sched_info->tail = tail;
3355 /* Set_priorities: compute priority of each insn in the block. */
3358 set_priorities (rtx head, rtx tail)
3362 int sched_max_insns_priority =
3363 current_sched_info->sched_max_insns_priority;
3366 if (head == tail && ! INSN_P (head))
3371 prev_head = PREV_INSN (head);
3372 for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
3378 (void) priority (insn);
3380 gcc_assert (INSN_PRIORITY_KNOWN (insn));
3382 sched_max_insns_priority = MAX (sched_max_insns_priority,
3383 INSN_PRIORITY (insn));
3386 current_sched_info->sched_max_insns_priority = sched_max_insns_priority;
3391 /* Set dump and sched_verbose for the desired debugging output. If no
3392 dump-file was specified, but -fsched-verbose=N (any N), print to stderr.
3393 For -fsched-verbose=N, N>=10, print everything to stderr. */
3395 setup_sched_dump (void)
3397 sched_verbose = sched_verbose_param;
3398 if (sched_verbose_param == 0 && dump_file)
3400 sched_dump = ((sched_verbose_param >= 10 || !dump_file)
3401 ? stderr : dump_file);
3404 /* Initialize some global state for the scheduler. This function works
3405 with the common data shared between all the schedulers. It is called
3406 from the scheduler specific initialization routine. */
3411 /* Disable speculative loads in their presence if cc0 defined. */
3413 flag_schedule_speculative_load = 0;
3416 if (targetm.sched.dispatch (NULL_RTX, IS_DISPATCH_ON))
3417 targetm.sched.dispatch_do (NULL_RTX, DISPATCH_INIT);
3419 sched_pressure_p = (flag_sched_pressure && ! reload_completed
3420 && common_sched_info->sched_pass_id == SCHED_RGN_PASS);
3422 if (sched_pressure_p)
3423 ira_setup_eliminable_regset ();
3425 /* Initialize SPEC_INFO. */
3426 if (targetm.sched.set_sched_flags)
3428 spec_info = &spec_info_var;
3429 targetm.sched.set_sched_flags (spec_info);
3431 if (spec_info->mask != 0)
3433 spec_info->data_weakness_cutoff =
3434 (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF) * MAX_DEP_WEAK) / 100;
3435 spec_info->control_weakness_cutoff =
3436 (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF)
3437 * REG_BR_PROB_BASE) / 100;
3440 /* So we won't read anything accidentally. */
3445 /* So we won't read anything accidentally. */
3448 /* Initialize issue_rate. */
3449 if (targetm.sched.issue_rate)
3450 issue_rate = targetm.sched.issue_rate ();
3454 if (cached_issue_rate != issue_rate)
3456 cached_issue_rate = issue_rate;
3457 /* To invalidate max_lookahead_tries: */
3458 cached_first_cycle_multipass_dfa_lookahead = 0;
3461 if (targetm.sched.first_cycle_multipass_dfa_lookahead)
3462 dfa_lookahead = targetm.sched.first_cycle_multipass_dfa_lookahead ();
3466 if (targetm.sched.init_dfa_pre_cycle_insn)
3467 targetm.sched.init_dfa_pre_cycle_insn ();
3469 if (targetm.sched.init_dfa_post_cycle_insn)
3470 targetm.sched.init_dfa_post_cycle_insn ();
3473 dfa_state_size = state_size ();
3475 init_alias_analysis ();
3477 df_set_flags (DF_LR_RUN_DCE);
3478 df_note_add_problem ();
3480 /* More problems needed for interloop dep calculation in SMS. */
3481 if (common_sched_info->sched_pass_id == SCHED_SMS_PASS)
3483 df_rd_add_problem ();
3484 df_chain_add_problem (DF_DU_CHAIN + DF_UD_CHAIN);
3489 /* Do not run DCE after reload, as this can kill nops inserted
3491 if (reload_completed)
3492 df_clear_flags (DF_LR_RUN_DCE);
3494 regstat_compute_calls_crossed ();
3496 if (targetm.sched.init_global)
3497 targetm.sched.init_global (sched_dump, sched_verbose, get_max_uid () + 1);
3499 if (sched_pressure_p)
3501 int i, max_regno = max_reg_num ();
3503 ira_set_pseudo_classes (sched_verbose ? sched_dump : NULL);
3504 sched_regno_pressure_class
3505 = (enum reg_class *) xmalloc (max_regno * sizeof (enum reg_class));
3506 for (i = 0; i < max_regno; i++)
3507 sched_regno_pressure_class[i]
3508 = (i < FIRST_PSEUDO_REGISTER
3509 ? ira_pressure_class_translate[REGNO_REG_CLASS (i)]
3510 : ira_pressure_class_translate[reg_allocno_class (i)]);
3511 curr_reg_live = BITMAP_ALLOC (NULL);
3512 saved_reg_live = BITMAP_ALLOC (NULL);
3513 region_ref_regs = BITMAP_ALLOC (NULL);
3516 curr_state = xmalloc (dfa_state_size);
3519 static void haifa_init_only_bb (basic_block, basic_block);
3521 /* Initialize data structures specific to the Haifa scheduler. */
3523 haifa_sched_init (void)
3525 setup_sched_dump ();
3528 scheduled_insns = VEC_alloc (rtx, heap, 0);
3530 if (spec_info != NULL)
3532 sched_deps_info->use_deps_list = 1;
3533 sched_deps_info->generate_spec_deps = 1;
3536 /* Initialize luids, dependency caches, target and h_i_d for the
3539 bb_vec_t bbs = VEC_alloc (basic_block, heap, n_basic_blocks);
3545 VEC_quick_push (basic_block, bbs, bb);
3546 sched_init_luids (bbs);
3547 sched_deps_init (true);
3548 sched_extend_target ();
3549 haifa_init_h_i_d (bbs);
3551 VEC_free (basic_block, heap, bbs);
3554 sched_init_only_bb = haifa_init_only_bb;
3555 sched_split_block = sched_split_block_1;
3556 sched_create_empty_bb = sched_create_empty_bb_1;
3557 haifa_recovery_bb_ever_added_p = false;
3559 #ifdef ENABLE_CHECKING
3560 /* This is used preferably for finding bugs in check_cfg () itself.
3561 We must call sched_bbs_init () before check_cfg () because check_cfg ()
3562 assumes that the last insn in the last bb has a non-null successor. */
3566 nr_begin_data = nr_begin_control = nr_be_in_data = nr_be_in_control = 0;
3567 before_recovery = 0;
3571 /* Finish work with the data specific to the Haifa scheduler. */
3573 haifa_sched_finish (void)
3575 sched_create_empty_bb = NULL;
3576 sched_split_block = NULL;
3577 sched_init_only_bb = NULL;
3579 if (spec_info && spec_info->dump)
3581 char c = reload_completed ? 'a' : 'b';
3583 fprintf (spec_info->dump,
3584 ";; %s:\n", current_function_name ());
3586 fprintf (spec_info->dump,
3587 ";; Procedure %cr-begin-data-spec motions == %d\n",
3589 fprintf (spec_info->dump,
3590 ";; Procedure %cr-be-in-data-spec motions == %d\n",
3592 fprintf (spec_info->dump,
3593 ";; Procedure %cr-begin-control-spec motions == %d\n",
3594 c, nr_begin_control);
3595 fprintf (spec_info->dump,
3596 ";; Procedure %cr-be-in-control-spec motions == %d\n",
3597 c, nr_be_in_control);
3600 VEC_free (rtx, heap, scheduled_insns);
3602 /* Finalize h_i_d, dependency caches, and luids for the whole
3603 function. Target will be finalized in md_global_finish (). */
3604 sched_deps_finish ();
3605 sched_finish_luids ();
3606 current_sched_info = NULL;
3610 /* Free global data used during insn scheduling. This function works with
3611 the common data shared between the schedulers. */
3616 haifa_finish_h_i_d ();
3617 if (sched_pressure_p)
3619 free (sched_regno_pressure_class);
3620 BITMAP_FREE (region_ref_regs);
3621 BITMAP_FREE (saved_reg_live);
3622 BITMAP_FREE (curr_reg_live);
3626 if (targetm.sched.finish_global)
3627 targetm.sched.finish_global (sched_dump, sched_verbose);
3629 end_alias_analysis ();
3631 regstat_free_calls_crossed ();
3635 #ifdef ENABLE_CHECKING
3636 /* After reload ia64 backend clobbers CFG, so can't check anything. */
3637 if (!reload_completed)
3642 /* Fix INSN_TICKs of the instructions in the current block as well as
3643 INSN_TICKs of their dependents.
3644 HEAD and TAIL are the begin and the end of the current scheduled block. */
3646 fix_inter_tick (rtx head, rtx tail)
3648 /* Set of instructions with corrected INSN_TICK. */
3649 bitmap_head processed;
3650 /* ??? It is doubtful if we should assume that cycle advance happens on
3651 basic block boundaries. Basically insns that are unconditionally ready
3652 on the start of the block are more preferable then those which have
3653 a one cycle dependency over insn from the previous block. */
3654 int next_clock = clock_var + 1;
3656 bitmap_initialize (&processed, 0);
3658 /* Iterates over scheduled instructions and fix their INSN_TICKs and
3659 INSN_TICKs of dependent instructions, so that INSN_TICKs are consistent
3660 across different blocks. */
3661 for (tail = NEXT_INSN (tail); head != tail; head = NEXT_INSN (head))
3666 sd_iterator_def sd_it;
3669 tick = INSN_TICK (head);
3670 gcc_assert (tick >= MIN_TICK);
3672 /* Fix INSN_TICK of instruction from just scheduled block. */
3673 if (bitmap_set_bit (&processed, INSN_LUID (head)))
3677 if (tick < MIN_TICK)
3680 INSN_TICK (head) = tick;
3683 FOR_EACH_DEP (head, SD_LIST_RES_FORW, sd_it, dep)
3687 next = DEP_CON (dep);
3688 tick = INSN_TICK (next);
3690 if (tick != INVALID_TICK
3691 /* If NEXT has its INSN_TICK calculated, fix it.
3692 If not - it will be properly calculated from
3693 scratch later in fix_tick_ready. */
3694 && bitmap_set_bit (&processed, INSN_LUID (next)))
3698 if (tick < MIN_TICK)
3701 if (tick > INTER_TICK (next))
3702 INTER_TICK (next) = tick;
3704 tick = INTER_TICK (next);
3706 INSN_TICK (next) = tick;
3711 bitmap_clear (&processed);
3714 static int haifa_speculate_insn (rtx, ds_t, rtx *);
3716 /* Check if NEXT is ready to be added to the ready or queue list.
3717 If "yes", add it to the proper list.
3719 -1 - is not ready yet,
3720 0 - added to the ready list,
3721 0 < N - queued for N cycles. */
3723 try_ready (rtx next)
3727 ts = &TODO_SPEC (next);
3730 gcc_assert (!(old_ts & ~(SPECULATIVE | HARD_DEP))
3731 && ((old_ts & HARD_DEP)
3732 || (old_ts & SPECULATIVE)));
3734 if (sd_lists_empty_p (next, SD_LIST_BACK))
3735 /* NEXT has all its dependencies resolved. */
3737 /* Remove HARD_DEP bit from NEXT's status. */
3740 if (current_sched_info->flags & DO_SPECULATION)
3741 /* Remove all speculative bits from NEXT's status. */
3742 *ts &= ~SPECULATIVE;
3746 /* One of the NEXT's dependencies has been resolved.
3747 Recalculate NEXT's status. */
3749 *ts &= ~SPECULATIVE & ~HARD_DEP;
3751 if (sd_lists_empty_p (next, SD_LIST_HARD_BACK))
3752 /* Now we've got NEXT with speculative deps only.
3753 1. Look at the deps to see what we have to do.
3754 2. Check if we can do 'todo'. */
3756 sd_iterator_def sd_it;
3758 bool first_p = true;
3760 FOR_EACH_DEP (next, SD_LIST_BACK, sd_it, dep)
3762 ds_t ds = DEP_STATUS (dep) & SPECULATIVE;
3764 if (DEBUG_INSN_P (DEP_PRO (dep))
3765 && !DEBUG_INSN_P (next))
3775 *ts = ds_merge (*ts, ds);
3778 if (ds_weak (*ts) < spec_info->data_weakness_cutoff)
3779 /* Too few points. */
3780 *ts = (*ts & ~SPECULATIVE) | HARD_DEP;
3787 gcc_assert (*ts == old_ts
3788 && QUEUE_INDEX (next) == QUEUE_NOWHERE);
3789 else if (current_sched_info->new_ready)
3790 *ts = current_sched_info->new_ready (next, *ts);
3792 /* * if !(old_ts & SPECULATIVE) (e.g. HARD_DEP or 0), then insn might
3793 have its original pattern or changed (speculative) one. This is due
3794 to changing ebb in region scheduling.
3795 * But if (old_ts & SPECULATIVE), then we are pretty sure that insn
3796 has speculative pattern.
3798 We can't assert (!(*ts & HARD_DEP) || *ts == old_ts) 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 ()). */
3802 if ((*ts & SPECULATIVE)
3803 /* If (old_ts == *ts), then (old_ts & SPECULATIVE) and we don't
3804 need to change anything. */
3810 gcc_assert ((*ts & SPECULATIVE) && !(*ts & ~SPECULATIVE));
3812 res = haifa_speculate_insn (next, *ts, &new_pat);
3817 /* It would be nice to change DEP_STATUS of all dependences,
3818 which have ((DEP_STATUS & SPECULATIVE) == *ts) to HARD_DEP,
3819 so we won't reanalyze anything. */
3820 *ts = (*ts & ~SPECULATIVE) | HARD_DEP;
3824 /* We follow the rule, that every speculative insn
3825 has non-null ORIG_PAT. */
3826 if (!ORIG_PAT (next))
3827 ORIG_PAT (next) = PATTERN (next);
3831 if (!ORIG_PAT (next))
3832 /* If we gonna to overwrite the original pattern of insn,
3834 ORIG_PAT (next) = PATTERN (next);
3836 haifa_change_pattern (next, new_pat);
3844 /* We need to restore pattern only if (*ts == 0), because otherwise it is
3845 either correct (*ts & SPECULATIVE),
3846 or we simply don't care (*ts & HARD_DEP). */
3848 gcc_assert (!ORIG_PAT (next)
3849 || !IS_SPECULATION_BRANCHY_CHECK_P (next));
3853 /* We can't assert (QUEUE_INDEX (next) == QUEUE_NOWHERE) here because
3854 control-speculative NEXT could have been discarded by sched-rgn.c
3855 (the same case as when discarded by can_schedule_ready_p ()). */
3856 /*gcc_assert (QUEUE_INDEX (next) == QUEUE_NOWHERE);*/
3858 change_queue_index (next, QUEUE_NOWHERE);
3861 else if (!(*ts & BEGIN_SPEC) && ORIG_PAT (next) && !IS_SPECULATION_CHECK_P (next))
3862 /* We should change pattern of every previously speculative
3863 instruction - and we determine if NEXT was speculative by using
3864 ORIG_PAT field. Except one case - speculation checks have ORIG_PAT
3865 pat too, so skip them. */
3867 haifa_change_pattern (next, ORIG_PAT (next));
3868 ORIG_PAT (next) = 0;
3871 if (sched_verbose >= 2)
3873 int s = TODO_SPEC (next);
3875 fprintf (sched_dump, ";;\t\tdependencies resolved: insn %s",
3876 (*current_sched_info->print_insn) (next, 0));
3878 if (spec_info && spec_info->dump)
3881 fprintf (spec_info->dump, "; data-spec;");
3882 if (s & BEGIN_CONTROL)
3883 fprintf (spec_info->dump, "; control-spec;");
3884 if (s & BE_IN_CONTROL)
3885 fprintf (spec_info->dump, "; in-control-spec;");
3888 fprintf (sched_dump, "\n");
3891 adjust_priority (next);
3893 return fix_tick_ready (next);
3896 /* Calculate INSN_TICK of NEXT and add it to either ready or queue list. */
3898 fix_tick_ready (rtx next)
3902 if (!DEBUG_INSN_P (next) && !sd_lists_empty_p (next, SD_LIST_RES_BACK))
3905 sd_iterator_def sd_it;
3908 tick = INSN_TICK (next);
3909 /* if tick is not equal to INVALID_TICK, then update
3910 INSN_TICK of NEXT with the most recent resolved dependence
3911 cost. Otherwise, recalculate from scratch. */
3912 full_p = (tick == INVALID_TICK);
3914 FOR_EACH_DEP (next, SD_LIST_RES_BACK, sd_it, dep)
3916 rtx pro = DEP_PRO (dep);
3919 gcc_assert (INSN_TICK (pro) >= MIN_TICK);
3921 tick1 = INSN_TICK (pro) + dep_cost (dep);
3932 INSN_TICK (next) = tick;
3934 delay = tick - clock_var;
3935 if (delay <= 0 || sched_pressure_p)
3936 delay = QUEUE_READY;
3938 change_queue_index (next, delay);
3943 /* Move NEXT to the proper queue list with (DELAY >= 1),
3944 or add it to the ready list (DELAY == QUEUE_READY),
3945 or remove it from ready and queue lists at all (DELAY == QUEUE_NOWHERE). */
3947 change_queue_index (rtx next, int delay)
3949 int i = QUEUE_INDEX (next);
3951 gcc_assert (QUEUE_NOWHERE <= delay && delay <= max_insn_queue_index
3953 gcc_assert (i != QUEUE_SCHEDULED);
3955 if ((delay > 0 && NEXT_Q_AFTER (q_ptr, delay) == i)
3956 || (delay < 0 && delay == i))
3957 /* We have nothing to do. */
3960 /* Remove NEXT from wherever it is now. */
3961 if (i == QUEUE_READY)
3962 ready_remove_insn (next);
3964 queue_remove (next);
3966 /* Add it to the proper place. */
3967 if (delay == QUEUE_READY)
3968 ready_add (readyp, next, false);
3969 else if (delay >= 1)
3970 queue_insn (next, delay, "change queue index");
3972 if (sched_verbose >= 2)
3974 fprintf (sched_dump, ";;\t\ttick updated: insn %s",
3975 (*current_sched_info->print_insn) (next, 0));
3977 if (delay == QUEUE_READY)
3978 fprintf (sched_dump, " into ready\n");
3979 else if (delay >= 1)
3980 fprintf (sched_dump, " into queue with cost=%d\n", delay);
3982 fprintf (sched_dump, " removed from ready or queue lists\n");
3986 static int sched_ready_n_insns = -1;
3988 /* Initialize per region data structures. */
3990 sched_extend_ready_list (int new_sched_ready_n_insns)
3994 if (sched_ready_n_insns == -1)
3995 /* At the first call we need to initialize one more choice_stack
3999 sched_ready_n_insns = 0;
4000 VEC_reserve (rtx, heap, scheduled_insns, new_sched_ready_n_insns);
4003 i = sched_ready_n_insns + 1;
4005 ready.veclen = new_sched_ready_n_insns + issue_rate;
4006 ready.vec = XRESIZEVEC (rtx, ready.vec, ready.veclen);
4008 gcc_assert (new_sched_ready_n_insns >= sched_ready_n_insns);
4010 ready_try = (char *) xrecalloc (ready_try, new_sched_ready_n_insns,
4011 sched_ready_n_insns, sizeof (*ready_try));
4013 /* We allocate +1 element to save initial state in the choice_stack[0]
4015 choice_stack = XRESIZEVEC (struct choice_entry, choice_stack,
4016 new_sched_ready_n_insns + 1);
4018 for (; i <= new_sched_ready_n_insns; i++)
4020 choice_stack[i].state = xmalloc (dfa_state_size);
4022 if (targetm.sched.first_cycle_multipass_init)
4023 targetm.sched.first_cycle_multipass_init (&(choice_stack[i]
4027 sched_ready_n_insns = new_sched_ready_n_insns;
4030 /* Free per region data structures. */
4032 sched_finish_ready_list (void)
4043 for (i = 0; i <= sched_ready_n_insns; i++)
4045 if (targetm.sched.first_cycle_multipass_fini)
4046 targetm.sched.first_cycle_multipass_fini (&(choice_stack[i]
4049 free (choice_stack [i].state);
4051 free (choice_stack);
4052 choice_stack = NULL;
4054 sched_ready_n_insns = -1;
4058 haifa_luid_for_non_insn (rtx x)
4060 gcc_assert (NOTE_P (x) || LABEL_P (x));
4065 /* Generates recovery code for INSN. */
4067 generate_recovery_code (rtx insn)
4069 if (TODO_SPEC (insn) & BEGIN_SPEC)
4070 begin_speculative_block (insn);
4072 /* Here we have insn with no dependencies to
4073 instructions other then CHECK_SPEC ones. */
4075 if (TODO_SPEC (insn) & BE_IN_SPEC)
4076 add_to_speculative_block (insn);
4080 Tries to add speculative dependencies of type FS between instructions
4081 in deps_list L and TWIN. */
4083 process_insn_forw_deps_be_in_spec (rtx insn, rtx twin, ds_t fs)
4085 sd_iterator_def sd_it;
4088 FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
4093 consumer = DEP_CON (dep);
4095 ds = DEP_STATUS (dep);
4097 if (/* If we want to create speculative dep. */
4099 /* And we can do that because this is a true dep. */
4100 && (ds & DEP_TYPES) == DEP_TRUE)
4102 gcc_assert (!(ds & BE_IN_SPEC));
4104 if (/* If this dep can be overcome with 'begin speculation'. */
4106 /* Then we have a choice: keep the dep 'begin speculative'
4107 or transform it into 'be in speculative'. */
4109 if (/* In try_ready we assert that if insn once became ready
4110 it can be removed from the ready (or queue) list only
4111 due to backend decision. Hence we can't let the
4112 probability of the speculative dep to decrease. */
4113 ds_weak (ds) <= ds_weak (fs))
4117 new_ds = (ds & ~BEGIN_SPEC) | fs;
4119 if (/* consumer can 'be in speculative'. */
4120 sched_insn_is_legitimate_for_speculation_p (consumer,
4122 /* Transform it to be in speculative. */
4127 /* Mark the dep as 'be in speculative'. */
4132 dep_def _new_dep, *new_dep = &_new_dep;
4134 init_dep_1 (new_dep, twin, consumer, DEP_TYPE (dep), ds);
4135 sd_add_dep (new_dep, false);
4140 /* Generates recovery code for BEGIN speculative INSN. */
4142 begin_speculative_block (rtx insn)
4144 if (TODO_SPEC (insn) & BEGIN_DATA)
4146 if (TODO_SPEC (insn) & BEGIN_CONTROL)
4149 create_check_block_twin (insn, false);
4151 TODO_SPEC (insn) &= ~BEGIN_SPEC;
4154 static void haifa_init_insn (rtx);
4156 /* Generates recovery code for BE_IN speculative INSN. */
4158 add_to_speculative_block (rtx insn)
4161 sd_iterator_def sd_it;
4164 rtx_vec_t priorities_roots;
4166 ts = TODO_SPEC (insn);
4167 gcc_assert (!(ts & ~BE_IN_SPEC));
4169 if (ts & BE_IN_DATA)
4171 if (ts & BE_IN_CONTROL)
4174 TODO_SPEC (insn) &= ~BE_IN_SPEC;
4175 gcc_assert (!TODO_SPEC (insn));
4177 DONE_SPEC (insn) |= ts;
4179 /* First we convert all simple checks to branchy. */
4180 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
4181 sd_iterator_cond (&sd_it, &dep);)
4183 rtx check = DEP_PRO (dep);
4185 if (IS_SPECULATION_SIMPLE_CHECK_P (check))
4187 create_check_block_twin (check, true);
4189 /* Restart search. */
4190 sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
4193 /* Continue search. */
4194 sd_iterator_next (&sd_it);
4197 priorities_roots = NULL;
4198 clear_priorities (insn, &priorities_roots);
4205 /* Get the first backward dependency of INSN. */
4206 sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
4207 if (!sd_iterator_cond (&sd_it, &dep))
4208 /* INSN has no backward dependencies left. */
4211 gcc_assert ((DEP_STATUS (dep) & BEGIN_SPEC) == 0
4212 && (DEP_STATUS (dep) & BE_IN_SPEC) != 0
4213 && (DEP_STATUS (dep) & DEP_TYPES) == DEP_TRUE);
4215 check = DEP_PRO (dep);
4217 gcc_assert (!IS_SPECULATION_CHECK_P (check) && !ORIG_PAT (check)
4218 && QUEUE_INDEX (check) == QUEUE_NOWHERE);
4220 rec = BLOCK_FOR_INSN (check);
4222 twin = emit_insn_before (copy_insn (PATTERN (insn)), BB_END (rec));
4223 haifa_init_insn (twin);
4225 sd_copy_back_deps (twin, insn, true);
4227 if (sched_verbose && spec_info->dump)
4228 /* INSN_BB (insn) isn't determined for twin insns yet.
4229 So we can't use current_sched_info->print_insn. */
4230 fprintf (spec_info->dump, ";;\t\tGenerated twin insn : %d/rec%d\n",
4231 INSN_UID (twin), rec->index);
4233 twins = alloc_INSN_LIST (twin, twins);
4235 /* Add dependences between TWIN and all appropriate
4236 instructions from REC. */
4237 FOR_EACH_DEP (insn, SD_LIST_SPEC_BACK, sd_it, dep)
4239 rtx pro = DEP_PRO (dep);
4241 gcc_assert (DEP_TYPE (dep) == REG_DEP_TRUE);
4243 /* INSN might have dependencies from the instructions from
4244 several recovery blocks. At this iteration we process those
4245 producers that reside in REC. */
4246 if (BLOCK_FOR_INSN (pro) == rec)
4248 dep_def _new_dep, *new_dep = &_new_dep;
4250 init_dep (new_dep, pro, twin, REG_DEP_TRUE);
4251 sd_add_dep (new_dep, false);
4255 process_insn_forw_deps_be_in_spec (insn, twin, ts);
4257 /* Remove all dependencies between INSN and insns in REC. */
4258 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
4259 sd_iterator_cond (&sd_it, &dep);)
4261 rtx pro = DEP_PRO (dep);
4263 if (BLOCK_FOR_INSN (pro) == rec)
4264 sd_delete_dep (sd_it);
4266 sd_iterator_next (&sd_it);
4270 /* We couldn't have added the dependencies between INSN and TWINS earlier
4271 because that would make TWINS appear in the INSN_BACK_DEPS (INSN). */
4276 twin = XEXP (twins, 0);
4279 dep_def _new_dep, *new_dep = &_new_dep;
4281 init_dep (new_dep, insn, twin, REG_DEP_OUTPUT);
4282 sd_add_dep (new_dep, false);
4285 twin = XEXP (twins, 1);
4286 free_INSN_LIST_node (twins);
4290 calc_priorities (priorities_roots);
4291 VEC_free (rtx, heap, priorities_roots);
4294 /* Extends and fills with zeros (only the new part) array pointed to by P. */
4296 xrecalloc (void *p, size_t new_nmemb, size_t old_nmemb, size_t size)
4298 gcc_assert (new_nmemb >= old_nmemb);
4299 p = XRESIZEVAR (void, p, new_nmemb * size);
4300 memset (((char *) p) + old_nmemb * size, 0, (new_nmemb - old_nmemb) * size);
4305 Find fallthru edge from PRED. */
4307 find_fallthru_edge_from (basic_block pred)
4312 succ = pred->next_bb;
4313 gcc_assert (succ->prev_bb == pred);
4315 if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds))
4317 e = find_fallthru_edge (pred->succs);
4321 gcc_assert (e->dest == succ);
4327 e = find_fallthru_edge (succ->preds);
4331 gcc_assert (e->src == pred);
4339 /* Extend per basic block data structures. */
4341 sched_extend_bb (void)
4345 /* The following is done to keep current_sched_info->next_tail non null. */
4346 insn = BB_END (EXIT_BLOCK_PTR->prev_bb);
4347 if (NEXT_INSN (insn) == 0
4350 /* Don't emit a NOTE if it would end up before a BARRIER. */
4351 && !BARRIER_P (NEXT_INSN (insn))))
4353 rtx note = emit_note_after (NOTE_INSN_DELETED, insn);
4354 /* Make insn appear outside BB. */
4355 set_block_for_insn (note, NULL);
4356 BB_END (EXIT_BLOCK_PTR->prev_bb) = insn;
4360 /* Init per basic block data structures. */
4362 sched_init_bbs (void)
4367 /* Initialize BEFORE_RECOVERY variable. */
4369 init_before_recovery (basic_block *before_recovery_ptr)
4374 last = EXIT_BLOCK_PTR->prev_bb;
4375 e = find_fallthru_edge_from (last);
4379 /* We create two basic blocks:
4380 1. Single instruction block is inserted right after E->SRC
4382 2. Empty block right before EXIT_BLOCK.
4383 Between these two blocks recovery blocks will be emitted. */
4385 basic_block single, empty;
4388 /* If the fallthrough edge to exit we've found is from the block we've
4389 created before, don't do anything more. */
4390 if (last == after_recovery)
4393 adding_bb_to_current_region_p = false;
4395 single = sched_create_empty_bb (last);
4396 empty = sched_create_empty_bb (single);
4398 /* Add new blocks to the root loop. */
4399 if (current_loops != NULL)
4401 add_bb_to_loop (single, VEC_index (loop_p, current_loops->larray, 0));
4402 add_bb_to_loop (empty, VEC_index (loop_p, current_loops->larray, 0));
4405 single->count = last->count;
4406 empty->count = last->count;
4407 single->frequency = last->frequency;
4408 empty->frequency = last->frequency;
4409 BB_COPY_PARTITION (single, last);
4410 BB_COPY_PARTITION (empty, last);
4412 redirect_edge_succ (e, single);
4413 make_single_succ_edge (single, empty, 0);
4414 make_single_succ_edge (empty, EXIT_BLOCK_PTR,
4415 EDGE_FALLTHRU | EDGE_CAN_FALLTHRU);
4417 label = block_label (empty);
4418 x = emit_jump_insn_after (gen_jump (label), BB_END (single));
4419 JUMP_LABEL (x) = label;
4420 LABEL_NUSES (label)++;
4421 haifa_init_insn (x);
4423 emit_barrier_after (x);
4425 sched_init_only_bb (empty, NULL);
4426 sched_init_only_bb (single, NULL);
4429 adding_bb_to_current_region_p = true;
4430 before_recovery = single;
4431 after_recovery = empty;
4433 if (before_recovery_ptr)
4434 *before_recovery_ptr = before_recovery;
4436 if (sched_verbose >= 2 && spec_info->dump)
4437 fprintf (spec_info->dump,
4438 ";;\t\tFixed fallthru to EXIT : %d->>%d->%d->>EXIT\n",
4439 last->index, single->index, empty->index);
4442 before_recovery = last;
4445 /* Returns new recovery block. */
4447 sched_create_recovery_block (basic_block *before_recovery_ptr)
4453 haifa_recovery_bb_recently_added_p = true;
4454 haifa_recovery_bb_ever_added_p = true;
4456 init_before_recovery (before_recovery_ptr);
4458 barrier = get_last_bb_insn (before_recovery);
4459 gcc_assert (BARRIER_P (barrier));
4461 label = emit_label_after (gen_label_rtx (), barrier);
4463 rec = create_basic_block (label, label, before_recovery);
4465 /* A recovery block always ends with an unconditional jump. */
4466 emit_barrier_after (BB_END (rec));
4468 if (BB_PARTITION (before_recovery) != BB_UNPARTITIONED)
4469 BB_SET_PARTITION (rec, BB_COLD_PARTITION);
4471 if (sched_verbose && spec_info->dump)
4472 fprintf (spec_info->dump, ";;\t\tGenerated recovery block rec%d\n",
4478 /* Create edges: FIRST_BB -> REC; FIRST_BB -> SECOND_BB; REC -> SECOND_BB
4479 and emit necessary jumps. */
4481 sched_create_recovery_edges (basic_block first_bb, basic_block rec,
4482 basic_block second_bb)
4488 /* This is fixing of incoming edge. */
4489 /* ??? Which other flags should be specified? */
4490 if (BB_PARTITION (first_bb) != BB_PARTITION (rec))
4491 /* Partition type is the same, if it is "unpartitioned". */
4492 edge_flags = EDGE_CROSSING;
4496 make_edge (first_bb, rec, edge_flags);
4497 label = block_label (second_bb);
4498 jump = emit_jump_insn_after (gen_jump (label), BB_END (rec));
4499 JUMP_LABEL (jump) = label;
4500 LABEL_NUSES (label)++;
4502 if (BB_PARTITION (second_bb) != BB_PARTITION (rec))
4503 /* Partition type is the same, if it is "unpartitioned". */
4505 /* Rewritten from cfgrtl.c. */
4506 if (flag_reorder_blocks_and_partition
4507 && targetm_common.have_named_sections)
4509 /* We don't need the same note for the check because
4510 any_condjump_p (check) == true. */
4511 add_reg_note (jump, REG_CROSSING_JUMP, NULL_RTX);
4513 edge_flags = EDGE_CROSSING;
4518 make_single_succ_edge (rec, second_bb, edge_flags);
4519 if (dom_info_available_p (CDI_DOMINATORS))
4520 set_immediate_dominator (CDI_DOMINATORS, rec, first_bb);
4523 /* This function creates recovery code for INSN. If MUTATE_P is nonzero,
4524 INSN is a simple check, that should be converted to branchy one. */
4526 create_check_block_twin (rtx insn, bool mutate_p)
4529 rtx label, check, twin;
4531 sd_iterator_def sd_it;
4533 dep_def _new_dep, *new_dep = &_new_dep;
4536 gcc_assert (ORIG_PAT (insn) != NULL_RTX);
4539 todo_spec = TODO_SPEC (insn);
4542 gcc_assert (IS_SPECULATION_SIMPLE_CHECK_P (insn)
4543 && (TODO_SPEC (insn) & SPECULATIVE) == 0);
4545 todo_spec = CHECK_SPEC (insn);
4548 todo_spec &= SPECULATIVE;
4550 /* Create recovery block. */
4551 if (mutate_p || targetm.sched.needs_block_p (todo_spec))
4553 rec = sched_create_recovery_block (NULL);
4554 label = BB_HEAD (rec);
4558 rec = EXIT_BLOCK_PTR;
4563 check = targetm.sched.gen_spec_check (insn, label, todo_spec);
4565 if (rec != EXIT_BLOCK_PTR)
4567 /* To have mem_reg alive at the beginning of second_bb,
4568 we emit check BEFORE insn, so insn after splitting
4569 insn will be at the beginning of second_bb, which will
4570 provide us with the correct life information. */
4571 check = emit_jump_insn_before (check, insn);
4572 JUMP_LABEL (check) = label;
4573 LABEL_NUSES (label)++;
4576 check = emit_insn_before (check, insn);
4578 /* Extend data structures. */
4579 haifa_init_insn (check);
4581 /* CHECK is being added to current region. Extend ready list. */
4582 gcc_assert (sched_ready_n_insns != -1);
4583 sched_extend_ready_list (sched_ready_n_insns + 1);
4585 if (current_sched_info->add_remove_insn)
4586 current_sched_info->add_remove_insn (insn, 0);
4588 RECOVERY_BLOCK (check) = rec;
4590 if (sched_verbose && spec_info->dump)
4591 fprintf (spec_info->dump, ";;\t\tGenerated check insn : %s\n",
4592 (*current_sched_info->print_insn) (check, 0));
4594 gcc_assert (ORIG_PAT (insn));
4596 /* Initialize TWIN (twin is a duplicate of original instruction
4597 in the recovery block). */
4598 if (rec != EXIT_BLOCK_PTR)
4600 sd_iterator_def sd_it;
4603 FOR_EACH_DEP (insn, SD_LIST_RES_BACK, sd_it, dep)
4604 if ((DEP_STATUS (dep) & DEP_OUTPUT) != 0)
4606 struct _dep _dep2, *dep2 = &_dep2;
4608 init_dep (dep2, DEP_PRO (dep), check, REG_DEP_TRUE);
4610 sd_add_dep (dep2, true);
4613 twin = emit_insn_after (ORIG_PAT (insn), BB_END (rec));
4614 haifa_init_insn (twin);
4616 if (sched_verbose && spec_info->dump)
4617 /* INSN_BB (insn) isn't determined for twin insns yet.
4618 So we can't use current_sched_info->print_insn. */
4619 fprintf (spec_info->dump, ";;\t\tGenerated twin insn : %d/rec%d\n",
4620 INSN_UID (twin), rec->index);
4624 ORIG_PAT (check) = ORIG_PAT (insn);
4625 HAS_INTERNAL_DEP (check) = 1;
4627 /* ??? We probably should change all OUTPUT dependencies to
4631 /* Copy all resolved back dependencies of INSN to TWIN. This will
4632 provide correct value for INSN_TICK (TWIN). */
4633 sd_copy_back_deps (twin, insn, true);
4635 if (rec != EXIT_BLOCK_PTR)
4636 /* In case of branchy check, fix CFG. */
4638 basic_block first_bb, second_bb;
4641 first_bb = BLOCK_FOR_INSN (check);
4642 second_bb = sched_split_block (first_bb, check);
4644 sched_create_recovery_edges (first_bb, rec, second_bb);
4646 sched_init_only_bb (second_bb, first_bb);
4647 sched_init_only_bb (rec, EXIT_BLOCK_PTR);
4649 jump = BB_END (rec);
4650 haifa_init_insn (jump);
4653 /* Move backward dependences from INSN to CHECK and
4654 move forward dependences from INSN to TWIN. */
4656 /* First, create dependencies between INSN's producers and CHECK & TWIN. */
4657 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
4659 rtx pro = DEP_PRO (dep);
4662 /* If BEGIN_DATA: [insn ~~TRUE~~> producer]:
4663 check --TRUE--> producer ??? or ANTI ???
4664 twin --TRUE--> producer
4665 twin --ANTI--> check
4667 If BEGIN_CONTROL: [insn ~~ANTI~~> producer]:
4668 check --ANTI--> producer
4669 twin --ANTI--> producer
4670 twin --ANTI--> check
4672 If BE_IN_SPEC: [insn ~~TRUE~~> producer]:
4673 check ~~TRUE~~> producer
4674 twin ~~TRUE~~> producer
4675 twin --ANTI--> check */
4677 ds = DEP_STATUS (dep);
4679 if (ds & BEGIN_SPEC)
4681 gcc_assert (!mutate_p);
4685 init_dep_1 (new_dep, pro, check, DEP_TYPE (dep), ds);
4686 sd_add_dep (new_dep, false);
4688 if (rec != EXIT_BLOCK_PTR)
4690 DEP_CON (new_dep) = twin;
4691 sd_add_dep (new_dep, false);
4695 /* Second, remove backward dependencies of INSN. */
4696 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
4697 sd_iterator_cond (&sd_it, &dep);)
4699 if ((DEP_STATUS (dep) & BEGIN_SPEC)
4701 /* We can delete this dep because we overcome it with
4702 BEGIN_SPECULATION. */
4703 sd_delete_dep (sd_it);
4705 sd_iterator_next (&sd_it);
4708 /* Future Speculations. Determine what BE_IN speculations will be like. */
4711 /* Fields (DONE_SPEC (x) & BEGIN_SPEC) and CHECK_SPEC (x) are set only
4714 gcc_assert (!DONE_SPEC (insn));
4718 ds_t ts = TODO_SPEC (insn);
4720 DONE_SPEC (insn) = ts & BEGIN_SPEC;
4721 CHECK_SPEC (check) = ts & BEGIN_SPEC;
4723 /* Luckiness of future speculations solely depends upon initial
4724 BEGIN speculation. */
4725 if (ts & BEGIN_DATA)
4726 fs = set_dep_weak (fs, BE_IN_DATA, get_dep_weak (ts, BEGIN_DATA));
4727 if (ts & BEGIN_CONTROL)
4728 fs = set_dep_weak (fs, BE_IN_CONTROL,
4729 get_dep_weak (ts, BEGIN_CONTROL));
4732 CHECK_SPEC (check) = CHECK_SPEC (insn);
4734 /* Future speculations: call the helper. */
4735 process_insn_forw_deps_be_in_spec (insn, twin, fs);
4737 if (rec != EXIT_BLOCK_PTR)
4739 /* Which types of dependencies should we use here is,
4740 generally, machine-dependent question... But, for now,
4745 init_dep (new_dep, insn, check, REG_DEP_TRUE);
4746 sd_add_dep (new_dep, false);
4748 init_dep (new_dep, insn, twin, REG_DEP_OUTPUT);
4749 sd_add_dep (new_dep, false);
4753 if (spec_info->dump)
4754 fprintf (spec_info->dump, ";;\t\tRemoved simple check : %s\n",
4755 (*current_sched_info->print_insn) (insn, 0));
4757 /* Remove all dependencies of the INSN. */
4759 sd_it = sd_iterator_start (insn, (SD_LIST_FORW
4761 | SD_LIST_RES_BACK));
4762 while (sd_iterator_cond (&sd_it, &dep))
4763 sd_delete_dep (sd_it);
4766 /* If former check (INSN) already was moved to the ready (or queue)
4767 list, add new check (CHECK) there too. */
4768 if (QUEUE_INDEX (insn) != QUEUE_NOWHERE)
4771 /* Remove old check from instruction stream and free its
4773 sched_remove_insn (insn);
4776 init_dep (new_dep, check, twin, REG_DEP_ANTI);
4777 sd_add_dep (new_dep, false);
4781 init_dep_1 (new_dep, insn, check, REG_DEP_TRUE, DEP_TRUE | DEP_OUTPUT);
4782 sd_add_dep (new_dep, false);
4786 /* Fix priorities. If MUTATE_P is nonzero, this is not necessary,
4787 because it'll be done later in add_to_speculative_block. */
4789 rtx_vec_t priorities_roots = NULL;
4791 clear_priorities (twin, &priorities_roots);
4792 calc_priorities (priorities_roots);
4793 VEC_free (rtx, heap, priorities_roots);
4797 /* Removes dependency between instructions in the recovery block REC
4798 and usual region instructions. It keeps inner dependences so it
4799 won't be necessary to recompute them. */
4801 fix_recovery_deps (basic_block rec)
4803 rtx note, insn, jump, ready_list = 0;
4804 bitmap_head in_ready;
4807 bitmap_initialize (&in_ready, 0);
4809 /* NOTE - a basic block note. */
4810 note = NEXT_INSN (BB_HEAD (rec));
4811 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
4812 insn = BB_END (rec);
4813 gcc_assert (JUMP_P (insn));
4814 insn = PREV_INSN (insn);
4818 sd_iterator_def sd_it;
4821 for (sd_it = sd_iterator_start (insn, SD_LIST_FORW);
4822 sd_iterator_cond (&sd_it, &dep);)
4824 rtx consumer = DEP_CON (dep);
4826 if (BLOCK_FOR_INSN (consumer) != rec)
4828 sd_delete_dep (sd_it);
4830 if (bitmap_set_bit (&in_ready, INSN_LUID (consumer)))
4831 ready_list = alloc_INSN_LIST (consumer, ready_list);
4835 gcc_assert ((DEP_STATUS (dep) & DEP_TYPES) == DEP_TRUE);
4837 sd_iterator_next (&sd_it);
4841 insn = PREV_INSN (insn);
4843 while (insn != note);
4845 bitmap_clear (&in_ready);
4847 /* Try to add instructions to the ready or queue list. */
4848 for (link = ready_list; link; link = XEXP (link, 1))
4849 try_ready (XEXP (link, 0));
4850 free_INSN_LIST_list (&ready_list);
4852 /* Fixing jump's dependences. */
4853 insn = BB_HEAD (rec);
4854 jump = BB_END (rec);
4856 gcc_assert (LABEL_P (insn));
4857 insn = NEXT_INSN (insn);
4859 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
4860 add_jump_dependencies (insn, jump);
4863 /* Change pattern of INSN to NEW_PAT. */
4865 sched_change_pattern (rtx insn, rtx new_pat)
4869 t = validate_change (insn, &PATTERN (insn), new_pat, 0);
4871 dfa_clear_single_insn_cache (insn);
4874 /* Change pattern of INSN to NEW_PAT. Invalidate cached haifa
4875 instruction data. */
4877 haifa_change_pattern (rtx insn, rtx new_pat)
4879 sched_change_pattern (insn, new_pat);
4881 /* Invalidate INSN_COST, so it'll be recalculated. */
4882 INSN_COST (insn) = -1;
4883 /* Invalidate INSN_TICK, so it'll be recalculated. */
4884 INSN_TICK (insn) = INVALID_TICK;
4887 /* -1 - can't speculate,
4888 0 - for speculation with REQUEST mode it is OK to use
4889 current instruction pattern,
4890 1 - need to change pattern for *NEW_PAT to be speculative. */
4892 sched_speculate_insn (rtx insn, ds_t request, rtx *new_pat)
4894 gcc_assert (current_sched_info->flags & DO_SPECULATION
4895 && (request & SPECULATIVE)
4896 && sched_insn_is_legitimate_for_speculation_p (insn, request));
4898 if ((request & spec_info->mask) != request)
4901 if (request & BE_IN_SPEC
4902 && !(request & BEGIN_SPEC))
4905 return targetm.sched.speculate_insn (insn, request, new_pat);
4909 haifa_speculate_insn (rtx insn, ds_t request, rtx *new_pat)
4911 gcc_assert (sched_deps_info->generate_spec_deps
4912 && !IS_SPECULATION_CHECK_P (insn));
4914 if (HAS_INTERNAL_DEP (insn)
4915 || SCHED_GROUP_P (insn))
4918 return sched_speculate_insn (insn, request, new_pat);
4921 /* Print some information about block BB, which starts with HEAD and
4922 ends with TAIL, before scheduling it.
4923 I is zero, if scheduler is about to start with the fresh ebb. */
4925 dump_new_block_header (int i, basic_block bb, rtx head, rtx tail)
4928 fprintf (sched_dump,
4929 ";; ======================================================\n");
4931 fprintf (sched_dump,
4932 ";; =====================ADVANCING TO=====================\n");
4933 fprintf (sched_dump,
4934 ";; -- basic block %d from %d to %d -- %s reload\n",
4935 bb->index, INSN_UID (head), INSN_UID (tail),
4936 (reload_completed ? "after" : "before"));
4937 fprintf (sched_dump,
4938 ";; ======================================================\n");
4939 fprintf (sched_dump, "\n");
4942 /* Unlink basic block notes and labels and saves them, so they
4943 can be easily restored. We unlink basic block notes in EBB to
4944 provide back-compatibility with the previous code, as target backends
4945 assume, that there'll be only instructions between
4946 current_sched_info->{head and tail}. We restore these notes as soon
4948 FIRST (LAST) is the first (last) basic block in the ebb.
4949 NB: In usual case (FIRST == LAST) nothing is really done. */
4951 unlink_bb_notes (basic_block first, basic_block last)
4953 /* We DON'T unlink basic block notes of the first block in the ebb. */
4957 bb_header = XNEWVEC (rtx, last_basic_block);
4959 /* Make a sentinel. */
4960 if (last->next_bb != EXIT_BLOCK_PTR)
4961 bb_header[last->next_bb->index] = 0;
4963 first = first->next_bb;
4966 rtx prev, label, note, next;
4968 label = BB_HEAD (last);
4969 if (LABEL_P (label))
4970 note = NEXT_INSN (label);
4973 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
4975 prev = PREV_INSN (label);
4976 next = NEXT_INSN (note);
4977 gcc_assert (prev && next);
4979 NEXT_INSN (prev) = next;
4980 PREV_INSN (next) = prev;
4982 bb_header[last->index] = label;
4987 last = last->prev_bb;
4992 /* Restore basic block notes.
4993 FIRST is the first basic block in the ebb. */
4995 restore_bb_notes (basic_block first)
5000 /* We DON'T unlink basic block notes of the first block in the ebb. */
5001 first = first->next_bb;
5002 /* Remember: FIRST is actually a second basic block in the ebb. */
5004 while (first != EXIT_BLOCK_PTR
5005 && bb_header[first->index])
5007 rtx prev, label, note, next;
5009 label = bb_header[first->index];
5010 prev = PREV_INSN (label);
5011 next = NEXT_INSN (prev);
5013 if (LABEL_P (label))
5014 note = NEXT_INSN (label);
5017 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
5019 bb_header[first->index] = 0;
5021 NEXT_INSN (prev) = label;
5022 NEXT_INSN (note) = next;
5023 PREV_INSN (next) = note;
5025 first = first->next_bb;
5033 Fix CFG after both in- and inter-block movement of
5034 control_flow_insn_p JUMP. */
5036 fix_jump_move (rtx jump)
5038 basic_block bb, jump_bb, jump_bb_next;
5040 bb = BLOCK_FOR_INSN (PREV_INSN (jump));
5041 jump_bb = BLOCK_FOR_INSN (jump);
5042 jump_bb_next = jump_bb->next_bb;
5044 gcc_assert (common_sched_info->sched_pass_id == SCHED_EBB_PASS
5045 || IS_SPECULATION_BRANCHY_CHECK_P (jump));
5047 if (!NOTE_INSN_BASIC_BLOCK_P (BB_END (jump_bb_next)))
5048 /* if jump_bb_next is not empty. */
5049 BB_END (jump_bb) = BB_END (jump_bb_next);
5051 if (BB_END (bb) != PREV_INSN (jump))
5052 /* Then there are instruction after jump that should be placed
5054 BB_END (jump_bb_next) = BB_END (bb);
5056 /* Otherwise jump_bb_next is empty. */
5057 BB_END (jump_bb_next) = NEXT_INSN (BB_HEAD (jump_bb_next));
5059 /* To make assertion in move_insn happy. */
5060 BB_END (bb) = PREV_INSN (jump);
5062 update_bb_for_insn (jump_bb_next);
5065 /* Fix CFG after interblock movement of control_flow_insn_p JUMP. */
5067 move_block_after_check (rtx jump)
5069 basic_block bb, jump_bb, jump_bb_next;
5072 bb = BLOCK_FOR_INSN (PREV_INSN (jump));
5073 jump_bb = BLOCK_FOR_INSN (jump);
5074 jump_bb_next = jump_bb->next_bb;
5076 update_bb_for_insn (jump_bb);
5078 gcc_assert (IS_SPECULATION_CHECK_P (jump)
5079 || IS_SPECULATION_CHECK_P (BB_END (jump_bb_next)));
5081 unlink_block (jump_bb_next);
5082 link_block (jump_bb_next, bb);
5086 move_succs (&(jump_bb->succs), bb);
5087 move_succs (&(jump_bb_next->succs), jump_bb);
5088 move_succs (&t, jump_bb_next);
5090 df_mark_solutions_dirty ();
5092 common_sched_info->fix_recovery_cfg
5093 (bb->index, jump_bb->index, jump_bb_next->index);
5096 /* Helper function for move_block_after_check.
5097 This functions attaches edge vector pointed to by SUCCSP to
5100 move_succs (VEC(edge,gc) **succsp, basic_block to)
5105 gcc_assert (to->succs == 0);
5107 to->succs = *succsp;
5109 FOR_EACH_EDGE (e, ei, to->succs)
5115 /* Remove INSN from the instruction stream.
5116 INSN should have any dependencies. */
5118 sched_remove_insn (rtx insn)
5120 sd_finish_insn (insn);
5122 change_queue_index (insn, QUEUE_NOWHERE);
5123 current_sched_info->add_remove_insn (insn, 1);
5127 /* Clear priorities of all instructions, that are forward dependent on INSN.
5128 Store in vector pointed to by ROOTS_PTR insns on which priority () should
5129 be invoked to initialize all cleared priorities. */
5131 clear_priorities (rtx insn, rtx_vec_t *roots_ptr)
5133 sd_iterator_def sd_it;
5135 bool insn_is_root_p = true;
5137 gcc_assert (QUEUE_INDEX (insn) != QUEUE_SCHEDULED);
5139 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
5141 rtx pro = DEP_PRO (dep);
5143 if (INSN_PRIORITY_STATUS (pro) >= 0
5144 && QUEUE_INDEX (insn) != QUEUE_SCHEDULED)
5146 /* If DEP doesn't contribute to priority then INSN itself should
5147 be added to priority roots. */
5148 if (contributes_to_priority_p (dep))
5149 insn_is_root_p = false;
5151 INSN_PRIORITY_STATUS (pro) = -1;
5152 clear_priorities (pro, roots_ptr);
5157 VEC_safe_push (rtx, heap, *roots_ptr, insn);
5160 /* Recompute priorities of instructions, whose priorities might have been
5161 changed. ROOTS is a vector of instructions whose priority computation will
5162 trigger initialization of all cleared priorities. */
5164 calc_priorities (rtx_vec_t roots)
5169 FOR_EACH_VEC_ELT (rtx, roots, i, insn)
5174 /* Add dependences between JUMP and other instructions in the recovery
5175 block. INSN is the first insn the recovery block. */
5177 add_jump_dependencies (rtx insn, rtx jump)
5181 insn = NEXT_INSN (insn);
5185 if (dep_list_size (insn) == 0)
5187 dep_def _new_dep, *new_dep = &_new_dep;
5189 init_dep (new_dep, insn, jump, REG_DEP_ANTI);
5190 sd_add_dep (new_dep, false);
5195 gcc_assert (!sd_lists_empty_p (jump, SD_LIST_BACK));
5198 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
5200 bb_note (basic_block bb)
5204 note = BB_HEAD (bb);
5206 note = NEXT_INSN (note);
5208 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
5212 #ifdef ENABLE_CHECKING
5213 /* Helper function for check_cfg.
5214 Return nonzero, if edge vector pointed to by EL has edge with TYPE in
5217 has_edge_p (VEC(edge,gc) *el, int type)
5222 FOR_EACH_EDGE (e, ei, el)
5223 if (e->flags & type)
5228 /* Search back, starting at INSN, for an insn that is not a
5229 NOTE_INSN_VAR_LOCATION. Don't search beyond HEAD, and return it if
5230 no such insn can be found. */
5232 prev_non_location_insn (rtx insn, rtx head)
5234 while (insn != head && NOTE_P (insn)
5235 && NOTE_KIND (insn) == NOTE_INSN_VAR_LOCATION)
5236 insn = PREV_INSN (insn);
5241 /* Check few properties of CFG between HEAD and TAIL.
5242 If HEAD (TAIL) is NULL check from the beginning (till the end) of the
5243 instruction stream. */
5245 check_cfg (rtx head, rtx tail)
5249 int not_first = 0, not_last;
5252 head = get_insns ();
5254 tail = get_last_insn ();
5255 next_tail = NEXT_INSN (tail);
5259 not_last = head != tail;
5262 gcc_assert (NEXT_INSN (PREV_INSN (head)) == head);
5264 gcc_assert (PREV_INSN (NEXT_INSN (head)) == head);
5267 || (NOTE_INSN_BASIC_BLOCK_P (head)
5269 || (not_first && !LABEL_P (PREV_INSN (head))))))
5271 gcc_assert (bb == 0);
5272 bb = BLOCK_FOR_INSN (head);
5274 gcc_assert (BB_HEAD (bb) == head);
5276 /* This is the case of jump table. See inside_basic_block_p (). */
5277 gcc_assert (LABEL_P (head) && !inside_basic_block_p (head));
5282 gcc_assert (!inside_basic_block_p (head));
5283 head = NEXT_INSN (head);
5287 gcc_assert (inside_basic_block_p (head)
5289 gcc_assert (BLOCK_FOR_INSN (head) == bb);
5293 head = NEXT_INSN (head);
5294 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (head));
5298 if (control_flow_insn_p (head))
5300 gcc_assert (prev_non_location_insn (BB_END (bb), head)
5303 if (any_uncondjump_p (head))
5304 gcc_assert (EDGE_COUNT (bb->succs) == 1
5305 && BARRIER_P (NEXT_INSN (head)));
5306 else if (any_condjump_p (head))
5307 gcc_assert (/* Usual case. */
5308 (EDGE_COUNT (bb->succs) > 1
5309 && !BARRIER_P (NEXT_INSN (head)))
5310 /* Or jump to the next instruction. */
5311 || (EDGE_COUNT (bb->succs) == 1
5312 && (BB_HEAD (EDGE_I (bb->succs, 0)->dest)
5313 == JUMP_LABEL (head))));
5315 if (BB_END (bb) == head)
5317 if (EDGE_COUNT (bb->succs) > 1)
5318 gcc_assert (control_flow_insn_p (prev_non_location_insn
5319 (head, BB_HEAD (bb)))
5320 || has_edge_p (bb->succs, EDGE_COMPLEX));
5324 head = NEXT_INSN (head);
5330 while (head != next_tail);
5332 gcc_assert (bb == 0);
5335 #endif /* ENABLE_CHECKING */
5337 /* Extend data structures for logical insn UID. */
5339 sched_extend_luids (void)
5341 int new_luids_max_uid = get_max_uid () + 1;
5343 VEC_safe_grow_cleared (int, heap, sched_luids, new_luids_max_uid);
5346 /* Initialize LUID for INSN. */
5348 sched_init_insn_luid (rtx insn)
5350 int i = INSN_P (insn) ? 1 : common_sched_info->luid_for_non_insn (insn);
5355 luid = sched_max_luid;
5356 sched_max_luid += i;
5361 SET_INSN_LUID (insn, luid);
5364 /* Initialize luids for BBS.
5365 The hook common_sched_info->luid_for_non_insn () is used to determine
5366 if notes, labels, etc. need luids. */
5368 sched_init_luids (bb_vec_t bbs)
5373 sched_extend_luids ();
5374 FOR_EACH_VEC_ELT (basic_block, bbs, i, bb)
5378 FOR_BB_INSNS (bb, insn)
5379 sched_init_insn_luid (insn);
5385 sched_finish_luids (void)
5387 VEC_free (int, heap, sched_luids);
5391 /* Return logical uid of INSN. Helpful while debugging. */
5393 insn_luid (rtx insn)
5395 return INSN_LUID (insn);
5398 /* Extend per insn data in the target. */
5400 sched_extend_target (void)
5402 if (targetm.sched.h_i_d_extended)
5403 targetm.sched.h_i_d_extended ();
5406 /* Extend global scheduler structures (those, that live across calls to
5407 schedule_block) to include information about just emitted INSN. */
5411 int reserve = (get_max_uid () + 1
5412 - VEC_length (haifa_insn_data_def, h_i_d));
5414 && ! VEC_space (haifa_insn_data_def, h_i_d, reserve))
5416 VEC_safe_grow_cleared (haifa_insn_data_def, heap, h_i_d,
5417 3 * get_max_uid () / 2);
5418 sched_extend_target ();
5422 /* Initialize h_i_d entry of the INSN with default values.
5423 Values, that are not explicitly initialized here, hold zero. */
5425 init_h_i_d (rtx insn)
5427 if (INSN_LUID (insn) > 0)
5429 INSN_COST (insn) = -1;
5430 QUEUE_INDEX (insn) = QUEUE_NOWHERE;
5431 INSN_TICK (insn) = INVALID_TICK;
5432 INTER_TICK (insn) = INVALID_TICK;
5433 TODO_SPEC (insn) = HARD_DEP;
5437 /* Initialize haifa_insn_data for BBS. */
5439 haifa_init_h_i_d (bb_vec_t bbs)
5445 FOR_EACH_VEC_ELT (basic_block, bbs, i, bb)
5449 FOR_BB_INSNS (bb, insn)
5454 /* Finalize haifa_insn_data. */
5456 haifa_finish_h_i_d (void)
5459 haifa_insn_data_t data;
5460 struct reg_use_data *use, *next;
5462 FOR_EACH_VEC_ELT (haifa_insn_data_def, h_i_d, i, data)
5464 free (data->reg_pressure);
5465 for (use = data->reg_use_list; use != NULL; use = next)
5467 next = use->next_insn_use;
5471 VEC_free (haifa_insn_data_def, heap, h_i_d);
5474 /* Init data for the new insn INSN. */
5476 haifa_init_insn (rtx insn)
5478 gcc_assert (insn != NULL);
5480 sched_extend_luids ();
5481 sched_init_insn_luid (insn);
5482 sched_extend_target ();
5483 sched_deps_init (false);
5487 if (adding_bb_to_current_region_p)
5489 sd_init_insn (insn);
5491 /* Extend dependency caches by one element. */
5492 extend_dependency_caches (1, false);
5494 if (sched_pressure_p)
5495 init_insn_reg_pressure_info (insn);
5498 /* Init data for the new basic block BB which comes after AFTER. */
5500 haifa_init_only_bb (basic_block bb, basic_block after)
5502 gcc_assert (bb != NULL);
5506 if (common_sched_info->add_block)
5507 /* This changes only data structures of the front-end. */
5508 common_sched_info->add_block (bb, after);
5511 /* A generic version of sched_split_block (). */
5513 sched_split_block_1 (basic_block first_bb, rtx after)
5517 e = split_block (first_bb, after);
5518 gcc_assert (e->src == first_bb);
5520 /* sched_split_block emits note if *check == BB_END. Probably it
5521 is better to rip that note off. */
5526 /* A generic version of sched_create_empty_bb (). */
5528 sched_create_empty_bb_1 (basic_block after)
5530 return create_empty_bb (after);
5533 /* Insert PAT as an INSN into the schedule and update the necessary data
5534 structures to account for it. */
5536 sched_emit_insn (rtx pat)
5538 rtx insn = emit_insn_before (pat, nonscheduled_insns_begin);
5539 haifa_init_insn (insn);
5541 if (current_sched_info->add_remove_insn)
5542 current_sched_info->add_remove_insn (insn, 0);
5544 (*current_sched_info->begin_schedule_ready) (insn);
5545 VEC_safe_push (rtx, heap, scheduled_insns, insn);
5547 last_scheduled_insn = insn;
5551 /* This function returns a candidate satisfying dispatch constraints from
5555 ready_remove_first_dispatch (struct ready_list *ready)
5558 rtx insn = ready_element (ready, 0);
5560 if (ready->n_ready == 1
5561 || INSN_CODE (insn) < 0
5563 || !active_insn_p (insn)
5564 || targetm.sched.dispatch (insn, FITS_DISPATCH_WINDOW))
5565 return ready_remove_first (ready);
5567 for (i = 1; i < ready->n_ready; i++)
5569 insn = ready_element (ready, i);
5571 if (INSN_CODE (insn) < 0
5573 || !active_insn_p (insn))
5576 if (targetm.sched.dispatch (insn, FITS_DISPATCH_WINDOW))
5578 /* Return ith element of ready. */
5579 insn = ready_remove (ready, i);
5584 if (targetm.sched.dispatch (NULL_RTX, DISPATCH_VIOLATION))
5585 return ready_remove_first (ready);
5587 for (i = 1; i < ready->n_ready; i++)
5589 insn = ready_element (ready, i);
5591 if (INSN_CODE (insn) < 0
5593 || !active_insn_p (insn))
5596 /* Return i-th element of ready. */
5597 if (targetm.sched.dispatch (insn, IS_CMP))
5598 return ready_remove (ready, i);
5601 return ready_remove_first (ready);
5604 /* Get number of ready insn in the ready list. */
5607 number_in_ready (void)
5609 return ready.n_ready;
5612 /* Get number of ready's in the ready list. */
5615 get_ready_element (int i)
5617 return ready_element (&ready, i);
5620 #endif /* INSN_SCHEDULING */