1 /* Instruction scheduling pass.
2 Copyright (C) 1992-2015 Free Software Foundation, Inc.
3 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
4 and currently maintained by, Jim Wilson (wilson@cygnus.com)
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* Instruction scheduling pass. This file, along with sched-deps.c,
23 contains the generic parts. The actual entry point for
24 the normal instruction scheduling pass is found in sched-rgn.c.
26 We compute insn priorities based on data dependencies. Flow
27 analysis only creates a fraction of the data-dependencies we must
28 observe: namely, only those dependencies which the combiner can be
29 expected to use. For this pass, we must therefore create the
30 remaining dependencies we need to observe: register dependencies,
31 memory dependencies, dependencies to keep function calls in order,
32 and the dependence between a conditional branch and the setting of
33 condition codes are all dealt with here.
35 The scheduler first traverses the data flow graph, starting with
36 the last instruction, and proceeding to the first, assigning values
37 to insn_priority as it goes. This sorts the instructions
38 topologically by data dependence.
40 Once priorities have been established, we order the insns using
41 list scheduling. This works as follows: starting with a list of
42 all the ready insns, and sorted according to priority number, we
43 schedule the insn from the end of the list by placing its
44 predecessors in the list according to their priority order. We
45 consider this insn scheduled by setting the pointer to the "end" of
46 the list to point to the previous insn. When an insn has no
47 predecessors, we either queue it until sufficient time has elapsed
48 or add it to the ready list. As the instructions are scheduled or
49 when stalls are introduced, the queue advances and dumps insns into
50 the ready list. When all insns down to the lowest priority have
51 been scheduled, the critical path of the basic block has been made
52 as short as possible. The remaining insns are then scheduled in
55 The following list shows the order in which we want to break ties
56 among insns in the ready list:
58 1. choose insn with the longest path to end of bb, ties
60 2. choose insn with least contribution to register pressure,
62 3. prefer in-block upon interblock motion, ties broken by
63 4. prefer useful upon speculative motion, ties broken by
64 5. choose insn with largest control flow probability, ties
66 6. choose insn with the least dependences upon the previously
67 scheduled insn, or finally
68 7 choose the insn which has the most insns dependent on it.
69 8. choose insn with lowest UID.
71 Memory references complicate matters. Only if we can be certain
72 that memory references are not part of the data dependency graph
73 (via true, anti, or output dependence), can we move operations past
74 memory references. To first approximation, reads can be done
75 independently, while writes introduce dependencies. Better
76 approximations will yield fewer dependencies.
78 Before reload, an extended analysis of interblock data dependences
79 is required for interblock scheduling. This is performed in
80 compute_block_dependences ().
82 Dependencies set up by memory references are treated in exactly the
83 same way as other dependencies, by using insn backward dependences
84 INSN_BACK_DEPS. INSN_BACK_DEPS are translated into forward dependences
85 INSN_FORW_DEPS for the purpose of forward list scheduling.
87 Having optimized the critical path, we may have also unduly
88 extended the lifetimes of some registers. If an operation requires
89 that constants be loaded into registers, it is certainly desirable
90 to load those constants as early as necessary, but no earlier.
91 I.e., it will not do to load up a bunch of registers at the
92 beginning of a basic block only to use them at the end, if they
93 could be loaded later, since this may result in excessive register
96 Note that since branches are never in basic blocks, but only end
97 basic blocks, this pass will not move branches. But that is ok,
98 since we can use GNU's delayed branch scheduling pass to take care
101 Also note that no further optimizations based on algebraic
102 identities are performed, so this pass would be a good one to
103 perform instruction splitting, such as breaking up a multiply
104 instruction into shifts and adds where that is profitable.
106 Given the memory aliasing analysis that this pass should perform,
107 it should be possible to remove redundant stores to memory, and to
108 load values from registers instead of hitting memory.
110 Before reload, speculative insns are moved only if a 'proof' exists
111 that no exception will be caused by this, and if no live registers
112 exist that inhibit the motion (live registers constraints are not
113 represented by data dependence edges).
115 This pass must update information that subsequent passes expect to
116 be correct. Namely: reg_n_refs, reg_n_sets, reg_n_deaths,
117 reg_n_calls_crossed, and reg_live_length. Also, BB_HEAD, BB_END.
119 The information in the line number notes is carefully retained by
120 this pass. Notes that refer to the starting and ending of
121 exception regions are also carefully retained by this pass. All
122 other NOTE insns are grouped in their same relative order at the
123 beginning of basic blocks and regions that have been scheduled. */
127 #include "coretypes.h"
129 #include "diagnostic-core.h"
130 #include "hard-reg-set.h"
135 #include "hash-set.h"
137 #include "machmode.h"
139 #include "function.h"
141 #include "insn-config.h"
142 #include "insn-attr.h"
145 #include "dominance.h"
148 #include "cfgbuild.h"
150 #include "basic-block.h"
151 #include "sched-int.h"
153 #include "common/common-target.h"
158 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
159 #include "hash-table.h"
160 #include "dumpfile.h"
162 #ifdef INSN_SCHEDULING
164 /* True if we do register pressure relief through live-range
166 static bool live_range_shrinkage_p;
168 /* Switch on live range shrinkage. */
170 initialize_live_range_shrinkage (void)
172 live_range_shrinkage_p = true;
175 /* Switch off live range shrinkage. */
177 finish_live_range_shrinkage (void)
179 live_range_shrinkage_p = false;
182 /* issue_rate is the number of insns that can be scheduled in the same
183 machine cycle. It can be defined in the config/mach/mach.h file,
184 otherwise we set it to 1. */
188 /* This can be set to true by a backend if the scheduler should not
189 enable a DCE pass. */
192 /* The current initiation interval used when modulo scheduling. */
193 static int modulo_ii;
195 /* The maximum number of stages we are prepared to handle. */
196 static int modulo_max_stages;
198 /* The number of insns that exist in each iteration of the loop. We use this
199 to detect when we've scheduled all insns from the first iteration. */
200 static int modulo_n_insns;
202 /* The current count of insns in the first iteration of the loop that have
203 already been scheduled. */
204 static int modulo_insns_scheduled;
206 /* The maximum uid of insns from the first iteration of the loop. */
207 static int modulo_iter0_max_uid;
209 /* The number of times we should attempt to backtrack when modulo scheduling.
210 Decreased each time we have to backtrack. */
211 static int modulo_backtracks_left;
213 /* The stage in which the last insn from the original loop was
215 static int modulo_last_stage;
217 /* sched-verbose controls the amount of debugging output the
218 scheduler prints. It is controlled by -fsched-verbose=N:
219 N>0 and no -DSR : the output is directed to stderr.
220 N>=10 will direct the printouts to stderr (regardless of -dSR).
222 N=2: bb's probabilities, detailed ready list info, unit/insn info.
223 N=3: rtl at abort point, control-flow, regions info.
224 N=5: dependences info. */
226 int sched_verbose = 0;
228 /* Debugging file. All printouts are sent to dump, which is always set,
229 either to stderr, or to the dump listing file (-dRS). */
230 FILE *sched_dump = 0;
232 /* This is a placeholder for the scheduler parameters common
233 to all schedulers. */
234 struct common_sched_info_def *common_sched_info;
236 #define INSN_TICK(INSN) (HID (INSN)->tick)
237 #define INSN_EXACT_TICK(INSN) (HID (INSN)->exact_tick)
238 #define INSN_TICK_ESTIMATE(INSN) (HID (INSN)->tick_estimate)
239 #define INTER_TICK(INSN) (HID (INSN)->inter_tick)
240 #define FEEDS_BACKTRACK_INSN(INSN) (HID (INSN)->feeds_backtrack_insn)
241 #define SHADOW_P(INSN) (HID (INSN)->shadow_p)
242 #define MUST_RECOMPUTE_SPEC_P(INSN) (HID (INSN)->must_recompute_spec)
243 /* Cached cost of the instruction. Use insn_cost to get cost of the
244 insn. -1 here means that the field is not initialized. */
245 #define INSN_COST(INSN) (HID (INSN)->cost)
247 /* If INSN_TICK of an instruction is equal to INVALID_TICK,
248 then it should be recalculated from scratch. */
249 #define INVALID_TICK (-(max_insn_queue_index + 1))
250 /* The minimal value of the INSN_TICK of an instruction. */
251 #define MIN_TICK (-max_insn_queue_index)
253 /* Original order of insns in the ready list.
254 Used to keep order of normal insns while separating DEBUG_INSNs. */
255 #define INSN_RFS_DEBUG_ORIG_ORDER(INSN) (HID (INSN)->rfs_debug_orig_order)
257 /* The deciding reason for INSN's place in the ready list. */
258 #define INSN_LAST_RFS_WIN(INSN) (HID (INSN)->last_rfs_win)
260 /* List of important notes we must keep around. This is a pointer to the
261 last element in the list. */
264 static struct spec_info_def spec_info_var;
265 /* Description of the speculative part of the scheduling.
266 If NULL - no speculation. */
267 spec_info_t spec_info = NULL;
269 /* True, if recovery block was added during scheduling of current block.
270 Used to determine, if we need to fix INSN_TICKs. */
271 static bool haifa_recovery_bb_recently_added_p;
273 /* True, if recovery block was added during this scheduling pass.
274 Used to determine if we should have empty memory pools of dependencies
275 after finishing current region. */
276 bool haifa_recovery_bb_ever_added_p;
278 /* Counters of different types of speculative instructions. */
279 static int nr_begin_data, nr_be_in_data, nr_begin_control, nr_be_in_control;
281 /* Array used in {unlink, restore}_bb_notes. */
282 static rtx_insn **bb_header = 0;
284 /* Basic block after which recovery blocks will be created. */
285 static basic_block before_recovery;
287 /* Basic block just before the EXIT_BLOCK and after recovery, if we have
289 basic_block after_recovery;
291 /* FALSE if we add bb to another region, so we don't need to initialize it. */
292 bool adding_bb_to_current_region_p = true;
296 /* An instruction is ready to be scheduled when all insns preceding it
297 have already been scheduled. It is important to ensure that all
298 insns which use its result will not be executed until its result
299 has been computed. An insn is maintained in one of four structures:
301 (P) the "Pending" set of insns which cannot be scheduled until
302 their dependencies have been satisfied.
303 (Q) the "Queued" set of insns that can be scheduled when sufficient
305 (R) the "Ready" list of unscheduled, uncommitted insns.
306 (S) the "Scheduled" list of insns.
308 Initially, all insns are either "Pending" or "Ready" depending on
309 whether their dependencies are satisfied.
311 Insns move from the "Ready" list to the "Scheduled" list as they
312 are committed to the schedule. As this occurs, the insns in the
313 "Pending" list have their dependencies satisfied and move to either
314 the "Ready" list or the "Queued" set depending on whether
315 sufficient time has passed to make them ready. As time passes,
316 insns move from the "Queued" set to the "Ready" list.
318 The "Pending" list (P) are the insns in the INSN_FORW_DEPS of the
319 unscheduled insns, i.e., those that are ready, queued, and pending.
320 The "Queued" set (Q) is implemented by the variable `insn_queue'.
321 The "Ready" list (R) is implemented by the variables `ready' and
323 The "Scheduled" list (S) is the new insn chain built by this pass.
325 The transition (R->S) is implemented in the scheduling loop in
326 `schedule_block' when the best insn to schedule is chosen.
327 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
328 insns move from the ready list to the scheduled list.
329 The transition (Q->R) is implemented in 'queue_to_insn' as time
330 passes or stalls are introduced. */
332 /* Implement a circular buffer to delay instructions until sufficient
333 time has passed. For the new pipeline description interface,
334 MAX_INSN_QUEUE_INDEX is a power of two minus one which is not less
335 than maximal time of instruction execution computed by genattr.c on
336 the base maximal time of functional unit reservations and getting a
337 result. This is the longest time an insn may be queued. */
339 static rtx_insn_list **insn_queue;
340 static int q_ptr = 0;
341 static int q_size = 0;
342 #define NEXT_Q(X) (((X)+1) & max_insn_queue_index)
343 #define NEXT_Q_AFTER(X, C) (((X)+C) & max_insn_queue_index)
345 #define QUEUE_SCHEDULED (-3)
346 #define QUEUE_NOWHERE (-2)
347 #define QUEUE_READY (-1)
348 /* QUEUE_SCHEDULED - INSN is scheduled.
349 QUEUE_NOWHERE - INSN isn't scheduled yet and is neither in
351 QUEUE_READY - INSN is in ready list.
352 N >= 0 - INSN queued for X [where NEXT_Q_AFTER (q_ptr, X) == N] cycles. */
354 #define QUEUE_INDEX(INSN) (HID (INSN)->queue_index)
356 /* The following variable value refers for all current and future
357 reservations of the processor units. */
360 /* The following variable value is size of memory representing all
361 current and future reservations of the processor units. */
362 size_t dfa_state_size;
364 /* The following array is used to find the best insn from ready when
365 the automaton pipeline interface is used. */
366 signed char *ready_try = NULL;
368 /* The ready list. */
369 struct ready_list ready = {NULL, 0, 0, 0, 0};
371 /* The pointer to the ready list (to be removed). */
372 static struct ready_list *readyp = &ready;
374 /* Scheduling clock. */
375 static int clock_var;
377 /* Clock at which the previous instruction was issued. */
378 static int last_clock_var;
380 /* Set to true if, when queuing a shadow insn, we discover that it would be
381 scheduled too late. */
382 static bool must_backtrack;
384 /* The following variable value is number of essential insns issued on
385 the current cycle. An insn is essential one if it changes the
387 int cycle_issued_insns;
389 /* This records the actual schedule. It is built up during the main phase
390 of schedule_block, and afterwards used to reorder the insns in the RTL. */
391 static vec<rtx_insn *> scheduled_insns;
393 static int may_trap_exp (const_rtx, int);
395 /* Nonzero iff the address is comprised from at most 1 register. */
396 #define CONST_BASED_ADDRESS_P(x) \
398 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
399 || (GET_CODE (x) == LO_SUM)) \
400 && (CONSTANT_P (XEXP (x, 0)) \
401 || CONSTANT_P (XEXP (x, 1)))))
403 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
404 as found by analyzing insn's expression. */
407 static int haifa_luid_for_non_insn (rtx x);
409 /* Haifa version of sched_info hooks common to all headers. */
410 const struct common_sched_info_def haifa_common_sched_info =
412 NULL, /* fix_recovery_cfg */
413 NULL, /* add_block */
414 NULL, /* estimate_number_of_insns */
415 haifa_luid_for_non_insn, /* luid_for_non_insn */
416 SCHED_PASS_UNKNOWN /* sched_pass_id */
419 /* Mapping from instruction UID to its Logical UID. */
420 vec<int> sched_luids = vNULL;
422 /* Next LUID to assign to an instruction. */
423 int sched_max_luid = 1;
425 /* Haifa Instruction Data. */
426 vec<haifa_insn_data_def> h_i_d = vNULL;
428 void (* sched_init_only_bb) (basic_block, basic_block);
430 /* Split block function. Different schedulers might use different functions
431 to handle their internal data consistent. */
432 basic_block (* sched_split_block) (basic_block, rtx);
434 /* Create empty basic block after the specified block. */
435 basic_block (* sched_create_empty_bb) (basic_block);
437 /* Return the number of cycles until INSN is expected to be ready.
438 Return zero if it already is. */
440 insn_delay (rtx_insn *insn)
442 return MAX (INSN_TICK (insn) - clock_var, 0);
446 may_trap_exp (const_rtx x, int is_store)
455 if (code == MEM && may_trap_p (x))
462 /* The insn uses memory: a volatile load. */
463 if (MEM_VOLATILE_P (x))
465 /* An exception-free load. */
468 /* A load with 1 base register, to be further checked. */
469 if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))
470 return PFREE_CANDIDATE;
471 /* No info on the load, to be further checked. */
472 return PRISKY_CANDIDATE;
477 int i, insn_class = TRAP_FREE;
479 /* Neither store nor load, check if it may cause a trap. */
482 /* Recursive step: walk the insn... */
483 fmt = GET_RTX_FORMAT (code);
484 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
488 int tmp_class = may_trap_exp (XEXP (x, i), is_store);
489 insn_class = WORST_CLASS (insn_class, tmp_class);
491 else if (fmt[i] == 'E')
494 for (j = 0; j < XVECLEN (x, i); j++)
496 int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);
497 insn_class = WORST_CLASS (insn_class, tmp_class);
498 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
502 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
509 /* Classifies rtx X of an insn for the purpose of verifying that X can be
510 executed speculatively (and consequently the insn can be moved
511 speculatively), by examining X, returning:
512 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
513 TRAP_FREE: non-load insn.
514 IFREE: load from a globally safe location.
515 IRISKY: volatile load.
516 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
517 being either PFREE or PRISKY. */
520 haifa_classify_rtx (const_rtx x)
522 int tmp_class = TRAP_FREE;
523 int insn_class = TRAP_FREE;
526 if (GET_CODE (x) == PARALLEL)
528 int i, len = XVECLEN (x, 0);
530 for (i = len - 1; i >= 0; i--)
532 tmp_class = haifa_classify_rtx (XVECEXP (x, 0, i));
533 insn_class = WORST_CLASS (insn_class, tmp_class);
534 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
544 /* Test if it is a 'store'. */
545 tmp_class = may_trap_exp (XEXP (x, 0), 1);
548 /* Test if it is a store. */
549 tmp_class = may_trap_exp (SET_DEST (x), 1);
550 if (tmp_class == TRAP_RISKY)
552 /* Test if it is a load. */
554 WORST_CLASS (tmp_class,
555 may_trap_exp (SET_SRC (x), 0));
558 tmp_class = haifa_classify_rtx (COND_EXEC_CODE (x));
559 if (tmp_class == TRAP_RISKY)
561 tmp_class = WORST_CLASS (tmp_class,
562 may_trap_exp (COND_EXEC_TEST (x), 0));
565 tmp_class = TRAP_RISKY;
569 insn_class = tmp_class;
576 haifa_classify_insn (const_rtx insn)
578 return haifa_classify_rtx (PATTERN (insn));
581 /* After the scheduler initialization function has been called, this function
582 can be called to enable modulo scheduling. II is the initiation interval
583 we should use, it affects the delays for delay_pairs that were recorded as
584 separated by a given number of stages.
586 MAX_STAGES provides us with a limit
587 after which we give up scheduling; the caller must have unrolled at least
588 as many copies of the loop body and recorded delay_pairs for them.
590 INSNS is the number of real (non-debug) insns in one iteration of
591 the loop. MAX_UID can be used to test whether an insn belongs to
592 the first iteration of the loop; all of them have a uid lower than
595 set_modulo_params (int ii, int max_stages, int insns, int max_uid)
598 modulo_max_stages = max_stages;
599 modulo_n_insns = insns;
600 modulo_iter0_max_uid = max_uid;
601 modulo_backtracks_left = PARAM_VALUE (PARAM_MAX_MODULO_BACKTRACK_ATTEMPTS);
604 /* A structure to record a pair of insns where the first one is a real
605 insn that has delay slots, and the second is its delayed shadow.
606 I1 is scheduled normally and will emit an assembly instruction,
607 while I2 describes the side effect that takes place at the
608 transition between cycles CYCLES and (CYCLES + 1) after I1. */
611 struct delay_pair *next_same_i1;
614 /* When doing modulo scheduling, we a delay_pair can also be used to
615 show that I1 and I2 are the same insn in a different stage. If that
616 is the case, STAGES will be nonzero. */
620 /* Helpers for delay hashing. */
622 struct delay_i1_hasher : typed_noop_remove <delay_pair>
624 typedef delay_pair *value_type;
625 typedef void *compare_type;
626 static inline hashval_t hash (const delay_pair *);
627 static inline bool equal (const delay_pair *, const void *);
630 /* Returns a hash value for X, based on hashing just I1. */
633 delay_i1_hasher::hash (const delay_pair *x)
635 return htab_hash_pointer (x->i1);
638 /* Return true if I1 of pair X is the same as that of pair Y. */
641 delay_i1_hasher::equal (const delay_pair *x, const void *y)
646 struct delay_i2_hasher : typed_free_remove <delay_pair>
648 typedef delay_pair *value_type;
649 typedef void *compare_type;
650 static inline hashval_t hash (const delay_pair *);
651 static inline bool equal (const delay_pair *, const void *);
654 /* Returns a hash value for X, based on hashing just I2. */
657 delay_i2_hasher::hash (const delay_pair *x)
659 return htab_hash_pointer (x->i2);
662 /* Return true if I2 of pair X is the same as that of pair Y. */
665 delay_i2_hasher::equal (const delay_pair *x, const void *y)
670 /* Two hash tables to record delay_pairs, one indexed by I1 and the other
672 static hash_table<delay_i1_hasher> *delay_htab;
673 static hash_table<delay_i2_hasher> *delay_htab_i2;
675 /* Called through htab_traverse. Walk the hashtable using I2 as
676 index, and delete all elements involving an UID higher than
677 that pointed to by *DATA. */
679 haifa_htab_i2_traverse (delay_pair **slot, int *data)
682 struct delay_pair *p = *slot;
683 if (INSN_UID (p->i2) >= maxuid || INSN_UID (p->i1) >= maxuid)
685 delay_htab_i2->clear_slot (slot);
690 /* Called through htab_traverse. Walk the hashtable using I2 as
691 index, and delete all elements involving an UID higher than
692 that pointed to by *DATA. */
694 haifa_htab_i1_traverse (delay_pair **pslot, int *data)
697 struct delay_pair *p, *first, **pprev;
699 if (INSN_UID ((*pslot)->i1) >= maxuid)
701 delay_htab->clear_slot (pslot);
705 for (p = *pslot; p; p = p->next_same_i1)
707 if (INSN_UID (p->i2) < maxuid)
710 pprev = &p->next_same_i1;
715 delay_htab->clear_slot (pslot);
721 /* Discard all delay pairs which involve an insn with an UID higher
724 discard_delay_pairs_above (int max_uid)
726 delay_htab->traverse <int *, haifa_htab_i1_traverse> (&max_uid);
727 delay_htab_i2->traverse <int *, haifa_htab_i2_traverse> (&max_uid);
730 /* This function can be called by a port just before it starts the final
731 scheduling pass. It records the fact that an instruction with delay
732 slots has been split into two insns, I1 and I2. The first one will be
733 scheduled normally and initiates the operation. The second one is a
734 shadow which must follow a specific number of cycles after I1; its only
735 purpose is to show the side effect that occurs at that cycle in the RTL.
736 If a JUMP_INSN or a CALL_INSN has been split, I1 should be a normal INSN,
737 while I2 retains the original insn type.
739 There are two ways in which the number of cycles can be specified,
740 involving the CYCLES and STAGES arguments to this function. If STAGES
741 is zero, we just use the value of CYCLES. Otherwise, STAGES is a factor
742 which is multiplied by MODULO_II to give the number of cycles. This is
743 only useful if the caller also calls set_modulo_params to enable modulo
747 record_delay_slot_pair (rtx_insn *i1, rtx_insn *i2, int cycles, int stages)
749 struct delay_pair *p = XNEW (struct delay_pair);
750 struct delay_pair **slot;
759 delay_htab = new hash_table<delay_i1_hasher> (10);
760 delay_htab_i2 = new hash_table<delay_i2_hasher> (10);
762 slot = delay_htab->find_slot_with_hash (i1, htab_hash_pointer (i1), INSERT);
763 p->next_same_i1 = *slot;
765 slot = delay_htab_i2->find_slot (p, INSERT);
769 /* Examine the delay pair hashtable to see if INSN is a shadow for another,
770 and return the other insn if so. Return NULL otherwise. */
772 real_insn_for_shadow (rtx_insn *insn)
774 struct delay_pair *pair;
779 pair = delay_htab_i2->find_with_hash (insn, htab_hash_pointer (insn));
780 if (!pair || pair->stages > 0)
785 /* For a pair P of insns, return the fixed distance in cycles from the first
786 insn after which the second must be scheduled. */
788 pair_delay (struct delay_pair *p)
793 return p->stages * modulo_ii;
796 /* Given an insn INSN, add a dependence on its delayed shadow if it
797 has one. Also try to find situations where shadows depend on each other
798 and add dependencies to the real insns to limit the amount of backtracking
801 add_delay_dependencies (rtx_insn *insn)
803 struct delay_pair *pair;
804 sd_iterator_def sd_it;
810 pair = delay_htab_i2->find_with_hash (insn, htab_hash_pointer (insn));
813 add_dependence (insn, pair->i1, REG_DEP_ANTI);
817 FOR_EACH_DEP (pair->i2, SD_LIST_BACK, sd_it, dep)
819 rtx_insn *pro = DEP_PRO (dep);
820 struct delay_pair *other_pair
821 = delay_htab_i2->find_with_hash (pro, htab_hash_pointer (pro));
822 if (!other_pair || other_pair->stages)
824 if (pair_delay (other_pair) >= pair_delay (pair))
826 if (sched_verbose >= 4)
828 fprintf (sched_dump, ";;\tadding dependence %d <- %d\n",
829 INSN_UID (other_pair->i1),
830 INSN_UID (pair->i1));
831 fprintf (sched_dump, ";;\tpair1 %d <- %d, cost %d\n",
835 fprintf (sched_dump, ";;\tpair2 %d <- %d, cost %d\n",
836 INSN_UID (other_pair->i1),
837 INSN_UID (other_pair->i2),
838 pair_delay (other_pair));
840 add_dependence (pair->i1, other_pair->i1, REG_DEP_ANTI);
845 /* Forward declarations. */
847 static int priority (rtx_insn *);
848 static int autopref_rank_for_schedule (const rtx_insn *, const rtx_insn *);
849 static int rank_for_schedule (const void *, const void *);
850 static void swap_sort (rtx_insn **, int);
851 static void queue_insn (rtx_insn *, int, const char *);
852 static int schedule_insn (rtx_insn *);
853 static void adjust_priority (rtx_insn *);
854 static void advance_one_cycle (void);
855 static void extend_h_i_d (void);
858 /* Notes handling mechanism:
859 =========================
860 Generally, NOTES are saved before scheduling and restored after scheduling.
861 The scheduler distinguishes between two types of notes:
863 (1) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
864 Before scheduling a region, a pointer to the note is added to the insn
865 that follows or precedes it. (This happens as part of the data dependence
866 computation). After scheduling an insn, the pointer contained in it is
867 used for regenerating the corresponding note (in reemit_notes).
869 (2) All other notes (e.g. INSN_DELETED): Before scheduling a block,
870 these notes are put in a list (in rm_other_notes() and
871 unlink_other_notes ()). After scheduling the block, these notes are
872 inserted at the beginning of the block (in schedule_block()). */
874 static void ready_add (struct ready_list *, rtx_insn *, bool);
875 static rtx_insn *ready_remove_first (struct ready_list *);
876 static rtx_insn *ready_remove_first_dispatch (struct ready_list *ready);
878 static void queue_to_ready (struct ready_list *);
879 static int early_queue_to_ready (state_t, struct ready_list *);
881 /* The following functions are used to implement multi-pass scheduling
882 on the first cycle. */
883 static rtx_insn *ready_remove (struct ready_list *, int);
884 static void ready_remove_insn (rtx);
886 static void fix_inter_tick (rtx_insn *, rtx_insn *);
887 static int fix_tick_ready (rtx_insn *);
888 static void change_queue_index (rtx_insn *, int);
890 /* The following functions are used to implement scheduling of data/control
891 speculative instructions. */
893 static void extend_h_i_d (void);
894 static void init_h_i_d (rtx_insn *);
895 static int haifa_speculate_insn (rtx_insn *, ds_t, rtx *);
896 static void generate_recovery_code (rtx_insn *);
897 static void process_insn_forw_deps_be_in_spec (rtx, rtx_insn *, ds_t);
898 static void begin_speculative_block (rtx_insn *);
899 static void add_to_speculative_block (rtx_insn *);
900 static void init_before_recovery (basic_block *);
901 static void create_check_block_twin (rtx_insn *, bool);
902 static void fix_recovery_deps (basic_block);
903 static bool haifa_change_pattern (rtx_insn *, rtx);
904 static void dump_new_block_header (int, basic_block, rtx_insn *, rtx_insn *);
905 static void restore_bb_notes (basic_block);
906 static void fix_jump_move (rtx_insn *);
907 static void move_block_after_check (rtx_insn *);
908 static void move_succs (vec<edge, va_gc> **, basic_block);
909 static void sched_remove_insn (rtx_insn *);
910 static void clear_priorities (rtx_insn *, rtx_vec_t *);
911 static void calc_priorities (rtx_vec_t);
912 static void add_jump_dependencies (rtx_insn *, rtx_insn *);
914 #endif /* INSN_SCHEDULING */
916 /* Point to state used for the current scheduling pass. */
917 struct haifa_sched_info *current_sched_info;
919 #ifndef INSN_SCHEDULING
921 schedule_insns (void)
926 /* Do register pressure sensitive insn scheduling if the flag is set
928 enum sched_pressure_algorithm sched_pressure;
930 /* Map regno -> its pressure class. The map defined only when
931 SCHED_PRESSURE != SCHED_PRESSURE_NONE. */
932 enum reg_class *sched_regno_pressure_class;
934 /* The current register pressure. Only elements corresponding pressure
935 classes are defined. */
936 static int curr_reg_pressure[N_REG_CLASSES];
938 /* Saved value of the previous array. */
939 static int saved_reg_pressure[N_REG_CLASSES];
941 /* Register living at given scheduling point. */
942 static bitmap curr_reg_live;
944 /* Saved value of the previous array. */
945 static bitmap saved_reg_live;
947 /* Registers mentioned in the current region. */
948 static bitmap region_ref_regs;
950 /* Effective number of available registers of a given class (see comment
951 in sched_pressure_start_bb). */
952 static int sched_class_regs_num[N_REG_CLASSES];
953 /* Number of call_used_regs. This is a helper for calculating of
954 sched_class_regs_num. */
955 static int call_used_regs_num[N_REG_CLASSES];
957 /* Initiate register pressure relative info for scheduling the current
958 region. Currently it is only clearing register mentioned in the
961 sched_init_region_reg_pressure_info (void)
963 bitmap_clear (region_ref_regs);
966 /* PRESSURE[CL] describes the pressure on register class CL. Update it
967 for the birth (if BIRTH_P) or death (if !BIRTH_P) of register REGNO.
968 LIVE tracks the set of live registers; if it is null, assume that
969 every birth or death is genuine. */
971 mark_regno_birth_or_death (bitmap live, int *pressure, int regno, bool birth_p)
973 enum reg_class pressure_class;
975 pressure_class = sched_regno_pressure_class[regno];
976 if (regno >= FIRST_PSEUDO_REGISTER)
978 if (pressure_class != NO_REGS)
982 if (!live || bitmap_set_bit (live, regno))
983 pressure[pressure_class]
984 += (ira_reg_class_max_nregs
985 [pressure_class][PSEUDO_REGNO_MODE (regno)]);
989 if (!live || bitmap_clear_bit (live, regno))
990 pressure[pressure_class]
991 -= (ira_reg_class_max_nregs
992 [pressure_class][PSEUDO_REGNO_MODE (regno)]);
996 else if (pressure_class != NO_REGS
997 && ! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
1001 if (!live || bitmap_set_bit (live, regno))
1002 pressure[pressure_class]++;
1006 if (!live || bitmap_clear_bit (live, regno))
1007 pressure[pressure_class]--;
1012 /* Initiate current register pressure related info from living
1013 registers given by LIVE. */
1015 initiate_reg_pressure_info (bitmap live)
1021 for (i = 0; i < ira_pressure_classes_num; i++)
1022 curr_reg_pressure[ira_pressure_classes[i]] = 0;
1023 bitmap_clear (curr_reg_live);
1024 EXECUTE_IF_SET_IN_BITMAP (live, 0, j, bi)
1025 if (sched_pressure == SCHED_PRESSURE_MODEL
1026 || current_nr_blocks == 1
1027 || bitmap_bit_p (region_ref_regs, j))
1028 mark_regno_birth_or_death (curr_reg_live, curr_reg_pressure, j, true);
1031 /* Mark registers in X as mentioned in the current region. */
1033 setup_ref_regs (rtx x)
1036 const RTX_CODE code = GET_CODE (x);
1042 if (HARD_REGISTER_NUM_P (regno))
1043 bitmap_set_range (region_ref_regs, regno,
1044 hard_regno_nregs[regno][GET_MODE (x)]);
1046 bitmap_set_bit (region_ref_regs, REGNO (x));
1049 fmt = GET_RTX_FORMAT (code);
1050 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1052 setup_ref_regs (XEXP (x, i));
1053 else if (fmt[i] == 'E')
1055 for (j = 0; j < XVECLEN (x, i); j++)
1056 setup_ref_regs (XVECEXP (x, i, j));
1060 /* Initiate current register pressure related info at the start of
1063 initiate_bb_reg_pressure_info (basic_block bb)
1065 unsigned int i ATTRIBUTE_UNUSED;
1068 if (current_nr_blocks > 1)
1069 FOR_BB_INSNS (bb, insn)
1070 if (NONDEBUG_INSN_P (insn))
1071 setup_ref_regs (PATTERN (insn));
1072 initiate_reg_pressure_info (df_get_live_in (bb));
1073 if (bb_has_eh_pred (bb))
1076 unsigned int regno = EH_RETURN_DATA_REGNO (i);
1078 if (regno == INVALID_REGNUM)
1080 if (! bitmap_bit_p (df_get_live_in (bb), regno))
1081 mark_regno_birth_or_death (curr_reg_live, curr_reg_pressure,
1086 /* Save current register pressure related info. */
1088 save_reg_pressure (void)
1092 for (i = 0; i < ira_pressure_classes_num; i++)
1093 saved_reg_pressure[ira_pressure_classes[i]]
1094 = curr_reg_pressure[ira_pressure_classes[i]];
1095 bitmap_copy (saved_reg_live, curr_reg_live);
1098 /* Restore saved register pressure related info. */
1100 restore_reg_pressure (void)
1104 for (i = 0; i < ira_pressure_classes_num; i++)
1105 curr_reg_pressure[ira_pressure_classes[i]]
1106 = saved_reg_pressure[ira_pressure_classes[i]];
1107 bitmap_copy (curr_reg_live, saved_reg_live);
1110 /* Return TRUE if the register is dying after its USE. */
1112 dying_use_p (struct reg_use_data *use)
1114 struct reg_use_data *next;
1116 for (next = use->next_regno_use; next != use; next = next->next_regno_use)
1117 if (NONDEBUG_INSN_P (next->insn)
1118 && QUEUE_INDEX (next->insn) != QUEUE_SCHEDULED)
1123 /* Print info about the current register pressure and its excess for
1124 each pressure class. */
1126 print_curr_reg_pressure (void)
1131 fprintf (sched_dump, ";;\t");
1132 for (i = 0; i < ira_pressure_classes_num; i++)
1134 cl = ira_pressure_classes[i];
1135 gcc_assert (curr_reg_pressure[cl] >= 0);
1136 fprintf (sched_dump, " %s:%d(%d)", reg_class_names[cl],
1137 curr_reg_pressure[cl],
1138 curr_reg_pressure[cl] - sched_class_regs_num[cl]);
1140 fprintf (sched_dump, "\n");
1143 /* Determine if INSN has a condition that is clobbered if a register
1144 in SET_REGS is modified. */
1146 cond_clobbered_p (rtx_insn *insn, HARD_REG_SET set_regs)
1148 rtx pat = PATTERN (insn);
1149 gcc_assert (GET_CODE (pat) == COND_EXEC);
1150 if (TEST_HARD_REG_BIT (set_regs, REGNO (XEXP (COND_EXEC_TEST (pat), 0))))
1152 sd_iterator_def sd_it;
1154 haifa_change_pattern (insn, ORIG_PAT (insn));
1155 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
1156 DEP_STATUS (dep) &= ~DEP_CANCELLED;
1157 TODO_SPEC (insn) = HARD_DEP;
1158 if (sched_verbose >= 2)
1159 fprintf (sched_dump,
1160 ";;\t\tdequeue insn %s because of clobbered condition\n",
1161 (*current_sched_info->print_insn) (insn, 0));
1168 /* This function should be called after modifying the pattern of INSN,
1169 to update scheduler data structures as needed. */
1171 update_insn_after_change (rtx_insn *insn)
1173 sd_iterator_def sd_it;
1176 dfa_clear_single_insn_cache (insn);
1178 sd_it = sd_iterator_start (insn,
1179 SD_LIST_FORW | SD_LIST_BACK | SD_LIST_RES_BACK);
1180 while (sd_iterator_cond (&sd_it, &dep))
1182 DEP_COST (dep) = UNKNOWN_DEP_COST;
1183 sd_iterator_next (&sd_it);
1186 /* Invalidate INSN_COST, so it'll be recalculated. */
1187 INSN_COST (insn) = -1;
1188 /* Invalidate INSN_TICK, so it'll be recalculated. */
1189 INSN_TICK (insn) = INVALID_TICK;
1191 /* Invalidate autoprefetch data entry. */
1192 INSN_AUTOPREF_MULTIPASS_DATA (insn)[0].status
1193 = AUTOPREF_MULTIPASS_DATA_UNINITIALIZED;
1194 INSN_AUTOPREF_MULTIPASS_DATA (insn)[1].status
1195 = AUTOPREF_MULTIPASS_DATA_UNINITIALIZED;
1199 /* Two VECs, one to hold dependencies for which pattern replacements
1200 need to be applied or restored at the start of the next cycle, and
1201 another to hold an integer that is either one, to apply the
1202 corresponding replacement, or zero to restore it. */
1203 static vec<dep_t> next_cycle_replace_deps;
1204 static vec<int> next_cycle_apply;
1206 static void apply_replacement (dep_t, bool);
1207 static void restore_pattern (dep_t, bool);
1209 /* Look at the remaining dependencies for insn NEXT, and compute and return
1210 the TODO_SPEC value we should use for it. This is called after one of
1211 NEXT's dependencies has been resolved.
1212 We also perform pattern replacements for predication, and for broken
1213 replacement dependencies. The latter is only done if FOR_BACKTRACK is
1217 recompute_todo_spec (rtx_insn *next, bool for_backtrack)
1220 sd_iterator_def sd_it;
1221 dep_t dep, modify_dep = NULL;
1225 bool first_p = true;
1227 if (sd_lists_empty_p (next, SD_LIST_BACK))
1228 /* NEXT has all its dependencies resolved. */
1231 if (!sd_lists_empty_p (next, SD_LIST_HARD_BACK))
1234 /* If NEXT is intended to sit adjacent to this instruction, we don't
1235 want to try to break any dependencies. Treat it as a HARD_DEP. */
1236 if (SCHED_GROUP_P (next))
1239 /* Now we've got NEXT with speculative deps only.
1240 1. Look at the deps to see what we have to do.
1241 2. Check if we can do 'todo'. */
1244 FOR_EACH_DEP (next, SD_LIST_BACK, sd_it, dep)
1246 rtx_insn *pro = DEP_PRO (dep);
1247 ds_t ds = DEP_STATUS (dep) & SPECULATIVE;
1249 if (DEBUG_INSN_P (pro) && !DEBUG_INSN_P (next))
1262 new_ds = ds_merge (new_ds, ds);
1264 else if (DEP_TYPE (dep) == REG_DEP_CONTROL)
1266 if (QUEUE_INDEX (pro) != QUEUE_SCHEDULED)
1271 DEP_STATUS (dep) &= ~DEP_CANCELLED;
1273 else if (DEP_REPLACE (dep) != NULL)
1275 if (QUEUE_INDEX (pro) != QUEUE_SCHEDULED)
1280 DEP_STATUS (dep) &= ~DEP_CANCELLED;
1284 if (n_replace > 0 && n_control == 0 && n_spec == 0)
1286 if (!dbg_cnt (sched_breakdep))
1288 FOR_EACH_DEP (next, SD_LIST_BACK, sd_it, dep)
1290 struct dep_replacement *desc = DEP_REPLACE (dep);
1293 if (desc->insn == next && !for_backtrack)
1295 gcc_assert (n_replace == 1);
1296 apply_replacement (dep, true);
1298 DEP_STATUS (dep) |= DEP_CANCELLED;
1304 else if (n_control == 1 && n_replace == 0 && n_spec == 0)
1306 rtx_insn *pro, *other;
1308 rtx cond = NULL_RTX;
1310 rtx_insn *prev = NULL;
1314 if ((current_sched_info->flags & DO_PREDICATION) == 0
1315 || (ORIG_PAT (next) != NULL_RTX
1316 && PREDICATED_PAT (next) == NULL_RTX))
1319 pro = DEP_PRO (modify_dep);
1320 other = real_insn_for_shadow (pro);
1321 if (other != NULL_RTX)
1324 cond = sched_get_reverse_condition_uncached (pro);
1325 regno = REGNO (XEXP (cond, 0));
1327 /* Find the last scheduled insn that modifies the condition register.
1328 We can stop looking once we find the insn we depend on through the
1329 REG_DEP_CONTROL; if the condition register isn't modified after it,
1330 we know that it still has the right value. */
1331 if (QUEUE_INDEX (pro) == QUEUE_SCHEDULED)
1332 FOR_EACH_VEC_ELT_REVERSE (scheduled_insns, i, prev)
1336 find_all_hard_reg_sets (prev, &t, true);
1337 if (TEST_HARD_REG_BIT (t, regno))
1342 if (ORIG_PAT (next) == NULL_RTX)
1344 ORIG_PAT (next) = PATTERN (next);
1346 new_pat = gen_rtx_COND_EXEC (VOIDmode, cond, PATTERN (next));
1347 success = haifa_change_pattern (next, new_pat);
1350 PREDICATED_PAT (next) = new_pat;
1352 else if (PATTERN (next) != PREDICATED_PAT (next))
1354 bool success = haifa_change_pattern (next,
1355 PREDICATED_PAT (next));
1356 gcc_assert (success);
1358 DEP_STATUS (modify_dep) |= DEP_CANCELLED;
1362 if (PREDICATED_PAT (next) != NULL_RTX)
1364 int tick = INSN_TICK (next);
1365 bool success = haifa_change_pattern (next,
1367 INSN_TICK (next) = tick;
1368 gcc_assert (success);
1371 /* We can't handle the case where there are both speculative and control
1372 dependencies, so we return HARD_DEP in such a case. Also fail if
1373 we have speculative dependencies with not enough points, or more than
1374 one control dependency. */
1375 if ((n_spec > 0 && (n_control > 0 || n_replace > 0))
1377 /* Too few points? */
1378 && ds_weak (new_ds) < spec_info->data_weakness_cutoff)
1386 /* Pointer to the last instruction scheduled. */
1387 static rtx_insn *last_scheduled_insn;
1389 /* Pointer to the last nondebug instruction scheduled within the
1390 block, or the prev_head of the scheduling block. Used by
1391 rank_for_schedule, so that insns independent of the last scheduled
1392 insn will be preferred over dependent instructions. */
1393 static rtx last_nondebug_scheduled_insn;
1395 /* Pointer that iterates through the list of unscheduled insns if we
1396 have a dbg_cnt enabled. It always points at an insn prior to the
1397 first unscheduled one. */
1398 static rtx_insn *nonscheduled_insns_begin;
1400 /* Compute cost of executing INSN.
1401 This is the number of cycles between instruction issue and
1402 instruction results. */
1404 insn_cost (rtx_insn *insn)
1413 if (recog_memoized (insn) < 0)
1416 cost = insn_default_latency (insn);
1423 cost = INSN_COST (insn);
1427 /* A USE insn, or something else we don't need to
1428 understand. We can't pass these directly to
1429 result_ready_cost or insn_default_latency because it will
1430 trigger a fatal error for unrecognizable insns. */
1431 if (recog_memoized (insn) < 0)
1433 INSN_COST (insn) = 0;
1438 cost = insn_default_latency (insn);
1442 INSN_COST (insn) = cost;
1449 /* Compute cost of dependence LINK.
1450 This is the number of cycles between instruction issue and
1451 instruction results.
1452 ??? We also use this function to call recog_memoized on all insns. */
1454 dep_cost_1 (dep_t link, dw_t dw)
1456 rtx_insn *insn = DEP_PRO (link);
1457 rtx_insn *used = DEP_CON (link);
1460 if (DEP_COST (link) != UNKNOWN_DEP_COST)
1461 return DEP_COST (link);
1465 struct delay_pair *delay_entry;
1467 = delay_htab_i2->find_with_hash (used, htab_hash_pointer (used));
1470 if (delay_entry->i1 == insn)
1472 DEP_COST (link) = pair_delay (delay_entry);
1473 return DEP_COST (link);
1478 /* A USE insn should never require the value used to be computed.
1479 This allows the computation of a function's result and parameter
1480 values to overlap the return and call. We don't care about the
1481 dependence cost when only decreasing register pressure. */
1482 if (recog_memoized (used) < 0)
1485 recog_memoized (insn);
1489 enum reg_note dep_type = DEP_TYPE (link);
1491 cost = insn_cost (insn);
1493 if (INSN_CODE (insn) >= 0)
1495 if (dep_type == REG_DEP_ANTI)
1497 else if (dep_type == REG_DEP_OUTPUT)
1499 cost = (insn_default_latency (insn)
1500 - insn_default_latency (used));
1504 else if (bypass_p (insn))
1505 cost = insn_latency (insn, used);
1509 if (targetm.sched.adjust_cost_2)
1510 cost = targetm.sched.adjust_cost_2 (used, (int) dep_type, insn, cost,
1512 else if (targetm.sched.adjust_cost != NULL)
1514 /* This variable is used for backward compatibility with the
1516 rtx_insn_list *dep_cost_rtx_link =
1517 alloc_INSN_LIST (NULL_RTX, NULL);
1519 /* Make it self-cycled, so that if some tries to walk over this
1520 incomplete list he/she will be caught in an endless loop. */
1521 XEXP (dep_cost_rtx_link, 1) = dep_cost_rtx_link;
1523 /* Targets use only REG_NOTE_KIND of the link. */
1524 PUT_REG_NOTE_KIND (dep_cost_rtx_link, DEP_TYPE (link));
1526 cost = targetm.sched.adjust_cost (used, dep_cost_rtx_link,
1529 free_INSN_LIST_node (dep_cost_rtx_link);
1536 DEP_COST (link) = cost;
1540 /* Compute cost of dependence LINK.
1541 This is the number of cycles between instruction issue and
1542 instruction results. */
1544 dep_cost (dep_t link)
1546 return dep_cost_1 (link, 0);
1549 /* Use this sel-sched.c friendly function in reorder2 instead of increasing
1550 INSN_PRIORITY explicitly. */
1552 increase_insn_priority (rtx_insn *insn, int amount)
1554 if (!sel_sched_p ())
1556 /* We're dealing with haifa-sched.c INSN_PRIORITY. */
1557 if (INSN_PRIORITY_KNOWN (insn))
1558 INSN_PRIORITY (insn) += amount;
1562 /* In sel-sched.c INSN_PRIORITY is not kept up to date.
1563 Use EXPR_PRIORITY instead. */
1564 sel_add_to_insn_priority (insn, amount);
1568 /* Return 'true' if DEP should be included in priority calculations. */
1570 contributes_to_priority_p (dep_t dep)
1572 if (DEBUG_INSN_P (DEP_CON (dep))
1573 || DEBUG_INSN_P (DEP_PRO (dep)))
1576 /* Critical path is meaningful in block boundaries only. */
1577 if (!current_sched_info->contributes_to_priority (DEP_CON (dep),
1581 if (DEP_REPLACE (dep) != NULL)
1584 /* If flag COUNT_SPEC_IN_CRITICAL_PATH is set,
1585 then speculative instructions will less likely be
1586 scheduled. That is because the priority of
1587 their producers will increase, and, thus, the
1588 producers will more likely be scheduled, thus,
1589 resolving the dependence. */
1590 if (sched_deps_info->generate_spec_deps
1591 && !(spec_info->flags & COUNT_SPEC_IN_CRITICAL_PATH)
1592 && (DEP_STATUS (dep) & SPECULATIVE))
1598 /* Compute the number of nondebug deps in list LIST for INSN. */
1601 dep_list_size (rtx insn, sd_list_types_def list)
1603 sd_iterator_def sd_it;
1605 int dbgcount = 0, nodbgcount = 0;
1607 if (!MAY_HAVE_DEBUG_INSNS)
1608 return sd_lists_size (insn, list);
1610 FOR_EACH_DEP (insn, list, sd_it, dep)
1612 if (DEBUG_INSN_P (DEP_CON (dep)))
1614 else if (!DEBUG_INSN_P (DEP_PRO (dep)))
1618 gcc_assert (dbgcount + nodbgcount == sd_lists_size (insn, list));
1625 /* Compute the priority number for INSN. */
1627 priority (rtx_insn *insn)
1629 if (! INSN_P (insn))
1632 /* We should not be interested in priority of an already scheduled insn. */
1633 gcc_assert (QUEUE_INDEX (insn) != QUEUE_SCHEDULED);
1635 if (!INSN_PRIORITY_KNOWN (insn))
1637 int this_priority = -1;
1641 int this_fusion_priority;
1643 targetm.sched.fusion_priority (insn, FUSION_MAX_PRIORITY,
1644 &this_fusion_priority, &this_priority);
1645 INSN_FUSION_PRIORITY (insn) = this_fusion_priority;
1647 else if (dep_list_size (insn, SD_LIST_FORW) == 0)
1648 /* ??? We should set INSN_PRIORITY to insn_cost when and insn has
1649 some forward deps but all of them are ignored by
1650 contributes_to_priority hook. At the moment we set priority of
1652 this_priority = insn_cost (insn);
1655 rtx_insn *prev_first, *twin;
1658 /* For recovery check instructions we calculate priority slightly
1659 different than that of normal instructions. Instead of walking
1660 through INSN_FORW_DEPS (check) list, we walk through
1661 INSN_FORW_DEPS list of each instruction in the corresponding
1664 /* Selective scheduling does not define RECOVERY_BLOCK macro. */
1665 rec = sel_sched_p () ? NULL : RECOVERY_BLOCK (insn);
1666 if (!rec || rec == EXIT_BLOCK_PTR_FOR_FN (cfun))
1668 prev_first = PREV_INSN (insn);
1673 prev_first = NEXT_INSN (BB_HEAD (rec));
1674 twin = PREV_INSN (BB_END (rec));
1679 sd_iterator_def sd_it;
1682 FOR_EACH_DEP (twin, SD_LIST_FORW, sd_it, dep)
1687 next = DEP_CON (dep);
1689 if (BLOCK_FOR_INSN (next) != rec)
1693 if (!contributes_to_priority_p (dep))
1697 cost = dep_cost (dep);
1700 struct _dep _dep1, *dep1 = &_dep1;
1702 init_dep (dep1, insn, next, REG_DEP_ANTI);
1704 cost = dep_cost (dep1);
1707 next_priority = cost + priority (next);
1709 if (next_priority > this_priority)
1710 this_priority = next_priority;
1714 twin = PREV_INSN (twin);
1716 while (twin != prev_first);
1719 if (this_priority < 0)
1721 gcc_assert (this_priority == -1);
1723 this_priority = insn_cost (insn);
1726 INSN_PRIORITY (insn) = this_priority;
1727 INSN_PRIORITY_STATUS (insn) = 1;
1730 return INSN_PRIORITY (insn);
1733 /* Macros and functions for keeping the priority queue sorted, and
1734 dealing with queuing and dequeuing of instructions. */
1736 /* For each pressure class CL, set DEATH[CL] to the number of registers
1737 in that class that die in INSN. */
1740 calculate_reg_deaths (rtx_insn *insn, int *death)
1743 struct reg_use_data *use;
1745 for (i = 0; i < ira_pressure_classes_num; i++)
1746 death[ira_pressure_classes[i]] = 0;
1747 for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
1748 if (dying_use_p (use))
1749 mark_regno_birth_or_death (0, death, use->regno, true);
1752 /* Setup info about the current register pressure impact of scheduling
1753 INSN at the current scheduling point. */
1755 setup_insn_reg_pressure_info (rtx_insn *insn)
1757 int i, change, before, after, hard_regno;
1758 int excess_cost_change;
1761 struct reg_pressure_data *pressure_info;
1762 int *max_reg_pressure;
1763 static int death[N_REG_CLASSES];
1765 gcc_checking_assert (!DEBUG_INSN_P (insn));
1767 excess_cost_change = 0;
1768 calculate_reg_deaths (insn, death);
1769 pressure_info = INSN_REG_PRESSURE (insn);
1770 max_reg_pressure = INSN_MAX_REG_PRESSURE (insn);
1771 gcc_assert (pressure_info != NULL && max_reg_pressure != NULL);
1772 for (i = 0; i < ira_pressure_classes_num; i++)
1774 cl = ira_pressure_classes[i];
1775 gcc_assert (curr_reg_pressure[cl] >= 0);
1776 change = (int) pressure_info[i].set_increase - death[cl];
1777 before = MAX (0, max_reg_pressure[i] - sched_class_regs_num[cl]);
1778 after = MAX (0, max_reg_pressure[i] + change
1779 - sched_class_regs_num[cl]);
1780 hard_regno = ira_class_hard_regs[cl][0];
1781 gcc_assert (hard_regno >= 0);
1782 mode = reg_raw_mode[hard_regno];
1783 excess_cost_change += ((after - before)
1784 * (ira_memory_move_cost[mode][cl][0]
1785 + ira_memory_move_cost[mode][cl][1]));
1787 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insn) = excess_cost_change;
1790 /* This is the first page of code related to SCHED_PRESSURE_MODEL.
1791 It tries to make the scheduler take register pressure into account
1792 without introducing too many unnecessary stalls. It hooks into the
1793 main scheduling algorithm at several points:
1795 - Before scheduling starts, model_start_schedule constructs a
1796 "model schedule" for the current block. This model schedule is
1797 chosen solely to keep register pressure down. It does not take the
1798 target's pipeline or the original instruction order into account,
1799 except as a tie-breaker. It also doesn't work to a particular
1802 This model schedule gives us an idea of what pressure can be
1803 achieved for the block and gives us an example of a schedule that
1804 keeps to that pressure. It also makes the final schedule less
1805 dependent on the original instruction order. This is important
1806 because the original order can either be "wide" (many values live
1807 at once, such as in user-scheduled code) or "narrow" (few values
1808 live at once, such as after loop unrolling, where several
1809 iterations are executed sequentially).
1811 We do not apply this model schedule to the rtx stream. We simply
1812 record it in model_schedule. We also compute the maximum pressure,
1813 MP, that was seen during this schedule.
1815 - Instructions are added to the ready queue even if they require
1816 a stall. The length of the stall is instead computed as:
1818 MAX (INSN_TICK (INSN) - clock_var, 0)
1820 (= insn_delay). This allows rank_for_schedule to choose between
1821 introducing a deliberate stall or increasing pressure.
1823 - Before sorting the ready queue, model_set_excess_costs assigns
1824 a pressure-based cost to each ready instruction in the queue.
1825 This is the instruction's INSN_REG_PRESSURE_EXCESS_COST_CHANGE
1826 (ECC for short) and is effectively measured in cycles.
1828 - rank_for_schedule ranks instructions based on:
1830 ECC (insn) + insn_delay (insn)
1836 So, for example, an instruction X1 with an ECC of 1 that can issue
1837 now will win over an instruction X0 with an ECC of zero that would
1838 introduce a stall of one cycle. However, an instruction X2 with an
1839 ECC of 2 that can issue now will lose to both X0 and X1.
1841 - When an instruction is scheduled, model_recompute updates the model
1842 schedule with the new pressures (some of which might now exceed the
1843 original maximum pressure MP). model_update_limit_points then searches
1844 for the new point of maximum pressure, if not already known. */
1846 /* Used to separate high-verbosity debug information for SCHED_PRESSURE_MODEL
1847 from surrounding debug information. */
1849 ";;\t\t+------------------------------------------------------\n"
1851 /* Information about the pressure on a particular register class at a
1852 particular point of the model schedule. */
1853 struct model_pressure_data {
1854 /* The pressure at this point of the model schedule, or -1 if the
1855 point is associated with an instruction that has already been
1859 /* The maximum pressure during or after this point of the model schedule. */
1863 /* Per-instruction information that is used while building the model
1864 schedule. Here, "schedule" refers to the model schedule rather
1865 than the main schedule. */
1866 struct model_insn_info {
1867 /* The instruction itself. */
1870 /* If this instruction is in model_worklist, these fields link to the
1871 previous (higher-priority) and next (lower-priority) instructions
1873 struct model_insn_info *prev;
1874 struct model_insn_info *next;
1876 /* While constructing the schedule, QUEUE_INDEX describes whether an
1877 instruction has already been added to the schedule (QUEUE_SCHEDULED),
1878 is in model_worklist (QUEUE_READY), or neither (QUEUE_NOWHERE).
1879 old_queue records the value that QUEUE_INDEX had before scheduling
1880 started, so that we can restore it once the schedule is complete. */
1883 /* The relative importance of an unscheduled instruction. Higher
1884 values indicate greater importance. */
1885 unsigned int model_priority;
1887 /* The length of the longest path of satisfied true dependencies
1888 that leads to this instruction. */
1891 /* The length of the longest path of dependencies of any kind
1892 that leads from this instruction. */
1895 /* The number of predecessor nodes that must still be scheduled. */
1896 int unscheduled_preds;
1899 /* Information about the pressure limit for a particular register class.
1900 This structure is used when applying a model schedule to the main
1902 struct model_pressure_limit {
1903 /* The maximum register pressure seen in the original model schedule. */
1906 /* The maximum register pressure seen in the current model schedule
1907 (which excludes instructions that have already been scheduled). */
1910 /* The point of the current model schedule at which PRESSURE is first
1911 reached. It is set to -1 if the value needs to be recomputed. */
1915 /* Describes a particular way of measuring register pressure. */
1916 struct model_pressure_group {
1917 /* Index PCI describes the maximum pressure on ira_pressure_classes[PCI]. */
1918 struct model_pressure_limit limits[N_REG_CLASSES];
1920 /* Index (POINT * ira_num_pressure_classes + PCI) describes the pressure
1921 on register class ira_pressure_classes[PCI] at point POINT of the
1922 current model schedule. A POINT of model_num_insns describes the
1923 pressure at the end of the schedule. */
1924 struct model_pressure_data *model;
1927 /* Index POINT gives the instruction at point POINT of the model schedule.
1928 This array doesn't change during main scheduling. */
1929 static vec<rtx_insn *> model_schedule;
1931 /* The list of instructions in the model worklist, sorted in order of
1932 decreasing priority. */
1933 static struct model_insn_info *model_worklist;
1935 /* Index I describes the instruction with INSN_LUID I. */
1936 static struct model_insn_info *model_insns;
1938 /* The number of instructions in the model schedule. */
1939 static int model_num_insns;
1941 /* The index of the first instruction in model_schedule that hasn't yet been
1942 added to the main schedule, or model_num_insns if all of them have. */
1943 static int model_curr_point;
1945 /* Describes the pressure before each instruction in the model schedule. */
1946 static struct model_pressure_group model_before_pressure;
1948 /* The first unused model_priority value (as used in model_insn_info). */
1949 static unsigned int model_next_priority;
1952 /* The model_pressure_data for ira_pressure_classes[PCI] in GROUP
1953 at point POINT of the model schedule. */
1954 #define MODEL_PRESSURE_DATA(GROUP, POINT, PCI) \
1955 (&(GROUP)->model[(POINT) * ira_pressure_classes_num + (PCI)])
1957 /* The maximum pressure on ira_pressure_classes[PCI] in GROUP at or
1958 after point POINT of the model schedule. */
1959 #define MODEL_MAX_PRESSURE(GROUP, POINT, PCI) \
1960 (MODEL_PRESSURE_DATA (GROUP, POINT, PCI)->max_pressure)
1962 /* The pressure on ira_pressure_classes[PCI] in GROUP at point POINT
1963 of the model schedule. */
1964 #define MODEL_REF_PRESSURE(GROUP, POINT, PCI) \
1965 (MODEL_PRESSURE_DATA (GROUP, POINT, PCI)->ref_pressure)
1967 /* Information about INSN that is used when creating the model schedule. */
1968 #define MODEL_INSN_INFO(INSN) \
1969 (&model_insns[INSN_LUID (INSN)])
1971 /* The instruction at point POINT of the model schedule. */
1972 #define MODEL_INSN(POINT) \
1973 (model_schedule[POINT])
1976 /* Return INSN's index in the model schedule, or model_num_insns if it
1977 doesn't belong to that schedule. */
1980 model_index (rtx_insn *insn)
1982 if (INSN_MODEL_INDEX (insn) == 0)
1983 return model_num_insns;
1984 return INSN_MODEL_INDEX (insn) - 1;
1987 /* Make sure that GROUP->limits is up-to-date for the current point
1988 of the model schedule. */
1991 model_update_limit_points_in_group (struct model_pressure_group *group)
1993 int pci, max_pressure, point;
1995 for (pci = 0; pci < ira_pressure_classes_num; pci++)
1997 /* We may have passed the final point at which the pressure in
1998 group->limits[pci].pressure was reached. Update the limit if so. */
1999 max_pressure = MODEL_MAX_PRESSURE (group, model_curr_point, pci);
2000 group->limits[pci].pressure = max_pressure;
2002 /* Find the point at which MAX_PRESSURE is first reached. We need
2003 to search in three cases:
2005 - We've already moved past the previous pressure point.
2006 In this case we search forward from model_curr_point.
2008 - We scheduled the previous point of maximum pressure ahead of
2009 its position in the model schedule, but doing so didn't bring
2010 the pressure point earlier. In this case we search forward
2011 from that previous pressure point.
2013 - Scheduling an instruction early caused the maximum pressure
2014 to decrease. In this case we will have set the pressure
2015 point to -1, and we search forward from model_curr_point. */
2016 point = MAX (group->limits[pci].point, model_curr_point);
2017 while (point < model_num_insns
2018 && MODEL_REF_PRESSURE (group, point, pci) < max_pressure)
2020 group->limits[pci].point = point;
2022 gcc_assert (MODEL_REF_PRESSURE (group, point, pci) == max_pressure);
2023 gcc_assert (MODEL_MAX_PRESSURE (group, point, pci) == max_pressure);
2027 /* Make sure that all register-pressure limits are up-to-date for the
2028 current position in the model schedule. */
2031 model_update_limit_points (void)
2033 model_update_limit_points_in_group (&model_before_pressure);
2036 /* Return the model_index of the last unscheduled use in chain USE
2037 outside of USE's instruction. Return -1 if there are no other uses,
2038 or model_num_insns if the register is live at the end of the block. */
2041 model_last_use_except (struct reg_use_data *use)
2043 struct reg_use_data *next;
2047 for (next = use->next_regno_use; next != use; next = next->next_regno_use)
2048 if (NONDEBUG_INSN_P (next->insn)
2049 && QUEUE_INDEX (next->insn) != QUEUE_SCHEDULED)
2051 index = model_index (next->insn);
2052 if (index == model_num_insns)
2053 return model_num_insns;
2060 /* An instruction with model_index POINT has just been scheduled, and it
2061 adds DELTA to the pressure on ira_pressure_classes[PCI] after POINT - 1.
2062 Update MODEL_REF_PRESSURE (GROUP, POINT, PCI) and
2063 MODEL_MAX_PRESSURE (GROUP, POINT, PCI) accordingly. */
2066 model_start_update_pressure (struct model_pressure_group *group,
2067 int point, int pci, int delta)
2069 int next_max_pressure;
2071 if (point == model_num_insns)
2073 /* The instruction wasn't part of the model schedule; it was moved
2074 from a different block. Update the pressure for the end of
2075 the model schedule. */
2076 MODEL_REF_PRESSURE (group, point, pci) += delta;
2077 MODEL_MAX_PRESSURE (group, point, pci) += delta;
2081 /* Record that this instruction has been scheduled. Nothing now
2082 changes between POINT and POINT + 1, so get the maximum pressure
2083 from the latter. If the maximum pressure decreases, the new
2084 pressure point may be before POINT. */
2085 MODEL_REF_PRESSURE (group, point, pci) = -1;
2086 next_max_pressure = MODEL_MAX_PRESSURE (group, point + 1, pci);
2087 if (MODEL_MAX_PRESSURE (group, point, pci) > next_max_pressure)
2089 MODEL_MAX_PRESSURE (group, point, pci) = next_max_pressure;
2090 if (group->limits[pci].point == point)
2091 group->limits[pci].point = -1;
2096 /* Record that scheduling a later instruction has changed the pressure
2097 at point POINT of the model schedule by DELTA (which might be 0).
2098 Update GROUP accordingly. Return nonzero if these changes might
2099 trigger changes to previous points as well. */
2102 model_update_pressure (struct model_pressure_group *group,
2103 int point, int pci, int delta)
2105 int ref_pressure, max_pressure, next_max_pressure;
2107 /* If POINT hasn't yet been scheduled, update its pressure. */
2108 ref_pressure = MODEL_REF_PRESSURE (group, point, pci);
2109 if (ref_pressure >= 0 && delta != 0)
2111 ref_pressure += delta;
2112 MODEL_REF_PRESSURE (group, point, pci) = ref_pressure;
2114 /* Check whether the maximum pressure in the overall schedule
2115 has increased. (This means that the MODEL_MAX_PRESSURE of
2116 every point <= POINT will need to increase too; see below.) */
2117 if (group->limits[pci].pressure < ref_pressure)
2118 group->limits[pci].pressure = ref_pressure;
2120 /* If we are at maximum pressure, and the maximum pressure
2121 point was previously unknown or later than POINT,
2122 bring it forward. */
2123 if (group->limits[pci].pressure == ref_pressure
2124 && !IN_RANGE (group->limits[pci].point, 0, point))
2125 group->limits[pci].point = point;
2127 /* If POINT used to be the point of maximum pressure, but isn't
2128 any longer, we need to recalculate it using a forward walk. */
2129 if (group->limits[pci].pressure > ref_pressure
2130 && group->limits[pci].point == point)
2131 group->limits[pci].point = -1;
2134 /* Update the maximum pressure at POINT. Changes here might also
2135 affect the maximum pressure at POINT - 1. */
2136 next_max_pressure = MODEL_MAX_PRESSURE (group, point + 1, pci);
2137 max_pressure = MAX (ref_pressure, next_max_pressure);
2138 if (MODEL_MAX_PRESSURE (group, point, pci) != max_pressure)
2140 MODEL_MAX_PRESSURE (group, point, pci) = max_pressure;
2146 /* INSN has just been scheduled. Update the model schedule accordingly. */
2149 model_recompute (rtx_insn *insn)
2154 } uses[FIRST_PSEUDO_REGISTER + MAX_RECOG_OPERANDS];
2155 struct reg_use_data *use;
2156 struct reg_pressure_data *reg_pressure;
2157 int delta[N_REG_CLASSES];
2158 int pci, point, mix, new_last, cl, ref_pressure, queue;
2159 unsigned int i, num_uses, num_pending_births;
2162 /* The destinations of INSN were previously live from POINT onwards, but are
2163 now live from model_curr_point onwards. Set up DELTA accordingly. */
2164 point = model_index (insn);
2165 reg_pressure = INSN_REG_PRESSURE (insn);
2166 for (pci = 0; pci < ira_pressure_classes_num; pci++)
2168 cl = ira_pressure_classes[pci];
2169 delta[cl] = reg_pressure[pci].set_increase;
2172 /* Record which registers previously died at POINT, but which now die
2173 before POINT. Adjust DELTA so that it represents the effect of
2174 this change after POINT - 1. Set NUM_PENDING_BIRTHS to the number of
2175 registers that will be born in the range [model_curr_point, POINT). */
2177 num_pending_births = 0;
2178 for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
2180 new_last = model_last_use_except (use);
2181 if (new_last < point)
2183 gcc_assert (num_uses < ARRAY_SIZE (uses));
2184 uses[num_uses].last_use = new_last;
2185 uses[num_uses].regno = use->regno;
2186 /* This register is no longer live after POINT - 1. */
2187 mark_regno_birth_or_death (NULL, delta, use->regno, false);
2190 num_pending_births++;
2194 /* Update the MODEL_REF_PRESSURE and MODEL_MAX_PRESSURE for POINT.
2195 Also set each group pressure limit for POINT. */
2196 for (pci = 0; pci < ira_pressure_classes_num; pci++)
2198 cl = ira_pressure_classes[pci];
2199 model_start_update_pressure (&model_before_pressure,
2200 point, pci, delta[cl]);
2203 /* Walk the model schedule backwards, starting immediately before POINT. */
2205 if (point != model_curr_point)
2209 insn = MODEL_INSN (point);
2210 queue = QUEUE_INDEX (insn);
2212 if (queue != QUEUE_SCHEDULED)
2214 /* DELTA describes the effect of the move on the register pressure
2215 after POINT. Make it describe the effect on the pressure
2218 while (i < num_uses)
2220 if (uses[i].last_use == point)
2222 /* This register is now live again. */
2223 mark_regno_birth_or_death (NULL, delta,
2224 uses[i].regno, true);
2226 /* Remove this use from the array. */
2227 uses[i] = uses[num_uses - 1];
2229 num_pending_births--;
2235 if (sched_verbose >= 5)
2239 fprintf (sched_dump, MODEL_BAR);
2240 fprintf (sched_dump, ";;\t\t| New pressure for model"
2242 fprintf (sched_dump, MODEL_BAR);
2246 fprintf (sched_dump, ";;\t\t| %3d %4d %-30s ",
2247 point, INSN_UID (insn),
2248 str_pattern_slim (PATTERN (insn)));
2249 for (pci = 0; pci < ira_pressure_classes_num; pci++)
2251 cl = ira_pressure_classes[pci];
2252 ref_pressure = MODEL_REF_PRESSURE (&model_before_pressure,
2254 fprintf (sched_dump, " %s:[%d->%d]",
2255 reg_class_names[ira_pressure_classes[pci]],
2256 ref_pressure, ref_pressure + delta[cl]);
2258 fprintf (sched_dump, "\n");
2262 /* Adjust the pressure at POINT. Set MIX to nonzero if POINT - 1
2263 might have changed as well. */
2264 mix = num_pending_births;
2265 for (pci = 0; pci < ira_pressure_classes_num; pci++)
2267 cl = ira_pressure_classes[pci];
2269 mix |= model_update_pressure (&model_before_pressure,
2270 point, pci, delta[cl]);
2273 while (mix && point > model_curr_point);
2276 fprintf (sched_dump, MODEL_BAR);
2279 /* After DEP, which was cancelled, has been resolved for insn NEXT,
2280 check whether the insn's pattern needs restoring. */
2282 must_restore_pattern_p (rtx_insn *next, dep_t dep)
2284 if (QUEUE_INDEX (next) == QUEUE_SCHEDULED)
2287 if (DEP_TYPE (dep) == REG_DEP_CONTROL)
2289 gcc_assert (ORIG_PAT (next) != NULL_RTX);
2290 gcc_assert (next == DEP_CON (dep));
2294 struct dep_replacement *desc = DEP_REPLACE (dep);
2295 if (desc->insn != next)
2297 gcc_assert (*desc->loc == desc->orig);
2304 /* model_spill_cost (CL, P, P') returns the cost of increasing the
2305 pressure on CL from P to P'. We use this to calculate a "base ECC",
2306 baseECC (CL, X), for each pressure class CL and each instruction X.
2307 Supposing X changes the pressure on CL from P to P', and that the
2308 maximum pressure on CL in the current model schedule is MP', then:
2310 * if X occurs before or at the next point of maximum pressure in
2311 the model schedule and P' > MP', then:
2313 baseECC (CL, X) = model_spill_cost (CL, MP, P')
2315 The idea is that the pressure after scheduling a fixed set of
2316 instructions -- in this case, the set up to and including the
2317 next maximum pressure point -- is going to be the same regardless
2318 of the order; we simply want to keep the intermediate pressure
2319 under control. Thus X has a cost of zero unless scheduling it
2320 now would exceed MP'.
2322 If all increases in the set are by the same amount, no zero-cost
2323 instruction will ever cause the pressure to exceed MP'. However,
2324 if X is instead moved past an instruction X' with pressure in the
2325 range (MP' - (P' - P), MP'), the pressure at X' will increase
2326 beyond MP'. Since baseECC is very much a heuristic anyway,
2327 it doesn't seem worth the overhead of tracking cases like these.
2329 The cost of exceeding MP' is always based on the original maximum
2330 pressure MP. This is so that going 2 registers over the original
2331 limit has the same cost regardless of whether it comes from two
2332 separate +1 deltas or from a single +2 delta.
2334 * if X occurs after the next point of maximum pressure in the model
2335 schedule and P' > P, then:
2337 baseECC (CL, X) = model_spill_cost (CL, MP, MP' + (P' - P))
2339 That is, if we move X forward across a point of maximum pressure,
2340 and if X increases the pressure by P' - P, then we conservatively
2341 assume that scheduling X next would increase the maximum pressure
2342 by P' - P. Again, the cost of doing this is based on the original
2343 maximum pressure MP, for the same reason as above.
2345 * if P' < P, P > MP, and X occurs at or after the next point of
2346 maximum pressure, then:
2348 baseECC (CL, X) = -model_spill_cost (CL, MAX (MP, P'), P)
2350 That is, if we have already exceeded the original maximum pressure MP,
2351 and if X might reduce the maximum pressure again -- or at least push
2352 it further back, and thus allow more scheduling freedom -- it is given
2353 a negative cost to reflect the improvement.
2359 In this case, X is not expected to affect the maximum pressure MP',
2360 so it has zero cost.
2362 We then create a combined value baseECC (X) that is the sum of
2363 baseECC (CL, X) for each pressure class CL.
2365 baseECC (X) could itself be used as the ECC value described above.
2366 However, this is often too conservative, in the sense that it
2367 tends to make high-priority instructions that increase pressure
2368 wait too long in cases where introducing a spill would be better.
2369 For this reason the final ECC is a priority-adjusted form of
2370 baseECC (X). Specifically, we calculate:
2372 P (X) = INSN_PRIORITY (X) - insn_delay (X) - baseECC (X)
2373 baseP = MAX { P (X) | baseECC (X) <= 0 }
2377 ECC (X) = MAX (MIN (baseP - P (X), baseECC (X)), 0)
2379 Thus an instruction's effect on pressure is ignored if it has a high
2380 enough priority relative to the ones that don't increase pressure.
2381 Negative values of baseECC (X) do not increase the priority of X
2382 itself, but they do make it harder for other instructions to
2383 increase the pressure further.
2385 This pressure cost is deliberately timid. The intention has been
2386 to choose a heuristic that rarely interferes with the normal list
2387 scheduler in cases where that scheduler would produce good code.
2388 We simply want to curb some of its worst excesses. */
2390 /* Return the cost of increasing the pressure in class CL from FROM to TO.
2392 Here we use the very simplistic cost model that every register above
2393 sched_class_regs_num[CL] has a spill cost of 1. We could use other
2394 measures instead, such as one based on MEMORY_MOVE_COST. However:
2396 (1) In order for an instruction to be scheduled, the higher cost
2397 would need to be justified in a single saving of that many stalls.
2398 This is overly pessimistic, because the benefit of spilling is
2399 often to avoid a sequence of several short stalls rather than
2402 (2) The cost is still arbitrary. Because we are not allocating
2403 registers during scheduling, we have no way of knowing for
2404 sure how many memory accesses will be required by each spill,
2405 where the spills will be placed within the block, or even
2406 which block(s) will contain the spills.
2408 So a higher cost than 1 is often too conservative in practice,
2409 forcing blocks to contain unnecessary stalls instead of spill code.
2410 The simple cost below seems to be the best compromise. It reduces
2411 the interference with the normal list scheduler, which helps make
2412 it more suitable for a default-on option. */
2415 model_spill_cost (int cl, int from, int to)
2417 from = MAX (from, sched_class_regs_num[cl]);
2418 return MAX (to, from) - from;
2421 /* Return baseECC (ira_pressure_classes[PCI], POINT), given that
2422 P = curr_reg_pressure[ira_pressure_classes[PCI]] and that
2426 model_excess_group_cost (struct model_pressure_group *group,
2427 int point, int pci, int delta)
2431 cl = ira_pressure_classes[pci];
2432 if (delta < 0 && point >= group->limits[pci].point)
2434 pressure = MAX (group->limits[pci].orig_pressure,
2435 curr_reg_pressure[cl] + delta);
2436 return -model_spill_cost (cl, pressure, curr_reg_pressure[cl]);
2441 if (point > group->limits[pci].point)
2442 pressure = group->limits[pci].pressure + delta;
2444 pressure = curr_reg_pressure[cl] + delta;
2446 if (pressure > group->limits[pci].pressure)
2447 return model_spill_cost (cl, group->limits[pci].orig_pressure,
2454 /* Return baseECC (MODEL_INSN (INSN)). Dump the costs to sched_dump
2458 model_excess_cost (rtx_insn *insn, bool print_p)
2460 int point, pci, cl, cost, this_cost, delta;
2461 struct reg_pressure_data *insn_reg_pressure;
2462 int insn_death[N_REG_CLASSES];
2464 calculate_reg_deaths (insn, insn_death);
2465 point = model_index (insn);
2466 insn_reg_pressure = INSN_REG_PRESSURE (insn);
2470 fprintf (sched_dump, ";;\t\t| %3d %4d | %4d %+3d |", point,
2471 INSN_UID (insn), INSN_PRIORITY (insn), insn_delay (insn));
2473 /* Sum up the individual costs for each register class. */
2474 for (pci = 0; pci < ira_pressure_classes_num; pci++)
2476 cl = ira_pressure_classes[pci];
2477 delta = insn_reg_pressure[pci].set_increase - insn_death[cl];
2478 this_cost = model_excess_group_cost (&model_before_pressure,
2482 fprintf (sched_dump, " %s:[%d base cost %d]",
2483 reg_class_names[cl], delta, this_cost);
2487 fprintf (sched_dump, "\n");
2492 /* Dump the next points of maximum pressure for GROUP. */
2495 model_dump_pressure_points (struct model_pressure_group *group)
2499 fprintf (sched_dump, ";;\t\t| pressure points");
2500 for (pci = 0; pci < ira_pressure_classes_num; pci++)
2502 cl = ira_pressure_classes[pci];
2503 fprintf (sched_dump, " %s:[%d->%d at ", reg_class_names[cl],
2504 curr_reg_pressure[cl], group->limits[pci].pressure);
2505 if (group->limits[pci].point < model_num_insns)
2506 fprintf (sched_dump, "%d:%d]", group->limits[pci].point,
2507 INSN_UID (MODEL_INSN (group->limits[pci].point)));
2509 fprintf (sched_dump, "end]");
2511 fprintf (sched_dump, "\n");
2514 /* Set INSN_REG_PRESSURE_EXCESS_COST_CHANGE for INSNS[0...COUNT-1]. */
2517 model_set_excess_costs (rtx_insn **insns, int count)
2519 int i, cost, priority_base, priority;
2522 /* Record the baseECC value for each instruction in the model schedule,
2523 except that negative costs are converted to zero ones now rather than
2524 later. Do not assign a cost to debug instructions, since they must
2525 not change code-generation decisions. Experiments suggest we also
2526 get better results by not assigning a cost to instructions from
2529 Set PRIORITY_BASE to baseP in the block comment above. This is the
2530 maximum priority of the "cheap" instructions, which should always
2531 include the next model instruction. */
2534 for (i = 0; i < count; i++)
2535 if (INSN_MODEL_INDEX (insns[i]))
2537 if (sched_verbose >= 6 && !print_p)
2539 fprintf (sched_dump, MODEL_BAR);
2540 fprintf (sched_dump, ";;\t\t| Pressure costs for ready queue\n");
2541 model_dump_pressure_points (&model_before_pressure);
2542 fprintf (sched_dump, MODEL_BAR);
2545 cost = model_excess_cost (insns[i], print_p);
2548 priority = INSN_PRIORITY (insns[i]) - insn_delay (insns[i]) - cost;
2549 priority_base = MAX (priority_base, priority);
2552 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insns[i]) = cost;
2555 fprintf (sched_dump, MODEL_BAR);
2557 /* Use MAX (baseECC, 0) and baseP to calculcate ECC for each
2559 for (i = 0; i < count; i++)
2561 cost = INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insns[i]);
2562 priority = INSN_PRIORITY (insns[i]) - insn_delay (insns[i]);
2563 if (cost > 0 && priority > priority_base)
2565 cost += priority_base - priority;
2566 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insns[i]) = MAX (cost, 0);
2572 /* Enum of rank_for_schedule heuristic decisions. */
2574 RFS_LIVE_RANGE_SHRINK1, RFS_LIVE_RANGE_SHRINK2,
2575 RFS_SCHED_GROUP, RFS_PRESSURE_DELAY, RFS_PRESSURE_TICK,
2576 RFS_FEEDS_BACKTRACK_INSN, RFS_PRIORITY, RFS_SPECULATION,
2577 RFS_SCHED_RANK, RFS_LAST_INSN, RFS_PRESSURE_INDEX,
2578 RFS_DEP_COUNT, RFS_TIE, RFS_FUSION, RFS_N };
2580 /* Corresponding strings for print outs. */
2581 static const char *rfs_str[RFS_N] = {
2582 "RFS_LIVE_RANGE_SHRINK1", "RFS_LIVE_RANGE_SHRINK2",
2583 "RFS_SCHED_GROUP", "RFS_PRESSURE_DELAY", "RFS_PRESSURE_TICK",
2584 "RFS_FEEDS_BACKTRACK_INSN", "RFS_PRIORITY", "RFS_SPECULATION",
2585 "RFS_SCHED_RANK", "RFS_LAST_INSN", "RFS_PRESSURE_INDEX",
2586 "RFS_DEP_COUNT", "RFS_TIE", "RFS_FUSION" };
2588 /* Statistical breakdown of rank_for_schedule decisions. */
2589 typedef struct { unsigned stats[RFS_N]; } rank_for_schedule_stats_t;
2590 static rank_for_schedule_stats_t rank_for_schedule_stats;
2592 /* Return the result of comparing insns TMP and TMP2 and update
2593 Rank_For_Schedule statistics. */
2595 rfs_result (enum rfs_decision decision, int result, rtx tmp, rtx tmp2)
2597 ++rank_for_schedule_stats.stats[decision];
2599 INSN_LAST_RFS_WIN (tmp) = decision;
2600 else if (result > 0)
2601 INSN_LAST_RFS_WIN (tmp2) = decision;
2607 /* Sorting predicate to move DEBUG_INSNs to the top of ready list, while
2608 keeping normal insns in original order. */
2611 rank_for_schedule_debug (const void *x, const void *y)
2613 rtx_insn *tmp = *(rtx_insn * const *) y;
2614 rtx_insn *tmp2 = *(rtx_insn * const *) x;
2616 /* Schedule debug insns as early as possible. */
2617 if (DEBUG_INSN_P (tmp) && !DEBUG_INSN_P (tmp2))
2619 else if (!DEBUG_INSN_P (tmp) && DEBUG_INSN_P (tmp2))
2621 else if (DEBUG_INSN_P (tmp) && DEBUG_INSN_P (tmp2))
2622 return INSN_LUID (tmp) - INSN_LUID (tmp2);
2624 return INSN_RFS_DEBUG_ORIG_ORDER (tmp2) - INSN_RFS_DEBUG_ORIG_ORDER (tmp);
2627 /* Returns a positive value if x is preferred; returns a negative value if
2628 y is preferred. Should never return 0, since that will make the sort
2632 rank_for_schedule (const void *x, const void *y)
2634 rtx_insn *tmp = *(rtx_insn * const *) y;
2635 rtx_insn *tmp2 = *(rtx_insn * const *) x;
2636 int tmp_class, tmp2_class;
2637 int val, priority_val, info_val, diff;
2639 if (live_range_shrinkage_p)
2641 /* Don't use SCHED_PRESSURE_MODEL -- it results in much worse
2643 gcc_assert (sched_pressure == SCHED_PRESSURE_WEIGHTED);
2644 if ((INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp) < 0
2645 || INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp2) < 0)
2646 && (diff = (INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp)
2647 - INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp2))) != 0)
2648 return rfs_result (RFS_LIVE_RANGE_SHRINK1, diff, tmp, tmp2);
2649 /* Sort by INSN_LUID (original insn order), so that we make the
2650 sort stable. This minimizes instruction movement, thus
2651 minimizing sched's effect on debugging and cross-jumping. */
2652 return rfs_result (RFS_LIVE_RANGE_SHRINK2,
2653 INSN_LUID (tmp) - INSN_LUID (tmp2), tmp, tmp2);
2656 /* The insn in a schedule group should be issued the first. */
2657 if (flag_sched_group_heuristic &&
2658 SCHED_GROUP_P (tmp) != SCHED_GROUP_P (tmp2))
2659 return rfs_result (RFS_SCHED_GROUP, SCHED_GROUP_P (tmp2) ? 1 : -1,
2662 /* Make sure that priority of TMP and TMP2 are initialized. */
2663 gcc_assert (INSN_PRIORITY_KNOWN (tmp) && INSN_PRIORITY_KNOWN (tmp2));
2667 /* The instruction that has the same fusion priority as the last
2668 instruction is the instruction we picked next. If that is not
2669 the case, we sort ready list firstly by fusion priority, then
2670 by priority, and at last by INSN_LUID. */
2671 int a = INSN_FUSION_PRIORITY (tmp);
2672 int b = INSN_FUSION_PRIORITY (tmp2);
2675 if (last_nondebug_scheduled_insn
2676 && !NOTE_P (last_nondebug_scheduled_insn)
2677 && BLOCK_FOR_INSN (tmp)
2678 == BLOCK_FOR_INSN (last_nondebug_scheduled_insn))
2679 last = INSN_FUSION_PRIORITY (last_nondebug_scheduled_insn);
2681 if (a != last && b != last)
2685 a = INSN_PRIORITY (tmp);
2686 b = INSN_PRIORITY (tmp2);
2689 return rfs_result (RFS_FUSION, b - a, tmp, tmp2);
2691 return rfs_result (RFS_FUSION,
2692 INSN_LUID (tmp) - INSN_LUID (tmp2), tmp, tmp2);
2696 gcc_assert (last_nondebug_scheduled_insn
2697 && !NOTE_P (last_nondebug_scheduled_insn));
2698 last = INSN_PRIORITY (last_nondebug_scheduled_insn);
2700 a = abs (INSN_PRIORITY (tmp) - last);
2701 b = abs (INSN_PRIORITY (tmp2) - last);
2703 return rfs_result (RFS_FUSION, a - b, tmp, tmp2);
2705 return rfs_result (RFS_FUSION,
2706 INSN_LUID (tmp) - INSN_LUID (tmp2), tmp, tmp2);
2709 return rfs_result (RFS_FUSION, -1, tmp, tmp2);
2711 return rfs_result (RFS_FUSION, 1, tmp, tmp2);
2714 if (sched_pressure != SCHED_PRESSURE_NONE)
2716 /* Prefer insn whose scheduling results in the smallest register
2718 if ((diff = (INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp)
2720 - INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp2)
2721 - insn_delay (tmp2))))
2722 return rfs_result (RFS_PRESSURE_DELAY, diff, tmp, tmp2);
2725 if (sched_pressure != SCHED_PRESSURE_NONE
2726 && (INSN_TICK (tmp2) > clock_var || INSN_TICK (tmp) > clock_var)
2727 && INSN_TICK (tmp2) != INSN_TICK (tmp))
2729 diff = INSN_TICK (tmp) - INSN_TICK (tmp2);
2730 return rfs_result (RFS_PRESSURE_TICK, diff, tmp, tmp2);
2733 /* If we are doing backtracking in this schedule, prefer insns that
2734 have forward dependencies with negative cost against an insn that
2735 was already scheduled. */
2736 if (current_sched_info->flags & DO_BACKTRACKING)
2738 priority_val = FEEDS_BACKTRACK_INSN (tmp2) - FEEDS_BACKTRACK_INSN (tmp);
2740 return rfs_result (RFS_FEEDS_BACKTRACK_INSN, priority_val, tmp, tmp2);
2743 /* Prefer insn with higher priority. */
2744 priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
2746 if (flag_sched_critical_path_heuristic && priority_val)
2747 return rfs_result (RFS_PRIORITY, priority_val, tmp, tmp2);
2749 if (PARAM_VALUE (PARAM_SCHED_AUTOPREF_QUEUE_DEPTH) >= 0)
2751 int autopref = autopref_rank_for_schedule (tmp, tmp2);
2756 /* Prefer speculative insn with greater dependencies weakness. */
2757 if (flag_sched_spec_insn_heuristic && spec_info)
2763 ds1 = TODO_SPEC (tmp) & SPECULATIVE;
2765 dw1 = ds_weak (ds1);
2769 ds2 = TODO_SPEC (tmp2) & SPECULATIVE;
2771 dw2 = ds_weak (ds2);
2776 if (dw > (NO_DEP_WEAK / 8) || dw < -(NO_DEP_WEAK / 8))
2777 return rfs_result (RFS_SPECULATION, dw, tmp, tmp2);
2780 info_val = (*current_sched_info->rank) (tmp, tmp2);
2781 if (flag_sched_rank_heuristic && info_val)
2782 return rfs_result (RFS_SCHED_RANK, info_val, tmp, tmp2);
2784 /* Compare insns based on their relation to the last scheduled
2786 if (flag_sched_last_insn_heuristic && last_nondebug_scheduled_insn)
2790 rtx last = last_nondebug_scheduled_insn;
2792 /* Classify the instructions into three classes:
2793 1) Data dependent on last schedule insn.
2794 2) Anti/Output dependent on last scheduled insn.
2795 3) Independent of last scheduled insn, or has latency of one.
2796 Choose the insn from the highest numbered class if different. */
2797 dep1 = sd_find_dep_between (last, tmp, true);
2799 if (dep1 == NULL || dep_cost (dep1) == 1)
2801 else if (/* Data dependence. */
2802 DEP_TYPE (dep1) == REG_DEP_TRUE)
2807 dep2 = sd_find_dep_between (last, tmp2, true);
2809 if (dep2 == NULL || dep_cost (dep2) == 1)
2811 else if (/* Data dependence. */
2812 DEP_TYPE (dep2) == REG_DEP_TRUE)
2817 if ((val = tmp2_class - tmp_class))
2818 return rfs_result (RFS_LAST_INSN, val, tmp, tmp2);
2821 /* Prefer instructions that occur earlier in the model schedule. */
2822 if (sched_pressure == SCHED_PRESSURE_MODEL
2823 && INSN_BB (tmp) == target_bb && INSN_BB (tmp2) == target_bb)
2825 diff = model_index (tmp) - model_index (tmp2);
2826 gcc_assert (diff != 0);
2827 return rfs_result (RFS_PRESSURE_INDEX, diff, tmp, tmp2);
2830 /* Prefer the insn which has more later insns that depend on it.
2831 This gives the scheduler more freedom when scheduling later
2832 instructions at the expense of added register pressure. */
2834 val = (dep_list_size (tmp2, SD_LIST_FORW)
2835 - dep_list_size (tmp, SD_LIST_FORW));
2837 if (flag_sched_dep_count_heuristic && val != 0)
2838 return rfs_result (RFS_DEP_COUNT, val, tmp, tmp2);
2840 /* If insns are equally good, sort by INSN_LUID (original insn order),
2841 so that we make the sort stable. This minimizes instruction movement,
2842 thus minimizing sched's effect on debugging and cross-jumping. */
2843 return rfs_result (RFS_TIE, INSN_LUID (tmp) - INSN_LUID (tmp2), tmp, tmp2);
2846 /* Resort the array A in which only element at index N may be out of order. */
2848 HAIFA_INLINE static void
2849 swap_sort (rtx_insn **a, int n)
2851 rtx_insn *insn = a[n - 1];
2854 while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0)
2862 /* Add INSN to the insn queue so that it can be executed at least
2863 N_CYCLES after the currently executing insn. Preserve insns
2864 chain for debugging purposes. REASON will be printed in debugging
2867 HAIFA_INLINE static void
2868 queue_insn (rtx_insn *insn, int n_cycles, const char *reason)
2870 int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
2871 rtx_insn_list *link = alloc_INSN_LIST (insn, insn_queue[next_q]);
2874 gcc_assert (n_cycles <= max_insn_queue_index);
2875 gcc_assert (!DEBUG_INSN_P (insn));
2877 insn_queue[next_q] = link;
2880 if (sched_verbose >= 2)
2882 fprintf (sched_dump, ";;\t\tReady-->Q: insn %s: ",
2883 (*current_sched_info->print_insn) (insn, 0));
2885 fprintf (sched_dump, "queued for %d cycles (%s).\n", n_cycles, reason);
2888 QUEUE_INDEX (insn) = next_q;
2890 if (current_sched_info->flags & DO_BACKTRACKING)
2892 new_tick = clock_var + n_cycles;
2893 if (INSN_TICK (insn) == INVALID_TICK || INSN_TICK (insn) < new_tick)
2894 INSN_TICK (insn) = new_tick;
2896 if (INSN_EXACT_TICK (insn) != INVALID_TICK
2897 && INSN_EXACT_TICK (insn) < clock_var + n_cycles)
2899 must_backtrack = true;
2900 if (sched_verbose >= 2)
2901 fprintf (sched_dump, ";;\t\tcausing a backtrack.\n");
2906 /* Remove INSN from queue. */
2908 queue_remove (rtx_insn *insn)
2910 gcc_assert (QUEUE_INDEX (insn) >= 0);
2911 remove_free_INSN_LIST_elem (insn, &insn_queue[QUEUE_INDEX (insn)]);
2913 QUEUE_INDEX (insn) = QUEUE_NOWHERE;
2916 /* Return a pointer to the bottom of the ready list, i.e. the insn
2917 with the lowest priority. */
2920 ready_lastpos (struct ready_list *ready)
2922 gcc_assert (ready->n_ready >= 1);
2923 return ready->vec + ready->first - ready->n_ready + 1;
2926 /* Add an element INSN to the ready list so that it ends up with the
2927 lowest/highest priority depending on FIRST_P. */
2929 HAIFA_INLINE static void
2930 ready_add (struct ready_list *ready, rtx_insn *insn, bool first_p)
2934 if (ready->first == ready->n_ready)
2936 memmove (ready->vec + ready->veclen - ready->n_ready,
2937 ready_lastpos (ready),
2938 ready->n_ready * sizeof (rtx));
2939 ready->first = ready->veclen - 1;
2941 ready->vec[ready->first - ready->n_ready] = insn;
2945 if (ready->first == ready->veclen - 1)
2948 /* ready_lastpos() fails when called with (ready->n_ready == 0). */
2949 memmove (ready->vec + ready->veclen - ready->n_ready - 1,
2950 ready_lastpos (ready),
2951 ready->n_ready * sizeof (rtx));
2952 ready->first = ready->veclen - 2;
2954 ready->vec[++(ready->first)] = insn;
2958 if (DEBUG_INSN_P (insn))
2961 gcc_assert (QUEUE_INDEX (insn) != QUEUE_READY);
2962 QUEUE_INDEX (insn) = QUEUE_READY;
2964 if (INSN_EXACT_TICK (insn) != INVALID_TICK
2965 && INSN_EXACT_TICK (insn) < clock_var)
2967 must_backtrack = true;
2971 /* Remove the element with the highest priority from the ready list and
2974 HAIFA_INLINE static rtx_insn *
2975 ready_remove_first (struct ready_list *ready)
2979 gcc_assert (ready->n_ready);
2980 t = ready->vec[ready->first--];
2982 if (DEBUG_INSN_P (t))
2984 /* If the queue becomes empty, reset it. */
2985 if (ready->n_ready == 0)
2986 ready->first = ready->veclen - 1;
2988 gcc_assert (QUEUE_INDEX (t) == QUEUE_READY);
2989 QUEUE_INDEX (t) = QUEUE_NOWHERE;
2994 /* The following code implements multi-pass scheduling for the first
2995 cycle. In other words, we will try to choose ready insn which
2996 permits to start maximum number of insns on the same cycle. */
2998 /* Return a pointer to the element INDEX from the ready. INDEX for
2999 insn with the highest priority is 0, and the lowest priority has
3003 ready_element (struct ready_list *ready, int index)
3005 gcc_assert (ready->n_ready && index < ready->n_ready);
3007 return ready->vec[ready->first - index];
3010 /* Remove the element INDEX from the ready list and return it. INDEX
3011 for insn with the highest priority is 0, and the lowest priority
3014 HAIFA_INLINE static rtx_insn *
3015 ready_remove (struct ready_list *ready, int index)
3021 return ready_remove_first (ready);
3022 gcc_assert (ready->n_ready && index < ready->n_ready);
3023 t = ready->vec[ready->first - index];
3025 if (DEBUG_INSN_P (t))
3027 for (i = index; i < ready->n_ready; i++)
3028 ready->vec[ready->first - i] = ready->vec[ready->first - i - 1];
3029 QUEUE_INDEX (t) = QUEUE_NOWHERE;
3033 /* Remove INSN from the ready list. */
3035 ready_remove_insn (rtx insn)
3039 for (i = 0; i < readyp->n_ready; i++)
3040 if (ready_element (readyp, i) == insn)
3042 ready_remove (readyp, i);
3048 /* Calculate difference of two statistics set WAS and NOW.
3049 Result returned in WAS. */
3051 rank_for_schedule_stats_diff (rank_for_schedule_stats_t *was,
3052 const rank_for_schedule_stats_t *now)
3054 for (int i = 0; i < RFS_N; ++i)
3055 was->stats[i] = now->stats[i] - was->stats[i];
3058 /* Print rank_for_schedule statistics. */
3060 print_rank_for_schedule_stats (const char *prefix,
3061 const rank_for_schedule_stats_t *stats,
3062 struct ready_list *ready)
3064 for (int i = 0; i < RFS_N; ++i)
3065 if (stats->stats[i])
3067 fprintf (sched_dump, "%s%20s: %u", prefix, rfs_str[i], stats->stats[i]);
3070 /* Print out insns that won due to RFS_<I>. */
3072 rtx_insn **p = ready_lastpos (ready);
3074 fprintf (sched_dump, ":");
3075 /* Start with 1 since least-priority insn didn't have any wins. */
3076 for (int j = 1; j < ready->n_ready; ++j)
3077 if (INSN_LAST_RFS_WIN (p[j]) == i)
3078 fprintf (sched_dump, " %s",
3079 (*current_sched_info->print_insn) (p[j], 0));
3081 fprintf (sched_dump, "\n");
3085 /* Separate DEBUG_INSNS from normal insns. DEBUG_INSNs go to the end
3088 ready_sort_debug (struct ready_list *ready)
3091 rtx_insn **first = ready_lastpos (ready);
3093 for (i = 0; i < ready->n_ready; ++i)
3094 if (!DEBUG_INSN_P (first[i]))
3095 INSN_RFS_DEBUG_ORIG_ORDER (first[i]) = i;
3097 qsort (first, ready->n_ready, sizeof (rtx), rank_for_schedule_debug);
3100 /* Sort non-debug insns in the ready list READY by ascending priority.
3101 Assumes that all debug insns are separated from the real insns. */
3103 ready_sort_real (struct ready_list *ready)
3106 rtx_insn **first = ready_lastpos (ready);
3107 int n_ready_real = ready->n_ready - ready->n_debug;
3109 if (sched_pressure == SCHED_PRESSURE_WEIGHTED)
3110 for (i = 0; i < n_ready_real; ++i)
3111 setup_insn_reg_pressure_info (first[i]);
3112 else if (sched_pressure == SCHED_PRESSURE_MODEL
3113 && model_curr_point < model_num_insns)
3114 model_set_excess_costs (first, n_ready_real);
3116 rank_for_schedule_stats_t stats1;
3117 if (sched_verbose >= 4)
3118 stats1 = rank_for_schedule_stats;
3120 if (n_ready_real == 2)
3121 swap_sort (first, n_ready_real);
3122 else if (n_ready_real > 2)
3123 qsort (first, n_ready_real, sizeof (rtx), rank_for_schedule);
3125 if (sched_verbose >= 4)
3127 rank_for_schedule_stats_diff (&stats1, &rank_for_schedule_stats);
3128 print_rank_for_schedule_stats (";;\t\t", &stats1, ready);
3132 /* Sort the ready list READY by ascending priority. */
3134 ready_sort (struct ready_list *ready)
3136 if (ready->n_debug > 0)
3137 ready_sort_debug (ready);
3139 ready_sort_real (ready);
3142 /* PREV is an insn that is ready to execute. Adjust its priority if that
3143 will help shorten or lengthen register lifetimes as appropriate. Also
3144 provide a hook for the target to tweak itself. */
3146 HAIFA_INLINE static void
3147 adjust_priority (rtx_insn *prev)
3149 /* ??? There used to be code here to try and estimate how an insn
3150 affected register lifetimes, but it did it by looking at REG_DEAD
3151 notes, which we removed in schedule_region. Nor did it try to
3152 take into account register pressure or anything useful like that.
3154 Revisit when we have a machine model to work with and not before. */
3156 if (targetm.sched.adjust_priority)
3157 INSN_PRIORITY (prev) =
3158 targetm.sched.adjust_priority (prev, INSN_PRIORITY (prev));
3161 /* Advance DFA state STATE on one cycle. */
3163 advance_state (state_t state)
3165 if (targetm.sched.dfa_pre_advance_cycle)
3166 targetm.sched.dfa_pre_advance_cycle ();
3168 if (targetm.sched.dfa_pre_cycle_insn)
3169 state_transition (state,
3170 targetm.sched.dfa_pre_cycle_insn ());
3172 state_transition (state, NULL);
3174 if (targetm.sched.dfa_post_cycle_insn)
3175 state_transition (state,
3176 targetm.sched.dfa_post_cycle_insn ());
3178 if (targetm.sched.dfa_post_advance_cycle)
3179 targetm.sched.dfa_post_advance_cycle ();
3182 /* Advance time on one cycle. */
3183 HAIFA_INLINE static void
3184 advance_one_cycle (void)
3186 advance_state (curr_state);
3187 if (sched_verbose >= 4)
3188 fprintf (sched_dump, ";;\tAdvance the current state.\n");
3191 /* Update register pressure after scheduling INSN. */
3193 update_register_pressure (rtx_insn *insn)
3195 struct reg_use_data *use;
3196 struct reg_set_data *set;
3198 gcc_checking_assert (!DEBUG_INSN_P (insn));
3200 for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
3201 if (dying_use_p (use))
3202 mark_regno_birth_or_death (curr_reg_live, curr_reg_pressure,
3204 for (set = INSN_REG_SET_LIST (insn); set != NULL; set = set->next_insn_set)
3205 mark_regno_birth_or_death (curr_reg_live, curr_reg_pressure,
3209 /* Set up or update (if UPDATE_P) max register pressure (see its
3210 meaning in sched-int.h::_haifa_insn_data) for all current BB insns
3211 after insn AFTER. */
3213 setup_insn_max_reg_pressure (rtx_insn *after, bool update_p)
3218 static int max_reg_pressure[N_REG_CLASSES];
3220 save_reg_pressure ();
3221 for (i = 0; i < ira_pressure_classes_num; i++)
3222 max_reg_pressure[ira_pressure_classes[i]]
3223 = curr_reg_pressure[ira_pressure_classes[i]];
3224 for (insn = NEXT_INSN (after);
3225 insn != NULL_RTX && ! BARRIER_P (insn)
3226 && BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (after);
3227 insn = NEXT_INSN (insn))
3228 if (NONDEBUG_INSN_P (insn))
3231 for (i = 0; i < ira_pressure_classes_num; i++)
3233 p = max_reg_pressure[ira_pressure_classes[i]];
3234 if (INSN_MAX_REG_PRESSURE (insn)[i] != p)
3237 INSN_MAX_REG_PRESSURE (insn)[i]
3238 = max_reg_pressure[ira_pressure_classes[i]];
3241 if (update_p && eq_p)
3243 update_register_pressure (insn);
3244 for (i = 0; i < ira_pressure_classes_num; i++)
3245 if (max_reg_pressure[ira_pressure_classes[i]]
3246 < curr_reg_pressure[ira_pressure_classes[i]])
3247 max_reg_pressure[ira_pressure_classes[i]]
3248 = curr_reg_pressure[ira_pressure_classes[i]];
3250 restore_reg_pressure ();
3253 /* Update the current register pressure after scheduling INSN. Update
3254 also max register pressure for unscheduled insns of the current
3257 update_reg_and_insn_max_reg_pressure (rtx_insn *insn)
3260 int before[N_REG_CLASSES];
3262 for (i = 0; i < ira_pressure_classes_num; i++)
3263 before[i] = curr_reg_pressure[ira_pressure_classes[i]];
3264 update_register_pressure (insn);
3265 for (i = 0; i < ira_pressure_classes_num; i++)
3266 if (curr_reg_pressure[ira_pressure_classes[i]] != before[i])
3268 if (i < ira_pressure_classes_num)
3269 setup_insn_max_reg_pressure (insn, true);
3272 /* Set up register pressure at the beginning of basic block BB whose
3273 insns starting after insn AFTER. Set up also max register pressure
3274 for all insns of the basic block. */
3276 sched_setup_bb_reg_pressure_info (basic_block bb, rtx_insn *after)
3278 gcc_assert (sched_pressure == SCHED_PRESSURE_WEIGHTED);
3279 initiate_bb_reg_pressure_info (bb);
3280 setup_insn_max_reg_pressure (after, false);
3283 /* If doing predication while scheduling, verify whether INSN, which
3284 has just been scheduled, clobbers the conditions of any
3285 instructions that must be predicated in order to break their
3286 dependencies. If so, remove them from the queues so that they will
3287 only be scheduled once their control dependency is resolved. */
3290 check_clobbered_conditions (rtx insn)
3295 if ((current_sched_info->flags & DO_PREDICATION) == 0)
3298 find_all_hard_reg_sets (insn, &t, true);
3301 for (i = 0; i < ready.n_ready; i++)
3303 rtx_insn *x = ready_element (&ready, i);
3304 if (TODO_SPEC (x) == DEP_CONTROL && cond_clobbered_p (x, t))
3306 ready_remove_insn (x);
3310 for (i = 0; i <= max_insn_queue_index; i++)
3312 rtx_insn_list *link;
3313 int q = NEXT_Q_AFTER (q_ptr, i);
3316 for (link = insn_queue[q]; link; link = link->next ())
3318 rtx_insn *x = link->insn ();
3319 if (TODO_SPEC (x) == DEP_CONTROL && cond_clobbered_p (x, t))
3328 /* Return (in order):
3330 - positive if INSN adversely affects the pressure on one
3333 - negative if INSN reduces the pressure on one register class
3335 - 0 if INSN doesn't affect the pressure on any register class. */
3338 model_classify_pressure (struct model_insn_info *insn)
3340 struct reg_pressure_data *reg_pressure;
3341 int death[N_REG_CLASSES];
3344 calculate_reg_deaths (insn->insn, death);
3345 reg_pressure = INSN_REG_PRESSURE (insn->insn);
3347 for (pci = 0; pci < ira_pressure_classes_num; pci++)
3349 cl = ira_pressure_classes[pci];
3350 if (death[cl] < reg_pressure[pci].set_increase)
3352 sum += reg_pressure[pci].set_increase - death[cl];
3357 /* Return true if INSN1 should come before INSN2 in the model schedule. */
3360 model_order_p (struct model_insn_info *insn1, struct model_insn_info *insn2)
3362 unsigned int height1, height2;
3363 unsigned int priority1, priority2;
3365 /* Prefer instructions with a higher model priority. */
3366 if (insn1->model_priority != insn2->model_priority)
3367 return insn1->model_priority > insn2->model_priority;
3369 /* Combine the length of the longest path of satisfied true dependencies
3370 that leads to each instruction (depth) with the length of the longest
3371 path of any dependencies that leads from the instruction (alap).
3372 Prefer instructions with the greatest combined length. If the combined
3373 lengths are equal, prefer instructions with the greatest depth.
3375 The idea is that, if we have a set S of "equal" instructions that each
3376 have ALAP value X, and we pick one such instruction I, any true-dependent
3377 successors of I that have ALAP value X - 1 should be preferred over S.
3378 This encourages the schedule to be "narrow" rather than "wide".
3379 However, if I is a low-priority instruction that we decided to
3380 schedule because of its model_classify_pressure, and if there
3381 is a set of higher-priority instructions T, the aforementioned
3382 successors of I should not have the edge over T. */
3383 height1 = insn1->depth + insn1->alap;
3384 height2 = insn2->depth + insn2->alap;
3385 if (height1 != height2)
3386 return height1 > height2;
3387 if (insn1->depth != insn2->depth)
3388 return insn1->depth > insn2->depth;
3390 /* We have no real preference between INSN1 an INSN2 as far as attempts
3391 to reduce pressure go. Prefer instructions with higher priorities. */
3392 priority1 = INSN_PRIORITY (insn1->insn);
3393 priority2 = INSN_PRIORITY (insn2->insn);
3394 if (priority1 != priority2)
3395 return priority1 > priority2;
3397 /* Use the original rtl sequence as a tie-breaker. */
3398 return insn1 < insn2;
3401 /* Add INSN to the model worklist immediately after PREV. Add it to the
3402 beginning of the list if PREV is null. */
3405 model_add_to_worklist_at (struct model_insn_info *insn,
3406 struct model_insn_info *prev)
3408 gcc_assert (QUEUE_INDEX (insn->insn) == QUEUE_NOWHERE);
3409 QUEUE_INDEX (insn->insn) = QUEUE_READY;
3414 insn->next = prev->next;
3419 insn->next = model_worklist;
3420 model_worklist = insn;
3423 insn->next->prev = insn;
3426 /* Remove INSN from the model worklist. */
3429 model_remove_from_worklist (struct model_insn_info *insn)
3431 gcc_assert (QUEUE_INDEX (insn->insn) == QUEUE_READY);
3432 QUEUE_INDEX (insn->insn) = QUEUE_NOWHERE;
3435 insn->prev->next = insn->next;
3437 model_worklist = insn->next;
3439 insn->next->prev = insn->prev;
3442 /* Add INSN to the model worklist. Start looking for a suitable position
3443 between neighbors PREV and NEXT, testing at most MAX_SCHED_READY_INSNS
3444 insns either side. A null PREV indicates the beginning of the list and
3445 a null NEXT indicates the end. */
3448 model_add_to_worklist (struct model_insn_info *insn,
3449 struct model_insn_info *prev,
3450 struct model_insn_info *next)
3454 count = MAX_SCHED_READY_INSNS;
3455 if (count > 0 && prev && model_order_p (insn, prev))
3461 while (count > 0 && prev && model_order_p (insn, prev));
3463 while (count > 0 && next && model_order_p (next, insn))
3469 model_add_to_worklist_at (insn, prev);
3472 /* INSN may now have a higher priority (in the model_order_p sense)
3473 than before. Move it up the worklist if necessary. */
3476 model_promote_insn (struct model_insn_info *insn)
3478 struct model_insn_info *prev;
3482 count = MAX_SCHED_READY_INSNS;
3483 while (count > 0 && prev && model_order_p (insn, prev))
3488 if (prev != insn->prev)
3490 model_remove_from_worklist (insn);
3491 model_add_to_worklist_at (insn, prev);
3495 /* Add INSN to the end of the model schedule. */
3498 model_add_to_schedule (rtx_insn *insn)
3502 gcc_assert (QUEUE_INDEX (insn) == QUEUE_NOWHERE);
3503 QUEUE_INDEX (insn) = QUEUE_SCHEDULED;
3505 point = model_schedule.length ();
3506 model_schedule.quick_push (insn);
3507 INSN_MODEL_INDEX (insn) = point + 1;
3510 /* Analyze the instructions that are to be scheduled, setting up
3511 MODEL_INSN_INFO (...) and model_num_insns accordingly. Add ready
3512 instructions to model_worklist. */
3515 model_analyze_insns (void)
3517 rtx_insn *start, *end, *iter;
3518 sd_iterator_def sd_it;
3520 struct model_insn_info *insn, *con;
3522 model_num_insns = 0;
3523 start = PREV_INSN (current_sched_info->next_tail);
3524 end = current_sched_info->prev_head;
3525 for (iter = start; iter != end; iter = PREV_INSN (iter))
3526 if (NONDEBUG_INSN_P (iter))
3528 insn = MODEL_INSN_INFO (iter);
3530 FOR_EACH_DEP (iter, SD_LIST_FORW, sd_it, dep)
3532 con = MODEL_INSN_INFO (DEP_CON (dep));
3533 if (con->insn && insn->alap < con->alap + 1)
3534 insn->alap = con->alap + 1;
3537 insn->old_queue = QUEUE_INDEX (iter);
3538 QUEUE_INDEX (iter) = QUEUE_NOWHERE;
3540 insn->unscheduled_preds = dep_list_size (iter, SD_LIST_HARD_BACK);
3541 if (insn->unscheduled_preds == 0)
3542 model_add_to_worklist (insn, NULL, model_worklist);
3548 /* The global state describes the register pressure at the start of the
3549 model schedule. Initialize GROUP accordingly. */
3552 model_init_pressure_group (struct model_pressure_group *group)
3556 for (pci = 0; pci < ira_pressure_classes_num; pci++)
3558 cl = ira_pressure_classes[pci];
3559 group->limits[pci].pressure = curr_reg_pressure[cl];
3560 group->limits[pci].point = 0;
3562 /* Use index model_num_insns to record the state after the last
3563 instruction in the model schedule. */
3564 group->model = XNEWVEC (struct model_pressure_data,
3565 (model_num_insns + 1) * ira_pressure_classes_num);
3568 /* Record that MODEL_REF_PRESSURE (GROUP, POINT, PCI) is PRESSURE.
3569 Update the maximum pressure for the whole schedule. */
3572 model_record_pressure (struct model_pressure_group *group,
3573 int point, int pci, int pressure)
3575 MODEL_REF_PRESSURE (group, point, pci) = pressure;
3576 if (group->limits[pci].pressure < pressure)
3578 group->limits[pci].pressure = pressure;
3579 group->limits[pci].point = point;
3583 /* INSN has just been added to the end of the model schedule. Record its
3584 register-pressure information. */
3587 model_record_pressures (struct model_insn_info *insn)
3589 struct reg_pressure_data *reg_pressure;
3590 int point, pci, cl, delta;
3591 int death[N_REG_CLASSES];
3593 point = model_index (insn->insn);
3594 if (sched_verbose >= 2)
3598 fprintf (sched_dump, "\n;;\tModel schedule:\n;;\n");
3599 fprintf (sched_dump, ";;\t| idx insn | mpri hght dpth prio |\n");
3601 fprintf (sched_dump, ";;\t| %3d %4d | %4d %4d %4d %4d | %-30s ",
3602 point, INSN_UID (insn->insn), insn->model_priority,
3603 insn->depth + insn->alap, insn->depth,
3604 INSN_PRIORITY (insn->insn),
3605 str_pattern_slim (PATTERN (insn->insn)));
3607 calculate_reg_deaths (insn->insn, death);
3608 reg_pressure = INSN_REG_PRESSURE (insn->insn);
3609 for (pci = 0; pci < ira_pressure_classes_num; pci++)
3611 cl = ira_pressure_classes[pci];
3612 delta = reg_pressure[pci].set_increase - death[cl];
3613 if (sched_verbose >= 2)
3614 fprintf (sched_dump, " %s:[%d,%+d]", reg_class_names[cl],
3615 curr_reg_pressure[cl], delta);
3616 model_record_pressure (&model_before_pressure, point, pci,
3617 curr_reg_pressure[cl]);
3619 if (sched_verbose >= 2)
3620 fprintf (sched_dump, "\n");
3623 /* All instructions have been added to the model schedule. Record the
3624 final register pressure in GROUP and set up all MODEL_MAX_PRESSUREs. */
3627 model_record_final_pressures (struct model_pressure_group *group)
3629 int point, pci, max_pressure, ref_pressure, cl;
3631 for (pci = 0; pci < ira_pressure_classes_num; pci++)
3633 /* Record the final pressure for this class. */
3634 cl = ira_pressure_classes[pci];
3635 point = model_num_insns;
3636 ref_pressure = curr_reg_pressure[cl];
3637 model_record_pressure (group, point, pci, ref_pressure);
3639 /* Record the original maximum pressure. */
3640 group->limits[pci].orig_pressure = group->limits[pci].pressure;
3642 /* Update the MODEL_MAX_PRESSURE for every point of the schedule. */
3643 max_pressure = ref_pressure;
3644 MODEL_MAX_PRESSURE (group, point, pci) = max_pressure;
3648 ref_pressure = MODEL_REF_PRESSURE (group, point, pci);
3649 max_pressure = MAX (max_pressure, ref_pressure);
3650 MODEL_MAX_PRESSURE (group, point, pci) = max_pressure;
3655 /* Update all successors of INSN, given that INSN has just been scheduled. */
3658 model_add_successors_to_worklist (struct model_insn_info *insn)
3660 sd_iterator_def sd_it;
3661 struct model_insn_info *con;
3664 FOR_EACH_DEP (insn->insn, SD_LIST_FORW, sd_it, dep)
3666 con = MODEL_INSN_INFO (DEP_CON (dep));
3667 /* Ignore debug instructions, and instructions from other blocks. */
3670 con->unscheduled_preds--;
3672 /* Update the depth field of each true-dependent successor.
3673 Increasing the depth gives them a higher priority than
3675 if (DEP_TYPE (dep) == REG_DEP_TRUE && con->depth < insn->depth + 1)
3677 con->depth = insn->depth + 1;
3678 if (QUEUE_INDEX (con->insn) == QUEUE_READY)
3679 model_promote_insn (con);
3682 /* If this is a true dependency, or if there are no remaining
3683 dependencies for CON (meaning that CON only had non-true
3684 dependencies), make sure that CON is on the worklist.
3685 We don't bother otherwise because it would tend to fill the
3686 worklist with a lot of low-priority instructions that are not
3687 yet ready to issue. */
3688 if ((con->depth > 0 || con->unscheduled_preds == 0)
3689 && QUEUE_INDEX (con->insn) == QUEUE_NOWHERE)
3690 model_add_to_worklist (con, insn, insn->next);
3695 /* Give INSN a higher priority than any current instruction, then give
3696 unscheduled predecessors of INSN a higher priority still. If any of
3697 those predecessors are not on the model worklist, do the same for its
3698 predecessors, and so on. */
3701 model_promote_predecessors (struct model_insn_info *insn)
3703 struct model_insn_info *pro, *first;
3704 sd_iterator_def sd_it;
3707 if (sched_verbose >= 7)
3708 fprintf (sched_dump, ";;\t+--- priority of %d = %d, priority of",
3709 INSN_UID (insn->insn), model_next_priority);
3710 insn->model_priority = model_next_priority++;
3711 model_remove_from_worklist (insn);
3712 model_add_to_worklist_at (insn, NULL);
3717 FOR_EACH_DEP (insn->insn, SD_LIST_HARD_BACK, sd_it, dep)
3719 pro = MODEL_INSN_INFO (DEP_PRO (dep));
3720 /* The first test is to ignore debug instructions, and instructions
3721 from other blocks. */
3723 && pro->model_priority != model_next_priority
3724 && QUEUE_INDEX (pro->insn) != QUEUE_SCHEDULED)
3726 pro->model_priority = model_next_priority;
3727 if (sched_verbose >= 7)
3728 fprintf (sched_dump, " %d", INSN_UID (pro->insn));
3729 if (QUEUE_INDEX (pro->insn) == QUEUE_READY)
3731 /* PRO is already in the worklist, but it now has
3732 a higher priority than before. Move it at the
3733 appropriate place. */
3734 model_remove_from_worklist (pro);
3735 model_add_to_worklist (pro, NULL, model_worklist);
3739 /* PRO isn't in the worklist. Recursively process
3740 its predecessors until we find one that is. */
3751 if (sched_verbose >= 7)
3752 fprintf (sched_dump, " = %d\n", model_next_priority);
3753 model_next_priority++;
3756 /* Pick one instruction from model_worklist and process it. */
3759 model_choose_insn (void)
3761 struct model_insn_info *insn, *fallback;
3764 if (sched_verbose >= 7)
3766 fprintf (sched_dump, ";;\t+--- worklist:\n");
3767 insn = model_worklist;
3768 count = MAX_SCHED_READY_INSNS;
3769 while (count > 0 && insn)
3771 fprintf (sched_dump, ";;\t+--- %d [%d, %d, %d, %d]\n",
3772 INSN_UID (insn->insn), insn->model_priority,
3773 insn->depth + insn->alap, insn->depth,
3774 INSN_PRIORITY (insn->insn));
3780 /* Look for a ready instruction whose model_classify_priority is zero
3781 or negative, picking the highest-priority one. Adding such an
3782 instruction to the schedule now should do no harm, and may actually
3785 Failing that, see whether there is an instruction with the highest
3786 extant model_priority that is not yet ready, but which would reduce
3787 pressure if it became ready. This is designed to catch cases like:
3789 (set (mem (reg R1)) (reg R2))
3791 where the instruction is the last remaining use of R1 and where the
3792 value of R2 is not yet available (or vice versa). The death of R1
3793 means that this instruction already reduces pressure. It is of
3794 course possible that the computation of R2 involves other registers
3795 that are hard to kill, but such cases are rare enough for this
3796 heuristic to be a win in general.
3798 Failing that, just pick the highest-priority instruction in the
3800 count = MAX_SCHED_READY_INSNS;
3801 insn = model_worklist;
3805 if (count == 0 || !insn)
3807 insn = fallback ? fallback : model_worklist;
3810 if (insn->unscheduled_preds)
3812 if (model_worklist->model_priority == insn->model_priority
3814 && model_classify_pressure (insn) < 0)
3819 if (model_classify_pressure (insn) <= 0)
3826 if (sched_verbose >= 7 && insn != model_worklist)
3828 if (insn->unscheduled_preds)
3829 fprintf (sched_dump, ";;\t+--- promoting insn %d, with dependencies\n",
3830 INSN_UID (insn->insn));
3832 fprintf (sched_dump, ";;\t+--- promoting insn %d, which is ready\n",
3833 INSN_UID (insn->insn));
3835 if (insn->unscheduled_preds)
3836 /* INSN isn't yet ready to issue. Give all its predecessors the
3837 highest priority. */
3838 model_promote_predecessors (insn);
3841 /* INSN is ready. Add it to the end of model_schedule and
3842 process its successors. */
3843 model_add_successors_to_worklist (insn);
3844 model_remove_from_worklist (insn);
3845 model_add_to_schedule (insn->insn);
3846 model_record_pressures (insn);
3847 update_register_pressure (insn->insn);
3851 /* Restore all QUEUE_INDEXs to the values that they had before
3852 model_start_schedule was called. */
3855 model_reset_queue_indices (void)
3860 FOR_EACH_VEC_ELT (model_schedule, i, insn)
3861 QUEUE_INDEX (insn) = MODEL_INSN_INFO (insn)->old_queue;
3864 /* We have calculated the model schedule and spill costs. Print a summary
3868 model_dump_pressure_summary (void)
3872 fprintf (sched_dump, ";; Pressure summary:");
3873 for (pci = 0; pci < ira_pressure_classes_num; pci++)
3875 cl = ira_pressure_classes[pci];
3876 fprintf (sched_dump, " %s:%d", reg_class_names[cl],
3877 model_before_pressure.limits[pci].pressure);
3879 fprintf (sched_dump, "\n\n");
3882 /* Initialize the SCHED_PRESSURE_MODEL information for the current
3883 scheduling region. */
3886 model_start_schedule (basic_block bb)
3888 model_next_priority = 1;
3889 model_schedule.create (sched_max_luid);
3890 model_insns = XCNEWVEC (struct model_insn_info, sched_max_luid);
3892 gcc_assert (bb == BLOCK_FOR_INSN (NEXT_INSN (current_sched_info->prev_head)));
3893 initiate_reg_pressure_info (df_get_live_in (bb));
3895 model_analyze_insns ();
3896 model_init_pressure_group (&model_before_pressure);
3897 while (model_worklist)
3898 model_choose_insn ();
3899 gcc_assert (model_num_insns == (int) model_schedule.length ());
3900 if (sched_verbose >= 2)
3901 fprintf (sched_dump, "\n");
3903 model_record_final_pressures (&model_before_pressure);
3904 model_reset_queue_indices ();
3906 XDELETEVEC (model_insns);
3908 model_curr_point = 0;
3909 initiate_reg_pressure_info (df_get_live_in (bb));
3910 if (sched_verbose >= 1)
3911 model_dump_pressure_summary ();
3914 /* Free the information associated with GROUP. */
3917 model_finalize_pressure_group (struct model_pressure_group *group)
3919 XDELETEVEC (group->model);
3922 /* Free the information created by model_start_schedule. */
3925 model_end_schedule (void)
3927 model_finalize_pressure_group (&model_before_pressure);
3928 model_schedule.release ();
3931 /* Prepare reg pressure scheduling for basic block BB. */
3933 sched_pressure_start_bb (basic_block bb)
3935 /* Set the number of available registers for each class taking into account
3936 relative probability of current basic block versus function prologue and
3938 * If the basic block executes much more often than the prologue/epilogue
3939 (e.g., inside a hot loop), then cost of spill in the prologue is close to
3940 nil, so the effective number of available registers is
3941 (ira_class_hard_regs_num[cl] - 0).
3942 * If the basic block executes as often as the prologue/epilogue,
3943 then spill in the block is as costly as in the prologue, so the effective
3944 number of available registers is
3945 (ira_class_hard_regs_num[cl] - call_used_regs_num[cl]).
3946 Note that all-else-equal, we prefer to spill in the prologue, since that
3947 allows "extra" registers for other basic blocks of the function.
3948 * If the basic block is on the cold path of the function and executes
3949 rarely, then we should always prefer to spill in the block, rather than
3950 in the prologue/epilogue. The effective number of available register is
3951 (ira_class_hard_regs_num[cl] - call_used_regs_num[cl]). */
3954 int entry_freq = ENTRY_BLOCK_PTR_FOR_FN (cfun)->frequency;
3955 int bb_freq = bb->frequency;
3959 if (entry_freq == 0)
3960 entry_freq = bb_freq = 1;
3962 if (bb_freq < entry_freq)
3963 bb_freq = entry_freq;
3965 for (i = 0; i < ira_pressure_classes_num; ++i)
3967 enum reg_class cl = ira_pressure_classes[i];
3968 sched_class_regs_num[cl] = ira_class_hard_regs_num[cl];
3969 sched_class_regs_num[cl]
3970 -= (call_used_regs_num[cl] * entry_freq) / bb_freq;
3974 if (sched_pressure == SCHED_PRESSURE_MODEL)
3975 model_start_schedule (bb);
3978 /* A structure that holds local state for the loop in schedule_block. */
3979 struct sched_block_state
3981 /* True if no real insns have been scheduled in the current cycle. */
3982 bool first_cycle_insn_p;
3983 /* True if a shadow insn has been scheduled in the current cycle, which
3984 means that no more normal insns can be issued. */
3985 bool shadows_only_p;
3986 /* True if we're winding down a modulo schedule, which means that we only
3987 issue insns with INSN_EXACT_TICK set. */
3988 bool modulo_epilogue;
3989 /* Initialized with the machine's issue rate every cycle, and updated
3990 by calls to the variable_issue hook. */
3994 /* INSN is the "currently executing insn". Launch each insn which was
3995 waiting on INSN. READY is the ready list which contains the insns
3996 that are ready to fire. CLOCK is the current cycle. The function
3997 returns necessary cycle advance after issuing the insn (it is not
3998 zero for insns in a schedule group). */
4001 schedule_insn (rtx_insn *insn)
4003 sd_iterator_def sd_it;
4008 if (sched_verbose >= 1)
4010 struct reg_pressure_data *pressure_info;
4011 fprintf (sched_dump, ";;\t%3i--> %s %-40s:",
4012 clock_var, (*current_sched_info->print_insn) (insn, 1),
4013 str_pattern_slim (PATTERN (insn)));
4015 if (recog_memoized (insn) < 0)
4016 fprintf (sched_dump, "nothing");
4018 print_reservation (sched_dump, insn);
4019 pressure_info = INSN_REG_PRESSURE (insn);
4020 if (pressure_info != NULL)
4022 fputc (':', sched_dump);
4023 for (i = 0; i < ira_pressure_classes_num; i++)
4024 fprintf (sched_dump, "%s%s%+d(%d)",
4025 scheduled_insns.length () > 1
4027 < INSN_LUID (scheduled_insns[scheduled_insns.length () - 2]) ? "@" : "",
4028 reg_class_names[ira_pressure_classes[i]],
4029 pressure_info[i].set_increase, pressure_info[i].change);
4031 if (sched_pressure == SCHED_PRESSURE_MODEL
4032 && model_curr_point < model_num_insns
4033 && model_index (insn) == model_curr_point)
4034 fprintf (sched_dump, ":model %d", model_curr_point);
4035 fputc ('\n', sched_dump);
4038 if (sched_pressure == SCHED_PRESSURE_WEIGHTED && !DEBUG_INSN_P (insn))
4039 update_reg_and_insn_max_reg_pressure (insn);
4041 /* Scheduling instruction should have all its dependencies resolved and
4042 should have been removed from the ready list. */
4043 gcc_assert (sd_lists_empty_p (insn, SD_LIST_HARD_BACK));
4045 /* Reset debug insns invalidated by moving this insn. */
4046 if (MAY_HAVE_DEBUG_INSNS && !DEBUG_INSN_P (insn))
4047 for (sd_it = sd_iterator_start (insn, SD_LIST_BACK);
4048 sd_iterator_cond (&sd_it, &dep);)
4050 rtx_insn *dbg = DEP_PRO (dep);
4051 struct reg_use_data *use, *next;
4053 if (DEP_STATUS (dep) & DEP_CANCELLED)
4055 sd_iterator_next (&sd_it);
4059 gcc_assert (DEBUG_INSN_P (dbg));
4061 if (sched_verbose >= 6)
4062 fprintf (sched_dump, ";;\t\tresetting: debug insn %d\n",
4065 /* ??? Rather than resetting the debug insn, we might be able
4066 to emit a debug temp before the just-scheduled insn, but
4067 this would involve checking that the expression at the
4068 point of the debug insn is equivalent to the expression
4069 before the just-scheduled insn. They might not be: the
4070 expression in the debug insn may depend on other insns not
4071 yet scheduled that set MEMs, REGs or even other debug
4072 insns. It's not clear that attempting to preserve debug
4073 information in these cases is worth the effort, given how
4074 uncommon these resets are and the likelihood that the debug
4075 temps introduced won't survive the schedule change. */
4076 INSN_VAR_LOCATION_LOC (dbg) = gen_rtx_UNKNOWN_VAR_LOC ();
4077 df_insn_rescan (dbg);
4079 /* Unknown location doesn't use any registers. */
4080 for (use = INSN_REG_USE_LIST (dbg); use != NULL; use = next)
4082 struct reg_use_data *prev = use;
4084 /* Remove use from the cyclic next_regno_use chain first. */
4085 while (prev->next_regno_use != use)
4086 prev = prev->next_regno_use;
4087 prev->next_regno_use = use->next_regno_use;
4088 next = use->next_insn_use;
4091 INSN_REG_USE_LIST (dbg) = NULL;
4093 /* We delete rather than resolve these deps, otherwise we
4094 crash in sched_free_deps(), because forward deps are
4095 expected to be released before backward deps. */
4096 sd_delete_dep (sd_it);
4099 gcc_assert (QUEUE_INDEX (insn) == QUEUE_NOWHERE);
4100 QUEUE_INDEX (insn) = QUEUE_SCHEDULED;
4102 if (sched_pressure == SCHED_PRESSURE_MODEL
4103 && model_curr_point < model_num_insns
4104 && NONDEBUG_INSN_P (insn))
4106 if (model_index (insn) == model_curr_point)
4109 while (model_curr_point < model_num_insns
4110 && (QUEUE_INDEX (MODEL_INSN (model_curr_point))
4111 == QUEUE_SCHEDULED));
4113 model_recompute (insn);
4114 model_update_limit_points ();
4115 update_register_pressure (insn);
4116 if (sched_verbose >= 2)
4117 print_curr_reg_pressure ();
4120 gcc_assert (INSN_TICK (insn) >= MIN_TICK);
4121 if (INSN_TICK (insn) > clock_var)
4122 /* INSN has been prematurely moved from the queue to the ready list.
4123 This is possible only if following flags are set. */
4124 gcc_assert (flag_sched_stalled_insns || sched_fusion);
4126 /* ??? Probably, if INSN is scheduled prematurely, we should leave
4127 INSN_TICK untouched. This is a machine-dependent issue, actually. */
4128 INSN_TICK (insn) = clock_var;
4130 check_clobbered_conditions (insn);
4132 /* Update dependent instructions. First, see if by scheduling this insn
4133 now we broke a dependence in a way that requires us to change another
4135 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
4136 sd_iterator_cond (&sd_it, &dep); sd_iterator_next (&sd_it))
4138 struct dep_replacement *desc = DEP_REPLACE (dep);
4139 rtx_insn *pro = DEP_PRO (dep);
4140 if (QUEUE_INDEX (pro) != QUEUE_SCHEDULED
4141 && desc != NULL && desc->insn == pro)
4142 apply_replacement (dep, false);
4145 /* Go through and resolve forward dependencies. */
4146 for (sd_it = sd_iterator_start (insn, SD_LIST_FORW);
4147 sd_iterator_cond (&sd_it, &dep);)
4149 rtx_insn *next = DEP_CON (dep);
4150 bool cancelled = (DEP_STATUS (dep) & DEP_CANCELLED) != 0;
4152 /* Resolve the dependence between INSN and NEXT.
4153 sd_resolve_dep () moves current dep to another list thus
4154 advancing the iterator. */
4155 sd_resolve_dep (sd_it);
4159 if (must_restore_pattern_p (next, dep))
4160 restore_pattern (dep, false);
4164 /* Don't bother trying to mark next as ready if insn is a debug
4165 insn. If insn is the last hard dependency, it will have
4166 already been discounted. */
4167 if (DEBUG_INSN_P (insn) && !DEBUG_INSN_P (next))
4170 if (!IS_SPECULATION_BRANCHY_CHECK_P (insn))
4174 effective_cost = try_ready (next);
4176 if (effective_cost >= 0
4177 && SCHED_GROUP_P (next)
4178 && advance < effective_cost)
4179 advance = effective_cost;
4182 /* Check always has only one forward dependence (to the first insn in
4183 the recovery block), therefore, this will be executed only once. */
4185 gcc_assert (sd_lists_empty_p (insn, SD_LIST_FORW));
4186 fix_recovery_deps (RECOVERY_BLOCK (insn));
4190 /* Annotate the instruction with issue information -- TImode
4191 indicates that the instruction is expected not to be able
4192 to issue on the same cycle as the previous insn. A machine
4193 may use this information to decide how the instruction should
4196 && GET_CODE (PATTERN (insn)) != USE
4197 && GET_CODE (PATTERN (insn)) != CLOBBER
4198 && !DEBUG_INSN_P (insn))
4200 if (reload_completed)
4201 PUT_MODE (insn, clock_var > last_clock_var ? TImode : VOIDmode);
4202 last_clock_var = clock_var;
4205 if (nonscheduled_insns_begin != NULL_RTX)
4206 /* Indicate to debug counters that INSN is scheduled. */
4207 nonscheduled_insns_begin = insn;
4212 /* Functions for handling of notes. */
4214 /* Add note list that ends on FROM_END to the end of TO_ENDP. */
4216 concat_note_lists (rtx_insn *from_end, rtx_insn **to_endp)
4218 rtx_insn *from_start;
4220 /* It's easy when have nothing to concat. */
4221 if (from_end == NULL)
4224 /* It's also easy when destination is empty. */
4225 if (*to_endp == NULL)
4227 *to_endp = from_end;
4231 from_start = from_end;
4232 while (PREV_INSN (from_start) != NULL)
4233 from_start = PREV_INSN (from_start);
4235 SET_PREV_INSN (from_start) = *to_endp;
4236 SET_NEXT_INSN (*to_endp) = from_start;
4237 *to_endp = from_end;
4240 /* Delete notes between HEAD and TAIL and put them in the chain
4241 of notes ended by NOTE_LIST. */
4243 remove_notes (rtx_insn *head, rtx_insn *tail)
4245 rtx_insn *next_tail, *insn, *next;
4248 if (head == tail && !INSN_P (head))
4251 next_tail = NEXT_INSN (tail);
4252 for (insn = head; insn != next_tail; insn = next)
4254 next = NEXT_INSN (insn);
4258 switch (NOTE_KIND (insn))
4260 case NOTE_INSN_BASIC_BLOCK:
4263 case NOTE_INSN_EPILOGUE_BEG:
4267 add_reg_note (next, REG_SAVE_NOTE,
4268 GEN_INT (NOTE_INSN_EPILOGUE_BEG));
4276 /* Add the note to list that ends at NOTE_LIST. */
4277 SET_PREV_INSN (insn) = note_list;
4278 SET_NEXT_INSN (insn) = NULL_RTX;
4280 SET_NEXT_INSN (note_list) = insn;
4285 gcc_assert ((sel_sched_p () || insn != tail) && insn != head);
4289 /* A structure to record enough data to allow us to backtrack the scheduler to
4290 a previous state. */
4291 struct haifa_saved_data
4293 /* Next entry on the list. */
4294 struct haifa_saved_data *next;
4296 /* Backtracking is associated with scheduling insns that have delay slots.
4297 DELAY_PAIR points to the structure that contains the insns involved, and
4298 the number of cycles between them. */
4299 struct delay_pair *delay_pair;
4301 /* Data used by the frontend (e.g. sched-ebb or sched-rgn). */
4302 void *fe_saved_data;
4303 /* Data used by the backend. */
4304 void *be_saved_data;
4306 /* Copies of global state. */
4307 int clock_var, last_clock_var;
4308 struct ready_list ready;
4311 rtx_insn *last_scheduled_insn;
4312 rtx last_nondebug_scheduled_insn;
4313 rtx_insn *nonscheduled_insns_begin;
4314 int cycle_issued_insns;
4316 /* Copies of state used in the inner loop of schedule_block. */
4317 struct sched_block_state sched_block;
4319 /* We don't need to save q_ptr, as its value is arbitrary and we can set it
4320 to 0 when restoring. */
4322 rtx_insn_list **insn_queue;
4324 /* Describe pattern replacements that occurred since this backtrack point
4326 vec<dep_t> replacement_deps;
4327 vec<int> replace_apply;
4329 /* A copy of the next-cycle replacement vectors at the time of the backtrack
4331 vec<dep_t> next_cycle_deps;
4332 vec<int> next_cycle_apply;
4335 /* A record, in reverse order, of all scheduled insns which have delay slots
4336 and may require backtracking. */
4337 static struct haifa_saved_data *backtrack_queue;
4339 /* For every dependency of INSN, set the FEEDS_BACKTRACK_INSN bit according
4342 mark_backtrack_feeds (rtx insn, int set_p)
4344 sd_iterator_def sd_it;
4346 FOR_EACH_DEP (insn, SD_LIST_HARD_BACK, sd_it, dep)
4348 FEEDS_BACKTRACK_INSN (DEP_PRO (dep)) = set_p;
4352 /* Save the current scheduler state so that we can backtrack to it
4353 later if necessary. PAIR gives the insns that make it necessary to
4354 save this point. SCHED_BLOCK is the local state of schedule_block
4355 that need to be saved. */
4357 save_backtrack_point (struct delay_pair *pair,
4358 struct sched_block_state sched_block)
4361 struct haifa_saved_data *save = XNEW (struct haifa_saved_data);
4363 save->curr_state = xmalloc (dfa_state_size);
4364 memcpy (save->curr_state, curr_state, dfa_state_size);
4366 save->ready.first = ready.first;
4367 save->ready.n_ready = ready.n_ready;
4368 save->ready.n_debug = ready.n_debug;
4369 save->ready.veclen = ready.veclen;
4370 save->ready.vec = XNEWVEC (rtx_insn *, ready.veclen);
4371 memcpy (save->ready.vec, ready.vec, ready.veclen * sizeof (rtx));
4373 save->insn_queue = XNEWVEC (rtx_insn_list *, max_insn_queue_index + 1);
4374 save->q_size = q_size;
4375 for (i = 0; i <= max_insn_queue_index; i++)
4377 int q = NEXT_Q_AFTER (q_ptr, i);
4378 save->insn_queue[i] = copy_INSN_LIST (insn_queue[q]);
4381 save->clock_var = clock_var;
4382 save->last_clock_var = last_clock_var;
4383 save->cycle_issued_insns = cycle_issued_insns;
4384 save->last_scheduled_insn = last_scheduled_insn;
4385 save->last_nondebug_scheduled_insn = last_nondebug_scheduled_insn;
4386 save->nonscheduled_insns_begin = nonscheduled_insns_begin;
4388 save->sched_block = sched_block;
4390 save->replacement_deps.create (0);
4391 save->replace_apply.create (0);
4392 save->next_cycle_deps = next_cycle_replace_deps.copy ();
4393 save->next_cycle_apply = next_cycle_apply.copy ();
4395 if (current_sched_info->save_state)
4396 save->fe_saved_data = (*current_sched_info->save_state) ();
4398 if (targetm.sched.alloc_sched_context)
4400 save->be_saved_data = targetm.sched.alloc_sched_context ();
4401 targetm.sched.init_sched_context (save->be_saved_data, false);
4404 save->be_saved_data = NULL;
4406 save->delay_pair = pair;
4408 save->next = backtrack_queue;
4409 backtrack_queue = save;
4413 mark_backtrack_feeds (pair->i2, 1);
4414 INSN_TICK (pair->i2) = INVALID_TICK;
4415 INSN_EXACT_TICK (pair->i2) = clock_var + pair_delay (pair);
4416 SHADOW_P (pair->i2) = pair->stages == 0;
4417 pair = pair->next_same_i1;
4421 /* Walk the ready list and all queues. If any insns have unresolved backwards
4422 dependencies, these must be cancelled deps, broken by predication. Set or
4423 clear (depending on SET) the DEP_CANCELLED bit in DEP_STATUS. */
4426 toggle_cancelled_flags (bool set)
4429 sd_iterator_def sd_it;
4432 if (ready.n_ready > 0)
4434 rtx_insn **first = ready_lastpos (&ready);
4435 for (i = 0; i < ready.n_ready; i++)
4436 FOR_EACH_DEP (first[i], SD_LIST_BACK, sd_it, dep)
4437 if (!DEBUG_INSN_P (DEP_PRO (dep)))
4440 DEP_STATUS (dep) |= DEP_CANCELLED;
4442 DEP_STATUS (dep) &= ~DEP_CANCELLED;
4445 for (i = 0; i <= max_insn_queue_index; i++)
4447 int q = NEXT_Q_AFTER (q_ptr, i);
4448 rtx_insn_list *link;
4449 for (link = insn_queue[q]; link; link = link->next ())
4451 rtx_insn *insn = link->insn ();
4452 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
4453 if (!DEBUG_INSN_P (DEP_PRO (dep)))
4456 DEP_STATUS (dep) |= DEP_CANCELLED;
4458 DEP_STATUS (dep) &= ~DEP_CANCELLED;
4464 /* Undo the replacements that have occurred after backtrack point SAVE
4467 undo_replacements_for_backtrack (struct haifa_saved_data *save)
4469 while (!save->replacement_deps.is_empty ())
4471 dep_t dep = save->replacement_deps.pop ();
4472 int apply_p = save->replace_apply.pop ();
4475 restore_pattern (dep, true);
4477 apply_replacement (dep, true);
4479 save->replacement_deps.release ();
4480 save->replace_apply.release ();
4483 /* Pop entries from the SCHEDULED_INSNS vector up to and including INSN.
4484 Restore their dependencies to an unresolved state, and mark them as
4488 unschedule_insns_until (rtx insn)
4490 auto_vec<rtx_insn *> recompute_vec;
4492 /* Make two passes over the insns to be unscheduled. First, we clear out
4493 dependencies and other trivial bookkeeping. */
4497 sd_iterator_def sd_it;
4500 last = scheduled_insns.pop ();
4502 /* This will be changed by restore_backtrack_point if the insn is in
4504 QUEUE_INDEX (last) = QUEUE_NOWHERE;
4506 INSN_TICK (last) = INVALID_TICK;
4508 if (modulo_ii > 0 && INSN_UID (last) < modulo_iter0_max_uid)
4509 modulo_insns_scheduled--;
4511 for (sd_it = sd_iterator_start (last, SD_LIST_RES_FORW);
4512 sd_iterator_cond (&sd_it, &dep);)
4514 rtx_insn *con = DEP_CON (dep);
4515 sd_unresolve_dep (sd_it);
4516 if (!MUST_RECOMPUTE_SPEC_P (con))
4518 MUST_RECOMPUTE_SPEC_P (con) = 1;
4519 recompute_vec.safe_push (con);
4527 /* A second pass, to update ready and speculation status for insns
4528 depending on the unscheduled ones. The first pass must have
4529 popped the scheduled_insns vector up to the point where we
4530 restart scheduling, as recompute_todo_spec requires it to be
4532 while (!recompute_vec.is_empty ())
4536 con = recompute_vec.pop ();
4537 MUST_RECOMPUTE_SPEC_P (con) = 0;
4538 if (!sd_lists_empty_p (con, SD_LIST_HARD_BACK))
4540 TODO_SPEC (con) = HARD_DEP;
4541 INSN_TICK (con) = INVALID_TICK;
4542 if (PREDICATED_PAT (con) != NULL_RTX)
4543 haifa_change_pattern (con, ORIG_PAT (con));
4545 else if (QUEUE_INDEX (con) != QUEUE_SCHEDULED)
4546 TODO_SPEC (con) = recompute_todo_spec (con, true);
4550 /* Restore scheduler state from the topmost entry on the backtracking queue.
4551 PSCHED_BLOCK_P points to the local data of schedule_block that we must
4552 overwrite with the saved data.
4553 The caller must already have called unschedule_insns_until. */
4556 restore_last_backtrack_point (struct sched_block_state *psched_block)
4559 struct haifa_saved_data *save = backtrack_queue;
4561 backtrack_queue = save->next;
4563 if (current_sched_info->restore_state)
4564 (*current_sched_info->restore_state) (save->fe_saved_data);
4566 if (targetm.sched.alloc_sched_context)
4568 targetm.sched.set_sched_context (save->be_saved_data);
4569 targetm.sched.free_sched_context (save->be_saved_data);
4572 /* Do this first since it clobbers INSN_TICK of the involved
4574 undo_replacements_for_backtrack (save);
4576 /* Clear the QUEUE_INDEX of everything in the ready list or one
4578 if (ready.n_ready > 0)
4580 rtx_insn **first = ready_lastpos (&ready);
4581 for (i = 0; i < ready.n_ready; i++)
4583 rtx_insn *insn = first[i];
4584 QUEUE_INDEX (insn) = QUEUE_NOWHERE;
4585 INSN_TICK (insn) = INVALID_TICK;
4588 for (i = 0; i <= max_insn_queue_index; i++)
4590 int q = NEXT_Q_AFTER (q_ptr, i);
4592 for (rtx_insn_list *link = insn_queue[q]; link; link = link->next ())
4594 rtx_insn *x = link->insn ();
4595 QUEUE_INDEX (x) = QUEUE_NOWHERE;
4596 INSN_TICK (x) = INVALID_TICK;
4598 free_INSN_LIST_list (&insn_queue[q]);
4602 ready = save->ready;
4604 if (ready.n_ready > 0)
4606 rtx_insn **first = ready_lastpos (&ready);
4607 for (i = 0; i < ready.n_ready; i++)
4609 rtx_insn *insn = first[i];
4610 QUEUE_INDEX (insn) = QUEUE_READY;
4611 TODO_SPEC (insn) = recompute_todo_spec (insn, true);
4612 INSN_TICK (insn) = save->clock_var;
4617 q_size = save->q_size;
4618 for (i = 0; i <= max_insn_queue_index; i++)
4620 int q = NEXT_Q_AFTER (q_ptr, i);
4622 insn_queue[q] = save->insn_queue[q];
4624 for (rtx_insn_list *link = insn_queue[q]; link; link = link->next ())
4626 rtx_insn *x = link->insn ();
4627 QUEUE_INDEX (x) = i;
4628 TODO_SPEC (x) = recompute_todo_spec (x, true);
4629 INSN_TICK (x) = save->clock_var + i;
4632 free (save->insn_queue);
4634 toggle_cancelled_flags (true);
4636 clock_var = save->clock_var;
4637 last_clock_var = save->last_clock_var;
4638 cycle_issued_insns = save->cycle_issued_insns;
4639 last_scheduled_insn = save->last_scheduled_insn;
4640 last_nondebug_scheduled_insn = save->last_nondebug_scheduled_insn;
4641 nonscheduled_insns_begin = save->nonscheduled_insns_begin;
4643 *psched_block = save->sched_block;
4645 memcpy (curr_state, save->curr_state, dfa_state_size);
4646 free (save->curr_state);
4648 mark_backtrack_feeds (save->delay_pair->i2, 0);
4650 gcc_assert (next_cycle_replace_deps.is_empty ());
4651 next_cycle_replace_deps = save->next_cycle_deps.copy ();
4652 next_cycle_apply = save->next_cycle_apply.copy ();
4656 for (save = backtrack_queue; save; save = save->next)
4658 mark_backtrack_feeds (save->delay_pair->i2, 1);
4662 /* Discard all data associated with the topmost entry in the backtrack
4663 queue. If RESET_TICK is false, we just want to free the data. If true,
4664 we are doing this because we discovered a reason to backtrack. In the
4665 latter case, also reset the INSN_TICK for the shadow insn. */
4667 free_topmost_backtrack_point (bool reset_tick)
4669 struct haifa_saved_data *save = backtrack_queue;
4672 backtrack_queue = save->next;
4676 struct delay_pair *pair = save->delay_pair;
4679 INSN_TICK (pair->i2) = INVALID_TICK;
4680 INSN_EXACT_TICK (pair->i2) = INVALID_TICK;
4681 pair = pair->next_same_i1;
4683 undo_replacements_for_backtrack (save);
4687 save->replacement_deps.release ();
4688 save->replace_apply.release ();
4691 if (targetm.sched.free_sched_context)
4692 targetm.sched.free_sched_context (save->be_saved_data);
4693 if (current_sched_info->restore_state)
4694 free (save->fe_saved_data);
4695 for (i = 0; i <= max_insn_queue_index; i++)
4696 free_INSN_LIST_list (&save->insn_queue[i]);
4697 free (save->insn_queue);
4698 free (save->curr_state);
4699 free (save->ready.vec);
4703 /* Free the entire backtrack queue. */
4705 free_backtrack_queue (void)
4707 while (backtrack_queue)
4708 free_topmost_backtrack_point (false);
4711 /* Apply a replacement described by DESC. If IMMEDIATELY is false, we
4712 may have to postpone the replacement until the start of the next cycle,
4713 at which point we will be called again with IMMEDIATELY true. This is
4714 only done for machines which have instruction packets with explicit
4715 parallelism however. */
4717 apply_replacement (dep_t dep, bool immediately)
4719 struct dep_replacement *desc = DEP_REPLACE (dep);
4720 if (!immediately && targetm.sched.exposed_pipeline && reload_completed)
4722 next_cycle_replace_deps.safe_push (dep);
4723 next_cycle_apply.safe_push (1);
4729 if (QUEUE_INDEX (desc->insn) == QUEUE_SCHEDULED)
4732 if (sched_verbose >= 5)
4733 fprintf (sched_dump, "applying replacement for insn %d\n",
4734 INSN_UID (desc->insn));
4736 success = validate_change (desc->insn, desc->loc, desc->newval, 0);
4737 gcc_assert (success);
4739 update_insn_after_change (desc->insn);
4740 if ((TODO_SPEC (desc->insn) & (HARD_DEP | DEP_POSTPONED)) == 0)
4741 fix_tick_ready (desc->insn);
4743 if (backtrack_queue != NULL)
4745 backtrack_queue->replacement_deps.safe_push (dep);
4746 backtrack_queue->replace_apply.safe_push (1);
4751 /* We have determined that a pattern involved in DEP must be restored.
4752 If IMMEDIATELY is false, we may have to postpone the replacement
4753 until the start of the next cycle, at which point we will be called
4754 again with IMMEDIATELY true. */
4756 restore_pattern (dep_t dep, bool immediately)
4758 rtx_insn *next = DEP_CON (dep);
4759 int tick = INSN_TICK (next);
4761 /* If we already scheduled the insn, the modified version is
4763 if (QUEUE_INDEX (next) == QUEUE_SCHEDULED)
4766 if (!immediately && targetm.sched.exposed_pipeline && reload_completed)
4768 next_cycle_replace_deps.safe_push (dep);
4769 next_cycle_apply.safe_push (0);
4774 if (DEP_TYPE (dep) == REG_DEP_CONTROL)
4776 if (sched_verbose >= 5)
4777 fprintf (sched_dump, "restoring pattern for insn %d\n",
4779 haifa_change_pattern (next, ORIG_PAT (next));
4783 struct dep_replacement *desc = DEP_REPLACE (dep);
4786 if (sched_verbose >= 5)
4787 fprintf (sched_dump, "restoring pattern for insn %d\n",
4788 INSN_UID (desc->insn));
4789 tick = INSN_TICK (desc->insn);
4791 success = validate_change (desc->insn, desc->loc, desc->orig, 0);
4792 gcc_assert (success);
4793 update_insn_after_change (desc->insn);
4794 if (backtrack_queue != NULL)
4796 backtrack_queue->replacement_deps.safe_push (dep);
4797 backtrack_queue->replace_apply.safe_push (0);
4800 INSN_TICK (next) = tick;
4801 if (TODO_SPEC (next) == DEP_POSTPONED)
4804 if (sd_lists_empty_p (next, SD_LIST_BACK))
4805 TODO_SPEC (next) = 0;
4806 else if (!sd_lists_empty_p (next, SD_LIST_HARD_BACK))
4807 TODO_SPEC (next) = HARD_DEP;
4810 /* Perform pattern replacements that were queued up until the next
4813 perform_replacements_new_cycle (void)
4817 FOR_EACH_VEC_ELT (next_cycle_replace_deps, i, dep)
4819 int apply_p = next_cycle_apply[i];
4821 apply_replacement (dep, true);
4823 restore_pattern (dep, true);
4825 next_cycle_replace_deps.truncate (0);
4826 next_cycle_apply.truncate (0);
4829 /* Compute INSN_TICK_ESTIMATE for INSN. PROCESSED is a bitmap of
4830 instructions we've previously encountered, a set bit prevents
4831 recursion. BUDGET is a limit on how far ahead we look, it is
4832 reduced on recursive calls. Return true if we produced a good
4833 estimate, or false if we exceeded the budget. */
4835 estimate_insn_tick (bitmap processed, rtx_insn *insn, int budget)
4837 sd_iterator_def sd_it;
4839 int earliest = INSN_TICK (insn);
4841 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
4843 rtx_insn *pro = DEP_PRO (dep);
4846 if (DEP_STATUS (dep) & DEP_CANCELLED)
4849 if (QUEUE_INDEX (pro) == QUEUE_SCHEDULED)
4850 gcc_assert (INSN_TICK (pro) + dep_cost (dep) <= INSN_TICK (insn));
4853 int cost = dep_cost (dep);
4856 if (!bitmap_bit_p (processed, INSN_LUID (pro)))
4858 if (!estimate_insn_tick (processed, pro, budget - cost))
4861 gcc_assert (INSN_TICK_ESTIMATE (pro) != INVALID_TICK);
4862 t = INSN_TICK_ESTIMATE (pro) + cost;
4863 if (earliest == INVALID_TICK || t > earliest)
4867 bitmap_set_bit (processed, INSN_LUID (insn));
4868 INSN_TICK_ESTIMATE (insn) = earliest;
4872 /* Examine the pair of insns in P, and estimate (optimistically, assuming
4873 infinite resources) the cycle in which the delayed shadow can be issued.
4874 Return the number of cycles that must pass before the real insn can be
4875 issued in order to meet this constraint. */
4877 estimate_shadow_tick (struct delay_pair *p)
4879 bitmap_head processed;
4882 bitmap_initialize (&processed, 0);
4884 cutoff = !estimate_insn_tick (&processed, p->i2,
4885 max_insn_queue_index + pair_delay (p));
4886 bitmap_clear (&processed);
4888 return max_insn_queue_index;
4889 t = INSN_TICK_ESTIMATE (p->i2) - (clock_var + pair_delay (p) + 1);
4895 /* If INSN has no unresolved backwards dependencies, add it to the schedule and
4896 recursively resolve all its forward dependencies. */
4898 resolve_dependencies (rtx_insn *insn)
4900 sd_iterator_def sd_it;
4903 /* Don't use sd_lists_empty_p; it ignores debug insns. */
4904 if (DEPS_LIST_FIRST (INSN_HARD_BACK_DEPS (insn)) != NULL
4905 || DEPS_LIST_FIRST (INSN_SPEC_BACK_DEPS (insn)) != NULL)
4908 if (sched_verbose >= 4)
4909 fprintf (sched_dump, ";;\tquickly resolving %d\n", INSN_UID (insn));
4911 if (QUEUE_INDEX (insn) >= 0)
4912 queue_remove (insn);
4914 scheduled_insns.safe_push (insn);
4916 /* Update dependent instructions. */
4917 for (sd_it = sd_iterator_start (insn, SD_LIST_FORW);
4918 sd_iterator_cond (&sd_it, &dep);)
4920 rtx_insn *next = DEP_CON (dep);
4922 if (sched_verbose >= 4)
4923 fprintf (sched_dump, ";;\t\tdep %d against %d\n", INSN_UID (insn),
4926 /* Resolve the dependence between INSN and NEXT.
4927 sd_resolve_dep () moves current dep to another list thus
4928 advancing the iterator. */
4929 sd_resolve_dep (sd_it);
4931 if (!IS_SPECULATION_BRANCHY_CHECK_P (insn))
4933 resolve_dependencies (next);
4936 /* Check always has only one forward dependence (to the first insn in
4937 the recovery block), therefore, this will be executed only once. */
4939 gcc_assert (sd_lists_empty_p (insn, SD_LIST_FORW));
4945 /* Return the head and tail pointers of ebb starting at BEG and ending
4948 get_ebb_head_tail (basic_block beg, basic_block end,
4949 rtx_insn **headp, rtx_insn **tailp)
4951 rtx_insn *beg_head = BB_HEAD (beg);
4952 rtx_insn * beg_tail = BB_END (beg);
4953 rtx_insn * end_head = BB_HEAD (end);
4954 rtx_insn * end_tail = BB_END (end);
4956 /* Don't include any notes or labels at the beginning of the BEG
4957 basic block, or notes at the end of the END basic blocks. */
4959 if (LABEL_P (beg_head))
4960 beg_head = NEXT_INSN (beg_head);
4962 while (beg_head != beg_tail)
4963 if (NOTE_P (beg_head))
4964 beg_head = NEXT_INSN (beg_head);
4965 else if (DEBUG_INSN_P (beg_head))
4967 rtx_insn * note, *next;
4969 for (note = NEXT_INSN (beg_head);
4973 next = NEXT_INSN (note);
4976 if (sched_verbose >= 9)
4977 fprintf (sched_dump, "reorder %i\n", INSN_UID (note));
4979 reorder_insns_nobb (note, note, PREV_INSN (beg_head));
4981 if (BLOCK_FOR_INSN (note) != beg)
4982 df_insn_change_bb (note, beg);
4984 else if (!DEBUG_INSN_P (note))
4996 end_head = beg_head;
4997 else if (LABEL_P (end_head))
4998 end_head = NEXT_INSN (end_head);
5000 while (end_head != end_tail)
5001 if (NOTE_P (end_tail))
5002 end_tail = PREV_INSN (end_tail);
5003 else if (DEBUG_INSN_P (end_tail))
5005 rtx_insn * note, *prev;
5007 for (note = PREV_INSN (end_tail);
5011 prev = PREV_INSN (note);
5014 if (sched_verbose >= 9)
5015 fprintf (sched_dump, "reorder %i\n", INSN_UID (note));
5017 reorder_insns_nobb (note, note, end_tail);
5019 if (end_tail == BB_END (end))
5020 BB_END (end) = note;
5022 if (BLOCK_FOR_INSN (note) != end)
5023 df_insn_change_bb (note, end);
5025 else if (!DEBUG_INSN_P (note))
5037 /* Return nonzero if there are no real insns in the range [ HEAD, TAIL ]. */
5040 no_real_insns_p (const rtx_insn *head, const rtx_insn *tail)
5042 while (head != NEXT_INSN (tail))
5044 if (!NOTE_P (head) && !LABEL_P (head))
5046 head = NEXT_INSN (head);
5051 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
5052 previously found among the insns. Insert them just before HEAD. */
5054 restore_other_notes (rtx_insn *head, basic_block head_bb)
5058 rtx_insn *note_head = note_list;
5061 head_bb = BLOCK_FOR_INSN (head);
5063 head = NEXT_INSN (bb_note (head_bb));
5065 while (PREV_INSN (note_head))
5067 set_block_for_insn (note_head, head_bb);
5068 note_head = PREV_INSN (note_head);
5070 /* In the above cycle we've missed this note. */
5071 set_block_for_insn (note_head, head_bb);
5073 SET_PREV_INSN (note_head) = PREV_INSN (head);
5074 SET_NEXT_INSN (PREV_INSN (head)) = note_head;
5075 SET_PREV_INSN (head) = note_list;
5076 SET_NEXT_INSN (note_list) = head;
5078 if (BLOCK_FOR_INSN (head) != head_bb)
5079 BB_END (head_bb) = note_list;
5087 /* When we know we are going to discard the schedule due to a failed attempt
5088 at modulo scheduling, undo all replacements. */
5090 undo_all_replacements (void)
5095 FOR_EACH_VEC_ELT (scheduled_insns, i, insn)
5097 sd_iterator_def sd_it;
5100 /* See if we must undo a replacement. */
5101 for (sd_it = sd_iterator_start (insn, SD_LIST_RES_FORW);
5102 sd_iterator_cond (&sd_it, &dep); sd_iterator_next (&sd_it))
5104 struct dep_replacement *desc = DEP_REPLACE (dep);
5106 validate_change (desc->insn, desc->loc, desc->orig, 0);
5111 /* Return first non-scheduled insn in the current scheduling block.
5112 This is mostly used for debug-counter purposes. */
5114 first_nonscheduled_insn (void)
5116 rtx_insn *insn = (nonscheduled_insns_begin != NULL_RTX
5117 ? nonscheduled_insns_begin
5118 : current_sched_info->prev_head);
5122 insn = next_nonnote_nondebug_insn (insn);
5124 while (QUEUE_INDEX (insn) == QUEUE_SCHEDULED);
5129 /* Move insns that became ready to fire from queue to ready list. */
5132 queue_to_ready (struct ready_list *ready)
5135 rtx_insn_list *link;
5138 q_ptr = NEXT_Q (q_ptr);
5140 if (dbg_cnt (sched_insn) == false)
5141 /* If debug counter is activated do not requeue the first
5142 nonscheduled insn. */
5143 skip_insn = first_nonscheduled_insn ();
5145 skip_insn = NULL_RTX;
5147 /* Add all pending insns that can be scheduled without stalls to the
5149 for (link = insn_queue[q_ptr]; link; link = link->next ())
5151 insn = link->insn ();
5154 if (sched_verbose >= 2)
5155 fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
5156 (*current_sched_info->print_insn) (insn, 0));
5158 /* If the ready list is full, delay the insn for 1 cycle.
5159 See the comment in schedule_block for the rationale. */
5160 if (!reload_completed
5161 && (ready->n_ready - ready->n_debug > MAX_SCHED_READY_INSNS
5162 || (sched_pressure == SCHED_PRESSURE_MODEL
5163 /* Limit pressure recalculations to MAX_SCHED_READY_INSNS
5164 instructions too. */
5165 && model_index (insn) > (model_curr_point
5166 + MAX_SCHED_READY_INSNS)))
5167 && !(sched_pressure == SCHED_PRESSURE_MODEL
5168 && model_curr_point < model_num_insns
5169 /* Always allow the next model instruction to issue. */
5170 && model_index (insn) == model_curr_point)
5171 && !SCHED_GROUP_P (insn)
5172 && insn != skip_insn)
5174 if (sched_verbose >= 2)
5175 fprintf (sched_dump, "keeping in queue, ready full\n");
5176 queue_insn (insn, 1, "ready full");
5180 ready_add (ready, insn, false);
5181 if (sched_verbose >= 2)
5182 fprintf (sched_dump, "moving to ready without stalls\n");
5185 free_INSN_LIST_list (&insn_queue[q_ptr]);
5187 /* If there are no ready insns, stall until one is ready and add all
5188 of the pending insns at that point to the ready list. */
5189 if (ready->n_ready == 0)
5193 for (stalls = 1; stalls <= max_insn_queue_index; stalls++)
5195 if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
5197 for (; link; link = link->next ())
5199 insn = link->insn ();
5202 if (sched_verbose >= 2)
5203 fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
5204 (*current_sched_info->print_insn) (insn, 0));
5206 ready_add (ready, insn, false);
5207 if (sched_verbose >= 2)
5208 fprintf (sched_dump, "moving to ready with %d stalls\n", stalls);
5210 free_INSN_LIST_list (&insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]);
5212 advance_one_cycle ();
5217 advance_one_cycle ();
5220 q_ptr = NEXT_Q_AFTER (q_ptr, stalls);
5221 clock_var += stalls;
5222 if (sched_verbose >= 2)
5223 fprintf (sched_dump, ";;\tAdvancing clock by %d cycle[s] to %d\n",
5228 /* Used by early_queue_to_ready. Determines whether it is "ok" to
5229 prematurely move INSN from the queue to the ready list. Currently,
5230 if a target defines the hook 'is_costly_dependence', this function
5231 uses the hook to check whether there exist any dependences which are
5232 considered costly by the target, between INSN and other insns that
5233 have already been scheduled. Dependences are checked up to Y cycles
5234 back, with default Y=1; The flag -fsched-stalled-insns-dep=Y allows
5235 controlling this value.
5236 (Other considerations could be taken into account instead (or in
5237 addition) depending on user flags and target hooks. */
5240 ok_for_early_queue_removal (rtx insn)
5242 if (targetm.sched.is_costly_dependence)
5246 int i = scheduled_insns.length ();
5247 for (n_cycles = flag_sched_stalled_insns_dep; n_cycles; n_cycles--)
5253 prev_insn = scheduled_insns[i];
5255 if (!NOTE_P (prev_insn))
5259 dep = sd_find_dep_between (prev_insn, insn, true);
5263 cost = dep_cost (dep);
5265 if (targetm.sched.is_costly_dependence (dep, cost,
5266 flag_sched_stalled_insns_dep - n_cycles))
5271 if (GET_MODE (prev_insn) == TImode) /* end of dispatch group */
5284 /* Remove insns from the queue, before they become "ready" with respect
5285 to FU latency considerations. */
5288 early_queue_to_ready (state_t state, struct ready_list *ready)
5291 rtx_insn_list *link;
5292 rtx_insn_list *next_link;
5293 rtx_insn_list *prev_link;
5296 state_t temp_state = alloca (dfa_state_size);
5298 int insns_removed = 0;
5301 Flag '-fsched-stalled-insns=X' determines the aggressiveness of this
5304 X == 0: There is no limit on how many queued insns can be removed
5305 prematurely. (flag_sched_stalled_insns = -1).
5307 X >= 1: Only X queued insns can be removed prematurely in each
5308 invocation. (flag_sched_stalled_insns = X).
5310 Otherwise: Early queue removal is disabled.
5311 (flag_sched_stalled_insns = 0)
5314 if (! flag_sched_stalled_insns)
5317 for (stalls = 0; stalls <= max_insn_queue_index; stalls++)
5319 if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
5321 if (sched_verbose > 6)
5322 fprintf (sched_dump, ";; look at index %d + %d\n", q_ptr, stalls);
5327 next_link = link->next ();
5328 insn = link->insn ();
5329 if (insn && sched_verbose > 6)
5330 print_rtl_single (sched_dump, insn);
5332 memcpy (temp_state, state, dfa_state_size);
5333 if (recog_memoized (insn) < 0)
5334 /* non-negative to indicate that it's not ready
5335 to avoid infinite Q->R->Q->R... */
5338 cost = state_transition (temp_state, insn);
5340 if (sched_verbose >= 6)
5341 fprintf (sched_dump, "transition cost = %d\n", cost);
5343 move_to_ready = false;
5346 move_to_ready = ok_for_early_queue_removal (insn);
5347 if (move_to_ready == true)
5349 /* move from Q to R */
5351 ready_add (ready, insn, false);
5354 XEXP (prev_link, 1) = next_link;
5356 insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = next_link;
5358 free_INSN_LIST_node (link);
5360 if (sched_verbose >= 2)
5361 fprintf (sched_dump, ";;\t\tEarly Q-->Ready: insn %s\n",
5362 (*current_sched_info->print_insn) (insn, 0));
5365 if (insns_removed == flag_sched_stalled_insns)
5366 /* Remove no more than flag_sched_stalled_insns insns
5367 from Q at a time. */
5368 return insns_removed;
5372 if (move_to_ready == false)
5379 } /* for stalls.. */
5381 return insns_removed;
5385 /* Print the ready list for debugging purposes.
5386 If READY_TRY is non-zero then only print insns that max_issue
5389 debug_ready_list_1 (struct ready_list *ready, signed char *ready_try)
5394 if (ready->n_ready == 0)
5396 fprintf (sched_dump, "\n");
5400 p = ready_lastpos (ready);
5401 for (i = 0; i < ready->n_ready; i++)
5403 if (ready_try != NULL && ready_try[ready->n_ready - i - 1])
5406 fprintf (sched_dump, " %s:%d",
5407 (*current_sched_info->print_insn) (p[i], 0),
5409 if (sched_pressure != SCHED_PRESSURE_NONE)
5410 fprintf (sched_dump, "(cost=%d",
5411 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (p[i]));
5412 fprintf (sched_dump, ":prio=%d", INSN_PRIORITY (p[i]));
5413 if (INSN_TICK (p[i]) > clock_var)
5414 fprintf (sched_dump, ":delay=%d", INSN_TICK (p[i]) - clock_var);
5415 if (sched_pressure == SCHED_PRESSURE_MODEL)
5416 fprintf (sched_dump, ":idx=%d",
5417 model_index (p[i]));
5418 if (sched_pressure != SCHED_PRESSURE_NONE)
5419 fprintf (sched_dump, ")");
5421 fprintf (sched_dump, "\n");
5424 /* Print the ready list. Callable from debugger. */
5426 debug_ready_list (struct ready_list *ready)
5428 debug_ready_list_1 (ready, NULL);
5431 /* Search INSN for REG_SAVE_NOTE notes and convert them back into insn
5432 NOTEs. This is used for NOTE_INSN_EPILOGUE_BEG, so that sched-ebb
5433 replaces the epilogue note in the correct basic block. */
5435 reemit_notes (rtx_insn *insn)
5438 rtx_insn *last = insn;
5440 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
5442 if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
5444 enum insn_note note_type = (enum insn_note) INTVAL (XEXP (note, 0));
5446 last = emit_note_before (note_type, last);
5447 remove_note (insn, note);
5452 /* Move INSN. Reemit notes if needed. Update CFG, if needed. */
5454 move_insn (rtx_insn *insn, rtx_insn *last, rtx nt)
5456 if (PREV_INSN (insn) != last)
5462 bb = BLOCK_FOR_INSN (insn);
5464 /* BB_HEAD is either LABEL or NOTE. */
5465 gcc_assert (BB_HEAD (bb) != insn);
5467 if (BB_END (bb) == insn)
5468 /* If this is last instruction in BB, move end marker one
5471 /* Jumps are always placed at the end of basic block. */
5472 jump_p = control_flow_insn_p (insn);
5475 || ((common_sched_info->sched_pass_id == SCHED_RGN_PASS)
5476 && IS_SPECULATION_BRANCHY_CHECK_P (insn))
5477 || (common_sched_info->sched_pass_id
5478 == SCHED_EBB_PASS));
5480 gcc_assert (BLOCK_FOR_INSN (PREV_INSN (insn)) == bb);
5482 BB_END (bb) = PREV_INSN (insn);
5485 gcc_assert (BB_END (bb) != last);
5488 /* We move the block note along with jump. */
5492 note = NEXT_INSN (insn);
5493 while (NOTE_NOT_BB_P (note) && note != nt)
5494 note = NEXT_INSN (note);
5498 || BARRIER_P (note)))
5499 note = NEXT_INSN (note);
5501 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
5506 SET_NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (note);
5507 SET_PREV_INSN (NEXT_INSN (note)) = PREV_INSN (insn);
5509 SET_NEXT_INSN (note) = NEXT_INSN (last);
5510 SET_PREV_INSN (NEXT_INSN (last)) = note;
5512 SET_NEXT_INSN (last) = insn;
5513 SET_PREV_INSN (insn) = last;
5515 bb = BLOCK_FOR_INSN (last);
5519 fix_jump_move (insn);
5521 if (BLOCK_FOR_INSN (insn) != bb)
5522 move_block_after_check (insn);
5524 gcc_assert (BB_END (bb) == last);
5527 df_insn_change_bb (insn, bb);
5529 /* Update BB_END, if needed. */
5530 if (BB_END (bb) == last)
5534 SCHED_GROUP_P (insn) = 0;
5537 /* Return true if scheduling INSN will finish current clock cycle. */
5539 insn_finishes_cycle_p (rtx_insn *insn)
5541 if (SCHED_GROUP_P (insn))
5542 /* After issuing INSN, rest of the sched_group will be forced to issue
5543 in order. Don't make any plans for the rest of cycle. */
5546 /* Finishing the block will, apparently, finish the cycle. */
5547 if (current_sched_info->insn_finishes_block_p
5548 && current_sched_info->insn_finishes_block_p (insn))
5554 /* Functions to model cache auto-prefetcher.
5556 Some of the CPUs have cache auto-prefetcher, which /seems/ to initiate
5557 memory prefetches if it sees instructions with consequitive memory accesses
5558 in the instruction stream. Details of such hardware units are not published,
5559 so we can only guess what exactly is going on there.
5560 In the scheduler, we model abstract auto-prefetcher. If there are memory
5561 insns in the ready list (or the queue) that have same memory base, but
5562 different offsets, then we delay the insns with larger offsets until insns
5563 with smaller offsets get scheduled. If PARAM_SCHED_AUTOPREF_QUEUE_DEPTH
5564 is "1", then we look at the ready list; if it is N>1, then we also look
5565 through N-1 queue entries.
5566 If the param is N>=0, then rank_for_schedule will consider auto-prefetching
5567 among its heuristics.
5568 Param value of "-1" disables modelling of the auto-prefetcher. */
5570 /* Initialize autoprefetcher model data for INSN. */
5572 autopref_multipass_init (const rtx_insn *insn, int write)
5574 autopref_multipass_data_t data = &INSN_AUTOPREF_MULTIPASS_DATA (insn)[write];
5576 gcc_assert (data->status == AUTOPREF_MULTIPASS_DATA_UNINITIALIZED);
5577 data->base = NULL_RTX;
5579 /* Set insn entry initialized, but not relevant for auto-prefetcher. */
5580 data->status = AUTOPREF_MULTIPASS_DATA_IRRELEVANT;
5582 rtx set = single_set (insn);
5583 if (set == NULL_RTX)
5586 rtx mem = write ? SET_DEST (set) : SET_SRC (set);
5590 struct address_info info;
5591 decompose_mem_address (&info, mem);
5593 /* TODO: Currently only (base+const) addressing is supported. */
5594 if (info.base == NULL || !REG_P (*info.base)
5595 || (info.disp != NULL && !CONST_INT_P (*info.disp)))
5598 /* This insn is relevant for auto-prefetcher. */
5599 data->base = *info.base;
5600 data->offset = info.disp ? INTVAL (*info.disp) : 0;
5601 data->status = AUTOPREF_MULTIPASS_DATA_NORMAL;
5604 /* Helper function for rank_for_schedule sorting. */
5606 autopref_rank_for_schedule (const rtx_insn *insn1, const rtx_insn *insn2)
5608 for (int write = 0; write < 2; ++write)
5610 autopref_multipass_data_t data1
5611 = &INSN_AUTOPREF_MULTIPASS_DATA (insn1)[write];
5612 autopref_multipass_data_t data2
5613 = &INSN_AUTOPREF_MULTIPASS_DATA (insn2)[write];
5615 if (data1->status == AUTOPREF_MULTIPASS_DATA_UNINITIALIZED)
5616 autopref_multipass_init (insn1, write);
5617 if (data1->status == AUTOPREF_MULTIPASS_DATA_IRRELEVANT)
5620 if (data2->status == AUTOPREF_MULTIPASS_DATA_UNINITIALIZED)
5621 autopref_multipass_init (insn2, write);
5622 if (data2->status == AUTOPREF_MULTIPASS_DATA_IRRELEVANT)
5625 if (!rtx_equal_p (data1->base, data2->base))
5628 return data1->offset - data2->offset;
5634 /* True if header of debug dump was printed. */
5635 static bool autopref_multipass_dfa_lookahead_guard_started_dump_p;
5637 /* Helper for autopref_multipass_dfa_lookahead_guard.
5638 Return "1" if INSN1 should be delayed in favor of INSN2. */
5640 autopref_multipass_dfa_lookahead_guard_1 (const rtx_insn *insn1,
5641 const rtx_insn *insn2, int write)
5643 autopref_multipass_data_t data1
5644 = &INSN_AUTOPREF_MULTIPASS_DATA (insn1)[write];
5645 autopref_multipass_data_t data2
5646 = &INSN_AUTOPREF_MULTIPASS_DATA (insn2)[write];
5648 if (data2->status == AUTOPREF_MULTIPASS_DATA_UNINITIALIZED)
5649 autopref_multipass_init (insn2, write);
5650 if (data2->status == AUTOPREF_MULTIPASS_DATA_IRRELEVANT)
5653 if (rtx_equal_p (data1->base, data2->base)
5654 && data1->offset > data2->offset)
5656 if (sched_verbose >= 2)
5658 if (!autopref_multipass_dfa_lookahead_guard_started_dump_p)
5660 fprintf (sched_dump,
5661 ";;\t\tnot trying in max_issue due to autoprefetch "
5663 autopref_multipass_dfa_lookahead_guard_started_dump_p = true;
5666 fprintf (sched_dump, " %d(%d)", INSN_UID (insn1), INSN_UID (insn2));
5677 We could have also hooked autoprefetcher model into
5678 first_cycle_multipass_backtrack / first_cycle_multipass_issue hooks
5679 to enable intelligent selection of "[r1+0]=r2; [r1+4]=r3" on the same cycle
5680 (e.g., once "[r1+0]=r2" is issued in max_issue(), "[r1+4]=r3" gets
5681 unblocked). We don't bother about this yet because target of interest
5682 (ARM Cortex-A15) can issue only 1 memory operation per cycle. */
5684 /* Implementation of first_cycle_multipass_dfa_lookahead_guard hook.
5685 Return "1" if INSN1 should not be considered in max_issue due to
5686 auto-prefetcher considerations. */
5688 autopref_multipass_dfa_lookahead_guard (rtx_insn *insn1, int ready_index)
5692 if (PARAM_VALUE (PARAM_SCHED_AUTOPREF_QUEUE_DEPTH) <= 0)
5695 if (sched_verbose >= 2 && ready_index == 0)
5696 autopref_multipass_dfa_lookahead_guard_started_dump_p = false;
5698 for (int write = 0; write < 2; ++write)
5700 autopref_multipass_data_t data1
5701 = &INSN_AUTOPREF_MULTIPASS_DATA (insn1)[write];
5703 if (data1->status == AUTOPREF_MULTIPASS_DATA_UNINITIALIZED)
5704 autopref_multipass_init (insn1, write);
5705 if (data1->status == AUTOPREF_MULTIPASS_DATA_IRRELEVANT)
5708 if (ready_index == 0
5709 && data1->status == AUTOPREF_MULTIPASS_DATA_DONT_DELAY)
5710 /* We allow only a single delay on priviledged instructions.
5711 Doing otherwise would cause infinite loop. */
5713 if (sched_verbose >= 2)
5715 if (!autopref_multipass_dfa_lookahead_guard_started_dump_p)
5717 fprintf (sched_dump,
5718 ";;\t\tnot trying in max_issue due to autoprefetch "
5720 autopref_multipass_dfa_lookahead_guard_started_dump_p = true;
5723 fprintf (sched_dump, " *%d*", INSN_UID (insn1));
5728 for (int i2 = 0; i2 < ready.n_ready; ++i2)
5730 rtx_insn *insn2 = get_ready_element (i2);
5733 r = autopref_multipass_dfa_lookahead_guard_1 (insn1, insn2, write);
5736 if (ready_index == 0)
5739 data1->status = AUTOPREF_MULTIPASS_DATA_DONT_DELAY;
5745 if (PARAM_VALUE (PARAM_SCHED_AUTOPREF_QUEUE_DEPTH) == 1)
5748 /* Everything from the current queue slot should have been moved to
5750 gcc_assert (insn_queue[NEXT_Q_AFTER (q_ptr, 0)] == NULL_RTX);
5752 int n_stalls = PARAM_VALUE (PARAM_SCHED_AUTOPREF_QUEUE_DEPTH) - 1;
5753 if (n_stalls > max_insn_queue_index)
5754 n_stalls = max_insn_queue_index;
5756 for (int stalls = 1; stalls <= n_stalls; ++stalls)
5758 for (rtx_insn_list *link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)];
5760 link = link->next ())
5762 rtx_insn *insn2 = link->insn ();
5763 r = autopref_multipass_dfa_lookahead_guard_1 (insn1, insn2,
5767 /* Queue INSN1 until INSN2 can issue. */
5769 if (ready_index == 0)
5770 data1->status = AUTOPREF_MULTIPASS_DATA_DONT_DELAY;
5778 if (sched_verbose >= 2
5779 && autopref_multipass_dfa_lookahead_guard_started_dump_p
5780 && (ready_index == ready.n_ready - 1 || r < 0))
5781 /* This does not /always/ trigger. We don't output EOL if the last
5782 insn is not recognized (INSN_CODE < 0) and lookahead_guard is not
5783 called. We can live with this. */
5784 fprintf (sched_dump, "\n");
5789 /* Define type for target data used in multipass scheduling. */
5790 #ifndef TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T
5791 # define TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T int
5793 typedef TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T first_cycle_multipass_data_t;
5795 /* The following structure describe an entry of the stack of choices. */
5798 /* Ordinal number of the issued insn in the ready queue. */
5800 /* The number of the rest insns whose issues we should try. */
5802 /* The number of issued essential insns. */
5804 /* State after issuing the insn. */
5806 /* Target-specific data. */
5807 first_cycle_multipass_data_t target_data;
5810 /* The following array is used to implement a stack of choices used in
5811 function max_issue. */
5812 static struct choice_entry *choice_stack;
5814 /* This holds the value of the target dfa_lookahead hook. */
5817 /* The following variable value is maximal number of tries of issuing
5818 insns for the first cycle multipass insn scheduling. We define
5819 this value as constant*(DFA_LOOKAHEAD**ISSUE_RATE). We would not
5820 need this constraint if all real insns (with non-negative codes)
5821 had reservations because in this case the algorithm complexity is
5822 O(DFA_LOOKAHEAD**ISSUE_RATE). Unfortunately, the dfa descriptions
5823 might be incomplete and such insn might occur. For such
5824 descriptions, the complexity of algorithm (without the constraint)
5825 could achieve DFA_LOOKAHEAD ** N , where N is the queue length. */
5826 static int max_lookahead_tries;
5828 /* The following function returns maximal (or close to maximal) number
5829 of insns which can be issued on the same cycle and one of which
5830 insns is insns with the best rank (the first insn in READY). To
5831 make this function tries different samples of ready insns. READY
5832 is current queue `ready'. Global array READY_TRY reflects what
5833 insns are already issued in this try. The function stops immediately,
5834 if it reached the such a solution, that all instruction can be issued.
5835 INDEX will contain index of the best insn in READY. The following
5836 function is used only for first cycle multipass scheduling.
5840 This function expects recognized insns only. All USEs,
5841 CLOBBERs, etc must be filtered elsewhere. */
5843 max_issue (struct ready_list *ready, int privileged_n, state_t state,
5844 bool first_cycle_insn_p, int *index)
5846 int n, i, all, n_ready, best, delay, tries_num;
5848 struct choice_entry *top;
5854 n_ready = ready->n_ready;
5855 gcc_assert (dfa_lookahead >= 1 && privileged_n >= 0
5856 && privileged_n <= n_ready);
5858 /* Init MAX_LOOKAHEAD_TRIES. */
5859 if (max_lookahead_tries == 0)
5861 max_lookahead_tries = 100;
5862 for (i = 0; i < issue_rate; i++)
5863 max_lookahead_tries *= dfa_lookahead;
5866 /* Init max_points. */
5867 more_issue = issue_rate - cycle_issued_insns;
5868 gcc_assert (more_issue >= 0);
5870 /* The number of the issued insns in the best solution. */
5875 /* Set initial state of the search. */
5876 memcpy (top->state, state, dfa_state_size);
5877 top->rest = dfa_lookahead;
5879 if (targetm.sched.first_cycle_multipass_begin)
5880 targetm.sched.first_cycle_multipass_begin (&top->target_data,
5882 first_cycle_insn_p);
5884 /* Count the number of the insns to search among. */
5885 for (all = i = 0; i < n_ready; i++)
5889 if (sched_verbose >= 2)
5891 fprintf (sched_dump, ";;\t\tmax_issue among %d insns:", all);
5892 debug_ready_list_1 (ready, ready_try);
5895 /* I is the index of the insn to try next. */
5900 if (/* If we've reached a dead end or searched enough of what we have
5903 /* or have nothing else to try... */
5905 /* or should not issue more. */
5906 || top->n >= more_issue)
5908 /* ??? (... || i == n_ready). */
5909 gcc_assert (i <= n_ready);
5911 /* We should not issue more than issue_rate instructions. */
5912 gcc_assert (top->n <= more_issue);
5914 if (top == choice_stack)
5917 if (best < top - choice_stack)
5922 /* Try to find issued privileged insn. */
5923 while (n && !ready_try[--n])
5927 if (/* If all insns are equally good... */
5929 /* Or a privileged insn will be issued. */
5931 /* Then we have a solution. */
5933 best = top - choice_stack;
5934 /* This is the index of the insn issued first in this
5936 *index = choice_stack [1].index;
5937 if (top->n == more_issue || best == all)
5942 /* Set ready-list index to point to the last insn
5943 ('i++' below will advance it to the next insn). */
5949 if (targetm.sched.first_cycle_multipass_backtrack)
5950 targetm.sched.first_cycle_multipass_backtrack (&top->target_data,
5951 ready_try, n_ready);
5954 memcpy (state, top->state, dfa_state_size);
5956 else if (!ready_try [i])
5959 if (tries_num > max_lookahead_tries)
5961 insn = ready_element (ready, i);
5962 delay = state_transition (state, insn);
5965 if (state_dead_lock_p (state)
5966 || insn_finishes_cycle_p (insn))
5967 /* We won't issue any more instructions in the next
5974 if (memcmp (top->state, state, dfa_state_size) != 0)
5977 /* Advance to the next choice_entry. */
5979 /* Initialize it. */
5980 top->rest = dfa_lookahead;
5983 memcpy (top->state, state, dfa_state_size);
5986 if (targetm.sched.first_cycle_multipass_issue)
5987 targetm.sched.first_cycle_multipass_issue (&top->target_data,
5997 /* Increase ready-list index. */
6001 if (targetm.sched.first_cycle_multipass_end)
6002 targetm.sched.first_cycle_multipass_end (best != 0
6003 ? &choice_stack[1].target_data
6006 /* Restore the original state of the DFA. */
6007 memcpy (state, choice_stack->state, dfa_state_size);
6012 /* The following function chooses insn from READY and modifies
6013 READY. The following function is used only for first
6014 cycle multipass scheduling.
6016 -1 if cycle should be advanced,
6017 0 if INSN_PTR is set to point to the desirable insn,
6018 1 if choose_ready () should be restarted without advancing the cycle. */
6020 choose_ready (struct ready_list *ready, bool first_cycle_insn_p,
6021 rtx_insn **insn_ptr)
6023 if (dbg_cnt (sched_insn) == false)
6025 if (nonscheduled_insns_begin == NULL_RTX)
6026 nonscheduled_insns_begin = current_sched_info->prev_head;
6028 rtx_insn *insn = first_nonscheduled_insn ();
6030 if (QUEUE_INDEX (insn) == QUEUE_READY)
6031 /* INSN is in the ready_list. */
6033 ready_remove_insn (insn);
6038 /* INSN is in the queue. Advance cycle to move it to the ready list. */
6039 gcc_assert (QUEUE_INDEX (insn) >= 0);
6043 if (dfa_lookahead <= 0 || SCHED_GROUP_P (ready_element (ready, 0))
6044 || DEBUG_INSN_P (ready_element (ready, 0)))
6046 if (targetm.sched.dispatch (NULL, IS_DISPATCH_ON))
6047 *insn_ptr = ready_remove_first_dispatch (ready);
6049 *insn_ptr = ready_remove_first (ready);
6055 /* Try to choose the best insn. */
6059 insn = ready_element (ready, 0);
6060 if (INSN_CODE (insn) < 0)
6062 *insn_ptr = ready_remove_first (ready);
6066 /* Filter the search space. */
6067 for (i = 0; i < ready->n_ready; i++)
6071 insn = ready_element (ready, i);
6073 /* If this insn is recognizable we should have already
6074 recognized it earlier.
6075 ??? Not very clear where this is supposed to be done.
6077 gcc_checking_assert (INSN_CODE (insn) >= 0
6078 || recog_memoized (insn) < 0);
6079 if (INSN_CODE (insn) < 0)
6081 /* Non-recognized insns at position 0 are handled above. */
6087 if (targetm.sched.first_cycle_multipass_dfa_lookahead_guard)
6090 = (targetm.sched.first_cycle_multipass_dfa_lookahead_guard
6093 if (ready_try[i] < 0)
6094 /* Queue instruction for several cycles.
6095 We need to restart choose_ready as we have changed
6098 change_queue_index (insn, -ready_try[i]);
6102 /* Make sure that we didn't end up with 0'th insn filtered out.
6103 Don't be tempted to make life easier for backends and just
6104 requeue 0'th insn if (ready_try[0] == 0) and restart
6105 choose_ready. Backends should be very considerate about
6106 requeueing instructions -- especially the highest priority
6107 one at position 0. */
6108 gcc_assert (ready_try[i] == 0 || i > 0);
6113 gcc_assert (ready_try[i] == 0);
6114 /* INSN made it through the scrutiny of filters! */
6117 if (max_issue (ready, 1, curr_state, first_cycle_insn_p, &index) == 0)
6119 *insn_ptr = ready_remove_first (ready);
6120 if (sched_verbose >= 4)
6121 fprintf (sched_dump, ";;\t\tChosen insn (but can't issue) : %s \n",
6122 (*current_sched_info->print_insn) (*insn_ptr, 0));
6127 if (sched_verbose >= 4)
6128 fprintf (sched_dump, ";;\t\tChosen insn : %s\n",
6129 (*current_sched_info->print_insn)
6130 (ready_element (ready, index), 0));
6132 *insn_ptr = ready_remove (ready, index);
6138 /* This function is called when we have successfully scheduled a
6139 block. It uses the schedule stored in the scheduled_insns vector
6140 to rearrange the RTL. PREV_HEAD is used as the anchor to which we
6141 append the scheduled insns; TAIL is the insn after the scheduled
6142 block. TARGET_BB is the argument passed to schedule_block. */
6145 commit_schedule (rtx_insn *prev_head, rtx_insn *tail, basic_block *target_bb)
6150 last_scheduled_insn = prev_head;
6152 scheduled_insns.iterate (i, &insn);
6155 if (control_flow_insn_p (last_scheduled_insn)
6156 || current_sched_info->advance_target_bb (*target_bb, insn))
6158 *target_bb = current_sched_info->advance_target_bb (*target_bb, 0);
6164 x = next_real_insn (last_scheduled_insn);
6166 dump_new_block_header (1, *target_bb, x, tail);
6169 last_scheduled_insn = bb_note (*target_bb);
6172 if (current_sched_info->begin_move_insn)
6173 (*current_sched_info->begin_move_insn) (insn, last_scheduled_insn);
6174 move_insn (insn, last_scheduled_insn,
6175 current_sched_info->next_tail);
6176 if (!DEBUG_INSN_P (insn))
6177 reemit_notes (insn);
6178 last_scheduled_insn = insn;
6181 scheduled_insns.truncate (0);
6184 /* Examine all insns on the ready list and queue those which can't be
6185 issued in this cycle. TEMP_STATE is temporary scheduler state we
6186 can use as scratch space. If FIRST_CYCLE_INSN_P is true, no insns
6187 have been issued for the current cycle, which means it is valid to
6188 issue an asm statement.
6190 If SHADOWS_ONLY_P is true, we eliminate all real insns and only
6191 leave those for which SHADOW_P is true. If MODULO_EPILOGUE is true,
6192 we only leave insns which have an INSN_EXACT_TICK. */
6195 prune_ready_list (state_t temp_state, bool first_cycle_insn_p,
6196 bool shadows_only_p, bool modulo_epilogue_p)
6199 bool sched_group_found = false;
6200 int min_cost_group = 1;
6205 for (i = 0; i < ready.n_ready; i++)
6207 rtx_insn *insn = ready_element (&ready, i);
6208 if (SCHED_GROUP_P (insn))
6210 sched_group_found = true;
6215 /* Make two passes if there's a SCHED_GROUP_P insn; make sure to handle
6216 such an insn first and note its cost, then schedule all other insns
6217 for one cycle later. */
6218 for (pass = sched_group_found ? 0 : 1; pass < 2; )
6220 int n = ready.n_ready;
6221 for (i = 0; i < n; i++)
6223 rtx_insn *insn = ready_element (&ready, i);
6225 const char *reason = "resource conflict";
6227 if (DEBUG_INSN_P (insn))
6230 if (sched_group_found && !SCHED_GROUP_P (insn))
6234 cost = min_cost_group;
6235 reason = "not in sched group";
6237 else if (modulo_epilogue_p
6238 && INSN_EXACT_TICK (insn) == INVALID_TICK)
6240 cost = max_insn_queue_index;
6241 reason = "not an epilogue insn";
6243 else if (shadows_only_p && !SHADOW_P (insn))
6246 reason = "not a shadow";
6248 else if (recog_memoized (insn) < 0)
6250 if (!first_cycle_insn_p
6251 && (GET_CODE (PATTERN (insn)) == ASM_INPUT
6252 || asm_noperands (PATTERN (insn)) >= 0))
6256 else if (sched_pressure != SCHED_PRESSURE_NONE)
6258 if (sched_pressure == SCHED_PRESSURE_MODEL
6259 && INSN_TICK (insn) <= clock_var)
6261 memcpy (temp_state, curr_state, dfa_state_size);
6262 if (state_transition (temp_state, insn) >= 0)
6263 INSN_TICK (insn) = clock_var + 1;
6273 struct delay_pair *delay_entry;
6275 = delay_htab->find_with_hash (insn,
6276 htab_hash_pointer (insn));
6277 while (delay_entry && delay_cost == 0)
6279 delay_cost = estimate_shadow_tick (delay_entry);
6280 if (delay_cost > max_insn_queue_index)
6281 delay_cost = max_insn_queue_index;
6282 delay_entry = delay_entry->next_same_i1;
6286 memcpy (temp_state, curr_state, dfa_state_size);
6287 cost = state_transition (temp_state, insn);
6292 if (cost < delay_cost)
6295 reason = "shadow tick";
6300 if (SCHED_GROUP_P (insn) && cost > min_cost_group)
6301 min_cost_group = cost;
6302 ready_remove (&ready, i);
6303 /* Normally we'd want to queue INSN for COST cycles. However,
6304 if SCHED_GROUP_P is set, then we must ensure that nothing
6305 else comes between INSN and its predecessor. If there is
6306 some other insn ready to fire on the next cycle, then that
6307 invariant would be broken.
6309 So when SCHED_GROUP_P is set, just queue this insn for a
6311 queue_insn (insn, SCHED_GROUP_P (insn) ? 1 : cost, reason);
6321 /* Called when we detect that the schedule is impossible. We examine the
6322 backtrack queue to find the earliest insn that caused this condition. */
6324 static struct haifa_saved_data *
6325 verify_shadows (void)
6327 struct haifa_saved_data *save, *earliest_fail = NULL;
6328 for (save = backtrack_queue; save; save = save->next)
6331 struct delay_pair *pair = save->delay_pair;
6332 rtx_insn *i1 = pair->i1;
6334 for (; pair; pair = pair->next_same_i1)
6336 rtx_insn *i2 = pair->i2;
6338 if (QUEUE_INDEX (i2) == QUEUE_SCHEDULED)
6341 t = INSN_TICK (i1) + pair_delay (pair);
6344 if (sched_verbose >= 2)
6345 fprintf (sched_dump,
6346 ";;\t\tfailed delay requirements for %d/%d (%d->%d)"
6348 INSN_UID (pair->i1), INSN_UID (pair->i2),
6349 INSN_TICK (pair->i1), INSN_EXACT_TICK (pair->i2));
6350 earliest_fail = save;
6353 if (QUEUE_INDEX (i2) >= 0)
6355 int queued_for = INSN_TICK (i2);
6359 if (sched_verbose >= 2)
6360 fprintf (sched_dump,
6361 ";;\t\tfailed delay requirements for %d/%d"
6362 " (%d->%d), queued too late\n",
6363 INSN_UID (pair->i1), INSN_UID (pair->i2),
6364 INSN_TICK (pair->i1), INSN_EXACT_TICK (pair->i2));
6365 earliest_fail = save;
6372 return earliest_fail;
6375 /* Print instructions together with useful scheduling information between
6376 HEAD and TAIL (inclusive). */
6378 dump_insn_stream (rtx_insn *head, rtx_insn *tail)
6380 fprintf (sched_dump, ";;\t| insn | prio |\n");
6382 rtx_insn *next_tail = NEXT_INSN (tail);
6383 for (rtx_insn *insn = head; insn != next_tail; insn = NEXT_INSN (insn))
6385 int priority = NOTE_P (insn) ? 0 : INSN_PRIORITY (insn);
6386 const char *pattern = (NOTE_P (insn)
6388 : str_pattern_slim (PATTERN (insn)));
6390 fprintf (sched_dump, ";;\t| %4d | %4d | %-30s ",
6391 INSN_UID (insn), priority, pattern);
6393 if (sched_verbose >= 4)
6395 if (NOTE_P (insn) || recog_memoized (insn) < 0)
6396 fprintf (sched_dump, "nothing");
6398 print_reservation (sched_dump, insn);
6400 fprintf (sched_dump, "\n");
6404 /* Use forward list scheduling to rearrange insns of block pointed to by
6405 TARGET_BB, possibly bringing insns from subsequent blocks in the same
6409 schedule_block (basic_block *target_bb, state_t init_state)
6412 bool success = modulo_ii == 0;
6413 struct sched_block_state ls;
6414 state_t temp_state = NULL; /* It is used for multipass scheduling. */
6415 int sort_p, advance, start_clock_var;
6417 /* Head/tail info for this block. */
6418 rtx_insn *prev_head = current_sched_info->prev_head;
6419 rtx_insn *next_tail = current_sched_info->next_tail;
6420 rtx_insn *head = NEXT_INSN (prev_head);
6421 rtx_insn *tail = PREV_INSN (next_tail);
6423 if ((current_sched_info->flags & DONT_BREAK_DEPENDENCIES) == 0
6424 && sched_pressure != SCHED_PRESSURE_MODEL && !sched_fusion)
6425 find_modifiable_mems (head, tail);
6427 /* We used to have code to avoid getting parameters moved from hard
6428 argument registers into pseudos.
6430 However, it was removed when it proved to be of marginal benefit
6431 and caused problems because schedule_block and compute_forward_dependences
6432 had different notions of what the "head" insn was. */
6434 gcc_assert (head != tail || INSN_P (head));
6436 haifa_recovery_bb_recently_added_p = false;
6438 backtrack_queue = NULL;
6443 dump_new_block_header (0, *target_bb, head, tail);
6445 if (sched_verbose >= 2)
6447 dump_insn_stream (head, tail);
6448 memset (&rank_for_schedule_stats, 0,
6449 sizeof (rank_for_schedule_stats));
6453 if (init_state == NULL)
6454 state_reset (curr_state);
6456 memcpy (curr_state, init_state, dfa_state_size);
6458 /* Clear the ready list. */
6459 ready.first = ready.veclen - 1;
6463 /* It is used for first cycle multipass scheduling. */
6464 temp_state = alloca (dfa_state_size);
6466 if (targetm.sched.init)
6467 targetm.sched.init (sched_dump, sched_verbose, ready.veclen);
6469 /* We start inserting insns after PREV_HEAD. */
6470 last_scheduled_insn = prev_head;
6471 last_nondebug_scheduled_insn = NULL_RTX;
6472 nonscheduled_insns_begin = NULL;
6474 gcc_assert ((NOTE_P (last_scheduled_insn)
6475 || DEBUG_INSN_P (last_scheduled_insn))
6476 && BLOCK_FOR_INSN (last_scheduled_insn) == *target_bb);
6478 /* Initialize INSN_QUEUE. Q_SIZE is the total number of insns in the
6483 insn_queue = XALLOCAVEC (rtx_insn_list *, max_insn_queue_index + 1);
6484 memset (insn_queue, 0, (max_insn_queue_index + 1) * sizeof (rtx));
6486 /* Start just before the beginning of time. */
6489 /* We need queue and ready lists and clock_var be initialized
6490 in try_ready () (which is called through init_ready_list ()). */
6491 (*current_sched_info->init_ready_list) ();
6494 sched_pressure_start_bb (*target_bb);
6496 /* The algorithm is O(n^2) in the number of ready insns at any given
6497 time in the worst case. Before reload we are more likely to have
6498 big lists so truncate them to a reasonable size. */
6499 if (!reload_completed
6500 && ready.n_ready - ready.n_debug > MAX_SCHED_READY_INSNS)
6502 ready_sort_debug (&ready);
6503 ready_sort_real (&ready);
6505 /* Find first free-standing insn past MAX_SCHED_READY_INSNS.
6506 If there are debug insns, we know they're first. */
6507 for (i = MAX_SCHED_READY_INSNS + ready.n_debug; i < ready.n_ready; i++)
6508 if (!SCHED_GROUP_P (ready_element (&ready, i)))
6511 if (sched_verbose >= 2)
6513 fprintf (sched_dump,
6514 ";;\t\tReady list on entry: %d insns: ", ready.n_ready);
6515 debug_ready_list (&ready);
6516 fprintf (sched_dump,
6517 ";;\t\t before reload => truncated to %d insns\n", i);
6520 /* Delay all insns past it for 1 cycle. If debug counter is
6521 activated make an exception for the insn right after
6522 nonscheduled_insns_begin. */
6524 rtx_insn *skip_insn;
6526 if (dbg_cnt (sched_insn) == false)
6527 skip_insn = first_nonscheduled_insn ();
6531 while (i < ready.n_ready)
6535 insn = ready_remove (&ready, i);
6537 if (insn != skip_insn)
6538 queue_insn (insn, 1, "list truncated");
6541 ready_add (&ready, skip_insn, true);
6545 /* Now we can restore basic block notes and maintain precise cfg. */
6546 restore_bb_notes (*target_bb);
6548 last_clock_var = -1;
6552 gcc_assert (scheduled_insns.length () == 0);
6554 must_backtrack = false;
6555 modulo_insns_scheduled = 0;
6557 ls.modulo_epilogue = false;
6558 ls.first_cycle_insn_p = true;
6560 /* Loop until all the insns in BB are scheduled. */
6561 while ((*current_sched_info->schedule_more_p) ())
6563 perform_replacements_new_cycle ();
6566 start_clock_var = clock_var;
6570 advance_one_cycle ();
6572 /* Add to the ready list all pending insns that can be issued now.
6573 If there are no ready insns, increment clock until one
6574 is ready and add all pending insns at that point to the ready
6576 queue_to_ready (&ready);
6578 gcc_assert (ready.n_ready);
6580 if (sched_verbose >= 2)
6582 fprintf (sched_dump, ";;\t\tReady list after queue_to_ready:");
6583 debug_ready_list (&ready);
6585 advance -= clock_var - start_clock_var;
6587 while (advance > 0);
6589 if (ls.modulo_epilogue)
6591 int stage = clock_var / modulo_ii;
6592 if (stage > modulo_last_stage * 2 + 2)
6594 if (sched_verbose >= 2)
6595 fprintf (sched_dump,
6596 ";;\t\tmodulo scheduled succeeded at II %d\n",
6602 else if (modulo_ii > 0)
6604 int stage = clock_var / modulo_ii;
6605 if (stage > modulo_max_stages)
6607 if (sched_verbose >= 2)
6608 fprintf (sched_dump,
6609 ";;\t\tfailing schedule due to excessive stages\n");
6612 if (modulo_n_insns == modulo_insns_scheduled
6613 && stage > modulo_last_stage)
6615 if (sched_verbose >= 2)
6616 fprintf (sched_dump,
6617 ";;\t\tfound kernel after %d stages, II %d\n",
6619 ls.modulo_epilogue = true;
6623 prune_ready_list (temp_state, true, false, ls.modulo_epilogue);
6624 if (ready.n_ready == 0)
6629 ls.shadows_only_p = false;
6630 cycle_issued_insns = 0;
6631 ls.can_issue_more = issue_rate;
6638 if (sort_p && ready.n_ready > 0)
6640 /* Sort the ready list based on priority. This must be
6641 done every iteration through the loop, as schedule_insn
6642 may have readied additional insns that will not be
6643 sorted correctly. */
6644 ready_sort (&ready);
6646 if (sched_verbose >= 2)
6648 fprintf (sched_dump,
6649 ";;\t\tReady list after ready_sort: ");
6650 debug_ready_list (&ready);
6654 /* We don't want md sched reorder to even see debug isns, so put
6655 them out right away. */
6656 if (ready.n_ready && DEBUG_INSN_P (ready_element (&ready, 0))
6657 && (*current_sched_info->schedule_more_p) ())
6659 while (ready.n_ready && DEBUG_INSN_P (ready_element (&ready, 0)))
6661 rtx_insn *insn = ready_remove_first (&ready);
6662 gcc_assert (DEBUG_INSN_P (insn));
6663 (*current_sched_info->begin_schedule_ready) (insn);
6664 scheduled_insns.safe_push (insn);
6665 last_scheduled_insn = insn;
6666 advance = schedule_insn (insn);
6667 gcc_assert (advance == 0);
6668 if (ready.n_ready > 0)
6669 ready_sort (&ready);
6673 if (ls.first_cycle_insn_p && !ready.n_ready)
6676 resume_after_backtrack:
6677 /* Allow the target to reorder the list, typically for
6678 better instruction bundling. */
6680 && (ready.n_ready == 0
6681 || !SCHED_GROUP_P (ready_element (&ready, 0))))
6683 if (ls.first_cycle_insn_p && targetm.sched.reorder)
6685 = targetm.sched.reorder (sched_dump, sched_verbose,
6686 ready_lastpos (&ready),
6687 &ready.n_ready, clock_var);
6688 else if (!ls.first_cycle_insn_p && targetm.sched.reorder2)
6690 = targetm.sched.reorder2 (sched_dump, sched_verbose,
6692 ? ready_lastpos (&ready) : NULL,
6693 &ready.n_ready, clock_var);
6696 restart_choose_ready:
6697 if (sched_verbose >= 2)
6699 fprintf (sched_dump, ";;\tReady list (t = %3d): ",
6701 debug_ready_list (&ready);
6702 if (sched_pressure == SCHED_PRESSURE_WEIGHTED)
6703 print_curr_reg_pressure ();
6706 if (ready.n_ready == 0
6707 && ls.can_issue_more
6708 && reload_completed)
6710 /* Allow scheduling insns directly from the queue in case
6711 there's nothing better to do (ready list is empty) but
6712 there are still vacant dispatch slots in the current cycle. */
6713 if (sched_verbose >= 6)
6714 fprintf (sched_dump,";;\t\tSecond chance\n");
6715 memcpy (temp_state, curr_state, dfa_state_size);
6716 if (early_queue_to_ready (temp_state, &ready))
6717 ready_sort (&ready);
6720 if (ready.n_ready == 0
6721 || !ls.can_issue_more
6722 || state_dead_lock_p (curr_state)
6723 || !(*current_sched_info->schedule_more_p) ())
6726 /* Select and remove the insn from the ready list. */
6732 res = choose_ready (&ready, ls.first_cycle_insn_p, &insn);
6738 goto restart_choose_ready;
6740 gcc_assert (insn != NULL_RTX);
6743 insn = ready_remove_first (&ready);
6745 if (sched_pressure != SCHED_PRESSURE_NONE
6746 && INSN_TICK (insn) > clock_var)
6748 ready_add (&ready, insn, true);
6753 if (targetm.sched.dfa_new_cycle
6754 && targetm.sched.dfa_new_cycle (sched_dump, sched_verbose,
6755 insn, last_clock_var,
6756 clock_var, &sort_p))
6757 /* SORT_P is used by the target to override sorting
6758 of the ready list. This is needed when the target
6759 has modified its internal structures expecting that
6760 the insn will be issued next. As we need the insn
6761 to have the highest priority (so it will be returned by
6762 the ready_remove_first call above), we invoke
6763 ready_add (&ready, insn, true).
6764 But, still, there is one issue: INSN can be later
6765 discarded by scheduler's front end through
6766 current_sched_info->can_schedule_ready_p, hence, won't
6769 ready_add (&ready, insn, true);
6775 if (current_sched_info->can_schedule_ready_p
6776 && ! (*current_sched_info->can_schedule_ready_p) (insn))
6777 /* We normally get here only if we don't want to move
6778 insn from the split block. */
6780 TODO_SPEC (insn) = DEP_POSTPONED;
6781 goto restart_choose_ready;
6786 /* If this insn is the first part of a delay-slot pair, record a
6788 struct delay_pair *delay_entry;
6790 = delay_htab->find_with_hash (insn, htab_hash_pointer (insn));
6793 save_backtrack_point (delay_entry, ls);
6794 if (sched_verbose >= 2)
6795 fprintf (sched_dump, ";;\t\tsaving backtrack point\n");
6799 /* DECISION is made. */
6801 if (modulo_ii > 0 && INSN_UID (insn) < modulo_iter0_max_uid)
6803 modulo_insns_scheduled++;
6804 modulo_last_stage = clock_var / modulo_ii;
6806 if (TODO_SPEC (insn) & SPECULATIVE)
6807 generate_recovery_code (insn);
6809 if (targetm.sched.dispatch (NULL, IS_DISPATCH_ON))
6810 targetm.sched.dispatch_do (insn, ADD_TO_DISPATCH_WINDOW);
6812 /* Update counters, etc in the scheduler's front end. */
6813 (*current_sched_info->begin_schedule_ready) (insn);
6814 scheduled_insns.safe_push (insn);
6815 gcc_assert (NONDEBUG_INSN_P (insn));
6816 last_nondebug_scheduled_insn = last_scheduled_insn = insn;
6818 if (recog_memoized (insn) >= 0)
6820 memcpy (temp_state, curr_state, dfa_state_size);
6821 cost = state_transition (curr_state, insn);
6822 if (sched_pressure != SCHED_PRESSURE_WEIGHTED && !sched_fusion)
6823 gcc_assert (cost < 0);
6824 if (memcmp (temp_state, curr_state, dfa_state_size) != 0)
6825 cycle_issued_insns++;
6829 asm_p = (GET_CODE (PATTERN (insn)) == ASM_INPUT
6830 || asm_noperands (PATTERN (insn)) >= 0);
6832 if (targetm.sched.variable_issue)
6834 targetm.sched.variable_issue (sched_dump, sched_verbose,
6835 insn, ls.can_issue_more);
6836 /* A naked CLOBBER or USE generates no instruction, so do
6837 not count them against the issue rate. */
6838 else if (GET_CODE (PATTERN (insn)) != USE
6839 && GET_CODE (PATTERN (insn)) != CLOBBER)
6840 ls.can_issue_more--;
6841 advance = schedule_insn (insn);
6843 if (SHADOW_P (insn))
6844 ls.shadows_only_p = true;
6846 /* After issuing an asm insn we should start a new cycle. */
6847 if (advance == 0 && asm_p)
6856 ls.first_cycle_insn_p = false;
6857 if (ready.n_ready > 0)
6858 prune_ready_list (temp_state, false, ls.shadows_only_p,
6859 ls.modulo_epilogue);
6863 if (!must_backtrack)
6864 for (i = 0; i < ready.n_ready; i++)
6866 rtx_insn *insn = ready_element (&ready, i);
6867 if (INSN_EXACT_TICK (insn) == clock_var)
6869 must_backtrack = true;
6874 if (must_backtrack && modulo_ii > 0)
6876 if (modulo_backtracks_left == 0)
6878 modulo_backtracks_left--;
6880 while (must_backtrack)
6882 struct haifa_saved_data *failed;
6883 rtx_insn *failed_insn;
6885 must_backtrack = false;
6886 failed = verify_shadows ();
6887 gcc_assert (failed);
6889 failed_insn = failed->delay_pair->i1;
6890 /* Clear these queues. */
6891 perform_replacements_new_cycle ();
6892 toggle_cancelled_flags (false);
6893 unschedule_insns_until (failed_insn);
6894 while (failed != backtrack_queue)
6895 free_topmost_backtrack_point (true);
6896 restore_last_backtrack_point (&ls);
6897 if (sched_verbose >= 2)
6898 fprintf (sched_dump, ";;\t\trewind to cycle %d\n", clock_var);
6899 /* Delay by at least a cycle. This could cause additional
6901 queue_insn (failed_insn, 1, "backtracked");
6905 if (ready.n_ready > 0)
6906 goto resume_after_backtrack;
6909 if (clock_var == 0 && ls.first_cycle_insn_p)
6915 ls.first_cycle_insn_p = true;
6917 if (ls.modulo_epilogue)
6920 if (!ls.first_cycle_insn_p || advance)
6921 advance_one_cycle ();
6922 perform_replacements_new_cycle ();
6925 /* Once again, debug insn suckiness: they can be on the ready list
6926 even if they have unresolved dependencies. To make our view
6927 of the world consistent, remove such "ready" insns. */
6928 restart_debug_insn_loop:
6929 for (i = ready.n_ready - 1; i >= 0; i--)
6933 x = ready_element (&ready, i);
6934 if (DEPS_LIST_FIRST (INSN_HARD_BACK_DEPS (x)) != NULL
6935 || DEPS_LIST_FIRST (INSN_SPEC_BACK_DEPS (x)) != NULL)
6937 ready_remove (&ready, i);
6938 goto restart_debug_insn_loop;
6941 for (i = ready.n_ready - 1; i >= 0; i--)
6945 x = ready_element (&ready, i);
6946 resolve_dependencies (x);
6948 for (i = 0; i <= max_insn_queue_index; i++)
6950 rtx_insn_list *link;
6951 while ((link = insn_queue[i]) != NULL)
6953 rtx_insn *x = link->insn ();
6954 insn_queue[i] = link->next ();
6955 QUEUE_INDEX (x) = QUEUE_NOWHERE;
6956 free_INSN_LIST_node (link);
6957 resolve_dependencies (x);
6963 undo_all_replacements ();
6968 fprintf (sched_dump, ";;\tReady list (final): ");
6969 debug_ready_list (&ready);
6972 if (modulo_ii == 0 && current_sched_info->queue_must_finish_empty)
6973 /* Sanity check -- queue must be empty now. Meaningless if region has
6975 gcc_assert (!q_size && !ready.n_ready && !ready.n_debug);
6976 else if (modulo_ii == 0)
6978 /* We must maintain QUEUE_INDEX between blocks in region. */
6979 for (i = ready.n_ready - 1; i >= 0; i--)
6983 x = ready_element (&ready, i);
6984 QUEUE_INDEX (x) = QUEUE_NOWHERE;
6985 TODO_SPEC (x) = HARD_DEP;
6989 for (i = 0; i <= max_insn_queue_index; i++)
6991 rtx_insn_list *link;
6992 for (link = insn_queue[i]; link; link = link->next ())
6997 QUEUE_INDEX (x) = QUEUE_NOWHERE;
6998 TODO_SPEC (x) = HARD_DEP;
7000 free_INSN_LIST_list (&insn_queue[i]);
7004 if (sched_pressure == SCHED_PRESSURE_MODEL)
7005 model_end_schedule ();
7009 commit_schedule (prev_head, tail, target_bb);
7011 fprintf (sched_dump, ";; total time = %d\n", clock_var);
7014 last_scheduled_insn = tail;
7016 scheduled_insns.truncate (0);
7018 if (!current_sched_info->queue_must_finish_empty
7019 || haifa_recovery_bb_recently_added_p)
7021 /* INSN_TICK (minimum clock tick at which the insn becomes
7022 ready) may be not correct for the insn in the subsequent
7023 blocks of the region. We should use a correct value of
7024 `clock_var' or modify INSN_TICK. It is better to keep
7025 clock_var value equal to 0 at the start of a basic block.
7026 Therefore we modify INSN_TICK here. */
7027 fix_inter_tick (NEXT_INSN (prev_head), last_scheduled_insn);
7030 if (targetm.sched.finish)
7032 targetm.sched.finish (sched_dump, sched_verbose);
7033 /* Target might have added some instructions to the scheduled block
7034 in its md_finish () hook. These new insns don't have any data
7035 initialized and to identify them we extend h_i_d so that they'll
7037 sched_extend_luids ();
7040 /* Update head/tail boundaries. */
7041 head = NEXT_INSN (prev_head);
7042 tail = last_scheduled_insn;
7046 fprintf (sched_dump, ";; new head = %d\n;; new tail = %d\n",
7047 INSN_UID (head), INSN_UID (tail));
7049 if (sched_verbose >= 2)
7051 dump_insn_stream (head, tail);
7052 print_rank_for_schedule_stats (";; TOTAL ", &rank_for_schedule_stats,
7056 fprintf (sched_dump, "\n");
7059 head = restore_other_notes (head, NULL);
7061 current_sched_info->head = head;
7062 current_sched_info->tail = tail;
7064 free_backtrack_queue ();
7069 /* Set_priorities: compute priority of each insn in the block. */
7072 set_priorities (rtx_insn *head, rtx_insn *tail)
7076 int sched_max_insns_priority =
7077 current_sched_info->sched_max_insns_priority;
7078 rtx_insn *prev_head;
7080 if (head == tail && ! INSN_P (head))
7085 prev_head = PREV_INSN (head);
7086 for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
7092 (void) priority (insn);
7094 gcc_assert (INSN_PRIORITY_KNOWN (insn));
7096 sched_max_insns_priority = MAX (sched_max_insns_priority,
7097 INSN_PRIORITY (insn));
7100 current_sched_info->sched_max_insns_priority = sched_max_insns_priority;
7105 /* Set dump and sched_verbose for the desired debugging output. If no
7106 dump-file was specified, but -fsched-verbose=N (any N), print to stderr.
7107 For -fsched-verbose=N, N>=10, print everything to stderr. */
7109 setup_sched_dump (void)
7111 sched_verbose = sched_verbose_param;
7112 if (sched_verbose_param == 0 && dump_file)
7114 sched_dump = ((sched_verbose_param >= 10 || !dump_file)
7115 ? stderr : dump_file);
7118 /* Allocate data for register pressure sensitive scheduling. */
7120 alloc_global_sched_pressure_data (void)
7122 if (sched_pressure != SCHED_PRESSURE_NONE)
7124 int i, max_regno = max_reg_num ();
7126 if (sched_dump != NULL)
7127 /* We need info about pseudos for rtl dumps about pseudo
7128 classes and costs. */
7129 regstat_init_n_sets_and_refs ();
7130 ira_set_pseudo_classes (true, sched_verbose ? sched_dump : NULL);
7131 sched_regno_pressure_class
7132 = (enum reg_class *) xmalloc (max_regno * sizeof (enum reg_class));
7133 for (i = 0; i < max_regno; i++)
7134 sched_regno_pressure_class[i]
7135 = (i < FIRST_PSEUDO_REGISTER
7136 ? ira_pressure_class_translate[REGNO_REG_CLASS (i)]
7137 : ira_pressure_class_translate[reg_allocno_class (i)]);
7138 curr_reg_live = BITMAP_ALLOC (NULL);
7139 if (sched_pressure == SCHED_PRESSURE_WEIGHTED)
7141 saved_reg_live = BITMAP_ALLOC (NULL);
7142 region_ref_regs = BITMAP_ALLOC (NULL);
7145 /* Calculate number of CALL_USED_REGS in register classes that
7146 we calculate register pressure for. */
7147 for (int c = 0; c < ira_pressure_classes_num; ++c)
7149 enum reg_class cl = ira_pressure_classes[c];
7151 call_used_regs_num[cl] = 0;
7153 for (int i = 0; i < ira_class_hard_regs_num[cl]; ++i)
7154 if (call_used_regs[ira_class_hard_regs[cl][i]])
7155 ++call_used_regs_num[cl];
7160 /* Free data for register pressure sensitive scheduling. Also called
7161 from schedule_region when stopping sched-pressure early. */
7163 free_global_sched_pressure_data (void)
7165 if (sched_pressure != SCHED_PRESSURE_NONE)
7167 if (regstat_n_sets_and_refs != NULL)
7168 regstat_free_n_sets_and_refs ();
7169 if (sched_pressure == SCHED_PRESSURE_WEIGHTED)
7171 BITMAP_FREE (region_ref_regs);
7172 BITMAP_FREE (saved_reg_live);
7174 BITMAP_FREE (curr_reg_live);
7175 free (sched_regno_pressure_class);
7179 /* Initialize some global state for the scheduler. This function works
7180 with the common data shared between all the schedulers. It is called
7181 from the scheduler specific initialization routine. */
7186 /* Disable speculative loads in their presence if cc0 defined. */
7188 flag_schedule_speculative_load = 0;
7191 if (targetm.sched.dispatch (NULL, IS_DISPATCH_ON))
7192 targetm.sched.dispatch_do (NULL, DISPATCH_INIT);
7194 if (live_range_shrinkage_p)
7195 sched_pressure = SCHED_PRESSURE_WEIGHTED;
7196 else if (flag_sched_pressure
7197 && !reload_completed
7198 && common_sched_info->sched_pass_id == SCHED_RGN_PASS)
7199 sched_pressure = ((enum sched_pressure_algorithm)
7200 PARAM_VALUE (PARAM_SCHED_PRESSURE_ALGORITHM));
7202 sched_pressure = SCHED_PRESSURE_NONE;
7204 if (sched_pressure != SCHED_PRESSURE_NONE)
7205 ira_setup_eliminable_regset ();
7207 /* Initialize SPEC_INFO. */
7208 if (targetm.sched.set_sched_flags)
7210 spec_info = &spec_info_var;
7211 targetm.sched.set_sched_flags (spec_info);
7213 if (spec_info->mask != 0)
7215 spec_info->data_weakness_cutoff =
7216 (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF) * MAX_DEP_WEAK) / 100;
7217 spec_info->control_weakness_cutoff =
7218 (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF)
7219 * REG_BR_PROB_BASE) / 100;
7222 /* So we won't read anything accidentally. */
7227 /* So we won't read anything accidentally. */
7230 /* Initialize issue_rate. */
7231 if (targetm.sched.issue_rate)
7232 issue_rate = targetm.sched.issue_rate ();
7236 if (targetm.sched.first_cycle_multipass_dfa_lookahead
7237 /* Don't use max_issue with reg_pressure scheduling. Multipass
7238 scheduling and reg_pressure scheduling undo each other's decisions. */
7239 && sched_pressure == SCHED_PRESSURE_NONE)
7240 dfa_lookahead = targetm.sched.first_cycle_multipass_dfa_lookahead ();
7244 /* Set to "0" so that we recalculate. */
7245 max_lookahead_tries = 0;
7247 if (targetm.sched.init_dfa_pre_cycle_insn)
7248 targetm.sched.init_dfa_pre_cycle_insn ();
7250 if (targetm.sched.init_dfa_post_cycle_insn)
7251 targetm.sched.init_dfa_post_cycle_insn ();
7254 dfa_state_size = state_size ();
7256 init_alias_analysis ();
7259 df_set_flags (DF_LR_RUN_DCE);
7260 df_note_add_problem ();
7262 /* More problems needed for interloop dep calculation in SMS. */
7263 if (common_sched_info->sched_pass_id == SCHED_SMS_PASS)
7265 df_rd_add_problem ();
7266 df_chain_add_problem (DF_DU_CHAIN + DF_UD_CHAIN);
7271 /* Do not run DCE after reload, as this can kill nops inserted
7273 if (reload_completed)
7274 df_clear_flags (DF_LR_RUN_DCE);
7276 regstat_compute_calls_crossed ();
7278 if (targetm.sched.init_global)
7279 targetm.sched.init_global (sched_dump, sched_verbose, get_max_uid () + 1);
7281 alloc_global_sched_pressure_data ();
7283 curr_state = xmalloc (dfa_state_size);
7286 static void haifa_init_only_bb (basic_block, basic_block);
7288 /* Initialize data structures specific to the Haifa scheduler. */
7290 haifa_sched_init (void)
7292 setup_sched_dump ();
7295 scheduled_insns.create (0);
7297 if (spec_info != NULL)
7299 sched_deps_info->use_deps_list = 1;
7300 sched_deps_info->generate_spec_deps = 1;
7303 /* Initialize luids, dependency caches, target and h_i_d for the
7307 bbs.create (n_basic_blocks_for_fn (cfun));
7312 FOR_EACH_BB_FN (bb, cfun)
7313 bbs.quick_push (bb);
7314 sched_init_luids (bbs);
7315 sched_deps_init (true);
7316 sched_extend_target ();
7317 haifa_init_h_i_d (bbs);
7322 sched_init_only_bb = haifa_init_only_bb;
7323 sched_split_block = sched_split_block_1;
7324 sched_create_empty_bb = sched_create_empty_bb_1;
7325 haifa_recovery_bb_ever_added_p = false;
7327 nr_begin_data = nr_begin_control = nr_be_in_data = nr_be_in_control = 0;
7328 before_recovery = 0;
7334 /* Finish work with the data specific to the Haifa scheduler. */
7336 haifa_sched_finish (void)
7338 sched_create_empty_bb = NULL;
7339 sched_split_block = NULL;
7340 sched_init_only_bb = NULL;
7342 if (spec_info && spec_info->dump)
7344 char c = reload_completed ? 'a' : 'b';
7346 fprintf (spec_info->dump,
7347 ";; %s:\n", current_function_name ());
7349 fprintf (spec_info->dump,
7350 ";; Procedure %cr-begin-data-spec motions == %d\n",
7352 fprintf (spec_info->dump,
7353 ";; Procedure %cr-be-in-data-spec motions == %d\n",
7355 fprintf (spec_info->dump,
7356 ";; Procedure %cr-begin-control-spec motions == %d\n",
7357 c, nr_begin_control);
7358 fprintf (spec_info->dump,
7359 ";; Procedure %cr-be-in-control-spec motions == %d\n",
7360 c, nr_be_in_control);
7363 scheduled_insns.release ();
7365 /* Finalize h_i_d, dependency caches, and luids for the whole
7366 function. Target will be finalized in md_global_finish (). */
7367 sched_deps_finish ();
7368 sched_finish_luids ();
7369 current_sched_info = NULL;
7373 /* Free global data used during insn scheduling. This function works with
7374 the common data shared between the schedulers. */
7379 haifa_finish_h_i_d ();
7380 free_global_sched_pressure_data ();
7383 if (targetm.sched.finish_global)
7384 targetm.sched.finish_global (sched_dump, sched_verbose);
7386 end_alias_analysis ();
7388 regstat_free_calls_crossed ();
7393 /* Free all delay_pair structures that were recorded. */
7395 free_delay_pairs (void)
7399 delay_htab->empty ();
7400 delay_htab_i2->empty ();
7404 /* Fix INSN_TICKs of the instructions in the current block as well as
7405 INSN_TICKs of their dependents.
7406 HEAD and TAIL are the begin and the end of the current scheduled block. */
7408 fix_inter_tick (rtx_insn *head, rtx_insn *tail)
7410 /* Set of instructions with corrected INSN_TICK. */
7411 bitmap_head processed;
7412 /* ??? It is doubtful if we should assume that cycle advance happens on
7413 basic block boundaries. Basically insns that are unconditionally ready
7414 on the start of the block are more preferable then those which have
7415 a one cycle dependency over insn from the previous block. */
7416 int next_clock = clock_var + 1;
7418 bitmap_initialize (&processed, 0);
7420 /* Iterates over scheduled instructions and fix their INSN_TICKs and
7421 INSN_TICKs of dependent instructions, so that INSN_TICKs are consistent
7422 across different blocks. */
7423 for (tail = NEXT_INSN (tail); head != tail; head = NEXT_INSN (head))
7428 sd_iterator_def sd_it;
7431 tick = INSN_TICK (head);
7432 gcc_assert (tick >= MIN_TICK);
7434 /* Fix INSN_TICK of instruction from just scheduled block. */
7435 if (bitmap_set_bit (&processed, INSN_LUID (head)))
7439 if (tick < MIN_TICK)
7442 INSN_TICK (head) = tick;
7445 if (DEBUG_INSN_P (head))
7448 FOR_EACH_DEP (head, SD_LIST_RES_FORW, sd_it, dep)
7452 next = DEP_CON (dep);
7453 tick = INSN_TICK (next);
7455 if (tick != INVALID_TICK
7456 /* If NEXT has its INSN_TICK calculated, fix it.
7457 If not - it will be properly calculated from
7458 scratch later in fix_tick_ready. */
7459 && bitmap_set_bit (&processed, INSN_LUID (next)))
7463 if (tick < MIN_TICK)
7466 if (tick > INTER_TICK (next))
7467 INTER_TICK (next) = tick;
7469 tick = INTER_TICK (next);
7471 INSN_TICK (next) = tick;
7476 bitmap_clear (&processed);
7479 /* Check if NEXT is ready to be added to the ready or queue list.
7480 If "yes", add it to the proper list.
7482 -1 - is not ready yet,
7483 0 - added to the ready list,
7484 0 < N - queued for N cycles. */
7486 try_ready (rtx_insn *next)
7488 ds_t old_ts, new_ts;
7490 old_ts = TODO_SPEC (next);
7492 gcc_assert (!(old_ts & ~(SPECULATIVE | HARD_DEP | DEP_CONTROL | DEP_POSTPONED))
7493 && (old_ts == HARD_DEP
7494 || old_ts == DEP_POSTPONED
7495 || (old_ts & SPECULATIVE)
7496 || old_ts == DEP_CONTROL));
7498 new_ts = recompute_todo_spec (next, false);
7500 if (new_ts & (HARD_DEP | DEP_POSTPONED))
7501 gcc_assert (new_ts == old_ts
7502 && QUEUE_INDEX (next) == QUEUE_NOWHERE);
7503 else if (current_sched_info->new_ready)
7504 new_ts = current_sched_info->new_ready (next, new_ts);
7506 /* * if !(old_ts & SPECULATIVE) (e.g. HARD_DEP or 0), then insn might
7507 have its original pattern or changed (speculative) one. This is due
7508 to changing ebb in region scheduling.
7509 * But if (old_ts & SPECULATIVE), then we are pretty sure that insn
7510 has speculative pattern.
7512 We can't assert (!(new_ts & HARD_DEP) || new_ts == old_ts) here because
7513 control-speculative NEXT could have been discarded by sched-rgn.c
7514 (the same case as when discarded by can_schedule_ready_p ()). */
7516 if ((new_ts & SPECULATIVE)
7517 /* If (old_ts == new_ts), then (old_ts & SPECULATIVE) and we don't
7518 need to change anything. */
7519 && new_ts != old_ts)
7524 gcc_assert ((new_ts & SPECULATIVE) && !(new_ts & ~SPECULATIVE));
7526 res = haifa_speculate_insn (next, new_ts, &new_pat);
7531 /* It would be nice to change DEP_STATUS of all dependences,
7532 which have ((DEP_STATUS & SPECULATIVE) == new_ts) to HARD_DEP,
7533 so we won't reanalyze anything. */
7538 /* We follow the rule, that every speculative insn
7539 has non-null ORIG_PAT. */
7540 if (!ORIG_PAT (next))
7541 ORIG_PAT (next) = PATTERN (next);
7545 if (!ORIG_PAT (next))
7546 /* If we gonna to overwrite the original pattern of insn,
7548 ORIG_PAT (next) = PATTERN (next);
7550 res = haifa_change_pattern (next, new_pat);
7559 /* We need to restore pattern only if (new_ts == 0), because otherwise it is
7560 either correct (new_ts & SPECULATIVE),
7561 or we simply don't care (new_ts & HARD_DEP). */
7563 gcc_assert (!ORIG_PAT (next)
7564 || !IS_SPECULATION_BRANCHY_CHECK_P (next));
7566 TODO_SPEC (next) = new_ts;
7568 if (new_ts & (HARD_DEP | DEP_POSTPONED))
7570 /* We can't assert (QUEUE_INDEX (next) == QUEUE_NOWHERE) here because
7571 control-speculative NEXT could have been discarded by sched-rgn.c
7572 (the same case as when discarded by can_schedule_ready_p ()). */
7573 /*gcc_assert (QUEUE_INDEX (next) == QUEUE_NOWHERE);*/
7575 change_queue_index (next, QUEUE_NOWHERE);
7579 else if (!(new_ts & BEGIN_SPEC)
7580 && ORIG_PAT (next) && PREDICATED_PAT (next) == NULL_RTX
7581 && !IS_SPECULATION_CHECK_P (next))
7582 /* We should change pattern of every previously speculative
7583 instruction - and we determine if NEXT was speculative by using
7584 ORIG_PAT field. Except one case - speculation checks have ORIG_PAT
7585 pat too, so skip them. */
7587 bool success = haifa_change_pattern (next, ORIG_PAT (next));
7588 gcc_assert (success);
7589 ORIG_PAT (next) = 0;
7592 if (sched_verbose >= 2)
7594 fprintf (sched_dump, ";;\t\tdependencies resolved: insn %s",
7595 (*current_sched_info->print_insn) (next, 0));
7597 if (spec_info && spec_info->dump)
7599 if (new_ts & BEGIN_DATA)
7600 fprintf (spec_info->dump, "; data-spec;");
7601 if (new_ts & BEGIN_CONTROL)
7602 fprintf (spec_info->dump, "; control-spec;");
7603 if (new_ts & BE_IN_CONTROL)
7604 fprintf (spec_info->dump, "; in-control-spec;");
7606 if (TODO_SPEC (next) & DEP_CONTROL)
7607 fprintf (sched_dump, " predicated");
7608 fprintf (sched_dump, "\n");
7611 adjust_priority (next);
7613 return fix_tick_ready (next);
7616 /* Calculate INSN_TICK of NEXT and add it to either ready or queue list. */
7618 fix_tick_ready (rtx_insn *next)
7622 if (!DEBUG_INSN_P (next) && !sd_lists_empty_p (next, SD_LIST_RES_BACK))
7625 sd_iterator_def sd_it;
7628 tick = INSN_TICK (next);
7629 /* if tick is not equal to INVALID_TICK, then update
7630 INSN_TICK of NEXT with the most recent resolved dependence
7631 cost. Otherwise, recalculate from scratch. */
7632 full_p = (tick == INVALID_TICK);
7634 FOR_EACH_DEP (next, SD_LIST_RES_BACK, sd_it, dep)
7636 rtx_insn *pro = DEP_PRO (dep);
7639 gcc_assert (INSN_TICK (pro) >= MIN_TICK);
7641 tick1 = INSN_TICK (pro) + dep_cost (dep);
7652 INSN_TICK (next) = tick;
7654 delay = tick - clock_var;
7655 if (delay <= 0 || sched_pressure != SCHED_PRESSURE_NONE || sched_fusion)
7656 delay = QUEUE_READY;
7658 change_queue_index (next, delay);
7663 /* Move NEXT to the proper queue list with (DELAY >= 1),
7664 or add it to the ready list (DELAY == QUEUE_READY),
7665 or remove it from ready and queue lists at all (DELAY == QUEUE_NOWHERE). */
7667 change_queue_index (rtx_insn *next, int delay)
7669 int i = QUEUE_INDEX (next);
7671 gcc_assert (QUEUE_NOWHERE <= delay && delay <= max_insn_queue_index
7673 gcc_assert (i != QUEUE_SCHEDULED);
7675 if ((delay > 0 && NEXT_Q_AFTER (q_ptr, delay) == i)
7676 || (delay < 0 && delay == i))
7677 /* We have nothing to do. */
7680 /* Remove NEXT from wherever it is now. */
7681 if (i == QUEUE_READY)
7682 ready_remove_insn (next);
7684 queue_remove (next);
7686 /* Add it to the proper place. */
7687 if (delay == QUEUE_READY)
7688 ready_add (readyp, next, false);
7689 else if (delay >= 1)
7690 queue_insn (next, delay, "change queue index");
7692 if (sched_verbose >= 2)
7694 fprintf (sched_dump, ";;\t\ttick updated: insn %s",
7695 (*current_sched_info->print_insn) (next, 0));
7697 if (delay == QUEUE_READY)
7698 fprintf (sched_dump, " into ready\n");
7699 else if (delay >= 1)
7700 fprintf (sched_dump, " into queue with cost=%d\n", delay);
7702 fprintf (sched_dump, " removed from ready or queue lists\n");
7706 static int sched_ready_n_insns = -1;
7708 /* Initialize per region data structures. */
7710 sched_extend_ready_list (int new_sched_ready_n_insns)
7714 if (sched_ready_n_insns == -1)
7715 /* At the first call we need to initialize one more choice_stack
7719 sched_ready_n_insns = 0;
7720 scheduled_insns.reserve (new_sched_ready_n_insns);
7723 i = sched_ready_n_insns + 1;
7725 ready.veclen = new_sched_ready_n_insns + issue_rate;
7726 ready.vec = XRESIZEVEC (rtx_insn *, ready.vec, ready.veclen);
7728 gcc_assert (new_sched_ready_n_insns >= sched_ready_n_insns);
7730 ready_try = (signed char *) xrecalloc (ready_try, new_sched_ready_n_insns,
7731 sched_ready_n_insns,
7732 sizeof (*ready_try));
7734 /* We allocate +1 element to save initial state in the choice_stack[0]
7736 choice_stack = XRESIZEVEC (struct choice_entry, choice_stack,
7737 new_sched_ready_n_insns + 1);
7739 for (; i <= new_sched_ready_n_insns; i++)
7741 choice_stack[i].state = xmalloc (dfa_state_size);
7743 if (targetm.sched.first_cycle_multipass_init)
7744 targetm.sched.first_cycle_multipass_init (&(choice_stack[i]
7748 sched_ready_n_insns = new_sched_ready_n_insns;
7751 /* Free per region data structures. */
7753 sched_finish_ready_list (void)
7764 for (i = 0; i <= sched_ready_n_insns; i++)
7766 if (targetm.sched.first_cycle_multipass_fini)
7767 targetm.sched.first_cycle_multipass_fini (&(choice_stack[i]
7770 free (choice_stack [i].state);
7772 free (choice_stack);
7773 choice_stack = NULL;
7775 sched_ready_n_insns = -1;
7779 haifa_luid_for_non_insn (rtx x)
7781 gcc_assert (NOTE_P (x) || LABEL_P (x));
7786 /* Generates recovery code for INSN. */
7788 generate_recovery_code (rtx_insn *insn)
7790 if (TODO_SPEC (insn) & BEGIN_SPEC)
7791 begin_speculative_block (insn);
7793 /* Here we have insn with no dependencies to
7794 instructions other then CHECK_SPEC ones. */
7796 if (TODO_SPEC (insn) & BE_IN_SPEC)
7797 add_to_speculative_block (insn);
7801 Tries to add speculative dependencies of type FS between instructions
7802 in deps_list L and TWIN. */
7804 process_insn_forw_deps_be_in_spec (rtx insn, rtx_insn *twin, ds_t fs)
7806 sd_iterator_def sd_it;
7809 FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
7814 consumer = DEP_CON (dep);
7816 ds = DEP_STATUS (dep);
7818 if (/* If we want to create speculative dep. */
7820 /* And we can do that because this is a true dep. */
7821 && (ds & DEP_TYPES) == DEP_TRUE)
7823 gcc_assert (!(ds & BE_IN_SPEC));
7825 if (/* If this dep can be overcome with 'begin speculation'. */
7827 /* Then we have a choice: keep the dep 'begin speculative'
7828 or transform it into 'be in speculative'. */
7830 if (/* In try_ready we assert that if insn once became ready
7831 it can be removed from the ready (or queue) list only
7832 due to backend decision. Hence we can't let the
7833 probability of the speculative dep to decrease. */
7834 ds_weak (ds) <= ds_weak (fs))
7838 new_ds = (ds & ~BEGIN_SPEC) | fs;
7840 if (/* consumer can 'be in speculative'. */
7841 sched_insn_is_legitimate_for_speculation_p (consumer,
7843 /* Transform it to be in speculative. */
7848 /* Mark the dep as 'be in speculative'. */
7853 dep_def _new_dep, *new_dep = &_new_dep;
7855 init_dep_1 (new_dep, twin, consumer, DEP_TYPE (dep), ds);
7856 sd_add_dep (new_dep, false);
7861 /* Generates recovery code for BEGIN speculative INSN. */
7863 begin_speculative_block (rtx_insn *insn)
7865 if (TODO_SPEC (insn) & BEGIN_DATA)
7867 if (TODO_SPEC (insn) & BEGIN_CONTROL)
7870 create_check_block_twin (insn, false);
7872 TODO_SPEC (insn) &= ~BEGIN_SPEC;
7875 static void haifa_init_insn (rtx_insn *);
7877 /* Generates recovery code for BE_IN speculative INSN. */
7879 add_to_speculative_block (rtx_insn *insn)
7882 sd_iterator_def sd_it;
7884 rtx_insn_list *twins = NULL;
7885 rtx_vec_t priorities_roots;
7887 ts = TODO_SPEC (insn);
7888 gcc_assert (!(ts & ~BE_IN_SPEC));
7890 if (ts & BE_IN_DATA)
7892 if (ts & BE_IN_CONTROL)
7895 TODO_SPEC (insn) &= ~BE_IN_SPEC;
7896 gcc_assert (!TODO_SPEC (insn));
7898 DONE_SPEC (insn) |= ts;
7900 /* First we convert all simple checks to branchy. */
7901 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
7902 sd_iterator_cond (&sd_it, &dep);)
7904 rtx_insn *check = DEP_PRO (dep);
7906 if (IS_SPECULATION_SIMPLE_CHECK_P (check))
7908 create_check_block_twin (check, true);
7910 /* Restart search. */
7911 sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
7914 /* Continue search. */
7915 sd_iterator_next (&sd_it);
7918 priorities_roots.create (0);
7919 clear_priorities (insn, &priorities_roots);
7923 rtx_insn *check, *twin;
7926 /* Get the first backward dependency of INSN. */
7927 sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
7928 if (!sd_iterator_cond (&sd_it, &dep))
7929 /* INSN has no backward dependencies left. */
7932 gcc_assert ((DEP_STATUS (dep) & BEGIN_SPEC) == 0
7933 && (DEP_STATUS (dep) & BE_IN_SPEC) != 0
7934 && (DEP_STATUS (dep) & DEP_TYPES) == DEP_TRUE);
7936 check = DEP_PRO (dep);
7938 gcc_assert (!IS_SPECULATION_CHECK_P (check) && !ORIG_PAT (check)
7939 && QUEUE_INDEX (check) == QUEUE_NOWHERE);
7941 rec = BLOCK_FOR_INSN (check);
7943 twin = emit_insn_before (copy_insn (PATTERN (insn)), BB_END (rec));
7944 haifa_init_insn (twin);
7946 sd_copy_back_deps (twin, insn, true);
7948 if (sched_verbose && spec_info->dump)
7949 /* INSN_BB (insn) isn't determined for twin insns yet.
7950 So we can't use current_sched_info->print_insn. */
7951 fprintf (spec_info->dump, ";;\t\tGenerated twin insn : %d/rec%d\n",
7952 INSN_UID (twin), rec->index);
7954 twins = alloc_INSN_LIST (twin, twins);
7956 /* Add dependences between TWIN and all appropriate
7957 instructions from REC. */
7958 FOR_EACH_DEP (insn, SD_LIST_SPEC_BACK, sd_it, dep)
7960 rtx_insn *pro = DEP_PRO (dep);
7962 gcc_assert (DEP_TYPE (dep) == REG_DEP_TRUE);
7964 /* INSN might have dependencies from the instructions from
7965 several recovery blocks. At this iteration we process those
7966 producers that reside in REC. */
7967 if (BLOCK_FOR_INSN (pro) == rec)
7969 dep_def _new_dep, *new_dep = &_new_dep;
7971 init_dep (new_dep, pro, twin, REG_DEP_TRUE);
7972 sd_add_dep (new_dep, false);
7976 process_insn_forw_deps_be_in_spec (insn, twin, ts);
7978 /* Remove all dependencies between INSN and insns in REC. */
7979 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
7980 sd_iterator_cond (&sd_it, &dep);)
7982 rtx_insn *pro = DEP_PRO (dep);
7984 if (BLOCK_FOR_INSN (pro) == rec)
7985 sd_delete_dep (sd_it);
7987 sd_iterator_next (&sd_it);
7991 /* We couldn't have added the dependencies between INSN and TWINS earlier
7992 because that would make TWINS appear in the INSN_BACK_DEPS (INSN). */
7996 rtx_insn_list *next_node;
7998 twin = twins->insn ();
8001 dep_def _new_dep, *new_dep = &_new_dep;
8003 init_dep (new_dep, insn, twin, REG_DEP_OUTPUT);
8004 sd_add_dep (new_dep, false);
8007 next_node = twins->next ();
8008 free_INSN_LIST_node (twins);
8012 calc_priorities (priorities_roots);
8013 priorities_roots.release ();
8016 /* Extends and fills with zeros (only the new part) array pointed to by P. */
8018 xrecalloc (void *p, size_t new_nmemb, size_t old_nmemb, size_t size)
8020 gcc_assert (new_nmemb >= old_nmemb);
8021 p = XRESIZEVAR (void, p, new_nmemb * size);
8022 memset (((char *) p) + old_nmemb * size, 0, (new_nmemb - old_nmemb) * size);
8027 Find fallthru edge from PRED. */
8029 find_fallthru_edge_from (basic_block pred)
8034 succ = pred->next_bb;
8035 gcc_assert (succ->prev_bb == pred);
8037 if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds))
8039 e = find_fallthru_edge (pred->succs);
8043 gcc_assert (e->dest == succ);
8049 e = find_fallthru_edge (succ->preds);
8053 gcc_assert (e->src == pred);
8061 /* Extend per basic block data structures. */
8063 sched_extend_bb (void)
8065 /* The following is done to keep current_sched_info->next_tail non null. */
8066 rtx_insn *end = BB_END (EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb);
8067 rtx_insn *insn = DEBUG_INSN_P (end) ? prev_nondebug_insn (end) : end;
8068 if (NEXT_INSN (end) == 0
8071 /* Don't emit a NOTE if it would end up before a BARRIER. */
8072 && !BARRIER_P (NEXT_INSN (end))))
8074 rtx_note *note = emit_note_after (NOTE_INSN_DELETED, end);
8075 /* Make note appear outside BB. */
8076 set_block_for_insn (note, NULL);
8077 BB_END (EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb) = end;
8081 /* Init per basic block data structures. */
8083 sched_init_bbs (void)
8088 /* Initialize BEFORE_RECOVERY variable. */
8090 init_before_recovery (basic_block *before_recovery_ptr)
8095 last = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
8096 e = find_fallthru_edge_from (last);
8100 /* We create two basic blocks:
8101 1. Single instruction block is inserted right after E->SRC
8103 2. Empty block right before EXIT_BLOCK.
8104 Between these two blocks recovery blocks will be emitted. */
8106 basic_block single, empty;
8110 /* If the fallthrough edge to exit we've found is from the block we've
8111 created before, don't do anything more. */
8112 if (last == after_recovery)
8115 adding_bb_to_current_region_p = false;
8117 single = sched_create_empty_bb (last);
8118 empty = sched_create_empty_bb (single);
8120 /* Add new blocks to the root loop. */
8121 if (current_loops != NULL)
8123 add_bb_to_loop (single, (*current_loops->larray)[0]);
8124 add_bb_to_loop (empty, (*current_loops->larray)[0]);
8127 single->count = last->count;
8128 empty->count = last->count;
8129 single->frequency = last->frequency;
8130 empty->frequency = last->frequency;
8131 BB_COPY_PARTITION (single, last);
8132 BB_COPY_PARTITION (empty, last);
8134 redirect_edge_succ (e, single);
8135 make_single_succ_edge (single, empty, 0);
8136 make_single_succ_edge (empty, EXIT_BLOCK_PTR_FOR_FN (cfun),
8139 label = block_label (empty);
8140 x = emit_jump_insn_after (gen_jump (label), BB_END (single));
8141 JUMP_LABEL (x) = label;
8142 LABEL_NUSES (label)++;
8143 haifa_init_insn (x);
8145 emit_barrier_after (x);
8147 sched_init_only_bb (empty, NULL);
8148 sched_init_only_bb (single, NULL);
8151 adding_bb_to_current_region_p = true;
8152 before_recovery = single;
8153 after_recovery = empty;
8155 if (before_recovery_ptr)
8156 *before_recovery_ptr = before_recovery;
8158 if (sched_verbose >= 2 && spec_info->dump)
8159 fprintf (spec_info->dump,
8160 ";;\t\tFixed fallthru to EXIT : %d->>%d->%d->>EXIT\n",
8161 last->index, single->index, empty->index);
8164 before_recovery = last;
8167 /* Returns new recovery block. */
8169 sched_create_recovery_block (basic_block *before_recovery_ptr)
8175 haifa_recovery_bb_recently_added_p = true;
8176 haifa_recovery_bb_ever_added_p = true;
8178 init_before_recovery (before_recovery_ptr);
8180 barrier = get_last_bb_insn (before_recovery);
8181 gcc_assert (BARRIER_P (barrier));
8183 label = emit_label_after (gen_label_rtx (), barrier);
8185 rec = create_basic_block (label, label, before_recovery);
8187 /* A recovery block always ends with an unconditional jump. */
8188 emit_barrier_after (BB_END (rec));
8190 if (BB_PARTITION (before_recovery) != BB_UNPARTITIONED)
8191 BB_SET_PARTITION (rec, BB_COLD_PARTITION);
8193 if (sched_verbose && spec_info->dump)
8194 fprintf (spec_info->dump, ";;\t\tGenerated recovery block rec%d\n",
8200 /* Create edges: FIRST_BB -> REC; FIRST_BB -> SECOND_BB; REC -> SECOND_BB
8201 and emit necessary jumps. */
8203 sched_create_recovery_edges (basic_block first_bb, basic_block rec,
8204 basic_block second_bb)
8210 /* This is fixing of incoming edge. */
8211 /* ??? Which other flags should be specified? */
8212 if (BB_PARTITION (first_bb) != BB_PARTITION (rec))
8213 /* Partition type is the same, if it is "unpartitioned". */
8214 edge_flags = EDGE_CROSSING;
8218 make_edge (first_bb, rec, edge_flags);
8219 label = block_label (second_bb);
8220 jump = emit_jump_insn_after (gen_jump (label), BB_END (rec));
8221 JUMP_LABEL (jump) = label;
8222 LABEL_NUSES (label)++;
8224 if (BB_PARTITION (second_bb) != BB_PARTITION (rec))
8225 /* Partition type is the same, if it is "unpartitioned". */
8227 /* Rewritten from cfgrtl.c. */
8228 if (flag_reorder_blocks_and_partition
8229 && targetm_common.have_named_sections)
8231 /* We don't need the same note for the check because
8232 any_condjump_p (check) == true. */
8233 CROSSING_JUMP_P (jump) = 1;
8235 edge_flags = EDGE_CROSSING;
8240 make_single_succ_edge (rec, second_bb, edge_flags);
8241 if (dom_info_available_p (CDI_DOMINATORS))
8242 set_immediate_dominator (CDI_DOMINATORS, rec, first_bb);
8245 /* This function creates recovery code for INSN. If MUTATE_P is nonzero,
8246 INSN is a simple check, that should be converted to branchy one. */
8248 create_check_block_twin (rtx_insn *insn, bool mutate_p)
8251 rtx_insn *label, *check, *twin;
8254 sd_iterator_def sd_it;
8256 dep_def _new_dep, *new_dep = &_new_dep;
8259 gcc_assert (ORIG_PAT (insn) != NULL_RTX);
8262 todo_spec = TODO_SPEC (insn);
8265 gcc_assert (IS_SPECULATION_SIMPLE_CHECK_P (insn)
8266 && (TODO_SPEC (insn) & SPECULATIVE) == 0);
8268 todo_spec = CHECK_SPEC (insn);
8271 todo_spec &= SPECULATIVE;
8273 /* Create recovery block. */
8274 if (mutate_p || targetm.sched.needs_block_p (todo_spec))
8276 rec = sched_create_recovery_block (NULL);
8277 label = BB_HEAD (rec);
8281 rec = EXIT_BLOCK_PTR_FOR_FN (cfun);
8286 check_pat = targetm.sched.gen_spec_check (insn, label, todo_spec);
8288 if (rec != EXIT_BLOCK_PTR_FOR_FN (cfun))
8290 /* To have mem_reg alive at the beginning of second_bb,
8291 we emit check BEFORE insn, so insn after splitting
8292 insn will be at the beginning of second_bb, which will
8293 provide us with the correct life information. */
8294 check = emit_jump_insn_before (check_pat, insn);
8295 JUMP_LABEL (check) = label;
8296 LABEL_NUSES (label)++;
8299 check = emit_insn_before (check_pat, insn);
8301 /* Extend data structures. */
8302 haifa_init_insn (check);
8304 /* CHECK is being added to current region. Extend ready list. */
8305 gcc_assert (sched_ready_n_insns != -1);
8306 sched_extend_ready_list (sched_ready_n_insns + 1);
8308 if (current_sched_info->add_remove_insn)
8309 current_sched_info->add_remove_insn (insn, 0);
8311 RECOVERY_BLOCK (check) = rec;
8313 if (sched_verbose && spec_info->dump)
8314 fprintf (spec_info->dump, ";;\t\tGenerated check insn : %s\n",
8315 (*current_sched_info->print_insn) (check, 0));
8317 gcc_assert (ORIG_PAT (insn));
8319 /* Initialize TWIN (twin is a duplicate of original instruction
8320 in the recovery block). */
8321 if (rec != EXIT_BLOCK_PTR_FOR_FN (cfun))
8323 sd_iterator_def sd_it;
8326 FOR_EACH_DEP (insn, SD_LIST_RES_BACK, sd_it, dep)
8327 if ((DEP_STATUS (dep) & DEP_OUTPUT) != 0)
8329 struct _dep _dep2, *dep2 = &_dep2;
8331 init_dep (dep2, DEP_PRO (dep), check, REG_DEP_TRUE);
8333 sd_add_dep (dep2, true);
8336 twin = emit_insn_after (ORIG_PAT (insn), BB_END (rec));
8337 haifa_init_insn (twin);
8339 if (sched_verbose && spec_info->dump)
8340 /* INSN_BB (insn) isn't determined for twin insns yet.
8341 So we can't use current_sched_info->print_insn. */
8342 fprintf (spec_info->dump, ";;\t\tGenerated twin insn : %d/rec%d\n",
8343 INSN_UID (twin), rec->index);
8347 ORIG_PAT (check) = ORIG_PAT (insn);
8348 HAS_INTERNAL_DEP (check) = 1;
8350 /* ??? We probably should change all OUTPUT dependencies to
8354 /* Copy all resolved back dependencies of INSN to TWIN. This will
8355 provide correct value for INSN_TICK (TWIN). */
8356 sd_copy_back_deps (twin, insn, true);
8358 if (rec != EXIT_BLOCK_PTR_FOR_FN (cfun))
8359 /* In case of branchy check, fix CFG. */
8361 basic_block first_bb, second_bb;
8364 first_bb = BLOCK_FOR_INSN (check);
8365 second_bb = sched_split_block (first_bb, check);
8367 sched_create_recovery_edges (first_bb, rec, second_bb);
8369 sched_init_only_bb (second_bb, first_bb);
8370 sched_init_only_bb (rec, EXIT_BLOCK_PTR_FOR_FN (cfun));
8372 jump = BB_END (rec);
8373 haifa_init_insn (jump);
8376 /* Move backward dependences from INSN to CHECK and
8377 move forward dependences from INSN to TWIN. */
8379 /* First, create dependencies between INSN's producers and CHECK & TWIN. */
8380 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
8382 rtx_insn *pro = DEP_PRO (dep);
8385 /* If BEGIN_DATA: [insn ~~TRUE~~> producer]:
8386 check --TRUE--> producer ??? or ANTI ???
8387 twin --TRUE--> producer
8388 twin --ANTI--> check
8390 If BEGIN_CONTROL: [insn ~~ANTI~~> producer]:
8391 check --ANTI--> producer
8392 twin --ANTI--> producer
8393 twin --ANTI--> check
8395 If BE_IN_SPEC: [insn ~~TRUE~~> producer]:
8396 check ~~TRUE~~> producer
8397 twin ~~TRUE~~> producer
8398 twin --ANTI--> check */
8400 ds = DEP_STATUS (dep);
8402 if (ds & BEGIN_SPEC)
8404 gcc_assert (!mutate_p);
8408 init_dep_1 (new_dep, pro, check, DEP_TYPE (dep), ds);
8409 sd_add_dep (new_dep, false);
8411 if (rec != EXIT_BLOCK_PTR_FOR_FN (cfun))
8413 DEP_CON (new_dep) = twin;
8414 sd_add_dep (new_dep, false);
8418 /* Second, remove backward dependencies of INSN. */
8419 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
8420 sd_iterator_cond (&sd_it, &dep);)
8422 if ((DEP_STATUS (dep) & BEGIN_SPEC)
8424 /* We can delete this dep because we overcome it with
8425 BEGIN_SPECULATION. */
8426 sd_delete_dep (sd_it);
8428 sd_iterator_next (&sd_it);
8431 /* Future Speculations. Determine what BE_IN speculations will be like. */
8434 /* Fields (DONE_SPEC (x) & BEGIN_SPEC) and CHECK_SPEC (x) are set only
8437 gcc_assert (!DONE_SPEC (insn));
8441 ds_t ts = TODO_SPEC (insn);
8443 DONE_SPEC (insn) = ts & BEGIN_SPEC;
8444 CHECK_SPEC (check) = ts & BEGIN_SPEC;
8446 /* Luckiness of future speculations solely depends upon initial
8447 BEGIN speculation. */
8448 if (ts & BEGIN_DATA)
8449 fs = set_dep_weak (fs, BE_IN_DATA, get_dep_weak (ts, BEGIN_DATA));
8450 if (ts & BEGIN_CONTROL)
8451 fs = set_dep_weak (fs, BE_IN_CONTROL,
8452 get_dep_weak (ts, BEGIN_CONTROL));
8455 CHECK_SPEC (check) = CHECK_SPEC (insn);
8457 /* Future speculations: call the helper. */
8458 process_insn_forw_deps_be_in_spec (insn, twin, fs);
8460 if (rec != EXIT_BLOCK_PTR_FOR_FN (cfun))
8462 /* Which types of dependencies should we use here is,
8463 generally, machine-dependent question... But, for now,
8468 init_dep (new_dep, insn, check, REG_DEP_TRUE);
8469 sd_add_dep (new_dep, false);
8471 init_dep (new_dep, insn, twin, REG_DEP_OUTPUT);
8472 sd_add_dep (new_dep, false);
8476 if (spec_info->dump)
8477 fprintf (spec_info->dump, ";;\t\tRemoved simple check : %s\n",
8478 (*current_sched_info->print_insn) (insn, 0));
8480 /* Remove all dependencies of the INSN. */
8482 sd_it = sd_iterator_start (insn, (SD_LIST_FORW
8484 | SD_LIST_RES_BACK));
8485 while (sd_iterator_cond (&sd_it, &dep))
8486 sd_delete_dep (sd_it);
8489 /* If former check (INSN) already was moved to the ready (or queue)
8490 list, add new check (CHECK) there too. */
8491 if (QUEUE_INDEX (insn) != QUEUE_NOWHERE)
8494 /* Remove old check from instruction stream and free its
8496 sched_remove_insn (insn);
8499 init_dep (new_dep, check, twin, REG_DEP_ANTI);
8500 sd_add_dep (new_dep, false);
8504 init_dep_1 (new_dep, insn, check, REG_DEP_TRUE, DEP_TRUE | DEP_OUTPUT);
8505 sd_add_dep (new_dep, false);
8509 /* Fix priorities. If MUTATE_P is nonzero, this is not necessary,
8510 because it'll be done later in add_to_speculative_block. */
8512 rtx_vec_t priorities_roots = rtx_vec_t ();
8514 clear_priorities (twin, &priorities_roots);
8515 calc_priorities (priorities_roots);
8516 priorities_roots.release ();
8520 /* Removes dependency between instructions in the recovery block REC
8521 and usual region instructions. It keeps inner dependences so it
8522 won't be necessary to recompute them. */
8524 fix_recovery_deps (basic_block rec)
8526 rtx_insn *note, *insn, *jump;
8527 rtx_insn_list *ready_list = 0;
8528 bitmap_head in_ready;
8529 rtx_insn_list *link;
8531 bitmap_initialize (&in_ready, 0);
8533 /* NOTE - a basic block note. */
8534 note = NEXT_INSN (BB_HEAD (rec));
8535 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
8536 insn = BB_END (rec);
8537 gcc_assert (JUMP_P (insn));
8538 insn = PREV_INSN (insn);
8542 sd_iterator_def sd_it;
8545 for (sd_it = sd_iterator_start (insn, SD_LIST_FORW);
8546 sd_iterator_cond (&sd_it, &dep);)
8548 rtx_insn *consumer = DEP_CON (dep);
8550 if (BLOCK_FOR_INSN (consumer) != rec)
8552 sd_delete_dep (sd_it);
8554 if (bitmap_set_bit (&in_ready, INSN_LUID (consumer)))
8555 ready_list = alloc_INSN_LIST (consumer, ready_list);
8559 gcc_assert ((DEP_STATUS (dep) & DEP_TYPES) == DEP_TRUE);
8561 sd_iterator_next (&sd_it);
8565 insn = PREV_INSN (insn);
8567 while (insn != note);
8569 bitmap_clear (&in_ready);
8571 /* Try to add instructions to the ready or queue list. */
8572 for (link = ready_list; link; link = link->next ())
8573 try_ready (link->insn ());
8574 free_INSN_LIST_list (&ready_list);
8576 /* Fixing jump's dependences. */
8577 insn = BB_HEAD (rec);
8578 jump = BB_END (rec);
8580 gcc_assert (LABEL_P (insn));
8581 insn = NEXT_INSN (insn);
8583 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
8584 add_jump_dependencies (insn, jump);
8587 /* Change pattern of INSN to NEW_PAT. Invalidate cached haifa
8588 instruction data. */
8590 haifa_change_pattern (rtx_insn *insn, rtx new_pat)
8594 t = validate_change (insn, &PATTERN (insn), new_pat, 0);
8598 update_insn_after_change (insn);
8602 /* -1 - can't speculate,
8603 0 - for speculation with REQUEST mode it is OK to use
8604 current instruction pattern,
8605 1 - need to change pattern for *NEW_PAT to be speculative. */
8607 sched_speculate_insn (rtx_insn *insn, ds_t request, rtx *new_pat)
8609 gcc_assert (current_sched_info->flags & DO_SPECULATION
8610 && (request & SPECULATIVE)
8611 && sched_insn_is_legitimate_for_speculation_p (insn, request));
8613 if ((request & spec_info->mask) != request)
8616 if (request & BE_IN_SPEC
8617 && !(request & BEGIN_SPEC))
8620 return targetm.sched.speculate_insn (insn, request, new_pat);
8624 haifa_speculate_insn (rtx_insn *insn, ds_t request, rtx *new_pat)
8626 gcc_assert (sched_deps_info->generate_spec_deps
8627 && !IS_SPECULATION_CHECK_P (insn));
8629 if (HAS_INTERNAL_DEP (insn)
8630 || SCHED_GROUP_P (insn))
8633 return sched_speculate_insn (insn, request, new_pat);
8636 /* Print some information about block BB, which starts with HEAD and
8637 ends with TAIL, before scheduling it.
8638 I is zero, if scheduler is about to start with the fresh ebb. */
8640 dump_new_block_header (int i, basic_block bb, rtx_insn *head, rtx_insn *tail)
8643 fprintf (sched_dump,
8644 ";; ======================================================\n");
8646 fprintf (sched_dump,
8647 ";; =====================ADVANCING TO=====================\n");
8648 fprintf (sched_dump,
8649 ";; -- basic block %d from %d to %d -- %s reload\n",
8650 bb->index, INSN_UID (head), INSN_UID (tail),
8651 (reload_completed ? "after" : "before"));
8652 fprintf (sched_dump,
8653 ";; ======================================================\n");
8654 fprintf (sched_dump, "\n");
8657 /* Unlink basic block notes and labels and saves them, so they
8658 can be easily restored. We unlink basic block notes in EBB to
8659 provide back-compatibility with the previous code, as target backends
8660 assume, that there'll be only instructions between
8661 current_sched_info->{head and tail}. We restore these notes as soon
8663 FIRST (LAST) is the first (last) basic block in the ebb.
8664 NB: In usual case (FIRST == LAST) nothing is really done. */
8666 unlink_bb_notes (basic_block first, basic_block last)
8668 /* We DON'T unlink basic block notes of the first block in the ebb. */
8672 bb_header = XNEWVEC (rtx_insn *, last_basic_block_for_fn (cfun));
8674 /* Make a sentinel. */
8675 if (last->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
8676 bb_header[last->next_bb->index] = 0;
8678 first = first->next_bb;
8681 rtx_insn *prev, *label, *note, *next;
8683 label = BB_HEAD (last);
8684 if (LABEL_P (label))
8685 note = NEXT_INSN (label);
8688 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
8690 prev = PREV_INSN (label);
8691 next = NEXT_INSN (note);
8692 gcc_assert (prev && next);
8694 SET_NEXT_INSN (prev) = next;
8695 SET_PREV_INSN (next) = prev;
8697 bb_header[last->index] = label;
8702 last = last->prev_bb;
8707 /* Restore basic block notes.
8708 FIRST is the first basic block in the ebb. */
8710 restore_bb_notes (basic_block first)
8715 /* We DON'T unlink basic block notes of the first block in the ebb. */
8716 first = first->next_bb;
8717 /* Remember: FIRST is actually a second basic block in the ebb. */
8719 while (first != EXIT_BLOCK_PTR_FOR_FN (cfun)
8720 && bb_header[first->index])
8722 rtx_insn *prev, *label, *note, *next;
8724 label = bb_header[first->index];
8725 prev = PREV_INSN (label);
8726 next = NEXT_INSN (prev);
8728 if (LABEL_P (label))
8729 note = NEXT_INSN (label);
8732 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
8734 bb_header[first->index] = 0;
8736 SET_NEXT_INSN (prev) = label;
8737 SET_NEXT_INSN (note) = next;
8738 SET_PREV_INSN (next) = note;
8740 first = first->next_bb;
8748 Fix CFG after both in- and inter-block movement of
8749 control_flow_insn_p JUMP. */
8751 fix_jump_move (rtx_insn *jump)
8753 basic_block bb, jump_bb, jump_bb_next;
8755 bb = BLOCK_FOR_INSN (PREV_INSN (jump));
8756 jump_bb = BLOCK_FOR_INSN (jump);
8757 jump_bb_next = jump_bb->next_bb;
8759 gcc_assert (common_sched_info->sched_pass_id == SCHED_EBB_PASS
8760 || IS_SPECULATION_BRANCHY_CHECK_P (jump));
8762 if (!NOTE_INSN_BASIC_BLOCK_P (BB_END (jump_bb_next)))
8763 /* if jump_bb_next is not empty. */
8764 BB_END (jump_bb) = BB_END (jump_bb_next);
8766 if (BB_END (bb) != PREV_INSN (jump))
8767 /* Then there are instruction after jump that should be placed
8769 BB_END (jump_bb_next) = BB_END (bb);
8771 /* Otherwise jump_bb_next is empty. */
8772 BB_END (jump_bb_next) = NEXT_INSN (BB_HEAD (jump_bb_next));
8774 /* To make assertion in move_insn happy. */
8775 BB_END (bb) = PREV_INSN (jump);
8777 update_bb_for_insn (jump_bb_next);
8780 /* Fix CFG after interblock movement of control_flow_insn_p JUMP. */
8782 move_block_after_check (rtx_insn *jump)
8784 basic_block bb, jump_bb, jump_bb_next;
8785 vec<edge, va_gc> *t;
8787 bb = BLOCK_FOR_INSN (PREV_INSN (jump));
8788 jump_bb = BLOCK_FOR_INSN (jump);
8789 jump_bb_next = jump_bb->next_bb;
8791 update_bb_for_insn (jump_bb);
8793 gcc_assert (IS_SPECULATION_CHECK_P (jump)
8794 || IS_SPECULATION_CHECK_P (BB_END (jump_bb_next)));
8796 unlink_block (jump_bb_next);
8797 link_block (jump_bb_next, bb);
8801 move_succs (&(jump_bb->succs), bb);
8802 move_succs (&(jump_bb_next->succs), jump_bb);
8803 move_succs (&t, jump_bb_next);
8805 df_mark_solutions_dirty ();
8807 common_sched_info->fix_recovery_cfg
8808 (bb->index, jump_bb->index, jump_bb_next->index);
8811 /* Helper function for move_block_after_check.
8812 This functions attaches edge vector pointed to by SUCCSP to
8815 move_succs (vec<edge, va_gc> **succsp, basic_block to)
8820 gcc_assert (to->succs == 0);
8822 to->succs = *succsp;
8824 FOR_EACH_EDGE (e, ei, to->succs)
8830 /* Remove INSN from the instruction stream.
8831 INSN should have any dependencies. */
8833 sched_remove_insn (rtx_insn *insn)
8835 sd_finish_insn (insn);
8837 change_queue_index (insn, QUEUE_NOWHERE);
8838 current_sched_info->add_remove_insn (insn, 1);
8842 /* Clear priorities of all instructions, that are forward dependent on INSN.
8843 Store in vector pointed to by ROOTS_PTR insns on which priority () should
8844 be invoked to initialize all cleared priorities. */
8846 clear_priorities (rtx_insn *insn, rtx_vec_t *roots_ptr)
8848 sd_iterator_def sd_it;
8850 bool insn_is_root_p = true;
8852 gcc_assert (QUEUE_INDEX (insn) != QUEUE_SCHEDULED);
8854 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
8856 rtx_insn *pro = DEP_PRO (dep);
8858 if (INSN_PRIORITY_STATUS (pro) >= 0
8859 && QUEUE_INDEX (insn) != QUEUE_SCHEDULED)
8861 /* If DEP doesn't contribute to priority then INSN itself should
8862 be added to priority roots. */
8863 if (contributes_to_priority_p (dep))
8864 insn_is_root_p = false;
8866 INSN_PRIORITY_STATUS (pro) = -1;
8867 clear_priorities (pro, roots_ptr);
8872 roots_ptr->safe_push (insn);
8875 /* Recompute priorities of instructions, whose priorities might have been
8876 changed. ROOTS is a vector of instructions whose priority computation will
8877 trigger initialization of all cleared priorities. */
8879 calc_priorities (rtx_vec_t roots)
8884 FOR_EACH_VEC_ELT (roots, i, insn)
8889 /* Add dependences between JUMP and other instructions in the recovery
8890 block. INSN is the first insn the recovery block. */
8892 add_jump_dependencies (rtx_insn *insn, rtx_insn *jump)
8896 insn = NEXT_INSN (insn);
8900 if (dep_list_size (insn, SD_LIST_FORW) == 0)
8902 dep_def _new_dep, *new_dep = &_new_dep;
8904 init_dep (new_dep, insn, jump, REG_DEP_ANTI);
8905 sd_add_dep (new_dep, false);
8910 gcc_assert (!sd_lists_empty_p (jump, SD_LIST_BACK));
8913 /* Extend data structures for logical insn UID. */
8915 sched_extend_luids (void)
8917 int new_luids_max_uid = get_max_uid () + 1;
8919 sched_luids.safe_grow_cleared (new_luids_max_uid);
8922 /* Initialize LUID for INSN. */
8924 sched_init_insn_luid (rtx_insn *insn)
8926 int i = INSN_P (insn) ? 1 : common_sched_info->luid_for_non_insn (insn);
8931 luid = sched_max_luid;
8932 sched_max_luid += i;
8937 SET_INSN_LUID (insn, luid);
8940 /* Initialize luids for BBS.
8941 The hook common_sched_info->luid_for_non_insn () is used to determine
8942 if notes, labels, etc. need luids. */
8944 sched_init_luids (bb_vec_t bbs)
8949 sched_extend_luids ();
8950 FOR_EACH_VEC_ELT (bbs, i, bb)
8954 FOR_BB_INSNS (bb, insn)
8955 sched_init_insn_luid (insn);
8961 sched_finish_luids (void)
8963 sched_luids.release ();
8967 /* Return logical uid of INSN. Helpful while debugging. */
8969 insn_luid (rtx_insn *insn)
8971 return INSN_LUID (insn);
8974 /* Extend per insn data in the target. */
8976 sched_extend_target (void)
8978 if (targetm.sched.h_i_d_extended)
8979 targetm.sched.h_i_d_extended ();
8982 /* Extend global scheduler structures (those, that live across calls to
8983 schedule_block) to include information about just emitted INSN. */
8987 int reserve = (get_max_uid () + 1 - h_i_d.length ());
8989 && ! h_i_d.space (reserve))
8991 h_i_d.safe_grow_cleared (3 * get_max_uid () / 2);
8992 sched_extend_target ();
8996 /* Initialize h_i_d entry of the INSN with default values.
8997 Values, that are not explicitly initialized here, hold zero. */
8999 init_h_i_d (rtx_insn *insn)
9001 if (INSN_LUID (insn) > 0)
9003 INSN_COST (insn) = -1;
9004 QUEUE_INDEX (insn) = QUEUE_NOWHERE;
9005 INSN_TICK (insn) = INVALID_TICK;
9006 INSN_EXACT_TICK (insn) = INVALID_TICK;
9007 INTER_TICK (insn) = INVALID_TICK;
9008 TODO_SPEC (insn) = HARD_DEP;
9009 INSN_AUTOPREF_MULTIPASS_DATA (insn)[0].status
9010 = AUTOPREF_MULTIPASS_DATA_UNINITIALIZED;
9011 INSN_AUTOPREF_MULTIPASS_DATA (insn)[1].status
9012 = AUTOPREF_MULTIPASS_DATA_UNINITIALIZED;
9016 /* Initialize haifa_insn_data for BBS. */
9018 haifa_init_h_i_d (bb_vec_t bbs)
9024 FOR_EACH_VEC_ELT (bbs, i, bb)
9028 FOR_BB_INSNS (bb, insn)
9033 /* Finalize haifa_insn_data. */
9035 haifa_finish_h_i_d (void)
9038 haifa_insn_data_t data;
9039 struct reg_use_data *use, *next;
9041 FOR_EACH_VEC_ELT (h_i_d, i, data)
9043 free (data->max_reg_pressure);
9044 free (data->reg_pressure);
9045 for (use = data->reg_use_list; use != NULL; use = next)
9047 next = use->next_insn_use;
9054 /* Init data for the new insn INSN. */
9056 haifa_init_insn (rtx_insn *insn)
9058 gcc_assert (insn != NULL);
9060 sched_extend_luids ();
9061 sched_init_insn_luid (insn);
9062 sched_extend_target ();
9063 sched_deps_init (false);
9067 if (adding_bb_to_current_region_p)
9069 sd_init_insn (insn);
9071 /* Extend dependency caches by one element. */
9072 extend_dependency_caches (1, false);
9074 if (sched_pressure != SCHED_PRESSURE_NONE)
9075 init_insn_reg_pressure_info (insn);
9078 /* Init data for the new basic block BB which comes after AFTER. */
9080 haifa_init_only_bb (basic_block bb, basic_block after)
9082 gcc_assert (bb != NULL);
9086 if (common_sched_info->add_block)
9087 /* This changes only data structures of the front-end. */
9088 common_sched_info->add_block (bb, after);
9091 /* A generic version of sched_split_block (). */
9093 sched_split_block_1 (basic_block first_bb, rtx after)
9097 e = split_block (first_bb, after);
9098 gcc_assert (e->src == first_bb);
9100 /* sched_split_block emits note if *check == BB_END. Probably it
9101 is better to rip that note off. */
9106 /* A generic version of sched_create_empty_bb (). */
9108 sched_create_empty_bb_1 (basic_block after)
9110 return create_empty_bb (after);
9113 /* Insert PAT as an INSN into the schedule and update the necessary data
9114 structures to account for it. */
9116 sched_emit_insn (rtx pat)
9118 rtx_insn *insn = emit_insn_before (pat, first_nonscheduled_insn ());
9119 haifa_init_insn (insn);
9121 if (current_sched_info->add_remove_insn)
9122 current_sched_info->add_remove_insn (insn, 0);
9124 (*current_sched_info->begin_schedule_ready) (insn);
9125 scheduled_insns.safe_push (insn);
9127 last_scheduled_insn = insn;
9131 /* This function returns a candidate satisfying dispatch constraints from
9135 ready_remove_first_dispatch (struct ready_list *ready)
9138 rtx_insn *insn = ready_element (ready, 0);
9140 if (ready->n_ready == 1
9142 || INSN_CODE (insn) < 0
9143 || !active_insn_p (insn)
9144 || targetm.sched.dispatch (insn, FITS_DISPATCH_WINDOW))
9145 return ready_remove_first (ready);
9147 for (i = 1; i < ready->n_ready; i++)
9149 insn = ready_element (ready, i);
9152 || INSN_CODE (insn) < 0
9153 || !active_insn_p (insn))
9156 if (targetm.sched.dispatch (insn, FITS_DISPATCH_WINDOW))
9158 /* Return ith element of ready. */
9159 insn = ready_remove (ready, i);
9164 if (targetm.sched.dispatch (NULL, DISPATCH_VIOLATION))
9165 return ready_remove_first (ready);
9167 for (i = 1; i < ready->n_ready; i++)
9169 insn = ready_element (ready, i);
9172 || INSN_CODE (insn) < 0
9173 || !active_insn_p (insn))
9176 /* Return i-th element of ready. */
9177 if (targetm.sched.dispatch (insn, IS_CMP))
9178 return ready_remove (ready, i);
9181 return ready_remove_first (ready);
9184 /* Get number of ready insn in the ready list. */
9187 number_in_ready (void)
9189 return ready.n_ready;
9192 /* Get number of ready's in the ready list. */
9195 get_ready_element (int i)
9197 return ready_element (&ready, i);
9200 #endif /* INSN_SCHEDULING */