1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
3 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
4 Free Software Foundation, Inc.
5 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
6 and currently maintained by, Jim Wilson (wilson@cygnus.com)
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
24 /* Instruction scheduling pass. This file, along with sched-deps.c,
25 contains the generic parts. The actual entry point is found for
26 the normal instruction scheduling pass is found in sched-rgn.c.
28 We compute insn priorities based on data dependencies. Flow
29 analysis only creates a fraction of the data-dependencies we must
30 observe: namely, only those dependencies which the combiner can be
31 expected to use. For this pass, we must therefore create the
32 remaining dependencies we need to observe: register dependencies,
33 memory dependencies, dependencies to keep function calls in order,
34 and the dependence between a conditional branch and the setting of
35 condition codes are all dealt with here.
37 The scheduler first traverses the data flow graph, starting with
38 the last instruction, and proceeding to the first, assigning values
39 to insn_priority as it goes. This sorts the instructions
40 topologically by data dependence.
42 Once priorities have been established, we order the insns using
43 list scheduling. This works as follows: starting with a list of
44 all the ready insns, and sorted according to priority number, we
45 schedule the insn from the end of the list by placing its
46 predecessors in the list according to their priority order. We
47 consider this insn scheduled by setting the pointer to the "end" of
48 the list to point to the previous insn. When an insn has no
49 predecessors, we either queue it until sufficient time has elapsed
50 or add it to the ready list. As the instructions are scheduled or
51 when stalls are introduced, the queue advances and dumps insns into
52 the ready list. When all insns down to the lowest priority have
53 been scheduled, the critical path of the basic block has been made
54 as short as possible. The remaining insns are then scheduled in
57 The following list shows the order in which we want to break ties
58 among insns in the ready list:
60 1. choose insn with the longest path to end of bb, ties
62 2. choose insn with least contribution to register pressure,
64 3. prefer in-block upon interblock motion, ties broken by
65 4. prefer useful upon speculative motion, ties broken by
66 5. choose insn with largest control flow probability, ties
68 6. choose insn with the least dependences upon the previously
69 scheduled insn, or finally
70 7 choose the insn which has the most insns dependent on it.
71 8. choose insn with lowest UID.
73 Memory references complicate matters. Only if we can be certain
74 that memory references are not part of the data dependency graph
75 (via true, anti, or output dependence), can we move operations past
76 memory references. To first approximation, reads can be done
77 independently, while writes introduce dependencies. Better
78 approximations will yield fewer dependencies.
80 Before reload, an extended analysis of interblock data dependences
81 is required for interblock scheduling. This is performed in
82 compute_block_backward_dependences ().
84 Dependencies set up by memory references are treated in exactly the
85 same way as other dependencies, by using insn backward dependences
86 INSN_BACK_DEPS. INSN_BACK_DEPS are translated into forward dependences
87 INSN_FORW_DEPS the purpose of forward list scheduling.
89 Having optimized the critical path, we may have also unduly
90 extended the lifetimes of some registers. If an operation requires
91 that constants be loaded into registers, it is certainly desirable
92 to load those constants as early as necessary, but no earlier.
93 I.e., it will not do to load up a bunch of registers at the
94 beginning of a basic block only to use them at the end, if they
95 could be loaded later, since this may result in excessive register
98 Note that since branches are never in basic blocks, but only end
99 basic blocks, this pass will not move branches. But that is ok,
100 since we can use GNU's delayed branch scheduling pass to take care
103 Also note that no further optimizations based on algebraic
104 identities are performed, so this pass would be a good one to
105 perform instruction splitting, such as breaking up a multiply
106 instruction into shifts and adds where that is profitable.
108 Given the memory aliasing analysis that this pass should perform,
109 it should be possible to remove redundant stores to memory, and to
110 load values from registers instead of hitting memory.
112 Before reload, speculative insns are moved only if a 'proof' exists
113 that no exception will be caused by this, and if no live registers
114 exist that inhibit the motion (live registers constraints are not
115 represented by data dependence edges).
117 This pass must update information that subsequent passes expect to
118 be correct. Namely: reg_n_refs, reg_n_sets, reg_n_deaths,
119 reg_n_calls_crossed, and reg_live_length. Also, BB_HEAD, BB_END.
121 The information in the line number notes is carefully retained by
122 this pass. Notes that refer to the starting and ending of
123 exception regions are also carefully retained by this pass. All
124 other NOTE insns are grouped in their same relative order at the
125 beginning of basic blocks and regions that have been scheduled. */
129 #include "coretypes.h"
131 #include "diagnostic-core.h"
135 #include "hard-reg-set.h"
137 #include "function.h"
139 #include "insn-config.h"
140 #include "insn-attr.h"
143 #include "sched-int.h"
151 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
153 #ifdef INSN_SCHEDULING
155 /* issue_rate is the number of insns that can be scheduled in the same
156 machine cycle. It can be defined in the config/mach/mach.h file,
157 otherwise we set it to 1. */
161 /* sched-verbose controls the amount of debugging output the
162 scheduler prints. It is controlled by -fsched-verbose=N:
163 N>0 and no -DSR : the output is directed to stderr.
164 N>=10 will direct the printouts to stderr (regardless of -dSR).
166 N=2: bb's probabilities, detailed ready list info, unit/insn info.
167 N=3: rtl at abort point, control-flow, regions info.
168 N=5: dependences info. */
170 static int sched_verbose_param
= 0;
171 int sched_verbose
= 0;
173 /* Debugging file. All printouts are sent to dump, which is always set,
174 either to stderr, or to the dump listing file (-dRS). */
175 FILE *sched_dump
= 0;
177 /* fix_sched_param() is called from toplev.c upon detection
178 of the -fsched-verbose=N option. */
181 fix_sched_param (const char *param
, const char *val
)
183 if (!strcmp (param
, "verbose"))
184 sched_verbose_param
= atoi (val
);
186 warning (0, "fix_sched_param: unknown param: %s", param
);
189 /* This is a placeholder for the scheduler parameters common
190 to all schedulers. */
191 struct common_sched_info_def
*common_sched_info
;
193 #define INSN_TICK(INSN) (HID (INSN)->tick)
194 #define INTER_TICK(INSN) (HID (INSN)->inter_tick)
196 /* If INSN_TICK of an instruction is equal to INVALID_TICK,
197 then it should be recalculated from scratch. */
198 #define INVALID_TICK (-(max_insn_queue_index + 1))
199 /* The minimal value of the INSN_TICK of an instruction. */
200 #define MIN_TICK (-max_insn_queue_index)
202 /* Issue points are used to distinguish between instructions in max_issue ().
203 For now, all instructions are equally good. */
204 #define ISSUE_POINTS(INSN) 1
206 /* List of important notes we must keep around. This is a pointer to the
207 last element in the list. */
210 static struct spec_info_def spec_info_var
;
211 /* Description of the speculative part of the scheduling.
212 If NULL - no speculation. */
213 spec_info_t spec_info
= NULL
;
215 /* True, if recovery block was added during scheduling of current block.
216 Used to determine, if we need to fix INSN_TICKs. */
217 static bool haifa_recovery_bb_recently_added_p
;
219 /* True, if recovery block was added during this scheduling pass.
220 Used to determine if we should have empty memory pools of dependencies
221 after finishing current region. */
222 bool haifa_recovery_bb_ever_added_p
;
224 /* Counters of different types of speculative instructions. */
225 static int nr_begin_data
, nr_be_in_data
, nr_begin_control
, nr_be_in_control
;
227 /* Array used in {unlink, restore}_bb_notes. */
228 static rtx
*bb_header
= 0;
230 /* Basic block after which recovery blocks will be created. */
231 static basic_block before_recovery
;
233 /* Basic block just before the EXIT_BLOCK and after recovery, if we have
235 basic_block after_recovery
;
237 /* FALSE if we add bb to another region, so we don't need to initialize it. */
238 bool adding_bb_to_current_region_p
= true;
242 /* An instruction is ready to be scheduled when all insns preceding it
243 have already been scheduled. It is important to ensure that all
244 insns which use its result will not be executed until its result
245 has been computed. An insn is maintained in one of four structures:
247 (P) the "Pending" set of insns which cannot be scheduled until
248 their dependencies have been satisfied.
249 (Q) the "Queued" set of insns that can be scheduled when sufficient
251 (R) the "Ready" list of unscheduled, uncommitted insns.
252 (S) the "Scheduled" list of insns.
254 Initially, all insns are either "Pending" or "Ready" depending on
255 whether their dependencies are satisfied.
257 Insns move from the "Ready" list to the "Scheduled" list as they
258 are committed to the schedule. As this occurs, the insns in the
259 "Pending" list have their dependencies satisfied and move to either
260 the "Ready" list or the "Queued" set depending on whether
261 sufficient time has passed to make them ready. As time passes,
262 insns move from the "Queued" set to the "Ready" list.
264 The "Pending" list (P) are the insns in the INSN_FORW_DEPS of the
265 unscheduled insns, i.e., those that are ready, queued, and pending.
266 The "Queued" set (Q) is implemented by the variable `insn_queue'.
267 The "Ready" list (R) is implemented by the variables `ready' and
269 The "Scheduled" list (S) is the new insn chain built by this pass.
271 The transition (R->S) is implemented in the scheduling loop in
272 `schedule_block' when the best insn to schedule is chosen.
273 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
274 insns move from the ready list to the scheduled list.
275 The transition (Q->R) is implemented in 'queue_to_insn' as time
276 passes or stalls are introduced. */
278 /* Implement a circular buffer to delay instructions until sufficient
279 time has passed. For the new pipeline description interface,
280 MAX_INSN_QUEUE_INDEX is a power of two minus one which is not less
281 than maximal time of instruction execution computed by genattr.c on
282 the base maximal time of functional unit reservations and getting a
283 result. This is the longest time an insn may be queued. */
285 static rtx
*insn_queue
;
286 static int q_ptr
= 0;
287 static int q_size
= 0;
288 #define NEXT_Q(X) (((X)+1) & max_insn_queue_index)
289 #define NEXT_Q_AFTER(X, C) (((X)+C) & max_insn_queue_index)
291 #define QUEUE_SCHEDULED (-3)
292 #define QUEUE_NOWHERE (-2)
293 #define QUEUE_READY (-1)
294 /* QUEUE_SCHEDULED - INSN is scheduled.
295 QUEUE_NOWHERE - INSN isn't scheduled yet and is neither in
297 QUEUE_READY - INSN is in ready list.
298 N >= 0 - INSN queued for X [where NEXT_Q_AFTER (q_ptr, X) == N] cycles. */
300 #define QUEUE_INDEX(INSN) (HID (INSN)->queue_index)
302 /* The following variable value refers for all current and future
303 reservations of the processor units. */
306 /* The following variable value is size of memory representing all
307 current and future reservations of the processor units. */
308 size_t dfa_state_size
;
310 /* The following array is used to find the best insn from ready when
311 the automaton pipeline interface is used. */
312 char *ready_try
= NULL
;
314 /* The ready list. */
315 struct ready_list ready
= {NULL
, 0, 0, 0, 0};
317 /* The pointer to the ready list (to be removed). */
318 static struct ready_list
*readyp
= &ready
;
320 /* Scheduling clock. */
321 static int clock_var
;
323 static int may_trap_exp (const_rtx
, int);
325 /* Nonzero iff the address is comprised from at most 1 register. */
326 #define CONST_BASED_ADDRESS_P(x) \
328 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
329 || (GET_CODE (x) == LO_SUM)) \
330 && (CONSTANT_P (XEXP (x, 0)) \
331 || CONSTANT_P (XEXP (x, 1)))))
333 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
334 as found by analyzing insn's expression. */
337 static int haifa_luid_for_non_insn (rtx x
);
339 /* Haifa version of sched_info hooks common to all headers. */
340 const struct common_sched_info_def haifa_common_sched_info
=
342 NULL
, /* fix_recovery_cfg */
343 NULL
, /* add_block */
344 NULL
, /* estimate_number_of_insns */
345 haifa_luid_for_non_insn
, /* luid_for_non_insn */
346 SCHED_PASS_UNKNOWN
/* sched_pass_id */
349 const struct sched_scan_info_def
*sched_scan_info
;
351 /* Mapping from instruction UID to its Logical UID. */
352 VEC (int, heap
) *sched_luids
= NULL
;
354 /* Next LUID to assign to an instruction. */
355 int sched_max_luid
= 1;
357 /* Haifa Instruction Data. */
358 VEC (haifa_insn_data_def
, heap
) *h_i_d
= NULL
;
360 void (* sched_init_only_bb
) (basic_block
, basic_block
);
362 /* Split block function. Different schedulers might use different functions
363 to handle their internal data consistent. */
364 basic_block (* sched_split_block
) (basic_block
, rtx
);
366 /* Create empty basic block after the specified block. */
367 basic_block (* sched_create_empty_bb
) (basic_block
);
370 may_trap_exp (const_rtx x
, int is_store
)
379 if (code
== MEM
&& may_trap_p (x
))
386 /* The insn uses memory: a volatile load. */
387 if (MEM_VOLATILE_P (x
))
389 /* An exception-free load. */
392 /* A load with 1 base register, to be further checked. */
393 if (CONST_BASED_ADDRESS_P (XEXP (x
, 0)))
394 return PFREE_CANDIDATE
;
395 /* No info on the load, to be further checked. */
396 return PRISKY_CANDIDATE
;
401 int i
, insn_class
= TRAP_FREE
;
403 /* Neither store nor load, check if it may cause a trap. */
406 /* Recursive step: walk the insn... */
407 fmt
= GET_RTX_FORMAT (code
);
408 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
412 int tmp_class
= may_trap_exp (XEXP (x
, i
), is_store
);
413 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
415 else if (fmt
[i
] == 'E')
418 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
420 int tmp_class
= may_trap_exp (XVECEXP (x
, i
, j
), is_store
);
421 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
422 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
426 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
433 /* Classifies rtx X of an insn for the purpose of verifying that X can be
434 executed speculatively (and consequently the insn can be moved
435 speculatively), by examining X, returning:
436 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
437 TRAP_FREE: non-load insn.
438 IFREE: load from a globally safe location.
439 IRISKY: volatile load.
440 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
441 being either PFREE or PRISKY. */
444 haifa_classify_rtx (const_rtx x
)
446 int tmp_class
= TRAP_FREE
;
447 int insn_class
= TRAP_FREE
;
450 if (GET_CODE (x
) == PARALLEL
)
452 int i
, len
= XVECLEN (x
, 0);
454 for (i
= len
- 1; i
>= 0; i
--)
456 tmp_class
= haifa_classify_rtx (XVECEXP (x
, 0, i
));
457 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
458 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
468 /* Test if it is a 'store'. */
469 tmp_class
= may_trap_exp (XEXP (x
, 0), 1);
472 /* Test if it is a store. */
473 tmp_class
= may_trap_exp (SET_DEST (x
), 1);
474 if (tmp_class
== TRAP_RISKY
)
476 /* Test if it is a load. */
478 WORST_CLASS (tmp_class
,
479 may_trap_exp (SET_SRC (x
), 0));
482 tmp_class
= haifa_classify_rtx (COND_EXEC_CODE (x
));
483 if (tmp_class
== TRAP_RISKY
)
485 tmp_class
= WORST_CLASS (tmp_class
,
486 may_trap_exp (COND_EXEC_TEST (x
), 0));
489 tmp_class
= TRAP_RISKY
;
493 insn_class
= tmp_class
;
500 haifa_classify_insn (const_rtx insn
)
502 return haifa_classify_rtx (PATTERN (insn
));
505 /* Forward declarations. */
507 static int priority (rtx
);
508 static int rank_for_schedule (const void *, const void *);
509 static void swap_sort (rtx
*, int);
510 static void queue_insn (rtx
, int);
511 static int schedule_insn (rtx
);
512 static void adjust_priority (rtx
);
513 static void advance_one_cycle (void);
514 static void extend_h_i_d (void);
517 /* Notes handling mechanism:
518 =========================
519 Generally, NOTES are saved before scheduling and restored after scheduling.
520 The scheduler distinguishes between two types of notes:
522 (1) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
523 Before scheduling a region, a pointer to the note is added to the insn
524 that follows or precedes it. (This happens as part of the data dependence
525 computation). After scheduling an insn, the pointer contained in it is
526 used for regenerating the corresponding note (in reemit_notes).
528 (2) All other notes (e.g. INSN_DELETED): Before scheduling a block,
529 these notes are put in a list (in rm_other_notes() and
530 unlink_other_notes ()). After scheduling the block, these notes are
531 inserted at the beginning of the block (in schedule_block()). */
533 static void ready_add (struct ready_list
*, rtx
, bool);
534 static rtx
ready_remove_first (struct ready_list
*);
535 static rtx
ready_remove_first_dispatch (struct ready_list
*ready
);
537 static void queue_to_ready (struct ready_list
*);
538 static int early_queue_to_ready (state_t
, struct ready_list
*);
540 static void debug_ready_list (struct ready_list
*);
542 /* The following functions are used to implement multi-pass scheduling
543 on the first cycle. */
544 static rtx
ready_remove (struct ready_list
*, int);
545 static void ready_remove_insn (rtx
);
547 static int choose_ready (struct ready_list
*, rtx
*);
549 static void fix_inter_tick (rtx
, rtx
);
550 static int fix_tick_ready (rtx
);
551 static void change_queue_index (rtx
, int);
553 /* The following functions are used to implement scheduling of data/control
554 speculative instructions. */
556 static void extend_h_i_d (void);
557 static void init_h_i_d (rtx
);
558 static void generate_recovery_code (rtx
);
559 static void process_insn_forw_deps_be_in_spec (rtx
, rtx
, ds_t
);
560 static void begin_speculative_block (rtx
);
561 static void add_to_speculative_block (rtx
);
562 static void init_before_recovery (basic_block
*);
563 static void create_check_block_twin (rtx
, bool);
564 static void fix_recovery_deps (basic_block
);
565 static void haifa_change_pattern (rtx
, rtx
);
566 static void dump_new_block_header (int, basic_block
, rtx
, rtx
);
567 static void restore_bb_notes (basic_block
);
568 static void fix_jump_move (rtx
);
569 static void move_block_after_check (rtx
);
570 static void move_succs (VEC(edge
,gc
) **, basic_block
);
571 static void sched_remove_insn (rtx
);
572 static void clear_priorities (rtx
, rtx_vec_t
*);
573 static void calc_priorities (rtx_vec_t
);
574 static void add_jump_dependencies (rtx
, rtx
);
575 #ifdef ENABLE_CHECKING
576 static int has_edge_p (VEC(edge
,gc
) *, int);
577 static void check_cfg (rtx
, rtx
);
580 #endif /* INSN_SCHEDULING */
582 /* Point to state used for the current scheduling pass. */
583 struct haifa_sched_info
*current_sched_info
;
585 #ifndef INSN_SCHEDULING
587 schedule_insns (void)
592 /* Do register pressure sensitive insn scheduling if the flag is set
594 bool sched_pressure_p
;
596 /* Map regno -> its cover class. The map defined only when
597 SCHED_PRESSURE_P is true. */
598 enum reg_class
*sched_regno_cover_class
;
600 /* The current register pressure. Only elements corresponding cover
601 classes are defined. */
602 static int curr_reg_pressure
[N_REG_CLASSES
];
604 /* Saved value of the previous array. */
605 static int saved_reg_pressure
[N_REG_CLASSES
];
607 /* Register living at given scheduling point. */
608 static bitmap curr_reg_live
;
610 /* Saved value of the previous array. */
611 static bitmap saved_reg_live
;
613 /* Registers mentioned in the current region. */
614 static bitmap region_ref_regs
;
616 /* Initiate register pressure relative info for scheduling the current
617 region. Currently it is only clearing register mentioned in the
620 sched_init_region_reg_pressure_info (void)
622 bitmap_clear (region_ref_regs
);
625 /* Update current register pressure related info after birth (if
626 BIRTH_P) or death of register REGNO. */
628 mark_regno_birth_or_death (int regno
, bool birth_p
)
630 enum reg_class cover_class
;
632 cover_class
= sched_regno_cover_class
[regno
];
633 if (regno
>= FIRST_PSEUDO_REGISTER
)
635 if (cover_class
!= NO_REGS
)
639 bitmap_set_bit (curr_reg_live
, regno
);
640 curr_reg_pressure
[cover_class
]
641 += ira_reg_class_nregs
[cover_class
][PSEUDO_REGNO_MODE (regno
)];
645 bitmap_clear_bit (curr_reg_live
, regno
);
646 curr_reg_pressure
[cover_class
]
647 -= ira_reg_class_nregs
[cover_class
][PSEUDO_REGNO_MODE (regno
)];
651 else if (cover_class
!= NO_REGS
652 && ! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
656 bitmap_set_bit (curr_reg_live
, regno
);
657 curr_reg_pressure
[cover_class
]++;
661 bitmap_clear_bit (curr_reg_live
, regno
);
662 curr_reg_pressure
[cover_class
]--;
667 /* Initiate current register pressure related info from living
668 registers given by LIVE. */
670 initiate_reg_pressure_info (bitmap live
)
676 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
677 curr_reg_pressure
[ira_reg_class_cover
[i
]] = 0;
678 bitmap_clear (curr_reg_live
);
679 EXECUTE_IF_SET_IN_BITMAP (live
, 0, j
, bi
)
680 if (current_nr_blocks
== 1 || bitmap_bit_p (region_ref_regs
, j
))
681 mark_regno_birth_or_death (j
, true);
684 /* Mark registers in X as mentioned in the current region. */
686 setup_ref_regs (rtx x
)
689 const RTX_CODE code
= GET_CODE (x
);
695 if (regno
>= FIRST_PSEUDO_REGISTER
)
696 bitmap_set_bit (region_ref_regs
, REGNO (x
));
698 for (i
= hard_regno_nregs
[regno
][GET_MODE (x
)] - 1; i
>= 0; i
--)
699 bitmap_set_bit (region_ref_regs
, regno
+ i
);
702 fmt
= GET_RTX_FORMAT (code
);
703 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
705 setup_ref_regs (XEXP (x
, i
));
706 else if (fmt
[i
] == 'E')
708 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
709 setup_ref_regs (XVECEXP (x
, i
, j
));
713 /* Initiate current register pressure related info at the start of
716 initiate_bb_reg_pressure_info (basic_block bb
)
721 if (current_nr_blocks
> 1)
722 FOR_BB_INSNS (bb
, insn
)
723 if (NONDEBUG_INSN_P (insn
))
724 setup_ref_regs (PATTERN (insn
));
725 initiate_reg_pressure_info (df_get_live_in (bb
));
726 #ifdef EH_RETURN_DATA_REGNO
727 if (bb_has_eh_pred (bb
))
730 unsigned int regno
= EH_RETURN_DATA_REGNO (i
);
732 if (regno
== INVALID_REGNUM
)
734 if (! bitmap_bit_p (df_get_live_in (bb
), regno
))
735 mark_regno_birth_or_death (regno
, true);
740 /* Save current register pressure related info. */
742 save_reg_pressure (void)
746 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
747 saved_reg_pressure
[ira_reg_class_cover
[i
]]
748 = curr_reg_pressure
[ira_reg_class_cover
[i
]];
749 bitmap_copy (saved_reg_live
, curr_reg_live
);
752 /* Restore saved register pressure related info. */
754 restore_reg_pressure (void)
758 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
759 curr_reg_pressure
[ira_reg_class_cover
[i
]]
760 = saved_reg_pressure
[ira_reg_class_cover
[i
]];
761 bitmap_copy (curr_reg_live
, saved_reg_live
);
764 /* Return TRUE if the register is dying after its USE. */
766 dying_use_p (struct reg_use_data
*use
)
768 struct reg_use_data
*next
;
770 for (next
= use
->next_regno_use
; next
!= use
; next
= next
->next_regno_use
)
771 if (NONDEBUG_INSN_P (next
->insn
)
772 && QUEUE_INDEX (next
->insn
) != QUEUE_SCHEDULED
)
777 /* Print info about the current register pressure and its excess for
780 print_curr_reg_pressure (void)
785 fprintf (sched_dump
, ";;\t");
786 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
788 cl
= ira_reg_class_cover
[i
];
789 gcc_assert (curr_reg_pressure
[cl
] >= 0);
790 fprintf (sched_dump
, " %s:%d(%d)", reg_class_names
[cl
],
791 curr_reg_pressure
[cl
],
792 curr_reg_pressure
[cl
] - ira_available_class_regs
[cl
]);
794 fprintf (sched_dump
, "\n");
797 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
798 so that insns independent of the last scheduled insn will be preferred
799 over dependent instructions. */
801 static rtx last_scheduled_insn
;
803 /* Cached cost of the instruction. Use below function to get cost of the
804 insn. -1 here means that the field is not initialized. */
805 #define INSN_COST(INSN) (HID (INSN)->cost)
807 /* Compute cost of executing INSN.
808 This is the number of cycles between instruction issue and
809 instruction results. */
817 if (recog_memoized (insn
) < 0)
820 cost
= insn_default_latency (insn
);
827 cost
= INSN_COST (insn
);
831 /* A USE insn, or something else we don't need to
832 understand. We can't pass these directly to
833 result_ready_cost or insn_default_latency because it will
834 trigger a fatal error for unrecognizable insns. */
835 if (recog_memoized (insn
) < 0)
837 INSN_COST (insn
) = 0;
842 cost
= insn_default_latency (insn
);
846 INSN_COST (insn
) = cost
;
853 /* Compute cost of dependence LINK.
854 This is the number of cycles between instruction issue and
856 ??? We also use this function to call recog_memoized on all insns. */
858 dep_cost_1 (dep_t link
, dw_t dw
)
860 rtx insn
= DEP_PRO (link
);
861 rtx used
= DEP_CON (link
);
864 /* A USE insn should never require the value used to be computed.
865 This allows the computation of a function's result and parameter
866 values to overlap the return and call. We don't care about the
867 the dependence cost when only decreasing register pressure. */
868 if (recog_memoized (used
) < 0)
871 recog_memoized (insn
);
875 enum reg_note dep_type
= DEP_TYPE (link
);
877 cost
= insn_cost (insn
);
879 if (INSN_CODE (insn
) >= 0)
881 if (dep_type
== REG_DEP_ANTI
)
883 else if (dep_type
== REG_DEP_OUTPUT
)
885 cost
= (insn_default_latency (insn
)
886 - insn_default_latency (used
));
890 else if (bypass_p (insn
))
891 cost
= insn_latency (insn
, used
);
895 if (targetm
.sched
.adjust_cost_2
)
896 cost
= targetm
.sched
.adjust_cost_2 (used
, (int) dep_type
, insn
, cost
,
898 else if (targetm
.sched
.adjust_cost
!= NULL
)
900 /* This variable is used for backward compatibility with the
902 rtx dep_cost_rtx_link
= alloc_INSN_LIST (NULL_RTX
, NULL_RTX
);
904 /* Make it self-cycled, so that if some tries to walk over this
905 incomplete list he/she will be caught in an endless loop. */
906 XEXP (dep_cost_rtx_link
, 1) = dep_cost_rtx_link
;
908 /* Targets use only REG_NOTE_KIND of the link. */
909 PUT_REG_NOTE_KIND (dep_cost_rtx_link
, DEP_TYPE (link
));
911 cost
= targetm
.sched
.adjust_cost (used
, dep_cost_rtx_link
,
914 free_INSN_LIST_node (dep_cost_rtx_link
);
924 /* Compute cost of dependence LINK.
925 This is the number of cycles between instruction issue and
926 instruction results. */
928 dep_cost (dep_t link
)
930 return dep_cost_1 (link
, 0);
933 /* Use this sel-sched.c friendly function in reorder2 instead of increasing
934 INSN_PRIORITY explicitly. */
936 increase_insn_priority (rtx insn
, int amount
)
940 /* We're dealing with haifa-sched.c INSN_PRIORITY. */
941 if (INSN_PRIORITY_KNOWN (insn
))
942 INSN_PRIORITY (insn
) += amount
;
946 /* In sel-sched.c INSN_PRIORITY is not kept up to date.
947 Use EXPR_PRIORITY instead. */
948 sel_add_to_insn_priority (insn
, amount
);
952 /* Return 'true' if DEP should be included in priority calculations. */
954 contributes_to_priority_p (dep_t dep
)
956 if (DEBUG_INSN_P (DEP_CON (dep
))
957 || DEBUG_INSN_P (DEP_PRO (dep
)))
960 /* Critical path is meaningful in block boundaries only. */
961 if (!current_sched_info
->contributes_to_priority (DEP_CON (dep
),
965 /* If flag COUNT_SPEC_IN_CRITICAL_PATH is set,
966 then speculative instructions will less likely be
967 scheduled. That is because the priority of
968 their producers will increase, and, thus, the
969 producers will more likely be scheduled, thus,
970 resolving the dependence. */
971 if (sched_deps_info
->generate_spec_deps
972 && !(spec_info
->flags
& COUNT_SPEC_IN_CRITICAL_PATH
)
973 && (DEP_STATUS (dep
) & SPECULATIVE
))
979 /* Compute the number of nondebug forward deps of an insn. */
982 dep_list_size (rtx insn
)
984 sd_iterator_def sd_it
;
986 int dbgcount
= 0, nodbgcount
= 0;
988 if (!MAY_HAVE_DEBUG_INSNS
)
989 return sd_lists_size (insn
, SD_LIST_FORW
);
991 FOR_EACH_DEP (insn
, SD_LIST_FORW
, sd_it
, dep
)
993 if (DEBUG_INSN_P (DEP_CON (dep
)))
995 else if (!DEBUG_INSN_P (DEP_PRO (dep
)))
999 gcc_assert (dbgcount
+ nodbgcount
== sd_lists_size (insn
, SD_LIST_FORW
));
1004 /* Compute the priority number for INSN. */
1008 if (! INSN_P (insn
))
1011 /* We should not be interested in priority of an already scheduled insn. */
1012 gcc_assert (QUEUE_INDEX (insn
) != QUEUE_SCHEDULED
);
1014 if (!INSN_PRIORITY_KNOWN (insn
))
1016 int this_priority
= -1;
1018 if (dep_list_size (insn
) == 0)
1019 /* ??? We should set INSN_PRIORITY to insn_cost when and insn has
1020 some forward deps but all of them are ignored by
1021 contributes_to_priority hook. At the moment we set priority of
1023 this_priority
= insn_cost (insn
);
1026 rtx prev_first
, twin
;
1029 /* For recovery check instructions we calculate priority slightly
1030 different than that of normal instructions. Instead of walking
1031 through INSN_FORW_DEPS (check) list, we walk through
1032 INSN_FORW_DEPS list of each instruction in the corresponding
1035 /* Selective scheduling does not define RECOVERY_BLOCK macro. */
1036 rec
= sel_sched_p () ? NULL
: RECOVERY_BLOCK (insn
);
1037 if (!rec
|| rec
== EXIT_BLOCK_PTR
)
1039 prev_first
= PREV_INSN (insn
);
1044 prev_first
= NEXT_INSN (BB_HEAD (rec
));
1045 twin
= PREV_INSN (BB_END (rec
));
1050 sd_iterator_def sd_it
;
1053 FOR_EACH_DEP (twin
, SD_LIST_FORW
, sd_it
, dep
)
1058 next
= DEP_CON (dep
);
1060 if (BLOCK_FOR_INSN (next
) != rec
)
1064 if (!contributes_to_priority_p (dep
))
1068 cost
= dep_cost (dep
);
1071 struct _dep _dep1
, *dep1
= &_dep1
;
1073 init_dep (dep1
, insn
, next
, REG_DEP_ANTI
);
1075 cost
= dep_cost (dep1
);
1078 next_priority
= cost
+ priority (next
);
1080 if (next_priority
> this_priority
)
1081 this_priority
= next_priority
;
1085 twin
= PREV_INSN (twin
);
1087 while (twin
!= prev_first
);
1090 if (this_priority
< 0)
1092 gcc_assert (this_priority
== -1);
1094 this_priority
= insn_cost (insn
);
1097 INSN_PRIORITY (insn
) = this_priority
;
1098 INSN_PRIORITY_STATUS (insn
) = 1;
1101 return INSN_PRIORITY (insn
);
1104 /* Macros and functions for keeping the priority queue sorted, and
1105 dealing with queuing and dequeuing of instructions. */
1107 #define SCHED_SORT(READY, N_READY) \
1108 do { if ((N_READY) == 2) \
1109 swap_sort (READY, N_READY); \
1110 else if ((N_READY) > 2) \
1111 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
1114 /* Setup info about the current register pressure impact of scheduling
1115 INSN at the current scheduling point. */
1117 setup_insn_reg_pressure_info (rtx insn
)
1119 int i
, change
, before
, after
, hard_regno
;
1120 int excess_cost_change
;
1121 enum machine_mode mode
;
1123 struct reg_pressure_data
*pressure_info
;
1124 int *max_reg_pressure
;
1125 struct reg_use_data
*use
;
1126 static int death
[N_REG_CLASSES
];
1128 gcc_checking_assert (!DEBUG_INSN_P (insn
));
1130 excess_cost_change
= 0;
1131 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1132 death
[ira_reg_class_cover
[i
]] = 0;
1133 for (use
= INSN_REG_USE_LIST (insn
); use
!= NULL
; use
= use
->next_insn_use
)
1134 if (dying_use_p (use
))
1136 cl
= sched_regno_cover_class
[use
->regno
];
1137 if (use
->regno
< FIRST_PSEUDO_REGISTER
)
1140 death
[cl
] += ira_reg_class_nregs
[cl
][PSEUDO_REGNO_MODE (use
->regno
)];
1142 pressure_info
= INSN_REG_PRESSURE (insn
);
1143 max_reg_pressure
= INSN_MAX_REG_PRESSURE (insn
);
1144 gcc_assert (pressure_info
!= NULL
&& max_reg_pressure
!= NULL
);
1145 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1147 cl
= ira_reg_class_cover
[i
];
1148 gcc_assert (curr_reg_pressure
[cl
] >= 0);
1149 change
= (int) pressure_info
[i
].set_increase
- death
[cl
];
1150 before
= MAX (0, max_reg_pressure
[i
] - ira_available_class_regs
[cl
]);
1151 after
= MAX (0, max_reg_pressure
[i
] + change
1152 - ira_available_class_regs
[cl
]);
1153 hard_regno
= ira_class_hard_regs
[cl
][0];
1154 gcc_assert (hard_regno
>= 0);
1155 mode
= reg_raw_mode
[hard_regno
];
1156 excess_cost_change
+= ((after
- before
)
1157 * (ira_memory_move_cost
[mode
][cl
][0]
1158 + ira_memory_move_cost
[mode
][cl
][1]));
1160 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insn
) = excess_cost_change
;
1163 /* Returns a positive value if x is preferred; returns a negative value if
1164 y is preferred. Should never return 0, since that will make the sort
1168 rank_for_schedule (const void *x
, const void *y
)
1170 rtx tmp
= *(const rtx
*) y
;
1171 rtx tmp2
= *(const rtx
*) x
;
1173 int tmp_class
, tmp2_class
;
1174 int val
, priority_val
, info_val
;
1176 if (MAY_HAVE_DEBUG_INSNS
)
1178 /* Schedule debug insns as early as possible. */
1179 if (DEBUG_INSN_P (tmp
) && !DEBUG_INSN_P (tmp2
))
1181 else if (DEBUG_INSN_P (tmp2
))
1185 /* The insn in a schedule group should be issued the first. */
1186 if (flag_sched_group_heuristic
&&
1187 SCHED_GROUP_P (tmp
) != SCHED_GROUP_P (tmp2
))
1188 return SCHED_GROUP_P (tmp2
) ? 1 : -1;
1190 /* Make sure that priority of TMP and TMP2 are initialized. */
1191 gcc_assert (INSN_PRIORITY_KNOWN (tmp
) && INSN_PRIORITY_KNOWN (tmp2
));
1193 if (sched_pressure_p
)
1197 /* Prefer insn whose scheduling results in the smallest register
1199 if ((diff
= (INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp
)
1200 + (INSN_TICK (tmp
) > clock_var
1201 ? INSN_TICK (tmp
) - clock_var
: 0)
1202 - INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp2
)
1203 - (INSN_TICK (tmp2
) > clock_var
1204 ? INSN_TICK (tmp2
) - clock_var
: 0))) != 0)
1209 if (sched_pressure_p
1210 && (INSN_TICK (tmp2
) > clock_var
|| INSN_TICK (tmp
) > clock_var
))
1212 if (INSN_TICK (tmp
) <= clock_var
)
1214 else if (INSN_TICK (tmp2
) <= clock_var
)
1217 return INSN_TICK (tmp
) - INSN_TICK (tmp2
);
1219 /* Prefer insn with higher priority. */
1220 priority_val
= INSN_PRIORITY (tmp2
) - INSN_PRIORITY (tmp
);
1222 if (flag_sched_critical_path_heuristic
&& priority_val
)
1223 return priority_val
;
1225 /* Prefer speculative insn with greater dependencies weakness. */
1226 if (flag_sched_spec_insn_heuristic
&& spec_info
)
1232 ds1
= TODO_SPEC (tmp
) & SPECULATIVE
;
1234 dw1
= ds_weak (ds1
);
1238 ds2
= TODO_SPEC (tmp2
) & SPECULATIVE
;
1240 dw2
= ds_weak (ds2
);
1245 if (dw
> (NO_DEP_WEAK
/ 8) || dw
< -(NO_DEP_WEAK
/ 8))
1249 info_val
= (*current_sched_info
->rank
) (tmp
, tmp2
);
1250 if(flag_sched_rank_heuristic
&& info_val
)
1253 if (flag_sched_last_insn_heuristic
)
1255 last
= last_scheduled_insn
;
1257 if (DEBUG_INSN_P (last
) && last
!= current_sched_info
->prev_head
)
1259 last
= PREV_INSN (last
);
1260 while (!NONDEBUG_INSN_P (last
)
1261 && last
!= current_sched_info
->prev_head
);
1264 /* Compare insns based on their relation to the last scheduled
1266 if (flag_sched_last_insn_heuristic
&& NONDEBUG_INSN_P (last
))
1271 /* Classify the instructions into three classes:
1272 1) Data dependent on last schedule insn.
1273 2) Anti/Output dependent on last scheduled insn.
1274 3) Independent of last scheduled insn, or has latency of one.
1275 Choose the insn from the highest numbered class if different. */
1276 dep1
= sd_find_dep_between (last
, tmp
, true);
1278 if (dep1
== NULL
|| dep_cost (dep1
) == 1)
1280 else if (/* Data dependence. */
1281 DEP_TYPE (dep1
) == REG_DEP_TRUE
)
1286 dep2
= sd_find_dep_between (last
, tmp2
, true);
1288 if (dep2
== NULL
|| dep_cost (dep2
) == 1)
1290 else if (/* Data dependence. */
1291 DEP_TYPE (dep2
) == REG_DEP_TRUE
)
1296 if ((val
= tmp2_class
- tmp_class
))
1300 /* Prefer the insn which has more later insns that depend on it.
1301 This gives the scheduler more freedom when scheduling later
1302 instructions at the expense of added register pressure. */
1304 val
= (dep_list_size (tmp2
) - dep_list_size (tmp
));
1306 if (flag_sched_dep_count_heuristic
&& val
!= 0)
1309 /* If insns are equally good, sort by INSN_LUID (original insn order),
1310 so that we make the sort stable. This minimizes instruction movement,
1311 thus minimizing sched's effect on debugging and cross-jumping. */
1312 return INSN_LUID (tmp
) - INSN_LUID (tmp2
);
1315 /* Resort the array A in which only element at index N may be out of order. */
1317 HAIFA_INLINE
static void
1318 swap_sort (rtx
*a
, int n
)
1320 rtx insn
= a
[n
- 1];
1323 while (i
>= 0 && rank_for_schedule (a
+ i
, &insn
) >= 0)
1331 /* Add INSN to the insn queue so that it can be executed at least
1332 N_CYCLES after the currently executing insn. Preserve insns
1333 chain for debugging purposes. */
1335 HAIFA_INLINE
static void
1336 queue_insn (rtx insn
, int n_cycles
)
1338 int next_q
= NEXT_Q_AFTER (q_ptr
, n_cycles
);
1339 rtx link
= alloc_INSN_LIST (insn
, insn_queue
[next_q
]);
1341 gcc_assert (n_cycles
<= max_insn_queue_index
);
1342 gcc_assert (!DEBUG_INSN_P (insn
));
1344 insn_queue
[next_q
] = link
;
1347 if (sched_verbose
>= 2)
1349 fprintf (sched_dump
, ";;\t\tReady-->Q: insn %s: ",
1350 (*current_sched_info
->print_insn
) (insn
, 0));
1352 fprintf (sched_dump
, "queued for %d cycles.\n", n_cycles
);
1355 QUEUE_INDEX (insn
) = next_q
;
1358 /* Remove INSN from queue. */
1360 queue_remove (rtx insn
)
1362 gcc_assert (QUEUE_INDEX (insn
) >= 0);
1363 remove_free_INSN_LIST_elem (insn
, &insn_queue
[QUEUE_INDEX (insn
)]);
1365 QUEUE_INDEX (insn
) = QUEUE_NOWHERE
;
1368 /* Return a pointer to the bottom of the ready list, i.e. the insn
1369 with the lowest priority. */
1372 ready_lastpos (struct ready_list
*ready
)
1374 gcc_assert (ready
->n_ready
>= 1);
1375 return ready
->vec
+ ready
->first
- ready
->n_ready
+ 1;
1378 /* Add an element INSN to the ready list so that it ends up with the
1379 lowest/highest priority depending on FIRST_P. */
1381 HAIFA_INLINE
static void
1382 ready_add (struct ready_list
*ready
, rtx insn
, bool first_p
)
1386 if (ready
->first
== ready
->n_ready
)
1388 memmove (ready
->vec
+ ready
->veclen
- ready
->n_ready
,
1389 ready_lastpos (ready
),
1390 ready
->n_ready
* sizeof (rtx
));
1391 ready
->first
= ready
->veclen
- 1;
1393 ready
->vec
[ready
->first
- ready
->n_ready
] = insn
;
1397 if (ready
->first
== ready
->veclen
- 1)
1400 /* ready_lastpos() fails when called with (ready->n_ready == 0). */
1401 memmove (ready
->vec
+ ready
->veclen
- ready
->n_ready
- 1,
1402 ready_lastpos (ready
),
1403 ready
->n_ready
* sizeof (rtx
));
1404 ready
->first
= ready
->veclen
- 2;
1406 ready
->vec
[++(ready
->first
)] = insn
;
1410 if (DEBUG_INSN_P (insn
))
1413 gcc_assert (QUEUE_INDEX (insn
) != QUEUE_READY
);
1414 QUEUE_INDEX (insn
) = QUEUE_READY
;
1417 /* Remove the element with the highest priority from the ready list and
1420 HAIFA_INLINE
static rtx
1421 ready_remove_first (struct ready_list
*ready
)
1425 gcc_assert (ready
->n_ready
);
1426 t
= ready
->vec
[ready
->first
--];
1428 if (DEBUG_INSN_P (t
))
1430 /* If the queue becomes empty, reset it. */
1431 if (ready
->n_ready
== 0)
1432 ready
->first
= ready
->veclen
- 1;
1434 gcc_assert (QUEUE_INDEX (t
) == QUEUE_READY
);
1435 QUEUE_INDEX (t
) = QUEUE_NOWHERE
;
1440 /* The following code implements multi-pass scheduling for the first
1441 cycle. In other words, we will try to choose ready insn which
1442 permits to start maximum number of insns on the same cycle. */
1444 /* Return a pointer to the element INDEX from the ready. INDEX for
1445 insn with the highest priority is 0, and the lowest priority has
1449 ready_element (struct ready_list
*ready
, int index
)
1451 gcc_assert (ready
->n_ready
&& index
< ready
->n_ready
);
1453 return ready
->vec
[ready
->first
- index
];
1456 /* Remove the element INDEX from the ready list and return it. INDEX
1457 for insn with the highest priority is 0, and the lowest priority
1460 HAIFA_INLINE
static rtx
1461 ready_remove (struct ready_list
*ready
, int index
)
1467 return ready_remove_first (ready
);
1468 gcc_assert (ready
->n_ready
&& index
< ready
->n_ready
);
1469 t
= ready
->vec
[ready
->first
- index
];
1471 if (DEBUG_INSN_P (t
))
1473 for (i
= index
; i
< ready
->n_ready
; i
++)
1474 ready
->vec
[ready
->first
- i
] = ready
->vec
[ready
->first
- i
- 1];
1475 QUEUE_INDEX (t
) = QUEUE_NOWHERE
;
1479 /* Remove INSN from the ready list. */
1481 ready_remove_insn (rtx insn
)
1485 for (i
= 0; i
< readyp
->n_ready
; i
++)
1486 if (ready_element (readyp
, i
) == insn
)
1488 ready_remove (readyp
, i
);
1494 /* Sort the ready list READY by ascending priority, using the SCHED_SORT
1498 ready_sort (struct ready_list
*ready
)
1501 rtx
*first
= ready_lastpos (ready
);
1503 if (sched_pressure_p
)
1505 for (i
= 0; i
< ready
->n_ready
; i
++)
1506 if (!DEBUG_INSN_P (first
[i
]))
1507 setup_insn_reg_pressure_info (first
[i
]);
1509 SCHED_SORT (first
, ready
->n_ready
);
1512 /* PREV is an insn that is ready to execute. Adjust its priority if that
1513 will help shorten or lengthen register lifetimes as appropriate. Also
1514 provide a hook for the target to tweak itself. */
1516 HAIFA_INLINE
static void
1517 adjust_priority (rtx prev
)
1519 /* ??? There used to be code here to try and estimate how an insn
1520 affected register lifetimes, but it did it by looking at REG_DEAD
1521 notes, which we removed in schedule_region. Nor did it try to
1522 take into account register pressure or anything useful like that.
1524 Revisit when we have a machine model to work with and not before. */
1526 if (targetm
.sched
.adjust_priority
)
1527 INSN_PRIORITY (prev
) =
1528 targetm
.sched
.adjust_priority (prev
, INSN_PRIORITY (prev
));
1531 /* Advance DFA state STATE on one cycle. */
1533 advance_state (state_t state
)
1535 if (targetm
.sched
.dfa_pre_advance_cycle
)
1536 targetm
.sched
.dfa_pre_advance_cycle ();
1538 if (targetm
.sched
.dfa_pre_cycle_insn
)
1539 state_transition (state
,
1540 targetm
.sched
.dfa_pre_cycle_insn ());
1542 state_transition (state
, NULL
);
1544 if (targetm
.sched
.dfa_post_cycle_insn
)
1545 state_transition (state
,
1546 targetm
.sched
.dfa_post_cycle_insn ());
1548 if (targetm
.sched
.dfa_post_advance_cycle
)
1549 targetm
.sched
.dfa_post_advance_cycle ();
1552 /* Advance time on one cycle. */
1553 HAIFA_INLINE
static void
1554 advance_one_cycle (void)
1556 advance_state (curr_state
);
1557 if (sched_verbose
>= 6)
1558 fprintf (sched_dump
, ";;\tAdvanced a state.\n");
1561 /* Clock at which the previous instruction was issued. */
1562 static int last_clock_var
;
1564 /* Update register pressure after scheduling INSN. */
1566 update_register_pressure (rtx insn
)
1568 struct reg_use_data
*use
;
1569 struct reg_set_data
*set
;
1571 gcc_checking_assert (!DEBUG_INSN_P (insn
));
1573 for (use
= INSN_REG_USE_LIST (insn
); use
!= NULL
; use
= use
->next_insn_use
)
1574 if (dying_use_p (use
) && bitmap_bit_p (curr_reg_live
, use
->regno
))
1575 mark_regno_birth_or_death (use
->regno
, false);
1576 for (set
= INSN_REG_SET_LIST (insn
); set
!= NULL
; set
= set
->next_insn_set
)
1577 mark_regno_birth_or_death (set
->regno
, true);
1580 /* Set up or update (if UPDATE_P) max register pressure (see its
1581 meaning in sched-int.h::_haifa_insn_data) for all current BB insns
1582 after insn AFTER. */
1584 setup_insn_max_reg_pressure (rtx after
, bool update_p
)
1589 static int max_reg_pressure
[N_REG_CLASSES
];
1591 save_reg_pressure ();
1592 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1593 max_reg_pressure
[ira_reg_class_cover
[i
]]
1594 = curr_reg_pressure
[ira_reg_class_cover
[i
]];
1595 for (insn
= NEXT_INSN (after
);
1596 insn
!= NULL_RTX
&& ! BARRIER_P (insn
)
1597 && BLOCK_FOR_INSN (insn
) == BLOCK_FOR_INSN (after
);
1598 insn
= NEXT_INSN (insn
))
1599 if (NONDEBUG_INSN_P (insn
))
1602 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1604 p
= max_reg_pressure
[ira_reg_class_cover
[i
]];
1605 if (INSN_MAX_REG_PRESSURE (insn
)[i
] != p
)
1608 INSN_MAX_REG_PRESSURE (insn
)[i
]
1609 = max_reg_pressure
[ira_reg_class_cover
[i
]];
1612 if (update_p
&& eq_p
)
1614 update_register_pressure (insn
);
1615 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1616 if (max_reg_pressure
[ira_reg_class_cover
[i
]]
1617 < curr_reg_pressure
[ira_reg_class_cover
[i
]])
1618 max_reg_pressure
[ira_reg_class_cover
[i
]]
1619 = curr_reg_pressure
[ira_reg_class_cover
[i
]];
1621 restore_reg_pressure ();
1624 /* Update the current register pressure after scheduling INSN. Update
1625 also max register pressure for unscheduled insns of the current
1628 update_reg_and_insn_max_reg_pressure (rtx insn
)
1631 int before
[N_REG_CLASSES
];
1633 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1634 before
[i
] = curr_reg_pressure
[ira_reg_class_cover
[i
]];
1635 update_register_pressure (insn
);
1636 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1637 if (curr_reg_pressure
[ira_reg_class_cover
[i
]] != before
[i
])
1639 if (i
< ira_reg_class_cover_size
)
1640 setup_insn_max_reg_pressure (insn
, true);
1643 /* Set up register pressure at the beginning of basic block BB whose
1644 insns starting after insn AFTER. Set up also max register pressure
1645 for all insns of the basic block. */
1647 sched_setup_bb_reg_pressure_info (basic_block bb
, rtx after
)
1649 gcc_assert (sched_pressure_p
);
1650 initiate_bb_reg_pressure_info (bb
);
1651 setup_insn_max_reg_pressure (after
, false);
1654 /* INSN is the "currently executing insn". Launch each insn which was
1655 waiting on INSN. READY is the ready list which contains the insns
1656 that are ready to fire. CLOCK is the current cycle. The function
1657 returns necessary cycle advance after issuing the insn (it is not
1658 zero for insns in a schedule group). */
1661 schedule_insn (rtx insn
)
1663 sd_iterator_def sd_it
;
1668 if (sched_verbose
>= 1)
1670 struct reg_pressure_data
*pressure_info
;
1673 print_insn (buf
, insn
, 0);
1675 fprintf (sched_dump
, ";;\t%3i--> %-40s:", clock_var
, buf
);
1677 if (recog_memoized (insn
) < 0)
1678 fprintf (sched_dump
, "nothing");
1680 print_reservation (sched_dump
, insn
);
1681 pressure_info
= INSN_REG_PRESSURE (insn
);
1682 if (pressure_info
!= NULL
)
1684 fputc (':', sched_dump
);
1685 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1686 fprintf (sched_dump
, "%s%+d(%d)",
1687 reg_class_names
[ira_reg_class_cover
[i
]],
1688 pressure_info
[i
].set_increase
, pressure_info
[i
].change
);
1690 fputc ('\n', sched_dump
);
1693 if (sched_pressure_p
&& !DEBUG_INSN_P (insn
))
1694 update_reg_and_insn_max_reg_pressure (insn
);
1696 /* Scheduling instruction should have all its dependencies resolved and
1697 should have been removed from the ready list. */
1698 gcc_assert (sd_lists_empty_p (insn
, SD_LIST_BACK
));
1700 /* Reset debug insns invalidated by moving this insn. */
1701 if (MAY_HAVE_DEBUG_INSNS
&& !DEBUG_INSN_P (insn
))
1702 for (sd_it
= sd_iterator_start (insn
, SD_LIST_BACK
);
1703 sd_iterator_cond (&sd_it
, &dep
);)
1705 rtx dbg
= DEP_PRO (dep
);
1706 struct reg_use_data
*use
, *next
;
1708 gcc_assert (DEBUG_INSN_P (dbg
));
1710 if (sched_verbose
>= 6)
1711 fprintf (sched_dump
, ";;\t\tresetting: debug insn %d\n",
1714 /* ??? Rather than resetting the debug insn, we might be able
1715 to emit a debug temp before the just-scheduled insn, but
1716 this would involve checking that the expression at the
1717 point of the debug insn is equivalent to the expression
1718 before the just-scheduled insn. They might not be: the
1719 expression in the debug insn may depend on other insns not
1720 yet scheduled that set MEMs, REGs or even other debug
1721 insns. It's not clear that attempting to preserve debug
1722 information in these cases is worth the effort, given how
1723 uncommon these resets are and the likelihood that the debug
1724 temps introduced won't survive the schedule change. */
1725 INSN_VAR_LOCATION_LOC (dbg
) = gen_rtx_UNKNOWN_VAR_LOC ();
1726 df_insn_rescan (dbg
);
1728 /* Unknown location doesn't use any registers. */
1729 for (use
= INSN_REG_USE_LIST (dbg
); use
!= NULL
; use
= next
)
1731 struct reg_use_data
*prev
= use
;
1733 /* Remove use from the cyclic next_regno_use chain first. */
1734 while (prev
->next_regno_use
!= use
)
1735 prev
= prev
->next_regno_use
;
1736 prev
->next_regno_use
= use
->next_regno_use
;
1737 next
= use
->next_insn_use
;
1740 INSN_REG_USE_LIST (dbg
) = NULL
;
1742 /* We delete rather than resolve these deps, otherwise we
1743 crash in sched_free_deps(), because forward deps are
1744 expected to be released before backward deps. */
1745 sd_delete_dep (sd_it
);
1748 gcc_assert (QUEUE_INDEX (insn
) == QUEUE_NOWHERE
);
1749 QUEUE_INDEX (insn
) = QUEUE_SCHEDULED
;
1751 gcc_assert (INSN_TICK (insn
) >= MIN_TICK
);
1752 if (INSN_TICK (insn
) > clock_var
)
1753 /* INSN has been prematurely moved from the queue to the ready list.
1754 This is possible only if following flag is set. */
1755 gcc_assert (flag_sched_stalled_insns
);
1757 /* ??? Probably, if INSN is scheduled prematurely, we should leave
1758 INSN_TICK untouched. This is a machine-dependent issue, actually. */
1759 INSN_TICK (insn
) = clock_var
;
1761 /* Update dependent instructions. */
1762 for (sd_it
= sd_iterator_start (insn
, SD_LIST_FORW
);
1763 sd_iterator_cond (&sd_it
, &dep
);)
1765 rtx next
= DEP_CON (dep
);
1767 /* Resolve the dependence between INSN and NEXT.
1768 sd_resolve_dep () moves current dep to another list thus
1769 advancing the iterator. */
1770 sd_resolve_dep (sd_it
);
1772 /* Don't bother trying to mark next as ready if insn is a debug
1773 insn. If insn is the last hard dependency, it will have
1774 already been discounted. */
1775 if (DEBUG_INSN_P (insn
) && !DEBUG_INSN_P (next
))
1778 if (!IS_SPECULATION_BRANCHY_CHECK_P (insn
))
1782 effective_cost
= try_ready (next
);
1784 if (effective_cost
>= 0
1785 && SCHED_GROUP_P (next
)
1786 && advance
< effective_cost
)
1787 advance
= effective_cost
;
1790 /* Check always has only one forward dependence (to the first insn in
1791 the recovery block), therefore, this will be executed only once. */
1793 gcc_assert (sd_lists_empty_p (insn
, SD_LIST_FORW
));
1794 fix_recovery_deps (RECOVERY_BLOCK (insn
));
1798 /* This is the place where scheduler doesn't *basically* need backward and
1799 forward dependencies for INSN anymore. Nevertheless they are used in
1800 heuristics in rank_for_schedule (), early_queue_to_ready () and in
1801 some targets (e.g. rs6000). Thus the earliest place where we *can*
1802 remove dependencies is after targetm.sched.finish () call in
1803 schedule_block (). But, on the other side, the safest place to remove
1804 dependencies is when we are finishing scheduling entire region. As we
1805 don't generate [many] dependencies during scheduling itself, we won't
1806 need memory until beginning of next region.
1807 Bottom line: Dependencies are removed for all insns in the end of
1808 scheduling the region. */
1810 /* Annotate the instruction with issue information -- TImode
1811 indicates that the instruction is expected not to be able
1812 to issue on the same cycle as the previous insn. A machine
1813 may use this information to decide how the instruction should
1816 && GET_CODE (PATTERN (insn
)) != USE
1817 && GET_CODE (PATTERN (insn
)) != CLOBBER
1818 && !DEBUG_INSN_P (insn
))
1820 if (reload_completed
)
1821 PUT_MODE (insn
, clock_var
> last_clock_var
? TImode
: VOIDmode
);
1822 last_clock_var
= clock_var
;
1828 /* Functions for handling of notes. */
1830 /* Add note list that ends on FROM_END to the end of TO_ENDP. */
1832 concat_note_lists (rtx from_end
, rtx
*to_endp
)
1836 /* It's easy when have nothing to concat. */
1837 if (from_end
== NULL
)
1840 /* It's also easy when destination is empty. */
1841 if (*to_endp
== NULL
)
1843 *to_endp
= from_end
;
1847 from_start
= from_end
;
1848 while (PREV_INSN (from_start
) != NULL
)
1849 from_start
= PREV_INSN (from_start
);
1851 PREV_INSN (from_start
) = *to_endp
;
1852 NEXT_INSN (*to_endp
) = from_start
;
1853 *to_endp
= from_end
;
1856 /* Delete notes between HEAD and TAIL and put them in the chain
1857 of notes ended by NOTE_LIST. */
1859 remove_notes (rtx head
, rtx tail
)
1861 rtx next_tail
, insn
, next
;
1864 if (head
== tail
&& !INSN_P (head
))
1867 next_tail
= NEXT_INSN (tail
);
1868 for (insn
= head
; insn
!= next_tail
; insn
= next
)
1870 next
= NEXT_INSN (insn
);
1874 switch (NOTE_KIND (insn
))
1876 case NOTE_INSN_BASIC_BLOCK
:
1879 case NOTE_INSN_EPILOGUE_BEG
:
1883 add_reg_note (next
, REG_SAVE_NOTE
,
1884 GEN_INT (NOTE_INSN_EPILOGUE_BEG
));
1892 /* Add the note to list that ends at NOTE_LIST. */
1893 PREV_INSN (insn
) = note_list
;
1894 NEXT_INSN (insn
) = NULL_RTX
;
1896 NEXT_INSN (note_list
) = insn
;
1901 gcc_assert ((sel_sched_p () || insn
!= tail
) && insn
!= head
);
1906 /* Return the head and tail pointers of ebb starting at BEG and ending
1909 get_ebb_head_tail (basic_block beg
, basic_block end
, rtx
*headp
, rtx
*tailp
)
1911 rtx beg_head
= BB_HEAD (beg
);
1912 rtx beg_tail
= BB_END (beg
);
1913 rtx end_head
= BB_HEAD (end
);
1914 rtx end_tail
= BB_END (end
);
1916 /* Don't include any notes or labels at the beginning of the BEG
1917 basic block, or notes at the end of the END basic blocks. */
1919 if (LABEL_P (beg_head
))
1920 beg_head
= NEXT_INSN (beg_head
);
1922 while (beg_head
!= beg_tail
)
1923 if (NOTE_P (beg_head
) || BOUNDARY_DEBUG_INSN_P (beg_head
))
1924 beg_head
= NEXT_INSN (beg_head
);
1931 end_head
= beg_head
;
1932 else if (LABEL_P (end_head
))
1933 end_head
= NEXT_INSN (end_head
);
1935 while (end_head
!= end_tail
)
1936 if (NOTE_P (end_tail
) || BOUNDARY_DEBUG_INSN_P (end_tail
))
1937 end_tail
= PREV_INSN (end_tail
);
1944 /* Return nonzero if there are no real insns in the range [ HEAD, TAIL ]. */
1947 no_real_insns_p (const_rtx head
, const_rtx tail
)
1949 while (head
!= NEXT_INSN (tail
))
1951 if (!NOTE_P (head
) && !LABEL_P (head
)
1952 && !BOUNDARY_DEBUG_INSN_P (head
))
1954 head
= NEXT_INSN (head
);
1959 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
1960 previously found among the insns. Insert them just before HEAD. */
1962 restore_other_notes (rtx head
, basic_block head_bb
)
1966 rtx note_head
= note_list
;
1969 head_bb
= BLOCK_FOR_INSN (head
);
1971 head
= NEXT_INSN (bb_note (head_bb
));
1973 while (PREV_INSN (note_head
))
1975 set_block_for_insn (note_head
, head_bb
);
1976 note_head
= PREV_INSN (note_head
);
1978 /* In the above cycle we've missed this note. */
1979 set_block_for_insn (note_head
, head_bb
);
1981 PREV_INSN (note_head
) = PREV_INSN (head
);
1982 NEXT_INSN (PREV_INSN (head
)) = note_head
;
1983 PREV_INSN (head
) = note_list
;
1984 NEXT_INSN (note_list
) = head
;
1986 if (BLOCK_FOR_INSN (head
) != head_bb
)
1987 BB_END (head_bb
) = note_list
;
1995 /* Move insns that became ready to fire from queue to ready list. */
1998 queue_to_ready (struct ready_list
*ready
)
2004 q_ptr
= NEXT_Q (q_ptr
);
2006 if (dbg_cnt (sched_insn
) == false)
2007 /* If debug counter is activated do not requeue insn next after
2008 last_scheduled_insn. */
2009 skip_insn
= next_nonnote_nondebug_insn (last_scheduled_insn
);
2011 skip_insn
= NULL_RTX
;
2013 /* Add all pending insns that can be scheduled without stalls to the
2015 for (link
= insn_queue
[q_ptr
]; link
; link
= XEXP (link
, 1))
2017 insn
= XEXP (link
, 0);
2020 if (sched_verbose
>= 2)
2021 fprintf (sched_dump
, ";;\t\tQ-->Ready: insn %s: ",
2022 (*current_sched_info
->print_insn
) (insn
, 0));
2024 /* If the ready list is full, delay the insn for 1 cycle.
2025 See the comment in schedule_block for the rationale. */
2026 if (!reload_completed
2027 && ready
->n_ready
- ready
->n_debug
> MAX_SCHED_READY_INSNS
2028 && !SCHED_GROUP_P (insn
)
2029 && insn
!= skip_insn
)
2031 if (sched_verbose
>= 2)
2032 fprintf (sched_dump
, "requeued because ready full\n");
2033 queue_insn (insn
, 1);
2037 ready_add (ready
, insn
, false);
2038 if (sched_verbose
>= 2)
2039 fprintf (sched_dump
, "moving to ready without stalls\n");
2042 free_INSN_LIST_list (&insn_queue
[q_ptr
]);
2044 /* If there are no ready insns, stall until one is ready and add all
2045 of the pending insns at that point to the ready list. */
2046 if (ready
->n_ready
== 0)
2050 for (stalls
= 1; stalls
<= max_insn_queue_index
; stalls
++)
2052 if ((link
= insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]))
2054 for (; link
; link
= XEXP (link
, 1))
2056 insn
= XEXP (link
, 0);
2059 if (sched_verbose
>= 2)
2060 fprintf (sched_dump
, ";;\t\tQ-->Ready: insn %s: ",
2061 (*current_sched_info
->print_insn
) (insn
, 0));
2063 ready_add (ready
, insn
, false);
2064 if (sched_verbose
>= 2)
2065 fprintf (sched_dump
, "moving to ready with %d stalls\n", stalls
);
2067 free_INSN_LIST_list (&insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]);
2069 advance_one_cycle ();
2074 advance_one_cycle ();
2077 q_ptr
= NEXT_Q_AFTER (q_ptr
, stalls
);
2078 clock_var
+= stalls
;
2082 /* Used by early_queue_to_ready. Determines whether it is "ok" to
2083 prematurely move INSN from the queue to the ready list. Currently,
2084 if a target defines the hook 'is_costly_dependence', this function
2085 uses the hook to check whether there exist any dependences which are
2086 considered costly by the target, between INSN and other insns that
2087 have already been scheduled. Dependences are checked up to Y cycles
2088 back, with default Y=1; The flag -fsched-stalled-insns-dep=Y allows
2089 controlling this value.
2090 (Other considerations could be taken into account instead (or in
2091 addition) depending on user flags and target hooks. */
2094 ok_for_early_queue_removal (rtx insn
)
2097 rtx prev_insn
= last_scheduled_insn
;
2099 if (targetm
.sched
.is_costly_dependence
)
2101 for (n_cycles
= flag_sched_stalled_insns_dep
; n_cycles
; n_cycles
--)
2103 for ( ; prev_insn
; prev_insn
= PREV_INSN (prev_insn
))
2107 if (prev_insn
== current_sched_info
->prev_head
)
2113 if (!NOTE_P (prev_insn
))
2117 dep
= sd_find_dep_between (prev_insn
, insn
, true);
2121 cost
= dep_cost (dep
);
2123 if (targetm
.sched
.is_costly_dependence (dep
, cost
,
2124 flag_sched_stalled_insns_dep
- n_cycles
))
2129 if (GET_MODE (prev_insn
) == TImode
) /* end of dispatch group */
2135 prev_insn
= PREV_INSN (prev_insn
);
2143 /* Remove insns from the queue, before they become "ready" with respect
2144 to FU latency considerations. */
2147 early_queue_to_ready (state_t state
, struct ready_list
*ready
)
2155 state_t temp_state
= alloca (dfa_state_size
);
2157 int insns_removed
= 0;
2160 Flag '-fsched-stalled-insns=X' determines the aggressiveness of this
2163 X == 0: There is no limit on how many queued insns can be removed
2164 prematurely. (flag_sched_stalled_insns = -1).
2166 X >= 1: Only X queued insns can be removed prematurely in each
2167 invocation. (flag_sched_stalled_insns = X).
2169 Otherwise: Early queue removal is disabled.
2170 (flag_sched_stalled_insns = 0)
2173 if (! flag_sched_stalled_insns
)
2176 for (stalls
= 0; stalls
<= max_insn_queue_index
; stalls
++)
2178 if ((link
= insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]))
2180 if (sched_verbose
> 6)
2181 fprintf (sched_dump
, ";; look at index %d + %d\n", q_ptr
, stalls
);
2186 next_link
= XEXP (link
, 1);
2187 insn
= XEXP (link
, 0);
2188 if (insn
&& sched_verbose
> 6)
2189 print_rtl_single (sched_dump
, insn
);
2191 memcpy (temp_state
, state
, dfa_state_size
);
2192 if (recog_memoized (insn
) < 0)
2193 /* non-negative to indicate that it's not ready
2194 to avoid infinite Q->R->Q->R... */
2197 cost
= state_transition (temp_state
, insn
);
2199 if (sched_verbose
>= 6)
2200 fprintf (sched_dump
, "transition cost = %d\n", cost
);
2202 move_to_ready
= false;
2205 move_to_ready
= ok_for_early_queue_removal (insn
);
2206 if (move_to_ready
== true)
2208 /* move from Q to R */
2210 ready_add (ready
, insn
, false);
2213 XEXP (prev_link
, 1) = next_link
;
2215 insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)] = next_link
;
2217 free_INSN_LIST_node (link
);
2219 if (sched_verbose
>= 2)
2220 fprintf (sched_dump
, ";;\t\tEarly Q-->Ready: insn %s\n",
2221 (*current_sched_info
->print_insn
) (insn
, 0));
2224 if (insns_removed
== flag_sched_stalled_insns
)
2225 /* Remove no more than flag_sched_stalled_insns insns
2226 from Q at a time. */
2227 return insns_removed
;
2231 if (move_to_ready
== false)
2238 } /* for stalls.. */
2240 return insns_removed
;
2244 /* Print the ready list for debugging purposes. Callable from debugger. */
2247 debug_ready_list (struct ready_list
*ready
)
2252 if (ready
->n_ready
== 0)
2254 fprintf (sched_dump
, "\n");
2258 p
= ready_lastpos (ready
);
2259 for (i
= 0; i
< ready
->n_ready
; i
++)
2261 fprintf (sched_dump
, " %s:%d",
2262 (*current_sched_info
->print_insn
) (p
[i
], 0),
2264 if (sched_pressure_p
)
2265 fprintf (sched_dump
, "(cost=%d",
2266 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (p
[i
]));
2267 if (INSN_TICK (p
[i
]) > clock_var
)
2268 fprintf (sched_dump
, ":delay=%d", INSN_TICK (p
[i
]) - clock_var
);
2269 if (sched_pressure_p
)
2270 fprintf (sched_dump
, ")");
2272 fprintf (sched_dump
, "\n");
2275 /* Search INSN for REG_SAVE_NOTE notes and convert them back into insn
2276 NOTEs. This is used for NOTE_INSN_EPILOGUE_BEG, so that sched-ebb
2277 replaces the epilogue note in the correct basic block. */
2279 reemit_notes (rtx insn
)
2281 rtx note
, last
= insn
;
2283 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
2285 if (REG_NOTE_KIND (note
) == REG_SAVE_NOTE
)
2287 enum insn_note note_type
= (enum insn_note
) INTVAL (XEXP (note
, 0));
2289 last
= emit_note_before (note_type
, last
);
2290 remove_note (insn
, note
);
2295 /* Move INSN. Reemit notes if needed. Update CFG, if needed. */
2297 move_insn (rtx insn
, rtx last
, rtx nt
)
2299 if (PREV_INSN (insn
) != last
)
2305 bb
= BLOCK_FOR_INSN (insn
);
2307 /* BB_HEAD is either LABEL or NOTE. */
2308 gcc_assert (BB_HEAD (bb
) != insn
);
2310 if (BB_END (bb
) == insn
)
2311 /* If this is last instruction in BB, move end marker one
2314 /* Jumps are always placed at the end of basic block. */
2315 jump_p
= control_flow_insn_p (insn
);
2318 || ((common_sched_info
->sched_pass_id
== SCHED_RGN_PASS
)
2319 && IS_SPECULATION_BRANCHY_CHECK_P (insn
))
2320 || (common_sched_info
->sched_pass_id
2321 == SCHED_EBB_PASS
));
2323 gcc_assert (BLOCK_FOR_INSN (PREV_INSN (insn
)) == bb
);
2325 BB_END (bb
) = PREV_INSN (insn
);
2328 gcc_assert (BB_END (bb
) != last
);
2331 /* We move the block note along with jump. */
2335 note
= NEXT_INSN (insn
);
2336 while (NOTE_NOT_BB_P (note
) && note
!= nt
)
2337 note
= NEXT_INSN (note
);
2341 || BARRIER_P (note
)))
2342 note
= NEXT_INSN (note
);
2344 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
2349 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (note
);
2350 PREV_INSN (NEXT_INSN (note
)) = PREV_INSN (insn
);
2352 NEXT_INSN (note
) = NEXT_INSN (last
);
2353 PREV_INSN (NEXT_INSN (last
)) = note
;
2355 NEXT_INSN (last
) = insn
;
2356 PREV_INSN (insn
) = last
;
2358 bb
= BLOCK_FOR_INSN (last
);
2362 fix_jump_move (insn
);
2364 if (BLOCK_FOR_INSN (insn
) != bb
)
2365 move_block_after_check (insn
);
2367 gcc_assert (BB_END (bb
) == last
);
2370 df_insn_change_bb (insn
, bb
);
2372 /* Update BB_END, if needed. */
2373 if (BB_END (bb
) == last
)
2377 SCHED_GROUP_P (insn
) = 0;
2380 /* Return true if scheduling INSN will finish current clock cycle. */
2382 insn_finishes_cycle_p (rtx insn
)
2384 if (SCHED_GROUP_P (insn
))
2385 /* After issuing INSN, rest of the sched_group will be forced to issue
2386 in order. Don't make any plans for the rest of cycle. */
2389 /* Finishing the block will, apparently, finish the cycle. */
2390 if (current_sched_info
->insn_finishes_block_p
2391 && current_sched_info
->insn_finishes_block_p (insn
))
2397 /* The following structure describe an entry of the stack of choices. */
2400 /* Ordinal number of the issued insn in the ready queue. */
2402 /* The number of the rest insns whose issues we should try. */
2404 /* The number of issued essential insns. */
2406 /* State after issuing the insn. */
2410 /* The following array is used to implement a stack of choices used in
2411 function max_issue. */
2412 static struct choice_entry
*choice_stack
;
2414 /* The following variable value is number of essential insns issued on
2415 the current cycle. An insn is essential one if it changes the
2416 processors state. */
2417 int cycle_issued_insns
;
2419 /* This holds the value of the target dfa_lookahead hook. */
2422 /* The following variable value is maximal number of tries of issuing
2423 insns for the first cycle multipass insn scheduling. We define
2424 this value as constant*(DFA_LOOKAHEAD**ISSUE_RATE). We would not
2425 need this constraint if all real insns (with non-negative codes)
2426 had reservations because in this case the algorithm complexity is
2427 O(DFA_LOOKAHEAD**ISSUE_RATE). Unfortunately, the dfa descriptions
2428 might be incomplete and such insn might occur. For such
2429 descriptions, the complexity of algorithm (without the constraint)
2430 could achieve DFA_LOOKAHEAD ** N , where N is the queue length. */
2431 static int max_lookahead_tries
;
2433 /* The following value is value of hook
2434 `first_cycle_multipass_dfa_lookahead' at the last call of
2436 static int cached_first_cycle_multipass_dfa_lookahead
= 0;
2438 /* The following value is value of `issue_rate' at the last call of
2440 static int cached_issue_rate
= 0;
2442 /* The following function returns maximal (or close to maximal) number
2443 of insns which can be issued on the same cycle and one of which
2444 insns is insns with the best rank (the first insn in READY). To
2445 make this function tries different samples of ready insns. READY
2446 is current queue `ready'. Global array READY_TRY reflects what
2447 insns are already issued in this try. MAX_POINTS is the sum of points
2448 of all instructions in READY. The function stops immediately,
2449 if it reached the such a solution, that all instruction can be issued.
2450 INDEX will contain index of the best insn in READY. The following
2451 function is used only for first cycle multipass scheduling.
2455 This function expects recognized insns only. All USEs,
2456 CLOBBERs, etc must be filtered elsewhere. */
2458 max_issue (struct ready_list
*ready
, int privileged_n
, state_t state
,
2461 int n
, i
, all
, n_ready
, best
, delay
, tries_num
, max_points
;
2463 struct choice_entry
*top
;
2466 n_ready
= ready
->n_ready
;
2467 gcc_assert (dfa_lookahead
>= 1 && privileged_n
>= 0
2468 && privileged_n
<= n_ready
);
2470 /* Init MAX_LOOKAHEAD_TRIES. */
2471 if (cached_first_cycle_multipass_dfa_lookahead
!= dfa_lookahead
)
2473 cached_first_cycle_multipass_dfa_lookahead
= dfa_lookahead
;
2474 max_lookahead_tries
= 100;
2475 for (i
= 0; i
< issue_rate
; i
++)
2476 max_lookahead_tries
*= dfa_lookahead
;
2479 /* Init max_points. */
2481 more_issue
= issue_rate
- cycle_issued_insns
;
2483 /* ??? We used to assert here that we never issue more insns than issue_rate.
2484 However, some targets (e.g. MIPS/SB1) claim lower issue rate than can be
2485 achieved to get better performance. Until these targets are fixed to use
2486 scheduler hooks to manipulate insns priority instead, the assert should
2489 gcc_assert (more_issue >= 0); */
2491 for (i
= 0; i
< n_ready
; i
++)
2494 if (more_issue
-- > 0)
2495 max_points
+= ISSUE_POINTS (ready_element (ready
, i
));
2500 /* The number of the issued insns in the best solution. */
2505 /* Set initial state of the search. */
2506 memcpy (top
->state
, state
, dfa_state_size
);
2507 top
->rest
= dfa_lookahead
;
2510 /* Count the number of the insns to search among. */
2511 for (all
= i
= 0; i
< n_ready
; i
++)
2515 /* I is the index of the insn to try next. */
2520 if (/* If we've reached a dead end or searched enough of what we have
2523 /* Or have nothing else to try. */
2526 /* ??? (... || i == n_ready). */
2527 gcc_assert (i
<= n_ready
);
2529 if (top
== choice_stack
)
2532 if (best
< top
- choice_stack
)
2537 /* Try to find issued privileged insn. */
2538 while (n
&& !ready_try
[--n
]);
2541 if (/* If all insns are equally good... */
2543 /* Or a privileged insn will be issued. */
2545 /* Then we have a solution. */
2547 best
= top
- choice_stack
;
2548 /* This is the index of the insn issued first in this
2550 *index
= choice_stack
[1].index
;
2551 if (top
->n
== max_points
|| best
== all
)
2556 /* Set ready-list index to point to the last insn
2557 ('i++' below will advance it to the next insn). */
2563 memcpy (state
, top
->state
, dfa_state_size
);
2565 else if (!ready_try
[i
])
2568 if (tries_num
> max_lookahead_tries
)
2570 insn
= ready_element (ready
, i
);
2571 delay
= state_transition (state
, insn
);
2574 if (state_dead_lock_p (state
)
2575 || insn_finishes_cycle_p (insn
))
2576 /* We won't issue any more instructions in the next
2583 if (memcmp (top
->state
, state
, dfa_state_size
) != 0)
2584 n
+= ISSUE_POINTS (insn
);
2586 /* Advance to the next choice_entry. */
2588 /* Initialize it. */
2589 top
->rest
= dfa_lookahead
;
2592 memcpy (top
->state
, state
, dfa_state_size
);
2599 /* Increase ready-list index. */
2603 /* Restore the original state of the DFA. */
2604 memcpy (state
, choice_stack
->state
, dfa_state_size
);
2609 /* The following function chooses insn from READY and modifies
2610 READY. The following function is used only for first
2611 cycle multipass scheduling.
2613 -1 if cycle should be advanced,
2614 0 if INSN_PTR is set to point to the desirable insn,
2615 1 if choose_ready () should be restarted without advancing the cycle. */
2617 choose_ready (struct ready_list
*ready
, rtx
*insn_ptr
)
2621 if (dbg_cnt (sched_insn
) == false)
2625 insn
= next_nonnote_insn (last_scheduled_insn
);
2627 if (QUEUE_INDEX (insn
) == QUEUE_READY
)
2628 /* INSN is in the ready_list. */
2630 ready_remove_insn (insn
);
2635 /* INSN is in the queue. Advance cycle to move it to the ready list. */
2641 if (targetm
.sched
.first_cycle_multipass_dfa_lookahead
)
2642 lookahead
= targetm
.sched
.first_cycle_multipass_dfa_lookahead ();
2643 if (lookahead
<= 0 || SCHED_GROUP_P (ready_element (ready
, 0))
2644 || DEBUG_INSN_P (ready_element (ready
, 0)))
2646 if (targetm
.sched
.dispatch (NULL_RTX
, IS_DISPATCH_ON
))
2647 *insn_ptr
= ready_remove_first_dispatch (ready
);
2649 *insn_ptr
= ready_remove_first (ready
);
2655 /* Try to choose the better insn. */
2656 int index
= 0, i
, n
;
2658 int try_data
= 1, try_control
= 1;
2661 insn
= ready_element (ready
, 0);
2662 if (INSN_CODE (insn
) < 0)
2664 *insn_ptr
= ready_remove_first (ready
);
2669 && spec_info
->flags
& (PREFER_NON_DATA_SPEC
2670 | PREFER_NON_CONTROL_SPEC
))
2672 for (i
= 0, n
= ready
->n_ready
; i
< n
; i
++)
2677 x
= ready_element (ready
, i
);
2680 if (spec_info
->flags
& PREFER_NON_DATA_SPEC
2681 && !(s
& DATA_SPEC
))
2684 if (!(spec_info
->flags
& PREFER_NON_CONTROL_SPEC
)
2689 if (spec_info
->flags
& PREFER_NON_CONTROL_SPEC
2690 && !(s
& CONTROL_SPEC
))
2693 if (!(spec_info
->flags
& PREFER_NON_DATA_SPEC
) || !try_data
)
2699 ts
= TODO_SPEC (insn
);
2700 if ((ts
& SPECULATIVE
)
2701 && (((!try_data
&& (ts
& DATA_SPEC
))
2702 || (!try_control
&& (ts
& CONTROL_SPEC
)))
2703 || (targetm
.sched
.first_cycle_multipass_dfa_lookahead_guard_spec
2705 .first_cycle_multipass_dfa_lookahead_guard_spec (insn
))))
2706 /* Discard speculative instruction that stands first in the ready
2709 change_queue_index (insn
, 1);
2715 for (i
= 1; i
< ready
->n_ready
; i
++)
2717 insn
= ready_element (ready
, i
);
2720 = ((!try_data
&& (TODO_SPEC (insn
) & DATA_SPEC
))
2721 || (!try_control
&& (TODO_SPEC (insn
) & CONTROL_SPEC
)));
2724 /* Let the target filter the search space. */
2725 for (i
= 1; i
< ready
->n_ready
; i
++)
2728 insn
= ready_element (ready
, i
);
2730 #ifdef ENABLE_CHECKING
2731 /* If this insn is recognizable we should have already
2732 recognized it earlier.
2733 ??? Not very clear where this is supposed to be done.
2735 gcc_assert (INSN_CODE (insn
) >= 0
2736 || recog_memoized (insn
) < 0);
2740 = (/* INSN_CODE check can be omitted here as it is also done later
2742 INSN_CODE (insn
) < 0
2743 || (targetm
.sched
.first_cycle_multipass_dfa_lookahead_guard
2744 && !targetm
.sched
.first_cycle_multipass_dfa_lookahead_guard
2748 if (max_issue (ready
, 1, curr_state
, &index
) == 0)
2750 *insn_ptr
= ready_remove_first (ready
);
2751 if (sched_verbose
>= 4)
2752 fprintf (sched_dump
, ";;\t\tChosen insn (but can't issue) : %s \n",
2753 (*current_sched_info
->print_insn
) (*insn_ptr
, 0));
2758 if (sched_verbose
>= 4)
2759 fprintf (sched_dump
, ";;\t\tChosen insn : %s\n",
2760 (*current_sched_info
->print_insn
)
2761 (ready_element (ready
, index
), 0));
2763 *insn_ptr
= ready_remove (ready
, index
);
2769 /* Use forward list scheduling to rearrange insns of block pointed to by
2770 TARGET_BB, possibly bringing insns from subsequent blocks in the same
2774 schedule_block (basic_block
*target_bb
)
2776 int i
, first_cycle_insn_p
;
2778 state_t temp_state
= NULL
; /* It is used for multipass scheduling. */
2779 int sort_p
, advance
, start_clock_var
;
2781 /* Head/tail info for this block. */
2782 rtx prev_head
= current_sched_info
->prev_head
;
2783 rtx next_tail
= current_sched_info
->next_tail
;
2784 rtx head
= NEXT_INSN (prev_head
);
2785 rtx tail
= PREV_INSN (next_tail
);
2787 /* We used to have code to avoid getting parameters moved from hard
2788 argument registers into pseudos.
2790 However, it was removed when it proved to be of marginal benefit
2791 and caused problems because schedule_block and compute_forward_dependences
2792 had different notions of what the "head" insn was. */
2794 gcc_assert (head
!= tail
|| INSN_P (head
));
2796 haifa_recovery_bb_recently_added_p
= false;
2800 dump_new_block_header (0, *target_bb
, head
, tail
);
2802 state_reset (curr_state
);
2804 /* Clear the ready list. */
2805 ready
.first
= ready
.veclen
- 1;
2809 /* It is used for first cycle multipass scheduling. */
2810 temp_state
= alloca (dfa_state_size
);
2812 if (targetm
.sched
.init
)
2813 targetm
.sched
.init (sched_dump
, sched_verbose
, ready
.veclen
);
2815 /* We start inserting insns after PREV_HEAD. */
2816 last_scheduled_insn
= prev_head
;
2818 gcc_assert ((NOTE_P (last_scheduled_insn
)
2819 || BOUNDARY_DEBUG_INSN_P (last_scheduled_insn
))
2820 && BLOCK_FOR_INSN (last_scheduled_insn
) == *target_bb
);
2822 /* Initialize INSN_QUEUE. Q_SIZE is the total number of insns in the
2827 insn_queue
= XALLOCAVEC (rtx
, max_insn_queue_index
+ 1);
2828 memset (insn_queue
, 0, (max_insn_queue_index
+ 1) * sizeof (rtx
));
2830 /* Start just before the beginning of time. */
2833 /* We need queue and ready lists and clock_var be initialized
2834 in try_ready () (which is called through init_ready_list ()). */
2835 (*current_sched_info
->init_ready_list
) ();
2837 /* The algorithm is O(n^2) in the number of ready insns at any given
2838 time in the worst case. Before reload we are more likely to have
2839 big lists so truncate them to a reasonable size. */
2840 if (!reload_completed
2841 && ready
.n_ready
- ready
.n_debug
> MAX_SCHED_READY_INSNS
)
2843 ready_sort (&ready
);
2845 /* Find first free-standing insn past MAX_SCHED_READY_INSNS.
2846 If there are debug insns, we know they're first. */
2847 for (i
= MAX_SCHED_READY_INSNS
+ ready
.n_debug
; i
< ready
.n_ready
; i
++)
2848 if (!SCHED_GROUP_P (ready_element (&ready
, i
)))
2851 if (sched_verbose
>= 2)
2853 fprintf (sched_dump
,
2854 ";;\t\tReady list on entry: %d insns\n", ready
.n_ready
);
2855 fprintf (sched_dump
,
2856 ";;\t\t before reload => truncated to %d insns\n", i
);
2859 /* Delay all insns past it for 1 cycle. If debug counter is
2860 activated make an exception for the insn right after
2861 last_scheduled_insn. */
2865 if (dbg_cnt (sched_insn
) == false)
2866 skip_insn
= next_nonnote_insn (last_scheduled_insn
);
2868 skip_insn
= NULL_RTX
;
2870 while (i
< ready
.n_ready
)
2874 insn
= ready_remove (&ready
, i
);
2876 if (insn
!= skip_insn
)
2877 queue_insn (insn
, 1);
2882 /* Now we can restore basic block notes and maintain precise cfg. */
2883 restore_bb_notes (*target_bb
);
2885 last_clock_var
= -1;
2890 /* Loop until all the insns in BB are scheduled. */
2891 while ((*current_sched_info
->schedule_more_p
) ())
2895 start_clock_var
= clock_var
;
2899 advance_one_cycle ();
2901 /* Add to the ready list all pending insns that can be issued now.
2902 If there are no ready insns, increment clock until one
2903 is ready and add all pending insns at that point to the ready
2905 queue_to_ready (&ready
);
2907 gcc_assert (ready
.n_ready
);
2909 if (sched_verbose
>= 2)
2911 fprintf (sched_dump
, ";;\t\tReady list after queue_to_ready: ");
2912 debug_ready_list (&ready
);
2914 advance
-= clock_var
- start_clock_var
;
2916 while (advance
> 0);
2920 /* Sort the ready list based on priority. */
2921 ready_sort (&ready
);
2923 if (sched_verbose
>= 2)
2925 fprintf (sched_dump
, ";;\t\tReady list after ready_sort: ");
2926 debug_ready_list (&ready
);
2930 /* We don't want md sched reorder to even see debug isns, so put
2931 them out right away. */
2932 if (ready
.n_ready
&& DEBUG_INSN_P (ready_element (&ready
, 0)))
2934 if (control_flow_insn_p (last_scheduled_insn
))
2936 *target_bb
= current_sched_info
->advance_target_bb
2943 x
= next_real_insn (last_scheduled_insn
);
2945 dump_new_block_header (1, *target_bb
, x
, tail
);
2948 last_scheduled_insn
= bb_note (*target_bb
);
2951 while (ready
.n_ready
&& DEBUG_INSN_P (ready_element (&ready
, 0)))
2953 rtx insn
= ready_remove_first (&ready
);
2954 gcc_assert (DEBUG_INSN_P (insn
));
2955 (*current_sched_info
->begin_schedule_ready
) (insn
,
2956 last_scheduled_insn
);
2957 move_insn (insn
, last_scheduled_insn
,
2958 current_sched_info
->next_tail
);
2959 last_scheduled_insn
= insn
;
2960 advance
= schedule_insn (insn
);
2961 gcc_assert (advance
== 0);
2962 if (ready
.n_ready
> 0)
2963 ready_sort (&ready
);
2970 /* Allow the target to reorder the list, typically for
2971 better instruction bundling. */
2972 if (sort_p
&& targetm
.sched
.reorder
2973 && (ready
.n_ready
== 0
2974 || !SCHED_GROUP_P (ready_element (&ready
, 0))))
2976 targetm
.sched
.reorder (sched_dump
, sched_verbose
,
2977 ready_lastpos (&ready
),
2978 &ready
.n_ready
, clock_var
);
2980 can_issue_more
= issue_rate
;
2982 first_cycle_insn_p
= 1;
2983 cycle_issued_insns
= 0;
2990 if (sched_verbose
>= 2)
2992 fprintf (sched_dump
, ";;\tReady list (t = %3d): ",
2994 debug_ready_list (&ready
);
2995 if (sched_pressure_p
)
2996 print_curr_reg_pressure ();
2999 if (ready
.n_ready
== 0
3001 && reload_completed
)
3003 /* Allow scheduling insns directly from the queue in case
3004 there's nothing better to do (ready list is empty) but
3005 there are still vacant dispatch slots in the current cycle. */
3006 if (sched_verbose
>= 6)
3007 fprintf (sched_dump
,";;\t\tSecond chance\n");
3008 memcpy (temp_state
, curr_state
, dfa_state_size
);
3009 if (early_queue_to_ready (temp_state
, &ready
))
3010 ready_sort (&ready
);
3013 if (ready
.n_ready
== 0
3015 || state_dead_lock_p (curr_state
)
3016 || !(*current_sched_info
->schedule_more_p
) ())
3019 /* Select and remove the insn from the ready list. */
3025 res
= choose_ready (&ready
, &insn
);
3031 /* Restart choose_ready (). */
3034 gcc_assert (insn
!= NULL_RTX
);
3037 insn
= ready_remove_first (&ready
);
3039 if (sched_pressure_p
&& INSN_TICK (insn
) > clock_var
)
3041 ready_add (&ready
, insn
, true);
3046 if (targetm
.sched
.dfa_new_cycle
3047 && targetm
.sched
.dfa_new_cycle (sched_dump
, sched_verbose
,
3048 insn
, last_clock_var
,
3049 clock_var
, &sort_p
))
3050 /* SORT_P is used by the target to override sorting
3051 of the ready list. This is needed when the target
3052 has modified its internal structures expecting that
3053 the insn will be issued next. As we need the insn
3054 to have the highest priority (so it will be returned by
3055 the ready_remove_first call above), we invoke
3056 ready_add (&ready, insn, true).
3057 But, still, there is one issue: INSN can be later
3058 discarded by scheduler's front end through
3059 current_sched_info->can_schedule_ready_p, hence, won't
3062 ready_add (&ready
, insn
, true);
3067 memcpy (temp_state
, curr_state
, dfa_state_size
);
3068 if (recog_memoized (insn
) < 0)
3070 asm_p
= (GET_CODE (PATTERN (insn
)) == ASM_INPUT
3071 || asm_noperands (PATTERN (insn
)) >= 0);
3072 if (!first_cycle_insn_p
&& asm_p
)
3073 /* This is asm insn which is tried to be issued on the
3074 cycle not first. Issue it on the next cycle. */
3077 /* A USE insn, or something else we don't need to
3078 understand. We can't pass these directly to
3079 state_transition because it will trigger a
3080 fatal error for unrecognizable insns. */
3083 else if (sched_pressure_p
)
3087 cost
= state_transition (temp_state
, insn
);
3096 queue_insn (insn
, cost
);
3097 if (SCHED_GROUP_P (insn
))
3106 if (current_sched_info
->can_schedule_ready_p
3107 && ! (*current_sched_info
->can_schedule_ready_p
) (insn
))
3108 /* We normally get here only if we don't want to move
3109 insn from the split block. */
3111 TODO_SPEC (insn
) = (TODO_SPEC (insn
) & ~SPECULATIVE
) | HARD_DEP
;
3115 /* DECISION is made. */
3117 if (TODO_SPEC (insn
) & SPECULATIVE
)
3118 generate_recovery_code (insn
);
3120 if (control_flow_insn_p (last_scheduled_insn
)
3121 /* This is used to switch basic blocks by request
3122 from scheduler front-end (actually, sched-ebb.c only).
3123 This is used to process blocks with single fallthru
3124 edge. If succeeding block has jump, it [jump] will try
3125 move at the end of current bb, thus corrupting CFG. */
3126 || current_sched_info
->advance_target_bb (*target_bb
, insn
))
3128 *target_bb
= current_sched_info
->advance_target_bb
3135 x
= next_real_insn (last_scheduled_insn
);
3137 dump_new_block_header (1, *target_bb
, x
, tail
);
3140 last_scheduled_insn
= bb_note (*target_bb
);
3143 /* Update counters, etc in the scheduler's front end. */
3144 (*current_sched_info
->begin_schedule_ready
) (insn
,
3145 last_scheduled_insn
);
3147 move_insn (insn
, last_scheduled_insn
, current_sched_info
->next_tail
);
3149 if (targetm
.sched
.dispatch (NULL_RTX
, IS_DISPATCH_ON
))
3150 targetm
.sched
.dispatch_do (insn
, ADD_TO_DISPATCH_WINDOW
);
3152 reemit_notes (insn
);
3153 last_scheduled_insn
= insn
;
3155 if (memcmp (curr_state
, temp_state
, dfa_state_size
) != 0)
3157 cycle_issued_insns
++;
3158 memcpy (curr_state
, temp_state
, dfa_state_size
);
3161 if (targetm
.sched
.variable_issue
)
3163 targetm
.sched
.variable_issue (sched_dump
, sched_verbose
,
3164 insn
, can_issue_more
);
3165 /* A naked CLOBBER or USE generates no instruction, so do
3166 not count them against the issue rate. */
3167 else if (GET_CODE (PATTERN (insn
)) != USE
3168 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
3170 advance
= schedule_insn (insn
);
3172 /* After issuing an asm insn we should start a new cycle. */
3173 if (advance
== 0 && asm_p
)
3178 first_cycle_insn_p
= 0;
3180 /* Sort the ready list based on priority. This must be
3181 redone here, as schedule_insn may have readied additional
3182 insns that will not be sorted correctly. */
3183 if (ready
.n_ready
> 0)
3184 ready_sort (&ready
);
3186 /* Quickly go through debug insns such that md sched
3187 reorder2 doesn't have to deal with debug insns. */
3188 if (ready
.n_ready
&& DEBUG_INSN_P (ready_element (&ready
, 0))
3189 && (*current_sched_info
->schedule_more_p
) ())
3191 if (control_flow_insn_p (last_scheduled_insn
))
3193 *target_bb
= current_sched_info
->advance_target_bb
3200 x
= next_real_insn (last_scheduled_insn
);
3202 dump_new_block_header (1, *target_bb
, x
, tail
);
3205 last_scheduled_insn
= bb_note (*target_bb
);
3208 while (ready
.n_ready
&& DEBUG_INSN_P (ready_element (&ready
, 0)))
3210 insn
= ready_remove_first (&ready
);
3211 gcc_assert (DEBUG_INSN_P (insn
));
3212 (*current_sched_info
->begin_schedule_ready
)
3213 (insn
, last_scheduled_insn
);
3214 move_insn (insn
, last_scheduled_insn
,
3215 current_sched_info
->next_tail
);
3216 advance
= schedule_insn (insn
);
3217 last_scheduled_insn
= insn
;
3218 gcc_assert (advance
== 0);
3219 if (ready
.n_ready
> 0)
3220 ready_sort (&ready
);
3224 if (targetm
.sched
.reorder2
3225 && (ready
.n_ready
== 0
3226 || !SCHED_GROUP_P (ready_element (&ready
, 0))))
3229 targetm
.sched
.reorder2 (sched_dump
, sched_verbose
,
3231 ? ready_lastpos (&ready
) : NULL
,
3232 &ready
.n_ready
, clock_var
);
3240 fprintf (sched_dump
, ";;\tReady list (final): ");
3241 debug_ready_list (&ready
);
3244 if (current_sched_info
->queue_must_finish_empty
)
3245 /* Sanity check -- queue must be empty now. Meaningless if region has
3247 gcc_assert (!q_size
&& !ready
.n_ready
&& !ready
.n_debug
);
3250 /* We must maintain QUEUE_INDEX between blocks in region. */
3251 for (i
= ready
.n_ready
- 1; i
>= 0; i
--)
3255 x
= ready_element (&ready
, i
);
3256 QUEUE_INDEX (x
) = QUEUE_NOWHERE
;
3257 TODO_SPEC (x
) = (TODO_SPEC (x
) & ~SPECULATIVE
) | HARD_DEP
;
3261 for (i
= 0; i
<= max_insn_queue_index
; i
++)
3264 for (link
= insn_queue
[i
]; link
; link
= XEXP (link
, 1))
3269 QUEUE_INDEX (x
) = QUEUE_NOWHERE
;
3270 TODO_SPEC (x
) = (TODO_SPEC (x
) & ~SPECULATIVE
) | HARD_DEP
;
3272 free_INSN_LIST_list (&insn_queue
[i
]);
3277 fprintf (sched_dump
, ";; total time = %d\n", clock_var
);
3279 if (!current_sched_info
->queue_must_finish_empty
3280 || haifa_recovery_bb_recently_added_p
)
3282 /* INSN_TICK (minimum clock tick at which the insn becomes
3283 ready) may be not correct for the insn in the subsequent
3284 blocks of the region. We should use a correct value of
3285 `clock_var' or modify INSN_TICK. It is better to keep
3286 clock_var value equal to 0 at the start of a basic block.
3287 Therefore we modify INSN_TICK here. */
3288 fix_inter_tick (NEXT_INSN (prev_head
), last_scheduled_insn
);
3291 if (targetm
.sched
.finish
)
3293 targetm
.sched
.finish (sched_dump
, sched_verbose
);
3294 /* Target might have added some instructions to the scheduled block
3295 in its md_finish () hook. These new insns don't have any data
3296 initialized and to identify them we extend h_i_d so that they'll
3298 sched_init_luids (NULL
, NULL
, NULL
, NULL
);
3302 fprintf (sched_dump
, ";; new head = %d\n;; new tail = %d\n\n",
3303 INSN_UID (head
), INSN_UID (tail
));
3305 /* Update head/tail boundaries. */
3306 head
= NEXT_INSN (prev_head
);
3307 tail
= last_scheduled_insn
;
3309 head
= restore_other_notes (head
, NULL
);
3311 current_sched_info
->head
= head
;
3312 current_sched_info
->tail
= tail
;
3315 /* Set_priorities: compute priority of each insn in the block. */
3318 set_priorities (rtx head
, rtx tail
)
3322 int sched_max_insns_priority
=
3323 current_sched_info
->sched_max_insns_priority
;
3326 if (head
== tail
&& (! INSN_P (head
) || BOUNDARY_DEBUG_INSN_P (head
)))
3331 prev_head
= PREV_INSN (head
);
3332 for (insn
= tail
; insn
!= prev_head
; insn
= PREV_INSN (insn
))
3338 (void) priority (insn
);
3340 gcc_assert (INSN_PRIORITY_KNOWN (insn
));
3342 sched_max_insns_priority
= MAX (sched_max_insns_priority
,
3343 INSN_PRIORITY (insn
));
3346 current_sched_info
->sched_max_insns_priority
= sched_max_insns_priority
;
3351 /* Set dump and sched_verbose for the desired debugging output. If no
3352 dump-file was specified, but -fsched-verbose=N (any N), print to stderr.
3353 For -fsched-verbose=N, N>=10, print everything to stderr. */
3355 setup_sched_dump (void)
3357 sched_verbose
= sched_verbose_param
;
3358 if (sched_verbose_param
== 0 && dump_file
)
3360 sched_dump
= ((sched_verbose_param
>= 10 || !dump_file
)
3361 ? stderr
: dump_file
);
3364 /* Initialize some global state for the scheduler. This function works
3365 with the common data shared between all the schedulers. It is called
3366 from the scheduler specific initialization routine. */
3371 /* Disable speculative loads in their presence if cc0 defined. */
3373 flag_schedule_speculative_load
= 0;
3376 if (targetm
.sched
.dispatch (NULL_RTX
, IS_DISPATCH_ON
))
3377 targetm
.sched
.dispatch_do (NULL_RTX
, DISPATCH_INIT
);
3379 sched_pressure_p
= (flag_sched_pressure
&& ! reload_completed
3380 && common_sched_info
->sched_pass_id
== SCHED_RGN_PASS
);
3382 if (sched_pressure_p
)
3383 ira_setup_eliminable_regset ();
3385 /* Initialize SPEC_INFO. */
3386 if (targetm
.sched
.set_sched_flags
)
3388 spec_info
= &spec_info_var
;
3389 targetm
.sched
.set_sched_flags (spec_info
);
3391 if (spec_info
->mask
!= 0)
3393 spec_info
->data_weakness_cutoff
=
3394 (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF
) * MAX_DEP_WEAK
) / 100;
3395 spec_info
->control_weakness_cutoff
=
3396 (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF
)
3397 * REG_BR_PROB_BASE
) / 100;
3400 /* So we won't read anything accidentally. */
3405 /* So we won't read anything accidentally. */
3408 /* Initialize issue_rate. */
3409 if (targetm
.sched
.issue_rate
)
3410 issue_rate
= targetm
.sched
.issue_rate ();
3414 if (cached_issue_rate
!= issue_rate
)
3416 cached_issue_rate
= issue_rate
;
3417 /* To invalidate max_lookahead_tries: */
3418 cached_first_cycle_multipass_dfa_lookahead
= 0;
3421 if (targetm
.sched
.first_cycle_multipass_dfa_lookahead
)
3422 dfa_lookahead
= targetm
.sched
.first_cycle_multipass_dfa_lookahead ();
3426 if (targetm
.sched
.init_dfa_pre_cycle_insn
)
3427 targetm
.sched
.init_dfa_pre_cycle_insn ();
3429 if (targetm
.sched
.init_dfa_post_cycle_insn
)
3430 targetm
.sched
.init_dfa_post_cycle_insn ();
3433 dfa_state_size
= state_size ();
3435 init_alias_analysis ();
3437 df_set_flags (DF_LR_RUN_DCE
);
3438 df_note_add_problem ();
3440 /* More problems needed for interloop dep calculation in SMS. */
3441 if (common_sched_info
->sched_pass_id
== SCHED_SMS_PASS
)
3443 df_rd_add_problem ();
3444 df_chain_add_problem (DF_DU_CHAIN
+ DF_UD_CHAIN
);
3449 /* Do not run DCE after reload, as this can kill nops inserted
3451 if (reload_completed
)
3452 df_clear_flags (DF_LR_RUN_DCE
);
3454 regstat_compute_calls_crossed ();
3456 if (targetm
.sched
.init_global
)
3457 targetm
.sched
.init_global (sched_dump
, sched_verbose
, get_max_uid () + 1);
3459 if (sched_pressure_p
)
3461 int i
, max_regno
= max_reg_num ();
3463 ira_set_pseudo_classes (sched_verbose
? sched_dump
: NULL
);
3464 sched_regno_cover_class
3465 = (enum reg_class
*) xmalloc (max_regno
* sizeof (enum reg_class
));
3466 for (i
= 0; i
< max_regno
; i
++)
3467 sched_regno_cover_class
[i
]
3468 = (i
< FIRST_PSEUDO_REGISTER
3469 ? ira_class_translate
[REGNO_REG_CLASS (i
)]
3470 : reg_cover_class (i
));
3471 curr_reg_live
= BITMAP_ALLOC (NULL
);
3472 saved_reg_live
= BITMAP_ALLOC (NULL
);
3473 region_ref_regs
= BITMAP_ALLOC (NULL
);
3476 curr_state
= xmalloc (dfa_state_size
);
3479 static void haifa_init_only_bb (basic_block
, basic_block
);
3481 /* Initialize data structures specific to the Haifa scheduler. */
3483 haifa_sched_init (void)
3485 setup_sched_dump ();
3488 if (spec_info
!= NULL
)
3490 sched_deps_info
->use_deps_list
= 1;
3491 sched_deps_info
->generate_spec_deps
= 1;
3494 /* Initialize luids, dependency caches, target and h_i_d for the
3497 bb_vec_t bbs
= VEC_alloc (basic_block
, heap
, n_basic_blocks
);
3503 VEC_quick_push (basic_block
, bbs
, bb
);
3504 sched_init_luids (bbs
, NULL
, NULL
, NULL
);
3505 sched_deps_init (true);
3506 sched_extend_target ();
3507 haifa_init_h_i_d (bbs
, NULL
, NULL
, NULL
);
3509 VEC_free (basic_block
, heap
, bbs
);
3512 sched_init_only_bb
= haifa_init_only_bb
;
3513 sched_split_block
= sched_split_block_1
;
3514 sched_create_empty_bb
= sched_create_empty_bb_1
;
3515 haifa_recovery_bb_ever_added_p
= false;
3517 #ifdef ENABLE_CHECKING
3518 /* This is used preferably for finding bugs in check_cfg () itself.
3519 We must call sched_bbs_init () before check_cfg () because check_cfg ()
3520 assumes that the last insn in the last bb has a non-null successor. */
3524 nr_begin_data
= nr_begin_control
= nr_be_in_data
= nr_be_in_control
= 0;
3525 before_recovery
= 0;
3529 /* Finish work with the data specific to the Haifa scheduler. */
3531 haifa_sched_finish (void)
3533 sched_create_empty_bb
= NULL
;
3534 sched_split_block
= NULL
;
3535 sched_init_only_bb
= NULL
;
3537 if (spec_info
&& spec_info
->dump
)
3539 char c
= reload_completed
? 'a' : 'b';
3541 fprintf (spec_info
->dump
,
3542 ";; %s:\n", current_function_name ());
3544 fprintf (spec_info
->dump
,
3545 ";; Procedure %cr-begin-data-spec motions == %d\n",
3547 fprintf (spec_info
->dump
,
3548 ";; Procedure %cr-be-in-data-spec motions == %d\n",
3550 fprintf (spec_info
->dump
,
3551 ";; Procedure %cr-begin-control-spec motions == %d\n",
3552 c
, nr_begin_control
);
3553 fprintf (spec_info
->dump
,
3554 ";; Procedure %cr-be-in-control-spec motions == %d\n",
3555 c
, nr_be_in_control
);
3558 /* Finalize h_i_d, dependency caches, and luids for the whole
3559 function. Target will be finalized in md_global_finish (). */
3560 sched_deps_finish ();
3561 sched_finish_luids ();
3562 current_sched_info
= NULL
;
3566 /* Free global data used during insn scheduling. This function works with
3567 the common data shared between the schedulers. */
3572 haifa_finish_h_i_d ();
3573 if (sched_pressure_p
)
3575 free (sched_regno_cover_class
);
3576 BITMAP_FREE (region_ref_regs
);
3577 BITMAP_FREE (saved_reg_live
);
3578 BITMAP_FREE (curr_reg_live
);
3582 if (targetm
.sched
.finish_global
)
3583 targetm
.sched
.finish_global (sched_dump
, sched_verbose
);
3585 end_alias_analysis ();
3587 regstat_free_calls_crossed ();
3591 #ifdef ENABLE_CHECKING
3592 /* After reload ia64 backend clobbers CFG, so can't check anything. */
3593 if (!reload_completed
)
3598 /* Fix INSN_TICKs of the instructions in the current block as well as
3599 INSN_TICKs of their dependents.
3600 HEAD and TAIL are the begin and the end of the current scheduled block. */
3602 fix_inter_tick (rtx head
, rtx tail
)
3604 /* Set of instructions with corrected INSN_TICK. */
3605 bitmap_head processed
;
3606 /* ??? It is doubtful if we should assume that cycle advance happens on
3607 basic block boundaries. Basically insns that are unconditionally ready
3608 on the start of the block are more preferable then those which have
3609 a one cycle dependency over insn from the previous block. */
3610 int next_clock
= clock_var
+ 1;
3612 bitmap_initialize (&processed
, 0);
3614 /* Iterates over scheduled instructions and fix their INSN_TICKs and
3615 INSN_TICKs of dependent instructions, so that INSN_TICKs are consistent
3616 across different blocks. */
3617 for (tail
= NEXT_INSN (tail
); head
!= tail
; head
= NEXT_INSN (head
))
3622 sd_iterator_def sd_it
;
3625 tick
= INSN_TICK (head
);
3626 gcc_assert (tick
>= MIN_TICK
);
3628 /* Fix INSN_TICK of instruction from just scheduled block. */
3629 if (bitmap_set_bit (&processed
, INSN_LUID (head
)))
3633 if (tick
< MIN_TICK
)
3636 INSN_TICK (head
) = tick
;
3639 FOR_EACH_DEP (head
, SD_LIST_RES_FORW
, sd_it
, dep
)
3643 next
= DEP_CON (dep
);
3644 tick
= INSN_TICK (next
);
3646 if (tick
!= INVALID_TICK
3647 /* If NEXT has its INSN_TICK calculated, fix it.
3648 If not - it will be properly calculated from
3649 scratch later in fix_tick_ready. */
3650 && bitmap_set_bit (&processed
, INSN_LUID (next
)))
3654 if (tick
< MIN_TICK
)
3657 if (tick
> INTER_TICK (next
))
3658 INTER_TICK (next
) = tick
;
3660 tick
= INTER_TICK (next
);
3662 INSN_TICK (next
) = tick
;
3667 bitmap_clear (&processed
);
3670 static int haifa_speculate_insn (rtx
, ds_t
, rtx
*);
3672 /* Check if NEXT is ready to be added to the ready or queue list.
3673 If "yes", add it to the proper list.
3675 -1 - is not ready yet,
3676 0 - added to the ready list,
3677 0 < N - queued for N cycles. */
3679 try_ready (rtx next
)
3683 ts
= &TODO_SPEC (next
);
3686 gcc_assert (!(old_ts
& ~(SPECULATIVE
| HARD_DEP
))
3687 && ((old_ts
& HARD_DEP
)
3688 || (old_ts
& SPECULATIVE
)));
3690 if (sd_lists_empty_p (next
, SD_LIST_BACK
))
3691 /* NEXT has all its dependencies resolved. */
3693 /* Remove HARD_DEP bit from NEXT's status. */
3696 if (current_sched_info
->flags
& DO_SPECULATION
)
3697 /* Remove all speculative bits from NEXT's status. */
3698 *ts
&= ~SPECULATIVE
;
3702 /* One of the NEXT's dependencies has been resolved.
3703 Recalculate NEXT's status. */
3705 *ts
&= ~SPECULATIVE
& ~HARD_DEP
;
3707 if (sd_lists_empty_p (next
, SD_LIST_HARD_BACK
))
3708 /* Now we've got NEXT with speculative deps only.
3709 1. Look at the deps to see what we have to do.
3710 2. Check if we can do 'todo'. */
3712 sd_iterator_def sd_it
;
3714 bool first_p
= true;
3716 FOR_EACH_DEP (next
, SD_LIST_BACK
, sd_it
, dep
)
3718 ds_t ds
= DEP_STATUS (dep
) & SPECULATIVE
;
3720 if (DEBUG_INSN_P (DEP_PRO (dep
))
3721 && !DEBUG_INSN_P (next
))
3731 *ts
= ds_merge (*ts
, ds
);
3734 if (ds_weak (*ts
) < spec_info
->data_weakness_cutoff
)
3735 /* Too few points. */
3736 *ts
= (*ts
& ~SPECULATIVE
) | HARD_DEP
;
3743 gcc_assert (*ts
== old_ts
3744 && QUEUE_INDEX (next
) == QUEUE_NOWHERE
);
3745 else if (current_sched_info
->new_ready
)
3746 *ts
= current_sched_info
->new_ready (next
, *ts
);
3748 /* * if !(old_ts & SPECULATIVE) (e.g. HARD_DEP or 0), then insn might
3749 have its original pattern or changed (speculative) one. This is due
3750 to changing ebb in region scheduling.
3751 * But if (old_ts & SPECULATIVE), then we are pretty sure that insn
3752 has speculative pattern.
3754 We can't assert (!(*ts & HARD_DEP) || *ts == old_ts) here because
3755 control-speculative NEXT could have been discarded by sched-rgn.c
3756 (the same case as when discarded by can_schedule_ready_p ()). */
3758 if ((*ts
& SPECULATIVE
)
3759 /* If (old_ts == *ts), then (old_ts & SPECULATIVE) and we don't
3760 need to change anything. */
3766 gcc_assert ((*ts
& SPECULATIVE
) && !(*ts
& ~SPECULATIVE
));
3768 res
= haifa_speculate_insn (next
, *ts
, &new_pat
);
3773 /* It would be nice to change DEP_STATUS of all dependences,
3774 which have ((DEP_STATUS & SPECULATIVE) == *ts) to HARD_DEP,
3775 so we won't reanalyze anything. */
3776 *ts
= (*ts
& ~SPECULATIVE
) | HARD_DEP
;
3780 /* We follow the rule, that every speculative insn
3781 has non-null ORIG_PAT. */
3782 if (!ORIG_PAT (next
))
3783 ORIG_PAT (next
) = PATTERN (next
);
3787 if (!ORIG_PAT (next
))
3788 /* If we gonna to overwrite the original pattern of insn,
3790 ORIG_PAT (next
) = PATTERN (next
);
3792 haifa_change_pattern (next
, new_pat
);
3800 /* We need to restore pattern only if (*ts == 0), because otherwise it is
3801 either correct (*ts & SPECULATIVE),
3802 or we simply don't care (*ts & HARD_DEP). */
3804 gcc_assert (!ORIG_PAT (next
)
3805 || !IS_SPECULATION_BRANCHY_CHECK_P (next
));
3809 /* We can't assert (QUEUE_INDEX (next) == QUEUE_NOWHERE) here because
3810 control-speculative NEXT could have been discarded by sched-rgn.c
3811 (the same case as when discarded by can_schedule_ready_p ()). */
3812 /*gcc_assert (QUEUE_INDEX (next) == QUEUE_NOWHERE);*/
3814 change_queue_index (next
, QUEUE_NOWHERE
);
3817 else if (!(*ts
& BEGIN_SPEC
) && ORIG_PAT (next
) && !IS_SPECULATION_CHECK_P (next
))
3818 /* We should change pattern of every previously speculative
3819 instruction - and we determine if NEXT was speculative by using
3820 ORIG_PAT field. Except one case - speculation checks have ORIG_PAT
3821 pat too, so skip them. */
3823 haifa_change_pattern (next
, ORIG_PAT (next
));
3824 ORIG_PAT (next
) = 0;
3827 if (sched_verbose
>= 2)
3829 int s
= TODO_SPEC (next
);
3831 fprintf (sched_dump
, ";;\t\tdependencies resolved: insn %s",
3832 (*current_sched_info
->print_insn
) (next
, 0));
3834 if (spec_info
&& spec_info
->dump
)
3837 fprintf (spec_info
->dump
, "; data-spec;");
3838 if (s
& BEGIN_CONTROL
)
3839 fprintf (spec_info
->dump
, "; control-spec;");
3840 if (s
& BE_IN_CONTROL
)
3841 fprintf (spec_info
->dump
, "; in-control-spec;");
3844 fprintf (sched_dump
, "\n");
3847 adjust_priority (next
);
3849 return fix_tick_ready (next
);
3852 /* Calculate INSN_TICK of NEXT and add it to either ready or queue list. */
3854 fix_tick_ready (rtx next
)
3858 if (!sd_lists_empty_p (next
, SD_LIST_RES_BACK
))
3861 sd_iterator_def sd_it
;
3864 tick
= INSN_TICK (next
);
3865 /* if tick is not equal to INVALID_TICK, then update
3866 INSN_TICK of NEXT with the most recent resolved dependence
3867 cost. Otherwise, recalculate from scratch. */
3868 full_p
= (tick
== INVALID_TICK
);
3870 FOR_EACH_DEP (next
, SD_LIST_RES_BACK
, sd_it
, dep
)
3872 rtx pro
= DEP_PRO (dep
);
3875 gcc_assert (INSN_TICK (pro
) >= MIN_TICK
);
3877 tick1
= INSN_TICK (pro
) + dep_cost (dep
);
3888 INSN_TICK (next
) = tick
;
3890 delay
= tick
- clock_var
;
3891 if (delay
<= 0 || sched_pressure_p
)
3892 delay
= QUEUE_READY
;
3894 change_queue_index (next
, delay
);
3899 /* Move NEXT to the proper queue list with (DELAY >= 1),
3900 or add it to the ready list (DELAY == QUEUE_READY),
3901 or remove it from ready and queue lists at all (DELAY == QUEUE_NOWHERE). */
3903 change_queue_index (rtx next
, int delay
)
3905 int i
= QUEUE_INDEX (next
);
3907 gcc_assert (QUEUE_NOWHERE
<= delay
&& delay
<= max_insn_queue_index
3909 gcc_assert (i
!= QUEUE_SCHEDULED
);
3911 if ((delay
> 0 && NEXT_Q_AFTER (q_ptr
, delay
) == i
)
3912 || (delay
< 0 && delay
== i
))
3913 /* We have nothing to do. */
3916 /* Remove NEXT from wherever it is now. */
3917 if (i
== QUEUE_READY
)
3918 ready_remove_insn (next
);
3920 queue_remove (next
);
3922 /* Add it to the proper place. */
3923 if (delay
== QUEUE_READY
)
3924 ready_add (readyp
, next
, false);
3925 else if (delay
>= 1)
3926 queue_insn (next
, delay
);
3928 if (sched_verbose
>= 2)
3930 fprintf (sched_dump
, ";;\t\ttick updated: insn %s",
3931 (*current_sched_info
->print_insn
) (next
, 0));
3933 if (delay
== QUEUE_READY
)
3934 fprintf (sched_dump
, " into ready\n");
3935 else if (delay
>= 1)
3936 fprintf (sched_dump
, " into queue with cost=%d\n", delay
);
3938 fprintf (sched_dump
, " removed from ready or queue lists\n");
3942 static int sched_ready_n_insns
= -1;
3944 /* Initialize per region data structures. */
3946 sched_extend_ready_list (int new_sched_ready_n_insns
)
3950 if (sched_ready_n_insns
== -1)
3951 /* At the first call we need to initialize one more choice_stack
3955 sched_ready_n_insns
= 0;
3958 i
= sched_ready_n_insns
+ 1;
3960 ready
.veclen
= new_sched_ready_n_insns
+ issue_rate
;
3961 ready
.vec
= XRESIZEVEC (rtx
, ready
.vec
, ready
.veclen
);
3963 gcc_assert (new_sched_ready_n_insns
>= sched_ready_n_insns
);
3965 ready_try
= (char *) xrecalloc (ready_try
, new_sched_ready_n_insns
,
3966 sched_ready_n_insns
, sizeof (*ready_try
));
3968 /* We allocate +1 element to save initial state in the choice_stack[0]
3970 choice_stack
= XRESIZEVEC (struct choice_entry
, choice_stack
,
3971 new_sched_ready_n_insns
+ 1);
3973 for (; i
<= new_sched_ready_n_insns
; i
++)
3974 choice_stack
[i
].state
= xmalloc (dfa_state_size
);
3976 sched_ready_n_insns
= new_sched_ready_n_insns
;
3979 /* Free per region data structures. */
3981 sched_finish_ready_list (void)
3992 for (i
= 0; i
<= sched_ready_n_insns
; i
++)
3993 free (choice_stack
[i
].state
);
3994 free (choice_stack
);
3995 choice_stack
= NULL
;
3997 sched_ready_n_insns
= -1;
4001 haifa_luid_for_non_insn (rtx x
)
4003 gcc_assert (NOTE_P (x
) || LABEL_P (x
));
4008 /* Generates recovery code for INSN. */
4010 generate_recovery_code (rtx insn
)
4012 if (TODO_SPEC (insn
) & BEGIN_SPEC
)
4013 begin_speculative_block (insn
);
4015 /* Here we have insn with no dependencies to
4016 instructions other then CHECK_SPEC ones. */
4018 if (TODO_SPEC (insn
) & BE_IN_SPEC
)
4019 add_to_speculative_block (insn
);
4023 Tries to add speculative dependencies of type FS between instructions
4024 in deps_list L and TWIN. */
4026 process_insn_forw_deps_be_in_spec (rtx insn
, rtx twin
, ds_t fs
)
4028 sd_iterator_def sd_it
;
4031 FOR_EACH_DEP (insn
, SD_LIST_FORW
, sd_it
, dep
)
4036 consumer
= DEP_CON (dep
);
4038 ds
= DEP_STATUS (dep
);
4040 if (/* If we want to create speculative dep. */
4042 /* And we can do that because this is a true dep. */
4043 && (ds
& DEP_TYPES
) == DEP_TRUE
)
4045 gcc_assert (!(ds
& BE_IN_SPEC
));
4047 if (/* If this dep can be overcome with 'begin speculation'. */
4049 /* Then we have a choice: keep the dep 'begin speculative'
4050 or transform it into 'be in speculative'. */
4052 if (/* In try_ready we assert that if insn once became ready
4053 it can be removed from the ready (or queue) list only
4054 due to backend decision. Hence we can't let the
4055 probability of the speculative dep to decrease. */
4056 ds_weak (ds
) <= ds_weak (fs
))
4060 new_ds
= (ds
& ~BEGIN_SPEC
) | fs
;
4062 if (/* consumer can 'be in speculative'. */
4063 sched_insn_is_legitimate_for_speculation_p (consumer
,
4065 /* Transform it to be in speculative. */
4070 /* Mark the dep as 'be in speculative'. */
4075 dep_def _new_dep
, *new_dep
= &_new_dep
;
4077 init_dep_1 (new_dep
, twin
, consumer
, DEP_TYPE (dep
), ds
);
4078 sd_add_dep (new_dep
, false);
4083 /* Generates recovery code for BEGIN speculative INSN. */
4085 begin_speculative_block (rtx insn
)
4087 if (TODO_SPEC (insn
) & BEGIN_DATA
)
4089 if (TODO_SPEC (insn
) & BEGIN_CONTROL
)
4092 create_check_block_twin (insn
, false);
4094 TODO_SPEC (insn
) &= ~BEGIN_SPEC
;
4097 static void haifa_init_insn (rtx
);
4099 /* Generates recovery code for BE_IN speculative INSN. */
4101 add_to_speculative_block (rtx insn
)
4104 sd_iterator_def sd_it
;
4107 rtx_vec_t priorities_roots
;
4109 ts
= TODO_SPEC (insn
);
4110 gcc_assert (!(ts
& ~BE_IN_SPEC
));
4112 if (ts
& BE_IN_DATA
)
4114 if (ts
& BE_IN_CONTROL
)
4117 TODO_SPEC (insn
) &= ~BE_IN_SPEC
;
4118 gcc_assert (!TODO_SPEC (insn
));
4120 DONE_SPEC (insn
) |= ts
;
4122 /* First we convert all simple checks to branchy. */
4123 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
4124 sd_iterator_cond (&sd_it
, &dep
);)
4126 rtx check
= DEP_PRO (dep
);
4128 if (IS_SPECULATION_SIMPLE_CHECK_P (check
))
4130 create_check_block_twin (check
, true);
4132 /* Restart search. */
4133 sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
4136 /* Continue search. */
4137 sd_iterator_next (&sd_it
);
4140 priorities_roots
= NULL
;
4141 clear_priorities (insn
, &priorities_roots
);
4148 /* Get the first backward dependency of INSN. */
4149 sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
4150 if (!sd_iterator_cond (&sd_it
, &dep
))
4151 /* INSN has no backward dependencies left. */
4154 gcc_assert ((DEP_STATUS (dep
) & BEGIN_SPEC
) == 0
4155 && (DEP_STATUS (dep
) & BE_IN_SPEC
) != 0
4156 && (DEP_STATUS (dep
) & DEP_TYPES
) == DEP_TRUE
);
4158 check
= DEP_PRO (dep
);
4160 gcc_assert (!IS_SPECULATION_CHECK_P (check
) && !ORIG_PAT (check
)
4161 && QUEUE_INDEX (check
) == QUEUE_NOWHERE
);
4163 rec
= BLOCK_FOR_INSN (check
);
4165 twin
= emit_insn_before (copy_insn (PATTERN (insn
)), BB_END (rec
));
4166 haifa_init_insn (twin
);
4168 sd_copy_back_deps (twin
, insn
, true);
4170 if (sched_verbose
&& spec_info
->dump
)
4171 /* INSN_BB (insn) isn't determined for twin insns yet.
4172 So we can't use current_sched_info->print_insn. */
4173 fprintf (spec_info
->dump
, ";;\t\tGenerated twin insn : %d/rec%d\n",
4174 INSN_UID (twin
), rec
->index
);
4176 twins
= alloc_INSN_LIST (twin
, twins
);
4178 /* Add dependences between TWIN and all appropriate
4179 instructions from REC. */
4180 FOR_EACH_DEP (insn
, SD_LIST_SPEC_BACK
, sd_it
, dep
)
4182 rtx pro
= DEP_PRO (dep
);
4184 gcc_assert (DEP_TYPE (dep
) == REG_DEP_TRUE
);
4186 /* INSN might have dependencies from the instructions from
4187 several recovery blocks. At this iteration we process those
4188 producers that reside in REC. */
4189 if (BLOCK_FOR_INSN (pro
) == rec
)
4191 dep_def _new_dep
, *new_dep
= &_new_dep
;
4193 init_dep (new_dep
, pro
, twin
, REG_DEP_TRUE
);
4194 sd_add_dep (new_dep
, false);
4198 process_insn_forw_deps_be_in_spec (insn
, twin
, ts
);
4200 /* Remove all dependencies between INSN and insns in REC. */
4201 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
4202 sd_iterator_cond (&sd_it
, &dep
);)
4204 rtx pro
= DEP_PRO (dep
);
4206 if (BLOCK_FOR_INSN (pro
) == rec
)
4207 sd_delete_dep (sd_it
);
4209 sd_iterator_next (&sd_it
);
4213 /* We couldn't have added the dependencies between INSN and TWINS earlier
4214 because that would make TWINS appear in the INSN_BACK_DEPS (INSN). */
4219 twin
= XEXP (twins
, 0);
4222 dep_def _new_dep
, *new_dep
= &_new_dep
;
4224 init_dep (new_dep
, insn
, twin
, REG_DEP_OUTPUT
);
4225 sd_add_dep (new_dep
, false);
4228 twin
= XEXP (twins
, 1);
4229 free_INSN_LIST_node (twins
);
4233 calc_priorities (priorities_roots
);
4234 VEC_free (rtx
, heap
, priorities_roots
);
4237 /* Extends and fills with zeros (only the new part) array pointed to by P. */
4239 xrecalloc (void *p
, size_t new_nmemb
, size_t old_nmemb
, size_t size
)
4241 gcc_assert (new_nmemb
>= old_nmemb
);
4242 p
= XRESIZEVAR (void, p
, new_nmemb
* size
);
4243 memset (((char *) p
) + old_nmemb
* size
, 0, (new_nmemb
- old_nmemb
) * size
);
4248 Find fallthru edge from PRED. */
4250 find_fallthru_edge_from (basic_block pred
)
4255 succ
= pred
->next_bb
;
4256 gcc_assert (succ
->prev_bb
== pred
);
4258 if (EDGE_COUNT (pred
->succs
) <= EDGE_COUNT (succ
->preds
))
4260 e
= find_fallthru_edge (pred
->succs
);
4264 gcc_assert (e
->dest
== succ
);
4270 e
= find_fallthru_edge (succ
->preds
);
4274 gcc_assert (e
->src
== pred
);
4282 /* Extend per basic block data structures. */
4284 sched_extend_bb (void)
4288 /* The following is done to keep current_sched_info->next_tail non null. */
4289 insn
= BB_END (EXIT_BLOCK_PTR
->prev_bb
);
4290 if (NEXT_INSN (insn
) == 0
4293 /* Don't emit a NOTE if it would end up before a BARRIER. */
4294 && !BARRIER_P (NEXT_INSN (insn
))))
4296 rtx note
= emit_note_after (NOTE_INSN_DELETED
, insn
);
4297 /* Make insn appear outside BB. */
4298 set_block_for_insn (note
, NULL
);
4299 BB_END (EXIT_BLOCK_PTR
->prev_bb
) = insn
;
4303 /* Init per basic block data structures. */
4305 sched_init_bbs (void)
4310 /* Initialize BEFORE_RECOVERY variable. */
4312 init_before_recovery (basic_block
*before_recovery_ptr
)
4317 last
= EXIT_BLOCK_PTR
->prev_bb
;
4318 e
= find_fallthru_edge_from (last
);
4322 /* We create two basic blocks:
4323 1. Single instruction block is inserted right after E->SRC
4325 2. Empty block right before EXIT_BLOCK.
4326 Between these two blocks recovery blocks will be emitted. */
4328 basic_block single
, empty
;
4331 /* If the fallthrough edge to exit we've found is from the block we've
4332 created before, don't do anything more. */
4333 if (last
== after_recovery
)
4336 adding_bb_to_current_region_p
= false;
4338 single
= sched_create_empty_bb (last
);
4339 empty
= sched_create_empty_bb (single
);
4341 /* Add new blocks to the root loop. */
4342 if (current_loops
!= NULL
)
4344 add_bb_to_loop (single
, VEC_index (loop_p
, current_loops
->larray
, 0));
4345 add_bb_to_loop (empty
, VEC_index (loop_p
, current_loops
->larray
, 0));
4348 single
->count
= last
->count
;
4349 empty
->count
= last
->count
;
4350 single
->frequency
= last
->frequency
;
4351 empty
->frequency
= last
->frequency
;
4352 BB_COPY_PARTITION (single
, last
);
4353 BB_COPY_PARTITION (empty
, last
);
4355 redirect_edge_succ (e
, single
);
4356 make_single_succ_edge (single
, empty
, 0);
4357 make_single_succ_edge (empty
, EXIT_BLOCK_PTR
,
4358 EDGE_FALLTHRU
| EDGE_CAN_FALLTHRU
);
4360 label
= block_label (empty
);
4361 x
= emit_jump_insn_after (gen_jump (label
), BB_END (single
));
4362 JUMP_LABEL (x
) = label
;
4363 LABEL_NUSES (label
)++;
4364 haifa_init_insn (x
);
4366 emit_barrier_after (x
);
4368 sched_init_only_bb (empty
, NULL
);
4369 sched_init_only_bb (single
, NULL
);
4372 adding_bb_to_current_region_p
= true;
4373 before_recovery
= single
;
4374 after_recovery
= empty
;
4376 if (before_recovery_ptr
)
4377 *before_recovery_ptr
= before_recovery
;
4379 if (sched_verbose
>= 2 && spec_info
->dump
)
4380 fprintf (spec_info
->dump
,
4381 ";;\t\tFixed fallthru to EXIT : %d->>%d->%d->>EXIT\n",
4382 last
->index
, single
->index
, empty
->index
);
4385 before_recovery
= last
;
4388 /* Returns new recovery block. */
4390 sched_create_recovery_block (basic_block
*before_recovery_ptr
)
4396 haifa_recovery_bb_recently_added_p
= true;
4397 haifa_recovery_bb_ever_added_p
= true;
4399 init_before_recovery (before_recovery_ptr
);
4401 barrier
= get_last_bb_insn (before_recovery
);
4402 gcc_assert (BARRIER_P (barrier
));
4404 label
= emit_label_after (gen_label_rtx (), barrier
);
4406 rec
= create_basic_block (label
, label
, before_recovery
);
4408 /* A recovery block always ends with an unconditional jump. */
4409 emit_barrier_after (BB_END (rec
));
4411 if (BB_PARTITION (before_recovery
) != BB_UNPARTITIONED
)
4412 BB_SET_PARTITION (rec
, BB_COLD_PARTITION
);
4414 if (sched_verbose
&& spec_info
->dump
)
4415 fprintf (spec_info
->dump
, ";;\t\tGenerated recovery block rec%d\n",
4421 /* Create edges: FIRST_BB -> REC; FIRST_BB -> SECOND_BB; REC -> SECOND_BB
4422 and emit necessary jumps. */
4424 sched_create_recovery_edges (basic_block first_bb
, basic_block rec
,
4425 basic_block second_bb
)
4431 /* This is fixing of incoming edge. */
4432 /* ??? Which other flags should be specified? */
4433 if (BB_PARTITION (first_bb
) != BB_PARTITION (rec
))
4434 /* Partition type is the same, if it is "unpartitioned". */
4435 edge_flags
= EDGE_CROSSING
;
4439 make_edge (first_bb
, rec
, edge_flags
);
4440 label
= block_label (second_bb
);
4441 jump
= emit_jump_insn_after (gen_jump (label
), BB_END (rec
));
4442 JUMP_LABEL (jump
) = label
;
4443 LABEL_NUSES (label
)++;
4445 if (BB_PARTITION (second_bb
) != BB_PARTITION (rec
))
4446 /* Partition type is the same, if it is "unpartitioned". */
4448 /* Rewritten from cfgrtl.c. */
4449 if (flag_reorder_blocks_and_partition
4450 && targetm
.have_named_sections
)
4452 /* We don't need the same note for the check because
4453 any_condjump_p (check) == true. */
4454 add_reg_note (jump
, REG_CROSSING_JUMP
, NULL_RTX
);
4456 edge_flags
= EDGE_CROSSING
;
4461 make_single_succ_edge (rec
, second_bb
, edge_flags
);
4464 /* This function creates recovery code for INSN. If MUTATE_P is nonzero,
4465 INSN is a simple check, that should be converted to branchy one. */
4467 create_check_block_twin (rtx insn
, bool mutate_p
)
4470 rtx label
, check
, twin
;
4472 sd_iterator_def sd_it
;
4474 dep_def _new_dep
, *new_dep
= &_new_dep
;
4477 gcc_assert (ORIG_PAT (insn
) != NULL_RTX
);
4480 todo_spec
= TODO_SPEC (insn
);
4483 gcc_assert (IS_SPECULATION_SIMPLE_CHECK_P (insn
)
4484 && (TODO_SPEC (insn
) & SPECULATIVE
) == 0);
4486 todo_spec
= CHECK_SPEC (insn
);
4489 todo_spec
&= SPECULATIVE
;
4491 /* Create recovery block. */
4492 if (mutate_p
|| targetm
.sched
.needs_block_p (todo_spec
))
4494 rec
= sched_create_recovery_block (NULL
);
4495 label
= BB_HEAD (rec
);
4499 rec
= EXIT_BLOCK_PTR
;
4504 check
= targetm
.sched
.gen_spec_check (insn
, label
, todo_spec
);
4506 if (rec
!= EXIT_BLOCK_PTR
)
4508 /* To have mem_reg alive at the beginning of second_bb,
4509 we emit check BEFORE insn, so insn after splitting
4510 insn will be at the beginning of second_bb, which will
4511 provide us with the correct life information. */
4512 check
= emit_jump_insn_before (check
, insn
);
4513 JUMP_LABEL (check
) = label
;
4514 LABEL_NUSES (label
)++;
4517 check
= emit_insn_before (check
, insn
);
4519 /* Extend data structures. */
4520 haifa_init_insn (check
);
4522 /* CHECK is being added to current region. Extend ready list. */
4523 gcc_assert (sched_ready_n_insns
!= -1);
4524 sched_extend_ready_list (sched_ready_n_insns
+ 1);
4526 if (current_sched_info
->add_remove_insn
)
4527 current_sched_info
->add_remove_insn (insn
, 0);
4529 RECOVERY_BLOCK (check
) = rec
;
4531 if (sched_verbose
&& spec_info
->dump
)
4532 fprintf (spec_info
->dump
, ";;\t\tGenerated check insn : %s\n",
4533 (*current_sched_info
->print_insn
) (check
, 0));
4535 gcc_assert (ORIG_PAT (insn
));
4537 /* Initialize TWIN (twin is a duplicate of original instruction
4538 in the recovery block). */
4539 if (rec
!= EXIT_BLOCK_PTR
)
4541 sd_iterator_def sd_it
;
4544 FOR_EACH_DEP (insn
, SD_LIST_RES_BACK
, sd_it
, dep
)
4545 if ((DEP_STATUS (dep
) & DEP_OUTPUT
) != 0)
4547 struct _dep _dep2
, *dep2
= &_dep2
;
4549 init_dep (dep2
, DEP_PRO (dep
), check
, REG_DEP_TRUE
);
4551 sd_add_dep (dep2
, true);
4554 twin
= emit_insn_after (ORIG_PAT (insn
), BB_END (rec
));
4555 haifa_init_insn (twin
);
4557 if (sched_verbose
&& spec_info
->dump
)
4558 /* INSN_BB (insn) isn't determined for twin insns yet.
4559 So we can't use current_sched_info->print_insn. */
4560 fprintf (spec_info
->dump
, ";;\t\tGenerated twin insn : %d/rec%d\n",
4561 INSN_UID (twin
), rec
->index
);
4565 ORIG_PAT (check
) = ORIG_PAT (insn
);
4566 HAS_INTERNAL_DEP (check
) = 1;
4568 /* ??? We probably should change all OUTPUT dependencies to
4572 /* Copy all resolved back dependencies of INSN to TWIN. This will
4573 provide correct value for INSN_TICK (TWIN). */
4574 sd_copy_back_deps (twin
, insn
, true);
4576 if (rec
!= EXIT_BLOCK_PTR
)
4577 /* In case of branchy check, fix CFG. */
4579 basic_block first_bb
, second_bb
;
4582 first_bb
= BLOCK_FOR_INSN (check
);
4583 second_bb
= sched_split_block (first_bb
, check
);
4585 sched_create_recovery_edges (first_bb
, rec
, second_bb
);
4587 sched_init_only_bb (second_bb
, first_bb
);
4588 sched_init_only_bb (rec
, EXIT_BLOCK_PTR
);
4590 jump
= BB_END (rec
);
4591 haifa_init_insn (jump
);
4594 /* Move backward dependences from INSN to CHECK and
4595 move forward dependences from INSN to TWIN. */
4597 /* First, create dependencies between INSN's producers and CHECK & TWIN. */
4598 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
4600 rtx pro
= DEP_PRO (dep
);
4603 /* If BEGIN_DATA: [insn ~~TRUE~~> producer]:
4604 check --TRUE--> producer ??? or ANTI ???
4605 twin --TRUE--> producer
4606 twin --ANTI--> check
4608 If BEGIN_CONTROL: [insn ~~ANTI~~> producer]:
4609 check --ANTI--> producer
4610 twin --ANTI--> producer
4611 twin --ANTI--> check
4613 If BE_IN_SPEC: [insn ~~TRUE~~> producer]:
4614 check ~~TRUE~~> producer
4615 twin ~~TRUE~~> producer
4616 twin --ANTI--> check */
4618 ds
= DEP_STATUS (dep
);
4620 if (ds
& BEGIN_SPEC
)
4622 gcc_assert (!mutate_p
);
4626 init_dep_1 (new_dep
, pro
, check
, DEP_TYPE (dep
), ds
);
4627 sd_add_dep (new_dep
, false);
4629 if (rec
!= EXIT_BLOCK_PTR
)
4631 DEP_CON (new_dep
) = twin
;
4632 sd_add_dep (new_dep
, false);
4636 /* Second, remove backward dependencies of INSN. */
4637 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
4638 sd_iterator_cond (&sd_it
, &dep
);)
4640 if ((DEP_STATUS (dep
) & BEGIN_SPEC
)
4642 /* We can delete this dep because we overcome it with
4643 BEGIN_SPECULATION. */
4644 sd_delete_dep (sd_it
);
4646 sd_iterator_next (&sd_it
);
4649 /* Future Speculations. Determine what BE_IN speculations will be like. */
4652 /* Fields (DONE_SPEC (x) & BEGIN_SPEC) and CHECK_SPEC (x) are set only
4655 gcc_assert (!DONE_SPEC (insn
));
4659 ds_t ts
= TODO_SPEC (insn
);
4661 DONE_SPEC (insn
) = ts
& BEGIN_SPEC
;
4662 CHECK_SPEC (check
) = ts
& BEGIN_SPEC
;
4664 /* Luckiness of future speculations solely depends upon initial
4665 BEGIN speculation. */
4666 if (ts
& BEGIN_DATA
)
4667 fs
= set_dep_weak (fs
, BE_IN_DATA
, get_dep_weak (ts
, BEGIN_DATA
));
4668 if (ts
& BEGIN_CONTROL
)
4669 fs
= set_dep_weak (fs
, BE_IN_CONTROL
,
4670 get_dep_weak (ts
, BEGIN_CONTROL
));
4673 CHECK_SPEC (check
) = CHECK_SPEC (insn
);
4675 /* Future speculations: call the helper. */
4676 process_insn_forw_deps_be_in_spec (insn
, twin
, fs
);
4678 if (rec
!= EXIT_BLOCK_PTR
)
4680 /* Which types of dependencies should we use here is,
4681 generally, machine-dependent question... But, for now,
4686 init_dep (new_dep
, insn
, check
, REG_DEP_TRUE
);
4687 sd_add_dep (new_dep
, false);
4689 init_dep (new_dep
, insn
, twin
, REG_DEP_OUTPUT
);
4690 sd_add_dep (new_dep
, false);
4694 if (spec_info
->dump
)
4695 fprintf (spec_info
->dump
, ";;\t\tRemoved simple check : %s\n",
4696 (*current_sched_info
->print_insn
) (insn
, 0));
4698 /* Remove all dependencies of the INSN. */
4700 sd_it
= sd_iterator_start (insn
, (SD_LIST_FORW
4702 | SD_LIST_RES_BACK
));
4703 while (sd_iterator_cond (&sd_it
, &dep
))
4704 sd_delete_dep (sd_it
);
4707 /* If former check (INSN) already was moved to the ready (or queue)
4708 list, add new check (CHECK) there too. */
4709 if (QUEUE_INDEX (insn
) != QUEUE_NOWHERE
)
4712 /* Remove old check from instruction stream and free its
4714 sched_remove_insn (insn
);
4717 init_dep (new_dep
, check
, twin
, REG_DEP_ANTI
);
4718 sd_add_dep (new_dep
, false);
4722 init_dep_1 (new_dep
, insn
, check
, REG_DEP_TRUE
, DEP_TRUE
| DEP_OUTPUT
);
4723 sd_add_dep (new_dep
, false);
4727 /* Fix priorities. If MUTATE_P is nonzero, this is not necessary,
4728 because it'll be done later in add_to_speculative_block. */
4730 rtx_vec_t priorities_roots
= NULL
;
4732 clear_priorities (twin
, &priorities_roots
);
4733 calc_priorities (priorities_roots
);
4734 VEC_free (rtx
, heap
, priorities_roots
);
4738 /* Removes dependency between instructions in the recovery block REC
4739 and usual region instructions. It keeps inner dependences so it
4740 won't be necessary to recompute them. */
4742 fix_recovery_deps (basic_block rec
)
4744 rtx note
, insn
, jump
, ready_list
= 0;
4745 bitmap_head in_ready
;
4748 bitmap_initialize (&in_ready
, 0);
4750 /* NOTE - a basic block note. */
4751 note
= NEXT_INSN (BB_HEAD (rec
));
4752 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
4753 insn
= BB_END (rec
);
4754 gcc_assert (JUMP_P (insn
));
4755 insn
= PREV_INSN (insn
);
4759 sd_iterator_def sd_it
;
4762 for (sd_it
= sd_iterator_start (insn
, SD_LIST_FORW
);
4763 sd_iterator_cond (&sd_it
, &dep
);)
4765 rtx consumer
= DEP_CON (dep
);
4767 if (BLOCK_FOR_INSN (consumer
) != rec
)
4769 sd_delete_dep (sd_it
);
4771 if (bitmap_set_bit (&in_ready
, INSN_LUID (consumer
)))
4772 ready_list
= alloc_INSN_LIST (consumer
, ready_list
);
4776 gcc_assert ((DEP_STATUS (dep
) & DEP_TYPES
) == DEP_TRUE
);
4778 sd_iterator_next (&sd_it
);
4782 insn
= PREV_INSN (insn
);
4784 while (insn
!= note
);
4786 bitmap_clear (&in_ready
);
4788 /* Try to add instructions to the ready or queue list. */
4789 for (link
= ready_list
; link
; link
= XEXP (link
, 1))
4790 try_ready (XEXP (link
, 0));
4791 free_INSN_LIST_list (&ready_list
);
4793 /* Fixing jump's dependences. */
4794 insn
= BB_HEAD (rec
);
4795 jump
= BB_END (rec
);
4797 gcc_assert (LABEL_P (insn
));
4798 insn
= NEXT_INSN (insn
);
4800 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
4801 add_jump_dependencies (insn
, jump
);
4804 /* Change pattern of INSN to NEW_PAT. */
4806 sched_change_pattern (rtx insn
, rtx new_pat
)
4810 t
= validate_change (insn
, &PATTERN (insn
), new_pat
, 0);
4812 dfa_clear_single_insn_cache (insn
);
4815 /* Change pattern of INSN to NEW_PAT. Invalidate cached haifa
4816 instruction data. */
4818 haifa_change_pattern (rtx insn
, rtx new_pat
)
4820 sched_change_pattern (insn
, new_pat
);
4822 /* Invalidate INSN_COST, so it'll be recalculated. */
4823 INSN_COST (insn
) = -1;
4824 /* Invalidate INSN_TICK, so it'll be recalculated. */
4825 INSN_TICK (insn
) = INVALID_TICK
;
4828 /* -1 - can't speculate,
4829 0 - for speculation with REQUEST mode it is OK to use
4830 current instruction pattern,
4831 1 - need to change pattern for *NEW_PAT to be speculative. */
4833 sched_speculate_insn (rtx insn
, ds_t request
, rtx
*new_pat
)
4835 gcc_assert (current_sched_info
->flags
& DO_SPECULATION
4836 && (request
& SPECULATIVE
)
4837 && sched_insn_is_legitimate_for_speculation_p (insn
, request
));
4839 if ((request
& spec_info
->mask
) != request
)
4842 if (request
& BE_IN_SPEC
4843 && !(request
& BEGIN_SPEC
))
4846 return targetm
.sched
.speculate_insn (insn
, request
, new_pat
);
4850 haifa_speculate_insn (rtx insn
, ds_t request
, rtx
*new_pat
)
4852 gcc_assert (sched_deps_info
->generate_spec_deps
4853 && !IS_SPECULATION_CHECK_P (insn
));
4855 if (HAS_INTERNAL_DEP (insn
)
4856 || SCHED_GROUP_P (insn
))
4859 return sched_speculate_insn (insn
, request
, new_pat
);
4862 /* Print some information about block BB, which starts with HEAD and
4863 ends with TAIL, before scheduling it.
4864 I is zero, if scheduler is about to start with the fresh ebb. */
4866 dump_new_block_header (int i
, basic_block bb
, rtx head
, rtx tail
)
4869 fprintf (sched_dump
,
4870 ";; ======================================================\n");
4872 fprintf (sched_dump
,
4873 ";; =====================ADVANCING TO=====================\n");
4874 fprintf (sched_dump
,
4875 ";; -- basic block %d from %d to %d -- %s reload\n",
4876 bb
->index
, INSN_UID (head
), INSN_UID (tail
),
4877 (reload_completed
? "after" : "before"));
4878 fprintf (sched_dump
,
4879 ";; ======================================================\n");
4880 fprintf (sched_dump
, "\n");
4883 /* Unlink basic block notes and labels and saves them, so they
4884 can be easily restored. We unlink basic block notes in EBB to
4885 provide back-compatibility with the previous code, as target backends
4886 assume, that there'll be only instructions between
4887 current_sched_info->{head and tail}. We restore these notes as soon
4889 FIRST (LAST) is the first (last) basic block in the ebb.
4890 NB: In usual case (FIRST == LAST) nothing is really done. */
4892 unlink_bb_notes (basic_block first
, basic_block last
)
4894 /* We DON'T unlink basic block notes of the first block in the ebb. */
4898 bb_header
= XNEWVEC (rtx
, last_basic_block
);
4900 /* Make a sentinel. */
4901 if (last
->next_bb
!= EXIT_BLOCK_PTR
)
4902 bb_header
[last
->next_bb
->index
] = 0;
4904 first
= first
->next_bb
;
4907 rtx prev
, label
, note
, next
;
4909 label
= BB_HEAD (last
);
4910 if (LABEL_P (label
))
4911 note
= NEXT_INSN (label
);
4914 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
4916 prev
= PREV_INSN (label
);
4917 next
= NEXT_INSN (note
);
4918 gcc_assert (prev
&& next
);
4920 NEXT_INSN (prev
) = next
;
4921 PREV_INSN (next
) = prev
;
4923 bb_header
[last
->index
] = label
;
4928 last
= last
->prev_bb
;
4933 /* Restore basic block notes.
4934 FIRST is the first basic block in the ebb. */
4936 restore_bb_notes (basic_block first
)
4941 /* We DON'T unlink basic block notes of the first block in the ebb. */
4942 first
= first
->next_bb
;
4943 /* Remember: FIRST is actually a second basic block in the ebb. */
4945 while (first
!= EXIT_BLOCK_PTR
4946 && bb_header
[first
->index
])
4948 rtx prev
, label
, note
, next
;
4950 label
= bb_header
[first
->index
];
4951 prev
= PREV_INSN (label
);
4952 next
= NEXT_INSN (prev
);
4954 if (LABEL_P (label
))
4955 note
= NEXT_INSN (label
);
4958 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
4960 bb_header
[first
->index
] = 0;
4962 NEXT_INSN (prev
) = label
;
4963 NEXT_INSN (note
) = next
;
4964 PREV_INSN (next
) = note
;
4966 first
= first
->next_bb
;
4974 Fix CFG after both in- and inter-block movement of
4975 control_flow_insn_p JUMP. */
4977 fix_jump_move (rtx jump
)
4979 basic_block bb
, jump_bb
, jump_bb_next
;
4981 bb
= BLOCK_FOR_INSN (PREV_INSN (jump
));
4982 jump_bb
= BLOCK_FOR_INSN (jump
);
4983 jump_bb_next
= jump_bb
->next_bb
;
4985 gcc_assert (common_sched_info
->sched_pass_id
== SCHED_EBB_PASS
4986 || IS_SPECULATION_BRANCHY_CHECK_P (jump
));
4988 if (!NOTE_INSN_BASIC_BLOCK_P (BB_END (jump_bb_next
)))
4989 /* if jump_bb_next is not empty. */
4990 BB_END (jump_bb
) = BB_END (jump_bb_next
);
4992 if (BB_END (bb
) != PREV_INSN (jump
))
4993 /* Then there are instruction after jump that should be placed
4995 BB_END (jump_bb_next
) = BB_END (bb
);
4997 /* Otherwise jump_bb_next is empty. */
4998 BB_END (jump_bb_next
) = NEXT_INSN (BB_HEAD (jump_bb_next
));
5000 /* To make assertion in move_insn happy. */
5001 BB_END (bb
) = PREV_INSN (jump
);
5003 update_bb_for_insn (jump_bb_next
);
5006 /* Fix CFG after interblock movement of control_flow_insn_p JUMP. */
5008 move_block_after_check (rtx jump
)
5010 basic_block bb
, jump_bb
, jump_bb_next
;
5013 bb
= BLOCK_FOR_INSN (PREV_INSN (jump
));
5014 jump_bb
= BLOCK_FOR_INSN (jump
);
5015 jump_bb_next
= jump_bb
->next_bb
;
5017 update_bb_for_insn (jump_bb
);
5019 gcc_assert (IS_SPECULATION_CHECK_P (jump
)
5020 || IS_SPECULATION_CHECK_P (BB_END (jump_bb_next
)));
5022 unlink_block (jump_bb_next
);
5023 link_block (jump_bb_next
, bb
);
5027 move_succs (&(jump_bb
->succs
), bb
);
5028 move_succs (&(jump_bb_next
->succs
), jump_bb
);
5029 move_succs (&t
, jump_bb_next
);
5031 df_mark_solutions_dirty ();
5033 common_sched_info
->fix_recovery_cfg
5034 (bb
->index
, jump_bb
->index
, jump_bb_next
->index
);
5037 /* Helper function for move_block_after_check.
5038 This functions attaches edge vector pointed to by SUCCSP to
5041 move_succs (VEC(edge
,gc
) **succsp
, basic_block to
)
5046 gcc_assert (to
->succs
== 0);
5048 to
->succs
= *succsp
;
5050 FOR_EACH_EDGE (e
, ei
, to
->succs
)
5056 /* Remove INSN from the instruction stream.
5057 INSN should have any dependencies. */
5059 sched_remove_insn (rtx insn
)
5061 sd_finish_insn (insn
);
5063 change_queue_index (insn
, QUEUE_NOWHERE
);
5064 current_sched_info
->add_remove_insn (insn
, 1);
5068 /* Clear priorities of all instructions, that are forward dependent on INSN.
5069 Store in vector pointed to by ROOTS_PTR insns on which priority () should
5070 be invoked to initialize all cleared priorities. */
5072 clear_priorities (rtx insn
, rtx_vec_t
*roots_ptr
)
5074 sd_iterator_def sd_it
;
5076 bool insn_is_root_p
= true;
5078 gcc_assert (QUEUE_INDEX (insn
) != QUEUE_SCHEDULED
);
5080 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
5082 rtx pro
= DEP_PRO (dep
);
5084 if (INSN_PRIORITY_STATUS (pro
) >= 0
5085 && QUEUE_INDEX (insn
) != QUEUE_SCHEDULED
)
5087 /* If DEP doesn't contribute to priority then INSN itself should
5088 be added to priority roots. */
5089 if (contributes_to_priority_p (dep
))
5090 insn_is_root_p
= false;
5092 INSN_PRIORITY_STATUS (pro
) = -1;
5093 clear_priorities (pro
, roots_ptr
);
5098 VEC_safe_push (rtx
, heap
, *roots_ptr
, insn
);
5101 /* Recompute priorities of instructions, whose priorities might have been
5102 changed. ROOTS is a vector of instructions whose priority computation will
5103 trigger initialization of all cleared priorities. */
5105 calc_priorities (rtx_vec_t roots
)
5110 FOR_EACH_VEC_ELT (rtx
, roots
, i
, insn
)
5115 /* Add dependences between JUMP and other instructions in the recovery
5116 block. INSN is the first insn the recovery block. */
5118 add_jump_dependencies (rtx insn
, rtx jump
)
5122 insn
= NEXT_INSN (insn
);
5126 if (dep_list_size (insn
) == 0)
5128 dep_def _new_dep
, *new_dep
= &_new_dep
;
5130 init_dep (new_dep
, insn
, jump
, REG_DEP_ANTI
);
5131 sd_add_dep (new_dep
, false);
5136 gcc_assert (!sd_lists_empty_p (jump
, SD_LIST_BACK
));
5139 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
5141 bb_note (basic_block bb
)
5145 note
= BB_HEAD (bb
);
5147 note
= NEXT_INSN (note
);
5149 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
5153 #ifdef ENABLE_CHECKING
5154 /* Helper function for check_cfg.
5155 Return nonzero, if edge vector pointed to by EL has edge with TYPE in
5158 has_edge_p (VEC(edge
,gc
) *el
, int type
)
5163 FOR_EACH_EDGE (e
, ei
, el
)
5164 if (e
->flags
& type
)
5169 /* Search back, starting at INSN, for an insn that is not a
5170 NOTE_INSN_VAR_LOCATION. Don't search beyond HEAD, and return it if
5171 no such insn can be found. */
5173 prev_non_location_insn (rtx insn
, rtx head
)
5175 while (insn
!= head
&& NOTE_P (insn
)
5176 && NOTE_KIND (insn
) == NOTE_INSN_VAR_LOCATION
)
5177 insn
= PREV_INSN (insn
);
5182 /* Check few properties of CFG between HEAD and TAIL.
5183 If HEAD (TAIL) is NULL check from the beginning (till the end) of the
5184 instruction stream. */
5186 check_cfg (rtx head
, rtx tail
)
5190 int not_first
= 0, not_last
;
5193 head
= get_insns ();
5195 tail
= get_last_insn ();
5196 next_tail
= NEXT_INSN (tail
);
5200 not_last
= head
!= tail
;
5203 gcc_assert (NEXT_INSN (PREV_INSN (head
)) == head
);
5205 gcc_assert (PREV_INSN (NEXT_INSN (head
)) == head
);
5208 || (NOTE_INSN_BASIC_BLOCK_P (head
)
5210 || (not_first
&& !LABEL_P (PREV_INSN (head
))))))
5212 gcc_assert (bb
== 0);
5213 bb
= BLOCK_FOR_INSN (head
);
5215 gcc_assert (BB_HEAD (bb
) == head
);
5217 /* This is the case of jump table. See inside_basic_block_p (). */
5218 gcc_assert (LABEL_P (head
) && !inside_basic_block_p (head
));
5223 gcc_assert (!inside_basic_block_p (head
));
5224 head
= NEXT_INSN (head
);
5228 gcc_assert (inside_basic_block_p (head
)
5230 gcc_assert (BLOCK_FOR_INSN (head
) == bb
);
5234 head
= NEXT_INSN (head
);
5235 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (head
));
5239 if (control_flow_insn_p (head
))
5241 gcc_assert (prev_non_location_insn (BB_END (bb
), head
)
5244 if (any_uncondjump_p (head
))
5245 gcc_assert (EDGE_COUNT (bb
->succs
) == 1
5246 && BARRIER_P (NEXT_INSN (head
)));
5247 else if (any_condjump_p (head
))
5248 gcc_assert (/* Usual case. */
5249 (EDGE_COUNT (bb
->succs
) > 1
5250 && !BARRIER_P (NEXT_INSN (head
)))
5251 /* Or jump to the next instruction. */
5252 || (EDGE_COUNT (bb
->succs
) == 1
5253 && (BB_HEAD (EDGE_I (bb
->succs
, 0)->dest
)
5254 == JUMP_LABEL (head
))));
5256 if (BB_END (bb
) == head
)
5258 if (EDGE_COUNT (bb
->succs
) > 1)
5259 gcc_assert (control_flow_insn_p (prev_non_location_insn
5260 (head
, BB_HEAD (bb
)))
5261 || has_edge_p (bb
->succs
, EDGE_COMPLEX
));
5265 head
= NEXT_INSN (head
);
5271 while (head
!= next_tail
);
5273 gcc_assert (bb
== 0);
5276 #endif /* ENABLE_CHECKING */
5278 /* Extend per basic block data structures. */
5282 if (sched_scan_info
->extend_bb
)
5283 sched_scan_info
->extend_bb ();
5286 /* Init data for BB. */
5288 init_bb (basic_block bb
)
5290 if (sched_scan_info
->init_bb
)
5291 sched_scan_info
->init_bb (bb
);
5294 /* Extend per insn data structures. */
5298 if (sched_scan_info
->extend_insn
)
5299 sched_scan_info
->extend_insn ();
5302 /* Init data structures for INSN. */
5304 init_insn (rtx insn
)
5306 if (sched_scan_info
->init_insn
)
5307 sched_scan_info
->init_insn (insn
);
5310 /* Init all insns in BB. */
5312 init_insns_in_bb (basic_block bb
)
5316 FOR_BB_INSNS (bb
, insn
)
5320 /* A driver function to add a set of basic blocks (BBS),
5321 a single basic block (BB), a set of insns (INSNS) or a single insn (INSN)
5322 to the scheduling region. */
5324 sched_scan (const struct sched_scan_info_def
*ssi
,
5325 bb_vec_t bbs
, basic_block bb
, insn_vec_t insns
, rtx insn
)
5327 sched_scan_info
= ssi
;
5329 if (bbs
!= NULL
|| bb
!= NULL
)
5338 FOR_EACH_VEC_ELT (basic_block
, bbs
, i
, x
)
5353 FOR_EACH_VEC_ELT (basic_block
, bbs
, i
, x
)
5354 init_insns_in_bb (x
);
5358 init_insns_in_bb (bb
);
5365 FOR_EACH_VEC_ELT (rtx
, insns
, i
, x
)
5374 /* Extend data structures for logical insn UID. */
5376 luids_extend_insn (void)
5378 int new_luids_max_uid
= get_max_uid () + 1;
5380 VEC_safe_grow_cleared (int, heap
, sched_luids
, new_luids_max_uid
);
5383 /* Initialize LUID for INSN. */
5385 luids_init_insn (rtx insn
)
5387 int i
= INSN_P (insn
) ? 1 : common_sched_info
->luid_for_non_insn (insn
);
5392 luid
= sched_max_luid
;
5393 sched_max_luid
+= i
;
5398 SET_INSN_LUID (insn
, luid
);
5401 /* Initialize luids for BBS, BB, INSNS and INSN.
5402 The hook common_sched_info->luid_for_non_insn () is used to determine
5403 if notes, labels, etc. need luids. */
5405 sched_init_luids (bb_vec_t bbs
, basic_block bb
, insn_vec_t insns
, rtx insn
)
5407 const struct sched_scan_info_def ssi
=
5409 NULL
, /* extend_bb */
5411 luids_extend_insn
, /* extend_insn */
5412 luids_init_insn
/* init_insn */
5415 sched_scan (&ssi
, bbs
, bb
, insns
, insn
);
5420 sched_finish_luids (void)
5422 VEC_free (int, heap
, sched_luids
);
5426 /* Return logical uid of INSN. Helpful while debugging. */
5428 insn_luid (rtx insn
)
5430 return INSN_LUID (insn
);
5433 /* Extend per insn data in the target. */
5435 sched_extend_target (void)
5437 if (targetm
.sched
.h_i_d_extended
)
5438 targetm
.sched
.h_i_d_extended ();
5441 /* Extend global scheduler structures (those, that live across calls to
5442 schedule_block) to include information about just emitted INSN. */
5446 int reserve
= (get_max_uid () + 1
5447 - VEC_length (haifa_insn_data_def
, h_i_d
));
5449 && ! VEC_space (haifa_insn_data_def
, h_i_d
, reserve
))
5451 VEC_safe_grow_cleared (haifa_insn_data_def
, heap
, h_i_d
,
5452 3 * get_max_uid () / 2);
5453 sched_extend_target ();
5457 /* Initialize h_i_d entry of the INSN with default values.
5458 Values, that are not explicitly initialized here, hold zero. */
5460 init_h_i_d (rtx insn
)
5462 if (INSN_LUID (insn
) > 0)
5464 INSN_COST (insn
) = -1;
5465 QUEUE_INDEX (insn
) = QUEUE_NOWHERE
;
5466 INSN_TICK (insn
) = INVALID_TICK
;
5467 INTER_TICK (insn
) = INVALID_TICK
;
5468 TODO_SPEC (insn
) = HARD_DEP
;
5472 /* Initialize haifa_insn_data for BBS, BB, INSNS and INSN. */
5474 haifa_init_h_i_d (bb_vec_t bbs
, basic_block bb
, insn_vec_t insns
, rtx insn
)
5476 const struct sched_scan_info_def ssi
=
5478 NULL
, /* extend_bb */
5480 extend_h_i_d
, /* extend_insn */
5481 init_h_i_d
/* init_insn */
5484 sched_scan (&ssi
, bbs
, bb
, insns
, insn
);
5487 /* Finalize haifa_insn_data. */
5489 haifa_finish_h_i_d (void)
5492 haifa_insn_data_t data
;
5493 struct reg_use_data
*use
, *next
;
5495 FOR_EACH_VEC_ELT (haifa_insn_data_def
, h_i_d
, i
, data
)
5497 if (data
->reg_pressure
!= NULL
)
5498 free (data
->reg_pressure
);
5499 for (use
= data
->reg_use_list
; use
!= NULL
; use
= next
)
5501 next
= use
->next_insn_use
;
5505 VEC_free (haifa_insn_data_def
, heap
, h_i_d
);
5508 /* Init data for the new insn INSN. */
5510 haifa_init_insn (rtx insn
)
5512 gcc_assert (insn
!= NULL
);
5514 sched_init_luids (NULL
, NULL
, NULL
, insn
);
5515 sched_extend_target ();
5516 sched_deps_init (false);
5517 haifa_init_h_i_d (NULL
, NULL
, NULL
, insn
);
5519 if (adding_bb_to_current_region_p
)
5521 sd_init_insn (insn
);
5523 /* Extend dependency caches by one element. */
5524 extend_dependency_caches (1, false);
5528 /* Init data for the new basic block BB which comes after AFTER. */
5530 haifa_init_only_bb (basic_block bb
, basic_block after
)
5532 gcc_assert (bb
!= NULL
);
5536 if (common_sched_info
->add_block
)
5537 /* This changes only data structures of the front-end. */
5538 common_sched_info
->add_block (bb
, after
);
5541 /* A generic version of sched_split_block (). */
5543 sched_split_block_1 (basic_block first_bb
, rtx after
)
5547 e
= split_block (first_bb
, after
);
5548 gcc_assert (e
->src
== first_bb
);
5550 /* sched_split_block emits note if *check == BB_END. Probably it
5551 is better to rip that note off. */
5556 /* A generic version of sched_create_empty_bb (). */
5558 sched_create_empty_bb_1 (basic_block after
)
5560 return create_empty_bb (after
);
5563 /* Insert PAT as an INSN into the schedule and update the necessary data
5564 structures to account for it. */
5566 sched_emit_insn (rtx pat
)
5568 rtx insn
= emit_insn_after (pat
, last_scheduled_insn
);
5569 last_scheduled_insn
= insn
;
5570 haifa_init_insn (insn
);
5574 /* This function returns a candidate satisfying dispatch constraints from
5578 ready_remove_first_dispatch (struct ready_list
*ready
)
5581 rtx insn
= ready_element (ready
, 0);
5583 if (ready
->n_ready
== 1
5584 || INSN_CODE (insn
) < 0
5586 || !active_insn_p (insn
)
5587 || targetm
.sched
.dispatch (insn
, FITS_DISPATCH_WINDOW
))
5588 return ready_remove_first (ready
);
5590 for (i
= 1; i
< ready
->n_ready
; i
++)
5592 insn
= ready_element (ready
, i
);
5594 if (INSN_CODE (insn
) < 0
5596 || !active_insn_p (insn
))
5599 if (targetm
.sched
.dispatch (insn
, FITS_DISPATCH_WINDOW
))
5601 /* Return ith element of ready. */
5602 insn
= ready_remove (ready
, i
);
5607 if (targetm
.sched
.dispatch (NULL_RTX
, DISPATCH_VIOLATION
))
5608 return ready_remove_first (ready
);
5610 for (i
= 1; i
< ready
->n_ready
; i
++)
5612 insn
= ready_element (ready
, i
);
5614 if (INSN_CODE (insn
) < 0
5616 || !active_insn_p (insn
))
5619 /* Return i-th element of ready. */
5620 if (targetm
.sched
.dispatch (insn
, IS_CMP
))
5621 return ready_remove (ready
, i
);
5624 return ready_remove_first (ready
);
5627 /* Get number of ready insn in the ready list. */
5630 number_in_ready (void)
5632 return ready
.n_ready
;
5635 /* Get number of ready's in the ready list. */
5638 get_ready_element (int i
)
5640 return ready_element (&ready
, i
);
5643 #endif /* INSN_SCHEDULING */