1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
3 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
4 Free Software Foundation, Inc.
5 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
6 and currently maintained by, Jim Wilson (wilson@cygnus.com)
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
24 /* Instruction scheduling pass. This file, along with sched-deps.c,
25 contains the generic parts. The actual entry point is found for
26 the normal instruction scheduling pass is found in sched-rgn.c.
28 We compute insn priorities based on data dependencies. Flow
29 analysis only creates a fraction of the data-dependencies we must
30 observe: namely, only those dependencies which the combiner can be
31 expected to use. For this pass, we must therefore create the
32 remaining dependencies we need to observe: register dependencies,
33 memory dependencies, dependencies to keep function calls in order,
34 and the dependence between a conditional branch and the setting of
35 condition codes are all dealt with here.
37 The scheduler first traverses the data flow graph, starting with
38 the last instruction, and proceeding to the first, assigning values
39 to insn_priority as it goes. This sorts the instructions
40 topologically by data dependence.
42 Once priorities have been established, we order the insns using
43 list scheduling. This works as follows: starting with a list of
44 all the ready insns, and sorted according to priority number, we
45 schedule the insn from the end of the list by placing its
46 predecessors in the list according to their priority order. We
47 consider this insn scheduled by setting the pointer to the "end" of
48 the list to point to the previous insn. When an insn has no
49 predecessors, we either queue it until sufficient time has elapsed
50 or add it to the ready list. As the instructions are scheduled or
51 when stalls are introduced, the queue advances and dumps insns into
52 the ready list. When all insns down to the lowest priority have
53 been scheduled, the critical path of the basic block has been made
54 as short as possible. The remaining insns are then scheduled in
57 The following list shows the order in which we want to break ties
58 among insns in the ready list:
60 1. choose insn with the longest path to end of bb, ties
62 2. choose insn with least contribution to register pressure,
64 3. prefer in-block upon interblock motion, ties broken by
65 4. prefer useful upon speculative motion, ties broken by
66 5. choose insn with largest control flow probability, ties
68 6. choose insn with the least dependences upon the previously
69 scheduled insn, or finally
70 7 choose the insn which has the most insns dependent on it.
71 8. choose insn with lowest UID.
73 Memory references complicate matters. Only if we can be certain
74 that memory references are not part of the data dependency graph
75 (via true, anti, or output dependence), can we move operations past
76 memory references. To first approximation, reads can be done
77 independently, while writes introduce dependencies. Better
78 approximations will yield fewer dependencies.
80 Before reload, an extended analysis of interblock data dependences
81 is required for interblock scheduling. This is performed in
82 compute_block_backward_dependences ().
84 Dependencies set up by memory references are treated in exactly the
85 same way as other dependencies, by using insn backward dependences
86 INSN_BACK_DEPS. INSN_BACK_DEPS are translated into forward dependences
87 INSN_FORW_DEPS the purpose of forward list scheduling.
89 Having optimized the critical path, we may have also unduly
90 extended the lifetimes of some registers. If an operation requires
91 that constants be loaded into registers, it is certainly desirable
92 to load those constants as early as necessary, but no earlier.
93 I.e., it will not do to load up a bunch of registers at the
94 beginning of a basic block only to use them at the end, if they
95 could be loaded later, since this may result in excessive register
98 Note that since branches are never in basic blocks, but only end
99 basic blocks, this pass will not move branches. But that is ok,
100 since we can use GNU's delayed branch scheduling pass to take care
103 Also note that no further optimizations based on algebraic
104 identities are performed, so this pass would be a good one to
105 perform instruction splitting, such as breaking up a multiply
106 instruction into shifts and adds where that is profitable.
108 Given the memory aliasing analysis that this pass should perform,
109 it should be possible to remove redundant stores to memory, and to
110 load values from registers instead of hitting memory.
112 Before reload, speculative insns are moved only if a 'proof' exists
113 that no exception will be caused by this, and if no live registers
114 exist that inhibit the motion (live registers constraints are not
115 represented by data dependence edges).
117 This pass must update information that subsequent passes expect to
118 be correct. Namely: reg_n_refs, reg_n_sets, reg_n_deaths,
119 reg_n_calls_crossed, and reg_live_length. Also, BB_HEAD, BB_END.
121 The information in the line number notes is carefully retained by
122 this pass. Notes that refer to the starting and ending of
123 exception regions are also carefully retained by this pass. All
124 other NOTE insns are grouped in their same relative order at the
125 beginning of basic blocks and regions that have been scheduled. */
129 #include "coretypes.h"
131 #include "diagnostic-core.h"
134 #include "hard-reg-set.h"
136 #include "function.h"
138 #include "insn-config.h"
139 #include "insn-attr.h"
142 #include "sched-int.h"
150 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
152 #ifdef INSN_SCHEDULING
154 /* issue_rate is the number of insns that can be scheduled in the same
155 machine cycle. It can be defined in the config/mach/mach.h file,
156 otherwise we set it to 1. */
160 /* sched-verbose controls the amount of debugging output the
161 scheduler prints. It is controlled by -fsched-verbose=N:
162 N>0 and no -DSR : the output is directed to stderr.
163 N>=10 will direct the printouts to stderr (regardless of -dSR).
165 N=2: bb's probabilities, detailed ready list info, unit/insn info.
166 N=3: rtl at abort point, control-flow, regions info.
167 N=5: dependences info. */
169 int sched_verbose
= 0;
171 /* Debugging file. All printouts are sent to dump, which is always set,
172 either to stderr, or to the dump listing file (-dRS). */
173 FILE *sched_dump
= 0;
175 /* This is a placeholder for the scheduler parameters common
176 to all schedulers. */
177 struct common_sched_info_def
*common_sched_info
;
179 #define INSN_TICK(INSN) (HID (INSN)->tick)
180 #define INTER_TICK(INSN) (HID (INSN)->inter_tick)
182 /* If INSN_TICK of an instruction is equal to INVALID_TICK,
183 then it should be recalculated from scratch. */
184 #define INVALID_TICK (-(max_insn_queue_index + 1))
185 /* The minimal value of the INSN_TICK of an instruction. */
186 #define MIN_TICK (-max_insn_queue_index)
188 /* List of important notes we must keep around. This is a pointer to the
189 last element in the list. */
192 static struct spec_info_def spec_info_var
;
193 /* Description of the speculative part of the scheduling.
194 If NULL - no speculation. */
195 spec_info_t spec_info
= NULL
;
197 /* True, if recovery block was added during scheduling of current block.
198 Used to determine, if we need to fix INSN_TICKs. */
199 static bool haifa_recovery_bb_recently_added_p
;
201 /* True, if recovery block was added during this scheduling pass.
202 Used to determine if we should have empty memory pools of dependencies
203 after finishing current region. */
204 bool haifa_recovery_bb_ever_added_p
;
206 /* Counters of different types of speculative instructions. */
207 static int nr_begin_data
, nr_be_in_data
, nr_begin_control
, nr_be_in_control
;
209 /* Array used in {unlink, restore}_bb_notes. */
210 static rtx
*bb_header
= 0;
212 /* Basic block after which recovery blocks will be created. */
213 static basic_block before_recovery
;
215 /* Basic block just before the EXIT_BLOCK and after recovery, if we have
217 basic_block after_recovery
;
219 /* FALSE if we add bb to another region, so we don't need to initialize it. */
220 bool adding_bb_to_current_region_p
= true;
224 /* An instruction is ready to be scheduled when all insns preceding it
225 have already been scheduled. It is important to ensure that all
226 insns which use its result will not be executed until its result
227 has been computed. An insn is maintained in one of four structures:
229 (P) the "Pending" set of insns which cannot be scheduled until
230 their dependencies have been satisfied.
231 (Q) the "Queued" set of insns that can be scheduled when sufficient
233 (R) the "Ready" list of unscheduled, uncommitted insns.
234 (S) the "Scheduled" list of insns.
236 Initially, all insns are either "Pending" or "Ready" depending on
237 whether their dependencies are satisfied.
239 Insns move from the "Ready" list to the "Scheduled" list as they
240 are committed to the schedule. As this occurs, the insns in the
241 "Pending" list have their dependencies satisfied and move to either
242 the "Ready" list or the "Queued" set depending on whether
243 sufficient time has passed to make them ready. As time passes,
244 insns move from the "Queued" set to the "Ready" list.
246 The "Pending" list (P) are the insns in the INSN_FORW_DEPS of the
247 unscheduled insns, i.e., those that are ready, queued, and pending.
248 The "Queued" set (Q) is implemented by the variable `insn_queue'.
249 The "Ready" list (R) is implemented by the variables `ready' and
251 The "Scheduled" list (S) is the new insn chain built by this pass.
253 The transition (R->S) is implemented in the scheduling loop in
254 `schedule_block' when the best insn to schedule is chosen.
255 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
256 insns move from the ready list to the scheduled list.
257 The transition (Q->R) is implemented in 'queue_to_insn' as time
258 passes or stalls are introduced. */
260 /* Implement a circular buffer to delay instructions until sufficient
261 time has passed. For the new pipeline description interface,
262 MAX_INSN_QUEUE_INDEX is a power of two minus one which is not less
263 than maximal time of instruction execution computed by genattr.c on
264 the base maximal time of functional unit reservations and getting a
265 result. This is the longest time an insn may be queued. */
267 static rtx
*insn_queue
;
268 static int q_ptr
= 0;
269 static int q_size
= 0;
270 #define NEXT_Q(X) (((X)+1) & max_insn_queue_index)
271 #define NEXT_Q_AFTER(X, C) (((X)+C) & max_insn_queue_index)
273 #define QUEUE_SCHEDULED (-3)
274 #define QUEUE_NOWHERE (-2)
275 #define QUEUE_READY (-1)
276 /* QUEUE_SCHEDULED - INSN is scheduled.
277 QUEUE_NOWHERE - INSN isn't scheduled yet and is neither in
279 QUEUE_READY - INSN is in ready list.
280 N >= 0 - INSN queued for X [where NEXT_Q_AFTER (q_ptr, X) == N] cycles. */
282 #define QUEUE_INDEX(INSN) (HID (INSN)->queue_index)
284 /* The following variable value refers for all current and future
285 reservations of the processor units. */
288 /* The following variable value is size of memory representing all
289 current and future reservations of the processor units. */
290 size_t dfa_state_size
;
292 /* The following array is used to find the best insn from ready when
293 the automaton pipeline interface is used. */
294 char *ready_try
= NULL
;
296 /* The ready list. */
297 struct ready_list ready
= {NULL
, 0, 0, 0, 0};
299 /* The pointer to the ready list (to be removed). */
300 static struct ready_list
*readyp
= &ready
;
302 /* Scheduling clock. */
303 static int clock_var
;
305 /* This records the actual schedule. It is built up during the main phase
306 of schedule_block, and afterwards used to reorder the insns in the RTL. */
307 static VEC(rtx
, heap
) *scheduled_insns
;
309 static int may_trap_exp (const_rtx
, int);
311 /* Nonzero iff the address is comprised from at most 1 register. */
312 #define CONST_BASED_ADDRESS_P(x) \
314 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
315 || (GET_CODE (x) == LO_SUM)) \
316 && (CONSTANT_P (XEXP (x, 0)) \
317 || CONSTANT_P (XEXP (x, 1)))))
319 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
320 as found by analyzing insn's expression. */
323 static int haifa_luid_for_non_insn (rtx x
);
325 /* Haifa version of sched_info hooks common to all headers. */
326 const struct common_sched_info_def haifa_common_sched_info
=
328 NULL
, /* fix_recovery_cfg */
329 NULL
, /* add_block */
330 NULL
, /* estimate_number_of_insns */
331 haifa_luid_for_non_insn
, /* luid_for_non_insn */
332 SCHED_PASS_UNKNOWN
/* sched_pass_id */
335 const struct sched_scan_info_def
*sched_scan_info
;
337 /* Mapping from instruction UID to its Logical UID. */
338 VEC (int, heap
) *sched_luids
= NULL
;
340 /* Next LUID to assign to an instruction. */
341 int sched_max_luid
= 1;
343 /* Haifa Instruction Data. */
344 VEC (haifa_insn_data_def
, heap
) *h_i_d
= NULL
;
346 void (* sched_init_only_bb
) (basic_block
, basic_block
);
348 /* Split block function. Different schedulers might use different functions
349 to handle their internal data consistent. */
350 basic_block (* sched_split_block
) (basic_block
, rtx
);
352 /* Create empty basic block after the specified block. */
353 basic_block (* sched_create_empty_bb
) (basic_block
);
356 may_trap_exp (const_rtx x
, int is_store
)
365 if (code
== MEM
&& may_trap_p (x
))
372 /* The insn uses memory: a volatile load. */
373 if (MEM_VOLATILE_P (x
))
375 /* An exception-free load. */
378 /* A load with 1 base register, to be further checked. */
379 if (CONST_BASED_ADDRESS_P (XEXP (x
, 0)))
380 return PFREE_CANDIDATE
;
381 /* No info on the load, to be further checked. */
382 return PRISKY_CANDIDATE
;
387 int i
, insn_class
= TRAP_FREE
;
389 /* Neither store nor load, check if it may cause a trap. */
392 /* Recursive step: walk the insn... */
393 fmt
= GET_RTX_FORMAT (code
);
394 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
398 int tmp_class
= may_trap_exp (XEXP (x
, i
), is_store
);
399 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
401 else if (fmt
[i
] == 'E')
404 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
406 int tmp_class
= may_trap_exp (XVECEXP (x
, i
, j
), is_store
);
407 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
408 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
412 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
419 /* Classifies rtx X of an insn for the purpose of verifying that X can be
420 executed speculatively (and consequently the insn can be moved
421 speculatively), by examining X, returning:
422 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
423 TRAP_FREE: non-load insn.
424 IFREE: load from a globally safe location.
425 IRISKY: volatile load.
426 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
427 being either PFREE or PRISKY. */
430 haifa_classify_rtx (const_rtx x
)
432 int tmp_class
= TRAP_FREE
;
433 int insn_class
= TRAP_FREE
;
436 if (GET_CODE (x
) == PARALLEL
)
438 int i
, len
= XVECLEN (x
, 0);
440 for (i
= len
- 1; i
>= 0; i
--)
442 tmp_class
= haifa_classify_rtx (XVECEXP (x
, 0, i
));
443 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
444 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
454 /* Test if it is a 'store'. */
455 tmp_class
= may_trap_exp (XEXP (x
, 0), 1);
458 /* Test if it is a store. */
459 tmp_class
= may_trap_exp (SET_DEST (x
), 1);
460 if (tmp_class
== TRAP_RISKY
)
462 /* Test if it is a load. */
464 WORST_CLASS (tmp_class
,
465 may_trap_exp (SET_SRC (x
), 0));
468 tmp_class
= haifa_classify_rtx (COND_EXEC_CODE (x
));
469 if (tmp_class
== TRAP_RISKY
)
471 tmp_class
= WORST_CLASS (tmp_class
,
472 may_trap_exp (COND_EXEC_TEST (x
), 0));
475 tmp_class
= TRAP_RISKY
;
479 insn_class
= tmp_class
;
486 haifa_classify_insn (const_rtx insn
)
488 return haifa_classify_rtx (PATTERN (insn
));
491 /* Forward declarations. */
493 static int priority (rtx
);
494 static int rank_for_schedule (const void *, const void *);
495 static void swap_sort (rtx
*, int);
496 static void queue_insn (rtx
, int, const char *);
497 static int schedule_insn (rtx
);
498 static void adjust_priority (rtx
);
499 static void advance_one_cycle (void);
500 static void extend_h_i_d (void);
503 /* Notes handling mechanism:
504 =========================
505 Generally, NOTES are saved before scheduling and restored after scheduling.
506 The scheduler distinguishes between two types of notes:
508 (1) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
509 Before scheduling a region, a pointer to the note is added to the insn
510 that follows or precedes it. (This happens as part of the data dependence
511 computation). After scheduling an insn, the pointer contained in it is
512 used for regenerating the corresponding note (in reemit_notes).
514 (2) All other notes (e.g. INSN_DELETED): Before scheduling a block,
515 these notes are put in a list (in rm_other_notes() and
516 unlink_other_notes ()). After scheduling the block, these notes are
517 inserted at the beginning of the block (in schedule_block()). */
519 static void ready_add (struct ready_list
*, rtx
, bool);
520 static rtx
ready_remove_first (struct ready_list
*);
521 static rtx
ready_remove_first_dispatch (struct ready_list
*ready
);
523 static void queue_to_ready (struct ready_list
*);
524 static int early_queue_to_ready (state_t
, struct ready_list
*);
526 static void debug_ready_list (struct ready_list
*);
528 /* The following functions are used to implement multi-pass scheduling
529 on the first cycle. */
530 static rtx
ready_remove (struct ready_list
*, int);
531 static void ready_remove_insn (rtx
);
533 static void fix_inter_tick (rtx
, rtx
);
534 static int fix_tick_ready (rtx
);
535 static void change_queue_index (rtx
, int);
537 /* The following functions are used to implement scheduling of data/control
538 speculative instructions. */
540 static void extend_h_i_d (void);
541 static void init_h_i_d (rtx
);
542 static void generate_recovery_code (rtx
);
543 static void process_insn_forw_deps_be_in_spec (rtx
, rtx
, ds_t
);
544 static void begin_speculative_block (rtx
);
545 static void add_to_speculative_block (rtx
);
546 static void init_before_recovery (basic_block
*);
547 static void create_check_block_twin (rtx
, bool);
548 static void fix_recovery_deps (basic_block
);
549 static void haifa_change_pattern (rtx
, rtx
);
550 static void dump_new_block_header (int, basic_block
, rtx
, rtx
);
551 static void restore_bb_notes (basic_block
);
552 static void fix_jump_move (rtx
);
553 static void move_block_after_check (rtx
);
554 static void move_succs (VEC(edge
,gc
) **, basic_block
);
555 static void sched_remove_insn (rtx
);
556 static void clear_priorities (rtx
, rtx_vec_t
*);
557 static void calc_priorities (rtx_vec_t
);
558 static void add_jump_dependencies (rtx
, rtx
);
559 #ifdef ENABLE_CHECKING
560 static int has_edge_p (VEC(edge
,gc
) *, int);
561 static void check_cfg (rtx
, rtx
);
564 #endif /* INSN_SCHEDULING */
566 /* Point to state used for the current scheduling pass. */
567 struct haifa_sched_info
*current_sched_info
;
569 #ifndef INSN_SCHEDULING
571 schedule_insns (void)
576 /* Do register pressure sensitive insn scheduling if the flag is set
578 bool sched_pressure_p
;
580 /* Map regno -> its pressure class. The map defined only when
581 SCHED_PRESSURE_P is true. */
582 enum reg_class
*sched_regno_pressure_class
;
584 /* The current register pressure. Only elements corresponding pressure
585 classes are defined. */
586 static int curr_reg_pressure
[N_REG_CLASSES
];
588 /* Saved value of the previous array. */
589 static int saved_reg_pressure
[N_REG_CLASSES
];
591 /* Register living at given scheduling point. */
592 static bitmap curr_reg_live
;
594 /* Saved value of the previous array. */
595 static bitmap saved_reg_live
;
597 /* Registers mentioned in the current region. */
598 static bitmap region_ref_regs
;
600 /* Initiate register pressure relative info for scheduling the current
601 region. Currently it is only clearing register mentioned in the
604 sched_init_region_reg_pressure_info (void)
606 bitmap_clear (region_ref_regs
);
609 /* Update current register pressure related info after birth (if
610 BIRTH_P) or death of register REGNO. */
612 mark_regno_birth_or_death (int regno
, bool birth_p
)
614 enum reg_class pressure_class
;
616 pressure_class
= sched_regno_pressure_class
[regno
];
617 if (regno
>= FIRST_PSEUDO_REGISTER
)
619 if (pressure_class
!= NO_REGS
)
623 bitmap_set_bit (curr_reg_live
, regno
);
624 curr_reg_pressure
[pressure_class
]
625 += (ira_reg_class_max_nregs
626 [pressure_class
][PSEUDO_REGNO_MODE (regno
)]);
630 bitmap_clear_bit (curr_reg_live
, regno
);
631 curr_reg_pressure
[pressure_class
]
632 -= (ira_reg_class_max_nregs
633 [pressure_class
][PSEUDO_REGNO_MODE (regno
)]);
637 else if (pressure_class
!= NO_REGS
638 && ! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
642 bitmap_set_bit (curr_reg_live
, regno
);
643 curr_reg_pressure
[pressure_class
]++;
647 bitmap_clear_bit (curr_reg_live
, regno
);
648 curr_reg_pressure
[pressure_class
]--;
653 /* Initiate current register pressure related info from living
654 registers given by LIVE. */
656 initiate_reg_pressure_info (bitmap live
)
662 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
663 curr_reg_pressure
[ira_pressure_classes
[i
]] = 0;
664 bitmap_clear (curr_reg_live
);
665 EXECUTE_IF_SET_IN_BITMAP (live
, 0, j
, bi
)
666 if (current_nr_blocks
== 1 || bitmap_bit_p (region_ref_regs
, j
))
667 mark_regno_birth_or_death (j
, true);
670 /* Mark registers in X as mentioned in the current region. */
672 setup_ref_regs (rtx x
)
675 const RTX_CODE code
= GET_CODE (x
);
681 if (HARD_REGISTER_NUM_P (regno
))
682 bitmap_set_range (region_ref_regs
, regno
,
683 hard_regno_nregs
[regno
][GET_MODE (x
)]);
685 bitmap_set_bit (region_ref_regs
, REGNO (x
));
688 fmt
= GET_RTX_FORMAT (code
);
689 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
691 setup_ref_regs (XEXP (x
, i
));
692 else if (fmt
[i
] == 'E')
694 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
695 setup_ref_regs (XVECEXP (x
, i
, j
));
699 /* Initiate current register pressure related info at the start of
702 initiate_bb_reg_pressure_info (basic_block bb
)
704 unsigned int i ATTRIBUTE_UNUSED
;
707 if (current_nr_blocks
> 1)
708 FOR_BB_INSNS (bb
, insn
)
709 if (NONDEBUG_INSN_P (insn
))
710 setup_ref_regs (PATTERN (insn
));
711 initiate_reg_pressure_info (df_get_live_in (bb
));
712 #ifdef EH_RETURN_DATA_REGNO
713 if (bb_has_eh_pred (bb
))
716 unsigned int regno
= EH_RETURN_DATA_REGNO (i
);
718 if (regno
== INVALID_REGNUM
)
720 if (! bitmap_bit_p (df_get_live_in (bb
), regno
))
721 mark_regno_birth_or_death (regno
, true);
726 /* Save current register pressure related info. */
728 save_reg_pressure (void)
732 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
733 saved_reg_pressure
[ira_pressure_classes
[i
]]
734 = curr_reg_pressure
[ira_pressure_classes
[i
]];
735 bitmap_copy (saved_reg_live
, curr_reg_live
);
738 /* Restore saved register pressure related info. */
740 restore_reg_pressure (void)
744 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
745 curr_reg_pressure
[ira_pressure_classes
[i
]]
746 = saved_reg_pressure
[ira_pressure_classes
[i
]];
747 bitmap_copy (curr_reg_live
, saved_reg_live
);
750 /* Return TRUE if the register is dying after its USE. */
752 dying_use_p (struct reg_use_data
*use
)
754 struct reg_use_data
*next
;
756 for (next
= use
->next_regno_use
; next
!= use
; next
= next
->next_regno_use
)
757 if (NONDEBUG_INSN_P (next
->insn
)
758 && QUEUE_INDEX (next
->insn
) != QUEUE_SCHEDULED
)
763 /* Print info about the current register pressure and its excess for
764 each pressure class. */
766 print_curr_reg_pressure (void)
771 fprintf (sched_dump
, ";;\t");
772 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
774 cl
= ira_pressure_classes
[i
];
775 gcc_assert (curr_reg_pressure
[cl
] >= 0);
776 fprintf (sched_dump
, " %s:%d(%d)", reg_class_names
[cl
],
777 curr_reg_pressure
[cl
],
778 curr_reg_pressure
[cl
] - ira_available_class_regs
[cl
]);
780 fprintf (sched_dump
, "\n");
783 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
784 so that insns independent of the last scheduled insn will be preferred
785 over dependent instructions. */
787 static rtx last_scheduled_insn
;
789 /* Cached cost of the instruction. Use below function to get cost of the
790 insn. -1 here means that the field is not initialized. */
791 #define INSN_COST(INSN) (HID (INSN)->cost)
793 /* Compute cost of executing INSN.
794 This is the number of cycles between instruction issue and
795 instruction results. */
803 if (recog_memoized (insn
) < 0)
806 cost
= insn_default_latency (insn
);
813 cost
= INSN_COST (insn
);
817 /* A USE insn, or something else we don't need to
818 understand. We can't pass these directly to
819 result_ready_cost or insn_default_latency because it will
820 trigger a fatal error for unrecognizable insns. */
821 if (recog_memoized (insn
) < 0)
823 INSN_COST (insn
) = 0;
828 cost
= insn_default_latency (insn
);
832 INSN_COST (insn
) = cost
;
839 /* Compute cost of dependence LINK.
840 This is the number of cycles between instruction issue and
842 ??? We also use this function to call recog_memoized on all insns. */
844 dep_cost_1 (dep_t link
, dw_t dw
)
846 rtx insn
= DEP_PRO (link
);
847 rtx used
= DEP_CON (link
);
850 /* A USE insn should never require the value used to be computed.
851 This allows the computation of a function's result and parameter
852 values to overlap the return and call. We don't care about the
853 the dependence cost when only decreasing register pressure. */
854 if (recog_memoized (used
) < 0)
857 recog_memoized (insn
);
861 enum reg_note dep_type
= DEP_TYPE (link
);
863 cost
= insn_cost (insn
);
865 if (INSN_CODE (insn
) >= 0)
867 if (dep_type
== REG_DEP_ANTI
)
869 else if (dep_type
== REG_DEP_OUTPUT
)
871 cost
= (insn_default_latency (insn
)
872 - insn_default_latency (used
));
876 else if (bypass_p (insn
))
877 cost
= insn_latency (insn
, used
);
881 if (targetm
.sched
.adjust_cost_2
)
882 cost
= targetm
.sched
.adjust_cost_2 (used
, (int) dep_type
, insn
, cost
,
884 else if (targetm
.sched
.adjust_cost
!= NULL
)
886 /* This variable is used for backward compatibility with the
888 rtx dep_cost_rtx_link
= alloc_INSN_LIST (NULL_RTX
, NULL_RTX
);
890 /* Make it self-cycled, so that if some tries to walk over this
891 incomplete list he/she will be caught in an endless loop. */
892 XEXP (dep_cost_rtx_link
, 1) = dep_cost_rtx_link
;
894 /* Targets use only REG_NOTE_KIND of the link. */
895 PUT_REG_NOTE_KIND (dep_cost_rtx_link
, DEP_TYPE (link
));
897 cost
= targetm
.sched
.adjust_cost (used
, dep_cost_rtx_link
,
900 free_INSN_LIST_node (dep_cost_rtx_link
);
910 /* Compute cost of dependence LINK.
911 This is the number of cycles between instruction issue and
912 instruction results. */
914 dep_cost (dep_t link
)
916 return dep_cost_1 (link
, 0);
919 /* Use this sel-sched.c friendly function in reorder2 instead of increasing
920 INSN_PRIORITY explicitly. */
922 increase_insn_priority (rtx insn
, int amount
)
926 /* We're dealing with haifa-sched.c INSN_PRIORITY. */
927 if (INSN_PRIORITY_KNOWN (insn
))
928 INSN_PRIORITY (insn
) += amount
;
932 /* In sel-sched.c INSN_PRIORITY is not kept up to date.
933 Use EXPR_PRIORITY instead. */
934 sel_add_to_insn_priority (insn
, amount
);
938 /* Return 'true' if DEP should be included in priority calculations. */
940 contributes_to_priority_p (dep_t dep
)
942 if (DEBUG_INSN_P (DEP_CON (dep
))
943 || DEBUG_INSN_P (DEP_PRO (dep
)))
946 /* Critical path is meaningful in block boundaries only. */
947 if (!current_sched_info
->contributes_to_priority (DEP_CON (dep
),
951 /* If flag COUNT_SPEC_IN_CRITICAL_PATH is set,
952 then speculative instructions will less likely be
953 scheduled. That is because the priority of
954 their producers will increase, and, thus, the
955 producers will more likely be scheduled, thus,
956 resolving the dependence. */
957 if (sched_deps_info
->generate_spec_deps
958 && !(spec_info
->flags
& COUNT_SPEC_IN_CRITICAL_PATH
)
959 && (DEP_STATUS (dep
) & SPECULATIVE
))
965 /* Compute the number of nondebug forward deps of an insn. */
968 dep_list_size (rtx insn
)
970 sd_iterator_def sd_it
;
972 int dbgcount
= 0, nodbgcount
= 0;
974 if (!MAY_HAVE_DEBUG_INSNS
)
975 return sd_lists_size (insn
, SD_LIST_FORW
);
977 FOR_EACH_DEP (insn
, SD_LIST_FORW
, sd_it
, dep
)
979 if (DEBUG_INSN_P (DEP_CON (dep
)))
981 else if (!DEBUG_INSN_P (DEP_PRO (dep
)))
985 gcc_assert (dbgcount
+ nodbgcount
== sd_lists_size (insn
, SD_LIST_FORW
));
990 /* Compute the priority number for INSN. */
997 /* We should not be interested in priority of an already scheduled insn. */
998 gcc_assert (QUEUE_INDEX (insn
) != QUEUE_SCHEDULED
);
1000 if (!INSN_PRIORITY_KNOWN (insn
))
1002 int this_priority
= -1;
1004 if (dep_list_size (insn
) == 0)
1005 /* ??? We should set INSN_PRIORITY to insn_cost when and insn has
1006 some forward deps but all of them are ignored by
1007 contributes_to_priority hook. At the moment we set priority of
1009 this_priority
= insn_cost (insn
);
1012 rtx prev_first
, twin
;
1015 /* For recovery check instructions we calculate priority slightly
1016 different than that of normal instructions. Instead of walking
1017 through INSN_FORW_DEPS (check) list, we walk through
1018 INSN_FORW_DEPS list of each instruction in the corresponding
1021 /* Selective scheduling does not define RECOVERY_BLOCK macro. */
1022 rec
= sel_sched_p () ? NULL
: RECOVERY_BLOCK (insn
);
1023 if (!rec
|| rec
== EXIT_BLOCK_PTR
)
1025 prev_first
= PREV_INSN (insn
);
1030 prev_first
= NEXT_INSN (BB_HEAD (rec
));
1031 twin
= PREV_INSN (BB_END (rec
));
1036 sd_iterator_def sd_it
;
1039 FOR_EACH_DEP (twin
, SD_LIST_FORW
, sd_it
, dep
)
1044 next
= DEP_CON (dep
);
1046 if (BLOCK_FOR_INSN (next
) != rec
)
1050 if (!contributes_to_priority_p (dep
))
1054 cost
= dep_cost (dep
);
1057 struct _dep _dep1
, *dep1
= &_dep1
;
1059 init_dep (dep1
, insn
, next
, REG_DEP_ANTI
);
1061 cost
= dep_cost (dep1
);
1064 next_priority
= cost
+ priority (next
);
1066 if (next_priority
> this_priority
)
1067 this_priority
= next_priority
;
1071 twin
= PREV_INSN (twin
);
1073 while (twin
!= prev_first
);
1076 if (this_priority
< 0)
1078 gcc_assert (this_priority
== -1);
1080 this_priority
= insn_cost (insn
);
1083 INSN_PRIORITY (insn
) = this_priority
;
1084 INSN_PRIORITY_STATUS (insn
) = 1;
1087 return INSN_PRIORITY (insn
);
1090 /* Macros and functions for keeping the priority queue sorted, and
1091 dealing with queuing and dequeuing of instructions. */
1093 #define SCHED_SORT(READY, N_READY) \
1094 do { if ((N_READY) == 2) \
1095 swap_sort (READY, N_READY); \
1096 else if ((N_READY) > 2) \
1097 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
1100 /* Setup info about the current register pressure impact of scheduling
1101 INSN at the current scheduling point. */
1103 setup_insn_reg_pressure_info (rtx insn
)
1105 int i
, change
, before
, after
, hard_regno
;
1106 int excess_cost_change
;
1107 enum machine_mode mode
;
1109 struct reg_pressure_data
*pressure_info
;
1110 int *max_reg_pressure
;
1111 struct reg_use_data
*use
;
1112 static int death
[N_REG_CLASSES
];
1114 gcc_checking_assert (!DEBUG_INSN_P (insn
));
1116 excess_cost_change
= 0;
1117 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1118 death
[ira_pressure_classes
[i
]] = 0;
1119 for (use
= INSN_REG_USE_LIST (insn
); use
!= NULL
; use
= use
->next_insn_use
)
1120 if (dying_use_p (use
))
1122 cl
= sched_regno_pressure_class
[use
->regno
];
1123 if (use
->regno
< FIRST_PSEUDO_REGISTER
)
1127 += ira_reg_class_max_nregs
[cl
][PSEUDO_REGNO_MODE (use
->regno
)];
1129 pressure_info
= INSN_REG_PRESSURE (insn
);
1130 max_reg_pressure
= INSN_MAX_REG_PRESSURE (insn
);
1131 gcc_assert (pressure_info
!= NULL
&& max_reg_pressure
!= NULL
);
1132 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1134 cl
= ira_pressure_classes
[i
];
1135 gcc_assert (curr_reg_pressure
[cl
] >= 0);
1136 change
= (int) pressure_info
[i
].set_increase
- death
[cl
];
1137 before
= MAX (0, max_reg_pressure
[i
] - ira_available_class_regs
[cl
]);
1138 after
= MAX (0, max_reg_pressure
[i
] + change
1139 - ira_available_class_regs
[cl
]);
1140 hard_regno
= ira_class_hard_regs
[cl
][0];
1141 gcc_assert (hard_regno
>= 0);
1142 mode
= reg_raw_mode
[hard_regno
];
1143 excess_cost_change
+= ((after
- before
)
1144 * (ira_memory_move_cost
[mode
][cl
][0]
1145 + ira_memory_move_cost
[mode
][cl
][1]));
1147 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insn
) = excess_cost_change
;
1150 /* Returns a positive value if x is preferred; returns a negative value if
1151 y is preferred. Should never return 0, since that will make the sort
1155 rank_for_schedule (const void *x
, const void *y
)
1157 rtx tmp
= *(const rtx
*) y
;
1158 rtx tmp2
= *(const rtx
*) x
;
1160 int tmp_class
, tmp2_class
;
1161 int val
, priority_val
, info_val
;
1163 if (MAY_HAVE_DEBUG_INSNS
)
1165 /* Schedule debug insns as early as possible. */
1166 if (DEBUG_INSN_P (tmp
) && !DEBUG_INSN_P (tmp2
))
1168 else if (DEBUG_INSN_P (tmp2
))
1172 /* The insn in a schedule group should be issued the first. */
1173 if (flag_sched_group_heuristic
&&
1174 SCHED_GROUP_P (tmp
) != SCHED_GROUP_P (tmp2
))
1175 return SCHED_GROUP_P (tmp2
) ? 1 : -1;
1177 /* Make sure that priority of TMP and TMP2 are initialized. */
1178 gcc_assert (INSN_PRIORITY_KNOWN (tmp
) && INSN_PRIORITY_KNOWN (tmp2
));
1180 if (sched_pressure_p
)
1184 /* Prefer insn whose scheduling results in the smallest register
1186 if ((diff
= (INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp
)
1187 + (INSN_TICK (tmp
) > clock_var
1188 ? INSN_TICK (tmp
) - clock_var
: 0)
1189 - INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp2
)
1190 - (INSN_TICK (tmp2
) > clock_var
1191 ? INSN_TICK (tmp2
) - clock_var
: 0))) != 0)
1196 if (sched_pressure_p
1197 && (INSN_TICK (tmp2
) > clock_var
|| INSN_TICK (tmp
) > clock_var
))
1199 if (INSN_TICK (tmp
) <= clock_var
)
1201 else if (INSN_TICK (tmp2
) <= clock_var
)
1204 return INSN_TICK (tmp
) - INSN_TICK (tmp2
);
1206 /* Prefer insn with higher priority. */
1207 priority_val
= INSN_PRIORITY (tmp2
) - INSN_PRIORITY (tmp
);
1209 if (flag_sched_critical_path_heuristic
&& priority_val
)
1210 return priority_val
;
1212 /* Prefer speculative insn with greater dependencies weakness. */
1213 if (flag_sched_spec_insn_heuristic
&& spec_info
)
1219 ds1
= TODO_SPEC (tmp
) & SPECULATIVE
;
1221 dw1
= ds_weak (ds1
);
1225 ds2
= TODO_SPEC (tmp2
) & SPECULATIVE
;
1227 dw2
= ds_weak (ds2
);
1232 if (dw
> (NO_DEP_WEAK
/ 8) || dw
< -(NO_DEP_WEAK
/ 8))
1236 info_val
= (*current_sched_info
->rank
) (tmp
, tmp2
);
1237 if(flag_sched_rank_heuristic
&& info_val
)
1240 if (flag_sched_last_insn_heuristic
)
1242 last
= last_scheduled_insn
;
1244 if (DEBUG_INSN_P (last
) && last
!= current_sched_info
->prev_head
)
1246 last
= PREV_INSN (last
);
1247 while (!NONDEBUG_INSN_P (last
)
1248 && last
!= current_sched_info
->prev_head
);
1251 /* Compare insns based on their relation to the last scheduled
1253 if (flag_sched_last_insn_heuristic
&& NONDEBUG_INSN_P (last
))
1258 /* Classify the instructions into three classes:
1259 1) Data dependent on last schedule insn.
1260 2) Anti/Output dependent on last scheduled insn.
1261 3) Independent of last scheduled insn, or has latency of one.
1262 Choose the insn from the highest numbered class if different. */
1263 dep1
= sd_find_dep_between (last
, tmp
, true);
1265 if (dep1
== NULL
|| dep_cost (dep1
) == 1)
1267 else if (/* Data dependence. */
1268 DEP_TYPE (dep1
) == REG_DEP_TRUE
)
1273 dep2
= sd_find_dep_between (last
, tmp2
, true);
1275 if (dep2
== NULL
|| dep_cost (dep2
) == 1)
1277 else if (/* Data dependence. */
1278 DEP_TYPE (dep2
) == REG_DEP_TRUE
)
1283 if ((val
= tmp2_class
- tmp_class
))
1287 /* Prefer the insn which has more later insns that depend on it.
1288 This gives the scheduler more freedom when scheduling later
1289 instructions at the expense of added register pressure. */
1291 val
= (dep_list_size (tmp2
) - dep_list_size (tmp
));
1293 if (flag_sched_dep_count_heuristic
&& val
!= 0)
1296 /* If insns are equally good, sort by INSN_LUID (original insn order),
1297 so that we make the sort stable. This minimizes instruction movement,
1298 thus minimizing sched's effect on debugging and cross-jumping. */
1299 return INSN_LUID (tmp
) - INSN_LUID (tmp2
);
1302 /* Resort the array A in which only element at index N may be out of order. */
1304 HAIFA_INLINE
static void
1305 swap_sort (rtx
*a
, int n
)
1307 rtx insn
= a
[n
- 1];
1310 while (i
>= 0 && rank_for_schedule (a
+ i
, &insn
) >= 0)
1318 /* Add INSN to the insn queue so that it can be executed at least
1319 N_CYCLES after the currently executing insn. Preserve insns
1320 chain for debugging purposes. REASON will be printed in debugging
1323 HAIFA_INLINE
static void
1324 queue_insn (rtx insn
, int n_cycles
, const char *reason
)
1326 int next_q
= NEXT_Q_AFTER (q_ptr
, n_cycles
);
1327 rtx link
= alloc_INSN_LIST (insn
, insn_queue
[next_q
]);
1329 gcc_assert (n_cycles
<= max_insn_queue_index
);
1330 gcc_assert (!DEBUG_INSN_P (insn
));
1332 insn_queue
[next_q
] = link
;
1335 if (sched_verbose
>= 2)
1337 fprintf (sched_dump
, ";;\t\tReady-->Q: insn %s: ",
1338 (*current_sched_info
->print_insn
) (insn
, 0));
1340 fprintf (sched_dump
, "queued for %d cycles (%s).\n", n_cycles
, reason
);
1343 QUEUE_INDEX (insn
) = next_q
;
1346 /* Remove INSN from queue. */
1348 queue_remove (rtx insn
)
1350 gcc_assert (QUEUE_INDEX (insn
) >= 0);
1351 remove_free_INSN_LIST_elem (insn
, &insn_queue
[QUEUE_INDEX (insn
)]);
1353 QUEUE_INDEX (insn
) = QUEUE_NOWHERE
;
1356 /* Return a pointer to the bottom of the ready list, i.e. the insn
1357 with the lowest priority. */
1360 ready_lastpos (struct ready_list
*ready
)
1362 gcc_assert (ready
->n_ready
>= 1);
1363 return ready
->vec
+ ready
->first
- ready
->n_ready
+ 1;
1366 /* Add an element INSN to the ready list so that it ends up with the
1367 lowest/highest priority depending on FIRST_P. */
1369 HAIFA_INLINE
static void
1370 ready_add (struct ready_list
*ready
, rtx insn
, bool first_p
)
1374 if (ready
->first
== ready
->n_ready
)
1376 memmove (ready
->vec
+ ready
->veclen
- ready
->n_ready
,
1377 ready_lastpos (ready
),
1378 ready
->n_ready
* sizeof (rtx
));
1379 ready
->first
= ready
->veclen
- 1;
1381 ready
->vec
[ready
->first
- ready
->n_ready
] = insn
;
1385 if (ready
->first
== ready
->veclen
- 1)
1388 /* ready_lastpos() fails when called with (ready->n_ready == 0). */
1389 memmove (ready
->vec
+ ready
->veclen
- ready
->n_ready
- 1,
1390 ready_lastpos (ready
),
1391 ready
->n_ready
* sizeof (rtx
));
1392 ready
->first
= ready
->veclen
- 2;
1394 ready
->vec
[++(ready
->first
)] = insn
;
1398 if (DEBUG_INSN_P (insn
))
1401 gcc_assert (QUEUE_INDEX (insn
) != QUEUE_READY
);
1402 QUEUE_INDEX (insn
) = QUEUE_READY
;
1405 /* Remove the element with the highest priority from the ready list and
1408 HAIFA_INLINE
static rtx
1409 ready_remove_first (struct ready_list
*ready
)
1413 gcc_assert (ready
->n_ready
);
1414 t
= ready
->vec
[ready
->first
--];
1416 if (DEBUG_INSN_P (t
))
1418 /* If the queue becomes empty, reset it. */
1419 if (ready
->n_ready
== 0)
1420 ready
->first
= ready
->veclen
- 1;
1422 gcc_assert (QUEUE_INDEX (t
) == QUEUE_READY
);
1423 QUEUE_INDEX (t
) = QUEUE_NOWHERE
;
1428 /* The following code implements multi-pass scheduling for the first
1429 cycle. In other words, we will try to choose ready insn which
1430 permits to start maximum number of insns on the same cycle. */
1432 /* Return a pointer to the element INDEX from the ready. INDEX for
1433 insn with the highest priority is 0, and the lowest priority has
1437 ready_element (struct ready_list
*ready
, int index
)
1439 gcc_assert (ready
->n_ready
&& index
< ready
->n_ready
);
1441 return ready
->vec
[ready
->first
- index
];
1444 /* Remove the element INDEX from the ready list and return it. INDEX
1445 for insn with the highest priority is 0, and the lowest priority
1448 HAIFA_INLINE
static rtx
1449 ready_remove (struct ready_list
*ready
, int index
)
1455 return ready_remove_first (ready
);
1456 gcc_assert (ready
->n_ready
&& index
< ready
->n_ready
);
1457 t
= ready
->vec
[ready
->first
- index
];
1459 if (DEBUG_INSN_P (t
))
1461 for (i
= index
; i
< ready
->n_ready
; i
++)
1462 ready
->vec
[ready
->first
- i
] = ready
->vec
[ready
->first
- i
- 1];
1463 QUEUE_INDEX (t
) = QUEUE_NOWHERE
;
1467 /* Remove INSN from the ready list. */
1469 ready_remove_insn (rtx insn
)
1473 for (i
= 0; i
< readyp
->n_ready
; i
++)
1474 if (ready_element (readyp
, i
) == insn
)
1476 ready_remove (readyp
, i
);
1482 /* Sort the ready list READY by ascending priority, using the SCHED_SORT
1486 ready_sort (struct ready_list
*ready
)
1489 rtx
*first
= ready_lastpos (ready
);
1491 if (sched_pressure_p
)
1493 for (i
= 0; i
< ready
->n_ready
; i
++)
1494 if (!DEBUG_INSN_P (first
[i
]))
1495 setup_insn_reg_pressure_info (first
[i
]);
1497 SCHED_SORT (first
, ready
->n_ready
);
1500 /* PREV is an insn that is ready to execute. Adjust its priority if that
1501 will help shorten or lengthen register lifetimes as appropriate. Also
1502 provide a hook for the target to tweak itself. */
1504 HAIFA_INLINE
static void
1505 adjust_priority (rtx prev
)
1507 /* ??? There used to be code here to try and estimate how an insn
1508 affected register lifetimes, but it did it by looking at REG_DEAD
1509 notes, which we removed in schedule_region. Nor did it try to
1510 take into account register pressure or anything useful like that.
1512 Revisit when we have a machine model to work with and not before. */
1514 if (targetm
.sched
.adjust_priority
)
1515 INSN_PRIORITY (prev
) =
1516 targetm
.sched
.adjust_priority (prev
, INSN_PRIORITY (prev
));
1519 /* Advance DFA state STATE on one cycle. */
1521 advance_state (state_t state
)
1523 if (targetm
.sched
.dfa_pre_advance_cycle
)
1524 targetm
.sched
.dfa_pre_advance_cycle ();
1526 if (targetm
.sched
.dfa_pre_cycle_insn
)
1527 state_transition (state
,
1528 targetm
.sched
.dfa_pre_cycle_insn ());
1530 state_transition (state
, NULL
);
1532 if (targetm
.sched
.dfa_post_cycle_insn
)
1533 state_transition (state
,
1534 targetm
.sched
.dfa_post_cycle_insn ());
1536 if (targetm
.sched
.dfa_post_advance_cycle
)
1537 targetm
.sched
.dfa_post_advance_cycle ();
1540 /* Advance time on one cycle. */
1541 HAIFA_INLINE
static void
1542 advance_one_cycle (void)
1544 advance_state (curr_state
);
1545 if (sched_verbose
>= 6)
1546 fprintf (sched_dump
, ";;\tAdvanced a state.\n");
1549 /* Clock at which the previous instruction was issued. */
1550 static int last_clock_var
;
1552 /* Update register pressure after scheduling INSN. */
1554 update_register_pressure (rtx insn
)
1556 struct reg_use_data
*use
;
1557 struct reg_set_data
*set
;
1559 gcc_checking_assert (!DEBUG_INSN_P (insn
));
1561 for (use
= INSN_REG_USE_LIST (insn
); use
!= NULL
; use
= use
->next_insn_use
)
1562 if (dying_use_p (use
) && bitmap_bit_p (curr_reg_live
, use
->regno
))
1563 mark_regno_birth_or_death (use
->regno
, false);
1564 for (set
= INSN_REG_SET_LIST (insn
); set
!= NULL
; set
= set
->next_insn_set
)
1565 mark_regno_birth_or_death (set
->regno
, true);
1568 /* Set up or update (if UPDATE_P) max register pressure (see its
1569 meaning in sched-int.h::_haifa_insn_data) for all current BB insns
1570 after insn AFTER. */
1572 setup_insn_max_reg_pressure (rtx after
, bool update_p
)
1577 static int max_reg_pressure
[N_REG_CLASSES
];
1579 save_reg_pressure ();
1580 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1581 max_reg_pressure
[ira_pressure_classes
[i
]]
1582 = curr_reg_pressure
[ira_pressure_classes
[i
]];
1583 for (insn
= NEXT_INSN (after
);
1584 insn
!= NULL_RTX
&& ! BARRIER_P (insn
)
1585 && BLOCK_FOR_INSN (insn
) == BLOCK_FOR_INSN (after
);
1586 insn
= NEXT_INSN (insn
))
1587 if (NONDEBUG_INSN_P (insn
))
1590 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1592 p
= max_reg_pressure
[ira_pressure_classes
[i
]];
1593 if (INSN_MAX_REG_PRESSURE (insn
)[i
] != p
)
1596 INSN_MAX_REG_PRESSURE (insn
)[i
]
1597 = max_reg_pressure
[ira_pressure_classes
[i
]];
1600 if (update_p
&& eq_p
)
1602 update_register_pressure (insn
);
1603 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1604 if (max_reg_pressure
[ira_pressure_classes
[i
]]
1605 < curr_reg_pressure
[ira_pressure_classes
[i
]])
1606 max_reg_pressure
[ira_pressure_classes
[i
]]
1607 = curr_reg_pressure
[ira_pressure_classes
[i
]];
1609 restore_reg_pressure ();
1612 /* Update the current register pressure after scheduling INSN. Update
1613 also max register pressure for unscheduled insns of the current
1616 update_reg_and_insn_max_reg_pressure (rtx insn
)
1619 int before
[N_REG_CLASSES
];
1621 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1622 before
[i
] = curr_reg_pressure
[ira_pressure_classes
[i
]];
1623 update_register_pressure (insn
);
1624 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1625 if (curr_reg_pressure
[ira_pressure_classes
[i
]] != before
[i
])
1627 if (i
< ira_pressure_classes_num
)
1628 setup_insn_max_reg_pressure (insn
, true);
1631 /* Set up register pressure at the beginning of basic block BB whose
1632 insns starting after insn AFTER. Set up also max register pressure
1633 for all insns of the basic block. */
1635 sched_setup_bb_reg_pressure_info (basic_block bb
, rtx after
)
1637 gcc_assert (sched_pressure_p
);
1638 initiate_bb_reg_pressure_info (bb
);
1639 setup_insn_max_reg_pressure (after
, false);
1642 /* INSN is the "currently executing insn". Launch each insn which was
1643 waiting on INSN. READY is the ready list which contains the insns
1644 that are ready to fire. CLOCK is the current cycle. The function
1645 returns necessary cycle advance after issuing the insn (it is not
1646 zero for insns in a schedule group). */
1649 schedule_insn (rtx insn
)
1651 sd_iterator_def sd_it
;
1656 if (sched_verbose
>= 1)
1658 struct reg_pressure_data
*pressure_info
;
1661 print_insn (buf
, insn
, 0);
1663 fprintf (sched_dump
, ";;\t%3i--> %-40s:", clock_var
, buf
);
1665 if (recog_memoized (insn
) < 0)
1666 fprintf (sched_dump
, "nothing");
1668 print_reservation (sched_dump
, insn
);
1669 pressure_info
= INSN_REG_PRESSURE (insn
);
1670 if (pressure_info
!= NULL
)
1672 fputc (':', sched_dump
);
1673 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1674 fprintf (sched_dump
, "%s%+d(%d)",
1675 reg_class_names
[ira_pressure_classes
[i
]],
1676 pressure_info
[i
].set_increase
, pressure_info
[i
].change
);
1678 fputc ('\n', sched_dump
);
1681 if (sched_pressure_p
&& !DEBUG_INSN_P (insn
))
1682 update_reg_and_insn_max_reg_pressure (insn
);
1684 /* Scheduling instruction should have all its dependencies resolved and
1685 should have been removed from the ready list. */
1686 gcc_assert (sd_lists_empty_p (insn
, SD_LIST_BACK
));
1688 /* Reset debug insns invalidated by moving this insn. */
1689 if (MAY_HAVE_DEBUG_INSNS
&& !DEBUG_INSN_P (insn
))
1690 for (sd_it
= sd_iterator_start (insn
, SD_LIST_BACK
);
1691 sd_iterator_cond (&sd_it
, &dep
);)
1693 rtx dbg
= DEP_PRO (dep
);
1694 struct reg_use_data
*use
, *next
;
1696 gcc_assert (DEBUG_INSN_P (dbg
));
1698 if (sched_verbose
>= 6)
1699 fprintf (sched_dump
, ";;\t\tresetting: debug insn %d\n",
1702 /* ??? Rather than resetting the debug insn, we might be able
1703 to emit a debug temp before the just-scheduled insn, but
1704 this would involve checking that the expression at the
1705 point of the debug insn is equivalent to the expression
1706 before the just-scheduled insn. They might not be: the
1707 expression in the debug insn may depend on other insns not
1708 yet scheduled that set MEMs, REGs or even other debug
1709 insns. It's not clear that attempting to preserve debug
1710 information in these cases is worth the effort, given how
1711 uncommon these resets are and the likelihood that the debug
1712 temps introduced won't survive the schedule change. */
1713 INSN_VAR_LOCATION_LOC (dbg
) = gen_rtx_UNKNOWN_VAR_LOC ();
1714 df_insn_rescan (dbg
);
1716 /* Unknown location doesn't use any registers. */
1717 for (use
= INSN_REG_USE_LIST (dbg
); use
!= NULL
; use
= next
)
1719 struct reg_use_data
*prev
= use
;
1721 /* Remove use from the cyclic next_regno_use chain first. */
1722 while (prev
->next_regno_use
!= use
)
1723 prev
= prev
->next_regno_use
;
1724 prev
->next_regno_use
= use
->next_regno_use
;
1725 next
= use
->next_insn_use
;
1728 INSN_REG_USE_LIST (dbg
) = NULL
;
1730 /* We delete rather than resolve these deps, otherwise we
1731 crash in sched_free_deps(), because forward deps are
1732 expected to be released before backward deps. */
1733 sd_delete_dep (sd_it
);
1736 gcc_assert (QUEUE_INDEX (insn
) == QUEUE_NOWHERE
);
1737 QUEUE_INDEX (insn
) = QUEUE_SCHEDULED
;
1739 gcc_assert (INSN_TICK (insn
) >= MIN_TICK
);
1740 if (INSN_TICK (insn
) > clock_var
)
1741 /* INSN has been prematurely moved from the queue to the ready list.
1742 This is possible only if following flag is set. */
1743 gcc_assert (flag_sched_stalled_insns
);
1745 /* ??? Probably, if INSN is scheduled prematurely, we should leave
1746 INSN_TICK untouched. This is a machine-dependent issue, actually. */
1747 INSN_TICK (insn
) = clock_var
;
1749 /* Update dependent instructions. */
1750 for (sd_it
= sd_iterator_start (insn
, SD_LIST_FORW
);
1751 sd_iterator_cond (&sd_it
, &dep
);)
1753 rtx next
= DEP_CON (dep
);
1755 /* Resolve the dependence between INSN and NEXT.
1756 sd_resolve_dep () moves current dep to another list thus
1757 advancing the iterator. */
1758 sd_resolve_dep (sd_it
);
1760 /* Don't bother trying to mark next as ready if insn is a debug
1761 insn. If insn is the last hard dependency, it will have
1762 already been discounted. */
1763 if (DEBUG_INSN_P (insn
) && !DEBUG_INSN_P (next
))
1766 if (!IS_SPECULATION_BRANCHY_CHECK_P (insn
))
1770 effective_cost
= try_ready (next
);
1772 if (effective_cost
>= 0
1773 && SCHED_GROUP_P (next
)
1774 && advance
< effective_cost
)
1775 advance
= effective_cost
;
1778 /* Check always has only one forward dependence (to the first insn in
1779 the recovery block), therefore, this will be executed only once. */
1781 gcc_assert (sd_lists_empty_p (insn
, SD_LIST_FORW
));
1782 fix_recovery_deps (RECOVERY_BLOCK (insn
));
1786 /* This is the place where scheduler doesn't *basically* need backward and
1787 forward dependencies for INSN anymore. Nevertheless they are used in
1788 heuristics in rank_for_schedule (), early_queue_to_ready () and in
1789 some targets (e.g. rs6000). Thus the earliest place where we *can*
1790 remove dependencies is after targetm.sched.finish () call in
1791 schedule_block (). But, on the other side, the safest place to remove
1792 dependencies is when we are finishing scheduling entire region. As we
1793 don't generate [many] dependencies during scheduling itself, we won't
1794 need memory until beginning of next region.
1795 Bottom line: Dependencies are removed for all insns in the end of
1796 scheduling the region. */
1798 /* Annotate the instruction with issue information -- TImode
1799 indicates that the instruction is expected not to be able
1800 to issue on the same cycle as the previous insn. A machine
1801 may use this information to decide how the instruction should
1804 && GET_CODE (PATTERN (insn
)) != USE
1805 && GET_CODE (PATTERN (insn
)) != CLOBBER
1806 && !DEBUG_INSN_P (insn
))
1808 if (reload_completed
)
1809 PUT_MODE (insn
, clock_var
> last_clock_var
? TImode
: VOIDmode
);
1810 last_clock_var
= clock_var
;
1816 /* Functions for handling of notes. */
1818 /* Add note list that ends on FROM_END to the end of TO_ENDP. */
1820 concat_note_lists (rtx from_end
, rtx
*to_endp
)
1824 /* It's easy when have nothing to concat. */
1825 if (from_end
== NULL
)
1828 /* It's also easy when destination is empty. */
1829 if (*to_endp
== NULL
)
1831 *to_endp
= from_end
;
1835 from_start
= from_end
;
1836 while (PREV_INSN (from_start
) != NULL
)
1837 from_start
= PREV_INSN (from_start
);
1839 PREV_INSN (from_start
) = *to_endp
;
1840 NEXT_INSN (*to_endp
) = from_start
;
1841 *to_endp
= from_end
;
1844 /* Delete notes between HEAD and TAIL and put them in the chain
1845 of notes ended by NOTE_LIST. */
1847 remove_notes (rtx head
, rtx tail
)
1849 rtx next_tail
, insn
, next
;
1852 if (head
== tail
&& !INSN_P (head
))
1855 next_tail
= NEXT_INSN (tail
);
1856 for (insn
= head
; insn
!= next_tail
; insn
= next
)
1858 next
= NEXT_INSN (insn
);
1862 switch (NOTE_KIND (insn
))
1864 case NOTE_INSN_BASIC_BLOCK
:
1867 case NOTE_INSN_EPILOGUE_BEG
:
1871 add_reg_note (next
, REG_SAVE_NOTE
,
1872 GEN_INT (NOTE_INSN_EPILOGUE_BEG
));
1880 /* Add the note to list that ends at NOTE_LIST. */
1881 PREV_INSN (insn
) = note_list
;
1882 NEXT_INSN (insn
) = NULL_RTX
;
1884 NEXT_INSN (note_list
) = insn
;
1889 gcc_assert ((sel_sched_p () || insn
!= tail
) && insn
!= head
);
1894 /* Return the head and tail pointers of ebb starting at BEG and ending
1897 get_ebb_head_tail (basic_block beg
, basic_block end
, rtx
*headp
, rtx
*tailp
)
1899 rtx beg_head
= BB_HEAD (beg
);
1900 rtx beg_tail
= BB_END (beg
);
1901 rtx end_head
= BB_HEAD (end
);
1902 rtx end_tail
= BB_END (end
);
1904 /* Don't include any notes or labels at the beginning of the BEG
1905 basic block, or notes at the end of the END basic blocks. */
1907 if (LABEL_P (beg_head
))
1908 beg_head
= NEXT_INSN (beg_head
);
1910 while (beg_head
!= beg_tail
)
1911 if (NOTE_P (beg_head
))
1912 beg_head
= NEXT_INSN (beg_head
);
1913 else if (DEBUG_INSN_P (beg_head
))
1917 for (note
= NEXT_INSN (beg_head
);
1921 next
= NEXT_INSN (note
);
1924 if (sched_verbose
>= 9)
1925 fprintf (sched_dump
, "reorder %i\n", INSN_UID (note
));
1927 reorder_insns_nobb (note
, note
, PREV_INSN (beg_head
));
1929 if (BLOCK_FOR_INSN (note
) != beg
)
1930 df_insn_change_bb (note
, beg
);
1932 else if (!DEBUG_INSN_P (note
))
1944 end_head
= beg_head
;
1945 else if (LABEL_P (end_head
))
1946 end_head
= NEXT_INSN (end_head
);
1948 while (end_head
!= end_tail
)
1949 if (NOTE_P (end_tail
))
1950 end_tail
= PREV_INSN (end_tail
);
1951 else if (DEBUG_INSN_P (end_tail
))
1955 for (note
= PREV_INSN (end_tail
);
1959 prev
= PREV_INSN (note
);
1962 if (sched_verbose
>= 9)
1963 fprintf (sched_dump
, "reorder %i\n", INSN_UID (note
));
1965 reorder_insns_nobb (note
, note
, end_tail
);
1967 if (end_tail
== BB_END (end
))
1968 BB_END (end
) = note
;
1970 if (BLOCK_FOR_INSN (note
) != end
)
1971 df_insn_change_bb (note
, end
);
1973 else if (!DEBUG_INSN_P (note
))
1985 /* Return nonzero if there are no real insns in the range [ HEAD, TAIL ]. */
1988 no_real_insns_p (const_rtx head
, const_rtx tail
)
1990 while (head
!= NEXT_INSN (tail
))
1992 if (!NOTE_P (head
) && !LABEL_P (head
))
1994 head
= NEXT_INSN (head
);
1999 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
2000 previously found among the insns. Insert them just before HEAD. */
2002 restore_other_notes (rtx head
, basic_block head_bb
)
2006 rtx note_head
= note_list
;
2009 head_bb
= BLOCK_FOR_INSN (head
);
2011 head
= NEXT_INSN (bb_note (head_bb
));
2013 while (PREV_INSN (note_head
))
2015 set_block_for_insn (note_head
, head_bb
);
2016 note_head
= PREV_INSN (note_head
);
2018 /* In the above cycle we've missed this note. */
2019 set_block_for_insn (note_head
, head_bb
);
2021 PREV_INSN (note_head
) = PREV_INSN (head
);
2022 NEXT_INSN (PREV_INSN (head
)) = note_head
;
2023 PREV_INSN (head
) = note_list
;
2024 NEXT_INSN (note_list
) = head
;
2026 if (BLOCK_FOR_INSN (head
) != head_bb
)
2027 BB_END (head_bb
) = note_list
;
2035 /* Move insns that became ready to fire from queue to ready list. */
2038 queue_to_ready (struct ready_list
*ready
)
2044 q_ptr
= NEXT_Q (q_ptr
);
2046 if (dbg_cnt (sched_insn
) == false)
2047 /* If debug counter is activated do not requeue insn next after
2048 last_scheduled_insn. */
2049 skip_insn
= next_nonnote_nondebug_insn (last_scheduled_insn
);
2051 skip_insn
= NULL_RTX
;
2053 /* Add all pending insns that can be scheduled without stalls to the
2055 for (link
= insn_queue
[q_ptr
]; link
; link
= XEXP (link
, 1))
2057 insn
= XEXP (link
, 0);
2060 if (sched_verbose
>= 2)
2061 fprintf (sched_dump
, ";;\t\tQ-->Ready: insn %s: ",
2062 (*current_sched_info
->print_insn
) (insn
, 0));
2064 /* If the ready list is full, delay the insn for 1 cycle.
2065 See the comment in schedule_block for the rationale. */
2066 if (!reload_completed
2067 && ready
->n_ready
- ready
->n_debug
> MAX_SCHED_READY_INSNS
2068 && !SCHED_GROUP_P (insn
)
2069 && insn
!= skip_insn
)
2070 queue_insn (insn
, 1, "ready full");
2073 ready_add (ready
, insn
, false);
2074 if (sched_verbose
>= 2)
2075 fprintf (sched_dump
, "moving to ready without stalls\n");
2078 free_INSN_LIST_list (&insn_queue
[q_ptr
]);
2080 /* If there are no ready insns, stall until one is ready and add all
2081 of the pending insns at that point to the ready list. */
2082 if (ready
->n_ready
== 0)
2086 for (stalls
= 1; stalls
<= max_insn_queue_index
; stalls
++)
2088 if ((link
= insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]))
2090 for (; link
; link
= XEXP (link
, 1))
2092 insn
= XEXP (link
, 0);
2095 if (sched_verbose
>= 2)
2096 fprintf (sched_dump
, ";;\t\tQ-->Ready: insn %s: ",
2097 (*current_sched_info
->print_insn
) (insn
, 0));
2099 ready_add (ready
, insn
, false);
2100 if (sched_verbose
>= 2)
2101 fprintf (sched_dump
, "moving to ready with %d stalls\n", stalls
);
2103 free_INSN_LIST_list (&insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]);
2105 advance_one_cycle ();
2110 advance_one_cycle ();
2113 q_ptr
= NEXT_Q_AFTER (q_ptr
, stalls
);
2114 clock_var
+= stalls
;
2118 /* Used by early_queue_to_ready. Determines whether it is "ok" to
2119 prematurely move INSN from the queue to the ready list. Currently,
2120 if a target defines the hook 'is_costly_dependence', this function
2121 uses the hook to check whether there exist any dependences which are
2122 considered costly by the target, between INSN and other insns that
2123 have already been scheduled. Dependences are checked up to Y cycles
2124 back, with default Y=1; The flag -fsched-stalled-insns-dep=Y allows
2125 controlling this value.
2126 (Other considerations could be taken into account instead (or in
2127 addition) depending on user flags and target hooks. */
2130 ok_for_early_queue_removal (rtx insn
)
2133 rtx prev_insn
= last_scheduled_insn
;
2135 if (targetm
.sched
.is_costly_dependence
)
2137 for (n_cycles
= flag_sched_stalled_insns_dep
; n_cycles
; n_cycles
--)
2139 for ( ; prev_insn
; prev_insn
= PREV_INSN (prev_insn
))
2143 if (prev_insn
== current_sched_info
->prev_head
)
2149 if (!NOTE_P (prev_insn
))
2153 dep
= sd_find_dep_between (prev_insn
, insn
, true);
2157 cost
= dep_cost (dep
);
2159 if (targetm
.sched
.is_costly_dependence (dep
, cost
,
2160 flag_sched_stalled_insns_dep
- n_cycles
))
2165 if (GET_MODE (prev_insn
) == TImode
) /* end of dispatch group */
2171 prev_insn
= PREV_INSN (prev_insn
);
2179 /* Remove insns from the queue, before they become "ready" with respect
2180 to FU latency considerations. */
2183 early_queue_to_ready (state_t state
, struct ready_list
*ready
)
2191 state_t temp_state
= alloca (dfa_state_size
);
2193 int insns_removed
= 0;
2196 Flag '-fsched-stalled-insns=X' determines the aggressiveness of this
2199 X == 0: There is no limit on how many queued insns can be removed
2200 prematurely. (flag_sched_stalled_insns = -1).
2202 X >= 1: Only X queued insns can be removed prematurely in each
2203 invocation. (flag_sched_stalled_insns = X).
2205 Otherwise: Early queue removal is disabled.
2206 (flag_sched_stalled_insns = 0)
2209 if (! flag_sched_stalled_insns
)
2212 for (stalls
= 0; stalls
<= max_insn_queue_index
; stalls
++)
2214 if ((link
= insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]))
2216 if (sched_verbose
> 6)
2217 fprintf (sched_dump
, ";; look at index %d + %d\n", q_ptr
, stalls
);
2222 next_link
= XEXP (link
, 1);
2223 insn
= XEXP (link
, 0);
2224 if (insn
&& sched_verbose
> 6)
2225 print_rtl_single (sched_dump
, insn
);
2227 memcpy (temp_state
, state
, dfa_state_size
);
2228 if (recog_memoized (insn
) < 0)
2229 /* non-negative to indicate that it's not ready
2230 to avoid infinite Q->R->Q->R... */
2233 cost
= state_transition (temp_state
, insn
);
2235 if (sched_verbose
>= 6)
2236 fprintf (sched_dump
, "transition cost = %d\n", cost
);
2238 move_to_ready
= false;
2241 move_to_ready
= ok_for_early_queue_removal (insn
);
2242 if (move_to_ready
== true)
2244 /* move from Q to R */
2246 ready_add (ready
, insn
, false);
2249 XEXP (prev_link
, 1) = next_link
;
2251 insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)] = next_link
;
2253 free_INSN_LIST_node (link
);
2255 if (sched_verbose
>= 2)
2256 fprintf (sched_dump
, ";;\t\tEarly Q-->Ready: insn %s\n",
2257 (*current_sched_info
->print_insn
) (insn
, 0));
2260 if (insns_removed
== flag_sched_stalled_insns
)
2261 /* Remove no more than flag_sched_stalled_insns insns
2262 from Q at a time. */
2263 return insns_removed
;
2267 if (move_to_ready
== false)
2274 } /* for stalls.. */
2276 return insns_removed
;
2280 /* Print the ready list for debugging purposes. Callable from debugger. */
2283 debug_ready_list (struct ready_list
*ready
)
2288 if (ready
->n_ready
== 0)
2290 fprintf (sched_dump
, "\n");
2294 p
= ready_lastpos (ready
);
2295 for (i
= 0; i
< ready
->n_ready
; i
++)
2297 fprintf (sched_dump
, " %s:%d",
2298 (*current_sched_info
->print_insn
) (p
[i
], 0),
2300 if (sched_pressure_p
)
2301 fprintf (sched_dump
, "(cost=%d",
2302 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (p
[i
]));
2303 if (INSN_TICK (p
[i
]) > clock_var
)
2304 fprintf (sched_dump
, ":delay=%d", INSN_TICK (p
[i
]) - clock_var
);
2305 if (sched_pressure_p
)
2306 fprintf (sched_dump
, ")");
2308 fprintf (sched_dump
, "\n");
2311 /* Search INSN for REG_SAVE_NOTE notes and convert them back into insn
2312 NOTEs. This is used for NOTE_INSN_EPILOGUE_BEG, so that sched-ebb
2313 replaces the epilogue note in the correct basic block. */
2315 reemit_notes (rtx insn
)
2317 rtx note
, last
= insn
;
2319 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
2321 if (REG_NOTE_KIND (note
) == REG_SAVE_NOTE
)
2323 enum insn_note note_type
= (enum insn_note
) INTVAL (XEXP (note
, 0));
2325 last
= emit_note_before (note_type
, last
);
2326 remove_note (insn
, note
);
2331 /* Move INSN. Reemit notes if needed. Update CFG, if needed. */
2333 move_insn (rtx insn
, rtx last
, rtx nt
)
2335 if (PREV_INSN (insn
) != last
)
2341 bb
= BLOCK_FOR_INSN (insn
);
2343 /* BB_HEAD is either LABEL or NOTE. */
2344 gcc_assert (BB_HEAD (bb
) != insn
);
2346 if (BB_END (bb
) == insn
)
2347 /* If this is last instruction in BB, move end marker one
2350 /* Jumps are always placed at the end of basic block. */
2351 jump_p
= control_flow_insn_p (insn
);
2354 || ((common_sched_info
->sched_pass_id
== SCHED_RGN_PASS
)
2355 && IS_SPECULATION_BRANCHY_CHECK_P (insn
))
2356 || (common_sched_info
->sched_pass_id
2357 == SCHED_EBB_PASS
));
2359 gcc_assert (BLOCK_FOR_INSN (PREV_INSN (insn
)) == bb
);
2361 BB_END (bb
) = PREV_INSN (insn
);
2364 gcc_assert (BB_END (bb
) != last
);
2367 /* We move the block note along with jump. */
2371 note
= NEXT_INSN (insn
);
2372 while (NOTE_NOT_BB_P (note
) && note
!= nt
)
2373 note
= NEXT_INSN (note
);
2377 || BARRIER_P (note
)))
2378 note
= NEXT_INSN (note
);
2380 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
2385 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (note
);
2386 PREV_INSN (NEXT_INSN (note
)) = PREV_INSN (insn
);
2388 NEXT_INSN (note
) = NEXT_INSN (last
);
2389 PREV_INSN (NEXT_INSN (last
)) = note
;
2391 NEXT_INSN (last
) = insn
;
2392 PREV_INSN (insn
) = last
;
2394 bb
= BLOCK_FOR_INSN (last
);
2398 fix_jump_move (insn
);
2400 if (BLOCK_FOR_INSN (insn
) != bb
)
2401 move_block_after_check (insn
);
2403 gcc_assert (BB_END (bb
) == last
);
2406 df_insn_change_bb (insn
, bb
);
2408 /* Update BB_END, if needed. */
2409 if (BB_END (bb
) == last
)
2413 SCHED_GROUP_P (insn
) = 0;
2416 /* Return true if scheduling INSN will finish current clock cycle. */
2418 insn_finishes_cycle_p (rtx insn
)
2420 if (SCHED_GROUP_P (insn
))
2421 /* After issuing INSN, rest of the sched_group will be forced to issue
2422 in order. Don't make any plans for the rest of cycle. */
2425 /* Finishing the block will, apparently, finish the cycle. */
2426 if (current_sched_info
->insn_finishes_block_p
2427 && current_sched_info
->insn_finishes_block_p (insn
))
2433 /* Define type for target data used in multipass scheduling. */
2434 #ifndef TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T
2435 # define TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T int
2437 typedef TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T first_cycle_multipass_data_t
;
2439 /* The following structure describe an entry of the stack of choices. */
2442 /* Ordinal number of the issued insn in the ready queue. */
2444 /* The number of the rest insns whose issues we should try. */
2446 /* The number of issued essential insns. */
2448 /* State after issuing the insn. */
2450 /* Target-specific data. */
2451 first_cycle_multipass_data_t target_data
;
2454 /* The following array is used to implement a stack of choices used in
2455 function max_issue. */
2456 static struct choice_entry
*choice_stack
;
2458 /* The following variable value is number of essential insns issued on
2459 the current cycle. An insn is essential one if it changes the
2460 processors state. */
2461 int cycle_issued_insns
;
2463 /* This holds the value of the target dfa_lookahead hook. */
2466 /* The following variable value is maximal number of tries of issuing
2467 insns for the first cycle multipass insn scheduling. We define
2468 this value as constant*(DFA_LOOKAHEAD**ISSUE_RATE). We would not
2469 need this constraint if all real insns (with non-negative codes)
2470 had reservations because in this case the algorithm complexity is
2471 O(DFA_LOOKAHEAD**ISSUE_RATE). Unfortunately, the dfa descriptions
2472 might be incomplete and such insn might occur. For such
2473 descriptions, the complexity of algorithm (without the constraint)
2474 could achieve DFA_LOOKAHEAD ** N , where N is the queue length. */
2475 static int max_lookahead_tries
;
2477 /* The following value is value of hook
2478 `first_cycle_multipass_dfa_lookahead' at the last call of
2480 static int cached_first_cycle_multipass_dfa_lookahead
= 0;
2482 /* The following value is value of `issue_rate' at the last call of
2484 static int cached_issue_rate
= 0;
2486 /* The following function returns maximal (or close to maximal) number
2487 of insns which can be issued on the same cycle and one of which
2488 insns is insns with the best rank (the first insn in READY). To
2489 make this function tries different samples of ready insns. READY
2490 is current queue `ready'. Global array READY_TRY reflects what
2491 insns are already issued in this try. The function stops immediately,
2492 if it reached the such a solution, that all instruction can be issued.
2493 INDEX will contain index of the best insn in READY. The following
2494 function is used only for first cycle multipass scheduling.
2498 This function expects recognized insns only. All USEs,
2499 CLOBBERs, etc must be filtered elsewhere. */
2501 max_issue (struct ready_list
*ready
, int privileged_n
, state_t state
,
2502 bool first_cycle_insn_p
, int *index
)
2504 int n
, i
, all
, n_ready
, best
, delay
, tries_num
;
2506 struct choice_entry
*top
;
2509 n_ready
= ready
->n_ready
;
2510 gcc_assert (dfa_lookahead
>= 1 && privileged_n
>= 0
2511 && privileged_n
<= n_ready
);
2513 /* Init MAX_LOOKAHEAD_TRIES. */
2514 if (cached_first_cycle_multipass_dfa_lookahead
!= dfa_lookahead
)
2516 cached_first_cycle_multipass_dfa_lookahead
= dfa_lookahead
;
2517 max_lookahead_tries
= 100;
2518 for (i
= 0; i
< issue_rate
; i
++)
2519 max_lookahead_tries
*= dfa_lookahead
;
2522 /* Init max_points. */
2523 more_issue
= issue_rate
- cycle_issued_insns
;
2524 gcc_assert (more_issue
>= 0);
2526 /* The number of the issued insns in the best solution. */
2531 /* Set initial state of the search. */
2532 memcpy (top
->state
, state
, dfa_state_size
);
2533 top
->rest
= dfa_lookahead
;
2535 if (targetm
.sched
.first_cycle_multipass_begin
)
2536 targetm
.sched
.first_cycle_multipass_begin (&top
->target_data
,
2538 first_cycle_insn_p
);
2540 /* Count the number of the insns to search among. */
2541 for (all
= i
= 0; i
< n_ready
; i
++)
2545 /* I is the index of the insn to try next. */
2550 if (/* If we've reached a dead end or searched enough of what we have
2553 /* or have nothing else to try... */
2555 /* or should not issue more. */
2556 || top
->n
>= more_issue
)
2558 /* ??? (... || i == n_ready). */
2559 gcc_assert (i
<= n_ready
);
2561 /* We should not issue more than issue_rate instructions. */
2562 gcc_assert (top
->n
<= more_issue
);
2564 if (top
== choice_stack
)
2567 if (best
< top
- choice_stack
)
2572 /* Try to find issued privileged insn. */
2573 while (n
&& !ready_try
[--n
]);
2576 if (/* If all insns are equally good... */
2578 /* Or a privileged insn will be issued. */
2580 /* Then we have a solution. */
2582 best
= top
- choice_stack
;
2583 /* This is the index of the insn issued first in this
2585 *index
= choice_stack
[1].index
;
2586 if (top
->n
== more_issue
|| best
== all
)
2591 /* Set ready-list index to point to the last insn
2592 ('i++' below will advance it to the next insn). */
2598 if (targetm
.sched
.first_cycle_multipass_backtrack
)
2599 targetm
.sched
.first_cycle_multipass_backtrack (&top
->target_data
,
2600 ready_try
, n_ready
);
2603 memcpy (state
, top
->state
, dfa_state_size
);
2605 else if (!ready_try
[i
])
2608 if (tries_num
> max_lookahead_tries
)
2610 insn
= ready_element (ready
, i
);
2611 delay
= state_transition (state
, insn
);
2614 if (state_dead_lock_p (state
)
2615 || insn_finishes_cycle_p (insn
))
2616 /* We won't issue any more instructions in the next
2623 if (memcmp (top
->state
, state
, dfa_state_size
) != 0)
2626 /* Advance to the next choice_entry. */
2628 /* Initialize it. */
2629 top
->rest
= dfa_lookahead
;
2632 memcpy (top
->state
, state
, dfa_state_size
);
2635 if (targetm
.sched
.first_cycle_multipass_issue
)
2636 targetm
.sched
.first_cycle_multipass_issue (&top
->target_data
,
2646 /* Increase ready-list index. */
2650 if (targetm
.sched
.first_cycle_multipass_end
)
2651 targetm
.sched
.first_cycle_multipass_end (best
!= 0
2652 ? &choice_stack
[1].target_data
2655 /* Restore the original state of the DFA. */
2656 memcpy (state
, choice_stack
->state
, dfa_state_size
);
2661 /* The following function chooses insn from READY and modifies
2662 READY. The following function is used only for first
2663 cycle multipass scheduling.
2665 -1 if cycle should be advanced,
2666 0 if INSN_PTR is set to point to the desirable insn,
2667 1 if choose_ready () should be restarted without advancing the cycle. */
2669 choose_ready (struct ready_list
*ready
, bool first_cycle_insn_p
,
2674 if (dbg_cnt (sched_insn
) == false)
2678 insn
= next_nonnote_insn (last_scheduled_insn
);
2680 if (QUEUE_INDEX (insn
) == QUEUE_READY
)
2681 /* INSN is in the ready_list. */
2683 ready_remove_insn (insn
);
2688 /* INSN is in the queue. Advance cycle to move it to the ready list. */
2694 if (targetm
.sched
.first_cycle_multipass_dfa_lookahead
)
2695 lookahead
= targetm
.sched
.first_cycle_multipass_dfa_lookahead ();
2696 if (lookahead
<= 0 || SCHED_GROUP_P (ready_element (ready
, 0))
2697 || DEBUG_INSN_P (ready_element (ready
, 0)))
2699 if (targetm
.sched
.dispatch (NULL_RTX
, IS_DISPATCH_ON
))
2700 *insn_ptr
= ready_remove_first_dispatch (ready
);
2702 *insn_ptr
= ready_remove_first (ready
);
2708 /* Try to choose the better insn. */
2709 int index
= 0, i
, n
;
2711 int try_data
= 1, try_control
= 1;
2714 insn
= ready_element (ready
, 0);
2715 if (INSN_CODE (insn
) < 0)
2717 *insn_ptr
= ready_remove_first (ready
);
2722 && spec_info
->flags
& (PREFER_NON_DATA_SPEC
2723 | PREFER_NON_CONTROL_SPEC
))
2725 for (i
= 0, n
= ready
->n_ready
; i
< n
; i
++)
2730 x
= ready_element (ready
, i
);
2733 if (spec_info
->flags
& PREFER_NON_DATA_SPEC
2734 && !(s
& DATA_SPEC
))
2737 if (!(spec_info
->flags
& PREFER_NON_CONTROL_SPEC
)
2742 if (spec_info
->flags
& PREFER_NON_CONTROL_SPEC
2743 && !(s
& CONTROL_SPEC
))
2746 if (!(spec_info
->flags
& PREFER_NON_DATA_SPEC
) || !try_data
)
2752 ts
= TODO_SPEC (insn
);
2753 if ((ts
& SPECULATIVE
)
2754 && (((!try_data
&& (ts
& DATA_SPEC
))
2755 || (!try_control
&& (ts
& CONTROL_SPEC
)))
2756 || (targetm
.sched
.first_cycle_multipass_dfa_lookahead_guard_spec
2758 .first_cycle_multipass_dfa_lookahead_guard_spec (insn
))))
2759 /* Discard speculative instruction that stands first in the ready
2762 change_queue_index (insn
, 1);
2768 for (i
= 1; i
< ready
->n_ready
; i
++)
2770 insn
= ready_element (ready
, i
);
2773 = ((!try_data
&& (TODO_SPEC (insn
) & DATA_SPEC
))
2774 || (!try_control
&& (TODO_SPEC (insn
) & CONTROL_SPEC
)));
2777 /* Let the target filter the search space. */
2778 for (i
= 1; i
< ready
->n_ready
; i
++)
2781 insn
= ready_element (ready
, i
);
2783 /* If this insn is recognizable we should have already
2784 recognized it earlier.
2785 ??? Not very clear where this is supposed to be done.
2787 gcc_checking_assert (INSN_CODE (insn
) >= 0
2788 || recog_memoized (insn
) < 0);
2791 = (/* INSN_CODE check can be omitted here as it is also done later
2793 INSN_CODE (insn
) < 0
2794 || (targetm
.sched
.first_cycle_multipass_dfa_lookahead_guard
2795 && !targetm
.sched
.first_cycle_multipass_dfa_lookahead_guard
2799 if (max_issue (ready
, 1, curr_state
, first_cycle_insn_p
, &index
) == 0)
2801 *insn_ptr
= ready_remove_first (ready
);
2802 if (sched_verbose
>= 4)
2803 fprintf (sched_dump
, ";;\t\tChosen insn (but can't issue) : %s \n",
2804 (*current_sched_info
->print_insn
) (*insn_ptr
, 0));
2809 if (sched_verbose
>= 4)
2810 fprintf (sched_dump
, ";;\t\tChosen insn : %s\n",
2811 (*current_sched_info
->print_insn
)
2812 (ready_element (ready
, index
), 0));
2814 *insn_ptr
= ready_remove (ready
, index
);
2820 /* This function is called when we have successfully scheduled a
2821 block. It uses the schedule stored in the scheduled_insns vector
2822 to rearrange the RTL. PREV_HEAD is used as the anchor to which we
2823 append the scheduled insns; TAIL is the insn after the scheduled
2824 block. TARGET_BB is the argument passed to schedule_block. */
2827 commit_schedule (rtx prev_head
, rtx tail
, basic_block
*target_bb
)
2831 last_scheduled_insn
= prev_head
;
2832 for (i
= 0; i
< (int)VEC_length (rtx
, scheduled_insns
); i
++)
2834 rtx insn
= VEC_index (rtx
, scheduled_insns
, i
);
2836 if (control_flow_insn_p (last_scheduled_insn
)
2837 || current_sched_info
->advance_target_bb (*target_bb
, insn
))
2839 *target_bb
= current_sched_info
->advance_target_bb (*target_bb
, 0);
2845 x
= next_real_insn (last_scheduled_insn
);
2847 dump_new_block_header (1, *target_bb
, x
, tail
);
2850 last_scheduled_insn
= bb_note (*target_bb
);
2853 if (current_sched_info
->begin_move_insn
)
2854 (*current_sched_info
->begin_move_insn
) (insn
, last_scheduled_insn
);
2855 move_insn (insn
, last_scheduled_insn
,
2856 current_sched_info
->next_tail
);
2857 if (!DEBUG_INSN_P (insn
))
2858 reemit_notes (insn
);
2859 last_scheduled_insn
= insn
;
2862 VEC_truncate (rtx
, scheduled_insns
, 0);
2865 /* Examine all insns on the ready list and queue those which can't be
2866 issued in this cycle. TEMP_STATE is temporary scheduler state we
2867 can use as scratch space. If FIRST_CYCLE_INSN_P is true, no insns
2868 have been issued for the current cycle, which means it is valid to
2869 issue an asm statement. */
2872 prune_ready_list (state_t temp_state
, bool first_cycle_insn_p
)
2877 for (i
= 0; i
< ready
.n_ready
; i
++)
2879 rtx insn
= ready_element (&ready
, i
);
2881 const char *reason
= "resource conflict";
2883 if (recog_memoized (insn
) < 0)
2885 if (!first_cycle_insn_p
2886 && (GET_CODE (PATTERN (insn
)) == ASM_INPUT
2887 || asm_noperands (PATTERN (insn
)) >= 0))
2891 else if (flag_sched_pressure
)
2895 memcpy (temp_state
, curr_state
, dfa_state_size
);
2896 cost
= state_transition (temp_state
, insn
);
2904 ready_remove (&ready
, i
);
2905 queue_insn (insn
, cost
, reason
);
2911 /* Use forward list scheduling to rearrange insns of block pointed to by
2912 TARGET_BB, possibly bringing insns from subsequent blocks in the same
2916 schedule_block (basic_block
*target_bb
)
2919 bool first_cycle_insn_p
;
2921 state_t temp_state
= NULL
; /* It is used for multipass scheduling. */
2922 int sort_p
, advance
, start_clock_var
;
2924 /* Head/tail info for this block. */
2925 rtx prev_head
= current_sched_info
->prev_head
;
2926 rtx next_tail
= current_sched_info
->next_tail
;
2927 rtx head
= NEXT_INSN (prev_head
);
2928 rtx tail
= PREV_INSN (next_tail
);
2930 /* We used to have code to avoid getting parameters moved from hard
2931 argument registers into pseudos.
2933 However, it was removed when it proved to be of marginal benefit
2934 and caused problems because schedule_block and compute_forward_dependences
2935 had different notions of what the "head" insn was. */
2937 gcc_assert (head
!= tail
|| INSN_P (head
));
2939 haifa_recovery_bb_recently_added_p
= false;
2943 dump_new_block_header (0, *target_bb
, head
, tail
);
2945 state_reset (curr_state
);
2947 /* Clear the ready list. */
2948 ready
.first
= ready
.veclen
- 1;
2952 /* It is used for first cycle multipass scheduling. */
2953 temp_state
= alloca (dfa_state_size
);
2955 if (targetm
.sched
.init
)
2956 targetm
.sched
.init (sched_dump
, sched_verbose
, ready
.veclen
);
2958 /* We start inserting insns after PREV_HEAD. */
2959 last_scheduled_insn
= prev_head
;
2961 gcc_assert ((NOTE_P (last_scheduled_insn
)
2962 || DEBUG_INSN_P (last_scheduled_insn
))
2963 && BLOCK_FOR_INSN (last_scheduled_insn
) == *target_bb
);
2965 /* Initialize INSN_QUEUE. Q_SIZE is the total number of insns in the
2970 insn_queue
= XALLOCAVEC (rtx
, max_insn_queue_index
+ 1);
2971 memset (insn_queue
, 0, (max_insn_queue_index
+ 1) * sizeof (rtx
));
2973 /* Start just before the beginning of time. */
2976 /* We need queue and ready lists and clock_var be initialized
2977 in try_ready () (which is called through init_ready_list ()). */
2978 (*current_sched_info
->init_ready_list
) ();
2980 /* The algorithm is O(n^2) in the number of ready insns at any given
2981 time in the worst case. Before reload we are more likely to have
2982 big lists so truncate them to a reasonable size. */
2983 if (!reload_completed
2984 && ready
.n_ready
- ready
.n_debug
> MAX_SCHED_READY_INSNS
)
2986 ready_sort (&ready
);
2988 /* Find first free-standing insn past MAX_SCHED_READY_INSNS.
2989 If there are debug insns, we know they're first. */
2990 for (i
= MAX_SCHED_READY_INSNS
+ ready
.n_debug
; i
< ready
.n_ready
; i
++)
2991 if (!SCHED_GROUP_P (ready_element (&ready
, i
)))
2994 if (sched_verbose
>= 2)
2996 fprintf (sched_dump
,
2997 ";;\t\tReady list on entry: %d insns\n", ready
.n_ready
);
2998 fprintf (sched_dump
,
2999 ";;\t\t before reload => truncated to %d insns\n", i
);
3002 /* Delay all insns past it for 1 cycle. If debug counter is
3003 activated make an exception for the insn right after
3004 last_scheduled_insn. */
3008 if (dbg_cnt (sched_insn
) == false)
3009 skip_insn
= next_nonnote_insn (last_scheduled_insn
);
3011 skip_insn
= NULL_RTX
;
3013 while (i
< ready
.n_ready
)
3017 insn
= ready_remove (&ready
, i
);
3019 if (insn
!= skip_insn
)
3020 queue_insn (insn
, 1, "list truncated");
3025 /* Now we can restore basic block notes and maintain precise cfg. */
3026 restore_bb_notes (*target_bb
);
3028 last_clock_var
= -1;
3032 gcc_assert (VEC_length (rtx
, scheduled_insns
) == 0);
3034 /* Loop until all the insns in BB are scheduled. */
3035 while ((*current_sched_info
->schedule_more_p
) ())
3039 start_clock_var
= clock_var
;
3043 advance_one_cycle ();
3045 /* Add to the ready list all pending insns that can be issued now.
3046 If there are no ready insns, increment clock until one
3047 is ready and add all pending insns at that point to the ready
3049 queue_to_ready (&ready
);
3051 gcc_assert (ready
.n_ready
);
3053 if (sched_verbose
>= 2)
3055 fprintf (sched_dump
, ";;\t\tReady list after queue_to_ready: ");
3056 debug_ready_list (&ready
);
3058 advance
-= clock_var
- start_clock_var
;
3060 while (advance
> 0);
3062 prune_ready_list (temp_state
, true);
3063 if (ready
.n_ready
== 0)
3068 /* Sort the ready list based on priority. */
3069 ready_sort (&ready
);
3071 if (sched_verbose
>= 2)
3073 fprintf (sched_dump
, ";;\t\tReady list after ready_sort: ");
3074 debug_ready_list (&ready
);
3078 /* We don't want md sched reorder to even see debug isns, so put
3079 them out right away. */
3080 if (ready
.n_ready
&& DEBUG_INSN_P (ready_element (&ready
, 0)))
3082 while (ready
.n_ready
&& DEBUG_INSN_P (ready_element (&ready
, 0)))
3084 rtx insn
= ready_remove_first (&ready
);
3085 gcc_assert (DEBUG_INSN_P (insn
));
3086 (*current_sched_info
->begin_schedule_ready
) (insn
);
3087 VEC_safe_push (rtx
, heap
, scheduled_insns
, insn
);
3088 last_scheduled_insn
= insn
;
3089 advance
= schedule_insn (insn
);
3090 gcc_assert (advance
== 0);
3091 if (ready
.n_ready
> 0)
3092 ready_sort (&ready
);
3099 /* Allow the target to reorder the list, typically for
3100 better instruction bundling. */
3101 if (sort_p
&& targetm
.sched
.reorder
3102 && (ready
.n_ready
== 0
3103 || !SCHED_GROUP_P (ready_element (&ready
, 0))))
3105 targetm
.sched
.reorder (sched_dump
, sched_verbose
,
3106 ready_lastpos (&ready
),
3107 &ready
.n_ready
, clock_var
);
3109 can_issue_more
= issue_rate
;
3111 first_cycle_insn_p
= true;
3112 cycle_issued_insns
= 0;
3119 if (sched_verbose
>= 2)
3121 fprintf (sched_dump
, ";;\tReady list (t = %3d): ",
3123 debug_ready_list (&ready
);
3124 if (sched_pressure_p
)
3125 print_curr_reg_pressure ();
3128 if (ready
.n_ready
== 0
3130 && reload_completed
)
3132 /* Allow scheduling insns directly from the queue in case
3133 there's nothing better to do (ready list is empty) but
3134 there are still vacant dispatch slots in the current cycle. */
3135 if (sched_verbose
>= 6)
3136 fprintf (sched_dump
,";;\t\tSecond chance\n");
3137 memcpy (temp_state
, curr_state
, dfa_state_size
);
3138 if (early_queue_to_ready (temp_state
, &ready
))
3139 ready_sort (&ready
);
3142 if (ready
.n_ready
== 0
3144 || state_dead_lock_p (curr_state
)
3145 || !(*current_sched_info
->schedule_more_p
) ())
3148 /* Select and remove the insn from the ready list. */
3154 res
= choose_ready (&ready
, first_cycle_insn_p
, &insn
);
3160 /* Restart choose_ready (). */
3163 gcc_assert (insn
!= NULL_RTX
);
3166 insn
= ready_remove_first (&ready
);
3168 if (sched_pressure_p
&& INSN_TICK (insn
) > clock_var
)
3170 ready_add (&ready
, insn
, true);
3175 if (targetm
.sched
.dfa_new_cycle
3176 && targetm
.sched
.dfa_new_cycle (sched_dump
, sched_verbose
,
3177 insn
, last_clock_var
,
3178 clock_var
, &sort_p
))
3179 /* SORT_P is used by the target to override sorting
3180 of the ready list. This is needed when the target
3181 has modified its internal structures expecting that
3182 the insn will be issued next. As we need the insn
3183 to have the highest priority (so it will be returned by
3184 the ready_remove_first call above), we invoke
3185 ready_add (&ready, insn, true).
3186 But, still, there is one issue: INSN can be later
3187 discarded by scheduler's front end through
3188 current_sched_info->can_schedule_ready_p, hence, won't
3191 ready_add (&ready
, insn
, true);
3197 if (current_sched_info
->can_schedule_ready_p
3198 && ! (*current_sched_info
->can_schedule_ready_p
) (insn
))
3199 /* We normally get here only if we don't want to move
3200 insn from the split block. */
3202 TODO_SPEC (insn
) = (TODO_SPEC (insn
) & ~SPECULATIVE
) | HARD_DEP
;
3206 /* DECISION is made. */
3208 if (TODO_SPEC (insn
) & SPECULATIVE
)
3209 generate_recovery_code (insn
);
3211 if (targetm
.sched
.dispatch (NULL_RTX
, IS_DISPATCH_ON
))
3212 targetm
.sched
.dispatch_do (insn
, ADD_TO_DISPATCH_WINDOW
);
3214 /* Update counters, etc in the scheduler's front end. */
3215 (*current_sched_info
->begin_schedule_ready
) (insn
);
3216 VEC_safe_push (rtx
, heap
, scheduled_insns
, insn
);
3217 last_scheduled_insn
= insn
;
3219 if (recog_memoized (insn
) >= 0)
3221 cost
= state_transition (curr_state
, insn
);
3222 if (!flag_sched_pressure
)
3223 gcc_assert (cost
< 0);
3224 cycle_issued_insns
++;
3228 asm_p
= (GET_CODE (PATTERN (insn
)) == ASM_INPUT
3229 || asm_noperands (PATTERN (insn
)) >= 0);
3231 if (targetm
.sched
.variable_issue
)
3233 targetm
.sched
.variable_issue (sched_dump
, sched_verbose
,
3234 insn
, can_issue_more
);
3235 /* A naked CLOBBER or USE generates no instruction, so do
3236 not count them against the issue rate. */
3237 else if (GET_CODE (PATTERN (insn
)) != USE
3238 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
3240 advance
= schedule_insn (insn
);
3242 /* After issuing an asm insn we should start a new cycle. */
3243 if (advance
== 0 && asm_p
)
3248 first_cycle_insn_p
= false;
3250 if (ready
.n_ready
> 0)
3251 prune_ready_list (temp_state
, false);
3253 /* Sort the ready list based on priority. This must be
3254 redone here, as schedule_insn may have readied additional
3255 insns that will not be sorted correctly. */
3256 if (ready
.n_ready
> 0)
3257 ready_sort (&ready
);
3259 /* Quickly go through debug insns such that md sched
3260 reorder2 doesn't have to deal with debug insns. */
3261 if (ready
.n_ready
&& DEBUG_INSN_P (ready_element (&ready
, 0))
3262 && (*current_sched_info
->schedule_more_p
) ())
3264 while (ready
.n_ready
&& DEBUG_INSN_P (ready_element (&ready
, 0)))
3266 insn
= ready_remove_first (&ready
);
3267 gcc_assert (DEBUG_INSN_P (insn
));
3268 (*current_sched_info
->begin_schedule_ready
) (insn
);
3269 VEC_safe_push (rtx
, heap
, scheduled_insns
, insn
);
3270 advance
= schedule_insn (insn
);
3271 last_scheduled_insn
= insn
;
3272 gcc_assert (advance
== 0);
3273 if (ready
.n_ready
> 0)
3274 ready_sort (&ready
);
3278 if (targetm
.sched
.reorder2
3279 && (ready
.n_ready
== 0
3280 || !SCHED_GROUP_P (ready_element (&ready
, 0))))
3283 targetm
.sched
.reorder2 (sched_dump
, sched_verbose
,
3285 ? ready_lastpos (&ready
) : NULL
,
3286 &ready
.n_ready
, clock_var
);
3294 fprintf (sched_dump
, ";;\tReady list (final): ");
3295 debug_ready_list (&ready
);
3298 if (current_sched_info
->queue_must_finish_empty
)
3299 /* Sanity check -- queue must be empty now. Meaningless if region has
3301 gcc_assert (!q_size
&& !ready
.n_ready
&& !ready
.n_debug
);
3304 /* We must maintain QUEUE_INDEX between blocks in region. */
3305 for (i
= ready
.n_ready
- 1; i
>= 0; i
--)
3309 x
= ready_element (&ready
, i
);
3310 QUEUE_INDEX (x
) = QUEUE_NOWHERE
;
3311 TODO_SPEC (x
) = (TODO_SPEC (x
) & ~SPECULATIVE
) | HARD_DEP
;
3315 for (i
= 0; i
<= max_insn_queue_index
; i
++)
3318 for (link
= insn_queue
[i
]; link
; link
= XEXP (link
, 1))
3323 QUEUE_INDEX (x
) = QUEUE_NOWHERE
;
3324 TODO_SPEC (x
) = (TODO_SPEC (x
) & ~SPECULATIVE
) | HARD_DEP
;
3326 free_INSN_LIST_list (&insn_queue
[i
]);
3330 commit_schedule (prev_head
, tail
, target_bb
);
3332 fprintf (sched_dump
, ";; total time = %d\n", clock_var
);
3334 if (!current_sched_info
->queue_must_finish_empty
3335 || haifa_recovery_bb_recently_added_p
)
3337 /* INSN_TICK (minimum clock tick at which the insn becomes
3338 ready) may be not correct for the insn in the subsequent
3339 blocks of the region. We should use a correct value of
3340 `clock_var' or modify INSN_TICK. It is better to keep
3341 clock_var value equal to 0 at the start of a basic block.
3342 Therefore we modify INSN_TICK here. */
3343 fix_inter_tick (NEXT_INSN (prev_head
), last_scheduled_insn
);
3346 if (targetm
.sched
.finish
)
3348 targetm
.sched
.finish (sched_dump
, sched_verbose
);
3349 /* Target might have added some instructions to the scheduled block
3350 in its md_finish () hook. These new insns don't have any data
3351 initialized and to identify them we extend h_i_d so that they'll
3353 sched_init_luids (NULL
, NULL
, NULL
, NULL
);
3357 fprintf (sched_dump
, ";; new head = %d\n;; new tail = %d\n\n",
3358 INSN_UID (head
), INSN_UID (tail
));
3360 /* Update head/tail boundaries. */
3361 head
= NEXT_INSN (prev_head
);
3362 tail
= last_scheduled_insn
;
3364 head
= restore_other_notes (head
, NULL
);
3366 current_sched_info
->head
= head
;
3367 current_sched_info
->tail
= tail
;
3370 /* Set_priorities: compute priority of each insn in the block. */
3373 set_priorities (rtx head
, rtx tail
)
3377 int sched_max_insns_priority
=
3378 current_sched_info
->sched_max_insns_priority
;
3381 if (head
== tail
&& ! INSN_P (head
))
3386 prev_head
= PREV_INSN (head
);
3387 for (insn
= tail
; insn
!= prev_head
; insn
= PREV_INSN (insn
))
3393 (void) priority (insn
);
3395 gcc_assert (INSN_PRIORITY_KNOWN (insn
));
3397 sched_max_insns_priority
= MAX (sched_max_insns_priority
,
3398 INSN_PRIORITY (insn
));
3401 current_sched_info
->sched_max_insns_priority
= sched_max_insns_priority
;
3406 /* Set dump and sched_verbose for the desired debugging output. If no
3407 dump-file was specified, but -fsched-verbose=N (any N), print to stderr.
3408 For -fsched-verbose=N, N>=10, print everything to stderr. */
3410 setup_sched_dump (void)
3412 sched_verbose
= sched_verbose_param
;
3413 if (sched_verbose_param
== 0 && dump_file
)
3415 sched_dump
= ((sched_verbose_param
>= 10 || !dump_file
)
3416 ? stderr
: dump_file
);
3419 /* Initialize some global state for the scheduler. This function works
3420 with the common data shared between all the schedulers. It is called
3421 from the scheduler specific initialization routine. */
3426 /* Disable speculative loads in their presence if cc0 defined. */
3428 flag_schedule_speculative_load
= 0;
3431 if (targetm
.sched
.dispatch (NULL_RTX
, IS_DISPATCH_ON
))
3432 targetm
.sched
.dispatch_do (NULL_RTX
, DISPATCH_INIT
);
3434 sched_pressure_p
= (flag_sched_pressure
&& ! reload_completed
3435 && common_sched_info
->sched_pass_id
== SCHED_RGN_PASS
);
3437 if (sched_pressure_p
)
3438 ira_setup_eliminable_regset ();
3440 /* Initialize SPEC_INFO. */
3441 if (targetm
.sched
.set_sched_flags
)
3443 spec_info
= &spec_info_var
;
3444 targetm
.sched
.set_sched_flags (spec_info
);
3446 if (spec_info
->mask
!= 0)
3448 spec_info
->data_weakness_cutoff
=
3449 (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF
) * MAX_DEP_WEAK
) / 100;
3450 spec_info
->control_weakness_cutoff
=
3451 (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF
)
3452 * REG_BR_PROB_BASE
) / 100;
3455 /* So we won't read anything accidentally. */
3460 /* So we won't read anything accidentally. */
3463 /* Initialize issue_rate. */
3464 if (targetm
.sched
.issue_rate
)
3465 issue_rate
= targetm
.sched
.issue_rate ();
3469 if (cached_issue_rate
!= issue_rate
)
3471 cached_issue_rate
= issue_rate
;
3472 /* To invalidate max_lookahead_tries: */
3473 cached_first_cycle_multipass_dfa_lookahead
= 0;
3476 if (targetm
.sched
.first_cycle_multipass_dfa_lookahead
)
3477 dfa_lookahead
= targetm
.sched
.first_cycle_multipass_dfa_lookahead ();
3481 if (targetm
.sched
.init_dfa_pre_cycle_insn
)
3482 targetm
.sched
.init_dfa_pre_cycle_insn ();
3484 if (targetm
.sched
.init_dfa_post_cycle_insn
)
3485 targetm
.sched
.init_dfa_post_cycle_insn ();
3488 dfa_state_size
= state_size ();
3490 init_alias_analysis ();
3492 df_set_flags (DF_LR_RUN_DCE
);
3493 df_note_add_problem ();
3495 /* More problems needed for interloop dep calculation in SMS. */
3496 if (common_sched_info
->sched_pass_id
== SCHED_SMS_PASS
)
3498 df_rd_add_problem ();
3499 df_chain_add_problem (DF_DU_CHAIN
+ DF_UD_CHAIN
);
3504 /* Do not run DCE after reload, as this can kill nops inserted
3506 if (reload_completed
)
3507 df_clear_flags (DF_LR_RUN_DCE
);
3509 regstat_compute_calls_crossed ();
3511 if (targetm
.sched
.init_global
)
3512 targetm
.sched
.init_global (sched_dump
, sched_verbose
, get_max_uid () + 1);
3514 if (sched_pressure_p
)
3516 int i
, max_regno
= max_reg_num ();
3518 ira_set_pseudo_classes (sched_verbose
? sched_dump
: NULL
);
3519 sched_regno_pressure_class
3520 = (enum reg_class
*) xmalloc (max_regno
* sizeof (enum reg_class
));
3521 for (i
= 0; i
< max_regno
; i
++)
3522 sched_regno_pressure_class
[i
]
3523 = (i
< FIRST_PSEUDO_REGISTER
3524 ? ira_pressure_class_translate
[REGNO_REG_CLASS (i
)]
3525 : ira_pressure_class_translate
[reg_allocno_class (i
)]);
3526 curr_reg_live
= BITMAP_ALLOC (NULL
);
3527 saved_reg_live
= BITMAP_ALLOC (NULL
);
3528 region_ref_regs
= BITMAP_ALLOC (NULL
);
3531 curr_state
= xmalloc (dfa_state_size
);
3534 static void haifa_init_only_bb (basic_block
, basic_block
);
3536 /* Initialize data structures specific to the Haifa scheduler. */
3538 haifa_sched_init (void)
3540 setup_sched_dump ();
3543 if (spec_info
!= NULL
)
3545 sched_deps_info
->use_deps_list
= 1;
3546 sched_deps_info
->generate_spec_deps
= 1;
3549 /* Initialize luids, dependency caches, target and h_i_d for the
3552 bb_vec_t bbs
= VEC_alloc (basic_block
, heap
, n_basic_blocks
);
3558 VEC_quick_push (basic_block
, bbs
, bb
);
3559 sched_init_luids (bbs
, NULL
, NULL
, NULL
);
3560 sched_deps_init (true);
3561 sched_extend_target ();
3562 haifa_init_h_i_d (bbs
, NULL
, NULL
, NULL
);
3564 VEC_free (basic_block
, heap
, bbs
);
3567 sched_init_only_bb
= haifa_init_only_bb
;
3568 sched_split_block
= sched_split_block_1
;
3569 sched_create_empty_bb
= sched_create_empty_bb_1
;
3570 haifa_recovery_bb_ever_added_p
= false;
3572 #ifdef ENABLE_CHECKING
3573 /* This is used preferably for finding bugs in check_cfg () itself.
3574 We must call sched_bbs_init () before check_cfg () because check_cfg ()
3575 assumes that the last insn in the last bb has a non-null successor. */
3579 nr_begin_data
= nr_begin_control
= nr_be_in_data
= nr_be_in_control
= 0;
3580 before_recovery
= 0;
3584 /* Finish work with the data specific to the Haifa scheduler. */
3586 haifa_sched_finish (void)
3588 sched_create_empty_bb
= NULL
;
3589 sched_split_block
= NULL
;
3590 sched_init_only_bb
= NULL
;
3592 if (spec_info
&& spec_info
->dump
)
3594 char c
= reload_completed
? 'a' : 'b';
3596 fprintf (spec_info
->dump
,
3597 ";; %s:\n", current_function_name ());
3599 fprintf (spec_info
->dump
,
3600 ";; Procedure %cr-begin-data-spec motions == %d\n",
3602 fprintf (spec_info
->dump
,
3603 ";; Procedure %cr-be-in-data-spec motions == %d\n",
3605 fprintf (spec_info
->dump
,
3606 ";; Procedure %cr-begin-control-spec motions == %d\n",
3607 c
, nr_begin_control
);
3608 fprintf (spec_info
->dump
,
3609 ";; Procedure %cr-be-in-control-spec motions == %d\n",
3610 c
, nr_be_in_control
);
3613 /* Finalize h_i_d, dependency caches, and luids for the whole
3614 function. Target will be finalized in md_global_finish (). */
3615 sched_deps_finish ();
3616 sched_finish_luids ();
3617 current_sched_info
= NULL
;
3621 /* Free global data used during insn scheduling. This function works with
3622 the common data shared between the schedulers. */
3627 haifa_finish_h_i_d ();
3628 if (sched_pressure_p
)
3630 free (sched_regno_pressure_class
);
3631 BITMAP_FREE (region_ref_regs
);
3632 BITMAP_FREE (saved_reg_live
);
3633 BITMAP_FREE (curr_reg_live
);
3637 if (targetm
.sched
.finish_global
)
3638 targetm
.sched
.finish_global (sched_dump
, sched_verbose
);
3640 end_alias_analysis ();
3642 regstat_free_calls_crossed ();
3646 #ifdef ENABLE_CHECKING
3647 /* After reload ia64 backend clobbers CFG, so can't check anything. */
3648 if (!reload_completed
)
3653 /* Fix INSN_TICKs of the instructions in the current block as well as
3654 INSN_TICKs of their dependents.
3655 HEAD and TAIL are the begin and the end of the current scheduled block. */
3657 fix_inter_tick (rtx head
, rtx tail
)
3659 /* Set of instructions with corrected INSN_TICK. */
3660 bitmap_head processed
;
3661 /* ??? It is doubtful if we should assume that cycle advance happens on
3662 basic block boundaries. Basically insns that are unconditionally ready
3663 on the start of the block are more preferable then those which have
3664 a one cycle dependency over insn from the previous block. */
3665 int next_clock
= clock_var
+ 1;
3667 bitmap_initialize (&processed
, 0);
3669 /* Iterates over scheduled instructions and fix their INSN_TICKs and
3670 INSN_TICKs of dependent instructions, so that INSN_TICKs are consistent
3671 across different blocks. */
3672 for (tail
= NEXT_INSN (tail
); head
!= tail
; head
= NEXT_INSN (head
))
3677 sd_iterator_def sd_it
;
3680 tick
= INSN_TICK (head
);
3681 gcc_assert (tick
>= MIN_TICK
);
3683 /* Fix INSN_TICK of instruction from just scheduled block. */
3684 if (bitmap_set_bit (&processed
, INSN_LUID (head
)))
3688 if (tick
< MIN_TICK
)
3691 INSN_TICK (head
) = tick
;
3694 FOR_EACH_DEP (head
, SD_LIST_RES_FORW
, sd_it
, dep
)
3698 next
= DEP_CON (dep
);
3699 tick
= INSN_TICK (next
);
3701 if (tick
!= INVALID_TICK
3702 /* If NEXT has its INSN_TICK calculated, fix it.
3703 If not - it will be properly calculated from
3704 scratch later in fix_tick_ready. */
3705 && bitmap_set_bit (&processed
, INSN_LUID (next
)))
3709 if (tick
< MIN_TICK
)
3712 if (tick
> INTER_TICK (next
))
3713 INTER_TICK (next
) = tick
;
3715 tick
= INTER_TICK (next
);
3717 INSN_TICK (next
) = tick
;
3722 bitmap_clear (&processed
);
3725 static int haifa_speculate_insn (rtx
, ds_t
, rtx
*);
3727 /* Check if NEXT is ready to be added to the ready or queue list.
3728 If "yes", add it to the proper list.
3730 -1 - is not ready yet,
3731 0 - added to the ready list,
3732 0 < N - queued for N cycles. */
3734 try_ready (rtx next
)
3738 ts
= &TODO_SPEC (next
);
3741 gcc_assert (!(old_ts
& ~(SPECULATIVE
| HARD_DEP
))
3742 && ((old_ts
& HARD_DEP
)
3743 || (old_ts
& SPECULATIVE
)));
3745 if (sd_lists_empty_p (next
, SD_LIST_BACK
))
3746 /* NEXT has all its dependencies resolved. */
3748 /* Remove HARD_DEP bit from NEXT's status. */
3751 if (current_sched_info
->flags
& DO_SPECULATION
)
3752 /* Remove all speculative bits from NEXT's status. */
3753 *ts
&= ~SPECULATIVE
;
3757 /* One of the NEXT's dependencies has been resolved.
3758 Recalculate NEXT's status. */
3760 *ts
&= ~SPECULATIVE
& ~HARD_DEP
;
3762 if (sd_lists_empty_p (next
, SD_LIST_HARD_BACK
))
3763 /* Now we've got NEXT with speculative deps only.
3764 1. Look at the deps to see what we have to do.
3765 2. Check if we can do 'todo'. */
3767 sd_iterator_def sd_it
;
3769 bool first_p
= true;
3771 FOR_EACH_DEP (next
, SD_LIST_BACK
, sd_it
, dep
)
3773 ds_t ds
= DEP_STATUS (dep
) & SPECULATIVE
;
3775 if (DEBUG_INSN_P (DEP_PRO (dep
))
3776 && !DEBUG_INSN_P (next
))
3786 *ts
= ds_merge (*ts
, ds
);
3789 if (ds_weak (*ts
) < spec_info
->data_weakness_cutoff
)
3790 /* Too few points. */
3791 *ts
= (*ts
& ~SPECULATIVE
) | HARD_DEP
;
3798 gcc_assert (*ts
== old_ts
3799 && QUEUE_INDEX (next
) == QUEUE_NOWHERE
);
3800 else if (current_sched_info
->new_ready
)
3801 *ts
= current_sched_info
->new_ready (next
, *ts
);
3803 /* * if !(old_ts & SPECULATIVE) (e.g. HARD_DEP or 0), then insn might
3804 have its original pattern or changed (speculative) one. This is due
3805 to changing ebb in region scheduling.
3806 * But if (old_ts & SPECULATIVE), then we are pretty sure that insn
3807 has speculative pattern.
3809 We can't assert (!(*ts & HARD_DEP) || *ts == old_ts) here because
3810 control-speculative NEXT could have been discarded by sched-rgn.c
3811 (the same case as when discarded by can_schedule_ready_p ()). */
3813 if ((*ts
& SPECULATIVE
)
3814 /* If (old_ts == *ts), then (old_ts & SPECULATIVE) and we don't
3815 need to change anything. */
3821 gcc_assert ((*ts
& SPECULATIVE
) && !(*ts
& ~SPECULATIVE
));
3823 res
= haifa_speculate_insn (next
, *ts
, &new_pat
);
3828 /* It would be nice to change DEP_STATUS of all dependences,
3829 which have ((DEP_STATUS & SPECULATIVE) == *ts) to HARD_DEP,
3830 so we won't reanalyze anything. */
3831 *ts
= (*ts
& ~SPECULATIVE
) | HARD_DEP
;
3835 /* We follow the rule, that every speculative insn
3836 has non-null ORIG_PAT. */
3837 if (!ORIG_PAT (next
))
3838 ORIG_PAT (next
) = PATTERN (next
);
3842 if (!ORIG_PAT (next
))
3843 /* If we gonna to overwrite the original pattern of insn,
3845 ORIG_PAT (next
) = PATTERN (next
);
3847 haifa_change_pattern (next
, new_pat
);
3855 /* We need to restore pattern only if (*ts == 0), because otherwise it is
3856 either correct (*ts & SPECULATIVE),
3857 or we simply don't care (*ts & HARD_DEP). */
3859 gcc_assert (!ORIG_PAT (next
)
3860 || !IS_SPECULATION_BRANCHY_CHECK_P (next
));
3864 /* We can't assert (QUEUE_INDEX (next) == QUEUE_NOWHERE) here because
3865 control-speculative NEXT could have been discarded by sched-rgn.c
3866 (the same case as when discarded by can_schedule_ready_p ()). */
3867 /*gcc_assert (QUEUE_INDEX (next) == QUEUE_NOWHERE);*/
3869 change_queue_index (next
, QUEUE_NOWHERE
);
3872 else if (!(*ts
& BEGIN_SPEC
) && ORIG_PAT (next
) && !IS_SPECULATION_CHECK_P (next
))
3873 /* We should change pattern of every previously speculative
3874 instruction - and we determine if NEXT was speculative by using
3875 ORIG_PAT field. Except one case - speculation checks have ORIG_PAT
3876 pat too, so skip them. */
3878 haifa_change_pattern (next
, ORIG_PAT (next
));
3879 ORIG_PAT (next
) = 0;
3882 if (sched_verbose
>= 2)
3884 int s
= TODO_SPEC (next
);
3886 fprintf (sched_dump
, ";;\t\tdependencies resolved: insn %s",
3887 (*current_sched_info
->print_insn
) (next
, 0));
3889 if (spec_info
&& spec_info
->dump
)
3892 fprintf (spec_info
->dump
, "; data-spec;");
3893 if (s
& BEGIN_CONTROL
)
3894 fprintf (spec_info
->dump
, "; control-spec;");
3895 if (s
& BE_IN_CONTROL
)
3896 fprintf (spec_info
->dump
, "; in-control-spec;");
3899 fprintf (sched_dump
, "\n");
3902 adjust_priority (next
);
3904 return fix_tick_ready (next
);
3907 /* Calculate INSN_TICK of NEXT and add it to either ready or queue list. */
3909 fix_tick_ready (rtx next
)
3913 if (!DEBUG_INSN_P (next
) && !sd_lists_empty_p (next
, SD_LIST_RES_BACK
))
3916 sd_iterator_def sd_it
;
3919 tick
= INSN_TICK (next
);
3920 /* if tick is not equal to INVALID_TICK, then update
3921 INSN_TICK of NEXT with the most recent resolved dependence
3922 cost. Otherwise, recalculate from scratch. */
3923 full_p
= (tick
== INVALID_TICK
);
3925 FOR_EACH_DEP (next
, SD_LIST_RES_BACK
, sd_it
, dep
)
3927 rtx pro
= DEP_PRO (dep
);
3930 gcc_assert (INSN_TICK (pro
) >= MIN_TICK
);
3932 tick1
= INSN_TICK (pro
) + dep_cost (dep
);
3943 INSN_TICK (next
) = tick
;
3945 delay
= tick
- clock_var
;
3946 if (delay
<= 0 || sched_pressure_p
)
3947 delay
= QUEUE_READY
;
3949 change_queue_index (next
, delay
);
3954 /* Move NEXT to the proper queue list with (DELAY >= 1),
3955 or add it to the ready list (DELAY == QUEUE_READY),
3956 or remove it from ready and queue lists at all (DELAY == QUEUE_NOWHERE). */
3958 change_queue_index (rtx next
, int delay
)
3960 int i
= QUEUE_INDEX (next
);
3962 gcc_assert (QUEUE_NOWHERE
<= delay
&& delay
<= max_insn_queue_index
3964 gcc_assert (i
!= QUEUE_SCHEDULED
);
3966 if ((delay
> 0 && NEXT_Q_AFTER (q_ptr
, delay
) == i
)
3967 || (delay
< 0 && delay
== i
))
3968 /* We have nothing to do. */
3971 /* Remove NEXT from wherever it is now. */
3972 if (i
== QUEUE_READY
)
3973 ready_remove_insn (next
);
3975 queue_remove (next
);
3977 /* Add it to the proper place. */
3978 if (delay
== QUEUE_READY
)
3979 ready_add (readyp
, next
, false);
3980 else if (delay
>= 1)
3981 queue_insn (next
, delay
, "change queue index");
3983 if (sched_verbose
>= 2)
3985 fprintf (sched_dump
, ";;\t\ttick updated: insn %s",
3986 (*current_sched_info
->print_insn
) (next
, 0));
3988 if (delay
== QUEUE_READY
)
3989 fprintf (sched_dump
, " into ready\n");
3990 else if (delay
>= 1)
3991 fprintf (sched_dump
, " into queue with cost=%d\n", delay
);
3993 fprintf (sched_dump
, " removed from ready or queue lists\n");
3997 static int sched_ready_n_insns
= -1;
3999 /* Initialize per region data structures. */
4001 sched_extend_ready_list (int new_sched_ready_n_insns
)
4005 if (sched_ready_n_insns
== -1)
4006 /* At the first call we need to initialize one more choice_stack
4010 sched_ready_n_insns
= 0;
4011 scheduled_insns
= VEC_alloc (rtx
, heap
, new_sched_ready_n_insns
);
4014 i
= sched_ready_n_insns
+ 1;
4016 ready
.veclen
= new_sched_ready_n_insns
+ issue_rate
;
4017 ready
.vec
= XRESIZEVEC (rtx
, ready
.vec
, ready
.veclen
);
4019 gcc_assert (new_sched_ready_n_insns
>= sched_ready_n_insns
);
4021 ready_try
= (char *) xrecalloc (ready_try
, new_sched_ready_n_insns
,
4022 sched_ready_n_insns
, sizeof (*ready_try
));
4024 /* We allocate +1 element to save initial state in the choice_stack[0]
4026 choice_stack
= XRESIZEVEC (struct choice_entry
, choice_stack
,
4027 new_sched_ready_n_insns
+ 1);
4029 for (; i
<= new_sched_ready_n_insns
; i
++)
4031 choice_stack
[i
].state
= xmalloc (dfa_state_size
);
4033 if (targetm
.sched
.first_cycle_multipass_init
)
4034 targetm
.sched
.first_cycle_multipass_init (&(choice_stack
[i
]
4038 sched_ready_n_insns
= new_sched_ready_n_insns
;
4041 /* Free per region data structures. */
4043 sched_finish_ready_list (void)
4054 for (i
= 0; i
<= sched_ready_n_insns
; i
++)
4056 if (targetm
.sched
.first_cycle_multipass_fini
)
4057 targetm
.sched
.first_cycle_multipass_fini (&(choice_stack
[i
]
4060 free (choice_stack
[i
].state
);
4062 free (choice_stack
);
4063 choice_stack
= NULL
;
4065 sched_ready_n_insns
= -1;
4069 haifa_luid_for_non_insn (rtx x
)
4071 gcc_assert (NOTE_P (x
) || LABEL_P (x
));
4076 /* Generates recovery code for INSN. */
4078 generate_recovery_code (rtx insn
)
4080 if (TODO_SPEC (insn
) & BEGIN_SPEC
)
4081 begin_speculative_block (insn
);
4083 /* Here we have insn with no dependencies to
4084 instructions other then CHECK_SPEC ones. */
4086 if (TODO_SPEC (insn
) & BE_IN_SPEC
)
4087 add_to_speculative_block (insn
);
4091 Tries to add speculative dependencies of type FS between instructions
4092 in deps_list L and TWIN. */
4094 process_insn_forw_deps_be_in_spec (rtx insn
, rtx twin
, ds_t fs
)
4096 sd_iterator_def sd_it
;
4099 FOR_EACH_DEP (insn
, SD_LIST_FORW
, sd_it
, dep
)
4104 consumer
= DEP_CON (dep
);
4106 ds
= DEP_STATUS (dep
);
4108 if (/* If we want to create speculative dep. */
4110 /* And we can do that because this is a true dep. */
4111 && (ds
& DEP_TYPES
) == DEP_TRUE
)
4113 gcc_assert (!(ds
& BE_IN_SPEC
));
4115 if (/* If this dep can be overcome with 'begin speculation'. */
4117 /* Then we have a choice: keep the dep 'begin speculative'
4118 or transform it into 'be in speculative'. */
4120 if (/* In try_ready we assert that if insn once became ready
4121 it can be removed from the ready (or queue) list only
4122 due to backend decision. Hence we can't let the
4123 probability of the speculative dep to decrease. */
4124 ds_weak (ds
) <= ds_weak (fs
))
4128 new_ds
= (ds
& ~BEGIN_SPEC
) | fs
;
4130 if (/* consumer can 'be in speculative'. */
4131 sched_insn_is_legitimate_for_speculation_p (consumer
,
4133 /* Transform it to be in speculative. */
4138 /* Mark the dep as 'be in speculative'. */
4143 dep_def _new_dep
, *new_dep
= &_new_dep
;
4145 init_dep_1 (new_dep
, twin
, consumer
, DEP_TYPE (dep
), ds
);
4146 sd_add_dep (new_dep
, false);
4151 /* Generates recovery code for BEGIN speculative INSN. */
4153 begin_speculative_block (rtx insn
)
4155 if (TODO_SPEC (insn
) & BEGIN_DATA
)
4157 if (TODO_SPEC (insn
) & BEGIN_CONTROL
)
4160 create_check_block_twin (insn
, false);
4162 TODO_SPEC (insn
) &= ~BEGIN_SPEC
;
4165 static void haifa_init_insn (rtx
);
4167 /* Generates recovery code for BE_IN speculative INSN. */
4169 add_to_speculative_block (rtx insn
)
4172 sd_iterator_def sd_it
;
4175 rtx_vec_t priorities_roots
;
4177 ts
= TODO_SPEC (insn
);
4178 gcc_assert (!(ts
& ~BE_IN_SPEC
));
4180 if (ts
& BE_IN_DATA
)
4182 if (ts
& BE_IN_CONTROL
)
4185 TODO_SPEC (insn
) &= ~BE_IN_SPEC
;
4186 gcc_assert (!TODO_SPEC (insn
));
4188 DONE_SPEC (insn
) |= ts
;
4190 /* First we convert all simple checks to branchy. */
4191 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
4192 sd_iterator_cond (&sd_it
, &dep
);)
4194 rtx check
= DEP_PRO (dep
);
4196 if (IS_SPECULATION_SIMPLE_CHECK_P (check
))
4198 create_check_block_twin (check
, true);
4200 /* Restart search. */
4201 sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
4204 /* Continue search. */
4205 sd_iterator_next (&sd_it
);
4208 priorities_roots
= NULL
;
4209 clear_priorities (insn
, &priorities_roots
);
4216 /* Get the first backward dependency of INSN. */
4217 sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
4218 if (!sd_iterator_cond (&sd_it
, &dep
))
4219 /* INSN has no backward dependencies left. */
4222 gcc_assert ((DEP_STATUS (dep
) & BEGIN_SPEC
) == 0
4223 && (DEP_STATUS (dep
) & BE_IN_SPEC
) != 0
4224 && (DEP_STATUS (dep
) & DEP_TYPES
) == DEP_TRUE
);
4226 check
= DEP_PRO (dep
);
4228 gcc_assert (!IS_SPECULATION_CHECK_P (check
) && !ORIG_PAT (check
)
4229 && QUEUE_INDEX (check
) == QUEUE_NOWHERE
);
4231 rec
= BLOCK_FOR_INSN (check
);
4233 twin
= emit_insn_before (copy_insn (PATTERN (insn
)), BB_END (rec
));
4234 haifa_init_insn (twin
);
4236 sd_copy_back_deps (twin
, insn
, true);
4238 if (sched_verbose
&& spec_info
->dump
)
4239 /* INSN_BB (insn) isn't determined for twin insns yet.
4240 So we can't use current_sched_info->print_insn. */
4241 fprintf (spec_info
->dump
, ";;\t\tGenerated twin insn : %d/rec%d\n",
4242 INSN_UID (twin
), rec
->index
);
4244 twins
= alloc_INSN_LIST (twin
, twins
);
4246 /* Add dependences between TWIN and all appropriate
4247 instructions from REC. */
4248 FOR_EACH_DEP (insn
, SD_LIST_SPEC_BACK
, sd_it
, dep
)
4250 rtx pro
= DEP_PRO (dep
);
4252 gcc_assert (DEP_TYPE (dep
) == REG_DEP_TRUE
);
4254 /* INSN might have dependencies from the instructions from
4255 several recovery blocks. At this iteration we process those
4256 producers that reside in REC. */
4257 if (BLOCK_FOR_INSN (pro
) == rec
)
4259 dep_def _new_dep
, *new_dep
= &_new_dep
;
4261 init_dep (new_dep
, pro
, twin
, REG_DEP_TRUE
);
4262 sd_add_dep (new_dep
, false);
4266 process_insn_forw_deps_be_in_spec (insn
, twin
, ts
);
4268 /* Remove all dependencies between INSN and insns in REC. */
4269 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
4270 sd_iterator_cond (&sd_it
, &dep
);)
4272 rtx pro
= DEP_PRO (dep
);
4274 if (BLOCK_FOR_INSN (pro
) == rec
)
4275 sd_delete_dep (sd_it
);
4277 sd_iterator_next (&sd_it
);
4281 /* We couldn't have added the dependencies between INSN and TWINS earlier
4282 because that would make TWINS appear in the INSN_BACK_DEPS (INSN). */
4287 twin
= XEXP (twins
, 0);
4290 dep_def _new_dep
, *new_dep
= &_new_dep
;
4292 init_dep (new_dep
, insn
, twin
, REG_DEP_OUTPUT
);
4293 sd_add_dep (new_dep
, false);
4296 twin
= XEXP (twins
, 1);
4297 free_INSN_LIST_node (twins
);
4301 calc_priorities (priorities_roots
);
4302 VEC_free (rtx
, heap
, priorities_roots
);
4305 /* Extends and fills with zeros (only the new part) array pointed to by P. */
4307 xrecalloc (void *p
, size_t new_nmemb
, size_t old_nmemb
, size_t size
)
4309 gcc_assert (new_nmemb
>= old_nmemb
);
4310 p
= XRESIZEVAR (void, p
, new_nmemb
* size
);
4311 memset (((char *) p
) + old_nmemb
* size
, 0, (new_nmemb
- old_nmemb
) * size
);
4316 Find fallthru edge from PRED. */
4318 find_fallthru_edge_from (basic_block pred
)
4323 succ
= pred
->next_bb
;
4324 gcc_assert (succ
->prev_bb
== pred
);
4326 if (EDGE_COUNT (pred
->succs
) <= EDGE_COUNT (succ
->preds
))
4328 e
= find_fallthru_edge (pred
->succs
);
4332 gcc_assert (e
->dest
== succ
);
4338 e
= find_fallthru_edge (succ
->preds
);
4342 gcc_assert (e
->src
== pred
);
4350 /* Extend per basic block data structures. */
4352 sched_extend_bb (void)
4356 /* The following is done to keep current_sched_info->next_tail non null. */
4357 insn
= BB_END (EXIT_BLOCK_PTR
->prev_bb
);
4358 if (NEXT_INSN (insn
) == 0
4361 /* Don't emit a NOTE if it would end up before a BARRIER. */
4362 && !BARRIER_P (NEXT_INSN (insn
))))
4364 rtx note
= emit_note_after (NOTE_INSN_DELETED
, insn
);
4365 /* Make insn appear outside BB. */
4366 set_block_for_insn (note
, NULL
);
4367 BB_END (EXIT_BLOCK_PTR
->prev_bb
) = insn
;
4371 /* Init per basic block data structures. */
4373 sched_init_bbs (void)
4378 /* Initialize BEFORE_RECOVERY variable. */
4380 init_before_recovery (basic_block
*before_recovery_ptr
)
4385 last
= EXIT_BLOCK_PTR
->prev_bb
;
4386 e
= find_fallthru_edge_from (last
);
4390 /* We create two basic blocks:
4391 1. Single instruction block is inserted right after E->SRC
4393 2. Empty block right before EXIT_BLOCK.
4394 Between these two blocks recovery blocks will be emitted. */
4396 basic_block single
, empty
;
4399 /* If the fallthrough edge to exit we've found is from the block we've
4400 created before, don't do anything more. */
4401 if (last
== after_recovery
)
4404 adding_bb_to_current_region_p
= false;
4406 single
= sched_create_empty_bb (last
);
4407 empty
= sched_create_empty_bb (single
);
4409 /* Add new blocks to the root loop. */
4410 if (current_loops
!= NULL
)
4412 add_bb_to_loop (single
, VEC_index (loop_p
, current_loops
->larray
, 0));
4413 add_bb_to_loop (empty
, VEC_index (loop_p
, current_loops
->larray
, 0));
4416 single
->count
= last
->count
;
4417 empty
->count
= last
->count
;
4418 single
->frequency
= last
->frequency
;
4419 empty
->frequency
= last
->frequency
;
4420 BB_COPY_PARTITION (single
, last
);
4421 BB_COPY_PARTITION (empty
, last
);
4423 redirect_edge_succ (e
, single
);
4424 make_single_succ_edge (single
, empty
, 0);
4425 make_single_succ_edge (empty
, EXIT_BLOCK_PTR
,
4426 EDGE_FALLTHRU
| EDGE_CAN_FALLTHRU
);
4428 label
= block_label (empty
);
4429 x
= emit_jump_insn_after (gen_jump (label
), BB_END (single
));
4430 JUMP_LABEL (x
) = label
;
4431 LABEL_NUSES (label
)++;
4432 haifa_init_insn (x
);
4434 emit_barrier_after (x
);
4436 sched_init_only_bb (empty
, NULL
);
4437 sched_init_only_bb (single
, NULL
);
4440 adding_bb_to_current_region_p
= true;
4441 before_recovery
= single
;
4442 after_recovery
= empty
;
4444 if (before_recovery_ptr
)
4445 *before_recovery_ptr
= before_recovery
;
4447 if (sched_verbose
>= 2 && spec_info
->dump
)
4448 fprintf (spec_info
->dump
,
4449 ";;\t\tFixed fallthru to EXIT : %d->>%d->%d->>EXIT\n",
4450 last
->index
, single
->index
, empty
->index
);
4453 before_recovery
= last
;
4456 /* Returns new recovery block. */
4458 sched_create_recovery_block (basic_block
*before_recovery_ptr
)
4464 haifa_recovery_bb_recently_added_p
= true;
4465 haifa_recovery_bb_ever_added_p
= true;
4467 init_before_recovery (before_recovery_ptr
);
4469 barrier
= get_last_bb_insn (before_recovery
);
4470 gcc_assert (BARRIER_P (barrier
));
4472 label
= emit_label_after (gen_label_rtx (), barrier
);
4474 rec
= create_basic_block (label
, label
, before_recovery
);
4476 /* A recovery block always ends with an unconditional jump. */
4477 emit_barrier_after (BB_END (rec
));
4479 if (BB_PARTITION (before_recovery
) != BB_UNPARTITIONED
)
4480 BB_SET_PARTITION (rec
, BB_COLD_PARTITION
);
4482 if (sched_verbose
&& spec_info
->dump
)
4483 fprintf (spec_info
->dump
, ";;\t\tGenerated recovery block rec%d\n",
4489 /* Create edges: FIRST_BB -> REC; FIRST_BB -> SECOND_BB; REC -> SECOND_BB
4490 and emit necessary jumps. */
4492 sched_create_recovery_edges (basic_block first_bb
, basic_block rec
,
4493 basic_block second_bb
)
4499 /* This is fixing of incoming edge. */
4500 /* ??? Which other flags should be specified? */
4501 if (BB_PARTITION (first_bb
) != BB_PARTITION (rec
))
4502 /* Partition type is the same, if it is "unpartitioned". */
4503 edge_flags
= EDGE_CROSSING
;
4507 make_edge (first_bb
, rec
, edge_flags
);
4508 label
= block_label (second_bb
);
4509 jump
= emit_jump_insn_after (gen_jump (label
), BB_END (rec
));
4510 JUMP_LABEL (jump
) = label
;
4511 LABEL_NUSES (label
)++;
4513 if (BB_PARTITION (second_bb
) != BB_PARTITION (rec
))
4514 /* Partition type is the same, if it is "unpartitioned". */
4516 /* Rewritten from cfgrtl.c. */
4517 if (flag_reorder_blocks_and_partition
4518 && targetm
.have_named_sections
)
4520 /* We don't need the same note for the check because
4521 any_condjump_p (check) == true. */
4522 add_reg_note (jump
, REG_CROSSING_JUMP
, NULL_RTX
);
4524 edge_flags
= EDGE_CROSSING
;
4529 make_single_succ_edge (rec
, second_bb
, edge_flags
);
4530 if (dom_info_available_p (CDI_DOMINATORS
))
4531 set_immediate_dominator (CDI_DOMINATORS
, rec
, first_bb
);
4534 /* This function creates recovery code for INSN. If MUTATE_P is nonzero,
4535 INSN is a simple check, that should be converted to branchy one. */
4537 create_check_block_twin (rtx insn
, bool mutate_p
)
4540 rtx label
, check
, twin
;
4542 sd_iterator_def sd_it
;
4544 dep_def _new_dep
, *new_dep
= &_new_dep
;
4547 gcc_assert (ORIG_PAT (insn
) != NULL_RTX
);
4550 todo_spec
= TODO_SPEC (insn
);
4553 gcc_assert (IS_SPECULATION_SIMPLE_CHECK_P (insn
)
4554 && (TODO_SPEC (insn
) & SPECULATIVE
) == 0);
4556 todo_spec
= CHECK_SPEC (insn
);
4559 todo_spec
&= SPECULATIVE
;
4561 /* Create recovery block. */
4562 if (mutate_p
|| targetm
.sched
.needs_block_p (todo_spec
))
4564 rec
= sched_create_recovery_block (NULL
);
4565 label
= BB_HEAD (rec
);
4569 rec
= EXIT_BLOCK_PTR
;
4574 check
= targetm
.sched
.gen_spec_check (insn
, label
, todo_spec
);
4576 if (rec
!= EXIT_BLOCK_PTR
)
4578 /* To have mem_reg alive at the beginning of second_bb,
4579 we emit check BEFORE insn, so insn after splitting
4580 insn will be at the beginning of second_bb, which will
4581 provide us with the correct life information. */
4582 check
= emit_jump_insn_before (check
, insn
);
4583 JUMP_LABEL (check
) = label
;
4584 LABEL_NUSES (label
)++;
4587 check
= emit_insn_before (check
, insn
);
4589 /* Extend data structures. */
4590 haifa_init_insn (check
);
4592 /* CHECK is being added to current region. Extend ready list. */
4593 gcc_assert (sched_ready_n_insns
!= -1);
4594 sched_extend_ready_list (sched_ready_n_insns
+ 1);
4596 if (current_sched_info
->add_remove_insn
)
4597 current_sched_info
->add_remove_insn (insn
, 0);
4599 RECOVERY_BLOCK (check
) = rec
;
4601 if (sched_verbose
&& spec_info
->dump
)
4602 fprintf (spec_info
->dump
, ";;\t\tGenerated check insn : %s\n",
4603 (*current_sched_info
->print_insn
) (check
, 0));
4605 gcc_assert (ORIG_PAT (insn
));
4607 /* Initialize TWIN (twin is a duplicate of original instruction
4608 in the recovery block). */
4609 if (rec
!= EXIT_BLOCK_PTR
)
4611 sd_iterator_def sd_it
;
4614 FOR_EACH_DEP (insn
, SD_LIST_RES_BACK
, sd_it
, dep
)
4615 if ((DEP_STATUS (dep
) & DEP_OUTPUT
) != 0)
4617 struct _dep _dep2
, *dep2
= &_dep2
;
4619 init_dep (dep2
, DEP_PRO (dep
), check
, REG_DEP_TRUE
);
4621 sd_add_dep (dep2
, true);
4624 twin
= emit_insn_after (ORIG_PAT (insn
), BB_END (rec
));
4625 haifa_init_insn (twin
);
4627 if (sched_verbose
&& spec_info
->dump
)
4628 /* INSN_BB (insn) isn't determined for twin insns yet.
4629 So we can't use current_sched_info->print_insn. */
4630 fprintf (spec_info
->dump
, ";;\t\tGenerated twin insn : %d/rec%d\n",
4631 INSN_UID (twin
), rec
->index
);
4635 ORIG_PAT (check
) = ORIG_PAT (insn
);
4636 HAS_INTERNAL_DEP (check
) = 1;
4638 /* ??? We probably should change all OUTPUT dependencies to
4642 /* Copy all resolved back dependencies of INSN to TWIN. This will
4643 provide correct value for INSN_TICK (TWIN). */
4644 sd_copy_back_deps (twin
, insn
, true);
4646 if (rec
!= EXIT_BLOCK_PTR
)
4647 /* In case of branchy check, fix CFG. */
4649 basic_block first_bb
, second_bb
;
4652 first_bb
= BLOCK_FOR_INSN (check
);
4653 second_bb
= sched_split_block (first_bb
, check
);
4655 sched_create_recovery_edges (first_bb
, rec
, second_bb
);
4657 sched_init_only_bb (second_bb
, first_bb
);
4658 sched_init_only_bb (rec
, EXIT_BLOCK_PTR
);
4660 jump
= BB_END (rec
);
4661 haifa_init_insn (jump
);
4664 /* Move backward dependences from INSN to CHECK and
4665 move forward dependences from INSN to TWIN. */
4667 /* First, create dependencies between INSN's producers and CHECK & TWIN. */
4668 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
4670 rtx pro
= DEP_PRO (dep
);
4673 /* If BEGIN_DATA: [insn ~~TRUE~~> producer]:
4674 check --TRUE--> producer ??? or ANTI ???
4675 twin --TRUE--> producer
4676 twin --ANTI--> check
4678 If BEGIN_CONTROL: [insn ~~ANTI~~> producer]:
4679 check --ANTI--> producer
4680 twin --ANTI--> producer
4681 twin --ANTI--> check
4683 If BE_IN_SPEC: [insn ~~TRUE~~> producer]:
4684 check ~~TRUE~~> producer
4685 twin ~~TRUE~~> producer
4686 twin --ANTI--> check */
4688 ds
= DEP_STATUS (dep
);
4690 if (ds
& BEGIN_SPEC
)
4692 gcc_assert (!mutate_p
);
4696 init_dep_1 (new_dep
, pro
, check
, DEP_TYPE (dep
), ds
);
4697 sd_add_dep (new_dep
, false);
4699 if (rec
!= EXIT_BLOCK_PTR
)
4701 DEP_CON (new_dep
) = twin
;
4702 sd_add_dep (new_dep
, false);
4706 /* Second, remove backward dependencies of INSN. */
4707 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
4708 sd_iterator_cond (&sd_it
, &dep
);)
4710 if ((DEP_STATUS (dep
) & BEGIN_SPEC
)
4712 /* We can delete this dep because we overcome it with
4713 BEGIN_SPECULATION. */
4714 sd_delete_dep (sd_it
);
4716 sd_iterator_next (&sd_it
);
4719 /* Future Speculations. Determine what BE_IN speculations will be like. */
4722 /* Fields (DONE_SPEC (x) & BEGIN_SPEC) and CHECK_SPEC (x) are set only
4725 gcc_assert (!DONE_SPEC (insn
));
4729 ds_t ts
= TODO_SPEC (insn
);
4731 DONE_SPEC (insn
) = ts
& BEGIN_SPEC
;
4732 CHECK_SPEC (check
) = ts
& BEGIN_SPEC
;
4734 /* Luckiness of future speculations solely depends upon initial
4735 BEGIN speculation. */
4736 if (ts
& BEGIN_DATA
)
4737 fs
= set_dep_weak (fs
, BE_IN_DATA
, get_dep_weak (ts
, BEGIN_DATA
));
4738 if (ts
& BEGIN_CONTROL
)
4739 fs
= set_dep_weak (fs
, BE_IN_CONTROL
,
4740 get_dep_weak (ts
, BEGIN_CONTROL
));
4743 CHECK_SPEC (check
) = CHECK_SPEC (insn
);
4745 /* Future speculations: call the helper. */
4746 process_insn_forw_deps_be_in_spec (insn
, twin
, fs
);
4748 if (rec
!= EXIT_BLOCK_PTR
)
4750 /* Which types of dependencies should we use here is,
4751 generally, machine-dependent question... But, for now,
4756 init_dep (new_dep
, insn
, check
, REG_DEP_TRUE
);
4757 sd_add_dep (new_dep
, false);
4759 init_dep (new_dep
, insn
, twin
, REG_DEP_OUTPUT
);
4760 sd_add_dep (new_dep
, false);
4764 if (spec_info
->dump
)
4765 fprintf (spec_info
->dump
, ";;\t\tRemoved simple check : %s\n",
4766 (*current_sched_info
->print_insn
) (insn
, 0));
4768 /* Remove all dependencies of the INSN. */
4770 sd_it
= sd_iterator_start (insn
, (SD_LIST_FORW
4772 | SD_LIST_RES_BACK
));
4773 while (sd_iterator_cond (&sd_it
, &dep
))
4774 sd_delete_dep (sd_it
);
4777 /* If former check (INSN) already was moved to the ready (or queue)
4778 list, add new check (CHECK) there too. */
4779 if (QUEUE_INDEX (insn
) != QUEUE_NOWHERE
)
4782 /* Remove old check from instruction stream and free its
4784 sched_remove_insn (insn
);
4787 init_dep (new_dep
, check
, twin
, REG_DEP_ANTI
);
4788 sd_add_dep (new_dep
, false);
4792 init_dep_1 (new_dep
, insn
, check
, REG_DEP_TRUE
, DEP_TRUE
| DEP_OUTPUT
);
4793 sd_add_dep (new_dep
, false);
4797 /* Fix priorities. If MUTATE_P is nonzero, this is not necessary,
4798 because it'll be done later in add_to_speculative_block. */
4800 rtx_vec_t priorities_roots
= NULL
;
4802 clear_priorities (twin
, &priorities_roots
);
4803 calc_priorities (priorities_roots
);
4804 VEC_free (rtx
, heap
, priorities_roots
);
4808 /* Removes dependency between instructions in the recovery block REC
4809 and usual region instructions. It keeps inner dependences so it
4810 won't be necessary to recompute them. */
4812 fix_recovery_deps (basic_block rec
)
4814 rtx note
, insn
, jump
, ready_list
= 0;
4815 bitmap_head in_ready
;
4818 bitmap_initialize (&in_ready
, 0);
4820 /* NOTE - a basic block note. */
4821 note
= NEXT_INSN (BB_HEAD (rec
));
4822 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
4823 insn
= BB_END (rec
);
4824 gcc_assert (JUMP_P (insn
));
4825 insn
= PREV_INSN (insn
);
4829 sd_iterator_def sd_it
;
4832 for (sd_it
= sd_iterator_start (insn
, SD_LIST_FORW
);
4833 sd_iterator_cond (&sd_it
, &dep
);)
4835 rtx consumer
= DEP_CON (dep
);
4837 if (BLOCK_FOR_INSN (consumer
) != rec
)
4839 sd_delete_dep (sd_it
);
4841 if (bitmap_set_bit (&in_ready
, INSN_LUID (consumer
)))
4842 ready_list
= alloc_INSN_LIST (consumer
, ready_list
);
4846 gcc_assert ((DEP_STATUS (dep
) & DEP_TYPES
) == DEP_TRUE
);
4848 sd_iterator_next (&sd_it
);
4852 insn
= PREV_INSN (insn
);
4854 while (insn
!= note
);
4856 bitmap_clear (&in_ready
);
4858 /* Try to add instructions to the ready or queue list. */
4859 for (link
= ready_list
; link
; link
= XEXP (link
, 1))
4860 try_ready (XEXP (link
, 0));
4861 free_INSN_LIST_list (&ready_list
);
4863 /* Fixing jump's dependences. */
4864 insn
= BB_HEAD (rec
);
4865 jump
= BB_END (rec
);
4867 gcc_assert (LABEL_P (insn
));
4868 insn
= NEXT_INSN (insn
);
4870 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
4871 add_jump_dependencies (insn
, jump
);
4874 /* Change pattern of INSN to NEW_PAT. */
4876 sched_change_pattern (rtx insn
, rtx new_pat
)
4880 t
= validate_change (insn
, &PATTERN (insn
), new_pat
, 0);
4882 dfa_clear_single_insn_cache (insn
);
4885 /* Change pattern of INSN to NEW_PAT. Invalidate cached haifa
4886 instruction data. */
4888 haifa_change_pattern (rtx insn
, rtx new_pat
)
4890 sched_change_pattern (insn
, new_pat
);
4892 /* Invalidate INSN_COST, so it'll be recalculated. */
4893 INSN_COST (insn
) = -1;
4894 /* Invalidate INSN_TICK, so it'll be recalculated. */
4895 INSN_TICK (insn
) = INVALID_TICK
;
4898 /* -1 - can't speculate,
4899 0 - for speculation with REQUEST mode it is OK to use
4900 current instruction pattern,
4901 1 - need to change pattern for *NEW_PAT to be speculative. */
4903 sched_speculate_insn (rtx insn
, ds_t request
, rtx
*new_pat
)
4905 gcc_assert (current_sched_info
->flags
& DO_SPECULATION
4906 && (request
& SPECULATIVE
)
4907 && sched_insn_is_legitimate_for_speculation_p (insn
, request
));
4909 if ((request
& spec_info
->mask
) != request
)
4912 if (request
& BE_IN_SPEC
4913 && !(request
& BEGIN_SPEC
))
4916 return targetm
.sched
.speculate_insn (insn
, request
, new_pat
);
4920 haifa_speculate_insn (rtx insn
, ds_t request
, rtx
*new_pat
)
4922 gcc_assert (sched_deps_info
->generate_spec_deps
4923 && !IS_SPECULATION_CHECK_P (insn
));
4925 if (HAS_INTERNAL_DEP (insn
)
4926 || SCHED_GROUP_P (insn
))
4929 return sched_speculate_insn (insn
, request
, new_pat
);
4932 /* Print some information about block BB, which starts with HEAD and
4933 ends with TAIL, before scheduling it.
4934 I is zero, if scheduler is about to start with the fresh ebb. */
4936 dump_new_block_header (int i
, basic_block bb
, rtx head
, rtx tail
)
4939 fprintf (sched_dump
,
4940 ";; ======================================================\n");
4942 fprintf (sched_dump
,
4943 ";; =====================ADVANCING TO=====================\n");
4944 fprintf (sched_dump
,
4945 ";; -- basic block %d from %d to %d -- %s reload\n",
4946 bb
->index
, INSN_UID (head
), INSN_UID (tail
),
4947 (reload_completed
? "after" : "before"));
4948 fprintf (sched_dump
,
4949 ";; ======================================================\n");
4950 fprintf (sched_dump
, "\n");
4953 /* Unlink basic block notes and labels and saves them, so they
4954 can be easily restored. We unlink basic block notes in EBB to
4955 provide back-compatibility with the previous code, as target backends
4956 assume, that there'll be only instructions between
4957 current_sched_info->{head and tail}. We restore these notes as soon
4959 FIRST (LAST) is the first (last) basic block in the ebb.
4960 NB: In usual case (FIRST == LAST) nothing is really done. */
4962 unlink_bb_notes (basic_block first
, basic_block last
)
4964 /* We DON'T unlink basic block notes of the first block in the ebb. */
4968 bb_header
= XNEWVEC (rtx
, last_basic_block
);
4970 /* Make a sentinel. */
4971 if (last
->next_bb
!= EXIT_BLOCK_PTR
)
4972 bb_header
[last
->next_bb
->index
] = 0;
4974 first
= first
->next_bb
;
4977 rtx prev
, label
, note
, next
;
4979 label
= BB_HEAD (last
);
4980 if (LABEL_P (label
))
4981 note
= NEXT_INSN (label
);
4984 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
4986 prev
= PREV_INSN (label
);
4987 next
= NEXT_INSN (note
);
4988 gcc_assert (prev
&& next
);
4990 NEXT_INSN (prev
) = next
;
4991 PREV_INSN (next
) = prev
;
4993 bb_header
[last
->index
] = label
;
4998 last
= last
->prev_bb
;
5003 /* Restore basic block notes.
5004 FIRST is the first basic block in the ebb. */
5006 restore_bb_notes (basic_block first
)
5011 /* We DON'T unlink basic block notes of the first block in the ebb. */
5012 first
= first
->next_bb
;
5013 /* Remember: FIRST is actually a second basic block in the ebb. */
5015 while (first
!= EXIT_BLOCK_PTR
5016 && bb_header
[first
->index
])
5018 rtx prev
, label
, note
, next
;
5020 label
= bb_header
[first
->index
];
5021 prev
= PREV_INSN (label
);
5022 next
= NEXT_INSN (prev
);
5024 if (LABEL_P (label
))
5025 note
= NEXT_INSN (label
);
5028 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
5030 bb_header
[first
->index
] = 0;
5032 NEXT_INSN (prev
) = label
;
5033 NEXT_INSN (note
) = next
;
5034 PREV_INSN (next
) = note
;
5036 first
= first
->next_bb
;
5044 Fix CFG after both in- and inter-block movement of
5045 control_flow_insn_p JUMP. */
5047 fix_jump_move (rtx jump
)
5049 basic_block bb
, jump_bb
, jump_bb_next
;
5051 bb
= BLOCK_FOR_INSN (PREV_INSN (jump
));
5052 jump_bb
= BLOCK_FOR_INSN (jump
);
5053 jump_bb_next
= jump_bb
->next_bb
;
5055 gcc_assert (common_sched_info
->sched_pass_id
== SCHED_EBB_PASS
5056 || IS_SPECULATION_BRANCHY_CHECK_P (jump
));
5058 if (!NOTE_INSN_BASIC_BLOCK_P (BB_END (jump_bb_next
)))
5059 /* if jump_bb_next is not empty. */
5060 BB_END (jump_bb
) = BB_END (jump_bb_next
);
5062 if (BB_END (bb
) != PREV_INSN (jump
))
5063 /* Then there are instruction after jump that should be placed
5065 BB_END (jump_bb_next
) = BB_END (bb
);
5067 /* Otherwise jump_bb_next is empty. */
5068 BB_END (jump_bb_next
) = NEXT_INSN (BB_HEAD (jump_bb_next
));
5070 /* To make assertion in move_insn happy. */
5071 BB_END (bb
) = PREV_INSN (jump
);
5073 update_bb_for_insn (jump_bb_next
);
5076 /* Fix CFG after interblock movement of control_flow_insn_p JUMP. */
5078 move_block_after_check (rtx jump
)
5080 basic_block bb
, jump_bb
, jump_bb_next
;
5083 bb
= BLOCK_FOR_INSN (PREV_INSN (jump
));
5084 jump_bb
= BLOCK_FOR_INSN (jump
);
5085 jump_bb_next
= jump_bb
->next_bb
;
5087 update_bb_for_insn (jump_bb
);
5089 gcc_assert (IS_SPECULATION_CHECK_P (jump
)
5090 || IS_SPECULATION_CHECK_P (BB_END (jump_bb_next
)));
5092 unlink_block (jump_bb_next
);
5093 link_block (jump_bb_next
, bb
);
5097 move_succs (&(jump_bb
->succs
), bb
);
5098 move_succs (&(jump_bb_next
->succs
), jump_bb
);
5099 move_succs (&t
, jump_bb_next
);
5101 df_mark_solutions_dirty ();
5103 common_sched_info
->fix_recovery_cfg
5104 (bb
->index
, jump_bb
->index
, jump_bb_next
->index
);
5107 /* Helper function for move_block_after_check.
5108 This functions attaches edge vector pointed to by SUCCSP to
5111 move_succs (VEC(edge
,gc
) **succsp
, basic_block to
)
5116 gcc_assert (to
->succs
== 0);
5118 to
->succs
= *succsp
;
5120 FOR_EACH_EDGE (e
, ei
, to
->succs
)
5126 /* Remove INSN from the instruction stream.
5127 INSN should have any dependencies. */
5129 sched_remove_insn (rtx insn
)
5131 sd_finish_insn (insn
);
5133 change_queue_index (insn
, QUEUE_NOWHERE
);
5134 current_sched_info
->add_remove_insn (insn
, 1);
5138 /* Clear priorities of all instructions, that are forward dependent on INSN.
5139 Store in vector pointed to by ROOTS_PTR insns on which priority () should
5140 be invoked to initialize all cleared priorities. */
5142 clear_priorities (rtx insn
, rtx_vec_t
*roots_ptr
)
5144 sd_iterator_def sd_it
;
5146 bool insn_is_root_p
= true;
5148 gcc_assert (QUEUE_INDEX (insn
) != QUEUE_SCHEDULED
);
5150 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
5152 rtx pro
= DEP_PRO (dep
);
5154 if (INSN_PRIORITY_STATUS (pro
) >= 0
5155 && QUEUE_INDEX (insn
) != QUEUE_SCHEDULED
)
5157 /* If DEP doesn't contribute to priority then INSN itself should
5158 be added to priority roots. */
5159 if (contributes_to_priority_p (dep
))
5160 insn_is_root_p
= false;
5162 INSN_PRIORITY_STATUS (pro
) = -1;
5163 clear_priorities (pro
, roots_ptr
);
5168 VEC_safe_push (rtx
, heap
, *roots_ptr
, insn
);
5171 /* Recompute priorities of instructions, whose priorities might have been
5172 changed. ROOTS is a vector of instructions whose priority computation will
5173 trigger initialization of all cleared priorities. */
5175 calc_priorities (rtx_vec_t roots
)
5180 FOR_EACH_VEC_ELT (rtx
, roots
, i
, insn
)
5185 /* Add dependences between JUMP and other instructions in the recovery
5186 block. INSN is the first insn the recovery block. */
5188 add_jump_dependencies (rtx insn
, rtx jump
)
5192 insn
= NEXT_INSN (insn
);
5196 if (dep_list_size (insn
) == 0)
5198 dep_def _new_dep
, *new_dep
= &_new_dep
;
5200 init_dep (new_dep
, insn
, jump
, REG_DEP_ANTI
);
5201 sd_add_dep (new_dep
, false);
5206 gcc_assert (!sd_lists_empty_p (jump
, SD_LIST_BACK
));
5209 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
5211 bb_note (basic_block bb
)
5215 note
= BB_HEAD (bb
);
5217 note
= NEXT_INSN (note
);
5219 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
5223 #ifdef ENABLE_CHECKING
5224 /* Helper function for check_cfg.
5225 Return nonzero, if edge vector pointed to by EL has edge with TYPE in
5228 has_edge_p (VEC(edge
,gc
) *el
, int type
)
5233 FOR_EACH_EDGE (e
, ei
, el
)
5234 if (e
->flags
& type
)
5239 /* Search back, starting at INSN, for an insn that is not a
5240 NOTE_INSN_VAR_LOCATION. Don't search beyond HEAD, and return it if
5241 no such insn can be found. */
5243 prev_non_location_insn (rtx insn
, rtx head
)
5245 while (insn
!= head
&& NOTE_P (insn
)
5246 && NOTE_KIND (insn
) == NOTE_INSN_VAR_LOCATION
)
5247 insn
= PREV_INSN (insn
);
5252 /* Check few properties of CFG between HEAD and TAIL.
5253 If HEAD (TAIL) is NULL check from the beginning (till the end) of the
5254 instruction stream. */
5256 check_cfg (rtx head
, rtx tail
)
5260 int not_first
= 0, not_last
;
5263 head
= get_insns ();
5265 tail
= get_last_insn ();
5266 next_tail
= NEXT_INSN (tail
);
5270 not_last
= head
!= tail
;
5273 gcc_assert (NEXT_INSN (PREV_INSN (head
)) == head
);
5275 gcc_assert (PREV_INSN (NEXT_INSN (head
)) == head
);
5278 || (NOTE_INSN_BASIC_BLOCK_P (head
)
5280 || (not_first
&& !LABEL_P (PREV_INSN (head
))))))
5282 gcc_assert (bb
== 0);
5283 bb
= BLOCK_FOR_INSN (head
);
5285 gcc_assert (BB_HEAD (bb
) == head
);
5287 /* This is the case of jump table. See inside_basic_block_p (). */
5288 gcc_assert (LABEL_P (head
) && !inside_basic_block_p (head
));
5293 gcc_assert (!inside_basic_block_p (head
));
5294 head
= NEXT_INSN (head
);
5298 gcc_assert (inside_basic_block_p (head
)
5300 gcc_assert (BLOCK_FOR_INSN (head
) == bb
);
5304 head
= NEXT_INSN (head
);
5305 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (head
));
5309 if (control_flow_insn_p (head
))
5311 gcc_assert (prev_non_location_insn (BB_END (bb
), head
)
5314 if (any_uncondjump_p (head
))
5315 gcc_assert (EDGE_COUNT (bb
->succs
) == 1
5316 && BARRIER_P (NEXT_INSN (head
)));
5317 else if (any_condjump_p (head
))
5318 gcc_assert (/* Usual case. */
5319 (EDGE_COUNT (bb
->succs
) > 1
5320 && !BARRIER_P (NEXT_INSN (head
)))
5321 /* Or jump to the next instruction. */
5322 || (EDGE_COUNT (bb
->succs
) == 1
5323 && (BB_HEAD (EDGE_I (bb
->succs
, 0)->dest
)
5324 == JUMP_LABEL (head
))));
5326 if (BB_END (bb
) == head
)
5328 if (EDGE_COUNT (bb
->succs
) > 1)
5329 gcc_assert (control_flow_insn_p (prev_non_location_insn
5330 (head
, BB_HEAD (bb
)))
5331 || has_edge_p (bb
->succs
, EDGE_COMPLEX
));
5335 head
= NEXT_INSN (head
);
5341 while (head
!= next_tail
);
5343 gcc_assert (bb
== 0);
5346 #endif /* ENABLE_CHECKING */
5348 /* Extend per basic block data structures. */
5352 if (sched_scan_info
->extend_bb
)
5353 sched_scan_info
->extend_bb ();
5356 /* Init data for BB. */
5358 init_bb (basic_block bb
)
5360 if (sched_scan_info
->init_bb
)
5361 sched_scan_info
->init_bb (bb
);
5364 /* Extend per insn data structures. */
5368 if (sched_scan_info
->extend_insn
)
5369 sched_scan_info
->extend_insn ();
5372 /* Init data structures for INSN. */
5374 init_insn (rtx insn
)
5376 if (sched_scan_info
->init_insn
)
5377 sched_scan_info
->init_insn (insn
);
5380 /* Init all insns in BB. */
5382 init_insns_in_bb (basic_block bb
)
5386 FOR_BB_INSNS (bb
, insn
)
5390 /* A driver function to add a set of basic blocks (BBS),
5391 a single basic block (BB), a set of insns (INSNS) or a single insn (INSN)
5392 to the scheduling region. */
5394 sched_scan (const struct sched_scan_info_def
*ssi
,
5395 bb_vec_t bbs
, basic_block bb
, insn_vec_t insns
, rtx insn
)
5397 sched_scan_info
= ssi
;
5399 if (bbs
!= NULL
|| bb
!= NULL
)
5408 FOR_EACH_VEC_ELT (basic_block
, bbs
, i
, x
)
5423 FOR_EACH_VEC_ELT (basic_block
, bbs
, i
, x
)
5424 init_insns_in_bb (x
);
5428 init_insns_in_bb (bb
);
5435 FOR_EACH_VEC_ELT (rtx
, insns
, i
, x
)
5444 /* Extend data structures for logical insn UID. */
5446 luids_extend_insn (void)
5448 int new_luids_max_uid
= get_max_uid () + 1;
5450 VEC_safe_grow_cleared (int, heap
, sched_luids
, new_luids_max_uid
);
5453 /* Initialize LUID for INSN. */
5455 luids_init_insn (rtx insn
)
5457 int i
= INSN_P (insn
) ? 1 : common_sched_info
->luid_for_non_insn (insn
);
5462 luid
= sched_max_luid
;
5463 sched_max_luid
+= i
;
5468 SET_INSN_LUID (insn
, luid
);
5471 /* Initialize luids for BBS, BB, INSNS and INSN.
5472 The hook common_sched_info->luid_for_non_insn () is used to determine
5473 if notes, labels, etc. need luids. */
5475 sched_init_luids (bb_vec_t bbs
, basic_block bb
, insn_vec_t insns
, rtx insn
)
5477 const struct sched_scan_info_def ssi
=
5479 NULL
, /* extend_bb */
5481 luids_extend_insn
, /* extend_insn */
5482 luids_init_insn
/* init_insn */
5485 sched_scan (&ssi
, bbs
, bb
, insns
, insn
);
5490 sched_finish_luids (void)
5492 VEC_free (int, heap
, sched_luids
);
5496 /* Return logical uid of INSN. Helpful while debugging. */
5498 insn_luid (rtx insn
)
5500 return INSN_LUID (insn
);
5503 /* Extend per insn data in the target. */
5505 sched_extend_target (void)
5507 if (targetm
.sched
.h_i_d_extended
)
5508 targetm
.sched
.h_i_d_extended ();
5511 /* Extend global scheduler structures (those, that live across calls to
5512 schedule_block) to include information about just emitted INSN. */
5516 int reserve
= (get_max_uid () + 1
5517 - VEC_length (haifa_insn_data_def
, h_i_d
));
5519 && ! VEC_space (haifa_insn_data_def
, h_i_d
, reserve
))
5521 VEC_safe_grow_cleared (haifa_insn_data_def
, heap
, h_i_d
,
5522 3 * get_max_uid () / 2);
5523 sched_extend_target ();
5527 /* Initialize h_i_d entry of the INSN with default values.
5528 Values, that are not explicitly initialized here, hold zero. */
5530 init_h_i_d (rtx insn
)
5532 if (INSN_LUID (insn
) > 0)
5534 INSN_COST (insn
) = -1;
5535 QUEUE_INDEX (insn
) = QUEUE_NOWHERE
;
5536 INSN_TICK (insn
) = INVALID_TICK
;
5537 INTER_TICK (insn
) = INVALID_TICK
;
5538 TODO_SPEC (insn
) = HARD_DEP
;
5542 /* Initialize haifa_insn_data for BBS, BB, INSNS and INSN. */
5544 haifa_init_h_i_d (bb_vec_t bbs
, basic_block bb
, insn_vec_t insns
, rtx insn
)
5546 const struct sched_scan_info_def ssi
=
5548 NULL
, /* extend_bb */
5550 extend_h_i_d
, /* extend_insn */
5551 init_h_i_d
/* init_insn */
5554 sched_scan (&ssi
, bbs
, bb
, insns
, insn
);
5557 /* Finalize haifa_insn_data. */
5559 haifa_finish_h_i_d (void)
5562 haifa_insn_data_t data
;
5563 struct reg_use_data
*use
, *next
;
5565 FOR_EACH_VEC_ELT (haifa_insn_data_def
, h_i_d
, i
, data
)
5567 if (data
->reg_pressure
!= NULL
)
5568 free (data
->reg_pressure
);
5569 for (use
= data
->reg_use_list
; use
!= NULL
; use
= next
)
5571 next
= use
->next_insn_use
;
5575 VEC_free (haifa_insn_data_def
, heap
, h_i_d
);
5578 /* Init data for the new insn INSN. */
5580 haifa_init_insn (rtx insn
)
5582 gcc_assert (insn
!= NULL
);
5584 sched_init_luids (NULL
, NULL
, NULL
, insn
);
5585 sched_extend_target ();
5586 sched_deps_init (false);
5587 haifa_init_h_i_d (NULL
, NULL
, NULL
, insn
);
5589 if (adding_bb_to_current_region_p
)
5591 sd_init_insn (insn
);
5593 /* Extend dependency caches by one element. */
5594 extend_dependency_caches (1, false);
5598 /* Init data for the new basic block BB which comes after AFTER. */
5600 haifa_init_only_bb (basic_block bb
, basic_block after
)
5602 gcc_assert (bb
!= NULL
);
5606 if (common_sched_info
->add_block
)
5607 /* This changes only data structures of the front-end. */
5608 common_sched_info
->add_block (bb
, after
);
5611 /* A generic version of sched_split_block (). */
5613 sched_split_block_1 (basic_block first_bb
, rtx after
)
5617 e
= split_block (first_bb
, after
);
5618 gcc_assert (e
->src
== first_bb
);
5620 /* sched_split_block emits note if *check == BB_END. Probably it
5621 is better to rip that note off. */
5626 /* A generic version of sched_create_empty_bb (). */
5628 sched_create_empty_bb_1 (basic_block after
)
5630 return create_empty_bb (after
);
5633 /* Insert PAT as an INSN into the schedule and update the necessary data
5634 structures to account for it. */
5636 sched_emit_insn (rtx pat
)
5638 rtx insn
= emit_insn_after (pat
, last_scheduled_insn
);
5639 last_scheduled_insn
= insn
;
5640 haifa_init_insn (insn
);
5644 /* This function returns a candidate satisfying dispatch constraints from
5648 ready_remove_first_dispatch (struct ready_list
*ready
)
5651 rtx insn
= ready_element (ready
, 0);
5653 if (ready
->n_ready
== 1
5654 || INSN_CODE (insn
) < 0
5656 || !active_insn_p (insn
)
5657 || targetm
.sched
.dispatch (insn
, FITS_DISPATCH_WINDOW
))
5658 return ready_remove_first (ready
);
5660 for (i
= 1; i
< ready
->n_ready
; i
++)
5662 insn
= ready_element (ready
, i
);
5664 if (INSN_CODE (insn
) < 0
5666 || !active_insn_p (insn
))
5669 if (targetm
.sched
.dispatch (insn
, FITS_DISPATCH_WINDOW
))
5671 /* Return ith element of ready. */
5672 insn
= ready_remove (ready
, i
);
5677 if (targetm
.sched
.dispatch (NULL_RTX
, DISPATCH_VIOLATION
))
5678 return ready_remove_first (ready
);
5680 for (i
= 1; i
< ready
->n_ready
; i
++)
5682 insn
= ready_element (ready
, i
);
5684 if (INSN_CODE (insn
) < 0
5686 || !active_insn_p (insn
))
5689 /* Return i-th element of ready. */
5690 if (targetm
.sched
.dispatch (insn
, IS_CMP
))
5691 return ready_remove (ready
, i
);
5694 return ready_remove_first (ready
);
5697 /* Get number of ready insn in the ready list. */
5700 number_in_ready (void)
5702 return ready
.n_ready
;
5705 /* Get number of ready's in the ready list. */
5708 get_ready_element (int i
)
5710 return ready_element (&ready
, i
);
5713 #endif /* INSN_SCHEDULING */