1 /* Instruction scheduling pass.
2 Copyright (C) 1992-2014 Free Software Foundation, Inc.
3 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
4 and currently maintained by, Jim Wilson (wilson@cygnus.com)
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* Instruction scheduling pass. This file, along with sched-deps.c,
23 contains the generic parts. The actual entry point for
24 the normal instruction scheduling pass is found in sched-rgn.c.
26 We compute insn priorities based on data dependencies. Flow
27 analysis only creates a fraction of the data-dependencies we must
28 observe: namely, only those dependencies which the combiner can be
29 expected to use. For this pass, we must therefore create the
30 remaining dependencies we need to observe: register dependencies,
31 memory dependencies, dependencies to keep function calls in order,
32 and the dependence between a conditional branch and the setting of
33 condition codes are all dealt with here.
35 The scheduler first traverses the data flow graph, starting with
36 the last instruction, and proceeding to the first, assigning values
37 to insn_priority as it goes. This sorts the instructions
38 topologically by data dependence.
40 Once priorities have been established, we order the insns using
41 list scheduling. This works as follows: starting with a list of
42 all the ready insns, and sorted according to priority number, we
43 schedule the insn from the end of the list by placing its
44 predecessors in the list according to their priority order. We
45 consider this insn scheduled by setting the pointer to the "end" of
46 the list to point to the previous insn. When an insn has no
47 predecessors, we either queue it until sufficient time has elapsed
48 or add it to the ready list. As the instructions are scheduled or
49 when stalls are introduced, the queue advances and dumps insns into
50 the ready list. When all insns down to the lowest priority have
51 been scheduled, the critical path of the basic block has been made
52 as short as possible. The remaining insns are then scheduled in
55 The following list shows the order in which we want to break ties
56 among insns in the ready list:
58 1. choose insn with the longest path to end of bb, ties
60 2. choose insn with least contribution to register pressure,
62 3. prefer in-block upon interblock motion, ties broken by
63 4. prefer useful upon speculative motion, ties broken by
64 5. choose insn with largest control flow probability, ties
66 6. choose insn with the least dependences upon the previously
67 scheduled insn, or finally
68 7 choose the insn which has the most insns dependent on it.
69 8. choose insn with lowest UID.
71 Memory references complicate matters. Only if we can be certain
72 that memory references are not part of the data dependency graph
73 (via true, anti, or output dependence), can we move operations past
74 memory references. To first approximation, reads can be done
75 independently, while writes introduce dependencies. Better
76 approximations will yield fewer dependencies.
78 Before reload, an extended analysis of interblock data dependences
79 is required for interblock scheduling. This is performed in
80 compute_block_dependences ().
82 Dependencies set up by memory references are treated in exactly the
83 same way as other dependencies, by using insn backward dependences
84 INSN_BACK_DEPS. INSN_BACK_DEPS are translated into forward dependences
85 INSN_FORW_DEPS for the purpose of forward list scheduling.
87 Having optimized the critical path, we may have also unduly
88 extended the lifetimes of some registers. If an operation requires
89 that constants be loaded into registers, it is certainly desirable
90 to load those constants as early as necessary, but no earlier.
91 I.e., it will not do to load up a bunch of registers at the
92 beginning of a basic block only to use them at the end, if they
93 could be loaded later, since this may result in excessive register
96 Note that since branches are never in basic blocks, but only end
97 basic blocks, this pass will not move branches. But that is ok,
98 since we can use GNU's delayed branch scheduling pass to take care
101 Also note that no further optimizations based on algebraic
102 identities are performed, so this pass would be a good one to
103 perform instruction splitting, such as breaking up a multiply
104 instruction into shifts and adds where that is profitable.
106 Given the memory aliasing analysis that this pass should perform,
107 it should be possible to remove redundant stores to memory, and to
108 load values from registers instead of hitting memory.
110 Before reload, speculative insns are moved only if a 'proof' exists
111 that no exception will be caused by this, and if no live registers
112 exist that inhibit the motion (live registers constraints are not
113 represented by data dependence edges).
115 This pass must update information that subsequent passes expect to
116 be correct. Namely: reg_n_refs, reg_n_sets, reg_n_deaths,
117 reg_n_calls_crossed, and reg_live_length. Also, BB_HEAD, BB_END.
119 The information in the line number notes is carefully retained by
120 this pass. Notes that refer to the starting and ending of
121 exception regions are also carefully retained by this pass. All
122 other NOTE insns are grouped in their same relative order at the
123 beginning of basic blocks and regions that have been scheduled. */
127 #include "coretypes.h"
129 #include "diagnostic-core.h"
130 #include "hard-reg-set.h"
134 #include "function.h"
136 #include "insn-config.h"
137 #include "insn-attr.h"
140 #include "sched-int.h"
142 #include "common/common-target.h"
147 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
148 #include "hash-table.h"
149 #include "dumpfile.h"
151 #ifdef INSN_SCHEDULING
153 /* True if we do register pressure relief through live-range
155 static bool live_range_shrinkage_p
;
157 /* Switch on live range shrinkage. */
159 initialize_live_range_shrinkage (void)
161 live_range_shrinkage_p
= true;
164 /* Switch off live range shrinkage. */
166 finish_live_range_shrinkage (void)
168 live_range_shrinkage_p
= false;
171 /* issue_rate is the number of insns that can be scheduled in the same
172 machine cycle. It can be defined in the config/mach/mach.h file,
173 otherwise we set it to 1. */
177 /* This can be set to true by a backend if the scheduler should not
178 enable a DCE pass. */
181 /* The current initiation interval used when modulo scheduling. */
182 static int modulo_ii
;
184 /* The maximum number of stages we are prepared to handle. */
185 static int modulo_max_stages
;
187 /* The number of insns that exist in each iteration of the loop. We use this
188 to detect when we've scheduled all insns from the first iteration. */
189 static int modulo_n_insns
;
191 /* The current count of insns in the first iteration of the loop that have
192 already been scheduled. */
193 static int modulo_insns_scheduled
;
195 /* The maximum uid of insns from the first iteration of the loop. */
196 static int modulo_iter0_max_uid
;
198 /* The number of times we should attempt to backtrack when modulo scheduling.
199 Decreased each time we have to backtrack. */
200 static int modulo_backtracks_left
;
202 /* The stage in which the last insn from the original loop was
204 static int modulo_last_stage
;
206 /* sched-verbose controls the amount of debugging output the
207 scheduler prints. It is controlled by -fsched-verbose=N:
208 N>0 and no -DSR : the output is directed to stderr.
209 N>=10 will direct the printouts to stderr (regardless of -dSR).
211 N=2: bb's probabilities, detailed ready list info, unit/insn info.
212 N=3: rtl at abort point, control-flow, regions info.
213 N=5: dependences info. */
215 int sched_verbose
= 0;
217 /* Debugging file. All printouts are sent to dump, which is always set,
218 either to stderr, or to the dump listing file (-dRS). */
219 FILE *sched_dump
= 0;
221 /* This is a placeholder for the scheduler parameters common
222 to all schedulers. */
223 struct common_sched_info_def
*common_sched_info
;
225 #define INSN_TICK(INSN) (HID (INSN)->tick)
226 #define INSN_EXACT_TICK(INSN) (HID (INSN)->exact_tick)
227 #define INSN_TICK_ESTIMATE(INSN) (HID (INSN)->tick_estimate)
228 #define INTER_TICK(INSN) (HID (INSN)->inter_tick)
229 #define FEEDS_BACKTRACK_INSN(INSN) (HID (INSN)->feeds_backtrack_insn)
230 #define SHADOW_P(INSN) (HID (INSN)->shadow_p)
231 #define MUST_RECOMPUTE_SPEC_P(INSN) (HID (INSN)->must_recompute_spec)
232 /* Cached cost of the instruction. Use insn_cost to get cost of the
233 insn. -1 here means that the field is not initialized. */
234 #define INSN_COST(INSN) (HID (INSN)->cost)
236 /* If INSN_TICK of an instruction is equal to INVALID_TICK,
237 then it should be recalculated from scratch. */
238 #define INVALID_TICK (-(max_insn_queue_index + 1))
239 /* The minimal value of the INSN_TICK of an instruction. */
240 #define MIN_TICK (-max_insn_queue_index)
242 /* Original order of insns in the ready list.
243 Used to keep order of normal insns while separating DEBUG_INSNs. */
244 #define INSN_RFS_DEBUG_ORIG_ORDER(INSN) (HID (INSN)->rfs_debug_orig_order)
246 /* The deciding reason for INSN's place in the ready list. */
247 #define INSN_LAST_RFS_WIN(INSN) (HID (INSN)->last_rfs_win)
249 /* List of important notes we must keep around. This is a pointer to the
250 last element in the list. */
253 static struct spec_info_def spec_info_var
;
254 /* Description of the speculative part of the scheduling.
255 If NULL - no speculation. */
256 spec_info_t spec_info
= NULL
;
258 /* True, if recovery block was added during scheduling of current block.
259 Used to determine, if we need to fix INSN_TICKs. */
260 static bool haifa_recovery_bb_recently_added_p
;
262 /* True, if recovery block was added during this scheduling pass.
263 Used to determine if we should have empty memory pools of dependencies
264 after finishing current region. */
265 bool haifa_recovery_bb_ever_added_p
;
267 /* Counters of different types of speculative instructions. */
268 static int nr_begin_data
, nr_be_in_data
, nr_begin_control
, nr_be_in_control
;
270 /* Array used in {unlink, restore}_bb_notes. */
271 static rtx
*bb_header
= 0;
273 /* Basic block after which recovery blocks will be created. */
274 static basic_block before_recovery
;
276 /* Basic block just before the EXIT_BLOCK and after recovery, if we have
278 basic_block after_recovery
;
280 /* FALSE if we add bb to another region, so we don't need to initialize it. */
281 bool adding_bb_to_current_region_p
= true;
285 /* An instruction is ready to be scheduled when all insns preceding it
286 have already been scheduled. It is important to ensure that all
287 insns which use its result will not be executed until its result
288 has been computed. An insn is maintained in one of four structures:
290 (P) the "Pending" set of insns which cannot be scheduled until
291 their dependencies have been satisfied.
292 (Q) the "Queued" set of insns that can be scheduled when sufficient
294 (R) the "Ready" list of unscheduled, uncommitted insns.
295 (S) the "Scheduled" list of insns.
297 Initially, all insns are either "Pending" or "Ready" depending on
298 whether their dependencies are satisfied.
300 Insns move from the "Ready" list to the "Scheduled" list as they
301 are committed to the schedule. As this occurs, the insns in the
302 "Pending" list have their dependencies satisfied and move to either
303 the "Ready" list or the "Queued" set depending on whether
304 sufficient time has passed to make them ready. As time passes,
305 insns move from the "Queued" set to the "Ready" list.
307 The "Pending" list (P) are the insns in the INSN_FORW_DEPS of the
308 unscheduled insns, i.e., those that are ready, queued, and pending.
309 The "Queued" set (Q) is implemented by the variable `insn_queue'.
310 The "Ready" list (R) is implemented by the variables `ready' and
312 The "Scheduled" list (S) is the new insn chain built by this pass.
314 The transition (R->S) is implemented in the scheduling loop in
315 `schedule_block' when the best insn to schedule is chosen.
316 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
317 insns move from the ready list to the scheduled list.
318 The transition (Q->R) is implemented in 'queue_to_insn' as time
319 passes or stalls are introduced. */
321 /* Implement a circular buffer to delay instructions until sufficient
322 time has passed. For the new pipeline description interface,
323 MAX_INSN_QUEUE_INDEX is a power of two minus one which is not less
324 than maximal time of instruction execution computed by genattr.c on
325 the base maximal time of functional unit reservations and getting a
326 result. This is the longest time an insn may be queued. */
328 static rtx
*insn_queue
;
329 static int q_ptr
= 0;
330 static int q_size
= 0;
331 #define NEXT_Q(X) (((X)+1) & max_insn_queue_index)
332 #define NEXT_Q_AFTER(X, C) (((X)+C) & max_insn_queue_index)
334 #define QUEUE_SCHEDULED (-3)
335 #define QUEUE_NOWHERE (-2)
336 #define QUEUE_READY (-1)
337 /* QUEUE_SCHEDULED - INSN is scheduled.
338 QUEUE_NOWHERE - INSN isn't scheduled yet and is neither in
340 QUEUE_READY - INSN is in ready list.
341 N >= 0 - INSN queued for X [where NEXT_Q_AFTER (q_ptr, X) == N] cycles. */
343 #define QUEUE_INDEX(INSN) (HID (INSN)->queue_index)
345 /* The following variable value refers for all current and future
346 reservations of the processor units. */
349 /* The following variable value is size of memory representing all
350 current and future reservations of the processor units. */
351 size_t dfa_state_size
;
353 /* The following array is used to find the best insn from ready when
354 the automaton pipeline interface is used. */
355 signed char *ready_try
= NULL
;
357 /* The ready list. */
358 struct ready_list ready
= {NULL
, 0, 0, 0, 0};
360 /* The pointer to the ready list (to be removed). */
361 static struct ready_list
*readyp
= &ready
;
363 /* Scheduling clock. */
364 static int clock_var
;
366 /* Clock at which the previous instruction was issued. */
367 static int last_clock_var
;
369 /* Set to true if, when queuing a shadow insn, we discover that it would be
370 scheduled too late. */
371 static bool must_backtrack
;
373 /* The following variable value is number of essential insns issued on
374 the current cycle. An insn is essential one if it changes the
376 int cycle_issued_insns
;
378 /* This records the actual schedule. It is built up during the main phase
379 of schedule_block, and afterwards used to reorder the insns in the RTL. */
380 static vec
<rtx
> scheduled_insns
;
382 static int may_trap_exp (const_rtx
, int);
384 /* Nonzero iff the address is comprised from at most 1 register. */
385 #define CONST_BASED_ADDRESS_P(x) \
387 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
388 || (GET_CODE (x) == LO_SUM)) \
389 && (CONSTANT_P (XEXP (x, 0)) \
390 || CONSTANT_P (XEXP (x, 1)))))
392 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
393 as found by analyzing insn's expression. */
396 static int haifa_luid_for_non_insn (rtx x
);
398 /* Haifa version of sched_info hooks common to all headers. */
399 const struct common_sched_info_def haifa_common_sched_info
=
401 NULL
, /* fix_recovery_cfg */
402 NULL
, /* add_block */
403 NULL
, /* estimate_number_of_insns */
404 haifa_luid_for_non_insn
, /* luid_for_non_insn */
405 SCHED_PASS_UNKNOWN
/* sched_pass_id */
408 /* Mapping from instruction UID to its Logical UID. */
409 vec
<int> sched_luids
= vNULL
;
411 /* Next LUID to assign to an instruction. */
412 int sched_max_luid
= 1;
414 /* Haifa Instruction Data. */
415 vec
<haifa_insn_data_def
> h_i_d
= vNULL
;
417 void (* sched_init_only_bb
) (basic_block
, basic_block
);
419 /* Split block function. Different schedulers might use different functions
420 to handle their internal data consistent. */
421 basic_block (* sched_split_block
) (basic_block
, rtx
);
423 /* Create empty basic block after the specified block. */
424 basic_block (* sched_create_empty_bb
) (basic_block
);
426 /* Return the number of cycles until INSN is expected to be ready.
427 Return zero if it already is. */
429 insn_delay (rtx insn
)
431 return MAX (INSN_TICK (insn
) - clock_var
, 0);
435 may_trap_exp (const_rtx x
, int is_store
)
444 if (code
== MEM
&& may_trap_p (x
))
451 /* The insn uses memory: a volatile load. */
452 if (MEM_VOLATILE_P (x
))
454 /* An exception-free load. */
457 /* A load with 1 base register, to be further checked. */
458 if (CONST_BASED_ADDRESS_P (XEXP (x
, 0)))
459 return PFREE_CANDIDATE
;
460 /* No info on the load, to be further checked. */
461 return PRISKY_CANDIDATE
;
466 int i
, insn_class
= TRAP_FREE
;
468 /* Neither store nor load, check if it may cause a trap. */
471 /* Recursive step: walk the insn... */
472 fmt
= GET_RTX_FORMAT (code
);
473 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
477 int tmp_class
= may_trap_exp (XEXP (x
, i
), is_store
);
478 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
480 else if (fmt
[i
] == 'E')
483 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
485 int tmp_class
= may_trap_exp (XVECEXP (x
, i
, j
), is_store
);
486 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
487 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
491 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
498 /* Classifies rtx X of an insn for the purpose of verifying that X can be
499 executed speculatively (and consequently the insn can be moved
500 speculatively), by examining X, returning:
501 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
502 TRAP_FREE: non-load insn.
503 IFREE: load from a globally safe location.
504 IRISKY: volatile load.
505 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
506 being either PFREE or PRISKY. */
509 haifa_classify_rtx (const_rtx x
)
511 int tmp_class
= TRAP_FREE
;
512 int insn_class
= TRAP_FREE
;
515 if (GET_CODE (x
) == PARALLEL
)
517 int i
, len
= XVECLEN (x
, 0);
519 for (i
= len
- 1; i
>= 0; i
--)
521 tmp_class
= haifa_classify_rtx (XVECEXP (x
, 0, i
));
522 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
523 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
533 /* Test if it is a 'store'. */
534 tmp_class
= may_trap_exp (XEXP (x
, 0), 1);
537 /* Test if it is a store. */
538 tmp_class
= may_trap_exp (SET_DEST (x
), 1);
539 if (tmp_class
== TRAP_RISKY
)
541 /* Test if it is a load. */
543 WORST_CLASS (tmp_class
,
544 may_trap_exp (SET_SRC (x
), 0));
547 tmp_class
= haifa_classify_rtx (COND_EXEC_CODE (x
));
548 if (tmp_class
== TRAP_RISKY
)
550 tmp_class
= WORST_CLASS (tmp_class
,
551 may_trap_exp (COND_EXEC_TEST (x
), 0));
554 tmp_class
= TRAP_RISKY
;
558 insn_class
= tmp_class
;
565 haifa_classify_insn (const_rtx insn
)
567 return haifa_classify_rtx (PATTERN (insn
));
570 /* After the scheduler initialization function has been called, this function
571 can be called to enable modulo scheduling. II is the initiation interval
572 we should use, it affects the delays for delay_pairs that were recorded as
573 separated by a given number of stages.
575 MAX_STAGES provides us with a limit
576 after which we give up scheduling; the caller must have unrolled at least
577 as many copies of the loop body and recorded delay_pairs for them.
579 INSNS is the number of real (non-debug) insns in one iteration of
580 the loop. MAX_UID can be used to test whether an insn belongs to
581 the first iteration of the loop; all of them have a uid lower than
584 set_modulo_params (int ii
, int max_stages
, int insns
, int max_uid
)
587 modulo_max_stages
= max_stages
;
588 modulo_n_insns
= insns
;
589 modulo_iter0_max_uid
= max_uid
;
590 modulo_backtracks_left
= PARAM_VALUE (PARAM_MAX_MODULO_BACKTRACK_ATTEMPTS
);
593 /* A structure to record a pair of insns where the first one is a real
594 insn that has delay slots, and the second is its delayed shadow.
595 I1 is scheduled normally and will emit an assembly instruction,
596 while I2 describes the side effect that takes place at the
597 transition between cycles CYCLES and (CYCLES + 1) after I1. */
600 struct delay_pair
*next_same_i1
;
603 /* When doing modulo scheduling, we a delay_pair can also be used to
604 show that I1 and I2 are the same insn in a different stage. If that
605 is the case, STAGES will be nonzero. */
609 /* Helpers for delay hashing. */
611 struct delay_i1_hasher
: typed_noop_remove
<delay_pair
>
613 typedef delay_pair value_type
;
614 typedef void compare_type
;
615 static inline hashval_t
hash (const value_type
*);
616 static inline bool equal (const value_type
*, const compare_type
*);
619 /* Returns a hash value for X, based on hashing just I1. */
622 delay_i1_hasher::hash (const value_type
*x
)
624 return htab_hash_pointer (x
->i1
);
627 /* Return true if I1 of pair X is the same as that of pair Y. */
630 delay_i1_hasher::equal (const value_type
*x
, const compare_type
*y
)
635 struct delay_i2_hasher
: typed_free_remove
<delay_pair
>
637 typedef delay_pair value_type
;
638 typedef void compare_type
;
639 static inline hashval_t
hash (const value_type
*);
640 static inline bool equal (const value_type
*, const compare_type
*);
643 /* Returns a hash value for X, based on hashing just I2. */
646 delay_i2_hasher::hash (const value_type
*x
)
648 return htab_hash_pointer (x
->i2
);
651 /* Return true if I2 of pair X is the same as that of pair Y. */
654 delay_i2_hasher::equal (const value_type
*x
, const compare_type
*y
)
659 /* Two hash tables to record delay_pairs, one indexed by I1 and the other
661 static hash_table
<delay_i1_hasher
> delay_htab
;
662 static hash_table
<delay_i2_hasher
> delay_htab_i2
;
664 /* Called through htab_traverse. Walk the hashtable using I2 as
665 index, and delete all elements involving an UID higher than
666 that pointed to by *DATA. */
668 haifa_htab_i2_traverse (delay_pair
**slot
, int *data
)
671 struct delay_pair
*p
= *slot
;
672 if (INSN_UID (p
->i2
) >= maxuid
|| INSN_UID (p
->i1
) >= maxuid
)
674 delay_htab_i2
.clear_slot (slot
);
679 /* Called through htab_traverse. Walk the hashtable using I2 as
680 index, and delete all elements involving an UID higher than
681 that pointed to by *DATA. */
683 haifa_htab_i1_traverse (delay_pair
**pslot
, int *data
)
686 struct delay_pair
*p
, *first
, **pprev
;
688 if (INSN_UID ((*pslot
)->i1
) >= maxuid
)
690 delay_htab
.clear_slot (pslot
);
694 for (p
= *pslot
; p
; p
= p
->next_same_i1
)
696 if (INSN_UID (p
->i2
) < maxuid
)
699 pprev
= &p
->next_same_i1
;
704 delay_htab
.clear_slot (pslot
);
710 /* Discard all delay pairs which involve an insn with an UID higher
713 discard_delay_pairs_above (int max_uid
)
715 delay_htab
.traverse
<int *, haifa_htab_i1_traverse
> (&max_uid
);
716 delay_htab_i2
.traverse
<int *, haifa_htab_i2_traverse
> (&max_uid
);
719 /* This function can be called by a port just before it starts the final
720 scheduling pass. It records the fact that an instruction with delay
721 slots has been split into two insns, I1 and I2. The first one will be
722 scheduled normally and initiates the operation. The second one is a
723 shadow which must follow a specific number of cycles after I1; its only
724 purpose is to show the side effect that occurs at that cycle in the RTL.
725 If a JUMP_INSN or a CALL_INSN has been split, I1 should be a normal INSN,
726 while I2 retains the original insn type.
728 There are two ways in which the number of cycles can be specified,
729 involving the CYCLES and STAGES arguments to this function. If STAGES
730 is zero, we just use the value of CYCLES. Otherwise, STAGES is a factor
731 which is multiplied by MODULO_II to give the number of cycles. This is
732 only useful if the caller also calls set_modulo_params to enable modulo
736 record_delay_slot_pair (rtx i1
, rtx i2
, int cycles
, int stages
)
738 struct delay_pair
*p
= XNEW (struct delay_pair
);
739 struct delay_pair
**slot
;
746 if (!delay_htab
.is_created ())
748 delay_htab
.create (10);
749 delay_htab_i2
.create (10);
751 slot
= delay_htab
.find_slot_with_hash (i1
, htab_hash_pointer (i1
), INSERT
);
752 p
->next_same_i1
= *slot
;
754 slot
= delay_htab_i2
.find_slot_with_hash (i2
, htab_hash_pointer (i2
), INSERT
);
758 /* Examine the delay pair hashtable to see if INSN is a shadow for another,
759 and return the other insn if so. Return NULL otherwise. */
761 real_insn_for_shadow (rtx insn
)
763 struct delay_pair
*pair
;
765 if (!delay_htab
.is_created ())
768 pair
= delay_htab_i2
.find_with_hash (insn
, htab_hash_pointer (insn
));
769 if (!pair
|| pair
->stages
> 0)
774 /* For a pair P of insns, return the fixed distance in cycles from the first
775 insn after which the second must be scheduled. */
777 pair_delay (struct delay_pair
*p
)
782 return p
->stages
* modulo_ii
;
785 /* Given an insn INSN, add a dependence on its delayed shadow if it
786 has one. Also try to find situations where shadows depend on each other
787 and add dependencies to the real insns to limit the amount of backtracking
790 add_delay_dependencies (rtx insn
)
792 struct delay_pair
*pair
;
793 sd_iterator_def sd_it
;
796 if (!delay_htab
.is_created ())
799 pair
= delay_htab_i2
.find_with_hash (insn
, htab_hash_pointer (insn
));
802 add_dependence (insn
, pair
->i1
, REG_DEP_ANTI
);
806 FOR_EACH_DEP (pair
->i2
, SD_LIST_BACK
, sd_it
, dep
)
808 rtx pro
= DEP_PRO (dep
);
809 struct delay_pair
*other_pair
810 = delay_htab_i2
.find_with_hash (pro
, htab_hash_pointer (pro
));
811 if (!other_pair
|| other_pair
->stages
)
813 if (pair_delay (other_pair
) >= pair_delay (pair
))
815 if (sched_verbose
>= 4)
817 fprintf (sched_dump
, ";;\tadding dependence %d <- %d\n",
818 INSN_UID (other_pair
->i1
),
819 INSN_UID (pair
->i1
));
820 fprintf (sched_dump
, ";;\tpair1 %d <- %d, cost %d\n",
824 fprintf (sched_dump
, ";;\tpair2 %d <- %d, cost %d\n",
825 INSN_UID (other_pair
->i1
),
826 INSN_UID (other_pair
->i2
),
827 pair_delay (other_pair
));
829 add_dependence (pair
->i1
, other_pair
->i1
, REG_DEP_ANTI
);
834 /* Forward declarations. */
836 static int priority (rtx
);
837 static int autopref_rank_for_schedule (const rtx
, const rtx
);
838 static int rank_for_schedule (const void *, const void *);
839 static void swap_sort (rtx
*, int);
840 static void queue_insn (rtx
, int, const char *);
841 static int schedule_insn (rtx
);
842 static void adjust_priority (rtx
);
843 static void advance_one_cycle (void);
844 static void extend_h_i_d (void);
847 /* Notes handling mechanism:
848 =========================
849 Generally, NOTES are saved before scheduling and restored after scheduling.
850 The scheduler distinguishes between two types of notes:
852 (1) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
853 Before scheduling a region, a pointer to the note is added to the insn
854 that follows or precedes it. (This happens as part of the data dependence
855 computation). After scheduling an insn, the pointer contained in it is
856 used for regenerating the corresponding note (in reemit_notes).
858 (2) All other notes (e.g. INSN_DELETED): Before scheduling a block,
859 these notes are put in a list (in rm_other_notes() and
860 unlink_other_notes ()). After scheduling the block, these notes are
861 inserted at the beginning of the block (in schedule_block()). */
863 static void ready_add (struct ready_list
*, rtx
, bool);
864 static rtx
ready_remove_first (struct ready_list
*);
865 static rtx
ready_remove_first_dispatch (struct ready_list
*ready
);
867 static void queue_to_ready (struct ready_list
*);
868 static int early_queue_to_ready (state_t
, struct ready_list
*);
870 /* The following functions are used to implement multi-pass scheduling
871 on the first cycle. */
872 static rtx
ready_remove (struct ready_list
*, int);
873 static void ready_remove_insn (rtx
);
875 static void fix_inter_tick (rtx
, rtx
);
876 static int fix_tick_ready (rtx
);
877 static void change_queue_index (rtx
, int);
879 /* The following functions are used to implement scheduling of data/control
880 speculative instructions. */
882 static void extend_h_i_d (void);
883 static void init_h_i_d (rtx
);
884 static int haifa_speculate_insn (rtx
, ds_t
, rtx
*);
885 static void generate_recovery_code (rtx
);
886 static void process_insn_forw_deps_be_in_spec (rtx
, rtx
, ds_t
);
887 static void begin_speculative_block (rtx
);
888 static void add_to_speculative_block (rtx
);
889 static void init_before_recovery (basic_block
*);
890 static void create_check_block_twin (rtx
, bool);
891 static void fix_recovery_deps (basic_block
);
892 static bool haifa_change_pattern (rtx
, rtx
);
893 static void dump_new_block_header (int, basic_block
, rtx
, rtx
);
894 static void restore_bb_notes (basic_block
);
895 static void fix_jump_move (rtx
);
896 static void move_block_after_check (rtx
);
897 static void move_succs (vec
<edge
, va_gc
> **, basic_block
);
898 static void sched_remove_insn (rtx
);
899 static void clear_priorities (rtx
, rtx_vec_t
*);
900 static void calc_priorities (rtx_vec_t
);
901 static void add_jump_dependencies (rtx
, rtx
);
903 #endif /* INSN_SCHEDULING */
905 /* Point to state used for the current scheduling pass. */
906 struct haifa_sched_info
*current_sched_info
;
908 #ifndef INSN_SCHEDULING
910 schedule_insns (void)
915 /* Do register pressure sensitive insn scheduling if the flag is set
917 enum sched_pressure_algorithm sched_pressure
;
919 /* Map regno -> its pressure class. The map defined only when
920 SCHED_PRESSURE != SCHED_PRESSURE_NONE. */
921 enum reg_class
*sched_regno_pressure_class
;
923 /* The current register pressure. Only elements corresponding pressure
924 classes are defined. */
925 static int curr_reg_pressure
[N_REG_CLASSES
];
927 /* Saved value of the previous array. */
928 static int saved_reg_pressure
[N_REG_CLASSES
];
930 /* Register living at given scheduling point. */
931 static bitmap curr_reg_live
;
933 /* Saved value of the previous array. */
934 static bitmap saved_reg_live
;
936 /* Registers mentioned in the current region. */
937 static bitmap region_ref_regs
;
939 /* Effective number of available registers of a given class (see comment
940 in sched_pressure_start_bb). */
941 static int sched_class_regs_num
[N_REG_CLASSES
];
942 /* Number of call_used_regs. This is a helper for calculating of
943 sched_class_regs_num. */
944 static int call_used_regs_num
[N_REG_CLASSES
];
946 /* Initiate register pressure relative info for scheduling the current
947 region. Currently it is only clearing register mentioned in the
950 sched_init_region_reg_pressure_info (void)
952 bitmap_clear (region_ref_regs
);
955 /* PRESSURE[CL] describes the pressure on register class CL. Update it
956 for the birth (if BIRTH_P) or death (if !BIRTH_P) of register REGNO.
957 LIVE tracks the set of live registers; if it is null, assume that
958 every birth or death is genuine. */
960 mark_regno_birth_or_death (bitmap live
, int *pressure
, int regno
, bool birth_p
)
962 enum reg_class pressure_class
;
964 pressure_class
= sched_regno_pressure_class
[regno
];
965 if (regno
>= FIRST_PSEUDO_REGISTER
)
967 if (pressure_class
!= NO_REGS
)
971 if (!live
|| bitmap_set_bit (live
, regno
))
972 pressure
[pressure_class
]
973 += (ira_reg_class_max_nregs
974 [pressure_class
][PSEUDO_REGNO_MODE (regno
)]);
978 if (!live
|| bitmap_clear_bit (live
, regno
))
979 pressure
[pressure_class
]
980 -= (ira_reg_class_max_nregs
981 [pressure_class
][PSEUDO_REGNO_MODE (regno
)]);
985 else if (pressure_class
!= NO_REGS
986 && ! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
990 if (!live
|| bitmap_set_bit (live
, regno
))
991 pressure
[pressure_class
]++;
995 if (!live
|| bitmap_clear_bit (live
, regno
))
996 pressure
[pressure_class
]--;
1001 /* Initiate current register pressure related info from living
1002 registers given by LIVE. */
1004 initiate_reg_pressure_info (bitmap live
)
1010 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1011 curr_reg_pressure
[ira_pressure_classes
[i
]] = 0;
1012 bitmap_clear (curr_reg_live
);
1013 EXECUTE_IF_SET_IN_BITMAP (live
, 0, j
, bi
)
1014 if (sched_pressure
== SCHED_PRESSURE_MODEL
1015 || current_nr_blocks
== 1
1016 || bitmap_bit_p (region_ref_regs
, j
))
1017 mark_regno_birth_or_death (curr_reg_live
, curr_reg_pressure
, j
, true);
1020 /* Mark registers in X as mentioned in the current region. */
1022 setup_ref_regs (rtx x
)
1025 const RTX_CODE code
= GET_CODE (x
);
1031 if (HARD_REGISTER_NUM_P (regno
))
1032 bitmap_set_range (region_ref_regs
, regno
,
1033 hard_regno_nregs
[regno
][GET_MODE (x
)]);
1035 bitmap_set_bit (region_ref_regs
, REGNO (x
));
1038 fmt
= GET_RTX_FORMAT (code
);
1039 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1041 setup_ref_regs (XEXP (x
, i
));
1042 else if (fmt
[i
] == 'E')
1044 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1045 setup_ref_regs (XVECEXP (x
, i
, j
));
1049 /* Initiate current register pressure related info at the start of
1052 initiate_bb_reg_pressure_info (basic_block bb
)
1054 unsigned int i ATTRIBUTE_UNUSED
;
1057 if (current_nr_blocks
> 1)
1058 FOR_BB_INSNS (bb
, insn
)
1059 if (NONDEBUG_INSN_P (insn
))
1060 setup_ref_regs (PATTERN (insn
));
1061 initiate_reg_pressure_info (df_get_live_in (bb
));
1062 #ifdef EH_RETURN_DATA_REGNO
1063 if (bb_has_eh_pred (bb
))
1066 unsigned int regno
= EH_RETURN_DATA_REGNO (i
);
1068 if (regno
== INVALID_REGNUM
)
1070 if (! bitmap_bit_p (df_get_live_in (bb
), regno
))
1071 mark_regno_birth_or_death (curr_reg_live
, curr_reg_pressure
,
1077 /* Save current register pressure related info. */
1079 save_reg_pressure (void)
1083 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1084 saved_reg_pressure
[ira_pressure_classes
[i
]]
1085 = curr_reg_pressure
[ira_pressure_classes
[i
]];
1086 bitmap_copy (saved_reg_live
, curr_reg_live
);
1089 /* Restore saved register pressure related info. */
1091 restore_reg_pressure (void)
1095 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1096 curr_reg_pressure
[ira_pressure_classes
[i
]]
1097 = saved_reg_pressure
[ira_pressure_classes
[i
]];
1098 bitmap_copy (curr_reg_live
, saved_reg_live
);
1101 /* Return TRUE if the register is dying after its USE. */
1103 dying_use_p (struct reg_use_data
*use
)
1105 struct reg_use_data
*next
;
1107 for (next
= use
->next_regno_use
; next
!= use
; next
= next
->next_regno_use
)
1108 if (NONDEBUG_INSN_P (next
->insn
)
1109 && QUEUE_INDEX (next
->insn
) != QUEUE_SCHEDULED
)
1114 /* Print info about the current register pressure and its excess for
1115 each pressure class. */
1117 print_curr_reg_pressure (void)
1122 fprintf (sched_dump
, ";;\t");
1123 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1125 cl
= ira_pressure_classes
[i
];
1126 gcc_assert (curr_reg_pressure
[cl
] >= 0);
1127 fprintf (sched_dump
, " %s:%d(%d)", reg_class_names
[cl
],
1128 curr_reg_pressure
[cl
],
1129 curr_reg_pressure
[cl
] - sched_class_regs_num
[cl
]);
1131 fprintf (sched_dump
, "\n");
1134 /* Determine if INSN has a condition that is clobbered if a register
1135 in SET_REGS is modified. */
1137 cond_clobbered_p (rtx insn
, HARD_REG_SET set_regs
)
1139 rtx pat
= PATTERN (insn
);
1140 gcc_assert (GET_CODE (pat
) == COND_EXEC
);
1141 if (TEST_HARD_REG_BIT (set_regs
, REGNO (XEXP (COND_EXEC_TEST (pat
), 0))))
1143 sd_iterator_def sd_it
;
1145 haifa_change_pattern (insn
, ORIG_PAT (insn
));
1146 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
1147 DEP_STATUS (dep
) &= ~DEP_CANCELLED
;
1148 TODO_SPEC (insn
) = HARD_DEP
;
1149 if (sched_verbose
>= 2)
1150 fprintf (sched_dump
,
1151 ";;\t\tdequeue insn %s because of clobbered condition\n",
1152 (*current_sched_info
->print_insn
) (insn
, 0));
1159 /* This function should be called after modifying the pattern of INSN,
1160 to update scheduler data structures as needed. */
1162 update_insn_after_change (rtx insn
)
1164 sd_iterator_def sd_it
;
1167 dfa_clear_single_insn_cache (insn
);
1169 sd_it
= sd_iterator_start (insn
,
1170 SD_LIST_FORW
| SD_LIST_BACK
| SD_LIST_RES_BACK
);
1171 while (sd_iterator_cond (&sd_it
, &dep
))
1173 DEP_COST (dep
) = UNKNOWN_DEP_COST
;
1174 sd_iterator_next (&sd_it
);
1177 /* Invalidate INSN_COST, so it'll be recalculated. */
1178 INSN_COST (insn
) = -1;
1179 /* Invalidate INSN_TICK, so it'll be recalculated. */
1180 INSN_TICK (insn
) = INVALID_TICK
;
1182 /* Invalidate autoprefetch data entry. */
1183 INSN_AUTOPREF_MULTIPASS_DATA (insn
)[0].status
1184 = AUTOPREF_MULTIPASS_DATA_UNINITIALIZED
;
1185 INSN_AUTOPREF_MULTIPASS_DATA (insn
)[1].status
1186 = AUTOPREF_MULTIPASS_DATA_UNINITIALIZED
;
1190 /* Two VECs, one to hold dependencies for which pattern replacements
1191 need to be applied or restored at the start of the next cycle, and
1192 another to hold an integer that is either one, to apply the
1193 corresponding replacement, or zero to restore it. */
1194 static vec
<dep_t
> next_cycle_replace_deps
;
1195 static vec
<int> next_cycle_apply
;
1197 static void apply_replacement (dep_t
, bool);
1198 static void restore_pattern (dep_t
, bool);
1200 /* Look at the remaining dependencies for insn NEXT, and compute and return
1201 the TODO_SPEC value we should use for it. This is called after one of
1202 NEXT's dependencies has been resolved.
1203 We also perform pattern replacements for predication, and for broken
1204 replacement dependencies. The latter is only done if FOR_BACKTRACK is
1208 recompute_todo_spec (rtx next
, bool for_backtrack
)
1211 sd_iterator_def sd_it
;
1212 dep_t dep
, modify_dep
= NULL
;
1216 bool first_p
= true;
1218 if (sd_lists_empty_p (next
, SD_LIST_BACK
))
1219 /* NEXT has all its dependencies resolved. */
1222 if (!sd_lists_empty_p (next
, SD_LIST_HARD_BACK
))
1225 /* If NEXT is intended to sit adjacent to this instruction, we don't
1226 want to try to break any dependencies. Treat it as a HARD_DEP. */
1227 if (SCHED_GROUP_P (next
))
1230 /* Now we've got NEXT with speculative deps only.
1231 1. Look at the deps to see what we have to do.
1232 2. Check if we can do 'todo'. */
1235 FOR_EACH_DEP (next
, SD_LIST_BACK
, sd_it
, dep
)
1237 rtx pro
= DEP_PRO (dep
);
1238 ds_t ds
= DEP_STATUS (dep
) & SPECULATIVE
;
1240 if (DEBUG_INSN_P (pro
) && !DEBUG_INSN_P (next
))
1253 new_ds
= ds_merge (new_ds
, ds
);
1255 else if (DEP_TYPE (dep
) == REG_DEP_CONTROL
)
1257 if (QUEUE_INDEX (pro
) != QUEUE_SCHEDULED
)
1262 DEP_STATUS (dep
) &= ~DEP_CANCELLED
;
1264 else if (DEP_REPLACE (dep
) != NULL
)
1266 if (QUEUE_INDEX (pro
) != QUEUE_SCHEDULED
)
1271 DEP_STATUS (dep
) &= ~DEP_CANCELLED
;
1275 if (n_replace
> 0 && n_control
== 0 && n_spec
== 0)
1277 if (!dbg_cnt (sched_breakdep
))
1279 FOR_EACH_DEP (next
, SD_LIST_BACK
, sd_it
, dep
)
1281 struct dep_replacement
*desc
= DEP_REPLACE (dep
);
1284 if (desc
->insn
== next
&& !for_backtrack
)
1286 gcc_assert (n_replace
== 1);
1287 apply_replacement (dep
, true);
1289 DEP_STATUS (dep
) |= DEP_CANCELLED
;
1295 else if (n_control
== 1 && n_replace
== 0 && n_spec
== 0)
1297 rtx pro
, other
, new_pat
;
1298 rtx cond
= NULL_RTX
;
1300 rtx prev
= NULL_RTX
;
1304 if ((current_sched_info
->flags
& DO_PREDICATION
) == 0
1305 || (ORIG_PAT (next
) != NULL_RTX
1306 && PREDICATED_PAT (next
) == NULL_RTX
))
1309 pro
= DEP_PRO (modify_dep
);
1310 other
= real_insn_for_shadow (pro
);
1311 if (other
!= NULL_RTX
)
1314 cond
= sched_get_reverse_condition_uncached (pro
);
1315 regno
= REGNO (XEXP (cond
, 0));
1317 /* Find the last scheduled insn that modifies the condition register.
1318 We can stop looking once we find the insn we depend on through the
1319 REG_DEP_CONTROL; if the condition register isn't modified after it,
1320 we know that it still has the right value. */
1321 if (QUEUE_INDEX (pro
) == QUEUE_SCHEDULED
)
1322 FOR_EACH_VEC_ELT_REVERSE (scheduled_insns
, i
, prev
)
1326 find_all_hard_reg_sets (prev
, &t
);
1327 if (TEST_HARD_REG_BIT (t
, regno
))
1332 if (ORIG_PAT (next
) == NULL_RTX
)
1334 ORIG_PAT (next
) = PATTERN (next
);
1336 new_pat
= gen_rtx_COND_EXEC (VOIDmode
, cond
, PATTERN (next
));
1337 success
= haifa_change_pattern (next
, new_pat
);
1340 PREDICATED_PAT (next
) = new_pat
;
1342 else if (PATTERN (next
) != PREDICATED_PAT (next
))
1344 bool success
= haifa_change_pattern (next
,
1345 PREDICATED_PAT (next
));
1346 gcc_assert (success
);
1348 DEP_STATUS (modify_dep
) |= DEP_CANCELLED
;
1352 if (PREDICATED_PAT (next
) != NULL_RTX
)
1354 int tick
= INSN_TICK (next
);
1355 bool success
= haifa_change_pattern (next
,
1357 INSN_TICK (next
) = tick
;
1358 gcc_assert (success
);
1361 /* We can't handle the case where there are both speculative and control
1362 dependencies, so we return HARD_DEP in such a case. Also fail if
1363 we have speculative dependencies with not enough points, or more than
1364 one control dependency. */
1365 if ((n_spec
> 0 && (n_control
> 0 || n_replace
> 0))
1367 /* Too few points? */
1368 && ds_weak (new_ds
) < spec_info
->data_weakness_cutoff
)
1376 /* Pointer to the last instruction scheduled. */
1377 static rtx last_scheduled_insn
;
1379 /* Pointer to the last nondebug instruction scheduled within the
1380 block, or the prev_head of the scheduling block. Used by
1381 rank_for_schedule, so that insns independent of the last scheduled
1382 insn will be preferred over dependent instructions. */
1383 static rtx last_nondebug_scheduled_insn
;
1385 /* Pointer that iterates through the list of unscheduled insns if we
1386 have a dbg_cnt enabled. It always points at an insn prior to the
1387 first unscheduled one. */
1388 static rtx nonscheduled_insns_begin
;
1390 /* Compute cost of executing INSN.
1391 This is the number of cycles between instruction issue and
1392 instruction results. */
1394 insn_cost (rtx insn
)
1400 if (recog_memoized (insn
) < 0)
1403 cost
= insn_default_latency (insn
);
1410 cost
= INSN_COST (insn
);
1414 /* A USE insn, or something else we don't need to
1415 understand. We can't pass these directly to
1416 result_ready_cost or insn_default_latency because it will
1417 trigger a fatal error for unrecognizable insns. */
1418 if (recog_memoized (insn
) < 0)
1420 INSN_COST (insn
) = 0;
1425 cost
= insn_default_latency (insn
);
1429 INSN_COST (insn
) = cost
;
1436 /* Compute cost of dependence LINK.
1437 This is the number of cycles between instruction issue and
1438 instruction results.
1439 ??? We also use this function to call recog_memoized on all insns. */
1441 dep_cost_1 (dep_t link
, dw_t dw
)
1443 rtx insn
= DEP_PRO (link
);
1444 rtx used
= DEP_CON (link
);
1447 if (DEP_COST (link
) != UNKNOWN_DEP_COST
)
1448 return DEP_COST (link
);
1450 if (delay_htab
.is_created ())
1452 struct delay_pair
*delay_entry
;
1454 = delay_htab_i2
.find_with_hash (used
, htab_hash_pointer (used
));
1457 if (delay_entry
->i1
== insn
)
1459 DEP_COST (link
) = pair_delay (delay_entry
);
1460 return DEP_COST (link
);
1465 /* A USE insn should never require the value used to be computed.
1466 This allows the computation of a function's result and parameter
1467 values to overlap the return and call. We don't care about the
1468 dependence cost when only decreasing register pressure. */
1469 if (recog_memoized (used
) < 0)
1472 recog_memoized (insn
);
1476 enum reg_note dep_type
= DEP_TYPE (link
);
1478 cost
= insn_cost (insn
);
1480 if (INSN_CODE (insn
) >= 0)
1482 if (dep_type
== REG_DEP_ANTI
)
1484 else if (dep_type
== REG_DEP_OUTPUT
)
1486 cost
= (insn_default_latency (insn
)
1487 - insn_default_latency (used
));
1491 else if (bypass_p (insn
))
1492 cost
= insn_latency (insn
, used
);
1496 if (targetm
.sched
.adjust_cost_2
)
1497 cost
= targetm
.sched
.adjust_cost_2 (used
, (int) dep_type
, insn
, cost
,
1499 else if (targetm
.sched
.adjust_cost
!= NULL
)
1501 /* This variable is used for backward compatibility with the
1503 rtx dep_cost_rtx_link
= alloc_INSN_LIST (NULL_RTX
, NULL_RTX
);
1505 /* Make it self-cycled, so that if some tries to walk over this
1506 incomplete list he/she will be caught in an endless loop. */
1507 XEXP (dep_cost_rtx_link
, 1) = dep_cost_rtx_link
;
1509 /* Targets use only REG_NOTE_KIND of the link. */
1510 PUT_REG_NOTE_KIND (dep_cost_rtx_link
, DEP_TYPE (link
));
1512 cost
= targetm
.sched
.adjust_cost (used
, dep_cost_rtx_link
,
1515 free_INSN_LIST_node (dep_cost_rtx_link
);
1522 DEP_COST (link
) = cost
;
1526 /* Compute cost of dependence LINK.
1527 This is the number of cycles between instruction issue and
1528 instruction results. */
1530 dep_cost (dep_t link
)
1532 return dep_cost_1 (link
, 0);
1535 /* Use this sel-sched.c friendly function in reorder2 instead of increasing
1536 INSN_PRIORITY explicitly. */
1538 increase_insn_priority (rtx insn
, int amount
)
1540 if (!sel_sched_p ())
1542 /* We're dealing with haifa-sched.c INSN_PRIORITY. */
1543 if (INSN_PRIORITY_KNOWN (insn
))
1544 INSN_PRIORITY (insn
) += amount
;
1548 /* In sel-sched.c INSN_PRIORITY is not kept up to date.
1549 Use EXPR_PRIORITY instead. */
1550 sel_add_to_insn_priority (insn
, amount
);
1554 /* Return 'true' if DEP should be included in priority calculations. */
1556 contributes_to_priority_p (dep_t dep
)
1558 if (DEBUG_INSN_P (DEP_CON (dep
))
1559 || DEBUG_INSN_P (DEP_PRO (dep
)))
1562 /* Critical path is meaningful in block boundaries only. */
1563 if (!current_sched_info
->contributes_to_priority (DEP_CON (dep
),
1567 if (DEP_REPLACE (dep
) != NULL
)
1570 /* If flag COUNT_SPEC_IN_CRITICAL_PATH is set,
1571 then speculative instructions will less likely be
1572 scheduled. That is because the priority of
1573 their producers will increase, and, thus, the
1574 producers will more likely be scheduled, thus,
1575 resolving the dependence. */
1576 if (sched_deps_info
->generate_spec_deps
1577 && !(spec_info
->flags
& COUNT_SPEC_IN_CRITICAL_PATH
)
1578 && (DEP_STATUS (dep
) & SPECULATIVE
))
1584 /* Compute the number of nondebug deps in list LIST for INSN. */
1587 dep_list_size (rtx insn
, sd_list_types_def list
)
1589 sd_iterator_def sd_it
;
1591 int dbgcount
= 0, nodbgcount
= 0;
1593 if (!MAY_HAVE_DEBUG_INSNS
)
1594 return sd_lists_size (insn
, list
);
1596 FOR_EACH_DEP (insn
, list
, sd_it
, dep
)
1598 if (DEBUG_INSN_P (DEP_CON (dep
)))
1600 else if (!DEBUG_INSN_P (DEP_PRO (dep
)))
1604 gcc_assert (dbgcount
+ nodbgcount
== sd_lists_size (insn
, list
));
1609 /* Compute the priority number for INSN. */
1613 if (! INSN_P (insn
))
1616 /* We should not be interested in priority of an already scheduled insn. */
1617 gcc_assert (QUEUE_INDEX (insn
) != QUEUE_SCHEDULED
);
1619 if (!INSN_PRIORITY_KNOWN (insn
))
1621 int this_priority
= -1;
1623 if (dep_list_size (insn
, SD_LIST_FORW
) == 0)
1624 /* ??? We should set INSN_PRIORITY to insn_cost when and insn has
1625 some forward deps but all of them are ignored by
1626 contributes_to_priority hook. At the moment we set priority of
1628 this_priority
= insn_cost (insn
);
1631 rtx prev_first
, twin
;
1634 /* For recovery check instructions we calculate priority slightly
1635 different than that of normal instructions. Instead of walking
1636 through INSN_FORW_DEPS (check) list, we walk through
1637 INSN_FORW_DEPS list of each instruction in the corresponding
1640 /* Selective scheduling does not define RECOVERY_BLOCK macro. */
1641 rec
= sel_sched_p () ? NULL
: RECOVERY_BLOCK (insn
);
1642 if (!rec
|| rec
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1644 prev_first
= PREV_INSN (insn
);
1649 prev_first
= NEXT_INSN (BB_HEAD (rec
));
1650 twin
= PREV_INSN (BB_END (rec
));
1655 sd_iterator_def sd_it
;
1658 FOR_EACH_DEP (twin
, SD_LIST_FORW
, sd_it
, dep
)
1663 next
= DEP_CON (dep
);
1665 if (BLOCK_FOR_INSN (next
) != rec
)
1669 if (!contributes_to_priority_p (dep
))
1673 cost
= dep_cost (dep
);
1676 struct _dep _dep1
, *dep1
= &_dep1
;
1678 init_dep (dep1
, insn
, next
, REG_DEP_ANTI
);
1680 cost
= dep_cost (dep1
);
1683 next_priority
= cost
+ priority (next
);
1685 if (next_priority
> this_priority
)
1686 this_priority
= next_priority
;
1690 twin
= PREV_INSN (twin
);
1692 while (twin
!= prev_first
);
1695 if (this_priority
< 0)
1697 gcc_assert (this_priority
== -1);
1699 this_priority
= insn_cost (insn
);
1702 INSN_PRIORITY (insn
) = this_priority
;
1703 INSN_PRIORITY_STATUS (insn
) = 1;
1706 return INSN_PRIORITY (insn
);
1709 /* Macros and functions for keeping the priority queue sorted, and
1710 dealing with queuing and dequeuing of instructions. */
1712 /* For each pressure class CL, set DEATH[CL] to the number of registers
1713 in that class that die in INSN. */
1716 calculate_reg_deaths (rtx insn
, int *death
)
1719 struct reg_use_data
*use
;
1721 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1722 death
[ira_pressure_classes
[i
]] = 0;
1723 for (use
= INSN_REG_USE_LIST (insn
); use
!= NULL
; use
= use
->next_insn_use
)
1724 if (dying_use_p (use
))
1725 mark_regno_birth_or_death (0, death
, use
->regno
, true);
1728 /* Setup info about the current register pressure impact of scheduling
1729 INSN at the current scheduling point. */
1731 setup_insn_reg_pressure_info (rtx insn
)
1733 int i
, change
, before
, after
, hard_regno
;
1734 int excess_cost_change
;
1735 enum machine_mode mode
;
1737 struct reg_pressure_data
*pressure_info
;
1738 int *max_reg_pressure
;
1739 static int death
[N_REG_CLASSES
];
1741 gcc_checking_assert (!DEBUG_INSN_P (insn
));
1743 excess_cost_change
= 0;
1744 calculate_reg_deaths (insn
, death
);
1745 pressure_info
= INSN_REG_PRESSURE (insn
);
1746 max_reg_pressure
= INSN_MAX_REG_PRESSURE (insn
);
1747 gcc_assert (pressure_info
!= NULL
&& max_reg_pressure
!= NULL
);
1748 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1750 cl
= ira_pressure_classes
[i
];
1751 gcc_assert (curr_reg_pressure
[cl
] >= 0);
1752 change
= (int) pressure_info
[i
].set_increase
- death
[cl
];
1753 before
= MAX (0, max_reg_pressure
[i
] - sched_class_regs_num
[cl
]);
1754 after
= MAX (0, max_reg_pressure
[i
] + change
1755 - sched_class_regs_num
[cl
]);
1756 hard_regno
= ira_class_hard_regs
[cl
][0];
1757 gcc_assert (hard_regno
>= 0);
1758 mode
= reg_raw_mode
[hard_regno
];
1759 excess_cost_change
+= ((after
- before
)
1760 * (ira_memory_move_cost
[mode
][cl
][0]
1761 + ira_memory_move_cost
[mode
][cl
][1]));
1763 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insn
) = excess_cost_change
;
1766 /* This is the first page of code related to SCHED_PRESSURE_MODEL.
1767 It tries to make the scheduler take register pressure into account
1768 without introducing too many unnecessary stalls. It hooks into the
1769 main scheduling algorithm at several points:
1771 - Before scheduling starts, model_start_schedule constructs a
1772 "model schedule" for the current block. This model schedule is
1773 chosen solely to keep register pressure down. It does not take the
1774 target's pipeline or the original instruction order into account,
1775 except as a tie-breaker. It also doesn't work to a particular
1778 This model schedule gives us an idea of what pressure can be
1779 achieved for the block and gives us an example of a schedule that
1780 keeps to that pressure. It also makes the final schedule less
1781 dependent on the original instruction order. This is important
1782 because the original order can either be "wide" (many values live
1783 at once, such as in user-scheduled code) or "narrow" (few values
1784 live at once, such as after loop unrolling, where several
1785 iterations are executed sequentially).
1787 We do not apply this model schedule to the rtx stream. We simply
1788 record it in model_schedule. We also compute the maximum pressure,
1789 MP, that was seen during this schedule.
1791 - Instructions are added to the ready queue even if they require
1792 a stall. The length of the stall is instead computed as:
1794 MAX (INSN_TICK (INSN) - clock_var, 0)
1796 (= insn_delay). This allows rank_for_schedule to choose between
1797 introducing a deliberate stall or increasing pressure.
1799 - Before sorting the ready queue, model_set_excess_costs assigns
1800 a pressure-based cost to each ready instruction in the queue.
1801 This is the instruction's INSN_REG_PRESSURE_EXCESS_COST_CHANGE
1802 (ECC for short) and is effectively measured in cycles.
1804 - rank_for_schedule ranks instructions based on:
1806 ECC (insn) + insn_delay (insn)
1812 So, for example, an instruction X1 with an ECC of 1 that can issue
1813 now will win over an instruction X0 with an ECC of zero that would
1814 introduce a stall of one cycle. However, an instruction X2 with an
1815 ECC of 2 that can issue now will lose to both X0 and X1.
1817 - When an instruction is scheduled, model_recompute updates the model
1818 schedule with the new pressures (some of which might now exceed the
1819 original maximum pressure MP). model_update_limit_points then searches
1820 for the new point of maximum pressure, if not already known. */
1822 /* Used to separate high-verbosity debug information for SCHED_PRESSURE_MODEL
1823 from surrounding debug information. */
1825 ";;\t\t+------------------------------------------------------\n"
1827 /* Information about the pressure on a particular register class at a
1828 particular point of the model schedule. */
1829 struct model_pressure_data
{
1830 /* The pressure at this point of the model schedule, or -1 if the
1831 point is associated with an instruction that has already been
1835 /* The maximum pressure during or after this point of the model schedule. */
1839 /* Per-instruction information that is used while building the model
1840 schedule. Here, "schedule" refers to the model schedule rather
1841 than the main schedule. */
1842 struct model_insn_info
{
1843 /* The instruction itself. */
1846 /* If this instruction is in model_worklist, these fields link to the
1847 previous (higher-priority) and next (lower-priority) instructions
1849 struct model_insn_info
*prev
;
1850 struct model_insn_info
*next
;
1852 /* While constructing the schedule, QUEUE_INDEX describes whether an
1853 instruction has already been added to the schedule (QUEUE_SCHEDULED),
1854 is in model_worklist (QUEUE_READY), or neither (QUEUE_NOWHERE).
1855 old_queue records the value that QUEUE_INDEX had before scheduling
1856 started, so that we can restore it once the schedule is complete. */
1859 /* The relative importance of an unscheduled instruction. Higher
1860 values indicate greater importance. */
1861 unsigned int model_priority
;
1863 /* The length of the longest path of satisfied true dependencies
1864 that leads to this instruction. */
1867 /* The length of the longest path of dependencies of any kind
1868 that leads from this instruction. */
1871 /* The number of predecessor nodes that must still be scheduled. */
1872 int unscheduled_preds
;
1875 /* Information about the pressure limit for a particular register class.
1876 This structure is used when applying a model schedule to the main
1878 struct model_pressure_limit
{
1879 /* The maximum register pressure seen in the original model schedule. */
1882 /* The maximum register pressure seen in the current model schedule
1883 (which excludes instructions that have already been scheduled). */
1886 /* The point of the current model schedule at which PRESSURE is first
1887 reached. It is set to -1 if the value needs to be recomputed. */
1891 /* Describes a particular way of measuring register pressure. */
1892 struct model_pressure_group
{
1893 /* Index PCI describes the maximum pressure on ira_pressure_classes[PCI]. */
1894 struct model_pressure_limit limits
[N_REG_CLASSES
];
1896 /* Index (POINT * ira_num_pressure_classes + PCI) describes the pressure
1897 on register class ira_pressure_classes[PCI] at point POINT of the
1898 current model schedule. A POINT of model_num_insns describes the
1899 pressure at the end of the schedule. */
1900 struct model_pressure_data
*model
;
1903 /* Index POINT gives the instruction at point POINT of the model schedule.
1904 This array doesn't change during main scheduling. */
1905 static vec
<rtx
> model_schedule
;
1907 /* The list of instructions in the model worklist, sorted in order of
1908 decreasing priority. */
1909 static struct model_insn_info
*model_worklist
;
1911 /* Index I describes the instruction with INSN_LUID I. */
1912 static struct model_insn_info
*model_insns
;
1914 /* The number of instructions in the model schedule. */
1915 static int model_num_insns
;
1917 /* The index of the first instruction in model_schedule that hasn't yet been
1918 added to the main schedule, or model_num_insns if all of them have. */
1919 static int model_curr_point
;
1921 /* Describes the pressure before each instruction in the model schedule. */
1922 static struct model_pressure_group model_before_pressure
;
1924 /* The first unused model_priority value (as used in model_insn_info). */
1925 static unsigned int model_next_priority
;
1928 /* The model_pressure_data for ira_pressure_classes[PCI] in GROUP
1929 at point POINT of the model schedule. */
1930 #define MODEL_PRESSURE_DATA(GROUP, POINT, PCI) \
1931 (&(GROUP)->model[(POINT) * ira_pressure_classes_num + (PCI)])
1933 /* The maximum pressure on ira_pressure_classes[PCI] in GROUP at or
1934 after point POINT of the model schedule. */
1935 #define MODEL_MAX_PRESSURE(GROUP, POINT, PCI) \
1936 (MODEL_PRESSURE_DATA (GROUP, POINT, PCI)->max_pressure)
1938 /* The pressure on ira_pressure_classes[PCI] in GROUP at point POINT
1939 of the model schedule. */
1940 #define MODEL_REF_PRESSURE(GROUP, POINT, PCI) \
1941 (MODEL_PRESSURE_DATA (GROUP, POINT, PCI)->ref_pressure)
1943 /* Information about INSN that is used when creating the model schedule. */
1944 #define MODEL_INSN_INFO(INSN) \
1945 (&model_insns[INSN_LUID (INSN)])
1947 /* The instruction at point POINT of the model schedule. */
1948 #define MODEL_INSN(POINT) \
1949 (model_schedule[POINT])
1952 /* Return INSN's index in the model schedule, or model_num_insns if it
1953 doesn't belong to that schedule. */
1956 model_index (rtx insn
)
1958 if (INSN_MODEL_INDEX (insn
) == 0)
1959 return model_num_insns
;
1960 return INSN_MODEL_INDEX (insn
) - 1;
1963 /* Make sure that GROUP->limits is up-to-date for the current point
1964 of the model schedule. */
1967 model_update_limit_points_in_group (struct model_pressure_group
*group
)
1969 int pci
, max_pressure
, point
;
1971 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
1973 /* We may have passed the final point at which the pressure in
1974 group->limits[pci].pressure was reached. Update the limit if so. */
1975 max_pressure
= MODEL_MAX_PRESSURE (group
, model_curr_point
, pci
);
1976 group
->limits
[pci
].pressure
= max_pressure
;
1978 /* Find the point at which MAX_PRESSURE is first reached. We need
1979 to search in three cases:
1981 - We've already moved past the previous pressure point.
1982 In this case we search forward from model_curr_point.
1984 - We scheduled the previous point of maximum pressure ahead of
1985 its position in the model schedule, but doing so didn't bring
1986 the pressure point earlier. In this case we search forward
1987 from that previous pressure point.
1989 - Scheduling an instruction early caused the maximum pressure
1990 to decrease. In this case we will have set the pressure
1991 point to -1, and we search forward from model_curr_point. */
1992 point
= MAX (group
->limits
[pci
].point
, model_curr_point
);
1993 while (point
< model_num_insns
1994 && MODEL_REF_PRESSURE (group
, point
, pci
) < max_pressure
)
1996 group
->limits
[pci
].point
= point
;
1998 gcc_assert (MODEL_REF_PRESSURE (group
, point
, pci
) == max_pressure
);
1999 gcc_assert (MODEL_MAX_PRESSURE (group
, point
, pci
) == max_pressure
);
2003 /* Make sure that all register-pressure limits are up-to-date for the
2004 current position in the model schedule. */
2007 model_update_limit_points (void)
2009 model_update_limit_points_in_group (&model_before_pressure
);
2012 /* Return the model_index of the last unscheduled use in chain USE
2013 outside of USE's instruction. Return -1 if there are no other uses,
2014 or model_num_insns if the register is live at the end of the block. */
2017 model_last_use_except (struct reg_use_data
*use
)
2019 struct reg_use_data
*next
;
2023 for (next
= use
->next_regno_use
; next
!= use
; next
= next
->next_regno_use
)
2024 if (NONDEBUG_INSN_P (next
->insn
)
2025 && QUEUE_INDEX (next
->insn
) != QUEUE_SCHEDULED
)
2027 index
= model_index (next
->insn
);
2028 if (index
== model_num_insns
)
2029 return model_num_insns
;
2036 /* An instruction with model_index POINT has just been scheduled, and it
2037 adds DELTA to the pressure on ira_pressure_classes[PCI] after POINT - 1.
2038 Update MODEL_REF_PRESSURE (GROUP, POINT, PCI) and
2039 MODEL_MAX_PRESSURE (GROUP, POINT, PCI) accordingly. */
2042 model_start_update_pressure (struct model_pressure_group
*group
,
2043 int point
, int pci
, int delta
)
2045 int next_max_pressure
;
2047 if (point
== model_num_insns
)
2049 /* The instruction wasn't part of the model schedule; it was moved
2050 from a different block. Update the pressure for the end of
2051 the model schedule. */
2052 MODEL_REF_PRESSURE (group
, point
, pci
) += delta
;
2053 MODEL_MAX_PRESSURE (group
, point
, pci
) += delta
;
2057 /* Record that this instruction has been scheduled. Nothing now
2058 changes between POINT and POINT + 1, so get the maximum pressure
2059 from the latter. If the maximum pressure decreases, the new
2060 pressure point may be before POINT. */
2061 MODEL_REF_PRESSURE (group
, point
, pci
) = -1;
2062 next_max_pressure
= MODEL_MAX_PRESSURE (group
, point
+ 1, pci
);
2063 if (MODEL_MAX_PRESSURE (group
, point
, pci
) > next_max_pressure
)
2065 MODEL_MAX_PRESSURE (group
, point
, pci
) = next_max_pressure
;
2066 if (group
->limits
[pci
].point
== point
)
2067 group
->limits
[pci
].point
= -1;
2072 /* Record that scheduling a later instruction has changed the pressure
2073 at point POINT of the model schedule by DELTA (which might be 0).
2074 Update GROUP accordingly. Return nonzero if these changes might
2075 trigger changes to previous points as well. */
2078 model_update_pressure (struct model_pressure_group
*group
,
2079 int point
, int pci
, int delta
)
2081 int ref_pressure
, max_pressure
, next_max_pressure
;
2083 /* If POINT hasn't yet been scheduled, update its pressure. */
2084 ref_pressure
= MODEL_REF_PRESSURE (group
, point
, pci
);
2085 if (ref_pressure
>= 0 && delta
!= 0)
2087 ref_pressure
+= delta
;
2088 MODEL_REF_PRESSURE (group
, point
, pci
) = ref_pressure
;
2090 /* Check whether the maximum pressure in the overall schedule
2091 has increased. (This means that the MODEL_MAX_PRESSURE of
2092 every point <= POINT will need to increase too; see below.) */
2093 if (group
->limits
[pci
].pressure
< ref_pressure
)
2094 group
->limits
[pci
].pressure
= ref_pressure
;
2096 /* If we are at maximum pressure, and the maximum pressure
2097 point was previously unknown or later than POINT,
2098 bring it forward. */
2099 if (group
->limits
[pci
].pressure
== ref_pressure
2100 && !IN_RANGE (group
->limits
[pci
].point
, 0, point
))
2101 group
->limits
[pci
].point
= point
;
2103 /* If POINT used to be the point of maximum pressure, but isn't
2104 any longer, we need to recalculate it using a forward walk. */
2105 if (group
->limits
[pci
].pressure
> ref_pressure
2106 && group
->limits
[pci
].point
== point
)
2107 group
->limits
[pci
].point
= -1;
2110 /* Update the maximum pressure at POINT. Changes here might also
2111 affect the maximum pressure at POINT - 1. */
2112 next_max_pressure
= MODEL_MAX_PRESSURE (group
, point
+ 1, pci
);
2113 max_pressure
= MAX (ref_pressure
, next_max_pressure
);
2114 if (MODEL_MAX_PRESSURE (group
, point
, pci
) != max_pressure
)
2116 MODEL_MAX_PRESSURE (group
, point
, pci
) = max_pressure
;
2122 /* INSN has just been scheduled. Update the model schedule accordingly. */
2125 model_recompute (rtx insn
)
2130 } uses
[FIRST_PSEUDO_REGISTER
+ MAX_RECOG_OPERANDS
];
2131 struct reg_use_data
*use
;
2132 struct reg_pressure_data
*reg_pressure
;
2133 int delta
[N_REG_CLASSES
];
2134 int pci
, point
, mix
, new_last
, cl
, ref_pressure
, queue
;
2135 unsigned int i
, num_uses
, num_pending_births
;
2138 /* The destinations of INSN were previously live from POINT onwards, but are
2139 now live from model_curr_point onwards. Set up DELTA accordingly. */
2140 point
= model_index (insn
);
2141 reg_pressure
= INSN_REG_PRESSURE (insn
);
2142 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
2144 cl
= ira_pressure_classes
[pci
];
2145 delta
[cl
] = reg_pressure
[pci
].set_increase
;
2148 /* Record which registers previously died at POINT, but which now die
2149 before POINT. Adjust DELTA so that it represents the effect of
2150 this change after POINT - 1. Set NUM_PENDING_BIRTHS to the number of
2151 registers that will be born in the range [model_curr_point, POINT). */
2153 num_pending_births
= 0;
2154 for (use
= INSN_REG_USE_LIST (insn
); use
!= NULL
; use
= use
->next_insn_use
)
2156 new_last
= model_last_use_except (use
);
2157 if (new_last
< point
)
2159 gcc_assert (num_uses
< ARRAY_SIZE (uses
));
2160 uses
[num_uses
].last_use
= new_last
;
2161 uses
[num_uses
].regno
= use
->regno
;
2162 /* This register is no longer live after POINT - 1. */
2163 mark_regno_birth_or_death (NULL
, delta
, use
->regno
, false);
2166 num_pending_births
++;
2170 /* Update the MODEL_REF_PRESSURE and MODEL_MAX_PRESSURE for POINT.
2171 Also set each group pressure limit for POINT. */
2172 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
2174 cl
= ira_pressure_classes
[pci
];
2175 model_start_update_pressure (&model_before_pressure
,
2176 point
, pci
, delta
[cl
]);
2179 /* Walk the model schedule backwards, starting immediately before POINT. */
2181 if (point
!= model_curr_point
)
2185 insn
= MODEL_INSN (point
);
2186 queue
= QUEUE_INDEX (insn
);
2188 if (queue
!= QUEUE_SCHEDULED
)
2190 /* DELTA describes the effect of the move on the register pressure
2191 after POINT. Make it describe the effect on the pressure
2194 while (i
< num_uses
)
2196 if (uses
[i
].last_use
== point
)
2198 /* This register is now live again. */
2199 mark_regno_birth_or_death (NULL
, delta
,
2200 uses
[i
].regno
, true);
2202 /* Remove this use from the array. */
2203 uses
[i
] = uses
[num_uses
- 1];
2205 num_pending_births
--;
2211 if (sched_verbose
>= 5)
2215 fprintf (sched_dump
, MODEL_BAR
);
2216 fprintf (sched_dump
, ";;\t\t| New pressure for model"
2218 fprintf (sched_dump
, MODEL_BAR
);
2222 fprintf (sched_dump
, ";;\t\t| %3d %4d %-30s ",
2223 point
, INSN_UID (insn
),
2224 str_pattern_slim (PATTERN (insn
)));
2225 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
2227 cl
= ira_pressure_classes
[pci
];
2228 ref_pressure
= MODEL_REF_PRESSURE (&model_before_pressure
,
2230 fprintf (sched_dump
, " %s:[%d->%d]",
2231 reg_class_names
[ira_pressure_classes
[pci
]],
2232 ref_pressure
, ref_pressure
+ delta
[cl
]);
2234 fprintf (sched_dump
, "\n");
2238 /* Adjust the pressure at POINT. Set MIX to nonzero if POINT - 1
2239 might have changed as well. */
2240 mix
= num_pending_births
;
2241 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
2243 cl
= ira_pressure_classes
[pci
];
2245 mix
|= model_update_pressure (&model_before_pressure
,
2246 point
, pci
, delta
[cl
]);
2249 while (mix
&& point
> model_curr_point
);
2252 fprintf (sched_dump
, MODEL_BAR
);
2255 /* After DEP, which was cancelled, has been resolved for insn NEXT,
2256 check whether the insn's pattern needs restoring. */
2258 must_restore_pattern_p (rtx next
, dep_t dep
)
2260 if (QUEUE_INDEX (next
) == QUEUE_SCHEDULED
)
2263 if (DEP_TYPE (dep
) == REG_DEP_CONTROL
)
2265 gcc_assert (ORIG_PAT (next
) != NULL_RTX
);
2266 gcc_assert (next
== DEP_CON (dep
));
2270 struct dep_replacement
*desc
= DEP_REPLACE (dep
);
2271 if (desc
->insn
!= next
)
2273 gcc_assert (*desc
->loc
== desc
->orig
);
2280 /* model_spill_cost (CL, P, P') returns the cost of increasing the
2281 pressure on CL from P to P'. We use this to calculate a "base ECC",
2282 baseECC (CL, X), for each pressure class CL and each instruction X.
2283 Supposing X changes the pressure on CL from P to P', and that the
2284 maximum pressure on CL in the current model schedule is MP', then:
2286 * if X occurs before or at the next point of maximum pressure in
2287 the model schedule and P' > MP', then:
2289 baseECC (CL, X) = model_spill_cost (CL, MP, P')
2291 The idea is that the pressure after scheduling a fixed set of
2292 instructions -- in this case, the set up to and including the
2293 next maximum pressure point -- is going to be the same regardless
2294 of the order; we simply want to keep the intermediate pressure
2295 under control. Thus X has a cost of zero unless scheduling it
2296 now would exceed MP'.
2298 If all increases in the set are by the same amount, no zero-cost
2299 instruction will ever cause the pressure to exceed MP'. However,
2300 if X is instead moved past an instruction X' with pressure in the
2301 range (MP' - (P' - P), MP'), the pressure at X' will increase
2302 beyond MP'. Since baseECC is very much a heuristic anyway,
2303 it doesn't seem worth the overhead of tracking cases like these.
2305 The cost of exceeding MP' is always based on the original maximum
2306 pressure MP. This is so that going 2 registers over the original
2307 limit has the same cost regardless of whether it comes from two
2308 separate +1 deltas or from a single +2 delta.
2310 * if X occurs after the next point of maximum pressure in the model
2311 schedule and P' > P, then:
2313 baseECC (CL, X) = model_spill_cost (CL, MP, MP' + (P' - P))
2315 That is, if we move X forward across a point of maximum pressure,
2316 and if X increases the pressure by P' - P, then we conservatively
2317 assume that scheduling X next would increase the maximum pressure
2318 by P' - P. Again, the cost of doing this is based on the original
2319 maximum pressure MP, for the same reason as above.
2321 * if P' < P, P > MP, and X occurs at or after the next point of
2322 maximum pressure, then:
2324 baseECC (CL, X) = -model_spill_cost (CL, MAX (MP, P'), P)
2326 That is, if we have already exceeded the original maximum pressure MP,
2327 and if X might reduce the maximum pressure again -- or at least push
2328 it further back, and thus allow more scheduling freedom -- it is given
2329 a negative cost to reflect the improvement.
2335 In this case, X is not expected to affect the maximum pressure MP',
2336 so it has zero cost.
2338 We then create a combined value baseECC (X) that is the sum of
2339 baseECC (CL, X) for each pressure class CL.
2341 baseECC (X) could itself be used as the ECC value described above.
2342 However, this is often too conservative, in the sense that it
2343 tends to make high-priority instructions that increase pressure
2344 wait too long in cases where introducing a spill would be better.
2345 For this reason the final ECC is a priority-adjusted form of
2346 baseECC (X). Specifically, we calculate:
2348 P (X) = INSN_PRIORITY (X) - insn_delay (X) - baseECC (X)
2349 baseP = MAX { P (X) | baseECC (X) <= 0 }
2353 ECC (X) = MAX (MIN (baseP - P (X), baseECC (X)), 0)
2355 Thus an instruction's effect on pressure is ignored if it has a high
2356 enough priority relative to the ones that don't increase pressure.
2357 Negative values of baseECC (X) do not increase the priority of X
2358 itself, but they do make it harder for other instructions to
2359 increase the pressure further.
2361 This pressure cost is deliberately timid. The intention has been
2362 to choose a heuristic that rarely interferes with the normal list
2363 scheduler in cases where that scheduler would produce good code.
2364 We simply want to curb some of its worst excesses. */
2366 /* Return the cost of increasing the pressure in class CL from FROM to TO.
2368 Here we use the very simplistic cost model that every register above
2369 sched_class_regs_num[CL] has a spill cost of 1. We could use other
2370 measures instead, such as one based on MEMORY_MOVE_COST. However:
2372 (1) In order for an instruction to be scheduled, the higher cost
2373 would need to be justified in a single saving of that many stalls.
2374 This is overly pessimistic, because the benefit of spilling is
2375 often to avoid a sequence of several short stalls rather than
2378 (2) The cost is still arbitrary. Because we are not allocating
2379 registers during scheduling, we have no way of knowing for
2380 sure how many memory accesses will be required by each spill,
2381 where the spills will be placed within the block, or even
2382 which block(s) will contain the spills.
2384 So a higher cost than 1 is often too conservative in practice,
2385 forcing blocks to contain unnecessary stalls instead of spill code.
2386 The simple cost below seems to be the best compromise. It reduces
2387 the interference with the normal list scheduler, which helps make
2388 it more suitable for a default-on option. */
2391 model_spill_cost (int cl
, int from
, int to
)
2393 from
= MAX (from
, sched_class_regs_num
[cl
]);
2394 return MAX (to
, from
) - from
;
2397 /* Return baseECC (ira_pressure_classes[PCI], POINT), given that
2398 P = curr_reg_pressure[ira_pressure_classes[PCI]] and that
2402 model_excess_group_cost (struct model_pressure_group
*group
,
2403 int point
, int pci
, int delta
)
2407 cl
= ira_pressure_classes
[pci
];
2408 if (delta
< 0 && point
>= group
->limits
[pci
].point
)
2410 pressure
= MAX (group
->limits
[pci
].orig_pressure
,
2411 curr_reg_pressure
[cl
] + delta
);
2412 return -model_spill_cost (cl
, pressure
, curr_reg_pressure
[cl
]);
2417 if (point
> group
->limits
[pci
].point
)
2418 pressure
= group
->limits
[pci
].pressure
+ delta
;
2420 pressure
= curr_reg_pressure
[cl
] + delta
;
2422 if (pressure
> group
->limits
[pci
].pressure
)
2423 return model_spill_cost (cl
, group
->limits
[pci
].orig_pressure
,
2430 /* Return baseECC (MODEL_INSN (INSN)). Dump the costs to sched_dump
2434 model_excess_cost (rtx insn
, bool print_p
)
2436 int point
, pci
, cl
, cost
, this_cost
, delta
;
2437 struct reg_pressure_data
*insn_reg_pressure
;
2438 int insn_death
[N_REG_CLASSES
];
2440 calculate_reg_deaths (insn
, insn_death
);
2441 point
= model_index (insn
);
2442 insn_reg_pressure
= INSN_REG_PRESSURE (insn
);
2446 fprintf (sched_dump
, ";;\t\t| %3d %4d | %4d %+3d |", point
,
2447 INSN_UID (insn
), INSN_PRIORITY (insn
), insn_delay (insn
));
2449 /* Sum up the individual costs for each register class. */
2450 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
2452 cl
= ira_pressure_classes
[pci
];
2453 delta
= insn_reg_pressure
[pci
].set_increase
- insn_death
[cl
];
2454 this_cost
= model_excess_group_cost (&model_before_pressure
,
2458 fprintf (sched_dump
, " %s:[%d base cost %d]",
2459 reg_class_names
[cl
], delta
, this_cost
);
2463 fprintf (sched_dump
, "\n");
2468 /* Dump the next points of maximum pressure for GROUP. */
2471 model_dump_pressure_points (struct model_pressure_group
*group
)
2475 fprintf (sched_dump
, ";;\t\t| pressure points");
2476 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
2478 cl
= ira_pressure_classes
[pci
];
2479 fprintf (sched_dump
, " %s:[%d->%d at ", reg_class_names
[cl
],
2480 curr_reg_pressure
[cl
], group
->limits
[pci
].pressure
);
2481 if (group
->limits
[pci
].point
< model_num_insns
)
2482 fprintf (sched_dump
, "%d:%d]", group
->limits
[pci
].point
,
2483 INSN_UID (MODEL_INSN (group
->limits
[pci
].point
)));
2485 fprintf (sched_dump
, "end]");
2487 fprintf (sched_dump
, "\n");
2490 /* Set INSN_REG_PRESSURE_EXCESS_COST_CHANGE for INSNS[0...COUNT-1]. */
2493 model_set_excess_costs (rtx
*insns
, int count
)
2495 int i
, cost
, priority_base
, priority
;
2498 /* Record the baseECC value for each instruction in the model schedule,
2499 except that negative costs are converted to zero ones now rather than
2500 later. Do not assign a cost to debug instructions, since they must
2501 not change code-generation decisions. Experiments suggest we also
2502 get better results by not assigning a cost to instructions from
2505 Set PRIORITY_BASE to baseP in the block comment above. This is the
2506 maximum priority of the "cheap" instructions, which should always
2507 include the next model instruction. */
2510 for (i
= 0; i
< count
; i
++)
2511 if (INSN_MODEL_INDEX (insns
[i
]))
2513 if (sched_verbose
>= 6 && !print_p
)
2515 fprintf (sched_dump
, MODEL_BAR
);
2516 fprintf (sched_dump
, ";;\t\t| Pressure costs for ready queue\n");
2517 model_dump_pressure_points (&model_before_pressure
);
2518 fprintf (sched_dump
, MODEL_BAR
);
2521 cost
= model_excess_cost (insns
[i
], print_p
);
2524 priority
= INSN_PRIORITY (insns
[i
]) - insn_delay (insns
[i
]) - cost
;
2525 priority_base
= MAX (priority_base
, priority
);
2528 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insns
[i
]) = cost
;
2531 fprintf (sched_dump
, MODEL_BAR
);
2533 /* Use MAX (baseECC, 0) and baseP to calculcate ECC for each
2535 for (i
= 0; i
< count
; i
++)
2537 cost
= INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insns
[i
]);
2538 priority
= INSN_PRIORITY (insns
[i
]) - insn_delay (insns
[i
]);
2539 if (cost
> 0 && priority
> priority_base
)
2541 cost
+= priority_base
- priority
;
2542 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insns
[i
]) = MAX (cost
, 0);
2548 /* Enum of rank_for_schedule heuristic decisions. */
2550 RFS_LIVE_RANGE_SHRINK1
, RFS_LIVE_RANGE_SHRINK2
,
2551 RFS_SCHED_GROUP
, RFS_PRESSURE_DELAY
, RFS_PRESSURE_TICK
,
2552 RFS_FEEDS_BACKTRACK_INSN
, RFS_PRIORITY
, RFS_SPECULATION
,
2553 RFS_SCHED_RANK
, RFS_LAST_INSN
, RFS_PRESSURE_INDEX
,
2554 RFS_DEP_COUNT
, RFS_TIE
, RFS_N
};
2556 /* Corresponding strings for print outs. */
2557 static const char *rfs_str
[RFS_N
] = {
2558 "RFS_LIVE_RANGE_SHRINK1", "RFS_LIVE_RANGE_SHRINK2",
2559 "RFS_SCHED_GROUP", "RFS_PRESSURE_DELAY", "RFS_PRESSURE_TICK",
2560 "RFS_FEEDS_BACKTRACK_INSN", "RFS_PRIORITY", "RFS_SPECULATION",
2561 "RFS_SCHED_RANK", "RFS_LAST_INSN", "RFS_PRESSURE_INDEX",
2562 "RFS_DEP_COUNT", "RFS_TIE" };
2564 /* Statistical breakdown of rank_for_schedule decisions. */
2565 typedef struct { unsigned stats
[RFS_N
]; } rank_for_schedule_stats_t
;
2566 static rank_for_schedule_stats_t rank_for_schedule_stats
;
2568 /* Return the result of comparing insns TMP and TMP2 and update
2569 Rank_For_Schedule statistics. */
2571 rfs_result (enum rfs_decision decision
, int result
, rtx tmp
, rtx tmp2
)
2573 ++rank_for_schedule_stats
.stats
[decision
];
2575 INSN_LAST_RFS_WIN (tmp
) = decision
;
2576 else if (result
> 0)
2577 INSN_LAST_RFS_WIN (tmp2
) = decision
;
2583 /* Sorting predicate to move DEBUG_INSNs to the top of ready list, while
2584 keeping normal insns in original order. */
2587 rank_for_schedule_debug (const void *x
, const void *y
)
2589 rtx tmp
= *(rtx
const *) y
;
2590 rtx tmp2
= *(rtx
const *) x
;
2592 /* Schedule debug insns as early as possible. */
2593 if (DEBUG_INSN_P (tmp
) && !DEBUG_INSN_P (tmp2
))
2595 else if (!DEBUG_INSN_P (tmp
) && DEBUG_INSN_P (tmp2
))
2597 else if (DEBUG_INSN_P (tmp
) && DEBUG_INSN_P (tmp2
))
2598 return INSN_LUID (tmp
) - INSN_LUID (tmp2
);
2600 return INSN_RFS_DEBUG_ORIG_ORDER (tmp2
) - INSN_RFS_DEBUG_ORIG_ORDER (tmp
);
2603 /* Returns a positive value if x is preferred; returns a negative value if
2604 y is preferred. Should never return 0, since that will make the sort
2608 rank_for_schedule (const void *x
, const void *y
)
2610 rtx tmp
= *(const rtx
*) y
;
2611 rtx tmp2
= *(const rtx
*) x
;
2612 int tmp_class
, tmp2_class
;
2613 int val
, priority_val
, info_val
, diff
;
2615 if (live_range_shrinkage_p
)
2617 /* Don't use SCHED_PRESSURE_MODEL -- it results in much worse
2619 gcc_assert (sched_pressure
== SCHED_PRESSURE_WEIGHTED
);
2620 if ((INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp
) < 0
2621 || INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp2
) < 0)
2622 && (diff
= (INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp
)
2623 - INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp2
))) != 0)
2624 return rfs_result (RFS_LIVE_RANGE_SHRINK1
, diff
, tmp
, tmp2
);
2625 /* Sort by INSN_LUID (original insn order), so that we make the
2626 sort stable. This minimizes instruction movement, thus
2627 minimizing sched's effect on debugging and cross-jumping. */
2628 return rfs_result (RFS_LIVE_RANGE_SHRINK2
,
2629 INSN_LUID (tmp
) - INSN_LUID (tmp2
), tmp
, tmp2
);
2632 /* The insn in a schedule group should be issued the first. */
2633 if (flag_sched_group_heuristic
&&
2634 SCHED_GROUP_P (tmp
) != SCHED_GROUP_P (tmp2
))
2635 return rfs_result (RFS_SCHED_GROUP
, SCHED_GROUP_P (tmp2
) ? 1 : -1,
2638 /* Make sure that priority of TMP and TMP2 are initialized. */
2639 gcc_assert (INSN_PRIORITY_KNOWN (tmp
) && INSN_PRIORITY_KNOWN (tmp2
));
2641 if (sched_pressure
!= SCHED_PRESSURE_NONE
)
2643 /* Prefer insn whose scheduling results in the smallest register
2645 if ((diff
= (INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp
)
2647 - INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp2
)
2648 - insn_delay (tmp2
))))
2649 return rfs_result (RFS_PRESSURE_DELAY
, diff
, tmp
, tmp2
);
2652 if (sched_pressure
!= SCHED_PRESSURE_NONE
2653 && (INSN_TICK (tmp2
) > clock_var
|| INSN_TICK (tmp
) > clock_var
)
2654 && INSN_TICK (tmp2
) != INSN_TICK (tmp
))
2656 diff
= INSN_TICK (tmp
) - INSN_TICK (tmp2
);
2657 return rfs_result (RFS_PRESSURE_TICK
, diff
, tmp
, tmp2
);
2660 /* If we are doing backtracking in this schedule, prefer insns that
2661 have forward dependencies with negative cost against an insn that
2662 was already scheduled. */
2663 if (current_sched_info
->flags
& DO_BACKTRACKING
)
2665 priority_val
= FEEDS_BACKTRACK_INSN (tmp2
) - FEEDS_BACKTRACK_INSN (tmp
);
2667 return rfs_result (RFS_FEEDS_BACKTRACK_INSN
, priority_val
, tmp
, tmp2
);
2670 /* Prefer insn with higher priority. */
2671 priority_val
= INSN_PRIORITY (tmp2
) - INSN_PRIORITY (tmp
);
2673 if (flag_sched_critical_path_heuristic
&& priority_val
)
2674 return rfs_result (RFS_PRIORITY
, priority_val
, tmp
, tmp2
);
2676 if (PARAM_VALUE (PARAM_SCHED_AUTOPREF_QUEUE_DEPTH
) >= 0)
2678 int autopref
= autopref_rank_for_schedule (tmp
, tmp2
);
2683 /* Prefer speculative insn with greater dependencies weakness. */
2684 if (flag_sched_spec_insn_heuristic
&& spec_info
)
2690 ds1
= TODO_SPEC (tmp
) & SPECULATIVE
;
2692 dw1
= ds_weak (ds1
);
2696 ds2
= TODO_SPEC (tmp2
) & SPECULATIVE
;
2698 dw2
= ds_weak (ds2
);
2703 if (dw
> (NO_DEP_WEAK
/ 8) || dw
< -(NO_DEP_WEAK
/ 8))
2704 return rfs_result (RFS_SPECULATION
, dw
, tmp
, tmp2
);
2707 info_val
= (*current_sched_info
->rank
) (tmp
, tmp2
);
2708 if (flag_sched_rank_heuristic
&& info_val
)
2709 return rfs_result (RFS_SCHED_RANK
, info_val
, tmp
, tmp2
);
2711 /* Compare insns based on their relation to the last scheduled
2713 if (flag_sched_last_insn_heuristic
&& last_nondebug_scheduled_insn
)
2717 rtx last
= last_nondebug_scheduled_insn
;
2719 /* Classify the instructions into three classes:
2720 1) Data dependent on last schedule insn.
2721 2) Anti/Output dependent on last scheduled insn.
2722 3) Independent of last scheduled insn, or has latency of one.
2723 Choose the insn from the highest numbered class if different. */
2724 dep1
= sd_find_dep_between (last
, tmp
, true);
2726 if (dep1
== NULL
|| dep_cost (dep1
) == 1)
2728 else if (/* Data dependence. */
2729 DEP_TYPE (dep1
) == REG_DEP_TRUE
)
2734 dep2
= sd_find_dep_between (last
, tmp2
, true);
2736 if (dep2
== NULL
|| dep_cost (dep2
) == 1)
2738 else if (/* Data dependence. */
2739 DEP_TYPE (dep2
) == REG_DEP_TRUE
)
2744 if ((val
= tmp2_class
- tmp_class
))
2745 return rfs_result (RFS_LAST_INSN
, val
, tmp
, tmp2
);
2748 /* Prefer instructions that occur earlier in the model schedule. */
2749 if (sched_pressure
== SCHED_PRESSURE_MODEL
2750 && INSN_BB (tmp
) == target_bb
&& INSN_BB (tmp2
) == target_bb
)
2752 diff
= model_index (tmp
) - model_index (tmp2
);
2753 gcc_assert (diff
!= 0);
2754 return rfs_result (RFS_PRESSURE_INDEX
, diff
, tmp
, tmp2
);
2757 /* Prefer the insn which has more later insns that depend on it.
2758 This gives the scheduler more freedom when scheduling later
2759 instructions at the expense of added register pressure. */
2761 val
= (dep_list_size (tmp2
, SD_LIST_FORW
)
2762 - dep_list_size (tmp
, SD_LIST_FORW
));
2764 if (flag_sched_dep_count_heuristic
&& val
!= 0)
2765 return rfs_result (RFS_DEP_COUNT
, val
, tmp
, tmp2
);
2767 /* If insns are equally good, sort by INSN_LUID (original insn order),
2768 so that we make the sort stable. This minimizes instruction movement,
2769 thus minimizing sched's effect on debugging and cross-jumping. */
2770 return rfs_result (RFS_TIE
, INSN_LUID (tmp
) - INSN_LUID (tmp2
), tmp
, tmp2
);
2773 /* Resort the array A in which only element at index N may be out of order. */
2775 HAIFA_INLINE
static void
2776 swap_sort (rtx
*a
, int n
)
2778 rtx insn
= a
[n
- 1];
2781 while (i
>= 0 && rank_for_schedule (a
+ i
, &insn
) >= 0)
2789 /* Add INSN to the insn queue so that it can be executed at least
2790 N_CYCLES after the currently executing insn. Preserve insns
2791 chain for debugging purposes. REASON will be printed in debugging
2794 HAIFA_INLINE
static void
2795 queue_insn (rtx insn
, int n_cycles
, const char *reason
)
2797 int next_q
= NEXT_Q_AFTER (q_ptr
, n_cycles
);
2798 rtx link
= alloc_INSN_LIST (insn
, insn_queue
[next_q
]);
2801 gcc_assert (n_cycles
<= max_insn_queue_index
);
2802 gcc_assert (!DEBUG_INSN_P (insn
));
2804 insn_queue
[next_q
] = link
;
2807 if (sched_verbose
>= 2)
2809 fprintf (sched_dump
, ";;\t\tReady-->Q: insn %s: ",
2810 (*current_sched_info
->print_insn
) (insn
, 0));
2812 fprintf (sched_dump
, "queued for %d cycles (%s).\n", n_cycles
, reason
);
2815 QUEUE_INDEX (insn
) = next_q
;
2817 if (current_sched_info
->flags
& DO_BACKTRACKING
)
2819 new_tick
= clock_var
+ n_cycles
;
2820 if (INSN_TICK (insn
) == INVALID_TICK
|| INSN_TICK (insn
) < new_tick
)
2821 INSN_TICK (insn
) = new_tick
;
2823 if (INSN_EXACT_TICK (insn
) != INVALID_TICK
2824 && INSN_EXACT_TICK (insn
) < clock_var
+ n_cycles
)
2826 must_backtrack
= true;
2827 if (sched_verbose
>= 2)
2828 fprintf (sched_dump
, ";;\t\tcausing a backtrack.\n");
2833 /* Remove INSN from queue. */
2835 queue_remove (rtx insn
)
2837 gcc_assert (QUEUE_INDEX (insn
) >= 0);
2838 remove_free_INSN_LIST_elem (insn
, &insn_queue
[QUEUE_INDEX (insn
)]);
2840 QUEUE_INDEX (insn
) = QUEUE_NOWHERE
;
2843 /* Return a pointer to the bottom of the ready list, i.e. the insn
2844 with the lowest priority. */
2847 ready_lastpos (struct ready_list
*ready
)
2849 gcc_assert (ready
->n_ready
>= 1);
2850 return ready
->vec
+ ready
->first
- ready
->n_ready
+ 1;
2853 /* Add an element INSN to the ready list so that it ends up with the
2854 lowest/highest priority depending on FIRST_P. */
2856 HAIFA_INLINE
static void
2857 ready_add (struct ready_list
*ready
, rtx insn
, bool first_p
)
2861 if (ready
->first
== ready
->n_ready
)
2863 memmove (ready
->vec
+ ready
->veclen
- ready
->n_ready
,
2864 ready_lastpos (ready
),
2865 ready
->n_ready
* sizeof (rtx
));
2866 ready
->first
= ready
->veclen
- 1;
2868 ready
->vec
[ready
->first
- ready
->n_ready
] = insn
;
2872 if (ready
->first
== ready
->veclen
- 1)
2875 /* ready_lastpos() fails when called with (ready->n_ready == 0). */
2876 memmove (ready
->vec
+ ready
->veclen
- ready
->n_ready
- 1,
2877 ready_lastpos (ready
),
2878 ready
->n_ready
* sizeof (rtx
));
2879 ready
->first
= ready
->veclen
- 2;
2881 ready
->vec
[++(ready
->first
)] = insn
;
2885 if (DEBUG_INSN_P (insn
))
2888 gcc_assert (QUEUE_INDEX (insn
) != QUEUE_READY
);
2889 QUEUE_INDEX (insn
) = QUEUE_READY
;
2891 if (INSN_EXACT_TICK (insn
) != INVALID_TICK
2892 && INSN_EXACT_TICK (insn
) < clock_var
)
2894 must_backtrack
= true;
2898 /* Remove the element with the highest priority from the ready list and
2901 HAIFA_INLINE
static rtx
2902 ready_remove_first (struct ready_list
*ready
)
2906 gcc_assert (ready
->n_ready
);
2907 t
= ready
->vec
[ready
->first
--];
2909 if (DEBUG_INSN_P (t
))
2911 /* If the queue becomes empty, reset it. */
2912 if (ready
->n_ready
== 0)
2913 ready
->first
= ready
->veclen
- 1;
2915 gcc_assert (QUEUE_INDEX (t
) == QUEUE_READY
);
2916 QUEUE_INDEX (t
) = QUEUE_NOWHERE
;
2921 /* The following code implements multi-pass scheduling for the first
2922 cycle. In other words, we will try to choose ready insn which
2923 permits to start maximum number of insns on the same cycle. */
2925 /* Return a pointer to the element INDEX from the ready. INDEX for
2926 insn with the highest priority is 0, and the lowest priority has
2930 ready_element (struct ready_list
*ready
, int index
)
2932 gcc_assert (ready
->n_ready
&& index
< ready
->n_ready
);
2934 return ready
->vec
[ready
->first
- index
];
2937 /* Remove the element INDEX from the ready list and return it. INDEX
2938 for insn with the highest priority is 0, and the lowest priority
2941 HAIFA_INLINE
static rtx
2942 ready_remove (struct ready_list
*ready
, int index
)
2948 return ready_remove_first (ready
);
2949 gcc_assert (ready
->n_ready
&& index
< ready
->n_ready
);
2950 t
= ready
->vec
[ready
->first
- index
];
2952 if (DEBUG_INSN_P (t
))
2954 for (i
= index
; i
< ready
->n_ready
; i
++)
2955 ready
->vec
[ready
->first
- i
] = ready
->vec
[ready
->first
- i
- 1];
2956 QUEUE_INDEX (t
) = QUEUE_NOWHERE
;
2960 /* Remove INSN from the ready list. */
2962 ready_remove_insn (rtx insn
)
2966 for (i
= 0; i
< readyp
->n_ready
; i
++)
2967 if (ready_element (readyp
, i
) == insn
)
2969 ready_remove (readyp
, i
);
2975 /* Calculate difference of two statistics set WAS and NOW.
2976 Result returned in WAS. */
2978 rank_for_schedule_stats_diff (rank_for_schedule_stats_t
*was
,
2979 const rank_for_schedule_stats_t
*now
)
2981 for (int i
= 0; i
< RFS_N
; ++i
)
2982 was
->stats
[i
] = now
->stats
[i
] - was
->stats
[i
];
2985 /* Print rank_for_schedule statistics. */
2987 print_rank_for_schedule_stats (const char *prefix
,
2988 const rank_for_schedule_stats_t
*stats
,
2989 struct ready_list
*ready
)
2991 for (int i
= 0; i
< RFS_N
; ++i
)
2992 if (stats
->stats
[i
])
2994 fprintf (sched_dump
, "%s%20s: %u", prefix
, rfs_str
[i
], stats
->stats
[i
]);
2997 /* Print out insns that won due to RFS_<I>. */
2999 rtx
*p
= ready_lastpos (ready
);
3001 fprintf (sched_dump
, ":");
3002 /* Start with 1 since least-priority insn didn't have any wins. */
3003 for (int j
= 1; j
< ready
->n_ready
; ++j
)
3004 if (INSN_LAST_RFS_WIN (p
[j
]) == i
)
3005 fprintf (sched_dump
, " %s",
3006 (*current_sched_info
->print_insn
) (p
[j
], 0));
3008 fprintf (sched_dump
, "\n");
3012 /* Separate DEBUG_INSNS from normal insns. DEBUG_INSNs go to the end
3015 ready_sort_debug (struct ready_list
*ready
)
3018 rtx
*first
= ready_lastpos (ready
);
3020 for (i
= 0; i
< ready
->n_ready
; ++i
)
3021 if (!DEBUG_INSN_P (first
[i
]))
3022 INSN_RFS_DEBUG_ORIG_ORDER (first
[i
]) = i
;
3024 qsort (first
, ready
->n_ready
, sizeof (rtx
), rank_for_schedule_debug
);
3027 /* Sort non-debug insns in the ready list READY by ascending priority.
3028 Assumes that all debug insns are separated from the real insns. */
3030 ready_sort_real (struct ready_list
*ready
)
3033 rtx
*first
= ready_lastpos (ready
);
3034 int n_ready_real
= ready
->n_ready
- ready
->n_debug
;
3036 if (sched_pressure
== SCHED_PRESSURE_WEIGHTED
)
3037 for (i
= 0; i
< n_ready_real
; ++i
)
3038 setup_insn_reg_pressure_info (first
[i
]);
3039 else if (sched_pressure
== SCHED_PRESSURE_MODEL
3040 && model_curr_point
< model_num_insns
)
3041 model_set_excess_costs (first
, n_ready_real
);
3043 rank_for_schedule_stats_t stats1
;
3044 if (sched_verbose
>= 4)
3045 stats1
= rank_for_schedule_stats
;
3047 if (n_ready_real
== 2)
3048 swap_sort (first
, n_ready_real
);
3049 else if (n_ready_real
> 2)
3050 qsort (first
, n_ready_real
, sizeof (rtx
), rank_for_schedule
);
3052 if (sched_verbose
>= 4)
3054 rank_for_schedule_stats_diff (&stats1
, &rank_for_schedule_stats
);
3055 print_rank_for_schedule_stats (";;\t\t", &stats1
, ready
);
3059 /* Sort the ready list READY by ascending priority. */
3061 ready_sort (struct ready_list
*ready
)
3063 if (ready
->n_debug
> 0)
3064 ready_sort_debug (ready
);
3066 ready_sort_real (ready
);
3069 /* PREV is an insn that is ready to execute. Adjust its priority if that
3070 will help shorten or lengthen register lifetimes as appropriate. Also
3071 provide a hook for the target to tweak itself. */
3073 HAIFA_INLINE
static void
3074 adjust_priority (rtx prev
)
3076 /* ??? There used to be code here to try and estimate how an insn
3077 affected register lifetimes, but it did it by looking at REG_DEAD
3078 notes, which we removed in schedule_region. Nor did it try to
3079 take into account register pressure or anything useful like that.
3081 Revisit when we have a machine model to work with and not before. */
3083 if (targetm
.sched
.adjust_priority
)
3084 INSN_PRIORITY (prev
) =
3085 targetm
.sched
.adjust_priority (prev
, INSN_PRIORITY (prev
));
3088 /* Advance DFA state STATE on one cycle. */
3090 advance_state (state_t state
)
3092 if (targetm
.sched
.dfa_pre_advance_cycle
)
3093 targetm
.sched
.dfa_pre_advance_cycle ();
3095 if (targetm
.sched
.dfa_pre_cycle_insn
)
3096 state_transition (state
,
3097 targetm
.sched
.dfa_pre_cycle_insn ());
3099 state_transition (state
, NULL
);
3101 if (targetm
.sched
.dfa_post_cycle_insn
)
3102 state_transition (state
,
3103 targetm
.sched
.dfa_post_cycle_insn ());
3105 if (targetm
.sched
.dfa_post_advance_cycle
)
3106 targetm
.sched
.dfa_post_advance_cycle ();
3109 /* Advance time on one cycle. */
3110 HAIFA_INLINE
static void
3111 advance_one_cycle (void)
3113 advance_state (curr_state
);
3114 if (sched_verbose
>= 4)
3115 fprintf (sched_dump
, ";;\tAdvance the current state.\n");
3118 /* Update register pressure after scheduling INSN. */
3120 update_register_pressure (rtx insn
)
3122 struct reg_use_data
*use
;
3123 struct reg_set_data
*set
;
3125 gcc_checking_assert (!DEBUG_INSN_P (insn
));
3127 for (use
= INSN_REG_USE_LIST (insn
); use
!= NULL
; use
= use
->next_insn_use
)
3128 if (dying_use_p (use
))
3129 mark_regno_birth_or_death (curr_reg_live
, curr_reg_pressure
,
3131 for (set
= INSN_REG_SET_LIST (insn
); set
!= NULL
; set
= set
->next_insn_set
)
3132 mark_regno_birth_or_death (curr_reg_live
, curr_reg_pressure
,
3136 /* Set up or update (if UPDATE_P) max register pressure (see its
3137 meaning in sched-int.h::_haifa_insn_data) for all current BB insns
3138 after insn AFTER. */
3140 setup_insn_max_reg_pressure (rtx after
, bool update_p
)
3145 static int max_reg_pressure
[N_REG_CLASSES
];
3147 save_reg_pressure ();
3148 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
3149 max_reg_pressure
[ira_pressure_classes
[i
]]
3150 = curr_reg_pressure
[ira_pressure_classes
[i
]];
3151 for (insn
= NEXT_INSN (after
);
3152 insn
!= NULL_RTX
&& ! BARRIER_P (insn
)
3153 && BLOCK_FOR_INSN (insn
) == BLOCK_FOR_INSN (after
);
3154 insn
= NEXT_INSN (insn
))
3155 if (NONDEBUG_INSN_P (insn
))
3158 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
3160 p
= max_reg_pressure
[ira_pressure_classes
[i
]];
3161 if (INSN_MAX_REG_PRESSURE (insn
)[i
] != p
)
3164 INSN_MAX_REG_PRESSURE (insn
)[i
]
3165 = max_reg_pressure
[ira_pressure_classes
[i
]];
3168 if (update_p
&& eq_p
)
3170 update_register_pressure (insn
);
3171 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
3172 if (max_reg_pressure
[ira_pressure_classes
[i
]]
3173 < curr_reg_pressure
[ira_pressure_classes
[i
]])
3174 max_reg_pressure
[ira_pressure_classes
[i
]]
3175 = curr_reg_pressure
[ira_pressure_classes
[i
]];
3177 restore_reg_pressure ();
3180 /* Update the current register pressure after scheduling INSN. Update
3181 also max register pressure for unscheduled insns of the current
3184 update_reg_and_insn_max_reg_pressure (rtx insn
)
3187 int before
[N_REG_CLASSES
];
3189 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
3190 before
[i
] = curr_reg_pressure
[ira_pressure_classes
[i
]];
3191 update_register_pressure (insn
);
3192 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
3193 if (curr_reg_pressure
[ira_pressure_classes
[i
]] != before
[i
])
3195 if (i
< ira_pressure_classes_num
)
3196 setup_insn_max_reg_pressure (insn
, true);
3199 /* Set up register pressure at the beginning of basic block BB whose
3200 insns starting after insn AFTER. Set up also max register pressure
3201 for all insns of the basic block. */
3203 sched_setup_bb_reg_pressure_info (basic_block bb
, rtx after
)
3205 gcc_assert (sched_pressure
== SCHED_PRESSURE_WEIGHTED
);
3206 initiate_bb_reg_pressure_info (bb
);
3207 setup_insn_max_reg_pressure (after
, false);
3210 /* If doing predication while scheduling, verify whether INSN, which
3211 has just been scheduled, clobbers the conditions of any
3212 instructions that must be predicated in order to break their
3213 dependencies. If so, remove them from the queues so that they will
3214 only be scheduled once their control dependency is resolved. */
3217 check_clobbered_conditions (rtx insn
)
3222 if ((current_sched_info
->flags
& DO_PREDICATION
) == 0)
3225 find_all_hard_reg_sets (insn
, &t
);
3228 for (i
= 0; i
< ready
.n_ready
; i
++)
3230 rtx x
= ready_element (&ready
, i
);
3231 if (TODO_SPEC (x
) == DEP_CONTROL
&& cond_clobbered_p (x
, t
))
3233 ready_remove_insn (x
);
3237 for (i
= 0; i
<= max_insn_queue_index
; i
++)
3240 int q
= NEXT_Q_AFTER (q_ptr
, i
);
3243 for (link
= insn_queue
[q
]; link
; link
= XEXP (link
, 1))
3245 rtx x
= XEXP (link
, 0);
3246 if (TODO_SPEC (x
) == DEP_CONTROL
&& cond_clobbered_p (x
, t
))
3255 /* Return (in order):
3257 - positive if INSN adversely affects the pressure on one
3260 - negative if INSN reduces the pressure on one register class
3262 - 0 if INSN doesn't affect the pressure on any register class. */
3265 model_classify_pressure (struct model_insn_info
*insn
)
3267 struct reg_pressure_data
*reg_pressure
;
3268 int death
[N_REG_CLASSES
];
3271 calculate_reg_deaths (insn
->insn
, death
);
3272 reg_pressure
= INSN_REG_PRESSURE (insn
->insn
);
3274 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
3276 cl
= ira_pressure_classes
[pci
];
3277 if (death
[cl
] < reg_pressure
[pci
].set_increase
)
3279 sum
+= reg_pressure
[pci
].set_increase
- death
[cl
];
3284 /* Return true if INSN1 should come before INSN2 in the model schedule. */
3287 model_order_p (struct model_insn_info
*insn1
, struct model_insn_info
*insn2
)
3289 unsigned int height1
, height2
;
3290 unsigned int priority1
, priority2
;
3292 /* Prefer instructions with a higher model priority. */
3293 if (insn1
->model_priority
!= insn2
->model_priority
)
3294 return insn1
->model_priority
> insn2
->model_priority
;
3296 /* Combine the length of the longest path of satisfied true dependencies
3297 that leads to each instruction (depth) with the length of the longest
3298 path of any dependencies that leads from the instruction (alap).
3299 Prefer instructions with the greatest combined length. If the combined
3300 lengths are equal, prefer instructions with the greatest depth.
3302 The idea is that, if we have a set S of "equal" instructions that each
3303 have ALAP value X, and we pick one such instruction I, any true-dependent
3304 successors of I that have ALAP value X - 1 should be preferred over S.
3305 This encourages the schedule to be "narrow" rather than "wide".
3306 However, if I is a low-priority instruction that we decided to
3307 schedule because of its model_classify_pressure, and if there
3308 is a set of higher-priority instructions T, the aforementioned
3309 successors of I should not have the edge over T. */
3310 height1
= insn1
->depth
+ insn1
->alap
;
3311 height2
= insn2
->depth
+ insn2
->alap
;
3312 if (height1
!= height2
)
3313 return height1
> height2
;
3314 if (insn1
->depth
!= insn2
->depth
)
3315 return insn1
->depth
> insn2
->depth
;
3317 /* We have no real preference between INSN1 an INSN2 as far as attempts
3318 to reduce pressure go. Prefer instructions with higher priorities. */
3319 priority1
= INSN_PRIORITY (insn1
->insn
);
3320 priority2
= INSN_PRIORITY (insn2
->insn
);
3321 if (priority1
!= priority2
)
3322 return priority1
> priority2
;
3324 /* Use the original rtl sequence as a tie-breaker. */
3325 return insn1
< insn2
;
3328 /* Add INSN to the model worklist immediately after PREV. Add it to the
3329 beginning of the list if PREV is null. */
3332 model_add_to_worklist_at (struct model_insn_info
*insn
,
3333 struct model_insn_info
*prev
)
3335 gcc_assert (QUEUE_INDEX (insn
->insn
) == QUEUE_NOWHERE
);
3336 QUEUE_INDEX (insn
->insn
) = QUEUE_READY
;
3341 insn
->next
= prev
->next
;
3346 insn
->next
= model_worklist
;
3347 model_worklist
= insn
;
3350 insn
->next
->prev
= insn
;
3353 /* Remove INSN from the model worklist. */
3356 model_remove_from_worklist (struct model_insn_info
*insn
)
3358 gcc_assert (QUEUE_INDEX (insn
->insn
) == QUEUE_READY
);
3359 QUEUE_INDEX (insn
->insn
) = QUEUE_NOWHERE
;
3362 insn
->prev
->next
= insn
->next
;
3364 model_worklist
= insn
->next
;
3366 insn
->next
->prev
= insn
->prev
;
3369 /* Add INSN to the model worklist. Start looking for a suitable position
3370 between neighbors PREV and NEXT, testing at most MAX_SCHED_READY_INSNS
3371 insns either side. A null PREV indicates the beginning of the list and
3372 a null NEXT indicates the end. */
3375 model_add_to_worklist (struct model_insn_info
*insn
,
3376 struct model_insn_info
*prev
,
3377 struct model_insn_info
*next
)
3381 count
= MAX_SCHED_READY_INSNS
;
3382 if (count
> 0 && prev
&& model_order_p (insn
, prev
))
3388 while (count
> 0 && prev
&& model_order_p (insn
, prev
));
3390 while (count
> 0 && next
&& model_order_p (next
, insn
))
3396 model_add_to_worklist_at (insn
, prev
);
3399 /* INSN may now have a higher priority (in the model_order_p sense)
3400 than before. Move it up the worklist if necessary. */
3403 model_promote_insn (struct model_insn_info
*insn
)
3405 struct model_insn_info
*prev
;
3409 count
= MAX_SCHED_READY_INSNS
;
3410 while (count
> 0 && prev
&& model_order_p (insn
, prev
))
3415 if (prev
!= insn
->prev
)
3417 model_remove_from_worklist (insn
);
3418 model_add_to_worklist_at (insn
, prev
);
3422 /* Add INSN to the end of the model schedule. */
3425 model_add_to_schedule (rtx insn
)
3429 gcc_assert (QUEUE_INDEX (insn
) == QUEUE_NOWHERE
);
3430 QUEUE_INDEX (insn
) = QUEUE_SCHEDULED
;
3432 point
= model_schedule
.length ();
3433 model_schedule
.quick_push (insn
);
3434 INSN_MODEL_INDEX (insn
) = point
+ 1;
3437 /* Analyze the instructions that are to be scheduled, setting up
3438 MODEL_INSN_INFO (...) and model_num_insns accordingly. Add ready
3439 instructions to model_worklist. */
3442 model_analyze_insns (void)
3444 rtx start
, end
, iter
;
3445 sd_iterator_def sd_it
;
3447 struct model_insn_info
*insn
, *con
;
3449 model_num_insns
= 0;
3450 start
= PREV_INSN (current_sched_info
->next_tail
);
3451 end
= current_sched_info
->prev_head
;
3452 for (iter
= start
; iter
!= end
; iter
= PREV_INSN (iter
))
3453 if (NONDEBUG_INSN_P (iter
))
3455 insn
= MODEL_INSN_INFO (iter
);
3457 FOR_EACH_DEP (iter
, SD_LIST_FORW
, sd_it
, dep
)
3459 con
= MODEL_INSN_INFO (DEP_CON (dep
));
3460 if (con
->insn
&& insn
->alap
< con
->alap
+ 1)
3461 insn
->alap
= con
->alap
+ 1;
3464 insn
->old_queue
= QUEUE_INDEX (iter
);
3465 QUEUE_INDEX (iter
) = QUEUE_NOWHERE
;
3467 insn
->unscheduled_preds
= dep_list_size (iter
, SD_LIST_HARD_BACK
);
3468 if (insn
->unscheduled_preds
== 0)
3469 model_add_to_worklist (insn
, NULL
, model_worklist
);
3475 /* The global state describes the register pressure at the start of the
3476 model schedule. Initialize GROUP accordingly. */
3479 model_init_pressure_group (struct model_pressure_group
*group
)
3483 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
3485 cl
= ira_pressure_classes
[pci
];
3486 group
->limits
[pci
].pressure
= curr_reg_pressure
[cl
];
3487 group
->limits
[pci
].point
= 0;
3489 /* Use index model_num_insns to record the state after the last
3490 instruction in the model schedule. */
3491 group
->model
= XNEWVEC (struct model_pressure_data
,
3492 (model_num_insns
+ 1) * ira_pressure_classes_num
);
3495 /* Record that MODEL_REF_PRESSURE (GROUP, POINT, PCI) is PRESSURE.
3496 Update the maximum pressure for the whole schedule. */
3499 model_record_pressure (struct model_pressure_group
*group
,
3500 int point
, int pci
, int pressure
)
3502 MODEL_REF_PRESSURE (group
, point
, pci
) = pressure
;
3503 if (group
->limits
[pci
].pressure
< pressure
)
3505 group
->limits
[pci
].pressure
= pressure
;
3506 group
->limits
[pci
].point
= point
;
3510 /* INSN has just been added to the end of the model schedule. Record its
3511 register-pressure information. */
3514 model_record_pressures (struct model_insn_info
*insn
)
3516 struct reg_pressure_data
*reg_pressure
;
3517 int point
, pci
, cl
, delta
;
3518 int death
[N_REG_CLASSES
];
3520 point
= model_index (insn
->insn
);
3521 if (sched_verbose
>= 2)
3525 fprintf (sched_dump
, "\n;;\tModel schedule:\n;;\n");
3526 fprintf (sched_dump
, ";;\t| idx insn | mpri hght dpth prio |\n");
3528 fprintf (sched_dump
, ";;\t| %3d %4d | %4d %4d %4d %4d | %-30s ",
3529 point
, INSN_UID (insn
->insn
), insn
->model_priority
,
3530 insn
->depth
+ insn
->alap
, insn
->depth
,
3531 INSN_PRIORITY (insn
->insn
),
3532 str_pattern_slim (PATTERN (insn
->insn
)));
3534 calculate_reg_deaths (insn
->insn
, death
);
3535 reg_pressure
= INSN_REG_PRESSURE (insn
->insn
);
3536 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
3538 cl
= ira_pressure_classes
[pci
];
3539 delta
= reg_pressure
[pci
].set_increase
- death
[cl
];
3540 if (sched_verbose
>= 2)
3541 fprintf (sched_dump
, " %s:[%d,%+d]", reg_class_names
[cl
],
3542 curr_reg_pressure
[cl
], delta
);
3543 model_record_pressure (&model_before_pressure
, point
, pci
,
3544 curr_reg_pressure
[cl
]);
3546 if (sched_verbose
>= 2)
3547 fprintf (sched_dump
, "\n");
3550 /* All instructions have been added to the model schedule. Record the
3551 final register pressure in GROUP and set up all MODEL_MAX_PRESSUREs. */
3554 model_record_final_pressures (struct model_pressure_group
*group
)
3556 int point
, pci
, max_pressure
, ref_pressure
, cl
;
3558 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
3560 /* Record the final pressure for this class. */
3561 cl
= ira_pressure_classes
[pci
];
3562 point
= model_num_insns
;
3563 ref_pressure
= curr_reg_pressure
[cl
];
3564 model_record_pressure (group
, point
, pci
, ref_pressure
);
3566 /* Record the original maximum pressure. */
3567 group
->limits
[pci
].orig_pressure
= group
->limits
[pci
].pressure
;
3569 /* Update the MODEL_MAX_PRESSURE for every point of the schedule. */
3570 max_pressure
= ref_pressure
;
3571 MODEL_MAX_PRESSURE (group
, point
, pci
) = max_pressure
;
3575 ref_pressure
= MODEL_REF_PRESSURE (group
, point
, pci
);
3576 max_pressure
= MAX (max_pressure
, ref_pressure
);
3577 MODEL_MAX_PRESSURE (group
, point
, pci
) = max_pressure
;
3582 /* Update all successors of INSN, given that INSN has just been scheduled. */
3585 model_add_successors_to_worklist (struct model_insn_info
*insn
)
3587 sd_iterator_def sd_it
;
3588 struct model_insn_info
*con
;
3591 FOR_EACH_DEP (insn
->insn
, SD_LIST_FORW
, sd_it
, dep
)
3593 con
= MODEL_INSN_INFO (DEP_CON (dep
));
3594 /* Ignore debug instructions, and instructions from other blocks. */
3597 con
->unscheduled_preds
--;
3599 /* Update the depth field of each true-dependent successor.
3600 Increasing the depth gives them a higher priority than
3602 if (DEP_TYPE (dep
) == REG_DEP_TRUE
&& con
->depth
< insn
->depth
+ 1)
3604 con
->depth
= insn
->depth
+ 1;
3605 if (QUEUE_INDEX (con
->insn
) == QUEUE_READY
)
3606 model_promote_insn (con
);
3609 /* If this is a true dependency, or if there are no remaining
3610 dependencies for CON (meaning that CON only had non-true
3611 dependencies), make sure that CON is on the worklist.
3612 We don't bother otherwise because it would tend to fill the
3613 worklist with a lot of low-priority instructions that are not
3614 yet ready to issue. */
3615 if ((con
->depth
> 0 || con
->unscheduled_preds
== 0)
3616 && QUEUE_INDEX (con
->insn
) == QUEUE_NOWHERE
)
3617 model_add_to_worklist (con
, insn
, insn
->next
);
3622 /* Give INSN a higher priority than any current instruction, then give
3623 unscheduled predecessors of INSN a higher priority still. If any of
3624 those predecessors are not on the model worklist, do the same for its
3625 predecessors, and so on. */
3628 model_promote_predecessors (struct model_insn_info
*insn
)
3630 struct model_insn_info
*pro
, *first
;
3631 sd_iterator_def sd_it
;
3634 if (sched_verbose
>= 7)
3635 fprintf (sched_dump
, ";;\t+--- priority of %d = %d, priority of",
3636 INSN_UID (insn
->insn
), model_next_priority
);
3637 insn
->model_priority
= model_next_priority
++;
3638 model_remove_from_worklist (insn
);
3639 model_add_to_worklist_at (insn
, NULL
);
3644 FOR_EACH_DEP (insn
->insn
, SD_LIST_HARD_BACK
, sd_it
, dep
)
3646 pro
= MODEL_INSN_INFO (DEP_PRO (dep
));
3647 /* The first test is to ignore debug instructions, and instructions
3648 from other blocks. */
3650 && pro
->model_priority
!= model_next_priority
3651 && QUEUE_INDEX (pro
->insn
) != QUEUE_SCHEDULED
)
3653 pro
->model_priority
= model_next_priority
;
3654 if (sched_verbose
>= 7)
3655 fprintf (sched_dump
, " %d", INSN_UID (pro
->insn
));
3656 if (QUEUE_INDEX (pro
->insn
) == QUEUE_READY
)
3658 /* PRO is already in the worklist, but it now has
3659 a higher priority than before. Move it at the
3660 appropriate place. */
3661 model_remove_from_worklist (pro
);
3662 model_add_to_worklist (pro
, NULL
, model_worklist
);
3666 /* PRO isn't in the worklist. Recursively process
3667 its predecessors until we find one that is. */
3678 if (sched_verbose
>= 7)
3679 fprintf (sched_dump
, " = %d\n", model_next_priority
);
3680 model_next_priority
++;
3683 /* Pick one instruction from model_worklist and process it. */
3686 model_choose_insn (void)
3688 struct model_insn_info
*insn
, *fallback
;
3691 if (sched_verbose
>= 7)
3693 fprintf (sched_dump
, ";;\t+--- worklist:\n");
3694 insn
= model_worklist
;
3695 count
= MAX_SCHED_READY_INSNS
;
3696 while (count
> 0 && insn
)
3698 fprintf (sched_dump
, ";;\t+--- %d [%d, %d, %d, %d]\n",
3699 INSN_UID (insn
->insn
), insn
->model_priority
,
3700 insn
->depth
+ insn
->alap
, insn
->depth
,
3701 INSN_PRIORITY (insn
->insn
));
3707 /* Look for a ready instruction whose model_classify_priority is zero
3708 or negative, picking the highest-priority one. Adding such an
3709 instruction to the schedule now should do no harm, and may actually
3712 Failing that, see whether there is an instruction with the highest
3713 extant model_priority that is not yet ready, but which would reduce
3714 pressure if it became ready. This is designed to catch cases like:
3716 (set (mem (reg R1)) (reg R2))
3718 where the instruction is the last remaining use of R1 and where the
3719 value of R2 is not yet available (or vice versa). The death of R1
3720 means that this instruction already reduces pressure. It is of
3721 course possible that the computation of R2 involves other registers
3722 that are hard to kill, but such cases are rare enough for this
3723 heuristic to be a win in general.
3725 Failing that, just pick the highest-priority instruction in the
3727 count
= MAX_SCHED_READY_INSNS
;
3728 insn
= model_worklist
;
3732 if (count
== 0 || !insn
)
3734 insn
= fallback
? fallback
: model_worklist
;
3737 if (insn
->unscheduled_preds
)
3739 if (model_worklist
->model_priority
== insn
->model_priority
3741 && model_classify_pressure (insn
) < 0)
3746 if (model_classify_pressure (insn
) <= 0)
3753 if (sched_verbose
>= 7 && insn
!= model_worklist
)
3755 if (insn
->unscheduled_preds
)
3756 fprintf (sched_dump
, ";;\t+--- promoting insn %d, with dependencies\n",
3757 INSN_UID (insn
->insn
));
3759 fprintf (sched_dump
, ";;\t+--- promoting insn %d, which is ready\n",
3760 INSN_UID (insn
->insn
));
3762 if (insn
->unscheduled_preds
)
3763 /* INSN isn't yet ready to issue. Give all its predecessors the
3764 highest priority. */
3765 model_promote_predecessors (insn
);
3768 /* INSN is ready. Add it to the end of model_schedule and
3769 process its successors. */
3770 model_add_successors_to_worklist (insn
);
3771 model_remove_from_worklist (insn
);
3772 model_add_to_schedule (insn
->insn
);
3773 model_record_pressures (insn
);
3774 update_register_pressure (insn
->insn
);
3778 /* Restore all QUEUE_INDEXs to the values that they had before
3779 model_start_schedule was called. */
3782 model_reset_queue_indices (void)
3787 FOR_EACH_VEC_ELT (model_schedule
, i
, insn
)
3788 QUEUE_INDEX (insn
) = MODEL_INSN_INFO (insn
)->old_queue
;
3791 /* We have calculated the model schedule and spill costs. Print a summary
3795 model_dump_pressure_summary (void)
3799 fprintf (sched_dump
, ";; Pressure summary:");
3800 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
3802 cl
= ira_pressure_classes
[pci
];
3803 fprintf (sched_dump
, " %s:%d", reg_class_names
[cl
],
3804 model_before_pressure
.limits
[pci
].pressure
);
3806 fprintf (sched_dump
, "\n\n");
3809 /* Initialize the SCHED_PRESSURE_MODEL information for the current
3810 scheduling region. */
3813 model_start_schedule (basic_block bb
)
3815 model_next_priority
= 1;
3816 model_schedule
.create (sched_max_luid
);
3817 model_insns
= XCNEWVEC (struct model_insn_info
, sched_max_luid
);
3819 gcc_assert (bb
== BLOCK_FOR_INSN (NEXT_INSN (current_sched_info
->prev_head
)));
3820 initiate_reg_pressure_info (df_get_live_in (bb
));
3822 model_analyze_insns ();
3823 model_init_pressure_group (&model_before_pressure
);
3824 while (model_worklist
)
3825 model_choose_insn ();
3826 gcc_assert (model_num_insns
== (int) model_schedule
.length ());
3827 if (sched_verbose
>= 2)
3828 fprintf (sched_dump
, "\n");
3830 model_record_final_pressures (&model_before_pressure
);
3831 model_reset_queue_indices ();
3833 XDELETEVEC (model_insns
);
3835 model_curr_point
= 0;
3836 initiate_reg_pressure_info (df_get_live_in (bb
));
3837 if (sched_verbose
>= 1)
3838 model_dump_pressure_summary ();
3841 /* Free the information associated with GROUP. */
3844 model_finalize_pressure_group (struct model_pressure_group
*group
)
3846 XDELETEVEC (group
->model
);
3849 /* Free the information created by model_start_schedule. */
3852 model_end_schedule (void)
3854 model_finalize_pressure_group (&model_before_pressure
);
3855 model_schedule
.release ();
3858 /* Prepare reg pressure scheduling for basic block BB. */
3860 sched_pressure_start_bb (basic_block bb
)
3862 /* Set the number of available registers for each class taking into account
3863 relative probability of current basic block versus function prologue and
3865 * If the basic block executes much more often than the prologue/epilogue
3866 (e.g., inside a hot loop), then cost of spill in the prologue is close to
3867 nil, so the effective number of available registers is
3868 (ira_class_hard_regs_num[cl] - 0).
3869 * If the basic block executes as often as the prologue/epilogue,
3870 then spill in the block is as costly as in the prologue, so the effective
3871 number of available registers is
3872 (ira_class_hard_regs_num[cl] - call_used_regs_num[cl]).
3873 Note that all-else-equal, we prefer to spill in the prologue, since that
3874 allows "extra" registers for other basic blocks of the function.
3875 * If the basic block is on the cold path of the function and executes
3876 rarely, then we should always prefer to spill in the block, rather than
3877 in the prologue/epilogue. The effective number of available register is
3878 (ira_class_hard_regs_num[cl] - call_used_regs_num[cl]). */
3881 int entry_freq
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
;
3882 int bb_freq
= bb
->frequency
;
3886 if (entry_freq
== 0)
3887 entry_freq
= bb_freq
= 1;
3889 if (bb_freq
< entry_freq
)
3890 bb_freq
= entry_freq
;
3892 for (i
= 0; i
< ira_pressure_classes_num
; ++i
)
3894 enum reg_class cl
= ira_pressure_classes
[i
];
3895 sched_class_regs_num
[cl
] = ira_class_hard_regs_num
[cl
];
3896 sched_class_regs_num
[cl
]
3897 -= (call_used_regs_num
[cl
] * entry_freq
) / bb_freq
;
3901 if (sched_pressure
== SCHED_PRESSURE_MODEL
)
3902 model_start_schedule (bb
);
3905 /* A structure that holds local state for the loop in schedule_block. */
3906 struct sched_block_state
3908 /* True if no real insns have been scheduled in the current cycle. */
3909 bool first_cycle_insn_p
;
3910 /* True if a shadow insn has been scheduled in the current cycle, which
3911 means that no more normal insns can be issued. */
3912 bool shadows_only_p
;
3913 /* True if we're winding down a modulo schedule, which means that we only
3914 issue insns with INSN_EXACT_TICK set. */
3915 bool modulo_epilogue
;
3916 /* Initialized with the machine's issue rate every cycle, and updated
3917 by calls to the variable_issue hook. */
3921 /* INSN is the "currently executing insn". Launch each insn which was
3922 waiting on INSN. READY is the ready list which contains the insns
3923 that are ready to fire. CLOCK is the current cycle. The function
3924 returns necessary cycle advance after issuing the insn (it is not
3925 zero for insns in a schedule group). */
3928 schedule_insn (rtx insn
)
3930 sd_iterator_def sd_it
;
3935 if (sched_verbose
>= 1)
3937 struct reg_pressure_data
*pressure_info
;
3938 fprintf (sched_dump
, ";;\t%3i--> %s %-40s:",
3939 clock_var
, (*current_sched_info
->print_insn
) (insn
, 1),
3940 str_pattern_slim (PATTERN (insn
)));
3942 if (recog_memoized (insn
) < 0)
3943 fprintf (sched_dump
, "nothing");
3945 print_reservation (sched_dump
, insn
);
3946 pressure_info
= INSN_REG_PRESSURE (insn
);
3947 if (pressure_info
!= NULL
)
3949 fputc (':', sched_dump
);
3950 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
3951 fprintf (sched_dump
, "%s%s%+d(%d)",
3952 scheduled_insns
.length () > 1
3954 < INSN_LUID (scheduled_insns
[scheduled_insns
.length () - 2]) ? "@" : "",
3955 reg_class_names
[ira_pressure_classes
[i
]],
3956 pressure_info
[i
].set_increase
, pressure_info
[i
].change
);
3958 if (sched_pressure
== SCHED_PRESSURE_MODEL
3959 && model_curr_point
< model_num_insns
3960 && model_index (insn
) == model_curr_point
)
3961 fprintf (sched_dump
, ":model %d", model_curr_point
);
3962 fputc ('\n', sched_dump
);
3965 if (sched_pressure
== SCHED_PRESSURE_WEIGHTED
&& !DEBUG_INSN_P (insn
))
3966 update_reg_and_insn_max_reg_pressure (insn
);
3968 /* Scheduling instruction should have all its dependencies resolved and
3969 should have been removed from the ready list. */
3970 gcc_assert (sd_lists_empty_p (insn
, SD_LIST_HARD_BACK
));
3972 /* Reset debug insns invalidated by moving this insn. */
3973 if (MAY_HAVE_DEBUG_INSNS
&& !DEBUG_INSN_P (insn
))
3974 for (sd_it
= sd_iterator_start (insn
, SD_LIST_BACK
);
3975 sd_iterator_cond (&sd_it
, &dep
);)
3977 rtx dbg
= DEP_PRO (dep
);
3978 struct reg_use_data
*use
, *next
;
3980 if (DEP_STATUS (dep
) & DEP_CANCELLED
)
3982 sd_iterator_next (&sd_it
);
3986 gcc_assert (DEBUG_INSN_P (dbg
));
3988 if (sched_verbose
>= 6)
3989 fprintf (sched_dump
, ";;\t\tresetting: debug insn %d\n",
3992 /* ??? Rather than resetting the debug insn, we might be able
3993 to emit a debug temp before the just-scheduled insn, but
3994 this would involve checking that the expression at the
3995 point of the debug insn is equivalent to the expression
3996 before the just-scheduled insn. They might not be: the
3997 expression in the debug insn may depend on other insns not
3998 yet scheduled that set MEMs, REGs or even other debug
3999 insns. It's not clear that attempting to preserve debug
4000 information in these cases is worth the effort, given how
4001 uncommon these resets are and the likelihood that the debug
4002 temps introduced won't survive the schedule change. */
4003 INSN_VAR_LOCATION_LOC (dbg
) = gen_rtx_UNKNOWN_VAR_LOC ();
4004 df_insn_rescan (dbg
);
4006 /* Unknown location doesn't use any registers. */
4007 for (use
= INSN_REG_USE_LIST (dbg
); use
!= NULL
; use
= next
)
4009 struct reg_use_data
*prev
= use
;
4011 /* Remove use from the cyclic next_regno_use chain first. */
4012 while (prev
->next_regno_use
!= use
)
4013 prev
= prev
->next_regno_use
;
4014 prev
->next_regno_use
= use
->next_regno_use
;
4015 next
= use
->next_insn_use
;
4018 INSN_REG_USE_LIST (dbg
) = NULL
;
4020 /* We delete rather than resolve these deps, otherwise we
4021 crash in sched_free_deps(), because forward deps are
4022 expected to be released before backward deps. */
4023 sd_delete_dep (sd_it
);
4026 gcc_assert (QUEUE_INDEX (insn
) == QUEUE_NOWHERE
);
4027 QUEUE_INDEX (insn
) = QUEUE_SCHEDULED
;
4029 if (sched_pressure
== SCHED_PRESSURE_MODEL
4030 && model_curr_point
< model_num_insns
4031 && NONDEBUG_INSN_P (insn
))
4033 if (model_index (insn
) == model_curr_point
)
4036 while (model_curr_point
< model_num_insns
4037 && (QUEUE_INDEX (MODEL_INSN (model_curr_point
))
4038 == QUEUE_SCHEDULED
));
4040 model_recompute (insn
);
4041 model_update_limit_points ();
4042 update_register_pressure (insn
);
4043 if (sched_verbose
>= 2)
4044 print_curr_reg_pressure ();
4047 gcc_assert (INSN_TICK (insn
) >= MIN_TICK
);
4048 if (INSN_TICK (insn
) > clock_var
)
4049 /* INSN has been prematurely moved from the queue to the ready list.
4050 This is possible only if following flag is set. */
4051 gcc_assert (flag_sched_stalled_insns
);
4053 /* ??? Probably, if INSN is scheduled prematurely, we should leave
4054 INSN_TICK untouched. This is a machine-dependent issue, actually. */
4055 INSN_TICK (insn
) = clock_var
;
4057 check_clobbered_conditions (insn
);
4059 /* Update dependent instructions. First, see if by scheduling this insn
4060 now we broke a dependence in a way that requires us to change another
4062 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
4063 sd_iterator_cond (&sd_it
, &dep
); sd_iterator_next (&sd_it
))
4065 struct dep_replacement
*desc
= DEP_REPLACE (dep
);
4066 rtx pro
= DEP_PRO (dep
);
4067 if (QUEUE_INDEX (pro
) != QUEUE_SCHEDULED
4068 && desc
!= NULL
&& desc
->insn
== pro
)
4069 apply_replacement (dep
, false);
4072 /* Go through and resolve forward dependencies. */
4073 for (sd_it
= sd_iterator_start (insn
, SD_LIST_FORW
);
4074 sd_iterator_cond (&sd_it
, &dep
);)
4076 rtx next
= DEP_CON (dep
);
4077 bool cancelled
= (DEP_STATUS (dep
) & DEP_CANCELLED
) != 0;
4079 /* Resolve the dependence between INSN and NEXT.
4080 sd_resolve_dep () moves current dep to another list thus
4081 advancing the iterator. */
4082 sd_resolve_dep (sd_it
);
4086 if (must_restore_pattern_p (next
, dep
))
4087 restore_pattern (dep
, false);
4091 /* Don't bother trying to mark next as ready if insn is a debug
4092 insn. If insn is the last hard dependency, it will have
4093 already been discounted. */
4094 if (DEBUG_INSN_P (insn
) && !DEBUG_INSN_P (next
))
4097 if (!IS_SPECULATION_BRANCHY_CHECK_P (insn
))
4101 effective_cost
= try_ready (next
);
4103 if (effective_cost
>= 0
4104 && SCHED_GROUP_P (next
)
4105 && advance
< effective_cost
)
4106 advance
= effective_cost
;
4109 /* Check always has only one forward dependence (to the first insn in
4110 the recovery block), therefore, this will be executed only once. */
4112 gcc_assert (sd_lists_empty_p (insn
, SD_LIST_FORW
));
4113 fix_recovery_deps (RECOVERY_BLOCK (insn
));
4117 /* Annotate the instruction with issue information -- TImode
4118 indicates that the instruction is expected not to be able
4119 to issue on the same cycle as the previous insn. A machine
4120 may use this information to decide how the instruction should
4123 && GET_CODE (PATTERN (insn
)) != USE
4124 && GET_CODE (PATTERN (insn
)) != CLOBBER
4125 && !DEBUG_INSN_P (insn
))
4127 if (reload_completed
)
4128 PUT_MODE (insn
, clock_var
> last_clock_var
? TImode
: VOIDmode
);
4129 last_clock_var
= clock_var
;
4132 if (nonscheduled_insns_begin
!= NULL_RTX
)
4133 /* Indicate to debug counters that INSN is scheduled. */
4134 nonscheduled_insns_begin
= insn
;
4139 /* Functions for handling of notes. */
4141 /* Add note list that ends on FROM_END to the end of TO_ENDP. */
4143 concat_note_lists (rtx from_end
, rtx
*to_endp
)
4147 /* It's easy when have nothing to concat. */
4148 if (from_end
== NULL
)
4151 /* It's also easy when destination is empty. */
4152 if (*to_endp
== NULL
)
4154 *to_endp
= from_end
;
4158 from_start
= from_end
;
4159 while (PREV_INSN (from_start
) != NULL
)
4160 from_start
= PREV_INSN (from_start
);
4162 PREV_INSN (from_start
) = *to_endp
;
4163 NEXT_INSN (*to_endp
) = from_start
;
4164 *to_endp
= from_end
;
4167 /* Delete notes between HEAD and TAIL and put them in the chain
4168 of notes ended by NOTE_LIST. */
4170 remove_notes (rtx head
, rtx tail
)
4172 rtx next_tail
, insn
, next
;
4175 if (head
== tail
&& !INSN_P (head
))
4178 next_tail
= NEXT_INSN (tail
);
4179 for (insn
= head
; insn
!= next_tail
; insn
= next
)
4181 next
= NEXT_INSN (insn
);
4185 switch (NOTE_KIND (insn
))
4187 case NOTE_INSN_BASIC_BLOCK
:
4190 case NOTE_INSN_EPILOGUE_BEG
:
4194 add_reg_note (next
, REG_SAVE_NOTE
,
4195 GEN_INT (NOTE_INSN_EPILOGUE_BEG
));
4203 /* Add the note to list that ends at NOTE_LIST. */
4204 PREV_INSN (insn
) = note_list
;
4205 NEXT_INSN (insn
) = NULL_RTX
;
4207 NEXT_INSN (note_list
) = insn
;
4212 gcc_assert ((sel_sched_p () || insn
!= tail
) && insn
!= head
);
4216 /* A structure to record enough data to allow us to backtrack the scheduler to
4217 a previous state. */
4218 struct haifa_saved_data
4220 /* Next entry on the list. */
4221 struct haifa_saved_data
*next
;
4223 /* Backtracking is associated with scheduling insns that have delay slots.
4224 DELAY_PAIR points to the structure that contains the insns involved, and
4225 the number of cycles between them. */
4226 struct delay_pair
*delay_pair
;
4228 /* Data used by the frontend (e.g. sched-ebb or sched-rgn). */
4229 void *fe_saved_data
;
4230 /* Data used by the backend. */
4231 void *be_saved_data
;
4233 /* Copies of global state. */
4234 int clock_var
, last_clock_var
;
4235 struct ready_list ready
;
4238 rtx last_scheduled_insn
;
4239 rtx last_nondebug_scheduled_insn
;
4240 rtx nonscheduled_insns_begin
;
4241 int cycle_issued_insns
;
4243 /* Copies of state used in the inner loop of schedule_block. */
4244 struct sched_block_state sched_block
;
4246 /* We don't need to save q_ptr, as its value is arbitrary and we can set it
4247 to 0 when restoring. */
4251 /* Describe pattern replacements that occurred since this backtrack point
4253 vec
<dep_t
> replacement_deps
;
4254 vec
<int> replace_apply
;
4256 /* A copy of the next-cycle replacement vectors at the time of the backtrack
4258 vec
<dep_t
> next_cycle_deps
;
4259 vec
<int> next_cycle_apply
;
4262 /* A record, in reverse order, of all scheduled insns which have delay slots
4263 and may require backtracking. */
4264 static struct haifa_saved_data
*backtrack_queue
;
4266 /* For every dependency of INSN, set the FEEDS_BACKTRACK_INSN bit according
4269 mark_backtrack_feeds (rtx insn
, int set_p
)
4271 sd_iterator_def sd_it
;
4273 FOR_EACH_DEP (insn
, SD_LIST_HARD_BACK
, sd_it
, dep
)
4275 FEEDS_BACKTRACK_INSN (DEP_PRO (dep
)) = set_p
;
4279 /* Save the current scheduler state so that we can backtrack to it
4280 later if necessary. PAIR gives the insns that make it necessary to
4281 save this point. SCHED_BLOCK is the local state of schedule_block
4282 that need to be saved. */
4284 save_backtrack_point (struct delay_pair
*pair
,
4285 struct sched_block_state sched_block
)
4288 struct haifa_saved_data
*save
= XNEW (struct haifa_saved_data
);
4290 save
->curr_state
= xmalloc (dfa_state_size
);
4291 memcpy (save
->curr_state
, curr_state
, dfa_state_size
);
4293 save
->ready
.first
= ready
.first
;
4294 save
->ready
.n_ready
= ready
.n_ready
;
4295 save
->ready
.n_debug
= ready
.n_debug
;
4296 save
->ready
.veclen
= ready
.veclen
;
4297 save
->ready
.vec
= XNEWVEC (rtx
, ready
.veclen
);
4298 memcpy (save
->ready
.vec
, ready
.vec
, ready
.veclen
* sizeof (rtx
));
4300 save
->insn_queue
= XNEWVEC (rtx
, max_insn_queue_index
+ 1);
4301 save
->q_size
= q_size
;
4302 for (i
= 0; i
<= max_insn_queue_index
; i
++)
4304 int q
= NEXT_Q_AFTER (q_ptr
, i
);
4305 save
->insn_queue
[i
] = copy_INSN_LIST (insn_queue
[q
]);
4308 save
->clock_var
= clock_var
;
4309 save
->last_clock_var
= last_clock_var
;
4310 save
->cycle_issued_insns
= cycle_issued_insns
;
4311 save
->last_scheduled_insn
= last_scheduled_insn
;
4312 save
->last_nondebug_scheduled_insn
= last_nondebug_scheduled_insn
;
4313 save
->nonscheduled_insns_begin
= nonscheduled_insns_begin
;
4315 save
->sched_block
= sched_block
;
4317 save
->replacement_deps
.create (0);
4318 save
->replace_apply
.create (0);
4319 save
->next_cycle_deps
= next_cycle_replace_deps
.copy ();
4320 save
->next_cycle_apply
= next_cycle_apply
.copy ();
4322 if (current_sched_info
->save_state
)
4323 save
->fe_saved_data
= (*current_sched_info
->save_state
) ();
4325 if (targetm
.sched
.alloc_sched_context
)
4327 save
->be_saved_data
= targetm
.sched
.alloc_sched_context ();
4328 targetm
.sched
.init_sched_context (save
->be_saved_data
, false);
4331 save
->be_saved_data
= NULL
;
4333 save
->delay_pair
= pair
;
4335 save
->next
= backtrack_queue
;
4336 backtrack_queue
= save
;
4340 mark_backtrack_feeds (pair
->i2
, 1);
4341 INSN_TICK (pair
->i2
) = INVALID_TICK
;
4342 INSN_EXACT_TICK (pair
->i2
) = clock_var
+ pair_delay (pair
);
4343 SHADOW_P (pair
->i2
) = pair
->stages
== 0;
4344 pair
= pair
->next_same_i1
;
4348 /* Walk the ready list and all queues. If any insns have unresolved backwards
4349 dependencies, these must be cancelled deps, broken by predication. Set or
4350 clear (depending on SET) the DEP_CANCELLED bit in DEP_STATUS. */
4353 toggle_cancelled_flags (bool set
)
4356 sd_iterator_def sd_it
;
4359 if (ready
.n_ready
> 0)
4361 rtx
*first
= ready_lastpos (&ready
);
4362 for (i
= 0; i
< ready
.n_ready
; i
++)
4363 FOR_EACH_DEP (first
[i
], SD_LIST_BACK
, sd_it
, dep
)
4364 if (!DEBUG_INSN_P (DEP_PRO (dep
)))
4367 DEP_STATUS (dep
) |= DEP_CANCELLED
;
4369 DEP_STATUS (dep
) &= ~DEP_CANCELLED
;
4372 for (i
= 0; i
<= max_insn_queue_index
; i
++)
4374 int q
= NEXT_Q_AFTER (q_ptr
, i
);
4376 for (link
= insn_queue
[q
]; link
; link
= XEXP (link
, 1))
4378 rtx insn
= XEXP (link
, 0);
4379 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
4380 if (!DEBUG_INSN_P (DEP_PRO (dep
)))
4383 DEP_STATUS (dep
) |= DEP_CANCELLED
;
4385 DEP_STATUS (dep
) &= ~DEP_CANCELLED
;
4391 /* Undo the replacements that have occurred after backtrack point SAVE
4394 undo_replacements_for_backtrack (struct haifa_saved_data
*save
)
4396 while (!save
->replacement_deps
.is_empty ())
4398 dep_t dep
= save
->replacement_deps
.pop ();
4399 int apply_p
= save
->replace_apply
.pop ();
4402 restore_pattern (dep
, true);
4404 apply_replacement (dep
, true);
4406 save
->replacement_deps
.release ();
4407 save
->replace_apply
.release ();
4410 /* Pop entries from the SCHEDULED_INSNS vector up to and including INSN.
4411 Restore their dependencies to an unresolved state, and mark them as
4415 unschedule_insns_until (rtx insn
)
4417 auto_vec
<rtx
> recompute_vec
;
4419 /* Make two passes over the insns to be unscheduled. First, we clear out
4420 dependencies and other trivial bookkeeping. */
4424 sd_iterator_def sd_it
;
4427 last
= scheduled_insns
.pop ();
4429 /* This will be changed by restore_backtrack_point if the insn is in
4431 QUEUE_INDEX (last
) = QUEUE_NOWHERE
;
4433 INSN_TICK (last
) = INVALID_TICK
;
4435 if (modulo_ii
> 0 && INSN_UID (last
) < modulo_iter0_max_uid
)
4436 modulo_insns_scheduled
--;
4438 for (sd_it
= sd_iterator_start (last
, SD_LIST_RES_FORW
);
4439 sd_iterator_cond (&sd_it
, &dep
);)
4441 rtx con
= DEP_CON (dep
);
4442 sd_unresolve_dep (sd_it
);
4443 if (!MUST_RECOMPUTE_SPEC_P (con
))
4445 MUST_RECOMPUTE_SPEC_P (con
) = 1;
4446 recompute_vec
.safe_push (con
);
4454 /* A second pass, to update ready and speculation status for insns
4455 depending on the unscheduled ones. The first pass must have
4456 popped the scheduled_insns vector up to the point where we
4457 restart scheduling, as recompute_todo_spec requires it to be
4459 while (!recompute_vec
.is_empty ())
4463 con
= recompute_vec
.pop ();
4464 MUST_RECOMPUTE_SPEC_P (con
) = 0;
4465 if (!sd_lists_empty_p (con
, SD_LIST_HARD_BACK
))
4467 TODO_SPEC (con
) = HARD_DEP
;
4468 INSN_TICK (con
) = INVALID_TICK
;
4469 if (PREDICATED_PAT (con
) != NULL_RTX
)
4470 haifa_change_pattern (con
, ORIG_PAT (con
));
4472 else if (QUEUE_INDEX (con
) != QUEUE_SCHEDULED
)
4473 TODO_SPEC (con
) = recompute_todo_spec (con
, true);
4477 /* Restore scheduler state from the topmost entry on the backtracking queue.
4478 PSCHED_BLOCK_P points to the local data of schedule_block that we must
4479 overwrite with the saved data.
4480 The caller must already have called unschedule_insns_until. */
4483 restore_last_backtrack_point (struct sched_block_state
*psched_block
)
4487 struct haifa_saved_data
*save
= backtrack_queue
;
4489 backtrack_queue
= save
->next
;
4491 if (current_sched_info
->restore_state
)
4492 (*current_sched_info
->restore_state
) (save
->fe_saved_data
);
4494 if (targetm
.sched
.alloc_sched_context
)
4496 targetm
.sched
.set_sched_context (save
->be_saved_data
);
4497 targetm
.sched
.free_sched_context (save
->be_saved_data
);
4500 /* Do this first since it clobbers INSN_TICK of the involved
4502 undo_replacements_for_backtrack (save
);
4504 /* Clear the QUEUE_INDEX of everything in the ready list or one
4506 if (ready
.n_ready
> 0)
4508 rtx
*first
= ready_lastpos (&ready
);
4509 for (i
= 0; i
< ready
.n_ready
; i
++)
4511 rtx insn
= first
[i
];
4512 QUEUE_INDEX (insn
) = QUEUE_NOWHERE
;
4513 INSN_TICK (insn
) = INVALID_TICK
;
4516 for (i
= 0; i
<= max_insn_queue_index
; i
++)
4518 int q
= NEXT_Q_AFTER (q_ptr
, i
);
4520 for (link
= insn_queue
[q
]; link
; link
= XEXP (link
, 1))
4522 rtx x
= XEXP (link
, 0);
4523 QUEUE_INDEX (x
) = QUEUE_NOWHERE
;
4524 INSN_TICK (x
) = INVALID_TICK
;
4526 free_INSN_LIST_list (&insn_queue
[q
]);
4530 ready
= save
->ready
;
4532 if (ready
.n_ready
> 0)
4534 rtx
*first
= ready_lastpos (&ready
);
4535 for (i
= 0; i
< ready
.n_ready
; i
++)
4537 rtx insn
= first
[i
];
4538 QUEUE_INDEX (insn
) = QUEUE_READY
;
4539 TODO_SPEC (insn
) = recompute_todo_spec (insn
, true);
4540 INSN_TICK (insn
) = save
->clock_var
;
4545 q_size
= save
->q_size
;
4546 for (i
= 0; i
<= max_insn_queue_index
; i
++)
4548 int q
= NEXT_Q_AFTER (q_ptr
, i
);
4550 insn_queue
[q
] = save
->insn_queue
[q
];
4552 for (link
= insn_queue
[q
]; link
; link
= XEXP (link
, 1))
4554 rtx x
= XEXP (link
, 0);
4555 QUEUE_INDEX (x
) = i
;
4556 TODO_SPEC (x
) = recompute_todo_spec (x
, true);
4557 INSN_TICK (x
) = save
->clock_var
+ i
;
4560 free (save
->insn_queue
);
4562 toggle_cancelled_flags (true);
4564 clock_var
= save
->clock_var
;
4565 last_clock_var
= save
->last_clock_var
;
4566 cycle_issued_insns
= save
->cycle_issued_insns
;
4567 last_scheduled_insn
= save
->last_scheduled_insn
;
4568 last_nondebug_scheduled_insn
= save
->last_nondebug_scheduled_insn
;
4569 nonscheduled_insns_begin
= save
->nonscheduled_insns_begin
;
4571 *psched_block
= save
->sched_block
;
4573 memcpy (curr_state
, save
->curr_state
, dfa_state_size
);
4574 free (save
->curr_state
);
4576 mark_backtrack_feeds (save
->delay_pair
->i2
, 0);
4578 gcc_assert (next_cycle_replace_deps
.is_empty ());
4579 next_cycle_replace_deps
= save
->next_cycle_deps
.copy ();
4580 next_cycle_apply
= save
->next_cycle_apply
.copy ();
4584 for (save
= backtrack_queue
; save
; save
= save
->next
)
4586 mark_backtrack_feeds (save
->delay_pair
->i2
, 1);
4590 /* Discard all data associated with the topmost entry in the backtrack
4591 queue. If RESET_TICK is false, we just want to free the data. If true,
4592 we are doing this because we discovered a reason to backtrack. In the
4593 latter case, also reset the INSN_TICK for the shadow insn. */
4595 free_topmost_backtrack_point (bool reset_tick
)
4597 struct haifa_saved_data
*save
= backtrack_queue
;
4600 backtrack_queue
= save
->next
;
4604 struct delay_pair
*pair
= save
->delay_pair
;
4607 INSN_TICK (pair
->i2
) = INVALID_TICK
;
4608 INSN_EXACT_TICK (pair
->i2
) = INVALID_TICK
;
4609 pair
= pair
->next_same_i1
;
4611 undo_replacements_for_backtrack (save
);
4615 save
->replacement_deps
.release ();
4616 save
->replace_apply
.release ();
4619 if (targetm
.sched
.free_sched_context
)
4620 targetm
.sched
.free_sched_context (save
->be_saved_data
);
4621 if (current_sched_info
->restore_state
)
4622 free (save
->fe_saved_data
);
4623 for (i
= 0; i
<= max_insn_queue_index
; i
++)
4624 free_INSN_LIST_list (&save
->insn_queue
[i
]);
4625 free (save
->insn_queue
);
4626 free (save
->curr_state
);
4627 free (save
->ready
.vec
);
4631 /* Free the entire backtrack queue. */
4633 free_backtrack_queue (void)
4635 while (backtrack_queue
)
4636 free_topmost_backtrack_point (false);
4639 /* Apply a replacement described by DESC. If IMMEDIATELY is false, we
4640 may have to postpone the replacement until the start of the next cycle,
4641 at which point we will be called again with IMMEDIATELY true. This is
4642 only done for machines which have instruction packets with explicit
4643 parallelism however. */
4645 apply_replacement (dep_t dep
, bool immediately
)
4647 struct dep_replacement
*desc
= DEP_REPLACE (dep
);
4648 if (!immediately
&& targetm
.sched
.exposed_pipeline
&& reload_completed
)
4650 next_cycle_replace_deps
.safe_push (dep
);
4651 next_cycle_apply
.safe_push (1);
4657 if (QUEUE_INDEX (desc
->insn
) == QUEUE_SCHEDULED
)
4660 if (sched_verbose
>= 5)
4661 fprintf (sched_dump
, "applying replacement for insn %d\n",
4662 INSN_UID (desc
->insn
));
4664 success
= validate_change (desc
->insn
, desc
->loc
, desc
->newval
, 0);
4665 gcc_assert (success
);
4667 update_insn_after_change (desc
->insn
);
4668 if ((TODO_SPEC (desc
->insn
) & (HARD_DEP
| DEP_POSTPONED
)) == 0)
4669 fix_tick_ready (desc
->insn
);
4671 if (backtrack_queue
!= NULL
)
4673 backtrack_queue
->replacement_deps
.safe_push (dep
);
4674 backtrack_queue
->replace_apply
.safe_push (1);
4679 /* We have determined that a pattern involved in DEP must be restored.
4680 If IMMEDIATELY is false, we may have to postpone the replacement
4681 until the start of the next cycle, at which point we will be called
4682 again with IMMEDIATELY true. */
4684 restore_pattern (dep_t dep
, bool immediately
)
4686 rtx next
= DEP_CON (dep
);
4687 int tick
= INSN_TICK (next
);
4689 /* If we already scheduled the insn, the modified version is
4691 if (QUEUE_INDEX (next
) == QUEUE_SCHEDULED
)
4694 if (!immediately
&& targetm
.sched
.exposed_pipeline
&& reload_completed
)
4696 next_cycle_replace_deps
.safe_push (dep
);
4697 next_cycle_apply
.safe_push (0);
4702 if (DEP_TYPE (dep
) == REG_DEP_CONTROL
)
4704 if (sched_verbose
>= 5)
4705 fprintf (sched_dump
, "restoring pattern for insn %d\n",
4707 haifa_change_pattern (next
, ORIG_PAT (next
));
4711 struct dep_replacement
*desc
= DEP_REPLACE (dep
);
4714 if (sched_verbose
>= 5)
4715 fprintf (sched_dump
, "restoring pattern for insn %d\n",
4716 INSN_UID (desc
->insn
));
4717 tick
= INSN_TICK (desc
->insn
);
4719 success
= validate_change (desc
->insn
, desc
->loc
, desc
->orig
, 0);
4720 gcc_assert (success
);
4721 update_insn_after_change (desc
->insn
);
4722 if (backtrack_queue
!= NULL
)
4724 backtrack_queue
->replacement_deps
.safe_push (dep
);
4725 backtrack_queue
->replace_apply
.safe_push (0);
4728 INSN_TICK (next
) = tick
;
4729 if (TODO_SPEC (next
) == DEP_POSTPONED
)
4732 if (sd_lists_empty_p (next
, SD_LIST_BACK
))
4733 TODO_SPEC (next
) = 0;
4734 else if (!sd_lists_empty_p (next
, SD_LIST_HARD_BACK
))
4735 TODO_SPEC (next
) = HARD_DEP
;
4738 /* Perform pattern replacements that were queued up until the next
4741 perform_replacements_new_cycle (void)
4745 FOR_EACH_VEC_ELT (next_cycle_replace_deps
, i
, dep
)
4747 int apply_p
= next_cycle_apply
[i
];
4749 apply_replacement (dep
, true);
4751 restore_pattern (dep
, true);
4753 next_cycle_replace_deps
.truncate (0);
4754 next_cycle_apply
.truncate (0);
4757 /* Compute INSN_TICK_ESTIMATE for INSN. PROCESSED is a bitmap of
4758 instructions we've previously encountered, a set bit prevents
4759 recursion. BUDGET is a limit on how far ahead we look, it is
4760 reduced on recursive calls. Return true if we produced a good
4761 estimate, or false if we exceeded the budget. */
4763 estimate_insn_tick (bitmap processed
, rtx insn
, int budget
)
4765 sd_iterator_def sd_it
;
4767 int earliest
= INSN_TICK (insn
);
4769 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
4771 rtx pro
= DEP_PRO (dep
);
4774 if (DEP_STATUS (dep
) & DEP_CANCELLED
)
4777 if (QUEUE_INDEX (pro
) == QUEUE_SCHEDULED
)
4778 gcc_assert (INSN_TICK (pro
) + dep_cost (dep
) <= INSN_TICK (insn
));
4781 int cost
= dep_cost (dep
);
4784 if (!bitmap_bit_p (processed
, INSN_LUID (pro
)))
4786 if (!estimate_insn_tick (processed
, pro
, budget
- cost
))
4789 gcc_assert (INSN_TICK_ESTIMATE (pro
) != INVALID_TICK
);
4790 t
= INSN_TICK_ESTIMATE (pro
) + cost
;
4791 if (earliest
== INVALID_TICK
|| t
> earliest
)
4795 bitmap_set_bit (processed
, INSN_LUID (insn
));
4796 INSN_TICK_ESTIMATE (insn
) = earliest
;
4800 /* Examine the pair of insns in P, and estimate (optimistically, assuming
4801 infinite resources) the cycle in which the delayed shadow can be issued.
4802 Return the number of cycles that must pass before the real insn can be
4803 issued in order to meet this constraint. */
4805 estimate_shadow_tick (struct delay_pair
*p
)
4807 bitmap_head processed
;
4810 bitmap_initialize (&processed
, 0);
4812 cutoff
= !estimate_insn_tick (&processed
, p
->i2
,
4813 max_insn_queue_index
+ pair_delay (p
));
4814 bitmap_clear (&processed
);
4816 return max_insn_queue_index
;
4817 t
= INSN_TICK_ESTIMATE (p
->i2
) - (clock_var
+ pair_delay (p
) + 1);
4823 /* If INSN has no unresolved backwards dependencies, add it to the schedule and
4824 recursively resolve all its forward dependencies. */
4826 resolve_dependencies (rtx insn
)
4828 sd_iterator_def sd_it
;
4831 /* Don't use sd_lists_empty_p; it ignores debug insns. */
4832 if (DEPS_LIST_FIRST (INSN_HARD_BACK_DEPS (insn
)) != NULL
4833 || DEPS_LIST_FIRST (INSN_SPEC_BACK_DEPS (insn
)) != NULL
)
4836 if (sched_verbose
>= 4)
4837 fprintf (sched_dump
, ";;\tquickly resolving %d\n", INSN_UID (insn
));
4839 if (QUEUE_INDEX (insn
) >= 0)
4840 queue_remove (insn
);
4842 scheduled_insns
.safe_push (insn
);
4844 /* Update dependent instructions. */
4845 for (sd_it
= sd_iterator_start (insn
, SD_LIST_FORW
);
4846 sd_iterator_cond (&sd_it
, &dep
);)
4848 rtx next
= DEP_CON (dep
);
4850 if (sched_verbose
>= 4)
4851 fprintf (sched_dump
, ";;\t\tdep %d against %d\n", INSN_UID (insn
),
4854 /* Resolve the dependence between INSN and NEXT.
4855 sd_resolve_dep () moves current dep to another list thus
4856 advancing the iterator. */
4857 sd_resolve_dep (sd_it
);
4859 if (!IS_SPECULATION_BRANCHY_CHECK_P (insn
))
4861 resolve_dependencies (next
);
4864 /* Check always has only one forward dependence (to the first insn in
4865 the recovery block), therefore, this will be executed only once. */
4867 gcc_assert (sd_lists_empty_p (insn
, SD_LIST_FORW
));
4873 /* Return the head and tail pointers of ebb starting at BEG and ending
4876 get_ebb_head_tail (basic_block beg
, basic_block end
, rtx
*headp
, rtx
*tailp
)
4878 rtx beg_head
= BB_HEAD (beg
);
4879 rtx beg_tail
= BB_END (beg
);
4880 rtx end_head
= BB_HEAD (end
);
4881 rtx end_tail
= BB_END (end
);
4883 /* Don't include any notes or labels at the beginning of the BEG
4884 basic block, or notes at the end of the END basic blocks. */
4886 if (LABEL_P (beg_head
))
4887 beg_head
= NEXT_INSN (beg_head
);
4889 while (beg_head
!= beg_tail
)
4890 if (NOTE_P (beg_head
))
4891 beg_head
= NEXT_INSN (beg_head
);
4892 else if (DEBUG_INSN_P (beg_head
))
4896 for (note
= NEXT_INSN (beg_head
);
4900 next
= NEXT_INSN (note
);
4903 if (sched_verbose
>= 9)
4904 fprintf (sched_dump
, "reorder %i\n", INSN_UID (note
));
4906 reorder_insns_nobb (note
, note
, PREV_INSN (beg_head
));
4908 if (BLOCK_FOR_INSN (note
) != beg
)
4909 df_insn_change_bb (note
, beg
);
4911 else if (!DEBUG_INSN_P (note
))
4923 end_head
= beg_head
;
4924 else if (LABEL_P (end_head
))
4925 end_head
= NEXT_INSN (end_head
);
4927 while (end_head
!= end_tail
)
4928 if (NOTE_P (end_tail
))
4929 end_tail
= PREV_INSN (end_tail
);
4930 else if (DEBUG_INSN_P (end_tail
))
4934 for (note
= PREV_INSN (end_tail
);
4938 prev
= PREV_INSN (note
);
4941 if (sched_verbose
>= 9)
4942 fprintf (sched_dump
, "reorder %i\n", INSN_UID (note
));
4944 reorder_insns_nobb (note
, note
, end_tail
);
4946 if (end_tail
== BB_END (end
))
4947 BB_END (end
) = note
;
4949 if (BLOCK_FOR_INSN (note
) != end
)
4950 df_insn_change_bb (note
, end
);
4952 else if (!DEBUG_INSN_P (note
))
4964 /* Return nonzero if there are no real insns in the range [ HEAD, TAIL ]. */
4967 no_real_insns_p (const_rtx head
, const_rtx tail
)
4969 while (head
!= NEXT_INSN (tail
))
4971 if (!NOTE_P (head
) && !LABEL_P (head
))
4973 head
= NEXT_INSN (head
);
4978 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
4979 previously found among the insns. Insert them just before HEAD. */
4981 restore_other_notes (rtx head
, basic_block head_bb
)
4985 rtx note_head
= note_list
;
4988 head_bb
= BLOCK_FOR_INSN (head
);
4990 head
= NEXT_INSN (bb_note (head_bb
));
4992 while (PREV_INSN (note_head
))
4994 set_block_for_insn (note_head
, head_bb
);
4995 note_head
= PREV_INSN (note_head
);
4997 /* In the above cycle we've missed this note. */
4998 set_block_for_insn (note_head
, head_bb
);
5000 PREV_INSN (note_head
) = PREV_INSN (head
);
5001 NEXT_INSN (PREV_INSN (head
)) = note_head
;
5002 PREV_INSN (head
) = note_list
;
5003 NEXT_INSN (note_list
) = head
;
5005 if (BLOCK_FOR_INSN (head
) != head_bb
)
5006 BB_END (head_bb
) = note_list
;
5014 /* When we know we are going to discard the schedule due to a failed attempt
5015 at modulo scheduling, undo all replacements. */
5017 undo_all_replacements (void)
5022 FOR_EACH_VEC_ELT (scheduled_insns
, i
, insn
)
5024 sd_iterator_def sd_it
;
5027 /* See if we must undo a replacement. */
5028 for (sd_it
= sd_iterator_start (insn
, SD_LIST_RES_FORW
);
5029 sd_iterator_cond (&sd_it
, &dep
); sd_iterator_next (&sd_it
))
5031 struct dep_replacement
*desc
= DEP_REPLACE (dep
);
5033 validate_change (desc
->insn
, desc
->loc
, desc
->orig
, 0);
5038 /* Return first non-scheduled insn in the current scheduling block.
5039 This is mostly used for debug-counter purposes. */
5041 first_nonscheduled_insn (void)
5043 rtx insn
= (nonscheduled_insns_begin
!= NULL_RTX
5044 ? nonscheduled_insns_begin
5045 : current_sched_info
->prev_head
);
5049 insn
= next_nonnote_nondebug_insn (insn
);
5051 while (QUEUE_INDEX (insn
) == QUEUE_SCHEDULED
);
5056 /* Move insns that became ready to fire from queue to ready list. */
5059 queue_to_ready (struct ready_list
*ready
)
5065 q_ptr
= NEXT_Q (q_ptr
);
5067 if (dbg_cnt (sched_insn
) == false)
5068 /* If debug counter is activated do not requeue the first
5069 nonscheduled insn. */
5070 skip_insn
= first_nonscheduled_insn ();
5072 skip_insn
= NULL_RTX
;
5074 /* Add all pending insns that can be scheduled without stalls to the
5076 for (link
= insn_queue
[q_ptr
]; link
; link
= XEXP (link
, 1))
5078 insn
= XEXP (link
, 0);
5081 if (sched_verbose
>= 2)
5082 fprintf (sched_dump
, ";;\t\tQ-->Ready: insn %s: ",
5083 (*current_sched_info
->print_insn
) (insn
, 0));
5085 /* If the ready list is full, delay the insn for 1 cycle.
5086 See the comment in schedule_block for the rationale. */
5087 if (!reload_completed
5088 && (ready
->n_ready
- ready
->n_debug
> MAX_SCHED_READY_INSNS
5089 || (sched_pressure
== SCHED_PRESSURE_MODEL
5090 /* Limit pressure recalculations to MAX_SCHED_READY_INSNS
5091 instructions too. */
5092 && model_index (insn
) > (model_curr_point
5093 + MAX_SCHED_READY_INSNS
)))
5094 && !(sched_pressure
== SCHED_PRESSURE_MODEL
5095 && model_curr_point
< model_num_insns
5096 /* Always allow the next model instruction to issue. */
5097 && model_index (insn
) == model_curr_point
)
5098 && !SCHED_GROUP_P (insn
)
5099 && insn
!= skip_insn
)
5101 if (sched_verbose
>= 2)
5102 fprintf (sched_dump
, "keeping in queue, ready full\n");
5103 queue_insn (insn
, 1, "ready full");
5107 ready_add (ready
, insn
, false);
5108 if (sched_verbose
>= 2)
5109 fprintf (sched_dump
, "moving to ready without stalls\n");
5112 free_INSN_LIST_list (&insn_queue
[q_ptr
]);
5114 /* If there are no ready insns, stall until one is ready and add all
5115 of the pending insns at that point to the ready list. */
5116 if (ready
->n_ready
== 0)
5120 for (stalls
= 1; stalls
<= max_insn_queue_index
; stalls
++)
5122 if ((link
= insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]))
5124 for (; link
; link
= XEXP (link
, 1))
5126 insn
= XEXP (link
, 0);
5129 if (sched_verbose
>= 2)
5130 fprintf (sched_dump
, ";;\t\tQ-->Ready: insn %s: ",
5131 (*current_sched_info
->print_insn
) (insn
, 0));
5133 ready_add (ready
, insn
, false);
5134 if (sched_verbose
>= 2)
5135 fprintf (sched_dump
, "moving to ready with %d stalls\n", stalls
);
5137 free_INSN_LIST_list (&insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]);
5139 advance_one_cycle ();
5144 advance_one_cycle ();
5147 q_ptr
= NEXT_Q_AFTER (q_ptr
, stalls
);
5148 clock_var
+= stalls
;
5149 if (sched_verbose
>= 2)
5150 fprintf (sched_dump
, ";;\tAdvancing clock by %d cycle[s] to %d\n",
5155 /* Used by early_queue_to_ready. Determines whether it is "ok" to
5156 prematurely move INSN from the queue to the ready list. Currently,
5157 if a target defines the hook 'is_costly_dependence', this function
5158 uses the hook to check whether there exist any dependences which are
5159 considered costly by the target, between INSN and other insns that
5160 have already been scheduled. Dependences are checked up to Y cycles
5161 back, with default Y=1; The flag -fsched-stalled-insns-dep=Y allows
5162 controlling this value.
5163 (Other considerations could be taken into account instead (or in
5164 addition) depending on user flags and target hooks. */
5167 ok_for_early_queue_removal (rtx insn
)
5169 if (targetm
.sched
.is_costly_dependence
)
5173 int i
= scheduled_insns
.length ();
5174 for (n_cycles
= flag_sched_stalled_insns_dep
; n_cycles
; n_cycles
--)
5180 prev_insn
= scheduled_insns
[i
];
5182 if (!NOTE_P (prev_insn
))
5186 dep
= sd_find_dep_between (prev_insn
, insn
, true);
5190 cost
= dep_cost (dep
);
5192 if (targetm
.sched
.is_costly_dependence (dep
, cost
,
5193 flag_sched_stalled_insns_dep
- n_cycles
))
5198 if (GET_MODE (prev_insn
) == TImode
) /* end of dispatch group */
5211 /* Remove insns from the queue, before they become "ready" with respect
5212 to FU latency considerations. */
5215 early_queue_to_ready (state_t state
, struct ready_list
*ready
)
5223 state_t temp_state
= alloca (dfa_state_size
);
5225 int insns_removed
= 0;
5228 Flag '-fsched-stalled-insns=X' determines the aggressiveness of this
5231 X == 0: There is no limit on how many queued insns can be removed
5232 prematurely. (flag_sched_stalled_insns = -1).
5234 X >= 1: Only X queued insns can be removed prematurely in each
5235 invocation. (flag_sched_stalled_insns = X).
5237 Otherwise: Early queue removal is disabled.
5238 (flag_sched_stalled_insns = 0)
5241 if (! flag_sched_stalled_insns
)
5244 for (stalls
= 0; stalls
<= max_insn_queue_index
; stalls
++)
5246 if ((link
= insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]))
5248 if (sched_verbose
> 6)
5249 fprintf (sched_dump
, ";; look at index %d + %d\n", q_ptr
, stalls
);
5254 next_link
= XEXP (link
, 1);
5255 insn
= XEXP (link
, 0);
5256 if (insn
&& sched_verbose
> 6)
5257 print_rtl_single (sched_dump
, insn
);
5259 memcpy (temp_state
, state
, dfa_state_size
);
5260 if (recog_memoized (insn
) < 0)
5261 /* non-negative to indicate that it's not ready
5262 to avoid infinite Q->R->Q->R... */
5265 cost
= state_transition (temp_state
, insn
);
5267 if (sched_verbose
>= 6)
5268 fprintf (sched_dump
, "transition cost = %d\n", cost
);
5270 move_to_ready
= false;
5273 move_to_ready
= ok_for_early_queue_removal (insn
);
5274 if (move_to_ready
== true)
5276 /* move from Q to R */
5278 ready_add (ready
, insn
, false);
5281 XEXP (prev_link
, 1) = next_link
;
5283 insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)] = next_link
;
5285 free_INSN_LIST_node (link
);
5287 if (sched_verbose
>= 2)
5288 fprintf (sched_dump
, ";;\t\tEarly Q-->Ready: insn %s\n",
5289 (*current_sched_info
->print_insn
) (insn
, 0));
5292 if (insns_removed
== flag_sched_stalled_insns
)
5293 /* Remove no more than flag_sched_stalled_insns insns
5294 from Q at a time. */
5295 return insns_removed
;
5299 if (move_to_ready
== false)
5306 } /* for stalls.. */
5308 return insns_removed
;
5312 /* Print the ready list for debugging purposes.
5313 If READY_TRY is non-zero then only print insns that max_issue
5316 debug_ready_list_1 (struct ready_list
*ready
, signed char *ready_try
)
5321 if (ready
->n_ready
== 0)
5323 fprintf (sched_dump
, "\n");
5327 p
= ready_lastpos (ready
);
5328 for (i
= 0; i
< ready
->n_ready
; i
++)
5330 if (ready_try
!= NULL
&& ready_try
[ready
->n_ready
- i
- 1])
5333 fprintf (sched_dump
, " %s:%d",
5334 (*current_sched_info
->print_insn
) (p
[i
], 0),
5336 if (sched_pressure
!= SCHED_PRESSURE_NONE
)
5337 fprintf (sched_dump
, "(cost=%d",
5338 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (p
[i
]));
5339 fprintf (sched_dump
, ":prio=%d", INSN_PRIORITY (p
[i
]));
5340 if (INSN_TICK (p
[i
]) > clock_var
)
5341 fprintf (sched_dump
, ":delay=%d", INSN_TICK (p
[i
]) - clock_var
);
5342 if (sched_pressure
== SCHED_PRESSURE_MODEL
)
5343 fprintf (sched_dump
, ":idx=%d",
5344 model_index (p
[i
]));
5345 if (sched_pressure
!= SCHED_PRESSURE_NONE
)
5346 fprintf (sched_dump
, ")");
5348 fprintf (sched_dump
, "\n");
5351 /* Print the ready list. Callable from debugger. */
5353 debug_ready_list (struct ready_list
*ready
)
5355 debug_ready_list_1 (ready
, NULL
);
5358 /* Search INSN for REG_SAVE_NOTE notes and convert them back into insn
5359 NOTEs. This is used for NOTE_INSN_EPILOGUE_BEG, so that sched-ebb
5360 replaces the epilogue note in the correct basic block. */
5362 reemit_notes (rtx insn
)
5364 rtx note
, last
= insn
;
5366 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
5368 if (REG_NOTE_KIND (note
) == REG_SAVE_NOTE
)
5370 enum insn_note note_type
= (enum insn_note
) INTVAL (XEXP (note
, 0));
5372 last
= emit_note_before (note_type
, last
);
5373 remove_note (insn
, note
);
5378 /* Move INSN. Reemit notes if needed. Update CFG, if needed. */
5380 move_insn (rtx insn
, rtx last
, rtx nt
)
5382 if (PREV_INSN (insn
) != last
)
5388 bb
= BLOCK_FOR_INSN (insn
);
5390 /* BB_HEAD is either LABEL or NOTE. */
5391 gcc_assert (BB_HEAD (bb
) != insn
);
5393 if (BB_END (bb
) == insn
)
5394 /* If this is last instruction in BB, move end marker one
5397 /* Jumps are always placed at the end of basic block. */
5398 jump_p
= control_flow_insn_p (insn
);
5401 || ((common_sched_info
->sched_pass_id
== SCHED_RGN_PASS
)
5402 && IS_SPECULATION_BRANCHY_CHECK_P (insn
))
5403 || (common_sched_info
->sched_pass_id
5404 == SCHED_EBB_PASS
));
5406 gcc_assert (BLOCK_FOR_INSN (PREV_INSN (insn
)) == bb
);
5408 BB_END (bb
) = PREV_INSN (insn
);
5411 gcc_assert (BB_END (bb
) != last
);
5414 /* We move the block note along with jump. */
5418 note
= NEXT_INSN (insn
);
5419 while (NOTE_NOT_BB_P (note
) && note
!= nt
)
5420 note
= NEXT_INSN (note
);
5424 || BARRIER_P (note
)))
5425 note
= NEXT_INSN (note
);
5427 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
5432 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (note
);
5433 PREV_INSN (NEXT_INSN (note
)) = PREV_INSN (insn
);
5435 NEXT_INSN (note
) = NEXT_INSN (last
);
5436 PREV_INSN (NEXT_INSN (last
)) = note
;
5438 NEXT_INSN (last
) = insn
;
5439 PREV_INSN (insn
) = last
;
5441 bb
= BLOCK_FOR_INSN (last
);
5445 fix_jump_move (insn
);
5447 if (BLOCK_FOR_INSN (insn
) != bb
)
5448 move_block_after_check (insn
);
5450 gcc_assert (BB_END (bb
) == last
);
5453 df_insn_change_bb (insn
, bb
);
5455 /* Update BB_END, if needed. */
5456 if (BB_END (bb
) == last
)
5460 SCHED_GROUP_P (insn
) = 0;
5463 /* Return true if scheduling INSN will finish current clock cycle. */
5465 insn_finishes_cycle_p (rtx insn
)
5467 if (SCHED_GROUP_P (insn
))
5468 /* After issuing INSN, rest of the sched_group will be forced to issue
5469 in order. Don't make any plans for the rest of cycle. */
5472 /* Finishing the block will, apparently, finish the cycle. */
5473 if (current_sched_info
->insn_finishes_block_p
5474 && current_sched_info
->insn_finishes_block_p (insn
))
5480 /* Functions to model cache auto-prefetcher.
5482 Some of the CPUs have cache auto-prefetcher, which /seems/ to initiate
5483 memory prefetches if it sees instructions with consequitive memory accesses
5484 in the instruction stream. Details of such hardware units are not published,
5485 so we can only guess what exactly is going on there.
5486 In the scheduler, we model abstract auto-prefetcher. If there are memory
5487 insns in the ready list (or the queue) that have same memory base, but
5488 different offsets, then we delay the insns with larger offsets until insns
5489 with smaller offsets get scheduled. If PARAM_SCHED_AUTOPREF_QUEUE_DEPTH
5490 is "1", then we look at the ready list; if it is N>1, then we also look
5491 through N-1 queue entries.
5492 If the param is N>=0, then rank_for_schedule will consider auto-prefetching
5493 among its heuristics.
5494 Param value of "-1" disables modelling of the auto-prefetcher. */
5496 /* Initialize autoprefetcher model data for INSN. */
5498 autopref_multipass_init (const rtx insn
, int write
)
5500 autopref_multipass_data_t data
= &INSN_AUTOPREF_MULTIPASS_DATA (insn
)[write
];
5502 gcc_assert (data
->status
== AUTOPREF_MULTIPASS_DATA_UNINITIALIZED
);
5503 data
->base
= NULL_RTX
;
5505 /* Set insn entry initialized, but not relevant for auto-prefetcher. */
5506 data
->status
= AUTOPREF_MULTIPASS_DATA_IRRELEVANT
;
5508 rtx set
= single_set (insn
);
5509 if (set
== NULL_RTX
)
5512 rtx mem
= write
? SET_DEST (set
) : SET_SRC (set
);
5516 struct address_info info
;
5517 decompose_mem_address (&info
, mem
);
5519 /* TODO: Currently only (base+const) addressing is supported. */
5520 if (info
.base
== NULL
|| !REG_P (*info
.base
)
5521 || (info
.disp
!= NULL
&& !CONST_INT_P (*info
.disp
)))
5524 /* This insn is relevant for auto-prefetcher. */
5525 data
->base
= *info
.base
;
5526 data
->offset
= info
.disp
? INTVAL (*info
.disp
) : 0;
5527 data
->status
= AUTOPREF_MULTIPASS_DATA_NORMAL
;
5530 /* Helper function for rank_for_schedule sorting. */
5532 autopref_rank_for_schedule (const rtx insn1
, const rtx insn2
)
5534 for (int write
= 0; write
< 2; ++write
)
5536 autopref_multipass_data_t data1
5537 = &INSN_AUTOPREF_MULTIPASS_DATA (insn1
)[write
];
5538 autopref_multipass_data_t data2
5539 = &INSN_AUTOPREF_MULTIPASS_DATA (insn2
)[write
];
5541 if (data1
->status
== AUTOPREF_MULTIPASS_DATA_UNINITIALIZED
)
5542 autopref_multipass_init (insn1
, write
);
5543 if (data1
->status
== AUTOPREF_MULTIPASS_DATA_IRRELEVANT
)
5546 if (data2
->status
== AUTOPREF_MULTIPASS_DATA_UNINITIALIZED
)
5547 autopref_multipass_init (insn2
, write
);
5548 if (data2
->status
== AUTOPREF_MULTIPASS_DATA_IRRELEVANT
)
5551 if (!rtx_equal_p (data1
->base
, data2
->base
))
5554 return data1
->offset
- data2
->offset
;
5560 /* True if header of debug dump was printed. */
5561 static bool autopref_multipass_dfa_lookahead_guard_started_dump_p
;
5563 /* Helper for autopref_multipass_dfa_lookahead_guard.
5564 Return "1" if INSN1 should be delayed in favor of INSN2. */
5566 autopref_multipass_dfa_lookahead_guard_1 (const rtx insn1
,
5567 const rtx insn2
, int write
)
5569 autopref_multipass_data_t data1
5570 = &INSN_AUTOPREF_MULTIPASS_DATA (insn1
)[write
];
5571 autopref_multipass_data_t data2
5572 = &INSN_AUTOPREF_MULTIPASS_DATA (insn2
)[write
];
5574 if (data2
->status
== AUTOPREF_MULTIPASS_DATA_UNINITIALIZED
)
5575 autopref_multipass_init (insn2
, write
);
5576 if (data2
->status
== AUTOPREF_MULTIPASS_DATA_IRRELEVANT
)
5579 if (rtx_equal_p (data1
->base
, data2
->base
)
5580 && data1
->offset
> data2
->offset
)
5582 if (sched_verbose
>= 2)
5584 if (!autopref_multipass_dfa_lookahead_guard_started_dump_p
)
5586 fprintf (sched_dump
,
5587 ";;\t\tnot trying in max_issue due to autoprefetch "
5589 autopref_multipass_dfa_lookahead_guard_started_dump_p
= true;
5592 fprintf (sched_dump
, " %d(%d)", INSN_UID (insn1
), INSN_UID (insn2
));
5603 We could have also hooked autoprefetcher model into
5604 first_cycle_multipass_backtrack / first_cycle_multipass_issue hooks
5605 to enable intelligent selection of "[r1+0]=r2; [r1+4]=r3" on the same cycle
5606 (e.g., once "[r1+0]=r2" is issued in max_issue(), "[r1+4]=r3" gets
5607 unblocked). We don't bother about this yet because target of interest
5608 (ARM Cortex-A15) can issue only 1 memory operation per cycle. */
5610 /* Implementation of first_cycle_multipass_dfa_lookahead_guard hook.
5611 Return "1" if INSN1 should not be considered in max_issue due to
5612 auto-prefetcher considerations. */
5614 autopref_multipass_dfa_lookahead_guard (rtx insn1
, int ready_index
)
5618 if (PARAM_VALUE (PARAM_SCHED_AUTOPREF_QUEUE_DEPTH
) <= 0)
5621 if (sched_verbose
>= 2 && ready_index
== 0)
5622 autopref_multipass_dfa_lookahead_guard_started_dump_p
= false;
5624 for (int write
= 0; write
< 2; ++write
)
5626 autopref_multipass_data_t data1
5627 = &INSN_AUTOPREF_MULTIPASS_DATA (insn1
)[write
];
5629 if (data1
->status
== AUTOPREF_MULTIPASS_DATA_UNINITIALIZED
)
5630 autopref_multipass_init (insn1
, write
);
5631 if (data1
->status
== AUTOPREF_MULTIPASS_DATA_IRRELEVANT
)
5634 if (ready_index
== 0
5635 && data1
->status
== AUTOPREF_MULTIPASS_DATA_DONT_DELAY
)
5636 /* We allow only a single delay on priviledged instructions.
5637 Doing otherwise would cause infinite loop. */
5639 if (sched_verbose
>= 2)
5641 if (!autopref_multipass_dfa_lookahead_guard_started_dump_p
)
5643 fprintf (sched_dump
,
5644 ";;\t\tnot trying in max_issue due to autoprefetch "
5646 autopref_multipass_dfa_lookahead_guard_started_dump_p
= true;
5649 fprintf (sched_dump
, " *%d*", INSN_UID (insn1
));
5654 for (int i2
= 0; i2
< ready
.n_ready
; ++i2
)
5656 rtx insn2
= get_ready_element (i2
);
5659 r
= autopref_multipass_dfa_lookahead_guard_1 (insn1
, insn2
, write
);
5662 if (ready_index
== 0)
5665 data1
->status
= AUTOPREF_MULTIPASS_DATA_DONT_DELAY
;
5671 if (PARAM_VALUE (PARAM_SCHED_AUTOPREF_QUEUE_DEPTH
) == 1)
5674 /* Everything from the current queue slot should have been moved to
5676 gcc_assert (insn_queue
[NEXT_Q_AFTER (q_ptr
, 0)] == NULL_RTX
);
5678 int n_stalls
= PARAM_VALUE (PARAM_SCHED_AUTOPREF_QUEUE_DEPTH
) - 1;
5679 if (n_stalls
> max_insn_queue_index
)
5680 n_stalls
= max_insn_queue_index
;
5682 for (int stalls
= 1; stalls
<= n_stalls
; ++stalls
)
5684 for (rtx link
= insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)];
5686 link
= XEXP (link
, 1))
5688 rtx insn2
= XEXP (link
, 0);
5689 r
= autopref_multipass_dfa_lookahead_guard_1 (insn1
, insn2
,
5693 /* Queue INSN1 until INSN2 can issue. */
5695 if (ready_index
== 0)
5696 data1
->status
= AUTOPREF_MULTIPASS_DATA_DONT_DELAY
;
5704 if (sched_verbose
>= 2
5705 && autopref_multipass_dfa_lookahead_guard_started_dump_p
5706 && (ready_index
== ready
.n_ready
- 1 || r
< 0))
5707 /* This does not /always/ trigger. We don't output EOL if the last
5708 insn is not recognized (INSN_CODE < 0) and lookahead_guard is not
5709 called. We can live with this. */
5710 fprintf (sched_dump
, "\n");
5715 /* Define type for target data used in multipass scheduling. */
5716 #ifndef TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T
5717 # define TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T int
5719 typedef TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T first_cycle_multipass_data_t
;
5721 /* The following structure describe an entry of the stack of choices. */
5724 /* Ordinal number of the issued insn in the ready queue. */
5726 /* The number of the rest insns whose issues we should try. */
5728 /* The number of issued essential insns. */
5730 /* State after issuing the insn. */
5732 /* Target-specific data. */
5733 first_cycle_multipass_data_t target_data
;
5736 /* The following array is used to implement a stack of choices used in
5737 function max_issue. */
5738 static struct choice_entry
*choice_stack
;
5740 /* This holds the value of the target dfa_lookahead hook. */
5743 /* The following variable value is maximal number of tries of issuing
5744 insns for the first cycle multipass insn scheduling. We define
5745 this value as constant*(DFA_LOOKAHEAD**ISSUE_RATE). We would not
5746 need this constraint if all real insns (with non-negative codes)
5747 had reservations because in this case the algorithm complexity is
5748 O(DFA_LOOKAHEAD**ISSUE_RATE). Unfortunately, the dfa descriptions
5749 might be incomplete and such insn might occur. For such
5750 descriptions, the complexity of algorithm (without the constraint)
5751 could achieve DFA_LOOKAHEAD ** N , where N is the queue length. */
5752 static int max_lookahead_tries
;
5754 /* The following function returns maximal (or close to maximal) number
5755 of insns which can be issued on the same cycle and one of which
5756 insns is insns with the best rank (the first insn in READY). To
5757 make this function tries different samples of ready insns. READY
5758 is current queue `ready'. Global array READY_TRY reflects what
5759 insns are already issued in this try. The function stops immediately,
5760 if it reached the such a solution, that all instruction can be issued.
5761 INDEX will contain index of the best insn in READY. The following
5762 function is used only for first cycle multipass scheduling.
5766 This function expects recognized insns only. All USEs,
5767 CLOBBERs, etc must be filtered elsewhere. */
5769 max_issue (struct ready_list
*ready
, int privileged_n
, state_t state
,
5770 bool first_cycle_insn_p
, int *index
)
5772 int n
, i
, all
, n_ready
, best
, delay
, tries_num
;
5774 struct choice_entry
*top
;
5777 n_ready
= ready
->n_ready
;
5778 gcc_assert (dfa_lookahead
>= 1 && privileged_n
>= 0
5779 && privileged_n
<= n_ready
);
5781 /* Init MAX_LOOKAHEAD_TRIES. */
5782 if (max_lookahead_tries
== 0)
5784 max_lookahead_tries
= 100;
5785 for (i
= 0; i
< issue_rate
; i
++)
5786 max_lookahead_tries
*= dfa_lookahead
;
5789 /* Init max_points. */
5790 more_issue
= issue_rate
- cycle_issued_insns
;
5791 gcc_assert (more_issue
>= 0);
5793 /* The number of the issued insns in the best solution. */
5798 /* Set initial state of the search. */
5799 memcpy (top
->state
, state
, dfa_state_size
);
5800 top
->rest
= dfa_lookahead
;
5802 if (targetm
.sched
.first_cycle_multipass_begin
)
5803 targetm
.sched
.first_cycle_multipass_begin (&top
->target_data
,
5805 first_cycle_insn_p
);
5807 /* Count the number of the insns to search among. */
5808 for (all
= i
= 0; i
< n_ready
; i
++)
5812 if (sched_verbose
>= 2)
5814 fprintf (sched_dump
, ";;\t\tmax_issue among %d insns:", all
);
5815 debug_ready_list_1 (ready
, ready_try
);
5818 /* I is the index of the insn to try next. */
5823 if (/* If we've reached a dead end or searched enough of what we have
5826 /* or have nothing else to try... */
5828 /* or should not issue more. */
5829 || top
->n
>= more_issue
)
5831 /* ??? (... || i == n_ready). */
5832 gcc_assert (i
<= n_ready
);
5834 /* We should not issue more than issue_rate instructions. */
5835 gcc_assert (top
->n
<= more_issue
);
5837 if (top
== choice_stack
)
5840 if (best
< top
- choice_stack
)
5845 /* Try to find issued privileged insn. */
5846 while (n
&& !ready_try
[--n
])
5850 if (/* If all insns are equally good... */
5852 /* Or a privileged insn will be issued. */
5854 /* Then we have a solution. */
5856 best
= top
- choice_stack
;
5857 /* This is the index of the insn issued first in this
5859 *index
= choice_stack
[1].index
;
5860 if (top
->n
== more_issue
|| best
== all
)
5865 /* Set ready-list index to point to the last insn
5866 ('i++' below will advance it to the next insn). */
5872 if (targetm
.sched
.first_cycle_multipass_backtrack
)
5873 targetm
.sched
.first_cycle_multipass_backtrack (&top
->target_data
,
5874 ready_try
, n_ready
);
5877 memcpy (state
, top
->state
, dfa_state_size
);
5879 else if (!ready_try
[i
])
5882 if (tries_num
> max_lookahead_tries
)
5884 insn
= ready_element (ready
, i
);
5885 delay
= state_transition (state
, insn
);
5888 if (state_dead_lock_p (state
)
5889 || insn_finishes_cycle_p (insn
))
5890 /* We won't issue any more instructions in the next
5897 if (memcmp (top
->state
, state
, dfa_state_size
) != 0)
5900 /* Advance to the next choice_entry. */
5902 /* Initialize it. */
5903 top
->rest
= dfa_lookahead
;
5906 memcpy (top
->state
, state
, dfa_state_size
);
5909 if (targetm
.sched
.first_cycle_multipass_issue
)
5910 targetm
.sched
.first_cycle_multipass_issue (&top
->target_data
,
5920 /* Increase ready-list index. */
5924 if (targetm
.sched
.first_cycle_multipass_end
)
5925 targetm
.sched
.first_cycle_multipass_end (best
!= 0
5926 ? &choice_stack
[1].target_data
5929 /* Restore the original state of the DFA. */
5930 memcpy (state
, choice_stack
->state
, dfa_state_size
);
5935 /* The following function chooses insn from READY and modifies
5936 READY. The following function is used only for first
5937 cycle multipass scheduling.
5939 -1 if cycle should be advanced,
5940 0 if INSN_PTR is set to point to the desirable insn,
5941 1 if choose_ready () should be restarted without advancing the cycle. */
5943 choose_ready (struct ready_list
*ready
, bool first_cycle_insn_p
,
5946 if (dbg_cnt (sched_insn
) == false)
5948 if (nonscheduled_insns_begin
== NULL_RTX
)
5949 nonscheduled_insns_begin
= current_sched_info
->prev_head
;
5951 rtx insn
= first_nonscheduled_insn ();
5953 if (QUEUE_INDEX (insn
) == QUEUE_READY
)
5954 /* INSN is in the ready_list. */
5956 ready_remove_insn (insn
);
5961 /* INSN is in the queue. Advance cycle to move it to the ready list. */
5962 gcc_assert (QUEUE_INDEX (insn
) >= 0);
5966 if (dfa_lookahead
<= 0 || SCHED_GROUP_P (ready_element (ready
, 0))
5967 || DEBUG_INSN_P (ready_element (ready
, 0)))
5969 if (targetm
.sched
.dispatch (NULL_RTX
, IS_DISPATCH_ON
))
5970 *insn_ptr
= ready_remove_first_dispatch (ready
);
5972 *insn_ptr
= ready_remove_first (ready
);
5978 /* Try to choose the best insn. */
5982 insn
= ready_element (ready
, 0);
5983 if (INSN_CODE (insn
) < 0)
5985 *insn_ptr
= ready_remove_first (ready
);
5989 /* Filter the search space. */
5990 for (i
= 0; i
< ready
->n_ready
; i
++)
5994 insn
= ready_element (ready
, i
);
5996 /* If this insn is recognizable we should have already
5997 recognized it earlier.
5998 ??? Not very clear where this is supposed to be done.
6000 gcc_checking_assert (INSN_CODE (insn
) >= 0
6001 || recog_memoized (insn
) < 0);
6002 if (INSN_CODE (insn
) < 0)
6004 /* Non-recognized insns at position 0 are handled above. */
6010 if (targetm
.sched
.first_cycle_multipass_dfa_lookahead_guard
)
6013 = (targetm
.sched
.first_cycle_multipass_dfa_lookahead_guard
6016 if (ready_try
[i
] < 0)
6017 /* Queue instruction for several cycles.
6018 We need to restart choose_ready as we have changed
6021 change_queue_index (insn
, -ready_try
[i
]);
6025 /* Make sure that we didn't end up with 0'th insn filtered out.
6026 Don't be tempted to make life easier for backends and just
6027 requeue 0'th insn if (ready_try[0] == 0) and restart
6028 choose_ready. Backends should be very considerate about
6029 requeueing instructions -- especially the highest priority
6030 one at position 0. */
6031 gcc_assert (ready_try
[i
] == 0 || i
> 0);
6036 gcc_assert (ready_try
[i
] == 0);
6037 /* INSN made it through the scrutiny of filters! */
6040 if (max_issue (ready
, 1, curr_state
, first_cycle_insn_p
, &index
) == 0)
6042 *insn_ptr
= ready_remove_first (ready
);
6043 if (sched_verbose
>= 4)
6044 fprintf (sched_dump
, ";;\t\tChosen insn (but can't issue) : %s \n",
6045 (*current_sched_info
->print_insn
) (*insn_ptr
, 0));
6050 if (sched_verbose
>= 4)
6051 fprintf (sched_dump
, ";;\t\tChosen insn : %s\n",
6052 (*current_sched_info
->print_insn
)
6053 (ready_element (ready
, index
), 0));
6055 *insn_ptr
= ready_remove (ready
, index
);
6061 /* This function is called when we have successfully scheduled a
6062 block. It uses the schedule stored in the scheduled_insns vector
6063 to rearrange the RTL. PREV_HEAD is used as the anchor to which we
6064 append the scheduled insns; TAIL is the insn after the scheduled
6065 block. TARGET_BB is the argument passed to schedule_block. */
6068 commit_schedule (rtx prev_head
, rtx tail
, basic_block
*target_bb
)
6073 last_scheduled_insn
= prev_head
;
6075 scheduled_insns
.iterate (i
, &insn
);
6078 if (control_flow_insn_p (last_scheduled_insn
)
6079 || current_sched_info
->advance_target_bb (*target_bb
, insn
))
6081 *target_bb
= current_sched_info
->advance_target_bb (*target_bb
, 0);
6087 x
= next_real_insn (last_scheduled_insn
);
6089 dump_new_block_header (1, *target_bb
, x
, tail
);
6092 last_scheduled_insn
= bb_note (*target_bb
);
6095 if (current_sched_info
->begin_move_insn
)
6096 (*current_sched_info
->begin_move_insn
) (insn
, last_scheduled_insn
);
6097 move_insn (insn
, last_scheduled_insn
,
6098 current_sched_info
->next_tail
);
6099 if (!DEBUG_INSN_P (insn
))
6100 reemit_notes (insn
);
6101 last_scheduled_insn
= insn
;
6104 scheduled_insns
.truncate (0);
6107 /* Examine all insns on the ready list and queue those which can't be
6108 issued in this cycle. TEMP_STATE is temporary scheduler state we
6109 can use as scratch space. If FIRST_CYCLE_INSN_P is true, no insns
6110 have been issued for the current cycle, which means it is valid to
6111 issue an asm statement.
6113 If SHADOWS_ONLY_P is true, we eliminate all real insns and only
6114 leave those for which SHADOW_P is true. If MODULO_EPILOGUE is true,
6115 we only leave insns which have an INSN_EXACT_TICK. */
6118 prune_ready_list (state_t temp_state
, bool first_cycle_insn_p
,
6119 bool shadows_only_p
, bool modulo_epilogue_p
)
6122 bool sched_group_found
= false;
6123 int min_cost_group
= 1;
6125 for (i
= 0; i
< ready
.n_ready
; i
++)
6127 rtx insn
= ready_element (&ready
, i
);
6128 if (SCHED_GROUP_P (insn
))
6130 sched_group_found
= true;
6135 /* Make two passes if there's a SCHED_GROUP_P insn; make sure to handle
6136 such an insn first and note its cost, then schedule all other insns
6137 for one cycle later. */
6138 for (pass
= sched_group_found
? 0 : 1; pass
< 2; )
6140 int n
= ready
.n_ready
;
6141 for (i
= 0; i
< n
; i
++)
6143 rtx insn
= ready_element (&ready
, i
);
6145 const char *reason
= "resource conflict";
6147 if (DEBUG_INSN_P (insn
))
6150 if (sched_group_found
&& !SCHED_GROUP_P (insn
))
6154 cost
= min_cost_group
;
6155 reason
= "not in sched group";
6157 else if (modulo_epilogue_p
6158 && INSN_EXACT_TICK (insn
) == INVALID_TICK
)
6160 cost
= max_insn_queue_index
;
6161 reason
= "not an epilogue insn";
6163 else if (shadows_only_p
&& !SHADOW_P (insn
))
6166 reason
= "not a shadow";
6168 else if (recog_memoized (insn
) < 0)
6170 if (!first_cycle_insn_p
6171 && (GET_CODE (PATTERN (insn
)) == ASM_INPUT
6172 || asm_noperands (PATTERN (insn
)) >= 0))
6176 else if (sched_pressure
!= SCHED_PRESSURE_NONE
)
6178 if (sched_pressure
== SCHED_PRESSURE_MODEL
6179 && INSN_TICK (insn
) <= clock_var
)
6181 memcpy (temp_state
, curr_state
, dfa_state_size
);
6182 if (state_transition (temp_state
, insn
) >= 0)
6183 INSN_TICK (insn
) = clock_var
+ 1;
6191 if (delay_htab
.is_created ())
6193 struct delay_pair
*delay_entry
;
6195 = delay_htab
.find_with_hash (insn
,
6196 htab_hash_pointer (insn
));
6197 while (delay_entry
&& delay_cost
== 0)
6199 delay_cost
= estimate_shadow_tick (delay_entry
);
6200 if (delay_cost
> max_insn_queue_index
)
6201 delay_cost
= max_insn_queue_index
;
6202 delay_entry
= delay_entry
->next_same_i1
;
6206 memcpy (temp_state
, curr_state
, dfa_state_size
);
6207 cost
= state_transition (temp_state
, insn
);
6212 if (cost
< delay_cost
)
6215 reason
= "shadow tick";
6220 if (SCHED_GROUP_P (insn
) && cost
> min_cost_group
)
6221 min_cost_group
= cost
;
6222 ready_remove (&ready
, i
);
6223 queue_insn (insn
, cost
, reason
);
6233 /* Called when we detect that the schedule is impossible. We examine the
6234 backtrack queue to find the earliest insn that caused this condition. */
6236 static struct haifa_saved_data
*
6237 verify_shadows (void)
6239 struct haifa_saved_data
*save
, *earliest_fail
= NULL
;
6240 for (save
= backtrack_queue
; save
; save
= save
->next
)
6243 struct delay_pair
*pair
= save
->delay_pair
;
6246 for (; pair
; pair
= pair
->next_same_i1
)
6250 if (QUEUE_INDEX (i2
) == QUEUE_SCHEDULED
)
6253 t
= INSN_TICK (i1
) + pair_delay (pair
);
6256 if (sched_verbose
>= 2)
6257 fprintf (sched_dump
,
6258 ";;\t\tfailed delay requirements for %d/%d (%d->%d)"
6260 INSN_UID (pair
->i1
), INSN_UID (pair
->i2
),
6261 INSN_TICK (pair
->i1
), INSN_EXACT_TICK (pair
->i2
));
6262 earliest_fail
= save
;
6265 if (QUEUE_INDEX (i2
) >= 0)
6267 int queued_for
= INSN_TICK (i2
);
6271 if (sched_verbose
>= 2)
6272 fprintf (sched_dump
,
6273 ";;\t\tfailed delay requirements for %d/%d"
6274 " (%d->%d), queued too late\n",
6275 INSN_UID (pair
->i1
), INSN_UID (pair
->i2
),
6276 INSN_TICK (pair
->i1
), INSN_EXACT_TICK (pair
->i2
));
6277 earliest_fail
= save
;
6284 return earliest_fail
;
6287 /* Print instructions together with useful scheduling information between
6288 HEAD and TAIL (inclusive). */
6290 dump_insn_stream (rtx head
, rtx tail
)
6292 fprintf (sched_dump
, ";;\t| insn | prio |\n");
6294 rtx next_tail
= NEXT_INSN (tail
);
6295 for (rtx insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
6297 int priority
= NOTE_P (insn
) ? 0 : INSN_PRIORITY (insn
);
6298 const char *pattern
= (NOTE_P (insn
)
6300 : str_pattern_slim (PATTERN (insn
)));
6302 fprintf (sched_dump
, ";;\t| %4d | %4d | %-30s ",
6303 INSN_UID (insn
), priority
, pattern
);
6305 if (sched_verbose
>= 4)
6307 if (NOTE_P (insn
) || recog_memoized (insn
) < 0)
6308 fprintf (sched_dump
, "nothing");
6310 print_reservation (sched_dump
, insn
);
6312 fprintf (sched_dump
, "\n");
6316 /* Use forward list scheduling to rearrange insns of block pointed to by
6317 TARGET_BB, possibly bringing insns from subsequent blocks in the same
6321 schedule_block (basic_block
*target_bb
, state_t init_state
)
6324 bool success
= modulo_ii
== 0;
6325 struct sched_block_state ls
;
6326 state_t temp_state
= NULL
; /* It is used for multipass scheduling. */
6327 int sort_p
, advance
, start_clock_var
;
6329 /* Head/tail info for this block. */
6330 rtx prev_head
= current_sched_info
->prev_head
;
6331 rtx next_tail
= current_sched_info
->next_tail
;
6332 rtx head
= NEXT_INSN (prev_head
);
6333 rtx tail
= PREV_INSN (next_tail
);
6335 if ((current_sched_info
->flags
& DONT_BREAK_DEPENDENCIES
) == 0
6336 && sched_pressure
!= SCHED_PRESSURE_MODEL
)
6337 find_modifiable_mems (head
, tail
);
6339 /* We used to have code to avoid getting parameters moved from hard
6340 argument registers into pseudos.
6342 However, it was removed when it proved to be of marginal benefit
6343 and caused problems because schedule_block and compute_forward_dependences
6344 had different notions of what the "head" insn was. */
6346 gcc_assert (head
!= tail
|| INSN_P (head
));
6348 haifa_recovery_bb_recently_added_p
= false;
6350 backtrack_queue
= NULL
;
6355 dump_new_block_header (0, *target_bb
, head
, tail
);
6357 if (sched_verbose
>= 2)
6359 dump_insn_stream (head
, tail
);
6360 memset (&rank_for_schedule_stats
, 0,
6361 sizeof (rank_for_schedule_stats
));
6365 if (init_state
== NULL
)
6366 state_reset (curr_state
);
6368 memcpy (curr_state
, init_state
, dfa_state_size
);
6370 /* Clear the ready list. */
6371 ready
.first
= ready
.veclen
- 1;
6375 /* It is used for first cycle multipass scheduling. */
6376 temp_state
= alloca (dfa_state_size
);
6378 if (targetm
.sched
.init
)
6379 targetm
.sched
.init (sched_dump
, sched_verbose
, ready
.veclen
);
6381 /* We start inserting insns after PREV_HEAD. */
6382 last_scheduled_insn
= prev_head
;
6383 last_nondebug_scheduled_insn
= NULL_RTX
;
6384 nonscheduled_insns_begin
= NULL_RTX
;
6386 gcc_assert ((NOTE_P (last_scheduled_insn
)
6387 || DEBUG_INSN_P (last_scheduled_insn
))
6388 && BLOCK_FOR_INSN (last_scheduled_insn
) == *target_bb
);
6390 /* Initialize INSN_QUEUE. Q_SIZE is the total number of insns in the
6395 insn_queue
= XALLOCAVEC (rtx
, max_insn_queue_index
+ 1);
6396 memset (insn_queue
, 0, (max_insn_queue_index
+ 1) * sizeof (rtx
));
6398 /* Start just before the beginning of time. */
6401 /* We need queue and ready lists and clock_var be initialized
6402 in try_ready () (which is called through init_ready_list ()). */
6403 (*current_sched_info
->init_ready_list
) ();
6406 sched_pressure_start_bb (*target_bb
);
6408 /* The algorithm is O(n^2) in the number of ready insns at any given
6409 time in the worst case. Before reload we are more likely to have
6410 big lists so truncate them to a reasonable size. */
6411 if (!reload_completed
6412 && ready
.n_ready
- ready
.n_debug
> MAX_SCHED_READY_INSNS
)
6414 ready_sort_debug (&ready
);
6415 ready_sort_real (&ready
);
6417 /* Find first free-standing insn past MAX_SCHED_READY_INSNS.
6418 If there are debug insns, we know they're first. */
6419 for (i
= MAX_SCHED_READY_INSNS
+ ready
.n_debug
; i
< ready
.n_ready
; i
++)
6420 if (!SCHED_GROUP_P (ready_element (&ready
, i
)))
6423 if (sched_verbose
>= 2)
6425 fprintf (sched_dump
,
6426 ";;\t\tReady list on entry: %d insns: ", ready
.n_ready
);
6427 debug_ready_list (&ready
);
6428 fprintf (sched_dump
,
6429 ";;\t\t before reload => truncated to %d insns\n", i
);
6432 /* Delay all insns past it for 1 cycle. If debug counter is
6433 activated make an exception for the insn right after
6434 nonscheduled_insns_begin. */
6438 if (dbg_cnt (sched_insn
) == false)
6439 skip_insn
= first_nonscheduled_insn ();
6441 skip_insn
= NULL_RTX
;
6443 while (i
< ready
.n_ready
)
6447 insn
= ready_remove (&ready
, i
);
6449 if (insn
!= skip_insn
)
6450 queue_insn (insn
, 1, "list truncated");
6453 ready_add (&ready
, skip_insn
, true);
6457 /* Now we can restore basic block notes and maintain precise cfg. */
6458 restore_bb_notes (*target_bb
);
6460 last_clock_var
= -1;
6464 gcc_assert (scheduled_insns
.length () == 0);
6466 must_backtrack
= false;
6467 modulo_insns_scheduled
= 0;
6469 ls
.modulo_epilogue
= false;
6470 ls
.first_cycle_insn_p
= true;
6472 /* Loop until all the insns in BB are scheduled. */
6473 while ((*current_sched_info
->schedule_more_p
) ())
6475 perform_replacements_new_cycle ();
6478 start_clock_var
= clock_var
;
6482 advance_one_cycle ();
6484 /* Add to the ready list all pending insns that can be issued now.
6485 If there are no ready insns, increment clock until one
6486 is ready and add all pending insns at that point to the ready
6488 queue_to_ready (&ready
);
6490 gcc_assert (ready
.n_ready
);
6492 if (sched_verbose
>= 2)
6494 fprintf (sched_dump
, ";;\t\tReady list after queue_to_ready:");
6495 debug_ready_list (&ready
);
6497 advance
-= clock_var
- start_clock_var
;
6499 while (advance
> 0);
6501 if (ls
.modulo_epilogue
)
6503 int stage
= clock_var
/ modulo_ii
;
6504 if (stage
> modulo_last_stage
* 2 + 2)
6506 if (sched_verbose
>= 2)
6507 fprintf (sched_dump
,
6508 ";;\t\tmodulo scheduled succeeded at II %d\n",
6514 else if (modulo_ii
> 0)
6516 int stage
= clock_var
/ modulo_ii
;
6517 if (stage
> modulo_max_stages
)
6519 if (sched_verbose
>= 2)
6520 fprintf (sched_dump
,
6521 ";;\t\tfailing schedule due to excessive stages\n");
6524 if (modulo_n_insns
== modulo_insns_scheduled
6525 && stage
> modulo_last_stage
)
6527 if (sched_verbose
>= 2)
6528 fprintf (sched_dump
,
6529 ";;\t\tfound kernel after %d stages, II %d\n",
6531 ls
.modulo_epilogue
= true;
6535 prune_ready_list (temp_state
, true, false, ls
.modulo_epilogue
);
6536 if (ready
.n_ready
== 0)
6541 ls
.shadows_only_p
= false;
6542 cycle_issued_insns
= 0;
6543 ls
.can_issue_more
= issue_rate
;
6550 if (sort_p
&& ready
.n_ready
> 0)
6552 /* Sort the ready list based on priority. This must be
6553 done every iteration through the loop, as schedule_insn
6554 may have readied additional insns that will not be
6555 sorted correctly. */
6556 ready_sort (&ready
);
6558 if (sched_verbose
>= 2)
6560 fprintf (sched_dump
,
6561 ";;\t\tReady list after ready_sort: ");
6562 debug_ready_list (&ready
);
6566 /* We don't want md sched reorder to even see debug isns, so put
6567 them out right away. */
6568 if (ready
.n_ready
&& DEBUG_INSN_P (ready_element (&ready
, 0))
6569 && (*current_sched_info
->schedule_more_p
) ())
6571 while (ready
.n_ready
&& DEBUG_INSN_P (ready_element (&ready
, 0)))
6573 rtx insn
= ready_remove_first (&ready
);
6574 gcc_assert (DEBUG_INSN_P (insn
));
6575 (*current_sched_info
->begin_schedule_ready
) (insn
);
6576 scheduled_insns
.safe_push (insn
);
6577 last_scheduled_insn
= insn
;
6578 advance
= schedule_insn (insn
);
6579 gcc_assert (advance
== 0);
6580 if (ready
.n_ready
> 0)
6581 ready_sort (&ready
);
6585 if (ls
.first_cycle_insn_p
&& !ready
.n_ready
)
6588 resume_after_backtrack
:
6589 /* Allow the target to reorder the list, typically for
6590 better instruction bundling. */
6592 && (ready
.n_ready
== 0
6593 || !SCHED_GROUP_P (ready_element (&ready
, 0))))
6595 if (ls
.first_cycle_insn_p
&& targetm
.sched
.reorder
)
6597 = targetm
.sched
.reorder (sched_dump
, sched_verbose
,
6598 ready_lastpos (&ready
),
6599 &ready
.n_ready
, clock_var
);
6600 else if (!ls
.first_cycle_insn_p
&& targetm
.sched
.reorder2
)
6602 = targetm
.sched
.reorder2 (sched_dump
, sched_verbose
,
6604 ? ready_lastpos (&ready
) : NULL
,
6605 &ready
.n_ready
, clock_var
);
6608 restart_choose_ready
:
6609 if (sched_verbose
>= 2)
6611 fprintf (sched_dump
, ";;\tReady list (t = %3d): ",
6613 debug_ready_list (&ready
);
6614 if (sched_pressure
== SCHED_PRESSURE_WEIGHTED
)
6615 print_curr_reg_pressure ();
6618 if (ready
.n_ready
== 0
6619 && ls
.can_issue_more
6620 && reload_completed
)
6622 /* Allow scheduling insns directly from the queue in case
6623 there's nothing better to do (ready list is empty) but
6624 there are still vacant dispatch slots in the current cycle. */
6625 if (sched_verbose
>= 6)
6626 fprintf (sched_dump
,";;\t\tSecond chance\n");
6627 memcpy (temp_state
, curr_state
, dfa_state_size
);
6628 if (early_queue_to_ready (temp_state
, &ready
))
6629 ready_sort (&ready
);
6632 if (ready
.n_ready
== 0
6633 || !ls
.can_issue_more
6634 || state_dead_lock_p (curr_state
)
6635 || !(*current_sched_info
->schedule_more_p
) ())
6638 /* Select and remove the insn from the ready list. */
6644 res
= choose_ready (&ready
, ls
.first_cycle_insn_p
, &insn
);
6650 goto restart_choose_ready
;
6652 gcc_assert (insn
!= NULL_RTX
);
6655 insn
= ready_remove_first (&ready
);
6657 if (sched_pressure
!= SCHED_PRESSURE_NONE
6658 && INSN_TICK (insn
) > clock_var
)
6660 ready_add (&ready
, insn
, true);
6665 if (targetm
.sched
.dfa_new_cycle
6666 && targetm
.sched
.dfa_new_cycle (sched_dump
, sched_verbose
,
6667 insn
, last_clock_var
,
6668 clock_var
, &sort_p
))
6669 /* SORT_P is used by the target to override sorting
6670 of the ready list. This is needed when the target
6671 has modified its internal structures expecting that
6672 the insn will be issued next. As we need the insn
6673 to have the highest priority (so it will be returned by
6674 the ready_remove_first call above), we invoke
6675 ready_add (&ready, insn, true).
6676 But, still, there is one issue: INSN can be later
6677 discarded by scheduler's front end through
6678 current_sched_info->can_schedule_ready_p, hence, won't
6681 ready_add (&ready
, insn
, true);
6687 if (current_sched_info
->can_schedule_ready_p
6688 && ! (*current_sched_info
->can_schedule_ready_p
) (insn
))
6689 /* We normally get here only if we don't want to move
6690 insn from the split block. */
6692 TODO_SPEC (insn
) = DEP_POSTPONED
;
6693 goto restart_choose_ready
;
6696 if (delay_htab
.is_created ())
6698 /* If this insn is the first part of a delay-slot pair, record a
6700 struct delay_pair
*delay_entry
;
6702 = delay_htab
.find_with_hash (insn
, htab_hash_pointer (insn
));
6705 save_backtrack_point (delay_entry
, ls
);
6706 if (sched_verbose
>= 2)
6707 fprintf (sched_dump
, ";;\t\tsaving backtrack point\n");
6711 /* DECISION is made. */
6713 if (modulo_ii
> 0 && INSN_UID (insn
) < modulo_iter0_max_uid
)
6715 modulo_insns_scheduled
++;
6716 modulo_last_stage
= clock_var
/ modulo_ii
;
6718 if (TODO_SPEC (insn
) & SPECULATIVE
)
6719 generate_recovery_code (insn
);
6721 if (targetm
.sched
.dispatch (NULL_RTX
, IS_DISPATCH_ON
))
6722 targetm
.sched
.dispatch_do (insn
, ADD_TO_DISPATCH_WINDOW
);
6724 /* Update counters, etc in the scheduler's front end. */
6725 (*current_sched_info
->begin_schedule_ready
) (insn
);
6726 scheduled_insns
.safe_push (insn
);
6727 gcc_assert (NONDEBUG_INSN_P (insn
));
6728 last_nondebug_scheduled_insn
= last_scheduled_insn
= insn
;
6730 if (recog_memoized (insn
) >= 0)
6732 memcpy (temp_state
, curr_state
, dfa_state_size
);
6733 cost
= state_transition (curr_state
, insn
);
6734 if (sched_pressure
!= SCHED_PRESSURE_WEIGHTED
)
6735 gcc_assert (cost
< 0);
6736 if (memcmp (temp_state
, curr_state
, dfa_state_size
) != 0)
6737 cycle_issued_insns
++;
6741 asm_p
= (GET_CODE (PATTERN (insn
)) == ASM_INPUT
6742 || asm_noperands (PATTERN (insn
)) >= 0);
6744 if (targetm
.sched
.variable_issue
)
6746 targetm
.sched
.variable_issue (sched_dump
, sched_verbose
,
6747 insn
, ls
.can_issue_more
);
6748 /* A naked CLOBBER or USE generates no instruction, so do
6749 not count them against the issue rate. */
6750 else if (GET_CODE (PATTERN (insn
)) != USE
6751 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
6752 ls
.can_issue_more
--;
6753 advance
= schedule_insn (insn
);
6755 if (SHADOW_P (insn
))
6756 ls
.shadows_only_p
= true;
6758 /* After issuing an asm insn we should start a new cycle. */
6759 if (advance
== 0 && asm_p
)
6768 ls
.first_cycle_insn_p
= false;
6769 if (ready
.n_ready
> 0)
6770 prune_ready_list (temp_state
, false, ls
.shadows_only_p
,
6771 ls
.modulo_epilogue
);
6775 if (!must_backtrack
)
6776 for (i
= 0; i
< ready
.n_ready
; i
++)
6778 rtx insn
= ready_element (&ready
, i
);
6779 if (INSN_EXACT_TICK (insn
) == clock_var
)
6781 must_backtrack
= true;
6786 if (must_backtrack
&& modulo_ii
> 0)
6788 if (modulo_backtracks_left
== 0)
6790 modulo_backtracks_left
--;
6792 while (must_backtrack
)
6794 struct haifa_saved_data
*failed
;
6797 must_backtrack
= false;
6798 failed
= verify_shadows ();
6799 gcc_assert (failed
);
6801 failed_insn
= failed
->delay_pair
->i1
;
6802 /* Clear these queues. */
6803 perform_replacements_new_cycle ();
6804 toggle_cancelled_flags (false);
6805 unschedule_insns_until (failed_insn
);
6806 while (failed
!= backtrack_queue
)
6807 free_topmost_backtrack_point (true);
6808 restore_last_backtrack_point (&ls
);
6809 if (sched_verbose
>= 2)
6810 fprintf (sched_dump
, ";;\t\trewind to cycle %d\n", clock_var
);
6811 /* Delay by at least a cycle. This could cause additional
6813 queue_insn (failed_insn
, 1, "backtracked");
6817 if (ready
.n_ready
> 0)
6818 goto resume_after_backtrack
;
6821 if (clock_var
== 0 && ls
.first_cycle_insn_p
)
6827 ls
.first_cycle_insn_p
= true;
6829 if (ls
.modulo_epilogue
)
6832 if (!ls
.first_cycle_insn_p
|| advance
)
6833 advance_one_cycle ();
6834 perform_replacements_new_cycle ();
6837 /* Once again, debug insn suckiness: they can be on the ready list
6838 even if they have unresolved dependencies. To make our view
6839 of the world consistent, remove such "ready" insns. */
6840 restart_debug_insn_loop
:
6841 for (i
= ready
.n_ready
- 1; i
>= 0; i
--)
6845 x
= ready_element (&ready
, i
);
6846 if (DEPS_LIST_FIRST (INSN_HARD_BACK_DEPS (x
)) != NULL
6847 || DEPS_LIST_FIRST (INSN_SPEC_BACK_DEPS (x
)) != NULL
)
6849 ready_remove (&ready
, i
);
6850 goto restart_debug_insn_loop
;
6853 for (i
= ready
.n_ready
- 1; i
>= 0; i
--)
6857 x
= ready_element (&ready
, i
);
6858 resolve_dependencies (x
);
6860 for (i
= 0; i
<= max_insn_queue_index
; i
++)
6863 while ((link
= insn_queue
[i
]) != NULL
)
6865 rtx x
= XEXP (link
, 0);
6866 insn_queue
[i
] = XEXP (link
, 1);
6867 QUEUE_INDEX (x
) = QUEUE_NOWHERE
;
6868 free_INSN_LIST_node (link
);
6869 resolve_dependencies (x
);
6875 undo_all_replacements ();
6880 fprintf (sched_dump
, ";;\tReady list (final): ");
6881 debug_ready_list (&ready
);
6884 if (modulo_ii
== 0 && current_sched_info
->queue_must_finish_empty
)
6885 /* Sanity check -- queue must be empty now. Meaningless if region has
6887 gcc_assert (!q_size
&& !ready
.n_ready
&& !ready
.n_debug
);
6888 else if (modulo_ii
== 0)
6890 /* We must maintain QUEUE_INDEX between blocks in region. */
6891 for (i
= ready
.n_ready
- 1; i
>= 0; i
--)
6895 x
= ready_element (&ready
, i
);
6896 QUEUE_INDEX (x
) = QUEUE_NOWHERE
;
6897 TODO_SPEC (x
) = HARD_DEP
;
6901 for (i
= 0; i
<= max_insn_queue_index
; i
++)
6904 for (link
= insn_queue
[i
]; link
; link
= XEXP (link
, 1))
6909 QUEUE_INDEX (x
) = QUEUE_NOWHERE
;
6910 TODO_SPEC (x
) = HARD_DEP
;
6912 free_INSN_LIST_list (&insn_queue
[i
]);
6916 if (sched_pressure
== SCHED_PRESSURE_MODEL
)
6917 model_end_schedule ();
6921 commit_schedule (prev_head
, tail
, target_bb
);
6923 fprintf (sched_dump
, ";; total time = %d\n", clock_var
);
6926 last_scheduled_insn
= tail
;
6928 scheduled_insns
.truncate (0);
6930 if (!current_sched_info
->queue_must_finish_empty
6931 || haifa_recovery_bb_recently_added_p
)
6933 /* INSN_TICK (minimum clock tick at which the insn becomes
6934 ready) may be not correct for the insn in the subsequent
6935 blocks of the region. We should use a correct value of
6936 `clock_var' or modify INSN_TICK. It is better to keep
6937 clock_var value equal to 0 at the start of a basic block.
6938 Therefore we modify INSN_TICK here. */
6939 fix_inter_tick (NEXT_INSN (prev_head
), last_scheduled_insn
);
6942 if (targetm
.sched
.finish
)
6944 targetm
.sched
.finish (sched_dump
, sched_verbose
);
6945 /* Target might have added some instructions to the scheduled block
6946 in its md_finish () hook. These new insns don't have any data
6947 initialized and to identify them we extend h_i_d so that they'll
6949 sched_extend_luids ();
6952 /* Update head/tail boundaries. */
6953 head
= NEXT_INSN (prev_head
);
6954 tail
= last_scheduled_insn
;
6958 fprintf (sched_dump
, ";; new head = %d\n;; new tail = %d\n",
6959 INSN_UID (head
), INSN_UID (tail
));
6961 if (sched_verbose
>= 2)
6963 dump_insn_stream (head
, tail
);
6964 print_rank_for_schedule_stats (";; TOTAL ", &rank_for_schedule_stats
,
6968 fprintf (sched_dump
, "\n");
6971 head
= restore_other_notes (head
, NULL
);
6973 current_sched_info
->head
= head
;
6974 current_sched_info
->tail
= tail
;
6976 free_backtrack_queue ();
6981 /* Set_priorities: compute priority of each insn in the block. */
6984 set_priorities (rtx head
, rtx tail
)
6988 int sched_max_insns_priority
=
6989 current_sched_info
->sched_max_insns_priority
;
6992 if (head
== tail
&& ! INSN_P (head
))
6997 prev_head
= PREV_INSN (head
);
6998 for (insn
= tail
; insn
!= prev_head
; insn
= PREV_INSN (insn
))
7004 (void) priority (insn
);
7006 gcc_assert (INSN_PRIORITY_KNOWN (insn
));
7008 sched_max_insns_priority
= MAX (sched_max_insns_priority
,
7009 INSN_PRIORITY (insn
));
7012 current_sched_info
->sched_max_insns_priority
= sched_max_insns_priority
;
7017 /* Set dump and sched_verbose for the desired debugging output. If no
7018 dump-file was specified, but -fsched-verbose=N (any N), print to stderr.
7019 For -fsched-verbose=N, N>=10, print everything to stderr. */
7021 setup_sched_dump (void)
7023 sched_verbose
= sched_verbose_param
;
7024 if (sched_verbose_param
== 0 && dump_file
)
7026 sched_dump
= ((sched_verbose_param
>= 10 || !dump_file
)
7027 ? stderr
: dump_file
);
7030 /* Allocate data for register pressure sensitive scheduling. */
7032 alloc_global_sched_pressure_data (void)
7034 if (sched_pressure
!= SCHED_PRESSURE_NONE
)
7036 int i
, max_regno
= max_reg_num ();
7038 if (sched_dump
!= NULL
)
7039 /* We need info about pseudos for rtl dumps about pseudo
7040 classes and costs. */
7041 regstat_init_n_sets_and_refs ();
7042 ira_set_pseudo_classes (true, sched_verbose
? sched_dump
: NULL
);
7043 sched_regno_pressure_class
7044 = (enum reg_class
*) xmalloc (max_regno
* sizeof (enum reg_class
));
7045 for (i
= 0; i
< max_regno
; i
++)
7046 sched_regno_pressure_class
[i
]
7047 = (i
< FIRST_PSEUDO_REGISTER
7048 ? ira_pressure_class_translate
[REGNO_REG_CLASS (i
)]
7049 : ira_pressure_class_translate
[reg_allocno_class (i
)]);
7050 curr_reg_live
= BITMAP_ALLOC (NULL
);
7051 if (sched_pressure
== SCHED_PRESSURE_WEIGHTED
)
7053 saved_reg_live
= BITMAP_ALLOC (NULL
);
7054 region_ref_regs
= BITMAP_ALLOC (NULL
);
7057 /* Calculate number of CALL_USED_REGS in register classes that
7058 we calculate register pressure for. */
7059 for (int c
= 0; c
< ira_pressure_classes_num
; ++c
)
7061 enum reg_class cl
= ira_pressure_classes
[c
];
7063 call_used_regs_num
[cl
] = 0;
7065 for (int i
= 0; i
< ira_class_hard_regs_num
[cl
]; ++i
)
7066 if (call_used_regs
[ira_class_hard_regs
[cl
][i
]])
7067 ++call_used_regs_num
[cl
];
7072 /* Free data for register pressure sensitive scheduling. Also called
7073 from schedule_region when stopping sched-pressure early. */
7075 free_global_sched_pressure_data (void)
7077 if (sched_pressure
!= SCHED_PRESSURE_NONE
)
7079 if (regstat_n_sets_and_refs
!= NULL
)
7080 regstat_free_n_sets_and_refs ();
7081 if (sched_pressure
== SCHED_PRESSURE_WEIGHTED
)
7083 BITMAP_FREE (region_ref_regs
);
7084 BITMAP_FREE (saved_reg_live
);
7086 BITMAP_FREE (curr_reg_live
);
7087 free (sched_regno_pressure_class
);
7091 /* Initialize some global state for the scheduler. This function works
7092 with the common data shared between all the schedulers. It is called
7093 from the scheduler specific initialization routine. */
7098 /* Disable speculative loads in their presence if cc0 defined. */
7100 flag_schedule_speculative_load
= 0;
7103 if (targetm
.sched
.dispatch (NULL_RTX
, IS_DISPATCH_ON
))
7104 targetm
.sched
.dispatch_do (NULL_RTX
, DISPATCH_INIT
);
7106 if (live_range_shrinkage_p
)
7107 sched_pressure
= SCHED_PRESSURE_WEIGHTED
;
7108 else if (flag_sched_pressure
7109 && !reload_completed
7110 && common_sched_info
->sched_pass_id
== SCHED_RGN_PASS
)
7111 sched_pressure
= ((enum sched_pressure_algorithm
)
7112 PARAM_VALUE (PARAM_SCHED_PRESSURE_ALGORITHM
));
7114 sched_pressure
= SCHED_PRESSURE_NONE
;
7116 if (sched_pressure
!= SCHED_PRESSURE_NONE
)
7117 ira_setup_eliminable_regset ();
7119 /* Initialize SPEC_INFO. */
7120 if (targetm
.sched
.set_sched_flags
)
7122 spec_info
= &spec_info_var
;
7123 targetm
.sched
.set_sched_flags (spec_info
);
7125 if (spec_info
->mask
!= 0)
7127 spec_info
->data_weakness_cutoff
=
7128 (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF
) * MAX_DEP_WEAK
) / 100;
7129 spec_info
->control_weakness_cutoff
=
7130 (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF
)
7131 * REG_BR_PROB_BASE
) / 100;
7134 /* So we won't read anything accidentally. */
7139 /* So we won't read anything accidentally. */
7142 /* Initialize issue_rate. */
7143 if (targetm
.sched
.issue_rate
)
7144 issue_rate
= targetm
.sched
.issue_rate ();
7148 if (targetm
.sched
.first_cycle_multipass_dfa_lookahead
7149 /* Don't use max_issue with reg_pressure scheduling. Multipass
7150 scheduling and reg_pressure scheduling undo each other's decisions. */
7151 && sched_pressure
== SCHED_PRESSURE_NONE
)
7152 dfa_lookahead
= targetm
.sched
.first_cycle_multipass_dfa_lookahead ();
7156 /* Set to "0" so that we recalculate. */
7157 max_lookahead_tries
= 0;
7159 if (targetm
.sched
.init_dfa_pre_cycle_insn
)
7160 targetm
.sched
.init_dfa_pre_cycle_insn ();
7162 if (targetm
.sched
.init_dfa_post_cycle_insn
)
7163 targetm
.sched
.init_dfa_post_cycle_insn ();
7166 dfa_state_size
= state_size ();
7168 init_alias_analysis ();
7171 df_set_flags (DF_LR_RUN_DCE
);
7172 df_note_add_problem ();
7174 /* More problems needed for interloop dep calculation in SMS. */
7175 if (common_sched_info
->sched_pass_id
== SCHED_SMS_PASS
)
7177 df_rd_add_problem ();
7178 df_chain_add_problem (DF_DU_CHAIN
+ DF_UD_CHAIN
);
7183 /* Do not run DCE after reload, as this can kill nops inserted
7185 if (reload_completed
)
7186 df_clear_flags (DF_LR_RUN_DCE
);
7188 regstat_compute_calls_crossed ();
7190 if (targetm
.sched
.init_global
)
7191 targetm
.sched
.init_global (sched_dump
, sched_verbose
, get_max_uid () + 1);
7193 alloc_global_sched_pressure_data ();
7195 curr_state
= xmalloc (dfa_state_size
);
7198 static void haifa_init_only_bb (basic_block
, basic_block
);
7200 /* Initialize data structures specific to the Haifa scheduler. */
7202 haifa_sched_init (void)
7204 setup_sched_dump ();
7207 scheduled_insns
.create (0);
7209 if (spec_info
!= NULL
)
7211 sched_deps_info
->use_deps_list
= 1;
7212 sched_deps_info
->generate_spec_deps
= 1;
7215 /* Initialize luids, dependency caches, target and h_i_d for the
7219 bbs
.create (n_basic_blocks_for_fn (cfun
));
7224 FOR_EACH_BB_FN (bb
, cfun
)
7225 bbs
.quick_push (bb
);
7226 sched_init_luids (bbs
);
7227 sched_deps_init (true);
7228 sched_extend_target ();
7229 haifa_init_h_i_d (bbs
);
7234 sched_init_only_bb
= haifa_init_only_bb
;
7235 sched_split_block
= sched_split_block_1
;
7236 sched_create_empty_bb
= sched_create_empty_bb_1
;
7237 haifa_recovery_bb_ever_added_p
= false;
7239 nr_begin_data
= nr_begin_control
= nr_be_in_data
= nr_be_in_control
= 0;
7240 before_recovery
= 0;
7246 /* Finish work with the data specific to the Haifa scheduler. */
7248 haifa_sched_finish (void)
7250 sched_create_empty_bb
= NULL
;
7251 sched_split_block
= NULL
;
7252 sched_init_only_bb
= NULL
;
7254 if (spec_info
&& spec_info
->dump
)
7256 char c
= reload_completed
? 'a' : 'b';
7258 fprintf (spec_info
->dump
,
7259 ";; %s:\n", current_function_name ());
7261 fprintf (spec_info
->dump
,
7262 ";; Procedure %cr-begin-data-spec motions == %d\n",
7264 fprintf (spec_info
->dump
,
7265 ";; Procedure %cr-be-in-data-spec motions == %d\n",
7267 fprintf (spec_info
->dump
,
7268 ";; Procedure %cr-begin-control-spec motions == %d\n",
7269 c
, nr_begin_control
);
7270 fprintf (spec_info
->dump
,
7271 ";; Procedure %cr-be-in-control-spec motions == %d\n",
7272 c
, nr_be_in_control
);
7275 scheduled_insns
.release ();
7277 /* Finalize h_i_d, dependency caches, and luids for the whole
7278 function. Target will be finalized in md_global_finish (). */
7279 sched_deps_finish ();
7280 sched_finish_luids ();
7281 current_sched_info
= NULL
;
7285 /* Free global data used during insn scheduling. This function works with
7286 the common data shared between the schedulers. */
7291 haifa_finish_h_i_d ();
7292 free_global_sched_pressure_data ();
7295 if (targetm
.sched
.finish_global
)
7296 targetm
.sched
.finish_global (sched_dump
, sched_verbose
);
7298 end_alias_analysis ();
7300 regstat_free_calls_crossed ();
7305 /* Free all delay_pair structures that were recorded. */
7307 free_delay_pairs (void)
7309 if (delay_htab
.is_created ())
7311 delay_htab
.empty ();
7312 delay_htab_i2
.empty ();
7316 /* Fix INSN_TICKs of the instructions in the current block as well as
7317 INSN_TICKs of their dependents.
7318 HEAD and TAIL are the begin and the end of the current scheduled block. */
7320 fix_inter_tick (rtx head
, rtx tail
)
7322 /* Set of instructions with corrected INSN_TICK. */
7323 bitmap_head processed
;
7324 /* ??? It is doubtful if we should assume that cycle advance happens on
7325 basic block boundaries. Basically insns that are unconditionally ready
7326 on the start of the block are more preferable then those which have
7327 a one cycle dependency over insn from the previous block. */
7328 int next_clock
= clock_var
+ 1;
7330 bitmap_initialize (&processed
, 0);
7332 /* Iterates over scheduled instructions and fix their INSN_TICKs and
7333 INSN_TICKs of dependent instructions, so that INSN_TICKs are consistent
7334 across different blocks. */
7335 for (tail
= NEXT_INSN (tail
); head
!= tail
; head
= NEXT_INSN (head
))
7340 sd_iterator_def sd_it
;
7343 tick
= INSN_TICK (head
);
7344 gcc_assert (tick
>= MIN_TICK
);
7346 /* Fix INSN_TICK of instruction from just scheduled block. */
7347 if (bitmap_set_bit (&processed
, INSN_LUID (head
)))
7351 if (tick
< MIN_TICK
)
7354 INSN_TICK (head
) = tick
;
7357 if (DEBUG_INSN_P (head
))
7360 FOR_EACH_DEP (head
, SD_LIST_RES_FORW
, sd_it
, dep
)
7364 next
= DEP_CON (dep
);
7365 tick
= INSN_TICK (next
);
7367 if (tick
!= INVALID_TICK
7368 /* If NEXT has its INSN_TICK calculated, fix it.
7369 If not - it will be properly calculated from
7370 scratch later in fix_tick_ready. */
7371 && bitmap_set_bit (&processed
, INSN_LUID (next
)))
7375 if (tick
< MIN_TICK
)
7378 if (tick
> INTER_TICK (next
))
7379 INTER_TICK (next
) = tick
;
7381 tick
= INTER_TICK (next
);
7383 INSN_TICK (next
) = tick
;
7388 bitmap_clear (&processed
);
7391 /* Check if NEXT is ready to be added to the ready or queue list.
7392 If "yes", add it to the proper list.
7394 -1 - is not ready yet,
7395 0 - added to the ready list,
7396 0 < N - queued for N cycles. */
7398 try_ready (rtx next
)
7400 ds_t old_ts
, new_ts
;
7402 old_ts
= TODO_SPEC (next
);
7404 gcc_assert (!(old_ts
& ~(SPECULATIVE
| HARD_DEP
| DEP_CONTROL
| DEP_POSTPONED
))
7405 && (old_ts
== HARD_DEP
7406 || old_ts
== DEP_POSTPONED
7407 || (old_ts
& SPECULATIVE
)
7408 || old_ts
== DEP_CONTROL
));
7410 new_ts
= recompute_todo_spec (next
, false);
7412 if (new_ts
& (HARD_DEP
| DEP_POSTPONED
))
7413 gcc_assert (new_ts
== old_ts
7414 && QUEUE_INDEX (next
) == QUEUE_NOWHERE
);
7415 else if (current_sched_info
->new_ready
)
7416 new_ts
= current_sched_info
->new_ready (next
, new_ts
);
7418 /* * if !(old_ts & SPECULATIVE) (e.g. HARD_DEP or 0), then insn might
7419 have its original pattern or changed (speculative) one. This is due
7420 to changing ebb in region scheduling.
7421 * But if (old_ts & SPECULATIVE), then we are pretty sure that insn
7422 has speculative pattern.
7424 We can't assert (!(new_ts & HARD_DEP) || new_ts == old_ts) here because
7425 control-speculative NEXT could have been discarded by sched-rgn.c
7426 (the same case as when discarded by can_schedule_ready_p ()). */
7428 if ((new_ts
& SPECULATIVE
)
7429 /* If (old_ts == new_ts), then (old_ts & SPECULATIVE) and we don't
7430 need to change anything. */
7431 && new_ts
!= old_ts
)
7436 gcc_assert ((new_ts
& SPECULATIVE
) && !(new_ts
& ~SPECULATIVE
));
7438 res
= haifa_speculate_insn (next
, new_ts
, &new_pat
);
7443 /* It would be nice to change DEP_STATUS of all dependences,
7444 which have ((DEP_STATUS & SPECULATIVE) == new_ts) to HARD_DEP,
7445 so we won't reanalyze anything. */
7450 /* We follow the rule, that every speculative insn
7451 has non-null ORIG_PAT. */
7452 if (!ORIG_PAT (next
))
7453 ORIG_PAT (next
) = PATTERN (next
);
7457 if (!ORIG_PAT (next
))
7458 /* If we gonna to overwrite the original pattern of insn,
7460 ORIG_PAT (next
) = PATTERN (next
);
7462 res
= haifa_change_pattern (next
, new_pat
);
7471 /* We need to restore pattern only if (new_ts == 0), because otherwise it is
7472 either correct (new_ts & SPECULATIVE),
7473 or we simply don't care (new_ts & HARD_DEP). */
7475 gcc_assert (!ORIG_PAT (next
)
7476 || !IS_SPECULATION_BRANCHY_CHECK_P (next
));
7478 TODO_SPEC (next
) = new_ts
;
7480 if (new_ts
& (HARD_DEP
| DEP_POSTPONED
))
7482 /* We can't assert (QUEUE_INDEX (next) == QUEUE_NOWHERE) here because
7483 control-speculative NEXT could have been discarded by sched-rgn.c
7484 (the same case as when discarded by can_schedule_ready_p ()). */
7485 /*gcc_assert (QUEUE_INDEX (next) == QUEUE_NOWHERE);*/
7487 change_queue_index (next
, QUEUE_NOWHERE
);
7491 else if (!(new_ts
& BEGIN_SPEC
)
7492 && ORIG_PAT (next
) && PREDICATED_PAT (next
) == NULL_RTX
7493 && !IS_SPECULATION_CHECK_P (next
))
7494 /* We should change pattern of every previously speculative
7495 instruction - and we determine if NEXT was speculative by using
7496 ORIG_PAT field. Except one case - speculation checks have ORIG_PAT
7497 pat too, so skip them. */
7499 bool success
= haifa_change_pattern (next
, ORIG_PAT (next
));
7500 gcc_assert (success
);
7501 ORIG_PAT (next
) = 0;
7504 if (sched_verbose
>= 2)
7506 fprintf (sched_dump
, ";;\t\tdependencies resolved: insn %s",
7507 (*current_sched_info
->print_insn
) (next
, 0));
7509 if (spec_info
&& spec_info
->dump
)
7511 if (new_ts
& BEGIN_DATA
)
7512 fprintf (spec_info
->dump
, "; data-spec;");
7513 if (new_ts
& BEGIN_CONTROL
)
7514 fprintf (spec_info
->dump
, "; control-spec;");
7515 if (new_ts
& BE_IN_CONTROL
)
7516 fprintf (spec_info
->dump
, "; in-control-spec;");
7518 if (TODO_SPEC (next
) & DEP_CONTROL
)
7519 fprintf (sched_dump
, " predicated");
7520 fprintf (sched_dump
, "\n");
7523 adjust_priority (next
);
7525 return fix_tick_ready (next
);
7528 /* Calculate INSN_TICK of NEXT and add it to either ready or queue list. */
7530 fix_tick_ready (rtx next
)
7534 if (!DEBUG_INSN_P (next
) && !sd_lists_empty_p (next
, SD_LIST_RES_BACK
))
7537 sd_iterator_def sd_it
;
7540 tick
= INSN_TICK (next
);
7541 /* if tick is not equal to INVALID_TICK, then update
7542 INSN_TICK of NEXT with the most recent resolved dependence
7543 cost. Otherwise, recalculate from scratch. */
7544 full_p
= (tick
== INVALID_TICK
);
7546 FOR_EACH_DEP (next
, SD_LIST_RES_BACK
, sd_it
, dep
)
7548 rtx pro
= DEP_PRO (dep
);
7551 gcc_assert (INSN_TICK (pro
) >= MIN_TICK
);
7553 tick1
= INSN_TICK (pro
) + dep_cost (dep
);
7564 INSN_TICK (next
) = tick
;
7566 delay
= tick
- clock_var
;
7567 if (delay
<= 0 || sched_pressure
!= SCHED_PRESSURE_NONE
)
7568 delay
= QUEUE_READY
;
7570 change_queue_index (next
, delay
);
7575 /* Move NEXT to the proper queue list with (DELAY >= 1),
7576 or add it to the ready list (DELAY == QUEUE_READY),
7577 or remove it from ready and queue lists at all (DELAY == QUEUE_NOWHERE). */
7579 change_queue_index (rtx next
, int delay
)
7581 int i
= QUEUE_INDEX (next
);
7583 gcc_assert (QUEUE_NOWHERE
<= delay
&& delay
<= max_insn_queue_index
7585 gcc_assert (i
!= QUEUE_SCHEDULED
);
7587 if ((delay
> 0 && NEXT_Q_AFTER (q_ptr
, delay
) == i
)
7588 || (delay
< 0 && delay
== i
))
7589 /* We have nothing to do. */
7592 /* Remove NEXT from wherever it is now. */
7593 if (i
== QUEUE_READY
)
7594 ready_remove_insn (next
);
7596 queue_remove (next
);
7598 /* Add it to the proper place. */
7599 if (delay
== QUEUE_READY
)
7600 ready_add (readyp
, next
, false);
7601 else if (delay
>= 1)
7602 queue_insn (next
, delay
, "change queue index");
7604 if (sched_verbose
>= 2)
7606 fprintf (sched_dump
, ";;\t\ttick updated: insn %s",
7607 (*current_sched_info
->print_insn
) (next
, 0));
7609 if (delay
== QUEUE_READY
)
7610 fprintf (sched_dump
, " into ready\n");
7611 else if (delay
>= 1)
7612 fprintf (sched_dump
, " into queue with cost=%d\n", delay
);
7614 fprintf (sched_dump
, " removed from ready or queue lists\n");
7618 static int sched_ready_n_insns
= -1;
7620 /* Initialize per region data structures. */
7622 sched_extend_ready_list (int new_sched_ready_n_insns
)
7626 if (sched_ready_n_insns
== -1)
7627 /* At the first call we need to initialize one more choice_stack
7631 sched_ready_n_insns
= 0;
7632 scheduled_insns
.reserve (new_sched_ready_n_insns
);
7635 i
= sched_ready_n_insns
+ 1;
7637 ready
.veclen
= new_sched_ready_n_insns
+ issue_rate
;
7638 ready
.vec
= XRESIZEVEC (rtx
, ready
.vec
, ready
.veclen
);
7640 gcc_assert (new_sched_ready_n_insns
>= sched_ready_n_insns
);
7642 ready_try
= (signed char *) xrecalloc (ready_try
, new_sched_ready_n_insns
,
7643 sched_ready_n_insns
,
7644 sizeof (*ready_try
));
7646 /* We allocate +1 element to save initial state in the choice_stack[0]
7648 choice_stack
= XRESIZEVEC (struct choice_entry
, choice_stack
,
7649 new_sched_ready_n_insns
+ 1);
7651 for (; i
<= new_sched_ready_n_insns
; i
++)
7653 choice_stack
[i
].state
= xmalloc (dfa_state_size
);
7655 if (targetm
.sched
.first_cycle_multipass_init
)
7656 targetm
.sched
.first_cycle_multipass_init (&(choice_stack
[i
]
7660 sched_ready_n_insns
= new_sched_ready_n_insns
;
7663 /* Free per region data structures. */
7665 sched_finish_ready_list (void)
7676 for (i
= 0; i
<= sched_ready_n_insns
; i
++)
7678 if (targetm
.sched
.first_cycle_multipass_fini
)
7679 targetm
.sched
.first_cycle_multipass_fini (&(choice_stack
[i
]
7682 free (choice_stack
[i
].state
);
7684 free (choice_stack
);
7685 choice_stack
= NULL
;
7687 sched_ready_n_insns
= -1;
7691 haifa_luid_for_non_insn (rtx x
)
7693 gcc_assert (NOTE_P (x
) || LABEL_P (x
));
7698 /* Generates recovery code for INSN. */
7700 generate_recovery_code (rtx insn
)
7702 if (TODO_SPEC (insn
) & BEGIN_SPEC
)
7703 begin_speculative_block (insn
);
7705 /* Here we have insn with no dependencies to
7706 instructions other then CHECK_SPEC ones. */
7708 if (TODO_SPEC (insn
) & BE_IN_SPEC
)
7709 add_to_speculative_block (insn
);
7713 Tries to add speculative dependencies of type FS between instructions
7714 in deps_list L and TWIN. */
7716 process_insn_forw_deps_be_in_spec (rtx insn
, rtx twin
, ds_t fs
)
7718 sd_iterator_def sd_it
;
7721 FOR_EACH_DEP (insn
, SD_LIST_FORW
, sd_it
, dep
)
7726 consumer
= DEP_CON (dep
);
7728 ds
= DEP_STATUS (dep
);
7730 if (/* If we want to create speculative dep. */
7732 /* And we can do that because this is a true dep. */
7733 && (ds
& DEP_TYPES
) == DEP_TRUE
)
7735 gcc_assert (!(ds
& BE_IN_SPEC
));
7737 if (/* If this dep can be overcome with 'begin speculation'. */
7739 /* Then we have a choice: keep the dep 'begin speculative'
7740 or transform it into 'be in speculative'. */
7742 if (/* In try_ready we assert that if insn once became ready
7743 it can be removed from the ready (or queue) list only
7744 due to backend decision. Hence we can't let the
7745 probability of the speculative dep to decrease. */
7746 ds_weak (ds
) <= ds_weak (fs
))
7750 new_ds
= (ds
& ~BEGIN_SPEC
) | fs
;
7752 if (/* consumer can 'be in speculative'. */
7753 sched_insn_is_legitimate_for_speculation_p (consumer
,
7755 /* Transform it to be in speculative. */
7760 /* Mark the dep as 'be in speculative'. */
7765 dep_def _new_dep
, *new_dep
= &_new_dep
;
7767 init_dep_1 (new_dep
, twin
, consumer
, DEP_TYPE (dep
), ds
);
7768 sd_add_dep (new_dep
, false);
7773 /* Generates recovery code for BEGIN speculative INSN. */
7775 begin_speculative_block (rtx insn
)
7777 if (TODO_SPEC (insn
) & BEGIN_DATA
)
7779 if (TODO_SPEC (insn
) & BEGIN_CONTROL
)
7782 create_check_block_twin (insn
, false);
7784 TODO_SPEC (insn
) &= ~BEGIN_SPEC
;
7787 static void haifa_init_insn (rtx
);
7789 /* Generates recovery code for BE_IN speculative INSN. */
7791 add_to_speculative_block (rtx insn
)
7794 sd_iterator_def sd_it
;
7797 rtx_vec_t priorities_roots
;
7799 ts
= TODO_SPEC (insn
);
7800 gcc_assert (!(ts
& ~BE_IN_SPEC
));
7802 if (ts
& BE_IN_DATA
)
7804 if (ts
& BE_IN_CONTROL
)
7807 TODO_SPEC (insn
) &= ~BE_IN_SPEC
;
7808 gcc_assert (!TODO_SPEC (insn
));
7810 DONE_SPEC (insn
) |= ts
;
7812 /* First we convert all simple checks to branchy. */
7813 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
7814 sd_iterator_cond (&sd_it
, &dep
);)
7816 rtx check
= DEP_PRO (dep
);
7818 if (IS_SPECULATION_SIMPLE_CHECK_P (check
))
7820 create_check_block_twin (check
, true);
7822 /* Restart search. */
7823 sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
7826 /* Continue search. */
7827 sd_iterator_next (&sd_it
);
7830 priorities_roots
.create (0);
7831 clear_priorities (insn
, &priorities_roots
);
7838 /* Get the first backward dependency of INSN. */
7839 sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
7840 if (!sd_iterator_cond (&sd_it
, &dep
))
7841 /* INSN has no backward dependencies left. */
7844 gcc_assert ((DEP_STATUS (dep
) & BEGIN_SPEC
) == 0
7845 && (DEP_STATUS (dep
) & BE_IN_SPEC
) != 0
7846 && (DEP_STATUS (dep
) & DEP_TYPES
) == DEP_TRUE
);
7848 check
= DEP_PRO (dep
);
7850 gcc_assert (!IS_SPECULATION_CHECK_P (check
) && !ORIG_PAT (check
)
7851 && QUEUE_INDEX (check
) == QUEUE_NOWHERE
);
7853 rec
= BLOCK_FOR_INSN (check
);
7855 twin
= emit_insn_before (copy_insn (PATTERN (insn
)), BB_END (rec
));
7856 haifa_init_insn (twin
);
7858 sd_copy_back_deps (twin
, insn
, true);
7860 if (sched_verbose
&& spec_info
->dump
)
7861 /* INSN_BB (insn) isn't determined for twin insns yet.
7862 So we can't use current_sched_info->print_insn. */
7863 fprintf (spec_info
->dump
, ";;\t\tGenerated twin insn : %d/rec%d\n",
7864 INSN_UID (twin
), rec
->index
);
7866 twins
= alloc_INSN_LIST (twin
, twins
);
7868 /* Add dependences between TWIN and all appropriate
7869 instructions from REC. */
7870 FOR_EACH_DEP (insn
, SD_LIST_SPEC_BACK
, sd_it
, dep
)
7872 rtx pro
= DEP_PRO (dep
);
7874 gcc_assert (DEP_TYPE (dep
) == REG_DEP_TRUE
);
7876 /* INSN might have dependencies from the instructions from
7877 several recovery blocks. At this iteration we process those
7878 producers that reside in REC. */
7879 if (BLOCK_FOR_INSN (pro
) == rec
)
7881 dep_def _new_dep
, *new_dep
= &_new_dep
;
7883 init_dep (new_dep
, pro
, twin
, REG_DEP_TRUE
);
7884 sd_add_dep (new_dep
, false);
7888 process_insn_forw_deps_be_in_spec (insn
, twin
, ts
);
7890 /* Remove all dependencies between INSN and insns in REC. */
7891 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
7892 sd_iterator_cond (&sd_it
, &dep
);)
7894 rtx pro
= DEP_PRO (dep
);
7896 if (BLOCK_FOR_INSN (pro
) == rec
)
7897 sd_delete_dep (sd_it
);
7899 sd_iterator_next (&sd_it
);
7903 /* We couldn't have added the dependencies between INSN and TWINS earlier
7904 because that would make TWINS appear in the INSN_BACK_DEPS (INSN). */
7909 twin
= XEXP (twins
, 0);
7912 dep_def _new_dep
, *new_dep
= &_new_dep
;
7914 init_dep (new_dep
, insn
, twin
, REG_DEP_OUTPUT
);
7915 sd_add_dep (new_dep
, false);
7918 twin
= XEXP (twins
, 1);
7919 free_INSN_LIST_node (twins
);
7923 calc_priorities (priorities_roots
);
7924 priorities_roots
.release ();
7927 /* Extends and fills with zeros (only the new part) array pointed to by P. */
7929 xrecalloc (void *p
, size_t new_nmemb
, size_t old_nmemb
, size_t size
)
7931 gcc_assert (new_nmemb
>= old_nmemb
);
7932 p
= XRESIZEVAR (void, p
, new_nmemb
* size
);
7933 memset (((char *) p
) + old_nmemb
* size
, 0, (new_nmemb
- old_nmemb
) * size
);
7938 Find fallthru edge from PRED. */
7940 find_fallthru_edge_from (basic_block pred
)
7945 succ
= pred
->next_bb
;
7946 gcc_assert (succ
->prev_bb
== pred
);
7948 if (EDGE_COUNT (pred
->succs
) <= EDGE_COUNT (succ
->preds
))
7950 e
= find_fallthru_edge (pred
->succs
);
7954 gcc_assert (e
->dest
== succ
);
7960 e
= find_fallthru_edge (succ
->preds
);
7964 gcc_assert (e
->src
== pred
);
7972 /* Extend per basic block data structures. */
7974 sched_extend_bb (void)
7976 /* The following is done to keep current_sched_info->next_tail non null. */
7977 rtx end
= BB_END (EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
);
7978 rtx insn
= DEBUG_INSN_P (end
) ? prev_nondebug_insn (end
) : end
;
7979 if (NEXT_INSN (end
) == 0
7982 /* Don't emit a NOTE if it would end up before a BARRIER. */
7983 && !BARRIER_P (NEXT_INSN (end
))))
7985 rtx note
= emit_note_after (NOTE_INSN_DELETED
, end
);
7986 /* Make note appear outside BB. */
7987 set_block_for_insn (note
, NULL
);
7988 BB_END (EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
) = end
;
7992 /* Init per basic block data structures. */
7994 sched_init_bbs (void)
7999 /* Initialize BEFORE_RECOVERY variable. */
8001 init_before_recovery (basic_block
*before_recovery_ptr
)
8006 last
= EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
;
8007 e
= find_fallthru_edge_from (last
);
8011 /* We create two basic blocks:
8012 1. Single instruction block is inserted right after E->SRC
8014 2. Empty block right before EXIT_BLOCK.
8015 Between these two blocks recovery blocks will be emitted. */
8017 basic_block single
, empty
;
8020 /* If the fallthrough edge to exit we've found is from the block we've
8021 created before, don't do anything more. */
8022 if (last
== after_recovery
)
8025 adding_bb_to_current_region_p
= false;
8027 single
= sched_create_empty_bb (last
);
8028 empty
= sched_create_empty_bb (single
);
8030 /* Add new blocks to the root loop. */
8031 if (current_loops
!= NULL
)
8033 add_bb_to_loop (single
, (*current_loops
->larray
)[0]);
8034 add_bb_to_loop (empty
, (*current_loops
->larray
)[0]);
8037 single
->count
= last
->count
;
8038 empty
->count
= last
->count
;
8039 single
->frequency
= last
->frequency
;
8040 empty
->frequency
= last
->frequency
;
8041 BB_COPY_PARTITION (single
, last
);
8042 BB_COPY_PARTITION (empty
, last
);
8044 redirect_edge_succ (e
, single
);
8045 make_single_succ_edge (single
, empty
, 0);
8046 make_single_succ_edge (empty
, EXIT_BLOCK_PTR_FOR_FN (cfun
),
8049 label
= block_label (empty
);
8050 x
= emit_jump_insn_after (gen_jump (label
), BB_END (single
));
8051 JUMP_LABEL (x
) = label
;
8052 LABEL_NUSES (label
)++;
8053 haifa_init_insn (x
);
8055 emit_barrier_after (x
);
8057 sched_init_only_bb (empty
, NULL
);
8058 sched_init_only_bb (single
, NULL
);
8061 adding_bb_to_current_region_p
= true;
8062 before_recovery
= single
;
8063 after_recovery
= empty
;
8065 if (before_recovery_ptr
)
8066 *before_recovery_ptr
= before_recovery
;
8068 if (sched_verbose
>= 2 && spec_info
->dump
)
8069 fprintf (spec_info
->dump
,
8070 ";;\t\tFixed fallthru to EXIT : %d->>%d->%d->>EXIT\n",
8071 last
->index
, single
->index
, empty
->index
);
8074 before_recovery
= last
;
8077 /* Returns new recovery block. */
8079 sched_create_recovery_block (basic_block
*before_recovery_ptr
)
8085 haifa_recovery_bb_recently_added_p
= true;
8086 haifa_recovery_bb_ever_added_p
= true;
8088 init_before_recovery (before_recovery_ptr
);
8090 barrier
= get_last_bb_insn (before_recovery
);
8091 gcc_assert (BARRIER_P (barrier
));
8093 label
= emit_label_after (gen_label_rtx (), barrier
);
8095 rec
= create_basic_block (label
, label
, before_recovery
);
8097 /* A recovery block always ends with an unconditional jump. */
8098 emit_barrier_after (BB_END (rec
));
8100 if (BB_PARTITION (before_recovery
) != BB_UNPARTITIONED
)
8101 BB_SET_PARTITION (rec
, BB_COLD_PARTITION
);
8103 if (sched_verbose
&& spec_info
->dump
)
8104 fprintf (spec_info
->dump
, ";;\t\tGenerated recovery block rec%d\n",
8110 /* Create edges: FIRST_BB -> REC; FIRST_BB -> SECOND_BB; REC -> SECOND_BB
8111 and emit necessary jumps. */
8113 sched_create_recovery_edges (basic_block first_bb
, basic_block rec
,
8114 basic_block second_bb
)
8120 /* This is fixing of incoming edge. */
8121 /* ??? Which other flags should be specified? */
8122 if (BB_PARTITION (first_bb
) != BB_PARTITION (rec
))
8123 /* Partition type is the same, if it is "unpartitioned". */
8124 edge_flags
= EDGE_CROSSING
;
8128 make_edge (first_bb
, rec
, edge_flags
);
8129 label
= block_label (second_bb
);
8130 jump
= emit_jump_insn_after (gen_jump (label
), BB_END (rec
));
8131 JUMP_LABEL (jump
) = label
;
8132 LABEL_NUSES (label
)++;
8134 if (BB_PARTITION (second_bb
) != BB_PARTITION (rec
))
8135 /* Partition type is the same, if it is "unpartitioned". */
8137 /* Rewritten from cfgrtl.c. */
8138 if (flag_reorder_blocks_and_partition
8139 && targetm_common
.have_named_sections
)
8141 /* We don't need the same note for the check because
8142 any_condjump_p (check) == true. */
8143 add_reg_note (jump
, REG_CROSSING_JUMP
, NULL_RTX
);
8145 edge_flags
= EDGE_CROSSING
;
8150 make_single_succ_edge (rec
, second_bb
, edge_flags
);
8151 if (dom_info_available_p (CDI_DOMINATORS
))
8152 set_immediate_dominator (CDI_DOMINATORS
, rec
, first_bb
);
8155 /* This function creates recovery code for INSN. If MUTATE_P is nonzero,
8156 INSN is a simple check, that should be converted to branchy one. */
8158 create_check_block_twin (rtx insn
, bool mutate_p
)
8161 rtx label
, check
, twin
;
8163 sd_iterator_def sd_it
;
8165 dep_def _new_dep
, *new_dep
= &_new_dep
;
8168 gcc_assert (ORIG_PAT (insn
) != NULL_RTX
);
8171 todo_spec
= TODO_SPEC (insn
);
8174 gcc_assert (IS_SPECULATION_SIMPLE_CHECK_P (insn
)
8175 && (TODO_SPEC (insn
) & SPECULATIVE
) == 0);
8177 todo_spec
= CHECK_SPEC (insn
);
8180 todo_spec
&= SPECULATIVE
;
8182 /* Create recovery block. */
8183 if (mutate_p
|| targetm
.sched
.needs_block_p (todo_spec
))
8185 rec
= sched_create_recovery_block (NULL
);
8186 label
= BB_HEAD (rec
);
8190 rec
= EXIT_BLOCK_PTR_FOR_FN (cfun
);
8195 check
= targetm
.sched
.gen_spec_check (insn
, label
, todo_spec
);
8197 if (rec
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
8199 /* To have mem_reg alive at the beginning of second_bb,
8200 we emit check BEFORE insn, so insn after splitting
8201 insn will be at the beginning of second_bb, which will
8202 provide us with the correct life information. */
8203 check
= emit_jump_insn_before (check
, insn
);
8204 JUMP_LABEL (check
) = label
;
8205 LABEL_NUSES (label
)++;
8208 check
= emit_insn_before (check
, insn
);
8210 /* Extend data structures. */
8211 haifa_init_insn (check
);
8213 /* CHECK is being added to current region. Extend ready list. */
8214 gcc_assert (sched_ready_n_insns
!= -1);
8215 sched_extend_ready_list (sched_ready_n_insns
+ 1);
8217 if (current_sched_info
->add_remove_insn
)
8218 current_sched_info
->add_remove_insn (insn
, 0);
8220 RECOVERY_BLOCK (check
) = rec
;
8222 if (sched_verbose
&& spec_info
->dump
)
8223 fprintf (spec_info
->dump
, ";;\t\tGenerated check insn : %s\n",
8224 (*current_sched_info
->print_insn
) (check
, 0));
8226 gcc_assert (ORIG_PAT (insn
));
8228 /* Initialize TWIN (twin is a duplicate of original instruction
8229 in the recovery block). */
8230 if (rec
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
8232 sd_iterator_def sd_it
;
8235 FOR_EACH_DEP (insn
, SD_LIST_RES_BACK
, sd_it
, dep
)
8236 if ((DEP_STATUS (dep
) & DEP_OUTPUT
) != 0)
8238 struct _dep _dep2
, *dep2
= &_dep2
;
8240 init_dep (dep2
, DEP_PRO (dep
), check
, REG_DEP_TRUE
);
8242 sd_add_dep (dep2
, true);
8245 twin
= emit_insn_after (ORIG_PAT (insn
), BB_END (rec
));
8246 haifa_init_insn (twin
);
8248 if (sched_verbose
&& spec_info
->dump
)
8249 /* INSN_BB (insn) isn't determined for twin insns yet.
8250 So we can't use current_sched_info->print_insn. */
8251 fprintf (spec_info
->dump
, ";;\t\tGenerated twin insn : %d/rec%d\n",
8252 INSN_UID (twin
), rec
->index
);
8256 ORIG_PAT (check
) = ORIG_PAT (insn
);
8257 HAS_INTERNAL_DEP (check
) = 1;
8259 /* ??? We probably should change all OUTPUT dependencies to
8263 /* Copy all resolved back dependencies of INSN to TWIN. This will
8264 provide correct value for INSN_TICK (TWIN). */
8265 sd_copy_back_deps (twin
, insn
, true);
8267 if (rec
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
8268 /* In case of branchy check, fix CFG. */
8270 basic_block first_bb
, second_bb
;
8273 first_bb
= BLOCK_FOR_INSN (check
);
8274 second_bb
= sched_split_block (first_bb
, check
);
8276 sched_create_recovery_edges (first_bb
, rec
, second_bb
);
8278 sched_init_only_bb (second_bb
, first_bb
);
8279 sched_init_only_bb (rec
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
8281 jump
= BB_END (rec
);
8282 haifa_init_insn (jump
);
8285 /* Move backward dependences from INSN to CHECK and
8286 move forward dependences from INSN to TWIN. */
8288 /* First, create dependencies between INSN's producers and CHECK & TWIN. */
8289 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
8291 rtx pro
= DEP_PRO (dep
);
8294 /* If BEGIN_DATA: [insn ~~TRUE~~> producer]:
8295 check --TRUE--> producer ??? or ANTI ???
8296 twin --TRUE--> producer
8297 twin --ANTI--> check
8299 If BEGIN_CONTROL: [insn ~~ANTI~~> producer]:
8300 check --ANTI--> producer
8301 twin --ANTI--> producer
8302 twin --ANTI--> check
8304 If BE_IN_SPEC: [insn ~~TRUE~~> producer]:
8305 check ~~TRUE~~> producer
8306 twin ~~TRUE~~> producer
8307 twin --ANTI--> check */
8309 ds
= DEP_STATUS (dep
);
8311 if (ds
& BEGIN_SPEC
)
8313 gcc_assert (!mutate_p
);
8317 init_dep_1 (new_dep
, pro
, check
, DEP_TYPE (dep
), ds
);
8318 sd_add_dep (new_dep
, false);
8320 if (rec
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
8322 DEP_CON (new_dep
) = twin
;
8323 sd_add_dep (new_dep
, false);
8327 /* Second, remove backward dependencies of INSN. */
8328 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
8329 sd_iterator_cond (&sd_it
, &dep
);)
8331 if ((DEP_STATUS (dep
) & BEGIN_SPEC
)
8333 /* We can delete this dep because we overcome it with
8334 BEGIN_SPECULATION. */
8335 sd_delete_dep (sd_it
);
8337 sd_iterator_next (&sd_it
);
8340 /* Future Speculations. Determine what BE_IN speculations will be like. */
8343 /* Fields (DONE_SPEC (x) & BEGIN_SPEC) and CHECK_SPEC (x) are set only
8346 gcc_assert (!DONE_SPEC (insn
));
8350 ds_t ts
= TODO_SPEC (insn
);
8352 DONE_SPEC (insn
) = ts
& BEGIN_SPEC
;
8353 CHECK_SPEC (check
) = ts
& BEGIN_SPEC
;
8355 /* Luckiness of future speculations solely depends upon initial
8356 BEGIN speculation. */
8357 if (ts
& BEGIN_DATA
)
8358 fs
= set_dep_weak (fs
, BE_IN_DATA
, get_dep_weak (ts
, BEGIN_DATA
));
8359 if (ts
& BEGIN_CONTROL
)
8360 fs
= set_dep_weak (fs
, BE_IN_CONTROL
,
8361 get_dep_weak (ts
, BEGIN_CONTROL
));
8364 CHECK_SPEC (check
) = CHECK_SPEC (insn
);
8366 /* Future speculations: call the helper. */
8367 process_insn_forw_deps_be_in_spec (insn
, twin
, fs
);
8369 if (rec
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
8371 /* Which types of dependencies should we use here is,
8372 generally, machine-dependent question... But, for now,
8377 init_dep (new_dep
, insn
, check
, REG_DEP_TRUE
);
8378 sd_add_dep (new_dep
, false);
8380 init_dep (new_dep
, insn
, twin
, REG_DEP_OUTPUT
);
8381 sd_add_dep (new_dep
, false);
8385 if (spec_info
->dump
)
8386 fprintf (spec_info
->dump
, ";;\t\tRemoved simple check : %s\n",
8387 (*current_sched_info
->print_insn
) (insn
, 0));
8389 /* Remove all dependencies of the INSN. */
8391 sd_it
= sd_iterator_start (insn
, (SD_LIST_FORW
8393 | SD_LIST_RES_BACK
));
8394 while (sd_iterator_cond (&sd_it
, &dep
))
8395 sd_delete_dep (sd_it
);
8398 /* If former check (INSN) already was moved to the ready (or queue)
8399 list, add new check (CHECK) there too. */
8400 if (QUEUE_INDEX (insn
) != QUEUE_NOWHERE
)
8403 /* Remove old check from instruction stream and free its
8405 sched_remove_insn (insn
);
8408 init_dep (new_dep
, check
, twin
, REG_DEP_ANTI
);
8409 sd_add_dep (new_dep
, false);
8413 init_dep_1 (new_dep
, insn
, check
, REG_DEP_TRUE
, DEP_TRUE
| DEP_OUTPUT
);
8414 sd_add_dep (new_dep
, false);
8418 /* Fix priorities. If MUTATE_P is nonzero, this is not necessary,
8419 because it'll be done later in add_to_speculative_block. */
8421 rtx_vec_t priorities_roots
= rtx_vec_t ();
8423 clear_priorities (twin
, &priorities_roots
);
8424 calc_priorities (priorities_roots
);
8425 priorities_roots
.release ();
8429 /* Removes dependency between instructions in the recovery block REC
8430 and usual region instructions. It keeps inner dependences so it
8431 won't be necessary to recompute them. */
8433 fix_recovery_deps (basic_block rec
)
8435 rtx note
, insn
, jump
, ready_list
= 0;
8436 bitmap_head in_ready
;
8439 bitmap_initialize (&in_ready
, 0);
8441 /* NOTE - a basic block note. */
8442 note
= NEXT_INSN (BB_HEAD (rec
));
8443 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
8444 insn
= BB_END (rec
);
8445 gcc_assert (JUMP_P (insn
));
8446 insn
= PREV_INSN (insn
);
8450 sd_iterator_def sd_it
;
8453 for (sd_it
= sd_iterator_start (insn
, SD_LIST_FORW
);
8454 sd_iterator_cond (&sd_it
, &dep
);)
8456 rtx consumer
= DEP_CON (dep
);
8458 if (BLOCK_FOR_INSN (consumer
) != rec
)
8460 sd_delete_dep (sd_it
);
8462 if (bitmap_set_bit (&in_ready
, INSN_LUID (consumer
)))
8463 ready_list
= alloc_INSN_LIST (consumer
, ready_list
);
8467 gcc_assert ((DEP_STATUS (dep
) & DEP_TYPES
) == DEP_TRUE
);
8469 sd_iterator_next (&sd_it
);
8473 insn
= PREV_INSN (insn
);
8475 while (insn
!= note
);
8477 bitmap_clear (&in_ready
);
8479 /* Try to add instructions to the ready or queue list. */
8480 for (link
= ready_list
; link
; link
= XEXP (link
, 1))
8481 try_ready (XEXP (link
, 0));
8482 free_INSN_LIST_list (&ready_list
);
8484 /* Fixing jump's dependences. */
8485 insn
= BB_HEAD (rec
);
8486 jump
= BB_END (rec
);
8488 gcc_assert (LABEL_P (insn
));
8489 insn
= NEXT_INSN (insn
);
8491 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
8492 add_jump_dependencies (insn
, jump
);
8495 /* Change pattern of INSN to NEW_PAT. Invalidate cached haifa
8496 instruction data. */
8498 haifa_change_pattern (rtx insn
, rtx new_pat
)
8502 t
= validate_change (insn
, &PATTERN (insn
), new_pat
, 0);
8506 update_insn_after_change (insn
);
8510 /* -1 - can't speculate,
8511 0 - for speculation with REQUEST mode it is OK to use
8512 current instruction pattern,
8513 1 - need to change pattern for *NEW_PAT to be speculative. */
8515 sched_speculate_insn (rtx insn
, ds_t request
, rtx
*new_pat
)
8517 gcc_assert (current_sched_info
->flags
& DO_SPECULATION
8518 && (request
& SPECULATIVE
)
8519 && sched_insn_is_legitimate_for_speculation_p (insn
, request
));
8521 if ((request
& spec_info
->mask
) != request
)
8524 if (request
& BE_IN_SPEC
8525 && !(request
& BEGIN_SPEC
))
8528 return targetm
.sched
.speculate_insn (insn
, request
, new_pat
);
8532 haifa_speculate_insn (rtx insn
, ds_t request
, rtx
*new_pat
)
8534 gcc_assert (sched_deps_info
->generate_spec_deps
8535 && !IS_SPECULATION_CHECK_P (insn
));
8537 if (HAS_INTERNAL_DEP (insn
)
8538 || SCHED_GROUP_P (insn
))
8541 return sched_speculate_insn (insn
, request
, new_pat
);
8544 /* Print some information about block BB, which starts with HEAD and
8545 ends with TAIL, before scheduling it.
8546 I is zero, if scheduler is about to start with the fresh ebb. */
8548 dump_new_block_header (int i
, basic_block bb
, rtx head
, rtx tail
)
8551 fprintf (sched_dump
,
8552 ";; ======================================================\n");
8554 fprintf (sched_dump
,
8555 ";; =====================ADVANCING TO=====================\n");
8556 fprintf (sched_dump
,
8557 ";; -- basic block %d from %d to %d -- %s reload\n",
8558 bb
->index
, INSN_UID (head
), INSN_UID (tail
),
8559 (reload_completed
? "after" : "before"));
8560 fprintf (sched_dump
,
8561 ";; ======================================================\n");
8562 fprintf (sched_dump
, "\n");
8565 /* Unlink basic block notes and labels and saves them, so they
8566 can be easily restored. We unlink basic block notes in EBB to
8567 provide back-compatibility with the previous code, as target backends
8568 assume, that there'll be only instructions between
8569 current_sched_info->{head and tail}. We restore these notes as soon
8571 FIRST (LAST) is the first (last) basic block in the ebb.
8572 NB: In usual case (FIRST == LAST) nothing is really done. */
8574 unlink_bb_notes (basic_block first
, basic_block last
)
8576 /* We DON'T unlink basic block notes of the first block in the ebb. */
8580 bb_header
= XNEWVEC (rtx
, last_basic_block_for_fn (cfun
));
8582 /* Make a sentinel. */
8583 if (last
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
8584 bb_header
[last
->next_bb
->index
] = 0;
8586 first
= first
->next_bb
;
8589 rtx prev
, label
, note
, next
;
8591 label
= BB_HEAD (last
);
8592 if (LABEL_P (label
))
8593 note
= NEXT_INSN (label
);
8596 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
8598 prev
= PREV_INSN (label
);
8599 next
= NEXT_INSN (note
);
8600 gcc_assert (prev
&& next
);
8602 NEXT_INSN (prev
) = next
;
8603 PREV_INSN (next
) = prev
;
8605 bb_header
[last
->index
] = label
;
8610 last
= last
->prev_bb
;
8615 /* Restore basic block notes.
8616 FIRST is the first basic block in the ebb. */
8618 restore_bb_notes (basic_block first
)
8623 /* We DON'T unlink basic block notes of the first block in the ebb. */
8624 first
= first
->next_bb
;
8625 /* Remember: FIRST is actually a second basic block in the ebb. */
8627 while (first
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
8628 && bb_header
[first
->index
])
8630 rtx prev
, label
, note
, next
;
8632 label
= bb_header
[first
->index
];
8633 prev
= PREV_INSN (label
);
8634 next
= NEXT_INSN (prev
);
8636 if (LABEL_P (label
))
8637 note
= NEXT_INSN (label
);
8640 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
8642 bb_header
[first
->index
] = 0;
8644 NEXT_INSN (prev
) = label
;
8645 NEXT_INSN (note
) = next
;
8646 PREV_INSN (next
) = note
;
8648 first
= first
->next_bb
;
8656 Fix CFG after both in- and inter-block movement of
8657 control_flow_insn_p JUMP. */
8659 fix_jump_move (rtx jump
)
8661 basic_block bb
, jump_bb
, jump_bb_next
;
8663 bb
= BLOCK_FOR_INSN (PREV_INSN (jump
));
8664 jump_bb
= BLOCK_FOR_INSN (jump
);
8665 jump_bb_next
= jump_bb
->next_bb
;
8667 gcc_assert (common_sched_info
->sched_pass_id
== SCHED_EBB_PASS
8668 || IS_SPECULATION_BRANCHY_CHECK_P (jump
));
8670 if (!NOTE_INSN_BASIC_BLOCK_P (BB_END (jump_bb_next
)))
8671 /* if jump_bb_next is not empty. */
8672 BB_END (jump_bb
) = BB_END (jump_bb_next
);
8674 if (BB_END (bb
) != PREV_INSN (jump
))
8675 /* Then there are instruction after jump that should be placed
8677 BB_END (jump_bb_next
) = BB_END (bb
);
8679 /* Otherwise jump_bb_next is empty. */
8680 BB_END (jump_bb_next
) = NEXT_INSN (BB_HEAD (jump_bb_next
));
8682 /* To make assertion in move_insn happy. */
8683 BB_END (bb
) = PREV_INSN (jump
);
8685 update_bb_for_insn (jump_bb_next
);
8688 /* Fix CFG after interblock movement of control_flow_insn_p JUMP. */
8690 move_block_after_check (rtx jump
)
8692 basic_block bb
, jump_bb
, jump_bb_next
;
8693 vec
<edge
, va_gc
> *t
;
8695 bb
= BLOCK_FOR_INSN (PREV_INSN (jump
));
8696 jump_bb
= BLOCK_FOR_INSN (jump
);
8697 jump_bb_next
= jump_bb
->next_bb
;
8699 update_bb_for_insn (jump_bb
);
8701 gcc_assert (IS_SPECULATION_CHECK_P (jump
)
8702 || IS_SPECULATION_CHECK_P (BB_END (jump_bb_next
)));
8704 unlink_block (jump_bb_next
);
8705 link_block (jump_bb_next
, bb
);
8709 move_succs (&(jump_bb
->succs
), bb
);
8710 move_succs (&(jump_bb_next
->succs
), jump_bb
);
8711 move_succs (&t
, jump_bb_next
);
8713 df_mark_solutions_dirty ();
8715 common_sched_info
->fix_recovery_cfg
8716 (bb
->index
, jump_bb
->index
, jump_bb_next
->index
);
8719 /* Helper function for move_block_after_check.
8720 This functions attaches edge vector pointed to by SUCCSP to
8723 move_succs (vec
<edge
, va_gc
> **succsp
, basic_block to
)
8728 gcc_assert (to
->succs
== 0);
8730 to
->succs
= *succsp
;
8732 FOR_EACH_EDGE (e
, ei
, to
->succs
)
8738 /* Remove INSN from the instruction stream.
8739 INSN should have any dependencies. */
8741 sched_remove_insn (rtx insn
)
8743 sd_finish_insn (insn
);
8745 change_queue_index (insn
, QUEUE_NOWHERE
);
8746 current_sched_info
->add_remove_insn (insn
, 1);
8750 /* Clear priorities of all instructions, that are forward dependent on INSN.
8751 Store in vector pointed to by ROOTS_PTR insns on which priority () should
8752 be invoked to initialize all cleared priorities. */
8754 clear_priorities (rtx insn
, rtx_vec_t
*roots_ptr
)
8756 sd_iterator_def sd_it
;
8758 bool insn_is_root_p
= true;
8760 gcc_assert (QUEUE_INDEX (insn
) != QUEUE_SCHEDULED
);
8762 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
8764 rtx pro
= DEP_PRO (dep
);
8766 if (INSN_PRIORITY_STATUS (pro
) >= 0
8767 && QUEUE_INDEX (insn
) != QUEUE_SCHEDULED
)
8769 /* If DEP doesn't contribute to priority then INSN itself should
8770 be added to priority roots. */
8771 if (contributes_to_priority_p (dep
))
8772 insn_is_root_p
= false;
8774 INSN_PRIORITY_STATUS (pro
) = -1;
8775 clear_priorities (pro
, roots_ptr
);
8780 roots_ptr
->safe_push (insn
);
8783 /* Recompute priorities of instructions, whose priorities might have been
8784 changed. ROOTS is a vector of instructions whose priority computation will
8785 trigger initialization of all cleared priorities. */
8787 calc_priorities (rtx_vec_t roots
)
8792 FOR_EACH_VEC_ELT (roots
, i
, insn
)
8797 /* Add dependences between JUMP and other instructions in the recovery
8798 block. INSN is the first insn the recovery block. */
8800 add_jump_dependencies (rtx insn
, rtx jump
)
8804 insn
= NEXT_INSN (insn
);
8808 if (dep_list_size (insn
, SD_LIST_FORW
) == 0)
8810 dep_def _new_dep
, *new_dep
= &_new_dep
;
8812 init_dep (new_dep
, insn
, jump
, REG_DEP_ANTI
);
8813 sd_add_dep (new_dep
, false);
8818 gcc_assert (!sd_lists_empty_p (jump
, SD_LIST_BACK
));
8821 /* Extend data structures for logical insn UID. */
8823 sched_extend_luids (void)
8825 int new_luids_max_uid
= get_max_uid () + 1;
8827 sched_luids
.safe_grow_cleared (new_luids_max_uid
);
8830 /* Initialize LUID for INSN. */
8832 sched_init_insn_luid (rtx insn
)
8834 int i
= INSN_P (insn
) ? 1 : common_sched_info
->luid_for_non_insn (insn
);
8839 luid
= sched_max_luid
;
8840 sched_max_luid
+= i
;
8845 SET_INSN_LUID (insn
, luid
);
8848 /* Initialize luids for BBS.
8849 The hook common_sched_info->luid_for_non_insn () is used to determine
8850 if notes, labels, etc. need luids. */
8852 sched_init_luids (bb_vec_t bbs
)
8857 sched_extend_luids ();
8858 FOR_EACH_VEC_ELT (bbs
, i
, bb
)
8862 FOR_BB_INSNS (bb
, insn
)
8863 sched_init_insn_luid (insn
);
8869 sched_finish_luids (void)
8871 sched_luids
.release ();
8875 /* Return logical uid of INSN. Helpful while debugging. */
8877 insn_luid (rtx insn
)
8879 return INSN_LUID (insn
);
8882 /* Extend per insn data in the target. */
8884 sched_extend_target (void)
8886 if (targetm
.sched
.h_i_d_extended
)
8887 targetm
.sched
.h_i_d_extended ();
8890 /* Extend global scheduler structures (those, that live across calls to
8891 schedule_block) to include information about just emitted INSN. */
8895 int reserve
= (get_max_uid () + 1 - h_i_d
.length ());
8897 && ! h_i_d
.space (reserve
))
8899 h_i_d
.safe_grow_cleared (3 * get_max_uid () / 2);
8900 sched_extend_target ();
8904 /* Initialize h_i_d entry of the INSN with default values.
8905 Values, that are not explicitly initialized here, hold zero. */
8907 init_h_i_d (rtx insn
)
8909 if (INSN_LUID (insn
) > 0)
8911 INSN_COST (insn
) = -1;
8912 QUEUE_INDEX (insn
) = QUEUE_NOWHERE
;
8913 INSN_TICK (insn
) = INVALID_TICK
;
8914 INSN_EXACT_TICK (insn
) = INVALID_TICK
;
8915 INTER_TICK (insn
) = INVALID_TICK
;
8916 TODO_SPEC (insn
) = HARD_DEP
;
8917 INSN_AUTOPREF_MULTIPASS_DATA (insn
)[0].status
8918 = AUTOPREF_MULTIPASS_DATA_UNINITIALIZED
;
8919 INSN_AUTOPREF_MULTIPASS_DATA (insn
)[1].status
8920 = AUTOPREF_MULTIPASS_DATA_UNINITIALIZED
;
8924 /* Initialize haifa_insn_data for BBS. */
8926 haifa_init_h_i_d (bb_vec_t bbs
)
8932 FOR_EACH_VEC_ELT (bbs
, i
, bb
)
8936 FOR_BB_INSNS (bb
, insn
)
8941 /* Finalize haifa_insn_data. */
8943 haifa_finish_h_i_d (void)
8946 haifa_insn_data_t data
;
8947 struct reg_use_data
*use
, *next
;
8949 FOR_EACH_VEC_ELT (h_i_d
, i
, data
)
8951 free (data
->max_reg_pressure
);
8952 free (data
->reg_pressure
);
8953 for (use
= data
->reg_use_list
; use
!= NULL
; use
= next
)
8955 next
= use
->next_insn_use
;
8962 /* Init data for the new insn INSN. */
8964 haifa_init_insn (rtx insn
)
8966 gcc_assert (insn
!= NULL
);
8968 sched_extend_luids ();
8969 sched_init_insn_luid (insn
);
8970 sched_extend_target ();
8971 sched_deps_init (false);
8975 if (adding_bb_to_current_region_p
)
8977 sd_init_insn (insn
);
8979 /* Extend dependency caches by one element. */
8980 extend_dependency_caches (1, false);
8982 if (sched_pressure
!= SCHED_PRESSURE_NONE
)
8983 init_insn_reg_pressure_info (insn
);
8986 /* Init data for the new basic block BB which comes after AFTER. */
8988 haifa_init_only_bb (basic_block bb
, basic_block after
)
8990 gcc_assert (bb
!= NULL
);
8994 if (common_sched_info
->add_block
)
8995 /* This changes only data structures of the front-end. */
8996 common_sched_info
->add_block (bb
, after
);
8999 /* A generic version of sched_split_block (). */
9001 sched_split_block_1 (basic_block first_bb
, rtx after
)
9005 e
= split_block (first_bb
, after
);
9006 gcc_assert (e
->src
== first_bb
);
9008 /* sched_split_block emits note if *check == BB_END. Probably it
9009 is better to rip that note off. */
9014 /* A generic version of sched_create_empty_bb (). */
9016 sched_create_empty_bb_1 (basic_block after
)
9018 return create_empty_bb (after
);
9021 /* Insert PAT as an INSN into the schedule and update the necessary data
9022 structures to account for it. */
9024 sched_emit_insn (rtx pat
)
9026 rtx insn
= emit_insn_before (pat
, first_nonscheduled_insn ());
9027 haifa_init_insn (insn
);
9029 if (current_sched_info
->add_remove_insn
)
9030 current_sched_info
->add_remove_insn (insn
, 0);
9032 (*current_sched_info
->begin_schedule_ready
) (insn
);
9033 scheduled_insns
.safe_push (insn
);
9035 last_scheduled_insn
= insn
;
9039 /* This function returns a candidate satisfying dispatch constraints from
9043 ready_remove_first_dispatch (struct ready_list
*ready
)
9046 rtx insn
= ready_element (ready
, 0);
9048 if (ready
->n_ready
== 1
9050 || INSN_CODE (insn
) < 0
9051 || !active_insn_p (insn
)
9052 || targetm
.sched
.dispatch (insn
, FITS_DISPATCH_WINDOW
))
9053 return ready_remove_first (ready
);
9055 for (i
= 1; i
< ready
->n_ready
; i
++)
9057 insn
= ready_element (ready
, i
);
9060 || INSN_CODE (insn
) < 0
9061 || !active_insn_p (insn
))
9064 if (targetm
.sched
.dispatch (insn
, FITS_DISPATCH_WINDOW
))
9066 /* Return ith element of ready. */
9067 insn
= ready_remove (ready
, i
);
9072 if (targetm
.sched
.dispatch (NULL_RTX
, DISPATCH_VIOLATION
))
9073 return ready_remove_first (ready
);
9075 for (i
= 1; i
< ready
->n_ready
; i
++)
9077 insn
= ready_element (ready
, i
);
9080 || INSN_CODE (insn
) < 0
9081 || !active_insn_p (insn
))
9084 /* Return i-th element of ready. */
9085 if (targetm
.sched
.dispatch (insn
, IS_CMP
))
9086 return ready_remove (ready
, i
);
9089 return ready_remove_first (ready
);
9092 /* Get number of ready insn in the ready list. */
9095 number_in_ready (void)
9097 return ready
.n_ready
;
9100 /* Get number of ready's in the ready list. */
9103 get_ready_element (int i
)
9105 return ready_element (&ready
, i
);
9108 #endif /* INSN_SCHEDULING */