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
4 Free Software Foundation, Inc.
5 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
6 and currently maintained by, Jim Wilson (wilson@cygnus.com)
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
24 /* Instruction scheduling pass. This file, along with sched-deps.c,
25 contains the generic parts. The actual entry point is found for
26 the normal instruction scheduling pass is found in sched-rgn.c.
28 We compute insn priorities based on data dependencies. Flow
29 analysis only creates a fraction of the data-dependencies we must
30 observe: namely, only those dependencies which the combiner can be
31 expected to use. For this pass, we must therefore create the
32 remaining dependencies we need to observe: register dependencies,
33 memory dependencies, dependencies to keep function calls in order,
34 and the dependence between a conditional branch and the setting of
35 condition codes are all dealt with here.
37 The scheduler first traverses the data flow graph, starting with
38 the last instruction, and proceeding to the first, assigning values
39 to insn_priority as it goes. This sorts the instructions
40 topologically by data dependence.
42 Once priorities have been established, we order the insns using
43 list scheduling. This works as follows: starting with a list of
44 all the ready insns, and sorted according to priority number, we
45 schedule the insn from the end of the list by placing its
46 predecessors in the list according to their priority order. We
47 consider this insn scheduled by setting the pointer to the "end" of
48 the list to point to the previous insn. When an insn has no
49 predecessors, we either queue it until sufficient time has elapsed
50 or add it to the ready list. As the instructions are scheduled or
51 when stalls are introduced, the queue advances and dumps insns into
52 the ready list. When all insns down to the lowest priority have
53 been scheduled, the critical path of the basic block has been made
54 as short as possible. The remaining insns are then scheduled in
57 The following list shows the order in which we want to break ties
58 among insns in the ready list:
60 1. choose insn with the longest path to end of bb, ties
62 2. choose insn with least contribution to register pressure,
64 3. prefer in-block upon interblock motion, ties broken by
65 4. prefer useful upon speculative motion, ties broken by
66 5. choose insn with largest control flow probability, ties
68 6. choose insn with the least dependences upon the previously
69 scheduled insn, or finally
70 7 choose the insn which has the most insns dependent on it.
71 8. choose insn with lowest UID.
73 Memory references complicate matters. Only if we can be certain
74 that memory references are not part of the data dependency graph
75 (via true, anti, or output dependence), can we move operations past
76 memory references. To first approximation, reads can be done
77 independently, while writes introduce dependencies. Better
78 approximations will yield fewer dependencies.
80 Before reload, an extended analysis of interblock data dependences
81 is required for interblock scheduling. This is performed in
82 compute_block_backward_dependences ().
84 Dependencies set up by memory references are treated in exactly the
85 same way as other dependencies, by using insn backward dependences
86 INSN_BACK_DEPS. INSN_BACK_DEPS are translated into forward dependences
87 INSN_FORW_DEPS the purpose of forward list scheduling.
89 Having optimized the critical path, we may have also unduly
90 extended the lifetimes of some registers. If an operation requires
91 that constants be loaded into registers, it is certainly desirable
92 to load those constants as early as necessary, but no earlier.
93 I.e., it will not do to load up a bunch of registers at the
94 beginning of a basic block only to use them at the end, if they
95 could be loaded later, since this may result in excessive register
98 Note that since branches are never in basic blocks, but only end
99 basic blocks, this pass will not move branches. But that is ok,
100 since we can use GNU's delayed branch scheduling pass to take care
103 Also note that no further optimizations based on algebraic
104 identities are performed, so this pass would be a good one to
105 perform instruction splitting, such as breaking up a multiply
106 instruction into shifts and adds where that is profitable.
108 Given the memory aliasing analysis that this pass should perform,
109 it should be possible to remove redundant stores to memory, and to
110 load values from registers instead of hitting memory.
112 Before reload, speculative insns are moved only if a 'proof' exists
113 that no exception will be caused by this, and if no live registers
114 exist that inhibit the motion (live registers constraints are not
115 represented by data dependence edges).
117 This pass must update information that subsequent passes expect to
118 be correct. Namely: reg_n_refs, reg_n_sets, reg_n_deaths,
119 reg_n_calls_crossed, and reg_live_length. Also, BB_HEAD, BB_END.
121 The information in the line number notes is carefully retained by
122 this pass. Notes that refer to the starting and ending of
123 exception regions are also carefully retained by this pass. All
124 other NOTE insns are grouped in their same relative order at the
125 beginning of basic blocks and regions that have been scheduled. */
129 #include "coretypes.h"
134 #include "hard-reg-set.h"
136 #include "function.h"
138 #include "insn-config.h"
139 #include "insn-attr.h"
143 #include "sched-int.h"
151 #ifdef INSN_SCHEDULING
153 /* issue_rate is the number of insns that can be scheduled in the same
154 machine cycle. It can be defined in the config/mach/mach.h file,
155 otherwise we set it to 1. */
159 /* sched-verbose controls the amount of debugging output the
160 scheduler prints. It is controlled by -fsched-verbose=N:
161 N>0 and no -DSR : the output is directed to stderr.
162 N>=10 will direct the printouts to stderr (regardless of -dSR).
164 N=2: bb's probabilities, detailed ready list info, unit/insn info.
165 N=3: rtl at abort point, control-flow, regions info.
166 N=5: dependences info. */
168 static int sched_verbose_param = 0;
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 /* fix_sched_param() is called from toplev.c upon detection
176 of the -fsched-verbose=N option. */
179 fix_sched_param (const char *param, const char *val)
181 if (!strcmp (param, "verbose"))
182 sched_verbose_param = atoi (val);
184 warning (0, "fix_sched_param: unknown param: %s", param);
187 /* This is a placeholder for the scheduler parameters common
188 to all schedulers. */
189 struct common_sched_info_def *common_sched_info;
191 #define INSN_TICK(INSN) (HID (INSN)->tick)
192 #define INTER_TICK(INSN) (HID (INSN)->inter_tick)
194 /* If INSN_TICK of an instruction is equal to INVALID_TICK,
195 then it should be recalculated from scratch. */
196 #define INVALID_TICK (-(max_insn_queue_index + 1))
197 /* The minimal value of the INSN_TICK of an instruction. */
198 #define MIN_TICK (-max_insn_queue_index)
200 /* Issue points are used to distinguish between instructions in max_issue ().
201 For now, all instructions are equally good. */
202 #define ISSUE_POINTS(INSN) 1
204 /* List of important notes we must keep around. This is a pointer to the
205 last element in the list. */
208 static struct spec_info_def spec_info_var;
209 /* Description of the speculative part of the scheduling.
210 If NULL - no speculation. */
211 spec_info_t spec_info = NULL;
213 /* True, if recovery block was added during scheduling of current block.
214 Used to determine, if we need to fix INSN_TICKs. */
215 static bool haifa_recovery_bb_recently_added_p;
217 /* True, if recovery block was added during this scheduling pass.
218 Used to determine if we should have empty memory pools of dependencies
219 after finishing current region. */
220 bool haifa_recovery_bb_ever_added_p;
222 /* Counters of different types of speculative instructions. */
223 static int nr_begin_data, nr_be_in_data, nr_begin_control, nr_be_in_control;
225 /* Array used in {unlink, restore}_bb_notes. */
226 static rtx *bb_header = 0;
228 /* Basic block after which recovery blocks will be created. */
229 static basic_block before_recovery;
231 /* Basic block just before the EXIT_BLOCK and after recovery, if we have
233 basic_block after_recovery;
235 /* FALSE if we add bb to another region, so we don't need to initialize it. */
236 bool adding_bb_to_current_region_p = true;
240 /* An instruction is ready to be scheduled when all insns preceding it
241 have already been scheduled. It is important to ensure that all
242 insns which use its result will not be executed until its result
243 has been computed. An insn is maintained in one of four structures:
245 (P) the "Pending" set of insns which cannot be scheduled until
246 their dependencies have been satisfied.
247 (Q) the "Queued" set of insns that can be scheduled when sufficient
249 (R) the "Ready" list of unscheduled, uncommitted insns.
250 (S) the "Scheduled" list of insns.
252 Initially, all insns are either "Pending" or "Ready" depending on
253 whether their dependencies are satisfied.
255 Insns move from the "Ready" list to the "Scheduled" list as they
256 are committed to the schedule. As this occurs, the insns in the
257 "Pending" list have their dependencies satisfied and move to either
258 the "Ready" list or the "Queued" set depending on whether
259 sufficient time has passed to make them ready. As time passes,
260 insns move from the "Queued" set to the "Ready" list.
262 The "Pending" list (P) are the insns in the INSN_FORW_DEPS of the
263 unscheduled insns, i.e., those that are ready, queued, and pending.
264 The "Queued" set (Q) is implemented by the variable `insn_queue'.
265 The "Ready" list (R) is implemented by the variables `ready' and
267 The "Scheduled" list (S) is the new insn chain built by this pass.
269 The transition (R->S) is implemented in the scheduling loop in
270 `schedule_block' when the best insn to schedule is chosen.
271 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
272 insns move from the ready list to the scheduled list.
273 The transition (Q->R) is implemented in 'queue_to_insn' as time
274 passes or stalls are introduced. */
276 /* Implement a circular buffer to delay instructions until sufficient
277 time has passed. For the new pipeline description interface,
278 MAX_INSN_QUEUE_INDEX is a power of two minus one which is not less
279 than maximal time of instruction execution computed by genattr.c on
280 the base maximal time of functional unit reservations and getting a
281 result. This is the longest time an insn may be queued. */
283 static rtx *insn_queue;
284 static int q_ptr = 0;
285 static int q_size = 0;
286 #define NEXT_Q(X) (((X)+1) & max_insn_queue_index)
287 #define NEXT_Q_AFTER(X, C) (((X)+C) & max_insn_queue_index)
289 #define QUEUE_SCHEDULED (-3)
290 #define QUEUE_NOWHERE (-2)
291 #define QUEUE_READY (-1)
292 /* QUEUE_SCHEDULED - INSN is scheduled.
293 QUEUE_NOWHERE - INSN isn't scheduled yet and is neither in
295 QUEUE_READY - INSN is in ready list.
296 N >= 0 - INSN queued for X [where NEXT_Q_AFTER (q_ptr, X) == N] cycles. */
298 #define QUEUE_INDEX(INSN) (HID (INSN)->queue_index)
300 /* The following variable value refers for all current and future
301 reservations of the processor units. */
304 /* The following variable value is size of memory representing all
305 current and future reservations of the processor units. */
306 size_t dfa_state_size;
308 /* The following array is used to find the best insn from ready when
309 the automaton pipeline interface is used. */
310 char *ready_try = NULL;
312 /* The ready list. */
313 struct ready_list ready = {NULL, 0, 0, 0};
315 /* The pointer to the ready list (to be removed). */
316 static struct ready_list *readyp = &ready;
318 /* Scheduling clock. */
319 static int clock_var;
321 static int may_trap_exp (const_rtx, int);
323 /* Nonzero iff the address is comprised from at most 1 register. */
324 #define CONST_BASED_ADDRESS_P(x) \
326 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
327 || (GET_CODE (x) == LO_SUM)) \
328 && (CONSTANT_P (XEXP (x, 0)) \
329 || CONSTANT_P (XEXP (x, 1)))))
331 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
332 as found by analyzing insn's expression. */
335 static int haifa_luid_for_non_insn (rtx x);
337 /* Haifa version of sched_info hooks common to all headers. */
338 const struct common_sched_info_def haifa_common_sched_info =
340 NULL, /* fix_recovery_cfg */
341 NULL, /* add_block */
342 NULL, /* estimate_number_of_insns */
343 haifa_luid_for_non_insn, /* luid_for_non_insn */
344 SCHED_PASS_UNKNOWN /* sched_pass_id */
347 const struct sched_scan_info_def *sched_scan_info;
349 /* Mapping from instruction UID to its Logical UID. */
350 VEC (int, heap) *sched_luids = NULL;
352 /* Next LUID to assign to an instruction. */
353 int sched_max_luid = 1;
355 /* Haifa Instruction Data. */
356 VEC (haifa_insn_data_def, heap) *h_i_d = NULL;
358 void (* sched_init_only_bb) (basic_block, basic_block);
360 /* Split block function. Different schedulers might use different functions
361 to handle their internal data consistent. */
362 basic_block (* sched_split_block) (basic_block, rtx);
364 /* Create empty basic block after the specified block. */
365 basic_block (* sched_create_empty_bb) (basic_block);
368 may_trap_exp (const_rtx x, int is_store)
377 if (code == MEM && may_trap_p (x))
384 /* The insn uses memory: a volatile load. */
385 if (MEM_VOLATILE_P (x))
387 /* An exception-free load. */
390 /* A load with 1 base register, to be further checked. */
391 if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))
392 return PFREE_CANDIDATE;
393 /* No info on the load, to be further checked. */
394 return PRISKY_CANDIDATE;
399 int i, insn_class = TRAP_FREE;
401 /* Neither store nor load, check if it may cause a trap. */
404 /* Recursive step: walk the insn... */
405 fmt = GET_RTX_FORMAT (code);
406 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
410 int tmp_class = may_trap_exp (XEXP (x, i), is_store);
411 insn_class = WORST_CLASS (insn_class, tmp_class);
413 else if (fmt[i] == 'E')
416 for (j = 0; j < XVECLEN (x, i); j++)
418 int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);
419 insn_class = WORST_CLASS (insn_class, tmp_class);
420 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
424 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
431 /* Classifies rtx X of an insn for the purpose of verifying that X can be
432 executed speculatively (and consequently the insn can be moved
433 speculatively), by examining X, returning:
434 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
435 TRAP_FREE: non-load insn.
436 IFREE: load from a globally safe location.
437 IRISKY: volatile load.
438 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
439 being either PFREE or PRISKY. */
442 haifa_classify_rtx (const_rtx x)
444 int tmp_class = TRAP_FREE;
445 int insn_class = TRAP_FREE;
448 if (GET_CODE (x) == PARALLEL)
450 int i, len = XVECLEN (x, 0);
452 for (i = len - 1; i >= 0; i--)
454 tmp_class = haifa_classify_rtx (XVECEXP (x, 0, i));
455 insn_class = WORST_CLASS (insn_class, tmp_class);
456 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
466 /* Test if it is a 'store'. */
467 tmp_class = may_trap_exp (XEXP (x, 0), 1);
470 /* Test if it is a store. */
471 tmp_class = may_trap_exp (SET_DEST (x), 1);
472 if (tmp_class == TRAP_RISKY)
474 /* Test if it is a load. */
476 WORST_CLASS (tmp_class,
477 may_trap_exp (SET_SRC (x), 0));
480 tmp_class = haifa_classify_rtx (COND_EXEC_CODE (x));
481 if (tmp_class == TRAP_RISKY)
483 tmp_class = WORST_CLASS (tmp_class,
484 may_trap_exp (COND_EXEC_TEST (x), 0));
487 tmp_class = TRAP_RISKY;
491 insn_class = tmp_class;
498 haifa_classify_insn (const_rtx insn)
500 return haifa_classify_rtx (PATTERN (insn));
503 /* Forward declarations. */
505 static int priority (rtx);
506 static int rank_for_schedule (const void *, const void *);
507 static void swap_sort (rtx *, int);
508 static void queue_insn (rtx, int);
509 static int schedule_insn (rtx);
510 static int find_set_reg_weight (const_rtx);
511 static void find_insn_reg_weight (const_rtx);
512 static void adjust_priority (rtx);
513 static void advance_one_cycle (void);
514 static void extend_h_i_d (void);
517 /* Notes handling mechanism:
518 =========================
519 Generally, NOTES are saved before scheduling and restored after scheduling.
520 The scheduler distinguishes between two types of notes:
522 (1) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
523 Before scheduling a region, a pointer to the note is added to the insn
524 that follows or precedes it. (This happens as part of the data dependence
525 computation). After scheduling an insn, the pointer contained in it is
526 used for regenerating the corresponding note (in reemit_notes).
528 (2) All other notes (e.g. INSN_DELETED): Before scheduling a block,
529 these notes are put in a list (in rm_other_notes() and
530 unlink_other_notes ()). After scheduling the block, these notes are
531 inserted at the beginning of the block (in schedule_block()). */
533 static void ready_add (struct ready_list *, rtx, bool);
534 static rtx ready_remove_first (struct ready_list *);
536 static void queue_to_ready (struct ready_list *);
537 static int early_queue_to_ready (state_t, struct ready_list *);
539 static void debug_ready_list (struct ready_list *);
541 /* The following functions are used to implement multi-pass scheduling
542 on the first cycle. */
543 static rtx ready_remove (struct ready_list *, int);
544 static void ready_remove_insn (rtx);
546 static int choose_ready (struct ready_list *, rtx *);
548 static void fix_inter_tick (rtx, rtx);
549 static int fix_tick_ready (rtx);
550 static void change_queue_index (rtx, int);
552 /* The following functions are used to implement scheduling of data/control
553 speculative instructions. */
555 static void extend_h_i_d (void);
556 static void init_h_i_d (rtx);
557 static void generate_recovery_code (rtx);
558 static void process_insn_forw_deps_be_in_spec (rtx, rtx, ds_t);
559 static void begin_speculative_block (rtx);
560 static void add_to_speculative_block (rtx);
561 static void init_before_recovery (basic_block *);
562 static void create_check_block_twin (rtx, bool);
563 static void fix_recovery_deps (basic_block);
564 static void haifa_change_pattern (rtx, rtx);
565 static void dump_new_block_header (int, basic_block, rtx, rtx);
566 static void restore_bb_notes (basic_block);
567 static void fix_jump_move (rtx);
568 static void move_block_after_check (rtx);
569 static void move_succs (VEC(edge,gc) **, basic_block);
570 static void sched_remove_insn (rtx);
571 static void clear_priorities (rtx, rtx_vec_t *);
572 static void calc_priorities (rtx_vec_t);
573 static void add_jump_dependencies (rtx, rtx);
574 #ifdef ENABLE_CHECKING
575 static int has_edge_p (VEC(edge,gc) *, int);
576 static void check_cfg (rtx, rtx);
579 #endif /* INSN_SCHEDULING */
581 /* Point to state used for the current scheduling pass. */
582 struct haifa_sched_info *current_sched_info;
584 #ifndef INSN_SCHEDULING
586 schedule_insns (void)
591 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
592 so that insns independent of the last scheduled insn will be preferred
593 over dependent instructions. */
595 static rtx last_scheduled_insn;
597 /* Cached cost of the instruction. Use below function to get cost of the
598 insn. -1 here means that the field is not initialized. */
599 #define INSN_COST(INSN) (HID (INSN)->cost)
601 /* Compute cost of executing INSN.
602 This is the number of cycles between instruction issue and
603 instruction results. */
611 if (recog_memoized (insn) < 0)
614 cost = insn_default_latency (insn);
621 cost = INSN_COST (insn);
625 /* A USE insn, or something else we don't need to
626 understand. We can't pass these directly to
627 result_ready_cost or insn_default_latency because it will
628 trigger a fatal error for unrecognizable insns. */
629 if (recog_memoized (insn) < 0)
631 INSN_COST (insn) = 0;
636 cost = insn_default_latency (insn);
640 INSN_COST (insn) = cost;
647 /* Compute cost of dependence LINK.
648 This is the number of cycles between instruction issue and
649 instruction results. */
651 dep_cost_1 (dep_t link, dw_t dw)
653 rtx used = DEP_CON (link);
656 /* A USE insn should never require the value used to be computed.
657 This allows the computation of a function's result and parameter
658 values to overlap the return and call. */
659 if (recog_memoized (used) < 0)
663 rtx insn = DEP_PRO (link);
664 enum reg_note dep_type = DEP_TYPE (link);
666 cost = insn_cost (insn);
668 if (INSN_CODE (insn) >= 0)
670 if (dep_type == REG_DEP_ANTI)
672 else if (dep_type == REG_DEP_OUTPUT)
674 cost = (insn_default_latency (insn)
675 - insn_default_latency (used));
679 else if (bypass_p (insn))
680 cost = insn_latency (insn, used);
684 if (targetm.sched.adjust_cost_2)
686 cost = targetm.sched.adjust_cost_2 (used, (int) dep_type, insn, cost,
689 else if (targetm.sched.adjust_cost != NULL)
691 /* This variable is used for backward compatibility with the
693 rtx dep_cost_rtx_link = alloc_INSN_LIST (NULL_RTX, NULL_RTX);
695 /* Make it self-cycled, so that if some tries to walk over this
696 incomplete list he/she will be caught in an endless loop. */
697 XEXP (dep_cost_rtx_link, 1) = dep_cost_rtx_link;
699 /* Targets use only REG_NOTE_KIND of the link. */
700 PUT_REG_NOTE_KIND (dep_cost_rtx_link, DEP_TYPE (link));
702 cost = targetm.sched.adjust_cost (used, dep_cost_rtx_link,
705 free_INSN_LIST_node (dep_cost_rtx_link);
715 /* Compute cost of dependence LINK.
716 This is the number of cycles between instruction issue and
717 instruction results. */
719 dep_cost (dep_t link)
721 return dep_cost_1 (link, 0);
724 /* Use this sel-sched.c friendly function in reorder2 instead of increasing
725 INSN_PRIORITY explicitly. */
727 increase_insn_priority (rtx insn, int amount)
731 /* We're dealing with haifa-sched.c INSN_PRIORITY. */
732 if (INSN_PRIORITY_KNOWN (insn))
733 INSN_PRIORITY (insn) += amount;
737 /* In sel-sched.c INSN_PRIORITY is not kept up to date.
738 Use EXPR_PRIORITY instead. */
739 sel_add_to_insn_priority (insn, amount);
743 /* Return 'true' if DEP should be included in priority calculations. */
745 contributes_to_priority_p (dep_t dep)
747 /* Critical path is meaningful in block boundaries only. */
748 if (!current_sched_info->contributes_to_priority (DEP_CON (dep),
752 /* If flag COUNT_SPEC_IN_CRITICAL_PATH is set,
753 then speculative instructions will less likely be
754 scheduled. That is because the priority of
755 their producers will increase, and, thus, the
756 producers will more likely be scheduled, thus,
757 resolving the dependence. */
758 if (sched_deps_info->generate_spec_deps
759 && !(spec_info->flags & COUNT_SPEC_IN_CRITICAL_PATH)
760 && (DEP_STATUS (dep) & SPECULATIVE))
766 /* Compute the priority number for INSN. */
773 /* We should not be interested in priority of an already scheduled insn. */
774 gcc_assert (QUEUE_INDEX (insn) != QUEUE_SCHEDULED);
776 if (!INSN_PRIORITY_KNOWN (insn))
778 int this_priority = -1;
780 if (sd_lists_empty_p (insn, SD_LIST_FORW))
781 /* ??? We should set INSN_PRIORITY to insn_cost when and insn has
782 some forward deps but all of them are ignored by
783 contributes_to_priority hook. At the moment we set priority of
785 this_priority = insn_cost (insn);
788 rtx prev_first, twin;
791 /* For recovery check instructions we calculate priority slightly
792 different than that of normal instructions. Instead of walking
793 through INSN_FORW_DEPS (check) list, we walk through
794 INSN_FORW_DEPS list of each instruction in the corresponding
797 /* Selective scheduling does not define RECOVERY_BLOCK macro. */
798 rec = sel_sched_p () ? NULL : RECOVERY_BLOCK (insn);
799 if (!rec || rec == EXIT_BLOCK_PTR)
801 prev_first = PREV_INSN (insn);
806 prev_first = NEXT_INSN (BB_HEAD (rec));
807 twin = PREV_INSN (BB_END (rec));
812 sd_iterator_def sd_it;
815 FOR_EACH_DEP (twin, SD_LIST_FORW, sd_it, dep)
820 next = DEP_CON (dep);
822 if (BLOCK_FOR_INSN (next) != rec)
826 if (!contributes_to_priority_p (dep))
830 cost = dep_cost (dep);
833 struct _dep _dep1, *dep1 = &_dep1;
835 init_dep (dep1, insn, next, REG_DEP_ANTI);
837 cost = dep_cost (dep1);
840 next_priority = cost + priority (next);
842 if (next_priority > this_priority)
843 this_priority = next_priority;
847 twin = PREV_INSN (twin);
849 while (twin != prev_first);
852 if (this_priority < 0)
854 gcc_assert (this_priority == -1);
856 this_priority = insn_cost (insn);
859 INSN_PRIORITY (insn) = this_priority;
860 INSN_PRIORITY_STATUS (insn) = 1;
863 return INSN_PRIORITY (insn);
866 /* Macros and functions for keeping the priority queue sorted, and
867 dealing with queuing and dequeuing of instructions. */
869 #define SCHED_SORT(READY, N_READY) \
870 do { if ((N_READY) == 2) \
871 swap_sort (READY, N_READY); \
872 else if ((N_READY) > 2) \
873 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
876 /* Returns a positive value if x is preferred; returns a negative value if
877 y is preferred. Should never return 0, since that will make the sort
881 rank_for_schedule (const void *x, const void *y)
883 rtx tmp = *(const rtx *) y;
884 rtx tmp2 = *(const rtx *) x;
885 int tmp_class, tmp2_class;
886 int val, priority_val, weight_val, info_val;
888 /* The insn in a schedule group should be issued the first. */
889 if (SCHED_GROUP_P (tmp) != SCHED_GROUP_P (tmp2))
890 return SCHED_GROUP_P (tmp2) ? 1 : -1;
892 /* Make sure that priority of TMP and TMP2 are initialized. */
893 gcc_assert (INSN_PRIORITY_KNOWN (tmp) && INSN_PRIORITY_KNOWN (tmp2));
895 /* Prefer insn with higher priority. */
896 priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
901 /* Prefer speculative insn with greater dependencies weakness. */
908 ds1 = TODO_SPEC (tmp) & SPECULATIVE;
914 ds2 = TODO_SPEC (tmp2) & SPECULATIVE;
921 if (dw > (NO_DEP_WEAK / 8) || dw < -(NO_DEP_WEAK / 8))
925 /* Prefer an insn with smaller contribution to registers-pressure. */
926 if (!reload_completed &&
927 (weight_val = INSN_REG_WEIGHT (tmp) - INSN_REG_WEIGHT (tmp2)))
930 info_val = (*current_sched_info->rank) (tmp, tmp2);
934 /* Compare insns based on their relation to the last-scheduled-insn. */
935 if (INSN_P (last_scheduled_insn))
940 /* Classify the instructions into three classes:
941 1) Data dependent on last schedule insn.
942 2) Anti/Output dependent on last scheduled insn.
943 3) Independent of last scheduled insn, or has latency of one.
944 Choose the insn from the highest numbered class if different. */
945 dep1 = sd_find_dep_between (last_scheduled_insn, tmp, true);
947 if (dep1 == NULL || dep_cost (dep1) == 1)
949 else if (/* Data dependence. */
950 DEP_TYPE (dep1) == REG_DEP_TRUE)
955 dep2 = sd_find_dep_between (last_scheduled_insn, tmp2, true);
957 if (dep2 == NULL || dep_cost (dep2) == 1)
959 else if (/* Data dependence. */
960 DEP_TYPE (dep2) == REG_DEP_TRUE)
965 if ((val = tmp2_class - tmp_class))
969 /* Prefer the insn which has more later insns that depend on it.
970 This gives the scheduler more freedom when scheduling later
971 instructions at the expense of added register pressure. */
973 val = (sd_lists_size (tmp2, SD_LIST_FORW)
974 - sd_lists_size (tmp, SD_LIST_FORW));
979 /* If insns are equally good, sort by INSN_LUID (original insn order),
980 so that we make the sort stable. This minimizes instruction movement,
981 thus minimizing sched's effect on debugging and cross-jumping. */
982 return INSN_LUID (tmp) - INSN_LUID (tmp2);
985 /* Resort the array A in which only element at index N may be out of order. */
987 HAIFA_INLINE static void
988 swap_sort (rtx *a, int n)
993 while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0)
1001 /* Add INSN to the insn queue so that it can be executed at least
1002 N_CYCLES after the currently executing insn. Preserve insns
1003 chain for debugging purposes. */
1005 HAIFA_INLINE static void
1006 queue_insn (rtx insn, int n_cycles)
1008 int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
1009 rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]);
1011 gcc_assert (n_cycles <= max_insn_queue_index);
1013 insn_queue[next_q] = link;
1016 if (sched_verbose >= 2)
1018 fprintf (sched_dump, ";;\t\tReady-->Q: insn %s: ",
1019 (*current_sched_info->print_insn) (insn, 0));
1021 fprintf (sched_dump, "queued for %d cycles.\n", n_cycles);
1024 QUEUE_INDEX (insn) = next_q;
1027 /* Remove INSN from queue. */
1029 queue_remove (rtx insn)
1031 gcc_assert (QUEUE_INDEX (insn) >= 0);
1032 remove_free_INSN_LIST_elem (insn, &insn_queue[QUEUE_INDEX (insn)]);
1034 QUEUE_INDEX (insn) = QUEUE_NOWHERE;
1037 /* Return a pointer to the bottom of the ready list, i.e. the insn
1038 with the lowest priority. */
1041 ready_lastpos (struct ready_list *ready)
1043 gcc_assert (ready->n_ready >= 1);
1044 return ready->vec + ready->first - ready->n_ready + 1;
1047 /* Add an element INSN to the ready list so that it ends up with the
1048 lowest/highest priority depending on FIRST_P. */
1050 HAIFA_INLINE static void
1051 ready_add (struct ready_list *ready, rtx insn, bool first_p)
1055 if (ready->first == ready->n_ready)
1057 memmove (ready->vec + ready->veclen - ready->n_ready,
1058 ready_lastpos (ready),
1059 ready->n_ready * sizeof (rtx));
1060 ready->first = ready->veclen - 1;
1062 ready->vec[ready->first - ready->n_ready] = insn;
1066 if (ready->first == ready->veclen - 1)
1069 /* ready_lastpos() fails when called with (ready->n_ready == 0). */
1070 memmove (ready->vec + ready->veclen - ready->n_ready - 1,
1071 ready_lastpos (ready),
1072 ready->n_ready * sizeof (rtx));
1073 ready->first = ready->veclen - 2;
1075 ready->vec[++(ready->first)] = insn;
1080 gcc_assert (QUEUE_INDEX (insn) != QUEUE_READY);
1081 QUEUE_INDEX (insn) = QUEUE_READY;
1084 /* Remove the element with the highest priority from the ready list and
1087 HAIFA_INLINE static rtx
1088 ready_remove_first (struct ready_list *ready)
1092 gcc_assert (ready->n_ready);
1093 t = ready->vec[ready->first--];
1095 /* If the queue becomes empty, reset it. */
1096 if (ready->n_ready == 0)
1097 ready->first = ready->veclen - 1;
1099 gcc_assert (QUEUE_INDEX (t) == QUEUE_READY);
1100 QUEUE_INDEX (t) = QUEUE_NOWHERE;
1105 /* The following code implements multi-pass scheduling for the first
1106 cycle. In other words, we will try to choose ready insn which
1107 permits to start maximum number of insns on the same cycle. */
1109 /* Return a pointer to the element INDEX from the ready. INDEX for
1110 insn with the highest priority is 0, and the lowest priority has
1114 ready_element (struct ready_list *ready, int index)
1116 gcc_assert (ready->n_ready && index < ready->n_ready);
1118 return ready->vec[ready->first - index];
1121 /* Remove the element INDEX from the ready list and return it. INDEX
1122 for insn with the highest priority is 0, and the lowest priority
1125 HAIFA_INLINE static rtx
1126 ready_remove (struct ready_list *ready, int index)
1132 return ready_remove_first (ready);
1133 gcc_assert (ready->n_ready && index < ready->n_ready);
1134 t = ready->vec[ready->first - index];
1136 for (i = index; i < ready->n_ready; i++)
1137 ready->vec[ready->first - i] = ready->vec[ready->first - i - 1];
1138 QUEUE_INDEX (t) = QUEUE_NOWHERE;
1142 /* Remove INSN from the ready list. */
1144 ready_remove_insn (rtx insn)
1148 for (i = 0; i < readyp->n_ready; i++)
1149 if (ready_element (readyp, i) == insn)
1151 ready_remove (readyp, i);
1157 /* Sort the ready list READY by ascending priority, using the SCHED_SORT
1161 ready_sort (struct ready_list *ready)
1163 rtx *first = ready_lastpos (ready);
1164 SCHED_SORT (first, ready->n_ready);
1167 /* PREV is an insn that is ready to execute. Adjust its priority if that
1168 will help shorten or lengthen register lifetimes as appropriate. Also
1169 provide a hook for the target to tweak itself. */
1171 HAIFA_INLINE static void
1172 adjust_priority (rtx prev)
1174 /* ??? There used to be code here to try and estimate how an insn
1175 affected register lifetimes, but it did it by looking at REG_DEAD
1176 notes, which we removed in schedule_region. Nor did it try to
1177 take into account register pressure or anything useful like that.
1179 Revisit when we have a machine model to work with and not before. */
1181 if (targetm.sched.adjust_priority)
1182 INSN_PRIORITY (prev) =
1183 targetm.sched.adjust_priority (prev, INSN_PRIORITY (prev));
1186 /* Advance DFA state STATE on one cycle. */
1188 advance_state (state_t state)
1190 if (targetm.sched.dfa_pre_advance_cycle)
1191 targetm.sched.dfa_pre_advance_cycle ();
1193 if (targetm.sched.dfa_pre_cycle_insn)
1194 state_transition (state,
1195 targetm.sched.dfa_pre_cycle_insn ());
1197 state_transition (state, NULL);
1199 if (targetm.sched.dfa_post_cycle_insn)
1200 state_transition (state,
1201 targetm.sched.dfa_post_cycle_insn ());
1203 if (targetm.sched.dfa_post_advance_cycle)
1204 targetm.sched.dfa_post_advance_cycle ();
1207 /* Advance time on one cycle. */
1208 HAIFA_INLINE static void
1209 advance_one_cycle (void)
1211 advance_state (curr_state);
1212 if (sched_verbose >= 6)
1213 fprintf (sched_dump, "\n;;\tAdvanced a state.\n");
1216 /* Clock at which the previous instruction was issued. */
1217 static int last_clock_var;
1219 /* INSN is the "currently executing insn". Launch each insn which was
1220 waiting on INSN. READY is the ready list which contains the insns
1221 that are ready to fire. CLOCK is the current cycle. The function
1222 returns necessary cycle advance after issuing the insn (it is not
1223 zero for insns in a schedule group). */
1226 schedule_insn (rtx insn)
1228 sd_iterator_def sd_it;
1232 if (sched_verbose >= 1)
1236 print_insn (buf, insn, 0);
1238 fprintf (sched_dump, ";;\t%3i--> %-40s:", clock_var, buf);
1240 if (recog_memoized (insn) < 0)
1241 fprintf (sched_dump, "nothing");
1243 print_reservation (sched_dump, insn);
1244 fputc ('\n', sched_dump);
1247 /* Scheduling instruction should have all its dependencies resolved and
1248 should have been removed from the ready list. */
1249 gcc_assert (sd_lists_empty_p (insn, SD_LIST_BACK));
1251 gcc_assert (QUEUE_INDEX (insn) == QUEUE_NOWHERE);
1252 QUEUE_INDEX (insn) = QUEUE_SCHEDULED;
1254 gcc_assert (INSN_TICK (insn) >= MIN_TICK);
1255 if (INSN_TICK (insn) > clock_var)
1256 /* INSN has been prematurely moved from the queue to the ready list.
1257 This is possible only if following flag is set. */
1258 gcc_assert (flag_sched_stalled_insns);
1260 /* ??? Probably, if INSN is scheduled prematurely, we should leave
1261 INSN_TICK untouched. This is a machine-dependent issue, actually. */
1262 INSN_TICK (insn) = clock_var;
1264 /* Update dependent instructions. */
1265 for (sd_it = sd_iterator_start (insn, SD_LIST_FORW);
1266 sd_iterator_cond (&sd_it, &dep);)
1268 rtx next = DEP_CON (dep);
1270 /* Resolve the dependence between INSN and NEXT.
1271 sd_resolve_dep () moves current dep to another list thus
1272 advancing the iterator. */
1273 sd_resolve_dep (sd_it);
1275 if (!IS_SPECULATION_BRANCHY_CHECK_P (insn))
1279 effective_cost = try_ready (next);
1281 if (effective_cost >= 0
1282 && SCHED_GROUP_P (next)
1283 && advance < effective_cost)
1284 advance = effective_cost;
1287 /* Check always has only one forward dependence (to the first insn in
1288 the recovery block), therefore, this will be executed only once. */
1290 gcc_assert (sd_lists_empty_p (insn, SD_LIST_FORW));
1291 fix_recovery_deps (RECOVERY_BLOCK (insn));
1295 /* This is the place where scheduler doesn't *basically* need backward and
1296 forward dependencies for INSN anymore. Nevertheless they are used in
1297 heuristics in rank_for_schedule (), early_queue_to_ready () and in
1298 some targets (e.g. rs6000). Thus the earliest place where we *can*
1299 remove dependencies is after targetm.sched.md_finish () call in
1300 schedule_block (). But, on the other side, the safest place to remove
1301 dependencies is when we are finishing scheduling entire region. As we
1302 don't generate [many] dependencies during scheduling itself, we won't
1303 need memory until beginning of next region.
1304 Bottom line: Dependencies are removed for all insns in the end of
1305 scheduling the region. */
1307 /* Annotate the instruction with issue information -- TImode
1308 indicates that the instruction is expected not to be able
1309 to issue on the same cycle as the previous insn. A machine
1310 may use this information to decide how the instruction should
1313 && GET_CODE (PATTERN (insn)) != USE
1314 && GET_CODE (PATTERN (insn)) != CLOBBER)
1316 if (reload_completed)
1317 PUT_MODE (insn, clock_var > last_clock_var ? TImode : VOIDmode);
1318 last_clock_var = clock_var;
1324 /* Functions for handling of notes. */
1326 /* Insert the INSN note at the end of the notes list. */
1328 add_to_note_list (rtx insn, rtx *note_list_end_p)
1330 PREV_INSN (insn) = *note_list_end_p;
1331 if (*note_list_end_p)
1332 NEXT_INSN (*note_list_end_p) = insn;
1333 *note_list_end_p = insn;
1336 /* Add note list that ends on FROM_END to the end of TO_ENDP. */
1338 concat_note_lists (rtx from_end, rtx *to_endp)
1342 if (from_end == NULL)
1343 /* It's easy when have nothing to concat. */
1346 if (*to_endp == NULL)
1347 /* It's also easy when destination is empty. */
1349 *to_endp = from_end;
1353 from_start = from_end;
1354 /* A note list should be traversed via PREV_INSN. */
1355 while (PREV_INSN (from_start) != NULL)
1356 from_start = PREV_INSN (from_start);
1358 add_to_note_list (from_start, to_endp);
1359 *to_endp = from_end;
1362 /* Delete notes beginning with INSN and put them in the chain
1363 of notes ended by NOTE_LIST.
1364 Returns the insn following the notes. */
1366 unlink_other_notes (rtx insn, rtx tail)
1368 rtx prev = PREV_INSN (insn);
1370 while (insn != tail && NOTE_NOT_BB_P (insn))
1372 rtx next = NEXT_INSN (insn);
1373 basic_block bb = BLOCK_FOR_INSN (insn);
1375 /* Delete the note from its current position. */
1377 NEXT_INSN (prev) = next;
1379 PREV_INSN (next) = prev;
1383 /* Basic block can begin with either LABEL or
1384 NOTE_INSN_BASIC_BLOCK. */
1385 gcc_assert (BB_HEAD (bb) != insn);
1387 /* Check if we are removing last insn in the BB. */
1388 if (BB_END (bb) == insn)
1392 /* See sched_analyze to see how these are handled. */
1393 if (NOTE_KIND (insn) != NOTE_INSN_EH_REGION_BEG
1394 && NOTE_KIND (insn) != NOTE_INSN_EH_REGION_END)
1395 add_to_note_list (insn, ¬e_list);
1402 gcc_assert (sel_sched_p ());
1409 /* Return the head and tail pointers of ebb starting at BEG and ending
1412 get_ebb_head_tail (basic_block beg, basic_block end, rtx *headp, rtx *tailp)
1414 rtx beg_head = BB_HEAD (beg);
1415 rtx beg_tail = BB_END (beg);
1416 rtx end_head = BB_HEAD (end);
1417 rtx end_tail = BB_END (end);
1419 /* Don't include any notes or labels at the beginning of the BEG
1420 basic block, or notes at the end of the END basic blocks. */
1422 if (LABEL_P (beg_head))
1423 beg_head = NEXT_INSN (beg_head);
1425 while (beg_head != beg_tail)
1426 if (NOTE_P (beg_head))
1427 beg_head = NEXT_INSN (beg_head);
1434 end_head = beg_head;
1435 else if (LABEL_P (end_head))
1436 end_head = NEXT_INSN (end_head);
1438 while (end_head != end_tail)
1439 if (NOTE_P (end_tail))
1440 end_tail = PREV_INSN (end_tail);
1447 /* Return nonzero if there are no real insns in the range [ HEAD, TAIL ]. */
1450 no_real_insns_p (const_rtx head, const_rtx tail)
1452 while (head != NEXT_INSN (tail))
1454 if (!NOTE_P (head) && !LABEL_P (head))
1456 head = NEXT_INSN (head);
1461 /* Delete notes between HEAD and TAIL and put them in the chain
1462 of notes ended by NOTE_LIST. */
1464 rm_other_notes (rtx head, rtx tail)
1470 if (head == tail && (! INSN_P (head)))
1473 next_tail = NEXT_INSN (tail);
1474 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1478 /* Farm out notes, and maybe save them in NOTE_LIST.
1479 This is needed to keep the debugger from
1480 getting completely deranged. */
1481 if (NOTE_NOT_BB_P (insn))
1484 insn = unlink_other_notes (insn, next_tail);
1486 gcc_assert ((sel_sched_p ()
1487 || prev != tail) && prev != head && insn != next_tail);
1492 /* Same as above, but also process REG_SAVE_NOTEs of HEAD. */
1494 remove_notes (rtx head, rtx tail)
1496 /* rm_other_notes only removes notes which are _inside_ the
1497 block---that is, it won't remove notes before the first real insn
1498 or after the last real insn of the block. So if the first insn
1499 has a REG_SAVE_NOTE which would otherwise be emitted before the
1500 insn, it is redundant with the note before the start of the
1501 block, and so we have to take it out. */
1506 for (note = REG_NOTES (head); note; note = XEXP (note, 1))
1507 if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
1508 remove_note (head, note);
1511 /* Remove remaining note insns from the block, save them in
1512 note_list. These notes are restored at the end of
1513 schedule_block (). */
1514 rm_other_notes (head, tail);
1517 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
1518 previously found among the insns. Insert them just before HEAD. */
1520 restore_other_notes (rtx head, basic_block head_bb)
1524 rtx note_head = note_list;
1527 head_bb = BLOCK_FOR_INSN (head);
1529 head = NEXT_INSN (bb_note (head_bb));
1531 while (PREV_INSN (note_head))
1533 set_block_for_insn (note_head, head_bb);
1534 note_head = PREV_INSN (note_head);
1536 /* In the above cycle we've missed this note. */
1537 set_block_for_insn (note_head, head_bb);
1539 PREV_INSN (note_head) = PREV_INSN (head);
1540 NEXT_INSN (PREV_INSN (head)) = note_head;
1541 PREV_INSN (head) = note_list;
1542 NEXT_INSN (note_list) = head;
1544 if (BLOCK_FOR_INSN (head) != head_bb)
1545 BB_END (head_bb) = note_list;
1553 /* Functions for computation of registers live/usage info. */
1555 /* This function looks for a new register being defined.
1556 If the destination register is already used by the source,
1557 a new register is not needed. */
1559 find_set_reg_weight (const_rtx x)
1561 if (GET_CODE (x) == CLOBBER
1562 && register_operand (SET_DEST (x), VOIDmode))
1564 if (GET_CODE (x) == SET
1565 && register_operand (SET_DEST (x), VOIDmode))
1567 if (REG_P (SET_DEST (x)))
1569 if (!reg_mentioned_p (SET_DEST (x), SET_SRC (x)))
1579 /* Calculate INSN_REG_WEIGHT for INSN. */
1581 find_insn_reg_weight (const_rtx insn)
1586 /* Handle register life information. */
1587 if (! INSN_P (insn))
1590 /* Increment weight for each register born here. */
1592 reg_weight += find_set_reg_weight (x);
1593 if (GET_CODE (x) == PARALLEL)
1596 for (j = XVECLEN (x, 0) - 1; j >= 0; j--)
1598 x = XVECEXP (PATTERN (insn), 0, j);
1599 reg_weight += find_set_reg_weight (x);
1602 /* Decrement weight for each register that dies here. */
1603 for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
1605 if (REG_NOTE_KIND (x) == REG_DEAD
1606 || REG_NOTE_KIND (x) == REG_UNUSED)
1610 INSN_REG_WEIGHT (insn) = reg_weight;
1613 /* Move insns that became ready to fire from queue to ready list. */
1616 queue_to_ready (struct ready_list *ready)
1622 q_ptr = NEXT_Q (q_ptr);
1624 if (dbg_cnt (sched_insn) == false)
1625 /* If debug counter is activated do not requeue insn next after
1626 last_scheduled_insn. */
1627 skip_insn = next_nonnote_insn (last_scheduled_insn);
1629 skip_insn = NULL_RTX;
1631 /* Add all pending insns that can be scheduled without stalls to the
1633 for (link = insn_queue[q_ptr]; link; link = XEXP (link, 1))
1635 insn = XEXP (link, 0);
1638 if (sched_verbose >= 2)
1639 fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
1640 (*current_sched_info->print_insn) (insn, 0));
1642 /* If the ready list is full, delay the insn for 1 cycle.
1643 See the comment in schedule_block for the rationale. */
1644 if (!reload_completed
1645 && ready->n_ready > MAX_SCHED_READY_INSNS
1646 && !SCHED_GROUP_P (insn)
1647 && insn != skip_insn)
1649 if (sched_verbose >= 2)
1650 fprintf (sched_dump, "requeued because ready full\n");
1651 queue_insn (insn, 1);
1655 ready_add (ready, insn, false);
1656 if (sched_verbose >= 2)
1657 fprintf (sched_dump, "moving to ready without stalls\n");
1660 free_INSN_LIST_list (&insn_queue[q_ptr]);
1662 /* If there are no ready insns, stall until one is ready and add all
1663 of the pending insns at that point to the ready list. */
1664 if (ready->n_ready == 0)
1668 for (stalls = 1; stalls <= max_insn_queue_index; stalls++)
1670 if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
1672 for (; link; link = XEXP (link, 1))
1674 insn = XEXP (link, 0);
1677 if (sched_verbose >= 2)
1678 fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
1679 (*current_sched_info->print_insn) (insn, 0));
1681 ready_add (ready, insn, false);
1682 if (sched_verbose >= 2)
1683 fprintf (sched_dump, "moving to ready with %d stalls\n", stalls);
1685 free_INSN_LIST_list (&insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]);
1687 advance_one_cycle ();
1692 advance_one_cycle ();
1695 q_ptr = NEXT_Q_AFTER (q_ptr, stalls);
1696 clock_var += stalls;
1700 /* Used by early_queue_to_ready. Determines whether it is "ok" to
1701 prematurely move INSN from the queue to the ready list. Currently,
1702 if a target defines the hook 'is_costly_dependence', this function
1703 uses the hook to check whether there exist any dependences which are
1704 considered costly by the target, between INSN and other insns that
1705 have already been scheduled. Dependences are checked up to Y cycles
1706 back, with default Y=1; The flag -fsched-stalled-insns-dep=Y allows
1707 controlling this value.
1708 (Other considerations could be taken into account instead (or in
1709 addition) depending on user flags and target hooks. */
1712 ok_for_early_queue_removal (rtx insn)
1715 rtx prev_insn = last_scheduled_insn;
1717 if (targetm.sched.is_costly_dependence)
1719 for (n_cycles = flag_sched_stalled_insns_dep; n_cycles; n_cycles--)
1721 for ( ; prev_insn; prev_insn = PREV_INSN (prev_insn))
1725 if (prev_insn == current_sched_info->prev_head)
1731 if (!NOTE_P (prev_insn))
1735 dep = sd_find_dep_between (prev_insn, insn, true);
1739 cost = dep_cost (dep);
1741 if (targetm.sched.is_costly_dependence (dep, cost,
1742 flag_sched_stalled_insns_dep - n_cycles))
1747 if (GET_MODE (prev_insn) == TImode) /* end of dispatch group */
1753 prev_insn = PREV_INSN (prev_insn);
1761 /* Remove insns from the queue, before they become "ready" with respect
1762 to FU latency considerations. */
1765 early_queue_to_ready (state_t state, struct ready_list *ready)
1773 state_t temp_state = alloca (dfa_state_size);
1775 int insns_removed = 0;
1778 Flag '-fsched-stalled-insns=X' determines the aggressiveness of this
1781 X == 0: There is no limit on how many queued insns can be removed
1782 prematurely. (flag_sched_stalled_insns = -1).
1784 X >= 1: Only X queued insns can be removed prematurely in each
1785 invocation. (flag_sched_stalled_insns = X).
1787 Otherwise: Early queue removal is disabled.
1788 (flag_sched_stalled_insns = 0)
1791 if (! flag_sched_stalled_insns)
1794 for (stalls = 0; stalls <= max_insn_queue_index; stalls++)
1796 if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
1798 if (sched_verbose > 6)
1799 fprintf (sched_dump, ";; look at index %d + %d\n", q_ptr, stalls);
1804 next_link = XEXP (link, 1);
1805 insn = XEXP (link, 0);
1806 if (insn && sched_verbose > 6)
1807 print_rtl_single (sched_dump, insn);
1809 memcpy (temp_state, state, dfa_state_size);
1810 if (recog_memoized (insn) < 0)
1811 /* non-negative to indicate that it's not ready
1812 to avoid infinite Q->R->Q->R... */
1815 cost = state_transition (temp_state, insn);
1817 if (sched_verbose >= 6)
1818 fprintf (sched_dump, "transition cost = %d\n", cost);
1820 move_to_ready = false;
1823 move_to_ready = ok_for_early_queue_removal (insn);
1824 if (move_to_ready == true)
1826 /* move from Q to R */
1828 ready_add (ready, insn, false);
1831 XEXP (prev_link, 1) = next_link;
1833 insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = next_link;
1835 free_INSN_LIST_node (link);
1837 if (sched_verbose >= 2)
1838 fprintf (sched_dump, ";;\t\tEarly Q-->Ready: insn %s\n",
1839 (*current_sched_info->print_insn) (insn, 0));
1842 if (insns_removed == flag_sched_stalled_insns)
1843 /* Remove no more than flag_sched_stalled_insns insns
1844 from Q at a time. */
1845 return insns_removed;
1849 if (move_to_ready == false)
1856 } /* for stalls.. */
1858 return insns_removed;
1862 /* Print the ready list for debugging purposes. Callable from debugger. */
1865 debug_ready_list (struct ready_list *ready)
1870 if (ready->n_ready == 0)
1872 fprintf (sched_dump, "\n");
1876 p = ready_lastpos (ready);
1877 for (i = 0; i < ready->n_ready; i++)
1878 fprintf (sched_dump, " %s", (*current_sched_info->print_insn) (p[i], 0));
1879 fprintf (sched_dump, "\n");
1882 /* Search INSN for REG_SAVE_NOTE note pairs for
1883 NOTE_INSN_EHREGION_{BEG,END}; and convert them back into
1884 NOTEs. The REG_SAVE_NOTE note following first one is contains the
1885 saved value for NOTE_BLOCK_NUMBER which is useful for
1886 NOTE_INSN_EH_REGION_{BEG,END} NOTEs. */
1888 reemit_notes (rtx insn)
1890 rtx note, last = insn;
1892 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1894 if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
1896 enum insn_note note_type = INTVAL (XEXP (note, 0));
1898 last = emit_note_before (note_type, last);
1899 remove_note (insn, note);
1904 /* Move INSN. Reemit notes if needed. Update CFG, if needed. */
1906 move_insn (rtx insn, rtx last, rtx nt)
1908 if (PREV_INSN (insn) != last)
1914 bb = BLOCK_FOR_INSN (insn);
1916 /* BB_HEAD is either LABEL or NOTE. */
1917 gcc_assert (BB_HEAD (bb) != insn);
1919 if (BB_END (bb) == insn)
1920 /* If this is last instruction in BB, move end marker one
1923 /* Jumps are always placed at the end of basic block. */
1924 jump_p = control_flow_insn_p (insn);
1927 || ((common_sched_info->sched_pass_id == SCHED_RGN_PASS)
1928 && IS_SPECULATION_BRANCHY_CHECK_P (insn))
1929 || (common_sched_info->sched_pass_id
1930 == SCHED_EBB_PASS));
1932 gcc_assert (BLOCK_FOR_INSN (PREV_INSN (insn)) == bb);
1934 BB_END (bb) = PREV_INSN (insn);
1937 gcc_assert (BB_END (bb) != last);
1940 /* We move the block note along with jump. */
1944 note = NEXT_INSN (insn);
1945 while (NOTE_NOT_BB_P (note) && note != nt)
1946 note = NEXT_INSN (note);
1950 || BARRIER_P (note)))
1951 note = NEXT_INSN (note);
1953 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
1958 NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (note);
1959 PREV_INSN (NEXT_INSN (note)) = PREV_INSN (insn);
1961 NEXT_INSN (note) = NEXT_INSN (last);
1962 PREV_INSN (NEXT_INSN (last)) = note;
1964 NEXT_INSN (last) = insn;
1965 PREV_INSN (insn) = last;
1967 bb = BLOCK_FOR_INSN (last);
1971 fix_jump_move (insn);
1973 if (BLOCK_FOR_INSN (insn) != bb)
1974 move_block_after_check (insn);
1976 gcc_assert (BB_END (bb) == last);
1979 df_insn_change_bb (insn, bb);
1981 /* Update BB_END, if needed. */
1982 if (BB_END (bb) == last)
1986 SCHED_GROUP_P (insn) = 0;
1989 /* The following structure describe an entry of the stack of choices. */
1992 /* Ordinal number of the issued insn in the ready queue. */
1994 /* The number of the rest insns whose issues we should try. */
1996 /* The number of issued essential insns. */
1998 /* State after issuing the insn. */
2002 /* The following array is used to implement a stack of choices used in
2003 function max_issue. */
2004 static struct choice_entry *choice_stack;
2006 /* The following variable value is number of essential insns issued on
2007 the current cycle. An insn is essential one if it changes the
2008 processors state. */
2009 int cycle_issued_insns;
2011 /* This holds the value of the target dfa_lookahead hook. */
2014 /* The following variable value is maximal number of tries of issuing
2015 insns for the first cycle multipass insn scheduling. We define
2016 this value as constant*(DFA_LOOKAHEAD**ISSUE_RATE). We would not
2017 need this constraint if all real insns (with non-negative codes)
2018 had reservations because in this case the algorithm complexity is
2019 O(DFA_LOOKAHEAD**ISSUE_RATE). Unfortunately, the dfa descriptions
2020 might be incomplete and such insn might occur. For such
2021 descriptions, the complexity of algorithm (without the constraint)
2022 could achieve DFA_LOOKAHEAD ** N , where N is the queue length. */
2023 static int max_lookahead_tries;
2025 /* The following value is value of hook
2026 `first_cycle_multipass_dfa_lookahead' at the last call of
2028 static int cached_first_cycle_multipass_dfa_lookahead = 0;
2030 /* The following value is value of `issue_rate' at the last call of
2032 static int cached_issue_rate = 0;
2034 /* The following function returns maximal (or close to maximal) number
2035 of insns which can be issued on the same cycle and one of which
2036 insns is insns with the best rank (the first insn in READY). To
2037 make this function tries different samples of ready insns. READY
2038 is current queue `ready'. Global array READY_TRY reflects what
2039 insns are already issued in this try. MAX_POINTS is the sum of points
2040 of all instructions in READY. The function stops immediately,
2041 if it reached the such a solution, that all instruction can be issued.
2042 INDEX will contain index of the best insn in READY. The following
2043 function is used only for first cycle multipass scheduling.
2047 This function expects recognized insns only. All USEs,
2048 CLOBBERs, etc must be filtered elsewhere. */
2050 max_issue (struct ready_list *ready, int privileged_n, state_t state,
2053 int n, i, all, n_ready, best, delay, tries_num, points = -1, max_points;
2055 struct choice_entry *top;
2058 n_ready = ready->n_ready;
2059 gcc_assert (dfa_lookahead >= 1 && privileged_n >= 0
2060 && privileged_n <= n_ready);
2062 /* Init MAX_LOOKAHEAD_TRIES. */
2063 if (cached_first_cycle_multipass_dfa_lookahead != dfa_lookahead)
2065 cached_first_cycle_multipass_dfa_lookahead = dfa_lookahead;
2066 max_lookahead_tries = 100;
2067 for (i = 0; i < issue_rate; i++)
2068 max_lookahead_tries *= dfa_lookahead;
2071 /* Init max_points. */
2073 more_issue = issue_rate - cycle_issued_insns;
2074 gcc_assert (more_issue >= 0);
2076 for (i = 0; i < n_ready; i++)
2079 if (more_issue-- > 0)
2080 max_points += ISSUE_POINTS (ready_element (ready, i));
2085 /* The number of the issued insns in the best solution. */
2090 /* Set initial state of the search. */
2091 memcpy (top->state, state, dfa_state_size);
2092 top->rest = dfa_lookahead;
2095 /* Count the number of the insns to search among. */
2096 for (all = i = 0; i < n_ready; i++)
2100 /* I is the index of the insn to try next. */
2105 if (/* If we've reached a dead end or searched enough of what we have
2108 /* Or have nothing else to try. */
2111 /* ??? (... || i == n_ready). */
2112 gcc_assert (i <= n_ready);
2114 if (top == choice_stack)
2117 if (best < top - choice_stack)
2122 /* Try to find issued privileged insn. */
2123 while (n && !ready_try[--n]);
2126 if (/* If all insns are equally good... */
2128 /* Or a privileged insn will be issued. */
2130 /* Then we have a solution. */
2132 best = top - choice_stack;
2133 /* This is the index of the insn issued first in this
2135 *index = choice_stack [1].index;
2137 if (top->n == max_points || best == all)
2142 /* Set ready-list index to point to the last insn
2143 ('i++' below will advance it to the next insn). */
2149 memcpy (state, top->state, dfa_state_size);
2151 else if (!ready_try [i])
2154 if (tries_num > max_lookahead_tries)
2156 insn = ready_element (ready, i);
2157 delay = state_transition (state, insn);
2160 if (state_dead_lock_p (state))
2166 if (memcmp (top->state, state, dfa_state_size) != 0)
2167 n += ISSUE_POINTS (insn);
2169 /* Advance to the next choice_entry. */
2171 /* Initialize it. */
2172 top->rest = dfa_lookahead;
2175 memcpy (top->state, state, dfa_state_size);
2182 /* Increase ready-list index. */
2186 /* Restore the original state of the DFA. */
2187 memcpy (state, choice_stack->state, dfa_state_size);
2192 /* The following function chooses insn from READY and modifies
2193 READY. The following function is used only for first
2194 cycle multipass scheduling.
2196 -1 if cycle should be advanced,
2197 0 if INSN_PTR is set to point to the desirable insn,
2198 1 if choose_ready () should be restarted without advancing the cycle. */
2200 choose_ready (struct ready_list *ready, rtx *insn_ptr)
2204 if (dbg_cnt (sched_insn) == false)
2208 insn = next_nonnote_insn (last_scheduled_insn);
2210 if (QUEUE_INDEX (insn) == QUEUE_READY)
2211 /* INSN is in the ready_list. */
2213 ready_remove_insn (insn);
2218 /* INSN is in the queue. Advance cycle to move it to the ready list. */
2224 if (targetm.sched.first_cycle_multipass_dfa_lookahead)
2225 lookahead = targetm.sched.first_cycle_multipass_dfa_lookahead ();
2226 if (lookahead <= 0 || SCHED_GROUP_P (ready_element (ready, 0)))
2228 *insn_ptr = ready_remove_first (ready);
2233 /* Try to choose the better insn. */
2234 int index = 0, i, n;
2236 int try_data = 1, try_control = 1;
2239 insn = ready_element (ready, 0);
2240 if (INSN_CODE (insn) < 0)
2242 *insn_ptr = ready_remove_first (ready);
2247 && spec_info->flags & (PREFER_NON_DATA_SPEC
2248 | PREFER_NON_CONTROL_SPEC))
2250 for (i = 0, n = ready->n_ready; i < n; i++)
2255 x = ready_element (ready, i);
2258 if (spec_info->flags & PREFER_NON_DATA_SPEC
2259 && !(s & DATA_SPEC))
2262 if (!(spec_info->flags & PREFER_NON_CONTROL_SPEC)
2267 if (spec_info->flags & PREFER_NON_CONTROL_SPEC
2268 && !(s & CONTROL_SPEC))
2271 if (!(spec_info->flags & PREFER_NON_DATA_SPEC) || !try_data)
2277 ts = TODO_SPEC (insn);
2278 if ((ts & SPECULATIVE)
2279 && (((!try_data && (ts & DATA_SPEC))
2280 || (!try_control && (ts & CONTROL_SPEC)))
2281 || (targetm.sched.first_cycle_multipass_dfa_lookahead_guard_spec
2283 .first_cycle_multipass_dfa_lookahead_guard_spec (insn))))
2284 /* Discard speculative instruction that stands first in the ready
2287 change_queue_index (insn, 1);
2293 for (i = 1; i < ready->n_ready; i++)
2295 insn = ready_element (ready, i);
2298 = ((!try_data && (TODO_SPEC (insn) & DATA_SPEC))
2299 || (!try_control && (TODO_SPEC (insn) & CONTROL_SPEC)));
2302 /* Let the target filter the search space. */
2303 for (i = 1; i < ready->n_ready; i++)
2306 insn = ready_element (ready, i);
2308 gcc_assert (INSN_CODE (insn) >= 0
2309 || recog_memoized (insn) < 0);
2312 = (/* INSN_CODE check can be omitted here as it is also done later
2314 INSN_CODE (insn) < 0
2315 || (targetm.sched.first_cycle_multipass_dfa_lookahead_guard
2316 && !targetm.sched.first_cycle_multipass_dfa_lookahead_guard
2320 if (max_issue (ready, 1, curr_state, &index) == 0)
2322 if (sched_verbose >= 4)
2323 fprintf (sched_dump, ";;\t\tChosen none\n");
2324 *insn_ptr = ready_remove_first (ready);
2329 if (sched_verbose >= 4)
2330 fprintf (sched_dump, ";;\t\tChosen insn : %s\n",
2331 (*current_sched_info->print_insn)
2332 (ready_element (ready, index), 0));
2334 *insn_ptr = ready_remove (ready, index);
2340 /* Use forward list scheduling to rearrange insns of block pointed to by
2341 TARGET_BB, possibly bringing insns from subsequent blocks in the same
2345 schedule_block (basic_block *target_bb)
2347 int i, first_cycle_insn_p;
2349 state_t temp_state = NULL; /* It is used for multipass scheduling. */
2350 int sort_p, advance, start_clock_var;
2352 /* Head/tail info for this block. */
2353 rtx prev_head = current_sched_info->prev_head;
2354 rtx next_tail = current_sched_info->next_tail;
2355 rtx head = NEXT_INSN (prev_head);
2356 rtx tail = PREV_INSN (next_tail);
2358 /* We used to have code to avoid getting parameters moved from hard
2359 argument registers into pseudos.
2361 However, it was removed when it proved to be of marginal benefit
2362 and caused problems because schedule_block and compute_forward_dependences
2363 had different notions of what the "head" insn was. */
2365 gcc_assert (head != tail || INSN_P (head));
2367 haifa_recovery_bb_recently_added_p = false;
2371 dump_new_block_header (0, *target_bb, head, tail);
2373 state_reset (curr_state);
2375 /* Clear the ready list. */
2376 ready.first = ready.veclen - 1;
2379 /* It is used for first cycle multipass scheduling. */
2380 temp_state = alloca (dfa_state_size);
2382 if (targetm.sched.md_init)
2383 targetm.sched.md_init (sched_dump, sched_verbose, ready.veclen);
2385 /* We start inserting insns after PREV_HEAD. */
2386 last_scheduled_insn = prev_head;
2388 gcc_assert (NOTE_P (last_scheduled_insn)
2389 && BLOCK_FOR_INSN (last_scheduled_insn) == *target_bb);
2391 /* Initialize INSN_QUEUE. Q_SIZE is the total number of insns in the
2396 insn_queue = XALLOCAVEC (rtx, max_insn_queue_index + 1);
2397 memset (insn_queue, 0, (max_insn_queue_index + 1) * sizeof (rtx));
2399 /* Start just before the beginning of time. */
2402 /* We need queue and ready lists and clock_var be initialized
2403 in try_ready () (which is called through init_ready_list ()). */
2404 (*current_sched_info->init_ready_list) ();
2406 /* The algorithm is O(n^2) in the number of ready insns at any given
2407 time in the worst case. Before reload we are more likely to have
2408 big lists so truncate them to a reasonable size. */
2409 if (!reload_completed && ready.n_ready > MAX_SCHED_READY_INSNS)
2411 ready_sort (&ready);
2413 /* Find first free-standing insn past MAX_SCHED_READY_INSNS. */
2414 for (i = MAX_SCHED_READY_INSNS; i < ready.n_ready; i++)
2415 if (!SCHED_GROUP_P (ready_element (&ready, i)))
2418 if (sched_verbose >= 2)
2420 fprintf (sched_dump,
2421 ";;\t\tReady list on entry: %d insns\n", ready.n_ready);
2422 fprintf (sched_dump,
2423 ";;\t\t before reload => truncated to %d insns\n", i);
2426 /* Delay all insns past it for 1 cycle. If debug counter is
2427 activated make an exception for the insn right after
2428 last_scheduled_insn. */
2432 if (dbg_cnt (sched_insn) == false)
2433 skip_insn = next_nonnote_insn (last_scheduled_insn);
2435 skip_insn = NULL_RTX;
2437 while (i < ready.n_ready)
2441 insn = ready_remove (&ready, i);
2443 if (insn != skip_insn)
2444 queue_insn (insn, 1);
2449 /* Now we can restore basic block notes and maintain precise cfg. */
2450 restore_bb_notes (*target_bb);
2452 last_clock_var = -1;
2457 /* Loop until all the insns in BB are scheduled. */
2458 while ((*current_sched_info->schedule_more_p) ())
2462 start_clock_var = clock_var;
2466 advance_one_cycle ();
2468 /* Add to the ready list all pending insns that can be issued now.
2469 If there are no ready insns, increment clock until one
2470 is ready and add all pending insns at that point to the ready
2472 queue_to_ready (&ready);
2474 gcc_assert (ready.n_ready);
2476 if (sched_verbose >= 2)
2478 fprintf (sched_dump, ";;\t\tReady list after queue_to_ready: ");
2479 debug_ready_list (&ready);
2481 advance -= clock_var - start_clock_var;
2483 while (advance > 0);
2487 /* Sort the ready list based on priority. */
2488 ready_sort (&ready);
2490 if (sched_verbose >= 2)
2492 fprintf (sched_dump, ";;\t\tReady list after ready_sort: ");
2493 debug_ready_list (&ready);
2497 /* Allow the target to reorder the list, typically for
2498 better instruction bundling. */
2499 if (sort_p && targetm.sched.reorder
2500 && (ready.n_ready == 0
2501 || !SCHED_GROUP_P (ready_element (&ready, 0))))
2503 targetm.sched.reorder (sched_dump, sched_verbose,
2504 ready_lastpos (&ready),
2505 &ready.n_ready, clock_var);
2507 can_issue_more = issue_rate;
2509 first_cycle_insn_p = 1;
2510 cycle_issued_insns = 0;
2517 if (sched_verbose >= 2)
2519 fprintf (sched_dump, ";;\tReady list (t = %3d): ",
2521 debug_ready_list (&ready);
2524 if (ready.n_ready == 0
2526 && reload_completed)
2528 /* Allow scheduling insns directly from the queue in case
2529 there's nothing better to do (ready list is empty) but
2530 there are still vacant dispatch slots in the current cycle. */
2531 if (sched_verbose >= 6)
2532 fprintf (sched_dump,";;\t\tSecond chance\n");
2533 memcpy (temp_state, curr_state, dfa_state_size);
2534 if (early_queue_to_ready (temp_state, &ready))
2535 ready_sort (&ready);
2538 if (ready.n_ready == 0 || !can_issue_more
2539 || state_dead_lock_p (curr_state)
2540 || !(*current_sched_info->schedule_more_p) ())
2543 /* Select and remove the insn from the ready list. */
2549 res = choose_ready (&ready, &insn);
2555 /* Restart choose_ready (). */
2558 gcc_assert (insn != NULL_RTX);
2561 insn = ready_remove_first (&ready);
2563 if (targetm.sched.dfa_new_cycle
2564 && targetm.sched.dfa_new_cycle (sched_dump, sched_verbose,
2565 insn, last_clock_var,
2566 clock_var, &sort_p))
2567 /* SORT_P is used by the target to override sorting
2568 of the ready list. This is needed when the target
2569 has modified its internal structures expecting that
2570 the insn will be issued next. As we need the insn
2571 to have the highest priority (so it will be returned by
2572 the ready_remove_first call above), we invoke
2573 ready_add (&ready, insn, true).
2574 But, still, there is one issue: INSN can be later
2575 discarded by scheduler's front end through
2576 current_sched_info->can_schedule_ready_p, hence, won't
2579 ready_add (&ready, insn, true);
2584 memcpy (temp_state, curr_state, dfa_state_size);
2585 if (recog_memoized (insn) < 0)
2587 asm_p = (GET_CODE (PATTERN (insn)) == ASM_INPUT
2588 || asm_noperands (PATTERN (insn)) >= 0);
2589 if (!first_cycle_insn_p && asm_p)
2590 /* This is asm insn which is tried to be issued on the
2591 cycle not first. Issue it on the next cycle. */
2594 /* A USE insn, or something else we don't need to
2595 understand. We can't pass these directly to
2596 state_transition because it will trigger a
2597 fatal error for unrecognizable insns. */
2602 cost = state_transition (temp_state, insn);
2611 queue_insn (insn, cost);
2612 if (SCHED_GROUP_P (insn))
2621 if (current_sched_info->can_schedule_ready_p
2622 && ! (*current_sched_info->can_schedule_ready_p) (insn))
2623 /* We normally get here only if we don't want to move
2624 insn from the split block. */
2626 TODO_SPEC (insn) = (TODO_SPEC (insn) & ~SPECULATIVE) | HARD_DEP;
2630 /* DECISION is made. */
2632 if (TODO_SPEC (insn) & SPECULATIVE)
2633 generate_recovery_code (insn);
2635 if (control_flow_insn_p (last_scheduled_insn)
2636 /* This is used to switch basic blocks by request
2637 from scheduler front-end (actually, sched-ebb.c only).
2638 This is used to process blocks with single fallthru
2639 edge. If succeeding block has jump, it [jump] will try
2640 move at the end of current bb, thus corrupting CFG. */
2641 || current_sched_info->advance_target_bb (*target_bb, insn))
2643 *target_bb = current_sched_info->advance_target_bb
2650 x = next_real_insn (last_scheduled_insn);
2652 dump_new_block_header (1, *target_bb, x, tail);
2655 last_scheduled_insn = bb_note (*target_bb);
2658 /* Update counters, etc in the scheduler's front end. */
2659 (*current_sched_info->begin_schedule_ready) (insn,
2660 last_scheduled_insn);
2662 move_insn (insn, last_scheduled_insn, current_sched_info->next_tail);
2663 reemit_notes (insn);
2664 last_scheduled_insn = insn;
2666 if (memcmp (curr_state, temp_state, dfa_state_size) != 0)
2668 cycle_issued_insns++;
2669 memcpy (curr_state, temp_state, dfa_state_size);
2672 if (targetm.sched.variable_issue)
2674 targetm.sched.variable_issue (sched_dump, sched_verbose,
2675 insn, can_issue_more);
2676 /* A naked CLOBBER or USE generates no instruction, so do
2677 not count them against the issue rate. */
2678 else if (GET_CODE (PATTERN (insn)) != USE
2679 && GET_CODE (PATTERN (insn)) != CLOBBER)
2682 advance = schedule_insn (insn);
2684 /* After issuing an asm insn we should start a new cycle. */
2685 if (advance == 0 && asm_p)
2690 first_cycle_insn_p = 0;
2692 /* Sort the ready list based on priority. This must be
2693 redone here, as schedule_insn may have readied additional
2694 insns that will not be sorted correctly. */
2695 if (ready.n_ready > 0)
2696 ready_sort (&ready);
2698 if (targetm.sched.reorder2
2699 && (ready.n_ready == 0
2700 || !SCHED_GROUP_P (ready_element (&ready, 0))))
2703 targetm.sched.reorder2 (sched_dump, sched_verbose,
2705 ? ready_lastpos (&ready) : NULL,
2706 &ready.n_ready, clock_var);
2714 fprintf (sched_dump, ";;\tReady list (final): ");
2715 debug_ready_list (&ready);
2718 if (current_sched_info->queue_must_finish_empty)
2719 /* Sanity check -- queue must be empty now. Meaningless if region has
2721 gcc_assert (!q_size && !ready.n_ready);
2724 /* We must maintain QUEUE_INDEX between blocks in region. */
2725 for (i = ready.n_ready - 1; i >= 0; i--)
2729 x = ready_element (&ready, i);
2730 QUEUE_INDEX (x) = QUEUE_NOWHERE;
2731 TODO_SPEC (x) = (TODO_SPEC (x) & ~SPECULATIVE) | HARD_DEP;
2735 for (i = 0; i <= max_insn_queue_index; i++)
2738 for (link = insn_queue[i]; link; link = XEXP (link, 1))
2743 QUEUE_INDEX (x) = QUEUE_NOWHERE;
2744 TODO_SPEC (x) = (TODO_SPEC (x) & ~SPECULATIVE) | HARD_DEP;
2746 free_INSN_LIST_list (&insn_queue[i]);
2751 fprintf (sched_dump, ";; total time = %d\n", clock_var);
2753 if (!current_sched_info->queue_must_finish_empty
2754 || haifa_recovery_bb_recently_added_p)
2756 /* INSN_TICK (minimum clock tick at which the insn becomes
2757 ready) may be not correct for the insn in the subsequent
2758 blocks of the region. We should use a correct value of
2759 `clock_var' or modify INSN_TICK. It is better to keep
2760 clock_var value equal to 0 at the start of a basic block.
2761 Therefore we modify INSN_TICK here. */
2762 fix_inter_tick (NEXT_INSN (prev_head), last_scheduled_insn);
2765 if (targetm.sched.md_finish)
2767 targetm.sched.md_finish (sched_dump, sched_verbose);
2768 /* Target might have added some instructions to the scheduled block
2769 in its md_finish () hook. These new insns don't have any data
2770 initialized and to identify them we extend h_i_d so that they'll
2772 sched_init_luids (NULL, NULL, NULL, NULL);
2776 fprintf (sched_dump, ";; new head = %d\n;; new tail = %d\n\n",
2777 INSN_UID (head), INSN_UID (tail));
2779 /* Update head/tail boundaries. */
2780 head = NEXT_INSN (prev_head);
2781 tail = last_scheduled_insn;
2783 head = restore_other_notes (head, NULL);
2785 current_sched_info->head = head;
2786 current_sched_info->tail = tail;
2789 /* Set_priorities: compute priority of each insn in the block. */
2792 set_priorities (rtx head, rtx tail)
2796 int sched_max_insns_priority =
2797 current_sched_info->sched_max_insns_priority;
2800 if (head == tail && (! INSN_P (head)))
2805 prev_head = PREV_INSN (head);
2806 for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
2812 (void) priority (insn);
2814 gcc_assert (INSN_PRIORITY_KNOWN (insn));
2816 sched_max_insns_priority = MAX (sched_max_insns_priority,
2817 INSN_PRIORITY (insn));
2820 current_sched_info->sched_max_insns_priority = sched_max_insns_priority;
2825 /* Set dump and sched_verbose for the desired debugging output. If no
2826 dump-file was specified, but -fsched-verbose=N (any N), print to stderr.
2827 For -fsched-verbose=N, N>=10, print everything to stderr. */
2829 setup_sched_dump (void)
2831 sched_verbose = sched_verbose_param;
2832 if (sched_verbose_param == 0 && dump_file)
2834 sched_dump = ((sched_verbose_param >= 10 || !dump_file)
2835 ? stderr : dump_file);
2838 /* Initialize some global state for the scheduler. This function works
2839 with the common data shared between all the schedulers. It is called
2840 from the scheduler specific initialization routine. */
2845 /* Disable speculative loads in their presence if cc0 defined. */
2847 flag_schedule_speculative_load = 0;
2850 /* Initialize SPEC_INFO. */
2851 if (targetm.sched.set_sched_flags)
2853 spec_info = &spec_info_var;
2854 targetm.sched.set_sched_flags (spec_info);
2856 if (spec_info->mask != 0)
2858 spec_info->data_weakness_cutoff =
2859 (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF) * MAX_DEP_WEAK) / 100;
2860 spec_info->control_weakness_cutoff =
2861 (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF)
2862 * REG_BR_PROB_BASE) / 100;
2865 /* So we won't read anything accidentally. */
2870 /* So we won't read anything accidentally. */
2873 /* Initialize issue_rate. */
2874 if (targetm.sched.issue_rate)
2875 issue_rate = targetm.sched.issue_rate ();
2879 if (cached_issue_rate != issue_rate)
2881 cached_issue_rate = issue_rate;
2882 /* To invalidate max_lookahead_tries: */
2883 cached_first_cycle_multipass_dfa_lookahead = 0;
2886 if (targetm.sched.first_cycle_multipass_dfa_lookahead)
2887 dfa_lookahead = targetm.sched.first_cycle_multipass_dfa_lookahead ();
2891 if (targetm.sched.init_dfa_pre_cycle_insn)
2892 targetm.sched.init_dfa_pre_cycle_insn ();
2894 if (targetm.sched.init_dfa_post_cycle_insn)
2895 targetm.sched.init_dfa_post_cycle_insn ();
2898 dfa_state_size = state_size ();
2900 init_alias_analysis ();
2902 df_set_flags (DF_LR_RUN_DCE);
2903 df_note_add_problem ();
2905 /* More problems needed for interloop dep calculation in SMS. */
2906 if (common_sched_info->sched_pass_id == SCHED_SMS_PASS)
2908 df_rd_add_problem ();
2909 df_chain_add_problem (DF_DU_CHAIN + DF_UD_CHAIN);
2914 /* Do not run DCE after reload, as this can kill nops inserted
2916 if (reload_completed)
2917 df_clear_flags (DF_LR_RUN_DCE);
2919 regstat_compute_calls_crossed ();
2921 if (targetm.sched.md_init_global)
2922 targetm.sched.md_init_global (sched_dump, sched_verbose,
2923 get_max_uid () + 1);
2925 curr_state = xmalloc (dfa_state_size);
2928 static void haifa_init_only_bb (basic_block, basic_block);
2930 /* Initialize data structures specific to the Haifa scheduler. */
2932 haifa_sched_init (void)
2934 setup_sched_dump ();
2937 if (spec_info != NULL)
2939 sched_deps_info->use_deps_list = 1;
2940 sched_deps_info->generate_spec_deps = 1;
2943 /* Initialize luids, dependency caches, target and h_i_d for the
2946 bb_vec_t bbs = VEC_alloc (basic_block, heap, n_basic_blocks);
2952 VEC_quick_push (basic_block, bbs, bb);
2953 sched_init_luids (bbs, NULL, NULL, NULL);
2954 sched_deps_init (true);
2955 sched_extend_target ();
2956 haifa_init_h_i_d (bbs, NULL, NULL, NULL);
2958 VEC_free (basic_block, heap, bbs);
2961 sched_init_only_bb = haifa_init_only_bb;
2962 sched_split_block = sched_split_block_1;
2963 sched_create_empty_bb = sched_create_empty_bb_1;
2964 haifa_recovery_bb_ever_added_p = false;
2966 #ifdef ENABLE_CHECKING
2967 /* This is used preferably for finding bugs in check_cfg () itself.
2968 We must call sched_bbs_init () before check_cfg () because check_cfg ()
2969 assumes that the last insn in the last bb has a non-null successor. */
2973 nr_begin_data = nr_begin_control = nr_be_in_data = nr_be_in_control = 0;
2974 before_recovery = 0;
2978 /* Finish work with the data specific to the Haifa scheduler. */
2980 haifa_sched_finish (void)
2982 sched_create_empty_bb = NULL;
2983 sched_split_block = NULL;
2984 sched_init_only_bb = NULL;
2986 if (spec_info && spec_info->dump)
2988 char c = reload_completed ? 'a' : 'b';
2990 fprintf (spec_info->dump,
2991 ";; %s:\n", current_function_name ());
2993 fprintf (spec_info->dump,
2994 ";; Procedure %cr-begin-data-spec motions == %d\n",
2996 fprintf (spec_info->dump,
2997 ";; Procedure %cr-be-in-data-spec motions == %d\n",
2999 fprintf (spec_info->dump,
3000 ";; Procedure %cr-begin-control-spec motions == %d\n",
3001 c, nr_begin_control);
3002 fprintf (spec_info->dump,
3003 ";; Procedure %cr-be-in-control-spec motions == %d\n",
3004 c, nr_be_in_control);
3007 /* Finalize h_i_d, dependency caches, and luids for the whole
3008 function. Target will be finalized in md_global_finish (). */
3009 sched_deps_finish ();
3010 sched_finish_luids ();
3011 current_sched_info = NULL;
3015 /* Free global data used during insn scheduling. This function works with
3016 the common data shared between the schedulers. */
3021 haifa_finish_h_i_d ();
3024 if (targetm.sched.md_finish_global)
3025 targetm.sched.md_finish_global (sched_dump, sched_verbose);
3027 end_alias_analysis ();
3029 regstat_free_calls_crossed ();
3033 #ifdef ENABLE_CHECKING
3034 /* After reload ia64 backend clobbers CFG, so can't check anything. */
3035 if (!reload_completed)
3040 /* Fix INSN_TICKs of the instructions in the current block as well as
3041 INSN_TICKs of their dependents.
3042 HEAD and TAIL are the begin and the end of the current scheduled block. */
3044 fix_inter_tick (rtx head, rtx tail)
3046 /* Set of instructions with corrected INSN_TICK. */
3047 bitmap_head processed;
3048 /* ??? It is doubtful if we should assume that cycle advance happens on
3049 basic block boundaries. Basically insns that are unconditionally ready
3050 on the start of the block are more preferable then those which have
3051 a one cycle dependency over insn from the previous block. */
3052 int next_clock = clock_var + 1;
3054 bitmap_initialize (&processed, 0);
3056 /* Iterates over scheduled instructions and fix their INSN_TICKs and
3057 INSN_TICKs of dependent instructions, so that INSN_TICKs are consistent
3058 across different blocks. */
3059 for (tail = NEXT_INSN (tail); head != tail; head = NEXT_INSN (head))
3064 sd_iterator_def sd_it;
3067 tick = INSN_TICK (head);
3068 gcc_assert (tick >= MIN_TICK);
3070 /* Fix INSN_TICK of instruction from just scheduled block. */
3071 if (!bitmap_bit_p (&processed, INSN_LUID (head)))
3073 bitmap_set_bit (&processed, INSN_LUID (head));
3076 if (tick < MIN_TICK)
3079 INSN_TICK (head) = tick;
3082 FOR_EACH_DEP (head, SD_LIST_RES_FORW, sd_it, dep)
3086 next = DEP_CON (dep);
3087 tick = INSN_TICK (next);
3089 if (tick != INVALID_TICK
3090 /* If NEXT has its INSN_TICK calculated, fix it.
3091 If not - it will be properly calculated from
3092 scratch later in fix_tick_ready. */
3093 && !bitmap_bit_p (&processed, INSN_LUID (next)))
3095 bitmap_set_bit (&processed, INSN_LUID (next));
3098 if (tick < MIN_TICK)
3101 if (tick > INTER_TICK (next))
3102 INTER_TICK (next) = tick;
3104 tick = INTER_TICK (next);
3106 INSN_TICK (next) = tick;
3111 bitmap_clear (&processed);
3114 static int haifa_speculate_insn (rtx, ds_t, rtx *);
3116 /* Check if NEXT is ready to be added to the ready or queue list.
3117 If "yes", add it to the proper list.
3119 -1 - is not ready yet,
3120 0 - added to the ready list,
3121 0 < N - queued for N cycles. */
3123 try_ready (rtx next)
3127 ts = &TODO_SPEC (next);
3130 gcc_assert (!(old_ts & ~(SPECULATIVE | HARD_DEP))
3131 && ((old_ts & HARD_DEP)
3132 || (old_ts & SPECULATIVE)));
3134 if (sd_lists_empty_p (next, SD_LIST_BACK))
3135 /* NEXT has all its dependencies resolved. */
3137 /* Remove HARD_DEP bit from NEXT's status. */
3140 if (current_sched_info->flags & DO_SPECULATION)
3141 /* Remove all speculative bits from NEXT's status. */
3142 *ts &= ~SPECULATIVE;
3146 /* One of the NEXT's dependencies has been resolved.
3147 Recalculate NEXT's status. */
3149 *ts &= ~SPECULATIVE & ~HARD_DEP;
3151 if (sd_lists_empty_p (next, SD_LIST_HARD_BACK))
3152 /* Now we've got NEXT with speculative deps only.
3153 1. Look at the deps to see what we have to do.
3154 2. Check if we can do 'todo'. */
3156 sd_iterator_def sd_it;
3158 bool first_p = true;
3160 FOR_EACH_DEP (next, SD_LIST_BACK, sd_it, dep)
3162 ds_t ds = DEP_STATUS (dep) & SPECULATIVE;
3171 *ts = ds_merge (*ts, ds);
3174 if (ds_weak (*ts) < spec_info->data_weakness_cutoff)
3175 /* Too few points. */
3176 *ts = (*ts & ~SPECULATIVE) | HARD_DEP;
3183 gcc_assert (*ts == old_ts
3184 && QUEUE_INDEX (next) == QUEUE_NOWHERE);
3185 else if (current_sched_info->new_ready)
3186 *ts = current_sched_info->new_ready (next, *ts);
3188 /* * if !(old_ts & SPECULATIVE) (e.g. HARD_DEP or 0), then insn might
3189 have its original pattern or changed (speculative) one. This is due
3190 to changing ebb in region scheduling.
3191 * But if (old_ts & SPECULATIVE), then we are pretty sure that insn
3192 has speculative pattern.
3194 We can't assert (!(*ts & HARD_DEP) || *ts == old_ts) here because
3195 control-speculative NEXT could have been discarded by sched-rgn.c
3196 (the same case as when discarded by can_schedule_ready_p ()). */
3198 if ((*ts & SPECULATIVE)
3199 /* If (old_ts == *ts), then (old_ts & SPECULATIVE) and we don't
3200 need to change anything. */
3206 gcc_assert ((*ts & SPECULATIVE) && !(*ts & ~SPECULATIVE));
3208 res = haifa_speculate_insn (next, *ts, &new_pat);
3213 /* It would be nice to change DEP_STATUS of all dependences,
3214 which have ((DEP_STATUS & SPECULATIVE) == *ts) to HARD_DEP,
3215 so we won't reanalyze anything. */
3216 *ts = (*ts & ~SPECULATIVE) | HARD_DEP;
3220 /* We follow the rule, that every speculative insn
3221 has non-null ORIG_PAT. */
3222 if (!ORIG_PAT (next))
3223 ORIG_PAT (next) = PATTERN (next);
3227 if (!ORIG_PAT (next))
3228 /* If we gonna to overwrite the original pattern of insn,
3230 ORIG_PAT (next) = PATTERN (next);
3232 haifa_change_pattern (next, new_pat);
3240 /* We need to restore pattern only if (*ts == 0), because otherwise it is
3241 either correct (*ts & SPECULATIVE),
3242 or we simply don't care (*ts & HARD_DEP). */
3244 gcc_assert (!ORIG_PAT (next)
3245 || !IS_SPECULATION_BRANCHY_CHECK_P (next));
3249 /* We can't assert (QUEUE_INDEX (next) == QUEUE_NOWHERE) here because
3250 control-speculative NEXT could have been discarded by sched-rgn.c
3251 (the same case as when discarded by can_schedule_ready_p ()). */
3252 /*gcc_assert (QUEUE_INDEX (next) == QUEUE_NOWHERE);*/
3254 change_queue_index (next, QUEUE_NOWHERE);
3257 else if (!(*ts & BEGIN_SPEC) && ORIG_PAT (next) && !IS_SPECULATION_CHECK_P (next))
3258 /* We should change pattern of every previously speculative
3259 instruction - and we determine if NEXT was speculative by using
3260 ORIG_PAT field. Except one case - speculation checks have ORIG_PAT
3261 pat too, so skip them. */
3263 haifa_change_pattern (next, ORIG_PAT (next));
3264 ORIG_PAT (next) = 0;
3267 if (sched_verbose >= 2)
3269 int s = TODO_SPEC (next);
3271 fprintf (sched_dump, ";;\t\tdependencies resolved: insn %s",
3272 (*current_sched_info->print_insn) (next, 0));
3274 if (spec_info && spec_info->dump)
3277 fprintf (spec_info->dump, "; data-spec;");
3278 if (s & BEGIN_CONTROL)
3279 fprintf (spec_info->dump, "; control-spec;");
3280 if (s & BE_IN_CONTROL)
3281 fprintf (spec_info->dump, "; in-control-spec;");
3284 fprintf (sched_dump, "\n");
3287 adjust_priority (next);
3289 return fix_tick_ready (next);
3292 /* Calculate INSN_TICK of NEXT and add it to either ready or queue list. */
3294 fix_tick_ready (rtx next)
3298 if (!sd_lists_empty_p (next, SD_LIST_RES_BACK))
3301 sd_iterator_def sd_it;
3304 tick = INSN_TICK (next);
3305 /* if tick is not equal to INVALID_TICK, then update
3306 INSN_TICK of NEXT with the most recent resolved dependence
3307 cost. Otherwise, recalculate from scratch. */
3308 full_p = (tick == INVALID_TICK);
3310 FOR_EACH_DEP (next, SD_LIST_RES_BACK, sd_it, dep)
3312 rtx pro = DEP_PRO (dep);
3315 gcc_assert (INSN_TICK (pro) >= MIN_TICK);
3317 tick1 = INSN_TICK (pro) + dep_cost (dep);
3328 INSN_TICK (next) = tick;
3330 delay = tick - clock_var;
3332 delay = QUEUE_READY;
3334 change_queue_index (next, delay);
3339 /* Move NEXT to the proper queue list with (DELAY >= 1),
3340 or add it to the ready list (DELAY == QUEUE_READY),
3341 or remove it from ready and queue lists at all (DELAY == QUEUE_NOWHERE). */
3343 change_queue_index (rtx next, int delay)
3345 int i = QUEUE_INDEX (next);
3347 gcc_assert (QUEUE_NOWHERE <= delay && delay <= max_insn_queue_index
3349 gcc_assert (i != QUEUE_SCHEDULED);
3351 if ((delay > 0 && NEXT_Q_AFTER (q_ptr, delay) == i)
3352 || (delay < 0 && delay == i))
3353 /* We have nothing to do. */
3356 /* Remove NEXT from wherever it is now. */
3357 if (i == QUEUE_READY)
3358 ready_remove_insn (next);
3360 queue_remove (next);
3362 /* Add it to the proper place. */
3363 if (delay == QUEUE_READY)
3364 ready_add (readyp, next, false);
3365 else if (delay >= 1)
3366 queue_insn (next, delay);
3368 if (sched_verbose >= 2)
3370 fprintf (sched_dump, ";;\t\ttick updated: insn %s",
3371 (*current_sched_info->print_insn) (next, 0));
3373 if (delay == QUEUE_READY)
3374 fprintf (sched_dump, " into ready\n");
3375 else if (delay >= 1)
3376 fprintf (sched_dump, " into queue with cost=%d\n", delay);
3378 fprintf (sched_dump, " removed from ready or queue lists\n");
3382 static int sched_ready_n_insns = -1;
3384 /* Initialize per region data structures. */
3386 sched_extend_ready_list (int new_sched_ready_n_insns)
3390 if (sched_ready_n_insns == -1)
3391 /* At the first call we need to initialize one more choice_stack
3395 sched_ready_n_insns = 0;
3398 i = sched_ready_n_insns + 1;
3400 ready.veclen = new_sched_ready_n_insns + issue_rate;
3401 ready.vec = XRESIZEVEC (rtx, ready.vec, ready.veclen);
3403 gcc_assert (new_sched_ready_n_insns >= sched_ready_n_insns);
3405 ready_try = (char *) xrecalloc (ready_try, new_sched_ready_n_insns,
3406 sched_ready_n_insns, sizeof (*ready_try));
3408 /* We allocate +1 element to save initial state in the choice_stack[0]
3410 choice_stack = XRESIZEVEC (struct choice_entry, choice_stack,
3411 new_sched_ready_n_insns + 1);
3413 for (; i <= new_sched_ready_n_insns; i++)
3414 choice_stack[i].state = xmalloc (dfa_state_size);
3416 sched_ready_n_insns = new_sched_ready_n_insns;
3419 /* Free per region data structures. */
3421 sched_finish_ready_list (void)
3432 for (i = 0; i <= sched_ready_n_insns; i++)
3433 free (choice_stack [i].state);
3434 free (choice_stack);
3435 choice_stack = NULL;
3437 sched_ready_n_insns = -1;
3441 haifa_luid_for_non_insn (rtx x)
3443 gcc_assert (NOTE_P (x) || LABEL_P (x));
3448 /* Generates recovery code for INSN. */
3450 generate_recovery_code (rtx insn)
3452 if (TODO_SPEC (insn) & BEGIN_SPEC)
3453 begin_speculative_block (insn);
3455 /* Here we have insn with no dependencies to
3456 instructions other then CHECK_SPEC ones. */
3458 if (TODO_SPEC (insn) & BE_IN_SPEC)
3459 add_to_speculative_block (insn);
3463 Tries to add speculative dependencies of type FS between instructions
3464 in deps_list L and TWIN. */
3466 process_insn_forw_deps_be_in_spec (rtx insn, rtx twin, ds_t fs)
3468 sd_iterator_def sd_it;
3471 FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
3476 consumer = DEP_CON (dep);
3478 ds = DEP_STATUS (dep);
3480 if (/* If we want to create speculative dep. */
3482 /* And we can do that because this is a true dep. */
3483 && (ds & DEP_TYPES) == DEP_TRUE)
3485 gcc_assert (!(ds & BE_IN_SPEC));
3487 if (/* If this dep can be overcome with 'begin speculation'. */
3489 /* Then we have a choice: keep the dep 'begin speculative'
3490 or transform it into 'be in speculative'. */
3492 if (/* In try_ready we assert that if insn once became ready
3493 it can be removed from the ready (or queue) list only
3494 due to backend decision. Hence we can't let the
3495 probability of the speculative dep to decrease. */
3496 ds_weak (ds) <= ds_weak (fs))
3500 new_ds = (ds & ~BEGIN_SPEC) | fs;
3502 if (/* consumer can 'be in speculative'. */
3503 sched_insn_is_legitimate_for_speculation_p (consumer,
3505 /* Transform it to be in speculative. */
3510 /* Mark the dep as 'be in speculative'. */
3515 dep_def _new_dep, *new_dep = &_new_dep;
3517 init_dep_1 (new_dep, twin, consumer, DEP_TYPE (dep), ds);
3518 sd_add_dep (new_dep, false);
3523 /* Generates recovery code for BEGIN speculative INSN. */
3525 begin_speculative_block (rtx insn)
3527 if (TODO_SPEC (insn) & BEGIN_DATA)
3529 if (TODO_SPEC (insn) & BEGIN_CONTROL)
3532 create_check_block_twin (insn, false);
3534 TODO_SPEC (insn) &= ~BEGIN_SPEC;
3537 static void haifa_init_insn (rtx);
3539 /* Generates recovery code for BE_IN speculative INSN. */
3541 add_to_speculative_block (rtx insn)
3544 sd_iterator_def sd_it;
3547 rtx_vec_t priorities_roots;
3549 ts = TODO_SPEC (insn);
3550 gcc_assert (!(ts & ~BE_IN_SPEC));
3552 if (ts & BE_IN_DATA)
3554 if (ts & BE_IN_CONTROL)
3557 TODO_SPEC (insn) &= ~BE_IN_SPEC;
3558 gcc_assert (!TODO_SPEC (insn));
3560 DONE_SPEC (insn) |= ts;
3562 /* First we convert all simple checks to branchy. */
3563 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
3564 sd_iterator_cond (&sd_it, &dep);)
3566 rtx check = DEP_PRO (dep);
3568 if (IS_SPECULATION_SIMPLE_CHECK_P (check))
3570 create_check_block_twin (check, true);
3572 /* Restart search. */
3573 sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
3576 /* Continue search. */
3577 sd_iterator_next (&sd_it);
3580 priorities_roots = NULL;
3581 clear_priorities (insn, &priorities_roots);
3588 /* Get the first backward dependency of INSN. */
3589 sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
3590 if (!sd_iterator_cond (&sd_it, &dep))
3591 /* INSN has no backward dependencies left. */
3594 gcc_assert ((DEP_STATUS (dep) & BEGIN_SPEC) == 0
3595 && (DEP_STATUS (dep) & BE_IN_SPEC) != 0
3596 && (DEP_STATUS (dep) & DEP_TYPES) == DEP_TRUE);
3598 check = DEP_PRO (dep);
3600 gcc_assert (!IS_SPECULATION_CHECK_P (check) && !ORIG_PAT (check)
3601 && QUEUE_INDEX (check) == QUEUE_NOWHERE);
3603 rec = BLOCK_FOR_INSN (check);
3605 twin = emit_insn_before (copy_insn (PATTERN (insn)), BB_END (rec));
3606 haifa_init_insn (twin);
3608 sd_copy_back_deps (twin, insn, true);
3610 if (sched_verbose && spec_info->dump)
3611 /* INSN_BB (insn) isn't determined for twin insns yet.
3612 So we can't use current_sched_info->print_insn. */
3613 fprintf (spec_info->dump, ";;\t\tGenerated twin insn : %d/rec%d\n",
3614 INSN_UID (twin), rec->index);
3616 twins = alloc_INSN_LIST (twin, twins);
3618 /* Add dependences between TWIN and all appropriate
3619 instructions from REC. */
3620 FOR_EACH_DEP (insn, SD_LIST_SPEC_BACK, sd_it, dep)
3622 rtx pro = DEP_PRO (dep);
3624 gcc_assert (DEP_TYPE (dep) == REG_DEP_TRUE);
3626 /* INSN might have dependencies from the instructions from
3627 several recovery blocks. At this iteration we process those
3628 producers that reside in REC. */
3629 if (BLOCK_FOR_INSN (pro) == rec)
3631 dep_def _new_dep, *new_dep = &_new_dep;
3633 init_dep (new_dep, pro, twin, REG_DEP_TRUE);
3634 sd_add_dep (new_dep, false);
3638 process_insn_forw_deps_be_in_spec (insn, twin, ts);
3640 /* Remove all dependencies between INSN and insns in REC. */
3641 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
3642 sd_iterator_cond (&sd_it, &dep);)
3644 rtx pro = DEP_PRO (dep);
3646 if (BLOCK_FOR_INSN (pro) == rec)
3647 sd_delete_dep (sd_it);
3649 sd_iterator_next (&sd_it);
3653 /* We couldn't have added the dependencies between INSN and TWINS earlier
3654 because that would make TWINS appear in the INSN_BACK_DEPS (INSN). */
3659 twin = XEXP (twins, 0);
3662 dep_def _new_dep, *new_dep = &_new_dep;
3664 init_dep (new_dep, insn, twin, REG_DEP_OUTPUT);
3665 sd_add_dep (new_dep, false);
3668 twin = XEXP (twins, 1);
3669 free_INSN_LIST_node (twins);
3673 calc_priorities (priorities_roots);
3674 VEC_free (rtx, heap, priorities_roots);
3677 /* Extends and fills with zeros (only the new part) array pointed to by P. */
3679 xrecalloc (void *p, size_t new_nmemb, size_t old_nmemb, size_t size)
3681 gcc_assert (new_nmemb >= old_nmemb);
3682 p = XRESIZEVAR (void, p, new_nmemb * size);
3683 memset (((char *) p) + old_nmemb * size, 0, (new_nmemb - old_nmemb) * size);
3688 Find fallthru edge from PRED. */
3690 find_fallthru_edge (basic_block pred)
3696 succ = pred->next_bb;
3697 gcc_assert (succ->prev_bb == pred);
3699 if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds))
3701 FOR_EACH_EDGE (e, ei, pred->succs)
3702 if (e->flags & EDGE_FALLTHRU)
3704 gcc_assert (e->dest == succ);
3710 FOR_EACH_EDGE (e, ei, succ->preds)
3711 if (e->flags & EDGE_FALLTHRU)
3713 gcc_assert (e->src == pred);
3721 /* Extend per basic block data structures. */
3723 sched_extend_bb (void)
3727 /* The following is done to keep current_sched_info->next_tail non null. */
3728 insn = BB_END (EXIT_BLOCK_PTR->prev_bb);
3729 if (NEXT_INSN (insn) == 0
3732 /* Don't emit a NOTE if it would end up before a BARRIER. */
3733 && !BARRIER_P (NEXT_INSN (insn))))
3735 rtx note = emit_note_after (NOTE_INSN_DELETED, insn);
3736 /* Make insn appear outside BB. */
3737 set_block_for_insn (note, NULL);
3738 BB_END (EXIT_BLOCK_PTR->prev_bb) = insn;
3742 /* Init per basic block data structures. */
3744 sched_init_bbs (void)
3749 /* Initialize BEFORE_RECOVERY variable. */
3751 init_before_recovery (basic_block *before_recovery_ptr)
3756 last = EXIT_BLOCK_PTR->prev_bb;
3757 e = find_fallthru_edge (last);
3761 /* We create two basic blocks:
3762 1. Single instruction block is inserted right after E->SRC
3764 2. Empty block right before EXIT_BLOCK.
3765 Between these two blocks recovery blocks will be emitted. */
3767 basic_block single, empty;
3770 /* If the fallthrough edge to exit we've found is from the block we've
3771 created before, don't do anything more. */
3772 if (last == after_recovery)
3775 adding_bb_to_current_region_p = false;
3777 single = sched_create_empty_bb (last);
3778 empty = sched_create_empty_bb (single);
3780 /* Add new blocks to the root loop. */
3781 if (current_loops != NULL)
3783 add_bb_to_loop (single, VEC_index (loop_p, current_loops->larray, 0));
3784 add_bb_to_loop (empty, VEC_index (loop_p, current_loops->larray, 0));
3787 single->count = last->count;
3788 empty->count = last->count;
3789 single->frequency = last->frequency;
3790 empty->frequency = last->frequency;
3791 BB_COPY_PARTITION (single, last);
3792 BB_COPY_PARTITION (empty, last);
3794 redirect_edge_succ (e, single);
3795 make_single_succ_edge (single, empty, 0);
3796 make_single_succ_edge (empty, EXIT_BLOCK_PTR,
3797 EDGE_FALLTHRU | EDGE_CAN_FALLTHRU);
3799 label = block_label (empty);
3800 x = emit_jump_insn_after (gen_jump (label), BB_END (single));
3801 JUMP_LABEL (x) = label;
3802 LABEL_NUSES (label)++;
3803 haifa_init_insn (x);
3805 emit_barrier_after (x);
3807 sched_init_only_bb (empty, NULL);
3808 sched_init_only_bb (single, NULL);
3811 adding_bb_to_current_region_p = true;
3812 before_recovery = single;
3813 after_recovery = empty;
3815 if (before_recovery_ptr)
3816 *before_recovery_ptr = before_recovery;
3818 if (sched_verbose >= 2 && spec_info->dump)
3819 fprintf (spec_info->dump,
3820 ";;\t\tFixed fallthru to EXIT : %d->>%d->%d->>EXIT\n",
3821 last->index, single->index, empty->index);
3824 before_recovery = last;
3827 /* Returns new recovery block. */
3829 sched_create_recovery_block (basic_block *before_recovery_ptr)
3835 haifa_recovery_bb_recently_added_p = true;
3836 haifa_recovery_bb_ever_added_p = true;
3838 init_before_recovery (before_recovery_ptr);
3840 barrier = get_last_bb_insn (before_recovery);
3841 gcc_assert (BARRIER_P (barrier));
3843 label = emit_label_after (gen_label_rtx (), barrier);
3845 rec = create_basic_block (label, label, before_recovery);
3847 /* A recovery block always ends with an unconditional jump. */
3848 emit_barrier_after (BB_END (rec));
3850 if (BB_PARTITION (before_recovery) != BB_UNPARTITIONED)
3851 BB_SET_PARTITION (rec, BB_COLD_PARTITION);
3853 if (sched_verbose && spec_info->dump)
3854 fprintf (spec_info->dump, ";;\t\tGenerated recovery block rec%d\n",
3860 /* Create edges: FIRST_BB -> REC; FIRST_BB -> SECOND_BB; REC -> SECOND_BB
3861 and emit necessary jumps. */
3863 sched_create_recovery_edges (basic_block first_bb, basic_block rec,
3864 basic_block second_bb)
3871 /* This is fixing of incoming edge. */
3872 /* ??? Which other flags should be specified? */
3873 if (BB_PARTITION (first_bb) != BB_PARTITION (rec))
3874 /* Partition type is the same, if it is "unpartitioned". */
3875 edge_flags = EDGE_CROSSING;
3879 e = make_edge (first_bb, rec, edge_flags);
3880 label = block_label (second_bb);
3881 jump = emit_jump_insn_after (gen_jump (label), BB_END (rec));
3882 JUMP_LABEL (jump) = label;
3883 LABEL_NUSES (label)++;
3885 if (BB_PARTITION (second_bb) != BB_PARTITION (rec))
3886 /* Partition type is the same, if it is "unpartitioned". */
3888 /* Rewritten from cfgrtl.c. */
3889 if (flag_reorder_blocks_and_partition
3890 && targetm.have_named_sections)
3891 /* We don't need the same note for the check because
3892 any_condjump_p (check) == true. */
3894 REG_NOTES (jump) = gen_rtx_EXPR_LIST (REG_CROSSING_JUMP,
3898 edge_flags = EDGE_CROSSING;
3903 make_single_succ_edge (rec, second_bb, edge_flags);
3906 /* This function creates recovery code for INSN. If MUTATE_P is nonzero,
3907 INSN is a simple check, that should be converted to branchy one. */
3909 create_check_block_twin (rtx insn, bool mutate_p)
3912 rtx label, check, twin;
3914 sd_iterator_def sd_it;
3916 dep_def _new_dep, *new_dep = &_new_dep;
3919 gcc_assert (ORIG_PAT (insn) != NULL_RTX);
3922 todo_spec = TODO_SPEC (insn);
3925 gcc_assert (IS_SPECULATION_SIMPLE_CHECK_P (insn)
3926 && (TODO_SPEC (insn) & SPECULATIVE) == 0);
3928 todo_spec = CHECK_SPEC (insn);
3931 todo_spec &= SPECULATIVE;
3933 /* Create recovery block. */
3934 if (mutate_p || targetm.sched.needs_block_p (insn))
3936 rec = sched_create_recovery_block (NULL);
3937 label = BB_HEAD (rec);
3941 rec = EXIT_BLOCK_PTR;
3946 check = targetm.sched.gen_spec_check (insn, label, mutate_p);
3948 if (rec != EXIT_BLOCK_PTR)
3950 /* To have mem_reg alive at the beginning of second_bb,
3951 we emit check BEFORE insn, so insn after splitting
3952 insn will be at the beginning of second_bb, which will
3953 provide us with the correct life information. */
3954 check = emit_jump_insn_before (check, insn);
3955 JUMP_LABEL (check) = label;
3956 LABEL_NUSES (label)++;
3959 check = emit_insn_before (check, insn);
3961 /* Extend data structures. */
3962 haifa_init_insn (check);
3964 /* CHECK is being added to current region. Extend ready list. */
3965 gcc_assert (sched_ready_n_insns != -1);
3966 sched_extend_ready_list (sched_ready_n_insns + 1);
3968 if (current_sched_info->add_remove_insn)
3969 current_sched_info->add_remove_insn (insn, 0);
3971 RECOVERY_BLOCK (check) = rec;
3973 if (sched_verbose && spec_info->dump)
3974 fprintf (spec_info->dump, ";;\t\tGenerated check insn : %s\n",
3975 (*current_sched_info->print_insn) (check, 0));
3977 gcc_assert (ORIG_PAT (insn));
3979 /* Initialize TWIN (twin is a duplicate of original instruction
3980 in the recovery block). */
3981 if (rec != EXIT_BLOCK_PTR)
3983 sd_iterator_def sd_it;
3986 FOR_EACH_DEP (insn, SD_LIST_RES_BACK, sd_it, dep)
3987 if ((DEP_STATUS (dep) & DEP_OUTPUT) != 0)
3989 struct _dep _dep2, *dep2 = &_dep2;
3991 init_dep (dep2, DEP_PRO (dep), check, REG_DEP_TRUE);
3993 sd_add_dep (dep2, true);
3996 twin = emit_insn_after (ORIG_PAT (insn), BB_END (rec));
3997 haifa_init_insn (twin);
3999 if (sched_verbose && spec_info->dump)
4000 /* INSN_BB (insn) isn't determined for twin insns yet.
4001 So we can't use current_sched_info->print_insn. */
4002 fprintf (spec_info->dump, ";;\t\tGenerated twin insn : %d/rec%d\n",
4003 INSN_UID (twin), rec->index);
4007 ORIG_PAT (check) = ORIG_PAT (insn);
4008 HAS_INTERNAL_DEP (check) = 1;
4010 /* ??? We probably should change all OUTPUT dependencies to
4014 /* Copy all resolved back dependencies of INSN to TWIN. This will
4015 provide correct value for INSN_TICK (TWIN). */
4016 sd_copy_back_deps (twin, insn, true);
4018 if (rec != EXIT_BLOCK_PTR)
4019 /* In case of branchy check, fix CFG. */
4021 basic_block first_bb, second_bb;
4024 first_bb = BLOCK_FOR_INSN (check);
4025 second_bb = sched_split_block (first_bb, check);
4027 sched_create_recovery_edges (first_bb, rec, second_bb);
4029 sched_init_only_bb (second_bb, first_bb);
4030 sched_init_only_bb (rec, EXIT_BLOCK_PTR);
4032 jump = BB_END (rec);
4033 haifa_init_insn (jump);
4036 /* Move backward dependences from INSN to CHECK and
4037 move forward dependences from INSN to TWIN. */
4039 /* First, create dependencies between INSN's producers and CHECK & TWIN. */
4040 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
4042 rtx pro = DEP_PRO (dep);
4045 /* If BEGIN_DATA: [insn ~~TRUE~~> producer]:
4046 check --TRUE--> producer ??? or ANTI ???
4047 twin --TRUE--> producer
4048 twin --ANTI--> check
4050 If BEGIN_CONTROL: [insn ~~ANTI~~> producer]:
4051 check --ANTI--> producer
4052 twin --ANTI--> producer
4053 twin --ANTI--> check
4055 If BE_IN_SPEC: [insn ~~TRUE~~> producer]:
4056 check ~~TRUE~~> producer
4057 twin ~~TRUE~~> producer
4058 twin --ANTI--> check */
4060 ds = DEP_STATUS (dep);
4062 if (ds & BEGIN_SPEC)
4064 gcc_assert (!mutate_p);
4068 init_dep_1 (new_dep, pro, check, DEP_TYPE (dep), ds);
4069 sd_add_dep (new_dep, false);
4071 if (rec != EXIT_BLOCK_PTR)
4073 DEP_CON (new_dep) = twin;
4074 sd_add_dep (new_dep, false);
4078 /* Second, remove backward dependencies of INSN. */
4079 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
4080 sd_iterator_cond (&sd_it, &dep);)
4082 if ((DEP_STATUS (dep) & BEGIN_SPEC)
4084 /* We can delete this dep because we overcome it with
4085 BEGIN_SPECULATION. */
4086 sd_delete_dep (sd_it);
4088 sd_iterator_next (&sd_it);
4091 /* Future Speculations. Determine what BE_IN speculations will be like. */
4094 /* Fields (DONE_SPEC (x) & BEGIN_SPEC) and CHECK_SPEC (x) are set only
4097 gcc_assert (!DONE_SPEC (insn));
4101 ds_t ts = TODO_SPEC (insn);
4103 DONE_SPEC (insn) = ts & BEGIN_SPEC;
4104 CHECK_SPEC (check) = ts & BEGIN_SPEC;
4106 /* Luckiness of future speculations solely depends upon initial
4107 BEGIN speculation. */
4108 if (ts & BEGIN_DATA)
4109 fs = set_dep_weak (fs, BE_IN_DATA, get_dep_weak (ts, BEGIN_DATA));
4110 if (ts & BEGIN_CONTROL)
4111 fs = set_dep_weak (fs, BE_IN_CONTROL,
4112 get_dep_weak (ts, BEGIN_CONTROL));
4115 CHECK_SPEC (check) = CHECK_SPEC (insn);
4117 /* Future speculations: call the helper. */
4118 process_insn_forw_deps_be_in_spec (insn, twin, fs);
4120 if (rec != EXIT_BLOCK_PTR)
4122 /* Which types of dependencies should we use here is,
4123 generally, machine-dependent question... But, for now,
4128 init_dep (new_dep, insn, check, REG_DEP_TRUE);
4129 sd_add_dep (new_dep, false);
4131 init_dep (new_dep, insn, twin, REG_DEP_OUTPUT);
4132 sd_add_dep (new_dep, false);
4136 if (spec_info->dump)
4137 fprintf (spec_info->dump, ";;\t\tRemoved simple check : %s\n",
4138 (*current_sched_info->print_insn) (insn, 0));
4140 /* Remove all dependencies of the INSN. */
4142 sd_it = sd_iterator_start (insn, (SD_LIST_FORW
4144 | SD_LIST_RES_BACK));
4145 while (sd_iterator_cond (&sd_it, &dep))
4146 sd_delete_dep (sd_it);
4149 /* If former check (INSN) already was moved to the ready (or queue)
4150 list, add new check (CHECK) there too. */
4151 if (QUEUE_INDEX (insn) != QUEUE_NOWHERE)
4154 /* Remove old check from instruction stream and free its
4156 sched_remove_insn (insn);
4159 init_dep (new_dep, check, twin, REG_DEP_ANTI);
4160 sd_add_dep (new_dep, false);
4164 init_dep_1 (new_dep, insn, check, REG_DEP_TRUE, DEP_TRUE | DEP_OUTPUT);
4165 sd_add_dep (new_dep, false);
4169 /* Fix priorities. If MUTATE_P is nonzero, this is not necessary,
4170 because it'll be done later in add_to_speculative_block. */
4172 rtx_vec_t priorities_roots = NULL;
4174 clear_priorities (twin, &priorities_roots);
4175 calc_priorities (priorities_roots);
4176 VEC_free (rtx, heap, priorities_roots);
4180 /* Removes dependency between instructions in the recovery block REC
4181 and usual region instructions. It keeps inner dependences so it
4182 won't be necessary to recompute them. */
4184 fix_recovery_deps (basic_block rec)
4186 rtx note, insn, jump, ready_list = 0;
4187 bitmap_head in_ready;
4190 bitmap_initialize (&in_ready, 0);
4192 /* NOTE - a basic block note. */
4193 note = NEXT_INSN (BB_HEAD (rec));
4194 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
4195 insn = BB_END (rec);
4196 gcc_assert (JUMP_P (insn));
4197 insn = PREV_INSN (insn);
4201 sd_iterator_def sd_it;
4204 for (sd_it = sd_iterator_start (insn, SD_LIST_FORW);
4205 sd_iterator_cond (&sd_it, &dep);)
4207 rtx consumer = DEP_CON (dep);
4209 if (BLOCK_FOR_INSN (consumer) != rec)
4211 sd_delete_dep (sd_it);
4213 if (!bitmap_bit_p (&in_ready, INSN_LUID (consumer)))
4215 ready_list = alloc_INSN_LIST (consumer, ready_list);
4216 bitmap_set_bit (&in_ready, INSN_LUID (consumer));
4221 gcc_assert ((DEP_STATUS (dep) & DEP_TYPES) == DEP_TRUE);
4223 sd_iterator_next (&sd_it);
4227 insn = PREV_INSN (insn);
4229 while (insn != note);
4231 bitmap_clear (&in_ready);
4233 /* Try to add instructions to the ready or queue list. */
4234 for (link = ready_list; link; link = XEXP (link, 1))
4235 try_ready (XEXP (link, 0));
4236 free_INSN_LIST_list (&ready_list);
4238 /* Fixing jump's dependences. */
4239 insn = BB_HEAD (rec);
4240 jump = BB_END (rec);
4242 gcc_assert (LABEL_P (insn));
4243 insn = NEXT_INSN (insn);
4245 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
4246 add_jump_dependencies (insn, jump);
4249 /* Change pattern of INSN to NEW_PAT. */
4251 sched_change_pattern (rtx insn, rtx new_pat)
4255 t = validate_change (insn, &PATTERN (insn), new_pat, 0);
4257 dfa_clear_single_insn_cache (insn);
4260 /* Change pattern of INSN to NEW_PAT. Invalidate cached haifa
4261 instruction data. */
4263 haifa_change_pattern (rtx insn, rtx new_pat)
4265 sched_change_pattern (insn, new_pat);
4267 /* Invalidate INSN_COST, so it'll be recalculated. */
4268 INSN_COST (insn) = -1;
4269 /* Invalidate INSN_TICK, so it'll be recalculated. */
4270 INSN_TICK (insn) = INVALID_TICK;
4273 /* -1 - can't speculate,
4274 0 - for speculation with REQUEST mode it is OK to use
4275 current instruction pattern,
4276 1 - need to change pattern for *NEW_PAT to be speculative. */
4278 sched_speculate_insn (rtx insn, ds_t request, rtx *new_pat)
4280 gcc_assert (current_sched_info->flags & DO_SPECULATION
4281 && (request & SPECULATIVE)
4282 && sched_insn_is_legitimate_for_speculation_p (insn, request));
4284 if ((request & spec_info->mask) != request)
4287 if (request & BE_IN_SPEC
4288 && !(request & BEGIN_SPEC))
4291 return targetm.sched.speculate_insn (insn, request, new_pat);
4295 haifa_speculate_insn (rtx insn, ds_t request, rtx *new_pat)
4297 gcc_assert (sched_deps_info->generate_spec_deps
4298 && !IS_SPECULATION_CHECK_P (insn));
4300 if (HAS_INTERNAL_DEP (insn)
4301 || SCHED_GROUP_P (insn))
4304 return sched_speculate_insn (insn, request, new_pat);
4307 /* Print some information about block BB, which starts with HEAD and
4308 ends with TAIL, before scheduling it.
4309 I is zero, if scheduler is about to start with the fresh ebb. */
4311 dump_new_block_header (int i, basic_block bb, rtx head, rtx tail)
4314 fprintf (sched_dump,
4315 ";; ======================================================\n");
4317 fprintf (sched_dump,
4318 ";; =====================ADVANCING TO=====================\n");
4319 fprintf (sched_dump,
4320 ";; -- basic block %d from %d to %d -- %s reload\n",
4321 bb->index, INSN_UID (head), INSN_UID (tail),
4322 (reload_completed ? "after" : "before"));
4323 fprintf (sched_dump,
4324 ";; ======================================================\n");
4325 fprintf (sched_dump, "\n");
4328 /* Unlink basic block notes and labels and saves them, so they
4329 can be easily restored. We unlink basic block notes in EBB to
4330 provide back-compatibility with the previous code, as target backends
4331 assume, that there'll be only instructions between
4332 current_sched_info->{head and tail}. We restore these notes as soon
4334 FIRST (LAST) is the first (last) basic block in the ebb.
4335 NB: In usual case (FIRST == LAST) nothing is really done. */
4337 unlink_bb_notes (basic_block first, basic_block last)
4339 /* We DON'T unlink basic block notes of the first block in the ebb. */
4343 bb_header = XNEWVEC (rtx, last_basic_block);
4345 /* Make a sentinel. */
4346 if (last->next_bb != EXIT_BLOCK_PTR)
4347 bb_header[last->next_bb->index] = 0;
4349 first = first->next_bb;
4352 rtx prev, label, note, next;
4354 label = BB_HEAD (last);
4355 if (LABEL_P (label))
4356 note = NEXT_INSN (label);
4359 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
4361 prev = PREV_INSN (label);
4362 next = NEXT_INSN (note);
4363 gcc_assert (prev && next);
4365 NEXT_INSN (prev) = next;
4366 PREV_INSN (next) = prev;
4368 bb_header[last->index] = label;
4373 last = last->prev_bb;
4378 /* Restore basic block notes.
4379 FIRST is the first basic block in the ebb. */
4381 restore_bb_notes (basic_block first)
4386 /* We DON'T unlink basic block notes of the first block in the ebb. */
4387 first = first->next_bb;
4388 /* Remember: FIRST is actually a second basic block in the ebb. */
4390 while (first != EXIT_BLOCK_PTR
4391 && bb_header[first->index])
4393 rtx prev, label, note, next;
4395 label = bb_header[first->index];
4396 prev = PREV_INSN (label);
4397 next = NEXT_INSN (prev);
4399 if (LABEL_P (label))
4400 note = NEXT_INSN (label);
4403 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
4405 bb_header[first->index] = 0;
4407 NEXT_INSN (prev) = label;
4408 NEXT_INSN (note) = next;
4409 PREV_INSN (next) = note;
4411 first = first->next_bb;
4419 Fix CFG after both in- and inter-block movement of
4420 control_flow_insn_p JUMP. */
4422 fix_jump_move (rtx jump)
4424 basic_block bb, jump_bb, jump_bb_next;
4426 bb = BLOCK_FOR_INSN (PREV_INSN (jump));
4427 jump_bb = BLOCK_FOR_INSN (jump);
4428 jump_bb_next = jump_bb->next_bb;
4430 gcc_assert (common_sched_info->sched_pass_id == SCHED_EBB_PASS
4431 || IS_SPECULATION_BRANCHY_CHECK_P (jump));
4433 if (!NOTE_INSN_BASIC_BLOCK_P (BB_END (jump_bb_next)))
4434 /* if jump_bb_next is not empty. */
4435 BB_END (jump_bb) = BB_END (jump_bb_next);
4437 if (BB_END (bb) != PREV_INSN (jump))
4438 /* Then there are instruction after jump that should be placed
4440 BB_END (jump_bb_next) = BB_END (bb);
4442 /* Otherwise jump_bb_next is empty. */
4443 BB_END (jump_bb_next) = NEXT_INSN (BB_HEAD (jump_bb_next));
4445 /* To make assertion in move_insn happy. */
4446 BB_END (bb) = PREV_INSN (jump);
4448 update_bb_for_insn (jump_bb_next);
4451 /* Fix CFG after interblock movement of control_flow_insn_p JUMP. */
4453 move_block_after_check (rtx jump)
4455 basic_block bb, jump_bb, jump_bb_next;
4458 bb = BLOCK_FOR_INSN (PREV_INSN (jump));
4459 jump_bb = BLOCK_FOR_INSN (jump);
4460 jump_bb_next = jump_bb->next_bb;
4462 update_bb_for_insn (jump_bb);
4464 gcc_assert (IS_SPECULATION_CHECK_P (jump)
4465 || IS_SPECULATION_CHECK_P (BB_END (jump_bb_next)));
4467 unlink_block (jump_bb_next);
4468 link_block (jump_bb_next, bb);
4472 move_succs (&(jump_bb->succs), bb);
4473 move_succs (&(jump_bb_next->succs), jump_bb);
4474 move_succs (&t, jump_bb_next);
4476 df_mark_solutions_dirty ();
4478 common_sched_info->fix_recovery_cfg
4479 (bb->index, jump_bb->index, jump_bb_next->index);
4482 /* Helper function for move_block_after_check.
4483 This functions attaches edge vector pointed to by SUCCSP to
4486 move_succs (VEC(edge,gc) **succsp, basic_block to)
4491 gcc_assert (to->succs == 0);
4493 to->succs = *succsp;
4495 FOR_EACH_EDGE (e, ei, to->succs)
4501 /* Remove INSN from the instruction stream.
4502 INSN should have any dependencies. */
4504 sched_remove_insn (rtx insn)
4506 sd_finish_insn (insn);
4508 change_queue_index (insn, QUEUE_NOWHERE);
4509 current_sched_info->add_remove_insn (insn, 1);
4513 /* Clear priorities of all instructions, that are forward dependent on INSN.
4514 Store in vector pointed to by ROOTS_PTR insns on which priority () should
4515 be invoked to initialize all cleared priorities. */
4517 clear_priorities (rtx insn, rtx_vec_t *roots_ptr)
4519 sd_iterator_def sd_it;
4521 bool insn_is_root_p = true;
4523 gcc_assert (QUEUE_INDEX (insn) != QUEUE_SCHEDULED);
4525 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
4527 rtx pro = DEP_PRO (dep);
4529 if (INSN_PRIORITY_STATUS (pro) >= 0
4530 && QUEUE_INDEX (insn) != QUEUE_SCHEDULED)
4532 /* If DEP doesn't contribute to priority then INSN itself should
4533 be added to priority roots. */
4534 if (contributes_to_priority_p (dep))
4535 insn_is_root_p = false;
4537 INSN_PRIORITY_STATUS (pro) = -1;
4538 clear_priorities (pro, roots_ptr);
4543 VEC_safe_push (rtx, heap, *roots_ptr, insn);
4546 /* Recompute priorities of instructions, whose priorities might have been
4547 changed. ROOTS is a vector of instructions whose priority computation will
4548 trigger initialization of all cleared priorities. */
4550 calc_priorities (rtx_vec_t roots)
4555 for (i = 0; VEC_iterate (rtx, roots, i, insn); i++)
4560 /* Add dependences between JUMP and other instructions in the recovery
4561 block. INSN is the first insn the recovery block. */
4563 add_jump_dependencies (rtx insn, rtx jump)
4567 insn = NEXT_INSN (insn);
4571 if (sd_lists_empty_p (insn, SD_LIST_FORW))
4573 dep_def _new_dep, *new_dep = &_new_dep;
4575 init_dep (new_dep, insn, jump, REG_DEP_ANTI);
4576 sd_add_dep (new_dep, false);
4581 gcc_assert (!sd_lists_empty_p (jump, SD_LIST_BACK));
4584 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
4586 bb_note (basic_block bb)
4590 note = BB_HEAD (bb);
4592 note = NEXT_INSN (note);
4594 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
4598 #ifdef ENABLE_CHECKING
4599 /* Helper function for check_cfg.
4600 Return nonzero, if edge vector pointed to by EL has edge with TYPE in
4603 has_edge_p (VEC(edge,gc) *el, int type)
4608 FOR_EACH_EDGE (e, ei, el)
4609 if (e->flags & type)
4614 /* Check few properties of CFG between HEAD and TAIL.
4615 If HEAD (TAIL) is NULL check from the beginning (till the end) of the
4616 instruction stream. */
4618 check_cfg (rtx head, rtx tail)
4622 int not_first = 0, not_last;
4625 head = get_insns ();
4627 tail = get_last_insn ();
4628 next_tail = NEXT_INSN (tail);
4632 not_last = head != tail;
4635 gcc_assert (NEXT_INSN (PREV_INSN (head)) == head);
4637 gcc_assert (PREV_INSN (NEXT_INSN (head)) == head);
4640 || (NOTE_INSN_BASIC_BLOCK_P (head)
4642 || (not_first && !LABEL_P (PREV_INSN (head))))))
4644 gcc_assert (bb == 0);
4645 bb = BLOCK_FOR_INSN (head);
4647 gcc_assert (BB_HEAD (bb) == head);
4649 /* This is the case of jump table. See inside_basic_block_p (). */
4650 gcc_assert (LABEL_P (head) && !inside_basic_block_p (head));
4655 gcc_assert (!inside_basic_block_p (head));
4656 head = NEXT_INSN (head);
4660 gcc_assert (inside_basic_block_p (head)
4662 gcc_assert (BLOCK_FOR_INSN (head) == bb);
4666 head = NEXT_INSN (head);
4667 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (head));
4671 if (control_flow_insn_p (head))
4673 gcc_assert (BB_END (bb) == head);
4675 if (any_uncondjump_p (head))
4676 gcc_assert (EDGE_COUNT (bb->succs) == 1
4677 && BARRIER_P (NEXT_INSN (head)));
4678 else if (any_condjump_p (head))
4679 gcc_assert (/* Usual case. */
4680 (EDGE_COUNT (bb->succs) > 1
4681 && !BARRIER_P (NEXT_INSN (head)))
4682 /* Or jump to the next instruction. */
4683 || (EDGE_COUNT (bb->succs) == 1
4684 && (BB_HEAD (EDGE_I (bb->succs, 0)->dest)
4685 == JUMP_LABEL (head))));
4687 if (BB_END (bb) == head)
4689 if (EDGE_COUNT (bb->succs) > 1)
4690 gcc_assert (control_flow_insn_p (head)
4691 || has_edge_p (bb->succs, EDGE_COMPLEX));
4695 head = NEXT_INSN (head);
4701 while (head != next_tail);
4703 gcc_assert (bb == 0);
4706 #endif /* ENABLE_CHECKING */
4708 const struct sched_scan_info_def *sched_scan_info;
4710 /* Extend per basic block data structures. */
4714 if (sched_scan_info->extend_bb)
4715 sched_scan_info->extend_bb ();
4718 /* Init data for BB. */
4720 init_bb (basic_block bb)
4722 if (sched_scan_info->init_bb)
4723 sched_scan_info->init_bb (bb);
4726 /* Extend per insn data structures. */
4730 if (sched_scan_info->extend_insn)
4731 sched_scan_info->extend_insn ();
4734 /* Init data structures for INSN. */
4736 init_insn (rtx insn)
4738 if (sched_scan_info->init_insn)
4739 sched_scan_info->init_insn (insn);
4742 /* Init all insns in BB. */
4744 init_insns_in_bb (basic_block bb)
4748 FOR_BB_INSNS (bb, insn)
4752 /* A driver function to add a set of basic blocks (BBS),
4753 a single basic block (BB), a set of insns (INSNS) or a single insn (INSN)
4754 to the scheduling region. */
4756 sched_scan (const struct sched_scan_info_def *ssi,
4757 bb_vec_t bbs, basic_block bb, insn_vec_t insns, rtx insn)
4759 sched_scan_info = ssi;
4761 if (bbs != NULL || bb != NULL)
4770 for (i = 0; VEC_iterate (basic_block, bbs, i, x); i++)
4785 for (i = 0; VEC_iterate (basic_block, bbs, i, x); i++)
4786 init_insns_in_bb (x);
4790 init_insns_in_bb (bb);
4797 for (i = 0; VEC_iterate (rtx, insns, i, x); i++)
4806 /* Extend data structures for logical insn UID. */
4808 luids_extend_insn (void)
4810 int new_luids_max_uid = get_max_uid () + 1;
4812 VEC_safe_grow_cleared (int, heap, sched_luids, new_luids_max_uid);
4815 /* Initialize LUID for INSN. */
4817 luids_init_insn (rtx insn)
4819 int i = INSN_P (insn) ? 1 : common_sched_info->luid_for_non_insn (insn);
4824 luid = sched_max_luid;
4825 sched_max_luid += i;
4830 SET_INSN_LUID (insn, luid);
4833 /* Initialize luids for BBS, BB, INSNS and INSN.
4834 The hook common_sched_info->luid_for_non_insn () is used to determine
4835 if notes, labels, etc. need luids. */
4837 sched_init_luids (bb_vec_t bbs, basic_block bb, insn_vec_t insns, rtx insn)
4839 const struct sched_scan_info_def ssi =
4841 NULL, /* extend_bb */
4843 luids_extend_insn, /* extend_insn */
4844 luids_init_insn /* init_insn */
4847 sched_scan (&ssi, bbs, bb, insns, insn);
4852 sched_finish_luids (void)
4854 VEC_free (int, heap, sched_luids);
4858 /* Return logical uid of INSN. Helpful while debugging. */
4860 insn_luid (rtx insn)
4862 return INSN_LUID (insn);
4865 /* Extend per insn data in the target. */
4867 sched_extend_target (void)
4869 if (targetm.sched.h_i_d_extended)
4870 targetm.sched.h_i_d_extended ();
4873 /* Extend global scheduler structures (those, that live across calls to
4874 schedule_block) to include information about just emitted INSN. */
4878 int reserve = (get_max_uid () + 1
4879 - VEC_length (haifa_insn_data_def, h_i_d));
4881 && ! VEC_space (haifa_insn_data_def, h_i_d, reserve))
4883 VEC_safe_grow_cleared (haifa_insn_data_def, heap, h_i_d,
4884 3 * get_max_uid () / 2);
4885 sched_extend_target ();
4889 /* Initialize h_i_d entry of the INSN with default values.
4890 Values, that are not explicitly initialized here, hold zero. */
4892 init_h_i_d (rtx insn)
4894 if (INSN_LUID (insn) > 0)
4896 INSN_COST (insn) = -1;
4897 find_insn_reg_weight (insn);
4898 QUEUE_INDEX (insn) = QUEUE_NOWHERE;
4899 INSN_TICK (insn) = INVALID_TICK;
4900 INTER_TICK (insn) = INVALID_TICK;
4901 TODO_SPEC (insn) = HARD_DEP;
4905 /* Initialize haifa_insn_data for BBS, BB, INSNS and INSN. */
4907 haifa_init_h_i_d (bb_vec_t bbs, basic_block bb, insn_vec_t insns, rtx insn)
4909 const struct sched_scan_info_def ssi =
4911 NULL, /* extend_bb */
4913 extend_h_i_d, /* extend_insn */
4914 init_h_i_d /* init_insn */
4917 sched_scan (&ssi, bbs, bb, insns, insn);
4920 /* Finalize haifa_insn_data. */
4922 haifa_finish_h_i_d (void)
4924 VEC_free (haifa_insn_data_def, heap, h_i_d);
4927 /* Init data for the new insn INSN. */
4929 haifa_init_insn (rtx insn)
4931 gcc_assert (insn != NULL);
4933 sched_init_luids (NULL, NULL, NULL, insn);
4934 sched_extend_target ();
4935 sched_deps_init (false);
4936 haifa_init_h_i_d (NULL, NULL, NULL, insn);
4938 if (adding_bb_to_current_region_p)
4940 sd_init_insn (insn);
4942 /* Extend dependency caches by one element. */
4943 extend_dependency_caches (1, false);
4947 /* Init data for the new basic block BB which comes after AFTER. */
4949 haifa_init_only_bb (basic_block bb, basic_block after)
4951 gcc_assert (bb != NULL);
4955 if (common_sched_info->add_block)
4956 /* This changes only data structures of the front-end. */
4957 common_sched_info->add_block (bb, after);
4960 /* A generic version of sched_split_block (). */
4962 sched_split_block_1 (basic_block first_bb, rtx after)
4966 e = split_block (first_bb, after);
4967 gcc_assert (e->src == first_bb);
4969 /* sched_split_block emits note if *check == BB_END. Probably it
4970 is better to rip that note off. */
4975 /* A generic version of sched_create_empty_bb (). */
4977 sched_create_empty_bb_1 (basic_block after)
4979 return create_empty_bb (after);
4982 #endif /* INSN_SCHEDULING */