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"
131 #include "cfghooks.h"
134 #include "insn-config.h"
138 #include "insn-attr.h"
140 #include "cfgbuild.h"
141 #include "sched-int.h"
142 #include "common/common-target.h"
146 #include "dumpfile.h"
147 #include "print-rtl.h"
149 #ifdef INSN_SCHEDULING
151 /* True if we do register pressure relief through live-range
153 static bool live_range_shrinkage_p;
155 /* Switch on live range shrinkage. */
157 initialize_live_range_shrinkage (void)
159 live_range_shrinkage_p = true;
162 /* Switch off live range shrinkage. */
164 finish_live_range_shrinkage (void)
166 live_range_shrinkage_p = false;
169 /* issue_rate is the number of insns that can be scheduled in the same
170 machine cycle. It can be defined in the config/mach/mach.h file,
171 otherwise we set it to 1. */
175 /* This can be set to true by a backend if the scheduler should not
176 enable a DCE pass. */
179 /* The current initiation interval used when modulo scheduling. */
180 static int modulo_ii;
182 /* The maximum number of stages we are prepared to handle. */
183 static int modulo_max_stages;
185 /* The number of insns that exist in each iteration of the loop. We use this
186 to detect when we've scheduled all insns from the first iteration. */
187 static int modulo_n_insns;
189 /* The current count of insns in the first iteration of the loop that have
190 already been scheduled. */
191 static int modulo_insns_scheduled;
193 /* The maximum uid of insns from the first iteration of the loop. */
194 static int modulo_iter0_max_uid;
196 /* The number of times we should attempt to backtrack when modulo scheduling.
197 Decreased each time we have to backtrack. */
198 static int modulo_backtracks_left;
200 /* The stage in which the last insn from the original loop was
202 static int modulo_last_stage;
204 /* sched-verbose controls the amount of debugging output the
205 scheduler prints. It is controlled by -fsched-verbose=N:
206 N=0: no debugging output.
208 N=2: bb's probabilities, detailed ready list info, unit/insn info.
209 N=3: rtl at abort point, control-flow, regions info.
210 N=5: dependences info. */
211 int sched_verbose = 0;
213 /* Debugging file. All printouts are sent to dump. */
214 FILE *sched_dump = 0;
216 /* This is a placeholder for the scheduler parameters common
217 to all schedulers. */
218 struct common_sched_info_def *common_sched_info;
220 #define INSN_TICK(INSN) (HID (INSN)->tick)
221 #define INSN_EXACT_TICK(INSN) (HID (INSN)->exact_tick)
222 #define INSN_TICK_ESTIMATE(INSN) (HID (INSN)->tick_estimate)
223 #define INTER_TICK(INSN) (HID (INSN)->inter_tick)
224 #define FEEDS_BACKTRACK_INSN(INSN) (HID (INSN)->feeds_backtrack_insn)
225 #define SHADOW_P(INSN) (HID (INSN)->shadow_p)
226 #define MUST_RECOMPUTE_SPEC_P(INSN) (HID (INSN)->must_recompute_spec)
227 /* Cached cost of the instruction. Use insn_cost to get cost of the
228 insn. -1 here means that the field is not initialized. */
229 #define INSN_COST(INSN) (HID (INSN)->cost)
231 /* If INSN_TICK of an instruction is equal to INVALID_TICK,
232 then it should be recalculated from scratch. */
233 #define INVALID_TICK (-(max_insn_queue_index + 1))
234 /* The minimal value of the INSN_TICK of an instruction. */
235 #define MIN_TICK (-max_insn_queue_index)
237 /* Original order of insns in the ready list.
238 Used to keep order of normal insns while separating DEBUG_INSNs. */
239 #define INSN_RFS_DEBUG_ORIG_ORDER(INSN) (HID (INSN)->rfs_debug_orig_order)
241 /* The deciding reason for INSN's place in the ready list. */
242 #define INSN_LAST_RFS_WIN(INSN) (HID (INSN)->last_rfs_win)
244 /* List of important notes we must keep around. This is a pointer to the
245 last element in the list. */
248 static struct spec_info_def spec_info_var;
249 /* Description of the speculative part of the scheduling.
250 If NULL - no speculation. */
251 spec_info_t spec_info = NULL;
253 /* True, if recovery block was added during scheduling of current block.
254 Used to determine, if we need to fix INSN_TICKs. */
255 static bool haifa_recovery_bb_recently_added_p;
257 /* True, if recovery block was added during this scheduling pass.
258 Used to determine if we should have empty memory pools of dependencies
259 after finishing current region. */
260 bool haifa_recovery_bb_ever_added_p;
262 /* Counters of different types of speculative instructions. */
263 static int nr_begin_data, nr_be_in_data, nr_begin_control, nr_be_in_control;
265 /* Array used in {unlink, restore}_bb_notes. */
266 static rtx_insn **bb_header = 0;
268 /* Basic block after which recovery blocks will be created. */
269 static basic_block before_recovery;
271 /* Basic block just before the EXIT_BLOCK and after recovery, if we have
273 basic_block after_recovery;
275 /* FALSE if we add bb to another region, so we don't need to initialize it. */
276 bool adding_bb_to_current_region_p = true;
280 /* An instruction is ready to be scheduled when all insns preceding it
281 have already been scheduled. It is important to ensure that all
282 insns which use its result will not be executed until its result
283 has been computed. An insn is maintained in one of four structures:
285 (P) the "Pending" set of insns which cannot be scheduled until
286 their dependencies have been satisfied.
287 (Q) the "Queued" set of insns that can be scheduled when sufficient
289 (R) the "Ready" list of unscheduled, uncommitted insns.
290 (S) the "Scheduled" list of insns.
292 Initially, all insns are either "Pending" or "Ready" depending on
293 whether their dependencies are satisfied.
295 Insns move from the "Ready" list to the "Scheduled" list as they
296 are committed to the schedule. As this occurs, the insns in the
297 "Pending" list have their dependencies satisfied and move to either
298 the "Ready" list or the "Queued" set depending on whether
299 sufficient time has passed to make them ready. As time passes,
300 insns move from the "Queued" set to the "Ready" list.
302 The "Pending" list (P) are the insns in the INSN_FORW_DEPS of the
303 unscheduled insns, i.e., those that are ready, queued, and pending.
304 The "Queued" set (Q) is implemented by the variable `insn_queue'.
305 The "Ready" list (R) is implemented by the variables `ready' and
307 The "Scheduled" list (S) is the new insn chain built by this pass.
309 The transition (R->S) is implemented in the scheduling loop in
310 `schedule_block' when the best insn to schedule is chosen.
311 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
312 insns move from the ready list to the scheduled list.
313 The transition (Q->R) is implemented in 'queue_to_insn' as time
314 passes or stalls are introduced. */
316 /* Implement a circular buffer to delay instructions until sufficient
317 time has passed. For the new pipeline description interface,
318 MAX_INSN_QUEUE_INDEX is a power of two minus one which is not less
319 than maximal time of instruction execution computed by genattr.c on
320 the base maximal time of functional unit reservations and getting a
321 result. This is the longest time an insn may be queued. */
323 static rtx_insn_list **insn_queue;
324 static int q_ptr = 0;
325 static int q_size = 0;
326 #define NEXT_Q(X) (((X)+1) & max_insn_queue_index)
327 #define NEXT_Q_AFTER(X, C) (((X)+C) & max_insn_queue_index)
329 #define QUEUE_SCHEDULED (-3)
330 #define QUEUE_NOWHERE (-2)
331 #define QUEUE_READY (-1)
332 /* QUEUE_SCHEDULED - INSN is scheduled.
333 QUEUE_NOWHERE - INSN isn't scheduled yet and is neither in
335 QUEUE_READY - INSN is in ready list.
336 N >= 0 - INSN queued for X [where NEXT_Q_AFTER (q_ptr, X) == N] cycles. */
338 #define QUEUE_INDEX(INSN) (HID (INSN)->queue_index)
340 /* The following variable value refers for all current and future
341 reservations of the processor units. */
344 /* The following variable value is size of memory representing all
345 current and future reservations of the processor units. */
346 size_t dfa_state_size;
348 /* The following array is used to find the best insn from ready when
349 the automaton pipeline interface is used. */
350 signed char *ready_try = NULL;
352 /* The ready list. */
353 struct ready_list ready = {NULL, 0, 0, 0, 0};
355 /* The pointer to the ready list (to be removed). */
356 static struct ready_list *readyp = &ready;
358 /* Scheduling clock. */
359 static int clock_var;
361 /* Clock at which the previous instruction was issued. */
362 static int last_clock_var;
364 /* Set to true if, when queuing a shadow insn, we discover that it would be
365 scheduled too late. */
366 static bool must_backtrack;
368 /* The following variable value is number of essential insns issued on
369 the current cycle. An insn is essential one if it changes the
371 int cycle_issued_insns;
373 /* This records the actual schedule. It is built up during the main phase
374 of schedule_block, and afterwards used to reorder the insns in the RTL. */
375 static vec<rtx_insn *> scheduled_insns;
377 static int may_trap_exp (const_rtx, int);
379 /* Nonzero iff the address is comprised from at most 1 register. */
380 #define CONST_BASED_ADDRESS_P(x) \
382 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
383 || (GET_CODE (x) == LO_SUM)) \
384 && (CONSTANT_P (XEXP (x, 0)) \
385 || CONSTANT_P (XEXP (x, 1)))))
387 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
388 as found by analyzing insn's expression. */
391 static int haifa_luid_for_non_insn (rtx x);
393 /* Haifa version of sched_info hooks common to all headers. */
394 const struct common_sched_info_def haifa_common_sched_info =
396 NULL, /* fix_recovery_cfg */
397 NULL, /* add_block */
398 NULL, /* estimate_number_of_insns */
399 haifa_luid_for_non_insn, /* luid_for_non_insn */
400 SCHED_PASS_UNKNOWN /* sched_pass_id */
403 /* Mapping from instruction UID to its Logical UID. */
404 vec<int> sched_luids = vNULL;
406 /* Next LUID to assign to an instruction. */
407 int sched_max_luid = 1;
409 /* Haifa Instruction Data. */
410 vec<haifa_insn_data_def> h_i_d = vNULL;
412 void (* sched_init_only_bb) (basic_block, basic_block);
414 /* Split block function. Different schedulers might use different functions
415 to handle their internal data consistent. */
416 basic_block (* sched_split_block) (basic_block, rtx);
418 /* Create empty basic block after the specified block. */
419 basic_block (* sched_create_empty_bb) (basic_block);
421 /* Return the number of cycles until INSN is expected to be ready.
422 Return zero if it already is. */
424 insn_delay (rtx_insn *insn)
426 return MAX (INSN_TICK (insn) - clock_var, 0);
430 may_trap_exp (const_rtx x, int is_store)
439 if (code == MEM && may_trap_p (x))
446 /* The insn uses memory: a volatile load. */
447 if (MEM_VOLATILE_P (x))
449 /* An exception-free load. */
452 /* A load with 1 base register, to be further checked. */
453 if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))
454 return PFREE_CANDIDATE;
455 /* No info on the load, to be further checked. */
456 return PRISKY_CANDIDATE;
461 int i, insn_class = TRAP_FREE;
463 /* Neither store nor load, check if it may cause a trap. */
466 /* Recursive step: walk the insn... */
467 fmt = GET_RTX_FORMAT (code);
468 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
472 int tmp_class = may_trap_exp (XEXP (x, i), is_store);
473 insn_class = WORST_CLASS (insn_class, tmp_class);
475 else if (fmt[i] == 'E')
478 for (j = 0; j < XVECLEN (x, i); j++)
480 int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);
481 insn_class = WORST_CLASS (insn_class, tmp_class);
482 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
486 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
493 /* Classifies rtx X of an insn for the purpose of verifying that X can be
494 executed speculatively (and consequently the insn can be moved
495 speculatively), by examining X, returning:
496 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
497 TRAP_FREE: non-load insn.
498 IFREE: load from a globally safe location.
499 IRISKY: volatile load.
500 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
501 being either PFREE or PRISKY. */
504 haifa_classify_rtx (const_rtx x)
506 int tmp_class = TRAP_FREE;
507 int insn_class = TRAP_FREE;
510 if (GET_CODE (x) == PARALLEL)
512 int i, len = XVECLEN (x, 0);
514 for (i = len - 1; i >= 0; i--)
516 tmp_class = haifa_classify_rtx (XVECEXP (x, 0, i));
517 insn_class = WORST_CLASS (insn_class, tmp_class);
518 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
528 /* Test if it is a 'store'. */
529 tmp_class = may_trap_exp (XEXP (x, 0), 1);
532 /* Test if it is a store. */
533 tmp_class = may_trap_exp (SET_DEST (x), 1);
534 if (tmp_class == TRAP_RISKY)
536 /* Test if it is a load. */
538 WORST_CLASS (tmp_class,
539 may_trap_exp (SET_SRC (x), 0));
542 tmp_class = haifa_classify_rtx (COND_EXEC_CODE (x));
543 if (tmp_class == TRAP_RISKY)
545 tmp_class = WORST_CLASS (tmp_class,
546 may_trap_exp (COND_EXEC_TEST (x), 0));
549 tmp_class = TRAP_RISKY;
553 insn_class = tmp_class;
560 haifa_classify_insn (const_rtx insn)
562 return haifa_classify_rtx (PATTERN (insn));
565 /* After the scheduler initialization function has been called, this function
566 can be called to enable modulo scheduling. II is the initiation interval
567 we should use, it affects the delays for delay_pairs that were recorded as
568 separated by a given number of stages.
570 MAX_STAGES provides us with a limit
571 after which we give up scheduling; the caller must have unrolled at least
572 as many copies of the loop body and recorded delay_pairs for them.
574 INSNS is the number of real (non-debug) insns in one iteration of
575 the loop. MAX_UID can be used to test whether an insn belongs to
576 the first iteration of the loop; all of them have a uid lower than
579 set_modulo_params (int ii, int max_stages, int insns, int max_uid)
582 modulo_max_stages = max_stages;
583 modulo_n_insns = insns;
584 modulo_iter0_max_uid = max_uid;
585 modulo_backtracks_left = PARAM_VALUE (PARAM_MAX_MODULO_BACKTRACK_ATTEMPTS);
588 /* A structure to record a pair of insns where the first one is a real
589 insn that has delay slots, and the second is its delayed shadow.
590 I1 is scheduled normally and will emit an assembly instruction,
591 while I2 describes the side effect that takes place at the
592 transition between cycles CYCLES and (CYCLES + 1) after I1. */
595 struct delay_pair *next_same_i1;
598 /* When doing modulo scheduling, we a delay_pair can also be used to
599 show that I1 and I2 are the same insn in a different stage. If that
600 is the case, STAGES will be nonzero. */
604 /* Helpers for delay hashing. */
606 struct delay_i1_hasher : nofree_ptr_hash <delay_pair>
608 typedef void *compare_type;
609 static inline hashval_t hash (const delay_pair *);
610 static inline bool equal (const delay_pair *, const void *);
613 /* Returns a hash value for X, based on hashing just I1. */
616 delay_i1_hasher::hash (const delay_pair *x)
618 return htab_hash_pointer (x->i1);
621 /* Return true if I1 of pair X is the same as that of pair Y. */
624 delay_i1_hasher::equal (const delay_pair *x, const void *y)
629 struct delay_i2_hasher : free_ptr_hash <delay_pair>
631 typedef void *compare_type;
632 static inline hashval_t hash (const delay_pair *);
633 static inline bool equal (const delay_pair *, const void *);
636 /* Returns a hash value for X, based on hashing just I2. */
639 delay_i2_hasher::hash (const delay_pair *x)
641 return htab_hash_pointer (x->i2);
644 /* Return true if I2 of pair X is the same as that of pair Y. */
647 delay_i2_hasher::equal (const delay_pair *x, const void *y)
652 /* Two hash tables to record delay_pairs, one indexed by I1 and the other
654 static hash_table<delay_i1_hasher> *delay_htab;
655 static hash_table<delay_i2_hasher> *delay_htab_i2;
657 /* Called through htab_traverse. Walk the hashtable using I2 as
658 index, and delete all elements involving an UID higher than
659 that pointed to by *DATA. */
661 haifa_htab_i2_traverse (delay_pair **slot, int *data)
664 struct delay_pair *p = *slot;
665 if (INSN_UID (p->i2) >= maxuid || INSN_UID (p->i1) >= maxuid)
667 delay_htab_i2->clear_slot (slot);
672 /* Called through htab_traverse. Walk the hashtable using I2 as
673 index, and delete all elements involving an UID higher than
674 that pointed to by *DATA. */
676 haifa_htab_i1_traverse (delay_pair **pslot, int *data)
679 struct delay_pair *p, *first, **pprev;
681 if (INSN_UID ((*pslot)->i1) >= maxuid)
683 delay_htab->clear_slot (pslot);
687 for (p = *pslot; p; p = p->next_same_i1)
689 if (INSN_UID (p->i2) < maxuid)
692 pprev = &p->next_same_i1;
697 delay_htab->clear_slot (pslot);
703 /* Discard all delay pairs which involve an insn with an UID higher
706 discard_delay_pairs_above (int max_uid)
708 delay_htab->traverse <int *, haifa_htab_i1_traverse> (&max_uid);
709 delay_htab_i2->traverse <int *, haifa_htab_i2_traverse> (&max_uid);
712 /* This function can be called by a port just before it starts the final
713 scheduling pass. It records the fact that an instruction with delay
714 slots has been split into two insns, I1 and I2. The first one will be
715 scheduled normally and initiates the operation. The second one is a
716 shadow which must follow a specific number of cycles after I1; its only
717 purpose is to show the side effect that occurs at that cycle in the RTL.
718 If a JUMP_INSN or a CALL_INSN has been split, I1 should be a normal INSN,
719 while I2 retains the original insn type.
721 There are two ways in which the number of cycles can be specified,
722 involving the CYCLES and STAGES arguments to this function. If STAGES
723 is zero, we just use the value of CYCLES. Otherwise, STAGES is a factor
724 which is multiplied by MODULO_II to give the number of cycles. This is
725 only useful if the caller also calls set_modulo_params to enable modulo
729 record_delay_slot_pair (rtx_insn *i1, rtx_insn *i2, int cycles, int stages)
731 struct delay_pair *p = XNEW (struct delay_pair);
732 struct delay_pair **slot;
741 delay_htab = new hash_table<delay_i1_hasher> (10);
742 delay_htab_i2 = new hash_table<delay_i2_hasher> (10);
744 slot = delay_htab->find_slot_with_hash (i1, htab_hash_pointer (i1), INSERT);
745 p->next_same_i1 = *slot;
747 slot = delay_htab_i2->find_slot (p, INSERT);
751 /* Examine the delay pair hashtable to see if INSN is a shadow for another,
752 and return the other insn if so. Return NULL otherwise. */
754 real_insn_for_shadow (rtx_insn *insn)
756 struct delay_pair *pair;
761 pair = delay_htab_i2->find_with_hash (insn, htab_hash_pointer (insn));
762 if (!pair || pair->stages > 0)
767 /* For a pair P of insns, return the fixed distance in cycles from the first
768 insn after which the second must be scheduled. */
770 pair_delay (struct delay_pair *p)
775 return p->stages * modulo_ii;
778 /* Given an insn INSN, add a dependence on its delayed shadow if it
779 has one. Also try to find situations where shadows depend on each other
780 and add dependencies to the real insns to limit the amount of backtracking
783 add_delay_dependencies (rtx_insn *insn)
785 struct delay_pair *pair;
786 sd_iterator_def sd_it;
792 pair = delay_htab_i2->find_with_hash (insn, htab_hash_pointer (insn));
795 add_dependence (insn, pair->i1, REG_DEP_ANTI);
799 FOR_EACH_DEP (pair->i2, SD_LIST_BACK, sd_it, dep)
801 rtx_insn *pro = DEP_PRO (dep);
802 struct delay_pair *other_pair
803 = delay_htab_i2->find_with_hash (pro, htab_hash_pointer (pro));
804 if (!other_pair || other_pair->stages)
806 if (pair_delay (other_pair) >= pair_delay (pair))
808 if (sched_verbose >= 4)
810 fprintf (sched_dump, ";;\tadding dependence %d <- %d\n",
811 INSN_UID (other_pair->i1),
812 INSN_UID (pair->i1));
813 fprintf (sched_dump, ";;\tpair1 %d <- %d, cost %d\n",
817 fprintf (sched_dump, ";;\tpair2 %d <- %d, cost %d\n",
818 INSN_UID (other_pair->i1),
819 INSN_UID (other_pair->i2),
820 pair_delay (other_pair));
822 add_dependence (pair->i1, other_pair->i1, REG_DEP_ANTI);
827 /* Forward declarations. */
829 static int priority (rtx_insn *);
830 static int autopref_rank_for_schedule (const rtx_insn *, const rtx_insn *);
831 static int rank_for_schedule (const void *, const void *);
832 static void swap_sort (rtx_insn **, int);
833 static void queue_insn (rtx_insn *, int, const char *);
834 static int schedule_insn (rtx_insn *);
835 static void adjust_priority (rtx_insn *);
836 static void advance_one_cycle (void);
837 static void extend_h_i_d (void);
840 /* Notes handling mechanism:
841 =========================
842 Generally, NOTES are saved before scheduling and restored after scheduling.
843 The scheduler distinguishes between two types of notes:
845 (1) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
846 Before scheduling a region, a pointer to the note is added to the insn
847 that follows or precedes it. (This happens as part of the data dependence
848 computation). After scheduling an insn, the pointer contained in it is
849 used for regenerating the corresponding note (in reemit_notes).
851 (2) All other notes (e.g. INSN_DELETED): Before scheduling a block,
852 these notes are put in a list (in rm_other_notes() and
853 unlink_other_notes ()). After scheduling the block, these notes are
854 inserted at the beginning of the block (in schedule_block()). */
856 static void ready_add (struct ready_list *, rtx_insn *, bool);
857 static rtx_insn *ready_remove_first (struct ready_list *);
858 static rtx_insn *ready_remove_first_dispatch (struct ready_list *ready);
860 static void queue_to_ready (struct ready_list *);
861 static int early_queue_to_ready (state_t, struct ready_list *);
863 /* The following functions are used to implement multi-pass scheduling
864 on the first cycle. */
865 static rtx_insn *ready_remove (struct ready_list *, int);
866 static void ready_remove_insn (rtx_insn *);
868 static void fix_inter_tick (rtx_insn *, rtx_insn *);
869 static int fix_tick_ready (rtx_insn *);
870 static void change_queue_index (rtx_insn *, int);
872 /* The following functions are used to implement scheduling of data/control
873 speculative instructions. */
875 static void extend_h_i_d (void);
876 static void init_h_i_d (rtx_insn *);
877 static int haifa_speculate_insn (rtx_insn *, ds_t, rtx *);
878 static void generate_recovery_code (rtx_insn *);
879 static void process_insn_forw_deps_be_in_spec (rtx_insn *, rtx_insn *, ds_t);
880 static void begin_speculative_block (rtx_insn *);
881 static void add_to_speculative_block (rtx_insn *);
882 static void init_before_recovery (basic_block *);
883 static void create_check_block_twin (rtx_insn *, bool);
884 static void fix_recovery_deps (basic_block);
885 static bool haifa_change_pattern (rtx_insn *, rtx);
886 static void dump_new_block_header (int, basic_block, rtx_insn *, rtx_insn *);
887 static void restore_bb_notes (basic_block);
888 static void fix_jump_move (rtx_insn *);
889 static void move_block_after_check (rtx_insn *);
890 static void move_succs (vec<edge, va_gc> **, basic_block);
891 static void sched_remove_insn (rtx_insn *);
892 static void clear_priorities (rtx_insn *, rtx_vec_t *);
893 static void calc_priorities (rtx_vec_t);
894 static void add_jump_dependencies (rtx_insn *, rtx_insn *);
896 #endif /* INSN_SCHEDULING */
898 /* Point to state used for the current scheduling pass. */
899 struct haifa_sched_info *current_sched_info;
901 #ifndef INSN_SCHEDULING
903 schedule_insns (void)
908 /* Do register pressure sensitive insn scheduling if the flag is set
910 enum sched_pressure_algorithm sched_pressure;
912 /* Map regno -> its pressure class. The map defined only when
913 SCHED_PRESSURE != SCHED_PRESSURE_NONE. */
914 enum reg_class *sched_regno_pressure_class;
916 /* The current register pressure. Only elements corresponding pressure
917 classes are defined. */
918 static int curr_reg_pressure[N_REG_CLASSES];
920 /* Saved value of the previous array. */
921 static int saved_reg_pressure[N_REG_CLASSES];
923 /* Register living at given scheduling point. */
924 static bitmap curr_reg_live;
926 /* Saved value of the previous array. */
927 static bitmap saved_reg_live;
929 /* Registers mentioned in the current region. */
930 static bitmap region_ref_regs;
932 /* Effective number of available registers of a given class (see comment
933 in sched_pressure_start_bb). */
934 static int sched_class_regs_num[N_REG_CLASSES];
935 /* Number of call_used_regs. This is a helper for calculating of
936 sched_class_regs_num. */
937 static int call_used_regs_num[N_REG_CLASSES];
939 /* Initiate register pressure relative info for scheduling the current
940 region. Currently it is only clearing register mentioned in the
943 sched_init_region_reg_pressure_info (void)
945 bitmap_clear (region_ref_regs);
948 /* PRESSURE[CL] describes the pressure on register class CL. Update it
949 for the birth (if BIRTH_P) or death (if !BIRTH_P) of register REGNO.
950 LIVE tracks the set of live registers; if it is null, assume that
951 every birth or death is genuine. */
953 mark_regno_birth_or_death (bitmap live, int *pressure, int regno, bool birth_p)
955 enum reg_class pressure_class;
957 pressure_class = sched_regno_pressure_class[regno];
958 if (regno >= FIRST_PSEUDO_REGISTER)
960 if (pressure_class != NO_REGS)
964 if (!live || bitmap_set_bit (live, regno))
965 pressure[pressure_class]
966 += (ira_reg_class_max_nregs
967 [pressure_class][PSEUDO_REGNO_MODE (regno)]);
971 if (!live || bitmap_clear_bit (live, regno))
972 pressure[pressure_class]
973 -= (ira_reg_class_max_nregs
974 [pressure_class][PSEUDO_REGNO_MODE (regno)]);
978 else if (pressure_class != NO_REGS
979 && ! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
983 if (!live || bitmap_set_bit (live, regno))
984 pressure[pressure_class]++;
988 if (!live || bitmap_clear_bit (live, regno))
989 pressure[pressure_class]--;
994 /* Initiate current register pressure related info from living
995 registers given by LIVE. */
997 initiate_reg_pressure_info (bitmap live)
1003 for (i = 0; i < ira_pressure_classes_num; i++)
1004 curr_reg_pressure[ira_pressure_classes[i]] = 0;
1005 bitmap_clear (curr_reg_live);
1006 EXECUTE_IF_SET_IN_BITMAP (live, 0, j, bi)
1007 if (sched_pressure == SCHED_PRESSURE_MODEL
1008 || current_nr_blocks == 1
1009 || bitmap_bit_p (region_ref_regs, j))
1010 mark_regno_birth_or_death (curr_reg_live, curr_reg_pressure, j, true);
1013 /* Mark registers in X as mentioned in the current region. */
1015 setup_ref_regs (rtx x)
1018 const RTX_CODE code = GET_CODE (x);
1023 bitmap_set_range (region_ref_regs, REGNO (x), REG_NREGS (x));
1026 fmt = GET_RTX_FORMAT (code);
1027 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1029 setup_ref_regs (XEXP (x, i));
1030 else if (fmt[i] == 'E')
1032 for (j = 0; j < XVECLEN (x, i); j++)
1033 setup_ref_regs (XVECEXP (x, i, j));
1037 /* Initiate current register pressure related info at the start of
1040 initiate_bb_reg_pressure_info (basic_block bb)
1042 unsigned int i ATTRIBUTE_UNUSED;
1045 if (current_nr_blocks > 1)
1046 FOR_BB_INSNS (bb, insn)
1047 if (NONDEBUG_INSN_P (insn))
1048 setup_ref_regs (PATTERN (insn));
1049 initiate_reg_pressure_info (df_get_live_in (bb));
1050 if (bb_has_eh_pred (bb))
1053 unsigned int regno = EH_RETURN_DATA_REGNO (i);
1055 if (regno == INVALID_REGNUM)
1057 if (! bitmap_bit_p (df_get_live_in (bb), regno))
1058 mark_regno_birth_or_death (curr_reg_live, curr_reg_pressure,
1063 /* Save current register pressure related info. */
1065 save_reg_pressure (void)
1069 for (i = 0; i < ira_pressure_classes_num; i++)
1070 saved_reg_pressure[ira_pressure_classes[i]]
1071 = curr_reg_pressure[ira_pressure_classes[i]];
1072 bitmap_copy (saved_reg_live, curr_reg_live);
1075 /* Restore saved register pressure related info. */
1077 restore_reg_pressure (void)
1081 for (i = 0; i < ira_pressure_classes_num; i++)
1082 curr_reg_pressure[ira_pressure_classes[i]]
1083 = saved_reg_pressure[ira_pressure_classes[i]];
1084 bitmap_copy (curr_reg_live, saved_reg_live);
1087 /* Return TRUE if the register is dying after its USE. */
1089 dying_use_p (struct reg_use_data *use)
1091 struct reg_use_data *next;
1093 for (next = use->next_regno_use; next != use; next = next->next_regno_use)
1094 if (NONDEBUG_INSN_P (next->insn)
1095 && QUEUE_INDEX (next->insn) != QUEUE_SCHEDULED)
1100 /* Print info about the current register pressure and its excess for
1101 each pressure class. */
1103 print_curr_reg_pressure (void)
1108 fprintf (sched_dump, ";;\t");
1109 for (i = 0; i < ira_pressure_classes_num; i++)
1111 cl = ira_pressure_classes[i];
1112 gcc_assert (curr_reg_pressure[cl] >= 0);
1113 fprintf (sched_dump, " %s:%d(%d)", reg_class_names[cl],
1114 curr_reg_pressure[cl],
1115 curr_reg_pressure[cl] - sched_class_regs_num[cl]);
1117 fprintf (sched_dump, "\n");
1120 /* Determine if INSN has a condition that is clobbered if a register
1121 in SET_REGS is modified. */
1123 cond_clobbered_p (rtx_insn *insn, HARD_REG_SET set_regs)
1125 rtx pat = PATTERN (insn);
1126 gcc_assert (GET_CODE (pat) == COND_EXEC);
1127 if (TEST_HARD_REG_BIT (set_regs, REGNO (XEXP (COND_EXEC_TEST (pat), 0))))
1129 sd_iterator_def sd_it;
1131 haifa_change_pattern (insn, ORIG_PAT (insn));
1132 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
1133 DEP_STATUS (dep) &= ~DEP_CANCELLED;
1134 TODO_SPEC (insn) = HARD_DEP;
1135 if (sched_verbose >= 2)
1136 fprintf (sched_dump,
1137 ";;\t\tdequeue insn %s because of clobbered condition\n",
1138 (*current_sched_info->print_insn) (insn, 0));
1145 /* This function should be called after modifying the pattern of INSN,
1146 to update scheduler data structures as needed. */
1148 update_insn_after_change (rtx_insn *insn)
1150 sd_iterator_def sd_it;
1153 dfa_clear_single_insn_cache (insn);
1155 sd_it = sd_iterator_start (insn,
1156 SD_LIST_FORW | SD_LIST_BACK | SD_LIST_RES_BACK);
1157 while (sd_iterator_cond (&sd_it, &dep))
1159 DEP_COST (dep) = UNKNOWN_DEP_COST;
1160 sd_iterator_next (&sd_it);
1163 /* Invalidate INSN_COST, so it'll be recalculated. */
1164 INSN_COST (insn) = -1;
1165 /* Invalidate INSN_TICK, so it'll be recalculated. */
1166 INSN_TICK (insn) = INVALID_TICK;
1168 /* Invalidate autoprefetch data entry. */
1169 INSN_AUTOPREF_MULTIPASS_DATA (insn)[0].status
1170 = AUTOPREF_MULTIPASS_DATA_UNINITIALIZED;
1171 INSN_AUTOPREF_MULTIPASS_DATA (insn)[1].status
1172 = AUTOPREF_MULTIPASS_DATA_UNINITIALIZED;
1176 /* Two VECs, one to hold dependencies for which pattern replacements
1177 need to be applied or restored at the start of the next cycle, and
1178 another to hold an integer that is either one, to apply the
1179 corresponding replacement, or zero to restore it. */
1180 static vec<dep_t> next_cycle_replace_deps;
1181 static vec<int> next_cycle_apply;
1183 static void apply_replacement (dep_t, bool);
1184 static void restore_pattern (dep_t, bool);
1186 /* Look at the remaining dependencies for insn NEXT, and compute and return
1187 the TODO_SPEC value we should use for it. This is called after one of
1188 NEXT's dependencies has been resolved.
1189 We also perform pattern replacements for predication, and for broken
1190 replacement dependencies. The latter is only done if FOR_BACKTRACK is
1194 recompute_todo_spec (rtx_insn *next, bool for_backtrack)
1197 sd_iterator_def sd_it;
1198 dep_t dep, modify_dep = NULL;
1202 bool first_p = true;
1204 if (sd_lists_empty_p (next, SD_LIST_BACK))
1205 /* NEXT has all its dependencies resolved. */
1208 if (!sd_lists_empty_p (next, SD_LIST_HARD_BACK))
1211 /* If NEXT is intended to sit adjacent to this instruction, we don't
1212 want to try to break any dependencies. Treat it as a HARD_DEP. */
1213 if (SCHED_GROUP_P (next))
1216 /* Now we've got NEXT with speculative deps only.
1217 1. Look at the deps to see what we have to do.
1218 2. Check if we can do 'todo'. */
1221 FOR_EACH_DEP (next, SD_LIST_BACK, sd_it, dep)
1223 rtx_insn *pro = DEP_PRO (dep);
1224 ds_t ds = DEP_STATUS (dep) & SPECULATIVE;
1226 if (DEBUG_INSN_P (pro) && !DEBUG_INSN_P (next))
1239 new_ds = ds_merge (new_ds, ds);
1241 else if (DEP_TYPE (dep) == REG_DEP_CONTROL)
1243 if (QUEUE_INDEX (pro) != QUEUE_SCHEDULED)
1248 DEP_STATUS (dep) &= ~DEP_CANCELLED;
1250 else if (DEP_REPLACE (dep) != NULL)
1252 if (QUEUE_INDEX (pro) != QUEUE_SCHEDULED)
1257 DEP_STATUS (dep) &= ~DEP_CANCELLED;
1261 if (n_replace > 0 && n_control == 0 && n_spec == 0)
1263 if (!dbg_cnt (sched_breakdep))
1265 FOR_EACH_DEP (next, SD_LIST_BACK, sd_it, dep)
1267 struct dep_replacement *desc = DEP_REPLACE (dep);
1270 if (desc->insn == next && !for_backtrack)
1272 gcc_assert (n_replace == 1);
1273 apply_replacement (dep, true);
1275 DEP_STATUS (dep) |= DEP_CANCELLED;
1281 else if (n_control == 1 && n_replace == 0 && n_spec == 0)
1283 rtx_insn *pro, *other;
1285 rtx cond = NULL_RTX;
1287 rtx_insn *prev = NULL;
1291 if ((current_sched_info->flags & DO_PREDICATION) == 0
1292 || (ORIG_PAT (next) != NULL_RTX
1293 && PREDICATED_PAT (next) == NULL_RTX))
1296 pro = DEP_PRO (modify_dep);
1297 other = real_insn_for_shadow (pro);
1298 if (other != NULL_RTX)
1301 cond = sched_get_reverse_condition_uncached (pro);
1302 regno = REGNO (XEXP (cond, 0));
1304 /* Find the last scheduled insn that modifies the condition register.
1305 We can stop looking once we find the insn we depend on through the
1306 REG_DEP_CONTROL; if the condition register isn't modified after it,
1307 we know that it still has the right value. */
1308 if (QUEUE_INDEX (pro) == QUEUE_SCHEDULED)
1309 FOR_EACH_VEC_ELT_REVERSE (scheduled_insns, i, prev)
1313 find_all_hard_reg_sets (prev, &t, true);
1314 if (TEST_HARD_REG_BIT (t, regno))
1319 if (ORIG_PAT (next) == NULL_RTX)
1321 ORIG_PAT (next) = PATTERN (next);
1323 new_pat = gen_rtx_COND_EXEC (VOIDmode, cond, PATTERN (next));
1324 success = haifa_change_pattern (next, new_pat);
1327 PREDICATED_PAT (next) = new_pat;
1329 else if (PATTERN (next) != PREDICATED_PAT (next))
1331 bool success = haifa_change_pattern (next,
1332 PREDICATED_PAT (next));
1333 gcc_assert (success);
1335 DEP_STATUS (modify_dep) |= DEP_CANCELLED;
1339 if (PREDICATED_PAT (next) != NULL_RTX)
1341 int tick = INSN_TICK (next);
1342 bool success = haifa_change_pattern (next,
1344 INSN_TICK (next) = tick;
1345 gcc_assert (success);
1348 /* We can't handle the case where there are both speculative and control
1349 dependencies, so we return HARD_DEP in such a case. Also fail if
1350 we have speculative dependencies with not enough points, or more than
1351 one control dependency. */
1352 if ((n_spec > 0 && (n_control > 0 || n_replace > 0))
1354 /* Too few points? */
1355 && ds_weak (new_ds) < spec_info->data_weakness_cutoff)
1363 /* Pointer to the last instruction scheduled. */
1364 static rtx_insn *last_scheduled_insn;
1366 /* Pointer to the last nondebug instruction scheduled within the
1367 block, or the prev_head of the scheduling block. Used by
1368 rank_for_schedule, so that insns independent of the last scheduled
1369 insn will be preferred over dependent instructions. */
1370 static rtx_insn *last_nondebug_scheduled_insn;
1372 /* Pointer that iterates through the list of unscheduled insns if we
1373 have a dbg_cnt enabled. It always points at an insn prior to the
1374 first unscheduled one. */
1375 static rtx_insn *nonscheduled_insns_begin;
1377 /* Compute cost of executing INSN.
1378 This is the number of cycles between instruction issue and
1379 instruction results. */
1381 insn_cost (rtx_insn *insn)
1390 if (recog_memoized (insn) < 0)
1393 cost = insn_default_latency (insn);
1400 cost = INSN_COST (insn);
1404 /* A USE insn, or something else we don't need to
1405 understand. We can't pass these directly to
1406 result_ready_cost or insn_default_latency because it will
1407 trigger a fatal error for unrecognizable insns. */
1408 if (recog_memoized (insn) < 0)
1410 INSN_COST (insn) = 0;
1415 cost = insn_default_latency (insn);
1419 INSN_COST (insn) = cost;
1426 /* Compute cost of dependence LINK.
1427 This is the number of cycles between instruction issue and
1428 instruction results.
1429 ??? We also use this function to call recog_memoized on all insns. */
1431 dep_cost_1 (dep_t link, dw_t dw)
1433 rtx_insn *insn = DEP_PRO (link);
1434 rtx_insn *used = DEP_CON (link);
1437 if (DEP_COST (link) != UNKNOWN_DEP_COST)
1438 return DEP_COST (link);
1442 struct delay_pair *delay_entry;
1444 = delay_htab_i2->find_with_hash (used, htab_hash_pointer (used));
1447 if (delay_entry->i1 == insn)
1449 DEP_COST (link) = pair_delay (delay_entry);
1450 return DEP_COST (link);
1455 /* A USE insn should never require the value used to be computed.
1456 This allows the computation of a function's result and parameter
1457 values to overlap the return and call. We don't care about the
1458 dependence cost when only decreasing register pressure. */
1459 if (recog_memoized (used) < 0)
1462 recog_memoized (insn);
1466 enum reg_note dep_type = DEP_TYPE (link);
1468 cost = insn_cost (insn);
1470 if (INSN_CODE (insn) >= 0)
1472 if (dep_type == REG_DEP_ANTI)
1474 else if (dep_type == REG_DEP_OUTPUT)
1476 cost = (insn_default_latency (insn)
1477 - insn_default_latency (used));
1481 else if (bypass_p (insn))
1482 cost = insn_latency (insn, used);
1486 if (targetm.sched.adjust_cost_2)
1487 cost = targetm.sched.adjust_cost_2 (used, (int) dep_type, insn, cost,
1489 else if (targetm.sched.adjust_cost != NULL)
1491 /* This variable is used for backward compatibility with the
1493 rtx_insn_list *dep_cost_rtx_link =
1494 alloc_INSN_LIST (NULL_RTX, NULL);
1496 /* Make it self-cycled, so that if some tries to walk over this
1497 incomplete list he/she will be caught in an endless loop. */
1498 XEXP (dep_cost_rtx_link, 1) = dep_cost_rtx_link;
1500 /* Targets use only REG_NOTE_KIND of the link. */
1501 PUT_REG_NOTE_KIND (dep_cost_rtx_link, DEP_TYPE (link));
1503 cost = targetm.sched.adjust_cost (used, dep_cost_rtx_link,
1506 free_INSN_LIST_node (dep_cost_rtx_link);
1513 DEP_COST (link) = cost;
1517 /* Compute cost of dependence LINK.
1518 This is the number of cycles between instruction issue and
1519 instruction results. */
1521 dep_cost (dep_t link)
1523 return dep_cost_1 (link, 0);
1526 /* Use this sel-sched.c friendly function in reorder2 instead of increasing
1527 INSN_PRIORITY explicitly. */
1529 increase_insn_priority (rtx_insn *insn, int amount)
1531 if (!sel_sched_p ())
1533 /* We're dealing with haifa-sched.c INSN_PRIORITY. */
1534 if (INSN_PRIORITY_KNOWN (insn))
1535 INSN_PRIORITY (insn) += amount;
1539 /* In sel-sched.c INSN_PRIORITY is not kept up to date.
1540 Use EXPR_PRIORITY instead. */
1541 sel_add_to_insn_priority (insn, amount);
1545 /* Return 'true' if DEP should be included in priority calculations. */
1547 contributes_to_priority_p (dep_t dep)
1549 if (DEBUG_INSN_P (DEP_CON (dep))
1550 || DEBUG_INSN_P (DEP_PRO (dep)))
1553 /* Critical path is meaningful in block boundaries only. */
1554 if (!current_sched_info->contributes_to_priority (DEP_CON (dep),
1558 if (DEP_REPLACE (dep) != NULL)
1561 /* If flag COUNT_SPEC_IN_CRITICAL_PATH is set,
1562 then speculative instructions will less likely be
1563 scheduled. That is because the priority of
1564 their producers will increase, and, thus, the
1565 producers will more likely be scheduled, thus,
1566 resolving the dependence. */
1567 if (sched_deps_info->generate_spec_deps
1568 && !(spec_info->flags & COUNT_SPEC_IN_CRITICAL_PATH)
1569 && (DEP_STATUS (dep) & SPECULATIVE))
1575 /* Compute the number of nondebug deps in list LIST for INSN. */
1578 dep_list_size (rtx_insn *insn, sd_list_types_def list)
1580 sd_iterator_def sd_it;
1582 int dbgcount = 0, nodbgcount = 0;
1584 if (!MAY_HAVE_DEBUG_INSNS)
1585 return sd_lists_size (insn, list);
1587 FOR_EACH_DEP (insn, list, sd_it, dep)
1589 if (DEBUG_INSN_P (DEP_CON (dep)))
1591 else if (!DEBUG_INSN_P (DEP_PRO (dep)))
1595 gcc_assert (dbgcount + nodbgcount == sd_lists_size (insn, list));
1602 /* Compute the priority number for INSN. */
1604 priority (rtx_insn *insn)
1606 if (! INSN_P (insn))
1609 /* We should not be interested in priority of an already scheduled insn. */
1610 gcc_assert (QUEUE_INDEX (insn) != QUEUE_SCHEDULED);
1612 if (!INSN_PRIORITY_KNOWN (insn))
1614 int this_priority = -1;
1618 int this_fusion_priority;
1620 targetm.sched.fusion_priority (insn, FUSION_MAX_PRIORITY,
1621 &this_fusion_priority, &this_priority);
1622 INSN_FUSION_PRIORITY (insn) = this_fusion_priority;
1624 else if (dep_list_size (insn, SD_LIST_FORW) == 0)
1625 /* ??? We should set INSN_PRIORITY to insn_cost when and insn has
1626 some forward deps but all of them are ignored by
1627 contributes_to_priority hook. At the moment we set priority of
1629 this_priority = insn_cost (insn);
1632 rtx_insn *prev_first, *twin;
1635 /* For recovery check instructions we calculate priority slightly
1636 different than that of normal instructions. Instead of walking
1637 through INSN_FORW_DEPS (check) list, we walk through
1638 INSN_FORW_DEPS list of each instruction in the corresponding
1641 /* Selective scheduling does not define RECOVERY_BLOCK macro. */
1642 rec = sel_sched_p () ? NULL : RECOVERY_BLOCK (insn);
1643 if (!rec || rec == EXIT_BLOCK_PTR_FOR_FN (cfun))
1645 prev_first = PREV_INSN (insn);
1650 prev_first = NEXT_INSN (BB_HEAD (rec));
1651 twin = PREV_INSN (BB_END (rec));
1656 sd_iterator_def sd_it;
1659 FOR_EACH_DEP (twin, SD_LIST_FORW, sd_it, dep)
1664 next = DEP_CON (dep);
1666 if (BLOCK_FOR_INSN (next) != rec)
1670 if (!contributes_to_priority_p (dep))
1674 cost = dep_cost (dep);
1677 struct _dep _dep1, *dep1 = &_dep1;
1679 init_dep (dep1, insn, next, REG_DEP_ANTI);
1681 cost = dep_cost (dep1);
1684 next_priority = cost + priority (next);
1686 if (next_priority > this_priority)
1687 this_priority = next_priority;
1691 twin = PREV_INSN (twin);
1693 while (twin != prev_first);
1696 if (this_priority < 0)
1698 gcc_assert (this_priority == -1);
1700 this_priority = insn_cost (insn);
1703 INSN_PRIORITY (insn) = this_priority;
1704 INSN_PRIORITY_STATUS (insn) = 1;
1707 return INSN_PRIORITY (insn);
1710 /* Macros and functions for keeping the priority queue sorted, and
1711 dealing with queuing and dequeuing of instructions. */
1713 /* For each pressure class CL, set DEATH[CL] to the number of registers
1714 in that class that die in INSN. */
1717 calculate_reg_deaths (rtx_insn *insn, int *death)
1720 struct reg_use_data *use;
1722 for (i = 0; i < ira_pressure_classes_num; i++)
1723 death[ira_pressure_classes[i]] = 0;
1724 for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
1725 if (dying_use_p (use))
1726 mark_regno_birth_or_death (0, death, use->regno, true);
1729 /* Setup info about the current register pressure impact of scheduling
1730 INSN at the current scheduling point. */
1732 setup_insn_reg_pressure_info (rtx_insn *insn)
1734 int i, change, before, after, hard_regno;
1735 int excess_cost_change;
1738 struct reg_pressure_data *pressure_info;
1739 int *max_reg_pressure;
1740 static int death[N_REG_CLASSES];
1742 gcc_checking_assert (!DEBUG_INSN_P (insn));
1744 excess_cost_change = 0;
1745 calculate_reg_deaths (insn, death);
1746 pressure_info = INSN_REG_PRESSURE (insn);
1747 max_reg_pressure = INSN_MAX_REG_PRESSURE (insn);
1748 gcc_assert (pressure_info != NULL && max_reg_pressure != NULL);
1749 for (i = 0; i < ira_pressure_classes_num; i++)
1751 cl = ira_pressure_classes[i];
1752 gcc_assert (curr_reg_pressure[cl] >= 0);
1753 change = (int) pressure_info[i].set_increase - death[cl];
1754 before = MAX (0, max_reg_pressure[i] - sched_class_regs_num[cl]);
1755 after = MAX (0, max_reg_pressure[i] + change
1756 - sched_class_regs_num[cl]);
1757 hard_regno = ira_class_hard_regs[cl][0];
1758 gcc_assert (hard_regno >= 0);
1759 mode = reg_raw_mode[hard_regno];
1760 excess_cost_change += ((after - before)
1761 * (ira_memory_move_cost[mode][cl][0]
1762 + ira_memory_move_cost[mode][cl][1]));
1764 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insn) = excess_cost_change;
1767 /* This is the first page of code related to SCHED_PRESSURE_MODEL.
1768 It tries to make the scheduler take register pressure into account
1769 without introducing too many unnecessary stalls. It hooks into the
1770 main scheduling algorithm at several points:
1772 - Before scheduling starts, model_start_schedule constructs a
1773 "model schedule" for the current block. This model schedule is
1774 chosen solely to keep register pressure down. It does not take the
1775 target's pipeline or the original instruction order into account,
1776 except as a tie-breaker. It also doesn't work to a particular
1779 This model schedule gives us an idea of what pressure can be
1780 achieved for the block and gives us an example of a schedule that
1781 keeps to that pressure. It also makes the final schedule less
1782 dependent on the original instruction order. This is important
1783 because the original order can either be "wide" (many values live
1784 at once, such as in user-scheduled code) or "narrow" (few values
1785 live at once, such as after loop unrolling, where several
1786 iterations are executed sequentially).
1788 We do not apply this model schedule to the rtx stream. We simply
1789 record it in model_schedule. We also compute the maximum pressure,
1790 MP, that was seen during this schedule.
1792 - Instructions are added to the ready queue even if they require
1793 a stall. The length of the stall is instead computed as:
1795 MAX (INSN_TICK (INSN) - clock_var, 0)
1797 (= insn_delay). This allows rank_for_schedule to choose between
1798 introducing a deliberate stall or increasing pressure.
1800 - Before sorting the ready queue, model_set_excess_costs assigns
1801 a pressure-based cost to each ready instruction in the queue.
1802 This is the instruction's INSN_REG_PRESSURE_EXCESS_COST_CHANGE
1803 (ECC for short) and is effectively measured in cycles.
1805 - rank_for_schedule ranks instructions based on:
1807 ECC (insn) + insn_delay (insn)
1813 So, for example, an instruction X1 with an ECC of 1 that can issue
1814 now will win over an instruction X0 with an ECC of zero that would
1815 introduce a stall of one cycle. However, an instruction X2 with an
1816 ECC of 2 that can issue now will lose to both X0 and X1.
1818 - When an instruction is scheduled, model_recompute updates the model
1819 schedule with the new pressures (some of which might now exceed the
1820 original maximum pressure MP). model_update_limit_points then searches
1821 for the new point of maximum pressure, if not already known. */
1823 /* Used to separate high-verbosity debug information for SCHED_PRESSURE_MODEL
1824 from surrounding debug information. */
1826 ";;\t\t+------------------------------------------------------\n"
1828 /* Information about the pressure on a particular register class at a
1829 particular point of the model schedule. */
1830 struct model_pressure_data {
1831 /* The pressure at this point of the model schedule, or -1 if the
1832 point is associated with an instruction that has already been
1836 /* The maximum pressure during or after this point of the model schedule. */
1840 /* Per-instruction information that is used while building the model
1841 schedule. Here, "schedule" refers to the model schedule rather
1842 than the main schedule. */
1843 struct model_insn_info {
1844 /* The instruction itself. */
1847 /* If this instruction is in model_worklist, these fields link to the
1848 previous (higher-priority) and next (lower-priority) instructions
1850 struct model_insn_info *prev;
1851 struct model_insn_info *next;
1853 /* While constructing the schedule, QUEUE_INDEX describes whether an
1854 instruction has already been added to the schedule (QUEUE_SCHEDULED),
1855 is in model_worklist (QUEUE_READY), or neither (QUEUE_NOWHERE).
1856 old_queue records the value that QUEUE_INDEX had before scheduling
1857 started, so that we can restore it once the schedule is complete. */
1860 /* The relative importance of an unscheduled instruction. Higher
1861 values indicate greater importance. */
1862 unsigned int model_priority;
1864 /* The length of the longest path of satisfied true dependencies
1865 that leads to this instruction. */
1868 /* The length of the longest path of dependencies of any kind
1869 that leads from this instruction. */
1872 /* The number of predecessor nodes that must still be scheduled. */
1873 int unscheduled_preds;
1876 /* Information about the pressure limit for a particular register class.
1877 This structure is used when applying a model schedule to the main
1879 struct model_pressure_limit {
1880 /* The maximum register pressure seen in the original model schedule. */
1883 /* The maximum register pressure seen in the current model schedule
1884 (which excludes instructions that have already been scheduled). */
1887 /* The point of the current model schedule at which PRESSURE is first
1888 reached. It is set to -1 if the value needs to be recomputed. */
1892 /* Describes a particular way of measuring register pressure. */
1893 struct model_pressure_group {
1894 /* Index PCI describes the maximum pressure on ira_pressure_classes[PCI]. */
1895 struct model_pressure_limit limits[N_REG_CLASSES];
1897 /* Index (POINT * ira_num_pressure_classes + PCI) describes the pressure
1898 on register class ira_pressure_classes[PCI] at point POINT of the
1899 current model schedule. A POINT of model_num_insns describes the
1900 pressure at the end of the schedule. */
1901 struct model_pressure_data *model;
1904 /* Index POINT gives the instruction at point POINT of the model schedule.
1905 This array doesn't change during main scheduling. */
1906 static vec<rtx_insn *> model_schedule;
1908 /* The list of instructions in the model worklist, sorted in order of
1909 decreasing priority. */
1910 static struct model_insn_info *model_worklist;
1912 /* Index I describes the instruction with INSN_LUID I. */
1913 static struct model_insn_info *model_insns;
1915 /* The number of instructions in the model schedule. */
1916 static int model_num_insns;
1918 /* The index of the first instruction in model_schedule that hasn't yet been
1919 added to the main schedule, or model_num_insns if all of them have. */
1920 static int model_curr_point;
1922 /* Describes the pressure before each instruction in the model schedule. */
1923 static struct model_pressure_group model_before_pressure;
1925 /* The first unused model_priority value (as used in model_insn_info). */
1926 static unsigned int model_next_priority;
1929 /* The model_pressure_data for ira_pressure_classes[PCI] in GROUP
1930 at point POINT of the model schedule. */
1931 #define MODEL_PRESSURE_DATA(GROUP, POINT, PCI) \
1932 (&(GROUP)->model[(POINT) * ira_pressure_classes_num + (PCI)])
1934 /* The maximum pressure on ira_pressure_classes[PCI] in GROUP at or
1935 after point POINT of the model schedule. */
1936 #define MODEL_MAX_PRESSURE(GROUP, POINT, PCI) \
1937 (MODEL_PRESSURE_DATA (GROUP, POINT, PCI)->max_pressure)
1939 /* The pressure on ira_pressure_classes[PCI] in GROUP at point POINT
1940 of the model schedule. */
1941 #define MODEL_REF_PRESSURE(GROUP, POINT, PCI) \
1942 (MODEL_PRESSURE_DATA (GROUP, POINT, PCI)->ref_pressure)
1944 /* Information about INSN that is used when creating the model schedule. */
1945 #define MODEL_INSN_INFO(INSN) \
1946 (&model_insns[INSN_LUID (INSN)])
1948 /* The instruction at point POINT of the model schedule. */
1949 #define MODEL_INSN(POINT) \
1950 (model_schedule[POINT])
1953 /* Return INSN's index in the model schedule, or model_num_insns if it
1954 doesn't belong to that schedule. */
1957 model_index (rtx_insn *insn)
1959 if (INSN_MODEL_INDEX (insn) == 0)
1960 return model_num_insns;
1961 return INSN_MODEL_INDEX (insn) - 1;
1964 /* Make sure that GROUP->limits is up-to-date for the current point
1965 of the model schedule. */
1968 model_update_limit_points_in_group (struct model_pressure_group *group)
1970 int pci, max_pressure, point;
1972 for (pci = 0; pci < ira_pressure_classes_num; pci++)
1974 /* We may have passed the final point at which the pressure in
1975 group->limits[pci].pressure was reached. Update the limit if so. */
1976 max_pressure = MODEL_MAX_PRESSURE (group, model_curr_point, pci);
1977 group->limits[pci].pressure = max_pressure;
1979 /* Find the point at which MAX_PRESSURE is first reached. We need
1980 to search in three cases:
1982 - We've already moved past the previous pressure point.
1983 In this case we search forward from model_curr_point.
1985 - We scheduled the previous point of maximum pressure ahead of
1986 its position in the model schedule, but doing so didn't bring
1987 the pressure point earlier. In this case we search forward
1988 from that previous pressure point.
1990 - Scheduling an instruction early caused the maximum pressure
1991 to decrease. In this case we will have set the pressure
1992 point to -1, and we search forward from model_curr_point. */
1993 point = MAX (group->limits[pci].point, model_curr_point);
1994 while (point < model_num_insns
1995 && MODEL_REF_PRESSURE (group, point, pci) < max_pressure)
1997 group->limits[pci].point = point;
1999 gcc_assert (MODEL_REF_PRESSURE (group, point, pci) == max_pressure);
2000 gcc_assert (MODEL_MAX_PRESSURE (group, point, pci) == max_pressure);
2004 /* Make sure that all register-pressure limits are up-to-date for the
2005 current position in the model schedule. */
2008 model_update_limit_points (void)
2010 model_update_limit_points_in_group (&model_before_pressure);
2013 /* Return the model_index of the last unscheduled use in chain USE
2014 outside of USE's instruction. Return -1 if there are no other uses,
2015 or model_num_insns if the register is live at the end of the block. */
2018 model_last_use_except (struct reg_use_data *use)
2020 struct reg_use_data *next;
2024 for (next = use->next_regno_use; next != use; next = next->next_regno_use)
2025 if (NONDEBUG_INSN_P (next->insn)
2026 && QUEUE_INDEX (next->insn) != QUEUE_SCHEDULED)
2028 index = model_index (next->insn);
2029 if (index == model_num_insns)
2030 return model_num_insns;
2037 /* An instruction with model_index POINT has just been scheduled, and it
2038 adds DELTA to the pressure on ira_pressure_classes[PCI] after POINT - 1.
2039 Update MODEL_REF_PRESSURE (GROUP, POINT, PCI) and
2040 MODEL_MAX_PRESSURE (GROUP, POINT, PCI) accordingly. */
2043 model_start_update_pressure (struct model_pressure_group *group,
2044 int point, int pci, int delta)
2046 int next_max_pressure;
2048 if (point == model_num_insns)
2050 /* The instruction wasn't part of the model schedule; it was moved
2051 from a different block. Update the pressure for the end of
2052 the model schedule. */
2053 MODEL_REF_PRESSURE (group, point, pci) += delta;
2054 MODEL_MAX_PRESSURE (group, point, pci) += delta;
2058 /* Record that this instruction has been scheduled. Nothing now
2059 changes between POINT and POINT + 1, so get the maximum pressure
2060 from the latter. If the maximum pressure decreases, the new
2061 pressure point may be before POINT. */
2062 MODEL_REF_PRESSURE (group, point, pci) = -1;
2063 next_max_pressure = MODEL_MAX_PRESSURE (group, point + 1, pci);
2064 if (MODEL_MAX_PRESSURE (group, point, pci) > next_max_pressure)
2066 MODEL_MAX_PRESSURE (group, point, pci) = next_max_pressure;
2067 if (group->limits[pci].point == point)
2068 group->limits[pci].point = -1;
2073 /* Record that scheduling a later instruction has changed the pressure
2074 at point POINT of the model schedule by DELTA (which might be 0).
2075 Update GROUP accordingly. Return nonzero if these changes might
2076 trigger changes to previous points as well. */
2079 model_update_pressure (struct model_pressure_group *group,
2080 int point, int pci, int delta)
2082 int ref_pressure, max_pressure, next_max_pressure;
2084 /* If POINT hasn't yet been scheduled, update its pressure. */
2085 ref_pressure = MODEL_REF_PRESSURE (group, point, pci);
2086 if (ref_pressure >= 0 && delta != 0)
2088 ref_pressure += delta;
2089 MODEL_REF_PRESSURE (group, point, pci) = ref_pressure;
2091 /* Check whether the maximum pressure in the overall schedule
2092 has increased. (This means that the MODEL_MAX_PRESSURE of
2093 every point <= POINT will need to increase too; see below.) */
2094 if (group->limits[pci].pressure < ref_pressure)
2095 group->limits[pci].pressure = ref_pressure;
2097 /* If we are at maximum pressure, and the maximum pressure
2098 point was previously unknown or later than POINT,
2099 bring it forward. */
2100 if (group->limits[pci].pressure == ref_pressure
2101 && !IN_RANGE (group->limits[pci].point, 0, point))
2102 group->limits[pci].point = point;
2104 /* If POINT used to be the point of maximum pressure, but isn't
2105 any longer, we need to recalculate it using a forward walk. */
2106 if (group->limits[pci].pressure > ref_pressure
2107 && group->limits[pci].point == point)
2108 group->limits[pci].point = -1;
2111 /* Update the maximum pressure at POINT. Changes here might also
2112 affect the maximum pressure at POINT - 1. */
2113 next_max_pressure = MODEL_MAX_PRESSURE (group, point + 1, pci);
2114 max_pressure = MAX (ref_pressure, next_max_pressure);
2115 if (MODEL_MAX_PRESSURE (group, point, pci) != max_pressure)
2117 MODEL_MAX_PRESSURE (group, point, pci) = max_pressure;
2123 /* INSN has just been scheduled. Update the model schedule accordingly. */
2126 model_recompute (rtx_insn *insn)
2131 } uses[FIRST_PSEUDO_REGISTER + MAX_RECOG_OPERANDS];
2132 struct reg_use_data *use;
2133 struct reg_pressure_data *reg_pressure;
2134 int delta[N_REG_CLASSES];
2135 int pci, point, mix, new_last, cl, ref_pressure, queue;
2136 unsigned int i, num_uses, num_pending_births;
2139 /* The destinations of INSN were previously live from POINT onwards, but are
2140 now live from model_curr_point onwards. Set up DELTA accordingly. */
2141 point = model_index (insn);
2142 reg_pressure = INSN_REG_PRESSURE (insn);
2143 for (pci = 0; pci < ira_pressure_classes_num; pci++)
2145 cl = ira_pressure_classes[pci];
2146 delta[cl] = reg_pressure[pci].set_increase;
2149 /* Record which registers previously died at POINT, but which now die
2150 before POINT. Adjust DELTA so that it represents the effect of
2151 this change after POINT - 1. Set NUM_PENDING_BIRTHS to the number of
2152 registers that will be born in the range [model_curr_point, POINT). */
2154 num_pending_births = 0;
2155 for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
2157 new_last = model_last_use_except (use);
2158 if (new_last < point)
2160 gcc_assert (num_uses < ARRAY_SIZE (uses));
2161 uses[num_uses].last_use = new_last;
2162 uses[num_uses].regno = use->regno;
2163 /* This register is no longer live after POINT - 1. */
2164 mark_regno_birth_or_death (NULL, delta, use->regno, false);
2167 num_pending_births++;
2171 /* Update the MODEL_REF_PRESSURE and MODEL_MAX_PRESSURE for POINT.
2172 Also set each group pressure limit for POINT. */
2173 for (pci = 0; pci < ira_pressure_classes_num; pci++)
2175 cl = ira_pressure_classes[pci];
2176 model_start_update_pressure (&model_before_pressure,
2177 point, pci, delta[cl]);
2180 /* Walk the model schedule backwards, starting immediately before POINT. */
2182 if (point != model_curr_point)
2186 insn = MODEL_INSN (point);
2187 queue = QUEUE_INDEX (insn);
2189 if (queue != QUEUE_SCHEDULED)
2191 /* DELTA describes the effect of the move on the register pressure
2192 after POINT. Make it describe the effect on the pressure
2195 while (i < num_uses)
2197 if (uses[i].last_use == point)
2199 /* This register is now live again. */
2200 mark_regno_birth_or_death (NULL, delta,
2201 uses[i].regno, true);
2203 /* Remove this use from the array. */
2204 uses[i] = uses[num_uses - 1];
2206 num_pending_births--;
2212 if (sched_verbose >= 5)
2216 fprintf (sched_dump, MODEL_BAR);
2217 fprintf (sched_dump, ";;\t\t| New pressure for model"
2219 fprintf (sched_dump, MODEL_BAR);
2223 fprintf (sched_dump, ";;\t\t| %3d %4d %-30s ",
2224 point, INSN_UID (insn),
2225 str_pattern_slim (PATTERN (insn)));
2226 for (pci = 0; pci < ira_pressure_classes_num; pci++)
2228 cl = ira_pressure_classes[pci];
2229 ref_pressure = MODEL_REF_PRESSURE (&model_before_pressure,
2231 fprintf (sched_dump, " %s:[%d->%d]",
2232 reg_class_names[ira_pressure_classes[pci]],
2233 ref_pressure, ref_pressure + delta[cl]);
2235 fprintf (sched_dump, "\n");
2239 /* Adjust the pressure at POINT. Set MIX to nonzero if POINT - 1
2240 might have changed as well. */
2241 mix = num_pending_births;
2242 for (pci = 0; pci < ira_pressure_classes_num; pci++)
2244 cl = ira_pressure_classes[pci];
2246 mix |= model_update_pressure (&model_before_pressure,
2247 point, pci, delta[cl]);
2250 while (mix && point > model_curr_point);
2253 fprintf (sched_dump, MODEL_BAR);
2256 /* After DEP, which was cancelled, has been resolved for insn NEXT,
2257 check whether the insn's pattern needs restoring. */
2259 must_restore_pattern_p (rtx_insn *next, dep_t dep)
2261 if (QUEUE_INDEX (next) == QUEUE_SCHEDULED)
2264 if (DEP_TYPE (dep) == REG_DEP_CONTROL)
2266 gcc_assert (ORIG_PAT (next) != NULL_RTX);
2267 gcc_assert (next == DEP_CON (dep));
2271 struct dep_replacement *desc = DEP_REPLACE (dep);
2272 if (desc->insn != next)
2274 gcc_assert (*desc->loc == desc->orig);
2281 /* model_spill_cost (CL, P, P') returns the cost of increasing the
2282 pressure on CL from P to P'. We use this to calculate a "base ECC",
2283 baseECC (CL, X), for each pressure class CL and each instruction X.
2284 Supposing X changes the pressure on CL from P to P', and that the
2285 maximum pressure on CL in the current model schedule is MP', then:
2287 * if X occurs before or at the next point of maximum pressure in
2288 the model schedule and P' > MP', then:
2290 baseECC (CL, X) = model_spill_cost (CL, MP, P')
2292 The idea is that the pressure after scheduling a fixed set of
2293 instructions -- in this case, the set up to and including the
2294 next maximum pressure point -- is going to be the same regardless
2295 of the order; we simply want to keep the intermediate pressure
2296 under control. Thus X has a cost of zero unless scheduling it
2297 now would exceed MP'.
2299 If all increases in the set are by the same amount, no zero-cost
2300 instruction will ever cause the pressure to exceed MP'. However,
2301 if X is instead moved past an instruction X' with pressure in the
2302 range (MP' - (P' - P), MP'), the pressure at X' will increase
2303 beyond MP'. Since baseECC is very much a heuristic anyway,
2304 it doesn't seem worth the overhead of tracking cases like these.
2306 The cost of exceeding MP' is always based on the original maximum
2307 pressure MP. This is so that going 2 registers over the original
2308 limit has the same cost regardless of whether it comes from two
2309 separate +1 deltas or from a single +2 delta.
2311 * if X occurs after the next point of maximum pressure in the model
2312 schedule and P' > P, then:
2314 baseECC (CL, X) = model_spill_cost (CL, MP, MP' + (P' - P))
2316 That is, if we move X forward across a point of maximum pressure,
2317 and if X increases the pressure by P' - P, then we conservatively
2318 assume that scheduling X next would increase the maximum pressure
2319 by P' - P. Again, the cost of doing this is based on the original
2320 maximum pressure MP, for the same reason as above.
2322 * if P' < P, P > MP, and X occurs at or after the next point of
2323 maximum pressure, then:
2325 baseECC (CL, X) = -model_spill_cost (CL, MAX (MP, P'), P)
2327 That is, if we have already exceeded the original maximum pressure MP,
2328 and if X might reduce the maximum pressure again -- or at least push
2329 it further back, and thus allow more scheduling freedom -- it is given
2330 a negative cost to reflect the improvement.
2336 In this case, X is not expected to affect the maximum pressure MP',
2337 so it has zero cost.
2339 We then create a combined value baseECC (X) that is the sum of
2340 baseECC (CL, X) for each pressure class CL.
2342 baseECC (X) could itself be used as the ECC value described above.
2343 However, this is often too conservative, in the sense that it
2344 tends to make high-priority instructions that increase pressure
2345 wait too long in cases where introducing a spill would be better.
2346 For this reason the final ECC is a priority-adjusted form of
2347 baseECC (X). Specifically, we calculate:
2349 P (X) = INSN_PRIORITY (X) - insn_delay (X) - baseECC (X)
2350 baseP = MAX { P (X) | baseECC (X) <= 0 }
2354 ECC (X) = MAX (MIN (baseP - P (X), baseECC (X)), 0)
2356 Thus an instruction's effect on pressure is ignored if it has a high
2357 enough priority relative to the ones that don't increase pressure.
2358 Negative values of baseECC (X) do not increase the priority of X
2359 itself, but they do make it harder for other instructions to
2360 increase the pressure further.
2362 This pressure cost is deliberately timid. The intention has been
2363 to choose a heuristic that rarely interferes with the normal list
2364 scheduler in cases where that scheduler would produce good code.
2365 We simply want to curb some of its worst excesses. */
2367 /* Return the cost of increasing the pressure in class CL from FROM to TO.
2369 Here we use the very simplistic cost model that every register above
2370 sched_class_regs_num[CL] has a spill cost of 1. We could use other
2371 measures instead, such as one based on MEMORY_MOVE_COST. However:
2373 (1) In order for an instruction to be scheduled, the higher cost
2374 would need to be justified in a single saving of that many stalls.
2375 This is overly pessimistic, because the benefit of spilling is
2376 often to avoid a sequence of several short stalls rather than
2379 (2) The cost is still arbitrary. Because we are not allocating
2380 registers during scheduling, we have no way of knowing for
2381 sure how many memory accesses will be required by each spill,
2382 where the spills will be placed within the block, or even
2383 which block(s) will contain the spills.
2385 So a higher cost than 1 is often too conservative in practice,
2386 forcing blocks to contain unnecessary stalls instead of spill code.
2387 The simple cost below seems to be the best compromise. It reduces
2388 the interference with the normal list scheduler, which helps make
2389 it more suitable for a default-on option. */
2392 model_spill_cost (int cl, int from, int to)
2394 from = MAX (from, sched_class_regs_num[cl]);
2395 return MAX (to, from) - from;
2398 /* Return baseECC (ira_pressure_classes[PCI], POINT), given that
2399 P = curr_reg_pressure[ira_pressure_classes[PCI]] and that
2403 model_excess_group_cost (struct model_pressure_group *group,
2404 int point, int pci, int delta)
2408 cl = ira_pressure_classes[pci];
2409 if (delta < 0 && point >= group->limits[pci].point)
2411 pressure = MAX (group->limits[pci].orig_pressure,
2412 curr_reg_pressure[cl] + delta);
2413 return -model_spill_cost (cl, pressure, curr_reg_pressure[cl]);
2418 if (point > group->limits[pci].point)
2419 pressure = group->limits[pci].pressure + delta;
2421 pressure = curr_reg_pressure[cl] + delta;
2423 if (pressure > group->limits[pci].pressure)
2424 return model_spill_cost (cl, group->limits[pci].orig_pressure,
2431 /* Return baseECC (MODEL_INSN (INSN)). Dump the costs to sched_dump
2435 model_excess_cost (rtx_insn *insn, bool print_p)
2437 int point, pci, cl, cost, this_cost, delta;
2438 struct reg_pressure_data *insn_reg_pressure;
2439 int insn_death[N_REG_CLASSES];
2441 calculate_reg_deaths (insn, insn_death);
2442 point = model_index (insn);
2443 insn_reg_pressure = INSN_REG_PRESSURE (insn);
2447 fprintf (sched_dump, ";;\t\t| %3d %4d | %4d %+3d |", point,
2448 INSN_UID (insn), INSN_PRIORITY (insn), insn_delay (insn));
2450 /* Sum up the individual costs for each register class. */
2451 for (pci = 0; pci < ira_pressure_classes_num; pci++)
2453 cl = ira_pressure_classes[pci];
2454 delta = insn_reg_pressure[pci].set_increase - insn_death[cl];
2455 this_cost = model_excess_group_cost (&model_before_pressure,
2459 fprintf (sched_dump, " %s:[%d base cost %d]",
2460 reg_class_names[cl], delta, this_cost);
2464 fprintf (sched_dump, "\n");
2469 /* Dump the next points of maximum pressure for GROUP. */
2472 model_dump_pressure_points (struct model_pressure_group *group)
2476 fprintf (sched_dump, ";;\t\t| pressure points");
2477 for (pci = 0; pci < ira_pressure_classes_num; pci++)
2479 cl = ira_pressure_classes[pci];
2480 fprintf (sched_dump, " %s:[%d->%d at ", reg_class_names[cl],
2481 curr_reg_pressure[cl], group->limits[pci].pressure);
2482 if (group->limits[pci].point < model_num_insns)
2483 fprintf (sched_dump, "%d:%d]", group->limits[pci].point,
2484 INSN_UID (MODEL_INSN (group->limits[pci].point)));
2486 fprintf (sched_dump, "end]");
2488 fprintf (sched_dump, "\n");
2491 /* Set INSN_REG_PRESSURE_EXCESS_COST_CHANGE for INSNS[0...COUNT-1]. */
2494 model_set_excess_costs (rtx_insn **insns, int count)
2496 int i, cost, priority_base, priority;
2499 /* Record the baseECC value for each instruction in the model schedule,
2500 except that negative costs are converted to zero ones now rather than
2501 later. Do not assign a cost to debug instructions, since they must
2502 not change code-generation decisions. Experiments suggest we also
2503 get better results by not assigning a cost to instructions from
2506 Set PRIORITY_BASE to baseP in the block comment above. This is the
2507 maximum priority of the "cheap" instructions, which should always
2508 include the next model instruction. */
2511 for (i = 0; i < count; i++)
2512 if (INSN_MODEL_INDEX (insns[i]))
2514 if (sched_verbose >= 6 && !print_p)
2516 fprintf (sched_dump, MODEL_BAR);
2517 fprintf (sched_dump, ";;\t\t| Pressure costs for ready queue\n");
2518 model_dump_pressure_points (&model_before_pressure);
2519 fprintf (sched_dump, MODEL_BAR);
2522 cost = model_excess_cost (insns[i], print_p);
2525 priority = INSN_PRIORITY (insns[i]) - insn_delay (insns[i]) - cost;
2526 priority_base = MAX (priority_base, priority);
2529 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insns[i]) = cost;
2532 fprintf (sched_dump, MODEL_BAR);
2534 /* Use MAX (baseECC, 0) and baseP to calculcate ECC for each
2536 for (i = 0; i < count; i++)
2538 cost = INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insns[i]);
2539 priority = INSN_PRIORITY (insns[i]) - insn_delay (insns[i]);
2540 if (cost > 0 && priority > priority_base)
2542 cost += priority_base - priority;
2543 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insns[i]) = MAX (cost, 0);
2549 /* Enum of rank_for_schedule heuristic decisions. */
2551 RFS_LIVE_RANGE_SHRINK1, RFS_LIVE_RANGE_SHRINK2,
2552 RFS_SCHED_GROUP, RFS_PRESSURE_DELAY, RFS_PRESSURE_TICK,
2553 RFS_FEEDS_BACKTRACK_INSN, RFS_PRIORITY, RFS_SPECULATION,
2554 RFS_SCHED_RANK, RFS_LAST_INSN, RFS_PRESSURE_INDEX,
2555 RFS_DEP_COUNT, RFS_TIE, RFS_FUSION, RFS_N };
2557 /* Corresponding strings for print outs. */
2558 static const char *rfs_str[RFS_N] = {
2559 "RFS_LIVE_RANGE_SHRINK1", "RFS_LIVE_RANGE_SHRINK2",
2560 "RFS_SCHED_GROUP", "RFS_PRESSURE_DELAY", "RFS_PRESSURE_TICK",
2561 "RFS_FEEDS_BACKTRACK_INSN", "RFS_PRIORITY", "RFS_SPECULATION",
2562 "RFS_SCHED_RANK", "RFS_LAST_INSN", "RFS_PRESSURE_INDEX",
2563 "RFS_DEP_COUNT", "RFS_TIE", "RFS_FUSION" };
2565 /* Statistical breakdown of rank_for_schedule decisions. */
2566 struct rank_for_schedule_stats_t { unsigned stats[RFS_N]; };
2567 static rank_for_schedule_stats_t rank_for_schedule_stats;
2569 /* Return the result of comparing insns TMP and TMP2 and update
2570 Rank_For_Schedule statistics. */
2572 rfs_result (enum rfs_decision decision, int result, rtx tmp, rtx tmp2)
2574 ++rank_for_schedule_stats.stats[decision];
2576 INSN_LAST_RFS_WIN (tmp) = decision;
2577 else if (result > 0)
2578 INSN_LAST_RFS_WIN (tmp2) = decision;
2584 /* Sorting predicate to move DEBUG_INSNs to the top of ready list, while
2585 keeping normal insns in original order. */
2588 rank_for_schedule_debug (const void *x, const void *y)
2590 rtx_insn *tmp = *(rtx_insn * const *) y;
2591 rtx_insn *tmp2 = *(rtx_insn * const *) x;
2593 /* Schedule debug insns as early as possible. */
2594 if (DEBUG_INSN_P (tmp) && !DEBUG_INSN_P (tmp2))
2596 else if (!DEBUG_INSN_P (tmp) && DEBUG_INSN_P (tmp2))
2598 else if (DEBUG_INSN_P (tmp) && DEBUG_INSN_P (tmp2))
2599 return INSN_LUID (tmp) - INSN_LUID (tmp2);
2601 return INSN_RFS_DEBUG_ORIG_ORDER (tmp2) - INSN_RFS_DEBUG_ORIG_ORDER (tmp);
2604 /* Returns a positive value if x is preferred; returns a negative value if
2605 y is preferred. Should never return 0, since that will make the sort
2609 rank_for_schedule (const void *x, const void *y)
2611 rtx_insn *tmp = *(rtx_insn * const *) y;
2612 rtx_insn *tmp2 = *(rtx_insn * const *) x;
2613 int tmp_class, tmp2_class;
2614 int val, priority_val, info_val, diff;
2616 if (live_range_shrinkage_p)
2618 /* Don't use SCHED_PRESSURE_MODEL -- it results in much worse
2620 gcc_assert (sched_pressure == SCHED_PRESSURE_WEIGHTED);
2621 if ((INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp) < 0
2622 || INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp2) < 0)
2623 && (diff = (INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp)
2624 - INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp2))) != 0)
2625 return rfs_result (RFS_LIVE_RANGE_SHRINK1, diff, tmp, tmp2);
2626 /* Sort by INSN_LUID (original insn order), so that we make the
2627 sort stable. This minimizes instruction movement, thus
2628 minimizing sched's effect on debugging and cross-jumping. */
2629 return rfs_result (RFS_LIVE_RANGE_SHRINK2,
2630 INSN_LUID (tmp) - INSN_LUID (tmp2), tmp, tmp2);
2633 /* The insn in a schedule group should be issued the first. */
2634 if (flag_sched_group_heuristic &&
2635 SCHED_GROUP_P (tmp) != SCHED_GROUP_P (tmp2))
2636 return rfs_result (RFS_SCHED_GROUP, SCHED_GROUP_P (tmp2) ? 1 : -1,
2639 /* Make sure that priority of TMP and TMP2 are initialized. */
2640 gcc_assert (INSN_PRIORITY_KNOWN (tmp) && INSN_PRIORITY_KNOWN (tmp2));
2644 /* The instruction that has the same fusion priority as the last
2645 instruction is the instruction we picked next. If that is not
2646 the case, we sort ready list firstly by fusion priority, then
2647 by priority, and at last by INSN_LUID. */
2648 int a = INSN_FUSION_PRIORITY (tmp);
2649 int b = INSN_FUSION_PRIORITY (tmp2);
2652 if (last_nondebug_scheduled_insn
2653 && !NOTE_P (last_nondebug_scheduled_insn)
2654 && BLOCK_FOR_INSN (tmp)
2655 == BLOCK_FOR_INSN (last_nondebug_scheduled_insn))
2656 last = INSN_FUSION_PRIORITY (last_nondebug_scheduled_insn);
2658 if (a != last && b != last)
2662 a = INSN_PRIORITY (tmp);
2663 b = INSN_PRIORITY (tmp2);
2666 return rfs_result (RFS_FUSION, b - a, tmp, tmp2);
2668 return rfs_result (RFS_FUSION,
2669 INSN_LUID (tmp) - INSN_LUID (tmp2), tmp, tmp2);
2673 gcc_assert (last_nondebug_scheduled_insn
2674 && !NOTE_P (last_nondebug_scheduled_insn));
2675 last = INSN_PRIORITY (last_nondebug_scheduled_insn);
2677 a = abs (INSN_PRIORITY (tmp) - last);
2678 b = abs (INSN_PRIORITY (tmp2) - last);
2680 return rfs_result (RFS_FUSION, a - b, tmp, tmp2);
2682 return rfs_result (RFS_FUSION,
2683 INSN_LUID (tmp) - INSN_LUID (tmp2), tmp, tmp2);
2686 return rfs_result (RFS_FUSION, -1, tmp, tmp2);
2688 return rfs_result (RFS_FUSION, 1, tmp, tmp2);
2691 if (sched_pressure != SCHED_PRESSURE_NONE)
2693 /* Prefer insn whose scheduling results in the smallest register
2695 if ((diff = (INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp)
2697 - INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp2)
2698 - insn_delay (tmp2))))
2699 return rfs_result (RFS_PRESSURE_DELAY, diff, tmp, tmp2);
2702 if (sched_pressure != SCHED_PRESSURE_NONE
2703 && (INSN_TICK (tmp2) > clock_var || INSN_TICK (tmp) > clock_var)
2704 && INSN_TICK (tmp2) != INSN_TICK (tmp))
2706 diff = INSN_TICK (tmp) - INSN_TICK (tmp2);
2707 return rfs_result (RFS_PRESSURE_TICK, diff, tmp, tmp2);
2710 /* If we are doing backtracking in this schedule, prefer insns that
2711 have forward dependencies with negative cost against an insn that
2712 was already scheduled. */
2713 if (current_sched_info->flags & DO_BACKTRACKING)
2715 priority_val = FEEDS_BACKTRACK_INSN (tmp2) - FEEDS_BACKTRACK_INSN (tmp);
2717 return rfs_result (RFS_FEEDS_BACKTRACK_INSN, priority_val, tmp, tmp2);
2720 /* Prefer insn with higher priority. */
2721 priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
2723 if (flag_sched_critical_path_heuristic && priority_val)
2724 return rfs_result (RFS_PRIORITY, priority_val, tmp, tmp2);
2726 if (PARAM_VALUE (PARAM_SCHED_AUTOPREF_QUEUE_DEPTH) >= 0)
2728 int autopref = autopref_rank_for_schedule (tmp, tmp2);
2733 /* Prefer speculative insn with greater dependencies weakness. */
2734 if (flag_sched_spec_insn_heuristic && spec_info)
2740 ds1 = TODO_SPEC (tmp) & SPECULATIVE;
2742 dw1 = ds_weak (ds1);
2746 ds2 = TODO_SPEC (tmp2) & SPECULATIVE;
2748 dw2 = ds_weak (ds2);
2753 if (dw > (NO_DEP_WEAK / 8) || dw < -(NO_DEP_WEAK / 8))
2754 return rfs_result (RFS_SPECULATION, dw, tmp, tmp2);
2757 info_val = (*current_sched_info->rank) (tmp, tmp2);
2758 if (flag_sched_rank_heuristic && info_val)
2759 return rfs_result (RFS_SCHED_RANK, info_val, tmp, tmp2);
2761 /* Compare insns based on their relation to the last scheduled
2763 if (flag_sched_last_insn_heuristic && last_nondebug_scheduled_insn)
2767 rtx_insn *last = last_nondebug_scheduled_insn;
2769 /* Classify the instructions into three classes:
2770 1) Data dependent on last schedule insn.
2771 2) Anti/Output dependent on last scheduled insn.
2772 3) Independent of last scheduled insn, or has latency of one.
2773 Choose the insn from the highest numbered class if different. */
2774 dep1 = sd_find_dep_between (last, tmp, true);
2776 if (dep1 == NULL || dep_cost (dep1) == 1)
2778 else if (/* Data dependence. */
2779 DEP_TYPE (dep1) == REG_DEP_TRUE)
2784 dep2 = sd_find_dep_between (last, tmp2, true);
2786 if (dep2 == NULL || dep_cost (dep2) == 1)
2788 else if (/* Data dependence. */
2789 DEP_TYPE (dep2) == REG_DEP_TRUE)
2794 if ((val = tmp2_class - tmp_class))
2795 return rfs_result (RFS_LAST_INSN, val, tmp, tmp2);
2798 /* Prefer instructions that occur earlier in the model schedule. */
2799 if (sched_pressure == SCHED_PRESSURE_MODEL
2800 && INSN_BB (tmp) == target_bb && INSN_BB (tmp2) == target_bb)
2802 diff = model_index (tmp) - model_index (tmp2);
2803 gcc_assert (diff != 0);
2804 return rfs_result (RFS_PRESSURE_INDEX, diff, tmp, tmp2);
2807 /* Prefer the insn which has more later insns that depend on it.
2808 This gives the scheduler more freedom when scheduling later
2809 instructions at the expense of added register pressure. */
2811 val = (dep_list_size (tmp2, SD_LIST_FORW)
2812 - dep_list_size (tmp, SD_LIST_FORW));
2814 if (flag_sched_dep_count_heuristic && val != 0)
2815 return rfs_result (RFS_DEP_COUNT, val, tmp, tmp2);
2817 /* If insns are equally good, sort by INSN_LUID (original insn order),
2818 so that we make the sort stable. This minimizes instruction movement,
2819 thus minimizing sched's effect on debugging and cross-jumping. */
2820 return rfs_result (RFS_TIE, INSN_LUID (tmp) - INSN_LUID (tmp2), tmp, tmp2);
2823 /* Resort the array A in which only element at index N may be out of order. */
2825 HAIFA_INLINE static void
2826 swap_sort (rtx_insn **a, int n)
2828 rtx_insn *insn = a[n - 1];
2831 while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0)
2839 /* Add INSN to the insn queue so that it can be executed at least
2840 N_CYCLES after the currently executing insn. Preserve insns
2841 chain for debugging purposes. REASON will be printed in debugging
2844 HAIFA_INLINE static void
2845 queue_insn (rtx_insn *insn, int n_cycles, const char *reason)
2847 int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
2848 rtx_insn_list *link = alloc_INSN_LIST (insn, insn_queue[next_q]);
2851 gcc_assert (n_cycles <= max_insn_queue_index);
2852 gcc_assert (!DEBUG_INSN_P (insn));
2854 insn_queue[next_q] = link;
2857 if (sched_verbose >= 2)
2859 fprintf (sched_dump, ";;\t\tReady-->Q: insn %s: ",
2860 (*current_sched_info->print_insn) (insn, 0));
2862 fprintf (sched_dump, "queued for %d cycles (%s).\n", n_cycles, reason);
2865 QUEUE_INDEX (insn) = next_q;
2867 if (current_sched_info->flags & DO_BACKTRACKING)
2869 new_tick = clock_var + n_cycles;
2870 if (INSN_TICK (insn) == INVALID_TICK || INSN_TICK (insn) < new_tick)
2871 INSN_TICK (insn) = new_tick;
2873 if (INSN_EXACT_TICK (insn) != INVALID_TICK
2874 && INSN_EXACT_TICK (insn) < clock_var + n_cycles)
2876 must_backtrack = true;
2877 if (sched_verbose >= 2)
2878 fprintf (sched_dump, ";;\t\tcausing a backtrack.\n");
2883 /* Remove INSN from queue. */
2885 queue_remove (rtx_insn *insn)
2887 gcc_assert (QUEUE_INDEX (insn) >= 0);
2888 remove_free_INSN_LIST_elem (insn, &insn_queue[QUEUE_INDEX (insn)]);
2890 QUEUE_INDEX (insn) = QUEUE_NOWHERE;
2893 /* Return a pointer to the bottom of the ready list, i.e. the insn
2894 with the lowest priority. */
2897 ready_lastpos (struct ready_list *ready)
2899 gcc_assert (ready->n_ready >= 1);
2900 return ready->vec + ready->first - ready->n_ready + 1;
2903 /* Add an element INSN to the ready list so that it ends up with the
2904 lowest/highest priority depending on FIRST_P. */
2906 HAIFA_INLINE static void
2907 ready_add (struct ready_list *ready, rtx_insn *insn, bool first_p)
2911 if (ready->first == ready->n_ready)
2913 memmove (ready->vec + ready->veclen - ready->n_ready,
2914 ready_lastpos (ready),
2915 ready->n_ready * sizeof (rtx));
2916 ready->first = ready->veclen - 1;
2918 ready->vec[ready->first - ready->n_ready] = insn;
2922 if (ready->first == ready->veclen - 1)
2925 /* ready_lastpos() fails when called with (ready->n_ready == 0). */
2926 memmove (ready->vec + ready->veclen - ready->n_ready - 1,
2927 ready_lastpos (ready),
2928 ready->n_ready * sizeof (rtx));
2929 ready->first = ready->veclen - 2;
2931 ready->vec[++(ready->first)] = insn;
2935 if (DEBUG_INSN_P (insn))
2938 gcc_assert (QUEUE_INDEX (insn) != QUEUE_READY);
2939 QUEUE_INDEX (insn) = QUEUE_READY;
2941 if (INSN_EXACT_TICK (insn) != INVALID_TICK
2942 && INSN_EXACT_TICK (insn) < clock_var)
2944 must_backtrack = true;
2948 /* Remove the element with the highest priority from the ready list and
2951 HAIFA_INLINE static rtx_insn *
2952 ready_remove_first (struct ready_list *ready)
2956 gcc_assert (ready->n_ready);
2957 t = ready->vec[ready->first--];
2959 if (DEBUG_INSN_P (t))
2961 /* If the queue becomes empty, reset it. */
2962 if (ready->n_ready == 0)
2963 ready->first = ready->veclen - 1;
2965 gcc_assert (QUEUE_INDEX (t) == QUEUE_READY);
2966 QUEUE_INDEX (t) = QUEUE_NOWHERE;
2971 /* The following code implements multi-pass scheduling for the first
2972 cycle. In other words, we will try to choose ready insn which
2973 permits to start maximum number of insns on the same cycle. */
2975 /* Return a pointer to the element INDEX from the ready. INDEX for
2976 insn with the highest priority is 0, and the lowest priority has
2980 ready_element (struct ready_list *ready, int index)
2982 gcc_assert (ready->n_ready && index < ready->n_ready);
2984 return ready->vec[ready->first - index];
2987 /* Remove the element INDEX from the ready list and return it. INDEX
2988 for insn with the highest priority is 0, and the lowest priority
2991 HAIFA_INLINE static rtx_insn *
2992 ready_remove (struct ready_list *ready, int index)
2998 return ready_remove_first (ready);
2999 gcc_assert (ready->n_ready && index < ready->n_ready);
3000 t = ready->vec[ready->first - index];
3002 if (DEBUG_INSN_P (t))
3004 for (i = index; i < ready->n_ready; i++)
3005 ready->vec[ready->first - i] = ready->vec[ready->first - i - 1];
3006 QUEUE_INDEX (t) = QUEUE_NOWHERE;
3010 /* Remove INSN from the ready list. */
3012 ready_remove_insn (rtx_insn *insn)
3016 for (i = 0; i < readyp->n_ready; i++)
3017 if (ready_element (readyp, i) == insn)
3019 ready_remove (readyp, i);
3025 /* Calculate difference of two statistics set WAS and NOW.
3026 Result returned in WAS. */
3028 rank_for_schedule_stats_diff (rank_for_schedule_stats_t *was,
3029 const rank_for_schedule_stats_t *now)
3031 for (int i = 0; i < RFS_N; ++i)
3032 was->stats[i] = now->stats[i] - was->stats[i];
3035 /* Print rank_for_schedule statistics. */
3037 print_rank_for_schedule_stats (const char *prefix,
3038 const rank_for_schedule_stats_t *stats,
3039 struct ready_list *ready)
3041 for (int i = 0; i < RFS_N; ++i)
3042 if (stats->stats[i])
3044 fprintf (sched_dump, "%s%20s: %u", prefix, rfs_str[i], stats->stats[i]);
3047 /* Print out insns that won due to RFS_<I>. */
3049 rtx_insn **p = ready_lastpos (ready);
3051 fprintf (sched_dump, ":");
3052 /* Start with 1 since least-priority insn didn't have any wins. */
3053 for (int j = 1; j < ready->n_ready; ++j)
3054 if (INSN_LAST_RFS_WIN (p[j]) == i)
3055 fprintf (sched_dump, " %s",
3056 (*current_sched_info->print_insn) (p[j], 0));
3058 fprintf (sched_dump, "\n");
3062 /* Separate DEBUG_INSNS from normal insns. DEBUG_INSNs go to the end
3065 ready_sort_debug (struct ready_list *ready)
3068 rtx_insn **first = ready_lastpos (ready);
3070 for (i = 0; i < ready->n_ready; ++i)
3071 if (!DEBUG_INSN_P (first[i]))
3072 INSN_RFS_DEBUG_ORIG_ORDER (first[i]) = i;
3074 qsort (first, ready->n_ready, sizeof (rtx), rank_for_schedule_debug);
3077 /* Sort non-debug insns in the ready list READY by ascending priority.
3078 Assumes that all debug insns are separated from the real insns. */
3080 ready_sort_real (struct ready_list *ready)
3083 rtx_insn **first = ready_lastpos (ready);
3084 int n_ready_real = ready->n_ready - ready->n_debug;
3086 if (sched_pressure == SCHED_PRESSURE_WEIGHTED)
3087 for (i = 0; i < n_ready_real; ++i)
3088 setup_insn_reg_pressure_info (first[i]);
3089 else if (sched_pressure == SCHED_PRESSURE_MODEL
3090 && model_curr_point < model_num_insns)
3091 model_set_excess_costs (first, n_ready_real);
3093 rank_for_schedule_stats_t stats1;
3094 if (sched_verbose >= 4)
3095 stats1 = rank_for_schedule_stats;
3097 if (n_ready_real == 2)
3098 swap_sort (first, n_ready_real);
3099 else if (n_ready_real > 2)
3100 qsort (first, n_ready_real, sizeof (rtx), rank_for_schedule);
3102 if (sched_verbose >= 4)
3104 rank_for_schedule_stats_diff (&stats1, &rank_for_schedule_stats);
3105 print_rank_for_schedule_stats (";;\t\t", &stats1, ready);
3109 /* Sort the ready list READY by ascending priority. */
3111 ready_sort (struct ready_list *ready)
3113 if (ready->n_debug > 0)
3114 ready_sort_debug (ready);
3116 ready_sort_real (ready);
3119 /* PREV is an insn that is ready to execute. Adjust its priority if that
3120 will help shorten or lengthen register lifetimes as appropriate. Also
3121 provide a hook for the target to tweak itself. */
3123 HAIFA_INLINE static void
3124 adjust_priority (rtx_insn *prev)
3126 /* ??? There used to be code here to try and estimate how an insn
3127 affected register lifetimes, but it did it by looking at REG_DEAD
3128 notes, which we removed in schedule_region. Nor did it try to
3129 take into account register pressure or anything useful like that.
3131 Revisit when we have a machine model to work with and not before. */
3133 if (targetm.sched.adjust_priority)
3134 INSN_PRIORITY (prev) =
3135 targetm.sched.adjust_priority (prev, INSN_PRIORITY (prev));
3138 /* Advance DFA state STATE on one cycle. */
3140 advance_state (state_t state)
3142 if (targetm.sched.dfa_pre_advance_cycle)
3143 targetm.sched.dfa_pre_advance_cycle ();
3145 if (targetm.sched.dfa_pre_cycle_insn)
3146 state_transition (state,
3147 targetm.sched.dfa_pre_cycle_insn ());
3149 state_transition (state, NULL);
3151 if (targetm.sched.dfa_post_cycle_insn)
3152 state_transition (state,
3153 targetm.sched.dfa_post_cycle_insn ());
3155 if (targetm.sched.dfa_post_advance_cycle)
3156 targetm.sched.dfa_post_advance_cycle ();
3159 /* Advance time on one cycle. */
3160 HAIFA_INLINE static void
3161 advance_one_cycle (void)
3163 advance_state (curr_state);
3164 if (sched_verbose >= 4)
3165 fprintf (sched_dump, ";;\tAdvance the current state.\n");
3168 /* Update register pressure after scheduling INSN. */
3170 update_register_pressure (rtx_insn *insn)
3172 struct reg_use_data *use;
3173 struct reg_set_data *set;
3175 gcc_checking_assert (!DEBUG_INSN_P (insn));
3177 for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
3178 if (dying_use_p (use))
3179 mark_regno_birth_or_death (curr_reg_live, curr_reg_pressure,
3181 for (set = INSN_REG_SET_LIST (insn); set != NULL; set = set->next_insn_set)
3182 mark_regno_birth_or_death (curr_reg_live, curr_reg_pressure,
3186 /* Set up or update (if UPDATE_P) max register pressure (see its
3187 meaning in sched-int.h::_haifa_insn_data) for all current BB insns
3188 after insn AFTER. */
3190 setup_insn_max_reg_pressure (rtx_insn *after, bool update_p)
3195 static int max_reg_pressure[N_REG_CLASSES];
3197 save_reg_pressure ();
3198 for (i = 0; i < ira_pressure_classes_num; i++)
3199 max_reg_pressure[ira_pressure_classes[i]]
3200 = curr_reg_pressure[ira_pressure_classes[i]];
3201 for (insn = NEXT_INSN (after);
3202 insn != NULL_RTX && ! BARRIER_P (insn)
3203 && BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (after);
3204 insn = NEXT_INSN (insn))
3205 if (NONDEBUG_INSN_P (insn))
3208 for (i = 0; i < ira_pressure_classes_num; i++)
3210 p = max_reg_pressure[ira_pressure_classes[i]];
3211 if (INSN_MAX_REG_PRESSURE (insn)[i] != p)
3214 INSN_MAX_REG_PRESSURE (insn)[i]
3215 = max_reg_pressure[ira_pressure_classes[i]];
3218 if (update_p && eq_p)
3220 update_register_pressure (insn);
3221 for (i = 0; i < ira_pressure_classes_num; i++)
3222 if (max_reg_pressure[ira_pressure_classes[i]]
3223 < curr_reg_pressure[ira_pressure_classes[i]])
3224 max_reg_pressure[ira_pressure_classes[i]]
3225 = curr_reg_pressure[ira_pressure_classes[i]];
3227 restore_reg_pressure ();
3230 /* Update the current register pressure after scheduling INSN. Update
3231 also max register pressure for unscheduled insns of the current
3234 update_reg_and_insn_max_reg_pressure (rtx_insn *insn)
3237 int before[N_REG_CLASSES];
3239 for (i = 0; i < ira_pressure_classes_num; i++)
3240 before[i] = curr_reg_pressure[ira_pressure_classes[i]];
3241 update_register_pressure (insn);
3242 for (i = 0; i < ira_pressure_classes_num; i++)
3243 if (curr_reg_pressure[ira_pressure_classes[i]] != before[i])
3245 if (i < ira_pressure_classes_num)
3246 setup_insn_max_reg_pressure (insn, true);
3249 /* Set up register pressure at the beginning of basic block BB whose
3250 insns starting after insn AFTER. Set up also max register pressure
3251 for all insns of the basic block. */
3253 sched_setup_bb_reg_pressure_info (basic_block bb, rtx_insn *after)
3255 gcc_assert (sched_pressure == SCHED_PRESSURE_WEIGHTED);
3256 initiate_bb_reg_pressure_info (bb);
3257 setup_insn_max_reg_pressure (after, false);
3260 /* If doing predication while scheduling, verify whether INSN, which
3261 has just been scheduled, clobbers the conditions of any
3262 instructions that must be predicated in order to break their
3263 dependencies. If so, remove them from the queues so that they will
3264 only be scheduled once their control dependency is resolved. */
3267 check_clobbered_conditions (rtx_insn *insn)
3272 if ((current_sched_info->flags & DO_PREDICATION) == 0)
3275 find_all_hard_reg_sets (insn, &t, true);
3278 for (i = 0; i < ready.n_ready; i++)
3280 rtx_insn *x = ready_element (&ready, i);
3281 if (TODO_SPEC (x) == DEP_CONTROL && cond_clobbered_p (x, t))
3283 ready_remove_insn (x);
3287 for (i = 0; i <= max_insn_queue_index; i++)
3289 rtx_insn_list *link;
3290 int q = NEXT_Q_AFTER (q_ptr, i);
3293 for (link = insn_queue[q]; link; link = link->next ())
3295 rtx_insn *x = link->insn ();
3296 if (TODO_SPEC (x) == DEP_CONTROL && cond_clobbered_p (x, t))
3305 /* Return (in order):
3307 - positive if INSN adversely affects the pressure on one
3310 - negative if INSN reduces the pressure on one register class
3312 - 0 if INSN doesn't affect the pressure on any register class. */
3315 model_classify_pressure (struct model_insn_info *insn)
3317 struct reg_pressure_data *reg_pressure;
3318 int death[N_REG_CLASSES];
3321 calculate_reg_deaths (insn->insn, death);
3322 reg_pressure = INSN_REG_PRESSURE (insn->insn);
3324 for (pci = 0; pci < ira_pressure_classes_num; pci++)
3326 cl = ira_pressure_classes[pci];
3327 if (death[cl] < reg_pressure[pci].set_increase)
3329 sum += reg_pressure[pci].set_increase - death[cl];
3334 /* Return true if INSN1 should come before INSN2 in the model schedule. */
3337 model_order_p (struct model_insn_info *insn1, struct model_insn_info *insn2)
3339 unsigned int height1, height2;
3340 unsigned int priority1, priority2;
3342 /* Prefer instructions with a higher model priority. */
3343 if (insn1->model_priority != insn2->model_priority)
3344 return insn1->model_priority > insn2->model_priority;
3346 /* Combine the length of the longest path of satisfied true dependencies
3347 that leads to each instruction (depth) with the length of the longest
3348 path of any dependencies that leads from the instruction (alap).
3349 Prefer instructions with the greatest combined length. If the combined
3350 lengths are equal, prefer instructions with the greatest depth.
3352 The idea is that, if we have a set S of "equal" instructions that each
3353 have ALAP value X, and we pick one such instruction I, any true-dependent
3354 successors of I that have ALAP value X - 1 should be preferred over S.
3355 This encourages the schedule to be "narrow" rather than "wide".
3356 However, if I is a low-priority instruction that we decided to
3357 schedule because of its model_classify_pressure, and if there
3358 is a set of higher-priority instructions T, the aforementioned
3359 successors of I should not have the edge over T. */
3360 height1 = insn1->depth + insn1->alap;
3361 height2 = insn2->depth + insn2->alap;
3362 if (height1 != height2)
3363 return height1 > height2;
3364 if (insn1->depth != insn2->depth)
3365 return insn1->depth > insn2->depth;
3367 /* We have no real preference between INSN1 an INSN2 as far as attempts
3368 to reduce pressure go. Prefer instructions with higher priorities. */
3369 priority1 = INSN_PRIORITY (insn1->insn);
3370 priority2 = INSN_PRIORITY (insn2->insn);
3371 if (priority1 != priority2)
3372 return priority1 > priority2;
3374 /* Use the original rtl sequence as a tie-breaker. */
3375 return insn1 < insn2;
3378 /* Add INSN to the model worklist immediately after PREV. Add it to the
3379 beginning of the list if PREV is null. */
3382 model_add_to_worklist_at (struct model_insn_info *insn,
3383 struct model_insn_info *prev)
3385 gcc_assert (QUEUE_INDEX (insn->insn) == QUEUE_NOWHERE);
3386 QUEUE_INDEX (insn->insn) = QUEUE_READY;
3391 insn->next = prev->next;
3396 insn->next = model_worklist;
3397 model_worklist = insn;
3400 insn->next->prev = insn;
3403 /* Remove INSN from the model worklist. */
3406 model_remove_from_worklist (struct model_insn_info *insn)
3408 gcc_assert (QUEUE_INDEX (insn->insn) == QUEUE_READY);
3409 QUEUE_INDEX (insn->insn) = QUEUE_NOWHERE;
3412 insn->prev->next = insn->next;
3414 model_worklist = insn->next;
3416 insn->next->prev = insn->prev;
3419 /* Add INSN to the model worklist. Start looking for a suitable position
3420 between neighbors PREV and NEXT, testing at most MAX_SCHED_READY_INSNS
3421 insns either side. A null PREV indicates the beginning of the list and
3422 a null NEXT indicates the end. */
3425 model_add_to_worklist (struct model_insn_info *insn,
3426 struct model_insn_info *prev,
3427 struct model_insn_info *next)
3431 count = MAX_SCHED_READY_INSNS;
3432 if (count > 0 && prev && model_order_p (insn, prev))
3438 while (count > 0 && prev && model_order_p (insn, prev));
3440 while (count > 0 && next && model_order_p (next, insn))
3446 model_add_to_worklist_at (insn, prev);
3449 /* INSN may now have a higher priority (in the model_order_p sense)
3450 than before. Move it up the worklist if necessary. */
3453 model_promote_insn (struct model_insn_info *insn)
3455 struct model_insn_info *prev;
3459 count = MAX_SCHED_READY_INSNS;
3460 while (count > 0 && prev && model_order_p (insn, prev))
3465 if (prev != insn->prev)
3467 model_remove_from_worklist (insn);
3468 model_add_to_worklist_at (insn, prev);
3472 /* Add INSN to the end of the model schedule. */
3475 model_add_to_schedule (rtx_insn *insn)
3479 gcc_assert (QUEUE_INDEX (insn) == QUEUE_NOWHERE);
3480 QUEUE_INDEX (insn) = QUEUE_SCHEDULED;
3482 point = model_schedule.length ();
3483 model_schedule.quick_push (insn);
3484 INSN_MODEL_INDEX (insn) = point + 1;
3487 /* Analyze the instructions that are to be scheduled, setting up
3488 MODEL_INSN_INFO (...) and model_num_insns accordingly. Add ready
3489 instructions to model_worklist. */
3492 model_analyze_insns (void)
3494 rtx_insn *start, *end, *iter;
3495 sd_iterator_def sd_it;
3497 struct model_insn_info *insn, *con;
3499 model_num_insns = 0;
3500 start = PREV_INSN (current_sched_info->next_tail);
3501 end = current_sched_info->prev_head;
3502 for (iter = start; iter != end; iter = PREV_INSN (iter))
3503 if (NONDEBUG_INSN_P (iter))
3505 insn = MODEL_INSN_INFO (iter);
3507 FOR_EACH_DEP (iter, SD_LIST_FORW, sd_it, dep)
3509 con = MODEL_INSN_INFO (DEP_CON (dep));
3510 if (con->insn && insn->alap < con->alap + 1)
3511 insn->alap = con->alap + 1;
3514 insn->old_queue = QUEUE_INDEX (iter);
3515 QUEUE_INDEX (iter) = QUEUE_NOWHERE;
3517 insn->unscheduled_preds = dep_list_size (iter, SD_LIST_HARD_BACK);
3518 if (insn->unscheduled_preds == 0)
3519 model_add_to_worklist (insn, NULL, model_worklist);
3525 /* The global state describes the register pressure at the start of the
3526 model schedule. Initialize GROUP accordingly. */
3529 model_init_pressure_group (struct model_pressure_group *group)
3533 for (pci = 0; pci < ira_pressure_classes_num; pci++)
3535 cl = ira_pressure_classes[pci];
3536 group->limits[pci].pressure = curr_reg_pressure[cl];
3537 group->limits[pci].point = 0;
3539 /* Use index model_num_insns to record the state after the last
3540 instruction in the model schedule. */
3541 group->model = XNEWVEC (struct model_pressure_data,
3542 (model_num_insns + 1) * ira_pressure_classes_num);
3545 /* Record that MODEL_REF_PRESSURE (GROUP, POINT, PCI) is PRESSURE.
3546 Update the maximum pressure for the whole schedule. */
3549 model_record_pressure (struct model_pressure_group *group,
3550 int point, int pci, int pressure)
3552 MODEL_REF_PRESSURE (group, point, pci) = pressure;
3553 if (group->limits[pci].pressure < pressure)
3555 group->limits[pci].pressure = pressure;
3556 group->limits[pci].point = point;
3560 /* INSN has just been added to the end of the model schedule. Record its
3561 register-pressure information. */
3564 model_record_pressures (struct model_insn_info *insn)
3566 struct reg_pressure_data *reg_pressure;
3567 int point, pci, cl, delta;
3568 int death[N_REG_CLASSES];
3570 point = model_index (insn->insn);
3571 if (sched_verbose >= 2)
3575 fprintf (sched_dump, "\n;;\tModel schedule:\n;;\n");
3576 fprintf (sched_dump, ";;\t| idx insn | mpri hght dpth prio |\n");
3578 fprintf (sched_dump, ";;\t| %3d %4d | %4d %4d %4d %4d | %-30s ",
3579 point, INSN_UID (insn->insn), insn->model_priority,
3580 insn->depth + insn->alap, insn->depth,
3581 INSN_PRIORITY (insn->insn),
3582 str_pattern_slim (PATTERN (insn->insn)));
3584 calculate_reg_deaths (insn->insn, death);
3585 reg_pressure = INSN_REG_PRESSURE (insn->insn);
3586 for (pci = 0; pci < ira_pressure_classes_num; pci++)
3588 cl = ira_pressure_classes[pci];
3589 delta = reg_pressure[pci].set_increase - death[cl];
3590 if (sched_verbose >= 2)
3591 fprintf (sched_dump, " %s:[%d,%+d]", reg_class_names[cl],
3592 curr_reg_pressure[cl], delta);
3593 model_record_pressure (&model_before_pressure, point, pci,
3594 curr_reg_pressure[cl]);
3596 if (sched_verbose >= 2)
3597 fprintf (sched_dump, "\n");
3600 /* All instructions have been added to the model schedule. Record the
3601 final register pressure in GROUP and set up all MODEL_MAX_PRESSUREs. */
3604 model_record_final_pressures (struct model_pressure_group *group)
3606 int point, pci, max_pressure, ref_pressure, cl;
3608 for (pci = 0; pci < ira_pressure_classes_num; pci++)
3610 /* Record the final pressure for this class. */
3611 cl = ira_pressure_classes[pci];
3612 point = model_num_insns;
3613 ref_pressure = curr_reg_pressure[cl];
3614 model_record_pressure (group, point, pci, ref_pressure);
3616 /* Record the original maximum pressure. */
3617 group->limits[pci].orig_pressure = group->limits[pci].pressure;
3619 /* Update the MODEL_MAX_PRESSURE for every point of the schedule. */
3620 max_pressure = ref_pressure;
3621 MODEL_MAX_PRESSURE (group, point, pci) = max_pressure;
3625 ref_pressure = MODEL_REF_PRESSURE (group, point, pci);
3626 max_pressure = MAX (max_pressure, ref_pressure);
3627 MODEL_MAX_PRESSURE (group, point, pci) = max_pressure;
3632 /* Update all successors of INSN, given that INSN has just been scheduled. */
3635 model_add_successors_to_worklist (struct model_insn_info *insn)
3637 sd_iterator_def sd_it;
3638 struct model_insn_info *con;
3641 FOR_EACH_DEP (insn->insn, SD_LIST_FORW, sd_it, dep)
3643 con = MODEL_INSN_INFO (DEP_CON (dep));
3644 /* Ignore debug instructions, and instructions from other blocks. */
3647 con->unscheduled_preds--;
3649 /* Update the depth field of each true-dependent successor.
3650 Increasing the depth gives them a higher priority than
3652 if (DEP_TYPE (dep) == REG_DEP_TRUE && con->depth < insn->depth + 1)
3654 con->depth = insn->depth + 1;
3655 if (QUEUE_INDEX (con->insn) == QUEUE_READY)
3656 model_promote_insn (con);
3659 /* If this is a true dependency, or if there are no remaining
3660 dependencies for CON (meaning that CON only had non-true
3661 dependencies), make sure that CON is on the worklist.
3662 We don't bother otherwise because it would tend to fill the
3663 worklist with a lot of low-priority instructions that are not
3664 yet ready to issue. */
3665 if ((con->depth > 0 || con->unscheduled_preds == 0)
3666 && QUEUE_INDEX (con->insn) == QUEUE_NOWHERE)
3667 model_add_to_worklist (con, insn, insn->next);
3672 /* Give INSN a higher priority than any current instruction, then give
3673 unscheduled predecessors of INSN a higher priority still. If any of
3674 those predecessors are not on the model worklist, do the same for its
3675 predecessors, and so on. */
3678 model_promote_predecessors (struct model_insn_info *insn)
3680 struct model_insn_info *pro, *first;
3681 sd_iterator_def sd_it;
3684 if (sched_verbose >= 7)
3685 fprintf (sched_dump, ";;\t+--- priority of %d = %d, priority of",
3686 INSN_UID (insn->insn), model_next_priority);
3687 insn->model_priority = model_next_priority++;
3688 model_remove_from_worklist (insn);
3689 model_add_to_worklist_at (insn, NULL);
3694 FOR_EACH_DEP (insn->insn, SD_LIST_HARD_BACK, sd_it, dep)
3696 pro = MODEL_INSN_INFO (DEP_PRO (dep));
3697 /* The first test is to ignore debug instructions, and instructions
3698 from other blocks. */
3700 && pro->model_priority != model_next_priority
3701 && QUEUE_INDEX (pro->insn) != QUEUE_SCHEDULED)
3703 pro->model_priority = model_next_priority;
3704 if (sched_verbose >= 7)
3705 fprintf (sched_dump, " %d", INSN_UID (pro->insn));
3706 if (QUEUE_INDEX (pro->insn) == QUEUE_READY)
3708 /* PRO is already in the worklist, but it now has
3709 a higher priority than before. Move it at the
3710 appropriate place. */
3711 model_remove_from_worklist (pro);
3712 model_add_to_worklist (pro, NULL, model_worklist);
3716 /* PRO isn't in the worklist. Recursively process
3717 its predecessors until we find one that is. */
3728 if (sched_verbose >= 7)
3729 fprintf (sched_dump, " = %d\n", model_next_priority);
3730 model_next_priority++;
3733 /* Pick one instruction from model_worklist and process it. */
3736 model_choose_insn (void)
3738 struct model_insn_info *insn, *fallback;
3741 if (sched_verbose >= 7)
3743 fprintf (sched_dump, ";;\t+--- worklist:\n");
3744 insn = model_worklist;
3745 count = MAX_SCHED_READY_INSNS;
3746 while (count > 0 && insn)
3748 fprintf (sched_dump, ";;\t+--- %d [%d, %d, %d, %d]\n",
3749 INSN_UID (insn->insn), insn->model_priority,
3750 insn->depth + insn->alap, insn->depth,
3751 INSN_PRIORITY (insn->insn));
3757 /* Look for a ready instruction whose model_classify_priority is zero
3758 or negative, picking the highest-priority one. Adding such an
3759 instruction to the schedule now should do no harm, and may actually
3762 Failing that, see whether there is an instruction with the highest
3763 extant model_priority that is not yet ready, but which would reduce
3764 pressure if it became ready. This is designed to catch cases like:
3766 (set (mem (reg R1)) (reg R2))
3768 where the instruction is the last remaining use of R1 and where the
3769 value of R2 is not yet available (or vice versa). The death of R1
3770 means that this instruction already reduces pressure. It is of
3771 course possible that the computation of R2 involves other registers
3772 that are hard to kill, but such cases are rare enough for this
3773 heuristic to be a win in general.
3775 Failing that, just pick the highest-priority instruction in the
3777 count = MAX_SCHED_READY_INSNS;
3778 insn = model_worklist;
3782 if (count == 0 || !insn)
3784 insn = fallback ? fallback : model_worklist;
3787 if (insn->unscheduled_preds)
3789 if (model_worklist->model_priority == insn->model_priority
3791 && model_classify_pressure (insn) < 0)
3796 if (model_classify_pressure (insn) <= 0)
3803 if (sched_verbose >= 7 && insn != model_worklist)
3805 if (insn->unscheduled_preds)
3806 fprintf (sched_dump, ";;\t+--- promoting insn %d, with dependencies\n",
3807 INSN_UID (insn->insn));
3809 fprintf (sched_dump, ";;\t+--- promoting insn %d, which is ready\n",
3810 INSN_UID (insn->insn));
3812 if (insn->unscheduled_preds)
3813 /* INSN isn't yet ready to issue. Give all its predecessors the
3814 highest priority. */
3815 model_promote_predecessors (insn);
3818 /* INSN is ready. Add it to the end of model_schedule and
3819 process its successors. */
3820 model_add_successors_to_worklist (insn);
3821 model_remove_from_worklist (insn);
3822 model_add_to_schedule (insn->insn);
3823 model_record_pressures (insn);
3824 update_register_pressure (insn->insn);
3828 /* Restore all QUEUE_INDEXs to the values that they had before
3829 model_start_schedule was called. */
3832 model_reset_queue_indices (void)
3837 FOR_EACH_VEC_ELT (model_schedule, i, insn)
3838 QUEUE_INDEX (insn) = MODEL_INSN_INFO (insn)->old_queue;
3841 /* We have calculated the model schedule and spill costs. Print a summary
3845 model_dump_pressure_summary (void)
3849 fprintf (sched_dump, ";; Pressure summary:");
3850 for (pci = 0; pci < ira_pressure_classes_num; pci++)
3852 cl = ira_pressure_classes[pci];
3853 fprintf (sched_dump, " %s:%d", reg_class_names[cl],
3854 model_before_pressure.limits[pci].pressure);
3856 fprintf (sched_dump, "\n\n");
3859 /* Initialize the SCHED_PRESSURE_MODEL information for the current
3860 scheduling region. */
3863 model_start_schedule (basic_block bb)
3865 model_next_priority = 1;
3866 model_schedule.create (sched_max_luid);
3867 model_insns = XCNEWVEC (struct model_insn_info, sched_max_luid);
3869 gcc_assert (bb == BLOCK_FOR_INSN (NEXT_INSN (current_sched_info->prev_head)));
3870 initiate_reg_pressure_info (df_get_live_in (bb));
3872 model_analyze_insns ();
3873 model_init_pressure_group (&model_before_pressure);
3874 while (model_worklist)
3875 model_choose_insn ();
3876 gcc_assert (model_num_insns == (int) model_schedule.length ());
3877 if (sched_verbose >= 2)
3878 fprintf (sched_dump, "\n");
3880 model_record_final_pressures (&model_before_pressure);
3881 model_reset_queue_indices ();
3883 XDELETEVEC (model_insns);
3885 model_curr_point = 0;
3886 initiate_reg_pressure_info (df_get_live_in (bb));
3887 if (sched_verbose >= 1)
3888 model_dump_pressure_summary ();
3891 /* Free the information associated with GROUP. */
3894 model_finalize_pressure_group (struct model_pressure_group *group)
3896 XDELETEVEC (group->model);
3899 /* Free the information created by model_start_schedule. */
3902 model_end_schedule (void)
3904 model_finalize_pressure_group (&model_before_pressure);
3905 model_schedule.release ();
3908 /* Prepare reg pressure scheduling for basic block BB. */
3910 sched_pressure_start_bb (basic_block bb)
3912 /* Set the number of available registers for each class taking into account
3913 relative probability of current basic block versus function prologue and
3915 * If the basic block executes much more often than the prologue/epilogue
3916 (e.g., inside a hot loop), then cost of spill in the prologue is close to
3917 nil, so the effective number of available registers is
3918 (ira_class_hard_regs_num[cl] - 0).
3919 * If the basic block executes as often as the prologue/epilogue,
3920 then spill in the block is as costly as in the prologue, so the effective
3921 number of available registers is
3922 (ira_class_hard_regs_num[cl] - call_used_regs_num[cl]).
3923 Note that all-else-equal, we prefer to spill in the prologue, since that
3924 allows "extra" registers for other basic blocks of the function.
3925 * If the basic block is on the cold path of the function and executes
3926 rarely, then we should always prefer to spill in the block, rather than
3927 in the prologue/epilogue. The effective number of available register is
3928 (ira_class_hard_regs_num[cl] - call_used_regs_num[cl]). */
3931 int entry_freq = ENTRY_BLOCK_PTR_FOR_FN (cfun)->frequency;
3932 int bb_freq = bb->frequency;
3936 if (entry_freq == 0)
3937 entry_freq = bb_freq = 1;
3939 if (bb_freq < entry_freq)
3940 bb_freq = entry_freq;
3942 for (i = 0; i < ira_pressure_classes_num; ++i)
3944 enum reg_class cl = ira_pressure_classes[i];
3945 sched_class_regs_num[cl] = ira_class_hard_regs_num[cl];
3946 sched_class_regs_num[cl]
3947 -= (call_used_regs_num[cl] * entry_freq) / bb_freq;
3951 if (sched_pressure == SCHED_PRESSURE_MODEL)
3952 model_start_schedule (bb);
3955 /* A structure that holds local state for the loop in schedule_block. */
3956 struct sched_block_state
3958 /* True if no real insns have been scheduled in the current cycle. */
3959 bool first_cycle_insn_p;
3960 /* True if a shadow insn has been scheduled in the current cycle, which
3961 means that no more normal insns can be issued. */
3962 bool shadows_only_p;
3963 /* True if we're winding down a modulo schedule, which means that we only
3964 issue insns with INSN_EXACT_TICK set. */
3965 bool modulo_epilogue;
3966 /* Initialized with the machine's issue rate every cycle, and updated
3967 by calls to the variable_issue hook. */
3971 /* INSN is the "currently executing insn". Launch each insn which was
3972 waiting on INSN. READY is the ready list which contains the insns
3973 that are ready to fire. CLOCK is the current cycle. The function
3974 returns necessary cycle advance after issuing the insn (it is not
3975 zero for insns in a schedule group). */
3978 schedule_insn (rtx_insn *insn)
3980 sd_iterator_def sd_it;
3985 if (sched_verbose >= 1)
3987 struct reg_pressure_data *pressure_info;
3988 fprintf (sched_dump, ";;\t%3i--> %s %-40s:",
3989 clock_var, (*current_sched_info->print_insn) (insn, 1),
3990 str_pattern_slim (PATTERN (insn)));
3992 if (recog_memoized (insn) < 0)
3993 fprintf (sched_dump, "nothing");
3995 print_reservation (sched_dump, insn);
3996 pressure_info = INSN_REG_PRESSURE (insn);
3997 if (pressure_info != NULL)
3999 fputc (':', sched_dump);
4000 for (i = 0; i < ira_pressure_classes_num; i++)
4001 fprintf (sched_dump, "%s%s%+d(%d)",
4002 scheduled_insns.length () > 1
4004 < INSN_LUID (scheduled_insns[scheduled_insns.length () - 2]) ? "@" : "",
4005 reg_class_names[ira_pressure_classes[i]],
4006 pressure_info[i].set_increase, pressure_info[i].change);
4008 if (sched_pressure == SCHED_PRESSURE_MODEL
4009 && model_curr_point < model_num_insns
4010 && model_index (insn) == model_curr_point)
4011 fprintf (sched_dump, ":model %d", model_curr_point);
4012 fputc ('\n', sched_dump);
4015 if (sched_pressure == SCHED_PRESSURE_WEIGHTED && !DEBUG_INSN_P (insn))
4016 update_reg_and_insn_max_reg_pressure (insn);
4018 /* Scheduling instruction should have all its dependencies resolved and
4019 should have been removed from the ready list. */
4020 gcc_assert (sd_lists_empty_p (insn, SD_LIST_HARD_BACK));
4022 /* Reset debug insns invalidated by moving this insn. */
4023 if (MAY_HAVE_DEBUG_INSNS && !DEBUG_INSN_P (insn))
4024 for (sd_it = sd_iterator_start (insn, SD_LIST_BACK);
4025 sd_iterator_cond (&sd_it, &dep);)
4027 rtx_insn *dbg = DEP_PRO (dep);
4028 struct reg_use_data *use, *next;
4030 if (DEP_STATUS (dep) & DEP_CANCELLED)
4032 sd_iterator_next (&sd_it);
4036 gcc_assert (DEBUG_INSN_P (dbg));
4038 if (sched_verbose >= 6)
4039 fprintf (sched_dump, ";;\t\tresetting: debug insn %d\n",
4042 /* ??? Rather than resetting the debug insn, we might be able
4043 to emit a debug temp before the just-scheduled insn, but
4044 this would involve checking that the expression at the
4045 point of the debug insn is equivalent to the expression
4046 before the just-scheduled insn. They might not be: the
4047 expression in the debug insn may depend on other insns not
4048 yet scheduled that set MEMs, REGs or even other debug
4049 insns. It's not clear that attempting to preserve debug
4050 information in these cases is worth the effort, given how
4051 uncommon these resets are and the likelihood that the debug
4052 temps introduced won't survive the schedule change. */
4053 INSN_VAR_LOCATION_LOC (dbg) = gen_rtx_UNKNOWN_VAR_LOC ();
4054 df_insn_rescan (dbg);
4056 /* Unknown location doesn't use any registers. */
4057 for (use = INSN_REG_USE_LIST (dbg); use != NULL; use = next)
4059 struct reg_use_data *prev = use;
4061 /* Remove use from the cyclic next_regno_use chain first. */
4062 while (prev->next_regno_use != use)
4063 prev = prev->next_regno_use;
4064 prev->next_regno_use = use->next_regno_use;
4065 next = use->next_insn_use;
4068 INSN_REG_USE_LIST (dbg) = NULL;
4070 /* We delete rather than resolve these deps, otherwise we
4071 crash in sched_free_deps(), because forward deps are
4072 expected to be released before backward deps. */
4073 sd_delete_dep (sd_it);
4076 gcc_assert (QUEUE_INDEX (insn) == QUEUE_NOWHERE);
4077 QUEUE_INDEX (insn) = QUEUE_SCHEDULED;
4079 if (sched_pressure == SCHED_PRESSURE_MODEL
4080 && model_curr_point < model_num_insns
4081 && NONDEBUG_INSN_P (insn))
4083 if (model_index (insn) == model_curr_point)
4086 while (model_curr_point < model_num_insns
4087 && (QUEUE_INDEX (MODEL_INSN (model_curr_point))
4088 == QUEUE_SCHEDULED));
4090 model_recompute (insn);
4091 model_update_limit_points ();
4092 update_register_pressure (insn);
4093 if (sched_verbose >= 2)
4094 print_curr_reg_pressure ();
4097 gcc_assert (INSN_TICK (insn) >= MIN_TICK);
4098 if (INSN_TICK (insn) > clock_var)
4099 /* INSN has been prematurely moved from the queue to the ready list.
4100 This is possible only if following flags are set. */
4101 gcc_assert (flag_sched_stalled_insns || sched_fusion);
4103 /* ??? Probably, if INSN is scheduled prematurely, we should leave
4104 INSN_TICK untouched. This is a machine-dependent issue, actually. */
4105 INSN_TICK (insn) = clock_var;
4107 check_clobbered_conditions (insn);
4109 /* Update dependent instructions. First, see if by scheduling this insn
4110 now we broke a dependence in a way that requires us to change another
4112 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
4113 sd_iterator_cond (&sd_it, &dep); sd_iterator_next (&sd_it))
4115 struct dep_replacement *desc = DEP_REPLACE (dep);
4116 rtx_insn *pro = DEP_PRO (dep);
4117 if (QUEUE_INDEX (pro) != QUEUE_SCHEDULED
4118 && desc != NULL && desc->insn == pro)
4119 apply_replacement (dep, false);
4122 /* Go through and resolve forward dependencies. */
4123 for (sd_it = sd_iterator_start (insn, SD_LIST_FORW);
4124 sd_iterator_cond (&sd_it, &dep);)
4126 rtx_insn *next = DEP_CON (dep);
4127 bool cancelled = (DEP_STATUS (dep) & DEP_CANCELLED) != 0;
4129 /* Resolve the dependence between INSN and NEXT.
4130 sd_resolve_dep () moves current dep to another list thus
4131 advancing the iterator. */
4132 sd_resolve_dep (sd_it);
4136 if (must_restore_pattern_p (next, dep))
4137 restore_pattern (dep, false);
4141 /* Don't bother trying to mark next as ready if insn is a debug
4142 insn. If insn is the last hard dependency, it will have
4143 already been discounted. */
4144 if (DEBUG_INSN_P (insn) && !DEBUG_INSN_P (next))
4147 if (!IS_SPECULATION_BRANCHY_CHECK_P (insn))
4151 effective_cost = try_ready (next);
4153 if (effective_cost >= 0
4154 && SCHED_GROUP_P (next)
4155 && advance < effective_cost)
4156 advance = effective_cost;
4159 /* Check always has only one forward dependence (to the first insn in
4160 the recovery block), therefore, this will be executed only once. */
4162 gcc_assert (sd_lists_empty_p (insn, SD_LIST_FORW));
4163 fix_recovery_deps (RECOVERY_BLOCK (insn));
4167 /* Annotate the instruction with issue information -- TImode
4168 indicates that the instruction is expected not to be able
4169 to issue on the same cycle as the previous insn. A machine
4170 may use this information to decide how the instruction should
4173 && GET_CODE (PATTERN (insn)) != USE
4174 && GET_CODE (PATTERN (insn)) != CLOBBER
4175 && !DEBUG_INSN_P (insn))
4177 if (reload_completed)
4178 PUT_MODE (insn, clock_var > last_clock_var ? TImode : VOIDmode);
4179 last_clock_var = clock_var;
4182 if (nonscheduled_insns_begin != NULL_RTX)
4183 /* Indicate to debug counters that INSN is scheduled. */
4184 nonscheduled_insns_begin = insn;
4189 /* Functions for handling of notes. */
4191 /* Add note list that ends on FROM_END to the end of TO_ENDP. */
4193 concat_note_lists (rtx_insn *from_end, rtx_insn **to_endp)
4195 rtx_insn *from_start;
4197 /* It's easy when have nothing to concat. */
4198 if (from_end == NULL)
4201 /* It's also easy when destination is empty. */
4202 if (*to_endp == NULL)
4204 *to_endp = from_end;
4208 from_start = from_end;
4209 while (PREV_INSN (from_start) != NULL)
4210 from_start = PREV_INSN (from_start);
4212 SET_PREV_INSN (from_start) = *to_endp;
4213 SET_NEXT_INSN (*to_endp) = from_start;
4214 *to_endp = from_end;
4217 /* Delete notes between HEAD and TAIL and put them in the chain
4218 of notes ended by NOTE_LIST. */
4220 remove_notes (rtx_insn *head, rtx_insn *tail)
4222 rtx_insn *next_tail, *insn, *next;
4225 if (head == tail && !INSN_P (head))
4228 next_tail = NEXT_INSN (tail);
4229 for (insn = head; insn != next_tail; insn = next)
4231 next = NEXT_INSN (insn);
4235 switch (NOTE_KIND (insn))
4237 case NOTE_INSN_BASIC_BLOCK:
4240 case NOTE_INSN_EPILOGUE_BEG:
4244 add_reg_note (next, REG_SAVE_NOTE,
4245 GEN_INT (NOTE_INSN_EPILOGUE_BEG));
4253 /* Add the note to list that ends at NOTE_LIST. */
4254 SET_PREV_INSN (insn) = note_list;
4255 SET_NEXT_INSN (insn) = NULL_RTX;
4257 SET_NEXT_INSN (note_list) = insn;
4262 gcc_assert ((sel_sched_p () || insn != tail) && insn != head);
4266 /* A structure to record enough data to allow us to backtrack the scheduler to
4267 a previous state. */
4268 struct haifa_saved_data
4270 /* Next entry on the list. */
4271 struct haifa_saved_data *next;
4273 /* Backtracking is associated with scheduling insns that have delay slots.
4274 DELAY_PAIR points to the structure that contains the insns involved, and
4275 the number of cycles between them. */
4276 struct delay_pair *delay_pair;
4278 /* Data used by the frontend (e.g. sched-ebb or sched-rgn). */
4279 void *fe_saved_data;
4280 /* Data used by the backend. */
4281 void *be_saved_data;
4283 /* Copies of global state. */
4284 int clock_var, last_clock_var;
4285 struct ready_list ready;
4288 rtx_insn *last_scheduled_insn;
4289 rtx_insn *last_nondebug_scheduled_insn;
4290 rtx_insn *nonscheduled_insns_begin;
4291 int cycle_issued_insns;
4293 /* Copies of state used in the inner loop of schedule_block. */
4294 struct sched_block_state sched_block;
4296 /* We don't need to save q_ptr, as its value is arbitrary and we can set it
4297 to 0 when restoring. */
4299 rtx_insn_list **insn_queue;
4301 /* Describe pattern replacements that occurred since this backtrack point
4303 vec<dep_t> replacement_deps;
4304 vec<int> replace_apply;
4306 /* A copy of the next-cycle replacement vectors at the time of the backtrack
4308 vec<dep_t> next_cycle_deps;
4309 vec<int> next_cycle_apply;
4312 /* A record, in reverse order, of all scheduled insns which have delay slots
4313 and may require backtracking. */
4314 static struct haifa_saved_data *backtrack_queue;
4316 /* For every dependency of INSN, set the FEEDS_BACKTRACK_INSN bit according
4319 mark_backtrack_feeds (rtx_insn *insn, int set_p)
4321 sd_iterator_def sd_it;
4323 FOR_EACH_DEP (insn, SD_LIST_HARD_BACK, sd_it, dep)
4325 FEEDS_BACKTRACK_INSN (DEP_PRO (dep)) = set_p;
4329 /* Save the current scheduler state so that we can backtrack to it
4330 later if necessary. PAIR gives the insns that make it necessary to
4331 save this point. SCHED_BLOCK is the local state of schedule_block
4332 that need to be saved. */
4334 save_backtrack_point (struct delay_pair *pair,
4335 struct sched_block_state sched_block)
4338 struct haifa_saved_data *save = XNEW (struct haifa_saved_data);
4340 save->curr_state = xmalloc (dfa_state_size);
4341 memcpy (save->curr_state, curr_state, dfa_state_size);
4343 save->ready.first = ready.first;
4344 save->ready.n_ready = ready.n_ready;
4345 save->ready.n_debug = ready.n_debug;
4346 save->ready.veclen = ready.veclen;
4347 save->ready.vec = XNEWVEC (rtx_insn *, ready.veclen);
4348 memcpy (save->ready.vec, ready.vec, ready.veclen * sizeof (rtx));
4350 save->insn_queue = XNEWVEC (rtx_insn_list *, max_insn_queue_index + 1);
4351 save->q_size = q_size;
4352 for (i = 0; i <= max_insn_queue_index; i++)
4354 int q = NEXT_Q_AFTER (q_ptr, i);
4355 save->insn_queue[i] = copy_INSN_LIST (insn_queue[q]);
4358 save->clock_var = clock_var;
4359 save->last_clock_var = last_clock_var;
4360 save->cycle_issued_insns = cycle_issued_insns;
4361 save->last_scheduled_insn = last_scheduled_insn;
4362 save->last_nondebug_scheduled_insn = last_nondebug_scheduled_insn;
4363 save->nonscheduled_insns_begin = nonscheduled_insns_begin;
4365 save->sched_block = sched_block;
4367 save->replacement_deps.create (0);
4368 save->replace_apply.create (0);
4369 save->next_cycle_deps = next_cycle_replace_deps.copy ();
4370 save->next_cycle_apply = next_cycle_apply.copy ();
4372 if (current_sched_info->save_state)
4373 save->fe_saved_data = (*current_sched_info->save_state) ();
4375 if (targetm.sched.alloc_sched_context)
4377 save->be_saved_data = targetm.sched.alloc_sched_context ();
4378 targetm.sched.init_sched_context (save->be_saved_data, false);
4381 save->be_saved_data = NULL;
4383 save->delay_pair = pair;
4385 save->next = backtrack_queue;
4386 backtrack_queue = save;
4390 mark_backtrack_feeds (pair->i2, 1);
4391 INSN_TICK (pair->i2) = INVALID_TICK;
4392 INSN_EXACT_TICK (pair->i2) = clock_var + pair_delay (pair);
4393 SHADOW_P (pair->i2) = pair->stages == 0;
4394 pair = pair->next_same_i1;
4398 /* Walk the ready list and all queues. If any insns have unresolved backwards
4399 dependencies, these must be cancelled deps, broken by predication. Set or
4400 clear (depending on SET) the DEP_CANCELLED bit in DEP_STATUS. */
4403 toggle_cancelled_flags (bool set)
4406 sd_iterator_def sd_it;
4409 if (ready.n_ready > 0)
4411 rtx_insn **first = ready_lastpos (&ready);
4412 for (i = 0; i < ready.n_ready; i++)
4413 FOR_EACH_DEP (first[i], SD_LIST_BACK, sd_it, dep)
4414 if (!DEBUG_INSN_P (DEP_PRO (dep)))
4417 DEP_STATUS (dep) |= DEP_CANCELLED;
4419 DEP_STATUS (dep) &= ~DEP_CANCELLED;
4422 for (i = 0; i <= max_insn_queue_index; i++)
4424 int q = NEXT_Q_AFTER (q_ptr, i);
4425 rtx_insn_list *link;
4426 for (link = insn_queue[q]; link; link = link->next ())
4428 rtx_insn *insn = link->insn ();
4429 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
4430 if (!DEBUG_INSN_P (DEP_PRO (dep)))
4433 DEP_STATUS (dep) |= DEP_CANCELLED;
4435 DEP_STATUS (dep) &= ~DEP_CANCELLED;
4441 /* Undo the replacements that have occurred after backtrack point SAVE
4444 undo_replacements_for_backtrack (struct haifa_saved_data *save)
4446 while (!save->replacement_deps.is_empty ())
4448 dep_t dep = save->replacement_deps.pop ();
4449 int apply_p = save->replace_apply.pop ();
4452 restore_pattern (dep, true);
4454 apply_replacement (dep, true);
4456 save->replacement_deps.release ();
4457 save->replace_apply.release ();
4460 /* Pop entries from the SCHEDULED_INSNS vector up to and including INSN.
4461 Restore their dependencies to an unresolved state, and mark them as
4465 unschedule_insns_until (rtx_insn *insn)
4467 auto_vec<rtx_insn *> recompute_vec;
4469 /* Make two passes over the insns to be unscheduled. First, we clear out
4470 dependencies and other trivial bookkeeping. */
4474 sd_iterator_def sd_it;
4477 last = scheduled_insns.pop ();
4479 /* This will be changed by restore_backtrack_point if the insn is in
4481 QUEUE_INDEX (last) = QUEUE_NOWHERE;
4483 INSN_TICK (last) = INVALID_TICK;
4485 if (modulo_ii > 0 && INSN_UID (last) < modulo_iter0_max_uid)
4486 modulo_insns_scheduled--;
4488 for (sd_it = sd_iterator_start (last, SD_LIST_RES_FORW);
4489 sd_iterator_cond (&sd_it, &dep);)
4491 rtx_insn *con = DEP_CON (dep);
4492 sd_unresolve_dep (sd_it);
4493 if (!MUST_RECOMPUTE_SPEC_P (con))
4495 MUST_RECOMPUTE_SPEC_P (con) = 1;
4496 recompute_vec.safe_push (con);
4504 /* A second pass, to update ready and speculation status for insns
4505 depending on the unscheduled ones. The first pass must have
4506 popped the scheduled_insns vector up to the point where we
4507 restart scheduling, as recompute_todo_spec requires it to be
4509 while (!recompute_vec.is_empty ())
4513 con = recompute_vec.pop ();
4514 MUST_RECOMPUTE_SPEC_P (con) = 0;
4515 if (!sd_lists_empty_p (con, SD_LIST_HARD_BACK))
4517 TODO_SPEC (con) = HARD_DEP;
4518 INSN_TICK (con) = INVALID_TICK;
4519 if (PREDICATED_PAT (con) != NULL_RTX)
4520 haifa_change_pattern (con, ORIG_PAT (con));
4522 else if (QUEUE_INDEX (con) != QUEUE_SCHEDULED)
4523 TODO_SPEC (con) = recompute_todo_spec (con, true);
4527 /* Restore scheduler state from the topmost entry on the backtracking queue.
4528 PSCHED_BLOCK_P points to the local data of schedule_block that we must
4529 overwrite with the saved data.
4530 The caller must already have called unschedule_insns_until. */
4533 restore_last_backtrack_point (struct sched_block_state *psched_block)
4536 struct haifa_saved_data *save = backtrack_queue;
4538 backtrack_queue = save->next;
4540 if (current_sched_info->restore_state)
4541 (*current_sched_info->restore_state) (save->fe_saved_data);
4543 if (targetm.sched.alloc_sched_context)
4545 targetm.sched.set_sched_context (save->be_saved_data);
4546 targetm.sched.free_sched_context (save->be_saved_data);
4549 /* Do this first since it clobbers INSN_TICK of the involved
4551 undo_replacements_for_backtrack (save);
4553 /* Clear the QUEUE_INDEX of everything in the ready list or one
4555 if (ready.n_ready > 0)
4557 rtx_insn **first = ready_lastpos (&ready);
4558 for (i = 0; i < ready.n_ready; i++)
4560 rtx_insn *insn = first[i];
4561 QUEUE_INDEX (insn) = QUEUE_NOWHERE;
4562 INSN_TICK (insn) = INVALID_TICK;
4565 for (i = 0; i <= max_insn_queue_index; i++)
4567 int q = NEXT_Q_AFTER (q_ptr, i);
4569 for (rtx_insn_list *link = insn_queue[q]; link; link = link->next ())
4571 rtx_insn *x = link->insn ();
4572 QUEUE_INDEX (x) = QUEUE_NOWHERE;
4573 INSN_TICK (x) = INVALID_TICK;
4575 free_INSN_LIST_list (&insn_queue[q]);
4579 ready = save->ready;
4581 if (ready.n_ready > 0)
4583 rtx_insn **first = ready_lastpos (&ready);
4584 for (i = 0; i < ready.n_ready; i++)
4586 rtx_insn *insn = first[i];
4587 QUEUE_INDEX (insn) = QUEUE_READY;
4588 TODO_SPEC (insn) = recompute_todo_spec (insn, true);
4589 INSN_TICK (insn) = save->clock_var;
4594 q_size = save->q_size;
4595 for (i = 0; i <= max_insn_queue_index; i++)
4597 int q = NEXT_Q_AFTER (q_ptr, i);
4599 insn_queue[q] = save->insn_queue[q];
4601 for (rtx_insn_list *link = insn_queue[q]; link; link = link->next ())
4603 rtx_insn *x = link->insn ();
4604 QUEUE_INDEX (x) = i;
4605 TODO_SPEC (x) = recompute_todo_spec (x, true);
4606 INSN_TICK (x) = save->clock_var + i;
4609 free (save->insn_queue);
4611 toggle_cancelled_flags (true);
4613 clock_var = save->clock_var;
4614 last_clock_var = save->last_clock_var;
4615 cycle_issued_insns = save->cycle_issued_insns;
4616 last_scheduled_insn = save->last_scheduled_insn;
4617 last_nondebug_scheduled_insn = save->last_nondebug_scheduled_insn;
4618 nonscheduled_insns_begin = save->nonscheduled_insns_begin;
4620 *psched_block = save->sched_block;
4622 memcpy (curr_state, save->curr_state, dfa_state_size);
4623 free (save->curr_state);
4625 mark_backtrack_feeds (save->delay_pair->i2, 0);
4627 gcc_assert (next_cycle_replace_deps.is_empty ());
4628 next_cycle_replace_deps = save->next_cycle_deps.copy ();
4629 next_cycle_apply = save->next_cycle_apply.copy ();
4633 for (save = backtrack_queue; save; save = save->next)
4635 mark_backtrack_feeds (save->delay_pair->i2, 1);
4639 /* Discard all data associated with the topmost entry in the backtrack
4640 queue. If RESET_TICK is false, we just want to free the data. If true,
4641 we are doing this because we discovered a reason to backtrack. In the
4642 latter case, also reset the INSN_TICK for the shadow insn. */
4644 free_topmost_backtrack_point (bool reset_tick)
4646 struct haifa_saved_data *save = backtrack_queue;
4649 backtrack_queue = save->next;
4653 struct delay_pair *pair = save->delay_pair;
4656 INSN_TICK (pair->i2) = INVALID_TICK;
4657 INSN_EXACT_TICK (pair->i2) = INVALID_TICK;
4658 pair = pair->next_same_i1;
4660 undo_replacements_for_backtrack (save);
4664 save->replacement_deps.release ();
4665 save->replace_apply.release ();
4668 if (targetm.sched.free_sched_context)
4669 targetm.sched.free_sched_context (save->be_saved_data);
4670 if (current_sched_info->restore_state)
4671 free (save->fe_saved_data);
4672 for (i = 0; i <= max_insn_queue_index; i++)
4673 free_INSN_LIST_list (&save->insn_queue[i]);
4674 free (save->insn_queue);
4675 free (save->curr_state);
4676 free (save->ready.vec);
4680 /* Free the entire backtrack queue. */
4682 free_backtrack_queue (void)
4684 while (backtrack_queue)
4685 free_topmost_backtrack_point (false);
4688 /* Apply a replacement described by DESC. If IMMEDIATELY is false, we
4689 may have to postpone the replacement until the start of the next cycle,
4690 at which point we will be called again with IMMEDIATELY true. This is
4691 only done for machines which have instruction packets with explicit
4692 parallelism however. */
4694 apply_replacement (dep_t dep, bool immediately)
4696 struct dep_replacement *desc = DEP_REPLACE (dep);
4697 if (!immediately && targetm.sched.exposed_pipeline && reload_completed)
4699 next_cycle_replace_deps.safe_push (dep);
4700 next_cycle_apply.safe_push (1);
4706 if (QUEUE_INDEX (desc->insn) == QUEUE_SCHEDULED)
4709 if (sched_verbose >= 5)
4710 fprintf (sched_dump, "applying replacement for insn %d\n",
4711 INSN_UID (desc->insn));
4713 success = validate_change (desc->insn, desc->loc, desc->newval, 0);
4714 gcc_assert (success);
4716 update_insn_after_change (desc->insn);
4717 if ((TODO_SPEC (desc->insn) & (HARD_DEP | DEP_POSTPONED)) == 0)
4718 fix_tick_ready (desc->insn);
4720 if (backtrack_queue != NULL)
4722 backtrack_queue->replacement_deps.safe_push (dep);
4723 backtrack_queue->replace_apply.safe_push (1);
4728 /* We have determined that a pattern involved in DEP must be restored.
4729 If IMMEDIATELY is false, we may have to postpone the replacement
4730 until the start of the next cycle, at which point we will be called
4731 again with IMMEDIATELY true. */
4733 restore_pattern (dep_t dep, bool immediately)
4735 rtx_insn *next = DEP_CON (dep);
4736 int tick = INSN_TICK (next);
4738 /* If we already scheduled the insn, the modified version is
4740 if (QUEUE_INDEX (next) == QUEUE_SCHEDULED)
4743 if (!immediately && targetm.sched.exposed_pipeline && reload_completed)
4745 next_cycle_replace_deps.safe_push (dep);
4746 next_cycle_apply.safe_push (0);
4751 if (DEP_TYPE (dep) == REG_DEP_CONTROL)
4753 if (sched_verbose >= 5)
4754 fprintf (sched_dump, "restoring pattern for insn %d\n",
4756 haifa_change_pattern (next, ORIG_PAT (next));
4760 struct dep_replacement *desc = DEP_REPLACE (dep);
4763 if (sched_verbose >= 5)
4764 fprintf (sched_dump, "restoring pattern for insn %d\n",
4765 INSN_UID (desc->insn));
4766 tick = INSN_TICK (desc->insn);
4768 success = validate_change (desc->insn, desc->loc, desc->orig, 0);
4769 gcc_assert (success);
4770 update_insn_after_change (desc->insn);
4771 if (backtrack_queue != NULL)
4773 backtrack_queue->replacement_deps.safe_push (dep);
4774 backtrack_queue->replace_apply.safe_push (0);
4777 INSN_TICK (next) = tick;
4778 if (TODO_SPEC (next) == DEP_POSTPONED)
4781 if (sd_lists_empty_p (next, SD_LIST_BACK))
4782 TODO_SPEC (next) = 0;
4783 else if (!sd_lists_empty_p (next, SD_LIST_HARD_BACK))
4784 TODO_SPEC (next) = HARD_DEP;
4787 /* Perform pattern replacements that were queued up until the next
4790 perform_replacements_new_cycle (void)
4794 FOR_EACH_VEC_ELT (next_cycle_replace_deps, i, dep)
4796 int apply_p = next_cycle_apply[i];
4798 apply_replacement (dep, true);
4800 restore_pattern (dep, true);
4802 next_cycle_replace_deps.truncate (0);
4803 next_cycle_apply.truncate (0);
4806 /* Compute INSN_TICK_ESTIMATE for INSN. PROCESSED is a bitmap of
4807 instructions we've previously encountered, a set bit prevents
4808 recursion. BUDGET is a limit on how far ahead we look, it is
4809 reduced on recursive calls. Return true if we produced a good
4810 estimate, or false if we exceeded the budget. */
4812 estimate_insn_tick (bitmap processed, rtx_insn *insn, int budget)
4814 sd_iterator_def sd_it;
4816 int earliest = INSN_TICK (insn);
4818 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
4820 rtx_insn *pro = DEP_PRO (dep);
4823 if (DEP_STATUS (dep) & DEP_CANCELLED)
4826 if (QUEUE_INDEX (pro) == QUEUE_SCHEDULED)
4827 gcc_assert (INSN_TICK (pro) + dep_cost (dep) <= INSN_TICK (insn));
4830 int cost = dep_cost (dep);
4833 if (!bitmap_bit_p (processed, INSN_LUID (pro)))
4835 if (!estimate_insn_tick (processed, pro, budget - cost))
4838 gcc_assert (INSN_TICK_ESTIMATE (pro) != INVALID_TICK);
4839 t = INSN_TICK_ESTIMATE (pro) + cost;
4840 if (earliest == INVALID_TICK || t > earliest)
4844 bitmap_set_bit (processed, INSN_LUID (insn));
4845 INSN_TICK_ESTIMATE (insn) = earliest;
4849 /* Examine the pair of insns in P, and estimate (optimistically, assuming
4850 infinite resources) the cycle in which the delayed shadow can be issued.
4851 Return the number of cycles that must pass before the real insn can be
4852 issued in order to meet this constraint. */
4854 estimate_shadow_tick (struct delay_pair *p)
4856 bitmap_head processed;
4859 bitmap_initialize (&processed, 0);
4861 cutoff = !estimate_insn_tick (&processed, p->i2,
4862 max_insn_queue_index + pair_delay (p));
4863 bitmap_clear (&processed);
4865 return max_insn_queue_index;
4866 t = INSN_TICK_ESTIMATE (p->i2) - (clock_var + pair_delay (p) + 1);
4872 /* If INSN has no unresolved backwards dependencies, add it to the schedule and
4873 recursively resolve all its forward dependencies. */
4875 resolve_dependencies (rtx_insn *insn)
4877 sd_iterator_def sd_it;
4880 /* Don't use sd_lists_empty_p; it ignores debug insns. */
4881 if (DEPS_LIST_FIRST (INSN_HARD_BACK_DEPS (insn)) != NULL
4882 || DEPS_LIST_FIRST (INSN_SPEC_BACK_DEPS (insn)) != NULL)
4885 if (sched_verbose >= 4)
4886 fprintf (sched_dump, ";;\tquickly resolving %d\n", INSN_UID (insn));
4888 if (QUEUE_INDEX (insn) >= 0)
4889 queue_remove (insn);
4891 scheduled_insns.safe_push (insn);
4893 /* Update dependent instructions. */
4894 for (sd_it = sd_iterator_start (insn, SD_LIST_FORW);
4895 sd_iterator_cond (&sd_it, &dep);)
4897 rtx_insn *next = DEP_CON (dep);
4899 if (sched_verbose >= 4)
4900 fprintf (sched_dump, ";;\t\tdep %d against %d\n", INSN_UID (insn),
4903 /* Resolve the dependence between INSN and NEXT.
4904 sd_resolve_dep () moves current dep to another list thus
4905 advancing the iterator. */
4906 sd_resolve_dep (sd_it);
4908 if (!IS_SPECULATION_BRANCHY_CHECK_P (insn))
4910 resolve_dependencies (next);
4913 /* Check always has only one forward dependence (to the first insn in
4914 the recovery block), therefore, this will be executed only once. */
4916 gcc_assert (sd_lists_empty_p (insn, SD_LIST_FORW));
4922 /* Return the head and tail pointers of ebb starting at BEG and ending
4925 get_ebb_head_tail (basic_block beg, basic_block end,
4926 rtx_insn **headp, rtx_insn **tailp)
4928 rtx_insn *beg_head = BB_HEAD (beg);
4929 rtx_insn * beg_tail = BB_END (beg);
4930 rtx_insn * end_head = BB_HEAD (end);
4931 rtx_insn * end_tail = BB_END (end);
4933 /* Don't include any notes or labels at the beginning of the BEG
4934 basic block, or notes at the end of the END basic blocks. */
4936 if (LABEL_P (beg_head))
4937 beg_head = NEXT_INSN (beg_head);
4939 while (beg_head != beg_tail)
4940 if (NOTE_P (beg_head))
4941 beg_head = NEXT_INSN (beg_head);
4942 else if (DEBUG_INSN_P (beg_head))
4944 rtx_insn * note, *next;
4946 for (note = NEXT_INSN (beg_head);
4950 next = NEXT_INSN (note);
4953 if (sched_verbose >= 9)
4954 fprintf (sched_dump, "reorder %i\n", INSN_UID (note));
4956 reorder_insns_nobb (note, note, PREV_INSN (beg_head));
4958 if (BLOCK_FOR_INSN (note) != beg)
4959 df_insn_change_bb (note, beg);
4961 else if (!DEBUG_INSN_P (note))
4973 end_head = beg_head;
4974 else if (LABEL_P (end_head))
4975 end_head = NEXT_INSN (end_head);
4977 while (end_head != end_tail)
4978 if (NOTE_P (end_tail))
4979 end_tail = PREV_INSN (end_tail);
4980 else if (DEBUG_INSN_P (end_tail))
4982 rtx_insn * note, *prev;
4984 for (note = PREV_INSN (end_tail);
4988 prev = PREV_INSN (note);
4991 if (sched_verbose >= 9)
4992 fprintf (sched_dump, "reorder %i\n", INSN_UID (note));
4994 reorder_insns_nobb (note, note, end_tail);
4996 if (end_tail == BB_END (end))
4997 BB_END (end) = note;
4999 if (BLOCK_FOR_INSN (note) != end)
5000 df_insn_change_bb (note, end);
5002 else if (!DEBUG_INSN_P (note))
5014 /* Return nonzero if there are no real insns in the range [ HEAD, TAIL ]. */
5017 no_real_insns_p (const rtx_insn *head, const rtx_insn *tail)
5019 while (head != NEXT_INSN (tail))
5021 if (!NOTE_P (head) && !LABEL_P (head))
5023 head = NEXT_INSN (head);
5028 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
5029 previously found among the insns. Insert them just before HEAD. */
5031 restore_other_notes (rtx_insn *head, basic_block head_bb)
5035 rtx_insn *note_head = note_list;
5038 head_bb = BLOCK_FOR_INSN (head);
5040 head = NEXT_INSN (bb_note (head_bb));
5042 while (PREV_INSN (note_head))
5044 set_block_for_insn (note_head, head_bb);
5045 note_head = PREV_INSN (note_head);
5047 /* In the above cycle we've missed this note. */
5048 set_block_for_insn (note_head, head_bb);
5050 SET_PREV_INSN (note_head) = PREV_INSN (head);
5051 SET_NEXT_INSN (PREV_INSN (head)) = note_head;
5052 SET_PREV_INSN (head) = note_list;
5053 SET_NEXT_INSN (note_list) = head;
5055 if (BLOCK_FOR_INSN (head) != head_bb)
5056 BB_END (head_bb) = note_list;
5064 /* When we know we are going to discard the schedule due to a failed attempt
5065 at modulo scheduling, undo all replacements. */
5067 undo_all_replacements (void)
5072 FOR_EACH_VEC_ELT (scheduled_insns, i, insn)
5074 sd_iterator_def sd_it;
5077 /* See if we must undo a replacement. */
5078 for (sd_it = sd_iterator_start (insn, SD_LIST_RES_FORW);
5079 sd_iterator_cond (&sd_it, &dep); sd_iterator_next (&sd_it))
5081 struct dep_replacement *desc = DEP_REPLACE (dep);
5083 validate_change (desc->insn, desc->loc, desc->orig, 0);
5088 /* Return first non-scheduled insn in the current scheduling block.
5089 This is mostly used for debug-counter purposes. */
5091 first_nonscheduled_insn (void)
5093 rtx_insn *insn = (nonscheduled_insns_begin != NULL_RTX
5094 ? nonscheduled_insns_begin
5095 : current_sched_info->prev_head);
5099 insn = next_nonnote_nondebug_insn (insn);
5101 while (QUEUE_INDEX (insn) == QUEUE_SCHEDULED);
5106 /* Move insns that became ready to fire from queue to ready list. */
5109 queue_to_ready (struct ready_list *ready)
5112 rtx_insn_list *link;
5113 rtx_insn *skip_insn;
5115 q_ptr = NEXT_Q (q_ptr);
5117 if (dbg_cnt (sched_insn) == false)
5118 /* If debug counter is activated do not requeue the first
5119 nonscheduled insn. */
5120 skip_insn = first_nonscheduled_insn ();
5124 /* Add all pending insns that can be scheduled without stalls to the
5126 for (link = insn_queue[q_ptr]; link; link = link->next ())
5128 insn = link->insn ();
5131 if (sched_verbose >= 2)
5132 fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
5133 (*current_sched_info->print_insn) (insn, 0));
5135 /* If the ready list is full, delay the insn for 1 cycle.
5136 See the comment in schedule_block for the rationale. */
5137 if (!reload_completed
5138 && (ready->n_ready - ready->n_debug > MAX_SCHED_READY_INSNS
5139 || (sched_pressure == SCHED_PRESSURE_MODEL
5140 /* Limit pressure recalculations to MAX_SCHED_READY_INSNS
5141 instructions too. */
5142 && model_index (insn) > (model_curr_point
5143 + MAX_SCHED_READY_INSNS)))
5144 && !(sched_pressure == SCHED_PRESSURE_MODEL
5145 && model_curr_point < model_num_insns
5146 /* Always allow the next model instruction to issue. */
5147 && model_index (insn) == model_curr_point)
5148 && !SCHED_GROUP_P (insn)
5149 && insn != skip_insn)
5151 if (sched_verbose >= 2)
5152 fprintf (sched_dump, "keeping in queue, ready full\n");
5153 queue_insn (insn, 1, "ready full");
5157 ready_add (ready, insn, false);
5158 if (sched_verbose >= 2)
5159 fprintf (sched_dump, "moving to ready without stalls\n");
5162 free_INSN_LIST_list (&insn_queue[q_ptr]);
5164 /* If there are no ready insns, stall until one is ready and add all
5165 of the pending insns at that point to the ready list. */
5166 if (ready->n_ready == 0)
5170 for (stalls = 1; stalls <= max_insn_queue_index; stalls++)
5172 if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
5174 for (; link; link = link->next ())
5176 insn = link->insn ();
5179 if (sched_verbose >= 2)
5180 fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
5181 (*current_sched_info->print_insn) (insn, 0));
5183 ready_add (ready, insn, false);
5184 if (sched_verbose >= 2)
5185 fprintf (sched_dump, "moving to ready with %d stalls\n", stalls);
5187 free_INSN_LIST_list (&insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]);
5189 advance_one_cycle ();
5194 advance_one_cycle ();
5197 q_ptr = NEXT_Q_AFTER (q_ptr, stalls);
5198 clock_var += stalls;
5199 if (sched_verbose >= 2)
5200 fprintf (sched_dump, ";;\tAdvancing clock by %d cycle[s] to %d\n",
5205 /* Used by early_queue_to_ready. Determines whether it is "ok" to
5206 prematurely move INSN from the queue to the ready list. Currently,
5207 if a target defines the hook 'is_costly_dependence', this function
5208 uses the hook to check whether there exist any dependences which are
5209 considered costly by the target, between INSN and other insns that
5210 have already been scheduled. Dependences are checked up to Y cycles
5211 back, with default Y=1; The flag -fsched-stalled-insns-dep=Y allows
5212 controlling this value.
5213 (Other considerations could be taken into account instead (or in
5214 addition) depending on user flags and target hooks. */
5217 ok_for_early_queue_removal (rtx_insn *insn)
5219 if (targetm.sched.is_costly_dependence)
5222 int i = scheduled_insns.length ();
5223 for (n_cycles = flag_sched_stalled_insns_dep; n_cycles; n_cycles--)
5229 rtx_insn *prev_insn = scheduled_insns[i];
5231 if (!NOTE_P (prev_insn))
5235 dep = sd_find_dep_between (prev_insn, insn, true);
5239 cost = dep_cost (dep);
5241 if (targetm.sched.is_costly_dependence (dep, cost,
5242 flag_sched_stalled_insns_dep - n_cycles))
5247 if (GET_MODE (prev_insn) == TImode) /* end of dispatch group */
5260 /* Remove insns from the queue, before they become "ready" with respect
5261 to FU latency considerations. */
5264 early_queue_to_ready (state_t state, struct ready_list *ready)
5267 rtx_insn_list *link;
5268 rtx_insn_list *next_link;
5269 rtx_insn_list *prev_link;
5272 state_t temp_state = alloca (dfa_state_size);
5274 int insns_removed = 0;
5277 Flag '-fsched-stalled-insns=X' determines the aggressiveness of this
5280 X == 0: There is no limit on how many queued insns can be removed
5281 prematurely. (flag_sched_stalled_insns = -1).
5283 X >= 1: Only X queued insns can be removed prematurely in each
5284 invocation. (flag_sched_stalled_insns = X).
5286 Otherwise: Early queue removal is disabled.
5287 (flag_sched_stalled_insns = 0)
5290 if (! flag_sched_stalled_insns)
5293 for (stalls = 0; stalls <= max_insn_queue_index; stalls++)
5295 if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
5297 if (sched_verbose > 6)
5298 fprintf (sched_dump, ";; look at index %d + %d\n", q_ptr, stalls);
5303 next_link = link->next ();
5304 insn = link->insn ();
5305 if (insn && sched_verbose > 6)
5306 print_rtl_single (sched_dump, insn);
5308 memcpy (temp_state, state, dfa_state_size);
5309 if (recog_memoized (insn) < 0)
5310 /* non-negative to indicate that it's not ready
5311 to avoid infinite Q->R->Q->R... */
5314 cost = state_transition (temp_state, insn);
5316 if (sched_verbose >= 6)
5317 fprintf (sched_dump, "transition cost = %d\n", cost);
5319 move_to_ready = false;
5322 move_to_ready = ok_for_early_queue_removal (insn);
5323 if (move_to_ready == true)
5325 /* move from Q to R */
5327 ready_add (ready, insn, false);
5330 XEXP (prev_link, 1) = next_link;
5332 insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = next_link;
5334 free_INSN_LIST_node (link);
5336 if (sched_verbose >= 2)
5337 fprintf (sched_dump, ";;\t\tEarly Q-->Ready: insn %s\n",
5338 (*current_sched_info->print_insn) (insn, 0));
5341 if (insns_removed == flag_sched_stalled_insns)
5342 /* Remove no more than flag_sched_stalled_insns insns
5343 from Q at a time. */
5344 return insns_removed;
5348 if (move_to_ready == false)
5355 } /* for stalls.. */
5357 return insns_removed;
5361 /* Print the ready list for debugging purposes.
5362 If READY_TRY is non-zero then only print insns that max_issue
5365 debug_ready_list_1 (struct ready_list *ready, signed char *ready_try)
5370 if (ready->n_ready == 0)
5372 fprintf (sched_dump, "\n");
5376 p = ready_lastpos (ready);
5377 for (i = 0; i < ready->n_ready; i++)
5379 if (ready_try != NULL && ready_try[ready->n_ready - i - 1])
5382 fprintf (sched_dump, " %s:%d",
5383 (*current_sched_info->print_insn) (p[i], 0),
5385 if (sched_pressure != SCHED_PRESSURE_NONE)
5386 fprintf (sched_dump, "(cost=%d",
5387 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (p[i]));
5388 fprintf (sched_dump, ":prio=%d", INSN_PRIORITY (p[i]));
5389 if (INSN_TICK (p[i]) > clock_var)
5390 fprintf (sched_dump, ":delay=%d", INSN_TICK (p[i]) - clock_var);
5391 if (sched_pressure == SCHED_PRESSURE_MODEL)
5392 fprintf (sched_dump, ":idx=%d",
5393 model_index (p[i]));
5394 if (sched_pressure != SCHED_PRESSURE_NONE)
5395 fprintf (sched_dump, ")");
5397 fprintf (sched_dump, "\n");
5400 /* Print the ready list. Callable from debugger. */
5402 debug_ready_list (struct ready_list *ready)
5404 debug_ready_list_1 (ready, NULL);
5407 /* Search INSN for REG_SAVE_NOTE notes and convert them back into insn
5408 NOTEs. This is used for NOTE_INSN_EPILOGUE_BEG, so that sched-ebb
5409 replaces the epilogue note in the correct basic block. */
5411 reemit_notes (rtx_insn *insn)
5414 rtx_insn *last = insn;
5416 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
5418 if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
5420 enum insn_note note_type = (enum insn_note) INTVAL (XEXP (note, 0));
5422 last = emit_note_before (note_type, last);
5423 remove_note (insn, note);
5428 /* Move INSN. Reemit notes if needed. Update CFG, if needed. */
5430 move_insn (rtx_insn *insn, rtx_insn *last, rtx nt)
5432 if (PREV_INSN (insn) != last)
5438 bb = BLOCK_FOR_INSN (insn);
5440 /* BB_HEAD is either LABEL or NOTE. */
5441 gcc_assert (BB_HEAD (bb) != insn);
5443 if (BB_END (bb) == insn)
5444 /* If this is last instruction in BB, move end marker one
5447 /* Jumps are always placed at the end of basic block. */
5448 jump_p = control_flow_insn_p (insn);
5451 || ((common_sched_info->sched_pass_id == SCHED_RGN_PASS)
5452 && IS_SPECULATION_BRANCHY_CHECK_P (insn))
5453 || (common_sched_info->sched_pass_id
5454 == SCHED_EBB_PASS));
5456 gcc_assert (BLOCK_FOR_INSN (PREV_INSN (insn)) == bb);
5458 BB_END (bb) = PREV_INSN (insn);
5461 gcc_assert (BB_END (bb) != last);
5464 /* We move the block note along with jump. */
5468 note = NEXT_INSN (insn);
5469 while (NOTE_NOT_BB_P (note) && note != nt)
5470 note = NEXT_INSN (note);
5474 || BARRIER_P (note)))
5475 note = NEXT_INSN (note);
5477 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
5482 SET_NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (note);
5483 SET_PREV_INSN (NEXT_INSN (note)) = PREV_INSN (insn);
5485 SET_NEXT_INSN (note) = NEXT_INSN (last);
5486 SET_PREV_INSN (NEXT_INSN (last)) = note;
5488 SET_NEXT_INSN (last) = insn;
5489 SET_PREV_INSN (insn) = last;
5491 bb = BLOCK_FOR_INSN (last);
5495 fix_jump_move (insn);
5497 if (BLOCK_FOR_INSN (insn) != bb)
5498 move_block_after_check (insn);
5500 gcc_assert (BB_END (bb) == last);
5503 df_insn_change_bb (insn, bb);
5505 /* Update BB_END, if needed. */
5506 if (BB_END (bb) == last)
5510 SCHED_GROUP_P (insn) = 0;
5513 /* Return true if scheduling INSN will finish current clock cycle. */
5515 insn_finishes_cycle_p (rtx_insn *insn)
5517 if (SCHED_GROUP_P (insn))
5518 /* After issuing INSN, rest of the sched_group will be forced to issue
5519 in order. Don't make any plans for the rest of cycle. */
5522 /* Finishing the block will, apparently, finish the cycle. */
5523 if (current_sched_info->insn_finishes_block_p
5524 && current_sched_info->insn_finishes_block_p (insn))
5530 /* Helper for autopref_multipass_init. Given a SET in PAT and whether
5531 we're expecting a memory WRITE or not, check that the insn is relevant to
5532 the autoprefetcher modelling code. Return true iff that is the case.
5533 If it is relevant, record the base register of the memory op in BASE and
5534 the offset in OFFSET. */
5537 analyze_set_insn_for_autopref (rtx pat, bool write, rtx *base, int *offset)
5539 if (GET_CODE (pat) != SET)
5542 rtx mem = write ? SET_DEST (pat) : SET_SRC (pat);
5546 struct address_info info;
5547 decompose_mem_address (&info, mem);
5549 /* TODO: Currently only (base+const) addressing is supported. */
5550 if (info.base == NULL || !REG_P (*info.base)
5551 || (info.disp != NULL && !CONST_INT_P (*info.disp)))
5555 *offset = info.disp ? INTVAL (*info.disp) : 0;
5559 /* Functions to model cache auto-prefetcher.
5561 Some of the CPUs have cache auto-prefetcher, which /seems/ to initiate
5562 memory prefetches if it sees instructions with consequitive memory accesses
5563 in the instruction stream. Details of such hardware units are not published,
5564 so we can only guess what exactly is going on there.
5565 In the scheduler, we model abstract auto-prefetcher. If there are memory
5566 insns in the ready list (or the queue) that have same memory base, but
5567 different offsets, then we delay the insns with larger offsets until insns
5568 with smaller offsets get scheduled. If PARAM_SCHED_AUTOPREF_QUEUE_DEPTH
5569 is "1", then we look at the ready list; if it is N>1, then we also look
5570 through N-1 queue entries.
5571 If the param is N>=0, then rank_for_schedule will consider auto-prefetching
5572 among its heuristics.
5573 Param value of "-1" disables modelling of the auto-prefetcher. */
5575 /* Initialize autoprefetcher model data for INSN. */
5577 autopref_multipass_init (const rtx_insn *insn, int write)
5579 autopref_multipass_data_t data = &INSN_AUTOPREF_MULTIPASS_DATA (insn)[write];
5581 gcc_assert (data->status == AUTOPREF_MULTIPASS_DATA_UNINITIALIZED);
5582 data->base = NULL_RTX;
5583 data->min_offset = 0;
5584 data->max_offset = 0;
5585 data->multi_mem_insn_p = false;
5586 /* Set insn entry initialized, but not relevant for auto-prefetcher. */
5587 data->status = AUTOPREF_MULTIPASS_DATA_IRRELEVANT;
5589 rtx pat = PATTERN (insn);
5591 /* We have a multi-set insn like a load-multiple or store-multiple.
5592 We care about these as long as all the memory ops inside the PARALLEL
5593 have the same base register. We care about the minimum and maximum
5594 offsets from that base but don't check for the order of those offsets
5595 within the PARALLEL insn itself. */
5596 if (GET_CODE (pat) == PARALLEL)
5598 int n_elems = XVECLEN (pat, 0);
5601 rtx prev_base = NULL_RTX;
5605 for (i = 0; i < n_elems; i++)
5607 rtx set = XVECEXP (pat, 0, i);
5608 if (GET_CODE (set) != SET)
5611 rtx base = NULL_RTX;
5613 if (!analyze_set_insn_for_autopref (set, write, &base, &offset))
5619 min_offset = offset;
5620 max_offset = offset;
5622 /* Ensure that all memory operations in the PARALLEL use the same
5624 else if (REGNO (base) != REGNO (prev_base))
5628 min_offset = MIN (min_offset, offset);
5629 max_offset = MAX (max_offset, offset);
5633 /* If we reached here then we have a valid PARALLEL of multiple memory
5634 ops with prev_base as the base and min_offset and max_offset
5635 containing the offsets range. */
5636 gcc_assert (prev_base);
5637 data->base = prev_base;
5638 data->min_offset = min_offset;
5639 data->max_offset = max_offset;
5640 data->multi_mem_insn_p = true;
5641 data->status = AUTOPREF_MULTIPASS_DATA_NORMAL;
5646 /* Otherwise this is a single set memory operation. */
5647 rtx set = single_set (insn);
5648 if (set == NULL_RTX)
5651 if (!analyze_set_insn_for_autopref (set, write, &data->base,
5655 /* This insn is relevant for the auto-prefetcher.
5656 The base and offset fields will have been filled in the
5657 analyze_set_insn_for_autopref call above. */
5658 data->status = AUTOPREF_MULTIPASS_DATA_NORMAL;
5662 /* Helper for autopref_rank_for_schedule. Given the data of two
5663 insns relevant to the auto-prefetcher modelling code DATA1 and DATA2
5664 return their comparison result. Return 0 if there is no sensible
5665 ranking order for the two insns. */
5668 autopref_rank_data (autopref_multipass_data_t data1,
5669 autopref_multipass_data_t data2)
5671 /* Simple case when both insns are simple single memory ops. */
5672 if (!data1->multi_mem_insn_p && !data2->multi_mem_insn_p)
5673 return data1->min_offset - data2->min_offset;
5675 /* Two load/store multiple insns. Return 0 if the offset ranges
5676 overlap and the difference between the minimum offsets otherwise. */
5677 else if (data1->multi_mem_insn_p && data2->multi_mem_insn_p)
5679 int min1 = data1->min_offset;
5680 int max1 = data1->max_offset;
5681 int min2 = data2->min_offset;
5682 int max2 = data2->max_offset;
5684 if (max1 < min2 || min1 > max2)
5690 /* The other two cases is a pair of a load/store multiple and
5691 a simple memory op. Return 0 if the single op's offset is within the
5692 range of the multi-op insn and the difference between the single offset
5693 and the minimum offset of the multi-set insn otherwise. */
5694 else if (data1->multi_mem_insn_p && !data2->multi_mem_insn_p)
5696 int max1 = data1->max_offset;
5697 int min1 = data1->min_offset;
5699 if (data2->min_offset >= min1
5700 && data2->min_offset <= max1)
5703 return min1 - data2->min_offset;
5707 int max2 = data2->max_offset;
5708 int min2 = data2->min_offset;
5710 if (data1->min_offset >= min2
5711 && data1->min_offset <= max2)
5714 return data1->min_offset - min2;
5718 /* Helper function for rank_for_schedule sorting. */
5720 autopref_rank_for_schedule (const rtx_insn *insn1, const rtx_insn *insn2)
5722 for (int write = 0; write < 2; ++write)
5724 autopref_multipass_data_t data1
5725 = &INSN_AUTOPREF_MULTIPASS_DATA (insn1)[write];
5726 autopref_multipass_data_t data2
5727 = &INSN_AUTOPREF_MULTIPASS_DATA (insn2)[write];
5729 if (data1->status == AUTOPREF_MULTIPASS_DATA_UNINITIALIZED)
5730 autopref_multipass_init (insn1, write);
5731 if (data1->status == AUTOPREF_MULTIPASS_DATA_IRRELEVANT)
5734 if (data2->status == AUTOPREF_MULTIPASS_DATA_UNINITIALIZED)
5735 autopref_multipass_init (insn2, write);
5736 if (data2->status == AUTOPREF_MULTIPASS_DATA_IRRELEVANT)
5739 if (!rtx_equal_p (data1->base, data2->base))
5742 return autopref_rank_data (data1, data2);
5748 /* True if header of debug dump was printed. */
5749 static bool autopref_multipass_dfa_lookahead_guard_started_dump_p;
5751 /* Helper for autopref_multipass_dfa_lookahead_guard.
5752 Return "1" if INSN1 should be delayed in favor of INSN2. */
5754 autopref_multipass_dfa_lookahead_guard_1 (const rtx_insn *insn1,
5755 const rtx_insn *insn2, int write)
5757 autopref_multipass_data_t data1
5758 = &INSN_AUTOPREF_MULTIPASS_DATA (insn1)[write];
5759 autopref_multipass_data_t data2
5760 = &INSN_AUTOPREF_MULTIPASS_DATA (insn2)[write];
5762 if (data2->status == AUTOPREF_MULTIPASS_DATA_UNINITIALIZED)
5763 autopref_multipass_init (insn2, write);
5764 if (data2->status == AUTOPREF_MULTIPASS_DATA_IRRELEVANT)
5767 if (rtx_equal_p (data1->base, data2->base)
5768 && autopref_rank_data (data1, data2) > 0)
5770 if (sched_verbose >= 2)
5772 if (!autopref_multipass_dfa_lookahead_guard_started_dump_p)
5774 fprintf (sched_dump,
5775 ";;\t\tnot trying in max_issue due to autoprefetch "
5777 autopref_multipass_dfa_lookahead_guard_started_dump_p = true;
5780 fprintf (sched_dump, " %d(%d)", INSN_UID (insn1), INSN_UID (insn2));
5791 We could have also hooked autoprefetcher model into
5792 first_cycle_multipass_backtrack / first_cycle_multipass_issue hooks
5793 to enable intelligent selection of "[r1+0]=r2; [r1+4]=r3" on the same cycle
5794 (e.g., once "[r1+0]=r2" is issued in max_issue(), "[r1+4]=r3" gets
5795 unblocked). We don't bother about this yet because target of interest
5796 (ARM Cortex-A15) can issue only 1 memory operation per cycle. */
5798 /* Implementation of first_cycle_multipass_dfa_lookahead_guard hook.
5799 Return "1" if INSN1 should not be considered in max_issue due to
5800 auto-prefetcher considerations. */
5802 autopref_multipass_dfa_lookahead_guard (rtx_insn *insn1, int ready_index)
5806 if (PARAM_VALUE (PARAM_SCHED_AUTOPREF_QUEUE_DEPTH) <= 0)
5809 if (sched_verbose >= 2 && ready_index == 0)
5810 autopref_multipass_dfa_lookahead_guard_started_dump_p = false;
5812 for (int write = 0; write < 2; ++write)
5814 autopref_multipass_data_t data1
5815 = &INSN_AUTOPREF_MULTIPASS_DATA (insn1)[write];
5817 if (data1->status == AUTOPREF_MULTIPASS_DATA_UNINITIALIZED)
5818 autopref_multipass_init (insn1, write);
5819 if (data1->status == AUTOPREF_MULTIPASS_DATA_IRRELEVANT)
5822 if (ready_index == 0
5823 && data1->status == AUTOPREF_MULTIPASS_DATA_DONT_DELAY)
5824 /* We allow only a single delay on priviledged instructions.
5825 Doing otherwise would cause infinite loop. */
5827 if (sched_verbose >= 2)
5829 if (!autopref_multipass_dfa_lookahead_guard_started_dump_p)
5831 fprintf (sched_dump,
5832 ";;\t\tnot trying in max_issue due to autoprefetch "
5834 autopref_multipass_dfa_lookahead_guard_started_dump_p = true;
5837 fprintf (sched_dump, " *%d*", INSN_UID (insn1));
5842 for (int i2 = 0; i2 < ready.n_ready; ++i2)
5844 rtx_insn *insn2 = get_ready_element (i2);
5847 r = autopref_multipass_dfa_lookahead_guard_1 (insn1, insn2, write);
5850 if (ready_index == 0)
5853 data1->status = AUTOPREF_MULTIPASS_DATA_DONT_DELAY;
5859 if (PARAM_VALUE (PARAM_SCHED_AUTOPREF_QUEUE_DEPTH) == 1)
5862 /* Everything from the current queue slot should have been moved to
5864 gcc_assert (insn_queue[NEXT_Q_AFTER (q_ptr, 0)] == NULL_RTX);
5866 int n_stalls = PARAM_VALUE (PARAM_SCHED_AUTOPREF_QUEUE_DEPTH) - 1;
5867 if (n_stalls > max_insn_queue_index)
5868 n_stalls = max_insn_queue_index;
5870 for (int stalls = 1; stalls <= n_stalls; ++stalls)
5872 for (rtx_insn_list *link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)];
5874 link = link->next ())
5876 rtx_insn *insn2 = link->insn ();
5877 r = autopref_multipass_dfa_lookahead_guard_1 (insn1, insn2,
5881 /* Queue INSN1 until INSN2 can issue. */
5883 if (ready_index == 0)
5884 data1->status = AUTOPREF_MULTIPASS_DATA_DONT_DELAY;
5892 if (sched_verbose >= 2
5893 && autopref_multipass_dfa_lookahead_guard_started_dump_p
5894 && (ready_index == ready.n_ready - 1 || r < 0))
5895 /* This does not /always/ trigger. We don't output EOL if the last
5896 insn is not recognized (INSN_CODE < 0) and lookahead_guard is not
5897 called. We can live with this. */
5898 fprintf (sched_dump, "\n");
5903 /* Define type for target data used in multipass scheduling. */
5904 #ifndef TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T
5905 # define TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T int
5907 typedef TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T first_cycle_multipass_data_t;
5909 /* The following structure describe an entry of the stack of choices. */
5912 /* Ordinal number of the issued insn in the ready queue. */
5914 /* The number of the rest insns whose issues we should try. */
5916 /* The number of issued essential insns. */
5918 /* State after issuing the insn. */
5920 /* Target-specific data. */
5921 first_cycle_multipass_data_t target_data;
5924 /* The following array is used to implement a stack of choices used in
5925 function max_issue. */
5926 static struct choice_entry *choice_stack;
5928 /* This holds the value of the target dfa_lookahead hook. */
5931 /* The following variable value is maximal number of tries of issuing
5932 insns for the first cycle multipass insn scheduling. We define
5933 this value as constant*(DFA_LOOKAHEAD**ISSUE_RATE). We would not
5934 need this constraint if all real insns (with non-negative codes)
5935 had reservations because in this case the algorithm complexity is
5936 O(DFA_LOOKAHEAD**ISSUE_RATE). Unfortunately, the dfa descriptions
5937 might be incomplete and such insn might occur. For such
5938 descriptions, the complexity of algorithm (without the constraint)
5939 could achieve DFA_LOOKAHEAD ** N , where N is the queue length. */
5940 static int max_lookahead_tries;
5942 /* The following function returns maximal (or close to maximal) number
5943 of insns which can be issued on the same cycle and one of which
5944 insns is insns with the best rank (the first insn in READY). To
5945 make this function tries different samples of ready insns. READY
5946 is current queue `ready'. Global array READY_TRY reflects what
5947 insns are already issued in this try. The function stops immediately,
5948 if it reached the such a solution, that all instruction can be issued.
5949 INDEX will contain index of the best insn in READY. The following
5950 function is used only for first cycle multipass scheduling.
5954 This function expects recognized insns only. All USEs,
5955 CLOBBERs, etc must be filtered elsewhere. */
5957 max_issue (struct ready_list *ready, int privileged_n, state_t state,
5958 bool first_cycle_insn_p, int *index)
5960 int n, i, all, n_ready, best, delay, tries_num;
5962 struct choice_entry *top;
5968 n_ready = ready->n_ready;
5969 gcc_assert (dfa_lookahead >= 1 && privileged_n >= 0
5970 && privileged_n <= n_ready);
5972 /* Init MAX_LOOKAHEAD_TRIES. */
5973 if (max_lookahead_tries == 0)
5975 max_lookahead_tries = 100;
5976 for (i = 0; i < issue_rate; i++)
5977 max_lookahead_tries *= dfa_lookahead;
5980 /* Init max_points. */
5981 more_issue = issue_rate - cycle_issued_insns;
5982 gcc_assert (more_issue >= 0);
5984 /* The number of the issued insns in the best solution. */
5989 /* Set initial state of the search. */
5990 memcpy (top->state, state, dfa_state_size);
5991 top->rest = dfa_lookahead;
5993 if (targetm.sched.first_cycle_multipass_begin)
5994 targetm.sched.first_cycle_multipass_begin (&top->target_data,
5996 first_cycle_insn_p);
5998 /* Count the number of the insns to search among. */
5999 for (all = i = 0; i < n_ready; i++)
6003 if (sched_verbose >= 2)
6005 fprintf (sched_dump, ";;\t\tmax_issue among %d insns:", all);
6006 debug_ready_list_1 (ready, ready_try);
6009 /* I is the index of the insn to try next. */
6014 if (/* If we've reached a dead end or searched enough of what we have
6017 /* or have nothing else to try... */
6019 /* or should not issue more. */
6020 || top->n >= more_issue)
6022 /* ??? (... || i == n_ready). */
6023 gcc_assert (i <= n_ready);
6025 /* We should not issue more than issue_rate instructions. */
6026 gcc_assert (top->n <= more_issue);
6028 if (top == choice_stack)
6031 if (best < top - choice_stack)
6036 /* Try to find issued privileged insn. */
6037 while (n && !ready_try[--n])
6041 if (/* If all insns are equally good... */
6043 /* Or a privileged insn will be issued. */
6045 /* Then we have a solution. */
6047 best = top - choice_stack;
6048 /* This is the index of the insn issued first in this
6050 *index = choice_stack [1].index;
6051 if (top->n == more_issue || best == all)
6056 /* Set ready-list index to point to the last insn
6057 ('i++' below will advance it to the next insn). */
6063 if (targetm.sched.first_cycle_multipass_backtrack)
6064 targetm.sched.first_cycle_multipass_backtrack (&top->target_data,
6065 ready_try, n_ready);
6068 memcpy (state, top->state, dfa_state_size);
6070 else if (!ready_try [i])
6073 if (tries_num > max_lookahead_tries)
6075 insn = ready_element (ready, i);
6076 delay = state_transition (state, insn);
6079 if (state_dead_lock_p (state)
6080 || insn_finishes_cycle_p (insn))
6081 /* We won't issue any more instructions in the next
6088 if (memcmp (top->state, state, dfa_state_size) != 0)
6091 /* Advance to the next choice_entry. */
6093 /* Initialize it. */
6094 top->rest = dfa_lookahead;
6097 memcpy (top->state, state, dfa_state_size);
6100 if (targetm.sched.first_cycle_multipass_issue)
6101 targetm.sched.first_cycle_multipass_issue (&top->target_data,
6111 /* Increase ready-list index. */
6115 if (targetm.sched.first_cycle_multipass_end)
6116 targetm.sched.first_cycle_multipass_end (best != 0
6117 ? &choice_stack[1].target_data
6120 /* Restore the original state of the DFA. */
6121 memcpy (state, choice_stack->state, dfa_state_size);
6126 /* The following function chooses insn from READY and modifies
6127 READY. The following function is used only for first
6128 cycle multipass scheduling.
6130 -1 if cycle should be advanced,
6131 0 if INSN_PTR is set to point to the desirable insn,
6132 1 if choose_ready () should be restarted without advancing the cycle. */
6134 choose_ready (struct ready_list *ready, bool first_cycle_insn_p,
6135 rtx_insn **insn_ptr)
6137 if (dbg_cnt (sched_insn) == false)
6139 if (nonscheduled_insns_begin == NULL_RTX)
6140 nonscheduled_insns_begin = current_sched_info->prev_head;
6142 rtx_insn *insn = first_nonscheduled_insn ();
6144 if (QUEUE_INDEX (insn) == QUEUE_READY)
6145 /* INSN is in the ready_list. */
6147 ready_remove_insn (insn);
6152 /* INSN is in the queue. Advance cycle to move it to the ready list. */
6153 gcc_assert (QUEUE_INDEX (insn) >= 0);
6157 if (dfa_lookahead <= 0 || SCHED_GROUP_P (ready_element (ready, 0))
6158 || DEBUG_INSN_P (ready_element (ready, 0)))
6160 if (targetm.sched.dispatch (NULL, IS_DISPATCH_ON))
6161 *insn_ptr = ready_remove_first_dispatch (ready);
6163 *insn_ptr = ready_remove_first (ready);
6169 /* Try to choose the best insn. */
6173 insn = ready_element (ready, 0);
6174 if (INSN_CODE (insn) < 0)
6176 *insn_ptr = ready_remove_first (ready);
6180 /* Filter the search space. */
6181 for (i = 0; i < ready->n_ready; i++)
6185 insn = ready_element (ready, i);
6187 /* If this insn is recognizable we should have already
6188 recognized it earlier.
6189 ??? Not very clear where this is supposed to be done.
6191 gcc_checking_assert (INSN_CODE (insn) >= 0
6192 || recog_memoized (insn) < 0);
6193 if (INSN_CODE (insn) < 0)
6195 /* Non-recognized insns at position 0 are handled above. */
6201 if (targetm.sched.first_cycle_multipass_dfa_lookahead_guard)
6204 = (targetm.sched.first_cycle_multipass_dfa_lookahead_guard
6207 if (ready_try[i] < 0)
6208 /* Queue instruction for several cycles.
6209 We need to restart choose_ready as we have changed
6212 change_queue_index (insn, -ready_try[i]);
6216 /* Make sure that we didn't end up with 0'th insn filtered out.
6217 Don't be tempted to make life easier for backends and just
6218 requeue 0'th insn if (ready_try[0] == 0) and restart
6219 choose_ready. Backends should be very considerate about
6220 requeueing instructions -- especially the highest priority
6221 one at position 0. */
6222 gcc_assert (ready_try[i] == 0 || i > 0);
6227 gcc_assert (ready_try[i] == 0);
6228 /* INSN made it through the scrutiny of filters! */
6231 if (max_issue (ready, 1, curr_state, first_cycle_insn_p, &index) == 0)
6233 *insn_ptr = ready_remove_first (ready);
6234 if (sched_verbose >= 4)
6235 fprintf (sched_dump, ";;\t\tChosen insn (but can't issue) : %s \n",
6236 (*current_sched_info->print_insn) (*insn_ptr, 0));
6241 if (sched_verbose >= 4)
6242 fprintf (sched_dump, ";;\t\tChosen insn : %s\n",
6243 (*current_sched_info->print_insn)
6244 (ready_element (ready, index), 0));
6246 *insn_ptr = ready_remove (ready, index);
6252 /* This function is called when we have successfully scheduled a
6253 block. It uses the schedule stored in the scheduled_insns vector
6254 to rearrange the RTL. PREV_HEAD is used as the anchor to which we
6255 append the scheduled insns; TAIL is the insn after the scheduled
6256 block. TARGET_BB is the argument passed to schedule_block. */
6259 commit_schedule (rtx_insn *prev_head, rtx_insn *tail, basic_block *target_bb)
6264 last_scheduled_insn = prev_head;
6266 scheduled_insns.iterate (i, &insn);
6269 if (control_flow_insn_p (last_scheduled_insn)
6270 || current_sched_info->advance_target_bb (*target_bb, insn))
6272 *target_bb = current_sched_info->advance_target_bb (*target_bb, 0);
6278 x = next_real_insn (last_scheduled_insn);
6280 dump_new_block_header (1, *target_bb, x, tail);
6283 last_scheduled_insn = bb_note (*target_bb);
6286 if (current_sched_info->begin_move_insn)
6287 (*current_sched_info->begin_move_insn) (insn, last_scheduled_insn);
6288 move_insn (insn, last_scheduled_insn,
6289 current_sched_info->next_tail);
6290 if (!DEBUG_INSN_P (insn))
6291 reemit_notes (insn);
6292 last_scheduled_insn = insn;
6295 scheduled_insns.truncate (0);
6298 /* Examine all insns on the ready list and queue those which can't be
6299 issued in this cycle. TEMP_STATE is temporary scheduler state we
6300 can use as scratch space. If FIRST_CYCLE_INSN_P is true, no insns
6301 have been issued for the current cycle, which means it is valid to
6302 issue an asm statement.
6304 If SHADOWS_ONLY_P is true, we eliminate all real insns and only
6305 leave those for which SHADOW_P is true. If MODULO_EPILOGUE is true,
6306 we only leave insns which have an INSN_EXACT_TICK. */
6309 prune_ready_list (state_t temp_state, bool first_cycle_insn_p,
6310 bool shadows_only_p, bool modulo_epilogue_p)
6313 bool sched_group_found = false;
6314 int min_cost_group = 1;
6319 for (i = 0; i < ready.n_ready; i++)
6321 rtx_insn *insn = ready_element (&ready, i);
6322 if (SCHED_GROUP_P (insn))
6324 sched_group_found = true;
6329 /* Make two passes if there's a SCHED_GROUP_P insn; make sure to handle
6330 such an insn first and note its cost, then schedule all other insns
6331 for one cycle later. */
6332 for (pass = sched_group_found ? 0 : 1; pass < 2; )
6334 int n = ready.n_ready;
6335 for (i = 0; i < n; i++)
6337 rtx_insn *insn = ready_element (&ready, i);
6339 const char *reason = "resource conflict";
6341 if (DEBUG_INSN_P (insn))
6344 if (sched_group_found && !SCHED_GROUP_P (insn))
6348 cost = min_cost_group;
6349 reason = "not in sched group";
6351 else if (modulo_epilogue_p
6352 && INSN_EXACT_TICK (insn) == INVALID_TICK)
6354 cost = max_insn_queue_index;
6355 reason = "not an epilogue insn";
6357 else if (shadows_only_p && !SHADOW_P (insn))
6360 reason = "not a shadow";
6362 else if (recog_memoized (insn) < 0)
6364 if (!first_cycle_insn_p
6365 && (GET_CODE (PATTERN (insn)) == ASM_INPUT
6366 || asm_noperands (PATTERN (insn)) >= 0))
6370 else if (sched_pressure != SCHED_PRESSURE_NONE)
6372 if (sched_pressure == SCHED_PRESSURE_MODEL
6373 && INSN_TICK (insn) <= clock_var)
6375 memcpy (temp_state, curr_state, dfa_state_size);
6376 if (state_transition (temp_state, insn) >= 0)
6377 INSN_TICK (insn) = clock_var + 1;
6387 struct delay_pair *delay_entry;
6389 = delay_htab->find_with_hash (insn,
6390 htab_hash_pointer (insn));
6391 while (delay_entry && delay_cost == 0)
6393 delay_cost = estimate_shadow_tick (delay_entry);
6394 if (delay_cost > max_insn_queue_index)
6395 delay_cost = max_insn_queue_index;
6396 delay_entry = delay_entry->next_same_i1;
6400 memcpy (temp_state, curr_state, dfa_state_size);
6401 cost = state_transition (temp_state, insn);
6406 if (cost < delay_cost)
6409 reason = "shadow tick";
6414 if (SCHED_GROUP_P (insn) && cost > min_cost_group)
6415 min_cost_group = cost;
6416 ready_remove (&ready, i);
6417 /* Normally we'd want to queue INSN for COST cycles. However,
6418 if SCHED_GROUP_P is set, then we must ensure that nothing
6419 else comes between INSN and its predecessor. If there is
6420 some other insn ready to fire on the next cycle, then that
6421 invariant would be broken.
6423 So when SCHED_GROUP_P is set, just queue this insn for a
6425 queue_insn (insn, SCHED_GROUP_P (insn) ? 1 : cost, reason);
6435 /* Called when we detect that the schedule is impossible. We examine the
6436 backtrack queue to find the earliest insn that caused this condition. */
6438 static struct haifa_saved_data *
6439 verify_shadows (void)
6441 struct haifa_saved_data *save, *earliest_fail = NULL;
6442 for (save = backtrack_queue; save; save = save->next)
6445 struct delay_pair *pair = save->delay_pair;
6446 rtx_insn *i1 = pair->i1;
6448 for (; pair; pair = pair->next_same_i1)
6450 rtx_insn *i2 = pair->i2;
6452 if (QUEUE_INDEX (i2) == QUEUE_SCHEDULED)
6455 t = INSN_TICK (i1) + pair_delay (pair);
6458 if (sched_verbose >= 2)
6459 fprintf (sched_dump,
6460 ";;\t\tfailed delay requirements for %d/%d (%d->%d)"
6462 INSN_UID (pair->i1), INSN_UID (pair->i2),
6463 INSN_TICK (pair->i1), INSN_EXACT_TICK (pair->i2));
6464 earliest_fail = save;
6467 if (QUEUE_INDEX (i2) >= 0)
6469 int queued_for = INSN_TICK (i2);
6473 if (sched_verbose >= 2)
6474 fprintf (sched_dump,
6475 ";;\t\tfailed delay requirements for %d/%d"
6476 " (%d->%d), queued too late\n",
6477 INSN_UID (pair->i1), INSN_UID (pair->i2),
6478 INSN_TICK (pair->i1), INSN_EXACT_TICK (pair->i2));
6479 earliest_fail = save;
6486 return earliest_fail;
6489 /* Print instructions together with useful scheduling information between
6490 HEAD and TAIL (inclusive). */
6492 dump_insn_stream (rtx_insn *head, rtx_insn *tail)
6494 fprintf (sched_dump, ";;\t| insn | prio |\n");
6496 rtx_insn *next_tail = NEXT_INSN (tail);
6497 for (rtx_insn *insn = head; insn != next_tail; insn = NEXT_INSN (insn))
6499 int priority = NOTE_P (insn) ? 0 : INSN_PRIORITY (insn);
6500 const char *pattern = (NOTE_P (insn)
6502 : str_pattern_slim (PATTERN (insn)));
6504 fprintf (sched_dump, ";;\t| %4d | %4d | %-30s ",
6505 INSN_UID (insn), priority, pattern);
6507 if (sched_verbose >= 4)
6509 if (NOTE_P (insn) || recog_memoized (insn) < 0)
6510 fprintf (sched_dump, "nothing");
6512 print_reservation (sched_dump, insn);
6514 fprintf (sched_dump, "\n");
6518 /* Use forward list scheduling to rearrange insns of block pointed to by
6519 TARGET_BB, possibly bringing insns from subsequent blocks in the same
6523 schedule_block (basic_block *target_bb, state_t init_state)
6526 bool success = modulo_ii == 0;
6527 struct sched_block_state ls;
6528 state_t temp_state = NULL; /* It is used for multipass scheduling. */
6529 int sort_p, advance, start_clock_var;
6531 /* Head/tail info for this block. */
6532 rtx_insn *prev_head = current_sched_info->prev_head;
6533 rtx_insn *next_tail = current_sched_info->next_tail;
6534 rtx_insn *head = NEXT_INSN (prev_head);
6535 rtx_insn *tail = PREV_INSN (next_tail);
6537 if ((current_sched_info->flags & DONT_BREAK_DEPENDENCIES) == 0
6538 && sched_pressure != SCHED_PRESSURE_MODEL && !sched_fusion)
6539 find_modifiable_mems (head, tail);
6541 /* We used to have code to avoid getting parameters moved from hard
6542 argument registers into pseudos.
6544 However, it was removed when it proved to be of marginal benefit
6545 and caused problems because schedule_block and compute_forward_dependences
6546 had different notions of what the "head" insn was. */
6548 gcc_assert (head != tail || INSN_P (head));
6550 haifa_recovery_bb_recently_added_p = false;
6552 backtrack_queue = NULL;
6557 dump_new_block_header (0, *target_bb, head, tail);
6559 if (sched_verbose >= 2)
6561 dump_insn_stream (head, tail);
6562 memset (&rank_for_schedule_stats, 0,
6563 sizeof (rank_for_schedule_stats));
6567 if (init_state == NULL)
6568 state_reset (curr_state);
6570 memcpy (curr_state, init_state, dfa_state_size);
6572 /* Clear the ready list. */
6573 ready.first = ready.veclen - 1;
6577 /* It is used for first cycle multipass scheduling. */
6578 temp_state = alloca (dfa_state_size);
6580 if (targetm.sched.init)
6581 targetm.sched.init (sched_dump, sched_verbose, ready.veclen);
6583 /* We start inserting insns after PREV_HEAD. */
6584 last_scheduled_insn = prev_head;
6585 last_nondebug_scheduled_insn = NULL;
6586 nonscheduled_insns_begin = NULL;
6588 gcc_assert ((NOTE_P (last_scheduled_insn)
6589 || DEBUG_INSN_P (last_scheduled_insn))
6590 && BLOCK_FOR_INSN (last_scheduled_insn) == *target_bb);
6592 /* Initialize INSN_QUEUE. Q_SIZE is the total number of insns in the
6597 insn_queue = XALLOCAVEC (rtx_insn_list *, max_insn_queue_index + 1);
6598 memset (insn_queue, 0, (max_insn_queue_index + 1) * sizeof (rtx));
6600 /* Start just before the beginning of time. */
6603 /* We need queue and ready lists and clock_var be initialized
6604 in try_ready () (which is called through init_ready_list ()). */
6605 (*current_sched_info->init_ready_list) ();
6608 sched_pressure_start_bb (*target_bb);
6610 /* The algorithm is O(n^2) in the number of ready insns at any given
6611 time in the worst case. Before reload we are more likely to have
6612 big lists so truncate them to a reasonable size. */
6613 if (!reload_completed
6614 && ready.n_ready - ready.n_debug > MAX_SCHED_READY_INSNS)
6616 ready_sort_debug (&ready);
6617 ready_sort_real (&ready);
6619 /* Find first free-standing insn past MAX_SCHED_READY_INSNS.
6620 If there are debug insns, we know they're first. */
6621 for (i = MAX_SCHED_READY_INSNS + ready.n_debug; i < ready.n_ready; i++)
6622 if (!SCHED_GROUP_P (ready_element (&ready, i)))
6625 if (sched_verbose >= 2)
6627 fprintf (sched_dump,
6628 ";;\t\tReady list on entry: %d insns: ", ready.n_ready);
6629 debug_ready_list (&ready);
6630 fprintf (sched_dump,
6631 ";;\t\t before reload => truncated to %d insns\n", i);
6634 /* Delay all insns past it for 1 cycle. If debug counter is
6635 activated make an exception for the insn right after
6636 nonscheduled_insns_begin. */
6638 rtx_insn *skip_insn;
6640 if (dbg_cnt (sched_insn) == false)
6641 skip_insn = first_nonscheduled_insn ();
6645 while (i < ready.n_ready)
6649 insn = ready_remove (&ready, i);
6651 if (insn != skip_insn)
6652 queue_insn (insn, 1, "list truncated");
6655 ready_add (&ready, skip_insn, true);
6659 /* Now we can restore basic block notes and maintain precise cfg. */
6660 restore_bb_notes (*target_bb);
6662 last_clock_var = -1;
6666 gcc_assert (scheduled_insns.length () == 0);
6668 must_backtrack = false;
6669 modulo_insns_scheduled = 0;
6671 ls.modulo_epilogue = false;
6672 ls.first_cycle_insn_p = true;
6674 /* Loop until all the insns in BB are scheduled. */
6675 while ((*current_sched_info->schedule_more_p) ())
6677 perform_replacements_new_cycle ();
6680 start_clock_var = clock_var;
6684 advance_one_cycle ();
6686 /* Add to the ready list all pending insns that can be issued now.
6687 If there are no ready insns, increment clock until one
6688 is ready and add all pending insns at that point to the ready
6690 queue_to_ready (&ready);
6692 gcc_assert (ready.n_ready);
6694 if (sched_verbose >= 2)
6696 fprintf (sched_dump, ";;\t\tReady list after queue_to_ready:");
6697 debug_ready_list (&ready);
6699 advance -= clock_var - start_clock_var;
6701 while (advance > 0);
6703 if (ls.modulo_epilogue)
6705 int stage = clock_var / modulo_ii;
6706 if (stage > modulo_last_stage * 2 + 2)
6708 if (sched_verbose >= 2)
6709 fprintf (sched_dump,
6710 ";;\t\tmodulo scheduled succeeded at II %d\n",
6716 else if (modulo_ii > 0)
6718 int stage = clock_var / modulo_ii;
6719 if (stage > modulo_max_stages)
6721 if (sched_verbose >= 2)
6722 fprintf (sched_dump,
6723 ";;\t\tfailing schedule due to excessive stages\n");
6726 if (modulo_n_insns == modulo_insns_scheduled
6727 && stage > modulo_last_stage)
6729 if (sched_verbose >= 2)
6730 fprintf (sched_dump,
6731 ";;\t\tfound kernel after %d stages, II %d\n",
6733 ls.modulo_epilogue = true;
6737 prune_ready_list (temp_state, true, false, ls.modulo_epilogue);
6738 if (ready.n_ready == 0)
6743 ls.shadows_only_p = false;
6744 cycle_issued_insns = 0;
6745 ls.can_issue_more = issue_rate;
6752 if (sort_p && ready.n_ready > 0)
6754 /* Sort the ready list based on priority. This must be
6755 done every iteration through the loop, as schedule_insn
6756 may have readied additional insns that will not be
6757 sorted correctly. */
6758 ready_sort (&ready);
6760 if (sched_verbose >= 2)
6762 fprintf (sched_dump,
6763 ";;\t\tReady list after ready_sort: ");
6764 debug_ready_list (&ready);
6768 /* We don't want md sched reorder to even see debug isns, so put
6769 them out right away. */
6770 if (ready.n_ready && DEBUG_INSN_P (ready_element (&ready, 0))
6771 && (*current_sched_info->schedule_more_p) ())
6773 while (ready.n_ready && DEBUG_INSN_P (ready_element (&ready, 0)))
6775 rtx_insn *insn = ready_remove_first (&ready);
6776 gcc_assert (DEBUG_INSN_P (insn));
6777 (*current_sched_info->begin_schedule_ready) (insn);
6778 scheduled_insns.safe_push (insn);
6779 last_scheduled_insn = insn;
6780 advance = schedule_insn (insn);
6781 gcc_assert (advance == 0);
6782 if (ready.n_ready > 0)
6783 ready_sort (&ready);
6787 if (ls.first_cycle_insn_p && !ready.n_ready)
6790 resume_after_backtrack:
6791 /* Allow the target to reorder the list, typically for
6792 better instruction bundling. */
6794 && (ready.n_ready == 0
6795 || !SCHED_GROUP_P (ready_element (&ready, 0))))
6797 if (ls.first_cycle_insn_p && targetm.sched.reorder)
6799 = targetm.sched.reorder (sched_dump, sched_verbose,
6800 ready_lastpos (&ready),
6801 &ready.n_ready, clock_var);
6802 else if (!ls.first_cycle_insn_p && targetm.sched.reorder2)
6804 = targetm.sched.reorder2 (sched_dump, sched_verbose,
6806 ? ready_lastpos (&ready) : NULL,
6807 &ready.n_ready, clock_var);
6810 restart_choose_ready:
6811 if (sched_verbose >= 2)
6813 fprintf (sched_dump, ";;\tReady list (t = %3d): ",
6815 debug_ready_list (&ready);
6816 if (sched_pressure == SCHED_PRESSURE_WEIGHTED)
6817 print_curr_reg_pressure ();
6820 if (ready.n_ready == 0
6821 && ls.can_issue_more
6822 && reload_completed)
6824 /* Allow scheduling insns directly from the queue in case
6825 there's nothing better to do (ready list is empty) but
6826 there are still vacant dispatch slots in the current cycle. */
6827 if (sched_verbose >= 6)
6828 fprintf (sched_dump,";;\t\tSecond chance\n");
6829 memcpy (temp_state, curr_state, dfa_state_size);
6830 if (early_queue_to_ready (temp_state, &ready))
6831 ready_sort (&ready);
6834 if (ready.n_ready == 0
6835 || !ls.can_issue_more
6836 || state_dead_lock_p (curr_state)
6837 || !(*current_sched_info->schedule_more_p) ())
6840 /* Select and remove the insn from the ready list. */
6846 res = choose_ready (&ready, ls.first_cycle_insn_p, &insn);
6852 goto restart_choose_ready;
6854 gcc_assert (insn != NULL_RTX);
6857 insn = ready_remove_first (&ready);
6859 if (sched_pressure != SCHED_PRESSURE_NONE
6860 && INSN_TICK (insn) > clock_var)
6862 ready_add (&ready, insn, true);
6867 if (targetm.sched.dfa_new_cycle
6868 && targetm.sched.dfa_new_cycle (sched_dump, sched_verbose,
6869 insn, last_clock_var,
6870 clock_var, &sort_p))
6871 /* SORT_P is used by the target to override sorting
6872 of the ready list. This is needed when the target
6873 has modified its internal structures expecting that
6874 the insn will be issued next. As we need the insn
6875 to have the highest priority (so it will be returned by
6876 the ready_remove_first call above), we invoke
6877 ready_add (&ready, insn, true).
6878 But, still, there is one issue: INSN can be later
6879 discarded by scheduler's front end through
6880 current_sched_info->can_schedule_ready_p, hence, won't
6883 ready_add (&ready, insn, true);
6889 if (current_sched_info->can_schedule_ready_p
6890 && ! (*current_sched_info->can_schedule_ready_p) (insn))
6891 /* We normally get here only if we don't want to move
6892 insn from the split block. */
6894 TODO_SPEC (insn) = DEP_POSTPONED;
6895 goto restart_choose_ready;
6900 /* If this insn is the first part of a delay-slot pair, record a
6902 struct delay_pair *delay_entry;
6904 = delay_htab->find_with_hash (insn, htab_hash_pointer (insn));
6907 save_backtrack_point (delay_entry, ls);
6908 if (sched_verbose >= 2)
6909 fprintf (sched_dump, ";;\t\tsaving backtrack point\n");
6913 /* DECISION is made. */
6915 if (modulo_ii > 0 && INSN_UID (insn) < modulo_iter0_max_uid)
6917 modulo_insns_scheduled++;
6918 modulo_last_stage = clock_var / modulo_ii;
6920 if (TODO_SPEC (insn) & SPECULATIVE)
6921 generate_recovery_code (insn);
6923 if (targetm.sched.dispatch (NULL, IS_DISPATCH_ON))
6924 targetm.sched.dispatch_do (insn, ADD_TO_DISPATCH_WINDOW);
6926 /* Update counters, etc in the scheduler's front end. */
6927 (*current_sched_info->begin_schedule_ready) (insn);
6928 scheduled_insns.safe_push (insn);
6929 gcc_assert (NONDEBUG_INSN_P (insn));
6930 last_nondebug_scheduled_insn = last_scheduled_insn = insn;
6932 if (recog_memoized (insn) >= 0)
6934 memcpy (temp_state, curr_state, dfa_state_size);
6935 cost = state_transition (curr_state, insn);
6936 if (sched_pressure != SCHED_PRESSURE_WEIGHTED && !sched_fusion)
6937 gcc_assert (cost < 0);
6938 if (memcmp (temp_state, curr_state, dfa_state_size) != 0)
6939 cycle_issued_insns++;
6943 asm_p = (GET_CODE (PATTERN (insn)) == ASM_INPUT
6944 || asm_noperands (PATTERN (insn)) >= 0);
6946 if (targetm.sched.variable_issue)
6948 targetm.sched.variable_issue (sched_dump, sched_verbose,
6949 insn, ls.can_issue_more);
6950 /* A naked CLOBBER or USE generates no instruction, so do
6951 not count them against the issue rate. */
6952 else if (GET_CODE (PATTERN (insn)) != USE
6953 && GET_CODE (PATTERN (insn)) != CLOBBER)
6954 ls.can_issue_more--;
6955 advance = schedule_insn (insn);
6957 if (SHADOW_P (insn))
6958 ls.shadows_only_p = true;
6960 /* After issuing an asm insn we should start a new cycle. */
6961 if (advance == 0 && asm_p)
6970 ls.first_cycle_insn_p = false;
6971 if (ready.n_ready > 0)
6972 prune_ready_list (temp_state, false, ls.shadows_only_p,
6973 ls.modulo_epilogue);
6977 if (!must_backtrack)
6978 for (i = 0; i < ready.n_ready; i++)
6980 rtx_insn *insn = ready_element (&ready, i);
6981 if (INSN_EXACT_TICK (insn) == clock_var)
6983 must_backtrack = true;
6988 if (must_backtrack && modulo_ii > 0)
6990 if (modulo_backtracks_left == 0)
6992 modulo_backtracks_left--;
6994 while (must_backtrack)
6996 struct haifa_saved_data *failed;
6997 rtx_insn *failed_insn;
6999 must_backtrack = false;
7000 failed = verify_shadows ();
7001 gcc_assert (failed);
7003 failed_insn = failed->delay_pair->i1;
7004 /* Clear these queues. */
7005 perform_replacements_new_cycle ();
7006 toggle_cancelled_flags (false);
7007 unschedule_insns_until (failed_insn);
7008 while (failed != backtrack_queue)
7009 free_topmost_backtrack_point (true);
7010 restore_last_backtrack_point (&ls);
7011 if (sched_verbose >= 2)
7012 fprintf (sched_dump, ";;\t\trewind to cycle %d\n", clock_var);
7013 /* Delay by at least a cycle. This could cause additional
7015 queue_insn (failed_insn, 1, "backtracked");
7019 if (ready.n_ready > 0)
7020 goto resume_after_backtrack;
7023 if (clock_var == 0 && ls.first_cycle_insn_p)
7029 ls.first_cycle_insn_p = true;
7031 if (ls.modulo_epilogue)
7034 if (!ls.first_cycle_insn_p || advance)
7035 advance_one_cycle ();
7036 perform_replacements_new_cycle ();
7039 /* Once again, debug insn suckiness: they can be on the ready list
7040 even if they have unresolved dependencies. To make our view
7041 of the world consistent, remove such "ready" insns. */
7042 restart_debug_insn_loop:
7043 for (i = ready.n_ready - 1; i >= 0; i--)
7047 x = ready_element (&ready, i);
7048 if (DEPS_LIST_FIRST (INSN_HARD_BACK_DEPS (x)) != NULL
7049 || DEPS_LIST_FIRST (INSN_SPEC_BACK_DEPS (x)) != NULL)
7051 ready_remove (&ready, i);
7052 goto restart_debug_insn_loop;
7055 for (i = ready.n_ready - 1; i >= 0; i--)
7059 x = ready_element (&ready, i);
7060 resolve_dependencies (x);
7062 for (i = 0; i <= max_insn_queue_index; i++)
7064 rtx_insn_list *link;
7065 while ((link = insn_queue[i]) != NULL)
7067 rtx_insn *x = link->insn ();
7068 insn_queue[i] = link->next ();
7069 QUEUE_INDEX (x) = QUEUE_NOWHERE;
7070 free_INSN_LIST_node (link);
7071 resolve_dependencies (x);
7077 undo_all_replacements ();
7082 fprintf (sched_dump, ";;\tReady list (final): ");
7083 debug_ready_list (&ready);
7086 if (modulo_ii == 0 && current_sched_info->queue_must_finish_empty)
7087 /* Sanity check -- queue must be empty now. Meaningless if region has
7089 gcc_assert (!q_size && !ready.n_ready && !ready.n_debug);
7090 else if (modulo_ii == 0)
7092 /* We must maintain QUEUE_INDEX between blocks in region. */
7093 for (i = ready.n_ready - 1; i >= 0; i--)
7097 x = ready_element (&ready, i);
7098 QUEUE_INDEX (x) = QUEUE_NOWHERE;
7099 TODO_SPEC (x) = HARD_DEP;
7103 for (i = 0; i <= max_insn_queue_index; i++)
7105 rtx_insn_list *link;
7106 for (link = insn_queue[i]; link; link = link->next ())
7111 QUEUE_INDEX (x) = QUEUE_NOWHERE;
7112 TODO_SPEC (x) = HARD_DEP;
7114 free_INSN_LIST_list (&insn_queue[i]);
7118 if (sched_pressure == SCHED_PRESSURE_MODEL)
7119 model_end_schedule ();
7123 commit_schedule (prev_head, tail, target_bb);
7125 fprintf (sched_dump, ";; total time = %d\n", clock_var);
7128 last_scheduled_insn = tail;
7130 scheduled_insns.truncate (0);
7132 if (!current_sched_info->queue_must_finish_empty
7133 || haifa_recovery_bb_recently_added_p)
7135 /* INSN_TICK (minimum clock tick at which the insn becomes
7136 ready) may be not correct for the insn in the subsequent
7137 blocks of the region. We should use a correct value of
7138 `clock_var' or modify INSN_TICK. It is better to keep
7139 clock_var value equal to 0 at the start of a basic block.
7140 Therefore we modify INSN_TICK here. */
7141 fix_inter_tick (NEXT_INSN (prev_head), last_scheduled_insn);
7144 if (targetm.sched.finish)
7146 targetm.sched.finish (sched_dump, sched_verbose);
7147 /* Target might have added some instructions to the scheduled block
7148 in its md_finish () hook. These new insns don't have any data
7149 initialized and to identify them we extend h_i_d so that they'll
7151 sched_extend_luids ();
7154 /* Update head/tail boundaries. */
7155 head = NEXT_INSN (prev_head);
7156 tail = last_scheduled_insn;
7160 fprintf (sched_dump, ";; new head = %d\n;; new tail = %d\n",
7161 INSN_UID (head), INSN_UID (tail));
7163 if (sched_verbose >= 2)
7165 dump_insn_stream (head, tail);
7166 print_rank_for_schedule_stats (";; TOTAL ", &rank_for_schedule_stats,
7170 fprintf (sched_dump, "\n");
7173 head = restore_other_notes (head, NULL);
7175 current_sched_info->head = head;
7176 current_sched_info->tail = tail;
7178 free_backtrack_queue ();
7183 /* Set_priorities: compute priority of each insn in the block. */
7186 set_priorities (rtx_insn *head, rtx_insn *tail)
7190 int sched_max_insns_priority =
7191 current_sched_info->sched_max_insns_priority;
7192 rtx_insn *prev_head;
7194 if (head == tail && ! INSN_P (head))
7199 prev_head = PREV_INSN (head);
7200 for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
7206 (void) priority (insn);
7208 gcc_assert (INSN_PRIORITY_KNOWN (insn));
7210 sched_max_insns_priority = MAX (sched_max_insns_priority,
7211 INSN_PRIORITY (insn));
7214 current_sched_info->sched_max_insns_priority = sched_max_insns_priority;
7219 /* Set sched_dump and sched_verbose for the desired debugging output. */
7221 setup_sched_dump (void)
7223 sched_verbose = sched_verbose_param;
7224 sched_dump = dump_file;
7229 /* Allocate data for register pressure sensitive scheduling. */
7231 alloc_global_sched_pressure_data (void)
7233 if (sched_pressure != SCHED_PRESSURE_NONE)
7235 int i, max_regno = max_reg_num ();
7237 if (sched_dump != NULL)
7238 /* We need info about pseudos for rtl dumps about pseudo
7239 classes and costs. */
7240 regstat_init_n_sets_and_refs ();
7241 ira_set_pseudo_classes (true, sched_verbose ? sched_dump : NULL);
7242 sched_regno_pressure_class
7243 = (enum reg_class *) xmalloc (max_regno * sizeof (enum reg_class));
7244 for (i = 0; i < max_regno; i++)
7245 sched_regno_pressure_class[i]
7246 = (i < FIRST_PSEUDO_REGISTER
7247 ? ira_pressure_class_translate[REGNO_REG_CLASS (i)]
7248 : ira_pressure_class_translate[reg_allocno_class (i)]);
7249 curr_reg_live = BITMAP_ALLOC (NULL);
7250 if (sched_pressure == SCHED_PRESSURE_WEIGHTED)
7252 saved_reg_live = BITMAP_ALLOC (NULL);
7253 region_ref_regs = BITMAP_ALLOC (NULL);
7256 /* Calculate number of CALL_USED_REGS in register classes that
7257 we calculate register pressure for. */
7258 for (int c = 0; c < ira_pressure_classes_num; ++c)
7260 enum reg_class cl = ira_pressure_classes[c];
7262 call_used_regs_num[cl] = 0;
7264 for (int i = 0; i < ira_class_hard_regs_num[cl]; ++i)
7265 if (call_used_regs[ira_class_hard_regs[cl][i]])
7266 ++call_used_regs_num[cl];
7271 /* Free data for register pressure sensitive scheduling. Also called
7272 from schedule_region when stopping sched-pressure early. */
7274 free_global_sched_pressure_data (void)
7276 if (sched_pressure != SCHED_PRESSURE_NONE)
7278 if (regstat_n_sets_and_refs != NULL)
7279 regstat_free_n_sets_and_refs ();
7280 if (sched_pressure == SCHED_PRESSURE_WEIGHTED)
7282 BITMAP_FREE (region_ref_regs);
7283 BITMAP_FREE (saved_reg_live);
7285 BITMAP_FREE (curr_reg_live);
7286 free (sched_regno_pressure_class);
7290 /* Initialize some global state for the scheduler. This function works
7291 with the common data shared between all the schedulers. It is called
7292 from the scheduler specific initialization routine. */
7297 /* Disable speculative loads in their presence if cc0 defined. */
7299 flag_schedule_speculative_load = 0;
7301 if (targetm.sched.dispatch (NULL, IS_DISPATCH_ON))
7302 targetm.sched.dispatch_do (NULL, DISPATCH_INIT);
7304 if (live_range_shrinkage_p)
7305 sched_pressure = SCHED_PRESSURE_WEIGHTED;
7306 else if (flag_sched_pressure
7307 && !reload_completed
7308 && common_sched_info->sched_pass_id == SCHED_RGN_PASS)
7309 sched_pressure = ((enum sched_pressure_algorithm)
7310 PARAM_VALUE (PARAM_SCHED_PRESSURE_ALGORITHM));
7312 sched_pressure = SCHED_PRESSURE_NONE;
7314 if (sched_pressure != SCHED_PRESSURE_NONE)
7315 ira_setup_eliminable_regset ();
7317 /* Initialize SPEC_INFO. */
7318 if (targetm.sched.set_sched_flags)
7320 spec_info = &spec_info_var;
7321 targetm.sched.set_sched_flags (spec_info);
7323 if (spec_info->mask != 0)
7325 spec_info->data_weakness_cutoff =
7326 (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF) * MAX_DEP_WEAK) / 100;
7327 spec_info->control_weakness_cutoff =
7328 (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF)
7329 * REG_BR_PROB_BASE) / 100;
7332 /* So we won't read anything accidentally. */
7337 /* So we won't read anything accidentally. */
7340 /* Initialize issue_rate. */
7341 if (targetm.sched.issue_rate)
7342 issue_rate = targetm.sched.issue_rate ();
7346 if (targetm.sched.first_cycle_multipass_dfa_lookahead
7347 /* Don't use max_issue with reg_pressure scheduling. Multipass
7348 scheduling and reg_pressure scheduling undo each other's decisions. */
7349 && sched_pressure == SCHED_PRESSURE_NONE)
7350 dfa_lookahead = targetm.sched.first_cycle_multipass_dfa_lookahead ();
7354 /* Set to "0" so that we recalculate. */
7355 max_lookahead_tries = 0;
7357 if (targetm.sched.init_dfa_pre_cycle_insn)
7358 targetm.sched.init_dfa_pre_cycle_insn ();
7360 if (targetm.sched.init_dfa_post_cycle_insn)
7361 targetm.sched.init_dfa_post_cycle_insn ();
7364 dfa_state_size = state_size ();
7366 init_alias_analysis ();
7369 df_set_flags (DF_LR_RUN_DCE);
7370 df_note_add_problem ();
7372 /* More problems needed for interloop dep calculation in SMS. */
7373 if (common_sched_info->sched_pass_id == SCHED_SMS_PASS)
7375 df_rd_add_problem ();
7376 df_chain_add_problem (DF_DU_CHAIN + DF_UD_CHAIN);
7381 /* Do not run DCE after reload, as this can kill nops inserted
7383 if (reload_completed)
7384 df_clear_flags (DF_LR_RUN_DCE);
7386 regstat_compute_calls_crossed ();
7388 if (targetm.sched.init_global)
7389 targetm.sched.init_global (sched_dump, sched_verbose, get_max_uid () + 1);
7391 alloc_global_sched_pressure_data ();
7393 curr_state = xmalloc (dfa_state_size);
7396 static void haifa_init_only_bb (basic_block, basic_block);
7398 /* Initialize data structures specific to the Haifa scheduler. */
7400 haifa_sched_init (void)
7402 setup_sched_dump ();
7405 scheduled_insns.create (0);
7407 if (spec_info != NULL)
7409 sched_deps_info->use_deps_list = 1;
7410 sched_deps_info->generate_spec_deps = 1;
7413 /* Initialize luids, dependency caches, target and h_i_d for the
7417 bbs.create (n_basic_blocks_for_fn (cfun));
7422 FOR_EACH_BB_FN (bb, cfun)
7423 bbs.quick_push (bb);
7424 sched_init_luids (bbs);
7425 sched_deps_init (true);
7426 sched_extend_target ();
7427 haifa_init_h_i_d (bbs);
7432 sched_init_only_bb = haifa_init_only_bb;
7433 sched_split_block = sched_split_block_1;
7434 sched_create_empty_bb = sched_create_empty_bb_1;
7435 haifa_recovery_bb_ever_added_p = false;
7437 nr_begin_data = nr_begin_control = nr_be_in_data = nr_be_in_control = 0;
7438 before_recovery = 0;
7444 /* Finish work with the data specific to the Haifa scheduler. */
7446 haifa_sched_finish (void)
7448 sched_create_empty_bb = NULL;
7449 sched_split_block = NULL;
7450 sched_init_only_bb = NULL;
7452 if (spec_info && spec_info->dump)
7454 char c = reload_completed ? 'a' : 'b';
7456 fprintf (spec_info->dump,
7457 ";; %s:\n", current_function_name ());
7459 fprintf (spec_info->dump,
7460 ";; Procedure %cr-begin-data-spec motions == %d\n",
7462 fprintf (spec_info->dump,
7463 ";; Procedure %cr-be-in-data-spec motions == %d\n",
7465 fprintf (spec_info->dump,
7466 ";; Procedure %cr-begin-control-spec motions == %d\n",
7467 c, nr_begin_control);
7468 fprintf (spec_info->dump,
7469 ";; Procedure %cr-be-in-control-spec motions == %d\n",
7470 c, nr_be_in_control);
7473 scheduled_insns.release ();
7475 /* Finalize h_i_d, dependency caches, and luids for the whole
7476 function. Target will be finalized in md_global_finish (). */
7477 sched_deps_finish ();
7478 sched_finish_luids ();
7479 current_sched_info = NULL;
7483 /* Free global data used during insn scheduling. This function works with
7484 the common data shared between the schedulers. */
7489 haifa_finish_h_i_d ();
7490 free_global_sched_pressure_data ();
7493 if (targetm.sched.finish_global)
7494 targetm.sched.finish_global (sched_dump, sched_verbose);
7496 end_alias_analysis ();
7498 regstat_free_calls_crossed ();
7503 /* Free all delay_pair structures that were recorded. */
7505 free_delay_pairs (void)
7509 delay_htab->empty ();
7510 delay_htab_i2->empty ();
7514 /* Fix INSN_TICKs of the instructions in the current block as well as
7515 INSN_TICKs of their dependents.
7516 HEAD and TAIL are the begin and the end of the current scheduled block. */
7518 fix_inter_tick (rtx_insn *head, rtx_insn *tail)
7520 /* Set of instructions with corrected INSN_TICK. */
7521 bitmap_head processed;
7522 /* ??? It is doubtful if we should assume that cycle advance happens on
7523 basic block boundaries. Basically insns that are unconditionally ready
7524 on the start of the block are more preferable then those which have
7525 a one cycle dependency over insn from the previous block. */
7526 int next_clock = clock_var + 1;
7528 bitmap_initialize (&processed, 0);
7530 /* Iterates over scheduled instructions and fix their INSN_TICKs and
7531 INSN_TICKs of dependent instructions, so that INSN_TICKs are consistent
7532 across different blocks. */
7533 for (tail = NEXT_INSN (tail); head != tail; head = NEXT_INSN (head))
7538 sd_iterator_def sd_it;
7541 tick = INSN_TICK (head);
7542 gcc_assert (tick >= MIN_TICK);
7544 /* Fix INSN_TICK of instruction from just scheduled block. */
7545 if (bitmap_set_bit (&processed, INSN_LUID (head)))
7549 if (tick < MIN_TICK)
7552 INSN_TICK (head) = tick;
7555 if (DEBUG_INSN_P (head))
7558 FOR_EACH_DEP (head, SD_LIST_RES_FORW, sd_it, dep)
7562 next = DEP_CON (dep);
7563 tick = INSN_TICK (next);
7565 if (tick != INVALID_TICK
7566 /* If NEXT has its INSN_TICK calculated, fix it.
7567 If not - it will be properly calculated from
7568 scratch later in fix_tick_ready. */
7569 && bitmap_set_bit (&processed, INSN_LUID (next)))
7573 if (tick < MIN_TICK)
7576 if (tick > INTER_TICK (next))
7577 INTER_TICK (next) = tick;
7579 tick = INTER_TICK (next);
7581 INSN_TICK (next) = tick;
7586 bitmap_clear (&processed);
7589 /* Check if NEXT is ready to be added to the ready or queue list.
7590 If "yes", add it to the proper list.
7592 -1 - is not ready yet,
7593 0 - added to the ready list,
7594 0 < N - queued for N cycles. */
7596 try_ready (rtx_insn *next)
7598 ds_t old_ts, new_ts;
7600 old_ts = TODO_SPEC (next);
7602 gcc_assert (!(old_ts & ~(SPECULATIVE | HARD_DEP | DEP_CONTROL | DEP_POSTPONED))
7603 && (old_ts == HARD_DEP
7604 || old_ts == DEP_POSTPONED
7605 || (old_ts & SPECULATIVE)
7606 || old_ts == DEP_CONTROL));
7608 new_ts = recompute_todo_spec (next, false);
7610 if (new_ts & (HARD_DEP | DEP_POSTPONED))
7611 gcc_assert (new_ts == old_ts
7612 && QUEUE_INDEX (next) == QUEUE_NOWHERE);
7613 else if (current_sched_info->new_ready)
7614 new_ts = current_sched_info->new_ready (next, new_ts);
7616 /* * if !(old_ts & SPECULATIVE) (e.g. HARD_DEP or 0), then insn might
7617 have its original pattern or changed (speculative) one. This is due
7618 to changing ebb in region scheduling.
7619 * But if (old_ts & SPECULATIVE), then we are pretty sure that insn
7620 has speculative pattern.
7622 We can't assert (!(new_ts & HARD_DEP) || new_ts == old_ts) here because
7623 control-speculative NEXT could have been discarded by sched-rgn.c
7624 (the same case as when discarded by can_schedule_ready_p ()). */
7626 if ((new_ts & SPECULATIVE)
7627 /* If (old_ts == new_ts), then (old_ts & SPECULATIVE) and we don't
7628 need to change anything. */
7629 && new_ts != old_ts)
7634 gcc_assert ((new_ts & SPECULATIVE) && !(new_ts & ~SPECULATIVE));
7636 res = haifa_speculate_insn (next, new_ts, &new_pat);
7641 /* It would be nice to change DEP_STATUS of all dependences,
7642 which have ((DEP_STATUS & SPECULATIVE) == new_ts) to HARD_DEP,
7643 so we won't reanalyze anything. */
7648 /* We follow the rule, that every speculative insn
7649 has non-null ORIG_PAT. */
7650 if (!ORIG_PAT (next))
7651 ORIG_PAT (next) = PATTERN (next);
7655 if (!ORIG_PAT (next))
7656 /* If we gonna to overwrite the original pattern of insn,
7658 ORIG_PAT (next) = PATTERN (next);
7660 res = haifa_change_pattern (next, new_pat);
7669 /* We need to restore pattern only if (new_ts == 0), because otherwise it is
7670 either correct (new_ts & SPECULATIVE),
7671 or we simply don't care (new_ts & HARD_DEP). */
7673 gcc_assert (!ORIG_PAT (next)
7674 || !IS_SPECULATION_BRANCHY_CHECK_P (next));
7676 TODO_SPEC (next) = new_ts;
7678 if (new_ts & (HARD_DEP | DEP_POSTPONED))
7680 /* We can't assert (QUEUE_INDEX (next) == QUEUE_NOWHERE) here because
7681 control-speculative NEXT could have been discarded by sched-rgn.c
7682 (the same case as when discarded by can_schedule_ready_p ()). */
7683 /*gcc_assert (QUEUE_INDEX (next) == QUEUE_NOWHERE);*/
7685 change_queue_index (next, QUEUE_NOWHERE);
7689 else if (!(new_ts & BEGIN_SPEC)
7690 && ORIG_PAT (next) && PREDICATED_PAT (next) == NULL_RTX
7691 && !IS_SPECULATION_CHECK_P (next))
7692 /* We should change pattern of every previously speculative
7693 instruction - and we determine if NEXT was speculative by using
7694 ORIG_PAT field. Except one case - speculation checks have ORIG_PAT
7695 pat too, so skip them. */
7697 bool success = haifa_change_pattern (next, ORIG_PAT (next));
7698 gcc_assert (success);
7699 ORIG_PAT (next) = 0;
7702 if (sched_verbose >= 2)
7704 fprintf (sched_dump, ";;\t\tdependencies resolved: insn %s",
7705 (*current_sched_info->print_insn) (next, 0));
7707 if (spec_info && spec_info->dump)
7709 if (new_ts & BEGIN_DATA)
7710 fprintf (spec_info->dump, "; data-spec;");
7711 if (new_ts & BEGIN_CONTROL)
7712 fprintf (spec_info->dump, "; control-spec;");
7713 if (new_ts & BE_IN_CONTROL)
7714 fprintf (spec_info->dump, "; in-control-spec;");
7716 if (TODO_SPEC (next) & DEP_CONTROL)
7717 fprintf (sched_dump, " predicated");
7718 fprintf (sched_dump, "\n");
7721 adjust_priority (next);
7723 return fix_tick_ready (next);
7726 /* Calculate INSN_TICK of NEXT and add it to either ready or queue list. */
7728 fix_tick_ready (rtx_insn *next)
7732 if (!DEBUG_INSN_P (next) && !sd_lists_empty_p (next, SD_LIST_RES_BACK))
7735 sd_iterator_def sd_it;
7738 tick = INSN_TICK (next);
7739 /* if tick is not equal to INVALID_TICK, then update
7740 INSN_TICK of NEXT with the most recent resolved dependence
7741 cost. Otherwise, recalculate from scratch. */
7742 full_p = (tick == INVALID_TICK);
7744 FOR_EACH_DEP (next, SD_LIST_RES_BACK, sd_it, dep)
7746 rtx_insn *pro = DEP_PRO (dep);
7749 gcc_assert (INSN_TICK (pro) >= MIN_TICK);
7751 tick1 = INSN_TICK (pro) + dep_cost (dep);
7762 INSN_TICK (next) = tick;
7764 delay = tick - clock_var;
7765 if (delay <= 0 || sched_pressure != SCHED_PRESSURE_NONE || sched_fusion)
7766 delay = QUEUE_READY;
7768 change_queue_index (next, delay);
7773 /* Move NEXT to the proper queue list with (DELAY >= 1),
7774 or add it to the ready list (DELAY == QUEUE_READY),
7775 or remove it from ready and queue lists at all (DELAY == QUEUE_NOWHERE). */
7777 change_queue_index (rtx_insn *next, int delay)
7779 int i = QUEUE_INDEX (next);
7781 gcc_assert (QUEUE_NOWHERE <= delay && delay <= max_insn_queue_index
7783 gcc_assert (i != QUEUE_SCHEDULED);
7785 if ((delay > 0 && NEXT_Q_AFTER (q_ptr, delay) == i)
7786 || (delay < 0 && delay == i))
7787 /* We have nothing to do. */
7790 /* Remove NEXT from wherever it is now. */
7791 if (i == QUEUE_READY)
7792 ready_remove_insn (next);
7794 queue_remove (next);
7796 /* Add it to the proper place. */
7797 if (delay == QUEUE_READY)
7798 ready_add (readyp, next, false);
7799 else if (delay >= 1)
7800 queue_insn (next, delay, "change queue index");
7802 if (sched_verbose >= 2)
7804 fprintf (sched_dump, ";;\t\ttick updated: insn %s",
7805 (*current_sched_info->print_insn) (next, 0));
7807 if (delay == QUEUE_READY)
7808 fprintf (sched_dump, " into ready\n");
7809 else if (delay >= 1)
7810 fprintf (sched_dump, " into queue with cost=%d\n", delay);
7812 fprintf (sched_dump, " removed from ready or queue lists\n");
7816 static int sched_ready_n_insns = -1;
7818 /* Initialize per region data structures. */
7820 sched_extend_ready_list (int new_sched_ready_n_insns)
7824 if (sched_ready_n_insns == -1)
7825 /* At the first call we need to initialize one more choice_stack
7829 sched_ready_n_insns = 0;
7830 scheduled_insns.reserve (new_sched_ready_n_insns);
7833 i = sched_ready_n_insns + 1;
7835 ready.veclen = new_sched_ready_n_insns + issue_rate;
7836 ready.vec = XRESIZEVEC (rtx_insn *, ready.vec, ready.veclen);
7838 gcc_assert (new_sched_ready_n_insns >= sched_ready_n_insns);
7840 ready_try = (signed char *) xrecalloc (ready_try, new_sched_ready_n_insns,
7841 sched_ready_n_insns,
7842 sizeof (*ready_try));
7844 /* We allocate +1 element to save initial state in the choice_stack[0]
7846 choice_stack = XRESIZEVEC (struct choice_entry, choice_stack,
7847 new_sched_ready_n_insns + 1);
7849 for (; i <= new_sched_ready_n_insns; i++)
7851 choice_stack[i].state = xmalloc (dfa_state_size);
7853 if (targetm.sched.first_cycle_multipass_init)
7854 targetm.sched.first_cycle_multipass_init (&(choice_stack[i]
7858 sched_ready_n_insns = new_sched_ready_n_insns;
7861 /* Free per region data structures. */
7863 sched_finish_ready_list (void)
7874 for (i = 0; i <= sched_ready_n_insns; i++)
7876 if (targetm.sched.first_cycle_multipass_fini)
7877 targetm.sched.first_cycle_multipass_fini (&(choice_stack[i]
7880 free (choice_stack [i].state);
7882 free (choice_stack);
7883 choice_stack = NULL;
7885 sched_ready_n_insns = -1;
7889 haifa_luid_for_non_insn (rtx x)
7891 gcc_assert (NOTE_P (x) || LABEL_P (x));
7896 /* Generates recovery code for INSN. */
7898 generate_recovery_code (rtx_insn *insn)
7900 if (TODO_SPEC (insn) & BEGIN_SPEC)
7901 begin_speculative_block (insn);
7903 /* Here we have insn with no dependencies to
7904 instructions other then CHECK_SPEC ones. */
7906 if (TODO_SPEC (insn) & BE_IN_SPEC)
7907 add_to_speculative_block (insn);
7911 Tries to add speculative dependencies of type FS between instructions
7912 in deps_list L and TWIN. */
7914 process_insn_forw_deps_be_in_spec (rtx_insn *insn, rtx_insn *twin, ds_t fs)
7916 sd_iterator_def sd_it;
7919 FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
7924 consumer = DEP_CON (dep);
7926 ds = DEP_STATUS (dep);
7928 if (/* If we want to create speculative dep. */
7930 /* And we can do that because this is a true dep. */
7931 && (ds & DEP_TYPES) == DEP_TRUE)
7933 gcc_assert (!(ds & BE_IN_SPEC));
7935 if (/* If this dep can be overcome with 'begin speculation'. */
7937 /* Then we have a choice: keep the dep 'begin speculative'
7938 or transform it into 'be in speculative'. */
7940 if (/* In try_ready we assert that if insn once became ready
7941 it can be removed from the ready (or queue) list only
7942 due to backend decision. Hence we can't let the
7943 probability of the speculative dep to decrease. */
7944 ds_weak (ds) <= ds_weak (fs))
7948 new_ds = (ds & ~BEGIN_SPEC) | fs;
7950 if (/* consumer can 'be in speculative'. */
7951 sched_insn_is_legitimate_for_speculation_p (consumer,
7953 /* Transform it to be in speculative. */
7958 /* Mark the dep as 'be in speculative'. */
7963 dep_def _new_dep, *new_dep = &_new_dep;
7965 init_dep_1 (new_dep, twin, consumer, DEP_TYPE (dep), ds);
7966 sd_add_dep (new_dep, false);
7971 /* Generates recovery code for BEGIN speculative INSN. */
7973 begin_speculative_block (rtx_insn *insn)
7975 if (TODO_SPEC (insn) & BEGIN_DATA)
7977 if (TODO_SPEC (insn) & BEGIN_CONTROL)
7980 create_check_block_twin (insn, false);
7982 TODO_SPEC (insn) &= ~BEGIN_SPEC;
7985 static void haifa_init_insn (rtx_insn *);
7987 /* Generates recovery code for BE_IN speculative INSN. */
7989 add_to_speculative_block (rtx_insn *insn)
7992 sd_iterator_def sd_it;
7994 rtx_insn_list *twins = NULL;
7995 rtx_vec_t priorities_roots;
7997 ts = TODO_SPEC (insn);
7998 gcc_assert (!(ts & ~BE_IN_SPEC));
8000 if (ts & BE_IN_DATA)
8002 if (ts & BE_IN_CONTROL)
8005 TODO_SPEC (insn) &= ~BE_IN_SPEC;
8006 gcc_assert (!TODO_SPEC (insn));
8008 DONE_SPEC (insn) |= ts;
8010 /* First we convert all simple checks to branchy. */
8011 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
8012 sd_iterator_cond (&sd_it, &dep);)
8014 rtx_insn *check = DEP_PRO (dep);
8016 if (IS_SPECULATION_SIMPLE_CHECK_P (check))
8018 create_check_block_twin (check, true);
8020 /* Restart search. */
8021 sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
8024 /* Continue search. */
8025 sd_iterator_next (&sd_it);
8028 priorities_roots.create (0);
8029 clear_priorities (insn, &priorities_roots);
8033 rtx_insn *check, *twin;
8036 /* Get the first backward dependency of INSN. */
8037 sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
8038 if (!sd_iterator_cond (&sd_it, &dep))
8039 /* INSN has no backward dependencies left. */
8042 gcc_assert ((DEP_STATUS (dep) & BEGIN_SPEC) == 0
8043 && (DEP_STATUS (dep) & BE_IN_SPEC) != 0
8044 && (DEP_STATUS (dep) & DEP_TYPES) == DEP_TRUE);
8046 check = DEP_PRO (dep);
8048 gcc_assert (!IS_SPECULATION_CHECK_P (check) && !ORIG_PAT (check)
8049 && QUEUE_INDEX (check) == QUEUE_NOWHERE);
8051 rec = BLOCK_FOR_INSN (check);
8053 twin = emit_insn_before (copy_insn (PATTERN (insn)), BB_END (rec));
8054 haifa_init_insn (twin);
8056 sd_copy_back_deps (twin, insn, true);
8058 if (sched_verbose && spec_info->dump)
8059 /* INSN_BB (insn) isn't determined for twin insns yet.
8060 So we can't use current_sched_info->print_insn. */
8061 fprintf (spec_info->dump, ";;\t\tGenerated twin insn : %d/rec%d\n",
8062 INSN_UID (twin), rec->index);
8064 twins = alloc_INSN_LIST (twin, twins);
8066 /* Add dependences between TWIN and all appropriate
8067 instructions from REC. */
8068 FOR_EACH_DEP (insn, SD_LIST_SPEC_BACK, sd_it, dep)
8070 rtx_insn *pro = DEP_PRO (dep);
8072 gcc_assert (DEP_TYPE (dep) == REG_DEP_TRUE);
8074 /* INSN might have dependencies from the instructions from
8075 several recovery blocks. At this iteration we process those
8076 producers that reside in REC. */
8077 if (BLOCK_FOR_INSN (pro) == rec)
8079 dep_def _new_dep, *new_dep = &_new_dep;
8081 init_dep (new_dep, pro, twin, REG_DEP_TRUE);
8082 sd_add_dep (new_dep, false);
8086 process_insn_forw_deps_be_in_spec (insn, twin, ts);
8088 /* Remove all dependencies between INSN and insns in REC. */
8089 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
8090 sd_iterator_cond (&sd_it, &dep);)
8092 rtx_insn *pro = DEP_PRO (dep);
8094 if (BLOCK_FOR_INSN (pro) == rec)
8095 sd_delete_dep (sd_it);
8097 sd_iterator_next (&sd_it);
8101 /* We couldn't have added the dependencies between INSN and TWINS earlier
8102 because that would make TWINS appear in the INSN_BACK_DEPS (INSN). */
8106 rtx_insn_list *next_node;
8108 twin = twins->insn ();
8111 dep_def _new_dep, *new_dep = &_new_dep;
8113 init_dep (new_dep, insn, twin, REG_DEP_OUTPUT);
8114 sd_add_dep (new_dep, false);
8117 next_node = twins->next ();
8118 free_INSN_LIST_node (twins);
8122 calc_priorities (priorities_roots);
8123 priorities_roots.release ();
8126 /* Extends and fills with zeros (only the new part) array pointed to by P. */
8128 xrecalloc (void *p, size_t new_nmemb, size_t old_nmemb, size_t size)
8130 gcc_assert (new_nmemb >= old_nmemb);
8131 p = XRESIZEVAR (void, p, new_nmemb * size);
8132 memset (((char *) p) + old_nmemb * size, 0, (new_nmemb - old_nmemb) * size);
8137 Find fallthru edge from PRED. */
8139 find_fallthru_edge_from (basic_block pred)
8144 succ = pred->next_bb;
8145 gcc_assert (succ->prev_bb == pred);
8147 if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds))
8149 e = find_fallthru_edge (pred->succs);
8153 gcc_assert (e->dest == succ);
8159 e = find_fallthru_edge (succ->preds);
8163 gcc_assert (e->src == pred);
8171 /* Extend per basic block data structures. */
8173 sched_extend_bb (void)
8175 /* The following is done to keep current_sched_info->next_tail non null. */
8176 rtx_insn *end = BB_END (EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb);
8177 rtx_insn *insn = DEBUG_INSN_P (end) ? prev_nondebug_insn (end) : end;
8178 if (NEXT_INSN (end) == 0
8181 /* Don't emit a NOTE if it would end up before a BARRIER. */
8182 && !BARRIER_P (NEXT_INSN (end))))
8184 rtx_note *note = emit_note_after (NOTE_INSN_DELETED, end);
8185 /* Make note appear outside BB. */
8186 set_block_for_insn (note, NULL);
8187 BB_END (EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb) = end;
8191 /* Init per basic block data structures. */
8193 sched_init_bbs (void)
8198 /* Initialize BEFORE_RECOVERY variable. */
8200 init_before_recovery (basic_block *before_recovery_ptr)
8205 last = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
8206 e = find_fallthru_edge_from (last);
8210 /* We create two basic blocks:
8211 1. Single instruction block is inserted right after E->SRC
8213 2. Empty block right before EXIT_BLOCK.
8214 Between these two blocks recovery blocks will be emitted. */
8216 basic_block single, empty;
8218 /* If the fallthrough edge to exit we've found is from the block we've
8219 created before, don't do anything more. */
8220 if (last == after_recovery)
8223 adding_bb_to_current_region_p = false;
8225 single = sched_create_empty_bb (last);
8226 empty = sched_create_empty_bb (single);
8228 /* Add new blocks to the root loop. */
8229 if (current_loops != NULL)
8231 add_bb_to_loop (single, (*current_loops->larray)[0]);
8232 add_bb_to_loop (empty, (*current_loops->larray)[0]);
8235 single->count = last->count;
8236 empty->count = last->count;
8237 single->frequency = last->frequency;
8238 empty->frequency = last->frequency;
8239 BB_COPY_PARTITION (single, last);
8240 BB_COPY_PARTITION (empty, last);
8242 redirect_edge_succ (e, single);
8243 make_single_succ_edge (single, empty, 0);
8244 make_single_succ_edge (empty, EXIT_BLOCK_PTR_FOR_FN (cfun),
8247 rtx_code_label *label = block_label (empty);
8248 rtx_jump_insn *x = emit_jump_insn_after (targetm.gen_jump (label),
8250 JUMP_LABEL (x) = label;
8251 LABEL_NUSES (label)++;
8252 haifa_init_insn (x);
8254 emit_barrier_after (x);
8256 sched_init_only_bb (empty, NULL);
8257 sched_init_only_bb (single, NULL);
8260 adding_bb_to_current_region_p = true;
8261 before_recovery = single;
8262 after_recovery = empty;
8264 if (before_recovery_ptr)
8265 *before_recovery_ptr = before_recovery;
8267 if (sched_verbose >= 2 && spec_info->dump)
8268 fprintf (spec_info->dump,
8269 ";;\t\tFixed fallthru to EXIT : %d->>%d->%d->>EXIT\n",
8270 last->index, single->index, empty->index);
8273 before_recovery = last;
8276 /* Returns new recovery block. */
8278 sched_create_recovery_block (basic_block *before_recovery_ptr)
8283 haifa_recovery_bb_recently_added_p = true;
8284 haifa_recovery_bb_ever_added_p = true;
8286 init_before_recovery (before_recovery_ptr);
8288 barrier = get_last_bb_insn (before_recovery);
8289 gcc_assert (BARRIER_P (barrier));
8291 rtx_insn *label = emit_label_after (gen_label_rtx (), barrier);
8293 rec = create_basic_block (label, label, before_recovery);
8295 /* A recovery block always ends with an unconditional jump. */
8296 emit_barrier_after (BB_END (rec));
8298 if (BB_PARTITION (before_recovery) != BB_UNPARTITIONED)
8299 BB_SET_PARTITION (rec, BB_COLD_PARTITION);
8301 if (sched_verbose && spec_info->dump)
8302 fprintf (spec_info->dump, ";;\t\tGenerated recovery block rec%d\n",
8308 /* Create edges: FIRST_BB -> REC; FIRST_BB -> SECOND_BB; REC -> SECOND_BB
8309 and emit necessary jumps. */
8311 sched_create_recovery_edges (basic_block first_bb, basic_block rec,
8312 basic_block second_bb)
8316 /* This is fixing of incoming edge. */
8317 /* ??? Which other flags should be specified? */
8318 if (BB_PARTITION (first_bb) != BB_PARTITION (rec))
8319 /* Partition type is the same, if it is "unpartitioned". */
8320 edge_flags = EDGE_CROSSING;
8324 make_edge (first_bb, rec, edge_flags);
8325 rtx_code_label *label = block_label (second_bb);
8326 rtx_jump_insn *jump = emit_jump_insn_after (targetm.gen_jump (label),
8328 JUMP_LABEL (jump) = label;
8329 LABEL_NUSES (label)++;
8331 if (BB_PARTITION (second_bb) != BB_PARTITION (rec))
8332 /* Partition type is the same, if it is "unpartitioned". */
8334 /* Rewritten from cfgrtl.c. */
8335 if (flag_reorder_blocks_and_partition
8336 && targetm_common.have_named_sections)
8338 /* We don't need the same note for the check because
8339 any_condjump_p (check) == true. */
8340 CROSSING_JUMP_P (jump) = 1;
8342 edge_flags = EDGE_CROSSING;
8347 make_single_succ_edge (rec, second_bb, edge_flags);
8348 if (dom_info_available_p (CDI_DOMINATORS))
8349 set_immediate_dominator (CDI_DOMINATORS, rec, first_bb);
8352 /* This function creates recovery code for INSN. If MUTATE_P is nonzero,
8353 INSN is a simple check, that should be converted to branchy one. */
8355 create_check_block_twin (rtx_insn *insn, bool mutate_p)
8358 rtx_insn *label, *check, *twin;
8361 sd_iterator_def sd_it;
8363 dep_def _new_dep, *new_dep = &_new_dep;
8366 gcc_assert (ORIG_PAT (insn) != NULL_RTX);
8369 todo_spec = TODO_SPEC (insn);
8372 gcc_assert (IS_SPECULATION_SIMPLE_CHECK_P (insn)
8373 && (TODO_SPEC (insn) & SPECULATIVE) == 0);
8375 todo_spec = CHECK_SPEC (insn);
8378 todo_spec &= SPECULATIVE;
8380 /* Create recovery block. */
8381 if (mutate_p || targetm.sched.needs_block_p (todo_spec))
8383 rec = sched_create_recovery_block (NULL);
8384 label = BB_HEAD (rec);
8388 rec = EXIT_BLOCK_PTR_FOR_FN (cfun);
8393 check_pat = targetm.sched.gen_spec_check (insn, label, todo_spec);
8395 if (rec != EXIT_BLOCK_PTR_FOR_FN (cfun))
8397 /* To have mem_reg alive at the beginning of second_bb,
8398 we emit check BEFORE insn, so insn after splitting
8399 insn will be at the beginning of second_bb, which will
8400 provide us with the correct life information. */
8401 check = emit_jump_insn_before (check_pat, insn);
8402 JUMP_LABEL (check) = label;
8403 LABEL_NUSES (label)++;
8406 check = emit_insn_before (check_pat, insn);
8408 /* Extend data structures. */
8409 haifa_init_insn (check);
8411 /* CHECK is being added to current region. Extend ready list. */
8412 gcc_assert (sched_ready_n_insns != -1);
8413 sched_extend_ready_list (sched_ready_n_insns + 1);
8415 if (current_sched_info->add_remove_insn)
8416 current_sched_info->add_remove_insn (insn, 0);
8418 RECOVERY_BLOCK (check) = rec;
8420 if (sched_verbose && spec_info->dump)
8421 fprintf (spec_info->dump, ";;\t\tGenerated check insn : %s\n",
8422 (*current_sched_info->print_insn) (check, 0));
8424 gcc_assert (ORIG_PAT (insn));
8426 /* Initialize TWIN (twin is a duplicate of original instruction
8427 in the recovery block). */
8428 if (rec != EXIT_BLOCK_PTR_FOR_FN (cfun))
8430 sd_iterator_def sd_it;
8433 FOR_EACH_DEP (insn, SD_LIST_RES_BACK, sd_it, dep)
8434 if ((DEP_STATUS (dep) & DEP_OUTPUT) != 0)
8436 struct _dep _dep2, *dep2 = &_dep2;
8438 init_dep (dep2, DEP_PRO (dep), check, REG_DEP_TRUE);
8440 sd_add_dep (dep2, true);
8443 twin = emit_insn_after (ORIG_PAT (insn), BB_END (rec));
8444 haifa_init_insn (twin);
8446 if (sched_verbose && spec_info->dump)
8447 /* INSN_BB (insn) isn't determined for twin insns yet.
8448 So we can't use current_sched_info->print_insn. */
8449 fprintf (spec_info->dump, ";;\t\tGenerated twin insn : %d/rec%d\n",
8450 INSN_UID (twin), rec->index);
8454 ORIG_PAT (check) = ORIG_PAT (insn);
8455 HAS_INTERNAL_DEP (check) = 1;
8457 /* ??? We probably should change all OUTPUT dependencies to
8461 /* Copy all resolved back dependencies of INSN to TWIN. This will
8462 provide correct value for INSN_TICK (TWIN). */
8463 sd_copy_back_deps (twin, insn, true);
8465 if (rec != EXIT_BLOCK_PTR_FOR_FN (cfun))
8466 /* In case of branchy check, fix CFG. */
8468 basic_block first_bb, second_bb;
8471 first_bb = BLOCK_FOR_INSN (check);
8472 second_bb = sched_split_block (first_bb, check);
8474 sched_create_recovery_edges (first_bb, rec, second_bb);
8476 sched_init_only_bb (second_bb, first_bb);
8477 sched_init_only_bb (rec, EXIT_BLOCK_PTR_FOR_FN (cfun));
8479 jump = BB_END (rec);
8480 haifa_init_insn (jump);
8483 /* Move backward dependences from INSN to CHECK and
8484 move forward dependences from INSN to TWIN. */
8486 /* First, create dependencies between INSN's producers and CHECK & TWIN. */
8487 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
8489 rtx_insn *pro = DEP_PRO (dep);
8492 /* If BEGIN_DATA: [insn ~~TRUE~~> producer]:
8493 check --TRUE--> producer ??? or ANTI ???
8494 twin --TRUE--> producer
8495 twin --ANTI--> check
8497 If BEGIN_CONTROL: [insn ~~ANTI~~> producer]:
8498 check --ANTI--> producer
8499 twin --ANTI--> producer
8500 twin --ANTI--> check
8502 If BE_IN_SPEC: [insn ~~TRUE~~> producer]:
8503 check ~~TRUE~~> producer
8504 twin ~~TRUE~~> producer
8505 twin --ANTI--> check */
8507 ds = DEP_STATUS (dep);
8509 if (ds & BEGIN_SPEC)
8511 gcc_assert (!mutate_p);
8515 init_dep_1 (new_dep, pro, check, DEP_TYPE (dep), ds);
8516 sd_add_dep (new_dep, false);
8518 if (rec != EXIT_BLOCK_PTR_FOR_FN (cfun))
8520 DEP_CON (new_dep) = twin;
8521 sd_add_dep (new_dep, false);
8525 /* Second, remove backward dependencies of INSN. */
8526 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
8527 sd_iterator_cond (&sd_it, &dep);)
8529 if ((DEP_STATUS (dep) & BEGIN_SPEC)
8531 /* We can delete this dep because we overcome it with
8532 BEGIN_SPECULATION. */
8533 sd_delete_dep (sd_it);
8535 sd_iterator_next (&sd_it);
8538 /* Future Speculations. Determine what BE_IN speculations will be like. */
8541 /* Fields (DONE_SPEC (x) & BEGIN_SPEC) and CHECK_SPEC (x) are set only
8544 gcc_assert (!DONE_SPEC (insn));
8548 ds_t ts = TODO_SPEC (insn);
8550 DONE_SPEC (insn) = ts & BEGIN_SPEC;
8551 CHECK_SPEC (check) = ts & BEGIN_SPEC;
8553 /* Luckiness of future speculations solely depends upon initial
8554 BEGIN speculation. */
8555 if (ts & BEGIN_DATA)
8556 fs = set_dep_weak (fs, BE_IN_DATA, get_dep_weak (ts, BEGIN_DATA));
8557 if (ts & BEGIN_CONTROL)
8558 fs = set_dep_weak (fs, BE_IN_CONTROL,
8559 get_dep_weak (ts, BEGIN_CONTROL));
8562 CHECK_SPEC (check) = CHECK_SPEC (insn);
8564 /* Future speculations: call the helper. */
8565 process_insn_forw_deps_be_in_spec (insn, twin, fs);
8567 if (rec != EXIT_BLOCK_PTR_FOR_FN (cfun))
8569 /* Which types of dependencies should we use here is,
8570 generally, machine-dependent question... But, for now,
8575 init_dep (new_dep, insn, check, REG_DEP_TRUE);
8576 sd_add_dep (new_dep, false);
8578 init_dep (new_dep, insn, twin, REG_DEP_OUTPUT);
8579 sd_add_dep (new_dep, false);
8583 if (spec_info->dump)
8584 fprintf (spec_info->dump, ";;\t\tRemoved simple check : %s\n",
8585 (*current_sched_info->print_insn) (insn, 0));
8587 /* Remove all dependencies of the INSN. */
8589 sd_it = sd_iterator_start (insn, (SD_LIST_FORW
8591 | SD_LIST_RES_BACK));
8592 while (sd_iterator_cond (&sd_it, &dep))
8593 sd_delete_dep (sd_it);
8596 /* If former check (INSN) already was moved to the ready (or queue)
8597 list, add new check (CHECK) there too. */
8598 if (QUEUE_INDEX (insn) != QUEUE_NOWHERE)
8601 /* Remove old check from instruction stream and free its
8603 sched_remove_insn (insn);
8606 init_dep (new_dep, check, twin, REG_DEP_ANTI);
8607 sd_add_dep (new_dep, false);
8611 init_dep_1 (new_dep, insn, check, REG_DEP_TRUE, DEP_TRUE | DEP_OUTPUT);
8612 sd_add_dep (new_dep, false);
8616 /* Fix priorities. If MUTATE_P is nonzero, this is not necessary,
8617 because it'll be done later in add_to_speculative_block. */
8619 rtx_vec_t priorities_roots = rtx_vec_t ();
8621 clear_priorities (twin, &priorities_roots);
8622 calc_priorities (priorities_roots);
8623 priorities_roots.release ();
8627 /* Removes dependency between instructions in the recovery block REC
8628 and usual region instructions. It keeps inner dependences so it
8629 won't be necessary to recompute them. */
8631 fix_recovery_deps (basic_block rec)
8633 rtx_insn *note, *insn, *jump;
8634 rtx_insn_list *ready_list = 0;
8635 bitmap_head in_ready;
8636 rtx_insn_list *link;
8638 bitmap_initialize (&in_ready, 0);
8640 /* NOTE - a basic block note. */
8641 note = NEXT_INSN (BB_HEAD (rec));
8642 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
8643 insn = BB_END (rec);
8644 gcc_assert (JUMP_P (insn));
8645 insn = PREV_INSN (insn);
8649 sd_iterator_def sd_it;
8652 for (sd_it = sd_iterator_start (insn, SD_LIST_FORW);
8653 sd_iterator_cond (&sd_it, &dep);)
8655 rtx_insn *consumer = DEP_CON (dep);
8657 if (BLOCK_FOR_INSN (consumer) != rec)
8659 sd_delete_dep (sd_it);
8661 if (bitmap_set_bit (&in_ready, INSN_LUID (consumer)))
8662 ready_list = alloc_INSN_LIST (consumer, ready_list);
8666 gcc_assert ((DEP_STATUS (dep) & DEP_TYPES) == DEP_TRUE);
8668 sd_iterator_next (&sd_it);
8672 insn = PREV_INSN (insn);
8674 while (insn != note);
8676 bitmap_clear (&in_ready);
8678 /* Try to add instructions to the ready or queue list. */
8679 for (link = ready_list; link; link = link->next ())
8680 try_ready (link->insn ());
8681 free_INSN_LIST_list (&ready_list);
8683 /* Fixing jump's dependences. */
8684 insn = BB_HEAD (rec);
8685 jump = BB_END (rec);
8687 gcc_assert (LABEL_P (insn));
8688 insn = NEXT_INSN (insn);
8690 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
8691 add_jump_dependencies (insn, jump);
8694 /* Change pattern of INSN to NEW_PAT. Invalidate cached haifa
8695 instruction data. */
8697 haifa_change_pattern (rtx_insn *insn, rtx new_pat)
8701 t = validate_change (insn, &PATTERN (insn), new_pat, 0);
8705 update_insn_after_change (insn);
8709 /* -1 - can't speculate,
8710 0 - for speculation with REQUEST mode it is OK to use
8711 current instruction pattern,
8712 1 - need to change pattern for *NEW_PAT to be speculative. */
8714 sched_speculate_insn (rtx_insn *insn, ds_t request, rtx *new_pat)
8716 gcc_assert (current_sched_info->flags & DO_SPECULATION
8717 && (request & SPECULATIVE)
8718 && sched_insn_is_legitimate_for_speculation_p (insn, request));
8720 if ((request & spec_info->mask) != request)
8723 if (request & BE_IN_SPEC
8724 && !(request & BEGIN_SPEC))
8727 return targetm.sched.speculate_insn (insn, request, new_pat);
8731 haifa_speculate_insn (rtx_insn *insn, ds_t request, rtx *new_pat)
8733 gcc_assert (sched_deps_info->generate_spec_deps
8734 && !IS_SPECULATION_CHECK_P (insn));
8736 if (HAS_INTERNAL_DEP (insn)
8737 || SCHED_GROUP_P (insn))
8740 return sched_speculate_insn (insn, request, new_pat);
8743 /* Print some information about block BB, which starts with HEAD and
8744 ends with TAIL, before scheduling it.
8745 I is zero, if scheduler is about to start with the fresh ebb. */
8747 dump_new_block_header (int i, basic_block bb, rtx_insn *head, rtx_insn *tail)
8750 fprintf (sched_dump,
8751 ";; ======================================================\n");
8753 fprintf (sched_dump,
8754 ";; =====================ADVANCING TO=====================\n");
8755 fprintf (sched_dump,
8756 ";; -- basic block %d from %d to %d -- %s reload\n",
8757 bb->index, INSN_UID (head), INSN_UID (tail),
8758 (reload_completed ? "after" : "before"));
8759 fprintf (sched_dump,
8760 ";; ======================================================\n");
8761 fprintf (sched_dump, "\n");
8764 /* Unlink basic block notes and labels and saves them, so they
8765 can be easily restored. We unlink basic block notes in EBB to
8766 provide back-compatibility with the previous code, as target backends
8767 assume, that there'll be only instructions between
8768 current_sched_info->{head and tail}. We restore these notes as soon
8770 FIRST (LAST) is the first (last) basic block in the ebb.
8771 NB: In usual case (FIRST == LAST) nothing is really done. */
8773 unlink_bb_notes (basic_block first, basic_block last)
8775 /* We DON'T unlink basic block notes of the first block in the ebb. */
8779 bb_header = XNEWVEC (rtx_insn *, last_basic_block_for_fn (cfun));
8781 /* Make a sentinel. */
8782 if (last->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
8783 bb_header[last->next_bb->index] = 0;
8785 first = first->next_bb;
8788 rtx_insn *prev, *label, *note, *next;
8790 label = BB_HEAD (last);
8791 if (LABEL_P (label))
8792 note = NEXT_INSN (label);
8795 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
8797 prev = PREV_INSN (label);
8798 next = NEXT_INSN (note);
8799 gcc_assert (prev && next);
8801 SET_NEXT_INSN (prev) = next;
8802 SET_PREV_INSN (next) = prev;
8804 bb_header[last->index] = label;
8809 last = last->prev_bb;
8814 /* Restore basic block notes.
8815 FIRST is the first basic block in the ebb. */
8817 restore_bb_notes (basic_block first)
8822 /* We DON'T unlink basic block notes of the first block in the ebb. */
8823 first = first->next_bb;
8824 /* Remember: FIRST is actually a second basic block in the ebb. */
8826 while (first != EXIT_BLOCK_PTR_FOR_FN (cfun)
8827 && bb_header[first->index])
8829 rtx_insn *prev, *label, *note, *next;
8831 label = bb_header[first->index];
8832 prev = PREV_INSN (label);
8833 next = NEXT_INSN (prev);
8835 if (LABEL_P (label))
8836 note = NEXT_INSN (label);
8839 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
8841 bb_header[first->index] = 0;
8843 SET_NEXT_INSN (prev) = label;
8844 SET_NEXT_INSN (note) = next;
8845 SET_PREV_INSN (next) = note;
8847 first = first->next_bb;
8855 Fix CFG after both in- and inter-block movement of
8856 control_flow_insn_p JUMP. */
8858 fix_jump_move (rtx_insn *jump)
8860 basic_block bb, jump_bb, jump_bb_next;
8862 bb = BLOCK_FOR_INSN (PREV_INSN (jump));
8863 jump_bb = BLOCK_FOR_INSN (jump);
8864 jump_bb_next = jump_bb->next_bb;
8866 gcc_assert (common_sched_info->sched_pass_id == SCHED_EBB_PASS
8867 || IS_SPECULATION_BRANCHY_CHECK_P (jump));
8869 if (!NOTE_INSN_BASIC_BLOCK_P (BB_END (jump_bb_next)))
8870 /* if jump_bb_next is not empty. */
8871 BB_END (jump_bb) = BB_END (jump_bb_next);
8873 if (BB_END (bb) != PREV_INSN (jump))
8874 /* Then there are instruction after jump that should be placed
8876 BB_END (jump_bb_next) = BB_END (bb);
8878 /* Otherwise jump_bb_next is empty. */
8879 BB_END (jump_bb_next) = NEXT_INSN (BB_HEAD (jump_bb_next));
8881 /* To make assertion in move_insn happy. */
8882 BB_END (bb) = PREV_INSN (jump);
8884 update_bb_for_insn (jump_bb_next);
8887 /* Fix CFG after interblock movement of control_flow_insn_p JUMP. */
8889 move_block_after_check (rtx_insn *jump)
8891 basic_block bb, jump_bb, jump_bb_next;
8892 vec<edge, va_gc> *t;
8894 bb = BLOCK_FOR_INSN (PREV_INSN (jump));
8895 jump_bb = BLOCK_FOR_INSN (jump);
8896 jump_bb_next = jump_bb->next_bb;
8898 update_bb_for_insn (jump_bb);
8900 gcc_assert (IS_SPECULATION_CHECK_P (jump)
8901 || IS_SPECULATION_CHECK_P (BB_END (jump_bb_next)));
8903 unlink_block (jump_bb_next);
8904 link_block (jump_bb_next, bb);
8908 move_succs (&(jump_bb->succs), bb);
8909 move_succs (&(jump_bb_next->succs), jump_bb);
8910 move_succs (&t, jump_bb_next);
8912 df_mark_solutions_dirty ();
8914 common_sched_info->fix_recovery_cfg
8915 (bb->index, jump_bb->index, jump_bb_next->index);
8918 /* Helper function for move_block_after_check.
8919 This functions attaches edge vector pointed to by SUCCSP to
8922 move_succs (vec<edge, va_gc> **succsp, basic_block to)
8927 gcc_assert (to->succs == 0);
8929 to->succs = *succsp;
8931 FOR_EACH_EDGE (e, ei, to->succs)
8937 /* Remove INSN from the instruction stream.
8938 INSN should have any dependencies. */
8940 sched_remove_insn (rtx_insn *insn)
8942 sd_finish_insn (insn);
8944 change_queue_index (insn, QUEUE_NOWHERE);
8945 current_sched_info->add_remove_insn (insn, 1);
8949 /* Clear priorities of all instructions, that are forward dependent on INSN.
8950 Store in vector pointed to by ROOTS_PTR insns on which priority () should
8951 be invoked to initialize all cleared priorities. */
8953 clear_priorities (rtx_insn *insn, rtx_vec_t *roots_ptr)
8955 sd_iterator_def sd_it;
8957 bool insn_is_root_p = true;
8959 gcc_assert (QUEUE_INDEX (insn) != QUEUE_SCHEDULED);
8961 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
8963 rtx_insn *pro = DEP_PRO (dep);
8965 if (INSN_PRIORITY_STATUS (pro) >= 0
8966 && QUEUE_INDEX (insn) != QUEUE_SCHEDULED)
8968 /* If DEP doesn't contribute to priority then INSN itself should
8969 be added to priority roots. */
8970 if (contributes_to_priority_p (dep))
8971 insn_is_root_p = false;
8973 INSN_PRIORITY_STATUS (pro) = -1;
8974 clear_priorities (pro, roots_ptr);
8979 roots_ptr->safe_push (insn);
8982 /* Recompute priorities of instructions, whose priorities might have been
8983 changed. ROOTS is a vector of instructions whose priority computation will
8984 trigger initialization of all cleared priorities. */
8986 calc_priorities (rtx_vec_t roots)
8991 FOR_EACH_VEC_ELT (roots, i, insn)
8996 /* Add dependences between JUMP and other instructions in the recovery
8997 block. INSN is the first insn the recovery block. */
8999 add_jump_dependencies (rtx_insn *insn, rtx_insn *jump)
9003 insn = NEXT_INSN (insn);
9007 if (dep_list_size (insn, SD_LIST_FORW) == 0)
9009 dep_def _new_dep, *new_dep = &_new_dep;
9011 init_dep (new_dep, insn, jump, REG_DEP_ANTI);
9012 sd_add_dep (new_dep, false);
9017 gcc_assert (!sd_lists_empty_p (jump, SD_LIST_BACK));
9020 /* Extend data structures for logical insn UID. */
9022 sched_extend_luids (void)
9024 int new_luids_max_uid = get_max_uid () + 1;
9026 sched_luids.safe_grow_cleared (new_luids_max_uid);
9029 /* Initialize LUID for INSN. */
9031 sched_init_insn_luid (rtx_insn *insn)
9033 int i = INSN_P (insn) ? 1 : common_sched_info->luid_for_non_insn (insn);
9038 luid = sched_max_luid;
9039 sched_max_luid += i;
9044 SET_INSN_LUID (insn, luid);
9047 /* Initialize luids for BBS.
9048 The hook common_sched_info->luid_for_non_insn () is used to determine
9049 if notes, labels, etc. need luids. */
9051 sched_init_luids (bb_vec_t bbs)
9056 sched_extend_luids ();
9057 FOR_EACH_VEC_ELT (bbs, i, bb)
9061 FOR_BB_INSNS (bb, insn)
9062 sched_init_insn_luid (insn);
9068 sched_finish_luids (void)
9070 sched_luids.release ();
9074 /* Return logical uid of INSN. Helpful while debugging. */
9076 insn_luid (rtx_insn *insn)
9078 return INSN_LUID (insn);
9081 /* Extend per insn data in the target. */
9083 sched_extend_target (void)
9085 if (targetm.sched.h_i_d_extended)
9086 targetm.sched.h_i_d_extended ();
9089 /* Extend global scheduler structures (those, that live across calls to
9090 schedule_block) to include information about just emitted INSN. */
9094 int reserve = (get_max_uid () + 1 - h_i_d.length ());
9096 && ! h_i_d.space (reserve))
9098 h_i_d.safe_grow_cleared (3 * get_max_uid () / 2);
9099 sched_extend_target ();
9103 /* Initialize h_i_d entry of the INSN with default values.
9104 Values, that are not explicitly initialized here, hold zero. */
9106 init_h_i_d (rtx_insn *insn)
9108 if (INSN_LUID (insn) > 0)
9110 INSN_COST (insn) = -1;
9111 QUEUE_INDEX (insn) = QUEUE_NOWHERE;
9112 INSN_TICK (insn) = INVALID_TICK;
9113 INSN_EXACT_TICK (insn) = INVALID_TICK;
9114 INTER_TICK (insn) = INVALID_TICK;
9115 TODO_SPEC (insn) = HARD_DEP;
9116 INSN_AUTOPREF_MULTIPASS_DATA (insn)[0].status
9117 = AUTOPREF_MULTIPASS_DATA_UNINITIALIZED;
9118 INSN_AUTOPREF_MULTIPASS_DATA (insn)[1].status
9119 = AUTOPREF_MULTIPASS_DATA_UNINITIALIZED;
9123 /* Initialize haifa_insn_data for BBS. */
9125 haifa_init_h_i_d (bb_vec_t bbs)
9131 FOR_EACH_VEC_ELT (bbs, i, bb)
9135 FOR_BB_INSNS (bb, insn)
9140 /* Finalize haifa_insn_data. */
9142 haifa_finish_h_i_d (void)
9145 haifa_insn_data_t data;
9146 struct reg_use_data *use, *next;
9148 FOR_EACH_VEC_ELT (h_i_d, i, data)
9150 free (data->max_reg_pressure);
9151 free (data->reg_pressure);
9152 for (use = data->reg_use_list; use != NULL; use = next)
9154 next = use->next_insn_use;
9161 /* Init data for the new insn INSN. */
9163 haifa_init_insn (rtx_insn *insn)
9165 gcc_assert (insn != NULL);
9167 sched_extend_luids ();
9168 sched_init_insn_luid (insn);
9169 sched_extend_target ();
9170 sched_deps_init (false);
9174 if (adding_bb_to_current_region_p)
9176 sd_init_insn (insn);
9178 /* Extend dependency caches by one element. */
9179 extend_dependency_caches (1, false);
9181 if (sched_pressure != SCHED_PRESSURE_NONE)
9182 init_insn_reg_pressure_info (insn);
9185 /* Init data for the new basic block BB which comes after AFTER. */
9187 haifa_init_only_bb (basic_block bb, basic_block after)
9189 gcc_assert (bb != NULL);
9193 if (common_sched_info->add_block)
9194 /* This changes only data structures of the front-end. */
9195 common_sched_info->add_block (bb, after);
9198 /* A generic version of sched_split_block (). */
9200 sched_split_block_1 (basic_block first_bb, rtx after)
9204 e = split_block (first_bb, after);
9205 gcc_assert (e->src == first_bb);
9207 /* sched_split_block emits note if *check == BB_END. Probably it
9208 is better to rip that note off. */
9213 /* A generic version of sched_create_empty_bb (). */
9215 sched_create_empty_bb_1 (basic_block after)
9217 return create_empty_bb (after);
9220 /* Insert PAT as an INSN into the schedule and update the necessary data
9221 structures to account for it. */
9223 sched_emit_insn (rtx pat)
9225 rtx_insn *insn = emit_insn_before (pat, first_nonscheduled_insn ());
9226 haifa_init_insn (insn);
9228 if (current_sched_info->add_remove_insn)
9229 current_sched_info->add_remove_insn (insn, 0);
9231 (*current_sched_info->begin_schedule_ready) (insn);
9232 scheduled_insns.safe_push (insn);
9234 last_scheduled_insn = insn;
9238 /* This function returns a candidate satisfying dispatch constraints from
9242 ready_remove_first_dispatch (struct ready_list *ready)
9245 rtx_insn *insn = ready_element (ready, 0);
9247 if (ready->n_ready == 1
9249 || INSN_CODE (insn) < 0
9250 || !active_insn_p (insn)
9251 || targetm.sched.dispatch (insn, FITS_DISPATCH_WINDOW))
9252 return ready_remove_first (ready);
9254 for (i = 1; i < ready->n_ready; i++)
9256 insn = ready_element (ready, i);
9259 || INSN_CODE (insn) < 0
9260 || !active_insn_p (insn))
9263 if (targetm.sched.dispatch (insn, FITS_DISPATCH_WINDOW))
9265 /* Return ith element of ready. */
9266 insn = ready_remove (ready, i);
9271 if (targetm.sched.dispatch (NULL, DISPATCH_VIOLATION))
9272 return ready_remove_first (ready);
9274 for (i = 1; i < ready->n_ready; i++)
9276 insn = ready_element (ready, i);
9279 || INSN_CODE (insn) < 0
9280 || !active_insn_p (insn))
9283 /* Return i-th element of ready. */
9284 if (targetm.sched.dispatch (insn, IS_CMP))
9285 return ready_remove (ready, i);
9288 return ready_remove_first (ready);
9291 /* Get number of ready insn in the ready list. */
9294 number_in_ready (void)
9296 return ready.n_ready;
9299 /* Get number of ready's in the ready list. */
9302 get_ready_element (int i)
9304 return ready_element (&ready, i);
9307 #endif /* INSN_SCHEDULING */